use std::{fmt::Formatter, ops::Index}; use gix_hash::oid;use smallvec::SmallVec; use crate::Graph; /// A mapping between an object id and arbitrary data, and produced when calling [`Graph::detach()`].pub type IdMap<T> = gix_hashtable::HashMap<gix_hash::ObjectId, T>; ///pub mod commit; mod errors {    ///    pub mod insert_parents {        use crate::graph::commit::iter_parents;         /// The error returned by [`insert_parents()`](crate::Graph::insert_parents()).        #[derive(Debug, thiserror::Error)]        #[expect(missing_docs)]        pub enum Error {            #[error(transparent)]            Lookup(#[from] gix_object::find::existing_iter::Error),            #[error("A commit could not be decoded during traversal")]            Decode(#[from] gix_object::decode::Error),            #[error(transparent)]            Parent(#[from] iter_parents::Error),        }    }     ///    pub mod get_or_insert_default {        use crate::graph::commit::to_owned;         /// The error returned by [`try_lookup_or_insert_default()`](crate::Graph::try_lookup_or_insert_default()).        #[derive(Debug, thiserror::Error)]        #[expect(missing_docs)]        pub enum Error {            #[error(transparent)]            Lookup(#[from] gix_object::find::existing_iter::Error),            #[error(transparent)]            ToOwned(#[from] to_owned::Error),        }    }}pub use errors::{get_or_insert_default, insert_parents};use gix_date::SecondsSinceUnixEpoch; /// The generation away from the HEAD of graph, useful to limit algorithms by topological depth as well.////// 0 would mean the starting point of the hierarchy, and 1 their parents./// This number is only available natively if there is a commit-graph.pub type Generation = u32; impl<T: std::fmt::Debug> std::fmt::Debug for Graph<'_, '_, T> {    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {        std::fmt::Debug::fmt(&self.map, f)    }} impl<'cache, T: Default> Graph<'_, 'cache, T> {    /// Lookup `id` without failing if the commit doesn't exist, and assure that `id` is inserted into our set.    /// If it wasn't, associate it with the default value. Assure `update_data(data)` gets run.    /// Return the commit when done.    /// Note that none of the data updates happen if there was no commit named `id`.    pub fn try_lookup_or_insert(        &mut self,        id: gix_hash::ObjectId,        update_data: impl FnOnce(&mut T),    ) -> Result<Option<LazyCommit<'_, 'cache>>, get_or_insert_default::Error> {        self.try_lookup_or_insert_default(id, T::default, update_data)    }} /// Access and mutationimpl<'cache, T> Graph<'_, 'cache, T> {    /// Returns the amount of entries in the graph.    pub fn len(&self) -> usize {        self.map.len()    }     /// Returns `true` if there is no entry in the graph.    pub fn is_empty(&self) -> bool {        self.map.is_empty()    }     /// Returns true if `id` has data associated with it, meaning that we processed it already.    pub fn contains(&self, id: &gix_hash::oid) -> bool {        self.map.contains_key(id.as_ref())    }     /// Returns the data associated with `id` if available.    pub fn get(&self, id: &gix_hash::oid) -> Option<&T> {        self.map.get(id)    }     /// Returns the data associated with `id` if available as mutable reference.    pub fn get_mut(&mut self, id: &gix_hash::oid) -> Option<&mut T> {        self.map.get_mut(id)    }     /// Insert `id` into the graph and associate it with `value`, returning the previous value associated with `id` if it existed.    pub fn insert(&mut self, id: gix_hash::ObjectId, value: T) -> Option<T> {        self.map.insert(id, value)    }     /// Insert `id` into the graph and associate it with the value returned by `make_data`,    /// and returning the previous value associated with `id` if it existed.    /// Fail if `id` doesn't exist in the object database.    pub fn insert_data<E>(        &mut self,        id: gix_hash::ObjectId,        mut make_data: impl FnMut(LazyCommit<'_, 'cache>) -> Result<T, E>,    ) -> Result<Option<T>, E>    where        E: From<gix_object::find::existing_iter::Error>,    {        let value = make_data(self.lookup(&id).map_err(E::from)?)?;        Ok(self.map.insert(id, value))    }     /// Remove all data from the graph to start over.    pub fn clear(&mut self) {        self.map.clear();    }     /// Insert the parents of commit named `id` to the graph and associate new parents with data    /// by calling `new_parent_data(parent_id, committer_timestamp)`, or update existing parents    /// data with `update_existing(parent_id, &mut existing_data)`.    /// If `first_parent` is `true`, only the first parent of commits will be looked at.    pub fn insert_parents(        &mut self,        id: &gix_hash::oid,        new_parent_data: &mut dyn FnMut(gix_hash::ObjectId, SecondsSinceUnixEpoch) -> T,        update_existing: &mut dyn FnMut(gix_hash::ObjectId, &mut T),        first_parent: bool,    ) -> Result<(), insert_parents::Error> {        let commit = self.lookup(id)?;        let parents: SmallVec<[_; 2]> = commit.iter_parents().collect();        for parent_id in parents {            let parent_id = parent_id?;            match self.map.entry(parent_id) {                gix_hashtable::hash_map::Entry::Vacant(entry) => {                    let parent = match try_lookup(&parent_id, &*self.find, self.cache, &mut self.parent_buf)? {                        Some(p) => p,                        None => continue, // skip missing objects, this is due to shallow clones for instance.                    };                     let parent_commit_date = parent.committer_timestamp().unwrap_or_default();                    entry.insert(new_parent_data(parent_id, parent_commit_date));                }                gix_hashtable::hash_map::Entry::Occupied(mut entry) => {                    update_existing(parent_id, entry.get_mut());                }            }            if first_parent {                break;            }        }        Ok(())    }     /// Insert the parents of commit named `id` to the graph and associate new parents with data    /// as produced by `parent_data(parent_id, parent_info, maybe-existing-data &mut T) -> T`, which is always    /// provided the full parent commit information.    /// It will be provided either existing data, along with complete information about the parent,    /// and produces new data even though it's only used in case the parent isn't stored in the graph yet.    #[expect(clippy::type_complexity)]    pub fn insert_parents_with_lookup<E>(        &mut self,        id: &gix_hash::oid,        parent_data: &mut dyn FnMut(gix_hash::ObjectId, LazyCommit<'_, 'cache>, Option<&mut T>) -> Result<T, E>,    ) -> Result<(), E>    where        E: From<gix_object::find::existing_iter::Error>            + From<gix_object::decode::Error>            + From<commit::iter_parents::Error>,    {        let commit = self.lookup(id).map_err(E::from)?;        let parents: SmallVec<[_; 2]> = commit.iter_parents().collect();        for parent_id in parents {            let parent_id = parent_id.map_err(E::from)?;            let parent = match try_lookup(&parent_id, &*self.find, self.cache, &mut self.parent_buf).map_err(E::from)? {                Some(p) => p,                None => continue, // skip missing objects, this is due to shallow clones for instance.            };             match self.map.entry(parent_id) {                gix_hashtable::hash_map::Entry::Vacant(entry) => {                    entry.insert(parent_data(parent_id, parent, None)?);                }                gix_hashtable::hash_map::Entry::Occupied(mut entry) => {                    parent_data(parent_id, parent, Some(entry.get_mut()))?;                }            }        }        Ok(())    }     /// Turn ourselves into the underlying graph structure, which is a mere mapping between object ids and their data.    pub fn detach(self) -> IdMap<T> {        self.map    }} /// Initializationimpl<'find, 'cache, T> Graph<'find, 'cache, T> {    /// Create a new instance with `objects` to retrieve commits and optionally `cache` to accelerate commit access.    ///    /// ### Performance    ///    /// `find` should be optimized to access the same object repeatedly, ideally with an object cache to keep the last couple of    /// most recently used commits.    /// Furthermore, **none-existing commits should not trigger the pack-db to be refreshed.** Otherwise, performance may be sub-optimal    /// in shallow repositories as running into non-existing commits will trigger a refresh of the `packs` directory.    pub fn new(objects: impl gix_object::Find + 'find, cache: Option<&'cache gix_commitgraph::Graph>) -> Self {        Graph {            find: Box::new(objects),            cache,            map: gix_hashtable::HashMap::default(),            buf: Vec::new(),            parent_buf: Vec::new(),        }    }} /// Commit based methodsimpl<T> Graph<'_, '_, Commit<T>> {    /// Lookup `id` in the graph, but insert it if it's not yet present by looking it up without failing if the commit doesn't exist.    /// Call `new_data()` to obtain data for a newly inserted commit.    /// `update_data(data)` gets run either on existing or on new data.    ///    /// Note that none of the data updates happen if `id` didn't exist.    pub fn get_or_insert_commit_default(        &mut self,        id: gix_hash::ObjectId,        new_data: impl FnOnce() -> T,        update_data: impl FnOnce(&mut T),    ) -> Result<Option<&mut Commit<T>>, get_or_insert_default::Error> {        match self.map.entry(id) {            gix_hashtable::hash_map::Entry::Vacant(entry) => {                let res = try_lookup(&id, &*self.find, self.cache, &mut self.buf)?;                let commit = match res {                    None => return Ok(None),                    Some(commit) => commit,                };                let mut commit = commit.to_owned(new_data)?;                update_data(&mut commit.data);                entry.insert(commit);            }            gix_hashtable::hash_map::Entry::Occupied(mut entry) => {                update_data(&mut entry.get_mut().data);            }        }        Ok(self.map.get_mut(&id))    }     /// For each stored commit, call `clear` on its data.    pub fn clear_commit_data(&mut self, mut clear: impl FnMut(&mut T)) {        self.map.values_mut().for_each(|c| clear(&mut c.data));    }} /// Commit based methodsimpl<T: Default> Graph<'_, '_, Commit<T>> {    /// Lookup `id` in the graph, but insert it if it's not yet present by looking it up without failing if the commit doesn't exist.    /// Newly inserted commits are populated with default data.    /// `update_data(data)` gets run either on existing or on new data.    ///    /// Note that none of the data updates happen if `id` didn't exist.    ///    /// If only commit data is desired without the need for attaching custom data, use    /// [`try_lookup(id).to_owned()`][Graph::try_lookup()] instead.    pub fn get_or_insert_commit(        &mut self,        id: gix_hash::ObjectId,        update_data: impl FnOnce(&mut T),    ) -> Result<Option<&mut Commit<T>>, get_or_insert_default::Error> {        self.get_or_insert_commit_default(id, T::default, update_data)    }     /// Lookup `id` in the graph, but insert it if it's not yet present by looking it up without failing if the commit doesn't exist.    /// `update_commit(commit)` gets run either on existing or on new data.    ///    /// Note that none of the data updates happen if `id` didn't exist in the graph.    pub fn get_or_insert_full_commit(        &mut self,        id: gix_hash::ObjectId,        update_commit: impl FnOnce(&mut Commit<T>),    ) -> Result<Option<&mut Commit<T>>, get_or_insert_default::Error> {        match self.map.entry(id) {            gix_hashtable::hash_map::Entry::Vacant(entry) => {                let res = try_lookup(&id, &*self.find, self.cache, &mut self.buf)?;                let commit = match res {                    None => return Ok(None),                    Some(commit) => commit,                };                let mut commit = commit.to_owned(T::default)?;                update_commit(&mut commit);                entry.insert(commit);            }            gix_hashtable::hash_map::Entry::Occupied(mut entry) => {                update_commit(entry.get_mut());            }        }        Ok(self.map.get_mut(&id))    }} /// Lazy commit accessimpl<'cache, T> Graph<'_, 'cache, T> {    /// Lookup `id` without failing if the commit doesn't exist or `id` isn't a commit,    /// and assure that `id` is inserted into our set    /// with a `default` value assigned to it.    /// `update_data(data)` gets run either on existing or no new data.    /// Return the commit when done.    ///    /// Note that none of the data updates happen if `id` didn't exist.    ///    /// If only commit data is desired without the need for attaching custom data, use    /// [`try_lookup(id)`][Graph::try_lookup()] instead.    pub fn try_lookup_or_insert_default(        &mut self,        id: gix_hash::ObjectId,        default: impl FnOnce() -> T,        update_data: impl FnOnce(&mut T),    ) -> Result<Option<LazyCommit<'_, 'cache>>, get_or_insert_default::Error> {        let res = try_lookup(&id, &*self.find, self.cache, &mut self.buf)?;        Ok(res.inspect(|_commit| match self.map.entry(id) {            gix_hashtable::hash_map::Entry::Vacant(entry) => {                let mut data = default();                update_data(&mut data);                entry.insert(data);            }            gix_hashtable::hash_map::Entry::Occupied(mut entry) => {                update_data(entry.get_mut());            }        }))    }     /// Try to lookup `id` and return a handle to it for accessing its data, but don't fail if the commit doesn't exist    /// or isn't a commit.    ///    /// It's possible that commits don't exist if the repository is shallow.    pub fn try_lookup(        &mut self,        id: &gix_hash::oid,    ) -> Result<Option<LazyCommit<'_, 'cache>>, gix_object::find::existing_iter::Error> {        try_lookup(id, &*self.find, self.cache, &mut self.buf)    }     /// Lookup `id` and return a handle to it, or fail if it doesn't exist or is no commit.    pub fn lookup(        &mut self,        id: &gix_hash::oid,    ) -> Result<LazyCommit<'_, 'cache>, gix_object::find::existing_iter::Error> {        self.try_lookup(id)?            .ok_or(gix_object::find::existing_iter::Error::NotFound { oid: id.to_owned() })    }} fn try_lookup<'graph, 'cache>(    id: &gix_hash::oid,    objects: &dyn gix_object::Find,    cache: Option<&'cache gix_commitgraph::Graph>,    buf: &'graph mut Vec<u8>,) -> Result<Option<LazyCommit<'graph, 'cache>>, gix_object::find::existing_iter::Error> {    if let Some(cache) = cache {        if let Some(pos) = cache.lookup(id) {            return Ok(Some(LazyCommit {                object_hash: id.kind(),                backing: Either::Right((cache, pos)),            }));        }    }    Ok(        match objects            .try_find(id, buf)            .map_err(gix_object::find::existing_iter::Error::Find)?        {            Some(data) => data.kind.is_commit().then_some(LazyCommit {                object_hash: data.object_hash,                backing: Either::Left(buf),            }),            None => None,        },    )} impl<'a, T> Index<&'a gix_hash::oid> for Graph<'_, '_, T> {    type Output = T;     fn index(&self, index: &'a oid) -> &Self::Output {        &self.map[index]    }} /// A commit that contains all information we can obtain through the commit-graph, which is typically enough to fuel any graph iteration.pub struct Commit<T> {    /// The parents of the commit.    pub parents: SmallVec<[gix_hash::ObjectId; 1]>,    /// The time at which the commit was created.    pub commit_time: SecondsSinceUnixEpoch,    /// The generation of the commit, if available.    pub generation: Option<u32>,    /// Any kind of data to associate with this commit.    pub data: T,} impl<T> std::fmt::Debug for Commit<T>where    T: std::fmt::Debug,{    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {        f.debug_struct("Commit")            .field("parents", &self.parents)            .field("commit_time", &self.commit_time)            .field("generation", &self.generation)            .field("data", &self.data)            .finish()    }} impl<T> Clone for Commit<T>where    T: Clone,{    fn clone(&self) -> Self {        Commit {            parents: self.parents.clone(),            commit_time: self.commit_time,            generation: self.generation,            data: self.data.clone(),        }    }} /// A commit that provides access to graph-related information, on demand.////// The owned version of this type is called [`Commit`] and can be obtained by calling [`LazyCommit::to_owned()`].pub struct LazyCommit<'graph, 'cache> {    object_hash: gix_hash::Kind,    backing: Either<&'graph [u8], (&'cache gix_commitgraph::Graph, gix_commitgraph::Position)>,} enum Either<T, U> {    Left(T),    Right(U),}