Pattern matching: match / case

# A small general-purpose regex engine, written in PatLang, for use by the
# Rust-side `syntax_dsl` source preprocessor (and anything else that needs
# pattern matching) without depending on Rust's `regex` crate or any other
# Rust-native pattern-matching feature. PatLang is meant to be fully
# self-hosting, so the actual matching *logic* has to be genuine PatLang
# code, invoked from Rust only as "run this program's function with these
# arguments" (see `Interpreter::call_function`).
#
# Supported syntax subset:
#   literals            a b c ...
#   escapes             \\ \. \d \w \s \b (and \n \t \\ \( \) \[ \] \| \* \+ \? \^ \$)
#   any char            .
#   character class     [abc] [a-z0-9] [^abc]
#   grouping             (...)
#   alternation          a|b|c
#   quantifiers          a* a+ a?
#   anchors              ^ $ \b (word boundary)
#
# No capture groups are extracted (whole-match only) — sufficient for
# tokenizing DSL blocks, which only need "does this token pattern match here,
# and how long is the match".
#
# AST nodes are tagged lists: ["lit", ch], ["any"], ["class", negate, items],
# ["seq", nodes], ["alt", branches], ["star", node], ["plus", node],
# ["opt", node], ["bol"], ["eol"], ["wordb"].

fn is_digit_char(ch) {
    return ch == "0" or ch == "1" or ch == "2" or ch == "3" or ch == "4" or ch == "5" or ch == "6" or ch == "7" or ch == "8" or ch == "9"
}

fn is_word_char(ch) {
    if ch == "_" { return true }
    if is_digit_char(ch) { return true }
    let code = char_code(ch, 0)
    # A-Z: 65-90, a-z: 97-122
    if code >= 65 and code <= 90 { return true }
    if code >= 97 and code <= 122 { return true }
    return false
}

fn is_space_char(ch) {
    return ch == " " or ch == "\t" or ch == "\n" or ch == "\r"
}

# ---------------------------------------------------------------------
# Parsing: pattern (string) -> AST node. Returns [node, next_pos]; on
# failure next_pos is -1.
# ---------------------------------------------------------------------

fn regex_parse(pattern) {
    let result = regex_parse_alt(pattern, 0)
    return list_get(result, 0)
}

fn regex_parse_alt(pattern, pos) {
    let plen = to_num(list_len(pattern))
    let first = regex_parse_seq(pattern, pos)
    let node = list_get(first, 0)
    let mut p = list_get(first, 1)
    if p < 0 { return [node, p] }
    let mut branches = list_push([], node)
    while p < plen and substr(pattern, p, 1) == "|" {
        let nxt = regex_parse_seq(pattern, p + 1)
        branches = list_push(branches, list_get(nxt, 0))
        p = list_get(nxt, 1)
        if p < 0 { return [["alt", branches], -1] }
    }
    let n = to_num(list_len(branches))
    if n == 1 {
        return [list_get(branches, 0), p]
    }
    return [["alt", branches], p]
}

fn regex_parse_seq(pattern, pos) {
    let plen = to_num(list_len(pattern))
    let mut nodes = []
    let mut p = pos
    while p < plen and substr(pattern, p, 1) != "|" and substr(pattern, p, 1) != ")" {
        let r = regex_parse_quantified(pattern, p)
        let node = list_get(r, 0)
        p = list_get(r, 1)
        if p < 0 { return [["seq", nodes], -1] }
        nodes = list_push(nodes, node)
    }
    return [["seq", nodes], p]
}

fn regex_parse_quantified(pattern, pos) {
    let r = regex_parse_atom(pattern, pos)
    let node = list_get(r, 0)
    let mut p = list_get(r, 1)
    if p < 0 { return [node, -1] }
    let plen = to_num(list_len(pattern))
    if p < plen {
        let c = substr(pattern, p, 1)
        if c == "*" { return [["star", node], p + 1] }
        if c == "+" { return [["plus", node], p + 1] }
        if c == "?" { return [["opt", node], p + 1] }
    }
    return [node, p]
}

fn regex_atom_for_escape(ch) {
    if ch == "d" { return ["class", 0, [["range", "0", "9"]]] }
    if ch == "w" { return ["class", 0, [["range", "a", "z"], ["range", "A", "Z"], ["range", "0", "9"], ["char", "_"]]] }
    if ch == "s" { return ["class", 0, [["char", " "], ["char", "\t"], ["char", "\n"], ["char", "\r"]]] }
    if ch == "b" { return ["wordb"] }
    if ch == "n" { return ["lit", "\n"] }
    if ch == "t" { return ["lit", "\t"] }
    return ["lit", ch]
}

