diff options
author | Florian Klink <flokli@flokli.de> | 2024-04-13T20·33+0300 |
---|---|---|
committer | clbot <clbot@tvl.fyi> | 2024-04-15T14·47+0000 |
commit | 9498ac936e8eadebfac55d5e54a6c16852953e07 (patch) | |
tree | a85518d190a641caef296c447ea662787c714662 /tools | |
parent | 6ebaa7b88a25636ee90f21b3a42a3674c98d00ef (diff) |
fix(tvix/castore/directory): fix graph traversal r/7928
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 <flokli@flokli.de> Reviewed-by: Connor Brewster <cbrewster@hey.com> Tested-by: BuildkiteCI
Diffstat (limited to 'tools')
0 files changed, 0 insertions, 0 deletions