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