glob

stdlib/extra/glob.hk: glob matching over slash-separated paths.

fs.walk! hands back every path beneath a root and its own doc says to "filter for a glob"; this is the filter. Pure and lexical, like path: it reads no filesystem, which lets a pattern be matched against a path that does not exist, and matching is the same on both tiers.

The syntax is the familiar one, written out here and not left to a reference because every implementation differs at the edges:

• any run of characters, never crossing / ** any run of characters, crossing / freely ? one character, never / [abc] one character from the set; [a-z] a range, [!abc] / [^abc] a negation. ] first in the set is a literal ] \x a literal x, for the metacharacters above

** is the only construct that crosses a separator. That is what it is for, and it is why src/*.hk does not match src/a/b.hk while src/**.hk does.

**/ means zero or more directory components, and **/x.hk therefore finds x.hk at the root as well as a/b/x.hk. That is the one edge every implementation disagrees on, settled this way because **/*.hk is the most common glob anyone writes and a version that missed every file at the root would be a papercut on first use. A bare ** with no / after it is a run that may cross separators.

A pattern is compiled once and matched many times: filtering a walk means matching one pattern against thousands of paths, and re-parsing per path would be the dominant cost. A bad character class is a compile-time Err and never a pattern that matches nothing, a typo'd filter returning no files with no word about why being the worst outcome available.

PatternError

struct PatternError
  at: int
  reason: string
end

Why a pattern would not compile. at is the byte offset the problem was found at, which lets a caller point at it.

impl Display<PatternError>

to_string

def to_string(self) -> string

Renders as <reason> at offset <at>.

PatternError(at=3, reason="unterminated character class").to_string() => "unterminated character class at offset 3"

impl Eq<PatternError>

eq?

def eq?(self, other: Self) -> bool

Equal when both the offset and the reason match.

PatternError(at=1, reason="x").eq?(PatternError(at=1, reason="x")) => true

Token

type Token
  Literal(string)
  Any
  Star
  DoubleStar
  DoubleStarSlash
  Class(CharClass)
end

One matching step. Star and DoubleStar are the two wildcards that consume a run; the rest consume one character each.

CharClass

struct CharClass
  ranges: List<Range>
  negated: bool
end

A [...] set: the ranges it admits, and whether membership is inverted.

Range

struct Range
  lo: string
  hi: string
end

One inclusive character range. A bare a is stored as a..a.

Pattern

opaque Pattern
  _tokens: List<Token>
end

A compiled pattern, ready to match many paths.

compile

def compile(pattern: string) -> Result<Pattern, PatternError>

Compile pattern, or say why it cannot be.

compile("*.hk").map(|p| p.matches?("main.hk")) => Ok(true)
compile("[a-").map(|_| "ok").map_err(|e| e.reason) => Err("unterminated character class")

matches?

def matches?(pattern: string, p: string) -> Result<bool, PatternError>

Compile pattern and match p in one step: the convenience for a one-off test. Filtering a list wants compile once and matches? per path instead.

matches?("*.hk", "main.hk") => Ok(true)
matches?("src/*.hk", "src/a/b.hk") => Ok(false)
matches?("src/**.hk", "src/a/b.hk") => Ok(true)

impl Pattern

matches?

def matches?(self, p: string) -> bool

Whether p matches this pattern. Lexical: p is treated as a slash-separated path, and nothing is read from disk.

compile("*.hk").map(|c| c.matches?("main.hk"))  => Ok(true)
compile("*.hk").map(|c| c.matches?("main.rs"))  => Ok(false)
compile("?.hk").map(|c| c.matches?("a.hk"))     => Ok(true)
compile("?.hk").map(|c| c.matches?("ab.hk"))    => Ok(false)

_scan

def _scan(pattern: string, i: int, acc: List<Token>) -> Result<List<Token>, PatternError>

Scan pattern from i, accumulating tokens. Recursive and not a loop, which leaves the accumulator a value; a pattern is short, and so is the depth.

scanstar

def _scan_star(pattern: string, i: int, acc: List<Token>) -> Result<List<Token>, PatternError>

* or **, distinguished by whether a second star follows. A ** with a / right behind it takes the separator with it, as one token: that is what lets **/x.hk match a bare x.hk as well as a/b/x.hk. Scanning them apart would leave the / a literal the pattern insists on, and the most common glob anyone writes would miss every file at the root.

scanescape

def _scan_escape(pattern: string, i: int, acc: List<Token>) -> Result<List<Token>, PatternError>

\x: the next character, literally. A backslash at the very end escapes nothing, which is a typo and no pattern.

scanclass

def _scan_class(pattern: string, open_at: int, acc: List<Token>) -> Result<List<Token>, PatternError>

A [...] set beginning at open_at. Delegates the body to _class_ranges and resumes the outer scan past the closing bracket.

_ClassScan

struct _ClassScan
  ranges: List<Range>
  next: int
end

Where a class body starts and what is in it, threaded through the scan.

classnegated?

def _class_negated?(pattern: string, at: int) -> bool

classbody_start

def _class_body_start(pattern: string, at: int) -> int

The body starts after any negation mark. A ] in first position is a literal, and is left for _class_ranges to consume as one.

classranges

def _class_ranges(pattern: string, i: int, acc: List<Range>, first_of: int) -> Result<_ClassScan, PatternError>

Read ranges until the closing ]. first_of is the offset of the opening bracket, reported when the class never closes.

rangecloses?

def _range_closes?(pattern: string, at: int) -> bool

Whether offset at has a character that can close an a-z range: present, and not the ] that would make the - a literal trailing dash.

_match

def _match(tokens: List<Token>, ti: int, p: string, pi: int) -> bool

Match tokens from index ti against p from offset pi. Backtracking is explicit: a Star tries the shortest run first and lengthens, which is what makes a*b*c terminate in place of committing to a greedy first guess.

matchtoken

def _match_token(t: Token, tokens: List<Token>, ti: int, p: string, pi: int) -> bool

consumesone?

def _consumes_one?(p: string, pi: int) -> bool

A single-character token consumes anything except a separator, and never the end of the path.

matchrun

def _match_run(tokens: List<Token>, ti: int, p: string, pi: int, cross: bool) -> bool

A wildcard run: try matching the rest here, then extend by one character. cross is whether the run may swallow a separator, which is the only difference between * and **.

matchdir_run

def _match_dir_run(tokens: List<Token>, ti: int, p: string, pi: int) -> bool

**/: zero or more whole directory components. Either the rest matches right here, the zero-directory case that makes **/x.hk find x.hk, or some prefix ending in / is consumed and the question is asked again.

nextsep

def _next_sep(p: string, from: int) -> Option<int>

The offset of the next / at or after from, if any.

inclass?

def _in_class?(k: CharClass, c: string) -> bool