changeset 822:7e3e9f6d013f

7004029: intermittent failures compiling pack200 Summary: remove "bogus" entries from star-import scopes Reviewed-by: mcimadamore Contributed-by: per.bothner@oracle.com
author jjg
date Thu, 02 Dec 2010 16:37:23 -0800
parents c44234f680da
children 28566c763dad
files src/share/classes/com/sun/tools/javac/code/Scope.java src/share/classes/com/sun/tools/javac/comp/Enter.java src/share/classes/com/sun/tools/javac/comp/MemberEnter.java src/share/classes/com/sun/tools/javac/tree/JCTree.java test/tools/javac/scope/HashCollisionTest.java test/tools/javac/scope/StarImportTest.java
diffstat 6 files changed, 692 insertions(+), 55 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/com/sun/tools/javac/code/Scope.java	Mon Nov 29 14:15:36 2010 -0800
+++ b/src/share/classes/com/sun/tools/javac/code/Scope.java	Thu Dec 02 16:37:23 2010 -0800
@@ -83,6 +83,10 @@
         }
     };
 
+    /** A list of scopes to be notified if items are to be removed from this scope.
+     */
+    List<Scope> listeners = List.nil();
+
     public static class ScopeCounter {
         protected static final Context.Key<ScopeCounter> scopeCounterKey =
             new Context.Key<ScopeCounter>();
@@ -220,7 +224,7 @@
         int n = 0;
         for (int i = oldtable.length; --i >= 0; ) {
             Entry e = oldtable[i];
-            if (e != null && e != sentinel && ! e.isBogus()) {
+            if (e != null && e != sentinel) {
                 table[getIndex(e.sym.name)] = e;
                 n++;
             }
@@ -300,6 +304,11 @@
             }
             te = te.sibling;
         }
+
+        // remove items from scopes that have done importAll
+        for (List<Scope> l = listeners; l.nonEmpty(); l = l.tail) {
+            l.head.remove(sym);
+        }
     }
 
     /** Enter symbol sym in this scope if not already there.
@@ -365,7 +374,7 @@
         int h = name.hashCode();
         int i = h & hashMask;
         // The expression below is always odd, so it is guaranteed
-        // be be mutually prime with table.length, a power of 2.
+        // to be mutually prime with table.length, a power of 2.
         int x = hashMask - ((h + (h >> 16)) << 1);
         int d = -1; // Index of a deleted item.
         for (;;) {
@@ -495,8 +504,6 @@
             // in many cases.
             return scope;
         }
-
-        protected boolean isBogus () { return false; }
     }
 
     public static class ImportScope extends Scope {
@@ -510,15 +517,6 @@
             return new ImportEntry(sym, shadowed, sibling, scope, origin);
         }
 
-        public Entry lookup(Name name) {
-            Entry e = table[getIndex(name)];
-            if (e == null)
-                return sentinel;
-            while (e.isBogus())
-                e = e.shadowed;
-            return e;
-        }
-
         static class ImportEntry extends Entry {
             private Scope origin;
 
@@ -526,35 +524,25 @@
                 super(sym, shadowed, sibling, scope);
                 this.origin = origin;
             }
-            public Entry next() {
-                Entry e = super.shadowed;
-                while (e.isBogus())
-                    e = e.shadowed;
-                return e;
-            }
 
             @Override
             public Scope getOrigin() { return origin; }
+        }
+    }
 
-            /**
-             * Is this a bogus inner-class import?
-             * An inner class {@code Outer$Inner.class} read from a class file
-             * starts out in a package scope under the name {@code Outer$Inner},
-             * which (if star-imported) gets copied to the import scope.
-             * When the InnerClasses attribute is processed, the ClassSymbol
-             * is renamed in place (to {@code Inner}), and the owner changed
-             * to the {@code Outer} class.  The ImportScope still has the old
-             * Entry that was created and hashed as {@code "Outer$Inner"},
-             * but whose name was changed to {@code "Inner"}.  This violates
-             * the invariants for the Scope hash table, and so is pretty bogus.
-             * When the symbol was renamed, it should have been removed from
-             * the import scope (and not just the package scope); however,
-             * doing so is difficult.  A better fix would be to change
-             * import scopes to indirectly reference package symbols, rather
-             * than copy from them.
-             * Until then, we detect and skip the bogus entries using this test.
-             */
-            protected boolean isBogus () { return sym.owner != scope.owner; }
+    public static class StarImportScope extends ImportScope {
+
+        public StarImportScope(Symbol owner) {
+            super(owner);
+        }
+
+        public void importAll (Scope fromScope) {
+            for (Scope.Entry e = fromScope.elems; e != null; e = e.sibling) {
+                if (e.sym.kind == Kinds.TYP && !includes(e.sym))
+                    enter(e.sym, fromScope);
+            }
+            // Register to be notified when imported items are removed
+            fromScope.listeners = fromScope.listeners.prepend(this);
         }
     }
 
