onepass.hpp

Go to the documentation of this file.

 
#ifndef REAL_ONEPASS_HPP
#define REAL_ONEPASS_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 <bit>
#include <mutex>
#include <optional>
#include <cstddef>
#include <cstdint>
#include <string>
#include <string_view>
#include <vector>
 
#include "real/engine/assert_eval.hpp"
#include "real/automata/lazy_dfa.hpp"
#include "real/core/program.hpp"
 
namespace real::detail {
 
  struct onepass_edge
  {
    std::uint32_t next        {0};     
    std::uint64_t cap_mask    {0};     
    std::uint32_t assert_mask {0};     
    bool          assigned    {false}; 
  };
 
  struct onepass_node
  {
    std::vector<onepass_edge> edge;                      
    bool                      matches           {false}; 
    std::uint64_t             match_cap_mask    {0};     
    std::uint32_t             match_assert_mask {0};     
  };
 
  class onepass
  {
  public:
 
    static constexpr std::uint32_t no_node          {0xFFFFFFFFU};  
    static constexpr std::size_t   max_nodes        {65000};        
    static constexpr std::size_t   max_slots        {10};           
    static constexpr std::size_t   minimize_buckets {4096};         
    static constexpr std::size_t   max_table_bytes  {8U << 20};     
 
    explicit constexpr onepass(const byte_program&  bp,
                               std::size_t          max_bytes = max_table_bytes)
      : max_bytes_ {max_bytes},
        ascii_word_ {!bp.unicode_word} // word-ness mode for \b \B < > in edge conditions (Tier-B)
    {
      if (!bp.eligible) {
        bail("the byte-program is itself ineligible (a lookaround, or a word-ness-flipped assertion)");
        return;
      }
      build(bp);
    }
 
    [[nodiscard]] bool eligible() const
    {
      return eligible_;
    }
 
    [[nodiscard]] const std::string& bail_reason() const
    {
      return bail_reason_;
    }
 
    [[nodiscard]] std::size_t node_count() const
    {
      return nodes_.size();
    }
 
    [[nodiscard]] std::uint16_t num_classes() const
    {
      return alpha_.count;
    }
 
    [[nodiscard]] const std::vector<onepass_node>& nodes() const
    {
      return nodes_;
    }
 
    [[nodiscard]] std::uint8_t class_of(std::uint8_t byte) const
    {
      return alpha_.of[byte];
    }
 
    [[nodiscard]] std::size_t slot_count() const
    {
      return slot_count_;
    }
 
    template <typename OutSlots>
    [[nodiscard]] bool extract(std::string_view text,
                               std::size_t      s,
                               std::size_t      e,
                               OutSlots&        out) const
    {
      if (!eligible_) {
        return false;
      }
      out.assign(slot_count_, npos);
      std::uint32_t node {0}; // node 0 is the start (the closure of pc 0)
      for (std::size_t pos = s; pos < e; ++pos) {
        const std::uint8_t  cls  {alpha_.of[static_cast<std::uint8_t>(text[pos])]};
        const onepass_edge& edge {nodes_[node].edge[cls]};
        if (!edge.assigned) {
          return false;                                             // no outgoing edge for this byte — the span does not match
        }
        if (edge.assert_mask != 0 && !asserts_hold(edge.assert_mask, text, pos)) {
          return false;                                             // an assertion on this edge does not hold here (Tier-B)
        }
        for (std::uint64_t m = edge.cap_mask; m != 0; m &= m - 1) {
          out[static_cast<std::size_t>(std::countr_zero(m))] = pos; // saves crossed before this byte take pos
        }
        node = edge.next;
      }
      if (!nodes_[node].matches) {
        return false;                                           // reached e but not at an accept
      }
      if (nodes_[node].match_assert_mask != 0 && !asserts_hold(nodes_[node].match_assert_mask, text, e)) {
        return false;                                           // an end assertion ($, \b, \Z…) does not hold at e
      }
      for (std::uint64_t m = nodes_[node].match_cap_mask; m != 0; m &= m - 1) {
        out[static_cast<std::size_t>(std::countr_zero(m))] = e; // saves crossed to the match take e
      }
      return true;
    }
 
