// Port of regex-syntax 0.8.11 src/hir/mod.rs (and the `utf8_decode` helper
// of src/debug.rs).
//
// Defines a high-level intermediate (HIR) representation for regular
// expressions. The smart constructors (`Hir::concat`, `Hir::alternation`,
// `Hir::repetition`, `Hir::class`, ...) simplify exactly like upstream, since
// the shape of the HIR determines the NFA built from it. `usize` lengths are
// `UInt64`, `u32` counts are `UInt`, `char` bounds are `Int` code points. The
// `Drop` impl and `memory_usage` are not needed.

///|
/// An error that can occur while translating an `Ast` to a `Hir`
/// (upstream `hir::Error`).
pub(all) suberror HirError {
  HirError(kind~ : ErrorKind, pattern~ : String, span~ : @ast.Span)
} derive(Eq, Debug)

///|
/// Return the type of this error.
pub fn HirError::kind(self : HirError) -> ErrorKind {
  let HirError(kind~, ..) = self
  kind
}

///|
/// The original pattern string in which this error occurred.
pub fn HirError::pattern(self : HirError) -> String {
  let HirError(pattern~, ..) = self
  pattern
}

///|
/// Return the span at which this error occurred.
pub fn HirError::span(self : HirError) -> @ast.Span {
  let HirError(span~, ..) = self
  span
}

///|
/// The type of an error that occurred while building an `Hir`.
pub(all) enum ErrorKind {
  /// This error occurs when a Unicode feature is used when Unicode
  /// support is disabled. For example `(?-u:\pL)` would trigger this error.
  UnicodeNotAllowed
  /// This error occurs when translating a pattern that could match a byte
  /// sequence that isn't UTF-8 and `utf8` was enabled.
  InvalidUtf8
  /// This error occurs when one uses a non-ASCII byte for a line terminator,
  /// but where Unicode mode is enabled and UTF-8 mode is disabled.
  InvalidLineTerminator
  /// This occurs when an unrecognized Unicode property name could not
  /// be found.
  UnicodePropertyNotFound
  /// This occurs when an unrecognized Unicode property value could not
  /// be found.
  UnicodePropertyValueNotFound
  /// This occurs when a Unicode-aware Perl character class (`\w`, `\s` or
  /// `\d`) could not be found.
  UnicodePerlClassNotFound
  /// This occurs when the Unicode simple case mapping tables are not
  /// available, and the regular expression required Unicode aware case
  /// insensitivity.
  UnicodeCaseUnavailable
} derive(Eq, Debug)

///|
pub impl Show for ErrorKind with fn output(self, f) {
  let msg = match self {
    UnicodeNotAllowed => "Unicode not allowed here"
    InvalidUtf8 => "pattern can match invalid UTF-8"
    InvalidLineTerminator => "invalid line terminator, must be ASCII"
    UnicodePropertyNotFound => "Unicode property not found"
    UnicodePropertyValueNotFound => "Unicode property value not found"
    UnicodePerlClassNotFound =>
      "Unicode-aware Perl class not found (make sure the unicode-perl feature is enabled)"
    UnicodeCaseUnavailable =>
      "Unicode-aware case insensitivity matching is not available (make sure the unicode-case feature is enabled)"
  }
  f.write_string(msg)
}

///|
/// A high-level intermediate representation (HIR) for a regular expression.
///
/// An HIR value is a combination of a [`HirKind`] and a set of [`Properties`].
/// An `HirKind` indicates what kind of regular expression it is (a literal,
/// a repetition, a look-around assertion, etc.), where as a `Properties`
/// describes various facts about the regular expression.
pub struct Hir {
  /// The underlying HIR kind.
  priv kind : HirKind
  /// Analysis info about this HIR, computed bottom-up.
  priv props : Properties
} derive(Eq, Debug)

///|
/// Returns a reference to the underlying HIR kind.
pub fn Hir::kind(self : Hir) -> HirKind {
  self.kind
}

///|
/// Consumes ownership of this HIR expression and returns its underlying
/// `HirKind`.
pub fn Hir::into_kind(self : Hir) -> HirKind {
  self.kind
}

///|
/// Returns the properties computed for this `Hir`.
pub fn Hir::properties(self : Hir) -> Properties {
  self.props
}

///|
/// Splits this HIR into its constituent parts.
fn Hir::into_parts(self : Hir) -> (HirKind, Properties) {
  (self.kind, self.props)
}

///|
/// Returns an empty HIR expression.
///
/// An empty HIR expression always matches, including the empty string.
pub fn Hir::empty() -> Hir {
  let props = Properties::empty()
  { kind: Empty, props, }
}

///|
/// Returns an HIR expression that can never match anything. That is,
/// the size of the set of strings in the language described by the HIR
/// returned is `0`.
pub fn Hir::fail() -> Hir {
  let class = Class::Bytes(ClassBytes::empty())
  let props = Properties::class(class)
  // We can't just call Hir::class here because it defers to Hir::fail
  // in order to canonicalize the Hir value used to represent "cannot
  // match."
  { kind: Class(class), props, }
}

///|
/// Creates a literal HIR expression.
///
/// This accepts anything that can be converted into a `Box<[u8]>`.
///
/// Note that there is no mechanism for storing a `char` or a `Box`
/// in an HIR. Everything is "just bytes." Whether a `Literal` (or
/// any HIR node) matches valid UTF-8 exclusively can be queried via
/// [`Properties::is_utf8`].
pub fn Hir::literal(lit : Bytes) -> Hir {
  let bytes = lit
  if bytes.is_empty() {
    return Hir::empty()
  }
  let lit = Literal::Literal(bytes)
  let props = Properties::literal(lit)
  { kind: Literal(lit), props, }
}

///|
/// Creates a class HIR expression. The class may either be defined over
/// ranges of Unicode codepoints or ranges of raw byte values.
///
/// Note that an empty class is permitted. An empty class is equivalent to
/// `Hir::fail()`.
pub fn Hir::class(class : Class) -> Hir {
  if class.is_empty() {
    return Hir::fail()
  } else if class.literal() is Some(bytes) {
    return Hir::literal(bytes)
  }
  let props = Properties::class(class)
  { kind: Class(class), props, }
}

///|
/// Creates a look-around assertion HIR expression.
pub fn Hir::look(look : Look) -> Hir {
  let props = Properties::look(look)
  { kind: Look(look), props, }
}

///|
/// Creates a repetition HIR expression.
pub fn Hir::repetition(rep : Repetition) -> Hir {
  let mut rep = rep
  // If the sub-expression of a repetition can only match the empty
  // string, then we force its maximum to be at most 1.
  if rep.sub.properties().maximum_len() == Some(0) {
    rep = {
      ..rep,
      min: @cmp.minimum(rep.min, 1),
      max: Some(
        match rep.max {
          Some(n) => @cmp.minimum(n, 1)
          None => 1
        },
      ),
    }
  }
  // The regex 'a{0}' is always equivalent to the empty regex. This is
  // true even when 'a' is an expression that never matches anything
  // (like '\P{any}').
  //
  // Additionally, the regex 'a{1}' is always equivalent to 'a'.
  if rep.min == 0 && rep.max == Some(0) {
    return Hir::empty()
  } else if rep.min == 1 && rep.max == Some(1) {
    return rep.sub
  }
  let props = Properties::repetition(rep)
  { kind: Repetition(rep), props, }
}

///|
/// Creates a capture HIR expression.
///
/// Note that there is no explicit HIR value for a non-capturing group.
/// Since a non-capturing group only exists to override precedence in the
/// concrete syntax and since an HIR already does its own grouping based on
/// what is parsed, there is no need to explicitly represent non-capturing
/// groups in the HIR.
pub fn Hir::capture(capture : Capture) -> Hir {
  let props = Properties::capture(capture)
  { kind: Capture(capture), props, }
}

