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 and cheap to copy-share. match is the lexer munch. which_matched is Stage-2 multi-accept (only valid 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).

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 – if any program holds a non-head zero-width assertion, a lookaround, a code-point class, or a possessive/atomic construct.

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 – if any pattern holds a non-head zero-width assertion, a lookaround, a code-point class, or a possessive/atomic construct.

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::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. Returns a bitset of length rule_count in construction order. Early-exits when every pattern has hit. Empty matches are excluded (only states that accepted after consuming a byte contribute, via post-move accept masks).

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 (a pure optimization). Pass false to disable 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.

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

Build mode for real::dfa.

munch — maximal-munch at the cursor (lexer; default, SciLex). which_matched — unanchored multi-accept single-pass (Stage-2 RegexSet fused).

Values:

enumerator munch#

One winner at the start of the subject (existing contract).

enumerator which_matched#

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

class dfa_error : public std::runtime_error#

Thrown when a pattern cannot be represented as a DFA.

Four causes: a zero-width assertion other than a leading \A/^ ($, \b, \B, multiline anchors), a lookaround, a Unicode code-point class (\w/\d/\s in text mode — use byte classes), or a possessive quantifier / atomic group. real::dfa never falls back silently — a violated contract is an error the caller handles (e.g. by keeping that rule on the Pike VM).

Complexity#

Matching is guaranteed linear – one table transition per input byte, never backtracking (ReDoS-safe). 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 Unicode code-point class (\w / \d / \s in text mode – use byte classes like [0-9] instead), or a possessive quantifier / atomic group.

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.
  // DFA rules must be byte-representable -- ASCII classes here (a Unicode \d
  // 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};

  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.