SI-9623 Avoid unnecessary hasNext calls in JoinIterator & ConcatIterator

These iterator implementations are used to concatenate two (JoinIterator)
or more (ConcatIterator) other iterators with `++`. They used to perform
many unnecessary calls to the child iterators’ `hasNext` methods.

This improved state machine-based implementation reduces that number to
the bare minimum, i.e. iterating over concatenated iterators with
`foreach` calls the children's `hasNext` methods a total of (number of
children) + (number of elements) times, the same as when iterating over
all children separately.

1 files changed, 28 insertions, 0 deletions

diff --git a/test/junit/scala/collection/IteratorTest.scala b/test/junit/scala/collection/IteratorTest.scala
index 1c1e50aed9..329c85127a 100644
--- a/test/junit/scala/collection/IteratorTest.scala
+++ b/test/junit/scala/collection/IteratorTest.scala
@@ -164,4 +164,32 @@ class IteratorTest {
     assertEquals(1, y.next)
     assertFalse(x.hasNext)   // was true, after advancing underlying iterator
   }
+  // SI-9623
+  @Test def noExcessiveHasNextInJoinIterator: Unit = {
+    var counter = 0
+    val exp = List(1,2,3,1,2,3)
+    def it: Iterator[Int] = new Iterator[Int] {
+      val parent = List(1,2,3).iterator
+      def next(): Int = parent.next
+      def hasNext: Boolean = { counter += 1; parent.hasNext }
+    }
+    // Iterate separately
+    val res = new mutable.ArrayBuffer[Int]
+    it.foreach(res += _)
+    it.foreach(res += _)
+    assertSameElements(exp, res)
+    assertEquals(8, counter)
+    // JoinIterator
+    counter = 0
+    res.clear
+    (it ++ it).foreach(res += _)
+    assertSameElements(exp, res)
+    assertEquals(8, counter) // was 17
+    // ConcatIterator
+    counter = 0
+    res.clear
+    (Iterator.empty ++ it ++ it).foreach(res += _)
+    assertSameElements(exp, res)
+    assertEquals(8, counter) // was 14
+  }
 }