1 /* 2 * Copyright (c) 1999, 2018, 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 com.sun.tools.javac.code.Kinds.Kind; 29 import java.lang.ref.WeakReference; 30 import java.util.*; 31 import java.util.function.BiConsumer; 32 33 import com.sun.tools.javac.code.Symbol.CompletionFailure; 34 import com.sun.tools.javac.code.Symbol.TypeSymbol; 35 import com.sun.tools.javac.tree.JCTree.JCImport; 36 import com.sun.tools.javac.util.*; 37 import com.sun.tools.javac.util.List; 38 39 import static com.sun.tools.javac.code.Scope.LookupKind.NON_RECURSIVE; 40 import static com.sun.tools.javac.code.Scope.LookupKind.RECURSIVE; 41 import static com.sun.tools.javac.util.Iterators.createCompoundIterator; 42 import static com.sun.tools.javac.util.Iterators.createFilterIterator; 43 44 /** A scope represents an area of visibility in a Java program. The 45 * Scope class is a container for symbols which provides 46 * efficient access to symbols given their names. Scopes are implemented 47 * as hash tables with "open addressing" and "double hashing". 48 * Scopes can be nested. Nested scopes can share their hash tables. 49 * 50 * <p><b>This is NOT part of any supported API. 51 * If you write code that depends on this, you do so at your own risk. 52 * This code and its internal interfaces are subject to change or 53 * deletion without notice.</b> 54 */ 55 public abstract class Scope { 56 57 /** The scope's owner. 58 */ 59 public final Symbol owner; 60 Scope(Symbol owner)61 protected Scope(Symbol owner) { 62 this.owner = owner; 63 } 64 65 /**Returns all Symbols in this Scope. Symbols from outward Scopes are included. 66 */ getSymbols()67 public final Iterable<Symbol> getSymbols() { 68 return getSymbols(noFilter); 69 } 70 71 /**Returns Symbols that match the given filter. Symbols from outward Scopes are included. 72 */ getSymbols(Filter<Symbol> sf)73 public final Iterable<Symbol> getSymbols(Filter<Symbol> sf) { 74 return getSymbols(sf, RECURSIVE); 75 } 76 77 /**Returns all Symbols in this Scope. Symbols from outward Scopes are included 78 * iff lookupKind == RECURSIVE. 79 */ getSymbols(LookupKind lookupKind)80 public final Iterable<Symbol> getSymbols(LookupKind lookupKind) { 81 return getSymbols(noFilter, lookupKind); 82 } 83 84 /**Returns Symbols that match the given filter. Symbols from outward Scopes are included 85 * iff lookupKind == RECURSIVE. 86 */ getSymbols(Filter<Symbol> sf, LookupKind lookupKind)87 public abstract Iterable<Symbol> getSymbols(Filter<Symbol> sf, LookupKind lookupKind); 88 89 /**Returns Symbols with the given name. Symbols from outward Scopes are included. 90 */ getSymbolsByName(Name name)91 public final Iterable<Symbol> getSymbolsByName(Name name) { 92 return getSymbolsByName(name, RECURSIVE); 93 } 94 95 /**Returns Symbols with the given name that match the given filter. 96 * Symbols from outward Scopes are included. 97 */ getSymbolsByName(final Name name, final Filter<Symbol> sf)98 public final Iterable<Symbol> getSymbolsByName(final Name name, final Filter<Symbol> sf) { 99 return getSymbolsByName(name, sf, RECURSIVE); 100 } 101 102 /**Returns Symbols with the given name. Symbols from outward Scopes are included 103 * iff lookupKind == RECURSIVE. 104 */ getSymbolsByName(Name name, LookupKind lookupKind)105 public final Iterable<Symbol> getSymbolsByName(Name name, LookupKind lookupKind) { 106 return getSymbolsByName(name, noFilter, lookupKind); 107 } 108 109 /**Returns Symbols with the given name that match the given filter. 110 * Symbols from outward Scopes are included iff lookupKind == RECURSIVE. 111 */ getSymbolsByName(final Name name, final Filter<Symbol> sf, final LookupKind lookupKind)112 public abstract Iterable<Symbol> getSymbolsByName(final Name name, final Filter<Symbol> sf, 113 final LookupKind lookupKind); 114 115 /** Return the first Symbol from this or outward scopes with the given name. 116 * Returns null if none. 117 */ findFirst(Name name)118 public final Symbol findFirst(Name name) { 119 return findFirst(name, noFilter); 120 } 121 122 /** Return the first Symbol from this or outward scopes with the given name that matches the 123 * given filter. Returns null if none. 124 */ findFirst(Name name, Filter<Symbol> sf)125 public Symbol findFirst(Name name, Filter<Symbol> sf) { 126 Iterator<Symbol> it = getSymbolsByName(name, sf).iterator(); 127 return it.hasNext() ? it.next() : null; 128 } 129 130 /** Returns true iff there are is at least one Symbol in this scope matching the given filter. 131 * Does not inspect outward scopes. 132 */ anyMatch(Filter<Symbol> filter)133 public boolean anyMatch(Filter<Symbol> filter) { 134 return getSymbols(filter, NON_RECURSIVE).iterator().hasNext(); 135 } 136 137 /** Returns true iff the given Symbol is in this scope or any outward scope. 138 */ includes(final Symbol sym)139 public boolean includes(final Symbol sym) { 140 return includes(sym, RECURSIVE); 141 } 142 143 /** Returns true iff the given Symbol is in this scope, optionally checking outward scopes. 144 */ includes(final Symbol sym, LookupKind lookupKind)145 public boolean includes(final Symbol sym, LookupKind lookupKind) { 146 return getSymbolsByName(sym.name, t -> t == sym, lookupKind).iterator().hasNext(); 147 } 148 149 /** Returns true iff this scope does not contain any Symbol. Does not inspect outward scopes. 150 */ isEmpty()151 public boolean isEmpty() { 152 return !getSymbols(NON_RECURSIVE).iterator().hasNext(); 153 } 154 155 /** Returns the Scope from which the givins Symbol originates in this scope. 156 */ getOrigin(Symbol byName)157 public abstract Scope getOrigin(Symbol byName); 158 159 /** Returns true iff the given Symbol is part of this scope due to a static import. 160 */ isStaticallyImported(Symbol byName)161 public abstract boolean isStaticallyImported(Symbol byName); 162 163 private static final Filter<Symbol> noFilter = null; 164 165 /** A list of scopes to be notified if items are to be removed from this scope. 166 */ 167 ScopeListenerList listeners = new ScopeListenerList(); 168 169 public interface ScopeListener { symbolAdded(Symbol sym, Scope s)170 void symbolAdded(Symbol sym, Scope s); symbolRemoved(Symbol sym, Scope s)171 void symbolRemoved(Symbol sym, Scope s); 172 } 173 174 /** 175 * A list of scope listeners; listeners are stored in weak references, to avoid memory leaks. 176 * When the listener list is scanned (upon notification), elements corresponding to GC-ed 177 * listeners are removed so that the listener list size is kept in check. 178 */ 179 public static class ScopeListenerList { 180 181 List<WeakReference<ScopeListener>> listeners = List.nil(); 182 add(ScopeListener sl)183 void add(ScopeListener sl) { 184 listeners = listeners.prepend(new WeakReference<>(sl)); 185 } 186 symbolAdded(Symbol sym, Scope scope)187 void symbolAdded(Symbol sym, Scope scope) { 188 walkReferences(sym, scope, false); 189 } 190 symbolRemoved(Symbol sym, Scope scope)191 void symbolRemoved(Symbol sym, Scope scope) { 192 walkReferences(sym, scope, true); 193 } 194 walkReferences(Symbol sym, Scope scope, boolean isRemove)195 private void walkReferences(Symbol sym, Scope scope, boolean isRemove) { 196 ListBuffer<WeakReference<ScopeListener>> newListeners = new ListBuffer<>(); 197 for (WeakReference<ScopeListener> wsl : listeners) { 198 ScopeListener sl = wsl.get(); 199 if (sl != null) { 200 if (isRemove) { 201 sl.symbolRemoved(sym, scope); 202 } else { 203 sl.symbolAdded(sym, scope); 204 } 205 newListeners.add(wsl); 206 } 207 } 208 listeners = newListeners.toList(); 209 } 210 } 211 212 public enum LookupKind { 213 RECURSIVE, 214 NON_RECURSIVE; 215 } 216 217 /**A scope into which Symbols can be added.*/ 218 public abstract static class WriteableScope extends Scope { 219 WriteableScope(Symbol owner)220 public WriteableScope(Symbol owner) { 221 super(owner); 222 } 223 224 /** Enter the given Symbol into this scope. 225 */ enter(Symbol c)226 public abstract void enter(Symbol c); 227 /** Enter symbol sym in this scope if not already there. 228 */ enterIfAbsent(Symbol c)229 public abstract void enterIfAbsent(Symbol c); 230 remove(Symbol c)231 public abstract void remove(Symbol c); 232 233 /** Construct a fresh scope within this scope, with same owner. The new scope may 234 * shares internal structures with the this scope. Used in connection with 235 * method leave if scope access is stack-like in order to avoid allocation 236 * of fresh tables. 237 */ dup()238 public final WriteableScope dup() { 239 return dup(this.owner); 240 } 241 242 /** Construct a fresh scope within this scope, with new owner. The new scope may 243 * shares internal structures with the this scope. Used in connection with 244 * method leave if scope access is stack-like in order to avoid allocation 245 * of fresh tables. 246 */ dup(Symbol newOwner)247 public abstract WriteableScope dup(Symbol newOwner); 248 249 /** Must be called on dup-ed scopes to be able to work with the outward scope again. 250 */ leave()251 public abstract WriteableScope leave(); 252 253 /** Construct a fresh scope within this scope, with same owner. The new scope 254 * will not share internal structures with this scope. 255 */ dupUnshared()256 public final WriteableScope dupUnshared() { 257 return dupUnshared(owner); 258 } 259 260 /** Construct a fresh scope within this scope, with new owner. The new scope 261 * will not share internal structures with this scope. 262 */ dupUnshared(Symbol newOwner)263 public abstract WriteableScope dupUnshared(Symbol newOwner); 264 265 /** Create a new WriteableScope. 266 */ create(Symbol owner)267 public static WriteableScope create(Symbol owner) { 268 return new ScopeImpl(owner); 269 } 270 271 } 272 273 private static class ScopeImpl extends WriteableScope { 274 /** The number of scopes that share this scope's hash table. 275 */ 276 private int shared; 277 278 /** Next enclosing scope (with whom this scope may share a hashtable) 279 */ 280 public ScopeImpl next; 281 282 /** A hash table for the scope's entries. 283 */ 284 Entry[] table; 285 286 /** Mask for hash codes, always equal to (table.length - 1). 287 */ 288 int hashMask; 289 290 /** A linear list that also contains all entries in 291 * reverse order of appearance (i.e later entries are pushed on top). 292 */ 293 public Entry elems; 294 295 /** The number of elements in this scope. 296 * This includes deleted elements, whose value is the sentinel. 297 */ 298 int nelems = 0; 299 300 int removeCount = 0; 301 302 /** Use as a "not-found" result for lookup. 303 * Also used to mark deleted entries in the table. 304 */ 305 private static final Entry sentinel = new Entry(null, null, null, null); 306 307 /** The hash table's initial size. 308 */ 309 private static final int INITIAL_SIZE = 0x10; 310 311 /** Construct a new scope, within scope next, with given owner, using 312 * given table. The table's length must be an exponent of 2. 313 */ ScopeImpl(ScopeImpl next, Symbol owner, Entry[] table)314 private ScopeImpl(ScopeImpl next, Symbol owner, Entry[] table) { 315 super(owner); 316 this.next = next; 317 Assert.check(owner != null); 318 this.table = table; 319 this.hashMask = table.length - 1; 320 } 321 322 /** Convenience constructor used for dup and dupUnshared. */ ScopeImpl(ScopeImpl next, Symbol owner, Entry[] table, int nelems)323 private ScopeImpl(ScopeImpl next, Symbol owner, Entry[] table, int nelems) { 324 this(next, owner, table); 325 this.nelems = nelems; 326 } 327 328 /** Construct a new scope, within scope next, with given owner, 329 * using a fresh table of length INITIAL_SIZE. 330 */ ScopeImpl(Symbol owner)331 public ScopeImpl(Symbol owner) { 332 this(null, owner, new Entry[INITIAL_SIZE]); 333 } 334 335 /** Construct a fresh scope within this scope, with new owner, 336 * which shares its table with the outer scope. Used in connection with 337 * method leave if scope access is stack-like in order to avoid allocation 338 * of fresh tables. 339 */ dup(Symbol newOwner)340 public WriteableScope dup(Symbol newOwner) { 341 ScopeImpl result = new ScopeImpl(this, newOwner, this.table, this.nelems); 342 shared++; 343 // System.out.println("====> duping scope " + this.hashCode() + " owned by " + newOwner + " to " + result.hashCode()); 344 // new Error().printStackTrace(System.out); 345 return result; 346 } 347 348 /** Construct a fresh scope within this scope, with new owner, 349 * with a new hash table, whose contents initially are those of 350 * the table of its outer scope. 351 */ dupUnshared(Symbol newOwner)352 public WriteableScope dupUnshared(Symbol newOwner) { 353 if (shared > 0) { 354 //The nested Scopes might have already added something to the table, so all items 355 //that don't originate in this Scope or any of its outer Scopes need to be cleared: 356 Set<Scope> acceptScopes = Collections.newSetFromMap(new IdentityHashMap<>()); 357 ScopeImpl c = this; 358 while (c != null) { 359 acceptScopes.add(c); 360 c = c.next; 361 } 362 int n = 0; 363 Entry[] oldTable = this.table; 364 Entry[] newTable = new Entry[this.table.length]; 365 for (int i = 0; i < oldTable.length; i++) { 366 Entry e = oldTable[i]; 367 while (e != null && e != sentinel && !acceptScopes.contains(e.scope)) { 368 e = e.shadowed; 369 } 370 if (e != null) { 371 n++; 372 newTable[i] = e; 373 } 374 } 375 return new ScopeImpl(this, newOwner, newTable, n); 376 } else { 377 return new ScopeImpl(this, newOwner, this.table.clone(), this.nelems); 378 } 379 } 380 381 /** Remove all entries of this scope from its table, if shared 382 * with next. 383 */ leave()384 public WriteableScope leave() { 385 Assert.check(shared == 0); 386 if (table != next.table) return next; 387 while (elems != null) { 388 int hash = getIndex(elems.sym.name); 389 Entry e = table[hash]; 390 Assert.check(e == elems, elems.sym); 391 table[hash] = elems.shadowed; 392 elems = elems.sibling; 393 } 394 Assert.check(next.shared > 0); 395 next.shared--; 396 next.nelems = nelems; 397 // System.out.println("====> leaving scope " + this.hashCode() + " owned by " + this.owner + " to " + next.hashCode()); 398 // new Error().printStackTrace(System.out); 399 return next; 400 } 401 402 /** Double size of hash table. 403 */ dble()404 private void dble() { 405 Assert.check(shared == 0); 406 Entry[] oldtable = table; 407 Entry[] newtable = new Entry[oldtable.length * 2]; 408 for (ScopeImpl s = this; s != null; s = s.next) { 409 if (s.table == oldtable) { 410 Assert.check(s == this || s.shared != 0); 411 s.table = newtable; 412 s.hashMask = newtable.length - 1; 413 } 414 } 415 int n = 0; 416 for (int i = oldtable.length; --i >= 0; ) { 417 Entry e = oldtable[i]; 418 if (e != null && e != sentinel) { 419 table[getIndex(e.sym.name)] = e; 420 n++; 421 } 422 } 423 // We don't need to update nelems for shared inherited scopes, 424 // since that gets handled by leave(). 425 nelems = n; 426 } 427 428 /** Enter symbol sym in this scope. 429 */ enter(Symbol sym)430 public void enter(Symbol sym) { 431 Assert.check(shared == 0); 432 if (nelems * 3 >= hashMask * 2) 433 dble(); 434 int hash = getIndex(sym.name); 435 Entry old = table[hash]; 436 if (old == null) { 437 old = sentinel; 438 nelems++; 439 } 440 Entry e = new Entry(sym, old, elems, this); 441 table[hash] = e; 442 elems = e; 443 444 //notify listeners 445 listeners.symbolAdded(sym, this); 446 } 447 448 /** Remove symbol from this scope. 449 */ remove(Symbol sym)450 public void remove(Symbol sym) { 451 Assert.check(shared == 0); 452 Entry e = lookup(sym.name, candidate -> candidate == sym); 453 if (e.scope == null) return; 454 455 // remove e from table and shadowed list; 456 int i = getIndex(sym.name); 457 Entry te = table[i]; 458 if (te == e) 459 table[i] = e.shadowed; 460 else while (true) { 461 if (te.shadowed == e) { 462 te.shadowed = e.shadowed; 463 break; 464 } 465 te = te.shadowed; 466 } 467 468 // remove e from elems and sibling list 469 te = elems; 470 if (te == e) 471 elems = e.sibling; 472 else while (true) { 473 if (te.sibling == e) { 474 te.sibling = e.sibling; 475 break; 476 } 477 te = te.sibling; 478 } 479 480 removeCount++; 481 482 //notify listeners 483 listeners.symbolRemoved(sym, this); 484 } 485 486 /** Enter symbol sym in this scope if not already there. 487 */ enterIfAbsent(Symbol sym)488 public void enterIfAbsent(Symbol sym) { 489 Assert.check(shared == 0); 490 Entry e = lookup(sym.name); 491 while (e.scope == this && e.sym.kind != sym.kind) e = e.next(); 492 if (e.scope != this) enter(sym); 493 } 494 495 /** Given a class, is there already a class with same fully 496 * qualified name in this (import) scope? 497 */ includes(Symbol c)498 public boolean includes(Symbol c) { 499 for (Scope.Entry e = lookup(c.name); 500 e.scope == this; 501 e = e.next()) { 502 if (e.sym == c) return true; 503 } 504 return false; 505 } 506 507 /** Return the entry associated with given name, starting in 508 * this scope and proceeding outwards. If no entry was found, 509 * return the sentinel, which is characterized by having a null in 510 * both its scope and sym fields, whereas both fields are non-null 511 * for regular entries. 512 */ lookup(Name name)513 protected Entry lookup(Name name) { 514 return lookup(name, noFilter); 515 } 516 lookup(Name name, Filter<Symbol> sf)517 protected Entry lookup(Name name, Filter<Symbol> sf) { 518 Entry e = table[getIndex(name)]; 519 if (e == null || e == sentinel) 520 return sentinel; 521 while (e.scope != null && (e.sym.name != name || (sf != null && !sf.accepts(e.sym)))) 522 e = e.shadowed; 523 return e; 524 } 525 findFirst(Name name, Filter<Symbol> sf)526 public Symbol findFirst(Name name, Filter<Symbol> sf) { 527 return lookup(name, sf).sym; 528 } 529 530 /*void dump (java.io.PrintStream out) { 531 out.println(this); 532 for (int l=0; l < table.length; l++) { 533 Entry le = table[l]; 534 out.print("#"+l+": "); 535 if (le==sentinel) out.println("sentinel"); 536 else if(le == null) out.println("null"); 537 else out.println(""+le+" s:"+le.sym); 538 } 539 }*/ 540 541 /** Look for slot in the table. 542 * We use open addressing with double hashing. 543 */ getIndex(Name name)544 int getIndex (Name name) { 545 int h = name.hashCode(); 546 int i = h & hashMask; 547 // The expression below is always odd, so it is guaranteed 548 // to be mutually prime with table.length, a power of 2. 549 int x = hashMask - ((h + (h >> 16)) << 1); 550 int d = -1; // Index of a deleted item. 551 for (;;) { 552 Entry e = table[i]; 553 if (e == null) 554 return d >= 0 ? d : i; 555 if (e == sentinel) { 556 // We have to keep searching even if we see a deleted item. 557 // However, remember the index in case we fail to find the name. 558 if (d < 0) 559 d = i; 560 } else if (e.sym.name == name) 561 return i; 562 i = (i + x) & hashMask; 563 } 564 } 565 anyMatch(Filter<Symbol> sf)566 public boolean anyMatch(Filter<Symbol> sf) { 567 return getSymbols(sf, NON_RECURSIVE).iterator().hasNext(); 568 } 569 getSymbols(final Filter<Symbol> sf, final LookupKind lookupKind)570 public Iterable<Symbol> getSymbols(final Filter<Symbol> sf, 571 final LookupKind lookupKind) { 572 return () -> new Iterator<Symbol>() { 573 private ScopeImpl currScope = ScopeImpl.this; 574 private Entry currEntry = elems; 575 private int seenRemoveCount = currScope.removeCount; 576 { 577 update(); 578 } 579 580 public boolean hasNext() { 581 if (seenRemoveCount != currScope.removeCount && 582 currEntry != null && 583 !currEntry.scope.includes(currEntry.sym)) { 584 doNext(); //skip entry that is no longer in the Scope 585 seenRemoveCount = currScope.removeCount; 586 } 587 return currEntry != null; 588 } 589 590 public Symbol next() { 591 if (!hasNext()) { 592 throw new NoSuchElementException(); 593 } 594 595 return doNext(); 596 } 597 private Symbol doNext() { 598 Symbol sym = (currEntry == null ? null : currEntry.sym); 599 if (currEntry != null) { 600 currEntry = currEntry.sibling; 601 } 602 update(); 603 return sym; 604 } 605 606 private void update() { 607 skipToNextMatchingEntry(); 608 if (lookupKind == RECURSIVE) { 609 while (currEntry == null && currScope.next != null) { 610 currScope = currScope.next; 611 currEntry = currScope.elems; 612 seenRemoveCount = currScope.removeCount; 613 skipToNextMatchingEntry(); 614 } 615 } 616 } 617 618 void skipToNextMatchingEntry() { 619 while (currEntry != null && sf != null && !sf.accepts(currEntry.sym)) { 620 currEntry = currEntry.sibling; 621 } 622 } 623 }; 624 } 625 getSymbolsByName(final Name name, final Filter<Symbol> sf, final LookupKind lookupKind)626 public Iterable<Symbol> getSymbolsByName(final Name name, 627 final Filter<Symbol> sf, 628 final LookupKind lookupKind) { 629 return () -> new Iterator<Symbol>() { 630 Entry currentEntry = lookup(name, sf); 631 int seenRemoveCount = currentEntry.scope != null ? 632 currentEntry.scope.removeCount : -1; 633 634 public boolean hasNext() { 635 if (currentEntry.scope != null && 636 seenRemoveCount != currentEntry.scope.removeCount && 637 !currentEntry.scope.includes(currentEntry.sym)) { 638 doNext(); //skip entry that is no longer in the Scope 639 } 640 return currentEntry.scope != null && 641 (lookupKind == RECURSIVE || 642 currentEntry.scope == ScopeImpl.this); 643 } 644 public Symbol next() { 645 if (!hasNext()) { 646 throw new NoSuchElementException(); 647 } 648 return doNext(); 649 } 650 private Symbol doNext() { 651 Entry prevEntry = currentEntry; 652 currentEntry = currentEntry.next(sf); 653 return prevEntry.sym; 654 } 655 public void remove() { 656 throw new UnsupportedOperationException(); 657 } 658 }; 659 } 660 getOrigin(Symbol s)661 public Scope getOrigin(Symbol s) { 662 for (Scope.Entry e = lookup(s.name); e.scope != null ; e = e.next()) { 663 if (e.sym == s) { 664 return this; 665 } 666 } 667 return null; 668 } 669 670 @Override isStaticallyImported(Symbol s)671 public boolean isStaticallyImported(Symbol s) { 672 return false; 673 } 674 toString()675 public String toString() { 676 StringBuilder result = new StringBuilder(); 677 result.append("Scope["); 678 for (ScopeImpl s = this; s != null ; s = s.next) { 679 if (s != this) result.append(" | "); 680 for (Entry e = s.elems; e != null; e = e.sibling) { 681 if (e != s.elems) result.append(", "); 682 result.append(e.sym); 683 } 684 } 685 result.append("]"); 686 return result.toString(); 687 } 688 } 689 690 /** A class for scope entries. 691 */ 692 private static class Entry { 693 694 /** The referenced symbol. 695 * sym == null iff this == sentinel 696 */ 697 public Symbol sym; 698 699 /** An entry with the same hash code, or sentinel. 700 */ 701 private Entry shadowed; 702 703 /** Next entry in same scope. 704 */ 705 public Entry sibling; 706 707 /** The entry's scope. 708 * scope == null iff this == sentinel 709 */ 710 public ScopeImpl scope; 711 712 public Entry(Symbol sym, Entry shadowed, Entry sibling, ScopeImpl scope) { 713 this.sym = sym; 714 this.shadowed = shadowed; 715 this.sibling = sibling; 716 this.scope = scope; 717 } 718 719 /** Return next entry with the same name as this entry, proceeding 720 * outwards if not found in this scope. 721 */ 722 public Entry next() { 723 return shadowed; 724 } 725 726 public Entry next(Filter<Symbol> sf) { 727 if (shadowed.sym == null || sf == null || sf.accepts(shadowed.sym)) return shadowed; 728 else return shadowed.next(sf); 729 } 730 731 } 732 733 public static class ImportScope extends CompoundScope { 734 735 public ImportScope(Symbol owner) { 736 super(owner); 737 } 738 739 /**Finalize the content of the ImportScope to speed-up future lookups. 740 * No further changes to class hierarchy or class content will be reflected. 741 */ 742 public void finalizeScope() { 743 for (List<Scope> scopes = this.subScopes.toList(); scopes.nonEmpty(); scopes = scopes.tail) { 744 scopes.head = finalizeSingleScope(scopes.head); 745 } 746 } 747 748 protected Scope finalizeSingleScope(Scope impScope) { 749 if (impScope instanceof FilterImportScope && impScope.owner.kind == Kind.TYP && 750 ((FilterImportScope) impScope).isStaticallyImported()) { 751 WriteableScope finalized = WriteableScope.create(impScope.owner); 752 753 for (Symbol sym : impScope.getSymbols()) { 754 finalized.enter(sym); 755 } 756 757 finalized.listeners.add(new ScopeListener() { 758 @Override 759 public void symbolAdded(Symbol sym, Scope s) { 760 Assert.error("The scope is sealed."); 761 } 762 763 @Override 764 public void symbolRemoved(Symbol sym, Scope s) { 765 Assert.error("The scope is sealed."); 766 } 767 }); 768 769 return finalized; 770 } 771 772 return impScope; 773 } 774 775 } 776 777 public static class NamedImportScope extends ImportScope { 778 779 /*A cache for quick lookup of Scopes that may contain the given name. 780 ScopeImpl and Entry is not used, as it is maps names to Symbols, 781 but it is necessary to map names to Scopes at this place (so that any 782 changes to the content of the Scopes is reflected when looking up the 783 Symbols. 784 */ 785 private final Map<Name, Scope[]> name2Scopes = new HashMap<>(); 786 787 public NamedImportScope(Symbol owner) { 788 super(owner); 789 } 790 791 public Scope importByName(Types types, Scope origin, Name name, ImportFilter filter, JCImport imp, BiConsumer<JCImport, CompletionFailure> cfHandler) { 792 return appendScope(new FilterImportScope(types, origin, name, filter, imp, cfHandler), name); 793 } 794 795 public Scope importType(Scope delegate, Scope origin, Symbol sym) { 796 return appendScope(new SingleEntryScope(delegate.owner, sym, origin), sym.name); 797 } 798 799 private Scope appendScope(Scope newScope, Name name) { 800 appendSubScope(newScope); 801 Scope[] existing = name2Scopes.get(name); 802 if (existing != null) 803 existing = Arrays.copyOf(existing, existing.length + 1); 804 else 805 existing = new Scope[1]; 806 existing[existing.length - 1] = newScope; 807 name2Scopes.put(name, existing); 808 return newScope; 809 } 810 811 @Override 812 public Iterable<Symbol> getSymbolsByName(Name name, Filter<Symbol> sf, LookupKind lookupKind) { 813 Scope[] scopes = name2Scopes.get(name); 814 if (scopes == null) 815 return Collections.emptyList(); 816 return () -> Iterators.createCompoundIterator(Arrays.asList(scopes), 817 scope -> scope.getSymbolsByName(name, 818 sf, 819 lookupKind) 820 .iterator()); 821 } 822 public void finalizeScope() { 823 super.finalizeScope(); 824 for (Scope[] scopes : name2Scopes.values()) { 825 for (int i = 0; i < scopes.length; i++) { 826 scopes[i] = finalizeSingleScope(scopes[i]); 827 } 828 } 829 } 830 831 private static class SingleEntryScope extends Scope { 832 833 private final Symbol sym; 834 private final List<Symbol> content; 835 private final Scope origin; 836 837 public SingleEntryScope(Symbol owner, Symbol sym, Scope origin) { 838 super(owner); 839 this.sym = sym; 840 this.content = List.of(sym); 841 this.origin = origin; 842 } 843 844 @Override 845 public Iterable<Symbol> getSymbols(Filter<Symbol> sf, LookupKind lookupKind) { 846 return sf == null || sf.accepts(sym) ? content : Collections.emptyList(); 847 } 848 849 @Override 850 public Iterable<Symbol> getSymbolsByName(Name name, 851 Filter<Symbol> sf, 852 LookupKind lookupKind) { 853 return sym.name == name && 854 (sf == null || sf.accepts(sym)) ? content : Collections.emptyList(); 855 } 856 857 @Override 858 public Scope getOrigin(Symbol byName) { 859 return sym == byName ? origin : null; 860 } 861 862 @Override 863 public boolean isStaticallyImported(Symbol byName) { 864 return false; 865 } 866 867 } 868 } 869 870 public static class StarImportScope extends ImportScope { 871 872 public StarImportScope(Symbol owner) { 873 super(owner); 874 } 875 876 public void importAll(Types types, Scope origin, 877 ImportFilter filter, 878 JCImport imp, 879 BiConsumer<JCImport, CompletionFailure> cfHandler) { 880 for (Scope existing : subScopes) { 881 Assert.check(existing instanceof FilterImportScope); 882 FilterImportScope fis = (FilterImportScope) existing; 883 if (fis.origin == origin && fis.filter == filter && 884 fis.imp.staticImport == imp.staticImport) 885 return ; //avoid entering the same scope twice 886 } 887 prependSubScope(new FilterImportScope(types, origin, null, filter, imp, cfHandler)); 888 } 889 890 public boolean isFilled() { 891 return subScopes.nonEmpty(); 892 } 893 894 } 895 896 public interface ImportFilter { 897 public boolean accepts(Scope origin, Symbol sym); 898 } 899 900 private static class FilterImportScope extends Scope { 901 902 private final Types types; 903 private final Scope origin; 904 private final Name filterName; 905 private final ImportFilter filter; 906 private final JCImport imp; 907 private final BiConsumer<JCImport, CompletionFailure> cfHandler; 908 909 public FilterImportScope(Types types, 910 Scope origin, 911 Name filterName, 912 ImportFilter filter, 913 JCImport imp, 914 BiConsumer<JCImport, CompletionFailure> cfHandler) { 915 super(origin.owner); 916 this.types = types; 917 this.origin = origin; 918 this.filterName = filterName; 919 this.filter = filter; 920 this.imp = imp; 921 this.cfHandler = cfHandler; 922 } 923 924 @Override 925 public Iterable<Symbol> getSymbols(final Filter<Symbol> sf, final LookupKind lookupKind) { 926 if (filterName != null) 927 return getSymbolsByName(filterName, sf, lookupKind); 928 try { 929 SymbolImporter si = new SymbolImporter(imp.staticImport) { 930 @Override 931 Iterable<Symbol> doLookup(TypeSymbol tsym) { 932 return tsym.members().getSymbols(sf, lookupKind); 933 } 934 }; 935 List<Iterable<Symbol>> results = 936 si.importFrom((TypeSymbol) origin.owner, List.nil()); 937 return () -> createFilterIterator(createCompoundIterator(results, 938 Iterable::iterator), 939 s -> filter.accepts(origin, s)); 940 } catch (CompletionFailure cf) { 941 cfHandler.accept(imp, cf); 942 return Collections.emptyList(); 943 } 944 } 945 946 @Override 947 public Iterable<Symbol> getSymbolsByName(final Name name, 948 final Filter<Symbol> sf, 949 final LookupKind lookupKind) { 950 if (filterName != null && filterName != name) 951 return Collections.emptyList(); 952 try { 953 SymbolImporter si = new SymbolImporter(imp.staticImport) { 954 @Override 955 Iterable<Symbol> doLookup(TypeSymbol tsym) { 956 return tsym.members().getSymbolsByName(name, sf, lookupKind); 957 } 958 }; 959 List<Iterable<Symbol>> results = 960 si.importFrom((TypeSymbol) origin.owner, List.nil()); 961 return () -> createFilterIterator(createCompoundIterator(results, 962 Iterable::iterator), 963 s -> filter.accepts(origin, s)); 964 } catch (CompletionFailure cf) { 965 cfHandler.accept(imp, cf); 966 return Collections.emptyList(); 967 } 968 } 969 970 @Override 971 public Scope getOrigin(Symbol byName) { 972 return origin; 973 } 974 975 @Override 976 public boolean isStaticallyImported(Symbol byName) { 977 return isStaticallyImported(); 978 } 979 980 public boolean isStaticallyImported() { 981 return imp.staticImport; 982 } 983 984 abstract class SymbolImporter { 985 Set<Symbol> processed = new HashSet<>(); 986 List<Iterable<Symbol>> delegates = List.nil(); 987 final boolean inspectSuperTypes; 988 public SymbolImporter(boolean inspectSuperTypes) { 989 this.inspectSuperTypes = inspectSuperTypes; 990 } 991 List<Iterable<Symbol>> importFrom(TypeSymbol tsym, List<Iterable<Symbol>> results) { 992 if (tsym == null || !processed.add(tsym)) 993 return results; 994 995 996 if (inspectSuperTypes) { 997 // also import inherited names 998 results = importFrom(types.supertype(tsym.type).tsym, results); 999 for (Type t : types.interfaces(tsym.type)) 1000 results = importFrom(t.tsym, results); 1001 } 1002 1003 return results.prepend(doLookup(tsym)); 1004 } 1005 abstract Iterable<Symbol> doLookup(TypeSymbol tsym); 1006 } 1007 1008 } 1009 1010 /** A class scope adds capabilities to keep track of changes in related 1011 * class scopes - this allows client to realize whether a class scope 1012 * has changed, either directly (because a new member has been added/removed 1013 * to this scope) or indirectly (i.e. because a new member has been 1014 * added/removed into a supertype scope) 1015 */ 1016 public static class CompoundScope extends Scope implements ScopeListener { 1017 1018 ListBuffer<Scope> subScopes = new ListBuffer<>(); 1019 private int mark = 0; 1020 1021 public CompoundScope(Symbol owner) { 1022 super(owner); 1023 } 1024 1025 public void prependSubScope(Scope that) { 1026 if (that != null) { 1027 subScopes.prepend(that); 1028 that.listeners.add(this); 1029 mark++; 1030 listeners.symbolAdded(null, this); 1031 } 1032 } 1033 1034 public void appendSubScope(Scope that) { 1035 if (that != null) { 1036 subScopes.append(that); 1037 that.listeners.add(this); 1038 mark++; 1039 listeners.symbolAdded(null, this); 1040 } 1041 } 1042 1043 public void symbolAdded(Symbol sym, Scope s) { 1044 mark++; 1045 listeners.symbolAdded(sym, s); 1046 } 1047 1048 public void symbolRemoved(Symbol sym, Scope s) { 1049 mark++; 1050 listeners.symbolRemoved(sym, s); 1051 } 1052 1053 public int getMark() { 1054 return mark; 1055 } 1056 1057 @Override 1058 public String toString() { 1059 StringBuilder buf = new StringBuilder(); 1060 buf.append("CompoundScope{"); 1061 String sep = ""; 1062 for (Scope s : subScopes) { 1063 buf.append(sep); 1064 buf.append(s); 1065 sep = ","; 1066 } 1067 buf.append("}"); 1068 return buf.toString(); 1069 } 1070 1071 @Override 1072 public Iterable<Symbol> getSymbols(final Filter<Symbol> sf, 1073 final LookupKind lookupKind) { 1074 return () -> Iterators.createCompoundIterator(subScopes, 1075 scope -> scope.getSymbols(sf, 1076 lookupKind) 1077 .iterator()); 1078 } 1079 1080 @Override 1081 public Iterable<Symbol> getSymbolsByName(final Name name, 1082 final Filter<Symbol> sf, 1083 final LookupKind lookupKind) { 1084 return () -> Iterators.createCompoundIterator(subScopes, 1085 scope -> scope.getSymbolsByName(name, 1086 sf, 1087 lookupKind) 1088 .iterator()); 1089 } 1090 1091 @Override 1092 public Scope getOrigin(Symbol sym) { 1093 for (Scope delegate : subScopes) { 1094 if (delegate.includes(sym)) 1095 return delegate.getOrigin(sym); 1096 } 1097 1098 return null; 1099 } 1100 1101 @Override 1102 public boolean isStaticallyImported(Symbol sym) { 1103 for (Scope delegate : subScopes) { 1104 if (delegate.includes(sym)) 1105 return delegate.isStaticallyImported(sym); 1106 } 1107 1108 return false; 1109 } 1110 1111 } 1112 1113 /** An error scope, for which the owner should be an error symbol. */ 1114 public static class ErrorScope extends ScopeImpl { 1115 ErrorScope(ScopeImpl next, Symbol errSymbol, Entry[] table) { 1116 super(next, /*owner=*/errSymbol, table); 1117 } 1118 public ErrorScope(Symbol errSymbol) { 1119 super(errSymbol); 1120 } 1121 public WriteableScope dup(Symbol newOwner) { 1122 return new ErrorScope(this, newOwner, table); 1123 } 1124 public WriteableScope dupUnshared(Symbol newOwner) { 1125 return new ErrorScope(this, newOwner, table.clone()); 1126 } 1127 public Entry lookup(Name name) { 1128 Entry e = super.lookup(name); 1129 if (e.scope == null) 1130 return new Entry(owner, null, null, null); 1131 else 1132 return e; 1133 } 1134 } 1135 } 1136