rexact-core 0.2.0

//! Lowering from the syntax tree to terms.
//!
//! Contract: produces a term whose language is exactly the pattern's language
//! under the dialect's rules, or fails. Anything not yet modelled exactly is
//! rejected with `RX-U007` (RULE-05): anchors and lookaround (M6) and any
//! character the chosen alphabet cannot represent. Counted repetition is
//! expanded under a cost limit (`RX-L004`): `cost` is the number of leaf
//! symbols after expansion.
//!
//! Dialect rules live in small functions (`shorthand`, `case_model`, `any`)
//! and are never unified across dialects (RULE-10).

use crate::alphabet::Alphabet;
use crate::casefold::{CaseFold, CaseModel};
use crate::charset::CharSet;
use crate::limits::Budget;
use crate::resolved::{RKind, RNode};
use crate::term::{AssertKind, TermId, TermStore};
use rexact_syntax::ast::{
    Assertion, Class, ClassExpr, ClassItem, Node, NodeKind, PropKind, PropertyRef, SetOp, Shorthand,
};
use rexact_syntax::error::{ErrorCode, RexactError};
use rexact_syntax::locate::locate;
use rexact_syntax::{Dialect, Flags, Pattern};
use rexact_unicode as uni;

pub(crate) struct Lower<'a> {
    pub store: &'a mut TermStore,
    pub alphabet: Alphabet,
    pub dialect: Dialect,
    pub chars: Vec<char>,
    pub budget: &'a mut Budget,
}

type R = Result<(TermId, u64), RexactError>;

fn ascii_space() -> CharSet {
    CharSet::from_ranges([(9, 13), (32, 32)])
}

/// ECMAScript WhiteSpace and LineTerminator (ECMA-262 12.2, 12.3).
fn es_space() -> CharSet {
    CharSet::from_ranges([
        (9, 13),
        (32, 32),
        (0xA0, 0xA0),
        (0x1680, 0x1680),
        (0x2000, 0x200A),
        (0x2028, 0x2029),
        (0x202F, 0x202F),
        (0x205F, 0x205F),
        (0x3000, 0x3000),
        (0xFEFF, 0xFEFF),
    ])
}

fn ascii_word() -> CharSet {
    CharSet::from_ranges([(0x30, 0x39), (0x41, 0x5A), (0x5F, 0x5F), (0x61, 0x7A)])
}

fn ranges(r: Vec<(u32, u32)>) -> CharSet {
    CharSet::from_ranges(r)
}

