Change to CompilationStateBuilder to prevent recursive invalidation on changed units.

Previously, changing any unit would not only force that unit to be recompiled, but we would then transitively invalidate any units depending on that unit.  So changing one file could result in hundreds of invalidated units.

With this change, we only recompile referrers when a unit changes *structurally*.  That is, when its API changes.  This means that a simple code change to a unit will only recompile that unit, and API changes generally won't go beyond direct referrers.

Patch by: kplatfoot, me
Review by: me, kplatfoot
Review at http://gwt-code-reviews.appspot.com/756802


git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@8550 8db76d5a-ed1c-0410-87a9-c151d255dfc7
diff --git a/dev/core/src/com/google/gwt/dev/javac/CompilationState.java b/dev/core/src/com/google/gwt/dev/javac/CompilationState.java
index 0d7c024..391fdbc 100644
--- a/dev/core/src/com/google/gwt/dev/javac/CompilationState.java
+++ b/dev/core/src/com/google/gwt/dev/javac/CompilationState.java
@@ -149,7 +149,7 @@
       }
     }
     CompilationUnitInvalidator.retainValidUnits(logger, units,
-        compileMoreLater.getValidDependencies());
+        compileMoreLater.getValidClasses());
     mediator.addNewUnits(logger, units);
   }
 }
diff --git a/dev/core/src/com/google/gwt/dev/javac/CompilationStateBuilder.java b/dev/core/src/com/google/gwt/dev/javac/CompilationStateBuilder.java
index aa3a8e7..ded19bb 100644
--- a/dev/core/src/com/google/gwt/dev/javac/CompilationStateBuilder.java
+++ b/dev/core/src/com/google/gwt/dev/javac/CompilationStateBuilder.java
@@ -29,6 +29,7 @@
 import org.apache.commons.collections.map.AbstractReferenceMap;
 import org.apache.commons.collections.map.ReferenceIdentityMap;
 import org.apache.commons.collections.map.ReferenceMap;
+import org.eclipse.jdt.core.compiler.CharOperation;
 import org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration;
 import org.eclipse.jdt.internal.compiler.ast.CompilationUnitDeclaration;
 import org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding;
@@ -38,9 +39,12 @@
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.IdentityHashMap;
+import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.Map.Entry;
 
 /**
  * Manages a centralized cache for compiled units.
@@ -65,8 +69,7 @@
           public ReferenceBinding resolveType(String typeName) {
             ReferenceBinding resolveType = compiler.resolveType(typeName);
             if (resolveType != null) {
-              String fileName = String.valueOf(resolveType.getFileName());
-              jsniDeps.add(fileName);
+              jsniDeps.add(String.valueOf(resolveType.qualifiedSourceName()));
             }
             return resolveType;
           }
@@ -81,8 +84,21 @@
         CompilationUnitInvalidator.reportErrors(logger, cud,
             builder.getSource());
 
-        Set<ContentId> dependencies = compiler.computeDependencies(cud,
-            jsniDeps);
+        String packageName = Shared.getPackageName(builder.getTypeName());
+        List<String> unresolvedQualified = new ArrayList<String>();
+        List<String> unresolvedSimple = new ArrayList<String>();
+        for (char[] simpleRef : cud.compilationResult().simpleNameReferences) {
+          unresolvedSimple.add(canonical(String.valueOf(simpleRef)));
+        }
+        for (char[][] qualifiedRef : cud.compilationResult().qualifiedReferences) {
+          unresolvedQualified.add(canonical(CharOperation.toString(qualifiedRef)));
+        }
+        for (String jsniDep : jsniDeps) {
+          unresolvedQualified.add(canonical(jsniDep));
+        }
+        Dependencies dependencies = new Dependencies(packageName,
+            unresolvedQualified, unresolvedSimple);
+
         CompilationUnit unit = builder.build(compiledClasses, dependencies,
             jsniMethods.values(), methodArgs,
             cud.compilationResult().getProblems());
@@ -99,25 +115,49 @@
         } else if (builder instanceof GeneratedCompilationUnitBuilder) {
           keepAliveRecentlyGenerated.put(unit.getTypeName(), unit);
         }
-        resultUnits.put(unit.getTypeName(), unit);
+
+        newlyBuiltUnits.add(unit);
+      }
+
+      private String canonical(String str) {
+        String result = internedTypeNames.get(str);
+        if (result != null) {
+          return result;
+        }
+        internedTypeNames.put(str, str);
+        return str;
       }
     }
 
     /**
+     * A global cache of all currently-valid class files. This is used to
+     * validate dependencies when reusing previously cached units, to make sure
+     * they can be recompiled if necessary.
+     */
+    private final Map<String, CompiledClass> allValidClasses = new HashMap<String, CompiledClass>();
+
+    /**
      * The JDT compiler.
      */
     private final JdtCompiler compiler = new JdtCompiler(
         new UnitProcessorImpl());
 
     /**
+     * Memory efficiency only. Stores canonical versions of dependency type
+     * names so that String instances can be shared among many units. Otherwise,
+     * we'd get many duplicate String objects since we have to build them from
+     * JDT's char arrays.
+     */
+    private final Map<String, String> internedTypeNames = new HashMap<String, String>();
+
+    /**
      * Continuation state for JSNI checking.
      */
     private final JSORestrictionsChecker.CheckerState jsoState = new JSORestrictionsChecker.CheckerState();
 
     private transient TreeLogger logger;
 
-    private transient Map<String, CompilationUnit> resultUnits;
-    private final Set<ContentId> validDependencies = new HashSet<ContentId>();
+    private transient Collection<CompilationUnit> newlyBuiltUnits;
 
     public CompileMoreLater(AdditionalTypeProviderDelegate delegate) {
       compiler.setAdditionalTypeProviderDelegate(delegate);
@@ -134,24 +174,80 @@
       }
     }
 
