// Port of regex-syntax 0.8.11 src/ast/visitor.rs.

///|
/// A trait for visiting an abstract syntax tree (AST) in depth first order.
///
/// Typical usage of this trait involves providing an implementation and then
/// running it using the [`visit`] function. Upstream's `finish` (which yields
/// the visitor's output) is left to the caller after `visit` returns.
pub(open) trait Visitor {
  /// This method is called before beginning traversal of the AST.
  fn start(Self) -> Unit = _
  /// This method is called on an `Ast` before descending into child `Ast`
  /// nodes.
  fn visit_pre(Self, Ast) -> Unit raise = _
  /// This method is called on an `Ast` after descending all of its child
  /// `Ast` nodes.
  fn visit_post(Self, Ast) -> Unit raise = _
  /// This method is called between child nodes of an `Alternation`.
  fn visit_alternation_in(Self) -> Unit raise = _
  /// This method is called between child nodes of a concatenation.
  fn visit_concat_in(Self) -> Unit raise = _
  /// This method is called on every `ClassSetItem` before descending into
  /// child nodes.
  fn visit_class_set_item_pre(Self, ClassSetItem) -> Unit raise = _
  /// This method is called on every `ClassSetItem` after descending into
  /// child nodes.
  fn visit_class_set_item_post(Self, ClassSetItem) -> Unit raise = _
  /// This method is called on every `ClassSetBinaryOp` before descending into
  /// child nodes.
  fn visit_class_set_binary_op_pre(Self, ClassSetBinaryOp) -> Unit raise = _
  /// This method is called on every `ClassSetBinaryOp` after descending into
  /// child nodes.
  fn visit_class_set_binary_op_post(Self, ClassSetBinaryOp) -> Unit raise = _
  /// This method is called between the left hand and right hand child nodes
  /// of a `ClassSetBinaryOp`.
  fn visit_class_set_binary_op_in(Self, ClassSetBinaryOp) -> Unit raise = _
}

///|
impl Visitor with fn start(_self) {
  ()
}

///|
impl Visitor with fn visit_pre(_self, _ast) {
  ()
}

///|
impl Visitor with fn visit_post(_self, _ast) {
  ()
}

///|
impl Visitor with fn visit_alternation_in(_self) {
  ()
}

///|
impl Visitor with fn visit_concat_in(_self) {
  ()
}

///|
impl Visitor with fn visit_class_set_item_pre(_self, _ast) {
  ()
}

///|
impl Visitor with fn visit_class_set_item_post(_self, _ast) {
  ()
}

///|
impl Visitor with fn visit_class_set_binary_op_pre(_self, _ast) {
  ()
}

///|
impl Visitor with fn visit_class_set_binary_op_post(_self, _ast) {
  ()
}

///|
impl Visitor with fn visit_class_set_binary_op_in(_self, _ast) {
  ()
}

///|
/// Executes an implementation of `Visitor` in constant stack space.
///
/// This function will visit every node in the given `Ast` while calling the
/// appropriate methods provided by the [`Visitor`] trait.
///
/// If the visitor returns an error at any point, then visiting is stopped and
/// the error is returned.
pub fn[V : Visitor] visit(ast : Ast, visitor : V) -> Unit raise {
  HeapVisitor::new().visit(ast, visitor)
}

///|
/// HeapVisitor visits every item in an `Ast` recursively using constant stack
/// size and a heap size proportional to the size of the `Ast`.
priv struct HeapVisitor {
  /// A stack of `Ast` nodes. This is roughly analogous to the call stack
  /// used in a typical recursive visitor.
  stack : Array[(Ast, Frame)]
  /// Similar to the `Ast` stack above, but is used only for character
  /// classes. In particular, character classes embed their own mini
  /// recursive syntax.
  stack_class : Array[(ClassInduct, ClassFrame)]
}

///|
/// Represents a single stack frame while performing structural induction over
/// an `Ast`. Upstream's `head`/`tail` slices are an array and the index of
/// `head`.
priv enum Frame {
  /// A stack frame allocated just before descending into a repetition
  /// operator's child node.
  Repetition(Repetition)
  /// A stack frame allocated just before descending into a group's child
  /// node.
  Group(Group)
  /// The stack frame used while visiting every child node of a concatenation
  /// of expressions.
  Concat(Array[Ast], Int32)
  /// The stack frame used while visiting every child node of an alternation
  /// of expressions.
  Alternation(Array[Ast], Int32)
}