///|
/// Returns the concatenation of the given expressions.
///
/// This attempts to flatten and simplify the concatenation as appropriate.
pub fn Hir::concat(subs : Array[Hir]) -> Hir {
  // We rebuild the concatenation by simplifying it. Would be nice to do
  // it in place, but that seems a little tricky?
  let new = []
  // This gobbles up any adjacent literals in a concatenation and smushes
  // them together. Basically, when we see a literal, we add its bytes
  // to 'prior_lit', and whenever we see anything else, we first take
  // any bytes in 'prior_lit' and add it to the 'new' concatenation.
  let mut prior_lit : Array[Byte]? = None
  for sub in subs {
    let (kind, props) = sub.into_parts()
    match kind {
      Literal(Literal(bytes)) =>
        match prior_lit {
          Some(prior_bytes) =>
            for b in bytes {
              prior_bytes.push(b)
            }
          None => prior_lit = Some(bytes.to_array())
        }
      // We also flatten concats that are direct children of another
      // concat. We only need to do this one level deep since
      // Hir::concat is the only way to build concatenations, and so
      // flattening happens inductively.
      Concat(subs2) =>
        for sub2 in subs2 {
          let (kind2, props2) = sub2.into_parts()
          match kind2 {
            Literal(Literal(bytes)) =>
              match prior_lit {
                Some(prior_bytes) =>
                  for b in bytes {
                    prior_bytes.push(b)
                  }
                None => prior_lit = Some(bytes.to_array())
              }
            kind2 => {
              if prior_lit is Some(prior_bytes) {
                prior_lit = None
                new.push(Hir::literal(Bytes::from_array(prior_bytes)))
              }
              new.push({ kind: kind2, props: props2, })
            }
          }
        }
      // We can just skip empty HIRs.
      Empty => ()
      kind => {
        if prior_lit is Some(prior_bytes) {
          prior_lit = None
          new.push(Hir::literal(Bytes::from_array(prior_bytes)))
        }
        new.push({ kind, props, })
      }
    }
  }
  if prior_lit is Some(prior_bytes) {
    new.push(Hir::literal(Bytes::from_array(prior_bytes)))
  }
  if new.is_empty() {
    return Hir::empty()
  } else if new.length() == 1 {
    return new.unsafe_pop()
  }
  let props = Properties::concat(new)
  { kind: Concat(new), props, }
}

///|
/// Returns the alternation of the given expressions.
///
/// This flattens and simplifies the alternation as appropriate. This may
/// include factoring out common prefixes or even rewriting the alternation
/// as a character class.
///
/// Note that an empty alternation is equivalent to `Hir::fail()`. (It
/// is not possible for one to write an empty alternation, or even an
/// alternation with a single sub-expression, in the concrete syntax of a
/// regex.)
pub fn Hir::alternation(subs : Array[Hir]) -> Hir {
  // We rebuild the alternation by simplifying it. We proceed similarly
  // as the concatenation case. But in this case, there's no literal
  // simplification happening. We're just flattening alternations.
  let mut new = []
  for sub in subs {
    let (kind, props) = sub.into_parts()
    match kind {
      Alternation(subs2) =>
        for s in subs2 {
          new.push(s)
        }
      kind => new.push({ kind, props, })
    }
  }
  if new.is_empty() {
    return Hir::fail()
  } else if new.length() == 1 {
    return new.unsafe_pop()
  }
  // Now that it's completely flattened, look for the special case of
  // 'char1|char2|...|charN' and collapse that into a class. Note that
  // we look for 'char' first and then bytes. The issue here is that if
  // we find both non-ASCII codepoints and non-ASCII singleton bytes,
  // then it isn't actually possible to smush them into a single class.
  // (Because classes are either "all codepoints" or "all bytes." You
  // can have a class that both matches non-ASCII but valid UTF-8 and
  // invalid UTF-8.) So we look for all chars and then all bytes, and
  // don't handle anything else.
  if singleton_chars(new) is Some(singletons) {
    let it = singletons.map(ch => ClassUnicodeRange::{ start: ch, end: ch, })
    return Hir::class(Unicode(ClassUnicode::new(it)))
  }
  if singleton_bytes(new) is Some(singletons) {
    let it = singletons.map(b => ClassBytesRange::{ start: b, end: b, })
    return Hir::class(Bytes(ClassBytes::new(it)))
  }
  // Similar to singleton chars, we can also look for alternations of
  // classes. Those can be smushed into a single class.
  if class_chars(new) is Some(cls) {
    return Hir::class(cls)
  }
  if class_bytes(new) is Some(cls) {
    return Hir::class(cls)
  }
  // Factor out a common prefix if we can, which might potentially
  // simplify the expression and unlock other optimizations downstream.
  // It also might generally make NFA matching and DFA construction
  // faster by reducing the scope of branching in the regex.
  new = match lift_common_prefix(new) {
    Ok(hir) => return hir
    Err(unchanged) => unchanged
  }
  let props = Properties::alternation(new)
  { kind: Alternation(new), props, }
}

///|
/// Returns an HIR expression for `.`.
pub fn Hir::dot(dot : Dot) -> Hir {
  match dot {
    AnyChar =>
      Hir::class(
        Unicode(ClassUnicode::new([ClassUnicodeRange::new(0, 0x10FFFF)])),
      )
    AnyByte =>
      Hir::class(
        Bytes(ClassBytes::new([ClassBytesRange::new(b'\x00', b'\xFF')])),
      )
    AnyCharExcept(ch) => {
      let cls = ClassUnicode::new([ClassUnicodeRange::new(ch, ch)])
      cls.negate()
      Hir::class(Unicode(cls))
    }
    AnyCharExceptLF =>
      Hir::class(
        Unicode(
          ClassUnicode::new([
            ClassUnicodeRange::new(0, 0x09),
            ClassUnicodeRange::new(0x0B, 0x10FFFF),
          ]),
        ),
      )
    AnyCharExceptCRLF =>
      Hir::class(
        Unicode(
          ClassUnicode::new([
            ClassUnicodeRange::new(0, 0x09),
            ClassUnicodeRange::new(0x0B, 0x0C),
            ClassUnicodeRange::new(0x0E, 0x10FFFF),
          ]),
        ),
      )
    AnyByteExcept(byte) => {
      let cls = ClassBytes::new([ClassBytesRange::new(byte, byte)])
      cls.negate()
      Hir::class(Bytes(cls))
    }
    AnyByteExceptLF =>
      Hir::class(
        Bytes(
          ClassBytes::new([
            ClassBytesRange::new(b'\x00', b'\x09'),
            ClassBytesRange::new(b'\x0B', b'\xFF'),
          ]),
        ),
      )
    AnyByteExceptCRLF =>
      Hir::class(
        Bytes(
          ClassBytes::new([
            ClassBytesRange::new(b'\x00', b'\x09'),
            ClassBytesRange::new(b'\x0B', b'\x0C'),
            ClassBytesRange::new(b'\x0E', b'\xFF'),
          ]),
        ),
      )
  }
}

///|
/// The underlying kind of an arbitrary [`Hir`] expression.
pub(all) enum HirKind {
  /// The empty regular expression, which matches everything, including the
  /// empty string.
  Empty
  /// A literal string that matches exactly these bytes.
  Literal(Literal)
  /// A single character class that matches any of the characters in the
  /// class. A class can either consist of Unicode scalar values as
  /// characters, or it can use bytes.
  Class(Class)
  /// A look-around assertion. A look-around match always has zero length.
  Look(Look)
  /// A repetition operation applied to a sub-expression.
  Repetition(Repetition)
  /// A capturing group, which contains a sub-expression.
  Capture(Capture)
  /// A concatenation of expressions.
  Concat(Array[Hir])
  /// An alternation of expressions.
  Alternation(Array[Hir])
} derive(Eq, Debug)

///|
/// Returns a slice of this kind's sub-expressions, if any.
pub fn HirKind::subs(self : HirKind) -> Array[Hir] {
  match self {
    Empty | Literal(_) | Class(_) | Look(_) => []
    Repetition(rep) => [rep.sub]
    Capture(cap) => [cap.sub]
    Concat(subs) => subs
    Alternation(subs) => subs
  }
}

///|
/// The high-level intermediate representation of a literal.
pub(all) struct Literal(Bytes) derive(Eq, Debug)

///|
/// The high-level intermediate representation of a character class.
pub(all) enum Class {
  /// A set of characters represented by Unicode scalar values.
  Unicode(ClassUnicode)
  /// A set of characters represented by arbitrary bytes (one byte per
  /// character).
  Bytes(ClassBytes)
} derive(Eq, Debug)

