From a0b8f38ab54ac451646aa00cd5e91b6c76f22a84 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Thu, 30 May 2024 05:57:19 +0200 Subject: Merging upstream version 1.72.1+dfsg1. Signed-off-by: Daniel Baumann --- vendor/gix-revision/src/describe.rs | 187 ++++++++----------------- vendor/gix-revision/src/lib.rs | 4 +- vendor/gix-revision/src/spec/mod.rs | 51 +++++++ vendor/gix-revision/src/spec/parse/function.rs | 4 +- vendor/gix-revision/src/types.rs | 48 ------- 5 files changed, 112 insertions(+), 182 deletions(-) delete mode 100644 vendor/gix-revision/src/types.rs (limited to 'vendor/gix-revision/src') diff --git a/vendor/gix-revision/src/describe.rs b/vendor/gix-revision/src/describe.rs index 55cc3deef..2c1636477 100644 --- a/vendor/gix-revision/src/describe.rs +++ b/vendor/gix-revision/src/describe.rs @@ -94,7 +94,8 @@ impl<'a> Display for Format<'a> { } } -type Flags = u32; +/// A bit-field which keeps track of which commit is reachable by one of 32 candidates names. +pub type Flags = u32; const MAX_CANDIDATES: usize = std::mem::size_of::() * 8; /// The options required to call [`describe()`][function::describe()]. @@ -129,14 +130,11 @@ impl<'name> Default for Options<'name> { /// The error returned by the [`describe()`][function::describe()] function. #[derive(Debug, thiserror::Error)] #[allow(missing_docs)] -pub enum Error -where - E: std::error::Error + Send + Sync + 'static, -{ - #[error("Commit {} could not be found during graph traversal", .oid.to_hex())] - Find { +pub enum Error { + #[error("The parents of commit {} could not be added to graph during traversal", oid.to_hex())] + InsertParentsToGraph { #[source] - err: Option, + err: crate::graph::insert_parents::Error, oid: gix_hash::ObjectId, }, #[error("A commit could not be decoded during traversal")] @@ -144,35 +142,32 @@ where } pub(crate) mod function { - use std::{borrow::Cow, cmp::Ordering, collections::VecDeque, iter::FromIterator}; + use std::{borrow::Cow, cmp::Ordering}; use bstr::BStr; use gix_hash::oid; - use gix_hashtable::{hash_map, HashMap}; - use gix_object::CommitRefIter; use super::{Error, Outcome}; - use crate::describe::{Flags, Options, MAX_CANDIDATES}; + use crate::{ + describe::{CommitTime, Flags, Options, MAX_CANDIDATES}, + Graph, PriorityQueue, + }; - /// Given a `commit` id, traverse the commit graph and collect candidate names from the `name_by_oid` mapping to produce + /// Given a `commit` id, traverse the commit `graph` and collect candidate names from the `name_by_oid` mapping to produce /// an `Outcome`, which converted [`into_format()`][Outcome::into_format()] will produce a typical `git describe` string. /// /// Note that the `name_by_oid` map is returned in the [`Outcome`], which can be forcefully returned even if there was no matching /// candidate by setting `fallback_to_oid` to true. - pub fn describe<'name, Find, E>( + pub fn describe<'name>( commit: &oid, - mut find: Find, + graph: &mut Graph<'_, Flags>, Options { name_by_oid, mut max_candidates, fallback_to_oid, first_parent, }: Options<'name>, - ) -> Result>, Error> - where - Find: for<'b> FnMut(&oid, &'b mut Vec) -> Result>, E>, - E: std::error::Error + Send + Sync + 'static, - { + ) -> Result>, Error> { max_candidates = max_candidates.min(MAX_CANDIDATES); if let Some(name) = name_by_oid.get(commit) { return Ok(Some(Outcome { @@ -198,19 +193,16 @@ pub(crate) mod function { }; } - let mut buf = Vec::new(); - let mut parent_buf = Vec::new(); - - let mut queue = VecDeque::from_iter(Some((commit.to_owned(), u32::MAX))); + let mut queue = PriorityQueue::from_iter(Some((u32::MAX, commit.to_owned()))); let mut candidates = Vec::new(); let mut commits_seen = 0; let mut gave_up_on_commit = None; - let mut seen = HashMap::::default(); - seen.insert(commit.to_owned(), 0u32); + graph.clear(); + graph.insert(commit.to_owned(), 0u32); - while let Some((commit, _commit_time)) = queue.pop_front() { + while let Some(commit) = queue.pop_value() { commits_seen += 1; - if let Some(name) = name_by_oid.get(&commit) { + let flags = if let Some(name) = name_by_oid.get(&commit) { if candidates.len() < max_candidates { let identity_bit = 1 << candidates.len(); candidates.push(Candidate { @@ -219,14 +211,17 @@ pub(crate) mod function { identity_bit, order: candidates.len(), }); - *seen.get_mut(&commit).expect("inserted") |= identity_bit; + let flags = graph.get_mut(&commit).expect("inserted"); + *flags |= identity_bit; + *flags } else { gave_up_on_commit = Some(commit); break; } - } + } else { + graph[&commit] + }; - let flags = seen[&commit]; for candidate in candidates .iter_mut() .filter(|c| (flags & c.identity_bit) != c.identity_bit) @@ -257,16 +252,7 @@ pub(crate) mod function { } } - parents_by_date_onto_queue_and_track_names( - &mut find, - &mut buf, - &mut parent_buf, - &mut queue, - &mut seen, - &commit, - flags, - first_parent, - )?; + parents_by_date_onto_queue_and_track_names(graph, &mut queue, commit, flags, first_parent)?; } if candidates.is_empty() { @@ -290,17 +276,14 @@ pub(crate) mod function { }); if let Some(commit_id) = gave_up_on_commit { - queue.push_front((commit_id, u32::MAX)); + queue.insert(u32::MAX, commit_id); commits_seen -= 1; } commits_seen += finish_depth_computation( queue, - find, + graph, candidates.first_mut().expect("at least one candidate"), - seen, - buf, - parent_buf, first_parent, )?; @@ -313,91 +296,41 @@ pub(crate) mod function { })) } - #[allow(clippy::too_many_arguments)] - fn parents_by_date_onto_queue_and_track_names( - find: &mut Find, - buf: &mut Vec, - parent_buf: &mut Vec, - queue: &mut VecDeque<(gix_hash::ObjectId, u32)>, - seen: &mut HashMap, - commit: &gix_hash::oid, + fn parents_by_date_onto_queue_and_track_names( + graph: &mut Graph<'_, Flags>, + queue: &mut PriorityQueue, + commit: gix_hash::ObjectId, commit_flags: Flags, first_parent: bool, - ) -> Result<(), Error> - where - Find: for<'b> FnMut(&oid, &'b mut Vec) -> Result>, E>, - E: std::error::Error + Send + Sync + 'static, - { - let commit_iter = find(commit, buf) - .map_err(|err| Error::Find { - err: Some(err), - oid: commit.to_owned(), - })? - .ok_or_else(|| Error::Find { - err: None, - oid: commit.to_owned(), - })?; - 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: parent_id }) => match seen.entry(parent_id) { - hash_map::Entry::Vacant(entry) => { - let parent = match find(&parent_id, parent_buf).map_err(|err| Error::Find { - err: Some(err), - oid: commit.to_owned(), - })? { - Some(p) => p, - None => continue, // skip missing objects, they don't exist. - }; - - let parent_commit_date = parent - .committer() - .map(|committer| committer.time.seconds_since_unix_epoch) - .unwrap_or_default(); - - entry.insert(commit_flags); - match queue.binary_search_by(|c| c.1.cmp(&parent_commit_date).reverse()) { - Ok(_) => queue.push_back((parent_id, parent_commit_date)), - Err(pos) => queue.insert(pos, (parent_id, parent_commit_date)), - }; - } - hash_map::Entry::Occupied(mut entry) => { - *entry.get_mut() |= commit_flags; - } + ) -> Result<(), Error> { + graph + .insert_parents( + &commit, + |parent_id, parent_commit_date| { + queue.insert(parent_commit_date as u32, parent_id); + commit_flags }, - Ok(_unused_token) => break, - Err(err) => return Err(err.into()), - } - if first_parent { - break; - } - } - + |_parent_id, flags| *flags |= commit_flags, + first_parent, + ) + .map_err(|err| Error::InsertParentsToGraph { err, oid: commit })?; Ok(()) } - #[allow(clippy::too_many_arguments)] - fn finish_depth_computation<'name, Find, E>( - mut queue: VecDeque<(gix_hash::ObjectId, u32)>, - mut find: Find, - best_candidate: &mut Candidate<'name>, - mut seen: HashMap, - mut buf: Vec, - mut parent_buf: Vec, + fn finish_depth_computation( + mut queue: PriorityQueue, + graph: &mut Graph<'_, Flags>, + best_candidate: &mut Candidate<'_>, first_parent: bool, - ) -> Result> - where - Find: for<'b> FnMut(&oid, &'b mut Vec) -> Result>, E>, - E: std::error::Error + Send + Sync + 'static, - { + ) -> Result { let mut commits_seen = 0; - while let Some((commit, _commit_time)) = queue.pop_front() { + while let Some(commit) = queue.pop_value() { commits_seen += 1; - let flags = seen[&commit]; + let flags = graph[&commit]; if (flags & best_candidate.identity_bit) == best_candidate.identity_bit { if queue - .iter() - .all(|(id, _)| (seen[id] & best_candidate.identity_bit) == best_candidate.identity_bit) + .iter_unordered() + .all(|id| (graph[id] & best_candidate.identity_bit) == best_candidate.identity_bit) { break; } @@ -405,16 +338,7 @@ pub(crate) mod function { best_candidate.commits_in_its_future += 1; } - parents_by_date_onto_queue_and_track_names( - &mut find, - &mut buf, - &mut parent_buf, - &mut queue, - &mut seen, - &commit, - flags, - first_parent, - )?; + parents_by_date_onto_queue_and_track_names(graph, &mut queue, commit, flags, first_parent)?; } Ok(commits_seen) } @@ -429,3 +353,6 @@ pub(crate) mod function { order: usize, } } + +/// The timestamp for the creation date of a commit in seconds since unix epoch. +type CommitTime = u32; diff --git a/vendor/gix-revision/src/lib.rs b/vendor/gix-revision/src/lib.rs index ef273b5ae..31d22768c 100644 --- a/vendor/gix-revision/src/lib.rs +++ b/vendor/gix-revision/src/lib.rs @@ -14,6 +14,6 @@ pub use describe::function::describe; /// pub mod spec; +pub use spec::types::Spec; -mod types; -pub use types::Spec; +pub use gix_revwalk::{graph, Graph, PriorityQueue}; diff --git a/vendor/gix-revision/src/spec/mod.rs b/vendor/gix-revision/src/spec/mod.rs index c2df7bc1e..616ad3a26 100644 --- a/vendor/gix-revision/src/spec/mod.rs +++ b/vendor/gix-revision/src/spec/mod.rs @@ -53,6 +53,57 @@ mod _impls { } } +pub(crate) mod types { + /// A revision specification without any bindings to a repository, useful for serialization or movement over thread boundaries. + /// + /// Note that all [object ids][gix_hash::ObjectId] should be a committish, but don't have to be. + /// Unless the field name contains `_exclusive`, the respective objects are included in the set. + #[derive(Copy, Clone, Debug, Ord, PartialOrd, Eq, PartialEq, Hash)] + #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] + pub enum Spec { + /// Include commits reachable from this revision, i.e. `a` and its ancestors. + /// + /// The equivalent to [crate::spec::Kind::IncludeReachable], but with data. + Include(gix_hash::ObjectId), + /// Exclude commits reachable from this revision, i.e. `a` and its ancestors. Example: `^a`. + /// + /// The equivalent to [crate::spec::Kind::ExcludeReachable], but with data. + Exclude(gix_hash::ObjectId), + /// Every commit that is reachable from `from` to `to`, but not any ancestors of `from`. Example: `from..to`. + /// + /// The equivalent to [crate::spec::Kind::RangeBetween], but with data. + Range { + /// The starting point of the range, which is included in the set. + from: gix_hash::ObjectId, + /// The end point of the range, which is included in the set. + to: gix_hash::ObjectId, + }, + /// Every commit reachable through either `theirs` or `ours`, but no commit that is reachable by both. Example: `theirs...ours`. + /// + /// The equivalent to [crate::spec::Kind::ReachableToMergeBase], but with data. + Merge { + /// Their side of the merge, which is included in the set. + theirs: gix_hash::ObjectId, + /// Our side of the merge, which is included in the set. + ours: gix_hash::ObjectId, + }, + /// Include every commit of all parents of `a`, but not `a` itself. Example: `a^@`. + /// + /// The equivalent to [crate::spec::Kind::IncludeReachableFromParents], but with data. + IncludeOnlyParents( + /// Include only the parents of this object, but not the object itself. + gix_hash::ObjectId, + ), + /// Exclude every commit of all parents of `a`, but not `a` itself. Example: `a^!`. + /// + /// The equivalent to [crate::spec::Kind::ExcludeReachableFromParents], but with data. + ExcludeParents( + /// Exclude the parents of this object, but not the object itself. + gix_hash::ObjectId, + ), + } +} + /// pub mod parse; pub use parse::function::parse; diff --git a/vendor/gix-revision/src/spec/parse/function.rs b/vendor/gix-revision/src/spec/parse/function.rs index 94fb4ee5d..8a89f8f68 100644 --- a/vendor/gix-revision/src/spec/parse/function.rs +++ b/vendor/gix-revision/src/spec/parse/function.rs @@ -213,7 +213,7 @@ fn long_describe_prefix(name: &BStr) -> Option<(&BStr, delegate::PrefixHint<'_>) .and_then(|generation| { iter.next().map(|token| { let last_token_len = token.len(); - let first_token_ptr = iter.last().map(|token| token.as_ptr()).unwrap_or(token.as_ptr()); + let first_token_ptr = iter.last().map_or(token.as_ptr(), |token| token.as_ptr()); // SAFETY: both pointers are definitely part of the same object #[allow(unsafe_code)] let prior_tokens_len: usize = unsafe { token.as_ptr().offset_from(first_token_ptr) } @@ -413,7 +413,7 @@ where input = { if let Some(b'@') = sep { - let past_sep = input[sep_pos.map(|pos| pos + 1).unwrap_or(input.len())..].as_bstr(); + let past_sep = input[sep_pos.map_or(input.len(), |pos| pos + 1)..].as_bstr(); let (nav, rest, _consumed) = parens(past_sep)?.ok_or_else(|| Error::AtNeedsCurlyBrackets { input: input[sep_pos.unwrap_or(input.len())..].into(), })?; diff --git a/vendor/gix-revision/src/types.rs b/vendor/gix-revision/src/types.rs deleted file mode 100644 index 374d43e20..000000000 --- a/vendor/gix-revision/src/types.rs +++ /dev/null @@ -1,48 +0,0 @@ -/// A revision specification without any bindings to a repository, useful for serialization or movement over thread boundaries. -/// -/// Note that all [object ids][gix_hash::ObjectId] should be a committish, but don't have to be. -/// Unless the field name contains `_exclusive`, the respective objects are included in the set. -#[derive(Copy, Clone, Debug, Ord, PartialOrd, Eq, PartialEq, Hash)] -#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] -pub enum Spec { - /// Include commits reachable from this revision, i.e. `a` and its ancestors. - /// - /// The equivalent to [crate::spec::Kind::IncludeReachable], but with data. - Include(gix_hash::ObjectId), - /// Exclude commits reachable from this revision, i.e. `a` and its ancestors. Example: `^a`. - /// - /// The equivalent to [crate::spec::Kind::ExcludeReachable], but with data. - Exclude(gix_hash::ObjectId), - /// Every commit that is reachable from `from` to `to`, but not any ancestors of `from`. Example: `from..to`. - /// - /// The equivalent to [crate::spec::Kind::RangeBetween], but with data. - Range { - /// The starting point of the range, which is included in the set. - from: gix_hash::ObjectId, - /// The end point of the range, which is included in the set. - to: gix_hash::ObjectId, - }, - /// Every commit reachable through either `theirs` or `ours`, but no commit that is reachable by both. Example: `theirs...ours`. - /// - /// The equivalent to [crate::spec::Kind::ReachableToMergeBase], but with data. - Merge { - /// Their side of the merge, which is included in the set. - theirs: gix_hash::ObjectId, - /// Our side of the merge, which is included in the set. - ours: gix_hash::ObjectId, - }, - /// Include every commit of all parents of `a`, but not `a` itself. Example: `a^@`. - /// - /// The equivalent to [crate::spec::Kind::IncludeReachableFromParents], but with data. - IncludeOnlyParents( - /// Include only the parents of this object, but not the object itself. - gix_hash::ObjectId, - ), - /// Exclude every commit of all parents of `a`, but not `a` itself. Example: `a^!`. - /// - /// The equivalent to [crate::spec::Kind::ExcludeReachableFromParents], but with data. - ExcludeParents( - /// Exclude the parents of this object, but not the object itself. - gix_hash::ObjectId, - ), -} -- cgit v1.2.3