///|
/// Represents a single stack frame while performing structural induction over
/// a character class.
priv enum ClassFrame {
  /// The stack frame used while visiting every child node of a union of
  /// character class items.
  Union(Array[ClassSetItem], Int32)
  /// The stack frame used while a binary class operation.
  Binary(ClassSetBinaryOp)
  /// A stack frame allocated just before descending into a binary operator's
  /// left hand child node.
  BinaryLHS(ClassSetBinaryOp)
  /// A stack frame allocated just before descending into a binary operator's
  /// right hand child node.
  BinaryRHS(ClassSetBinaryOp)
}

///|
/// A representation of the inductive step when performing structural induction
/// over a character class.
priv enum ClassInduct {
  Item(ClassSetItem)
  BinaryOp(ClassSetBinaryOp)
}

///|
fn HeapVisitor::new() -> HeapVisitor {
  { stack: [], stack_class: [], }
}

///|
fn[V : Visitor] HeapVisitor::visit(
  self : HeapVisitor,
  ast : Ast,
  visitor : V,
) -> Unit raise {
  self.stack.clear()
  self.stack_class.clear()
  visitor.start()
  let mut ast = ast
  while true {
    visitor.visit_pre(ast)
    if self.induct(ast, visitor) is Some(x) {
      let child = x.child()
      self.stack.push((ast, x))
      ast = child
      continue
    }
    // No induction means we have a base case, so we can post visit
    // it now.
    visitor.visit_post(ast)

    // At this point, we now try to pop our call stack until it is
    // either empty or we hit another inductive case.
    while true {
      let (post_ast, frame) = match self.stack.pop() {
        None => return
        Some(item) => item
      }
      // If this is a concat/alternate, then we might have additional
      // inductive steps to process.
      if self.pop(frame) is Some(x) {
        match x {
          Alternation(_, _) => visitor.visit_alternation_in()
          Concat(_, _) => visitor.visit_concat_in()
          _ => ()
        }
        ast = x.child()
        self.stack.push((post_ast, x))
        break
      }
      // Otherwise, we've finished visiting all the child nodes for
      // this AST, so we can post visit it now.
      visitor.visit_post(post_ast)
    }
  }
}

///|
/// Build a stack frame for the given AST if one is needed (which occurs if
/// and only if there are child nodes in the AST). Otherwise, return None.
///
/// If this visits a class, then the underlying visitor implementation may
/// return an error which will be passed on here.
fn[V : Visitor] HeapVisitor::induct(
  self : HeapVisitor,
  ast : Ast,
  visitor : V,
) -> Frame? raise {
  match ast {
    ClassBracketed(x) => {
      self.visit_class(x, visitor)
      None
    }
    Repetition(x) => Some(Frame::Repetition(x))
    Group(x) => Some(Frame::Group(x))
    Concat(x) if x.asts.is_empty() => None
    Concat(x) => Some(Frame::Concat(x.asts, 0))
    Alternation(x) if x.asts.is_empty() => None
    Alternation(x) => Some(Frame::Alternation(x.asts, 0))
    _ => None
  }
}

///|
/// Pops the given frame. If the frame has an additional inductive step,
/// then return it, otherwise return `None`.
fn HeapVisitor::pop(_self : HeapVisitor, induct : Frame) -> Frame? {
  match induct {
    Repetition(_) => None
    Group(_) => None
    Concat(asts, i) =>
      if i + 1 >= asts.length() {
        None
      } else {
        Some(Concat(asts, i + 1))
      }
    Alternation(asts, i) =>
      if i + 1 >= asts.length() {
        None
      } else {
        Some(Alternation(asts, i + 1))
      }
  }
}

