fm84 0.41.0

//! Shell-style patterns, for selecting files by name with + and -, and for
//! narrowing a panel with Ctrl+S. Small enough to write rather than bring in
//! a crate for.

/// One or more patterns, separated by `;` - "*.jpg;*.png". `*` is any run of
/// characters, `?` any one, `[abc]` and `[a-z]` one of those, `[!abc]` one
/// that is not. Unlike the shell's, `*` matches a leading dot too: hidden
/// files are files like any other here.
///
/// Smart case, as Find is: all in lower case matches either case, and a
/// capital anywhere makes the match exact.
///
/// A pattern ending in `/` is for directories - `*/` is every one of them -
/// and one without is for files, so that `+` then Enter on `*` takes the files
/// and leaves the directories, whose selection would sweep whole trees into
/// the next copy or delete.
///
/// Under Ctrl+B a name is a path through the directories below, as
/// `sub/a.txt`, and a pattern is matched against the file's own name, as
/// anywhere else: `test_*` is every test file, however deep. One with a `/` before
/// its end, `src/*.rs`, is about the path, and is matched against all of it;
/// so is a plain word typed into the filter, which looks anywhere.
pub struct Glob {
    patterns: Vec<Pattern>,
    fold: bool,
    /// A pattern without the `/` takes directories too, as the filter has it.
    either: bool,
}

impl Glob {
    /// None when there is no pattern in it at all.
    pub fn new(text: &str) -> Option<Self> {
        Self::parse(text, false, &[])
    }

    /// Ctrl+S's filter, which narrows a panel rather than picking from it: a
    /// pattern without `/` keeps the directories it matches as well as the
    /// files, and one with nothing wild in it - `rep` - is looked for
    /// anywhere in the name, as `*rep*`.
    pub fn filter(text: &str) -> Option<Self> {
        let mut plain = Vec::new();
        let widened: Vec<String> = text
            .split(';')
            .map(|pattern| {
                let trimmed = pattern.trim();
                let (name, slash) = trimmed.strip_suffix('/').map_or((trimmed, ""), |name| (name, "/"));
                if name.is_empty() {
                    return trimmed.to_string();
                }
                let wild = name.contains(['*', '?', '[']);
                plain.push(!wild);
                if wild { trimmed.to_string() } else { format!("*{name}*{slash}") }
            })
            .collect();
        Self::parse(&widened.join(";"), true, &plain)
    }

    /// `plain` says, pattern by pattern, which were plain words widened to
    /// look anywhere - and so anywhere in a path too.
    fn parse(text: &str, either: bool, plain: &[bool]) -> Option<Self> {
        let fold = !text.chars().any(char::is_uppercase);
        let patterns: Vec<Pattern> = text
            .split(';')
            .map(str::trim)
            .filter(|pattern| !pattern.is_empty())
            .map(|pattern| match pattern.strip_suffix('/') {
                Some(directory) => (directory, true),
                None => (pattern, false),
            })
            .filter(|(pattern, _)| !pattern.is_empty())
            .enumerate()
            .map(|(index, (pattern, for_dirs))| Pattern {
                // Either separator, typed, stands for the one the names have.
                chars: pattern.chars().map(|c| if std::path::is_separator(c) { '/' } else { fold_if(c, fold) }).collect(),
                for_dirs,
                whole: pattern.contains(std::path::is_separator) || plain.get(index).copied().unwrap_or(false),
            })
            .collect();
        if patterns.is_empty() { None } else { Some(Glob { patterns, fold, either }) }
    }

    pub fn matches(&self, name: &str, is_dir: bool) -> bool {
        let path: Vec<char> = name.chars().map(|c| if std::path::is_separator(c) { '/' } else { fold_if(c, self.fold) }).collect();
        let leaf = &path[path.iter().rposition(|&c| c == '/').map_or(0, |at| at + 1)..];
        self.patterns
            .iter()
            .any(|pattern| (pattern.for_dirs == is_dir || (self.either && !pattern.for_dirs)) && matches(&pattern.chars, if pattern.whole { &path } else { leaf }))
    }
}

struct Pattern {
    chars: Vec<char>,
    /// Ended in `/`: for directories.
    for_dirs: bool,
    /// Matched against the whole of a path, rather than its last name.
    whole: bool,
}

fn fold_if(c: char, fold: bool) -> char {
    if fold { crate::find::fold_char(c) } else { c }
}

/// The usual backtracking match: on a mismatch, let the last `*` take one more
/// character and carry on from there. Linear in practice, and never worse
/// than the pattern's length times the name's.
fn matches(pattern: &[char], name: &[char]) -> bool {
    let (mut p, mut n) = (0, 0);
    let mut star: Option<(usize, usize)> = None;
    while n < name.len() {
        if p < pattern.len() {
            match pattern[p] {
                '*' => {
                    star = Some((p, n));
                    p += 1;
                    continue;
                }
                '?' => {
                    p += 1;
                    n += 1;
                    continue;
                }
                '[' => {
                    if let Some((hit, next)) = class(pattern, p, name[n]) {
                        if hit {
                            p = next;
                            n += 1;
                            continue;
                        }
                    } else if name[n] == '[' {
                        // Never closed, so it is only a bracket.
                        p += 1;
                        n += 1;
                        continue;
                    }
                }
                c if c == name[n] => {
                    p += 1;
                    n += 1;
                    continue;
                }
                _ => {}
            }
        }
        match star {
            Some((star_p, star_n)) => {
                star = Some((star_p, star_n + 1));
                p = star_p + 1;
                n = star_n + 1;
            }
            None => return false,
        }
    }
    pattern[p..].iter().all(|&c| c == '*')
}

