rexact_syntax/

parser.rs

//! Hand-written recursive-descent parsers for the `ecma` and `python` dialects
//! (FR-A04..A06, FR-A12).
//!
//! Contract: text in, [`Pattern`] or a catalogue error out; never a panic,
//! never an approximation (RULE-05). Unsupported constructs are recognised and
//! rejected with their own code. Invariant: nesting is bounded by
//! [`ParseLimits::max_depth`], so hostile input cannot overflow the stack.
//! Dialect rules are kept in separate functions (`esc_ecma`, `esc_py`, ...)
//! and never unified (RULE-10).

use crate::ast::*;
use crate::dialect::Dialect;
use crate::error::{ErrorCode, RexactError};
use crate::flags::Flags;
use crate::locate::locate;
use rexact_unicode as uni;

/// Bounds enforced while parsing (RULE-08).
#[derive(Debug, Clone)]
pub struct ParseLimits {
    /// Maximum pattern length in scalar values (`RX-L005`).
    pub max_length: u64,
    /// Maximum group nesting depth (`RX-L006`).
    pub max_depth: u32,
}

impl Default for ParseLimits {
    fn default() -> Self {
        Self {
            max_length: 1_000_000,
            max_depth: 100,
        }
    }
}

/// A parsed pattern.
#[derive(Debug, Clone)]
pub struct Pattern {
    /// Original text.
    pub source: String,
    /// Dialect it was written for.
    pub dialect: Dialect,
    /// Effective global flags (option flags plus leading inline flags).
    pub flags: Flags,
    /// Syntax tree.
    pub ast: Node,
    /// Number of capturing groups.
    pub group_count: u32,
    /// Names of named groups, in order of appearance.
    pub group_names: Vec<String>,
    /// Non-fatal notes (for example ignored flags).
    pub notes: Vec<String>,
}

impl Pattern {
    /// Parse with default limits.
    pub fn parse(source: &str, dialect: Dialect, flags: Flags) -> Result<Pattern, RexactError> {
        Self::parse_with(source, dialect, flags, &ParseLimits::default())
    }

    /// Parse with explicit limits.
    pub fn parse_with(
        source: &str,
        dialect: Dialect,
        flags: Flags,
        limits: &ParseLimits,
    ) -> Result<Pattern, RexactError> {
        let chars: Vec<char> = source.chars().collect();
        let fail = |e: PErr| {
            let mut r = RexactError::new(e.code);
            r.detail = e.detail;
            r.position = Some(locate(&chars, e.offset));
            r
        };
        if chars.len() as u64 > limits.max_length {
            return Err(fail(PErr::new(
                ErrorCode::L005,
                0,
                "pattern exceeds the length limit",
            )));
        }
        if matches!(dialect, Dialect::Go | Dialect::Rust) {
            let out = crate::parser_re2::parse(&chars, dialect, flags, limits).map_err(fail)?;
            return Ok(Pattern {
                source: source.to_string(),
                dialect,
                flags: out.flags,
                ast: out.ast,
                group_count: out.groups,
                group_names: out.names,
                notes: out.notes,
            });
        }
        if dialect == Dialect::Java {
            // Java strings are UTF-16: the pattern is read as characters, whatever the flags.
            crate::java::check(&chars).map_err(fail)?;
            let out = crate::parser_pcre::parse(&chars, flags, limits).map_err(fail)?;
            return Ok(Pattern {
                source: source.to_string(),
                dialect,
                flags: out.flags,
                ast: out.ast,
                group_count: out.groups,
                group_names: out.names,
                notes: Vec::new(),
            });
        }
        if dialect == Dialect::Pcre2 {
            // Without `u` PCRE2 works on bytes: parse the UTF-8 bytes of the text.
            let byte_chars: Vec<char>;
            let input: &[char] = if flags.u {
                &chars
            } else {
                byte_chars = source.bytes().map(char::from).collect();
                &byte_chars
            };
            let out = crate::parser_pcre::parse(input, flags, limits).map_err(fail)?;
            return Ok(Pattern {
                source: source.to_string(),
                dialect,
                flags: out.flags,
                ast: out.ast,
                group_count: out.groups,
                group_names: out.names,
                notes: Vec::new(),
            });
        }
        let (groups, has_named) = scan_groups(&chars, dialect, flags.x);
        let mut p = Parser {
            chars: &chars,
            pos: 0,
            d: dialect,
            flags,
            max_depth: limits.max_depth,
            depth: 0,
            total_groups: groups,
            has_named,
            next_capture: 1,
            names: Vec::new(),
            seen_content: false,
        };
        let ast = p.alt().map_err(fail)?;
        if p.pos < chars.len() {
            return Err(fail(PErr::new(ErrorCode::P007, p.pos, "unmatched ')'")));
        }
        Ok(Pattern {
            source: source.to_string(),
            dialect,
            flags: p.flags,
            ast,
            group_count: p.next_capture - 1,
            group_names: p.names,
            notes: Vec::new(),
        })
    }

