View Javadoc
1   /*
2    * Copyright (c) 1999, 2013, 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   */
25  
26  package com.sun.tools.javac.code;
27  
28  import java.util.Iterator;
29  
30  import com.sun.tools.javac.util.*;
31  
32  /** A scope represents an area of visibility in a Java program. The
33   *  Scope class is a container for symbols which provides
34   *  efficient access to symbols given their names. Scopes are implemented
35   *  as hash tables with "open addressing" and "double hashing".
36   *  Scopes can be nested; the next field of a scope points
37   *  to its next outer scope. Nested scopes can share their hash tables.
38   *
39   *  <p><b>This is NOT part of any supported API.
40   *  If you write code that depends on this, you do so at your own risk.
41   *  This code and its internal interfaces are subject to change or
42   *  deletion without notice.</b>
43   */
44  public class Scope {
45  
46      /** The number of scopes that share this scope's hash table.
47       */
48      private int shared;
49  
50      /** Next enclosing scope (with whom this scope may share a hashtable)
51       */
52      public Scope next;
53  
54      /** The scope's owner.
55       */
56      public Symbol owner;
57  
58      /** A hash table for the scope's entries.
59       */
60      Entry[] table;
61  
62      /** Mask for hash codes, always equal to (table.length - 1).
63       */
64      int hashMask;
65  
66      /** A linear list that also contains all entries in
67       *  reverse order of appearance (i.e later entries are pushed on top).
68       */
69      public Entry elems;
70  
71      /** The number of elements in this scope.
72       * This includes deleted elements, whose value is the sentinel.
73       */
74      int nelems = 0;
75  
76      /** A list of scopes to be notified if items are to be removed from this scope.
77       */
78      List<ScopeListener> listeners = List.nil();
79  
80      /** Use as a "not-found" result for lookup.
81       * Also used to mark deleted entries in the table.
82       */
83      private static final Entry sentinel = new Entry(null, null, null, null);
84  
85      /** The hash table's initial size.
86       */
87      private static final int INITIAL_SIZE = 0x10;
88  
89      /** A value for the empty scope.
90       */
91      public static final Scope emptyScope = new Scope(null, null, new Entry[]{});
92  
93      /** Construct a new scope, within scope next, with given owner, using
94       *  given table. The table's length must be an exponent of 2.
95       */
96      private Scope(Scope next, Symbol owner, Entry[] table) {
97          this.next = next;
98          Assert.check(emptyScope == null || owner != null);
99          this.owner = owner;
100         this.table = table;
101         this.hashMask = table.length - 1;
102     }
103 
104     /** Convenience constructor used for dup and dupUnshared. */
105     private Scope(Scope next, Symbol owner, Entry[] table, int nelems) {
106         this(next, owner, table);
107         this.nelems = nelems;
108     }
109 
110     /** Construct a new scope, within scope next, with given owner,
111      *  using a fresh table of length INITIAL_SIZE.
112      */
113     public Scope(Symbol owner) {
114         this(null, owner, new Entry[INITIAL_SIZE]);
115     }
116 
117     /** Construct a fresh scope within this scope, with same owner,
118      *  which shares its table with the outer scope. Used in connection with
119      *  method leave if scope access is stack-like in order to avoid allocation
120      *  of fresh tables.
121      */
122     public Scope dup() {
123         return dup(this.owner);
124     }
125 
126     /** Construct a fresh scope within this scope, with new 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(Symbol newOwner) {
132         Scope result = new Scope(this, newOwner, this.table, this.nelems);
133         shared++;
134         // System.out.println("====> duping scope " + this.hashCode() + " owned by " + newOwner + " to " + result.hashCode());
135         // new Error().printStackTrace(System.out);
136         return result;
137     }
138 
139     /** Construct a fresh scope within this scope, with same owner,
140      *  with a new hash table, whose contents initially are those of
141      *  the table of its outer scope.
142      */
143     public Scope dupUnshared() {
144         return new Scope(this, this.owner, this.table.clone(), this.nelems);
145     }
146 
147     /** Remove all entries of this scope from its table, if shared
148      *  with next.
149      */
150     public Scope leave() {
151         Assert.check(shared == 0);
152         if (table != next.table) return next;
153         while (elems != null) {
154             int hash = getIndex(elems.sym.name);
155             Entry e = table[hash];
156             Assert.check(e == elems, elems.sym);
157             table[hash] = elems.shadowed;
158             elems = elems.sibling;
159         }
160         Assert.check(next.shared > 0);
161         next.shared--;
162         next.nelems = nelems;
163         // System.out.println("====> leaving scope " + this.hashCode() + " owned by " + this.owner + " to " + next.hashCode());
164         // new Error().printStackTrace(System.out);
165         return next;
166     }
167 
168     /** Double size of hash table.
169      */
170     private void dble() {
171         Assert.check(shared == 0);
172         Entry[] oldtable = table;
173         Entry[] newtable = new Entry[oldtable.length * 2];
174         for (Scope s = this; s != null; s = s.next) {
175             if (s.table == oldtable) {
176                 Assert.check(s == this || s.shared != 0);
177                 s.table = newtable;
178                 s.hashMask = newtable.length - 1;
179             }
180         }
181         int n = 0;
182         for (int i = oldtable.length; --i >= 0; ) {
183             Entry e = oldtable[i];
184             if (e != null && e != sentinel) {
185                 table[getIndex(e.sym.name)] = e;
186                 n++;
187             }
188         }
189         // We don't need to update nelems for shared inherited scopes,
190         // since that gets handled by leave().
191         nelems = n;
192     }
193 
194     /** Enter symbol sym in this scope.
195      */
196     public void enter(Symbol sym) {
197         Assert.check(shared == 0);
198         enter(sym, this);
199     }
200 
201     public void enter(Symbol sym, Scope s) {
202         enter(sym, s, s, false);
203     }
204 
205     /**
206      * Enter symbol sym in this scope, but mark that it comes from
207      * given scope `s' accessed through `origin'.  The last two
208      * arguments are only used in import scopes.
209      */
210     public void enter(Symbol sym, Scope s, Scope origin, boolean staticallyImported) {
211         Assert.check(shared == 0);
212         if (nelems * 3 >= hashMask * 2)
213             dble();
214         int hash = getIndex(sym.name);
215         Entry old = table[hash];
216         if (old == null) {
217             old = sentinel;
218             nelems++;
219         }
220         Entry e = makeEntry(sym, old, elems, s, origin, staticallyImported);
221         table[hash] = e;
222         elems = e;
223 
224         //notify listeners
225         for (List<ScopeListener> l = listeners; l.nonEmpty(); l = l.tail) {
226             l.head.symbolAdded(sym, this);
227         }
228     }
229 
230     Entry makeEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, Scope origin, boolean staticallyImported) {
231         return new Entry(sym, shadowed, sibling, scope);
232     }
233 
234 
235     public interface ScopeListener {
236         public void symbolAdded(Symbol sym, Scope s);
237         public void symbolRemoved(Symbol sym, Scope s);
238     }
239 
240     public void addScopeListener(ScopeListener sl) {
241         listeners = listeners.prepend(sl);
242     }
243 
244     /** Remove symbol from this scope.  Used when an inner class
245      *  attribute tells us that the class isn't a package member.
246      */
247     public void remove(Symbol sym) {
248         Assert.check(shared == 0);
249         Entry e = lookup(sym.name);
250         if (e.scope == null) return;
251 
252         // remove e from table and shadowed list;
253         int i = getIndex(sym.name);
254         Entry te = table[i];
255         if (te == e)
256             table[i] = e.shadowed;
257         else while (true) {
258             if (te.shadowed == e) {
259                 te.shadowed = e.shadowed;
260                 break;
261             }
262             te = te.shadowed;
263         }
264 
265         // remove e from elems and sibling list
266         te = elems;
267         if (te == e)
268             elems = e.sibling;
269         else while (true) {
270             if (te.sibling == e) {
271                 te.sibling = e.sibling;
272                 break;
273             }
274             te = te.sibling;
275         }
276 
277         //notify listeners
278         for (List<ScopeListener> l = listeners; l.nonEmpty(); l = l.tail) {
279             l.head.symbolRemoved(sym, this);
280         }
281     }
282 
283     /** Enter symbol sym in this scope if not already there.
284      */
285     public void enterIfAbsent(Symbol sym) {
286         Assert.check(shared == 0);
287         Entry e = lookup(sym.name);
288         while (e.scope == this && e.sym.kind != sym.kind) e = e.next();
289         if (e.scope != this) enter(sym);
290     }
291 
292     /** Given a class, is there already a class with same fully
293      *  qualified name in this (import) scope?
294      */
295     public boolean includes(Symbol c) {
296         for (Scope.Entry e = lookup(c.name);
297              e.scope == this;
298              e = e.next()) {
299             if (e.sym == c) return true;
300         }
301         return false;
302     }
303 
304     static final Filter<Symbol> noFilter = new Filter<Symbol>() {
305         public boolean accepts(Symbol s) {
306             return true;
307         }
308     };
309 
310     /** Return the entry associated with given name, starting in
311      *  this scope and proceeding outwards. If no entry was found,
312      *  return the sentinel, which is characterized by having a null in
313      *  both its scope and sym fields, whereas both fields are non-null
314      *  for regular entries.
315      */
316     public Entry lookup(Name name) {
317         return lookup(name, noFilter);
318     }
319 
320     public Entry lookup(Name name, Filter<Symbol> sf) {
321         Entry e = table[getIndex(name)];
322         if (e == null || e == sentinel)
323             return sentinel;
324         while (e.scope != null && (e.sym.name != name || !sf.accepts(e.sym)))
325             e = e.shadowed;
326         return e;
327     }
328 
329     /*void dump (java.io.PrintStream out) {
330         out.println(this);
331         for (int l=0; l < table.length; l++) {
332             Entry le = table[l];
333             out.print("#"+l+": ");
334             if (le==sentinel) out.println("sentinel");
335             else if(le == null) out.println("null");
336             else out.println(""+le+" s:"+le.sym);
337         }
338     }*/
339 
340     /** Look for slot in the table.
341      *  We use open addressing with double hashing.
342      */
343     int getIndex (Name name) {
344         int h = name.hashCode();
345         int i = h & hashMask;
346         // The expression below is always odd, so it is guaranteed
347         // to be mutually prime with table.length, a power of 2.
348         int x = hashMask - ((h + (h >> 16)) << 1);
349         int d = -1; // Index of a deleted item.
350         for (;;) {
351             Entry e = table[i];
352             if (e == null)
353                 return d >= 0 ? d : i;
354             if (e == sentinel) {
355                 // We have to keep searching even if we see a deleted item.
356                 // However, remember the index in case we fail to find the name.
357                 if (d < 0)
358                     d = i;
359             } else if (e.sym.name == name)
360                 return i;
361             i = (i + x) & hashMask;
362         }
363     }
364 
365     public boolean anyMatch(Filter<Symbol> sf) {
366         return getElements(sf).iterator().hasNext();
367     }
368 
369     public Iterable<Symbol> getElements() {
370         return getElements(noFilter);
371     }
372 
373     public Iterable<Symbol> getElements(final Filter<Symbol> sf) {
374         return new Iterable<Symbol>() {
375             public Iterator<Symbol> iterator() {
376                 return new Iterator<Symbol>() {
377                     private Scope currScope = Scope.this;
378                     private Scope.Entry currEntry = elems;
379                     {
380                         update();
381                     }
382 
383                     public boolean hasNext() {
384                         return currEntry != null;
385                     }
386 
387                     public Symbol next() {
388                         Symbol sym = (currEntry == null ? null : currEntry.sym);
389                         if (currEntry != null) {
390                             currEntry = currEntry.sibling;
391                         }
392                         update();
393                         return sym;
394                     }
395 
396                     public void remove() {
397                         throw new UnsupportedOperationException();
398                     }
399 
400                     private void update() {
401                         skipToNextMatchingEntry();
402                         while (currEntry == null && currScope.next != null) {
403                             currScope = currScope.next;
404                             currEntry = currScope.elems;
405                             skipToNextMatchingEntry();
406                         }
407                     }
408 
409                     void skipToNextMatchingEntry() {
410                         while (currEntry != null && !sf.accepts(currEntry.sym)) {
411                             currEntry = currEntry.sibling;
412                         }
413                     }
414                 };
415             }
416         };
417     }
418 
419     public Iterable<Symbol> getElementsByName(Name name) {
420         return getElementsByName(name, noFilter);
421     }
422 
423     public Iterable<Symbol> getElementsByName(final Name name, final Filter<Symbol> sf) {
424         return new Iterable<Symbol>() {
425             public Iterator<Symbol> iterator() {
426                  return new Iterator<Symbol>() {
427                     Scope.Entry currentEntry = lookup(name, sf);
428 
429                     public boolean hasNext() {
430                         return currentEntry.scope != null;
431                     }
432                     public Symbol next() {
433                         Scope.Entry prevEntry = currentEntry;
434                         currentEntry = currentEntry.next(sf);
435                         return prevEntry.sym;
436                     }
437                     public void remove() {
438                         throw new UnsupportedOperationException();
439                     }
440                 };
441             }
442         };
443     }
444 
445     public String toString() {
446         StringBuilder result = new StringBuilder();
447         result.append("Scope[");
448         for (Scope s = this; s != null ; s = s.next) {
449             if (s != this) result.append(" | ");
450             for (Entry e = s.elems; e != null; e = e.sibling) {
451                 if (e != s.elems) result.append(", ");
452                 result.append(e.sym);
453             }
454         }
455         result.append("]");
456         return result.toString();
457     }
458 
459     /** A class for scope entries.
460      */
461     public static class Entry {
462 
463         /** The referenced symbol.
464          *  sym == null   iff   this == sentinel
465          */
466         public Symbol sym;
467 
468         /** An entry with the same hash code, or sentinel.
469          */
470         private Entry shadowed;
471 
472         /** Next entry in same scope.
473          */
474         public Entry sibling;
475 
476         /** The entry's scope.
477          *  scope == null   iff   this == sentinel
478          *  for an entry in an import scope, this is the scope
479          *  where the entry came from (i.e. was imported from).
480          */
481         public Scope scope;
482 
483         public Entry(Symbol sym, Entry shadowed, Entry sibling, Scope scope) {
484             this.sym = sym;
485             this.shadowed = shadowed;
486             this.sibling = sibling;
487             this.scope = scope;
488         }
489 
490         /** Return next entry with the same name as this entry, proceeding
491          *  outwards if not found in this scope.
492          */
493         public Entry next() {
494             return shadowed;
495         }
496 
497         public Entry next(Filter<Symbol> sf) {
498             if (shadowed.sym == null || sf.accepts(shadowed.sym)) return shadowed;
499             else return shadowed.next(sf);
500         }
501 
502         public boolean isStaticallyImported() {
503             return false;
504         }
505 
506         public Scope getOrigin() {
507             // The origin is only recorded for import scopes.  For all
508             // other scope entries, the "enclosing" type is available
509             // from other sources.  See Attr.visitSelect and
510             // Attr.visitIdent.  Rather than throwing an assertion
511             // error, we return scope which will be the same as origin
512             // in many cases.
513             return scope;
514         }
515     }
516 
517     public static class ImportScope extends Scope {
518 
519         public ImportScope(Symbol owner) {
520             super(owner);
521         }
522 
523         @Override
524         Entry makeEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope,
525                 final Scope origin, final boolean staticallyImported) {
526             return new Entry(sym, shadowed, sibling, scope) {
527                 @Override
528                 public Scope getOrigin() {
529                     return origin;
530                 }
531 
532                 @Override
533                 public boolean isStaticallyImported() {
534                     return staticallyImported;
535                 }
536             };
537         }
538     }
539 
540     public static class StarImportScope extends ImportScope implements ScopeListener {
541 
542         public StarImportScope(Symbol owner) {
543             super(owner);
544         }
545 
546         public void importAll (Scope fromScope) {
547             for (Scope.Entry e = fromScope.elems; e != null; e = e.sibling) {
548                 if (e.sym.kind == Kinds.TYP && !includes(e.sym))
549                     enter(e.sym, fromScope);
550             }
551             // Register to be notified when imported items are removed
552             fromScope.addScopeListener(this);
553         }
554 
555         public void symbolRemoved(Symbol sym, Scope s) {
556             remove(sym);
557         }
558         public void symbolAdded(Symbol sym, Scope s) { }
559     }
560 
561     /** An empty scope, into which you can't place anything.  Used for
562      *  the scope for a variable initializer.
563      */
564     public static class DelegatedScope extends Scope {
565         Scope delegatee;
566         public static final Entry[] emptyTable = new Entry[0];
567 
568         public DelegatedScope(Scope outer) {
569             super(outer, outer.owner, emptyTable);
570             delegatee = outer;
571         }
572         public Scope dup() {
573             return new DelegatedScope(next);
574         }
575         public Scope dupUnshared() {
576             return new DelegatedScope(next);
577         }
578         public Scope leave() {
579             return next;
580         }
581         public void enter(Symbol sym) {
582             // only anonymous classes could be put here
583         }
584         public void enter(Symbol sym, Scope s) {
585             // only anonymous classes could be put here
586         }
587         public void remove(Symbol sym) {
588             throw new AssertionError(sym);
589         }
590         public Entry lookup(Name name) {
591             return delegatee.lookup(name);
592         }
593     }
594 
595     /** A class scope adds capabilities to keep track of changes in related
596      *  class scopes - this allows client to realize whether a class scope
597      *  has changed, either directly (because a new member has been added/removed
598      *  to this scope) or indirectly (i.e. because a new member has been
599      *  added/removed into a supertype scope)
600      */
601     public static class CompoundScope extends Scope implements ScopeListener {
602 
603         public static final Entry[] emptyTable = new Entry[0];
604 
605         private List<Scope> subScopes = List.nil();
606         private int mark = 0;
607 
608         public CompoundScope(Symbol owner) {
609             super(null, owner, emptyTable);
610         }
611 
612         public void addSubScope(Scope that) {
613            if (that != null) {
614                 subScopes = subScopes.prepend(that);
615                 that.addScopeListener(this);
616                 mark++;
617                 for (ScopeListener sl : listeners) {
618                     sl.symbolAdded(null, this); //propagate upwards in case of nested CompoundScopes
619                 }
620            }
621          }
622 
623         public void symbolAdded(Symbol sym, Scope s) {
624             mark++;
625             for (ScopeListener sl : listeners) {
626                 sl.symbolAdded(sym, s);
627             }
628         }
629 
630         public void symbolRemoved(Symbol sym, Scope s) {
631             mark++;
632             for (ScopeListener sl : listeners) {
633                 sl.symbolRemoved(sym, s);
634             }
635         }
636 
637         public int getMark() {
638             return mark;
639         }
640 
641         @Override
642         public String toString() {
643             StringBuilder buf = new StringBuilder();
644             buf.append("CompoundScope{");
645             String sep = "";
646             for (Scope s : subScopes) {
647                 buf.append(sep);
648                 buf.append(s);
649                 sep = ",";
650             }
651             buf.append("}");
652             return buf.toString();
653         }
654 
655         @Override
656         public Iterable<Symbol> getElements(final Filter<Symbol> sf) {
657             return new Iterable<Symbol>() {
658                 public Iterator<Symbol> iterator() {
659                     return new CompoundScopeIterator(subScopes) {
660                         Iterator<Symbol> nextIterator(Scope s) {
661                             return s.getElements(sf).iterator();
662                         }
663                     };
664                 }
665             };
666         }
667 
668         @Override
669         public Iterable<Symbol> getElementsByName(final Name name, final Filter<Symbol> sf) {
670             return new Iterable<Symbol>() {
671                 public Iterator<Symbol> iterator() {
672                     return new CompoundScopeIterator(subScopes) {
673                         Iterator<Symbol> nextIterator(Scope s) {
674                             return s.getElementsByName(name, sf).iterator();
675                         }
676                     };
677                 }
678             };
679         }
680 
681         abstract class CompoundScopeIterator implements Iterator<Symbol> {
682 
683             private Iterator<Symbol> currentIterator;
684             private List<Scope> scopesToScan;
685 
686             public CompoundScopeIterator(List<Scope> scopesToScan) {
687                 this.scopesToScan = scopesToScan;
688                 update();
689             }
690 
691             abstract Iterator<Symbol> nextIterator(Scope s);
692 
693             public boolean hasNext() {
694                 return currentIterator != null;
695             }
696 
697             public Symbol next() {
698                 Symbol sym = currentIterator.next();
699                 if (!currentIterator.hasNext()) {
700                     update();
701                 }
702                 return sym;
703             }
704 
705             public void remove() {
706                 throw new UnsupportedOperationException();
707             }
708 
709             private void update() {
710                 while (scopesToScan.nonEmpty()) {
711                     currentIterator = nextIterator(scopesToScan.head);
712                     scopesToScan = scopesToScan.tail;
713                     if (currentIterator.hasNext()) return;
714                 }
715                 currentIterator = null;
716             }
717         }
718 
719         @Override
720         public Entry lookup(Name name, Filter<Symbol> sf) {
721             throw new UnsupportedOperationException();
722         }
723 
724         @Override
725         public Scope dup(Symbol newOwner) {
726             throw new UnsupportedOperationException();
727         }
728 
729         @Override
730         public void enter(Symbol sym, Scope s, Scope origin, boolean staticallyImported) {
731             throw new UnsupportedOperationException();
732         }
733 
734         @Override
735         public void remove(Symbol sym) {
736             throw new UnsupportedOperationException();
737         }
738     }
739 
740     /** An error scope, for which the owner should be an error symbol. */
741     public static class ErrorScope extends Scope {
742         ErrorScope(Scope next, Symbol errSymbol, Entry[] table) {
743             super(next, /*owner=*/errSymbol, table);
744         }
745         public ErrorScope(Symbol errSymbol) {
746             super(errSymbol);
747         }
748         public Scope dup() {
749             return new ErrorScope(this, owner, table);
750         }
751         public Scope dupUnshared() {
752             return new ErrorScope(this, owner, table.clone());
753         }
754         public Entry lookup(Name name) {
755             Entry e = super.lookup(name);
756             if (e.scope == null)
757                 return new Entry(owner, null, null, null);
758             else
759                 return e;
760         }
761     }
762 }