Open source dex merging tools for incremental dexing.

Tested with
bazel build --incremental_dexing_binary_types=monodex,multidex_unsharded,multidex_sharded -- //examples/android/java/bazel:hello_world

--
MOS_MIGRATED_REVID=134690103

15 files changed, 1583 insertions, 0 deletions

diff --git a/src/tools/android/java/com/google/devtools/build/android/BUILD b/src/tools/android/java/com/google/devtools/build/android/BUILD
index d8df5b4103..07db559fcf 100644
--- a/src/tools/android/java/com/google/devtools/build/android/BUILD
+++ b/src/tools/android/java/com/google/devtools/build/android/BUILD
@@ -104,6 +104,7 @@ java_library(
 filegroup(
     name = "srcs",
     srcs = glob(["**"]) + [
+        "//src/tools/android/java/com/google/devtools/build/android/dexer:srcs",
         "//src/tools/android/java/com/google/devtools/build/android/ideinfo:srcs",
         "//src/tools/android/java/com/google/devtools/build/android/idlclass:srcs",
         "//src/tools/android/java/com/google/devtools/build/android/incrementaldeployment:srcs",
diff --git a/src/tools/android/java/com/google/devtools/build/android/dexer/BUILD b/src/tools/android/java/com/google/devtools/build/android/dexer/BUILD
new file mode 100644
index 0000000000..f56dcd490a
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/BUILD
@@ -0,0 +1,33 @@
+# Description:
+#   Collection of dex utilities used in the bazel android actions.
+
+filegroup(
+    name = "srcs",
+    srcs = glob(["**"]),
+)
+
+filegroup(
+    name = "embedded_tools",
+    srcs = glob(["*.java"]) + [
+        "BUILD.tools",
+        ":dexerdeps_deploy.jar",
+    ],
+    visibility = ["//visibility:public"],
+)
+
+# The DexFileMerger and DexBuilder are built in BUILD.tools which is built in
+# a developers workspace, not the Bazel workspace. So we must bundle the
+# dependencies of those binaries into the embedded tools. We use a java_binary
+# instead of a java_library so that we can build a deploy jar which contains the
+# transitive closure of the dependencies.
+java_binary(
+    name = "dexerdeps",
+    runtime_deps = [
+        "//src/main/java/com/google/devtools/common/options",
+        "//src/main/protobuf:worker_protocol_java_proto",
+        "//src/tools/android/java/com/google/devtools/build/android:android_builder_lib",
+        "//third_party:auto_value",
+        "//third_party:guava",
+        "//third_party:jsr305",
+    ],
+)
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
new file mode 100644
index 0000000000..da14efacd7
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/BUILD.tools
@@ -0,0 +1,31 @@
+package(default_visibility = ["//visibility:public"])
+
+java_library(
+    name = "dexer",
+    srcs = glob(["*.java"]),
+    deps = [
+        "//external:android/dx_jar_import",
+        ":dexerdeps_deploy.jar",
+    ],
+    plugins = ["auto_value_plugin"],
+)
+
+java_plugin(
+    name = "auto_value_plugin",
+    processor_class = "com.google.auto.value.processor.AutoValueProcessor",
+    deps = [":dexerdeps_deploy.jar"],
+)
+
+java_binary(
+    name = "DexBuilder",
+    main_class = "com.google.devtools.build.android.dexer.DexBuilder",
+    visibility = ["//tools/android:__subpackages__"],
+    runtime_deps = [":dexer"],
+)
+
+java_binary(
+    name = "DexFileMerger",
+    main_class = "com.google.devtools.build.android.dexer.DexFileMerger",
+    visibility = ["//tools/android:__subpackages__"],
+    runtime_deps = [":dexer"],
+)
diff --git a/src/tools/android/java/com/google/devtools/build/android/dexer/DexBuilder.java b/src/tools/android/java/com/google/devtools/build/android/dexer/DexBuilder.java
new file mode 100644
index 0000000000..20ef957009
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/DexBuilder.java
@@ -0,0 +1,255 @@
+// Copyright 2016 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 java.nio.charset.StandardCharsets.ISO_8859_1;
+import static java.util.concurrent.Executors.newFixedThreadPool;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.cache.Cache;
+import com.google.common.cache.CacheBuilder;
+import com.google.common.cache.Weigher;
+import com.google.common.util.concurrent.MoreExecutors;
+import com.google.devtools.build.android.Converters.ExistingPathConverter;
+import com.google.devtools.build.android.Converters.PathConverter;
+import com.google.devtools.build.android.dexer.Dexing.DexingKey;
+import com.google.devtools.build.android.dexer.Dexing.DexingOptions;
+import com.google.devtools.build.lib.worker.WorkerProtocol.WorkRequest;
+import com.google.devtools.build.lib.worker.WorkerProtocol.WorkResponse;
+import com.google.devtools.common.options.Option;
+import com.google.devtools.common.options.OptionsBase;
+import com.google.devtools.common.options.OptionsParser;
+import com.google.devtools.common.options.OptionsParsingException;
+
+import com.android.dx.command.DxConsole;
+
+import java.io.BufferedOutputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+import java.io.PrintStream;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.nio.file.Paths;
+import java.util.List;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Future;
+import java.util.zip.ZipFile;
+import java.util.zip.ZipOutputStream;
+
+import javax.annotation.Nullable;
+
+/**
+ * Tool used by Bazel that converts a Jar file of .class files into a .zip file of .dex files,
+ * one per .class file, which we call a <i>dex archive</i>.
+ */
+class DexBuilder {
+
+  private static final long ONE_MEG = 1_000_000L;
+
+  /**
+   * Commandline options.
+   */
+  public static class Options extends OptionsBase {
+    @Option(name = "input_jar",
+        defaultValue = "null",
+        category = "input",
+        converter = ExistingPathConverter.class,
+        abbrev = 'i',
+        help = "Input file to read classes and jars from.")
+    public Path inputJar;
+
+    @Option(name = "output_zip",
+        defaultValue = "null",
+        category = "output",
+        converter = PathConverter.class,
+        abbrev = 'o',
+        help = "Output file to write.")
+    public Path outputZip;
+
+    @Option(name = "max_threads",
+        defaultValue = "8",
+        category = "misc",
+        help = "How many threads (besides the main thread) to use at most.")
+    public int maxThreads;
+
+    @Option(name = "persistent_worker",
+        defaultValue = "false",
+        category = "hidden",
+        help = "Run as a Bazel persistent worker.")
+    public boolean persistentWorker;
+  }
+
+  public static void main(String[] args) throws Exception {
+    if (args.length == 1 && args[0].startsWith("@")) {
+      args = Files.readAllLines(Paths.get(args[0].substring(1)), ISO_8859_1).toArray(new String[0]);
+    }
+
+    OptionsParser optionsParser =
+        OptionsParser.newOptionsParser(Options.class, DexingOptions.class);
+    optionsParser.parseAndExitUponError(args);
+    Options options = optionsParser.getOptions(Options.class);
+    if (options.persistentWorker) {
+      runPersistentWorker();
+    } else {
+      buildDexArchive(options, optionsParser.getOptions(DexingOptions.class));
+    }
+  }
+
+  @VisibleForTesting
+  static void buildDexArchive(Options options, DexingOptions dexingOptions)
+      throws Exception {
+    checkArgument(options.maxThreads > 0,
+        "--max_threads must be strictly positive, was: %s", options.maxThreads);
+    try (ZipFile in = new ZipFile(options.inputJar.toFile())) {
+      // Heuristic: use at most 1 thread per 1000 files in the input Jar
+      int threads = Math.min(options.maxThreads, in.size() / 1000 + 1);
+      ExecutorService executor = newFixedThreadPool(threads);
+      try (ZipOutputStream out = createZipOutputStream(options.outputZip)) {
+        produceDexArchive(in, out, executor, threads <= 1, dexingOptions, null);
+      } finally {
+        executor.shutdown();
+      }
+    }
+    // Use input's timestamp for output file so the output file is stable.
+    Files.setLastModifiedTime(options.outputZip, Files.getLastModifiedTime(options.inputJar));
+  }
+
+  /**
+   * Implements a persistent worker process for use with Bazel (see {@code WorkerSpawnStrategy}).
+   */
+  private static void runPersistentWorker() throws IOException {
+    ExecutorService executor = newFixedThreadPool(Runtime.getRuntime().availableProcessors());
+    Cache<DexingKey, byte[]> dexCache = CacheBuilder.newBuilder()
+        // Use at most 200 MB for cache and leave at least 25 MB of heap space alone. For reference:
+        // .class & class.dex files are around 1-5 KB, so this fits ~30K-35K class-dex pairs.
+        .maximumWeight(Math.min(Runtime.getRuntime().maxMemory() - 25 * ONE_MEG, 200 * ONE_MEG))
+        .weigher(new Weigher<DexingKey, byte[]>() {
+          @Override
+          public int weigh(DexingKey key, byte[] value) {
+            return key.classfileContent().length + value.length;
+          }
+        })
+        .build();
+    try {
+      while (true) {
+        WorkRequest request = WorkRequest.parseDelimitedFrom(System.in);
+        if (request == null) {
+          return;
+        }
+
+        // Redirect dx's output so we can return it in response
+        ByteArrayOutputStream baos = new ByteArrayOutputStream();
+        PrintStream ps = new PrintStream(baos, /*autoFlush*/ true);
+        DxConsole.out = DxConsole.err = ps;
+        // Make sure that we exit nonzero in case uncaught errors occur during processRequest.
+        int exitCode = 1;
+        try {
+          processRequest(executor, dexCache, request.getArgumentsList());
+          exitCode = 0; // success!
+        } catch (Exception e) {
+          // Deliberate catch-all so we can capture a stack trace.
+          // TODO(bazel-team): Consider canceling any outstanding futures created for this request
+          e.printStackTrace(ps);
+        } catch (Error e) {
+          e.printStackTrace();
+          e.printStackTrace(ps); // try capturing the error, may fail if out of memory
+          throw e; // rethrow to kill the worker
+        } finally {
+          // Try sending a response no matter what
+          String output;
+          try {
+            output = baos.toString();
+          } catch (Throwable t) { // most likely out of memory, so log with minimal memory needs
+            t.printStackTrace();
+            output = "check worker log for exceptions";
+          }
+          WorkResponse.newBuilder()
+              .setOutput(output)
+              .setExitCode(exitCode)
+              .build()
+              .writeDelimitedTo(System.out);
+          System.out.flush();
+        }
+      }
+    } finally {
+      executor.shutdown();
+    }
+  }
+
+  private static void processRequest(
+      ExecutorService executor, Cache<DexingKey, byte[]> dexCache, List<String> args)
+      throws OptionsParsingException, IOException, InterruptedException, ExecutionException {
+    OptionsParser optionsParser =
+        OptionsParser.newOptionsParser(Options.class, DexingOptions.class);
+    optionsParser.setAllowResidue(false);
+    optionsParser.parse(args);
+    Options options = optionsParser.getOptions(Options.class);
+    try (ZipFile in = new ZipFile(options.inputJar.toFile());
+        ZipOutputStream out = createZipOutputStream(options.outputZip)) {
+      produceDexArchive(
+          in,
+          out,
+          executor,
+          /*convertOnReaderThread*/ false,
+          optionsParser.getOptions(DexingOptions.class),
+          dexCache);
+    }
+    // Use input's timestamp for output file so the output file is stable.
+    Files.setLastModifiedTime(options.outputZip, Files.getLastModifiedTime(options.inputJar));
+  }
+
+  private static ZipOutputStream createZipOutputStream(Path path) throws IOException {
+    return new ZipOutputStream(new BufferedOutputStream(Files.newOutputStream(path)));
+  }
+
+  private static void produceDexArchive(
+      ZipFile in,
+      ZipOutputStream out,
+      ExecutorService executor,
+      boolean convertOnReaderThread,
+      DexingOptions dexingOptions,
+      @Nullable Cache<DexingKey, byte[]> dexCache)
+      throws InterruptedException, ExecutionException, IOException {
+    // If we only have one thread in executor, we give a "direct" executor to the stuffer, which
+    // will convert .class files to .dex inline on the same thread that reads the input jar.
+    // This is an optimization that makes sure we can start writing the output file below while
+    // the stuffer is still working its way through the input.
+    DexConversionEnqueuer enqueuer = new DexConversionEnqueuer(in,
+        convertOnReaderThread ? MoreExecutors.newDirectExecutorService() : executor,
+        new DexConverter(new Dexing(dexingOptions)),
+        dexCache);
+    Future<?> enqueuerTask = executor.submit(enqueuer);
+    while (true) {
+      // Wait for next future in the queue *and* for that future to finish.  To guarantee
+      // deterministic output we just write out the files in the order they appear, which is
+      // the same order as in the input zip.
+      ZipEntryContent file = enqueuer.getFiles().take().get();
+      if (file == null) {
+        // "done" marker indicating no more files coming.
+        // Make sure enqueuer terminates normally (any wait should be minimal).  This in
+        // particular surfaces any exceptions thrown in the enqueuer.
+        enqueuerTask.get();
+        break;
+      }
+      out.putNextEntry(file.getEntry());
+      out.write(file.getContent());
+      out.closeEntry();
+    }
+  }
+
+  private DexBuilder() {
+  }
+}
diff --git a/src/tools/android/java/com/google/devtools/build/android/dexer/DexConversionEnqueuer.java b/src/tools/android/java/com/google/devtools/build/android/dexer/DexConversionEnqueuer.java
new file mode 100644
index 0000000000..2c84af3683
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/DexConversionEnqueuer.java
@@ -0,0 +1,170 @@
+// Copyright 2016 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 com.google.common.util.concurrent.Futures.immediateFuture;
+
+import com.google.common.cache.Cache;
+import com.google.common.io.ByteStreams;
+import com.google.devtools.build.android.dexer.Dexing.DexingKey;
+
+import java.io.IOException;
+import java.io.InputStream;
+import java.util.Enumeration;
+import java.util.concurrent.ArrayBlockingQueue;
+import java.util.concurrent.BlockingQueue;
+import java.util.concurrent.Callable;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Future;
+import java.util.zip.ZipEntry;
+import java.util.zip.ZipFile;
+
+import javax.annotation.Nullable;
+
+/**
+ * Worker that reads an input Jar file and creates futures to convert .class to .dex files while
+ * leaving other files in the Jar unchanged.  Converted files appear in {@link #getFiles()}.
+ * Because the queue of files is size-limited, this {@link Callable} must not be invoked on the
+ * main thread to avoid deadlocking.
+ *
+ * <p>Note on the name: this callable enqueues futures to convert .class files into a thread pool;
+ * it doesn't return a value itself other than successful termination or an exception during input
+ * file reading.
+ */
+class DexConversionEnqueuer implements Callable<Void> {
+
+  private static final byte[] EMPTY = new byte[0];
+
+  private final ZipFile in;
+  private final DexConverter dexer;
+  private final ExecutorService executor;
+  @Nullable private final Cache<DexingKey, byte[]> dexCache;
+
+  /** Converted content of the input file.  See {@link #getFiles()} for more details. */
+  // Rate-limit to 30000 files in flight at once, which is about what we've tested.  Theoretically,
+  // an unbounded queue can lead to OutOfMemoryErrors, and any limit is helpful so that one can
+  // set -Xmx to handle even large files.  The "downside" is that this callable can theoretically
+  // block trying to add more elements to the queue, wasting the thread during that time.
+  private final BlockingQueue<Future<ZipEntryContent>> files = new ArrayBlockingQueue<>(30000);
+
+  public DexConversionEnqueuer(ZipFile in, ExecutorService executor, DexConverter dexer,
+      @Nullable Cache<DexingKey, byte[]> dexCache) {
+    this.in = in;
+    this.executor = executor;
+    this.dexer = dexer;
+    this.dexCache = dexCache;
+  }
+
+  @Override
+  public Void call() throws InterruptedException, IOException {
+    try {
+      Enumeration<? extends ZipEntry> entries = in.entries();
+      while (entries.hasMoreElements()) {
+        ZipEntry entry = entries.nextElement();
+        // Since these entries come from an existing zip file, they should always know their size
+        // (meaning, never return -1). We also can't handle files that don't fit into a byte array.
+        checkArgument(entry.getSize() >= 0, "Cannot process entry with unknown size: %s", entry);
+        checkArgument(entry.getSize() <= Integer.MAX_VALUE, "Entry too large: %s", entry);
+        byte[] content;
+        if (entry.getSize() == 0L) {
+          content = EMPTY; // this in particular covers directory entries
+        } else {
+          try (InputStream entryStream = in.getInputStream(entry)) {
+            // Read all the content at once, which avoids temporary arrays and extra array copies
+            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());
+          }
+        }
+        if (!entry.isDirectory() && entry.getName().endsWith(".class")) {
+          files.put(toDex(entry, content));
+        } else {
+          // Copy other files and directory entries
+          if (entry.getCompressedSize() != 0) {
+            entry.setCompressedSize(-1L); // We may compress differently from source Zip
+          }
+          files.put(immediateFuture(new ZipEntryContent(entry, content)));
+        }
+      }
+    } finally {
+      // Use try-finally to make absolutely sure we do this, otherwise the reader might deadlock
+      files.put(immediateFuture((ZipEntryContent) null)); // "end of stream" marker
+    }
+    return null;
+  }
+
+  private Future<ZipEntryContent> toDex(ZipEntry entry, byte[] content) {
+    byte[] cached = dexCache != null ? dexCache.getIfPresent(dexer.getDexingKey(content)) : null;
+    return cached != null
+        ? immediateFuture(newDexEntry(entry, cached))
+        : executor.submit(new ClassToDex(entry, content, dexer, dexCache));
+  }
+
+  /**
+   * Converted .dex files as well as (unchanged) resources in the order they appear in {@link #in
+   * the input zip file}.  For simplicity we use a separate future for each file, followed by a
+   * future returning {@code null} to indicate that the input zip file is exhausted.  To achieve
+   * determinism, the consumer of this queue should write the content of each file in the order
+   * they appear in this queue.  Note that no files will appear in this queue until this callable is
+   * {@link #call invoked}, typically by submitting it to an {@link ExecutorService}.  Once a
+   * future returning {@code null} appears in the queue, no more elements will follow, so the
+   * consumer should be a single-threaded loop that terminates on this {@code null} sentinel.
+   */
+  public BlockingQueue<Future<ZipEntryContent>> getFiles() {
+    return files;
+  }
+
+  private static ZipEntryContent newDexEntry(ZipEntry classfile, byte[] dexed) {
+    return new ZipEntryContent(withFileName(classfile, classfile.getName() + ".dex"), dexed);
+  }
+
+  private static ZipEntry withFileName(ZipEntry orig, String filename) {
+    ZipEntry result = new ZipEntry(filename);
+    result.setTime(orig.getTime());
+    return result;
+  }
+
+  /**
+   * Worker to convert a {@code byte[]} representing a .class file into a {@code byte[]}
+   * representing a .dex file.
+   */
+  private static class ClassToDex implements Callable<ZipEntryContent> {
+
+    private final ZipEntry entry;
+    private final byte[] content;
+    private final DexConverter dexer;
+    @Nullable private final Cache<DexingKey, byte[]> dexCache;
+
+    public ClassToDex(ZipEntry entry, byte[] content, DexConverter dexer,
+        @Nullable Cache<DexingKey, byte[]> dexCache) {
+      this.entry = entry;
+      this.content = content;
+      this.dexer = dexer;
+      this.dexCache = dexCache;
+    }
+
+    @Override
+    public ZipEntryContent call() throws Exception {
+      byte[] dexed = DexFiles.encode(dexer.toDexFile(content, entry.getName()));
+      if (dexCache != null) {
+        dexCache.put(dexer.getDexingKey(content), dexed);
+      }
+      // Use .class.dex suffix expected by SplitZip
+      return newDexEntry(entry, dexed);
+    }
+  }
+}
diff --git a/src/tools/android/java/com/google/devtools/build/android/dexer/DexConverter.java b/src/tools/android/java/com/google/devtools/build/android/dexer/DexConverter.java
new file mode 100644
index 0000000000..924e636521
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/DexConverter.java
@@ -0,0 +1,38 @@
+// Copyright 2016 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.dx.dex.file.DexFile;
+
+/**
+ * Converter from Java classes to corresponding standalone .dex files.
+ */
+class DexConverter {
+
+  private final Dexing dexing;
+
+  public DexConverter(Dexing dexing) {
+    this.dexing = dexing;
+  }
+
+  public DexFile toDexFile(byte[] classfile, String classfilePath) {
+    DexFile result = dexing.newDexFile();
+    dexing.addToDexFile(result, Dexing.parseClassFile(classfile, classfilePath));
+    return result;
+  }
+
+  public Dexing.DexingKey getDexingKey(byte[] classfile) {
+    return dexing.getDexingKey(classfile);
+  }
+}
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
new file mode 100644
index 0000000000..b30eb9dbe9
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/DexFileAggregator.java
@@ -0,0 +1,251 @@
+// Copyright 2016 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.checkState;
+
+import com.google.auto.value.AutoValue;
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.collect.ImmutableList;
+
+import com.android.dex.Dex;
+import com.android.dex.DexFormat;
+import com.android.dex.FieldId;
+import com.android.dex.MethodId;
+import com.android.dx.dex.file.DexFile;
+import com.android.dx.merge.CollisionPolicy;
+import com.android.dx.merge.DexMerger;
+
+import java.io.Closeable;
+import java.io.IOException;
+import java.nio.BufferOverflowException;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.zip.ZipEntry;
+
+/**
+ * Merger for {@code .dex} files into larger chunks subject to {@code .dex} file limits on methods
+ * and fields.
+ */
+class DexFileAggregator implements Closeable {
+
+  /**
+   * File extension of a {@code .dex} file.
+   */
+  private static final String DEX_EXTENSION = ".dex";
+
+  /**
+   * File name prefix of a {@code .dex} file automatically loaded in an
+   * archive.
+   */
+  private static final String DEX_PREFIX = "classes";
+
+  private final ArrayList<Dex> currentShard = new ArrayList<>();
+  private final HashSet<FieldDescriptor> fieldsInCurrentShard = new HashSet<>();
+  private final HashSet<MethodDescriptor> methodsInCurrentShard = new HashSet<>();
+  private final int maxNumberOfIdxPerDex;
+  private final int wasteThresholdPerDex;
+  private final MultidexStrategy multidex;
+  private DexFileArchive dest;
+  private int nextDexFileIndex = 0;
+
+  public DexFileAggregator(DexFileArchive dest, MultidexStrategy multidex) {
+    this(dest,
+        multidex,
+        DexFormat.MAX_MEMBER_IDX + 1,
+        1024 * 1024 /* DexMerger's default wasteThreshold */);
+  }
+
+  public DexFileAggregator(
+      DexFileArchive dest,
+      MultidexStrategy multidex,
+      int maxNumberOfIdxPerDex,
+      int wasteThresholdPerDex) {
+    this.dest = dest;
+    this.multidex = multidex;
+    this.maxNumberOfIdxPerDex = maxNumberOfIdxPerDex;
+    this.wasteThresholdPerDex = wasteThresholdPerDex;
+  }
+
+  public DexFileAggregator add(Dex dexFile) throws IOException {
+    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)) {
+        // 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);
+      }
+    }
+    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));
+    }
+  }
+
+  public DexFileAggregator add(DexFile dexFile) throws IOException {
+    if (multidex == MultidexStrategy.BEST_EFFORT) {
+      addSeparate(dexFile);
+    } else {
+      // Could be smarter here and e.g. check whether dexFile will fit into current shard first
+      // and, with a hint as to whether this is a "full" file (e.g., from rotating in MergingDexer),
+      // write the current shard and then the given file separately.  The following is slower but
+      // guarantees that in the MINIMAL case, classes are written in the order in which we saw them
+      // as best as possible.  Since practically we aim for this method to never or almost never
+      // be called it shouldn't matter much.  (This method is called when we had to convert .class
+      // files on the fly, while add(Dex) is in particular called for pre-dexed .class.dex files.)
+      add(DexFiles.toDex(dexFile));
+    }
+    return this;
+  }
+
+  private DexFileAggregator addSeparate(DexFile dexFile) throws IOException {
+    checkState(multidex.isMultidexAllowed());
+    dest.addFile(nextArchiveEntry(), dexFile);
+    return this;
+  }
+
+  @Override
+  public void close() throws IOException {
+    try {
+      if (!currentShard.isEmpty()) {
+        rotateDexFile();
+      }
+    } finally {
+      dest.close();
+      dest = null;
+    }
+  }
+
+  public void flush() throws IOException {
+    checkState(multidex.isMultidexAllowed());
+    if (!currentShard.isEmpty()) {
+      rotateDexFile();
+    }
+  }
+
+  public int getDexFilesWritten() {
+    return nextDexFileIndex;
+  }
+
+  private void rotateDexFile() throws IOException {
+    writeMergedFile(currentShard.toArray(/* apparently faster than pre-sized array */ new Dex[0]));
+    currentShard.clear();
+    fieldsInCurrentShard.clear();
+    methodsInCurrentShard.clear();
+  }
+
+  private void writeMergedFile(Dex... dexes) throws IOException {
+    Dex merged = merge(dexes);
+    dest.addFile(nextArchiveEntry(), merged);
+  }
+
+  private Dex merge(Dex... dexes) throws IOException {
+    switch (dexes.length) {
+      case 0:
+        return new Dex(0);
+      case 1:
+        return dexes[0];
+      default:
+        try {
+          DexMerger dexMerger = new DexMerger(dexes, CollisionPolicy.FAIL);
+          dexMerger.setCompactWasteThreshold(wasteThresholdPerDex);
+          return dexMerger.merge();
+        } catch (BufferOverflowException e) {
+          // Bug in dx can cause this for ~1500 or more classes
+          Dex[] left = Arrays.copyOf(dexes, dexes.length / 2);
+          Dex[] right = Arrays.copyOfRange(dexes, left.length, dexes.length);
+          System.err.printf("Couldn't merge %d classes, trying %d%n", dexes.length, left.length);
+          try {
+            return merge(merge(left), merge(right));
+          } catch (RuntimeException e2) {
+            e2.addSuppressed(e);
+            throw e2;
+          }
+        }
+    }
+  }
+
+  private ZipEntry nextArchiveEntry() {
+    checkState(multidex.isMultidexAllowed() || nextDexFileIndex == 0);
+    ZipEntry result = new ZipEntry(getDexFileName(nextDexFileIndex++));
+    result.setTime(0L); // Use simple stable timestamps for deterministic output
+    return result;
+  }
+
+  // More or less copied from from com.android.dx.command.dexer.Main
+  @VisibleForTesting
+  static String getDexFileName(int i) {
+    return i == 0 ? DexFormat.DEX_IN_JAR_NAME : DEX_PREFIX + (i + 1) + DEX_EXTENSION;
+  }
+
+  @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);
+      String name = dex.strings().get(method.getNameIndex());
+      String declaringClass = typeName(dex, method.getDeclaringClassIndex());
+      String returnType = typeName(dex, dex.returnTypeIndexFromMethodIndex(methodIndex));
+      short[] parameterTypeIndices = dex.parameterTypeIndicesFromMethodIndex(methodIndex);
+      ImmutableList.Builder<String> parameterTypes = ImmutableList.builder();
+      for (short parameterTypeIndex : parameterTypeIndices) {
+        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 static String typeName(Dex dex, int typeIndex) {
+    return dex.typeNames().get(typeIndex);
+  }
+}
\ No newline at end of file
diff --git a/src/tools/android/java/com/google/devtools/build/android/dexer/DexFileArchive.java b/src/tools/android/java/com/google/devtools/build/android/dexer/DexFileArchive.java
new file mode 100644
index 0000000000..20edd0b886
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/DexFileArchive.java
@@ -0,0 +1,79 @@
+// Copyright 2016 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.io.ByteStreams;
+
+import com.android.dex.Dex;
+import com.android.dx.dex.file.DexFile;
+
+import java.io.Closeable;
+import java.io.IOException;
+import java.io.InputStream;
+import java.util.zip.ZipEntry;
+import java.util.zip.ZipOutputStream;
+
+/**
+ * Wrapper around a {@link ZipOutputStream} to simplify writing archives with {@code .dex} files.
+ * Adding files generally requires a {@link ZipEntry} in order to control timestamps.
+ */
+class DexFileArchive implements Closeable {
+
+  private final ZipOutputStream out;
+
+  public DexFileArchive(ZipOutputStream out) {
+    this.out = out;
+  }
+
+  /**
+   * Copies the content of the given {@link InputStream} into an entry with the given details.
+   */
+  public DexFileArchive copy(ZipEntry entry, InputStream in) throws IOException {
+    out.putNextEntry(entry);
+    ByteStreams.copy(in, out);
+    out.closeEntry();
+    return this;
+  }
+
+  /**
+   * Serializes and adds a {@code .dex} file with the given details.
+   */
+  public DexFileArchive addFile(ZipEntry entry, DexFile dex) throws IOException {
+    return addFile(entry, DexFiles.encode(dex));
+  }
+
+  /**
+   * Adds a {@code .dex} file with the given details.
+   */
+  public DexFileArchive addFile(ZipEntry entry, Dex dex) throws IOException {
+    entry.setSize(dex.getLength());
+    out.putNextEntry(entry);
+    dex.writeTo(out);
+    out.closeEntry();
+    return this;
+  }
+
+  @Override
+  public void close() throws IOException {
+    out.close();
+  }
+
+  private DexFileArchive addFile(ZipEntry entry, byte[] content) throws IOException {
+    entry.setSize(content.length);
+    out.putNextEntry(entry);
+    out.write(content);
+    out.closeEntry();
+    return this;
+  }
+}
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
new file mode 100644
index 0000000000..7f6692b80d
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/DexFileMerger.java
@@ -0,0 +1,280 @@
+// Copyright 2016 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.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Predicate;
+import com.google.common.base.Predicates;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterators;
+import com.google.common.collect.Lists;
+import com.google.common.io.ByteStreams;
+import com.google.devtools.build.android.Converters.ExistingPathConverter;
+import com.google.devtools.build.android.Converters.PathConverter;
+import com.google.devtools.common.options.EnumConverter;
+import com.google.devtools.common.options.Option;
+import com.google.devtools.common.options.OptionsBase;
+import com.google.devtools.common.options.OptionsParser;
+
+import com.android.dex.Dex;
+import com.android.dex.DexFormat;
+import com.android.dx.command.DxConsole;
+
+import java.io.BufferedOutputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.PrintStream;
+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.zip.ZipEntry;
+import java.util.zip.ZipFile;
+import java.util.zip.ZipOutputStream;
+
+/**
+ * Tool used by Bazel as a replacement for Android's {@code dx} tool that assembles a single or, if
+ * allowed and necessary, multiple {@code .dex} files from a given archive of {@code .dex} and
+ * {@code .class} files.  The tool merges the {@code .dex} files it encounters into a single file
+ * and additionally encodes any {@code .class} files it encounters.  If multidex is allowed then the
+ * tool will generate multiple files subject to the {@code .dex} file format's limits on the number
+ * of methods and fields.
+ */
+class DexFileMerger {
+
+  /**
+   * Commandline options.
+   */
+  public static class Options extends OptionsBase {
+    @Option(name = "input",
+        defaultValue = "null",
+        category = "input",
+        converter = ExistingPathConverter.class,
+        abbrev = 'i',
+        help = "Input file to read to aggregate.")
+    public Path inputArchive;
+
+    @Option(name = "output",
+        defaultValue = "classes.dex.jar",
+        category = "output",
+        converter = PathConverter.class,
+        abbrev = 'o',
+        help = "Output archive to write.")
+    public Path outputArchive;
+
+    @Option(name = "multidex",
+        defaultValue = "off",
+        category = "multidex",
+        converter = MultidexStrategyConverter.class,
+        help = "Allow more than one .dex file in the output.")
+    public MultidexStrategy multidexMode;
+
+    @Option(name = "main-dex-list",
+        defaultValue = "null",
+        category = "multidex",
+        converter = ExistingPathConverter.class,
+        implicitRequirements = "--multidex=minimal",
+        help = "List of classes to be placed into \"main\" classes.dex file.")
+    public Path mainDexListFile;
+
+    @Option(name = "minimal-main-dex",
+        defaultValue = "false",
+        category = "multidex",
+        implicitRequirements = "--multidex=minimal",
+        help = "If true, *only* classes listed in --main_dex_list file are placed into \"main\" "
+            + "classes.dex file.")
+    public boolean minimalMainDex;
+
+    @Option(name = "verbose",
+        defaultValue = "false",
+        category = "misc",
+        help = "If true, print information about the merged files and resulting files to stdout.")
+    public boolean verbose;
+
+    @Option(name = "max-bytes-wasted-per-file",
+        defaultValue = "0",
+        category = "misc",
+        help = "Limit on conservatively allocated but unused bytes per dex file, which can enable "
+            + "faster merging.")
+    public int wasteThresholdPerDex;
+
+    // Undocumented dx option for testing multidex logic
+    @Option(name = "set-max-idx-number",
+        defaultValue = "" + (DexFormat.MAX_MEMBER_IDX + 1),
+        category = "undocumented",
+        help = "Limit on fields and methods in a single dex file.")
+    public int maxNumberOfIdxPerDex;
+  }
+
+  public static class MultidexStrategyConverter extends EnumConverter<MultidexStrategy> {
+    public MultidexStrategyConverter() {
+      super(MultidexStrategy.class, "multidex strategy");
+    }
+  }
+
+  public static void main(String[] args) throws Exception {
+    OptionsParser optionsParser =
+        OptionsParser.newOptionsParser(Options.class, Dexing.DexingOptions.class);
+    optionsParser.parseAndExitUponError(args);
+
+    buildMergedDexFiles(
+        optionsParser.getOptions(Options.class),
+        optionsParser.getOptions(Dexing.DexingOptions.class));
+  }
+
+  @VisibleForTesting
+  static void buildMergedDexFiles(Options options, Dexing.DexingOptions dexingOptions)
+      throws IOException {
+    ImmutableSet<String> classesInMainDex = options.mainDexListFile != null
+        ? ImmutableSet.copyOf(Files.readAllLines(options.mainDexListFile, UTF_8))
+        : null;
+    PrintStream originalStdOut = System.out;
+    try (ZipFile zip = new ZipFile(options.inputArchive.toFile());
+        DexFileAggregator out = createDexFileAggregator(options)) {
+      if (!options.verbose) {
+        // com.android.dx.merge.DexMerger prints tons of debug information to System.out that we
+        // silence here unless it was explicitly requested.
+        System.setOut(DxConsole.noop);
+      }
+
+      MergingDexer dexer =
+          new MergingDexer(
+              new Dexing(dexingOptions),
+              out,
+              options.multidexMode.isMultidexAllowed(),
+              options.maxNumberOfIdxPerDex);
+      if (classesInMainDex == null) {
+        processClassAndDexFiles(zip, out, dexer, Predicates.<ZipEntry>alwaysTrue());
+      } else {
+        // Options parser should be making sure of this but let's be extra-safe as other modes
+        // might result in classes from main dex list ending up in files other than classes.dex
+        checkArgument(options.multidexMode == MultidexStrategy.MINIMAL, "Only minimal multidex "
+            + "mode is supported with --main_dex_list, but mode is: %s", options.multidexMode);
+        // To honor --main_dex_list make two passes:
+        // 1. process only the classes listed in the given file
+        // 2. process the remaining files
+        Predicate<ZipEntry> classFileFilter = ZipEntryPredicates.classFileFilter(classesInMainDex);
+        processClassAndDexFiles(zip, out, dexer, classFileFilter);
+        dexer.flush(); // Add any main dex list classes we had to convert on-the-fly
+        // Fail if main_dex_list is too big, following dx's example
+        checkState(out.getDexFilesWritten() == 0, "Too many classes listed in main dex list file "
+            + "%s, main dex capacity exceeded", options.mainDexListFile);
+        if (options.minimalMainDex) {
+          out.flush(); // Start new .dex file if requested
+        }
+        processClassAndDexFiles(zip, out, dexer, Predicates.not(classFileFilter));
+      }
+      // Add any classes to output archive that we had to convert on-the-fly
+      dexer.finish();
+    } finally {
+      System.setOut(originalStdOut);
+    }
+    // Use input's timestamp for output file so the output file is stable.
+    Files.setLastModifiedTime(options.outputArchive,
+        Files.getLastModifiedTime(options.inputArchive));
+  }
+
+  private static void processClassAndDexFiles(
+      ZipFile zip,
+      DexFileAggregator out,
+      MergingDexer dexer,
+      Predicate<ZipEntry> extraFilter)
+      throws IOException {
+    @SuppressWarnings("unchecked") // Predicates.and uses varargs parameter with generics
+    ArrayList<? extends ZipEntry> filesToProcess =
+        Lists.newArrayList(
+            Iterators.filter(
+                Iterators.forEnumeration(zip.entries()),
+                Predicates.and(
+                    Predicates.not(ZipEntryPredicates.isDirectory()),
+                    ZipEntryPredicates.suffixes(".class", ".dex"),
+                    extraFilter)));
+    Collections.sort(filesToProcess, ZipEntryComparator.LIKE_DX);
+    for (ZipEntry entry : filesToProcess) {
+      String filename = entry.getName();
+      try (InputStream content = zip.getInputStream(entry)) {
+        if (filename.endsWith(".dex")) {
+          // 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.
+          out.add(new Dex(ByteStreams.toByteArray(content)));
+        } else if (filename.endsWith(".class")) {
+          dexer.add(Dexing.parseClassFile(ByteStreams.toByteArray(content), filename));
+        } else {
+          throw new IllegalStateException("Shouldn't get here: " + filename);
+        }
+      }
+    }
+  }
+
+  private static DexFileAggregator createDexFileAggregator(Options options) throws IOException {
+    return new DexFileAggregator(
+        new DexFileArchive(
+            new ZipOutputStream(
+                new BufferedOutputStream(Files.newOutputStream(options.outputArchive)))),
+        options.multidexMode,
+        options.maxNumberOfIdxPerDex,
+        options.wasteThresholdPerDex);
+  }
+
+  /**
+   * 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/DexFiles.java b/src/tools/android/java/com/google/devtools/build/android/dexer/DexFiles.java
new file mode 100644
index 0000000000..dc7004e42c
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/DexFiles.java
@@ -0,0 +1,42 @@
+// Copyright 2016 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.dx.dex.file.DexFile;
+
+import java.io.IOException;
+
+/**
+ * Helper methods to write out {@code dx}'s {@link DexFile} objects.
+ */
+public class DexFiles {
+
+  /**
+   * Returns the {@link Dex} file resulting from writing out the given {@link DexFile}.
+   */
+  public static Dex toDex(DexFile dex) throws IOException {
+    return new Dex(encode(dex));
+  }
+
+  /**
+   * Serializes the given {@link DexFile} into {@code .dex}'s file format.
+   */
+  static byte[] encode(DexFile dex) throws IOException {
+    return dex.toDex(null, false);
+  }
+
+  private DexFiles() {
+  }
+}
diff --git a/src/tools/android/java/com/google/devtools/build/android/dexer/Dexing.java b/src/tools/android/java/com/google/devtools/build/android/dexer/Dexing.java
new file mode 100644
index 0000000000..26fd9facaa
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/Dexing.java
@@ -0,0 +1,142 @@
+// Copyright 2016 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.auto.value.AutoValue;
+import com.google.common.annotations.VisibleForTesting;
+import com.google.devtools.common.options.Option;
+import com.google.devtools.common.options.OptionsBase;
+
+import com.android.dx.cf.direct.DirectClassFile;
+import com.android.dx.cf.direct.StdAttributeFactory;
+import com.android.dx.command.DxConsole;
+import com.android.dx.dex.DexOptions;
+import com.android.dx.dex.cf.CfOptions;
+import com.android.dx.dex.cf.CfTranslator;
+import com.android.dx.dex.code.PositionList;
+import com.android.dx.dex.file.ClassDefItem;
+import com.android.dx.dex.file.DexFile;
+import com.android.dx.util.ByteArray;
+
+/**
+ * Common helper class that encodes Java classes into {@link DexFile}s.
+ */
+class Dexing {
+
+  /**
+   * Common command line options for use with {@link Dexing}.
+   */
+  public static class DexingOptions extends OptionsBase {
+
+    @Option(name = "locals",
+        defaultValue = "true", // dx's default
+        category = "semantics",
+        allowMultiple = false,
+        help = "Whether to include local variable tables (useful for debugging).")
+    public boolean localInfo;
+
+    @Option(name = "optimize",
+        defaultValue = "true", // dx's default
+        category = "semantics",
+        allowMultiple = false,
+        help = "Whether to do SSA/register optimization.")
+    public boolean optimize;
+
+    @Option(name = "warning",
+        defaultValue = "true", // dx's default
+        category = "misc",
+        allowMultiple = false,
+        help = "Whether to print warnings.")
+    public boolean printWarnings;
+
+    public CfOptions toCfOptions() {
+      CfOptions result = new CfOptions();
+      result.localInfo = this.localInfo;
+      result.optimize = this.optimize;
+      result.warn = printWarnings ? DxConsole.err : DxConsole.noop;
+      // Use dx's defaults
+      result.optimizeListFile = null;
+      result.dontOptimizeListFile = null;
+      result.positionInfo = PositionList.LINES;
+      result.strictNameCheck = true;
+      result.statistics = false; // we're not supporting statistics anyways
+      return result;
+    }
+
+    public DexOptions toDexOptions() {
+      DexOptions result = new DexOptions();
+      result.forceJumbo = false; // dx's default
+      return result;
+    }
+  }
+
+  /**
+   * Class file and possible dexing options, to look up dexing results in caches.
+   */
+  @AutoValue
+  abstract static class DexingKey {
+    static DexingKey create(boolean localInfo, boolean optimize, byte[] classfileContent) {
+      // TODO(bazel-team): Maybe we can use a minimal collision hash instead of full content
+      return new AutoValue_Dexing_DexingKey(localInfo, optimize, classfileContent);
+    }
+
+    /** Returns whether {@link CfOptions#localInfo local variable information} is included. */
+    abstract boolean localInfo();
+
+    /** Returns whether {@link CfOptions#optimize SSA/register optimization} is performed. */
+    abstract boolean optimize();
+
+    /** Returns the class file to dex, <b>not</b> the dexed class. Don't modify the return value! */
+    @SuppressWarnings("mutable") abstract byte[] classfileContent();
+  }
+
+  private final DexOptions dexOptions;
+  private final CfOptions cfOptions;
+
+  public Dexing(DexingOptions options) {
+    this(options.toDexOptions(), options.toCfOptions());
+  }
+
+  @VisibleForTesting
+  Dexing(DexOptions dexOptions, CfOptions cfOptions) {
+    this.dexOptions = dexOptions;
+    this.cfOptions = cfOptions;
+  }
+
+  public static DirectClassFile parseClassFile(byte[] classfile, String classfilePath) {
+    DirectClassFile result = new DirectClassFile(
+        new ByteArray(classfile), classfilePath, /*strictParse*/ false);
+    result.setAttributeFactory(StdAttributeFactory.THE_ONE);
+    result.getMagic(); // triggers the parsing
+    return result;
+  }
+
+  public DexFile newDexFile() {
+    return new DexFile(dexOptions);
+  }
+
+  public ClassDefItem addToDexFile(DexFile dest, DirectClassFile classFile) {
+    ClassDefItem result = CfTranslator.translate(classFile,
+        (byte[]) null /*ignored*/,
+        cfOptions,
+        dest.getDexOptions(),
+        dest);
+    dest.add(result);
+    return result;
+  }
+
+  public DexingKey getDexingKey(byte[] classfile) {
+    return DexingKey.create(cfOptions.localInfo, cfOptions.optimize, classfile);
+  }
+}
diff --git a/src/tools/android/java/com/google/devtools/build/android/dexer/MergingDexer.java b/src/tools/android/java/com/google/devtools/build/android/dexer/MergingDexer.java
new file mode 100644
index 0000000000..0c565cbbd9
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/MergingDexer.java
@@ -0,0 +1,124 @@
+// Copyright 2016 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.checkState;
+
+import com.android.dx.cf.direct.DirectClassFile;
+import com.android.dx.dex.file.DexFile;
+
+import java.io.IOException;
+
+class MergingDexer {
+
+  // NB: The following two constants are copied from com.android.dx.command.dexer.Main
+
+  /**
+   * Maximum number of methods added during dexing:
+   * <ul>
+   * <li>Array.newInstance may be added by RopperMachine,
+   * <li>ArrayIndexOutOfBoundsException.<init> may be added by EscapeAnalysis
+   * </ul>
+   */
+  private static final int MAX_METHOD_ADDED_DURING_DEX_CREATION = 2;
+
+  /** Maximum number of fields added during dexing: &lt;primitive types box class&gt;.TYPE. */
+  private static final int MAX_FIELD_ADDED_DURING_DEX_CREATION = 9;
+
+  private final int maxNumberOfIdxPerDex;
+  private final Dexing dexing;
+  private final DexFileAggregator dest;
+  private final boolean multidex;
+  private DexFile currentShard;
+
+  public MergingDexer(
+      Dexing dexing,
+      DexFileAggregator dest,
+      boolean multidex,
+      int maxNumberOfIdxPerDex) {
+    this.dexing = dexing;
+    this.dest = dest;
+    this.multidex = multidex;
+    this.maxNumberOfIdxPerDex = maxNumberOfIdxPerDex;
+    currentShard = dexing.newDexFile();
+  }
+
+  public MergingDexer add(DirectClassFile classFile) throws IOException {
+    if (multidex && !currentShard.isEmpty()) {
+      // NB: This code is copied from com.android.dx.command.dexer.Main
+
+      // Calculate max number of indices this class will add to the
+      // dex file.
+      // The possibility of overloading means that we can't easily
+      // know how many constant are needed for declared methods and
+      // fields. We therefore make the simplifying assumption that
+      // all constants are external method or field references.
+
+      int constantPoolSize = classFile.getConstantPool().size();
+      int maxMethodIdsInClass = constantPoolSize + classFile.getMethods().size()
+              + MAX_METHOD_ADDED_DURING_DEX_CREATION;
+      int maxFieldIdsInClass = constantPoolSize + classFile.getFields().size()
+              + MAX_FIELD_ADDED_DURING_DEX_CREATION;
+
+      if (maxNumberOfIdxPerDex < getCurrentShardFieldCount() + maxFieldIdsInClass
+          || maxNumberOfIdxPerDex < getCurrentShardMethodCount() + maxMethodIdsInClass) {
+        // 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();
+      }
+    }
+
+    dexing.addToDexFile(currentShard, classFile);
+    return this;
+  }
+
+  public void finish() throws IOException {
+    if (currentShard != null && !currentShard.isEmpty()) {
+      dest.add(currentShard);
+    }
+    currentShard = null;
+  }
+
+  public void flush() throws IOException {
+    checkState(multidex);
+    if (!currentShard.isEmpty()) {
+      dest.add(currentShard);
+    }
+    currentShard = dexing.newDexFile();
+  }
+
+  private void rotateDexFile() throws IOException {
+    checkState(multidex);
+    checkState(!currentShard.isEmpty());
+    // We could take advantage here of knowing that currentShard is "full" and force dest to just
+    // write it out instead of it trying to merge currentShard with other .dex files.
+    // We're not doing that for the moment because that can cause problems when processing a
+    // main_dex_list: if dest's currentShard still contains classes from main_dex_list then writing
+    // our currentShard (with classes not from main dex list) separately would cause dest to write
+    // classes.dex with our currentShard and classes from main_dex_list to end up in classes2.dex or
+    // later, unless we prevent that case somehow (e.g., by knowing that order matters when writing
+    // the first shard).
+    dest.add(currentShard);
+    currentShard = dexing.newDexFile();
+  }
+
+  private int getCurrentShardMethodCount() {
+    return currentShard.getMethodIds().items().size();
+  }
+
+  private int getCurrentShardFieldCount() {
+    return currentShard.getFieldIds().items().size();
+  }
+}
diff --git a/src/tools/android/java/com/google/devtools/build/android/dexer/MultidexStrategy.java b/src/tools/android/java/com/google/devtools/build/android/dexer/MultidexStrategy.java
new file mode 100644
index 0000000000..f1903c7e3b
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/MultidexStrategy.java
@@ -0,0 +1,36 @@
+// Copyright 2016 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;
+
+/**
+ * Strategies for outputting multiple {@code .dex} files supported by {@link DexFileMerger}.
+ */
+public enum MultidexStrategy {
+  /** Create exactly one .dex file.  The operation will fail if .dex limits are exceeded. */
+  OFF,
+  /**
+   * Assemble .dex files similar to {@link com.android.dx.command.dexer.Main dx}, with all but one
+   * file as large as possible.
+   */
+  MINIMAL,
+  /**
+   * Allow some leeway and sometimes use additional .dex files to speed up processing.  This option
+   * exists to give flexibility but it often (or always) may be identical to {@link #MINIMAL}.
+   */
+  BEST_EFFORT;
+
+  public boolean isMultidexAllowed() {
+    return this != OFF;
+  }
+}
diff --git a/src/tools/android/java/com/google/devtools/build/android/dexer/ZipEntryContent.java b/src/tools/android/java/com/google/devtools/build/android/dexer/ZipEntryContent.java
new file mode 100644
index 0000000000..13795f5729
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/ZipEntryContent.java
@@ -0,0 +1,39 @@
+// Copyright 2016 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 java.util.zip.ZipEntry;
+
+/**
+ * Structured pair of file metadata encoded as {@link ZipEntry} and {@code byte[]} file content.
+ * Typically this class is used to represent an entry in a zip file.
+ */
+class ZipEntryContent {
+
+  private final ZipEntry entry;
+  private final byte[] content;
+
+  public ZipEntryContent(ZipEntry entry, byte[] content) {
+    this.entry = entry;
+    this.content = content;
+  }
+
+  public ZipEntry getEntry() {
+    return entry;
+  }
+
+  public byte[] getContent() {
+    return content;
+  }
+}
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
new file mode 100644
index 0000000000..dcdc6d7a3d
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/dexer/ZipEntryPredicates.java
@@ -0,0 +1,62 @@
+// Copyright 2016 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.base.Predicate;
+import com.google.common.collect.ImmutableSet;
+
+import java.util.zip.ZipEntry;
+
+class ZipEntryPredicates {
+
+  public static Predicate<ZipEntry> isDirectory() {
+    return new Predicate<ZipEntry>() {
+      @Override
+      public boolean apply(ZipEntry input) {
+        return input.isDirectory();
+      }
+    };
+  }
+
+  public static Predicate<ZipEntry> suffixes(final String... suffixes) {
+    return new Predicate<ZipEntry>() {
+      @Override
+      public boolean apply(ZipEntry input) {
+        String filename = input.getName();
+        for (String suffix : suffixes) {
+          if (filename.endsWith(suffix)) {
+            return true;
+          }
+        }
+        return false;
+      }
+    };
+  }
+
+  public static Predicate<ZipEntry> classFileFilter(final ImmutableSet<String> classFileNames) {
+    return new Predicate<ZipEntry>() {
+      @Override
+      public boolean apply(ZipEntry input) {
+        String filename = input.getName();
+        if (filename.endsWith(".class.dex")) {
+          // Chop off file suffix generated by DexBuilder
+          filename = filename.substring(0, filename.length() - ".dex".length());
+        }
+        return filename.endsWith(".class") && classFileNames.contains(filename);
+      }
+    };
+  }
+
+  private ZipEntryPredicates() {}
+}