diff options
author | Sébastien Doeraene <sjrdoeraene@gmail.com> | 2017-01-16 11:45:56 +0100 |
---|---|---|
committer | Sébastien Doeraene <sjrdoeraene@gmail.com> | 2017-01-16 11:45:56 +0100 |
commit | 648eba62b0054d7a0442de3f5a79eb75d38e7602 (patch) | |
tree | 7e6ae6bd680962c4a501ada04438cb85c27d950d /test/script-tests | |
parent | a5d38ea33430e144d05e7486791f70e144c5b602 (diff) | |
download | scala-648eba62b0054d7a0442de3f5a79eb75d38e7602.tar.gz scala-648eba62b0054d7a0442de3f5a79eb75d38e7602.tar.bz2 scala-648eba62b0054d7a0442de3f5a79eb75d38e7602.zip |
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.
Diffstat (limited to 'test/script-tests')
0 files changed, 0 insertions, 0 deletions