/// An iterator over the ancestors one or more starting commitspub struct Ancestors<Find, Predicate, StateMut> {    find: Find,    predicate: Predicate,    state: StateMut,    parents: Parents,    sorting: Sorting,} /// Specify how to handle commit parents during traversal.#[derive(Copy, Clone)]pub enum Parents {    /// Traverse all parents, useful for traversing the entire ancestry.    All,    /// Only traverse along the first parent, which commonly ignores all branches.    First,} impl Default for Parents {    fn default() -> Self {        Parents::All    }} /// Specify how to sort commits during traversal.#[derive(Copy, Clone)]pub enum Sorting {    /// Commits are sorted as they are mentioned in the commit graph.    Topological,    /// Commits are sorted by their commit time in descending order, that is newest first.    ///    /// The sorting applies to all currently queued commit ids and thus is full.    ///    /// # Performance    ///    /// This mode benefits greatly from having an object_cache in `find()`    /// to avoid having to lookup each commit twice.    ByCommitTimeNewestFirst,    /// This sorting is similar to `ByCommitTimeNewestFirst`, but adds a cutoff to not return commits older than    /// a given time, stopping the iteration once no younger commits is queued to be traversed.    ///    /// As the query is usually repeated with different cutoff dates, this search mode benefits greatly from an object cache.    ByCommitTimeNewestFirstCutoffOlderThan {        /// The amount of seconds since unix epoch, the same value obtained by any `git_date::Time` structure and the way git counts time.        time_in_seconds_since_epoch: u32,    },} impl Default for Sorting {    fn default() -> Self {        Sorting::Topological    }} ///pub mod ancestors {    use std::{        borrow::{Borrow, BorrowMut},        collections::VecDeque,        iter::FromIterator,    };     use git_hash::{oid, ObjectId};    use git_hashtable::HashSet;    use git_object::CommitRefIter;     use crate::commit::{Ancestors, Parents, Sorting};     /// The error is part of the item returned by the [Ancestors] iterator.    #[derive(Debug, thiserror::Error)]    #[allow(missing_docs)]    pub enum Error {        #[error("The commit {oid} could not be found")]        FindExisting {            oid: ObjectId,            source: Box<dyn std::error::Error + Send + Sync + 'static>,        },        #[error(transparent)]        ObjectDecode(#[from] git_object::decode::Error),    }     type TimeInSeconds = u32;     /// The state used and potentially shared by multiple graph traversals.    #[derive(Default, Clone)]    pub struct State {        next: VecDeque<(ObjectId, TimeInSeconds)>,        buf: Vec<u8>,        seen: HashSet<ObjectId>,        parents_buf: Vec<u8>,    }     impl State {        fn clear(&mut self) {            self.next.clear();            self.buf.clear();            self.seen.clear();        }    }     /// Builder    impl<Find, Predicate, StateMut> Ancestors<Find, Predicate, StateMut> {        /// Change our commit parent handling mode to the given one.        pub fn parents(mut self, mode: Parents) -> Self {            self.parents = mode;            self        }    }     /// Builder    impl<Find, Predicate, StateMut, E> Ancestors<Find, Predicate, StateMut>    where        Find: for<'a> FnMut(&oid, &'a mut Vec<u8>) -> Result<CommitRefIter<'a>, E>,        StateMut: BorrowMut<State>,        E: std::error::Error + Send + Sync + 'static,    {        /// Set the sorting method, either topological or by author date        pub fn sorting(mut self, sorting: Sorting) -> Result<Self, Error> {            self.sorting = sorting;            if !matches!(self.sorting, Sorting::Topological) {                let mut cutoff_time_storage = self.sorting.cutoff_time().map(|cot| (cot, Vec::new()));                let state = self.state.borrow_mut();                for (commit_id, commit_time) in state.next.iter_mut() {                    let commit_iter = (self.find)(commit_id, &mut state.buf).map_err(|err| Error::FindExisting {                        oid: *commit_id,                        source: err.into(),                    })?;                    let time = commit_iter.committer()?.time.seconds_since_unix_epoch;                    match &mut cutoff_time_storage {                        Some((cutoff_time, storage)) if time >= *cutoff_time => {                            storage.push((*commit_id, time));                        }                        Some(_) => {}                        None => *commit_time = time,                    }                }                let mut v = match cutoff_time_storage {                    Some((_, storage)) => storage,                    None => Vec::from_iter(std::mem::take(&mut state.next).into_iter()),                };                v.sort_by(|a, b| a.1.cmp(&b.1).reverse());                state.next = v.into();            }            Ok(self)        }    }     /// Initialization    impl<Find, StateMut, E> Ancestors<Find, fn(&oid) -> bool, StateMut>    where        Find: for<'a> FnMut(&oid, &'a mut Vec<u8>) -> Result<CommitRefIter<'a>, E>,        StateMut: BorrowMut<State>,        E: std::error::Error + Send + Sync + 'static,    {        /// Create a new instance.        ///        /// * `find` - a way to lookup new object data during traversal by their ObjectId, writing their data into buffer and returning        ///    an iterator over commit tokens if the object is present and is a commit. Caching should be implemented within this function        ///    as needed.        /// * `state` - all state used for the traversal. If multiple traversals are performed, allocations can be minimized by reusing        ///   this state.        /// * `tips`        ///   * the starting points of the iteration, usually commits        ///   * each commit they lead to will only be returned once, including the tip that started it        pub fn new(tips: impl IntoIterator<Item = impl Into<ObjectId>>, state: StateMut, find: Find) -> Self {            Self::filtered(tips, state, find, |_| true)        }    }     /// Initialization    impl<Find, Predicate, StateMut, E> Ancestors<Find, Predicate, StateMut>    where        Find: for<'a> FnMut(&oid, &'a mut Vec<u8>) -> Result<CommitRefIter<'a>, E>,        Predicate: FnMut(&oid) -> bool,        StateMut: BorrowMut<State>,        E: std::error::Error + Send + Sync + 'static,    {        /// Create a new instance with commit filtering enabled.        ///        /// * `find` - a way to lookup new object data during traversal by their ObjectId, writing their data into buffer and returning        ///    an iterator over commit tokens if the object is present and is a commit. Caching should be implemented within this function        ///    as needed.        /// * `state` - all state used for the traversal. If multiple traversals are performed, allocations can be minimized by reusing        ///   this state.        /// * `tips`        ///   * the starting points of the iteration, usually commits        ///   * each commit they lead to will only be returned once, including the tip that started it        /// * `predicate` - indicate whether a given commit should be included in the result as well        ///   as whether its parent commits should be traversed.        pub fn filtered(            tips: impl IntoIterator<Item = impl Into<ObjectId>>,            mut state: StateMut,            find: Find,            mut predicate: Predicate,        ) -> Self {            let tips = tips.into_iter();            {                let state = state.borrow_mut();                state.clear();                state.next.reserve(tips.size_hint().0);                for tip in tips.map(Into::into) {                    let was_inserted = state.seen.insert(tip);                    if was_inserted && predicate(&tip) {                        state.next.push_back((tip, 0));                    }                }            }            Self {                find,                predicate,                state,                parents: Default::default(),                sorting: Default::default(),            }        }    }    /// Access    impl<Find, Predicate, StateMut> Ancestors<Find, Predicate, StateMut>    where        StateMut: Borrow<State>,    {        /// Return an iterator for accessing more of the current commits data.        pub fn commit_iter(&self) -> CommitRefIter<'_> {            CommitRefIter::from_bytes(&self.state.borrow().buf)        }    }     impl<Find, Predicate, StateMut, E> Iterator for Ancestors<Find, Predicate, StateMut>    where        Find: for<'a> FnMut(&oid, &'a mut Vec<u8>) -> Result<CommitRefIter<'a>, E>,        Predicate: FnMut(&oid) -> bool,        StateMut: BorrowMut<State>,        E: std::error::Error + Send + Sync + 'static,    {        type Item = Result<ObjectId, Error>;         fn next(&mut self) -> Option<Self::Item> {            if matches!(self.parents, Parents::First) {                self.next_by_topology()            } else {                match self.sorting {                    Sorting::Topological => self.next_by_topology(),                    Sorting::ByCommitTimeNewestFirst => self.next_by_commit_date(None),                    Sorting::ByCommitTimeNewestFirstCutoffOlderThan {                        time_in_seconds_since_epoch,                    } => self.next_by_commit_date(time_in_seconds_since_epoch.into()),                }            }        }    }     impl Sorting {        /// If not topo sort, provide the cutoff date if present.        fn cutoff_time(&self) -> Option<u32> {            match self {                Sorting::ByCommitTimeNewestFirstCutoffOlderThan {                    time_in_seconds_since_epoch,                } => Some(*time_in_seconds_since_epoch),                _ => None,            }        }    }     /// Utilities    impl<Find, Predicate, StateMut, E> Ancestors<Find, Predicate, StateMut>    where        Find: for<'a> FnMut(&oid, &'a mut Vec<u8>) -> Result<CommitRefIter<'a>, E>,        Predicate: FnMut(&oid) -> bool,        StateMut: BorrowMut<State>,        E: std::error::Error + Send + Sync + 'static,    {        fn next_by_commit_date(&mut self, cutoff_older_than: Option<TimeInSeconds>) -> Option<Result<ObjectId, Error>> {            let state = self.state.borrow_mut();             let (oid, _commit_time) = state.next.pop_front()?;            match (self.find)(&oid, &mut state.buf) {                Ok(commit_iter) => {                    let mut count = 0;                    for token in commit_iter {                        count += 1;                        let is_first = count == 1;                        match token {                            Ok(git_object::commit::ref_iter::Token::Tree { .. }) => continue,                            Ok(git_object::commit::ref_iter::Token::Parent { id }) => {                                let was_inserted = state.seen.insert(id);                                if !(was_inserted && (self.predicate)(&id)) {                                    if is_first && matches!(self.parents, Parents::First) {                                        break;                                    } else {                                        continue;                                    }                                }                                 let parent = (self.find)(id.as_ref(), &mut state.parents_buf).ok();                                let parent_commit_time = parent                                    .and_then(|parent| {                                        parent                                            .committer()                                            .ok()                                            .map(|committer| committer.time.seconds_since_unix_epoch)                                    })                                    .unwrap_or_default();                                 let pos = match state.next.binary_search_by(|c| c.1.cmp(&parent_commit_time).reverse())                                {                                    Ok(_) => None,                                    Err(pos) => Some(pos),                                };                                match cutoff_older_than {                                    Some(cutoff_older_than) if parent_commit_time < cutoff_older_than => continue,                                    Some(_) | None => match pos {                                        Some(pos) => state.next.insert(pos, (id, parent_commit_time)),                                        None => state.next.push_back((id, parent_commit_time)),                                    },                                }                                 if is_first && matches!(self.parents, Parents::First) {                                    break;                                }                            }                            Ok(_unused_token) => break,                            Err(err) => return Some(Err(err.into())),                        }                    }                }                Err(err) => {                    return Some(Err(Error::FindExisting {                        oid,                        source: err.into(),                    }))                }            }            Some(Ok(oid))        }    }     /// Utilities    impl<Find, Predicate, StateMut, E> Ancestors<Find, Predicate, StateMut>    where        Find: for<'a> FnMut(&oid, &'a mut Vec<u8>) -> Result<CommitRefIter<'a>, E>,        Predicate: FnMut(&oid) -> bool,        StateMut: BorrowMut<State>,        E: std::error::Error + Send + Sync + 'static,    {        fn next_by_topology(&mut self) -> Option<Result<ObjectId, Error>> {            let state = self.state.borrow_mut();            let (oid, _commit_time) = state.next.pop_front()?;            match (self.find)(&oid, &mut state.buf) {                Ok(commit_iter) => {                    for token in commit_iter {                        match token {                            Ok(git_object::commit::ref_iter::Token::Tree { .. }) => continue,                            Ok(git_object::commit::ref_iter::Token::Parent { id }) => {                                let was_inserted = state.seen.insert(id);                                if was_inserted && (self.predicate)(&id) {                                    state.next.push_back((id, 0));                                }                                if matches!(self.parents, Parents::First) {                                    break;                                }                            }                            Ok(_a_token_past_the_parents) => break,                            Err(err) => return Some(Err(err.into())),                        }                    }                }                Err(err) => {                    return Some(Err(Error::FindExisting {                        oid,                        source: err.into(),                    }))                }            }            Some(Ok(oid))        }    }}