dfa#

Synopsis#

The capture-free maximal-munch engine, opt-in via <real/dfa.hpp> (not pulled in by <real/real.hpp>). Several patterns compile into one automaton walked one table transition per byte – lexer-grade tokenizing. The contract: the longest match wins; on equal length the earliest pattern (lowest index) wins; an empty match never wins. No capture groups – that is the trade-off against basic_regex.

Interface#

class dfa#

A multi-rule DFA: maximal-munch (dfa_mode::munch) or which-matched unanchored scan (dfa_mode::which_matched).

Built once (heap-allocated tables), then immutable. match is the lexer munch; which_matched is valid only when built with dfa_mode::which_matched.

Public Functions

inline explicit dfa(std::span<const detail::program_view> programs, dfa_mode mode = dfa_mode::munch)#

Builds the DFA from compiled programs (the embedder path).

Warning

An advanced, unstable extension point: detail::program_view is an implementation type, and its members may change in any release. Build from regexes instead unless the programs come from an embedder that already holds them.

Parameters:

  • programs – [in] The patterns’ programs, in priority order (see regex::raw_program).

  • mode – [in] Munch (default) or which-matched unanchored multi-accept.

Throws:

real::dfa_error – for a pattern that is not DFA-able (see dfa_error).

inline explicit dfa(std::span<const regex> patterns, dfa_mode mode = dfa_mode::munch)#

Builds the DFA from regexes (a convenience over regex::raw_program).

Parameters:

  • patterns – [in] The patterns, in priority order; they must outlive this call.

  • mode – [in] Munch (default) or which-matched.

Throws:

real::dfa_error – for a pattern that is not DFA-able (see dfa_error).

inline std::optional<dfa_match> match(std::string_view rest) const noexcept#

Matches the longest pattern anchored at the start of rest.

Maximal munch: the longest match wins; on equal length the earliest pattern (lowest index passed to the constructor) wins; an empty match never wins.

Parameters:

rest – [in] The text to match at its start.

Returns:

The winning rule index and byte length, or std::nullopt if nothing non-empty matches.

inline std::optional<dfa_match> match(std::string_view subject, std::size_t offset, dfa_munch_memo &memo) const#

match(std::string_view) const at offset of subject, remembering in memo what the walk proved so that successive calls over the same subject cost linear time in total.

Answers exactly what match(subject.substr(offset)) answers.

Parameters:

  • subject – [in] The whole subject; every call with memo must pass the same one.

  • offset – [in] Where this munch starts (at most subject.size()).

  • memo – [inout] The subject’s memo (see dfa_munch_memo).

Throws:

std::invalid_argument – If memo was made for a subject of another length, was used with another DFA, or offset lies beyond subject.

Returns:

The winning rule index and byte length, or std::nullopt if nothing non-empty matches.

inline dfa_munch munch(std::string_view subject, std::size_t offset, dfa_munch_memo &memo) const#

match(std::string_view, std::size_t, dfa_munch_memo&) const, and whether text after subject could change the answer: a lexer reading text that arrives in pieces commits to a munch only when it could not.

The walk is the same; telling costs nothing more. A walk that died within the subject proves the answer final, whatever follows; so does one that ends in a state every byte leaves for the dead one, and one the memo stopped while every stretch it marked was walked to a death. Any other walk alive at the subject’s end may not be final.

Parameters:

  • subject – [in] The text so far; every call with memo must pass the same one.

  • offset – [in] Where this munch starts (at most subject.size()).

  • memo – [inout] The subject’s memo (see dfa_munch_memo).

Throws:

std::invalid_argument – As match(std::string_view, std::size_t, dfa_munch_memo&) const.

Returns:

The munch and whether more text may change it.

inline std::vector<bool> which_matched(std::string_view text, bool first_byte_skip = true) const#

Which patterns match the subject at least once (single-pass).

Requires a build with dfa_mode::which_matched. Early-exits when every pattern has hit. The start state’s accept mask is folded in before the walk, so a rule accepting the EMPTY string answers true on an empty subject, as N separate walks would; every other accept comes from a post-move mask.

Parameters:

  • text – [in] Subject text.

  • first_byte_skip – [in] When true (default), fast-forward over bytes that cannot start any rule while the walk is in the start state; false is for equivalence tests.

Returns:

One bool per rule, in construction order, true where that pattern matched.

inline bool has_first_byte_skip() const noexcept#

True if set-level first-byte skip is armed for which_matched.

Returns:

Whether every rule contributed a valid first-byte set at build time.

inline bool is_unanchored() const noexcept#

True if this DFA was built with mid-stream restart (which-matched mode).

Returns:

Whether the tables carry self-restart transitions.

inline std::size_t state_count() const noexcept#

The number of states in the minimized automaton (includes the dead state).

Returns:

The state count.

inline std::size_t rule_count() const noexcept#

The number of patterns the DFA was built from.

Returns:

The rule count, which is also the width of which_matched’s answer.

inline std::size_t class_count() const noexcept#

The number of byte-equivalence classes (the reduced alphabet width).

Returns:

The class count.

struct dfa_match#

The outcome of dfa::match — which rule won, and how many bytes it spans.

Public Members

std::uint32_t rule_index#

Index of the winning pattern, in the order passed to the ctor.

std::size_t length#

Byte length of the (non-empty) match.

struct dfa_munch#

A munch, and whether text after the subject could change it (dfa::munch).

Public Members

std::optional<dfa_match> match#

The winning rule and length, as dfa::match answers.

bool more_text_may_change#

False once the walk died within the subject, or the memo stopped it on a stretch walked to a death: no text appended after the subject can change match. True when the walk was still alive at the subject’s end, or the memo stopped it on a stretch proven dead for this subject only.

enum class real::dfa_mode : std::uint8_t#

Build mode for real::dfa: maximal munch at the cursor (a lexer; the default), or an unanchored multi-accept single pass (which patterns match anywhere).

Values:

enumerator munch#

One winner at the start of the subject.

enumerator which_matched#

Mid-stream restart; full accept-mask per state for which-matched.

class dfa_munch_memo#

What successive munches over ONE subject have learnt, so that tokenizing the whole subject costs O(states × length) instead of O(length²) (Reps, “Maximal-munch tokenization in linear

time”, 1998).

A munch walks the DFA until it dies or the subject ends, then answers its last accepting position. Every (state, position) visited after that position leads to no accept, so a later munch reaching the same pair can stop there with the answer it holds. Without this, a rule like a*b beside a rescans the rest of aaa… from every position.

Bound to one dfa and one subject: pass it to dfa::match(std::string_view, std::size_t,dfa_munch_memo&) const with the same pair every time. Memory is one bit per remembered state per subject position, allocated on a state’s first mark; a walk replays its dead stretch to mark it rather than holding it.

Public Functions

inline explicit dfa_munch_memo(std::size_t subject_size)#

An empty memo for one subject.

Parameters:

subject_size – [in] The subject’s length in bytes.

inline std::size_t transitions() const noexcept#

DFA transitions taken by every munch so far &#8212; the work the bound is stated in.

Returns:

The count, summed over every call that used this memo.

inline bool armed() const noexcept#

Whether a walk over this subject has run more than short_stretch steps past its last accept, so later walks consult the memo; until then it holds nothing and costs nothing.

Returns:

True once armed.

Public Static Attributes

static constexpr std::size_t short_stretch = {32}#

The longest stretch after a walk’s last accept that is left unmarked. A later walk reaching one of its pairs dies within that many steps on its own, so the bound stays linear (O(length x (states + short_stretch))). The first longer stretch also arms the memo: until then no walk consults it, so an ordinary tokenization pays nothing for it.

class dfa_error : public std::runtime_error#

Thrown when a pattern cannot be represented as a DFA.

Five causes: a zero-width assertion other than a leading \A/^ ($, \b, \B, multiline anchors), a lookaround, a possessive quantifier / atomic group, a code-point class whose UTF-8 expansion is too large (text-mode \w, or a class repeated many times; \d, \p{Greek} or [àé] build), or an automaton past the state cap (65 536 states). Never a silent fallback: the caller decides, e.g. by keeping that rule on the Pike VM.

inline dfa_fidelity real::dfa_faithful(const regex &pattern, std::size_t state_budget = dfa_default_state_budget)#

Decides whether pattern's match() is always its longest match &#8212; whether a dfa built from it reproduces pattern.match() on every input.

The answer is EXACT for the pattern, never a sample: faithful holds for every input, and divergent comes with an input that proves it. Only the search’s size is bounded; past state_budget the answer is undecided, which a caller must treat as not faithful.

Parameters:

  • pattern – [in] The pattern to decide.

  • state_budget – [in] Product states the search may explore.

Throws:

real::dfa_error – for a pattern that is not DFA-able (see dfa_error).

Returns:

The decision, with a witness when divergent.

inline dfa_fidelity real::dfa_faithful(std::span<const regex> patterns, std::size_t state_budget = dfa_default_state_budget)#

Decides real::dfa_faithful for each of patterns, in order, and answers for the first one not proven faithful (its index in dfa_fidelity::rule_index).

faithful means every pattern is, which is SUFFICIENT for a dfa over the set to reproduce the per-rule match() munch (longest wins, earliest on a tie, empty never wins): with every rule’s match() equal to its longest match, both reach the same length and the same earliest rule. It is not NECESSARY &#8212; a divergent rule that a higher-priority rule always outlasts changes no answer, and this still refuses the set. That refusal is correct, only cautious; an acceptance is never wrong.

Parameters:

  • patterns – [in] The patterns, in priority order.

  • state_budget – [in] Product states each pattern’s search may explore.

Throws:

real::dfa_error – for a pattern that is not DFA-able (see dfa_error).

Returns:

The first non-faithful pattern’s decision, or faithful.

struct dfa_fidelity#

The answer of real::dfa_faithful.

Public Members

dfa_fidelity_outcome outcome = {dfa_fidelity_outcome::faithful}#

The decision.

std::size_t rule_index = {0}#

The first pattern not proven faithful (0 for one pattern).

std::string witness#

Divergent only: an input on which match() is shorter than the longest match. Bytes, not necessarily valid UTF-8.

enum class real::dfa_fidelity_outcome : std::uint8_t#

The three answers real::dfa_faithful can give.

Values:

enumerator faithful#

match() equals the longest match on every input: the DFA reproduces it.

enumerator divergent#

Some input separates them; dfa_fidelity::witness is one.

enumerator undecided#

The search hit its state budget. Treat as not faithful; never as faithful.

constexpr std::size_t real::dfa_default_state_budget = {65536}#

The default search budget of real::dfa_faithful, in product states: the default cap a dfa’s own construction runs under. A build that lowers that cap (REAL_MAX_DFA_STATES) keeps this budget; its construction then refuses, with real::dfa_error, what the search accepts.

Fidelity#

A DFA takes the longest match; regex::match() takes the match its priority order prefers. For many patterns the two coincide, for others they do not, and the difference is not visible in the syntax: a|ab on "ab" matches one byte where the DFA takes two, and so does the greedy, longer-branch-first (?:ab|a)(?:bc)? on "abc" – while the lazy x*?y agrees on every input. A caller that needs the DFA to reproduce each rule’s match() (a lexer falling back to per-rule matching, say) asks dfa_faithful. It decides the question exactly for each pattern and returns one of three answers: faithful, divergent with an input that separates the two, or undecided when its state budget runs out – which must be read as not faithful. Over a set, all-faithful is sufficient for the DFA’s munch to equal the per-rule one, not necessary: a divergent rule that a higher-priority rule always outlasts is still refused.

Complexity#

Matching is guaranteed linear – one table transition per input byte, never backtracking (ReDoS-safe). That bounds one munch by the bytes it reads, not a whole tokenization: a munch walks until the automaton dies, so a*b beside a over "aaa…" rereads the rest of the subject from every position, n(n+1)/2 transitions in all. match(subject, offset, memo) with a dfa_munch_memo for the subject answers the same and remembers every state a walk proved leads to no accept, so tokenizing costs O(states × length) – 5n transitions on that input, the replays that mark the dead pairs included, and one bit per remembered state per byte of memory (Reps, Maximal-munch tokenization in linear time, 1998). A memo holds and consults nothing until a walk runs more than dfa_munch_memo::short_stretch (32) bytes past its last accept, so a tokenization whose walks die near their tokens pays neither the memory nor the lookups. The price is capture-freedom: the result names the winning rule and its length, nothing inside it. Use basic_regex when you need groups, or regex_set when you need which-matched without the DFA restrictions. Numbers live in Performance.

Raises#

Construction audits every pattern for DFA-ability and raises dfa_error rather than silently mis-recognizing. A pattern is rejected when it holds a zero-width assertion other than a leading \A/^ ($, \b, multiline anchors), a lookaround, a possessive quantifier / atomic group, a code-point class whose UTF-8 expansion is too large (text-mode \w, or a class repeated many times – narrower ones such as \d, \p{Greek} or [àé] build), or when the automaton outgrows its state cap. dfa_faithful raises the same error for the same patterns.

Example#

Compiled and run by the example-check gate on every push:

  // A tiny lexer: three rules, longest match wins, a tie goes to the lowest index.
  // A rule the DFA cannot represent (a `$`, a lookaround, text-mode \w) raises
  // real::dfa_error at construction.
  const std::array<real::regex, 3> rules {
      real::regex {R"([0-9]+)"}, real::regex {R"([A-Za-z0-9]+)"}, real::regex {R"( +)"}};
  const real::dfa lex {rules};
  // The DFA takes each rule's LONGEST match. Whether that is also what each
  // rule's match() returns is decided, not assumed -- `a|ab` would say no:
  if (real::dfa_faithful(rules).outcome != real::dfa_fidelity_outcome::faithful) {
    return 1;
  }

  std::string_view rest {"if x1 42"};
  while (const auto tok = lex.match(rest)) {
    std::cout << tok->rule_index << ":" << rest.substr(0, tok->length) << "\n";
    rest.remove_prefix(tok->length);
  }
  // 1:if · 2:" " · 1:x1 · 2:" " · 0:42 -- "42" matches [0-9]+ and [A-Za-z0-9]+
  // at equal length; the tie goes to [0-9]+, the lower index.

See also#

  • The capture-full engine, the usual choice: basic_regex.

  • Which-matched over a shared scan, without the DFA opt-in: regex_set.

  • The measured trade-off: Performance.