1 /*

     2  * Copyright (c) 2010, 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

    27  * @summary Ensure Scope impl can cope with hash collisions

    28  */

    29 

    30 import java.lang.reflect.*;

    31 import java.io.*;

    32 import com.sun.tools.javac.util.*;

    33 import com.sun.tools.javac.code.*;

    34 import com.sun.tools.javac.code.Scope.*;

    35 import com.sun.tools.javac.code.Symbol.*;

    36 import com.sun.tools.javac.file.JavacFileManager;

    37 import static com.sun.tools.javac.code.Kinds.*;

    38 

    39 public class HashCollisionTest {

    40     public static void main(String... args) throws Exception {

    41         new HashCollisionTest().run();

    42     }

    43 

    44     void run() throws Exception {

    45         // set up basic environment for test

    46         Context context = new Context();

    47         JavacFileManager.preRegister(context); // required by ClassReader which is required by Symtab

    48         names = Names.instance(context);       // Name.Table impls tied to an instance of Names

    49         symtab = Symtab.instance(context);

    50         scopeCounter = ScopeCounter.instance(context);

    51 

    52         // determine hashMask for an empty scope

    53         Scope emptyScope = new Scope(symtab.unnamedPackage); // any owner will do

    54         Field sHashMask = Scope.class.getDeclaredField("hashMask");

    55         sHashMask.setAccessible(true);

    56         scopeHashMask = sHashMask.getInt(emptyScope);

    57         log("scopeHashMask: " + scopeHashMask);

    58 

    59         // 1. determine the Name.hashCode of "Entry", and therefore the index of

    60         // Entry in an empty scope.  i.e. name.hashCode() & Scope.hashMask

    61         Name entry = names.fromString("Entry");

    62 

    63         // 2. create names of the form *$Entry until we find a name with a

    64         // hashcode which yields the same index as Entry in an empty scope.

    65         // Since Name.hashCode is a function of position (and not content) it

    66         // should work to create successively longer names until one with the

    67         // desired characteristics is found.

    68         Name outerName;

    69         Name innerName;

    70         StringBuilder sb = new StringBuilder("C");

    71         int i = 0;

    72         do {

    73             sb.append(Integer.toString(i % 10));

    74             innerName = names.fromString(sb + "$Entry");

    75         } while (!clash(entry, innerName) && (++i) < MAX_TRIES);

    76 

    77         if (clash(entry, innerName)) {

    78             log("Detected expected hash collision for " + entry + " and " + innerName

    79                     + " after " + i + " tries");

    80         } else {

    81             throw new Exception("No potential collision found after " + i + " tries");

    82         }

    83 

    84         outerName = names.fromString(sb.toString());

    85 

    86         /*

    87          * Now we can set up the scenario.

    88          */

    89 

    90         // 3. Create a nested class named Entry

    91         ClassSymbol cc = createClass(names.fromString("C"), symtab.unnamedPackage);

    92         ClassSymbol ce = createClass(entry, cc);

    93 

    94         // 4. Create a package containing a nested class using the name from 2

    95         PackageSymbol p = new PackageSymbol(names.fromString("p"), symtab.rootPackage);

    96         p.members_field = new Scope(p);

    97         ClassSymbol inner = createClass(innerName, p);

    98         // we'll need this later when we "rename" cn

    99         ClassSymbol outer = createClass(outerName, p);

   100 

   101         // 5. Create a star-import scope

   102         log ("createStarImportScope");

   103 

   104         // if StarImportScope exists, use it, otherwise, for testing legacy code,

   105         // fall back on ImportScope

   106         Scope starImportScope;

   107         Method importAll;

   108         PackageSymbol pkg = new PackageSymbol(names.fromString("pkg"), symtab.rootPackage);

   109         try {

   110             Class<?> c = Class.forName("com.sun.tools.javac.code.Scope$StarImportScope");

   111             Constructor ctor = c.getDeclaredConstructor(new Class[] { Symbol.class });

   112             importAll = c.getDeclaredMethod("importAll", new Class[] { Scope.class });

   113             starImportScope = (Scope) ctor.newInstance(new Object[] { pkg });

   114         } catch (ClassNotFoundException e) {

   115             starImportScope = new ImportScope(pkg);

   116             importAll = null;

   117         }

   118 

   119         dump("initial", starImportScope);

   120 

   121         // 6. Insert the contents of the package from 4.

   122         Scope p_members = p.members();

   123         if (importAll != null) {

   124             importAll.invoke(starImportScope, p_members);

   125         } else {

   126             Scope fromScope = p_members;

   127             Scope toScope = starImportScope;

   128             // The following lines are taken from MemberEnter.importAll,

   129             // before the use of StarImportScope.importAll.

   130             for (Scope.Entry e = fromScope.elems; e != null; e = e.sibling) {

   131                 if (e.sym.kind == TYP && !toScope.includes(e.sym))

   132                     toScope.enter(e.sym, fromScope);

   133             }

   134         }

   135 

   136         dump("imported p", starImportScope);

   137 

   138         // 7. Insert the class from 3.

   139         starImportScope.enter(ce, cc.members_field);

   140         dump("imported ce", starImportScope);

   141 

   142         /*

   143          * Set the trap.

   144          */

   145 

   146         // 8. Rename the nested class to Entry. so that there is a bogus entry in the star-import scope

   147         p.members_field.remove(inner);

   148         inner.name = entry;

   149         inner.owner = outer;

   150         outer.members_field.enter(inner);

   151 

   152         // 9. Lookup Entry

   153         Scope.Entry e = starImportScope.lookup(entry);

   154         dump("final", starImportScope);

   155 

   156         if (e.sym == null)

   157             throw new Exception("symbol not found: " + entry);

   158     }

   159 

   160     /*

   161      * Check for a (probable) hash collision in an empty scope.

   162      */

   163     boolean clash(Name n1, Name n2) {

   164         log(n1 + " hc:" + n1.hashCode() + " v:" + (n1.hashCode() & scopeHashMask) + ", " +

   165                 n2 + " hc:" + n2.hashCode() + " v:" + (n2.hashCode() & scopeHashMask));

   166         return (n1.hashCode() & scopeHashMask) == (n2.hashCode() & scopeHashMask);

   167     }

   168 

   169     /**

   170      * Create a class symbol, init the members scope, and add it to owner's scope.

   171      */

   172     ClassSymbol createClass(Name name, Symbol owner) {

   173         ClassSymbol sym = new ClassSymbol(0, name, owner);

   174         sym.members_field = new ClassScope(sym, scopeCounter);

   175         if (owner != symtab.unnamedPackage)

   176             owner.members().enter(sym);

   177         return sym;

   178     }

   179 

   180     /**

   181      * Dump the contents of a scope to System.err.

   182      */

   183     void dump(String label, Scope s) throws Exception {

   184         dump(label, s, System.err);

   185     }

   186 

   187     /**

   188      * Dump the contents of a scope to a stream.

   189      */

   190     void dump(String label, Scope s, PrintStream out) throws Exception {

   191         out.println(label);

   192         Field sTable = Scope.class.getDeclaredField("table");

   193         sTable.setAccessible(true);

   194 

   195         out.println("owner:" + s.owner);

   196         Scope.Entry[] table = (Scope.Entry[]) sTable.get(s);

   197         for (int i = 0; i < table.length; i++) {

   198             if (i > 0)

   199                 out.print(", ");

   200             out.print(i + ":" + toString(table[i], table, false));

   201         }

   202         out.println();

   203     }

   204 

   205     /**

   206      * Create a string showing the contents of an entry, using the table

   207      * to help identify cross-references to other entries in the table.

   208      * @param e the entry to be shown

   209      * @param table the table containing the other entries

   210      */

   211     String toString(Scope.Entry e, Scope.Entry[] table, boolean ref) {

   212         if (e == null)

   213             return "null";

   214         if (e.sym == null)

   215             return "sent"; // sentinel

   216         if (ref) {

   217             int index = indexOf(table, e);

   218             if (index != -1)

   219                 return String.valueOf(index);

   220         }

   221         return "(" + e.sym.name + ":" + e.sym

   222                 + ",shdw:" + toString(e.next(), table, true)

   223                 + ",sibl:" + toString(e.sibling, table, true)

   224                 + ((e.sym.owner != e.scope.owner)

   225                     ? (",BOGUS[" + e.sym.owner + "," + e.scope.owner + "]")

   226                     : "")

   227                 + ")";

   228     }

   229 

   230     <T> int indexOf(T[] array, T item) {

   231         for (int i = 0; i < array.length; i++) {

   232             if (array[i] == item)

   233                 return i;

   234         }

   235         return -1;

   236     }

   237 

   238     /**

   239      * Write a message to stderr.

   240      */

   241     void log(String msg) {

   242         System.err.println(msg);

   243     }

   244 

   245     int MAX_TRIES = 100; // max tries to find a hash clash before giving up.

   246     int scopeHashMask;

   247 

   248     Names names;

   249     Symtab symtab;

   250     ScopeCounter scopeCounter;

   251 }