packages /

glob 0.1.0

Glob patterns for file paths: *, ?, [...], ** and {a,b}.

files / src/lib.auk 16.4 kB · 543 lines

/// Glob patterns for paths: `*`, `?`, `[...]`, `**` and `{a,b}`. Matching is pure; only `walk`
/// and `find`, which list directories, use `fs`. Paths use `/` separators, and matching is
/// case-sensitive. A wildcard never matches a `/`, and never matches a leading `.` (hidden
/// files) unless the pattern spells the dot out.

// One token of a path segment pattern.
enum Tok {
  Lit(c: char),
  One,                              // ?
  Star,                             // *
  Class(neg: bool, ranges: [int]),  // [a-z_] as flat [lo, hi, lo, hi, ...] code points
}

// One `/`-separated part of a pattern.
enum Seg { Deep, Part(toks: [Tok]) }  // Deep is `**`: zero or more whole segments

/// A compiled pattern, for matching many paths: `let g = glob.compile("**/*.auk")`. Every
/// string is a valid pattern (see `matches`), so compiling never fails.
pub struct Glob { rooted: bool, alts: [[Seg]] }

/// Compiles a pattern once: `{a,b}` alternatives are expanded and each `/`-separated part is
/// tokenized.
pub fn compile(pattern: str): Glob {
  let alts = expand(pattern).map(p => segments(p).map(seg))
  Glob { rooted: pattern.starts_with("/"), alts }
}

/// Does `path` match `pattern`? Syntax:
/// - `?` any one char, `*` any run of chars (both within one path segment, never `/`)
/// - `[abc]`, `[a-z0-9]`, `[!a]` or `[^a]` one char from (or not from) a set; `]` first in the
///   set is literal, as is `-` first or last
/// - `**` as a whole segment: zero or more segments (`src/**/*.auk` also matches `src/a.auk`)
/// - `{a,b,c}` alternatives, which may nest and may contain `/` and other wildcards
/// - `\x` matches `x` literally
/// An unclosed `[` or a `{` without a top-level `,` and closing `}` is matched literally. Hidden
/// segments (starting with `.`) only match a pattern segment that starts with a literal `.`.
/// Leading `./` and repeated `/` are ignored on both sides; a pattern starting with `/` matches
/// only absolute paths and vice versa. A trailing `/` is ignored.
pub fn matches(pattern: str, path: str): bool = matches(compile(pattern), path)
/// `matches` with a compiled pattern.
pub fn matches(g: Glob, path: str): bool {
  if path.starts_with("/") != g.rooted { return false }
  let segs = segments(path)
  g.alts.any(a => match_segs(a, 0, segs, 0))
}

/// Does `s` use any glob syntax (`* ? [ { \`)? A string without it only matches itself.
pub fn is_pattern(s: str): bool = s.chars().any(c => "*?[{{\\".contains(c))

/// `s` with every glob special char escaped, so it matches only itself: `escape("a*b") == "a\\*b"`.
pub fn escape(s: str): str {
  var out: [char] = []
  for c in s.chars() {
    if "*?[]{{}}\\,".contains(c) { out.push('\\') }
    out.push(c)
  }
  str(out)
}

// ---- walking the file system ----

/// The deepest directory level `walk` descends to (guards against symlink cycles, which `fs`
/// can't detect).
pub let MAX_DEPTH = 64

/// Every file and directory under `dir` whose path relative to `dir` matches `pattern`, e.g.
/// `walk("src", "**/*.auk")` -> `["lib.auk", "net/tcp.auk"]`. Paths are relative to `dir`,
/// joined with `/`, in walk order (each directory's entries sorted by name, a directory's
/// contents right after it). Only directories that could still match are opened, so hidden
/// directories like `.git` are skipped unless the pattern names them. Symlinks are followed.
pub fn walk(dir: str, pattern: str): [str]! uses fs {
  let g = compile(pattern)
  var out: [str] = []
  visit(dir.trim_end_slash(), "", [], g, &out)?
  out
}

