diff --git a/src/com/facebook/buck/android/AndroidBinaryRule.java b/src/com/facebook/buck/android/AndroidBinaryRule.java
index 401dc5c..d99c4dd 100644
--- a/src/com/facebook/buck/android/AndroidBinaryRule.java
+++ b/src/com/facebook/buck/android/AndroidBinaryRule.java
@@ -1352,13 +1352,13 @@
             (AccumulateClassNames) accumulateClassNamesRule.getBuildable();
 
         // Create the PreDex and add it to both the ruleResolver and preDexDeps.
-        DexProducedFromJavaLibraryThatContainsClassFiles.Builder preDexBuilder =
-            DexProducedFromJavaLibraryThatContainsClassFiles.newPreDexBuilder(
+        IntermediateDexRule.Builder preDexBuilder =
+            IntermediateDexRule.newPreDexBuilder(
                 new DefaultBuildRuleBuilderParams(
                     pathRelativizer,
                     ruleKeyBuilderFactory));
         preDexBuilder.setBuildTarget(preDexTarget);
-        preDexBuilder.setPathToClassNamesList(accumulateClassNames);
+        preDexBuilder.setAccumulateClassNamesDep(accumulateClassNames);
         preDexBuilder.addDep(accumulateClassNamesBuildTarget);
         preDexBuilder.addVisibilityPattern(BuildTargetPattern.MATCH_ALL);
         BuildRule preDex = ruleResolver.buildAndAddToIndex(preDexBuilder);
diff --git a/src/com/facebook/buck/android/BUCK b/src/com/facebook/buck/android/BUCK
index 9fb3aca..7270ae2 100644
--- a/src/com/facebook/buck/android/BUCK
+++ b/src/com/facebook/buck/android/BUCK
@@ -59,6 +59,7 @@
   'GenAidl.java',
   'GenAidlBuildRuleFactory.java',
   'HasAndroidPlatformTarget.java',
+  'IntermediateDexRule.java',
   'NativeLibraryBuildable.java',
   'NdkLibraryBuildRuleFactory.java',
   'NdkLibrary.java',
@@ -82,6 +83,7 @@
     '//src/com/facebook/buck/graph:graph',
     '//src/com/facebook/buck/java:rules',
     '//src/com/facebook/buck/java:support',
+    '//src/com/facebook/buck/java/abi:protocol',
     '//src/com/facebook/buck/model:model',
     '//src/com/facebook/buck/parser:rule_pattern',
     '//src/com/facebook/buck/rules:build_rule',
diff --git a/src/com/facebook/buck/android/DexProducedFromJavaLibraryThatContainsClassFiles.java b/src/com/facebook/buck/android/DexProducedFromJavaLibraryThatContainsClassFiles.java
index d917476..1728704 100644
--- a/src/com/facebook/buck/android/DexProducedFromJavaLibraryThatContainsClassFiles.java
+++ b/src/com/facebook/buck/android/DexProducedFromJavaLibraryThatContainsClassFiles.java
@@ -19,14 +19,12 @@
 import com.facebook.buck.java.AccumulateClassNames;
 import com.facebook.buck.java.JavaLibraryRule;
 import com.facebook.buck.model.BuildTarget;
-import com.facebook.buck.rules.AbstractBuildRuleBuilderParams;
+import com.facebook.buck.rules.AbiRule;
 import com.facebook.buck.rules.AbstractBuildable;
 import com.facebook.buck.rules.BuildContext;
-import com.facebook.buck.rules.BuildRuleParams;
-import com.facebook.buck.rules.BuildRuleResolver;
-import com.facebook.buck.rules.BuildRuleType;
 import com.facebook.buck.rules.Buildable;
 import com.facebook.buck.rules.BuildableContext;
+import com.facebook.buck.rules.Sha1HashCode;
 import com.facebook.buck.step.AbstractExecutionStep;
 import com.facebook.buck.step.ExecutionContext;
 import com.facebook.buck.step.Step;
@@ -36,6 +34,8 @@
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSortedMap;
+import com.google.common.hash.HashCode;
 
 import java.io.IOException;
 import java.nio.file.Path;
@@ -87,7 +87,9 @@
     // Make sure that the buck-out/gen/ directory exists for this.buildTarget.
     steps.add(new MkdirStep(getPathToDex().getParent()));
 
-    if (!javaLibraryWithClassesList.getClassNames().isEmpty()) {
+    // If there are classes, run dx.
+    final boolean hasClassesToDx = !javaLibraryWithClassesList.getClassNames().isEmpty();
+    if (hasClassesToDx) {
       // To be conservative, use --force-jumbo for these intermediate .dex files so that they can be
       // merged into a final classes.dex that uses jumbo instructions.
       JavaLibraryRule javaLibraryRuleToDex = javaLibraryWithClassesList.getJavaLibraryRule();
@@ -95,17 +97,30 @@
           Collections.singleton(Paths.get(javaLibraryRuleToDex.getPathToOutputFile())),
           EnumSet.of(DxStep.Option.NO_OPTIMIZE, DxStep.Option.FORCE_JUMBO));
       steps.add(dx);
-
-      AbstractExecutionStep recordArtifactStep = new AbstractExecutionStep("record_dx_success") {
-        @Override
-        public int execute(ExecutionContext context) {
-          buildableContext.recordArtifact(getPathToDex().getFileName());
-          return 0;
-        }
-      };
-      steps.add(recordArtifactStep);
     }
 
+    // Run a step to record artifacts and metadata. The values recorded depend upon whether dx was
+    // run.
+    String stepName = hasClassesToDx ? "record_dx_success" : "record_empty_dx";
+    AbstractExecutionStep recordArtifactAndMetadataStep = new AbstractExecutionStep(stepName) {
+      @Override
+      public int execute(ExecutionContext context) {
+        if (hasClassesToDx) {
+          buildableContext.recordArtifact(getPathToDex().getFileName());
+        }
+
+        // The ABI key for the deps is also the ABI key for this Buildable. A dx-merge step can keep
+        // track of the ABIs of the DexProducedFromJavaLibraryThatContainsClassFiles that it has
+        // dexed before so it knows whether it needs to re-dex them. This way, adding a comment to a
+        // Java file that triggers a recompile will not trigger a dx or a dx-merge.
+        String abiKeyHash = getAbiKeyForDeps().getHash();
+        buildableContext.addMetadata(AbiRule.ABI_KEY_FOR_DEPS_ON_DISK_METADATA, abiKeyHash);
+        buildableContext.addMetadata(AbiRule.ABI_KEY_ON_DISK_METADATA, abiKeyHash);
+        return 0;
+      }
+    };
+    steps.add(recordArtifactAndMetadataStep);
+
     return steps.build();
   }
 
@@ -124,38 +139,17 @@
   }
 
   public boolean hasOutput() {
+    return !getClassNames().isEmpty();
+  }
+
+  private ImmutableSortedMap<String, HashCode> getClassNames() {
     // TODO(mbolin): Assert that this Buildable has been built. Currently, there is no way to do
     // that from a Buildable (but there is from an AbstractCachingBuildRule).
-    return !javaLibraryWithClassesList.getClassNames().isEmpty();
+    return javaLibraryWithClassesList.getClassNames();
   }
 
-  public static Builder newPreDexBuilder(AbstractBuildRuleBuilderParams params) {
-    return new Builder(params);
+  Sha1HashCode getAbiKeyForDeps() {
+    return javaLibraryWithClassesList.getAbiKey();
   }
 
-  public static class Builder extends AbstractBuildable.Builder {
-
-    private AccumulateClassNames javaLibraryWithClassesList;
-
-    private Builder(AbstractBuildRuleBuilderParams params) {
-      super(params);
-    }
-
-    @Override
-    protected BuildRuleType getType() {
-      return BuildRuleType._PRE_DEX;
-    }
-
-    @Override
-    protected DexProducedFromJavaLibraryThatContainsClassFiles newBuildable(
-        BuildRuleParams params, BuildRuleResolver resolver) {
-      return new DexProducedFromJavaLibraryThatContainsClassFiles(params.getBuildTarget(),
-          javaLibraryWithClassesList);
-    }
-
-    public Builder setPathToClassNamesList(AccumulateClassNames javaLibraryWithClassesList) {
-      this.javaLibraryWithClassesList = javaLibraryWithClassesList;
-      return this;
-    }
-  }
 }
diff --git a/src/com/facebook/buck/android/IntermediateDexRule.java b/src/com/facebook/buck/android/IntermediateDexRule.java
new file mode 100644
index 0000000..8d5b301
--- /dev/null
+++ b/src/com/facebook/buck/android/IntermediateDexRule.java
@@ -0,0 +1,86 @@
+/*
+ * Copyright 2013-present Facebook, Inc.
+ *
+ * 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.facebook.buck.android;
+
+import com.facebook.buck.java.AccumulateClassNames;
+import com.facebook.buck.rules.AbiRule;
+import com.facebook.buck.rules.AbstractBuildRuleBuilder;
+import com.facebook.buck.rules.AbstractBuildRuleBuilderParams;
+import com.facebook.buck.rules.AbstractCachingBuildRule;
+import com.facebook.buck.rules.BuildRuleParams;
+import com.facebook.buck.rules.BuildRuleResolver;
+import com.facebook.buck.rules.BuildRuleType;
+import com.facebook.buck.rules.Buildable;
+import com.facebook.buck.rules.Sha1HashCode;
+import com.google.common.base.Preconditions;
+
+public class IntermediateDexRule extends AbstractCachingBuildRule implements AbiRule {
+
+  private final DexProducedFromJavaLibraryThatContainsClassFiles buildable;
+
+  IntermediateDexRule(DexProducedFromJavaLibraryThatContainsClassFiles buildable,
+      BuildRuleParams params) {
+    super(buildable, params);
+    this.buildable = Preconditions.checkNotNull(buildable);
+  }
+
+  @Override
+  public Buildable getBuildable() {
+    return buildable;
+  }
+
+  @Override
+  public BuildRuleType getType() {
+    return BuildRuleType._PRE_DEX;
+  }
+
+  /**
+   * The ABI key for the deps of this rule should be a hash of the classes.txt file produced by
+   * {@link AccumulateClassNames}.
+   */
+  @Override
+  public Sha1HashCode getAbiKeyForDeps() {
+    return buildable.getAbiKeyForDeps();
+  }
+
+  public static Builder newPreDexBuilder(AbstractBuildRuleBuilderParams params) {
+    return new Builder(params);
+  }
+
+  public static class Builder extends AbstractBuildRuleBuilder<IntermediateDexRule> {
+
+    private AccumulateClassNames javaLibraryWithClassesList;
+
+    protected Builder(AbstractBuildRuleBuilderParams params) {
+      super(params);
+    }
+
+    @Override
+    public IntermediateDexRule build(BuildRuleResolver ruleResolver) {
+      DexProducedFromJavaLibraryThatContainsClassFiles buildable =
+          new DexProducedFromJavaLibraryThatContainsClassFiles(getBuildTarget(),
+              javaLibraryWithClassesList);
+      return new IntermediateDexRule(buildable,
+          createBuildRuleParams(ruleResolver));
+    }
+
+    public Builder setAccumulateClassNamesDep(AccumulateClassNames javaLibraryWithClassesList) {
+      this.javaLibraryWithClassesList = javaLibraryWithClassesList;
+      return this;
+    }
+  }
+}
diff --git a/src/com/facebook/buck/java/AccumulateClassNames.java b/src/com/facebook/buck/java/AccumulateClassNames.java
index 142bfad..a0069cc 100644
--- a/src/com/facebook/buck/java/AccumulateClassNames.java
+++ b/src/com/facebook/buck/java/AccumulateClassNames.java
@@ -17,6 +17,7 @@
 package com.facebook.buck.java;
 
 import com.facebook.buck.model.BuildTarget;
