vivacity_core/
glob.rs

1//! The `glob()` a `path` repository runs (`PathRepository::getUrlMatches`:
2//! `GLOB_MARK | GLOB_ONLYDIR | GLOB_BRACE`) and `Platform::expandPath`,
3//! reproduced from the libc semantics PHP exposes on Linux and macOS:
4//!
5//! - braces expand first, left to right, nesting allowed; every alternative
6//!   is globbed on its own and its matches are sorted bytewise among
7//!   themselves (glibc's order: `{b,a}` lists the `b` matches before the
8//!   `a` ones — PHP builds differ here, the 8.4 build of the macOS CI runner
9//!   sorts across alternatives where 8.5 on macOS and glibc do not; the
10//!   order only decides `addPackage` order between alternatives, i.e. which
11//!   of two identical name/version packages comes first); a duplicate
12//!   alternative yields the same path twice;
13//! - `*`, `?` and `[…]` match inside one path segment and never a leading
14//!   `.` (no `GLOB_PERIOD`); a segment without a metacharacter is a literal
15//!   that must exist; `\` escapes the next character;
16//! - the result keeps the pattern's spelling (`./packages/*` → `./packages/x`,
17//!   `a//*` → `a//x`); a directory gets a trailing `/` (`GLOB_MARK`), which
18//!   a pattern ending in `/` already carries once;
19//! - only directories are kept (`GLOB_ONLYDIR`, a link to a directory counts).
20
21use std::path::{Path, PathBuf};
22
23/// `glob($pattern, GLOB_MARK | GLOB_ONLYDIR | GLOB_BRACE)` with a relative
24/// pattern resolved against `base` (the project directory, PHP's cwd).
25pub fn glob_dirs(pattern: &str, base: &Path) -> Vec<String> {
26    let mut out = Vec::new();
27    for alternative in brace_expand(pattern) {
28        let mut found = glob_one(&alternative, base);
29        found.sort_by(|a, b| a.as_bytes().cmp(b.as_bytes()));
30        out.extend(found);
31    }
32    out
33}
34
35/// `GLOB_BRACE`: the first `{…}` with a matching `}` is expanded, each
36/// alternative recursively.
37pub fn brace_expand(pattern: &str) -> Vec<String> {
38    let bytes = pattern.as_bytes();
39    let Some(open) = find_unescaped(bytes, 0, b'{') else {
40        return vec![pattern.to_owned()];
41    };
42    // The matching brace and the top-level commas between them.
43    let mut depth = 0usize;
44    let mut cuts: Vec<usize> = Vec::new();
45    let mut close: Option<usize> = None;
46    let mut i = open;
47    while i < bytes.len() {
48        match bytes[i] {
49            b'\\' => i += 1,
50            b'{' => depth += 1,
51            b'}' => {
52                depth -= 1;
53                if depth == 0 {
54                    close = Some(i);
55                    break;
56                }
57            }
58            b',' if depth == 1 => cuts.push(i),
59            _ => {}
60        }
61        i += 1;
62    }
63    let Some(close) = close else {
64        return vec![pattern.to_owned()];
65    };
66    let head = &pattern[..open];
67    let tail = &pattern[close + 1..];
68    let mut out = Vec::new();
69    let mut start = open + 1;
70    for end in cuts.into_iter().chain(std::iter::once(close)) {
71        let alt = &pattern[start..end];
72        out.extend(brace_expand(&format!("{head}{alt}{tail}")));
73        start = end + 1;
74    }
75    out
76}
77
78fn find_unescaped(bytes: &[u8], from: usize, needle: u8) -> Option<usize> {
79    let mut i = from;
80    while i < bytes.len() {
81        if bytes[i] == b'\\' {
82            i += 2;
83            continue;
84        }
85        if bytes[i] == needle {
86            return Some(i);
87        }
88        i += 1;
89    }
90    None
91}
92
93fn has_magic(segment: &str) -> bool {
94    let b = segment.as_bytes();
95    let mut i = 0;
96    while i < b.len() {
97        match b[i] {
98            b'\\' => i += 1,
99            b'*' | b'?' | b'[' => return true,
100            _ => {}
101        }
102        i += 1;
103    }
104    false
105}
106
107fn unescape(segment: &str) -> String {
108    let mut out = String::with_capacity(segment.len());
109    let mut chars = segment.chars();
110    while let Some(c) = chars.next() {
111        if c == '\\' {
112            if let Some(n) = chars.next() {
113                out.push(n);
114            }
115        } else {
116            out.push(c);
117        }
118    }
119    out
120}
121
122fn glob_one(pattern: &str, base: &Path) -> Vec<String> {
123    if pattern.is_empty() {
124        return Vec::new();
125    }
126    let segments: Vec<&str> = pattern.split('/').collect();
127    // (spelling so far, filesystem path so far)
128    let mut current: Vec<(String, PathBuf)> = vec![(String::new(), base.to_path_buf())];
129    let last = segments.len() - 1;
130    for (i, seg) in segments.iter().enumerate() {
131        let mut next: Vec<(String, PathBuf)> = Vec::new();
132        for (spelling, dir) in &current {
133            let prefix = if i == 0 {
134                String::new()
135            } else {
136                format!("{spelling}/")
137            };
138            if seg.is_empty() {
139                // A leading `/` (absolute), a doubled `//`, or a trailing `/`
140                // (directories only): the spelling keeps the slash, the
141                // filesystem path is unchanged (or the root).
142                let fs = if i == 0 {
143                    PathBuf::from("/")
144                } else {
145                    dir.clone()
146                };
147                if i == last && !fs.is_dir() {
148                    continue;
149                }
150                next.push((prefix, fs));
151            } else if has_magic(seg) {
152                let Ok(rd) = std::fs::read_dir(dir) else {
153                    continue;
154                };
155                // readdir lists `.` and `..` too: a pattern starting with a
156                // dot matches them (`.*` → `packages/./`, `packages/../`).
157                let mut names: Vec<String> = vec![".".into(), "..".into()];
158                names.extend(
159                    rd.flatten()
160                        .filter_map(|e| e.file_name().to_str().map(str::to_owned)),
161                );
162                for name in names {
163                    if !fnmatch_period(seg, &name) {
164                        continue;
165                    }
166                    let fs = dir.join(&name);
167                    if i == last && !fs.is_dir() {
168                        continue;
169                    }
170                    next.push((format!("{prefix}{name}"), fs));
171                }
172            } else {
173                let literal = unescape(seg);
174                let fs = dir.join(&literal);
175                let exists = if i == last { fs.is_dir() } else { fs.exists() };
176                if !exists {
177                    continue;
178                }
179                next.push((format!("{prefix}{seg}"), fs));
180            }
181        }
182        current = next;
183    }
184    current
185        .into_iter()
186        .map(|(spelling, _)| {
187            if spelling.ends_with('/') {
188                spelling
189            } else {
190                format!("{spelling}/")
191            }
192        })
193        .collect()
194}
195
196/// `fnmatch(pattern, name, FNM_PERIOD)` on one segment.
197fn fnmatch_period(pattern: &str, name: &str) -> bool {
198    if name.starts_with('.') && !pattern.starts_with('.') {
199        return false;
200    }
201    fnmatch(pattern.as_bytes(), name.as_bytes())
202}
203
204fn fnmatch(p: &[u8], s: &[u8]) -> bool {
205    if p.is_empty() {
206        return s.is_empty();
207    }
208    match p[0] {
209        b'*' => {
210            // Collapse consecutive stars; try every split.
211            let rest = &p[1..];
212            (0..=s.len()).any(|k| fnmatch(rest, &s[k..]))
213        }
214        b'?' => !s.is_empty() && fnmatch(&p[1..], &s[1..]),
215        b'[' => {
216            let Some((matched, consumed)) = bracket(p, s) else {
217                // No closing bracket: a literal `[`.
218                return !s.is_empty() && s[0] == b'[' && fnmatch(&p[1..], &s[1..]);
219            };
220            matched && fnmatch(&p[consumed..], &s[1..])
221        }
222        b'\\' if p.len() > 1 => !s.is_empty() && s[0] == p[1] && fnmatch(&p[2..], &s[1..]),
223        c => !s.is_empty() && s[0] == c && fnmatch(&p[1..], &s[1..]),
224    }
225}
226
227/// `[…]` at the start of `p` against the first byte of `s`: (matched, bytes
228/// of the pattern consumed), None without a closing bracket.
229fn bracket(p: &[u8], s: &[u8]) -> Option<(bool, usize)> {
230    let mut i = 1;
231    let negate = i < p.len() && (p[i] == b'!' || p[i] == b'^');
232    if negate {
233        i += 1;
234    }
235    let mut matched = false;
236    let mut first = true;
237    let c = s.first().copied();
238    while i < p.len() {
239        let mut lo = p[i];
240        if lo == b']' && !first {
241            let hit = matched != negate;
242            return Some((c.is_some() && hit, i + 1));
243        }
244        first = false;
245        if lo == b'\\' && i + 1 < p.len() {
246            i += 1;
247            lo = p[i];
248        }
249        let mut hi = lo;
250        if i + 2 < p.len() && p[i + 1] == b'-' && p[i + 2] != b']' {
251            hi = p[i + 2];
252            if hi == b'\\' && i + 3 < p.len() {
253                hi = p[i + 3];
254                i += 1;
255            }
256            i += 2;
257        }
258        if let Some(c) = c {
259            if lo <= c && c <= hi {
260                matched = true;
261            }
262        }
263        i += 1;
264    }
265    None
266}
267
268/// PHP `dirname()` for the "does not exist" walk of `PathRepository`:
269/// trailing slashes ignored, `.` without a slash, `/` for a root child.
270pub fn php_dirname(path: &str) -> String {
271    let trimmed = path.trim_end_matches('/');
272    if trimmed.is_empty() {
273        return if path.starts_with('/') {
274            "/".into()
275        } else {
276            ".".into()
277        };
278    }
279    match trimmed.rfind('/') {
280        None => ".".into(),
281        Some(0) => "/".into(),
282        Some(i) => {
283            let parent = trimmed[..i].trim_end_matches('/');
284            if parent.is_empty() {
285                "/".into()
286            } else {
287                parent.to_owned()
288            }
289        }
290    }
291}
292
293/// `Platform::expandPath`: `~/x` → `$HOME/x`; a leading `$VAR` or `%VAR%`
294/// is replaced by the variable (empty when unset), the rest kept.
295pub fn expand_path(path: &str) -> String {
296    if path.starts_with("~/") || path.starts_with("~\\") {
297        return format!("{}{}", user_directory(), &path[1..]);
298    }
299    let b = path.as_bytes();
300    let (percent, start) = match b.first() {
301        Some(b'$') => (false, 1),
302        Some(b'%') => (true, 1),
303        _ => return path.to_owned(),
304    };
305    let mut end = start;
306    while end < b.len() && (b[end].is_ascii_alphanumeric() || b[end] == b'_') {
307        end += 1;
308    }
309    if end == start {
310        return path.to_owned();
311    }
312    let var = &path[start..end];
313    let rest = if percent {
314        match path[end..].strip_prefix('%') {
315            Some(r) => r,
316            None => return path.to_owned(),
317        }
318    } else {
319        &path[end..]
320    };
321    let value = if cfg!(windows) && var == "HOME" {
322        match std::env::var("HOME") {
323            Ok(h) if !h.is_empty() => h,
324            _ => std::env::var("USERPROFILE").unwrap_or_default(),
325        }
326    } else {
327        std::env::var(var).unwrap_or_default()
328    };
329    format!("{value}{rest}")
330}
331
332fn user_directory() -> String {
333    if let Ok(h) = std::env::var("HOME") {
334        return h;
335    }
336    if cfg!(windows) {
337        if let Ok(h) = std::env::var("USERPROFILE") {
338            return h;
339        }
340    }
341    String::new()
342}
343
344#[cfg(test)]
345mod tests {
346    use super::*;
347
348    #[test]
349    fn braces() {
350        assert_eq!(brace_expand("a{b,c}d"), vec!["abd", "acd"]);
351        assert_eq!(
352            brace_expand("a{b,c}d{e,f}"),
353            vec!["abde", "abdf", "acde", "acdf"]
354        );
355        assert_eq!(brace_expand("x{a,{b,c}}"), vec!["xa", "xb", "xc"]);
356        assert_eq!(brace_expand("plain"), vec!["plain"]);
357        assert_eq!(brace_expand("un{closed"), vec!["un{closed"]);
358    }
359
360    #[test]
361    fn matching() {
362        assert!(fnmatch_period("*", "alpha"));
363        assert!(!fnmatch_period("*", ".hidden"));
364        assert!(fnmatch_period(".*", ".hidden"));
365        assert!(fnmatch_period("a?pha", "alpha"));
366        assert!(fnmatch_period("[a-c]*", "beta"));
367        assert!(!fnmatch_period("[!a-c]*", "beta"));
368        assert!(fnmatch_period("*a", "alpha"));
369        assert!(!fnmatch_period("*a", "alphabet"));
370        assert!(fnmatch_period("\\*", "*"));
371    }
372
373    #[test]
374    fn dirname_like_php() {
375        assert_eq!(php_dirname("packages/x*"), "packages");
376        assert_eq!(php_dirname("packages/*/"), "packages");
377        assert_eq!(php_dirname("*"), ".");
378        assert_eq!(php_dirname("/a"), "/");
379        assert_eq!(php_dirname("/a/b"), "/a");
380        assert_eq!(php_dirname("a//b"), "a");
381    }
382
383    /// Against PHP's own `glob()` on a temporary tree, when a `php` binary is
384    /// on the PATH (the CI images of the harness have one).
385    #[test]
386    fn matches_php_glob() {
387        let tmp = tempfile::tempdir().expect("tmp");
388        let root = tmp.path();
389        for d in [
390            "packages/alpha/src",
391            "packages/delta",
392            "packages/.hidden",
393            "packages/gamma",
394            "libs/beta",
395            "libs/epsilon",
396            "src-zeta",
397            "a-b",
398        ] {
399            std::fs::create_dir_all(root.join(d)).expect("mkdir");
400        }
401        std::fs::write(root.join("packages/file"), "").expect("file");
402        #[cfg(unix)]
403        std::os::unix::fs::symlink("packages/alpha", root.join("link")).expect("link");
404        let patterns = [
405            "packages/*",
406            "./packages/*/",
407            "packages//*",
408            "libs/{epsilon,beta}",
409            "packages/{alpha,alpha}",
410            "packages/*/src",
411            "packages/*a",
412            "packages/.*",
413            "packages/?elta",
414            "packages/[ad]*",
415            "packages/[!a]*",
416            "packages/file",
417            "packages/alpha",
418            "nowhere/*",
419            "*",
420            "{packages,libs}/*",
421            "a-b",
422            "l?nk",
423            "",
424        ];
425        let php = std::process::Command::new("php")
426            .arg("-r")
427            .arg("chdir($argv[1]); foreach (array_slice($argv, 2) as $p) { echo json_encode(glob($p, GLOB_MARK|GLOB_ONLYDIR|GLOB_BRACE), JSON_UNESCAPED_SLASHES), \"\\n\"; }")
428            .arg(root)
429            .args(patterns)
430            .output();
431        let Ok(php) = php else {
432            eprintln!("php not found: oracle skipped");
433            return;
434        };
435        assert!(
436            php.status.success(),
437            "{}",
438            String::from_utf8_lossy(&php.stderr)
439        );
440        let lines: Vec<String> = String::from_utf8_lossy(&php.stdout)
441            .lines()
442            .map(str::to_owned)
443            .collect();
444        for (p, expected) in patterns.iter().zip(lines) {
445            let mut ours = glob_dirs(p, root);
446            // PHP's GLOB_MARK appends the OS separator (`\` on Windows);
447            // `getUrlMatches` turns it into `/` before anything else.
448            let mut theirs: Vec<String> = serde_json::from_str::<Vec<String>>(&expected)
449                .unwrap()
450                .into_iter()
451                .map(|m| m.replace('\\', "/"))
452                .collect();
453            // The order across brace alternatives depends on the PHP build
454            // (module header): compared as sets for those patterns.
455            if brace_expand(p).len() > 1 {
456                ours.sort();
457                theirs.sort();
458            }
459            assert_eq!(ours, theirs, "pattern {p}");
460        }
461    }
462}
vivacity_core/glob.rs

vivacity_core/
glob.rs
