objects/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::{
7    error::Result,
8    object::{ContentHash, Tree, TreeEntry},
9    store::ObjectSource,
10};
11
12/// Events emitted while walking reachable trees for integrity checks.
13#[derive(Debug, Clone, PartialEq, Eq)]
14pub enum TreeIntegrityEvent<'a> {
15    /// A tree was entered for the first time during this walk.
16    EnterTree { hash: ContentHash, tree: &'a Tree },
17    /// A blob file entry at `path` (symlinks and gitlinks are excluded).
18    BlobLeaf { entry: &'a TreeEntry, path: String },
19    /// A child tree entry from `parent_hash`.
20    TreeRef {
21        parent_hash: ContentHash,
22        entry: &'a TreeEntry,
23    },
24}
25
26/// Walk all trees reachable from `roots`, deduplicating visited trees.
27///
28/// Missing root or subtree trees are skipped silently. Gitlink entries are not
29/// descended into. Visitation order is depth-first, sorted tree entry order.
30pub fn walk_tree_integrity<S, V>(
31    source: &S,
32    roots: impl IntoIterator<Item = ContentHash>,
33    visitor: &mut V,
34) -> Result<()>
35where
36    S: ObjectSource + ?Sized,
37    V: FnMut(TreeIntegrityEvent<'_>) -> Result<()>,
38{
39    let mut visited = HashSet::new();
40    for root in roots {
41        walk_tree_recursive(source, &root, "", &mut visited, visitor)?;
42    }
43    Ok(())
44}
45
46fn walk_tree_recursive<S, V>(
47    source: &S,
48    tree_hash: &ContentHash,
49    path_prefix: &str,
50    visited: &mut HashSet<ContentHash>,
51    visitor: &mut V,
52) -> Result<()>
53where
54    S: ObjectSource + ?Sized,
55    V: FnMut(TreeIntegrityEvent<'_>) -> Result<()>,
56{
57    if visited.contains(tree_hash) {
58        return Ok(());
59    }
60    visited.insert(*tree_hash);
61
62    let Some(tree) = source.get_tree(tree_hash)? else {
63        return Ok(());
64    };
65
66    visitor(TreeIntegrityEvent::EnterTree {
67        hash: *tree_hash,
68        tree: &tree,
69    })?;
70
71    for entry in tree.entries() {
72        let path = if path_prefix.is_empty() {
73            entry.name().to_string()
74        } else {
75            format!("{path_prefix}/{}", entry.name())
76        };
77
78        if entry.blob_hash().is_some() {
79            visitor(TreeIntegrityEvent::BlobLeaf {
80                entry,
81                path: path.clone(),
82            })?;
83        } else if let Some(child_hash) = entry.tree_hash() {
84            visitor(TreeIntegrityEvent::TreeRef {
85                parent_hash: *tree_hash,
86                entry,
87            })?;
88            walk_tree_recursive(source, &child_hash, &path, visited, visitor)?;
89        }
90    }
91
92    Ok(())
93}
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98    use crate::{
99        object::{Blob, Tree, TreeEntry},
100        store::{InMemoryStore, ObjectStore},
101    };
102
103    #[test]
104    fn walk_tree_integrity_dedups_shared_subtrees() {
105        let store = InMemoryStore::new();
106        let blob = Blob::from("shared\n");
107        let blob_hash = store.put_blob(&blob).unwrap();
108        let shared =
109            Tree::from_entries(vec![TreeEntry::file("leaf.txt", blob_hash, false).unwrap()]);
110        let shared_hash = store.put_tree(&shared).unwrap();
111        let root_a = Tree::from_entries(vec![
112            TreeEntry::directory("shared", shared_hash).unwrap(),
113            TreeEntry::file("a.txt", blob_hash, false).unwrap(),
114        ]);
115        let root_b = Tree::from_entries(vec![TreeEntry::directory("shared", shared_hash).unwrap()]);
116        let root_a_hash = store.put_tree(&root_a).unwrap();
117        let root_b_hash = store.put_tree(&root_b).unwrap();
118
119        let mut enter_count = 0;
120        let mut blob_leaves = Vec::new();
121
122        walk_tree_integrity(&store, [root_a_hash, root_b_hash], &mut |event| {
123            match event {
124                TreeIntegrityEvent::EnterTree { .. } => enter_count += 1,
125                TreeIntegrityEvent::BlobLeaf { path, .. } => blob_leaves.push(path),
126                TreeIntegrityEvent::TreeRef { .. } => {}
127            }
128            Ok(())
129        })
130        .unwrap();
131
132        assert_eq!(enter_count, 3, "shared subtree must be visited once");
133        assert_eq!(
134            blob_leaves,
135            vec!["a.txt".to_string(), "shared/leaf.txt".to_string()]
136        );
137    }
138
139    #[test]
140    fn walk_tree_integrity_skips_missing_subtree_silently() {
141        let store = InMemoryStore::new();
142        let missing = ContentHash::compute(b"missing-tree");
143        let root = Tree::from_entries(vec![TreeEntry::directory("gone", missing).unwrap()]);
144        let root_hash = store.put_tree(&root).unwrap();
145
146        let mut enter_count = 0;
147        walk_tree_integrity(&store, [root_hash], &mut |event| {
148            if let TreeIntegrityEvent::EnterTree { .. } = event {
149                enter_count += 1;
150            }
151            Ok(())
152        })
153        .unwrap();
154
155        assert_eq!(enter_count, 1);
156    }
157}
objects/object/tree_walk.rs

objects/object/
tree_walk.rs
