diff options
| author | Jason Zaugg <jzaugg@gmail.com> | 2014-02-06 11:04:16 +0100 |
|---|---|---|
| committer | Jason Zaugg <jzaugg@gmail.com> | 2014-02-06 11:04:16 +0100 |
| commit | 8d5fad8be801200890d2ef34ac43982135cd0bc3 (patch) | |
| tree | e44a85a62b20efd4436ee749a6e5e389be379713 /src | |
| parent | 431ae49c3ebab1979f914e060cc5740f667bc482 (diff) | |
| parent | 8e9e4649ed619f8769c05145e39aaf81750626f8 (diff) | |
| download | scala-8d5fad8be801200890d2ef34ac43982135cd0bc3.tar.gz scala-8d5fad8be801200890d2ef34ac43982135cd0bc3.tar.bz2 scala-8d5fad8be801200890d2ef34ac43982135cd0bc3.zip | |
Merge pull request #3469 from adriaanm/t8239
don't loop forever in ContextTrees.locateContextTree
Diffstat (limited to 'src')
| -rw-r--r-- | src/interactive/scala/tools/nsc/interactive/ContextTrees.scala | 16 |
1 files changed, 14 insertions, 2 deletions
diff --git a/src/interactive/scala/tools/nsc/interactive/ContextTrees.scala b/src/interactive/scala/tools/nsc/interactive/ContextTrees.scala index 4f67a22b8f..bf718c27cc 100644 --- a/src/interactive/scala/tools/nsc/interactive/ContextTrees.scala +++ b/src/interactive/scala/tools/nsc/interactive/ContextTrees.scala @@ -64,9 +64,12 @@ trait ContextTrees { self: Global => def locateContextTree(contexts: Contexts, pos: Position): Option[ContextTree] = { if (contexts.isEmpty) None else { + // binary search on contexts, loop invar: lo <= hi, recursion metric: `hi - lo` @tailrec def loop(lo: Int, hi: Int, previousSibling: Option[ContextTree]): Option[ContextTree] = { - if (pos properlyPrecedes contexts(lo).pos) + // [SI-8239] enforce loop invariant & ensure recursion metric decreases monotonically on every recursion + if (lo > hi) previousSibling + else if (pos properlyPrecedes contexts(lo).pos) previousSibling else if (contexts(hi).pos properlyPrecedes pos) Some(contexts(hi)) @@ -76,9 +79,18 @@ trait ContextTrees { self: Global => if (midpos includes pos) Some(contexts(mid)) else if (midpos properlyPrecedes pos) + // recursion metric: (hi - ((lo + hi)/2 + 1)) < (hi - lo) + // since (hi - ((lo + hi)/2 + 1)) - (hi - lo) = lo - ((lo + hi)/2 + 1) < 0 + // since 2*lo - lo - hi - 2 = lo - hi - 2 < 0 + // since lo < hi + 2 + // can violate lo <= hi, hence the lo > hi check at the top [SI-8239] loop(mid + 1, hi, Some(contexts(mid))) - else + else if (lo != hi) // avoid looping forever (lo == hi violates the recursion metric) [SI-8239] + // recursion metric: ((lo + hi)/2) - lo < (hi - lo) + // since ((lo + hi)/2) - lo - (hi - lo) = ((lo + hi)/2) - hi < 0 + // since 2 * (((lo + hi)/2) - hi) = lo - hi < 0 since lo < hi loop(lo, mid, previousSibling) + else previousSibling } } loop(0, contexts.length - 1, None) |