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 */ 23 24 /* 25 * @test 26 * @bug 7004029 27 * @summary Ensure Scope impl can cope with hash collisions 28 */ 29 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.*; 38 39 public class HashCollisionTest { 40 public static void main(String... args) throws Exception { 41 new HashCollisionTest().run(); 42 } 43 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 51 // determine hashMask for an empty scope 52 Scope emptyScope = new Scope(symtab.unnamedPackage); // any owner will do 53 Field sHashMask = Scope.class.getDeclaredField("hashMask"); 54 sHashMask.setAccessible(true); 55 scopeHashMask = sHashMask.getInt(emptyScope); 56 log("scopeHashMask: " + scopeHashMask); 57 58 // 1. determine the Name.hashCode of "Entry", and therefore the index of 59 // Entry in an empty scope. i.e. name.hashCode() & Scope.hashMask 60 Name entry = names.fromString("Entry"); 61 62 // 2. create names of the form *$Entry until we find a name with a 63 // hashcode which yields the same index as Entry in an empty scope. 64 // Since Name.hashCode is a function of position (and not content) it 65 // should work to create successively longer names until one with the 66 // desired characteristics is found. 67 Name outerName; 68 Name innerName; 69 StringBuilder sb = new StringBuilder("C"); 70 int i = 0; 71 do { 72 sb.append(Integer.toString(i % 10)); 73 innerName = names.fromString(sb + "$Entry"); 74 } while (!clash(entry, innerName) && (++i) < MAX_TRIES); 75 76 if (clash(entry, innerName)) { 77 log("Detected expected hash collision for " + entry + " and " + innerName 78 + " after " + i + " tries"); 79 } else { 80 throw new Exception("No potential collision found after " + i + " tries"); 81 } 82 83 outerName = names.fromString(sb.toString()); 84 85 /* 86 * Now we can set up the scenario. 87 */ 88 89 // 3. Create a nested class named Entry 90 ClassSymbol cc = createClass(names.fromString("C"), symtab.unnamedPackage); 91 ClassSymbol ce = createClass(entry, cc); 92 93 // 4. Create a package containing a nested class using the name from 2 94 PackageSymbol p = new PackageSymbol(names.fromString("p"), symtab.rootPackage); 95 p.members_field = new Scope(p); 96 ClassSymbol inner = createClass(innerName, p); 97 // we'll need this later when we "rename" cn 98 ClassSymbol outer = createClass(outerName, p); 99 100 // 5. Create a star-import scope 101 log ("createStarImportScope"); 102 103 // if StarImportScope exists, use it, otherwise, for testing legacy code, 104 // fall back on ImportScope 105 Scope starImportScope; 106 Method importAll; 107 PackageSymbol pkg = new PackageSymbol(names.fromString("pkg"), symtab.rootPackage); 108 try { 109 Class<?> c = Class.forName("com.sun.tools.javac.code.Scope$StarImportScope"); 110 Constructor ctor = c.getDeclaredConstructor(new Class[] { Symbol.class }); 111 importAll = c.getDeclaredMethod("importAll", new Class[] { Scope.class }); 112 starImportScope = (Scope) ctor.newInstance(new Object[] { pkg }); 113 } catch (ClassNotFoundException e) { 114 starImportScope = new ImportScope(pkg); 115 importAll = null; 116 } 117 118 dump("initial", starImportScope); 119 120 // 6. Insert the contents of the package from 4. 121 Scope p_members = p.members(); 122 if (importAll != null) { 123 importAll.invoke(starImportScope, p_members); 124 } else { 125 Scope fromScope = p_members; 126 Scope toScope = starImportScope; 127 // The following lines are taken from MemberEnter.importAll, 128 // before the use of StarImportScope.importAll. 129 for (Scope.Entry e = fromScope.elems; e != null; e = e.sibling) { 130 if (e.sym.kind == TYP && !toScope.includes(e.sym)) 131 toScope.enter(e.sym, fromScope); 132 } 133 } 134 135 dump("imported p", starImportScope); 136 137 // 7. Insert the class from 3. 138 starImportScope.enter(ce, cc.members_field); 139 dump("imported ce", starImportScope); 140 141 /* 142 * Set the trap. 143 */ 144 145 // 8. Rename the nested class to Entry. so that there is a bogus entry in the star-import scope 146 p.members_field.remove(inner); 147 inner.name = entry; 148 inner.owner = outer; 149 outer.members_field.enter(inner); 150 151 // 9. Lookup Entry 152 Scope.Entry e = starImportScope.lookup(entry); 153 dump("final", starImportScope); 154 155 if (e.sym == null) 156 throw new Exception("symbol not found: " + entry); 157 } 158 159 /* 160 * Check for a (probable) hash collision in an empty scope. 161 */ 162 boolean clash(Name n1, Name n2) { 163 log(n1 + " hc:" + n1.hashCode() + " v:" + (n1.hashCode() & scopeHashMask) + ", " + 164 n2 + " hc:" + n2.hashCode() + " v:" + (n2.hashCode() & scopeHashMask)); 165 return (n1.hashCode() & scopeHashMask) == (n2.hashCode() & scopeHashMask); 166 } 167 168 /** 169 * Create a class symbol, init the members scope, and add it to owner's scope. 170 */ 171 ClassSymbol createClass(Name name, Symbol owner) { 172 ClassSymbol sym = new ClassSymbol(0, name, owner); 173 sym.members_field = new Scope(sym); 174 if (owner != symtab.unnamedPackage) 175 owner.members().enter(sym); 176 return sym; 177 } 178 179 /** 180 * Dump the contents of a scope to System.err. 181 */ 182 void dump(String label, Scope s) throws Exception { 183 dump(label, s, System.err); 184 } 185 186 /** 187 * Dump the contents of a scope to a stream. 188 */ 189 void dump(String label, Scope s, PrintStream out) throws Exception { 190 out.println(label); 191 Field sTable = Scope.class.getDeclaredField("table"); 192 sTable.setAccessible(true); 193 194 out.println("owner:" + s.owner); 195 Scope.Entry[] table = (Scope.Entry[]) sTable.get(s); 196 for (int i = 0; i < table.length; i++) { 197 if (i > 0) 198 out.print(", "); 199 out.print(i + ":" + toString(table[i], table, false)); 200 } 201 out.println(); 202 } 203 204 /** 205 * Create a string showing the contents of an entry, using the table 206 * to help identify cross-references to other entries in the table. 207 * @param e the entry to be shown 208 * @param table the table containing the other entries 209 */ 210 String toString(Scope.Entry e, Scope.Entry[] table, boolean ref) { 211 if (e == null) 212 return "null"; 213 if (e.sym == null) 214 return "sent"; // sentinel 215 if (ref) { 216 int index = indexOf(table, e); 217 if (index != -1) 218 return String.valueOf(index); 219 } 220 return "(" + e.sym.name + ":" + e.sym 221 + ",shdw:" + toString(e.next(), table, true) 222 + ",sibl:" + toString(e.sibling, table, true) 223 + ((e.sym.owner != e.scope.owner) 224 ? (",BOGUS[" + e.sym.owner + "," + e.scope.owner + "]") 225 : "") 226 + ")"; 227 } 228 229 <T> int indexOf(T[] array, T item) { 230 for (int i = 0; i < array.length; i++) { 231 if (array[i] == item) 232 return i; 233 } 234 return -1; 235 } 236 237 /** 238 * Write a message to stderr. 239 */ 240 void log(String msg) { 241 System.err.println(msg); 242 } 243 244 int MAX_TRIES = 100; // max tries to find a hash clash before giving up. 245 int scopeHashMask; 246 247 Names names; 248 Symtab symtab; 249 }