Clojure

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

Details

  • Type: Defect Defect
  • Status: Closed Closed
  • Priority: Major Major
  • Resolution: Completed
  • Affects Version/s: Release 1.6
  • Fix Version/s: Release 1.8
  • Component/s: None
  • Labels:
  • Patch:
    Code and Test
  • Approval:
    Ok

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:

(-> [] .iterator .next)

This throws a NPE instead of NSEE.

(doto (.iterator [1 2]) .next .next .next)

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:

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
nil

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:

(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:

  1. 0001-Fix-iterator-implementations-to-throw-NSEE-when-exha.patch
    24/Jun/14 5:00 PM
    4 kB
    Meikel Brandmeyer
  2. 0001-Throw-NSEE-in-gvec-iterator.patch
    15/Jul/14 10:17 PM
    0.9 kB
    Tim McCormack
  3. CLJ-1453.patch
    18/Jul/15 4:38 PM
    9 kB
    Andrew Rosa
  4. clj-1453-2.patch
    30/Jul/15 11:02 PM
    9 kB
    Alex Miller
  5. clj-1453-3.patch
    01/Oct/15 8:40 AM
    9 kB
    Alex Miller
  6. CLJ-1453-tests.patch
    18/Jul/15 4:38 PM
    8 kB
    Andrew Rosa

Activity

Hide
Tim McCormack added a comment -

To establish a baseline, this piece of code checks all the iterators I could find within Clojure 1.6.0 and makes sure they throw an appropriate exception:

iterator-checker.clj
(defn next-failure
  []
  (let [ok (atom [])]
    (doseq [[tp v]
            (sorted-map
             :vec-0 []
             :vec-n [1 2 3]
             :vec-start (subvec [1 2 3 4] 0 1)
             :vec-end (subvec [1 2 3 4] 3 4)
             :vec-ls-0 (.listIterator [])
             :vec-ls-n (.listIterator [1 2 3])
             :vec-start-ls (.listIterator (subvec [1 2 3 4] 0 1))
             :vec-end-ls (.listIterator (subvec [1 2 3 4] 3 4))
             :seq ()
             :list-n '(1 2 3)
             :set-hash-0 (hash-set)
             :set-hash-n (hash-set 1 2 3)
             :set-sor-0 (sorted-set)
             :set-sor-n (sorted-set 1 2 3)
             :map-arr-0 (array-map)
             :map-arr-n (array-map 1 2, 3 4)
             :map-hash-0 (hash-map)
             :map-hash-n (hash-map 1 2, 3 4)
             :map-sor-n (sorted-map)
             :map-sor-n (sorted-map 1 2, 3 4)
             :map-sor-ks-0 (.keys (sorted-map))
             :map-sor-ks-n (.keys (sorted-map 1 2, 3 4))
             :map-sor-vs-0 (.vals (sorted-map))
             :map-sor-vs-n (.vals (sorted-map 1 2, 3 4))
             :map-sor-rev-0 (.reverseIterator (sorted-map))
             :map-sor-rev-n (.reverseIterator (sorted-map 1 2, 3 4))
             :map-ks-0 (.keySet {})
             :map-ks-n (.keySet {1 2, 3 4})
             :map-vs-0 (.values {})
             :map-vs-n (.values {1 2, 3 4})
             :gvec-int-0 (vector-of :long)
             :gvec-int-n (vector-of :long 1 2 3))]
      (let [it (if (instance? java.util.Iterator v)
                 v
                 (.iterator v))]
        (when-not it
          (println "Null iterator:" tp))
        (try (dotimes [_ 50]
               (.next it))
             (catch java.util.NoSuchElementException nsee
               (swap! ok conj tp))
             (catch Throwable t
               (println tp "threw" (class t))))))
    (println "OK:" @ok)))

The output as of current Clojure master (201a0dd970) is:

:gvec-int-0 threw java.lang.IndexOutOfBoundsException
:gvec-int-n threw java.lang.IndexOutOfBoundsException
:map-arr-0 threw java.lang.ArrayIndexOutOfBoundsException
:map-arr-n threw java.lang.ArrayIndexOutOfBoundsException
:map-hash-0 threw java.lang.ArrayIndexOutOfBoundsException
:map-ks-0 threw java.lang.ArrayIndexOutOfBoundsException
:map-ks-n threw java.lang.ArrayIndexOutOfBoundsException
:map-sor-ks-0 threw java.util.EmptyStackException
:map-sor-ks-n threw java.util.EmptyStackException
:map-sor-n threw java.util.EmptyStackException
:map-sor-rev-0 threw java.util.EmptyStackException
:map-sor-rev-n threw java.util.EmptyStackException
:map-sor-vs-0 threw java.util.EmptyStackException
:map-sor-vs-n threw java.util.EmptyStackException
:map-vs-0 threw java.lang.ArrayIndexOutOfBoundsException
:map-vs-n threw java.lang.ArrayIndexOutOfBoundsException
:vec-0 threw java.lang.NullPointerException
:vec-end threw java.lang.ArrayIndexOutOfBoundsException
:vec-end-ls threw java.lang.IndexOutOfBoundsException
:vec-ls-0 threw java.lang.IndexOutOfBoundsException
:vec-ls-n threw java.lang.IndexOutOfBoundsException
:vec-n threw java.lang.ArrayIndexOutOfBoundsException
:vec-start threw java.lang.ArrayIndexOutOfBoundsException
:vec-start-ls threw java.lang.IndexOutOfBoundsException
OK: [:list-n :map-hash-n :seq :set-hash-0 :set-hash-n :set-sor-0 :set-sor-n]
Show
Tim McCormack added a comment - To establish a baseline, this piece of code checks all the iterators I could find within Clojure 1.6.0 and makes sure they throw an appropriate exception:
iterator-checker.clj
(defn next-failure
  []
  (let [ok (atom [])]
    (doseq [[tp v]
            (sorted-map
             :vec-0 []
             :vec-n [1 2 3]
             :vec-start (subvec [1 2 3 4] 0 1)
             :vec-end (subvec [1 2 3 4] 3 4)
             :vec-ls-0 (.listIterator [])
             :vec-ls-n (.listIterator [1 2 3])
             :vec-start-ls (.listIterator (subvec [1 2 3 4] 0 1))
             :vec-end-ls (.listIterator (subvec [1 2 3 4] 3 4))
             :seq ()
             :list-n '(1 2 3)
             :set-hash-0 (hash-set)
             :set-hash-n (hash-set 1 2 3)
             :set-sor-0 (sorted-set)
             :set-sor-n (sorted-set 1 2 3)
             :map-arr-0 (array-map)
             :map-arr-n (array-map 1 2, 3 4)
             :map-hash-0 (hash-map)
             :map-hash-n (hash-map 1 2, 3 4)
             :map-sor-n (sorted-map)
             :map-sor-n (sorted-map 1 2, 3 4)
             :map-sor-ks-0 (.keys (sorted-map))
             :map-sor-ks-n (.keys (sorted-map 1 2, 3 4))
             :map-sor-vs-0 (.vals (sorted-map))
             :map-sor-vs-n (.vals (sorted-map 1 2, 3 4))
             :map-sor-rev-0 (.reverseIterator (sorted-map))
             :map-sor-rev-n (.reverseIterator (sorted-map 1 2, 3 4))
             :map-ks-0 (.keySet {})
             :map-ks-n (.keySet {1 2, 3 4})
             :map-vs-0 (.values {})
             :map-vs-n (.values {1 2, 3 4})
             :gvec-int-0 (vector-of :long)
             :gvec-int-n (vector-of :long 1 2 3))]
      (let [it (if (instance? java.util.Iterator v)
                 v
                 (.iterator v))]
        (when-not it
          (println "Null iterator:" tp))
        (try (dotimes [_ 50]
               (.next it))
             (catch java.util.NoSuchElementException nsee
               (swap! ok conj tp))
             (catch Throwable t
               (println tp "threw" (class t))))))
    (println "OK:" @ok)))
The output as of current Clojure master (201a0dd970) is:
:gvec-int-0 threw java.lang.IndexOutOfBoundsException
:gvec-int-n threw java.lang.IndexOutOfBoundsException
:map-arr-0 threw java.lang.ArrayIndexOutOfBoundsException
:map-arr-n threw java.lang.ArrayIndexOutOfBoundsException
:map-hash-0 threw java.lang.ArrayIndexOutOfBoundsException
:map-ks-0 threw java.lang.ArrayIndexOutOfBoundsException
:map-ks-n threw java.lang.ArrayIndexOutOfBoundsException
:map-sor-ks-0 threw java.util.EmptyStackException
:map-sor-ks-n threw java.util.EmptyStackException
:map-sor-n threw java.util.EmptyStackException
:map-sor-rev-0 threw java.util.EmptyStackException
:map-sor-rev-n threw java.util.EmptyStackException
:map-sor-vs-0 threw java.util.EmptyStackException
:map-sor-vs-n threw java.util.EmptyStackException
:map-vs-0 threw java.lang.ArrayIndexOutOfBoundsException
:map-vs-n threw java.lang.ArrayIndexOutOfBoundsException
:vec-0 threw java.lang.NullPointerException
:vec-end threw java.lang.ArrayIndexOutOfBoundsException
:vec-end-ls threw java.lang.IndexOutOfBoundsException
:vec-ls-0 threw java.lang.IndexOutOfBoundsException
:vec-ls-n threw java.lang.IndexOutOfBoundsException
:vec-n threw java.lang.ArrayIndexOutOfBoundsException
:vec-start threw java.lang.ArrayIndexOutOfBoundsException
:vec-start-ls threw java.lang.IndexOutOfBoundsException
OK: [:list-n :map-hash-n :seq :set-hash-0 :set-hash-n :set-sor-0 :set-sor-n]
Hide
Tim McCormack added a comment -

0001-Fix-iterator-implementations-to-throw-NSEE-when-exha.patch missed one thing: clojure.gvec. With the patch in place, my checker outputs the following:

:gvec-int-0 threw java.lang.IndexOutOfBoundsException
:gvec-int-n threw java.lang.IndexOutOfBoundsException
OK: [:list-n :map-arr-0 :map-arr-n :map-hash-0 :map-hash-n :map-ks-0 :map-ks-n :map-sor-ks-0 :map-sor-ks-n :map-sor-n :map-sor-rev-0 :map-sor-rev-n :map-sor-vs-0 :map-sor-vs-n :map-vs-0 :map-vs-n :seq :set-hash-0 :set-hash-n :set-sor-0 :set-sor-n :vec-0 :vec-end :vec-end-ls :vec-ls-0 :vec-ls-n :vec-n :vec-start :vec-start-ls]

That should be a quick fix.

Show
Tim McCormack added a comment - 0001-Fix-iterator-implementations-to-throw-NSEE-when-exha.patch missed one thing: clojure.gvec. With the patch in place, my checker outputs the following:
:gvec-int-0 threw java.lang.IndexOutOfBoundsException
:gvec-int-n threw java.lang.IndexOutOfBoundsException
OK: [:list-n :map-arr-0 :map-arr-n :map-hash-0 :map-hash-n :map-ks-0 :map-ks-n :map-sor-ks-0 :map-sor-ks-n :map-sor-n :map-sor-rev-0 :map-sor-rev-n :map-sor-vs-0 :map-sor-vs-n :map-vs-0 :map-vs-n :seq :set-hash-0 :set-hash-n :set-sor-0 :set-sor-n :vec-0 :vec-end :vec-end-ls :vec-ls-0 :vec-ls-n :vec-n :vec-start :vec-start-ls]
That should be a quick fix.
Hide
Michał Marczyk added a comment -

CLJ-1416 includes a fix for gvec's iterator impls (and some other improvements to interop).

Show
Michał Marczyk added a comment - CLJ-1416 includes a fix for gvec's iterator impls (and some other improvements to interop).
Hide
Tim McCormack added a comment -

Attaching a fix for the gvec iterator. Combined with the existing patch, this fixes all broken iterators that I could find.

Show
Tim McCormack added a comment - Attaching a fix for the gvec iterator. Combined with the existing patch, this fixes all broken iterators that I could find.
Hide
Andy Fingerhut added a comment -

I believe this Clojure commit: https://github.com/clojure/clojure/commit/e7215ce82215bda33f4f0887cb88570776d558a0

introduces more implementations of the java.util.Iterator interface where next() returns null instead of throwing a NoSuchElementException

Show
Andy Fingerhut added a comment - I believe this Clojure commit: https://github.com/clojure/clojure/commit/e7215ce82215bda33f4f0887cb88570776d558a0 introduces more implementations of the java.util.Iterator interface where next() returns null instead of throwing a NoSuchElementException
Hide
Alex Miller added a comment -

Would love to have a patch that:
1) combined patches to date
2) updated to master
3) reviewed for new iterators since this ticket was written
4) added the tests in the comments

Show
Alex Miller added a comment - Would love to have a patch that: 1) combined patches to date 2) updated to master 3) reviewed for new iterators since this ticket was written 4) added the tests in the comments
Hide
Alex Miller added a comment -

Bump - would be happy to screen this for 1.8 if my last comments were addressed.

Show
Alex Miller added a comment - Bump - would be happy to screen this for 1.8 if my last comments were addressed.
Hide
Andrew Rosa added a comment -

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.

Show
Andrew Rosa added a comment - 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.
Hide
Alex Miller added a comment -

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

Show
Alex Miller added a comment - Thanks Andrew. It will likely be a couple weeks before I have time to look at this.
Hide
Alex Miller added a comment -

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

Show
Alex Miller added a comment - clj-1453-2.patch squashes CLJ-1453.patch and updates to current master.
Hide
Rich Hickey added a comment -

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

Show
Rich Hickey added a comment - 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
Hide
Alex Miller added a comment -

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.

Show
Alex Miller added a comment - 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.

People

Vote (3)
Watch (4)

Dates

  • Created:
    Updated:
    Resolved: