Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_text/src/glob.rs

14.5 KiB, 1 run

created by r1870400018:20952, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Shell-style path globbing.
2//!
3//! `*` matches any run of characters within one path segment, `?` matches one such character,
4//! `**` matches any number of whole segments including none, `[abc]` and `[a-z]` and `[!abc]`
5//! match one character from a set, and `{a,b}` offers alternatives.
6//!
7//! A pattern with no `/` in it is matched against the file's name alone, which is what makes
8//! `*.rs` mean "any Rust file anywhere" -- the convention every search tool uses. A pattern that
9//! does contain a `/` is matched against the whole relative path.
10
11use oxedyne_fe2o3_core::prelude::*;
12
13
14/// The most alternatives a pattern's braces may expand to.
15///
16/// Nested braces multiply, so `{a,b}{c,d}{e,f}` is eight; the cap stops a pattern from becoming a
17/// denial of service against the process reading it.
18const MAX_ALTS: usize = 256;
19
20
21/// One piece of a single path segment.
22#[derive(Clone, Debug, Eq, PartialEq)]
23enum Part {
24 /// Literal text.
25 Lit(String),
26 /// `*`: any run of characters, `/` excepted.
27 Star,
28 /// `?`: exactly one character, `/` excepted.
29 One,
30 /// `[...]`: one character from a set, which may be negated.
31 Set {
32 /// Whether the set is negated, `[!...]` or `[^...]`.
33 neg: bool,
34 /// Single characters the set admits.
35 chars: Vec<char>,
36 /// Inclusive ranges the set admits.
37 ranges: Vec<(char, char)>,
38 },
39}
40
41/// One path segment of a pattern.
42#[derive(Clone, Debug, Eq, PartialEq)]
43enum Seg {
44 /// `**`: any number of whole segments, including none.
45 Deep,
46 /// An ordinary segment, matched piecewise.
47 Parts(Vec<Part>),
48}
49
50/// A compiled glob pattern.
51#[derive(Clone, Debug)]
52pub struct Glob {
53 /// One segment list per brace alternative; a path matching any of them matches the glob.
54 alts: Vec<Vec<Seg>>,
55 /// Whether the pattern named a path rather than a file name.
56 on_path: bool,
57 /// The pattern as written, for error messages.
58 src: String,
59}
60
61impl Glob {
62
63 /// Compile a glob pattern.
64 ///
65 /// # Arguments
66 /// * `pattern` - The pattern, e.g. `**/*_test.rs` or `*.{md,typ}`.
67 ///
68 /// # Returns
69 /// The compiled glob, or an error naming what could not be read.
70 pub fn new(pattern: &str) -> Outcome<Self> {
71 if pattern.trim().is_empty() {
72 return Err(err!("glob: the pattern is empty."; Invalid, Input, Missing));
73 }
74 let expanded = res!(expand_braces(pattern));
75 let on_path = pattern.contains('/');
76 let mut alts = Vec::with_capacity(expanded.len());
77 for e in &expanded {
78 alts.push(res!(compile(e)));
79 }
80 Ok(Self { alts, on_path, src: pattern.to_string() })
81 }
82
83 /// The pattern as it was written.
84 pub fn as_str(&self) -> &str {
85 &self.src
86 }
87
88 /// Whether `path` matches.
89 ///
90 /// # Arguments
91 /// * `path` - A relative path with `/` separators, e.g. `src/wasm/opfs.rs`.
92 pub fn matches(&self, path: &str) -> bool {
93 let subject = if self.on_path {
94 path.trim_start_matches("./")
95 } else {
96 // A bare pattern names a file, so only the last segment is offered to it.
97 match path.rsplit('/').next() {
98 Some(name) => name,
99 None => path,
100 }
101 };
102 let segs: Vec<&str> = subject.split('/').filter(|s| !s.is_empty()).collect();
103 for alt in &self.alts {
104 if seg_match(alt, &segs) {
105 return true;
106 }
107 }
108 false
109 }
110}
111
112/// Whether the pattern segments match the path segments, `**` spanning as many as it needs.
113///
114/// # Arguments
115/// * `pat` - The pattern's segments.
116/// * `path` - The path's segments.
117fn seg_match(pat: &[Seg], path: &[&str]) -> bool {
118 match pat.split_first() {
119 None => path.is_empty(),
120 Some((Seg::Deep, rest)) => {
121 // `**` takes nothing, then one segment, then two, until something fits.
122 for take in 0..=path.len() {
123 if seg_match(rest, &path[take..]) {
124 return true;
125 }
126 }
127 false
128 }
129 Some((Seg::Parts(parts), rest)) => {
130 match path.split_first() {
131 Some((head, tail)) => part_match(parts, &head.chars().collect::<Vec<char>>())
132 && seg_match(rest, tail),
133 None => false,
134 }
135 }
136 }
137}
138
139/// Whether one segment's parts match one segment's characters.
140///
141/// # Arguments
142/// * `parts` - The pattern pieces.
143/// * `seg` - The segment, as characters.
144fn part_match(parts: &[Part], seg: &[char]) -> bool {
145 match parts.split_first() {
146 None => seg.is_empty(),
147 Some((Part::Star, rest)) => {
148 for take in 0..=seg.len() {
149 if part_match(rest, &seg[take..]) {
150 return true;
151 }
152 }
153 false
154 }
155 Some((Part::One, rest)) => !seg.is_empty() && part_match(rest, &seg[1..]),
156 Some((Part::Set { neg, chars, ranges }, rest)) => {
157 match seg.first() {
158 None => false,
159 Some(&c) => {
160 let mut hit = chars.contains(&c);
161 if !hit {
162 for (a, b) in ranges {
163 if c >= *a && c <= *b {
164 hit = true;
165 break;
166 }
167 }
168 }
169 (hit != *neg) && part_match(rest, &seg[1..])
170 }
171 }
172 }
173 Some((Part::Lit(text), rest)) => {
174 let want: Vec<char> = text.chars().collect();
175 seg.len() >= want.len()
176 && seg[..want.len()] == want[..]
177 && part_match(rest, &seg[want.len()..])
178 }
179 }
180}
181
182/// Expand `{a,b}` alternatives into one pattern each, leftmost group first.
183///
184/// # Arguments
185/// * `pattern` - The pattern, possibly with braces.
186fn expand_braces(pattern: &str) -> Outcome<Vec<String>> {
187 let chars: Vec<char> = pattern.chars().collect();
188 // Find the first unescaped `{` and its matching `}`.
189 let mut open = None;
190 let mut depth = 0usize;
191 let mut close = None;
192 let mut i = 0usize;
193 while i < chars.len() {
194 match chars[i] {
195 '\\' => { i += 1; }
196 '{' => {
197 if open.is_none() {
198 open = Some(i);
199 }
200 depth += 1;
201 }
202 '}' => {
203 if depth > 0 {
204 depth -= 1;
205 if depth == 0 {
206 close = Some(i);
207 break;
208 }
209 }
210 }
211 _ => {}
212 }
213 i += 1;
214 }
215 let (o, c) = match (open, close) {
216 (Some(o), Some(c)) => (o, c),
217 (Some(_), None) => return Err(err!(
218 "glob '{}': unclosed '{{'.", pattern; Invalid, Input)),
219 _ => return Ok(vec![pattern.to_string()]),
220 };
221 // Split the body on top-level commas.
222 let mut bodies = Vec::new();
223 let mut cur = String::new();
224 let mut d = 0usize;
225 let mut j = o + 1;
226 while j < c {
227 let ch = chars[j];
228 match ch {
229 '{' => { d += 1; cur.push(ch); }
230 '}' => { d -= 1; cur.push(ch); }
231 ',' if d == 0 => { bodies.push(std::mem::take(&mut cur)); }
232 _ => cur.push(ch),
233 }
234 j += 1;
235 }
236 bodies.push(cur);
237 let head: String = chars[..o].iter().collect();
238 let tail: String = chars[c + 1..].iter().collect();
239 let mut out = Vec::new();
240 for b in bodies {
241 for rest in res!(expand_braces(&fmt!("{}{}{}", head, b, tail))) {
242 if out.len() >= MAX_ALTS {
243 return Err(err!(
244 "glob '{}': braces expand to more than {} alternatives.", pattern, MAX_ALTS;
245 Excessive, Input));
246 }
247 out.push(rest);
248 }
249 }
250 Ok(out)
251}
252
253/// Compile one brace-free pattern into segments.
254///
255/// # Arguments
256/// * `pattern` - The pattern, with no `{}` left in it.
257fn compile(pattern: &str) -> Outcome<Vec<Seg>> {
258 let mut segs = Vec::new();
259 for raw in pattern.trim_start_matches("./").split('/') {
260 if raw.is_empty() {
261 continue; // a doubled or trailing slash names no segment
262 }
263 if raw == "**" {
264 segs.push(Seg::Deep);
265 continue;
266 }
267 segs.push(Seg::Parts(res!(compile_seg(raw, pattern))));
268 }
269 if segs.is_empty() {
270 return Err(err!("glob '{}': names no path.", pattern; Invalid, Input));
271 }
272 Ok(segs)
273}
274
275/// Compile one segment into its parts.
276///
277/// # Arguments
278/// * `seg` - The segment source.
279/// * `whole` - The whole pattern, for error messages.
280fn compile_seg(seg: &str, whole: &str) -> Outcome<Vec<Part>> {
281 let chars: Vec<char> = seg.chars().collect();
282 let mut parts: Vec<Part> = Vec::new();
283 let mut lit = String::new();
284 let mut i = 0usize;
285 while i < chars.len() {
286 match chars[i] {
287 '*' => {
288 if !lit.is_empty() {
289 parts.push(Part::Lit(std::mem::take(&mut lit)));
290 }
291 // `***` and `a**b` are all just "any run within the segment".
292 while i < chars.len() && chars[i] == '*' {
293 i += 1;
294 }
295 parts.push(Part::Star);
296 }
297 '?' => {
298 if !lit.is_empty() {
299 parts.push(Part::Lit(std::mem::take(&mut lit)));
300 }
301 parts.push(Part::One);
302 i += 1;
303 }
304 '[' => {
305 if !lit.is_empty() {
306 parts.push(Part::Lit(std::mem::take(&mut lit)));
307 }
308 let (part, next) = res!(compile_set(&chars, i, whole));
309 parts.push(part);
310 i = next;
311 }
312 '\\' if i + 1 < chars.len() => {
313 lit.push(chars[i + 1]);
314 i += 2;
315 }
316 c => { lit.push(c); i += 1; }
317 }
318 }
319 if !lit.is_empty() {
320 parts.push(Part::Lit(lit));
321 }
322 Ok(parts)
323}
324
325/// Compile a `[...]` set beginning at `start`, returning it and the index after the `]`.
326///
327/// # Arguments
328/// * `chars` - The segment's characters.
329/// * `start` - Index of the `[`.
330/// * `whole` - The whole pattern, for error messages.
331fn compile_set(chars: &[char], start: usize, whole: &str) -> Outcome<(Part, usize)> {
332 let mut i = start + 1;
333 let neg = if chars.get(i) == Some(&'!') || chars.get(i) == Some(&'^') {
334 i += 1;
335 true
336 } else {
337 false
338 };
339 let mut set_chars = Vec::new();
340 let mut ranges = Vec::new();
341 // A `]` first thing is a literal `]`, as the shell has it.
342 if chars.get(i) == Some(&']') {
343 set_chars.push(']');
344 i += 1;
345 }
346 loop {
347 let c = match chars.get(i) {
348 Some(']') => { i += 1; break; }
349 Some(&c) => c,
350 None => return Err(err!("glob '{}': unclosed '['.", whole; Invalid, Input)),
351 };
352 i += 1;
353 if chars.get(i) == Some(&'-') && chars.get(i + 1).map(|x| *x != ']').unwrap_or(false) {
354 let hi = match chars.get(i + 1) {
355 Some(&h) => h,
356 None => return Err(err!("glob '{}': unclosed '['.", whole; Invalid, Input)),
357 };
358 if hi < c {
359 return Err(err!(
360 "glob '{}': the range '{}-{}' runs backwards.", whole, c, hi; Invalid, Input));
361 }
362 ranges.push((c, hi));
363 i += 2;
364 } else {
365 set_chars.push(c);
366 }
367 }
368 if set_chars.is_empty() && ranges.is_empty() {
369 return Err(err!("glob '{}': '[]' admits nothing.", whole; Invalid, Input));
370 }
371 Ok((Part::Set { neg, chars: set_chars, ranges }, i))
372}
373
374
375#[cfg(test)]
376mod tests {
377 use super::*;
378
379 /// Compile and match, so a test reads as one line.
380 fn m(pat: &str, path: &str) -> bool {
381 match Glob::new(pat) {
382 Ok(g) => g.matches(path),
383 Err(e) => panic!("compiling '{}': {}", pat, e),
384 }
385 }
386
387 #[test]
388 fn test_a_bare_pattern_matches_the_file_name_anywhere() {
389 assert!(m("*.rs", "src/wasm/opfs.rs"));
390 assert!(m("*.rs", "opfs.rs"));
391 assert!(!m("*.rs", "src/wasm/opfs.js"));
392 assert!(m("Cargo.toml", "a/b/Cargo.toml"));
393 }
394
395 #[test]
396 fn test_a_pattern_with_a_slash_matches_the_whole_path() {
397 assert!(m("src/*.rs", "src/tools.rs"));
398 assert!(!m("src/*.rs", "src/wasm/opfs.rs"), "'*' must not cross a '/'");
399 assert!(m("src/**/*.rs", "src/wasm/opfs.rs"));
400 assert!(m("src/**/*.rs", "src/tools.rs"), "'**' must be able to take no segments at all");
401 assert!(m("**/*_test.rs", "a/b/c/thing_test.rs"));
402 assert!(m("**/*_test.rs", "thing_test.rs"));
403 }
404
405 #[test]
406 fn test_question_and_sets() {
407 assert!(m("?.rs", "a.rs"));
408 assert!(!m("?.rs", "ab.rs"));
409 assert!(m("[abc]*.rs", "b_thing.rs"));
410 assert!(!m("[abc]*.rs", "z_thing.rs"));
411 assert!(m("[a-z][0-9].txt", "a1.txt"));
412 assert!(m("[!x]*.rs", "a.rs"));
413 assert!(!m("[!x]*.rs", "x.rs"));
414 }
415
416 #[test]
417 fn test_braces_offer_alternatives() {
418 assert!(m("*.{md,typ}", "notes.md"));
419 assert!(m("*.{md,typ}", "notes.typ"));
420 assert!(!m("*.{md,typ}", "notes.txt"));
421 assert!(m("src/{a,b}/*.rs", "src/b/x.rs"));
422 assert!(m("{a,b}{c,d}.rs", "ad.rs"));
423 }
424
425 #[test]
426 fn test_a_leading_dot_slash_is_not_a_segment() {
427 assert!(m("src/*.rs", "./src/tools.rs"));
428 assert!(m("./src/*.rs", "src/tools.rs"));
429 }
430
431 #[test]
432 fn test_bad_patterns_are_refused_with_a_reason() {
433 for (pat, want) in [
434 ("a[bc", "unclosed '['"),
435 ("a{b,c", "unclosed '{'"),
436 ("[z-a]", "runs backwards"),
437 ("", "empty"),
438 ] {
439 let e = Glob::new(pat).expect_err(&fmt!("'{}' should not compile", pat));
440 let msg = fmt!("{}", e);
441 assert!(msg.contains(want), "'{}' should say '{}', said: {}", pat, want, msg);
442 }
443 }
444
445 #[test]
446 fn test_a_dotted_name_is_matched_like_any_other() {
447 // Unlike the shell, a leading dot is not special here: a search tool that hid dotfiles
448 // from an explicit pattern would be answering a question nobody asked.
449 assert!(m("*.yml", ".github/workflows/ci.yml"));
450 assert!(m(".github/**", ".github/workflows/ci.yml"));
451 }
452}