Skip to content

Commit 7ccc661

Browse files
ShreeM01EdSchouten
ShreeM01
and
EdSchouten
authored
[6.0.0] Emit Tree objects in topological order (bazelbuild#16904)
* Emit Tree objects in topological order remote-apis PR 230 added a way where producers of Tree messages can indicate that the directories contained within are stored in topological order. The advantage of using such an ordering is that it permits instantiation of such objects onto a local file system in a streaming fashion. The same holds for lookups of individual paths. Even though Bazel currently does not gain from this, this change at least modifies Bazel's REv2 client to emit topologically sorted trees. This makes it possible for tools such as Buildbarn's bb-browser to process them more efficiently. More details: - bazelbuild/remote-apis#229 - bazelbuild/remote-apis#230 Closes bazelbuild#16463. PiperOrigin-RevId: 487196375 Change-Id: Iafcfd617fc101fec7bfa943552113ce57ab8041b * Emit Tree objects in topological order remote-apis PR 230 added a way where producers of Tree messages can indicate that the directories contained within are stored in topological order. The advantage of using such an ordering is that it permits instantiation of such objects onto a local file system in a streaming fashion. The same holds for lookups of individual paths. Even though Bazel currently does not gain from this, this change at least modifies Bazel's REv2 client to emit topologically sorted trees. This makes it possible for tools such as Buildbarn's bb-browser to process them more efficiently. More details: - bazelbuild/remote-apis#229 - bazelbuild/remote-apis#230 Partial commit for third_party/*, see bazelbuild#16463. Signed-off-by: Sunil Gowroji <[email protected]> Signed-off-by: Sunil Gowroji <[email protected]> Co-authored-by: Ed Schouten <[email protected]>
1 parent f717d6a commit 7ccc661

File tree

7 files changed

+325
-44
lines changed

7 files changed

+325
-44
lines changed

‎src/main/java/com/google/devtools/build/lib/remote/UploadManifest.java‎

Lines changed: 36 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -31,6 +31,7 @@
3131
import com.google.common.annotations.VisibleForTesting;
3232
import com.google.common.base.Preconditions;
3333
import com.google.common.collect.ImmutableList;
34+
import com.google.common.collect.Lists;
3435
import com.google.devtools.build.lib.actions.ActionExecutionMetadata;
3536
import com.google.devtools.build.lib.actions.ActionUploadFinishedEvent;
3637
import com.google.devtools.build.lib.actions.ActionUploadStartedEvent;
@@ -54,20 +55,24 @@
5455
import com.google.devtools.build.lib.vfs.PathFragment;
5556
import com.google.devtools.build.lib.vfs.Symlinks;
5657
import com.google.protobuf.ByteString;
58+
import com.google.protobuf.CodedOutputStream;
5759
import com.google.protobuf.Timestamp;
5860
import io.reactivex.rxjava3.core.Completable;
5961
import io.reactivex.rxjava3.core.Flowable;
6062
import io.reactivex.rxjava3.core.Single;
63+
import java.io.ByteArrayOutputStream;
6164
import java.io.IOException;
6265
import java.time.Duration;
6366
import java.time.Instant;
6467
import java.util.ArrayList;
6568
import java.util.Collection;
6669
import java.util.Comparator;
6770
import java.util.HashMap;
71+
import java.util.LinkedHashSet;
6872
import java.util.List;
6973
import java.util.Map;
7074
import java.util.Optional;
75+
import java.util.Set;
7176
import java.util.stream.Collectors;
7277
import javax.annotation.Nullable;
7378

@@ -303,25 +308,43 @@ private void addFile(Digest digest, Path file) throws IOException {
303308
digestToFile.put(digest, file);
304309
}
305310

311+
// Field numbers of the 'root' and 'directory' fields in the Tree message.
312+
private static final int TREE_ROOT_FIELD_NUMBER =
313+
Tree.getDescriptor().findFieldByName("root").getNumber();
314+
private static final int TREE_CHILDREN_FIELD_NUMBER =
315+
Tree.getDescriptor().findFieldByName("children").getNumber();
316+
306317
private void addDirectory(Path dir) throws ExecException, IOException {
307-
Tree.Builder tree = Tree.newBuilder();
308-
Directory root = computeDirectory(dir, tree);
309-
tree.setRoot(root);
318+
Set<ByteString> directories = new LinkedHashSet<>();
319+
var ignored = computeDirectory(dir, directories);
320+
321+
// Convert individual Directory messages to a Tree message. As we want the
322+
// records to be topologically sorted (parents before children), we iterate
323+
// over the directories in reverse insertion order.
324+
ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream();
325+
CodedOutputStream codedOutputStream = CodedOutputStream.newInstance(byteArrayOutputStream);
326+
int fieldNumber = TREE_ROOT_FIELD_NUMBER;
327+
for (ByteString directory : Lists.reverse(new ArrayList<ByteString>(directories))) {
328+
codedOutputStream.writeBytes(fieldNumber, directory);
329+
fieldNumber = TREE_CHILDREN_FIELD_NUMBER;
330+
}
331+
codedOutputStream.flush();
310332

311-
ByteString data = tree.build().toByteString();
333+
ByteString data = ByteString.copyFrom(byteArrayOutputStream.toByteArray());
312334
Digest digest = digestUtil.compute(data.toByteArray());
313335

314336
if (result != null) {
315337
result
316338
.addOutputDirectoriesBuilder()
317339
.setPath(remotePathResolver.localPathToOutputPath(dir))
318-
.setTreeDigest(digest);
340+
.setTreeDigest(digest)
341+
.setIsTopologicallySorted(true);
319342
}
320343

321344
digestToBlobs.put(digest, data);
322345
}
323346

324-
private Directory computeDirectory(Path path, Tree.Builder tree)
347+
private ByteString computeDirectory(Path path, Set<ByteString> directories)
325348
throws ExecException, IOException {
326349
Directory.Builder b = Directory.newBuilder();
327350

@@ -332,9 +355,8 @@ private Directory computeDirectory(Path path, Tree.Builder tree)
332355
String name = dirent.getName();
333356
Path child = path.getRelative(name);
334357
if (dirent.getType() == Dirent.Type.DIRECTORY) {
335-
Directory dir = computeDirectory(child, tree);
336-
b.addDirectoriesBuilder().setName(name).setDigest(digestUtil.compute(dir));
337-
tree.addChildren(dir);
358+
ByteString dir = computeDirectory(child, directories);
359+
b.addDirectoriesBuilder().setName(name).setDigest(digestUtil.compute(dir.toByteArray()));
338360
} else if (dirent.getType() == Dirent.Type.SYMLINK) {
339361
PathFragment target = child.readSymbolicLink();
340362
if (!followSymlinks && !target.isAbsolute()) {
@@ -353,9 +375,8 @@ private Directory computeDirectory(Path path, Tree.Builder tree)
353375
b.addFilesBuilder().setName(name).setDigest(digest).setIsExecutable(child.isExecutable());
354376
digestToFile.put(digest, child);
355377
} else if (statFollow.isDirectory()) {
356-
Directory dir = computeDirectory(child, tree);
357-
b.addDirectoriesBuilder().setName(name).setDigest(digestUtil.compute(dir));
358-
tree.addChildren(dir);
378+
ByteString dir = computeDirectory(child, directories);
379+
b.addDirectoriesBuilder().setName(name).setDigest(digestUtil.compute(dir.toByteArray()));
359380
} else {
360381
illegalOutput(child);
361382
}
@@ -368,7 +389,9 @@ private Directory computeDirectory(Path path, Tree.Builder tree)
368389
}
369390
}
370391

371-
return b.build();
392+
ByteString directory = b.build().toByteString();
393+
directories.add(directory);
394+
return directory;
372395
}
373396

