standalone tool to split dex archives into shards to merge.

factor out dex file limit tracking into shared helper class.
RELNOTES: None.

PiperOrigin-RevId: 172826493

7 files changed, 465 insertions, 121 deletions

diff --git a/src/tools/android/java/com/google/devtools/build/android/dexer/BUILD.tools b/src/tools/android/java/com/google/devtools/build/android/dexer/BUILD.tools
index dd5be15715..51beb3df39 100644
--- a/src/tools/android/java/com/google/devtools/build/android/dexer/BUILD.tools
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/BUILD.tools
@@ -29,3 +29,10 @@ java_binary(
     visibility = ["//tools/android:__subpackages__"],
     runtime_deps = [":dexer"],
 )
+
+java_binary(
+    name = "DexFileSplitter",
+    main_class = "com.google.devtools.build.android.dexer.DexFileSplitter",
+    visibility = ["//tools/android:__subpackages__"],
+    runtime_deps = [":dexer"],
+)
diff --git a/src/tools/android/java/com/google/devtools/build/android/dexer/DexFileAggregator.java b/src/tools/android/java/com/google/devtools/build/android/dexer/DexFileAggregator.java
index aff159ec49..dcb0dec15f 100644
--- a/src/tools/android/java/com/google/devtools/build/android/dexer/DexFileAggregator.java
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/DexFileAggregator.java
@@ -17,16 +17,10 @@ import static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.base.Preconditions.checkState;
 
 import com.android.dex.Dex;
-import com.android.dex.FieldId;
-import com.android.dex.MethodId;
-import com.android.dex.ProtoId;
-import com.android.dex.TypeList;
 import com.android.dx.command.dexer.DxContext;
 import com.android.dx.merge.CollisionPolicy;
 import com.android.dx.merge.DexMerger;
-import com.google.auto.value.AutoValue;
 import com.google.common.base.Throwables;
-import com.google.common.collect.ImmutableList;
 import com.google.common.util.concurrent.Futures;
 import com.google.common.util.concurrent.ListenableFuture;
 import com.google.common.util.concurrent.ListeningExecutorService;
@@ -35,7 +29,6 @@ import java.io.IOException;
 import java.nio.BufferOverflowException;
 import java.util.ArrayList;
 import java.util.Arrays;
-import java.util.HashSet;
 import java.util.concurrent.Callable;
 import java.util.concurrent.ExecutionException;
 import java.util.zip.ZipEntry;
