Incremental dexing for sharded android_binary targets

--
MOS_MIGRATED_REVID=117186609

6 files changed, 502 insertions, 61 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinary.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinary.java
index 42ddaf11be..baa59b1f11 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinary.java
@@ -16,6 +16,7 @@ package com.google.devtools.build.lib.rules.android;
 import static com.google.common.base.Strings.isNullOrEmpty;
 
 import com.google.common.base.Optional;
+import com.google.common.base.Predicate;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
@@ -46,6 +47,7 @@ import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.packages.TriState;
 import com.google.devtools.build.lib.rules.RuleConfiguredTargetFactory;
+import com.google.devtools.build.lib.rules.android.AndroidConfiguration.IncrementalDexing;
 import com.google.devtools.build.lib.rules.android.AndroidRuleClasses.MultidexMode;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainProvider;
 import com.google.devtools.build.lib.rules.cpp.CppHelper;
@@ -373,8 +375,6 @@ public abstract class AndroidBinary implements RuleConfiguredTargetFactory {
             ? dexWithJack(ruleContext, androidCommon, proguardSpecs)
             : dex(
                 ruleContext,
-                getMultidexMode(ruleContext),
-                ruleContext.getTokenizedStringListAttr("dexopts"),
                 deployJar,
                 jarToDex,
                 androidCommon,
@@ -589,7 +589,7 @@ public abstract class AndroidBinary implements RuleConfiguredTargetFactory {
         resourceClasses,
         resourceApk,
         nativeLibs);
-    
+
     androidCommon.addTransitiveInfoProviders(
         builder, androidSemantics, resourceApk, zipAlignedApk, apksUnderTest);
     androidSemantics.addTransitiveInfoProviders(
@@ -758,7 +758,7 @@ public abstract class AndroidBinary implements RuleConfiguredTargetFactory {
         resourceClasses.getArchiveInputs(true), androidCommon.getRuntimeJars());
 
     AndroidSdkProvider sdk = AndroidSdkProvider.fromRuleContext(ruleContext);
-    
+
     ApkManifestAction manifestAction = new ApkManifestAction(
         ruleContext.getActionOwner(),
         apkManfiest,
@@ -953,11 +953,17 @@ public abstract class AndroidBinary implements RuleConfiguredTargetFactory {
     return new DexingOutput(classesDexZip, null, ImmutableList.of(classesDexZip));
   }
 
-  /** Dexes the ProguardedJar to generate ClassesDex that has a reference classes.dex. */
-  private static DexingOutput dex(RuleContext ruleContext, MultidexMode multidexMode,
-      List<String> dexopts, Artifact deployJar,  Artifact proguardedJar, AndroidCommon common,
-      JavaTargetAttributes attributes) throws InterruptedException {
-    String classesDexFileName = getMultidexMode(ruleContext).getOutputDexFilename();
+  /** Creates one or more classes.dex files that correspond to {@code proguardedJar}. */
+  private static DexingOutput dex(
+      RuleContext ruleContext,
+      Artifact deployJar,
+      Artifact proguardedJar,
+      AndroidCommon common,
+      JavaTargetAttributes attributes)
+      throws InterruptedException {
+    List<String> dexopts = ruleContext.getTokenizedStringListAttr("dexopts");
+    MultidexMode multidexMode = getMultidexMode(ruleContext);
+    String classesDexFileName = multidexMode.getOutputDexFilename();
     Artifact classesDex = AndroidBinary.getDxArtifact(ruleContext, classesDexFileName);
     if (!AndroidBinary.supportsMultidexMode(ruleContext, multidexMode)) {
       ruleContext.ruleError("Multidex mode \"" + multidexMode.getAttributeValue()
@@ -995,19 +1001,28 @@ public abstract class AndroidBinary implements RuleConfiguredTargetFactory {
       }
 
       if (dexShards > 1) {
-        List<Artifact> shardJars = new ArrayList<>(dexShards);
+        List<Artifact> shards = new ArrayList<>(dexShards);
         for (int i = 1; i <= dexShards; i++) {
-          shardJars.add(getDxArtifact(ruleContext, "shard" + i + ".jar"));
+          shards.add(getDxArtifact(ruleContext, "shard" + i + ".jar"));
         }
 
-        CustomCommandLine.Builder shardCommandLine = CustomCommandLine.builder()
-            .addBeforeEachExecPath("--output_jar", shardJars);
-
         Artifact javaResourceJar =
             ruleContext.getImplicitOutputArtifact(AndroidRuleClasses.JAVA_RESOURCES_JAR);
 
+        SpawnAction.Builder shardAction = new SpawnAction.Builder()
+            .setMnemonic("ShardClassesToDex")
+            .setProgressMessage("Sharding classes for dexing for " + ruleContext.getLabel())
+            .setExecutable(ruleContext.getExecutablePrerequisite("$shuffle_jars", Mode.HOST))
+            .addOutputs(shards)
+            .addOutput(javaResourceJar);
+
+        CustomCommandLine.Builder shardCommandLine = CustomCommandLine.builder()
+            .addBeforeEachExecPath("--output_jar", shards)
+            .addExecPath("--output_resources", javaResourceJar);
+
         if (mainDexList != null) {
           shardCommandLine.addExecPath("--main_dex_filter", mainDexList);
+          shardAction.addInput(mainDexList);
         }
 
         // If we need to run Proguard, all the class files will be in the Proguarded jar and the
@@ -1015,44 +1030,54 @@ public abstract class AndroidBinary implements RuleConfiguredTargetFactory {
         // contain all the Java resources. Otherwise, we don't want to have deploy jar creation on
         // the critical path, so we put all the jar files that constitute it on the inputs of the
         // jar shuffler.
+        boolean useDexArchives = false;
         if (proguardedJar != deployJar) {
+          // When proguard is used we can't use dex archives, so just shuffle the proguarded jar
           shardCommandLine.addExecPath("--input_jar", proguardedJar);
-        } else {
-          shardCommandLine
-              .addBeforeEachExecPath("--input_jar", common.getRuntimeJars())
-              .addBeforeEachExecPath("--input_jar", attributes.getRuntimeClassPathForArchive());
-        }
-
-        shardCommandLine.addExecPath("--output_resources", javaResourceJar);
-
-        SpawnAction.Builder shardAction = new SpawnAction.Builder()
-            .setMnemonic("ShardClassesToDex")
-            .setProgressMessage("Sharding classes for dexing for " + ruleContext.getLabel())
-            .setExecutable(ruleContext.getExecutablePrerequisite("$shuffle_jars", Mode.HOST))
-            .addOutputs(shardJars)
-            .addOutput(javaResourceJar)
-            .setCommandLine(shardCommandLine.build());
-
-        if (mainDexList != null) {
-          shardAction.addInput(mainDexList);
-        }
-        if (proguardedJar != deployJar) {
           shardAction.addInput(proguardedJar);
         } else {
-          shardAction
-              .addInputs(common.getRuntimeJars())
-              .addInputs(attributes.getRuntimeClassPathForArchive());
+          Iterable<Artifact> classpath =
+              Iterables.concat(common.getRuntimeJars(), attributes.getRuntimeClassPathForArchive());
+          // Check whether we can use dex archives.  Besides the --incremental_dexing flag, also
+          // make sure the "dexopts" attribute on this target doesn't mention any problematic flags.
+          useDexArchives =
+              AndroidCommon.getAndroidConfig(ruleContext).getIncrementalDexing()
+                  != IncrementalDexing.OFF
+              && !Iterables.any(dexopts,
+                  new FlagMatcher(AndroidCommon
+                      .getAndroidConfig(ruleContext)
+                      .getTargetDexoptsThatPreventIncrementalDexing()));
+          if (useDexArchives) {
+            // Use dex archives instead of their corresponding Jars wherever we can.  At this point
+            // there should be very few or no Jar files that still end up in shards.  The dexing
+            // step below will have to deal with those in addition to merging .dex files together.
+            classpath = Iterables.transform(classpath, collectDexArchives(ruleContext, common));
+            shardCommandLine.add("--split_dexed_classes");
+          }
+          shardCommandLine.addBeforeEachExecPath("--input_jar", classpath);
+          shardAction.addInputs(classpath);
         }
 
+        shardAction.setCommandLine(shardCommandLine.build());
         ruleContext.registerAction(shardAction.build(ruleContext));
 
         List<Artifact> shardDexes = new ArrayList<>(dexShards);
         for (int i = 1; i <= dexShards; i++) {
-          Artifact shardJar = shardJars.get(i - 1);
-          Artifact shard = getDxArtifact(ruleContext, "shard" + i + ".dex.zip");
-          shardDexes.add(shard);
-          AndroidCommon.createDexAction(
-              ruleContext, shardJar, shard, dexopts, true, null);
+          Artifact shard = shards.get(i - 1);
+          Artifact shardDex = getDxArtifact(ruleContext, "shard" + i + ".dex.zip");
+          shardDexes.add(shardDex);
+          if (useDexArchives) {
+            // If there's a main dex list then the first shard contains exactly those files.
+            // To work with devices that lack native multi-dex support we need to make sure that
+            // the main dex list becomes one dex file if at all possible.
+            // Note shard here (mostly) contains of .class.dex files from shuffled dex archives,
+            // instead of being a conventional Jar file with .class files.
+            String multidexStrategy = mainDexList != null && i == 1 ? "minimal" : "best_effort";
+            createDexMergerAction(ruleContext, multidexStrategy, shard, shardDex);
+          } else {
+            AndroidCommon.createDexAction(
+                ruleContext, shard, shardDex, dexopts, /* multidex */ true, (Artifact) null);
+          }
         }
 
         CommandLine mergeCommandLine = CustomCommandLine.builder()
@@ -1084,6 +1109,50 @@ public abstract class AndroidBinary implements RuleConfiguredTargetFactory {
     }
   }
 
+  private static void createDexMergerAction(
+      RuleContext ruleContext, String multidexStrategy, Artifact inputJar, Artifact classesDex) {
+    SpawnAction.Builder dexmerger = new SpawnAction.Builder()
+        .setExecutable(ruleContext.getExecutablePrerequisite("$dexmerger", Mode.HOST))
+        .addArgument("--input")
+        .addInputArgument(inputJar)
+        .addArgument("--output")
+        .addOutputArgument(classesDex)
+        .addArgument("--multidex=" + multidexStrategy)
+        .setMnemonic("DexMerger")
+        .setProgressMessage("Assembling dex files into " + classesDex.prettyPrint());
+    if (ruleContext.getConfiguration().isCodeCoverageEnabled()) {
+      // Match what we do in AndroidCommon.createDexAction
+      dexmerger.addArgument("--nolocals"); // TODO(bazel-team): Still needed? See createDexAction
+    }
+    ruleContext.registerAction(dexmerger.build(ruleContext));
+  }
+
+  /**
+   * Returns a {@link DexArchiveProvider} of all transitively generated dex archives as well as
+   * dex archives for the Jars produced by the binary target itself.
+   */
+  private static DexArchiveProvider collectDexArchives(
+      RuleContext ruleContext, AndroidCommon common) {
+    DexArchiveProvider.Builder result = new DexArchiveProvider.Builder()
+        // Use providers from all attributes that declare DexArchiveAspect
+        .addTransitiveProviders(
+            ruleContext.getPrerequisites("deps", Mode.TARGET, DexArchiveProvider.class));
+    for (Artifact jar : common.getJarsProducedForRuntime()) {
+      // Create dex archives next to all Jars produced by AndroidCommon for this rule.  We need to
+      // do this (instead of placing dex archives into the _dx subdirectory like DexArchiveAspect
+      // does because for "legacy" ResourceApks, AndroidCommon produces Jars per resource dependency
+      // that can theoretically have duplicate basenames, so they go into special directories, and
+      // we piggyback on that naming scheme here by placing dex archives into the same directories.
+      PathFragment jarPath = jar.getRootRelativePath();
+      Artifact dexArchive = ruleContext.getDerivedArtifact(
+          jarPath.replaceName(jarPath.getBaseName() + ".dex.zip"),
+          jar.getRoot());
+      DexArchiveAspect.createDexArchiveAction(ruleContext, jar, dexArchive);
+      result.addDexArchive(dexArchive, jar);
+    }
+    return result.build();
+  }
+
   /**
    * Creates an action that copies a .zip file to a specified path, filtering all non-.dex files
    * out of the output.
@@ -1442,4 +1511,22 @@ public abstract class AndroidBinary implements RuleConfiguredTargetFactory {
     return ruleContext.getUniqueDirectoryArtifact("_dx", baseName,
         ruleContext.getBinOrGenfilesDirectory());
   }
+
+  private static class FlagMatcher implements Predicate<String> {
+    private final ImmutableList<String> matching;
+
+    FlagMatcher(ImmutableList<String> matching) {
+      this.matching = matching;
+    }
+
+    @Override
+    public boolean apply(String input) {
+      for (String match : matching) {
+        if (input.contains(match)) {
+          return true;
+        }
+      }
+      return false;
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCommon.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCommon.java
index ed61872a7c..bd1dd656ee 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCommon.java
@@ -128,6 +128,7 @@ public class AndroidCommon {
   private JavaCompilationArgs javaCompilationArgs = JavaCompilationArgs.EMPTY_ARGS;
   private JavaCompilationArgs recursiveJavaCompilationArgs = JavaCompilationArgs.EMPTY_ARGS;
   private JackCompilationHelper jackCompilationHelper;
+  private ImmutableList<Artifact> jarsProducedForRuntime;
   private Artifact classJar;
   private Artifact iJar;
   private Artifact srcJar;
@@ -199,10 +200,12 @@ public class AndroidCommon {
       Artifact mainDexList) {
     List<String> args = new ArrayList<>();
     args.add("--dex");
-    // Add --no-locals to coverage builds. Otherwise local variable debug information is not
-    // preserved, which leads to runtime errors.
+    // Add --no-locals to coverage builds.  Older coverage tools don't correctly preserve local
+    // variable information in stack frame maps that are required since Java 7, so to avoid runtime
+    // errors we just don't add local variable info in the first place.  This may no longer be
+    // necessary, however, as long as we use a coverage tool that generates stack frame maps.
     if (ruleContext.getConfiguration().isCodeCoverageEnabled()) {
-      args.add("--no-locals");
+      args.add("--no-locals");  // TODO(bazel-team): Is this still needed?
     }
 
     // Multithreaded dex does not work when using --multi-dex.
@@ -365,7 +368,8 @@ public class AndroidCommon {
       Artifact resourcesJar,
       JavaCompilationArtifacts.Builder artifactsBuilder,
       JavaTargetAttributes.Builder attributes,
-      NestedSetBuilder<Artifact> filesBuilder) throws InterruptedException {
+      NestedSetBuilder<Artifact> filesBuilder,
+      ImmutableList.Builder<Artifact> jarsProducedForRuntime) throws InterruptedException {
     compileResourceJar(javaSemantics, resourcesJar);
     // Add the compiled resource jar to the classpath of the main compilation.
     attributes.addDirectJars(ImmutableList.of(resourceClassJar));
@@ -375,6 +379,7 @@ public class AndroidCommon {
     // Combined resource constants needs to come even before our own classes that may contain
     // local resource constants.
     artifactsBuilder.addRuntimeJar(resourceClassJar);
+    jarsProducedForRuntime.add(resourceClassJar);
     // Add the compiled resource jar as a declared output of the rule.
     filesBuilder.add(resourceSourceJar);
     filesBuilder.add(resourceClassJar);
@@ -407,6 +412,7 @@ public class AndroidCommon {
 
   private void createJarJarActions(
       JavaTargetAttributes.Builder attributes,
+      ImmutableList.Builder<Artifact> jarsProducedForRuntime,
       Iterable<ResourceContainer> resourceContainers,
       String originalPackage,
       Artifact binaryResourcesJar) {
@@ -443,6 +449,7 @@ public class AndroidCommon {
           .setProgressMessage("Repackaging jar")
           .setMnemonic("AndroidRepackageJar")
           .build(ruleContext));
+      jarsProducedForRuntime.add(resourcesJar);
     }
   }
 
@@ -474,16 +481,19 @@ public class AndroidCommon {
             AndroidSdkProvider.fromRuleContext(ruleContext).getAndroidJar()));
 
     JavaCompilationArtifacts.Builder artifactsBuilder = new JavaCompilationArtifacts.Builder();
+    ImmutableList.Builder<Artifact> jarsProducedForRuntime = ImmutableList.builder();
     NestedSetBuilder<Artifact> filesBuilder = NestedSetBuilder.<Artifact>stableOrder();
 
     Artifact resourcesJar = resourceApk.getResourceJavaSrcJar();
     if (resourcesJar != null) {
       filesBuilder.add(resourcesJar);
-      compileResources(javaSemantics, resourcesJar, artifactsBuilder, attributes, filesBuilder);
+      compileResources(javaSemantics, resourcesJar, artifactsBuilder, attributes, filesBuilder,
+          jarsProducedForRuntime);
       if (resourceApk.isLegacy()) {
         // Repackages the R.java for each dependency package and places the resultant jars before
         // the dependency libraries to ensure that the generated resource ids are correct.
-        createJarJarActions(attributes, resourceApk.getResourceDependencies().getResources(),
+        createJarJarActions(attributes, jarsProducedForRuntime,
+            resourceApk.getResourceDependencies().getResources(),
             resourceApk.getPrimaryResource().getJavaPackage(), resourceClassJar);
       }
     }
@@ -510,6 +520,7 @@ public class AndroidCommon {
     if (ruleContext.hasErrors()) {
       return null;
     }
+    this.jarsProducedForRuntime = jarsProducedForRuntime.add(classJar).build();
     return helper.getAttributes();
   }
 
@@ -517,7 +528,7 @@ public class AndroidCommon {
       JavaTargetAttributes.Builder attributes, JavaSemantics semantics) {
     JavaCompilationHelper helper = new JavaCompilationHelper(
         ruleContext, semantics, javaCommon.getJavacOpts(), attributes);
-    
+
     helper.addLibrariesToAttributes(javaCommon.targetsTreatedAsDeps(ClasspathType.COMPILE_ONLY));
     helper.addProvidersToAttributes(
         JavaCommon.compilationArgsFromSources(ruleContext), asNeverLink);
@@ -600,7 +611,7 @@ public class AndroidCommon {
     helper.createCompileActionWithInstrumentation(classJar, manifestProtoOutput, genSourceJar,
         outputDepsProto, javaArtifactsBuilder);
 
-    compileTimeDependencyArtifacts = 
+    compileTimeDependencyArtifacts =
         javaCommon.collectCompileTimeDependencyArtifacts(outputDepsProto);
     filesToBuild = filesBuilder.build();
 
@@ -631,7 +642,7 @@ public class AndroidCommon {
           true, asNeverLink, /* hasSources */ true);
     }
   }
-  
+
   public RuleConfiguredTargetBuilder addTransitiveInfoProviders(
       RuleConfiguredTargetBuilder builder,
       AndroidSemantics androidSemantics,
@@ -684,7 +695,7 @@ public class AndroidCommon {
             OutputGroupProvider.HIDDEN_TOP_LEVEL, collectHiddenTopLevelArtifacts(ruleContext))
         .addOutputGroup(JavaSemantics.SOURCE_JARS_OUTPUT_GROUP, transitiveSourceJars);
   }
-  
+
   private Runfiles getRunfiles() {
     // TODO(bazel-team): why return any Runfiles in the neverlink case?
     if (asNeverLink) {
@@ -760,7 +771,7 @@ public class AndroidCommon {
       boolean hasSrcs) {
     boolean exportDeps = !hasSrcs
         && ruleContext.getFragment(AndroidConfiguration.class).allowSrcsLessAndroidLibraryDeps();
-    Iterable<SourcesJavaCompilationArgsProvider> fromSrcs = 
+    Iterable<SourcesJavaCompilationArgsProvider> fromSrcs =
         ImmutableList.<SourcesJavaCompilationArgsProvider> of();
     return javaCommon.collectJavaCompilationArgs(recursive, isNeverLink, fromSrcs, exportDeps);
   }
@@ -781,6 +792,15 @@ public class AndroidCommon {
     return javaCommon.getJavaCompilationArtifacts().getRuntimeJars();
   }
 
+  /**
+   * Returns Jars produced by this rule that may go into the runtime classpath.  By contrast
+   * {@link #getRuntimeJars()} returns the complete runtime classpath needed by this rule, including
+   * dependencies.
+   */
+  public ImmutableList<Artifact> getJarsProducedForRuntime() {
+    return jarsProducedForRuntime;
+  }
+
   public Artifact getInstrumentedJar() {
     return javaCommon.getJavaCompilationArtifacts().getInstrumentedJar();
   }
@@ -826,6 +846,13 @@ public class AndroidCommon {
     };
   }
 
+  /**
+   * Returns {@link AndroidConfiguration} in given context.
+   */
+  static AndroidConfiguration getAndroidConfig(RuleContext context) {
+    return context.getConfiguration().getFragment(AndroidConfiguration.class);
+  }
+
   private NestedSet<Artifact> collectHiddenTopLevelArtifacts(RuleContext ruleContext) {
     NestedSetBuilder<Artifact> builder = NestedSetBuilder.stableOrder();
     for (OutputGroupProvider provider :
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidConfiguration.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidConfiguration.java
index 83ac2aa738..a2637cf641 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidConfiguration.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidConfiguration.java
@@ -52,6 +52,25 @@ public class AndroidConfiguration extends BuildConfiguration.Fragment {
   }
 
   /**
+   * Converter for {@link com.google.devtools.build.lib.rules.android.AndroidConfiguration.ConfigurationDistinguisher}
+   */
+  public static final class ConfigurationDistinguisherConverter
+      extends EnumConverter<ConfigurationDistinguisher> {
+    public ConfigurationDistinguisherConverter() {
+      super(ConfigurationDistinguisher.class, "Android configuration distinguisher");
+    }
+  }
+
+  /**
+   * Converter for {@link IncrementalDexing}.
+   */
+  public static final class IncrementalDexingConverter extends EnumConverter<IncrementalDexing> {
+    public IncrementalDexingConverter() {
+      super(IncrementalDexing.class, "use incremental dexing");
+    }
+  }
+
+  /**
    * Value used to avoid multiple configurations from conflicting.
    *
    * <p>This is set to {@code ANDROID} in Android configurations and to {@code MAIN} otherwise. This
@@ -73,14 +92,9 @@ public class AndroidConfiguration extends BuildConfiguration.Fragment {
     }
   }
 
-  /**
-   * Converter for {@link com.google.devtools.build.lib.rules.android.AndroidConfiguration.ConfigurationDistinguisher}
-   */
-  public static final class ConfigurationDistinguisherConverter
-      extends EnumConverter<ConfigurationDistinguisher> {
-    public ConfigurationDistinguisherConverter() {
-      super(ConfigurationDistinguisher.class, "Android configuration distinguisher");
-    }
+  /** When to use incremental dexing (using {@link DexArchiveProvider}). */
+  public enum IncrementalDexing {
+    OFF, WITH_DEX_SHARDS,
   }
 
   /**
@@ -173,6 +187,28 @@ public class AndroidConfiguration extends BuildConfiguration.Fragment {
         help = "Enables sanity checks for Jack and Jill compilation.")
     public boolean jackSanityChecks;
 
+    // Do not use on the command line.
+    // The idea is that once this option works, we'll flip the default value in a config file, then
+    // once it is proven that it works, remove it from Bazel and said config file.
+    @Option(name = "experimental_incremental_dexing",
+        defaultValue = "off",
+        category = "undocumented",
+        converter = IncrementalDexingConverter.class,
+        help = "Does most of the work for dexing separately for each Jar file.  Incompatible with "
+            + "Jack and Jill.")
+    public IncrementalDexing dexingStrategy;
+
+    @Option(name = "non_incremental_per_target_dexopts",
+        converter = Converters.CommaSeparatedOptionListConverter.class,
+        defaultValue = "--no-locals",
+        category = "undocumented",
+        help = "dx flags that that prevent incremental dexing for binary targets that list any of "
+            + "the flags listed here in their 'dexopts' attribute, which are ignored with "
+            + "incremental dexing.  Defaults to --no-locals for safety but can in general be used "
+            + "to make sure the listed dx flags are honored, with additional build latency.  "
+            + "Please notify us if you find yourself needing this flag.")
+    public List<String> nonIncrementalPerTargetDexopts;
+
     @Option(name = "experimental_allow_android_library_deps_without_srcs",
         defaultValue = "true",
         category = "undocumented",
@@ -254,6 +290,8 @@ public class AndroidConfiguration extends BuildConfiguration.Fragment {
   private final ConfigurationDistinguisher configurationDistinguisher;
   private final boolean useJackForDexing;
   private final boolean jackSanityChecks;
+  private final IncrementalDexing dexingStrategy;
+  private final ImmutableList<String> targetDexoptsThatPreventIncrementalDexing;
   private final boolean allowAndroidLibraryDepsWithoutSrcs;
   private final boolean useAndroidResourceShrinking;
 
@@ -267,6 +305,9 @@ public class AndroidConfiguration extends BuildConfiguration.Fragment {
     this.configurationDistinguisher = options.configurationDistinguisher;
     this.useJackForDexing = options.useJackForDexing;
     this.jackSanityChecks = options.jackSanityChecks;
+    this.dexingStrategy = options.dexingStrategy;
+    this.targetDexoptsThatPreventIncrementalDexing =
+        ImmutableList.copyOf(options.nonIncrementalPerTargetDexopts);
     this.allowAndroidLibraryDepsWithoutSrcs = options.allowAndroidLibraryDepsWithoutSrcs;
     this.useAndroidResourceShrinking = options.useAndroidResourceShrinking;
   }
@@ -310,6 +351,22 @@ public class AndroidConfiguration extends BuildConfiguration.Fragment {
     return incrementalNativeLibs;
   }
 
+  /**
+   * Returns when to use incremental dexing using {@link DexArchiveProvider}.  Note this is disabled
+   * if {@link #isJackUsedForDexing()}.
+   */
+  public IncrementalDexing getIncrementalDexing() {
+    return isJackUsedForDexing() ? IncrementalDexing.OFF : dexingStrategy;
+  }
+
+  /**
+   * Regardless of {@link #getIncrementalDexing}, incremental dexing must not be used for binaries
+   * that list any of these flags in their {@code dexopts} attribute.
+   */
+  public ImmutableList<String> getTargetDexoptsThatPreventIncrementalDexing() {
+    return targetDexoptsThatPreventIncrementalDexing;
+  }
+
   public boolean allowSrcsLessAndroidLibraryDeps() {
     return allowAndroidLibraryDepsWithoutSrcs;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidRuleClasses.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidRuleClasses.java
index 96315719a9..c1d12ed7ee 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidRuleClasses.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidRuleClasses.java
@@ -62,10 +62,16 @@ import javax.annotation.Nullable;
  * Rule definitions for Android rules.
  */
 public final class AndroidRuleClasses {
+  /** Sources generated by a given target, in particular, {@code R.java}. */
   public static final SafeImplicitOutputsFunction ANDROID_JAVA_SOURCE_JAR =
       fromTemplates("%{name}.srcjar");
+  /** Sources compiled in a given target, excluding {@link #ANDROID_JAVA_SOURCE_JAR}. */
   public static final SafeImplicitOutputsFunction ANDROID_LIBRARY_SOURCE_JAR =
       JavaSemantics.JAVA_LIBRARY_SOURCE_JAR;
+  /**
+   * Compiled sources of a given target, excluding {@link #ANDROID_JAVA_SOURCE_JAR}. This is the
+   * conventional output Jar of any java library target, including android libs.
+   */
   public static final SafeImplicitOutputsFunction ANDROID_LIBRARY_CLASS_JAR =
       JavaSemantics.JAVA_LIBRARY_CLASS_JAR;
   public static final SafeImplicitOutputsFunction ANDROID_LIBRARY_JACK_FILE =
@@ -74,8 +80,13 @@ public final class AndroidRuleClasses {
       fromTemplates("%{name}.aar");
   public static final SafeImplicitOutputsFunction ANDROID_LIBRARY_AAR_CLASSES_JAR =
       fromTemplates("%{name}_aar/classes.jar");
+  /**
+   * Source Jar for {@link #ANDROID_RESOURCES_CLASS_JAR}, which should be the same as
+   * {@link #ANDROID_JAVA_SOURCE_JAR}.
+   */
   public static final SafeImplicitOutputsFunction ANDROID_RESOURCES_SOURCE_JAR =
       fromTemplates("%{name}_resources-src.jar");
+  /** Compiled {@link #ANDROID_JAVA_SOURCE_JAR}. */
   public static final SafeImplicitOutputsFunction ANDROID_RESOURCES_CLASS_JAR =
       fromTemplates("%{name}_resources.jar");
   public static final SafeImplicitOutputsFunction ANDROID_RESOURCES_APK =
@@ -556,6 +567,7 @@ public final class AndroidRuleClasses {
               .allowedRuleClasses(ALLOWED_DEPENDENCIES)
               .allowedFileTypes()
               .aspect(AndroidNeverlinkAspect.class)
+              .aspect(DexArchiveAspect.class)
               .aspect(JackAspect.class))
           // Proguard rule specifying master list of classes to keep during legacy multidexing.
           .add(attr("$build_incremental_dexmanifest", LABEL).cfg(HOST).exec()
@@ -564,6 +576,10 @@ public final class AndroidRuleClasses {
               .value(env.getToolsLabel(STUBIFY_MANIFEST_LABEL)))
           .add(attr("$shuffle_jars", LABEL).cfg(HOST).exec()
               .value(env.getToolsLabel("//tools/android:shuffle_jars")))
+          .add(attr("$dexbuilder", LABEL).cfg(HOST).exec()
+              .value(env.getToolsLabel("//tools/android:dexbuilder")))
+          .add(attr("$dexmerger", LABEL).cfg(HOST).exec()
+              .value(env.getToolsLabel("//tools/android:dexmerger")))
           .add(attr("$merge_dexzips", LABEL).cfg(HOST).exec()
               .value(env.getToolsLabel("//tools/android:merge_dexzips")))
           .add(attr("$incremental_install", LABEL).cfg(HOST).exec()
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/DexArchiveAspect.java b/src/main/java/com/google/devtools/build/lib/rules/android/DexArchiveAspect.java
new file mode 100644
index 0000000000..7e396af425
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/DexArchiveAspect.java
@@ -0,0 +1,127 @@
+// 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.lib.rules.android;
+
+import static com.google.common.base.Preconditions.checkState;
+import static com.google.devtools.build.lib.Constants.TOOLS_REPOSITORY;
+import static com.google.devtools.build.lib.packages.Attribute.ConfigurationTransition.HOST;
+import static com.google.devtools.build.lib.packages.Attribute.attr;
+import static com.google.devtools.build.lib.packages.BuildType.LABEL;
+import static com.google.devtools.build.lib.packages.BuildType.LABEL_LIST;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.analysis.ConfiguredAspect;
+import com.google.devtools.build.lib.analysis.ConfiguredAspectFactory;
+import com.google.devtools.build.lib.analysis.ConfiguredTarget;
+import com.google.devtools.build.lib.analysis.RuleConfiguredTarget.Mode;
+import com.google.devtools.build.lib.analysis.RuleContext;
+import com.google.devtools.build.lib.analysis.actions.SpawnAction;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.packages.AspectDefinition;
+import com.google.devtools.build.lib.packages.AspectParameters;
+import com.google.devtools.build.lib.packages.NativeAspectClass.NativeAspectFactory;
+import com.google.devtools.build.lib.rules.java.JavaCommon;
+import com.google.devtools.build.lib.rules.java.JavaCompilationArgsProvider;
+import com.google.devtools.build.lib.rules.java.JavaRuntimeJarProvider;
+
+/**
+ * Aspect to {@link DexArchiveProvider build .dex Archives} from Jars.
+ */
+public final class DexArchiveAspect implements NativeAspectFactory, ConfiguredAspectFactory {
+  private static final String NAME = "DexArchiveAspect";
+  private static final ImmutableList<String> TRANSITIVE_ATTRIBUTES =
+      ImmutableList.of("deps", "exports", "runtime_deps");
+
+  @Override
+  public AspectDefinition getDefinition(AspectParameters params) {
+    AspectDefinition.Builder result = new AspectDefinition.Builder(NAME)
+        // Actually we care about JavaRuntimeJarProvider, but rules don't advertise that provider.
+        .requireProvider(JavaCompilationArgsProvider.class)
+        .add(attr("$dexbuilder", LABEL).cfg(HOST).exec()
+        // Parse label here since we don't have RuleDefinitionEnvironment.getLabel like in a rule
+            .value(Label.parseAbsoluteUnchecked(TOOLS_REPOSITORY + "//tools/android:dexbuilder")))
+        .requiresConfigurationFragments(AndroidConfiguration.class);
+    for (String attr : TRANSITIVE_ATTRIBUTES) {
+      result.attributeAspect(attr, DexArchiveAspect.class);
+    }
+    return result.build();
+  }
+
+  @Override
+  public ConfiguredAspect create(ConfiguredTarget base, RuleContext ruleContext,
+      AspectParameters params) throws InterruptedException {
+    if (AndroidCommon.getAndroidConfig(ruleContext).getIncrementalDexing()
+        == AndroidConfiguration.IncrementalDexing.OFF) {
+      // Dex archives will never be used, so don't bother setting them up.
+      return new ConfiguredAspect.Builder(NAME, ruleContext).build();
+    }
+    checkState(base.getProvider(DexArchiveProvider.class) == null,
+        "dex archive natively generated: %s", ruleContext.getLabel());
+
+    if (JavaCommon.isNeverLink(ruleContext)) {
+      return new ConfiguredAspect.Builder(NAME, ruleContext)
+          .addProvider(DexArchiveProvider.class, DexArchiveProvider.NEVERLINK)
+          .build();
+    }
+
+    DexArchiveProvider.Builder result = createArchiveProviderBuilderFromDeps(ruleContext);
+    JavaRuntimeJarProvider jarProvider = base.getProvider(JavaRuntimeJarProvider.class);
+    if (jarProvider != null) {
+      for (Artifact jar : jarProvider.getRuntimeJars()) {
+        Artifact dexArchive = createDexArchiveAction(ruleContext, jar);
+        result.addDexArchive(dexArchive, jar);
+      }
+    }
+    return new ConfiguredAspect.Builder(NAME, ruleContext)
+        .addProvider(DexArchiveProvider.class, result.build())
+        .build();
+  }
+
+  private static DexArchiveProvider.Builder createArchiveProviderBuilderFromDeps(
+      RuleContext ruleContext) {
+    DexArchiveProvider.Builder result = new DexArchiveProvider.Builder();
+    for (String attr : TRANSITIVE_ATTRIBUTES) {
+      if (ruleContext.getRule().getRuleClassObject().hasAttr(attr, LABEL_LIST)) {
+        result.addTransitiveProviders(
+            ruleContext.getPrerequisites(attr, Mode.TARGET, DexArchiveProvider.class));
+      }
+    }
+    return result;
+  }
+
+  private static Artifact createDexArchiveAction(RuleContext ruleContext, Artifact jar) {
+    Artifact result = AndroidBinary.getDxArtifact(ruleContext, jar.getFilename() + ".dex.zip");
+    createDexArchiveAction(ruleContext, jar, result);
+    return result;
+  }
+
+  // Package-private methods for use in AndroidBinary
+
+  static void createDexArchiveAction(RuleContext ruleContext, Artifact jar, Artifact dexArchive) {
+    SpawnAction.Builder dexbuilder = new SpawnAction.Builder()
+        .setExecutable(ruleContext.getExecutablePrerequisite("$dexbuilder", Mode.HOST))
+        .addArgument("--input_jar")
+        .addInputArgument(jar)
+        .addArgument("--output_zip")
+        .addOutputArgument(dexArchive)
+        .setMnemonic("DexBuilder")
+        .setProgressMessage("Dexing " + jar.prettyPrint());
+    if (ruleContext.getConfiguration().isCodeCoverageEnabled()) {
+      // Match what we do in AndroidCommon.createDexAction
+      dexbuilder.addArgument("--nolocals"); // TODO(bazel-team): Still needed? See createDexAction
+    }
+    ruleContext.registerAction(dexbuilder.build(ruleContext));
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/DexArchiveProvider.java b/src/main/java/com/google/devtools/build/lib/rules/android/DexArchiveProvider.java
new file mode 100644
index 0000000000..6ced3815de
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/DexArchiveProvider.java
@@ -0,0 +1,127 @@
+// 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.lib.rules.android;
+
+import static com.google.common.base.Preconditions.checkArgument;
+import static com.google.common.base.Preconditions.checkNotNull;
+
+import com.google.common.base.Function;
+import com.google.common.collect.BiMap;
+import com.google.common.collect.HashBiMap;
+import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.analysis.TransitiveInfoProvider;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+
+import javax.annotation.Nullable;
+
+/**
+ * Provider of transitively available dex archives corresponding to Jars.  A dex archive is a zip of
+ * {@code .dex} files that each encode exactly one {@code .class} file in an Android-readable form.
+ * The file names in a dex archive should match the file names in the originating Jar file, except
+ * with {@code .dex} appended, i.e., {@code <package/for/ClassName[$Inner].class.dex}.
+ *
+ * <p>For convenience this class implements a {@link Function} to map from Jars to dex archives if
+ * available (returns the given Jar otherwise).
+ */
+@Immutable
+public class DexArchiveProvider implements TransitiveInfoProvider, Function<Artifact, Artifact> {
+
+  /**
+   * Provider that doesn't provide any dex archives, which is what any neverlink target should use.
+   * It's not strictly necessary to handle neverlink specially, but doing so reduces the amount
+   * of processing done for targets that won't be used for dexing anyway.
+   */
+  public static final DexArchiveProvider NEVERLINK = new DexArchiveProvider.Builder().build();
+
+  /**
+   * Builder for {@link DexArchiveProvider}.
+   */
+  public static class Builder {
+
+    private final BiMap<Artifact, Artifact> dexArchives = HashBiMap.create();
+
+    public Builder() {
+    }
+
+    /**
+     * Adds all dex archives from the given providers, which is useful to aggregate providers from
+     * dependencies.
+     */
+    public Builder addTransitiveProviders(Iterable<DexArchiveProvider> providers) {
+      for (DexArchiveProvider provider : providers) {
+        dexArchives.putAll(provider.dexArchives);
+      }
+      return this;
+    }
+
+    /**
+     * Adds the given dex archive as a replacement for the given Jar.
+     */
+    public Builder addDexArchive(Artifact dexArchive, Artifact dexedJar) {
+      checkArgument(dexArchive.getFilename().endsWith(".dex.zip"),
+          "Doesn't look like a dex archive: %s", dexArchive);
+      // Adding this artifact will fail iff dexArchive already appears as the value of another jar.
+      // It's ok and expected to put the same pair multiple times. Note that ImmutableBiMap fails
+      // in that situation, which is why we're not using it here.
+      // It's weird to put a dexedJar that's already in the map with a different value so we fail.
+      Artifact old = dexArchives.put(checkNotNull(dexedJar, "dexedJar"), dexArchive);
+      checkArgument(old == null || old.equals(dexedJar),
+          "We already had mapping %s-%s, so we don't also need %s", dexedJar, old, dexArchive);
+      return this;
+    }
+
+    /**
+     * Returns the finished {@link DexArchiveProvider}.
+     */
+    public DexArchiveProvider build() {
+      return new DexArchiveProvider(ImmutableMap.copyOf(dexArchives));
+    }
+  }
+
+  /** Map from Jar artifacts to the corresponding dex archives. */
+  private final ImmutableMap<Artifact, Artifact> dexArchives;
+
+  private DexArchiveProvider(ImmutableMap<Artifact, Artifact> dexArchives) {
+    this.dexArchives = dexArchives;
+  }
+
+  /** Maps Jars to available dex archives and returns the given Jar otherwise. */
+  @Override
+  @Nullable
+  public Artifact apply(@Nullable Artifact jar) {
+    Artifact dexArchive = dexArchives.get(jar);
+    return dexArchive != null ? dexArchive : jar; // return null iff input == null
+  }
+
+  @Override
+  public int hashCode() {
+    return dexArchives.hashCode();
+  }
+
+  @Override
+  public boolean equals(Object obj) {
+    if (this == obj) {
+      return true;
+    }
+    if (obj == null) {
+      return false;
+    }
+    if (getClass() != obj.getClass()) {
+      return false;
+    }
+    DexArchiveProvider other = (DexArchiveProvider) obj;
+    return dexArchives.equals(other.dexArchives);
+  }
+}