impl Lower<'_> {
    fn fail(&self, code: ErrorCode, n: &Node, why: &str) -> RexactError {
        let mut e = RexactError::new(code);
        e.detail = Some(why.to_string());
        e.position = Some(locate(&self.chars, n.span.start));
        e
    }

    pub fn pattern(&mut self, p: &Pattern) -> R {
        self.lower(&p.ast, p.flags)
    }

    /// Fit a set to the alphabet: surrogates are dropped from the Unicode
    /// universe; any other member outside the universe cannot be represented.
    fn fit(&self, set: CharSet, n: &Node) -> Result<CharSet, RexactError> {
        let fitted = set.intersect(self.store.universe());
        // PCRE2 in byte mode applies Unicode properties to the byte values 0-255.
        let pcre_bytes = self.dialect == Dialect::Pcre2 && self.alphabet == Alphabet::Bytes;
        if self.alphabet != Alphabet::Unicode && !pcre_bytes && fitted != set {
            return Err(self.fail(
                ErrorCode::U007,
                n,
                "a class member is not representable in the chosen alphabet mode",
            ));
        }
        Ok(fitted)
    }

    fn case_model(&self, f: Flags) -> CaseModel {
        match self.dialect {
            Dialect::Ecma if f.u => CaseModel::SimpleFold,
            Dialect::Ecma => CaseModel::EsLegacy,
            Dialect::Python if f.a => CaseModel::PythonAscii,
            Dialect::Python => CaseModel::Python,
            // Rust with Unicode mode off folds ASCII letters only.
            Dialect::Rust if !f.u => CaseModel::PythonAscii,
            // PCRE2 outside UTF mode folds with the C-locale tables: ASCII only.
            Dialect::Pcre2 | Dialect::Java if !f.u => CaseModel::PythonAscii,
            _ => CaseModel::SimpleFold,
        }
    }

    fn lower(&mut self, n: &Node, f: Flags) -> R {
        match &n.kind {
            NodeKind::Empty => Ok((self.store.epsilon(), 0)),
            NodeKind::Literal(c) => self.literal(*c, n, f),
            NodeKind::Any => {
                let u = self.store.universe().clone();
                let set = if f.s {
                    u
                } else if matches!(self.dialect, Dialect::Ecma | Dialect::Java) {
                    u.difference(&self.line_set())
                } else {
                    u.difference(&CharSet::single(10))
                };
                Ok((self.store.class(&set), 1))
            }
            NodeKind::Class(c) => self.class(c, n, f),
            NodeKind::ClassSet(e) => {
                let set = self.eval_class_expr(e, n, f)?;
                Ok((self.store.class(&set), 1))
            }
            NodeKind::Concat(v) => {
                let (mut ids, mut cost) = (Vec::with_capacity(v.len()), 0u64);
                for x in v {
                    let (t, c) = self.lower(x, f)?;
                    ids.push(t);
                    cost = cost.saturating_add(c);
                }
                Ok((self.store.concat_all(&ids), cost))
            }
            NodeKind::Alt(v) => {
                let (mut ids, mut cost) = (Vec::with_capacity(v.len()), 0u64);
                for x in v {
                    let (t, c) = self.lower(x, f)?;
                    ids.push(t);
                    cost = cost.saturating_add(c);
                }
                Ok((self.store.union(&ids), cost))
            }
            NodeKind::Group { node, .. } => self.lower(node, f),
            NodeKind::FlagGroup { delta, node } => {
                self.lower(node, f.union(delta.on).minus(delta.off))
            }
            NodeKind::Repeat { node, min, max, .. } => self.repeat(n, node, *min, *max, f),
            NodeKind::Assert(a) => self.assertion(*a, n, f),
            NodeKind::Look {
                ahead,
                negate,
                node,
            } => {
                let (body, cost) = self.lower(node, f)?;
                let t = if *ahead {
                    self.store.look_ahead(*negate, body)
                } else {
                    self.store.look_behind(*negate, body).ok_or_else(|| {
                        self.fail(
                            ErrorCode::U005,
                            n,
                            "lookbehind bodies must not contain anchors or lookaround, and at most 16 distinct lookbehinds are supported",
                        )
                    })?
                };
                Ok((t, cost))
            }
        }
    }

    /// Characters that act as line terminators for `^` / `$` in multiline mode.
    fn line_set(&self) -> CharSet {
        if self.dialect == Dialect::Java {
            // Java line terminators: LF, CR, U+0085, U+2028, U+2029 (and the pair CR LF).
            CharSet::from_ranges([(10, 10), (13, 13), (0x85, 0x85), (0x2028, 0x2029)])
        } else if self.dialect == Dialect::Ecma {
            CharSet::from_ranges([(10, 10), (13, 13), (0x2028, 0x2029)])
        } else {
            CharSet::single(10)
        }
    }

    fn aux_fail(&self, n: &Node) -> RexactError {
        self.fail(
            ErrorCode::U005,
            n,
            "too many distinct word or line definitions in one analysis",
        )
    }

    /// `$` outside multiline mode in Python and PCRE2: the end, or just before
    /// a final newline, that is a lookahead for an optional newline and then the end.
    fn dollar_before_final_newline(&mut self, n: &Node) -> Result<TermId, RexactError> {
        let nl = if self.dialect == Dialect::Java {
            // A final terminator: the pair CR LF or any single terminator.
            let any = self.store.class(&self.line_set());
            let cr = self.store.class(&CharSet::single(13));
            let lf = self.store.class(&CharSet::single(10));
            let pair = self.store.concat_all(&[cr, lf]);
            self.store.union(&[pair, any])
        } else {
            self.store.class(&CharSet::single(10))
        };
        let opt_nl = self.store.opt(nl);
        let end = self
            .store
            .assertion(AssertKind::TextEnd, None, None)
            .ok_or_else(|| self.aux_fail(n))?;
        let body = self.store.concat_all(&[opt_nl, end]);
        Ok(self.store.look_ahead(false, body))
    }

    fn assertion(&mut self, a: Assertion, n: &Node, f: Flags) -> R {
        let aux = |s: &Self| s.aux_fail(n);
        let word = |s: &Self| -> Result<CharSet, RexactError> {
            s.fit(s.shorthand(Shorthand::Word, f), n)
        };
        let line = self.line_set();
        let multiline_dollar_like = matches!(
            self.dialect,
            Dialect::Python | Dialect::Pcre2 | Dialect::Java
        );
        let t = match a {
            Assertion::TextStart => self
                .store
                .assertion(AssertKind::TextStart, None, None)
                .ok_or_else(|| aux(self))?,
            Assertion::TextEnd => self
                .store
                .assertion(AssertKind::TextEnd, None, None)
                .ok_or_else(|| aux(self))?,
            Assertion::LineStart if !f.m => self
                .store
                .assertion(AssertKind::TextStart, None, None)
                .ok_or_else(|| aux(self))?,
            Assertion::LineStart => {
                let ls = self
                    .store
                    .assertion(AssertKind::LineStart, None, Some(&line))
                    .ok_or_else(|| aux(self))?;
                if self.dialect == Dialect::Java {
                    // Java: never at the very end of the input, not even on empty input.
                    let end = self
                        .store
                        .assertion(AssertKind::TextEnd, None, None)
                        .ok_or_else(|| aux(self))?;
                    let not_end = self.store.not(end);
                    self.store.inter(&[ls, not_end])
                } else if self.dialect == Dialect::Pcre2 {
                    // PCRE2: not after a newline that ends the subject.
                    let start = self
                        .store
                        .assertion(AssertKind::TextStart, None, None)
                        .ok_or_else(|| aux(self))?;
                    let end = self
                        .store
                        .assertion(AssertKind::TextEnd, None, None)
                        .ok_or_else(|| aux(self))?;
                    let not_end = self.store.not(end);
                    let inner = self.store.inter(&[ls, not_end]);
                    self.store.union(&[start, inner])
                } else {
                    ls
                }
            }
            Assertion::LineEnd if f.m => self
                .store
                .assertion(AssertKind::LineEnd, None, Some(&line))
                .ok_or_else(|| aux(self))?,
            Assertion::LineEnd if multiline_dollar_like => self.dollar_before_final_newline(n)?,
            Assertion::LineEnd => self
                .store
                .assertion(AssertKind::TextEnd, None, None)
                .ok_or_else(|| aux(self))?,
            Assertion::TextEndOptionalNewline => self.dollar_before_final_newline(n)?,
            Assertion::WordBoundary => self
                .store
                .assertion(AssertKind::WordBoundary, Some(&word(self)?), None)
                .ok_or_else(|| aux(self))?,
            Assertion::NotWordBoundary => {
                let nwb = self
                    .store
                    .assertion(AssertKind::NotWordBoundary, Some(&word(self)?), None)
                    .ok_or_else(|| aux(self))?;
                if self.dialect == Dialect::Python {
                    // Python (3.11) never matches \B on an empty input.
                    let st = self
                        .store
                        .assertion(AssertKind::TextStart, None, None)
                        .ok_or_else(|| aux(self))?;
                    let en = self
                        .store
                        .assertion(AssertKind::TextEnd, None, None)
                        .ok_or_else(|| aux(self))?;
                    let both = self.store.concat_all(&[st, en]);
                    let not_empty = self.store.not(both);
                    self.store.inter(&[nwb, not_empty])
                } else {
                    nwb
                }
            }
            Assertion::WordStart => self
                .store
                .assertion(AssertKind::WordStart, Some(&word(self)?), None)
                .ok_or_else(|| aux(self))?,
            Assertion::WordEnd => self
                .store
                .assertion(AssertKind::WordEnd, Some(&word(self)?), None)
                .ok_or_else(|| aux(self))?,
        };
        Ok((t, 0))
    }

    fn literal(&mut self, c: u32, n: &Node, f: Flags) -> R {
        // ECMAScript without `u` works on UTF-16 units: an astral literal is two
        // surrogate units, which have no case.
        let units_only = self.alphabet == Alphabet::Utf16 && c > 0xFFFF;
        if f.i && !units_only {
            let fold = CaseFold::new(self.case_model(f));
            let single = CharSet::single(c);
            let closed = match self.dialect {
                Dialect::Python => fold.close_python_class(&single, &CharSet::empty()),
                _ => fold.close(&single),
            };
            if closed != single {
                let set = self.fit(closed, n)?;
                return Ok((self.store.class(&set), 1));
            }
        }
        self.symbol(c, n)
    }

    fn symbol(&mut self, c: u32, n: &Node) -> R {
        let surrogate = (0xD800..0xE000).contains(&c);
        match self.alphabet {
            Alphabet::Unicode if surrogate => Err(self.fail(
                ErrorCode::U007,
                n,
                "lone surrogate cannot be a Unicode scalar value",
            )),
            Alphabet::Bytes if c >= 0x80 && !(self.dialect == Dialect::Pcre2 && c <= 0xFF) => {
                Err(self.fail(
                    ErrorCode::U007,
                    n,
                    "non-ASCII literal in byte mode is not yet supported",
                ))
            }
            Alphabet::Utf16 if c > 0xFFFF => {
                let v = c - 0x10000;
                let hi = self.store.class(&CharSet::single(0xD800 + (v >> 10)));
                let lo = self.store.class(&CharSet::single(0xDC00 + (v & 0x3FF)));
                Ok((self.store.concat(hi, lo), 2))
            }
            _ => Ok((self.store.class(&CharSet::single(c)), 1)),
        }
    }

    /// Does `\d \w \s` mean the Unicode sets in this dialect and mode?
    fn unicode_classes(&self, f: Flags) -> bool {
        match self.dialect {
            Dialect::Python => !f.a,
            Dialect::Rust => f.u,
            Dialect::Pcre2 | Dialect::Java => f.u,
            Dialect::Ecma | Dialect::Go => false,
        }
    }

    /// The positive set of a shorthand letter.
    fn positive(&self, s: Shorthand, f: Flags) -> CharSet {
        let uni_classes = self.unicode_classes(f);
        match s {
            Shorthand::Digit | Shorthand::NotDigit => {
                if !uni_classes {
                    CharSet::range(0x30, 0x39)
                } else if self.dialect == Dialect::Python {
                    ranges(uni::py_digit())
                } else {
                    ranges(uni::general_category("Nd").unwrap_or_default())
                }
            }
            Shorthand::Word | Shorthand::NotWord => {
                if !uni_classes {
                    ascii_word()
                } else if self.dialect == Dialect::Python {
                    ranges(uni::py_word())
                } else if self.dialect == Dialect::Pcre2 {
                    // PCRE2 UCP (10.43+): \p{L}, \p{N}, \p{Mn} and \p{Pc} (which holds the underscore).
                    let mut v = uni::general_category("L").unwrap_or_default();
                    for cat in ["N", "Mn", "Pc"] {
                        v.extend(uni::general_category(cat).unwrap_or_default());
                    }
                    ranges(v)
                } else {
                    // Rust: alphabetic, marks, decimal digits, connector punctuation, join control.
                    let parts = [
                        uni::binary("Alphabetic"),
                        uni::general_category("M"),
                        uni::general_category("Nd"),
                        uni::general_category("Pc"),
                        uni::binary("Join_Control"),
                    ];
                    ranges(parts.into_iter().flatten().flatten().collect())
                }
            }
            Shorthand::Space | Shorthand::NotSpace => {
                if self.dialect == Dialect::Ecma {
                    es_space()
                } else if !uni_classes {
                    match self.dialect {
                        // RE2 / Go: [\t\n\f\r ]; PCRE2 non-UCP adds vertical tab.
                        Dialect::Go => CharSet::from_ranges([(9, 10), (12, 13), (32, 32)]),
                        _ => ascii_space(),
                    }
                } else if self.dialect == Dialect::Python {
                    ranges(uni::py_space())
                } else {
                    ranges(uni::binary("White_Space").unwrap_or_default())
                }
            }
        }
    }

    fn shorthand(&self, s: Shorthand, f: Flags) -> CharSet {
        let mut base = self.positive(s, f);
        // ECMAScript /iu: \w and \W use WordCharacters, which adds characters
        // whose simple case folding is a basic word character (U+017F, U+212A).
        if self.dialect == Dialect::Ecma
            && f.u
            && f.i
            && matches!(s, Shorthand::Word | Shorthand::NotWord)
        {
            base = CaseFold::new(CaseModel::SimpleFold).close(&base);
        }
        match s {
            Shorthand::Digit | Shorthand::Word | Shorthand::Space => base,
            _ => self.store.universe().difference(&base),
        }
    }

    /// The positive member set of a property (negation is applied by the caller,
    /// because dialects disagree on whether it happens before or after case folding).
    fn property(&self, p: &PropertyRef, n: &Node) -> Result<CharSet, RexactError> {
        let members = match p.kind {
            PropKind::GeneralCategory => uni::general_category(p.name),
            PropKind::Script => uni::script(p.name, false),
            PropKind::ScriptExtensions => uni::script(p.name, true),
            PropKind::Binary => uni::binary(p.name),
        }
        .ok_or_else(|| self.fail(ErrorCode::X001, n, "validated property has no data"))?;
        self.fit(ranges(members), n)
    }

    /// The positive set of a list of class items, including case closure.
    fn items_set(&self, items: &[ClassItem], n: &Node, f: Flags) -> Result<CharSet, RexactError> {
        // Split members: literal characters/ranges versus category-like sets.
        let mut members = CharSet::empty();
        let mut categories = CharSet::empty();
        let mut finished = CharSet::empty();
        for item in items {
            match *item {
                ClassItem::Shorthand(s) => {
                    let set = self.shorthand(s, f);
                    categories = categories.union(&self.fit(set, n)?);
                }
                ClassItem::Property(p) => {
                    let pos = self.property(&p, n)?;
                    if self.dialect == Dialect::Ecma {
                        // ECMAScript: the complement is formed first; the class matcher folds afterwards.
                        let set = if p.negated {
                            self.store.universe().difference(&pos)
                        } else {
                            pos
                        };
                        categories = categories.union(&set);
                    } else {
                        // Go, Rust, PCRE2: fold the property, then negate.
                        let mut set = pos;
                        if f.i && self.dialect == Dialect::Pcre2 {
                            // PCRE2: caseless \p{Lu}, \p{Ll}, \p{Lt} match all cased letters.
                            let widen = !p.exact
                                && p.kind == PropKind::GeneralCategory
                                && matches!(p.name, "Lu" | "Ll" | "Lt");
                            if widen {
                                set = self.fit(
                                    ranges(uni::general_category("LC").unwrap_or_default()),
                                    n,
                                )?;
                            }
                        } else if f.i {
                            set = CaseFold::new(self.case_model(f)).close(&set);
                        }
                        if p.negated {
                            set = self.store.universe().difference(&set);
                        }
                        finished = finished.union(&set);
                    }
                }
                ClassItem::Range(lo, hi) => {
                    let ok = match self.alphabet {
                        Alphabet::Utf16 => hi <= 0xFFFF,
                        Alphabet::Bytes => {
                            hi < 0x80 || (self.dialect == Dialect::Pcre2 && hi <= 0xFF)
                        }
                        Alphabet::Unicode => !(0xD800..0xE000).contains(&lo) || hi >= 0xE000,
                    };
                    if !ok {
                        return Err(self.fail(
                            ErrorCode::U007,
                            n,
                            "class member not representable in the chosen alphabet mode",
                        ));
                    }
                    members = members.union(&CharSet::range(lo, hi));
                }
            }
        }
        let set = if f.i {
            let fold = CaseFold::new(self.case_model(f));
            if self.dialect == Dialect::Python {
                fold.close_python_class(&members, &categories)
            } else {
                fold.close(&members.union(&categories))
            }
        } else {
            members.union(&categories)
        };
        Ok(set.union(&finished).intersect(self.store.universe()))
    }

    fn eval_class_expr(&self, e: &ClassExpr, n: &Node, f: Flags) -> Result<CharSet, RexactError> {
        Ok(match e {
            ClassExpr::Items(items) => self.items_set(items, n, f)?,
            ClassExpr::Union(v) => {
                let mut acc = CharSet::empty();
                for x in v {
                    acc = acc.union(&self.eval_class_expr(x, n, f)?);
                }
                acc
            }
            ClassExpr::Bracket { negated, inner } => {
                let s = self.eval_class_expr(inner, n, f)?;
                if *negated {
                    self.store.universe().difference(&s)
                } else {
                    s
                }
            }
            ClassExpr::Op(op, a, b) => {
                let (x, y) = (
                    self.eval_class_expr(a, n, f)?,
                    self.eval_class_expr(b, n, f)?,
                );
                match op {
                    SetOp::Intersect => x.intersect(&y),
                    SetOp::Difference => x.difference(&y),
                    SetOp::SymmetricDifference => x.difference(&y).union(&y.difference(&x)),
                }
            }
        })
    }

    fn class(&mut self, c: &Class, n: &Node, f: Flags) -> R {
        let mut set = self.items_set(&c.items, n, f)?;
        if c.negated {
            set = self.store.universe().difference(&set);
        }
        Ok((self.store.class(&set), 1))
    }

    fn repeat(&mut self, n: &Node, body: &Node, min: u64, max: Option<u64>, f: Flags) -> R {
        let (x, cost) = self.lower(body, f)?;
        let cost = cost.max(1);
        let copies = max.unwrap_or(min).max(min);
        let total = cost.saturating_mul(copies.saturating_add(u64::from(max.is_none())));
        if let Err(code) = self.budget.check_repeat(total) {
            return Err(self.fail(code, n, "repetition expansion exceeds the limit"));
        }
        let mut parts = vec![x; min as usize];
        match max {
            None => parts.push(self.store.star(x)),
            Some(m) => {
                // x{n,m} = x^n (x (x (...)?)?)?  -- nested, so it stays linear in m.
                let mut acc = self.store.epsilon();
                for _ in 0..(m - min) {
                    let step = self.store.concat(x, acc);
                    acc = self.store.opt(step);
                }
                parts.push(acc);
            }
        }
        Ok((self.store.concat_all(&parts), total))
    }
}

