lazy_dfa.hpp

Go to the documentation of this file.

 
#ifndef REAL_LAZY_DFA_HPP
#define REAL_LAZY_DFA_HPP
 
// Internal — do not include directly.
// Users: #include <real/real.hpp> (or the documented opt-ins <real/dfa.hpp>, <real/std/regex.hpp>).
 
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <span>
#include <string>
#include <string_view>
#include <vector>
 
#include "real/core/program.hpp"
#include "real/automata/utf8_ranges.hpp"
 
namespace real::detail {
 
  inline bool& lazy_dfa_route_disabled()
  {
    static bool disabled {false};
    return disabled;
  }
 
  inline bool& inner_literal_route_disabled()
  {
    static bool disabled {false};
    return disabled;
  }
 
  inline bool& inner_literal_guard_disabled()
  {
    static bool disabled {false};
    return disabled;
  }
 
  struct byte_program
  {
    std::vector<instr>      code;
    std::vector<char_class> classes;
    bool                    eligible       {true};  
    bool                    has_assertions {false}; 
    bool                    unicode_word   {false}; 
  };
 
  struct utf8_trie_node
  {
    std::vector<std::pair<utf8_byte_range, std::int32_t>> trans;
  };
 
  struct utf8_trie
  {
    std::vector<utf8_trie_node> nodes;
    std::int32_t                root {-1};
  };
 
  inline utf8_trie build_utf8_trie(const cp_class&             cc,
                                   std::span<const code_range> cp_ranges)
  {
    std::vector<std::vector<utf8_byte_range>> seqs;
    for (int b = 0; b < 0x80;) { // ASCII: each contiguous run of set bits is a one-byte sequence
      if (cc.ascii.test(static_cast<std::uint8_t>(b))) {
        const int lo {b};
        while (b < 0x80 && cc.ascii.test(static_cast<std::uint8_t>(b))) {
          ++b;
        }
        seqs.push_back({utf8_byte_range {.lo = static_cast<std::uint8_t>(lo), .hi = static_cast<std::uint8_t>(b - 1)}});
      }
      else {
        ++b;
      }
    }
    for (std::uint32_t k = 0; k < cc.range_count; ++k) { // non-ASCII: canonical byte-range sequences
      const code_range& r {cp_ranges[cc.range_begin + k]};
      for (const utf8_byte_seq& s : utf8_range_sequences(r.lo, r.hi)) {
        std::vector<utf8_byte_range> seq;
        for (std::size_t j = 0; j < s.length; ++j) {
          seq.push_back(s.parts[j]);
        }
        seqs.push_back(std::move(seq));
      }
    }
 
    utf8_trie trie;
    if (seqs.empty()) {
      return trie;
    }
    struct builder
    {
      std::vector<utf8_trie_node>&            nodes;
      std::vector<std::vector<std::int32_t>>& memo; // hash-cons index: FNV(trans) bucket -> node ids. The
                                                    // engine headers avoid std::hash / std::unordered_map,
                                                    // whose out-of-line libc++ symbols (e.g. __hash_memory)
                                                    // drift across toolchains; an in-house FNV over the
                                                    // transitions hash-conses with no string key per node.
 
      static constexpr std::uint64_t hash_trans(const std::vector<std::pair<utf8_byte_range, std::int32_t>>& trans)
      {
        std::uint64_t h {1469598103934665603ULL};
        for (const std::pair<utf8_byte_range, std::int32_t>& t : trans) {
          h = (h ^ t.first.lo) * 1099511628211ULL;
          h = (h ^ t.first.hi) * 1099511628211ULL;
          h = (h ^ static_cast<std::uint32_t>(t.second)) * 1099511628211ULL;
        }
        return h;
      }
 
      static bool trans_equal(const std::vector<std::pair<utf8_byte_range, std::int32_t>>& a,
                              const std::vector<std::pair<utf8_byte_range, std::int32_t>>& b)
      {
        if (a.size() != b.size()) {
          return false;
        }
        for (std::size_t i = 0; i < a.size(); ++i) {
          if (a[i].first.lo != b[i].first.lo || a[i].first.hi != b[i].first.hi || a[i].second != b[i].second) {
            return false;
          }
        }
        return true;
      }
 
      std::int32_t build(const std::vector<std::vector<utf8_byte_range>>& in) // all non-empty sequences
      {
        std::vector<int> bounds;
        for (const std::vector<utf8_byte_range>& s : in) {
          bounds.push_back(s[0].lo);
          bounds.push_back(s[0].hi + 1);
        }
        std::sort(bounds.begin(), bounds.end());
        bounds.erase(std::unique(bounds.begin(), bounds.end()), bounds.end());
 
        utf8_trie_node node;
        for (std::size_t i = 0; i + 1 < bounds.size(); ++i) {
          const int                                 lo        {bounds[i]};
          const int                                 hi        {bounds[i + 1] - 1};
          std::vector<std::vector<utf8_byte_range>> tails;
          bool                                      all_empty {true};
          for (const std::vector<utf8_byte_range>& s : in) {
            if (s[0].lo <= lo && hi <= s[0].hi) { // this disjoint interval sits inside sequence s's first range
              std::vector<utf8_byte_range> tail(s.begin() + 1, s.end());
              all_empty = all_empty && tail.empty();
              tails.push_back(std::move(tail));
            }
          }
          if (tails.empty()) {
            continue;
          }
          std::int32_t child {-1};
          if (!all_empty) { // UTF-8 is prefix-free, so within one interval the tails share a length
            std::vector<std::vector<utf8_byte_range>> nonempty;
            for (std::vector<utf8_byte_range>& t : tails) {
              if (!t.empty()) {
                nonempty.push_back(std::move(t));
              }
            }
            child = build(nonempty);
          }
          node.trans.emplace_back(utf8_byte_range {.lo = static_cast<std::uint8_t>(lo), .hi = static_cast<std::uint8_t>(hi)}, child);
        }
 
        std::vector<std::int32_t>& bucket {memo[hash_trans(node.trans) % memo.size()]};
        for (const std::int32_t existing : bucket) {
          if (trans_equal(nodes[static_cast<std::size_t>(existing)].trans, node.trans)) {
            return existing; // an identical suffix sub-trie already exists (Daciuk sharing)
          }
        }
        const auto id {static_cast<std::int32_t>(nodes.size())};
        nodes.push_back(std::move(node));
        bucket.push_back(id);
        return id;
      }
    };
    constexpr std::size_t                  trie_memo_buckets {1024}; // chained buckets, sized for the bounded trie
    std::vector<std::vector<std::int32_t>> memo(trie_memo_buckets);
    builder                                b                 {trie.nodes, memo};
    trie.root = b.build(seqs);
    return trie;
  }
 
