Uploaded image for project: 'Clojure'
  1. CLJ-2089

Sorted colls with default comparator don't check that first element is Comparable

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major
    • Resolution: Completed
    • Affects versions: Release 1.9
    • Fix versions: Release 1.10
    • Labels:
    • Approval:
      Ok
    • Patch:
      Code and Test

      Description

      Sorted maps and sets use the default comparator. The default comparator requires elements to be Comparable. PersistentTreeMap will not actually invoke the comparator until the second element is added to the map/set, so it is possible to create an invalid single element sorted map/set that will blow up only on later use.

      The following examples create invalid "timebomb" collections that will throw ClassCastException if another element is added or if they're used in other ways (because sets are not comparable):

      (sorted-set #{1})
      (conj (sorted-set) #{1})
      (sorted-map #{} 1)
      (assoc (sorted-map) #{} 1)
      

      Example:

      (def s (sorted-set #{1}))  ;; this doesn't fail
      (conj s #{2})              ;; first conj triggers error
      ClassCastException clojure.lang.PersistentHashSet cannot be cast to java.lang.Comparable  clojure.lang.Util.compare (Util.java:153)
      

      Cause: In PersistentTreeMap.add(), in the case where the existing tree is null, the comparator is never invoked and so the default comparator will never throw the ClassCastException seen on later compares. Note that none of this applies for a custom comparator (sorted-set-by and sorted-map-by) - those comparators can do whatever.

      Proposed: In add(), if the map is empty AND the comparator is the default comparator, then check whether the added key is Comparable and throw CCE if not. Note that PersistentTreeMap is also the impl used by PersistentTreeSet so this covers both. The error message is customized to give you a better hint about the problem (and written to be applicable for both maps and sets). In the patch some existing (bad) tests had to be adjusted.

      user=> (def s (sorted-set #{1}))
      ClassCastException Default comparator requires nil, Number, or Comparable: #{1}  clojure.lang.PersistentTreeMap.add (PersistentTreeMap.java:335)
      

      One downside of the current patch is that does not catch the equivalent problem if using a custom comparator and a bad first element. You could maybe do this by calling comp.compare(k,k) (although many comparators, like the default comparator, have an early identity check that would not fail on this). For now, decided that if you supply a custom comparator, it's up to you to not use it with elements that don't work with that comparator.

      Patch: clj-2089.patch

      Screener Notes: The error is a ClassCastException in order to match the exception that would have come later, but is odd in that no class casting was done. Maybe IllegalArgumentException?

        Attachments

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              alexmiller Alex Miller
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: