Simple example to do overlapping regex matches

[gagbo]

Hello,

I am a regex noob, but I’d like to have a function that returns all matches from a DFA regex (because I have lookahead in some regexes). From the documentation about the try_search_overlapping_fwd function I got this far: (playground code replicated below the link) https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=dbf731b8968f35412e9ff5340351c634

use regex_automata::{
    Input, MatchKind,
    hybrid::dfa::{DFA, OverlappingState},
}; // 0.4.9

const EMAIL_REGEX: &str = r"[a-zA-Z0-9-_.]*[a-zA-Z0-9_](@[a-zA-Z0-9_]+)(\.[a-zA-Z0-9_]+(\.[a-zA-Z0-9_]+)?[a-zA-Z])(?-u:\b)";
const SHA_REGEX: &str = r"(?-u:\b)[0-9a-fA-F]{7,28}(?-u:\b)";

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Match {
    pattern_id: usize,
    offset_start: usize,
    offset_end: usize,
}

fn main() {
    let haystack = "email@deadbeef.com";
    assert_eq!(
        &find_all_matches(haystack),
        &[
            Match {
                pattern_id: 0,
                offset_start: 0,
                offset_end: 18,
            },
            Match {
                pattern_id: 1,
                offset_start: 6,
                offset_end: 14,
            }
        ]
    )
}

fn find_all_matches(haystack: &str) -> Vec<Match> {
    let dfa = DFA::builder()
        .configure(DFA::config().match_kind(MatchKind::All))
        .build_many(&[EMAIL_REGEX, SHA_REGEX])
        .unwrap();
    let mut cache = dfa.create_cache();
    let mut state = OverlappingState::start();

    let mut matches = Vec::<Match>::new();

    loop {
        if dfa
            .try_search_overlapping_fwd(&mut cache, &Input::new(haystack), &mut state)
            .is_err()
        {
            break;
        }
        let Some(half_match) = state.get_match() else {
            break;
        };
        // half_match reports the end of the first match
        todo!("Combine this half match with a reverse search to complete the match")
    }

    matches
}

But now that I successfully have a half_match, I don’t know how I’m supposed to get complete matches from it:

• I’m assuming I need to somehow loop, in case a single pattern has multiple matches ending at the same offset (but starting at different offsets in the haystack)
• Should I reuse the same dfa? Another one with a reverse flag?
• Should I clone/reuse the state in the try_search_overlapping_rev call that I need to make somewhere?

It is a bit hand-holding I know, but I really can’t figure out how to close the loop there.

Thanks for the library anyways,

Gerry

[BurntSushi]

Does this code snippet and comment help? I think it's what you're trying to do:

regex/regex-automata/tests/dfa/suite.rs

Lines 393 to 443 in 1a069b9

	/// Execute an overlapping search, and for each match found, also find its
	/// overlapping starting positions.
	///
	/// N.B. This routine used to be part of the crate API, but 1) it wasn't clear
	/// to me how useful it was and 2) it wasn't clear to me what its semantics
	/// should be. In particular, a potentially surprising footgun of this routine
	/// that it is worst case *quadratic* in the size of the haystack. Namely, it's
	/// possible to report a match at every position, and for every such position,
	/// scan all the way to the beginning of the haystack to find the starting
	/// position. Typical leftmost non-overlapping searches don't suffer from this
	/// because, well, matches can't overlap. So subsequent searches after a match
	/// is found don't revisit previously scanned parts of the haystack.
	///
	/// Its semantics can be strange for other reasons too. For example, given
	/// the regex '.*' and the haystack 'zz', the full set of overlapping matches
	/// is: [0, 0], [1, 1], [0, 1], [2, 2], [1, 2], [0, 2]. The ordering of
	/// those matches is quite strange, but makes sense when you think about the
	/// implementation: an end offset is found left-to-right, and then one or more
	/// starting offsets are found right-to-left.
	///
	/// Nevertheless, we provide this routine in our test suite because it's
	/// useful to test the low level DFA overlapping search and our test suite
	/// is written in a way that requires starting offsets.
	fn try_search_overlapping<A: Automaton>(
	re: &Regex<A>,
	input: &Input<'_>,
	) -> Result<TestResult> {
	let mut matches = vec![];
	let mut fwd_state = OverlappingState::start();
	let (fwd_dfa, rev_dfa) = (re.forward(), re.reverse());
	while let Some(end) = {
	fwd_dfa.try_search_overlapping_fwd(input, &mut fwd_state)?;
	fwd_state.get_match()
	} {
	let revsearch = input
	.clone()
	.range(input.start()..end.offset())
	.anchored(Anchored::Pattern(end.pattern()))
	.earliest(false);
	let mut rev_state = OverlappingState::start();
	while let Some(start) = {
	rev_dfa.try_search_overlapping_rev(&revsearch, &mut rev_state)?;
	rev_state.get_match()
	} {
	let span = Span { start: start.offset(), end: end.offset() };
	let mat = Match { id: end.pattern().as_usize(), span };
	matches.push(mat);
	}
	}
	Ok(TestResult::matches(matches))
	}

