1 | /* |
2 | * Copyright 1999-2006 Sun Microsystems, Inc. All Rights Reserved. |
3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 | * |
5 | * This code is free software; you can redistribute it and/or modify it |
6 | * under the terms of the GNU General Public License version 2 only, as |
7 | * published by the Free Software Foundation. Sun designates this |
8 | * particular file as subject to the "Classpath" exception as provided |
9 | * by Sun in the LICENSE file that accompanied this code. |
10 | * |
11 | * This code is distributed in the hope that it will be useful, but WITHOUT |
12 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
13 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
14 | * version 2 for more details (a copy is included in the LICENSE file that |
15 | * accompanied this code). |
16 | * |
17 | * You should have received a copy of the GNU General Public License version |
18 | * 2 along with this work; if not, write to the Free Software Foundation, |
19 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
20 | * |
21 | * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
22 | * CA 95054 USA or visit www.sun.com if you need additional information or |
23 | * have any questions. |
24 | */ |
25 | |
26 | package com.sun.tools.javac.code; |
27 | |
28 | import com.sun.tools.javac.util.*; |
29 | import java.util.Iterator; |
30 | |
31 | /** A scope represents an area of visibility in a Java program. The |
32 | * Scope class is a container for symbols which provides |
33 | * efficient access to symbols given their names. Scopes are implemented |
34 | * as hash tables. Scopes can be nested; the next field of a scope points |
35 | * to its next outer scope. Nested scopes can share their hash tables. |
36 | * |
37 | * <p><b>This is NOT part of any API supported by Sun Microsystems. If |
38 | * you write code that depends on this, you do so at your own risk. |
39 | * This code and its internal interfaces are subject to change or |
40 | * deletion without notice.</b> |
41 | */ |
42 | public class Scope { |
43 | |
44 | /** The number of scopes that share this scope's hash table. |
45 | */ |
46 | private int shared; |
47 | |
48 | /** Next enclosing scope (with whom this scope may share a hashtable) |
49 | */ |
50 | public Scope next; |
51 | |
52 | /** The scope's owner. |
53 | */ |
54 | public Symbol owner; |
55 | |
56 | /** A hash table for the scope's entries. |
57 | */ |
58 | public Entry[] table; |
59 | |
60 | /** Mask for hash codes, always equal to (table.length - 1). |
61 | */ |
62 | int hashMask; |
63 | |
64 | /** A linear list that also contains all entries in |
65 | * reverse order of appearance (i.e later entries are pushed on top). |
66 | */ |
67 | public Entry elems; |
68 | |
69 | /** The number of elements in this scope. |
70 | */ |
71 | public int nelems = 0; |
72 | |
73 | /** Every hash bucket is a list of Entry's which ends in sentinel. |
74 | */ |
75 | private static final Entry sentinel = new Entry(null, null, null, null); |
76 | |
77 | /** The hash table's initial size. |
78 | */ |
79 | private static final int INITIAL_SIZE = 0x10; |
80 | |
81 | /** A value for the empty scope. |
82 | */ |
83 | public static final Scope emptyScope = new Scope(null, null, new Entry[]{}); |
84 | |
85 | /** Construct a new scope, within scope next, with given owner, using |
86 | * given table. The table's length must be an exponent of 2. |
87 | */ |
88 | Scope(Scope next, Symbol owner, Entry[] table) { |
89 | this.next = next; |
90 | assert emptyScope == null || owner != null; |
91 | this.owner = owner; |
92 | this.table = table; |
93 | this.hashMask = table.length - 1; |
94 | this.elems = null; |
95 | this.nelems = 0; |
96 | this.shared = 0; |
97 | } |
98 | |
99 | /** Construct a new scope, within scope next, with given owner, |
100 | * using a fresh table of length INITIAL_SIZE. |
101 | */ |
102 | public Scope(Symbol owner) { |
103 | this(null, owner, new Entry[INITIAL_SIZE]); |
104 | for (int i = 0; i < INITIAL_SIZE; i++) table[i] = sentinel; |
105 | } |
106 | |
107 | /** Construct a fresh scope within this scope, with same owner, |
108 | * which shares its table with the outer scope. Used in connection with |
109 | * method leave if scope access is stack-like in order to avoid allocation |
110 | * of fresh tables. |
111 | */ |
112 | public Scope dup() { |
113 | Scope result = new Scope(this, this.owner, this.table); |
114 | shared++; |
115 | // System.out.println("====> duping scope " + this.hashCode() + " owned by " + this.owner + " to " + result.hashCode()); |
116 | // new Error().printStackTrace(System.out); |
117 | return result; |
118 | } |
119 | |
120 | /** Construct a fresh scope within this scope, with new owner, |
121 | * which shares its table with the outer scope. Used in connection with |
122 | * method leave if scope access is stack-like in order to avoid allocation |
123 | * of fresh tables. |
124 | */ |
125 | public Scope dup(Symbol newOwner) { |
126 | Scope result = new Scope(this, newOwner, this.table); |
127 | shared++; |
128 | // System.out.println("====> duping scope " + this.hashCode() + " owned by " + newOwner + " to " + result.hashCode()); |
129 | // new Error().printStackTrace(System.out); |
130 | return result; |
131 | } |
132 | |
133 | /** Construct a fresh scope within this scope, with same owner, |
134 | * with a new hash table, whose contents initially are those of |
135 | * the table of its outer scope. |
136 | */ |
137 | public Scope dupUnshared() { |
138 | return new Scope(this, this.owner, this.table.clone()); |
139 | } |
140 | |
141 | /** Remove all entries of this scope from its table, if shared |
142 | * with next. |
143 | */ |
144 | public Scope leave() { |
145 | assert shared == 0; |
146 | if (table != next.table) return next; |
147 | while (elems != null) { |
148 | int hash = elems.sym.name.index & hashMask; |
149 | Entry e = table[hash]; |
150 | assert e == elems : elems.sym; |
151 | table[hash] = elems.shadowed; |
152 | elems = elems.sibling; |
153 | } |
154 | assert next.shared > 0; |
155 | next.shared--; |
156 | // System.out.println("====> leaving scope " + this.hashCode() + " owned by " + this.owner + " to " + next.hashCode()); |
157 | // new Error().printStackTrace(System.out); |
158 | return next; |
159 | } |
160 | |
161 | /** Double size of hash table. |
162 | */ |
163 | private void dble() { |
164 | assert shared == 0; |
165 | Entry[] oldtable = table; |
166 | Entry[] newtable = new Entry[oldtable.length * 2]; |
167 | for (Scope s = this; s != null; s = s.next) { |
168 | if (s.table == oldtable) { |
169 | assert s == this || s.shared != 0; |
170 | s.table = newtable; |
171 | s.hashMask = newtable.length - 1; |
172 | } |
173 | } |
174 | for (int i = 0; i < newtable.length; i++) newtable[i] = sentinel; |
175 | for (int i = 0; i < oldtable.length; i++) copy(oldtable[i]); |
176 | } |
177 | |
178 | /** Copy the given entry and all entries shadowed by it to table |
179 | */ |
180 | private void copy(Entry e) { |
181 | if (e.sym != null) { |
182 | copy(e.shadowed); |
183 | int hash = e.sym.name.index & hashMask; |
184 | e.shadowed = table[hash]; |
185 | table[hash] = e; |
186 | } |
187 | } |
188 | |
189 | /** Enter symbol sym in this scope. |
190 | */ |
191 | public void enter(Symbol sym) { |
192 | assert shared == 0; |
193 | enter(sym, this); |
194 | } |
195 | |
196 | public void enter(Symbol sym, Scope s) { |
197 | enter(sym, s, s); |
198 | } |
199 | |
200 | /** |
201 | * Enter symbol sym in this scope, but mark that it comes from |
202 | * given scope `s' accessed through `origin'. The last two |
203 | * arguments are only used in import scopes. |
204 | */ |
205 | public void enter(Symbol sym, Scope s, Scope origin) { |
206 | assert shared == 0; |
207 | // Temporarily disabled (bug 6460352): |
208 | // if (nelems * 3 >= hashMask * 2) dble(); |
209 | int hash = sym.name.index & hashMask; |
210 | Entry e = makeEntry(sym, table[hash], elems, s, origin); |
211 | table[hash] = e; |
212 | elems = e; |
213 | nelems++; |
214 | } |
215 | |
216 | Entry makeEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, Scope origin) { |
217 | return new Entry(sym, shadowed, sibling, scope); |
218 | } |
219 | |
220 | /** Remove symbol from this scope. Used when an inner class |
221 | * attribute tells us that the class isn't a package member. |
222 | */ |
223 | public void remove(Symbol sym) { |
224 | assert shared == 0; |
225 | Entry e = lookup(sym.name); |
226 | while (e.scope == this && e.sym != sym) e = e.next(); |
227 | if (e.scope == null) return; |
228 | |
229 | // remove e from table and shadowed list; |
230 | Entry te = table[sym.name.index & hashMask]; |
231 | if (te == e) |
232 | table[sym.name.index & hashMask] = e.shadowed; |
233 | else while (true) { |
234 | if (te.shadowed == e) { |
235 | te.shadowed = e.shadowed; |
236 | break; |
237 | } |
238 | te = te.shadowed; |
239 | } |
240 | |
241 | // remove e from elems and sibling list |
242 | te = elems; |
243 | if (te == e) |
244 | elems = e.sibling; |
245 | else while (true) { |
246 | if (te.sibling == e) { |
247 | te.sibling = e.sibling; |
248 | break; |
249 | } |
250 | te = te.sibling; |
251 | } |
252 | } |
253 | |
254 | /** Enter symbol sym in this scope if not already there. |
255 | */ |
256 | public void enterIfAbsent(Symbol sym) { |
257 | assert shared == 0; |
258 | Entry e = lookup(sym.name); |
259 | while (e.scope == this && e.sym.kind != sym.kind) e = e.next(); |
260 | if (e.scope != this) enter(sym); |
261 | } |
262 | |
263 | /** Given a class, is there already a class with same fully |
264 | * qualified name in this (import) scope? |
265 | */ |
266 | public boolean includes(Symbol c) { |
267 | for (Scope.Entry e = lookup(c.name); |
268 | e.scope == this; |
269 | e = e.next()) { |
270 | if (e.sym == c) return true; |
271 | } |
272 | return false; |
273 | } |
274 | |
275 | /** Return the entry associated with given name, starting in |
276 | * this scope and proceeding outwards. If no entry was found, |
277 | * return the sentinel, which is characterized by having a null in |
278 | * both its scope and sym fields, whereas both fields are non-null |
279 | * for regular entries. |
280 | */ |
281 | public Entry lookup(Name name) { |
282 | Entry e = table[name.index & hashMask]; |
283 | while (e.scope != null && e.sym.name != name) |
284 | e = e.shadowed; |
285 | return e; |
286 | } |
287 | |
288 | public Iterable<Symbol> getElements() { |
289 | return new Iterable<Symbol>() { |
290 | public Iterator<Symbol> iterator() { |
291 | return new Iterator<Symbol>() { |
292 | private Scope currScope = Scope.this; |
293 | private Scope.Entry currEntry = elems; |
294 | { |
295 | update(); |
296 | } |
297 | |
298 | public boolean hasNext() { |
299 | return currEntry != null; |
300 | } |
301 | |
302 | public Symbol next() { |
303 | Symbol sym = (currEntry == null ? null : currEntry.sym); |
304 | currEntry = currEntry.sibling; |
305 | update(); |
306 | return sym; |
307 | } |
308 | |
309 | public void remove() { |
310 | throw new UnsupportedOperationException(); |
311 | } |
312 | |
313 | private void update() { |
314 | while (currEntry == null && currScope.next != null) { |
315 | currScope = currScope.next; |
316 | currEntry = currScope.elems; |
317 | } |
318 | } |
319 | }; |
320 | } |
321 | }; |
322 | |
323 | } |
324 | |
325 | public String toString() { |
326 | StringBuilder result = new StringBuilder(); |
327 | result.append("Scope["); |
328 | for (Scope s = this; s != null ; s = s.next) { |
329 | if (s != this) result.append(" | "); |
330 | for (Entry e = s.elems; e != null; e = e.sibling) { |
331 | if (e != s.elems) result.append(", "); |
332 | result.append(e.sym); |
333 | } |
334 | } |
335 | result.append("]"); |
336 | return result.toString(); |
337 | } |
338 | |
339 | /** A class for scope entries. |
340 | */ |
341 | public static class Entry { |
342 | |
343 | /** The referenced symbol. |
344 | * sym == null iff this == sentinel |
345 | */ |
346 | public Symbol sym; |
347 | |
348 | /** An entry with the same hash code, or sentinel. |
349 | */ |
350 | private Entry shadowed; |
351 | |
352 | /** Next entry in same scope. |
353 | */ |
354 | public Entry sibling; |
355 | |
356 | /** The entry's scope. |
357 | * scope == null iff this == sentinel |
358 | * for an entry in an import scope, this is the scope |
359 | * where the entry came from (i.e. was imported from). |
360 | */ |
361 | public Scope scope; |
362 | |
363 | public Entry(Symbol sym, Entry shadowed, Entry sibling, Scope scope) { |
364 | this.sym = sym; |
365 | this.shadowed = shadowed; |
366 | this.sibling = sibling; |
367 | this.scope = scope; |
368 | } |
369 | |
370 | /** Return next entry with the same name as this entry, proceeding |
371 | * outwards if not found in this scope. |
372 | */ |
373 | public Entry next() { |
374 | Entry e = shadowed; |
375 | while (e.scope != null && e.sym.name != sym.name) |
376 | e = e.shadowed; |
377 | return e; |
378 | } |
379 | |
380 | public Scope getOrigin() { |
381 | // The origin is only recorded for import scopes. For all |
382 | // other scope entries, the "enclosing" type is available |
383 | // from other sources. See Attr.visitSelect and |
384 | // Attr.visitIdent. Rather than throwing an assertion |
385 | // error, we return scope which will be the same as origin |
386 | // in many cases. |
387 | return scope; |
388 | } |
389 | } |
390 | |
391 | public static class ImportScope extends Scope { |
392 | |
393 | public ImportScope(Symbol owner) { |
394 | super(owner); |
395 | } |
396 | |
397 | @Override |
398 | Entry makeEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, Scope origin) { |
399 | return new ImportEntry(sym, shadowed, sibling, scope, origin); |
400 | } |
401 | |
402 | public Entry lookup(Name name) { |
403 | Entry e = table[name.index & hashMask]; |
404 | while (e.scope != null && |
405 | (e.sym.name != name || |
406 | /* Since an inner class will show up in package and |
407 | * import scopes until its inner class attribute has |
408 | * been processed, we have to weed it out here. This |
409 | * is done by comparing the owners of the entry's |
410 | * scope and symbol fields. The scope field's owner |
411 | * points to where the class originally was imported |
412 | * from. The symbol field's owner points to where the |
413 | * class is situated now. This can change when an |
414 | * inner class is read (see ClassReader.enterClass). |
415 | * By comparing the two fields we make sure that we do |
416 | * not accidentally import an inner class that started |
417 | * life as a flat class in a package. */ |
418 | e.sym.owner != e.scope.owner)) |
419 | e = e.shadowed; |
420 | return e; |
421 | } |
422 | |
423 | static class ImportEntry extends Entry { |
424 | private Scope origin; |
425 | |
426 | ImportEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, Scope origin) { |
427 | super(sym, shadowed, sibling, scope); |
428 | this.origin = origin; |
429 | } |
430 | public Entry next() { |
431 | Entry e = super.shadowed; |
432 | while (e.scope != null && |
433 | (e.sym.name != sym.name || |
434 | e.sym.owner != e.scope.owner)) // see lookup() |
435 | e = e.shadowed; |
436 | return e; |
437 | } |
438 | |
439 | @Override |
440 | public Scope getOrigin() { return origin; } |
441 | } |
442 | } |
443 | |
444 | /** An empty scope, into which you can't place anything. Used for |
445 | * the scope for a variable initializer. |
446 | */ |
447 | public static class DelegatedScope extends Scope { |
448 | Scope delegatee; |
449 | public static final Entry[] emptyTable = new Entry[0]; |
450 | |
451 | public DelegatedScope(Scope outer) { |
452 | super(outer, outer.owner, emptyTable); |
453 | delegatee = outer; |
454 | } |
455 | public Scope dup() { |
456 | return new DelegatedScope(next); |
457 | } |
458 | public Scope dupUnshared() { |
459 | return new DelegatedScope(next); |
460 | } |
461 | public Scope leave() { |
462 | return next; |
463 | } |
464 | public void enter(Symbol sym) { |
465 | // only anonymous classes could be put here |
466 | } |
467 | public void enter(Symbol sym, Scope s) { |
468 | // only anonymous classes could be put here |
469 | } |
470 | public void remove(Symbol sym) { |
471 | throw new AssertionError(sym); |
472 | } |
473 | public Entry lookup(Name name) { |
474 | return delegatee.lookup(name); |
475 | } |
476 | } |
477 | |
478 | /** An error scope, for which the owner should be an error symbol. */ |
479 | public static class ErrorScope extends Scope { |
480 | ErrorScope(Scope next, Symbol errSymbol, Entry[] table) { |
481 | super(next, /*owner=*/errSymbol, table); |
482 | } |
483 | public ErrorScope(Symbol errSymbol) { |
484 | super(errSymbol); |
485 | } |
486 | public Scope dup() { |
487 | return new ErrorScope(this, owner, table); |
488 | } |
489 | public Scope dupUnshared() { |
490 | return new ErrorScope(this, owner, table.clone()); |
491 | } |
492 | public Entry lookup(Name name) { |
493 | Entry e = super.lookup(name); |
494 | if (e.scope == null) |
495 | return new Entry(owner, null, null, null); |
496 | else |
497 | return e; |
498 | } |
499 | } |
500 | } |