diff --git a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
index e7cc0e6..9d1c291 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
@@ -21,6 +21,7 @@
 import com.google.common.base.Predicate;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
+import com.google.common.collect.Ordering;
 import com.google.devtools.build.lib.actions.Action.MiddlemanType;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
@@ -797,6 +798,15 @@
     return ImmutableList.copyOf(Iterables.transform(artifacts, EXEC_PATH_FORMATTER));
   }
 
+  /**
+   * Returns the exec paths of the input artifacts in alphabetical order.
+   */
+  public static ImmutableList<PathFragment> asSortedPathFragments(Iterable<Artifact> input) {
+    return Ordering.natural().immutableSortedCopy(Iterables.transform(
+        input, EXEC_PATH_FORMATTER));
+  }
+
+
   static final ArtifactOwner DESERIALIZED_MARKER_OWNER = new ArtifactOwner() {
     @Override
     public Label getLabel() {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
index 868332c..9a7c4a2 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
@@ -1107,6 +1107,7 @@
     f.addPaths(context.getDeclaredIncludeWarnDirs());
     f.addPaths(getDeclaredIncludeSrcsInStableOrder());
     f.addPaths(getExtraSystemIncludePrefixes());
+    f.addPaths(Artifact.asSortedPathFragments(getMandatoryInputs()));
     return f.hexDigestAndReset();
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/actions/util/TestAction.java b/src/test/java/com/google/devtools/build/lib/actions/util/TestAction.java
index 1877b72..cec7df7 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/util/TestAction.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/util/TestAction.java
@@ -22,8 +22,8 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Executor;
 import com.google.devtools.build.lib.actions.ResourceSet;
+import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.util.Preconditions;
-import com.google.devtools.build.lib.util.StringUtilities;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 
 import java.io.IOException;
@@ -129,12 +129,10 @@
 
   @Override
   protected String computeKey() {
-    List<String> outputsList = new ArrayList<>();
-    for (Artifact output : getOutputs()) {
-      outputsList.add(output.getPath().getPathString());
-    }
-    // This could use a functional iterable and avoid creating a list
-    return "test " + StringUtilities.combineKeys(outputsList);
+    Fingerprint f = new Fingerprint();
+    f.addPaths(Artifact.asSortedPathFragments(getOutputs()));
+    f.addPaths(Artifact.asSortedPathFragments(getMandatoryInputs()));
+    return f.hexDigestAndReset();
   }
 
   @Override