Vavr: TreeSet.flatMap - cannot be cast to java.lang.Comparable

[benoitheinrich]

Hi,

I've started to use that great library and just hit an issue when using a TreeSet with a specific comparator, and doing a flatMap on it.

Here is a test case that reproduces the error:

public class TreeSetTest {
    @Test
    public void testFlapMap() {
        final TreeSet<Obj> objs = TreeSet.ofAll((o1, o2) -> o1.field.compareTo(o2.field),
                Stream.of("o1", "o2").map(Obj::new)
        );
        objs.flatMap(o -> List.of(new Obj("nicer " + o.field)));
    }

    private static final class Obj {
        private final String field;

        private Obj(final String field) {
            this.field = field;
        }
    }
}

And this will produce the following exception:

java.lang.ClassCastException: TreeSetTest$Obj cannot be cast to java.lang.Comparable

    at javaslang.collection.Comparators.lambda$naturalComparator$7c28a3e$1(Comparators.java:30)
    at javaslang.collection.RedBlackTreeModule$Node.insert(RedBlackTree.java:670)
    at javaslang.collection.RedBlackTree.insert(RedBlackTree.java:103)
    at javaslang.collection.RedBlackTree.ofAll(RedBlackTree.java:90)
    at javaslang.collection.TreeSet.ofAll(TreeSet.java:180)
    at javaslang.collection.TreeSet.flatMap(TreeSet.java:584)
    at javaslang.collection.TreeSet.flatMap(TreeSet.java:589)
    at TreeSetTest.testFlapMap(TreeSetTest.java:24)

Looking at TreeSet.java:589 the actual implementation does:

    @Override
    public <U> TreeSet<U> flatMap(Function<? super T, ? extends Iterable<? extends U>> mapper) {
        return flatMap(naturalComparator(), mapper);
    }

So here it uses a naturalComparator().
Should it maybe use the comparator provided in the TreeSet instance?

I'm using javaslang 2.0.1 version.

Thanks for the great work guys, and keep going ;)

Cheers,
/Benoit

[danieldietrich]

Hi @benoitheinrich,

the existing comparator is related to elements of type T. We are mapping to elements of type U, therefore we need a new comparator.

If no comparator is specified we take the naturalComparator for elements of type U (even if elements of U are not comparable - that's also the way java.util.SortedSet is working). We can't check the special case where T is U. So in that case flatMap(comparator, mapper) has to be called explicitely be the user:

treeSet.flatMap(treeSet.comparator(), mapper);

I currently can't test it but I think that is the way to go.

Thanks for the kind words :-)

Daniel

[benoitheinrich]

Hi @danieldietrich,

Thanks for the quick answer !! that was really quick ;)

In fact your right, I was doing another test scenario to check how that new comparator would work and indeed, it applies to the mapped type U not the element type T.

Here is the example:

public class TreeSetTest {
    @Test
    public void testFlapMap() {
        final TreeSet<Obj> objs = TreeSet.ofAll((o1, o2) -> o1.field.compareTo(o2.field),
                Stream.of("o1", "o2").map(Obj::new)
        );
        // That works as you're using a TreeSet and so you can specify a Comparator
        objs.flatMap((o1, o2) -> o1.differentField.compareTo(o2.differentField),
                o -> List.of(new OtherObj("nicer " + o.field)));

        // That won't compile as the flatMap(c, f) is only defined on TreeSet
        ((Set<Obj>) objs).flatMap((o1, o2) -> o1.differentField.compareTo(o2.differentField), 
                o -> List.of(new OtherObj("nicer " + o.field)));
    }

    private static final class Obj {
        private final String field;
        private Obj(final String field) { this.field = field; }
    }

    private static final class OtherObj {
        private final String differentField;
        private OtherObj(final String differentField) { this.differentField = differentField; }
    }
}

There it's clear that the comparators are different.

