Most Iterator implementations do not correctly implement next failing to throw the required NoSuchElementException
Iterators on Clojure's collections should follow the expected JDK behavior of throwing NoSuchElementException on next() when an iterator is exhausted. Current collections have a variety of other behaviors.
Issue encountered in real world code using http://pipes.tinkerpop.com.
This throws a NPE instead of NSEE.
This throws an ArrayIndexOutOfBoundsException instead of NSEE.
An additional problem found during testing is that subvecs will iterate past the subvector end and produce data from the underlying source vector:
Approach: The attached patch fixes the methods by adding a check for hasNext before actually trying to provide the next element. If there is no next element the correct exception is thrown.
Patch: clj-1453-3.patch and tests: CLJ-1453-tests.patch
The -3 patch changes the approach on several implementations to catch exceptions thrown in the case of invalid use and convert to the proper exception, rather than preemptively checking for this invalid case. This effectively assumes the "normal" case of a consumer walking the iterator and stopping (based on hasNext()) before making a call off the end of the iterator. This also has the benefit of minimizing the performance impact, which you can see in the example tests for sorted maps and primitive vectors.
With vectors, we can't take this approach. Normal vectors have two "invalid use" failure modes - NullPointer and IndexOutOfBounds. However, subvectors (which use the same rangedIterator code) actually have valid data from the source vector to iterate to, so there must be a check for the end of the iteration. Perf tests show minimal cost to this change as implemented.
have we looked at the perf impacts of the redundant hashNext calls? I understand hasNext should be idempotent, but could do work. An alternative would be putting in try and throwing NSE
clj-1453-2.patch squashes CLJ-1453.patch and updates to current master.
Thanks Andrew. It will likely be a couple weeks before I have time to look at this.
Addressed you comments on the first patch. On the process of applying them to master, I've changed the code to follow a single "format" of bound checking and throw, so everything will be more consistent with the code style of Clojure codebase. The commit themselves still maintain the original authors, to give correct credit.
The second patch includes only the tests for these features, which I used test.check to do them, as I talked to you on clojure-dev channel. If you think they are too much complex or prefer a different style of testing, please let me know - that's why I made a separate patch only for the tests.