Fri, 29 Oct 2010 12:47:49 -0700
6993304: JavacTrees.getAttrContext not updated to Tree.Kind.{ANNOTATION_TYPE,ENUM,INTERFACE}
Reviewed-by: mcimadamore
1 /*
2 * Copyright (c) 1999, 2010, Oracle and/or its affiliates. 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. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
26 package com.sun.tools.javac.code;
28 import com.sun.tools.javac.util.*;
29 import java.util.Iterator;
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 with "open addressing" and "double hashing".
35 * Scopes can be nested; the next field of a scope points
36 * to its next outer scope. Nested scopes can share their hash tables.
37 *
38 * <p><b>This is NOT part of any supported API.
39 * If you write code that depends on this, you do so at your own risk.
40 * This code and its internal interfaces are subject to change or
41 * deletion without notice.</b>
42 */
43 public class Scope {
45 /** The number of scopes that share this scope's hash table.
46 */
47 private int shared;
49 /** Next enclosing scope (with whom this scope may share a hashtable)
50 */
51 public Scope next;
53 /** The scope's owner.
54 */
55 public Symbol owner;
57 /** A hash table for the scope's entries.
58 */
59 public Entry[] table;
61 /** Mask for hash codes, always equal to (table.length - 1).
62 */
63 int hashMask;
65 /** A linear list that also contains all entries in
66 * reverse order of appearance (i.e later entries are pushed on top).
67 */
68 public Entry elems;
70 /** The number of elements in this scope.
71 * This includes deleted elements, whose value is the sentinel.
72 */
73 public int nelems = 0;
75 /** A timestamp - useful to quickly check whether a scope has changed or not
76 */
77 public ScopeCounter scopeCounter;
79 static ScopeCounter dummyCounter = new ScopeCounter() {
80 @Override
81 public void inc() {
82 //do nothing
83 }
84 };
86 public static class ScopeCounter {
87 protected static final Context.Key<ScopeCounter> scopeCounterKey =
88 new Context.Key<ScopeCounter>();
90 public static ScopeCounter instance(Context context) {
91 ScopeCounter instance = context.get(scopeCounterKey);
92 if (instance == null)
93 instance = new ScopeCounter(context);
94 return instance;
95 }
97 protected ScopeCounter(Context context) {
98 context.put(scopeCounterKey, this);
99 }
101 private ScopeCounter() {};
103 private long val = 0;
105 public void inc() {
106 val++;
107 }
109 public long val() {
110 return val;
111 }
112 }
114 /** Use as a "not-found" result for lookup.
115 * Also used to mark deleted entries in the table.
116 */
117 private static final Entry sentinel = new Entry(null, null, null, null);
119 /** The hash table's initial size.
120 */
121 private static final int INITIAL_SIZE = 0x10;
123 /** A value for the empty scope.
124 */
125 public static final Scope emptyScope = new Scope(null, null, new Entry[]{}, dummyCounter);
127 /** Construct a new scope, within scope next, with given owner, using
128 * given table. The table's length must be an exponent of 2.
129 */
130 private Scope(Scope next, Symbol owner, Entry[] table, ScopeCounter scopeCounter) {
131 this.next = next;
132 assert emptyScope == null || owner != null;
133 this.owner = owner;
134 this.table = table;
135 this.hashMask = table.length - 1;
136 this.scopeCounter = scopeCounter;
137 }
139 /** Convenience constructor used for dup and dupUnshared. */
140 private Scope(Scope next, Symbol owner, Entry[] table) {
141 this(next, owner, table, next.scopeCounter);
142 this.nelems = next.nelems;
143 }
145 /** Construct a new scope, within scope next, with given owner,
146 * using a fresh table of length INITIAL_SIZE.
147 */
148 public Scope(Symbol owner) {
149 this(owner, dummyCounter);
150 }
152 protected Scope(Symbol owner, ScopeCounter scopeCounter) {
153 this(null, owner, new Entry[INITIAL_SIZE], scopeCounter);
154 }
156 /** Construct a fresh scope within this scope, with same owner,
157 * which shares its table with the outer scope. Used in connection with
158 * method leave if scope access is stack-like in order to avoid allocation
159 * of fresh tables.
160 */
161 public Scope dup() {
162 return dup(this.owner);
163 }
165 /** Construct a fresh scope within this scope, with new owner,
166 * which shares its table with the outer scope. Used in connection with
167 * method leave if scope access is stack-like in order to avoid allocation
168 * of fresh tables.
169 */
170 public Scope dup(Symbol newOwner) {
171 Scope result = new Scope(this, newOwner, this.table);
172 shared++;
173 // System.out.println("====> duping scope " + this.hashCode() + " owned by " + newOwner + " to " + result.hashCode());
174 // new Error().printStackTrace(System.out);
175 return result;
176 }
178 /** Construct a fresh scope within this scope, with same owner,
179 * with a new hash table, whose contents initially are those of
180 * the table of its outer scope.
181 */
182 public Scope dupUnshared() {
183 return new Scope(this, this.owner, this.table.clone());
184 }
186 /** Remove all entries of this scope from its table, if shared
187 * with next.
188 */
189 public Scope leave() {
190 assert shared == 0;
191 if (table != next.table) return next;
192 while (elems != null) {
193 int hash = getIndex(elems.sym.name);
194 Entry e = table[hash];
195 assert e == elems : elems.sym;
196 table[hash] = elems.shadowed;
197 elems = elems.sibling;
198 }
199 assert next.shared > 0;
200 next.shared--;
201 next.nelems = nelems;
202 // System.out.println("====> leaving scope " + this.hashCode() + " owned by " + this.owner + " to " + next.hashCode());
203 // new Error().printStackTrace(System.out);
204 return next;
205 }
207 /** Double size of hash table.
208 */
209 private void dble() {
210 assert shared == 0;
211 Entry[] oldtable = table;
212 Entry[] newtable = new Entry[oldtable.length * 2];
213 for (Scope s = this; s != null; s = s.next) {
214 if (s.table == oldtable) {
215 assert s == this || s.shared != 0;
216 s.table = newtable;
217 s.hashMask = newtable.length - 1;
218 }
219 }
220 int n = 0;
221 for (int i = oldtable.length; --i >= 0; ) {
222 Entry e = oldtable[i];
223 if (e != null && e != sentinel) {
224 table[getIndex(e.sym.name)] = e;
225 n++;
226 }
227 }
228 // We don't need to update nelems for shared inherited scopes,
229 // since that gets handled by leave().
230 nelems = n;
231 }
233 /** Enter symbol sym in this scope.
234 */
235 public void enter(Symbol sym) {
236 assert shared == 0;
237 enter(sym, this);
238 }
240 public void enter(Symbol sym, Scope s) {
241 enter(sym, s, s);
242 }
244 /**
245 * Enter symbol sym in this scope, but mark that it comes from
246 * given scope `s' accessed through `origin'. The last two
247 * arguments are only used in import scopes.
248 */
249 public void enter(Symbol sym, Scope s, Scope origin) {
250 assert shared == 0;
251 if (nelems * 3 >= hashMask * 2)
252 dble();
253 int hash = getIndex(sym.name);
254 Entry old = table[hash];
255 if (old == null) {
256 old = sentinel;
257 nelems++;
258 }
259 Entry e = makeEntry(sym, old, elems, s, origin);
260 table[hash] = e;
261 elems = e;
262 scopeCounter.inc();
263 }
265 Entry makeEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, Scope origin) {
266 return new Entry(sym, shadowed, sibling, scope);
267 }
269 /** Remove symbol from this scope. Used when an inner class
270 * attribute tells us that the class isn't a package member.
271 */
272 public void remove(Symbol sym) {
273 assert shared == 0;
274 Entry e = lookup(sym.name);
275 if (e.scope == null) return;
277 scopeCounter.inc();
279 // remove e from table and shadowed list;
280 int i = getIndex(sym.name);
281 Entry te = table[i];
282 if (te == e)
283 table[i] = e.shadowed;
284 else while (true) {
285 if (te.shadowed == e) {
286 te.shadowed = e.shadowed;
287 break;
288 }
289 te = te.shadowed;
290 }
292 // remove e from elems and sibling list
293 te = elems;
294 if (te == e)
295 elems = e.sibling;
296 else while (true) {
297 if (te.sibling == e) {
298 te.sibling = e.sibling;
299 break;
300 }
301 te = te.sibling;
302 }
303 }
305 /** Enter symbol sym in this scope if not already there.
306 */
307 public void enterIfAbsent(Symbol sym) {
308 assert shared == 0;
309 Entry e = lookup(sym.name);
310 while (e.scope == this && e.sym.kind != sym.kind) e = e.next();
311 if (e.scope != this) enter(sym);
312 }
314 /** Given a class, is there already a class with same fully
315 * qualified name in this (import) scope?
316 */
317 public boolean includes(Symbol c) {
318 for (Scope.Entry e = lookup(c.name);
319 e.scope == this;
320 e = e.next()) {
321 if (e.sym == c) return true;
322 }
323 return false;
324 }
326 static final Filter<Symbol> noFilter = new Filter<Symbol>() {
327 public boolean accepts(Symbol s) {
328 return true;
329 }
330 };
332 /** Return the entry associated with given name, starting in
333 * this scope and proceeding outwards. If no entry was found,
334 * return the sentinel, which is characterized by having a null in
335 * both its scope and sym fields, whereas both fields are non-null
336 * for regular entries.
337 */
338 public Entry lookup(Name name) {
339 return lookup(name, noFilter);
340 }
341 public Entry lookup(Name name, Filter<Symbol> sf) {
342 Entry e = table[getIndex(name)];
343 if (e == null || e == sentinel)
344 return sentinel;
345 while (e.scope != null && (e.sym.name != name || !sf.accepts(e.sym)))
346 e = e.shadowed;
347 return e;
348 }
350 /*void dump (java.io.PrintStream out) {
351 out.println(this);
352 for (int l=0; l < table.length; l++) {
353 Entry le = table[l];
354 out.print("#"+l+": ");
355 if (le==sentinel) out.println("sentinel");
356 else if(le == null) out.println("null");
357 else out.println(""+le+" s:"+le.sym);
358 }
359 }*/
361 /** Look for slot in the table.
362 * We use open addressing with double hashing.
363 */
364 int getIndex (Name name) {
365 int h = name.hashCode();
366 int i = h & hashMask;
367 // The expression below is always odd, so it is guaranteed
368 // be be mutually prime with table.length, a power of 2.
369 int x = hashMask - ((h + (h >> 16)) << 1);
370 int d = -1; // Index of a deleted item.
371 for (;;) {
372 Entry e = table[i];
373 if (e == null)
374 return d >= 0 ? d : i;
375 if (e == sentinel) {
376 // We have to keep searching even if we see a deleted item.
377 // However, remember the index in case we fail to find the name.
378 if (d < 0)
379 d = i;
380 } else if (e.sym.name == name)
381 return i;
382 i = (i + x) & hashMask;
383 }
384 }
386 public Iterable<Symbol> getElements() {
387 return getElements(noFilter);
388 }
390 public Iterable<Symbol> getElements(final Filter<Symbol> sf) {
391 return new Iterable<Symbol>() {
392 public Iterator<Symbol> iterator() {
393 return new Iterator<Symbol>() {
394 private Scope currScope = Scope.this;
395 private Scope.Entry currEntry = elems;
396 {
397 update();
398 }
400 public boolean hasNext() {
401 return currEntry != null;
402 }
404 public Symbol next() {
405 Symbol sym = (currEntry == null ? null : currEntry.sym);
406 if (currEntry != null) {
407 currEntry = currEntry.sibling;
408 }
409 update();
410 return sym;
411 }
413 public void remove() {
414 throw new UnsupportedOperationException();
415 }
417 private void update() {
418 skipToNextMatchingEntry();
419 while (currEntry == null && currScope.next != null) {
420 currScope = currScope.next;
421 currEntry = currScope.elems;
422 skipToNextMatchingEntry();
423 }
424 }
426 void skipToNextMatchingEntry() {
427 while (currEntry != null && !sf.accepts(currEntry.sym)) {
428 currEntry = currEntry.sibling;
429 }
430 }
431 };
432 }
433 };
435 }
437 public String toString() {
438 StringBuilder result = new StringBuilder();
439 result.append("Scope[");
440 for (Scope s = this; s != null ; s = s.next) {
441 if (s != this) result.append(" | ");
442 for (Entry e = s.elems; e != null; e = e.sibling) {
443 if (e != s.elems) result.append(", ");
444 result.append(e.sym);
445 }
446 }
447 result.append("]");
448 return result.toString();
449 }
451 /** A class for scope entries.
452 */
453 public static class Entry {
455 /** The referenced symbol.
456 * sym == null iff this == sentinel
457 */
458 public Symbol sym;
460 /** An entry with the same hash code, or sentinel.
461 */
462 private Entry shadowed;
464 /** Next entry in same scope.
465 */
466 public Entry sibling;
468 /** The entry's scope.
469 * scope == null iff this == sentinel
470 * for an entry in an import scope, this is the scope
471 * where the entry came from (i.e. was imported from).
472 */
473 public Scope scope;
475 public Entry(Symbol sym, Entry shadowed, Entry sibling, Scope scope) {
476 this.sym = sym;
477 this.shadowed = shadowed;
478 this.sibling = sibling;
479 this.scope = scope;
480 }
482 /** Return next entry with the same name as this entry, proceeding
483 * outwards if not found in this scope.
484 */
485 public Entry next() {
486 Entry e = shadowed;
487 while (e.scope != null && e.sym.name != sym.name)
488 e = e.shadowed;
489 return e;
490 }
492 public Scope getOrigin() {
493 // The origin is only recorded for import scopes. For all
494 // other scope entries, the "enclosing" type is available
495 // from other sources. See Attr.visitSelect and
496 // Attr.visitIdent. Rather than throwing an assertion
497 // error, we return scope which will be the same as origin
498 // in many cases.
499 return scope;
500 }
501 }
503 public static class ImportScope extends Scope {
505 public ImportScope(Symbol owner) {
506 super(owner);
507 }
509 @Override
510 Entry makeEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, Scope origin) {
511 return new ImportEntry(sym, shadowed, sibling, scope, origin);
512 }
514 public Entry lookup(Name name) {
515 Entry e = table[getIndex(name)];
516 if (e == null)
517 return sentinel;
518 while (e.scope != null &&
519 (/* Since an inner class will show up in package and
520 * import scopes until its inner class attribute has
521 * been processed, we have to weed it out here. This
522 * is done by comparing the owners of the entry's
523 * scope and symbol fields. The scope field's owner
524 * points to where the class originally was imported
525 * from. The symbol field's owner points to where the
526 * class is situated now. This can change when an
527 * inner class is read (see ClassReader.enterClass).
528 * By comparing the two fields we make sure that we do
529 * not accidentally import an inner class that started
530 * life as a flat class in a package. */
531 e.sym.owner != e.scope.owner))
532 e = e.shadowed;
533 return e;
534 }
536 static class ImportEntry extends Entry {
537 private Scope origin;
539 ImportEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, Scope origin) {
540 super(sym, shadowed, sibling, scope);
541 this.origin = origin;
542 }
543 public Entry next() {
544 Entry e = super.shadowed;
545 while (e.scope != null &&
546 (e.sym.name != sym.name ||
547 e.sym.owner != e.scope.owner)) // see lookup()
548 e = e.shadowed;
549 return e;
550 }
552 @Override
553 public Scope getOrigin() { return origin; }
554 }
555 }
557 /** An empty scope, into which you can't place anything. Used for
558 * the scope for a variable initializer.
559 */
560 public static class DelegatedScope extends Scope {
561 Scope delegatee;
562 public static final Entry[] emptyTable = new Entry[0];
564 public DelegatedScope(Scope outer) {
565 super(outer, outer.owner, emptyTable, outer.scopeCounter);
566 delegatee = outer;
567 }
568 public Scope dup() {
569 return new DelegatedScope(next);
570 }
571 public Scope dupUnshared() {
572 return new DelegatedScope(next);
573 }
574 public Scope leave() {
575 return next;
576 }
577 public void enter(Symbol sym) {
578 // only anonymous classes could be put here
579 }
580 public void enter(Symbol sym, Scope s) {
581 // only anonymous classes could be put here
582 }
583 public void remove(Symbol sym) {
584 throw new AssertionError(sym);
585 }
586 public Entry lookup(Name name) {
587 return delegatee.lookup(name);
588 }
589 }
591 /** A class scope, for which a scope counter should be provided */
592 public static class ClassScope extends Scope {
594 ClassScope(Scope next, Symbol owner, Entry[] table, ScopeCounter scopeCounter) {
595 super(next, owner, table, scopeCounter);
596 }
598 public ClassScope(Symbol owner, ScopeCounter scopeCounter) {
599 super(owner, scopeCounter);
600 }
601 }
603 /** An error scope, for which the owner should be an error symbol. */
604 public static class ErrorScope extends Scope {
605 ErrorScope(Scope next, Symbol errSymbol, Entry[] table) {
606 super(next, /*owner=*/errSymbol, table, dummyCounter);
607 }
608 public ErrorScope(Symbol errSymbol) {
609 super(errSymbol);
610 }
611 public Scope dup() {
612 return new ErrorScope(this, owner, table);
613 }
614 public Scope dupUnshared() {
615 return new ErrorScope(this, owner, table.clone());
616 }
617 public Entry lookup(Name name) {
618 Entry e = super.lookup(name);
619 if (e.scope == null)
620 return new Entry(owner, null, null, null);
621 else
622 return e;
623 }
624 }
625 }