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

//! Various iterators to traverse a graph

///
pub mod ancestors {
    use crate::pack;
    use git_hash::ObjectId;
    use git_object::immutable;
    use std::{
        borrow::Borrow,
        collections::{BTreeSet, VecDeque},
    };

    /// The error used in the iterator implementation of [Ancestors].
    #[derive(Debug, thiserror::Error)]
    #[allow(missing_docs)]
    pub enum Error<LocateErr>
    where
        LocateErr: std::error::Error + 'static,
    {
        #[error(transparent)]
        Locate(LocateErr),
        #[error(transparent)]
        ObjectDecode(#[from] immutable::object::decode::Error),
        #[error("Object id {oid} wasn't found in object database")]
        NotFound { oid: ObjectId },
    }

    /// An iterator over the ancestors one or more starting commits
    pub struct Ancestors<'a, Cache, Locate> {
        db: Locate,
        next: VecDeque<ObjectId>,
        buf: Vec<u8>,
        seen: BTreeSet<ObjectId>,
        cache: &'a mut Cache,
    }

    impl<'a, Cache, Locate> Ancestors<'a, Cache, Locate>
    where
        Cache: pack::cache::DecodeEntry,
        Locate: crate::Locate,
    {
        /// Create a new instance.
        ///
        /// * `db` - a way to lookup new object data during traversal
        /// * `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
        /// * `cache` - a way to speedup object database access
        pub fn new(db: Locate, tips: impl IntoIterator<Item = impl Into<ObjectId>>, cache: &'a mut Cache) -> Self {
            let next: VecDeque<_> = tips.into_iter().map(Into::into).collect();
            let seen = next.iter().cloned().collect();
            Ancestors {
                db,
                next,
                buf: Vec::with_capacity(4096),
                seen,
                cache,
            }
        }
    }

    impl<'a, Cache, Locate> Iterator for Ancestors<'a, Cache, Locate>
    where
        Cache: pack::cache::DecodeEntry,
        Locate: crate::Locate,
    {
        type Item = Result<ObjectId, Error<Locate::Error>>;

        fn next(&mut self) -> Option<Self::Item> {
            let res = self.next.pop_front();
            if let Some(oid) = res {
                match self.db.borrow().locate(oid, &mut self.buf, self.cache) {
                    Ok(Some(obj)) => {
                        if let Some(mut iter) = obj.into_commit_iter() {
                            if let Some(Err(decode_tree_err)) = iter.next() {
                                return Some(Err(decode_tree_err.into()));
                            }
                            for token in iter {
                                match token {
                                    Ok(immutable::commit::iter::Token::Parent { id }) => {
                                        let was_inserted = self.seen.insert(id);
                                        if was_inserted {
                                            self.next.push_back(id);
                                        }
                                    }
                                    Ok(_a_token_past_the_parents) => break,
                                    Err(err) => return Some(Err(err.into())),
                                }
                            }
                        }
                    }
                    Ok(None) => return Some(Err(Error::NotFound { oid })),
                    Err(err) => return Some(Err(Error::Locate(err))),
                }
            }
            res.map(Ok)
        }
    }
}
#[doc(inline)]
pub use ancestors::Ancestors;