ObjectArraySet iterator remove throwing ArrayIndexOutOfBoundsException

[frajt]

Guava collection testing failing on ObjectArraySet iterator remove throwing ArrayIndexOutOfBoundsException instead of expected and documented IllegalStateException when removed called for hasNext==false. Hash implementations are fine.

junit.framework.AssertionFailedError: failed with stimuli [hasNext, hasNext, hasNext, hasNext, remove] at com.google.common.collect.testing.Helpers.fail(Helpers.java:256) at com.google.common.collect.testing.AbstractIteratorTester.compareResultsForThisListOfStimuli(AbstractIteratorTester.java:371)

junit.framework.AssertionFailedError: Exception ArrayIndexOutOfBoundsException was thrown; expected IllegalStateException at com.google.common.collect.testing.Helpers.fail(Helpers.java:256)

Likely missing a check only.

[frajt]

And when it throws ArrayIndexOutOfBoundsException instead of the IllegalStateException it destroys its state by decrementing the size field. It is a serious defect looking for a fix.

[vigna]

I'm not at a computer—how did you generate this?

[vigna]

BTW, replication procedures are the most basic best practice in bug reporting.

[frajt]

I am sorry. I thought it would be obvious. I strongly recommend to use the Guava collection tests. It tests all collections very deep for all specified, expected and common behavior.

Some deps you might need library('junit-jupiter', "org.junit.jupiter:junit-jupiter:5.10.0") library('junit-jupiter-engine', "org.junit.jupiter:junit-jupiter-engine:5.10.0") library('junit-vintage-engine', "org.junit.vintage:junit-vintage-engine:5.10.0") library('guava-testlib', "com.google.guava:guava-testlib:32.1.1-jre")

Testing code (mind the CollectionFeature.NON_STANDARD_TOSTRING required - another story).

import com.google.common.collect.testing.SetTestSuiteBuilder; import com.google.common.collect.testing.TestStringSetGenerator; import com.google.common.collect.testing.features.CollectionFeature; import com.google.common.collect.testing.features.CollectionSize; import com.google.common.collect.testing.features.SetFeature; import it.unimi.dsi.fastutil.objects.ObjectArraySet; import java.util.Set; import junit.framework.Test; import junit.framework.TestSuite;

public class ObjectArraySetTest { public static Test suite() { final TestSuite suite = new TestSuite(); { suite.addTest(SetTestSuiteBuilder.using(new TestStringSetGenerator() { @Override protected Set create(final String[] entries) { return new ObjectArraySet<>(entries); } }) .named("ObjectArraySetTest") .withFeatures( CollectionSize.ANY, SetFeature.GENERAL_PURPOSE, CollectionFeature.GENERAL_PURPOSE, CollectionFeature.ALLOWS_NULL_VALUES, CollectionFeature.NON_STANDARD_TOSTRING, CollectionFeature.SERIALIZABLE) .createTestSuite()); } return suite; } }

[vigna]

There's nothing obvious in reproduction of an unexpected behavior.

[frajt]

When a user code calls remove on ObjectArraySet before the next() was called, the spec says it should throw IllegalStateException, operation not done. Your code will instead reduce the size of the set, and fail on the System.arrayCopy destination index being -1. Result is shortened set by the last element in the array, iterator broken, unexpected exception thrown. Nothing the application can recover from. Note that OpenObjectHashSet works right.

java.lang.ArrayIndexOutOfBoundsException: arraycopy: destination index -1 out of bounds for object array[4]

ObjectArraySet::Iterator @Override public void remove() { final int tail = size-- - next--; System.arraycopy(a, next + 1, a, next, tail); a[size] = null; }

[vigna]

So, there is guava directory with some tests from Guava. It was contributed, so I don't really know how that works. But indeed it does not apply Guava tests to array-based sets. If you want to do a PR extending those tests to array-based set and maps you're welcome. In the mean time I'll write a specific test and try to fix the problem.

[vigna]

When a user code calls remove on ObjectArraySet before the next() was called, the spec says it should throw IllegalStateException, operation not done. Your code will instead reduce the size of the set, and fail on the System.arrayCopy destination index being -1. Result is shortened set by the last element in the array, iterator broken, unexpected exception thrown. Nothing the application can recover from. Note that OpenObjectHashSet works right.

java.lang.ArrayIndexOutOfBoundsException: arraycopy: destination index -1 out of bounds for object array[4]

ObjectArraySet::Iterator @OverRide public void remove() { final int tail = size-- - next--; System.arraycopy(a, next + 1, a, next, tail); a[size] = null; }

Ok, that's the opposite of what you wrote initially. Initially you said this happens when hasNext() == false. I tried to write a test, impossible. Now you're saying this happen when hasNext() has not been called. That, I can reproduce.

[vigna]

Fixed with the last commit. Please let me know if this works for you. Weirdly, the code for array-based maps was correct.

[frajt]

Thank you for the fast fix. Is 8.5.14 published anywhere?

[vigna]

Nope, I was waiting for your comments and from comments from https://github.com/vigna/fastutil/issues/321 .

[frajt]

We have not stepped into making fastutil on our side. I guess due to bash scripts it requires Linux build environment, right? Any chance to get the jar file of 8.5.14?

[vigna]

http://vigna.di.unimi.it/fastutil-8.5.14.jar

[frajt]

I tested it for the reported ObjectArraySet and it seems to works fine now.

In between we have applied Guava Collection tests for FastUtil Map. And it reports errors there as well. Likely both Array and Hash implementations are failing. It is always in the CollectionIteratorTester.testIterator_unknownOrderRemoveUnsupported test. Would you be able to apply Guava Collection tests on your side to see the failing contracts? For the maps there is actually more. A few tests failing around null handling in computeIfAbsent, merge, replaceAll next to the setValue on entry set iterator not being implemented at all.

[vigna]

The semantics of some of those methods is documented to be different from Java's because we have default return values. Also, note that some exception types might be different because I cut some checks relying on the fact that mistakes will be caught at the JVM levels for efficiency (e.g., setValue on a removed entry will cause an ArrayIndexOutOfBoundException, not an IllegalStateException). Can you report some of those failing tests?

[frajt]

Most of the iterator failing tests are caused by FastUtils iterators not fulfilling the JDK Iterator remove method contract by allowing the remove method to be called without the next method invocation in between.

Removes from the underlying collection the last element returned by this iterator (optional operation). This method can be called only once per call to next().

[vigna]

This happens with the new jar I've provided you with, right?

[frajt]

Yes, but same happens for Maps in 8.5.12.

The Guava Collections tests, especially the one around iterator remove testing, are generating several test combinations of hasNext, next, remove calls and testing it against referential implementation to see the tested implementation fulfilling the contract including exception being thrown of concrete type. The random/unexpected combination of hasNext/next/remove calls invokes unprotected situations in FastUtil iterator implementations, leading sometimes even to internal state corruption. I again recommend to add Guava Collections tests to your testing.

[vigna]

I understand, but I'm working on other things at the moment and that is not going to happen anytime soon. That's why I suggested a PR if you're familiar with the framework. There's already some Guava testing in the guava directory, albeit clearly not the tests you mention.

[frajt]

We selected FastUtil as the replacement of Trove library we were using for 20 years like. Finaly we had to clone it and add several changes and improvements as the project became unsupported despite there were some attemps by a few.

We should have a capacity on our side to help with the implementation. We will setup FastUtil builds and try to deliver PRs for reported issues around iterators, and more.