// Port of regex-syntax 0.8.11 src/ast/parse.rs.
//
// This module provides a regular expression parser. Positions are UTF-8 byte
// offsets like upstream; the parser additionally tracks the char index that
// corresponds to the current byte offset to read the UTF-16 MoonBit string.

///|
/// A primitive is an expression with no sub-expressions. This includes
/// literals, assertions and non-set character classes. This representation
/// is used as intermediate state in the parser.
///
/// This does not include ASCII character classes, since they can only appear
/// within a set character class.
priv enum Primitive {
  Literal(Literal)
  Assertion(Assertion)
  Dot(Span)
  Perl(ClassPerl)
  Unicode(ClassUnicode)
}

///|
/// Return the span of this primitive.
fn Primitive::span(self : Primitive) -> Span {
  match self {
    Literal(x) => x.span
    Assertion(x) => x.span
    Dot(span) => span
    Perl(x) => x.span
    Unicode(x) => x.span
  }
}

///|
/// Convert this primitive into a proper AST.
fn Primitive::into_ast(self : Primitive) -> Ast {
  match self {
    Literal(lit) => Ast::Literal(lit)
    Assertion(assert) => Ast::Assertion(assert)
    Dot(span) => Ast::Dot(span)
    Perl(cls) => Ast::ClassPerl(cls)
    Unicode(cls) => Ast::ClassUnicode(cls)
  }
}

///|
/// Convert this primitive into an item in a character class.
///
/// If this primitive is not a legal item (i.e., an assertion or a dot),
/// then return an error.
fn Primitive::into_class_set_item(
  self : Primitive,
  p : ParserI,
) -> ClassSetItem raise AstError {
  match self {
    Literal(lit) => ClassSetItem::Literal(lit)
    Perl(cls) => ClassSetItem::Perl(cls)
    Unicode(cls) => ClassSetItem::Unicode(cls)
    x => raise p.error(x.span(), ClassEscapeInvalid)
  }
}

///|
/// Convert this primitive into a literal in a character class. In
/// particular, literals are the only valid items that can appear in
/// ranges.
///
/// If this primitive is not a legal item (i.e., a class, assertion or a
/// dot), then return an error.
fn Primitive::into_class_literal(
  self : Primitive,
  p : ParserI,
) -> Literal raise AstError {
  match self {
    Literal(lit) => lit
    x => raise p.error(x.span(), ClassRangeLiteral)
  }
}

///|
/// Returns true if the given character is a hexadecimal digit.
fn is_hex(c : Char) -> Bool {
  ('0' <= c && c <= '9') || ('a' <= c && c <= 'f') || ('A' <= c && c <= 'F')
}

///|
/// Returns true if the given character is a valid in a capture group name.
///
/// If `first` is true, then `c` is treated as the first character in the
/// group name (which must be alphabetic or underscore).
fn is_capture_char(c : Char, first : Bool) -> Bool {
  if first {
    c == '_' || is_alphabetic(c)
  } else {
    c == '_' || c == '.' || c == '[' || c == ']' || is_alphanumeric(c)
  }
}

///|
/// A builder for a regular expression parser.
///
/// This builder permits modifying configuration options for the parser.
pub struct ParserBuilder {
  priv mut ignore_whitespace : Bool
  priv mut nest_limit : UInt32
  priv mut octal : Bool
  priv mut empty_min_range : Bool
}

///|
/// Create a new parser builder with a default configuration.
pub fn ParserBuilder::new() -> ParserBuilder {
  {
    ignore_whitespace: false,
    nest_limit: 250,
    octal: false,
    empty_min_range: false,
  }
}

///|
/// Build a parser from this configuration with the given pattern.
pub fn ParserBuilder::build(self : ParserBuilder) -> Parser {
  {
    pos: { offset: 0, line: 1, column: 1, },
    capture_index: 0,
    nest_limit: self.nest_limit,
    octal: self.octal,
    empty_min_range: self.empty_min_range,
    initial_ignore_whitespace: self.ignore_whitespace,
    ignore_whitespace: self.ignore_whitespace,
    comments: [],
    stack_group: [],
    stack_class: [],
    capture_names: [],
  }
}

///|
/// Set the nesting limit for this parser.
pub fn ParserBuilder::nest_limit(
  self : ParserBuilder,
  limit : UInt32,
) -> ParserBuilder {
  self.nest_limit = limit
  self
}

///|
/// Whether to support octal syntax or not.
pub fn ParserBuilder::octal(self : ParserBuilder, yes : Bool) -> ParserBuilder {
  self.octal = yes
  self
}

///|
/// Enable verbose mode in the regular expression.
pub fn ParserBuilder::ignore_whitespace(
  self : ParserBuilder,
  yes : Bool,
) -> ParserBuilder {
  self.ignore_whitespace = yes
  self
}

///|
/// Allow using `{,n}` as an equivalent to `{0,n}`.
pub fn ParserBuilder::empty_min_range(
  self : ParserBuilder,
  yes : Bool,
) -> ParserBuilder {
  self.empty_min_range = yes
  self
}

///|
/// A regular expression parser.
///
/// This parses a string representation of a regular expression into an
/// abstract syntax tree. The size of the tree is proportional to the length
/// of the regular expression pattern.
pub struct Parser {
  /// The current position of the parser.
  priv mut pos : Position
  /// The current capture index.
  priv mut capture_index : UInt32
  /// The maximum number of open parens/brackets allowed.
  priv nest_limit : UInt32
  /// Whether to support octal syntax or not.
  priv octal : Bool
  /// The initial setting for `ignore_whitespace` as provided by
  /// `ParserBuilder`. It is used when resetting the parser's state.
  priv initial_ignore_whitespace : Bool
  /// Whether the parser supports `{,n}` repetitions as an equivalent to
  /// `{0,n}.`
  priv empty_min_range : Bool
  /// Whether whitespace should be ignored. When enabled, comments are
  /// also permitted.
  priv mut ignore_whitespace : Bool
  /// A list of comments, in order of appearance.
  priv comments : Array[Comment]
  /// A stack of grouped sub-expressions, including alternations.
  priv stack_group : Array[GroupState]
  /// A stack of nested character classes. This is only non-empty when
  /// parsing a class.
  priv stack_class : Array[ClassState]
  /// A sorted sequence of capture names. This is used to detect duplicate
  /// capture names and report an error if one is detected.
  priv capture_names : Array[CaptureName]
}

///|
/// ParserI is the internal parser implementation.
///
/// We use this separate type so that we can carry the provided pattern string
/// along with us. In particular, a `Parser` internal state is not tied to any
/// one pattern, but `ParserI` is.
priv struct ParserI {
  /// The parser state/configuration.
  parser : Parser
  /// The full regular expression provided by the user.
  pattern : String
  /// The chars of `pattern`.
  chars : Array[Char]
  /// The UTF-8 byte offset of every char of `pattern`, followed by the total
  /// UTF-8 length.
  offsets : Array[Int32]
  /// For every UTF-8 byte offset that starts a char (or is the end), the
  /// index of that char; -1 elsewhere.
  index_at : FixedArray[Int32]
}

///|
/// GroupState represents a single stack frame while parsing nested groups
/// and alternations. Each frame records the state up to an opening parenthesis
/// or a alternating bracket `|`.
priv enum GroupState {
  /// This state is pushed whenever an opening group is found.
  Group(concat~ : Concat, group~ : Group, ignore_whitespace~ : Bool)
  /// This state is pushed whenever a new alternation branch is found. If
  /// an alternation branch is found and this state is at the top of the
  /// stack, then this state should be modified to include the new
  /// alternation.
  Alternation(Alternation)
}

///|
/// ClassState represents a single stack frame while parsing character classes.
/// Each frame records the state up to an intersection, difference, symmetric
/// difference or nested class.
///
/// Note that a parser's character class stack is only non-empty when parsing
/// a character class. In all other cases, it is empty.
priv enum ClassState {
  /// This state is pushed whenever an opening bracket is found.
  Open(union~ : ClassSetUnion, set~ : ClassBracketed)
  /// This state is pushed when a operator is seen. When popped, the stored
  /// set becomes the left hand side of the operator.
  Op(kind~ : ClassSetBinaryOpKind, lhs~ : ClassSet)
}

///|
/// Create a new parser with a default configuration.
pub fn Parser::new() -> Parser {
  ParserBuilder::new().build()
}

