-
Notifications
You must be signed in to change notification settings - Fork 415
/
dfa.rs
4418 lines (4277 loc) · 185 KB
/
dfa.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/*!
Types and routines specific to lazy DFAs.
This module is the home of [`hybrid::dfa::DFA`](DFA).
This module also contains a [`hybrid::dfa::Builder`](Builder) and a
[`hybrid::dfa::Config`](Config) for configuring and building a lazy DFA.
*/
use core::{iter, mem::size_of};
use alloc::vec::Vec;
use crate::{
hybrid::{
error::{BuildError, CacheError, StartError},
id::{LazyStateID, LazyStateIDError},
search,
},
nfa::thompson,
util::{
alphabet::{self, ByteClasses, ByteSet},
determinize::{self, State, StateBuilderEmpty, StateBuilderNFA},
empty,
prefilter::Prefilter,
primitives::{PatternID, StateID as NFAStateID},
search::{
Anchored, HalfMatch, Input, MatchError, MatchKind, PatternSet,
},
sparse_set::SparseSets,
start::{self, Start, StartByteMap},
},
};
/// The minimum number of states that a lazy DFA's cache size must support.
///
/// This is checked at time of construction to ensure that at least some small
/// number of states can fit in the given capacity allotment. If we can't fit
/// at least this number of states, then the thinking is that it's pretty
/// senseless to use the lazy DFA. More to the point, parts of the code do
/// assume that the cache can fit at least some small number of states.
const MIN_STATES: usize = SENTINEL_STATES + 2;
/// The number of "sentinel" states that get added to every lazy DFA.
///
/// These are special states indicating status conditions of a search: unknown,
/// dead and quit. These states in particular also use zero NFA states, so
/// their memory usage is quite small. This is relevant for computing the
/// minimum memory needed for a lazy DFA cache.
const SENTINEL_STATES: usize = 3;
/// A hybrid NFA/DFA (also called a "lazy DFA") for regex searching.
///
/// A lazy DFA is a DFA that builds itself at search time. It otherwise has
/// very similar characteristics as a [`dense::DFA`](crate::dfa::dense::DFA).
/// Indeed, both support precisely the same regex features with precisely the
/// same semantics.
///
/// Where as a `dense::DFA` must be completely built to handle any input before
/// it may be used for search, a lazy DFA starts off effectively empty. During
/// a search, a lazy DFA will build itself depending on whether it has already
/// computed the next transition or not. If it has, then it looks a lot like
/// a `dense::DFA` internally: it does a very fast table based access to find
/// the next transition. Otherwise, if the state hasn't been computed, then it
/// does determinization _for that specific transition_ to compute the next DFA
/// state.
///
/// The main selling point of a lazy DFA is that, in practice, it has
/// the performance profile of a `dense::DFA` without the weakness of it
/// taking worst case exponential time to build. Indeed, for each byte of
/// input, the lazy DFA will construct as most one new DFA state. Thus, a
/// lazy DFA achieves worst case `O(mn)` time for regex search (where `m ~
/// pattern.len()` and `n ~ haystack.len()`).
///
/// The main downsides of a lazy DFA are:
///
/// 1. It requires mutable "cache" space during search. This is where the
/// transition table, among other things, is stored.
/// 2. In pathological cases (e.g., if the cache is too small), it will run
/// out of room and either require a bigger cache capacity or will repeatedly
/// clear the cache and thus repeatedly regenerate DFA states. Overall, this
/// will tend to be slower than a typical NFA simulation.
///
/// # Capabilities
///
/// Like a `dense::DFA`, a single lazy DFA fundamentally supports the following
/// operations:
///
/// 1. Detection of a match.
/// 2. Location of the end of a match.
/// 3. In the case of a lazy DFA with multiple patterns, which pattern matched
/// is reported as well.
///
/// A notable absence from the above list of capabilities is the location of
/// the *start* of a match. In order to provide both the start and end of
/// a match, *two* lazy DFAs are required. This functionality is provided by a
/// [`Regex`](crate::hybrid::regex::Regex).
///
/// # Example
///
/// This shows how to build a lazy DFA with the default configuration and
/// execute a search. Notice how, in contrast to a `dense::DFA`, we must create
/// a cache and pass it to our search routine.
///
/// ```
/// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
///
/// let dfa = DFA::new("foo[0-9]+")?;
/// let mut cache = dfa.create_cache();
///
/// let expected = Some(HalfMatch::must(0, 8));
/// assert_eq!(expected, dfa.try_search_fwd(
/// &mut cache, &Input::new("foo12345"))?,
/// );
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[derive(Clone, Debug)]
pub struct DFA {
config: Config,
nfa: thompson::NFA,
stride2: usize,
start_map: StartByteMap,
classes: ByteClasses,
quitset: ByteSet,
cache_capacity: usize,
}
impl DFA {
/// Parse the given regular expression using a default configuration and
/// return the corresponding lazy DFA.
///
/// If you want a non-default configuration, then use the [`Builder`] to
/// set your own configuration.
///
/// # Example
///
/// ```
/// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
///
/// let dfa = DFA::new("foo[0-9]+bar")?;
/// let mut cache = dfa.create_cache();
///
/// let expected = HalfMatch::must(0, 11);
/// assert_eq!(
/// Some(expected),
/// dfa.try_search_fwd(&mut cache, &Input::new("foo12345bar"))?,
/// );
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[cfg(feature = "syntax")]
pub fn new(pattern: &str) -> Result<DFA, BuildError> {
DFA::builder().build(pattern)
}
/// Parse the given regular expressions using a default configuration and
/// return the corresponding lazy multi-DFA.
///
/// If you want a non-default configuration, then use the [`Builder`] to
/// set your own configuration.
///
/// # Example
///
/// ```
/// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
///
/// let dfa = DFA::new_many(&["[0-9]+", "[a-z]+"])?;
/// let mut cache = dfa.create_cache();
///
/// let expected = HalfMatch::must(1, 3);
/// assert_eq!(
/// Some(expected),
/// dfa.try_search_fwd(&mut cache, &Input::new("foo12345bar"))?,
/// );
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[cfg(feature = "syntax")]
pub fn new_many<P: AsRef<str>>(patterns: &[P]) -> Result<DFA, BuildError> {
DFA::builder().build_many(patterns)
}
/// Create a new lazy DFA that matches every input.
///
/// # Example
///
/// ```
/// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
///
/// let dfa = DFA::always_match()?;
/// let mut cache = dfa.create_cache();
///
/// let expected = HalfMatch::must(0, 0);
/// assert_eq!(Some(expected), dfa.try_search_fwd(
/// &mut cache, &Input::new(""))?,
/// );
/// assert_eq!(Some(expected), dfa.try_search_fwd(
/// &mut cache, &Input::new("foo"))?,
/// );
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn always_match() -> Result<DFA, BuildError> {
let nfa = thompson::NFA::always_match();
Builder::new().build_from_nfa(nfa)
}
/// Create a new lazy DFA that never matches any input.
///
/// # Example
///
/// ```
/// use regex_automata::{hybrid::dfa::DFA, Input};
///
/// let dfa = DFA::never_match()?;
/// let mut cache = dfa.create_cache();
///
/// assert_eq!(None, dfa.try_search_fwd(&mut cache, &Input::new(""))?);
/// assert_eq!(None, dfa.try_search_fwd(&mut cache, &Input::new("foo"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn never_match() -> Result<DFA, BuildError> {
let nfa = thompson::NFA::never_match();
Builder::new().build_from_nfa(nfa)
}
/// Return a default configuration for a `DFA`.
///
/// This is a convenience routine to avoid needing to import the [`Config`]
/// type when customizing the construction of a lazy DFA.
///
/// # Example
///
/// This example shows how to build a lazy DFA that heuristically supports
/// Unicode word boundaries.
///
/// ```
/// # if cfg!(miri) { return Ok(()); } // miri takes too long
/// use regex_automata::{hybrid::dfa::DFA, HalfMatch, MatchError, Input};
///
/// let re = DFA::builder()
/// .configure(DFA::config().unicode_word_boundary(true))
/// .build(r"\b\w+\b")?;
/// let mut cache = re.create_cache();
///
/// // Since our haystack is all ASCII, the DFA search sees then and knows
/// // it is legal to interpret Unicode word boundaries as ASCII word
/// // boundaries.
/// let input = Input::new("!!foo!!");
/// let expected = HalfMatch::must(0, 5);
/// assert_eq!(Some(expected), re.try_search_fwd(&mut cache, &input)?);
///
/// // But if our haystack contains non-ASCII, then the search will fail
/// // with an error.
/// let input = Input::new("!!βββ!!");
/// let expected = MatchError::quit(b'\xCE', 2);
/// assert_eq!(Err(expected), re.try_search_fwd(&mut cache, &input));
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn config() -> Config {
Config::new()
}
/// Return a builder for configuring the construction of a `Regex`.
///
/// This is a convenience routine to avoid needing to import the
/// [`Builder`] type in common cases.
///
/// # Example
///
/// This example shows how to use the builder to disable UTF-8 mode
/// everywhere for lazy DFAs.
///
/// ```
/// # if cfg!(miri) { return Ok(()); } // miri takes too long
/// use regex_automata::{hybrid::dfa::DFA, util::syntax, HalfMatch, Input};
///
/// let re = DFA::builder()
/// .syntax(syntax::Config::new().utf8(false))
/// .build(r"foo(?-u:[^b])ar.*")?;
/// let mut cache = re.create_cache();
///
/// let input = Input::new(b"\xFEfoo\xFFarzz\xE2\x98\xFF\n");
/// let expected = Some(HalfMatch::must(0, 9));
/// let got = re.try_search_fwd(&mut cache, &input)?;
/// assert_eq!(expected, got);
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn builder() -> Builder {
Builder::new()
}
/// Create a new cache for this lazy DFA.
///
/// The cache returned should only be used for searches for this
/// lazy DFA. If you want to reuse the cache for another DFA, then
/// you must call [`Cache::reset`] with that DFA (or, equivalently,
/// [`DFA::reset_cache`]).
pub fn create_cache(&self) -> Cache {
Cache::new(self)
}
/// Reset the given cache such that it can be used for searching with the
/// this lazy DFA (and only this DFA).
///
/// A cache reset permits reusing memory already allocated in this cache
/// with a different lazy DFA.
///
/// Resetting a cache sets its "clear count" to 0. This is relevant if the
/// lazy DFA has been configured to "give up" after it has cleared the
/// cache a certain number of times.
///
/// Any lazy state ID generated by the cache prior to resetting it is
/// invalid after the reset.
///
/// # Example
///
/// This shows how to re-purpose a cache for use with a different DFA.
///
/// ```
/// # if cfg!(miri) { return Ok(()); } // miri takes too long
/// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
///
/// let dfa1 = DFA::new(r"\w")?;
/// let dfa2 = DFA::new(r"\W")?;
///
/// let mut cache = dfa1.create_cache();
/// assert_eq!(
/// Some(HalfMatch::must(0, 2)),
/// dfa1.try_search_fwd(&mut cache, &Input::new("Δ"))?,
/// );
///
/// // Using 'cache' with dfa2 is not allowed. It may result in panics or
/// // incorrect results. In order to re-purpose the cache, we must reset
/// // it with the DFA we'd like to use it with.
/// //
/// // Similarly, after this reset, using the cache with 'dfa1' is also not
/// // allowed.
/// dfa2.reset_cache(&mut cache);
/// assert_eq!(
/// Some(HalfMatch::must(0, 3)),
/// dfa2.try_search_fwd(&mut cache, &Input::new("☃"))?,
/// );
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn reset_cache(&self, cache: &mut Cache) {
Lazy::new(self, cache).reset_cache()
}
/// Returns the total number of patterns compiled into this lazy DFA.
///
/// In the case of a DFA that contains no patterns, this returns `0`.
///
/// # Example
///
/// This example shows the pattern length for a DFA that never matches:
///
/// ```
/// use regex_automata::hybrid::dfa::DFA;
///
/// let dfa = DFA::never_match()?;
/// assert_eq!(dfa.pattern_len(), 0);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// And another example for a DFA that matches at every position:
///
/// ```
/// use regex_automata::hybrid::dfa::DFA;
///
/// let dfa = DFA::always_match()?;
/// assert_eq!(dfa.pattern_len(), 1);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// And finally, a DFA that was constructed from multiple patterns:
///
/// ```
/// use regex_automata::hybrid::dfa::DFA;
///
/// let dfa = DFA::new_many(&["[0-9]+", "[a-z]+", "[A-Z]+"])?;
/// assert_eq!(dfa.pattern_len(), 3);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn pattern_len(&self) -> usize {
self.nfa.pattern_len()
}
/// Returns the equivalence classes that make up the alphabet for this DFA.
///
/// Unless [`Config::byte_classes`] was disabled, it is possible that
/// multiple distinct bytes are grouped into the same equivalence class
/// if it is impossible for them to discriminate between a match and a
/// non-match. This has the effect of reducing the overall alphabet size
/// and in turn potentially substantially reducing the size of the DFA's
/// transition table.
///
/// The downside of using equivalence classes like this is that every state
/// transition will automatically use this map to convert an arbitrary
/// byte to its corresponding equivalence class. In practice this has a
/// negligible impact on performance.
pub fn byte_classes(&self) -> &ByteClasses {
&self.classes
}
/// Returns this lazy DFA's configuration.
pub fn get_config(&self) -> &Config {
&self.config
}
/// Returns a reference to the underlying NFA.
pub fn get_nfa(&self) -> &thompson::NFA {
&self.nfa
}
/// Returns the stride, as a base-2 exponent, required for these
/// equivalence classes.
///
/// The stride is always the smallest power of 2 that is greater than or
/// equal to the alphabet length. This is done so that converting between
/// state IDs and indices can be done with shifts alone, which is much
/// faster than integer division.
fn stride2(&self) -> usize {
self.stride2
}
/// Returns the total stride for every state in this lazy DFA. This
/// corresponds to the total number of transitions used by each state in
/// this DFA's transition table.
fn stride(&self) -> usize {
1 << self.stride2()
}
/// Returns the memory usage, in bytes, of this lazy DFA.
///
/// This does **not** include the stack size used up by this lazy DFA. To
/// compute that, use `std::mem::size_of::<DFA>()`. This also does not
/// include the size of the `Cache` used.
///
/// This also does not include any heap memory used by the NFA inside of
/// this hybrid NFA/DFA. This is because the NFA's ownership is shared, and
/// thus not owned by this hybrid NFA/DFA. More practically, several regex
/// engines in this crate embed an NFA, and reporting the NFA's memory
/// usage in all of them would likely result in reporting higher heap
/// memory than is actually used.
pub fn memory_usage(&self) -> usize {
// The only thing that uses heap memory in a DFA is the NFA. But the
// NFA has shared ownership, so reporting its memory as part of the
// hybrid DFA is likely to lead to double-counting the NFA memory
// somehow. In particular, this DFA does not really own an NFA, so
// including it in the DFA's memory usage doesn't seem semantically
// correct.
0
}
}
impl DFA {
/// Executes a forward search and returns the end position of the leftmost
/// match that is found. If no match exists, then `None` is returned.
///
/// In particular, this method continues searching even after it enters
/// a match state. The search only terminates once it has reached the
/// end of the input or when it has entered a dead or quit state. Upon
/// termination, the position of the last byte seen while still in a match
/// state is returned.
///
/// # Errors
///
/// This routine errors if the search could not complete. This can occur
/// in a number of circumstances:
///
/// * The configuration of the lazy DFA may permit it to "quit" the search.
/// For example, setting quit bytes or enabling heuristic support for
/// Unicode word boundaries. The default configuration does not enable any
/// option that could result in the lazy DFA quitting.
/// * The configuration of the lazy DFA may also permit it to "give up"
/// on a search if it makes ineffective use of its transition table
/// cache. The default configuration does not enable this by default,
/// although it is typically a good idea to.
/// * When the provided `Input` configuration is not supported. For
/// example, by providing an unsupported anchor mode.
///
/// When a search returns an error, callers cannot know whether a match
/// exists or not.
///
/// # Example
///
/// This example shows how to run a basic search.
///
/// ```
/// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
///
/// let dfa = DFA::new("foo[0-9]+")?;
/// let mut cache = dfa.create_cache();
/// let expected = HalfMatch::must(0, 8);
/// assert_eq!(Some(expected), dfa.try_search_fwd(
/// &mut cache, &Input::new("foo12345"))?,
/// );
///
/// // Even though a match is found after reading the first byte (`a`),
/// // the leftmost first match semantics demand that we find the earliest
/// // match that prefers earlier parts of the pattern over later parts.
/// let dfa = DFA::new("abc|a")?;
/// let mut cache = dfa.create_cache();
/// let expected = HalfMatch::must(0, 3);
/// assert_eq!(Some(expected), dfa.try_search_fwd(
/// &mut cache, &Input::new("abc"))?,
/// );
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// # Example: specific pattern search
///
/// This example shows how to build a lazy multi-DFA that permits searching
/// for specific patterns.
///
/// ```
/// use regex_automata::{
/// hybrid::dfa::DFA,
/// Anchored, HalfMatch, PatternID, Input,
/// };
///
/// let dfa = DFA::builder()
/// .configure(DFA::config().starts_for_each_pattern(true))
/// .build_many(&["[a-z0-9]{6}", "[a-z][a-z0-9]{5}"])?;
/// let mut cache = dfa.create_cache();
/// let haystack = "foo123";
///
/// // Since we are using the default leftmost-first match and both
/// // patterns match at the same starting position, only the first pattern
/// // will be returned in this case when doing a search for any of the
/// // patterns.
/// let expected = Some(HalfMatch::must(0, 6));
/// let got = dfa.try_search_fwd(&mut cache, &Input::new(haystack))?;
/// assert_eq!(expected, got);
///
/// // But if we want to check whether some other pattern matches, then we
/// // can provide its pattern ID.
/// let expected = Some(HalfMatch::must(1, 6));
/// let input = Input::new(haystack)
/// .anchored(Anchored::Pattern(PatternID::must(1)));
/// let got = dfa.try_search_fwd(&mut cache, &input)?;
/// assert_eq!(expected, got);
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// # Example: specifying the bounds of a search
///
/// This example shows how providing the bounds of a search can produce
/// different results than simply sub-slicing the haystack.
///
/// ```
/// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
///
/// // N.B. We disable Unicode here so that we use a simple ASCII word
/// // boundary. Alternatively, we could enable heuristic support for
/// // Unicode word boundaries since our haystack is pure ASCII.
/// let dfa = DFA::new(r"(?-u)\b[0-9]{3}\b")?;
/// let mut cache = dfa.create_cache();
/// let haystack = "foo123bar";
///
/// // Since we sub-slice the haystack, the search doesn't know about the
/// // larger context and assumes that `123` is surrounded by word
/// // boundaries. And of course, the match position is reported relative
/// // to the sub-slice as well, which means we get `3` instead of `6`.
/// let expected = Some(HalfMatch::must(0, 3));
/// let got = dfa.try_search_fwd(
/// &mut cache,
/// &Input::new(&haystack[3..6]),
/// )?;
/// assert_eq!(expected, got);
///
/// // But if we provide the bounds of the search within the context of the
/// // entire haystack, then the search can take the surrounding context
/// // into account. (And if we did find a match, it would be reported
/// // as a valid offset into `haystack` instead of its sub-slice.)
/// let expected = None;
/// let got = dfa.try_search_fwd(
/// &mut cache,
/// &Input::new(haystack).range(3..6),
/// )?;
/// assert_eq!(expected, got);
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[inline]
pub fn try_search_fwd(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Result<Option<HalfMatch>, MatchError> {
let utf8empty = self.get_nfa().has_empty() && self.get_nfa().is_utf8();
let hm = match search::find_fwd(self, cache, input)? {
None => return Ok(None),
Some(hm) if !utf8empty => return Ok(Some(hm)),
Some(hm) => hm,
};
// We get to this point when we know our DFA can match the empty string
// AND when UTF-8 mode is enabled. In this case, we skip any matches
// whose offset splits a codepoint. Such a match is necessarily a
// zero-width match, because UTF-8 mode requires the underlying NFA
// to be built such that all non-empty matches span valid UTF-8.
// Therefore, any match that ends in the middle of a codepoint cannot
// be part of a span of valid UTF-8 and thus must be an empty match.
// In such cases, we skip it, so as not to report matches that split a
// codepoint.
//
// Note that this is not a checked assumption. Callers *can* provide an
// NFA with UTF-8 mode enabled but produces non-empty matches that span
// invalid UTF-8. But doing so is documented to result in unspecified
// behavior.
empty::skip_splits_fwd(input, hm, hm.offset(), |input| {
let got = search::find_fwd(self, cache, input)?;
Ok(got.map(|hm| (hm, hm.offset())))
})
}
/// Executes a reverse search and returns the start of the position of the
/// leftmost match that is found. If no match exists, then `None` is
/// returned.
///
/// # Errors
///
/// This routine errors if the search could not complete. This can occur
/// in a number of circumstances:
///
/// * The configuration of the lazy DFA may permit it to "quit" the search.
/// For example, setting quit bytes or enabling heuristic support for
/// Unicode word boundaries. The default configuration does not enable any
/// option that could result in the lazy DFA quitting.
/// * The configuration of the lazy DFA may also permit it to "give up"
/// on a search if it makes ineffective use of its transition table
/// cache. The default configuration does not enable this by default,
/// although it is typically a good idea to.
/// * When the provided `Input` configuration is not supported. For
/// example, by providing an unsupported anchor mode.
///
/// When a search returns an error, callers cannot know whether a match
/// exists or not.
///
/// # Example
///
/// This routine is principally useful when used in
/// conjunction with the
/// [`nfa::thompson::Config::reverse`](crate::nfa::thompson::Config::reverse)
/// configuration. In general, it's unlikely to be correct to use both
/// `try_search_fwd` and `try_search_rev` with the same DFA since any
/// particular DFA will only support searching in one direction with
/// respect to the pattern.
///
/// ```
/// use regex_automata::{
/// nfa::thompson,
/// hybrid::dfa::DFA,
/// HalfMatch, Input,
/// };
///
/// let dfa = DFA::builder()
/// .thompson(thompson::Config::new().reverse(true))
/// .build("foo[0-9]+")?;
/// let mut cache = dfa.create_cache();
/// let expected = HalfMatch::must(0, 0);
/// assert_eq!(
/// Some(expected),
/// dfa.try_search_rev(&mut cache, &Input::new("foo12345"))?,
/// );
///
/// // Even though a match is found after reading the last byte (`c`),
/// // the leftmost first match semantics demand that we find the earliest
/// // match that prefers earlier parts of the pattern over latter parts.
/// let dfa = DFA::builder()
/// .thompson(thompson::Config::new().reverse(true))
/// .build("abc|c")?;
/// let mut cache = dfa.create_cache();
/// let expected = HalfMatch::must(0, 0);
/// assert_eq!(Some(expected), dfa.try_search_rev(
/// &mut cache, &Input::new("abc"))?,
/// );
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// # Example: UTF-8 mode
///
/// This examples demonstrates that UTF-8 mode applies to reverse
/// DFAs. When UTF-8 mode is enabled in the underlying NFA, then all
/// matches reported must correspond to valid UTF-8 spans. This includes
/// prohibiting zero-width matches that split a codepoint.
///
/// UTF-8 mode is enabled by default. Notice below how the only zero-width
/// matches reported are those at UTF-8 boundaries:
///
/// ```
/// use regex_automata::{
/// hybrid::dfa::DFA,
/// nfa::thompson,
/// HalfMatch, Input, MatchKind,
/// };
///
/// let dfa = DFA::builder()
/// .thompson(thompson::Config::new().reverse(true))
/// .build(r"")?;
/// let mut cache = dfa.create_cache();
///
/// // Run the reverse DFA to collect all matches.
/// let mut input = Input::new("☃");
/// let mut matches = vec![];
/// loop {
/// match dfa.try_search_rev(&mut cache, &input)? {
/// None => break,
/// Some(hm) => {
/// matches.push(hm);
/// if hm.offset() == 0 || input.end() == 0 {
/// break;
/// } else if hm.offset() < input.end() {
/// input.set_end(hm.offset());
/// } else {
/// // This is only necessary to handle zero-width
/// // matches, which of course occur in this example.
/// // Without this, the search would never advance
/// // backwards beyond the initial match.
/// input.set_end(input.end() - 1);
/// }
/// }
/// }
/// }
///
/// // No matches split a codepoint.
/// let expected = vec![
/// HalfMatch::must(0, 3),
/// HalfMatch::must(0, 0),
/// ];
/// assert_eq!(expected, matches);
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// Now let's look at the same example, but with UTF-8 mode on the
/// underlying NFA disabled:
///
/// ```
/// use regex_automata::{
/// hybrid::dfa::DFA,
/// nfa::thompson,
/// HalfMatch, Input, MatchKind,
/// };
///
/// let dfa = DFA::builder()
/// .thompson(thompson::Config::new().reverse(true).utf8(false))
/// .build(r"")?;
/// let mut cache = dfa.create_cache();
///
/// // Run the reverse DFA to collect all matches.
/// let mut input = Input::new("☃");
/// let mut matches = vec![];
/// loop {
/// match dfa.try_search_rev(&mut cache, &input)? {
/// None => break,
/// Some(hm) => {
/// matches.push(hm);
/// if hm.offset() == 0 || input.end() == 0 {
/// break;
/// } else if hm.offset() < input.end() {
/// input.set_end(hm.offset());
/// } else {
/// // This is only necessary to handle zero-width
/// // matches, which of course occur in this example.
/// // Without this, the search would never advance
/// // backwards beyond the initial match.
/// input.set_end(input.end() - 1);
/// }
/// }
/// }
/// }
///
/// // No matches split a codepoint.
/// let expected = vec![
/// HalfMatch::must(0, 3),
/// HalfMatch::must(0, 2),
/// HalfMatch::must(0, 1),
/// HalfMatch::must(0, 0),
/// ];
/// assert_eq!(expected, matches);
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[inline]
pub fn try_search_rev(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Result<Option<HalfMatch>, MatchError> {
let utf8empty = self.get_nfa().has_empty() && self.get_nfa().is_utf8();
let hm = match search::find_rev(self, cache, input)? {
None => return Ok(None),
Some(hm) if !utf8empty => return Ok(Some(hm)),
Some(hm) => hm,
};
empty::skip_splits_rev(input, hm, hm.offset(), |input| {
let got = search::find_rev(self, cache, input)?;
Ok(got.map(|hm| (hm, hm.offset())))
})
}
/// Executes an overlapping forward search and returns the end position of
/// matches as they are found. If no match exists, then `None` is returned.
///
/// This routine is principally only useful when searching for multiple
/// patterns on inputs where multiple patterns may match the same regions
/// of text. In particular, callers must preserve the automaton's search
/// state from prior calls so that the implementation knows where the last
/// match occurred.
///
/// When using this routine to implement an iterator of overlapping
/// matches, the `start` of the search should remain invariant throughout
/// iteration. The `OverlappingState` given to the search will keep track
/// of the current position of the search. (This is because multiple
/// matches may be reported at the same position, so only the search
/// implementation itself knows when to advance the position.)
///
/// If for some reason you want the search to forget about its previous
/// state and restart the search at a particular position, then setting the
/// state to [`OverlappingState::start`] will accomplish that.
///
/// # Errors
///
/// This routine errors if the search could not complete. This can occur
/// in a number of circumstances:
///
/// * The configuration of the lazy DFA may permit it to "quit" the search.
/// For example, setting quit bytes or enabling heuristic support for
/// Unicode word boundaries. The default configuration does not enable any
/// option that could result in the lazy DFA quitting.
/// * The configuration of the lazy DFA may also permit it to "give up"
/// on a search if it makes ineffective use of its transition table
/// cache. The default configuration does not enable this by default,
/// although it is typically a good idea to.
/// * When the provided `Input` configuration is not supported. For
/// example, by providing an unsupported anchor mode.
///
/// When a search returns an error, callers cannot know whether a match
/// exists or not.
///
/// # Example
///
/// This example shows how to run a basic overlapping search. Notice
/// that we build the automaton with a `MatchKind::All` configuration.
/// Overlapping searches are unlikely to work as one would expect when
/// using the default `MatchKind::LeftmostFirst` match semantics, since
/// leftmost-first matching is fundamentally incompatible with overlapping
/// searches. Namely, overlapping searches need to report matches as they
/// are seen, where as leftmost-first searches will continue searching even
/// after a match has been observed in order to find the conventional end
/// position of the match. More concretely, leftmost-first searches use
/// dead states to terminate a search after a specific match can no longer
/// be extended. Overlapping searches instead do the opposite by continuing
/// the search to find totally new matches (potentially of other patterns).
///
/// ```
/// # if cfg!(miri) { return Ok(()); } // miri takes too long
/// use regex_automata::{
/// hybrid::dfa::{DFA, OverlappingState},
/// HalfMatch, Input, MatchKind,
/// };
///
/// let dfa = DFA::builder()
/// .configure(DFA::config().match_kind(MatchKind::All))
/// .build_many(&[r"\w+$", r"\S+$"])?;
/// let mut cache = dfa.create_cache();
///
/// let haystack = "@foo";
/// let mut state = OverlappingState::start();
///
/// let expected = Some(HalfMatch::must(1, 4));
/// dfa.try_search_overlapping_fwd(
/// &mut cache, &Input::new(haystack), &mut state,
/// )?;
/// assert_eq!(expected, state.get_match());
///
/// // The first pattern also matches at the same position, so re-running
/// // the search will yield another match. Notice also that the first
/// // pattern is returned after the second. This is because the second
/// // pattern begins its match before the first, is therefore an earlier
/// // match and is thus reported first.
/// let expected = Some(HalfMatch::must(0, 4));
/// dfa.try_search_overlapping_fwd(
/// &mut cache, &Input::new(haystack), &mut state,
/// )?;
/// assert_eq!(expected, state.get_match());
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[inline]
pub fn try_search_overlapping_fwd(
&self,
cache: &mut Cache,
input: &Input<'_>,
state: &mut OverlappingState,
) -> Result<(), MatchError> {
let utf8empty = self.get_nfa().has_empty() && self.get_nfa().is_utf8();
search::find_overlapping_fwd(self, cache, input, state)?;
match state.get_match() {
None => Ok(()),
Some(_) if !utf8empty => Ok(()),
Some(_) => skip_empty_utf8_splits_overlapping(
input,
state,
|input, state| {
search::find_overlapping_fwd(self, cache, input, state)
},
),
}
}
/// Executes a reverse overlapping search and returns the start of the
/// position of the leftmost match that is found. If no match exists, then
/// `None` is returned.
///
/// When using this routine to implement an iterator of overlapping
/// matches, the `start` of the search should remain invariant throughout
/// iteration. The `OverlappingState` given to the search will keep track
/// of the current position of the search. (This is because multiple
/// matches may be reported at the same position, so only the search
/// implementation itself knows when to advance the position.)
///
/// If for some reason you want the search to forget about its previous
/// state and restart the search at a particular position, then setting the
/// state to [`OverlappingState::start`] will accomplish that.
///
/// # Errors
///
/// This routine errors if the search could not complete. This can occur
/// in a number of circumstances:
///
/// * The configuration of the lazy DFA may permit it to "quit" the search.
/// For example, setting quit bytes or enabling heuristic support for
/// Unicode word boundaries. The default configuration does not enable any
/// option that could result in the lazy DFA quitting.
/// * The configuration of the lazy DFA may also permit it to "give up"
/// on a search if it makes ineffective use of its transition table
/// cache. The default configuration does not enable this by default,
/// although it is typically a good idea to.
/// * When the provided `Input` configuration is not supported. For
/// example, by providing an unsupported anchor mode.
///
/// When a search returns an error, callers cannot know whether a match
/// exists or not.
///
/// # Example: UTF-8 mode
///
/// This examples demonstrates that UTF-8 mode applies to reverse
/// DFAs. When UTF-8 mode is enabled in the underlying NFA, then all
/// matches reported must correspond to valid UTF-8 spans. This includes
/// prohibiting zero-width matches that split a codepoint.
///
/// UTF-8 mode is enabled by default. Notice below how the only zero-width
/// matches reported are those at UTF-8 boundaries:
///
/// ```
/// use regex_automata::{
/// hybrid::dfa::{DFA, OverlappingState},
/// nfa::thompson,
/// HalfMatch, Input, MatchKind,
/// };
///
/// let dfa = DFA::builder()
/// .configure(DFA::config().match_kind(MatchKind::All))
/// .thompson(thompson::Config::new().reverse(true))
/// .build_many(&[r"", r"☃"])?;
/// let mut cache = dfa.create_cache();
///
/// // Run the reverse DFA to collect all matches.
/// let input = Input::new("☃");
/// let mut state = OverlappingState::start();
/// let mut matches = vec![];
/// loop {
/// dfa.try_search_overlapping_rev(&mut cache, &input, &mut state)?;
/// match state.get_match() {
/// None => break,
/// Some(hm) => matches.push(hm),
/// }
/// }
///
/// // No matches split a codepoint.
/// let expected = vec![
/// HalfMatch::must(0, 3),
/// HalfMatch::must(1, 0),
/// HalfMatch::must(0, 0),
/// ];
/// assert_eq!(expected, matches);
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// Now let's look at the same example, but with UTF-8 mode on the
/// underlying NFA disabled:
///
/// ```