+import com.facebook.buck.rules.AbiRule;
 import com.facebook.buck.rules.AbstractBuildRuleBuilderParams;
 import com.facebook.buck.rules.AbstractBuildable;
 import com.facebook.buck.rules.BuildContext;
@@ -26,6 +27,9 @@
 import com.facebook.buck.rules.Buildable;
 import com.facebook.buck.rules.BuildableContext;
 import com.facebook.buck.rules.OnDiskBuildInfo;
+import com.facebook.buck.rules.Sha1HashCode;
+import com.facebook.buck.step.AbstractExecutionStep;
+import com.facebook.buck.step.ExecutionContext;
 import com.facebook.buck.step.Step;
 import com.facebook.buck.step.fs.MkdirStep;
 import com.facebook.buck.step.fs.RmStep;
@@ -39,11 +43,14 @@
 import com.google.common.collect.ImmutableSortedMap;
 import com.google.common.collect.ImmutableSortedSet;
 import com.google.common.hash.HashCode;
+import com.google.common.hash.Hasher;
+import com.google.common.hash.Hashing;
 
 import java.io.IOException;
 import java.nio.file.Path;
 import java.nio.file.Paths;
 import java.util.List;
+import java.util.Map;
 
 import javax.annotation.Nullable;
 
@@ -60,6 +67,12 @@
   private final Path pathToOutputFile;
 
   /**
+   * This is not set until this {@link Buildable} is built.
+   */
+  @Nullable
+  private Sha1HashCode abiKey;
+
+  /**
    * This will contain the classes info discovered in the course of building this {@link Buildable}.
    * This {@link Supplier} will be defined and determined after this buildable is built.
    */
@@ -93,7 +106,7 @@
   }
 
   @Override
-  public List<Step> getBuildSteps(BuildContext context, BuildableContext buildableContext)
+  public List<Step> getBuildSteps(BuildContext context, final BuildableContext buildableContext)
       throws IOException {
     ImmutableList.Builder<Step> steps = ImmutableList.builder();
 
@@ -108,20 +121,24 @@
     classNames = accumulateClassNamesStep;
     steps.add(accumulateClassNamesStep);
 
+    AbstractExecutionStep recordAbiStep = new AbstractExecutionStep("record_abi") {
+      @Override
+      public int execute(ExecutionContext context) {
+        AccumulateClassNames.this.abiKey = computeAbiKey(classNames);
+        buildableContext.addMetadata(AbiRule.ABI_KEY_ON_DISK_METADATA, abiKey.toString());
+        return 0;
+      }
+    };
+    steps.add(recordAbiStep);
+
     return steps.build();
   }
 
-  public ImmutableSortedMap<String, HashCode> getClassNames() {
-    // TODO(mbolin): Assert that this Buildable has been built. Currently, there is no way to do
-    // that from a Buildable (but there is from an AbstractCachingBuildRule).
-    Preconditions.checkNotNull(classNames);
-    return classNames.get();
-  }
-
+  /**
+   * Sets both {@link #classNames} and {@link #abiKey}.
+   */
   @Override
   protected void initializeFromDisk(OnDiskBuildInfo onDiskBuildInfo) {
-    // Assign this.classNames when instantiating this Buildable when pulled from cache.
-
     // Read the output file, which should now be in place because this rule was downloaded from
     // cache.
     List<String> lines;
@@ -141,6 +158,31 @@
       classNamesBuilder.put(key, value);
     }
     this.classNames = Suppliers.ofInstance(classNamesBuilder.build());
