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