From 9498ac936e8eadebfac55d5e54a6c16852953e07 Mon Sep 17 00:00:00 2001 From: Florian Klink Date: Sat, 13 Apr 2024 23:33:18 +0300 Subject: fix(tvix/castore/directory): fix graph traversal Use a proper graph library to ensure all nodes are reachable from the root. We had a bit of that handrolled during add(), as well as later, which had an annoying bug: Redundant nodes were omitted during insert, but when returning the list during finalize, we did not properly account they need to be introduced before their parents are sent. We now simply populate a petgraph DiGraph during insert (skipping inserting nodes we already saw), and use petgraph's DfsPostOrder to traverse the graph during finalize. If the number of returned indices equals the total number of nodes in the graph, all nodes are reachable from the root, we can consume the graph and return the nodes as a vec, in the same order as the traversal (and insertion). Providing a regression test for the initial bug is challenging, as the current code uses a bunch of HashSets. I manually tested ingesting a full NixOS closure using this mechanism (via gRPC, which exposes this problem, as it validates twice), and it now works. Change-Id: Ic1d5e3e981f2993cc08c5c6b60ad895e578326dc Reviewed-on: https://cl.tvl.fyi/c/depot/+/11418 Autosubmit: flokli Reviewed-by: Connor Brewster Tested-by: BuildkiteCI --- tvix/Cargo.nix | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'tvix/Cargo.nix') diff --git a/tvix/Cargo.nix b/tvix/Cargo.nix index 48b53a1943b5..1145b8254460 100644 --- a/tvix/Cargo.nix +++ b/tvix/Cargo.nix @@ -7768,6 +7768,7 @@ rec { "serde_derive" = [ "dep:serde_derive" ]; "unstable" = [ "generate" ]; }; + resolvedDefaultFeatures = [ "default" "graphmap" "matrix_graph" "stable_graph" ]; }; "pin-project" = rec { crateName = "pin-project"; @@ -13814,6 +13815,10 @@ rec { name = "parking_lot"; packageId = "parking_lot 0.12.1"; } + { + name = "petgraph"; + packageId = "petgraph"; + } { name = "pin-project-lite"; packageId = "pin-project-lite"; -- cgit 1.4.1