<html>
  <head>
    <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    <tt>Returning back to the short-term goal of migrating the
      Collections API...  I realize that a certain degree of "tell me
      the story again for X?" is needed to meaningfully respond, but I'd
      like to bring the focus back to the core APIs (and secondarily the
      impact on anyfying generic APIs in general.)  <br>
      <br>
      I think Map.get offers us an existence proof that *some* degree of
      API evolution is needed here.  So I don't think there's a credible
      "do nothing" approach.  Still, minimizing the impact seems a
      reasonable goal.  <br>
      <br>
      We have a set of credible tools for evolving the APIs -- migrating
      ref-specific methods to more suitable total alternatives (remove
      -> removeAt), abandoning some methods to "reference purgatory"
      where there is already a suitable total alternative (e.g.,
      abandoning removeAll in favor of the existing removeIf added in
      8), and some form of "superation".  Plenty of additional work is
      needed to find a way to express superation in way that's not
      painfully ugly, but we can address that after the concept has
      proven itself.<br>
      <br>
      So, I propose we return to the topic of Collection APIs.  In
      addition to making collections safe for values, we also have some
      limited opportunity to fix errors in the API, within reason, if
      there are any that rise to the appropriate threshold.  (</tt><tt><tt>More
        intrusive migration -- such as busting the 32-bit index
        limitations -- is likely to be possible with additional
        linguistic tools, but I'd like to save that for another round.) 
        Further, let's focus (for now) on the perspective of clients,
        not implementors.  <br>
        <br>
        Under any of the proposed changes:<br>
         - existing binary clients will continue to work unchanged<br>
         - existing sources can be recompiled and will work without
        change<br>
         - if a client is anyfied (either by anyfying a generic method,
        or by naming a value instantiation of a generic class), then its
        possible some method calls will no longer exist.  However, since
        the client is changing the source, this is not a compatibility
        issue, it is only a migration burden (and one that can be
        mitigated to some degree by tooling.)<br>
      </tt><br>
    </tt><br>
    <div class="moz-cite-prefix">On 12/16/2015 2:43 PM, Brian Goetz
      wrote:<br>
    </div>
    <blockquote cite="mid:5671BEC8.8010508@oracle.com" type="cite">
      <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
      <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><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 moz-do-not-send="true"
          class="moz-txt-link-freetext"
          href="http://www.cis.upenn.edu/%7Ebcpierce/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 moz-do-not-send="true"
          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> </blockquote>
    <br>
  </body>
</html>