/// Whether `c` is in the class opening at `pattern[open]`, and where the
/// pattern goes on after it. None when the class is never closed.
fn class(pattern: &[char], open: usize, c: char) -> Option<(bool, usize)> {
    let mut index = open + 1;
    let negated = matches!(pattern.get(index), Some('!' | '^'));
    if negated {
        index += 1;
    }
    let mut hit = false;
    let mut first = true;
    loop {
        let &start = pattern.get(index)?;
        // A ] straight after the opening is one of the class, not its end.
        if start == ']' && !first {
            return Some((hit != negated, index + 1));
        }
        first = false;
        if pattern.get(index + 1) == Some(&'-') && pattern.get(index + 2).is_some_and(|&end| end != ']') {
            hit |= (start..=pattern[index + 2]).contains(&c);
            index += 3;
        } else {
            hit |= start == c;
            index += 1;
        }
    }
}

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

    fn file(pattern: &str, name: &str) -> bool {
        Glob::new(pattern).unwrap().matches(name, false)
    }

    #[test]
    fn stars_and_question_marks() {
        assert!(file("*", "anything"));
        assert!(file("*", ".hidden"));
        assert!(file("*.rs", "main.rs"));
        assert!(!file("*.rs", "main.rsx"));
        assert!(file("a*b*c", "aXXbYYc"));
        assert!(!file("a*b*c", "aXXbYY"));
        assert!(file("?.txt", "a.txt"));
        assert!(!file("?.txt", "ab.txt"));
        assert!(file("**x", "x"));
    }

    #[test]
    fn classes() {
        assert!(file("[abc].txt", "b.txt"));
        assert!(!file("[abc].txt", "d.txt"));
        assert!(file("file[0-9]", "file7"));
        assert!(!file("file[!0-9]", "file7"));
        assert!(file("file[!0-9]", "fileX"));
        assert!(file("[]]", "]"));
        assert!(file("[a-]", "-"));
        // Never closed, so a plain bracket.
        assert!(file("[ab", "[ab"));
    }

    #[test]
    fn smart_case_as_find_does() {
        assert!(file("*.jpg", "PHOTO.JPG"));
        assert!(file("*.JPG", "PHOTO.JPG"));
        assert!(!file("*.JPG", "photo.jpg"));
    }

    #[test]
    fn several_patterns_and_directories_apart() {
        let glob = Glob::new("*.jpg; *.png").unwrap();
        assert!(glob.matches("a.png", false));
        assert!(glob.matches("b.jpg", false));
        assert!(!glob.matches("c.gif", false));

        let files = Glob::new("*").unwrap();
        assert!(!files.matches("src", true));
        let dirs = Glob::new("*/").unwrap();
        assert!(dirs.matches("src", true));
        assert!(!dirs.matches("main.rs", false));

        assert!(Glob::new("").is_none());
        assert!(Glob::new(" ; /").is_none());
    }

    #[test]
    fn the_filter_looks_anywhere_in_the_name_and_takes_directories_too() {
        let plain = Glob::filter("rep").unwrap();
        assert!(plain.matches("report.txt", false));
        assert!(plain.matches("Prep", false));
        assert!(plain.matches("repos", true));
        assert!(!plain.matches("main.rs", false));

        let wild = Glob::filter("*.rs").unwrap();
        assert!(wild.matches("main.rs", false));
        assert!(!wild.matches("main.rsx", false));
        assert!(wild.matches("crate.rs", true));

        let dirs = Glob::filter("src/").unwrap();
        assert!(dirs.matches("src", true));
        assert!(dirs.matches("old-src", true));
        assert!(!dirs.matches("src", false));

        // Under Ctrl+B: a pattern by the file's own name, one with a / in it
        // or a plain word by the path.
        let sep = std::path::MAIN_SEPARATOR;
        let deep = format!("src{sep}tests{sep}test_one.rs");
        assert!(Glob::filter("test_*").unwrap().matches(&deep, false));
        assert!(Glob::new("test_*").unwrap().matches(&deep, false));
        assert!(Glob::new("[s-u]*.rs").unwrap().matches(&deep, false));
        assert!(!Glob::new("s*").unwrap().matches(&deep, false));
        assert!(Glob::new("src/*/*.rs").unwrap().matches(&deep, false));
        assert!(!Glob::new("tests/*").unwrap().matches(&deep, false));
        assert!(Glob::filter("tests").unwrap().matches(&deep, false));
        assert!(Glob::filter("tests/test_*").is_some_and(|glob| !glob.matches(&deep, false)));
        assert!(Glob::filter("*tests/test_*").unwrap().matches(&deep, false));

        let several = Glob::filter("toml; *.md").unwrap();
        assert!(several.matches("Cargo.toml", false));
        assert!(several.matches("README.md", false));
        assert!(Glob::filter(" ; ").is_none());
    }

    #[test]
    fn a_caret_negates_as_an_exclamation_mark_does() {
        assert!(file("[^0-9]x", "ax"));
        assert!(!file("[^0-9]x", "1x"));
    }

    #[test]
    fn a_question_mark_is_one_character_not_one_byte() {
        assert!(file("caf?", "café"));
        assert!(file("??", "日本"));
        assert!(!file("?", "日本"));
    }

    #[test]
    fn many_stars_against_a_long_name_that_misses_still_ends() {
        let name = "a".repeat(10_000);
        let started = std::time::Instant::now();
        assert!(!file("*a*a*a*a*a*b", &name));
        assert!(started.elapsed() < std::time::Duration::from_secs(1), "{:?}", started.elapsed());
    }
}