// A small pattern engine for numbering-plan rules.
//
// The numbering plans published by libphonenumber describe each number type with
// a regular expression over the national number, for example
//
//     (?:2(?:04|[23]6|[48]9)|3(?:06|43|54))\d{7}
//
// Those expressions are not arbitrary PCRE: the corpus uses only literals,
// `\d`, character classes with ranges, non-capturing groups, alternation and the
// `?`, `*`, `+`, `{n}`, `{n,}` and `{n,m}` quantifiers. This file implements
// exactly that grammar: a recursive-descent parser builds a syntax tree, the
// tree is compiled to a Thompson NFA, and matching simulates the NFA over a set
// of live states.
//
// The simulation matters: it is O(pattern size x input length) and cannot
// backtrack, so a hostile pattern cannot make a validation call explode. The
// engine is also deliberately total — a malformed pattern is a parse failure,
// not a panic.

// ---------------------------------------------------------------------------
// Syntax tree
// ---------------------------------------------------------------------------

///|
/// One node of a parsed pattern.
priv enum PatNode {
  PatLit(Char)
  PatDigit
  PatClass(Array[(Char, Char)])
  PatSeq(Array[PatNode])
  PatAlt(Array[PatNode])
  PatRep(PatNode, Int32, Int32) // minimum, maximum; -1 means unbounded
  PatCapture(Int32, PatNode)
}

// ---------------------------------------------------------------------------
// Parser
// ---------------------------------------------------------------------------

///|
/// Parse a whole pattern. None when the text is not a member of the grammar.
fn parse_pattern(text : String) -> PatNode? {
  let src = chars_of(text)
  if src.length() > 8192 {
    return None
  }
  let mut depth = 0
  let mut in_class = false
  for i = 0; i < src.length(); i = i + 1 {
    if src[i] == '[' {
      in_class = true
    }
    if src[i] == ']' {
      in_class = false
    }
    if !in_class && src[i] == '(' {
      depth = depth + 1
    }
    if !in_class && src[i] == ')' {
      depth = depth - 1
    }
    if depth > 64 {
      return None
    }
  }
  match parse_alt(src, 0) {
    None => None
    Some((node, end)) =>
      if end == src.length() && pattern_cost(node, 65536) is Some(_) {
        Some(node)
      } else {
        None
      }
  }
}

///|
/// `alt := seq ('|' seq)*`
fn parse_alt(src : Array[Char], pos : Int32) -> (PatNode, Int32)? {
  let branches : Array[PatNode] = []
  let mut p = pos
  let (first, np) = match parse_seq(src, p) {
    None => return None
    Some(v) => v
  }
  branches.push(first)
  p = np
  while p < src.length() && src[p] == '|' {
    let (next, np2) = match parse_seq(src, p + 1) {
      None => return None
      Some(v) => v
    }
    branches.push(next)
    p = np2
  }
  if branches.length() == 1 {
    Some((branches[0], p))
  } else {
    Some((PatAlt(branches), p))
  }
}

///|
/// `seq := atom*`, stopping at end of input, `|` or `)`.
fn parse_seq(src : Array[Char], pos : Int32) -> (PatNode, Int32)? {
  let items : Array[PatNode] = []
  let mut p = pos
  while p < src.length() && src[p] != '|' && src[p] != ')' {
    let (node, np) = match parse_atom(src, p) {
      None => return None
      Some(v) => v
    }
    items.push(node)
    p = np
  }
  if items.length() == 1 {
    Some((items[0], p))
  } else {
    Some((PatSeq(items), p))
  }
}

///|
/// `atom := base quantifier?`
fn parse_atom(src : Array[Char], pos : Int32) -> (PatNode, Int32)? {
  let (base, p) = match parse_base(src, pos) {
    None => return None
    Some(v) => v
  }
  if p >= src.length() {
    return Some((base, p))
  }
  match src[p] {
    '?' => Some((PatRep(base, 0, 1), p + 1))
    '*' => Some((PatRep(base, 0, -1), p + 1))
    '+' => Some((PatRep(base, 1, -1), p + 1))
    '{' => parse_braces(src, p, base)
    _ => Some((base, p))
  }
}

///|
/// `{n}`, `{n,}` and `{n,m}` after an atom.
fn parse_braces(
  src : Array[Char],
  pos : Int32,
  base : PatNode,
) -> (PatNode, Int32)? {
  let (min, p0) = match parse_int(src, pos + 1) {
    None => return None
    Some(v) => v
  }
  if min > 10000 {
    return None
  }
  if p0 >= src.length() {
    return None
  }
  if src[p0] == '}' {
    return Some((PatRep(base, min, min), p0 + 1))
  }
  if src[p0] != ',' {
    return None
  }
  if p0 + 1 < src.length() && src[p0 + 1] == '}' {
    return Some((PatRep(base, min, -1), p0 + 2))
  }
  let (max, p1) = match parse_int(src, p0 + 1) {
    None => return None
    Some(v) => v
  }
  if p1 >= src.length() || src[p1] != '}' || max < min || max > 10000 {
    return None
  }
  Some((PatRep(base, min, max), p1 + 1))
}

///|
/// A run of decimal digits.
fn parse_int(src : Array[Char], pos : Int32) -> (Int32, Int32)? {
  let mut p = pos
  let mut v = 0
  while p < src.length() && is_digit(src[p]) {
    let digit = src[p].to_int() - '0'.to_int()
    if v > (2147483647 - digit) / 10 {
      return None
    }
    v = v * 10 + digit
    p = p + 1
  }
  if p == pos {
    None
  } else {
    Some((v, p))
  }
}

///|
/// A literal, `\d`, a class, or a group.
fn parse_base(src : Array[Char], pos : Int32) -> (PatNode, Int32)? {
  if pos >= src.length() {
    return None
  }
  match src[pos] {
    '\\' =>
      if pos + 1 < src.length() && src[pos + 1] == 'd' {
        Some((PatDigit, pos + 2))
      } else {
        None
      }
    '[' => parse_class(src, pos)
    '(' => parse_group(src, pos)
    ')' | '|' | '?' | '*' | '+' | '{' => None
    c => Some((PatLit(c), pos + 1))
  }
}

///|
/// `(?:alt)` or `(alt)`.
fn parse_group(src : Array[Char], pos : Int32) -> (PatNode, Int32)? {
  let mut p = pos + 1
  let noncapturing = p + 1 < src.length() && src[p] == '?' && src[p + 1] == ':'
  if noncapturing {
    p = p + 2
  }
  let (inner, np) = match parse_alt(src, p) {
    None => return None
    Some(v) => v
  }
  if np >= src.length() || src[np] != ')' {
    return None
  }
  Some(
    (
      if noncapturing {
        inner
      } else {
        PatCapture(capture_count(src, pos) + 1, inner)
      },
      np + 1,
    ),
  )
}

///|
/// Capturing group numbers are lexical, including groups in unmatched branches.
fn capture_count(src : Array[Char], end : Int32) -> Int32 {
  let mut count = 0
  let mut in_class = false
  let mut i = 0
  while i < end {
    if src[i] == '\\' {
      i = i + 2
      continue
    }
    if src[i] == '[' {
      in_class = true
    }
    if src[i] == ']' {
      in_class = false
    }
    if !in_class &&
      src[i] == '(' &&
      !(i + 1 < src.length() && src[i + 1] == '?') {
      count = count + 1
    }
    i = i + 1
  }
  count
}

///|
/// Bound expanded NFA size before allocation; arithmetic is checked against
/// remaining budget before addition/multiplication, including nested repeats.
fn pattern_cost(node : PatNode, budget : Int32) -> Int32? {
  if budget < 4 {
    return None
  }
  match node {
    PatLit(_) | PatDigit | PatClass(_) => Some(1)
    PatCapture(_, inner) => pattern_cost(inner, budget)
    PatSeq(items) | PatAlt(items) => {
      let mut sum = 2
      for item in items {
        let cost = match pattern_cost(item, budget - sum) {
          None => return None
          Some(v) => v
        }
        if cost + 2 > budget - sum {
          return None
        }
        sum = sum + cost + 2
      }
      Some(sum)
    }
    PatRep(inner, min, max) => {
      let cost = match pattern_cost(inner, budget - 4) {
        None => return None
        Some(v) => v + 2
      }
      let copies = if max < 0 { min + 1 } else { max }
      if copies > (budget - 4) / cost {
        None
      } else {
        Some(4 + cost * copies)
      }
    }
  }
}

///|
/// `[...]` with single characters and `a-b` ranges.
fn parse_class(src : Array[Char], pos : Int32) -> (PatNode, Int32)? {
  let ranges : Array[(Char, Char)] = []
  let mut p = pos + 1
  if p < src.length() && src[p] == '^' {
    // Negation is outside the published grammar; reject rather than guess.
    return None
  }
  while p < src.length() && src[p] != ']' {
    let lo = src[p]
    if lo == '\\' {
      return None
    }
    if p + 2 < src.length() && src[p + 1] == '-' && src[p + 2] != ']' {
      let hi = src[p + 2]
      if hi < lo {
        return None
      }
      ranges.push((lo, hi))
      p = p + 3
    } else {
      ranges.push((lo, lo))
      p = p + 1
    }
  }
  if p >= src.length() || ranges.length() == 0 {
    return None
  }
  Some((PatClass(ranges), p + 1))
}

// ---------------------------------------------------------------------------
// Thompson NFA
// ---------------------------------------------------------------------------

///|
let st_char : Int32 = 0

///|
let st_split : Int32 = 1

///|
let st_match : Int32 = 2

///|
/// A character predicate: explicit ranges, and whether `\d` is included.
priv struct PatClassSet {
  ranges : Array[(Char, Char)]
  digits : Bool
}

///|
/// A compiled program: four integers per state (kind, class index, out1, out2).
priv struct PatProg {
  code : Array[Int32]
  classes : Array[PatClassSet]
}

///|
/// A fragment under construction: an entry state and the edges still dangling.
priv struct PatFrag {
  start : Int32
  holes : Array[(Int32, Int32)] // (state index, 0 = out1, 1 = out2)
}

///|
/// Append a state and return its index.
fn pat_emit(
  prog : PatProg,
  kind : Int32,
  cls : Int32,
  out1 : Int32,
  out2 : Int32,
) -> Int32 {
  let idx = prog.code.length() / 4
  prog.code.push(kind)
  prog.code.push(cls)
  prog.code.push(out1)
  prog.code.push(out2)
  idx
}

///|
/// Point every dangling edge at `target`.
fn pat_patch(
  prog : PatProg,
  holes : Array[(Int32, Int32)],
  target : Int32,
) -> Unit {
  for h in holes {
    let slot = h.0 * 4 + 2 + h.1
    prog.code[slot] = target
  }
}

///|
/// An empty fragment: a single epsilon edge that is still dangling.
fn pat_epsilon(prog : PatProg) -> PatFrag {
  let idx = pat_emit(prog, st_split, -1, -1, -1)
  { start: idx, holes: [(idx, 0)], }
}

///|
/// Compile a syntax tree into one fragment.
fn pat_compile(prog : PatProg, node : PatNode) -> PatFrag {
  match node {
    PatCapture(_, inner) => pat_compile(prog, inner)
    PatLit(c) => {
      let cls = prog.classes.length()
      prog.classes.push({ ranges: [(c, c)], digits: false, })
      let idx = pat_emit(prog, st_char, cls, -1, -1)
      { start: idx, holes: [(idx, 0)], }
    }
    PatDigit => {
      let cls = prog.classes.length()
      prog.classes.push({ ranges: [], digits: true, })
      let idx = pat_emit(prog, st_char, cls, -1, -1)
      { start: idx, holes: [(idx, 0)], }
    }
    PatClass(ranges) => {
      let cls = prog.classes.length()
      prog.classes.push({ ranges, digits: false, })
      let idx = pat_emit(prog, st_char, cls, -1, -1)
      { start: idx, holes: [(idx, 0)], }
    }
    PatSeq(items) => pat_compile_seq(prog, items)
    PatAlt(items) => pat_compile_alt(prog, items)
    PatRep(body, min, max) => pat_compile_rep(prog, body, min, max)
  }
}

///|
/// Concatenation: chain the fragments, patching each exit into the next entry.
fn pat_compile_seq(prog : PatProg, items : Array[PatNode]) -> PatFrag {
  if items.length() == 0 {
    return pat_epsilon(prog)
  }
  let mut frag = pat_compile(prog, items[0])
  let mut i = 1
  while i < items.length() {
    let next = pat_compile(prog, items[i])
    pat_patch(prog, frag.holes, next.start)
    frag = { start: frag.start, holes: next.holes, }
    i = i + 1
  }
  frag
}

