base/
pattern.rs

1// pattern -- shell wildcards and a small engine for regular expressions (the shells of
2// JFNetworker's hosts: globs, find -name, grep)
3//
4//   glob(pat, s) -> bool          fnmatch(3) without flags: * any run of characters, ? one,
5//                                 [abc] [a-z] [!x] [^x] [[:digit:]] one of a set, \x the
6//                                 character x; '/' and a leading '.' are ordinary characters
7//                                 here (a caller matches path components one by one and hides
8//                                 dot files itself)
9//   has_glob(s) -> bool           s holds an unescaped *, ? or [ (a word to expand)
10//   Regex::new(pat, Syntax::Basic | Syntax::Extended, icase) -> Result<Regex, ReErr>
11//   Regex::is_match(s)            the expression matches somewhere in s
12//   Regex::find(s) / find_at(s, from) -> Option<(start, end)>   byte offsets of the leftmost
13//                                 match, the longest one starting there (POSIX)
14//   ReErr::text()                 the error in GNU grep's words ("Unmatched ( or \(")
15//
16// The expressions are POSIX's basic (BRE) and extended (ERE) syntax without back-references
17// and collating elements: characters, ".", bracket expressions with ranges, negation and the
18// classes [:alpha:] [:digit:] [:alnum:] [:upper:] [:lower:] [:space:] [:blank:] [:punct:]
19// [:xdigit:] [:print:] [:graph:] [:cntrl:]; the anchors ^ and $; the repetitions *, and in
20// ERE + ? {m} {m,} {m,n} (BRE: \+ \? \{m,n\} as GNU takes them); groups ( ) and alternatives |
21// (BRE: \( \) \|); GNU's \w \W \s \S and the word edges \< \> \b \B.  As GNU does, a
22// repetition with nothing before it is an ordinary character, an ERE "{" that starts no
23// interval too, and BRE takes ^ and $ as anchors only at the ends of the expression or of a
24// group.  Matching runs a Pike VM over the characters: time grows with the text times the
25// program, never exponentially; a repetition counts to 255 at most and a program has at most
26// 20000 steps (ReErr::TooBig beyond).  Case-insensitive matching compares simple lowercase
27// forms.
28
29use alloc::boxed::Box;
30use alloc::vec;
31use alloc::vec::Vec;
32
33// ---------------------------------------------------------------- wildcards
34
35/// a character class name of a bracket expression
36fn class_holds(name: &str, c: char) -> Option<bool> {
37    Some(match name {
38        "alpha" => c.is_alphabetic(),
39        "digit" => c.is_ascii_digit(),
40        "alnum" => c.is_alphanumeric(),
41        "upper" => c.is_uppercase(),
42        "lower" => c.is_lowercase(),
43        "space" => c.is_whitespace(),
44        "blank" => c == ' ' || c == '\t',
45        "punct" => c.is_ascii_punctuation(),
46        "xdigit" => c.is_ascii_hexdigit(),
47        "print" => !c.is_control(),
48        "graph" => !c.is_control() && !c.is_whitespace(),
49        "cntrl" => c.is_control(),
50        _ => return None,
51    })
52}
53
54/// a bracket expression from just after its '[': the set and the index after its ']' (None:
55/// not closed, or a class name that does not exist)
56fn bracket(p: &[char], mut i: usize, glob: bool) -> Option<(Set, usize)> {
57    let mut set = Set { neg: false, items: Vec::new() };
58    if i < p.len() && (p[i] == '^' || (glob && p[i] == '!')) {
59        set.neg = true;
60        i += 1;
61    }
62    let start = i;
63    loop {
64        let c = *p.get(i)?;
65        if c == ']' && i > start {
66            return Some((set, i + 1));
67        }
68        if c == '[' && p.get(i + 1) == Some(&':') {
69            let rest = &p[i + 2..];
70            let end = rest.windows(2).position(|w| w == [':', ']'])?;
71            let name: alloc::string::String = rest[..end].iter().collect();
72            class_holds(&name, 'a')?;
73            set.items.push(Item::Class(name));
74            i += 2 + end + 2;
75            continue;
76        }
77        if c == '[' && matches!(p.get(i + 1), Some('.') | Some('=')) {
78            return None;
79        }
80        let mut lo = c;
81        i += 1;
82        if glob && c == '\\' && i < p.len() {
83            lo = p[i];
84            i += 1;
85        }
86        if p.get(i) == Some(&'-') && p.get(i + 1).is_some_and(|&x| x != ']') {
87            let mut hi = p[i + 1];
88            i += 2;
89            if glob && hi == '\\' && i < p.len() {
90                hi = p[i];
91                i += 1;
92            }
93            if hi < lo {
94                return None;
95            }
96            set.items.push(Item::Range(lo, hi));
97        } else {
98            set.items.push(Item::Range(lo, lo));
99        }
100    }
101}
102
103/// the wildcard pattern matches all of s (fnmatch without flags)
104pub fn glob(pat: &str, s: &str) -> bool {
105    let p: Vec<char> = pat.chars().collect();
106    let t: Vec<char> = s.chars().collect();
107    let (mut pi, mut ti) = (0usize, 0usize);
108    // the last '*' and where its run ends now: a mismatch makes the run one longer
109    let mut star: Option<(usize, usize)> = None;
110    loop {
111        if pi < p.len() {
112            match p[pi] {
113                '*' => {
114                    star = Some((pi, ti));
115                    pi += 1;
116                    continue;
117                }
118                '?' if ti < t.len() => {
119                    pi += 1;
120                    ti += 1;
121                    continue;
122                }
123                '[' => {
124                    if let Some((set, next)) = bracket(&p, pi + 1, true) {
125                        if ti < t.len() && set.holds(t[ti], false) {
126                            pi = next;
127                            ti += 1;
128                            continue;
129                        }
130                    } else if ti < t.len() && t[ti] == '[' {
131                        // an open '[' stands for itself
132                        pi += 1;
133                        ti += 1;
134                        continue;
135                    }
136                }
137                '\\' if pi + 1 < p.len() => {
138                    if ti < t.len() && t[ti] == p[pi + 1] {
139                        pi += 2;
140                        ti += 1;
141                        continue;
142                    }
143                }
144                '?' => {}
145                c => {
146                    if ti < t.len() && t[ti] == c {
147                        pi += 1;
148                        ti += 1;
149                        continue;
150                    }
151                }
152            }
153        } else if ti == t.len() {
154            return true;
155        }
156        match star {
157            Some((sp, st)) if st < t.len() => {
158                star = Some((sp, st + 1));
159                pi = sp + 1;
160                ti = st + 1;
161            }
162            _ => return false,
163        }
164    }
165}
166
167/// the word holds an unescaped wildcard (*, ? or [)
168pub fn has_glob(s: &str) -> bool {
169    let mut esc = false;
170    for c in s.chars() {
171        if esc {
172            esc = false;
173            continue;
174        }
175        match c {
176            '\\' => esc = true,
177            '*' | '?' | '[' => return true,
178            _ => {}
179        }
180    }
181    false
182}
183
184// ---------------------------------------------------------------- regular expressions
185
186/// which syntax an expression is written in
187#[derive(Clone, Copy, Debug, PartialEq, Eq)]
188#[non_exhaustive]
189pub enum Syntax {
190    /// POSIX basic (grep): \( \) \{ \} \| \+ \? are the operators
191    Basic,
192    /// POSIX extended (grep -E, egrep)
193    Extended,
194}
195
196/// why an expression does not compile
197#[derive(Clone, Copy, Debug, PartialEq, Eq)]
198#[non_exhaustive]
199pub enum ReErr {
200    /// an open group without its end
201    Paren,
202    /// a group's end without its start
203    CloseParen,
204    /// a bracket expression without its ']'
205    Bracket,
206    /// a range whose end comes before its start
207    Range,
208    /// [:name:] with a name that is no class
209    Class,
210    /// a '\' at the end
211    Backslash,
212    /// \{ without \}
213    Brace,
214    /// what is between { and } is no interval
215    BraceContent,
216    /// a repetition of something that cannot repeat
217    Repeat,
218    /// the program would be too long
219    TooBig,
220}
221
222impl ReErr {
223    /// GNU grep's message
224    pub fn text(self) -> &'static str {
225        match self {
226            ReErr::Paren => "Unmatched ( or \\(",
227            ReErr::CloseParen => "Unmatched ) or \\)",
228            ReErr::Bracket => "Unmatched [, [^, [:, [., or [=",
229            ReErr::Range => "Invalid range end",
230            ReErr::Class => "Invalid character class name",
231            ReErr::Backslash => "Trailing backslash",
232            ReErr::Brace => "Unmatched \\{",
233            ReErr::BraceContent => "Invalid content of \\{\\}",
234            ReErr::Repeat => "Invalid preceding regular expression",
235            ReErr::TooBig => "Regular expression too big",
236        }
237    }
238}
239
240#[derive(Clone, Debug, PartialEq, Eq)]
241enum Item {
242    Range(char, char),
243    Class(alloc::string::String),
244}
245
246/// a set of characters of a bracket expression or of \w \s
247#[derive(Clone, Debug, PartialEq, Eq)]
248struct Set {
249    neg: bool,
250    items: Vec<Item>,
251}
252
253fn lower(c: char) -> char {
254    c.to_lowercase().next().unwrap_or(c)
255}
256
257fn upper(c: char) -> char {
258    c.to_uppercase().next().unwrap_or(c)
259}
260
261impl Set {
262    fn holds(&self, c: char, icase: bool) -> bool {
263        let one = |c: char| {
264            self.items.iter().any(|it| match it {
265                Item::Range(a, b) => *a <= c && c <= *b,
266                Item::Class(n) => class_holds(n, c).unwrap_or(false),
267            })
268        };
269        let hit = one(c) || (icase && (one(lower(c)) || one(upper(c))));
270        hit != self.neg
271    }
272    fn word(neg: bool) -> Set {
273        Set { neg, items: vec![Item::Class(alloc::string::String::from("alnum")), Item::Range('_', '_')] }
274    }
275    fn space(neg: bool) -> Set {
276        Set { neg, items: vec![Item::Class(alloc::string::String::from("space"))] }
277    }
278}
279
280/// a zero-width test at a position
281#[derive(Clone, Copy, Debug, PartialEq, Eq)]
282enum Edge {
283    Bol,
284    Eol,
285    /// \< and \>: a word starts / ends here
286    WordStart,
287    WordEnd,
288    /// \b and \B
289    Word,
290    NotWord,
291}
292
293#[derive(Clone, Debug, PartialEq, Eq)]
294enum Node {
295    Empty,
296    Char(char),
297    Any,
298    Set(Set),
299    Edge(Edge),
300    Cat(Vec<Node>),
301    Alt(Vec<Node>),
302    Rep(Box<Node>, u32, Option<u32>),
303}
304
305const REP_MAX: u32 = 255;
306const PROG_MAX: usize = 20_000;
307
308struct Parser<'a> {
309    p: &'a [char],
310    i: usize,
311    ere: bool,
312    depth: u32,
313}
314
315impl Parser<'_> {
316    fn peek(&self) -> Option<char> {
317        self.p.get(self.i).copied()
318    }
319    fn peek2(&self) -> Option<char> {
320        self.p.get(self.i + 1).copied()
321    }
322    /// at "|" (ERE) or "\|" (BRE)
323    fn at_alt(&self) -> bool {
324        if self.ere { self.peek() == Some('|') } else { self.peek() == Some('\\') && self.peek2() == Some('|') }
325    }
326    /// at ")" (ERE) or "\)" (BRE)
327    fn at_close(&self) -> bool {
328        if self.ere { self.peek() == Some(')') } else { self.peek() == Some('\\') && self.peek2() == Some(')') }
329    }
330    fn alt(&mut self) -> Result<Node, ReErr> {
331        let mut alts = vec![self.cat()?];
332        while self.at_alt() {
333            self.i += if self.ere { 1 } else { 2 };
334            alts.push(self.cat()?);
335        }
336        Ok(if alts.len() == 1 { alts.pop().unwrap_or(Node::Empty) } else { Node::Alt(alts) })
337    }
338    fn cat(&mut self) -> Result<Node, ReErr> {
339        let mut v: Vec<Node> = Vec::new();
340        let begin = self.i;
341        while self.i < self.p.len() && !self.at_alt() && !(self.depth > 0 && self.at_close()) {
342            if self.at_close() {
343                // ")" without a group: ERE takes it as a character only in GNU's lax way
344                return Err(ReErr::CloseParen);
345            }
346            let first = self.i == begin;
347            let atom = self.atom(first)?;
348            let atom = self.reps(atom)?;
349            v.push(atom);
350        }
351        Ok(match v.len() {
352            0 => Node::Empty,
353            1 => v.pop().unwrap_or(Node::Empty),
354            _ => Node::Cat(v),
355        })
356    }
357    /// an interval's numbers from just after its "{" up to and with its "}" ("\}" in BRE);
358    /// None when it is none (ERE: then "{" is a character)
359    fn interval(&mut self) -> Result<Option<(u32, Option<u32>)>, ReErr> {
360        let save = self.i;
361        let num = |s: &mut Parser| -> Option<u32> {
362            let st = s.i;
363            while s.peek().is_some_and(|c| c.is_ascii_digit()) {
364                s.i += 1;
365            }
366            if s.i == st {
367                return None;
368            }
369            let t: alloc::string::String = s.p[st..s.i].iter().collect();
370            Some(t.parse::<u32>().unwrap_or(u32::MAX))
371        };
372        let lo = num(self);
373        let comma = self.peek() == Some(',');
374        if comma {
375            self.i += 1;
376        }
377        let hi = if comma { num(self) } else { lo };
378        let closed = if self.ere {
379            if self.peek() == Some('}') {
380                self.i += 1;
381                true
382            } else {
383                false
384            }
385        } else if self.peek() == Some('\\') && self.peek2() == Some('}') {
386            self.i += 2;
387            true
388        } else {
389            false
390        };
391        if !closed || (lo.is_none() && !comma) {
392            if self.ere {
393                self.i = save;
394                return Ok(None);
395            }
396            return Err(if closed { ReErr::BraceContent } else { ReErr::Brace });
397        }
398        // "{,n}" is "{0,n}" (GNU)
399        let lo = lo.unwrap_or(0);
400        if lo > REP_MAX || hi.is_some_and(|h| h > REP_MAX || h < lo) {
401            return Err(if hi.is_some_and(|h| h < lo) { ReErr::BraceContent } else { ReErr::TooBig });
402        }
403        Ok(Some((lo, hi)))
404    }
405    /// the repetitions after an atom
406    fn reps(&mut self, mut atom: Node) -> Result<Node, ReErr> {
407        loop {
408            // an anchor does not repeat: the "*" after it is a character (GNU)
409            if matches!(atom, Node::Edge(_)) {
410                return Ok(atom);
411            }
412            let (lo, hi) = match (self.peek(), self.peek2()) {
413                (Some('*'), _) => {
414                    self.i += 1;
415                    (0, None)
416                }
417                (Some('+'), _) if self.ere => {
418                    self.i += 1;
419                    (1, None)
420                }
421                (Some('?'), _) if self.ere => {
422                    self.i += 1;
423                    (0, Some(1))
424                }
425                (Some('\\'), Some('+')) if !self.ere => {
426                    self.i += 2;
427                    (1, None)
428                }
429                (Some('\\'), Some('?')) if !self.ere => {
430                    self.i += 2;
431                    (0, Some(1))
432                }
433                (Some('{'), _) if self.ere => {
434                    self.i += 1;
435                    match self.interval()? {
436                        Some(x) => x,
437                        None => {
438                            // "{" that starts no interval is a character
439                            self.i -= 1;
440                            return Ok(atom);
441                        }
442                    }
443                }
444                (Some('\\'), Some('{')) if !self.ere => {
445                    self.i += 2;
446                    match self.interval()? {
447                        Some(x) => x,
448                        None => return Err(ReErr::Brace),
449                    }
450                }
451                _ => return Ok(atom),
452            };
453            // a repetition of a repetition that may be empty makes no new strings: x** is x*
454            if let Node::Rep(_, 0, None) = atom
455                && lo <= 1
456            {
457                continue;
458            }
459            atom = Node::Rep(Box::new(atom), lo, hi);
460        }
461    }
462    fn atom(&mut self, first: bool) -> Result<Node, ReErr> {
463        let Some(c) = self.peek() else { return Ok(Node::Empty) };
464        self.i += 1;
465        match c {
466            '.' => Ok(Node::Any),
467            '[' => {
468                let (set, next) = match bracket(self.p, self.i, false) {
469                    Some(x) => x,
470                    None => return Err(self.bracket_err()),
471                };
472                self.i = next;
473                Ok(Node::Set(set))
474            }
475            '^' if self.ere || first => Ok(Node::Edge(Edge::Bol)),
476            '$' if self.ere || self.i == self.p.len() || self.at_close() || self.at_alt() => Ok(Node::Edge(Edge::Eol)),
477            // a repetition with nothing before it stands for itself
478            '*' => Ok(Node::Char('*')),
479            '+' | '?' if self.ere && first => Ok(Node::Char(c)),
480            '{' if self.ere && first => Ok(Node::Char('{')),
481            '(' if self.ere => self.group(),
482            '\\' => {
483                let Some(e) = self.peek() else { return Err(ReErr::Backslash) };
484                self.i += 1;
485                match e {
486                    '(' if !self.ere => self.group(),
487                    '{' if !self.ere && first => Ok(Node::Char('{')),
488                    'w' => Ok(Node::Set(Set::word(false))),
489                    'W' => Ok(Node::Set(Set::word(true))),
490                    's' => Ok(Node::Set(Set::space(false))),
491                    'S' => Ok(Node::Set(Set::space(true))),
492                    '<' => Ok(Node::Edge(Edge::WordStart)),
493                    '>' => Ok(Node::Edge(Edge::WordEnd)),
494                    'b' => Ok(Node::Edge(Edge::Word)),
495                    'B' => Ok(Node::Edge(Edge::NotWord)),
496                    'n' => Ok(Node::Char('\n')),
497                    't' => Ok(Node::Char('\t')),
498                    x => Ok(Node::Char(x)),
499                }
500            }
501            x => Ok(Node::Char(x)),
502        }
503    }
504    fn bracket_err(&self) -> ReErr {
505        // a range backwards or a class that does not exist, else the bracket is open
506        let rest = &self.p[self.i..];
507        let end = rest.iter().skip(1).position(|&c| c == ']').map(|x| x + 1);
508        match end {
509            Some(e) => {
510                let body = &rest[..e];
511                if body.windows(2).any(|w| w == ['[', ':']) {
512                    ReErr::Class
513                } else if body.windows(3).any(|w| w[1] == '-' && w[2] < w[0]) {
514                    ReErr::Range
515                } else {
516                    ReErr::Bracket
517                }
518            }
519            None => ReErr::Bracket,
520        }
521    }
522    fn group(&mut self) -> Result<Node, ReErr> {
523        self.depth += 1;
524        let inner = self.alt()?;
525        self.depth -= 1;
526        if !self.at_close() {
527            return Err(ReErr::Paren);
528        }
529        self.i += if self.ere { 1 } else { 2 };
530        Ok(inner)
531    }
532}
533
534#[derive(Clone, Debug, PartialEq, Eq)]
535enum Inst {
536    Char(char),
537    Any,
538    Set(usize),
539    Edge(Edge),
540    Split(usize, usize),
541    Jmp(usize),
542    Match,
543}
544
545/// a compiled regular expression
546#[derive(Clone, Debug, PartialEq, Eq)]
547pub struct Regex {
548    prog: Vec<Inst>,
549    sets: Vec<Set>,
550    icase: bool,
551}
552
553struct Comp {
554    prog: Vec<Inst>,
555    sets: Vec<Set>,
556}
557
558impl Comp {
559    fn emit(&mut self, i: Inst) -> Result<usize, ReErr> {
560        if self.prog.len() >= PROG_MAX {
561            return Err(ReErr::TooBig);
562        }
563        self.prog.push(i);
564        Ok(self.prog.len() - 1)
565    }
566    fn node(&mut self, n: &Node) -> Result<(), ReErr> {
567        match n {
568            Node::Empty => {}
569            Node::Char(c) => {
570                self.emit(Inst::Char(*c))?;
571            }
572            Node::Any => {
573                self.emit(Inst::Any)?;
574            }
575            Node::Set(s) => {
576                self.sets.push(s.clone());
577                let k = self.sets.len() - 1;
578                self.emit(Inst::Set(k))?;
579            }
580            Node::Edge(e) => {
581                self.emit(Inst::Edge(*e))?;
582            }
583            Node::Cat(v) => {
584                for x in v {
585                    self.node(x)?;
586                }
587            }
588            Node::Alt(v) => {
589                let mut jumps = Vec::new();
590                for (k, x) in v.iter().enumerate() {
591                    if k + 1 < v.len() {
592                        let split = self.emit(Inst::Split(0, 0))?;
593                        self.node(x)?;
594                        jumps.push(self.emit(Inst::Jmp(0))?);
595                        let next = self.prog.len();
596                        self.prog[split] = Inst::Split(split + 1, next);
597                    } else {
598                        self.node(x)?;
599                    }
600                }
601                let end = self.prog.len();
602                for j in jumps {
603                    self.prog[j] = Inst::Jmp(end);
604                }
605            }
606            Node::Rep(x, lo, hi) => {
607                for _ in 0..*lo {
608                    self.node(x)?;
609                }
610                match hi {
611                    None => {
612                        // x*
613                        let split = self.emit(Inst::Split(0, 0))?;
614                        self.node(x)?;
615                        self.emit(Inst::Jmp(split))?;
616                        let end = self.prog.len();
617                        self.prog[split] = Inst::Split(split + 1, end);
618                    }
619                    Some(h) => {
620                        // (x(x(x)?)?)? for the optional ones
621                        let mut splits = Vec::new();
622                        for _ in *lo..*h {
623                            splits.push(self.emit(Inst::Split(0, 0))?);
624                            self.node(x)?;
625                        }
626                        let end = self.prog.len();
627                        for s in splits {
628                            self.prog[s] = Inst::Split(s + 1, end);
629                        }
630                    }
631                }
632            }
633        }
634        Ok(())
635    }
636}
637
638fn is_word(c: Option<char>) -> bool {
639    c.is_some_and(|c| c.is_alphanumeric() || c == '_')
640}
641
642impl Regex {
643    /// compiles an expression; `icase`: upper and lower case are the same
644    pub fn new(pat: &str, syntax: Syntax, icase: bool) -> Result<Regex, ReErr> {
645        let p: Vec<char> = pat.chars().collect();
646        let mut ps = Parser { p: &p, i: 0, ere: syntax == Syntax::Extended, depth: 0 };
647        let node = ps.alt()?;
648        if ps.i < p.len() {
649            return Err(if ps.at_close() { ReErr::CloseParen } else { ReErr::Paren });
650        }
651        let mut c = Comp { prog: Vec::new(), sets: Vec::new() };
652        c.node(&node)?;
653        c.emit(Inst::Match)?;
654        Ok(Regex { prog: c.prog, sets: c.sets, icase })
655    }
656
657    /// the expression matches somewhere in s
658    pub fn is_match(&self, s: &str) -> bool {
659        self.find(s).is_some()
660    }
661
662    /// the leftmost match (the longest of those starting there): byte offsets
663    pub fn find(&self, s: &str) -> Option<(usize, usize)> {
664        self.find_at(s, 0)
665    }
666
667    /// as find, starting the search at byte `from` (the edges still see the text before it)
668    pub fn find_at(&self, s: &str, from: usize) -> Option<(usize, usize)> {
669        let chars: Vec<(usize, char)> = s.char_indices().collect();
670        let start_k = chars.iter().position(|&(b, _)| b >= from).unwrap_or(chars.len());
671        // threads: (pc, start byte) in priority order (their starts never decrease along the
672        // list); `seen` holds the position each pc was last added at
673        let mut cur: Vec<(usize, usize)> = Vec::new();
674        let mut next: Vec<(usize, usize)> = Vec::new();
675        let mut seen = vec![usize::MAX; self.prog.len()];
676        let mut best: Option<(usize, usize)> = None;
677        let byte_at = |k: usize| chars.get(k).map_or(s.len(), |x| x.0);
678        let ch = |k: usize| chars.get(k).map(|x| x.1);
679        let mut k = start_k;
680        loop {
681            let prev = if k == 0 { None } else { ch(k - 1) };
682            let here = ch(k);
683            // a new thread at this position while nothing matched yet
684            if best.is_none() {
685                self.add(&mut cur, &mut seen, k, 0, byte_at(k), prev, here);
686            }
687            next.clear();
688            for &(pc, st) in cur.iter() {
689                let step = match &self.prog[pc] {
690                    Inst::Match => {
691                        let end = byte_at(k);
692                        if best.is_none_or(|(bs, be)| st < bs || (st == bs && end > be)) {
693                            best = Some((st, end));
694                        }
695                        false
696                    }
697                    Inst::Char(c) => here.is_some_and(|h| h == *c || (self.icase && lower(h) == lower(*c))),
698                    Inst::Any => here.is_some_and(|h| h != '\n'),
699                    Inst::Set(i) => here.is_some_and(|h| self.sets[*i].holds(h, self.icase)),
700                    _ => false,
701                };
702                if step {
703                    self.add(&mut next, &mut seen, k + 1, pc + 1, st, here, ch(k + 1));
704                }
705            }
706            // a thread that started after the best match's start cannot win any more
707            if let Some((bs, _)) = best {
708                next.retain(|t| t.1 <= bs);
709            }
710            if k >= chars.len() || (next.is_empty() && best.is_some()) {
711                break;
712            }
713            core::mem::swap(&mut cur, &mut next);
714            k += 1;
715        }
716        best
717    }
718
719    /// adds a thread at character `k` (prev / here: the characters around the position),
720    /// following jumps, splits and edges
721    #[allow(clippy::too_many_arguments)]
722    fn add(&self, list: &mut Vec<(usize, usize)>, seen: &mut [usize], k: usize, pc: usize, st: usize, prev: Option<char>, here: Option<char>) {
723        if seen[pc] == k {
724            return;
725        }
726        seen[pc] = k;
727        match &self.prog[pc] {
728            Inst::Jmp(t) => self.add(list, seen, k, *t, st, prev, here),
729            Inst::Split(a, b) => {
730                self.add(list, seen, k, *a, st, prev, here);
731                self.add(list, seen, k, *b, st, prev, here);
732            }
733            Inst::Edge(e) => {
734                let ok = match e {
735                    Edge::Bol => prev.is_none() || prev == Some('\n'),
736                    Edge::Eol => here.is_none() || here == Some('\n'),
737                    Edge::WordStart => !is_word(prev) && is_word(here),
738                    Edge::WordEnd => is_word(prev) && !is_word(here),
739                    Edge::Word => is_word(prev) != is_word(here),
740                    Edge::NotWord => is_word(prev) == is_word(here),
741                };
742                if ok {
743                    self.add(list, seen, k, pc + 1, st, prev, here);
744                }
745            }
746            _ => list.push((pc, st)),
747        }
748    }
749}
base/pattern.rs

base/
pattern.rs
