git_traverse/tree/
breadthfirst.rs

1use std::collections::VecDeque;
2
3use git_hash::ObjectId;
4
5/// The error is part of the item returned by the [`traverse()`][impl_::traverse()] function.
6#[derive(Debug, thiserror::Error)]
7#[allow(missing_docs)]
8pub enum Error {
9    #[error("The tree {oid} could not be found")]
10    NotFound { oid: ObjectId },
11    #[error("The delegate cancelled the operation")]
12    Cancelled,
13    #[error(transparent)]
14    ObjectDecode(#[from] git_object::decode::Error),
15}
16
17/// The state used and potentially shared by multiple tree traversals.
18#[derive(Default, Clone)]
19pub struct State {
20    next: VecDeque<ObjectId>,
21    buf: Vec<u8>,
22}
23
24impl State {
25    fn clear(&mut self) {
26        self.next.clear();
27        self.buf.clear();
28    }
29}
30
31pub(crate) mod impl_ {
32    use std::borrow::BorrowMut;
33
34    use git_hash::oid;
35    use git_object::{tree::EntryMode, TreeRefIter};
36
37    use super::{Error, State};
38    use crate::tree::Visit;
39
40    /// Start a breadth-first iteration over the `root` trees entries.
41    ///
42    /// * `root`
43    ///   * the tree to iterate in a nested fashion.
44    /// * `state` - all state used for the iteration. If multiple iterations are performed, allocations can be minimized by reusing
45    ///   this state.
46    /// * `find` - a way to lookup new object data during traversal by their ObjectId, writing their data into buffer and returning
47    ///    an iterator over entries if the object is present and is a tree. Caching should be implemented within this function
48    ///    as needed. The return value is `Option<TreeIter>` which degenerates all error information. Not finding a commit should also
49    ///    be considered an errors as all objects in the tree DAG should be present in the database. Hence [`Error::NotFound`] should
50    ///    be escalated into a more specific error if its encountered by the caller.
51    /// * `delegate` - A way to observe entries and control the iteration while allowing the optimizer to let you pay only for what you use.
52    pub fn traverse<StateMut, Find, V>(
53        root: TreeRefIter<'_>,
54        mut state: StateMut,
55        mut find: Find,
56        delegate: &mut V,
57    ) -> Result<(), Error>
58    where
59        Find: for<'a> FnMut(&oid, &'a mut Vec<u8>) -> Option<TreeRefIter<'a>>,
60        StateMut: BorrowMut<State>,
61        V: Visit,
62    {
63        let state = state.borrow_mut();
64        state.clear();
65        let mut tree = root;
66        loop {
67            for entry in tree {
68                let entry = entry?;
69                match entry.mode {
70                    EntryMode::Tree => {
71                        use crate::tree::visit::Action::*;
72                        delegate.push_path_component(entry.filename);
73                        let action = delegate.visit_tree(&entry);
74                        match action {
75                            Skip => {}
76                            Continue => {
77                                delegate.pop_path_component();
78                                delegate.push_back_tracked_path_component(entry.filename);
79                                state.next.push_back(entry.oid.to_owned())
80                            }
81                            Cancel => {
82                                return Err(Error::Cancelled);
83                            }
84                        }
85                    }
86                    _non_tree => {
87                        delegate.push_path_component(entry.filename);
88                        if delegate.visit_nontree(&entry).cancelled() {
89                            return Err(Error::Cancelled);
90                        }
91                    }
92                }
93                delegate.pop_path_component();
94            }
95            match state.next.pop_front() {
96                Some(oid) => {
97                    delegate.pop_front_tracked_path_and_set_current();
98                    match find(&oid, &mut state.buf) {
99                        Some(tree_iter) => tree = tree_iter,
100                        None => return Err(Error::NotFound { oid: oid.to_owned() }),
101                    }
102                }
103                None => break Ok(()),
104            }
105        }
106    }
107}
git_traverse/tree/breadthfirst.rs

git_traverse/tree/
breadthfirst.rs