///|
/// Parse the regular expression into an abstract syntax tree.
pub fn Parser::parse(self : Parser, pattern : String) -> Ast raise AstError {
  ParserI::new(self, pattern).parse()
}

///|
/// Parse the regular expression and return an abstract syntax tree with
/// all of the comments found in the pattern.
pub fn Parser::parse_with_comments(
  self : Parser,
  pattern : String,
) -> WithComments raise AstError {
  ParserI::new(self, pattern).parse_with_comments()
}

///|
/// Reset the internal state of a parser.
///
/// This is called at the beginning of every parse. This prevents the
/// parser from running with inconsistent state (say, if a previous
/// invocation returned an error and the parser is reused).
fn Parser::reset(self : Parser) -> Unit {
  // These settings should be in line with the construction
  // in `ParserBuilder::build`.
  self.pos = { offset: 0, line: 1, column: 1, }
  self.ignore_whitespace = self.initial_ignore_whitespace
  self.comments.clear()
  self.stack_group.clear()
  self.stack_class.clear()
}

///|
/// Build an internal parser from a parser configuration and a pattern.
fn ParserI::new(parser : Parser, pattern : String) -> ParserI {
  let chars = []
  let offsets = []
  let mut offset = 0
  for c in pattern {
    chars.push(c)
    offsets.push(offset)
    offset += len_utf8(c)
  }
  offsets.push(offset)
  let index_at = FixedArray::make(offset + 1, -1)
  for i, o in offsets {
    index_at[o] = i
  }
  { parser, pattern, chars, offsets, index_at, }
}

///|
/// Return a reference to the pattern being parsed.
fn ParserI::pattern(self : ParserI) -> String {
  self.pattern
}

///|
/// Create a new error with the given span and error type.
fn ParserI::error(self : ParserI, span : Span, kind : ErrorKind) -> AstError {
  AstError(kind~, pattern=self.pattern(), span~)
}

///|
/// Return the current offset of the parser.
///
/// The offset starts at `0` from the beginning of the regular expression
/// pattern string.
fn ParserI::offset(self : ParserI) -> Int32 {
  self.parser.pos.offset
}

///|
/// Return the current line number of the parser.
fn ParserI::line(self : ParserI) -> Int32 {
  self.parser.pos.line
}

///|
/// Return the current column of the parser.
fn ParserI::column(self : ParserI) -> Int32 {
  self.parser.pos.column
}

///|
/// The char index of the given byte offset.
fn ParserI::index_of(self : ParserI, offset : Int32) -> Int32 {
  let i = self.index_at[offset]
  guard i >= 0 else { abort("offset \{offset} is not a char boundary") }
  i
}

///|
/// The text between two byte offsets.
fn ParserI::slice(self : ParserI, start : Int32, end : Int32) -> String {
  String::from_array(self.chars[self.index_of(start):self.index_of(end)])
}

///|
/// Return the next capturing index. Each subsequent call increments the
/// internal index.
///
/// The span given should correspond to the location of the opening
/// parenthesis.
///
/// If the capture limit is exceeded, then an error is returned.
fn ParserI::next_capture_index(
  self : ParserI,
  span : Span,
) -> UInt32 raise AstError {
  let current = self.parser.capture_index
  if current == 4294967295U {
    raise self.error(span, CaptureLimitExceeded)
  }
  let i = current + 1
  self.parser.capture_index = i
  i
}

///|
/// Adds the given capture name to this parser. If this capture name has
/// already been used, then an error is returned.
fn ParserI::add_capture_name(
  self : ParserI,
  cap : CaptureName,
) -> Unit raise AstError {
  let names = self.parser.capture_names
  // `binary_search_by_key` on the names (byte-wise order).
  let mut lo = 0
  let mut hi = names.length()
  while lo < hi {
    let mid = lo + (hi - lo) / 2
    let cmp = compare_utf8(names[mid].name, cap.name)
    if cmp == 0 {
      raise self.error(cap.span, GroupNameDuplicate(original=names[mid].span))
    } else if cmp < 0 {
      lo = mid + 1
    } else {
      hi = mid
    }
  }
  names.insert(lo, cap)
}

///|
/// Rust `str` ordering: byte-wise on UTF-8, which equals code point order.
fn compare_utf8(a : String, b : String) -> Int32 {
  let xs = a.iter().collect()
  let ys = b.iter().collect()
  let n = if xs.length() < ys.length() { xs.length() } else { ys.length() }
  for i in 0.. Bool {
  self.parser.ignore_whitespace
}

///|
/// Return the character at the current position of the parser.
///
/// This panics if the current position does not point to a valid char.
fn ParserI::char(self : ParserI) -> Char {
  self.char_at(self.offset())
}

///|
/// Return the character at the given position.
///
/// This panics if the given position does not point to a valid char.
fn ParserI::char_at(self : ParserI, i : Int32) -> Char {
  match self.chars.get(self.index_of(i)) {
    Some(c) => c
    None => abort("expected char at offset \{i}")
  }
}

///|
/// Bump the parser to the next Unicode scalar value.
///
/// If the end of the input has been reached, then `false` is returned.
fn ParserI::bump(self : ParserI) -> Bool {
  if self.is_eof() {
    return false
  }
  let { offset, line, column, } = self.pos()
  let (line, column) = if self.char() == '\n' {
    (line + 1, 1)
  } else {
    (line, column + 1)
  }
  let offset = offset + len_utf8(self.char())
  self.parser.pos = { offset, line, column, }
  !self.is_eof()
}

///|
/// If the substring starting at the current position of the parser has
/// the given prefix, then bump the parser to the character immediately
/// following the prefix and return true. Otherwise, don't bump the parser
/// and return false.
fn ParserI::bump_if(self : ParserI, prefix : String) -> Bool {
  let start = self.index_of(self.offset())
  let prefix_chars : Array[Char] = prefix.iter().collect()
  if start + prefix_chars.length() > self.chars.length() {
    return false
  }
  for i, c in prefix_chars {
    if self.chars[start + i] != c {
      return false
    }
  }
  for _ in 0.. Bool {
  self.bump_if("?=") ||
  self.bump_if("?!") ||
  self.bump_if("?<=") ||
  self.bump_if("? Bool {
  if !self.bump() {
    return false
  }
  self.bump_space()
  !self.is_eof()
}

///|
/// If the `x` flag is enabled (i.e., whitespace insensitivity with
/// comments), then this will advance the parser through all whitespace
/// and comments to the next non-whitespace non-comment byte.
///
/// If the `x` flag is disabled, then this is a no-op.
fn ParserI::bump_space(self : ParserI) -> Unit {
  if !self.ignore_whitespace() {
    return
  }
  while !self.is_eof() {
    if is_whitespace(self.char()) {
      ignore(self.bump())
    } else if self.char() == '#' {
      let start = self.pos()
      let comment_text = StringBuilder()
      ignore(self.bump())
      while !self.is_eof() {
        let c = self.char()
        ignore(self.bump())
        if c == '\n' {
          break
        }
        comment_text.write_char(c)
      }
      let comment = {
        span: Span::new(start, self.pos()),
        comment: comment_text.to_string(),
      }
      self.parser.comments.push(comment)
    } else {
      break
    }
  }
}

///|
/// Peek at the next character in the input without advancing the parser.
///
/// If the input has been exhausted, then this returns `None`.
fn ParserI::peek(self : ParserI) -> Char? {
  if self.is_eof() {
    return None
  }
  self.chars.get(self.index_of(self.offset()) + 1)
}

///|
/// Like peek, but will ignore spaces when the parser is in whitespace
/// insensitive mode.
fn ParserI::peek_space(self : ParserI) -> Char? {
  if !self.ignore_whitespace() {
    return self.peek()
  }
  if self.is_eof() {
    return None
  }
  let mut start = self.index_of(self.offset()) + 1
  let mut in_comment = false
  for i in start.. Bool {
  self.offset() == self.offsets[self.offsets.length() - 1]
}

///|
/// Return the current position of the parser, which includes the offset,
/// line and column.
fn ParserI::pos(self : ParserI) -> Position {
  self.parser.pos
}

///|
/// Create a span at the current position of the parser. Both the start
/// and end of the span are set.
fn ParserI::span(self : ParserI) -> Span {
  Span::splat(self.pos())
}

///|
/// Create a span that covers the current character.
fn ParserI::span_char(self : ParserI) -> Span {
  let mut next = Position::new(
    self.offset() + len_utf8(self.char()),
    self.line(),
    self.column() + 1,
  )
  if self.char() == '\n' {
    next = { ..next, line: next.line + 1, column: 1, }
  }
  Span::new(self.pos(), next)
}

///|
/// Parse and push a single alternation on to the parser's internal stack.
/// If the top of the stack already has an alternation, then add to that
/// instead of pushing a new one.
///
/// The concatenation given corresponds to a single alternation branch.
/// The concatenation returned starts the next branch and is empty.
///
/// This assumes the parser is currently positioned at `|` and will advance
/// the parser to the character following `|`.
fn ParserI::push_alternate(self : ParserI, concat : Concat) -> Concat {
  guard! self.char() == '|'
  concat.span = { ..concat.span, end: self.pos(), }
  self.push_or_add_alternation(concat)
  ignore(self.bump())
  { span: self.span(), asts: [], }
}

///|
/// Pushes or adds the given branch of an alternation to the parser's
/// internal stack of state.
fn ParserI::push_or_add_alternation(self : ParserI, concat : Concat) -> Unit {
  let stack = self.parser.stack_group
  if stack.last() is Some(Alternation(alts)) {
    alts.asts.push(concat.into_ast())
    return
  }
  stack.push(
    Alternation({
      span: Span::new(concat.span.start, self.pos()),
      asts: [concat.into_ast()],
    }),
  )
}

///|
/// Parse and push a group AST (and its parent concatenation) on to the
/// parser's internal stack. Return a fresh concatenation corresponding
/// to the group's sub-AST.
///
/// If a set of flags was found (with no group), then the concatenation
/// is returned with that set of flags added.
///
/// This assumes that the parser is currently positioned on the opening
/// parenthesis. It advances the parser to the character at the start
/// of the sub-expression (or adjoining expression).
///
/// If there was a problem parsing the start of the group, then an error
/// is returned.
fn ParserI::push_group(
  self : ParserI,
  concat : Concat,
) -> Concat raise AstError {
  guard! self.char() == '('
  match self.parse_group() {
    Left(set) => {
      let ignore = set.flags.flag_state(IgnoreWhitespace)
      if ignore is Some(v) {
        self.parser.ignore_whitespace = v
      }
      concat.asts.push(Flags(set))
      concat
    }
    Right(group) => {
      let old_ignore_whitespace = self.ignore_whitespace()
      let new_ignore_whitespace = (match group.flags() {
        Some(f) => f.flag_state(IgnoreWhitespace)
        None => None
      }).unwrap_or(old_ignore_whitespace)
      self.parser.stack_group.push(
        Group(concat~, group~, ignore_whitespace=old_ignore_whitespace),
      )
      self.parser.ignore_whitespace = new_ignore_whitespace
      { span: self.span(), asts: [], }
    }
  }
}

///|
/// Pop a group AST from the parser's internal stack and set the group's
/// AST to the given concatenation. Return the concatenation containing
/// the group.
///
/// This assumes that the parser is currently positioned on the closing
/// parenthesis and advances the parser to the character following the `)`.
///
/// If no such group could be popped, then an unopened group error is
/// returned.
fn ParserI::pop_group(
  self : ParserI,
  group_concat : Concat,
) -> Concat raise AstError {
  guard! self.char() == ')'
  let stack = self.parser.stack_group
  let (prior_concat, group, ignore_whitespace, alt) = match stack.pop() {
    Some(Group(concat~, group~, ignore_whitespace~)) =>
      (concat, group, ignore_whitespace, None)
    Some(Alternation(alt)) =>
      match stack.pop() {
        Some(Group(concat~, group~, ignore_whitespace~)) =>
          (concat, group, ignore_whitespace, Some(alt))
        None | Some(Alternation(_)) =>
          raise self.error(self.span_char(), GroupUnopened)
      }
    None => raise self.error(self.span_char(), GroupUnopened)
  }
  self.parser.ignore_whitespace = ignore_whitespace
  group_concat.span = { ..group_concat.span, end: self.pos(), }
  ignore(self.bump())
  group.span = { ..group.span, end: self.pos(), }
  match alt {
    Some(alt) => {
      alt.span = { ..alt.span, end: group_concat.span.end, }
      alt.asts.push(group_concat.into_ast())
      group.ast = alt.into_ast()
    }
    None => group.ast = group_concat.into_ast()
  }
  prior_concat.asts.push(Group(group))
  prior_concat
}

///|
/// Pop the last state from the parser's internal stack, if it exists, and
/// add the given concatenation to it. There either must be no state or a
/// single alternation item on the stack. Any other scenario produces an
/// error.
///
/// This assumes that the parser has advanced to the end.
fn ParserI::pop_group_end(
  self : ParserI,
  concat : Concat,
) -> Ast raise AstError {
  concat.span = { ..concat.span, end: self.pos(), }
  let stack = self.parser.stack_group
  let ast = match stack.pop() {
    None => concat.into_ast()
    Some(Alternation(alt)) => {
      alt.span = { ..alt.span, end: self.pos(), }
      alt.asts.push(concat.into_ast())
      Ast::Alternation(alt)
    }
    Some(Group(group~, ..)) => raise self.error(group.span, GroupUnclosed)
  }
  // If we try to pop again, there should be nothing.
  match stack.pop() {
    None => ast
    Some(Alternation(_)) =>
      // This unreachable is unfortunate. This case can't happen
      // because the only way we can be here is if there were two
      // `GroupState::Alternation`s adjacent in the parser's stack,
      // which we guarantee to never happen because we never push a
      // `GroupState::Alternation` if one is already at the top of
      // the stack.
      abort("unreachable")
    Some(Group(group~, ..)) => raise self.error(group.span, GroupUnclosed)
  }
}

///|
/// Parse the opening of a character class and push the current class
/// parsing context onto the parser's stack. This assumes that the parser
/// is positioned at an opening `[`. The given union should correspond to
/// the union of set items built up before seeing the `[`.
///
/// If there was a problem parsing the opening of the class, then an error
/// is returned. Otherwise, a new union of set items for the class is
/// returned (which may be populated with either a `]` or a `-`).
fn ParserI::push_class_open(
  self : ParserI,
  parent_union : ClassSetUnion,
) -> ClassSetUnion raise AstError {
  guard! self.char() == '['
  let (nested_set, nested_union) = self.parse_set_class_open()
  self.parser.stack_class.push(Open(union=parent_union, set=nested_set))
  nested_union
}

///|
/// Parse the end of a character class set and pop the character class
/// parser stack. The union given corresponds to the last union built
/// before seeing the closing `]`. The union returned corresponds to the
/// parent character class set with the nested class added to it.
///
/// This assumes that the parser is positioned at a `]` and will advance
/// the parser to the byte immediately following the `]`.
///
/// If the stack is empty after popping, then this returns the final
/// "top-level" character class AST (where a "top-level" character class
/// is one that is not nested inside any other character class).
///
/// If there is no corresponding opening bracket on the parser's stack,
/// then an error is returned.
fn ParserI::pop_class(
  self : ParserI,
  nested_union : ClassSetUnion,
) -> Either[ClassSetUnion, ClassBracketed] {
  guard! self.char() == ']'
  let item = ClassSet::Item(nested_union.into_item())
  let prevset = self.pop_class_op(item)
  let stack = self.parser.stack_class
  match stack.pop() {
    None =>
      // We can never observe an empty stack:
      //
      // 1) We are guaranteed to start with a non-empty stack since
      //    the character class parser is only initiated when it sees
      //    a `[`.
      // 2) If we ever observe an empty stack while popping after
      //    seeing a `]`, then we signal the character class parser
      //    to terminate.
      abort("unexpected empty character class stack")
    Some(Op(..)) =>
      // This panic is unfortunate, but this case is impossible
      // since we already popped the Op state if one exists above.
      // Namely, every push to the class parser stack is guarded by
      // whether an existing Op is already on the top of the stack.
      // If it is, the existing Op is modified. That is, the stack
      // can never have consecutive Op states.
      abort("unexpected ClassState::Op")
    Some(Open(union~, set~)) => {
      ignore(self.bump())
      set.span = { ..set.span, end: self.pos(), }
      set.kind = prevset
      if stack.is_empty() {
        Right(set)
      } else {
        union.push(Bracketed(set))
        Left(union)
      }
    }
  }
}

///|
/// Return an "unclosed class" error whose span points to the most
/// recently opened class.
///
/// This should only be called while parsing a character class.
fn ParserI::unclosed_class_error(self : ParserI) -> AstError {
  for state in self.parser.stack_class.rev_iter() {
    if state is Open(set~, ..) {
      return self.error(set.span, ClassUnclosed)
    }
  }
  // We are guaranteed to have a non-empty stack with at least
  // one open bracket, so we should never get here.
  abort("no open character class found")
}

///|
/// Push the current set of class items on to the class parser's stack as
/// the left hand side of the given operator.
///
/// A fresh set union is returned, which should be used to build the right
/// hand side of this operator.
fn ParserI::push_class_op(
  self : ParserI,
  next_kind : ClassSetBinaryOpKind,
  next_union : ClassSetUnion,
) -> ClassSetUnion {
  let item = ClassSet::Item(next_union.into_item())
  let new_lhs = self.pop_class_op(item)
  self.parser.stack_class.push(Op(kind=next_kind, lhs=new_lhs))
  { span: self.span(), items: [], }
}

///|
/// Pop a character class set from the character class parser stack. If the
/// top of the stack is just an item (not an operation), then return the
/// given set unchanged. If the top of the stack is an operation, then the
/// given set will be used as the rhs of the operation on the top of the
/// stack. In that case, the binary operation is returned as a set.
fn ParserI::pop_class_op(self : ParserI, rhs : ClassSet) -> ClassSet {
  let stack = self.parser.stack_class
  let (kind, lhs) = match stack.pop() {
    Some(Op(kind~, lhs~)) => (kind, lhs)
    Some(Open(..) as state) => {
      stack.push(state)
      return rhs
    }
    None => abort("unreachable")
  }
  let span = Span::new(lhs.span().start, rhs.span().end)
  BinaryOp({ span, kind, lhs, rhs, })
}

///|
/// Upstream's `either::Either`.
priv enum Either[L, R] {
  Left(L)
  Right(R)
}

///|
/// Parse the regular expression into an abstract syntax tree.
fn ParserI::parse(self : ParserI) -> Ast raise AstError {
  self.parse_with_comments().ast
}

///|
/// Parse the regular expression and return an abstract syntax tree with
/// all of the comments found in the pattern.
fn ParserI::parse_with_comments(self : ParserI) -> WithComments raise AstError {
  guard self.offset() == 0 else { abort("parser can only be used once") }
  self.parser.reset()
  let mut concat : Concat = { span: self.span(), asts: [], }
  while true {
    self.bump_space()
    if self.is_eof() {
      break
    }
    match self.char() {
      '(' => concat = self.push_group(concat)
      ')' => concat = self.pop_group(concat)
      '|' => concat = self.push_alternate(concat)
      '[' => {
        let class = self.parse_set_class()
        concat.asts.push(ClassBracketed(class))
      }
      '?' => concat = self.parse_uncounted_repetition(concat, ZeroOrOne)
      '*' => concat = self.parse_uncounted_repetition(concat, ZeroOrMore)
      '+' => concat = self.parse_uncounted_repetition(concat, OneOrMore)
      '{' => concat = self.parse_counted_repetition(concat)
      _ => concat.asts.push(self.parse_primitive().into_ast())
    }
  }
  let ast = self.pop_group_end(concat)
  NestLimiter::new(self).check(ast)
  let comments = self.parser.comments.copy()
  self.parser.comments.clear()
  { ast, comments, }
}

///|
/// Parses an uncounted repetition operation. An uncounted repetition
/// operator includes ?, * and +, but does not include the {m,n} syntax.
/// The given `kind` should correspond to the operator observed by the
/// caller.
///
/// This assumes that the parser is currently positioned at the repetition
/// operator and advances the parser to the first character after the
/// operator. (Note that the operator may include a single additional `?`,
/// which makes the operator ungreedy.)
///
/// The caller should include the concatenation that is being built. The
/// concatenation returned includes the repetition operator applied to the
/// last expression in the given concatenation.
fn ParserI::parse_uncounted_repetition(
  self : ParserI,
  concat : Concat,
  kind : RepetitionKind,
) -> Concat raise AstError {
  guard! self.char() == '?' || self.char() == '*' || self.char() == '+'
  let op_start = self.pos()
  let ast = match concat.asts.pop() {
    Some(ast) => ast
    None => raise self.error(self.span(), RepetitionMissing)
  }
  match ast {
    Empty(_) | Flags(_) => raise self.error(self.span(), RepetitionMissing)
    _ => ()
  }
  let mut greedy = true
  if self.bump() && self.char() == '?' {
    greedy = false
    ignore(self.bump())
  }
  concat.asts.push(
    Repetition({
      span: ast.span().with_end(self.pos()),
      op: { span: Span::new(op_start, self.pos()), kind, },
      greedy,
      ast,
    }),
  )
  concat
}

///|
/// Parses a counted repetition operation. A counted repetition operator
/// corresponds to the {m,n} syntax, and does not include the ?, * or +
/// operators.
///
/// This assumes that the parser is currently positioned at the opening `{`
/// and advances the parser to the first character after the operator.
/// (Note that the operator may include a single additional `?`, which
/// makes the operator ungreedy.)
///
/// The caller should include the concatenation that is being built. The
/// concatenation returned includes the repetition operator applied to the
/// last expression in the given concatenation.
fn ParserI::parse_counted_repetition(
  self : ParserI,
  concat : Concat,
) -> Concat raise AstError {
  guard! self.char() == '{'
  let start = self.pos()
  let ast = match concat.asts.pop() {
    Some(ast) => ast
    None => raise self.error(self.span(), RepetitionMissing)
  }
  match ast {
    Empty(_) | Flags(_) => raise self.error(self.span(), RepetitionMissing)
    _ => ()
  }
  if !self.bump_and_bump_space() {
    raise self.error(Span::new(start, self.pos()), RepetitionCountUnclosed)
  }
  let count_start = specialize_err(
    Ok(self.parse_decimal()) catch {
      e => Err(e)
    },
    DecimalEmpty,
    RepetitionCountDecimalEmpty,
  )
  if self.is_eof() {
    raise self.error(Span::new(start, self.pos()), RepetitionCountUnclosed)
  }
  let range = if self.char() == ',' {
    if !self.bump_and_bump_space() {
      raise self.error(Span::new(start, self.pos()), RepetitionCountUnclosed)
    }
    if self.char() != '}' {
      let count_start = match count_start {
        Ok(c) => c
        Err(err) if err.kind() == RepetitionCountDecimalEmpty =>
          if self.parser.empty_min_range {
            0U
          } else {
            raise err
          }
        Err(err) => raise err
      }
      let count_end = specialize_err(
        Ok(self.parse_decimal()) catch {
          e => Err(e)
        },
        DecimalEmpty,
        RepetitionCountDecimalEmpty,
      ).unwrap_or_error()
      RepetitionRange::Bounded(count_start, count_end)
    } else {
      RepetitionRange::AtLeast(count_start.unwrap_or_error())
    }
  } else {
    RepetitionRange::Exactly(count_start.unwrap_or_error())
  }
  if self.is_eof() || self.char() != '}' {
    raise self.error(Span::new(start, self.pos()), RepetitionCountUnclosed)
  }
  let mut greedy = true
  if self.bump_and_bump_space() && self.char() == '?' {
    greedy = false
    ignore(self.bump())
  }
  let op_span = Span::new(start, self.pos())
  if !range.is_valid() {
    raise self.error(op_span, RepetitionCountInvalid)
  }
  concat.asts.push(
    Repetition({
      span: ast.span().with_end(self.pos()),
      op: { span: op_span, kind: Range(range), },
      greedy,
      ast,
    }),
  )
  concat
}

///|
/// Parse a group (which contains a sub-expression) or a set of flags.
///
/// If a group was found, then it is returned with an empty AST. If a set
/// of flags is found, then that set is returned.
///
/// The parser should be positioned at the opening parenthesis.
///
/// This advances the parser to the character before the start of the
/// sub-expression (in the case of a group) or to the closing parenthesis
/// immediately following the set of flags.
///
/// # Errors
///
/// If flags are given and incorrectly specified, then a corresponding
/// error is returned.
///
/// If a capture name is given and it is incorrectly specified, then a
/// corresponding error is returned.
fn ParserI::parse_group(
  self : ParserI,
) -> Either[SetFlags, Group] raise AstError {
  guard! self.char() == '('
  let open_span = self.span_char()
  ignore(self.bump())
  self.bump_space()
  if self.is_lookaround_prefix() {
    raise self.error(
      Span::new(open_span.start, self.span().end),
      UnsupportedLookAround,
    )
  }
  let inner_span = self.span()
  let mut starts_with_p = true
  if self.bump_if("?P<") ||
    ({
      starts_with_p = false
      self.bump_if("?<")
    }) {
    let capture_index = self.next_capture_index(open_span)
    let name = self.parse_capture_name(capture_index)
    Right({
      span: open_span,
      kind: CaptureName(starts_with_p~, name~),
      ast: Empty(self.span()),
    })
  } else if self.bump_if("?") {
    if self.is_eof() {
      raise self.error(open_span, GroupUnclosed)
    }
    let flags = self.parse_flags()
    let char_end = self.char()
    ignore(self.bump())
    if char_end == ')' {
      // We don't allow empty flags, e.g., `(?)`. We instead
      // interpret it as a repetition operator missing its argument.
      if flags.items.is_empty() {
        raise self.error(inner_span, RepetitionMissing)
      }
      Left({ span: { ..open_span, end: self.pos(), }, flags, })
    } else {
      guard! char_end == ':'
      Right({
        span: open_span,
        kind: NonCapturing(flags),
        ast: Empty(self.span()),
      })
    }
  } else {
    let capture_index = self.next_capture_index(open_span)
    Right({
      span: open_span,
      kind: CaptureIndex(capture_index),
      ast: Empty(self.span()),
    })
  }
}

///|
/// Parses a capture group name. Assumes that the parser is positioned at
/// the first character in the name following the opening `<` (and may
/// possibly be EOF). This advances the parser to the first character
/// following the closing `>`.
///
/// The caller must provide the capture index of the group for this name.
fn ParserI::parse_capture_name(
  self : ParserI,
  capture_index : UInt32,
) -> CaptureName raise AstError {
  if self.is_eof() {
    raise self.error(self.span(), GroupNameUnexpectedEof)
  }
  let start = self.pos()
  while true {
    if self.char() == '>' {
      break
    }
    if !is_capture_char(self.char(), self.pos() == start) {
      raise self.error(self.span_char(), GroupNameInvalid)
    }
    if !self.bump() {
      break
    }
  }
  let end = self.pos()
  if self.is_eof() {
    raise self.error(self.span(), GroupNameUnexpectedEof)
  }
  guard! self.char() == '>'
  ignore(self.bump())
  let name = self.slice(start.offset, end.offset)
  if name.is_empty() {
    raise self.error(Span::new(start, start), GroupNameEmpty)
  }
  let capname = { span: Span::new(start, end), name, index: capture_index, }
  self.add_capture_name(capname)
  capname
}

///|
/// Parse a sequence of flags starting at the current character.
///
/// This advances the parser to the character immediately following the
/// flags, which is guaranteed to be either `:` or `)`.
///
/// # Errors
///
/// If any flags are duplicated, then an error is returned.
///
/// If the negation operator is used more than once, then an error is
/// returned.
///
/// If no flags could be found or if the negation operation is not followed
/// by any flags, then an error is returned.
fn ParserI::parse_flags(self : ParserI) -> Flags raise AstError {
  let flags : Flags = { span: self.span(), items: [], }
  let mut last_was_negation = None
  while self.char() != ':' && self.char() != ')' {
    if self.char() == '-' {
      last_was_negation = Some(self.span_char())
      let item : FlagsItem = { span: self.span_char(), kind: Negation, }
      if flags.add_item(item) is Some(i) {
        raise self.error(
          self.span_char(),
          FlagRepeatedNegation(original=flags.items[i].span),
        )
      }
    } else {
      last_was_negation = None
      let item : FlagsItem = {
        span: self.span_char(),
        kind: Flag(self.parse_flag()),
      }
      if flags.add_item(item) is Some(i) {
        raise self.error(
          self.span_char(),
          FlagDuplicate(original=flags.items[i].span),
        )
      }
    }
    if !self.bump() {
      raise self.error(self.span(), FlagUnexpectedEof)
    }
  }
  if last_was_negation is Some(span) {
    raise self.error(span, FlagDanglingNegation)
  }
  flags.span = { ..flags.span, end: self.pos(), }
  flags
}

///|
/// Parse the current character as a flag. Do not advance the parser.
///
/// # Errors
///
/// If the flag is not recognized, then an error is returned.
fn ParserI::parse_flag(self : ParserI) -> Flag raise AstError {
  match self.char() {
    'i' => CaseInsensitive
    'm' => MultiLine
    's' => DotMatchesNewLine
    'U' => SwapGreed
    'u' => Unicode
    'R' => CRLF
    'x' => IgnoreWhitespace
    _ => raise self.error(self.span_char(), FlagUnrecognized)
  }
}

///|
/// Parse a primitive AST. e.g., A literal, non-set character class or
/// assertion.
///
/// This assumes that the parser expects a primitive at the current
/// location. i.e., All other non-primitive cases have been handled.
/// For example, if the parser's position is at `|`, then `|` will be
/// treated as a literal (e.g., inside a character class).
///
/// This advances the parser to the first character immediately following
/// the primitive.
fn ParserI::parse_primitive(self : ParserI) -> Primitive raise AstError {
  match self.char() {
    '\\' => self.parse_escape()
    '.' => {
      let ast = Primitive::Dot(self.span_char())
      ignore(self.bump())
      ast
    }
    '^' => {
      let ast = Primitive::Assertion({
        span: self.span_char(),
        kind: StartLine,
      })
      ignore(self.bump())
      ast
    }
    '$' => {
      let ast = Primitive::Assertion({ span: self.span_char(), kind: EndLine, })
      ignore(self.bump())
      ast
    }
    c => {
      let ast = Primitive::Literal({
        span: self.span_char(),
        kind: Verbatim,
        c,
      })
      ignore(self.bump())
      ast
    }
  }
}

///|
/// Parse an escape sequence as a primitive AST.
///
/// This assumes the parser is positioned at the start of the escape
/// sequence, i.e., `\`. It advances the parser to the first position
/// immediately following the escape sequence.
fn ParserI::parse_escape(self : ParserI) -> Primitive raise AstError {
  guard! self.char() == '\\'
  let start = self.pos()
  if !self.bump() {
    raise self.error(Span::new(start, self.pos()), EscapeUnexpectedEof)
  }
  let c = self.char()
  // Put some of the more complicated routines into helpers.
  match c {
    '0'..<='7' => {
      if !self.parser.octal {
        raise self.error(
          Span::new(start, self.span_char().end),
          UnsupportedBackreference,
        )
      }
      let lit = self.parse_octal()
      lit.span = { ..lit.span, start, }
      return Primitive::Literal(lit)
    }
    '8'..<='9' if !self.parser.octal =>
      raise self.error(
        Span::new(start, self.span_char().end),
        UnsupportedBackreference,
      )
    'x' | 'u' | 'U' => {
      let lit = self.parse_hex()
      lit.span = { ..lit.span, start, }
      return Primitive::Literal(lit)
    }
    'p' | 'P' => {
      let cls = self.parse_unicode_class()
      cls.span = { ..cls.span, start, }
      return Primitive::Unicode(cls)
    }
    'd' | 's' | 'w' | 'D' | 'S' | 'W' => {
      let cls = self.parse_perl_class()
      cls.span = { ..cls.span, start, }
      return Primitive::Perl(cls)
    }
    _ => ()
  }

  // Handle all of the one letter sequences inline.
  ignore(self.bump())
  let span = Span::new(start, self.pos())
  if is_meta_character(c) {
    return Primitive::Literal({ span, kind: Meta, c, })
  }
  if is_escapeable_character(c) {
    return Primitive::Literal({ span, kind: Superfluous, c, })
  }
  let special = (kind, c) => {
    Primitive::Literal({ span, kind: Special(kind), c, })
  }
  match c {
    'a' => special(Bell, '\u{07}')
    'f' => special(FormFeed, '\u{0C}')
    't' => special(Tab, '\t')
    'n' => special(LineFeed, '\n')
    'r' => special(CarriageReturn, '\r')
    'v' => special(VerticalTab, '\u{0B}')
    'A' => Primitive::Assertion({ span, kind: StartText, })
    'z' => Primitive::Assertion({ span, kind: EndText, })
    'b' => {
      let wb : Assertion = { span, kind: WordBoundary, }
      // After a \b, we "try" to parse things like \b{start} for
      // special word boundary assertions.
      if !self.is_eof() && self.char() == '{' {
        if self.maybe_parse_special_word_boundary(start) is Some(kind) {
          wb.kind = kind
          wb.span = { ..wb.span, end: self.pos(), }
        }
      }
      Primitive::Assertion(wb)
    }
    'B' => Primitive::Assertion({ span, kind: NotWordBoundary, })
    '<' => Primitive::Assertion({ span, kind: WordBoundaryStartAngle, })
    '>' => Primitive::Assertion({ span, kind: WordBoundaryEndAngle, })
    _ => raise self.error(span, EscapeUnrecognized)
  }
}

///|
/// Attempt to parse a specialty word boundary. That is, `\b{start}`,
/// `\b{end}`, `\b{start-half}` or `\b{end-half}`.
///
/// This is similar to `maybe_parse_ascii_class` in that, in most cases,
/// if it fails it will just return `None` with no error. This is done
/// because `\b{5}` is a valid expression and we want to let that be parsed
/// by the existing counted repetition parsing code.
///
/// Unlike `maybe_parse_ascii_class` though, this can return an error.
/// Namely, if we definitely know it isn't a counted repetition, then we
/// return an error specific to the specialty word boundaries.
///
/// This assumes the parser is positioned at a `{` immediately following
/// a `\b`. When `None` is returned, the parser is returned to the position
/// at which it started: pointing at a `{`.
///
/// The position given should correspond to the start of the `\b`.
fn ParserI::maybe_parse_special_word_boundary(
  self : ParserI,
  wb_start : Position,
) -> AssertionKind? raise AstError {
  guard! self.char() == '{'
  let is_valid_char = (c : Char) => c is ('A'..<='Z' | 'a'..<='z' | '-')
  let start = self.pos()
  if !self.bump_and_bump_space() {
    raise self.error(
      Span::new(wb_start, self.pos()),
      SpecialWordOrRepetitionUnexpectedEof,
    )
  }
  let start_contents = self.pos()
  // This is one of the critical bits: if the first non-whitespace
  // character isn't in [-A-Za-z] (i.e., this can't be a special word
  // boundary), then we bail and let the counted repetition parser deal
  // with this.
  if !is_valid_char(self.char()) {
    self.parser.pos = start
    return None
  }

  // Now collect up our chars until we see a '}'.
  let scratch = StringBuilder()
  while !self.is_eof() && is_valid_char(self.char()) {
    scratch.write_char(self.char())
    ignore(self.bump_and_bump_space())
  }
  if self.is_eof() || self.char() != '}' {
    raise self.error(Span::new(start, self.pos()), SpecialWordBoundaryUnclosed)
  }
  let end = self.pos()
  ignore(self.bump())
  let kind : AssertionKind = match scratch.to_string() {
    "start" => WordBoundaryStart
    "end" => WordBoundaryEnd
    "start-half" => WordBoundaryStartHalf
    "end-half" => WordBoundaryEndHalf
    _ =>
      raise self.error(
        Span::new(start_contents, end),
        SpecialWordBoundaryUnrecognized,
      )
  }
  Some(kind)
}

///|
/// Parse an octal representation of a Unicode codepoint up to 3 digits
/// long. This expects the parser to be positioned at the first octal
/// digit and advances the parser to the first character immediately
/// following the octal number. This also assumes that parsing octal
/// escapes is enabled.
///
/// Assuming the preconditions are met, this routine can never fail.
fn ParserI::parse_octal(self : ParserI) -> Literal {
  guard! self.parser.octal
  guard! '0' <= self.char() && self.char() <= '7'
  let start = self.pos()
  // Parse up to two more digits.
  while self.bump() &&
        '0' <= self.char() &&
        self.char() <= '7' &&
        self.pos().offset - start.offset <= 2 {

  }
  let end = self.pos()
  let octal = self.slice(start.offset, end.offset)
  // Parsing the octal should never fail since the above guarantees a
  // valid number.
  let mut codepoint = 0
  for d in octal {
    codepoint = codepoint * 8 + (d.to_int() - '0'.to_int())
  }
  // The max value for 3 digit octal is 0777 = 511 and [0, 511] has no
  // invalid Unicode scalar values.
  let c = codepoint.to_char().unwrap()
  { span: Span::new(start, end), kind: Octal, c, }
}

///|
/// Parse a hex representation of a Unicode codepoint. This handles both
/// hex notations, i.e., `\xFF` and `\x{FFFF}`. This expects the parser to
/// be positioned at the `x`, `u` or `U` prefix. The parser is advanced to
/// the first character immediately following the hexadecimal literal.
fn ParserI::parse_hex(self : ParserI) -> Literal raise AstError {
  guard! self.char() == 'x' || self.char() == 'u' || self.char() == 'U'
  let hex_kind : HexLiteralKind = match self.char() {
    'x' => X
    'u' => UnicodeShort
    _ => UnicodeLong
  }
  if !self.bump_and_bump_space() {
    raise self.error(self.span(), EscapeUnexpectedEof)
  }
  if self.char() == '{' {
    self.parse_hex_brace(hex_kind)
  } else {
    self.parse_hex_digits(hex_kind)
  }
}

///|
/// `u32::from_str_radix(hex, 16).ok().and_then(char::from_u32)`.
fn hex_to_char(hex : String) -> Char? {
  let mut value = 0L
  for c in hex {
    let d = if c >= '0' && c <= '9' {
      c.to_int() - '0'.to_int()
    } else if c >= 'a' && c <= 'f' {
      c.to_int() - 'a'.to_int() + 10
    } else {
      c.to_int() - 'A'.to_int() + 10
    }
    value = value * 16L + d.to_int64()
    if value > 0xFFFFFFFFL {
      return None
    }
  }
  if value > 0x10FFFFL {
    return None
  }
  value.to_int().to_char()
}

///|
/// Parse an N-digit hex representation of a Unicode codepoint. This
/// expects the parser to be positioned at the first digit and will advance
/// the parser to the first character immediately following the escape
/// sequence.
///
/// The number of digits given must be 2 (for `\xNN`), 4 (for `\uNNNN`)
/// or 8 (for `\UNNNNNNNN`).
fn ParserI::parse_hex_digits(
  self : ParserI,
  kind : HexLiteralKind,
) -> Literal raise AstError {
  let scratch = StringBuilder()
  let start = self.pos()
  for i in 0.. 0 && !self.bump_and_bump_space() {
      raise self.error(self.span(), EscapeUnexpectedEof)
    }
    if !is_hex(self.char()) {
      raise self.error(self.span_char(), EscapeHexInvalidDigit)
    }
    scratch.write_char(self.char())
  }
  // The final bump just moves the parser past the literal, which may
  // be EOF.
  ignore(self.bump_and_bump_space())
  let end = self.pos()
  match hex_to_char(scratch.to_string()) {
    None => raise self.error(Span::new(start, end), EscapeHexInvalid)
    Some(c) => { span: Span::new(start, end), kind: HexFixed(kind), c, }
  }
}

///|
/// Parse a hex representation of any Unicode scalar value. This expects
/// the parser to be positioned at the opening brace `{` and will advance
/// the parser to the first character following the closing brace `}`.
fn ParserI::parse_hex_brace(
  self : ParserI,
  kind : HexLiteralKind,
) -> Literal raise AstError {
  let scratch = StringBuilder()
  let brace_pos = self.pos()
  let start = self.span_char().end
  while self.bump_and_bump_space() && self.char() != '}' {
    if !is_hex(self.char()) {
      raise self.error(self.span_char(), EscapeHexInvalidDigit)
    }
    scratch.write_char(self.char())
  }
  if self.is_eof() {
    raise self.error(Span::new(brace_pos, self.pos()), EscapeUnexpectedEof)
  }
  let end = self.pos()
  let hex = scratch.to_string()
  guard! self.char() == '}'
  ignore(self.bump_and_bump_space())
  if hex.is_empty() {
    raise self.error(Span::new(brace_pos, self.pos()), EscapeHexEmpty)
  }
  match hex_to_char(hex) {
    None => raise self.error(Span::new(start, end), EscapeHexInvalid)
    Some(c) => { span: Span::new(start, self.pos()), kind: HexBrace(kind), c, }
  }
}

///|
/// Parse a decimal number into a u32 while trimming leading and trailing
/// whitespace.
///
/// This expects the parser to be positioned at the first position where
/// a decimal digit could occur. This will advance the parser to the byte
/// immediately following the last contiguous decimal digit.
///
/// If no decimal digit could be found or if there was a problem parsing
/// the complete set of digits into a u32, then an error is returned.
fn ParserI::parse_decimal(self : ParserI) -> UInt32 raise AstError {
  let scratch = StringBuilder()
  while !self.is_eof() && is_whitespace(self.char()) {
    ignore(self.bump())
  }
  let start = self.pos()
  while !self.is_eof() && '0' <= self.char() && self.char() <= '9' {
    scratch.write_char(self.char())
    ignore(self.bump_and_bump_space())
  }
  let span = Span::new(start, self.pos())
  while !self.is_eof() && is_whitespace(self.char()) {
    ignore(self.bump_and_bump_space())
  }
  let digits = scratch.to_string()
  if digits.is_empty() {
    raise self.error(span, DecimalEmpty)
  }
  let mut value = 0L
  for d in digits {
    value = value * 10L + (d.to_int() - '0'.to_int()).to_int64()
    if value > 0xFFFFFFFFL {
      raise self.error(span, DecimalInvalid)
    }
  }
  value.to_int().reinterpret_as_uint()
}

///|
/// Parse a standard character class consisting primarily of characters or
/// character ranges, but can also contain nested character classes of
/// any type (sans `.`).
///
/// This assumes the parser is positioned at the opening `[`. If parsing
/// is successful, then the parser is advanced to the position immediately
/// following the closing `]`.
fn ParserI::parse_set_class(self : ParserI) -> ClassBracketed raise AstError {
  guard! self.char() == '['
  let mut union : ClassSetUnion = { span: self.span(), items: [], }
  while true {
    self.bump_space()
    if self.is_eof() {
      raise self.unclosed_class_error()
    }
    match self.char() {
      '[' => {
        // If we've already parsed the opening bracket, then
        // attempt to treat this as the beginning of an ASCII
        // class. If ASCII class parsing fails, then the parser
        // backs up to `[`.
        if !self.parser.stack_class.is_empty() {
          if self.maybe_parse_ascii_class() is Some(cls) {
            union.push(Ascii(cls))
            continue
          }
        }
        union = self.push_class_open(union)
      }
      ']' =>
        match self.pop_class(union) {
          Left(nested_union) => union = nested_union
          Right(class) => return class
        }
      '&' if self.peek() == Some('&') => {
        guard! self.bump_if("&&")
        union = self.push_class_op(Intersection, union)
      }
      '-' if self.peek() == Some('-') => {
        guard! self.bump_if("--")
        union = self.push_class_op(Difference, union)
      }
      '~' if self.peek() == Some('~') => {
        guard! self.bump_if("~~")
        union = self.push_class_op(SymmetricDifference, union)
      }
      _ => union.push(self.parse_set_class_range())
    }
  }
  abort("unreachable")
}

///|
/// Parse a single primitive item in a character class set. The item to
/// be parsed can either be one of a simple literal character, a range
/// between two simple literal characters or a "primitive" character
/// class like \w or \p{Greek}.
///
/// If an invalid escape is found, or if a character class is found where
/// a simple literal is expected (e.g., in a range), then an error is
/// returned.
fn ParserI::parse_set_class_range(
  self : ParserI,
) -> ClassSetItem raise AstError {
  let prim1 = self.parse_set_class_item()
  self.bump_space()
  if self.is_eof() {
    raise self.unclosed_class_error()
  }
  // If the next char isn't a `-`, then we don't have a range.
  // There are two exceptions. If the char after a `-` is a `]`, then
  // `-` is interpreted as a literal `-`. Alternatively, if the char
  // after a `-` is a `-`, then `--` corresponds to a "difference"
  // operation.
  if self.char() != '-' ||
    self.peek_space() == Some(']') ||
    self.peek_space() == Some('-') {
    return prim1.into_class_set_item(self)
  }
  // OK, now we're parsing a range, so bump past the `-` and parse the
  // second half of the range.
  if !self.bump_and_bump_space() {
    raise self.unclosed_class_error()
  }
  let prim2 = self.parse_set_class_item()
  let range : ClassSetRange = {
    span: Span::new(prim1.span().start, prim2.span().end),
    start: prim1.into_class_literal(self),
    end: prim2.into_class_literal(self),
  }
  if !range.is_valid() {
    raise self.error(range.span, ClassRangeInvalid)
  }
  Range(range)
}

///|
/// Parse a single item in a character class as a primitive, where the
/// primitive either consists of a verbatim literal or a single escape
/// sequence.
///
/// This assumes the parser is positioned at the beginning of a primitive,
/// and advances the parser to the first position after the primitive if
/// successful.
///
/// Note that it is the caller's responsibility to report an error if an
/// illegal primitive was parsed.
fn ParserI::parse_set_class_item(self : ParserI) -> Primitive raise AstError {
  if self.char() == '\\' {
    self.parse_escape()
  } else {
    let x = Primitive::Literal({
      span: self.span_char(),
      kind: Verbatim,
      c: self.char(),
    })
    ignore(self.bump())
    x
  }
}

///|
/// Parses the opening of a character class set. This includes the opening
/// bracket along with `^` if present to indicate negation. This also
/// starts parsing the opening set of unioned items if applicable, since
/// there are special rules applied to certain characters in the opening
/// of a character class. For example, `[^]]` is the class of all
/// characters not equal to `]`. (`]` would need to be escaped in any other
/// position.) Similarly for `-`.
///
/// In all cases, the op inside the returned `ast::ClassBracketed` is an
/// empty union. This empty union should be replaced with the actual item
/// when it is popped from the parser's stack.
///
/// This assumes the parser is positioned at the opening `[` and advances
/// the parser to the first non-special byte of the character class.
///
/// An error is returned if EOF is found.
fn ParserI::parse_set_class_open(
  self : ParserI,
) -> (ClassBracketed, ClassSetUnion) raise AstError {
  guard! self.char() == '['
  let start = self.pos()
  if !self.bump_and_bump_space() {
    raise self.error(Span::new(start, self.pos()), ClassUnclosed)
  }
  let negated = if self.char() != '^' {
    false
  } else {
    if !self.bump_and_bump_space() {
      raise self.error(Span::new(start, self.pos()), ClassUnclosed)
    }
    true
  }
  // Accept any number of `-` as literal `-`.
  let union : ClassSetUnion = { span: self.span(), items: [], }
  while self.char() == '-' {
    union.push(Literal({ span: self.span_char(), kind: Verbatim, c: '-', }))
    if !self.bump_and_bump_space() {
      raise self.error(Span::new(start, start), ClassUnclosed)
    }
  }
  // If `]` is the *first* char in a set, then interpret it as a literal
  // `]`. That is, an empty class is impossible to write.
  if union.items.is_empty() && self.char() == ']' {
    union.push(Literal({ span: self.span_char(), kind: Verbatim, c: ']', }))
    if !self.bump_and_bump_space() {
      raise self.error(Span::new(start, self.pos()), ClassUnclosed)
    }
  }
  let set : ClassBracketed = {
    span: Span::new(start, self.pos()),
    negated,
    kind: ClassSet::union({
      span: Span::new(union.span.start, union.span.start),
      items: [],
    }),
  }
  (set, union)
}

///|
/// Attempt to parse an ASCII character class, e.g., `[:alnum:]`.
///
/// This assumes the parser is positioned at the opening `[`.
///
/// If no valid ASCII character class could be found, then this does not
/// advance the parser and `None` is returned. Otherwise, the parser is
/// advanced to the first byte following the closing `]` and the
/// corresponding ASCII class is returned.
fn ParserI::maybe_parse_ascii_class(self : ParserI) -> ClassAscii? {
  // ASCII character classes are interesting from a parsing perspective
  // because parsing cannot fail with any interesting error. For example,
  // in order to use an ASCII character class, it must be enclosed in
  // double brackets, e.g., `[[:alnum:]]`. Alternatively, you might think
  // of it as "ASCII character classes have the syntax `[:NAME:]` which
  // can only appear within character brackets." This means that things
  // like `[[:lower:]A]` are legal constructs.
  //
  // However, if one types an incorrect ASCII character class, e.g.,
  // `[[:loower:]]`, then we treat that as a normal nested character
  // class containing the characters `:elorw`. One might argue that we
  // should return an error instead since the repeated colons give away
  // the intent to write an ASCII class. But what if the user typed
  // `[[:lower]]` instead? How can we tell that was intended to be an
  // ASCII class and not just a normal nested class?
  //
  // Reasonable people can probably disagree over this, but for better
  // or worse, we implement semantics that never fails at the expense
  // of better failure modes.
  guard! self.char() == '['
  // If parsing fails, then we back up the parser to this starting point.
  let start = self.pos()
  let mut negated = false
  if !self.bump() || self.char() != ':' {
    self.parser.pos = start
    return None
  }
  if !self.bump() {
    self.parser.pos = start
    return None
  }
  if self.char() == '^' {
    negated = true
    if !self.bump() {
      self.parser.pos = start
      return None
    }
  }
  let name_start = self.offset()
  while self.char() != ':' && self.bump() {

  }
  if self.is_eof() {
    self.parser.pos = start
    return None
  }
  let name = self.slice(name_start, self.offset())
  if !self.bump_if(":]") {
    self.parser.pos = start
    return None
  }
  let kind = match ClassAsciiKind::from_name(name) {
    Some(kind) => kind
    None => {
      self.parser.pos = start
      return None
    }
  }
  Some({ span: Span::new(start, self.pos()), kind, negated, })
}

///|
/// Parse a Unicode class in either the single character notation, `\pN`
/// or the multi-character bracketed notation, `\p{Greek}`. This assumes
/// the parser is positioned at the `p` (or `P` for negation) and will
/// advance the parser to the character immediately following the class.
///
/// Note that this does not check whether the class name is valid or not.
fn ParserI::parse_unicode_class(self : ParserI) -> ClassUnicode raise AstError {
  guard! self.char() == 'p' || self.char() == 'P'
  let scratch = StringBuilder()
  let negated = self.char() == 'P'
  if !self.bump_and_bump_space() {
    raise self.error(self.span(), EscapeUnexpectedEof)
  }
  let (start, kind) = if self.char() == '{' {
    let start = self.span_char().end
    while self.bump_and_bump_space() && self.char() != '}' {
      scratch.write_char(self.char())
    }
    if self.is_eof() {
      raise self.error(self.span(), EscapeUnexpectedEof)
    }
    guard! self.char() == '}'
    ignore(self.bump())
    let name = scratch.to_string()
    if name.find("!=") is Some(i) {
      (
        start,
        ClassUnicodeKind::NamedValue(
          op=NotEqual,
          name=name.view(end_offset=i).to_owned(),
          value=name.view(start_offset=i + 2).to_owned(),
        ),
      )
    } else if name.find(":") is Some(i) {
      (
        start,
        ClassUnicodeKind::NamedValue(
          op=Colon,
          name=name.view(end_offset=i).to_owned(),
          value=name.view(start_offset=i + 1).to_owned(),
        ),
      )
    } else if name.find("=") is Some(i) {
      (
        start,
        ClassUnicodeKind::NamedValue(
          op=Equal,
          name=name.view(end_offset=i).to_owned(),
          value=name.view(start_offset=i + 1).to_owned(),
        ),
      )
    } else {
      (start, ClassUnicodeKind::Named(name))
    }
  } else {
    let start = self.pos()
    let c = self.char()
    if c == '\\' {
      raise self.error(self.span_char(), UnicodeClassInvalid)
    }
    ignore(self.bump_and_bump_space())
    let kind = ClassUnicodeKind::OneLetter(c)
    (start, kind)
  }
  { span: Span::new(start, self.pos()), negated, kind, }
}

///|
/// Parse a Perl character class, e.g., `\d` or `\W`. This assumes the
/// parser is currently at a valid character class name and will be
/// advanced to the character immediately following the class.
fn ParserI::parse_perl_class(self : ParserI) -> ClassPerl {
  let c = self.char()
  let span = self.span_char()
  ignore(self.bump())
  let (negated, kind) : (Bool, ClassPerlKind) = match c {
    'd' => (false, Digit)
    'D' => (true, Digit)
    's' => (false, Space)
    'S' => (true, Space)
    'w' => (false, Word)
    'W' => (true, Word)
    c => abort("expected valid Perl class but got '\{c}'")
  }
  { span, kind, negated, }
}

///|
/// A type that traverses a fully parsed Ast and checks whether its depth
/// exceeds the specified nesting limit. If it does, then an error is returned.
priv struct NestLimiter {
  /// The parser that is checking the nest limit.
  p : ParserI
  /// The current depth while walking an Ast.
  mut depth : UInt32
}

///|
fn NestLimiter::new(p : ParserI) -> NestLimiter {
  { p, depth: 0, }
}

///|
fn NestLimiter::check(self : NestLimiter, ast : Ast) -> Unit raise AstError {
  visit(ast, self) catch {
    AstError(_) as e => raise e
    _ => abort("unreachable")
  }
}

///|
fn NestLimiter::increment_depth(
  self : NestLimiter,
  span : Span,
) -> Unit raise AstError {
  if self.depth == 4294967295U {
    raise self.p.error(span, NestLimitExceeded(4294967295U))
  }
  let new = self.depth + 1
  let limit = self.p.parser.nest_limit
  if new > limit {
    raise self.p.error(span, NestLimitExceeded(limit))
  }
  self.depth = new
}

///|
fn NestLimiter::decrement_depth(self : NestLimiter) -> Unit {
  // Assuming the correctness of the visitor, this should never drop
  // below 0.
  guard! self.depth > 0
  self.depth = self.depth - 1
}

///|
impl Visitor for NestLimiter with fn visit_pre(self, ast) {
  let span = match ast {
    Empty(_)
    | Flags(_)
    | Literal(_)
    | Dot(_)
    | Assertion(_)
    | ClassUnicode(_)
    | ClassPerl(_) =>
      // These are all base cases, so we don't increment depth.
      return
    ClassBracketed(x) => x.span
    Repetition(x) => x.span
    Group(x) => x.span
    Alternation(x) => x.span
    Concat(x) => x.span
  }
  self.increment_depth(span)
}

///|
impl Visitor for NestLimiter with fn visit_post(self, ast) {
  match ast {
    Empty(_)
    | Flags(_)
    | Literal(_)
    | Dot(_)
    | Assertion(_)
    | ClassUnicode(_)
    | ClassPerl(_) =>
      // These are all base cases, so we don't decrement depth.
      ()
    ClassBracketed(_) | Repetition(_) | Group(_) | Alternation(_) | Concat(_) =>
      self.decrement_depth()
  }
}

///|
impl Visitor for NestLimiter with fn visit_class_set_item_pre(self, ast) {
  let span = match ast {
    Empty(_) | Literal(_) | Range(_) | Ascii(_) | Unicode(_) | Perl(_) =>
      // These are all base cases, so we don't increment depth.
      return
    Bracketed(x) => x.span
    Union(x) => x.span
  }
  self.increment_depth(span)
}

///|
impl Visitor for NestLimiter with fn visit_class_set_item_post(self, ast) {
  match ast {
    Empty(_) | Literal(_) | Range(_) | Ascii(_) | Unicode(_) | Perl(_) =>
      // These are all base cases, so we don't decrement depth.
      ()
    Bracketed(_) | Union(_) => self.decrement_depth()
  }
}

///|
impl Visitor for NestLimiter with fn visit_class_set_binary_op_pre(self, ast) {
  self.increment_depth(ast.span)
}

///|
impl Visitor for NestLimiter with fn visit_class_set_binary_op_post(self, _ast) {
  self.decrement_depth()
}

///|
/// When the result is an error, transforms the ast::ErrorKind from the source
/// Result into another one. This function is used to return clearer error
/// messages when possible.
#warnings("-result_error_return")
fn[T] specialize_err(
  result : Result[T, AstError],
  from : ErrorKind,
  to : ErrorKind,
) -> Result[T, AstError] {
  match result {
    Err(e) =>
      if e.kind() == from {
        Err(AstError(kind=to, pattern=e.pattern(), span=e.span()))
      } else {
        Err(e)
      }
    Ok(_) => result
  }
}