1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/test/tools/javac/scope/HashCollisionTest.java Wed Apr 27 01:34:52 2016 +0800 1.3 @@ -0,0 +1,249 @@ 1.4 +/* 1.5 + * Copyright (c) 2010, 2011, Oracle and/or its affiliates. All rights reserved. 1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 1.7 + * 1.8 + * This code is free software; you can redistribute it and/or modify it 1.9 + * under the terms of the GNU General Public License version 2 only, as 1.10 + * published by the Free Software Foundation. 1.11 + * 1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT 1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1.15 + * version 2 for more details (a copy is included in the LICENSE file that 1.16 + * accompanied this code). 1.17 + * 1.18 + * You should have received a copy of the GNU General Public License version 1.19 + * 2 along with this work; if not, write to the Free Software Foundation, 1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1.21 + * 1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 1.23 + * or visit www.oracle.com if you need additional information or have any 1.24 + * questions. 1.25 + */ 1.26 + 1.27 +/* 1.28 + * @test 1.29 + * @bug 7004029 1.30 + * @summary Ensure Scope impl can cope with hash collisions 1.31 + */ 1.32 + 1.33 +import java.lang.reflect.*; 1.34 +import java.io.*; 1.35 +import com.sun.tools.javac.util.*; 1.36 +import com.sun.tools.javac.code.*; 1.37 +import com.sun.tools.javac.code.Scope.*; 1.38 +import com.sun.tools.javac.code.Symbol.*; 1.39 +import com.sun.tools.javac.file.JavacFileManager; 1.40 +import static com.sun.tools.javac.code.Kinds.*; 1.41 + 1.42 +public class HashCollisionTest { 1.43 + public static void main(String... args) throws Exception { 1.44 + new HashCollisionTest().run(); 1.45 + } 1.46 + 1.47 + void run() throws Exception { 1.48 + // set up basic environment for test 1.49 + Context context = new Context(); 1.50 + JavacFileManager.preRegister(context); // required by ClassReader which is required by Symtab 1.51 + names = Names.instance(context); // Name.Table impls tied to an instance of Names 1.52 + symtab = Symtab.instance(context); 1.53 + 1.54 + // determine hashMask for an empty scope 1.55 + Scope emptyScope = new Scope(symtab.unnamedPackage); // any owner will do 1.56 + Field sHashMask = Scope.class.getDeclaredField("hashMask"); 1.57 + sHashMask.setAccessible(true); 1.58 + scopeHashMask = sHashMask.getInt(emptyScope); 1.59 + log("scopeHashMask: " + scopeHashMask); 1.60 + 1.61 + // 1. determine the Name.hashCode of "Entry", and therefore the index of 1.62 + // Entry in an empty scope. i.e. name.hashCode() & Scope.hashMask 1.63 + Name entry = names.fromString("Entry"); 1.64 + 1.65 + // 2. create names of the form *$Entry until we find a name with a 1.66 + // hashcode which yields the same index as Entry in an empty scope. 1.67 + // Since Name.hashCode is a function of position (and not content) it 1.68 + // should work to create successively longer names until one with the 1.69 + // desired characteristics is found. 1.70 + Name outerName; 1.71 + Name innerName; 1.72 + StringBuilder sb = new StringBuilder("C"); 1.73 + int i = 0; 1.74 + do { 1.75 + sb.append(Integer.toString(i % 10)); 1.76 + innerName = names.fromString(sb + "$Entry"); 1.77 + } while (!clash(entry, innerName) && (++i) < MAX_TRIES); 1.78 + 1.79 + if (clash(entry, innerName)) { 1.80 + log("Detected expected hash collision for " + entry + " and " + innerName 1.81 + + " after " + i + " tries"); 1.82 + } else { 1.83 + throw new Exception("No potential collision found after " + i + " tries"); 1.84 + } 1.85 + 1.86 + outerName = names.fromString(sb.toString()); 1.87 + 1.88 + /* 1.89 + * Now we can set up the scenario. 1.90 + */ 1.91 + 1.92 + // 3. Create a nested class named Entry 1.93 + ClassSymbol cc = createClass(names.fromString("C"), symtab.unnamedPackage); 1.94 + ClassSymbol ce = createClass(entry, cc); 1.95 + 1.96 + // 4. Create a package containing a nested class using the name from 2 1.97 + PackageSymbol p = new PackageSymbol(names.fromString("p"), symtab.rootPackage); 1.98 + p.members_field = new Scope(p); 1.99 + ClassSymbol inner = createClass(innerName, p); 1.100 + // we'll need this later when we "rename" cn 1.101 + ClassSymbol outer = createClass(outerName, p); 1.102 + 1.103 + // 5. Create a star-import scope 1.104 + log ("createStarImportScope"); 1.105 + 1.106 + // if StarImportScope exists, use it, otherwise, for testing legacy code, 1.107 + // fall back on ImportScope 1.108 + Scope starImportScope; 1.109 + Method importAll; 1.110 + PackageSymbol pkg = new PackageSymbol(names.fromString("pkg"), symtab.rootPackage); 1.111 + try { 1.112 + Class<?> c = Class.forName("com.sun.tools.javac.code.Scope$StarImportScope"); 1.113 + Constructor ctor = c.getDeclaredConstructor(new Class[] { Symbol.class }); 1.114 + importAll = c.getDeclaredMethod("importAll", new Class[] { Scope.class }); 1.115 + starImportScope = (Scope) ctor.newInstance(new Object[] { pkg }); 1.116 + } catch (ClassNotFoundException e) { 1.117 + starImportScope = new ImportScope(pkg); 1.118 + importAll = null; 1.119 + } 1.120 + 1.121 + dump("initial", starImportScope); 1.122 + 1.123 + // 6. Insert the contents of the package from 4. 1.124 + Scope p_members = p.members(); 1.125 + if (importAll != null) { 1.126 + importAll.invoke(starImportScope, p_members); 1.127 + } else { 1.128 + Scope fromScope = p_members; 1.129 + Scope toScope = starImportScope; 1.130 + // The following lines are taken from MemberEnter.importAll, 1.131 + // before the use of StarImportScope.importAll. 1.132 + for (Scope.Entry e = fromScope.elems; e != null; e = e.sibling) { 1.133 + if (e.sym.kind == TYP && !toScope.includes(e.sym)) 1.134 + toScope.enter(e.sym, fromScope); 1.135 + } 1.136 + } 1.137 + 1.138 + dump("imported p", starImportScope); 1.139 + 1.140 + // 7. Insert the class from 3. 1.141 + starImportScope.enter(ce, cc.members_field); 1.142 + dump("imported ce", starImportScope); 1.143 + 1.144 + /* 1.145 + * Set the trap. 1.146 + */ 1.147 + 1.148 + // 8. Rename the nested class to Entry. so that there is a bogus entry in the star-import scope 1.149 + p.members_field.remove(inner); 1.150 + inner.name = entry; 1.151 + inner.owner = outer; 1.152 + outer.members_field.enter(inner); 1.153 + 1.154 + // 9. Lookup Entry 1.155 + Scope.Entry e = starImportScope.lookup(entry); 1.156 + dump("final", starImportScope); 1.157 + 1.158 + if (e.sym == null) 1.159 + throw new Exception("symbol not found: " + entry); 1.160 + } 1.161 + 1.162 + /* 1.163 + * Check for a (probable) hash collision in an empty scope. 1.164 + */ 1.165 + boolean clash(Name n1, Name n2) { 1.166 + log(n1 + " hc:" + n1.hashCode() + " v:" + (n1.hashCode() & scopeHashMask) + ", " + 1.167 + n2 + " hc:" + n2.hashCode() + " v:" + (n2.hashCode() & scopeHashMask)); 1.168 + return (n1.hashCode() & scopeHashMask) == (n2.hashCode() & scopeHashMask); 1.169 + } 1.170 + 1.171 + /** 1.172 + * Create a class symbol, init the members scope, and add it to owner's scope. 1.173 + */ 1.174 + ClassSymbol createClass(Name name, Symbol owner) { 1.175 + ClassSymbol sym = new ClassSymbol(0, name, owner); 1.176 + sym.members_field = new Scope(sym); 1.177 + if (owner != symtab.unnamedPackage) 1.178 + owner.members().enter(sym); 1.179 + return sym; 1.180 + } 1.181 + 1.182 + /** 1.183 + * Dump the contents of a scope to System.err. 1.184 + */ 1.185 + void dump(String label, Scope s) throws Exception { 1.186 + dump(label, s, System.err); 1.187 + } 1.188 + 1.189 + /** 1.190 + * Dump the contents of a scope to a stream. 1.191 + */ 1.192 + void dump(String label, Scope s, PrintStream out) throws Exception { 1.193 + out.println(label); 1.194 + Field sTable = Scope.class.getDeclaredField("table"); 1.195 + sTable.setAccessible(true); 1.196 + 1.197 + out.println("owner:" + s.owner); 1.198 + Scope.Entry[] table = (Scope.Entry[]) sTable.get(s); 1.199 + for (int i = 0; i < table.length; i++) { 1.200 + if (i > 0) 1.201 + out.print(", "); 1.202 + out.print(i + ":" + toString(table[i], table, false)); 1.203 + } 1.204 + out.println(); 1.205 + } 1.206 + 1.207 + /** 1.208 + * Create a string showing the contents of an entry, using the table 1.209 + * to help identify cross-references to other entries in the table. 1.210 + * @param e the entry to be shown 1.211 + * @param table the table containing the other entries 1.212 + */ 1.213 + String toString(Scope.Entry e, Scope.Entry[] table, boolean ref) { 1.214 + if (e == null) 1.215 + return "null"; 1.216 + if (e.sym == null) 1.217 + return "sent"; // sentinel 1.218 + if (ref) { 1.219 + int index = indexOf(table, e); 1.220 + if (index != -1) 1.221 + return String.valueOf(index); 1.222 + } 1.223 + return "(" + e.sym.name + ":" + e.sym 1.224 + + ",shdw:" + toString(e.next(), table, true) 1.225 + + ",sibl:" + toString(e.sibling, table, true) 1.226 + + ((e.sym.owner != e.scope.owner) 1.227 + ? (",BOGUS[" + e.sym.owner + "," + e.scope.owner + "]") 1.228 + : "") 1.229 + + ")"; 1.230 + } 1.231 + 1.232 + <T> int indexOf(T[] array, T item) { 1.233 + for (int i = 0; i < array.length; i++) { 1.234 + if (array[i] == item) 1.235 + return i; 1.236 + } 1.237 + return -1; 1.238 + } 1.239 + 1.240 + /** 1.241 + * Write a message to stderr. 1.242 + */ 1.243 + void log(String msg) { 1.244 + System.err.println(msg); 1.245 + } 1.246 + 1.247 + int MAX_TRIES = 100; // max tries to find a hash clash before giving up. 1.248 + int scopeHashMask; 1.249 + 1.250 + Names names; 1.251 + Symtab symtab; 1.252 +}