    [[nodiscard]] bool asserts_hold(std::uint32_t    mask,
                                    std::string_view text,
                                    std::size_t      pos) const
    {
      for (std::uint32_t m = mask; m != 0; m &= m - 1) {
        const auto kind {static_cast<assert_kind>(std::countr_zero(m))};
        if (!assertion_holds(kind, text, pos, ascii_word_)) {
          return false;
        }
      }
      return true;
    }
 
  private:
 
    constexpr void bail(const char*  reason,
                        std::int32_t node  = -1,
                        std::int32_t klass = -1,
                        std::int32_t pc    = -1)
    {
      eligible_    = false;
      bail_reason_ = reason;
      bail_node_   = node;
      bail_class_  = klass;
      bail_pc_     = pc;
    }
 
    constexpr std::uint32_t node_of(std::int32_t               pc,
                                    std::vector<std::int32_t>& queue)
    {
      std::uint32_t& id {pc_to_node_[static_cast<std::size_t>(pc)]};
      if (id == no_node) {
        id = static_cast<std::uint32_t>(nodes_.size());
        onepass_node fresh;
        fresh.edge.assign(alpha_.count, onepass_edge {});
        nodes_.push_back(std::move(fresh));
        queue.push_back(pc);
      }
      return id;
    }
 
    constexpr void build(const byte_program& bp)
    {
      code_    = bp.code;
      classes_ = bp.classes;
      alpha_   = compute_lazy_alphabet(bp.code, bp.classes);
 
      // For each interned char-class, the byte-classes it consumes — so a `klass` instruction writes only
      // those edges instead of scanning the whole alphabet. Computed once here (O(classes x 256)) rather
      // than per instruction (which was O(nodes x classes) and dominated a Unicode \w build).
      class_cover_.assign(classes_.size(), {});
      for (std::size_t i = 0; i < classes_.size(); ++i) {
        std::vector<std::uint16_t>& cover {class_cover_[i]};
        for (unsigned b = 0; b < 256U; ++b) {
          if (classes_[i].test(static_cast<std::uint8_t>(b))) {
            cover.push_back(alpha_.of[b]);
          }
        }
        std::ranges::sort(cover);
        cover.erase(std::ranges::unique(cover).begin(), cover.end());
      }
 
      std::size_t max_slot {0};
      for (const instr& in : bp.code) {
        if (in.op == opcode::save) {
          max_slot = std::max(max_slot, static_cast<std::size_t>(in.arg16));
        }
      }
      slot_count_ = max_slot + 1;
      if (slot_count_ > max_slots) {
        bail("too many capture slots: the general Pike VM keeps these", static_cast<std::int32_t>(slot_count_));
        return;
      }
 
      pc_to_node_.assign(bp.code.size(), no_node);
      std::vector<std::int32_t> queue;
      node_of(0, queue); // the start node
      while (!queue.empty() && eligible_) {
        const std::int32_t pc {queue.back()};
        queue.pop_back();
        std::vector<char> on_path(bp.code.size(), 0);
        build_edges(pc, 0, 0, on_path, pc_to_node_[static_cast<std::size_t>(pc)], queue);
        if (nodes_.size() > max_nodes) {
          bail("node cap exceeded", static_cast<std::int32_t>(nodes_.size()));
          return;
        }
      }
      if (!eligible_) {
        return;
      }
      minimize(); // (i) collapse equivalent nodes (the byte-program's trie sharing, lost in the flood, recovered)
      // (ii) memory cap: even minimized, a pathological table declines to the Pike VM rather than bloat the regex.
      std::size_t bytes {0};
      for (const onepass_node& nd : nodes_) {
        bytes += nd.edge.capacity() * sizeof(onepass_edge);
      }
      if (bytes > max_bytes_) {
        bail("one-pass table too large after minimization (MB)", static_cast<std::int32_t>(bytes >> 20));
      }
    }
 