+    this.abiKey = onDiskBuildInfo.getHash(AbiRule.ABI_KEY_ON_DISK_METADATA).get();
+  }
+
+  public ImmutableSortedMap<String, HashCode> getClassNames() {
+    // TODO(mbolin): Assert that this Buildable has been built. Currently, there is no way to do
+    // that from a Buildable (but there is from an AbstractCachingBuildRule).
+    Preconditions.checkNotNull(classNames);
+    return classNames.get();
+  }
+
+  public Sha1HashCode getAbiKey() {
+    Preconditions.checkNotNull(abiKey);
+    return abiKey;
+  }
+
+  @VisibleForTesting
+  static Sha1HashCode computeAbiKey(Supplier<ImmutableSortedMap<String, HashCode>> classNames) {
+    Hasher hasher = Hashing.sha1().newHasher();
+    for (Map.Entry<String, HashCode> entry : classNames.get().entrySet()) {
+      hasher.putUnencodedChars(entry.getKey());
+      hasher.putByte((byte)0);
+      hasher.putUnencodedChars(entry.getValue().toString());
+      hasher.putByte((byte)0);
+    }
+    return new Sha1HashCode(hasher.hash().toString());
   }
 
   public static Builder newAccumulateClassNamesBuilder(AbstractBuildRuleBuilderParams params) {
diff --git a/src/com/facebook/buck/java/AccumulateClassNamesStep.java b/src/com/facebook/buck/java/AccumulateClassNamesStep.java
index e2e0cb5..8add939 100644
--- a/src/com/facebook/buck/java/AccumulateClassNamesStep.java
+++ b/src/com/facebook/buck/java/AccumulateClassNamesStep.java
@@ -23,6 +23,7 @@
 import com.facebook.buck.step.AbstractExecutionStep;
 import com.facebook.buck.step.ExecutionContext;
 import com.facebook.buck.step.Step;
+import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Function;
 import com.google.common.base.Preconditions;
 import com.google.common.base.Supplier;
@@ -142,4 +143,8 @@
     return classNames;
   }
 
+  @VisibleForTesting
+  void setClassNamesForTesting(ImmutableSortedMap<String, HashCode> classNames) {
+    this.classNames = classNames;
+  }
 }
diff --git a/test/com/facebook/buck/android/BUCK b/test/com/facebook/buck/android/BUCK
index 4d5fd00..4677812 100644
--- a/test/com/facebook/buck/android/BUCK
+++ b/test/com/facebook/buck/android/BUCK
@@ -18,6 +18,7 @@
     '//src/com/facebook/buck/graph:graph',
     '//src/com/facebook/buck/java:rules',
     '//src/com/facebook/buck/java:support',
+    '//src/com/facebook/buck/java/abi:protocol',
     '//src/com/facebook/buck/model:model',
     '//src/com/facebook/buck/parser:rule_pattern',
     '//src/com/facebook/buck/rules:build_rule',
diff --git a/test/com/facebook/buck/android/DexProducedFromJavaLibraryThatContainsClassFilesTest.java b/test/com/facebook/buck/android/DexProducedFromJavaLibraryThatContainsClassFilesTest.java
index c18b4a5..4d2f5bf 100644
--- a/test/com/facebook/buck/android/DexProducedFromJavaLibraryThatContainsClassFilesTest.java
+++ b/test/com/facebook/buck/android/DexProducedFromJavaLibraryThatContainsClassFilesTest.java
@@ -23,9 +23,12 @@
 
 import com.facebook.buck.java.AccumulateClassNames;
 import com.facebook.buck.java.JavaLibraryRule;
+import com.facebook.buck.java.abi.AbiWriterProtocol;
 import com.facebook.buck.model.BuildTarget;
+import com.facebook.buck.rules.AbiRule;
 import com.facebook.buck.rules.BuildContext;
 import com.facebook.buck.rules.BuildableContext;
+import com.facebook.buck.rules.Sha1HashCode;
 import com.facebook.buck.step.ExecutionContext;
 import com.facebook.buck.step.Step;
 import com.facebook.buck.step.TestExecutionContext;
@@ -102,6 +105,20 @@
         executionContext);
 
     verifyAll();
