Add support for having multiple definitions in app

Bug: 214382176
Change-Id: I68c090b9b6594d6f168ac9558a04093d16829208
diff --git a/src/main/java/com/android/tools/r8/JarSizeCompare.java b/src/main/java/com/android/tools/r8/JarSizeCompare.java
index e520d1b..60a8e08 100644
--- a/src/main/java/com/android/tools/r8/JarSizeCompare.java
+++ b/src/main/java/com/android/tools/r8/JarSizeCompare.java
@@ -26,6 +26,7 @@
 import java.nio.file.Path;
 import java.nio.file.Paths;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.HashMap;
@@ -131,7 +132,7 @@
   }
 
   private Map<String, DexProgramClass> translateClassNames(
-      DexApplication input, List<DexProgramClass> classes) {
+      DexApplication input, Collection<DexProgramClass> classes) {
     Map<String, DexProgramClass> result = new HashMap<>();
     ClassNameMapper classNameMapper = input.getProguardMap();
     for (DexProgramClass programClass : classes) {
diff --git a/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java b/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java
index 5d26e0a..1eb78d1 100644
--- a/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java
+++ b/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java
@@ -383,7 +383,7 @@
       return OriginalSourceFiles.unreachable();
     }
     // Clear all source files so as not to collect the original files.
-    List<DexProgramClass> classes = appView.appInfo().classes();
+    Collection<DexProgramClass> classes = appView.appInfo().classes();
     Map<DexType, DexString> originalSourceFiles = new HashMap<>(classes.size());
     for (DexProgramClass clazz : classes) {
       DexString originalSourceFile = clazz.getSourceFile();
diff --git a/src/main/java/com/android/tools/r8/graph/AppInfo.java b/src/main/java/com/android/tools/r8/graph/AppInfo.java
index ef10e8d..1fac1e6 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfo.java
@@ -11,7 +11,7 @@
 import com.android.tools.r8.synthesis.SyntheticItems;
 import com.android.tools.r8.utils.BooleanBox;
 import com.android.tools.r8.utils.InternalOptions;
-import java.util.List;
+import java.util.Collection;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 import java.util.function.Consumer;
@@ -122,12 +122,12 @@
     return syntheticItems;
   }
 
-  public List<DexProgramClass> classes() {
+  public Collection<DexProgramClass> classes() {
     assert checkIfObsolete();
     return app.classes();
   }
 
-  public List<DexProgramClass> classesWithDeterministicOrder() {
+  public Collection<DexProgramClass> classesWithDeterministicOrder() {
     assert checkIfObsolete();
     return app.classesWithDeterministicOrder();
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexApplication.java b/src/main/java/com/android/tools/r8/graph/DexApplication.java
index e08f2ed..feedd6c 100644
--- a/src/main/java/com/android/tools/r8/graph/DexApplication.java
+++ b/src/main/java/com/android/tools/r8/graph/DexApplication.java
@@ -94,9 +94,9 @@
   // may process classes concurrently and fail-fast on the first error.
   private static class ReorderBox<T> {
 
-    private List<T> classes;
+    private Collection<T> classes;
 
-    ReorderBox(List<T> classes) {
+    ReorderBox(Collection<T> classes) {
       this.classes = classes;
     }
 
@@ -109,20 +109,20 @@
       return true;
     }
 
-    List<T> getClasses() {
+    Collection<T> getClasses() {
       return classes;
     }
   }
 
-  abstract List<DexProgramClass> programClasses();
+  abstract Collection<DexProgramClass> programClasses();
 
-  public List<DexProgramClass> classes() {
+  public Collection<DexProgramClass> classes() {
     ReorderBox<DexProgramClass> box = new ReorderBox<>(programClasses());
     assert box.reorderClasses();
     return box.getClasses();
   }
 
-  public List<DexProgramClass> classesWithDeterministicOrder() {
+  public Collection<DexProgramClass> classesWithDeterministicOrder() {
     return classesWithDeterministicOrder(new ArrayList<>(programClasses()));
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/DirectMappedDexApplication.java b/src/main/java/com/android/tools/r8/graph/DirectMappedDexApplication.java
index 8e96fba..1f98402 100644
--- a/src/main/java/com/android/tools/r8/graph/DirectMappedDexApplication.java
+++ b/src/main/java/com/android/tools/r8/graph/DirectMappedDexApplication.java
@@ -6,21 +6,19 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.graph;
 
-import static com.android.tools.r8.graph.ClassResolutionResult.NoResolutionResult.noResult;
-
 import com.android.tools.r8.DataResourceProvider;
 import com.android.tools.r8.graph.LazyLoadedDexApplication.AllClasses;
-import com.android.tools.r8.graph.classmerging.MergedClasses;
 import com.android.tools.r8.naming.ClassNameMapper;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.Timing;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSortedMap;
 import java.util.ArrayList;
 import java.util.Collection;
-import java.util.Collections;
 import java.util.IdentityHashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.function.Consumer;
 
 public class DirectMappedDexApplication extends DexApplication {
 
@@ -28,64 +26,100 @@
   // and debugging purposes.
   private final Map<Code, DexEncodedMethod> codeOwners = new IdentityHashMap<>();
 
-  // Unmodifiable mapping of all types to their definitions.
-  private final Map<DexType, DexClass> allClasses;
   // Collections of the three different types for iteration.
-  private final ImmutableList<DexProgramClass> programClasses;
-  private final ImmutableList<DexClasspathClass> classpathClasses;
-  private final ImmutableList<DexLibraryClass> libraryClasses;
+  private final ImmutableSortedMap<DexType, DexProgramClass> programClasses;
+  private final ImmutableSortedMap<DexType, DexClasspathClass> classpathClasses;
+  private final ImmutableSortedMap<DexType, DexLibraryClass> libraryClasses;
 
   private DirectMappedDexApplication(
       ClassNameMapper proguardMap,
       DexApplicationReadFlags flags,
-      Map<DexType, DexClass> allClasses,
-      ImmutableList<DexProgramClass> programClasses,
-      ImmutableList<DexClasspathClass> classpathClasses,
-      ImmutableList<DexLibraryClass> libraryClasses,
+      ImmutableSortedMap<DexType, DexProgramClass> programClasses,
+      ImmutableSortedMap<DexType, DexClasspathClass> classpathClasses,
+      ImmutableSortedMap<DexType, DexLibraryClass> libraryClasses,
       ImmutableList<DataResourceProvider> dataResourceProviders,
       InternalOptions options,
       DexString highestSortingString,
       Timing timing) {
     super(proguardMap, flags, dataResourceProviders, options, highestSortingString, timing);
-    this.allClasses = Collections.unmodifiableMap(allClasses);
     this.programClasses = programClasses;
     this.classpathClasses = classpathClasses;
     this.libraryClasses = libraryClasses;
   }
 
-  public Collection<DexClass> allClasses() {
-    return allClasses.values();
-  }
-
-  public List<DexClasspathClass> classpathClasses() {
-    return classpathClasses;
+  public Collection<DexClasspathClass> classpathClasses() {
+    return classpathClasses.values();
   }
 
   @Override
-  List<DexProgramClass> programClasses() {
-    return programClasses;
+  Collection<DexProgramClass> programClasses() {
+    return programClasses.values();
   }
 
-  public List<DexLibraryClass> libraryClasses() {
-    return libraryClasses;
+  public Collection<DexLibraryClass> libraryClasses() {
+    return libraryClasses.values();
+  }
+
+  @Override
+  public Collection<DexProgramClass> classesWithDeterministicOrder() {
+    return programClasses.values();
   }
 
   @Override
   public ClassResolutionResult contextIndependentDefinitionForWithResolutionResult(DexType type) {
-    DexClass foundClass = definitionFor(type);
-    return foundClass == null ? noResult() : foundClass;
+    ClassResolutionResult.Builder builder = ClassResolutionResult.builder();
+    if (libraryClasses != null) {
+      addClassToBuilderIfNotNull(libraryClasses.get(type), builder::add);
+    }
+    if (programClasses == null
+        || !addClassToBuilderIfNotNull(programClasses.get(type), builder::add)) {
+      // When looking up a type that exists both on program path and classpath, we assume the
+      // program class is taken and only if not present will look at classpath.
+      if (classpathClasses != null) {
+        addClassToBuilderIfNotNull(classpathClasses.get(type), builder::add);
+      }
+    }
+    return builder.build();
+  }
+
+  private <T extends DexClass> boolean addClassToBuilderIfNotNull(T clazz, Consumer<T> adder) {
+    if (clazz != null) {
+      adder.accept(clazz);
+      return true;
+    } else {
+      return false;
+    }
   }
 
   @Override
   public DexClass definitionFor(DexType type) {
     assert type.isClassType() : "Cannot lookup definition for type: " + type;
-    return allClasses.get(type);
+    DexClass clazz = null;
+    if (options.lookupLibraryBeforeProgram) {
+      if (libraryClasses != null) {
+        clazz = libraryClasses.get(type);
+      }
+      if (clazz == null) {
+        clazz = programClasses.get(type);
+      }
+      if (clazz == null && classpathClasses != null) {
+        clazz = classpathClasses.get(type);
+      }
+    } else {
+      clazz = programClasses.get(type);
+      if (clazz == null && classpathClasses != null) {
+        clazz = classpathClasses.get(type);
+      }
+      if (clazz == null && libraryClasses != null) {
+        clazz = libraryClasses.get(type);
+      }
+    }
+    return clazz;
   }
 
   @Override
   public DexProgramClass programDefinitionFor(DexType type) {
-    // The direct mapped application has no duplicates so this coincides with definitionFor.
-    return DexProgramClass.asProgramClassOrNull(definitionFor(type));
+    return programClasses.get(type);
   }
 
   @Override
@@ -119,21 +153,8 @@
     return true;
   }
 
-  public boolean verifyNothingToRewrite(AppView<?> appView, GraphLens lens) {
-    assert allClasses.keySet().stream()
-        .allMatch(
-            type ->
-                lens.lookupType(type) == type
-                    || MergedClasses.hasBeenMergedIntoDifferentType(
-                        appView.verticallyMergedClasses(), type)
-                    || MergedClasses.hasBeenMergedIntoDifferentType(
-                        appView.horizontallyMergedClasses(), type));
-    assert verifyCodeObjectsOwners();
-    return true;
-  }
-
   private boolean mappingIsValid(
-      List<DexProgramClass> classesBeforeLensApplication, GraphLens lens) {
+      Collection<DexProgramClass> classesBeforeLensApplication, GraphLens lens) {
     // The lens might either map to a different type that is already present in the application
     // (e.g. relinking a type) or it might encode a type that was renamed, in which case the
     // original type will point to a definition that was renamed.
@@ -168,7 +189,7 @@
 
   public boolean verifyCodeObjectsOwners() {
     codeOwners.clear();
-    for (DexProgramClass clazz : programClasses) {
+    for (DexProgramClass clazz : programClasses()) {
       for (DexEncodedMethod method :
           clazz.methods(DexEncodedMethod::isNonAbstractNonNativeMethod)) {
         Code code = method.getCode();
@@ -188,19 +209,19 @@
 
   public static class Builder extends DexApplication.Builder<Builder> {
 
-    private ImmutableList<DexClasspathClass> classpathClasses;
-    private ImmutableList<DexLibraryClass> libraryClasses;
+    private Map<DexType, DexClasspathClass> classpathClasses;
+    private Map<DexType, DexLibraryClass> libraryClasses;
 
     private final List<DexClasspathClass> pendingClasspathClasses = new ArrayList<>();
+    private final List<DexProgramClass> pendingNonProgramRemovals = new ArrayList<>();
 
     Builder(LazyLoadedDexApplication application) {
       super(application);
       // As a side-effect, this will force-load all classes.
       AllClasses allClasses = application.loadAllClasses();
-      classpathClasses = allClasses.getClasspathClasses();
-      libraryClasses = allClasses.getLibraryClasses();
-      replaceProgramClasses(allClasses.getProgramClasses());
-      replaceClasspathClasses(allClasses.getClasspathClasses());
+      classpathClasses = new IdentityHashMap<>(allClasses.getClasspathClasses());
+      libraryClasses = new IdentityHashMap<>(allClasses.getLibraryClasses());
+      replaceProgramClasses(allClasses.getProgramClasses().values());
     }
 
     private Builder(DirectMappedDexApplication application) {
@@ -222,32 +243,7 @@
     @Override
     public void addProgramClassPotentiallyOverridingNonProgramClass(DexProgramClass clazz) {
       addProgramClass(clazz);
-      if (containsType(clazz.type, libraryClasses)) {
-        replaceLibraryClasses(withoutType(clazz.type, libraryClasses));
-        return;
-      }
-      if (containsType(clazz.type, classpathClasses)) {
-        replaceClasspathClasses(withoutType(clazz.type, classpathClasses));
-      }
-    }
-
-    private boolean containsType(DexType type, List<? extends DexClass> classes) {
-      for (DexClass clazz : classes) {
-        if (clazz.type == type) {
-          return true;
-        }
-      }
-      return false;
-    }
-
-    private <T extends DexClass> ImmutableList<T> withoutType(DexType type, List<T> classes) {
-      ImmutableList.Builder<T> builder = ImmutableList.builder();
-      for (T clazz : classes) {
-        if (clazz.type != type) {
-          builder.add(clazz);
-        }
-      }
-      return builder.build();
+      pendingNonProgramRemovals.add(clazz);
     }
 
     @Override
@@ -260,76 +256,69 @@
       return self();
     }
 
-    public Builder addClasspathClasses(Collection<DexClasspathClass> classes) {
-      pendingClasspathClasses.addAll(classes);
-      return self();
-    }
-
     private void commitPendingClasspathClasses() {
       if (!pendingClasspathClasses.isEmpty()) {
-        classpathClasses =
-            ImmutableList.<DexClasspathClass>builder()
-                .addAll(classpathClasses)
-                .addAll(pendingClasspathClasses)
-                .build();
+        pendingClasspathClasses.forEach(
+            clazz -> {
+              DexClasspathClass old = classpathClasses.put(clazz.type, clazz);
+              assert old == null;
+            });
         pendingClasspathClasses.clear();
       }
     }
 
-    public List<DexClasspathClass> getClasspathClasses() {
-      commitPendingClasspathClasses();
-      return classpathClasses;
-    }
-
     public Builder replaceClasspathClasses(Collection<DexClasspathClass> newClasspathClasses) {
-      assert newClasspathClasses != null;
-      classpathClasses = ImmutableList.copyOf(newClasspathClasses);
+      classpathClasses = new IdentityHashMap<>();
+      newClasspathClasses.forEach(clazz -> classpathClasses.put(clazz.type, clazz));
       pendingClasspathClasses.clear();
       return self();
     }
 
-    public Builder replaceLibraryClasses(Collection<DexLibraryClass> libraryClasses) {
-      this.libraryClasses = ImmutableList.copyOf(libraryClasses);
-      return self();
-    }
-
-    public Builder addLibraryClasses(Collection<DexLibraryClass> classes) {
-      libraryClasses =
-          ImmutableList.<DexLibraryClass>builder().addAll(libraryClasses).addAll(classes).build();
+    public Builder replaceLibraryClasses(Collection<DexLibraryClass> newLibraryClasses) {
+      libraryClasses = new IdentityHashMap<>();
+      newLibraryClasses.forEach(clazz -> libraryClasses.put(clazz.type, clazz));
       return self();
     }
 
     @Override
     public DirectMappedDexApplication build() {
-      // Rebuild the map. This will fail if keys are not unique.
-      // TODO(zerny): Consider not rebuilding the map if no program classes are added.
-      Map<DexType, DexClass> allClasses =
-          new IdentityHashMap<>(
-              getProgramClasses().size() + getClasspathClasses().size() + libraryClasses.size());
-      // Note: writing classes in reverse priority order, so a duplicate will be correctly ordered.
-      // There should never be duplicates and that is asserted in the addAll subroutine.
-      addAll(allClasses, libraryClasses);
-      addAll(allClasses, getClasspathClasses());
-      addAll(allClasses, getProgramClasses());
+      // If there are pending non-program removals or pending class path classes, create a new map
+      // to ensure not modifying an immutable collection.
+      if (!pendingNonProgramRemovals.isEmpty()) {
+        libraryClasses = new IdentityHashMap<>(libraryClasses);
+        classpathClasses = new IdentityHashMap<>(classpathClasses);
+      } else if (!pendingClasspathClasses.isEmpty()) {
+        classpathClasses = new IdentityHashMap<>(classpathClasses);
+      }
+      commitPendingClasspathClasses();
+      pendingNonProgramRemovals.forEach(
+          clazz -> {
+            libraryClasses.remove(clazz.type);
+            classpathClasses.remove(clazz.type);
+          });
+      pendingNonProgramRemovals.clear();
+      ImmutableSortedMap.Builder<DexType, DexProgramClass> programClassMap =
+          new ImmutableSortedMap.Builder<>(DexType::compareTo);
+      getProgramClasses().forEach(clazz -> programClassMap.put(clazz.type, clazz));
       return new DirectMappedDexApplication(
           proguardMap,
           flags,
-          allClasses,
-          ImmutableList.copyOf(getProgramClasses()),
-          ImmutableList.copyOf(getClasspathClasses()),
-          libraryClasses,
+          programClassMap.build(),
+          getImmutableMap(classpathClasses),
+          getImmutableMap(libraryClasses),
           ImmutableList.copyOf(dataResourceProviders),
           options,
           highestSortingString,
           timing);
     }
-  }
 
-  private static <T extends DexClass> void addAll(
-      Map<DexType, DexClass> allClasses, Iterable<T> toAdd) {
-    for (DexClass clazz : toAdd) {
-      DexClass old = allClasses.put(clazz.type, clazz);
-      assert old == null : "Class " + old.type.toString() + " was already present.";
+    private <T extends DexClass> ImmutableSortedMap<DexType, T> getImmutableMap(
+        Map<DexType, T> map) {
+      if (map instanceof ImmutableSortedMap) {
+        return (ImmutableSortedMap<DexType, T>) map;
+      } else {
+        return ImmutableSortedMap.copyOf(map);
+      }
     }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/GenericSignatureCorrectnessHelper.java b/src/main/java/com/android/tools/r8/graph/GenericSignatureCorrectnessHelper.java
index 8fa722d..950e824 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignatureCorrectnessHelper.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignatureCorrectnessHelper.java
@@ -26,6 +26,7 @@
 import com.android.tools.r8.shaking.KeepMethodInfo;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.ListUtils;
+import java.util.Collection;
 import java.util.List;
 import java.util.function.Consumer;
 import java.util.function.Function;
@@ -106,7 +107,7 @@
     return new GenericSignatureCorrectnessHelper(appView, contextBuilder, Mode.VERIFY);
   }
 
-  public SignatureEvaluationResult run(List<DexProgramClass> programClasses) {
+  public SignatureEvaluationResult run(Collection<DexProgramClass> programClasses) {
     if (appView.options().disableGenericSignatureValidation
         || !appView.options().parseSignatureAttribute()) {
       return VALID;
diff --git a/src/main/java/com/android/tools/r8/graph/LazyLoadedDexApplication.java b/src/main/java/com/android/tools/r8/graph/LazyLoadedDexApplication.java
index 772227c..35a2dd6 100644
--- a/src/main/java/com/android/tools/r8/graph/LazyLoadedDexApplication.java
+++ b/src/main/java/com/android/tools/r8/graph/LazyLoadedDexApplication.java
@@ -15,13 +15,13 @@
 import com.android.tools.r8.utils.ProgramClassCollection;
 import com.android.tools.r8.utils.Timing;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Sets;
-import java.util.Collections;
-import java.util.IdentityHashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.function.Consumer;
+import java.util.function.Function;
 import java.util.stream.Collectors;
 
 public class LazyLoadedDexApplication extends DexApplication {
@@ -119,92 +119,102 @@
   static class AllClasses {
 
     // Mapping of all types to their definitions.
-    private final Map<DexType, DexClass> allClasses;
     // Collections of the three different types for iteration.
-    private final ImmutableList<DexProgramClass> programClasses;
-    private final ImmutableList<DexClasspathClass> classpathClasses;
-    private final ImmutableList<DexLibraryClass> libraryClasses;
+    private final ImmutableMap<DexType, DexProgramClass> programClasses;
+    private final ImmutableMap<DexType, DexClasspathClass> classpathClasses;
+    private final ImmutableMap<DexType, DexLibraryClass> libraryClasses;
 
     AllClasses(
         LibraryClassCollection libraryClassesLoader,
         ClasspathClassCollection classpathClassesLoader,
         ProgramClassCollection programClassesLoader,
         InternalOptions options) {
-      int expectedMaxSize = 0;
 
       // Force-load library classes.
-      Map<DexType, DexLibraryClass> allLibraryClasses = null;
+      ImmutableMap<DexType, DexLibraryClass> allLibraryClasses;
       if (libraryClassesLoader != null) {
         libraryClassesLoader.forceLoad(type -> true);
         allLibraryClasses = libraryClassesLoader.getAllClassesInMap();
-        expectedMaxSize += allLibraryClasses.size();
+      } else {
+        allLibraryClasses = ImmutableMap.of();
       }
 
       // Program classes should be fully loaded.
       assert programClassesLoader != null;
       assert programClassesLoader.isFullyLoaded();
       programClassesLoader.forceLoad(type -> true);
-      Map<DexType, DexProgramClass> allProgramClasses = programClassesLoader.getAllClassesInMap();
-      expectedMaxSize += allProgramClasses.size();
+      ImmutableMap<DexType, DexProgramClass> allProgramClasses =
+          programClassesLoader.getAllClassesInMap();
 
       // Force-load classpath classes.
-      Map<DexType, DexClasspathClass> allClasspathClasses = null;
+      ImmutableMap<DexType, DexClasspathClass> allClasspathClasses;
       if (classpathClassesLoader != null) {
         classpathClassesLoader.forceLoad(type -> true);
         allClasspathClasses = classpathClassesLoader.getAllClassesInMap();
-        expectedMaxSize += allClasspathClasses.size();
+      } else {
+        allClasspathClasses = ImmutableMap.of();
       }
 
       // Collect loaded classes in the precedence order library classes, program classes and
       // class path classes or program classes, classpath classes and library classes depending
       // on the configured lookup order.
-      Map<DexType, DexClass> prioritizedClasses = new IdentityHashMap<>(expectedMaxSize);
-      if (options.lookupLibraryBeforeProgram) {
-        libraryClasses = fillPrioritizedClasses(allLibraryClasses, prioritizedClasses, options);
-        programClasses = fillPrioritizedClasses(allProgramClasses, prioritizedClasses, options);
-        classpathClasses = fillPrioritizedClasses(allClasspathClasses, prioritizedClasses, options);
+      if (options.loadAllClassDefinitions) {
+        libraryClasses = allLibraryClasses;
+        programClasses = allProgramClasses;
+        classpathClasses = allClasspathClasses;
       } else {
-        programClasses = fillPrioritizedClasses(allProgramClasses, prioritizedClasses, options);
-        classpathClasses = fillPrioritizedClasses(allClasspathClasses, prioritizedClasses, options);
-        libraryClasses = fillPrioritizedClasses(allLibraryClasses, prioritizedClasses, options);
+        if (options.lookupLibraryBeforeProgram) {
+          libraryClasses = fillPrioritizedClasses(allLibraryClasses, type -> null, options);
+          programClasses = fillPrioritizedClasses(allProgramClasses, libraryClasses::get, options);
+          classpathClasses =
+              fillPrioritizedClasses(
+                  allClasspathClasses,
+                  type -> {
+                    DexLibraryClass clazz = libraryClasses.get(type);
+                    return clazz != null ? clazz : programClasses.get(type);
+                  },
+                  options);
+        } else {
+          programClasses = fillPrioritizedClasses(allProgramClasses, type -> null, options);
+          classpathClasses =
+              fillPrioritizedClasses(allClasspathClasses, programClasses::get, options);
+          libraryClasses =
+              fillPrioritizedClasses(
+                  allLibraryClasses,
+                  type -> {
+                    DexProgramClass clazz = programClasses.get(type);
+                    return clazz != null ? clazz : classpathClasses.get(type);
+                  },
+                  options);
+        }
       }
-
-      allClasses = Collections.unmodifiableMap(prioritizedClasses);
-
-      assert prioritizedClasses.size()
-          == libraryClasses.size() + classpathClasses.size() + programClasses.size();
     }
 
-    public Map<DexType, DexClass> getAllClasses() {
-      return allClasses;
-    }
-
-    public ImmutableList<DexProgramClass> getProgramClasses() {
+    public ImmutableMap<DexType, DexProgramClass> getProgramClasses() {
       return programClasses;
     }
 
-    public ImmutableList<DexClasspathClass> getClasspathClasses() {
+    public ImmutableMap<DexType, DexClasspathClass> getClasspathClasses() {
       return classpathClasses;
     }
 
-    public ImmutableList<DexLibraryClass> getLibraryClasses() {
+    public ImmutableMap<DexType, DexLibraryClass> getLibraryClasses() {
       return libraryClasses;
     }
   }
 
-  private static <T extends DexClass> ImmutableList<T> fillPrioritizedClasses(
+  private static <T extends DexClass> ImmutableMap<DexType, T> fillPrioritizedClasses(
       Map<DexType, T> classCollection,
-      Map<DexType, DexClass> prioritizedClasses,
+      Function<DexType, DexClass> getExisting,
       InternalOptions options) {
     if (classCollection != null) {
       Set<DexType> javaLibraryOverride = Sets.newIdentityHashSet();
-      ImmutableList.Builder<T> builder = ImmutableList.builder();
+      ImmutableMap.Builder<DexType, T> builder = ImmutableMap.builder();
       classCollection.forEach(
           (type, clazz) -> {
-            DexClass other = prioritizedClasses.get(type);
+            DexClass other = getExisting.apply(type);
             if (other == null) {
-              prioritizedClasses.put(type, clazz);
-              builder.add(clazz);
+              builder.put(type, clazz);
             } else if (type.getPackageName().startsWith("java.")
                 && (clazz.isLibraryClass() || other.isLibraryClass())) {
               javaLibraryOverride.add(type);
@@ -215,7 +225,7 @@
       }
       return builder.build();
     } else {
-      return ImmutableList.of();
+      return ImmutableMap.of();
     }
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java b/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java
index 2382abc..b61f288 100644
--- a/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java
@@ -9,7 +9,6 @@
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Sets;
 import java.util.ArrayDeque;
-import java.util.Collection;
 import java.util.Deque;
 import java.util.HashSet;
 import java.util.IdentityHashMap;
@@ -49,11 +48,15 @@
   }
 
   public static SubtypingInfo create(AppInfoWithClassHierarchy appInfo) {
-    return create(appInfo.app().asDirect().allClasses(), appInfo);
+    DirectMappedDexApplication directApp = appInfo.app().asDirect();
+    return create(
+        Iterables.concat(
+            directApp.programClasses(), directApp.classpathClasses(), directApp.libraryClasses()),
+        appInfo);
   }
 
   public static SubtypingInfo create(
-      Collection<? extends DexClass> classes, DexDefinitionSupplier definitions) {
+      Iterable<? extends DexClass> classes, DexDefinitionSupplier definitions) {
     Map<DexType, TypeInfo> typeInfo = new ConcurrentHashMap<>();
     Map<DexType, Set<DexType>> subtypeMap = new IdentityHashMap<>();
     populateSubtypeMap(classes, subtypeMap, typeInfo, definitions);
@@ -117,7 +120,7 @@
   }
 
   private static void populateSubtypeMap(
-      Collection<? extends DexClass> classes,
+      Iterable<? extends DexClass> classes,
       Map<DexType, Set<DexType>> map,
       Map<DexType, TypeInfo> typeInfo,
       DexDefinitionSupplier definitionSupplier) {
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java
index 4a3f2ff..0c36573 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java
@@ -29,10 +29,10 @@
 import com.google.common.collect.HashBiMap;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Sets;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.IdentityHashMap;
 import java.util.LinkedHashSet;
-import java.util.List;
 import java.util.Map;
 import java.util.Optional;
 import java.util.Set;
@@ -124,7 +124,7 @@
    * </ul>
    */
   public HorizontalClassMergerGraphLens fixupTypeReferences() {
-    List<DexProgramClass> classes = appView.appInfo().classesWithDeterministicOrder();
+    Collection<DexProgramClass> classes = appView.appInfo().classesWithDeterministicOrder();
     Iterables.filter(classes, DexProgramClass::isInterface).forEach(this::fixupInterfaceClass);
     classes.forEach(this::fixupAttributes);
     classes.forEach(this::fixupProgramClassSuperTypes);
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/ClassConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/ClassConverter.java
index fa59829..fe2c785 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/ClassConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/ClassConverter.java
@@ -17,6 +17,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.List;
 import java.util.Set;
 import java.util.concurrent.ExecutionException;
@@ -62,7 +63,7 @@
   private void internalConvertClasses(
       ClassConverterResult.Builder resultBuilder, ExecutorService executorService)
       throws ExecutionException {
-    List<DexProgramClass> classes = appView.appInfo().classes();
+    Collection<DexProgramClass> classes = appView.appInfo().classes();
 
       CfClassSynthesizerDesugaringEventConsumer classSynthesizerEventConsumer =
           new CfClassSynthesizerDesugaringEventConsumer();
diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index 8681f33..15f53e2 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -57,7 +57,6 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.DexValue;
 import com.android.tools.r8.graph.DirectMappedDexApplication;
-import com.android.tools.r8.graph.DirectMappedDexApplication.Builder;
 import com.android.tools.r8.graph.EnclosingMethodAttribute;
 import com.android.tools.r8.graph.FieldAccessInfoCollectionImpl;
 import com.android.tools.r8.graph.FieldAccessInfoImpl;
@@ -3801,10 +3800,14 @@
 
     // Add just referenced non-program types. We can't replace the program classes at this point as
     // they are needed in tree pruning.
-    Builder appBuilder = appInfo.app().asDirect().builder();
-    appBuilder.replaceLibraryClasses(libraryClasses);
-    appBuilder.replaceClasspathClasses(classpathClasses);
-    DirectMappedDexApplication app = appBuilder.build();
+    DirectMappedDexApplication app =
+        appInfo
+            .app()
+            .asDirect()
+            .builder()
+            .replaceLibraryClasses(libraryClasses)
+            .replaceClasspathClasses(classpathClasses)
+            .build();
 
     // Verify the references on the pruned application after type synthesis.
     assert verifyReferences(app);
diff --git a/src/main/java/com/android/tools/r8/shaking/TreePruner.java b/src/main/java/com/android/tools/r8/shaking/TreePruner.java
index db5dcdc..f3391c8 100644
--- a/src/main/java/com/android/tools/r8/shaking/TreePruner.java
+++ b/src/main/java/com/android/tools/r8/shaking/TreePruner.java
@@ -89,7 +89,7 @@
         .replaceProgramClasses(getNewProgramClasses(application.classesWithDeterministicOrder()));
   }
 
-  private List<DexProgramClass> getNewProgramClasses(List<DexProgramClass> classes) {
+  private List<DexProgramClass> getNewProgramClasses(Collection<DexProgramClass> classes) {
     AppInfoWithLiveness appInfo = appView.appInfo();
     InternalOptions options = appView.options();
     List<DexProgramClass> newClasses = new ArrayList<>();
diff --git a/src/main/java/com/android/tools/r8/utils/ClassMap.java b/src/main/java/com/android/tools/r8/utils/ClassMap.java
index 23d71ee..506a990 100644
--- a/src/main/java/com/android/tools/r8/utils/ClassMap.java
+++ b/src/main/java/com/android/tools/r8/utils/ClassMap.java
@@ -147,7 +147,7 @@
     return loadedClasses;
   }
 
-  public Map<DexType, T> getAllClassesInMap() {
+  public ImmutableMap<DexType, T> getAllClassesInMap() {
     if (classProvider.get() != null) {
       throw new Unreachable("Getting all classes from not fully loaded collection.");
     }
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index 066ca9f..feac7f5 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -563,6 +563,8 @@
   // public boolean lookupLibraryBeforeProgram =
   //     System.getProperty("com.android.tools.r8.lookupProgramBeforeLibrary") == null;
 
+  public boolean loadAllClassDefinitions = false;
+
   // Whether or not to check for valid multi-dex builds.
   //
   // For min-api levels that did not support native multi-dex the user should provide a main dex