// ------------------------------------------------------------------ resolve

/// Convert a term made only of classes, concatenation and union back to a tree
/// (leaf lowering can produce a two-class concatenation for astral characters
/// in UTF-16 mode).
fn term_to_rnode(store: &TermStore, t: TermId, span: (usize, usize)) -> Option<RNode> {
    use crate::term::TermKind;
    Some(RNode {
        kind: match store.kind(t) {
            TermKind::Class(s) => RKind::Set(s.clone()),
            TermKind::Epsilon => RKind::Empty,
            TermKind::Concat(a, b) => RKind::Cat(vec![
                term_to_rnode(store, *a, span)?,
                term_to_rnode(store, *b, span)?,
            ]),
            _ => return None,
        },
        span,
    })
}

impl Lower<'_> {
    /// Resolve a pattern to an [`RNode`] tree for backtracking analysis.
    pub fn resolve_pattern(&mut self, p: &Pattern) -> Result<RNode, RexactError> {
        self.resolve(&p.ast, p.flags)
    }

    fn resolve(&mut self, n: &Node, f: Flags) -> Result<RNode, RexactError> {
        let span = (n.span.start, n.span.end);
        let kind = match &n.kind {
            NodeKind::Empty => RKind::Empty,
            NodeKind::Literal(_) | NodeKind::Any | NodeKind::Class(_) | NodeKind::ClassSet(_) => {
                let (t, _) = self.lower(n, f)?;
                return term_to_rnode(self.store, t, span).ok_or_else(|| {
                    self.fail(ErrorCode::X001, n, "leaf did not lower to a character set")
                });
            }
            NodeKind::Concat(v) => RKind::Cat(
                v.iter()
                    .map(|x| self.resolve(x, f))
                    .collect::<Result<_, _>>()?,
            ),
            NodeKind::Alt(v) => RKind::Alt(
                v.iter()
                    .map(|x| self.resolve(x, f))
                    .collect::<Result<_, _>>()?,
            ),
            NodeKind::Group { node, .. } => return self.resolve(node, f),
            NodeKind::FlagGroup { delta, node } => {
                return self.resolve(node, f.union(delta.on).minus(delta.off))
            }
            NodeKind::Repeat {
                node,
                min,
                max,
                greedy,
            } => {
                let (_, cost) = self.lower(n, f)?; // enforces the repetition limit
                let _ = cost;
                RKind::Repeat {
                    node: Box::new(self.resolve(node, f)?),
                    min: *min,
                    max: *max,
                    greedy: *greedy,
                }
            }
            NodeKind::Assert(a)
                if matches!(a, Assertion::TextEndOptionalNewline)
                    || (matches!(a, Assertion::LineEnd)
                        && !f.m
                        && matches!(self.dialect, Dialect::Python | Dialect::Pcre2)) =>
            {
                // `$` / `\Z` that may precede one final newline: a lookahead for an optional
                // newline followed by the end of the text, so the simulator can run it on the remainder.
                let (end, _) = self.assertion(Assertion::TextEnd, n, f)?;
                let nl = self.store.class(&CharSet::single(10));
                let opt_nl = RNode {
                    kind: RKind::Repeat {
                        node: Box::new(RNode {
                            kind: RKind::Set(CharSet::single(10)),
                            span,
                        }),
                        min: 0,
                        max: Some(1),
                        greedy: true,
                    },
                    span,
                };
                let _ = nl;
                RKind::LookAhead {
                    neg: false,
                    node: Box::new(RNode {
                        kind: RKind::Cat(vec![
                            opt_nl,
                            RNode {
                                kind: RKind::Assert(end),
                                span,
                            },
                        ]),
                        span,
                    }),
                }
            }
            NodeKind::Assert(_) => {
                let (t, _) = self.lower(n, f)?;
                RKind::Assert(t)
            }
            NodeKind::Look {
                ahead,
                negate,
                node,
            } => {
                let body = Box::new(self.resolve(node, f)?);
                if *ahead {
                    RKind::LookAhead {
                        neg: *negate,
                        node: body,
                    }
                } else {
                    RKind::LookBehind {
                        neg: *negate,
                        node: body,
                    }
                }
            }
        };
        Ok(RNode { kind, span })
    }
}