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
}
}
}
|
