atmos/os_lib/js/
regex.rs

1//! 小さなバックトラッキング正規表現エンジン。
2//!
3//! パターンを命令列（バックトラッキング VM のバイトコード）へコンパイルし、再帰で実行する。
4//! 暴走（catastrophic backtracking）からカーネルを守るため **実行予算**で打ち切る。
5//!
6//! 対応: リテラル・`.`・文字クラス `[...]`/`[^...]`（範囲・`\d\w\s` 等）・アンカー `^ $`・
7//! 量指定子 `* + ? {n} {n,} {n,m}`（貪欲/非貪欲）・グループ `(...)`/`(?:...)`・選択 `|`・
8//! 後方参照 `\1`・単語境界 `\b \B`。フラグ: `i`(無視) `m`(複数行) `s`(dotall) `g`(グローバル)。
9
10use alloc::boxed::Box;
11use alloc::string::String;
12use alloc::vec;
13use alloc::vec::Vec;
14
15/// 文字クラスの 1 要素。
16#[derive(Clone)]
17enum ClassItem {
18    Ch(char),
19    Range(char, char),
20    Digit,
21    NotDigit,
22    Word,
23    NotWord,
24    Space,
25    NotSpace,
26    UnicodeProp(String, bool),
27}
28
29#[derive(Clone)]
30struct ClassData {
31    negate: bool,
32    items: Vec<ClassItem>,
33}
34
35impl ClassData {
36    fn matches(&self, c: char, ignorecase: bool) -> bool {
37        let hit = self.items.iter().any(|it| item_match(it, c, ignorecase));
38        hit ^ self.negate
39    }
40}
41
42fn item_match(it: &ClassItem, c: char, ignorecase: bool) -> bool {
43    match it {
44        ClassItem::Ch(x) => eqc(*x, c, ignorecase),
45        ClassItem::Range(a, b) => {
46            if *a <= c && c <= *b {
47                return true;
48            }
49            if ignorecase {
50                let lc = c.to_ascii_lowercase();
51                let uc = c.to_ascii_uppercase();
52                (*a <= lc && lc <= *b) || (*a <= uc && uc <= *b)
53            } else {
54                false
55            }
56        }
57        ClassItem::Digit => c.is_ascii_digit(),
58        ClassItem::NotDigit => !c.is_ascii_digit(),
59        ClassItem::Word => c == '_' || c.is_ascii_alphanumeric(),
60        ClassItem::NotWord => !(c == '_' || c.is_ascii_alphanumeric()),
61        ClassItem::Space => c.is_whitespace(),
62        ClassItem::NotSpace => !c.is_whitespace(),
63        ClassItem::UnicodeProp(prop, negate) => {
64            let hit = match prop.as_str() {
65                "ASCII" => c.is_ascii(),
66                "Letter" | "L" => c.is_alphabetic(),
67                "Number" | "N" => c.is_numeric(),
68                "Punctuation" | "P" => c.is_ascii_punctuation(),
69                "Symbol" | "S" => c.is_ascii_punctuation() || (!c.is_alphanumeric() && !c.is_whitespace()),
70                "Separator" | "Z" | "Space" => c.is_whitespace(),
71                _ => c.is_alphanumeric(),
72            };
73            hit ^ negate
74        }
75    }
76}
77
78fn eqc(a: char, b: char, ignorecase: bool) -> bool {
79    if a == b {
80        return true;
81    }
82    ignorecase && a.eq_ignore_ascii_case(&b)
83}
84
85fn is_word(c: char) -> bool {
86    c == '_' || c.is_ascii_alphanumeric()
87}
88
89// ---- パース木 ----
90
91enum Node {
92    Empty,
93    Char(char),
94    Any,
95    Class(ClassData),
96    Start,
97    End,
98    WordBoundary(bool), // true=\b, false=\B
99    Group {
100        idx: Option<usize>,
101        node: Box<Node>,
102    },
103    Concat(Vec<Node>),
104    Alt(Vec<Node>),
105    Repeat {
106        node: Box<Node>,
107        min: usize,
108        max: Option<usize>,
109        greedy: bool,
110    },
111    Backref(usize),
112    /// 先読み `(?=…)`/`(?!…)`・後読み `(?<=…)`/`(?<!…)`（位置を進めない）。
113    Look {
114        ahead: bool,
115        negate: bool,
116        node: Box<Node>,
117    },
118}
119
120// ---- VM 命令 ----
121
122enum Inst {
123    Char(char),
124    Any,
125    Class(ClassData),
126    Match,
127    Jmp(usize),
128    Split(usize, usize),
129    Save(usize),
130    AssertStart,
131    AssertEnd,
132    WordBoundary(bool),
133    Backref(usize),
134    /// 先読み・後読み。直後から `next` の手前までが部分プログラム（`Match` で終わる。
135    /// 後読みは `LookBehindEnd` の後に `Match`）。成否だけを見て位置は進めない。
136    Look {
137        ahead: bool,
138        negate: bool,
139        next: usize,
140    },
141    /// 後読みの部分プログラムの終端: 位置が後読みを始めた位置（caps の末尾に積んだ値）と一致するか。
142    LookBehindEnd,
143}
144
145pub struct Regex {
146    prog: Vec<Inst>,
147    pub ngroups: usize,
148    pub ignorecase: bool,
149    pub multiline: bool,
150    pub dotall: bool,
151    pub global: bool,
152    pub sticky: bool,
153    /// `d`（hasIndices）フラグ。true なら `exec()` の結果に各キャプチャの
154    /// [start,end) 文字インデックスを持つ `indices` 配列を追加する。
155    pub has_indices: bool,
156    pub unicode: bool,
157    pub unicode_sets: bool,
158    pub source: String,
159    pub flags: String,
160    /// 名前付きキャプチャグループ `(?<name>...)`（ES2018）の (名前, グループ番号) 一覧。
161    /// 一つも無ければ空（`exec()` の `groups` プロパティは `undefined` になる）。
162    pub group_names: Vec<(String, usize)>,
163}
164
165/// 1 マッチ結果。captures[0] が全体、以降が各グループ（None は不参加）。
166pub struct Match {
167    pub start: usize,
168    pub end: usize,
169    pub captures: Vec<Option<(usize, usize)>>,
170}
171
172/// JS `RegExp` オブジェクトの内部状態（コンパイル済み + lastIndex）。
173pub struct RegExpData {
174    pub re: Regex,
175    pub last_index: usize,
176}
177
178struct Parser {
179    chars: Vec<char>,
180    pos: usize,
181    ngroups: usize,
182    /// 名前付きキャプチャグループ `(?<name>...)`（ES2018）の (名前, グループ番号) 一覧。
183    group_names: Vec<(String, usize)>,
184}
185
186impl Regex {
187    /// パターンとフラグからコンパイル。失敗時はリテラル一致にフォールバック。
188    pub fn new(pattern: &str, flags: &str) -> Regex {
189        let mut p = Parser {
190            chars: pattern.chars().collect(),
191            pos: 0,
192            ngroups: 0,
193            group_names: Vec::new(),
194        };
195        let node = p.parse_alt();
196        let ngroups = p.ngroups;
197        let group_names = p.group_names;
198        // コンパイル: Save(0) <body> Save(1) Match
199        let mut prog = Vec::new();
200        prog.push(Inst::Save(0));
201        compile(&node, &mut prog);
202        prog.push(Inst::Save(1));
203        prog.push(Inst::Match);
204        Regex {
205            prog,
206            ngroups,
207            ignorecase: flags.contains('i'),
208            multiline: flags.contains('m'),
209            dotall: flags.contains('s'),
210            global: flags.contains('g'),
211            sticky: flags.contains('y'),
212            has_indices: flags.contains('d'),
213            unicode: flags.contains('u'),
214            unicode_sets: flags.contains('v'),
215            source: String::from(pattern),
216            flags: String::from(flags),
217            group_names,
218        }
219    }
220
221    /// `start` 以降で最初のマッチを探す。
222    pub fn find_at(&self, subject: &[char], start: usize) -> Option<Match> {
223        for sp in start..=subject.len() {
224            if let Some(m) = self.try_match_at(subject, sp) {
225                return Some(m);
226            }
227        }
228        None
229    }
230
231    /// `y`（sticky）フラグ用: `start` の位置でのみマッチを試みる（前方探索しない）。
232    /// 通常の `find_at` と違い、その場所で一致しなければ探索を打ち切って `None` を返す。
233    pub fn find_exact_at(&self, subject: &[char], start: usize) -> Option<Match> {
234        if start > subject.len() {
235            return None;
236        }
237        self.try_match_at(subject, start)
238    }
239
240    fn try_match_at(&self, subject: &[char], sp: usize) -> Option<Match> {
241        let nslots = 2 * (self.ngroups + 1);
242        let mut caps: Vec<isize> = vec![-1; nslots];
243        let mut budget: u32 = 600_000;
244        if self.run(0, subject, sp, &mut caps, &mut budget) {
245            let s = caps[0].max(0) as usize;
246            let e = caps[1].max(0) as usize;
247            let mut captures = Vec::with_capacity(self.ngroups + 1);
248            for g in 0..=self.ngroups {
249                let a = caps[2 * g];
250                let b = caps[2 * g + 1];
251                if a >= 0 && b >= 0 {
252                    captures.push(Some((a as usize, b as usize)));
253                } else {
254                    captures.push(None);
255                }
256            }
257            Some(Match {
258                start: s,
259                end: e,
260                captures,
261            })
262        } else {
263            None
264        }
265    }
266
267    fn run(
268        &self,
269        mut pc: usize,
270        s: &[char],
271        mut sp: usize,
272        caps: &mut Vec<isize>,
273        budget: &mut u32,
274    ) -> bool {
275        loop {
276            if *budget == 0 {
277                return false;
278            }
279            *budget -= 1;
280            match &self.prog[pc] {
281                Inst::Match => return true,
282                Inst::Char(c) => {
283                    if sp < s.len() && eqc(*c, s[sp], self.ignorecase) {
284                        pc += 1;
285                        sp += 1;
286                    } else {
287                        return false;
288                    }
289                }
290                Inst::Any => {
291                    if sp < s.len() && (self.dotall || s[sp] != '\n') {
292                        pc += 1;
293                        sp += 1;
294                    } else {
295                        return false;
296                    }
297                }
298                Inst::Class(cd) => {
299                    if sp < s.len() && cd.matches(s[sp], self.ignorecase) {
300                        pc += 1;
301                        sp += 1;
302                    } else {
303                        return false;
304                    }
305                }
306                Inst::Jmp(x) => pc = *x,
307                Inst::Split(a, b) => {
308                    let (a, b) = (*a, *b);
309                    let saved = caps.clone();
310                    if self.run(a, s, sp, caps, budget) {
311                        return true;
312                    }
313                    *caps = saved;
314                    pc = b;
315                }
316                Inst::Save(n) => {
317                    let n = *n;
318                    let old = caps[n];
319                    caps[n] = sp as isize;
320                    if self.run(pc + 1, s, sp, caps, budget) {
321                        return true;
322                    }
323                    caps[n] = old;
324                    return false;
325                }
326                Inst::AssertStart => {
327                    let ok = sp == 0 || (self.multiline && sp > 0 && s[sp - 1] == '\n');
328                    if ok {
329                        pc += 1;
330                    } else {
331                        return false;
332                    }
333                }
334                Inst::AssertEnd => {
335                    let ok = sp == s.len() || (self.multiline && s[sp] == '\n');
336                    if ok {
337                        pc += 1;
338                    } else {
339                        return false;
340                    }
341                }
342                Inst::WordBoundary(want) => {
343                    let before = sp > 0 && is_word(s[sp - 1]);
344                    let after = sp < s.len() && is_word(s[sp]);
345                    let boundary = before != after;
346                    if boundary == *want {
347                        pc += 1;
348                    } else {
349                        return false;
350                    }
351                }
352                Inst::Look { ahead, negate, next } => {
353                    let (ahead, negate, next) = (*ahead, *negate, *next);
354                    let saved = caps.clone();
355                    let matched = if ahead {
356                        self.run(pc + 1, s, sp, caps, budget)
357                    } else {
358                        // 後読み: 終端が sp になる開始位置を近い方から探す。
359                        let mut found = false;
360                        let mut k = sp as isize;
361                        while k >= 0 {
362                            caps.push(sp as isize);
363                            let ok = self.run(pc + 1, s, k as usize, caps, budget);
364                            if ok {
365                                // 積んだ終端値を外す（部分実行中に caps が伸びた分も含めて元の長さへ）。
366                                caps.truncate(saved.len());
367                                found = true;
368                                break;
369                            }
370                            *caps = saved.clone();
371                            k -= 1;
372                        }
373                        found
374                    };
375                    if matched == negate {
376                        *caps = saved;
377                        return false;
378                    }
379                    let base_len = saved.len();
380                    if negate {
381                        // 否定の中のキャプチャは残さない。
382                        *caps = saved;
383                    }
384                    caps.truncate(base_len);
385                    pc = next;
386                }
387                Inst::LookBehindEnd => {
388                    if caps.last().copied() == Some(sp as isize) {
389                        pc += 1;
390                    } else {
391                        return false;
392                    }
393                }
394                Inst::Backref(idx) => {
395                    let (a, b) = (caps[2 * idx], caps[2 * idx + 1]);
396                    if a < 0 || b < 0 {
397                        pc += 1;
398                        continue;
399                    } // 未参加グループは空一致。
400                    let (a, b) = (a as usize, b as usize);
401                    let len = b - a;
402                    if sp + len <= s.len()
403                        && (0..len).all(|k| eqc(s[a + k], s[sp + k], self.ignorecase))
404                    {
405                        sp += len;
406                        pc += 1;
407                    } else {
408                        return false;
409                    }
410                }
411            }
412        }
413    }
414}
415
416fn compile(node: &Node, prog: &mut Vec<Inst>) {
417    match node {
418        Node::Empty => {}
419        Node::Char(c) => prog.push(Inst::Char(*c)),
420        Node::Any => prog.push(Inst::Any),
421        Node::Class(cd) => prog.push(Inst::Class(cd.clone())),
422        Node::Start => prog.push(Inst::AssertStart),
423        Node::End => prog.push(Inst::AssertEnd),
424        Node::WordBoundary(b) => prog.push(Inst::WordBoundary(*b)),
425        Node::Backref(i) => prog.push(Inst::Backref(*i)),
426        Node::Look { ahead, negate, node } => {
427            let look_pc = prog.len();
428            prog.push(Inst::Look { ahead: *ahead, negate: *negate, next: 0 });
429            compile(node, prog);
430            if !*ahead {
431                prog.push(Inst::LookBehindEnd);
432            }
433            prog.push(Inst::Match);
434            let next = prog.len();
435            if let Inst::Look { next: n, .. } = &mut prog[look_pc] {
436                *n = next;
437            }
438        }
439        Node::Concat(items) => {
440            for it in items {
441                compile(it, prog);
442            }
443        }
444        Node::Group { idx, node } => {
445            if let Some(i) = idx {
446                prog.push(Inst::Save(2 * i));
447            }
448            compile(node, prog);
449            if let Some(i) = idx {
450                prog.push(Inst::Save(2 * i + 1));
451            }
452        }
453        Node::Alt(branches) => {
454            // Split で分岐し、各枝の末尾を最後へ Jmp。
455            let mut jmp_fixups = Vec::new();
456            for (k, br) in branches.iter().enumerate() {
457                if k + 1 < branches.len() {
458                    let split_pc = prog.len();
459                    prog.push(Inst::Split(0, 0)); // 後で埋める
460                    let l1 = prog.len();
461                    compile(br, prog);
462                    let jmp_pc = prog.len();
463                    prog.push(Inst::Jmp(0));
464                    jmp_fixups.push(jmp_pc);
465                    let l2 = prog.len();
466                    if let Inst::Split(a, b) = &mut prog[split_pc] {
467                        *a = l1;
468                        *b = l2;
469                    }
470                } else {
471                    compile(br, prog);
472                }
473            }
474            let end = prog.len();
475            for j in jmp_fixups {
476                if let Inst::Jmp(x) = &mut prog[j] {
477                    *x = end;
478                }
479            }
480        }
481        Node::Repeat {
482            node,
483            min,
484            max,
485            greedy,
486        } => {
487            // 下限分を必須展開。
488            for _ in 0..*min {
489                compile(node, prog);
490            }
491            match max {
492                None => {
493                    // {min,}: 残りは * 相当のループ。
494                    let l1 = prog.len();
495                    let split_pc = prog.len();
496                    prog.push(Inst::Split(0, 0));
497                    let body = prog.len();
498                    compile(node, prog);
499                    prog.push(Inst::Jmp(l1));
500                    let after = prog.len();
501                    if let Inst::Split(a, b) = &mut prog[split_pc] {
502                        if *greedy {
503                            *a = body;
504                            *b = after;
505                        } else {
506                            *a = after;
507                            *b = body;
508                        }
509                    }
510                }
511                Some(mx) => {
512                    // {min,max}: 追加 (max-min) 回をオプション展開。
513                    let opt = mx.saturating_sub(*min);
514                    let mut split_fixups = Vec::new();
515                    for _ in 0..opt {
516                        let split_pc = prog.len();
517                        prog.push(Inst::Split(0, 0));
518                        let body = prog.len();
519                        compile(node, prog);
520                        split_fixups.push((split_pc, body));
521                    }
522                    let after = prog.len();
523                    for (sp_pc, body) in split_fixups {
524                        if let Inst::Split(a, b) = &mut prog[sp_pc] {
525                            if *greedy {
526                                *a = body;
527                                *b = after;
528                            } else {
529                                *a = after;
530                                *b = body;
531                            }
532                        }
533                    }
534                }
535            }
536        }
537    }
538}
539
540impl Parser {
541    fn peek(&self) -> Option<char> {
542        self.chars.get(self.pos).copied()
543    }
544    fn peek_at(&self, offset: usize) -> Option<char> {
545        self.chars.get(self.pos + offset).copied()
546    }
547    fn bump(&mut self) -> Option<char> {
548        let c = self.peek();
549        if c.is_some() {
550            self.pos += 1;
551        }
552        c
553    }
554    fn eat(&mut self, c: char) -> bool {
555        if self.peek() == Some(c) {
556            self.pos += 1;
557            true
558        } else {
559            false
560        }
561    }
562
563    fn parse_alt(&mut self) -> Node {
564        let mut branches = vec![self.parse_concat()];
565        while self.eat('|') {
566            branches.push(self.parse_concat());
567        }
568        if branches.len() == 1 {
569            branches.pop().unwrap_or(Node::Empty)
570        } else {
571            Node::Alt(branches)
572        }
573    }
574
575    fn parse_concat(&mut self) -> Node {
576        let mut items = Vec::new();
577        while let Some(c) = self.peek() {
578            if c == '|' || c == ')' {
579                break;
580            }
581            let atom = self.parse_atom();
582            let quantified = self.parse_quantifier(atom);
583            items.push(quantified);
584        }
585        if items.is_empty() {
586            Node::Empty
587        } else if items.len() == 1 {
588            items.pop().unwrap_or(Node::Empty)
589        } else {
590            Node::Concat(items)
591        }
592    }
593
594    fn parse_quantifier(&mut self, atom: Node) -> Node {
595        let (min, max) = match self.peek() {
596            Some('*') => {
597                self.bump();
598                (0, None)
599            }
600            Some('+') => {
601                self.bump();
602                (1, None)
603            }
604            Some('?') => {
605                self.bump();
606                (0, Some(1))
607            }
608            Some('{') => {
609                if let Some((mn, mx)) = self.try_parse_brace() {
610                    (mn, mx)
611                } else {
612                    return atom;
613                }
614            }
615            _ => return atom,
616        };
617        let greedy = !self.eat('?'); // 後置 ? で非貪欲。
618        Node::Repeat {
619            node: Box::new(atom),
620            min,
621            max,
622            greedy,
623        }
624    }
625
626    fn try_parse_brace(&mut self) -> Option<(usize, Option<usize>)> {
627        let save = self.pos;
628        self.bump(); // {
629        let mut min_s = String::new();
630        while let Some(c) = self.peek() {
631            if c.is_ascii_digit() {
632                min_s.push(c);
633                self.bump();
634            } else {
635                break;
636            }
637        }
638        if min_s.is_empty() {
639            self.pos = save;
640            return None;
641        }
642        let min: usize = min_s.parse().unwrap_or(0);
643        let max = if self.eat(',') {
644            let mut max_s = String::new();
645            while let Some(c) = self.peek() {
646                if c.is_ascii_digit() {
647                    max_s.push(c);
648                    self.bump();
649                } else {
650                    break;
651                }
652            }
653            if max_s.is_empty() {
654                None
655            } else {
656                Some(max_s.parse().unwrap_or(min))
657            }
658        } else {
659            Some(min)
660        };
661        if !self.eat('}') {
662            self.pos = save;
663            return None;
664        }
665        Some((min, max))
666    }
667
668    fn parse_atom(&mut self) -> Node {
669        match self.peek() {
670            Some('(') => {
671                self.bump();
672                let mut group_name: Option<String> = None;
673                let idx = if self.peek() == Some('?') {
674                    self.bump(); // ?
675                    // 名前付きキャプチャグループ `(?<name>...)`（ES2018）。lookbehind の
676                    // `(?<=...)`/`(?<!...)` と先頭が同じなので、`<` の次が `=`/`!` なら
677                    // 除外する（lookbehind 自体はこのエンジン未対応で、他の `(?...)` と同じ
678                    // 非キャプチャへのフォールバックのまま）。
679                    if self.peek() == Some('<') && !matches!(self.peek_at(1), Some('=') | Some('!'))
680                    {
681                        self.bump(); // <
682                        let mut name = String::new();
683                        while let Some(c) = self.peek() {
684                            if c == '>' {
685                                break;
686                            }
687                            name.push(c);
688                            self.bump();
689                        }
690                        self.bump(); // >
691                        self.ngroups += 1;
692                        group_name = Some(name);
693                        Some(self.ngroups)
694                    } else {
695                        // 先読み (?= (?! ・後読み (?<= (?<!。【2026-10-17】従来は非キャプチャ群
696                        // として文字を消費しており、Closure の URL 分解（`(?=[\\/?#]|$)`）が
697                        // パス先頭の "/" を食べていた（YouTube の動画サーバ URL が壊れた）。
698                        let look = match (self.peek(), self.peek_at(1)) {
699                            (Some('='), _) => Some((true, false, 1)),
700                            (Some('!'), _) => Some((true, true, 1)),
701                            (Some('<'), Some('=')) => Some((false, false, 2)),
702                            (Some('<'), Some('!')) => Some((false, true, 2)),
703                            _ => None,
704                        };
705                        if let Some((ahead, negate, n)) = look {
706                            for _ in 0..n {
707                                self.bump();
708                            }
709                            let inner = self.parse_alt();
710                            self.eat(')');
711                            return Node::Look { ahead, negate, node: Box::new(inner) };
712                        }
713                        // (?: 非キャプチャ。
714                        self.bump();
715                        None
716                    }
717                } else {
718                    self.ngroups += 1;
719                    Some(self.ngroups)
720                };
721                let inner = self.parse_alt();
722                self.eat(')');
723                if let (Some(idx), Some(name)) = (idx, group_name) {
724                    self.group_names.push((name, idx));
725                }
726                Node::Group {
727                    idx,
728                    node: Box::new(inner),
729                }
730            }
731            Some('[') => self.parse_class(),
732            Some('.') => {
733                self.bump();
734                Node::Any
735            }
736            Some('^') => {
737                self.bump();
738                Node::Start
739            }
740            Some('$') => {
741                self.bump();
742                Node::End
743            }
744            Some('\\') => {
745                self.bump();
746                self.parse_escape()
747            }
748            Some(c) => {
749                self.bump();
750                Node::Char(c)
751            }
752            None => Node::Empty,
753        }
754    }
755
756    fn parse_escape(&mut self) -> Node {
757        match self.bump() {
758            Some('d') => Node::Class(ClassData {
759                negate: false,
760                items: vec![ClassItem::Digit],
761            }),
762            Some('D') => Node::Class(ClassData {
763                negate: false,
764                items: vec![ClassItem::NotDigit],
765            }),
766            Some('w') => Node::Class(ClassData {
767                negate: false,
768                items: vec![ClassItem::Word],
769            }),
770            Some('W') => Node::Class(ClassData {
771                negate: false,
772                items: vec![ClassItem::NotWord],
773            }),
774            Some('s') => Node::Class(ClassData {
775                negate: false,
776                items: vec![ClassItem::Space],
777            }),
778            Some('S') => Node::Class(ClassData {
779                negate: false,
780                items: vec![ClassItem::NotSpace],
781            }),
782            Some('b') => Node::WordBoundary(true),
783            Some('B') => Node::WordBoundary(false),
784            Some('n') => Node::Char('\n'),
785            Some('t') => Node::Char('\t'),
786            Some('r') => Node::Char('\r'),
787            Some('f') => Node::Char('\u{0C}'),
788            Some('v') => Node::Char('\u{0B}'),
789            Some('0') => Node::Char('\0'),
790            // `\uXXXX`/`\u{X...}`（Unicode エスケープ）・`\xXX`（16進エスケープ）が
791            // 丸ごと未対応で、`A` が文字コード指定ではなくリテラルの `u0041`
792            // （4文字分の文字クラス）として解釈されてしまうバグだった。
793            Some('u') => Node::Char(self.parse_u_escape()),
794            Some('x') => Node::Char(self.parse_x_escape()),
795            Some('p') => self.parse_p_escape(false),
796            Some('P') => self.parse_p_escape(true),
797            Some(c) if c.is_ascii_digit() => {
798                let mut num = String::new();
799                num.push(c);
800                while let Some(d) = self.peek() {
801                    if d.is_ascii_digit() {
802                        num.push(d);
803                        self.bump();
804                    } else {
805                        break;
806                    }
807                }
808                Node::Backref(num.parse().unwrap_or(0))
809            }
810            Some(c) => Node::Char(c), // エスケープされたメタ文字。
811            None => Node::Empty,
812        }
813    }
814
815    fn parse_p_escape(&mut self, negate: bool) -> Node {
816        if self.peek() == Some('{') {
817            self.bump();
818            let mut prop_name = String::new();
819            while let Some(c) = self.bump() {
820                if c == '}' {
821                    break;
822                }
823                prop_name.push(c);
824            }
825            Node::Class(ClassData {
826                negate: false,
827                items: vec![ClassItem::UnicodeProp(prop_name, negate)],
828            })
829        } else {
830            Node::Char(if negate { 'P' } else { 'p' })
831        }
832    }
833
834    /// `\uXXXX`/`\u{X...}` の本体を解析する。呼出し時点で `\u` の `u` まで読み終えている
835    /// 前提（`parse_escape()`/`parse_class()` の両方から共用）。
836    fn parse_u_escape(&mut self) -> char {
837        if self.peek() == Some('{') {
838            self.bump(); // {
839            let mut hex = String::new();
840            while let Some(c) = self.peek() {
841                if c == '}' {
842                    break;
843                }
844                hex.push(c);
845                self.bump();
846            }
847            self.bump(); // }
848            u32::from_str_radix(&hex, 16).ok().and_then(char::from_u32).unwrap_or('u')
849        } else {
850            let save = self.pos;
851            let mut hex = String::new();
852            for _ in 0..4 {
853                match self.peek() {
854                    Some(c) if c.is_ascii_hexdigit() => {
855                        hex.push(c);
856                        self.bump();
857                    }
858                    _ => break,
859                }
860            }
861            match u32::from_str_radix(&hex, 16).ok().and_then(char::from_u32) {
862                Some(ch) if hex.len() == 4 => ch,
863                _ => {
864                    // 4桁揃わなければ通常の JS 正規表現と同様、`u` のリテラルに
865                    // フォールバックし、読み進めた分は巻き戻す。
866                    self.pos = save;
867                    'u'
868                }
869            }
870        }
871    }
872    /// `\xXX` の本体を解析する（呼出し時点で `x` まで読み終えている前提）。
873    fn parse_x_escape(&mut self) -> char {
874        let save = self.pos;
875        let mut hex = String::new();
876        for _ in 0..2 {
877            match self.peek() {
878                Some(c) if c.is_ascii_hexdigit() => {
879                    hex.push(c);
880                    self.bump();
881                }
882                _ => break,
883            }
884        }
885        match u32::from_str_radix(&hex, 16).ok().and_then(char::from_u32) {
886            Some(ch) if hex.len() == 2 => ch,
887            _ => {
888                self.pos = save;
889                'x'
890            }
891        }
892    }
893
894    fn parse_class(&mut self) -> Node {
895        self.bump(); // [
896        let negate = self.eat('^');
897        let mut items = Vec::new();
898        while let Some(c) = self.peek() {
899            if c == ']' {
900                break;
901            }
902            let lo = if c == '\\' {
903                self.bump();
904                match self.bump() {
905                    Some('d') => {
906                        items.push(ClassItem::Digit);
907                        continue;
908                    }
909                    Some('D') => {
910                        items.push(ClassItem::NotDigit);
911                        continue;
912                    }
913                    Some('w') => {
914                        items.push(ClassItem::Word);
915                        continue;
916                    }
917                    Some('W') => {
918                        items.push(ClassItem::NotWord);
919                        continue;
920                    }
921                    Some('s') => {
922                        items.push(ClassItem::Space);
923                        continue;
924                    }
925                    Some('S') => {
926                        items.push(ClassItem::NotSpace);
927                        continue;
928                    }
929                    Some('n') => '\n',
930                    Some('t') => '\t',
931                    Some('r') => '\r',
932                    // `[A-Z]` のような文字クラス内エスケープも `parse_escape()`
933                    // と同じく丸ごと未対応で、`u`/`x` の1文字＋続く16進桁がそのまま
934                    // リテラル文字として範囲に混入する静かなバグだった。
935                    Some('u') => self.parse_u_escape(),
936                    Some('x') => self.parse_x_escape(),
937                    Some(e) => e,
938                    None => break,
939                }
940            } else {
941                self.bump();
942                c
943            };
944            // 範囲 a-z
945            if self.peek() == Some('-') && self.chars.get(self.pos + 1).is_some_and(|&x| x != ']') {
946                self.bump(); // -
947                let hi = if self.peek() == Some('\\') {
948                    self.bump();
949                    match self.bump() {
950                        Some('u') => self.parse_u_escape(),
951                        Some('x') => self.parse_x_escape(),
952                        Some(e) => e,
953                        None => lo,
954                    }
955                } else {
956                    self.bump().unwrap_or(lo)
957                };
958                items.push(ClassItem::Range(lo, hi));
959            } else {
960                items.push(ClassItem::Ch(lo));
961            }
962        }
963        self.eat(']');
964        Node::Class(ClassData { negate, items })
965    }
966}
atmos/os_lib/js/regex.rs

atmos/os_lib/js/
regex.rs
