regex_automata/meta/
reverse_suffix.rs

1/*!
2Routines specific to the reverse suffix optimization.
3*/
4
5use alloc::vec::Vec;
6
7use regex_syntax::hir::{literal::Literal, Hir, HirKind, Repetition};
8
9use crate::meta::prefix;
10
11/// Returns true when it's impossible for an earlier match to be detected after
12/// a literal candidate (corresponding to `suffix`) has been found.
13///
14/// Specifically, that there is no earlier match than what a reverse scan of
15/// `hirs` after a match of `suffix` reports.
16///
17/// At present, this always returns `false` when `hirs` has any length except
18/// `1`. That is, this optimization does not apply to multi-regex.
19pub(super) fn has_no_earlier_match(hirs: &[&Hir], suffix: &[u8]) -> bool {
20    if hirs.len() != 1 || suffix.is_empty() {
21        return false;
22    }
23    let hir = hirs[0];
24    let Some(prefix) = strip_literal_suffix(hir, suffix) else { return false };
25
26    let fixed_length = prefix::hir_has_fixed_length(&prefix);
27    debug!("reverse suffix has fixed length prefix? {fixed_length}");
28    if fixed_length {
29        return true;
30    }
31
32    let class_separator = prefix::has_disjoint_class_separator(
33        &prefix,
34        &[Literal::inexact(suffix)],
35    );
36    debug!("reverse suffix has disjoint class separator? {class_separator}");
37    if class_separator {
38        return true;
39    }
40
41    let internal = prefix::hir_can_contain_literal(&prefix, suffix);
42    debug!("reverse suffix has internal suffix? {internal}");
43    if !internal {
44        return true;
45    }
46
47    // We couldn't prove that the reverse suffix optimization
48    // was safe, so bail out.
49    false
50}
51
52/// Strip `suffix` from the end of `hir` and return the HIR that remains.
53///
54/// This is conservative. It returns `None` when the structure of the HIR does
55/// not make the suffix straightforward to remove, even when `suffix` might be
56/// required by the pattern.
57fn strip_literal_suffix(hir: &Hir, suffix: &[u8]) -> Option<Hir> {
58    let (prefix, suffix_cursor) =
59        strip_literal_suffix_at(hir, suffix, suffix.len())?;
60    if suffix_cursor == 0 {
61        Some(prefix)
62    } else {
63        None
64    }
65}
66
67/// Strip a terminal part of `suffix[..suffix_cursor]` from the end of `hir`.
68///
69/// The returned cursor marks the end of the part of `suffix` that remains to
70/// be stripped. Thus, this call removes `suffix[after..suffix_cursor]`, where
71/// `after` is the returned cursor. A non-zero cursor may be returned only when
72/// the returned HIR cannot consume any bytes. This lets a concatenation
73/// continue stripping from its preceding child without losing adjacency.
74fn strip_literal_suffix_at(
75    hir: &Hir,
76    suffix: &[u8],
77    suffix_cursor: usize,
78) -> Option<(Hir, usize)> {
79    if suffix_cursor == 0 {
80        return Some((hir.clone(), 0));
81    }
82    match hir.kind() {
83        HirKind::Literal(lit) => {
84            let bytes = &lit.0;
85            let mut len = 0;
86            while len < bytes.len()
87                && len < suffix_cursor
88                && bytes[bytes.len() - len - 1]
89                    == suffix[suffix_cursor - len - 1]
90            {
91                len += 1;
92            }
93            if len == 0 || (len < bytes.len() && len < suffix_cursor) {
94                return None;
95            }
96            Some((
97                Hir::literal(bytes[..bytes.len() - len].to_vec()),
98                suffix_cursor - len,
99            ))
100        }
101        HirKind::Capture(capture) => {
102            strip_literal_suffix_at(&capture.sub, suffix, suffix_cursor)
103        }
104        HirKind::Concat(hirs) => {
105            let mut prefix = hirs.to_vec();
106            let mut cursor = suffix_cursor;
107            for i in (0..prefix.len()).rev() {
108                let (stripped, after) =
109                    strip_literal_suffix_at(&prefix[i], suffix, cursor)?;
110                if after == cursor {
111                    return None;
112                }
113                prefix[i] = stripped;
114                cursor = after;
115                if cursor == 0 {
116                    break;
117                }
118            }
119            Some((Hir::concat(prefix), cursor))
120        }
121        HirKind::Repetition(rep) => {
122            strip_repetition_literal_suffix(rep, suffix, suffix_cursor)
123        }
124        _ => None,
125    }
126}
127
128fn strip_repetition_literal_suffix(
129    rep: &Repetition,
130    suffix: &[u8],
131    suffix_cursor: usize,
132) -> Option<(Hir, usize)> {
133    let mut min = rep.min;
134    let mut max = rep.max;
135    let mut cursor = suffix_cursor;
136    let mut tail = Vec::new();
137    while cursor > 0 {
138        if min == 0 {
139            return None;
140        }
141        let before = cursor;
142        let (stripped, after) =
143            strip_literal_suffix_at(&rep.sub, suffix, cursor)?;
144        if after == before {
145            return None;
146        }
147        min = min.saturating_sub(1);
148        max = max.map(|max| max.saturating_sub(1));
149        if !matches!(stripped.kind(), HirKind::Empty) {
150            tail.push(stripped);
151        }
152        cursor = after;
153    }
154
155    let rest = Hir::repetition(Repetition {
156        min,
157        max,
158        greedy: rep.greedy,
159        sub: rep.sub.clone(),
160    });
161    let mut prefix = Vec::with_capacity(tail.len() + 1);
162    if !matches!(rest.kind(), HirKind::Empty) {
163        prefix.push(rest);
164    }
165    tail.reverse();
166    prefix.extend(tail);
167    Some((Hir::concat(prefix), 0))
168}
169
170// We only test when we have `unicode-perl` here since some regexes require
171// that.
172#[cfg(all(feature = "unicode-perl", not(miri),))]
173#[cfg(test)]
174mod tests {
175    use crate::util::syntax;
176
177    use super::*;
178
179    #[track_caller]
180    fn assert_strip(pattern: &str, suffix: &str, expected: Option<&str>) {
181        let hir = syntax::parse(pattern).unwrap();
182        let got = strip_literal_suffix(&hir, suffix.as_bytes());
183        let expected = expected.map(|pattern| syntax::parse(pattern).unwrap());
184        assert_eq!(expected, got);
185    }
186
187    #[test]
188    fn literal() {
189        assert_strip("foobar", "bar", Some("foo"));
190        assert_strip("foobar", "foobar", Some(""));
191        assert_strip("foobar", "", Some("foobar"));
192    }
193
194    #[test]
195    fn capture() {
196        assert_strip(r".+foo(bar)", "foobar", Some(r".+"));
197    }
198
199    #[test]
200    fn concat() {
201        assert_strip(r".+(?:ab){2}cd", "ababcd", Some(r".+"));
202        assert_strip(r"a(?:)cd", "acd", Some(r""));
203        assert_strip(r"az{0}cd", "acd", Some(r""));
204        assert_strip(r"az{2}cd", "acd", None);
205        assert_strip(r"az{0,2}cd", "acd", None);
206    }
207
208    #[test]
209    fn repetition() {
210        assert_strip(r"x(?:ab){3}", "bab", Some("xaba"));
211        assert_strip(r"x(?:ab){2,}", "bab", Some(r"x(?:ab)*a"));
212    }
213
214    #[test]
215    fn mismatch() {
216        assert_strip("foobar", "baz", None);
217        assert_strip("foobar", "xfoobar", None);
218        assert_strip(r"foo[a-z]", "a", None);
219    }
220
221    #[test]
222    fn suffix_must_be_adjacent() {
223        assert_strip(r"foo(xbar)", "foobar", None);
224    }
225
226    #[test]
227    fn repetition_must_be_required() {
228        assert_strip(r"x(?:ab)*cd", "abcd", None);
229    }
230
231    #[track_caller]
232    fn assert_fixed_length_prefix(yes: bool, pattern: &str, suffix: &[u8]) {
233        let hir = syntax::parse(pattern).unwrap();
234        assert_eq!(
235            yes,
236            strip_literal_suffix(&hir, suffix)
237                .map_or(false, |hir| prefix::hir_has_fixed_length(&hir)),
238        );
239    }
240
241    #[track_caller]
242    fn assert_internal_suffix(yes: bool, pattern: &str, suffix: &[u8]) {
243        let hir = syntax::parse(pattern).unwrap();
244        assert_eq!(
245            yes,
246            strip_literal_suffix(&hir, suffix).map_or(false, |hir| {
247                prefix::hir_can_contain_literal(&hir, suffix)
248            }),
249        );
250    }
251
252    #[test]
253    fn reverse_suffix_accepts_prefix_without_internal_suffix() {
254        assert_internal_suffix(false, r"\d+XYZ", b"XYZ");
255        assert_internal_suffix(false, r"[a-q][^u-z]{13}x", b"x");
256    }
257
258    #[test]
259    fn reverse_suffix_accepts_fixed_length_prefix() {
260        assert_fixed_length_prefix(true, r"(?:ab|cd)XYZ", b"XYZ");
261        assert_internal_suffix(true, r"[A-Z][0-9]XYZ", b"XYZ");
262        assert_fixed_length_prefix(true, r"[A-Z][0-9]XYZ", b"XYZ");
263    }
264
265    #[test]
266    fn reverse_suffix_fixed_length_prefix_is_conservative() {
267        assert_fixed_length_prefix(false, r"a{1,3}yy", b"yy");
268        assert_fixed_length_prefix(false, r"a*yy", b"yy");
269    }
270}
regex_automata/meta/reverse_suffix.rs

regex_automata/meta/
reverse_suffix.rs