///|
/// Apply Unicode simple case folding to this character class, in place.
pub fn Class::case_fold_simple(self : Class) -> Unit {
  match self {
    Unicode(x) => x.case_fold_simple()
    Bytes(x) => x.case_fold_simple()
  }
}

///|
/// Apply Unicode simple case folding to this character class, in place.
pub fn Class::try_case_fold_simple(self : Class) -> Unit raise CaseFoldError {
  match self {
    Unicode(x) => x.try_case_fold_simple()
    Bytes(x) => x.case_fold_simple()
  }
}

///|
/// Negate this character class in place.
pub fn Class::negate(self : Class) -> Unit {
  match self {
    Unicode(x) => x.negate()
    Bytes(x) => x.negate()
  }
}

///|
/// Returns true if and only if this character class will only ever match
/// valid UTF-8.
pub fn Class::is_utf8(self : Class) -> Bool {
  match self {
    Unicode(_) => true
    Bytes(x) => x.is_ascii()
  }
}

///|
/// Returns the length, in bytes, of the smallest string matched by this
/// character class.
pub fn Class::minimum_len(self : Class) -> UInt64? {
  match self {
    Unicode(x) => x.minimum_len()
    Bytes(x) => x.minimum_len()
  }
}

///|
/// Returns the length, in bytes, of the longest string matched by this
/// character class.
pub fn Class::maximum_len(self : Class) -> UInt64? {
  match self {
    Unicode(x) => x.maximum_len()
    Bytes(x) => x.maximum_len()
  }
}

///|
/// Returns true if and only if this character class is empty. That is,
/// it has no elements.
pub fn Class::is_empty(self : Class) -> Bool {
  match self {
    Unicode(x) => x.ranges().is_empty()
    Bytes(x) => x.ranges().is_empty()
  }
}

///|
/// If this class consists of exactly one element (whether a codepoint or a
/// byte), then return it as a literal byte string.
pub fn Class::literal(self : Class) -> Bytes? {
  match self {
    Unicode(x) => x.literal()
    Bytes(x) => x.literal()
  }
}

///|
/// A set of characters represented by Unicode scalar values.
pub struct ClassUnicode {
  priv set : IntervalSet[ClassUnicodeRange]
} derive(Eq, Debug)

///|
/// Create a new class from a sequence of ranges.
///
/// The given ranges do not need to be in any specific order, and ranges
/// may overlap. Ranges will automatically be sorted into a canonical
/// non-overlapping order.
pub fn ClassUnicode::new(ranges : Array[ClassUnicodeRange]) -> ClassUnicode {
  { set: IntervalSet::new(ranges), }
}

///|
/// Create a new class with no ranges.
pub fn ClassUnicode::empty() -> ClassUnicode {
  ClassUnicode::new([])
}

///|
/// A copy of this class (Rust `Clone`).
pub fn ClassUnicode::copy(self : ClassUnicode) -> ClassUnicode {
  { set: self.set.copy(), }
}

///|
/// Add a new range to this set.
pub fn ClassUnicode::push(
  self : ClassUnicode,
  range : ClassUnicodeRange,
) -> Unit {
  self.set.push(range)
}

///|
/// Return an iterator over all ranges in this class.
pub fn ClassUnicode::iter(self : ClassUnicode) -> Iter[ClassUnicodeRange] {
  self.set.iter()
}

///|
/// Return the underlying ranges as a slice.
pub fn ClassUnicode::ranges(
  self : ClassUnicode,
) -> ArrayView[ClassUnicodeRange] {
  self.set.intervals()
}

///|
/// Expand this character class such that it contains all case folded
/// characters, according to Unicode's "simple" mapping.
pub fn ClassUnicode::case_fold_simple(self : ClassUnicode) -> Unit {
  self.set.case_fold_simple() catch {
    _ => abort("unicode-case feature must be enabled")
  }
}

///|
/// Expand this character class such that it contains all case folded
/// characters, according to Unicode's "simple" mapping.
pub fn ClassUnicode::try_case_fold_simple(
  self : ClassUnicode,
) -> Unit raise CaseFoldError {
  self.set.case_fold_simple()
}

///|
/// Negate this character class.
pub fn ClassUnicode::negate(self : ClassUnicode) -> Unit {
  self.set.negate()
}

///|
/// Union this character class with the given character class, in place.
pub fn ClassUnicode::union(self : ClassUnicode, other : ClassUnicode) -> Unit {
  self.set.union(other.set)
}

///|
/// Intersect this character class with the given character class, in
/// place.
pub fn ClassUnicode::intersect(
  self : ClassUnicode,
  other : ClassUnicode,
) -> Unit {
  self.set.intersect(other.set)
}

///|
/// Subtract the given character class from this character class, in place.
pub fn ClassUnicode::difference(
  self : ClassUnicode,
  other : ClassUnicode,
) -> Unit {
  self.set.difference(other.set)
}

///|
/// Compute the symmetric difference of the given character classes, in
/// place.
pub fn ClassUnicode::symmetric_difference(
  self : ClassUnicode,
  other : ClassUnicode,
) -> Unit {
  self.set.symmetric_difference(other.set)
}

///|
/// Returns true if and only if this character class will either match
/// nothing or only ASCII bytes. Stated differently, this returns false
/// if and only if this class contains a non-ASCII codepoint.
pub fn ClassUnicode::is_ascii(self : ClassUnicode) -> Bool {
  match self.set.intervals().last() {
    None => true
    Some(r) => r.end <= 0x7F
  }
}

///|
/// Returns the length, in bytes, of the smallest string matched by this
/// character class.
pub fn ClassUnicode::minimum_len(self : ClassUnicode) -> UInt64? {
  guard self.ranges().get(0) is Some(first) else { return None }
  // Correct because c1 < c2 implies c1.len_utf8() < c2.len_utf8().
  Some(len_utf8(first.start).to_uint64())
}

///|
/// Returns the length, in bytes, of the longest string matched by this
/// character class.
pub fn ClassUnicode::maximum_len(self : ClassUnicode) -> UInt64? {
  guard self.ranges().last() is Some(last) else { return None }
  // Correct because c1 < c2 implies c1.len_utf8() < c2.len_utf8().
  Some(len_utf8(last.end).to_uint64())
}

///|
/// If this class consists of exactly one codepoint, then return its
/// corresponding UTF-8 encoding. Otherwise, return `None`.
pub fn ClassUnicode::literal(self : ClassUnicode) -> Bytes? {
  let rs = self.ranges()
  if rs.length() == 1 && rs[0].start == rs[0].end {
    let out = []
    encode_utf8_into(rs[0].start, out)
    Some(Bytes::from_array(out))
  } else {
    None
  }
}

///|
/// If this class consists of only ASCII ranges, then return its
/// corresponding and equivalent byte class.
pub fn ClassUnicode::to_byte_class(self : ClassUnicode) -> ClassBytes? {
  if !self.is_ascii() {
    return None
  }
  Some(
    ClassBytes::new(
      self
      .ranges()
      .iter()
      .map(r => ClassBytesRange::{
        // Since we are guaranteed that our codepoint range is ASCII, the
        // 'u8::try_from' calls below are guaranteed to be correct.
        start: r.start.to_byte(),
        end: r.end.to_byte(),
      })
      .collect(),
    ),
  )
}

///|
/// A single range of characters represented by Unicode scalar values.
///
/// The range is closed. That is, the start and end of the range are included
/// in the range.
pub(all) struct ClassUnicodeRange {
  start : Int32
  end : Int32
} derive(Eq, Compare, Debug)

///|
pub impl Interval for ClassUnicodeRange with fn lower(self) {
  self.start
}

///|
pub impl Interval for ClassUnicodeRange with fn upper(self) {
  self.end
}

///|
pub impl Interval for ClassUnicodeRange with fn create(lower, upper) {
  if lower <= upper {
    { start: lower, end: upper, }
  } else {
    { start: upper, end: lower, }
  }
}

///|
pub impl Interval for ClassUnicodeRange with fn bound_min_value() {
  0
}

///|
pub impl Interval for ClassUnicodeRange with fn bound_max_value() {
  0x10FFFF
}

///|
pub impl Interval for ClassUnicodeRange with fn bound_increment(c) {
  char_increment(c)
}

///|
pub impl Interval for ClassUnicodeRange with fn bound_decrement(c) {
  char_decrement(c)
}