--- a/src/share/classes/com/sun/tools/javac/comp/Enter.java	Mon Nov 29 14:15:36 2010 -0800
+++ b/src/share/classes/com/sun/tools/javac/comp/Enter.java	Thu Dec 02 16:37:23 2010 -0800
@@ -30,16 +30,17 @@
 import javax.tools.JavaFileManager;
 
 import com.sun.tools.javac.code.*;
+import com.sun.tools.javac.code.Scope.*;
+import com.sun.tools.javac.code.Symbol.*;
+import com.sun.tools.javac.code.Type.*;
 import com.sun.tools.javac.jvm.*;
+import com.sun.tools.javac.main.RecognizedOptions.PkgInfo;
 import com.sun.tools.javac.tree.*;
+import com.sun.tools.javac.tree.JCTree.*;
 import com.sun.tools.javac.util.*;
 import com.sun.tools.javac.util.JCDiagnostic.DiagnosticPosition;
 import com.sun.tools.javac.util.List;
 
-import com.sun.tools.javac.code.Type.*;
-import com.sun.tools.javac.code.Symbol.*;
-import com.sun.tools.javac.main.RecognizedOptions.PkgInfo;
-import com.sun.tools.javac.tree.JCTree.*;
 
 import static com.sun.tools.javac.code.Flags.*;
 import static com.sun.tools.javac.code.Kinds.*;
@@ -207,8 +208,8 @@
         Env<AttrContext> localEnv = new Env<AttrContext>(tree, new AttrContext());
         localEnv.toplevel = tree;
         localEnv.enclClass = predefClassDef;
-        tree.namedImportScope = new Scope.ImportScope(tree.packge);
-        tree.starImportScope = new Scope.ImportScope(tree.packge);
+        tree.namedImportScope = new ImportScope(tree.packge);
+        tree.starImportScope = new StarImportScope(tree.packge);
         localEnv.info.scope = tree.namedImportScope;
         localEnv.info.lint = lint;
         return localEnv;
--- a/src/share/classes/com/sun/tools/javac/comp/MemberEnter.java	Mon Nov 29 14:15:36 2010 -0800
+++ b/src/share/classes/com/sun/tools/javac/comp/MemberEnter.java	Thu Dec 02 16:37:23 2010 -0800
@@ -143,12 +143,7 @@
                 log.error(pos, "doesnt.exist", tsym);
             }
         }
