gix_traverse/tree/
depthfirst.rs

1pub use super::breadthfirst::Error;
2
3/// The state used and potentially shared by multiple tree traversals, reusing memory.
4#[derive(Default, Clone)]
5pub struct State {
6    freelist: Vec<Vec<u8>>,
7}
8
9impl State {
10    /// Pop one empty buffer from the free-list.
11    pub fn pop_buf(&mut self) -> Vec<u8> {
12        match self.freelist.pop() {
13            None => Vec::new(),
14            Some(mut buf) => {
15                buf.clear();
16                buf
17            }
18        }
19    }
20
21    /// Make `buf` available for re-use with [`Self::pop_buf()`].
22    pub fn push_buf(&mut self, buf: Vec<u8>) {
23        self.freelist.push(buf);
24    }
25}
26
27pub(super) mod function {
28    use super::{Error, State};
29    use crate::tree::visit::Action;
30    use crate::tree::Visit;
31    use gix_hash::ObjectId;
32    use gix_object::{FindExt, TreeRefIter};
33    use std::borrow::BorrowMut;
34
35    /// A depth-first traversal of the `root` tree, that preserves the natural order of a tree while immediately descending
36    /// into sub-trees.
37    ///
38    /// `state` can be passed to re-use memory during multiple invocations.
39    pub fn depthfirst<StateMut, Find, V>(
40        root: ObjectId,
41        mut state: StateMut,
42        objects: Find,
43        delegate: &mut V,
44    ) -> Result<(), Error>
45    where
46        Find: gix_object::Find,
47        StateMut: BorrowMut<State>,
48        V: Visit,
49    {
50        enum Machine {
51            GetTree(ObjectId),
52            Iterate {
53                tree_buf: Vec<u8>,
54                byte_offset_to_next_entry: usize,
55            },
56        }
57
58        let state = state.borrow_mut();
59        let mut stack = vec![Machine::GetTree(root)];
60        'outer: while let Some(item) = stack.pop() {
61            match item {
62                Machine::GetTree(id) => {
63                    let mut buf = state.pop_buf();
64                    objects.find_tree_iter(&id, &mut buf)?;
65                    stack.push(Machine::Iterate {
66                        tree_buf: buf,
67                        byte_offset_to_next_entry: 0,
68                    });
69                }
70                Machine::Iterate {
71                    tree_buf: buf,
72                    byte_offset_to_next_entry,
73                } => {
74                    let mut iter = TreeRefIter::from_bytes(&buf[byte_offset_to_next_entry..]);
75                    delegate.pop_back_tracked_path_and_set_current();
76                    while let Some(entry) = iter.next() {
77                        let entry = entry?;
78                        if entry.mode.is_tree() {
79                            delegate.push_path_component(entry.filename);
80                            let res = delegate.visit_tree(&entry);
81                            delegate.pop_path_component();
82                            match res {
83                                Action::Continue => {}
84                                Action::Cancel => break 'outer,
85                                Action::Skip => continue,
86                            }
87
88                            delegate.push_back_tracked_path_component("".into());
89                            delegate.push_back_tracked_path_component(entry.filename);
90                            let recurse_tree = Machine::GetTree(entry.oid.to_owned());
91                            let continue_at_next_entry = Machine::Iterate {
92                                byte_offset_to_next_entry: iter.offset_to_next_entry(&buf),
93                                tree_buf: buf,
94                            };
95                            stack.push(continue_at_next_entry);
96                            stack.push(recurse_tree);
97                            continue 'outer;
98                        } else {
99                            delegate.push_path_component(entry.filename);
100                            if let Action::Cancel = delegate.visit_nontree(&entry) {
101                                break 'outer;
102                            }
103                            delegate.pop_path_component();
104                        }
105                    }
106                    state.push_buf(buf);
107                }
108            }
109        }
110        Ok(())
111    }
112}
gix_traverse/tree/depthfirst.rs

gix_traverse/tree/
depthfirst.rs