///|
/// Apply simple case folding to this Unicode scalar value range.
///
/// Additional ranges are appended to the given vector. Canonical ordering
/// is *not* maintained in the given vector.
pub impl Interval for ClassUnicodeRange with fn case_fold_simple(self, ranges) {
  let folder = SimpleCaseFolder::new()
  if !folder.overlaps(self.start, self.end) {
    return
  }
  let (start, end) = (self.start, self.end)
  for cp in start..<=end {
    // `char::from_u32` skips the surrogates.
    if cp >= 0xD800 && cp <= 0xDFFF {
      continue
    }
    for cp_folded in folder.mapping(cp) {
      ranges.push(ClassUnicodeRange::new(cp_folded, cp_folded))
    }
  }
}

///|
/// Create a new Unicode scalar value range for a character class.
///
/// The returned range is always in a canonical form. That is, the range
/// returned always satisfies the invariant that `start <= end`.
pub fn ClassUnicodeRange::new(start : Int32, end : Int32) -> ClassUnicodeRange {
  Interval::create(start, end)
}

///|
/// Return the start of this range.
pub fn ClassUnicodeRange::start(self : ClassUnicodeRange) -> Int32 {
  self.start
}

///|
/// Return the end of this range.
pub fn ClassUnicodeRange::end(self : ClassUnicodeRange) -> Int32 {
  self.end
}

///|
/// Returns the number of codepoints in this range.
pub fn ClassUnicodeRange::len(self : ClassUnicodeRange) -> Int32 {
  1 + self.end - self.start
}

///|
/// A set of characters represented by arbitrary bytes.
///
/// Each byte corresponds to one character.
pub struct ClassBytes {
  priv set : IntervalSet[ClassBytesRange]
} derive(Eq, Debug)

///|
/// Create a new class from a sequence of ranges.
pub fn ClassBytes::new(ranges : Array[ClassBytesRange]) -> ClassBytes {
  { set: IntervalSet::new(ranges), }
}

///|
/// Create a new class with no ranges.
pub fn ClassBytes::empty() -> ClassBytes {
  ClassBytes::new([])
}

///|
/// A copy of this class (Rust `Clone`).
pub fn ClassBytes::copy(self : ClassBytes) -> ClassBytes {
  { set: self.set.copy(), }
}

///|
/// Add a new range to this set.
pub fn ClassBytes::push(self : ClassBytes, range : ClassBytesRange) -> Unit {
  self.set.push(range)
}

///|
/// Return an iterator over all ranges in this class.
pub fn ClassBytes::iter(self : ClassBytes) -> Iter[ClassBytesRange] {
  self.set.iter()
}

///|
/// Return the underlying ranges as a slice.
pub fn ClassBytes::ranges(self : ClassBytes) -> ArrayView[ClassBytesRange] {
  self.set.intervals()
}

///|
/// Expand this character class such that it contains all case folded
/// characters. For example, if this class consists of the range `a-z`,
/// then applying case folding will result in the class containing both the
/// ranges `a-z` and `A-Z`.
///
/// Note that this only applies ASCII case folding, which is limited to the
/// characters `a-z` and `A-Z`.
pub fn ClassBytes::case_fold_simple(self : ClassBytes) -> Unit {
  self.set.case_fold_simple() catch {
    _ => abort("ASCII case folding never fails")
  }
}

///|
/// Negate this byte class.
pub fn ClassBytes::negate(self : ClassBytes) -> Unit {
  self.set.negate()
}

///|
/// Union this byte class with the given byte class, in place.
pub fn ClassBytes::union(self : ClassBytes, other : ClassBytes) -> Unit {
  self.set.union(other.set)
}

///|
/// Intersect this byte class with the given byte class, in place.
pub fn ClassBytes::intersect(self : ClassBytes, other : ClassBytes) -> Unit {
  self.set.intersect(other.set)
}

///|
/// Subtract the given byte class from this byte class, in place.
pub fn ClassBytes::difference(self : ClassBytes, other : ClassBytes) -> Unit {
  self.set.difference(other.set)
}

///|
/// Compute the symmetric difference of the given byte classes, in place.
pub fn ClassBytes::symmetric_difference(
  self : ClassBytes,
  other : ClassBytes,
) -> Unit {
  self.set.symmetric_difference(other.set)
}

///|
/// Returns true if and only if this character class will either match
/// nothing or only ASCII bytes. Stated differently, this returns false
/// if and only if this class contains a non-ASCII byte.
pub fn ClassBytes::is_ascii(self : ClassBytes) -> Bool {
  match self.set.intervals().last() {
    None => true
    Some(r) => r.end <= 0x7F
  }
}

///|
/// Returns the length, in bytes, of the smallest string matched by this
/// character class.
pub fn ClassBytes::minimum_len(self : ClassBytes) -> UInt64? {
  if self.ranges().is_empty() {
    None
  } else {
    Some(1)
  }
}

///|
/// Returns the length, in bytes, of the longest string matched by this
/// character class.
pub fn ClassBytes::maximum_len(self : ClassBytes) -> UInt64? {
  if self.ranges().is_empty() {
    None
  } else {
    Some(1)
  }
}

///|
/// If this class consists of exactly one byte, then return it as
/// a literal byte string.
pub fn ClassBytes::literal(self : ClassBytes) -> Bytes? {
  let rs = self.ranges()
  if rs.length() == 1 && rs[0].start == rs[0].end {
    Some(Bytes::from_array([rs[0].start]))
  } else {
    None
  }
}

///|
/// If this class consists of only ASCII ranges, then return its
/// corresponding and equivalent Unicode class.
pub fn ClassBytes::to_unicode_class(self : ClassBytes) -> ClassUnicode? {
  if !self.is_ascii() {
    return None
  }
  Some(
    ClassUnicode::new(
      self
      .ranges()
      .iter()
      .map(r => ClassUnicodeRange::{
        // Since we are guaranteed that our byte range is ASCII, the
        // 'char::from' calls below are correct and will not erroneously
        // convert a raw byte value into its corresponding codepoint.
        start: r.start.to_int(),
        end: r.end.to_int(),
      })
      .collect(),
    ),
  )
}

///|
/// A single range of characters represented by arbitrary bytes.
///
/// The range is closed. That is, the start and end of the range are included
/// in the range.
pub(all) struct ClassBytesRange {
  start : Byte
  end : Byte
} derive(Eq, Compare, Debug)

///|
pub impl Interval for ClassBytesRange with fn lower(self) {
  self.start.to_int()
}

///|
pub impl Interval for ClassBytesRange with fn upper(self) {
  self.end.to_int()
}

///|
pub impl Interval for ClassBytesRange with fn create(lower, upper) {
  if lower <= upper {
    { start: lower.to_byte(), end: upper.to_byte(), }
  } else {
    { start: upper.to_byte(), end: lower.to_byte(), }
  }
}

///|
pub impl Interval for ClassBytesRange with fn bound_min_value() {
  0
}

///|
pub impl Interval for ClassBytesRange with fn bound_max_value() {
  0xFF
}

///|
pub impl Interval for ClassBytesRange with fn bound_increment(b) {
  byte_increment(b)
}

///|
pub impl Interval for ClassBytesRange with fn bound_decrement(b) {
  byte_decrement(b)
}

///|
/// Apply simple case folding to this byte range. Only ASCII case mappings
/// (for a-z) are applied.
///
/// Additional ranges are appended to the given vector. Canonical ordering
/// is *not* maintained in the given vector.
pub impl Interval for ClassBytesRange with fn case_fold_simple(self, ranges) {
  if !interval_is_intersection_empty(ClassBytesRange::new(b'a', b'z'), self) {
    let lower = @cmp.maximum(self.start, b'a')
    let upper = @cmp.minimum(self.end, b'z')
    ranges.push(ClassBytesRange::new(lower - 32, upper - 32))
  }
  if !interval_is_intersection_empty(ClassBytesRange::new(b'A', b'Z'), self) {
    let lower = @cmp.maximum(self.start, b'A')
    let upper = @cmp.minimum(self.end, b'Z')
    ranges.push(ClassBytesRange::new(lower + 32, upper + 32))
  }
}