/// Every path matching a pattern that starts with its own base directory, relative to the
/// working directory: `find("src/**/*.auk")` walks `src` and returns `src/...` paths.
/// A pattern without glob syntax gives `[pattern]` if that path exists, else `[]`.
pub fn find(pattern: str): [str]! uses fs {
  if !is_pattern(pattern) { return if fs.exists(pattern) { [pattern] } else { [] } }
  let parts = pattern.split("/")
  let n = parts.find_index(p => is_pattern(p))!
  let base = parts.take(n).join("/")
  let rest = parts.skip(n).join("/")
  if n == 0 { return walk(".", pattern) }
  let root = if base == "" { "/" } else { base }  // "/x/*": base "" means the root
  if !fs.is_dir(root) { return [] }
  let prefix = if root.ends_with("/") { root } else { root + "/" }
  (walk(root, rest)?).map(p => prefix + p)
}

fn visit(dir: str, rel: str, segs: [str], g: Glob, out: var [str]): ()! uses fs {
  if segs.len() >= MAX_DEPTH { return }
  let here = if rel == "" { dir } else { dir + "/" + rel }
  for name in fs.list(here)? {
    let r = if rel == "" { name } else { rel + "/" + name }
    let s = segs + [name]
    if g.alts.any(a => match_segs(a, 0, s, 0)) { out.push(r) }
    if g.alts.any(a => can_extend(a, 0, s, 0)) && fs.is_dir(here + "/" + name) {
      visit(dir, r, s, g, &out)?
    }
  }
}

fn trim_end_slash(s: str): str {
  var t = s
  while t.len() > 1 && t.ends_with("/") { t = t[0..t.len() - 1] }
  t
}

// ---- matching ----

// Path segments, without empty ones and a leading `.`.
fn segments(p: str): [str] {
  let parts = p.split("/").filter(s => s != "")
  if parts.len() > 0 && parts[0] == "." { parts.skip(1) } else { parts }
}

fn match_segs(ps: [Seg], pi: int, segs: [str], si: int): bool {
  if pi == ps.len() { return si == segs.len() }
  match ps[pi] {
    Deep => {
      var k = si
      loop {
        if match_segs(ps, pi + 1, segs, k) { return true }
        if k == segs.len() || segs[k].starts_with(".") { return false }
        k += 1
      }
    }
    Part(toks) =>
      si < segs.len() && match_part(toks, segs[si]) && match_segs(ps, pi + 1, segs, si + 1)
  }
}

// Could some path that starts with `segs` (and goes deeper) match? Decides which directories
// `walk` opens.
fn can_extend(ps: [Seg], pi: int, segs: [str], si: int): bool {
  if pi == ps.len() { return false }
  if si == segs.len() { return true }
  match ps[pi] {
    Deep => can_extend(ps, pi + 1, segs, si) ||
      (!segs[si].starts_with(".") && can_extend(ps, pi, segs, si + 1))
    Part(toks) => match_part(toks, segs[si]) && can_extend(ps, pi + 1, segs, si + 1)
  }
}

// One segment against its tokens: linear-time star backtracking (only the last `*` is retried).
fn match_part(toks: [Tok], seg: str): bool {
  let cs = seg.chars()
  if cs.len() > 0 && cs[0] == '.' && !(toks.first() is some(Lit('.'))) { return false }
  var t = 0
  var c = 0
  var star_t = -1
  var star_c = 0
  while c < cs.len() {
    if t < toks.len() && toks[t] is Star {
      star_t = t
      star_c = c
      t += 1
    } else if t < toks.len() && one(toks[t], cs[c]) {
      t += 1
      c += 1
    } else if star_t >= 0 {
      star_c += 1
      c = star_c
      t = star_t + 1
    } else {
      return false
    }
  }
  while t < toks.len() && toks[t] is Star { t += 1 }
  t == toks.len()
}

fn one(t: Tok, c: char): bool = match t {
  Lit(l) => l == c
  One => true
  Star => true
  Class(neg, rs) => in_class(rs, int(c)) != neg
}

fn in_class(rs: [int], cp: int): bool {
  var i = 0
  while i < rs.len() {
    if cp >= rs[i] && cp <= rs[i + 1] { return true }
    i += 2
  }
  false
}

// ---- parsing ----