[gagbo]

So, yes! That was exactly what I was looking for! But! https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=621360e40dfdea8605f610ea4d7b06c4

use regex_automata::{
    Anchored, Input, MatchKind,
    hybrid::dfa::{DFA, OverlappingState},
    hybrid::regex::{Cache, Regex},
}; // 0.4.9

const EMAIL_REGEX: &str = r"[a-zA-Z0-9-_.]*[a-zA-Z0-9_](@[a-zA-Z0-9_]+)(\.[a-zA-Z0-9_]+(\.[a-zA-Z0-9_]+)?[a-zA-Z])(?-u:\b)";
const SHA_REGEX: &str = r"(?-u:\b)[0-9a-fA-F]{7,28}(?-u:\b)";

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Match {
    pattern_id: usize,
    offset_start: usize,
    offset_end: usize,
}

fn main() {
    let haystack = "email@deadbeef.com";
    assert_eq!(
        &find_all_matches(haystack),
        &[
            Match {
                pattern_id: 0,
                offset_start: 0,
                offset_end: 18,
            },
            Match {
                pattern_id: 1,
                offset_start: 6,
                offset_end: 14,
            }
        ]
    )
}

fn find_all_matches(haystack: &str) -> Vec<Match> {
    let re = Regex::new_many(&[EMAIL_REGEX, SHA_REGEX]).unwrap();
    let mut cache = re.create_cache();
    try_search_overlapping(&re, &mut cache, &Input::new(haystack))
}

fn try_search_overlapping(re: &Regex, cache: &mut Cache, input: &Input<'_>) -> Vec<Match> {
    let mut matches = vec![];
    let mut fwd_state = OverlappingState::start();
    let (fwd_dfa, rev_dfa) = (re.forward(), re.reverse());
    let (fwd_cache, rev_cache) = cache.as_parts_mut();
    while let Some(end) = {
        fwd_dfa.try_search_overlapping_fwd(fwd_cache, input, &mut fwd_state).unwrap();
        fwd_state.get_match()
    } {
        let revsearch = input
            .clone()
            .range(input.start()..end.offset())
            .anchored(Anchored::Pattern(end.pattern()))
            .earliest(false);
        let mut rev_state = OverlappingState::start();
        while let Some(start) = {
            rev_dfa.try_search_overlapping_rev(rev_cache, &revsearch, &mut rev_state).unwrap();
            rev_state.get_match()
        } {
            let mat = Match {
                pattern_id: end.pattern().as_usize(),
                offset_start: start.offset(),
                offset_end: end.offset(),
            };

            matches.push(mat);
        }
    }
    matches
}

leads to called Result::unwrap()on anErr value: MatchError(UnsupportedAnchored { mode: Pattern(PatternID(1)) }), and even removing the (?-u:\b) from the SHA regex didn’t seem to fix that. So I assume that the {7, 28} bit prevents Anchoring?

At least I’m a lot closer now, so anyway I can try to debug myself out a bit

[BurntSushi]

I think you need to enable https://docs.rs/regex-automata/latest/regex_automata/dfa/dense/struct.Config.html#method.starts_for_each_pattern

[gagbo]

Yeah I just figured that out!! Thanks

Final code to mark the answer:

use regex_automata::{
    Anchored, Input, MatchKind,
    hybrid::dfa::{DFA, OverlappingState},
    hybrid::regex::{Cache, Regex},
}; // 0.4.9