    constexpr void minimize()
    {
      const std::size_t          n       {nodes_.size()};
      std::vector<std::uint32_t> cls(n, 0);
      std::uint32_t              classes {0};
      while (true) {
        std::vector<std::vector<std::uint64_t>> sigs(n);
        for (std::size_t i = 0; i < n; ++i) {
          std::vector<std::uint64_t>& s {sigs[i]};
          s.push_back(cls[i]);
          s.push_back(nodes_[i].matches ? 1U : 0U);
          s.push_back(nodes_[i].match_cap_mask);
          s.push_back(nodes_[i].match_assert_mask);
          for (const onepass_edge& e : nodes_[i].edge) {
            s.push_back(e.assigned ? static_cast<std::uint64_t>(cls[e.next]) + 1U : 0U);
            s.push_back(e.cap_mask);
            s.push_back(e.assert_mask);
          }
        }
        std::vector<std::uint32_t>              next_cls(n, 0);
        std::vector<std::vector<std::uint32_t>> buckets(minimize_buckets);
        std::uint32_t                           next {0};
        for (std::size_t i = 0; i < n; ++i) {
          std::vector<std::uint32_t>& bucket {buckets[sig_hash(sigs[i]) % minimize_buckets]};
          std::uint32_t               id     {no_node};
          for (const std::uint32_t j : bucket) {
            if (sigs[j] == sigs[i]) {
              id = next_cls[j];
              break;
            }
          }
          if (id == no_node) {
            next_cls[i] = next++;
            bucket.push_back(static_cast<std::uint32_t>(i));
          }
          else {
            next_cls[i] = id;
          }
        }
        cls = std::move(next_cls);
        if (next == classes) {
          break; // fixpoint: the partition stopped refining
        }
        classes = next;
      }
 
      // Rebuild with one node per class, the start (old node 0) renumbered to node 0.
      std::vector<std::int32_t> rep(classes, -1);
      for (std::size_t i = 0; i < n; ++i) {
        if (rep[cls[i]] < 0) {
          rep[cls[i]] = static_cast<std::int32_t>(i);
        }
      }
      std::vector<std::uint32_t> class_id(classes, no_node);
      class_id[cls[0]] = 0;
      std::uint32_t assigned {1};
      for (std::uint32_t c = 0; c < classes; ++c) {
        if (class_id[c] == no_node) {
          class_id[c] = assigned++;
        }
      }
      std::vector<onepass_node> merged(classes);
      for (std::uint32_t c = 0; c < classes; ++c) {
        const onepass_node& r  {nodes_[static_cast<std::size_t>(rep[c])]};
        onepass_node&       nn {merged[class_id[c]]};
        nn.matches           = r.matches;
        nn.match_cap_mask    = r.match_cap_mask;
        nn.match_assert_mask = r.match_assert_mask;
        nn.edge.assign(alpha_.count, onepass_edge {});
        for (std::uint16_t x = 0; x < alpha_.count; ++x) {
          if (r.edge[x].assigned) {
            nn.edge[x] = onepass_edge {.next        = class_id[cls[r.edge[x].next]],
                                       .cap_mask    = r.edge[x].cap_mask,
                                       .assert_mask = r.edge[x].assert_mask,
                                       .assigned    = true};
          }
        }
      }
      nodes_ = std::move(merged);
    }
 
    static constexpr std::size_t sig_hash(const std::vector<std::uint64_t>& v)
    {
      std::uint64_t h {1469598103934665603ULL};
      for (const std::uint64_t x : v) {
        h = (h ^ x) * 1099511628211ULL;
      }
      return static_cast<std::size_t>(h);
    }
 
    constexpr void build_edges(std::int32_t               pc,
                               std::uint64_t              cap_mask,
                               std::uint32_t              assert_mask,
                               std::vector<char>&         on_path,
                               std::uint32_t              node_id,
                               std::vector<std::int32_t>& queue)
    {
      if (!eligible_) {
        return;
      }
      if (on_path[static_cast<std::size_t>(pc)] != 0) {
        bail("epsilon cycle (a nullable loop): not one-pass", -1, -1, pc);
        return;
      }
      on_path[static_cast<std::size_t>(pc)] = 1;
      const instr& in {code_[static_cast<std::size_t>(pc)]};
      switch (in.op) {
        case opcode::byte:
        case opcode::klass: {
            const std::uint32_t next {node_of(pc + 1, queue)};
            onepass_node&       node {nodes_[node_id]};
            // Only the byte-classes this instruction actually consumes (one for `byte`, a precomputed few
            // for `klass`) — never a scan over the whole alphabet, which made the build O(nodes x classes)
            // and dominated a Unicode \w find_iter.
            const auto write_edge {[&](std::uint16_t cls) {
                                     onepass_edge& slot {node.edge[cls]};
                                     if (slot.assigned
                                         && (slot.next != next || slot.cap_mask != cap_mask
                                             || slot.assert_mask != assert_mask)) {
                                       bail("byte-class conflict: not one-pass", static_cast<std::int32_t>(node_id),
                                            cls, pc);
                                       return false;
                                     }
                                     slot = onepass_edge {.next        = next,
                                                          .cap_mask    = cap_mask,
                                                          .assert_mask = assert_mask,
                                                          .assigned    = true};
                                     return true;
                                   }};
            if (in.op == opcode::byte) {
              if (!write_edge(alpha_.of[static_cast<std::uint8_t>(in.arg8)])) {
                return;
              }
            }
            else {
              for (const std::uint16_t cls : class_cover_[in.arg16]) {
                if (!write_edge(cls)) {
                  return;
                }
              }
            }
            break; // a consuming instruction ends this epsilon path
          }
        case opcode::match: {
            onepass_node& node {nodes_[node_id]};
            if (node.matches && (node.match_cap_mask != cap_mask || node.match_assert_mask != assert_mask)) {
              bail("second distinct match: not one-pass", static_cast<std::int32_t>(node_id));
              return;
            }
            node.matches           = true;
            node.match_cap_mask    = cap_mask;
            node.match_assert_mask = assert_mask;
            break;
          }
        case opcode::split:
          build_edges(in.primary_target, cap_mask, assert_mask, on_path, node_id, queue);
          build_edges(in.secondary_target, cap_mask, assert_mask, on_path, node_id, queue);
          break;
        case opcode::jump:
          build_edges(in.primary_target, cap_mask, assert_mask, on_path, node_id, queue);
          break;
        case opcode::save:
          build_edges(pc + 1, cap_mask | (std::uint64_t {1} << in.arg16), assert_mask, on_path, node_id, queue);
          break;
        case opcode::assert_position:
          // Tier-B: the assertion becomes a condition on whatever edge (or match) this epsilon path reaches.
          // The build_byte_program Tier-B pass already rejected a word-ness-flipped assert, so arg16 is 0.
          build_edges(pc + 1, cap_mask, assert_mask | (std::uint32_t {1} << in.arg8), on_path, node_id, queue);
          break;
        default:
          bail("unexpected op in byte-program (lookaround/klass_cp should be absent)");
          return;
      }
      on_path[static_cast<std::size_t>(pc)] = 0; // backtrack: only a cycle bails, a diamond is fine
    }
 
    std::span<const instr>                  code_;
    std::span<const char_class>             classes_;
    lazy_byte_alphabet                      alpha_;
    std::vector<std::vector<std::uint16_t>> class_cover_; 
    std::vector<std::uint32_t>              pc_to_node_;  
    std::vector<onepass_node>               nodes_;
    std::size_t                             slot_count_ {0};
    std::size_t                             max_bytes_  {max_table_bytes};
    bool                                    ascii_word_ {true};
    std::int32_t                            bail_node_  {-1};
    std::int32_t                            bail_class_ {-1};
    std::int32_t                            bail_pc_    {-1};
    bool                                    eligible_   {true};
    std::string                             bail_reason_;
  };
 
  struct regex_immutables
  {
    byte_program           byte_prog;          
    lazy_byte_alphabet     alphabet;           
    std::optional<onepass> op_table;           
    byte_program           il_prefix_prog;     
    std::size_t            il_min_haystack {}; 
    std::once_flag         once;               
 
    // A copied regex is an independent regex: it gets its own fresh, unbuilt cache rather than sharing
    // (std::once_flag is not copyable anyway). Copy/move reset rather than transfer — the built state is a
    // pure runtime accelerator, cheap to rebuild.
    regex_immutables() = default;
    regex_immutables(const regex_immutables& /*other*/) noexcept
    {}
 
    regex_immutables(regex_immutables&& /*other*/) noexcept
    {}
 
    // Assignment keeps this object's own (fresh) cache — it deliberately copies/moves nothing, which is
    // inherently self-assignment-safe (there is no state to guard). NOLINT: the empty body is the contract.
    // NOLINTNEXTLINE(cert-oop54-cpp)
    regex_immutables& operator=(const regex_immutables& /*other*/) noexcept
    {
      return *this;
    }
 
    // NOLINTNEXTLINE(cert-oop54-cpp)
    regex_immutables& operator=(regex_immutables&& /*other*/) noexcept
    {
      return *this;
    }
 
    ~regex_immutables() = default;
  };
} // namespace real::detail
 
#endif // REAL_ONEPASS_HPP