Now the tricky thing is that when you assign your TreeSet to a Set type, then the flatMap(comparator, function) method isn't available anymore.
And because that Set could go quite far in your calls, when you get to do a flatMap then you might not know that the actual implementation is a TreeSet, and so, it will crash as soon as you use flatMap on a non-comparable U type.

Then it means that when you want to use a TreeSet for your Set implementation, then either you need to make all your code aware that it's a TreeSet so you don't hit that issue by providing a compator when using flatMap.

I'm not sure how people in general deal with this kind of issue, and I know that flatMap() is coming from the Traversable trait, but somehow it would be great if the code wouldn't compile with using the TreeSet.flatMap(f) where U is not a Comparable.

I know it's probably not possible, especially if you cast your TreeSet into a Set ;)
At that point the compiler would just read it as if you use Set.flatMap(f) and not the TreeSet one.

So maybe if somehow we could make the code fail sooner in the stracktrace, then it might help people understanding why they get an error like I did ;)
Or maybe make a special note in the documentation to emphasis this special behaviour of the TreeSet?

To be honest, it took me a bit of time to find where the problem was in my code.

[danieldietrich]

Thank you @benoitheinrich, you are right. I haven't thought this through when creating the TreeSet (and TreeMap, and soon TreeMultimap) API.

I think we can make it safe but it would change the semantics of the current implementation. We could provide another comparator that does never fail. It is important to provide a safe API, i.e. one that does not throw unexpectedly at runtime.

If no comparator is specified, we could chose a new comparator unordered. Even better would be to take the naturalComparator, if there exsists an order and the unordered comparator as fallback. But this is not possible in the case of empty collections where we can't take an element to check if it is comparable. Because of type erasure we are not a able to inspect the runtime element type of a collection. Also we can't take the naturalComparator by default and fall back to the unordered comparator because we would have internally to catch a ClassCastException which takes too much time.

The static factory methods, e.g. TreeSet.empty() et al, could still use the naturalComparator. Only flatMap et al would need to use the unordered comparator by default. I think that is a good solution. If the API docs makes it clear how it works, with an additional example (downcasting to a Set and calling flatMap), this sounds like a reasonable solution.

What do you think?

[danieldietrich]

