Pick any line to see why it is the way it is: the commit, the pull request and issue it came from, and what the agent was thinking.
| Merge rulesets: branch and tag rules, agent-first, enforced on push and merge | 1 | //! fnmatch patterns, for branch and tag names, repository names and file |
| 2 | //! paths. | |
| 3 | //! | |
| 4 | //! - `*` matches any run of characters but `/`. | |
| 5 | //! - `**` matches any run of characters, `/` included; `**/` also matches | |
| 6 | //! no directory at all, so `docs/**/*.md` matches `docs/a.md`. | |
| 7 | //! - `?` matches one character but `/`. | |
| 8 | //! - `[abc]`, `[a-z]` match one character of the set; `[!abc]` or `[^abc]` | |
| 9 | //! one not in it. | |
| 10 | //! - `\` makes the next character literal. | |
| 11 | //! | |
| 12 | //! Matching is a table over pattern and text positions, so it takes time in | |
| 13 | //! proportion to their lengths multiplied, never more. | |
| 14 | ||
| 15 | /// One piece of a pattern. | |
| 16 | #[derive(Clone, Debug, PartialEq, Eq)] | |
| 17 | enum Token { | |
| 18 | Literal(char), | |
| 19 | /// `?` | |
| 20 | One, | |
| 21 | /// `*` | |
| 22 | Star, | |
| 23 | /// `**`, and whether a `/` follows it (`**/`), which it may skip. | |
| 24 | Globstar { slash: bool }, | |
| 25 | Class { negated: bool, items: Vec<(char, char)> }, | |
| 26 | } | |
| 27 | ||
| 28 | fn tokens(pattern: &str) -> Vec<Token> { | |
| 29 | let chars: Vec<char> = pattern.chars().collect(); | |
| 30 | let mut out = Vec::new(); | |
| 31 | let mut at = 0; | |
| 32 | while at < chars.len() { | |
| 33 | match chars[at] { | |
| 34 | '\\' if at + 1 < chars.len() => { | |
| 35 | out.push(Token::Literal(chars[at + 1])); | |
| 36 | at += 2; | |
| 37 | } | |
| 38 | '*' if chars.get(at + 1) == Some(&'*') => { | |
| 39 | let slash = chars.get(at + 2) == Some(&'/'); | |
| 40 | out.push(Token::Globstar { slash }); | |
| 41 | at += if slash { 3 } else { 2 }; | |
| 42 | // More stars right after `**` say no more. | |
| 43 | while !slash && chars.get(at) == Some(&'*') { | |
| 44 | at += 1; | |
| 45 | } | |
| 46 | } | |
| 47 | '*' => { | |
| 48 | out.push(Token::Star); | |
| 49 | at += 1; | |
| 50 | } | |
| 51 | '?' => { | |
| 52 | out.push(Token::One); | |
| 53 | at += 1; | |
| 54 | } | |
| 55 | '[' => match class(&chars, at) { | |
| 56 | Some((token, next)) => { | |
| 57 | out.push(token); | |
| 58 | at = next; | |
| 59 | } | |
| 60 | None => { | |
| 61 | out.push(Token::Literal('[')); | |
| 62 | at += 1; | |
| 63 | } | |
| 64 | }, | |
| 65 | c => { | |
| 66 | out.push(Token::Literal(c)); | |
| 67 | at += 1; | |
| 68 | } | |
| 69 | } | |
| 70 | } | |
| 71 | out | |
| 72 | } | |
| 73 | ||
| 74 | /// A `[...]` class starting at `start`, and where the pattern goes on. | |
| 75 | fn class(chars: &[char], start: usize) -> Option<(Token, usize)> { | |
| 76 | let mut at = start + 1; | |
| 77 | let negated = matches!(chars.get(at), Some('!' | '^')); | |
| 78 | if negated { | |
| 79 | at += 1; | |
| 80 | } | |
| 81 | let mut items = Vec::new(); | |
| 82 | let mut first = true; | |
| 83 | loop { | |
| 84 | let c = *chars.get(at)?; | |
| 85 | if c == ']' && !first { | |
| 86 | return Some((Token::Class { negated, items }, at + 1)); | |
| 87 | } | |
| 88 | first = false; | |
| 89 | let c = if c == '\\' { | |
| 90 | at += 1; | |
| 91 | *chars.get(at)? | |
| 92 | } else { | |
| 93 | c | |
| 94 | }; | |
| 95 | if chars.get(at + 1) == Some(&'-') && chars.get(at + 2).is_some_and(|end| *end != ']') { | |
| 96 | items.push((c, chars[at + 2])); | |
| 97 | at += 3; | |
| 98 | } else { | |
| 99 | items.push((c, c)); | |
| 100 | at += 1; | |
| 101 | } | |
| 102 | } | |
| 103 | } | |
| 104 | ||
| 105 | fn in_class(c: char, negated: bool, items: &[(char, char)]) -> bool { | |
| 106 | let found = items.iter().any(|(low, high)| (*low..=*high).contains(&c)); | |
| 107 | found != negated && c != '/' | |
| 108 | } | |
| 109 | ||
| 110 | /// Whether `text` matches `pattern`, exactly. | |
| 111 | pub fn matches(pattern: &str, text: &str) -> bool { | |
| 112 | let tokens = tokens(pattern); | |
| 113 | let text: Vec<char> = text.chars().collect(); | |
| 114 | // done[t][p]: whether text[t..] matches tokens[p..]. | |
| 115 | let (rows, cols) = (text.len() + 1, tokens.len() + 1); | |
| 116 | let mut done = vec![false; rows * cols]; | |
| 117 | done[text.len() * cols + tokens.len()] = true; | |
| 118 | for t in (0..rows).rev() { | |
| 119 | for p in (0..tokens.len()).rev() { | |
| 120 | let next = |t: usize, p: usize| done[t * cols + p]; | |
| 121 | let here = match &tokens[p] { | |
| 122 | Token::Literal(c) => t < text.len() && text[t] == *c && next(t + 1, p + 1), | |
| 123 | Token::One => t < text.len() && text[t] != '/' && next(t + 1, p + 1), | |
| 124 | Token::Class { negated, items } => { | |
| 125 | t < text.len() && in_class(text[t], *negated, items) && next(t + 1, p + 1) | |
| 126 | } | |
| 127 | // Nothing more, or one more character (not `/`) and the star again. | |
| 128 | Token::Star => next(t, p + 1) || (t < text.len() && text[t] != '/' && next(t + 1, p)), | |
| 129 | Token::Globstar { slash: false } => next(t, p + 1) || (t < text.len() && next(t + 1, p)), | |
| 130 | // `**/`: no directory at all, or any run ending in `/`. | |
| 131 | Token::Globstar { slash: true } => { | |
| 132 | next(t, p + 1) | |
| 133 | || (t < text.len() && { | |
| 134 | // Consume up to and including a `/`. | |
| 135 | let mut end = t; | |
| 136 | let mut found = false; | |
| 137 | while end < text.len() { | |
| 138 | if text[end] == '/' && next(end + 1, p + 1) { | |
| 139 | found = true; | |
| 140 | break; | |
| 141 | } | |
| 142 | end += 1; | |
| 143 | } | |
| 144 | found | |
| 145 | }) | |
| 146 | } | |
| 147 | }; | |
| 148 | done[t * cols + p] = here; | |
| 149 | } | |
| 150 | } | |
| 151 | done[0] | |
| 152 | } | |
| 153 | ||
| 154 | /// Whether a file path matches a path pattern. A pattern with no `/` in it | |
| 155 | /// matches a file of that name in any directory (`*.exe`, `CODEOWNERS`); | |
| 156 | /// one with a `/` matches from the repository's root, a leading `/` | |
| 157 | /// optional. A pattern ending in `/` matches everything under it. | |
| 158 | pub fn path_matches(pattern: &str, path: &str) -> bool { | |
| 159 | let pattern = pattern.trim(); | |
| 160 | if pattern.is_empty() { | |
| 161 | return false; | |
| 162 | } | |
| 163 | let path = path.trim_start_matches('/'); | |
| 164 | if let Some(directory) = pattern.strip_suffix('/') { | |
| 165 | let directory = directory.trim_start_matches('/'); | |
| 166 | return matches(&format!("{directory}/**"), path); | |
| 167 | } | |
| 168 | if !pattern.contains('/') { | |
| 169 | let name = path.rsplit('/').next().unwrap_or(path); | |
| 170 | return matches(pattern, name) || matches(pattern, path); | |
| 171 | } | |
| 172 | matches(pattern.trim_start_matches('/'), path) | |
| 173 | } | |
| 174 | ||
| 175 | /// Whether a pattern is one [`matches`] reads as written: its classes are | |
| 176 | /// closed. Anything else is still matched, as literal text. | |
| 177 | pub fn well_formed(pattern: &str) -> bool { | |
| 178 | let chars: Vec<char> = pattern.chars().collect(); | |
| 179 | let mut at = 0; | |
| 180 | while at < chars.len() { | |
| 181 | match chars[at] { | |
| 182 | '\\' => at += 2, | |
| 183 | '[' => match class(&chars, at) { | |
| 184 | Some((_, next)) => at = next, | |
| 185 | None => return false, | |
| 186 | }, | |
| 187 | _ => at += 1, | |
| 188 | } | |
| 189 | } | |
| 190 | true | |
| 191 | } | |
| 192 | ||
| 193 | #[cfg(test)] | |
| 194 | mod tests { | |
| 195 | use super::*; | |
| 196 | ||
| 197 | #[test] | |
| 198 | fn a_star_stays_within_a_segment() { | |
| 199 | assert!(matches("release/*", "release/1.x")); | |
| 200 | assert!(!matches("release/*", "release/1.x/hotfix")); | |
| 201 | assert!(!matches("release/*", "release")); | |
| 202 | assert!(matches("*", "main")); | |
| 203 | assert!(!matches("*", "feature/x")); | |
| 204 | assert!(matches("feat*", "feature")); | |
| 205 | assert!(matches("*-rc", "v1-rc")); | |
| 206 | } | |
| 207 | ||
| 208 | #[test] | |
| 209 | fn a_globstar_crosses_segments() { | |
| 210 | assert!(matches("release/**", "release/1.x/hotfix")); | |
| 211 | assert!(matches("**", "a/b/c")); | |
| 212 | assert!(matches("docs/**/*.md", "docs/a.md")); | |
| 213 | assert!(matches("docs/**/*.md", "docs/guides/deep/a.md")); | |
| 214 | assert!(!matches("docs/**/*.md", "src/a.md")); | |
| 215 | assert!(matches(".g1t/workflows/**", ".g1t/workflows/ci.yml")); | |
| 216 | assert!(matches("**/secrets.json", "secrets.json")); | |
| 217 | assert!(matches("**/secrets.json", "config/prod/secrets.json")); | |
| 218 | } | |
| 219 | ||
| 220 | #[test] | |
| 221 | fn single_characters_and_classes() { | |
| 222 | assert!(matches("v?", "v1")); | |
| 223 | assert!(!matches("v?", "v10")); | |
| 224 | assert!(!matches("a?b", "a/b")); | |
| 225 | assert!(matches("v[0-9]*", "v1.2")); | |
| 226 | assert!(!matches("v[0-9]*", "va")); | |
| 227 | assert!(matches("[!m]*", "dev")); | |
| 228 | assert!(!matches("[!m]*", "main")); | |
| 229 | assert!(matches("[^m]*", "dev")); | |
| 230 | assert!(matches("[]]", "]")); | |
| 231 | } | |
| 232 | ||
| 233 | #[test] | |
| 234 | fn escapes_and_unclosed_classes_are_literal() { | |
| 235 | assert!(matches(r"a\*b", "a*b")); | |
| 236 | assert!(!matches(r"a\*b", "axb")); | |
| 237 | assert!(matches("a[b", "a[b")); | |
| 238 | assert!(!well_formed("a[b")); | |
| 239 | assert!(well_formed("release/[0-9]*")); | |
| 240 | } | |
| 241 | ||
| 242 | #[test] | |
| 243 | fn exact_names_match_only_themselves() { | |
| 244 | assert!(matches("main", "main")); | |
| 245 | assert!(!matches("main", "mainline")); | |
| 246 | assert!(!matches("main", "Main")); | |
| 247 | assert!(matches("", "")); | |
| 248 | assert!(!matches("", "x")); | |
| 249 | } | |
| 250 | ||
| 251 | #[test] | |
| 252 | fn long_texts_do_not_take_long() { | |
| 253 | let text = "a".repeat(2000); | |
| 254 | let pattern = "*a*a*a*a*a*a*a*a*b"; | |
| 255 | assert!(!matches(pattern, &text)); | |
| 256 | } | |
| 257 | ||
| 258 | #[test] | |
| 259 | fn paths_without_a_slash_match_a_name_anywhere() { | |
| 260 | assert!(path_matches("CODEOWNERS", "CODEOWNERS")); | |
| 261 | assert!(path_matches("CODEOWNERS", ".g1t/CODEOWNERS")); | |
| 262 | assert!(path_matches("*.exe", "bin/tool.exe")); | |
| 263 | assert!(!path_matches("*.exe", "bin/tool.exe.txt")); | |
| 264 | assert!(path_matches("/infra/**", "infra/main.tf")); | |
| 265 | assert!(path_matches("infra/", "infra/modules/a.tf")); | |
| 266 | assert!(!path_matches("infra/", "src/infra.rs")); | |
| 267 | assert!(!path_matches("src/*.rs", "lib/src/a.rs")); | |
| 268 | assert!(!path_matches(" ", "a")); | |
| 269 | } | |
| 270 | } |
This file's history is long; its oldest lines are credited to the oldest commit read.