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