gix_traverse/tree/
breadthfirst.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
use std::collections::VecDeque;

use gix_hash::ObjectId;

/// The error is part of the item returned by the [`traverse()`][impl_::traverse()] function.
#[derive(Debug, thiserror::Error)]
#[allow(missing_docs)]
pub enum Error {
    #[error(transparent)]
    Find(#[from] gix_object::find::existing_iter::Error),
    #[error("The delegate cancelled the operation")]
    Cancelled,
    #[error(transparent)]
    ObjectDecode(#[from] gix_object::decode::Error),
}

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

impl State {
    fn clear(&mut self) {
        self.next.clear();
        self.buf.clear();
    }
}

pub(crate) mod impl_ {
    use std::borrow::BorrowMut;

    use gix_object::{FindExt, TreeRefIter};

    use super::{Error, State};
    use crate::tree::Visit;

    /// Start a breadth-first iteration over the `root` trees entries.
    ///
    /// * `root`
    ///   * the tree to iterate in a nested fashion.
    /// * `state` - all state used for the iteration. If multiple iterations are performed, allocations can be minimized by reusing
    ///   this state.
    /// * `find` - a way to lookup new object data during traversal by their `ObjectId`, writing their data into buffer and returning
    ///    an iterator over entries if the object is present and is a tree. Caching should be implemented within this function
    ///    as needed. The return value is `Option<TreeIter>` which degenerates all error information. Not finding a commit should also
    ///    be considered an errors as all objects in the tree DAG should be present in the database. Hence [`Error::Find`] should
    ///    be escalated into a more specific error if its encountered by the caller.
    /// * `delegate` - A way to observe entries and control the iteration while allowing the optimizer to let you pay only for what you use.
    pub fn traverse<StateMut, Find, V>(
        root: TreeRefIter<'_>,
        mut state: StateMut,
        objects: Find,
        delegate: &mut V,
    ) -> Result<(), Error>
    where
        Find: gix_object::Find,
        StateMut: BorrowMut<State>,
        V: Visit,
    {
        let state = state.borrow_mut();
        state.clear();
        let mut tree = root;
        loop {
            for entry in tree {
                let entry = entry?;
                if entry.mode.is_tree() {
                    use crate::tree::visit::Action::*;
                    delegate.push_path_component(entry.filename);
                    let action = delegate.visit_tree(&entry);
                    match action {
                        Skip => {}
                        Continue => {
                            delegate.pop_path_component();
                            delegate.push_back_tracked_path_component(entry.filename);
                            state.next.push_back(entry.oid.to_owned());
                        }
                        Cancel => {
                            return Err(Error::Cancelled);
                        }
                    }
                } else {
                    delegate.push_path_component(entry.filename);
                    if delegate.visit_nontree(&entry).cancelled() {
                        return Err(Error::Cancelled);
                    }
                }
                delegate.pop_path_component();
            }
            match state.next.pop_front() {
                Some(oid) => {
                    delegate.pop_front_tracked_path_and_set_current();
                    tree = objects.find_tree_iter(&oid, &mut state.buf)?;
                }
                None => break Ok(()),
            }
        }
    }
}