HashCollisionTest.java revision 3792:d516975e8110
1/* 2 * Copyright (c) 2010, 2016, 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 8131915 27 * @summary Ensure Scope impl can cope with hash collisions 28 * @library /tools/javac/lib 29 * @modules jdk.compiler/com.sun.tools.javac.api 30 * jdk.compiler/com.sun.tools.javac.code:+open 31 * jdk.compiler/com.sun.tools.javac.file 32 * jdk.compiler/com.sun.tools.javac.tree 33 * jdk.compiler/com.sun.tools.javac.util 34 * @build DPrinter HashCollisionTest 35 * @run main HashCollisionTest 36 */ 37 38import java.lang.reflect.*; 39import java.io.*; 40import java.util.function.BiConsumer; 41 42import com.sun.source.util.Trees; 43import com.sun.tools.javac.api.JavacTrees; 44import com.sun.tools.javac.util.*; 45import com.sun.tools.javac.code.*; 46import com.sun.tools.javac.code.Scope.*; 47import com.sun.tools.javac.code.Symbol.*; 48import com.sun.tools.javac.file.JavacFileManager; 49import com.sun.tools.javac.tree.JCTree.JCImport; 50import com.sun.tools.javac.tree.TreeMaker; 51 52import static com.sun.tools.javac.code.Kinds.Kind.*; 53 54public class HashCollisionTest { 55 public static void main(String... args) throws Exception { 56 new HashCollisionTest().run(); 57 } 58 59 void run() throws Exception { 60 // set up basic environment for test 61 Context context = new Context(); 62 JavacFileManager.preRegister(context); // required by ClassReader which is required by Symtab 63 make = TreeMaker.instance(context); 64 names = Names.instance(context); // Name.Table impls tied to an instance of Names 65 symtab = Symtab.instance(context); 66 trees = JavacTrees.instance(context); 67 types = Types.instance(context); 68 69 // determine hashMask for an empty scope 70 Scope emptyScope = WriteableScope.create(symtab.unnamedModule.unnamedPackage); // any owner will do 71 Field field = emptyScope.getClass().getDeclaredField("hashMask"); 72 field.setAccessible(true); 73 scopeHashMask = field.getInt(emptyScope); 74 log("scopeHashMask: " + scopeHashMask); 75 76 // 1. determine the Name.hashCode of "Entry", and therefore the index of 77 // Entry in an empty scope. i.e. name.hashCode() & Scope.hashMask 78 Name entry = names.fromString("Entry"); 79 80 // 2. create names of the form *$Entry until we find a name with a 81 // hashcode which yields the same index as Entry in an empty scope. 82 // Since Name.hashCode is a function of position (and not content) it 83 // should work to create successively longer names until one with the 84 // desired characteristics is found. 85 Name outerName; 86 Name innerName; 87 StringBuilder sb = new StringBuilder("C"); 88 int i = 0; 89 do { 90 sb.append(Integer.toString(i % 10)); 91 innerName = names.fromString(sb + "$Entry"); 92 } while (!clash(entry, innerName) && (++i) < MAX_TRIES); 93 94 if (clash(entry, innerName)) { 95 log("Detected expected hash collision for " + entry + " and " + innerName 96 + " after " + i + " tries"); 97 } else { 98 throw new Exception("No potential collision found after " + i + " tries"); 99 } 100 101 outerName = names.fromString(sb.toString()); 102 103 /* 104 * Now we can set up the scenario. 105 */ 106 107 // 3. Create a nested class named Entry 108 ClassSymbol cc = createClass(names.fromString("C"), symtab.unnamedModule.unnamedPackage); 109 ClassSymbol ce = createClass(entry, cc); 110 111 // 4. Create a package containing a nested class using the name from 2 112 PackageSymbol p = new PackageSymbol(names.fromString("p"), symtab.rootPackage); 113 p.members_field = WriteableScope.create(p); 114 ClassSymbol inner = createClass(innerName, p); 115 // we'll need this later when we "rename" cn 116 ClassSymbol outer = createClass(outerName, p); 117 118 // 5. Create a star-import scope 119 log ("createStarImportScope"); 120 121 PackageSymbol pkg = new PackageSymbol(names.fromString("pkg"), symtab.rootPackage); 122 StarImportScope starImportScope = new StarImportScope(pkg); 123 124 dump("initial", starImportScope); 125 126 // 6. Insert the contents of the package from 4. 127 Scope fromScope = p.members(); 128 ImportFilter typeFilter = new ImportFilter() { 129 @Override 130 public boolean accepts(Scope origin, Symbol sym) { 131 return sym.kind == TYP; 132 } 133 }; 134 BiConsumer<JCImport, CompletionFailure> noCompletionFailure = 135 (imp, cf) -> { throw new IllegalStateException(); }; 136 starImportScope.importAll(types, fromScope, typeFilter, make.Import(null, false), noCompletionFailure); 137 138 dump("imported p", starImportScope); 139 140 // 7. Insert the class from 3. 141 starImportScope.importAll(types, cc.members_field, typeFilter, make.Import(null, false), noCompletionFailure); 142 dump("imported ce", starImportScope); 143 144 /* 145 * Set the trap. 146 */ 147 148 // 8. Rename the nested class to Entry. so that there is a bogus entry in the star-import scope 149 p.members_field.remove(inner); 150 inner.name = entry; 151 inner.owner = outer; 152 outer.members_field.enter(inner); 153 154 // 9. Lookup Entry 155 Symbol found = starImportScope.findFirst(entry); 156 if (found != ce) 157 throw new Exception("correct symbol not found: " + entry + "; found=" + found); 158 159 dump("final", starImportScope); 160 } 161 162 /* 163 * Check for a (probable) hash collision in an empty scope. 164 */ 165 boolean clash(Name n1, Name n2) { 166 log(n1 + " hc:" + n1.hashCode() + " v:" + (n1.hashCode() & scopeHashMask) + ", " + 167 n2 + " hc:" + n2.hashCode() + " v:" + (n2.hashCode() & scopeHashMask)); 168 return (n1.hashCode() & scopeHashMask) == (n2.hashCode() & scopeHashMask); 169 } 170 171 /** 172 * Create a class symbol, init the members scope, and add it to owner's scope. 173 */ 174 ClassSymbol createClass(Name name, Symbol owner) { 175 ClassSymbol sym = new ClassSymbol(0, name, owner); 176 sym.members_field = WriteableScope.create(sym); 177 if (owner != symtab.unnamedModule.unnamedPackage) 178 owner.members().enter(sym); 179 return sym; 180 } 181 182 /** 183 * Dump the contents of a scope to System.err. 184 */ 185 void dump(String label, Scope s) throws Exception { 186 PrintWriter pw = new PrintWriter(System.err); 187 new DPrinter(pw, trees).printScope(label, s); 188 pw.flush(); 189 } 190 191 Object readField(Object scope, String fieldName) throws Exception { 192 Field field = scope.getClass().getDeclaredField(fieldName); 193 field.setAccessible(true); 194 195 return field.get(scope); 196 } 197 198 /** 199 * Write a message to stderr. 200 */ 201 void log(String msg) { 202 System.err.println(msg); 203 } 204 205 int MAX_TRIES = 100; // max tries to find a hash clash before giving up. 206 int scopeHashMask; 207 208 TreeMaker make; 209 Names names; 210 Symtab symtab; 211 Trees trees; 212 Types types; 213} 214