// ZipLex-style lexer: maximal munch over per-rule derivatives,
// priority = rule order, memoized derivatives, exact print roundtrip.

///|
/// A lexical rule: name plus the regular language it accepts.
pub struct Rule {
  name : String
  re : Regex
}

///|
/// Construct a rule (priority = position in the rule list).
pub fn Rule::new(name : String, re : Regex) -> Rule {
  Rule::{ name, re }
}

///|
/// A lexed token: rule name plus the exact matched substring.
pub struct Token {
  rule : String
  lexeme : String
}

///|
/// Memoized derivative: same (regex-render, char) pair reuses the result.
fn memo_derivative(
  memo : @hashmap.HashMap[String, Regex],
  c : Char,
  r : Regex,
) -> Regex {
  let key = render(r) + "\u{0000}" + c.to_string()
  match memo.get(key) {
    Some(d) => d
    None => {
      let d = derivative(c, r)
      memo.set(key, d)
      d
    }
  }
}

///|
/// Lex `input` under `rules` with maximal munch (longest match) semantics;
/// ties at equal length are resolved by earlier rule position.
/// Err when some position cannot start any rule.
pub fn lex(rules : Array[Rule], input : String) -> Result[Array[Token], String] {
  let memo : @hashmap.HashMap[String, Regex] = HashMap([], capacity=64)
  let n = input.length()
  let k = rules.length()
  let tokens : Array[Token] = []
  let mut pos = 0
  while pos < n {
    // current derivative of each rule's regex
    let ders : Array[Regex] = []
    for r in rules {
      ders.push(r.re)
    }
    // best = (match length, rule index) of the FARTHEST nullable state so far
    let mut best_len = -1
    let mut best_rule = -1
    let mut j = pos
    let mut alive = true
    while alive && j < n {
      // update all derivatives with input[j]
      let c = match input[j].to_char() {
        Some(ch) => ch
        None => return Err("lex error: invalid UTF-16 unit at offset \{j}")
      }
      for i in 0.. String {
  let buf = StringBuilder()
  for t in tokens {
    buf.write_string(t.lexeme)
  }
  buf.to_string()
}