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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
|
/* NSC -- new Scala compiler
* Copyright 2005-2010 LAMP/EPFL
* @author Martin Odersky
*/
package scala.tools.nsc
package symtab
// Martin: I am about 1/4 way on a cleanup of scopes.
// The most important change is that scopes are now Iterables.
// This removed the need for the various iterators on ScopeEntries.
// ScopeEntries are conceptually an internal representation detail,
// so it's better not to return them in public iterators.
// It's true that other code also references ScopeEntries but that's
// done for performance (and could be reviewed).
// Another addition is a lookupAll method that returns all symbols with
// a name in a scopein an iterator.
trait Scopes {
self: SymbolTable =>
class ScopeEntry(val sym: Symbol, val owner: Scope) {
/** the next entry in the hash bucket
*/
var tail: ScopeEntry = null
/** the next entry in this scope
*/
var next: ScopeEntry = null
override def hashCode(): Int = sym.name.start
override def toString(): String = sym.toString()
}
/**
* @param sym ...
* @param owner ...
* @return ...
*/
private def newScopeEntry(sym: Symbol, owner: Scope): ScopeEntry = {
val e = new ScopeEntry(sym, owner)
e.next = owner.elems
owner.elems = e
e
}
class Scope(initElems: ScopeEntry) extends AbsScope {
var elems: ScopeEntry = initElems
/** The number of times this scope is nested in another
*/
private var nestinglevel = 0
/** the hash table
*/
private var hashtable: Array[ScopeEntry] = null
/** a cache for all elements, to be used by symbol iterator.
*/
private var elemsCache: List[Symbol] = null
/** size and mask of hash tables
* todo: make hashtables grow?
*/
private val HASHSIZE = 0x80
private val HASHMASK = 0x7f
/** the threshold number of entries from which a hashtable is constructed.
*/
private val MIN_HASH = 8
if (size >= MIN_HASH) createHash()
def this() = this(null: ScopeEntry)
def this(base: Scope) = {
this(base.elems)
nestinglevel = base.nestinglevel + 1
}
def this(decls: List[Symbol]) = {
this()
decls foreach enter
}
/** Returns a new scope with the same content as this one. */
def cloneScope: Scope = {
val clone = new Scope()
this.toList foreach (clone enter _)
clone
}
/** is the scope empty? */
override def isEmpty: Boolean = elems eq null
/** the number of entries in this scope */
override def size: Int = {
var s = 0
var e = elems
while (e ne null) {
s += 1
e = e.next
}
s
}
/** enter a scope entry
*
* @param e ...
*/
def enter(e: ScopeEntry) {
elemsCache = null
if (hashtable ne null) {
val i = e.sym.name.start & HASHMASK
elems.tail = hashtable(i)
hashtable(i) = elems
} else if (size >= MIN_HASH) {
createHash()
}
}
/** enter a symbol
*
* @param sym ...
*/
def enter(sym: Symbol): Symbol = { enter(newScopeEntry(sym, this)); sym }
/** enter a symbol, asserting that no symbol with same name exists in scope
*
* @param sym ...
*/
def enterUnique(sym: Symbol) {
assert(lookup(sym.name) == NoSymbol)
enter(sym)
}
private def createHash() {
hashtable = new Array[ScopeEntry](HASHSIZE)
enterInHash(elems)
}
private def enterInHash(e: ScopeEntry) {
if (e ne null) {
enterInHash(e.next)
val i = e.sym.name.start & HASHMASK
e.tail = hashtable(i)
hashtable(i) = e
}
}
def rehash(sym: Symbol, newname: Name) {
if (hashtable ne null) {
val index = sym.name.start & HASHMASK
var e1 = hashtable(index)
var e: ScopeEntry = null
if (e1 != null) {
if (e1.sym == sym) {
hashtable(index) = e1.tail
e = e1
} else {
while (e1.tail != null && e1.tail.sym != sym) e1 = e1.tail
if (e1.tail != null) {
e = e1.tail
e1.tail = e.tail
}
}
}
if (e != null) {
val newindex = newname.start & HASHMASK
e.tail = hashtable(newindex)
hashtable(newindex) = e
}
}
}
/** remove entry
*
* @param e ...
*/
def unlink(e: ScopeEntry) {
if (elems == e) {
elems = e.next
} else {
var e1 = elems
while (e1.next != e) e1 = e1.next
e1.next = e.next
}
if (hashtable ne null) {
val index = e.sym.name.start & HASHMASK
var e1 = hashtable(index)
if (e1 == e) {
hashtable(index) = e.tail
} else {
while (e1.tail != e) e1 = e1.tail;
e1.tail = e.tail
}
}
elemsCache = null
}
/** remove symbol */
def unlink(sym: Symbol) {
var e = lookupEntry(sym.name)
while (e ne null) {
if (e.sym == sym) unlink(e);
e = lookupNextEntry(e)
}
}
/** lookup a symbol
*
* @param name ...
* @return ...
*/
def lookup(name: Name): Symbol = {
val e = lookupEntry(name)
if (e eq null) NoSymbol else e.sym
}
/** Returns an iterator eidling every symbol with given name in this scope.
*/
def lookupAll(name: Name): Iterator[Symbol] = new Iterator[Symbol] {
var e = lookupEntry(name)
def hasNext: Boolean = e ne null
def next: Symbol = { val r = e.sym; e = lookupNextEntry(e); r }
}
/** lookup a symbol entry matching given name.
* @note from Martin: I believe this is a hotspot or will be one
* in future versions of the type system. I have reverted the previous
* change to use iterators as too costly.
*/
def lookupEntry(name: Name): ScopeEntry = {
var e: ScopeEntry = null
if (hashtable ne null) {
e = hashtable(name.start & HASHMASK)
while ((e ne null) && e.sym.name != name) {
e = e.tail
}
} else {
e = elems
while ((e ne null) && e.sym.name != name) {
e = e.next
}
}
e
}
/** lookup next entry with same name as this one
* @note from Martin: I believe this is a hotspot or will be one
* in future versions of the type system. I have reverted the previous
* change to use iterators as too costly.
*/
def lookupNextEntry(entry: ScopeEntry): ScopeEntry = {
var e = entry
if (hashtable ne null)
do { e = e.tail } while ((e ne null) && e.sym.name != entry.sym.name)
else
do { e = e.next } while ((e ne null) && e.sym.name != entry.sym.name);
e
}
/** Return all symbols as a list in the order they were entered in this scope.
*/
override def toList: List[Symbol] = {
if (elemsCache eq null) {
elemsCache = Nil
var e = elems
while ((e ne null) && e.owner == this) {
elemsCache = e.sym :: elemsCache
e = e.next
}
}
elemsCache
}
/** Return the nesting level of this scope, i.e. the number of times this scope
* was nested in another */
def nestingLevel = nestinglevel
/** Return all symbols as an iterator in the order they were entered in this scope.
*/
def iterator: Iterator[Symbol] = toList.iterator
/*
/** Does this scope contain an entry for `sym`?
*/
def contains(sym: Symbol): Boolean = lookupAll(sym.name) contains sym
/** A scope that contains all symbols of this scope and that also contains `sym`.
*/
def +(sym: Symbol): Scope =
if (contains(sym)) this
else {
val result = cloneScope
result enter sym
result
}
/** A scope that contains all symbols of this scope except `sym`.
*/
def -(sym: Symbol): Scope =
if (!contains(sym)) this
else {
val result = cloneScope
result unlink sym
result
}
*/
override def foreach[U](p: Symbol => U): Unit = toList foreach p
override def filter(p: Symbol => Boolean): Scope =
if (!(toList forall p)) new Scope(toList filter p) else this
override def mkString(start: String, sep: String, end: String) =
toList.map(_.defString).mkString(start, sep, end)
override def toString(): String = mkString("Scope{\n ", ";\n ", "\n}")
}
def newScope: Scope = new Scope
/** The empty scope (immutable).
*/
object EmptyScope extends Scope {
override def enter(e: ScopeEntry) {
abort("EmptyScope.enter")
}
}
/** The error scope.
*/
class ErrorScope(owner: Symbol) extends Scope(null: ScopeEntry)
}
|