fancy_regex/seek.rs
1// Copyright 2026 The Fancy Regex Authors.
2//
3// Permission is hereby granted, free of charge, to any person obtaining a copy
4// of this software and associated documentation files (the "Software"), to deal
5// in the Software without restriction, including without limitation the rights
6// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7// copies of the Software, and to permit persons to whom the Software is
8// furnished to do so, subject to the following conditions:
9//
10// The above copyright notice and this permission notice shall be included in
11// all copies or substantial portions of the Software.
12//
13// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
19// THE SOFTWARE.
20
21//! Seek pre-filter: build a simplified approximation of a pattern used to
22//! skip to plausible match positions before handing off to the backtracking VM.
23//!
24//! Every quantifier in the approximation is emitted lazily because we only care about
25//! the start and being lazy doesn't change the result.
26
27use alloc::format;
28use alloc::string::String;
29use alloc::vec::Vec;
30
31#[cfg(not(feature = "std"))]
32use alloc::collections::BTreeMap as Map;
33#[cfg(feature = "std")]
34use std::collections::HashMap as Map;
35
36use crate::analyze::Info;
37use crate::compile::MAX_SUBROUTINE_RECURSION_DEPTH;
38use crate::{write_quantifier, Absent, Assertion, Expr};
39
40/// Returns `true` if the expression tree contains a `StartText` or `EndText` assertion anywhere.
41///
42/// This is used to decide whether it is safe to inline a group body when approximating a backref:
43/// text-anchor assertions in an inlined body would be evaluated at the wrong string position and
44/// could cause false negatives (missing valid match positions).
45pub(crate) fn expr_contains_positional_anchor(expr: &Expr) -> bool {
46 match expr {
47 // StartText (^), EndText ($), StartLine ((?m)^), EndLine ((?m)$) are positional anchors
48 // that depend on absolute position in the string. When a group containing such anchors
49 // is inlined for a backref approximation, the anchors would be evaluated at the wrong
50 // position (the backref position rather than the original capture position), potentially
51 // producing false negatives.
52 Expr::Assertion(
53 Assertion::StartText
54 | Assertion::EndText
55 | Assertion::EndTextIgnoreTrailingNewlines { .. }
56 | Assertion::StartLine { .. }
57 | Assertion::StartLineOniguruma { .. }
58 | Assertion::EndLine { .. },
59 ) => true,
60 _ => expr.children_iter().any(expr_contains_positional_anchor),
61 }
62}
63
64/// Cap on the seek-pattern buffer length. Inlining a backref/subroutine
65/// substitutes the referenced group's body, and when that body transitively
66/// references the same group (e.g. `(\s+((\3|\4|\5)))?` where `\4`/`\5` point
67/// at ancestors of the backref) the substitution branches at every level and,
68/// bounded only by the recursion depth, expands the buffer exponentially — so
69/// a short pattern can produce a multi-megabyte seek string. Once the buffer
70/// is already this large, further inlining stops and a permissive placeholder
71/// is emitted instead: the seek pattern only narrows candidate start positions
72/// and never decides matches, so a less-selective approximation stays correct.
73pub(crate) const MAX_SEEK_PATTERN_LEN: usize = 4096;
74
75/// Emit a lazy permissive size placeholder — `(?s:.)*?`, `(?s:.)+?`, or `(?s:.){N,}?` — into `buf`.
76///
77/// Used when a hard node cannot be represented in the seek pattern but has a known minimum
78/// size. The placeholder is an over-approximation that avoids false negatives: it admits any
79/// run of characters of at least `min_size` length.
80pub(crate) fn emit_min_size_placeholder(buf: &mut String, min_size: usize, precedence: u8) {
81 if precedence > 2 {
82 buf.push_str("(?:");
83 }
84 buf.push_str("(?s:.)");
85 write_quantifier(buf, min_size, usize::MAX, false);
86 if precedence > 2 {
87 buf.push(')');
88 }
89}
90
91/// Write the seek-pattern approximation for `info` into `buf`.
92///
93/// Easy subtrees without capture groups are serialised verbatim via [`Expr::to_str`].
94/// Hard nodes are handled as follows:
95/// - `Backref` / `SubroutineCall`: inline the referenced group's body (up to
96/// `MAX_SUBROUTINE_RECURSION_DEPTH`). For backrefs, positional anchors (`^`, `$`, `\b`) etc.
97/// are dropped from the inlined body because backreferences only capture text, not positions.
98/// If inlining is not possible, a permissive `(?s:.){min_size,}` placeholder is emitted
99/// instead of silently dropping, to maintain correctness.
100/// - `LookAround`, `KeepOut`, `ContinueFromPreviousMatchEnd`, `BacktrackingControlVerb`,
101/// `BackrefExistsCondition`, `Absent`: dropped (emit nothing — safe over-approximation,
102/// their `min_size` is 0).
103/// - `AtomicGroup`: keep the contents, discard the atomicity wrapper.
104/// - `Group`: keep the contents, discard the capture group wrapper.
105/// - `Conditional`: emit the union of the true and false branches.
106/// - `GeneralNewline`: replaced with an explicit alternation.
107/// - `Assertion`: anchors and word-boundary assertions, half boundaries included, are emitted.
108pub(crate) fn build_seek_pattern<'a>(
109 info: &Info<'a>,
110 group_info_map: &Map<usize, &'a Info<'a>>,
111 depth: usize,
112 buf: &mut String,
113 precedence: u8,
114) {
115 let mut inlined_groups = Vec::new();
116 build_seek_pattern_impl(
117 info,
118 group_info_map,
119 depth,
120 buf,
121 precedence,
122 false,
123 &mut inlined_groups,
124 );
125}
126
127pub(crate) fn build_seek_pattern_impl<'a>(
128 info: &Info<'a>,
129 group_info_map: &Map<usize, &'a Info<'a>>,
130 depth: usize,
131 buf: &mut String,
132 precedence: u8,
133 drop_positional_anchors: bool,
134 inlined_groups: &mut Vec<usize>,
135) {
136 // Drop positional anchors at this node when requested (used when inlining for a backref).
137 if drop_positional_anchors {
138 if let Expr::Assertion(
139 Assertion::StartText
140 | Assertion::EndText
141 | Assertion::StartLine { .. }
142 | Assertion::StartLineOniguruma { .. }
143 | Assertion::EndLine { .. },
144 ) = info.expr
145 {
146 return;
147 }
148 // \Z is an odd one out, although it is a zero-width assertion, for the purposes of seeking
149 // it still needs to consume the newlines
150 if let Expr::Assertion(Assertion::EndTextIgnoreTrailingNewlines { crlf }) = info.expr {
151 if *crlf {
152 buf.push_str(r"[\r\n]*");
153 } else {
154 buf.push_str(r"\n*");
155 }
156 return;
157 }
158 }
159
160 let has_capture_groups = info.start_group() != info.end_group();
161 if !info.hard && !has_capture_groups {
162 // Easy subtree — use to_str directly when no positional-anchor dropping is needed,
163 // or when the subtree contains no positional anchors (so dropping is a no-op).
164 if !drop_positional_anchors || !expr_contains_positional_anchor(info.expr) {
165 info.expr.to_str(buf, precedence);
166 return;
167 }
168 // The easy subtree contains positional anchors that need to be stripped.
169 // Fall through to the match below, which recurses via build_seek_pattern_impl.
170 }
171
172 match info.expr {
173 Expr::Empty | Expr::DefineGroup { .. } => {}
174 Expr::Assertion(assertion) => {
175 // Emit word boundaries, including half boundaries, as `to_str` writes them.
176 // Note: easy positional assertions (StartText, EndText, StartLine, EndLine) are
177 // handled by the to_str early return above (drop_positional_anchors=false) or by
178 // the early drop at the top of this function (drop_positional_anchors=true).
179 // Only hard assertions reach this arm.
180 match assertion {
181 Assertion::EndTextIgnoreTrailingNewlines { crlf: false } => buf.push_str(r"\n*$"),
182 Assertion::EndTextIgnoreTrailingNewlines { crlf: true } => {
183 buf.push_str(r"[\r\n]*$")
184 }
185 Assertion::WordBoundary
186 | Assertion::NotWordBoundary
187 | Assertion::LeftWordBoundary
188 | Assertion::RightWordBoundary
189 | Assertion::LeftWordHalfBoundary
190 | Assertion::RightWordHalfBoundary => info.expr.to_str(buf, precedence),
191 // Easy positional anchors — handled by early return / early drop above.
192 // They can only reach here when drop_positional_anchors=false and the subtree
193 // is easy (handled by to_str) but the Group/Concat parent fell through to match.
194 // Emit them faithfully.
195 Assertion::StartText
196 | Assertion::EndText
197 | Assertion::StartLine { .. }
198 | Assertion::StartLineOniguruma { .. }
199 | Assertion::EndLine { .. } => info.expr.to_str(buf, precedence),
200 }
201 }
202 Expr::Concat(_) => {
203 if precedence > 1 {
204 buf.push_str("(?:");
205 }
206 for child in &info.children {
207 build_seek_pattern_impl(
208 child,
209 group_info_map,
210 depth,
211 buf,
212 2,
213 drop_positional_anchors,
214 inlined_groups,
215 );
216 }
217 if precedence > 1 {
218 buf.push(')');
219 }
220 }
221 Expr::Alt(_) => {
222 if precedence > 0 {
223 buf.push_str("(?:");
224 }
225 let mut first = true;
226 for child in &info.children {
227 if !first {
228 buf.push('|');
229 }
230 build_seek_pattern_impl(
231 child,
232 group_info_map,
233 depth,
234 buf,
235 1,
236 drop_positional_anchors,
237 inlined_groups,
238 );
239 first = false;
240 }
241 if precedence > 0 {
242 buf.push(')');
243 }
244 }
245 Expr::Group(_) => {
246 // Drop the capture group wrapper; keep the contents.
247 if !info.children.is_empty() {
248 build_seek_pattern_impl(
249 &info.children[0],
250 group_info_map,
251 depth,
252 buf,
253 precedence,
254 drop_positional_anchors,
255 inlined_groups,
256 );
257 }
258 }
259 Expr::Repeat { lo, hi, .. } => {
260 if precedence > 2 {
261 buf.push_str("(?:");
262 }
263 if !info.children.is_empty() {
264 build_seek_pattern_impl(
265 &info.children[0],
266 group_info_map,
267 depth,
268 buf,
269 3,
270 drop_positional_anchors,
271 inlined_groups,
272 );
273 }
274 write_quantifier(buf, *lo, *hi, false);
275 if precedence > 2 {
276 buf.push(')');
277 }
278 }
279 Expr::Backref { group, casei }
280 | Expr::BackrefWithRelativeRecursionLevel { group, casei, .. } => {
281 // Inline the body of the referenced capture group, wrapping with (?i:...) when
282 // the backref is case-insensitive so the approximation remains correct.
283 //
284 // Positional anchors are dropped from the inlined body: a backref matches the
285 // captured text, not a position, so anchors from the group definition do not hold
286 // at the backref's position.
287 //
288 // For BackrefWithRelativeRecursionLevel, the relative_level is ignored here:
289 // for seeking purposes, the group body is the same regardless of recursion level.
290 //
291 // If inlining is not possible (depth limit, group not in map, or recursive cycle), emit a permissive
292 // placeholder so that no match positions are incorrectly skipped.
293 if depth < MAX_SUBROUTINE_RECURSION_DEPTH && buf.len() < MAX_SEEK_PATTERN_LEN {
294 if let Some(group_info) = group_info_map.get(group) {
295 if inlined_groups.contains(group) {
296 emit_min_size_placeholder(buf, group_info.min_size, precedence);
297 return;
298 }
299 if !group_info.children.is_empty() {
300 let child = &group_info.children[0];
301 inlined_groups.push(*group);
302 if *casei {
303 let mut inner = String::new();
304 build_seek_pattern_impl(
305 child,
306 group_info_map,
307 depth + 1,
308 &mut inner,
309 // Precedence 0 (alternation) so content inside (?i:...) is unambiguous.
310 0,
311 true,
312 inlined_groups,
313 );
314 inlined_groups.pop();
315 if !inner.is_empty() {
316 buf.push_str("(?i:");
317 buf.push_str(&inner);
318 buf.push(')');
319 }
320 } else {
321 build_seek_pattern_impl(
322 child,
323 group_info_map,
324 depth + 1,
325 buf,
326 precedence,
327 true,
328 inlined_groups,
329 );
330 inlined_groups.pop();
331 }
332 return;
333 }
334 // Empty group (no children): min_size=0, nothing to emit.
335 return;
336 }
337 }
338 // Could not inline (depth limit or group not found): emit a permissive placeholder
339 // so we don't falsely skip positions where the backref's target could have matched.
340 emit_min_size_placeholder(buf, info.min_size, precedence);
341 }
342 Expr::SubroutineCall(target_group) => {
343 // Inline the body of the target group once, honouring the recursion depth limit.
344 if depth < MAX_SUBROUTINE_RECURSION_DEPTH && buf.len() < MAX_SEEK_PATTERN_LEN {
345 if let Some(group_info) = group_info_map.get(target_group) {
346 if inlined_groups.contains(target_group) {
347 let placeholder_min = usize::from(group_info.min_size > 0);
348 emit_min_size_placeholder(buf, placeholder_min, precedence);
349 return;
350 }
351
352 if !group_info.children.is_empty() {
353 inlined_groups.push(*target_group);
354 build_seek_pattern_impl(
355 &group_info.children[0],
356 group_info_map,
357 depth + 1,
358 buf,
359 precedence,
360 drop_positional_anchors,
361 inlined_groups,
362 );
363 inlined_groups.pop();
364 return;
365 }
366 return;
367 }
368 }
369 emit_min_size_placeholder(buf, info.min_size, precedence);
370 }
371 // LookAround is zero-width — drop it.
372 Expr::LookAround(_, _) => {}
373 Expr::AtomicGroup(_) => {
374 // Keep the contents; atomicity is invisible to the seek approximation.
375 if !info.children.is_empty() {
376 build_seek_pattern_impl(
377 &info.children[0],
378 group_info_map,
379 depth,
380 buf,
381 precedence,
382 drop_positional_anchors,
383 inlined_groups,
384 );
385 }
386 }
387 Expr::GeneralNewline { unicode } => {
388 // Replace \R with an explicit alternation accepted by regex-automata.
389 if *unicode {
390 buf.push_str(r"(?:\r\n|[\n\x0B\x0C\r\x85\u{2028}\u{2029}])");
391 } else {
392 buf.push_str(r"(?:\r\n|[\n\x0B\x0C\r])");
393 }
394 }
395 Expr::Conditional { .. } => {
396 // Emit the union of (condition + true_branch) and (false_branch).
397 //
398 // Including the condition prefix in the true alternative ensures that consuming
399 // conditions (e.g. `(?(a)b|c)` where `a` is matched and consumed) are
400 // over-approximated correctly. For zero-width conditions (e.g. backref-exists
401 // checks) the condition emits nothing and the result degenerates to
402 // `true_branch | false_branch`, preserving the original behaviour.
403 let mut cond_pat = String::new();
404 let mut true_pat = String::new();
405 let mut false_pat = String::new();
406 if !info.children.is_empty() {
407 build_seek_pattern_impl(
408 &info.children[0],
409 group_info_map,
410 depth,
411 &mut cond_pat,
412 2,
413 drop_positional_anchors,
414 inlined_groups,
415 );
416 }
417 if info.children.len() >= 2 {
418 build_seek_pattern_impl(
419 &info.children[1],
420 group_info_map,
421 depth,
422 &mut true_pat,
423 2,
424 drop_positional_anchors,
425 inlined_groups,
426 );
427 }
428 if info.children.len() >= 3 {
429 build_seek_pattern_impl(
430 &info.children[2],
431 group_info_map,
432 depth,
433 &mut false_pat,
434 1,
435 drop_positional_anchors,
436 inlined_groups,
437 );
438 }
439 // Build the "condition then true-branch" alternative.
440 let cond_true = if cond_pat.is_empty() {
441 true_pat.clone()
442 } else if true_pat.is_empty() {
443 cond_pat.clone()
444 } else {
445 format!("(?:{}{})", cond_pat, true_pat)
446 };
447 if cond_true.is_empty() && false_pat.is_empty() {
448 return;
449 }
450 // An empty branch still matches the empty string. Keep it in the union
451 // so the seek pattern does not require the other branch to match.
452 if precedence > 0 {
453 buf.push_str("(?:");
454 }
455 buf.push_str(&cond_true);
456 buf.push('|');
457 buf.push_str(&false_pat);
458 if precedence > 0 {
459 buf.push(')');
460 }
461 }
462 // Absent repeater `(?~expr)` matches any content not containing `expr`.
463 // Approximate with `(?s:.*?)` (any characters, including newline) since the repeater
464 // can consume an arbitrary number of characters.
465 Expr::Absent(Absent::Repeater(_)) => buf.push_str("(?s:.*?)"),
466 // Absent expression `(?~|absent|exp)` matches `exp` subject to the absent constraint.
467 // Approximate by seeking only for `exp`, dropping the constraint — this is a safe
468 // over-approximation since any position where `exp` matches (ignoring the constraint)
469 // is a superset of positions where the full expression matches.
470 Expr::Absent(crate::Absent::Expression { .. }) => {
471 if info.children.len() >= 2 {
472 build_seek_pattern_impl(
473 &info.children[1],
474 group_info_map,
475 depth,
476 buf,
477 precedence,
478 drop_positional_anchors,
479 inlined_groups,
480 );
481 }
482 }
483 // Zero-width / control nodes — drop them (all have min_size = 0).
484 Expr::KeepOut
485 | Expr::ContinueFromPreviousMatchEnd
486 | Expr::BacktrackingControlVerb(_)
487 | Expr::BackrefExistsCondition { .. }
488 | Expr::Absent(_) => {}
489 // Approximate since we don't want to have to deal with ascii vs unicode handling here
490 Expr::LiteralBytes { bytes } => buf.push_str(&format!("(?s:.{{0,{}}}?)", bytes.len())),
491 // Easy leaf nodes (Literal, Any, Delegate) are always handled by the easy no-captures
492 // early return above and never reach here. Listed explicitly so that adding a new
493 // Expr variant produces a compile error until the seek-pattern case is handled.
494 Expr::Literal { .. } | Expr::Any { .. } | Expr::Delegate { .. } => {
495 info.expr.to_str(buf, precedence)
496 }
497 // These variants cause a compile error during analysis and are therefore unreachable
498 // after a successful `analyze()` call.
499 Expr::AstNode(..) => {
500 unreachable!("unexpected expr variant after analysis")
501 }
502 }
503}
504
505/// Returns `true` if `pattern` contains at least one character that provides useful filtering
506/// (i.e. a literal character, character class, or anchor rather than just wildcards/quantifiers).
507///
508/// This is a conservative approximation: any pattern containing `[`, `\`, `^`, `$`, or an
509/// alphanumeric character is considered useful. The primary goal is to reject fully
510/// unconstrained patterns such as `.*`.
511pub fn seek_pattern_is_useful(pattern: &str) -> bool {
512 pattern
513 .bytes()
514 .any(|b| matches!(b, b'[' | b'\\' | b'^' | b'$' | b'A'..=b'Z' | b'a'..=b'z' | b'0'..=b'9'))
515}
516
517#[cfg(test)]
518mod tests {
519 use super::*;
520 use crate::analyze::{analyze, AnalyzeContext};
521 use crate::compile::populate_group_info_map;
522 use crate::optimize;
523 use crate::ExprTree;
524 use crate::Regex;
525 use alloc::string::ToString;
526
527 /// Build the seek pattern for a regex string and return it.
528 fn get_seek_pattern(re: &str) -> String {
529 let mut tree = Expr::parse_tree(re).unwrap();
530 get_seek_pattern_for_tree(&mut tree)
531 }
532
533 /// Build the seek pattern for a regex string parsed with the given flags.
534 fn get_seek_pattern_with_flags(re: &str, flags: u32) -> String {
535 let mut tree = Expr::parse_tree_with_flags(re, flags).unwrap();
536 get_seek_pattern_for_tree(&mut tree)
537 }
538
539 // Build the seek pattern for the given ExprTree
540 fn get_seek_pattern_for_tree(tree: &mut ExprTree) -> String {
541 let requires_capture_group_fixup = optimize(tree);
542
543 let info = analyze(
544 &tree,
545 AnalyzeContext {
546 explicit_capture_group_0: requires_capture_group_fixup,
547 ..AnalyzeContext::default()
548 },
549 )
550 .unwrap();
551
552 let mut group_info_map = Map::new();
553 populate_group_info_map(&mut group_info_map, &info);
554 let mut buf = String::new();
555 build_seek_pattern(&info, &group_info_map, 0, &mut buf, 0);
556 buf
557 }
558
559 #[test]
560 fn seek_pattern_conditionals_preserve_empty_alternatives() {
561 for (pattern, haystack) in [
562 (r"(a)?b(?(1)c)", "b"),
563 (r"(a)?b(?(1)c|)", "b"),
564 (r"(a)?b(?(1)|c)", "ab"),
565 ] {
566 let seek_pattern = get_seek_pattern(pattern);
567 assert!(
568 regex::Regex::new(&seek_pattern).unwrap().is_match(haystack),
569 "{pattern:?} produced {seek_pattern:?}, excluding {haystack:?}"
570 );
571 }
572 }
573
574 #[test]
575 fn seek_pattern_backref_no_anchor() {
576 // Simple backref with no positional anchors: group body is inlined verbatim.
577 // The `(?:...)` wrapping comes from Concat precedence handling when stripping groups.
578 assert_eq!(get_seek_pattern(r"(abc)\1"), "(?:abc)(?:abc)");
579 assert_eq!(
580 get_seek_pattern(r"(?i)(abc)\1"),
581 "(?:(?i:a)(?i:b)(?i:c))(?i:(?i:a)(?i:b)(?i:c))"
582 );
583 }
584
585 #[test]
586 fn seek_pattern_backref_with_start_anchor() {
587 // Backref to a group whose body starts with `^`: the anchor should be dropped from the
588 // inlined backref position but kept at the group definition site.
589 // `(^a)\1` — seek = `(?:^a)` (group) + `(?:a)` (backref, anchor dropped)
590 assert_eq!(get_seek_pattern(r"(^a)\1"), "(?:^a)(?:a)");
591 }
592
593 #[test]
594 fn seek_pattern_backref_with_start_anchor_variable_length() {
595 // The group has a start anchor plus a variable-length content.
596 // Anchor is dropped when inlining for the backref.
597 assert_eq!(get_seek_pattern(r"(^a+)\1"), "(?:^a+)(?:a+)");
598 }
599
600 #[test]
601 fn seek_pattern_backref_with_end_anchor() {
602 // Backref to a group ending with `$`: the anchor is dropped in the inline position.
603 assert_eq!(get_seek_pattern(r"(a$)\1"), "(?:a$)(?:a)");
604 }
605
606 #[test]
607 fn seek_pattern_backref_only_anchor() {
608 // Backref to a group that is only a positional anchor.
609 // The group emits `^` (min_size=0); the backref drops `^` and emits nothing.
610 assert_eq!(get_seek_pattern(r"(^)\1"), "^");
611 }
612
613 #[test]
614 fn seek_pattern_lookahead_dropped() {
615 // Lookahead is zero-width and is dropped; only the literal is kept.
616 assert_eq!(get_seek_pattern(r"(?=foo)bar"), "bar");
617 }
618
619 #[test]
620 fn seek_pattern_casei_literal_backref_with_anchor() {
621 // Group contains a case-insensitive literal and a start anchor.
622 // The anchor is dropped during backref inlining; the casei literal emits (?i:...).
623 assert_eq!(get_seek_pattern(r"(?i:(^a))\1"), "(?:^(?i:a))(?:(?i:a))");
624 }
625
626 #[test]
627 fn seek_pattern_easy_expr_preserved() {
628 // Easy (non-hard) expressions without capture groups are serialised verbatim via to_str.
629 assert_eq!(get_seek_pattern(r"abc"), "abc");
630 assert_eq!(get_seek_pattern(r"a|b"), "a|b");
631 assert_eq!(get_seek_pattern(r"a+b*c?"), "a+b*c?");
632 assert_eq!(get_seek_pattern(r"\ba+b*c?\b"), r"\ba+b*c?\b");
633 assert_eq!(
634 get_seek_pattern(r"\b{start-half}foo\b{end-half}"),
635 r"\b{start-half}foo\b{end-half}"
636 );
637 }
638
639 #[test]
640 fn seek_pattern_easy_expr_with_capture_group_strips_group_wrapper() {
641 // Easy expressions with capture groups drop the capture group wrappings.
642 assert_eq!(get_seek_pattern(r"(abc)"), "abc");
643 assert_eq!(
644 get_seek_pattern(r"(abc(def))(?<named>ghi)"),
645 "(?:abc(?:def))(?:ghi)"
646 );
647 }
648
649 #[test]
650 fn seek_pattern_optimized_easy_expr_strips_group_wrapper() {
651 // Optimized patterns lose the capture group wrappings
652 assert_eq!(get_seek_pattern(r"(?=abc)"), "(?:abc)");
653 assert_eq!(
654 get_seek_pattern(r"(h)(e)(l)(l)(o)\s*(?=world)"),
655 r"(?:hello\s*)(?:world)"
656 );
657 }
658
659 #[test]
660 fn seek_pattern_end_text_ignore_trailing_newlines_non_crlf() {
661 // \Z (non-CRLF mode) — approximate with `\n*$` so the seek only visits positions
662 // near end-of-text.
663 assert_eq!(get_seek_pattern(r"abc\Z"), r"abc\n*$");
664 }
665
666 #[test]
667 fn seek_pattern_end_text_ignore_trailing_newlines_crlf() {
668 // \Z in CRLF mode — approximate with `(?:\r?\n)*$`.
669 assert_eq!(get_seek_pattern(r"(?R)abc\Z"), r"abc[\r\n]*$");
670 }
671
672 #[test]
673 fn seek_pattern_end_text_ignore_trailing_newlines_only() {
674 // \Z alone (hard assertion) — just the seek pattern with no surrounding literal.
675 assert_eq!(get_seek_pattern(r"\Z"), r"\n*$");
676 }
677
678 #[test]
679 fn seek_pattern_backref_with_end_text_ignore_trailing_newlines() {
680 // Backref to a group that ends with \Z: \Z is a positional anchor and should be
681 // dropped when inlining the group body for the backref.
682 // `(a\Z)\1` — seek = `(?:a\n*$)` (group) + `(?:a\n*)` (backref, \Z anchor dropped, newline matching kept)
683 assert_eq!(get_seek_pattern(r"(a\Z)\1"), r"(?:a\n*$)(?:a\n*)");
684 }
685
686 #[test]
687 fn seek_pattern_subroutine_call_inlined() {
688 assert_eq!(
689 get_seek_pattern(r"([A-Z][a-z0-9]*)::\g<1>"),
690 r"(?:[A-Z][a-z0-9]*)::(?:[A-Z][a-z0-9]*)"
691 );
692 }
693
694 #[test]
695 fn seek_pattern_subroutine_call_inlined_and_anchors_are_preserved() {
696 assert_eq!(
697 get_seek_pattern(r"((?m:^)[A-Z][a-z0-9]*)\n\g<1>"),
698 "(?:(?m:^)[A-Z][a-z0-9]*)\\n(?:(?m:^)[A-Z][a-z0-9]*)"
699 );
700 }
701
702 #[test]
703 fn seek_pattern_self_referential_backref_is_bounded() {
704 // Inlining a backref whose target transitively references the backref's
705 // own ancestors would expand exponentially with recursion depth if we
706 // didn't have cycle detection or a length cap to cause it to fall back
707 // to a permissive placeholder instead of continuing to recurse.
708 // Together these help to keep the seek pattern small (and, therefore, compilation
709 // fast) rather than producing a multi-megabyte string which would likely not help
710 // to narrow candidate start positions much better anyway.
711 let seek = get_seek_pattern(r"(end)(\s+(function))?(\s+((\3|\4|\5)))?");
712 assert!(
713 seek.len() <= MAX_SEEK_PATTERN_LEN,
714 "seek pattern should stay bounded, got {} bytes",
715 seek.len()
716 );
717 // Compiling it must succeed and stay well-formed.
718 Regex::new(r"(end)(\s+(function))?(\s+((\3|\4|\5)))?").unwrap();
719 }
720
721 #[test]
722 fn seek_recursive_subroutine_with_empty_base_preserves_leftmost_match() {
723 let pattern = r"(?<g>(?:a\g<g>)?)b";
724 let haystack = "aab";
725
726 let mut options_no_seek = crate::RegexOptionsBuilder::new();
727 let expected = options_no_seek
728 .seek(false)
729 .build(pattern.to_string())
730 .unwrap()
731 .find(haystack)
732 .unwrap();
733
734 let mut options = crate::RegexOptionsBuilder::new();
735 options.seek(true);
736 let actual = options
737 .build(pattern.to_string())
738 .unwrap()
739 .find(haystack)
740 .unwrap();
741
742 assert_eq!(
743 expected.map(|m| (m.start(), m.end())),
744 actual.map(|m| (m.start(), m.end()))
745 );
746 assert_eq!(expected.unwrap().start, 0);
747 }
748
749 #[test]
750 fn seek_pattern_recursive_subroutine_is_inlined_once() {
751 let pattern = r"(?<tuple>\((?:[^()]|\g<tuple>)+\))\s*(?!=[=>])(?==)";
752 let seek = get_seek_pattern(pattern);
753 assert_eq!(
754 seek,
755 r#"(?:(?:\((?:[^()]|\((?:[^()]|(?s:.)+?)+?\))+?\))\s*)="#
756 );
757 }
758
759 #[test]
760 fn seek_pattern_literal_bytes() {
761 // In Unicode mode \xFF parses to a `Literal` (handled by the easy to_str path).
762 assert_eq!(get_seek_pattern(r"\xFF"), r"ÿ");
763 }
764
765 #[test]
766 fn seek_pattern_literal_bytes_ascii_mode() {
767 // In non-Unicode mode \xFF parses to `LiteralBytes`, which is hard and so
768 // reaches the seek-pattern arm that interpolates the byte length.
769 assert_eq!(get_seek_pattern_with_flags(r"\xFF", 0), r"(?s:.{0,1}?)");
770 // Two separate byte escapes are a Concat of two LiteralBytes nodes.
771 assert_eq!(
772 get_seek_pattern_with_flags(r"\xFF\xFF", 0),
773 r"(?s:.{0,1}?)(?s:.{0,1}?)"
774 );
775 }
776}