///|
fn[V : Visitor] HeapVisitor::visit_class(
  self : HeapVisitor,
  ast : ClassBracketed,
  visitor : V,
) -> Unit raise {
  let mut ast = ClassInduct::from_bracketed(ast)
  while true {
    self.visit_class_pre(ast, visitor)
    if self.induct_class(ast) is Some(x) {
      let child = x.child()
      self.stack_class.push((ast, x))
      ast = child
      continue
    }
    self.visit_class_post(ast, visitor)

    // At this point, we now try to pop our call stack until it is
    // either empty or we hit another inductive case.
    while true {
      let (post_ast, frame) = match self.stack_class.pop() {
        None => return
        Some(item) => item
      }
      // If this is a union or a binary op, then we might have
      // additional inductive steps to process.
      if self.pop_class(frame) is Some(x) {
        if x is BinaryRHS(op) {
          visitor.visit_class_set_binary_op_in(op)
        }
        ast = x.child()
        self.stack_class.push((post_ast, x))
        break
      }
      // Otherwise, we've finished visiting all the child nodes for
      // this class node, so we can post visit it now.
      self.visit_class_post(post_ast, visitor)
    }
  }
}

///|
/// Call the appropriate `Visitor` methods given an inductive step.
fn[V : Visitor] HeapVisitor::visit_class_pre(
  _self : HeapVisitor,
  ast : ClassInduct,
  visitor : V,
) -> Unit raise {
  match ast {
    Item(item) => visitor.visit_class_set_item_pre(item)
    BinaryOp(op) => visitor.visit_class_set_binary_op_pre(op)
  }
}

///|
/// Call the appropriate `Visitor` methods given an inductive step.
fn[V : Visitor] HeapVisitor::visit_class_post(
  _self : HeapVisitor,
  ast : ClassInduct,
  visitor : V,
) -> Unit raise {
  match ast {
    Item(item) => visitor.visit_class_set_item_post(item)
    BinaryOp(op) => visitor.visit_class_set_binary_op_post(op)
  }
}

///|
/// Build a stack frame for the given class node if one is needed (which
/// occurs if and only if there are child nodes). Otherwise, return None.
fn HeapVisitor::induct_class(
  _self : HeapVisitor,
  ast : ClassInduct,
) -> ClassFrame? {
  match ast {
    Item(Bracketed(x)) =>
      match x.kind {
        Item(item) => Some(ClassFrame::Union([item], 0))
        BinaryOp(op) => Some(ClassFrame::Binary(op))
      }
    Item(Union(x)) =>
      if x.items.is_empty() {
        None
      } else {
        Some(ClassFrame::Union(x.items, 0))
      }
    BinaryOp(op) => Some(ClassFrame::BinaryLHS(op))
    _ => None
  }
}

///|
/// Pops the given frame. If the frame has an additional inductive step,
/// then return it, otherwise return `None`.
fn HeapVisitor::pop_class(
  _self : HeapVisitor,
  induct : ClassFrame,
) -> ClassFrame? {
  match induct {
    Union(items, i) =>
      if i + 1 >= items.length() {
        None
      } else {
        Some(Union(items, i + 1))
      }
    Binary(_) => None
    BinaryLHS(op) => Some(BinaryRHS(op))
    BinaryRHS(_) => None
  }
}

///|
/// Perform the next inductive step on this frame and return the next
/// child AST node to visit.
fn Frame::child(self : Frame) -> Ast {
  match self {
    Repetition(rep) => rep.ast
    Group(group) => group.ast
    Concat(asts, i) => asts[i]
    Alternation(asts, i) => asts[i]
  }
}

///|
/// Perform the next inductive step on this frame and return the next
/// child class node to visit.
fn ClassFrame::child(self : ClassFrame) -> ClassInduct {
  match self {
    Union(items, i) => Item(items[i])
    Binary(op) => BinaryOp(op)
    BinaryLHS(op) => ClassInduct::from_set(op.lhs)
    BinaryRHS(op) => ClassInduct::from_set(op.rhs)
  }
}

///|
fn ClassInduct::from_bracketed(ast : ClassBracketed) -> ClassInduct {
  ClassInduct::from_set(ast.kind)
}

///|
fn ClassInduct::from_set(ast : ClassSet) -> ClassInduct {
  match ast {
    Item(item) => Item(item)
    BinaryOp(op) => BinaryOp(op)
  }
}