qk_cache/

glob.rs

//! Nx-compatible glob matching.
//!
//! Nx does not match extended globs directly. Patterns containing `|`, `(`, `{,`
//! or a leading `!` are first expanded into plain globs, and that expansion is
//! deliberately approximate: `+(a|b)` matches exactly one of `a` or `b`, `?(x)` and
//! `*(x)` mean "absent or once", an absent group in a directory segment widens that
//! segment to `*`, and a `?`, `+` or `@` not followed by `(` is dropped. The cache
//! mirrors the expansion of Nx 23 (`packages/nx/src/native/glob/glob_transform.rs`)
//! so input sets written for Nx select the same files.
//!
//! A negated group such as `!(a|b)` expands, as in Nx, into a glob with the
//! group widened and one with the group's items that excludes: a path matches
//! when an including glob does and no excluding one does. In a directory
//! segment the exclusion covers that whole directory. `!(a).` and `!(a)*`
//! widen to `*.` and `*`. Nx applies those exclusions to every pattern of a
//! project together; qk applies them to the pattern they come from, which can
//! only add inputs.

use anyhow::{Result, bail};
use globset::{GlobBuilder, GlobSet, GlobSetBuilder};

#[derive(Clone)]
pub struct Pattern {
    included: GlobSet,
    excluded: GlobSet,
}

impl Pattern {
    /// Compiles a glob without its leading `!`; `negated` says whether one was
    /// there. Nx expands every negated pattern, and every glob it expands to
    /// then excludes, so a negated pattern matches what any of them matches.
    /// As in Nx, `\` escapes the character after it on every platform.
    pub fn new(pattern: &str, negated: bool) -> Result<Self> {
        Self::from_globs(&[pattern], negated)
    }

    /// A fileset entry: as in Nx 24, a path with no glob pattern names that
    /// file, or that directory and everything under it.
    pub fn fileset(pattern: &str, negated: bool) -> Result<Self> {
        if pattern.is_empty() || pattern.ends_with('/') || !names_a_path(pattern) {
            return Self::new(pattern, negated);
        }
        Self::from_globs(&[pattern, &format!("{pattern}/**")], negated)
    }

    fn from_globs(patterns: &[&str], negated: bool) -> Result<Self> {
        let mut included = GlobSetBuilder::new();
        let mut excluded = GlobSetBuilder::new();
        for pattern in patterns {
            let globs = if negated
                || ["|", "(", "{,", "!"]
                    .iter()
                    .any(|token| unescaped(pattern).contains(token))
            {
                expand(pattern)?
            } else {
                vec![((*pattern).to_owned(), false)]
            };
            for (glob, excludes) in globs {
                let glob = if glob.ends_with('/') {
                    format!("{glob}**")
                } else {
                    glob
                };
                let glob = GlobBuilder::new(&glob)
                    .literal_separator(true)
                    .backslash_escape(true)
                    .build()?;
                if excludes && !negated {
                    excluded.add(glob);
                } else {
                    included.add(glob);
                }
            }
        }
        Ok(Self {
            included: included.build()?,
            excluded: excluded.build()?,
        })
    }

    /// Whether a negated group made it exclude anything: then what it matches
    /// below a directory can depend on more than that directory.
    pub fn excludes(&self) -> bool {
        !self.excluded.is_empty()
    }

    /// As Nx's glob sets: an including glob matches and no excluding one, or,
    /// with only excluding globs, none of them.
    pub fn is_match(&self, path: impl AsRef<std::path::Path>) -> bool {
        let path = path.as_ref();
        let excluded = self.excluded.is_match(path);
        if self.included.is_empty() {
            !excluded
        } else {
            !excluded && self.included.is_match(path)
        }
    }
}

/// `pattern` with every escaped character, and its `\`, left out, so what
/// remains is the syntax the pattern uses.
fn unescaped(pattern: &str) -> String {
    let mut result = String::new();
    let mut chars = pattern.chars();
    while let Some(c) = chars.next() {
        if c == '\\' {
            chars.next();
        } else {
            result.push(c);
        }
    }
    result
}

/// `path` with every character a pattern reads as syntax escaped, so that as
/// a pattern it names exactly that path.
pub fn escape(path: &str) -> String {
    let mut escaped = String::with_capacity(path.len());
    for c in path.chars() {
        if matches!(
            c,
            '*' | '?' | '[' | ']' | '{' | '}' | '(' | ')' | '!' | '@' | '+' | ',' | '|' | '\\'
        ) {
            escaped.push('\\');
        }
        escaped.push(c);
    }
    escaped
}