const EMAIL_REGEX: &str = r"[a-zA-Z0-9-_.]*[a-zA-Z0-9_](@[a-zA-Z0-9_]+)(\.[a-zA-Z0-9_]+(\.[a-zA-Z0-9_]+)?[a-zA-Z])(?-u:\b)";
const SHA_REGEX: &str = r"(?-u:\b)[0-9a-fA-F]{7,28}(?-u:\b)";

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Match {
    pattern_id: usize,
    offset_start: usize,
    offset_end: usize,
}

fn main() {
    let haystack = "email@deadbeef.com";
    assert_eq!(
        &find_all_matches(haystack),
        &[
            Match {
                pattern_id: 1,
                offset_start: 6,
                offset_end: 14,
            },
            // There are a lot of valid emails in this string. And they are sorted by _decreasing_ start offset, 
            // as what a reverse search would do.
            Match {
                pattern_id: 0,
                offset_start: 4,
                offset_end: 18,
            },
            Match {
                pattern_id: 0,
                offset_start: 3,
                offset_end: 18,
            },
            Match {
                pattern_id: 0,
                offset_start: 2,
                offset_end: 18,
            },
            Match {
                pattern_id: 0,
                offset_start: 1,
                offset_end: 18,
            },
            Match {
                pattern_id: 0,
                offset_start: 0,
                offset_end: 18,
            },
        ]
    )
}

fn find_all_matches(haystack: &str) -> Vec<Match> {
    let re = Regex::builder()
        .dfa(
            DFA::config()
                .match_kind(MatchKind::All)
                .starts_for_each_pattern(true),
        )
        .build_many(&[EMAIL_REGEX, SHA_REGEX])
        .unwrap();
    let mut cache = re.create_cache();
    try_search_overlapping(&re, &mut cache, &Input::new(haystack))
}

fn try_search_overlapping(re: &Regex, cache: &mut Cache, input: &Input<'_>) -> Vec<Match> {
    let mut matches = vec![];
    let mut fwd_state = OverlappingState::start();
    let (fwd_dfa, rev_dfa) = (re.forward(), re.reverse());
    let (fwd_cache, rev_cache) = cache.as_parts_mut();
    while let Some(end) = {
        fwd_dfa
            .try_search_overlapping_fwd(fwd_cache, input, &mut fwd_state)
            .unwrap();
        fwd_state.get_match()
    } {
        let revsearch = input
            .clone()
            .range(input.start()..end.offset())
            .anchored(Anchored::Pattern(end.pattern()))
            .earliest(false);
        let mut rev_state = OverlappingState::start();
        while let Some(start) = {
            rev_dfa
                .try_search_overlapping_rev(rev_cache, &revsearch, &mut rev_state)
                .unwrap();
            rev_state.get_match()
        } {
            let mat = Match {
                pattern_id: end.pattern().as_usize(),
                offset_start: start.offset(),
                offset_end: end.offset(),
            };

            matches.push(mat);
        }
    }
    matches
}

Thanks again, just a small note: while looking for this starts_for_each_pattern solution, I encountered this snippet in docs: https://docs.rs/regex-automata/latest/regex_automata/hybrid/dfa/struct.Config.html#example-reverse-automaton-to-find-start-of-match It might have helped me figuring out the Anchored API + needing to starts_for_each_pattern solution, but not sure.

[BurntSushi]

Yeah... it's always hard to know where to put the examples in a way that they get discovered in a crate like this. The API is so big and sprawling.

I wonder if adding some kind of hint to the MatchErrorKind::UnsupportedAnchored error variant would help. When you got that error, did you check the docs on it? If so, that might be the best place to put a link to starts_for_each_pattern.

[gagbo]

I’ve been there, but the comment is a bit sparse:

An error indicating that a particular type of anchored search was requested, but that the regex engine does not support it.

Just saying that the most common cases/mandatory conditions for DFA/NFA are to have the starts_for_each_pattern might help (I assume that starts_for_each_pattern is mandatory for Anchored(PatternId(_)) variant; I don’t know what’s necessary for the Yes one)

[BurntSushi]

Aye thanks, I've filed an issue tracking that here: #1262