Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8218945

ConcurrentSkipListSet.removeAll() uses semantics of wrong collection

    Details

    • Type: Bug
    • Status: In Progress
    • Priority: P4
    • Resolution: Unresolved
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: core-libs
    • Labels:
      None

      Description

      Collection.removeAll() is specified to remove from this collection every element that is contained in the argument collection. This implies that the contains() semantics of the argument collection are used. However, CSLS.removeAll() iterates its argument and calls this.remove(), using the contains() semantics of this set instead of the argument collection.

      (This is complicated by the performance heuristic in AbstractSet.removeAll, which is arguably broken. I've concluded that the contains() semantics of the argument collection must always be used. See JDK-6394757.)

      The following jshell sessions illustrate the anomalous behavior (edited for brevity).

      ==========
      jshell> List<String> removes = List.of("a", "b", "c", "d", "e", "f")
      removes ==> [a, b, c, d, e, f]
      jshell> Set<String> ts = new TreeSet<>(String.CASE_INSENSITIVE_ORDER)
      jshell> ts.addAll(List.of("A", "b", "x"))
      ts ==> [A, b, x]
      jshell> ts.removeAll(removes)
      ts ==> [A, x]
      jshell> ts.addAll(List.of("A", "b", "x"))
      jshell> ts.retainAll(removes)
      ts ==> [b]
      ==========

      The above shows that TreeSet uses the argument List's semantics of containership, namely case-sensitive equals(). Also note that the result of retainAll() is the complement of the result of removeAll(), which is expected. Now on to ConcurrentSkipListSet:

      ==========
      jshell> Set<String> csls = new ConcurrentSkipListSet<>(String.CASE_INSENSITIVE_ORDER)
      jshell> csls.addAll(List.of("A", "b", "x"))
      csls ==> [A, b, x]
      jshell> csls.removeAll(removes)
      csls ==> [x] ***1***
      jshell> csls.addAll(List.of("A", "b", "x"))
      jshell> csls.retainAll(removes)
      csls ==> [b] ***2***
      ==========

      The result of csls.removeAll() at ***1*** indicates that the case-insensitive semantics of csls are used, instead of the case-sensitive semantics of List.

      The result of csls.retainAll() at ***2*** is not a complement of the result of removeAll(), because retainAll() is inherited from AbstractSet and uses the contains() semantics of the argument.

      CSLS should be fixed to iterate "this" and check contains() on its argument. It might be able to inherit from AbstractSet once JDK-6394757 is fixed.

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                martin Martin Buchholz
                Reporter:
                smarks Stuart Marks
              • Votes:
                0 Vote for this issue
                Watchers:
                3 Start watching this issue

                Dates

                • Created:
                  Updated: