Introduce the use of graph enhancement to enable pre-dexing.

Test Plan:
Sandcastle builds.
diff --git a/src/com/facebook/buck/android/AndroidBinaryRule.java b/src/com/facebook/buck/android/AndroidBinaryRule.java
index c2450b9..d75ac36 100644
--- a/src/com/facebook/buck/android/AndroidBinaryRule.java
+++ b/src/com/facebook/buck/android/AndroidBinaryRule.java
@@ -22,6 +22,7 @@
 import com.android.common.SdkConstants;
 import com.facebook.buck.android.FilterResourcesStep.ResourceFilter;
 import com.facebook.buck.dalvik.ZipSplitter;
+import com.facebook.buck.java.AccumulateClassNames;
 import com.facebook.buck.java.Classpaths;
 import com.facebook.buck.java.HasClasspathEntries;
 import com.facebook.buck.java.JavaLibraryRule;
@@ -38,11 +39,13 @@
 import com.facebook.buck.rules.Buildable;
 import com.facebook.buck.rules.BuildableContext;
 import com.facebook.buck.rules.BuildableProperties;
+import com.facebook.buck.rules.DefaultBuildRuleBuilderParams;
 import com.facebook.buck.rules.DependencyGraph;
 import com.facebook.buck.rules.DoNotUseAbstractBuildable;
 import com.facebook.buck.rules.FileSourcePath;
 import com.facebook.buck.rules.InstallableBuildRule;
 import com.facebook.buck.rules.RuleKey;
+import com.facebook.buck.rules.RuleKeyBuilderFactory;
 import com.facebook.buck.rules.SourcePath;
 import com.facebook.buck.shell.AbstractGenruleStep;
 import com.facebook.buck.shell.EchoStep;
@@ -66,6 +69,7 @@
 import com.google.common.base.Joiner;
 import com.google.common.base.Optional;
 import com.google.common.base.Preconditions;
+import com.google.common.base.Predicates;
 import com.google.common.collect.FluentIterable;
 import com.google.common.collect.ImmutableBiMap;
 import com.google.common.collect.ImmutableList;
@@ -73,6 +77,7 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.ImmutableSetMultimap;
 import com.google.common.collect.ImmutableSortedSet;
+import com.google.common.collect.Iterables;
 import com.google.common.collect.Sets;
 import com.google.common.io.Files;
 
@@ -80,10 +85,13 @@
 import java.io.IOException;
 import java.nio.file.Path;
 import java.nio.file.Paths;
+import java.util.Collections;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 
+import javax.annotation.Nullable;
+
 /**
  * <pre>
  * android_binary(
@@ -189,6 +197,7 @@
 
   private final FilterResourcesStep.ResourceFilter resourceFilter;
   private final ImmutableSet<TargetCpuType> cpuFilters;
+  private final ImmutableSet<DexProducedFromJavaLibraryThatContainsClassFiles> preDexDeps;
   private final ImmutableSortedSet<BuildRule> preprocessJavaClassesDeps;
   private final Optional<String> preprocessJavaClassesBash;
   private final AndroidTransitiveDependencyGraph transitiveDependencyGraph;
@@ -218,6 +227,7 @@
       Optional<SourcePath> primaryDexClassesFile,
       FilterResourcesStep.ResourceFilter resourceFilter,
       Set<TargetCpuType> cpuFilters,
+      Set<DexProducedFromJavaLibraryThatContainsClassFiles> preDexDeps,
       Set<BuildRule> preprocessJavaClassesDeps,
       Optional<String> preprocessJavaClassesBash) {
     super(buildRuleParams);
@@ -239,6 +249,7 @@
         getBuildTarget().getBasePathWithSlash());
     this.resourceFilter = Preconditions.checkNotNull(resourceFilter);
     this.cpuFilters = ImmutableSet.copyOf(cpuFilters);
+    this.preDexDeps = ImmutableSet.copyOf(preDexDeps);
     this.preprocessJavaClassesDeps = ImmutableSortedSet.copyOf(preprocessJavaClassesDeps);
     this.preprocessJavaClassesBash = Preconditions.checkNotNull(preprocessJavaClassesBash);
     this.transitiveDependencyGraph = new AndroidTransitiveDependencyGraph(this);
@@ -321,6 +332,10 @@
     return this.cpuFilters;
   }
 
+  public ImmutableSet<DexProducedFromJavaLibraryThatContainsClassFiles> getPreDexDeps() {
+    return preDexDeps;
+  }
+
   public ImmutableSortedSet<BuildRule> getPreprocessJavaClassesDeps() {
     return preprocessJavaClassesDeps;
   }
@@ -574,12 +589,40 @@
     final ImmutableSet.Builder<String> secondaryDexDirectories = ImmutableSet.builder();
 
     // Create dex artifacts. This may modify assetsDirectories.
-    addDexingCommands(
-        classpathEntriesToDex,
-        secondaryDexDirectories,
-        commands,
-        dexFile,
-        context.getSourcePathResolver());
+    if (preDexDeps.isEmpty()) {
+      addDexingCommands(
+          classpathEntriesToDex,
+          secondaryDexDirectories,
+          commands,
+          dexFile,
+          context.getSourcePathResolver());
+    } else {
+      Iterable<Path> filesToDex = FluentIterable.from(preDexDeps)
+          .transform(
+              new Function<DexProducedFromJavaLibraryThatContainsClassFiles, Path>() {
+                  @Override
+                  @Nullable
+                  public Path apply(DexProducedFromJavaLibraryThatContainsClassFiles preDex) {
+                    if (preDex.hasOutput()) {
+                      return preDex.getPathToDex();
+                    } else {
+                      return null;
+                    }
+                  }
+              })
+          .filter(Predicates.notNull());
+
+      // If this APK has Android resources, then the generated R.class files also need to be dexed.
+      if (dexTransitiveDependencies.pathToCompiledRDotJavaFiles.isPresent()) {
+        Path pathToCompiledRDotJavaFilesDirectory =
+            dexTransitiveDependencies.pathToCompiledRDotJavaFiles.get();
+        filesToDex = Iterables.concat(filesToDex,
+            Collections.singleton(pathToCompiledRDotJavaFilesDirectory));
+      }
+
+      // This will combine the pre-dexed files and the R.class files into a single classes.dex file.
+      commands.add(new DxStep(dexFile, filesToDex));
+    }
 
     // Copy the transitive closure of files in assets to a single directory, if any.
     final ImmutableMap<String, File> extraAssets = extraAssetsBuilder.build();
@@ -1181,16 +1224,39 @@
             rule.getType().getName());
       }
 
+      BuildRuleParams originalParams = createBuildRuleParams(ruleResolver);
+      ImmutableSortedSet<BuildRule> originalDeps = originalParams.getDeps();
+      ImmutableSet<DexProducedFromJavaLibraryThatContainsClassFiles> preDexDeps;
+      if (PackageType.DEBUG.equals(packageType)
+          && !dexSplitMode.isShouldSplitDex() // TODO(mbolin): Support predex for split dex.
+          && !preprocessJavaClassesBash.isPresent() // TODO(mbolin): Support predex post-preprocess.
+          ) {
+        preDexDeps = enhanceGraphToLeveragePreDexing(originalDeps,
+            buildRulesToExcludeFromDex,
+            ruleResolver,
+            originalParams.getPathRelativizer(),
+            originalParams.getRuleKeyBuilderFactory());
+        for (DexProducedFromJavaLibraryThatContainsClassFiles preDexDep : preDexDeps) {
+          addDep(preDexDep.getBuildTarget());
+        }
+      } else {
+        preDexDeps = ImmutableSortedSet.of();
+      }
+
       boolean allowNonExistentRule =
           false;
+
+      // Must invoke this a second time, as the preDexDeps may have been added to the builder.
+      BuildRuleParams finalParams = createBuildRuleParams(ruleResolver);
+
       return new AndroidBinaryRule(
-          createBuildRuleParams(ruleResolver),
+          finalParams,
           manifest,
           target,
           getBuildTargetsAsBuildRules(ruleResolver, classpathDeps.build()),
           (Keystore)keystore,
           packageType,
-          getBuildTargetsAsBuildRules(ruleResolver,
+          /* buildRulesToExcludeFromDex */ getBuildTargetsAsBuildRules(ruleResolver,
               buildRulesToExcludeFromDex,
               allowNonExistentRule),
           dexSplitMode,
@@ -1202,10 +1268,81 @@
           primaryDexClassesFile,
           resourceFilter,
           cpuFilters.build(),
+          preDexDeps,
           getBuildTargetsAsBuildRules(ruleResolver, preprocessJavaClassesDeps.build()),
           preprocessJavaClassesBash);
     }
 
+    /**
+     * @return The set of build rules that correspond to pre-dex'd artifacts that should be merged
+     *     to create the final classes.dex for the APK.
+     */
+    private ImmutableSet<DexProducedFromJavaLibraryThatContainsClassFiles>
+        enhanceGraphToLeveragePreDexing(
+            ImmutableSortedSet<BuildRule> originalDeps,
+            Set<BuildTarget> buildRulesToExcludeFromDex,
+            BuildRuleResolver ruleResolver,
+            Function<String, Path> pathRelativizer,
+            RuleKeyBuilderFactory ruleKeyBuilderFactory) {
+      ImmutableSet.Builder<DexProducedFromJavaLibraryThatContainsClassFiles> preDexDeps =
+          ImmutableSet.builder();
+      ImmutableSet<JavaLibraryRule> transitiveJavaDeps = Classpaths
+          .getClasspathEntries(originalDeps).keySet();
+      for (JavaLibraryRule javaLibraryRule : transitiveJavaDeps) {
+        // If the rule has no output file (which happens when a java_library has no srcs or
+        // resources, but export_deps is true), then there will not be anything to dx.
+        if (javaLibraryRule.getPathToOutputFile() == null) {
+          continue;
+        }
+
+        // If the rule is in the no_dx list, then do not pre-dex it.
+        if (buildRulesToExcludeFromDex.contains(javaLibraryRule.getBuildTarget())) {
+          continue;
+        }
+
+        // See whether the corresponding PreDex has already been added to the ruleResolver.
+        BuildTarget originalTarget = javaLibraryRule.getBuildTarget();
+        BuildTarget preDexTarget = new BuildTarget(originalTarget.getBaseName(),
+            originalTarget.getShortName(),
+            "dex");
+        BuildRule preDexRule = ruleResolver.get(preDexTarget);
+        if (preDexRule != null) {
+          preDexDeps.add(
+              (DexProducedFromJavaLibraryThatContainsClassFiles) preDexRule.getBuildable());
+          continue;
+        }
+
+        // Create a rule to get the list of the classes in the JavaLibraryRule.
+        AccumulateClassNames.Builder accumulateClassNamesBuilder = AccumulateClassNames
+            .newAccumulateClassNamesBuilder(new DefaultBuildRuleBuilderParams(
+                pathRelativizer, ruleKeyBuilderFactory));
+        BuildTarget accumulateClassNamesBuildTarget = new BuildTarget(
+            originalTarget.getBaseName(), originalTarget.getShortName(), "class_names");
+        accumulateClassNamesBuilder.setBuildTarget(accumulateClassNamesBuildTarget);
+        accumulateClassNamesBuilder.setJavaLibraryToDex(javaLibraryRule);
+        accumulateClassNamesBuilder.addDep(originalTarget);
+        accumulateClassNamesBuilder.addVisibilityPattern(BuildTargetPattern.MATCH_ALL);
+        BuildRule accumulateClassNamesRule = ruleResolver.buildAndAddToIndex(
+            accumulateClassNamesBuilder);
+        AccumulateClassNames accumulateClassNames =
+            (AccumulateClassNames) accumulateClassNamesRule.getBuildable();
+
+        // Create the PreDex and add it to both the ruleResolver and preDexDeps.
+        DexProducedFromJavaLibraryThatContainsClassFiles.Builder preDexBuilder =
+            DexProducedFromJavaLibraryThatContainsClassFiles.newPreDexBuilder(
+                new DefaultBuildRuleBuilderParams(
+                    pathRelativizer,
+                    ruleKeyBuilderFactory));
+        preDexBuilder.setBuildTarget(preDexTarget);
+        preDexBuilder.setPathToClassNamesList(accumulateClassNames);
+        preDexBuilder.addDep(accumulateClassNamesBuildTarget);
+        preDexBuilder.addVisibilityPattern(BuildTargetPattern.MATCH_ALL);
+        BuildRule preDex = ruleResolver.buildAndAddToIndex(preDexBuilder);
+        preDexDeps.add((DexProducedFromJavaLibraryThatContainsClassFiles) preDex.getBuildable());
+      }
+      return preDexDeps.build();
+    }
+
     @Override
     public Builder setBuildTarget(BuildTarget buildTarget) {
       super.setBuildTarget(buildTarget);
diff --git a/src/com/facebook/buck/android/AndroidDexTransitiveDependencies.java b/src/com/facebook/buck/android/AndroidDexTransitiveDependencies.java
index 908e741..398b4d5 100644
--- a/src/com/facebook/buck/android/AndroidDexTransitiveDependencies.java
+++ b/src/com/facebook/buck/android/AndroidDexTransitiveDependencies.java
@@ -15,8 +15,11 @@
  */
 package com.facebook.buck.android;
 
+import com.google.common.base.Optional;
+import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableSet;
 
+import java.nio.file.Path;
 import java.util.Set;
 
 /**
@@ -30,11 +33,19 @@
   public final ImmutableSet<String> noDxClasspathEntries;
   public final ImmutableSet<String> pathsToThirdPartyJars;
 
+  /**
+   * If present, identifies a directory that contains the .class files that were generated as a
+   * result of compiling R.java files.
+   */
+  public final Optional<Path> pathToCompiledRDotJavaFiles;
+
   public AndroidDexTransitiveDependencies(Set<String> pathsToDex,
                                           Set<String> pathsToThirdPartyJars,
-                                          ImmutableSet<String> noDxClasspathEntries) {
+                                          ImmutableSet<String> noDxClasspathEntries,
+                                          Optional<Path> pathToCompiledRDotJavaFiles) {
     this.classpathEntriesToDex = ImmutableSet.copyOf(pathsToDex);
     this.pathsToThirdPartyJars = ImmutableSet.copyOf(pathsToThirdPartyJars);
     this.noDxClasspathEntries = ImmutableSet.copyOf(noDxClasspathEntries);
+    this.pathToCompiledRDotJavaFiles = Preconditions.checkNotNull(pathToCompiledRDotJavaFiles);
   }
 }
diff --git a/src/com/facebook/buck/android/AndroidInstrumentationApk.java b/src/com/facebook/buck/android/AndroidInstrumentationApk.java
index ba71982..bb5bd03 100644
--- a/src/com/facebook/buck/android/AndroidInstrumentationApk.java
+++ b/src/com/facebook/buck/android/AndroidInstrumentationApk.java
@@ -83,6 +83,7 @@
         apkUnderTest.getPrimaryDexClassesFile(),
         apkUnderTest.getResourceFilter(),
         apkUnderTest.getCpuFilters(),
+        apkUnderTest.getPreDexDeps(),
         apkUnderTest.getPreprocessJavaClassesDeps(),
         apkUnderTest.getPreprocessJavaClassesBash());
     this.apkUnderTest = apkUnderTest;
diff --git a/src/com/facebook/buck/android/AndroidTransitiveDependencyGraph.java b/src/com/facebook/buck/android/AndroidTransitiveDependencyGraph.java
index f8127ab..fef9fd4 100644
--- a/src/com/facebook/buck/android/AndroidTransitiveDependencyGraph.java
+++ b/src/com/facebook/buck/android/AndroidTransitiveDependencyGraph.java
@@ -28,6 +28,7 @@
 import com.facebook.buck.rules.Buildable;
 import com.facebook.buck.rules.DependencyGraph;
 import com.facebook.buck.util.Optionals;
+import com.google.common.base.Optional;
 import com.google.common.base.Preconditions;
 import com.google.common.base.Supplier;
 import com.google.common.base.Suppliers;
@@ -36,6 +37,8 @@
 import com.google.common.collect.ImmutableSortedSet;
 import com.google.common.collect.Sets;
 
+import java.nio.file.Path;
+import java.nio.file.Paths;
 import java.util.Map;
 import java.util.Set;
 
@@ -113,8 +116,17 @@
 
     // Include the directory of compiled R.java files on the classpath.
     ImmutableSet<String> rDotJavaPackages = details.rDotJavaPackages;
+    Optional<Path> pathToCompiledRDotJavaFilesOptional;
     if (!rDotJavaPackages.isEmpty()) {
-      pathsToDexBuilder.add(UberRDotJavaUtil.getPathToCompiledRDotJavaFiles(buildTargetForTheRootOfTheTraversal));
+      String pathToCompiledRDotJavaFiles = UberRDotJavaUtil.getPathToCompiledRDotJavaFiles(
+          buildTargetForTheRootOfTheTraversal);
+      pathsToDexBuilder.add(pathToCompiledRDotJavaFiles);
+
+      // TODO: Ultimately, pathToCompiledRDotJavaFiles should be pre-dexed so that it does not need
+      // its own field in AndroidDexTransitiveDependencies.
+      pathToCompiledRDotJavaFilesOptional = Optional.of(Paths.get(pathToCompiledRDotJavaFiles));
+    } else {
+      pathToCompiledRDotJavaFilesOptional = Optional.absent();
     }
 
     ImmutableSet<String> noDxPaths = noDxPathsBuilder.build();
@@ -132,7 +144,8 @@
 
     return new AndroidDexTransitiveDependencies(classpathEntries,
         pathsToThirdPartyJars,
-        noDxPaths);
+        noDxPaths,
+        pathToCompiledRDotJavaFilesOptional);
   }
 
   public AndroidTransitiveDependencies findDependencies(
diff --git a/src/com/facebook/buck/android/DexProducedFromJavaLibraryThatContainsClassFiles.java b/src/com/facebook/buck/android/DexProducedFromJavaLibraryThatContainsClassFiles.java
index 0073cc6..e485218 100644
--- a/src/com/facebook/buck/android/DexProducedFromJavaLibraryThatContainsClassFiles.java
+++ b/src/com/facebook/buck/android/DexProducedFromJavaLibraryThatContainsClassFiles.java
@@ -86,6 +86,10 @@
     this.javaLibraryWithClassesList = Preconditions.checkNotNull(javaLibraryWithClassesList);
   }
 
+  public BuildTarget getBuildTarget() {
+    return buildTarget;
+  }
+
   @Override
   public Iterable<String> getInputsToCompareToOutput() {
     // The deps of this rule already capture all of the inputs that should affect the cache key.
diff --git a/src/com/facebook/buck/rules/DefaultBuildRuleBuilderParams.java b/src/com/facebook/buck/rules/DefaultBuildRuleBuilderParams.java
index 3d3bf6e..6d3e378 100644
--- a/src/com/facebook/buck/rules/DefaultBuildRuleBuilderParams.java
+++ b/src/com/facebook/buck/rules/DefaultBuildRuleBuilderParams.java
@@ -29,7 +29,13 @@
 
   public DefaultBuildRuleBuilderParams(ProjectFilesystem projectFilesystem,
       RuleKeyBuilderFactory ruleKeyBuilderFactory) {
-    this.pathRelativizer = Preconditions.checkNotNull(projectFilesystem).getPathRelativizer();
+    this(Preconditions.checkNotNull(projectFilesystem).getPathRelativizer(),
+        ruleKeyBuilderFactory);
+  }
+
+  public DefaultBuildRuleBuilderParams(Function<String, Path> pathRelativizer,
+      RuleKeyBuilderFactory ruleKeyBuilderFactory) {
+    this.pathRelativizer = Preconditions.checkNotNull(pathRelativizer);
     this.ruleKeyBuilderFactory = Preconditions.checkNotNull(ruleKeyBuilderFactory);
   }
 
diff --git a/test/com/facebook/buck/cli/QuickstartIntegrationTest.java b/test/com/facebook/buck/cli/QuickstartIntegrationTest.java
index 20ccd5f..2af5f72 100644
--- a/test/com/facebook/buck/cli/QuickstartIntegrationTest.java
+++ b/test/com/facebook/buck/cli/QuickstartIntegrationTest.java
@@ -100,6 +100,7 @@
         "//apps/myapp:debug_keystore",
         "//apps/myapp:project_config",
         "//java/com/example/activity:activity",
+        "//java/com/example/activity:activity#dex",
         "//java/com/example/activity:project_config",
         "//res/com/example/activity:project_config",
         "//res/com/example/activity:res") + "\n",