Thu, 12 Jan 2012 15:28:34 +0000
7123100: javac fails with java.lang.StackOverflowError
Summary: Inference of under-constrained type-variables creates erroneous recursive wildcard types
Reviewed-by: jjg
1 /*
2 * Copyright (c) 1999, 2011, 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 com.sun.tools.javac.util.*;
29 import java.util.Iterator;
31 /** A scope represents an area of visibility in a Java program. The
32 * Scope class is a container for symbols which provides
33 * efficient access to symbols given their names. Scopes are implemented
34 * as hash tables with "open addressing" and "double hashing".
35 * Scopes can be nested; the next field of a scope points
36 * to its next outer scope. Nested scopes can share their hash tables.
37 *
38 * <p><b>This is NOT part of any supported API.
39 * If you write code that depends on this, you do so at your own risk.
40 * This code and its internal interfaces are subject to change or
41 * deletion without notice.</b>
42 */
43 public class Scope {
45 /** The number of scopes that share this scope's hash table.
46 */
47 private int shared;
49 /** Next enclosing scope (with whom this scope may share a hashtable)
50 */
51 public Scope next;
53 /** The scope's owner.
54 */
55 public Symbol owner;
57 /** A hash table for the scope's entries.
58 */
59 Entry[] table;
61 /** Mask for hash codes, always equal to (table.length - 1).
62 */
63 int hashMask;
65 /** A linear list that also contains all entries in
66 * reverse order of appearance (i.e later entries are pushed on top).
67 */
68 public Entry elems;
70 /** The number of elements in this scope.
71 * This includes deleted elements, whose value is the sentinel.
72 */
73 int nelems = 0;
75 /** A list of scopes to be notified if items are to be removed from this scope.
76 */
77 List<ScopeListener> listeners = List.nil();
79 /** Use as a "not-found" result for lookup.
80 * Also used to mark deleted entries in the table.
81 */
82 private static final Entry sentinel = new Entry(null, null, null, null);
84 /** The hash table's initial size.
85 */
86 private static final int INITIAL_SIZE = 0x10;
88 /** A value for the empty scope.
89 */
90 public static final Scope emptyScope = new Scope(null, null, new Entry[]{});
92 /** Construct a new scope, within scope next, with given owner, using
93 * given table. The table's length must be an exponent of 2.
94 */
95 private Scope(Scope next, Symbol owner, Entry[] table) {
96 this.next = next;
97 Assert.check(emptyScope == null || owner != null);
98 this.owner = owner;
99 this.table = table;
100 this.hashMask = table.length - 1;
101 }
103 /** Convenience constructor used for dup and dupUnshared. */
104 private Scope(Scope next, Symbol owner, Entry[] table, int nelems) {
105 this(next, owner, table);
106 this.nelems = nelems;
107 }
109 /** Construct a new scope, within scope next, with given owner,
110 * using a fresh table of length INITIAL_SIZE.
111 */
112 public Scope(Symbol owner) {
113 this(null, owner, new Entry[INITIAL_SIZE]);
114 }
116 /** Construct a fresh scope within this scope, with same owner,
117 * which shares its table with the outer scope. Used in connection with
118 * method leave if scope access is stack-like in order to avoid allocation
119 * of fresh tables.
120 */
121 public Scope dup() {
122 return dup(this.owner);
123 }
125 /** Construct a fresh scope within this scope, with new owner,
126 * which shares its table with the outer scope. Used in connection with
127 * method leave if scope access is stack-like in order to avoid allocation
128 * of fresh tables.
129 */
130 public Scope dup(Symbol newOwner) {
131 Scope result = new Scope(this, newOwner, this.table, this.nelems);
132 shared++;
133 // System.out.println("====> duping scope " + this.hashCode() + " owned by " + newOwner + " to " + result.hashCode());
134 // new Error().printStackTrace(System.out);
135 return result;
136 }
138 /** Construct a fresh scope within this scope, with same owner,
139 * with a new hash table, whose contents initially are those of
140 * the table of its outer scope.
141 */
142 public Scope dupUnshared() {
143 return new Scope(this, this.owner, this.table.clone(), this.nelems);
144 }
146 /** Remove all entries of this scope from its table, if shared
147 * with next.
148 */
149 public Scope leave() {
150 Assert.check(shared == 0);
151 if (table != next.table) return next;
152 while (elems != null) {
153 int hash = getIndex(elems.sym.name);
154 Entry e = table[hash];
155 Assert.check(e == elems, elems.sym);
156 table[hash] = elems.shadowed;
157 elems = elems.sibling;
158 }
159 Assert.check(next.shared > 0);
160 next.shared--;
161 next.nelems = nelems;
162 // System.out.println("====> leaving scope " + this.hashCode() + " owned by " + this.owner + " to " + next.hashCode());
163 // new Error().printStackTrace(System.out);
164 return next;
165 }
167 /** Double size of hash table.
168 */
169 private void dble() {
170 Assert.check(shared == 0);
171 Entry[] oldtable = table;
172 Entry[] newtable = new Entry[oldtable.length * 2];
173 for (Scope s = this; s != null; s = s.next) {
174 if (s.table == oldtable) {
175 Assert.check(s == this || s.shared != 0);
176 s.table = newtable;
177 s.hashMask = newtable.length - 1;
178 }
179 }
180 int n = 0;
181 for (int i = oldtable.length; --i >= 0; ) {
182 Entry e = oldtable[i];
183 if (e != null && e != sentinel) {
184 table[getIndex(e.sym.name)] = e;
185 n++;
186 }
187 }
188 // We don't need to update nelems for shared inherited scopes,
189 // since that gets handled by leave().
190 nelems = n;
191 }
193 /** Enter symbol sym in this scope.
194 */
195 public void enter(Symbol sym) {
196 Assert.check(shared == 0);
197 enter(sym, this);
198 }
200 public void enter(Symbol sym, Scope s) {
201 enter(sym, s, s);
202 }
204 /**
205 * Enter symbol sym in this scope, but mark that it comes from
206 * given scope `s' accessed through `origin'. The last two
207 * arguments are only used in import scopes.
208 */
209 public void enter(Symbol sym, Scope s, Scope origin) {
210 Assert.check(shared == 0);
211 if (nelems * 3 >= hashMask * 2)
212 dble();
213 int hash = getIndex(sym.name);
214 Entry old = table[hash];
215 if (old == null) {
216 old = sentinel;
217 nelems++;
218 }
219 Entry e = makeEntry(sym, old, elems, s, origin);
220 table[hash] = e;
221 elems = e;
223 //notify listeners
224 for (List<ScopeListener> l = listeners; l.nonEmpty(); l = l.tail) {
225 l.head.symbolAdded(sym, this);
226 }
227 }
229 Entry makeEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, Scope origin) {
230 return new Entry(sym, shadowed, sibling, scope);
231 }
234 public interface ScopeListener {
235 public void symbolAdded(Symbol sym, Scope s);
236 public void symbolRemoved(Symbol sym, Scope s);
237 }
239 public void addScopeListener(ScopeListener sl) {
240 listeners = listeners.prepend(sl);
241 }
243 /** Remove symbol from this scope. Used when an inner class
244 * attribute tells us that the class isn't a package member.
245 */
246 public void remove(Symbol sym) {
247 Assert.check(shared == 0);
248 Entry e = lookup(sym.name);
249 if (e.scope == null) return;
251 // remove e from table and shadowed list;
252 int i = getIndex(sym.name);
253 Entry te = table[i];
254 if (te == e)
255 table[i] = e.shadowed;
256 else while (true) {
257 if (te.shadowed == e) {
258 te.shadowed = e.shadowed;
259 break;
260 }
261 te = te.shadowed;
262 }
264 // remove e from elems and sibling list
265 te = elems;
266 if (te == e)
267 elems = e.sibling;
268 else while (true) {
269 if (te.sibling == e) {
270 te.sibling = e.sibling;
271 break;
272 }
273 te = te.sibling;
274 }
276 //notify listeners
277 for (List<ScopeListener> l = listeners; l.nonEmpty(); l = l.tail) {
278 l.head.symbolRemoved(sym, this);
279 }
280 }
282 /** Enter symbol sym in this scope if not already there.
283 */
284 public void enterIfAbsent(Symbol sym) {
285 Assert.check(shared == 0);
286 Entry e = lookup(sym.name);
287 while (e.scope == this && e.sym.kind != sym.kind) e = e.next();
288 if (e.scope != this) enter(sym);
289 }
291 /** Given a class, is there already a class with same fully
292 * qualified name in this (import) scope?
293 */
294 public boolean includes(Symbol c) {
295 for (Scope.Entry e = lookup(c.name);
296 e.scope == this;
297 e = e.next()) {
298 if (e.sym == c) return true;
299 }
300 return false;
301 }
303 static final Filter<Symbol> noFilter = new Filter<Symbol>() {
304 public boolean accepts(Symbol s) {
305 return true;
306 }
307 };
309 /** Return the entry associated with given name, starting in
310 * this scope and proceeding outwards. If no entry was found,
311 * return the sentinel, which is characterized by having a null in
312 * both its scope and sym fields, whereas both fields are non-null
313 * for regular entries.
314 */
315 public Entry lookup(Name name) {
316 return lookup(name, noFilter);
317 }
318 public Entry lookup(Name name, Filter<Symbol> sf) {
319 Entry e = table[getIndex(name)];
320 if (e == null || e == sentinel)
321 return sentinel;
322 while (e.scope != null && (e.sym.name != name || !sf.accepts(e.sym)))
323 e = e.shadowed;
324 return e;
325 }
327 /*void dump (java.io.PrintStream out) {
328 out.println(this);
329 for (int l=0; l < table.length; l++) {
330 Entry le = table[l];
331 out.print("#"+l+": ");
332 if (le==sentinel) out.println("sentinel");
333 else if(le == null) out.println("null");
334 else out.println(""+le+" s:"+le.sym);
335 }
336 }*/
338 /** Look for slot in the table.
339 * We use open addressing with double hashing.
340 */
341 int getIndex (Name name) {
342 int h = name.hashCode();
343 int i = h & hashMask;
344 // The expression below is always odd, so it is guaranteed
345 // to be mutually prime with table.length, a power of 2.
346 int x = hashMask - ((h + (h >> 16)) << 1);
347 int d = -1; // Index of a deleted item.
348 for (;;) {
349 Entry e = table[i];
350 if (e == null)
351 return d >= 0 ? d : i;
352 if (e == sentinel) {
353 // We have to keep searching even if we see a deleted item.
354 // However, remember the index in case we fail to find the name.
355 if (d < 0)
356 d = i;
357 } else if (e.sym.name == name)
358 return i;
359 i = (i + x) & hashMask;
360 }
361 }
363 public Iterable<Symbol> getElements() {
364 return getElements(noFilter);
365 }
367 public Iterable<Symbol> getElements(final Filter<Symbol> sf) {
368 return new Iterable<Symbol>() {
369 public Iterator<Symbol> iterator() {
370 return new Iterator<Symbol>() {
371 private Scope currScope = Scope.this;
372 private Scope.Entry currEntry = elems;
373 {
374 update();
375 }
377 public boolean hasNext() {
378 return currEntry != null;
379 }
381 public Symbol next() {
382 Symbol sym = (currEntry == null ? null : currEntry.sym);
383 if (currEntry != null) {
384 currEntry = currEntry.sibling;
385 }
386 update();
387 return sym;
388 }
390 public void remove() {
391 throw new UnsupportedOperationException();
392 }
394 private void update() {
395 skipToNextMatchingEntry();
396 while (currEntry == null && currScope.next != null) {
397 currScope = currScope.next;
398 currEntry = currScope.elems;
399 skipToNextMatchingEntry();
400 }
401 }
403 void skipToNextMatchingEntry() {
404 while (currEntry != null && !sf.accepts(currEntry.sym)) {
405 currEntry = currEntry.sibling;
406 }
407 }
408 };
409 }
410 };
411 }
413 public Iterable<Symbol> getElementsByName(Name name) {
414 return getElementsByName(name, noFilter);
415 }
417 public Iterable<Symbol> getElementsByName(final Name name, final Filter<Symbol> sf) {
418 return new Iterable<Symbol>() {
419 public Iterator<Symbol> iterator() {
420 return new Iterator<Symbol>() {
421 Scope.Entry currentEntry = lookup(name, sf);
423 public boolean hasNext() {
424 return currentEntry.scope != null;
425 }
426 public Symbol next() {
427 Scope.Entry prevEntry = currentEntry;
428 currentEntry = currentEntry.next(sf);
429 return prevEntry.sym;
430 }
431 public void remove() {
432 throw new UnsupportedOperationException();
433 }
434 };
435 }
436 };
437 }
439 public String toString() {
440 StringBuilder result = new StringBuilder();
441 result.append("Scope[");
442 for (Scope s = this; s != null ; s = s.next) {
443 if (s != this) result.append(" | ");
444 for (Entry e = s.elems; e != null; e = e.sibling) {
445 if (e != s.elems) result.append(", ");
446 result.append(e.sym);
447 }
448 }
449 result.append("]");
450 return result.toString();
451 }
453 /** A class for scope entries.
454 */
455 public static class Entry {
457 /** The referenced symbol.
458 * sym == null iff this == sentinel
459 */
460 public Symbol sym;
462 /** An entry with the same hash code, or sentinel.
463 */
464 private Entry shadowed;
466 /** Next entry in same scope.
467 */
468 public Entry sibling;
470 /** The entry's scope.
471 * scope == null iff this == sentinel
472 * for an entry in an import scope, this is the scope
473 * where the entry came from (i.e. was imported from).
474 */
475 public Scope scope;
477 public Entry(Symbol sym, Entry shadowed, Entry sibling, Scope scope) {
478 this.sym = sym;
479 this.shadowed = shadowed;
480 this.sibling = sibling;
481 this.scope = scope;
482 }
484 /** Return next entry with the same name as this entry, proceeding
485 * outwards if not found in this scope.
486 */
487 public Entry next() {
488 return shadowed;
489 }
491 public Entry next(Filter<Symbol> sf) {
492 if (shadowed.sym == null || sf.accepts(shadowed.sym)) return shadowed;
493 else return shadowed.next(sf);
494 }
496 public Scope getOrigin() {
497 // The origin is only recorded for import scopes. For all
498 // other scope entries, the "enclosing" type is available
499 // from other sources. See Attr.visitSelect and
500 // Attr.visitIdent. Rather than throwing an assertion
501 // error, we return scope which will be the same as origin
502 // in many cases.
503 return scope;
504 }
505 }
507 public static class ImportScope extends Scope {
509 public ImportScope(Symbol owner) {
510 super(owner);
511 }
513 @Override
514 Entry makeEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, Scope origin) {
515 return new ImportEntry(sym, shadowed, sibling, scope, origin);
516 }
518 static class ImportEntry extends Entry {
519 private Scope origin;
521 ImportEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, Scope origin) {
522 super(sym, shadowed, sibling, scope);
523 this.origin = origin;
524 }
526 @Override
527 public Scope getOrigin() { return origin; }
528 }
529 }
531 public static class StarImportScope extends ImportScope implements ScopeListener {
533 public StarImportScope(Symbol owner) {
534 super(owner);
535 }
537 public void importAll (Scope fromScope) {
538 for (Scope.Entry e = fromScope.elems; e != null; e = e.sibling) {
539 if (e.sym.kind == Kinds.TYP && !includes(e.sym))
540 enter(e.sym, fromScope);
541 }
542 // Register to be notified when imported items are removed
543 fromScope.addScopeListener(this);
544 }
546 public void symbolRemoved(Symbol sym, Scope s) {
547 remove(sym);
548 }
549 public void symbolAdded(Symbol sym, Scope s) { }
550 }
552 /** An empty scope, into which you can't place anything. Used for
553 * the scope for a variable initializer.
554 */
555 public static class DelegatedScope extends Scope {
556 Scope delegatee;
557 public static final Entry[] emptyTable = new Entry[0];
559 public DelegatedScope(Scope outer) {
560 super(outer, outer.owner, emptyTable);
561 delegatee = outer;
562 }
563 public Scope dup() {
564 return new DelegatedScope(next);
565 }
566 public Scope dupUnshared() {
567 return new DelegatedScope(next);
568 }
569 public Scope leave() {
570 return next;
571 }
572 public void enter(Symbol sym) {
573 // only anonymous classes could be put here
574 }
575 public void enter(Symbol sym, Scope s) {
576 // only anonymous classes could be put here
577 }
578 public void remove(Symbol sym) {
579 throw new AssertionError(sym);
580 }
581 public Entry lookup(Name name) {
582 return delegatee.lookup(name);
583 }
584 }
586 /** A class scope adds capabilities to keep track of changes in related
587 * class scopes - this allows client to realize whether a class scope
588 * has changed, either directly (because a new member has been added/removed
589 * to this scope) or indirectly (i.e. because a new member has been
590 * added/removed into a supertype scope)
591 */
592 public static class CompoundScope extends Scope implements ScopeListener {
594 public static final Entry[] emptyTable = new Entry[0];
596 private List<Scope> subScopes = List.nil();
597 private int mark = 0;
599 public CompoundScope(Symbol owner) {
600 super(null, owner, emptyTable);
601 }
603 public void addSubScope(Scope that) {
604 if (that != null) {
605 subScopes = subScopes.prepend(that);
606 that.addScopeListener(this);
607 mark++;
608 for (ScopeListener sl : listeners) {
609 sl.symbolAdded(null, this); //propagate upwards in case of nested CompoundScopes
610 }
611 }
612 }
614 public void symbolAdded(Symbol sym, Scope s) {
615 mark++;
616 for (ScopeListener sl : listeners) {
617 sl.symbolAdded(sym, s);
618 }
619 }
621 public void symbolRemoved(Symbol sym, Scope s) {
622 mark++;
623 for (ScopeListener sl : listeners) {
624 sl.symbolRemoved(sym, s);
625 }
626 }
628 public int getMark() {
629 return mark;
630 }
632 @Override
633 public String toString() {
634 StringBuilder buf = new StringBuilder();
635 buf.append("CompoundScope{");
636 String sep = "";
637 for (Scope s : subScopes) {
638 buf.append(sep);
639 buf.append(s);
640 sep = ",";
641 }
642 buf.append("}");
643 return buf.toString();
644 }
646 @Override
647 public Iterable<Symbol> getElements(final Filter<Symbol> sf) {
648 return new Iterable<Symbol>() {
649 public Iterator<Symbol> iterator() {
650 return new CompoundScopeIterator(subScopes) {
651 Iterator<Symbol> nextIterator(Scope s) {
652 return s.getElements(sf).iterator();
653 }
654 };
655 }
656 };
657 }
659 @Override
660 public Iterable<Symbol> getElementsByName(final Name name, 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.getElementsByName(name, sf).iterator();
666 }
667 };
668 }
669 };
670 }
672 abstract class CompoundScopeIterator implements Iterator<Symbol> {
674 private Iterator<Symbol> currentIterator;
675 private List<Scope> scopesToScan;
677 public CompoundScopeIterator(List<Scope> scopesToScan) {
678 this.scopesToScan = scopesToScan;
679 update();
680 }
682 abstract Iterator<Symbol> nextIterator(Scope s);
684 public boolean hasNext() {
685 return currentIterator != null;
686 }
688 public Symbol next() {
689 Symbol sym = currentIterator.next();
690 if (!currentIterator.hasNext()) {
691 update();
692 }
693 return sym;
694 }
696 public void remove() {
697 throw new UnsupportedOperationException();
698 }
700 private void update() {
701 while (scopesToScan.nonEmpty()) {
702 currentIterator = nextIterator(scopesToScan.head);
703 scopesToScan = scopesToScan.tail;
704 if (currentIterator.hasNext()) return;
705 }
706 currentIterator = null;
707 }
708 }
710 @Override
711 public Entry lookup(Name name, Filter<Symbol> sf) {
712 throw new UnsupportedOperationException();
713 }
715 @Override
716 public Scope dup(Symbol newOwner) {
717 throw new UnsupportedOperationException();
718 }
720 @Override
721 public void enter(Symbol sym, Scope s, Scope origin) {
722 throw new UnsupportedOperationException();
723 }
725 @Override
726 public void remove(Symbol sym) {
727 throw new UnsupportedOperationException();
728 }
729 }
731 /** An error scope, for which the owner should be an error symbol. */
732 public static class ErrorScope extends Scope {
733 ErrorScope(Scope next, Symbol errSymbol, Entry[] table) {
734 super(next, /*owner=*/errSymbol, table);
735 }
736 public ErrorScope(Symbol errSymbol) {
737 super(errSymbol);
738 }
739 public Scope dup() {
740 return new ErrorScope(this, owner, table);
741 }
742 public Scope dupUnshared() {
743 return new ErrorScope(this, owner, table.clone());
744 }
745 public Entry lookup(Name name) {
746 Entry e = super.lookup(name);
747 if (e.scope == null)
748 return new Entry(owner, null, null, null);
749 else
750 return e;
751 }
752 }
753 }