///|
/// Alternation: a chain of splits, built from the right so each split can point
/// at the rest of the chain.
fn pat_compile_alt(prog : PatProg, items : Array[PatNode]) -> PatFrag {
  if items.length() == 0 {
    return pat_epsilon(prog)
  }
  let mut frag = pat_compile(prog, items[items.length() - 1])
  let mut i = items.length() - 1
  while i > 0 {
    i = i - 1
    let left = pat_compile(prog, items[i])
    let split = pat_emit(prog, st_split, -1, left.start, frag.start)
    let holes : Array[(Int32, Int32)] = []
    for h in left.holes {
      holes.push(h)
    }
    for h in frag.holes {
      holes.push(h)
    }
    frag = { start: split, holes, }
  }
  frag
}

///|
/// Repetition. `min` mandatory copies, then either a loop (unbounded) or
/// `max - min` optional copies. Bounded expansion is what the published corpus
/// needs: no quantifier in it is larger than fourteen.
fn pat_compile_rep(
  prog : PatProg,
  body : PatNode,
  min : Int32,
  max : Int32,
) -> PatFrag {
  if max == 0 {
    return pat_epsilon(prog)
  }
  // The tail: a loop when unbounded, otherwise a cascade of optional copies.
  let mut tail = pat_epsilon(prog)
  if max < 0 {
    let inner = pat_compile(prog, body)
    let split = pat_emit(prog, st_split, -1, inner.start, tail.start)
    pat_patch(prog, inner.holes, split)
    tail = { start: split, holes: tail.holes, }
  } else {
    let mut copies = max - min
    while copies > 0 {
      let inner = pat_compile(prog, body)
      let split = pat_emit(prog, st_split, -1, inner.start, tail.start)
      pat_patch(prog, inner.holes, tail.start)
      tail = { start: split, holes: tail.holes, }
      copies = copies - 1
    }
  }
  // The mandatory prefix.
  let mut head = pat_epsilon(prog)
  let mut made = 0
  while made < min {
    let copy = pat_compile(prog, body)
    pat_patch(prog, head.holes, copy.start)
    head = { start: head.start, holes: copy.holes, }
    made = made + 1
  }
  pat_patch(prog, head.holes, tail.start)
  { start: head.start, holes: tail.holes, }
}

///|
/// Compile a syntax tree and finish it with an accept state. The entry state is
/// not always the first emitted one (an alternation is a split emitted after its
/// branches, a repetition an epsilon emitted before its body), so it is returned
/// alongside the program.
fn pat_build(node : PatNode) -> (PatProg, Int32) {
  let prog : PatProg = { code: [], classes: [], }
  let frag = pat_compile(prog, node)
  let accept = pat_emit(prog, st_match, -1, -1, -1)
  pat_patch(prog, frag.holes, accept)
  (prog, frag.start)
}

// ---------------------------------------------------------------------------
// Simulation
// ---------------------------------------------------------------------------

///|
/// True when `c` is in the class.
fn pat_class_matches(cls : PatClassSet, c : Char) -> Bool {
  if cls.digits && is_digit(c) {
    return true
  }
  for r in cls.ranges {
    if c >= r.0 && c <= r.1 {
      return true
    }
  }
  false
}

///|
/// Add the epsilon closure of `state` to the active list, stamping each state
/// with the current generation so it is added at most once per step.
fn pat_closure(
  prog : PatProg,
  state : Int32,
  mark : Array[Int32],
  gen : Int32,
  out : Array[Int32],
) -> Unit {
  if state < 0 || mark[state] == gen {
    return
  }
  mark[state] = gen
  let work : Array[Int32] = [state]
  let mut head = 0
  while head < work.length() {
    let s = work[head]
    head = head + 1
    if prog.code[s * 4] == st_split {
      let a = prog.code[s * 4 + 2]
      let b = prog.code[s * 4 + 3]
      if a >= 0 && mark[a] != gen {
        mark[a] = gen
        work.push(a)
      }
      if b >= 0 && mark[b] != gen {
        mark[b] = gen
        work.push(b)
      }
    } else {
      out.push(s)
    }
  }
}

