<html>
  <head>
    <meta http-equiv="content-type" content="text/html; charset=utf-8">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    <tt>[ sending again with HTML enabled so the tables don't get
      mangled ... and again ]<br>
      <br>
      I'd like to start with the "What about Collections" discussion. 
      While this topic is inextricably linked to all the other topics
      (value types, generic specialization, nullability, etc), to avoid
      getting overwhelmed, let's start by trying to keep our focus on
      the Collections API and the process of migrating it into an
      anyfied world.  So, I'll offer an ahead-of-time warning: there's
      going to be lots here that you will want to question, and to many
      of those questions I'm going to answer "OK, but let's come back to
      that later", because I'd like to stay focused for the time being
      on the Collection-related issues.  (</tt><tt>Let's also try to
      create separate threads for separate discussion topics, though I
      know this is harder to remember to do.)<br>
      <br>
      Most of these are already prototyped in some form in the Valhalla
      repos (which at least demonstrates that they are plausible.)<br>
    </tt><tt><br>
    </tt><tt><br>
    </tt><tt>Background</tt><tt> Material</tt><tt><br>
    </tt><tt>-------------------</tt><tt><br>
    </tt><tt><br>
    </tt><tt>The last "State of the Specialization" (<a
        class="moz-txt-link-freetext"
href="http://cr.openjdk.java.net/%7Ebriangoetz/valhalla/specialization.html"><a class="moz-txt-link-freetext" href="http://cr.openjdk.java.net/~briangoetz/valhalla/specialization.html">http://cr.openjdk.java.net/~briangoetz/valhalla/specialization.html</a></a>,
      Dec 2014) outlines an early approach towards the specialization
      challenges and features.  My talk at JVMLS 2015 (<a
        class="moz-txt-link-freetext"
        href="https://www.youtube.com/watch?v=uNgAFSUXuwc"><a class="moz-txt-link-freetext" href="https://www.youtube.com/watch?v=uNgAFSUXuwc">https://www.youtube.com/watch?v=uNgAFSUXuwc</a></a>)
      outlines the progress that had been made between last December and
      August.  The State of the Values (<a class="moz-txt-link-freetext"
        href="http://cr.openjdk.java.net/%7Ejrose/values/values-0.html">http://cr.openjdk.java.net/~jrose/values/values-0.html</a>)
      outlines the basic model for value types.  If you've not
      read/viewed these, that's a g</tt><tt>ood place to start.</tt><tt><br>
    </tt><tt><br>
    </tt><tt><br>
    </tt><tt>Core </tt><tt>Goals</tt><tt><br>
    </tt><tt>----------</tt><tt><br>
    </tt><tt><br>
    </tt><tt>The key requirement that drove many of the design choices
      in Java 5 when adding generics is *gradual migration
      compatibility*.  This means it must be possible to evolve a
      non-generic class to be generic in a manner that is
      binary-compatible and source-compatible for both clients and
      subtypes.  So an existing client or subtype should continue to
      work whether it is recompiled or not, and generified or not, and
      it should be equally practical to generify subtypes and clients at
      the same time as a library class, or later, or never.  </tt><tt><br>
    </tt><tt><br>
    </tt><tt>We adopt similar goals for "anyfication" -- anyfying a
      class should be binary- and source-compatible for clients and
      subclasses, and it should be possible to anyfy a generic class
      without requiring that either its clients or subclasses be
      anyfied, and whether or not they are recompiled.</tt><tt><br>
    </tt><tt><br>
    </tt><tt><br>
    </tt><tt>Basic Model, Ultra-</tt><tt>s</tt><tt>ummarized</tt><tt><br>
    </tt><tt>------------</tt><tt>-----------------</tt><tt><br>
    </tt><tt><br>
    </tt><tt>Just as the requirement of gradual migration compatibility
      was a significant design constraint in Java 5 (and which pushed us
      strongly towards erasure), this requirement is going to be a
      significant constraint here.  Essentially, this means that
      parameterizations like ArrayList<String> need to continue to
      be erased (otherwise they'd not be binary compatible), but
      parameterizations like ArrayList<int> need to be reified
      (since we cannot erase int to Object without boxing, and if boxing
      were good enough, we wouldn't be bothering at all.)  This pushes
      us towards an interpretation of anyfied generics that is erased
      over reference instantiations and reified over value
      instantiations.  </tt><tt><br>
    </tt><tt><br>
    </tt><tt>At the same time, there is code that is valid under the
      assumption that T <: Object that would not be valid if T can
      take on 'int'.  These include domain assumptions (e.g., assignment
      to null) and identity-based assumptions (a T can be used as a
      monitor lock.)  Accordingly, we cannot simply reinterpret existing
      reference-generic code to be any-generic; we need some indication
      from the user that they are opting into the broadened genericity
      domain (and therefore willing to accept the limitations of this
      broadened domain.)  Our working model for this is to annotate the
      declaration of a type variable with an "any" modifier (e.g.,
      "class Foo<any T>").  We sometimes use the abbreviation
      'tvar' to describe a type variable, and 'avar' to describe an
      any-type variable (similarly, </tt><tt>'ivar' for an inference
      type variable.)  </tt><tt><br>
    </tt><tt><br>
    </tt><tt>Conceptually, the enhanced generics model is simple:</tt><tt><br>
    </tt><tt> - Non-anyfied generic code means exactly the same thing in
      Valhalla as it does in Java 5-9;</tt><tt><br>
    </tt><tt><br>
    </tt><tt> - A reference instantiation of an anyfied generic class
      means exactly the same thing in Valhalla as </tt><tt>it does
      under erased generics; </tt><tt><br>
    </tt><tt><br>
    </tt><tt> - A class or method tvar declaration can be annotated with
      'any', in which case it can range over value types (including
      primitives) as well as reference types.  There are some
      restrictions on what you can do to an avar-typed variable to
      reflect the fact that values may not be nullable, have no monitor
      locks, that they don't participate in a subtyping relationship
      with Object (instead, they have a boxing conversion to Object),
      and that a V[] is not a subtype of Object[]</tt><tt>;</tt><tt><br>
    </tt><tt><br>
    </tt><tt> - There is a new wildcard type, Foo<any>, which is a
      supertype of both value and reference instantiations of Foo</tt><tt>. 



    </tt><tt><br>
      <br>
      The enhanced model embraces erasure more explicitly than the
      current model.  <br>
    </tt><tt><br>
    </tt><tt><br>
    </tt><tt>Migration Ch</tt><tt>allenges</tt><tt><br>
    </tt><tt>--------------------</tt><tt><br>
    </tt><tt><br>
    </tt><tt>Ideally, we could just sprinkle 'any' over our codebase,
      and be done -- and hopefully for many classes, this is all that
      will be required.  But for some classes, there may be migration
      challenges, which </tt><tt>come in two forms: </tt><tt><br>
    </tt><tt><br>
    </tt><tt> - A method signature is fundamentally incompatible with
      anyfication (such as Map.get(), which returns null when the
      mapping is not present, which makes no sense if V=int</tt><tt>);</tt><tt><br>
    </tt><tt><br>
    </tt><tt> - The existing implementation appeals to assumptions of
      object-ness, and needs to be adjusted</tt><tt>.  </tt><tt><br>
    </tt><tt><br>
    </tt><tt>For the purposes of this memo, I'm going to restrict myself
      to the first category; we'll come back to the second category
      later.  Here's a more-or-less complete list of methods in
      Collections that may need some sort of migration help.  </tt><tt>A
      blank cell indicates "same as above."</tt><tt><br>
    </tt><tt><br>
    </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>Issues</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>Assumes all Rs are castable to Object
              without boxing.</tt><tt><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>Should take Collection<? extends E></tt><tt>. 



              Collection<?> not a supertype of all instantiations.</tt><tt> 
              <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><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>Returns Object[], which is not a
              supertype of V[] for any value type V.  </tt><tt><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>Not strictly problematic, but relies on
              runtime checking that E <: T and on reflection for
              implementation.  </tt><tt><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>Not strictly problematic, but if
              remove(Object) becomes remove(T), will be a confusing
              overload.</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>Same as contains(Object).  Also, would be
              better as a lambda-consuming method, now that we have
              lambdas.  </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>Same as contains(Object)</tt><tt><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><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>put(K,V)</tt><tt><br>
            </tt></td>
          <td valign="top"><tt>Returns what was there before, or null if
              there was no mapping.  Not strictly problematic, but
              doesn't project so well to non-nullable Vs.</tt><tt>  <br>
            </tt></td>
        </tr>
        <tr>
          <td valign="top"><br>
          </td>
          <td valign="top"><tt>putIfAbsent, replace, computeIfAbsent</tt><br>
          </td>
          <td valign="top"><br>
          </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>Uses null to signal no mapping<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>Same as contains(Object)</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>Uses null to signal no element</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>Same as remove(Object)<br>
            </tt></td>
        </tr>
      </tbody>
    </table>
    <tt><br>
    </tt><tt><br>
    </tt><tt>It has often been suggested that "maybe it is time for
      Collections 2.0"; some would like to declare this to be the end of
      the road for existing collections.  However, redoing collections
      is only part of the battle; the Collection types are riddled
      throughout the JDK and other libraries, so we would need a
      mechanism for migrating all the methods that consume/dispense
      collections, and if we were to build new collections, saddling
      them with compatibility with old collections would be a big stone
      to hang around their neck.  So I think this path is less appealing
      that </tt><tt>it </tt><tt>might first appear.</tt><tt>  However,
      the techniques described here allow us to fix some of the errors
      of the past.<br>
    </tt><tt><br>
    </tt><tt><br>
    </tt><tt>Partial Methods</tt><tt><br>
    </tt><tt>---------------</tt><tt><br>
    </tt><tt><br>
    </tt><tt>Our approach is guided by the following observation: not
      all methods declared in a generic class Foo<any T> need be
      members of all instantiations of Foo; it is reasonable for some
      members to be restricted to certain instantiations.  </tt><tt>In
      particular, the instantiation Foo<all type vars instantiated
      with erased ref> is an important distinguished instantiation. 
      <br>
    </tt><tt><br>
    </tt><tt>If a method m() in Foo<any T> is a member of all
      instantiations of Foo<T>, we say m() is a *total* method. 
      Otherwise we call it a *restricted* or *partial* method.  For each
      method in an existing generic class to be anyfied, it could be
      made a total method in the new anyfied class, or it could be
      restricted to reference instantiations -- and either approach is
      fully compatible with existing clients and subclasses.  </tt><tt>This



      provides us a migration path to "leave behind" certain problematic
      methods (making them members only of reference instantiations),
      and also to add new methods as long as there is a default
      implementation at least for reference instantiations.  </tt><tt><br>
    </tt><tt><br>
    </tt><tt>As a simple illustration of this approach, let's say that
      we want to effectively rename the method List.remove(int) to
      removeAt(int).  Clearly we cannot simply take away remove(int);
      existing clients would fail to link.  Similarly we cannot simply
      add a new method removeAt(int) without a default; then existing
      subclasses would fail to compile.  </tt><tt><br>
    </tt><tt><br>
    </tt><tt>What we do here is (using a strawman syntax) add a new
      total method, with a ref default, and demote the existing method
      to a partial method on ref instantiations: </tt><tt><br>
    </tt><tt><br>
    </tt><tt>interface List<any T> {</tt><tt><br>
          // A new, total method<br>
    </tt><tt>    void removeAt(int i);  </tt><tt><br>
      <br>
          // demote the old method to ref-only<br>
    </tt><tt> </tt><tt>    <where ref T>  // Just a strawman
      syntax</tt><tt><br>
    </tt><tt>    void remove(int i);</tt><tt><br>
    </tt><tt><br>
          // give the new method a default in terms of the old, for ref<br>
    </tt><tt>    <where ref T></tt><tt><br>
    </tt><tt>    default void removeAt(int i) { remove(i); }</tt><tt><br>
    </tt><tt>}</tt><tt><br>
    </tt><tt><br>
    </tt><tt>Now:<br>
       - Clients of List<ref T> can invoke either remove(int) or
      removeAt(int), and both will do the same thing; this allows
      existing clients to (if they want) migrate away from the old
      method completely, since removeAt(int) is total, or keep using the
      old method, at their choice </tt><tt><tt>(IDEs can also provide
        migration help);<br>
        <br>
      </tt> - New clients of List<any T> can only use
      removeAt(int) -- they won't even *see* remove(int) when they ask
      their IDE to auto-complete -- and this is not a compatibility
      issue as there were no existing clients of List<any T>;<br>
      <br>
       - Existing (ref) subclasses of List<T> still see the same
      set of abstract methods, and therefore continue to work exactly as
      before;<br>
      <br>
       - When anyfying a subclass of List<T>, now you have to
      provide a new implementation for removeAt(int), but this is OK
      because *you* have decided to anyfy your class, and it is
      reasonable to expect some possible code changes in this situation;<br>
      <br>
       - Further, AbstractList can insulate most subclasses from this
      change.<br>
      <br>
      This gives us at least two tactics for dealing with problematic
      methods:<br>
      <br>
       - Migration: leave the old method in the "ref layer", and create
      a new total method with a ref-default in the "any layer", as with
      the removeAt example above;<br>
      <br>
       - Abandonment: leave the old method in the ref layer, and do
      nothing else, which may be suitable if an alternate idiom already
      exists (e.g., we could abandon removeAll because now we can
      express removeAll(c) as removeIf(c::contains), without adding any
      new method.)  <br>
      <br>
      With the controlled-migration option, the primary impediment is
      that many of the good names are already taken.  <br>
      <br>
      These two tactics get us much of the way there, but not all the
      way there.  I'm going to close this note with where these tactics
      get us, and then open a separate note for some of the options for
      the remaining cases.  The following table shows some
      possibilities.  There's plenty of time to bikeshed on the names. 
      <br>
      <br>
    </tt><tt><br>
    </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>Migrate to containsElement(E)</tt><tt><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>Migrate to removeElement(E)<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>Migrate to removeElements</tt><tt>(Collection<?



              extends T>).  <br>
              Alternately, 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>Same<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>).<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>Nothing good yet ...<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, or abandon in favor of new
              method toArray(IntFunction<E[]>), like Stream has.<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>Leave as is, or 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>Migrate to findLast(Predicate<? super
              E>)<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>Migrate to hasKey(K)<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>Migrate to hasValue(V)<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>Migrate to removeMapping(K)<br>
            </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; accept that we cannot
              distinguish between "nothing was there before" and
              "default value was there before" (as is true with null
              today.)</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, as above</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
              simply migrate to new name<br>
            </tt></td>
        </tr>
      </tbody>
    </table>
    <tt><br>
    </tt><tt><br>
      Notes:<br>
      <br>
      For Collection.contains() and remove(), while it may be tempting
      to try and narrow the argument type from Object to T, this is
      likely problematic.  In the following case, we can't express
      something that seems pretty natural:<br>
      <br>
          Collection<Animal> animals = ...<br>
          Collection<Dog> dogs = ...<br>
          Dog d = ...<br>
      <br>
          // Can't say these<br>
          for (Animal a : animals)<br>
              if (dogs.contains(a)) ...<br>
          animals.removeIf(a -> dogs.contains(a))<br>
      <br>
      Its actually pretty convenient for contains/remove to accept
      anything that might be a member of the collection, but Object is
      not the top type we're looking for here (since values require
      boxing to convert to Object.)  So neither the status quo (accept
      Object) nor recasting to a T-accepting method is all that great. 
      (But see next memo for an alternative.)  Its not clear whether all
      the other Object-accepting methods need the same treatment, or if
      migration to an E-accepting method is acceptable there.  <br>
      <br>
      For removeAll/retainAll, we probably just want to abandon in favor
      of the more powerful removeIf added in 8.  (Kevin/Louis -- would
      be good to get stats on actual usage of removeAll/retainAll.)  <br>
      <br>
      For Map.get(), it really sucks that the good name is taken but the
      existing signature is terminally polluted with nullness (even for
      non-null-supporting maps.)  We can migrate to multiple new methods
      (most of which have defaults in terms of the others): <br>
          Optional<V> map(K k)<br>
    </tt><tt><tt>    V mapOrElse(K k, V defaultV)<br>
      </tt>    boolean tryMap(K k, Consumer<? super V>)<br>
      <br>
      With Optional as a value type, there is essentially no cost
      (either footprint or invocation overhead) for using Optional over
      a naked reference.  So the first sig is not as problematic as it
      might look.  The second has an obvious default in terms of the
      first.  The Optional version, though, has an issue: if the map can
      contain null values, there's no way to express that.  However, I
      think its OK if this method throws on null values -- the other
      three get-like methods (the two here plus legacy get()) can all
      express null values.  (So null-lovers don't get to enjoy the
      Optional goodness.  More motivation for them to give up on their
      nulls!)<br>
      <br>
      <br>
    </tt>
  </body>
</html>