Task: Create singleton javaslang.collection.Comparator.NoOrderComparator (see also #1227), with

int compare(Object o1, Object o2) {
    return 0;
}

[benoitheinrich]

Do you think that an naturalComparatorIfPossible comparator would be possible?

    <T> Comparator<T> naturalComparatorIfPossible() {
        return new Comparator<T>() {
            Boolean useNatural = null;

            @Override
            public int compare(final T o1, final T o2) {
                return useNatural(o1, o2)
                        ? naturalComparator.compare(o1, o2)
                        : unorderedComparator.compare(o1, o2);
            }

            private boolean useNatural(final T o1, final T o2) {
                if (useNatural == null) {
                    useNatural = o1 instanceof Comparable || o2 instanceof Comparable;
                }
                return useNatural;
            }
        };
    }

The check to verify the type of element would occur only once, and wouldn't require a catch to ClassCastException, and this would just add an additional boolean evaluation and a method call.
If you're worried about performance then you could maybe remove the method call and put everything in the compare() method.
Also that comparator should be thread-safe event if mutable as the only state shared is the boolean, and even if it's overridden, it shouldn't be an issue.
That comparator can't be shared across many trees as the useNatural is specific to a tree.

Do you think this could work?

[danieldietrich]

Yes, great idea, I think it should be possible. Comparators are shared between different persistent versions of a collection. Empty collections never call the comparator. Once the element type is determined and therefore the comparator's state is initialized, the comparator can be shared between difference versions of the collection (e,.g. take(0) and then perend(elem) etc.).

Regarding thread-safety I also see no problem. Even if parallel threads execute useNatural(), the returned value is defined in each case. I need to check if there are benefits when we make the instance variable volatile.

Many thanks!

[ruslansennov]

Do you think this could work?

I believe this couldn't work :(

interface T {

}

class C1 implements T, Comparable<C1> {

    @Override
    public int compareTo(C1 o) {
        return 0;
    }
}

class C2 implements T, Comparable<C2> {

    @Override
    public int compareTo(C2 o) {
        return 0;
    }
}

Instances of T can be comparable, not comparable or comparable with different types

[danieldietrich]

@ruslansennov Yes, this is evil. It can also occur when creating empty collections without specifying a Comparator.

I think in practice it will be a rare case. However, it is still unsafe. Java is doing the same, e.g. java.util.stream.Stream.sorted().

In a SortedSet/Map we rely on specific behavior induced by the comparator, e.g. when calling min() and max(). The implementations of Traversable are overloaded there, relying on the RedBlackTree backend, which needs a comparator. Having no order will result in chaos.

Also having a Comparator with 'no order', e.g. comparison is always 0, is not a good idea in a Set. The RedBlackTree will contain at maximum 1 element then because it represents a Set and all elements are equal o_O.

I cannot reproduce the problem with Java collections because there is no default collector that creates a SortedSet:

java.util.SortedSet<String> sortedSet = new TreeSet<>();
sortedSet.add("a");
sortedSet.add("b");
sortedSet
    .stream()
    .flatMap(s -> Arrays.asList(s.hashCode()).stream())
    .collect(Collectors.toSet()); // <-- no toSortedSet present

I'm currently not sure, what is the best way to go on.

[danieldietrich]

In Java we can provoke the same, but it is not so easy to do the wrong thing as with Javaslang because we have to stream/collect forth and back and implement our own collector.

Nevertheless, having a fallback that just works would be great. We cannot use a Comparator that returns 0 for all elements. Instead we can compare the hashCodes (with null values ordered first) as fallback.

Even if there are situations that do not work (as Ruslan has shown), i favor to implement it similar to Benoits suggestion. I see no perfect solution.

Any other thoughts?

package test;

import java.util.Arrays;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.function.BiConsumer;
import java.util.function.BinaryOperator;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.Collector;

public class JavaSortedSetTest {

    public static void main(String[] args) {

        SortedSet<String> sortedSet = new TreeSet<>();
        sortedSet.add("a");
        sortedSet.add("b");

        // Exception in thread "main" java.lang.ClassCastException:
        // test.JavaSortedSetTest$Obj cannot be cast to java.lang.Comparable
        sortedSet
            .stream()
            .flatMap(s -> Arrays.asList(new Obj(s)).stream())
            .collect(toSortedSet());
    }

    static <T> Collector<T, TreeSet<T>, TreeSet<T>> toSortedSet() {
        final Supplier<TreeSet<T>> supplier = TreeSet::new;
        final BiConsumer<TreeSet<T>, T> accumulator = TreeSet::add;
        final BinaryOperator<TreeSet<T>> combiner = (left, right) -> {
            left.addAll(right);
            return left;
        };
        final Function<TreeSet<T>, TreeSet<T>> finisher = treeSet -> treeSet;
        return Collector.of(supplier, accumulator, combiner, finisher);
    }

    static class Obj {
        String s;
        Obj(String s) {
            this.s = s;
        }
    }

}

[kag0]

Hey all. Just ran into this exact same issue and agree with most of what's been said here.
My 2c on the issue: type erasure takes out a lot of good solutions. One available option is to change the signature of SortedSet flatMap(Function<T, Iterable>) in SortedSet to be Set flatMap(Function<T, Iterable>) and add a method SortedSet flatMapSorted(Function<T, U extends Comparable>). The contract of Set says if I have a Set and I flatMap it, I'll get back a Set, with no promises about order. That is something we are capable of fulfilling, and we probably need to, otherwise Set is extremely hard to program against (I'm saying maybe TreeSet.flatMap should return HashSet if there is no other option).
On the scala side, their SortedSet.flatMap returns either a Set or TreeSet depending on what you map to. It might be worth looking into how that is done to see if it can be done in java.