374397
private void illegalOutput(Path path) throws ExecException {

‎src/test/java/com/google/devtools/build/lib/remote/GrpcCacheClientTest.java‎

Lines changed: 15 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -369,7 +369,11 @@ public void updateActionResult(
369369
.setPath("a/foo")
370370
.setDigest(fooDigest)
371371
.setIsExecutable(true);
372-
expectedResult.addOutputDirectoriesBuilder().setPath("bar").setTreeDigest(barDigest);
372+
expectedResult
373+
.addOutputDirectoriesBuilder()
374+
.setPath("bar")
375+
.setTreeDigest(barDigest)
376+
.setIsTopologicallySorted(true);
373377
assertThat(result).isEqualTo(expectedResult.build());
374378
}
375379

@@ -409,7 +413,11 @@ public void updateActionResult(
409413

410414
ActionResult result = uploadDirectory(remoteCache, ImmutableList.<Path>of(barDir));
411415
ActionResult.Builder expectedResult = ActionResult.newBuilder();
412-
expectedResult.addOutputDirectoriesBuilder().setPath("bar").setTreeDigest(barDigest);
416+
expectedResult
417+
.addOutputDirectoriesBuilder()
418+
.setPath("bar")
419+
.setTreeDigest(barDigest)
420+
.setIsTopologicallySorted(true);
413421
assertThat(result).isEqualTo(expectedResult.build());
414422
}
415423

@@ -472,7 +480,11 @@ public void updateActionResult(
472480

473481
ActionResult result = uploadDirectory(remoteCache, ImmutableList.of(barDir));
474482
ActionResult.Builder expectedResult = ActionResult.newBuilder();
475-
expectedResult.addOutputDirectoriesBuilder().setPath("bar").setTreeDigest(barDigest);
483+
expectedResult
484+
.addOutputDirectoriesBuilder()
485+
.setPath("bar")
486+
.setTreeDigest(barDigest)
487+
.setIsTopologicallySorted(true);
476488
assertThat(result).isEqualTo(expectedResult.build());
477489
}
478490

‎src/test/java/com/google/devtools/build/lib/remote/RemoteExecutionServiceTest.java‎

Lines changed: 15 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1314,7 +1314,11 @@ public void uploadOutputs_uploadDirectory_works() throws Exception {
13141314
.setPath("outputs/a/foo")
13151315
.setDigest(fooDigest)
13161316
.setIsExecutable(true);
1317-
expectedResult.addOutputDirectoriesBuilder().setPath("outputs/bar").setTreeDigest(barDigest);
1317+
expectedResult
1318+
.addOutputDirectoriesBuilder()
1319+
.setPath("outputs/bar")
1320+
.setTreeDigest(barDigest)
1321+
.setIsTopologicallySorted(true);
13181322
assertThat(manifest.getActionResult()).isEqualTo(expectedResult.build());
13191323

13201324
ImmutableList<Digest> toQuery = ImmutableList.of(fooDigest, quxDigest, barDigest);
@@ -1352,7 +1356,11 @@ public void uploadOutputs_uploadEmptyDirectory_works() throws Exception {
13521356

13531357
// assert
13541358
ActionResult.Builder expectedResult = ActionResult.newBuilder();
1355-
expectedResult.addOutputDirectoriesBuilder().setPath("outputs/bar").setTreeDigest(barDigest);
1359+
expectedResult
1360+
.addOutputDirectoriesBuilder()
1361+
.setPath("outputs/bar")
1362+
.setTreeDigest(barDigest)
1363+
.setIsTopologicallySorted(true);
13561364
assertThat(manifest.getActionResult()).isEqualTo(expectedResult.build());
13571365
assertThat(
13581366
getFromFuture(
@@ -1417,7 +1425,11 @@ public void uploadOutputs_uploadNestedDirectory_works() throws Exception {
14171425

14181426
// assert
14191427
ActionResult.Builder expectedResult = ActionResult.newBuilder();
1420-
expectedResult.addOutputDirectoriesBuilder().setPath("outputs/bar").setTreeDigest(barDigest);
1428+
expectedResult
1429+
.addOutputDirectoriesBuilder()
1430+
.setPath("outputs/bar")
1431+
.setTreeDigest(barDigest)
1432+
.setIsTopologicallySorted(true);
14211433
assertThat(manifest.getActionResult()).isEqualTo(expectedResult.build());
14221434

14231435
ImmutableList<Digest> toQuery = ImmutableList.of(wobbleDigest, quxDigest, barDigest);

0 commit comments

Comments
 (0)