gix_traverse/tree/
breadthfirst.rs

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

gix_traverse/tree/
breadthfirst.rs
