RFR [15] 6394757: rev2: AbstractSet.removeAll semantics are surprisingly dependent on relative sizes

[Jason Mehrens]

Biasing towards ordering is covered in https://bugs.openjdk.java.net/browse/JDK-8181146 (read the markmail thread link in the ticket) and some of those changes worked there way into
http://hg.openjdk.java.net/jdk/jdk14/file/6c954123ee8d/src/java.base/share/classes/java/util/concurrent/ConcurrentSkipListMap.java#l1708 and http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/ConcurrentSkipListMap.java?r1=1.176&r2=1.177

I think there is some merit in even biasing toward ordering for non-sorted sets/maps to avoid expensive contains calls.  Any change we apply to equals we can usually apply a similar idea to containsAll.

I'm not sure about computing the hash code during equals.  It is not ideal but seems to solve the case you raised. I doubt it passes the compatibility bar for behavior or performance.

Jason

________________________________________
From: Alan Snyder <javalists at cbfiddle.com>
Sent: Wednesday, May 20, 2020 1:53 PM
To: Jason Mehrens
Cc: core-libs-dev
Subject: Re: RFR [15] 6394757: rev2: AbstractSet.removeAll semantics are surprisingly dependent on relative sizes

Do you believe that Set.equals() should behave this way on SortedSets?

On May 20, 2020, at 11:23 AM, Jason Mehrens <jason_mehrens at hotmail.com<mailto:jason_mehrens at hotmail.com>> wrote:

public class SetEquals {

   public static void main(String[] args) {
       Comparator<String> cc = String.CASE_INSENSITIVE_ORDER;
       Set<String> s1 = new TreeSet<>(cc);
       Set<String> s2 = new TreeSet<>(cc);
       s1.add("hello");
       s2.add("Hello");
       System.out.println(equals(s1, s2));
       System.out.println(equals(s2, s1));
       System.out.println(s1.hashCode() == s2.hashCode());
   }

   private static boolean equals(Set<?> s1, Set<?> s2) {
       if (s2 == null) {
           return false;
       }

       if (s1 == s2) {
           return true;
       }

       int s1h = 0;
       int s2h = 0;
       Iterator<?> e1 = s1.iterator();
       Iterator<?> e2 = s2.iterator();

       if (s1 instanceof SortedSet && s2 instanceof SortedSet
               && isSameOrder((SortedSet) s1, (SortedSet) s2)) {
           //TODO: raw type warnings.
           Comparator cmp = ((SortedSet<?>) s1).comparator();
           if (cmp == null) {
               cmp = Comparator.naturalOrder();
           }
           while (e1.hasNext() && e2.hasNext()) {
               Object o1 = e1.next();
               Object o2 = e2.next();

               try {
                   if (cmp.compare(o1, o2) != 0
                           && (!s1.contains(o2) || !s2.contains(o1))) {
                       return false;
                   }
               } catch (ClassCastException cce) {
                   return false;
               }

               s1h += Objects.hashCode(o1);
               s2h += Objects.hashCode(o2);

               //Iteration order should be the same.
               if (s1h != s2h) {
                   return false;
               }
           }
       } else {
           while (e1.hasNext() && e2.hasNext()) {
               Object o1 = e1.next();
               Object o2 = e2.next();

               try {
                   if (!Objects.equals(o1, o2)
                           && (!s1.contains(o2) || !s2.contains(o1))) {
                       return false;
                   }
               } catch (ClassCastException cce) {
                   return false;
               }

               s1h += Objects.hashCode(o1);
               s2h += Objects.hashCode(o2);
           }
       }
       return s1h == s2h && !e1.hasNext() && !e2.hasNext();
   }

   private static boolean isSameOrder(SortedSet<?> s1, SortedSet<?> s2) {
       //null matches natural ordering or unwrap to find a singleton.
       //Avoid calling equals on comparator.
       return Collections.reverseOrder(s1.comparator())
               == Collections.reverseOrder(s2.comparator());
   }
}