Skip to main content

nodejs/
regexp.rs

1//! JavaScript `RegExp` on top of the [`fancy_regex`] crate.
2//!
3//! `fancy-regex` wraps the linear Rust `regex` engine and layers a backtracking
4//! matcher on top, so it can express the JS constructs plain `regex` cannot:
5//! lookahead (`(?=)`/`(?!)`), lookbehind (`(?<=)`/`(?<!)`), and backreferences
6//! (`\1`, `\k<name>`). node-js therefore accepts a near-superset of the JS regex
7//! grammar; the small residue fancy-regex still cannot represent is documented
8//! in BUGS.md and rejected loudly at construction time (never a silently-wrong
9//! match).
10//!
11//! What `translate` still has to do (fancy-regex/regex differ from JS here):
12//!   * `\uXXXX` / `\u{...}` → `\x{...}` (regex spells fixed code points that
13//!     way), with lone-surrogate escapes (`\uD800`..`\uDFFF`) mapped into a
14//!     Plane-15 private-use block — surrogate code points are not valid Unicode
15//!     scalar values, so `\x{D800}` will not compile; a valid UTF-8 `&str` can
16//!     never contain a lone surrogate anyway, so those alternatives stay dead
17//!     (correct for all valid input, e.g. encodeurl's unmatched-surrogate scan).
18//!   * `\/` in a literal → a plain `/` (regex rejects the redundant escape).
19//!   * `\N` / `\k<name>` → a conditional, so a reference to an unset group
20//!     matches empty as in JS; the Annex B legacy escapes (`\0`, octal, `\cX`,
21//!     identity `\8`/`\k`) become fixed code points; non-JS group syntax
22//!     (`(?i)`, `(?P<n>`, `(?>`) is rejected with node's reason.
23//!
24//! Everything else — including `(?<name>...)`, `(?=)`/`(?!)`, `(?<=)`/`(?<!)`
25//! and the `(?ims-ims:...)` modifier groups — passes through verbatim.
26//!
27//! Flags: `i`/`m`/`s` map onto inline flags; `g`/`y` drive iteration and
28//! `lastIndex` here (fancy-regex has no global flag); `u`/`d` are accepted.
29
30use crate::host::{self, with_host, JsObj, RegExpObj};
31use crate::utf16::{self, U16Index};
32use fancy_regex::{Captures, Match, Regex};
33use fusevm::Value;
34use indexmap::IndexMap;
35use rustc_hash::FxHashMap;
36use std::cell::RefCell;
37use std::rc::Rc;
38
39/// Lone-surrogate code points are not valid Unicode scalar values, so they can
40/// never appear in a Rust `&str` and `regex` refuses to compile `\x{D800}`. Map
41/// the 2048-code-point surrogate block bijectively into Plane-15 PUA-B, which is
42/// valid, contiguous (so class ranges stay ranges), and never occurs in normal
43/// text — the surrogate alternatives thus compile and stay inert on valid input.
44const SURROGATE_LO: u32 = 0xD800;
45const SURROGATE_HI: u32 = 0xDFFF;
46const SURROGATE_PUA_BASE: u32 = 0xF_0000;
47
48/// Remap a surrogate code point into the inert PUA block; pass others through.
49fn remap_surrogate(cp: u32) -> u32 {
50    if (SURROGATE_LO..=SURROGATE_HI).contains(&cp) {
51        SURROGATE_PUA_BASE + (cp - SURROGATE_LO)
52    } else {
53        cp
54    }
55}
56
57/// Build a `RegExp` value from a JS `pattern` + `flags`, or a `SyntaxError` if the
58/// pattern uses an unsupported construct or is otherwise invalid.
59/// 22.2.6.13.1 EscapeRegExpPattern — the text `source` reports, escaped so that
60/// `/` + source + `/` is a parseable regular-expression literal that matches the
61/// same thing.
62///
63/// Two characters need it and neither was handled: an unescaped `/` ended the
64/// literal early, so `String(new RegExp('/'))` produced `///`, and a literal
65/// line terminator cannot appear in a literal at all, so `new RegExp('\n')`
66/// reported a raw newline where node reports the two characters `\n`.
67///
68/// A `/` inside a character class does NOT need escaping and node does not add
69/// one (`new RegExp('[/]').source` is `[/]`), so the scan tracks class depth.
70/// An already-escaped `\/` is left alone rather than doubled.
71fn escape_regexp_pattern(pattern: &str) -> String {
72    if pattern.is_empty() {
73        return "(?:)".to_string();
74    }
75    let mut out = String::with_capacity(pattern.len());
76    let mut in_class = false;
77    let mut chars = pattern.chars();
78    while let Some(c) = chars.next() {
79        match c {
80            // A backslash escapes whatever follows; both travel through as-is.
81            '\\' => {
82                out.push(c);
83                if let Some(next) = chars.next() {
84                    out.push(next);
85                }
86            }
87            '[' if !in_class => {
88                in_class = true;
89                out.push(c);
90            }
91            ']' if in_class => {
92                in_class = false;
93                out.push(c);
94            }
95            '/' if !in_class => out.push_str("\\/"),
96            '\n' => out.push_str("\\n"),
97            '\r' => out.push_str("\\r"),
98            '\u{2028}' => out.push_str("\\u2028"),
99            '\u{2029}' => out.push_str("\\u2029"),
100            _ => out.push(c),
101        }
102    }
103    out
104}
105
106/// The early errors of a regex LITERAL (13.2.7.3): its flags and its pattern
107/// grammar, in the wording V8 gives a literal. The flag message differs from
108/// the constructor's, which names the argument.
109pub fn check_literal(pattern: &str, flags: &str) -> Result<(), String> {
110    let mut seen = String::new();
111    for c in flags.chars() {
112        if !"dgimsuvy".contains(c) || seen.contains(c) {
113            return Err("SyntaxError: Invalid regular expression flags".to_string());
114        }
115        seen.push(c);
116    }
117    if flags.contains('u') && flags.contains('v') {
118        return Err("SyntaxError: Invalid regular expression flags".to_string());
119    }
120    let sets = flags.contains('v');
121    crate::regexp_syntax::validate(pattern, flags.contains('u') || sets, sets).map_err(|reason| {
122        format!("SyntaxError: Invalid regular expression: /{pattern}/{flags}: {reason}")
123    })
124}
125
126pub fn build_regexp(pattern: &str, flags: &str) -> Result<Value, String> {
127    // Validate flags (Node throws on an unknown/repeated flag).
128    let mut seen = String::new();
129    for c in flags.chars() {
130        // `u` and `v` are mutually exclusive (22.2.3.1 step 5).
131        if !"dgimsuvy".contains(c)
132            || seen.contains(c)
133            || (c == 'v' && seen.contains('u'))
134            || (c == 'u' && seen.contains('v'))
135        {
136            return Err(format!(
137                "SyntaxError: Invalid flags supplied to RegExp constructor '{flags}'"
138            ));
139        }
140        seen.push(c);
141    }
142    let global = flags.contains('g');
143    let ignore_case = flags.contains('i');
144    let multiline = flags.contains('m');
145    let dot_all = flags.contains('s');
146    let sticky = flags.contains('y');
147    // `v` (unicodeSets) is `u` plus nested classes and the `--` / `&&` set
148    // operators, which the regex layer spells the same way.
149    let sets = flags.contains('v');
150    let unicode = flags.contains('u') || sets;
151
152    let invalid = |reason: &str| {
153        format!("SyntaxError: Invalid regular expression: /{pattern}/{flags}: {reason}")
154    };
155    crate::regexp_syntax::validate(pattern, unicode, sets).map_err(|r| invalid(&r))?;
156    let (rust_pat, capture_map) =
157        translate(pattern, unicode, sets, dot_all, multiline).map_err(|r| invalid(&r))?;
158    // Assemble the inline-flag prefix fancy-regex (via the regex layer) understands.
159    let mut prefixed = String::new();
160    if ignore_case || multiline || dot_all {
161        prefixed.push_str("(?");
162        if ignore_case {
163            prefixed.push('i');
164        }
165        if multiline {
166            prefixed.push('m');
167        }
168        if dot_all {
169            prefixed.push('s');
170        }
171        prefixed.push(')');
172    }
173    prefixed.push_str(&rust_pat);
174
175    let re = compiled(&prefixed).map_err(|e| {
176        // Collapse the multi-line error to one line for a JS-shaped message.
177        invalid(&e.lines().collect::<Vec<_>>().join(" "))
178    })?;
179
180    // A `RegExpObj` is unavoidably fresh per evaluation (`lastIndex` is
181    // per-object mutable state), but the engine inside it is not.
182    let obj = RegExpObj {
183        re: Rc::new(Engine {
184            re,
185            map: Rc::new(capture_map),
186        }),
187        source: escape_regexp_pattern(pattern),
188        flags: flags.to_string(),
189        global,
190        ignore_case,
191        multiline,
192        dot_all,
193        sticky,
194        unicode: flags.contains('u'),
195        last_index: U16Index::ZERO,
196    };
197    Ok(with_host(|h| h.alloc(JsObj::RegExp(Box::new(obj)))))
198}
199
200/// The compiled engine for an already-translated, flag-prefixed pattern,
201/// compiling it at most once per process.
202///
203/// A JS regex LITERAL is re-evaluated every time control reaches it, and each
204/// evaluation must produce a fresh `RegExp` object (`lastIndex` is per-object
205/// mutable state). Building the ENGINE each time as well is what made module
206/// loading slow: `require("express")` compiled 1,782 regexes drawn from only 59
207/// distinct patterns, and `fancy_regex::Regex::new` — not matching — accounted
208/// for 85% of the wall time. A single literal inside a hot function is the worst
209/// case: `mime-types`' `/(\.|x-).*/` cost ~1.5 ms per compile, so 2,582 loop
210/// iterations spent 4.2 s compiling one constant pattern. Hoisting that same
211/// regex out of the loop by hand took it to 27 ms, which is what identified
212/// compilation rather than matching as the cost.
213///
214/// Keyed on the translated + prefixed pattern, so two literals that differ only
215/// in spelling before translation still share one engine, and two that differ in
216/// flags do not. A compile FAILURE is not cached: it is a one-off cost on a path
217/// that immediately throws, and caching it would mean holding the error string
218/// for the life of the process.
219///
220/// Unbounded on purpose. The entries are the distinct regexes a program's source
221/// contains, which is a property of the code rather than of the input — the 59
222/// above is what a whole express dependency tree amounts to. A program that
223/// builds patterns from unbounded INPUT (`new RegExp(userString)`) is the case
224/// this would grow with, and it is also the case that gets no benefit; if that
225/// ever matters the fix is a capacity bound here, not a different design.
226fn compiled(prefixed: &str) -> Result<Rc<Regex>, String> {
227    thread_local! {
228        static CACHE: RefCell<FxHashMap<String, Rc<Regex>>> =
229            RefCell::new(FxHashMap::default());
230    }
231    if let Some(hit) = CACHE.with(|c| c.borrow().get(prefixed).cloned()) {
232        return Ok(hit);
233    }
234    let re = Rc::new(Regex::new(prefixed).map_err(|e| e.to_string())?);
235    CACHE.with(|c| {
236        c.borrow_mut().insert(prefixed.to_string(), re.clone());
237    });
238    Ok(re)
239}
240
241/// The capturing groups of a JS pattern, in source order: how many there are,
242/// and the index each named one got. A group is capturing when its `(` is not
243/// escaped, not inside a class, and is either bare or `(?<name>`
244/// (`(?<=`/`(?<!` are lookbehinds).
245///
246/// `translate` needs both BEFORE it reaches any escape: a decimal escape `\N` is
247/// a backreference only when `N` does not exceed the pattern's TOTAL group count
248/// (22.2.1.1 — a forward reference such as `/\1(a)/` still counts), and `\k` is
249/// a named reference only when the pattern has a named group at all.
250fn scan_groups(chars: &[char]) -> (usize, Vec<(String, usize)>) {
251    let mut count = 0usize;
252    let mut names = Vec::new();
253    let mut in_class = false;
254    let mut i = 0;
255    while i < chars.len() {
256        match chars[i] {
257            '\\' => i += 1,
258            '[' if !in_class => in_class = true,
259            ']' if in_class => in_class = false,
260            '(' if !in_class => {
261                if chars.get(i + 1) != Some(&'?') {
262                    count += 1;
263                } else if chars.get(i + 2) == Some(&'<')
264                    && !matches!(chars.get(i + 3), Some('=') | Some('!'))
265                {
266                    count += 1;
267                    let name: String = chars[i + 3..].iter().take_while(|c| **c != '>').collect();
268                    names.push((name, count));
269                }
270            }
271            _ => {}
272        }
273        i += 1;
274    }
275    (count, names)
276}
277
278/// What a JS capture group number means to the engine, and which captures are
279/// STALE.
280///
281/// The engine keeps a capture from an earlier iteration of a quantified group
282/// when the last iteration did not set it, where 22.2.2.5.1 RepeatMatcher step
283/// 4 clears every capture inside the group at the start of each iteration:
284/// `/(z)((a+)?(b+)?(c))*/.exec('zaacbbbcac')` is `bbb` in the engine and
285/// `undefined` in JS. The engine cannot be told to reset, so the match is
286/// corrected afterwards: a capture inside a repeating group is valid only when
287/// it lies within the span the group's LAST iteration matched. A quantified
288/// group that is not itself capturing is made capturing in the translated
289/// pattern for exactly that reason, which shifts the engine's numbering —
290/// `fancy_of_js` maps JS numbers to it.
291///
292/// The same spans carry the other half of RepeatMatcher: an iteration that
293/// matches the empty string is rejected while the minimum is already met
294/// (step 2.b), so a group under a quantifier whose minimum is 0 never holds an
295/// empty capture — `/(a*)?/.exec('b')[1]` is `undefined`, where the engine
296/// reports `''`.
297///
298/// What this cannot see: an empty capture left at the start of the last
299/// iteration, and a backreference read inside the loop. A capture made inside
300/// a lookaround is judged by where it STARTS (lookahead) or ENDS (lookbehind),
301/// since the rest of its span may lie outside the iteration.
302pub struct CaptureMap {
303    /// Engine group number for each JS group number; index 0 is the whole match.
304    fancy_of_js: Vec<usize>,
305    /// Per ENGINE group number: the quantified groups enclosing it (engine
306    /// numbers), outermost first, with how its span must sit inside theirs.
307    guards: Vec<Vec<(usize, Within)>>,
308    /// Per ENGINE group number: whether an empty capture is impossible.
309    never_empty: Vec<bool>,
310    /// Named groups with their JS group numbers.
311    names: Vec<(String, usize)>,
312}
313
314/// How a capture's span is judged against the span of an enclosing group's
315/// iteration.
316#[derive(Clone, Copy)]
317enum Within {
318    /// The whole span lies inside.
319    Whole,
320    /// The span starts inside (a capture within a lookahead).
321    Start,
322    /// The span ends inside (a capture within a lookbehind).
323    End,
324}
325
326impl CaptureMap {
327    /// The identity numbering of a pattern with `count` capturing groups.
328    fn identity(count: usize, names: Vec<(String, usize)>) -> CaptureMap {
329        CaptureMap {
330            fancy_of_js: (0..=count).collect(),
331            guards: vec![Vec::new(); count + 1],
332            never_empty: vec![false; count + 1],
333            names,
334        }
335    }
336}
337
338/// A group's role while the pattern is scanned for repetition.
339#[derive(Clone, Copy, PartialEq)]
340enum GroupKind {
341    Capture,
342    /// `(?:…)`, the only kind that is rewritten into a capture.
343    Plain,
344    LookAhead,
345    LookBehind,
346    /// Anything else behind `(?` (modifier groups).
347    Other,
348}
349
350/// The pre-pass result for one pattern: which `(?:` groups `translate` must
351/// emit as captures, in `(` order, and the numbering that results.
352struct GroupPlan {
353    hidden: Vec<bool>,
354    map: CaptureMap,
355}
356
357/// Whether a quantifier at `chars[at..]` can run its operand more than once:
358/// `*`, `+`, `{n,}` and `{n,m}` with `m > 1`, `{n}` with `n > 1`.
359fn quantifier_repeats(chars: &[char], at: usize) -> bool {
360    match chars.get(at) {
361        Some('*' | '+') => true,
362        Some('{') => {
363            let body: String = chars[at + 1..].iter().take_while(|c| **c != '}').collect();
364            if chars.get(at + 1 + body.chars().count()) != Some(&'}') {
365                return false;
366            }
367            match body.split_once(',') {
368                None => body.parse::<u64>().is_ok_and(|n| n > 1),
369                Some((lo, "")) => lo.parse::<u64>().is_ok(),
370                Some((lo, hi)) => {
371                    lo.parse::<u64>().is_ok() && hi.parse::<u64>().is_ok_and(|n| n > 1)
372                }
373            }
374        }
375        _ => false,
376    }
377}
378
379/// Scan a pattern's group structure (the same notion of "a group" as
380/// [`scan_groups`]) and decide the numbering described on [`CaptureMap`].
381fn plan_groups(chars: &[char], names: Vec<(String, usize)>) -> GroupPlan {
382    let mut kind: Vec<GroupKind> = Vec::new();
383    let mut parent: Vec<Option<usize>> = Vec::new();
384    let mut repeats: Vec<bool> = Vec::new();
385    let mut min_zero: Vec<bool> = Vec::new();
386    let mut has_capture: Vec<bool> = Vec::new();
387    let mut open: Vec<usize> = Vec::new();
388    let mut in_class = false;
389    let mut i = 0;
390    while i < chars.len() {
391        match chars[i] {
392            '\\' => i += 1,
393            '[' if !in_class => in_class = true,
394            ']' if in_class => in_class = false,
395            '(' if !in_class => {
396                let k = if chars.get(i + 1) != Some(&'?') {
397                    GroupKind::Capture
398                } else {
399                    match (chars.get(i + 2), chars.get(i + 3)) {
400                        (Some(':'), _) => GroupKind::Plain,
401                        (Some('=' | '!'), _) => GroupKind::LookAhead,
402                        (Some('<'), Some('=' | '!')) => GroupKind::LookBehind,
403                        (Some('<'), _) => GroupKind::Capture,
404                        _ => GroupKind::Other,
405                    }
406                };
407                parent.push(open.last().copied());
408                open.push(kind.len());
409                kind.push(k);
410                repeats.push(false);
411                min_zero.push(false);
412                has_capture.push(false);
413            }
414            ')' if !in_class => {
415                if let Some(id) = open.pop() {
416                    repeats[id] = quantifier_repeats(chars, i + 1);
417                    min_zero[id] = quantifier_at(chars, i + 1).is_some_and(|(_, min)| min == 0);
418                    if kind[id] == GroupKind::Capture || has_capture[id] {
419                        if let Some(p) = parent[id] {
420                            has_capture[p] = true;
421                        }
422                    }
423                }
424            }
425            _ => {}
426        }
427        i += 1;
428    }
429    let hidden: Vec<bool> = (0..kind.len())
430        .map(|g| kind[g] == GroupKind::Plain && (repeats[g] || min_zero[g]) && has_capture[g])
431        .collect();
432    // Engine numbers follow `(` order over capturing and rewritten groups.
433    let mut fancy: Vec<usize> = vec![0; kind.len()];
434    let mut fancy_of_js = vec![0usize];
435    let mut next = 0;
436    for g in 0..kind.len() {
437        if kind[g] == GroupKind::Capture || hidden[g] {
438            next += 1;
439            fancy[g] = next;
440            if kind[g] == GroupKind::Capture {
441                fancy_of_js.push(next);
442            }
443        }
444    }
445    let mut guards: Vec<Vec<(usize, Within)>> = vec![Vec::new(); next + 1];
446    let mut never_empty = vec![false; next + 1];
447    for g in 0..kind.len() {
448        if fancy[g] == 0 {
449            continue;
450        }
451        never_empty[fancy[g]] = min_zero[g];
452        let mut chain = Vec::new();
453        let mut within = Within::Whole;
454        let mut p = parent[g];
455        while let Some(a) = p {
456            // A capture in a lookaround is judged at one end only, and a
457            // lookahead inside a lookbehind (or the reverse) at neither end.
458            within = match (kind[a], within) {
459                (GroupKind::LookAhead, Within::Whole | Within::Start) => Within::Start,
460                (GroupKind::LookBehind, Within::Whole | Within::End) => Within::End,
461                (GroupKind::LookAhead | GroupKind::LookBehind, _) => break,
462                _ => within,
463            };
464            if fancy[a] != 0 && (repeats[a] || min_zero[a]) {
465                chain.push((fancy[a], within));
466            }
467            p = parent[a];
468        }
469        chain.reverse();
470        guards[fancy[g]] = chain;
471    }
472    GroupPlan {
473        hidden,
474        map: CaptureMap {
475            fancy_of_js,
476            guards,
477            never_empty,
478            names,
479        },
480    }
481}
482
483/// A compiled pattern together with its [`CaptureMap`]. Derefs to the engine
484/// for everything that does not look at captures.
485pub struct Engine {
486    re: Rc<Regex>,
487    map: Rc<CaptureMap>,
488}
489
490impl std::ops::Deref for Engine {
491    type Target = Regex;
492    fn deref(&self) -> &Regex {
493        &self.re
494    }
495}
496
497impl Engine {
498    pub fn captures_from_pos<'t>(
499        &self,
500        s: &'t str,
501        pos: usize,
502    ) -> Result<Option<Caps<'t>>, fancy_regex::Error> {
503        Ok(self.re.captures_from_pos(s, pos)?.map(|inner| Caps {
504            inner,
505            map: self.map.clone(),
506        }))
507    }
508
509    pub fn captures<'t>(&self, s: &'t str) -> Result<Option<Caps<'t>>, fancy_regex::Error> {
510        Ok(self.re.captures(s)?.map(|inner| Caps {
511            inner,
512            map: self.map.clone(),
513        }))
514    }
515}
516
517/// The captures of one match, numbered and filtered as JS sees them.
518pub struct Caps<'t> {
519    inner: Captures<'t>,
520    map: Rc<CaptureMap>,
521}
522
523impl<'t> Caps<'t> {
524    /// Number of JS groups, including the whole match.
525    pub fn len(&self) -> usize {
526        self.map.fancy_of_js.len()
527    }
528
529    pub fn is_empty(&self) -> bool {
530        false
531    }
532
533    /// Capture `i` as JS numbers it, or `None` if it did not participate in
534    /// the last iteration of every repeating group around it.
535    pub fn get(&self, i: usize) -> Option<Match<'t>> {
536        let f = *self.map.fancy_of_js.get(i)?;
537        self.valid(f).then(|| self.inner.get(f)).flatten()
538    }
539
540    pub fn name(&self, name: &str) -> Option<Match<'t>> {
541        let (_, i) = self.map.names.iter().find(|(n, _)| n == name)?;
542        self.get(*i)
543    }
544
545    fn valid(&self, f: usize) -> bool {
546        let Some(m) = self.inner.get(f) else {
547            return false;
548        };
549        if self.map.never_empty[f] && m.start() == m.end() {
550            return false;
551        }
552        self.map.guards[f].iter().all(|&(q, within)| {
553            self.inner.get(q).is_some_and(|g| {
554                let inside = |at: usize| g.start() <= at && at <= g.end();
555                match within {
556                    Within::Whole => inside(m.start()) && inside(m.end()),
557                    Within::Start => inside(m.start()),
558                    Within::End => inside(m.end()),
559                }
560            }) && self.valid(q)
561        })
562    }
563}
564
565/// A code point as the fixed `\x{..}` spelling the regex layer accepts both in
566/// and out of a class.
567fn hex_escape(cp: u32) -> String {
568    format!("\\x{{{cp:X}}}")
569}
570
571/// Annex B.1.2 LegacyOctalEscapeSequence starting at `chars[i]` (an octal
572/// digit): the longest of `[0-3][0-7][0-7]`, `[0-7][0-7]`, `[0-7]`, so the value
573/// never exceeds 0o377. Returns the code point and how many digits it took.
574fn legacy_octal(chars: &[char], i: usize) -> (u32, usize) {
575    let oct = |k: usize| chars.get(k).and_then(|c| c.to_digit(8));
576    let first = oct(i).unwrap_or(0);
577    let max = if first <= 3 { 3 } else { 2 };
578    let mut value = first;
579    let mut len = 1;
580    while len < max {
581        match oct(i + len) {
582            Some(d) => {
583                value = value * 8 + d;
584                len += 1;
585            }
586            None => break,
587        }
588    }
589    (value, len)
590}
591
592/// Validate the group opener at `chars[i] == '('` when it is followed by `?`,
593/// returning the reason node's parser gives for a form JS does not have.
594///
595/// JS accepts exactly `(?:`, `(?=`, `(?!`, `(?<=`, `(?<!`, `(?<name>`, and the
596/// ES2025 modifier groups `(?ims-ims:` — never a bare inline flag (`(?i)`), and
597/// none of Perl/PCRE's `(?x)`, `(?P<n>`, `(?#…)`, `(?>…)`, all of which the
598/// regex layer would otherwise accept and silently give a meaning.
599fn check_group(chars: &[char], i: usize) -> Result<(), &'static str> {
600    match chars.get(i + 2) {
601        Some(':') | Some('=') | Some('!') | Some('<') => return Ok(()),
602        _ => {}
603    }
604    let mut seen = String::new();
605    let mut k = i + 2;
606    let mut saw_dash = false;
607    while let Some(&c) = chars.get(k) {
608        match c {
609            'i' | 'm' | 's' => {
610                if seen.contains(c) {
611                    return Err("Repeated flag in flag group");
612                }
613                seen.push(c);
614            }
615            '-' if !saw_dash => saw_dash = true,
616            ':' if seen.is_empty() => return Err("Invalid flag group"),
617            ':' => return Ok(()),
618            _ => return Err("Invalid group"),
619        }
620        k += 1;
621    }
622    Err("Invalid group")
623}
624
625/// `\b` and `\B` over the ASCII word set JS defines (22.2.2.9 IsWordChar). The
626/// regex layer's own `\b` is Unicode-aware and its `(?-u:\b)` is refused by
627/// fancy-regex, so the assertion is spelled out with lookaround.
628const WORD_BOUNDARY: &str =
629    "(?:(?<=[0-9A-Za-z_])(?![0-9A-Za-z_])|(?<![0-9A-Za-z_])(?=[0-9A-Za-z_]))";
630const NOT_WORD_BOUNDARY: &str =
631    "(?:(?<=[0-9A-Za-z_])(?=[0-9A-Za-z_])|(?<![0-9A-Za-z_])(?![0-9A-Za-z_]))";
632
633/// A quantifier at `chars[at..]` — `*`, `+`, `?`, `{n}`, `{n,}`, `{n,m}`, each
634/// with an optional lazy `?` — as (index past it, its minimum count).
635fn quantifier_at(chars: &[char], at: usize) -> Option<(usize, u64)> {
636    let (mut end, min) = match chars.get(at)? {
637        '*' | '?' => (at + 1, 0),
638        '+' => (at + 1, 1),
639        '{' => {
640            let mut j = at + 1;
641            let lo_start = j;
642            while chars.get(j).is_some_and(char::is_ascii_digit) {
643                j += 1;
644            }
645            if j == lo_start {
646                return None;
647            }
648            let min: u64 = chars[lo_start..j]
649                .iter()
650                .collect::<String>()
651                .parse()
652                .unwrap_or(u64::MAX);
653            if chars.get(j) == Some(&',') {
654                j += 1;
655                while chars.get(j).is_some_and(char::is_ascii_digit) {
656                    j += 1;
657                }
658            }
659            if chars.get(j) != Some(&'}') {
660                return None;
661            }
662            (j + 1, min)
663        }
664        _ => return None,
665    };
666    if chars.get(end) == Some(&'?') {
667        end += 1;
668    }
669    Some((end, min))
670}
671
672/// Whether four hex digits sit at `chars[at..]` — the `\uXXXX` form.
673fn four_hex(chars: &[char], at: usize) -> bool {
674    chars
675        .get(at..at + 4)
676        .is_some_and(|h| h.iter().all(|c| c.is_ascii_hexdigit()))
677}
678
679/// The JS meaning of `\d \D \w \W \s \S` (22.2.2.9) in the regex layer's
680/// syntax. Inside a class the positive forms are bare members and the negated
681/// ones nested classes, which the regex layer unions.
682fn class_escape(e: char, in_class: bool) -> String {
683    /// WhiteSpace and LineTerminator (12.2, 12.3) — which is NOT Unicode's
684    /// `White_Space`: it has U+FEFF and lacks U+0085.
685    const WS: &str = r"\t\n\x{B}\x{C}\r \x{A0}\x{1680}\x{2000}-\x{200A}\x{2028}\x{2029}\x{202F}\x{205F}\x{3000}\x{FEFF}";
686    const WORD: &str = "0-9A-Za-z_";
687    let members = match e.to_ascii_lowercase() {
688        'd' => "0-9",
689        'w' => WORD,
690        _ => WS,
691    };
692    match (e.is_ascii_lowercase(), in_class) {
693        (true, true) => members.to_string(),
694        (true, false) => format!("[{members}]"),
695        (false, _) => format!("[^{members}]"),
696    }
697}
698
699/// Translate a JS regex source into fancy-regex syntax, or the reason node's
700/// parser would reject it (the caller adds the `Invalid regular expression:
701/// /…/flags: ` frame).
702///
703/// Rewrites, each because the regex layer reads the same spelling differently:
704///   * `\uXXXX` / `\u{…}` → `\x{…}`, surrogates remapped (see `remap_surrogate`).
705///   * `\/` → `/`; a bare `[` inside a class → `\[`.
706///   * `\N` that names an existing group → `(?(N)\N|)`. JS matches a reference
707///     to a group that has not participated as the EMPTY string (22.2.2.7.2
708///     BackreferenceMatcher step 7), so `/\1(a)/` and `/(a)?b\1/` both match;
709///     fancy-regex fails such a reference instead, and its conditional is what
710///     restores "empty when unset". `\k<name>` gets the same treatment by index.
711///   * Outside unicode mode, the Annex B.1.2 legacy forms: `\N` past the group
712///     count is an octal escape (`\052` is `*`), or the digit itself for 8/9;
713///     `\0` is NUL; in a class every `\N` is octal; `\cX` is the control
714///     character X % 32 (plus `\c<digit>`/`\c_` in a class), and a `\c` that
715///     forms none of those is a literal backslash followed by `c`; `\k` with no
716///     named group in the pattern is the letter `k`.
717///   * In unicode mode those legacy forms are the SyntaxErrors node raises.
718fn translate(
719    pat: &str,
720    unicode: bool,
721    sets: bool,
722    dot_all: bool,
723    multiline: bool,
724) -> Result<(String, CaptureMap), String> {
725    match translate_with(pat, unicode, sets, dot_all, multiline, true)? {
726        (out, map, true) => Ok((out, map)),
727        // The pre-pass and the walk disagreed about the number of groups (a
728        // `v`-mode class holding a `(`), which would misnumber every capture
729        // after it: translate again with the engine's own numbering, which is
730        // merely un-filtered.
731        _ => translate_with(pat, unicode, sets, dot_all, multiline, false).map(|(o, m, _)| (o, m)),
732    }
733}
734
735/// [`translate`] with `allow_hidden` choosing whether repeating `(?:…)` groups
736/// are rewritten into captures. The flag in the result says the group count the
737/// pre-pass planned for matched the one the walk saw.
738fn translate_with(
739    pat: &str,
740    unicode: bool,
741    sets: bool,
742    dot_all: bool,
743    multiline: bool,
744    allow_hidden: bool,
745) -> Result<(String, CaptureMap, bool), String> {
746    let chars: Vec<char> = pat.chars().collect();
747    let (group_count, group_names) = scan_groups(&chars);
748    let mut plan = plan_groups(&chars, group_names.clone());
749    if !allow_hidden {
750        plan = GroupPlan {
751            hidden: vec![false; plan.hidden.len()],
752            map: CaptureMap::identity(group_count, group_names.clone()),
753        };
754    }
755    // How many source `(` have been seen, to index `plan.hidden` in step with
756    // the pre-pass.
757    let mut paren_seen = 0usize;
758    let mut out = String::new();
759    let mut i = 0;
760    // Track whether we're inside a `[...]` class. `class_pos` is how many chars
761    // into the current class we are, so we can spot the `]` that would close an
762    // empty class (`[]` / `[^]`) vs. a literal leading `]`.
763    let mut in_class = false;
764    let mut class_pos = 0usize;
765    // Under `v` classes nest; this counts the open ones.
766    let mut class_depth = 0usize;
767    // Whether the previous class member was a set escape (`\d`): a `-` after one
768    // is a literal, which the regex layer would otherwise read as a range.
769    let mut prev_set = false;
770    // One entry per open group: where its `(` landed in `out` when it is a
771    // lookahead (which Annex B lets take a quantifier — the regex layer does not,
772    // so it is wrapped in `(?:…)` once its close is seen).
773    let mut group_open: Vec<Option<usize>> = Vec::new();
774    while i < chars.len() {
775        let c = chars[i];
776        let after_set = std::mem::take(&mut prev_set);
777        // Character-class bookkeeping. A `\` escape is handled below and never
778        // toggles class state (it consumes its own two chars).
779        if c != '\\' {
780            if (!in_class || sets) && c == '[' {
781                // A `]` right after the opener (and its `^`) CLOSES the class in
782                // JS: `[]` matches nothing and `[^]` matches any code unit.
783                let negated = chars.get(i + 1) == Some(&'^');
784                let close_at = i + 1 + usize::from(negated);
785                if chars.get(close_at) == Some(&']') {
786                    out.push_str(if negated { r"[\s\S]" } else { r"[^\s\S]" });
787                    if in_class {
788                        class_pos += 1;
789                    }
790                    i = close_at + 1;
791                    continue;
792                }
793                in_class = true;
794                class_depth += 1;
795                class_pos = 0;
796                out.push('[');
797                i += 1;
798                // A leading `^` is the negation, not the first member.
799                if negated {
800                    out.push('^');
801                    i += 1;
802                }
803                continue;
804            }
805            if in_class {
806                // The first char of a class, if `]`, is a literal `]` in JS; a
807                // later bare `[` must be escaped for the regex layer.
808                if c == ']' && (class_pos > 0 || sets) {
809                    class_depth = class_depth.saturating_sub(1);
810                    in_class = class_depth > 0;
811                    out.push(']');
812                    i += 1;
813                    continue;
814                }
815                if c == '[' {
816                    out.push_str("\\[");
817                    class_pos += 1;
818                    i += 1;
819                    continue;
820                }
821            } else if c == '(' && chars.get(i + 1) == Some(&'?') {
822                check_group(&chars, i).map_err(str::to_string)?;
823            }
824        }
825        match c {
826            '\\' => {
827                class_pos += 1;
828                match chars.get(i + 1).copied() {
829                    // `\uXXXX` / `\u{...}` → `\x{...}` (surrogates remapped). Outside the
830                    // `u` flag only the four-digit form is an escape: `\u{61}` is `u`
831                    // repeated 61 times, and a malformed `\u` is the letter itself.
832                    Some('u') if !unicode && !four_hex(&chars, i + 2) => {
833                        out.push('u');
834                        i += 2;
835                        continue;
836                    }
837                    Some('u') if !unicode && chars.get(i + 2) == Some(&'{') => {
838                        out.push('u');
839                        i += 2;
840                        continue;
841                    }
842                    Some('u') => {
843                        i += 2;
844                        let cp_hex: String;
845                        if chars.get(i) == Some(&'{') {
846                            i += 1;
847                            let mut hex = String::new();
848                            while i < chars.len() && chars[i] != '}' {
849                                hex.push(chars[i]);
850                                i += 1;
851                            }
852                            i += 1; // consume '}'
853                            cp_hex = hex;
854                        } else {
855                            // Exactly four hex digits.
856                            cp_hex = chars[i..(i + 4).min(chars.len())].iter().collect();
857                            i += 4;
858                        }
859                        match u32::from_str_radix(cp_hex.trim(), 16) {
860                            Ok(cp) => out.push_str(&hex_escape(remap_surrogate(cp))),
861                            // Not valid hex — emit the code point literally so the
862                            // engine surfaces its own error rather than us guessing.
863                            Err(_) => out.push_str(&format!("\\x{{{cp_hex}}}")),
864                        }
865                        continue;
866                    }
867                    // `\xHH`; a malformed one outside `u` is the letter `x` (B.1.2).
868                    Some('x') => {
869                        let hex: String = chars
870                            .get(i + 2..i + 4)
871                            .map(|h| h.iter().collect())
872                            .unwrap_or_default();
873                        match u32::from_str_radix(&hex, 16) {
874                            Ok(v)
875                                if hex.len() == 2 && hex.chars().all(|c| c.is_ascii_hexdigit()) =>
876                            {
877                                out.push_str(&hex_escape(v));
878                                i += 4;
879                            }
880                            _ => {
881                                out.push('x');
882                                i += 2;
883                            }
884                        }
885                        continue;
886                    }
887                    // `\/` in a JS literal → a plain slash (regex rejects `\/`).
888                    Some('/') => {
889                        out.push('/');
890                        i += 2;
891                        continue;
892                    }
893                    Some('c') => {
894                        let control = match chars.get(i + 2) {
895                            Some(x) if x.is_ascii_alphabetic() => Some(*x),
896                            Some(x)
897                                if in_class && !unicode && (x.is_ascii_digit() || *x == '_') =>
898                            {
899                                Some(*x)
900                            }
901                            _ => None,
902                        };
903                        match control {
904                            Some(x) => {
905                                out.push_str(&hex_escape(x as u32 % 32));
906                                i += 3;
907                            }
908                            None if unicode => return Err("Invalid Unicode escape".into()),
909                            // Annex B: `\` stands for itself; `c` is read next.
910                            None => {
911                                out.push_str("\\\\");
912                                i += 1;
913                            }
914                        }
915                        continue;
916                    }
917                    Some(d) if d.is_ascii_digit() => {
918                        let lone_zero =
919                            d == '0' && !chars.get(i + 2).is_some_and(|n| n.is_ascii_digit());
920                        if lone_zero {
921                            out.push_str(&hex_escape(0));
922                            i += 2;
923                            continue;
924                        }
925                        if !in_class && d != '0' {
926                            let digits: String = chars[i + 1..]
927                                .iter()
928                                .take_while(|c| c.is_ascii_digit())
929                                .collect();
930                            let n = digits.parse::<usize>().unwrap_or(usize::MAX);
931                            if n <= group_count {
932                                let n = plan.map.fancy_of_js[n];
933                                out.push_str(&format!("(?({n})\\{n}|)"));
934                                i += 1 + digits.len();
935                                continue;
936                            }
937                        }
938                        if unicode {
939                            let reason = if in_class || d == '0' {
940                                "Invalid decimal escape"
941                            } else {
942                                "Invalid escape"
943                            };
944                            return Err(reason.into());
945                        }
946                        if d == '8' || d == '9' {
947                            out.push(d);
948                            i += 2;
949                        } else {
950                            let (cp, len) = legacy_octal(&chars, i + 1);
951                            out.push_str(&hex_escape(cp));
952                            i += 1 + len;
953                        }
954                        continue;
955                    }
956                    Some('k') if in_class || (group_names.is_empty() && !unicode) => {
957                        if unicode {
958                            return Err("Invalid class escape".into());
959                        }
960                        out.push('k');
961                        i += 2;
962                        continue;
963                    }
964                    Some('k') => {
965                        if chars.get(i + 2) != Some(&'<') {
966                            return Err("Invalid named reference".into());
967                        }
968                        let Some(close) = chars[i + 3..].iter().position(|c| *c == '>') else {
969                            return Err("Invalid capture group name".into());
970                        };
971                        let name: String = chars[i + 3..i + 3 + close].iter().collect();
972                        let Some((_, index)) = group_names.iter().find(|(n, _)| *n == name) else {
973                            return Err("Invalid named capture referenced".into());
974                        };
975                        let index = plan.map.fancy_of_js[*index];
976                        out.push_str(&format!("(?({index})\\{index}|)"));
977                        i += 4 + close;
978                        continue;
979                    }
980                    // `\p{…}` is a property escape only under `u`/`v`; without them it
981                    // is the letter itself, followed by whatever `{…}` is.
982                    Some(pc @ ('p' | 'P')) if !unicode => {
983                        out.push(pc);
984                        i += 2;
985                        continue;
986                    }
987                    // The class escapes are ASCII-only in JS (and `\s` is the spec's
988                    // WhiteSpace + LineTerminator list), where the regex layer's own
989                    // `\d \w \s \b` are Unicode-aware.
990                    Some(e @ ('d' | 'D' | 'w' | 'W' | 's' | 'S')) => {
991                        out.push_str(&class_escape(e, in_class));
992                        prev_set = in_class;
993                        i += 2;
994                        continue;
995                    }
996                    Some('b') if in_class => {
997                        out.push_str(&hex_escape(8));
998                        i += 2;
999                        continue;
1000                    }
1001                    Some(b @ ('b' | 'B')) => {
1002                        out.push_str(if b == 'b' {
1003                            WORD_BOUNDARY
1004                        } else {
1005                            NOT_WORD_BOUNDARY
1006                        });
1007                        i += 2;
1008                        continue;
1009                    }
1010                    // Everything else (`\n \. \\` …) passes through.
1011                    Some(other) => {
1012                        out.push('\\');
1013                        out.push(other);
1014                        i += 2;
1015                        continue;
1016                    }
1017                    None => {
1018                        out.push('\\');
1019                        i += 1;
1020                    }
1021                }
1022            }
1023            '(' if !in_class => {
1024                let source_paren = paren_seen;
1025                paren_seen += 1;
1026                // A repeating `(?:…)` that holds captures becomes a capture so
1027                // its last iteration's span is known (see `CaptureMap`).
1028                if plan.hidden.get(source_paren) == Some(&true) {
1029                    group_open.push(None);
1030                    out.push('(');
1031                    i += 3;
1032                    continue;
1033                }
1034                let lookahead =
1035                    chars.get(i + 1) == Some(&'?') && matches!(chars.get(i + 2), Some('=' | '!'));
1036                group_open.push(lookahead.then_some(out.len()));
1037                out.push('(');
1038                i += 1;
1039            }
1040            ')' if !in_class => {
1041                out.push(')');
1042                i += 1;
1043                // A quantified lookahead (Annex B) cannot be handed to the regex
1044                // layer, which refuses to repeat a zero-width assertion. It does
1045                // not need to: an iteration that matches the empty string is
1046                // rejected once the minimum is met (22.2.2.3.1 RepeatMatcher
1047                // step 2.b), so the quantifier can only ever run the assertion
1048                // ONCE when its minimum is 1 or more, and never when it is 0.
1049                if let Some(Some(at)) = group_open.pop() {
1050                    if let Some((next, min)) = quantifier_at(&chars, i).filter(|_| !unicode) {
1051                        if min == 0 {
1052                            // Kept as a group that can never match, so the
1053                            // numbering of any capture inside is unchanged.
1054                            out.insert_str(at, "(?:(?!)");
1055                            out.push_str(")?");
1056                        }
1057                        i = next;
1058                    }
1059                }
1060            }
1061            // `.` excludes all four LineTerminators, not just `\n`.
1062            '.' if !in_class && !dot_all => {
1063                out.push_str(r"[^\n\r\x{2028}\x{2029}]");
1064                i += 1;
1065            }
1066            // Under `m`, `^`/`$` also sit beside `\r`, LS and PS; the engine's own
1067            // multi-line anchors know only `\n`.
1068            '^' if !in_class && multiline => {
1069                out.push_str(r"(?:^|(?<=[\r\x{2028}\x{2029}]))");
1070                i += 1;
1071            }
1072            '$' if !in_class && multiline => {
1073                out.push_str(r"(?:$|(?=[\r\x{2028}\x{2029}]))");
1074                i += 1;
1075            }
1076            '-' if in_class
1077                && (after_set
1078                    || (chars.get(i + 1) == Some(&'\\')
1079                        && matches!(
1080                            chars.get(i + 2),
1081                            Some('d' | 'D' | 'w' | 'W' | 's' | 'S')
1082                        ))) =>
1083            {
1084                out.push_str("\\-");
1085                class_pos += 1;
1086                i += 1;
1087            }
1088            _ => {
1089                if in_class {
1090                    class_pos += 1;
1091                }
1092                out.push(c);
1093                i += 1;
1094            }
1095        }
1096    }
1097    Ok((out, plan.map, paren_seen == plan.hidden.len()))
1098}
1099
1100/// The flags string in the spec's canonical order (22.2.6.4 reads the six
1101/// reflectors in a fixed sequence), independent of how the literal spelled
1102/// them.
1103fn canonical_flags(flags: &str) -> String {
1104    "dgimsuvy"
1105        .chars()
1106        .filter(|c| flags.contains(*c))
1107        .collect::<String>()
1108}
1109
1110/// A `RegExp` own data property (`source`/`flags`/`global`/…/`lastIndex`), or
1111/// `None` if `name` is not one (so the caller tries methods).
1112pub fn regexp_property(r: &RegExpObj, name: &str) -> Option<Value> {
1113    Some(match name {
1114        "source" => with_host(|h| h.new_str(r.source.clone())),
1115        // `RegExp.prototype.flags` (22.2.6.4) is a GETTER that rebuilds the
1116        // string in the spec's fixed `dgimsuvy` order, not the spelling the
1117        // literal used: `/a/gid.flags` is `"dgi"` in node and was `"gid"` here,
1118        // so any code keyed on the flags string (a cache key, a `new
1119        // RegExp(src, flags)` round-trip comparison) disagreed.
1120        "flags" => with_host(|h| h.new_str(canonical_flags(&r.flags))),
1121        "global" => Value::Bool(r.global),
1122        "ignoreCase" => Value::Bool(r.ignore_case),
1123        "multiline" => Value::Bool(r.multiline),
1124        "dotAll" => Value::Bool(r.dot_all),
1125        "sticky" => Value::Bool(r.sticky),
1126        "unicode" => Value::Bool(r.unicode),
1127        // `d` is accepted and its match-indices output ignored (BUGS.md), but
1128        // the flag reflector still has to report it; it read `undefined` where
1129        // node says `true`/`false`.
1130        "hasIndices" => Value::Bool(r.flags.contains('d')),
1131        "unicodeSets" => Value::Bool(r.flags.contains('v')),
1132        "lastIndex" => Value::Float(r.last_index.get() as f64),
1133        _ => return None,
1134    })
1135}
1136
1137pub fn is_regexp_method(name: &str) -> bool {
1138    matches!(name, "test" | "exec" | "toString" | "compile")
1139        // The five symbol-keyed methods a RegExp exposes so the string methods
1140        // can delegate to it (22.2.6.x). They were absent, so
1141        // `/a/[Symbol.match]("x")` was not a function and a subclass could not
1142        // override the protocol by calling `super[Symbol.match]`.
1143        || matches!(
1144            name,
1145            "@@match" | "@@matchAll" | "@@search" | "@@split" | "@@replace"
1146        )
1147}
1148
1149/// V8's wording for a `RegExp.prototype` method whose receiver is not a RegExp.
1150pub fn incompatible_receiver(method: &str, recv: &Value) -> String {
1151    host::type_error(&format!(
1152        "Method RegExp.prototype.{method} called on incompatible receiver {}",
1153        crate::builtins::no_side_effects_string_pub(recv)
1154    ))
1155}
1156
1157/// Whether `f` is the built-in `RegExp.prototype.exec` — read off a RegExp
1158/// (a thunk bound to it) or off the prototype itself.
1159fn is_builtin_exec(f: &Value) -> bool {
1160    with_host(|h| match h.get(f) {
1161        Some(JsObj::BoundMethod { recv, name }) => {
1162            name == "exec" && matches!(h.get(recv), Some(JsObj::RegExp(_)))
1163        }
1164        Some(JsObj::Builtin(n)) => n == "@proto:RegExp:exec",
1165        _ => false,
1166    })
1167}
1168
1169/// `RegExpExec(R, S)` (22.2.7.1). `R`'s `exec` is read with `[[Get]]`; one that
1170/// is not the built-in — an own override, a subclass method, or the method of a
1171/// plain object — is called and must return an object or `null`. Otherwise `R`
1172/// has to be a RegExp, and the built-in matcher runs.
1173pub fn regexp_exec_generic(r: &Value, s: &str) -> Result<Value, String> {
1174    match user_exec(r)? {
1175        Some(exec) => call_user_exec(r, &exec, s),
1176        None => regexp_exec(require_regexp(r, "exec")?, s),
1177    }
1178}
1179
1180/// The `exec` `RegExpExec` must CALL: `Some` when `[[Get]](R, "exec")` is a
1181/// callable other than the built-in, `None` when the built-in matcher applies.
1182fn user_exec(r: &Value) -> Result<Option<Value>, String> {
1183    // The common case answers without materializing the method: a RegExp with
1184    // no own `exec`, linked straight to `RegExp.prototype`, whose `exec` no
1185    // script has replaced (a replacement lives in the namespace's own table).
1186    let untouched = with_host(|h| {
1187        matches!(h.get(r), Some(JsObj::RegExp(_)))
1188            && h.fn_prop(r, "exec").is_none()
1189            && h.proto_of(r).is_none()
1190            && h.builtin_static("RegExp.prototype", "exec").is_none()
1191    });
1192    if untouched {
1193        return Ok(None);
1194    }
1195    let exec = crate::builtins::get_property(r, "exec")?;
1196    Ok((!is_builtin_exec(&exec) && with_host(|h| host::is_callable(h, &exec))).then_some(exec))
1197}
1198
1199/// Call a user `exec` and enforce `RegExpExec` step 2.b on its result.
1200fn call_user_exec(r: &Value, exec: &Value, s: &str) -> Result<Value, String> {
1201    let subject = with_host(|h| h.new_str(s));
1202    let result = host::invoke(exec, vec![subject], Some(r.clone()))?;
1203    let ok = with_host(|h| {
1204        h.is_null(&result) || (matches!(result, Value::Obj(_)) && !host::is_primitive(h, &result))
1205    });
1206    if !ok {
1207        return Err(host::type_error(
1208            "RegExp exec method returned something other than an Object or null",
1209        ));
1210    }
1211    Ok(result)
1212}
1213
1214/// `r` itself when it is a RegExp, else V8's incompatible-receiver error for
1215/// `method` — the built-in matcher needs `[[RegExpMatcher]]`.
1216fn require_regexp<'a>(r: &'a Value, method: &str) -> Result<&'a Value, String> {
1217    if with_host(|h| matches!(h.get(r), Some(JsObj::RegExp(_)))) {
1218        Ok(r)
1219    } else {
1220        Err(incompatible_receiver(method, r))
1221    }
1222}
1223
1224/// `RegExp.prototype.test` (22.2.6.16): `RegExpExec` and a non-null result.
1225/// Generic over any object receiver; with the built-in `exec` it runs the
1226/// matcher without building a match array.
1227pub fn regexp_test_generic(r: &Value, arg: &Value) -> Result<Value, String> {
1228    let s = match with_host(|h| h.as_str(arg)) {
1229        Some(s) => s,
1230        None => {
1231            let v = host::to_string_value(arg)?;
1232            with_host(|h| h.str_of(&v))
1233        }
1234    };
1235    Ok(Value::Bool(match user_exec(r)? {
1236        Some(exec) => {
1237            let result = call_user_exec(r, &exec, &s)?;
1238            !with_host(|h| h.is_null(&result))
1239        }
1240        None => regexp_test(require_regexp(r, "exec")?, &s),
1241    }))
1242}
1243
1244/// `RegExp.prototype.toString` (22.2.6.17): `"/" + ToString(R.source) + "/" +
1245/// ToString(R.flags)`, both read with `[[Get]]`, for any object receiver.
1246pub fn regexp_to_string_generic(r: &Value) -> Result<Value, String> {
1247    let read = |k: &str| -> Result<String, String> {
1248        let v = crate::builtins::get_property(r, k)?;
1249        let s = host::to_string_value(&v)?;
1250        Ok(with_host(|h| h.str_of(&s)))
1251    };
1252    let source = read("source")?;
1253    let flags = read("flags")?;
1254    Ok(with_host(|h| h.new_str(format!("/{source}/{flags}"))))
1255}
1256
1257/// Dispatch a `RegExp.prototype` method.
1258pub fn regexp_method(recv: &Value, name: &str, args: Vec<Value>) -> Result<Value, String> {
1259    match name {
1260        "test" => regexp_test_generic(recv, &args.first().cloned().unwrap_or(Value::Undef)),
1261        "exec" => {
1262            let s = host::to_string_value(&args.first().cloned().unwrap_or(Value::Undef))?;
1263            let s = with_host(|h| h.str_of(&s));
1264            regexp_exec(recv, &s)
1265        }
1266        "toString" => Ok(with_host(|h| {
1267            let s = h.str_of(recv);
1268            h.new_str(s)
1269        })),
1270        // `compile` is a legacy no-op here (the pattern is already compiled).
1271        "compile" => Ok(recv.clone()),
1272        // The symbol-keyed forms ARE the string methods' implementations, so
1273        // each forwards to the same routine with the arguments swapped: the
1274        // subject is the argument here and the receiver there.
1275        "@@match" | "@@matchAll" | "@@search" | "@@split" | "@@replace" => {
1276            let s = with_host(|h| h.str_of(&args.first().cloned().unwrap_or(Value::Undef)));
1277            match name {
1278                "@@match" => str_match(&s, recv),
1279                "@@matchAll" => str_match_all(&s, recv),
1280                "@@search" => str_search(&s, recv),
1281                "@@split" => {
1282                    let limit = args.get(1).and_then(|v| {
1283                        let n = with_host(|h| h.to_number(v));
1284                        n.is_finite().then_some(n.max(0.0) as usize)
1285                    });
1286                    str_split_regex(&s, recv, limit)
1287                }
1288                _ => str_replace_regex(
1289                    &s,
1290                    recv,
1291                    &args.get(1).cloned().unwrap_or(Value::Undef),
1292                    false,
1293                ),
1294            }
1295        }
1296        _ => Err(host::type_error(&format!("{name} is not a function"))),
1297    }
1298}
1299
1300/// Snapshot the fields we need without holding the host borrow across a match.
1301fn regexp_snapshot(recv: &Value) -> Option<(Rc<Engine>, bool, bool, U16Index)> {
1302    with_host(|h| match h.get(recv) {
1303        Some(JsObj::RegExp(r)) => Some((r.re.clone(), r.global, r.sticky, r.last_index)),
1304        _ => None,
1305    })
1306}
1307
1308/// Whether the regexp carries the `d` flag, so its matches report `.indices`.
1309fn has_indices(recv: &Value) -> bool {
1310    with_host(|h| match h.get(recv) {
1311        Some(JsObj::RegExp(r)) => r.flags.contains('d'),
1312        _ => false,
1313    })
1314}
1315
1316fn set_last_index(recv: &Value, idx: U16Index) {
1317    with_host(|h| {
1318        if let Some(JsObj::RegExp(r)) = h.get_mut(recv) {
1319            r.last_index = idx;
1320        }
1321    });
1322}
1323
1324/// Byte offset of a UTF-16 index (clamped to the string length).
1325///
1326/// `lastIndex` and `.index` are UTF-16 code-unit offsets in JS, while the regex
1327/// engine works in UTF-8 byte offsets. Both are `usize`-shaped, so the newtype
1328/// is what stops one being passed where the other belongs.
1329fn byte_of_index(s: &str, n: U16Index) -> usize {
1330    utf16::byte_of_index(s, n)
1331}
1332/// UTF-16 index of a byte offset.
1333fn index_of_byte(s: &str, byte: usize) -> U16Index {
1334    utf16::index_of_byte(s, byte)
1335}
1336
1337/// `re.test(s)` — honoring `g`/`y` `lastIndex` advancement, exactly like `exec`.
1338pub fn regexp_test(recv: &Value, s: &str) -> bool {
1339    let Some((re, global, sticky, last)) = regexp_snapshot(recv) else {
1340        return false;
1341    };
1342    let start_idx = if global || sticky {
1343        last
1344    } else {
1345        U16Index::ZERO
1346    };
1347    if start_idx.get() > utf16::len(s) {
1348        if global || sticky {
1349            set_last_index(recv, U16Index::ZERO);
1350        }
1351        return false;
1352    }
1353    let start_byte = byte_of_index(s, start_idx);
1354    // A backtracking match can fail (catastrophic backtracking guard); treat an
1355    // engine error as "no match" so a pathological pattern never panics the VM.
1356    match re.find_from_pos(s, start_byte) {
1357        Ok(Some(m)) if !sticky || m.start() == start_byte => {
1358            if global || sticky {
1359                set_last_index(recv, index_of_byte(s, m.end()));
1360            }
1361            true
1362        }
1363        _ => {
1364            if global || sticky {
1365                set_last_index(recv, U16Index::ZERO);
1366            }
1367            false
1368        }
1369    }
1370}
1371
1372/// `re.exec(s)` — returns a match array (`[full, ...captures]` with `.index`,
1373/// `.input`, `.groups`), or `null`. Advances `lastIndex` under `g`/`y`.
1374pub fn regexp_exec(recv: &Value, s: &str) -> Result<Value, String> {
1375    let Some((re, global, sticky, last)) = regexp_snapshot(recv) else {
1376        return Ok(with_host(|h| h.null()));
1377    };
1378    let start_idx = if global || sticky {
1379        last
1380    } else {
1381        U16Index::ZERO
1382    };
1383    if start_idx.get() > utf16::len(s) {
1384        if global || sticky {
1385            set_last_index(recv, U16Index::ZERO);
1386        }
1387        return Ok(with_host(|h| h.null()));
1388    }
1389    let start_byte = byte_of_index(s, start_idx);
1390    let caps = re.captures_from_pos(s, start_byte).ok().flatten();
1391    let caps = match caps {
1392        Some(c) if !sticky || c.get(0).map(|m| m.start()) == Some(start_byte) => c,
1393        _ => {
1394            if global || sticky {
1395                set_last_index(recv, U16Index::ZERO);
1396            }
1397            return Ok(with_host(|h| h.null()));
1398        }
1399    };
1400    let whole = caps.get(0).unwrap();
1401    if global || sticky {
1402        set_last_index(recv, index_of_byte(s, whole.end()));
1403    }
1404    Ok(build_match_array(&re, &caps, s, has_indices(recv)))
1405}
1406
1407/// Build the JS match-result array from a `Captures`, attaching `.index`,
1408/// `.input`, and (named-group) `.groups` — plus `.indices` when the regexp
1409/// carried the `d` flag (22.2.7.2 step 34, `MakeMatchIndicesIndexPairArray`).
1410fn build_match_array(re: &Engine, caps: &Caps, s: &str, indices: bool) -> Value {
1411    let mut items: Vec<Value> = Vec::with_capacity(caps.len());
1412    for i in 0..caps.len() {
1413        items.push(match caps.get(i) {
1414            Some(m) => with_host(|h| h.new_str(m.as_str().to_string())),
1415            None => Value::Undef, // a non-participating optional group
1416        });
1417    }
1418    let whole = caps.get(0).unwrap();
1419    let arr = with_host(|h| h.new_array(items));
1420    let index = index_of_byte(s, whole.start()).get();
1421    with_host(|h| {
1422        let idx = Value::Float(index as f64);
1423        h.set_fn_prop(&arr, "index", idx);
1424        let input = h.new_str(s.to_string());
1425        h.set_fn_prop(&arr, "input", input);
1426    });
1427    // Named groups → a `.groups` object (or `undefined` if the regex has none).
1428    let names: Vec<&str> = re.capture_names().flatten().collect();
1429    if indices {
1430        attach_indices(caps, s, &arr, &names);
1431    }
1432    if names.is_empty() {
1433        with_host(|h| h.set_fn_prop(&arr, "groups", Value::Undef));
1434    } else {
1435        let mut g: IndexMap<String, Value> = IndexMap::new();
1436        for name in names {
1437            let v = match caps.name(name) {
1438                Some(m) => with_host(|h| h.new_str(m.as_str().to_string())),
1439                None => Value::Undef,
1440            };
1441            g.insert(name.to_string(), v);
1442        }
1443        with_host(|h| {
1444            let obj = h.new_object(g);
1445            // `groups` is an `OrdinaryObjectCreate(null)` (22.2.7.2 step 30), so
1446            // it inherits nothing and inspects as `[Object: null prototype]`.
1447            let null = h.null();
1448            h.set_proto(&obj, null);
1449            h.set_fn_prop(&arr, "groups", obj);
1450        });
1451    }
1452    arr
1453}
1454
1455/// `MakeMatchIndicesIndexPairArray` (22.2.7.8): a `[start, end]` pair per
1456/// capture — `null` for one that did not participate — with a null-prototype
1457/// `.groups` mirroring the named groups. Offsets are UTF-16 indices, the same
1458/// units `.index` uses.
1459fn attach_indices(caps: &Caps, s: &str, arr: &Value, names: &[&str]) {
1460    let pair = |m: Option<fancy_regex::Match>| match m {
1461        Some(m) => {
1462            let (a, b) = (index_of_byte(s, m.start()), index_of_byte(s, m.end()));
1463            with_host(|h| {
1464                h.new_array(vec![
1465                    Value::Float(a.get() as f64),
1466                    Value::Float(b.get() as f64),
1467                ])
1468            })
1469        }
1470        None => Value::Undef,
1471    };
1472    let mut pairs: Vec<Value> = Vec::with_capacity(caps.len());
1473    for i in 0..caps.len() {
1474        pairs.push(pair(caps.get(i)));
1475    }
1476    let idx_arr = with_host(|h| h.new_array(pairs));
1477    if names.is_empty() {
1478        with_host(|h| h.set_fn_prop(&idx_arr, "groups", Value::Undef));
1479    } else {
1480        let mut g: IndexMap<String, Value> = IndexMap::new();
1481        for name in names {
1482            g.insert((*name).to_string(), pair(caps.name(name)));
1483        }
1484        with_host(|h| {
1485            let obj = h.new_object(g);
1486            let null = h.null();
1487            h.set_proto(&obj, null);
1488            h.set_fn_prop(&idx_arr, "groups", obj);
1489        });
1490    }
1491    with_host(|h| h.set_fn_prop(arr, "indices", idx_arr));
1492}
1493
1494// ── String.prototype regex methods (called from builtins::string_method) ──────
1495
1496/// Every match `RegExpBuiltinExec` produces when driven in a loop from byte
1497/// offset `start` (22.2.6.9 / 22.2.6.11 / 22.2.9.1): each next search begins
1498/// where the last match ended, an EMPTY match steps one character further, and
1499/// under `y` a match must begin exactly where the search does — so a sticky
1500/// scan ends at the first gap rather than skipping over it.
1501fn collect_matches<'s>(re: &Engine, s: &'s str, start: usize, sticky: bool) -> Vec<Caps<'s>> {
1502    let mut out = Vec::new();
1503    let mut pos = start;
1504    while pos <= s.len() {
1505        let Some(caps) = re.captures_from_pos(s, pos).ok().flatten() else {
1506            break;
1507        };
1508        let m = caps.get(0).expect("group 0 always participates");
1509        if sticky && m.start() != pos {
1510            break;
1511        }
1512        pos = match m.end() == m.start() {
1513            true => match s[m.end()..].chars().next() {
1514                Some(c) => m.end() + c.len_utf8(),
1515                None => s.len() + 1,
1516            },
1517            false => m.end(),
1518        };
1519        out.push(caps);
1520    }
1521    out
1522}
1523
1524/// `str.match(re)`: without `g`, same as `exec` (array or null); with `g`, an
1525/// array of every whole-match string (or null if none).
1526pub fn str_match(s: &str, re_val: &Value) -> Result<Value, String> {
1527    let Some((re, global, sticky, _)) = regexp_snapshot(re_val) else {
1528        return Ok(with_host(|h| h.null()));
1529    };
1530    if !global {
1531        // A sticky match is an `exec`: it starts at, and advances, `lastIndex`.
1532        if sticky {
1533            return regexp_exec(re_val, s);
1534        }
1535        // Otherwise it ignores `lastIndex`, searches from the start and — it
1536        // being neither `g` nor `y` — leaves it exactly where it was.
1537        return regexp_exec_from_zero(&re, s, has_indices(re_val));
1538    }
1539    // 22.2.6.9 step 6.a: a global match sets `lastIndex` to 0 before it starts,
1540    // so it always collects from the beginning and leaves it there. It was
1541    // being left wherever the caller had put it.
1542    set_last_index(re_val, U16Index::ZERO);
1543    let matches: Vec<Value> = collect_matches(&re, s, 0, sticky)
1544        .iter()
1545        .map(|c| with_host(|h| h.new_str(c.get(0).map_or("", |m| m.as_str()).to_string())))
1546        .collect();
1547    if matches.is_empty() {
1548        Ok(with_host(|h| h.null()))
1549    } else {
1550        Ok(with_host(|h| h.new_array(matches)))
1551    }
1552}
1553
1554/// Non-global exec searching from offset 0 (for `str.match` without `g`).
1555fn regexp_exec_from_zero(re: &Engine, s: &str, indices: bool) -> Result<Value, String> {
1556    match re.captures(s).ok().flatten() {
1557        Some(caps) => Ok(build_match_array(re, &caps, s, indices)),
1558        None => Ok(with_host(|h| h.null())),
1559    }
1560}
1561
1562/// `str.matchAll(re)`: an iterator over every match array (requires the `g` flag
1563/// in Node, but we accept a non-global regex too and still iterate all matches).
1564pub fn str_match_all(s: &str, re_val: &Value) -> Result<Value, String> {
1565    let Some((re, global, sticky, last)) = regexp_snapshot(re_val) else {
1566        return Ok(with_host(|h| h.new_array(Vec::new())));
1567    };
1568    let indices = has_indices(re_val);
1569    // 22.1.3.14 step 5.c: a non-global regexp is a TypeError, because
1570    // `matchAll` cannot produce every match without `g` — the same rule
1571    // `replaceAll` enforces. This used to return just the first match.
1572    if !global {
1573        return Err(host::type_error(
1574            "String.prototype.matchAll called with a non-global RegExp argument",
1575        ));
1576    }
1577    // 22.2.6.9 `@@matchAll` clones the regexp with the ORIGINAL's `lastIndex`,
1578    // so the scan begins there rather than at 0.
1579    let mut items = Vec::new();
1580    if last.get() <= utf16::len(s) {
1581        let start = byte_of_index(s, last);
1582        for caps in collect_matches(&re, s, start, sticky) {
1583            items.push(build_match_array(&re, &caps, s, indices));
1584        }
1585    }
1586    // Return a live iterator so `for-of`/spread/`Array.from` all work.
1587    Ok(with_host(|h| {
1588        h.alloc_iter(JsObj::Iter {
1589            items,
1590            idx: 0,
1591            array: None,
1592            brand: Some("RegExp String Iterator"),
1593        })
1594    }))
1595}
1596
1597/// `str.search(re)`: char index of the first match, or -1.
1598pub fn str_search(s: &str, re_val: &Value) -> Result<Value, String> {
1599    let Some((re, _, sticky, _)) = regexp_snapshot(re_val) else {
1600        return Ok(Value::Float(-1.0));
1601    };
1602    // 22.2.6.12 runs the exec with `lastIndex` 0, so a sticky regexp can only
1603    // match AT the start; `lastIndex` itself is restored afterwards.
1604    Ok(match re.find(s).ok().flatten() {
1605        Some(m) if !sticky || m.start() == 0 => {
1606            Value::Float(index_of_byte(s, m.start()).get() as f64)
1607        }
1608        _ => Value::Float(-1.0),
1609    })
1610}
1611
1612/// `str.split(re[, limit])`: split on regex matches; captured groups are spliced
1613/// into the output (JS semantics).
1614/// `String.prototype.split(regexp[, limit])` — 22.2.6.14 `RegExp.prototype
1615/// [@@split]`.
1616///
1617/// The previous shape of this was a `captures_iter` with one hand-rolled
1618/// special case for a zero-width match at position 0, and it got every other
1619/// empty-match position wrong: `'ab'.split(/(?:)/)` grew a trailing `""`,
1620/// `''.split(/(?:)/)` answered `[""]` instead of `[]`, and `'ab'.split(/()/)`
1621/// answered five elements instead of three.
1622///
1623/// The spec loop is what gets those right, and the single rule doing the work
1624/// is `e == p`: a match ENDING where the previous piece began contributes
1625/// nothing and only advances the scan. The final piece is always the tail from
1626/// `p`, appended after the loop — which is why an empty match at the very end
1627/// does not produce an extra `""` (the loop stops at `q == size` before ever
1628/// matching there) while a real separator at the end does.
1629///
1630/// The scan is in UTF-16 code units, since that is what the spec indexes and
1631/// what `.index`/`lastIndex` report elsewhere in this file. Where the spec
1632/// advances `q` one position at a time until a match occurs AT `q`, this jumps
1633/// straight to the next match at or after `q`: every position skipped is one
1634/// the spec would have failed to match, so the two agree.
1635///
1636/// One divergence remains and is not fixable here: a lone surrogate cannot be
1637/// represented in a Rust `String`, so a split position INSIDE an astral
1638/// character does not exist to be split at. `'\u{1F600}a'.split(/(?:)/)` is
1639/// `['\u{1F600}', 'a']` here and three elements in node, which splits the
1640/// surrogate pair. `'\u{1F600}'.split('')` has always had the same limit; it
1641/// is the string representation, not this algorithm.
1642pub fn str_split_regex(s: &str, re_val: &Value, limit: Option<usize>) -> Result<Value, String> {
1643    let Some((re, _, _, _)) = regexp_snapshot(re_val) else {
1644        return Ok(with_host(|h| h.new_array(Vec::new())));
1645    };
1646    let lim = limit.unwrap_or(usize::MAX);
1647    if lim == 0 {
1648        return Ok(with_host(|h| h.new_array(Vec::new())));
1649    }
1650    let size = utf16::len(s);
1651    let units = |i: usize| byte_of_index(s, U16Index::new(i));
1652
1653    // An empty subject splits to nothing when the separator can match it, and
1654    // to `[""]`... which is the subject itself, when it cannot.
1655    if size == 0 {
1656        let out = if matches!(re.find(s), Ok(Some(_))) {
1657            Vec::new()
1658        } else {
1659            vec![with_host(|h| h.new_str(String::new()))]
1660        };
1661        return Ok(with_host(|h| h.new_array(out)));
1662    }
1663
1664    let mut out: Vec<Value> = Vec::new();
1665    let mut p = 0usize; // start of the piece being accumulated
1666    let mut q = 0usize; // scan position
1667    while q < size {
1668        let Some(caps) = re.captures_from_pos(s, units(q)).ok().flatten() else {
1669            break;
1670        };
1671        let m = caps.get(0).expect("group 0 always participates");
1672        let m_start = index_of_byte(s, m.start()).get();
1673        // The spec scans `q` only while `q < size` and requires the match to be
1674        // AT `q`, so a match starting at the very end is never reached. Jumping
1675        // to the next match does reach it, and letting it through appended a
1676        // spurious trailing `""` for every end-anchored zero-width separator —
1677        // `/$/`, `/\b/`, a trailing lookbehind.
1678        if m_start >= size {
1679            break;
1680        }
1681        let e = index_of_byte(s, m.end()).get().min(size);
1682        if e == p {
1683            // Contributes no piece; step past this position and rescan.
1684            //
1685            // The step is off `q`, not off `m_start`, because the two can move
1686            // backwards relative to each other: a unit index that falls INSIDE
1687            // an astral character has no byte offset of its own, so the search
1688            // starts at the character's first byte and reports a match before
1689            // `q`. Stepping off `m_start` there left `q` pinned and the loop
1690            // spun forever on `'\u{1F600}a'.split(/(?:)/)`.
1691            q = m_start.max(q) + 1;
1692            continue;
1693        }
1694        out.push(with_host(|h| {
1695            h.new_str(utf16::Units::of(s).slice(p, m_start))
1696        }));
1697        if out.len() >= lim {
1698            return Ok(with_host(|h| h.new_array(out)));
1699        }
1700        for i in 1..caps.len() {
1701            out.push(match caps.get(i) {
1702                Some(g) => with_host(|h| h.new_str(g.as_str().to_string())),
1703                None => Value::Undef,
1704            });
1705            if out.len() >= lim {
1706                return Ok(with_host(|h| h.new_array(out)));
1707            }
1708        }
1709        p = e;
1710        q = p;
1711    }
1712    out.push(with_host(|h| h.new_str(utf16::Units::of(s).slice(p, size))));
1713    out.truncate(lim);
1714    Ok(with_host(|h| h.new_array(out)))
1715}
1716
1717/// `str.replace(re, repl)` / `str.replaceAll(re, repl)`. `repl` is either a string
1718/// (with `$1`/`$&`/`` $` ``/`$'`/`$<name>`/`$$` patterns) or a function replacer.
1719pub fn str_replace_regex(
1720    s: &str,
1721    re_val: &Value,
1722    repl: &Value,
1723    all: bool,
1724) -> Result<Value, String> {
1725    let Some((re, global, sticky, last_index)) = regexp_snapshot(re_val) else {
1726        return Ok(with_host(|h| h.new_str(s.to_string())));
1727    };
1728    let replace_all = all || global;
1729    let has_named_groups = re.capture_names().flatten().next().is_some();
1730    let is_fn = with_host(|h| host::is_callable(h, repl));
1731
1732    let mut out = String::new();
1733    let mut last = 0usize;
1734    let mut count = 0;
1735    // Which matches the replace sees. A global one collects them all from 0; a
1736    // sticky one that is not global makes ONE `exec` at `lastIndex` and moves
1737    // `lastIndex` to its end (or back to 0 on failure); a plain one takes the
1738    // first match from the start.
1739    let found: Vec<Caps> = if global {
1740        collect_matches(&re, s, 0, sticky)
1741    } else if sticky {
1742        let all_from_here = if last_index.get() <= utf16::len(s) {
1743            collect_matches(&re, s, byte_of_index(s, last_index), true)
1744        } else {
1745            Vec::new()
1746        };
1747        let first: Vec<Caps> = all_from_here.into_iter().take(1).collect();
1748        let next = first
1749            .first()
1750            .and_then(|c| c.get(0))
1751            .map_or(U16Index::ZERO, |m| index_of_byte(s, m.end()));
1752        set_last_index(re_val, next);
1753        first
1754    } else {
1755        collect_matches(&re, s, 0, false)
1756    };
1757    for caps in found {
1758        let m = caps.get(0).unwrap();
1759        out.push_str(&s[last..m.start()]);
1760        if is_fn {
1761            // fn(match, p1, …, offset, whole_string)
1762            let mut call_args: Vec<Value> = Vec::new();
1763            for i in 0..caps.len() {
1764                call_args.push(match caps.get(i) {
1765                    Some(g) => with_host(|h| h.new_str(g.as_str().to_string())),
1766                    None => Value::Undef,
1767                });
1768            }
1769            call_args.push(Value::Float(index_of_byte(s, m.start()).get() as f64));
1770            call_args.push(with_host(|h| h.new_str(s.to_string())));
1771            // 22.1.3.19: when the pattern has named groups the callback takes a
1772            // final `groups` argument. Omitting it left `arguments.length` at 4
1773            // where node reports 5, and destructuring the groups out of the last
1774            // parameter saw the subject string.
1775            if let Some(groups) = named_groups_object(&re, &caps) {
1776                call_args.push(groups);
1777            }
1778            let r = host::invoke(repl, call_args, None)?;
1779            out.push_str(&with_host(|h| h.str_of(&r)));
1780        } else {
1781            let repl_str = with_host(|h| h.str_of(repl));
1782            out.push_str(&expand_replacement(&repl_str, &caps, s, has_named_groups));
1783        }
1784        last = m.end();
1785        count += 1;
1786        if !replace_all && count >= 1 {
1787            break;
1788        }
1789    }
1790    out.push_str(&s[last..]);
1791    // 22.2.6.11 step 8: a GLOBAL regexp has its `lastIndex` set to 0 by the
1792    // replace, so the next use starts from the beginning. It was left wherever
1793    // the caller had put it, which made a shared `/…/g` skip the front of the
1794    // string on its next `test`/`exec`.
1795    if global {
1796        set_last_index(re_val, U16Index::ZERO);
1797    }
1798    Ok(with_host(|h| h.new_str(out)))
1799}
1800
1801/// Expand a replacement template's `$` patterns against a match.
1802/// The `groups` object for a match — `OrdinaryObjectCreate(null)` carrying each
1803/// named capture (22.2.7.2 step 30), or `None` when the pattern names none.
1804fn named_groups_object(re: &Engine, caps: &Caps) -> Option<Value> {
1805    let names: Vec<&str> = re.capture_names().flatten().collect();
1806    if names.is_empty() {
1807        return None;
1808    }
1809    let mut g: IndexMap<String, Value> = IndexMap::new();
1810    for name in names {
1811        let v = match caps.name(name) {
1812            Some(m) => with_host(|h| h.new_str(m.as_str().to_string())),
1813            None => Value::Undef,
1814        };
1815        g.insert(name.to_string(), v);
1816    }
1817    Some(with_host(|h| {
1818        let obj = h.new_object(g);
1819        let null = h.null();
1820        h.set_proto(&obj, null);
1821        obj
1822    }))
1823}
1824
1825fn expand_replacement(templ: &str, caps: &Caps, s: &str, has_named_groups: bool) -> String {
1826    let chars: Vec<char> = templ.chars().collect();
1827    let mut out = String::new();
1828    let mut i = 0;
1829    let whole = caps.get(0).unwrap();
1830    while i < chars.len() {
1831        if chars[i] == '$' && i + 1 < chars.len() {
1832            let n = chars[i + 1];
1833            match n {
1834                '$' => {
1835                    out.push('$');
1836                    i += 2;
1837                }
1838                '&' => {
1839                    out.push_str(whole.as_str());
1840                    i += 2;
1841                }
1842                '`' => {
1843                    out.push_str(&s[..whole.start()]);
1844                    i += 2;
1845                }
1846                '\'' => {
1847                    out.push_str(&s[whole.end()..]);
1848                    i += 2;
1849                }
1850                // `$<name>` is a named-group reference only when the pattern has
1851                // named groups (22.1.3.19.1 GetSubstitution): without any, `$<`
1852                // is literal text, and so is `$<` with no closing `>`.
1853                '<' if has_named_groups && chars[i + 2..].contains(&'>') => {
1854                    let close = i + 2 + chars[i + 2..].iter().position(|c| *c == '>').unwrap_or(0);
1855                    let name: String = chars[i + 2..close].iter().collect();
1856                    if let Some(m) = caps.name(&name) {
1857                        out.push_str(m.as_str());
1858                    }
1859                    i = close + 1;
1860                }
1861                d if d.is_ascii_digit() => {
1862                    // `$1`..`$99`: prefer a two-digit group if it exists.
1863                    let d2 = chars.get(i + 2).copied().filter(|c| c.is_ascii_digit());
1864                    let two = d2.and_then(|c2| format!("{d}{c2}").parse::<usize>().ok());
1865                    if let Some(gi) = two.filter(|gi| *gi < caps.len()) {
1866                        if let Some(g) = caps.get(gi) {
1867                            out.push_str(g.as_str());
1868                        }
1869                        i += 3;
1870                    } else {
1871                        let gi = d.to_digit(10).unwrap() as usize;
1872                        if gi >= 1 && gi < caps.len() {
1873                            if let Some(g) = caps.get(gi) {
1874                                out.push_str(g.as_str());
1875                            }
1876                            i += 2;
1877                        } else {
1878                            out.push('$');
1879                            i += 1;
1880                        }
1881                    }
1882                }
1883                _ => {
1884                    out.push('$');
1885                    i += 1;
1886                }
1887            }
1888        } else {
1889            out.push(chars[i]);
1890            i += 1;
1891        }
1892    }
1893    out
1894}