| 1 |
/*! |
| 2 |
Provides literal extraction from `Hir` expressions. |
| 3 |
|
| 4 |
An [`Extractor`] pulls literals out of [`Hir`] expressions and returns a |
| 5 |
[`Seq`] of [`Literal`]s. |
| 6 |
|
| 7 |
The purpose of literal extraction is generally to provide avenues for |
| 8 |
optimizing regex searches. The main idea is that substring searches can be an |
| 9 |
order of magnitude faster than a regex search. Therefore, if one can execute |
| 10 |
a substring search to find candidate match locations and only run the regex |
| 11 |
search at those locations, then it is possible for huge improvements in |
| 12 |
performance to be realized. |
| 13 |
|
| 14 |
With that said, literal optimizations are generally a black art because even |
| 15 |
though substring search is generally faster, if the number of candidates |
| 16 |
produced is high, then it can create a lot of overhead by ping-ponging between |
| 17 |
the substring search and the regex search. |
| 18 |
|
| 19 |
Here are some heuristics that might be used to help increase the chances of |
| 20 |
effective literal optimizations: |
| 21 |
|
| 22 |
* Stick to small [`Seq`]s. If you search for too many literals, it's likely |
| 23 |
to lead to substring search that is only a little faster than a regex search, |
| 24 |
and thus the overhead of using literal optimizations in the first place might |
| 25 |
make things slower overall. |
| 26 |
* The literals in your [`Seq`] shouldn't be too short. In general, longer is |
| 27 |
better. A sequence corresponding to single bytes that occur frequently in the |
| 28 |
haystack, for example, is probably a bad literal optimization because it's |
| 29 |
likely to produce many false positive candidates. Longer literals are less |
| 30 |
likely to match, and thus probably produce fewer false positives. |
| 31 |
* If it's possible to estimate the approximate frequency of each byte according |
| 32 |
to some pre-computed background distribution, it is possible to compute a score |
| 33 |
of how "good" a `Seq` is. If a `Seq` isn't good enough, you might consider |
| 34 |
skipping the literal optimization and just use the regex engine. |
| 35 |
|
| 36 |
(It should be noted that there are always pathological cases that can make |
| 37 |
any kind of literal optimization be a net slower result. This is why it |
| 38 |
might be a good idea to be conservative, or to even provide a means for |
| 39 |
literal optimizations to be dynamically disabled if they are determined to be |
| 40 |
ineffective according to some measure.) |
| 41 |
|
| 42 |
You're encouraged to explore the methods on [`Seq`], which permit shrinking |
| 43 |
the size of sequences in a preference-order preserving fashion. |
| 44 |
|
| 45 |
Finally, note that it isn't strictly necessary to use an [`Extractor`]. Namely, |
| 46 |
an `Extractor` only uses public APIs of the [`Seq`] and [`Literal`] types, |
| 47 |
so it is possible to implement your own extractor. For example, for n-grams |
| 48 |
or "inner" literals (i.e., not prefix or suffix literals). The `Extractor` |
| 49 |
is mostly responsible for the case analysis over `Hir` expressions. Much of |
| 50 |
the "trickier" parts are how to combine literal sequences, and that is all |
| 51 |
implemented on [`Seq`]. |
| 52 |
*/ |
| 53 |
|
| 54 |
use core::{cmp, mem, num::NonZeroUsize}; |
| 55 |
|
| 56 |
use alloc::{vec, vec::Vec}; |
| 57 |
|
| 58 |
use crate::hir::{self, Hir}; |
| 59 |
|
| 60 |
/// Extracts prefix or suffix literal sequences from [`Hir`] expressions. |
| 61 |
/// |
| 62 |
/// Literal extraction is based on the following observations: |
| 63 |
/// |
| 64 |
/// * Many regexes start with one or a small number of literals. |
| 65 |
/// * Substring search for literals is often much faster (sometimes by an order |
| 66 |
/// of magnitude) than a regex search. |
| 67 |
/// |
| 68 |
/// Thus, in many cases, one can search for literals to find candidate starting |
| 69 |
/// locations of a match, and then only run the full regex engine at each such |
| 70 |
/// location instead of over the full haystack. |
| 71 |
/// |
| 72 |
/// The main downside of literal extraction is that it can wind up causing a |
| 73 |
/// search to be slower overall. For example, if there are many matches or if |
| 74 |
/// there are many candidates that don't ultimately lead to a match, then a |
| 75 |
/// lot of overhead will be spent in shuffing back-and-forth between substring |
| 76 |
/// search and the regex engine. This is the fundamental reason why literal |
| 77 |
/// optimizations for regex patterns is sometimes considered a "black art." |
| 78 |
/// |
| 79 |
/// # Look-around assertions |
| 80 |
/// |
| 81 |
/// Literal extraction treats all look-around assertions as-if they match every |
| 82 |
/// empty string. So for example, the regex `\bquux\b` will yield a sequence |
| 83 |
/// containing a single exact literal `quux`. However, not all occurrences |
| 84 |
/// of `quux` correspond to a match a of the regex. For example, `\bquux\b` |
| 85 |
/// does not match `ZquuxZ` anywhere because `quux` does not fall on a word |
| 86 |
/// boundary. |
| 87 |
/// |
| 88 |
/// In effect, if your regex contains look-around assertions, then a match of |
| 89 |
/// an exact literal does not necessarily mean the regex overall matches. So |
| 90 |
/// you may still need to run the regex engine in such cases to confirm the |
| 91 |
/// match. |
| 92 |
/// |
| 93 |
/// The precise guarantee you get from a literal sequence is: if every literal |
| 94 |
/// in the sequence is exact and the original regex contains zero look-around |
| 95 |
/// assertions, then a preference-order multi-substring search of those |
| 96 |
/// literals will precisely match a preference-order search of the original |
| 97 |
/// regex. |
| 98 |
/// |
| 99 |
/// # Example |
| 100 |
/// |
| 101 |
/// This shows how to extract prefixes: |
| 102 |
/// |
| 103 |
/// ``` |
| 104 |
/// use regex_syntax::{hir::literal::{Extractor, Literal, Seq}, parse}; |
| 105 |
/// |
| 106 |
/// let hir = parse(r"(a|b|c)(x|y|z)[A-Z]+foo")?; |
| 107 |
/// let got = Extractor::new().extract(&hir); |
| 108 |
/// // All literals returned are "inexact" because none of them reach the |
| 109 |
/// // match state. |
| 110 |
/// let expected = Seq::from_iter([ |
| 111 |
/// Literal::inexact("ax"), |
| 112 |
/// Literal::inexact("ay"), |
| 113 |
/// Literal::inexact("az"), |
| 114 |
/// Literal::inexact("bx"), |
| 115 |
/// Literal::inexact("by"), |
| 116 |
/// Literal::inexact("bz"), |
| 117 |
/// Literal::inexact("cx"), |
| 118 |
/// Literal::inexact("cy"), |
| 119 |
/// Literal::inexact("cz"), |
| 120 |
/// ]); |
| 121 |
/// assert_eq!(expected, got); |
| 122 |
/// |
| 123 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 124 |
/// ``` |
| 125 |
/// |
| 126 |
/// This shows how to extract suffixes: |
| 127 |
/// |
| 128 |
/// ``` |
| 129 |
/// use regex_syntax::{ |
| 130 |
/// hir::literal::{Extractor, ExtractKind, Literal, Seq}, |
| 131 |
/// parse, |
| 132 |
/// }; |
| 133 |
/// |
| 134 |
/// let hir = parse(r"foo|[A-Z]+bar")?; |
| 135 |
/// let got = Extractor::new().kind(ExtractKind::Suffix).extract(&hir); |
| 136 |
/// // Since 'foo' gets to a match state, it is considered exact. But 'bar' |
| 137 |
/// // does not because of the '[A-Z]+', and thus is marked inexact. |
| 138 |
/// let expected = Seq::from_iter([ |
| 139 |
/// Literal::exact("foo"), |
| 140 |
/// Literal::inexact("bar"), |
| 141 |
/// ]); |
| 142 |
/// assert_eq!(expected, got); |
| 143 |
/// |
| 144 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 145 |
/// ``` |
| 146 |
#[derive(Clone, Debug)] |
| 147 |
pub struct Extractor { |
| 148 |
kind: ExtractKind, |
| 149 |
limit_class: usize, |
| 150 |
limit_repeat: usize, |
| 151 |
limit_literal_len: usize, |
| 152 |
limit_total: usize, |
| 153 |
} |
| 154 |
|
| 155 |
impl Extractor { |
| 156 |
/// Create a new extractor with a default configuration. |
| 157 |
/// |
| 158 |
/// The extractor can be optionally configured before calling |
| 159 |
/// [`Extractor::extract`] to get a literal sequence. |
| 160 |
pub fn new() -> Extractor { |
| 161 |
Extractor { |
| 162 |
kind: ExtractKind::Prefix, |
| 163 |
limit_class: 10, |
| 164 |
limit_repeat: 10, |
| 165 |
limit_literal_len: 100, |
| 166 |
limit_total: 250, |
| 167 |
} |
| 168 |
} |
| 169 |
|
| 170 |
/// Execute the extractor and return a sequence of literals. |
| 171 |
pub fn extract(&self, hir: &Hir) -> Seq { |
| 172 |
use crate::hir::HirKind::*; |
| 173 |
|
| 174 |
match *hir.kind() { |
| 175 |
Empty | Look(_) => Seq::singleton(self::Literal::exact(vec![])), |
| 176 |
Literal(hir::Literal(ref bytes)) => { |
| 177 |
let mut seq = |
| 178 |
Seq::singleton(self::Literal::exact(bytes.to_vec())); |
| 179 |
self.enforce_literal_len(&mut seq); |
| 180 |
seq |
| 181 |
} |
| 182 |
Class(hir::Class::Unicode(ref cls)) => { |
| 183 |
self.extract_class_unicode(cls) |
| 184 |
} |
| 185 |
Class(hir::Class::Bytes(ref cls)) => self.extract_class_bytes(cls), |
| 186 |
Repetition(ref rep) => self.extract_repetition(rep), |
| 187 |
Capture(hir::Capture { ref sub, .. }) => self.extract(sub), |
| 188 |
Concat(ref hirs) => match self.kind { |
| 189 |
ExtractKind::Prefix => self.extract_concat(hirs.iter()), |
| 190 |
ExtractKind::Suffix => self.extract_concat(hirs.iter().rev()), |
| 191 |
}, |
| 192 |
Alternation(ref hirs) => { |
| 193 |
// Unlike concat, we always union starting from the beginning, |
| 194 |
// since the beginning corresponds to the highest preference, |
| 195 |
// which doesn't change based on forwards vs reverse. |
| 196 |
self.extract_alternation(hirs.iter()) |
| 197 |
} |
| 198 |
} |
| 199 |
} |
| 200 |
|
| 201 |
/// Set the kind of literal sequence to extract from an [`Hir`] expression. |
| 202 |
/// |
| 203 |
/// The default is to extract prefixes, but suffixes can be selected |
| 204 |
/// instead. The contract for prefixes is that every match of the |
| 205 |
/// corresponding `Hir` must start with one of the literals in the sequence |
| 206 |
/// returned. Moreover, the _order_ of the sequence returned corresponds to |
| 207 |
/// the preference order. |
| 208 |
/// |
| 209 |
/// Suffixes satisfy a similar contract in that every match of the |
| 210 |
/// corresponding `Hir` must end with one of the literals in the sequence |
| 211 |
/// returned. However, there is no guarantee that the literals are in |
| 212 |
/// preference order. |
| 213 |
/// |
| 214 |
/// Remember that a sequence can be infinite. For example, unless the |
| 215 |
/// limits are configured to be impractically large, attempting to extract |
| 216 |
/// prefixes (or suffixes) for the pattern `[A-Z]` will return an infinite |
| 217 |
/// sequence. Generally speaking, if the sequence returned is infinite, |
| 218 |
/// then it is presumed to be unwise to do prefix (or suffix) optimizations |
| 219 |
/// for the pattern. |
| 220 |
pub fn kind(&mut self, kind: ExtractKind) -> &mut Extractor { |
| 221 |
self.kind = kind; |
| 222 |
self |
| 223 |
} |
| 224 |
|
| 225 |
/// Configure a limit on the length of the sequence that is permitted for |
| 226 |
/// a character class. If a character class exceeds this limit, then the |
| 227 |
/// sequence returned for it is infinite. |
| 228 |
/// |
| 229 |
/// This prevents classes like `[A-Z]` or `\pL` from getting turned into |
| 230 |
/// huge and likely unproductive sequences of literals. |
| 231 |
/// |
| 232 |
/// # Example |
| 233 |
/// |
| 234 |
/// This example shows how this limit can be lowered to decrease the tolerance |
| 235 |
/// for character classes being turned into literal sequences. |
| 236 |
/// |
| 237 |
/// ``` |
| 238 |
/// use regex_syntax::{hir::literal::{Extractor, Seq}, parse}; |
| 239 |
/// |
| 240 |
/// let hir = parse(r"[0-9]")?; |
| 241 |
/// |
| 242 |
/// let got = Extractor::new().extract(&hir); |
| 243 |
/// let expected = Seq::new([ |
| 244 |
/// "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", |
| 245 |
/// ]); |
| 246 |
/// assert_eq!(expected, got); |
| 247 |
/// |
| 248 |
/// // Now let's shrink the limit and see how that changes things. |
| 249 |
/// let got = Extractor::new().limit_class(4).extract(&hir); |
| 250 |
/// let expected = Seq::infinite(); |
| 251 |
/// assert_eq!(expected, got); |
| 252 |
/// |
| 253 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 254 |
/// ``` |
| 255 |
pub fn limit_class(&mut self, limit: usize) -> &mut Extractor { |
| 256 |
self.limit_class = limit; |
| 257 |
self |
| 258 |
} |
| 259 |
|
| 260 |
/// Configure a limit on the total number of repetitions that is permitted |
| 261 |
/// before literal extraction is stopped. |
| 262 |
/// |
| 263 |
/// This is useful for limiting things like `(abcde){50}`, or more |
| 264 |
/// insidiously, `(?:){1000000000}`. This limit prevents any one single |
| 265 |
/// repetition from adding too much to a literal sequence. |
| 266 |
/// |
| 267 |
/// With this limit set, repetitions that exceed it will be stopped and any |
| 268 |
/// literals extracted up to that point will be made inexact. |
| 269 |
/// |
| 270 |
/// # Example |
| 271 |
/// |
| 272 |
/// This shows how to decrease the limit and compares it with the default. |
| 273 |
/// |
| 274 |
/// ``` |
| 275 |
/// use regex_syntax::{hir::literal::{Extractor, Literal, Seq}, parse}; |
| 276 |
/// |
| 277 |
/// let hir = parse(r"(abc){8}")?; |
| 278 |
/// |
| 279 |
/// let got = Extractor::new().extract(&hir); |
| 280 |
/// let expected = Seq::new(["abcabcabcabcabcabcabcabc"]); |
| 281 |
/// assert_eq!(expected, got); |
| 282 |
/// |
| 283 |
/// // Now let's shrink the limit and see how that changes things. |
| 284 |
/// let got = Extractor::new().limit_repeat(4).extract(&hir); |
| 285 |
/// let expected = Seq::from_iter([ |
| 286 |
/// Literal::inexact("abcabcabcabc"), |
| 287 |
/// ]); |
| 288 |
/// assert_eq!(expected, got); |
| 289 |
/// |
| 290 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 291 |
/// ``` |
| 292 |
pub fn limit_repeat(&mut self, limit: usize) -> &mut Extractor { |
| 293 |
self.limit_repeat = limit; |
| 294 |
self |
| 295 |
} |
| 296 |
|
| 297 |
/// Configure a limit on the maximum length of any literal in a sequence. |
| 298 |
/// |
| 299 |
/// This is useful for limiting things like `(abcde){5}{5}{5}{5}`. While |
| 300 |
/// each repetition or literal in that regex is small, when all the |
| 301 |
/// repetitions are applied, one ends up with a literal of length `5^4 = |
| 302 |
/// 625`. |
| 303 |
/// |
| 304 |
/// With this limit set, literals that exceed it will be made inexact and |
| 305 |
/// thus prevented from growing. |
| 306 |
/// |
| 307 |
/// # Example |
| 308 |
/// |
| 309 |
/// This shows how to decrease the limit and compares it with the default. |
| 310 |
/// |
| 311 |
/// ``` |
| 312 |
/// use regex_syntax::{hir::literal::{Extractor, Literal, Seq}, parse}; |
| 313 |
/// |
| 314 |
/// let hir = parse(r"(abc){2}{2}{2}")?; |
| 315 |
/// |
| 316 |
/// let got = Extractor::new().extract(&hir); |
| 317 |
/// let expected = Seq::new(["abcabcabcabcabcabcabcabc"]); |
| 318 |
/// assert_eq!(expected, got); |
| 319 |
/// |
| 320 |
/// // Now let's shrink the limit and see how that changes things. |
| 321 |
/// let got = Extractor::new().limit_literal_len(14).extract(&hir); |
| 322 |
/// let expected = Seq::from_iter([ |
| 323 |
/// Literal::inexact("abcabcabcabcab"), |
| 324 |
/// ]); |
| 325 |
/// assert_eq!(expected, got); |
| 326 |
/// |
| 327 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 328 |
/// ``` |
| 329 |
pub fn limit_literal_len(&mut self, limit: usize) -> &mut Extractor { |
| 330 |
self.limit_literal_len = limit; |
| 331 |
self |
| 332 |
} |
| 333 |
|
| 334 |
/// Configure a limit on the total number of literals that will be |
| 335 |
/// returned. |
| 336 |
/// |
| 337 |
/// This is useful as a practical measure for avoiding the creation of |
| 338 |
/// large sequences of literals. While the extractor will automatically |
| 339 |
/// handle local creations of large sequences (for example, `[A-Z]` yields |
| 340 |
/// an infinite sequence by default), large sequences can be created |
| 341 |
/// through non-local means as well. |
| 342 |
/// |
| 343 |
/// For example, `[ab]{3}{3}` would yield a sequence of length `512 = 2^9` |
| 344 |
/// despite each of the repetitions being small on their own. This limit |
| 345 |
/// thus represents a "catch all" for avoiding locally small sequences from |
| 346 |
/// combining into large sequences. |
| 347 |
/// |
| 348 |
/// # Example |
| 349 |
/// |
| 350 |
/// This example shows how reducing the limit will change the literal |
| 351 |
/// sequence returned. |
| 352 |
/// |
| 353 |
/// ``` |
| 354 |
/// use regex_syntax::{hir::literal::{Extractor, Literal, Seq}, parse}; |
| 355 |
/// |
| 356 |
/// let hir = parse(r"[ab]{2}{2}")?; |
| 357 |
/// |
| 358 |
/// let got = Extractor::new().extract(&hir); |
| 359 |
/// let expected = Seq::new([ |
| 360 |
/// "aaaa", "aaab", "aaba", "aabb", |
| 361 |
/// "abaa", "abab", "abba", "abbb", |
| 362 |
/// "baaa", "baab", "baba", "babb", |
| 363 |
/// "bbaa", "bbab", "bbba", "bbbb", |
| 364 |
/// ]); |
| 365 |
/// assert_eq!(expected, got); |
| 366 |
/// |
| 367 |
/// // The default limit is not too big, but big enough to extract all |
| 368 |
/// // literals from '[ab]{2}{2}'. If we shrink the limit to less than 16, |
| 369 |
/// // then we'll get a truncated set. Notice that it returns a sequence of |
| 370 |
/// // length 4 even though our limit was 10. This is because the sequence |
| 371 |
/// // is difficult to increase without blowing the limit. Notice also |
| 372 |
/// // that every literal in the sequence is now inexact because they were |
| 373 |
/// // stripped of some suffix. |
| 374 |
/// let got = Extractor::new().limit_total(10).extract(&hir); |
| 375 |
/// let expected = Seq::from_iter([ |
| 376 |
/// Literal::inexact("aa"), |
| 377 |
/// Literal::inexact("ab"), |
| 378 |
/// Literal::inexact("ba"), |
| 379 |
/// Literal::inexact("bb"), |
| 380 |
/// ]); |
| 381 |
/// assert_eq!(expected, got); |
| 382 |
/// |
| 383 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 384 |
/// ``` |
| 385 |
pub fn limit_total(&mut self, limit: usize) -> &mut Extractor { |
| 386 |
self.limit_total = limit; |
| 387 |
self |
| 388 |
} |
| 389 |
|
| 390 |
/// Extract a sequence from the given concatenation. Sequences from each of |
| 391 |
/// the child HIR expressions are combined via cross product. |
| 392 |
/// |
| 393 |
/// This short circuits once the cross product turns into a sequence |
| 394 |
/// containing only inexact literals. |
| 395 |
fn extract_concat<'a, I: Iterator<Item = &'a Hir>>(&self, it: I) -> Seq { |
| 396 |
let mut seq = Seq::singleton(self::Literal::exact(vec![])); |
| 397 |
for hir in it { |
| 398 |
// If every element in the sequence is inexact, then a cross |
| 399 |
// product will always be a no-op. Thus, there is nothing else we |
| 400 |
// can add to it and can quit early. Note that this also includes |
| 401 |
// infinite sequences. |
| 402 |
if seq.is_inexact() { |
| 403 |
break; |
| 404 |
} |
| 405 |
// Note that 'cross' also dispatches based on whether we're |
| 406 |
// extracting prefixes or suffixes. |
| 407 |
seq = self.cross(seq, &mut self.extract(hir)); |
| 408 |
} |
| 409 |
seq |
| 410 |
} |
| 411 |
|
| 412 |
/// Extract a sequence from the given alternation. |
| 413 |
/// |
| 414 |
/// This short circuits once the union turns into an infinite sequence. |
| 415 |
fn extract_alternation<'a, I: Iterator<Item = &'a Hir>>( |
| 416 |
&self, |
| 417 |
it: I, |
| 418 |
) -> Seq { |
| 419 |
let mut seq = Seq::empty(); |
| 420 |
for hir in it { |
| 421 |
// Once our 'seq' is infinite, every subsequent union |
| 422 |
// operation on it will itself always result in an |
| 423 |
// infinite sequence. Thus, it can never change and we can |
| 424 |
// short-circuit. |
| 425 |
if !seq.is_finite() { |
| 426 |
break; |
| 427 |
} |
| 428 |
seq = self.union(seq, &mut self.extract(hir)); |
| 429 |
} |
| 430 |
seq |
| 431 |
} |
| 432 |
|
| 433 |
/// Extract a sequence of literals from the given repetition. We do our |
| 434 |
/// best, Some examples: |
| 435 |
/// |
| 436 |
/// 'a*' => [inexact(a), exact("")] |
| 437 |
/// 'a*?' => [exact(""), inexact(a)] |
| 438 |
/// 'a+' => [inexact(a)] |
| 439 |
/// 'a{3}' => [exact(aaa)] |
| 440 |
/// 'a{3,5} => [inexact(aaa)] |
| 441 |
/// |
| 442 |
/// The key here really is making sure we get the 'inexact' vs 'exact' |
| 443 |
/// attributes correct on each of the literals we add. For example, the |
| 444 |
/// fact that 'a*' gives us an inexact 'a' and an exact empty string means |
| 445 |
/// that a regex like 'ab*c' will result in [inexact(ab), exact(ac)] |
| 446 |
/// literals being extracted, which might actually be a better prefilter |
| 447 |
/// than just 'a'. |
| 448 |
fn extract_repetition(&self, rep: &hir::Repetition) -> Seq { |
| 449 |
let mut subseq = self.extract(&rep.sub); |
| 450 |
match *rep { |
| 451 |
hir::Repetition { min: 0, max, greedy, .. } => { |
| 452 |
// When 'max=1', we can retain exactness, since 'a?' is |
| 453 |
// equivalent to 'a|'. Similarly below, 'a??' is equivalent to |
| 454 |
// '|a'. |
| 455 |
if max != Some(1) { |
| 456 |
subseq.make_inexact(); |
| 457 |
} |
| 458 |
let mut empty = Seq::singleton(Literal::exact(vec![])); |
| 459 |
if !greedy { |
| 460 |
mem::swap(&mut subseq, &mut empty); |
| 461 |
} |
| 462 |
self.union(subseq, &mut empty) |
| 463 |
} |
| 464 |
hir::Repetition { min, max: Some(max), .. } if min == max => { |
| 465 |
assert!(min > 0); // handled above |
| 466 |
let limit = |
| 467 |
u32::try_from(self.limit_repeat).unwrap_or(u32::MAX); |
| 468 |
let mut seq = Seq::singleton(Literal::exact(vec![])); |
| 469 |
for _ in 0..cmp::min(min, limit) { |
| 470 |
if seq.is_inexact() { |
| 471 |
break; |
| 472 |
} |
| 473 |
seq = self.cross(seq, &mut subseq.clone()); |
| 474 |
} |
| 475 |
if usize::try_from(min).is_err() || min > limit { |
| 476 |
seq.make_inexact(); |
| 477 |
} |
| 478 |
seq |
| 479 |
} |
| 480 |
hir::Repetition { min, .. } => { |
| 481 |
assert!(min > 0); // handled above |
| 482 |
let limit = |
| 483 |
u32::try_from(self.limit_repeat).unwrap_or(u32::MAX); |
| 484 |
let mut seq = Seq::singleton(Literal::exact(vec![])); |
| 485 |
for _ in 0..cmp::min(min, limit) { |
| 486 |
if seq.is_inexact() { |
| 487 |
break; |
| 488 |
} |
| 489 |
seq = self.cross(seq, &mut subseq.clone()); |
| 490 |
} |
| 491 |
seq.make_inexact(); |
| 492 |
seq |
| 493 |
} |
| 494 |
} |
| 495 |
} |
| 496 |
|
| 497 |
/// Convert the given Unicode class into a sequence of literals if the |
| 498 |
/// class is small enough. If the class is too big, return an infinite |
| 499 |
/// sequence. |
| 500 |
fn extract_class_unicode(&self, cls: &hir::ClassUnicode) -> Seq { |
| 501 |
if self.class_over_limit_unicode(cls) { |
| 502 |
return Seq::infinite(); |
| 503 |
} |
| 504 |
let mut seq = Seq::empty(); |
| 505 |
for r in cls.iter() { |
| 506 |
for ch in r.start()..=r.end() { |
| 507 |
seq.push(Literal::from(ch)); |
| 508 |
} |
| 509 |
} |
| 510 |
self.enforce_literal_len(&mut seq); |
| 511 |
seq |
| 512 |
} |
| 513 |
|
| 514 |
/// Convert the given byte class into a sequence of literals if the class |
| 515 |
/// is small enough. If the class is too big, return an infinite sequence. |
| 516 |
fn extract_class_bytes(&self, cls: &hir::ClassBytes) -> Seq { |
| 517 |
if self.class_over_limit_bytes(cls) { |
| 518 |
return Seq::infinite(); |
| 519 |
} |
| 520 |
let mut seq = Seq::empty(); |
| 521 |
for r in cls.iter() { |
| 522 |
for b in r.start()..=r.end() { |
| 523 |
seq.push(Literal::from(b)); |
| 524 |
} |
| 525 |
} |
| 526 |
self.enforce_literal_len(&mut seq); |
| 527 |
seq |
| 528 |
} |
| 529 |
|
| 530 |
/// Returns true if the given Unicode class exceeds the configured limits |
| 531 |
/// on this extractor. |
| 532 |
fn class_over_limit_unicode(&self, cls: &hir::ClassUnicode) -> bool { |
| 533 |
let mut count = 0; |
| 534 |
for r in cls.iter() { |
| 535 |
if count > self.limit_class { |
| 536 |
return true; |
| 537 |
} |
| 538 |
count += r.len(); |
| 539 |
} |
| 540 |
count > self.limit_class |
| 541 |
} |
| 542 |
|
| 543 |
/// Returns true if the given byte class exceeds the configured limits on |
| 544 |
/// this extractor. |
| 545 |
fn class_over_limit_bytes(&self, cls: &hir::ClassBytes) -> bool { |
| 546 |
let mut count = 0; |
| 547 |
for r in cls.iter() { |
| 548 |
if count > self.limit_class { |
| 549 |
return true; |
| 550 |
} |
| 551 |
count += r.len(); |
| 552 |
} |
| 553 |
count > self.limit_class |
| 554 |
} |
| 555 |
|
| 556 |
/// Compute the cross product of the two sequences if the result would be |
| 557 |
/// within configured limits. Otherwise, make `seq2` infinite and cross the |
| 558 |
/// infinite sequence with `seq1`. |
| 559 |
fn cross(&self, mut seq1: Seq, seq2: &mut Seq) -> Seq { |
| 560 |
if seq1.max_cross_len(seq2).map_or(false, |len| len > self.limit_total) |
| 561 |
{ |
| 562 |
seq2.make_infinite(); |
| 563 |
} |
| 564 |
if let ExtractKind::Suffix = self.kind { |
| 565 |
seq1.cross_reverse(seq2); |
| 566 |
} else { |
| 567 |
seq1.cross_forward(seq2); |
| 568 |
} |
| 569 |
assert!(seq1.len().map_or(true, |x| x <= self.limit_total)); |
| 570 |
self.enforce_literal_len(&mut seq1); |
| 571 |
seq1 |
| 572 |
} |
| 573 |
|
| 574 |
/// Union the two sequences if the result would be within configured |
| 575 |
/// limits. Otherwise, make `seq2` infinite and union the infinite sequence |
| 576 |
/// with `seq1`. |
| 577 |
fn union(&self, mut seq1: Seq, seq2: &mut Seq) -> Seq { |
| 578 |
if seq1.max_union_len(seq2).map_or(false, |len| len > self.limit_total) |
| 579 |
{ |
| 580 |
// We try to trim our literal sequences to see if we can make |
| 581 |
// room for more literals. The idea is that we'd rather trim down |
| 582 |
// literals already in our sequence if it means we can add a few |
| 583 |
// more and retain a finite sequence. Otherwise, we'll union with |
| 584 |
// an infinite sequence and that infects everything and effectively |
| 585 |
// stops literal extraction in its tracks. |
| 586 |
// |
| 587 |
// We do we keep 4 bytes here? Well, it's a bit of an abstraction |
| 588 |
// leakage. Downstream, the literals may wind up getting fed to |
| 589 |
// the Teddy algorithm, which supports searching literals up to |
| 590 |
// length 4. So that's why we pick that number here. Arguably this |
| 591 |
// should be a tuneable parameter, but it seems a little tricky to |
| 592 |
// describe. And I'm still unsure if this is the right way to go |
| 593 |
// about culling literal sequences. |
| 594 |
match self.kind { |
| 595 |
ExtractKind::Prefix => { |
| 596 |
seq1.keep_first_bytes(4); |
| 597 |
seq2.keep_first_bytes(4); |
| 598 |
} |
| 599 |
ExtractKind::Suffix => { |
| 600 |
seq1.keep_last_bytes(4); |
| 601 |
seq2.keep_last_bytes(4); |
| 602 |
} |
| 603 |
} |
| 604 |
seq1.dedup(); |
| 605 |
seq2.dedup(); |
| 606 |
if seq1 |
| 607 |
.max_union_len(seq2) |
| 608 |
.map_or(false, |len| len > self.limit_total) |
| 609 |
{ |
| 610 |
seq2.make_infinite(); |
| 611 |
} |
| 612 |
} |
| 613 |
seq1.union(seq2); |
| 614 |
assert!(seq1.len().map_or(true, |x| x <= self.limit_total)); |
| 615 |
seq1 |
| 616 |
} |
| 617 |
|
| 618 |
/// Applies the literal length limit to the given sequence. If none of the |
| 619 |
/// literals in the sequence exceed the limit, then this is a no-op. |
| 620 |
fn enforce_literal_len(&self, seq: &mut Seq) { |
| 621 |
let len = self.limit_literal_len; |
| 622 |
match self.kind { |
| 623 |
ExtractKind::Prefix => seq.keep_first_bytes(len), |
| 624 |
ExtractKind::Suffix => seq.keep_last_bytes(len), |
| 625 |
} |
| 626 |
} |
| 627 |
} |
| 628 |
|
| 629 |
impl Default for Extractor { |
| 630 |
fn default() -> Extractor { |
| 631 |
Extractor::new() |
| 632 |
} |
| 633 |
} |
| 634 |
|
| 635 |
/// The kind of literals to extract from an [`Hir`] expression. |
| 636 |
/// |
| 637 |
/// The default extraction kind is `Prefix`. |
| 638 |
#[non_exhaustive] |
| 639 |
#[derive(Clone, Debug)] |
| 640 |
pub enum ExtractKind { |
| 641 |
/// Extracts only prefix literals from a regex. |
| 642 |
Prefix, |
| 643 |
/// Extracts only suffix literals from a regex. |
| 644 |
/// |
| 645 |
/// Note that the sequence returned by suffix literals currently may |
| 646 |
/// not correctly represent leftmost-first or "preference" order match |
| 647 |
/// semantics. |
| 648 |
Suffix, |
| 649 |
} |
| 650 |
|
| 651 |
impl ExtractKind { |
| 652 |
/// Returns true if this kind is the `Prefix` variant. |
| 653 |
pub fn is_prefix(&self) -> bool { |
| 654 |
matches!(*self, ExtractKind::Prefix) |
| 655 |
} |
| 656 |
|
| 657 |
/// Returns true if this kind is the `Suffix` variant. |
| 658 |
pub fn is_suffix(&self) -> bool { |
| 659 |
matches!(*self, ExtractKind::Suffix) |
| 660 |
} |
| 661 |
} |
| 662 |
|
| 663 |
impl Default for ExtractKind { |
| 664 |
fn default() -> ExtractKind { |
| 665 |
ExtractKind::Prefix |
| 666 |
} |
| 667 |
} |
| 668 |
|
| 669 |
/// A sequence of literals. |
| 670 |
/// |
| 671 |
/// A `Seq` is very much like a set in that it represents a union of its |
| 672 |
/// members. That is, it corresponds to a set of literals where at least one |
| 673 |
/// must match in order for a particular [`Hir`] expression to match. (Whether |
| 674 |
/// this corresponds to the entire `Hir` expression, a prefix of it or a suffix |
| 675 |
/// of it depends on how the `Seq` was extracted from the `Hir`.) |
| 676 |
/// |
| 677 |
/// It is also unlike a set in that multiple identical literals may appear, |
| 678 |
/// and that the order of the literals in the `Seq` matters. For example, if |
| 679 |
/// the sequence is `[sam, samwise]` and leftmost-first matching is used, then |
| 680 |
/// `samwise` can never match and the sequence is equivalent to `[sam]`. |
| 681 |
/// |
| 682 |
/// # States of a sequence |
| 683 |
/// |
| 684 |
/// A `Seq` has a few different logical states to consider: |
| 685 |
/// |
| 686 |
/// * The sequence can represent "any" literal. When this happens, the set does |
| 687 |
/// not have a finite size. The purpose of this state is to inhibit callers |
| 688 |
/// from making assumptions about what literals are required in order to match |
| 689 |
/// a particular [`Hir`] expression. Generally speaking, when a set is in this |
| 690 |
/// state, literal optimizations are inhibited. A good example of a regex that |
| 691 |
/// will cause this sort of set to appear is `[A-Za-z]`. The character class |
| 692 |
/// is just too big (and also too narrow) to be usefully expanded into 52 |
| 693 |
/// different literals. (Note that the decision for when a seq should become |
| 694 |
/// infinite is determined by the caller. A seq itself has no hard-coded |
| 695 |
/// limits.) |
| 696 |
/// * The sequence can be empty, in which case, it is an affirmative statement |
| 697 |
/// that there are no literals that can match the corresponding `Hir`. |
| 698 |
/// Consequently, the `Hir` never matches any input. For example, `[a&&b]`. |
| 699 |
/// * The sequence can be non-empty, in which case, at least one of the |
| 700 |
/// literals must match in order for the corresponding `Hir` to match. |
| 701 |
/// |
| 702 |
/// # Example |
| 703 |
/// |
| 704 |
/// This example shows how literal sequences can be simplified by stripping |
| 705 |
/// suffixes and minimizing while maintaining preference order. |
| 706 |
/// |
| 707 |
/// ``` |
| 708 |
/// use regex_syntax::hir::literal::{Literal, Seq}; |
| 709 |
/// |
| 710 |
/// let mut seq = Seq::new(&[ |
| 711 |
/// "farm", |
| 712 |
/// "appliance", |
| 713 |
/// "faraway", |
| 714 |
/// "apple", |
| 715 |
/// "fare", |
| 716 |
/// "gap", |
| 717 |
/// "applicant", |
| 718 |
/// "applaud", |
| 719 |
/// ]); |
| 720 |
/// seq.keep_first_bytes(3); |
| 721 |
/// seq.minimize_by_preference(); |
| 722 |
/// // Notice that 'far' comes before 'app', which matches the order in the |
| 723 |
/// // original sequence. This guarantees that leftmost-first semantics are |
| 724 |
/// // not altered by simplifying the set. |
| 725 |
/// let expected = Seq::from_iter([ |
| 726 |
/// Literal::inexact("far"), |
| 727 |
/// Literal::inexact("app"), |
| 728 |
/// Literal::exact("gap"), |
| 729 |
/// ]); |
| 730 |
/// assert_eq!(expected, seq); |
| 731 |
/// ``` |
| 732 |
#[derive(Clone, Eq, PartialEq)] |
| 733 |
pub struct Seq { |
| 734 |
/// The members of this seq. |
| 735 |
/// |
| 736 |
/// When `None`, the seq represents all possible literals. That is, it |
| 737 |
/// prevents one from making assumptions about specific literals in the |
| 738 |
/// seq, and forces one to treat it as if any literal might be in the seq. |
| 739 |
/// |
| 740 |
/// Note that `Some(vec![])` is valid and corresponds to the empty seq of |
| 741 |
/// literals, i.e., a regex that can never match. For example, `[a&&b]`. |
| 742 |
/// It is distinct from `Some(vec![""])`, which corresponds to the seq |
| 743 |
/// containing an empty string, which matches at every position. |
| 744 |
literals: Option<Vec<Literal>>, |
| 745 |
} |
| 746 |
|
| 747 |
impl Seq { |
| 748 |
/// Returns an empty sequence. |
| 749 |
/// |
| 750 |
/// An empty sequence matches zero literals, and thus corresponds to a |
| 751 |
/// regex that itself can never match. |
| 752 |
#[inline] |
| 753 |
pub fn empty() -> Seq { |
| 754 |
Seq { literals: Some(vec![]) } |
| 755 |
} |
| 756 |
|
| 757 |
/// Returns a sequence of literals without a finite size and may contain |
| 758 |
/// any literal. |
| 759 |
/// |
| 760 |
/// A sequence without finite size does not reveal anything about the |
| 761 |
/// characteristics of the literals in its set. There are no fixed prefixes |
| 762 |
/// or suffixes, nor are lower or upper bounds on the length of the literals |
| 763 |
/// in the set known. |
| 764 |
/// |
| 765 |
/// This is useful to represent constructs in a regex that are "too big" |
| 766 |
/// to useful represent as a sequence of literals. For example, `[A-Za-z]`. |
| 767 |
/// When sequences get too big, they lose their discriminating nature and |
| 768 |
/// are more likely to produce false positives, which in turn makes them |
| 769 |
/// less likely to speed up searches. |
| 770 |
/// |
| 771 |
/// More pragmatically, for many regexes, enumerating all possible literals |
| 772 |
/// is itself not possible or might otherwise use too many resources. So |
| 773 |
/// constraining the size of sets during extraction is a practical trade |
| 774 |
/// off to make. |
| 775 |
#[inline] |
| 776 |
pub fn infinite() -> Seq { |
| 777 |
Seq { literals: None } |
| 778 |
} |
| 779 |
|
| 780 |
/// Returns a sequence containing a single literal. |
| 781 |
#[inline] |
| 782 |
pub fn singleton(lit: Literal) -> Seq { |
| 783 |
Seq { literals: Some(vec![lit]) } |
| 784 |
} |
| 785 |
|
| 786 |
/// Returns a sequence of exact literals from the given byte strings. |
| 787 |
#[inline] |
| 788 |
pub fn new<I, B>(it: I) -> Seq |
| 789 |
where |
| 790 |
I: IntoIterator<Item = B>, |
| 791 |
B: AsRef<[u8]>, |
| 792 |
{ |
| 793 |
it.into_iter().map(|b| Literal::exact(b.as_ref())).collect() |
| 794 |
} |
| 795 |
|
| 796 |
/// If this is a finite sequence, return its members as a slice of |
| 797 |
/// literals. |
| 798 |
/// |
| 799 |
/// The slice returned may be empty, in which case, there are no literals |
| 800 |
/// that can match this sequence. |
| 801 |
#[inline] |
| 802 |
pub fn literals(&self) -> Option<&[Literal]> { |
| 803 |
self.literals.as_deref() |
| 804 |
} |
| 805 |
|
| 806 |
/// Push a literal to the end of this sequence. |
| 807 |
/// |
| 808 |
/// If this sequence is not finite, then this is a no-op. |
| 809 |
/// |
| 810 |
/// Similarly, if the most recently added item of this sequence is |
| 811 |
/// equivalent to the literal given, then it is not added. This reflects |
| 812 |
/// a `Seq`'s "set like" behavior, and represents a practical trade off. |
| 813 |
/// Namely, there is never any need to have two adjacent and equivalent |
| 814 |
/// literals in the same sequence, _and_ it is easy to detect in some |
| 815 |
/// cases. |
| 816 |
#[inline] |
| 817 |
pub fn push(&mut self, lit: Literal) { |
| 818 |
let lits = match self.literals { |
| 819 |
None => return, |
| 820 |
Some(ref mut lits) => lits, |
| 821 |
}; |
| 822 |
if lits.last().map_or(false, |m| m == &lit) { |
| 823 |
return; |
| 824 |
} |
| 825 |
lits.push(lit); |
| 826 |
} |
| 827 |
|
| 828 |
/// Make all of the literals in this sequence inexact. |
| 829 |
/// |
| 830 |
/// This is a no-op if this sequence is not finite. |
| 831 |
#[inline] |
| 832 |
pub fn make_inexact(&mut self) { |
| 833 |
let lits = match self.literals { |
| 834 |
None => return, |
| 835 |
Some(ref mut lits) => lits, |
| 836 |
}; |
| 837 |
for lit in lits.iter_mut() { |
| 838 |
lit.make_inexact(); |
| 839 |
} |
| 840 |
} |
| 841 |
|
| 842 |
/// Converts this sequence to an infinite sequence. |
| 843 |
/// |
| 844 |
/// This is a no-op if the sequence is already infinite. |
| 845 |
#[inline] |
| 846 |
pub fn make_infinite(&mut self) { |
| 847 |
self.literals = None; |
| 848 |
} |
| 849 |
|
| 850 |
/// Modify this sequence to contain the cross product between it and the |
| 851 |
/// sequence given. |
| 852 |
/// |
| 853 |
/// The cross product only considers literals in this sequence that are |
| 854 |
/// exact. That is, inexact literals are not extended. |
| 855 |
/// |
| 856 |
/// The literals are always drained from `other`, even if none are used. |
| 857 |
/// This permits callers to reuse the sequence allocation elsewhere. |
| 858 |
/// |
| 859 |
/// If this sequence is infinite, then this is a no-op, regardless of what |
| 860 |
/// `other` contains (and in this case, the literals are still drained from |
| 861 |
/// `other`). If `other` is infinite and this sequence is finite, then this |
| 862 |
/// is a no-op, unless this sequence contains a zero-length literal. In |
| 863 |
/// which case, the infiniteness of `other` infects this sequence, and this |
| 864 |
/// sequence is itself made infinite. |
| 865 |
/// |
| 866 |
/// Like [`Seq::union`], this may attempt to deduplicate literals. See |
| 867 |
/// [`Seq::dedup`] for how deduplication deals with exact and inexact |
| 868 |
/// literals. |
| 869 |
/// |
| 870 |
/// # Example |
| 871 |
/// |
| 872 |
/// This example shows basic usage and how exact and inexact literals |
| 873 |
/// interact. |
| 874 |
/// |
| 875 |
/// ``` |
| 876 |
/// use regex_syntax::hir::literal::{Literal, Seq}; |
| 877 |
/// |
| 878 |
/// let mut seq1 = Seq::from_iter([ |
| 879 |
/// Literal::exact("foo"), |
| 880 |
/// Literal::inexact("bar"), |
| 881 |
/// ]); |
| 882 |
/// let mut seq2 = Seq::from_iter([ |
| 883 |
/// Literal::inexact("quux"), |
| 884 |
/// Literal::exact("baz"), |
| 885 |
/// ]); |
| 886 |
/// seq1.cross_forward(&mut seq2); |
| 887 |
/// |
| 888 |
/// // The literals are pulled out of seq2. |
| 889 |
/// assert_eq!(Some(0), seq2.len()); |
| 890 |
/// |
| 891 |
/// let expected = Seq::from_iter([ |
| 892 |
/// Literal::inexact("fooquux"), |
| 893 |
/// Literal::exact("foobaz"), |
| 894 |
/// Literal::inexact("bar"), |
| 895 |
/// ]); |
| 896 |
/// assert_eq!(expected, seq1); |
| 897 |
/// ``` |
| 898 |
/// |
| 899 |
/// This example shows the behavior of when `other` is an infinite |
| 900 |
/// sequence. |
| 901 |
/// |
| 902 |
/// ``` |
| 903 |
/// use regex_syntax::hir::literal::{Literal, Seq}; |
| 904 |
/// |
| 905 |
/// let mut seq1 = Seq::from_iter([ |
| 906 |
/// Literal::exact("foo"), |
| 907 |
/// Literal::inexact("bar"), |
| 908 |
/// ]); |
| 909 |
/// let mut seq2 = Seq::infinite(); |
| 910 |
/// seq1.cross_forward(&mut seq2); |
| 911 |
/// |
| 912 |
/// // When seq2 is infinite, cross product doesn't add anything, but |
| 913 |
/// // ensures all members of seq1 are inexact. |
| 914 |
/// let expected = Seq::from_iter([ |
| 915 |
/// Literal::inexact("foo"), |
| 916 |
/// Literal::inexact("bar"), |
| 917 |
/// ]); |
| 918 |
/// assert_eq!(expected, seq1); |
| 919 |
/// ``` |
| 920 |
/// |
| 921 |
/// This example is like the one above, but shows what happens when this |
| 922 |
/// sequence contains an empty string. In this case, an infinite `other` |
| 923 |
/// sequence infects this sequence (because the empty string means that |
| 924 |
/// there are no finite prefixes): |
| 925 |
/// |
| 926 |
/// ``` |
| 927 |
/// use regex_syntax::hir::literal::{Literal, Seq}; |
| 928 |
/// |
| 929 |
/// let mut seq1 = Seq::from_iter([ |
| 930 |
/// Literal::exact("foo"), |
| 931 |
/// Literal::exact(""), // inexact provokes same behavior |
| 932 |
/// Literal::inexact("bar"), |
| 933 |
/// ]); |
| 934 |
/// let mut seq2 = Seq::infinite(); |
| 935 |
/// seq1.cross_forward(&mut seq2); |
| 936 |
/// |
| 937 |
/// // seq1 is now infinite! |
| 938 |
/// assert!(!seq1.is_finite()); |
| 939 |
/// ``` |
| 940 |
/// |
| 941 |
/// This example shows the behavior of this sequence is infinite. |
| 942 |
/// |
| 943 |
/// ``` |
| 944 |
/// use regex_syntax::hir::literal::{Literal, Seq}; |
| 945 |
/// |
| 946 |
/// let mut seq1 = Seq::infinite(); |
| 947 |
/// let mut seq2 = Seq::from_iter([ |
| 948 |
/// Literal::exact("foo"), |
| 949 |
/// Literal::inexact("bar"), |
| 950 |
/// ]); |
| 951 |
/// seq1.cross_forward(&mut seq2); |
| 952 |
/// |
| 953 |
/// // seq1 remains unchanged. |
| 954 |
/// assert!(!seq1.is_finite()); |
| 955 |
/// // Even though the literals in seq2 weren't used, it was still drained. |
| 956 |
/// assert_eq!(Some(0), seq2.len()); |
| 957 |
/// ``` |
| 958 |
#[inline] |
| 959 |
pub fn cross_forward(&mut self, other: &mut Seq) { |
| 960 |
let (lits1, lits2) = match self.cross_preamble(other) { |
| 961 |
None => return, |
| 962 |
Some((lits1, lits2)) => (lits1, lits2), |
| 963 |
}; |
| 964 |
let newcap = lits1.len().saturating_mul(lits2.len()); |
| 965 |
for selflit in mem::replace(lits1, Vec::with_capacity(newcap)) { |
| 966 |
if !selflit.is_exact() { |
| 967 |
lits1.push(selflit); |
| 968 |
continue; |
| 969 |
} |
| 970 |
for otherlit in lits2.iter() { |
| 971 |
let mut newlit = Literal::exact(Vec::with_capacity( |
| 972 |
selflit.len() + otherlit.len(), |
| 973 |
)); |
| 974 |
newlit.extend(&selflit); |
| 975 |
newlit.extend(&otherlit); |
| 976 |
if !otherlit.is_exact() { |
| 977 |
newlit.make_inexact(); |
| 978 |
} |
| 979 |
lits1.push(newlit); |
| 980 |
} |
| 981 |
} |
| 982 |
lits2.drain(..); |
| 983 |
self.dedup(); |
| 984 |
} |
| 985 |
|
| 986 |
/// Modify this sequence to contain the cross product between it and |
| 987 |
/// the sequence given, where the sequences are treated as suffixes |
| 988 |
/// instead of prefixes. Namely, the sequence `other` is *prepended* |
| 989 |
/// to `self` (as opposed to `other` being *appended* to `self` in |
| 990 |
/// [`Seq::cross_forward`]). |
| 991 |
/// |
| 992 |
/// The cross product only considers literals in this sequence that are |
| 993 |
/// exact. That is, inexact literals are not extended. |
| 994 |
/// |
| 995 |
/// The literals are always drained from `other`, even if none are used. |
| 996 |
/// This permits callers to reuse the sequence allocation elsewhere. |
| 997 |
/// |
| 998 |
/// If this sequence is infinite, then this is a no-op, regardless of what |
| 999 |
/// `other` contains (and in this case, the literals are still drained from |
| 1000 |
/// `other`). If `other` is infinite and this sequence is finite, then this |
| 1001 |
/// is a no-op, unless this sequence contains a zero-length literal. In |
| 1002 |
/// which case, the infiniteness of `other` infects this sequence, and this |
| 1003 |
/// sequence is itself made infinite. |
| 1004 |
/// |
| 1005 |
/// Like [`Seq::union`], this may attempt to deduplicate literals. See |
| 1006 |
/// [`Seq::dedup`] for how deduplication deals with exact and inexact |
| 1007 |
/// literals. |
| 1008 |
/// |
| 1009 |
/// # Example |
| 1010 |
/// |
| 1011 |
/// This example shows basic usage and how exact and inexact literals |
| 1012 |
/// interact. |
| 1013 |
/// |
| 1014 |
/// ``` |
| 1015 |
/// use regex_syntax::hir::literal::{Literal, Seq}; |
| 1016 |
/// |
| 1017 |
/// let mut seq1 = Seq::from_iter([ |
| 1018 |
/// Literal::exact("foo"), |
| 1019 |
/// Literal::inexact("bar"), |
| 1020 |
/// ]); |
| 1021 |
/// let mut seq2 = Seq::from_iter([ |
| 1022 |
/// Literal::inexact("quux"), |
| 1023 |
/// Literal::exact("baz"), |
| 1024 |
/// ]); |
| 1025 |
/// seq1.cross_reverse(&mut seq2); |
| 1026 |
/// |
| 1027 |
/// // The literals are pulled out of seq2. |
| 1028 |
/// assert_eq!(Some(0), seq2.len()); |
| 1029 |
/// |
| 1030 |
/// let expected = Seq::from_iter([ |
| 1031 |
/// Literal::inexact("quuxfoo"), |
| 1032 |
/// Literal::inexact("bar"), |
| 1033 |
/// Literal::exact("bazfoo"), |
| 1034 |
/// ]); |
| 1035 |
/// assert_eq!(expected, seq1); |
| 1036 |
/// ``` |
| 1037 |
/// |
| 1038 |
/// This example shows the behavior of when `other` is an infinite |
| 1039 |
/// sequence. |
| 1040 |
/// |
| 1041 |
/// ``` |
| 1042 |
/// use regex_syntax::hir::literal::{Literal, Seq}; |
| 1043 |
/// |
| 1044 |
/// let mut seq1 = Seq::from_iter([ |
| 1045 |
/// Literal::exact("foo"), |
| 1046 |
/// Literal::inexact("bar"), |
| 1047 |
/// ]); |
| 1048 |
/// let mut seq2 = Seq::infinite(); |
| 1049 |
/// seq1.cross_reverse(&mut seq2); |
| 1050 |
/// |
| 1051 |
/// // When seq2 is infinite, cross product doesn't add anything, but |
| 1052 |
/// // ensures all members of seq1 are inexact. |
| 1053 |
/// let expected = Seq::from_iter([ |
| 1054 |
/// Literal::inexact("foo"), |
| 1055 |
/// Literal::inexact("bar"), |
| 1056 |
/// ]); |
| 1057 |
/// assert_eq!(expected, seq1); |
| 1058 |
/// ``` |
| 1059 |
/// |
| 1060 |
/// This example is like the one above, but shows what happens when this |
| 1061 |
/// sequence contains an empty string. In this case, an infinite `other` |
| 1062 |
/// sequence infects this sequence (because the empty string means that |
| 1063 |
/// there are no finite suffixes): |
| 1064 |
/// |
| 1065 |
/// ``` |
| 1066 |
/// use regex_syntax::hir::literal::{Literal, Seq}; |
| 1067 |
/// |
| 1068 |
/// let mut seq1 = Seq::from_iter([ |
| 1069 |
/// Literal::exact("foo"), |
| 1070 |
/// Literal::exact(""), // inexact provokes same behavior |
| 1071 |
/// Literal::inexact("bar"), |
| 1072 |
/// ]); |
| 1073 |
/// let mut seq2 = Seq::infinite(); |
| 1074 |
/// seq1.cross_reverse(&mut seq2); |
| 1075 |
/// |
| 1076 |
/// // seq1 is now infinite! |
| 1077 |
/// assert!(!seq1.is_finite()); |
| 1078 |
/// ``` |
| 1079 |
/// |
| 1080 |
/// This example shows the behavior when this sequence is infinite. |
| 1081 |
/// |
| 1082 |
/// ``` |
| 1083 |
/// use regex_syntax::hir::literal::{Literal, Seq}; |
| 1084 |
/// |
| 1085 |
/// let mut seq1 = Seq::infinite(); |
| 1086 |
/// let mut seq2 = Seq::from_iter([ |
| 1087 |
/// Literal::exact("foo"), |
| 1088 |
/// Literal::inexact("bar"), |
| 1089 |
/// ]); |
| 1090 |
/// seq1.cross_reverse(&mut seq2); |
| 1091 |
/// |
| 1092 |
/// // seq1 remains unchanged. |
| 1093 |
/// assert!(!seq1.is_finite()); |
| 1094 |
/// // Even though the literals in seq2 weren't used, it was still drained. |
| 1095 |
/// assert_eq!(Some(0), seq2.len()); |
| 1096 |
/// ``` |
| 1097 |
#[inline] |
| 1098 |
pub fn cross_reverse(&mut self, other: &mut Seq) { |
| 1099 |
let (lits1, lits2) = match self.cross_preamble(other) { |
| 1100 |
None => return, |
| 1101 |
Some((lits1, lits2)) => (lits1, lits2), |
| 1102 |
}; |
| 1103 |
// We basically proceed as we do in 'cross_forward' at this point, |
| 1104 |
// except that the outer loop is now 'other' and the inner loop is now |
| 1105 |
// 'self'. That's because 'self' corresponds to suffixes and 'other' |
| 1106 |
// corresponds to the sequence we want to *prepend* to the suffixes. |
| 1107 |
let newcap = lits1.len().saturating_mul(lits2.len()); |
| 1108 |
let selflits = mem::replace(lits1, Vec::with_capacity(newcap)); |
| 1109 |
for (i, otherlit) in lits2.drain(..).enumerate() { |
| 1110 |
for selflit in selflits.iter() { |
| 1111 |
if !selflit.is_exact() { |
| 1112 |
// If the suffix isn't exact, then we can't prepend |
| 1113 |
// anything to it. However, we still want to keep it. But |
| 1114 |
// we only want to keep one of them, to avoid duplication. |
| 1115 |
// (The duplication is okay from a correctness perspective, |
| 1116 |
// but wasteful.) |
| 1117 |
if i == 0 { |
| 1118 |
lits1.push(selflit.clone()); |
| 1119 |
} |
| 1120 |
continue; |
| 1121 |
} |
| 1122 |
let mut newlit = Literal::exact(Vec::with_capacity( |
| 1123 |
otherlit.len() + selflit.len(), |
| 1124 |
)); |
| 1125 |
newlit.extend(&otherlit); |
| 1126 |
newlit.extend(&selflit); |
| 1127 |
if !otherlit.is_exact() { |
| 1128 |
newlit.make_inexact(); |
| 1129 |
} |
| 1130 |
lits1.push(newlit); |
| 1131 |
} |
| 1132 |
} |
| 1133 |
self.dedup(); |
| 1134 |
} |
| 1135 |
|
| 1136 |
/// A helper function the corresponds to the subtle preamble for both |
| 1137 |
/// `cross_forward` and `cross_reverse`. In effect, it handles the cases |
| 1138 |
/// of infinite sequences for both `self` and `other`, as well as ensuring |
| 1139 |
/// that literals from `other` are drained even if they aren't used. |
| 1140 |
fn cross_preamble<'a>( |
| 1141 |
&'a mut self, |
| 1142 |
other: &'a mut Seq, |
| 1143 |
) -> Option<(&'a mut Vec<Literal>, &'a mut Vec<Literal>)> { |
| 1144 |
let lits2 = match other.literals { |
| 1145 |
None => { |
| 1146 |
// If our current seq contains the empty string and the seq |
| 1147 |
// we're adding matches any literal, then it follows that the |
| 1148 |
// current seq must now also match any literal. |
| 1149 |
// |
| 1150 |
// Otherwise, we just have to make sure everything in this |
| 1151 |
// sequence is inexact. |
| 1152 |
if self.min_literal_len() == Some(0) { |
| 1153 |
*self = Seq::infinite(); |
| 1154 |
} else { |
| 1155 |
self.make_inexact(); |
| 1156 |
} |
| 1157 |
return None; |
| 1158 |
} |
| 1159 |
Some(ref mut lits) => lits, |
| 1160 |
}; |
| 1161 |
let lits1 = match self.literals { |
| 1162 |
None => { |
| 1163 |
// If we aren't going to make it to the end of this routine |
| 1164 |
// where lits2 is drained, then we need to do it now. |
| 1165 |
lits2.drain(..); |
| 1166 |
return None; |
| 1167 |
} |
| 1168 |
Some(ref mut lits) => lits, |
| 1169 |
}; |
| 1170 |
Some((lits1, lits2)) |
| 1171 |
} |
| 1172 |
|
| 1173 |
/// Unions the `other` sequence into this one. |
| 1174 |
/// |
| 1175 |
/// The literals are always drained out of the given `other` sequence, |
| 1176 |
/// even if they are being unioned into an infinite sequence. This permits |
| 1177 |
/// the caller to reuse the `other` sequence in another context. |
| 1178 |
/// |
| 1179 |
/// Some literal deduping may be performed. If any deduping happens, |
| 1180 |
/// any leftmost-first or "preference" order match semantics will be |
| 1181 |
/// preserved. |
| 1182 |
/// |
| 1183 |
/// # Example |
| 1184 |
/// |
| 1185 |
/// This example shows basic usage. |
| 1186 |
/// |
| 1187 |
/// ``` |
| 1188 |
/// use regex_syntax::hir::literal::Seq; |
| 1189 |
/// |
| 1190 |
/// let mut seq1 = Seq::new(&["foo", "bar"]); |
| 1191 |
/// let mut seq2 = Seq::new(&["bar", "quux", "foo"]); |
| 1192 |
/// seq1.union(&mut seq2); |
| 1193 |
/// |
| 1194 |
/// // The literals are pulled out of seq2. |
| 1195 |
/// assert_eq!(Some(0), seq2.len()); |
| 1196 |
/// |
| 1197 |
/// // Adjacent literals are deduped, but non-adjacent literals may not be. |
| 1198 |
/// assert_eq!(Seq::new(&["foo", "bar", "quux", "foo"]), seq1); |
| 1199 |
/// ``` |
| 1200 |
/// |
| 1201 |
/// This example shows that literals are drained from `other` even when |
| 1202 |
/// they aren't necessarily used. |
| 1203 |
/// |
| 1204 |
/// ``` |
| 1205 |
/// use regex_syntax::hir::literal::Seq; |
| 1206 |
/// |
| 1207 |
/// let mut seq1 = Seq::infinite(); |
| 1208 |
/// // Infinite sequences have no finite length. |
| 1209 |
/// assert_eq!(None, seq1.len()); |
| 1210 |
/// |
| 1211 |
/// let mut seq2 = Seq::new(&["bar", "quux", "foo"]); |
| 1212 |
/// seq1.union(&mut seq2); |
| 1213 |
/// |
| 1214 |
/// // seq1 is still infinite and seq2 has been drained. |
| 1215 |
/// assert_eq!(None, seq1.len()); |
| 1216 |
/// assert_eq!(Some(0), seq2.len()); |
| 1217 |
/// ``` |
| 1218 |
#[inline] |
| 1219 |
pub fn union(&mut self, other: &mut Seq) { |
| 1220 |
let lits2 = match other.literals { |
| 1221 |
None => { |
| 1222 |
// Unioning with an infinite sequence always results in an |
| 1223 |
// infinite sequence. |
| 1224 |
self.make_infinite(); |
| 1225 |
return; |
| 1226 |
} |
| 1227 |
Some(ref mut lits) => lits.drain(..), |
| 1228 |
}; |
| 1229 |
let lits1 = match self.literals { |
| 1230 |
None => return, |
| 1231 |
Some(ref mut lits) => lits, |
| 1232 |
}; |
| 1233 |
lits1.extend(lits2); |
| 1234 |
self.dedup(); |
| 1235 |
} |
| 1236 |
|
| 1237 |
/// Unions the `other` sequence into this one by splice the `other` |
| 1238 |
/// sequence at the position of the first zero-length literal. |
| 1239 |
/// |
| 1240 |
/// This is useful for preserving preference order semantics when combining |
| 1241 |
/// two literal sequences. For example, in the regex `(a||f)+foo`, the |
| 1242 |
/// correct preference order prefix sequence is `[a, foo, f]`. |
| 1243 |
/// |
| 1244 |
/// The literals are always drained out of the given `other` sequence, |
| 1245 |
/// even if they are being unioned into an infinite sequence. This permits |
| 1246 |
/// the caller to reuse the `other` sequence in another context. Note that |
| 1247 |
/// the literals are drained even if no union is performed as well, i.e., |
| 1248 |
/// when this sequence does not contain a zero-length literal. |
| 1249 |
/// |
| 1250 |
/// Some literal deduping may be performed. If any deduping happens, |
| 1251 |
/// any leftmost-first or "preference" order match semantics will be |
| 1252 |
/// preserved. |
| 1253 |
/// |
| 1254 |
/// # Example |
| 1255 |
/// |
| 1256 |
/// This example shows basic usage. |
| 1257 |
/// |
| 1258 |
/// ``` |
| 1259 |
/// use regex_syntax::hir::literal::Seq; |
| 1260 |
/// |
| 1261 |
/// let mut seq1 = Seq::new(&["a", "", "f", ""]); |
| 1262 |
/// let mut seq2 = Seq::new(&["foo"]); |
| 1263 |
/// seq1.union_into_empty(&mut seq2); |
| 1264 |
/// |
| 1265 |
/// // The literals are pulled out of seq2. |
| 1266 |
/// assert_eq!(Some(0), seq2.len()); |
| 1267 |
/// // 'foo' gets spliced into seq1 where the first empty string occurs. |
| 1268 |
/// assert_eq!(Seq::new(&["a", "foo", "f"]), seq1); |
| 1269 |
/// ``` |
| 1270 |
/// |
| 1271 |
/// This example shows that literals are drained from `other` even when |
| 1272 |
/// they aren't necessarily used. |
| 1273 |
/// |
| 1274 |
/// ``` |
| 1275 |
/// use regex_syntax::hir::literal::Seq; |
| 1276 |
/// |
| 1277 |
/// let mut seq1 = Seq::new(&["foo", "bar"]); |
| 1278 |
/// let mut seq2 = Seq::new(&["bar", "quux", "foo"]); |
| 1279 |
/// seq1.union_into_empty(&mut seq2); |
| 1280 |
/// |
| 1281 |
/// // seq1 has no zero length literals, so no splicing happens. |
| 1282 |
/// assert_eq!(Seq::new(&["foo", "bar"]), seq1); |
| 1283 |
/// // Even though no splicing happens, seq2 is still drained. |
| 1284 |
/// assert_eq!(Some(0), seq2.len()); |
| 1285 |
/// ``` |
| 1286 |
#[inline] |
| 1287 |
pub fn union_into_empty(&mut self, other: &mut Seq) { |
| 1288 |
let lits2 = other.literals.as_mut().map(|lits| lits.drain(..)); |
| 1289 |
let lits1 = match self.literals { |
| 1290 |
None => return, |
| 1291 |
Some(ref mut lits) => lits, |
| 1292 |
}; |
| 1293 |
let first_empty = match lits1.iter().position(|m| m.is_empty()) { |
| 1294 |
None => return, |
| 1295 |
Some(i) => i, |
| 1296 |
}; |
| 1297 |
let lits2 = match lits2 { |
| 1298 |
None => { |
| 1299 |
// Note that we are only here if we've found an empty literal, |
| 1300 |
// which implies that an infinite sequence infects this seq and |
| 1301 |
// also turns it into an infinite sequence. |
| 1302 |
self.literals = None; |
| 1303 |
return; |
| 1304 |
} |
| 1305 |
Some(lits) => lits, |
| 1306 |
}; |
| 1307 |
// Clearing out the empties needs to come before the splice because |
| 1308 |
// the splice might add more empties that we don't want to get rid |
| 1309 |
// of. Since we're splicing into the position of the first empty, the |
| 1310 |
// 'first_empty' position computed above is still correct. |
| 1311 |
lits1.retain(|m| !m.is_empty()); |
| 1312 |
lits1.splice(first_empty..first_empty, lits2); |
| 1313 |
self.dedup(); |
| 1314 |
} |
| 1315 |
|
| 1316 |
/// Deduplicate adjacent equivalent literals in this sequence. |
| 1317 |
/// |
| 1318 |
/// If adjacent literals are equivalent strings but one is exact and the |
| 1319 |
/// other inexact, the inexact literal is kept and the exact one is |
| 1320 |
/// removed. |
| 1321 |
/// |
| 1322 |
/// Deduping an infinite sequence is a no-op. |
| 1323 |
/// |
| 1324 |
/// # Example |
| 1325 |
/// |
| 1326 |
/// This example shows how literals that are duplicate byte strings but |
| 1327 |
/// are not equivalent with respect to exactness are resolved. |
| 1328 |
/// |
| 1329 |
/// ``` |
| 1330 |
/// use regex_syntax::hir::literal::{Literal, Seq}; |
| 1331 |
/// |
| 1332 |
/// let mut seq = Seq::from_iter([ |
| 1333 |
/// Literal::exact("foo"), |
| 1334 |
/// Literal::inexact("foo"), |
| 1335 |
/// ]); |
| 1336 |
/// seq.dedup(); |
| 1337 |
/// |
| 1338 |
/// assert_eq!(Seq::from_iter([Literal::inexact("foo")]), seq); |
| 1339 |
/// ``` |
| 1340 |
#[inline] |
| 1341 |
pub fn dedup(&mut self) { |
| 1342 |
if let Some(ref mut lits) = self.literals { |
| 1343 |
lits.dedup_by(|lit1, lit2| { |
| 1344 |
if lit1.as_bytes() != lit2.as_bytes() { |
| 1345 |
return false; |
| 1346 |
} |
| 1347 |
if lit1.is_exact() != lit2.is_exact() { |
| 1348 |
lit1.make_inexact(); |
| 1349 |
lit2.make_inexact(); |
| 1350 |
} |
| 1351 |
true |
| 1352 |
}); |
| 1353 |
} |
| 1354 |
} |
| 1355 |
|
| 1356 |
/// Sorts this sequence of literals lexicographically. |
| 1357 |
/// |
| 1358 |
/// Note that if, before sorting, if a literal that is a prefix of another |
| 1359 |
/// literal appears after it, then after sorting, the sequence will not |
| 1360 |
/// represent the same preference order match semantics. For example, |
| 1361 |
/// sorting the sequence `[samwise, sam]` yields the sequence `[sam, |
| 1362 |
/// samwise]`. Under preference order semantics, the latter sequence will |
| 1363 |
/// never match `samwise` where as the first sequence can. |
| 1364 |
/// |
| 1365 |
/// # Example |
| 1366 |
/// |
| 1367 |
/// This example shows basic usage. |
| 1368 |
/// |
| 1369 |
/// ``` |
| 1370 |
/// use regex_syntax::hir::literal::Seq; |
| 1371 |
/// |
| 1372 |
/// let mut seq = Seq::new(&["foo", "quux", "bar"]); |
| 1373 |
/// seq.sort(); |
| 1374 |
/// |
| 1375 |
/// assert_eq!(Seq::new(&["bar", "foo", "quux"]), seq); |
| 1376 |
/// ``` |
| 1377 |
#[inline] |
| 1378 |
pub fn sort(&mut self) { |
| 1379 |
if let Some(ref mut lits) = self.literals { |
| 1380 |
lits.sort(); |
| 1381 |
} |
| 1382 |
} |
| 1383 |
|
| 1384 |
/// Reverses all of the literals in this sequence. |
| 1385 |
/// |
| 1386 |
/// The order of the sequence itself is preserved. |
| 1387 |
/// |
| 1388 |
/// # Example |
| 1389 |
/// |
| 1390 |
/// This example shows basic usage. |
| 1391 |
/// |
| 1392 |
/// ``` |
| 1393 |
/// use regex_syntax::hir::literal::Seq; |
| 1394 |
/// |
| 1395 |
/// let mut seq = Seq::new(&["oof", "rab"]); |
| 1396 |
/// seq.reverse_literals(); |
| 1397 |
/// assert_eq!(Seq::new(&["foo", "bar"]), seq); |
| 1398 |
/// ``` |
| 1399 |
#[inline] |
| 1400 |
pub fn reverse_literals(&mut self) { |
| 1401 |
if let Some(ref mut lits) = self.literals { |
| 1402 |
for lit in lits.iter_mut() { |
| 1403 |
lit.reverse(); |
| 1404 |
} |
| 1405 |
} |
| 1406 |
} |
| 1407 |
|
| 1408 |
/// Shrinks this seq to its minimal size while respecting the preference |
| 1409 |
/// order of its literals. |
| 1410 |
/// |
| 1411 |
/// While this routine will remove duplicate literals from this seq, it |
| 1412 |
/// will also remove literals that can never match in a leftmost-first or |
| 1413 |
/// "preference order" search. Similar to [`Seq::dedup`], if a literal is |
| 1414 |
/// deduped, then the one that remains is made inexact. |
| 1415 |
/// |
| 1416 |
/// This is a no-op on seqs that are empty or not finite. |
| 1417 |
/// |
| 1418 |
/// # Example |
| 1419 |
/// |
| 1420 |
/// This example shows the difference between `{sam, samwise}` and |
| 1421 |
/// `{samwise, sam}`. |
| 1422 |
/// |
| 1423 |
/// ``` |
| 1424 |
/// use regex_syntax::hir::literal::{Literal, Seq}; |
| 1425 |
/// |
| 1426 |
/// // If 'sam' comes before 'samwise' and a preference order search is |
| 1427 |
/// // executed, then 'samwise' can never match. |
| 1428 |
/// let mut seq = Seq::new(&["sam", "samwise"]); |
| 1429 |
/// seq.minimize_by_preference(); |
| 1430 |
/// assert_eq!(Seq::from_iter([Literal::inexact("sam")]), seq); |
| 1431 |
/// |
| 1432 |
/// // But if they are reversed, then it's possible for 'samwise' to match |
| 1433 |
/// // since it is given higher preference. |
| 1434 |
/// let mut seq = Seq::new(&["samwise", "sam"]); |
| 1435 |
/// seq.minimize_by_preference(); |
| 1436 |
/// assert_eq!(Seq::new(&["samwise", "sam"]), seq); |
| 1437 |
/// ``` |
| 1438 |
/// |
| 1439 |
/// This example shows that if an empty string is in this seq, then |
| 1440 |
/// anything that comes after it can never match. |
| 1441 |
/// |
| 1442 |
/// ``` |
| 1443 |
/// use regex_syntax::hir::literal::{Literal, Seq}; |
| 1444 |
/// |
| 1445 |
/// // An empty string is a prefix of all strings, so it automatically |
| 1446 |
/// // inhibits any subsequent strings from matching. |
| 1447 |
/// let mut seq = Seq::new(&["foo", "bar", "", "quux", "fox"]); |
| 1448 |
/// seq.minimize_by_preference(); |
| 1449 |
/// let expected = Seq::from_iter([ |
| 1450 |
/// Literal::exact("foo"), |
| 1451 |
/// Literal::exact("bar"), |
| 1452 |
/// Literal::inexact(""), |
| 1453 |
/// ]); |
| 1454 |
/// assert_eq!(expected, seq); |
| 1455 |
/// |
| 1456 |
/// // And of course, if it's at the beginning, then it makes it impossible |
| 1457 |
/// // for anything else to match. |
| 1458 |
/// let mut seq = Seq::new(&["", "foo", "quux", "fox"]); |
| 1459 |
/// seq.minimize_by_preference(); |
| 1460 |
/// assert_eq!(Seq::from_iter([Literal::inexact("")]), seq); |
| 1461 |
/// ``` |
| 1462 |
#[inline] |
| 1463 |
pub fn minimize_by_preference(&mut self) { |
| 1464 |
if let Some(ref mut lits) = self.literals { |
| 1465 |
PreferenceTrie::minimize(lits, false); |
| 1466 |
} |
| 1467 |
} |
| 1468 |
|
| 1469 |
/// Trims all literals in this seq such that only the first `len` bytes |
| 1470 |
/// remain. If a literal has less than or equal to `len` bytes, then it |
| 1471 |
/// remains unchanged. Otherwise, it is trimmed and made inexact. |
| 1472 |
/// |
| 1473 |
/// # Example |
| 1474 |
/// |
| 1475 |
/// ``` |
| 1476 |
/// use regex_syntax::hir::literal::{Literal, Seq}; |
| 1477 |
/// |
| 1478 |
/// let mut seq = Seq::new(&["a", "foo", "quux"]); |
| 1479 |
/// seq.keep_first_bytes(2); |
| 1480 |
/// |
| 1481 |
/// let expected = Seq::from_iter([ |
| 1482 |
/// Literal::exact("a"), |
| 1483 |
/// Literal::inexact("fo"), |
| 1484 |
/// Literal::inexact("qu"), |
| 1485 |
/// ]); |
| 1486 |
/// assert_eq!(expected, seq); |
| 1487 |
/// ``` |
| 1488 |
#[inline] |
| 1489 |
pub fn keep_first_bytes(&mut self, len: usize) { |
| 1490 |
if let Some(ref mut lits) = self.literals { |
| 1491 |
for m in lits.iter_mut() { |
| 1492 |
m.keep_first_bytes(len); |
| 1493 |
} |
| 1494 |
} |
| 1495 |
} |
| 1496 |
|
| 1497 |
/// Trims all literals in this seq such that only the last `len` bytes |
| 1498 |
/// remain. If a literal has less than or equal to `len` bytes, then it |
| 1499 |
/// remains unchanged. Otherwise, it is trimmed and made inexact. |
| 1500 |
/// |
| 1501 |
/// # Example |
| 1502 |
/// |
| 1503 |
/// ``` |
| 1504 |
/// use regex_syntax::hir::literal::{Literal, Seq}; |
| 1505 |
/// |
| 1506 |
/// let mut seq = Seq::new(&["a", "foo", "quux"]); |
| 1507 |
/// seq.keep_last_bytes(2); |
| 1508 |
/// |
| 1509 |
/// let expected = Seq::from_iter([ |
| 1510 |
/// Literal::exact("a"), |
| 1511 |
/// Literal::inexact("oo"), |
| 1512 |
/// Literal::inexact("ux"), |
| 1513 |
/// ]); |
| 1514 |
/// assert_eq!(expected, seq); |
| 1515 |
/// ``` |
| 1516 |
#[inline] |
| 1517 |
pub fn keep_last_bytes(&mut self, len: usize) { |
| 1518 |
if let Some(ref mut lits) = self.literals { |
| 1519 |
for m in lits.iter_mut() { |
| 1520 |
m.keep_last_bytes(len); |
| 1521 |
} |
| 1522 |
} |
| 1523 |
} |
| 1524 |
|
| 1525 |
/// Returns true if this sequence is finite. |
| 1526 |
/// |
| 1527 |
/// When false, this sequence is infinite and must be treated as if it |
| 1528 |
/// contains every possible literal. |
| 1529 |
#[inline] |
| 1530 |
pub fn is_finite(&self) -> bool { |
| 1531 |
self.literals.is_some() |
| 1532 |
} |
| 1533 |
|
| 1534 |
/// Returns true if and only if this sequence is finite and empty. |
| 1535 |
/// |
| 1536 |
/// An empty sequence never matches anything. It can only be produced by |
| 1537 |
/// literal extraction when the corresponding regex itself cannot match. |
| 1538 |
#[inline] |
| 1539 |
pub fn is_empty(&self) -> bool { |
| 1540 |
self.len() == Some(0) |
| 1541 |
} |
| 1542 |
|
| 1543 |
/// Returns the number of literals in this sequence if the sequence is |
| 1544 |
/// finite. If the sequence is infinite, then `None` is returned. |
| 1545 |
#[inline] |
| 1546 |
pub fn len(&self) -> Option<usize> { |
| 1547 |
self.literals.as_ref().map(|lits| lits.len()) |
| 1548 |
} |
| 1549 |
|
| 1550 |
/// Returns true if and only if all literals in this sequence are exact. |
| 1551 |
/// |
| 1552 |
/// This returns false if the sequence is infinite. |
| 1553 |
#[inline] |
| 1554 |
pub fn is_exact(&self) -> bool { |
| 1555 |
self.literals().map_or(false, |lits| lits.iter().all(|x| x.is_exact())) |
| 1556 |
} |
| 1557 |
|
| 1558 |
/// Returns true if and only if all literals in this sequence are inexact. |
| 1559 |
/// |
| 1560 |
/// This returns true if the sequence is infinite. |
| 1561 |
#[inline] |
| 1562 |
pub fn is_inexact(&self) -> bool { |
| 1563 |
self.literals().map_or(true, |lits| lits.iter().all(|x| !x.is_exact())) |
| 1564 |
} |
| 1565 |
|
| 1566 |
/// Return the maximum length of the sequence that would result from |
| 1567 |
/// unioning `self` with `other`. If either set is infinite, then this |
| 1568 |
/// returns `None`. |
| 1569 |
#[inline] |
| 1570 |
pub fn max_union_len(&self, other: &Seq) -> Option<usize> { |
| 1571 |
let len1 = self.len()?; |
| 1572 |
let len2 = other.len()?; |
| 1573 |
Some(len1.saturating_add(len2)) |
| 1574 |
} |
| 1575 |
|
| 1576 |
/// Return the maximum length of the sequence that would result from the |
| 1577 |
/// cross product of `self` with `other`. If either set is infinite, then |
| 1578 |
/// this returns `None`. |
| 1579 |
#[inline] |
| 1580 |
pub fn max_cross_len(&self, other: &Seq) -> Option<usize> { |
| 1581 |
let len1 = self.len()?; |
| 1582 |
let len2 = other.len()?; |
| 1583 |
Some(len1.saturating_mul(len2)) |
| 1584 |
} |
| 1585 |
|
| 1586 |
/// Returns the length of the shortest literal in this sequence. |
| 1587 |
/// |
| 1588 |
/// If the sequence is infinite or empty, then this returns `None`. |
| 1589 |
#[inline] |
| 1590 |
pub fn min_literal_len(&self) -> Option<usize> { |
| 1591 |
self.literals.as_ref()?.iter().map(|x| x.len()).min() |
| 1592 |
} |
| 1593 |
|
| 1594 |
/// Returns the length of the longest literal in this sequence. |
| 1595 |
/// |
| 1596 |
/// If the sequence is infinite or empty, then this returns `None`. |
| 1597 |
#[inline] |
| 1598 |
pub fn max_literal_len(&self) -> Option<usize> { |
| 1599 |
self.literals.as_ref()?.iter().map(|x| x.len()).max() |
| 1600 |
} |
| 1601 |
|
| 1602 |
/// Returns the longest common prefix from this seq. |
| 1603 |
/// |
| 1604 |
/// If the seq matches any literal or other contains no literals, then |
| 1605 |
/// there is no meaningful prefix and this returns `None`. |
| 1606 |
/// |
| 1607 |
/// # Example |
| 1608 |
/// |
| 1609 |
/// This shows some example seqs and their longest common prefix. |
| 1610 |
/// |
| 1611 |
/// ``` |
| 1612 |
/// use regex_syntax::hir::literal::Seq; |
| 1613 |
/// |
| 1614 |
/// let seq = Seq::new(&["foo", "foobar", "fo"]); |
| 1615 |
/// assert_eq!(Some(&b"fo"[..]), seq.longest_common_prefix()); |
| 1616 |
/// let seq = Seq::new(&["foo", "foo"]); |
| 1617 |
/// assert_eq!(Some(&b"foo"[..]), seq.longest_common_prefix()); |
| 1618 |
/// let seq = Seq::new(&["foo", "bar"]); |
| 1619 |
/// assert_eq!(Some(&b""[..]), seq.longest_common_prefix()); |
| 1620 |
/// let seq = Seq::new(&[""]); |
| 1621 |
/// assert_eq!(Some(&b""[..]), seq.longest_common_prefix()); |
| 1622 |
/// |
| 1623 |
/// let seq = Seq::infinite(); |
| 1624 |
/// assert_eq!(None, seq.longest_common_prefix()); |
| 1625 |
/// let seq = Seq::empty(); |
| 1626 |
/// assert_eq!(None, seq.longest_common_prefix()); |
| 1627 |
/// ``` |
| 1628 |
#[inline] |
| 1629 |
pub fn longest_common_prefix(&self) -> Option<&[u8]> { |
| 1630 |
// If we match everything or match nothing, then there's no meaningful |
| 1631 |
// longest common prefix. |
| 1632 |
let lits = match self.literals { |
| 1633 |
None => return None, |
| 1634 |
Some(ref lits) => lits, |
| 1635 |
}; |
| 1636 |
if lits.len() == 0 { |
| 1637 |
return None; |
| 1638 |
} |
| 1639 |
let base = lits[0].as_bytes(); |
| 1640 |
let mut len = base.len(); |
| 1641 |
for m in lits.iter().skip(1) { |
| 1642 |
len = m |
| 1643 |
.as_bytes() |
| 1644 |
.iter() |
| 1645 |
.zip(base[..len].iter()) |
| 1646 |
.take_while(|&(a, b)| a == b) |
| 1647 |
.count(); |
| 1648 |
if len == 0 { |
| 1649 |
return Some(&[]); |
| 1650 |
} |
| 1651 |
} |
| 1652 |
Some(&base[..len]) |
| 1653 |
} |
| 1654 |
|
| 1655 |
/// Returns the longest common suffix from this seq. |
| 1656 |
/// |
| 1657 |
/// If the seq matches any literal or other contains no literals, then |
| 1658 |
/// there is no meaningful suffix and this returns `None`. |
| 1659 |
/// |
| 1660 |
/// # Example |
| 1661 |
/// |
| 1662 |
/// This shows some example seqs and their longest common suffix. |
| 1663 |
/// |
| 1664 |
/// ``` |
| 1665 |
/// use regex_syntax::hir::literal::Seq; |
| 1666 |
/// |
| 1667 |
/// let seq = Seq::new(&["oof", "raboof", "of"]); |
| 1668 |
/// assert_eq!(Some(&b"of"[..]), seq.longest_common_suffix()); |
| 1669 |
/// let seq = Seq::new(&["foo", "foo"]); |
| 1670 |
/// assert_eq!(Some(&b"foo"[..]), seq.longest_common_suffix()); |
| 1671 |
/// let seq = Seq::new(&["foo", "bar"]); |
| 1672 |
/// assert_eq!(Some(&b""[..]), seq.longest_common_suffix()); |
| 1673 |
/// let seq = Seq::new(&[""]); |
| 1674 |
/// assert_eq!(Some(&b""[..]), seq.longest_common_suffix()); |
| 1675 |
/// |
| 1676 |
/// let seq = Seq::infinite(); |
| 1677 |
/// assert_eq!(None, seq.longest_common_suffix()); |
| 1678 |
/// let seq = Seq::empty(); |
| 1679 |
/// assert_eq!(None, seq.longest_common_suffix()); |
| 1680 |
/// ``` |
| 1681 |
#[inline] |
| 1682 |
pub fn longest_common_suffix(&self) -> Option<&[u8]> { |
| 1683 |
// If we match everything or match nothing, then there's no meaningful |
| 1684 |
// longest common suffix. |
| 1685 |
let lits = match self.literals { |
| 1686 |
None => return None, |
| 1687 |
Some(ref lits) => lits, |
| 1688 |
}; |
| 1689 |
if lits.len() == 0 { |
| 1690 |
return None; |
| 1691 |
} |
| 1692 |
let base = lits[0].as_bytes(); |
| 1693 |
let mut len = base.len(); |
| 1694 |
for m in lits.iter().skip(1) { |
| 1695 |
len = m |
| 1696 |
.as_bytes() |
| 1697 |
.iter() |
| 1698 |
.rev() |
| 1699 |
.zip(base[base.len() - len..].iter().rev()) |
| 1700 |
.take_while(|&(a, b)| a == b) |
| 1701 |
.count(); |
| 1702 |
if len == 0 { |
| 1703 |
return Some(&[]); |
| 1704 |
} |
| 1705 |
} |
| 1706 |
Some(&base[base.len() - len..]) |
| 1707 |
} |
| 1708 |
|
| 1709 |
/// Optimizes this seq while treating its literals as prefixes and |
| 1710 |
/// respecting the preference order of its literals. |
| 1711 |
/// |
| 1712 |
/// The specific way "optimization" works is meant to be an implementation |
| 1713 |
/// detail, as it essentially represents a set of heuristics. The goal |
| 1714 |
/// that optimization tries to accomplish is to make the literals in this |
| 1715 |
/// set reflect inputs that will result in a more effective prefilter. |
| 1716 |
/// Principally by reducing the false positive rate of candidates found by |
| 1717 |
/// the literals in this sequence. That is, when a match of a literal is |
| 1718 |
/// found, we would like it to be a strong predictor of the overall match |
| 1719 |
/// of the regex. If it isn't, then much time will be spent starting and |
| 1720 |
/// stopping the prefilter search and attempting to confirm the match only |
| 1721 |
/// to have it fail. |
| 1722 |
/// |
| 1723 |
/// Some of those heuristics might be: |
| 1724 |
/// |
| 1725 |
/// * Identifying a common prefix from a larger sequence of literals, and |
| 1726 |
/// shrinking the sequence down to that single common prefix. |
| 1727 |
/// * Rejecting the sequence entirely if it is believed to result in very |
| 1728 |
/// high false positive rate. When this happens, the sequence is made |
| 1729 |
/// infinite. |
| 1730 |
/// * Shrinking the sequence to a smaller number of literals representing |
| 1731 |
/// prefixes, but not shrinking it so much as to make literals too short. |
| 1732 |
/// (A sequence with very short literals, of 1 or 2 bytes, will typically |
| 1733 |
/// result in a higher false positive rate.) |
| 1734 |
/// |
| 1735 |
/// Optimization should only be run once extraction is complete. Namely, |
| 1736 |
/// optimization may make assumptions that do not compose with other |
| 1737 |
/// operations in the middle of extraction. For example, optimization will |
| 1738 |
/// reduce `[E(sam), E(samwise)]` to `[E(sam)]`, but such a transformation |
| 1739 |
/// is only valid if no other extraction will occur. If other extraction |
| 1740 |
/// may occur, then the correct transformation would be to `[I(sam)]`. |
| 1741 |
/// |
| 1742 |
/// The [`Seq::optimize_for_suffix_by_preference`] does the same thing, but |
| 1743 |
/// for suffixes. |
| 1744 |
/// |
| 1745 |
/// # Example |
| 1746 |
/// |
| 1747 |
/// This shows how optimization might transform a sequence. Note that |
| 1748 |
/// the specific behavior is not a documented guarantee. The heuristics |
| 1749 |
/// used are an implementation detail and may change over time in semver |
| 1750 |
/// compatible releases. |
| 1751 |
/// |
| 1752 |
/// ``` |
| 1753 |
/// use regex_syntax::hir::literal::{Seq, Literal}; |
| 1754 |
/// |
| 1755 |
/// let mut seq = Seq::new(&[ |
| 1756 |
/// "samantha", |
| 1757 |
/// "sam", |
| 1758 |
/// "samwise", |
| 1759 |
/// "frodo", |
| 1760 |
/// ]); |
| 1761 |
/// seq.optimize_for_prefix_by_preference(); |
| 1762 |
/// assert_eq!(Seq::from_iter([ |
| 1763 |
/// Literal::exact("samantha"), |
| 1764 |
/// // Kept exact even though 'samwise' got pruned |
| 1765 |
/// // because optimization assumes literal extraction |
| 1766 |
/// // has finished. |
| 1767 |
/// Literal::exact("sam"), |
| 1768 |
/// Literal::exact("frodo"), |
| 1769 |
/// ]), seq); |
| 1770 |
/// ``` |
| 1771 |
/// |
| 1772 |
/// # Example: optimization may make the sequence infinite |
| 1773 |
/// |
| 1774 |
/// If the heuristics deem that the sequence could cause a very high false |
| 1775 |
/// positive rate, then it may make the sequence infinite, effectively |
| 1776 |
/// disabling its use as a prefilter. |
| 1777 |
/// |
| 1778 |
/// ``` |
| 1779 |
/// use regex_syntax::hir::literal::{Seq, Literal}; |
| 1780 |
/// |
| 1781 |
/// let mut seq = Seq::new(&[ |
| 1782 |
/// "samantha", |
| 1783 |
/// // An empty string matches at every position, |
| 1784 |
/// // thus rendering the prefilter completely |
| 1785 |
/// // ineffective. |
| 1786 |
/// "", |
| 1787 |
/// "sam", |
| 1788 |
/// "samwise", |
| 1789 |
/// "frodo", |
| 1790 |
/// ]); |
| 1791 |
/// seq.optimize_for_prefix_by_preference(); |
| 1792 |
/// assert!(!seq.is_finite()); |
| 1793 |
/// ``` |
| 1794 |
/// |
| 1795 |
/// Do note that just because there is a `" "` in the sequence, that |
| 1796 |
/// doesn't mean the sequence will always be made infinite after it is |
| 1797 |
/// optimized. Namely, if the sequence is considered exact (any match |
| 1798 |
/// corresponds to an overall match of the original regex), then any match |
| 1799 |
/// is an overall match, and so the false positive rate is always `0`. |
| 1800 |
/// |
| 1801 |
/// To demonstrate this, we remove `samwise` from our sequence. This |
| 1802 |
/// results in no optimization happening and all literals remain exact. |
| 1803 |
/// Thus the entire sequence is exact, and it is kept as-is, even though |
| 1804 |
/// one is an ASCII space: |
| 1805 |
/// |
| 1806 |
/// ``` |
| 1807 |
/// use regex_syntax::hir::literal::{Seq, Literal}; |
| 1808 |
/// |
| 1809 |
/// let mut seq = Seq::new(&[ |
| 1810 |
/// "samantha", |
| 1811 |
/// " ", |
| 1812 |
/// "sam", |
| 1813 |
/// "frodo", |
| 1814 |
/// ]); |
| 1815 |
/// seq.optimize_for_prefix_by_preference(); |
| 1816 |
/// assert!(seq.is_finite()); |
| 1817 |
/// ``` |
| 1818 |
#[inline] |
| 1819 |
pub fn optimize_for_prefix_by_preference(&mut self) { |
| 1820 |
self.optimize_by_preference(true); |
| 1821 |
} |
| 1822 |
|
| 1823 |
/// Optimizes this seq while treating its literals as suffixes and |
| 1824 |
/// respecting the preference order of its literals. |
| 1825 |
/// |
| 1826 |
/// Optimization should only be run once extraction is complete. |
| 1827 |
/// |
| 1828 |
/// The [`Seq::optimize_for_prefix_by_preference`] does the same thing, but |
| 1829 |
/// for prefixes. See its documentation for more explanation. |
| 1830 |
#[inline] |
| 1831 |
pub fn optimize_for_suffix_by_preference(&mut self) { |
| 1832 |
self.optimize_by_preference(false); |
| 1833 |
} |
| 1834 |
|
| 1835 |
fn optimize_by_preference(&mut self, prefix: bool) { |
| 1836 |
let origlen = match self.len() { |
| 1837 |
None => return, |
| 1838 |
Some(len) => len, |
| 1839 |
}; |
| 1840 |
// Just give up now if our sequence contains an empty string. |
| 1841 |
if self.min_literal_len().map_or(false, |len| len == 0) { |
| 1842 |
// We squash the sequence so that nobody else gets any bright |
| 1843 |
// ideas to try and use it. An empty string implies a match at |
| 1844 |
// every position. A prefilter cannot help you here. |
| 1845 |
self.make_infinite(); |
| 1846 |
return; |
| 1847 |
} |
| 1848 |
// Make sure we start with the smallest sequence possible. We use a |
| 1849 |
// special version of preference minimization that retains exactness. |
| 1850 |
// This is legal because optimization is only expected to occur once |
| 1851 |
// extraction is complete. |
| 1852 |
if prefix { |
| 1853 |
if let Some(ref mut lits) = self.literals { |
| 1854 |
PreferenceTrie::minimize(lits, true); |
| 1855 |
} |
| 1856 |
} |
| 1857 |
|
| 1858 |
// Look for a common prefix (or suffix). If we found one of those and |
| 1859 |
// it's long enough, then it's a good bet that it will be our fastest |
| 1860 |
// possible prefilter since single-substring search is so fast. |
| 1861 |
let fix = if prefix { |
| 1862 |
self.longest_common_prefix() |
| 1863 |
} else { |
| 1864 |
self.longest_common_suffix() |
| 1865 |
}; |
| 1866 |
if let Some(fix) = fix { |
| 1867 |
// As a special case, if we have a common prefix and the leading |
| 1868 |
// byte of that prefix is one that we think probably occurs rarely, |
| 1869 |
// then strip everything down to just that single byte. This should |
| 1870 |
// promote the use of memchr. |
| 1871 |
// |
| 1872 |
// ... we only do this though if our sequence has more than one |
| 1873 |
// literal. Otherwise, we'd rather just stick with a single literal |
| 1874 |
// scan. That is, using memchr is probably better than looking |
| 1875 |
// for 2 or more literals, but probably not as good as a straight |
| 1876 |
// memmem search. |
| 1877 |
// |
| 1878 |
// ... and also only do this when the prefix is short and probably |
| 1879 |
// not too discriminatory anyway. If it's longer, then it's |
| 1880 |
// probably quite discriminatory and thus is likely to have a low |
| 1881 |
// false positive rate. |
| 1882 |
if prefix |
| 1883 |
&& origlen > 1 |
| 1884 |
&& fix.len() >= 1 |
| 1885 |
&& fix.len() <= 3 |
| 1886 |
&& rank(fix[0]) < 200 |
| 1887 |
{ |
| 1888 |
self.keep_first_bytes(1); |
| 1889 |
self.dedup(); |
| 1890 |
return; |
| 1891 |
} |
| 1892 |
// We only strip down to the common prefix/suffix if we think |
| 1893 |
// the existing set of literals isn't great, or if the common |
| 1894 |
// prefix/suffix is expected to be particularly discriminatory. |
| 1895 |
let isfast = |
| 1896 |
self.is_exact() && self.len().map_or(false, |len| len <= 16); |
| 1897 |
let usefix = fix.len() > 4 || (fix.len() > 1 && !isfast); |
| 1898 |
if usefix { |
| 1899 |
// If we keep exactly the number of bytes equal to the length |
| 1900 |
// of the prefix (or suffix), then by the definition of a |
| 1901 |
// prefix, every literal in the sequence will be equivalent. |
| 1902 |
// Thus, 'dedup' will leave us with one literal. |
| 1903 |
// |
| 1904 |
// We do it this way to avoid an alloc, but also to make sure |
| 1905 |
// the exactness of literals is kept (or not). |
| 1906 |
if prefix { |
| 1907 |
self.keep_first_bytes(fix.len()); |
| 1908 |
} else { |
| 1909 |
self.keep_last_bytes(fix.len()); |
| 1910 |
} |
| 1911 |
self.dedup(); |
| 1912 |
assert_eq!(Some(1), self.len()); |
| 1913 |
// We still fall through here. In particular, we want our |
| 1914 |
// longest common prefix to be subject to the poison check. |
| 1915 |
} |
| 1916 |
} |
| 1917 |
// If we have an exact sequence, we *probably* just want to keep it |
| 1918 |
// as-is. But there are some cases where we don't. So we save a copy of |
| 1919 |
// the exact sequence now, and then try to do some more optimizations |
| 1920 |
// below. If those don't work out, we go back to this exact sequence. |
| 1921 |
// |
| 1922 |
// The specific motivation for this is that we sometimes wind up with |
| 1923 |
// an exact sequence with a hefty number of literals. Say, 100. If we |
| 1924 |
// stuck with that, it would be too big for Teddy and would result in |
| 1925 |
// using Aho-Corasick. Which is fine... but the lazy DFA is plenty |
| 1926 |
// suitable in such cases. The real issue is that we will wind up not |
| 1927 |
// using a fast prefilter at all. So in cases like this, even though |
| 1928 |
// we have an exact sequence, it would be better to try and shrink the |
| 1929 |
// sequence (which we do below) and use it as a prefilter that can |
| 1930 |
// produce false positive matches. |
| 1931 |
// |
| 1932 |
// But if the shrinking below results in a sequence that "sucks," then |
| 1933 |
// we don't want to use that because we already have an exact sequence |
| 1934 |
// in hand. |
| 1935 |
let exact: Option<Seq> = |
| 1936 |
if self.is_exact() { Some(self.clone()) } else { None }; |
| 1937 |
// Now we attempt to shorten the sequence. The idea here is that we |
| 1938 |
// don't want to look for too many literals, but we want to shorten |
| 1939 |
// our sequence enough to improve our odds of using better algorithms |
| 1940 |
// downstream (such as Teddy). |
| 1941 |
// |
| 1942 |
// The pair of numbers in this list corresponds to the maximal prefix |
| 1943 |
// (in bytes) to keep for all literals and the length of the sequence |
| 1944 |
// at which to do it. |
| 1945 |
// |
| 1946 |
// So for example, the pair (3, 500) would mean, "if we have more than |
| 1947 |
// 500 literals in our sequence, then truncate all of our literals |
| 1948 |
// such that they are at most 3 bytes in length and the minimize the |
| 1949 |
// sequence." |
| 1950 |
const ATTEMPTS: [(usize, usize); 5] = |
| 1951 |
[(5, 10), (4, 10), (3, 64), (2, 64), (1, 10)]; |
| 1952 |
for (keep, limit) in ATTEMPTS { |
| 1953 |
let len = match self.len() { |
| 1954 |
None => break, |
| 1955 |
Some(len) => len, |
| 1956 |
}; |
| 1957 |
if len <= limit { |
| 1958 |
break; |
| 1959 |
} |
| 1960 |
if prefix { |
| 1961 |
self.keep_first_bytes(keep); |
| 1962 |
} else { |
| 1963 |
self.keep_last_bytes(keep); |
| 1964 |
} |
| 1965 |
if prefix { |
| 1966 |
if let Some(ref mut lits) = self.literals { |
| 1967 |
PreferenceTrie::minimize(lits, true); |
| 1968 |
} |
| 1969 |
} |
| 1970 |
} |
| 1971 |
// Check for a poison literal. A poison literal is one that is short |
| 1972 |
// and is believed to have a very high match count. These poisons |
| 1973 |
// generally lead to a prefilter with a very high false positive rate, |
| 1974 |
// and thus overall worse performance. |
| 1975 |
// |
| 1976 |
// We do this last because we could have gone from a non-poisonous |
| 1977 |
// sequence to a poisonous one. Perhaps we should add some code to |
| 1978 |
// prevent such transitions in the first place, but then again, we |
| 1979 |
// likely only made the transition in the first place if the sequence |
| 1980 |
// was itself huge. And huge sequences are themselves poisonous. So... |
| 1981 |
if let Some(lits) = self.literals() { |
| 1982 |
if lits.iter().any(|lit| lit.is_poisonous()) { |
| 1983 |
self.make_infinite(); |
| 1984 |
} |
| 1985 |
} |
| 1986 |
// OK, if we had an exact sequence before attempting more optimizations |
| 1987 |
// above and our post-optimized sequence sucks for some reason or |
| 1988 |
// another, then we go back to the exact sequence. |
| 1989 |
if let Some(exact) = exact { |
| 1990 |
// If optimizing resulted in dropping our literals, then certainly |
| 1991 |
// backup and use the exact sequence that we had. |
| 1992 |
if !self.is_finite() { |
| 1993 |
*self = exact; |
| 1994 |
return; |
| 1995 |
} |
| 1996 |
// If our optimized sequence contains a short literal, then it's |
| 1997 |
// *probably* not so great. So throw it away and revert to the |
| 1998 |
// exact sequence. |
| 1999 |
if self.min_literal_len().map_or(true, |len| len <= 2) { |
| 2000 |
*self = exact; |
| 2001 |
return; |
| 2002 |
} |
| 2003 |
// Finally, if our optimized sequence is "big" (i.e., can't use |
| 2004 |
// Teddy), then also don't use it and rely on the exact sequence. |
| 2005 |
if self.len().map_or(true, |len| len > 64) { |
| 2006 |
*self = exact; |
| 2007 |
return; |
| 2008 |
} |
| 2009 |
} |
| 2010 |
} |
| 2011 |
} |
| 2012 |
|
| 2013 |
impl core::fmt::Debug for Seq { |
| 2014 |
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { |
| 2015 |
write!(f, "Seq")?; |
| 2016 |
if let Some(lits) = self.literals() { |
| 2017 |
f.debug_list().entries(lits.iter()).finish() |
| 2018 |
} else { |
| 2019 |
write!(f, "[∞]") |
| 2020 |
} |
| 2021 |
} |
| 2022 |
} |
| 2023 |
|
| 2024 |
impl FromIterator<Literal> for Seq { |
| 2025 |
fn from_iter<T: IntoIterator<Item = Literal>>(it: T) -> Seq { |
| 2026 |
let mut seq = Seq::empty(); |
| 2027 |
for literal in it { |
| 2028 |
seq.push(literal); |
| 2029 |
} |
| 2030 |
seq |
| 2031 |
} |
| 2032 |
} |
| 2033 |
|
| 2034 |
/// A single literal extracted from an [`Hir`] expression. |
| 2035 |
/// |
| 2036 |
/// A literal is composed of two things: |
| 2037 |
/// |
| 2038 |
/// * A sequence of bytes. No guarantees with respect to UTF-8 are provided. |
| 2039 |
/// In particular, even if the regex a literal is extracted from is UTF-8, the |
| 2040 |
/// literal extracted may not be valid UTF-8. (For example, if an [`Extractor`] |
| 2041 |
/// limit resulted in trimming a literal in a way that splits a codepoint.) |
| 2042 |
/// * Whether the literal is "exact" or not. An "exact" literal means that it |
| 2043 |
/// has not been trimmed, and may continue to be extended. If a literal is |
| 2044 |
/// "exact" after visiting the entire `Hir` expression, then this implies that |
| 2045 |
/// the literal leads to a match state. (Although it doesn't necessarily imply |
| 2046 |
/// all occurrences of the literal correspond to a match of the regex, since |
| 2047 |
/// literal extraction ignores look-around assertions.) |
| 2048 |
#[derive(Clone, Eq, PartialEq, PartialOrd, Ord)] |
| 2049 |
pub struct Literal { |
| 2050 |
bytes: Vec<u8>, |
| 2051 |
exact: bool, |
| 2052 |
} |
| 2053 |
|
| 2054 |
impl Literal { |
| 2055 |
/// Returns a new exact literal containing the bytes given. |
| 2056 |
#[inline] |
| 2057 |
pub fn exact<B: Into<Vec<u8>>>(bytes: B) -> Literal { |
| 2058 |
Literal { bytes: bytes.into(), exact: true } |
| 2059 |
} |
| 2060 |
|
| 2061 |
/// Returns a new inexact literal containing the bytes given. |
| 2062 |
#[inline] |
| 2063 |
pub fn inexact<B: Into<Vec<u8>>>(bytes: B) -> Literal { |
| 2064 |
Literal { bytes: bytes.into(), exact: false } |
| 2065 |
} |
| 2066 |
|
| 2067 |
/// Returns the bytes in this literal. |
| 2068 |
#[inline] |
| 2069 |
pub fn as_bytes(&self) -> &[u8] { |
| 2070 |
&self.bytes |
| 2071 |
} |
| 2072 |
|
| 2073 |
/// Yields ownership of the bytes inside this literal. |
| 2074 |
/// |
| 2075 |
/// Note that this throws away whether the literal is "exact" or not. |
| 2076 |
#[inline] |
| 2077 |
pub fn into_bytes(self) -> Vec<u8> { |
| 2078 |
self.bytes |
| 2079 |
} |
| 2080 |
|
| 2081 |
/// Returns the length of this literal in bytes. |
| 2082 |
#[inline] |
| 2083 |
pub fn len(&self) -> usize { |
| 2084 |
self.as_bytes().len() |
| 2085 |
} |
| 2086 |
|
| 2087 |
/// Returns true if and only if this literal has zero bytes. |
| 2088 |
#[inline] |
| 2089 |
pub fn is_empty(&self) -> bool { |
| 2090 |
self.len() == 0 |
| 2091 |
} |
| 2092 |
|
| 2093 |
/// Returns true if and only if this literal is exact. |
| 2094 |
#[inline] |
| 2095 |
pub fn is_exact(&self) -> bool { |
| 2096 |
self.exact |
| 2097 |
} |
| 2098 |
|
| 2099 |
/// Marks this literal as inexact. |
| 2100 |
/// |
| 2101 |
/// Inexact literals can never be extended. For example, |
| 2102 |
/// [`Seq::cross_forward`] will not extend inexact literals. |
| 2103 |
#[inline] |
| 2104 |
pub fn make_inexact(&mut self) { |
| 2105 |
self.exact = false; |
| 2106 |
} |
| 2107 |
|
| 2108 |
/// Reverse the bytes in this literal. |
| 2109 |
#[inline] |
| 2110 |
pub fn reverse(&mut self) { |
| 2111 |
self.bytes.reverse(); |
| 2112 |
} |
| 2113 |
|
| 2114 |
/// Extend this literal with the literal given. |
| 2115 |
/// |
| 2116 |
/// If this literal is inexact, then this is a no-op. |
| 2117 |
#[inline] |
| 2118 |
pub fn extend(&mut self, lit: &Literal) { |
| 2119 |
if !self.is_exact() { |
| 2120 |
return; |
| 2121 |
} |
| 2122 |
self.bytes.extend_from_slice(&lit.bytes); |
| 2123 |
} |
| 2124 |
|
| 2125 |
/// Trims this literal such that only the first `len` bytes remain. If |
| 2126 |
/// this literal has fewer than `len` bytes, then it remains unchanged. |
| 2127 |
/// Otherwise, the literal is marked as inexact. |
| 2128 |
#[inline] |
| 2129 |
pub fn keep_first_bytes(&mut self, len: usize) { |
| 2130 |
if len >= self.len() { |
| 2131 |
return; |
| 2132 |
} |
| 2133 |
self.make_inexact(); |
| 2134 |
self.bytes.truncate(len); |
| 2135 |
} |
| 2136 |
|
| 2137 |
/// Trims this literal such that only the last `len` bytes remain. If this |
| 2138 |
/// literal has fewer than `len` bytes, then it remains unchanged. |
| 2139 |
/// Otherwise, the literal is marked as inexact. |
| 2140 |
#[inline] |
| 2141 |
pub fn keep_last_bytes(&mut self, len: usize) { |
| 2142 |
if len >= self.len() { |
| 2143 |
return; |
| 2144 |
} |
| 2145 |
self.make_inexact(); |
| 2146 |
self.bytes.drain(..self.len() - len); |
| 2147 |
} |
| 2148 |
|
| 2149 |
/// Returns true if it is believe that this literal is likely to match very |
| 2150 |
/// frequently, and is thus not a good candidate for a prefilter. |
| 2151 |
fn is_poisonous(&self) -> bool { |
| 2152 |
self.is_empty() || (self.len() == 1 && rank(self.as_bytes()[0]) >= 250) |
| 2153 |
} |
| 2154 |
} |
| 2155 |
|
| 2156 |
impl From<u8> for Literal { |
| 2157 |
fn from(byte: u8) -> Literal { |
| 2158 |
Literal::exact(vec![byte]) |
| 2159 |
} |
| 2160 |
} |
| 2161 |
|
| 2162 |
impl From<char> for Literal { |
| 2163 |
fn from(ch: char) -> Literal { |
| 2164 |
use alloc::string::ToString; |
| 2165 |
Literal::exact(ch.encode_utf8(&mut [0; 4]).to_string()) |
| 2166 |
} |
| 2167 |
} |
| 2168 |
|
| 2169 |
impl AsRef<[u8]> for Literal { |
| 2170 |
fn as_ref(&self) -> &[u8] { |
| 2171 |
self.as_bytes() |
| 2172 |
} |
| 2173 |
} |
| 2174 |
|
| 2175 |
impl core::fmt::Debug for Literal { |
| 2176 |
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { |
| 2177 |
let tag = if self.exact { "E" } else { "I" }; |
| 2178 |
f.debug_tuple(tag) |
| 2179 |
.field(&crate::debug::Bytes(self.as_bytes())) |
| 2180 |
.finish() |
| 2181 |
} |
| 2182 |
} |
| 2183 |
|
| 2184 |
/// A "preference" trie that rejects literals that will never match when |
| 2185 |
/// executing a leftmost first or "preference" search. |
| 2186 |
/// |
| 2187 |
/// For example, if 'sam' is inserted, then trying to insert 'samwise' will be |
| 2188 |
/// rejected because 'samwise' can never match since 'sam' will always take |
| 2189 |
/// priority. However, if 'samwise' is inserted first, then inserting 'sam' |
| 2190 |
/// after it is accepted. In this case, either 'samwise' or 'sam' can match in |
| 2191 |
/// a "preference" search. |
| 2192 |
/// |
| 2193 |
/// Note that we only use this trie as a "set." That is, given a sequence of |
| 2194 |
/// literals, we insert each one in order. An `insert` will reject a literal |
| 2195 |
/// if a prefix of that literal already exists in the trie. Thus, to rebuild |
| 2196 |
/// the "minimal" sequence, we simply only keep literals that were successfully |
| 2197 |
/// inserted. (Since we don't need traversal, one wonders whether we can make |
| 2198 |
/// some simplifications here, but I haven't given it a ton of thought and I've |
| 2199 |
/// never seen this show up on a profile. Because of the heuristic limits |
| 2200 |
/// imposed on literal extractions, the size of the inputs here is usually |
| 2201 |
/// very small.) |
| 2202 |
#[derive(Debug)] |
| 2203 |
struct PreferenceTrie { |
| 2204 |
/// The states in this trie. The index of a state in this vector is its ID. |
| 2205 |
states: Vec<State>, |
| 2206 |
/// This vec indicates which states are match states. It always has |
| 2207 |
/// the same length as `states` and is indexed by the same state ID. |
| 2208 |
/// A state with identifier `sid` is a match state if and only if |
| 2209 |
/// `matches[sid].is_some()`. The option contains the index of the literal |
| 2210 |
/// corresponding to the match. The index is offset by 1 so that it fits in |
| 2211 |
/// a NonZeroUsize. |
| 2212 |
matches: Vec<Option<NonZeroUsize>>, |
| 2213 |
/// The index to allocate to the next literal added to this trie. Starts at |
| 2214 |
/// 1 and increments by 1 for every literal successfully added to the trie. |
| 2215 |
next_literal_index: usize, |
| 2216 |
} |
| 2217 |
|
| 2218 |
/// A single state in a trie. Uses a sparse representation for its transitions. |
| 2219 |
#[derive(Debug, Default)] |
| 2220 |
struct State { |
| 2221 |
/// Sparse representation of the transitions out of this state. Transitions |
| 2222 |
/// are sorted by byte. There is at most one such transition for any |
| 2223 |
/// particular byte. |
| 2224 |
trans: Vec<(u8, usize)>, |
| 2225 |
} |
| 2226 |
|
| 2227 |
impl PreferenceTrie { |
| 2228 |
/// Minimizes the given sequence of literals while preserving preference |
| 2229 |
/// order semantics. |
| 2230 |
/// |
| 2231 |
/// When `keep_exact` is true, the exactness of every literal retained is |
| 2232 |
/// kept. This is useful when dealing with a fully extracted `Seq` that |
| 2233 |
/// only contains exact literals. In that case, we can keep all retained |
| 2234 |
/// literals as exact because we know we'll never need to match anything |
| 2235 |
/// after them and because any removed literals are guaranteed to never |
| 2236 |
/// match. |
| 2237 |
fn minimize(literals: &mut Vec<Literal>, keep_exact: bool) { |
| 2238 |
let mut trie = PreferenceTrie { |
| 2239 |
states: vec![], |
| 2240 |
matches: vec![], |
| 2241 |
next_literal_index: 1, |
| 2242 |
}; |
| 2243 |
let mut make_inexact = vec![]; |
| 2244 |
literals.retain_mut(|lit| match trie.insert(lit.as_bytes()) { |
| 2245 |
Ok(_) => true, |
| 2246 |
Err(i) => { |
| 2247 |
if !keep_exact { |
| 2248 |
make_inexact.push(i.checked_sub(1).unwrap()); |
| 2249 |
} |
| 2250 |
false |
| 2251 |
} |
| 2252 |
}); |
| 2253 |
for i in make_inexact { |
| 2254 |
literals[i].make_inexact(); |
| 2255 |
} |
| 2256 |
} |
| 2257 |
|
| 2258 |
/// Returns `Ok` if the given byte string is accepted into this trie and |
| 2259 |
/// `Err` otherwise. The index for the success case corresponds to the |
| 2260 |
/// index of the literal added. The index for the error case corresponds to |
| 2261 |
/// the index of the literal already in the trie that prevented the given |
| 2262 |
/// byte string from being added. (Which implies it is a prefix of the one |
| 2263 |
/// given.) |
| 2264 |
/// |
| 2265 |
/// In short, the byte string given is accepted into the trie if and only |
| 2266 |
/// if it is possible for it to match when executing a preference order |
| 2267 |
/// search. |
| 2268 |
fn insert(&mut self, bytes: &[u8]) -> Result<usize, usize> { |
| 2269 |
let mut prev = self.root(); |
| 2270 |
if let Some(idx) = self.matches[prev] { |
| 2271 |
return Err(idx.get()); |
| 2272 |
} |
| 2273 |
for &b in bytes.iter() { |
| 2274 |
match self.states[prev].trans.binary_search_by_key(&b, |t| t.0) { |
| 2275 |
Ok(i) => { |
| 2276 |
prev = self.states[prev].trans[i].1; |
| 2277 |
if let Some(idx) = self.matches[prev] { |
| 2278 |
return Err(idx.get()); |
| 2279 |
} |
| 2280 |
} |
| 2281 |
Err(i) => { |
| 2282 |
let next = self.create_state(); |
| 2283 |
self.states[prev].trans.insert(i, (b, next)); |
| 2284 |
prev = next; |
| 2285 |
} |
| 2286 |
} |
| 2287 |
} |
| 2288 |
let idx = self.next_literal_index; |
| 2289 |
self.next_literal_index += 1; |
| 2290 |
self.matches[prev] = NonZeroUsize::new(idx); |
| 2291 |
Ok(idx) |
| 2292 |
} |
| 2293 |
|
| 2294 |
/// Returns the root state ID, and if it doesn't exist, creates it. |
| 2295 |
fn root(&mut self) -> usize { |
| 2296 |
if !self.states.is_empty() { |
| 2297 |
0 |
| 2298 |
} else { |
| 2299 |
self.create_state() |
| 2300 |
} |
| 2301 |
} |
| 2302 |
|
| 2303 |
/// Creates a new empty state and returns its ID. |
| 2304 |
fn create_state(&mut self) -> usize { |
| 2305 |
let id = self.states.len(); |
| 2306 |
self.states.push(State::default()); |
| 2307 |
self.matches.push(None); |
| 2308 |
id |
| 2309 |
} |
| 2310 |
} |
| 2311 |
|
| 2312 |
/// Returns the "rank" of the given byte. |
| 2313 |
/// |
| 2314 |
/// The minimum rank value is `0` and the maximum rank value is `255`. |
| 2315 |
/// |
| 2316 |
/// The rank of a byte is derived from a heuristic background distribution of |
| 2317 |
/// relative frequencies of bytes. The heuristic says that lower the rank of a |
| 2318 |
/// byte, the less likely that byte is to appear in any arbitrary haystack. |
| 2319 |
pub fn rank(byte: u8) -> u8 { |
| 2320 |
crate::rank::BYTE_FREQUENCIES[usize::from(byte)] |
| 2321 |
} |
| 2322 |
|
| 2323 |
#[cfg(test)] |
| 2324 |
mod tests { |
| 2325 |
use super::*; |
| 2326 |
|
| 2327 |
fn parse(pattern: &str) -> Hir { |
| 2328 |
crate::ParserBuilder::new().utf8(false).build().parse(pattern).unwrap() |
| 2329 |
} |
| 2330 |
|
| 2331 |
fn prefixes(pattern: &str) -> Seq { |
| 2332 |
Extractor::new().kind(ExtractKind::Prefix).extract(&parse(pattern)) |
| 2333 |
} |
| 2334 |
|
| 2335 |
fn suffixes(pattern: &str) -> Seq { |
| 2336 |
Extractor::new().kind(ExtractKind::Suffix).extract(&parse(pattern)) |
| 2337 |
} |
| 2338 |
|
| 2339 |
fn e(pattern: &str) -> (Seq, Seq) { |
| 2340 |
(prefixes(pattern), suffixes(pattern)) |
| 2341 |
} |
| 2342 |
|
| 2343 |
#[allow(non_snake_case)] |
| 2344 |
fn E(x: &str) -> Literal { |
| 2345 |
Literal::exact(x.as_bytes()) |
| 2346 |
} |
| 2347 |
|
| 2348 |
#[allow(non_snake_case)] |
| 2349 |
fn I(x: &str) -> Literal { |
| 2350 |
Literal::inexact(x.as_bytes()) |
| 2351 |
} |
| 2352 |
|
| 2353 |
fn seq<I: IntoIterator<Item = Literal>>(it: I) -> Seq { |
| 2354 |
Seq::from_iter(it) |
| 2355 |
} |
| 2356 |
|
| 2357 |
fn infinite() -> (Seq, Seq) { |
| 2358 |
(Seq::infinite(), Seq::infinite()) |
| 2359 |
} |
| 2360 |
|
| 2361 |
fn inexact<I1, I2>(it1: I1, it2: I2) -> (Seq, Seq) |
| 2362 |
where |
| 2363 |
I1: IntoIterator<Item = Literal>, |
| 2364 |
I2: IntoIterator<Item = Literal>, |
| 2365 |
{ |
| 2366 |
(Seq::from_iter(it1), Seq::from_iter(it2)) |
| 2367 |
} |
| 2368 |
|
| 2369 |
fn exact<B: AsRef<[u8]>, I: IntoIterator<Item = B>>(it: I) -> (Seq, Seq) { |
| 2370 |
let s1 = Seq::new(it); |
| 2371 |
let s2 = s1.clone(); |
| 2372 |
(s1, s2) |
| 2373 |
} |
| 2374 |
|
| 2375 |
fn opt<B: AsRef<[u8]>, I: IntoIterator<Item = B>>(it: I) -> (Seq, Seq) { |
| 2376 |
let (mut p, mut s) = exact(it); |
| 2377 |
p.optimize_for_prefix_by_preference(); |
| 2378 |
s.optimize_for_suffix_by_preference(); |
| 2379 |
(p, s) |
| 2380 |
} |
| 2381 |
|
| 2382 |
#[test] |
| 2383 |
fn literal() { |
| 2384 |
assert_eq!(exact(["a"]), e("a")); |
| 2385 |
assert_eq!(exact(["aaaaa"]), e("aaaaa")); |
| 2386 |
assert_eq!(exact(["A", "a"]), e("(?i-u)a")); |
| 2387 |
assert_eq!(exact(["AB", "Ab", "aB", "ab"]), e("(?i-u)ab")); |
| 2388 |
assert_eq!(exact(["abC", "abc"]), e("ab(?i-u)c")); |
| 2389 |
|
| 2390 |
assert_eq!(exact([b"\xFF"]), e(r"(?-u:\xFF)")); |
| 2391 |
|
| 2392 |
#[cfg(feature = "unicode-case")] |
| 2393 |
{ |
| 2394 |
assert_eq!(exact(["☃"]), e("☃")); |
| 2395 |
assert_eq!(exact(["☃"]), e("(?i)☃")); |
| 2396 |
assert_eq!(exact(["☃☃☃☃☃"]), e("☃☃☃☃☃")); |
| 2397 |
|
| 2398 |
assert_eq!(exact(["Δ"]), e("Δ")); |
| 2399 |
assert_eq!(exact(["δ"]), e("δ")); |
| 2400 |
assert_eq!(exact(["Δ", "δ"]), e("(?i)Δ")); |
| 2401 |
assert_eq!(exact(["Δ", "δ"]), e("(?i)δ")); |
| 2402 |
|
| 2403 |
assert_eq!(exact(["S", "s", "ſ"]), e("(?i)S")); |
| 2404 |
assert_eq!(exact(["S", "s", "ſ"]), e("(?i)s")); |
| 2405 |
assert_eq!(exact(["S", "s", "ſ"]), e("(?i)ſ")); |
| 2406 |
} |
| 2407 |
|
| 2408 |
let letters = "ͱͳͷΐάέήίΰαβγδεζηθικλμνξοπρςστυφχψωϊϋ"; |
| 2409 |
assert_eq!(exact([letters]), e(letters)); |
| 2410 |
} |
| 2411 |
|
| 2412 |
#[test] |
| 2413 |
fn class() { |
| 2414 |
assert_eq!(exact(["a", "b", "c"]), e("[abc]")); |
| 2415 |
assert_eq!(exact(["a1b", "a2b", "a3b"]), e("a[123]b")); |
| 2416 |
assert_eq!(exact(["δ", "ε"]), e("[εδ]")); |
| 2417 |
#[cfg(feature = "unicode-case")] |
| 2418 |
{ |
| 2419 |
assert_eq!(exact(["Δ", "Ε", "δ", "ε", "ϵ"]), e(r"(?i)[εδ]")); |
| 2420 |
} |
| 2421 |
} |
| 2422 |
|
| 2423 |
#[test] |
| 2424 |
fn look() { |
| 2425 |
assert_eq!(exact(["ab"]), e(r"a\Ab")); |
| 2426 |
assert_eq!(exact(["ab"]), e(r"a\zb")); |
| 2427 |
assert_eq!(exact(["ab"]), e(r"a(?m:^)b")); |
| 2428 |
assert_eq!(exact(["ab"]), e(r"a(?m:$)b")); |
| 2429 |
assert_eq!(exact(["ab"]), e(r"a\bb")); |
| 2430 |
assert_eq!(exact(["ab"]), e(r"a\Bb")); |
| 2431 |
assert_eq!(exact(["ab"]), e(r"a(?-u:\b)b")); |
| 2432 |
assert_eq!(exact(["ab"]), e(r"a(?-u:\B)b")); |
| 2433 |
|
| 2434 |
assert_eq!(exact(["ab"]), e(r"^ab")); |
| 2435 |
assert_eq!(exact(["ab"]), e(r"$ab")); |
| 2436 |
assert_eq!(exact(["ab"]), e(r"(?m:^)ab")); |
| 2437 |
assert_eq!(exact(["ab"]), e(r"(?m:$)ab")); |
| 2438 |
assert_eq!(exact(["ab"]), e(r"\bab")); |
| 2439 |
assert_eq!(exact(["ab"]), e(r"\Bab")); |
| 2440 |
assert_eq!(exact(["ab"]), e(r"(?-u:\b)ab")); |
| 2441 |
assert_eq!(exact(["ab"]), e(r"(?-u:\B)ab")); |
| 2442 |
|
| 2443 |
assert_eq!(exact(["ab"]), e(r"ab^")); |
| 2444 |
assert_eq!(exact(["ab"]), e(r"ab$")); |
| 2445 |
assert_eq!(exact(["ab"]), e(r"ab(?m:^)")); |
| 2446 |
assert_eq!(exact(["ab"]), e(r"ab(?m:$)")); |
| 2447 |
assert_eq!(exact(["ab"]), e(r"ab\b")); |
| 2448 |
assert_eq!(exact(["ab"]), e(r"ab\B")); |
| 2449 |
assert_eq!(exact(["ab"]), e(r"ab(?-u:\b)")); |
| 2450 |
assert_eq!(exact(["ab"]), e(r"ab(?-u:\B)")); |
| 2451 |
|
| 2452 |
let expected = (seq([I("aZ"), E("ab")]), seq([I("Zb"), E("ab")])); |
| 2453 |
assert_eq!(expected, e(r"^aZ*b")); |
| 2454 |
} |
| 2455 |
|
| 2456 |
#[test] |
| 2457 |
fn repetition() { |
| 2458 |
assert_eq!(exact(["a", ""]), e(r"a?")); |
| 2459 |
assert_eq!(exact(["", "a"]), e(r"a??")); |
| 2460 |
assert_eq!(inexact([I("a"), E("")], [I("a"), E("")]), e(r"a*")); |
| 2461 |
assert_eq!(inexact([E(""), I("a")], [E(""), I("a")]), e(r"a*?")); |
| 2462 |
assert_eq!(inexact([I("a")], [I("a")]), e(r"a+")); |
| 2463 |
assert_eq!(inexact([I("a")], [I("a")]), e(r"(a+)+")); |
| 2464 |
|
| 2465 |
assert_eq!(exact(["ab"]), e(r"aZ{0}b")); |
| 2466 |
assert_eq!(exact(["aZb", "ab"]), e(r"aZ?b")); |
| 2467 |
assert_eq!(exact(["ab", "aZb"]), e(r"aZ??b")); |
| 2468 |
assert_eq!( |
| 2469 |
inexact([I("aZ"), E("ab")], [I("Zb"), E("ab")]), |
| 2470 |
e(r"aZ*b") |
| 2471 |
); |
| 2472 |
assert_eq!( |
| 2473 |
inexact([E("ab"), I("aZ")], [E("ab"), I("Zb")]), |
| 2474 |
e(r"aZ*?b") |
| 2475 |
); |
| 2476 |
assert_eq!(inexact([I("aZ")], [I("Zb")]), e(r"aZ+b")); |
| 2477 |
assert_eq!(inexact([I("aZ")], [I("Zb")]), e(r"aZ+?b")); |
| 2478 |
|
| 2479 |
assert_eq!(exact(["aZZb"]), e(r"aZ{2}b")); |
| 2480 |
assert_eq!(inexact([I("aZZ")], [I("ZZb")]), e(r"aZ{2,3}b")); |
| 2481 |
|
| 2482 |
assert_eq!(exact(["abc", ""]), e(r"(abc)?")); |
| 2483 |
assert_eq!(exact(["", "abc"]), e(r"(abc)??")); |
| 2484 |
|
| 2485 |
assert_eq!(inexact([I("a"), E("b")], [I("ab"), E("b")]), e(r"a*b")); |
| 2486 |
assert_eq!(inexact([E("b"), I("a")], [E("b"), I("ab")]), e(r"a*?b")); |
| 2487 |
assert_eq!(inexact([I("ab")], [I("b")]), e(r"ab+")); |
| 2488 |
assert_eq!(inexact([I("a"), I("b")], [I("b")]), e(r"a*b+")); |
| 2489 |
|
| 2490 |
// FIXME: The suffixes for this don't look quite right to me. I think |
| 2491 |
// the right suffixes would be: [I(ac), I(bc), E(c)]. The main issue I |
| 2492 |
// think is that suffixes are computed by iterating over concatenations |
| 2493 |
// in reverse, and then [bc, ac, c] ordering is indeed correct from |
| 2494 |
// that perspective. We also test a few more equivalent regexes, and |
| 2495 |
// we get the same result, so it is consistent at least I suppose. |
| 2496 |
// |
| 2497 |
// The reason why this isn't an issue is that it only messes up |
| 2498 |
// preference order, and currently, suffixes are never used in a |
| 2499 |
// context where preference order matters. For prefixes it matters |
| 2500 |
// because we sometimes want to use prefilters without confirmation |
| 2501 |
// when all of the literals are exact (and there's no look-around). But |
| 2502 |
// we never do that for suffixes. Any time we use suffixes, we always |
| 2503 |
// include a confirmation step. If that ever changes, then it's likely |
| 2504 |
// this bug will need to be fixed, but last time I looked, it appears |
| 2505 |
// hard to do so. |
| 2506 |
assert_eq!( |
| 2507 |
inexact([I("a"), I("b"), E("c")], [I("bc"), I("ac"), E("c")]), |
| 2508 |
e(r"a*b*c") |
| 2509 |
); |
| 2510 |
assert_eq!( |
| 2511 |
inexact([I("a"), I("b"), E("c")], [I("bc"), I("ac"), E("c")]), |
| 2512 |
e(r"(a+)?(b+)?c") |
| 2513 |
); |
| 2514 |
assert_eq!( |
| 2515 |
inexact([I("a"), I("b"), E("c")], [I("bc"), I("ac"), E("c")]), |
| 2516 |
e(r"(a+|)(b+|)c") |
| 2517 |
); |
| 2518 |
// A few more similarish but not identical regexes. These may have a |
| 2519 |
// similar problem as above. |
| 2520 |
assert_eq!( |
| 2521 |
inexact( |
| 2522 |
[I("a"), I("b"), I("c"), E("")], |
| 2523 |
[I("c"), I("b"), I("a"), E("")] |
| 2524 |
), |
| 2525 |
e(r"a*b*c*") |
| 2526 |
); |
| 2527 |
assert_eq!(inexact([I("a"), I("b"), I("c")], [I("c")]), e(r"a*b*c+")); |
| 2528 |
assert_eq!(inexact([I("a"), I("b")], [I("bc")]), e(r"a*b+c")); |
| 2529 |
assert_eq!(inexact([I("a"), I("b")], [I("c"), I("b")]), e(r"a*b+c*")); |
| 2530 |
assert_eq!(inexact([I("ab"), E("a")], [I("b"), E("a")]), e(r"ab*")); |
| 2531 |
assert_eq!( |
| 2532 |
inexact([I("ab"), E("ac")], [I("bc"), E("ac")]), |
| 2533 |
e(r"ab*c") |
| 2534 |
); |
| 2535 |
assert_eq!(inexact([I("ab")], [I("b")]), e(r"ab+")); |
| 2536 |
assert_eq!(inexact([I("ab")], [I("bc")]), e(r"ab+c")); |
| 2537 |
|
| 2538 |
assert_eq!( |
| 2539 |
inexact([I("z"), E("azb")], [I("zazb"), E("azb")]), |
| 2540 |
e(r"z*azb") |
| 2541 |
); |
| 2542 |
|
| 2543 |
let expected = |
| 2544 |
exact(["aaa", "aab", "aba", "abb", "baa", "bab", "bba", "bbb"]); |
| 2545 |
assert_eq!(expected, e(r"[ab]{3}")); |
| 2546 |
let expected = inexact( |
| 2547 |
[ |
| 2548 |
I("aaa"), |
| 2549 |
I("aab"), |
| 2550 |
I("aba"), |
| 2551 |
I("abb"), |
| 2552 |
I("baa"), |
| 2553 |
I("bab"), |
| 2554 |
I("bba"), |
| 2555 |
I("bbb"), |
| 2556 |
], |
| 2557 |
[ |
| 2558 |
I("aaa"), |
| 2559 |
I("aab"), |
| 2560 |
I("aba"), |
| 2561 |
I("abb"), |
| 2562 |
I("baa"), |
| 2563 |
I("bab"), |
| 2564 |
I("bba"), |
| 2565 |
I("bbb"), |
| 2566 |
], |
| 2567 |
); |
| 2568 |
assert_eq!(expected, e(r"[ab]{3,4}")); |
| 2569 |
} |
| 2570 |
|
| 2571 |
#[test] |
| 2572 |
fn concat() { |
| 2573 |
let empty: [&str; 0] = []; |
| 2574 |
|
| 2575 |
assert_eq!(exact(["abcxyz"]), e(r"abc()xyz")); |
| 2576 |
assert_eq!(exact(["abcxyz"]), e(r"(abc)(xyz)")); |
| 2577 |
assert_eq!(exact(["abcmnoxyz"]), e(r"abc()mno()xyz")); |
| 2578 |
assert_eq!(exact(empty), e(r"abc[a&&b]xyz")); |
| 2579 |
assert_eq!(exact(["abcxyz"]), e(r"abc[a&&b]*xyz")); |
| 2580 |
} |
| 2581 |
|
| 2582 |
#[test] |
| 2583 |
fn alternation() { |
| 2584 |
assert_eq!(exact(["abc", "mno", "xyz"]), e(r"abc|mno|xyz")); |
| 2585 |
assert_eq!( |
| 2586 |
inexact( |
| 2587 |
[E("abc"), I("mZ"), E("mo"), E("xyz")], |
| 2588 |
[E("abc"), I("Zo"), E("mo"), E("xyz")] |
| 2589 |
), |
| 2590 |
e(r"abc|mZ*o|xyz") |
| 2591 |
); |
| 2592 |
assert_eq!(exact(["abc", "xyz"]), e(r"abc|M[a&&b]N|xyz")); |
| 2593 |
assert_eq!(exact(["abc", "MN", "xyz"]), e(r"abc|M[a&&b]*N|xyz")); |
| 2594 |
|
| 2595 |
assert_eq!(exact(["aaa", "aaaaa"]), e(r"(?:|aa)aaa")); |
| 2596 |
assert_eq!( |
| 2597 |
inexact( |
| 2598 |
[I("aaa"), E(""), I("aaaaa"), E("aa")], |
| 2599 |
[I("aaa"), E(""), E("aa")] |
| 2600 |
), |
| 2601 |
e(r"(?:|aa)(?:aaa)*") |
| 2602 |
); |
| 2603 |
assert_eq!( |
| 2604 |
inexact( |
| 2605 |
[E(""), I("aaa"), E("aa"), I("aaaaa")], |
| 2606 |
[E(""), I("aaa"), E("aa")] |
| 2607 |
), |
| 2608 |
e(r"(?:|aa)(?:aaa)*?") |
| 2609 |
); |
| 2610 |
|
| 2611 |
assert_eq!( |
| 2612 |
inexact([E("a"), I("b"), E("")], [E("a"), I("b"), E("")]), |
| 2613 |
e(r"a|b*") |
| 2614 |
); |
| 2615 |
assert_eq!(inexact([E("a"), I("b")], [E("a"), I("b")]), e(r"a|b+")); |
| 2616 |
|
| 2617 |
assert_eq!( |
| 2618 |
inexact([I("a"), E("b"), E("c")], [I("ab"), E("b"), E("c")]), |
| 2619 |
e(r"a*b|c") |
| 2620 |
); |
| 2621 |
|
| 2622 |
assert_eq!( |
| 2623 |
inexact( |
| 2624 |
[E("a"), E("b"), I("c"), E("")], |
| 2625 |
[E("a"), E("b"), I("c"), E("")] |
| 2626 |
), |
| 2627 |
e(r"a|(?:b|c*)") |
| 2628 |
); |
| 2629 |
|
| 2630 |
assert_eq!( |
| 2631 |
inexact( |
| 2632 |
[I("a"), I("b"), E("c"), I("a"), I("ab"), E("c")], |
| 2633 |
[I("ac"), I("bc"), E("c"), I("ac"), I("abc"), E("c")], |
| 2634 |
), |
| 2635 |
e(r"(a|b)*c|(a|ab)*c") |
| 2636 |
); |
| 2637 |
|
| 2638 |
assert_eq!( |
| 2639 |
exact(["abef", "abgh", "cdef", "cdgh"]), |
| 2640 |
e(r"(ab|cd)(ef|gh)") |
| 2641 |
); |
| 2642 |
assert_eq!( |
| 2643 |
exact([ |
| 2644 |
"abefij", "abefkl", "abghij", "abghkl", "cdefij", "cdefkl", |
| 2645 |
"cdghij", "cdghkl", |
| 2646 |
]), |
| 2647 |
e(r"(ab|cd)(ef|gh)(ij|kl)") |
| 2648 |
); |
| 2649 |
|
| 2650 |
assert_eq!(inexact([E("abab")], [E("abab")]), e(r"(ab){2}")); |
| 2651 |
|
| 2652 |
assert_eq!(inexact([I("abab")], [I("abab")]), e(r"(ab){2,3}")); |
| 2653 |
|
| 2654 |
assert_eq!(inexact([I("abab")], [I("abab")]), e(r"(ab){2,}")); |
| 2655 |
} |
| 2656 |
|
| 2657 |
#[test] |
| 2658 |
fn impossible() { |
| 2659 |
let empty: [&str; 0] = []; |
| 2660 |
|
| 2661 |
assert_eq!(exact(empty), e(r"[a&&b]")); |
| 2662 |
assert_eq!(exact(empty), e(r"a[a&&b]")); |
| 2663 |
assert_eq!(exact(empty), e(r"[a&&b]b")); |
| 2664 |
assert_eq!(exact(empty), e(r"a[a&&b]b")); |
| 2665 |
assert_eq!(exact(["a", "b"]), e(r"a|[a&&b]|b")); |
| 2666 |
assert_eq!(exact(["a", "b"]), e(r"a|c[a&&b]|b")); |
| 2667 |
assert_eq!(exact(["a", "b"]), e(r"a|[a&&b]d|b")); |
| 2668 |
assert_eq!(exact(["a", "b"]), e(r"a|c[a&&b]d|b")); |
| 2669 |
assert_eq!(exact([""]), e(r"[a&&b]*")); |
| 2670 |
assert_eq!(exact(["MN"]), e(r"M[a&&b]*N")); |
| 2671 |
} |
| 2672 |
|
| 2673 |
// This tests patterns that contain something that defeats literal |
| 2674 |
// detection, usually because it would blow some limit on the total number |
| 2675 |
// of literals that can be returned. |
| 2676 |
// |
| 2677 |
// The main idea is that when literal extraction sees something that |
| 2678 |
// it knows will blow a limit, it replaces it with a marker that says |
| 2679 |
// "any literal will match here." While not necessarily true, the |
| 2680 |
// over-estimation is just fine for the purposes of literal extraction, |
| 2681 |
// because the imprecision doesn't matter: too big is too big. |
| 2682 |
// |
| 2683 |
// This is one of the trickier parts of literal extraction, since we need |
| 2684 |
// to make sure all of our literal extraction operations correctly compose |
| 2685 |
// with the markers. |
| 2686 |
#[test] |
| 2687 |
fn anything() { |
| 2688 |
assert_eq!(infinite(), e(r".")); |
| 2689 |
assert_eq!(infinite(), e(r"(?s).")); |
| 2690 |
assert_eq!(infinite(), e(r"[A-Za-z]")); |
| 2691 |
assert_eq!(infinite(), e(r"[A-Z]")); |
| 2692 |
assert_eq!(exact([""]), e(r"[A-Z]{0}")); |
| 2693 |
assert_eq!(infinite(), e(r"[A-Z]?")); |
| 2694 |
assert_eq!(infinite(), e(r"[A-Z]*")); |
| 2695 |
assert_eq!(infinite(), e(r"[A-Z]+")); |
| 2696 |
assert_eq!((seq([I("1")]), Seq::infinite()), e(r"1[A-Z]")); |
| 2697 |
assert_eq!((seq([I("1")]), seq([I("2")])), e(r"1[A-Z]2")); |
| 2698 |
assert_eq!((Seq::infinite(), seq([I("123")])), e(r"[A-Z]+123")); |
| 2699 |
assert_eq!(infinite(), e(r"[A-Z]+123[A-Z]+")); |
| 2700 |
assert_eq!(infinite(), e(r"1|[A-Z]|3")); |
| 2701 |
assert_eq!( |
| 2702 |
(seq([E("1"), I("2"), E("3")]), Seq::infinite()), |
| 2703 |
e(r"1|2[A-Z]|3"), |
| 2704 |
); |
| 2705 |
assert_eq!( |
| 2706 |
(Seq::infinite(), seq([E("1"), I("2"), E("3")])), |
| 2707 |
e(r"1|[A-Z]2|3"), |
| 2708 |
); |
| 2709 |
assert_eq!( |
| 2710 |
(seq([E("1"), I("2"), E("4")]), seq([E("1"), I("3"), E("4")])), |
| 2711 |
e(r"1|2[A-Z]3|4"), |
| 2712 |
); |
| 2713 |
assert_eq!((Seq::infinite(), seq([I("2")])), e(r"(?:|1)[A-Z]2")); |
| 2714 |
assert_eq!(inexact([I("a")], [I("z")]), e(r"a.z")); |
| 2715 |
} |
| 2716 |
|
| 2717 |
// Like the 'anything' test, but it uses smaller limits in order to test |
| 2718 |
// the logic for effectively aborting literal extraction when the seqs get |
| 2719 |
// too big. |
| 2720 |
#[test] |
| 2721 |
fn anything_small_limits() { |
| 2722 |
fn prefixes(pattern: &str) -> Seq { |
| 2723 |
Extractor::new() |
| 2724 |
.kind(ExtractKind::Prefix) |
| 2725 |
.limit_total(10) |
| 2726 |
.extract(&parse(pattern)) |
| 2727 |
} |
| 2728 |
|
| 2729 |
fn suffixes(pattern: &str) -> Seq { |
| 2730 |
Extractor::new() |
| 2731 |
.kind(ExtractKind::Suffix) |
| 2732 |
.limit_total(10) |
| 2733 |
.extract(&parse(pattern)) |
| 2734 |
} |
| 2735 |
|
| 2736 |
fn e(pattern: &str) -> (Seq, Seq) { |
| 2737 |
(prefixes(pattern), suffixes(pattern)) |
| 2738 |
} |
| 2739 |
|
| 2740 |
assert_eq!( |
| 2741 |
( |
| 2742 |
seq([ |
| 2743 |
I("aaa"), |
| 2744 |
I("aab"), |
| 2745 |
I("aba"), |
| 2746 |
I("abb"), |
| 2747 |
I("baa"), |
| 2748 |
I("bab"), |
| 2749 |
I("bba"), |
| 2750 |
I("bbb") |
| 2751 |
]), |
| 2752 |
seq([ |
| 2753 |
I("aaa"), |
| 2754 |
I("aab"), |
| 2755 |
I("aba"), |
| 2756 |
I("abb"), |
| 2757 |
I("baa"), |
| 2758 |
I("bab"), |
| 2759 |
I("bba"), |
| 2760 |
I("bbb") |
| 2761 |
]) |
| 2762 |
), |
| 2763 |
e(r"[ab]{3}{3}") |
| 2764 |
); |
| 2765 |
|
| 2766 |
assert_eq!(infinite(), e(r"ab|cd|ef|gh|ij|kl|mn|op|qr|st|uv|wx|yz")); |
| 2767 |
} |
| 2768 |
|
| 2769 |
#[test] |
| 2770 |
fn empty() { |
| 2771 |
assert_eq!(exact([""]), e(r"")); |
| 2772 |
assert_eq!(exact([""]), e(r"^")); |
| 2773 |
assert_eq!(exact([""]), e(r"$")); |
| 2774 |
assert_eq!(exact([""]), e(r"(?m:^)")); |
| 2775 |
assert_eq!(exact([""]), e(r"(?m:$)")); |
| 2776 |
assert_eq!(exact([""]), e(r"\b")); |
| 2777 |
assert_eq!(exact([""]), e(r"\B")); |
| 2778 |
assert_eq!(exact([""]), e(r"(?-u:\b)")); |
| 2779 |
assert_eq!(exact([""]), e(r"(?-u:\B)")); |
| 2780 |
} |
| 2781 |
|
| 2782 |
#[test] |
| 2783 |
fn odds_and_ends() { |
| 2784 |
assert_eq!((Seq::infinite(), seq([I("a")])), e(r".a")); |
| 2785 |
assert_eq!((seq([I("a")]), Seq::infinite()), e(r"a.")); |
| 2786 |
assert_eq!(infinite(), e(r"a|.")); |
| 2787 |
assert_eq!(infinite(), e(r".|a")); |
| 2788 |
|
| 2789 |
let pat = r"M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]"; |
| 2790 |
let expected = inexact( |
| 2791 |
["Mo'am", "Moam", "Mu'am", "Muam"].map(I), |
| 2792 |
[ |
| 2793 |
"ddafi", "ddafy", "dhafi", "dhafy", "dzafi", "dzafy", "dafi", |
| 2794 |
"dafy", "tdafi", "tdafy", "thafi", "thafy", "tzafi", "tzafy", |
| 2795 |
"tafi", "tafy", "zdafi", "zdafy", "zhafi", "zhafy", "zzafi", |
| 2796 |
"zzafy", "zafi", "zafy", |
| 2797 |
] |
| 2798 |
.map(I), |
| 2799 |
); |
| 2800 |
assert_eq!(expected, e(pat)); |
| 2801 |
|
| 2802 |
assert_eq!( |
| 2803 |
(seq(["fn is_", "fn as_"].map(I)), Seq::infinite()), |
| 2804 |
e(r"fn is_([A-Z]+)|fn as_([A-Z]+)"), |
| 2805 |
); |
| 2806 |
assert_eq!( |
| 2807 |
inexact([I("foo")], [I("quux")]), |
| 2808 |
e(r"foo[A-Z]+bar[A-Z]+quux") |
| 2809 |
); |
| 2810 |
assert_eq!(infinite(), e(r"[A-Z]+bar[A-Z]+")); |
| 2811 |
assert_eq!( |
| 2812 |
exact(["Sherlock Holmes"]), |
| 2813 |
e(r"(?m)^Sherlock Holmes|Sherlock Holmes$") |
| 2814 |
); |
| 2815 |
|
| 2816 |
assert_eq!(exact(["sa", "sb"]), e(r"\bs(?:[ab])")); |
| 2817 |
} |
| 2818 |
|
| 2819 |
// This tests a specific regex along with some heuristic steps to reduce |
| 2820 |
// the sequences extracted. This is meant to roughly correspond to the |
| 2821 |
// types of heuristics used to shrink literal sets in practice. (Shrinking |
| 2822 |
// is done because you want to balance "spend too much work looking for |
| 2823 |
// too many literals" and "spend too much work processing false positive |
| 2824 |
// matches from short literals.") |
| 2825 |
#[test] |
| 2826 |
#[cfg(feature = "unicode-case")] |
| 2827 |
fn holmes() { |
| 2828 |
let expected = inexact( |
| 2829 |
["HOL", "HOl", "HoL", "Hol", "hOL", "hOl", "hoL", "hol"].map(I), |
| 2830 |
[ |
| 2831 |
"MES", "MEs", "Eſ", "MeS", "Mes", "eſ", "mES", "mEs", "meS", |
| 2832 |
"mes", |
| 2833 |
] |
| 2834 |
.map(I), |
| 2835 |
); |
| 2836 |
let (mut prefixes, mut suffixes) = e(r"(?i)Holmes"); |
| 2837 |
prefixes.keep_first_bytes(3); |
| 2838 |
suffixes.keep_last_bytes(3); |
| 2839 |
prefixes.minimize_by_preference(); |
| 2840 |
suffixes.minimize_by_preference(); |
| 2841 |
assert_eq!(expected, (prefixes, suffixes)); |
| 2842 |
} |
| 2843 |
|
| 2844 |
// This tests that we get some kind of literals extracted for a beefier |
| 2845 |
// alternation with case insensitive mode enabled. At one point during |
| 2846 |
// development, this returned nothing, and motivated some special case |
| 2847 |
// code in Extractor::union to try and trim down the literal sequences |
| 2848 |
// if the union would blow the limits set. |
| 2849 |
#[test] |
| 2850 |
#[cfg(feature = "unicode-case")] |
| 2851 |
fn holmes_alt() { |
| 2852 |
let mut pre = |
| 2853 |
prefixes(r"(?i)Sherlock|Holmes|Watson|Irene|Adler|John|Baker"); |
| 2854 |
assert!(pre.len().unwrap() > 0); |
| 2855 |
pre.optimize_for_prefix_by_preference(); |
| 2856 |
assert!(pre.len().unwrap() > 0); |
| 2857 |
} |
| 2858 |
|
| 2859 |
// See: https://github.com/rust-lang/regex/security/advisories/GHSA-m5pq-gvj9-9vr8 |
| 2860 |
// See: CVE-2022-24713 |
| 2861 |
// |
| 2862 |
// We test this here to ensure literal extraction completes in reasonable |
| 2863 |
// time and isn't materially impacted by these sorts of pathological |
| 2864 |
// repeats. |
| 2865 |
#[test] |
| 2866 |
fn crazy_repeats() { |
| 2867 |
assert_eq!(inexact([E("")], [E("")]), e(r"(?:){4294967295}")); |
| 2868 |
assert_eq!( |
| 2869 |
inexact([E("")], [E("")]), |
| 2870 |
e(r"(?:){64}{64}{64}{64}{64}{64}") |
| 2871 |
); |
| 2872 |
assert_eq!(inexact([E("")], [E("")]), e(r"x{0}{4294967295}")); |
| 2873 |
assert_eq!(inexact([E("")], [E("")]), e(r"(?:|){4294967295}")); |
| 2874 |
|
| 2875 |
assert_eq!( |
| 2876 |
inexact([E("")], [E("")]), |
| 2877 |
e(r"(?:){8}{8}{8}{8}{8}{8}{8}{8}{8}{8}{8}{8}{8}{8}") |
| 2878 |
); |
| 2879 |
let repa = "a".repeat(100); |
| 2880 |
assert_eq!( |
| 2881 |
inexact([I(&repa)], [I(&repa)]), |
| 2882 |
e(r"a{8}{8}{8}{8}{8}{8}{8}{8}{8}{8}{8}{8}{8}{8}") |
| 2883 |
); |
| 2884 |
} |
| 2885 |
|
| 2886 |
#[test] |
| 2887 |
fn huge() { |
| 2888 |
let pat = r#"(?-u) |
| 2889 |
2(?: |
| 2890 |
[45]\d{3}| |
| 2891 |
7(?: |
| 2892 |
1[0-267]| |
| 2893 |
2[0-289]| |
| 2894 |
3[0-29]| |
| 2895 |
4[01]| |
| 2896 |
5[1-3]| |
| 2897 |
6[013]| |
| 2898 |
7[0178]| |
| 2899 |
91 |
| 2900 |
)| |
| 2901 |
8(?: |
| 2902 |
0[125]| |
| 2903 |
[139][1-6]| |
| 2904 |
2[0157-9]| |
| 2905 |
41| |
| 2906 |
6[1-35]| |
| 2907 |
7[1-5]| |
| 2908 |
8[1-8]| |
| 2909 |
90 |
| 2910 |
)| |
| 2911 |
9(?: |
| 2912 |
0[0-2]| |
| 2913 |
1[0-4]| |
| 2914 |
2[568]| |
| 2915 |
3[3-6]| |
| 2916 |
5[5-7]| |
| 2917 |
6[0167]| |
| 2918 |
7[15]| |
| 2919 |
8[0146-9] |
| 2920 |
) |
| 2921 |
)\d{4}| |
| 2922 |
3(?: |
| 2923 |
12?[5-7]\d{2}| |
| 2924 |
0(?: |
| 2925 |
2(?: |
| 2926 |
[025-79]\d| |
| 2927 |
[348]\d{1,2} |
| 2928 |
)| |
| 2929 |
3(?: |
| 2930 |
[2-4]\d| |
| 2931 |
[56]\d? |
| 2932 |
) |
| 2933 |
)| |
| 2934 |
2(?: |
| 2935 |
1\d{2}| |
| 2936 |
2(?: |
| 2937 |
[12]\d| |
| 2938 |
[35]\d{1,2}| |
| 2939 |
4\d? |
| 2940 |
) |
| 2941 |
)| |
| 2942 |
3(?: |
| 2943 |
1\d{2}| |
| 2944 |
2(?: |
| 2945 |
[2356]\d| |
| 2946 |
4\d{1,2} |
| 2947 |
) |
| 2948 |
)| |
| 2949 |
4(?: |
| 2950 |
1\d{2}| |
| 2951 |
2(?: |
| 2952 |
2\d{1,2}| |
| 2953 |
[47]| |
| 2954 |
5\d{2} |
| 2955 |
) |
| 2956 |
)| |
| 2957 |
5(?: |
| 2958 |
1\d{2}| |
| 2959 |
29 |
| 2960 |
)| |
| 2961 |
[67]1\d{2}| |
| 2962 |
8(?: |
| 2963 |
1\d{2}| |
| 2964 |
2(?: |
| 2965 |
2\d{2}| |
| 2966 |
3| |
| 2967 |
4\d |
| 2968 |
) |
| 2969 |
) |
| 2970 |
)\d{3}| |
| 2971 |
4(?: |
| 2972 |
0(?: |
| 2973 |
2(?: |
| 2974 |
[09]\d| |
| 2975 |
7 |
| 2976 |
)| |
| 2977 |
33\d{2} |
| 2978 |
)| |
| 2979 |
1\d{3}| |
| 2980 |
2(?: |
| 2981 |
1\d{2}| |
| 2982 |
2(?: |
| 2983 |
[25]\d?| |
| 2984 |
[348]\d| |
| 2985 |
[67]\d{1,2} |
| 2986 |
) |
| 2987 |
)| |
| 2988 |
3(?: |
| 2989 |
1\d{2}(?: |
| 2990 |
\d{2} |
| 2991 |
)?| |
| 2992 |
2(?: |
| 2993 |
[045]\d| |
| 2994 |
[236-9]\d{1,2} |
| 2995 |
)| |
| 2996 |
32\d{2} |
| 2997 |
)| |
| 2998 |
4(?: |
| 2999 |
[18]\d{2}| |
| 3000 |
2(?: |
| 3001 |
[2-46]\d{2}| |
| 3002 |
3 |
| 3003 |
)| |
| 3004 |
5[25]\d{2} |
| 3005 |
)| |
| 3006 |
5(?: |
| 3007 |
1\d{2}| |
| 3008 |
2(?: |
| 3009 |
3\d| |
| 3010 |
5 |
| 3011 |
) |
| 3012 |
)| |
| 3013 |
6(?: |
| 3014 |
[18]\d{2}| |
| 3015 |
2(?: |
| 3016 |
3(?: |
| 3017 |
\d{2} |
| 3018 |
)?| |
| 3019 |
[46]\d{1,2}| |
| 3020 |
5\d{2}| |
| 3021 |
7\d |
| 3022 |
)| |
| 3023 |
5(?: |
| 3024 |
3\d?| |
| 3025 |
4\d| |
| 3026 |
[57]\d{1,2}| |
| 3027 |
6\d{2}| |
| 3028 |
8 |
| 3029 |
) |
| 3030 |
)| |
| 3031 |
71\d{2}| |
| 3032 |
8(?: |
| 3033 |
[18]\d{2}| |
| 3034 |
23\d{2}| |
| 3035 |
54\d{2} |
| 3036 |
)| |
| 3037 |
9(?: |
| 3038 |
[18]\d{2}| |
| 3039 |
2[2-5]\d{2}| |
| 3040 |
53\d{1,2} |
| 3041 |
) |
| 3042 |
)\d{3}| |
| 3043 |
5(?: |
| 3044 |
02[03489]\d{2}| |
| 3045 |
1\d{2}| |
| 3046 |
2(?: |
| 3047 |
1\d{2}| |
| 3048 |
2(?: |
| 3049 |
2(?: |
| 3050 |
\d{2} |
| 3051 |
)?| |
| 3052 |
[457]\d{2} |
| 3053 |
) |
| 3054 |
)| |
| 3055 |
3(?: |
| 3056 |
1\d{2}| |
| 3057 |
2(?: |
| 3058 |
[37](?: |
| 3059 |
\d{2} |
| 3060 |
)?| |
| 3061 |
[569]\d{2} |
| 3062 |
) |
| 3063 |
)| |
| 3064 |
4(?: |
| 3065 |
1\d{2}| |
| 3066 |
2[46]\d{2} |
| 3067 |
)| |
| 3068 |
5(?: |
| 3069 |
1\d{2}| |
| 3070 |
26\d{1,2} |
| 3071 |
)| |
| 3072 |
6(?: |
| 3073 |
[18]\d{2}| |
| 3074 |
2| |
| 3075 |
53\d{2} |
| 3076 |
)| |
| 3077 |
7(?: |
| 3078 |
1| |
| 3079 |
24 |
| 3080 |
)\d{2}| |
| 3081 |
8(?: |
| 3082 |
1| |
| 3083 |
26 |
| 3084 |
)\d{2}| |
| 3085 |
91\d{2} |
| 3086 |
)\d{3}| |
| 3087 |
6(?: |
| 3088 |
0(?: |
| 3089 |
1\d{2}| |
| 3090 |
2(?: |
| 3091 |
3\d{2}| |
| 3092 |
4\d{1,2} |
| 3093 |
) |
| 3094 |
)| |
| 3095 |
2(?: |
| 3096 |
2[2-5]\d{2}| |
| 3097 |
5(?: |
| 3098 |
[3-5]\d{2}| |
| 3099 |
7 |
| 3100 |
)| |
| 3101 |
8\d{2} |
| 3102 |
)| |
| 3103 |
3(?: |
| 3104 |
1| |
| 3105 |
2[3478] |
| 3106 |
)\d{2}| |
| 3107 |
4(?: |
| 3108 |
1| |
| 3109 |
2[34] |
| 3110 |
)\d{2}| |
| 3111 |
5(?: |
| 3112 |
1| |
| 3113 |
2[47] |
| 3114 |
)\d{2}| |
| 3115 |
6(?: |
| 3116 |
[18]\d{2}| |
| 3117 |
6(?: |
| 3118 |
2(?: |
| 3119 |
2\d| |
| 3120 |
[34]\d{2} |
| 3121 |
)| |
| 3122 |
5(?: |
| 3123 |
[24]\d{2}| |
| 3124 |
3\d| |
| 3125 |
5\d{1,2} |
| 3126 |
) |
| 3127 |
) |
| 3128 |
)| |
| 3129 |
72[2-5]\d{2}| |
| 3130 |
8(?: |
| 3131 |
1\d{2}| |
| 3132 |
2[2-5]\d{2} |
| 3133 |
)| |
| 3134 |
9(?: |
| 3135 |
1\d{2}| |
| 3136 |
2[2-6]\d{2} |
| 3137 |
) |
| 3138 |
)\d{3}| |
| 3139 |
7(?: |
| 3140 |
(?: |
| 3141 |
02| |
| 3142 |
[3-589]1| |
| 3143 |
6[12]| |
| 3144 |
72[24] |
| 3145 |
)\d{2}| |
| 3146 |
21\d{3}| |
| 3147 |
32 |
| 3148 |
)\d{3}| |
| 3149 |
8(?: |
| 3150 |
(?: |
| 3151 |
4[12]| |
| 3152 |
[5-7]2| |
| 3153 |
1\d? |
| 3154 |
)| |
| 3155 |
(?: |
| 3156 |
0| |
| 3157 |
3[12]| |
| 3158 |
[5-7]1| |
| 3159 |
217 |
| 3160 |
)\d |
| 3161 |
)\d{4}| |
| 3162 |
9(?: |
| 3163 |
[35]1| |
| 3164 |
(?: |
| 3165 |
[024]2| |
| 3166 |
81 |
| 3167 |
)\d| |
| 3168 |
(?: |
| 3169 |
1| |
| 3170 |
[24]1 |
| 3171 |
)\d{2} |
| 3172 |
)\d{3} |
| 3173 |
"#; |
| 3174 |
// TODO: This is a good candidate of a seq of literals that could be |
| 3175 |
// shrunk quite a bit and still be very productive with respect to |
| 3176 |
// literal optimizations. |
| 3177 |
let (prefixes, suffixes) = e(pat); |
| 3178 |
assert!(!suffixes.is_finite()); |
| 3179 |
assert_eq!(Some(243), prefixes.len()); |
| 3180 |
} |
| 3181 |
|
| 3182 |
#[test] |
| 3183 |
fn optimize() { |
| 3184 |
// This gets a common prefix that isn't too short. |
| 3185 |
let (p, s) = |
| 3186 |
opt(["foobarfoobar", "foobar", "foobarzfoobar", "foobarfoobar"]); |
| 3187 |
assert_eq!(seq([I("foobar")]), p); |
| 3188 |
assert_eq!(seq([I("foobar")]), s); |
| 3189 |
|
| 3190 |
// This also finds a common prefix, but since it's only one byte, it |
| 3191 |
// prefers the multiple literals. |
| 3192 |
let (p, s) = opt(["abba", "akka", "abccba"]); |
| 3193 |
assert_eq!(exact(["abba", "akka", "abccba"]), (p, s)); |
| 3194 |
|
| 3195 |
let (p, s) = opt(["sam", "samwise"]); |
| 3196 |
assert_eq!((seq([E("sam")]), seq([E("sam"), E("samwise")])), (p, s)); |
| 3197 |
|
| 3198 |
// The empty string is poisonous, so our seq becomes infinite, even |
| 3199 |
// though all literals are exact. |
| 3200 |
let (p, s) = opt(["foobarfoo", "foo", "", "foozfoo", "foofoo"]); |
| 3201 |
assert!(!p.is_finite()); |
| 3202 |
assert!(!s.is_finite()); |
| 3203 |
|
| 3204 |
// A space is also poisonous, so our seq becomes infinite. But this |
| 3205 |
// only gets triggered when we don't have a completely exact sequence. |
| 3206 |
// When the sequence is exact, spaces are okay, since we presume that |
| 3207 |
// any prefilter will match a space more quickly than the regex engine. |
| 3208 |
// (When the sequence is exact, there's a chance of the prefilter being |
| 3209 |
// used without needing the regex engine at all.) |
| 3210 |
let mut p = seq([E("foobarfoo"), I("foo"), E(" "), E("foofoo")]); |
| 3211 |
p.optimize_for_prefix_by_preference(); |
| 3212 |
assert!(!p.is_finite()); |
| 3213 |
} |
| 3214 |
} |