///|
priv enum Inst {
  Char(Int)
  Set(CharSet)
  Split(Int, Int) // try first, backtrack to second
  Jmp(Int)
  Save(Int)
  Assert(AssertKind)
  Backref(Int, Int) // group, case folding mode
  RepChar(Int, CharSet?, Int, Int, Bool) // char (if set is None), set, min, max, greedy
  SetMark(Int) // regs[r] = pos
  IfEmpty(Int, Int) // if pos == regs[r] goto target
  Look(Bool, Bool, Int, Int) // behind, negated, width, body pc
  Atomic(Int) // body pc
  CondRef(Int, Int) // group, pc of the "no" branch
  Match
}

///|
priv struct Compiler {
  prog : Array[Inst]
  subs : Array[(Node, Int)] // deferred sub-programs and the Inst index to patch
  mut nregs : Int
}

///|
/// Maximum number of instructions a single pattern may compile to.
const MAX_PROGRAM : Int = 200000

///|
fn Compiler::emit(self : Compiler, i : Inst) -> Int raise RegexError {
  if self.prog.length() >= MAX_PROGRAM {
    raise Syntax(pattern="", pos=0, message="pattern too large")
  }
  self.prog.push(i)
  self.prog.length() - 1
}

///|
fn Compiler::pc(self : Compiler) -> Int {
  self.prog.length()
}

///|
fn nullable(node : Node) -> Bool {
  match node {
    Empty | Assert(_) | Look(_, _, _) | Backref(_, _) => true
    Char(_) | Set(_) => false
    Seq(items) => items.iter().all(nullable)
    Alt(branches) => branches.iter().any(nullable)
    Group(_, n) | Atomic(n) => nullable(n)
    Repeat(n, min, _, _) => min == 0 || nullable(n)
    Cond(_, a, b) => nullable(a) || nullable(b)
  }
}

///|
fn Compiler::compile(self : Compiler, node : Node) -> Unit raise RegexError {
  match node {
    Empty => ()
    Char(c) => ignore(self.emit(Char(c)))
    Set(s) => ignore(self.emit(Set(s)))
    Seq(items) =>
      for it in items {
        self.compile(it)
      }
    Alt(branches) => {
      // Split(b1, next) b1 Jmp(end) next: Split(b2, next2) ...
      let jumps = []
      for i, b in branches {
        if i < branches.length() - 1 {
          let split = self.emit(Split(0, 0))
          self.compile(b)
          jumps.push(self.emit(Jmp(0)))
          self.prog[split] = Split(split + 1, self.pc())
        } else {
          self.compile(b)
        }
      }
      let end = self.pc()
      for j in jumps {
        self.prog[j] = Jmp(end)
      }
    }
    Group(g, n) => {
      ignore(self.emit(Save(g * 2)))
      self.compile(n)
      ignore(self.emit(Save(g * 2 + 1)))
    }
    Assert(k) => ignore(self.emit(Assert(k)))
    Backref(g, ic) => ignore(self.emit(Backref(g, ic)))
    Look(n, behind, neg) => {
      let width = match fixed_width(n) {
        Some(w) => w
        None => 0
      }
      let at = self.emit(Look(behind, neg, width, 0))
      self.subs.push((n, at))
    }
    Atomic(n) => {
      let at = self.emit(Atomic(0))
      self.subs.push((n, at))
    }
    Cond(g, yes, no) => {
      let cond = self.emit(CondRef(g, 0))
      self.compile(yes)
      let j = self.emit(Jmp(0))
      self.prog[cond] = CondRef(g, self.pc())
      self.compile(no)
      self.prog[j] = Jmp(self.pc())
    }
    Repeat(n, min, max, greed) =>
      if greed == Possessive {
        let at = self.emit(Atomic(0))
        self.subs.push((Repeat(n, min, max, Greedy), at))
      } else {
        self.compile_repeat(n, min, max, greed == Greedy)
      }
  }
}

///|
fn Compiler::compile_repeat(
  self : Compiler,
  n : Node,
  min : Int,
  max : Int,
  greedy : Bool,
) -> Unit raise RegexError {
  match n {
    Char(c) => {
      ignore(self.emit(RepChar(c, None, min, max, greedy)))
      return
    }
    Set(s) => {
      ignore(self.emit(RepChar(0, Some(s), min, max, greedy)))
      return
    }
    _ => ()
  }
  if max == 0 {
    return
  }
  for _ in 0..= 0 {
      self.prog[check] = IfEmpty(reg, exit)
    }
  } else {
    // optional iterations; like CPython, an iteration that consumed nothing
    // ends the repetition
    let can_be_empty = nullable(n)
    let reg = self.nregs
    if can_be_empty {
      self.nregs += 1
    }
    let splits = []
    let checks = []
    for _ in min.. Unit raise RegexError {
  let mut i = 0
  while i < self.subs.length() {
    let (node, at) = self.subs[i]
    let start = self.pc()
    self.compile(node)
    ignore(self.emit(Match))
    self.prog[at] = match self.prog[at] {
      Look(b, neg, w, _) => Look(b, neg, w, start)
      Atomic(_) => Atomic(start)
      other => other
    }
    i += 1
  }
}

///|
/// A conservative approximation of the characters a match can start with.
priv struct FirstSet {
  mut lo : UInt64
  mut hi : UInt64
  mut non_ascii : Bool
}

///|
fn FirstSet::add_char(self : FirstSet, c : Int) -> Unit {
  if c < 64 {
    self.lo = self.lo | (1UL << c)
  } else if c < 128 {
    self.hi = self.hi | (1UL << (c - 64))
  } else {
    self.non_ascii = true
  }
}

///|
fn FirstSet::add_set(self : FirstSet, s : CharSet) -> Unit {
  self.lo = self.lo | s.lo
  self.hi = self.hi | s.hi
  if s.has_non_ascii {
    self.non_ascii = true
  }
}

///|
/// Adds the possible first characters of `node` to `fs`; returns whether
/// `node` can match without consuming a character.
fn first_chars(node : Node, fs : FirstSet) -> Bool {
  match node {
    Empty | Assert(_) | Look(_, _, _) => true
    Char(c) => {
      fs.add_char(c)
      false
    }
    Set(s) => {
      fs.add_set(s)
      false
    }
    Seq(items) => {
      for it in items {
        if !first_chars(it, fs) {
          return false
        }
      }
      true
    }
    Alt(branches) => {
      let mut nul = false
      for b in branches {
        if first_chars(b, fs) {
          nul = true
        }
      }
      nul
    }
    Group(_, n) | Atomic(n) => first_chars(n, fs)
    Repeat(n, min, _, _) => first_chars(n, fs) || min == 0
    Backref(_, _) => true
    Cond(_, a, b) => {
      let x = first_chars(a, fs)
      let y = first_chars(b, fs)
      x || y
    }
  }
}