Lastly, I don't think it's been said here, but this same issue probably applies to .map as well.

[danieldietrich]

Hi @kag0, thanks for your thoughts. I will come back to this issue during this week (because of too many parallel tasks already).

• Daniel

[danieldietrich]

I agree that the best solution is to let return our current SortedSet.flatMap at Set instead of a SortedSet.

The same applies to SortedSet.map.

The scan methods look like this:

    // DEV-NOTE: The return type is either Set or SortedSet, depending whether U is Comparable
    @Override
    <U> Set<U> scanLeft(U zero, BiFunction<? super U, ? super T, ? extends U> operation);

    // DEV-NOTE: The return type is either Set or SortedSet, depending whether U is Comparable
    @Override
    <U> Set<U> scanRight(U zero, BiFunction<? super T, ? super U, ? extends U> operation);

Also these have to be revised:

    @Override
    <T1, T2> Tuple2<? extends SortedSet<T1>, ? extends SortedSet<T2>> unzip(Function<? super T, Tuple2<? extends T1, ? extends T2>> unzipper);

    @Override
    <T1, T2, T3> Tuple3<? extends SortedSet<T1>, ? extends SortedSet<T2>, ? extends SortedSet<T3>> unzip3(Function<? super T, Tuple3<? extends T1, ? extends T2, ? extends T3>> unzipper);

    @Override
    <U> SortedSet<Tuple2<T, U>> zip(Iterable<? extends U> that);

    @Override
    <U, R> SortedSet<R> zipWith(Iterable<? extends U> that, BiFunction<? super T, ? super U, ? extends R> mapper);

    @Override
    <U> SortedSet<Tuple2<T, U>> zipAll(Iterable<? extends U> that, T thisElem, U thatElem);

    @Override
    SortedSet<Tuple2<T, Integer>> zipWithIndex();

    @Override
    <U> SortedSet<U> zipWithIndex(BiFunction<? super T, ? super Integer, ? extends U> mapper);

The above are Set methods. The same thing applies for Map methods...

This would be a breaking change :-/

