Sort entries by segment when building a parent node to prevent unordered directory structures.

When building a parent node from action inputs, the paths to the files are
sorted. These paths are then broken down into segments and a tree structure
is created from the segments.

Problem is, the segments at each level of the tree structure are not sorted
before they are added to the parent node. This can result in an unordered
directory tree.

For example, the sort order of this list of files
```
/foo/bar-client/bar-client_ijar.jar
/foo/bar/bar_ijar.jar
```

is maintained when it becomes a tree structure
```
foo ->
    bar-client ->
        bar-client_ijar.jar
    bar
        bar_ijar.jar
```
which is out of order.

Resolves: #5109

Closes #5110.

PiperOrigin-RevId: 195649710

1 files changed, 5 insertions, 0 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/remote/TreeNodeRepository.java b/src/main/java/com/google/devtools/build/lib/remote/TreeNodeRepository.java
index 7767cb8c7b..5012cb74d5 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/TreeNodeRepository.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/TreeNodeRepository.java
@@ -42,6 +42,7 @@ import com.google.protobuf.ByteString;
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.Collections;
 import java.util.Comparator;
 import java.util.HashMap;
 import java.util.List;
@@ -123,6 +124,9 @@ public final class TreeNodeRepository {
       public int hashCode() {
         return Objects.hash(segment, child);
       }
+
+      public static Comparator<ChildEntry> segmentOrder =
+          Comparator.comparing(ChildEntry::getSegment);
     }
 
     // Should only be called by the TreeNodeRepository.
@@ -344,6 +348,7 @@ public final class TreeNodeRepository {
         }
       }
     }
+    Collections.sort(entries, TreeNode.ChildEntry.segmentOrder);
     return interner.intern(new TreeNode(entries, null));
   }