regex_automata/meta/
literal.rs

1use alloc::{vec, vec::Vec};
2
3use regex_syntax::hir::Hir;
4
5use crate::{meta::regex::RegexInfo, util::search::MatchKind};
6
7/// Pull out an alternation of literals from the given sequence of HIR
8/// expressions.
9///
10/// There are numerous ways for this to fail. Generally, this only applies
11/// to regexes of the form 'foo|bar|baz|...|quux'. It can also fail if there
12/// are "too few" alternates, in which case, the regex engine is likely faster.
13///
14/// And currently, this only returns something when 'hirs.len() == 1'.
15pub(crate) fn alternation_literals(
16    info: &RegexInfo,
17    hirs: &[&Hir],
18) -> Option<Vec<Vec<u8>>> {
19    use regex_syntax::hir::{HirKind, Literal};
20
21    // Might as well skip the work below if we know we can't build an
22    // Aho-Corasick searcher.
23    if !cfg!(feature = "perf-literal-multisubstring") {
24        return None;
25    }
26    // This is pretty hacky, but basically, if `is_alternation_literal` is
27    // true, then we can make several assumptions about the structure of our
28    // HIR. This is what justifies the `unreachable!` statements below.
29    if hirs.len() != 1
30        || !info.props()[0].look_set().is_empty()
31        || info.props()[0].explicit_captures_len() > 0
32        || !info.props()[0].is_alternation_literal()
33        || info.config().get_match_kind() != MatchKind::LeftmostFirst
34    {
35        return None;
36    }
37    let hir = &hirs[0];
38    let alts = match *hir.kind() {
39        HirKind::Alternation(ref alts) => alts,
40        _ => return None, // one literal isn't worth it
41    };
42
43    let mut lits = vec![];
44    for alt in alts {
45        let mut lit = vec![];
46        match *alt.kind() {
47            HirKind::Literal(Literal(ref bytes)) => {
48                lit.extend_from_slice(bytes)
49            }
50            HirKind::Concat(ref exprs) => {
51                for e in exprs {
52                    match *e.kind() {
53                        HirKind::Literal(Literal(ref bytes)) => {
54                            lit.extend_from_slice(bytes);
55                        }
56                        _ => unreachable!("expected literal, got {:?}", e),
57                    }
58                }
59            }
60            _ => unreachable!("expected literal or concat, got {:?}", alt),
61        }
62        lits.push(lit);
63    }
64    // Why do this? Well, when the number of literals is small, it's likely
65    // that we'll use the lazy DFA which is in turn likely to be faster than
66    // Aho-Corasick in such cases. Primarily because Aho-Corasick doesn't have
67    // a "lazy DFA" but either a contiguous NFA or a full DFA. We rarely use
68    // the latter because it is so hungry (in time and space), and the former
69    // is decently fast, but not as fast as a well oiled lazy DFA.
70    //
71    // However, once the number starts getting large, the lazy DFA is likely
72    // to start thrashing because of the modest default cache size. When
73    // exactly does this happen? Dunno. But at whatever point that is (we make
74    // a guess below based on ad hoc benchmarking), we'll want to cut over to
75    // Aho-Corasick, where even the contiguous NFA is likely to do much better.
76    if lits.len() < 3000 {
77        debug!("skipping Aho-Corasick because there are too few literals");
78        return None;
79    }
80    Some(lits)
81}
regex_automata/meta/literal.rs

regex_automata/meta/
literal.rs
