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