+    resetAll();
+
+    buildableContext.recordArtifact(Paths.get("bar.dex.jar"));
+    Sha1HashCode abiKey = new Sha1HashCode("f7f34ed13b881c6c6f663533cde4a436ea84435e");
+    expect(accumulateClassNames.getAbiKey()).andReturn(abiKey);
+    buildableContext.addMetadata(AbiRule.ABI_KEY_FOR_DEPS_ON_DISK_METADATA, abiKey.getHash());
+    buildableContext.addMetadata(AbiRule.ABI_KEY_ON_DISK_METADATA, abiKey.getHash());
+    replayAll();
+
+    Step recordArtifactAndMetadataStep = steps.get(3);
+    int exitCode = recordArtifactAndMetadataStep.execute(executionContext);
+    assertEquals(0, exitCode);
+
+    verifyAll();
   }
 
   @Test
@@ -138,11 +155,25 @@
     MoreAsserts.assertSteps("Do not generate a .dex.jar file.",
         ImmutableList.of(
           "rm -f /home/user/buck-out/gen/foo/bar.dex.jar",
-          "mkdir -p /home/user/buck-out/gen/foo"),
+          "mkdir -p /home/user/buck-out/gen/foo",
+          "record_empty_dx"),
         steps,
         executionContext);
 
     verifyAll();
+    resetAll();
+
+    Sha1HashCode abiKey = new Sha1HashCode(AbiWriterProtocol.EMPTY_ABI_KEY);
+    expect(accumulateClassNames.getAbiKey()).andReturn(abiKey);
+    buildableContext.addMetadata(AbiRule.ABI_KEY_FOR_DEPS_ON_DISK_METADATA, abiKey.getHash());
+    buildableContext.addMetadata(AbiRule.ABI_KEY_ON_DISK_METADATA, abiKey.getHash());
+    replayAll();
+
+    Step recordArtifactAndMetadataStep = steps.get(2);
+    int exitCode = recordArtifactAndMetadataStep.execute(executionContext);
+    assertEquals(0, exitCode);
+
+    verifyAll();
   }
 
   @Test
diff --git a/test/com/facebook/buck/java/AccumulateClassNamesTest.java b/test/com/facebook/buck/java/AccumulateClassNamesTest.java
index d9987a6..9c1dbcf 100644
--- a/test/com/facebook/buck/java/AccumulateClassNamesTest.java
+++ b/test/com/facebook/buck/java/AccumulateClassNamesTest.java
@@ -20,7 +20,9 @@
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertNotNull;
 
+import com.facebook.buck.java.abi.AbiWriterProtocol;
 import com.facebook.buck.model.BuildTarget;
+import com.facebook.buck.rules.AbiRule;
 import com.facebook.buck.rules.AbstractBuildRuleBuilderParams;
 import com.facebook.buck.rules.BuildContext;
 import com.facebook.buck.rules.BuildRule;
@@ -29,15 +31,19 @@
 import com.facebook.buck.rules.BuildableContext;
 import com.facebook.buck.rules.FakeAbstractBuildRuleBuilderParams;
 import com.facebook.buck.rules.OnDiskBuildInfo;
+import com.facebook.buck.rules.Sha1HashCode;
 import com.facebook.buck.step.ExecutionContext;
 import com.facebook.buck.step.Step;
 import com.facebook.buck.step.TestExecutionContext;
 import com.facebook.buck.testutil.MoreAsserts;
 import com.facebook.buck.util.ProjectFilesystem;
+import com.google.common.base.Optional;
+import com.google.common.base.Suppliers;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSortedMap;
 import com.google.common.collect.ImmutableSortedSet;
 import com.google.common.hash.HashCode;
+import com.google.common.hash.Hashing;
 
 import org.easymock.EasyMockSupport;
 import org.junit.Test;
@@ -65,7 +71,6 @@
         params);
     assertEquals(BuildRuleType._CLASS_NAMES, builder.getType());
 
-
     // Construct the Buildable.
     BuildTarget buildTarget = new BuildTarget("//foo/bar", "baz", "class_names");
     builder.setBuildTarget(buildTarget);
