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 std::borrow::BorrowMut;
29
30    use gix_hash::ObjectId;
31    use gix_object::{FindExt, TreeRefIter};
32
33    use super::{Error, State};
34    use crate::tree::{visit::Action, Visit};
35
36    /// A depth-first traversal of the `root` tree, that preserves the natural order of a tree while immediately descending
37    /// into sub-trees.
38    ///
39    /// `state` can be passed to re-use memory during multiple invocations.
40    pub fn depthfirst<StateMut, Find, V>(
41        root: ObjectId,
42        mut state: StateMut,
43        objects: Find,
44        delegate: &mut V,
45    ) -> Result<(), Error>
46    where
47        Find: gix_object::Find,
48        StateMut: BorrowMut<State>,
49        V: Visit,
50    {
51        enum Machine {
52            GetTree(ObjectId),
53            Iterate {
54                tree_buf: Vec<u8>,
55                byte_offset_to_next_entry: usize,
56            },
57        }
58
59        let state = state.borrow_mut();
60        let mut stack = vec![Machine::GetTree(root)];
61        'outer: while let Some(item) = stack.pop() {
62            match item {
63                Machine::GetTree(id) => {
64                    let mut buf = state.pop_buf();
65                    objects.find_tree_iter(&id, &mut buf)?;
66                    stack.push(Machine::Iterate {
67                        tree_buf: buf,
68                        byte_offset_to_next_entry: 0,
69                    });
70                }
71                Machine::Iterate {
72                    tree_buf: buf,
73                    byte_offset_to_next_entry,
74                } => {
75                    let mut iter = TreeRefIter::from_bytes(&buf[byte_offset_to_next_entry..]);
76                    delegate.pop_back_tracked_path_and_set_current();
77                    while let Some(entry) = iter.next() {
78                        let entry = entry?;
79                        if entry.mode.is_tree() {
80                            delegate.push_path_component(entry.filename);
81                            let res = delegate.visit_tree(&entry);
82                            delegate.pop_path_component();
83                            match res {
84                                Action::Continue => {}
85                                Action::Cancel => break 'outer,
86                                Action::Skip => continue,
87                            }
88
89                            delegate.push_back_tracked_path_component("".into());
90                            delegate.push_back_tracked_path_component(entry.filename);
91                            let recurse_tree = Machine::GetTree(entry.oid.to_owned());
92                            let continue_at_next_entry = Machine::Iterate {
93                                byte_offset_to_next_entry: iter.offset_to_next_entry(&buf),
94                                tree_buf: buf,
95                            };
96                            stack.push(continue_at_next_entry);
97                            stack.push(recurse_tree);
98                            continue 'outer;
99                        } else {
100                            delegate.push_path_component(entry.filename);
101                            if let Action::Cancel = delegate.visit_nontree(&entry) {
102                                break 'outer;
103                            }
104                            delegate.pop_path_component();
105                        }
106                    }
107                    state.push_buf(buf);
108                }
109            }
110        }
111        Ok(())
112    }
113}
gix_traverse/tree/depthfirst.rs

gix_traverse/tree/
depthfirst.rs