+    public Map<String, CompiledClass> getValidClasses() {
+      return Collections.unmodifiableMap(allValidClasses);
+    }
+
     void addValidUnit(CompilationUnit unit) {
       compiler.addCompiledUnit(unit);
-      if (!unit.isError()) {
-        validDependencies.add(unit.getContentId());
+      for (CompiledClass cc : unit.getCompiledClasses()) {
+        String sourceName = cc.getSourceName();
+        allValidClasses.put(sourceName, cc);
       }
     }
 
-    void compile(TreeLogger logger,
+    Collection<CompilationUnit> compile(TreeLogger logger,
         Collection<CompilationUnitBuilder> builders,
-        Map<String, CompilationUnit> resultUnits) {
+        Map<CompilationUnitBuilder, CompilationUnit> cachedUnits) {
       this.logger = logger.branch(TreeLogger.DEBUG,
           "Validating newly compiled units");
-      this.resultUnits = resultUnits;
-      compiler.doCompile(builders);
-    }
 
-    Set<ContentId> getValidDependencies() {
-      return validDependencies;
+      // Initialize the set of valid classes to the initially cached units.
+      for (CompilationUnit unit : cachedUnits.values()) {
+        for (CompiledClass cc : unit.getCompiledClasses()) {
+          // Map by source name.
+          String sourceName = cc.getSourceName();
+          allValidClasses.put(sourceName, cc);
+        }
+      }
+      Map<CompiledClass, CompiledClass> cachedStructurallySame = new IdentityHashMap<CompiledClass, CompiledClass>();
+
+      Collection<CompilationUnit> resultUnits = new ArrayList<CompilationUnit>();
+      do {
+        // Compile anything that needs to be compiled.
+        this.newlyBuiltUnits = new ArrayList<CompilationUnit>();
+
+        compiler.doCompile(builders);
+        resultUnits.addAll(this.newlyBuiltUnits);
+        builders.clear();
+
+        // Resolve all newly built unit deps against the global classes.
+        for (CompilationUnit unit : this.newlyBuiltUnits) {
+          unit.getDependencies().resolve(allValidClasses);
+        }
+
+        /*
+         * Invalidate any cached units with invalid refs.
+         */
+        Collection<CompilationUnit> invalidatedUnits = new ArrayList<CompilationUnit>();
+        for (Iterator<Entry<CompilationUnitBuilder, CompilationUnit>> it = cachedUnits.entrySet().iterator(); it.hasNext();) {
+          Entry<CompilationUnitBuilder, CompilationUnit> entry = it.next();
+          CompilationUnit unit = entry.getValue();
+          boolean isValid = unit.getDependencies().validate(allValidClasses,
+              cachedStructurallySame);
+          if (!isValid) {
+            invalidatedUnits.add(unit);
+            builders.add(entry.getKey());
+            it.remove();
+          }
+        }
+
+        // Any units we invalidated must now be removed from the valid classes.
+        for (CompilationUnit unit : invalidatedUnits) {
+          for (CompiledClass cc : unit.getCompiledClasses()) {
+            allValidClasses.remove(cc.getSourceName());
+          }
+        }
+      } while (builders.size() > 0);
+
+      // Any remaining cached units are valid now.
+      resultUnits.addAll(cachedUnits.values());
+
+      // Re-report any errors on cached units we're reusing.
+      for (CompilationUnit unit : cachedUnits.values()) {
+        CompilationUnitInvalidator.reportErrors(logger, unit);
+      }
+      return resultUnits;
     }
   }
 
@@ -219,6 +315,8 @@
   /**
    * This map of weak keys to hard values exists solely to keep the most recent
    * version of any unit from being eagerly garbage collected.
+   * 
+   * WRITE-ONLY
    */
   @SuppressWarnings("unchecked")
   private final Map<ResourceTag, CompilationUnit> keepAliveLatestVersion = Collections.synchronizedMap(new ReferenceIdentityMap(
@@ -227,6 +325,8 @@
   /**
    * This map of hard keys to soft values exists solely to keep the most
    * recently generated version of a type from being eagerly garbage collected.
+   * 
+   * WRITE-ONLY
    */
   @SuppressWarnings("unchecked")
   private final Map<String, CompilationUnit> keepAliveRecentlyGenerated = Collections.synchronizedMap(new ReferenceMap(
@@ -251,10 +351,8 @@
 
   /**
    * Build a new compilation state from a source oracle.
-   * 
-   * TODO: maybe use a finer brush than to synchronize the whole thing.
    */
-  public synchronized CompilationState doBuildFrom(TreeLogger logger,
+  public CompilationState doBuildFrom(TreeLogger logger,
       Set<Resource> resources) {
     return doBuildFrom(logger, resources, null);
   }
@@ -262,6 +360,8 @@
   /**
    * Build a new compilation state from a source oracle.  Allow the caller to specify 
    * a compiler delegate that will handle undefined names. 
+   * 
+   * TODO: maybe use a finer brush than to synchronize the whole thing.
    */
   public synchronized CompilationState doBuildFrom(TreeLogger logger,
       Set<Resource> resources, AdditionalTypeProviderDelegate compilerDelegate) {
@@ -269,45 +369,37 @@
         SpeedTracerLogger.start(DevModeEventType.COMPILATION_STATE_BUILDER_PROCESS);
     
     try {
-      Map<String, CompilationUnit> resultUnits = new HashMap<String, CompilationUnit>();
+      // Units we definitely want to build.
+      List<CompilationUnitBuilder> builders = new ArrayList<CompilationUnitBuilder>();
+
+      // Units we don't want to rebuild unless we have to.
+      Map<CompilationUnitBuilder, CompilationUnit> cachedUnits = new IdentityHashMap<CompilationUnitBuilder, CompilationUnit>();
+
+      CompileMoreLater compileMoreLater = new CompileMoreLater(compilerDelegate);
 
       // For each incoming Java source file...
       for (Resource resource : resources) {
+        String typeName = Shared.toTypeName(resource.getPath());
+        // Create a builder for all incoming units.
+        ResourceCompilationUnitBuilder builder = new ResourceCompilationUnitBuilder(
+            typeName, resource);
         // Try to get an existing unit from the cache.
         String location = resource.getLocation();
         ResourceTag tag = resourceContentCache.get(location);
         if (tag != null && tag.getLastModified() == resource.getLastModified()) {
           ContentId contentId = tag.getContentId();
           CompilationUnit existingUnit = unitCache.get(contentId);
-          // Always try to recompile error units.
-          if (existingUnit != null && !existingUnit.isError()) {
-            resultUnits.put(existingUnit.getTypeName(), existingUnit);
+          if (existingUnit != null) {
+            cachedUnits.put(builder, existingUnit);
+            compileMoreLater.addValidUnit(existingUnit);
+            continue;
           }
         }
+        builders.add(builder);
       }
-
-      // Winnow the reusable set of units down to those still valid.
-      CompilationUnitInvalidator.retainValidUnits(TreeLogger.NULL,
-                                                  resultUnits.values());
-
-      // Compile everything else.
-      CompileMoreLater compileMoreLater = new CompileMoreLater(compilerDelegate);
-      List<CompilationUnitBuilder> builders = new ArrayList<CompilationUnitBuilder>();
-      for (Resource resource : resources) {
-        String typeName = Shared.toTypeName(resource.getPath());
-        CompilationUnit validUnit = resultUnits.get(typeName);
-        if (validUnit != null) {
-          compileMoreLater.addValidUnit(validUnit);
-          // Report any existing errors as if the unit were recompiled.
-          CompilationUnitInvalidator.reportErrors(logger, validUnit);
-        } else {
-          builders.add(new ResourceCompilationUnitBuilder(typeName, resource));
-        }
-      }
-      compileMoreLater.compile(logger, builders, resultUnits);
-
-      return new CompilationState(logger, resultUnits.values(),
-          compileMoreLater);
+      Collection<CompilationUnit> resultUnits = compileMoreLater.compile(
+          logger, builders, cachedUnits);
+      return new CompilationState(logger, resultUnits, compileMoreLater);
     } finally {
       compilationStateBuilderProcess.end();
     }
@@ -321,38 +413,29 @@
   synchronized Collection<CompilationUnit> doBuildGeneratedTypes(
       TreeLogger logger, Collection<GeneratedUnit> generatedUnits,
       CompileMoreLater compileMoreLater) {
-    Map<String, CompilationUnit> resultUnits = new HashMap<String, CompilationUnit>();
+
+    // Units we definitely want to build.
+    List<CompilationUnitBuilder> builders = new ArrayList<CompilationUnitBuilder>();
+
+    // Units we don't want to rebuild unless we have to.
+    Map<CompilationUnitBuilder, CompilationUnit> cachedUnits = new IdentityHashMap<CompilationUnitBuilder, CompilationUnit>();
 
     // For each incoming generated Java source file...
     for (GeneratedUnit generatedUnit : generatedUnits) {
+      // Create a builder for all incoming units.
+      GeneratedCompilationUnitBuilder builder = new GeneratedCompilationUnitBuilder(
+          generatedUnit);
       // Try to get an existing unit from the cache.
       ContentId contentId = new ContentId(generatedUnit.getTypeName(),
           generatedUnit.getStrongHash());
       CompilationUnit existingUnit = unitCache.get(contentId);
-      // Always try to recompile error units.
-      if (existingUnit != null && !existingUnit.isError()) {
-        resultUnits.put(existingUnit.getTypeName(), existingUnit);
+      if (existingUnit != null) {
+        cachedUnits.put(builder, existingUnit);
+        compileMoreLater.addValidUnit(existingUnit);
+      } else {
+        builders.add(builder);
       }
     }
-
-    // Winnow the reusable set of units down to those still valid.
-    CompilationUnitInvalidator.retainValidUnits(TreeLogger.NULL,
-        resultUnits.values(), compileMoreLater.getValidDependencies());
-    for (CompilationUnit validUnit : resultUnits.values()) {
-      compileMoreLater.addValidUnit(validUnit);
-      // Report any existing errors as if the unit were recompiled.
-      CompilationUnitInvalidator.reportErrors(logger, validUnit);
-    }
-
-    // Compile everything else.
-    List<CompilationUnitBuilder> builders = new ArrayList<CompilationUnitBuilder>();
-    for (GeneratedUnit generatedUnit : generatedUnits) {
-      if (!resultUnits.containsKey(generatedUnit.getTypeName())) {
-        builders.add(new GeneratedCompilationUnitBuilder(generatedUnit));
-      }
-    }
-
-    compileMoreLater.compile(logger, builders, resultUnits);
-    return resultUnits.values();
+    return compileMoreLater.compile(logger, builders, cachedUnits);
   }
 }
diff --git a/dev/core/src/com/google/gwt/dev/javac/CompilationUnit.java b/dev/core/src/com/google/gwt/dev/javac/CompilationUnit.java
index b7983ea..d571717 100644
--- a/dev/core/src/com/google/gwt/dev/javac/CompilationUnit.java
+++ b/dev/core/src/com/google/gwt/dev/javac/CompilationUnit.java
@@ -33,7 +33,6 @@
 import java.util.Collections;
 import java.util.List;
 import java.util.Map;
-import java.util.Set;
 import java.util.regex.Pattern;
 
 /**
@@ -336,7 +335,10 @@
    */
   abstract ContentId getContentId();
 
-  abstract Set<ContentId> getDependencies();
+  /**
+   * The set of dependencies on other classes.
+   */
+  abstract Dependencies getDependencies();
 
   abstract CategorizedProblem[] getProblems();
 
diff --git a/dev/core/src/com/google/gwt/dev/javac/CompilationUnitBuilder.java b/dev/core/src/com/google/gwt/dev/javac/CompilationUnitBuilder.java
index d5f3413..a846523 100644
--- a/dev/core/src/com/google/gwt/dev/javac/CompilationUnitBuilder.java
+++ b/dev/core/src/com/google/gwt/dev/javac/CompilationUnitBuilder.java
@@ -25,7 +25,6 @@
 import java.io.InputStream;
 import java.util.Collection;
 import java.util.List;
-import java.util.Set;
 
 /**
  * Builds a {@link CompilationUnit}.
@@ -61,7 +60,7 @@
 
     @Override
     protected CompilationUnit makeUnit(List<CompiledClass> compiledClasses,
-        Set<ContentId> dependencies,
+        Dependencies dependencies,
         Collection<? extends JsniMethod> jsniMethods,
         MethodArgNamesLookup methodArgs, CategorizedProblem[] problems) {
       return new GeneratedCompilationUnit(generatedUnit, compiledClasses,
@@ -146,7 +145,7 @@
 
     @Override
     protected CompilationUnit makeUnit(List<CompiledClass> compiledClasses,
-        Set<ContentId> dependencies,
+        Dependencies dependencies,
         Collection<? extends JsniMethod> jsniMethods,
         MethodArgNamesLookup methodArgs, CategorizedProblem[] problems) {
       return new SourceFileCompilationUnit(getResource(), contentId,
@@ -159,7 +158,7 @@
     private final GeneratedUnit generatedUnit;
 
     public GeneratedCompilationUnit(GeneratedUnit generatedUnit,
-        List<CompiledClass> compiledClasses, Set<ContentId> dependencies,
+        List<CompiledClass> compiledClasses, Dependencies dependencies,
         Collection<? extends JsniMethod> jsniMethods,
         MethodArgNamesLookup methodArgs, CategorizedProblem[] problems) {
       super(compiledClasses, dependencies, jsniMethods, methodArgs, problems);
@@ -235,8 +234,7 @@
   }
 
   public CompilationUnit build(List<CompiledClass> compiledClasses,
-      Set<ContentId> dependencies,
-      Collection<? extends JsniMethod> jsniMethods,
+      Dependencies dependencies, Collection<? extends JsniMethod> jsniMethods,
       MethodArgNamesLookup methodArgs, CategorizedProblem[] problems) {
     // Free the source now.
     source = null;
@@ -265,7 +263,7 @@
   protected abstract String doGetSource();
 
   protected abstract CompilationUnit makeUnit(
-      List<CompiledClass> compiledClasses, Set<ContentId> dependencies,
+      List<CompiledClass> compiledClasses, Dependencies dependencies,
       Collection<? extends JsniMethod> jsniMethods,
       MethodArgNamesLookup methodArgs, CategorizedProblem[] errors);
 
diff --git a/dev/core/src/com/google/gwt/dev/javac/CompilationUnitImpl.java b/dev/core/src/com/google/gwt/dev/javac/CompilationUnitImpl.java
index 851806c..3248fd8 100644
--- a/dev/core/src/com/google/gwt/dev/javac/CompilationUnitImpl.java
+++ b/dev/core/src/com/google/gwt/dev/javac/CompilationUnitImpl.java
@@ -21,11 +21,10 @@
 
 import java.util.Collection;
 import java.util.List;
-import java.util.Set;
 
 abstract class CompilationUnitImpl extends CompilationUnit {
 
-  private final Set<ContentId> dependencies;
+  private final Dependencies dependencies;
   private final List<CompiledClass> exposedCompiledClasses;
   private final boolean hasErrors;
   private final List<JsniMethod> jsniMethods;
@@ -33,8 +32,7 @@
   private final CategorizedProblem[] problems;
 
   public CompilationUnitImpl(List<CompiledClass> compiledClasses,
-      Set<ContentId> dependencies,
-      Collection<? extends JsniMethod> jsniMethods,
+      Dependencies dependencies, Collection<? extends JsniMethod> jsniMethods,
       MethodArgNamesLookup methodArgs, CategorizedProblem[] problems) {
     this.exposedCompiledClasses = Lists.normalizeUnmodifiable(compiledClasses);
     this.dependencies = dependencies;
@@ -79,7 +77,7 @@
   }
 
   @Override
-  Set<ContentId> getDependencies() {
+  Dependencies getDependencies() {
     return dependencies;
   }
 
diff --git a/dev/core/src/com/google/gwt/dev/javac/CompilationUnitInvalidator.java b/dev/core/src/com/google/gwt/dev/javac/CompilationUnitInvalidator.java
index 24134bc..9d6d0ac 100644
--- a/dev/core/src/com/google/gwt/dev/javac/CompilationUnitInvalidator.java
+++ b/dev/core/src/com/google/gwt/dev/javac/CompilationUnitInvalidator.java
@@ -27,7 +27,10 @@
 import java.util.Collections;
 import java.util.HashSet;
 import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
 import java.util.Set;
+import java.util.Map.Entry;
 
 /**
  * Helper class to invalidate units in a set based on errors or references to
@@ -57,20 +60,28 @@
 
   public static void retainValidUnits(TreeLogger logger,
       Collection<CompilationUnit> units) {
-    retainValidUnits(logger, units, Collections.<ContentId> emptySet());
+    retainValidUnits(logger, units,
+        Collections.<String, CompiledClass> emptyMap());
   }
 
   public static void retainValidUnits(TreeLogger logger,
-      Collection<CompilationUnit> units, Set<ContentId> knownValidRefs) {
+      Collection<CompilationUnit> units, Map<String, CompiledClass> validClasses) {
     logger = logger.branch(TreeLogger.TRACE, "Removing invalidated units");
 
     // Assume all units are valid at first.
     Set<CompilationUnit> currentlyValidUnits = new HashSet<CompilationUnit>();
-    Set<ContentId> currentlyValidRefs = new HashSet<ContentId>(knownValidRefs);
+    Set<String> currentlyValidClasses = new HashSet<String>();
     for (CompilationUnit unit : units) {
       if (!unit.isError()) {
         currentlyValidUnits.add(unit);
-        currentlyValidRefs.add(unit.getContentId());
+        for (CompiledClass cc : unit.getCompiledClasses()) {
+          currentlyValidClasses.add(cc.getSourceName());
+        }
+      }
+    }
+    for (Entry<String, CompiledClass> entry : validClasses.entrySet()) {
+      if (!entry.getValue().getUnit().isError()) {
+        currentlyValidClasses.add(entry.getKey());
       }
     }
 
@@ -79,17 +90,19 @@
       changed = false;
       for (Iterator<CompilationUnit> it = currentlyValidUnits.iterator(); it.hasNext();) {
         CompilationUnit unitToCheck = it.next();
-        TreeLogger branch = null;
-        for (ContentId ref : unitToCheck.getDependencies()) {
-          if (!currentlyValidRefs.contains(ref)) {
-            if (branch == null) {
-              branch = logger.branch(TreeLogger.DEBUG, "Compilation unit '"
-                  + unitToCheck + "' is removed due to invalid reference(s):");
-              it.remove();
-              currentlyValidRefs.remove(unitToCheck.getContentId());
-              changed = true;
-            }
-            branch.log(TreeLogger.DEBUG, ref.get());
+        List<String> missingDeps = unitToCheck.getDependencies().findMissingDeps(
+            currentlyValidClasses);
+        if (missingDeps.size() > 0) {
+          TreeLogger branch = logger.branch(TreeLogger.DEBUG,
+              "Compilation unit '" + unitToCheck
+                  + "' is removed due to invalid reference(s):");
+          it.remove();
+          for (CompiledClass cc : unitToCheck.getCompiledClasses()) {
+            currentlyValidClasses.remove(cc.getSourceName());
+          }
+          changed = true;
+          for (String dep : missingDeps) {
+            branch.log(TreeLogger.DEBUG, dep);
           }
         }
       }
diff --git a/dev/core/src/com/google/gwt/dev/javac/Dependencies.java b/dev/core/src/com/google/gwt/dev/javac/Dependencies.java
new file mode 100644
index 0000000..4af8ce6
--- /dev/null
+++ b/dev/core/src/com/google/gwt/dev/javac/Dependencies.java
@@ -0,0 +1,184 @@
+/*
+ * Copyright 2010 Google Inc.
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ * 
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.dev.javac;
+
+import com.google.gwt.dev.util.collect.HashMap;
+import com.google.gwt.dev.util.collect.Lists;
+
+import org.eclipse.jdt.internal.compiler.classfmt.ClassFileReader;
+import org.eclipse.jdt.internal.compiler.classfmt.ClassFormatException;
+
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.Map.Entry;
+
+/**
+ * Tracks dependencies from a {@link CompilationUnit} to {@link CompiledClass
+ * CompiledClasses}.
+ */
+class Dependencies {
+  Map<String, CompiledClass> qualified = new HashMap<String, CompiledClass>();
+  Map<String, CompiledClass> simple = new HashMap<String, CompiledClass>();
+  private final String myPackage;
+  private List<String> unresolvedQualified;
+  private List<String> unresolvedSimple;
+
+  Dependencies() {
+    this.myPackage = "";
+  }
+
+  /**
+   * Initializes the set of simple and qualified dependency names, but does not
+   * resolve them.
+   */
+  Dependencies(String myPackage, List<String> unresolvedQualified,
+      List<String> unresolvedSimple) {
+    this.myPackage = (myPackage.length() == 0) ? "" : (myPackage + '.');
+    this.unresolvedQualified = unresolvedQualified;
+    this.unresolvedSimple = unresolvedSimple;
+  }
+
+  /**
+   * Returns the list of deps that cannot be resolved at all.
+   */
+  List<String> findMissingDeps(Set<String> allValidClasses) {
+    List<String> result = Lists.create();
+    for (Entry<String, CompiledClass> entry : qualified.entrySet()) {
+      String sourceName = entry.getKey();
+      boolean expected = entry.getValue() != null;
+      boolean actual = allValidClasses.contains(sourceName);
+      if (expected != actual) {
+        result = Lists.add(result, sourceName);
+      }
+    }
+    for (Entry<String, CompiledClass> entry : simple.entrySet()) {
+      String sourceName = entry.getKey();
+      boolean expected = entry.getValue() != null;
+      boolean actual = allValidClasses.contains(myPackage + sourceName)
+          || allValidClasses.contains("java.lang." + sourceName);
+      if (expected != actual) {
+        result = Lists.add(result, sourceName);
+      }
+    }
+    return result;
+  }
+
+  /**
+   * Resolves unqualified dependencies against the global list of all valid
+   * classes. Must be called before {@link #validate(String, Map, Map)}.
+   */
+  void resolve(Map<String, CompiledClass> allValidClasses) {
+    for (String ref : unresolvedQualified) {
+      CompiledClass cc = allValidClasses.get(ref);
+      qualified.put(ref, cc);
+    }
+
+    for (String ref : unresolvedSimple) {
+      CompiledClass cc = findBySimpleName(ref, allValidClasses);
+      allValidClasses.get(ref);
+      simple.put(ref, cc);
+    }
+    unresolvedQualified = unresolvedSimple = null;
+  }
+
+  /**
+   * Validate that all of my existing dependencies can be found in the global
+   * set of valid classes, and resolve to structurally identical APIs.
+   * 
+   * @return <code>true</code> if all of my dependencies are valid
+   */
+  boolean validate(Map<String, CompiledClass> allValidClasses,
+      Map<CompiledClass, CompiledClass> cachedStructurallySame) {
+    for (Entry<String, CompiledClass> entry : qualified.entrySet()) {
+      CompiledClass theirs = allValidClasses.get(entry.getKey());
+      if (!validateClass(cachedStructurallySame, entry, theirs)) {
+        return false;
+      }
+    }
+    for (Entry<String, CompiledClass> entry : simple.entrySet()) {
+      CompiledClass theirs = findBySimpleName(entry.getKey(), allValidClasses);
+      if (!validateClass(cachedStructurallySame, entry, theirs)) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  /**
+   * Tries to resolve a simple name using Java lookup rules, first checking the
+   * current package, then java.lang.
+   */
+  private CompiledClass findBySimpleName(String ref,
+      Map<String, CompiledClass> allValidClasses) {
+    CompiledClass cc = allValidClasses.get(myPackage + ref);
+    if (cc != null) {
+      return cc;
+    }
+    return allValidClasses.get("java.lang." + ref);
+  }
+
+  private boolean hasStructuralChanges(CompiledClass mine, CompiledClass theirs) {
+    try {
+      ClassFileReader cfr = new ClassFileReader(theirs.getBytes(), null);
+      return cfr.hasStructuralChanges(mine.getBytes());
+    } catch (ClassFormatException e) {
+      throw new RuntimeException("Unexpected error reading compiled class", e);
+    }
+  }
+
+  private boolean structurallySame(CompiledClass mine, CompiledClass theirs,
+      Map<CompiledClass, CompiledClass> cachedStructurallySame) {
+    if (cachedStructurallySame.get(mine) == theirs) {
+      return true;
+    }
+    if (cachedStructurallySame.containsKey(mine)) {
+      return false;
+    }
+    boolean isSame = !hasStructuralChanges(mine, theirs);
+    if (isSame) {
+      cachedStructurallySame.put(mine, theirs);
+    } else {
+      cachedStructurallySame.put(mine, null);
+    }
+    return isSame;
+  }
+
+  /**
+   * Returns true if my class is the same as their class. Uses caching to avoid
+   * recomputing diffs. Updates the my entry to 'their' class if non-identical
+   * objects have the same structure.
+   */
+  private boolean validateClass(
+      Map<CompiledClass, CompiledClass> cachedStructurallySame,
+      Entry<String, CompiledClass> entry, CompiledClass theirs) {
+    CompiledClass mine = entry.getValue();
+    boolean result;
+    if (mine == theirs) {
+      // Identical.
+      result = true;
+    } else if ((mine == null) != (theirs == null)) {
+      result = false;
+    } else if (structurallySame(mine, theirs, cachedStructurallySame)) {
+      // Update our entry for identity.
+      entry.setValue(theirs);
+      result = true;
+    } else {
+      result = false;
+    }
+    return result;
+  }
+}
\ No newline at end of file
diff --git a/dev/core/src/com/google/gwt/dev/javac/JdtCompiler.java b/dev/core/src/com/google/gwt/dev/javac/JdtCompiler.java
index 192c94f..19a2760 100644
--- a/dev/core/src/com/google/gwt/dev/javac/JdtCompiler.java
+++ b/dev/core/src/com/google/gwt/dev/javac/JdtCompiler.java
@@ -1,12 +1,12 @@
 /*
  * Copyright 2008 Google Inc.
- *
+ * 
  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
  * use this file except in compliance with the License. You may obtain a copy of
  * the License at
- *
+ * 
  * http://www.apache.org/licenses/LICENSE-2.0
- *
+ * 
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
@@ -16,10 +16,8 @@
 package com.google.gwt.dev.javac;
 
 import com.google.gwt.dev.jdt.SafeASTVisitor;
-import com.google.gwt.dev.jdt.TypeRefVisitor;
 import com.google.gwt.dev.util.collect.IdentityHashMap;
 import com.google.gwt.dev.util.collect.Lists;
-import com.google.gwt.dev.util.collect.Sets;
 import com.google.gwt.dev.util.log.speedtracer.CompilerEventType;
 import com.google.gwt.dev.util.log.speedtracer.SpeedTracerLogger;
 import com.google.gwt.dev.util.log.speedtracer.SpeedTracerLogger.Event;
@@ -31,7 +29,6 @@
 import org.eclipse.jdt.internal.compiler.DefaultErrorHandlingPolicies;
 import org.eclipse.jdt.internal.compiler.ICompilerRequestor;
 import org.eclipse.jdt.internal.compiler.ast.CompilationUnitDeclaration;
-import org.eclipse.jdt.internal.compiler.ast.Expression;
 import org.eclipse.jdt.internal.compiler.ast.TypeDeclaration;
 import org.eclipse.jdt.internal.compiler.classfmt.ClassFileConstants;
 import org.eclipse.jdt.internal.compiler.classfmt.ClassFileReader;
@@ -76,7 +73,7 @@
     /**
      * Checks for additional packages which may contain additional compilation
      * units.
-     *
+     * 
      * @param slashedPackageName the '/' separated name of the package to find
      * @return <code>true</code> if such a package exists
      */
@@ -85,7 +82,7 @@
     /**
      * Finds a new compilation unit on-the-fly for the requested type, if there
      * is an alternate mechanism for doing so.
-     *
+     * 
      * @param binaryName the binary name of the requested type
      * @return a unit answering the name, or <code>null</code> if no such unit
      *         can be created
@@ -97,7 +94,6 @@
    * A default processor that simply collects build units.
    */
   public static final class DefaultUnitProcessor implements UnitProcessor {
-    private JdtCompiler compiler;
     private final List<CompilationUnit> results = new ArrayList<CompilationUnit>();
 
     public DefaultUnitProcessor() {
@@ -109,16 +105,11 @@
 
     public void process(CompilationUnitBuilder builder,
         CompilationUnitDeclaration cud, List<CompiledClass> compiledClasses) {
-      CompilationUnit unit = builder.build(compiledClasses,
-          compiler.computeDependencies(cud),
+      CompilationUnit unit = builder.build(compiledClasses, new Dependencies(),
           Collections.<JsniMethod> emptyList(), new MethodArgNamesLookup(),
           cud.compilationResult().getProblems());
       results.add(unit);
     }
-
-    public void setCompiler(JdtCompiler compiler) {
-      this.compiler = compiler;
-    }
   }
   /**
    * Interface for processing units on the fly during compilation.
@@ -185,7 +176,6 @@
       ICompilationUnit icu = cud.compilationResult().compilationUnit;
       Adapter adapter = (Adapter) icu;
       CompilationUnitBuilder builder = adapter.getBuilder();
-      contentIdMap.put(builder.getLocation(), builder.getContentId());
       processor.process(builder, cud, compiledClasses);
     }
   }
@@ -323,7 +313,6 @@
     try {
       DefaultUnitProcessor processor = new DefaultUnitProcessor();
       JdtCompiler compiler = new JdtCompiler(processor);
-      processor.setCompiler(compiler);
       compiler.doCompile(builders);
       return processor.getResults();
     } finally {
@@ -340,6 +329,8 @@
         | ClassFileConstants.ATTR_LINES | ClassFileConstants.ATTR_SOURCE;
     // Tricks like "boolean stopHere = true;" depend on this setting.
     options.preserveAllLocalVariables = true;
+    // Let the JDT collect compilation unit dependencies
+    options.produceReferenceInfo = true;
 
     // Turn off all warnings, saves some memory / speed.
     options.reportUnusedDeclaredThrownExceptionIncludeDocCommentReference = false;
@@ -402,19 +393,6 @@
    */
   private transient CompilerImpl compilerImpl;
 
-  /**
-   * Maps resource path names to contentId to resolve dependencies.
-   */
-  private final Map<String, ContentId> contentIdMap = new HashMap<String, ContentId>();
-
-  /**
-   * Builders don't compute their contentId until their source is read;
-   * therefore we cannot eagerly lookup their contentId up front. Keep the set
-   * of currently compiling units in a map and lazily fetch their id only when a
-   * dependency is encountered.
-   */
-  private transient Map<String, CompilationUnitBuilder> lazyContentIdMap;
-
   private final Set<String> notPackages = new HashSet<String>();
 
   private final Set<String> packages = new HashSet<String>();
@@ -430,69 +408,13 @@
   public void addCompiledUnit(CompilationUnit unit) {
     addPackages(Shared.getPackageName(unit.getTypeName()).replace('.', '/'));
     addBinaryTypes(unit.getCompiledClasses());
-    contentIdMap.put(unit.getDisplayLocation(), unit.getContentId());
-  }
-
-  public Set<ContentId> computeDependencies(CompilationUnitDeclaration cud) {
-    return computeDependencies(cud, Collections.<String> emptySet());
-  }
-
-  public Set<ContentId> computeDependencies(
-      final CompilationUnitDeclaration cud, Set<String> additionalDependencies) {
-    final Set<ContentId> result = new HashSet<ContentId>();
-    class DependencyVisitor extends TypeRefVisitor {
-      public DependencyVisitor() {
-        super(cud);
-      }
-
-      @Override
-      protected void onBinaryTypeRef(BinaryTypeBinding referencedType,
-          CompilationUnitDeclaration unitOfReferrer, Expression expression) {
-        String fileName = String.valueOf(referencedType.getFileName());
-        addFileReference(fileName);
-      }
-
-      @Override
-      protected void onTypeRef(SourceTypeBinding referencedType,
-          CompilationUnitDeclaration unitOfReferrer) {
-        // Map the referenced type to the target compilation unit file.
-        String fileName = String.valueOf(referencedType.getFileName());
-        addFileReference(fileName);
-      }
-
-      private void addFileReference(String fileName) {
-        if (!fileName.endsWith(".java")) {
-          // Binary-only reference, cannot compute dependency.
-          return;
-        }
-        ContentId contentId = contentIdMap.get(fileName);
-        if (contentId == null) {
-          // This may be a reference to a currently-compiling unit.
-          CompilationUnitBuilder builder = lazyContentIdMap.get(fileName);
-          assert builder != null : "Unexpected source reference ('" + fileName
-              + "') could not find builder";
-          contentId = builder.getContentId();
-        }
-        assert contentId != null;
-        result.add(contentId);
-      }
-    }
-    DependencyVisitor visitor = new DependencyVisitor();
-    cud.traverse(visitor, cud.scope);
-
-    for (String dependency : additionalDependencies) {
-      visitor.addFileReference(dependency);
-    }
-    return Sets.normalize(result);
   }
 
   public boolean doCompile(Collection<CompilationUnitBuilder> builders) {
-    lazyContentIdMap = new HashMap<String, CompilationUnitBuilder>();
     List<ICompilationUnit> icus = new ArrayList<ICompilationUnit>();
     for (CompilationUnitBuilder builder : builders) {
       addPackages(Shared.getPackageName(builder.getTypeName()).replace('.', '/'));
       icus.add(new Adapter(builder));
-      lazyContentIdMap.put(builder.getLocation(), builder);
     }
     if (icus.isEmpty()) {
       return false;
@@ -503,7 +425,6 @@
     compilerImpl.compile(icus.toArray(new ICompilationUnit[icus.size()]));
     compilerImpl = null;
     jdtCompilerEvent.end("# icus", "" + icus.size());
-    lazyContentIdMap = null;
     return true;
   }
 
diff --git a/dev/core/src/com/google/gwt/dev/javac/SourceFileCompilationUnit.java b/dev/core/src/com/google/gwt/dev/javac/SourceFileCompilationUnit.java
index e77f614..af1c3eb 100644
--- a/dev/core/src/com/google/gwt/dev/javac/SourceFileCompilationUnit.java
+++ b/dev/core/src/com/google/gwt/dev/javac/SourceFileCompilationUnit.java
@@ -21,7 +21,6 @@
 
 import java.util.Collection;
 import java.util.List;
-import java.util.Set;
 
 /**
  * A compilation unit that was generated.
@@ -40,7 +39,7 @@
   private final ContentId contentId;
 
   public SourceFileCompilationUnit(Resource sourceFile, ContentId contentId,
-      List<CompiledClass> compiledClasses, Set<ContentId> dependencies,
+      List<CompiledClass> compiledClasses, Dependencies dependencies,
       Collection<? extends JsniMethod> jsniMethods,
       MethodArgNamesLookup methodArgs, CategorizedProblem[] problems) {
     super(compiledClasses, dependencies, jsniMethods, methodArgs, problems);
diff --git a/dev/core/src/com/google/gwt/dev/util/Util.java b/dev/core/src/com/google/gwt/dev/util/Util.java
index 48acd27..77bbb0d 100644
--- a/dev/core/src/com/google/gwt/dev/util/Util.java
+++ b/dev/core/src/com/google/gwt/dev/util/Util.java
@@ -633,6 +633,11 @@
   public static void maybeDumpSource(TreeLogger logger, String location,
       String source, String typeName) {
 
+    if (location.startsWith("/mock/")) {
+      // Unit test mocks, don't dump to disk.
+      return;
+    }
+
     if (isCompilationUnitOnDisk(location)) {
       // Don't write another copy.
       return;
diff --git a/dev/core/test/com/google/gwt/dev/javac/CompilationStateTest.java b/dev/core/test/com/google/gwt/dev/javac/CompilationStateTest.java
index 36c6e18..4203e55 100644
--- a/dev/core/test/com/google/gwt/dev/javac/CompilationStateTest.java
+++ b/dev/core/test/com/google/gwt/dev/javac/CompilationStateTest.java
@@ -31,6 +31,33 @@
  */
 public class CompilationStateTest extends CompilationStateTestBase {
 
+  private static final MockJavaResource FOO_DIFF_API = new MockJavaResource(
+      "test.Foo") {
+    @Override
+    protected CharSequence getContent() {
+      StringBuffer code = new StringBuffer();
+      code.append("package test;\n");
+      code.append("public class Foo {\n");
+      code.append("  public String value() { return \"Foo\"; }\n");
+      code.append("  public String value2() { return \"Foo2\"; }\n");
+      code.append("}\n");
+      return code;
+    }
+  };
+
+  private static final MockJavaResource FOO_SAME_API = new MockJavaResource(
+      "test.Foo") {
+    @Override
+    protected CharSequence getContent() {
+      StringBuffer code = new StringBuffer();
+      code.append("package test;\n");
+      code.append("public class Foo {\n");
+      code.append("  public String value() { return \"Foo2\"; }\n");
+      code.append("}\n");
+      return code;
+    }
+  };
+
   public void testAddGeneratedCompilationUnit() {
     validateCompilationState();
 
@@ -119,9 +146,9 @@
    * another generated unit it depends on can be reused
    */
   public void testComplexCacheInvalidation() {
-    testCachingOverMultipleRefreshes(new MockJavaResource[] {
+    testCachingOverMultipleRefreshes(new MockJavaResource[]{
         JavaResourceBase.FOO, JavaResourceBase.BAR},
-        new MockJavaResource[] {
+        new MockJavaResource[]{
             JavaResourceBase.FOO,
             new TweakedMockJavaResource(JavaResourceBase.BAR)},
         Collections.singleton(JavaResourceBase.FOO.getTypeName()));
@@ -134,19 +161,32 @@
 
   public void testInvalidation() {
     testCachingOverMultipleRefreshes(
-        new MockJavaResource[] {JavaResourceBase.FOO},
-        new MockJavaResource[] {new TweakedMockJavaResource(
-            JavaResourceBase.FOO)}, Collections.<String> emptySet());
+        new MockJavaResource[]{JavaResourceBase.FOO},
+        new MockJavaResource[]{new TweakedMockJavaResource(JavaResourceBase.FOO)},
+        Collections.<String> emptySet());
+  }
+
+  public void testInvalidationNonstructuralDep() {
+    testCachingOverMultipleRefreshes(new MockJavaResource[]{
+        JavaResourceBase.FOO, JavaResourceBase.BAR}, new MockJavaResource[]{
+        FOO_SAME_API, JavaResourceBase.BAR},
+        Collections.singleton(JavaResourceBase.BAR.getTypeName()));
   }
 
   public void testInvalidationOfMultipleUnits() {
-    testCachingOverMultipleRefreshes(new MockJavaResource[] {
-        JavaResourceBase.FOO, JavaResourceBase.BAR}, new MockJavaResource[] {
+    testCachingOverMultipleRefreshes(new MockJavaResource[]{
+        JavaResourceBase.FOO, JavaResourceBase.BAR}, new MockJavaResource[]{
         new TweakedMockJavaResource(JavaResourceBase.FOO),
         new TweakedMockJavaResource(JavaResourceBase.BAR)},
         Collections.<String> emptySet());
   }
 
+  public void testInvalidationStructuralDep() {
+    testCachingOverMultipleRefreshes(new MockJavaResource[]{
+        JavaResourceBase.FOO, JavaResourceBase.BAR}, new MockJavaResource[]{
+        FOO_DIFF_API, JavaResourceBase.BAR}, Collections.<String> emptySet());
+  }
+
   public void testInvalidationWhenSourceUnitsChange() {
     /*
      * Steps: (i) Check compilation state. (ii) Add generated units. (iii)
@@ -165,7 +205,7 @@
     assertNotNull(oldBar);
 
     // change unit in source oracle
-    oracle.replace(new TweakedMockJavaResource(JavaResourceBase.FOO));
+    oracle.replace(FOO_DIFF_API);
     rebuildCompilationState();
 
     /*
@@ -230,15 +270,6 @@
     validateCompilationState();
   }
 
-  /* test if generatedUnits that depend on stale generatedUnits are invalidated */
-  public void testTransitiveInvalidation() {
-    testCachingOverMultipleRefreshes(new MockJavaResource[] {
-        JavaResourceBase.FOO, JavaResourceBase.BAR},
-        new MockJavaResource[] {
-            new TweakedMockJavaResource(JavaResourceBase.FOO),
-            JavaResourceBase.BAR}, Collections.<String> emptySet());
-  }
-
   private void testCaching(MockJavaResource... resources) {
     Set<String> reusedTypes = new HashSet<String>();
     for (MockJavaResource resource : resources) {
diff --git a/dev/core/test/com/google/gwt/dev/javac/CompilationStateTestBase.java b/dev/core/test/com/google/gwt/dev/javac/CompilationStateTestBase.java
index 05589b7..ffcb9c4 100644
--- a/dev/core/test/com/google/gwt/dev/javac/CompilationStateTestBase.java
+++ b/dev/core/test/com/google/gwt/dev/javac/CompilationStateTestBase.java
@@ -115,6 +115,10 @@
     Map<String, CompilationUnit> unitMap = state.getCompilationUnitMap();
     Collection<CompilationUnit> units = state.getCompilationUnits();
 
+    // Validate that we have as many units as resources.
+    assertEquals(oracle.getResources().size() + generatedTypeNames.length,
+        units.size());
+
     // Validate that the collections are consistent with each other.
     assertEquals(new HashSet<CompilationUnit>(unitMap.values()),
         new HashSet<CompilationUnit>(units));
diff --git a/dev/core/test/com/google/gwt/dev/javac/CompilationUnitFileReferenceTest.java b/dev/core/test/com/google/gwt/dev/javac/CompilationUnitFileReferenceTest.java
index b58e759..d041f6e 100644
--- a/dev/core/test/com/google/gwt/dev/javac/CompilationUnitFileReferenceTest.java
+++ b/dev/core/test/com/google/gwt/dev/javac/CompilationUnitFileReferenceTest.java
@@ -45,6 +45,30 @@
     }
   };
 
+  public static final MockJavaResource NOPACKAGE = new MockJavaResource(
+      "NoPackage") {
+    @Override
+    protected CharSequence getContent() {
+      StringBuffer code = new StringBuffer();
+      code.append("public class NoPackage extends test.Top {\n");
+      code.append("  public String value() { return \"NoPackage\"; }\n");
+      code.append("}\n");
+      return code;
+    }
+  };
+
+  public static final MockJavaResource NOPACKAGE2 = new MockJavaResource(
+      "NoPackage2") {
+    @Override
+    protected CharSequence getContent() {
+      StringBuffer code = new StringBuffer();
+      code.append("public class NoPackage2 extends NoPackage {\n");
+      code.append("  public String value() { return \"NoPackage2\"; }\n");
+      code.append("}\n");
+      return code;
+    }
+  };
+
   public static final MockJavaResource OUTER = new MockJavaResource(
       "test.Outer") {
     @Override
@@ -117,8 +141,11 @@
     initializeExpectedDependency(JavaResourceBase.BAR, JavaResourceBase.STRING,
         JavaResourceBase.FOO);
 
-    // TOP has a self-reference
-    initializeExpectedDependency(TOP, JavaResourceBase.STRING, TOP);
+    initializeExpectedDependency(NOPACKAGE, JavaResourceBase.STRING, TOP);
+    initializeExpectedDependency(NOPACKAGE2, NOPACKAGE,
+        JavaResourceBase.STRING, TOP);
+
+    initializeExpectedDependency(TOP, JavaResourceBase.STRING);
     initializeExpectedDependency(TOP3, JavaResourceBase.STRING, TOP);
 
     initializeExpectedDependency(OUTER, JavaResourceBase.STRING);
@@ -155,6 +182,10 @@
     testBinaryBindings(OUTER, STATIC_INNER_SUBCLASS);
   }
 
+  public void testBinaryNoPackage() {
+    testBinaryBindings(TOP, NOPACKAGE, NOPACKAGE2);
+  }
+
   public void testSourceBindingsWithMemberInnerClass() {
     testSourceBindings(OUTER, MEMBER_INNER_SUBCLASS);
   }
@@ -171,6 +202,10 @@
     testSourceBindings(OUTER, STATIC_INNER_SUBCLASS);
   }
 
+  public void testSourceNoPackage() {
+    testSourceBindings(TOP, NOPACKAGE, NOPACKAGE2);
+  }
+
   public void testWithGeneratedUnits() {
     addGeneratedUnits(JavaResourceBase.FOO, JavaResourceBase.BAR);
     assertRefsMatchExpectedRefs(JavaResourceBase.FOO, JavaResourceBase.BAR);
@@ -187,14 +222,21 @@
     Map<String, CompilationUnit> unitMap = state.getCompilationUnitMap();
     for (MockJavaResource file : files) {
       String typeName = file.getTypeName();
-      Set<ContentId> dependencies = unitMap.get(typeName).getDependencies();
-      Set<String> expectedTypeNames = EXPECTED_DEPENDENCIES.get(typeName);
-      assertEquals(expectedTypeNames.size(), dependencies.size());
-      for (String expectedTypeName : expectedTypeNames) {
-        CompilationUnit expectedUnit = unitMap.get(expectedTypeName);
-        assertNotNull(expectedUnit);
-        assertTrue(dependencies.contains(expectedUnit.getContentId()));
+      Dependencies dependencies = unitMap.get(typeName).getDependencies();
+      Set<CompiledClass> classDeps = new HashSet<CompiledClass>();
+      classDeps.addAll(dependencies.qualified.values());
+      classDeps.addAll(dependencies.simple.values());
+      classDeps.remove(null);
+      Set<String> actualTypeNames = new HashSet<String>();
+      for (CompiledClass cc : classDeps) {
+        actualTypeNames.add(cc.getUnit().getTypeName());
       }
+      // Not tracking deps on Object.
+      actualTypeNames.remove("java.lang.Object");
+      // Don't care about self dep.
+      actualTypeNames.remove(typeName);
+      Set<String> expectedTypeNames = EXPECTED_DEPENDENCIES.get(typeName);
+      assertEquals(expectedTypeNames, actualTypeNames);
     }
   }