diff options
Diffstat (limited to 'src/compiler')
-rwxr-xr-x | src/compiler/scala/tools/nsc/interactive/Positions.scala | 205 |
1 files changed, 205 insertions, 0 deletions
diff --git a/src/compiler/scala/tools/nsc/interactive/Positions.scala b/src/compiler/scala/tools/nsc/interactive/Positions.scala new file mode 100755 index 0000000000..ce4de1d311 --- /dev/null +++ b/src/compiler/scala/tools/nsc/interactive/Positions.scala @@ -0,0 +1,205 @@ +package scala.tools.nsc.interactive + +import ast.Trees +import scala.tools.nsc.util.{SourceFile, Position, RangePosition, OffsetPosition, NoPosition, WorkScheduler} +import scala.collection.mutable.ListBuffer + +/** Handling range positions + * atPos, the main method in this trait, will add positions to a tree, + * and will ensure the following properties: + * + * 1. All nodes between the root of the tree and nodes that already have positions + * will be assigned positions. + * 2. No node which already has a position will be assigned a different range; however + * a RangePosition might become a TransparentPosition. + * 3. The position of each assigned node includes the positions of each of its children. + * 4. The positions of all solid descendants of children of an assigned node + * are mutually non-overlapping. + * + * Here, the solid descendant of a node are: + * + * If the node has a TransparentPosition, the solid descendants of all its children + * Otherwise, then singleton consisting of the node itself. + */ +trait Positions extends Trees { +self: Global => + + private case class Range(val pos: Position, val tree: Tree) { + def isFree = tree == EmptyTree + } + + class TransparentPosition(source0: SourceFile, start: Int, point: Int, end: Int) extends RangePosition(source0, start, point, end) { + override def toString = "<"+super.toString+">" + } + + def isTransparent(pos: Position) = pos.isInstanceOf[TransparentPosition] + def isRange(pos: Position) = pos.isInstanceOf[RangePosition] + + // -------------- ensuring no overlaps ------------------------------- + + def solidDescendants(tree: Tree): List[Tree] = + if (isTransparent(tree.pos)) tree.children flatMap solidDescendants else List(tree) + + /** A free range from `lo` to `hi` */ + private def free(lo: Int, hi: Int): Range = + Range(new RangePosition(null, lo, lo, hi), EmptyTree) + + /** The maximal free range */ + private val maxFree: Range = free(0, Math.MAX_INT) + + /** A singleton list of a non-empty range from `lo` to `hi`, or else the empty List */ + private def maybeFree(lo: Int, hi: Int) = if (lo < hi) List(free(lo, hi)) else List() + + /** Insert `pos` into ranges `rs` if possible; + * otherwise add conflicting trees to `conflicting`. + */ + private def insert(rs: List[Range], t: Tree, conflicting: ListBuffer[Tree]): List[Range] = rs match { + case List() => + assert(conflicting.nonEmpty) + rs + case r :: rs1 => + assert(!isTransparent(t.pos)) + if (r.isFree && (r.pos includes t.pos)) { + maybeFree(t.pos.end, r.pos.end) ::: List(Range(t.pos, t)) ::: maybeFree(r.pos.start, t.pos.start) ::: rs1 + } else { + if (!r.isFree && (r.pos overlaps t.pos)) conflicting += r.tree + r :: insert(rs1, t, conflicting) + } + } + + /** Replace elem `t` of `ts` by `replacement` list. */ + private def replace(ts: List[Tree], t: Tree, replacement: List[Tree]): List[Tree] = + if (ts.head == t) replacement ::: ts.tail + else ts.head :: replace(ts.tail, t, replacement) + + /** Ensure that given list of trees has mutually non-overlapping positions, + * by assinging TransparentPositions to some of them, if necessary + */ + def ensureNonOverlapping(cts: List[Tree]): Unit = { + + /** Do a pass over all child trees `cts`, where `ranges` reflects positions previously + * encountered. If there are overlaps, break up one node by making its position a TransparentPosition + * and do another pass of `ensureOverlapping`. + * @param ranges The current list of non-overlapping ranges, + * both occupied and free, sorted from later to earlier. + * No TransparentPositions allowed here! + * @param cts The list of trees to insert in ranges. + */ + def iterate(ranges: List[Range], cts: List[Tree]): Unit = cts match { + case List() => + ; + case ct :: cts1 => + val conflicting = new ListBuffer[Tree] + val ranges1 = insert(ranges, ct, conflicting) + if (conflicting.isEmpty) { + iterate(ranges1, cts1) + } else { + val splitNode = + if (conflicting.size == 1 && (conflicting.head.pos includes ct.pos)) conflicting.head + else ct + splitNode setPos new TransparentPosition(splitNode.pos.source.get, splitNode.pos.start, splitNode.pos.point, splitNode.pos.end) + ensureNonOverlapping(replace(cts, splitNode, solidDescendants(splitNode))) + } + } + + iterate(List(maxFree), cts) + } + + /** Does given list of trees have mutually non-overlapping positions? */ + def findOverlapping(cts: List[Tree]): List[(Tree, Tree)] = { + var ranges = List(maxFree) + for (ct <- cts) { + val conflicting = new ListBuffer[Tree] + ranges = insert(ranges, ct, conflicting) + if (conflicting.nonEmpty) return conflicting.toList map (t => (t, ct)) + } + List() + } + + // -------------- setting positions ------------------------------- + + /** The sorted list of descendant nodes, a long positions */ + + + /** Set position of all children of a node + * @param pos A target position. + * Uses the point of the position as the point of all positions it assigns. + * Uses the start of this position as an Offset position for unpositioed trees + * without children. + * @param trees The children to position + */ + private def setChildrenPos(pos: Position, trees: List[Tree]) { + var currentPos = pos + for (tree <- trees) { + val children = tree.children + if (children.isEmpty) + tree setPos OffsetPosition(pos.source.get, currentPos.start) + else { + setChildrenPos(currentPos, children) + tree setPos new RangePosition( + pos.source.get, (children map (_.pos.start)).min, pos.point, (children map (_.pos.end)).max) + } + currentPos = new RangePosition(pos.source.get, tree.pos.end, pos.point, pos.end) + } + ensureNonOverlapping(trees) + } + + /** Position a tree. + * This means: Set position of a node and position all its unpositioned children. + */ + override def atPos[T <: Tree](pos: Position)(tree: T): T = + if (isRange(pos)) { + if (tree != EmptyTree && tree.pos == NoPosition) { + tree.setPos(pos) + val children = tree.children + if (children.nonEmpty) { + if (children.tail.isEmpty) atPos(pos)(children.head) + else setChildrenPos(pos, children) + } + } + tree + } else { + super.atPos(pos)(tree) + } + + // ---------------- Validating positions ---------------------------------- + + def validatePositions(tree: Tree) { + def error(msg: String) { + inform("**** bad positions:") + inform(msg) + inform("================= in =================") + inform(tree.toString) + } + def validate(tree: Tree, encltree: Tree) { + if (encltree.pos.isSynthetic && !tree.pos.isSynthetic) + error("synthetic "+encltree+" contains nonsynthetic" + tree) + if (!(encltree.pos includes tree.pos)) + error(encltree+" does not include "+tree) + for ((t1, t2) <- findOverlapping(tree.children flatMap solidDescendants)) + error("overlapping trees: "+t1+" === and === "+t2) + } + validate(tree, tree) + } + + // ---------------- Locating trees ---------------------------------- + + /** A locator for trees with given positions. + * Given a position `pos`, locator.apply returns + * the smallest tree that encloses `pos`. + */ + class Locator(pos: Position) extends Traverser { + var last: Tree = _ + def locateIn(root: Tree): Tree = { + this.last = EmptyTree + traverse(root) + this.last + } + override def traverse(t: Tree) { + if (!t.pos.isSynthetic && (t.pos includes pos)) { + if (!isTransparent(t.pos)) last = t + super.traverse(t) + } + } + } +} |