Fix the size of the stack used by RedBlackTree.iteratorFrom.

`s.c.i.RedBlackTree.TreeIterator` uses a stack of nodes that need
to be processed later. This stack is implemented as an `Array`,
which is allocated with the maximum size that can possibly be
used, based on properties of red-black trees. This was added in
72ec0ac869a29fca9ea0d45a3f70f1e9e1babaaf. At the time, there was
no `iteratorFrom` method, and as the comment in that commit says,
the deepest nodes were never added to the stack, hence the final
`- 1` in computing the maximum stack size.

However, this changed with the introduction of `iteratorFrom` in
62bc99d3b20a7b37a977b19a6202cdac474eb5f6. The method `startFrom`
used to initialize the iterator at the right `start` node does
push the deepest nodes in some cases.

This internal bug got unnoticed because `pushNext` (originally
`pushPath`) has some error recovery in case the stack size got
miscalculated. This has performance impacts, though, since an
exception is thrown and caught.

More importantly, this error recovery mechanism does not work in
Scala.js, which considers `ArrayIndexOutOfBoundsException` to be
undefined behavior.

This commit fixes the stack size computation by simply removing
the `- 1` term. To minimize risks on Scala/JVM, the error recovery
mechanism is left untouched.

1 files changed, 3 insertions, 2 deletions

diff --git a/src/library/scala/collection/immutable/RedBlackTree.scala b/src/library/scala/collection/immutable/RedBlackTree.scala
index afb4c9c552..4f2e9115fe 100644
--- a/src/library/scala/collection/immutable/RedBlackTree.scala
+++ b/src/library/scala/collection/immutable/RedBlackTree.scala
@@ -516,9 +516,10 @@ object RedBlackTree {
        *
        * According to {@see Integer#numberOfLeadingZeros} ceil(log_2(n)) = (32 - Integer.numberOfLeadingZeros(n - 1))
        *
-       * We also don't store the deepest nodes in the path so the maximum path length is further reduced by one.
+       * Although we don't store the deepest nodes in the path during iteration,
+       * we potentially do so in `startFrom`.
        */
-      val maximumHeight = 2 * (32 - Integer.numberOfLeadingZeros(root.count + 2 - 1)) - 2 - 1
+      val maximumHeight = 2 * (32 - Integer.numberOfLeadingZeros(root.count + 2 - 1)) - 2
       new Array[Tree[A, B]](maximumHeight)
     }
     private[this] var index = 0