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