1 /*

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

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

    28  * @library /tools/javac/lib

    29  * @modules jdk.compiler/com.sun.tools.javac.api

    30  *          jdk.compiler/com.sun.tools.javac.code:+open

    31  *          jdk.compiler/com.sun.tools.javac.file

    32  *          jdk.compiler/com.sun.tools.javac.tree

    33  *          jdk.compiler/com.sun.tools.javac.util

    34  * @build DPrinter HashCollisionTest

    35  * @run main HashCollisionTest

    36  */

    37 

    38 import java.lang.reflect.*;

    39 import java.io.*;

    40 import java.util.function.BiConsumer;

    41 

    42 import com.sun.source.util.Trees;

    43 import com.sun.tools.javac.api.JavacTrees;

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

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

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

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

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

    49 import com.sun.tools.javac.tree.JCTree.JCImport;

    50 import com.sun.tools.javac.tree.TreeMaker;

    51 

    52 import static com.sun.tools.javac.code.Kinds.Kind.*;

    53 

    54 public class HashCollisionTest {

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

    56         new HashCollisionTest().run();

    57     }

    58 

    59     void run() throws Exception {

    60         // set up basic environment for test

    61         Context context = new Context();

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

    63         make = TreeMaker.instance(context);

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

    65         symtab = Symtab.instance(context);

    66         trees = JavacTrees.instance(context);

    67         types = Types.instance(context);

    68 

    69         // determine hashMask for an empty scope

    70         Scope emptyScope = WriteableScope.create(symtab.unnamedModule.unnamedPackage); // any owner will do

    71         Field field = emptyScope.getClass().getDeclaredField("hashMask");

    72         field.setAccessible(true);

    73         scopeHashMask = field.getInt(emptyScope);

    74         log("scopeHashMask: " + scopeHashMask);

    75 

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

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

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

    79 

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

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

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

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

    84         // desired characteristics is found.

    85         Name outerName;

    86         Name innerName;

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

    88         int i = 0;

    89         do {

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

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

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

    93 

    94         if (clash(entry, innerName)) {

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

    96                     + " after " + i + " tries");

    97         } else {

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

    99         }

   100 

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

   102 

   103         /*

   104          * Now we can set up the scenario.

   105          */

   106 

   107         // 3. Create a nested class named Entry

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

   109         ClassSymbol ce = createClass(entry, cc);

   110 

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

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

   113         p.members_field = WriteableScope.create(p);

   114         ClassSymbol inner = createClass(innerName, p);

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

   116         ClassSymbol outer = createClass(outerName, p);

   117 

   118         // 5. Create a star-import scope

   119         log ("createStarImportScope");

   120 

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

   122         StarImportScope starImportScope = new StarImportScope(pkg);

   123 

   124         dump("initial", starImportScope);

   125 

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

   127         Scope fromScope = p.members();

   128         ImportFilter typeFilter = new ImportFilter() {

   129             @Override

   130             public boolean accepts(Scope origin, Symbol sym) {

   131                 return sym.kind == TYP;

   132             }

   133         };

   134         BiConsumer<JCImport, CompletionFailure> noCompletionFailure =

   135                 (imp, cf) -> { throw new IllegalStateException(); };

   136         starImportScope.importAll(types, fromScope, typeFilter, make.Import(null, false), noCompletionFailure);

   137 

   138         dump("imported p", starImportScope);

   139 

   140         // 7. Insert the class from 3.

   141         starImportScope.importAll(types, cc.members_field, typeFilter, make.Import(null, false), noCompletionFailure);

   142         dump("imported ce", starImportScope);

   143 

   144         /*

   145          * Set the trap.

   146          */

   147 

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

   149         p.members_field.remove(inner);

   150         inner.name = entry;

   151         inner.owner = outer;

   152         outer.members_field.enter(inner);

   153 

   154         // 9. Lookup Entry

   155         Symbol found = starImportScope.findFirst(entry);

   156         if (found != ce)

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

   158 

   159         dump("final", starImportScope);

   160     }

   161 

   162     /*

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

   164      */

   165     boolean clash(Name n1, Name n2) {

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

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

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

   169     }

   170 

   171     /**

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

   173      */

   174     ClassSymbol createClass(Name name, Symbol owner) {

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

   176         sym.members_field = WriteableScope.create(sym);

   177         if (owner != symtab.unnamedModule.unnamedPackage)

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

   179         return sym;

   180     }

   181 

   182     /**

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

   184      */

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

   186         PrintWriter pw = new PrintWriter(System.err);

   187         new DPrinter(pw, trees).printScope(label, s);

   188         pw.flush();

   189     }

   190 

   191     Object readField(Object scope, String fieldName) throws Exception {

   192         Field field = scope.getClass().getDeclaredField(fieldName);

   193         field.setAccessible(true);

   194 

   195         return field.get(scope);

   196     }

   197 

   198     /**

   199      * Write a message to stderr.

   200      */

   201     void log(String msg) {

   202         System.err.println(msg);

   203     }

   204 

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

   206     int scopeHashMask;

   207 

   208     TreeMaker make;

   209     Names names;

   210     Symtab symtab;

   211     Trees trees;

   212     Types types;

   213 }