Struct tvix_castore::directoryservice::directory_graph::DirectoryGraph

pub struct DirectoryGraph<O> {
    graph: DiGraph<Option<Directory>, Option<EdgeWeight>>,
    digest_to_node_ix: HashMap<B3Digest, NodeIndex>,
    order_validator: O,
}

This can be used to validate and/or re-order a Directory closure (DAG of connected Directories), and their insertion order.

The DirectoryGraph is parametrized on the insertion order, and can be constructed using the Default trait, or using with_order if the OrderValidator needs to be customized.

If the user is receiving directories from canonical protobuf encoding in root-to-leaves order, and parsing them, she can call digest_allowed before parsing the protobuf record and then add it with add_unchecked. All other users insert the directories via add, in their specified order. During insertion, we validate as much as we can at that time:

• individual validation of Directory messages
• validation of insertion order
• validation of size fields of referred Directories

Internally it keeps all received Directories in a directed graph, with node weights being the Directories and edges pointing to child/parent directories.

Once all Directories have been inserted, a validate function can be called to perform a check for graph connectivity and ensure there’s no disconnected components or missing nodes. Finally, the drain_leaves_to_root or drain_root_to_leaves can be chained on validate to get an iterator over the (deduplicated and) validated list of directories in either order.

Fields

graph: DiGraph<Option<Directory>, Option<EdgeWeight>>

digest_to_node_ix: HashMap<B3Digest, NodeIndex>

order_validator: O

Implementations

impl DirectoryGraph<LeavesToRootValidator>

pub fn add(&mut self, directory: Directory) -> Result<(), Error>

Insert a new Directory into the closure

impl DirectoryGraph<RootToLeavesValidator>

pub fn digest_allowed(&self, digest: B3Digest) -> bool

If the user is parsing directories from canonical protobuf encoding, she can call digest_allowed before parsing the protobuf record and then add it with add_unchecked.

pub fn add(&mut self, directory: Directory) -> Result<(), Error>

Insert a new Directory into the closure

impl<O: OrderValidator> DirectoryGraph<O>

pub fn with_order(order_validator: O) -> Self

Customize the ordering, i.e. for pre-setting the root of the RootToLeavesValidator

pub fn add_order_unchecked(&mut self, directory: Directory) -> Result<(), Error>

Adds a directory which has already been confirmed to be in-order to the graph

pub fn validate(self) -> Result<ValidatedDirectoryGraph, Error>

Trait Implementations

impl<O: Default> Default for DirectoryGraph<O>

fn default() -> DirectoryGraph<O>

Returns the “default value” for a type.