Globbing (Pathname Expansion)

Type rm *.log and rm receives... not *.log. It receives access.log error.log debug.log — because the shell expanded the pattern before rm ever ran. Programs never see globs; they see the filenames the shell matched. This lesson builds that matcher, and it's a small, satisfying recursive algorithm with two famous edge cases.

The pattern language

Three constructs, much simpler than regex:

*        any run of characters, INCLUDING empty    (*.txt, backup*, *)
?        exactly one character                     (file?.txt matches file1.txt, not file10.txt)
[abc]    one character from the set               ([0-9] ranges work; [!abc] negates)

Two rules distinguish glob semantics from "regex lite":

1. Matching is against the whole name — *.txt must match the entire filename, not find .txt somewhere inside. (In regex terms: implicitly anchored both ends.)
2. * and ? never match / — patterns match within one directory level; docs/*.md is a literal docs/ plus a pattern for that directory's contents. (And hidden files — names starting with . — are skipped unless the pattern itself starts with a dot: why rm * mercifully spares .git.)

The matcher: recursion earns its keep

? and […] consume exactly one character — trivial. All the interesting behavior is *, because it must decide how much to swallow, and the clean answer is recursion — at each *, two futures:

match(pattern, name):
    if pattern is empty:  return name is empty
    if pattern[0] == '*':
        return match(pattern[1:], name)                     # * matches empty
            or (name not empty and match(pattern, name[1:])) # * eats one more char
    if name is empty:     return false
    if pattern[0] == '?' or pattern[0] == name[0] or set-match:
        return match(pattern[1:], name[1:])
    return false

Trace *.txt against a.txt by hand once — watch the star try "match nothing" (fails: .txt vs a.txt), then eat the a and succeed. That branching-then-backtracking is the same mechanism inside regex engines; globs are where it's small enough to hold in your head. (Adjacent stars ** behave as one star in classic globbing; collapse them and the exponential-blowup pathological cases disappear.)

The no-match rule (the part everyone forgets)

What if *.xyz matches nothing? Bash's default is arguably the language's strangest choice: the pattern is passed through literally — the program receives the string *.xyz. That's why ls *.xyz in an empty directory prints ls: cannot access '*.xyz' — ls got the star itself! Contrast: a matched pattern replaces the token with N filename tokens, sorted (the sort is guaranteed and your tests check it). One pattern token thus becomes zero-or-more argument tokens — expansion happens after tokenizing (a * inside quotes was protected — the tokenizer's quote-tracking pays off here) and before execution.

Your exercise: Implement Glob Matching

Patterns and filename lists in; matched names out, per the spec (including its no-match behavior — read whether it wants bash's literal-pass-through or an empty result). Test ladder: literal names → *.ext → ? counting characters exactly → character classes → the empty-match star (a*b vs ab) → multiple stars (*a* — backtracking for real) → hidden-file and sort rules if specced. The matcher is ~15 lines; like the tokenizer, its value is turning something you've used ten thousand times into something you've built once — after which rm * is no longer an incantation, it's a function call you could reimplement on a whiteboard.