heddle_object_model/object/
tree_walk.rs

1// SPDX-License-Identifier: Apache-2.0
2//! Tree integrity walking — single traversal for reference and content checks.
3
4use std::collections::HashSet;
5
6use crate::error::Result;
7
8use super::{ContentHash, ObjectSource, Tree, TreeEntry};
9
10/// Events emitted while walking reachable trees for integrity checks.
11#[derive(Debug, Clone, PartialEq, Eq)]
12pub enum TreeIntegrityEvent<'a> {
13    /// A tree was entered for the first time during this walk.
14    EnterTree { hash: ContentHash, tree: &'a Tree },
15    /// A blob file entry at `path` (symlinks and gitlinks are excluded).
16    BlobLeaf { entry: &'a TreeEntry, path: String },
17    /// A child tree entry from `parent_hash`.
18    TreeRef {
19        parent_hash: ContentHash,
20        entry: &'a TreeEntry,
21    },
22}
23
24/// Walk all trees reachable from `roots`, deduplicating visited trees.
25///
26/// Missing root or subtree trees are skipped silently. Gitlink entries are not
27/// descended into. Visitation order is depth-first, sorted tree entry order.
28pub fn walk_tree_integrity<S, V>(
29    source: &S,
30    roots: impl IntoIterator<Item = ContentHash>,
31    visitor: &mut V,
32) -> Result<()>
33where
34    S: ObjectSource + ?Sized,
35    V: FnMut(TreeIntegrityEvent<'_>) -> Result<()>,
36{
37    let mut visited = HashSet::new();
38    for root in roots {
39        walk_tree_recursive(source, &root, "", &mut visited, visitor)?;
40    }
41    Ok(())
42}
43
44fn walk_tree_recursive<S, V>(
45    source: &S,
46    tree_hash: &ContentHash,
47    path_prefix: &str,
48    visited: &mut HashSet<ContentHash>,
49    visitor: &mut V,
50) -> Result<()>
51where
52    S: ObjectSource + ?Sized,
53    V: FnMut(TreeIntegrityEvent<'_>) -> Result<()>,
54{
55    if visited.contains(tree_hash) {
56        return Ok(());
57    }
58    visited.insert(*tree_hash);
59
60    let Some(tree) = source.get_tree(tree_hash)? else {
61        return Ok(());
62    };
63
64    visitor(TreeIntegrityEvent::EnterTree {
65        hash: *tree_hash,
66        tree: &tree,
67    })?;
68
69    for entry in tree.entries() {
70        let path = if path_prefix.is_empty() {
71            entry.name().to_string()
72        } else {
73            format!("{path_prefix}/{}", entry.name())
74        };
75
76        if entry.blob_hash().is_some() {
77            visitor(TreeIntegrityEvent::BlobLeaf {
78                entry,
79                path: path.clone(),
80            })?;
81        } else if let Some(child_hash) = entry.tree_hash() {
82            visitor(TreeIntegrityEvent::TreeRef {
83                parent_hash: *tree_hash,
84                entry,
85            })?;
86            walk_tree_recursive(source, &child_hash, &path, visited, visitor)?;
87        }
88    }
89
90    Ok(())
91}
heddle_object_model/object/tree_walk.rs

heddle_object_model/object/
tree_walk.rs