/// The path a pattern that [`names_a_path`] names: each `\` escape replaced
/// by the character it escapes.
pub fn literal_path(pattern: &str) -> String {
    let mut path = String::new();
    let mut chars = pattern.chars();
    while let Some(c) = chars.next() {
        path.push(if c == '\\' {
            chars.next().unwrap_or('\\')
        } else {
            c
        });
    }
    path
}

/// Whether `pattern` names a path rather than matching, as Nx 24 reads it:
/// nothing in it is glob syntax once its escapes are read. `@` and `+` start
/// a pattern only with a group after them, so `@types` and `c++` are names.
pub fn names_a_path(pattern: &str) -> bool {
    !unescaped(pattern).contains(['*', '?', '[', ']', '{', '}', '(', ')', '!'])
}

/// Whether a path segment needs matching rather than being a literal directory.
pub fn is_literal(segment: &str) -> bool {
    !segment.contains([
        '!', '?', '@', '+', '*', '|', ',', '{', '}', '[', ']', '(', ')', '\\',
    ])
}

#[derive(Debug, PartialEq)]
enum Group {
    /// `?(a|b)`, `*(a|b)` and `{,a}`: expanded as absent or once.
    Optional(String),
    /// `+(a|b)`, `@(a|b)` and `(a|b)`: expanded as exactly once.
    Once(String),
    /// `!(a|b)`.
    Negated(String),
    /// `!(a|b).`, which widens to `*.`.
    NegatedFileName(String),
    /// `!(a|b)*`, which widens to `*`.
    NegatedWildcard(String),
    Literal(String),
}

/// Expands one glob into plain globs, each with whether it excludes, sorted
/// and deduplicated like Nx's `convert_glob`. An excluding glob from a
/// directory segment ends there, with a `/`, and covers that directory.
fn expand(pattern: &str) -> Result<Vec<(String, bool)>> {
    let segments: Vec<_> = pattern.split('/').collect();
    let mut built = Vec::new();
    for (index, segment) in segments.iter().enumerate() {
        let groups = parse_segment(segment)
            .map_err(|error| anyhow::anyhow!("{error} in glob {pattern:?}"))?;
        built.push(build_segment(
            "",
            &groups,
            index == segments.len() - 1,
            false,
        ));
    }
    // Every combination of one option per segment, as Nx's cartesian product.
    let mut products: Vec<Vec<&(String, bool)>> = vec![Vec::new()];
    for options in &built {
        products = products
            .iter()
            .flat_map(|product| {
                options.iter().map(move |option| {
                    let mut next = product.clone();
                    next.push(option);
                    next
                })
            })
            .collect();
    }
    let mut globs: Vec<(String, bool)> = products
        .into_iter()
        .map(|product| {
            let mut path = String::new();
            let mut excludes = false;
            let mut whole = false;
            for (index, (segment, negative)) in product.iter().enumerate() {
                whole = index == product.len() - 1;
                path.push_str(segment);
                path.push('/');
                if *negative {
                    excludes = true;
                    if !whole {
                        break;
                    }
                }
            }
            if whole {
                path.pop();
            }
            (path, excludes)
        })
        .collect();
    globs.sort_by(|a, b| (!a.1, &a.0).cmp(&(!b.1, &b.0)));
    globs.dedup();
    Ok(globs)
}

fn parse_segment(segment: &str) -> Result<Vec<Group>> {
    let mut groups = Vec::new();
    let mut rest = segment;
    while !rest.is_empty() {
        // Nx drops `?`, `+` and `@` when no group follows, e.g. `+spec` means `spec`.
        if let Some(after) = rest.strip_prefix(['?', '+', '@'])
            && !after.is_empty()
            && !after.starts_with('(')
        {
            rest = after;
        }
        let parsed = [
            ("(", ")", false),
            ("*(", ")", true),
            ("?(", ")", true),
            ("+(", ")", false),
            ("@(", ")", false),
            ("{,", "}", true),
        ]
        .into_iter()
        .find_map(|(open, close, optional)| {
            let body = rest.strip_prefix(open)?;
            let end = body.find(close)?;
            let items = body[..end].split(['|', ',']).collect::<Vec<_>>().join(",");
            let group = if optional {
                Group::Optional(items)
            } else {
                Group::Once(items)
            };
            Some((group, &body[end + close.len()..]))
        })
        // Nx tries `!(…).`, then `!(…)*`, then `!(…)`.
        .or_else(|| {
            let body = rest.strip_prefix("!(")?;
            let end = body.find(')')?;
            let items = body[..end].split(['|', ',']).collect::<Vec<_>>().join(",");
            let after = &body[end + 1..];
            Some(if let Some(after) = after.strip_prefix('.') {
                (Group::NegatedFileName(items), after)
            } else if let Some(after) = after.strip_prefix('*') {
                (Group::NegatedWildcard(items), after)
            } else {
                (Group::Negated(items), after)
            })
        });
        if let Some((group, remaining)) = parsed {
            groups.push(group);
            rest = remaining;
            continue;
        }
        // A literal runs to the next `{,` or, without one, to the next special
        // character, and an escaped character is always literal.
        let end = literal_end(rest);
        if end == 0 {
            bail!("unsupported glob syntax at {rest:?}");
        }
        groups.push(Group::Literal(rest[..end].to_owned()));
        rest = &rest[end..];
    }
    Ok(groups)
}

