RFR: JDK-8199216: Quadratic layout time with nested nodes and pseudo-class in style sheet [v8]

[John Hendrikx]

On Tue, 15 Aug 2023 11:56:05 GMT, Jose Pereda <jpereda at openjdk.org> wrote:

>> John Hendrikx has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains 16 commits:
>> 
>>  - Merge branch 'master' of https://git.openjdk.org/jfx into
>>    feature/immutable-pseudoclassstate
>>  - Merge remote-tracking branch 'upstream/master' into feature/immutable-pseudoclassstate
>>  - Avoid using Lambda in ImmutablePseudoClassSetsCache.of()
>>  - Merge branch 'master' of https://git.openjdk.org/jfx into
>>    feature/immutable-pseudoclassstate
>>  - Fix another edge case in BitSet equals
>>    
>>    When arrays are not the same size, but there are no set bits in the ones
>>    the other set doesn't have, two bit sets can still be considered equal
>>  - Take element type into account for BitSet.equals()
>>  - Base BitSet on AbstractSet to inherit correct equals/hashCode/toArray
>>    
>>    - Removed faulty toArray implementations in PseudoClassState and
>>    StyleClassSet
>>    - Added test that verifies equals/hashCode for PseudoClassState respect
>>    Set contract now
>>    - Made getBits package private so it can't be inherited
>>  - Remove unused code
>>  - Ensure Match doesn't allow modification
>>  - Simplify ImmutablePseudoClassSetsCache and avoid an unnecessary copy
>>  - ... and 6 more: https://git.openjdk.org/jfx/compare/9ad0e908...7975ae99
>
> modules/javafx.graphics/src/main/java/com/sun/javafx/css/PseudoClassState.java line 65:
> 
>> 63:     /** {@inheritDoc} */
>> 64:     @Override
>> 65:     public <T> T[] toArray(T[] a) {
> 
> You have mentioned that this was a bug but hard to reproduce.
> Could you add a test that somehow calls `toArray` that fails before your patch and passes now?

It's definitely a bug, but it would only appear if you had bit sets which required more than 1 long to store their data **and** you called `toArray`.  It would then throw an `ArrayIndexOutOfBoundsException` in this line:

    final long state = getBits()[index];

This is because `index` is used for two unrelated purposes:
- the index into the array of longs
- the index of the entry in the resulting array

If the outer loop ever needs two passes, it again wants to read a `long` using `getBits()[index]` but as `index` was advanced (multiple times) while filling entries in the result array, it won't be the correct index at all.

Anyway, I'm not sure what the value would be of a test.  Since `toArray` is no longer implemented by us but by `AbstractSet`, I'd just be testing the `AbstractSet` code.

-------------

PR Review Comment: https://git.openjdk.org/jfx/pull/1076#discussion_r1294645621