HashCollisionTest.java revision 2739:9d2192f36e53 
1/*
2 * Copyright (c) 2010, 2014, 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 * @library /tools/javac/lib
29 * @build DPrinter HashCollisionTest
30 * @run main HashCollisionTest
31 */
32
33import java.lang.reflect.*;
34import java.io.*;
35
36import com.sun.source.util.Trees;
37import com.sun.tools.javac.api.JavacTrees;
38import com.sun.tools.javac.util.*;
39import com.sun.tools.javac.code.*;
40import com.sun.tools.javac.code.Scope.*;
41import com.sun.tools.javac.code.Symbol.*;
42import com.sun.tools.javac.file.JavacFileManager;
43
44import static com.sun.tools.javac.code.Kinds.Kind.*;
45
46public class HashCollisionTest {
47    public static void main(String... args) throws Exception {
48        new HashCollisionTest().run();
49    }
50
51    void run() throws Exception {
52        // set up basic environment for test
53        Context context = new Context();
54        JavacFileManager.preRegister(context); // required by ClassReader which is required by Symtab
55        names = Names.instance(context);       // Name.Table impls tied to an instance of Names
56        symtab = Symtab.instance(context);
57        trees = JavacTrees.instance(context);
58        types = Types.instance(context);
59
60        // determine hashMask for an empty scope
61        Scope emptyScope = WriteableScope.create(symtab.unnamedPackage); // any owner will do
62        Field field = emptyScope.getClass().getDeclaredField("hashMask");
63        field.setAccessible(true);
64        scopeHashMask = field.getInt(emptyScope);
65        log("scopeHashMask: " + scopeHashMask);
66
67        // 1. determine the Name.hashCode of "Entry", and therefore the index of
68        // Entry in an empty scope.  i.e. name.hashCode() & Scope.hashMask
69        Name entry = names.fromString("Entry");
70
71        // 2. create names of the form *$Entry until we find a name with a
72        // hashcode which yields the same index as Entry in an empty scope.
73        // Since Name.hashCode is a function of position (and not content) it
74        // should work to create successively longer names until one with the
75        // desired characteristics is found.
76        Name outerName;
77        Name innerName;
78        StringBuilder sb = new StringBuilder("C");
79        int i = 0;
80        do {
81            sb.append(Integer.toString(i % 10));
82            innerName = names.fromString(sb + "$Entry");
83        } while (!clash(entry, innerName) && (++i) < MAX_TRIES);
84
85        if (clash(entry, innerName)) {
86            log("Detected expected hash collision for " + entry + " and " + innerName
87                    + " after " + i + " tries");
88        } else {
89            throw new Exception("No potential collision found after " + i + " tries");
90        }
91
92        outerName = names.fromString(sb.toString());
93
94        /*
95         * Now we can set up the scenario.
96         */
97
98        // 3. Create a nested class named Entry
99        ClassSymbol cc = createClass(names.fromString("C"), symtab.unnamedPackage);
100        ClassSymbol ce = createClass(entry, cc);
101
102        // 4. Create a package containing a nested class using the name from 2
103        PackageSymbol p = new PackageSymbol(names.fromString("p"), symtab.rootPackage);
104        p.members_field = WriteableScope.create(p);
105        ClassSymbol inner = createClass(innerName, p);
106        // we'll need this later when we "rename" cn
107        ClassSymbol outer = createClass(outerName, p);
108
109        // 5. Create a star-import scope
110        log ("createStarImportScope");
111
112        PackageSymbol pkg = new PackageSymbol(names.fromString("pkg"), symtab.rootPackage);
113        StarImportScope starImportScope = new StarImportScope(pkg);
114
115        dump("initial", starImportScope);
116
117        // 6. Insert the contents of the package from 4.
118        Scope fromScope = p.members();
119        ImportFilter typeFilter = new ImportFilter() {
120            @Override
121            public boolean accepts(Scope origin, Symbol sym) {
122                return sym.kind == TYP;
123            }
124        };
125        starImportScope.importAll(types, fromScope, typeFilter, false);
126
127        dump("imported p", starImportScope);
128
129        // 7. Insert the class from 3.
130        starImportScope.importAll(types, cc.members_field, typeFilter, false);
131        dump("imported ce", starImportScope);
132
133        /*
134         * Set the trap.
135         */
136
137        // 8. Rename the nested class to Entry. so that there is a bogus entry in the star-import scope
138        p.members_field.remove(inner);
139        inner.name = entry;
140        inner.owner = outer;
141        outer.members_field.enter(inner);
142
143        // 9. Lookup Entry
144        Symbol found = starImportScope.findFirst(entry);
145        if (found != ce)
146            throw new Exception("correct symbol not found: " + entry + "; found=" + found);
147
148        dump("final", starImportScope);
149    }
150
151    /*
152     * Check for a (probable) hash collision in an empty scope.
153     */
154    boolean clash(Name n1, Name n2) {
155        log(n1 + " hc:" + n1.hashCode() + " v:" + (n1.hashCode() & scopeHashMask) + ", " +
156                n2 + " hc:" + n2.hashCode() + " v:" + (n2.hashCode() & scopeHashMask));
157        return (n1.hashCode() & scopeHashMask) == (n2.hashCode() & scopeHashMask);
158    }
159
160    /**
161     * Create a class symbol, init the members scope, and add it to owner's scope.
162     */
163    ClassSymbol createClass(Name name, Symbol owner) {
164        ClassSymbol sym = new ClassSymbol(0, name, owner);
165        sym.members_field = WriteableScope.create(sym);
166        if (owner != symtab.unnamedPackage)
167            owner.members().enter(sym);
168        return sym;
169    }
170
171    /**
172     * Dump the contents of a scope to System.err.
173     */
174    void dump(String label, Scope s) throws Exception {
175        PrintWriter pw = new PrintWriter(System.err);
176        new DPrinter(pw, trees).printScope(label, s);
177        pw.flush();
178    }
179
180    Object readField(Object scope, String fieldName) throws Exception {
181        Field field = scope.getClass().getDeclaredField(fieldName);
182        field.setAccessible(true);
183
184        return field.get(scope);
185    }
186
187    /**
188     * Write a message to stderr.
189     */
190    void log(String msg) {
191        System.err.println(msg);
192    }
193
194    int MAX_TRIES = 100; // max tries to find a hash clash before giving up.
195    int scopeHashMask;
196
197    Names names;
198    Symtab symtab;
199    Trees trees;
200    Types types;
201}
202