Skip to content
This repository
Fetching contributors…

Octocat-spinner-32-eaf2f5

Cannot retrieve contributors at this time

file 150 lines (140 sloc) 5.836 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149
/* NSC -- new Scala compiler
* Copyright 2009-2013 Typesafe/Scala Solutions and LAMP/EPFL
* @author Martin Odersky
*/
package scala.tools.nsc
package interactive

import scala.collection.mutable.ArrayBuffer

trait ContextTrees { self: Global =>

  type Context = analyzer.Context
  lazy val NoContext = analyzer.NoContext
  type Contexts = ArrayBuffer[ContextTree]

  /** A context tree contains contexts that are indexed by positions.
* It satisfies the following properties:
* 1. All context come from compiling the same unit.
* 2. Child contexts have parent contexts in their outer chain.
* 3. The `pos` field of a context is the same as `context.tree.pos`, unless that
* position is transparent. In that case, `pos` equals the position of
* one of the solid descendants of `context.tree`.
* 4. Children of a context have non-overlapping increasing positions.
* 5. No context in the tree has a transparent position.
*/
  class ContextTree(val pos: Position, val context: Context, val children: ArrayBuffer[ContextTree]) {
    def this(pos: Position, context: Context) = this(pos, context, new ArrayBuffer[ContextTree])
    override def toString = "ContextTree("+pos+", "+children+")"
  }

  /** Optionally returns the smallest context that contains given `pos`, or None if none exists.
*/
  def locateContext(contexts: Contexts, pos: Position): Option[Context] = synchronized {
    def locateNearestContextTree(contexts: Contexts, pos: Position, recent: Array[ContextTree]): Option[ContextTree] = {
      locateContextTree(contexts, pos) match {
        case Some(x) =>
          recent(0) = x
          locateNearestContextTree(x.children, pos, recent)
        case None => recent(0) match {
            case null => None
            case x => Some(x)
          }
      }
    }
    locateNearestContextTree(contexts, pos, new Array[ContextTree](1)) map (_.context)
  }

  def locateContextTree(contexts: Contexts, pos: Position): Option[ContextTree] = {
    if (contexts.isEmpty) None
    else {
      val hi = contexts.length - 1
      if ((contexts(hi).pos properlyPrecedes pos) || (pos properlyPrecedes contexts(0).pos)) None
      else {
        def loop(lo: Int, hi: Int): Option[ContextTree] = {
          val mid = (lo + hi) / 2
          val midpos = contexts(mid).pos
          if ((pos precedes midpos) && (mid < hi))
            loop(lo, mid)
          else if ((midpos precedes pos) && (lo < mid))
            loop(mid, hi)
          else if (midpos includes pos)
            Some(contexts(mid))
          else if (contexts(mid+1).pos includes pos)
            Some(contexts(mid+1))
          else None
        }
        loop(0, hi)
      }
    }
  }

  /** Insert a context at correct position into a buffer of context trees.
* If the `context` has a transparent position, add it multiple times
* at the positions of all its solid descendant trees.
*/
  def addContext(contexts: Contexts, context: Context): Unit = {
    val cpos = context.tree.pos
    if (cpos.isTransparent)
      for (t <- context.tree.children flatMap solidDescendants)
        addContext(contexts, context, t.pos)
    else
      addContext(contexts, context, cpos)
  }

  /** Insert a context with non-transparent position `cpos`
* at correct position into a buffer of context trees.
*/
  def addContext(contexts: Contexts, context: Context, cpos: Position): Unit = synchronized {
    try {
      if (!cpos.isRange) {}
      else if (contexts.isEmpty) contexts += new ContextTree(cpos, context)
      else {
        val hi = contexts.length - 1
        if (contexts(hi).pos precedes cpos)
          contexts += new ContextTree(cpos, context)
        else if (contexts(hi).pos properlyIncludes cpos) // fast path w/o search
          addContext(contexts(hi).children, context, cpos)
        else if (cpos precedes contexts(0).pos)
          new ContextTree(cpos, context) +=: contexts
        else {
          def insertAt(idx: Int): Boolean = {
            val oldpos = contexts(idx).pos
            if (oldpos sameRange cpos) {
              contexts(idx) = new ContextTree(cpos, context, contexts(idx).children)
              true
            } else if (oldpos includes cpos) {
              addContext(contexts(idx).children, context, cpos)
              true
            } else if (cpos includes oldpos) {
              val start = contexts.indexWhere(cpos includes _.pos)
              val last = contexts.lastIndexWhere(cpos includes _.pos)
              contexts(start) = new ContextTree(cpos, context, contexts.slice(start, last + 1))
              contexts.remove(start + 1, last - start)
              true
            } else false
          }
          def loop(lo: Int, hi: Int) {
            if (hi - lo > 1) {
              val mid = (lo + hi) / 2
              val midpos = contexts(mid).pos
              if (cpos precedes midpos)
                loop(lo, mid)
              else if (midpos precedes cpos)
                loop(mid, hi)
              else
                addContext(contexts(mid).children, context, cpos)
            } else if (!insertAt(lo) && !insertAt(hi)) {
              val lopos = contexts(lo).pos
              val hipos = contexts(hi).pos
              if ((lopos precedes cpos) && (cpos precedes hipos))
                contexts.insert(hi, new ContextTree(cpos, context))
              else
                inform("internal error? skewed positions: "+lopos+" !< "+cpos+" !< "+hipos)
            }
          }
          loop(0, hi)
        }
      }
    } catch {
      case ex: Throwable =>
        println(ex)
        ex.printStackTrace()
        println("failure inserting "+cpos+" into "+contexts+"/"+contexts(contexts.length - 1).pos+"/"+
                (contexts(contexts.length - 1).pos includes cpos))
        throw ex
    }
  }
}

Something went wrong with that request. Please try again.