git-ents.gitmain
⌘K
foforge

crates/kernel/ents-query/src/pattern.rs

pattern.rs243 lines · 8.1 KB · rusthistorycomment on this file
1//! Refname patterns and the static footprint (`query.footprint`).
2
3use gix::refs::FullNameRef;
4
5use crate::error::ParseError;
6
7/// A refname glob: literal bytes plus `*` wildcards, where each `*`
8/// matches any run of characters including `/` (the same shape git
9/// refspecs and the spec's own examples use — `refs/heads/*` matches
10/// `refs/heads/wip/x`).
11///
12/// # Examples
13///
14/// ```
15/// use ents_query::RefPattern;
16///
17/// let pattern = RefPattern::new("refs/heads/*").expect("valid");
18/// let name: gix::refs::FullName = "refs/heads/wip/x".try_into().expect("valid");
19/// assert!(pattern.matches(name.as_ref()));
20///
21/// let other: gix::refs::FullName = "refs/tags/v1".try_into().expect("valid");
22/// assert!(!pattern.matches(other.as_ref()));
23/// ```
24#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
25pub struct RefPattern(String);
26
27impl RefPattern {
28 /// Validate and wrap a pattern.
29 ///
30 /// # Errors
31 ///
32 /// [`ParseError::BadPattern`] when the pattern is empty or contains
33 /// bytes no refname can carry (whitespace, `\`, control bytes, the
34 /// query grammar's own metacharacters, `..`, or `//`).
35 pub fn new(pattern: impl Into<String>) -> Result<Self, ParseError> {
36 let pattern = pattern.into();
37 let bad = |why: &'static str| ParseError::BadPattern {
38 pattern: pattern.clone(),
39 why,
40 };
41 if pattern.is_empty() {
42 return Err(bad("empty pattern"));
43 }
44 if pattern
45 .bytes()
46 .any(|b| b.is_ascii_whitespace() || b.is_ascii_control())
47 {
48 return Err(bad("whitespace or control byte"));
49 }
50 if pattern.bytes().any(|b| b"\\()|&,?[".contains(&b)) {
51 return Err(bad("byte a refname cannot carry"));
52 }
53 if pattern.contains("..") || pattern.contains("//") {
54 return Err(bad("empty or dot-dot path segment"));
55 }
56 if pattern.starts_with('/') || pattern.ends_with('/') {
57 return Err(bad("leading or trailing slash"));
58 }
59 Ok(Self(pattern))
60 }
61
62 /// The pattern text.
63 ///
64 /// # Examples
65 ///
66 /// ```
67 /// use ents_query::RefPattern;
68 ///
69 /// assert_eq!(RefPattern::new("refs/tags/v*").expect("valid").as_str(), "refs/tags/v*");
70 /// ```
71 #[must_use]
72 pub fn as_str(&self) -> &str {
73 &self.0
74 }
75
76 /// Whether `name` matches this pattern.
77 #[must_use]
78 pub fn matches(&self, name: &FullNameRef) -> bool {
79 self.matches_str(&name.as_bstr().to_string())
80 }
81
82 /// [`RefPattern::matches`] over a plain string refname.
83 #[must_use]
84 pub(crate) fn matches_str(&self, name: &str) -> bool {
85 glob_match(self.0.as_bytes(), name.as_bytes())
86 }
87
88 /// The literal bytes before the first `*` (the whole pattern when
89 /// there is no wildcard).
90 pub(crate) fn literal_prefix(&self) -> &str {
91 self.0.split('*').next().unwrap_or(&self.0)
92 }
93
94 /// Whether some refname starting with `prefix` could match this
95 /// pattern — the conservative overlap test `query.meta` needs to
96 /// keep effect-written namespaces unreachable.
97 pub(crate) fn may_match_with_prefix(&self, prefix: &str) -> bool {
98 may_match(self.0.as_bytes(), prefix.as_bytes())
99 }
100}
101
102impl std::fmt::Display for RefPattern {
103 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
104 f.write_str(&self.0)
105 }
106}
107
108/// Classic wildcard match: `*` matches any run (including `/`),
109/// everything else is literal. Iterative two-pointer with backtracking.
110fn glob_match(pattern: &[u8], text: &[u8]) -> bool {
111 let (mut p, mut t) = (0usize, 0usize);
112 let (mut star, mut mark) = (None::<usize>, 0usize);
113 while t < text.len() {
114 match pattern.get(p) {
115 Some(b'*') => {
116 star = Some(p);
117 mark = t;
118 p = p.saturating_add(1);
119 }
120 Some(&c) if text.get(t) == Some(&c) => {
121 p = p.saturating_add(1);
122 t = t.saturating_add(1);
123 }
124 _ => match star {
125 Some(s) => {
126 p = s.saturating_add(1);
127 mark = mark.saturating_add(1);
128 t = mark;
129 }
130 None => return false,
131 },
132 }
133 }
134 while pattern.get(p) == Some(&b'*') {
135 p = p.saturating_add(1);
136 }
137 p == pattern.len()
138}
139
140/// Whether the pattern could match some string that starts with
141/// `prefix`. `true` whenever the pattern can consume all of `prefix`
142/// (whatever pattern remains can always match its own literal tail).
143fn may_match(pattern: &[u8], prefix: &[u8]) -> bool {
144 let Some(rest) = prefix.split_first() else {
145 return true;
146 };
147 match pattern.split_first() {
148 None => false,
149 Some((b'*', tail)) => (0..=prefix.len()).any(|k| {
150 prefix
151 .get(k..)
152 .is_some_and(|suffix| may_match(tail, suffix))
153 }),
154 Some((&c, tail)) => c == *rest.0 && may_match(tail, rest.1),
155 }
156}
157
158/// The set of refname patterns a query depends on, extractable from its
159/// syntax tree alone (`query.footprint`) — what lets `receive` map one
160/// ref transition to the affected queries without re-scanning every
161/// effect on every push.
162///
163/// # Examples
164///
165/// ```
166/// use ents_query::Query;
167///
168/// let query: Query = "rev(refs/heads/main) & results(unit, pass)".parse().expect("valid");
169/// let footprint = query.footprint();
170///
171/// let main: gix::refs::FullName = "refs/heads/main".try_into().expect("valid");
172/// let result: gix::refs::FullName = "refs/meta/results/unit/abc".try_into().expect("valid");
173/// let other: gix::refs::FullName = "refs/heads/dev".try_into().expect("valid");
174/// assert!(footprint.matches(main.as_ref()));
175/// assert!(footprint.matches(result.as_ref()));
176/// assert!(!footprint.matches(other.as_ref()));
177/// ```
178// @relation(query.footprint, scope=file)
179#[derive(Debug, Clone, PartialEq, Eq)]
180pub struct Footprint(Vec<RefPattern>);
181
182impl Footprint {
183 pub(crate) fn from_patterns(mut patterns: Vec<RefPattern>) -> Self {
184 patterns.sort();
185 patterns.dedup();
186 Self(patterns)
187 }
188
189 /// The patterns, sorted and deduplicated.
190 #[must_use]
191 pub fn patterns(&self) -> &[RefPattern] {
192 &self.0
193 }
194
195 /// Whether a transition on `name` can affect the query's set.
196 #[must_use]
197 pub fn matches(&self, name: &FullNameRef) -> bool {
198 let text = name.as_bstr().to_string();
199 self.0.iter().any(|p| p.matches_str(&text))
200 }
201}
202
203#[cfg(test)]
204mod tests {
205 #![expect(clippy::expect_used, reason = "unit test")]
206
207 use rstest::rstest;
208
209 use super::*;
210
211 #[rstest]
212 #[case::exact("refs/heads/main", "refs/heads/main", true)]
213 #[case::star_crosses_slashes("refs/heads/*", "refs/heads/wip/x", true)]
214 #[case::mid_star("refs/tags/v*-rc", "refs/tags/v1.2-rc", true)]
215 #[case::two_stars("refs/*/unit/*", "refs/meta/results/unit/abc", true)]
216 #[case::suffix_must_still_match("refs/*/unit", "refs/meta/results/unit/abc", false)]
217 #[case::no_match("refs/heads/*", "refs/tags/v1", false)]
218 #[case::literal_shorter_than_text("refs/heads", "refs/heads/main", false)]
219 // @relation(query.footprint, scope=function, role=Verifies)
220 fn glob_matching_matches_git_style_star_runs(
221 #[case] pattern: &str,
222 #[case] name: &str,
223 #[case] expected: bool,
224 ) {
225 let pattern = RefPattern::new(pattern).expect("valid");
226 assert_eq!(pattern.matches_str(name), expected);
227 }
228
229 #[rstest]
230 #[case::wildcard_reaches_into_prefix("refs/meta/*", "refs/meta/results/", true)]
231 #[case::exact_inside_prefix("refs/meta/results/unit/abc", "refs/meta/results/", true)]
232 #[case::disjoint("refs/meta/issues/*", "refs/meta/results/", false)]
233 #[case::prefix_of_the_prefix("refs/meta/res*", "refs/meta/results/", true)]
234 // @relation(query.meta, scope=function, role=Verifies)
235 fn prefix_overlap_is_detected_conservatively(
236 #[case] pattern: &str,
237 #[case] prefix: &str,
238 #[case] expected: bool,
239 ) {
240 let pattern = RefPattern::new(pattern).expect("valid");
241 assert_eq!(pattern.may_match_with_prefix(prefix), expected);
242 }
243}