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):
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.
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.
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?