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
113
114
115
116
117

use std::collections::VecDeque;

use git_hash::ObjectId;
use quick_error::quick_error;

quick_error! {
    /// The error is part of the item returned by the [`traverse()`] function.
    #[derive(Debug)]
    #[allow(missing_docs)]
    pub enum Error {
        NotFound{oid: ObjectId} {
            display("The tree {} could not be found", oid)
        }
        Cancelled {
            display("The delegate cancelled the operation")
        }
        ObjectDecode(err: git_object::decode::Error) {
            display("An object could not be decoded")
            source(err)
            from()
        }
    }
}

/// The state used and potentially shared by multiple tree traversals.
#[derive(Default, Clone)]
pub struct State {
    next: VecDeque<(bool, 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 git_hash::oid;
    use git_object::{tree::EntryMode, 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::NotFound`] 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,
        mut find: Find,
        delegate: &mut V,
    ) -> Result<(), Error>
    where
        Find: for<'a> FnMut(&oid, &'a mut Vec<u8>) -> Option<TreeRefIter<'a>>,
        StateMut: BorrowMut<State>,
        V: Visit,
    {
        let state = state.borrow_mut();
        state.clear();
        let mut tree = root;
        loop {
            for entry in tree {
                let entry = entry?;
                match entry.mode {
                    EntryMode::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((true, entry.oid.to_owned()))
                            }
                            Cancel => {
                                return Err(Error::Cancelled);
                            }
                        }
                    }
                    _non_tree => {
                        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((should_pop_path, oid)) => {
                    if should_pop_path {
                        delegate.pop_front_tracked_path_and_set_current();
                    }
                    match find(&oid, &mut state.buf) {
                        Some(tree_iter) => tree = tree_iter,
                        None => return Err(Error::NotFound { oid: oid.to_owned() }),
                    }
                }
                None => break Ok(()),
            }
        }
    }
}