/// Where a literal starting `rest` ends: at the next unescaped `{,`, or
/// without one at the next unescaped `?`, `+`, `@`, `!` or `(`.
fn literal_end(rest: &str) -> usize {
    let mut brace = None;
    let mut special = None;
    let mut chars = rest.char_indices();
    while let Some((index, c)) = chars.next() {
        match c {
            '\\' => {
                chars.next();
            }
            '{' if brace.is_none() && rest[index + 1..].starts_with(',') => brace = Some(index),
            '?' | '+' | '@' | '!' | '(' if special.is_none() => special = Some(index),
            _ => {}
        }
    }
    brace.or(special).unwrap_or(rest.len())
}

fn display(items: &str) -> String {
    if items.contains(',') {
        format!("{{{items}}}")
    } else {
        items.to_owned()
    }
}

/// A segment's options, each with whether a negated group made it one that
/// excludes: Nx's `build_segment`.
fn build_segment(
    existing: &str,
    groups: &[Group],
    is_last: bool,
    negative: bool,
) -> Vec<(String, bool)> {
    let Some((group, rest)) = groups.split_first() else {
        return vec![(existing.to_owned(), negative)];
    };
    // Nx widens an omitted group in a directory segment to the whole segment.
    let omitted = if is_last { existing } else { "*" };
    let both = |off: &str, on: &str, on_negative: bool| {
        let mut options = build_segment(off, rest, is_last, negative);
        options.extend(build_segment(on, rest, is_last, on_negative));
        options
    };
    match group {
        Group::Optional(items) => both(omitted, &format!("{existing}{}", display(items)), negative),
        Group::Negated(items) => both(omitted, &format!("{existing}{}", display(items)), true),
        Group::NegatedFileName(items) => {
            both("*.", &format!("{existing}{}.", display(items)), true)
        }
        Group::NegatedWildcard(items) => both("*", &format!("{existing}{}*", display(items)), true),
        Group::Once(items) => build_segment(
            &format!("{existing}{}", display(items)),
            rest,
            is_last,
            negative,
        ),
        Group::Literal(text) => {
            build_segment(&format!("{existing}{text}"), rest, is_last, negative)
        }
    }
}

#[cfg(test)]
mod tests {
    #[test]
    fn an_escaped_fileset_names_its_directory_exactly() {
        let named = super::Pattern::fileset(&super::escape("tmp/a!b (1)"), false).unwrap();
        assert!(named.is_match("tmp/a!b (1)/entry"));
        assert!(!named.is_match("tmp/ab 1/entry"));
    }

    use super::*;

    /// The expansion as Nx's `convert_glob` writes it, `!` for excluding.
    fn nx(pattern: &str) -> Vec<String> {
        expand(pattern)
            .unwrap()
            .into_iter()
            .map(|(glob, excludes)| if excludes { format!("!{glob}") } else { glob })
            .collect()
    }

    // Expected expansions are Nx 23.1's own glob_transform tests.
    #[test]
    fn expands_like_nx() {
        assert_eq!(
            nx("libs/**/?(*.)+spec.ts?(.snap)"),
            [
                "libs/**/*.spec.ts",
                "libs/**/*.spec.ts.snap",
                "libs/**/spec.ts",
                "libs/**/spec.ts.snap"
            ]
        );
        for pattern in [
            "libs/**/?(*.)@spec.ts?(.snap)",
            "libs/**/?(*.)?spec.ts?(.snap)",
        ] {
            assert_eq!(nx(pattern), nx("libs/**/?(*.)+spec.ts?(.snap)"));
        }
        assert_eq!(nx("dist/**/*.js"), ["dist/**/*.js"]);
        assert_eq!(nx("**/*.(js|ts)"), ["**/*.{js,ts}"]);
        assert_eq!(
            nx("**/*.spec.ts{,.snap}"),
            ["**/*.spec.ts", "**/*.spec.ts.snap"]
        );
    }