fn seg(s: str): Seg {
  if s == "**" { return Deep }
  let cs = s.chars()
  var toks: [Tok] = []
  var i = 0
  while i < cs.len() {
    let c = cs[i]
    if c == '\\' && i + 1 < cs.len() {
      toks.push(Lit(cs[i + 1]))
      i += 2
    } else if c == '*' {
      if !(toks.last() is some(Star)) { toks.push(Star) }
      i += 1
    } else if c == '?' {
      toks.push(One)
      i += 1
    } else if c == '[' {
      match class(cs, i) {
        some((t, next)) => {
          toks.push(t)
          i = next
        }
        none => {
          toks.push(Lit('['))
          i += 1
        }
      }
    } else {
      toks.push(Lit(c))
      i += 1
    }
  }
  Part(toks)
}

// A `[...]` set starting at cs[at] == '[': the token and the index after `]`, or none if the
// set is never closed.
fn class(cs: [char], at: int): (Tok, int)? {
  var i = at + 1
  var neg = false
  if i < cs.len() && (cs[i] == '!' || cs[i] == '^') {
    neg = true
    i += 1
  }
  var rs: [int] = []
  var first = true
  while i < cs.len() {
    var c = cs[i]
    if c == ']' && !first { return some((Class(neg, rs), i + 1)) }
    first = false
    if c == '\\' && i + 1 < cs.len() {
      i += 1
      c = cs[i]
    }
    if i + 2 < cs.len() && cs[i + 1] == '-' && cs[i + 2] != ']' {
      var hi = cs[i + 2]
      var skip = 3
      if hi == '\\' && i + 3 < cs.len() {
        hi = cs[i + 3]
        skip = 4
      }
      rs = rs + [int(c), int(hi)]
      i += skip
    } else {
      rs = rs + [int(c), int(c)]
      i += 1
    }
  }
  none
}

// Brace expansion: every alternative spelled out, left to right (`a{b,c}d` -> abd, acd).
// A `{` without a matching `}` and a top-level `,` stays literal, as in bash.
fn expand(p: str): [str] {
  let cs = p.chars()
  var i = 0
  while i < cs.len() {
    let c = cs[i]
    if c == '\\' {
      i += 2
      continue
    }
    if c == '{' {
      match brace_body(cs, i) {
        some((alts, close)) => {
          let pre = str(cs.take(i))
          let post = str(cs.skip(close + 1))
          // `pre` holds no expandable braces; `post` and the alternatives are expanded next
          return alts.flat_map(a => expand(a + post).map(rest => pre + rest))
        }
        none => {}
      }
    }
    i += 1
  }
  [p]
}

// The top-level alternatives of the `{...}` opening at cs[at], and the index of its `}`.
fn brace_body(cs: [char], at: int): ([str], int)? {
  var depth = 0
  var alts: [str] = []
  var cur: [char] = []
  var i = at + 1
  while i < cs.len() {
    let c = cs[i]
    if c == '\\' && i + 1 < cs.len() {
      cur.push(c)
      cur.push(cs[i + 1])
      i += 2
      continue
    }
    if c == '{' { depth += 1 }
    if c == '}' {
      if depth == 0 {
        if alts.len() == 0 { return none }  // `{a}`: no comma, literal
        alts.push(str(cur))
        return some((alts, i))
      }
      depth -= 1
    }
    if c == ',' && depth == 0 {
      alts.push(str(cur))
      cur = []
    } else {
      cur.push(c)
    }
    i += 1
  }
  none
}

// ---- tests ----

test "wildcards within a segment" {
  let yes = [
    ("*", "a"),
    ("*", "abc"),
    ("*.auk", "lib.auk"),
    ("*.auk", "a.auk.auk"),
    ("a*", "a"),
    ("*a*b*c*", "xaybzc"),
    ("?", "x"),
    ("??.txt", "ab.txt"),
    ("a?c", "abc"),
    ("*x", "xxxx"),
    ("a*a*a*a*b", "aaaaaaaaaaaaaaaaab"),
    ("日*", "日本"),
    ("?", "本"),
    ("", ""),
    ("**", ""),
    ("abc", "abc"),
  ]
  let no = [
    ("*", ""),
    ("*.auk", "lib.duc"),
    ("?", ""),
    ("?", "ab"),
    ("a?c", "ac"),
    ("abc", "abd"),
    ("*", "a/b"),
    ("a*b", "a/b"),
    ("?", "/"),
    ("a*a*a*a*b", "aaaaaaaaaaaaaaaaaa"),
    ("ABC", "abc"),
    ("*.auk", ".x.auk"),
  ]
  for (p, s) in yes { assert matches(p, s) }
  for (p, s) in no { assert !matches(p, s) }
}