///|
/// Create a new byte range for a character class.
///
/// The returned range is always in a canonical form. That is, the range
/// returned always satisfies the invariant that `start <= end`.
pub fn ClassBytesRange::new(start : Byte, end : Byte) -> ClassBytesRange {
  Interval::create(start.to_int(), end.to_int())
}

///|
/// Return the start of this range.
pub fn ClassBytesRange::start(self : ClassBytesRange) -> Byte {
  self.start
}

///|
/// Return the end of this range.
pub fn ClassBytesRange::end(self : ClassBytesRange) -> Byte {
  self.end
}

///|
/// Returns the number of bytes in this range.
pub fn ClassBytesRange::len(self : ClassBytesRange) -> Int32 {
  self.end.to_int() - self.start.to_int() + 1
}

///|
/// The high-level intermediate representation for a look-around assertion.
///
/// An assertion match is always zero-length. Also called an "empty match."
pub(all) enum Look {
  /// Match the beginning of text.
  Start
  /// Match the end of text.
  End
  /// Match the beginning of a line or the beginning of text.
  StartLF
  /// Match the end of a line or the end of text.
  EndLF
  /// Match the beginning of a line or the beginning of text (CRLF aware).
  StartCRLF
  /// Match the end of a line or the end of text (CRLF aware).
  EndCRLF
  /// Match an ASCII-only word boundary.
  WordAscii
  /// Match an ASCII-only negation of a word boundary.
  WordAsciiNegate
  /// Match a Unicode-aware word boundary.
  WordUnicode
  /// Match a Unicode-aware negation of a word boundary.
  WordUnicodeNegate
  /// Match the start of an ASCII-only word boundary.
  WordStartAscii
  /// Match the end of an ASCII-only word boundary.
  WordEndAscii
  /// Match the start of a Unicode word boundary.
  WordStartUnicode
  /// Match the end of a Unicode word boundary.
  WordEndUnicode
  /// Match the start half of an ASCII-only word boundary.
  WordStartHalfAscii
  /// Match the end half of an ASCII-only word boundary.
  WordEndHalfAscii
  /// Match the start half of a Unicode word boundary.
  WordStartHalfUnicode
  /// Match the end half of a Unicode word boundary.
  WordEndHalfUnicode
} derive(Eq, Debug)

///|
/// Flip the look-around assertion to its equivalent for reverse searches.
pub fn Look::reversed(self : Look) -> Look {
  match self {
    Start => End
    End => Start
    StartLF => EndLF
    EndLF => StartLF
    StartCRLF => EndCRLF
    EndCRLF => StartCRLF
    WordAscii => WordAscii
    WordAsciiNegate => WordAsciiNegate
    WordUnicode => WordUnicode
    WordUnicodeNegate => WordUnicodeNegate
    WordStartAscii => WordEndAscii
    WordEndAscii => WordStartAscii
    WordStartUnicode => WordEndUnicode
    WordEndUnicode => WordStartUnicode
    WordStartHalfAscii => WordEndHalfAscii
    WordEndHalfAscii => WordStartHalfAscii
    WordStartHalfUnicode => WordEndHalfUnicode
    WordEndHalfUnicode => WordStartHalfUnicode
  }
}

///|
/// Return the underlying representation of this look-around enumeration
/// as an integer. Giving the return value to the [`Look::from_repr`]
/// constructor is guaranteed to return the same look-around variant that
/// one started with within a semver compatible release of this crate.
pub fn Look::as_repr(self : Look) -> UInt32 {
  let bit = match self {
    Start => 0
    End => 1
    StartLF => 2
    EndLF => 3
    StartCRLF => 4
    EndCRLF => 5
    WordAscii => 6
    WordAsciiNegate => 7
    WordUnicode => 8
    WordUnicodeNegate => 9
    WordStartAscii => 10
    WordEndAscii => 11
    WordStartUnicode => 12
    WordEndUnicode => 13
    WordStartHalfAscii => 14
    WordEndHalfAscii => 15
    WordStartHalfUnicode => 16
    WordEndHalfUnicode => 17
  }
  1U << bit
}

///|
/// Given the underlying representation of a `Look` value, return the
/// corresponding `Look` value if the representation is valid. Otherwise
/// `None` is returned.
pub fn Look::from_repr(repr : UInt32) -> Look? {
  let all : Array[Look] = [
    Start,
    End,
    StartLF,
    EndLF,
    StartCRLF,
    EndCRLF,
    WordAscii,
    WordAsciiNegate,
    WordUnicode,
    WordUnicodeNegate,
    WordStartAscii,
    WordEndAscii,
    WordStartUnicode,
    WordEndUnicode,
    WordStartHalfAscii,
    WordEndHalfAscii,
    WordStartHalfUnicode,
    WordEndHalfUnicode,
  ]
  for look in all {
    if look.as_repr() == repr {
      return Some(look)
    }
  }
  None
}

///|
/// Returns a convenient single codepoint representation of this
/// look-around assertion.
pub fn Look::as_char(self : Look) -> Char {
  match self {
    Start => 'A'
    End => 'z'
    StartLF => '^'
    EndLF => '$'
    StartCRLF => 'r'
    EndCRLF => 'R'
    WordAscii => 'b'
    WordAsciiNegate => 'B'
    WordUnicode => '𝛃'
    WordUnicodeNegate => '𝚩'
    WordStartAscii => '<'
    WordEndAscii => '>'
    WordStartUnicode => '〈'
    WordEndUnicode => '〉'
    WordStartHalfAscii => '◁'
    WordEndHalfAscii => '▷'
    WordStartHalfUnicode => '◀'
    WordEndHalfUnicode => '▶'
  }
}

///|
/// The high-level intermediate representation for a capturing group.
pub(all) struct Capture {
  /// The capture index of the capture.
  index : UInt32
  /// The name of the capture, if it exists.
  name : String?
  /// The expression inside the capturing group, which may be empty.
  sub : Hir
} derive(Eq, Debug)

///|
/// The high-level intermediate representation of a repetition operator.
pub(all) struct Repetition {
  /// The minimum range of the repetition.
  min : UInt32
  /// The maximum range of the repetition.
  ///
  /// Note that when `max` is `None`, `min` acts as a lower bound but where
  /// there is no upper bound. For something like `x{5}` where the min and
  /// max are equivalent, `min` will be set to `5` and `max` will be set to
  /// `Some(5)`.
  max : UInt32?
  /// Whether this repetition operator is greedy or not.
  greedy : Bool
  /// The expression being repeated.
  sub : Hir
} derive(Eq, Debug)

///|
/// Returns a new repetition with the same `min`, `max` and `greedy`
/// values, but with its sub-expression replaced with the one given.
pub fn Repetition::with_sub(self : Repetition, sub : Hir) -> Repetition {
  { min: self.min, max: self.max, greedy: self.greedy, sub, }
}

///|
/// A type describing the different flavors of `.`.
pub(all) enum Dot {
  /// Matches the UTF-8 encoding of any Unicode scalar value.
  AnyChar
  /// Matches any byte value.
  AnyByte
  /// Matches the UTF-8 encoding of any Unicode scalar value except for the
  /// `char` given.
  AnyCharExcept(Int32)
  /// Matches the UTF-8 encoding of any Unicode scalar value except for `\n`.
  AnyCharExceptLF
  /// Matches the UTF-8 encoding of any Unicode scalar value except for `\r`
  /// and `\n`.
  AnyCharExceptCRLF
  /// Matches any byte value except for the `u8` given.
  AnyByteExcept(Byte)
  /// Matches any byte value except for `\n`.
  AnyByteExceptLF
  /// Matches any byte value except for `\r` and `\n`.
  AnyByteExceptCRLF
} derive(Eq, Debug)

///|
/// A type that collects various properties of an HIR value.
///
/// Properties are always scalar values and represent meta data that is
/// computed inductively on an HIR value. Properties are defined for all
/// HIR values.
pub struct Properties {
  priv minimum_len : UInt64?
  priv maximum_len : UInt64?
  priv look_set : LookSet
  priv look_set_prefix : LookSet
  priv look_set_suffix : LookSet
  priv look_set_prefix_any : LookSet
  priv look_set_suffix_any : LookSet
  priv utf8 : Bool
  priv explicit_captures_len : UInt64
  priv static_explicit_captures_len : UInt64?
  priv literal : Bool
  priv alternation_literal : Bool
} derive(Eq, Debug)

///|
/// Returns the length (in bytes) of the smallest string matched by this
/// HIR.
pub fn Properties::minimum_len(self : Properties) -> UInt64? {
  self.minimum_len
}

///|
/// Returns the length (in bytes) of the longest string matched by this
/// HIR.
pub fn Properties::maximum_len(self : Properties) -> UInt64? {
  self.maximum_len
}

///|
/// Returns a set of all look-around assertions that appear at least once
/// in this HIR value.
pub fn Properties::look_set(self : Properties) -> LookSet {
  self.look_set
}

///|
/// Returns a set of all look-around assertions that appear as a prefix for
/// this HIR value.
pub fn Properties::look_set_prefix(self : Properties) -> LookSet {
  self.look_set_prefix
}

///|
/// Returns a set of all look-around assertions that appear as a _possible_
/// prefix for this HIR value.
pub fn Properties::look_set_prefix_any(self : Properties) -> LookSet {
  self.look_set_prefix_any
}

///|
/// Returns a set of all look-around assertions that appear as a suffix for
/// this HIR value.
pub fn Properties::look_set_suffix(self : Properties) -> LookSet {
  self.look_set_suffix
}

///|
/// Returns a set of all look-around assertions that appear as a _possible_
/// suffix for this HIR value.
pub fn Properties::look_set_suffix_any(self : Properties) -> LookSet {
  self.look_set_suffix_any
}

///|
/// Return true if and only if the corresponding HIR will always match
/// valid UTF-8.
pub fn Properties::is_utf8(self : Properties) -> Bool {
  self.utf8
}

///|
/// Returns the total number of explicit capturing groups in the
/// corresponding HIR.
pub fn Properties::explicit_captures_len(self : Properties) -> UInt64 {
  self.explicit_captures_len
}

///|
/// Returns the total number of explicit capturing groups that appear in
/// every possible match.
pub fn Properties::static_explicit_captures_len(self : Properties) -> UInt64? {
  self.static_explicit_captures_len
}

///|
/// Return true if and only if this HIR is a simple literal.
pub fn Properties::is_literal(self : Properties) -> Bool {
  self.literal
}

///|
/// Return true if and only if this HIR is either a simple literal or an
/// alternation of simple literals.
pub fn Properties::is_alternation_literal(self : Properties) -> Bool {
  self.alternation_literal
}

///|
fn saturating_add(a : UInt64, b : UInt64) -> UInt64 {
  let s = a + b
  if s < a {
    18446744073709551615UL
  } else {
    s
  }
}

///|
fn saturating_mul(a : UInt64, b : UInt64) -> UInt64 {
  match checked_mul(a, b) {
    Some(p) => p
    None => 18446744073709551615UL
  }
}

///|
fn checked_mul(a : UInt64, b : UInt64) -> UInt64? {
  if a == 0 || b == 0 {
    return Some(0)
  }
  let p = a * b
  if p / b != a {
    None
  } else {
    Some(p)
  }
}

///|
fn checked_add(a : UInt64, b : UInt64) -> UInt64? {
  let s = a + b
  if s < a {
    None
  } else {
    Some(s)
  }
}

///|
/// Create a new set of HIR properties that represents the union of the
/// given properties.
///
/// This is useful when one has multiple `Hir` expressions and wants
/// to combine them into a single alternation without constructing the
/// corresponding `Hir`. This routine provides a way of combining the
/// properties of each `Hir` expression into one set of properties
/// representing the union of those expressions.
pub fn Properties::union(props : Array[Properties]) -> Properties {
  // While empty alternations aren't possible, we still behave as if they
  // are. When we have an empty alternate, then clearly the look-around
  // prefix and suffix is empty. Otherwise, it is the intersection of all
  // prefixes and suffixes (respectively) of the branches.
  let fix = if props.is_empty() { LookSet::empty() } else { LookSet::full() }
  // And also, an empty alternate means we have 0 static capture groups,
  // but we otherwise start with the number corresponding to the first
  // alternate. If any subsequent alternate has a different number of
  // static capture groups, then we overall have a variation and not a
  // static number of groups.
  let static_explicit_captures_len = match props.get(0) {
    Some(p) => p.static_explicit_captures_len()
    None => None
  }
  // The base case is an empty alternation, which matches nothing.
  // Note though that empty alternations aren't possible, because the
  // Hir::alternation smart constructor rewrites those as empty character
  // classes.
  let mut minimum_len : UInt64? = None
  let mut maximum_len : UInt64? = None
  let mut look_set = LookSet::empty()
  let mut look_set_prefix = fix
  let mut look_set_suffix = fix
  let mut look_set_prefix_any = LookSet::empty()
  let mut look_set_suffix_any = LookSet::empty()
  let mut utf8 = true
  let mut explicit_captures_len = 0UL
  let mut static_explicit_captures_len = static_explicit_captures_len
  let mut alternation_literal = true
  let mut min_poisoned = false
  let mut max_poisoned = false
  // Handle properties that need to visit every child hir.
  for p in props {
    look_set = look_set.union(p.look_set())
    look_set_prefix = look_set_prefix.intersect(p.look_set_prefix())
    look_set_suffix = look_set_suffix.intersect(p.look_set_suffix())
    look_set_prefix_any = look_set_prefix_any.union(p.look_set_prefix_any())
    look_set_suffix_any = look_set_suffix_any.union(p.look_set_suffix_any())
    utf8 = utf8 && p.is_utf8()
    explicit_captures_len = saturating_add(
      explicit_captures_len,
      p.explicit_captures_len(),
    )
    if static_explicit_captures_len != p.static_explicit_captures_len() {
      static_explicit_captures_len = None
    }
    alternation_literal = alternation_literal && p.is_literal()
    if !min_poisoned {
      match p.minimum_len() {
        Some(xmin) =>
          match minimum_len {
            Some(pmin) if !(xmin < pmin) => ()
            _ => minimum_len = Some(xmin)
          }
        None => {
          minimum_len = None
          min_poisoned = true
        }
      }
    }
    if !max_poisoned {
      match p.maximum_len() {
        Some(xmax) =>
          match maximum_len {
            Some(pmax) if !(xmax > pmax) => ()
            _ => maximum_len = Some(xmax)
          }
        None => {
          maximum_len = None
          max_poisoned = true
        }
      }
    }
  }
  {
    minimum_len,
    maximum_len,
    look_set,
    look_set_prefix,
    look_set_suffix,
    look_set_prefix_any,
    look_set_suffix_any,
    utf8,
    explicit_captures_len,
    static_explicit_captures_len,
    literal: false,
    alternation_literal,
  }
}

///|
/// Create a new set of HIR properties for an empty regex.
fn Properties::empty() -> Properties {
  {
    minimum_len: Some(0),
    maximum_len: Some(0),
    look_set: LookSet::empty(),
    look_set_prefix: LookSet::empty(),
    look_set_suffix: LookSet::empty(),
    look_set_prefix_any: LookSet::empty(),
    look_set_suffix_any: LookSet::empty(),
    // It is debatable whether an empty regex always matches at valid
    // UTF-8 boundaries. Strictly speaking, at a byte oriented view,
    // it is clearly false. There are, for example, many empty strings
    // between the bytes encoding a '☃'.
    //
    // However, when Unicode mode is enabled, the fundamental atom
    // of matching is really a codepoint. And in that scenario, an
    // empty regex is defined to only match at valid UTF-8 boundaries
    // and to never split a codepoint. It just so happens that this
    // enforcement is somewhat tricky to do for regexes that match
    // the empty string inside regex engines themselves. It usually
    // requires some layer above the regex engine to filter out such
    // matches.
    //
    // In any case, 'true' is really the only coherent option. If it
    // were false, for example, then 'a*' would also need to be false
    // since it too can match the empty string.
    utf8: true,
    explicit_captures_len: 0,
    static_explicit_captures_len: Some(0),
    literal: false,
    alternation_literal: false,
  }
}

///|
/// Create a new set of HIR properties for a literal regex.
fn Properties::literal(lit : Literal) -> Properties {
  let Literal(bytes) = lit
  {
    minimum_len: Some(bytes.length().to_uint64()),
    maximum_len: Some(bytes.length().to_uint64()),
    look_set: LookSet::empty(),
    look_set_prefix: LookSet::empty(),
    look_set_suffix: LookSet::empty(),
    look_set_prefix_any: LookSet::empty(),
    look_set_suffix_any: LookSet::empty(),
    utf8: try from_utf8(bytes[:]) |> ignore catch {
      _ => false
    } noraise {
      _ => true
    },
    explicit_captures_len: 0,
    static_explicit_captures_len: Some(0),
    literal: true,
    alternation_literal: true,
  }
}

///|
/// Create a new set of HIR properties for a character class.
fn Properties::class(class : Class) -> Properties {
  {
    minimum_len: class.minimum_len(),
    maximum_len: class.maximum_len(),
    look_set: LookSet::empty(),
    look_set_prefix: LookSet::empty(),
    look_set_suffix: LookSet::empty(),
    look_set_prefix_any: LookSet::empty(),
    look_set_suffix_any: LookSet::empty(),
    utf8: class.is_utf8(),
    explicit_captures_len: 0,
    static_explicit_captures_len: Some(0),
    literal: false,
    alternation_literal: false,
  }
}

///|
/// Create a new set of HIR properties for a look-around assertion.
fn Properties::look(look : Look) -> Properties {
  {
    minimum_len: Some(0),
    maximum_len: Some(0),
    look_set: LookSet::singleton(look),
    look_set_prefix: LookSet::singleton(look),
    look_set_suffix: LookSet::singleton(look),
    look_set_prefix_any: LookSet::singleton(look),
    look_set_suffix_any: LookSet::singleton(look),
    // This requires a little explanation. Basically, we don't consider
    // matching an empty string to be equivalent to matching invalid
    // UTF-8, even though technically matching every empty string will
    // split the UTF-8 encoding of a single codepoint when treating a
    // UTF-8 encoded string as a sequence of bytes. Our defense here is
    // that in such a case, a codepoint should logically be treated as
    // the fundamental atom for matching, and thus the only valid match
    // points are between codepoints and not bytes.
    //
    // More practically, this is true here because it's also true
    // for 'Hir::empty()', otherwise something like 'a*' would be
    // considered to match invalid UTF-8. That in turn makes this
    // property borderline useless.
    utf8: true,
    explicit_captures_len: 0,
    static_explicit_captures_len: Some(0),
    literal: false,
    alternation_literal: false,
  }
}

///|
/// Create a new set of HIR properties for a repetition.
fn Properties::repetition(rep : Repetition) -> Properties {
  let p = rep.sub.properties()
  let minimum_len = match p.minimum_len() {
    Some(child_min) => Some(saturating_mul(child_min, rep.min.to_uint64()))
    None => None
  }
  let maximum_len = match rep.max {
    Some(rep_max) =>
      match p.maximum_len() {
        Some(child_max) => checked_mul(child_max, rep_max.to_uint64())
        None => None
      }
    None => None
  }
  let mut inner : Properties = {
    minimum_len,
    maximum_len,
    look_set: p.look_set(),
    look_set_prefix: LookSet::empty(),
    look_set_suffix: LookSet::empty(),
    look_set_prefix_any: p.look_set_prefix_any(),
    look_set_suffix_any: p.look_set_suffix_any(),
    utf8: p.is_utf8(),
    explicit_captures_len: p.explicit_captures_len(),
    static_explicit_captures_len: p.static_explicit_captures_len(),
    literal: false,
    alternation_literal: false,
  }
  // If the repetition operator can match the empty string, then its
  // lookset prefix and suffixes themselves remain empty since they are
  // no longer required to match.
  if rep.min > 0 {
    inner = {
      ..inner,
      look_set_prefix: p.look_set_prefix(),
      look_set_suffix: p.look_set_suffix(),
    }
  }
  // If the static captures len of the sub-expression is not known or
  // is greater than zero, then it automatically propagates to the
  // repetition, regardless of the repetition. Otherwise, it might
  // change, but only when the repetition can match 0 times.
  if rep.min == 0 &&
    (match inner.static_explicit_captures_len {
      Some(len) => len > 0
      None => false
    }) {
    // If we require a match 0 times, then our captures len is
    // guaranteed to be zero. Otherwise, if we *can* match the empty
    // string, then it's impossible to know how many captures will be
    // in the resulting match.
    if rep.max == Some(0) {
      inner = { ..inner, static_explicit_captures_len: Some(0), }
    } else {
      inner = { ..inner, static_explicit_captures_len: None, }
    }
  }
  inner
}

///|
/// Create a new set of HIR properties for a capture.
fn Properties::capture(capture : Capture) -> Properties {
  let p = capture.sub.properties()
  {
    ..p,
    explicit_captures_len: saturating_add(p.explicit_captures_len(), 1),
    static_explicit_captures_len: match p.static_explicit_captures_len() {
      Some(len) => Some(saturating_add(len, 1))
      None => None
    },
    literal: false,
    alternation_literal: false,
  }
}

///|
/// Create a new set of HIR properties for a concatenation.
fn Properties::concat(concat : Array[Hir]) -> Properties {
  // The base case is an empty concatenation, which matches the empty
  // string. Note though that empty concatenations aren't possible,
  // because the Hir::concat smart constructor rewrites those as
  // Hir::empty.
  let mut minimum_len : UInt64? = Some(0)
  let mut maximum_len : UInt64? = Some(0)
  let mut look_set = LookSet::empty()
  let mut look_set_prefix = LookSet::empty()
  let mut look_set_suffix = LookSet::empty()
  let mut look_set_prefix_any = LookSet::empty()
  let mut look_set_suffix_any = LookSet::empty()
  let mut utf8 = true
  let mut explicit_captures_len = 0UL
  let mut static_explicit_captures_len : UInt64? = Some(0)
  let mut literal = true
  let mut alternation_literal = true
  // Handle properties that need to visit every child hir.
  for x in concat {
    let p = x.properties()
    look_set = look_set.union(p.look_set())
    utf8 = utf8 && p.is_utf8()
    explicit_captures_len = saturating_add(
      explicit_captures_len,
      p.explicit_captures_len(),
    )
    static_explicit_captures_len = match
      (p.static_explicit_captures_len(), static_explicit_captures_len) {
      (Some(len1), Some(len2)) => Some(saturating_add(len1, len2))
      _ => None
    }
    literal = literal && p.is_literal()
    alternation_literal = alternation_literal && p.is_alternation_literal()
    if minimum_len is Some(ml) {
      match p.minimum_len() {
        None => minimum_len = None
        Some(len) =>
          // We use saturating arithmetic here because the
          // minimum is just a lower bound. We can't go any
          // higher than what our number types permit.
          minimum_len = Some(saturating_add(ml, len))
      }
    }
    if maximum_len is Some(ml) {
      match p.maximum_len() {
        None => maximum_len = None
        Some(len) => maximum_len = checked_add(ml, len)
      }
    }
  }
  // Handle the prefix properties, which only requires visiting
  // child exprs until one matches more than the empty string.
  for x in concat {
    look_set_prefix = look_set_prefix.union(x.properties().look_set_prefix())
    look_set_prefix_any = look_set_prefix_any.union(
      x.properties().look_set_prefix_any(),
    )
    if (match x.properties().maximum_len() {
        Some(x) => x > 0
        None => true
      }) {
      break
    }
  }
  // Same thing for the suffix properties, but in reverse.
  for x in concat.rev_iter() {
    look_set_suffix = look_set_suffix.union(x.properties().look_set_suffix())
    look_set_suffix_any = look_set_suffix_any.union(
      x.properties().look_set_suffix_any(),
    )
    if (match x.properties().maximum_len() {
        Some(x) => x > 0
        None => true
      }) {
      break
    }
  }
  {
    minimum_len,
    maximum_len,
    look_set,
    look_set_prefix,
    look_set_suffix,
    look_set_prefix_any,
    look_set_suffix_any,
    utf8,
    explicit_captures_len,
    static_explicit_captures_len,
    literal,
    alternation_literal,
  }
}

///|
/// Create a new set of HIR properties for a concatenation.
fn Properties::alternation(alts : Array[Hir]) -> Properties {
  Properties::union(alts.map(hir => hir.properties()))
}