  inline std::size_t utf8_trie_emit_size(const utf8_trie& trie)
  {
    if (trie.root < 0) {
      return 1;
    }
    std::size_t n {0};
    for (const utf8_trie_node& node : trie.nodes) {
      n += (3 * node.trans.size()) - 1;
    }
    return n;
  }
 
  inline void emit_utf8_trie(byte_program&    bp,
                             const utf8_trie& trie,
                             std::int32_t     after)
  {
    if (trie.root < 0) {
      bp.code.push_back({.op = opcode::klass, .arg16 = static_cast<std::uint16_t>(bp.classes.size())});
      bp.classes.emplace_back(); // matches no byte: the run dies (an empty class matches nothing)
      return;
    }
    const auto                 base  {static_cast<std::int32_t>(bp.code.size())};
    std::vector<std::int32_t>  order {trie.root}; // root first, so the entry pc is `base`
    for (std::int32_t i = 0; i < static_cast<std::int32_t>(trie.nodes.size()); ++i) {
      if (i != trie.root) {
        order.push_back(i);
      }
    }
    std::vector<std::int32_t> node_pc(trie.nodes.size(), 0);
    std::int32_t              off {base};
    for (const std::int32_t id : order) {
      node_pc[static_cast<std::size_t>(id)] = off;
      off                                  += (3 * static_cast<std::int32_t>(trie.nodes[static_cast<std::size_t>(id)].trans.size())) - 1;
    }
    for (const std::int32_t id : order) {
      const utf8_trie_node& node {trie.nodes[static_cast<std::size_t>(id)]};
      const auto            k    {static_cast<std::int32_t>(node.trans.size())};
      for (std::int32_t j = 0; j < k; ++j) {
        const auto&        edge   {node.trans[static_cast<std::size_t>(j)]};
        const std::int32_t target {edge.second < 0 ? after : node_pc[static_cast<std::size_t>(edge.second)]};
        const auto         here   {static_cast<std::int32_t>(bp.code.size())};
        if (j + 1 < k) {
          bp.code.push_back({.op = opcode::split, .primary_target = here + 1, .secondary_target = here + 3});
        }
        char_class cc;
        cc.set_range(edge.first.lo, edge.first.hi);
        bp.code.push_back({.op = opcode::klass, .arg16 = static_cast<std::uint16_t>(bp.classes.size())});
        bp.classes.push_back(cc);
        bp.code.push_back({.op = opcode::jump, .primary_target = target});
      }
    }
  }
 