fn regex_parse_atom(pattern, pos) {
    let plen = to_num(list_len(pattern))
    if pos >= plen { return [["seq", []], -1] }
    let c = substr(pattern, pos, 1)
    if c == "(" {
        let inner = regex_parse_alt(pattern, pos + 1)
        let node = list_get(inner, 0)
        let mut p = list_get(inner, 1)
        if p < 0 { return [node, -1] }
        if p >= plen or substr(pattern, p, 1) != ")" { return [node, -1] }
        return [["group", node], p + 1]
    }
    if c == "." { return [["any"], pos + 1] }
    if c == "^" { return [["bol"], pos + 1] }
    if c == "$" { return [["eol"], pos + 1] }
    if c == "\\" {
        if pos + 1 >= plen { return [["lit", "\\"], pos + 1] }
        let esc = substr(pattern, pos + 1, 1)
        return [regex_atom_for_escape(esc), pos + 2]
    }
    if c == "[" {
        return regex_parse_class(pattern, pos + 1)
    }
    return [["lit", c], pos + 1]
}

fn regex_parse_class(pattern, pos) {
    let plen = to_num(list_len(pattern))
    let mut negate = 0
    let mut p = pos
    if p < plen and substr(pattern, p, 1) == "^" {
        negate = 1
        p = p + 1
    }
    let mut items = []
    while p < plen and substr(pattern, p, 1) != "]" {
        let mut c = substr(pattern, p, 1)
        if c == "\\" and p + 1 < plen {
            c = substr(pattern, p + 1, 1)
            p = p + 1
        }
        if p + 2 < plen and substr(pattern, p + 1, 1) == "-" and substr(pattern, p + 2, 1) != "]" {
            let hi = substr(pattern, p + 2, 1)
            items = list_push(items, ["range", c, hi])
            p = p + 3
        } else {
            items = list_push(items, ["char", c])
            p = p + 1
        }
    }
    if p >= plen { return [["class", negate, items], -1] }
    return [["class", negate, items], p + 1]
}

# ---------------------------------------------------------------------
# Matching: attempts to match `node` in `text` starting at `pos`, calling
# `k(new_pos)` (a closure) with every position reachable after a successful
# match, until `k` returns a non-negative number (accepted) or all
# possibilities are exhausted (returns -1). This continuation style is what
# makes backtracking over alternation/quantifiers correct: `k` represents
# "the rest of the overall pattern", so a quantifier can retry with fewer
# repetitions if a later part of the pattern needs the characters back.
# ---------------------------------------------------------------------

fn regex_class_matches(items, ch) {
    let n = to_num(list_len(items))
    let mut i = 0
    while i < n {
        let it = list_get(items, i)
        let tag = list_get(it, 0)
        if tag == "char" {
            if ch == list_get(it, 1) { return true }
        } else {
            if ch >= list_get(it, 1) and ch <= list_get(it, 2) { return true }
        }
        i = i + 1
    }
    return false
}

fn regex_match_node(node, text, pos, k) {
    let tag = list_get(node, 0)
    let tlen = to_num(list_len(text))
    if tag == "lit" {
        if pos < tlen and substr(text, pos, 1) == list_get(node, 1) {
            return k(pos + 1)
        }
        return -1
    }
    if tag == "any" {
        if pos < tlen and substr(text, pos, 1) != "\n" {
            return k(pos + 1)
        }
        return -1
    }
    if tag == "class" {
        if pos >= tlen { return -1 }
        let ch = substr(text, pos, 1)
        let mut hit = regex_class_matches(list_get(node, 2), ch)
        let negate = list_get(node, 1)
        if negate == 1 { hit = not hit }
        if hit { return k(pos + 1) }
        return -1
    }
    if tag == "bol" {
        if pos == 0 { return k(pos) }
        if pos > 0 and substr(text, pos - 1, 1) == "\n" { return k(pos) }
        return -1
    }
    if tag == "eol" {
        if pos == tlen { return k(pos) }
        if pos < tlen and substr(text, pos, 1) == "\n" { return k(pos) }
        return -1
    }
    if tag == "wordb" {
        let mut before = false
        let mut after = false
        if pos > 0 { before = is_word_char(substr(text, pos - 1, 1)) }
        if pos < tlen { after = is_word_char(substr(text, pos, 1)) }
        if before != after { return k(pos) }
        return -1
    }
    if tag == "group" {
        return regex_match_node(list_get(node, 1), text, pos, k)
    }
    if tag == "seq" {
        return regex_match_seq(list_get(node, 1), 0, text, pos, k)
    }
    if tag == "alt" {
        return regex_match_alt(list_get(node, 1), 0, text, pos, k)
    }
    if tag == "star" {
        return regex_match_repeat(list_get(node, 1), text, pos, k, 0)
    }
    if tag == "plus" {
        return regex_match_repeat(list_get(node, 1), text, pos, k, 1)
    }
    if tag == "opt" {
        let inner = list_get(node, 1)
        let r = regex_match_node(inner, text, pos, k)
        if r >= 0 { return r }
        return k(pos)
    }
    return -1
}

