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 https://github.com/ben-manes/caffeine/issues/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: https://github.com/google/guava/blob/162544b946eb9e69151fd5dd22355a963450588d/guava-testlib/src/com/google/common/collect/testing/MapTestSuiteBuilder.java#L164-L167

SetTestSuiteBuilder extends AbstractCollectionTestSuiteBuilder, which includes CollectionStreamTester and CollectionSpliteratorTester: https://github.com/google/guava/blob/162544b946eb9e69151fd5dd22355a963450588d/guava-testlib/src/com/google/common/collect/testing/AbstractCollectionTestSuiteBuilder.java#L73-L74

• CollectionStreamTester does test that the contents of the Stream is correct: https://github.com/google/guava/blob/162544b946eb9e69151fd5dd22355a963450588d/guava-testlib/src/com/google/common/collect/testing/testers/CollectionStreamTester.java#L44-L52
• CollectionSpliteratorTester does test that Spliterator.NONNULL is used correctly: https://github.com/google/guava/blob/162544b946eb9e69151fd5dd22355a963450588d/guava-testlib/src/com/google/common/collect/testing/testers/CollectionSpliteratorTester.java#L59-L64
• CollectionSpliteratorTester uses SpliteratorTester: https://github.com/google/guava/blob/162544b946eb9e69151fd5dd22355a963450588d/guava-testlib/src/com/google/common/collect/testing/testers/CollectionSpliteratorTester.java#L49-L57 which tests Spliterator.SIZED: https://github.com/google/guava/blob/162544b946eb9e69151fd5dd22355a963450588d/guava-testlib/src/com/google/common/collect/testing/SpliteratorTester.java#L327-L329

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.