1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/tools/javac/scope/HashCollisionTest.java Thu Dec 02 16:37:23 2010 -0800
1.3 @@ -0,0 +1,251 @@
1.4 +/*
1.5 + * Copyright (c) 2010, 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 + scopeCounter = ScopeCounter.instance(context);
1.54 +
1.55 + // determine hashMask for an empty scope
1.56 + Scope emptyScope = new Scope(symtab.unnamedPackage); // any owner will do
1.57 + Field sHashMask = Scope.class.getDeclaredField("hashMask");
1.58 + sHashMask.setAccessible(true);
1.59 + scopeHashMask = sHashMask.getInt(emptyScope);
1.60 + log("scopeHashMask: " + scopeHashMask);
1.61 +
1.62 + // 1. determine the Name.hashCode of "Entry", and therefore the index of
1.63 + // Entry in an empty scope. i.e. name.hashCode() & Scope.hashMask
1.64 + Name entry = names.fromString("Entry");
1.65 +
1.66 + // 2. create names of the form *$Entry until we find a name with a
1.67 + // hashcode which yields the same index as Entry in an empty scope.
1.68 + // Since Name.hashCode is a function of position (and not content) it
1.69 + // should work to create successively longer names until one with the
1.70 + // desired characteristics is found.
1.71 + Name outerName;
1.72 + Name innerName;
1.73 + StringBuilder sb = new StringBuilder("C");
1.74 + int i = 0;
1.75 + do {
1.76 + sb.append(Integer.toString(i % 10));
1.77 + innerName = names.fromString(sb + "$Entry");
1.78 + } while (!clash(entry, innerName) && (++i) < MAX_TRIES);
1.79 +
1.80 + if (clash(entry, innerName)) {
1.81 + log("Detected expected hash collision for " + entry + " and " + innerName
1.82 + + " after " + i + " tries");
1.83 + } else {
1.84 + throw new Exception("No potential collision found after " + i + " tries");
1.85 + }
1.86 +
1.87 + outerName = names.fromString(sb.toString());
1.88 +
1.89 + /*
1.90 + * Now we can set up the scenario.
1.91 + */
1.92 +
1.93 + // 3. Create a nested class named Entry
1.94 + ClassSymbol cc = createClass(names.fromString("C"), symtab.unnamedPackage);
1.95 + ClassSymbol ce = createClass(entry, cc);
1.96 +
1.97 + // 4. Create a package containing a nested class using the name from 2
1.98 + PackageSymbol p = new PackageSymbol(names.fromString("p"), symtab.rootPackage);
1.99 + p.members_field = new Scope(p);
1.100 + ClassSymbol inner = createClass(innerName, p);
1.101 + // we'll need this later when we "rename" cn
1.102 + ClassSymbol outer = createClass(outerName, p);
1.103 +
1.104 + // 5. Create a star-import scope
1.105 + log ("createStarImportScope");
1.106 +
1.107 + // if StarImportScope exists, use it, otherwise, for testing legacy code,
1.108 + // fall back on ImportScope
1.109 + Scope starImportScope;
1.110 + Method importAll;
1.111 + PackageSymbol pkg = new PackageSymbol(names.fromString("pkg"), symtab.rootPackage);
1.112 + try {
1.113 + Class<?> c = Class.forName("com.sun.tools.javac.code.Scope$StarImportScope");
1.114 + Constructor ctor = c.getDeclaredConstructor(new Class[] { Symbol.class });
1.115 + importAll = c.getDeclaredMethod("importAll", new Class[] { Scope.class });
1.116 + starImportScope = (Scope) ctor.newInstance(new Object[] { pkg });
1.117 + } catch (ClassNotFoundException e) {
1.118 + starImportScope = new ImportScope(pkg);
1.119 + importAll = null;
1.120 + }
1.121 +
1.122 + dump("initial", starImportScope);
1.123 +
1.124 + // 6. Insert the contents of the package from 4.
1.125 + Scope p_members = p.members();
1.126 + if (importAll != null) {
1.127 + importAll.invoke(starImportScope, p_members);
1.128 + } else {
1.129 + Scope fromScope = p_members;
1.130 + Scope toScope = starImportScope;
1.131 + // The following lines are taken from MemberEnter.importAll,
1.132 + // before the use of StarImportScope.importAll.
1.133 + for (Scope.Entry e = fromScope.elems; e != null; e = e.sibling) {
1.134 + if (e.sym.kind == TYP && !toScope.includes(e.sym))
1.135 + toScope.enter(e.sym, fromScope);
1.136 + }
1.137 + }
1.138 +
1.139 + dump("imported p", starImportScope);
1.140 +
1.141 + // 7. Insert the class from 3.
1.142 + starImportScope.enter(ce, cc.members_field);
1.143 + dump("imported ce", starImportScope);
1.144 +
1.145 + /*
1.146 + * Set the trap.
1.147 + */
1.148 +
1.149 + // 8. Rename the nested class to Entry. so that there is a bogus entry in the star-import scope
1.150 + p.members_field.remove(inner);
1.151 + inner.name = entry;
1.152 + inner.owner = outer;
1.153 + outer.members_field.enter(inner);
1.154 +
1.155 + // 9. Lookup Entry
1.156 + Scope.Entry e = starImportScope.lookup(entry);
1.157 + dump("final", starImportScope);
1.158 +
1.159 + if (e.sym == null)
1.160 + throw new Exception("symbol not found: " + entry);
1.161 + }
1.162 +
1.163 + /*
1.164 + * Check for a (probable) hash collision in an empty scope.
1.165 + */
1.166 + boolean clash(Name n1, Name n2) {
1.167 + log(n1 + " hc:" + n1.hashCode() + " v:" + (n1.hashCode() & scopeHashMask) + ", " +
1.168 + n2 + " hc:" + n2.hashCode() + " v:" + (n2.hashCode() & scopeHashMask));
1.169 + return (n1.hashCode() & scopeHashMask) == (n2.hashCode() & scopeHashMask);
1.170 + }
1.171 +
1.172 + /**
1.173 + * Create a class symbol, init the members scope, and add it to owner's scope.
1.174 + */
1.175 + ClassSymbol createClass(Name name, Symbol owner) {
1.176 + ClassSymbol sym = new ClassSymbol(0, name, owner);
1.177 + sym.members_field = new ClassScope(sym, scopeCounter);
1.178 + if (owner != symtab.unnamedPackage)
1.179 + owner.members().enter(sym);
1.180 + return sym;
1.181 + }
1.182 +
1.183 + /**
1.184 + * Dump the contents of a scope to System.err.
1.185 + */
1.186 + void dump(String label, Scope s) throws Exception {
1.187 + dump(label, s, System.err);
1.188 + }
1.189 +
1.190 + /**
1.191 + * Dump the contents of a scope to a stream.
1.192 + */
1.193 + void dump(String label, Scope s, PrintStream out) throws Exception {
1.194 + out.println(label);
1.195 + Field sTable = Scope.class.getDeclaredField("table");
1.196 + sTable.setAccessible(true);
1.197 +
1.198 + out.println("owner:" + s.owner);
1.199 + Scope.Entry[] table = (Scope.Entry[]) sTable.get(s);
1.200 + for (int i = 0; i < table.length; i++) {
1.201 + if (i > 0)
1.202 + out.print(", ");
1.203 + out.print(i + ":" + toString(table[i], table, false));
1.204 + }
1.205 + out.println();
1.206 + }
1.207 +
1.208 + /**
1.209 + * Create a string showing the contents of an entry, using the table
1.210 + * to help identify cross-references to other entries in the table.
1.211 + * @param e the entry to be shown
1.212 + * @param table the table containing the other entries
1.213 + */
1.214 + String toString(Scope.Entry e, Scope.Entry[] table, boolean ref) {
1.215 + if (e == null)
1.216 + return "null";
1.217 + if (e.sym == null)
1.218 + return "sent"; // sentinel
1.219 + if (ref) {
1.220 + int index = indexOf(table, e);
1.221 + if (index != -1)
1.222 + return String.valueOf(index);
1.223 + }
1.224 + return "(" + e.sym.name + ":" + e.sym
1.225 + + ",shdw:" + toString(e.next(), table, true)
1.226 + + ",sibl:" + toString(e.sibling, table, true)
1.227 + + ((e.sym.owner != e.scope.owner)
1.228 + ? (",BOGUS[" + e.sym.owner + "," + e.scope.owner + "]")
1.229 + : "")
1.230 + + ")";
1.231 + }
1.232 +
1.233 + <T> int indexOf(T[] array, T item) {
1.234 + for (int i = 0; i < array.length; i++) {
1.235 + if (array[i] == item)
1.236 + return i;
1.237 + }
1.238 + return -1;
1.239 + }
1.240 +
1.241 + /**
1.242 + * Write a message to stderr.
1.243 + */
1.244 + void log(String msg) {
1.245 + System.err.println(msg);
1.246 + }
1.247 +
1.248 + int MAX_TRIES = 100; // max tries to find a hash clash before giving up.
1.249 + int scopeHashMask;
1.250 +
1.251 + Names names;
1.252 + Symtab symtab;
1.253 + ScopeCounter scopeCounter;
1.254 +}
