git-traverse 0.8.1

use std::{borrow::BorrowMut, collections::VecDeque};

use git_hash::{oid, ObjectId};
use git_object::{tree, TreeRefIter};
use quick_error::quick_error;

use crate::tree::visit::Visit;

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

/// 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 {
                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(()),
        }
    }
}