    #[test]
    fn expands_workspace_patterns() {
        assert_eq!(
            nx("app/**/?(*.)+(spec|test).[jt]s?(x)?(.snap)"),
            [
                "app/**/*.{spec,test}.[jt]s",
                "app/**/*.{spec,test}.[jt]s.snap",
                "app/**/*.{spec,test}.[jt]sx",
                "app/**/*.{spec,test}.[jt]sx.snap",
                "app/**/{spec,test}.[jt]s",
                "app/**/{spec,test}.[jt]s.snap",
                "app/**/{spec,test}.[jt]sx",
                "app/**/{spec,test}.[jt]sx.snap",
            ]
        );
        assert_eq!(nx("biome.json?(c)"), ["biome.json", "biome.jsonc"]);
        assert_eq!(nx("app/(.cache|dist)/**/*"), ["app/{.cache,dist}/**/*"]);
        // An omitted group in a directory segment widens it, as in Nx.
        assert_eq!(nx("a?(b)/c"), ["*/c", "ab/c"]);
    }

    #[test]
    fn rejects_what_nx_rejects() {
        assert!(expand("src/a!b").is_err());
        assert!(expand("file?").is_err());
        assert!(expand("src/(unterminated").is_err());
    }

    // Nx 23.1's own convert_glob tests.
    #[test]
    fn expands_negated_groups_like_nx() {
        assert_eq!(
            nx("dist/!(cache|cache2)/**/!(README|LICENSE).(js|ts)"),
            [
                "!dist/*/**/{README,LICENSE}.{js,ts}",
                "!dist/{cache,cache2}/",
                "dist/*/**/*.{js,ts}",
            ]
        );
        assert_eq!(
            nx("dist/**/!(README|LICENSE).(js|ts)"),
            ["!dist/**/{README,LICENSE}.{js,ts}", "dist/**/*.{js,ts}"]
        );
        assert_eq!(
            nx("dist/!(cache|cache2)/**/*.(js|ts)"),
            ["!dist/{cache,cache2}/", "dist/*/**/*.{js,ts}"]
        );
        assert_eq!(
            nx("dist/!(cache|cache2)/**/*.js"),
            ["!dist/{cache,cache2}/", "dist/*/**/*.js"]
        );
        assert_eq!(
            nx("packages/!(package-a)*"),
            ["!packages/package-a*", "packages/*"]
        );
        assert_eq!(
            nx("packages/!(package-a)*/package.json"),
            ["!packages/package-a*/", "packages/*/package.json"]
        );
        assert_eq!(nx("**/!(package-a)*"), ["!**/package-a*", "**/*"]);
        assert_eq!(
            nx("!(test|e2e)/?(*.)+(spec|test).[jt]s!(x)?(.snap)"),
            [
                "!*/*.{spec,test}.[jt]sx",
                "!*/*.{spec,test}.[jt]sx.snap",
                "!*/{spec,test}.[jt]sx",
                "!*/{spec,test}.[jt]sx.snap",
                "!{test,e2e}/",
                "*/*.{spec,test}.[jt]s",
                "*/*.{spec,test}.[jt]s.snap",
                "*/{spec,test}.[jt]s",
                "*/{spec,test}.[jt]s.snap",
            ]
        );
    }

    #[test]
    fn negated_groups_exclude_what_they_name() {
        let pattern = Pattern::new("src/**/!(*.test|*.spec).ts", false).unwrap();
        assert!(pattern.is_match("src/a/x.ts"));
        assert!(!pattern.is_match("src/a/x.test.ts") && !pattern.is_match("src/a/x.spec.ts"));
        let directories = Pattern::new("src/!(a|b)/*", false).unwrap();
        assert!(directories.is_match("src/c/z.md"));
        assert!(!directories.is_match("src/a/x.ts"));
        // As in Nx, a negated group after a literal in its segment leaves
        // only files ending in that literal.
        let odd = Pattern::new("src/**/*.!(ts)", false).unwrap();
        assert!(!odd.is_match("src/b/y.js") && !odd.is_match("src/b/y.ts"));
        // Negated as a whole, every expansion excludes.
        let whole = Pattern::new("src/**/!(*.test).ts", true).unwrap();
        assert!(whole.is_match("src/a/x.ts") && whole.is_match("src/a/x.test.ts"));
    }

