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
|
/* NSC -- new Scala compiler
* Copyright 2005-2010 LAMP/EPFL
* @author Martin Odersky
*/
package scala.tools.nsc
package transform
import collection.mutable.HashMap
import symtab.Flags._
import util.HashSet
import annotation.tailrec
/** A class that yields a kind of iterator (`Cursor`),
* which yields all pairs of overriding/overridden symbols
* that are visible in some baseclass, unless there's a parent class
* that already contains the same pairs.
* @author Martin Odersky
* @version 1.0
*/
abstract class OverridingPairs {
val global: Global
import global._
/** The cursor class
* @param base the base class that contains the overriding pairs
*/
class Cursor(base: Symbol) {
private val self = base.thisType
/** Symbols to exclude: Here these are constructors, private locals,
* and bridges. But it may be refined in subclasses.
*
*/
protected def exclude(sym: Symbol): Boolean =
sym.isConstructor || sym.isPrivateLocal || sym.hasFlag(BRIDGE)
/** The parents of base (may also be refined).
*/
protected def parents: List[Type] = base.info.parents
/** Does `sym1` match `sym2` so that it qualifies as overriding.
* Types always match. Term symbols match if their membertypes
* relative to <base>.this do
*/
protected def matches(sym1: Symbol, sym2: Symbol): Boolean =
sym1.isType || (self.memberType(sym1) matches self.memberType(sym2))
/** An implementation of BitSets as arrays (maybe consider collection.BitSet
* for that?) The main purpose of this is to implement
* intersectionContainsElement efficiently.
*/
private type BitSet = Array[Int]
private def newBitSet(size: Int): BitSet = new Array((size + 31) >> 5)
private def include(bs: BitSet, n: Int) {
val nshifted = n >> 5
val nmask = 1 << (n & 31)
bs(nshifted) = bs(nshifted) | nmask
}
/** Implements `bs1 * bs2 * {0..n} != 0.
* Used in hasCommonParentAsSubclass */
private def intersectionContainsElementLeq(bs1: BitSet, bs2: BitSet, n: Int): Boolean = {
val nshifted = n >> 5
val nmask = 1 << (n & 31)
var i = 0
while (i < nshifted) {
if ((bs1(i) & bs2(i)) != 0) return true
i += 1
}
(bs1(nshifted) & bs2(nshifted) & (nmask | nmask - 1)) != 0
}
/** The symbols that can take part in an overriding pair */
private val decls = new Scope
// fill `decls` with overriding shadowing overridden */
{ def fillDecls(bcs: List[Symbol], deferredflag: Int) {
if (!bcs.isEmpty) {
fillDecls(bcs.tail, deferredflag)
var e = bcs.head.info.decls.elems;
while (e ne null) {
if (e.sym.getFlag(DEFERRED) == deferredflag.toLong && !exclude(e.sym))
decls enter e.sym;
e = e.next
}
}
}
// first, deferred (this wil need to change if we change lookup rules!
fillDecls(base.info.baseClasses, DEFERRED)
// then, concrete.
fillDecls(base.info.baseClasses, 0)
}
private val size = base.info.baseClasses.length
/** A map from baseclasses of <base> to ints, with smaller ints meaning lower in
* linearization order.
*/
private val index = new HashMap[Symbol, Int]
// Note: overridingPairs can be called at odd instances by the Eclipse plugin
// Soemtimes symbols are not yet defined and we get missing keys.
// The implementation here is hardened so that it does not crash on a missing key.
{ var i = 0
for (bc <- base.info.baseClasses) {
index(bc) = i
i += 1
}
}
/** A mapping from all base class indices to a bitset
* which indicates whether parents are subclasses.
*
* i \in subParents(j) iff
* exists p \in parents, b \in baseClasses:
* i = index(p)
* j = index(b)
* p isSubClass b
* p.baseType(b) == self.baseType(b)
*/
private val subParents = new Array[BitSet](size)
{ for (i <- List.range(0, size))
subParents(i) = new BitSet(size);
for (p <- parents) {
index get p.typeSymbol match {
case Some(pIndex) =>
for (bc <- p.baseClasses)
if (p.baseType(bc) =:= self.baseType(bc))
index get bc match {
case Some(bcIndex) =>
include(subParents(bcIndex), pIndex)
case None =>
}
else if (settings.debug.value)
log("SKIPPING "+p+" -> "+p.baseType(bc)+" / "+self.baseType(bc)+" from "+base)
case None =>
}
}
}
/** Do `sym1` and `sym2` have a common subclass in `parents`?
* In that case we do not follow their overriding pairs
*/
private def hasCommonParentAsSubclass(sym1: Symbol, sym2: Symbol) = {
index get sym1.owner match {
case Some(index1) =>
index get sym2.owner match {
case Some(index2) =>
intersectionContainsElementLeq(subParents(index1), subParents(index2), index1 min index2)
case None =>
false
}
case None =>
false
}
}
/** The scope entries that have already been visited as overridden
* (maybe excluded because of hasCommonParentAsSubclass).
* These will not appear as overriding
*/
private val visited = new HashSet[ScopeEntry]("visited", 64)
/** The current entry candidate for overriding
*/
private var curEntry = decls.elems
/** The current entry candidate for overridden */
private var nextEntry = curEntry
/** The current candidate symbol for overriding */
var overriding: Symbol = _
/** If not null: The symbol overridden by overriding */
var overridden: Symbol = _
//@M: note that next is called once during object initialization
def hasNext: Boolean = curEntry ne null
@tailrec
final def next {
if (curEntry ne null) {
overriding = curEntry.sym
if (nextEntry ne null) {
do {
do {
nextEntry = decls.lookupNextEntry(nextEntry);
/* DEBUG
if ((nextEntry ne null) &&
!(nextEntry.sym hasFlag PRIVATE) &&
!(overriding.owner == nextEntry.sym.owner) &&
!matches(overriding, nextEntry.sym))
println("skipping "+overriding+":"+self.memberType(overriding)+overriding.locationString+" to "+nextEntry.sym+":"+self.memberType(nextEntry.sym)+nextEntry.sym.locationString)
*/
} while ((nextEntry ne null) &&
((nextEntry.sym hasFlag PRIVATE) ||
(overriding.owner == nextEntry.sym.owner) ||
(!matches(overriding, nextEntry.sym)) ||
(exclude(overriding))))
if (nextEntry ne null) visited addEntry nextEntry
// skip nextEntry if a class in `parents` is a subclass of the owners of both
// overriding and nextEntry.sym
} while ((nextEntry ne null) && (hasCommonParentAsSubclass(overriding, nextEntry.sym)))
if (nextEntry ne null) {
overridden = nextEntry.sym;
//Console.println("yield: " + overriding + overriding.locationString + " / " + overridden + overridden.locationString);//DEBUG
} else {
do {
curEntry = curEntry.next
} while ((curEntry ne null) && (visited contains curEntry));
nextEntry = curEntry
next
}
}
}
}
next
}
}
|
