Module regex_automata::nfa::thompson::backtrack

An NFA backed bounded backtracker for executing regex searches with capturing groups.

This module provides a BoundedBacktracker that works by simulating an NFA using the classical backtracking algorithm with a twist: it avoids redoing work that it has done before and thereby avoids worst case exponential time. In exchange, it can only be used on “short” haystacks. Its advantage is that is can be faster than the PikeVM in many cases because it does less book-keeping.

Structs

• BoundedBacktracker
  A backtracking regex engine that bounds its execution to avoid exponential blow-up.
• Builder
  A builder for a bounded backtracker.
• Cache
  A cache represents mutable state that a BoundedBacktracker requires during a search.
• Config
  The configuration used for building a bounded backtracker.
• TryCapturesMatches
  An iterator over all non-overlapping leftmost matches, with their capturing groups, for a fallible search.
• TryFindMatches
  An iterator over all non-overlapping matches for a fallible search.

Functions

• min_visited_capacity
  Returns the minimum visited capacity for the given haystack.