fn regex_match_seq(nodes, idx, text, pos, k) {
    let n = to_num(list_len(nodes))
    if idx >= n { return k(pos) }
    let node = list_get(nodes, idx)
    return regex_match_node(node, text, pos, |p2| { return regex_match_seq(nodes, idx + 1, text, p2, k) })
}

fn regex_match_alt(branches, idx, text, pos, k) {
    let n = to_num(list_len(branches))
    if idx >= n { return -1 }
    let r = regex_match_node(list_get(branches, idx), text, pos, k)
    if r >= 0 { return r }
    return regex_match_alt(branches, idx + 1, text, pos, k)
}

# Backtracking repetition: tries the greatest number of repetitions first,
# then backs off, so that whatever comes after (represented by `k`) still
# gets a chance to match — the standard greedy-with-backtracking behavior.
fn regex_match_repeat(node, text, pos, k, min_count) {
    let r = regex_match_node(node, text, pos, |p2| {
        if p2 == pos { return -1 }
        return regex_match_repeat(node, text, p2, k, 0)
    })
    if r >= 0 { return r }
    if min_count <= 0 { return k(pos) }
    return -1
}

# Attempts to match `pattern_ast` (already parsed via regex_parse) against
# `text` starting exactly at `start`. Returns the end position of the
# longest-preferred (leftmost-greedy) match, or -1 if there is no match
# anchored at `start`.
#
# Note: the "return the position unchanged" continuation is written as an
# inline closure literal (`|p| { return p }`), not a reference to a plain
# top-level function — bare references to named functions lower to a
# local-variable load (and thus to Unit, since no such local exists), only
# closure literals actually produce a callable value in this IR. See
# `regex_match_seq` etc. below for the same reason every "rest of the
# match" continuation passed around is built the same way.
#
# GitHub follow-up (found while investigating 7 pre-existing
# regex_patlang_engine.rs failures, all "match length always 0"): this
# closure's own body used to be the BARE expression `p`, not `return p`
# -- PatLang has no implicit last-expression return (every function/
# closure needs an explicit `return`, unlike Ruby/Rust blocks), so the
# bare form silently evaluated to Unit every time it was called, which
# then propagated through this entire continuation-passing match engine
# to every single caller. Confirmed via a minimal standalone repro
# (`let k = |p| { p }; print(k(6))` prints nothing; `|p| { return p }`
# correctly prints 6) before touching this file.
fn regex_match_at(pattern_ast, text, start) {
    return regex_match_node(pattern_ast, text, start, |p| { return p })
}

# Convenience combined entry point for callers that only have the raw
# pattern string (no pre-parsed AST cached) — parses then matches.
fn regex_match_string_at(pattern, text, start) {
    let ast = regex_parse(pattern)
    return regex_match_at(ast, text, start)
}

# ---------------------------------------------------------------------
# Glob matching (used by `match`'s `case *fred* then` pattern kind, see
# self_hosting/lib/lower.patlang's compile_pattern PGlob arm). A glob is
# translated to a regex (`*` -> `.*`, `?` -> `.`, every other char
# escaped if it's a regex metachar) and matched as a WHOLE-STRING match
# (the translated regex must consume the entire input, not just a
# prefix) -- glob semantics, unlike regex_match_string_at's "match
# anchored at a start position", never mean "found somewhere inside".
# ---------------------------------------------------------------------

fn glob_regex_needs_escape(ch) {
    return ch == "\\" or ch == "." or ch == "(" or ch == ")" or ch == "[" or ch == "]" or ch == "^" or ch == "$" or ch == "|" or ch == "+" or ch == "{" or ch == "}"
}

fn glob_to_regex(pattern) {
    let plen = to_num(list_len(pattern))
    let out = sb_new()
    let mut i = 0
    while i < plen {
        let ch = substr(pattern, i, 1)
        if ch == "*" {
            sb_push(out, ".*")
        } else {
            if ch == "?" {
                sb_push(out, ".")
            } else {
                if glob_regex_needs_escape(ch) {
                    sb_push(out, "\\" + ch)
                } else {
                    sb_push(out, ch)
                }
            }
        }
        i = i + 1
    }
    return sb_str(out)
}

fn glob_match(text, pattern) {
    let regex_str = glob_to_regex(pattern)
    let ast = regex_parse(regex_str)
    let end = regex_match_at(ast, text, 0)
    return end == to_num(list_len(text))
}



