tf_types/
glob.rs

1//! TrustForge glob matching: the pattern language used by capability
2//! target sets, negative-capability targets, and policy `target_patterns`.
3//!
4//! Semantics (canonical since B8):
5//! - `*`  matches any run (possibly empty) of characters **except `/`**
6//! - `**` matches any run (possibly empty) of characters, including `/`
7//! - every other character, `?` included, matches itself literally
8//!
9//! Previously each call site converted the glob to a regex and matched
10//! with the `regex` crate; the three private copies had drifted (two
11//! still byte-iterated, corrupting non-ASCII patterns, and passed `?`
12//! through as a regex quantifier). This module is the single
13//! implementation. It matches directly — no regex, no compilation step —
14//! in O(pattern × value) worst case with plain DP, so untrusted patterns
15//! cannot trigger pathological backtracking.
16
17/// Match `value` against a TrustForge glob `pattern`.
18pub fn glob_match(pattern: &str, value: &str) -> bool {
19    enum Tok {
20        /// `**` — any run, `/` included.
21        Any,
22        /// `*` — any run without `/`.
23        AnySegment,
24        Lit(char),
25    }
26
27    let mut toks = Vec::with_capacity(pattern.len());
28    let mut chars = pattern.chars().peekable();
29    while let Some(c) = chars.next() {
30        if c == '*' {
31            if chars.peek() == Some(&'*') {
32                chars.next();
33                toks.push(Tok::Any);
34            } else {
35                toks.push(Tok::AnySegment);
36            }
37        } else {
38            toks.push(Tok::Lit(c));
39        }
40    }
41
42    let vals: Vec<char> = value.chars().collect();
43
44    // dp[j] = "the tokens consumed so far can match vals[..j]".
45    let mut dp = vec![false; vals.len() + 1];
46    dp[0] = true;
47    for tok in &toks {
48        let mut next = vec![false; vals.len() + 1];
49        match tok {
50            Tok::Lit(l) => {
51                for j in 0..vals.len() {
52                    next[j + 1] = dp[j] && vals[j] == *l;
53                }
54            }
55            Tok::Any => {
56                let mut reachable = false;
57                for j in 0..=vals.len() {
58                    reachable = reachable || dp[j];
59                    next[j] = reachable;
60                }
61            }
62            Tok::AnySegment => {
63                // Reachability propagates rightward but stops at `/`.
64                let mut reachable = false;
65                for j in 0..=vals.len() {
66                    reachable = reachable || dp[j];
67                    next[j] = reachable;
68                    if j < vals.len() && vals[j] == '/' {
69                        reachable = false;
70                    }
71                }
72            }
73        }
74        dp = next;
75    }
76    dp[vals.len()]
77}
78
79#[cfg(test)]
80mod tests {
81    use super::glob_match;
82
83    #[test]
84    fn literals() {
85        assert!(glob_match("files.read", "files.read"));
86        assert!(!glob_match("files.read", "files.write"));
87        assert!(!glob_match("files.read", "files.read2"));
88        assert!(!glob_match("files.read2", "files.read"));
89        assert!(glob_match("", ""));
90        assert!(!glob_match("", "a"));
91    }
92
93    #[test]
94    fn single_star_stops_at_slash() {
95        assert!(glob_match("repo/*", "repo/main"));
96        assert!(!glob_match("repo/*", "repo/main/file"));
97        assert!(glob_match("repo/*/file", "repo/main/file"));
98        assert!(glob_match("*.rs", "lib.rs"));
99        assert!(!glob_match("*.rs", "src/lib.rs"));
100        assert!(glob_match("a*", "a"));
101    }
102
103    #[test]
104    fn double_star_crosses_slash() {
105        assert!(glob_match("repo/**", "repo/main/deep/file"));
106        assert!(glob_match("repo/**", "repo/"));
107        assert!(glob_match("**/file", "repo/main/file"));
108        assert!(glob_match("**", ""));
109        assert!(glob_match("**", "anything/at/all"));
110    }
111
112    #[test]
113    fn mixed_stars_requiring_full_backtracking() {
114        // A single-backtrack matcher gets this wrong: `**` must grow
115        // even though a later `*` hit the mismatch.
116        assert!(glob_match("**/a*b", "x/a/ab"));
117        // `/` is literal here: `**` does not swallow the separator.
118        assert!(!glob_match("**/a*b", "aXb"));
119        assert!(!glob_match("**/a*b", "x/a/a"));
120        assert!(glob_match("*a*a*", "aaa"));
121        assert!(!glob_match("*a*a*", "a/a"));
122        assert!(glob_match("**a**a**", "a/a"));
123    }
124
125    #[test]
126    fn question_mark_is_literal() {
127        // B8: `?` is an ordinary character, not a wildcard.
128        assert!(glob_match("ok?", "ok?"));
129        assert!(!glob_match("ok?", "ok"));
130        assert!(!glob_match("ok?", "okX"));
131    }
132
133    #[test]
134    fn regex_meta_is_literal() {
135        assert!(glob_match("a.b+c(d)", "a.b+c(d)"));
136        assert!(!glob_match("a.b", "axb"));
137        assert!(glob_match("[env]", "[env]"));
138        assert!(glob_match("^start$", "^start$"));
139    }
140
141    #[test]
142    fn non_ascii_patterns() {
143        // The old byte-based converters corrupted multi-byte chars.
144        assert!(glob_match("café/*", "café/menu"));
145        assert!(!glob_match("café/*", "cafe/menu"));
146        assert!(glob_match("*é", "résumé"));
147    }
148}
tf_types/glob.rs

tf_types/
glob.rs
