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.nextSibling; 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 if (elems == e) { 470 elems = e.nextSibling; 471 if (elems != null) 472 elems.prevSibling = null; 473 } else { 474 Assert.check(e.prevSibling != null, e.sym); 475 e.prevSibling.nextSibling = e.nextSibling; 476 if (e.nextSibling != null) 477 e.nextSibling.prevSibling = e.prevSibling; 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.nextSibling; 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.nextSibling; 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.nextSibling) { 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 nextSibling; 706 707 /** Prev entry in same scope. 708 */ 709 public Entry prevSibling; 710 711 /** The entry's scope. 712 * scope == null iff this == sentinel 713 */ 714 public ScopeImpl scope; 715 716 public Entry(Symbol sym, Entry shadowed, Entry nextSibling, ScopeImpl scope) { 717 this.sym = sym; 718 this.shadowed = shadowed; 719 this.nextSibling = nextSibling; 720 this.scope = scope; 721 if (nextSibling != null) 722 nextSibling.prevSibling = this; 723 } 724 725 /** Return next entry with the same name as this entry, proceeding 726 * outwards if not found in this scope. 727 */ 728 public Entry next() { 729 return shadowed; 730 } 731 732 public Entry next(Filter<Symbol> sf) { 733 if (shadowed.sym == null || sf == null || sf.accepts(shadowed.sym)) return shadowed; 734 else return shadowed.next(sf); 735 } 736 737 } 738 739 public static class ImportScope extends CompoundScope { 740 741 public ImportScope(Symbol owner) { 742 super(owner); 743 } 744 745 /**Finalize the content of the ImportScope to speed-up future lookups. 746 * No further changes to class hierarchy or class content will be reflected. 747 */ 748 public void finalizeScope() { 749 for (List<Scope> scopes = this.subScopes.toList(); scopes.nonEmpty(); scopes = scopes.tail) { 750 scopes.head = finalizeSingleScope(scopes.head); 751 } 752 } 753 754 protected Scope finalizeSingleScope(Scope impScope) { 755 if (impScope instanceof FilterImportScope && impScope.owner.kind == Kind.TYP && 756 ((FilterImportScope) impScope).isStaticallyImported()) { 757 WriteableScope finalized = WriteableScope.create(impScope.owner); 758 759 for (Symbol sym : impScope.getSymbols()) { 760 finalized.enter(sym); 761 } 762 763 finalized.listeners.add(new ScopeListener() { 764 @Override 765 public void symbolAdded(Symbol sym, Scope s) { 766 Assert.error("The scope is sealed."); 767 } 768 769 @Override 770 public void symbolRemoved(Symbol sym, Scope s) { 771 Assert.error("The scope is sealed."); 772 } 773 }); 774 775 return finalized; 776 } 777 778 return impScope; 779 } 780 781 } 782 783 public static class NamedImportScope extends ImportScope { 784 785 /*A cache for quick lookup of Scopes that may contain the given name. 786 ScopeImpl and Entry is not used, as it is maps names to Symbols, 787 but it is necessary to map names to Scopes at this place (so that any 788 changes to the content of the Scopes is reflected when looking up the 789 Symbols. 790 */ 791 private final Map<Name, Scope[]> name2Scopes = new HashMap<>(); 792 793 public NamedImportScope(Symbol owner) { 794 super(owner); 795 } 796 797 public Scope importByName(Types types, Scope origin, Name name, ImportFilter filter, JCImport imp, BiConsumer<JCImport, CompletionFailure> cfHandler) { 798 return appendScope(new FilterImportScope(types, origin, name, filter, imp, cfHandler), name); 799 } 800 801 public Scope importType(Scope delegate, Scope origin, Symbol sym) { 802 return appendScope(new SingleEntryScope(delegate.owner, sym, origin), sym.name); 803 } 804 805 private Scope appendScope(Scope newScope, Name name) { 806 appendSubScope(newScope); 807 Scope[] existing = name2Scopes.get(name); 808 if (existing != null) 809 existing = Arrays.copyOf(existing, existing.length + 1); 810 else 811 existing = new Scope[1]; 812 existing[existing.length - 1] = newScope; 813 name2Scopes.put(name, existing); 814 return newScope; 815 } 816 817 @Override 818 public Iterable<Symbol> getSymbolsByName(Name name, Filter<Symbol> sf, LookupKind lookupKind) { 819 Scope[] scopes = name2Scopes.get(name); 820 if (scopes == null) 821 return Collections.emptyList(); 822 return () -> Iterators.createCompoundIterator(Arrays.asList(scopes), 823 scope -> scope.getSymbolsByName(name, 824 sf, 825 lookupKind) 826 .iterator()); 827 } 828 public void finalizeScope() { 829 super.finalizeScope(); 830 for (Scope[] scopes : name2Scopes.values()) { 831 for (int i = 0; i < scopes.length; i++) { 832 scopes[i] = finalizeSingleScope(scopes[i]); 833 } 834 } 835 } 836 837 private static class SingleEntryScope extends Scope { 838 839 private final Symbol sym; 840 private final List<Symbol> content; 841 private final Scope origin; 842 843 public SingleEntryScope(Symbol owner, Symbol sym, Scope origin) { 844 super(owner); 845 this.sym = sym; 846 this.content = List.of(sym); 847 this.origin = origin; 848 } 849 850 @Override 851 public Iterable<Symbol> getSymbols(Filter<Symbol> sf, LookupKind lookupKind) { 852 return sf == null || sf.accepts(sym) ? content : Collections.emptyList(); 853 } 854 855 @Override 856 public Iterable<Symbol> getSymbolsByName(Name name, 857 Filter<Symbol> sf, 858 LookupKind lookupKind) { 859 return sym.name == name && 860 (sf == null || sf.accepts(sym)) ? content : Collections.emptyList(); 861 } 862 863 @Override 864 public Scope getOrigin(Symbol byName) { 865 return sym == byName ? origin : null; 866 } 867 868 @Override 869 public boolean isStaticallyImported(Symbol byName) { 870 return false; 871 } 872 873 } 874 } 875 876 public static class StarImportScope extends ImportScope { 877 878 public StarImportScope(Symbol owner) { 879 super(owner); 880 } 881 882 public void importAll(Types types, Scope origin, 883 ImportFilter filter, 884 JCImport imp, 885 BiConsumer<JCImport, CompletionFailure> cfHandler) { 886 for (Scope existing : subScopes) { 887 Assert.check(existing instanceof FilterImportScope); 888 FilterImportScope fis = (FilterImportScope) existing; 889 if (fis.origin == origin && fis.filter == filter && 890 fis.imp.staticImport == imp.staticImport) 891 return ; //avoid entering the same scope twice 892 } 893 prependSubScope(new FilterImportScope(types, origin, null, filter, imp, cfHandler)); 894 } 895 896 public boolean isFilled() { 897 return subScopes.nonEmpty(); 898 } 899 900 } 901 902 public interface ImportFilter { 903 public boolean accepts(Scope origin, Symbol sym); 904 } 905 906 private static class FilterImportScope extends Scope { 907 908 private final Types types; 909 private final Scope origin; 910 private final Name filterName; 911 private final ImportFilter filter; 912 private final JCImport imp; 913 private final BiConsumer<JCImport, CompletionFailure> cfHandler; 914 915 public FilterImportScope(Types types, 916 Scope origin, 917 Name filterName, 918 ImportFilter filter, 919 JCImport imp, 920 BiConsumer<JCImport, CompletionFailure> cfHandler) { 921 super(origin.owner); 922 this.types = types; 923 this.origin = origin; 924 this.filterName = filterName; 925 this.filter = filter; 926 this.imp = imp; 927 this.cfHandler = cfHandler; 928 } 929 930 @Override 931 public Iterable<Symbol> getSymbols(final Filter<Symbol> sf, final LookupKind lookupKind) { 932 if (filterName != null) 933 return getSymbolsByName(filterName, sf, lookupKind); 934 try { 935 SymbolImporter si = new SymbolImporter(imp.staticImport) { 936 @Override 937 Iterable<Symbol> doLookup(TypeSymbol tsym) { 938 return tsym.members().getSymbols(sf, lookupKind); 939 } 940 }; 941 List<Iterable<Symbol>> results = 942 si.importFrom((TypeSymbol) origin.owner, List.nil()); 943 return () -> createFilterIterator(createCompoundIterator(results, 944 Iterable::iterator), 945 s -> filter.accepts(origin, s)); 946 } catch (CompletionFailure cf) { 947 cfHandler.accept(imp, cf); 948 return Collections.emptyList(); 949 } 950 } 951 952 @Override 953 public Iterable<Symbol> getSymbolsByName(final Name name, 954 final Filter<Symbol> sf, 955 final LookupKind lookupKind) { 956 if (filterName != null && filterName != name) 957 return Collections.emptyList(); 958 try { 959 SymbolImporter si = new SymbolImporter(imp.staticImport) { 960 @Override 961 Iterable<Symbol> doLookup(TypeSymbol tsym) { 962 return tsym.members().getSymbolsByName(name, sf, lookupKind); 963 } 964 }; 965 List<Iterable<Symbol>> results = 966 si.importFrom((TypeSymbol) origin.owner, List.nil()); 967 return () -> createFilterIterator(createCompoundIterator(results, 968 Iterable::iterator), 969 s -> filter.accepts(origin, s)); 970 } catch (CompletionFailure cf) { 971 cfHandler.accept(imp, cf); 972 return Collections.emptyList(); 973 } 974 } 975 976 @Override 977 public Scope getOrigin(Symbol byName) { 978 return origin; 979 } 980 981 @Override 982 public boolean isStaticallyImported(Symbol byName) { 983 return isStaticallyImported(); 984 } 985 986 public boolean isStaticallyImported() { 987 return imp.staticImport; 988 } 989 990 abstract class SymbolImporter { 991 Set<Symbol> processed = new HashSet<>(); 992 List<Iterable<Symbol>> delegates = List.nil(); 993 final boolean inspectSuperTypes; 994 public SymbolImporter(boolean inspectSuperTypes) { 995 this.inspectSuperTypes = inspectSuperTypes; 996 } 997 List<Iterable<Symbol>> importFrom(TypeSymbol tsym, List<Iterable<Symbol>> results) { 998 if (tsym == null || !processed.add(tsym)) 999 return results; 1000 1001 1002 if (inspectSuperTypes) { 1003 // also import inherited names 1004 results = importFrom(types.supertype(tsym.type).tsym, results); 1005 for (Type t : types.interfaces(tsym.type)) 1006 results = importFrom(t.tsym, results); 1007 } 1008 1009 return results.prepend(doLookup(tsym)); 1010 } 1011 abstract Iterable<Symbol> doLookup(TypeSymbol tsym); 1012 } 1013 1014 } 1015 1016 /** A class scope adds capabilities to keep track of changes in related 1017 * class scopes - this allows client to realize whether a class scope 1018 * has changed, either directly (because a new member has been added/removed 1019 * to this scope) or indirectly (i.e. because a new member has been 1020 * added/removed into a supertype scope) 1021 */ 1022 public static class CompoundScope extends Scope implements ScopeListener { 1023 1024 ListBuffer<Scope> subScopes = new ListBuffer<>(); 1025 private int mark = 0; 1026 1027 public CompoundScope(Symbol owner) { 1028 super(owner); 1029 } 1030 1031 public void prependSubScope(Scope that) { 1032 if (that != null) { 1033 subScopes.prepend(that); 1034 that.listeners.add(this); 1035 mark++; 1036 listeners.symbolAdded(null, this); 1037 } 1038 } 1039 1040 public void appendSubScope(Scope that) { 1041 if (that != null) { 1042 subScopes.append(that); 1043 that.listeners.add(this); 1044 mark++; 1045 listeners.symbolAdded(null, this); 1046 } 1047 } 1048 1049 public void symbolAdded(Symbol sym, Scope s) { 1050 mark++; 1051 listeners.symbolAdded(sym, s); 1052 } 1053 1054 public void symbolRemoved(Symbol sym, Scope s) { 1055 mark++; 1056 listeners.symbolRemoved(sym, s); 1057 } 1058 1059 public int getMark() { 1060 return mark; 1061 } 1062 1063 @Override 1064 public String toString() { 1065 StringBuilder buf = new StringBuilder(); 1066 buf.append("CompoundScope{"); 1067 String sep = ""; 1068 for (Scope s : subScopes) { 1069 buf.append(sep); 1070 buf.append(s); 1071 sep = ","; 1072 } 1073 buf.append("}"); 1074 return buf.toString(); 1075 } 1076 1077 @Override 1078 public Iterable<Symbol> getSymbols(final Filter<Symbol> sf, 1079 final LookupKind lookupKind) { 1080 return () -> Iterators.createCompoundIterator(subScopes, 1081 scope -> scope.getSymbols(sf, 1082 lookupKind) 1083 .iterator()); 1084 } 1085 1086 @Override 1087 public Iterable<Symbol> getSymbolsByName(final Name name, 1088 final Filter<Symbol> sf, 1089 final LookupKind lookupKind) { 1090 return () -> Iterators.createCompoundIterator(subScopes, 1091 scope -> scope.getSymbolsByName(name, 1092 sf, 1093 lookupKind) 1094 .iterator()); 1095 } 1096 1097 @Override 1098 public Scope getOrigin(Symbol sym) { 1099 for (Scope delegate : subScopes) { 1100 if (delegate.includes(sym)) 1101 return delegate.getOrigin(sym); 1102 } 1103 1104 return null; 1105 } 1106 1107 @Override 1108 public boolean isStaticallyImported(Symbol sym) { 1109 for (Scope delegate : subScopes) { 1110 if (delegate.includes(sym)) 1111 return delegate.isStaticallyImported(sym); 1112 } 1113 1114 return false; 1115 } 1116 1117 } 1118 1119 /** An error scope, for which the owner should be an error symbol. */ 1120 public static class ErrorScope extends ScopeImpl { 1121 ErrorScope(ScopeImpl next, Symbol errSymbol, Entry[] table) { 1122 super(next, /*owner=*/errSymbol, table); 1123 } 1124 public ErrorScope(Symbol errSymbol) { 1125 super(errSymbol); 1126 } 1127 public WriteableScope dup(Symbol newOwner) { 1128 return new ErrorScope(this, newOwner, table); 1129 } 1130 public WriteableScope dupUnshared(Symbol newOwner) { 1131 return new ErrorScope(this, newOwner, table.clone()); 1132 } 1133 public Entry lookup(Name name) { 1134 Entry e = super.lookup(name); 1135 if (e.scope == null) 1136 return new Entry(owner, null, null, null); 1137 else 1138 return e; 1139 } 1140 } 1141 } 1142