-
Notifications
You must be signed in to change notification settings - Fork 196
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
ObjectArraySet iterator remove throwing ArrayIndexOutOfBoundsException #322
Comments
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. |
I'm not at a computer—how did you generate this? |
BTW, replication procedures are the most basic best practice in bug reporting. |
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 Testing code (mind the CollectionFeature.NON_STANDARD_TOSTRING required - another story). import com.google.common.collect.testing.SetTestSuiteBuilder; public class ObjectArraySetTest { |
There's nothing obvious in reproduction of an unexpected behavior. |
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 |
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. |
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. |
Fixed with the last commit. Please let me know if this works for you. Weirdly, the code for array-based maps was correct. |
Thank you for the fast fix. Is 8.5.14 published anywhere? |
Nope, I was waiting for your comments and from comments from #321 . |
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? |
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. |
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? |
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.
|
This happens with the new jar I've provided you with, right? |
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. |
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. |
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. |
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.
The text was updated successfully, but these errors were encountered: