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.
• Visited 🔒
  A bitset that keeps track of whether a particular (StateID, offset) has been considered during backtracking. If it has already been visited, then backtracking skips it. This is what gives backtracking its “bound.”

Enums

• Frame 🔒
  Represents a stack frame on the heap while doing backtracking.

Functions

• div_ceil 🔒
  Integer division, but rounds up instead of down.
• min_visited_capacity
  Returns the minimum visited capacity for the given haystack.