test "character classes" {
  let yes = [
    ("[abc]", "b"),
    ("[a-z]", "q"),
    ("[a-z0-9_]x", "_x"),
    ("[!a]", "b"),
    ("[^a]", "b"),
    ("[]]", "]"),
    ("[]a]", "a"),
    ("[!]]", "x"),
    ("[-a]", "-"),
    ("[a-]", "-"),
    ("[\\]]", "]"),
    ("file[0-9].txt", "file7.txt"),
    ("[[]", "["),
    ("[*?]", "*"),
    ("[α-ω]", "λ"),
  ]
  let no = [
    ("[abc]", "d"),
    ("[a-z]", "A"),
    ("[!a]", "a"),
    ("[^a-c]", "b"),
    ("[a-]", "b"),
    ("[!/]", "/"),
    ("[*]", "x"),
    ("file[0-9].txt", "filex.txt"),
  ]
  for (p, s) in yes { assert matches(p, s) }
  for (p, s) in no { assert !matches(p, s) }
  // an unclosed `[` is a literal
  assert matches("a[b", "a[b") && !matches("a[b", "ab")
}

test "paths and **" {
  let yes = [
    ("src/*.auk", "src/a.auk"),
    ("src/**/*.auk", "src/a.auk"),
    ("src/**/*.auk", "src/x/y/z.auk"),
    ("**/*.auk", "a.auk"),
    ("**/*.auk", "a/b/c.auk"),
    ("**", "a/b/c"),
    ("a/**", "a"),
    ("a/**", "a/b/c"),
    ("a/**/b", "a/b"),
    ("a/**/b", "a/x/y/b"),
    ("**/test/**", "x/test/y"),
    ("*/*", "a/b"),
    ("./src/*.auk", "src/a.auk"),
    ("src/*.auk", "./src/a.auk"),
    ("src//*.auk", "src/a.auk"),
    ("src/", "src"),
    ("/tmp/*", "/tmp/x"),
    ("a/**/**/b", "a/b"),
  ]
  let no = [
    ("src/*.auk", "src/x/a.auk"),
    ("src/*.auk", "lib/a.auk"),
    ("*/*", "a"),
    ("*/*", "a/b/c"),
    ("a/**/b", "a/bc"),
    ("**/*.auk", "a/b.txt"),
    ("/tmp/*", "tmp/x"),
    ("tmp/*", "/tmp/x"),
    ("a/**", "b/a"),
  ]
  for (p, s) in yes { assert matches(p, s) }
  for (p, s) in no { assert !matches(p, s) }
  // `**` inside a longer segment is just `*`
  assert matches("a**b", "axxb") && !matches("a**b", "ax/xb")
}

test "hidden files" {
  assert !matches("*", ".hidden")
  assert !matches("?hidden", ".hidden")
  assert !matches("[.]hidden", ".hidden")
  assert matches(".*", ".hidden") && matches(".h*", ".hidden")
  assert !matches("**/*.auk", ".git/x.auk")
  assert !matches("**/*.auk", "a/.cache/x.auk")
  assert matches("**/.cache/*.auk", "a/.cache/x.auk")
  assert matches(".git/**", ".git/objects/ab")
  assert !matches("*", ".") && !matches("*", "..")
  assert matches("a.*", "a.txt")  // only a leading dot is special
}

test "braces" {
  assert expand(r"a{b,c}d") == ["abd", "acd"]
  assert expand(r"{a,b}{1,2}") == ["a1", "a2", "b1", "b2"]
  assert expand(r"{a,{b,c}x}") == ["a", "bx", "cx"]
  assert expand(r"{,s}") == ["", "s"]
  assert expand(r"{a}") == [r"{a}"]    // no comma: literal
  assert expand(r"{a,b") == [r"{a,b"]  // unclosed: literal
  assert expand(r"\{a,b}") == [r"\{a,b}"]
  assert expand(r"x{a\,b,c}") == ["xa\\,b", "xc"]
  let yes = [
    (r"*.{auk,toml}", "raft.toml"),
    (r"*.{auk,toml}", "lib.auk"),
    (r"{src,lib}/*.auk", "lib/a.auk"),
    (r"{src/**/,}*.auk", "src/x/a.auk"),
    (r"{src/**/,}*.auk", "a.auk"),
    (r"file{,.bak}", "file"),
    (r"file{,.bak}", "file.bak"),
    (r"{a}", r"{a}"),
    (r"x{1,2}{a,b}", "x2a"),
    (r"{[ab],c}", "b"),
  ]
  let no = [(r"*.{auk,toml}", "a.json"), (r"{src,lib}/*.auk", "test/a.auk"), (r"{a}", "a")]
  for (p, s) in yes { assert matches(p, s) }
  for (p, s) in no { assert !matches(p, s) }
}

