Logical roll-forward of https://github.com/bazelbuild/bazel/commit/32a97a653735cf7c9eff5abdf0f7632f9a6525e2 (order tree artifacts).
Fixes #5686.

Should give us deterministic action keys for action template expansions.

RELNOTES: Makes TreeArtifact deterministic.
PiperOrigin-RevId: 239311465

src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java

diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java
index ab82a31..c5f15b2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java
@@ -13,13 +13,13 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
-import com.google.common.base.Function;
+import static com.google.common.collect.ImmutableSet.toImmutableSet;
+
 import com.google.common.base.MoreObjects;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Iterables;
+import com.google.common.collect.ImmutableSortedMap;
 import com.google.common.collect.Maps;
-import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.actions.FileArtifactValue;
 import com.google.devtools.build.lib.actions.cache.DigestUtils;
@@ -45,22 +45,16 @@
  */
 @AutoCodec
 public class TreeArtifactValue implements SkyValue {
-  private static final Function<Artifact, PathFragment> PARENT_RELATIVE_PATHS =
-      new Function<Artifact, PathFragment>() {
-        @Override
-        public PathFragment apply(Artifact artifact) {
-            return artifact.getParentRelativePath();
-        }
-      };
 
   private final byte[] digest;
-  private final Map<TreeFileArtifact, FileArtifactValue> childData;
+  private final ImmutableSortedMap<TreeFileArtifact, FileArtifactValue> childData;
   private BigInteger valueFingerprint;
 
   @AutoCodec.VisibleForSerialization
-  TreeArtifactValue(byte[] digest, Map<TreeFileArtifact, FileArtifactValue> childData) {
+  TreeArtifactValue(
+      byte[] digest, ImmutableSortedMap<TreeFileArtifact, FileArtifactValue> childData) {
     this.digest = digest;
-    this.childData = ImmutableMap.copyOf(childData);
+    this.childData = childData;
   }
 
   /**
@@ -76,7 +70,7 @@
 
     return new TreeArtifactValue(
         DigestUtils.fromMetadata(digestBuilder).getDigestBytesUnsafe(),
-        ImmutableMap.copyOf(childFileValues));
+        ImmutableSortedMap.copyOf(childFileValues));
   }
 
   FileArtifactValue getSelfData() {
@@ -87,8 +81,10 @@
     return getSelfData();
   }
 
-  Set<PathFragment> getChildPaths() {
-    return ImmutableSet.copyOf(Iterables.transform(childData.keySet(), PARENT_RELATIVE_PATHS));
+  ImmutableSet<PathFragment> getChildPaths() {
+    return childData.keySet().stream()
+        .map(TreeFileArtifact::getParentRelativePath)
+        .collect(toImmutableSet());
   }
 
   @Nullable
@@ -100,7 +96,7 @@
     return childData.keySet();
   }
 
-  Map<TreeFileArtifact, FileArtifactValue> getChildValues() {
+  ImmutableMap<TreeFileArtifact, FileArtifactValue> getChildValues() {
     return childData;
   }
 
@@ -150,7 +146,7 @@
    * Java's concurrent collections disallow null members.
    */
   static final TreeArtifactValue MISSING_TREE_ARTIFACT =
-      new TreeArtifactValue(null, ImmutableMap.<TreeFileArtifact, FileArtifactValue>of()) {
+      new TreeArtifactValue(null, ImmutableSortedMap.of()) {
         @Override
         FileArtifactValue getSelfData() {
           throw new UnsupportedOperationException();
@@ -162,7 +158,7 @@
         }
 
         @Override
-        Map<TreeFileArtifact, FileArtifactValue> getChildValues() {
+        ImmutableMap<TreeFileArtifact, FileArtifactValue> getChildValues() {
           throw new UnsupportedOperationException();
         }
 
@@ -172,7 +168,7 @@
         }
 
         @Override
-        Set<PathFragment> getChildPaths() {
+        ImmutableSet<PathFragment> getChildPaths() {
           throw new UnsupportedOperationException();
         }
 

src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java

diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
index 04b3211..4a6261f 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
@@ -56,9 +56,14 @@
 import com.google.devtools.build.skyframe.SkyValue;
 import java.io.IOException;
 import java.util.Arrays;
+import java.util.Collections;
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.Random;
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
 import org.junit.Before;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -126,6 +131,24 @@
   }
 
   @Test
+  public void testTreeArtifactOrdering() throws Exception {
+    int rangeSize = 100;
+    int attempts = 10;
+    List<PathFragment> children =
+        IntStream.range(0, rangeSize)
+            .mapToObj(i -> PathFragment.create("file" + i))
+            .collect(Collectors.toList());
+
+    for (int i = 0; i < attempts; i++) {
+      Collections.shuffle(children, new Random());
+      Artifact treeArtifact = createTreeArtifact("out");
+      TreeArtifactValue value = evaluateTreeArtifact(treeArtifact, children);
+      assertThat(value.getChildPaths()).containsExactlyElementsIn(children);
+      assertThat(value.getChildPaths()).isOrdered(Comparator.naturalOrder());
+    }
+  }
+
+  @Test
   public void testEqualTreeArtifacts() throws Exception {
     Artifact treeArtifact = createTreeArtifact("out");
     ImmutableList<PathFragment> children =