  inline byte_program build_byte_program(const program_view& prog,
                                         bool                keep_assertions = false)
  {
    byte_program bp;
    bp.unicode_word = prog.unicode_word;
    for (const instr& in : prog.code) {
      if (in.op == opcode::assert_lookaround) {
        bp.eligible = false; // no byte automaton can carry a bounded lookaround (Tier-B stops at assertions)
        return bp;
      }
      if (in.op == opcode::assert_position) {
        if (!keep_assertions || in.arg16 != 0) {
          bp.eligible = false; // Tier-A declines any assertion; Tier-B declines a word-ness-flipped one (scoped (?a:))
          return bp;
        }
        bp.has_assertions = true; // Tier-B: kept, to become an edge condition in the one-pass table
      }
    }
    bp.classes.assign(prog.classes.begin(), prog.classes.end()); // original classes keep their indices
 
    const std::size_t         n {prog.code.size()};
    std::vector<std::int32_t> map(n + 1, 0);                     // old pc -> new pc (n = the one-past end)
    std::vector<utf8_trie>    tries(n);                          // the trie for each klass_cp pc (built once, reused when emitting)
    std::size_t               cur {0};
    for (std::size_t pc = 0; pc < n; ++pc) {
      map[pc] = static_cast<std::int32_t>(cur);
      if (prog.code[pc].op == opcode::klass_cp) {
        tries[pc]   = build_utf8_trie(prog.cp_classes[prog.code[pc].arg16], prog.cp_ranges);
        cur        += utf8_trie_emit_size(tries[pc]);
        map[pc + 1] = map[pc + 2] = map[pc + 3] = static_cast<std::int32_t>(cur); // continuation slots absorbed
        pc         += 3;                                                          // skip the construct's tail
      }
      else {
        ++cur;
      }
    }
    map[n] = static_cast<std::int32_t>(cur);
 
    const auto remap {[&](std::int32_t t) {
                        return (t >= 0 && static_cast<std::size_t>(t) <= n) ? map[static_cast<std::size_t>(t)] : t;
                      }};
    for (std::size_t pc = 0; pc < n; ++pc) {
      const instr& in {prog.code[pc]};
      if (in.op == opcode::klass_cp) {
        emit_utf8_trie(bp, tries[pc], map[pc + 4]);
        pc += 3;
      }
      else {
        instr out {in};
        out.primary_target   = remap(in.primary_target);
        out.secondary_target = remap(in.secondary_target);
        bp.code.push_back(out);
      }
    }
    return bp;
  }
 
  struct lazy_byte_alphabet
  {
    std::array<std::uint8_t, 256> of    {};    
    std::uint16_t                 count {0};   
  };
 
  inline constexpr lazy_byte_alphabet compute_lazy_alphabet(std::span<const instr>      code,
                                                            std::span<const char_class> classes)
  {
    std::vector<char_class>    class_preds;
    std::vector<std::uint16_t> literal_preds;
    const auto                 push_unique {[](auto& vec, const auto& value) {
                                              for (const auto& existing : vec) {
                                                if (existing == value) {
                                                  return;
                                                }
                                              }
                                              vec.push_back(value);
                                            }};
    for (const instr& in : code) {
      if (in.op == opcode::klass && in.arg16 < classes.size()) {
        push_unique(class_preds, classes[in.arg16]);
      }
      else if (in.op == opcode::byte) {
        push_unique(literal_preds, static_cast<std::uint16_t>(in.arg8));
      }
    }
    const auto sig_equal {[&](unsigned a, unsigned b) {
                            for (const char_class& cc : class_preds) {
                              if (cc.test(static_cast<std::uint8_t>(a)) != cc.test(static_cast<std::uint8_t>(b))) {
                                return false;
                              }
                            }
                            for (const std::uint16_t lit : literal_preds) {
                              if ((a == lit) != (b == lit)) {
                                return false;
                              }
                            }
                            return true;
                          }};
    lazy_byte_alphabet            alpha;
    std::array<std::uint8_t, 256> rep {};
    for (unsigned b = 0; b < 256U; ++b) {
      bool assigned {false};
      for (std::uint16_t c = 0; c < alpha.count; ++c) {
        if (sig_equal(b, rep[c])) {
          alpha.of[b] = static_cast<std::uint8_t>(c);
          assigned    = true;
          break;
        }
      }
      if (!assigned) {
        rep[alpha.count] = static_cast<std::uint8_t>(b);
        alpha.of[b]      = static_cast<std::uint8_t>(alpha.count);
        ++alpha.count;
      }
    }
    return alpha;
  }
 
  struct pc_set_cache
  {
    static constexpr std::size_t   bucket_count {2048};
    static constexpr std::uint32_t not_found    {0xFFFFFFFFU};
 
    std::vector<std::vector<std::uint32_t>> buckets;
 
    constexpr pc_set_cache()
      : buckets(bucket_count)
    {}
 
    static constexpr std::size_t hash(const std::vector<std::int32_t>& v)
    {
      // FNV-1a computed in a fixed 64-bit accumulator, truncated to size_t on return: the 64-bit
      // offset-basis brace-initialised straight into size_t narrows (an error) where size_t is 32-bit
      // (win32). Truncating a full FNV-64 keeps a well-distributed hash without width-specific constants.
      std::uint64_t h {1469598103934665603ULL};
      for (const std::int32_t x : v) {
        h = (h ^ static_cast<std::uint64_t>(static_cast<std::uint32_t>(x))) * 1099511628211ULL;
      }
      return static_cast<std::size_t>(h);
    }
 
    [[nodiscard]] constexpr std::uint32_t find(const std::vector<std::int32_t>&               pcs,
                                               const std::vector<std::vector<std::int32_t>>&  state_pcs) const
    {
      for (const std::uint32_t id : buckets[hash(pcs) % bucket_count]) {
        if (state_pcs[id] == pcs) {
          return id;
        }
      }
      return not_found;
    }
 
    constexpr void insert(const std::vector<std::int32_t>& pcs,
                          std::uint32_t                    id)
    {
      buckets[hash(pcs) % bucket_count].push_back(id);
    }
 
    constexpr void clear()
    {
      for (std::vector<std::uint32_t>& b : buckets) {
        b.clear();
      }
    }
  };
 
  class lazy_dfa
  {
  public:
 
    static constexpr std::uint32_t dead_state     {0};           
    static constexpr std::uint32_t no_transition  {0xFFFFFFFFU}; 
    static constexpr std::uint32_t no_match_idx   {0xFFFFFFFFU}; 
    static constexpr std::size_t   state_budget   {4096};        
    static constexpr std::size_t   thrash_flushes {2};           
 
    struct counters
    {
      std::size_t hits         {0};
      std::size_t misses       {0};
      std::size_t flushes      {0};
      std::size_t scan_flushes {0};   
    };
 
    explicit constexpr lazy_dfa(std::span<const instr>      code,
                                std::span<const char_class> classes,
                                std::size_t                 budget       = state_budget,
                                const lazy_byte_alphabet*   shared_alpha = nullptr)
      : code_ {code}, classes_ {classes},
        alpha_ {shared_alpha != nullptr ? *shared_alpha : compute_lazy_alphabet(code, classes)},
        eligible_ {compute_eligibility(code)}, budget_ {budget}
    {
      flush();                 // seeds the dead state (0) and the start state (1)
    }
 
    [[nodiscard]] bool eligible() const
    {
      return eligible_;
    }
 
    [[nodiscard]] std::uint16_t num_classes() const
    {
      return alpha_.count;
    }
 
    [[nodiscard]] std::uint32_t start_state() const
    {
      return start_state_;
    }
 
    void begin_scan()
    {
      stats_.scan_flushes = 0;
      thrashing_          = false;
    }
 
    [[nodiscard]] bool thrashing() const
    {
      return thrashing_;
    }
 
    [[nodiscard]] const counters& stats() const
    {
      return stats_;
    }
 