test "escapes" {
  assert matches("a\\*b", "a*b") && !matches("a\\*b", "axb")
  assert matches("\\?", "?") && !matches("\\?", "x")
  assert matches("\\[x]", "[x]")
  assert matches(r"\{a,b}", r"{a,b}")
  assert escape(r"a*b?[c]{d,e}") == r"a\*b\?\[c\]\{d\,e\}"
  assert escape("\\") == "\\\\"
  for s in ["a*b", "[x]", r"{a,b}", "c:\\dir", "plain.txt", "?"] {
    assert matches(escape(s), s)
    assert !is_pattern(s) || is_pattern(escape(s))
  }
  assert !matches(escape("a*"), "ab")
  assert is_pattern("*.auk") && is_pattern(r"a{b,c}") && !is_pattern("src/lib.auk")
}

test "compiled patterns" {
  let g = compile(r"**/*.{auk,toml}")
  let paths = ["raft.toml", "src/lib.auk", "src/x.rs", ".git/config.toml", "README.md"]
  assert paths.filter(p => matches(g, p)) == ["raft.toml", "src/lib.auk"]
}

test "walk and find in a temp dir" {
  let root = fs.temp_dir()?
  for d in ["src", "src/net", "src/.cache", ".git", "docs", "a.b"] { fs.mkdir("{root}/{d}")? }
  let files = [
    "raft.toml",
    "README.md",
    "src/lib.auk",
    "src/util.auk",
    "src/net/tcp.auk",
    "src/net/notes.txt",
    "src/.cache/old.auk",
    ".git/HEAD",
    "docs/guide.md",
    "a.b/c.auk",
    ".env",
  ]
  for f in files { fs.write("{root}/{f}", "x")? }

  assert walk(root, "**/*.auk")? == ["a.b/c.auk", "src/lib.auk", "src/net/tcp.auk", "src/util.auk"]
  assert walk(root, "src/*.auk")? == ["src/lib.auk", "src/util.auk"]
  assert walk(root, "*")? == ["README.md", "a.b", "docs", "raft.toml", "src"]
  assert walk(root, r"*.{md,toml}")? == ["README.md", "raft.toml"]
  assert walk(root, "src/**")? ==
    ["src", "src/lib.auk", "src/net", "src/net/notes.txt", "src/net/tcp.auk", "src/util.auk"]
  assert walk(root, "**/.cache/*")? == ["src/.cache/old.auk"]
  assert walk(root, ".*")? == [".env", ".git"]
  assert walk(root, ".git/*")? == [".git/HEAD"]
  assert walk(root, "nothing/*.auk")? == []
  assert walk(root + "/", "src/net/*")? == ["src/net/notes.txt", "src/net/tcp.auk"]
  assert walk(root, "src/net/tcp.auk")? == ["src/net/tcp.auk"]
  assert walk("{root}/missing", "*") is err(_)

  // find: the pattern carries its base directory
  assert find("{root}/src/**/*.auk")? ==
    ["{root}/src/lib.auk", "{root}/src/net/tcp.auk", "{root}/src/util.auk"]
  assert find("{root}/*.toml")? == ["{root}/raft.toml"]
  assert find("{root}/raft.toml")? == ["{root}/raft.toml"]
  assert find("{root}/nope.toml")? == []
  assert find("{root}/nope/*.toml")? == []

  // clean up: files, then directories deepest first
  for f in files { fs.remove("{root}/{f}")? }
  for d in ["src/net", "src/.cache", "src", "docs", "a.b", ".git"] { fs.remove("{root}/{d}")? }
  fs.remove(root)?
  assert !fs.exists(root)
}