diff options
| author | Adriaan Moors <adriaan.moors@typesafe.com> | 2014-02-05 10:28:34 -0800 |
|---|---|---|
| committer | Adriaan Moors <adriaan.moors@typesafe.com> | 2014-02-05 11:04:17 -0800 |
| commit | 8e9e4649ed619f8769c05145e39aaf81750626f8 (patch) | |
| tree | ee08d70120235680ca31fc81f8d38bd3ae496626 /src/interactive | |
| parent | 852a79285d832fae3e756d6bf21fee51e5baf6ef (diff) | |
| download | scala-8e9e4649ed619f8769c05145e39aaf81750626f8.tar.gz scala-8e9e4649ed619f8769c05145e39aaf81750626f8.tar.bz2 scala-8e9e4649ed619f8769c05145e39aaf81750626f8.zip | |
SI-8239 don't loop forever in ContextTrees.locateContextTree
Made loop invariant / recursion metric explicit.
Diffstat (limited to 'src/interactive')
| -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) |