Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_file/src/glob.rs

14.3 KiB, 44 runs

created by r1870400018:20063, 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//! Glob matching over byte paths, in the shapes git's ignore files use.
2//!
3//! A [`Glob`] is one compiled pattern and an [`IgnoreFile`] is an ordered list
4//! of them, parsed from the byte content of a `.gitignore`-shaped file. The
5//! semantics are git's:
6//!
7//! - `*` matches any run of bytes within one path component, `?` matches one
8//! byte within a component, and a character class `[a-z]` (negated with a
9//! leading `!` or `^`) matches one byte. None of these ever matches a `/`.
10//! - A component that is exactly `**` spans any number of components: a leading
11//! `**/` matches at any depth, a trailing `/**` matches everything inside a
12//! directory, and `a/**/b` matches zero or more directories between. A `**`
13//! sitting among other bytes in a component is an ordinary `*`.
14//! - A pattern containing a `/` anywhere but its end is anchored to the
15//! directory the ignore file sits in; one without matches at any depth. A
16//! leading `/` anchors without contributing a component.
17//! - A trailing `/` makes the pattern match directories only.
18//! - A leading `!` negates: a path the pattern matches is re-included. The
19//! *last* matching pattern in an [`IgnoreFile`] decides.
20//! - `\` escapes the byte after it, so `\*` is a literal asterisk and `\!` at
21//! the start of a line is a literal exclamation mark.
22//! - In a file, blank lines are nothing and lines beginning `#` are comments.
23//! Trailing spaces are trimmed unless escaped with `\`.
24//!
25//! # Paths are bytes
26//!
27//! A path here is a `&[u8]` of components joined by `/`, relative to the
28//! directory the rules speak from, with no leading or trailing slash. Matching
29//! is byte-for-byte: a pattern applies to a path that is not UTF-8 exactly as
30//! it applies to one that is, with `?` and `[a-z]` consuming one *byte*, not
31//! one character. That is the only footing on which a rule can treat every
32//! legal path, since a filesystem name need not be text.
33//!
34//! Two shapes are deliberately absent: POSIX named classes (`[[:alpha:]]`) are
35//! not recognised, and a `/` cannot appear inside a character class or be
36//! escaped, because the pattern is split on every `/` before anything else is
37//! read. An unclosed `[` is a literal `[`, as it is a match failure in git.
38//!
39//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
40//! Anthropic Claude
41
42use oxedyne_fe2o3_core::prelude::*;
43
44
45/// One token of a compiled pattern, within a single path component.
46#[derive(Clone, Debug, PartialEq, Eq)]
47enum Tok {
48 Lit(u8), // one literal byte
49 Any, // `?`: exactly one byte
50 Star, // `*`: any run of bytes, including none
51 // `[...]`: one byte drawn from, or kept out of, a set of ranges.
52 Class {
53 negated: bool, // the class began `[!` or `[^`
54 ranges: Vec<(u8, u8)>, // inclusive; a lone member is a range of one
55 },
56}
57
58/// One component of a compiled pattern.
59#[derive(Clone, Debug, PartialEq, Eq)]
60enum Comp {
61 Globstar, // a component that was exactly `**`: any number of path components
62 One(Vec<Tok>), // an ordinary component, matched against exactly one path component
63}
64
65/// One compiled ignore pattern.
66///
67/// Compile with [`Glob::new`], ask with [`Glob::matches`]. A `Glob` carries its
68/// own negation flag but does not apply it: negation only means something in
69/// the ordered context of an [`IgnoreFile`], which is where it is read.
70#[derive(Clone, Debug)]
71pub struct Glob {
72 negated: bool, // the pattern began with `!`
73 dir_only: bool, // the pattern ended with `/`, so directories only
74 // A leading Comp::Globstar stands in for an unanchored pattern's freedom to
75 // match at any depth.
76 comps: Vec<Comp>,
77}
78
79impl Glob {
80
81 /// Compiles one pattern, as written on one line of an ignore file.
82 ///
83 /// The line must already be free of comments and trailing unescaped spaces,
84 /// which are the file's business rather than the pattern's; see
85 /// [`IgnoreFile::parse`]. A line that is empty, or empty once its `!` and
86 /// `/` dressing is removed, is an error, since it can match nothing.
87 pub fn new(line: &[u8]) -> Outcome<Self> {
88 let mut rest = line;
89 let mut negated = false;
90 if rest.first() == Some(&b'!') {
91 negated = true;
92 rest = &rest[1..];
93 }
94 let mut dir_only = false;
95 if rest.last() == Some(&b'/') {
96 dir_only = true;
97 rest = &rest[..rest.len() - 1];
98 }
99 // A leading slash anchors and says nothing else. Anchoring is otherwise
100 // decided by whether a slash survives inside the pattern.
101 let anchored = if rest.first() == Some(&b'/') {
102 rest = &rest[1..];
103 true
104 } else {
105 rest.contains(&b'/')
106 };
107 if rest.is_empty() {
108 return Err(err!(
109 "The pattern {:?} has no content to match a path against.",
110 String::from_utf8_lossy(line);
111 Invalid, Input));
112 }
113 let mut comps = Vec::new();
114 if !anchored {
115 comps.push(Comp::Globstar);
116 }
117 for part in rest.split(|b| *b == b'/') {
118 if part == b"**" {
119 comps.push(Comp::Globstar);
120 } else {
121 comps.push(Comp::One(Self::tokens(part)));
122 }
123 }
124 Ok(Self { negated, dir_only, comps })
125 }
126
127 pub fn is_negated(&self) -> bool {
128 self.negated
129 }
130
131 pub fn is_dir_only(&self) -> bool {
132 self.dir_only
133 }
134
135 /// Reports whether a path matches, where `is_dir` says what the path names.
136 ///
137 /// The path is relative, `/`-joined, with no leading or trailing slash. A
138 /// directory-only pattern refuses anything that is not a directory; it does
139 /// not by itself speak for the files beneath, which is the business of
140 /// [`IgnoreFile::excludes`].
141 pub fn matches(&self, path: &[u8], is_dir: bool) -> bool {
142 if self.dir_only && !is_dir {
143 return false;
144 }
145 if path.is_empty() {
146 return false;
147 }
148 let parts: Vec<&[u8]> = path.split(|b| *b == b'/').collect();
149 Self::match_comps(&self.comps, &parts)
150 }
151
152 fn match_comps(comps: &[Comp], parts: &[&[u8]]) -> bool {
153 match comps.first() {
154 None => parts.is_empty(),
155 Some(Comp::Globstar) => {
156 if comps.len() == 1 {
157 // A trailing `**` names what is *inside*: it must consume
158 // at least one component, so `a/**` matches `a/b` and not
159 // `a` itself.
160 return !parts.is_empty();
161 }
162 for i in 0..=parts.len() {
163 if Self::match_comps(&comps[1..], &parts[i..]) {
164 return true;
165 }
166 }
167 false
168 },
169 Some(Comp::One(toks)) => match parts.first() {
170 None => false,
171 Some(part) => Self::match_toks(toks, part)
172 && Self::match_comps(&comps[1..], &parts[1..]),
173 },
174 }
175 }
176
177 fn match_toks(toks: &[Tok], s: &[u8]) -> bool {
178 match toks.first() {
179 None => s.is_empty(),
180 Some(Tok::Star) => {
181 for i in 0..=s.len() {
182 if Self::match_toks(&toks[1..], &s[i..]) {
183 return true;
184 }
185 }
186 false
187 },
188 Some(Tok::Any) => !s.is_empty()
189 && Self::match_toks(&toks[1..], &s[1..]),
190 Some(Tok::Lit(b)) => s.first() == Some(b)
191 && Self::match_toks(&toks[1..], &s[1..]),
192 Some(Tok::Class { negated, ranges }) => match s.first() {
193 None => false,
194 Some(c) => {
195 let inside = ranges.iter().any(|(lo, hi)| lo <= c && c <= hi);
196 inside != *negated && Self::match_toks(&toks[1..], &s[1..])
197 },
198 },
199 }
200 }
201
202 fn tokens(part: &[u8]) -> Vec<Tok> {
203 let mut toks = Vec::new();
204 let mut i = 0;
205 while i < part.len() {
206 match part[i] {
207 b'\\' if i + 1 < part.len() => {
208 toks.push(Tok::Lit(part[i + 1]));
209 i += 2;
210 },
211 b'*' => {
212 // A run of asterisks that is not a whole component is one
213 // ordinary star, as it is in git.
214 if toks.last() != Some(&Tok::Star) {
215 toks.push(Tok::Star);
216 }
217 i += 1;
218 },
219 b'?' => {
220 toks.push(Tok::Any);
221 i += 1;
222 },
223 b'[' => match Self::class(&part[i..]) {
224 Some((tok, used)) => {
225 toks.push(tok);
226 i += used;
227 },
228 // An unclosed class is a literal bracket.
229 None => {
230 toks.push(Tok::Lit(b'['));
231 i += 1;
232 },
233 },
234 b => {
235 toks.push(Tok::Lit(b));
236 i += 1;
237 },
238 }
239 }
240 toks
241 }
242
243 /// The `usize` is how many bytes the class took; nothing where it never
244 /// closes.
245 fn class(s: &[u8]) -> Option<(Tok, usize)> {
246 let mut i = 1; // Past the opening bracket.
247 let mut negated = false;
248 if i < s.len() && (s[i] == b'!' || s[i] == b'^') {
249 negated = true;
250 i += 1;
251 }
252 let mut ranges = Vec::new();
253 let mut first = true;
254 while i < s.len() {
255 let b = s[i];
256 // A closing bracket as the very first member is a literal.
257 if b == b']' && !first {
258 return Some((Tok::Class { negated, ranges }, i + 1));
259 }
260 first = false;
261 let lo = if b == b'\\' && i + 1 < s.len() {
262 i += 1;
263 s[i]
264 } else {
265 b
266 };
267 // A dash with a member on each side is a range; anywhere else it is
268 // itself.
269 if i + 2 < s.len() && s[i + 1] == b'-' && s[i + 2] != b']' {
270 let hb = s[i + 2];
271 let hi = if hb == b'\\' && i + 3 < s.len() {
272 i += 1;
273 s[i + 2]
274 } else {
275 hb
276 };
277 ranges.push((lo, hi));
278 i += 3;
279 } else {
280 ranges.push((lo, lo));
281 i += 1;
282 }
283 }
284 None
285 }
286}
287
288
289/// An ordered list of patterns, as a `.gitignore`-shaped file holds them.
290///
291/// Parse with [`IgnoreFile::parse`]. The questions it answers are
292/// [`IgnoreFile::ignores`], which applies last-match-wins to one path, and
293/// [`IgnoreFile::excludes`], which also holds a path to git's rule that nothing
294/// inside an ignored directory can be re-included.
295#[derive(Clone, Debug, Default)]
296pub struct IgnoreFile {
297 rules: Vec<Glob>, // in the order the file gives them
298}
299
300impl IgnoreFile {
301
302 /// Parses the byte content of an ignore file.
303 ///
304 /// Lines are split on `\n`, with a trailing `\r` dropped so a file written
305 /// on Windows reads the same. Blank lines and lines beginning `#` say
306 /// nothing; `\#` begins a pattern with a literal hash. Trailing spaces are
307 /// trimmed unless the space is escaped with `\`. A line no rule can be
308 /// compiled from is passed over, as git passes over a pattern it cannot
309 /// read.
310 pub fn parse(bytes: &[u8]) -> Self {
311 let mut rules = Vec::new();
312 for raw in bytes.split(|b| *b == b'\n') {
313 let mut line = raw;
314 if line.last() == Some(&b'\r') {
315 line = &line[..line.len() - 1];
316 }
317 if line.is_empty() || line.first() == Some(&b'#') {
318 continue;
319 }
320 line = Self::trim_trailing_spaces(line);
321 if line.is_empty() {
322 continue;
323 }
324 if let Ok(glob) = Glob::new(line) {
325 rules.push(glob);
326 }
327 }
328 Self { rules }
329 }
330
331 pub fn is_empty(&self) -> bool {
332 self.rules.is_empty()
333 }
334
335 /// Returns what the file says about a path, if it says anything.
336 ///
337 /// The last pattern that matches decides: `Some(true)` means ignored,
338 /// `Some(false)` means a `!` pattern re-included it, and `None` means no
339 /// pattern spoke.
340 pub fn decides(&self, path: &[u8], is_dir: bool) -> Option<bool> {
341 let mut decision = None;
342 for rule in &self.rules {
343 if rule.matches(path, is_dir) {
344 decision = Some(!rule.negated);
345 }
346 }
347 decision
348 }
349
350 /// Reports whether the path itself is ignored, last match winning.
351 ///
352 /// This asks about the path alone. To also honour an ignored directory
353 /// swallowing everything beneath it, ask [`IgnoreFile::excludes`].
354 pub fn ignores(&self, path: &[u8], is_dir: bool) -> bool {
355 self.decides(path, is_dir).unwrap_or(false)
356 }
357
358 /// Reports whether the path is excluded, counting its ancestors.
359 ///
360 /// A path inside an ignored directory is excluded no matter what a `!`
361 /// pattern says about the path itself, because git does not descend into a
362 /// directory it has ignored. Each ancestor is judged in its own right,
363 /// last match winning, before the path is.
364 pub fn excludes(&self, path: &[u8], is_dir: bool) -> bool {
365 for (i, b) in path.iter().enumerate() {
366 if *b == b'/' && self.ignores(&path[..i], true) {
367 return true;
368 }
369 }
370 self.ignores(path, is_dir)
371 }
372
373 /// Strips trailing spaces that are not escaped with a backslash.
374 ///
375 /// An even number of backslashes before a space leaves the space bare, so
376 /// it goes; an odd number quotes it, so it and everything before it stays.
377 fn trim_trailing_spaces(mut line: &[u8]) -> &[u8] {
378 while line.last() == Some(&b' ') {
379 let body = &line[..line.len() - 1];
380 let slashes = body.iter().rev().take_while(|b| **b == b'\\').count();
381 if slashes % 2 == 1 {
382 break;
383 }
384 line = body;
385 }
386 line
387 }
388}