diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-04 12:41:41 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-04 12:41:41 +0000 |
commit | 10ee2acdd26a7f1298c6f6d6b7af9b469fe29b87 (patch) | |
tree | bdffd5d80c26cf4a7a518281a204be1ace85b4c1 /vendor/gix-refspec/src/match_group | |
parent | Releasing progress-linux version 1.70.0+dfsg1-9~progress7.99u1. (diff) | |
download | rustc-10ee2acdd26a7f1298c6f6d6b7af9b469fe29b87.tar.xz rustc-10ee2acdd26a7f1298c6f6d6b7af9b469fe29b87.zip |
Merging upstream version 1.70.0+dfsg2.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'vendor/gix-refspec/src/match_group')
-rw-r--r-- | vendor/gix-refspec/src/match_group/mod.rs | 112 | ||||
-rw-r--r-- | vendor/gix-refspec/src/match_group/types.rs | 104 | ||||
-rw-r--r-- | vendor/gix-refspec/src/match_group/util.rs | 162 | ||||
-rw-r--r-- | vendor/gix-refspec/src/match_group/validate.rs | 141 |
4 files changed, 519 insertions, 0 deletions
diff --git a/vendor/gix-refspec/src/match_group/mod.rs b/vendor/gix-refspec/src/match_group/mod.rs new file mode 100644 index 000000000..c53b5b531 --- /dev/null +++ b/vendor/gix-refspec/src/match_group/mod.rs @@ -0,0 +1,112 @@ +use std::collections::BTreeSet; + +use crate::{parse::Operation, types::Mode, MatchGroup, RefSpecRef}; + +pub(crate) mod types; +pub use types::{Item, Mapping, Outcome, Source, SourceRef}; + +/// +pub mod validate; + +/// Initialization +impl<'a> MatchGroup<'a> { + /// Take all the fetch ref specs from `specs` get a match group ready. + pub fn from_fetch_specs(specs: impl IntoIterator<Item = RefSpecRef<'a>>) -> Self { + MatchGroup { + specs: specs.into_iter().filter(|s| s.op == Operation::Fetch).collect(), + } + } +} + +/// Matching +impl<'a> MatchGroup<'a> { + /// Match all `items` against all fetch specs present in this group, returning deduplicated mappings from source to destination. + /// Note that this method only makes sense if the specs are indeed fetch specs and may panic otherwise. + /// + /// Note that negative matches are not part of the return value, so they are not observable but will be used to remove mappings. + pub fn match_remotes<'item>(self, mut items: impl Iterator<Item = Item<'item>> + Clone) -> Outcome<'a, 'item> { + let mut out = Vec::new(); + let mut seen = BTreeSet::default(); + let mut push_unique = |mapping| { + if seen.insert(calculate_hash(&mapping)) { + out.push(mapping); + } + }; + let mut matchers: Vec<Option<Matcher<'_>>> = self + .specs + .iter() + .copied() + .map(Matcher::from) + .enumerate() + .map(|(idx, m)| match m.lhs { + Some(Needle::Object(id)) => { + push_unique(Mapping { + item_index: None, + lhs: SourceRef::ObjectId(id), + rhs: m.rhs.map(|n| n.to_bstr()), + spec_index: idx, + }); + None + } + _ => Some(m), + }) + .collect(); + + let mut has_negation = false; + for (spec_index, (spec, matcher)) in self.specs.iter().zip(matchers.iter_mut()).enumerate() { + for (item_index, item) in items.clone().enumerate() { + if spec.mode == Mode::Negative { + has_negation = true; + continue; + } + if let Some(matcher) = matcher { + let (matched, rhs) = matcher.matches_lhs(item); + if matched { + push_unique(Mapping { + item_index: Some(item_index), + lhs: SourceRef::FullName(item.full_ref_name), + rhs, + spec_index, + }) + } + } + } + } + + if let Some(id) = has_negation.then(|| items.next().map(|i| i.target)).flatten() { + let null_id = gix_hash::ObjectId::null(id.kind()); + for matcher in matchers + .into_iter() + .zip(self.specs.iter()) + .filter_map(|(m, spec)| m.and_then(|m| (spec.mode == Mode::Negative).then_some(m))) + { + out.retain(|m| match m.lhs { + SourceRef::ObjectId(_) => true, + SourceRef::FullName(name) => { + !matcher + .matches_lhs(Item { + full_ref_name: name, + target: &null_id, + object: None, + }) + .0 + } + }); + } + } + Outcome { + group: self, + mappings: out, + } + } +} + +fn calculate_hash<T: std::hash::Hash>(t: &T) -> u64 { + use std::hash::Hasher; + let mut s = std::collections::hash_map::DefaultHasher::new(); + t.hash(&mut s); + s.finish() +} + +mod util; +use util::{Matcher, Needle}; diff --git a/vendor/gix-refspec/src/match_group/types.rs b/vendor/gix-refspec/src/match_group/types.rs new file mode 100644 index 000000000..6be601dd5 --- /dev/null +++ b/vendor/gix-refspec/src/match_group/types.rs @@ -0,0 +1,104 @@ +use std::borrow::Cow; + +use bstr::{BStr, BString}; +use gix_hash::oid; + +use crate::RefSpecRef; + +/// A match group is able to match a list of ref specs in order while handling negation, conflicts and one to many mappings. +#[derive(Default, Debug, Clone)] +pub struct MatchGroup<'a> { + /// The specs that take part in item matching. + pub specs: Vec<RefSpecRef<'a>>, +} + +/// The outcome of any matching operation of a [`MatchGroup`]. +/// +/// It's used to validate and process the contained [mappings][Mapping]. +#[derive(Debug, Clone)] +pub struct Outcome<'spec, 'item> { + /// The match group that produced this outcome. + pub group: MatchGroup<'spec>, + /// The mappings derived from matching [items][Item]. + pub mappings: Vec<Mapping<'item, 'spec>>, +} + +/// An item to match, input to various matching operations. +#[derive(Debug, Copy, Clone)] +pub struct Item<'a> { + /// The full name of the references, like `refs/heads/main` + pub full_ref_name: &'a BStr, + /// The id that `full_ref_name` points to, which typically is a commit, but can also be a tag object (or anything else). + pub target: &'a oid, + /// The object an annotated tag is pointing to, if `target` is an annotated tag. + pub object: Option<&'a oid>, +} + +#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] +/// The source (or left-hand) side of a mapping, which references its name. +pub enum SourceRef<'a> { + /// A full reference name, which is expected to be valid. + /// + /// Validity, however, is not enforced here. + FullName(&'a BStr), + /// The name of an object that is expected to exist on the remote side. + /// Note that it might not be advertised by the remote but part of the object graph, + /// and thus gets sent in the pack. The server is expected to fail unless the desired + /// object is present but at some time it is merely a request by the user. + ObjectId(gix_hash::ObjectId), +} + +impl SourceRef<'_> { + /// Create a fully owned instance from this one. + pub fn to_owned(&self) -> Source { + match self { + SourceRef::ObjectId(id) => Source::ObjectId(*id), + SourceRef::FullName(name) => Source::FullName((*name).to_owned()), + } + } +} + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +/// The source (or left-hand) side of a mapping, which owns its name. +pub enum Source { + /// A full reference name, which is expected to be valid. + /// + /// Validity, however, is not enforced here. + FullName(BString), + /// The name of an object that is expected to exist on the remote side. + /// Note that it might not be advertised by the remote but part of the object graph, + /// and thus gets sent in the pack. The server is expected to fail unless the desired + /// object is present but at some time it is merely a request by the user. + ObjectId(gix_hash::ObjectId), +} + +impl std::fmt::Display for Source { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Source::FullName(name) => name.fmt(f), + Source::ObjectId(id) => id.fmt(f), + } + } +} + +/// A mapping from a remote to a local refs for fetches or local to remote refs for pushes. +/// +/// Mappings are like edges in a graph, initially without any constraints. +#[derive(Debug, Clone)] +pub struct Mapping<'a, 'b> { + /// The index into the initial `items` list that matched against a spec. + pub item_index: Option<usize>, + /// The name of the remote side for fetches or the local one for pushes that matched. + pub lhs: SourceRef<'a>, + /// The name of the local side for fetches or the remote one for pushes that corresponds to `lhs`, if available. + pub rhs: Option<Cow<'b, BStr>>, + /// The index of the matched ref-spec as seen from the match group. + pub spec_index: usize, +} + +impl std::hash::Hash for Mapping<'_, '_> { + fn hash<H: std::hash::Hasher>(&self, state: &mut H) { + self.lhs.hash(state); + self.rhs.hash(state); + } +} diff --git a/vendor/gix-refspec/src/match_group/util.rs b/vendor/gix-refspec/src/match_group/util.rs new file mode 100644 index 000000000..5339aef32 --- /dev/null +++ b/vendor/gix-refspec/src/match_group/util.rs @@ -0,0 +1,162 @@ +use std::{borrow::Cow, ops::Range}; + +use bstr::{BStr, BString, ByteSlice, ByteVec}; +use gix_hash::ObjectId; + +use crate::{match_group::Item, RefSpecRef}; + +/// A type keeping enough information about a ref-spec to be able to efficiently match it against multiple matcher items. +pub struct Matcher<'a> { + pub(crate) lhs: Option<Needle<'a>>, + pub(crate) rhs: Option<Needle<'a>>, +} + +impl<'a> Matcher<'a> { + /// Match `item` against this spec and return `(true, Some<rhs>)` to gain the other side of the match as configured, or `(true, None)` + /// if there was no `rhs`. + /// + /// This may involve resolving a glob with an allocation, as the destination is built using the matching portion of a glob. + pub fn matches_lhs(&self, item: Item<'_>) -> (bool, Option<Cow<'a, BStr>>) { + match (self.lhs, self.rhs) { + (Some(lhs), None) => (lhs.matches(item).is_match(), None), + (Some(lhs), Some(rhs)) => lhs.matches(item).into_match_outcome(rhs, item), + (None, None) | (None, Some(_)) => { + unreachable!("For all we know, the lefthand side is never empty. Push specs might change that.") + } + } + } +} + +#[derive(Debug, Copy, Clone)] +pub(crate) enum Needle<'a> { + FullName(&'a BStr), + PartialName(&'a BStr), + Glob { name: &'a BStr, asterisk_pos: usize }, + Object(ObjectId), +} + +enum Match { + /// There was no match. + None, + /// No additional data is provided as part of the match. + Normal, + /// The range of text to copy from the originating item name + GlobRange(Range<usize>), +} + +impl Match { + fn is_match(&self) -> bool { + !matches!(self, Match::None) + } + fn into_match_outcome<'a>(self, destination: Needle<'a>, item: Item<'_>) -> (bool, Option<Cow<'a, BStr>>) { + let arg = match self { + Match::None => return (false, None), + Match::Normal => None, + Match::GlobRange(range) => Some((range, item)), + }; + (true, destination.to_bstr_replace(arg).into()) + } +} + +impl<'a> Needle<'a> { + #[inline] + fn matches(&self, item: Item<'_>) -> Match { + match self { + Needle::FullName(name) => { + if *name == item.full_ref_name { + Match::Normal + } else { + Match::None + } + } + Needle::PartialName(name) => crate::spec::expand_partial_name(name, |expanded| { + (expanded == item.full_ref_name).then_some(Match::Normal) + }) + .unwrap_or(Match::None), + Needle::Glob { name, asterisk_pos } => { + match item.full_ref_name.get(..*asterisk_pos) { + Some(full_name_portion) if full_name_portion != name[..*asterisk_pos] => { + return Match::None; + } + None => return Match::None, + _ => {} + }; + let tail = &name[*asterisk_pos + 1..]; + if !item.full_ref_name.ends_with(tail) { + return Match::None; + } + let end = item.full_ref_name.len() - tail.len(); + Match::GlobRange(*asterisk_pos..end) + } + Needle::Object(id) => { + if *id == item.target { + return Match::Normal; + } + match item.object { + Some(object) if object == *id => Match::Normal, + _ => Match::None, + } + } + } + } + + fn to_bstr_replace(self, range: Option<(Range<usize>, Item<'_>)>) -> Cow<'a, BStr> { + match (self, range) { + (Needle::FullName(name), None) => Cow::Borrowed(name), + (Needle::PartialName(name), None) => Cow::Owned({ + let mut base: BString = "refs/".into(); + if !(name.starts_with(b"tags/") || name.starts_with(b"remotes/")) { + base.push_str("heads/"); + } + base.push_str(name); + base + }), + (Needle::Glob { name, asterisk_pos }, Some((range, item))) => { + let mut buf = Vec::with_capacity(name.len() + range.len() - 1); + buf.push_str(&name[..asterisk_pos]); + buf.push_str(&item.full_ref_name[range]); + buf.push_str(&name[asterisk_pos + 1..]); + Cow::Owned(buf.into()) + } + (Needle::Object(id), None) => { + let mut name = id.to_string(); + name.insert_str(0, "refs/heads/"); + Cow::Owned(name.into()) + } + (Needle::Glob { .. }, None) => unreachable!("BUG: no range provided for glob pattern"), + (_, Some(_)) => { + unreachable!("BUG: range provided even though needle wasn't a glob. Globs are symmetric.") + } + } + } + + pub fn to_bstr(self) -> Cow<'a, BStr> { + self.to_bstr_replace(None) + } +} + +impl<'a> From<&'a BStr> for Needle<'a> { + fn from(v: &'a BStr) -> Self { + if let Some(pos) = v.find_byte(b'*') { + Needle::Glob { + name: v, + asterisk_pos: pos, + } + } else if v.starts_with(b"refs/") { + Needle::FullName(v) + } else if let Ok(id) = gix_hash::ObjectId::from_hex(v) { + Needle::Object(id) + } else { + Needle::PartialName(v) + } + } +} + +impl<'a> From<RefSpecRef<'a>> for Matcher<'a> { + fn from(v: RefSpecRef<'a>) -> Self { + Matcher { + lhs: v.src.map(Into::into), + rhs: v.dst.map(Into::into), + } + } +} diff --git a/vendor/gix-refspec/src/match_group/validate.rs b/vendor/gix-refspec/src/match_group/validate.rs new file mode 100644 index 000000000..097a64587 --- /dev/null +++ b/vendor/gix-refspec/src/match_group/validate.rs @@ -0,0 +1,141 @@ +use std::collections::BTreeMap; + +use bstr::BString; + +use crate::{ + match_group::{Outcome, Source}, + RefSpec, +}; + +/// All possible issues found while validating matched mappings. +#[derive(Debug, PartialEq, Eq)] +pub enum Issue { + /// Multiple sources try to write the same destination. + /// + /// Note that this issue doesn't take into consideration that these sources might contain the same object behind a reference. + Conflict { + /// The unenforced full name of the reference to be written. + destination_full_ref_name: BString, + /// The list of sources that map to this destination. + sources: Vec<Source>, + /// The list of specs that caused the mapping conflict, each matching the respective one in `sources` to allow both + /// `sources` and `specs` to be zipped together. + specs: Vec<BString>, + }, +} + +impl std::fmt::Display for Issue { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Issue::Conflict { + destination_full_ref_name, + sources, + specs, + } => { + write!( + f, + "Conflicting destination {destination_full_ref_name:?} would be written by {}", + sources + .iter() + .zip(specs.iter()) + .map(|(src, spec)| format!("{src} ({spec:?})")) + .collect::<Vec<_>>() + .join(", ") + ) + } + } + } +} + +/// All possible fixes corrected while validating matched mappings. +#[derive(Debug, PartialEq, Eq, Clone)] +pub enum Fix { + /// Removed a mapping that contained a partial destination entirely. + MappingWithPartialDestinationRemoved { + /// The destination ref name that was ignored. + name: BString, + /// The spec that defined the mapping + spec: RefSpec, + }, +} + +/// The error returned [outcome validation][Outcome::validated()]. +#[derive(Debug)] +pub struct Error { + /// All issues discovered during validation. + pub issues: Vec<Issue>, +} + +impl std::fmt::Display for Error { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!( + f, + "Found {} {} the refspec mapping to be used: \n\t{}", + self.issues.len(), + if self.issues.len() == 1 { + "issue that prevents" + } else { + "issues that prevent" + }, + self.issues + .iter() + .map(|issue| issue.to_string()) + .collect::<Vec<_>>() + .join("\n\t") + ) + } +} + +impl std::error::Error for Error {} + +impl<'spec, 'item> Outcome<'spec, 'item> { + /// Validate all mappings or dissolve them into an error stating the discovered issues. + /// Return `(modified self, issues)` providing a fixed-up set of mappings in `self` with the fixed `issues` + /// provided as part of it. + /// Terminal issues are communicated using the [`Error`] type accordingly. + pub fn validated(mut self) -> Result<(Self, Vec<Fix>), Error> { + let mut sources_by_destinations = BTreeMap::new(); + for (dst, (spec_index, src)) in self + .mappings + .iter() + .filter_map(|m| m.rhs.as_ref().map(|dst| (dst.as_ref(), (m.spec_index, &m.lhs)))) + { + let sources = sources_by_destinations.entry(dst).or_insert_with(Vec::new); + if !sources.iter().any(|(_, lhs)| lhs == &src) { + sources.push((spec_index, src)) + } + } + let mut issues = Vec::new(); + for (dst, conflicting_sources) in sources_by_destinations.into_iter().filter(|(_, v)| v.len() > 1) { + issues.push(Issue::Conflict { + destination_full_ref_name: dst.to_owned(), + specs: conflicting_sources + .iter() + .map(|(spec_idx, _)| self.group.specs[*spec_idx].to_bstring()) + .collect(), + sources: conflicting_sources.into_iter().map(|(_, src)| src.to_owned()).collect(), + }) + } + if !issues.is_empty() { + Err(Error { issues }) + } else { + let mut fixed = Vec::new(); + let group = &self.group; + self.mappings.retain(|m| match m.rhs.as_ref() { + Some(dst) => { + if dst.starts_with(b"refs/") || dst.as_ref() == "HEAD" { + true + } else { + fixed.push(Fix::MappingWithPartialDestinationRemoved { + name: dst.as_ref().to_owned(), + spec: group.specs[m.spec_index].to_owned(), + }); + false + } + } + None => true, + }); + Ok((self, fixed)) + } + } +} |