1 /* 2 * Copyright (c) 1999, 2015, 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 */ Scope(Scope next, Symbol owner, Entry[] table)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. */ Scope(Scope next, Symbol owner, Entry[] table, int nelems)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 */ Scope(Symbol owner)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 */ dup()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 */ dup(Symbol newOwner)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 */ dupUnshared()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 */ leave()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 */ dble()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 */ enter(Symbol sym)196 public void enter(Symbol sym) { 197 Assert.check(shared == 0); 198 enter(sym, this); 199 } 200 enter(Symbol sym, Scope s)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 */ enter(Symbol sym, Scope s, Scope origin, boolean staticallyImported)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 makeEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, Scope origin, boolean staticallyImported)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 { symbolAdded(Symbol sym, Scope s)236 public void symbolAdded(Symbol sym, Scope s); symbolRemoved(Symbol sym, Scope s)237 public void symbolRemoved(Symbol sym, Scope s); 238 } 239 addScopeListener(ScopeListener sl)240 public void addScopeListener(ScopeListener sl) { 241 listeners = listeners.prepend(sl); 242 } 243 244 /** Remove symbol from this scope. 245 */ remove(final Symbol sym)246 public void remove(final Symbol sym) { 247 Assert.check(shared == 0); 248 Entry e = lookup(sym.name, new Filter<Symbol>() { 249 @Override 250 public boolean accepts(Symbol candidate) { 251 return candidate == sym; 252 } 253 }); 254 if (e.scope == null) return; 255 256 // remove e from table and shadowed list; 257 int i = getIndex(sym.name); 258 Entry te = table[i]; 259 if (te == e) 260 table[i] = e.shadowed; 261 else while (true) { 262 if (te.shadowed == e) { 263 te.shadowed = e.shadowed; 264 break; 265 } 266 te = te.shadowed; 267 } 268 269 // remove e from elems and sibling list 270 te = elems; 271 if (te == e) 272 elems = e.sibling; 273 else while (true) { 274 if (te.sibling == e) { 275 te.sibling = e.sibling; 276 break; 277 } 278 te = te.sibling; 279 } 280 281 //notify listeners 282 for (List<ScopeListener> l = listeners; l.nonEmpty(); l = l.tail) { 283 l.head.symbolRemoved(sym, this); 284 } 285 } 286 287 /** Enter symbol sym in this scope if not already there. 288 */ enterIfAbsent(Symbol sym)289 public void enterIfAbsent(Symbol sym) { 290 Assert.check(shared == 0); 291 Entry e = lookup(sym.name); 292 while (e.scope == this && e.sym.kind != sym.kind) e = e.next(); 293 if (e.scope != this) enter(sym); 294 } 295 296 /** Given a class, is there already a class with same fully 297 * qualified name in this (import) scope? 298 */ includes(Symbol c)299 public boolean includes(Symbol c) { 300 for (Scope.Entry e = lookup(c.name); 301 e.scope == this; 302 e = e.next()) { 303 if (e.sym == c) return true; 304 } 305 return false; 306 } 307 308 static final Filter<Symbol> noFilter = new Filter<Symbol>() { 309 public boolean accepts(Symbol s) { 310 return true; 311 } 312 }; 313 314 /** Return the entry associated with given name, starting in 315 * this scope and proceeding outwards. If no entry was found, 316 * return the sentinel, which is characterized by having a null in 317 * both its scope and sym fields, whereas both fields are non-null 318 * for regular entries. 319 */ lookup(Name name)320 public Entry lookup(Name name) { 321 return lookup(name, noFilter); 322 } 323 lookup(Name name, Filter<Symbol> sf)324 public Entry lookup(Name name, Filter<Symbol> sf) { 325 Entry e = table[getIndex(name)]; 326 if (e == null || e == sentinel) 327 return sentinel; 328 while (e.scope != null && (e.sym.name != name || !sf.accepts(e.sym))) 329 e = e.shadowed; 330 return e; 331 } 332 333 /*void dump (java.io.PrintStream out) { 334 out.println(this); 335 for (int l=0; l < table.length; l++) { 336 Entry le = table[l]; 337 out.print("#"+l+": "); 338 if (le==sentinel) out.println("sentinel"); 339 else if(le == null) out.println("null"); 340 else out.println(""+le+" s:"+le.sym); 341 } 342 }*/ 343 344 /** Look for slot in the table. 345 * We use open addressing with double hashing. 346 */ getIndex(Name name)347 int getIndex (Name name) { 348 int h = name.hashCode(); 349 int i = h & hashMask; 350 // The expression below is always odd, so it is guaranteed 351 // to be mutually prime with table.length, a power of 2. 352 int x = hashMask - ((h + (h >> 16)) << 1); 353 int d = -1; // Index of a deleted item. 354 for (;;) { 355 Entry e = table[i]; 356 if (e == null) 357 return d >= 0 ? d : i; 358 if (e == sentinel) { 359 // We have to keep searching even if we see a deleted item. 360 // However, remember the index in case we fail to find the name. 361 if (d < 0) 362 d = i; 363 } else if (e.sym.name == name) 364 return i; 365 i = (i + x) & hashMask; 366 } 367 } 368 anyMatch(Filter<Symbol> sf)369 public boolean anyMatch(Filter<Symbol> sf) { 370 return getElements(sf).iterator().hasNext(); 371 } 372 getElements()373 public Iterable<Symbol> getElements() { 374 return getElements(noFilter); 375 } 376 getElements(final Filter<Symbol> sf)377 public Iterable<Symbol> getElements(final Filter<Symbol> sf) { 378 return new Iterable<Symbol>() { 379 public Iterator<Symbol> iterator() { 380 return new Iterator<Symbol>() { 381 private Scope currScope = Scope.this; 382 private Scope.Entry currEntry = elems; 383 { 384 update(); 385 } 386 387 public boolean hasNext() { 388 return currEntry != null; 389 } 390 391 public Symbol next() { 392 Symbol sym = (currEntry == null ? null : currEntry.sym); 393 if (currEntry != null) { 394 currEntry = currEntry.sibling; 395 } 396 update(); 397 return sym; 398 } 399 400 public void remove() { 401 throw new UnsupportedOperationException(); 402 } 403 404 private void update() { 405 skipToNextMatchingEntry(); 406 while (currEntry == null && currScope.next != null) { 407 currScope = currScope.next; 408 currEntry = currScope.elems; 409 skipToNextMatchingEntry(); 410 } 411 } 412 413 void skipToNextMatchingEntry() { 414 while (currEntry != null && !sf.accepts(currEntry.sym)) { 415 currEntry = currEntry.sibling; 416 } 417 } 418 }; 419 } 420 }; 421 } 422 423 public Iterable<Symbol> getElementsByName(Name name) { 424 return getElementsByName(name, noFilter); 425 } 426 427 public Iterable<Symbol> getElementsByName(final Name name, final Filter<Symbol> sf) { 428 return new Iterable<Symbol>() { 429 public Iterator<Symbol> iterator() { 430 return new Iterator<Symbol>() { 431 Scope.Entry currentEntry = lookup(name, sf); 432 433 public boolean hasNext() { 434 return currentEntry.scope != null; 435 } 436 public Symbol next() { 437 Scope.Entry prevEntry = currentEntry; 438 currentEntry = currentEntry.next(sf); 439 return prevEntry.sym; 440 } 441 public void remove() { 442 throw new UnsupportedOperationException(); 443 } 444 }; 445 } 446 }; 447 } 448 449 public String toString() { 450 StringBuilder result = new StringBuilder(); 451 result.append("Scope["); 452 for (Scope s = this; s != null ; s = s.next) { 453 if (s != this) result.append(" | "); 454 for (Entry e = s.elems; e != null; e = e.sibling) { 455 if (e != s.elems) result.append(", "); 456 result.append(e.sym); 457 } 458 } 459 result.append("]"); 460 return result.toString(); 461 } 462 463 /** A class for scope entries. 464 */ 465 public static class Entry { 466 467 /** The referenced symbol. 468 * sym == null iff this == sentinel 469 */ 470 public Symbol sym; 471 472 /** An entry with the same hash code, or sentinel. 473 */ 474 private Entry shadowed; 475 476 /** Next entry in same scope. 477 */ 478 public Entry sibling; 479 480 /** The entry's scope. 481 * scope == null iff this == sentinel 482 * for an entry in an import scope, this is the scope 483 * where the entry came from (i.e. was imported from). 484 */ 485 public Scope scope; 486 487 public Entry(Symbol sym, Entry shadowed, Entry sibling, Scope scope) { 488 this.sym = sym; 489 this.shadowed = shadowed; 490 this.sibling = sibling; 491 this.scope = scope; 492 } 493 494 /** Return next entry with the same name as this entry, proceeding 495 * outwards if not found in this scope. 496 */ 497 public Entry next() { 498 return shadowed; 499 } 500 501 public Entry next(Filter<Symbol> sf) { 502 if (shadowed.sym == null || sf.accepts(shadowed.sym)) return shadowed; 503 else return shadowed.next(sf); 504 } 505 506 public boolean isStaticallyImported() { 507 return false; 508 } 509 510 public Scope getOrigin() { 511 // The origin is only recorded for import scopes. For all 512 // other scope entries, the "enclosing" type is available 513 // from other sources. See Attr.visitSelect and 514 // Attr.visitIdent. Rather than throwing an assertion 515 // error, we return scope which will be the same as origin 516 // in many cases. 517 return scope; 518 } 519 } 520 521 public static class ImportScope extends Scope { 522 523 public ImportScope(Symbol owner) { 524 super(owner); 525 } 526 527 @Override 528 Entry makeEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, 529 final Scope origin, final boolean staticallyImported) { 530 return new Entry(sym, shadowed, sibling, scope) { 531 @Override 532 public Scope getOrigin() { 533 return origin; 534 } 535 536 @Override 537 public boolean isStaticallyImported() { 538 return staticallyImported; 539 } 540 }; 541 } 542 } 543 544 public static class StarImportScope extends ImportScope implements ScopeListener { 545 546 public StarImportScope(Symbol owner) { 547 super(owner); 548 } 549 550 public void importAll (Scope fromScope) { 551 for (Scope.Entry e = fromScope.elems; e != null; e = e.sibling) { 552 if (e.sym.kind == Kinds.TYP && !includes(e.sym)) 553 enter(e.sym, fromScope); 554 } 555 // Register to be notified when imported items are removed 556 fromScope.addScopeListener(this); 557 } 558 559 public void symbolRemoved(Symbol sym, Scope s) { 560 remove(sym); 561 } 562 public void symbolAdded(Symbol sym, Scope s) { } 563 } 564 565 /** An empty scope, into which you can't place anything. Used for 566 * the scope for a variable initializer. 567 */ 568 public static class DelegatedScope extends Scope { 569 Scope delegatee; 570 public static final Entry[] emptyTable = new Entry[0]; 571 572 public DelegatedScope(Scope outer) { 573 super(outer, outer.owner, emptyTable); 574 delegatee = outer; 575 } 576 public Scope dup() { 577 return new DelegatedScope(next); 578 } 579 public Scope dupUnshared() { 580 return new DelegatedScope(next); 581 } 582 public Scope leave() { 583 return next; 584 } 585 public void enter(Symbol sym) { 586 // only anonymous classes could be put here 587 } 588 public void enter(Symbol sym, Scope s) { 589 // only anonymous classes could be put here 590 } 591 public void remove(Symbol sym) { 592 throw new AssertionError(sym); 593 } 594 public Entry lookup(Name name) { 595 return delegatee.lookup(name); 596 } 597 } 598 599 /** A class scope adds capabilities to keep track of changes in related 600 * class scopes - this allows client to realize whether a class scope 601 * has changed, either directly (because a new member has been added/removed 602 * to this scope) or indirectly (i.e. because a new member has been 603 * added/removed into a supertype scope) 604 */ 605 public static class CompoundScope extends Scope implements ScopeListener { 606 607 public static final Entry[] emptyTable = new Entry[0]; 608 609 private List<Scope> subScopes = List.nil(); 610 private int mark = 0; 611 612 public CompoundScope(Symbol owner) { 613 super(null, owner, emptyTable); 614 } 615 616 public void addSubScope(Scope that) { 617 if (that != null) { 618 subScopes = subScopes.prepend(that); 619 that.addScopeListener(this); 620 mark++; 621 for (ScopeListener sl : listeners) { 622 sl.symbolAdded(null, this); //propagate upwards in case of nested CompoundScopes 623 } 624 } 625 } 626 627 public void symbolAdded(Symbol sym, Scope s) { 628 mark++; 629 for (ScopeListener sl : listeners) { 630 sl.symbolAdded(sym, s); 631 } 632 } 633 634 public void symbolRemoved(Symbol sym, Scope s) { 635 mark++; 636 for (ScopeListener sl : listeners) { 637 sl.symbolRemoved(sym, s); 638 } 639 } 640 641 public int getMark() { 642 return mark; 643 } 644 645 @Override 646 public String toString() { 647 StringBuilder buf = new StringBuilder(); 648 buf.append("CompoundScope{"); 649 String sep = ""; 650 for (Scope s : subScopes) { 651 buf.append(sep); 652 buf.append(s); 653 sep = ","; 654 } 655 buf.append("}"); 656 return buf.toString(); 657 } 658 659 @Override 660 public Iterable<Symbol> getElements(final Filter<Symbol> sf) { 661 return new Iterable<Symbol>() { 662 public Iterator<Symbol> iterator() { 663 return new CompoundScopeIterator(subScopes) { 664 Iterator<Symbol> nextIterator(Scope s) { 665 return s.getElements(sf).iterator(); 666 } 667 }; 668 } 669 }; 670 } 671 672 @Override 673 public Iterable<Symbol> getElementsByName(final Name name, final Filter<Symbol> sf) { 674 return new Iterable<Symbol>() { 675 public Iterator<Symbol> iterator() { 676 return new CompoundScopeIterator(subScopes) { 677 Iterator<Symbol> nextIterator(Scope s) { 678 return s.getElementsByName(name, sf).iterator(); 679 } 680 }; 681 } 682 }; 683 } 684 685 abstract class CompoundScopeIterator implements Iterator<Symbol> { 686 687 private Iterator<Symbol> currentIterator; 688 private List<Scope> scopesToScan; 689 690 public CompoundScopeIterator(List<Scope> scopesToScan) { 691 this.scopesToScan = scopesToScan; 692 update(); 693 } 694 695 abstract Iterator<Symbol> nextIterator(Scope s); 696 697 public boolean hasNext() { 698 return currentIterator != null; 699 } 700 701 public Symbol next() { 702 Symbol sym = currentIterator.next(); 703 if (!currentIterator.hasNext()) { 704 update(); 705 } 706 return sym; 707 } 708 709 public void remove() { 710 throw new UnsupportedOperationException(); 711 } 712 713 private void update() { 714 while (scopesToScan.nonEmpty()) { 715 currentIterator = nextIterator(scopesToScan.head); 716 scopesToScan = scopesToScan.tail; 717 if (currentIterator.hasNext()) return; 718 } 719 currentIterator = null; 720 } 721 } 722 723 @Override 724 public Entry lookup(Name name, Filter<Symbol> sf) { 725 throw new UnsupportedOperationException(); 726 } 727 728 @Override 729 public Scope dup(Symbol newOwner) { 730 throw new UnsupportedOperationException(); 731 } 732 733 @Override 734 public void enter(Symbol sym, Scope s, Scope origin, boolean staticallyImported) { 735 throw new UnsupportedOperationException(); 736 } 737 738 @Override 739 public void remove(Symbol sym) { 740 throw new UnsupportedOperationException(); 741 } 742 } 743 744 /** An error scope, for which the owner should be an error symbol. */ 745 public static class ErrorScope extends Scope { 746 ErrorScope(Scope next, Symbol errSymbol, Entry[] table) { 747 super(next, /*owner=*/errSymbol, table); 748 } 749 public ErrorScope(Symbol errSymbol) { 750 super(errSymbol); 751 } 752 public Scope dup() { 753 return new ErrorScope(this, owner, table); 754 } 755 public Scope dupUnshared() { 756 return new ErrorScope(this, owner, table.clone()); 757 } 758 public Entry lookup(Name name) { 759 Entry e = super.lookup(name); 760 if (e.scope == null) 761 return new Entry(owner, null, null, null); 762 else 763 return e; 764 } 765 } 766 } 767