///|
/// A set of look-around assertions.
///
/// This is useful for efficiently tracking look-around assertions. For
/// example, an [`Hir`] provides properties that return `LookSet`s.
pub(all) struct LookSet {
  /// The underlying representation this set is exposed to make it possible
  /// to store it somewhere efficiently. The representation is that
  /// of a bitset, where each assertion occupies bit `i` where
  /// `i = Look::as_repr()`.
  bits : UInt32
} derive(Eq, Debug)

///|
/// Create an empty set of look-around assertions.
pub fn LookSet::empty() -> LookSet {
  { bits: 0, }
}

///|
/// Create a full set of look-around assertions.
pub fn LookSet::full() -> LookSet {
  { bits: 0xFFFFFFFFU, }
}

///|
/// Create a look-around set containing the look-around assertion given.
pub fn LookSet::singleton(look : Look) -> LookSet {
  LookSet::empty().insert(look)
}

///|
/// Returns the total number of look-around assertions in this set.
pub fn LookSet::len(self : LookSet) -> Int32 {
  self.bits.popcnt()
}

///|
/// Returns true if and only if this set is empty.
pub fn LookSet::is_empty(self : LookSet) -> Bool {
  self.len() == 0
}

///|
/// Returns true if and only if the given look-around assertion is in this
/// set.
pub fn LookSet::contains(self : LookSet, look : Look) -> Bool {
  (self.bits & look.as_repr()) != 0
}

///|
/// Return a new set that is equivalent to the original, but with the given
/// assertion added to it. If the assertion is already in the set, then the
/// returned set is equivalent to the original.
pub fn LookSet::insert(self : LookSet, look : Look) -> LookSet {
  { bits: self.bits | look.as_repr(), }
}

///|
/// Return a new set that is equivalent to the original, but with the given
/// assertion removed from it. If the assertion is not in the set, then the
/// returned set is equivalent to the original.
pub fn LookSet::remove(self : LookSet, look : Look) -> LookSet {
  { bits: self.bits & look.as_repr().lnot(), }
}

///|
/// Returns a new set that is the result of subtracting the given set from
/// this set.
pub fn LookSet::subtract(self : LookSet, other : LookSet) -> LookSet {
  { bits: self.bits & other.bits.lnot(), }
}

///|
/// Returns a new set that is the union of this and the one given.
pub fn LookSet::union(self : LookSet, other : LookSet) -> LookSet {
  { bits: self.bits | other.bits, }
}

///|
/// Returns a new set that is the intersection of this and the one given.
pub fn LookSet::intersect(self : LookSet, other : LookSet) -> LookSet {
  { bits: self.bits & other.bits, }
}

///|
/// Given a sequence of HIR values where each value corresponds to a Unicode
/// class (or an all-ASCII byte class), return a single Unicode class
/// corresponding to the union of the classes found.
fn class_chars(hirs : Array[Hir]) -> Class? {
  let cls = ClassUnicode::new([])
  for hir in hirs {
    match hir.kind() {
      Class(Unicode(cls2)) => cls.union(cls2)
      Class(Bytes(cls2)) =>
        match cls2.to_unicode_class() {
          Some(c) => cls.union(c)
          None => return None
        }
      _ => return None
    }
  }
  Some(Unicode(cls))
}

///|
/// Given a sequence of HIR values where each value corresponds to a byte class
/// (or an all-ASCII Unicode class), return a single byte class corresponding
/// to the union of the classes found.
fn class_bytes(hirs : Array[Hir]) -> Class? {
  let cls = ClassBytes::new([])
  for hir in hirs {
    match hir.kind() {
      Class(Unicode(cls2)) =>
        match cls2.to_byte_class() {
          Some(c) => cls.union(c)
          None => return None
        }
      Class(Bytes(cls2)) => cls.union(cls2)
      _ => return None
    }
  }
  Some(Bytes(cls))
}

///|
/// Given a sequence of HIR values where each value corresponds to a literal
/// that is a single `char`, return that sequence of `char`s. Otherwise return
/// None. No deduplication is done.
fn singleton_chars(hirs : Array[Hir]) -> Array[Int32]? {
  let singletons = []
  for hir in hirs {
    let literal = match hir.kind() {
      Literal(Literal(bytes)) => bytes
      _ => return None
    }
    let ch = match utf8_decode(literal[:]) {
      None => return None
      Some(Err(_)) => return None
      Some(Ok(ch)) => ch
    }
    if literal.length() != len_utf8(ch) {
      return None
    }
    singletons.push(ch)
  }
  Some(singletons)
}

///|
/// Given a sequence of HIR values where each value corresponds to a literal
/// that is a single byte, return that sequence of bytes. Otherwise return
/// None. No deduplication is done.
fn singleton_bytes(hirs : Array[Hir]) -> Array[Byte]? {
  let singletons = []
  for hir in hirs {
    let literal = match hir.kind() {
      Literal(Literal(bytes)) => bytes
      _ => return None
    }
    if literal.length() != 1 {
      return None
    }
    singletons.push(literal[0])
  }
  Some(singletons)
}

///|
/// Looks for a common prefix in the list of alternation branches given. If one
/// is found, then an equivalent but (hopefully) simplified Hir is returned.
/// Otherwise, the original given list of branches is returned unmodified.
///
/// This is not quite as good as it could be. Right now, it requires that
/// all branches are 'Concat' expressions. It also doesn't do well with
/// literals. For example, given 'foofoo|foobar', it will not refactor it to
/// 'foo(?:foo|bar)' because literals are flattened into their own special
/// concatenation. (One wonders if perhaps 'Literal' should be a single atom
/// instead of a string of bytes because of this. Otherwise, handling the
/// current representation in this routine will be pretty gnarly. Sigh.)
#warnings("-result_error_return")
fn lift_common_prefix(hirs : Array[Hir]) -> Result[Hir, Array[Hir]] {
  if hirs.length() <= 1 {
    return Err(hirs)
  }
  let mut prefix = match hirs[0].kind() {
    Concat(xs) => xs[:]
    _ => return Err(hirs)
  }
  if prefix.is_empty() {
    return Err(hirs)
  }
  for h in hirs[1:] {
    let concat = match h.kind() {
      Concat(xs) => xs
      _ => return Err(hirs)
    }
    let mut common_len = 0
    while common_len < prefix.length() &&
          common_len < concat.length() &&
          prefix[common_len] == concat[common_len] {
      common_len += 1
    }
    prefix = prefix[:common_len]
    if prefix.is_empty() {
      return Err(hirs)
    }
  }
  let len = prefix.length()
  guard len != 0 else { abort("assertion failed") }
  let mut prefix_concat = []
  let suffix_alts = []
  for h in hirs {
    let concat = match h.into_kind() {
      Concat(xs) => xs
      // We required all sub-expressions to be
      // concats above, so we're only here if we
      // have a concat.
      _ => abort("unreachable")
    }
    suffix_alts.push(Hir::concat(concat[len:].to_owned()))
    if prefix_concat.is_empty() {
      prefix_concat = concat[:len].to_owned()
    }
  }
  let concat = prefix_concat
  concat.push(Hir::alternation(suffix_alts))
  Ok(Hir::concat(concat))
}

///|
/// `debug::utf8_decode`: decode the first UTF-8 encoded code point in
/// `bytes`.
///
/// If no valid encoding of a code point exists at the beginning of the given
/// byte slice, then the first byte is returned instead. If `bytes` is empty,
/// `None` is returned.
#warnings("-result_error_return")
pub fn utf8_decode(bytes : BytesView) -> Result[Int32, Byte]? {
  fn len(byte : Byte) -> Int32? {
    if byte <= 0x7F {
      return Some(1)
    } else if (byte & 0b1100_0000) == 0b1000_0000 {
      return None
    } else if byte <= 0b1101_1111 {
      Some(2)
    } else if byte <= 0b1110_1111 {
      Some(3)
    } else if byte <= 0b1111_0111 {
      Some(4)
    } else {
      None
    }
  }

  if bytes.is_empty() {
    return None
  }
  let len = match len(bytes[0]) {
    None => return Some(Err(bytes[0]))
    Some(len) if len > bytes.length() => return Some(Err(bytes[0]))
    Some(1) => return Some(Ok(bytes[0].to_int()))
    Some(len) => len
  }
  try from_utf8(bytes[:len]) catch {
    _ => Some(Err(bytes[0]))
  } noraise {
    s => Some(Ok(s[0].to_int()))
  }
}