diff options
Diffstat (limited to 'vendor/gix-traverse/src/tree')
| -rw-r--r-- | vendor/gix-traverse/src/tree/breadthfirst.rs | 107 | ||||
| -rw-r--r-- | vendor/gix-traverse/src/tree/mod.rs | 69 | ||||
| -rw-r--r-- | vendor/gix-traverse/src/tree/recorder.rs | 139 |
3 files changed, 315 insertions, 0 deletions
diff --git a/vendor/gix-traverse/src/tree/breadthfirst.rs b/vendor/gix-traverse/src/tree/breadthfirst.rs new file mode 100644 index 000000000..b0c7ffdf5 --- /dev/null +++ b/vendor/gix-traverse/src/tree/breadthfirst.rs @@ -0,0 +1,107 @@ +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("The tree {oid} could not be found")] + NotFound { oid: ObjectId }, + #[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_hash::oid; + use gix_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(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(oid) => { + 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(()), + } + } + } +} diff --git a/vendor/gix-traverse/src/tree/mod.rs b/vendor/gix-traverse/src/tree/mod.rs new file mode 100644 index 000000000..5ae01736c --- /dev/null +++ b/vendor/gix-traverse/src/tree/mod.rs @@ -0,0 +1,69 @@ +use std::collections::VecDeque; + +use gix_object::bstr::{BStr, BString}; + +/// A trait to allow responding to a traversal designed to observe all entries in a tree, recursively while keeping track of +/// paths if desired. +pub trait Visit { + /// Sets the full path path in front of the queue so future calls to push and pop components affect it instead. + fn pop_front_tracked_path_and_set_current(&mut self); + /// Append a `component` to the end of a path, which may be empty. + fn push_back_tracked_path_component(&mut self, component: &BStr); + /// Append a `component` to the end of a path, which may be empty. + fn push_path_component(&mut self, component: &BStr); + /// Removes the last component from the path, which may leave it empty. + fn pop_path_component(&mut self); + + /// Observe a tree entry that is a tree and return an instruction whether to continue or not. + /// [`Action::Skip`][visit::Action::Skip] can be used to prevent traversing it, for example if it's known to the caller already. + /// + /// The implementation may use the current path to learn where in the tree the change is located. + fn visit_tree(&mut self, entry: &gix_object::tree::EntryRef<'_>) -> visit::Action; + + /// Observe a tree entry that is NO tree and return an instruction whether to continue or not. + /// [`Action::Skip`][visit::Action::Skip] has no effect here. + /// + /// The implementation may use the current path to learn where in the tree the change is located. + fn visit_nontree(&mut self, entry: &gix_object::tree::EntryRef<'_>) -> visit::Action; +} + +/// A [Visit][Visit] implementation to record every observed change and keep track of the changed paths. +/// +/// Recorders can also be instructed to track the filename only, or no location at all. +#[derive(Clone, Debug)] +pub struct Recorder { + path_deque: VecDeque<BString>, + path: BString, + /// How to track the location. + location: Option<recorder::Location>, + /// The observed entries. + pub records: Vec<recorder::Entry>, +} + +/// +pub mod visit { + /// What to do after an entry was [recorded][super::Visit::visit_tree()]. + #[derive(Clone, Copy, PartialOrd, PartialEq, Ord, Eq, Hash)] + pub enum Action { + /// Continue the traversal of entries. + Continue, + /// Stop the traversal of entries, making this te last call to [`visit_(tree|nontree)(…)`][super::Visit::visit_nontree()]. + Cancel, + /// Don't dive into the entry, skipping children effectively. Only useful in [`visit_tree(…)`][super::Visit::visit_tree()]. + Skip, + } + + impl Action { + /// Returns true if this action means to stop the traversal. + pub fn cancelled(&self) -> bool { + matches!(self, Action::Cancel) + } + } +} + +/// +pub mod recorder; + +/// +pub mod breadthfirst; +pub use breadthfirst::impl_::traverse as breadthfirst; diff --git a/vendor/gix-traverse/src/tree/recorder.rs b/vendor/gix-traverse/src/tree/recorder.rs new file mode 100644 index 000000000..d6144c9b9 --- /dev/null +++ b/vendor/gix-traverse/src/tree/recorder.rs @@ -0,0 +1,139 @@ +use gix_hash::ObjectId; +use gix_object::{ + bstr::{BStr, BString, ByteSlice, ByteVec}, + tree, +}; + +use crate::tree::{visit::Action, Recorder, Visit}; + +/// Describe how to track the location of an entry. +#[derive(Debug, Clone, Copy, Eq, PartialEq)] +pub enum Location { + /// Track the entire path, relative to the repository. + Path, + /// Keep only the file-name as location, which may be enough for some calculations. + /// + /// This is less expensive than tracking the entire `Path`. + FileName, +} + +/// An owned entry as observed by a call to [`visit_(tree|nontree)(…)`][Visit::visit_tree()], enhanced with the full path to it. +/// Otherwise similar to [`gix_object::tree::EntryRef`]. +#[derive(Clone, Debug, PartialEq, Eq)] +pub struct Entry { + /// The kind of entry, similar to entries in a unix directory tree. + pub mode: tree::EntryMode, + /// The full path to the entry. A root entry would be `d`, and a file `a` within the directory would be `d/a`. + /// + /// This is independent of the platform and the path separators actually used there. + pub filepath: BString, + /// The id of the entry which can be used to locate it in an object database. + pub oid: ObjectId, +} + +impl Entry { + fn new(entry: &tree::EntryRef<'_>, filepath: BString) -> Self { + Entry { + filepath, + oid: entry.oid.to_owned(), + mode: entry.mode, + } + } +} + +impl Default for Recorder { + fn default() -> Self { + Recorder { + path_deque: Default::default(), + path: Default::default(), + location: Location::Path.into(), + records: vec![], + } + } +} + +impl Recorder { + fn pop_element(&mut self) { + if let Some(pos) = self.path.rfind_byte(b'/') { + self.path.resize(pos, 0); + } else { + self.path.clear(); + } + } + + fn push_element(&mut self, name: &BStr) { + if !self.path.is_empty() { + self.path.push(b'/'); + } + self.path.push_str(name); + } +} + +/// Builder +impl Recorder { + /// Obtain a copy of the currently tracked, full path of the entry. + pub fn track_location(mut self, location: Option<Location>) -> Self { + self.location = location; + self + } +} + +/// Access +impl Recorder { + /// Obtain a copy of the currently tracked, full path of the entry. + pub fn path_clone(&self) -> BString { + self.path.clone() + } + + /// Return the currently set path. + pub fn path(&self) -> &BStr { + self.path.as_ref() + } +} + +impl Visit for Recorder { + fn pop_front_tracked_path_and_set_current(&mut self) { + if let Some(Location::Path) = self.location { + self.path = self + .path_deque + .pop_front() + .expect("every call is matched with push_tracked_path_component"); + } + } + + fn push_back_tracked_path_component(&mut self, component: &BStr) { + if let Some(Location::Path) = self.location { + self.push_element(component); + self.path_deque.push_back(self.path.clone()); + } + } + + fn push_path_component(&mut self, component: &BStr) { + match self.location { + None => {} + Some(Location::Path) => { + self.push_element(component); + } + Some(Location::FileName) => { + self.path.clear(); + self.path.extend_from_slice(component); + } + } + } + + fn pop_path_component(&mut self) { + if let Some(Location::Path) = self.location { + self.pop_element() + } + } + + fn visit_tree(&mut self, entry: &tree::EntryRef<'_>) -> Action { + self.records.push(Entry::new(entry, self.path_clone())); + Action::Continue + } + + fn visit_nontree(&mut self, entry: &tree::EntryRef<'_>) -> Action { + self.records.push(Entry::new(entry, self.path_clone())); + Action::Continue + } +} |