Most Iterator implementations do not correctly implement next failing to throw the required NoSuchElementException
Description
Environment
Attachments
- 01 Oct 2015, 02:40 PM
- 31 Jul 2015, 05:02 AM
- 18 Jul 2015, 10:38 PM
- 18 Jul 2015, 10:38 PM
- 16 Jul 2014, 04:17 AM
- 24 Jun 2014, 11:00 PM
Activity
Alex Miller October 1, 2015 at 7:35 PM
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.
Rich Hickey August 8, 2015 at 3:53 PM
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 July 31, 2015 at 5:02 AM
clj-1453-2.patch squashes CLJ-1453.patch and updates to current master.
Alex Miller July 18, 2015 at 11:04 PM
Thanks Andrew. It will likely be a couple weeks before I have time to look at this.
andrewhr July 18, 2015 at 10:38 PM
@Alex Miller 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.
Details
Assignee
Alex MillerAlex MillerReporter
Meikel BrandmeyerMeikel BrandmeyerLabels
Approval
OkPatch
Code and TestPriority
MajorAffects versions
Fix versions
Details
Details
Assignee
Reporter
Labels
Approval
Patch
Priority
Major
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:
(-> [] .iterator .next)This throws a NPE instead of NSEE.
(doto (.iterator [1 2]) .next .next .next)This throws an
ArrayIndexOutOfBoundsExceptioninstead 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:
user=> (def iter (.iterator (subvec [4 5 6 7] 0 1))) user=> (dotimes [_ 3] (println (.next iter))) 4 5 ;; should have thrown an exception here 6 nilApproach: The attached patch fixes the methods by adding a check for
hasNextbefore actually trying to provide the next element. If there is no next element the correct exception is thrown.Performance:
(use 'criterium.core) (def v (vec (range 10000))) (def sm (into (sorted-map) (zipmap (range 10000) (range 10000)))) (def pv (apply vector-of :long (range 10000))) (defn consume-iter [^Iterable src] (let [^java.util.Iterator i (.iterator ^Iterable src)] (loop [c []] (if (.hasNext i) (recur (conj c (.next i))) c)))) (bench (consume-iter v)) (bench (consume-iter sm)) (bench (consume-iter pv))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: