package scala.tools.nsc
package interactive

import ast.Trees
import symtab.Positions
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, the singleton consisting of the node itself.
 */
trait RangePositions extends Trees with Positions { 
self: scala.tools.nsc.Global =>

  case class Range(pos: Position, tree: Tree) {
    def isFree = tree == EmptyTree
  }

  override def rangePos(source: SourceFile, start: Int, point: Int, end: Int) = 
    new RangePosition(source, start, point, end)

  /** 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.
   */
  override def wrappingPos(default: Position, trees: List[Tree]): Position = {
    val ranged = trees filter (_.pos.isRange)
    if (ranged.isEmpty) default.focus
    else new RangePosition(default.source, (ranged map (_.pos.start)).min, default.point, (ranged map (_.pos.end)).max)
  }

  /** A position that wraps a 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 ranges, returns a range position enclosing all ranges
   *  Otherwise returns first tree's position.
   */
  override def wrappingPos(trees: List[Tree]): Position = {
    val headpos = trees.head.pos
    if (headpos.isDefined) wrappingPos(headpos, trees) else headpos
  }

/*
  override def integratePos(tree: Tree, pos: Position) = 
    if (pos.isSynthetic && !tree.pos.isSynthetic) tree.syntheticDuplicate 
    else tree
*/

  // -------------- ensuring no overlaps -------------------------------

  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, 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(!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)

  /** Ensure that given tree has no positions that overlap with
   *  any of the positions of `others`. This is done by
   *  shortening the range or assinging TransparentPositions
   *  to some of the nodes in `tree`.
   */
  override def ensureNonOverlapping(tree: Tree, others: List[Tree]) {
    def isOverlapping(pos: Position) = 
      pos.isRange && (others exists (pos overlaps _.pos))
    if (isOverlapping(tree.pos)) {
      val children = tree.children
      children foreach (ensureNonOverlapping(_, others))
      if (tree.pos.isOpaqueRange) {
        val wpos = wrappingPos(tree.pos.focus, children)
        tree setPos (if (isOverlapping(wpos)) tree.pos.makeTransparent else wpos)
      }
    }
  }

  /** 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()
  }

  // -------------- setting 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. All children must be positionable. 
   */
  private def setChildrenPos(pos: Position, trees: List[Tree]): Unit = try {
    for (tree <- trees) {
      if (!tree.isEmpty && 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
  }

  /** 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 (pos.isOpaqueRange) {
      if (!tree.isEmpty && 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 ----------------------------------

  override def validatePositions(tree: Tree) {
    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(tree.toString)
      inform("")
    }
    
    def error(msg: String)(body : => Unit) {
      inform("======= Bad positions: "+msg)
      inform("")
      body
      inform("=== While validating")
      inform("")
      inform(tree.toString)
      inform("")
      inform("=======")
      throw new ValidateError(msg)
    }
    
    def validate(tree: Tree, encltree: Tree): Unit = {
      if (!tree.isEmpty) {
        if (!tree.pos.isDefined) 
          error("Unpositioned tree ["+tree.id+"]") { reportTree("Unpositioned", tree) }
        if (tree.pos.isRange) {
          if (!encltree.pos.isRange)
            error("Synthetic tree ["+encltree.id+"] contains nonsynthetic tree ["+tree.id+"]") {
            reportTree("Enclosing", encltree)
            reportTree("Enclosed", tree)
            }
          if (!(encltree.pos includes tree.pos))
            error("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 => {
              error("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)
      }
    }

    validate(tree, tree)
  }

  class ValidateError(msg : String) extends Exception(msg)

  // ---------------- 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 includes pos) {
        if (!t.pos.isTransparent) last = t
        super.traverse(t)
      }
    }
  }
}