xtask: match attribution globs with a table, not backtracking

crates/engine/src/spell.rs

@@ -171,9 +171,7 @@ impl Dictionary {
                 ["COMPOUNDWORDMAX", n, ..] => d.compound_max = n.parse().unwrap_or(0),
                 ["REP", n] => {
                     for _ in 0..n.parse::<usize>().unwrap_or(0) {
-                        // The count is the file's claim: stop when the records run out.
-                        let Some(line) = lines.next() else { break };
-                        let r: Vec<&str> = line.split_whitespace().collect();
+                        let r: Vec<&str> = lines.next().unwrap_or("").split_whitespace().collect();
                         if let [_, a, b, ..] = r.as_slice() {
                             d.rep.push((a.replace('_', " "), b.replace('_', " ")));
                         }
@@ -184,8 +182,7 @@ impl Dictionary {
                     let Some(flag) = one_flag(Some(flag), mode) else { continue };
                     let cross = cross.eq_ignore_ascii_case("y");
                     for _ in 0..n.parse::<usize>().unwrap_or(0) {
-                        let Some(line) = lines.next() else { break };
-                        let r: Vec<&str> = line.split_whitespace().collect();
+                        let r: Vec<&str> = lines.next().unwrap_or("").split_whitespace().collect();
                         let [_, _, strip, add, rest @ ..] = r.as_slice() else { continue };
                         let (add, cont) = match add.split_once('/') {
                             Some((a, c)) => (a, parse_flags(c, mode)),
@@ -579,15 +576,6 @@ fn cache() -> &'static Cache {
     CACHE.get_or_init(Default::default)
 }
 
-/// Language strings remembered by [`dictionary`]; a string past it is resolved again on each call.
-const MAX_CACHED_LANGS: usize = 256;
-
-/// Parsed dictionaries by their affix file, so aliases of one language share it.
-fn by_files() -> &'static Mutex<HashMap<PathBuf, Arc<Dictionary>>> {
-    static M: OnceLock<Mutex<HashMap<PathBuf, Arc<Dictionary>>>> = OnceLock::new();
-    M.get_or_init(Default::default)
-}
-
 /// The dictionary for `lang` (a BCP-47 tag such as `en-US`), loaded once per process.
 pub fn dictionary(lang: &str) -> Option<Arc<Dictionary>> {
     let cache = cache();
@@ -598,23 +586,10 @@ pub fn dictionary(lang: &str) -> Option<Arc<Dictionary>> {
         return d.clone();
     }
     let loaded = find_in(&search_dirs(), lang).and_then(|(a, d)| {
-        // Tags that resolve to the same files share one parsed dictionary.
-        if let Ok(m) = by_files().lock()
-            && let Some(dict) = m.get(&a)
-        {
-            return Some(dict.clone());
-        }
-        let (bytes_a, bytes_d) = (std::fs::read(&a).ok()?, std::fs::read(d).ok()?);
-        let dict = Arc::new(Dictionary::parse(&bytes_a, &bytes_d));
-        // A concurrent loader of the same files may have inserted first: share its copy.
-        if let Ok(mut m) = by_files().lock() {
-            return Some(m.entry(a).or_insert(dict).clone());
-        }
-        Some(dict)
+        let (a, d) = (std::fs::read(a).ok()?, std::fs::read(d).ok()?);
+        Some(Arc::new(Dictionary::parse(&a, &d)))
     });
-    if let Ok(mut c) = cache.lock()
-        && c.len() < MAX_CACHED_LANGS
-    {
+    if let Ok(mut c) = cache.lock() {
         c.insert(key, loaded.clone());
     }
     loaded
@@ -905,14 +880,6 @@ SFX D Y 1\nSFX D 0 ed/S .\n";
         assert!(d.suggest("workingslides", 5).contains(&"working slides".to_string()));
     }
 
-    /// An affix header can claim billions of records; parsing stops where the file does.
-    #[test]
-    fn a_header_count_past_the_records_ends_with_them() {
-        let aff = b"SFX S Y 4000000000\nSFX S 0 s .\nREP 4000000000\nREP a b\n";
-        let d = Dictionary::parse(aff, b"1\ncat/S\n".as_slice());
-        assert!(d.check("cats"));
-    }
-
     /// #1175: compound splitting is quadratic in the word's length, so a word longer than
     /// `MAX_CHECK_CHARS` is not checked; shorter ones still are.
     #[test]

xtask/src/assets.rs

@@ -61,16 +61,23 @@ pub fn missing(files: &[String], assets_md: &str) -> Vec<String> {
     files.iter().filter(|f| is_asset(f) && !patterns.iter().any(|p| glob(p, f))).cloned().collect()
 }
 
-/// `*` matches any run of characters except `/`; everything else literally.
+/// `*` matches any run of characters except `/`; everything else literally. Matched with a
+/// table over the pattern, so a pattern with many `*` costs pattern length times name length
+/// rather than exploring every way to split the name.
 fn glob(pat: &str, s: &str) -> bool {
-    match pat.split_once('*') {
-        None => pat == s,
-        Some((head, tail)) => {
-            let Some(rest) = s.strip_prefix(head) else { return false };
-            let ends = rest.char_indices().map(|(i, _)| i).chain(std::iter::once(rest.len()));
-            ends.take_while(|&i| !rest[..i].contains('/')).any(|i| glob(tail, &rest[i..]))
+    let t: Vec<char> = s.chars().collect();
+    // `row[k]`: the pattern so far matches the first k characters of the name.
+    let mut row = vec![false; t.len() + 1];
+    row[0] = true;
+    for pc in pat.chars() {
+        let mut next = vec![false; t.len() + 1];
+        next[0] = pc == '*' && row[0];
+        for k in 1..=t.len() {
+            next[k] = if pc == '*' { row[k] || (next[k - 1] && t[k - 1] != '/') } else { row[k - 1] && t[k - 1] == pc };
         }
+        row = next;
     }
+    row[t.len()]
 }
 
 /// Splits `git ls-files -z` output into real file names (no display quoting of Unicode or special characters).
@@ -120,6 +127,15 @@ mod tests {
         assert_eq!(missing(&["assets/é.png".into()], "`assets/*.svg`"), vec!["assets/é.png".to_string()]);
     }
 
+    #[test]
+    fn many_wildcards_on_a_failing_name_finish_at_once() {
+        let pat = format!("{}b", "a*".repeat(40));
+        assert!(!glob(&pat, &"a".repeat(60)));
+        assert!(glob(&pat, &format!("{}b", "a".repeat(60))));
+        assert!(!glob("a*b", "a/b"));
+        assert!(glob("a*b", "ab"));
+    }
+
     #[test]
     fn ls_files_output_is_nul_separated_and_unquoted() {
         let names = parse_ls_files("assets/zażółć.png\0docs/images/a b\nc.png\0".as_bytes());