testlib: add tests for `ConcurrentMap` to make sure its derived `Set`s are concurrent

[vlsi]

• map.entrySet().stream().toList() should return the same elements
• spliterator().characteristics() should probably align with map/set characteristic. For instance, if the map permits nulls, and there are nulls, then Spliterator.NONNULL does not sound right.

See ben-manes/caffeine#1883

[ben-manes]

I see the mistake exists in every popular non-jdk ConcurrentMap implementation that I can find: Guava, Eclipse Collections, Apache Commons' and Spring's ConcurrentReferenceHashMap, JCTools, etc. Some of these implementations predated Java 8's addition and all inherit the default of SIZED which is unsafe in their concurrent collection. Including additional test coverage would be very nice, though admittedly I've been unsuccessful in getting testlib adoption when reporting the bugs it finds.

[vandan09]

Hi @vlsi,
I’d like to work on this and add test coverage for Map.entrySet().stream().toList() and the corresponding Spliterator characteristics.
Let me know if there are any specific map implementations you'd like covered or testing strategies you'd recommend.
Thanks!

[ShaikSalmaAga]

Hi @vlsi,

I hope you are doing well.

I'd love to contribute to this issue. I'm planning to update the entrySpliterator() implementation by removing the incorrect use of Spliterator.NONNULL, and I'll also add test coverage to ensure the characteristics reflect the actual behavior especially when null values may be present.

Please let me know if there's anything specific you'd like me to focus on or consider while working on this.

Thanks so much.

[chaoren]

MapTestSuiteBuilder creates a derived test suite for entrySet() using SetTestSuiteBuilder:

guava/guava-testlib/src/com/google/common/collect/testing/MapTestSuiteBuilder.java

Lines 164 to 167 in 162544b

	protected SetTestSuiteBuilder<Entry<K, V>> createDerivedEntrySetSuite(
	TestSetGenerator<Entry<K, V>> entrySetGenerator) {
	return SetTestSuiteBuilder.using(entrySetGenerator);
	}

SetTestSuiteBuilder extends AbstractCollectionTestSuiteBuilder, which includes CollectionStreamTester and CollectionSpliteratorTester:

guava/guava-testlib/src/com/google/common/collect/testing/AbstractCollectionTestSuiteBuilder.java

Lines 73 to 74 in 162544b

	CollectionSpliteratorTester.class,
	CollectionStreamTester.class,

• CollectionStreamTester does test that the contents of the Stream is correct:

  guava/guava-testlib/src/com/google/common/collect/testing/testers/CollectionStreamTester.java

  Lines 44 to 52 in 162544b

  	@CollectionFeature.Require(absent = KNOWN_ORDER)
  	public void testStreamToArrayUnknownOrder() {
  	assertEqualIgnoringOrder(getSampleElements(), asList(collection.stream().toArray()));
  	}
  	@CollectionFeature.Require(KNOWN_ORDER)
  	public void testStreamToArrayKnownOrder() {
  	assertEquals(getOrderedElements(), asList(collection.stream().toArray()));
  	}

• CollectionSpliteratorTester does test that Spliterator.NONNULL is used correctly:

  guava/guava-testlib/src/com/google/common/collect/testing/testers/CollectionSpliteratorTester.java

  Lines 59 to 64 in 162544b

  	@CollectionFeature.Require(ALLOWS_NULL_VALUES)
  	@CollectionSize.Require(absent = ZERO)
  	public void testSpliteratorNullable() {
  	initCollectionWithNullElement();
  	assertFalse(collection.spliterator().hasCharacteristics(Spliterator.NONNULL));
  	}

• CollectionSpliteratorTester uses SpliteratorTester:

  guava/guava-testlib/src/com/google/common/collect/testing/testers/CollectionSpliteratorTester.java

  Lines 49 to 57 in 162544b

  	@CollectionFeature.Require(absent = KNOWN_ORDER)
  	public void testSpliteratorUnknownOrder() {
  	SpliteratorTester.of(collection::spliterator).expect(getSampleElements());
  	}
  	@CollectionFeature.Require(KNOWN_ORDER)
  	public void testSpliteratorKnownOrder() {
  	SpliteratorTester.of(collection::spliterator).expect(getOrderedElements()).inOrder();
  	}

  which tests Spliterator.SIZED:

  guava/guava-testlib/src/com/google/common/collect/testing/SpliteratorTester.java

  Lines 327 to 329 in 162544b

  	if ((characteristics & Spliterator.SIZED) != 0) {
  	assertEquals(Ints.checkedCast(estimatedSize), resultsForStrategy.size());
  	}

It looks like what you're asking for is already there. Perhaps the Map under test needs to be generated in a way that exposes the problem?

[ben-manes]

The issue in Caffeine was that Set.spliterator().characteristics() returns SIZED by default coming from an ConcurrentMap.entrySet(). An exact count that matches the pending traversal wouldn't make sense for a concurrent data structure, so j.u.c. overrides to not return that characteristics. The request from my opinion would be checks for ConcurrentMapTestSuiteBuilder tests that they do not produce the wrong characteristics.

[chaoren]

https://docs.oracle.com/en/java/javase/22/docs/api/java.base/java/util/Spliterator.html#CONCURRENT says

A top-level Spliterator should not report both CONCURRENT and SIZED

Maybe we just need to test that?

[ben-manes]

I think that but also checking if the map implements ConcurrentMap which implies it that SIZED is incompatible, so I'd add tests specific to the ConcurrentMap.

For example Guava's Cache.asMap() has the same bug that Caffeine did, per the unit test

  @CacheSpec
  @CheckNoStats
  @Test(dataProvider = "caches")
  public void keySpliterator_characteristics(Map<Int, Int> map, CacheContext context) {
    var spliterator = map.keySet().spliterator();
    if (context.isGuava()) {
      assertThat(spliterator.characteristics()).isEqualTo(DISTINCT | SIZED | SUBSIZED);
    } else {
      assertThat(spliterator.characteristics()).isEqualTo(DISTINCT | NONNULL | CONCURRENT);
    }
  }

[vlsi]

Why in Caffeine's case map.entrySet().stream().toList() results in an exception? I wonder why that illegalstateexception does not reproduce with testlib tests.

[ben-manes]

1. If the map is changed concurrently the size will not be stable.
2. If the map contains expired, collected, or in-flight async entries, then Map.size() is an estimate instead of an exact count. This is documented in Guava and Caffeine's size methods.

[chaoren]

Right, ConcurrentMap should only return Sets whose spliterator() is CONCURRENT. CONCURRENT being incompatible with SIZED can be a separate test.