| 1 |
/*! |
| 2 |
A DFA that can return spans for matching capturing groups. |
| 3 |
|
| 4 |
This module is the home of a [one-pass DFA](DFA). |
| 5 |
|
| 6 |
This module also contains a [`Builder`] and a [`Config`] for building and |
| 7 |
configuring a one-pass DFA. |
| 8 |
*/ |
| 9 |
|
| 10 |
// A note on naming and credit: |
| 11 |
// |
| 12 |
// As far as I know, Russ Cox came up with the practical vision and |
| 13 |
// implementation of a "one-pass regex engine." He mentions and describes it |
| 14 |
// briefly in the third article of his regexp article series: |
| 15 |
// https://swtch.com/~rsc/regexp/regexp3.html |
| 16 |
// |
| 17 |
// Cox's implementation is in RE2, and the implementation below is most |
| 18 |
// heavily inspired by RE2's. The key thing they have in common is that |
| 19 |
// their transitions are defined over an alphabet of bytes. In contrast, |
| 20 |
// Go's regex engine also has a one-pass engine, but its transitions are |
| 21 |
// more firmly rooted on Unicode codepoints. The ideas are the same, but the |
| 22 |
// implementations are different. |
| 23 |
// |
| 24 |
// RE2 tends to call this a "one-pass NFA." Here, we call it a "one-pass DFA." |
| 25 |
// They're both true in their own ways: |
| 26 |
// |
| 27 |
// * The "one-pass" criterion is generally a property of the NFA itself. In |
| 28 |
// particular, it is said that an NFA is one-pass if, after each byte of input |
| 29 |
// during a search, there is at most one "VM thread" remaining to take for the |
| 30 |
// next byte of input. That is, there is never any ambiguity as to the path to |
| 31 |
// take through the NFA during a search. |
| 32 |
// |
| 33 |
// * On the other hand, once a one-pass NFA has its representation converted |
| 34 |
// to something where a constant number of instructions is used for each byte |
| 35 |
// of input, the implementation looks a lot more like a DFA. It's technically |
| 36 |
// more powerful than a DFA since it has side effects (storing offsets inside |
| 37 |
// of slots activated by a transition), but it is far closer to a DFA than an |
| 38 |
// NFA simulation. |
| 39 |
// |
| 40 |
// Thus, in this crate, we call it a one-pass DFA. |
| 41 |
|
| 42 |
use alloc::{vec, vec::Vec}; |
| 43 |
|
| 44 |
use crate::{ |
| 45 |
dfa::{remapper::Remapper, DEAD}, |
| 46 |
nfa::thompson::{self, NFA}, |
| 47 |
util::{ |
| 48 |
alphabet::ByteClasses, |
| 49 |
captures::Captures, |
| 50 |
escape::DebugByte, |
| 51 |
int::{Usize, U32, U64, U8}, |
| 52 |
look::{Look, LookSet, UnicodeWordBoundaryError}, |
| 53 |
primitives::{NonMaxUsize, PatternID, StateID}, |
| 54 |
search::{Anchored, Input, Match, MatchError, MatchKind, Span}, |
| 55 |
sparse_set::SparseSet, |
| 56 |
}, |
| 57 |
}; |
| 58 |
|
| 59 |
/// The configuration used for building a [one-pass DFA](DFA). |
| 60 |
/// |
| 61 |
/// A one-pass DFA configuration is a simple data object that is typically used |
| 62 |
/// with [`Builder::configure`]. It can be cheaply cloned. |
| 63 |
/// |
| 64 |
/// A default configuration can be created either with `Config::new`, or |
| 65 |
/// perhaps more conveniently, with [`DFA::config`]. |
| 66 |
#[derive(Clone, Debug, Default)] |
| 67 |
pub struct Config { |
| 68 |
match_kind: Option<MatchKind>, |
| 69 |
starts_for_each_pattern: Option<bool>, |
| 70 |
byte_classes: Option<bool>, |
| 71 |
size_limit: Option<Option<usize>>, |
| 72 |
} |
| 73 |
|
| 74 |
impl Config { |
| 75 |
/// Return a new default one-pass DFA configuration. |
| 76 |
pub fn new() -> Config { |
| 77 |
Config::default() |
| 78 |
} |
| 79 |
|
| 80 |
/// Set the desired match semantics. |
| 81 |
/// |
| 82 |
/// The default is [`MatchKind::LeftmostFirst`], which corresponds to the |
| 83 |
/// match semantics of Perl-like regex engines. That is, when multiple |
| 84 |
/// patterns would match at the same leftmost position, the pattern that |
| 85 |
/// appears first in the concrete syntax is chosen. |
| 86 |
/// |
| 87 |
/// Currently, the only other kind of match semantics supported is |
| 88 |
/// [`MatchKind::All`]. This corresponds to "classical DFA" construction |
| 89 |
/// where all possible matches are visited. |
| 90 |
/// |
| 91 |
/// When it comes to the one-pass DFA, it is rarer for preference order and |
| 92 |
/// "longest match" to actually disagree. Since if they did disagree, then |
| 93 |
/// the regex typically isn't one-pass. For example, searching `Samwise` |
| 94 |
/// for `Sam|Samwise` will report `Sam` for leftmost-first matching and |
| 95 |
/// `Samwise` for "longest match" or "all" matching. However, this regex is |
| 96 |
/// not one-pass if taken literally. The equivalent regex, `Sam(?:|wise)` |
| 97 |
/// is one-pass and `Sam|Samwise` may be optimized to it. |
| 98 |
/// |
| 99 |
/// The other main difference is that "all" match semantics don't support |
| 100 |
/// non-greedy matches. "All" match semantics always try to match as much |
| 101 |
/// as possible. |
| 102 |
pub fn match_kind(mut self, kind: MatchKind) -> Config { |
| 103 |
self.match_kind = Some(kind); |
| 104 |
self |
| 105 |
} |
| 106 |
|
| 107 |
/// Whether to compile a separate start state for each pattern in the |
| 108 |
/// one-pass DFA. |
| 109 |
/// |
| 110 |
/// When enabled, a separate **anchored** start state is added for each |
| 111 |
/// pattern in the DFA. When this start state is used, then the DFA will |
| 112 |
/// only search for matches for the pattern specified, even if there are |
| 113 |
/// other patterns in the DFA. |
| 114 |
/// |
| 115 |
/// The main downside of this option is that it can potentially increase |
| 116 |
/// the size of the DFA and/or increase the time it takes to build the DFA. |
| 117 |
/// |
| 118 |
/// You might want to enable this option when you want to both search for |
| 119 |
/// anchored matches of any pattern or to search for anchored matches of |
| 120 |
/// one particular pattern while using the same DFA. (Otherwise, you would |
| 121 |
/// need to compile a new DFA for each pattern.) |
| 122 |
/// |
| 123 |
/// By default this is disabled. |
| 124 |
/// |
| 125 |
/// # Example |
| 126 |
/// |
| 127 |
/// This example shows how to build a multi-regex and then search for |
| 128 |
/// matches for a any of the patterns or matches for a specific pattern. |
| 129 |
/// |
| 130 |
/// ``` |
| 131 |
/// use regex_automata::{ |
| 132 |
/// dfa::onepass::DFA, Anchored, Input, Match, PatternID, |
| 133 |
/// }; |
| 134 |
/// |
| 135 |
/// let re = DFA::builder() |
| 136 |
/// .configure(DFA::config().starts_for_each_pattern(true)) |
| 137 |
/// .build_many(&["[a-z]+", "[0-9]+"])?; |
| 138 |
/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); |
| 139 |
/// let haystack = "123abc"; |
| 140 |
/// let input = Input::new(haystack).anchored(Anchored::Yes); |
| 141 |
/// |
| 142 |
/// // A normal multi-pattern search will show pattern 1 matches. |
| 143 |
/// re.try_search(&mut cache, &input, &mut caps)?; |
| 144 |
/// assert_eq!(Some(Match::must(1, 0..3)), caps.get_match()); |
| 145 |
/// |
| 146 |
/// // If we only want to report pattern 0 matches, then we'll get no |
| 147 |
/// // match here. |
| 148 |
/// let input = input.anchored(Anchored::Pattern(PatternID::must(0))); |
| 149 |
/// re.try_search(&mut cache, &input, &mut caps)?; |
| 150 |
/// assert_eq!(None, caps.get_match()); |
| 151 |
/// |
| 152 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 153 |
/// ``` |
| 154 |
pub fn starts_for_each_pattern(mut self, yes: bool) -> Config { |
| 155 |
self.starts_for_each_pattern = Some(yes); |
| 156 |
self |
| 157 |
} |
| 158 |
|
| 159 |
/// Whether to attempt to shrink the size of the DFA's alphabet or not. |
| 160 |
/// |
| 161 |
/// This option is enabled by default and should never be disabled unless |
| 162 |
/// one is debugging a one-pass DFA. |
| 163 |
/// |
| 164 |
/// When enabled, the DFA will use a map from all possible bytes to their |
| 165 |
/// corresponding equivalence class. Each equivalence class represents a |
| 166 |
/// set of bytes that does not discriminate between a match and a non-match |
| 167 |
/// in the DFA. For example, the pattern `[ab]+` has at least two |
| 168 |
/// equivalence classes: a set containing `a` and `b` and a set containing |
| 169 |
/// every byte except for `a` and `b`. `a` and `b` are in the same |
| 170 |
/// equivalence class because they never discriminate between a match and a |
| 171 |
/// non-match. |
| 172 |
/// |
| 173 |
/// The advantage of this map is that the size of the transition table |
| 174 |
/// can be reduced drastically from (approximately) `#states * 256 * |
| 175 |
/// sizeof(StateID)` to `#states * k * sizeof(StateID)` where `k` is the |
| 176 |
/// number of equivalence classes (rounded up to the nearest power of 2). |
| 177 |
/// As a result, total space usage can decrease substantially. Moreover, |
| 178 |
/// since a smaller alphabet is used, DFA compilation becomes faster as |
| 179 |
/// well. |
| 180 |
/// |
| 181 |
/// **WARNING:** This is only useful for debugging DFAs. Disabling this |
| 182 |
/// does not yield any speed advantages. Namely, even when this is |
| 183 |
/// disabled, a byte class map is still used while searching. The only |
| 184 |
/// difference is that every byte will be forced into its own distinct |
| 185 |
/// equivalence class. This is useful for debugging the actual generated |
| 186 |
/// transitions because it lets one see the transitions defined on actual |
| 187 |
/// bytes instead of the equivalence classes. |
| 188 |
pub fn byte_classes(mut self, yes: bool) -> Config { |
| 189 |
self.byte_classes = Some(yes); |
| 190 |
self |
| 191 |
} |
| 192 |
|
| 193 |
/// Set a size limit on the total heap used by a one-pass DFA. |
| 194 |
/// |
| 195 |
/// This size limit is expressed in bytes and is applied during |
| 196 |
/// construction of a one-pass DFA. If the DFA's heap usage exceeds |
| 197 |
/// this configured limit, then construction is stopped and an error is |
| 198 |
/// returned. |
| 199 |
/// |
| 200 |
/// The default is no limit. |
| 201 |
/// |
| 202 |
/// # Example |
| 203 |
/// |
| 204 |
/// This example shows a one-pass DFA that fails to build because of |
| 205 |
/// a configured size limit. This particular example also serves as a |
| 206 |
/// cautionary tale demonstrating just how big DFAs with large Unicode |
| 207 |
/// character classes can get. |
| 208 |
/// |
| 209 |
/// ``` |
| 210 |
/// # if cfg!(miri) { return Ok(()); } // miri takes too long |
| 211 |
/// use regex_automata::{dfa::onepass::DFA, Match}; |
| 212 |
/// |
| 213 |
/// // 6MB isn't enough! |
| 214 |
/// DFA::builder() |
| 215 |
/// .configure(DFA::config().size_limit(Some(6_000_000))) |
| 216 |
/// .build(r"\w{20}") |
| 217 |
/// .unwrap_err(); |
| 218 |
/// |
| 219 |
/// // ... but 7MB probably is! |
| 220 |
/// // (Note that DFA sizes aren't necessarily stable between releases.) |
| 221 |
/// let re = DFA::builder() |
| 222 |
/// .configure(DFA::config().size_limit(Some(7_000_000))) |
| 223 |
/// .build(r"\w{20}")?; |
| 224 |
/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); |
| 225 |
/// let haystack = "A".repeat(20); |
| 226 |
/// re.captures(&mut cache, &haystack, &mut caps); |
| 227 |
/// assert_eq!(Some(Match::must(0, 0..20)), caps.get_match()); |
| 228 |
/// |
| 229 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 230 |
/// ``` |
| 231 |
/// |
| 232 |
/// While one needs a little more than 3MB to represent `\w{20}`, it |
| 233 |
/// turns out that you only need a little more than 4KB to represent |
| 234 |
/// `(?-u:\w{20})`. So only use Unicode if you need it! |
| 235 |
pub fn size_limit(mut self, limit: Option<usize>) -> Config { |
| 236 |
self.size_limit = Some(limit); |
| 237 |
self |
| 238 |
} |
| 239 |
|
| 240 |
/// Returns the match semantics set in this configuration. |
| 241 |
pub fn get_match_kind(&self) -> MatchKind { |
| 242 |
self.match_kind.unwrap_or(MatchKind::LeftmostFirst) |
| 243 |
} |
| 244 |
|
| 245 |
/// Returns whether this configuration has enabled anchored starting states |
| 246 |
/// for every pattern in the DFA. |
| 247 |
pub fn get_starts_for_each_pattern(&self) -> bool { |
| 248 |
self.starts_for_each_pattern.unwrap_or(false) |
| 249 |
} |
| 250 |
|
| 251 |
/// Returns whether this configuration has enabled byte classes or not. |
| 252 |
/// This is typically a debugging oriented option, as disabling it confers |
| 253 |
/// no speed benefit. |
| 254 |
pub fn get_byte_classes(&self) -> bool { |
| 255 |
self.byte_classes.unwrap_or(true) |
| 256 |
} |
| 257 |
|
| 258 |
/// Returns the DFA size limit of this configuration if one was set. |
| 259 |
/// The size limit is total number of bytes on the heap that a DFA is |
| 260 |
/// permitted to use. If the DFA exceeds this limit during construction, |
| 261 |
/// then construction is stopped and an error is returned. |
| 262 |
pub fn get_size_limit(&self) -> Option<usize> { |
| 263 |
self.size_limit.unwrap_or(None) |
| 264 |
} |
| 265 |
|
| 266 |
/// Overwrite the default configuration such that the options in `o` are |
| 267 |
/// always used. If an option in `o` is not set, then the corresponding |
| 268 |
/// option in `self` is used. If it's not set in `self` either, then it |
| 269 |
/// remains not set. |
| 270 |
pub(crate) fn overwrite(&self, o: Config) -> Config { |
| 271 |
Config { |
| 272 |
match_kind: o.match_kind.or(self.match_kind), |
| 273 |
starts_for_each_pattern: o |
| 274 |
.starts_for_each_pattern |
| 275 |
.or(self.starts_for_each_pattern), |
| 276 |
byte_classes: o.byte_classes.or(self.byte_classes), |
| 277 |
size_limit: o.size_limit.or(self.size_limit), |
| 278 |
} |
| 279 |
} |
| 280 |
} |
| 281 |
|
| 282 |
/// A builder for a [one-pass DFA](DFA). |
| 283 |
/// |
| 284 |
/// This builder permits configuring options for the syntax of a pattern, the |
| 285 |
/// NFA construction and the DFA construction. This builder is different from a |
| 286 |
/// general purpose regex builder in that it permits fine grain configuration |
| 287 |
/// of the construction process. The trade off for this is complexity, and |
| 288 |
/// the possibility of setting a configuration that might not make sense. For |
| 289 |
/// example, there are two different UTF-8 modes: |
| 290 |
/// |
| 291 |
/// * [`syntax::Config::utf8`](crate::util::syntax::Config::utf8) controls |
| 292 |
/// whether the pattern itself can contain sub-expressions that match invalid |
| 293 |
/// UTF-8. |
| 294 |
/// * [`thompson::Config::utf8`] controls whether empty matches that split a |
| 295 |
/// Unicode codepoint are reported or not. |
| 296 |
/// |
| 297 |
/// Generally speaking, callers will want to either enable all of these or |
| 298 |
/// disable all of these. |
| 299 |
/// |
| 300 |
/// # Example |
| 301 |
/// |
| 302 |
/// This example shows how to disable UTF-8 mode in the syntax and the NFA. |
| 303 |
/// This is generally what you want for matching on arbitrary bytes. |
| 304 |
/// |
| 305 |
/// ``` |
| 306 |
/// # if cfg!(miri) { return Ok(()); } // miri takes too long |
| 307 |
/// use regex_automata::{ |
| 308 |
/// dfa::onepass::DFA, |
| 309 |
/// nfa::thompson, |
| 310 |
/// util::syntax, |
| 311 |
/// Match, |
| 312 |
/// }; |
| 313 |
/// |
| 314 |
/// let re = DFA::builder() |
| 315 |
/// .syntax(syntax::Config::new().utf8(false)) |
| 316 |
/// .thompson(thompson::Config::new().utf8(false)) |
| 317 |
/// .build(r"foo(?-u:[^b])ar.*")?; |
| 318 |
/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); |
| 319 |
/// |
| 320 |
/// let haystack = b"foo\xFFarzz\xE2\x98\xFF\n"; |
| 321 |
/// re.captures(&mut cache, haystack, &mut caps); |
| 322 |
/// // Notice that `(?-u:[^b])` matches invalid UTF-8, |
| 323 |
/// // but the subsequent `.*` does not! Disabling UTF-8 |
| 324 |
/// // on the syntax permits this. |
| 325 |
/// // |
| 326 |
/// // N.B. This example does not show the impact of |
| 327 |
/// // disabling UTF-8 mode on a one-pass DFA Config, |
| 328 |
/// // since that only impacts regexes that can |
| 329 |
/// // produce matches of length 0. |
| 330 |
/// assert_eq!(Some(Match::must(0, 0..8)), caps.get_match()); |
| 331 |
/// |
| 332 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 333 |
/// ``` |
| 334 |
#[derive(Clone, Debug)] |
| 335 |
pub struct Builder { |
| 336 |
config: Config, |
| 337 |
#[cfg(feature = "syntax")] |
| 338 |
thompson: thompson::Compiler, |
| 339 |
} |
| 340 |
|
| 341 |
impl Builder { |
| 342 |
/// Create a new one-pass DFA builder with the default configuration. |
| 343 |
pub fn new() -> Builder { |
| 344 |
Builder { |
| 345 |
config: Config::default(), |
| 346 |
#[cfg(feature = "syntax")] |
| 347 |
thompson: thompson::Compiler::new(), |
| 348 |
} |
| 349 |
} |
| 350 |
|
| 351 |
/// Build a one-pass DFA from the given pattern. |
| 352 |
/// |
| 353 |
/// If there was a problem parsing or compiling the pattern, then an error |
| 354 |
/// is returned. |
| 355 |
#[cfg(feature = "syntax")] |
| 356 |
pub fn build(&self, pattern: &str) -> Result<DFA, BuildError> { |
| 357 |
self.build_many(&[pattern]) |
| 358 |
} |
| 359 |
|
| 360 |
/// Build a one-pass DFA from the given patterns. |
| 361 |
/// |
| 362 |
/// When matches are returned, the pattern ID corresponds to the index of |
| 363 |
/// the pattern in the slice given. |
| 364 |
#[cfg(feature = "syntax")] |
| 365 |
pub fn build_many<P: AsRef<str>>( |
| 366 |
&self, |
| 367 |
patterns: &[P], |
| 368 |
) -> Result<DFA, BuildError> { |
| 369 |
let nfa = |
| 370 |
self.thompson.build_many(patterns).map_err(BuildError::nfa)?; |
| 371 |
self.build_from_nfa(nfa) |
| 372 |
} |
| 373 |
|
| 374 |
/// Build a DFA from the given NFA. |
| 375 |
/// |
| 376 |
/// # Example |
| 377 |
/// |
| 378 |
/// This example shows how to build a DFA if you already have an NFA in |
| 379 |
/// hand. |
| 380 |
/// |
| 381 |
/// ``` |
| 382 |
/// use regex_automata::{dfa::onepass::DFA, nfa::thompson::NFA, Match}; |
| 383 |
/// |
| 384 |
/// // This shows how to set non-default options for building an NFA. |
| 385 |
/// let nfa = NFA::compiler() |
| 386 |
/// .configure(NFA::config().shrink(true)) |
| 387 |
/// .build(r"[a-z0-9]+")?; |
| 388 |
/// let re = DFA::builder().build_from_nfa(nfa)?; |
| 389 |
/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); |
| 390 |
/// re.captures(&mut cache, "foo123bar", &mut caps); |
| 391 |
/// assert_eq!(Some(Match::must(0, 0..9)), caps.get_match()); |
| 392 |
/// |
| 393 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 394 |
/// ``` |
| 395 |
pub fn build_from_nfa(&self, nfa: NFA) -> Result<DFA, BuildError> { |
| 396 |
// Why take ownership if we're just going to pass a reference to the |
| 397 |
// NFA to our internal builder? Well, the first thing to note is that |
| 398 |
// an NFA uses reference counting internally, so either choice is going |
| 399 |
// to be cheap. So there isn't much cost either way. |
| 400 |
// |
| 401 |
// The real reason is that a one-pass DFA, semantically, shares |
| 402 |
// ownership of an NFA. This is unlike other DFAs that don't share |
| 403 |
// ownership of an NFA at all, primarily because they want to be |
| 404 |
// self-contained in order to support cheap (de)serialization. |
| 405 |
// |
| 406 |
// But then why pass a '&nfa' below if we want to share ownership? |
| 407 |
// Well, it turns out that using a '&NFA' in our internal builder |
| 408 |
// separates its lifetime from the DFA we're building, and this turns |
| 409 |
// out to make code a bit more composable. e.g., We can iterate over |
| 410 |
// things inside the NFA while borrowing the builder as mutable because |
| 411 |
// we know the NFA cannot be mutated. So TL;DR --- this weirdness is |
| 412 |
// "because borrow checker." |
| 413 |
InternalBuilder::new(self.config.clone(), &nfa).build() |
| 414 |
} |
| 415 |
|
| 416 |
/// Apply the given one-pass DFA configuration options to this builder. |
| 417 |
pub fn configure(&mut self, config: Config) -> &mut Builder { |
| 418 |
self.config = self.config.overwrite(config); |
| 419 |
self |
| 420 |
} |
| 421 |
|
| 422 |
/// Set the syntax configuration for this builder using |
| 423 |
/// [`syntax::Config`](crate::util::syntax::Config). |
| 424 |
/// |
| 425 |
/// This permits setting things like case insensitivity, Unicode and multi |
| 426 |
/// line mode. |
| 427 |
/// |
| 428 |
/// These settings only apply when constructing a one-pass DFA directly |
| 429 |
/// from a pattern. |
| 430 |
#[cfg(feature = "syntax")] |
| 431 |
pub fn syntax( |
| 432 |
&mut self, |
| 433 |
config: crate::util::syntax::Config, |
| 434 |
) -> &mut Builder { |
| 435 |
self.thompson.syntax(config); |
| 436 |
self |
| 437 |
} |
| 438 |
|
| 439 |
/// Set the Thompson NFA configuration for this builder using |
| 440 |
/// [`nfa::thompson::Config`](crate::nfa::thompson::Config). |
| 441 |
/// |
| 442 |
/// This permits setting things like whether additional time should be |
| 443 |
/// spent shrinking the size of the NFA. |
| 444 |
/// |
| 445 |
/// These settings only apply when constructing a DFA directly from a |
| 446 |
/// pattern. |
| 447 |
#[cfg(feature = "syntax")] |
| 448 |
pub fn thompson(&mut self, config: thompson::Config) -> &mut Builder { |
| 449 |
self.thompson.configure(config); |
| 450 |
self |
| 451 |
} |
| 452 |
} |
| 453 |
|
| 454 |
/// An internal builder for encapsulating the state necessary to build a |
| 455 |
/// one-pass DFA. Typical use is just `InternalBuilder::new(..).build()`. |
| 456 |
/// |
| 457 |
/// There is no separate pass for determining whether the NFA is one-pass or |
| 458 |
/// not. We just try to build the DFA. If during construction we discover that |
| 459 |
/// it is not one-pass, we bail out. This is likely to lead to some undesirable |
| 460 |
/// expense in some cases, so it might make sense to try an identify common |
| 461 |
/// patterns in the NFA that make it definitively not one-pass. That way, we |
| 462 |
/// can avoid ever trying to build a one-pass DFA in the first place. For |
| 463 |
/// example, '\w*\s' is not one-pass, and since '\w' is Unicode-aware by |
| 464 |
/// default, it's probably not a trivial cost to try and build a one-pass DFA |
| 465 |
/// for it and then fail. |
| 466 |
/// |
| 467 |
/// Note that some (immutable) fields are duplicated here. For example, the |
| 468 |
/// 'nfa' and 'classes' fields are both in the 'DFA'. They are the same thing, |
| 469 |
/// but we duplicate them because it makes composition easier below. Otherwise, |
| 470 |
/// since the borrow checker can't see through method calls, the mutable borrow |
| 471 |
/// we use to mutate the DFA winds up preventing borrowing from any other part |
| 472 |
/// of the DFA, even though we aren't mutating those parts. We only do this |
| 473 |
/// because the duplication is cheap. |
| 474 |
#[derive(Debug)] |
| 475 |
struct InternalBuilder<'a> { |
| 476 |
/// The DFA we're building. |
| 477 |
dfa: DFA, |
| 478 |
/// An unordered collection of NFA state IDs that we haven't yet tried to |
| 479 |
/// build into a DFA state yet. |
| 480 |
/// |
| 481 |
/// This collection does not ultimately wind up including every NFA state |
| 482 |
/// ID. Instead, each ID represents a "start" state for a sub-graph of the |
| 483 |
/// NFA. The set of NFA states we then use to build a DFA state consists |
| 484 |
/// of that "start" state and all states reachable from it via epsilon |
| 485 |
/// transitions. |
| 486 |
uncompiled_nfa_ids: Vec<StateID>, |
| 487 |
/// A map from NFA state ID to DFA state ID. This is useful for easily |
| 488 |
/// determining whether an NFA state has been used as a "starting" point |
| 489 |
/// to build a DFA state yet. If it hasn't, then it is mapped to DEAD, |
| 490 |
/// and since DEAD is specially added and never corresponds to any NFA |
| 491 |
/// state, it follows that a mapping to DEAD implies the NFA state has |
| 492 |
/// no corresponding DFA state yet. |
| 493 |
nfa_to_dfa_id: Vec<StateID>, |
| 494 |
/// A stack used to traverse the NFA states that make up a single DFA |
| 495 |
/// state. Traversal occurs until the stack is empty, and we only push to |
| 496 |
/// the stack when the state ID isn't in 'seen'. Actually, even more than |
| 497 |
/// that, if we try to push something on to this stack that is already in |
| 498 |
/// 'seen', then we bail out on construction completely, since it implies |
| 499 |
/// that the NFA is not one-pass. |
| 500 |
stack: Vec<(StateID, Epsilons)>, |
| 501 |
/// The set of NFA states that we've visited via 'stack'. |
| 502 |
seen: SparseSet, |
| 503 |
/// Whether a match NFA state has been observed while constructing a |
| 504 |
/// one-pass DFA state. Once a match state is seen, assuming we are using |
| 505 |
/// leftmost-first match semantics, then we don't add any more transitions |
| 506 |
/// to the DFA state we're building. |
| 507 |
matched: bool, |
| 508 |
/// The config passed to the builder. |
| 509 |
/// |
| 510 |
/// This is duplicated in dfa.config. |
| 511 |
config: Config, |
| 512 |
/// The NFA we're building a one-pass DFA from. |
| 513 |
/// |
| 514 |
/// This is duplicated in dfa.nfa. |
| 515 |
nfa: &'a NFA, |
| 516 |
/// The equivalence classes that make up the alphabet for this DFA> |
| 517 |
/// |
| 518 |
/// This is duplicated in dfa.classes. |
| 519 |
classes: ByteClasses, |
| 520 |
} |
| 521 |
|
| 522 |
impl<'a> InternalBuilder<'a> { |
| 523 |
/// Create a new builder with an initial empty DFA. |
| 524 |
fn new(config: Config, nfa: &'a NFA) -> InternalBuilder { |
| 525 |
let classes = if !config.get_byte_classes() { |
| 526 |
// A one-pass DFA will always use the equivalence class map, but |
| 527 |
// enabling this option is useful for debugging. Namely, this will |
| 528 |
// cause all transitions to be defined over their actual bytes |
| 529 |
// instead of an opaque equivalence class identifier. The former is |
| 530 |
// much easier to grok as a human. |
| 531 |
ByteClasses::singletons() |
| 532 |
} else { |
| 533 |
nfa.byte_classes().clone() |
| 534 |
}; |
| 535 |
// Normally a DFA alphabet includes the EOI symbol, but we don't need |
| 536 |
// that in the one-pass DFA since we handle look-around explicitly |
| 537 |
// without encoding it into the DFA. Thus, we don't need to delay |
| 538 |
// matches by 1 byte. However, we reuse the space that *would* be used |
| 539 |
// by the EOI transition by putting match information there (like which |
| 540 |
// pattern matches and which look-around assertions need to hold). So |
| 541 |
// this means our real alphabet length is 1 fewer than what the byte |
| 542 |
// classes report, since we don't use EOI. |
| 543 |
let alphabet_len = classes.alphabet_len().checked_sub(1).unwrap(); |
| 544 |
let stride2 = classes.stride2(); |
| 545 |
let dfa = DFA { |
| 546 |
config: config.clone(), |
| 547 |
nfa: nfa.clone(), |
| 548 |
table: vec![], |
| 549 |
starts: vec![], |
| 550 |
// Since one-pass DFAs have a smaller state ID max than |
| 551 |
// StateID::MAX, it follows that StateID::MAX is a valid initial |
| 552 |
// value for min_match_id since no state ID can ever be greater |
| 553 |
// than it. In the case of a one-pass DFA with no match states, the |
| 554 |
// min_match_id will keep this sentinel value. |
| 555 |
min_match_id: StateID::MAX, |
| 556 |
classes: classes.clone(), |
| 557 |
alphabet_len, |
| 558 |
stride2, |
| 559 |
pateps_offset: alphabet_len, |
| 560 |
// OK because PatternID::MAX*2 is guaranteed not to overflow. |
| 561 |
explicit_slot_start: nfa.pattern_len().checked_mul(2).unwrap(), |
| 562 |
}; |
| 563 |
InternalBuilder { |
| 564 |
dfa, |
| 565 |
uncompiled_nfa_ids: vec![], |
| 566 |
nfa_to_dfa_id: vec![DEAD; nfa.states().len()], |
| 567 |
stack: vec![], |
| 568 |
seen: SparseSet::new(nfa.states().len()), |
| 569 |
matched: false, |
| 570 |
config, |
| 571 |
nfa, |
| 572 |
classes, |
| 573 |
} |
| 574 |
} |
| 575 |
|
| 576 |
/// Build the DFA from the NFA given to this builder. If the NFA is not |
| 577 |
/// one-pass, then return an error. An error may also be returned if a |
| 578 |
/// particular limit is exceeded. (Some limits, like the total heap memory |
| 579 |
/// used, are configurable. Others, like the total patterns or slots, are |
| 580 |
/// hard-coded based on representational limitations.) |
| 581 |
fn build(mut self) -> Result<DFA, BuildError> { |
| 582 |
self.nfa.look_set_any().available().map_err(BuildError::word)?; |
| 583 |
for look in self.nfa.look_set_any().iter() { |
| 584 |
// This is a future incompatibility check where if we add any |
| 585 |
// more look-around assertions, then the one-pass DFA either |
| 586 |
// needs to reject them (what we do here) or it needs to have its |
| 587 |
// Transition representation modified to be capable of storing the |
| 588 |
// new assertions. |
| 589 |
if look.as_repr() > Look::WordUnicodeNegate.as_repr() { |
| 590 |
return Err(BuildError::unsupported_look(look)); |
| 591 |
} |
| 592 |
} |
| 593 |
if self.nfa.pattern_len().as_u64() > PatternEpsilons::PATTERN_ID_LIMIT |
| 594 |
{ |
| 595 |
return Err(BuildError::too_many_patterns( |
| 596 |
PatternEpsilons::PATTERN_ID_LIMIT, |
| 597 |
)); |
| 598 |
} |
| 599 |
if self.nfa.group_info().explicit_slot_len() > Slots::LIMIT { |
| 600 |
return Err(BuildError::not_one_pass( |
| 601 |
"too many explicit capturing groups (max is 16)", |
| 602 |
)); |
| 603 |
} |
| 604 |
assert_eq!(DEAD, self.add_empty_state()?); |
| 605 |
|
| 606 |
// This is where the explicit slots start. We care about this because |
| 607 |
// we only need to track explicit slots. The implicit slots---two for |
| 608 |
// each pattern---are tracked as part of the search routine itself. |
| 609 |
let explicit_slot_start = self.nfa.pattern_len() * 2; |
| 610 |
self.add_start_state(None, self.nfa.start_anchored())?; |
| 611 |
if self.config.get_starts_for_each_pattern() { |
| 612 |
for pid in self.nfa.patterns() { |
| 613 |
self.add_start_state( |
| 614 |
Some(pid), |
| 615 |
self.nfa.start_pattern(pid).unwrap(), |
| 616 |
)?; |
| 617 |
} |
| 618 |
} |
| 619 |
// NOTE: One wonders what the effects of treating 'uncompiled_nfa_ids' |
| 620 |
// as a stack are. It is really an unordered *set* of NFA state IDs. |
| 621 |
// If it, for example, in practice led to discovering whether a regex |
| 622 |
// was or wasn't one-pass later than if we processed NFA state IDs in |
| 623 |
// ascending order, then that would make this routine more costly in |
| 624 |
// the somewhat common case of a regex that isn't one-pass. |
| 625 |
while let Some(nfa_id) = self.uncompiled_nfa_ids.pop() { |
| 626 |
let dfa_id = self.nfa_to_dfa_id[nfa_id]; |
| 627 |
// Once we see a match, we keep going, but don't add any new |
| 628 |
// transitions. Normally we'd just stop, but we have to keep |
| 629 |
// going in order to verify that our regex is actually one-pass. |
| 630 |
self.matched = false; |
| 631 |
// The NFA states we've already explored for this DFA state. |
| 632 |
self.seen.clear(); |
| 633 |
// The NFA states to explore via epsilon transitions. If we ever |
| 634 |
// try to push an NFA state that we've already seen, then the NFA |
| 635 |
// is not one-pass because it implies there are multiple epsilon |
| 636 |
// transition paths that lead to the same NFA state. In other |
| 637 |
// words, there is ambiguity. |
| 638 |
self.stack_push(nfa_id, Epsilons::empty())?; |
| 639 |
while let Some((id, epsilons)) = self.stack.pop() { |
| 640 |
match *self.nfa.state(id) { |
| 641 |
thompson::State::ByteRange { ref trans } => { |
| 642 |
self.compile_transition(dfa_id, trans, epsilons)?; |
| 643 |
} |
| 644 |
thompson::State::Sparse(ref sparse) => { |
| 645 |
for trans in sparse.transitions.iter() { |
| 646 |
self.compile_transition(dfa_id, trans, epsilons)?; |
| 647 |
} |
| 648 |
} |
| 649 |
thompson::State::Dense(ref dense) => { |
| 650 |
for trans in dense.iter() { |
| 651 |
self.compile_transition(dfa_id, &trans, epsilons)?; |
| 652 |
} |
| 653 |
} |
| 654 |
thompson::State::Look { look, next } => { |
| 655 |
let looks = epsilons.looks().insert(look); |
| 656 |
self.stack_push(next, epsilons.set_looks(looks))?; |
| 657 |
} |
| 658 |
thompson::State::Union { ref alternates } => { |
| 659 |
for &sid in alternates.iter().rev() { |
| 660 |
self.stack_push(sid, epsilons)?; |
| 661 |
} |
| 662 |
} |
| 663 |
thompson::State::BinaryUnion { alt1, alt2 } => { |
| 664 |
self.stack_push(alt2, epsilons)?; |
| 665 |
self.stack_push(alt1, epsilons)?; |
| 666 |
} |
| 667 |
thompson::State::Capture { next, slot, .. } => { |
| 668 |
let slot = slot.as_usize(); |
| 669 |
let epsilons = if slot < explicit_slot_start { |
| 670 |
// If this is an implicit slot, we don't care |
| 671 |
// about it, since we handle implicit slots in |
| 672 |
// the search routine. We can get away with that |
| 673 |
// because there are 2 implicit slots for every |
| 674 |
// pattern. |
| 675 |
epsilons |
| 676 |
} else { |
| 677 |
// Offset our explicit slots so that they start |
| 678 |
// at index 0. |
| 679 |
let offset = slot - explicit_slot_start; |
| 680 |
epsilons.set_slots(epsilons.slots().insert(offset)) |
| 681 |
}; |
| 682 |
self.stack_push(next, epsilons)?; |
| 683 |
} |
| 684 |
thompson::State::Fail => { |
| 685 |
continue; |
| 686 |
} |
| 687 |
thompson::State::Match { pattern_id } => { |
| 688 |
// If we found two different paths to a match state |
| 689 |
// for the same DFA state, then we have ambiguity. |
| 690 |
// Thus, it's not one-pass. |
| 691 |
if self.matched { |
| 692 |
return Err(BuildError::not_one_pass( |
| 693 |
"multiple epsilon transitions to match state", |
| 694 |
)); |
| 695 |
} |
| 696 |
self.matched = true; |
| 697 |
// Shove the matching pattern ID and the 'epsilons' |
| 698 |
// into the current DFA state's pattern epsilons. The |
| 699 |
// 'epsilons' includes the slots we need to capture |
| 700 |
// before reporting the match and also the conditional |
| 701 |
// epsilon transitions we need to check before we can |
| 702 |
// report a match. |
| 703 |
self.dfa.set_pattern_epsilons( |
| 704 |
dfa_id, |
| 705 |
PatternEpsilons::empty() |
| 706 |
.set_pattern_id(pattern_id) |
| 707 |
.set_epsilons(epsilons), |
| 708 |
); |
| 709 |
// N.B. It is tempting to just bail out here when |
| 710 |
// compiling a leftmost-first DFA, since we will never |
| 711 |
// compile any more transitions in that case. But we |
| 712 |
// actually need to keep going in order to verify that |
| 713 |
// we actually have a one-pass regex. e.g., We might |
| 714 |
// see more Match states (e.g., for other patterns) |
| 715 |
// that imply that we don't have a one-pass regex. |
| 716 |
// So instead, we mark that we've found a match and |
| 717 |
// continue on. When we go to compile a new DFA state, |
| 718 |
// we just skip that part. But otherwise check that the |
| 719 |
// one-pass property is upheld. |
| 720 |
} |
| 721 |
} |
| 722 |
} |
| 723 |
} |
| 724 |
self.shuffle_states(); |
| 725 |
Ok(self.dfa) |
| 726 |
} |
| 727 |
|
| 728 |
/// Shuffle all match states to the end of the transition table and set |
| 729 |
/// 'min_match_id' to the ID of the first such match state. |
| 730 |
/// |
| 731 |
/// The point of this is to make it extremely cheap to determine whether |
| 732 |
/// a state is a match state or not. We need to check on this on every |
| 733 |
/// transition during a search, so it being cheap is important. This |
| 734 |
/// permits us to check it by simply comparing two state identifiers, as |
| 735 |
/// opposed to looking for the pattern ID in the state's `PatternEpsilons`. |
| 736 |
/// (Which requires a memory load and some light arithmetic.) |
| 737 |
fn shuffle_states(&mut self) { |
| 738 |
let mut remapper = Remapper::new(&self.dfa); |
| 739 |
let mut next_dest = self.dfa.last_state_id(); |
| 740 |
for i in (0..self.dfa.state_len()).rev() { |
| 741 |
let id = StateID::must(i); |
| 742 |
let is_match = |
| 743 |
self.dfa.pattern_epsilons(id).pattern_id().is_some(); |
| 744 |
if !is_match { |
| 745 |
continue; |
| 746 |
} |
| 747 |
remapper.swap(&mut self.dfa, next_dest, id); |
| 748 |
self.dfa.min_match_id = next_dest; |
| 749 |
next_dest = self.dfa.prev_state_id(next_dest).expect( |
| 750 |
"match states should be a proper subset of all states", |
| 751 |
); |
| 752 |
} |
| 753 |
remapper.remap(&mut self.dfa); |
| 754 |
} |
| 755 |
|
| 756 |
/// Compile the given NFA transition into the DFA state given. |
| 757 |
/// |
| 758 |
/// 'Epsilons' corresponds to any conditional epsilon transitions that need |
| 759 |
/// to be satisfied to follow this transition, and any slots that need to |
| 760 |
/// be saved if the transition is followed. |
| 761 |
/// |
| 762 |
/// If this transition indicates that the NFA is not one-pass, then |
| 763 |
/// this returns an error. (This occurs, for example, if the DFA state |
| 764 |
/// already has a transition defined for the same input symbols as the |
| 765 |
/// given transition, *and* the result of the old and new transitions is |
| 766 |
/// different.) |
| 767 |
fn compile_transition( |
| 768 |
&mut self, |
| 769 |
dfa_id: StateID, |
| 770 |
trans: &thompson::Transition, |
| 771 |
epsilons: Epsilons, |
| 772 |
) -> Result<(), BuildError> { |
| 773 |
let next_dfa_id = self.add_dfa_state_for_nfa_state(trans.next)?; |
| 774 |
for byte in self |
| 775 |
.classes |
| 776 |
.representatives(trans.start..=trans.end) |
| 777 |
.filter_map(|r| r.as_u8()) |
| 778 |
{ |
| 779 |
let oldtrans = self.dfa.transition(dfa_id, byte); |
| 780 |
let newtrans = |
| 781 |
Transition::new(self.matched, next_dfa_id, epsilons); |
| 782 |
// If the old transition points to the DEAD state, then we know |
| 783 |
// 'byte' has not been mapped to any transition for this DFA state |
| 784 |
// yet. So set it unconditionally. Otherwise, we require that the |
| 785 |
// old and new transitions are equivalent. Otherwise, there is |
| 786 |
// ambiguity and thus the regex is not one-pass. |
| 787 |
if oldtrans.state_id() == DEAD { |
| 788 |
self.dfa.set_transition(dfa_id, byte, newtrans); |
| 789 |
} else if oldtrans != newtrans { |
| 790 |
return Err(BuildError::not_one_pass( |
| 791 |
"conflicting transition", |
| 792 |
)); |
| 793 |
} |
| 794 |
} |
| 795 |
Ok(()) |
| 796 |
} |
| 797 |
|
| 798 |
/// Add a start state to the DFA corresponding to the given NFA starting |
| 799 |
/// state ID. |
| 800 |
/// |
| 801 |
/// If adding a state would blow any limits (configured or hard-coded), |
| 802 |
/// then an error is returned. |
| 803 |
/// |
| 804 |
/// If the starting state is an anchored state for a particular pattern, |
| 805 |
/// then callers must provide the pattern ID for that starting state. |
| 806 |
/// Callers must also ensure that the first starting state added is the |
| 807 |
/// start state for all patterns, and then each anchored starting state for |
| 808 |
/// each pattern (if necessary) added in order. Otherwise, this panics. |
| 809 |
fn add_start_state( |
| 810 |
&mut self, |
| 811 |
pid: Option<PatternID>, |
| 812 |
nfa_id: StateID, |
| 813 |
) -> Result<StateID, BuildError> { |
| 814 |
match pid { |
| 815 |
// With no pid, this should be the start state for all patterns |
| 816 |
// and thus be the first one. |
| 817 |
None => assert!(self.dfa.starts.is_empty()), |
| 818 |
// With a pid, we want it to be at self.dfa.starts[pid+1]. |
| 819 |
Some(pid) => assert!(self.dfa.starts.len() == pid.one_more()), |
| 820 |
} |
| 821 |
let dfa_id = self.add_dfa_state_for_nfa_state(nfa_id)?; |
| 822 |
self.dfa.starts.push(dfa_id); |
| 823 |
Ok(dfa_id) |
| 824 |
} |
| 825 |
|
| 826 |
/// Add a new DFA state corresponding to the given NFA state. If adding a |
| 827 |
/// state would blow any limits (configured or hard-coded), then an error |
| 828 |
/// is returned. If a DFA state already exists for the given NFA state, |
| 829 |
/// then that DFA state's ID is returned and no new states are added. |
| 830 |
/// |
| 831 |
/// It is not expected that this routine is called for every NFA state. |
| 832 |
/// Instead, an NFA state ID will usually correspond to the "start" state |
| 833 |
/// for a sub-graph of the NFA, where all states in the sub-graph are |
| 834 |
/// reachable via epsilon transitions (conditional or unconditional). That |
| 835 |
/// sub-graph of NFA states is ultimately what produces a single DFA state. |
| 836 |
fn add_dfa_state_for_nfa_state( |
| 837 |
&mut self, |
| 838 |
nfa_id: StateID, |
| 839 |
) -> Result<StateID, BuildError> { |
| 840 |
// If we've already built a DFA state for the given NFA state, then |
| 841 |
// just return that. We definitely do not want to have more than one |
| 842 |
// DFA state in existence for the same NFA state, since all but one of |
| 843 |
// them will likely become unreachable. And at least some of them are |
| 844 |
// likely to wind up being incomplete. |
| 845 |
let existing_dfa_id = self.nfa_to_dfa_id[nfa_id]; |
| 846 |
if existing_dfa_id != DEAD { |
| 847 |
return Ok(existing_dfa_id); |
| 848 |
} |
| 849 |
// If we don't have any DFA state yet, add it and then add the given |
| 850 |
// NFA state to the list of states to explore. |
| 851 |
let dfa_id = self.add_empty_state()?; |
| 852 |
self.nfa_to_dfa_id[nfa_id] = dfa_id; |
| 853 |
self.uncompiled_nfa_ids.push(nfa_id); |
| 854 |
Ok(dfa_id) |
| 855 |
} |
| 856 |
|
| 857 |
/// Unconditionally add a new empty DFA state. If adding it would exceed |
| 858 |
/// any limits (configured or hard-coded), then an error is returned. The |
| 859 |
/// ID of the new state is returned on success. |
| 860 |
/// |
| 861 |
/// The added state is *not* a match state. |
| 862 |
fn add_empty_state(&mut self) -> Result<StateID, BuildError> { |
| 863 |
let state_limit = Transition::STATE_ID_LIMIT; |
| 864 |
// Note that unlike dense and lazy DFAs, we specifically do NOT |
| 865 |
// premultiply our state IDs here. The reason is that we want to pack |
| 866 |
// our state IDs into 64-bit transitions with other info, so the fewer |
| 867 |
// the bits we use for state IDs the better. If we premultiply, then |
| 868 |
// our state ID space shrinks. We justify this by the assumption that |
| 869 |
// a one-pass DFA is just already doing a fair bit more work than a |
| 870 |
// normal DFA anyway, so an extra multiplication to compute a state |
| 871 |
// transition doesn't seem like a huge deal. |
| 872 |
let next_id = self.dfa.table.len() >> self.dfa.stride2(); |
| 873 |
let id = StateID::new(next_id) |
| 874 |
.map_err(|_| BuildError::too_many_states(state_limit))?; |
| 875 |
if id.as_u64() > Transition::STATE_ID_LIMIT { |
| 876 |
return Err(BuildError::too_many_states(state_limit)); |
| 877 |
} |
| 878 |
self.dfa |
| 879 |
.table |
| 880 |
.extend(core::iter::repeat(Transition(0)).take(self.dfa.stride())); |
| 881 |
// The default empty value for 'PatternEpsilons' is sadly not all |
| 882 |
// zeroes. Instead, a special sentinel is used to indicate that there |
| 883 |
// is no pattern. So we need to explicitly set the pattern epsilons to |
| 884 |
// the correct "empty" PatternEpsilons. |
| 885 |
self.dfa.set_pattern_epsilons(id, PatternEpsilons::empty()); |
| 886 |
if let Some(size_limit) = self.config.get_size_limit() { |
| 887 |
if self.dfa.memory_usage() > size_limit { |
| 888 |
return Err(BuildError::exceeded_size_limit(size_limit)); |
| 889 |
} |
| 890 |
} |
| 891 |
Ok(id) |
| 892 |
} |
| 893 |
|
| 894 |
/// Push the given NFA state ID and its corresponding epsilons (slots and |
| 895 |
/// conditional epsilon transitions) on to a stack for use in a depth first |
| 896 |
/// traversal of a sub-graph of the NFA. |
| 897 |
/// |
| 898 |
/// If the given NFA state ID has already been pushed on to the stack, then |
| 899 |
/// it indicates the regex is not one-pass and this correspondingly returns |
| 900 |
/// an error. |
| 901 |
fn stack_push( |
| 902 |
&mut self, |
| 903 |
nfa_id: StateID, |
| 904 |
epsilons: Epsilons, |
| 905 |
) -> Result<(), BuildError> { |
| 906 |
// If we already have seen a match and we are compiling a leftmost |
| 907 |
// first DFA, then we shouldn't add any more states to look at. This is |
| 908 |
// effectively how preference order and non-greediness is implemented. |
| 909 |
// if !self.config.get_match_kind().continue_past_first_match() |
| 910 |
// && self.matched |
| 911 |
// { |
| 912 |
// return Ok(()); |
| 913 |
// } |
| 914 |
if !self.seen.insert(nfa_id) { |
| 915 |
return Err(BuildError::not_one_pass( |
| 916 |
"multiple epsilon transitions to same state", |
| 917 |
)); |
| 918 |
} |
| 919 |
self.stack.push((nfa_id, epsilons)); |
| 920 |
Ok(()) |
| 921 |
} |
| 922 |
} |
| 923 |
|
| 924 |
/// A one-pass DFA for executing a subset of anchored regex searches while |
| 925 |
/// resolving capturing groups. |
| 926 |
/// |
| 927 |
/// A one-pass DFA can be built from an NFA that is one-pass. An NFA is |
| 928 |
/// one-pass when there is never any ambiguity about how to continue a search. |
| 929 |
/// For example, `a*a` is not one-pass becuase during a search, it's not |
| 930 |
/// possible to know whether to continue matching the `a*` or to move on to |
| 931 |
/// the single `a`. However, `a*b` is one-pass, because for every byte in the |
| 932 |
/// input, it's always clear when to move on from `a*` to `b`. |
| 933 |
/// |
| 934 |
/// # Only anchored searches are supported |
| 935 |
/// |
| 936 |
/// In this crate, especially for DFAs, unanchored searches are implemented by |
| 937 |
/// treating the pattern as if it had a `(?s-u:.)*?` prefix. While the prefix |
| 938 |
/// is one-pass on its own, adding anything after it, e.g., `(?s-u:.)*?a` will |
| 939 |
/// make the overall pattern not one-pass. Why? Because the `(?s-u:.)` matches |
| 940 |
/// any byte, and there is therefore ambiguity as to when the prefix should |
| 941 |
/// stop matching and something else should start matching. |
| 942 |
/// |
| 943 |
/// Therefore, one-pass DFAs do not support unanchored searches. In addition |
| 944 |
/// to many regexes simply not being one-pass, it implies that one-pass DFAs |
| 945 |
/// have limited utility. With that said, when a one-pass DFA can be used, it |
| 946 |
/// can potentially provide a dramatic speed up over alternatives like the |
| 947 |
/// [`BoundedBacktracker`](crate::nfa::thompson::backtrack::BoundedBacktracker) |
| 948 |
/// and the [`PikeVM`](crate::nfa::thompson::pikevm::PikeVM). In particular, |
| 949 |
/// a one-pass DFA is the only DFA capable of reporting the spans of matching |
| 950 |
/// capturing groups. |
| 951 |
/// |
| 952 |
/// To clarify, when we say that unanchored searches are not supported, what |
| 953 |
/// that actually means is: |
| 954 |
/// |
| 955 |
/// * The high level routines, [`DFA::is_match`] and [`DFA::captures`], always |
| 956 |
/// do anchored searches. |
| 957 |
/// * Since iterators are most useful in the context of unanchored searches, |
| 958 |
/// there is no `DFA::captures_iter` method. |
| 959 |
/// * For lower level routines like [`DFA::try_search`], an error will be |
| 960 |
/// returned if the given [`Input`] is configured to do an unanchored search or |
| 961 |
/// search for an invalid pattern ID. (Note that an [`Input`] is configured to |
| 962 |
/// do an unanchored search by default, so just giving a `Input::new` is |
| 963 |
/// guaranteed to return an error.) |
| 964 |
/// |
| 965 |
/// # Other limitations |
| 966 |
/// |
| 967 |
/// In addition to the [configurable heap limit](Config::size_limit) and |
| 968 |
/// the requirement that a regex pattern be one-pass, there are some other |
| 969 |
/// limitations: |
| 970 |
/// |
| 971 |
/// * There is an internal limit on the total number of explicit capturing |
| 972 |
/// groups that appear across all patterns. It is somewhat small and there is |
| 973 |
/// no way to configure it. If your pattern(s) exceed this limit, then building |
| 974 |
/// a one-pass DFA will fail. |
| 975 |
/// * If the number of patterns exceeds an internal unconfigurable limit, then |
| 976 |
/// building a one-pass DFA will fail. This limit is quite large and you're |
| 977 |
/// unlikely to hit it. |
| 978 |
/// * If the total number of states exceeds an internal unconfigurable limit, |
| 979 |
/// then building a one-pass DFA will fail. This limit is quite large and |
| 980 |
/// you're unlikely to hit it. |
| 981 |
/// |
| 982 |
/// # Other examples of regexes that aren't one-pass |
| 983 |
/// |
| 984 |
/// One particularly unfortunate example is that enabling Unicode can cause |
| 985 |
/// regexes that were one-pass to no longer be one-pass. Consider the regex |
| 986 |
/// `(?-u)\w*\s` for example. It is one-pass because there is exactly no |
| 987 |
/// overlap between the ASCII definitions of `\w` and `\s`. But `\w*\s` |
| 988 |
/// (i.e., with Unicode enabled) is *not* one-pass because `\w` and `\s` get |
| 989 |
/// translated to UTF-8 automatons. And while the *codepoints* in `\w` and `\s` |
| 990 |
/// do not overlap, the underlying UTF-8 encodings do. Indeed, because of the |
| 991 |
/// overlap between UTF-8 automata, the use of Unicode character classes will |
| 992 |
/// tend to vastly increase the likelihood of a regex not being one-pass. |
| 993 |
/// |
| 994 |
/// # How does one know if a regex is one-pass or not? |
| 995 |
/// |
| 996 |
/// At the time of writing, the only way to know is to try and build a one-pass |
| 997 |
/// DFA. The one-pass property is checked while constructing the DFA. |
| 998 |
/// |
| 999 |
/// This does mean that you might potentially waste some CPU cycles and memory |
| 1000 |
/// by optimistically trying to build a one-pass DFA. But this is currently the |
| 1001 |
/// only way. In the future, building a one-pass DFA might be able to use some |
| 1002 |
/// heuristics to detect common violations of the one-pass property and bail |
| 1003 |
/// more quickly. |
| 1004 |
/// |
| 1005 |
/// # Resource usage |
| 1006 |
/// |
| 1007 |
/// Unlike a general DFA, a one-pass DFA has stricter bounds on its resource |
| 1008 |
/// usage. Namely, construction of a one-pass DFA has a time and space |
| 1009 |
/// complexity of `O(n)`, where `n ~ nfa.states().len()`. (A general DFA's time |
| 1010 |
/// and space complexity is `O(2^n)`.) This smaller time bound is achieved |
| 1011 |
/// because there is at most one DFA state created for each NFA state. If |
| 1012 |
/// additional DFA states would be required, then the pattern is not one-pass |
| 1013 |
/// and construction will fail. |
| 1014 |
/// |
| 1015 |
/// Note though that currently, this DFA uses a fully dense representation. |
| 1016 |
/// This means that while its space complexity is no worse than an NFA, it may |
| 1017 |
/// in practice use more memory because of higher constant factors. The reason |
| 1018 |
/// for this trade off is two-fold. Firstly, a dense representation makes the |
| 1019 |
/// search faster. Secondly, the bigger an NFA, the more unlikely it is to be |
| 1020 |
/// one-pass. Therefore, most one-pass DFAs are usually pretty small. |
| 1021 |
/// |
| 1022 |
/// # Example |
| 1023 |
/// |
| 1024 |
/// This example shows that the one-pass DFA implements Unicode word boundaries |
| 1025 |
/// correctly while simultaneously reporting spans for capturing groups that |
| 1026 |
/// participate in a match. (This is the only DFA that implements full support |
| 1027 |
/// for Unicode word boundaries.) |
| 1028 |
/// |
| 1029 |
/// ``` |
| 1030 |
/// # if cfg!(miri) { return Ok(()); } // miri takes too long |
| 1031 |
/// use regex_automata::{dfa::onepass::DFA, Match, Span}; |
| 1032 |
/// |
| 1033 |
/// let re = DFA::new(r"\b(?P<first>\w+)[[:space:]]+(?P<last>\w+)\b")?; |
| 1034 |
/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); |
| 1035 |
/// |
| 1036 |
/// re.captures(&mut cache, "Шерлок Холмс", &mut caps); |
| 1037 |
/// assert_eq!(Some(Match::must(0, 0..23)), caps.get_match()); |
| 1038 |
/// assert_eq!(Some(Span::from(0..12)), caps.get_group_by_name("first")); |
| 1039 |
/// assert_eq!(Some(Span::from(13..23)), caps.get_group_by_name("last")); |
| 1040 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1041 |
/// ``` |
| 1042 |
/// |
| 1043 |
/// # Example: iteration |
| 1044 |
/// |
| 1045 |
/// Unlike other regex engines in this crate, this one does not provide |
| 1046 |
/// iterator search functions. This is because a one-pass DFA only supports |
| 1047 |
/// anchored searches, and so iterator functions are generally not applicable. |
| 1048 |
/// |
| 1049 |
/// However, if you know that all of your matches are |
| 1050 |
/// directly adjacent, then an iterator can be used. The |
| 1051 |
/// [`util::iter::Searcher`](crate::util::iter::Searcher) type can be used for |
| 1052 |
/// this purpose: |
| 1053 |
/// |
| 1054 |
/// ``` |
| 1055 |
/// # if cfg!(miri) { return Ok(()); } // miri takes too long |
| 1056 |
/// use regex_automata::{ |
| 1057 |
/// dfa::onepass::DFA, |
| 1058 |
/// util::iter::Searcher, |
| 1059 |
/// Anchored, Input, Span, |
| 1060 |
/// }; |
| 1061 |
/// |
| 1062 |
/// let re = DFA::new(r"\w(\d)\w")?; |
| 1063 |
/// let (mut cache, caps) = (re.create_cache(), re.create_captures()); |
| 1064 |
/// let input = Input::new("a1zb2yc3x").anchored(Anchored::Yes); |
| 1065 |
/// |
| 1066 |
/// let mut it = Searcher::new(input).into_captures_iter(caps, |input, caps| { |
| 1067 |
/// Ok(re.try_search(&mut cache, input, caps)?) |
| 1068 |
/// }).infallible(); |
| 1069 |
/// let caps0 = it.next().unwrap(); |
| 1070 |
/// assert_eq!(Some(Span::from(1..2)), caps0.get_group(1)); |
| 1071 |
/// |
| 1072 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1073 |
/// ``` |
| 1074 |
#[derive(Clone)] |
| 1075 |
pub struct DFA { |
| 1076 |
/// The configuration provided by the caller. |
| 1077 |
config: Config, |
| 1078 |
/// The NFA used to build this DFA. |
| 1079 |
/// |
| 1080 |
/// NOTE: We probably don't need to store the NFA here, but we use enough |
| 1081 |
/// bits from it that it's convenient to do so. And there really isn't much |
| 1082 |
/// cost to doing so either, since an NFA is reference counted internally. |
| 1083 |
nfa: NFA, |
| 1084 |
/// The transition table. Given a state ID 's' and a byte of haystack 'b', |
| 1085 |
/// the next state is `table[sid + classes[byte]]`. |
| 1086 |
/// |
| 1087 |
/// The stride of this table (i.e., the number of columns) is always |
| 1088 |
/// a power of 2, even if the alphabet length is smaller. This makes |
| 1089 |
/// converting between state IDs and state indices very cheap. |
| 1090 |
/// |
| 1091 |
/// Note that the stride always includes room for one extra "transition" |
| 1092 |
/// that isn't actually a transition. It is a 'PatternEpsilons' that is |
| 1093 |
/// used for match states only. Because of this, the maximum number of |
| 1094 |
/// active columns in the transition table is 257, which means the maximum |
| 1095 |
/// stride is 512 (the next power of 2 greater than or equal to 257). |
| 1096 |
table: Vec<Transition>, |
| 1097 |
/// The DFA state IDs of the starting states. |
| 1098 |
/// |
| 1099 |
/// `starts[0]` is always present and corresponds to the starting state |
| 1100 |
/// when searching for matches of any pattern in the DFA. |
| 1101 |
/// |
| 1102 |
/// `starts[i]` where i>0 corresponds to the starting state for the pattern |
| 1103 |
/// ID 'i-1'. These starting states are optional. |
| 1104 |
starts: Vec<StateID>, |
| 1105 |
/// Every state ID >= this value corresponds to a match state. |
| 1106 |
/// |
| 1107 |
/// This is what a search uses to detect whether a state is a match state |
| 1108 |
/// or not. It requires only a simple comparison instead of bit-unpacking |
| 1109 |
/// the PatternEpsilons from every state. |
| 1110 |
min_match_id: StateID, |
| 1111 |
/// The alphabet of this DFA, split into equivalence classes. Bytes in the |
| 1112 |
/// same equivalence class can never discriminate between a match and a |
| 1113 |
/// non-match. |
| 1114 |
classes: ByteClasses, |
| 1115 |
/// The number of elements in each state in the transition table. This may |
| 1116 |
/// be less than the stride, since the stride is always a power of 2 and |
| 1117 |
/// the alphabet length can be anything up to and including 256. |
| 1118 |
alphabet_len: usize, |
| 1119 |
/// The number of columns in the transition table, expressed as a power of |
| 1120 |
/// 2. |
| 1121 |
stride2: usize, |
| 1122 |
/// The offset at which the PatternEpsilons for a match state is stored in |
| 1123 |
/// the transition table. |
| 1124 |
/// |
| 1125 |
/// PERF: One wonders whether it would be better to put this in a separate |
| 1126 |
/// allocation, since only match states have a non-empty PatternEpsilons |
| 1127 |
/// and the number of match states tends be dwarfed by the number of |
| 1128 |
/// non-match states. So this would save '8*len(non_match_states)' for each |
| 1129 |
/// DFA. The question is whether moving this to a different allocation will |
| 1130 |
/// lead to a perf hit during searches. You might think dealing with match |
| 1131 |
/// states is rare, but some regexes spend a lot of time in match states |
| 1132 |
/// gobbling up input. But... match state handling is already somewhat |
| 1133 |
/// expensive, so maybe this wouldn't do much? Either way, it's worth |
| 1134 |
/// experimenting. |
| 1135 |
pateps_offset: usize, |
| 1136 |
/// The first explicit slot index. This refers to the first slot appearing |
| 1137 |
/// immediately after the last implicit slot. It is always 'patterns.len() |
| 1138 |
/// * 2'. |
| 1139 |
/// |
| 1140 |
/// We record this because we only store the explicit slots in our DFA |
| 1141 |
/// transition table that need to be saved. Implicit slots are handled |
| 1142 |
/// automatically as part of the search. |
| 1143 |
explicit_slot_start: usize, |
| 1144 |
} |
| 1145 |
|
| 1146 |
impl DFA { |
| 1147 |
/// Parse the given regular expression using the default configuration and |
| 1148 |
/// return the corresponding one-pass DFA. |
| 1149 |
/// |
| 1150 |
/// If you want a non-default configuration, then use the [`Builder`] to |
| 1151 |
/// set your own configuration. |
| 1152 |
/// |
| 1153 |
/// # Example |
| 1154 |
/// |
| 1155 |
/// ``` |
| 1156 |
/// use regex_automata::{dfa::onepass::DFA, Match}; |
| 1157 |
/// |
| 1158 |
/// let re = DFA::new("foo[0-9]+bar")?; |
| 1159 |
/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); |
| 1160 |
/// |
| 1161 |
/// re.captures(&mut cache, "foo12345barzzz", &mut caps); |
| 1162 |
/// assert_eq!(Some(Match::must(0, 0..11)), caps.get_match()); |
| 1163 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1164 |
/// ``` |
| 1165 |
#[cfg(feature = "syntax")] |
| 1166 |
#[inline] |
| 1167 |
pub fn new(pattern: &str) -> Result<DFA, BuildError> { |
| 1168 |
DFA::builder().build(pattern) |
| 1169 |
} |
| 1170 |
|
| 1171 |
/// Like `new`, but parses multiple patterns into a single "multi regex." |
| 1172 |
/// This similarly uses the default regex configuration. |
| 1173 |
/// |
| 1174 |
/// # Example |
| 1175 |
/// |
| 1176 |
/// ``` |
| 1177 |
/// use regex_automata::{dfa::onepass::DFA, Match}; |
| 1178 |
/// |
| 1179 |
/// let re = DFA::new_many(&["[a-z]+", "[0-9]+"])?; |
| 1180 |
/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); |
| 1181 |
/// |
| 1182 |
/// re.captures(&mut cache, "abc123", &mut caps); |
| 1183 |
/// assert_eq!(Some(Match::must(0, 0..3)), caps.get_match()); |
| 1184 |
/// |
| 1185 |
/// re.captures(&mut cache, "123abc", &mut caps); |
| 1186 |
/// assert_eq!(Some(Match::must(1, 0..3)), caps.get_match()); |
| 1187 |
/// |
| 1188 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1189 |
/// ``` |
| 1190 |
#[cfg(feature = "syntax")] |
| 1191 |
#[inline] |
| 1192 |
pub fn new_many<P: AsRef<str>>(patterns: &[P]) -> Result<DFA, BuildError> { |
| 1193 |
DFA::builder().build_many(patterns) |
| 1194 |
} |
| 1195 |
|
| 1196 |
/// Like `new`, but builds a one-pass DFA directly from an NFA. This is |
| 1197 |
/// useful if you already have an NFA, or even if you hand-assembled the |
| 1198 |
/// NFA. |
| 1199 |
/// |
| 1200 |
/// # Example |
| 1201 |
/// |
| 1202 |
/// This shows how to hand assemble a regular expression via its HIR, |
| 1203 |
/// compile an NFA from it and build a one-pass DFA from the NFA. |
| 1204 |
/// |
| 1205 |
/// ``` |
| 1206 |
/// use regex_automata::{ |
| 1207 |
/// dfa::onepass::DFA, |
| 1208 |
/// nfa::thompson::NFA, |
| 1209 |
/// Match, |
| 1210 |
/// }; |
| 1211 |
/// use regex_syntax::hir::{Hir, Class, ClassBytes, ClassBytesRange}; |
| 1212 |
/// |
| 1213 |
/// let hir = Hir::class(Class::Bytes(ClassBytes::new(vec![ |
| 1214 |
/// ClassBytesRange::new(b'0', b'9'), |
| 1215 |
/// ClassBytesRange::new(b'A', b'Z'), |
| 1216 |
/// ClassBytesRange::new(b'_', b'_'), |
| 1217 |
/// ClassBytesRange::new(b'a', b'z'), |
| 1218 |
/// ]))); |
| 1219 |
/// |
| 1220 |
/// let config = NFA::config().nfa_size_limit(Some(1_000)); |
| 1221 |
/// let nfa = NFA::compiler().configure(config).build_from_hir(&hir)?; |
| 1222 |
/// |
| 1223 |
/// let re = DFA::new_from_nfa(nfa)?; |
| 1224 |
/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); |
| 1225 |
/// let expected = Some(Match::must(0, 0..1)); |
| 1226 |
/// re.captures(&mut cache, "A", &mut caps); |
| 1227 |
/// assert_eq!(expected, caps.get_match()); |
| 1228 |
/// |
| 1229 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1230 |
/// ``` |
| 1231 |
pub fn new_from_nfa(nfa: NFA) -> Result<DFA, BuildError> { |
| 1232 |
DFA::builder().build_from_nfa(nfa) |
| 1233 |
} |
| 1234 |
|
| 1235 |
/// Create a new one-pass DFA that matches every input. |
| 1236 |
/// |
| 1237 |
/// # Example |
| 1238 |
/// |
| 1239 |
/// ``` |
| 1240 |
/// use regex_automata::{dfa::onepass::DFA, Match}; |
| 1241 |
/// |
| 1242 |
/// let dfa = DFA::always_match()?; |
| 1243 |
/// let mut cache = dfa.create_cache(); |
| 1244 |
/// let mut caps = dfa.create_captures(); |
| 1245 |
/// |
| 1246 |
/// let expected = Match::must(0, 0..0); |
| 1247 |
/// dfa.captures(&mut cache, "", &mut caps); |
| 1248 |
/// assert_eq!(Some(expected), caps.get_match()); |
| 1249 |
/// dfa.captures(&mut cache, "foo", &mut caps); |
| 1250 |
/// assert_eq!(Some(expected), caps.get_match()); |
| 1251 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1252 |
/// ``` |
| 1253 |
pub fn always_match() -> Result<DFA, BuildError> { |
| 1254 |
let nfa = thompson::NFA::always_match(); |
| 1255 |
Builder::new().build_from_nfa(nfa) |
| 1256 |
} |
| 1257 |
|
| 1258 |
/// Create a new one-pass DFA that never matches any input. |
| 1259 |
/// |
| 1260 |
/// # Example |
| 1261 |
/// |
| 1262 |
/// ``` |
| 1263 |
/// use regex_automata::dfa::onepass::DFA; |
| 1264 |
/// |
| 1265 |
/// let dfa = DFA::never_match()?; |
| 1266 |
/// let mut cache = dfa.create_cache(); |
| 1267 |
/// let mut caps = dfa.create_captures(); |
| 1268 |
/// |
| 1269 |
/// dfa.captures(&mut cache, "", &mut caps); |
| 1270 |
/// assert_eq!(None, caps.get_match()); |
| 1271 |
/// dfa.captures(&mut cache, "foo", &mut caps); |
| 1272 |
/// assert_eq!(None, caps.get_match()); |
| 1273 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1274 |
/// ``` |
| 1275 |
pub fn never_match() -> Result<DFA, BuildError> { |
| 1276 |
let nfa = thompson::NFA::never_match(); |
| 1277 |
Builder::new().build_from_nfa(nfa) |
| 1278 |
} |
| 1279 |
|
| 1280 |
/// Return a default configuration for a DFA. |
| 1281 |
/// |
| 1282 |
/// This is a convenience routine to avoid needing to import the `Config` |
| 1283 |
/// type when customizing the construction of a DFA. |
| 1284 |
/// |
| 1285 |
/// # Example |
| 1286 |
/// |
| 1287 |
/// This example shows how to change the match semantics of this DFA from |
| 1288 |
/// its default "leftmost first" to "all." When using "all," non-greediness |
| 1289 |
/// doesn't apply and neither does preference order matching. Instead, the |
| 1290 |
/// longest match possible is always returned. (Although, by construction, |
| 1291 |
/// it's impossible for a one-pass DFA to have a different answer for |
| 1292 |
/// "preference order" vs "longest match.") |
| 1293 |
/// |
| 1294 |
/// ``` |
| 1295 |
/// use regex_automata::{dfa::onepass::DFA, Match, MatchKind}; |
| 1296 |
/// |
| 1297 |
/// let re = DFA::builder() |
| 1298 |
/// .configure(DFA::config().match_kind(MatchKind::All)) |
| 1299 |
/// .build(r"(abc)+?")?; |
| 1300 |
/// let mut cache = re.create_cache(); |
| 1301 |
/// let mut caps = re.create_captures(); |
| 1302 |
/// |
| 1303 |
/// re.captures(&mut cache, "abcabc", &mut caps); |
| 1304 |
/// // Normally, the non-greedy repetition would give us a 0..3 match. |
| 1305 |
/// assert_eq!(Some(Match::must(0, 0..6)), caps.get_match()); |
| 1306 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1307 |
/// ``` |
| 1308 |
#[inline] |
| 1309 |
pub fn config() -> Config { |
| 1310 |
Config::new() |
| 1311 |
} |
| 1312 |
|
| 1313 |
/// Return a builder for configuring the construction of a DFA. |
| 1314 |
/// |
| 1315 |
/// This is a convenience routine to avoid needing to import the |
| 1316 |
/// [`Builder`] type in common cases. |
| 1317 |
/// |
| 1318 |
/// # Example |
| 1319 |
/// |
| 1320 |
/// This example shows how to use the builder to disable UTF-8 mode. |
| 1321 |
/// |
| 1322 |
/// ``` |
| 1323 |
/// # if cfg!(miri) { return Ok(()); } // miri takes too long |
| 1324 |
/// use regex_automata::{ |
| 1325 |
/// dfa::onepass::DFA, |
| 1326 |
/// nfa::thompson, |
| 1327 |
/// util::syntax, |
| 1328 |
/// Match, |
| 1329 |
/// }; |
| 1330 |
/// |
| 1331 |
/// let re = DFA::builder() |
| 1332 |
/// .syntax(syntax::Config::new().utf8(false)) |
| 1333 |
/// .thompson(thompson::Config::new().utf8(false)) |
| 1334 |
/// .build(r"foo(?-u:[^b])ar.*")?; |
| 1335 |
/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); |
| 1336 |
/// |
| 1337 |
/// let haystack = b"foo\xFFarzz\xE2\x98\xFF\n"; |
| 1338 |
/// let expected = Some(Match::must(0, 0..8)); |
| 1339 |
/// re.captures(&mut cache, haystack, &mut caps); |
| 1340 |
/// assert_eq!(expected, caps.get_match()); |
| 1341 |
/// |
| 1342 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1343 |
/// ``` |
| 1344 |
#[inline] |
| 1345 |
pub fn builder() -> Builder { |
| 1346 |
Builder::new() |
| 1347 |
} |
| 1348 |
|
| 1349 |
/// Create a new empty set of capturing groups that is guaranteed to be |
| 1350 |
/// valid for the search APIs on this DFA. |
| 1351 |
/// |
| 1352 |
/// A `Captures` value created for a specific DFA cannot be used with any |
| 1353 |
/// other DFA. |
| 1354 |
/// |
| 1355 |
/// This is a convenience function for [`Captures::all`]. See the |
| 1356 |
/// [`Captures`] documentation for an explanation of its alternative |
| 1357 |
/// constructors that permit the DFA to do less work during a search, and |
| 1358 |
/// thus might make it faster. |
| 1359 |
#[inline] |
| 1360 |
pub fn create_captures(&self) -> Captures { |
| 1361 |
Captures::all(self.nfa.group_info().clone()) |
| 1362 |
} |
| 1363 |
|
| 1364 |
/// Create a new cache for this DFA. |
| 1365 |
/// |
| 1366 |
/// The cache returned should only be used for searches for this |
| 1367 |
/// DFA. If you want to reuse the cache for another DFA, then you |
| 1368 |
/// must call [`Cache::reset`] with that DFA (or, equivalently, |
| 1369 |
/// [`DFA::reset_cache`]). |
| 1370 |
#[inline] |
| 1371 |
pub fn create_cache(&self) -> Cache { |
| 1372 |
Cache::new(self) |
| 1373 |
} |
| 1374 |
|
| 1375 |
/// Reset the given cache such that it can be used for searching with the |
| 1376 |
/// this DFA (and only this DFA). |
| 1377 |
/// |
| 1378 |
/// A cache reset permits reusing memory already allocated in this cache |
| 1379 |
/// with a different DFA. |
| 1380 |
/// |
| 1381 |
/// # Example |
| 1382 |
/// |
| 1383 |
/// This shows how to re-purpose a cache for use with a different DFA. |
| 1384 |
/// |
| 1385 |
/// ``` |
| 1386 |
/// # if cfg!(miri) { return Ok(()); } // miri takes too long |
| 1387 |
/// use regex_automata::{dfa::onepass::DFA, Match}; |
| 1388 |
/// |
| 1389 |
/// let re1 = DFA::new(r"\w")?; |
| 1390 |
/// let re2 = DFA::new(r"\W")?; |
| 1391 |
/// let mut caps1 = re1.create_captures(); |
| 1392 |
/// let mut caps2 = re2.create_captures(); |
| 1393 |
/// |
| 1394 |
/// let mut cache = re1.create_cache(); |
| 1395 |
/// assert_eq!( |
| 1396 |
/// Some(Match::must(0, 0..2)), |
| 1397 |
/// { re1.captures(&mut cache, "Δ", &mut caps1); caps1.get_match() }, |
| 1398 |
/// ); |
| 1399 |
/// |
| 1400 |
/// // Using 'cache' with re2 is not allowed. It may result in panics or |
| 1401 |
/// // incorrect results. In order to re-purpose the cache, we must reset |
| 1402 |
/// // it with the one-pass DFA we'd like to use it with. |
| 1403 |
/// // |
| 1404 |
/// // Similarly, after this reset, using the cache with 're1' is also not |
| 1405 |
/// // allowed. |
| 1406 |
/// re2.reset_cache(&mut cache); |
| 1407 |
/// assert_eq!( |
| 1408 |
/// Some(Match::must(0, 0..3)), |
| 1409 |
/// { re2.captures(&mut cache, "☃", &mut caps2); caps2.get_match() }, |
| 1410 |
/// ); |
| 1411 |
/// |
| 1412 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1413 |
/// ``` |
| 1414 |
#[inline] |
| 1415 |
pub fn reset_cache(&self, cache: &mut Cache) { |
| 1416 |
cache.reset(self); |
| 1417 |
} |
| 1418 |
|
| 1419 |
/// Return the config for this one-pass DFA. |
| 1420 |
#[inline] |
| 1421 |
pub fn get_config(&self) -> &Config { |
| 1422 |
&self.config |
| 1423 |
} |
| 1424 |
|
| 1425 |
/// Returns a reference to the underlying NFA. |
| 1426 |
#[inline] |
| 1427 |
pub fn get_nfa(&self) -> &NFA { |
| 1428 |
&self.nfa |
| 1429 |
} |
| 1430 |
|
| 1431 |
/// Returns the total number of patterns compiled into this DFA. |
| 1432 |
/// |
| 1433 |
/// In the case of a DFA that contains no patterns, this returns `0`. |
| 1434 |
#[inline] |
| 1435 |
pub fn pattern_len(&self) -> usize { |
| 1436 |
self.get_nfa().pattern_len() |
| 1437 |
} |
| 1438 |
|
| 1439 |
/// Returns the total number of states in this one-pass DFA. |
| 1440 |
/// |
| 1441 |
/// Note that unlike dense or sparse DFAs, a one-pass DFA does not expose |
| 1442 |
/// a low level DFA API. Therefore, this routine has little use other than |
| 1443 |
/// being informational. |
| 1444 |
#[inline] |
| 1445 |
pub fn state_len(&self) -> usize { |
| 1446 |
self.table.len() >> self.stride2() |
| 1447 |
} |
| 1448 |
|
| 1449 |
/// Returns the total number of elements in the alphabet for this DFA. |
| 1450 |
/// |
| 1451 |
/// That is, this returns the total number of transitions that each |
| 1452 |
/// state in this DFA must have. The maximum alphabet size is 256, which |
| 1453 |
/// corresponds to each possible byte value. |
| 1454 |
/// |
| 1455 |
/// The alphabet size may be less than 256 though, and unless |
| 1456 |
/// [`Config::byte_classes`] is disabled, it is typically must less than |
| 1457 |
/// 256. Namely, bytes are grouped into equivalence classes such that no |
| 1458 |
/// two bytes in the same class can distinguish a match from a non-match. |
| 1459 |
/// For example, in the regex `^[a-z]+$`, the ASCII bytes `a-z` could |
| 1460 |
/// all be in the same equivalence class. This leads to a massive space |
| 1461 |
/// savings. |
| 1462 |
/// |
| 1463 |
/// Note though that the alphabet length does _not_ necessarily equal the |
| 1464 |
/// total stride space taken up by a single DFA state in the transition |
| 1465 |
/// table. Namely, for performance reasons, the stride is always the |
| 1466 |
/// smallest power of two that is greater than or equal to the alphabet |
| 1467 |
/// length. For this reason, [`DFA::stride`] or [`DFA::stride2`] are |
| 1468 |
/// often more useful. The alphabet length is typically useful only for |
| 1469 |
/// informational purposes. |
| 1470 |
/// |
| 1471 |
/// Note also that unlike dense or sparse DFAs, a one-pass DFA does |
| 1472 |
/// not have a special end-of-input (EOI) transition. This is because |
| 1473 |
/// a one-pass DFA handles look-around assertions explicitly (like the |
| 1474 |
/// [`PikeVM`](crate::nfa::thompson::pikevm::PikeVM)) and does not build |
| 1475 |
/// them into the transitions of the DFA. |
| 1476 |
#[inline] |
| 1477 |
pub fn alphabet_len(&self) -> usize { |
| 1478 |
self.alphabet_len |
| 1479 |
} |
| 1480 |
|
| 1481 |
/// Returns the total stride for every state in this DFA, expressed as the |
| 1482 |
/// exponent of a power of 2. The stride is the amount of space each state |
| 1483 |
/// takes up in the transition table, expressed as a number of transitions. |
| 1484 |
/// (Unused transitions map to dead states.) |
| 1485 |
/// |
| 1486 |
/// The stride of a DFA is always equivalent to the smallest power of |
| 1487 |
/// 2 that is greater than or equal to the DFA's alphabet length. This |
| 1488 |
/// definition uses extra space, but possibly permits faster translation |
| 1489 |
/// between state identifiers and their corresponding offsets in this DFA's |
| 1490 |
/// transition table. |
| 1491 |
/// |
| 1492 |
/// For example, if the DFA's stride is 16 transitions, then its `stride2` |
| 1493 |
/// is `4` since `2^4 = 16`. |
| 1494 |
/// |
| 1495 |
/// The minimum `stride2` value is `1` (corresponding to a stride of `2`) |
| 1496 |
/// while the maximum `stride2` value is `9` (corresponding to a stride |
| 1497 |
/// of `512`). The maximum in theory should be `8`, but because of some |
| 1498 |
/// implementation quirks that may be relaxed in the future, it is one more |
| 1499 |
/// than `8`. (Do note that a maximal stride is incredibly rare, as it |
| 1500 |
/// would imply that there is almost no redundant in the regex pattern.) |
| 1501 |
/// |
| 1502 |
/// Note that unlike dense or sparse DFAs, a one-pass DFA does not expose |
| 1503 |
/// a low level DFA API. Therefore, this routine has little use other than |
| 1504 |
/// being informational. |
| 1505 |
#[inline] |
| 1506 |
pub fn stride2(&self) -> usize { |
| 1507 |
self.stride2 |
| 1508 |
} |
| 1509 |
|
| 1510 |
/// Returns the total stride for every state in this DFA. This corresponds |
| 1511 |
/// to the total number of transitions used by each state in this DFA's |
| 1512 |
/// transition table. |
| 1513 |
/// |
| 1514 |
/// Please see [`DFA::stride2`] for more information. In particular, this |
| 1515 |
/// returns the stride as the number of transitions, where as `stride2` |
| 1516 |
/// returns it as the exponent of a power of 2. |
| 1517 |
/// |
| 1518 |
/// Note that unlike dense or sparse DFAs, a one-pass DFA does not expose |
| 1519 |
/// a low level DFA API. Therefore, this routine has little use other than |
| 1520 |
/// being informational. |
| 1521 |
#[inline] |
| 1522 |
pub fn stride(&self) -> usize { |
| 1523 |
1 << self.stride2() |
| 1524 |
} |
| 1525 |
|
| 1526 |
/// Returns the memory usage, in bytes, of this DFA. |
| 1527 |
/// |
| 1528 |
/// The memory usage is computed based on the number of bytes used to |
| 1529 |
/// represent this DFA. |
| 1530 |
/// |
| 1531 |
/// This does **not** include the stack size used up by this DFA. To |
| 1532 |
/// compute that, use `std::mem::size_of::<onepass::DFA>()`. |
| 1533 |
#[inline] |
| 1534 |
pub fn memory_usage(&self) -> usize { |
| 1535 |
use core::mem::size_of; |
| 1536 |
|
| 1537 |
self.table.len() * size_of::<Transition>() |
| 1538 |
+ self.starts.len() * size_of::<StateID>() |
| 1539 |
} |
| 1540 |
} |
| 1541 |
|
| 1542 |
impl DFA { |
| 1543 |
/// Executes an anchored leftmost forward search, and returns true if and |
| 1544 |
/// only if this one-pass DFA matches the given haystack. |
| 1545 |
/// |
| 1546 |
/// This routine may short circuit if it knows that scanning future |
| 1547 |
/// input will never lead to a different result. In particular, if the |
| 1548 |
/// underlying DFA enters a match state, then this routine will return |
| 1549 |
/// `true` immediately without inspecting any future input. (Consider how |
| 1550 |
/// this might make a difference given the regex `a+` on the haystack |
| 1551 |
/// `aaaaaaaaaaaaaaa`. This routine can stop after it sees the first `a`, |
| 1552 |
/// but routines like `find` need to continue searching because `+` is |
| 1553 |
/// greedy by default.) |
| 1554 |
/// |
| 1555 |
/// The given `Input` is forcefully set to use [`Anchored::Yes`] if the |
| 1556 |
/// given configuration was [`Anchored::No`] (which is the default). |
| 1557 |
/// |
| 1558 |
/// # Panics |
| 1559 |
/// |
| 1560 |
/// This routine panics if the search could not complete. This can occur |
| 1561 |
/// in the following circumstances: |
| 1562 |
/// |
| 1563 |
/// * When the provided `Input` configuration is not supported. For |
| 1564 |
/// example, by providing an unsupported anchor mode. Concretely, |
| 1565 |
/// this occurs when using [`Anchored::Pattern`] without enabling |
| 1566 |
/// [`Config::starts_for_each_pattern`]. |
| 1567 |
/// |
| 1568 |
/// When a search panics, callers cannot know whether a match exists or |
| 1569 |
/// not. |
| 1570 |
/// |
| 1571 |
/// Use [`DFA::try_search`] if you want to handle these panics as error |
| 1572 |
/// values instead. |
| 1573 |
/// |
| 1574 |
/// # Example |
| 1575 |
/// |
| 1576 |
/// This shows basic usage: |
| 1577 |
/// |
| 1578 |
/// ``` |
| 1579 |
/// use regex_automata::dfa::onepass::DFA; |
| 1580 |
/// |
| 1581 |
/// let re = DFA::new("foo[0-9]+bar")?; |
| 1582 |
/// let mut cache = re.create_cache(); |
| 1583 |
/// |
| 1584 |
/// assert!(re.is_match(&mut cache, "foo12345bar")); |
| 1585 |
/// assert!(!re.is_match(&mut cache, "foobar")); |
| 1586 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1587 |
/// ``` |
| 1588 |
/// |
| 1589 |
/// # Example: consistency with search APIs |
| 1590 |
/// |
| 1591 |
/// `is_match` is guaranteed to return `true` whenever `captures` returns |
| 1592 |
/// a match. This includes searches that are executed entirely within a |
| 1593 |
/// codepoint: |
| 1594 |
/// |
| 1595 |
/// ``` |
| 1596 |
/// use regex_automata::{dfa::onepass::DFA, Input}; |
| 1597 |
/// |
| 1598 |
/// let re = DFA::new("a*")?; |
| 1599 |
/// let mut cache = re.create_cache(); |
| 1600 |
/// |
| 1601 |
/// assert!(!re.is_match(&mut cache, Input::new("☃").span(1..2))); |
| 1602 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1603 |
/// ``` |
| 1604 |
/// |
| 1605 |
/// Notice that when UTF-8 mode is disabled, then the above reports a |
| 1606 |
/// match because the restriction against zero-width matches that split a |
| 1607 |
/// codepoint has been lifted: |
| 1608 |
/// |
| 1609 |
/// ``` |
| 1610 |
/// use regex_automata::{dfa::onepass::DFA, nfa::thompson::NFA, Input}; |
| 1611 |
/// |
| 1612 |
/// let re = DFA::builder() |
| 1613 |
/// .thompson(NFA::config().utf8(false)) |
| 1614 |
/// .build("a*")?; |
| 1615 |
/// let mut cache = re.create_cache(); |
| 1616 |
/// |
| 1617 |
/// assert!(re.is_match(&mut cache, Input::new("☃").span(1..2))); |
| 1618 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1619 |
/// ``` |
| 1620 |
#[inline] |
| 1621 |
pub fn is_match<'h, I: Into<Input<'h>>>( |
| 1622 |
&self, |
| 1623 |
cache: &mut Cache, |
| 1624 |
input: I, |
| 1625 |
) -> bool { |
| 1626 |
let mut input = input.into().earliest(true); |
| 1627 |
if matches!(input.get_anchored(), Anchored::No) { |
| 1628 |
input.set_anchored(Anchored::Yes); |
| 1629 |
} |
| 1630 |
self.try_search_slots(cache, &input, &mut []).unwrap().is_some() |
| 1631 |
} |
| 1632 |
|
| 1633 |
/// Executes an anchored leftmost forward search, and returns a `Match` if |
| 1634 |
/// and only if this one-pass DFA matches the given haystack. |
| 1635 |
/// |
| 1636 |
/// This routine only includes the overall match span. To get access to the |
| 1637 |
/// individual spans of each capturing group, use [`DFA::captures`]. |
| 1638 |
/// |
| 1639 |
/// The given `Input` is forcefully set to use [`Anchored::Yes`] if the |
| 1640 |
/// given configuration was [`Anchored::No`] (which is the default). |
| 1641 |
/// |
| 1642 |
/// # Panics |
| 1643 |
/// |
| 1644 |
/// This routine panics if the search could not complete. This can occur |
| 1645 |
/// in the following circumstances: |
| 1646 |
/// |
| 1647 |
/// * When the provided `Input` configuration is not supported. For |
| 1648 |
/// example, by providing an unsupported anchor mode. Concretely, |
| 1649 |
/// this occurs when using [`Anchored::Pattern`] without enabling |
| 1650 |
/// [`Config::starts_for_each_pattern`]. |
| 1651 |
/// |
| 1652 |
/// When a search panics, callers cannot know whether a match exists or |
| 1653 |
/// not. |
| 1654 |
/// |
| 1655 |
/// Use [`DFA::try_search`] if you want to handle these panics as error |
| 1656 |
/// values instead. |
| 1657 |
/// |
| 1658 |
/// # Example |
| 1659 |
/// |
| 1660 |
/// Leftmost first match semantics corresponds to the match with the |
| 1661 |
/// smallest starting offset, but where the end offset is determined by |
| 1662 |
/// preferring earlier branches in the original regular expression. For |
| 1663 |
/// example, `Sam|Samwise` will match `Sam` in `Samwise`, but `Samwise|Sam` |
| 1664 |
/// will match `Samwise` in `Samwise`. |
| 1665 |
/// |
| 1666 |
/// Generally speaking, the "leftmost first" match is how most backtracking |
| 1667 |
/// regular expressions tend to work. This is in contrast to POSIX-style |
| 1668 |
/// regular expressions that yield "leftmost longest" matches. Namely, |
| 1669 |
/// both `Sam|Samwise` and `Samwise|Sam` match `Samwise` when using |
| 1670 |
/// leftmost longest semantics. (This crate does not currently support |
| 1671 |
/// leftmost longest semantics.) |
| 1672 |
/// |
| 1673 |
/// ``` |
| 1674 |
/// use regex_automata::{dfa::onepass::DFA, Match}; |
| 1675 |
/// |
| 1676 |
/// let re = DFA::new("foo[0-9]+")?; |
| 1677 |
/// let mut cache = re.create_cache(); |
| 1678 |
/// let expected = Match::must(0, 0..8); |
| 1679 |
/// assert_eq!(Some(expected), re.find(&mut cache, "foo12345")); |
| 1680 |
/// |
| 1681 |
/// // Even though a match is found after reading the first byte (`a`), |
| 1682 |
/// // the leftmost first match semantics demand that we find the earliest |
| 1683 |
/// // match that prefers earlier parts of the pattern over later parts. |
| 1684 |
/// let re = DFA::new("abc|a")?; |
| 1685 |
/// let mut cache = re.create_cache(); |
| 1686 |
/// let expected = Match::must(0, 0..3); |
| 1687 |
/// assert_eq!(Some(expected), re.find(&mut cache, "abc")); |
| 1688 |
/// |
| 1689 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1690 |
/// ``` |
| 1691 |
#[inline] |
| 1692 |
pub fn find<'h, I: Into<Input<'h>>>( |
| 1693 |
&self, |
| 1694 |
cache: &mut Cache, |
| 1695 |
input: I, |
| 1696 |
) -> Option<Match> { |
| 1697 |
let mut input = input.into(); |
| 1698 |
if matches!(input.get_anchored(), Anchored::No) { |
| 1699 |
input.set_anchored(Anchored::Yes); |
| 1700 |
} |
| 1701 |
if self.get_nfa().pattern_len() == 1 { |
| 1702 |
let mut slots = [None, None]; |
| 1703 |
let pid = |
| 1704 |
self.try_search_slots(cache, &input, &mut slots).unwrap()?; |
| 1705 |
let start = slots[0].unwrap().get(); |
| 1706 |
let end = slots[1].unwrap().get(); |
| 1707 |
return Some(Match::new(pid, Span { start, end })); |
| 1708 |
} |
| 1709 |
let ginfo = self.get_nfa().group_info(); |
| 1710 |
let slots_len = ginfo.implicit_slot_len(); |
| 1711 |
let mut slots = vec![None; slots_len]; |
| 1712 |
let pid = self.try_search_slots(cache, &input, &mut slots).unwrap()?; |
| 1713 |
let start = slots[pid.as_usize() * 2].unwrap().get(); |
| 1714 |
let end = slots[pid.as_usize() * 2 + 1].unwrap().get(); |
| 1715 |
Some(Match::new(pid, Span { start, end })) |
| 1716 |
} |
| 1717 |
|
| 1718 |
/// Executes an anchored leftmost forward search and writes the spans |
| 1719 |
/// of capturing groups that participated in a match into the provided |
| 1720 |
/// [`Captures`] value. If no match was found, then [`Captures::is_match`] |
| 1721 |
/// is guaranteed to return `false`. |
| 1722 |
/// |
| 1723 |
/// The given `Input` is forcefully set to use [`Anchored::Yes`] if the |
| 1724 |
/// given configuration was [`Anchored::No`] (which is the default). |
| 1725 |
/// |
| 1726 |
/// # Panics |
| 1727 |
/// |
| 1728 |
/// This routine panics if the search could not complete. This can occur |
| 1729 |
/// in the following circumstances: |
| 1730 |
/// |
| 1731 |
/// * When the provided `Input` configuration is not supported. For |
| 1732 |
/// example, by providing an unsupported anchor mode. Concretely, |
| 1733 |
/// this occurs when using [`Anchored::Pattern`] without enabling |
| 1734 |
/// [`Config::starts_for_each_pattern`]. |
| 1735 |
/// |
| 1736 |
/// When a search panics, callers cannot know whether a match exists or |
| 1737 |
/// not. |
| 1738 |
/// |
| 1739 |
/// Use [`DFA::try_search`] if you want to handle these panics as error |
| 1740 |
/// values instead. |
| 1741 |
/// |
| 1742 |
/// # Example |
| 1743 |
/// |
| 1744 |
/// This shows a simple example of a one-pass regex that extracts |
| 1745 |
/// capturing group spans. |
| 1746 |
/// |
| 1747 |
/// ``` |
| 1748 |
/// use regex_automata::{dfa::onepass::DFA, Match, Span}; |
| 1749 |
/// |
| 1750 |
/// let re = DFA::new( |
| 1751 |
/// // Notice that we use ASCII here. The corresponding Unicode regex |
| 1752 |
/// // is sadly not one-pass. |
| 1753 |
/// "(?P<first>[[:alpha:]]+)[[:space:]]+(?P<last>[[:alpha:]]+)", |
| 1754 |
/// )?; |
| 1755 |
/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); |
| 1756 |
/// |
| 1757 |
/// re.captures(&mut cache, "Bruce Springsteen", &mut caps); |
| 1758 |
/// assert_eq!(Some(Match::must(0, 0..17)), caps.get_match()); |
| 1759 |
/// assert_eq!(Some(Span::from(0..5)), caps.get_group(1)); |
| 1760 |
/// assert_eq!(Some(Span::from(6..17)), caps.get_group_by_name("last")); |
| 1761 |
/// |
| 1762 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1763 |
/// ``` |
| 1764 |
#[inline] |
| 1765 |
pub fn captures<'h, I: Into<Input<'h>>>( |
| 1766 |
&self, |
| 1767 |
cache: &mut Cache, |
| 1768 |
input: I, |
| 1769 |
caps: &mut Captures, |
| 1770 |
) { |
| 1771 |
let mut input = input.into(); |
| 1772 |
if matches!(input.get_anchored(), Anchored::No) { |
| 1773 |
input.set_anchored(Anchored::Yes); |
| 1774 |
} |
| 1775 |
self.try_search(cache, &input, caps).unwrap(); |
| 1776 |
} |
| 1777 |
|
| 1778 |
/// Executes an anchored leftmost forward search and writes the spans |
| 1779 |
/// of capturing groups that participated in a match into the provided |
| 1780 |
/// [`Captures`] value. If no match was found, then [`Captures::is_match`] |
| 1781 |
/// is guaranteed to return `false`. |
| 1782 |
/// |
| 1783 |
/// The differences with [`DFA::captures`] are: |
| 1784 |
/// |
| 1785 |
/// 1. This returns an error instead of panicking if the search fails. |
| 1786 |
/// 2. Accepts an `&Input` instead of a `Into<Input>`. This permits reusing |
| 1787 |
/// the same input for multiple searches, which _may_ be important for |
| 1788 |
/// latency. |
| 1789 |
/// 3. This does not automatically change the [`Anchored`] mode from `No` |
| 1790 |
/// to `Yes`. Instead, if [`Input::anchored`] is `Anchored::No`, then an |
| 1791 |
/// error is returned. |
| 1792 |
/// |
| 1793 |
/// # Errors |
| 1794 |
/// |
| 1795 |
/// This routine errors if the search could not complete. This can occur |
| 1796 |
/// in the following circumstances: |
| 1797 |
/// |
| 1798 |
/// * When the provided `Input` configuration is not supported. For |
| 1799 |
/// example, by providing an unsupported anchor mode. Concretely, |
| 1800 |
/// this occurs when using [`Anchored::Pattern`] without enabling |
| 1801 |
/// [`Config::starts_for_each_pattern`]. |
| 1802 |
/// |
| 1803 |
/// When a search returns an error, callers cannot know whether a match |
| 1804 |
/// exists or not. |
| 1805 |
/// |
| 1806 |
/// # Example: specific pattern search |
| 1807 |
/// |
| 1808 |
/// This example shows how to build a multi-regex that permits searching |
| 1809 |
/// for specific patterns. Note that this is somewhat less useful than |
| 1810 |
/// in other regex engines, since a one-pass DFA by definition has no |
| 1811 |
/// ambiguity about which pattern can match at a position. That is, if it |
| 1812 |
/// were possible for two different patterns to match at the same starting |
| 1813 |
/// position, then the multi-regex would not be one-pass and construction |
| 1814 |
/// would have failed. |
| 1815 |
/// |
| 1816 |
/// Nevertheless, this can still be useful if you only care about matches |
| 1817 |
/// for a specific pattern, and want the DFA to report "no match" even if |
| 1818 |
/// some other pattern would have matched. |
| 1819 |
/// |
| 1820 |
/// Note that in order to make use of this functionality, |
| 1821 |
/// [`Config::starts_for_each_pattern`] must be enabled. It is disabled |
| 1822 |
/// by default since it may result in higher memory usage. |
| 1823 |
/// |
| 1824 |
/// ``` |
| 1825 |
/// use regex_automata::{ |
| 1826 |
/// dfa::onepass::DFA, Anchored, Input, Match, PatternID, |
| 1827 |
/// }; |
| 1828 |
/// |
| 1829 |
/// let re = DFA::builder() |
| 1830 |
/// .configure(DFA::config().starts_for_each_pattern(true)) |
| 1831 |
/// .build_many(&["[a-z]+", "[0-9]+"])?; |
| 1832 |
/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); |
| 1833 |
/// let haystack = "123abc"; |
| 1834 |
/// let input = Input::new(haystack).anchored(Anchored::Yes); |
| 1835 |
/// |
| 1836 |
/// // A normal multi-pattern search will show pattern 1 matches. |
| 1837 |
/// re.try_search(&mut cache, &input, &mut caps)?; |
| 1838 |
/// assert_eq!(Some(Match::must(1, 0..3)), caps.get_match()); |
| 1839 |
/// |
| 1840 |
/// // If we only want to report pattern 0 matches, then we'll get no |
| 1841 |
/// // match here. |
| 1842 |
/// let input = input.anchored(Anchored::Pattern(PatternID::must(0))); |
| 1843 |
/// re.try_search(&mut cache, &input, &mut caps)?; |
| 1844 |
/// assert_eq!(None, caps.get_match()); |
| 1845 |
/// |
| 1846 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1847 |
/// ``` |
| 1848 |
/// |
| 1849 |
/// # Example: specifying the bounds of a search |
| 1850 |
/// |
| 1851 |
/// This example shows how providing the bounds of a search can produce |
| 1852 |
/// different results than simply sub-slicing the haystack. |
| 1853 |
/// |
| 1854 |
/// ``` |
| 1855 |
/// # if cfg!(miri) { return Ok(()); } // miri takes too long |
| 1856 |
/// use regex_automata::{dfa::onepass::DFA, Anchored, Input, Match}; |
| 1857 |
/// |
| 1858 |
/// // one-pass DFAs fully support Unicode word boundaries! |
| 1859 |
/// // A sad joke is that a Unicode aware regex like \w+\s is not one-pass. |
| 1860 |
/// // :-( |
| 1861 |
/// let re = DFA::new(r"\b[0-9]{3}\b")?; |
| 1862 |
/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); |
| 1863 |
/// let haystack = "foo123bar"; |
| 1864 |
/// |
| 1865 |
/// // Since we sub-slice the haystack, the search doesn't know about |
| 1866 |
/// // the larger context and assumes that `123` is surrounded by word |
| 1867 |
/// // boundaries. And of course, the match position is reported relative |
| 1868 |
/// // to the sub-slice as well, which means we get `0..3` instead of |
| 1869 |
/// // `3..6`. |
| 1870 |
/// let expected = Some(Match::must(0, 0..3)); |
| 1871 |
/// let input = Input::new(&haystack[3..6]).anchored(Anchored::Yes); |
| 1872 |
/// re.try_search(&mut cache, &input, &mut caps)?; |
| 1873 |
/// assert_eq!(expected, caps.get_match()); |
| 1874 |
/// |
| 1875 |
/// // But if we provide the bounds of the search within the context of the |
| 1876 |
/// // entire haystack, then the search can take the surrounding context |
| 1877 |
/// // into account. (And if we did find a match, it would be reported |
| 1878 |
/// // as a valid offset into `haystack` instead of its sub-slice.) |
| 1879 |
/// let expected = None; |
| 1880 |
/// let input = Input::new(haystack).range(3..6).anchored(Anchored::Yes); |
| 1881 |
/// re.try_search(&mut cache, &input, &mut caps)?; |
| 1882 |
/// assert_eq!(expected, caps.get_match()); |
| 1883 |
/// |
| 1884 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1885 |
/// ``` |
| 1886 |
#[inline] |
| 1887 |
pub fn try_search( |
| 1888 |
&self, |
| 1889 |
cache: &mut Cache, |
| 1890 |
input: &Input<'_>, |
| 1891 |
caps: &mut Captures, |
| 1892 |
) -> Result<(), MatchError> { |
| 1893 |
let pid = self.try_search_slots(cache, input, caps.slots_mut())?; |
| 1894 |
caps.set_pattern(pid); |
| 1895 |
Ok(()) |
| 1896 |
} |
| 1897 |
|
| 1898 |
/// Executes an anchored leftmost forward search and writes the spans |
| 1899 |
/// of capturing groups that participated in a match into the provided |
| 1900 |
/// `slots`, and returns the matching pattern ID. The contents of the |
| 1901 |
/// slots for patterns other than the matching pattern are unspecified. If |
| 1902 |
/// no match was found, then `None` is returned and the contents of all |
| 1903 |
/// `slots` is unspecified. |
| 1904 |
/// |
| 1905 |
/// This is like [`DFA::try_search`], but it accepts a raw slots slice |
| 1906 |
/// instead of a `Captures` value. This is useful in contexts where you |
| 1907 |
/// don't want or need to allocate a `Captures`. |
| 1908 |
/// |
| 1909 |
/// It is legal to pass _any_ number of slots to this routine. If the regex |
| 1910 |
/// engine would otherwise write a slot offset that doesn't fit in the |
| 1911 |
/// provided slice, then it is simply skipped. In general though, there are |
| 1912 |
/// usually three slice lengths you might want to use: |
| 1913 |
/// |
| 1914 |
/// * An empty slice, if you only care about which pattern matched. |
| 1915 |
/// * A slice with |
| 1916 |
/// [`pattern_len() * 2`](crate::dfa::onepass::DFA::pattern_len) |
| 1917 |
/// slots, if you only care about the overall match spans for each matching |
| 1918 |
/// pattern. |
| 1919 |
/// * A slice with |
| 1920 |
/// [`slot_len()`](crate::util::captures::GroupInfo::slot_len) slots, which |
| 1921 |
/// permits recording match offsets for every capturing group in every |
| 1922 |
/// pattern. |
| 1923 |
/// |
| 1924 |
/// # Errors |
| 1925 |
/// |
| 1926 |
/// This routine errors if the search could not complete. This can occur |
| 1927 |
/// in the following circumstances: |
| 1928 |
/// |
| 1929 |
/// * When the provided `Input` configuration is not supported. For |
| 1930 |
/// example, by providing an unsupported anchor mode. Concretely, |
| 1931 |
/// this occurs when using [`Anchored::Pattern`] without enabling |
| 1932 |
/// [`Config::starts_for_each_pattern`]. |
| 1933 |
/// |
| 1934 |
/// When a search returns an error, callers cannot know whether a match |
| 1935 |
/// exists or not. |
| 1936 |
/// |
| 1937 |
/// # Example |
| 1938 |
/// |
| 1939 |
/// This example shows how to find the overall match offsets in a |
| 1940 |
/// multi-pattern search without allocating a `Captures` value. Indeed, we |
| 1941 |
/// can put our slots right on the stack. |
| 1942 |
/// |
| 1943 |
/// ``` |
| 1944 |
/// use regex_automata::{dfa::onepass::DFA, Anchored, Input, PatternID}; |
| 1945 |
/// |
| 1946 |
/// let re = DFA::new_many(&[ |
| 1947 |
/// r"[a-zA-Z]+", |
| 1948 |
/// r"[0-9]+", |
| 1949 |
/// ])?; |
| 1950 |
/// let mut cache = re.create_cache(); |
| 1951 |
/// let input = Input::new("123").anchored(Anchored::Yes); |
| 1952 |
/// |
| 1953 |
/// // We only care about the overall match offsets here, so we just |
| 1954 |
/// // allocate two slots for each pattern. Each slot records the start |
| 1955 |
/// // and end of the match. |
| 1956 |
/// let mut slots = [None; 4]; |
| 1957 |
/// let pid = re.try_search_slots(&mut cache, &input, &mut slots)?; |
| 1958 |
/// assert_eq!(Some(PatternID::must(1)), pid); |
| 1959 |
/// |
| 1960 |
/// // The overall match offsets are always at 'pid * 2' and 'pid * 2 + 1'. |
| 1961 |
/// // See 'GroupInfo' for more details on the mapping between groups and |
| 1962 |
/// // slot indices. |
| 1963 |
/// let slot_start = pid.unwrap().as_usize() * 2; |
| 1964 |
/// let slot_end = slot_start + 1; |
| 1965 |
/// assert_eq!(Some(0), slots[slot_start].map(|s| s.get())); |
| 1966 |
/// assert_eq!(Some(3), slots[slot_end].map(|s| s.get())); |
| 1967 |
/// |
| 1968 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 1969 |
/// ``` |
| 1970 |
#[inline] |
| 1971 |
pub fn try_search_slots( |
| 1972 |
&self, |
| 1973 |
cache: &mut Cache, |
| 1974 |
input: &Input<'_>, |
| 1975 |
slots: &mut [Option<NonMaxUsize>], |
| 1976 |
) -> Result<Option<PatternID>, MatchError> { |
| 1977 |
let utf8empty = self.get_nfa().has_empty() && self.get_nfa().is_utf8(); |
| 1978 |
if !utf8empty { |
| 1979 |
return self.try_search_slots_imp(cache, input, slots); |
| 1980 |
} |
| 1981 |
// See PikeVM::try_search_slots for why we do this. |
| 1982 |
let min = self.get_nfa().group_info().implicit_slot_len(); |
| 1983 |
if slots.len() >= min { |
| 1984 |
return self.try_search_slots_imp(cache, input, slots); |
| 1985 |
} |
| 1986 |
if self.get_nfa().pattern_len() == 1 { |
| 1987 |
let mut enough = [None, None]; |
| 1988 |
let got = self.try_search_slots_imp(cache, input, &mut enough)?; |
| 1989 |
// This is OK because we know `enough_slots` is strictly bigger |
| 1990 |
// than `slots`, otherwise this special case isn't reached. |
| 1991 |
slots.copy_from_slice(&enough[..slots.len()]); |
| 1992 |
return Ok(got); |
| 1993 |
} |
| 1994 |
let mut enough = vec![None; min]; |
| 1995 |
let got = self.try_search_slots_imp(cache, input, &mut enough)?; |
| 1996 |
// This is OK because we know `enough_slots` is strictly bigger than |
| 1997 |
// `slots`, otherwise this special case isn't reached. |
| 1998 |
slots.copy_from_slice(&enough[..slots.len()]); |
| 1999 |
Ok(got) |
| 2000 |
} |
| 2001 |
|
| 2002 |
#[inline(never)] |
| 2003 |
fn try_search_slots_imp( |
| 2004 |
&self, |
| 2005 |
cache: &mut Cache, |
| 2006 |
input: &Input<'_>, |
| 2007 |
slots: &mut [Option<NonMaxUsize>], |
| 2008 |
) -> Result<Option<PatternID>, MatchError> { |
| 2009 |
let utf8empty = self.get_nfa().has_empty() && self.get_nfa().is_utf8(); |
| 2010 |
match self.search_imp(cache, input, slots)? { |
| 2011 |
None => return Ok(None), |
| 2012 |
Some(pid) if !utf8empty => return Ok(Some(pid)), |
| 2013 |
Some(pid) => { |
| 2014 |
// These slot indices are always correct because we know our |
| 2015 |
// 'pid' is valid and thus we know that the slot indices for it |
| 2016 |
// are valid. |
| 2017 |
let slot_start = pid.as_usize().wrapping_mul(2); |
| 2018 |
let slot_end = slot_start.wrapping_add(1); |
| 2019 |
// OK because we know we have a match and we know our caller |
| 2020 |
// provided slots are big enough (which we make true above if |
| 2021 |
// the caller didn't). Namely, we're only here when 'utf8empty' |
| 2022 |
// is true, and when that's true, we require slots for every |
| 2023 |
// pattern. |
| 2024 |
let start = slots[slot_start].unwrap().get(); |
| 2025 |
let end = slots[slot_end].unwrap().get(); |
| 2026 |
// If our match splits a codepoint, then we cannot report is |
| 2027 |
// as a match. And since one-pass DFAs only support anchored |
| 2028 |
// searches, we don't try to skip ahead to find the next match. |
| 2029 |
// We can just quit with nothing. |
| 2030 |
if start == end && !input.is_char_boundary(start) { |
| 2031 |
return Ok(None); |
| 2032 |
} |
| 2033 |
Ok(Some(pid)) |
| 2034 |
} |
| 2035 |
} |
| 2036 |
} |
| 2037 |
} |
| 2038 |
|
| 2039 |
impl DFA { |
| 2040 |
fn search_imp( |
| 2041 |
&self, |
| 2042 |
cache: &mut Cache, |
| 2043 |
input: &Input<'_>, |
| 2044 |
slots: &mut [Option<NonMaxUsize>], |
| 2045 |
) -> Result<Option<PatternID>, MatchError> { |
| 2046 |
// PERF: Some ideas. I ran out of steam after my initial impl to try |
| 2047 |
// many of these. |
| 2048 |
// |
| 2049 |
// 1) Try doing more state shuffling. Right now, all we do is push |
| 2050 |
// match states to the end of the transition table so that we can do |
| 2051 |
// 'if sid >= self.min_match_id' to know whether we're in a match |
| 2052 |
// state or not. But what about doing something like dense DFAs and |
| 2053 |
// pushing dead, match and states with captures/looks all toward the |
| 2054 |
// beginning of the transition table. Then we could do 'if sid <= |
| 2055 |
// self.max_special_id', in which case, we need to do some special |
| 2056 |
// handling of some sort. Otherwise, we get the happy path, just |
| 2057 |
// like in a DFA search. The main argument against this is that the |
| 2058 |
// one-pass DFA is likely to be used most often with capturing groups |
| 2059 |
// and if capturing groups are common, then this might wind up being a |
| 2060 |
// pessimization. |
| 2061 |
// |
| 2062 |
// 2) Consider moving 'PatternEpsilons' out of the transition table. |
| 2063 |
// It is only needed for match states and usually a small minority of |
| 2064 |
// states are match states. Therefore, we're using an extra 'u64' for |
| 2065 |
// most states. |
| 2066 |
// |
| 2067 |
// 3) I played around with the match state handling and it seems like |
| 2068 |
// there is probably a lot left on the table for improvement. The |
| 2069 |
// key tension is that the 'find_match' routine is a giant mess, but |
| 2070 |
// splitting it out into a non-inlineable function is a non-starter |
| 2071 |
// because the match state might consume input, so 'find_match' COULD |
| 2072 |
// be called quite a lot, and a function call at that point would trash |
| 2073 |
// perf. In theory, we could detect whether a match state consumes |
| 2074 |
// input and then specialize our search routine based on that. In that |
| 2075 |
// case, maybe an extra function call is OK, but even then, it might be |
| 2076 |
// too much of a latency hit. Another idea is to just try and figure |
| 2077 |
// out how to reduce the code size of 'find_match'. RE2 has a trick |
| 2078 |
// here where the match handling isn't done if we know the next byte of |
| 2079 |
// input yields a match too. Maybe we adopt that? |
| 2080 |
// |
| 2081 |
// This just might be a tricky DFA to optimize. |
| 2082 |
|
| 2083 |
if input.is_done() { |
| 2084 |
return Ok(None); |
| 2085 |
} |
| 2086 |
// We unfortunately have a bit of book-keeping to do to set things |
| 2087 |
// up. We do have to setup our cache and clear all of our slots. In |
| 2088 |
// particular, clearing the slots is necessary for the case where we |
| 2089 |
// report a match, but one of the capturing groups didn't participate |
| 2090 |
// in the match but had a span set from a previous search. That would |
| 2091 |
// be bad. In theory, we could avoid all this slot clearing if we knew |
| 2092 |
// that every slot was always activated for every match. Then we would |
| 2093 |
// know they would always be overwritten when a match is found. |
| 2094 |
let explicit_slots_len = core::cmp::min( |
| 2095 |
Slots::LIMIT, |
| 2096 |
slots.len().saturating_sub(self.explicit_slot_start), |
| 2097 |
); |
| 2098 |
cache.setup_search(explicit_slots_len); |
| 2099 |
for slot in cache.explicit_slots() { |
| 2100 |
*slot = None; |
| 2101 |
} |
| 2102 |
for slot in slots.iter_mut() { |
| 2103 |
*slot = None; |
| 2104 |
} |
| 2105 |
// We set the starting slots for every pattern up front. This does |
| 2106 |
// increase our latency somewhat, but it avoids having to do it every |
| 2107 |
// time we see a match state (which could be many times in a single |
| 2108 |
// search if the match state consumes input). |
| 2109 |
for pid in self.nfa.patterns() { |
| 2110 |
let i = pid.as_usize() * 2; |
| 2111 |
if i >= slots.len() { |
| 2112 |
break; |
| 2113 |
} |
| 2114 |
slots[i] = NonMaxUsize::new(input.start()); |
| 2115 |
} |
| 2116 |
let mut pid = None; |
| 2117 |
let mut next_sid = match input.get_anchored() { |
| 2118 |
Anchored::Yes => self.start(), |
| 2119 |
Anchored::Pattern(pid) => self.start_pattern(pid)?, |
| 2120 |
Anchored::No => { |
| 2121 |
// If the regex is itself always anchored, then we're fine, |
| 2122 |
// even if the search is configured to be unanchored. |
| 2123 |
if !self.nfa.is_always_start_anchored() { |
| 2124 |
return Err(MatchError::unsupported_anchored( |
| 2125 |
Anchored::No, |
| 2126 |
)); |
| 2127 |
} |
| 2128 |
self.start() |
| 2129 |
} |
| 2130 |
}; |
| 2131 |
let leftmost_first = |
| 2132 |
matches!(self.config.get_match_kind(), MatchKind::LeftmostFirst); |
| 2133 |
for at in input.start()..input.end() { |
| 2134 |
let sid = next_sid; |
| 2135 |
let trans = self.transition(sid, input.haystack()[at]); |
| 2136 |
next_sid = trans.state_id(); |
| 2137 |
let epsilons = trans.epsilons(); |
| 2138 |
if sid >= self.min_match_id { |
| 2139 |
if self.find_match(cache, input, at, sid, slots, &mut pid) { |
| 2140 |
if input.get_earliest() |
| 2141 |
|| (leftmost_first && trans.match_wins()) |
| 2142 |
{ |
| 2143 |
return Ok(pid); |
| 2144 |
} |
| 2145 |
} |
| 2146 |
} |
| 2147 |
if sid == DEAD |
| 2148 |
|| (!epsilons.looks().is_empty() |
| 2149 |
&& !self.nfa.look_matcher().matches_set_inline( |
| 2150 |
epsilons.looks(), |
| 2151 |
input.haystack(), |
| 2152 |
at, |
| 2153 |
)) |
| 2154 |
{ |
| 2155 |
return Ok(pid); |
| 2156 |
} |
| 2157 |
epsilons.slots().apply(at, cache.explicit_slots()); |
| 2158 |
} |
| 2159 |
if next_sid >= self.min_match_id { |
| 2160 |
self.find_match( |
| 2161 |
cache, |
| 2162 |
input, |
| 2163 |
input.end(), |
| 2164 |
next_sid, |
| 2165 |
slots, |
| 2166 |
&mut pid, |
| 2167 |
); |
| 2168 |
} |
| 2169 |
Ok(pid) |
| 2170 |
} |
| 2171 |
|
| 2172 |
/// Assumes 'sid' is a match state and looks for whether a match can |
| 2173 |
/// be reported. If so, appropriate offsets are written to 'slots' and |
| 2174 |
/// 'matched_pid' is set to the matching pattern ID. |
| 2175 |
/// |
| 2176 |
/// Even when 'sid' is a match state, it's possible that a match won't |
| 2177 |
/// be reported. For example, when the conditional epsilon transitions |
| 2178 |
/// leading to the match state aren't satisfied at the given position in |
| 2179 |
/// the haystack. |
| 2180 |
#[cfg_attr(feature = "perf-inline", inline(always))] |
| 2181 |
fn find_match( |
| 2182 |
&self, |
| 2183 |
cache: &mut Cache, |
| 2184 |
input: &Input<'_>, |
| 2185 |
at: usize, |
| 2186 |
sid: StateID, |
| 2187 |
slots: &mut [Option<NonMaxUsize>], |
| 2188 |
matched_pid: &mut Option<PatternID>, |
| 2189 |
) -> bool { |
| 2190 |
debug_assert!(sid >= self.min_match_id); |
| 2191 |
let pateps = self.pattern_epsilons(sid); |
| 2192 |
let epsilons = pateps.epsilons(); |
| 2193 |
if !epsilons.looks().is_empty() |
| 2194 |
&& !self.nfa.look_matcher().matches_set_inline( |
| 2195 |
epsilons.looks(), |
| 2196 |
input.haystack(), |
| 2197 |
at, |
| 2198 |
) |
| 2199 |
{ |
| 2200 |
return false; |
| 2201 |
} |
| 2202 |
let pid = pateps.pattern_id_unchecked(); |
| 2203 |
// This calculation is always correct because we know our 'pid' is |
| 2204 |
// valid and thus we know that the slot indices for it are valid. |
| 2205 |
let slot_end = pid.as_usize().wrapping_mul(2).wrapping_add(1); |
| 2206 |
// Set the implicit 'end' slot for the matching pattern. (The 'start' |
| 2207 |
// slot was set at the beginning of the search.) |
| 2208 |
if slot_end < slots.len() { |
| 2209 |
slots[slot_end] = NonMaxUsize::new(at); |
| 2210 |
} |
| 2211 |
// If the caller provided enough room, copy the previously recorded |
| 2212 |
// explicit slots from our scratch space to the caller provided slots. |
| 2213 |
// We *also* need to set any explicit slots that are active as part of |
| 2214 |
// the path to the match state. |
| 2215 |
if self.explicit_slot_start < slots.len() { |
| 2216 |
// NOTE: The 'cache.explicit_slots()' slice is setup at the |
| 2217 |
// beginning of every search such that it is guaranteed to return a |
| 2218 |
// slice of length equivalent to 'slots[explicit_slot_start..]'. |
| 2219 |
slots[self.explicit_slot_start..] |
| 2220 |
.copy_from_slice(cache.explicit_slots()); |
| 2221 |
epsilons.slots().apply(at, &mut slots[self.explicit_slot_start..]); |
| 2222 |
} |
| 2223 |
*matched_pid = Some(pid); |
| 2224 |
true |
| 2225 |
} |
| 2226 |
} |
| 2227 |
|
| 2228 |
impl DFA { |
| 2229 |
/// Returns the anchored start state for matching any pattern in this DFA. |
| 2230 |
fn start(&self) -> StateID { |
| 2231 |
self.starts[0] |
| 2232 |
} |
| 2233 |
|
| 2234 |
/// Returns the anchored start state for matching the given pattern. If |
| 2235 |
/// 'starts_for_each_pattern' |
| 2236 |
/// was not enabled, then this returns an error. If the given pattern is |
| 2237 |
/// not in this DFA, then `Ok(None)` is returned. |
| 2238 |
fn start_pattern(&self, pid: PatternID) -> Result<StateID, MatchError> { |
| 2239 |
if !self.config.get_starts_for_each_pattern() { |
| 2240 |
return Err(MatchError::unsupported_anchored(Anchored::Pattern( |
| 2241 |
pid, |
| 2242 |
))); |
| 2243 |
} |
| 2244 |
// 'starts' always has non-zero length. The first entry is always the |
| 2245 |
// anchored starting state for all patterns, and the following entries |
| 2246 |
// are optional and correspond to the anchored starting states for |
| 2247 |
// patterns at pid+1. Thus, starts.len()-1 corresponds to the total |
| 2248 |
// number of patterns that one can explicitly search for. (And it may |
| 2249 |
// be zero.) |
| 2250 |
Ok(self.starts.get(pid.one_more()).copied().unwrap_or(DEAD)) |
| 2251 |
} |
| 2252 |
|
| 2253 |
/// Returns the transition from the given state ID and byte of input. The |
| 2254 |
/// transition includes the next state ID, the slots that should be saved |
| 2255 |
/// and any conditional epsilon transitions that must be satisfied in order |
| 2256 |
/// to take this transition. |
| 2257 |
fn transition(&self, sid: StateID, byte: u8) -> Transition { |
| 2258 |
let offset = sid.as_usize() << self.stride2(); |
| 2259 |
let class = self.classes.get(byte).as_usize(); |
| 2260 |
self.table[offset + class] |
| 2261 |
} |
| 2262 |
|
| 2263 |
/// Set the transition from the given state ID and byte of input to the |
| 2264 |
/// transition given. |
| 2265 |
fn set_transition(&mut self, sid: StateID, byte: u8, to: Transition) { |
| 2266 |
let offset = sid.as_usize() << self.stride2(); |
| 2267 |
let class = self.classes.get(byte).as_usize(); |
| 2268 |
self.table[offset + class] = to; |
| 2269 |
} |
| 2270 |
|
| 2271 |
/// Return an iterator of "sparse" transitions for the given state ID. |
| 2272 |
/// "sparse" in this context means that consecutive transitions that are |
| 2273 |
/// equivalent are returned as one group, and transitions to the DEAD state |
| 2274 |
/// are ignored. |
| 2275 |
/// |
| 2276 |
/// This winds up being useful for debug printing, since it's much terser |
| 2277 |
/// to display runs of equivalent transitions than the transition for every |
| 2278 |
/// possible byte value. Indeed, in practice, it's very common for runs |
| 2279 |
/// of equivalent transitions to appear. |
| 2280 |
fn sparse_transitions(&self, sid: StateID) -> SparseTransitionIter<'_> { |
| 2281 |
let start = sid.as_usize() << self.stride2(); |
| 2282 |
let end = start + self.alphabet_len(); |
| 2283 |
SparseTransitionIter { |
| 2284 |
it: self.table[start..end].iter().enumerate(), |
| 2285 |
cur: None, |
| 2286 |
} |
| 2287 |
} |
| 2288 |
|
| 2289 |
/// Return the pattern epsilons for the given state ID. |
| 2290 |
/// |
| 2291 |
/// If the given state ID does not correspond to a match state ID, then the |
| 2292 |
/// pattern epsilons returned is empty. |
| 2293 |
fn pattern_epsilons(&self, sid: StateID) -> PatternEpsilons { |
| 2294 |
let offset = sid.as_usize() << self.stride2(); |
| 2295 |
PatternEpsilons(self.table[offset + self.pateps_offset].0) |
| 2296 |
} |
| 2297 |
|
| 2298 |
/// Set the pattern epsilons for the given state ID. |
| 2299 |
fn set_pattern_epsilons(&mut self, sid: StateID, pateps: PatternEpsilons) { |
| 2300 |
let offset = sid.as_usize() << self.stride2(); |
| 2301 |
self.table[offset + self.pateps_offset] = Transition(pateps.0); |
| 2302 |
} |
| 2303 |
|
| 2304 |
/// Returns the state ID prior to the one given. This returns None if the |
| 2305 |
/// given ID is the first DFA state. |
| 2306 |
fn prev_state_id(&self, id: StateID) -> Option<StateID> { |
| 2307 |
if id == DEAD { |
| 2308 |
None |
| 2309 |
} else { |
| 2310 |
// CORRECTNESS: Since 'id' is not the first state, subtracting 1 |
| 2311 |
// is always valid. |
| 2312 |
Some(StateID::new_unchecked(id.as_usize().checked_sub(1).unwrap())) |
| 2313 |
} |
| 2314 |
} |
| 2315 |
|
| 2316 |
/// Returns the state ID of the last state in this DFA's transition table. |
| 2317 |
/// "last" in this context means the last state to appear in memory, i.e., |
| 2318 |
/// the one with the greatest ID. |
| 2319 |
fn last_state_id(&self) -> StateID { |
| 2320 |
// CORRECTNESS: A DFA table is always non-empty since it always at |
| 2321 |
// least contains a DEAD state. Since every state has the same stride, |
| 2322 |
// we can just compute what the "next" state ID would have been and |
| 2323 |
// then subtract 1 from it. |
| 2324 |
StateID::new_unchecked( |
| 2325 |
(self.table.len() >> self.stride2()).checked_sub(1).unwrap(), |
| 2326 |
) |
| 2327 |
} |
| 2328 |
|
| 2329 |
/// Move the transitions from 'id1' to 'id2' and vice versa. |
| 2330 |
/// |
| 2331 |
/// WARNING: This does not update the rest of the transition table to have |
| 2332 |
/// transitions to 'id1' changed to 'id2' and vice versa. This merely moves |
| 2333 |
/// the states in memory. |
| 2334 |
pub(super) fn swap_states(&mut self, id1: StateID, id2: StateID) { |
| 2335 |
let o1 = id1.as_usize() << self.stride2(); |
| 2336 |
let o2 = id2.as_usize() << self.stride2(); |
| 2337 |
for b in 0..self.stride() { |
| 2338 |
self.table.swap(o1 + b, o2 + b); |
| 2339 |
} |
| 2340 |
} |
| 2341 |
|
| 2342 |
/// Map all state IDs in this DFA (transition table + start states) |
| 2343 |
/// according to the closure given. |
| 2344 |
pub(super) fn remap(&mut self, map: impl Fn(StateID) -> StateID) { |
| 2345 |
for i in 0..self.state_len() { |
| 2346 |
let offset = i << self.stride2(); |
| 2347 |
for b in 0..self.alphabet_len() { |
| 2348 |
let next = self.table[offset + b].state_id(); |
| 2349 |
self.table[offset + b].set_state_id(map(next)); |
| 2350 |
} |
| 2351 |
} |
| 2352 |
for i in 0..self.starts.len() { |
| 2353 |
self.starts[i] = map(self.starts[i]); |
| 2354 |
} |
| 2355 |
} |
| 2356 |
} |
| 2357 |
|
| 2358 |
impl core::fmt::Debug for DFA { |
| 2359 |
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { |
| 2360 |
fn debug_state_transitions( |
| 2361 |
f: &mut core::fmt::Formatter, |
| 2362 |
dfa: &DFA, |
| 2363 |
sid: StateID, |
| 2364 |
) -> core::fmt::Result { |
| 2365 |
for (i, (start, end, trans)) in |
| 2366 |
dfa.sparse_transitions(sid).enumerate() |
| 2367 |
{ |
| 2368 |
let next = trans.state_id(); |
| 2369 |
if i > 0 { |
| 2370 |
write!(f, ", ")?; |
| 2371 |
} |
| 2372 |
if start == end { |
| 2373 |
write!( |
| 2374 |
f, |
| 2375 |
"{:?} => {:?}", |
| 2376 |
DebugByte(start), |
| 2377 |
next.as_usize(), |
| 2378 |
)?; |
| 2379 |
} else { |
| 2380 |
write!( |
| 2381 |
f, |
| 2382 |
"{:?}-{:?} => {:?}", |
| 2383 |
DebugByte(start), |
| 2384 |
DebugByte(end), |
| 2385 |
next.as_usize(), |
| 2386 |
)?; |
| 2387 |
} |
| 2388 |
if trans.match_wins() { |
| 2389 |
write!(f, " (MW)")?; |
| 2390 |
} |
| 2391 |
if !trans.epsilons().is_empty() { |
| 2392 |
write!(f, " ({:?})", trans.epsilons())?; |
| 2393 |
} |
| 2394 |
} |
| 2395 |
Ok(()) |
| 2396 |
} |
| 2397 |
|
| 2398 |
writeln!(f, "onepass::DFA(")?; |
| 2399 |
for index in 0..self.state_len() { |
| 2400 |
let sid = StateID::must(index); |
| 2401 |
let pateps = self.pattern_epsilons(sid); |
| 2402 |
if sid == DEAD { |
| 2403 |
write!(f, "D ")?; |
| 2404 |
} else if pateps.pattern_id().is_some() { |
| 2405 |
write!(f, "* ")?; |
| 2406 |
} else { |
| 2407 |
write!(f, " ")?; |
| 2408 |
} |
| 2409 |
write!(f, "{:06?}", sid.as_usize())?; |
| 2410 |
if !pateps.is_empty() { |
| 2411 |
write!(f, " ({:?})", pateps)?; |
| 2412 |
} |
| 2413 |
write!(f, ": ")?; |
| 2414 |
debug_state_transitions(f, self, sid)?; |
| 2415 |
write!(f, "\n")?; |
| 2416 |
} |
| 2417 |
writeln!(f, "")?; |
| 2418 |
for (i, &sid) in self.starts.iter().enumerate() { |
| 2419 |
if i == 0 { |
| 2420 |
writeln!(f, "START(ALL): {:?}", sid.as_usize())?; |
| 2421 |
} else { |
| 2422 |
writeln!( |
| 2423 |
f, |
| 2424 |
"START(pattern: {:?}): {:?}", |
| 2425 |
i - 1, |
| 2426 |
sid.as_usize(), |
| 2427 |
)?; |
| 2428 |
} |
| 2429 |
} |
| 2430 |
writeln!(f, "state length: {:?}", self.state_len())?; |
| 2431 |
writeln!(f, "pattern length: {:?}", self.pattern_len())?; |
| 2432 |
writeln!(f, ")")?; |
| 2433 |
Ok(()) |
| 2434 |
} |
| 2435 |
} |
| 2436 |
|
| 2437 |
/// An iterator over groups of consecutive equivalent transitions in a single |
| 2438 |
/// state. |
| 2439 |
#[derive(Debug)] |
| 2440 |
struct SparseTransitionIter<'a> { |
| 2441 |
it: core::iter::Enumerate<core::slice::Iter<'a, Transition>>, |
| 2442 |
cur: Option<(u8, u8, Transition)>, |
| 2443 |
} |
| 2444 |
|
| 2445 |
impl<'a> Iterator for SparseTransitionIter<'a> { |
| 2446 |
type Item = (u8, u8, Transition); |
| 2447 |
|
| 2448 |
fn next(&mut self) -> Option<(u8, u8, Transition)> { |
| 2449 |
while let Some((b, &trans)) = self.it.next() { |
| 2450 |
// Fine because we'll never have more than u8::MAX transitions in |
| 2451 |
// one state. |
| 2452 |
let b = b.as_u8(); |
| 2453 |
let (prev_start, prev_end, prev_trans) = match self.cur { |
| 2454 |
Some(t) => t, |
| 2455 |
None => { |
| 2456 |
self.cur = Some((b, b, trans)); |
| 2457 |
continue; |
| 2458 |
} |
| 2459 |
}; |
| 2460 |
if prev_trans == trans { |
| 2461 |
self.cur = Some((prev_start, b, prev_trans)); |
| 2462 |
} else { |
| 2463 |
self.cur = Some((b, b, trans)); |
| 2464 |
if prev_trans.state_id() != DEAD { |
| 2465 |
return Some((prev_start, prev_end, prev_trans)); |
| 2466 |
} |
| 2467 |
} |
| 2468 |
} |
| 2469 |
if let Some((start, end, trans)) = self.cur.take() { |
| 2470 |
if trans.state_id() != DEAD { |
| 2471 |
return Some((start, end, trans)); |
| 2472 |
} |
| 2473 |
} |
| 2474 |
None |
| 2475 |
} |
| 2476 |
} |
| 2477 |
|
| 2478 |
/// A cache represents mutable state that a one-pass [`DFA`] requires during a |
| 2479 |
/// search. |
| 2480 |
/// |
| 2481 |
/// For a given one-pass DFA, its corresponding cache may be created either via |
| 2482 |
/// [`DFA::create_cache`], or via [`Cache::new`]. They are equivalent in every |
| 2483 |
/// way, except the former does not require explicitly importing `Cache`. |
| 2484 |
/// |
| 2485 |
/// A particular `Cache` is coupled with the one-pass DFA from which it was |
| 2486 |
/// created. It may only be used with that one-pass DFA. A cache and its |
| 2487 |
/// allocations may be re-purposed via [`Cache::reset`], in which case, it can |
| 2488 |
/// only be used with the new one-pass DFA (and not the old one). |
| 2489 |
#[derive(Clone, Debug)] |
| 2490 |
pub struct Cache { |
| 2491 |
/// Scratch space used to store slots during a search. Basically, we use |
| 2492 |
/// the caller provided slots to store slots known when a match occurs. |
| 2493 |
/// But after a match occurs, we might continue a search but ultimately |
| 2494 |
/// fail to extend the match. When continuing the search, we need some |
| 2495 |
/// place to store candidate capture offsets without overwriting the slot |
| 2496 |
/// offsets recorded for the most recently seen match. |
| 2497 |
explicit_slots: Vec<Option<NonMaxUsize>>, |
| 2498 |
/// The number of slots in the caller-provided 'Captures' value for the |
| 2499 |
/// current search. This is always at most 'explicit_slots.len()', but |
| 2500 |
/// might be less than it, if the caller provided fewer slots to fill. |
| 2501 |
explicit_slot_len: usize, |
| 2502 |
} |
| 2503 |
|
| 2504 |
impl Cache { |
| 2505 |
/// Create a new [`onepass::DFA`](DFA) cache. |
| 2506 |
/// |
| 2507 |
/// A potentially more convenient routine to create a cache is |
| 2508 |
/// [`DFA::create_cache`], as it does not require also importing the |
| 2509 |
/// `Cache` type. |
| 2510 |
/// |
| 2511 |
/// If you want to reuse the returned `Cache` with some other one-pass DFA, |
| 2512 |
/// then you must call [`Cache::reset`] with the desired one-pass DFA. |
| 2513 |
pub fn new(re: &DFA) -> Cache { |
| 2514 |
let mut cache = Cache { explicit_slots: vec![], explicit_slot_len: 0 }; |
| 2515 |
cache.reset(re); |
| 2516 |
cache |
| 2517 |
} |
| 2518 |
|
| 2519 |
/// Reset this cache such that it can be used for searching with a |
| 2520 |
/// different [`onepass::DFA`](DFA). |
| 2521 |
/// |
| 2522 |
/// A cache reset permits reusing memory already allocated in this cache |
| 2523 |
/// with a different one-pass DFA. |
| 2524 |
/// |
| 2525 |
/// # Example |
| 2526 |
/// |
| 2527 |
/// This shows how to re-purpose a cache for use with a different one-pass |
| 2528 |
/// DFA. |
| 2529 |
/// |
| 2530 |
/// ``` |
| 2531 |
/// # if cfg!(miri) { return Ok(()); } // miri takes too long |
| 2532 |
/// use regex_automata::{dfa::onepass::DFA, Match}; |
| 2533 |
/// |
| 2534 |
/// let re1 = DFA::new(r"\w")?; |
| 2535 |
/// let re2 = DFA::new(r"\W")?; |
| 2536 |
/// let mut caps1 = re1.create_captures(); |
| 2537 |
/// let mut caps2 = re2.create_captures(); |
| 2538 |
/// |
| 2539 |
/// let mut cache = re1.create_cache(); |
| 2540 |
/// assert_eq!( |
| 2541 |
/// Some(Match::must(0, 0..2)), |
| 2542 |
/// { re1.captures(&mut cache, "Δ", &mut caps1); caps1.get_match() }, |
| 2543 |
/// ); |
| 2544 |
/// |
| 2545 |
/// // Using 'cache' with re2 is not allowed. It may result in panics or |
| 2546 |
/// // incorrect results. In order to re-purpose the cache, we must reset |
| 2547 |
/// // it with the one-pass DFA we'd like to use it with. |
| 2548 |
/// // |
| 2549 |
/// // Similarly, after this reset, using the cache with 're1' is also not |
| 2550 |
/// // allowed. |
| 2551 |
/// re2.reset_cache(&mut cache); |
| 2552 |
/// assert_eq!( |
| 2553 |
/// Some(Match::must(0, 0..3)), |
| 2554 |
/// { re2.captures(&mut cache, "☃", &mut caps2); caps2.get_match() }, |
| 2555 |
/// ); |
| 2556 |
/// |
| 2557 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 2558 |
/// ``` |
| 2559 |
pub fn reset(&mut self, re: &DFA) { |
| 2560 |
let explicit_slot_len = re.get_nfa().group_info().explicit_slot_len(); |
| 2561 |
self.explicit_slots.resize(explicit_slot_len, None); |
| 2562 |
self.explicit_slot_len = explicit_slot_len; |
| 2563 |
} |
| 2564 |
|
| 2565 |
/// Returns the heap memory usage, in bytes, of this cache. |
| 2566 |
/// |
| 2567 |
/// This does **not** include the stack size used up by this cache. To |
| 2568 |
/// compute that, use `std::mem::size_of::<Cache>()`. |
| 2569 |
pub fn memory_usage(&self) -> usize { |
| 2570 |
self.explicit_slots.len() * core::mem::size_of::<Option<NonMaxUsize>>() |
| 2571 |
} |
| 2572 |
|
| 2573 |
fn explicit_slots(&mut self) -> &mut [Option<NonMaxUsize>] { |
| 2574 |
&mut self.explicit_slots[..self.explicit_slot_len] |
| 2575 |
} |
| 2576 |
|
| 2577 |
fn setup_search(&mut self, explicit_slot_len: usize) { |
| 2578 |
self.explicit_slot_len = explicit_slot_len; |
| 2579 |
} |
| 2580 |
} |
| 2581 |
|
| 2582 |
/// Represents a single transition in a one-pass DFA. |
| 2583 |
/// |
| 2584 |
/// The high 21 bits corresponds to the state ID. The bit following corresponds |
| 2585 |
/// to the special "match wins" flag. The remaining low 42 bits corresponds to |
| 2586 |
/// the transition epsilons, which contains the slots that should be saved when |
| 2587 |
/// this transition is followed and the conditional epsilon transitions that |
| 2588 |
/// must be satisfied in order to follow this transition. |
| 2589 |
#[derive(Clone, Copy, Eq, PartialEq)] |
| 2590 |
struct Transition(u64); |
| 2591 |
|
| 2592 |
impl Transition { |
| 2593 |
const STATE_ID_BITS: u64 = 21; |
| 2594 |
const STATE_ID_SHIFT: u64 = 64 - Transition::STATE_ID_BITS; |
| 2595 |
const STATE_ID_LIMIT: u64 = 1 << Transition::STATE_ID_BITS; |
| 2596 |
const MATCH_WINS_SHIFT: u64 = 64 - (Transition::STATE_ID_BITS + 1); |
| 2597 |
const INFO_MASK: u64 = 0x000003FF_FFFFFFFF; |
| 2598 |
|
| 2599 |
/// Return a new transition to the given state ID with the given epsilons. |
| 2600 |
fn new(match_wins: bool, sid: StateID, epsilons: Epsilons) -> Transition { |
| 2601 |
let match_wins = |
| 2602 |
if match_wins { 1 << Transition::MATCH_WINS_SHIFT } else { 0 }; |
| 2603 |
let sid = sid.as_u64() << Transition::STATE_ID_SHIFT; |
| 2604 |
Transition(sid | match_wins | epsilons.0) |
| 2605 |
} |
| 2606 |
|
| 2607 |
/// Returns true if and only if this transition points to the DEAD state. |
| 2608 |
fn is_dead(self) -> bool { |
| 2609 |
self.state_id() == DEAD |
| 2610 |
} |
| 2611 |
|
| 2612 |
/// Return whether this transition has a "match wins" property. |
| 2613 |
/// |
| 2614 |
/// When a transition has this property, it means that if a match has been |
| 2615 |
/// found and the search uses leftmost-first semantics, then that match |
| 2616 |
/// should be returned immediately instead of continuing on. |
| 2617 |
/// |
| 2618 |
/// The "match wins" name comes from RE2, which uses a pretty much |
| 2619 |
/// identical mechanism for implementing leftmost-first semantics. |
| 2620 |
fn match_wins(&self) -> bool { |
| 2621 |
(self.0 >> Transition::MATCH_WINS_SHIFT & 1) == 1 |
| 2622 |
} |
| 2623 |
|
| 2624 |
/// Return the "next" state ID that this transition points to. |
| 2625 |
fn state_id(&self) -> StateID { |
| 2626 |
// OK because a Transition has a valid StateID in its upper bits by |
| 2627 |
// construction. The cast to usize is also correct, even on 16-bit |
| 2628 |
// targets because, again, we know the upper bits is a valid StateID, |
| 2629 |
// which can never overflow usize on any supported target. |
| 2630 |
StateID::new_unchecked( |
| 2631 |
(self.0 >> Transition::STATE_ID_SHIFT).as_usize(), |
| 2632 |
) |
| 2633 |
} |
| 2634 |
|
| 2635 |
/// Set the "next" state ID in this transition. |
| 2636 |
fn set_state_id(&mut self, sid: StateID) { |
| 2637 |
*self = Transition::new(self.match_wins(), sid, self.epsilons()); |
| 2638 |
} |
| 2639 |
|
| 2640 |
/// Return the epsilons embedded in this transition. |
| 2641 |
fn epsilons(&self) -> Epsilons { |
| 2642 |
Epsilons(self.0 & Transition::INFO_MASK) |
| 2643 |
} |
| 2644 |
} |
| 2645 |
|
| 2646 |
impl core::fmt::Debug for Transition { |
| 2647 |
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { |
| 2648 |
if self.is_dead() { |
| 2649 |
return write!(f, "0"); |
| 2650 |
} |
| 2651 |
write!(f, "{}", self.state_id().as_usize())?; |
| 2652 |
if self.match_wins() { |
| 2653 |
write!(f, "-MW")?; |
| 2654 |
} |
| 2655 |
if !self.epsilons().is_empty() { |
| 2656 |
write!(f, "-{:?}", self.epsilons())?; |
| 2657 |
} |
| 2658 |
Ok(()) |
| 2659 |
} |
| 2660 |
} |
| 2661 |
|
| 2662 |
/// A representation of a match state's pattern ID along with the epsilons for |
| 2663 |
/// when a match occurs. |
| 2664 |
/// |
| 2665 |
/// A match state in a one-pass DFA, unlike in a more general DFA, has exactly |
| 2666 |
/// one pattern ID. If it had more, then the original NFA would not have been |
| 2667 |
/// one-pass. |
| 2668 |
/// |
| 2669 |
/// The "epsilons" part of this corresponds to what was found in the epsilon |
| 2670 |
/// transitions between the transition taken in the last byte of input and the |
| 2671 |
/// ultimate match state. This might include saving slots and/or conditional |
| 2672 |
/// epsilon transitions that must be satisfied before one can report the match. |
| 2673 |
/// |
| 2674 |
/// Technically, every state has room for a 'PatternEpsilons', but it is only |
| 2675 |
/// ever non-empty for match states. |
| 2676 |
#[derive(Clone, Copy)] |
| 2677 |
struct PatternEpsilons(u64); |
| 2678 |
|
| 2679 |
impl PatternEpsilons { |
| 2680 |
const PATTERN_ID_BITS: u64 = 22; |
| 2681 |
const PATTERN_ID_SHIFT: u64 = 64 - PatternEpsilons::PATTERN_ID_BITS; |
| 2682 |
// A sentinel value indicating that this is not a match state. We don't |
| 2683 |
// use 0 since 0 is a valid pattern ID. |
| 2684 |
const PATTERN_ID_NONE: u64 = 0x00000000_003FFFFF; |
| 2685 |
const PATTERN_ID_LIMIT: u64 = PatternEpsilons::PATTERN_ID_NONE; |
| 2686 |
const PATTERN_ID_MASK: u64 = 0xFFFFFC00_00000000; |
| 2687 |
const EPSILONS_MASK: u64 = 0x000003FF_FFFFFFFF; |
| 2688 |
|
| 2689 |
/// Return a new empty pattern epsilons that has no pattern ID and has no |
| 2690 |
/// epsilons. This is suitable for non-match states. |
| 2691 |
fn empty() -> PatternEpsilons { |
| 2692 |
PatternEpsilons( |
| 2693 |
PatternEpsilons::PATTERN_ID_NONE |
| 2694 |
<< PatternEpsilons::PATTERN_ID_SHIFT, |
| 2695 |
) |
| 2696 |
} |
| 2697 |
|
| 2698 |
/// Whether this pattern epsilons is empty or not. It's empty when it has |
| 2699 |
/// no pattern ID and an empty epsilons. |
| 2700 |
fn is_empty(self) -> bool { |
| 2701 |
self.pattern_id().is_none() && self.epsilons().is_empty() |
| 2702 |
} |
| 2703 |
|
| 2704 |
/// Return the pattern ID in this pattern epsilons if one exists. |
| 2705 |
fn pattern_id(self) -> Option<PatternID> { |
| 2706 |
let pid = self.0 >> PatternEpsilons::PATTERN_ID_SHIFT; |
| 2707 |
if pid == PatternEpsilons::PATTERN_ID_LIMIT { |
| 2708 |
None |
| 2709 |
} else { |
| 2710 |
Some(PatternID::new_unchecked(pid.as_usize())) |
| 2711 |
} |
| 2712 |
} |
| 2713 |
|
| 2714 |
/// Returns the pattern ID without checking whether it's valid. If this is |
| 2715 |
/// called and there is no pattern ID in this `PatternEpsilons`, then this |
| 2716 |
/// will likely produce an incorrect result or possibly even a panic or |
| 2717 |
/// an overflow. But safety will not be violated. |
| 2718 |
/// |
| 2719 |
/// This is useful when you know a particular state is a match state. If |
| 2720 |
/// it's a match state, then it must have a pattern ID. |
| 2721 |
fn pattern_id_unchecked(self) -> PatternID { |
| 2722 |
let pid = self.0 >> PatternEpsilons::PATTERN_ID_SHIFT; |
| 2723 |
PatternID::new_unchecked(pid.as_usize()) |
| 2724 |
} |
| 2725 |
|
| 2726 |
/// Return a new pattern epsilons with the given pattern ID, but the same |
| 2727 |
/// epsilons. |
| 2728 |
fn set_pattern_id(self, pid: PatternID) -> PatternEpsilons { |
| 2729 |
PatternEpsilons( |
| 2730 |
(pid.as_u64() << PatternEpsilons::PATTERN_ID_SHIFT) |
| 2731 |
| (self.0 & PatternEpsilons::EPSILONS_MASK), |
| 2732 |
) |
| 2733 |
} |
| 2734 |
|
| 2735 |
/// Return the epsilons part of this pattern epsilons. |
| 2736 |
fn epsilons(self) -> Epsilons { |
| 2737 |
Epsilons(self.0 & PatternEpsilons::EPSILONS_MASK) |
| 2738 |
} |
| 2739 |
|
| 2740 |
/// Return a new pattern epsilons with the given epsilons, but the same |
| 2741 |
/// pattern ID. |
| 2742 |
fn set_epsilons(self, epsilons: Epsilons) -> PatternEpsilons { |
| 2743 |
PatternEpsilons( |
| 2744 |
(self.0 & PatternEpsilons::PATTERN_ID_MASK) |
| 2745 |
| (u64::from(epsilons.0) & PatternEpsilons::EPSILONS_MASK), |
| 2746 |
) |
| 2747 |
} |
| 2748 |
} |
| 2749 |
|
| 2750 |
impl core::fmt::Debug for PatternEpsilons { |
| 2751 |
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { |
| 2752 |
if self.is_empty() { |
| 2753 |
return write!(f, "N/A"); |
| 2754 |
} |
| 2755 |
if let Some(pid) = self.pattern_id() { |
| 2756 |
write!(f, "{}", pid.as_usize())?; |
| 2757 |
} |
| 2758 |
if !self.epsilons().is_empty() { |
| 2759 |
if self.pattern_id().is_some() { |
| 2760 |
write!(f, "/")?; |
| 2761 |
} |
| 2762 |
write!(f, "{:?}", self.epsilons())?; |
| 2763 |
} |
| 2764 |
Ok(()) |
| 2765 |
} |
| 2766 |
} |
| 2767 |
|
| 2768 |
/// Epsilons represents all of the NFA epsilons transitions that went into a |
| 2769 |
/// single transition in a single DFA state. In this case, it only represents |
| 2770 |
/// the epsilon transitions that have some kind of non-consuming side effect: |
| 2771 |
/// either the transition requires storing the current position of the search |
| 2772 |
/// into a slot, or the transition is conditional and requires the current |
| 2773 |
/// position in the input to satisfy an assertion before the transition may be |
| 2774 |
/// taken. |
| 2775 |
/// |
| 2776 |
/// This folds the cumulative effect of a group of NFA states (all connected |
| 2777 |
/// by epsilon transitions) down into a single set of bits. While these bits |
| 2778 |
/// can represent all possible conditional epsilon transitions, it only permits |
| 2779 |
/// storing up to a somewhat small number of slots. |
| 2780 |
/// |
| 2781 |
/// Epsilons is represented as a 42-bit integer. For example, it is packed into |
| 2782 |
/// the lower 42 bits of a `Transition`. (Where the high 22 bits contains a |
| 2783 |
/// `StateID` and a special "match wins" property.) |
| 2784 |
#[derive(Clone, Copy)] |
| 2785 |
struct Epsilons(u64); |
| 2786 |
|
| 2787 |
impl Epsilons { |
| 2788 |
const SLOT_MASK: u64 = 0x000003FF_FFFFFC00; |
| 2789 |
const SLOT_SHIFT: u64 = 10; |
| 2790 |
const LOOK_MASK: u64 = 0x00000000_000003FF; |
| 2791 |
|
| 2792 |
/// Create a new empty epsilons. It has no slots and no assertions that |
| 2793 |
/// need to be satisfied. |
| 2794 |
fn empty() -> Epsilons { |
| 2795 |
Epsilons(0) |
| 2796 |
} |
| 2797 |
|
| 2798 |
/// Returns true if this epsilons contains no slots and no assertions. |
| 2799 |
fn is_empty(self) -> bool { |
| 2800 |
self.0 == 0 |
| 2801 |
} |
| 2802 |
|
| 2803 |
/// Returns the slot epsilon transitions. |
| 2804 |
fn slots(self) -> Slots { |
| 2805 |
Slots((self.0 >> Epsilons::SLOT_SHIFT).low_u32()) |
| 2806 |
} |
| 2807 |
|
| 2808 |
/// Set the slot epsilon transitions. |
| 2809 |
fn set_slots(self, slots: Slots) -> Epsilons { |
| 2810 |
Epsilons( |
| 2811 |
(u64::from(slots.0) << Epsilons::SLOT_SHIFT) |
| 2812 |
| (self.0 & Epsilons::LOOK_MASK), |
| 2813 |
) |
| 2814 |
} |
| 2815 |
|
| 2816 |
/// Return the set of look-around assertions in these epsilon transitions. |
| 2817 |
fn looks(self) -> LookSet { |
| 2818 |
LookSet { bits: (self.0 & Epsilons::LOOK_MASK).low_u32() } |
| 2819 |
} |
| 2820 |
|
| 2821 |
/// Set the look-around assertions on these epsilon transitions. |
| 2822 |
fn set_looks(self, look_set: LookSet) -> Epsilons { |
| 2823 |
Epsilons( |
| 2824 |
(self.0 & Epsilons::SLOT_MASK) |
| 2825 |
| (u64::from(look_set.bits) & Epsilons::LOOK_MASK), |
| 2826 |
) |
| 2827 |
} |
| 2828 |
} |
| 2829 |
|
| 2830 |
impl core::fmt::Debug for Epsilons { |
| 2831 |
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { |
| 2832 |
let mut wrote = false; |
| 2833 |
if !self.slots().is_empty() { |
| 2834 |
write!(f, "{:?}", self.slots())?; |
| 2835 |
wrote = true; |
| 2836 |
} |
| 2837 |
if !self.looks().is_empty() { |
| 2838 |
if wrote { |
| 2839 |
write!(f, "/")?; |
| 2840 |
} |
| 2841 |
write!(f, "{:?}", self.looks())?; |
| 2842 |
wrote = true; |
| 2843 |
} |
| 2844 |
if !wrote { |
| 2845 |
write!(f, "N/A")?; |
| 2846 |
} |
| 2847 |
Ok(()) |
| 2848 |
} |
| 2849 |
} |
| 2850 |
|
| 2851 |
/// The set of epsilon transitions indicating that the current position in a |
| 2852 |
/// search should be saved to a slot. |
| 2853 |
/// |
| 2854 |
/// This *only* represents explicit slots. So for example, the pattern |
| 2855 |
/// `[a-z]+([0-9]+)([a-z]+)` has: |
| 2856 |
/// |
| 2857 |
/// * 3 capturing groups, thus 6 slots. |
| 2858 |
/// * 1 implicit capturing group, thus 2 implicit slots. |
| 2859 |
/// * 2 explicit capturing groups, thus 4 explicit slots. |
| 2860 |
/// |
| 2861 |
/// While implicit slots are represented by epsilon transitions in an NFA, we |
| 2862 |
/// do not explicitly represent them here. Instead, implicit slots are assumed |
| 2863 |
/// to be present and handled automatically in the search code. Therefore, |
| 2864 |
/// that means we only need to represent explicit slots in our epsilon |
| 2865 |
/// transitions. |
| 2866 |
/// |
| 2867 |
/// Its representation is a bit set. The bit 'i' is set if and only if there |
| 2868 |
/// exists an explicit slot at index 'c', where 'c = (#patterns * 2) + i'. That |
| 2869 |
/// is, the bit 'i' corresponds to the first explicit slot and the first |
| 2870 |
/// explicit slot appears immediately following the last implicit slot. (If |
| 2871 |
/// this is confusing, see `GroupInfo` for more details on how slots works.) |
| 2872 |
/// |
| 2873 |
/// A single `Slots` represents all the active slots in a sub-graph of an NFA, |
| 2874 |
/// where all the states are connected by epsilon transitions. In effect, when |
| 2875 |
/// traversing the one-pass DFA during a search, all slots set in a particular |
| 2876 |
/// transition must be captured by recording the current search position. |
| 2877 |
/// |
| 2878 |
/// The API of `Slots` requires the caller to handle the explicit slot offset. |
| 2879 |
/// That is, a `Slots` doesn't know where the explicit slots start for a |
| 2880 |
/// particular NFA. Thus, if the callers see's the bit 'i' is set, then they |
| 2881 |
/// need to do the arithmetic above to find 'c', which is the real actual slot |
| 2882 |
/// index in the corresponding NFA. |
| 2883 |
#[derive(Clone, Copy)] |
| 2884 |
struct Slots(u32); |
| 2885 |
|
| 2886 |
impl Slots { |
| 2887 |
const LIMIT: usize = 32; |
| 2888 |
|
| 2889 |
/// Insert the slot at the given bit index. |
| 2890 |
fn insert(self, slot: usize) -> Slots { |
| 2891 |
debug_assert!(slot < Slots::LIMIT); |
| 2892 |
Slots(self.0 | (1 << slot.as_u32())) |
| 2893 |
} |
| 2894 |
|
| 2895 |
/// Remove the slot at the given bit index. |
| 2896 |
fn remove(self, slot: usize) -> Slots { |
| 2897 |
debug_assert!(slot < Slots::LIMIT); |
| 2898 |
Slots(self.0 & !(1 << slot.as_u32())) |
| 2899 |
} |
| 2900 |
|
| 2901 |
/// Returns true if and only if this set contains no slots. |
| 2902 |
fn is_empty(self) -> bool { |
| 2903 |
self.0 == 0 |
| 2904 |
} |
| 2905 |
|
| 2906 |
/// Returns an iterator over all of the set bits in this set. |
| 2907 |
fn iter(self) -> SlotsIter { |
| 2908 |
SlotsIter { slots: self } |
| 2909 |
} |
| 2910 |
|
| 2911 |
/// For the position `at` in the current haystack, copy it to |
| 2912 |
/// `caller_explicit_slots` for all slots that are in this set. |
| 2913 |
/// |
| 2914 |
/// Callers may pass a slice of any length. Slots in this set bigger than |
| 2915 |
/// the length of the given explicit slots are simply skipped. |
| 2916 |
/// |
| 2917 |
/// The slice *must* correspond only to the explicit slots and the first |
| 2918 |
/// element of the slice must always correspond to the first explicit slot |
| 2919 |
/// in the corresponding NFA. |
| 2920 |
fn apply( |
| 2921 |
self, |
| 2922 |
at: usize, |
| 2923 |
caller_explicit_slots: &mut [Option<NonMaxUsize>], |
| 2924 |
) { |
| 2925 |
if self.is_empty() { |
| 2926 |
return; |
| 2927 |
} |
| 2928 |
let at = NonMaxUsize::new(at); |
| 2929 |
for slot in self.iter() { |
| 2930 |
if slot >= caller_explicit_slots.len() { |
| 2931 |
break; |
| 2932 |
} |
| 2933 |
caller_explicit_slots[slot] = at; |
| 2934 |
} |
| 2935 |
} |
| 2936 |
} |
| 2937 |
|
| 2938 |
impl core::fmt::Debug for Slots { |
| 2939 |
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { |
| 2940 |
write!(f, "S")?; |
| 2941 |
for slot in self.iter() { |
| 2942 |
write!(f, "-{:?}", slot)?; |
| 2943 |
} |
| 2944 |
Ok(()) |
| 2945 |
} |
| 2946 |
} |
| 2947 |
|
| 2948 |
/// An iterator over all of the bits set in a slot set. |
| 2949 |
/// |
| 2950 |
/// This returns the bit index that is set, so callers may need to offset it |
| 2951 |
/// to get the actual NFA slot index. |
| 2952 |
#[derive(Debug)] |
| 2953 |
struct SlotsIter { |
| 2954 |
slots: Slots, |
| 2955 |
} |
| 2956 |
|
| 2957 |
impl Iterator for SlotsIter { |
| 2958 |
type Item = usize; |
| 2959 |
|
| 2960 |
fn next(&mut self) -> Option<usize> { |
| 2961 |
// Number of zeroes here is always <= u8::MAX, and so fits in a usize. |
| 2962 |
let slot = self.slots.0.trailing_zeros().as_usize(); |
| 2963 |
if slot >= Slots::LIMIT { |
| 2964 |
return None; |
| 2965 |
} |
| 2966 |
self.slots = self.slots.remove(slot); |
| 2967 |
Some(slot) |
| 2968 |
} |
| 2969 |
} |
| 2970 |
|
| 2971 |
/// An error that occurred during the construction of a one-pass DFA. |
| 2972 |
/// |
| 2973 |
/// This error does not provide many introspection capabilities. There are |
| 2974 |
/// generally only two things you can do with it: |
| 2975 |
/// |
| 2976 |
/// * Obtain a human readable message via its `std::fmt::Display` impl. |
| 2977 |
/// * Access an underlying [`thompson::BuildError`] type from its `source` |
| 2978 |
/// method via the `std::error::Error` trait. This error only occurs when using |
| 2979 |
/// convenience routines for building a one-pass DFA directly from a pattern |
| 2980 |
/// string. |
| 2981 |
/// |
| 2982 |
/// When the `std` feature is enabled, this implements the `std::error::Error` |
| 2983 |
/// trait. |
| 2984 |
#[derive(Clone, Debug)] |
| 2985 |
pub struct BuildError { |
| 2986 |
kind: BuildErrorKind, |
| 2987 |
} |
| 2988 |
|
| 2989 |
/// The kind of error that occurred during the construction of a one-pass DFA. |
| 2990 |
#[derive(Clone, Debug)] |
| 2991 |
enum BuildErrorKind { |
| 2992 |
NFA(crate::nfa::thompson::BuildError), |
| 2993 |
Word(UnicodeWordBoundaryError), |
| 2994 |
TooManyStates { limit: u64 }, |
| 2995 |
TooManyPatterns { limit: u64 }, |
| 2996 |
UnsupportedLook { look: Look }, |
| 2997 |
ExceededSizeLimit { limit: usize }, |
| 2998 |
NotOnePass { msg: &'static str }, |
| 2999 |
} |
| 3000 |
|
| 3001 |
impl BuildError { |
| 3002 |
fn nfa(err: crate::nfa::thompson::BuildError) -> BuildError { |
| 3003 |
BuildError { kind: BuildErrorKind::NFA(err) } |
| 3004 |
} |
| 3005 |
|
| 3006 |
fn word(err: UnicodeWordBoundaryError) -> BuildError { |
| 3007 |
BuildError { kind: BuildErrorKind::Word(err) } |
| 3008 |
} |
| 3009 |
|
| 3010 |
fn too_many_states(limit: u64) -> BuildError { |
| 3011 |
BuildError { kind: BuildErrorKind::TooManyStates { limit } } |
| 3012 |
} |
| 3013 |
|
| 3014 |
fn too_many_patterns(limit: u64) -> BuildError { |
| 3015 |
BuildError { kind: BuildErrorKind::TooManyPatterns { limit } } |
| 3016 |
} |
| 3017 |
|
| 3018 |
fn unsupported_look(look: Look) -> BuildError { |
| 3019 |
BuildError { kind: BuildErrorKind::UnsupportedLook { look } } |
| 3020 |
} |
| 3021 |
|
| 3022 |
fn exceeded_size_limit(limit: usize) -> BuildError { |
| 3023 |
BuildError { kind: BuildErrorKind::ExceededSizeLimit { limit } } |
| 3024 |
} |
| 3025 |
|
| 3026 |
fn not_one_pass(msg: &'static str) -> BuildError { |
| 3027 |
BuildError { kind: BuildErrorKind::NotOnePass { msg } } |
| 3028 |
} |
| 3029 |
} |
| 3030 |
|
| 3031 |
#[cfg(feature = "std")] |
| 3032 |
impl std::error::Error for BuildError { |
| 3033 |
fn source(&self) -> Option<&(dyn std::error::Error + 'static)> { |
| 3034 |
use self::BuildErrorKind::*; |
| 3035 |
|
| 3036 |
match self.kind { |
| 3037 |
NFA(ref err) => Some(err), |
| 3038 |
Word(ref err) => Some(err), |
| 3039 |
_ => None, |
| 3040 |
} |
| 3041 |
} |
| 3042 |
} |
| 3043 |
|
| 3044 |
impl core::fmt::Display for BuildError { |
| 3045 |
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { |
| 3046 |
use self::BuildErrorKind::*; |
| 3047 |
|
| 3048 |
match self.kind { |
| 3049 |
NFA(_) => write!(f, "error building NFA"), |
| 3050 |
Word(_) => write!(f, "NFA contains Unicode word boundary"), |
| 3051 |
TooManyStates { limit } => write!( |
| 3052 |
f, |
| 3053 |
"one-pass DFA exceeded a limit of {:?} for number of states", |
| 3054 |
limit, |
| 3055 |
), |
| 3056 |
TooManyPatterns { limit } => write!( |
| 3057 |
f, |
| 3058 |
"one-pass DFA exceeded a limit of {:?} for number of patterns", |
| 3059 |
limit, |
| 3060 |
), |
| 3061 |
UnsupportedLook { look } => write!( |
| 3062 |
f, |
| 3063 |
"one-pass DFA does not support the {:?} assertion", |
| 3064 |
look, |
| 3065 |
), |
| 3066 |
ExceededSizeLimit { limit } => write!( |
| 3067 |
f, |
| 3068 |
"one-pass DFA exceeded size limit of {:?} during building", |
| 3069 |
limit, |
| 3070 |
), |
| 3071 |
NotOnePass { msg } => write!( |
| 3072 |
f, |
| 3073 |
"one-pass DFA could not be built because \ |
| 3074 |
pattern is not one-pass: {}", |
| 3075 |
msg, |
| 3076 |
), |
| 3077 |
} |
| 3078 |
} |
| 3079 |
} |
| 3080 |
|
| 3081 |
#[cfg(all(test, feature = "syntax"))] |
| 3082 |
mod tests { |
| 3083 |
use alloc::string::ToString; |
| 3084 |
|
| 3085 |
use super::*; |
| 3086 |
|
| 3087 |
#[test] |
| 3088 |
fn fail_conflicting_transition() { |
| 3089 |
let predicate = |err: &str| err.contains("conflicting transition"); |
| 3090 |
|
| 3091 |
let err = DFA::new(r"a*[ab]").unwrap_err().to_string(); |
| 3092 |
assert!(predicate(&err), "{}", err); |
| 3093 |
} |
| 3094 |
|
| 3095 |
#[test] |
| 3096 |
fn fail_multiple_epsilon() { |
| 3097 |
let predicate = |err: &str| { |
| 3098 |
err.contains("multiple epsilon transitions to same state") |
| 3099 |
}; |
| 3100 |
|
| 3101 |
let err = DFA::new(r"(^|$)a").unwrap_err().to_string(); |
| 3102 |
assert!(predicate(&err), "{}", err); |
| 3103 |
} |
| 3104 |
|
| 3105 |
#[test] |
| 3106 |
fn fail_multiple_match() { |
| 3107 |
let predicate = |err: &str| { |
| 3108 |
err.contains("multiple epsilon transitions to match state") |
| 3109 |
}; |
| 3110 |
|
| 3111 |
let err = DFA::new_many(&[r"^", r"$"]).unwrap_err().to_string(); |
| 3112 |
assert!(predicate(&err), "{}", err); |
| 3113 |
} |
| 3114 |
|
| 3115 |
// This test is meant to build a one-pass regex with the maximum number of |
| 3116 |
// possible slots. |
| 3117 |
// |
| 3118 |
// NOTE: Remember that the slot limit only applies to explicit capturing |
| 3119 |
// groups. Any number of implicit capturing groups is supported (up to the |
| 3120 |
// maximum number of supported patterns), since implicit groups are handled |
| 3121 |
// by the search loop itself. |
| 3122 |
#[test] |
| 3123 |
fn max_slots() { |
| 3124 |
// One too many... |
| 3125 |
let pat = r"(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)(q)"; |
| 3126 |
assert!(DFA::new(pat).is_err()); |
| 3127 |
// Just right. |
| 3128 |
let pat = r"(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)"; |
| 3129 |
assert!(DFA::new(pat).is_ok()); |
| 3130 |
} |
| 3131 |
|
| 3132 |
// This test ensures that the one-pass DFA works with all look-around |
| 3133 |
// assertions that we expect it to work with. |
| 3134 |
// |
| 3135 |
// The utility of this test is that each one-pass transition has a small |
| 3136 |
// amount of space to store look-around assertions. Currently, there is |
| 3137 |
// logic in the one-pass constructor to ensure there aren't more than ten |
| 3138 |
// possible assertions. And indeed, there are only ten possible assertions |
| 3139 |
// (at time of writing), so this is okay. But conceivably, more assertions |
| 3140 |
// could be added. So we check that things at least work with what we |
| 3141 |
// expect them to work with. |
| 3142 |
#[test] |
| 3143 |
fn assertions() { |
| 3144 |
// haystack anchors |
| 3145 |
assert!(DFA::new(r"^").is_ok()); |
| 3146 |
assert!(DFA::new(r"$").is_ok()); |
| 3147 |
|
| 3148 |
// line anchors |
| 3149 |
assert!(DFA::new(r"(?m)^").is_ok()); |
| 3150 |
assert!(DFA::new(r"(?m)$").is_ok()); |
| 3151 |
assert!(DFA::new(r"(?Rm)^").is_ok()); |
| 3152 |
assert!(DFA::new(r"(?Rm)$").is_ok()); |
| 3153 |
|
| 3154 |
// word boundaries |
| 3155 |
if cfg!(feature = "unicode-word-boundary") { |
| 3156 |
assert!(DFA::new(r"\b").is_ok()); |
| 3157 |
assert!(DFA::new(r"\B").is_ok()); |
| 3158 |
} |
| 3159 |
assert!(DFA::new(r"(?-u)\b").is_ok()); |
| 3160 |
assert!(DFA::new(r"(?-u)\B").is_ok()); |
| 3161 |
} |
| 3162 |
|
| 3163 |
#[cfg(not(miri))] // takes too long on miri |
| 3164 |
#[test] |
| 3165 |
fn is_one_pass() { |
| 3166 |
use crate::util::syntax; |
| 3167 |
|
| 3168 |
assert!(DFA::new(r"a*b").is_ok()); |
| 3169 |
if cfg!(feature = "unicode-perl") { |
| 3170 |
assert!(DFA::new(r"\w").is_ok()); |
| 3171 |
} |
| 3172 |
assert!(DFA::new(r"(?-u)\w*\s").is_ok()); |
| 3173 |
assert!(DFA::new(r"(?s:.)*?").is_ok()); |
| 3174 |
assert!(DFA::builder() |
| 3175 |
.syntax(syntax::Config::new().utf8(false)) |
| 3176 |
.build(r"(?s-u:.)*?") |
| 3177 |
.is_ok()); |
| 3178 |
} |
| 3179 |
|
| 3180 |
#[test] |
| 3181 |
fn is_not_one_pass() { |
| 3182 |
assert!(DFA::new(r"a*a").is_err()); |
| 3183 |
assert!(DFA::new(r"(?s-u:.)*?").is_err()); |
| 3184 |
assert!(DFA::new(r"(?s:.)*?a").is_err()); |
| 3185 |
} |
| 3186 |
|
| 3187 |
#[cfg(not(miri))] |
| 3188 |
#[test] |
| 3189 |
fn is_not_one_pass_bigger() { |
| 3190 |
assert!(DFA::new(r"\w*\s").is_err()); |
| 3191 |
} |
| 3192 |
} |