@@ -52,16 +45,14 @@ class DexFileAggregator implements Closeable {
   private static final String DEX_EXTENSION = ".dex";
 
   private final ArrayList<Dex> currentShard = new ArrayList<>();
-  private final HashSet<FieldDescriptor> fieldsInCurrentShard = new HashSet<>();
-  private final HashSet<MethodDescriptor> methodsInCurrentShard = new HashSet<>();
   private final boolean forceJumbo;
-  private final int maxNumberOfIdxPerDex;
   private final int wasteThresholdPerDex;
   private final MultidexStrategy multidex;
   private final DxContext context;
   private final ListeningExecutorService executor;
   private final DexFileArchive dest;
   private final String dexPrefix;
+  private final DexLimitTracker tracker;
 
   private int nextDexFileIndex = 0;
   private ListenableFuture<Void> lastWriter = Futures.<Void>immediateFuture(null);
@@ -80,44 +71,27 @@ class DexFileAggregator implements Closeable {
     this.executor = executor;
     this.multidex = multidex;
     this.forceJumbo = forceJumbo;
-    this.maxNumberOfIdxPerDex = maxNumberOfIdxPerDex;
     this.wasteThresholdPerDex = wasteThresholdPerDex;
     this.dexPrefix = dexPrefix;
+    tracker = new DexLimitTracker(maxNumberOfIdxPerDex);
   }
 
   public DexFileAggregator add(Dex dexFile) {
     if (multidex.isMultidexAllowed()) {
       // To determine whether currentShard is "full" we track unique field and method signatures,
       // which predicts precisely the number of field and method indices.
-      // Update xxxInCurrentShard first, then check if we overflowed.
-      // This can yield slightly larger .dex files than checking first, at the price of having to
-      // process the class that put us over the edge twice.
-      trackFieldsAndMethods(dexFile);
-      if (!currentShard.isEmpty()
-          && (fieldsInCurrentShard.size() > maxNumberOfIdxPerDex
-              || methodsInCurrentShard.size() > maxNumberOfIdxPerDex)) {
+      if (tracker.track(dexFile) && !currentShard.isEmpty()) {
         // For simplicity just start a new shard to fit the given file.
         // Don't bother with waiting for a later file that might fit the old shard as in the extreme
         // we'd have to wait until the end to write all shards.
         rotateDexFile();
-        trackFieldsAndMethods(dexFile);
+        tracker.track(dexFile);
       }
     }
     currentShard.add(dexFile);
     return this;
   }
 
-  private void trackFieldsAndMethods(Dex dexFile) {
-    int fieldCount = dexFile.fieldIds().size();
-    for (int fieldIndex = 0; fieldIndex < fieldCount; ++fieldIndex) {
-      fieldsInCurrentShard.add(FieldDescriptor.fromDex(dexFile, fieldIndex));
-    }
-    int methodCount = dexFile.methodIds().size();
-    for (int methodIndex = 0; methodIndex < methodCount; ++methodIndex) {
-      methodsInCurrentShard.add(MethodDescriptor.fromDex(dexFile, methodIndex));
-    }
-  }
-
   @Override
   public void close() throws IOException {
     try {
@@ -151,8 +125,7 @@ class DexFileAggregator implements Closeable {
   private void rotateDexFile() {
     writeMergedFile(currentShard.toArray(/* apparently faster than pre-sized array */ new Dex[0]));
     currentShard.clear();
-    fieldsInCurrentShard.clear();
-    methodsInCurrentShard.clear();
+    tracker.clear();
   }
 
   private void writeMergedFile(Dex... dexes) {
@@ -211,47 +184,6 @@ class DexFileAggregator implements Closeable {
     return dexPrefix + (i == 0 ? "" : i + 1) + DEX_EXTENSION;
   }
 
-  private static String typeName(Dex dex, int typeIndex) {
-    return dex.typeNames().get(typeIndex);
-  }
-
-  @AutoValue
-  abstract static class FieldDescriptor {
-    static FieldDescriptor fromDex(Dex dex, int fieldIndex) {
-      FieldId field = dex.fieldIds().get(fieldIndex);
-      String name = dex.strings().get(field.getNameIndex());
-      String declaringClass = typeName(dex, field.getDeclaringClassIndex());
-      String type = typeName(dex, field.getTypeIndex());
-      return new AutoValue_DexFileAggregator_FieldDescriptor(declaringClass, name, type);
-    }
-
-    abstract String declaringClass();
-    abstract String fieldName();
-    abstract String fieldType();
-  }
-
-  @AutoValue
-  abstract static class MethodDescriptor {
-    static MethodDescriptor fromDex(Dex dex, int methodIndex) {
-      MethodId method = dex.methodIds().get(methodIndex);
-      ProtoId proto = dex.protoIds().get(method.getProtoIndex());
-      String name = dex.strings().get(method.getNameIndex());
-      String declaringClass = typeName(dex, method.getDeclaringClassIndex());
-      String returnType = typeName(dex, proto.getReturnTypeIndex());
-      TypeList parameterTypeIndices = dex.readTypeList(proto.getParametersOffset());
-      ImmutableList.Builder<String> parameterTypes = ImmutableList.builder();
-      for (short parameterTypeIndex : parameterTypeIndices.getTypes()) {
-        parameterTypes.add(typeName(dex, parameterTypeIndex & 0xFFFF));
-      }
-      return new AutoValue_DexFileAggregator_MethodDescriptor(
-          declaringClass, name, parameterTypes.build(), returnType);
-    }
-
-    abstract String declaringClass();
-    abstract String methodName();
-    abstract ImmutableList<String> parameterTypes();
-    abstract String returnType();
-  }
 
   private class RunDexMerger implements Callable<Dex> {
 
@@ -279,7 +211,7 @@ class DexFileAggregator implements Closeable {
 
     private final ListenableFuture<Dex> dex;
     private final String filename;
-    private final DexFileArchive dest;
+    @SuppressWarnings ("hiding") private final DexFileArchive dest;
 
     public WriteFile(String filename, ListenableFuture<Dex> dex, DexFileArchive dest) {
       this.filename = filename;
diff --git a/src/tools/android/java/com/google/devtools/build/android/dexer/DexFileMerger.java b/src/tools/android/java/com/google/devtools/build/android/dexer/DexFileMerger.java
index 658f95f46f..e892f7a94a 100644
--- a/src/tools/android/java/com/google/devtools/build/android/dexer/DexFileMerger.java
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/DexFileMerger.java
@@ -47,7 +47,6 @@ import java.nio.file.Files;
 import java.nio.file.Path;
 import java.util.ArrayList;
 import java.util.Collections;
-import java.util.Comparator;
 import java.util.concurrent.Executors;
 import java.util.zip.ZipEntry;
 import java.util.zip.ZipFile;
@@ -153,7 +152,7 @@ class DexFileMerger {
     // Undocumented dx option for testing multidex logic
     @Option(
       name = "set-max-idx-number",
-      defaultValue = "" + (DexFormat.MAX_MEMBER_IDX + 1),
+      defaultValue = "" + DexFormat.MAX_MEMBER_IDX,
       documentationCategory = OptionDocumentationCategory.UNDOCUMENTED,
       effectTags = {OptionEffectTag.UNKNOWN},
       help = "Limit on fields and methods in a single dex file."
@@ -302,48 +301,6 @@ class DexFileMerger {
     return MoreExecutors.listeningDecorator(Executors.newCachedThreadPool());
   }
 
-  /**
-   * Sorts java class names such that outer classes preceed their inner
-   * classes and "package-info" preceeds all other classes in its package.
-   *
-   * @param a {@code non-null;} first class name
-   * @param b {@code non-null;} second class name
-   * @return {@code compareTo()}-style result
-   */
-  // Copied from com.android.dx.cf.direct.ClassPathOpener
-  @VisibleForTesting
-  static int compareClassNames(String a, String b) {
-    // Ensure inner classes sort second
-    a = a.replace('$', '0');
-    b = b.replace('$', '0');
-
-    /*
-     * Assuming "package-info" only occurs at the end, ensures package-info
-     * sorts first.
-     */
-    a = a.replace("package-info", "");
-    b = b.replace("package-info", "");
-
-    return a.compareTo(b);
-  }
-
-  /**
-   * Comparator that orders {@link ZipEntry ZipEntries} {@link #LIKE_DX like Android's dx tool}.
-   */
-  private static enum ZipEntryComparator implements Comparator<ZipEntry> {
-    /**
-     * Comparator to order more or less order alphabetically by file name.  See
-     * {@link DexFileMerger#compareClassNames} for the exact name comparison.
-     */
-    LIKE_DX;
-
-    @Override
-    // Copied from com.android.dx.cf.direct.ClassPathOpener
-    public int compare(ZipEntry a, ZipEntry b) {
-      return compareClassNames(a.getName(), b.getName());
-    }
-  }
-
   private DexFileMerger() {
   }
 }
diff --git a/src/tools/android/java/com/google/devtools/build/android/dexer/DexFileSplitter.java b/src/tools/android/java/com/google/devtools/build/android/dexer/DexFileSplitter.java
new file mode 100644
index 0000000000..a7eb651b6b
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/DexFileSplitter.java
@@ -0,0 +1,266 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.android.dexer;
+
+import static com.google.common.base.Preconditions.checkArgument;
+import static com.google.common.base.Preconditions.checkState;
+import static java.nio.charset.StandardCharsets.UTF_8;
+
+import com.android.dex.Dex;
+import com.android.dex.DexFormat;
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Predicate;
+import com.google.common.base.Predicates;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.io.ByteStreams;
+import com.google.common.io.Closer;
+import com.google.devtools.build.android.Converters.ExistingPathConverter;
+import com.google.devtools.build.android.Converters.PathConverter;
+import com.google.devtools.common.options.Option;
+import com.google.devtools.common.options.OptionDocumentationCategory;
+import com.google.devtools.common.options.OptionEffectTag;
+import com.google.devtools.common.options.OptionsBase;
+import com.google.devtools.common.options.OptionsParser;
+import java.io.BufferedOutputStream;
+import java.io.Closeable;
+import java.io.IOException;
+import java.io.InputStream;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.nio.file.StandardOpenOption;
+import java.util.Comparator;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.zip.ZipEntry;
+import java.util.zip.ZipFile;
+import java.util.zip.ZipOutputStream;
+
+/**
+ * Shuffles .class.dex files from input archives into 1 or more archives each to be merged into a
+ * single final .dex file by {@link DexFileMerger}, respecting main dex list and other constraints
+ * similar to how dx would process these files if they were in a single input archive.
+ */
+class DexFileSplitter implements Closeable {
+
+  /**
+   * Commandline options.
+   */
+  public static class Options extends OptionsBase {
+    @Option(
+      name = "input",
+      allowMultiple = true,
+      defaultValue = "",
+      category = "input",
+      documentationCategory = OptionDocumentationCategory.UNCATEGORIZED,
+      effectTags = {OptionEffectTag.UNKNOWN},
+      converter = ExistingPathConverter.class,
+      abbrev = 'i',
+      help = "Input dex archive."
+    )
+    public List<Path> inputArchives;
+
+    @Option(
+      name = "output",
+      defaultValue = ".",
+      category = "output",
+      documentationCategory = OptionDocumentationCategory.UNCATEGORIZED,
+      effectTags = {OptionEffectTag.UNKNOWN},
+      converter = PathConverter.class,
+      abbrev = 'o',
+      help = "Directory to write dex archives to merge."
+    )
+    public Path outputDirectory;
+
+    @Option(
+      name = "main-dex-list",
+      defaultValue = "null",
+      category = "multidex",
+      documentationCategory = OptionDocumentationCategory.UNCATEGORIZED,
+      effectTags = {OptionEffectTag.UNKNOWN},
+      converter = ExistingPathConverter.class,
+      help = "List of classes to be placed into \"main\" classes.dex file."
+    )
+    public Path mainDexListFile;
+
+    @Option(
+      name = "minimal-main-dex",
+      defaultValue = "false",
+      category = "multidex",
+      documentationCategory = OptionDocumentationCategory.UNCATEGORIZED,
+      effectTags = {OptionEffectTag.UNKNOWN},
+      help =
+          "If true, *only* classes listed in --main_dex_list file are placed into \"main\" "
+              + "classes.dex file."
+    )
+    public boolean minimalMainDex;
+
+    // Undocumented dx option for testing multidex logic
+    @Option(
+      name = "set-max-idx-number",
+      defaultValue = "" + DexFormat.MAX_MEMBER_IDX,
+      documentationCategory = OptionDocumentationCategory.UNDOCUMENTED,
+      effectTags = {OptionEffectTag.UNKNOWN},
+      help = "Limit on fields and methods in a single dex file."
+    )
+    public int maxNumberOfIdxPerDex;
+  }
+
+  public static void main(String[] args) throws Exception {
+    OptionsParser optionsParser =
+        OptionsParser.newOptionsParser(Options.class);
+    optionsParser.setAllowResidue(false);
+    optionsParser.parseAndExitUponError(args);
+
+    splitIntoShards(optionsParser.getOptions(Options.class));
+  }
+
+  @VisibleForTesting
+  static void splitIntoShards(Options options) throws IOException {
+    checkArgument(
+        !options.minimalMainDex || options.mainDexListFile != null,
+        "--minimal-main-dex not allowed without --main-dex-list");
+
+    if (!Files.exists(options.outputDirectory)) {
+      Files.createDirectories(options.outputDirectory);
+    }
+
+    ImmutableSet<String> classesInMainDex = options.mainDexListFile != null
+        ? ImmutableSet.copyOf(Files.readAllLines(options.mainDexListFile, UTF_8))
+        : null;
+    try (Closer closer = Closer.create();
+        DexFileSplitter out =
+            new DexFileSplitter(options.outputDirectory, options.maxNumberOfIdxPerDex)) {
+      // 1. Scan inputs in order and keep first occurrence of each class, keeping all zips open.
+      // We don't process anything yet so we can shard in sorted order, which is what dx would do
+      // if presented with a single jar containing all the given inputs.
+      // TODO(kmb): Abandon alphabetic sorting to process each input fully before moving on (still
+      // requires scanning inputs twice for main dex list).
+      LinkedHashMap<String, ZipFile> deduped = new LinkedHashMap<>();
+      for (Path inputArchive : options.inputArchives) {
+        ZipFile zip = closer.register(new ZipFile(inputArchive.toFile()));
+        zip.stream()
+            .filter(ZipEntryPredicates.suffixes(".dex", ".class"))
+            .forEach(e -> deduped.putIfAbsent(e.getName(), zip));
+      }
+      ImmutableList<Map.Entry<String, ZipFile>> files =
+          deduped
+              .entrySet()
+              .stream()
+              .sorted(Comparator.comparing(e -> e.getKey(), ZipEntryComparator::compareClassNames))
+              .collect(ImmutableList.toImmutableList());
+
+      // 2. Process each class in desired order, rolling from shard to shard as needed.
+      if (classesInMainDex == null || classesInMainDex.isEmpty()) {
+        out.processDexFiles(files, Predicates.alwaysTrue());
+      } else {
+        // To honor --main_dex_list make two passes:
+        // 1. process only the classes listed in the given file
+        // 2. process the remaining files
+        Predicate<String> mainDexFilter = ZipEntryPredicates.classFileNameFilter(classesInMainDex);
+        out.processDexFiles(files, mainDexFilter);
+        // Fail if main_dex_list is too big, following dx's example
+        checkState(out.shardsWritten() == 0, "Too many classes listed in main dex list file "
+            + "%s, main dex capacity exceeded", options.mainDexListFile);
+        if (options.minimalMainDex) {
+          out.nextShard(); // Start new .dex file if requested
+        }
+        out.processDexFiles(files, Predicates.not(mainDexFilter));
+      }
+    }
+  }
+
+  private final int maxNumberOfIdxPerDex;
+  private final Path outputDirectory;
+
+  private int curShard = 0;
+  private ZipOutputStream out;
+  private DexLimitTracker tracker;
+
+  private DexFileSplitter(Path outputDirectory, int maxNumberOfIdxPerDex) throws IOException {
+    checkArgument(!Files.isRegularFile(outputDirectory), "Must be a directory: ", outputDirectory);
+    this.maxNumberOfIdxPerDex = maxNumberOfIdxPerDex;
+    this.outputDirectory = outputDirectory;
+    startShard();
+  }
+
+  private void nextShard() throws IOException {
+    out.close();  // will NPE if called after close()
+    ++curShard;
+    startShard();
+  }
+
+  private void startShard() throws IOException {
+    tracker = new DexLimitTracker(maxNumberOfIdxPerDex);
+    out =
+        new ZipOutputStream(
+            new BufferedOutputStream(
+                Files.newOutputStream(
+                    outputDirectory.resolve((curShard + 1) + ".shard.zip"),
+                    StandardOpenOption.CREATE_NEW,
+                    StandardOpenOption.WRITE)));
+  }
+
+  private int shardsWritten() {
+    return curShard;
+  }
+
+  @Override
+  public void close() throws IOException {
+    if (out != null) {
+      out.close();
+      out = null;
+      ++curShard;
+    }
+  }
+
+  private void processDexFiles(
+      ImmutableList<Map.Entry<String, ZipFile>> filesToProcess, Predicate<String> filter)
+      throws IOException {
+    for (Map.Entry<String, ZipFile> entry : filesToProcess) {
+      String filename = entry.getKey();
+      if (filter.apply(filename)) {
+        ZipFile zipFile = entry.getValue();
+        processDexEntry(zipFile, zipFile.getEntry(filename));
+      }
+    }
+  }
+
+  private void processDexEntry(ZipFile zip, ZipEntry entry) throws IOException {
+    String filename = entry.getName();
+    checkState(filename.endsWith(".class.dex"),
+        "%s isn't a dex archive: %s", zip.getName(), filename);
+    checkState(entry.getMethod() == ZipEntry.STORED, "Expect to process STORED: %s", filename);
+    try (InputStream entryStream = zip.getInputStream(entry)) {
+      // We don't want to use the Dex(InputStream) constructor because it closes the stream,
+      // which will break the for loop, and it has its own bespoke way of reading the file into
+      // a byte buffer before effectively calling Dex(byte[]) anyway.
+      // TODO(kmb) since entry is stored, mmap content and give to Dex(ByteBuffer) and output zip
+      byte[] content = new byte[(int) entry.getSize()];
+      ByteStreams.readFully(entryStream, content); // throws if file is smaller than expected
+      checkState(entryStream.read() == -1,
+          "Too many bytes in jar entry %s, expected %s", entry, entry.getSize());
+
+      Dex dexFile = new Dex(content);
+      if (tracker.track(dexFile)) {
+        nextShard();
+        tracker.track(dexFile);
+      }
+      out.putNextEntry(entry);
+      out.write(content);
+      out.closeEntry();
+    }
+  }
+}
diff --git a/src/tools/android/java/com/google/devtools/build/android/dexer/DexLimitTracker.java b/src/tools/android/java/com/google/devtools/build/android/dexer/DexLimitTracker.java
new file mode 100644
index 0000000000..5c7631eaf0
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/DexLimitTracker.java
@@ -0,0 +1,118 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.android.dexer;
+
+import com.android.dex.Dex;
+import com.android.dex.FieldId;
+import com.android.dex.MethodId;
+import com.android.dex.ProtoId;
+import com.android.dex.TypeList;
+import com.google.auto.value.AutoValue;
+import com.google.auto.value.extension.memoized.Memoized;
+import com.google.common.collect.ImmutableList;
+import java.util.HashSet;
+
+/**
+ * Helper to track how many unique field and method references we've seen in a given set of .dex
+ * files.
+ */
+class DexLimitTracker {
+
+  private final HashSet<FieldDescriptor> fieldsSeen = new HashSet<>();
+  private final HashSet<MethodDescriptor> methodsSeen = new HashSet<>();
+  private final int maxNumberOfIdxPerDex;
+
+  public DexLimitTracker(int maxNumberOfIdxPerDex) {
+    this.maxNumberOfIdxPerDex = maxNumberOfIdxPerDex;
+  }
+
+  /**
+   * Tracks the field and method references in the given file and returns whether we're within
+   * limits.
+   *
+   * @return {@code true} if method or field references are outside limits, {@code false} both
+   *     are within limits.
+   */
+  public boolean track(Dex dexFile) {
+    trackFieldsAndMethods(dexFile);
+    return fieldsSeen.size() > maxNumberOfIdxPerDex
+        || methodsSeen.size() > maxNumberOfIdxPerDex;
+  }
+
+  public void clear() {
+    fieldsSeen.clear();
+    methodsSeen.clear();
+  }
+
+  private void trackFieldsAndMethods(Dex dexFile) {
+    int fieldCount = dexFile.fieldIds().size();
+    for (int fieldIndex = 0; fieldIndex < fieldCount; ++fieldIndex) {
+      fieldsSeen.add(FieldDescriptor.fromDex(dexFile, fieldIndex));
+    }
+    int methodCount = dexFile.methodIds().size();
+    for (int methodIndex = 0; methodIndex < methodCount; ++methodIndex) {
+      methodsSeen.add(MethodDescriptor.fromDex(dexFile, methodIndex));
+    }
+  }
+
+  private static String typeName(Dex dex, int typeIndex) {
+    return dex.typeNames().get(typeIndex);
+  }
+
+  @AutoValue
+  abstract static class FieldDescriptor {
+    static FieldDescriptor fromDex(Dex dex, int fieldIndex) {
+      FieldId field = dex.fieldIds().get(fieldIndex);
+      String name = dex.strings().get(field.getNameIndex());
+      String declaringClass = typeName(dex, field.getDeclaringClassIndex());
+      String type = typeName(dex, field.getTypeIndex());
+      return new AutoValue_DexLimitTracker_FieldDescriptor(declaringClass, name, type);
+    }
+
+    abstract String declaringClass();
+    abstract String fieldName();
+    abstract String fieldType();
+
+    @Override
+    @Memoized
+    public abstract int hashCode();
+  }
+
+  @AutoValue
+  abstract static class MethodDescriptor {
+    static MethodDescriptor fromDex(Dex dex, int methodIndex) {
+      MethodId method = dex.methodIds().get(methodIndex);
+      ProtoId proto = dex.protoIds().get(method.getProtoIndex());
+      String name = dex.strings().get(method.getNameIndex());
+      String declaringClass = typeName(dex, method.getDeclaringClassIndex());
+      String returnType = typeName(dex, proto.getReturnTypeIndex());
+      TypeList parameterTypeIndices = dex.readTypeList(proto.getParametersOffset());
+      ImmutableList.Builder<String> parameterTypes = ImmutableList.builder();
+      for (short parameterTypeIndex : parameterTypeIndices.getTypes()) {
+        parameterTypes.add(typeName(dex, parameterTypeIndex & 0xFFFF));
+      }
+      return new AutoValue_DexLimitTracker_MethodDescriptor(
+          declaringClass, name, parameterTypes.build(), returnType);
+    }
+
+    abstract String declaringClass();
+    abstract String methodName();
+    abstract ImmutableList<String> parameterTypes();
+    abstract String returnType();
+
+    @Override
+    @Memoized
+    public abstract int hashCode();
+  }
+}
diff --git a/src/tools/android/java/com/google/devtools/build/android/dexer/ZipEntryComparator.java b/src/tools/android/java/com/google/devtools/build/android/dexer/ZipEntryComparator.java
new file mode 100644
index 0000000000..1cd9b84321
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/ZipEntryComparator.java
@@ -0,0 +1,60 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.android.dexer;
+
+import com.google.common.annotations.VisibleForTesting;
+import java.util.Comparator;
+import java.util.zip.ZipEntry;
+
+/**
+ * Comparator that orders {@link ZipEntry ZipEntries} {@link #LIKE_DX like Android's dx tool}.
+ */
+enum ZipEntryComparator implements Comparator<ZipEntry> {
+  /**
+   * Comparator to order more or less order alphabetically by file name.  See
+   * {@link #compareClassNames} for the exact name comparison.
+   */
+  LIKE_DX;
+
+  @Override
+  // Copied from com.android.dx.cf.direct.ClassPathOpener
+  public int compare(ZipEntry a, ZipEntry b) {
+    return compareClassNames(a.getName(), b.getName());
+  }
+
+  /**
+   * Sorts java class names such that outer classes preceed their inner
+   * classes and "package-info" preceeds all other classes in its package.
+   *
+   * @param a {@code non-null;} first class name
+   * @param b {@code non-null;} second class name
+   * @return {@code compareTo()}-style result
+   */
+  // Copied from com.android.dx.cf.direct.ClassPathOpener
+  @VisibleForTesting
+  static int compareClassNames(String a, String b) {
+    // Ensure inner classes sort second
+    a = a.replace('$', '0');
+    b = b.replace('$', '0');
+
+    /*
+     * Assuming "package-info" only occurs at the end, ensures package-info
+     * sorts first.
+     */
+    a = a.replace("package-info", "");
+    b = b.replace("package-info", "");
+
+    return a.compareTo(b);
+  }
+}
diff --git a/src/tools/android/java/com/google/devtools/build/android/dexer/ZipEntryPredicates.java b/src/tools/android/java/com/google/devtools/build/android/dexer/ZipEntryPredicates.java
index 08e77bf4f2..5dd51d4edf 100644
--- a/src/tools/android/java/com/google/devtools/build/android/dexer/ZipEntryPredicates.java
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/ZipEntryPredicates.java
@@ -14,6 +14,7 @@
 package com.google.devtools.build.android.dexer;
 
 import com.google.common.base.Predicate;
+import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableSet;
 import java.util.zip.ZipEntry;
 
@@ -44,10 +45,13 @@ class ZipEntryPredicates {
   }
 
   public static Predicate<ZipEntry> classFileFilter(final ImmutableSet<String> classFileNames) {
-    return new Predicate<ZipEntry>() {
+    return Predicates.compose(classFileNameFilter(classFileNames), zipEntry -> zipEntry.getName());
+  }
+
+  public static Predicate<String> classFileNameFilter(final ImmutableSet<String> classFileNames) {
+    return new Predicate<String>() {
       @Override
-      public boolean apply(ZipEntry input) {
-        String filename = input.getName();
+      public boolean apply(String filename) {
         if (filename.endsWith(".class.dex")) {
           // Chop off file suffix generated by DexBuilder
           filename = filename.substring(0, filename.length() - ".dex".length());