<html>
  <head>
    <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    <tt>The previous memo outlined a tactic for effectively "migrating"
      a method in a current generic class to a related but different
      signature in an any-generic class, while retaining source and
      binary compatibility with existing clients and subclasses, and
      outlined the list of possibly problematic methods in the
      Collections framework.  </tt><tt><br>
    </tt><tt><br>
    </tt><tt>The effectiveness of this tactic on this set of methods
      ranges from "slam-dunk" to "seems like it could work" to "doesn't
      help."  It would be nice to have one hammer that pounds down all
      the nails, but I'm not sure there is one.  This memo outlines a
      range of complementary tactics that might, in combination with the
      above approach, enable us to cover the waterfront.  </tt><tt><br>
    </tt><tt><br>
    </tt><tt>I'll start with the method Collection.contains(Object).  It
      might at first seem that we want the signature here to be
      contains(</tt><tt>E), but this gets in the way of cases like:</tt><tt><br>
    </tt><tt><br>
    </tt><tt>    dogs.contains(animal)</tt><tt></tt><tt><br>
    </tt><tt><br>
    </tt><tt>or of converting dogs::contains to a Predicate<? super
      Animal></tt><tt> (which is what filter/removeIf would want.)  </tt><tt><br>
    </tt><tt><br>
    </tt><tt>Note that this has little to do directly with value types;
      value types are invariant.  But if we want a single contains()
      method that ranges over any E, it needs to accomodate variance for
      reference instantiations while not falling back on Object as a top
      type.</tt><tt><br>
    </tt><tt><br>
    </tt><tt>One technique for doing so would be to introduce
      contravariant inference variables.  Then we could write contains
      as:</tt><tt><br>
    </tt><tt><br>
    </tt><tt>    <U super E> boolean contains(U u)</tt><tt><br>
    </tt><tt><br>
    </tt><tt>This has three main downsides:</tt><tt><br>
    </tt><tt> - Even though this works, its still not that obvious.  </tt><tt><br>
    </tt><tt> - It's a *lot* of work in the spec and compiler; it pushes
      on all the fragile</tt><tt> bits.  </tt><tt><br>
    </tt><tt> - If that weren't enough, it is a theoretical minefield. 
      Papers like <a class="moz-txt-link-freetext" href="http://www.cis.upenn.edu/~bcpierce/papers/variance.pdf">http://www.cis.upenn.edu/~bcpierce/papers/variance.pdf</a>
      show that adding contravariance to certain type systems result in
      subtyping becoming undecidable.  </tt><tt><br>
    </tt><tt><br>
    </tt><tt>On the other hand, I'm sure many library writers would jump
      for joy to have this in the toolbox; the lack of contravariant
      tvars seems a notable inconsistency in the language.  (</tt><tt>But
      let's not kid ourselves about the costs.)</tt><tt><br>
    </tt><tt><br>
    </tt><tt>It just so happens that this construct works out; it is
      binary- and source- compatible to make a non-generic method
      generic, as long as the erasure of the signature remains the
      same.  So changing contains() or remove() as above would not cause
      subclasses or clients to fail to either link or recompile (in the
      subclass recompilation case, it would be reinterpreted as a raw
      override, which is allowed and compatible.)  And we'd end up with
      a total method that does the right thing both for refs and values</tt><tt>. 
    </tt><tt><br>
    </tt><tt><br>
    </tt><tt>Ignoring the costs and risks, </tt><tt>this technique
      applies to a number of the methods in our rogue's gallery,
      including toArray(), for which we didn't yet have a solution:<br>
      <br>
          <U super E> U[] toArray()<br>
      <br>
      This is compatible with existing clients who are expecting an
      Object[] to come back from toArray() on a collection of reference
      types, and collapses to V[] for any value type, so
      Collection<int>.toArray() returns int[].  (We might still
      want an unchecked warning if the compiler infers U != Object for
      reference E, but that's a separate and easily handled
      consideration.)<br>
      <br>
      Let's call this technique "superation" (yes, its an intentional
      (disgusting) pun.  See
      <a class="moz-txt-link-freetext" href="http://beta.merriam-webster.com/dictionary/suppurate">http://beta.merriam-webster.com/dictionary/suppurate</a>.  And think
      about that the next time you pass a "Super 8" motel on the
      highway.)  With this in our toolbox, the strategy matrix becomes:<br>
      <br>
    </tt><br>
    <tt><tt><br>
      </tt> </tt>
    <table border="1" cellpadding="2" cellspacing="2" width="100%">
      <tbody>
        <tr>
          <td valign="top"><tt><b>Class</b></tt><tt><b><br>
              </b></tt></td>
          <td valign="top"><tt><b>Method</b></tt><tt><b><br>
              </b></tt></td>
          <td valign="top"><tt><b>Possible Approaches</b></tt><tt><b><br>
              </b></tt></td>
        </tr>
        <tr>
          <td valign="top"><tt>Collection</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>contains(Object)</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>Superate</tt><tt> to <U super E>
              contains(U)<br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt><br>
            </tt></td>
          <td valign="top"><tt>remove(Object)</tt><tt><br>
            </tt></td>
          <td valign="top"><tt><br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt><br>
            </tt></td>
          <td valign="top"><tt>removeAll(Collection<?>)</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>Abandon in favor of existing
              removeIf(Predicate<? super E>).  <br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt><br>
            </tt></td>
          <td valign="top"><tt>retainAll(Collection<?>)</tt><tt><br>
            </tt></td>
          <td valign="top"><tt><br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt><br>
            </tt></td>
          <td valign="top"><tt>containsAll(Collection<?>)</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>Migrate to
              containsElements(Collection<? extends E>), or abandon. 
              <br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt><br>
            </tt></td>
          <td valign="top"><tt>toArray()</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>Superate to <U super E> U[]
              toArray()<br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt><br>
            </tt></td>
          <td valign="top"><tt>toArray(T[])</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>Leave as is, superate, or abandon.<br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt>List</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>remove(int)</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>Migrate to removeAt(int).</tt><tt><br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt><br>
            </tt></td>
          <td valign="top"><tt>indexOf(Object)</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>Migrate to Optional-bearing
              findFirst(Predicate<? super E>)</tt><tt><br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt><br>
            </tt></td>
          <td valign="top"><tt>lastIndexOf(Object)</tt><tt><br>
            </tt></td>
          <td valign="top"><tt><br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt>Map</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>containsKey(Object)</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>Superate<br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt><br>
            </tt></td>
          <td valign="top"><tt>containsValue(Object)</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>Superate</tt></td>
        </tr>
        <tr>
          <td valign="top"><tt><br>
            </tt></td>
          <td valign="top"><tt>remove(Object)</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>Superate</tt></td>
        </tr>
        <tr>
          <td valign="top"><tt><br>
            </tt></td>
          <td valign="top"><tt>put(K,V)</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>Leave as is</tt><tt><br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt><br>
            </tt></td>
          <td valign="top"><tt>get(K)</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>Migrate to one (or all) of:<br>
            </tt><tt>Optional<V> map(K)<br>
              mapOrElse(K, V)<br>
              tryMap(K, Consumer<? super V>)<br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt><br>
            </tt></td>
          <td valign="top"><tt>getOrDefault(Object, V)</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>Migrate to mapOrElse, or superate</tt><tt><br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt>Queue</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>poll()</tt><tt>, peek()</tt></td>
          <td valign="top"><tt>Migrate to tryPoll(Consumer) *or*
              optional-bearing method</tt><tt><br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt>Deque</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>poll(), peek()</tt><tt><br>
            </tt></td>
          <td valign="top"><tt><br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt><br>
            </tt></td>
          <td valign="top"><tt>pollFirst(), pollLast()</tt><tt><br>
            </tt></td>
          <td valign="top"><tt><br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt><br>
            </tt></td>
          <td valign="top"><tt>peekFirst(), peekLast()</tt><tt><br>
            </tt></td>
          <td valign="top"><tt><br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><tt><br>
            </tt></td>
          <td valign="top"><tt>removeFirstOccurrence(),
              removeLastOccurrence()</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>Migrate to predicate-accepting method, or
              superate<br>
            </tt></td>
        </tr>
      </tbody>
    </table>
    <br>
    <tt>This is a</tt><tt> more satisfying matrix; not only does
      everything have an acceptable strategy, but some have more than
      one, and the user impact of superating a method is lower (users
      might just not notice), so the perception is that fewer methods
      are affected.  Still, super-bounded tvars are a big hammer for
      such a small foe.  Maybe there's an alternate approach that has
      the effect of superation but doesn't need such a big hammer.  <br>
      <br>
      <br>
      Here's one possibility.  We already have a notion of partial
      methods.  We could have a pair of methods <br>
      <br>
          <where ref E><br>
          Object[] toArray()<br>
      <br>
          <where val E><br>
          E[] toArray()<br>
      <br>
      both of which are reasonable signatures for their restricted
      domains.  Unfortunately, the natural interpretation of this pair
      of methods is that the first is a member of Collection<ref
      T>, and the second is a member of Collection<val T>, but
      there is *no* toArray() method that is a member of
      Collection<any T>!  This means that code that is generic in
      any-T would not see a toArray() method at all.  That's a problem
      (though not as enormous as it initially sounds, there are possible
      mitigating techniques.) <br>
      <br>
      However, it is not unreasonable for the compiler to recognize this
      situation and deal.  Suppose I have some code generic in any-T:<br>
      <br>
          <any T> void foo(Collection<T> c) {<br>
              T[] arr = c.toArray();<br>
          }<br>
      <br>
      Now, the compiler doesn't know whether c is a collection of refs
      or values, but it knows it's one or the other (ref T and val T
      form a partition of any T).  So it could (and in some cases, has
      to anyway) do type checking by parts -- it can typecheck the above
      assignment under the assumption of ref T, and do it again under
      the assumption of val T, and if both succeed (and something else,
      see below), accept the method invocation as valid.  (In this case,
      the ref-T fork should result in an unchecked warning, meaning that
      the merged checking also yields an unchecked warning.)  <br>
      <br>
      The "something else" part is: when doing overload resolution by
      parts, both branches must resolve to overloads that are
      erasure-equivalent to each other.  Which is true for toArray()
      (and for all the cases for which superation would work.)<br>
      <br>
      Now, this is a lot of handwaving, and it doesn't even really
      describe how we think partial methods should actually work (I'd
      like to get rid of the where-val-T slices entirely, this is a
      separate discussion.)  But its a sketch of an option that achieves
      the positive result of superation without engaging the complexity
      of superation.  <br>
      <br>
      <br>
    </tt>
  </body>
</html>