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 super::{ContentHash, ObjectSource, Tree, TreeEntry};
7use crate::error::Result;
8
9/// Events emitted while walking reachable trees for integrity checks.
10#[derive(Debug, Clone, PartialEq, Eq)]
11pub enum TreeIntegrityEvent<'a> {
12    /// A tree was entered for the first time during this walk.
13    EnterTree { hash: ContentHash, tree: &'a Tree },
14    /// A blob file entry at `path` (symlinks and gitlinks are excluded).
15    BlobLeaf { entry: &'a TreeEntry, path: String },
16    /// A child tree entry from `parent_hash`.
17    TreeRef {
18        parent_hash: ContentHash,
19        entry: &'a TreeEntry,
20    },
21    /// A root or referenced subtree could not be loaded.
22    MissingTree {
23        hash: ContentHash,
24        parent_hash: Option<ContentHash>,
25        path: String,
26    },
27}
28
29/// Walk all trees reachable from `roots`, deduplicating visited trees.
30///
31/// Missing root or subtree trees emit [`TreeIntegrityEvent::MissingTree`].
32/// Gitlink entries are not descended into. Visitation order is depth-first,
33/// sorted tree entry order. The implementation uses explicit frames so tree
34/// depth cannot overflow the process stack.
35pub fn walk_tree_integrity<S, V>(
36    source: &S,
37    roots: impl IntoIterator<Item = ContentHash>,
38    visitor: &mut V,
39) -> Result<()>
40where
41    S: ObjectSource + ?Sized,
42    V: FnMut(TreeIntegrityEvent<'_>) -> Result<()>,
43{
44    let mut visited = HashSet::new();
45    for root in roots {
46        walk_tree_iterative(source, root, &mut visited, visitor)?;
47    }
48    Ok(())
49}
50
51struct WalkFrame {
52    hash: ContentHash,
53    tree: Tree,
54    path_prefix: String,
55    next_entry: usize,
56}
57
58fn walk_tree_iterative<S, V>(
59    source: &S,
60    root_hash: ContentHash,
61    visited: &mut HashSet<ContentHash>,
62    visitor: &mut V,
63) -> Result<()>
64where
65    S: ObjectSource + ?Sized,
66    V: FnMut(TreeIntegrityEvent<'_>) -> Result<()>,
67{
68    if !visited.insert(root_hash) {
69        return Ok(());
70    }
71
72    let Some(root_tree) = source.get_tree(&root_hash)? else {
73        visitor(TreeIntegrityEvent::MissingTree {
74            hash: root_hash,
75            parent_hash: None,
76            path: String::new(),
77        })?;
78        return Ok(());
79    };
80
81    visitor(TreeIntegrityEvent::EnterTree {
82        hash: root_hash,
83        tree: &root_tree,
84    })?;
85
86    let mut stack = vec![WalkFrame {
87        hash: root_hash,
88        tree: root_tree,
89        path_prefix: String::new(),
90        next_entry: 0,
91    }];
92
93    while let Some(frame) = stack.last_mut() {
94        let Some(entry) = frame.tree.entries().get(frame.next_entry).cloned() else {
95            stack.pop();
96            continue;
97        };
98        frame.next_entry += 1;
99
100        let path = if frame.path_prefix.is_empty() {
101            entry.name().to_string()
102        } else {
103            format!("{}/{}", frame.path_prefix, entry.name())
104        };
105
106        if entry.blob_hash().is_some() {
107            visitor(TreeIntegrityEvent::BlobLeaf {
108                entry: &entry,
109                path,
110            })?;
111        } else if let Some(child_hash) = entry.tree_hash() {
112            visitor(TreeIntegrityEvent::TreeRef {
113                parent_hash: frame.hash,
114                entry: &entry,
115            })?;
116
117            if !visited.insert(child_hash) {
118                continue;
119            }
120            let Some(child_tree) = source.get_tree(&child_hash)? else {
121                visitor(TreeIntegrityEvent::MissingTree {
122                    hash: child_hash,
123                    parent_hash: Some(frame.hash),
124                    path,
125                })?;
126                continue;
127            };
128            visitor(TreeIntegrityEvent::EnterTree {
129                hash: child_hash,
130                tree: &child_tree,
131            })?;
132            stack.push(WalkFrame {
133                hash: child_hash,
134                tree: child_tree,
135                path_prefix: path,
136                next_entry: 0,
137            });
138        }
139    }
140
141    Ok(())
142}
heddle_object_model/object/tree_walk.rs

heddle_object_model/object/
tree_walk.rs