///|
/// Run the program over the whole input.
///
/// The live states are kept as a list rather than a bitmap over every state: a
/// plan rule is a large alternation, and after the first digit only a handful of
/// its branches can still be alive. Walking those instead of the whole program is
/// what keeps a validation cheap even for the longest published rule.
fn pat_run(prog : PatProg, start : Int32, input : Array[Char]) -> Bool {
  let states = prog.code.length() / 4
  let mark = Array::make(states, 0)
  let mut gen = 1
  let mut cur : Array[Int32] = []
  pat_closure(prog, start, mark, gen, cur)
  for ch in input {
    if cur.length() == 0 {
      return false
    }
    gen = gen + 1
    let nxt : Array[Int32] = []
    for s in cur {
      if prog.code[s * 4] == st_char {
        let cls = prog.code[s * 4 + 1]
        if pat_class_matches(prog.classes[cls], ch) {
          pat_closure(prog, prog.code[s * 4 + 2], mark, gen, nxt)
        }
      }
    }
    cur = nxt
  }
  for s in cur {
    if prog.code[s * 4] == st_match {
      return true
    }
  }
  false
}

///|
/// Run the program and stop as soon as a prefix of the input has been accepted.
/// This is `lookingAt` semantics: the pattern has to match where the number
/// starts, not the whole of it.
fn pat_run_prefix(prog : PatProg, start : Int32, input : Array[Char]) -> Bool {
  let states = prog.code.length() / 4
  let mark = Array::make(states, 0)
  let mut gen = 1
  let mut cur : Array[Int32] = []
  pat_closure(prog, start, mark, gen, cur)
  let mut step = 0
  while step <= input.length() {
    let mut accepted = false
    for s in cur {
      if prog.code[s * 4] == st_match {
        accepted = true
      }
    }
    if accepted {
      return true
    }
    if step == input.length() || cur.length() == 0 {
      return false
    }
    gen = gen + 1
    let nxt : Array[Int32] = []
    for s in cur {
      if prog.code[s * 4] == st_char {
        let cls = prog.code[s * 4 + 1]
        if pat_class_matches(prog.classes[cls], input[step]) {
          pat_closure(prog, prog.code[s * 4 + 2], mark, gen, nxt)
        }
      }
    }
    cur = nxt
    step = step + 1
  }
  false
}

// ---------------------------------------------------------------------------
// Public surface
// ---------------------------------------------------------------------------

///|
/// A compiled pattern, ready to run: the program and its entry state.
priv struct CompiledPattern {
  prog : PatProg
  start : Int32
}

///|
/// Compile a pattern once. A pattern outside the grammar compiles to a program
/// that matches nothing, so the caller never has to carry the failure around.
fn compile_pattern(pattern : String) -> CompiledPattern {
  match parse_pattern(pattern) {
    None => { prog: { code: [], classes: [], }, start: -1, }
    Some(node) => {
      let (prog, start) = pat_build(node)
      { prog, start, }
    }
  }
}

///|
/// Run a compiled pattern over the whole text.
fn run_pattern(c : CompiledPattern, text : String) -> Bool {
  if c.start < 0 {
    return false
  }
  pat_run(c.prog, c.start, chars_of(text))
}

///|
/// True when the pattern matches some prefix of the text — the `lookingAt`
/// question the plan data asks of its leading-digit patterns. One pass over the
/// input, not one match per prefix.
fn run_pattern_prefix(c : CompiledPattern, text : String) -> Bool {
  if c.start < 0 {
    return false
  }
  pat_run_prefix(c.prog, c.start, chars_of(text))
}

///|
/// True when `text` matches `pattern` in full, under the numbering-plan grammar.
/// A pattern that does not parse matches nothing, so a bad data row can never
/// turn into a false positive.
pub fn matches_pattern(pattern : String, text : String) -> Bool {
  match parse_pattern(pattern) {
    None => false
    Some(node) => {
      let (prog, start) = pat_build(node)
      pat_run(prog, start, chars_of(text))
    }
  }
}

///|
/// True when the pattern is a member of the supported grammar. Used by the
/// data-pipeline tests to prove every published rule can be interpreted.
pub fn pattern_well_formed(pattern : String) -> Bool {
  parse_pattern(pattern) is Some(_)
}