    /// Parse a `/body/flags` literal (FR-A03). Flag letters are interpreted
    /// for `dialect`; letters that do not change the language become notes.
    pub fn parse_literal(text: &str, dialect: Dialect) -> Result<Pattern, RexactError> {
        let shape = |why: &str| {
            let mut e = RexactError::new(ErrorCode::P010);
            e.detail = Some(format!("{why}; expected /body/flags"));
            e
        };
        let rest = text
            .strip_prefix('/')
            .ok_or_else(|| shape("missing opening '/'"))?;
        let close = rest
            .rfind('/')
            .ok_or_else(|| shape("missing closing '/'"))?;
        let (body, flag_text) = (&rest[..close], &rest[close + 1..]);
        if body.is_empty() {
            return Err(shape("empty body (// is a comment, not a regex)"));
        }
        if !flag_text.chars().all(|c| c.is_ascii_alphabetic()) {
            return Err(shape("flags must be letters"));
        }
        let (flags, notes) = Flags::from_letters(dialect, flag_text)?;
        let mut p = Pattern::parse(body, dialect, flags)?;
        p.notes = notes;
        Ok(p)
    }
}

pub(crate) struct PErr {
    pub(crate) code: ErrorCode,
    pub(crate) offset: usize,
    pub(crate) detail: Option<String>,
}

impl PErr {
    pub(crate) fn new(code: ErrorCode, offset: usize, detail: &str) -> Self {
        Self {
            code,
            offset,
            detail: Some(detail.to_string()),
        }
    }
}

pub(crate) type R<T> = Result<T, PErr>;

pub(crate) fn err<T>(code: ErrorCode, offset: usize, detail: &str) -> R<T> {
    Err(PErr::new(code, offset, detail))
}

/// Count capturing groups and detect named groups without building a tree.
/// Needed because a backreference may precede the group it names.
fn scan_groups(chars: &[char], d: Dialect, verbose: bool) -> (u32, bool) {
    let (mut count, mut named) = (0u32, false);
    let (mut i, mut in_class, mut class_start) = (0usize, false, 0usize);
    while i < chars.len() {
        let c = chars[i];
        if c == '\\' {
            i += 2;
            continue;
        }
        if in_class {
            // ECMAScript closes at the first ']'; Python treats a leading ']' as literal.
            if c == ']' && !(d == Dialect::Python && i == class_start) {
                in_class = false;
            }
        } else if c == '[' {
            in_class = true;
            class_start = i + 1;
            if chars.get(class_start) == Some(&'^') {
                class_start += 1;
            }
        } else if c == '#' && verbose && d == Dialect::Python {
            while i < chars.len() && chars[i] != '\n' {
                i += 1;
            }
            continue;
        } else if c == '(' {
            if chars.get(i + 1) != Some(&'?') {
                count += 1;
            } else {
                let is_named = match d {
                    Dialect::Python => {
                        chars.get(i + 2) == Some(&'P') && chars.get(i + 3) == Some(&'<')
                    }
                    _ => {
                        chars.get(i + 2) == Some(&'<')
                            && !matches!(chars.get(i + 3), Some('=') | Some('!'))
                    }
                };
                if is_named {
                    count += 1;
                    named = true;
                }
            }
        }
        i += 1;
    }
    (count, named)
}

enum Esc {
    Char(u32),
    Short(Shorthand),
    Prop(PropertyRef),
    Assert(Assertion),
}

enum ClassAtom {
    Ch(u32),
    Sh(Shorthand),
    Prop(PropertyRef),
}

impl ClassAtom {
    fn item(self) -> ClassItem {
        match self {
            ClassAtom::Ch(c) => ClassItem::Range(c, c),
            ClassAtom::Sh(s) => ClassItem::Shorthand(s),
            ClassAtom::Prop(p) => ClassItem::Property(p),
        }
    }
}

struct Parser<'a> {
    chars: &'a [char],
    pos: usize,
    d: Dialect,
    flags: Flags,
    max_depth: u32,
    depth: u32,
    total_groups: u32,
    has_named: bool,
    next_capture: u32,
    names: Vec<String>,
    /// True once any atom or `|` was seen; Python global flags must come first.
    seen_content: bool,
}

fn mk(kind: NodeKind, start: usize, end: usize) -> Node {
    Node {
        kind,
        span: Span { start, end },
    }
}

fn shorthand(c: char) -> Option<Shorthand> {
    Some(match c {
        'd' => Shorthand::Digit,
        'D' => Shorthand::NotDigit,
        'w' => Shorthand::Word,
        'W' => Shorthand::NotWord,
        's' => Shorthand::Space,
        'S' => Shorthand::NotSpace,
        _ => return None,
    })
}

impl Parser<'_> {
    fn peek(&self) -> Option<char> {
        self.chars.get(self.pos).copied()
    }
    fn peek_at(&self, n: usize) -> Option<char> {
        self.chars.get(self.pos + n).copied()
    }
    fn eat(&mut self, c: char) -> bool {
        if self.peek() == Some(c) {
            self.pos += 1;
            true
        } else {
            false
        }
    }
    fn is_py(&self) -> bool {
        self.d == Dialect::Python
    }
    /// ECMAScript Unicode mode.
    fn es_unicode(&self) -> bool {
        self.d == Dialect::Ecma && self.flags.u
    }

    /// Verbose mode (Python `x`): skip whitespace and `#` comments.
    fn skip_x(&mut self) {
        if !(self.is_py() && self.flags.x) {
            return;
        }
        while let Some(c) = self.peek() {
            if matches!(c, ' ' | '\t' | '\n' | '\r' | '\x0b' | '\x0c') {
                self.pos += 1;
            } else if c == '#' {
                while let Some(c) = self.peek() {
                    if c == '\n' {
                        break;
                    }
                    self.pos += 1;
                }
            } else {
                break;
            }
        }
    }

    fn alt(&mut self) -> R<Node> {
        self.depth += 1;
        if self.depth > self.max_depth {
            return err(
                ErrorCode::L006,
                self.pos,
                "group nesting exceeds the depth limit",
            );
        }
        let start = self.pos;
        let mut branches = vec![self.concat()?];
        while self.eat('|') {
            self.seen_content = true;
            branches.push(self.concat()?);
        }
        self.depth -= 1;
        Ok(match branches.len() {
            1 => branches.remove(0),
            _ => mk(NodeKind::Alt(branches), start, self.pos),
        })
    }

    fn concat(&mut self) -> R<Node> {
        let start = self.pos;
        let mut items = Vec::new();
        loop {
            self.skip_x();
            if matches!(self.peek(), None | Some('|') | Some(')')) {
                break;
            }
            if let Some(n) = self.term()? {
                self.seen_content = true;
                items.push(n);
            }
        }
        Ok(match items.len() {
            0 => mk(NodeKind::Empty, start, self.pos),
            1 => items.remove(0),
            _ => mk(NodeKind::Concat(items), start, self.pos),
        })
    }

    fn term(&mut self) -> R<Option<Node>> {
        let start = self.pos;
        let (atom, quantifiable) = self.atom()?;
        self.skip_x();
        if !quantifiable || atom.is_none() {
            if self.quantifier_ahead()? {
                return err(ErrorCode::P005, self.pos, "nothing to repeat");
            }
            return Ok(atom);
        }
        let Some(atom) = atom else { return Ok(None) };
        let Some((min, max)) = self.take_quantifier()? else {
            return Ok(Some(atom));
        };
        let mut greedy = true;
        if self.eat('?') {
            greedy = false;
        } else if self.is_py() && self.peek() == Some('+') {
            return err(
                ErrorCode::U004,
                self.pos,
                "possessive quantifier changes matching semantics",
            );
        }
        if self.quantifier_ahead()? {
            return err(ErrorCode::P005, self.pos, "multiple repeat");
        }
        Ok(Some(mk(
            NodeKind::Repeat {
                node: Box::new(atom),
                min,
                max,
                greedy,
            },
            start,
            self.pos,
        )))
    }

    fn quantifier_ahead(&self) -> R<bool> {
        Ok(match self.peek() {
            Some('*') | Some('+') | Some('?') => true,
            Some('{') => self.braces()?.is_some(),
            _ => false,
        })
    }

    fn digits(&self, mut i: usize) -> (Option<u64>, usize) {
        let mut v: Option<u64> = None;
        while let Some(d) = self.chars.get(i).and_then(|c| c.to_digit(10)) {
            v = Some(
                v.unwrap_or(0)
                    .saturating_mul(10)
                    .saturating_add(u64::from(d)),
            );
            i += 1;
        }
        (v, i)
    }

    /// Recognise `{n}`, `{n,}`, `{n,m}` (Python also `{,m}`, `{,}`) at `pos`
    /// without consuming. Anything else is a literal brace.
    fn braces(&self) -> R<Option<(u64, Option<u64>, usize)>> {
        let (lo, i) = self.digits(self.pos + 1);
        match self.chars.get(i) {
            Some('}') => Ok(lo.map(|l| (l, Some(l), i + 1))),
            Some(',') => {
                let (hi, j) = self.digits(i + 1);
                if self.chars.get(j) != Some(&'}') {
                    return Ok(None);
                }
                Ok(match (lo, hi) {
                    (None, _) if !self.is_py() => None,
                    (l, h) => Some((l.unwrap_or(0), h, j + 1)),
                })
            }
            _ => Ok(None),
        }
    }

    fn take_quantifier(&mut self) -> R<Option<(u64, Option<u64>)>> {
        let start = self.pos;
        let q = match self.peek() {
            Some('*') => {
                self.pos += 1;
                (0, None)
            }
            Some('+') => {
                self.pos += 1;
                (1, None)
            }
            Some('?') => {
                self.pos += 1;
                (0, Some(1))
            }
            Some('{') => match self.braces()? {
                Some((lo, hi, end)) => {
                    self.pos = end;
                    if self.is_py()
                        && (lo >= u64::from(u32::MAX)
                            || hi.is_some_and(|h| h >= u64::from(u32::MAX)))
                    {
                        return err(ErrorCode::P005, start, "repetition count out of range");
                    }
                    if hi.is_some_and(|h| lo > h) {
                        return err(
                            ErrorCode::P005,
                            start,
                            "minimum repeat is greater than maximum",
                        );
                    }
                    (lo, hi)
                }
                None => return Ok(None),
            },
            _ => return Ok(None),
        };
        Ok(Some(q))
    }

    /// Returns the node (None when the construct vanishes, like a comment or
    /// global flags) and whether a quantifier may follow it.
    fn atom(&mut self) -> R<(Option<Node>, bool)> {
        let start = self.pos;
        let Some(c) = self.peek() else {
            return Ok((None, false));
        };
        match c {
            '(' => self.group(),
            '[' => Ok((Some(self.class()?), true)),
            '.' => {
                self.pos += 1;
                Ok((Some(mk(NodeKind::Any, start, self.pos)), true))
            }
            '^' | '$' => {
                self.pos += 1;
                let a = if c == '^' {
                    Assertion::LineStart
                } else {
                    Assertion::LineEnd
                };
                Ok((Some(mk(NodeKind::Assert(a), start, self.pos)), false))
            }
            '\\' => {
                let esc = self.escape(false)?;
                let (kind, q) = match esc {
                    Esc::Char(c) => (NodeKind::Literal(c), true),
                    Esc::Short(s) => (
                        NodeKind::Class(Class {
                            negated: false,
                            items: vec![ClassItem::Shorthand(s)],
                        }),
                        true,
                    ),
                    Esc::Prop(p) => (
                        NodeKind::Class(Class {
                            negated: false,
                            items: vec![ClassItem::Property(p)],
                        }),
                        true,
                    ),
                    Esc::Assert(a) => (NodeKind::Assert(a), false),
                };
                Ok((Some(mk(kind, start, self.pos)), q))
            }
            '*' | '+' | '?' => err(ErrorCode::P005, start, "nothing to repeat"),
            '{' => {
                if self.braces()?.is_some() {
                    return err(ErrorCode::P005, start, "nothing to repeat");
                }
                if self.es_unicode() {
                    return err(ErrorCode::P001, start, "lone '{' in Unicode mode");
                }
                self.pos += 1;
                Ok((
                    Some(mk(NodeKind::Literal('{' as u32), start, self.pos)),
                    true,
                ))
            }
            '}' | ']' if self.es_unicode() => err(
                ErrorCode::P001,
                start,
                "lone bracket in Unicode mode; escape it",
            ),
            _ => {
                self.pos += 1;
                Ok((Some(mk(NodeKind::Literal(c as u32), start, self.pos)), true))
            }
        }
    }

    // ---------------------------------------------------------------- groups

    fn group_body(&mut self, open: usize) -> R<Node> {
        let n = self.alt()?;
        if !self.eat(')') {
            return err(ErrorCode::P007, open, "unclosed group");
        }
        Ok(n)
    }

    fn group(&mut self) -> R<(Option<Node>, bool)> {
        let open = self.pos;
        self.pos += 1;
        if self.eat('?') {
            return self.special_group(open);
        }
        let idx = self.next_capture;
        self.next_capture += 1;
        let body = self.group_body(open)?;
        let kind = NodeKind::Group {
            capture: Some(idx),
            name: None,
            node: Box::new(body),
        };
        Ok((Some(mk(kind, open, self.pos)), true))
    }

    fn plain_group(
        &mut self,
        open: usize,
        capture: Option<u32>,
        name: Option<String>,
    ) -> R<(Option<Node>, bool)> {
        let body = self.group_body(open)?;
        let kind = NodeKind::Group {
            capture,
            name,
            node: Box::new(body),
        };
        Ok((Some(mk(kind, open, self.pos)), true))
    }

    fn look(&mut self, open: usize, ahead: bool, negate: bool) -> R<(Option<Node>, bool)> {
        let body = self.group_body(open)?;
        let kind = NodeKind::Look {
            ahead,
            negate,
            node: Box::new(body),
        };
        // ECMAScript: lookbehind never, lookahead only outside Unicode mode, is quantifiable.
        let q = !(self.d == Dialect::Ecma && (!ahead || self.flags.u));
        Ok((Some(mk(kind, open, self.pos)), q))
    }

    fn named(&mut self, open: usize) -> R<(Option<Node>, bool)> {
        let name_start = self.pos;
        let mut name = String::new();
        loop {
            match self.peek() {
                Some('>') => break,
                Some(c) => {
                    name.push(c);
                    self.pos += 1;
                }
                None => return err(ErrorCode::P009, name_start, "unterminated group name"),
            }
        }
        let ok_first = |c: char| c.is_alphabetic() || c == '_' || (!self.is_py() && c == '$');
        let ok_rest = |c: char| c.is_alphanumeric() || c == '_' || (!self.is_py() && c == '$');
        let valid = name.chars().next().is_some_and(ok_first) && name.chars().all(ok_rest);
        if !valid {
            return err(ErrorCode::P009, name_start, "invalid group name");
        }
        if self.names.contains(&name) {
            return err(ErrorCode::P009, name_start, "duplicate group name");
        }
        self.pos += 1; // '>'
        let idx = self.next_capture;
        self.next_capture += 1;
        self.names.push(name.clone());
        self.plain_group(open, Some(idx), Some(name))
    }

    fn special_group(&mut self, open: usize) -> R<(Option<Node>, bool)> {
        let Some(c) = self.peek() else {
            return err(ErrorCode::P007, open, "unclosed group");
        };
        self.pos += 1;
        match (self.d, c) {
            (_, ':') => self.plain_group(open, None, None),
            (_, '=') => self.look(open, true, false),
            (_, '!') => self.look(open, true, true),
            (_, '<') => match self.peek() {
                Some('=') => {
                    self.pos += 1;
                    self.look(open, false, false)
                }
                Some('!') => {
                    self.pos += 1;
                    self.look(open, false, true)
                }
                _ if self.d == Dialect::Ecma => self.named(open),
                _ => err(
                    ErrorCode::P001,
                    open,
                    "unknown group extension '(?<'; Python names use (?P<name>...)",
                ),
            },
            (Dialect::Python, 'P') => match self.peek() {
                Some('<') => {
                    self.pos += 1;
                    self.named(open)
                }
                Some('=') => err(ErrorCode::U001, open, "named backreference (?P=name)"),
                _ => err(ErrorCode::P001, open, "unknown group extension '(?P'"),
            },
            (Dialect::Python, '#') => {
                while let Some(c) = self.peek() {
                    self.pos += 1;
                    if c == ')' {
                        return Ok((None, false));
                    }
                }
                err(ErrorCode::P007, open, "unterminated comment")
            }
            (Dialect::Python, '>') => err(
                ErrorCode::U004,
                open,
                "atomic group changes matching semantics",
            ),
            (Dialect::Python, '(') => err(ErrorCode::U003, open, "conditional group"),
            (Dialect::Python, _) => {
                self.pos -= 1;
                self.py_flags(open)
            }
            _ => err(
                ErrorCode::P001,
                open,
                "unrecognised group syntax after '(?'",
            ),
        }
    }

    /// Python `(?aimsux-imsx)` and `(?aimsux-imsx:...)`.
    fn py_flags(&mut self, open: usize) -> R<(Option<Node>, bool)> {
        let (mut on, mut off) = (Flags::none(), Flags::none());
        let mut turning_off = false;
        let mut any = false;
        loop {
            let Some(c) = self.peek() else {
                return err(ErrorCode::P007, open, "unclosed group");
            };
            match c {
                '-' if !turning_off => {
                    turning_off = true;
                    any = false;
                    self.pos += 1;
                    continue;
                }
                'a' | 'i' | 'm' | 's' | 'u' | 'x' => {
                    if turning_off && matches!(c, 'a' | 'u') {
                        return err(
                            ErrorCode::P003,
                            self.pos,
                            "flags 'a' and 'u' cannot be turned off",
                        );
                    }
                    let target = if turning_off { &mut off } else { &mut on };
                    match c {
                        'a' => target.a = true,
                        'i' => target.i = true,
                        'm' => target.m = true,
                        's' => target.s = true,
                        'u' => target.u = true,
                        _ => target.x = true,
                    }
                }
                'L' => {
                    return err(
                        ErrorCode::P003,
                        self.pos,
                        "flag 'L' cannot be used with str patterns",
                    )
                }
                ')' | ':' => break,
                _ => return err(ErrorCode::P001, open, "unknown flag in inline group"),
            }
            any = true;
            self.pos += 1;
        }
        if turning_off && !any {
            return err(ErrorCode::P001, self.pos, "missing flag after '-'");
        }
        if !turning_off && !any {
            return err(ErrorCode::P001, open, "missing inline flags");
        }
        if on.a && on.u {
            return err(ErrorCode::P003, open, "flags 'a' and 'u' are incompatible");
        }
        if self.eat(')') {
            if turning_off {
                return err(ErrorCode::P001, open, "global flags cannot be turned off");
            }
            if self.seen_content || self.depth > 1 {
                return err(
                    ErrorCode::P001,
                    open,
                    "global flags not at the start of the expression",
                );
            }
            self.flags = self.flags.union(on);
            return Ok((None, false));
        }
        self.pos += 1; // ':'
        let saved = self.flags;
        self.flags = saved.union(on).minus(off);
        let body = self.group_body(open);
        self.flags = saved;
        let kind = NodeKind::FlagGroup {
            delta: FlagDelta { on, off },
            node: Box::new(body?),
        };
        Ok((Some(mk(kind, open, self.pos)), true))
    }

    // --------------------------------------------------------------- classes

    fn class_atom(&mut self) -> R<ClassAtom> {
        match self.peek() {
            Some('\\') => Ok(match self.escape(true)? {
                Esc::Char(c) => ClassAtom::Ch(c),
                Esc::Short(s) => ClassAtom::Sh(s),
                Esc::Prop(p) => ClassAtom::Prop(p),
                // `escape(true)` never returns assertions; keep the match total anyway.
                Esc::Assert(_) => return err(ErrorCode::X001, self.pos, "assertion inside class"),
            }),
            Some(c) => {
                self.pos += 1;
                Ok(ClassAtom::Ch(c as u32))
            }
            None => err(ErrorCode::P007, self.pos, "unterminated character class"),
        }
    }

    fn class(&mut self) -> R<Node> {
        let open = self.pos;
        self.pos += 1;
        let negated = self.eat('^');
        let mut items = Vec::new();
        let mut first = true;
        loop {
            let Some(c) = self.peek() else {
                return err(ErrorCode::P007, open, "unterminated character class");
            };
            if c == ']' && !(first && self.is_py()) {
                self.pos += 1;
                break;
            }
            first = false;
            let a = self.class_atom()?;
            if self.peek() == Some('-') && self.peek_at(1).is_some_and(|n| n != ']') {
                let dash = self.pos;
                self.pos += 1;
                let b = self.class_atom()?;
                match (a, b) {
                    (ClassAtom::Ch(x), ClassAtom::Ch(y)) => {
                        if x > y {
                            return err(ErrorCode::P006, dash, "range end precedes range start");
                        }
                        items.push(ClassItem::Range(x, y));
                    }
                    (a, b) => {
                        // Annex B: outside Unicode mode ECMAScript reads `a-\d` as three members.
                        if self.d != Dialect::Ecma || self.flags.u {
                            return err(
                                ErrorCode::P006,
                                dash,
                                "a class escape cannot be a range endpoint",
                            );
                        }
                        for x in [a, ClassAtom::Ch('-' as u32), b] {
                            items.push(x.item());
                        }
                    }
                }
            } else {
                items.push(a.item());
            }
        }
        Ok(mk(
            NodeKind::Class(Class { negated, items }),
            open,
            self.pos,
        ))
    }

    // --------------------------------------------------------------- escapes

    fn hex(&mut self, n: usize) -> Option<u32> {
        let mut v = 0u32;
        for k in 0..n {
            v = v * 16 + self.peek_at(k)?.to_digit(16)?;
        }
        self.pos += n;
        Some(v)
    }

    fn octal(&mut self, first: u32, max_extra: usize) -> u32 {
        let mut v = first;
        for _ in 0..max_extra {
            match self.peek().and_then(|c| c.to_digit(8)) {
                Some(d) => {
                    v = v * 8 + d;
                    self.pos += 1;
                }
                None => break,
            }
        }
        v
    }

    fn escape(&mut self, in_class: bool) -> R<Esc> {
        let bs = self.pos;
        self.pos += 1;
        let Some(c) = self.peek() else {
            return err(ErrorCode::P004, bs, "pattern ends with a backslash");
        };
        self.pos += 1;
        if let Some(s) = shorthand(c) {
            return Ok(Esc::Short(s));
        }
        match self.d {
            Dialect::Ecma => self.esc_ecma(c, bs, in_class),
            _ => self.esc_py(c, bs, in_class),
        }
    }

    fn esc_ecma(&mut self, c: char, bs: usize, in_class: bool) -> R<Esc> {
        let u = self.flags.u;
        Ok(Esc::Char(match c {
            'b' if in_class => 8,
            'b' => return Ok(Esc::Assert(Assertion::WordBoundary)),
            'B' if in_class && u => {
                return err(ErrorCode::P004, bs, "\\B is not allowed in a class")
            }
            'B' if in_class => 'B' as u32,
            'B' => return Ok(Esc::Assert(Assertion::NotWordBoundary)),
            'f' => 12,
            'n' => 10,
            'r' => 13,
            't' => 9,
            'v' => 11,
            '0' if !self.peek().is_some_and(|n| n.is_ascii_digit()) => 0,
            '0'..='9' => return self.es_digits(c, bs, in_class),
            'k' => {
                if in_class && !u {
                    'k' as u32
                } else if u || self.has_named {
                    if self.peek() == Some('<') && !in_class {
                        return err(ErrorCode::U001, bs, "named backreference \\k<name>");
                    }
                    return err(ErrorCode::P004, bs, "invalid named reference");
                } else {
                    'k' as u32
                }
            }
            'c' => match self.peek() {
                Some(l) if l.is_ascii_alphabetic() => {
                    self.pos += 1;
                    l as u32 % 32
                }
                _ if u => return err(ErrorCode::P004, bs, "invalid control escape"),
                _ => {
                    // Annex B: a lone `\c` is a literal backslash; `c` is read again.
                    self.pos -= 1;
                    '\\' as u32
                }
            },
            'x' => match self.hex(2) {
                Some(v) => v,
                None if u => return err(ErrorCode::P004, bs, "\\x needs two hex digits"),
                None => 'x' as u32,
            },
            'u' => return self.es_unicode_escape(bs),
            'p' | 'P' if u => return self.es_property(c == 'P', bs),
            '-' if in_class && u => '-' as u32,
            _ if u => {
                if "^$\\.*+?()[]{}|/".contains(c) {
                    c as u32
                } else {
                    return err(
                        ErrorCode::P004,
                        bs,
                        "invalid identity escape in Unicode mode",
                    );
                }
            }
            _ => c as u32,
        }))
    }

    /// ECMAScript `\p{Name}` / `\p{Name=Value}` (Unicode mode only): exact,
    /// case-sensitive names from the Unicode property alias files.
    fn es_property(&mut self, negated: bool, bs: usize) -> R<Esc> {
        if self.peek() != Some('{') {
            return err(
                ErrorCode::P004,
                bs,
                "\\p must be followed by {Name} in Unicode mode",
            );
        }
        let start = self.pos + 1;
        let mut i = start;
        while self
            .chars
            .get(i)
            .is_some_and(|c| c.is_ascii_alphanumeric() || *c == '_' || *c == '=')
        {
            i += 1;
        }
        if self.chars.get(i) != Some(&'}') {
            return err(ErrorCode::P004, bs, "malformed \\p{...} escape");
        }
        let body: String = self.chars[start..i].iter().collect();
        self.pos = i + 1;
        let unknown = |what: &str| {
            let hint = uni::suggest(what);
            let tail = if hint.is_empty() {
                String::new()
            } else {
                format!("; did you mean: {}", hint.join(", "))
            };
            PErr::new(
                ErrorCode::P008,
                bs,
                &format!("unknown Unicode property or value '{what}'{tail}"),
            )
        };
        let (kind, name) = match body.split_once('=') {
            None => match uni::gc_canonical(&body) {
                Some(n) => (PropKind::GeneralCategory, n),
                None => match uni::binary_canonical(&body) {
                    Some(n) => (PropKind::Binary, n),
                    None => return Err(unknown(&body)),
                },
            },
            Some(("General_Category" | "gc", v)) => (
                PropKind::GeneralCategory,
                uni::gc_canonical(v).ok_or_else(|| unknown(v))?,
            ),
            Some(("Script" | "sc", v)) => (
                PropKind::Script,
                uni::script_canonical(v).ok_or_else(|| unknown(v))?,
            ),
            Some(("Script_Extensions" | "scx", v)) => (
                PropKind::ScriptExtensions,
                uni::script_canonical(v).ok_or_else(|| unknown(v))?,
            ),
            Some((n, _)) => return Err(unknown(n)),
        };
        Ok(Esc::Prop(PropertyRef {
            negated,
            kind,
            name,
            exact: false,
        }))
    }

    fn es_digits(&mut self, c: char, bs: usize, in_class: bool) -> R<Esc> {
        let u = self.flags.u;
        let first = c.to_digit(10).unwrap_or(0);
        if u {
            if c == '0' || in_class {
                return err(
                    ErrorCode::P004,
                    bs,
                    "invalid decimal escape in Unicode mode",
                );
            }
            let (n, _) = self.digits(self.pos - 1);
            return if n.is_some_and(|n| n <= u64::from(self.total_groups)) {
                err(ErrorCode::U001, bs, "backreference")
            } else {
                err(
                    ErrorCode::P004,
                    bs,
                    "reference to a group that does not exist",
                )
            };
        }
        if !in_class && c != '0' {
            let (n, end) = self.digits(self.pos - 1);
            if n.is_some_and(|n| n <= u64::from(self.total_groups)) {
                self.pos = end;
                return err(ErrorCode::U001, bs, "backreference");
            }
        }
        if first >= 8 {
            return Ok(Esc::Char(c as u32));
        }
        let extra = if first <= 3 { 2 } else { 1 };
        Ok(Esc::Char(self.octal(first, extra)))
    }

    fn es_unicode_escape(&mut self, bs: usize) -> R<Esc> {
        let u = self.flags.u;
        if u && self.peek() == Some('{') {
            let mut i = self.pos + 1;
            let mut v: u32 = 0;
            let mut n = 0;
            while let Some(d) = self.chars.get(i).and_then(|c| c.to_digit(16)) {
                v = v.saturating_mul(16).saturating_add(d);
                i += 1;
                n += 1;
            }
            if n == 0 || self.chars.get(i) != Some(&'}') || v > 0x10FFFF {
                return err(ErrorCode::P004, bs, "invalid \\u{...} escape");
            }
            self.pos = i + 1;
            return Ok(Esc::Char(v));
        }
        match self.hex(4) {
            Some(hi) if u && (0xD800..0xDC00).contains(&hi) => {
                // A 😀 pair denotes one code point in Unicode mode.
                if self.peek() == Some('\\') && self.peek_at(1) == Some('u') {
                    let save = self.pos;
                    self.pos += 2;
                    if let Some(lo) = self.hex(4) {
                        if (0xDC00..0xE000).contains(&lo) {
                            return Ok(Esc::Char(0x10000 + ((hi - 0xD800) << 10) + (lo - 0xDC00)));
                        }
                    }
                    self.pos = save;
                }
                Ok(Esc::Char(hi))
            }
            Some(v) => Ok(Esc::Char(v)),
            None if u => err(ErrorCode::P004, bs, "\\u needs four hex digits"),
            None => Ok(Esc::Char('u' as u32)),
        }
    }

    fn esc_py(&mut self, c: char, bs: usize, in_class: bool) -> R<Esc> {
        Ok(Esc::Char(match c {
            'b' if in_class => 8,
            'b' => return Ok(Esc::Assert(Assertion::WordBoundary)),
            'B' | 'A' | 'Z' if in_class => {
                return err(ErrorCode::P004, bs, "assertion escape inside a class")
            }
            'B' => return Ok(Esc::Assert(Assertion::NotWordBoundary)),
            'A' => return Ok(Esc::Assert(Assertion::TextStart)),
            'Z' => return Ok(Esc::Assert(Assertion::TextEnd)),
            'a' => 7,
            'f' => 12,
            'n' => 10,
            'r' => 13,
            't' => 9,
            'v' => 11,
            'x' => self
                .hex(2)
                .ok_or_else(|| PErr::new(ErrorCode::P004, bs, "\\x needs two hex digits"))?,
            'u' => self
                .hex(4)
                .ok_or_else(|| PErr::new(ErrorCode::P004, bs, "\\u needs four hex digits"))?,
            'U' => match self.hex(8) {
                Some(v) if v <= 0x10FFFF => v,
                _ => {
                    return err(
                        ErrorCode::P004,
                        bs,
                        "\\U needs eight hex digits up to 10FFFF",
                    )
                }
            },
            'N' => {
                return err(
                    ErrorCode::U007,
                    bs,
                    "\\N{name} escapes are not yet supported",
                )
            }
            '0' => self.octal(0, 2),
            '1'..='9' => return self.py_digits(c, bs, in_class),
            _ if c.is_ascii_alphabetic() => {
                return err(ErrorCode::P004, bs, "unknown escape of an ASCII letter")
            }
            _ => c as u32,
        }))
    }

    fn py_digits(&mut self, c: char, bs: usize, in_class: bool) -> R<Esc> {
        let first = c.to_digit(10).unwrap_or(0);
        let is_octal3 = first < 8
            && self.peek().is_some_and(|d| d.is_digit(8))
            && self.peek_at(1).is_some_and(|d| d.is_digit(8));
        if in_class || is_octal3 {
            if first >= 8 {
                return err(ErrorCode::P004, bs, "bad escape");
            }
            let v = self.octal(first, 2);
            if v > 0o377 {
                return err(ErrorCode::P004, bs, "octal escape value outside 0-0o377");
            }
            return Ok(Esc::Char(v));
        }
        // Python reads at most two digits for a group reference.
        let second = self.peek().and_then(|d| d.to_digit(10));
        let n = u64::from(first) * if second.is_some() { 10 } else { 1 }
            + u64::from(second.unwrap_or(0));
        let end = self.pos + usize::from(second.is_some());
        if n <= u64::from(self.total_groups) {
            self.pos = end;
            err(ErrorCode::U001, bs, "backreference")
        } else {
            err(
                ErrorCode::P004,
                bs,
                "reference to a group that does not exist",
            )
        }
    }
}