diff --git a/src/main/java/com/google/devtools/build/lib/analysis/PseudoAction.java b/src/main/java/com/google/devtools/build/lib/analysis/PseudoAction.java
index 00d43a3..2ac3bcc 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/PseudoAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/PseudoAction.java
@@ -22,6 +22,7 @@
 import com.google.devtools.build.lib.actions.Executor;
 import com.google.devtools.build.lib.actions.ResourceSet;
 import com.google.devtools.build.lib.actions.extra.ExtraActionInfo;
+import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.protobuf.GeneratedMessage.GeneratedExtension;
 import com.google.protobuf.MessageLite;
@@ -41,7 +42,7 @@
   private final InfoType info;
 
   public PseudoAction(UUID uuid, ActionOwner owner,
-      Collection<Artifact> inputs, Collection<Artifact> outputs,
+      NestedSet<Artifact> inputs, Collection<Artifact> outputs,
       String mnemonic,
       GeneratedExtension<ExtraActionInfo, InfoType> infoExtension, InfoType info) {
     super(owner, inputs, outputs);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/python/PyCommon.java b/src/main/java/com/google/devtools/build/lib/rules/python/PyCommon.java
index 73deb83..33f6755 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/python/PyCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/python/PyCommon.java
@@ -33,6 +33,7 @@
 import com.google.devtools.build.lib.analysis.Util;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.Type;
 import com.google.devtools.build.lib.rules.cpp.CppFileTypes;
@@ -220,7 +221,7 @@
 
     ruleContext.getAnalysisEnvironment()
         .registerAction(new PyPseudoAction(ruleContext.getActionOwner(),
-            ImmutableList.copyOf(Iterables.concat(sources, dependencies)),
+            NestedSetBuilder.wrap(Order.STABLE_ORDER, Iterables.concat(sources, dependencies)),
             ImmutableList.of(PseudoAction.getDummyOutput(ruleContext)), "Python",
             PythonInfo.pythonInfo, info));
   }
@@ -391,7 +392,7 @@
     private static final UUID ACTION_UUID = UUID.fromString("8d720129-bc1a-481f-8c4c-dbe11dcef319");
 
     public PyPseudoAction(ActionOwner owner,
-        Collection<Artifact> inputs, Collection<Artifact> outputs,
+        NestedSet<Artifact> inputs, Collection<Artifact> outputs,
         String mnemonic, GeneratedExtension<ExtraActionInfo, PythonInfo> infoExtension,
         PythonInfo info) {
       super(ACTION_UUID, owner, inputs, outputs, mnemonic, infoExtension, info);