# Pattern matching (match/case): pure syntactic sugar over ordinary if/
# jump instructions -- see self_hosting/lib/lower.patlang's lower_match.
# Every arm kind below desugars to the exact same instructions an if/elif
# chain already uses, so it runs unmodified on every backend: the tree-
# walking interpreter, native rustc-compiled code, and this very page's
# in-browser WebAssembly playground.

fn classify(x) {
    match x do
      case 0 then
        return "zero"
      case "hi" then
        return "a greeting"
      case > 100 then
        return "big (" + x + ")"
      case n then
        return "just a number: " + n
    end
}

print(classify(0))
print(classify("hi"))
print(classify(250))
print(classify(7))

# Tagged-list patterns destructure and bind in one step -- no more
# `if x[0] == "Ok" then let v = x[1] ...` by hand.
fn describe(result) {
    match result do
      case ["Ok", v] then
        return "success: " + v
      case ["Err", ["Timeout", ms]] then
        return "failed after " + ms + "ms (timeout)"
      case ["Err", reason] then
        return "failed: " + reason
      case _ then
        return "not a recognized result shape"
    end
}

print(describe(["Ok", 42]))
print(describe(["Err", ["Timeout", 3000]]))
print(describe(["Err", "connection refused"]))
print(describe("garbage"))

# `when` adds an arbitrary boolean guard to any pattern, free to reference
# bindings the pattern just introduced.
fn triage(n) {
    match n do
      case v when v < 0 then
        return "negative: " + v
      case v when v > 1000 then
        return "way too big: " + v
      case v then
        return "in range: " + v
    end
}

print(triage(-5))
print(triage(5000))
print(triage(42))

# There's no dedicated "match by type" pattern kind -- `when` already
# covers it, since a guard is just an arbitrary boolean expression, free
# to call type_of()/numeric_kind() and reference OTHER variables in
# scope, not only the binding its own pattern just introduced. That also
# covers "select by a combination of criteria across multiple variables"
# for free: a guard can AND together checks on the scrutinee's binding
# and any number of unrelated outer variables in one expression.
fn type_report(v) {
    match v do
      case x when type_of(x) == "string" then
        return "string: \"" + x + "\""
      case x when numeric_kind(x) == "bigint" then
        return "bigint: " + x
      case x when type_of(x) == "list" then
        return "list of " + x.length + " item(s)"
      case x when type_of(x) == "bool" then
        return "boolean: " + x
      case x then
        return "number: " + x
    end
}

fn factorial(n) {
    if n <= 1 then
      return 1
    end
    return n * factorial(n - 1)
}

print(type_report("hello"))
print(type_report(factorial(25)))
print(type_report([1, 2, 3]))
print(type_report(true))
print(type_report(7))

fn describe_pair(a, b) {
    # Order matters here exactly like an if/elif chain: `and` short-
    # circuits left-to-right, so the type check must come FIRST in each
    # guard -- `x > 0 and ...` would throw a type error comparing a
    # string with `>`, not just evaluate falsy, if x ever isn't numeric.
    match a do
      case x when type_of(x) == "string" and type_of(b) == "string" then
        return "both strings: " + x + ", " + b
      case x when numeric_kind(x) != "other" and x > 0 and b > 0 then
        return "both positive: " + x + ", " + b
      case x when numeric_kind(x) != "other" and x > 0 and b < 0 then
        return "mixed signs: " + x + ", " + b
      case _ then
        return "no combined rule matched"
    end
}

print(describe_pair(3, 4))
print(describe_pair(3, -4))
print(describe_pair("a", "b"))
print(describe_pair(-3, -4))

# Unquoted glob patterns reuse the existing regex engine (glob_match, in
# self_hosting/lib/regex.patlang) rather than a bespoke matcher.
fn tag_file(name) {
    match name do
      case *.patlang then
        return "PatLang source"
      case *.md then
        return "documentation"
      case test_* then
        return "test artifact"
      case _ then
        return "unrecognized"
    end
}

print(tag_file("lower.patlang"))
print(tag_file("README.md"))
print(tag_file("test_output.log"))
print(tag_file("photo.jpg"))

# PatLang has no static type system to check exhaustiveness against, so a
# scrutinee with no matching arm -- and no wildcard `_` catch-all -- is a
# genuine runtime error, not a silent no-op. Uncomment the line below to
# see it fire (deliberately left commented so the rest of this demo's
# output stays visible):
# print(classify_strict(999))

fn classify_strict(x) {
    match x do
      case 1 then
        return "one"
      case 2 then
        return "two"
    end
}

print("strict(1) = " + classify_strict(1))
print("about to fall through classify_strict's only two cases...")
print(classify_strict(99))