Merge pull request #2197 from paulp/pr/integrate-range-positions

Integrate range positions.

7 files changed, 334 insertions, 52 deletions

diff --git a/src/reflect/scala/reflect/internal/Positions.scala b/src/reflect/scala/reflect/internal/Positions.scala
index f8c670827a..f5aeec63e1 100644
--- a/src/reflect/scala/reflect/internal/Positions.scala
+++ b/src/reflect/scala/reflect/internal/Positions.scala
@@ -1,26 +1,60 @@
 package scala.reflect
 package internal
 
+import util._
+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, the singleton consisting of the node itself.
+ */
 trait Positions extends api.Positions { self: SymbolTable =>
 
   type Position = scala.reflect.internal.util.Position
   val NoPosition = scala.reflect.internal.util.NoPosition
   implicit val PositionTag = ClassTag[Position](classOf[Position])
 
+  def inform(msg: String): Unit
+
+  def useOffsetPositions: Boolean = true
+
   /** A position that wraps a set of trees.
    *  The point of the wrapping position is the point of the default position.
    *  If some of the trees are ranges, returns a range position enclosing all ranges
    *  Otherwise returns default position that is either focused or not.
    */
-  def wrappingPos(default: Position, trees: List[Tree]) = wrappingPos(default, trees, true)
-  def wrappingPos(default: Position, trees: List[Tree], focus: Boolean): Position = default
+  def wrappingPos(default: Position, trees: List[Tree]): Position = wrappingPos(default, trees, true)
+  def wrappingPos(default: Position, trees: List[Tree], focus: Boolean): Position = {
+    if (useOffsetPositions) default else {
+      val ranged = trees filter (_.pos.isRange)
+      if (ranged.isEmpty) if (focus) default.focus else default
+      else new RangePosition(default.source, (ranged map (_.pos.start)).min, default.point, (ranged map (_.pos.end)).max)
+    }
+  }
 
   /** A position that wraps the non-empty set of trees.
    *  The point of the wrapping position is the point of the first trees' position.
    *  If some of the trees are non-synthetic, returns a range position enclosing the non-synthetic trees
    *  Otherwise returns a synthetic offset position to point.
    */
-  def wrappingPos(trees: List[Tree]): Position = trees.head.pos
+  def wrappingPos(trees: List[Tree]): Position = {
+    val headpos = trees.head.pos
+    if (useOffsetPositions || !headpos.isDefined) headpos
+    else wrappingPos(headpos, trees)
+  }
 
   /** Ensure that given tree has no positions that overlap with
    *  any of the positions of `others`. This is done by
@@ -28,7 +62,212 @@ trait Positions extends api.Positions { self: SymbolTable =>
    *  to some of the nodes in `tree` or focusing on the position.
    */
   def ensureNonOverlapping(tree: Tree, others: List[Tree]){ ensureNonOverlapping(tree, others, true) }
-  def ensureNonOverlapping(tree: Tree, others: List[Tree], focus: Boolean) {}
+  def ensureNonOverlapping(tree: Tree, others: List[Tree], focus: Boolean) {
+    if (useOffsetPositions) return
+
+    def isOverlapping(pos: Position) =
+      pos.isRange && (others exists (pos overlaps _.pos))
+
+    if (isOverlapping(tree.pos)) {
+      val children = tree.children
+      children foreach (ensureNonOverlapping(_, others, focus))
+      if (tree.pos.isOpaqueRange) {
+        val wpos = wrappingPos(tree.pos, children, focus)
+        tree setPos (if (isOverlapping(wpos)) tree.pos.makeTransparent else wpos)
+      }
+    }
+  }
+
+  def rangePos(source: SourceFile, start: Int, point: Int, end: Int): Position =
+    if (useOffsetPositions) new OffsetPosition(source, point)
+    else new RangePosition(source, start, point, end)
+
+  def validatePositions(tree: Tree) {
+    if (useOffsetPositions) return
+
+    def reportTree(prefix : String, tree : Tree) {
+      val source = if (tree.pos.isDefined) tree.pos.source else ""
+      inform("== "+prefix+" tree ["+tree.id+"] of type "+tree.productPrefix+" at "+tree.pos.show+source)
+      inform("")
+      inform(treeStatus(tree))
+      inform("")
+    }
+
+    def positionError(msg: String)(body : => Unit) {
+      inform("======= Position error\n" + msg)
+      body
+      inform("\nWhile validating #" + tree.id)
+      inform(treeStatus(tree))
+      inform("\nChildren:")
+      tree.children map (t => "  " + treeStatus(t, tree)) foreach inform
+      inform("=======")
+      throw new ValidateException(msg)
+    }
+
+    def validate(tree: Tree, encltree: Tree): Unit = {
+
+      if (!tree.isEmpty && tree.canHaveAttrs) {
+        if (settings.Yposdebug.value && (settings.verbose.value || settings.Yrangepos.value))
+          println("[%10s] %s".format("validate", treeStatus(tree, encltree)))
+
+        if (!tree.pos.isDefined)
+          positionError("Unpositioned tree #"+tree.id) {
+            inform("%15s %s".format("unpositioned", treeStatus(tree, encltree)))
+            inform("%15s %s".format("enclosing", treeStatus(encltree)))
+            encltree.children foreach (t => inform("%15s %s".format("sibling", treeStatus(t, encltree))))
+          }
+        if (tree.pos.isRange) {
+          if (!encltree.pos.isRange)
+            positionError("Synthetic tree ["+encltree.id+"] contains nonsynthetic tree ["+tree.id+"]") {
+            reportTree("Enclosing", encltree)
+            reportTree("Enclosed", tree)
+            }
+          if (!(encltree.pos includes tree.pos))
+            positionError("Enclosing tree ["+encltree.id+"] does not include tree ["+tree.id+"]") {
+              reportTree("Enclosing", encltree)
+              reportTree("Enclosed", tree)
+            }
+
+          findOverlapping(tree.children flatMap solidDescendants) match {
+            case List() => ;
+            case xs => {
+              positionError("Overlapping trees "+xs.map { case (x, y) => (x.id, y.id) }.mkString("", ", ", "")) {
+                reportTree("Ancestor", tree)
+                for((x, y) <- xs) {
+                  reportTree("First overlapping", x)
+                  reportTree("Second overlapping", y)
+                }
+              }
+            }
+          }
+        }
+        for (ct <- tree.children flatMap solidDescendants) validate(ct, tree)
+      }
+    }
+
+    if (!isPastTyper)
+      validate(tree, tree)
+  }
+
+  def solidDescendants(tree: Tree): List[Tree] =
+    if (tree.pos.isTransparent) 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 lazy val maxFree: Range = free(0, Int.MaxValue)
+
+  /** 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(!t.pos.isTransparent)
+      if (r.isFree && (r.pos includes t.pos)) {
+//      println("subdividing "+r+"/"+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)
+
+  /** Does given list of trees have mutually non-overlapping positions?
+   *  pre: None of the trees is transparent
+   */
+  def findOverlapping(cts: List[Tree]): List[(Tree, Tree)] = {
+    var ranges = List(maxFree)
+    for (ct <- cts) {
+      if (ct.pos.isOpaqueRange) {
+        val conflicting = new ListBuffer[Tree]
+        ranges = insert(ranges, ct, conflicting)
+        if (conflicting.nonEmpty) return conflicting.toList map (t => (t, ct))
+      }
+    }
+    List()
+  }
+
+  /** 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. All children must be positionable.
+   */
+  private def setChildrenPos(pos: Position, trees: List[Tree]): Unit = try {
+    for (tree <- trees) {
+      if (!tree.isEmpty && tree.canHaveAttrs && tree.pos == NoPosition) {
+        val children = tree.children
+        if (children.isEmpty) {
+          tree setPos pos.focus
+        } else {
+          setChildrenPos(pos, children)
+          tree setPos wrappingPos(pos, children)
+        }
+      }
+    }
+  } catch {
+    case ex: Exception =>
+      println("error while set children pos "+pos+" of "+trees)
+      throw ex
+  }
+
+
+  class ValidateException(msg : String) extends Exception(msg)
+
+
+  /** 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
+    }
+    protected def isEligible(t: Tree) = !t.pos.isTransparent
+    override def traverse(t: Tree) {
+      t match {
+        case tt : TypeTree if tt.original != null && (tt.pos includes tt.original.pos) =>
+          traverse(tt.original)
+        case _ =>
+          if (t.pos includes pos) {
+            if (isEligible(t)) last = t
+            super.traverse(t)
+          } else t match {
+            case mdef: MemberDef =>
+              traverseTrees(mdef.mods.annotations)
+            case _ =>
+          }
+      }
+    }
+  }
+
+  case class Range(pos: Position, tree: Tree) {
+    def isFree = tree == EmptyTree
+  }
+
+  class TypedLocator(pos: Position) extends Locator(pos) {
+    override protected def isEligible(t: Tree) = super.isEligible(t) && t.tpe != null
+  }
 
   trait PosAssigner extends Traverser {
     var pos: Position
@@ -57,9 +296,25 @@ trait Positions extends api.Positions { self: SymbolTable =>
     }
   }
 
+  /** Position a tree.
+   *  This means: Set position of a node and position all its unpositioned children.
+   */
   def atPos[T <: Tree](pos: Position)(tree: T): T = {
-    posAssigner.pos = pos
-    posAssigner.traverse(tree)
-    tree
+    if (useOffsetPositions || !pos.isOpaqueRange) {
+      posAssigner.pos = pos
+      posAssigner.traverse(tree)
+      tree
+    }
+    else {
+      if (!tree.isEmpty && tree.canHaveAttrs && 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
+    }
   }
-}
\ No newline at end of file
+}
diff --git a/src/reflect/scala/reflect/internal/Trees.scala b/src/reflect/scala/reflect/internal/Trees.scala
index ce33fd8408..c00337e578 100644
--- a/src/reflect/scala/reflect/internal/Trees.scala
+++ b/src/reflect/scala/reflect/internal/Trees.scala
@@ -14,6 +14,23 @@ trait Trees extends api.Trees { self: SymbolTable =>
 
   private[scala] var nodeCount = 0
 
+  protected def treeLine(t: Tree): String =
+    if (t.pos.isDefined && t.pos.isRange) t.pos.lineContent.drop(t.pos.column - 1).take(t.pos.end - t.pos.start + 1)
+    else t.summaryString
+
+  protected def treeStatus(t: Tree, enclosingTree: Tree = null) = {
+    val parent = if (enclosingTree eq null) "        " else " P#%5s".format(enclosingTree.id)
+
+    "[L%4s%8s] #%-6s %-15s %-10s // %s".format(t.pos.safeLine, parent, t.id, t.pos.show, t.shortClass, treeLine(t))
+  }
+  protected def treeSymStatus(t: Tree) = {
+    val line = if (t.pos.isDefined) "line %-4s".format(t.pos.safeLine) else "         "
+    "#%-5s %s %-10s // %s".format(t.id, line, t.shortClass,
+      if (t.symbol ne NoSymbol) "(" + t.symbol.fullLocationString + ")"
+      else treeLine(t)
+    )
+  }
+
   abstract class Tree extends TreeContextApiImpl with Attachable with Product {
     val id = nodeCount // TODO: add to attachment?
     nodeCount += 1
diff --git a/src/reflect/scala/reflect/internal/settings/MutableSettings.scala b/src/reflect/scala/reflect/internal/settings/MutableSettings.scala
index d5ed9dab5b..506edb861e 100644
--- a/src/reflect/scala/reflect/internal/settings/MutableSettings.scala
+++ b/src/reflect/scala/reflect/internal/settings/MutableSettings.scala
@@ -40,6 +40,8 @@ abstract class MutableSettings extends AbsSettings {
   def verbose: BooleanSetting
   def uniqid: BooleanSetting
   def Yshowsymkinds: BooleanSetting
+  def Yposdebug: BooleanSetting
+  def Yrangepos: BooleanSetting
   def Xprintpos: BooleanSetting
   def Yrecursion: IntSetting
   def maxClassfileName: IntSetting
diff --git a/src/reflect/scala/reflect/internal/util/Position.scala b/src/reflect/scala/reflect/internal/util/Position.scala
index f0185372c5..bb8c9e9b26 100644
--- a/src/reflect/scala/reflect/internal/util/Position.scala
+++ b/src/reflect/scala/reflect/internal/util/Position.scala
@@ -266,46 +266,3 @@ class OffsetPosition(override val source: SourceFile, override val point: Int) e
   }
   override def show = "["+point+"]"
 }
-
-/** new for position ranges */
-class RangePosition(source: SourceFile, override val start: Int, point: Int, override val end: Int)
-extends OffsetPosition(source, point) {
-  if (start > end) sys.error("bad position: "+show)
-  override def isRange: Boolean = true
-  override def isOpaqueRange: Boolean = true
-  override def startOrPoint: Int = start
-  override def endOrPoint: Int = end
-  override def withStart(off: Int) = new RangePosition(source, off, point, end)
-  override def withEnd(off: Int) = new RangePosition(source, start, point, off)
-  override def withPoint(off: Int) = new RangePosition(source, start, off, end)
-  override def withSource(source: SourceFile, shift: Int) = new RangePosition(source, start + shift, point + shift, end + shift)
-  override def focusStart = new OffsetPosition(source, start)
-  override def focus = {
-    if (focusCache eq NoPosition) focusCache = new OffsetPosition(source, point)
-    focusCache
-  }
-  override def focusEnd = new OffsetPosition(source, end)
-  override def makeTransparent = new TransparentPosition(source, start, point, end)
-  override def includes(pos: Position) = pos.isDefined && start <= pos.startOrPoint && pos.endOrPoint <= end
-  override def union(pos: Position): Position =
-    if (pos.isRange) new RangePosition(source, start min pos.start, point, end max pos.end) else this
-
-  override def toSingleLine: Position = source match {
-    case bs: BatchSourceFile
-    if end > 0 && bs.offsetToLine(start) < bs.offsetToLine(end - 1) =>
-      val pointLine = bs.offsetToLine(point)
-      new RangePosition(source, bs.lineToOffset(pointLine), point, bs.lineToOffset(pointLine + 1))
-    case _ => this
-  }
-
-  override def toString = "RangePosition("+source.file.canonicalPath+", "+start+", "+point+", "+end+")"
-  override def show = "["+start+":"+end+"]"
-  private var focusCache: Position = NoPosition
-}
-
-class TransparentPosition(source: SourceFile, start: Int, point: Int, end: Int) extends RangePosition(source, start, point, end) {
-  override def isOpaqueRange: Boolean = false
-  override def isTransparent = true
-  override def makeTransparent = this
-  override def show = "<"+start+":"+end+">"
-}
diff --git a/src/reflect/scala/reflect/internal/util/RangePosition.scala b/src/reflect/scala/reflect/internal/util/RangePosition.scala
new file mode 100644
index 0000000000..3712aa0a52
--- /dev/null
+++ b/src/reflect/scala/reflect/internal/util/RangePosition.scala
@@ -0,0 +1,49 @@
+/* NSC -- new Scala compiler
+ * Copyright 2005-2013 LAMP/EPFL
+ * @author  Paul Phillips
+ */
+
+package scala.reflect.internal.util
+
+/** new for position ranges */
+class RangePosition(source: SourceFile, override val start: Int, point: Int, override val end: Int)
+extends OffsetPosition(source, point) {
+  if (start > end) sys.error("bad position: "+show)
+  override def isRange: Boolean = true
+  override def isOpaqueRange: Boolean = true
+  override def startOrPoint: Int = start
+  override def endOrPoint: Int = end
+  override def withStart(off: Int) = new RangePosition(source, off, point, end)
+  override def withEnd(off: Int) = new RangePosition(source, start, point, off)
+  override def withPoint(off: Int) = new RangePosition(source, start, off, end)
+  override def withSource(source: SourceFile, shift: Int) = new RangePosition(source, start + shift, point + shift, end + shift)
+  override def focusStart = new OffsetPosition(source, start)
+  override def focus = {
+    if (focusCache eq NoPosition) focusCache = new OffsetPosition(source, point)
+    focusCache
+  }
+  override def focusEnd = new OffsetPosition(source, end)
+  override def makeTransparent = new TransparentPosition(source, start, point, end)
+  override def includes(pos: Position) = pos.isDefined && start <= pos.startOrPoint && pos.endOrPoint <= end
+  override def union(pos: Position): Position =
+    if (pos.isRange) new RangePosition(source, start min pos.start, point, end max pos.end) else this
+
+  override def toSingleLine: Position = source match {
+    case bs: BatchSourceFile
+    if end > 0 && bs.offsetToLine(start) < bs.offsetToLine(end - 1) =>
+      val pointLine = bs.offsetToLine(point)
+      new RangePosition(source, bs.lineToOffset(pointLine), point, bs.lineToOffset(pointLine + 1))
+    case _ => this
+  }
+
+  override def toString = "RangePosition("+source.file.canonicalPath+", "+start+", "+point+", "+end+")"
+  override def show = "["+start+":"+end+"]"
+  private var focusCache: Position = NoPosition
+}
+
+class TransparentPosition(source: SourceFile, start: Int, point: Int, end: Int) extends RangePosition(source, start, point, end) {
+  override def isOpaqueRange: Boolean = false
+  override def isTransparent = true
+  override def makeTransparent = this
+  override def show = "<"+start+":"+end+">"
+}
diff --git a/src/reflect/scala/reflect/runtime/JavaUniverse.scala b/src/reflect/scala/reflect/runtime/JavaUniverse.scala
index a12e7d43d4..5467d70cea 100644
--- a/src/reflect/scala/reflect/runtime/JavaUniverse.scala
+++ b/src/reflect/scala/reflect/runtime/JavaUniverse.scala
@@ -9,8 +9,8 @@ package runtime
  */
 class JavaUniverse extends internal.SymbolTable with ReflectSetup with runtime.SymbolTable { self =>
 
+  def inform(msg: String): Unit = log(msg)
   def picklerPhase = internal.SomePhase
-
   def forInteractive = false
   def forScaladoc = false
   lazy val settings = new Settings
diff --git a/src/reflect/scala/reflect/runtime/Settings.scala b/src/reflect/scala/reflect/runtime/Settings.scala
index ba524f4df2..5d58fa96d6 100644
--- a/src/reflect/scala/reflect/runtime/Settings.scala
+++ b/src/reflect/scala/reflect/runtime/Settings.scala
@@ -35,6 +35,8 @@ private[reflect] class Settings extends MutableSettings {
   val Xprintpos         = new BooleanSetting(false)
   val Ynotnull          = new BooleanSetting(false)
   val Yshowsymkinds     = new BooleanSetting(false)
+  val Yposdebug         = new BooleanSetting(false)
+  val Yrangepos         = new BooleanSetting(false)
   val debug             = new BooleanSetting(false)
   val deepCloning       = new BooleanSetting(false)
   val explaintypes      = new BooleanSetting(false)