commons-collections [COLLECTIONS-848] testToString() is non-deterministic

PR Overview:

This PR fixes the following tests-

Test Overview:

The function testToString tests how a MultiValuedMap works. A MultiValuedMap is basically a map with a key value that can associate itself to either a single value or multiple values (Collections). In this example a key is mapped to one value.

You can reproduce the issue by running the following commands (below command is for testToString in TransformedMultiValuedMapTest, please change class name for targeting other implementations of testToString) -

mvn install -pl . -am -DskipTests
mvn  -Dtest=org.apache.commons.collections4.multimap.TransformedMultiValuedMapTest#testToString
mvn  edu.illinois:nondex-maven-plugin:2.1.1:nondex -Dtest=org.apache.commons.collections4.multimap.TransformedMultiValuedMapTest#testToString

Problem

A multivalued map when being called will not maintain the order of values, the keys may be rearranged in any order. The function, map.toString() will return a new instance of a map every time so the following line makes the test flaky. This flakiness was identified by the nondex tool created by the researchers of UIUC

https://github.com/apache/commons-collections/blob/35e408717379eed0085cdb29e879209dbadc1ead/src/test/java/org/apache/commons/collections4/multimap/TransformedMultiValuedMapTest.java#L45-L48

https://github.com/apache/commons-collections/blob/35e408717379eed0085cdb29e879209dbadc1ead/src/test/java/org/apache/commons/collections4/multimap/AbstractMultiValuedMapTest.java#L708-L711

Here the map.toString() might return {B=[U, V, W], A=[X, Y, Z]} for the LHS and {A=[X, Y, Z], B=[U, V, W]} for the RHS. The toString() function is not inherently flaky and thus is not the root cause of the issue. The initialization of MultiValuedMap with makeObject() is what causes the issue as this can change the order of the keys.

Fix:

Instead of calling a new instance of map.toString(), we can assign it to a variable commonly and use it making the value constant for the entire test. This fix will avoid re-initializing the map thus reordering the values in the map. You can preview the fix here This PR provides a fix on the abstract class and hence provides a fix for the class with tests that implement this class.

JIRA Issue Link: https://issues.apache.org/jira/browse/COLLECTIONS-848

Nov 01 '23 21:11 anirudh711

Hello @anirudh711

You write:

A multivalued map when being called will not maintain the order of values

How is this possible when only performing reads from the Map, like in this test's assertions?

You write:

The function, map.toString() will return a new instance of a map every time

This does not make sense to me. toString() returns a String, not a Map. If you mean, a Map is allocated, please explain more carefully. I see:

TransformedMultiValuedMap.toString() delegates to
AbstractMultiValuedMapDecorator.toString()delegates to
`AbstractMultiValuedMap.toString() delegates to
AbstractMap.toString() calls
HashMap.entrySet() which allocates a HashMap.EntrySet on demand once, then calls
EntrySet.iterator() on that EntrySet which creates a new EntryIterator (a HashIterator)
next is called on the iterator and the underlying Map's table is not edited.

So where can this different ordering take place?

I don't know what the plugin you are calling does, but I do not see this as valid unless you can reproduce your use case in a unit test. Please help me understand.

Jan 20 '24 14:01 garydgregory

@anirudh711 ping

Jan 27 '24 13:01 garydgregory

No reply from @anirudh711; closing.

Mar 30 '24 14:03 garydgregory