gix_traverse/tree/
depthfirst.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
pub use super::breadthfirst::Error;

/// The state used and potentially shared by multiple tree traversals, reusing memory.
#[derive(Default, Clone)]
pub struct State {
    freelist: Vec<Vec<u8>>,
}

impl State {
    /// Pop one empty buffer from the free-list.
    pub fn pop_buf(&mut self) -> Vec<u8> {
        match self.freelist.pop() {
            None => Vec::new(),
            Some(mut buf) => {
                buf.clear();
                buf
            }
        }
    }

    /// Make `buf` available for re-use with [`Self::pop_buf()`].
    pub fn push_buf(&mut self, buf: Vec<u8>) {
        self.freelist.push(buf);
    }
}

pub(super) mod function {
    use super::{Error, State};
    use crate::tree::visit::Action;
    use crate::tree::Visit;
    use gix_hash::ObjectId;
    use gix_object::{FindExt, TreeRefIter};
    use std::borrow::BorrowMut;

    /// A depth-first traversal of the `root` tree, that preserves the natural order of a tree while immediately descending
    /// into sub-trees.
    ///
    /// `state` can be passed to re-use memory during multiple invocations.
    pub fn depthfirst<StateMut, Find, V>(
        root: ObjectId,
        mut state: StateMut,
        objects: Find,
        delegate: &mut V,
    ) -> Result<(), Error>
    where
        Find: gix_object::Find,
        StateMut: BorrowMut<State>,
        V: Visit,
    {
        enum Machine {
            GetTree(ObjectId),
            Iterate {
                tree_buf: Vec<u8>,
                byte_offset_to_next_entry: usize,
            },
        }

        let state = state.borrow_mut();
        let mut stack = vec![Machine::GetTree(root)];
        'outer: while let Some(item) = stack.pop() {
            match item {
                Machine::GetTree(id) => {
                    let mut buf = state.pop_buf();
                    objects.find_tree_iter(&id, &mut buf)?;
                    stack.push(Machine::Iterate {
                        tree_buf: buf,
                        byte_offset_to_next_entry: 0,
                    });
                }
                Machine::Iterate {
                    tree_buf: buf,
                    byte_offset_to_next_entry,
                } => {
                    let mut iter = TreeRefIter::from_bytes(&buf[byte_offset_to_next_entry..]);
                    delegate.pop_back_tracked_path_and_set_current();
                    while let Some(entry) = iter.next() {
                        let entry = entry?;
                        if entry.mode.is_tree() {
                            delegate.push_path_component(entry.filename);
                            let res = delegate.visit_tree(&entry);
                            delegate.pop_path_component();
                            match res {
                                Action::Continue => {}
                                Action::Cancel => break 'outer,
                                Action::Skip => continue,
                            }

                            delegate.push_back_tracked_path_component("".into());
                            delegate.push_back_tracked_path_component(entry.filename);
                            let recurse_tree = Machine::GetTree(entry.oid.to_owned());
                            let continue_at_next_entry = Machine::Iterate {
                                byte_offset_to_next_entry: iter.offset_to_next_entry(&buf),
                                tree_buf: buf,
                            };
                            stack.push(continue_at_next_entry);
                            stack.push(recurse_tree);
                            continue 'outer;
                        } else {
                            delegate.push_path_component(entry.filename);
                            if let Action::Cancel = delegate.visit_nontree(&entry) {
                                break 'outer;
                            }
                            delegate.pop_path_component();
                        }
                    }
                    state.push_buf(buf);
                }
            }
        }
        Ok(())
    }
}