The other idea was to keep the API and internally use an `unordered comparator' instead (if that is possible). Then the resulting SortedSet would be equivalent to an unordered Set.

[kag0]

The breaking change is a tough pill.

Supposing an un-ordered Comparator was possible, would it be possible to tell when it should be used (as opposed to natural ordering) without attempting a Comparable cast? Perhaps something like what @benoitheinrich proposed, but with additional constraints where in a.compareTo(b) b must be an instance of a.getClass().
EDIT: Thought about the additional constraints more. While they would prevent the exceptions @ruslansennov pointed out, the idea has a major flaw where if Comparable were declared at the interface or abstract class then you could end up with an unordered SortedSet of Comparables. nasty.

[danieldietrich]

The breaking change is a tough pill.

That's right. We will not break anything. In fact I do not plan to break anything in near future (opposed than stated in one of my previous blog posts). I've learned that backward compatibility is the most important feature a library has.

Today I had the idea of a _lazy_ comparator. This will first operate on a Comparator that

1. waits for the first non-null value to pass by
2. checks if the value is instanceof Comparable
3. if Yes => switches the comparator to the natural one of the value, if No => falls back to another (unordered?) comparator, e.g. comparing hashCodes!?!?

[kag0]

Doesn't the lazy comparator have the same issue ruslan pointed out? The first non-null element of a set may be a Comparable, but a) that doesn't guarantee that the other non-null elements of the set are Comparable and b) doesn't guarantee that the first element can be compared to any of the other non-null elements.

This is the best I could come up with

// Note: this comparator imposes orderings that are inconsistent with equals.
public class Comparator implements java.util.Comparator {
    public int compare(Object o1, Object o2) {
        if(o1 == o2)
            return 0;
        if((o1 != null && o1.equals(o2)) || (o2 != null && o2.equals(o1)))
            return 0;

        // region problem area
        if(o1 instanceof Comparable && (o2 != null && o1.getClass().isAssignableFrom(o2.getClass())))
            return natural((Comparable)o1, o2);
        // endregion

        return hash(o1, o2);
    }

    private <T> int natural(Comparable<T> o1, T o2){
        return o1.compareTo(o2);
    }

    private int hash(Object o1, Object o2){
        return
                (o1 == null
                    ? 0
                    : o1.hashCode())
                - (o2 == null
                    ? 0
                    : o2.hashCode());
    }
}

This correctly avoids the issue ruslan pointed out, but the problem area opens up an insidious behavior (demonstrated by the last assertion in the test).

public class ComparatorTest {
    @org.junit.Test
    public void compare() throws Exception {
        java.util.Comparator wonkyComparator = new Comparator();

        // ints
        assertEquals(Integer.compare(5, 9), wonkyComparator.compare(5, 9));

        // anon objects
        Object a = new Object(){
            int someField = 7;
        };
        Object b = new Object(){
            String hello = "world";
        };
        System.out.println(wonkyComparator.compare(a, b));
        assertNotEquals(0, wonkyComparator.compare(a, b));
        assertEquals(wonkyComparator.compare(a, b), -wonkyComparator.compare(b, a));

        // same interface, different comparable subclasses
        R1 r1 = new R1();
        r1.val = 1;
        R2 r2 = new R2();
        r2.val = 2;
        System.out.println(wonkyComparator.compare(r1, r2)); // no exception, yay

        // comparable interface, different subclasses
        T1 t1 = new T1();
        t1.val = 1;
        T2 t2 = new T2();
        t2.val = 2;
        assertEquals(t1.compareTo(t2), wonkyComparator.compare(t1, t2)); // oh crud
    }

    interface T extends Comparable<T>{
        int val();
    }

    class T1 implements T{
        int val;

        @Override
        public int val() {
            return val;
        }

        @Override
        public int compareTo(T o) {
            return Integer.compare(val, o.val());
        }
    }

    class T2 implements T{
        int val;

        @Override
        public int val() {
            return val;
        }

        @Override
        public int compareTo(T o) {
            return Integer.compare(val, o.val());
        }
    }

    interface ruslansennov{
    }

    class R1 implements ruslansennov, Comparable<R1>{
        int val;

        @Override
        public int compareTo(R1 o) {
            return Integer.compare(val, o.val);
        }
    }

    class R2 implements ruslansennov, Comparable<R2>{
        int val;

        @Override
        public int compareTo(R2 o) {
            return Integer.compare(val, o.val);
        }
    }
}

[danieldietrich]

Hi @kag0,

I like your idea and have made some modifications.

• We should move null values out of the way (nulls-first strategy).
• We should use an existing Comparator before testing for equality (which might be costly). That is how we expect a SortedSet to work by default.
• We should take a shortcut if type(o1) == type(o2). The type comparison is fast and we may safe a second equals check, which may be cost-intensive.
• I think the hash(o1, o2) method is a good solution as fallback for non-equal objects. (see also notes below)

final class ObjectComparator<T> implements java.util.Comparator<T>, Serializable {

    private static final long serialVersionUID = 1L;

    private static final ObjectComparator<?> INSTANCE = new ObjectComparator<>();

    private ObjectComparator() {
    }

    @SuppressWarnings("unchecked")
    static <T> ObjectComparator<T> instance() {
        return (ObjectComparator<T>) INSTANCE;
    }

    @Override
    public int compare(T o1, T o2) {
        if (o1 == o2) {
            return 0;
        } else if (o1 == null) {
            return -1;
        } else if (o2 == null) {
            return 1;
        } else {
            final Class<?> type1 = o1.getClass();
            final Class<?> type2 = o2.getClass();
            if (type1 == type2) {
                if (o1 instanceof Comparable) {
                    return natural(o1, o2);
                } else if (o1.equals(o2)) {
                    return 0;
                } else {
                    return hash(o1, o2);
                }
            } else {
                if (o1 instanceof Comparable && type1.isAssignableFrom(type2)) {
                    return natural(o1, o2);
                } else if (o2 instanceof Comparable && type2.isAssignableFrom(type1)) {
                    return -natural(o2, o1);
                } else if (o1.equals(o2) || o2.equals(o1)) {
                    return 0;
                } else {
                    return hash(o1, o2);
                }
            }
        }
    }

    @SuppressWarnings("unchecked")
    private static <T> int natural(T o1, T o2) {
        return ((Comparable<T>) o1).compareTo(o2);
    }

    private static int hash(Object o1, Object o2) {
        return o1.hashCode() - o2.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        return obj == this;
    }

    @Override
    public String toString() {
        return "ObjectComparator";
    }

    /**
     * Instance control for object serialization.
     *
     * @return The singleton instance of FallbackComparator.
     * @see java.io.Serializable
     */
    private Object readResolve() {
        return INSTANCE;
    }

}

Note: We assume that no hashCode collisions can occur, i.e. o1.hashCode() != o2.hashCode() for two different objects o1, o2. Technically we assume that the hashCode of an object corresponds to the memory address of the object. I don't know if this assumption still holds. Java's int is 32 bit, our machines address 64 bit memory. However, this problem applies to most equals methods of Javaslang.

Checking for hashCode collisions would be problematic. The first check obj == this cannot be performed any more. If we got to the hashCode branch of our if-statement we already know that the objects are not equal. This is the reason that hash(o1, o2) has to return a value different from 0. Because in the case of a collision the value is arbitrary, say -1, the whole order is provably arbitrary in the general case. The whole hashCode comparison makes no sense any more. What happens if we just return -1? I think the the RedBlackTree should still work.

Update: I understand the // oh crud problematic. It is no viable solution to search (once) for the most common comparator of two objects o1, o2. Because beside T1 and T2 (in your example) there might be also additional types T3, T4, ... like this:

     O------------------------
    /                         \
   T extends Comparable<T>     T'
  / \                         / \
T1   T2                     T3   T4

Example:

Set<O> set = Set.of(t1, t2, t3, t4);

where t1 of type T1, t2 of type T2, ...

[danieldietrich]

...we could search the type hierarchy

if (o1 instanceof Comparable) {
    if (type1.isAssignableFrom(type2)) {
        ...
    } else if (getTypeThatImplementsComparable(o1).isAssignableFrom(type2)) {
        ...
    } else ...
}


Map<Class, Class> cache = new ConcurrentHashMap<>();;

Class<?> getTypeThatImplementsComparable(Object o) {
    cache.computeIfAbsent(o.getClass(), c -> searchTypeHierarchy(c));
}

Class<?> searchTypeHierarchy(Class c) {
    ...
}

Will take a look tomorrow if this will work.

Update: Because such a Comparator would be stateful, it could either not be a singleton any more or the cache has to be static. The latter case might be a bottleneck when the singleton comparator is used by (many?) threads in parallel... However, I tend to use a static cache because the number of types of an application that implement comparable are finite and searching the hierarchy is relatively cost-intensive.

[danieldietrich]

There is still a problem (I already mentioned above: "Checking for hashCode collisions would be problematic."): hash(o1, o2) can be 0 for o1 != o2.

Maybe that can be fixed by returning an arbitrary int != 0 in that case, e.g. -1.

But if we do so, the whole hash(o1, o2) makes no sense any more. We should return -1 instead. Especially compare(o1, o2) == -1 == compare(o2, o1) in the unordered case. Don't know if that makes still sense regarding the RedBlackTree implementation...

Update: Of course this does not make any sense at all (using -1 instead of hash(o1, o2)) because binary search within the tree isn't possible any more. It is undecidable if we should further search in the left branch or in the right branch of the tree.

Update 2: It would be sufficient if the comparator returns an int ∈ {-1, 0, 1}. Given that we could also use unique long values to compare objects. But object addresses (JVM spec: 'type references') cannot be used because addresses may change during garbage collection (GC).

Update 3: o1.hashCode() - o2.hashCode() is not a good solution in general. See Oracle docs:

"This trick does not work in general because the signed integer type is not big enough to represent the difference of two arbitrary signed integers."

[ruslansennov]

Sorry, but isAssignableFrom is GWT-incompatible...

[danieldietrich]

I know but I see no other solution than using reflection - or breaking backward compatibility by returning Set instead of SortedSet.

Even in the reflection-variant that detects hash-collisions, there might come a SecurityManager into the way (see code below).

This looks way too complicated. The simplest solution seems to be the best: breaking backward-compatibility :-/

Update/Note: I think also a cycle detection is needed in the solution below (for mutable objects that contain a self-reference in a field...).

final class ObjectComparator<T> implements java.util.Comparator<T>, Serializable {

    private static final long serialVersionUID = 1L;

    private static final ObjectComparator<Object> INSTANCE = new ObjectComparator<>();

    private ObjectComparator() {
    }

    @SuppressWarnings("unchecked")
    static <T> ObjectComparator<T> instance() {
        return (ObjectComparator<T>) INSTANCE;
    }

    @Override
    public int compare(T o1, T o2) {
        if (o1 == o2) {
            return 0;
        } else if (o1 == null) {
            return -1;
        } else if (o2 == null) {
            return 1;
        } else {
            final Class<?> type1 = o1.getClass();
            final Class<?> type2 = o2.getClass();
            if (type1 == type2) {
                if (o1 instanceof Comparable) {
                    return naturalOrder(o1, o2);
                } else if (o1.equals(o2)) {
                    return 0;
                } else {
                    return pseudoOrder(o1, o2);
                }
            } else {
                if (exisitsCommonComparableType(type1, type2)) {
                    return naturalOrder(o1, o2);
                } else if (existsCommonComparableType(type2, type1)) {
                    return -naturalOrder(o2, o1);
                } else if (o1.equals(o2) || o2.equals(o1)) {
                    return 0;
                } else {
                    return pseudoOrder(o1, o2);
                }
            }
        }
    }

    @SuppressWarnings("unchecked")
    private static int naturalOrder(Object o1, Object o2) {
        return ((Comparable<Object>) o1).compareTo(o2);
    }

    private static int pseudoOrder(Object o1, Object o2) {
        final int hash1 = o1.hashCode();
        final int hash2 = o2.hashCode();
        // just return -1/1 because an overflow of hash1 - hash2 could also result in a collision
        if (hash1 < hash2) {
            return -1;
        } else if (hash1 > hash2) {
            return 1;
        } else {
            // resolve hash collision
            final String name1 = o1.getClass().getName();
            final String name2 = o2.getClass().getName();
            final int nameCompare = name1.compareTo(name2);
            if (nameCompare != 0) {
                return nameCompare;
            } else {
                try {
                    // o1.getClass() == o2.getClass()
                    Class<?> clazz = o1.getClass();
                    while (clazz != null) {
                        // nameCompare == 0 => fields of o1 and o2 are the same
                        final Field[] fields = clazz.getDeclaredFields();
                        for (Field field : fields) {
                            field.setAccessible(true);
                            final Object value1 = field.get(o1);
                            final Object value2 = field.get(o2);
                            final int fieldOrder = INSTANCE.compare(value1, value2);
                            if (fieldOrder != 0) {
                                return fieldOrder;
                            }
                        }
                        // if all fields are the same then go to super class and compare fields
                        clazz = clazz.getSuperclass();
                    }
                    return 0;
                } catch(Throwable x) {
                    // there is nothing more we can do at this point to induce a pseudo object-order
                    throw new IllegalStateException("Error comparing " + o1 + " and " + o2, x);
                }
            }
        }
    }

    private static boolean existsCommonComparableType(Object o1, Object o2) {
        ...
    }

    @Override
    public boolean equals(Object obj) {
        return obj == this;
    }

    @Override
    public String toString() {
        return "ObjectComparator";
    }

    /**
     * Instance control for object serialization.
     *
     * @return The singleton instance of ObjectComparator.
     * @see java.io.Serializable
     */
    private Object readResolve() {
        return INSTANCE;
    }

}

This whole thing above is a big _smell_...

[kag0]

 if (hash1 < hash2) {
  return -1;
} else if (hash1 > hash2) {
  return 1;
}

This seems reasonable. I agree that the reflection is some intense code smell though. Just returning -1 seems like the only plausible way to resolve the hash collision, but that itself smells as well.

[danieldietrich]

Just returning -1 seems like the only plausible way to resolve the hash collision, but that itself smells as well.

It is not only a smell, it is a *_blocker_ for that solution. Imagine the TreeSet.contains(value) method. The underlying RedBlackTree performs a binary search along the left/right tree branches. If we just return -1 (see above) then the 'real' comparison result may be 1 and the binary search goes terribly wrong because we do not find node that is already contained in the tree.

I agree that it is a tough decision to break the API by returning a Set instead of a SortedSet. But 'inventing' a comparator is also no good idea. In many cases operations on SortedSets having that comparator will be reasonable fast but I guess there exist executions where it starts to get relatively slow. This is unexpected behavior and may create headaches.

I see no other solution that returning a Set.

[kag0]

I see no other solution that returning a Set.

Agreed. I think diligence has been done to find a solution to avoid a non breaking-change, but there is none that I can conceive.

[danieldietrich]

On help let's discuss it first.

[pivovarit]

Even in the reflection-variant...

Just one more note, playing around with reflection means extra inconvenience for users playing around with GraalVM and native images.

Not really a no-go, but would require users digging into the internals to identify all reflection-touched classes, and apply a custom configuration to make it work.

---

I've done a quick PoC, and to be honest... it doesn't really look bad.
Have a look: https://github.com/vavr-io/vavr/pull/2546

I allowed myself to extrapolate the same idea over SortedSet#map as well(same issue).

[SergejIsbrecht]

@pivovarit , you could include a file in the jar, which will tell GraalVM to include said files in the native-image generation.

I think netty is already doing it.

https://medium.com/graalvm/simplifying-native-image-generation-with-maven-plugin-and-embeddable-configuration-d5b283b92f57

[danieldietrich]

@pivovarit you solution is the right one, reflection is a no go. I was on the wrong path when fiddling around with reflection in order to make it work. The simplest form is often the best way.

[danieldietrich]

@SergejIsbrecht it would be best if we can circumvent reflection completely. Pattern matching for example will be deprecated and replaced by Java's native pattern matching (Java 14+). There are only a few places where we use Class.* methods. Maybe we can get rid of them.

I would not add explicit support for GraalVM until someone is starting to use it. I'm not convinced that GraalVM is relevant at the moment. There are too many corners and edges that make GraalVM look like an academic project instead of ready-to-go. Let's wait a bit...

[pivovarit]

There are only a few places where we use Class.* methods. Maybe we can get rid of them.

...and that would give us full support for GraalVM, luckily there's not much hackery going on here :)

I don't think we need to add explicit support, just wanted to raise a point that becomes more and more relevant recently.

[nfekete]

Lack of reflection is also good for cross compilation to JavaScript through GWT and/or j2cl.

[danieldietrich]

Fixed with #2546