Invalid Diff because of duplicate hashes of global ids

[MaxKlotz]

Comparing two collections by using <T> Diff compareCollections(Collection<T> oldVersion, Collection<T> currentVersion, Class<T> itemClass);.
The elements in the collection are the same type.
The elements in the collection are entities.

Expectation:
All objects, identified by global id, that are present in the currentVersion, but missing in oldVersion, are present in the NewObject changes.

Reality:
Some entites, that are new, to not produce a NewObject change.

...

Steps To Reproduce

1. Create two collections.
2. Add elements to the collection with a different ID, that produces the same hash value. e.g. "FB" and "Ea"
3. Compare the two lists by using <T> Diff compareCollections(Collection<T> oldVersion, Collection<T> currentVersion, Class<T> itemClass);

Javers' Version
7.3.8

Additional context
I identified the root cause of this:
In GraphPair the graphs are built and the comparison in difference is done by using a hasher.
The wrong result happens because 2 different global IDs produce the same hash value.
So the oldVersion contains a different element with the same hash, thus it is not recoignized as a new object in the currentVersion.

[MaxKlotz]

Maybe a possible solution would be overriding the getHashCode() for ObjectNodes instead of adding the hasher function as parameter.
Then the ObjectNode can be used as the key.
The HashMap would handle the duplicate keys and it should still be fast.

I only saw 1 usage of difference with the hasher function and it is in the constructor of GraphPair.

[bartoszwalacik]

hi Max, thanks for reporting, please create a failing test case, see https://github.com/javers/javers/blob/master/CONTRIBUTING.md#guidelines-for-bug-reporting
also , the fastest way to fix this bug is to contribute a PR

[jamnaritesh]

Hi @bartoszwalacik / @MaxKlotz,
Sorry for hijacking this thread but we have a production deployment that is facing the same issue every now and then. I am keen on helping to fix it.

@bartoszwalacik I've created a test case that depicts the good and bad scenario.
jamnaritesh@0de44d8

As @MaxKlotz rightly pointed out, the issue is because of hashCollision of string objects + no equality measure when removing elements from the map.

public static <E> Collection<E> difference(Set<E> first, Set<E> second, Function<E, Integer> hasher) {
        if (first == null || first.size() == 0) {
            return Collections.emptyList();
        }

        if (second == null || second.size() == 0) {
            return first;
        }

        Map<Integer, E> map = new HashMap();

        first.stream().forEach(e -> map.put(hasher.apply(e), e));
        second.stream().forEach(e -> map.remove(hasher.apply(e))); <-- this needs an equality check

        return Collections.unmodifiableCollection(map.values());
    }

@bartoszwalacik i think this method was recently added, i can't find out why we need it and not just use the old:

public static <E> Set<E> difference(Set<E> first, Set<E> second) {
        if (first == null || first.size() == 0) {
            return new HashSet<>();
        }

        if (second == null || second.size() == 0) {
            return first;
        }

        Set<E> difference = new HashSet<>(first);
        difference.removeAll(second);
        return difference;
    }

If i remove the new implementation and just use the old one it works as expected. Let me know how you want to proceed and how we can fix it in next patch.

[jamnaritesh]

Just to add, this collision can happen in some other cases as well:

1. On same side of graphPair if two EntityType globalId's resolve to same hash. The later one will override the previous one leading to undercounting elements on the left.
2. It can lead to two different objects being considered as present on two graph pairs (even if they are not equal)
   G1 [a1 (hash) -> X], G2[b1(hash) -> X.] will return no difference.

[jamnaritesh]

@bartoszwalacik I changed the implementation of hasher function from

Function<ObjectNode, Integer> hasher = objectNode -> objectNode.cdoHashCode();

to

Function<ObjectNode, String> hasher = objectNode -> objectNode.getGlobalId().value()

This provides two advantages,

1. No overriding of elements on the same graph if they return same hash. They'll be in the same bucket, but the hashmap implementation will make sure we have two distinct elements.
2. When removing objects, we'll do a string equality comparison before removing the object from second map.

I ran the tests on javers-core and the test suite looks all green. Let me know how you want to proceed.
Thanks.

[bartoszwalacik]

Hi @jamnaritesh , just create a PR with the best option according to you, the tests will run on CI , then I will do the code review