Glob Pattern Matcher

The Problem

• Command-line shells use patterns like *.gleam, data?.csv, and report_2024* to match groups of filenames
  • These patterns are called globs (short for "global")

• Three rules cover everything a basic glob matcher needs:

• * matches any sequence of characters, including the empty sequence

• ? matches any single character

• Everything else matches exactly itself

• Writing a glob matcher uses custom types, recursion, and pattern matching in a single small program

Representing Pattern Elements

• First design decision is how to represent a parsed pattern
• A String would lose the structure: we could not easily tell a literal asterisk from a wildcard metacharacter.
• A custom type makes each case explicit:

pub type Elem {
  Literal(String)
  AnyChar
  Wildcard
}

• Literal(String) holds a single character that must match exactly
• AnyChar matches any one character and holds no data
• Wildcard matches zero or more characters and holds no data
• Adding a new rule (e.g., character classes) means adding a new variant, and the compiler will flag every case that does not handle it
• List(Elem) is the natural representation for a whole pattern
  • [Wildcard, Literal(".gl")] represents *.gl
• Get matching to work, then build a parser to turn strings into these lists

Matching a Pattern Against Text

• Matching consumes elements and characters in parallel:

pub fn match_pattern(pattern: List(Elem), text: String) -> Bool {
  match_pattern_chars(pattern, string_to_chars(text))
}

fn match_pattern_chars(pattern: List(Elem), chars: List(String)) -> Bool {
  case pattern, chars {
    [], [] -> True
    [], _ -> False
    [Literal(c), ..pat_rest], _ ->
      case drop_prefix(string.to_graphemes(c), chars) {
        Ok(remaining) -> match_pattern_chars(pat_rest, remaining)
        Error(_) -> False
      }
    [AnyChar, ..pat_rest], [_, ..char_rest] ->
      match_pattern_chars(pat_rest, char_rest)
    [Wildcard, ..pat_rest], _ -> {
      case match_pattern_chars(pat_rest, chars) {
        True -> True
        False -> {
          case chars {
            [] -> False
            [_, ..char_rest] -> match_pattern_chars(pattern, char_rest)
          }
        }
      }
    }
    _, _ -> False
  }
}

• match_pattern converts the input string to a list of graphemes and delegates to match_pattern_chars
• match_pattern_chars dispatches on the pair (pattern, chars):
  • Both empty: success
  • Pattern empty but input remains: failure (we required more)
  • Literal(c) with a matching character: advance both and recurse
  • AnyChar with any character: advance both and recurse
  • Wildcard: the two-branch case described below
  • Anything else (literal mismatch, empty input when pattern not empty): failure

Handling Wildcards

• The Wildcard branch is the most interesting one
• A wildcard can match zero characters (the pattern continues from the same position) or one or more characters (the input advances by one)
• The code tries the zero-match option first:

[Wildcard, ..pat_rest], _ -> {
  case match_pattern_chars(pat_rest, chars) {
    True -> True
    False -> {
      case chars {
        [] -> False
        [_, ..char_rest] -> match_pattern_chars(pattern, char_rest)
      }
    }
  }
}

• Try match_pattern_chars(prest, chars): does the rest of the pattern match the current input without consuming anything for the wildcard?
• If yes, return True
• If no and input is exhausted, return False

• If no and input remains, consume one character and retry with the same pattern

  • The wildcard is still active

• This is depth-first backtracking

• For most practical inputs it is fast enough
  • Pathological patterns like *a*a*a*a*a*b against a long string of as can be slow, but that is a known trade-off in backtracking matchers

Parsing Patterns

• src/match_demo.gleam constructs pattern lists by hand
• For real use we need a function that turns "*.gleam" into [Wildcard, Literal(".gleam")]

fn parse_pattern(s: String) -> List(Elem) {
  let chars = string.to_graphemes(s)
  parse_chars(chars, [])
}

fn parse_chars(chars: List(String), acc: List(Elem)) -> List(Elem) {
  case chars {
    [] -> list.reverse(acc)
    ["*", ..rest] -> parse_chars(rest, [Wildcard, ..acc])
    ["?", ..rest] -> parse_chars(rest, [AnyChar, ..acc])
    _ -> {
      let #(literal, remaining) = take_literal(chars, [])
      parse_chars(remaining, [Literal(literal), ..acc])
    }
  }
}

• parse_pattern converts the string to graphemes and calls the recursive parse_chars
  • This pattern of "entry point function calls recursive function" is used a lot
• parse_chars accumulates elements in reverse and reverses at the end
• "*" becomes Wildcard, "?" becomes AnyChar
• Consecutive non-special characters are collected into a single Literal by take_literal
  • Prevents Literal("h"), Literal("e"), Literal("l"), Literal("l"), Literal("o")
• Notice that Literal holds a String, not a UtfCodepoint
  • This lets one Literal represent a multi-character run, which is more efficient and easier to read in debug output

Running the Examples

gleam run --module match_demo

[Wildcard, Literal(".gleam")]
[Literal("data"), AnyChar, Literal(".csv")]
[Literal("hello")]

• The first three test *.gleam against:
  • hello.gleam (match)
  • hello.rs (no match)
  • .gleam (match, because * can match zero characters)
• The last three test d?t against:
  • dot (match)
  • dat (match)
  • dog (no match, the t is missing)

Writing Tests

• Create test/glob_test.gleam:

pub fn literal_match_test() {
  match_pattern([Literal("a")], "a")
  |> should.be_true()
}

pub fn anychar_test() {
  match_pattern([AnyChar], "x")
  |> should.be_true()
}

pub fn wildcard_many_test() {
  match_pattern([Wildcard, Literal(".gleam")], "mymodule.gleam")
  |> should.be_true()
}

• Each test covers exactly one behavior
• Test names end in _test so gleeunit discovers them automatically
• should.be_true() and should.be_false() are clearer than should.equal(True) for Boolean results
• Run with gleam test

Filtering a List of Files

Combining the parser and matcher gives a useful utility:

pub fn filter_files(
  pattern: String,
  files: List(String),
) -> List(String) {
  let elems = parse_pattern(pattern)
  list.filter(files, match_pattern(elems, _))
}

• match_pattern(elems, _) is a partial application: it creates a one-argument function that tests a single filename
• list.filter applies it to every element
• parse_pattern runs once, while List(Elem) is reused for every file
• This is an example of using a function value as data
  • list.filter expects fn(String) -> Bool
  • Partial application produces exactly that without writing a named helper function

Check Understanding

Exercises