@@ -104,9 +109,30 @@
         ImmutableList.of(
           "rm -f " + absolutePathToOutput,
           "mkdir -p " + absolutePathToOutput.getParent(),
-          "get_class_names foo/bar/example.jar > " + pathToOutput),
+          "get_class_names foo/bar/example.jar > " + pathToOutput,
+          "record_abi"),
         steps,
         context);
+
+    // Prepare to invoke the recordAbiStep by populating the accumulateClassNamesStep first.
+    AccumulateClassNamesStep accumulateClassNamesStep = (AccumulateClassNamesStep) steps.get(2);
+    ImmutableSortedMap<String, HashCode> classNames = ImmutableSortedMap.of();
+    accumulateClassNamesStep.setClassNamesForTesting(classNames);
+
+    resetAll();
+    String expectedAbiKey = AbiWriterProtocol.EMPTY_ABI_KEY;
+    buildableContext.addMetadata(AbiRule.ABI_KEY_ON_DISK_METADATA, expectedAbiKey);
+    replayAll();
+
+    // Invoke the recordAbiStep and ensure the correct data is recorded.
+    Step recordAbiStep = steps.get(3);
+    int exitCode = recordAbiStep.execute(context);
+    assertEquals(0, exitCode);
+    assertEquals("Should be the empty ABI key because the classNames map is empty.",
+        new Sha1HashCode(expectedAbiKey),
+        accumulateClassNames.getAbiKey());
+
+    verifyAll();
   }
 
   @Test
@@ -125,6 +151,8 @@
         "com/example/Baz 62b1c2510840c0de55c13f66065a98a719be0f19",
         "com/example/Foo e4fccb7520b7795e632651323c63217c9f59f72a");
     expect(onDiskBuildInfo.getOutputFileContentsByLine(accumulateClassNames)).andReturn(lines);
+    expect(onDiskBuildInfo.getHash(AbiRule.ABI_KEY_ON_DISK_METADATA))
+        .andReturn(Optional.of(new Sha1HashCode("f7d6d1efa11c8ceef36cc56b0ec6c3a20ddbf19f")));
 
     replayAll();
     accumulateClassNames.initializeFromDisk(onDiskBuildInfo);
@@ -139,5 +167,36 @@
           "com/example/Foo", HashCode.fromString("e4fccb7520b7795e632651323c63217c9f59f72a")
         ),
         observedClasses);
+    assertEquals(new Sha1HashCode("f7d6d1efa11c8ceef36cc56b0ec6c3a20ddbf19f"),
+        accumulateClassNames.getAbiKey());
+  }
+
+  @Test
+  public void testComputeAbiKey() {
+    ImmutableSortedMap<String, HashCode> classNamesAndHashes = ImmutableSortedMap.of(
+        "com/example/Foo", HashCode.fromString("e4fccb7520b7795e632651323c63217c9f59f72a"),
+        "com/example/Bar", HashCode.fromString("087b7707a5f8e0a2adf5652e3cd2072d89a197dc"),
+        "com/example/Baz", HashCode.fromString("62b1c2510840c0de55c13f66065a98a719be0f19")
+    );
+    String observedSha1 = AccumulateClassNames
+        .computeAbiKey(Suppliers.ofInstance(classNamesAndHashes))
+        .getHash();
+
+    String expectedSha1 = Hashing.sha1().newHasher()
+        .putUnencodedChars("com/example/Bar")
+        .putByte((byte)0)
+        .putUnencodedChars("087b7707a5f8e0a2adf5652e3cd2072d89a197dc")
+        .putByte((byte)0)
+        .putUnencodedChars("com/example/Baz")
+        .putByte((byte)0)
+        .putUnencodedChars("62b1c2510840c0de55c13f66065a98a719be0f19")
+        .putByte((byte)0)
+        .putUnencodedChars("com/example/Foo")
+        .putByte((byte)0)
+        .putUnencodedChars("e4fccb7520b7795e632651323c63217c9f59f72a")
+        .putByte((byte)0)
+        .hash()
+        .toString();
+    assertEquals(expectedSha1, observedSha1);
   }
 }