Most Iterator implementations do not correctly implement next failing to throw the required NoSuchElementException

Description

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.

To reproduce:

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.

Performance:

coll

1.8.0-alpha5

-2 patch

-3 patch

v

313 us

314 us

306 us

sm

723 us

741 us

708 us

pv

516 us

546 us

520 us

Patch: clj-1453-3.patch and tests: CLJ-1453-tests.patch

Screened by:

Environment

None

Activity

Show:
andrewhr
July 19, 2015, 8:38 AM

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.

Alex Miller
July 19, 2015, 9:04 AM

Thanks Andrew. It will likely be a couple weeks before I have time to look at this.

Alex Miller
July 31, 2015, 3:02 PM

clj-1453-2.patch squashes CLJ-1453.patch and updates to current master.

Rich Hickey
August 9, 2015, 1:53 AM

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

Alex Miller
October 2, 2015, 5:35 AM

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.

Completed

Assignee

Alex Miller

Reporter

Meikel Brandmeyer

Labels

Approval

Ok

Patch

Code and Test

Fix versions

Affects versions

Priority

Major