-        final Scope fromScope = tsym.members();
-        final Scope toScope = env.toplevel.starImportScope;
-        for (Scope.Entry e = fromScope.elems; e != null; e = e.sibling) {
-            if (e.sym.kind == TYP && !toScope.includes(e.sym))
-                toScope.enter(e.sym, fromScope);
-        }
+        env.toplevel.starImportScope.importAll(tsym.members());
     }
 
     /** Import all static members of a class or package on demand.
--- a/src/share/classes/com/sun/tools/javac/tree/JCTree.java	Mon Nov 29 14:15:36 2010 -0800
+++ b/src/share/classes/com/sun/tools/javac/tree/JCTree.java	Thu Dec 02 16:37:23 2010 -0800
@@ -37,7 +37,7 @@
 import com.sun.tools.javac.util.JCDiagnostic.DiagnosticPosition;
 import com.sun.tools.javac.util.List;
 import com.sun.tools.javac.code.*;
-import com.sun.tools.javac.code.Scope;
+import com.sun.tools.javac.code.Scope.*;
 import com.sun.tools.javac.code.Symbol.*;
 import com.sun.source.tree.*;
 
@@ -434,8 +434,8 @@
         public List<JCTree> defs;
         public JavaFileObject sourcefile;
         public PackageSymbol packge;
-        public Scope namedImportScope;
-        public Scope starImportScope;
+        public ImportScope namedImportScope;
+        public StarImportScope starImportScope;
         public long flags;
         public Position.LineMap lineMap = null;
         public Map<JCTree, String> docComments = null;
@@ -445,8 +445,8 @@
                         List<JCTree> defs,
                         JavaFileObject sourcefile,
                         PackageSymbol packge,
-                        Scope namedImportScope,
-                        Scope starImportScope) {
+                        ImportScope namedImportScope,
+                        StarImportScope starImportScope) {
             this.packageAnnotations = packageAnnotations;
             this.pid = pid;
             this.defs = defs;
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/tools/javac/scope/HashCollisionTest.java	Thu Dec 02 16:37:23 2010 -0800
@@ -0,0 +1,251 @@
+/*
+ * Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test
+ * @bug 7004029
+ * @summary Ensure Scope impl can cope with hash collisions
+ */
+
+import java.lang.reflect.*;
+import java.io.*;
+import com.sun.tools.javac.util.*;
+import com.sun.tools.javac.code.*;
+import com.sun.tools.javac.code.Scope.*;
+import com.sun.tools.javac.code.Symbol.*;
+import com.sun.tools.javac.file.JavacFileManager;
+import static com.sun.tools.javac.code.Kinds.*;
+
+public class HashCollisionTest {
+    public static void main(String... args) throws Exception {
+        new HashCollisionTest().run();
+    }
+
+    void run() throws Exception {
+        // set up basic environment for test
+        Context context = new Context();
+        JavacFileManager.preRegister(context); // required by ClassReader which is required by Symtab
+        names = Names.instance(context);       // Name.Table impls tied to an instance of Names
+        symtab = Symtab.instance(context);
+        scopeCounter = ScopeCounter.instance(context);
+
+        // determine hashMask for an empty scope
+        Scope emptyScope = new Scope(symtab.unnamedPackage); // any owner will do
+        Field sHashMask = Scope.class.getDeclaredField("hashMask");
+        sHashMask.setAccessible(true);
+        scopeHashMask = sHashMask.getInt(emptyScope);
+        log("scopeHashMask: " + scopeHashMask);
+
+        // 1. determine the Name.hashCode of "Entry", and therefore the index of
+        // Entry in an empty scope.  i.e. name.hashCode() & Scope.hashMask
+        Name entry = names.fromString("Entry");
+
+        // 2. create names of the form *$Entry until we find a name with a
+        // hashcode which yields the same index as Entry in an empty scope.
+        // Since Name.hashCode is a function of position (and not content) it
+        // should work to create successively longer names until one with the
+        // desired characteristics is found.
+        Name outerName;
+        Name innerName;
+        StringBuilder sb = new StringBuilder("C");
+        int i = 0;
+        do {
+            sb.append(Integer.toString(i % 10));
+            innerName = names.fromString(sb + "$Entry");
+        } while (!clash(entry, innerName) && (++i) < MAX_TRIES);
+
+        if (clash(entry, innerName)) {
+            log("Detected expected hash collision for " + entry + " and " + innerName
+                    + " after " + i + " tries");
+        } else {
+            throw new Exception("No potential collision found after " + i + " tries");
+        }
+
+        outerName = names.fromString(sb.toString());
+
+        /*
+         * Now we can set up the scenario.
+         */
+
+        // 3. Create a nested class named Entry
+        ClassSymbol cc = createClass(names.fromString("C"), symtab.unnamedPackage);
+        ClassSymbol ce = createClass(entry, cc);
+
+        // 4. Create a package containing a nested class using the name from 2
+        PackageSymbol p = new PackageSymbol(names.fromString("p"), symtab.rootPackage);
+        p.members_field = new Scope(p);
+        ClassSymbol inner = createClass(innerName, p);
+        // we'll need this later when we "rename" cn
+        ClassSymbol outer = createClass(outerName, p);
+
+        // 5. Create a star-import scope
+        log ("createStarImportScope");
+
+        // if StarImportScope exists, use it, otherwise, for testing legacy code,
+        // fall back on ImportScope
+        Scope starImportScope;
+        Method importAll;
+        PackageSymbol pkg = new PackageSymbol(names.fromString("pkg"), symtab.rootPackage);
+        try {
+            Class<?> c = Class.forName("com.sun.tools.javac.code.Scope$StarImportScope");
+            Constructor ctor = c.getDeclaredConstructor(new Class[] { Symbol.class });
+            importAll = c.getDeclaredMethod("importAll", new Class[] { Scope.class });
+            starImportScope = (Scope) ctor.newInstance(new Object[] { pkg });
+        } catch (ClassNotFoundException e) {
+            starImportScope = new ImportScope(pkg);
+            importAll = null;
+        }
+
+        dump("initial", starImportScope);
+
+        // 6. Insert the contents of the package from 4.
+        Scope p_members = p.members();
+        if (importAll != null) {
+            importAll.invoke(starImportScope, p_members);
+        } else {
+            Scope fromScope = p_members;
+            Scope toScope = starImportScope;
+            // The following lines are taken from MemberEnter.importAll,
+            // before the use of StarImportScope.importAll.
+            for (Scope.Entry e = fromScope.elems; e != null; e = e.sibling) {
+                if (e.sym.kind == TYP && !toScope.includes(e.sym))
+                    toScope.enter(e.sym, fromScope);
+            }
+        }
+
+        dump("imported p", starImportScope);
+
+        // 7. Insert the class from 3.
+        starImportScope.enter(ce, cc.members_field);
+        dump("imported ce", starImportScope);
+
+        /*
+         * Set the trap.
+         */
+
+        // 8. Rename the nested class to Entry. so that there is a bogus entry in the star-import scope
+        p.members_field.remove(inner);
+        inner.name = entry;
+        inner.owner = outer;
+        outer.members_field.enter(inner);
+
+        // 9. Lookup Entry
+        Scope.Entry e = starImportScope.lookup(entry);
+        dump("final", starImportScope);
+
+        if (e.sym == null)
+            throw new Exception("symbol not found: " + entry);
+    }
+
+    /*
+     * Check for a (probable) hash collision in an empty scope.
+     */
+    boolean clash(Name n1, Name n2) {
+        log(n1 + " hc:" + n1.hashCode() + " v:" + (n1.hashCode() & scopeHashMask) + ", " +
+                n2 + " hc:" + n2.hashCode() + " v:" + (n2.hashCode() & scopeHashMask));
+        return (n1.hashCode() & scopeHashMask) == (n2.hashCode() & scopeHashMask);
+    }
+
+    /**
+     * Create a class symbol, init the members scope, and add it to owner's scope.
+     */
+    ClassSymbol createClass(Name name, Symbol owner) {
+        ClassSymbol sym = new ClassSymbol(0, name, owner);
+        sym.members_field = new ClassScope(sym, scopeCounter);
+        if (owner != symtab.unnamedPackage)
+            owner.members().enter(sym);
+        return sym;
+    }
+
+    /**
+     * Dump the contents of a scope to System.err.
+     */
+    void dump(String label, Scope s) throws Exception {
+        dump(label, s, System.err);
+    }
+
+    /**
+     * Dump the contents of a scope to a stream.
+     */
+    void dump(String label, Scope s, PrintStream out) throws Exception {
+        out.println(label);
+        Field sTable = Scope.class.getDeclaredField("table");
+        sTable.setAccessible(true);
+
+        out.println("owner:" + s.owner);
+        Scope.Entry[] table = (Scope.Entry[]) sTable.get(s);
+        for (int i = 0; i < table.length; i++) {
+            if (i > 0)
+                out.print(", ");
+            out.print(i + ":" + toString(table[i], table, false));
+        }
+        out.println();
+    }
+
+    /**
+     * Create a string showing the contents of an entry, using the table
+     * to help identify cross-references to other entries in the table.
+     * @param e the entry to be shown
+     * @param table the table containing the other entries
+     */
+    String toString(Scope.Entry e, Scope.Entry[] table, boolean ref) {
+        if (e == null)
+            return "null";
+        if (e.sym == null)
+            return "sent"; // sentinel
+        if (ref) {
+            int index = indexOf(table, e);
+            if (index != -1)
+                return String.valueOf(index);
+        }
+        return "(" + e.sym.name + ":" + e.sym
+                + ",shdw:" + toString(e.next(), table, true)
+                + ",sibl:" + toString(e.sibling, table, true)
+                + ((e.sym.owner != e.scope.owner)
+                    ? (",BOGUS[" + e.sym.owner + "," + e.scope.owner + "]")
+                    : "")
+                + ")";
+    }
+
+    <T> int indexOf(T[] array, T item) {
+        for (int i = 0; i < array.length; i++) {
+            if (array[i] == item)
+                return i;
+        }
+        return -1;
+    }
+
+    /**
+     * Write a message to stderr.
+     */
+    void log(String msg) {
+        System.err.println(msg);
+    }
+
+    int MAX_TRIES = 100; // max tries to find a hash clash before giving up.
+    int scopeHashMask;
+
+    Names names;
+    Symtab symtab;
+    ScopeCounter scopeCounter;
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/tools/javac/scope/StarImportTest.java	Thu Dec 02 16:37:23 2010 -0800
@@ -0,0 +1,402 @@
+/*
+ * Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test
+ * @bug 7004029
+ * @summary Basher for star-import scopes
+ */
+
+import java.lang.reflect.*;
+import java.util.*;
+import java.util.List;
+import com.sun.tools.javac.util.*;
+import com.sun.tools.javac.code.*;
+import com.sun.tools.javac.code.Scope.*;
+import com.sun.tools.javac.code.Symbol.*;
+import com.sun.tools.javac.file.JavacFileManager;
+import static com.sun.tools.javac.code.Kinds.*;
+
+public class StarImportTest {
+    public static void main(String... args) throws Exception {
+        new StarImportTest().run(args);
+    }
+
+    void run(String... args) throws Exception {
+        int count = 1;
+
+        for (int i = 0; i < args.length; i++) {
+            String arg = args[i];
+            if (arg.equals("-seed") && (i + 1 < args.length))
+                seed = Long.parseLong(args[++i]);
+            else if(arg.equals("-tests") && (i + 1 < args.length))
+                count = Integer.parseInt(args[++i]);
+            else
+                throw new Exception("unknown arg: " + arg);
+        }
+
+        rgen = new Random(seed);
+
+        for (int i = 0; i < count; i++) {
+            Test t = new Test();
+            t.run();
+        }
+
+        if (errors > 0)
+            throw new Exception(errors + " errors found");
+    }
+
+    /**
+     * Select a random element from an array of choices.
+     */
+    <T> T random(T... choices) {
+        return choices[rgen.nextInt(choices.length)];
+    }
+
+    /**
+     * Write a message to stderr.
+     */
+    void log(String msg) {
+        System.err.println(msg);
+    }
+
+    /**
+     * Write a message to stderr, and dump a scope.
+     */
+    void log(String msg, Scope s) {
+        System.err.print(msg);
+        System.err.print(": ");
+        String sep = "(";
+        for (Scope.Entry se = s.elems; se != null; se = se.sibling) {
+            for (Scope.Entry e = se; e.sym != null; e = e.next()) {
+                System.err.print(sep + e.sym.name + ":" + e.sym);
+                sep = ",";
+            }
+            System.err.print(")");
+            sep = ", (";
+        }
+        System.err.println();
+    }
+
+    /**
+     * Write an error message to stderr.
+     */
+    void error(String msg) {
+        System.err.println("Error: " + msg);
+        errors++;
+    }
+
+    Random rgen;
+    long seed = 0;
+
+    int errors;
+
+    enum SetupKind { NAMES, PACKAGE, CLASS };
+    static final int MAX_SETUP_COUNT = 50;
+    static final int MAX_SETUP_NAME_COUNT = 20;
+    static final int MAX_SETUP_PACKAGE_COUNT = 20;
+    static final int MAX_SETUP_CLASS_COUNT = 20;
+
+    /** Class to encapsulate a test run. */
+    class Test {
+        /** Run the test. */
+        void run() throws Exception {
+            log ("starting test");
+            setup();
+            createStarImportScope();
+            test();
+        }
+
+        /**
+         * Setup env by creating pseudo-random collection of names, packages and classes.
+         */
+        void setup() {
+            log ("setup");
+            context = new Context();
+            JavacFileManager.preRegister(context); // required by ClassReader which is required by Symtab
+            names = Names.instance(context);       // Name.Table impls tied to an instance of Names
+            symtab = Symtab.instance(context);
+            scopeCounter = ScopeCounter.instance(context);
+            int setupCount = rgen.nextInt(MAX_SETUP_COUNT);
+            for (int i = 0; i < setupCount; i++) {
+                switch (random(SetupKind.values())) {
+                    case NAMES:
+                        setupNames();
+                        break;
+                    case PACKAGE:
+                        setupPackage();
+                        break;
+                    case CLASS:
+                        setupClass();
+                        break;
+                }
+            }
+        }
+
+        /**
+         * Set up a random number of names.
+         */
+        void setupNames() {
+            int count = rgen.nextInt(MAX_SETUP_NAME_COUNT);
+            log("setup: creating " + count + " new names");
+            for (int i = 0; i < count; i++) {
+                names.fromString("n" + (++nextNameSerial));
+            }
+        }
+
+        /**
+         * Set up a package containing a random number of member elements.
+         */
+        void setupPackage() {
+            Name name = names.fromString("p" + (++nextPackageSerial));
+            int count = rgen.nextInt(MAX_SETUP_PACKAGE_COUNT);
+            log("setup: creating package " + name + " with " + count + " entries");
+            PackageSymbol p = new PackageSymbol(name, symtab.rootPackage);
+            p.members_field = new Scope(p);
+            for (int i = 0; i < count; i++) {
+                String outer = name + "c" + i;
+                String suffix = random(null, "$Entry", "$Entry2");
+                ClassSymbol c1 = createClass(names.fromString(outer), p);
+//                log("setup: created " + c1);
+                if (suffix != null) {
+                    ClassSymbol c2 = createClass(names.fromString(outer + suffix), p);
+//                    log("setup: created " + c2);
+                }
+            }
+//            log("package " + p, p.members_field);
+            packages.add(p);
+            imports.add(p);
+        }
+
+        /**
+         * Set up a class containing a random number of member elements.
+         */
+        void setupClass() {
+            Name name = names.fromString("c" + (++nextClassSerial));
+            int count = rgen.nextInt(MAX_SETUP_CLASS_COUNT);
+            log("setup: creating class " + name + " with " + count + " entries");
+            ClassSymbol c = createClass(name, symtab.unnamedPackage);
+//            log("setup: created " + c);
+            for (int i = 0; i < count; i++) {
+                ClassSymbol ic = createClass(names.fromString("Entry" + i), c);
+//                log("setup: created " + ic);
+            }
+            classes.add(c);
+            imports.add(c);
+        }
+
+        /**
+         * Create a star-import scope and a model therof, from the packages and
+         * classes created by setupPackages and setupClasses.
+         * @throws Exception for fatal errors, such as from reflection
+         */
+        void createStarImportScope() throws Exception {
+            log ("createStarImportScope");
+            PackageSymbol pkg = new PackageSymbol(names.fromString("pkg"), symtab.rootPackage);
+
+            // if StarImportScope exists, use it, otherwise, for testing legacy code,
+            // fall back on ImportScope
+            Method importAll;
+            try {
+                Class<?> c = Class.forName("com.sun.tools.javac.code.Scope$StarImportScope");
+                Constructor ctor = c.getDeclaredConstructor(new Class[] { Symbol.class });
+                importAll = c.getDeclaredMethod("importAll", new Class[] { Scope.class });
+                starImportScope = (Scope) ctor.newInstance(new Object[] { pkg });
+            } catch (ClassNotFoundException e) {
+                starImportScope = new ImportScope(pkg);
+                importAll = null;
+            }
+            starImportModel = new Model();
+
+            for (Symbol imp: imports) {
+                Scope members = imp.members();
+                if (importAll != null) {
+//                    log("importAll", members);
+                    importAll.invoke(starImportScope, members);
+                } else {
+                    Scope fromScope = members;
+                    Scope toScope = starImportScope;
+                    // The following lines are taken from MemberEnter.importAll,
+                    // before the use of StarImportScope.importAll.
+                    for (Scope.Entry e = fromScope.elems; e != null; e = e.sibling) {
+                        if (e.sym.kind == TYP && !toScope.includes(e.sym))
+                            toScope.enter(e.sym, fromScope);
+                    }
+                }
+
+                for (Scope.Entry e = members.elems; e != null; e = e.sibling) {
+                    starImportModel.enter(e.sym);
+                }
+            }
+
+//            log("star-import scope", starImportScope);
+            starImportModel.check(starImportScope);
+        }
+
+        /**
+         * The core of the test. In a random order, move nested classes from
+         * the package in which they created to the class which should own them.
+         */
+        void test() {
+            log ("test");
+            List<ClassSymbol> nestedClasses = new LinkedList<ClassSymbol>();
+            for (PackageSymbol p: packages) {
+                for (Scope.Entry se = p.members_field.elems; se != null; se = se.sibling) {
+                    if (se.sym.name.toString().contains("$"))
+                        nestedClasses.add((ClassSymbol) se.sym);
+                }
+            }
+
+            for (int i = nestedClasses.size(); i > 0; i--) {
+                // select a random nested class to move from package to class
+                ClassSymbol sym = nestedClasses.remove(rgen.nextInt(i));
+                log("adjusting class " + sym);
+
+                // remove from star import model
+                starImportModel.remove(sym);
+
+                String s = sym.name.toString();
+                int dollar = s.indexOf("$");
+
+                // owner should be a package
+                assert (sym.owner.kind == PCK);
+
+                // determine new owner
+                Name outerName = names.fromString(s.substring(0, dollar));
+//                log(sym + " owner: " + sym.owner, sym.owner.members());
+                Scope.Entry outerEntry = sym.owner.members().lookup(outerName);
+                ClassSymbol outer = (ClassSymbol) outerEntry.sym;
+//                log("outer: " + outerName + " " + outer);
+
+                // remove from package
+                sym.owner.members().remove(sym);
+
+                // rename and insert into class
+                sym.name = names.fromString(s.substring(dollar + 1));
+                outer.members().enter(sym);
+                sym.owner = outer;
+
+                // verify
+                starImportModel.check(starImportScope);
+            }
+        }
+
+        ClassSymbol createClass(Name name, Symbol owner) {
+            ClassSymbol sym = new ClassSymbol(0, name, owner);
+            sym.members_field = new ClassScope(sym, scopeCounter);
+            if (owner != symtab.unnamedPackage)
+                owner.members().enter(sym);
+            return sym;
+        }
+
+        Context context;
+        Symtab symtab;
+        ScopeCounter scopeCounter;
+        Names names;
+        int nextNameSerial;
+        List<PackageSymbol> packages = new ArrayList<PackageSymbol>();
+        int nextPackageSerial;
+        List<ClassSymbol> classes = new ArrayList<ClassSymbol>();
+        List<Symbol> imports = new ArrayList<Symbol>();
+        int nextClassSerial;
+
+        Scope starImportScope;
+        Model starImportModel;
+    }
+
+    class Model {
+        private Map<Name, Set<Symbol>> map = new HashMap<Name, Set<Symbol>>();
+        private Set<Symbol> bogus = new HashSet<Symbol>();
+
+        void enter(Symbol sym) {
+            Set<Symbol> syms = map.get(sym.name);
+            if (syms == null)
+                map.put(sym.name, syms = new LinkedHashSet<Symbol>());
+            syms.add(sym);
+        }
+
+        void remove(Symbol sym) {
+            Set<Symbol> syms = map.get(sym.name);
+            if (syms == null)
+                error("no entries for " + sym.name + " found in reference model");
+            else {
+                boolean ok = syms.remove(sym);
+                if (ok) {
+//                        log(sym.name + "(" + sym + ") removed from reference model");
+                } else {
+                    error(sym.name + " not found in reference model");
+                }
+                if (syms.isEmpty())
+                    map.remove(sym.name);
+            }
+        }
+
+        /**
+         * Check the contents of a scope
+         */
+        void check(Scope scope) {
+            // First, check all entries in scope are in map
+            int bogusCount = 0;
+            for (Scope.Entry se = scope.elems; se != null; se = se.sibling) {
+                Symbol sym = se.sym;
+                if (sym.owner != se.scope.owner) {
+                    if (bogus.contains(sym)) {
+                        bogusCount++;
+                    } else {
+                        log("Warning: " + sym.name + ":" + sym + " appears to be bogus");
+                        bogus.add(sym);
+                    }
+                } else {
+                    Set<Symbol> syms = map.get(sym.name);
+                    if (syms == null) {
+                        error("check: no entries found for " + sym.name + ":" + sym + " in reference map");
+                    } else  if (!syms.contains(sym)) {
+                        error("check: symbol " + sym.name + ":" + sym + " not found in reference map");
+                    }
+                }
+            }
+            if (bogusCount > 0) {
+                log("Warning: " + bogusCount + " other bogus entries previously reported");
+            }
+
+            // Second, check all entries in map are in scope
+            for (Map.Entry<Name,Set<Symbol>> me: map.entrySet()) {
+                Name name = me.getKey();
+                Scope.Entry se = scope.lookup(name);
+                assert (se != null);
+                if (se.sym == null) {
+                    error("check: no entries found for " + name + " in scope");
+                    continue;
+                }
+            nextSym:
+                for (Symbol sym: me.getValue()) {
+                    for (Scope.Entry e = se; e.sym != null; e = e.next()) {
+                        if (sym == e.sym)
+                            continue nextSym;
+                    }
+                    error("check: symbol " + sym + " not found in scope");
+                }
+            }
+        }
+    }
+}