    #[test]
    fn matches_expanded_patterns() {
        let tests = Pattern::new("app/**/?(*.)+(spec|test).[jt]s?(x)?(.snap)", true).unwrap();
        for path in [
            "app/a.spec.ts",
            "app/deep/b.test.jsx",
            "app/test.ts",
            "app/c.spec.tsx.snap",
        ] {
            assert!(tests.is_match(path), "{path}");
        }
        for path in ["app/a.ts", "app/a.spec.mts", "other/a.spec.ts"] {
            assert!(!tests.is_match(path), "{path}");
        }
        let plain = Pattern::new("src/*.ts", false).unwrap();
        assert!(plain.is_match("src/a.ts") && !plain.is_match("src/a/b.ts"));
    }

    // Nx 24's `a_backslash_escapes_the_next_character` and the inputs
    // reference: an escaped character matches itself on every platform.
    #[test]
    fn a_backslash_escapes_the_next_character() {
        let route = Pattern::new(r"app/\(marketing\)/**/*", false).unwrap();
        assert!(route.is_match("app/(marketing)/page.tsx"));
        assert!(!route.is_match("app/marketing/page.tsx"));
        let id = Pattern::new(r"src/\[id\].ts", false).unwrap();
        assert!(id.is_match("src/[id].ts") && !id.is_match("src/i.ts"));
        let mixed = Pattern::new(r"app/\(a\)/?(*.)+(spec|test).ts", false).unwrap();
        assert!(mixed.is_match("app/(a)/x.spec.ts") && !mixed.is_match("app/a/x.spec.ts"));
        // A Windows-style separator is an escape too, so this matches nothing
        // under `src`.
        assert!(!Pattern::new(r"src\**", false).unwrap().is_match("src/a.ts"));
    }

    // Nx 24's `path_or_everything_under`.
    #[test]
    fn a_fileset_path_with_no_pattern_names_a_file_or_a_directory() {
        for pattern in ["src", "src/"] {
            let fileset = Pattern::fileset(pattern, false).unwrap();
            assert!(fileset.is_match("src/a.ts") && fileset.is_match("src/deep/b.ts"));
            assert!(!fileset.is_match("srcs/a.ts"));
        }
        assert!(
            Pattern::fileset("package.json", false)
                .unwrap()
                .is_match("package.json")
        );
        for named in ["@types", "c++", r"\(group\)"] {
            let fileset = Pattern::fileset(named, false).unwrap();
            let unescaped = named.replace('\\', "");
            assert!(fileset.is_match(format!("{unescaped}/x")), "{named}");
        }
        // A pattern keeps matching only what it matches.
        let glob = Pattern::fileset("src/*.ts", false).unwrap();
        assert!(glob.is_match("src/a.ts") && !glob.is_match("src/a.ts/b"));
        assert!(!Pattern::new("src", false).unwrap().is_match("src/a.ts"));
    }

    // What Nx 23.1's own glob sets select from the same files.
    #[test]
    fn selects_the_files_nx_selects() {
        let files = [
            "src/a/x.ts",
            "src/a/x.test.ts",
            "src/a/x.spec.ts",
            "src/b/y.ts",
            "src/b/y.js",
            "src/c/deep/z.ts",
            "src/c/z.md",
            "src/root.ts",
            "src/README.md",
        ];
        let selected = |pattern: &str| -> Vec<&str> {
            let pattern = Pattern::new(pattern, false).unwrap();
            files
                .iter()
                .copied()
                .filter(|file| pattern.is_match(file))
                .collect()
        };
        assert_eq!(
            selected("src/**/!(*.test).ts"),
            [
                "src/a/x.ts",
                "src/a/x.spec.ts",
                "src/b/y.ts",
                "src/c/deep/z.ts",
                "src/root.ts"
            ]
        );
        assert_eq!(
            selected("src/!(a)/**"),
            ["src/b/y.ts", "src/b/y.js", "src/c/deep/z.ts", "src/c/z.md"]
        );
        assert_eq!(selected("src/**/*.!(ts)"), [] as [&str; 0]);
        assert_eq!(selected("src/!(a|b)/*"), ["src/c/z.md"]);
        assert_eq!(
            selected("src/*/!(x)*"),
            ["src/b/y.ts", "src/b/y.js", "src/c/z.md"]
        );
        assert_eq!(
            selected("src/**/!(*.test|*.spec).ts"),
            ["src/a/x.ts", "src/b/y.ts", "src/c/deep/z.ts", "src/root.ts"]
        );
    }
}