retex-kpath 1.3.0-alpha.2

//! Variable, default-path and brace expansion, as in kpathsea's `expand.c`.

use crate::SEP;

/// Maximum nesting of variable references before giving up (guards
/// against self-referential definitions).
const MAX_DEPTH: usize = 32;

/// Expands `$NAME` and `${NAME}` using `lookup`. Undefined variables expand
/// to nothing, as in kpathsea.
pub fn expand_vars(s: &str, lookup: &dyn Fn(&str) -> Option<String>, depth: usize) -> String {
    if depth > MAX_DEPTH || !s.contains('$') {
        return s.to_owned();
    }
    let mut out = String::with_capacity(s.len());
    let mut chars = s.char_indices().peekable();
    while let Some((i, c)) = chars.next() {
        if c != '$' {
            out.push(c);
            continue;
        }
        let rest = &s[i + 1..];
        let (name, consumed) = if let Some(inner) = rest.strip_prefix('{') {
            match inner.find('}') {
                Some(end) => (&inner[..end], end + 2),
                None => {
                    out.push('$');
                    continue;
                }
            }
        } else {
            let end = rest
                .find(|c: char| !(c.is_ascii_alphanumeric() || c == '_'))
                .unwrap_or(rest.len());
            (&rest[..end], end)
        };
        if name.is_empty() {
            out.push('$');
            continue;
        }
        if let Some(value) = lookup(name) {
            out.push_str(&expand_vars(&value, lookup, depth + 1));
        }
        // Skip the characters making up the reference.
        for _ in 0..consumed {
            chars.next();
        }
    }
    out
}

/// Inserts `default` at the first empty element of `path` (a leading,
/// trailing or doubled separator), as kpathsea does for environment
/// variables.
pub fn expand_default(path: &str, default: &str) -> String {
    if path.is_empty() {
        return default.to_owned();
    }
    if let Some(rest) = path.strip_prefix(SEP) {
        return format!("{default}{SEP}{rest}");
    }
    if let Some(rest) = path.strip_suffix(SEP) {
        return format!("{rest}{SEP}{default}");
    }
    if let Some(i) = path.find(&format!("{SEP}{SEP}")) {
        return format!("{}{SEP}{default}{SEP}{}", &path[..i], &path[i + 2..]);
    }
    path.to_owned()
}

/// Splits a path at separators ([`SEP`]) that are not inside braces, then
/// brace-expands each element. Empty elements are dropped.
pub fn brace_expand_path(path: &str) -> Vec<String> {
    let mut out = Vec::new();
    for elt in split_top_level(path, SEP) {
        for e in brace_expand(elt) {
            if !e.is_empty() {
                out.push(e);
            }
        }
    }
    out
}

/// Expands `a{b,c}d` into `abd`, `acd`; braces nest. As in kpathsea, the
/// *last* brace group varies slowest: `{a,b}/{x,y}` gives `a/x`, `b/x`,
/// `a/y`, `b/y`. Elements of a brace list may contain `:` separators, which
/// then produce several path elements.
pub fn brace_expand(s: &str) -> Vec<String> {
    let Some((open, close)) = last_top_level_group(s) else {
        return split_top_level(s, SEP)
            .into_iter()
            .map(str::to_owned)
            .collect();
    };
    let prefix = &s[..open];
    let inner = &s[open + 1..close];
    let suffix = &s[close + 1..];
    let prefixes = brace_expand_keep_empty(prefix);
    let mut out = Vec::new();
    for alt in split_top_level(inner, ',') {
        for a in brace_expand_keep_empty(alt) {
            for p in &prefixes {
                out.extend(
                    split_top_level(&format!("{p}{a}{suffix}"), SEP)
                        .into_iter()
                        .map(str::to_owned),
                );
            }
        }
    }
    out
}

/// Like [`brace_expand`] but without splitting at `:` and keeping empty
/// results (an empty prefix is a valid expansion).
fn brace_expand_keep_empty(s: &str) -> Vec<String> {
    let Some((open, close)) = last_top_level_group(s) else {
        return vec![s.to_owned()];
    };
    let prefix = &s[..open];
    let inner = &s[open + 1..close];
    let suffix = &s[close + 1..];
    let prefixes = brace_expand_keep_empty(prefix);
    let mut out = Vec::new();
    for alt in split_top_level(inner, ',') {
        for a in brace_expand_keep_empty(alt) {
            for p in &prefixes {
                out.push(format!("{p}{a}{suffix}"));
            }
        }
    }
    out
}

/// Byte offsets of the last top-level `{`…`}` group.
fn last_top_level_group(s: &str) -> Option<(usize, usize)> {
    let mut depth = 0i32;
    let mut open = None;
    let mut last = None;
    for (i, b) in s.bytes().enumerate() {
        match b {
            b'{' => {
                if depth == 0 {
                    open = Some(i);
                }
                depth += 1;
            }
            b'}' if depth > 0 => {
                depth -= 1;
                if depth == 0 {
                    last = open.map(|o| (o, i));
                }
            }
            _ => {}
        }
    }
    last
}

fn split_top_level(s: &str, sep: char) -> Vec<&str> {
    let mut out = Vec::new();
    let mut depth = 0i32;
    let mut start = 0;
    for (i, c) in s.char_indices() {
        match c {
            '{' => depth += 1,
            '}' => depth -= 1,
            c if c == sep && depth == 0 => {
                out.push(&s[start..i]);
                start = i + 1;
            }
            _ => {}
        }
    }
    out.push(&s[start..]);
    out
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn variables() {
        let lookup = |n: &str| match n {
            "A" => Some("x$B".to_owned()),
            "B" => Some("y".to_owned()),
            _ => None,
        };
        assert_eq!(expand_vars("$A/${B}z/$C.", &lookup, 0), "xy/yz/.");
    }

    #[test]
    fn braces() {
        assert_eq!(brace_expand("a{b,c}d"), vec!["abd", "acd"]);
        assert_eq!(brace_expand("{{}x,y}/t"), vec!["x/t", "y/t"]);
        assert_eq!(
            brace_expand("/r/{a,b{1,2}}/"),
            vec!["/r/a/", "/r/b1/", "/r/b2/"]
        );
        assert_eq!(
            brace_expand("{a,b}/{x,y}"),
            vec!["a/x", "b/x", "a/y", "b/y"]
        );
        assert_eq!(
            brace_expand_path(&format!(".{SEP}{{/a,!!/b}}/tex//")),
            vec![".", "/a/tex//", "!!/b/tex//"]
        );
    }

    #[test]
    fn defaults() {
        let s = |t: &str| t.replace(':', &SEP.to_string());
        assert_eq!(expand_default(&s(":x"), "D"), s("D:x"));
        assert_eq!(expand_default(&s("x:"), "D"), s("x:D"));
        assert_eq!(expand_default(&s("x::y"), "D"), s("x:D:y"));
        assert_eq!(expand_default("x", "D"), "x");
    }
}