use std::{cmp::Reverse, collections::VecDeque}; use gix_date::SecondsSinceUnixEpoch;use gix_hash::ObjectId;use smallvec::SmallVec; #[derive(Default, Debug, Copy, Clone)]/// The order with which to prioritize the search.pub enum CommitTimeOrder {    #[default]    /// Sort commits by newest first.    NewestFirst,    /// Sort commits by oldest first.    #[doc(alias = "Sort::REVERSE", alias = "git2")]    OldestFirst,} /// Specify how to sort commits during a [simple](super::Simple) traversal.////// ### Sample History////// The following history will be referred to for explaining how the sort order works, with the number denoting the commit timestamp/// (*their X-alignment doesn't matter*).////// ```text/// ---1----2----4----7 <- second parent of 8///     \              \///      3----5----6----8---/// ```#[derive(Default, Debug, Copy, Clone)]pub enum Sorting {    /// Commits are sorted as they are mentioned in the commit graph.    ///    /// In the *sample history* the order would be `8, 6, 7, 5, 4, 3, 2, 1`.    ///    /// ### Note    ///    /// This is not to be confused with `git log/rev-list --topo-order`, which is notably different from    /// as it avoids overlapping branches.    #[default]    BreadthFirst,    /// Commits are sorted by their commit time in the order specified, either newest or oldest first.    ///    /// The sorting applies to all currently queued commit ids and thus is full.    ///    /// In the *sample history* the order would be `8, 7, 6, 5, 4, 3, 2, 1` for [`NewestFirst`](CommitTimeOrder::NewestFirst),    /// or `1, 2, 3, 4, 5, 6, 7, 8` for [`OldestFirst`](CommitTimeOrder::OldestFirst).    ///    /// # Performance    ///    /// This mode benefits greatly from having an object_cache in `find()`    /// to avoid having to lookup each commit twice.    ByCommitTime(CommitTimeOrder),    /// This sorting is similar to [`ByCommitTime`](Sorting::ByCommitTime), 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.    ///    /// In the *sample history* and a cut-off date of 4, the returned list of commits would be `8, 7, 6, 4`.    ByCommitTimeCutoff {        /// The order in which to prioritize lookups.        order: CommitTimeOrder,        /// The number of seconds since unix epoch, the same value obtained by any `gix_date::Time` structure and the way git counts time.        seconds: gix_date::SecondsSinceUnixEpoch,    },} /// The error is part of the item returned by the [Ancestors](super::Simple) iterator.#[derive(Debug, thiserror::Error)]#[allow(missing_docs)]pub enum Error {    #[error(transparent)]    Find(#[from] gix_object::find::existing_iter::Error),    #[error(transparent)]    ObjectDecode(#[from] gix_object::decode::Error),} use Result as Either; type QueueKey<T> = Either<T, Reverse<T>>;type CommitDateQueue = gix_revwalk::PriorityQueue<QueueKey<SecondsSinceUnixEpoch>, (ObjectId, CommitState)>;type Candidates = VecDeque<crate::commit::Info>; /// The state used and potentially shared by multiple graph traversals.#[derive(Clone)]pub(super) struct State {    next: VecDeque<(ObjectId, CommitState)>,    queue: CommitDateQueue,    buf: Vec<u8>,    seen: gix_revwalk::graph::IdMap<CommitState>,    parents_buf: Vec<u8>,    parent_ids: SmallVec<[(ObjectId, SecondsSinceUnixEpoch); 2]>,    /// The list (FIFO) of thus far interesting commits.    ///    /// As they may turn hidden later, we have to keep them until the conditions are met to return them.    /// If `None`, there is nothing to do with hidden commits.    candidates: Option<Candidates>,} #[derive(Debug, Clone, Copy)]enum CommitState {    /// The commit may be returned, it hasn't been hidden yet.    Interesting,    /// The commit should not be returned.    Hidden,} impl CommitState {    pub fn is_hidden(&self) -> bool {        matches!(self, CommitState::Hidden)    }    pub fn is_interesting(&self) -> bool {        matches!(self, CommitState::Interesting)    }} ///mod init {    use std::cmp::Reverse;     use super::{        super::{simple::Sorting, Either, Info, ParentIds, Parents, Simple},        collect_parents, Candidates, CommitDateQueue, CommitState, CommitTimeOrder, Error, State,    };    use gix_date::SecondsSinceUnixEpoch;    use gix_hash::{oid, ObjectId};    use gix_hashtable::hash_map::Entry;    use gix_object::{CommitRefIter, FindExt};    use std::collections::VecDeque;    use Err as Oldest;    use Ok as Newest;     impl Default for State {        fn default() -> Self {            State {                next: Default::default(),                queue: gix_revwalk::PriorityQueue::new(),                buf: vec![],                seen: Default::default(),                parents_buf: vec![],                parent_ids: Default::default(),                candidates: None,            }        }    }     impl State {        fn clear(&mut self) {            let Self {                next,                queue,                buf,                seen,                parents_buf: _,                parent_ids: _,                candidates,            } = self;            next.clear();            queue.clear();            buf.clear();            seen.clear();            *candidates = None;        }    }     fn to_queue_key(i: i64, order: CommitTimeOrder) -> super::QueueKey<i64> {        match order {            CommitTimeOrder::NewestFirst => Newest(i),            CommitTimeOrder::OldestFirst => Oldest(Reverse(i)),        }    }     /// Builder    impl<Find, Predicate> Simple<Find, Predicate>    where        Find: gix_object::Find,    {        /// Set the `sorting` method.        pub fn sorting(mut self, sorting: Sorting) -> Result<Self, Error> {            self.sorting = sorting;            match self.sorting {                Sorting::BreadthFirst => {                    self.queue_to_vecdeque();                }                Sorting::ByCommitTime(order) | Sorting::ByCommitTimeCutoff { order, .. } => {                    let state = &mut self.state;                    for (commit_id, commit_state) in state.next.drain(..) {                        add_to_queue(                            commit_id,                            commit_state,                            order,                            sorting.cutoff_time(),                            &mut state.queue,                            &self.objects,                            &mut state.buf,                        )?;                    }                }            }            Ok(self)        }         /// Change our commit parent handling mode to the given one.        pub fn parents(mut self, mode: Parents) -> Self {            self.parents = mode;            if matches!(self.parents, Parents::First) {                self.queue_to_vecdeque();            }            self        }         /// Hide the given `tips`, along with all commits reachable by them so that they will not be returned        /// by the traversal.        ///        /// Note that this will force the traversal into a non-intermediate mode and queue return candidates,        /// to be released when it's clear that they truly are not hidden.        ///        /// Note that hidden objects are expected to exist.        pub fn hide(mut self, tips: impl IntoIterator<Item = ObjectId>) -> Result<Self, Error> {            self.state.candidates = Some(VecDeque::new());            let state = &mut self.state;            for id_to_ignore in tips {                let previous = state.seen.insert(id_to_ignore, CommitState::Hidden);                // If there was something, it will pick up whatever commit-state we have set last                // upon iteration. Also, hidden states always override everything else.                if previous.is_none() {                    // Assure we *start* traversing hidden variants of a commit first, give them a head-start.                    match self.sorting {                        Sorting::BreadthFirst => {                            state.next.push_front((id_to_ignore, CommitState::Hidden));                        }                        Sorting::ByCommitTime(order) | Sorting::ByCommitTimeCutoff { order, .. } => {                            add_to_queue(                                id_to_ignore,                                CommitState::Hidden,                                order,                                self.sorting.cutoff_time(),                                &mut state.queue,                                &self.objects,                                &mut state.buf,                            )?;                        }                    }                }            }            if !self                .state                .seen                .values()                .any(|state| matches!(state, CommitState::Hidden))            {                self.state.candidates = None;            }            Ok(self)        }         /// Set the commitgraph as `cache` to greatly accelerate any traversal.        ///        /// The cache will be used if possible, but we will fall back without error to using the object        /// database for commit lookup. If the cache is corrupt, we will fall back to the object database as well.        pub fn commit_graph(mut self, cache: Option<gix_commitgraph::Graph>) -> Self {            self.cache = cache;            self        }         fn queue_to_vecdeque(&mut self) {            let state = &mut self.state;            state.next.extend(                std::mem::replace(&mut state.queue, gix_revwalk::PriorityQueue::new())                    .into_iter_unordered()                    .map(|(_time, id)| id),            );        }    }     fn add_to_queue(        commit_id: ObjectId,        commit_state: CommitState,        order: CommitTimeOrder,        cutoff_time: Option<SecondsSinceUnixEpoch>,        queue: &mut CommitDateQueue,        objects: &impl gix_object::Find,        buf: &mut Vec<u8>,    ) -> Result<(), Error> {        let commit_iter = objects.find_commit_iter(&commit_id, buf)?;        let time = commit_iter.committer()?.seconds();        let key = to_queue_key(time, order);        match (cutoff_time, order) {            (Some(cutoff_time), _) if time >= cutoff_time => {                queue.insert(key, (commit_id, commit_state));            }            (Some(_), _) => {}            (None, _) => {                queue.insert(key, (commit_id, commit_state));            }        }        Ok(())    }     /// Lifecycle    impl<Find> Simple<Find, fn(&oid) -> bool>    where        Find: gix_object::Find,    {        /// 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.        /// * `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>>, find: Find) -> Self {            Self::filtered(tips, find, |_| true)        }    }     /// Lifecycle    impl<Find, Predicate> Simple<Find, Predicate>    where        Find: gix_object::Find,        Predicate: FnMut(&oid) -> bool,    {        /// 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.        /// * `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>>,            find: Find,            mut predicate: Predicate,        ) -> Self {            let tips = tips.into_iter();            let mut state = State::default();            {                state.clear();                state.next.reserve(tips.size_hint().0);                for tip in tips.map(Into::into) {                    let commit_state = CommitState::Interesting;                    let seen = state.seen.insert(tip, commit_state);                    // We know there can only be duplicate interesting ones.                    if seen.is_none() && predicate(&tip) {                        state.next.push_back((tip, commit_state));                    }                }            }            Self {                objects: find,                cache: None,                predicate,                state,                parents: Default::default(),                sorting: Default::default(),            }        }    }     /// Access    impl<Find, Predicate> Simple<Find, Predicate> {        /// Return an iterator for accessing data of the current commit, parsed lazily.        pub fn commit_iter(&self) -> CommitRefIter<'_> {            CommitRefIter::from_bytes(self.commit_data())        }         /// Return the current commits' raw data, which can be parsed using [`gix_object::CommitRef::from_bytes()`].        pub fn commit_data(&self) -> &[u8] {            &self.state.buf        }    }     impl<Find, Predicate> Iterator for Simple<Find, Predicate>    where        Find: gix_object::Find,        Predicate: FnMut(&oid) -> bool,    {        type Item = Result<Info, Error>;         fn next(&mut self) -> Option<Self::Item> {            if matches!(self.parents, Parents::First) {                self.next_by_topology()            } else {                match self.sorting {                    Sorting::BreadthFirst => self.next_by_topology(),                    Sorting::ByCommitTime(order) => self.next_by_commit_date(order, None),                    Sorting::ByCommitTimeCutoff { seconds, order } => self.next_by_commit_date(order, seconds.into()),                }            }            .or_else(|| {                self.state                    .candidates                    .as_mut()                    .and_then(|candidates| candidates.pop_front().map(Ok))            })        }    }     impl Sorting {        /// If not topo sort, provide the cutoff date if present.        fn cutoff_time(&self) -> Option<SecondsSinceUnixEpoch> {            match self {                Sorting::ByCommitTimeCutoff { seconds, .. } => Some(*seconds),                _ => None,            }        }    }     /// Utilities    impl<Find, Predicate> Simple<Find, Predicate>    where        Find: gix_object::Find,        Predicate: FnMut(&oid) -> bool,    {        fn next_by_commit_date(            &mut self,            order: CommitTimeOrder,            cutoff: Option<SecondsSinceUnixEpoch>,        ) -> Option<Result<Info, Error>> {            let state = &mut self.state;            let next = &mut state.queue;             'skip_hidden: loop {                let (commit_time, (oid, _queued_commit_state)) = match next.pop()? {                    (Newest(t) | Oldest(Reverse(t)), o) => (t, o),                };                let mut parents: ParentIds = Default::default();                 // Always use the state that is actually stored, as we may change the type as we go.                let commit_state = *state.seen.get(&oid).expect("every commit we traverse has state added");                if can_deplete_candidates_early(                    next.iter_unordered().map(|t| t.1),                    commit_state,                    state.candidates.as_ref(),                ) {                    return None;                }                match super::super::find(self.cache.as_ref(), &self.objects, &oid, &mut state.buf) {                    Ok(Either::CachedCommit(commit)) => {                        if !collect_parents(&mut state.parent_ids, self.cache.as_ref(), commit.iter_parents()) {                            // drop corrupt caches and try again with ODB                            self.cache = None;                            return self.next_by_commit_date(order, cutoff);                        }                        for (id, parent_commit_time) in state.parent_ids.drain(..) {                            parents.push(id);                            insert_into_seen_and_queue(                                &mut state.seen,                                id,                                &mut state.candidates,                                commit_state,                                &mut self.predicate,                                next,                                order,                                cutoff,                                || parent_commit_time,                            );                        }                    }                    Ok(Either::CommitRefIter(commit_iter)) => {                        for token in commit_iter {                            match token {                                Ok(gix_object::commit::ref_iter::Token::Tree { .. }) => continue,                                Ok(gix_object::commit::ref_iter::Token::Parent { id }) => {                                    parents.push(id);                                    insert_into_seen_and_queue(                                        &mut state.seen,                                        id,                                        &mut state.candidates,                                        commit_state,                                        &mut self.predicate,                                        next,                                        order,                                        cutoff,                                        || {                                            let parent =                                                self.objects.find_commit_iter(id.as_ref(), &mut state.parents_buf).ok();                                            parent                                                .and_then(|parent| {                                                    parent.committer().ok().map(|committer| committer.seconds())                                                })                                                .unwrap_or_default()                                        },                                    );                                }                                Ok(_unused_token) => break,                                Err(err) => return Some(Err(err.into())),                            }                        }                    }                    Err(err) => return Some(Err(err.into())),                }                match commit_state {                    CommitState::Interesting => {                        let info = Info {                            id: oid,

Lines 1–500 of 751. Load more