766N/A/*
961N/A * Copyright (c) 2010, 2011, Oracle and/or its affiliates. All rights reserved.
766N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
766N/A *
766N/A * This code is free software; you can redistribute it and/or modify it
766N/A * under the terms of the GNU General Public License version 2 only, as
766N/A * published by the Free Software Foundation.
766N/A *
766N/A * This code is distributed in the hope that it will be useful, but WITHOUT
766N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
766N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
766N/A * version 2 for more details (a copy is included in the LICENSE file that
766N/A * accompanied this code).
766N/A *
766N/A * You should have received a copy of the GNU General Public License version
766N/A * 2 along with this work; if not, write to the Free Software Foundation,
766N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
766N/A *
766N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
766N/A * or visit www.oracle.com if you need additional information or have any
766N/A * questions.
766N/A */
766N/A
766N/A/*
766N/A * @test
766N/A * @bug 7004029
766N/A * @summary Ensure Scope impl can cope with hash collisions
766N/A */
766N/A
766N/Aimport java.lang.reflect.*;
766N/Aimport java.io.*;
766N/Aimport com.sun.tools.javac.util.*;
766N/Aimport com.sun.tools.javac.code.*;
766N/Aimport com.sun.tools.javac.code.Scope.*;
766N/Aimport com.sun.tools.javac.code.Symbol.*;
766N/Aimport com.sun.tools.javac.file.JavacFileManager;
766N/Aimport static com.sun.tools.javac.code.Kinds.*;
766N/A
766N/Apublic class HashCollisionTest {
766N/A public static void main(String... args) throws Exception {
766N/A new HashCollisionTest().run();
766N/A }
766N/A
766N/A void run() throws Exception {
766N/A // set up basic environment for test
766N/A Context context = new Context();
766N/A JavacFileManager.preRegister(context); // required by ClassReader which is required by Symtab
766N/A names = Names.instance(context); // Name.Table impls tied to an instance of Names
766N/A symtab = Symtab.instance(context);
766N/A
766N/A // determine hashMask for an empty scope
766N/A Scope emptyScope = new Scope(symtab.unnamedPackage); // any owner will do
766N/A Field sHashMask = Scope.class.getDeclaredField("hashMask");
766N/A sHashMask.setAccessible(true);
766N/A scopeHashMask = sHashMask.getInt(emptyScope);
766N/A log("scopeHashMask: " + scopeHashMask);
766N/A
766N/A // 1. determine the Name.hashCode of "Entry", and therefore the index of
766N/A // Entry in an empty scope. i.e. name.hashCode() & Scope.hashMask
766N/A Name entry = names.fromString("Entry");
766N/A
766N/A // 2. create names of the form *$Entry until we find a name with a
766N/A // hashcode which yields the same index as Entry in an empty scope.
766N/A // Since Name.hashCode is a function of position (and not content) it
766N/A // should work to create successively longer names until one with the
766N/A // desired characteristics is found.
766N/A Name outerName;
766N/A Name innerName;
766N/A StringBuilder sb = new StringBuilder("C");
766N/A int i = 0;
766N/A do {
766N/A sb.append(Integer.toString(i % 10));
766N/A innerName = names.fromString(sb + "$Entry");
766N/A } while (!clash(entry, innerName) && (++i) < MAX_TRIES);
766N/A
766N/A if (clash(entry, innerName)) {
766N/A log("Detected expected hash collision for " + entry + " and " + innerName
766N/A + " after " + i + " tries");
766N/A } else {
766N/A throw new Exception("No potential collision found after " + i + " tries");
766N/A }
766N/A
766N/A outerName = names.fromString(sb.toString());
766N/A
766N/A /*
766N/A * Now we can set up the scenario.
766N/A */
766N/A
766N/A // 3. Create a nested class named Entry
766N/A ClassSymbol cc = createClass(names.fromString("C"), symtab.unnamedPackage);
766N/A ClassSymbol ce = createClass(entry, cc);
766N/A
766N/A // 4. Create a package containing a nested class using the name from 2
766N/A PackageSymbol p = new PackageSymbol(names.fromString("p"), symtab.rootPackage);
766N/A p.members_field = new Scope(p);
766N/A ClassSymbol inner = createClass(innerName, p);
766N/A // we'll need this later when we "rename" cn
766N/A ClassSymbol outer = createClass(outerName, p);
766N/A
766N/A // 5. Create a star-import scope
766N/A log ("createStarImportScope");
766N/A
766N/A // if StarImportScope exists, use it, otherwise, for testing legacy code,
766N/A // fall back on ImportScope
766N/A Scope starImportScope;
766N/A Method importAll;
766N/A PackageSymbol pkg = new PackageSymbol(names.fromString("pkg"), symtab.rootPackage);
766N/A try {
766N/A Class<?> c = Class.forName("com.sun.tools.javac.code.Scope$StarImportScope");
766N/A Constructor ctor = c.getDeclaredConstructor(new Class[] { Symbol.class });
766N/A importAll = c.getDeclaredMethod("importAll", new Class[] { Scope.class });
766N/A starImportScope = (Scope) ctor.newInstance(new Object[] { pkg });
766N/A } catch (ClassNotFoundException e) {
766N/A starImportScope = new ImportScope(pkg);
766N/A importAll = null;
766N/A }
766N/A
766N/A dump("initial", starImportScope);
766N/A
766N/A // 6. Insert the contents of the package from 4.
766N/A Scope p_members = p.members();
766N/A if (importAll != null) {
766N/A importAll.invoke(starImportScope, p_members);
766N/A } else {
766N/A Scope fromScope = p_members;
766N/A Scope toScope = starImportScope;
766N/A // The following lines are taken from MemberEnter.importAll,
766N/A // before the use of StarImportScope.importAll.
766N/A for (Scope.Entry e = fromScope.elems; e != null; e = e.sibling) {
766N/A if (e.sym.kind == TYP && !toScope.includes(e.sym))
766N/A toScope.enter(e.sym, fromScope);
766N/A }
766N/A }
766N/A
766N/A dump("imported p", starImportScope);
766N/A
766N/A // 7. Insert the class from 3.
766N/A starImportScope.enter(ce, cc.members_field);
766N/A dump("imported ce", starImportScope);
766N/A
766N/A /*
766N/A * Set the trap.
766N/A */
766N/A
766N/A // 8. Rename the nested class to Entry. so that there is a bogus entry in the star-import scope
766N/A p.members_field.remove(inner);
766N/A inner.name = entry;
766N/A inner.owner = outer;
766N/A outer.members_field.enter(inner);
766N/A
766N/A // 9. Lookup Entry
766N/A Scope.Entry e = starImportScope.lookup(entry);
766N/A dump("final", starImportScope);
766N/A
766N/A if (e.sym == null)
766N/A throw new Exception("symbol not found: " + entry);
766N/A }
766N/A
766N/A /*
766N/A * Check for a (probable) hash collision in an empty scope.
766N/A */
766N/A boolean clash(Name n1, Name n2) {
766N/A log(n1 + " hc:" + n1.hashCode() + " v:" + (n1.hashCode() & scopeHashMask) + ", " +
766N/A n2 + " hc:" + n2.hashCode() + " v:" + (n2.hashCode() & scopeHashMask));
766N/A return (n1.hashCode() & scopeHashMask) == (n2.hashCode() & scopeHashMask);
766N/A }
766N/A
766N/A /**
766N/A * Create a class symbol, init the members scope, and add it to owner's scope.
766N/A */
766N/A ClassSymbol createClass(Name name, Symbol owner) {
766N/A ClassSymbol sym = new ClassSymbol(0, name, owner);
857N/A sym.members_field = new Scope(sym);
766N/A if (owner != symtab.unnamedPackage)
766N/A owner.members().enter(sym);
766N/A return sym;
766N/A }
766N/A
766N/A /**
766N/A * Dump the contents of a scope to System.err.
766N/A */
766N/A void dump(String label, Scope s) throws Exception {
766N/A dump(label, s, System.err);
766N/A }
766N/A
766N/A /**
766N/A * Dump the contents of a scope to a stream.
766N/A */
766N/A void dump(String label, Scope s, PrintStream out) throws Exception {
766N/A out.println(label);
766N/A Field sTable = Scope.class.getDeclaredField("table");
766N/A sTable.setAccessible(true);
766N/A
766N/A out.println("owner:" + s.owner);
766N/A Scope.Entry[] table = (Scope.Entry[]) sTable.get(s);
766N/A for (int i = 0; i < table.length; i++) {
766N/A if (i > 0)
766N/A out.print(", ");
766N/A out.print(i + ":" + toString(table[i], table, false));
766N/A }
766N/A out.println();
766N/A }
766N/A
766N/A /**
766N/A * Create a string showing the contents of an entry, using the table
766N/A * to help identify cross-references to other entries in the table.
766N/A * @param e the entry to be shown
766N/A * @param table the table containing the other entries
766N/A */
766N/A String toString(Scope.Entry e, Scope.Entry[] table, boolean ref) {
766N/A if (e == null)
766N/A return "null";
766N/A if (e.sym == null)
766N/A return "sent"; // sentinel
766N/A if (ref) {
766N/A int index = indexOf(table, e);
766N/A if (index != -1)
766N/A return String.valueOf(index);
766N/A }
766N/A return "(" + e.sym.name + ":" + e.sym
766N/A + ",shdw:" + toString(e.next(), table, true)
766N/A + ",sibl:" + toString(e.sibling, table, true)
766N/A + ((e.sym.owner != e.scope.owner)
766N/A ? (",BOGUS[" + e.sym.owner + "," + e.scope.owner + "]")
766N/A : "")
766N/A + ")";
766N/A }
766N/A
766N/A <T> int indexOf(T[] array, T item) {
766N/A for (int i = 0; i < array.length; i++) {
766N/A if (array[i] == item)
766N/A return i;
766N/A }
766N/A return -1;
766N/A }
766N/A
766N/A /**
766N/A * Write a message to stderr.
766N/A */
766N/A void log(String msg) {
766N/A System.err.println(msg);
766N/A }
766N/A
766N/A int MAX_TRIES = 100; // max tries to find a hash clash before giving up.
766N/A int scopeHashMask;
766N/A
766N/A Names names;
766N/A Symtab symtab;
766N/A}