Skip to main content

instruction_md/
pattern.rs

1//! A small regular-expression engine for the specification's patterns (the registry's grammar and attribute patterns)
2//! and the reader's line grammar: RE2's syntax subset those use, matched by a Pike VM — leftmost-first like RE2 and
3//! ECMAScript, in time linear in the input, so no document can make a pattern backtrack exponentially.
4//!
5//! Supported: literals and escapes (`\t \n \r \v \f \x{…} \w \d \s`, their complements `\W \D \S`, and escaped
6//! punctuation), classes (`[a-z]`,
7//! `[^…]`), `^` and `$` (the text's start and end), groups (capturing and `(?:…)`), alternation, the quantifiers
8//! `* + ? {n} {n,} {n,m}` and their lazy forms, and a leading `(?i)` (ASCII case folding).
9
10use std::fmt;
11
12/// A compiled pattern.
13#[derive(Clone)]
14pub struct Pattern {
15    source: String,
16    prog: Vec<Inst>,
17    groups: usize,
18    fold: bool,
19    /// the pattern starts with `^`: it can only match at the text's start
20    anchored: bool,
21}
22
23impl fmt::Debug for Pattern {
24    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
25        write!(f, "Pattern({:?})", self.source)
26    }
27}
28
29impl PartialEq for Pattern {
30    fn eq(&self, other: &Self) -> bool {
31        self.source == other.source
32    }
33}
34
35#[derive(Clone, Debug)]
36enum Matcher {
37    Char(char),
38    Class(Vec<(char, char)>, bool),
39}
40
41#[derive(Clone, Debug)]
42enum Inst {
43    Char(Matcher),
44    Split(usize, usize),
45    Jmp(usize),
46    Save(usize),
47    Start,
48    End,
49    Match,
50}
51
52#[derive(Clone, Debug)]
53enum Ast {
54    Empty,
55    Char(Matcher),
56    Start,
57    End,
58    Group(Box<Ast>, Option<usize>),
59    Concat(Vec<Ast>),
60    Alt(Vec<Ast>),
61    Repeat(Box<Ast>, u32, Option<u32>, bool),
62}
63
64/// The spans a match's groups cover: group 0 is the whole match.
65#[derive(Clone, Debug)]
66pub struct Captures {
67    slots: Vec<Option<usize>>,
68}
69
70impl Captures {
71    /// The byte span of group `i`, if it took part in the match.
72    pub fn span(&self, i: usize) -> Option<(usize, usize)> {
73        match (self.slots.get(2 * i).copied().flatten(), self.slots.get(2 * i + 1).copied().flatten()) {
74            (Some(a), Some(b)) if a <= b => Some((a, b)),
75            _ => None,
76        }
77    }
78
79    /// The text of group `i` in `text` (the text matched).
80    pub fn get<'t>(&self, text: &'t str, i: usize) -> Option<&'t str> {
81        self.span(i).and_then(|(a, b)| text.get(a..b))
82    }
83
84    /// The whole match's span.
85    pub fn whole(&self) -> (usize, usize) {
86        self.span(0).unwrap_or((0, 0))
87    }
88}
89
90struct Parser<'a> {
91    chars: Vec<char>,
92    i: usize,
93    groups: usize,
94    fold: bool,
95    _src: &'a str,
96}
97
98/// An error compiling a pattern.
99#[derive(Clone, Debug, PartialEq, Eq)]
100pub struct PatternError(pub String);
101
102impl fmt::Display for PatternError {
103    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
104        f.write_str(&self.0)
105    }
106}
107
108impl Pattern {
109    /// Compiles a pattern.
110    pub fn new(source: &str) -> Result<Pattern, PatternError> {
111        let mut p = Parser { chars: source.chars().collect(), i: 0, groups: 1, fold: false, _src: source };
112        if p.chars.starts_with(&['(', '?', 'i', ')']) {
113            p.fold = true;
114            p.i = 4;
115        }
116        let ast = p.alt()?;
117        if p.i != p.chars.len() {
118            return Err(PatternError(format!("unexpected {:?} in {source}", p.chars[p.i])));
119        }
120        let mut prog = vec![Inst::Save(0)];
121        compile(&ast, &mut prog);
122        prog.push(Inst::Save(1));
123        prog.push(Inst::Match);
124        let anchored = starts_anchored(&ast);
125        Ok(Pattern { source: source.to_string(), prog, groups: p.groups, fold: p.fold, anchored })
126    }
127
128    /// Compiles a pattern this crate writes itself (the registry's are checked when it loads).
129    pub(crate) fn must(source: &str) -> Pattern {
130        match Pattern::new(source) {
131            Ok(p) => p,
132            // the crate's own patterns are fixed text, compiled by the tests: an error here is a bug in this crate
133            Err(e) => Pattern::never(&e.0),
134        }
135    }
136
137    /// A pattern that matches nothing (the fallback for one that does not compile).
138    fn never(source: &str) -> Pattern {
139        Pattern {
140            source: source.to_string(),
141            prog: vec![Inst::Char(Matcher::Class(Vec::new(), false)), Inst::Match],
142            groups: 1,
143            fold: false,
144            anchored: false,
145        }
146    }
147
148    /// The pattern as written.
149    pub fn as_str(&self) -> &str {
150        &self.source
151    }
152
153    /// Does the pattern match anywhere in the text?
154    pub fn is_match(&self, text: &str) -> bool {
155        self.run(text, 0, 0, true).is_some()
156    }
157
158    /// The leftmost match's span.
159    pub fn find(&self, text: &str) -> Option<(usize, usize)> {
160        self.captures_at(text, 0).map(|c| c.whole())
161    }
162
163    /// The leftmost match's text.
164    pub fn find_str<'t>(&self, text: &'t str) -> Option<&'t str> {
165        self.find(text).and_then(|(a, b)| text.get(a..b))
166    }
167
168    /// The leftmost match and its groups.
169    pub fn captures(&self, text: &str) -> Option<Captures> {
170        self.captures_at(text, 0)
171    }
172
173    /// Every non-overlapping match's span, left to right.
174    pub fn find_iter(&self, text: &str) -> Vec<(usize, usize)> {
175        self.captures_iter(text).iter().map(Captures::whole).collect()
176    }
177
178    /// Every non-overlapping match, left to right.
179    pub fn captures_iter(&self, text: &str) -> Vec<Captures> {
180        let mut out = Vec::new();
181        let mut at = 0;
182        while at <= text.len() {
183            let Some(c) = self.captures_at(text, at) else { break };
184            let (a, b) = c.whole();
185            out.push(c);
186            at = if b > a {
187                b
188            } else {
189                match text[b..].chars().next() {
190                    Some(ch) => b + ch.len_utf8(),
191                    None => break,
192                }
193            };
194        }
195        out
196    }
197
198    /// The text with every match replaced by what `f` makes of it.
199    pub fn replace_all(&self, text: &str, mut f: impl FnMut(&Captures) -> String) -> String {
200        let mut out = String::with_capacity(text.len());
201        let mut last = 0;
202        for c in self.captures_iter(text) {
203            let (a, b) = c.whole();
204            out.push_str(&text[last..a]);
205            out.push_str(&f(&c));
206            last = b;
207        }
208        out.push_str(&text[last..]);
209        out
210    }
211
212    /// The leftmost match starting at or after `start` (a char boundary), with its groups.
213    pub fn captures_at(&self, text: &str, start: usize) -> Option<Captures> {
214        self.run(text, start, self.groups * 2, false).map(|slots| Captures { slots })
215    }
216
217    /// The Pike VM: threads in priority order, one step per character. `slots` are the capture slots kept (none for
218    /// a yes-or-no answer); `any`: stop at the first match found, leftmost-first or not.
219    fn run(&self, text: &str, start: usize, slots: usize, any: bool) -> Option<Vec<Option<usize>>> {
220        if start > text.len() || !text.is_char_boundary(start) || self.anchored && start > 0 {
221            return None;
222        }
223        let n = self.prog.len();
224        let mut clist = Threads::new(n);
225        let mut nlist = Threads::new(n);
226        let mut matched: Option<Vec<Option<usize>>> = None;
227        let mut pos = start;
228        loop {
229            if matched.is_none() && (!self.anchored || pos == 0) {
230                self.add(&mut clist, 0, pos, text, vec![None; slots]);
231            }
232            if clist.list.is_empty() {
233                break;
234            }
235            let ch = text[pos..].chars().next();
236            let next = pos + ch.map_or(0, char::len_utf8);
237            nlist.clear();
238            let threads = std::mem::take(&mut clist.list);
239            for (pc, caps) in threads {
240                match &self.prog[pc] {
241                    Inst::Char(m) => {
242                        if let Some(c) = ch
243                            && self.matches(m, c)
244                        {
245                            self.add(&mut nlist, pc + 1, next, text, caps);
246                        }
247                    }
248                    Inst::Match => {
249                        matched = Some(caps);
250                        if any {
251                            return matched;
252                        }
253                        break;
254                    }
255                    _ => {}
256                }
257            }
258            std::mem::swap(&mut clist, &mut nlist);
259            if ch.is_none() {
260                break;
261            }
262            pos = next;
263        }
264        matched
265    }
266
267    fn matches(&self, m: &Matcher, c: char) -> bool {
268        let fold = self.fold;
269        match m {
270            Matcher::Char(x) => *x == c || fold && x.eq_ignore_ascii_case(&c),
271            Matcher::Class(ranges, negated) => {
272                let hit = |c: char| ranges.iter().any(|&(a, b)| a <= c && c <= b);
273                let mut found = hit(c);
274                if !found && fold && c.is_ascii_alphabetic() {
275                    found = hit(c.to_ascii_lowercase()) || hit(c.to_ascii_uppercase());
276                }
277                found != *negated
278            }
279        }
280    }
281
282    /// Adds a thread at pc, following the instructions that consume nothing.
283    fn add(&self, list: &mut Threads, pc: usize, pos: usize, text: &str, mut caps: Vec<Option<usize>>) {
284        let mut stack: Vec<(usize, Restore)> = vec![(pc, None)];
285        // (an explicit stack: a restore entry puts a slot back once its branch is followed)
286        while let Some((pc, restore)) = stack.pop() {
287            if let Some((slot, old)) = restore {
288                caps[slot] = old;
289                continue;
290            }
291            if list.seen[pc] == list.generation {
292                continue;
293            }
294            list.seen[pc] = list.generation;
295            match &self.prog[pc] {
296                Inst::Jmp(t) => stack.push((*t, None)),
297                Inst::Split(a, b) => {
298                    stack.push((*b, None));
299                    stack.push((*a, None));
300                }
301                Inst::Save(slot) => {
302                    if *slot < caps.len() {
303                        let old = caps[*slot];
304                        caps[*slot] = Some(pos);
305                        stack.push((0, Some((*slot, old))));
306                        stack.push((pc + 1, None));
307                    } else {
308                        stack.push((pc + 1, None));
309                    }
310                }
311                Inst::Start => {
312                    if pos == 0 {
313                        stack.push((pc + 1, None));
314                    }
315                }
316                Inst::End => {
317                    if pos == text.len() {
318                        stack.push((pc + 1, None));
319                    }
320                }
321                Inst::Char(_) | Inst::Match => list.list.push((pc, caps.clone())),
322            }
323        }
324    }
325}
326
327/// A slot to put back once a branch has been followed: (the slot, its value before).
328type Restore = Option<(usize, Option<usize>)>;
329
330struct Threads {
331    /// the generation a pc was last added in (a list is cleared by moving to the next generation)
332    seen: Vec<u32>,
333    generation: u32,
334    list: Vec<(usize, Vec<Option<usize>>)>,
335}
336
337impl Threads {
338    fn new(n: usize) -> Threads {
339        Threads { seen: vec![0; n], generation: 1, list: Vec::new() }
340    }
341    fn clear(&mut self) {
342        self.generation = self.generation.wrapping_add(1);
343        if self.generation == 0 {
344            self.seen.iter_mut().for_each(|s| *s = 0);
345            self.generation = 1;
346        }
347        self.list.clear();
348    }
349}
350
351/// Does every match have to start at the text's start (a leading `^` on every branch)?
352fn starts_anchored(ast: &Ast) -> bool {
353    match ast {
354        Ast::Start => true,
355        Ast::Concat(items) => items.first().is_some_and(starts_anchored),
356        Ast::Group(inner, _) => starts_anchored(inner),
357        Ast::Alt(items) => !items.is_empty() && items.iter().all(starts_anchored),
358        _ => false,
359    }
360}
361
362fn compile(ast: &Ast, prog: &mut Vec<Inst>) {
363    match ast {
364        Ast::Empty => {}
365        Ast::Char(m) => prog.push(Inst::Char(m.clone())),
366        Ast::Start => prog.push(Inst::Start),
367        Ast::End => prog.push(Inst::End),
368        Ast::Group(inner, index) => {
369            if let Some(i) = index {
370                prog.push(Inst::Save(2 * i));
371                compile(inner, prog);
372                prog.push(Inst::Save(2 * i + 1));
373            } else {
374                compile(inner, prog);
375            }
376        }
377        Ast::Concat(items) => items.iter().for_each(|a| compile(a, prog)),
378        Ast::Alt(items) => {
379            let mut jumps = Vec::new();
380            for (k, item) in items.iter().enumerate() {
381                if k + 1 < items.len() {
382                    let split = prog.len();
383                    prog.push(Inst::Split(split + 1, 0));
384                    compile(item, prog);
385                    jumps.push(prog.len());
386                    prog.push(Inst::Jmp(0));
387                    let next = prog.len();
388                    prog[split] = Inst::Split(split + 1, next);
389                } else {
390                    compile(item, prog);
391                }
392            }
393            let end = prog.len();
394            for j in jumps {
395                prog[j] = Inst::Jmp(end);
396            }
397        }
398        Ast::Repeat(inner, min, max, greedy) => {
399            for _ in 0..*min {
400                compile(inner, prog);
401            }
402            match max {
403                None => {
404                    let split = prog.len();
405                    prog.push(Inst::Split(0, 0));
406                    compile(inner, prog);
407                    prog.push(Inst::Jmp(split));
408                    let out = prog.len();
409                    prog[split] = if *greedy { Inst::Split(split + 1, out) } else { Inst::Split(out, split + 1) };
410                }
411                Some(max) => {
412                    let mut splits = Vec::new();
413                    for _ in *min..*max {
414                        splits.push(prog.len());
415                        prog.push(Inst::Split(0, 0));
416                        compile(inner, prog);
417                    }
418                    let out = prog.len();
419                    for s in splits {
420                        prog[s] = if *greedy { Inst::Split(s + 1, out) } else { Inst::Split(out, s + 1) };
421                    }
422                }
423            }
424        }
425    }
426}
427
428impl Parser<'_> {
429    fn peek(&self) -> Option<char> {
430        self.chars.get(self.i).copied()
431    }
432
433    fn err<T>(&self, what: &str) -> Result<T, PatternError> {
434        Err(PatternError(format!("{what} at {}", self.i)))
435    }
436
437    fn alt(&mut self) -> Result<Ast, PatternError> {
438        let mut items = vec![self.concat()?];
439        while self.peek() == Some('|') {
440            self.i += 1;
441            items.push(self.concat()?);
442        }
443        Ok(if items.len() == 1 { items.pop().unwrap_or(Ast::Empty) } else { Ast::Alt(items) })
444    }
445
446    fn concat(&mut self) -> Result<Ast, PatternError> {
447        let mut items = Vec::new();
448        while let Some(c) = self.peek() {
449            if c == '|' || c == ')' {
450                break;
451            }
452            let atom = self.atom()?;
453            let atom = self.quantified(atom)?;
454            items.push(atom);
455        }
456        Ok(Ast::Concat(items))
457    }
458
459    fn quantified(&mut self, atom: Ast) -> Result<Ast, PatternError> {
460        let (min, max) = match self.peek() {
461            Some('*') => {
462                self.i += 1;
463                (0, None)
464            }
465            Some('+') => {
466                self.i += 1;
467                (1, None)
468            }
469            Some('?') => {
470                self.i += 1;
471                (0, Some(1))
472            }
473            Some('{') => {
474                let save = self.i;
475                self.i += 1;
476                let Some(min) = self.number() else {
477                    self.i = save;
478                    return Ok(atom);
479                };
480                let max = if self.peek() == Some(',') {
481                    self.i += 1;
482                    if self.peek() == Some('}') { None } else { self.number() }
483                } else {
484                    Some(min)
485                };
486                if self.peek() != Some('}') {
487                    return self.err("bad repetition");
488                }
489                self.i += 1;
490                if max.is_some_and(|m| m < min) || min > 1000 || max.is_some_and(|m| m > 1000) {
491                    return self.err("bad repetition");
492                }
493                (min, max)
494            }
495            _ => return Ok(atom),
496        };
497        let greedy = if self.peek() == Some('?') {
498            self.i += 1;
499            false
500        } else {
501            true
502        };
503        Ok(Ast::Repeat(Box::new(atom), min, max, greedy))
504    }
505
506    fn number(&mut self) -> Option<u32> {
507        let start = self.i;
508        let mut n: u32 = 0;
509        while let Some(c) = self.peek().filter(char::is_ascii_digit) {
510            n = n.saturating_mul(10).saturating_add(c as u32 - '0' as u32);
511            self.i += 1;
512        }
513        (self.i > start).then_some(n)
514    }
515
516    fn atom(&mut self) -> Result<Ast, PatternError> {
517        let Some(c) = self.peek() else { return self.err("unexpected end") };
518        self.i += 1;
519        match c {
520            '^' => Ok(Ast::Start),
521            '$' => Ok(Ast::End),
522            '.' => Ok(Ast::Char(Matcher::Class(vec![('\n', '\n')], true))),
523            '(' => {
524                let index = if self.chars[self.i..].starts_with(&['?', ':']) {
525                    self.i += 2;
526                    None
527                } else {
528                    let g = self.groups;
529                    self.groups += 1;
530                    Some(g)
531                };
532                let inner = self.alt()?;
533                if self.peek() != Some(')') {
534                    return self.err("unclosed group");
535                }
536                self.i += 1;
537                Ok(Ast::Group(Box::new(inner), index))
538            }
539            '[' => self.class(),
540            '\\' => {
541                let ranges = self.escape()?;
542                Ok(Ast::Char(ranges))
543            }
544            '*' | '+' | '?' => self.err("nothing to repeat"),
545            c => Ok(Ast::Char(Matcher::Char(c))),
546        }
547    }
548
549    /// An escape after its backslash: one character, or a class (\w, \d, \s, or its complement \W, \D, \S).
550    fn escape(&mut self) -> Result<Matcher, PatternError> {
551        let Some(c) = self.peek() else { return self.err("trailing backslash") };
552        self.i += 1;
553        Ok(match c {
554            't' => Matcher::Char('\t'),
555            'n' => Matcher::Char('\n'),
556            'r' => Matcher::Char('\r'),
557            'v' => Matcher::Char('\u{b}'),
558            'f' => Matcher::Char('\u{c}'),
559            'w' => Matcher::Class(vec![('0', '9'), ('A', 'Z'), ('_', '_'), ('a', 'z')], false),
560            'd' => Matcher::Class(vec![('0', '9')], false),
561            's' => Matcher::Class(vec![('\t', '\n'), ('\u{c}', '\r'), (' ', ' ')], false),
562            'W' => Matcher::Class(vec![('0', '9'), ('A', 'Z'), ('_', '_'), ('a', 'z')], true),
563            'D' => Matcher::Class(vec![('0', '9')], true),
564            'S' => Matcher::Class(vec![('\t', '\n'), ('\u{c}', '\r'), (' ', ' ')], true),
565            'x' => {
566                if self.peek() != Some('{') {
567                    return self.err("bad \\x");
568                }
569                self.i += 1;
570                let mut v: u32 = 0;
571                while let Some(d) = self.peek().and_then(|d| d.to_digit(16)) {
572                    v = v.saturating_mul(16).saturating_add(d);
573                    self.i += 1;
574                }
575                if self.peek() != Some('}') {
576                    return self.err("bad \\x");
577                }
578                self.i += 1;
579                match char::from_u32(v) {
580                    Some(ch) => Matcher::Char(ch),
581                    None => return self.err("bad \\x"),
582                }
583            }
584            c if c.is_ascii_punctuation() => Matcher::Char(c),
585            _ => return self.err("unknown escape"),
586        })
587    }
588
589    fn class(&mut self) -> Result<Ast, PatternError> {
590        let negated = self.peek() == Some('^');
591        if negated {
592            self.i += 1;
593        }
594        let mut ranges = Vec::new();
595        let mut first = true;
596        loop {
597            let Some(c) = self.peek() else { return self.err("unclosed class") };
598            if c == ']' && !first {
599                self.i += 1;
600                break;
601            }
602            first = false;
603            self.i += 1;
604            let lo = if c == '\\' {
605                match self.escape()? {
606                    Matcher::Char(ch) => ch,
607                    Matcher::Class(rs, false) => {
608                        ranges.extend(rs);
609                        continue;
610                    }
611                    // (`[\S…]`: the complement's ranges, as ECMAScript and RE2 read it)
612                    Matcher::Class(rs, true) => {
613                        ranges.extend(complement(rs));
614                        continue;
615                    }
616                }
617            } else {
618                c
619            };
620            if self.peek() == Some('-') && self.chars.get(self.i + 1).is_some_and(|&n| n != ']') {
621                self.i += 1;
622                let Some(h) = self.peek() else { return self.err("unclosed class") };
623                self.i += 1;
624                let hi = if h == '\\' {
625                    match self.escape()? {
626                        Matcher::Char(ch) => ch,
627                        Matcher::Class(..) => return self.err("bad range"),
628                    }
629                } else {
630                    h
631                };
632                if hi < lo {
633                    return self.err("bad range");
634                }
635                ranges.push((lo, hi));
636            } else {
637                ranges.push((lo, lo));
638            }
639        }
640        Ok(Ast::Char(Matcher::Class(ranges, negated)))
641    }
642}
643
644/// The characters outside `ranges` (sorted, not overlapping), as ranges.
645fn complement(mut ranges: Vec<(char, char)>) -> Vec<(char, char)> {
646    ranges.sort_unstable();
647    let mut out = Vec::new();
648    let mut next = 0u32;
649    for (lo, hi) in ranges {
650        if (lo as u32) > next
651            && let (Some(a), Some(b)) = (char::from_u32(next), char::from_u32(lo as u32 - 1))
652        {
653            out.push((a, b));
654        }
655        next = next.max(hi as u32 + 1);
656    }
657    if let Some(a) = char::from_u32(next) {
658        out.push((a, char::MAX));
659    }
660    out
661}
662
663#[cfg(test)]
664mod tests {
665    use super::*;
666
667    #[test]
668    fn matches_like_re2() {
669        let p = Pattern::must(r"^(\*\*)?(MUST NOT|MUST)(?:\[([^\]\s]*)\])?:(\*\*)?[ \t]+(\S.*)$".replace(r"\S", r"[^\s]").as_str());
670        let c = p.captures("**MUST NOT[x]:** go").unwrap();
671        assert_eq!(c.get("**MUST NOT[x]:** go", 2), Some("MUST NOT"));
672        assert_eq!(c.get("**MUST NOT[x]:** go", 3), Some("x"));
673        assert_eq!(c.get("**MUST NOT[x]:** go", 5), Some("go"));
674        assert!(Pattern::must("^sha256:[0-9a-f]{64}$").is_match(&format!("sha256:{}", "a".repeat(64))));
675        assert!(!Pattern::must("^sha256:[0-9a-f]{64}$").is_match(&format!("sha256:{}", "a".repeat(63))));
676        let lazy = Pattern::must(r"^#{1,6}[ \t].*?[ \t](\{[^{}]*\})[ \t]*$");
677        assert_eq!(lazy.captures("## A {x} b {#id}").and_then(|c| c.get("## A {x} b {#id}", 1).map(String::from)), Some("{#id}".into()));
678        assert_eq!(Pattern::must("`+").find_iter("a `` b ` c"), vec![(2, 4), (7, 8)]);
679        assert!(Pattern::must("(?i)^https?://x$").is_match("HTTPS://X"));
680        let nested = Pattern::must(r"^(?:/(?:[^~]|~[01])*)*$");
681        assert!(!nested.is_match(&format!("{}~x", "/".repeat(5000))));
682        assert_eq!(Pattern::must("a|ab").find("ab"), Some((0, 1)));
683        // (the specification's schema says a name is not blank with \S; and the complements inside a class)
684        assert!(Pattern::must(r"\S").is_match("  x "));
685        assert!(!Pattern::must(r"\S").is_match(" \t\n"));
686        assert!(Pattern::must(r"^[\D]+$").is_match("ab"));
687        assert!(!Pattern::must(r"^[\D]+$").is_match("a1"));
688        assert!(Pattern::must(r"^\W\w$").is_match("-a"));
689        assert!(!Pattern::must(r"^\W$").is_match("_"));
690    }
691}