    [[nodiscard]] std::size_t forward_end(std::string_view text)
    {
      if (!eligible_) {
        return npos;
      }
      begin_scan();
      std::uint32_t state    {start_state_}; // the seed at position 0 (a re-seeding state)
      std::size_t   best_end {npos};
      bool          matched  {false};
      std::size_t   pos      {0};
      while (true) {
        const std::uint32_t midx {state_match_idx_[state]};
        if (midx != no_match_idx) {
          best_end = pos;               // the highest-priority accept lives at index midx; a higher thread may extend it
          matched  = true;
          state    = cut_cached(state); // drop the accept and every lower-priority thread after it (memoized)
          if (state == dead_state) {
            break; // nothing higher-priority survives to extend the match
          }
        }
        if (pos >= text.size() || state == dead_state) {
          break;
        }
        const std::uint8_t byte {static_cast<std::uint8_t>(text[pos])};
        // pre-match transitions re-seed (unanchored search continues); post-match ones do not (leftmost).
        state = matched ? step(state, byte) : step_seeded(state, byte);
        ++pos;
      }
      return best_end;
    }
 
    [[nodiscard]] bool is_match(std::uint32_t state) const
    {
      return state_match_idx_[state] != no_match_idx;
    }
 
    std::uint32_t step(std::uint32_t state,
                       std::uint8_t  byte)
    {
      const std::uint8_t  cls    {alpha_.of[byte]};
      const std::uint32_t cached {trans_[(static_cast<std::size_t>(state) * alpha_.count) + cls]};   // by value: intern() below may realloc
      if (cached != no_transition) {
        ++stats_.hits;
        return cached;
      }
      ++stats_.misses;
      std::vector<std::int32_t> next;
      std::vector<char>         seen(code_.size(), 0);
      for (const std::int32_t pc : state_pcs_[state]) {
        if (consumes(pc, byte)) {
          close_into(pc + consumed_width(pc), next, seen);
        }
      }
      const std::size_t   flushes_before {stats_.flushes};
      const std::uint32_t result         {intern(next)}; // may grow/flush the tables — do not hold a reference
      if (stats_.flushes == flushes_before) {
        trans_[(static_cast<std::size_t>(state) * alpha_.count) + cls] = result;   // no flush: `state` is still valid, so cache the edge
      }
      // On a flush mid-step the caller's `state` id is stale; `result` is a fresh post-flush id, and the
      // caller re-seeds. (An eventual forward pass falls back to Pike once \ref thrashing trips.)
      return result;
    }
 
  private:
 
    std::uint32_t step_seeded(std::uint32_t state,
                              std::uint8_t  byte)
    {
      const std::uint8_t  cls    {alpha_.of[byte]};
      const std::uint32_t cached {trans_seeded_[(static_cast<std::size_t>(state) * alpha_.count) + cls]};
      if (cached != no_transition) {
        ++stats_.hits;
        return cached;
      }
      ++stats_.misses;
      const std::vector<std::int32_t> pcs {state_pcs_[state]}; // copy: intern() below may realloc state_pcs_
      std::vector<std::int32_t>       next;
      std::vector<char>               seen(code_.size(), 0);
      for (const std::int32_t pc : pcs) {
        if (consumes(pc, byte)) {
          close_into(pc + consumed_width(pc), next, seen);
        }
      }
      close_into(0, next, seen); // re-seed at the lowest priority (deduped against the advanced threads)
      const std::size_t   flushes_before {stats_.flushes};
      const std::uint32_t result         {intern(next)};
      if (stats_.flushes == flushes_before) {
        trans_seeded_[(static_cast<std::size_t>(state) * alpha_.count) + cls] = result;
      }
      return result;
    }
 
    std::uint32_t cut(std::uint32_t state,
                      std::uint32_t m)
    {
      // Copy the prefix element-by-element before interning, which may reallocate state_pcs_ (the intern
      // dangling-ref trap). A loop rather than an iterator-range copy — the latter trips a g++ false
      // -Werror=free-nonheap-object here.
      std::vector<std::int32_t> prefix;
      prefix.reserve(m);
      for (std::uint32_t i = 0; i < m; ++i) {
        prefix.push_back(state_pcs_[state][i]);
      }
      return intern(prefix);
    }
 
    std::uint32_t cut_cached(std::uint32_t state)
    {
      const std::uint32_t memo {state_cut_[state]};
      if (memo != no_transition) {
        return memo;
      }
      const std::size_t   flushes_before {stats_.flushes};
      const std::uint32_t result         {cut(state, state_match_idx_[state])}; // intern may flush/realloc
      if (stats_.flushes == flushes_before) {
        state_cut_[state] = result; // no flush: `state` is still valid, memoise the edge
      }
      return result;
    }
 
    static constexpr bool compute_eligibility(std::span<const instr> code)
    {
      for (const instr& in : code) {
        if (in.op == opcode::assert_position || in.op == opcode::assert_lookaround
            || in.op == opcode::klass_cp) {
          return false;   // position assertions / variable-width classes: no forward-DFA representation
        }
      }
      return true;
    }
 
    [[nodiscard]] bool consumes(std::int32_t pc,
                                std::uint8_t byte) const
    {
      const instr& in {code_[static_cast<std::size_t>(pc)]};
      if (in.op == opcode::byte) {
        return static_cast<std::uint8_t>(in.arg8) == byte;
      }
      if (in.op == opcode::klass) {
        return classes_[in.arg16].test(byte);
      }
      return false;   // match / anything else: not a consuming edge
    }
 
    [[nodiscard]] static std::int32_t consumed_width(std::int32_t /*pc*/)
    {
      return 1;
    }
 
    constexpr void close_into(std::int32_t               pc,
                              std::vector<std::int32_t>& out,
                              std::vector<char>&         seen) const
    {
      if (pc < 0 || static_cast<std::size_t>(pc) >= code_.size()) {
        return;
      }
      std::vector<std::int32_t> stack {pc};
      while (!stack.empty()) {
        const std::int32_t cur {stack.back()};
        stack.pop_back();
        if (cur < 0 || static_cast<std::size_t>(cur) >= code_.size() || seen[static_cast<std::size_t>(cur)] != 0) {
          continue;
        }
        seen[static_cast<std::size_t>(cur)] = 1;
        const instr& in {code_[static_cast<std::size_t>(cur)]};
        switch (in.op) {
          case opcode::byte:
          case opcode::klass:
          case opcode::match:
            out.push_back(cur);
            break;
          case opcode::split:
            stack.push_back(in.secondary_target);   // secondary pushed first -> primary explored first
            stack.push_back(in.primary_target);
            break;
          case opcode::jump:
            stack.push_back(in.primary_target);
            break;
          case opcode::save:
            stack.push_back(cur + 1);
            break;
          default:
            break;   // assert / klass_cp / lookaround: only reachable for ineligible programs (not built)
        }
      }
    }
 
    constexpr std::uint32_t intern(const std::vector<std::int32_t>& pcs)
    {
      if (pcs.empty()) {
        return dead_state;
      }
      const std::uint32_t found {cache_.find(pcs, state_pcs_)};
      if (found != pc_set_cache::not_found) {
        return found;
      }
      if (state_pcs_.size() >= budget_) {
        flush();
        return intern_fresh(pcs);   // rebuild from empty; the seeded start remains reachable
      }
      return intern_fresh(pcs);
    }
 
    constexpr std::uint32_t intern_fresh(const std::vector<std::int32_t>& pcs)
    {
      const auto id {static_cast<std::uint32_t>(state_pcs_.size())};
      state_pcs_.push_back(pcs);
      trans_.insert(trans_.end(), alpha_.count, no_transition);
      trans_seeded_.insert(trans_seeded_.end(), alpha_.count, no_transition);
      std::uint32_t match_idx {no_match_idx};
      for (std::size_t i = 0; i < pcs.size(); ++i) {
        if (code_[static_cast<std::size_t>(pcs[i])].op == opcode::match) {
          match_idx = static_cast<std::uint32_t>(i); // the highest-priority accept in this state
          break;
        }
      }
      state_match_idx_.push_back(match_idx);
      state_cut_.push_back(no_transition); // the priority-cut result, memoized lazily on first use
      cache_.insert(pcs, id);
      return id;
    }
 
    constexpr void flush()
    {
      const bool first {state_pcs_.empty()};
      if (!first) {
        ++stats_.flushes;
        ++stats_.scan_flushes;
        if (stats_.scan_flushes >= thrash_flushes) {
          thrashing_ = true;
        }
      }
      state_pcs_.clear();
      trans_.clear();
      trans_seeded_.clear();
      state_match_idx_.clear();
      state_cut_.clear();
      cache_.clear();
      // state 0 = dead (empty, self-looping), state 1 = start (closure of pc 0).
      state_pcs_.emplace_back();
      trans_.insert(trans_.end(), alpha_.count, dead_state);
      trans_seeded_.insert(trans_seeded_.end(), alpha_.count, dead_state);
      state_match_idx_.push_back(no_match_idx);
      state_cut_.push_back(no_transition);
      std::vector<std::int32_t> start;
      std::vector<char>         seen(code_.size(), 0);
      close_into(0, start, seen);
      start_state_ = intern_fresh(start);
    }
 
    std::span<const instr>      code_;
    std::span<const char_class> classes_;
    lazy_byte_alphabet          alpha_;
    bool                        eligible_    {false};
    std::uint32_t               start_state_ {0};
 
    std::vector<std::vector<std::int32_t>>                                    state_pcs_;          
    std::vector<std::uint32_t>                                                trans_;              
    std::vector<std::uint32_t>                                                trans_seeded_;       
    std::vector<std::uint32_t>                                                state_match_idx_;    
    std::vector<std::uint32_t>                                                state_cut_;          
    pc_set_cache                                                              cache_;
 
    std::size_t budget_    {state_budget};
    counters    stats_     {};
    bool        thrashing_ {false};
  };
 
  class reverse_dfa
  {
  public:
 
    static constexpr std::uint32_t dead_state    {0};
    static constexpr std::uint32_t no_transition {0xFFFFFFFFU};
    static constexpr std::size_t   state_budget  {4096};
 
    explicit constexpr reverse_dfa(std::span<const instr>      code,
                                   std::span<const char_class> classes,
                                   std::size_t                 budget       = state_budget,
                                   const lazy_byte_alphabet*   shared_alpha = nullptr)
      : code_ {code}, classes_ {classes},
        alpha_ {shared_alpha != nullptr ? *shared_alpha : compute_lazy_alphabet(code, classes)},
        eligible_ {compute_eligibility(code)}, budget_ {budget}
    {
      // Transpose the program: rev_eps_[x] = the pcs with a forward epsilon edge to x; rev_consume_[x] = the
      // consuming pcs whose successor is x (a byte/klass at pc goes to pc+1).
      rev_eps_.assign(code.size(), {});
      rev_consume_.assign(code.size(), {});
      for (std::int32_t pc = 0; pc < static_cast<std::int32_t>(code.size()); ++pc) {
        const instr& in {code[static_cast<std::size_t>(pc)]};
        switch (in.op) {
          case opcode::byte:
          case opcode::klass:
            rev_consume_[static_cast<std::size_t>(pc) + 1].push_back(pc);
            break;
          case opcode::split:
            rev_eps_[static_cast<std::size_t>(in.primary_target)].push_back(pc);
            rev_eps_[static_cast<std::size_t>(in.secondary_target)].push_back(pc);
            break;
          case opcode::jump:
            rev_eps_[static_cast<std::size_t>(in.primary_target)].push_back(pc);
            break;
          case opcode::save:
            rev_eps_[static_cast<std::size_t>(pc) + 1].push_back(pc);
            break;
          case opcode::match:
            match_pc_ = pc; // the reverse start
            break;
          default:
            break;
        }
      }
      flush();
    }
 
    [[nodiscard]] bool eligible() const
    {
      return eligible_;
    }
 
    [[nodiscard]] std::size_t reverse_start(std::string_view text,
                                            std::size_t      e,
                                            std::size_t      resume)
    {
      std::uint32_t state {start_state_}; // rev-closure of the forward `match`
      std::size_t   best  {npos};
      std::size_t   pos   {e};
      while (true) {
        if (state_has_start_[state] != 0) {
          best = pos; // reached the original start: [pos, e] matches; kLongest keeps the smallest pos
        }
        if (pos <= resume || state == dead_state) {
          break;
        }
        --pos;
        state = step(state, static_cast<std::uint8_t>(text[pos]));
      }
      return best;
    }
 
  private:
 
    constexpr void rev_closure(std::vector<std::int32_t>& set,
                               std::vector<char>&         seen) const
    {
      std::vector<std::int32_t> stack {set};
      while (!stack.empty()) {
        const std::int32_t pc {stack.back()};
        stack.pop_back();
        for (const std::int32_t pred : rev_eps_[static_cast<std::size_t>(pc)]) {
          if (seen[static_cast<std::size_t>(pred)] == 0) {
            seen[static_cast<std::size_t>(pred)] = 1;
            set.push_back(pred);
            stack.push_back(pred);
          }
        }
      }
      std::sort(set.begin(), set.end()); // unordered: a canonical (sorted) key, no priority
    }
 
