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

use crate::tree::visit::Visit;
use git_hash::{oid, ObjectId};
use git_object::{immutable, tree};
use quick_error::quick_error;
use std::{borrow::BorrowMut, collections::VecDeque};

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: immutable::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();
    }
}

/// 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: immutable::TreeIter<'_>,
    mut state: StateMut,
    mut find: Find,
    delegate: &mut V,
) -> Result<(), Error>
where
    Find: for<'a> FnMut(&oid, &'a mut Vec<u8>) -> Option<immutable::TreeIter<'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 {
                tree::EntryMode::Tree => {
                    use super::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(()),
        }
    }
}