001: /*
002: * Copyright 1999-2006 Sun Microsystems, Inc. All Rights Reserved.
003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004: *
005: * This code is free software; you can redistribute it and/or modify it
006: * under the terms of the GNU General Public License version 2 only, as
007: * published by the Free Software Foundation. Sun designates this
008: * particular file as subject to the "Classpath" exception as provided
009: * by Sun in the LICENSE file that accompanied this code.
010: *
011: * This code is distributed in the hope that it will be useful, but WITHOUT
012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014: * version 2 for more details (a copy is included in the LICENSE file that
015: * accompanied this code).
016: *
017: * You should have received a copy of the GNU General Public License version
018: * 2 along with this work; if not, write to the Free Software Foundation,
019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022: * CA 95054 USA or visit www.sun.com if you need additional information or
023: * have any questions.
024: */
025:
026: package com.sun.tools.javac.code;
027:
028: import com.sun.tools.javac.util.*;
029: import java.util.Iterator;
030:
031: /** A scope represents an area of visibility in a Java program. The
032: * Scope class is a container for symbols which provides
033: * efficient access to symbols given their names. Scopes are implemented
034: * as hash tables. Scopes can be nested; the next field of a scope points
035: * to its next outer scope. Nested scopes can share their hash tables.
036: *
037: * <p><b>This is NOT part of any API supported by Sun Microsystems. If
038: * you write code that depends on this, you do so at your own risk.
039: * This code and its internal interfaces are subject to change or
040: * deletion without notice.</b>
041: */
042: @Version("@(#)Scope.java 1.47 07/05/05")
043: public class Scope {
044:
045: /** The number of scopes that share this scope's hash table.
046: */
047: private int shared;
048:
049: /** Next enclosing scope (with whom this scope may share a hashtable)
050: */
051: public Scope next;
052:
053: /** The scope's owner.
054: */
055: public Symbol owner;
056:
057: /** A hash table for the scope's entries.
058: */
059: public Entry[] table;
060:
061: /** Mask for hash codes, always equal to (table.length - 1).
062: */
063: int hashMask;
064:
065: /** A linear list that also contains all entries in
066: * reverse order of appearance (i.e later entries are pushed on top).
067: */
068: public Entry elems;
069:
070: /** The number of elements in this scope.
071: */
072: public int nelems = 0;
073:
074: /** Every hash bucket is a list of Entry's which ends in sentinel.
075: */
076: private static final Entry sentinel = new Entry(null, null, null,
077: null);
078:
079: /** The hash table's initial size.
080: */
081: private static final int INITIAL_SIZE = 0x10;
082:
083: /** A value for the empty scope.
084: */
085: public static final Scope emptyScope = new Scope(null, null,
086: new Entry[] {});
087:
088: /** Construct a new scope, within scope next, with given owner, using
089: * given table. The table's length must be an exponent of 2.
090: */
091: Scope(Scope next, Symbol owner, Entry[] table) {
092: this .next = next;
093: assert emptyScope == null || owner != null;
094: this .owner = owner;
095: this .table = table;
096: this .hashMask = table.length - 1;
097: this .elems = null;
098: this .nelems = 0;
099: this .shared = 0;
100: }
101:
102: /** Construct a new scope, within scope next, with given owner,
103: * using a fresh table of length INITIAL_SIZE.
104: */
105: public Scope(Symbol owner) {
106: this (null, owner, new Entry[INITIAL_SIZE]);
107: for (int i = 0; i < INITIAL_SIZE; i++)
108: table[i] = sentinel;
109: }
110:
111: /** Construct a fresh scope within this scope, with same owner,
112: * which shares its table with the outer scope. Used in connection with
113: * method leave if scope access is stack-like in order to avoid allocation
114: * of fresh tables.
115: */
116: public Scope dup() {
117: Scope result = new Scope(this , this .owner, this .table);
118: shared++;
119: // System.out.println("====> duping scope " + this.hashCode() + " owned by " + this.owner + " to " + result.hashCode());
120: // new Error().printStackTrace(System.out);
121: return result;
122: }
123:
124: /** Construct a fresh scope within this scope, with new owner,
125: * which shares its table with the outer scope. Used in connection with
126: * method leave if scope access is stack-like in order to avoid allocation
127: * of fresh tables.
128: */
129: public Scope dup(Symbol newOwner) {
130: Scope result = new Scope(this , newOwner, this .table);
131: shared++;
132: // System.out.println("====> duping scope " + this.hashCode() + " owned by " + newOwner + " to " + result.hashCode());
133: // new Error().printStackTrace(System.out);
134: return result;
135: }
136:
137: /** Construct a fresh scope within this scope, with same owner,
138: * with a new hash table, whose contents initially are those of
139: * the table of its outer scope.
140: */
141: public Scope dupUnshared() {
142: return new Scope(this , this .owner, this .table.clone());
143: }
144:
145: /** Remove all entries of this scope from its table, if shared
146: * with next.
147: */
148: public Scope leave() {
149: assert shared == 0;
150: if (table != next.table)
151: return next;
152: while (elems != null) {
153: int hash = elems.sym.name.index & hashMask;
154: Entry e = table[hash];
155: assert e == elems : elems.sym;
156: table[hash] = elems.shadowed;
157: elems = elems.sibling;
158: }
159: assert next.shared > 0;
160: next.shared--;
161: // System.out.println("====> leaving scope " + this.hashCode() + " owned by " + this.owner + " to " + next.hashCode());
162: // new Error().printStackTrace(System.out);
163: return next;
164: }
165:
166: /** Double size of hash table.
167: */
168: private void dble() {
169: assert shared == 0;
170: Entry[] oldtable = table;
171: Entry[] newtable = new Entry[oldtable.length * 2];
172: for (Scope s = this ; s != null; s = s.next) {
173: if (s.table == oldtable) {
174: assert s == this || s.shared != 0;
175: s.table = newtable;
176: s.hashMask = newtable.length - 1;
177: }
178: }
179: for (int i = 0; i < newtable.length; i++)
180: newtable[i] = sentinel;
181: for (int i = 0; i < oldtable.length; i++)
182: copy(oldtable[i]);
183: }
184:
185: /** Copy the given entry and all entries shadowed by it to table
186: */
187: private void copy(Entry e) {
188: if (e.sym != null) {
189: copy(e.shadowed);
190: int hash = e.sym.name.index & hashMask;
191: e.shadowed = table[hash];
192: table[hash] = e;
193: }
194: }
195:
196: /** Enter symbol sym in this scope.
197: */
198: public void enter(Symbol sym) {
199: assert shared == 0;
200: enter(sym, this );
201: }
202:
203: public void enter(Symbol sym, Scope s) {
204: enter(sym, s, s);
205: }
206:
207: /**
208: * Enter symbol sym in this scope, but mark that it comes from
209: * given scope `s' accessed through `origin'. The last two
210: * arguments are only used in import scopes.
211: */
212: public void enter(Symbol sym, Scope s, Scope origin) {
213: assert shared == 0;
214: // Temporarily disabled (bug 6460352):
215: // if (nelems * 3 >= hashMask * 2) dble();
216: int hash = sym.name.index & hashMask;
217: Entry e = makeEntry(sym, table[hash], elems, s, origin);
218: table[hash] = e;
219: elems = e;
220: nelems++;
221: }
222:
223: Entry makeEntry(Symbol sym, Entry shadowed, Entry sibling,
224: Scope scope, Scope origin) {
225: return new Entry(sym, shadowed, sibling, scope);
226: }
227:
228: /** Remove symbol from this scope. Used when an inner class
229: * attribute tells us that the class isn't a package member.
230: */
231: public void remove(Symbol sym) {
232: assert shared == 0;
233: Entry e = lookup(sym.name);
234: while (e.scope == this && e.sym != sym)
235: e = e.next();
236: if (e.scope == null)
237: return;
238:
239: // remove e from table and shadowed list;
240: Entry te = table[sym.name.index & hashMask];
241: if (te == e)
242: table[sym.name.index & hashMask] = e.shadowed;
243: else
244: while (true) {
245: if (te.shadowed == e) {
246: te.shadowed = e.shadowed;
247: break;
248: }
249: te = te.shadowed;
250: }
251:
252: // remove e from elems and sibling list
253: te = elems;
254: if (te == e)
255: elems = e.sibling;
256: else
257: while (true) {
258: if (te.sibling == e) {
259: te.sibling = e.sibling;
260: break;
261: }
262: te = te.sibling;
263: }
264: }
265:
266: /** Enter symbol sym in this scope if not already there.
267: */
268: public void enterIfAbsent(Symbol sym) {
269: assert shared == 0;
270: Entry e = lookup(sym.name);
271: while (e.scope == this && e.sym.kind != sym.kind)
272: e = e.next();
273: if (e.scope != this )
274: enter(sym);
275: }
276:
277: /** Given a class, is there already a class with same fully
278: * qualified name in this (import) scope?
279: */
280: public boolean includes(Symbol c) {
281: for (Scope.Entry e = lookup(c.name); e.scope == this ; e = e
282: .next()) {
283: if (e.sym == c)
284: return true;
285: }
286: return false;
287: }
288:
289: /** Return the entry associated with given name, starting in
290: * this scope and proceeding outwards. If no entry was found,
291: * return the sentinel, which is characterized by having a null in
292: * both its scope and sym fields, whereas both fields are non-null
293: * for regular entries.
294: */
295: public Entry lookup(Name name) {
296: Entry e = table[name.index & hashMask];
297: while (e.scope != null && e.sym.name != name)
298: e = e.shadowed;
299: return e;
300: }
301:
302: public Iterable<Symbol> getElements() {
303: return new Iterable<Symbol>() {
304: public Iterator<Symbol> iterator() {
305: return new Iterator<Symbol>() {
306: private Scope currScope = Scope.this ;
307: private Scope.Entry currEntry = elems;
308: {
309: update();
310: }
311:
312: public boolean hasNext() {
313: return currEntry != null;
314: }
315:
316: public Symbol next() {
317: Symbol sym = (currEntry == null ? null
318: : currEntry.sym);
319: currEntry = currEntry.sibling;
320: update();
321: return sym;
322: }
323:
324: public void remove() {
325: throw new UnsupportedOperationException();
326: }
327:
328: private void update() {
329: while (currEntry == null
330: && currScope.next != null) {
331: currScope = currScope.next;
332: currEntry = currScope.elems;
333: }
334: }
335: };
336: }
337: };
338:
339: }
340:
341: public String toString() {
342: StringBuilder result = new StringBuilder();
343: result.append("Scope[");
344: for (Scope s = this ; s != null; s = s.next) {
345: if (s != this )
346: result.append(" | ");
347: for (Entry e = s.elems; e != null; e = e.sibling) {
348: if (e != s.elems)
349: result.append(", ");
350: result.append(e.sym);
351: }
352: }
353: result.append("]");
354: return result.toString();
355: }
356:
357: /** A class for scope entries.
358: */
359: public static class Entry {
360:
361: /** The referenced symbol.
362: * sym == null iff this == sentinel
363: */
364: public Symbol sym;
365:
366: /** An entry with the same hash code, or sentinel.
367: */
368: private Entry shadowed;
369:
370: /** Next entry in same scope.
371: */
372: public Entry sibling;
373:
374: /** The entry's scope.
375: * scope == null iff this == sentinel
376: * for an entry in an import scope, this is the scope
377: * where the entry came from (i.e. was imported from).
378: */
379: public Scope scope;
380:
381: public Entry(Symbol sym, Entry shadowed, Entry sibling,
382: Scope scope) {
383: this .sym = sym;
384: this .shadowed = shadowed;
385: this .sibling = sibling;
386: this .scope = scope;
387: }
388:
389: /** Return next entry with the same name as this entry, proceeding
390: * outwards if not found in this scope.
391: */
392: public Entry next() {
393: Entry e = shadowed;
394: while (e.scope != null && e.sym.name != sym.name)
395: e = e.shadowed;
396: return e;
397: }
398:
399: public Scope getOrigin() {
400: // The origin is only recorded for import scopes. For all
401: // other scope entries, the "enclosing" type is available
402: // from other sources. See Attr.visitSelect and
403: // Attr.visitIdent. Rather than throwing an assertion
404: // error, we return scope which will be the same as origin
405: // in many cases.
406: return scope;
407: }
408: }
409:
410: public static class ImportScope extends Scope {
411:
412: public ImportScope(Symbol owner) {
413: super (owner);
414: }
415:
416: @Override
417: Entry makeEntry(Symbol sym, Entry shadowed, Entry sibling,
418: Scope scope, Scope origin) {
419: return new ImportEntry(sym, shadowed, sibling, scope,
420: origin);
421: }
422:
423: public Entry lookup(Name name) {
424: Entry e = table[name.index & hashMask];
425: while (e.scope != null && (e.sym.name != name ||
426: /* Since an inner class will show up in package and
427: * import scopes until its inner class attribute has
428: * been processed, we have to weed it out here. This
429: * is done by comparing the owners of the entry's
430: * scope and symbol fields. The scope field's owner
431: * points to where the class originally was imported
432: * from. The symbol field's owner points to where the
433: * class is situated now. This can change when an
434: * inner class is read (see ClassReader.enterClass).
435: * By comparing the two fields we make sure that we do
436: * not accidentally import an inner class that started
437: * life as a flat class in a package. */
438: e.sym.owner != e.scope.owner))
439: e = e.shadowed;
440: return e;
441: }
442:
443: static class ImportEntry extends Entry {
444: private Scope origin;
445:
446: ImportEntry(Symbol sym, Entry shadowed, Entry sibling,
447: Scope scope, Scope origin) {
448: super (sym, shadowed, sibling, scope);
449: this .origin = origin;
450: }
451:
452: public Entry next() {
453: Entry e = super .shadowed;
454: while (e.scope != null
455: && (e.sym.name != sym.name || e.sym.owner != e.scope.owner))
456: // see lookup()
457: e = e.shadowed;
458: return e;
459: }
460:
461: @Override
462: public Scope getOrigin() {
463: return origin;
464: }
465: }
466: }
467:
468: /** An empty scope, into which you can't place anything. Used for
469: * the scope for a variable initializer.
470: */
471: public static class DelegatedScope extends Scope {
472: Scope delegatee;
473: public static final Entry[] emptyTable = new Entry[0];
474:
475: public DelegatedScope(Scope outer) {
476: super (outer, outer.owner, emptyTable);
477: delegatee = outer;
478: }
479:
480: public Scope dup() {
481: return new DelegatedScope(next);
482: }
483:
484: public Scope dupUnshared() {
485: return new DelegatedScope(next);
486: }
487:
488: public Scope leave() {
489: return next;
490: }
491:
492: public void enter(Symbol sym) {
493: // only anonymous classes could be put here
494: }
495:
496: public void enter(Symbol sym, Scope s) {
497: // only anonymous classes could be put here
498: }
499:
500: public void remove(Symbol sym) {
501: throw new AssertionError(sym);
502: }
503:
504: public Entry lookup(Name name) {
505: return delegatee.lookup(name);
506: }
507: }
508:
509: /** An error scope, for which the owner should be an error symbol. */
510: public static class ErrorScope extends Scope {
511: ErrorScope(Scope next, Symbol errSymbol, Entry[] table) {
512: super (next, /*owner=*/errSymbol, table);
513: }
514:
515: public ErrorScope(Symbol errSymbol) {
516: super (errSymbol);
517: }
518:
519: public Scope dup() {
520: return new ErrorScope(this , owner, table);
521: }
522:
523: public Scope dupUnshared() {
524: return new ErrorScope(this , owner, table.clone());
525: }
526:
527: public Entry lookup(Name name) {
528: Entry e = super .lookup(name);
529: if (e.scope == null)
530: return new Entry(owner, null, null, null);
531: else
532: return e;
533: }
534: }
535: }
|