Thu, 02 Dec 2010 16:37:23 -0800
7004029: intermittent failures compiling pack200
Summary: remove "bogus" entries from star-import scopes
Reviewed-by: mcimadamore
Contributed-by: per.bothner@oracle.com
1 /*
2 * Copyright (c) 2010, 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.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
24 /*
25 * @test
26 * @bug 7004029
27 * @summary Ensure Scope impl can cope with hash collisions
28 */
30 import java.lang.reflect.*;
31 import java.io.*;
32 import com.sun.tools.javac.util.*;
33 import com.sun.tools.javac.code.*;
34 import com.sun.tools.javac.code.Scope.*;
35 import com.sun.tools.javac.code.Symbol.*;
36 import com.sun.tools.javac.file.JavacFileManager;
37 import static com.sun.tools.javac.code.Kinds.*;
39 public class HashCollisionTest {
40 public static void main(String... args) throws Exception {
41 new HashCollisionTest().run();
42 }
44 void run() throws Exception {
45 // set up basic environment for test
46 Context context = new Context();
47 JavacFileManager.preRegister(context); // required by ClassReader which is required by Symtab
48 names = Names.instance(context); // Name.Table impls tied to an instance of Names
49 symtab = Symtab.instance(context);
50 scopeCounter = ScopeCounter.instance(context);
52 // determine hashMask for an empty scope
53 Scope emptyScope = new Scope(symtab.unnamedPackage); // any owner will do
54 Field sHashMask = Scope.class.getDeclaredField("hashMask");
55 sHashMask.setAccessible(true);
56 scopeHashMask = sHashMask.getInt(emptyScope);
57 log("scopeHashMask: " + scopeHashMask);
59 // 1. determine the Name.hashCode of "Entry", and therefore the index of
60 // Entry in an empty scope. i.e. name.hashCode() & Scope.hashMask
61 Name entry = names.fromString("Entry");
63 // 2. create names of the form *$Entry until we find a name with a
64 // hashcode which yields the same index as Entry in an empty scope.
65 // Since Name.hashCode is a function of position (and not content) it
66 // should work to create successively longer names until one with the
67 // desired characteristics is found.
68 Name outerName;
69 Name innerName;
70 StringBuilder sb = new StringBuilder("C");
71 int i = 0;
72 do {
73 sb.append(Integer.toString(i % 10));
74 innerName = names.fromString(sb + "$Entry");
75 } while (!clash(entry, innerName) && (++i) < MAX_TRIES);
77 if (clash(entry, innerName)) {
78 log("Detected expected hash collision for " + entry + " and " + innerName
79 + " after " + i + " tries");
80 } else {
81 throw new Exception("No potential collision found after " + i + " tries");
82 }
84 outerName = names.fromString(sb.toString());
86 /*
87 * Now we can set up the scenario.
88 */
90 // 3. Create a nested class named Entry
91 ClassSymbol cc = createClass(names.fromString("C"), symtab.unnamedPackage);
92 ClassSymbol ce = createClass(entry, cc);
94 // 4. Create a package containing a nested class using the name from 2
95 PackageSymbol p = new PackageSymbol(names.fromString("p"), symtab.rootPackage);
96 p.members_field = new Scope(p);
97 ClassSymbol inner = createClass(innerName, p);
98 // we'll need this later when we "rename" cn
99 ClassSymbol outer = createClass(outerName, p);
101 // 5. Create a star-import scope
102 log ("createStarImportScope");
104 // if StarImportScope exists, use it, otherwise, for testing legacy code,
105 // fall back on ImportScope
106 Scope starImportScope;
107 Method importAll;
108 PackageSymbol pkg = new PackageSymbol(names.fromString("pkg"), symtab.rootPackage);
109 try {
110 Class<?> c = Class.forName("com.sun.tools.javac.code.Scope$StarImportScope");
111 Constructor ctor = c.getDeclaredConstructor(new Class[] { Symbol.class });
112 importAll = c.getDeclaredMethod("importAll", new Class[] { Scope.class });
113 starImportScope = (Scope) ctor.newInstance(new Object[] { pkg });
114 } catch (ClassNotFoundException e) {
115 starImportScope = new ImportScope(pkg);
116 importAll = null;
117 }
119 dump("initial", starImportScope);
121 // 6. Insert the contents of the package from 4.
122 Scope p_members = p.members();
123 if (importAll != null) {
124 importAll.invoke(starImportScope, p_members);
125 } else {
126 Scope fromScope = p_members;
127 Scope toScope = starImportScope;
128 // The following lines are taken from MemberEnter.importAll,
129 // before the use of StarImportScope.importAll.
130 for (Scope.Entry e = fromScope.elems; e != null; e = e.sibling) {
131 if (e.sym.kind == TYP && !toScope.includes(e.sym))
132 toScope.enter(e.sym, fromScope);
133 }
134 }
136 dump("imported p", starImportScope);
138 // 7. Insert the class from 3.
139 starImportScope.enter(ce, cc.members_field);
140 dump("imported ce", starImportScope);
142 /*
143 * Set the trap.
144 */
146 // 8. Rename the nested class to Entry. so that there is a bogus entry in the star-import scope
147 p.members_field.remove(inner);
148 inner.name = entry;
149 inner.owner = outer;
150 outer.members_field.enter(inner);
152 // 9. Lookup Entry
153 Scope.Entry e = starImportScope.lookup(entry);
154 dump("final", starImportScope);
156 if (e.sym == null)
157 throw new Exception("symbol not found: " + entry);
158 }
160 /*
161 * Check for a (probable) hash collision in an empty scope.
162 */
163 boolean clash(Name n1, Name n2) {
164 log(n1 + " hc:" + n1.hashCode() + " v:" + (n1.hashCode() & scopeHashMask) + ", " +
165 n2 + " hc:" + n2.hashCode() + " v:" + (n2.hashCode() & scopeHashMask));
166 return (n1.hashCode() & scopeHashMask) == (n2.hashCode() & scopeHashMask);
167 }
169 /**
170 * Create a class symbol, init the members scope, and add it to owner's scope.
171 */
172 ClassSymbol createClass(Name name, Symbol owner) {
173 ClassSymbol sym = new ClassSymbol(0, name, owner);
174 sym.members_field = new ClassScope(sym, scopeCounter);
175 if (owner != symtab.unnamedPackage)
176 owner.members().enter(sym);
177 return sym;
178 }
180 /**
181 * Dump the contents of a scope to System.err.
182 */
183 void dump(String label, Scope s) throws Exception {
184 dump(label, s, System.err);
185 }
187 /**
188 * Dump the contents of a scope to a stream.
189 */
190 void dump(String label, Scope s, PrintStream out) throws Exception {
191 out.println(label);
192 Field sTable = Scope.class.getDeclaredField("table");
193 sTable.setAccessible(true);
195 out.println("owner:" + s.owner);
196 Scope.Entry[] table = (Scope.Entry[]) sTable.get(s);
197 for (int i = 0; i < table.length; i++) {
198 if (i > 0)
199 out.print(", ");
200 out.print(i + ":" + toString(table[i], table, false));
201 }
202 out.println();
203 }
205 /**
206 * Create a string showing the contents of an entry, using the table
207 * to help identify cross-references to other entries in the table.
208 * @param e the entry to be shown
209 * @param table the table containing the other entries
210 */
211 String toString(Scope.Entry e, Scope.Entry[] table, boolean ref) {
212 if (e == null)
213 return "null";
214 if (e.sym == null)
215 return "sent"; // sentinel
216 if (ref) {
217 int index = indexOf(table, e);
218 if (index != -1)
219 return String.valueOf(index);
220 }
221 return "(" + e.sym.name + ":" + e.sym
222 + ",shdw:" + toString(e.next(), table, true)
223 + ",sibl:" + toString(e.sibling, table, true)
224 + ((e.sym.owner != e.scope.owner)
225 ? (",BOGUS[" + e.sym.owner + "," + e.scope.owner + "]")
226 : "")
227 + ")";
228 }
230 <T> int indexOf(T[] array, T item) {
231 for (int i = 0; i < array.length; i++) {
232 if (array[i] == item)
233 return i;
234 }
235 return -1;
236 }
238 /**
239 * Write a message to stderr.
240 */
241 void log(String msg) {
242 System.err.println(msg);
243 }
245 int MAX_TRIES = 100; // max tries to find a hash clash before giving up.
246 int scopeHashMask;
248 Names names;
249 Symtab symtab;
250 ScopeCounter scopeCounter;
251 }