    std::uint32_t step(std::uint32_t state,
                       std::uint8_t  byte)
    {
      const std::uint8_t  cls    {alpha_.of[byte]};
      const std::uint32_t cached {trans_[(static_cast<std::size_t>(state) * alpha_.count) + cls]};
      if (cached != no_transition) {
        return cached;
      }
      const std::vector<std::int32_t> pcs {state_pcs_[state]}; // copy: intern may realloc
      std::vector<std::int32_t>       next;
      std::vector<char>               seen(code_.size(), 0);
      for (const std::int32_t pc : pcs) {
        for (const std::int32_t pred : rev_consume_[static_cast<std::size_t>(pc)]) {
          if (consumes(pred, byte) && seen[static_cast<std::size_t>(pred)] == 0) {
            seen[static_cast<std::size_t>(pred)] = 1;
            next.push_back(pred);
          }
        }
      }
      rev_closure(next, seen);
      const std::uint32_t result {intern(next)};
      trans_[(static_cast<std::size_t>(state) * alpha_.count) + cls] = result;
      return result;
    }
 
    [[nodiscard]] bool consumes(std::int32_t pc,
                                std::uint8_t byte) const
    {
      const instr& in {code_[static_cast<std::size_t>(pc)]};
      if (in.op == opcode::byte) {
        return static_cast<std::uint8_t>(in.arg8) == byte;
      }
      return in.op == opcode::klass && classes_[in.arg16].test(byte);
    }
 
    static constexpr bool compute_eligibility(std::span<const instr> code)
    {
      for (const instr& in : code) {
        if (in.op == opcode::assert_position || in.op == opcode::assert_lookaround
            || in.op == opcode::klass_cp) {
          return false;
        }
      }
      return true;
    }
 
    constexpr std::uint32_t intern(const std::vector<std::int32_t>& pcs)
    {
      if (pcs.empty()) {
        return dead_state;
      }
      const std::uint32_t found {cache_.find(pcs, state_pcs_)};
      if (found != pc_set_cache::not_found) {
        return found;
      }
      if (state_pcs_.size() >= budget_) {
        flush();
      }
      const auto id {static_cast<std::uint32_t>(state_pcs_.size())};
      state_pcs_.push_back(pcs);
      trans_.insert(trans_.end(), alpha_.count, no_transition);
      bool has_start {false};
      for (const std::int32_t pc : pcs) {
        if (pc == 0) { // pc 0 is the program's save-0 start
          has_start = true;
          break;
        }
      }
      state_has_start_.push_back(has_start ? 1 : 0);
      cache_.insert(pcs, id);
      return id;
    }
 
    constexpr void flush()
    {
      state_pcs_.clear();
      trans_.clear();
      state_has_start_.clear();
      cache_.clear();
      state_pcs_.emplace_back();                          // dead state 0
      trans_.insert(trans_.end(), alpha_.count, dead_state);
      state_has_start_.push_back(0);
      std::vector<std::int32_t> start;
      std::vector<char>         seen(code_.size(), 0);
      if (match_pc_ >= 0) {
        seen[static_cast<std::size_t>(match_pc_)] = 1;
        start.push_back(match_pc_);
        rev_closure(start, seen);
      }
      start_state_ = intern(start);
    }
 
    std::span<const instr>                                                    code_;
    std::span<const char_class>                                               classes_;
    lazy_byte_alphabet                                                        alpha_;
    bool                                                                      eligible_    {false};
    std::int32_t                                                              match_pc_    {-1};
    std::uint32_t                                                             start_state_ {0};
    std::size_t                                                               budget_      {state_budget};
    std::vector<std::vector<std::int32_t>>                                    rev_eps_;         
    std::vector<std::vector<std::int32_t>>                                    rev_consume_;     
    std::vector<std::vector<std::int32_t>>                                    state_pcs_;
    std::vector<std::uint32_t>                                                trans_;           
    std::vector<char>                                                         state_has_start_; 
    pc_set_cache                                                              cache_;
  };
} // namespace real::detail
 
#endif // REAL_LAZY_DFA_HPP