storage.hpp

Go to the documentation of this file.

 
#ifndef REAL_STORAGE_HPP
#define REAL_STORAGE_HPP
 
// Internal — do not include directly.
// Users: #include <real/real.hpp> (or the documented opt-ins <real/dfa.hpp>, <real/std/regex.hpp>).
 
#include "real/version.hpp"
 
#include <array>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <stdexcept>
#include <string>
#include <string_view>
 
#include "real/frontend/ast.hpp"
#include "real/frontend/compiler.hpp"
#include "real/engine/pike.hpp"
#include "real/core/program.hpp"
 
namespace real {
 
  template <std::size_t N>
  struct fixed_string
  {
    char data[N] = {}; 
 
    // NOLINTNEXTLINE(google-explicit-constructor,hicpp-explicit-conversions)
    constexpr fixed_string(const char (&literal)[N])
    {
      for (std::size_t i = 0; i < N; ++i) {
        data[i] = literal[i];
      }
    }
 
    [[nodiscard]] constexpr std::string_view view() const
    {
      return {data, N - 1};
    }
  };
 
  namespace detail {
 
    template <typename T, std::size_t Cap>
    class static_vec
    {
    public:
 
      constexpr void push_back(const T& value)
      {
        if (size_ == Cap) {
          throw std::length_error("static_vec overflow");
        }
        data_[size_] = value;
        ++size_;
      }
 
      constexpr void clear()
      {
        size_ = 0;
      }
 
      constexpr void assign(std::size_t count,
                            const T&    value)
      {
        if (count > Cap) {
          throw std::length_error("static_vec overflow");
        }
        for (std::size_t i = 0; i < count; ++i) {
          data_[i] = value;
        }
        size_ = count;
      }
 
      [[nodiscard]] constexpr std::size_t size() const
      {
        return size_;
      }
 
      [[nodiscard]] constexpr bool empty() const
      {
        return size_ == 0;
      }
 
      [[nodiscard]] constexpr T& operator[](std::size_t i)
      {
        return data_[i];
      }
 
      [[nodiscard]] constexpr const T& operator[](std::size_t i) const
      {
        return data_[i];
      }
 
      [[nodiscard]] constexpr T& back()
      {
        assert(size_ > 0 && "back() on an empty static_vec"); // debug precondition; no-op under NDEBUG
        return data_[size_ - 1];
      }
 
      constexpr void pop_back()
      {
        assert(size_ > 0 && "pop_back() on an empty static_vec");
        --size_;
      }
 
    private:
 
      std::array<T, Cap> data_ {}; 
      std::size_t        size_ {}; 
    };
 
    template <typename T, std::size_t InlineCapacity>
    class small_vec
    {
      static_assert(InlineCapacity > 0, "InlineCapacity must be positive");
      // small_vec runs no element destructors — inline elements in particular are never
      // destroyed (cleanup() only frees the heap block). That is correct only for
      // trivially-destructible types, which is its sole use (POD-like VM state).
      static_assert(std::is_trivially_destructible_v<T>,
                    "small_vec is for trivially-destructible types only");
 
      // size_ and capacity_ are ALWAYS std::size_t — never a type narrowed on
      // InlineCapacity. small_vec spills to the heap and routinely holds far more than
      // its inline capacity (up to code_size in the VM: ~3·code_size epsilon entries, the
      // live thread count of a wide alternation, the 2·(groups+1) capture slots). A
      // uint8_t / uint16_t counter would truncate: at 256 / 65536, static_cast wraps the
      // capacity to 0, reserve() then sees new_cap ≤ capacity_ and no-ops, so the buffer
      // is rewritten in place and back() indexes out of bounds. The inline buffer
      // dominates sizeof, so the wide counter is free.
      std::size_t size_     {};               
      std::size_t capacity_ {InlineCapacity}; 
      bool        is_heap_  {};               
 
      struct inline_block
      {
        T elems[InlineCapacity];
      };
      union Storage
      {
        inline_block inline_buffer; 
        T*           heap_ptr;      
 
        constexpr Storage() noexcept
        {
          if (std::is_constant_evaluated()) {
            std::construct_at(&inline_buffer);
          }
        }
 
        constexpr ~Storage() {} 
 
        // Rule of Five, made explicit. The union holds a possibly non-trivial T, so
        // copy/move would be implicitly deleted anyway; small_vec manages copy, move
        // and element lifetimes itself (is_heap_-aware) and never copies Storage by
        // value. Declaring these deleted is also a safety guard: a defaulted copy
        // would byte-copy the union and inherit the wrong active member (double-free).
        Storage(const Storage&)             = delete;
        Storage& operator=(const Storage&)  = delete;
        Storage(Storage &&)                 = delete;
        Storage& operator=(Storage&&)       = delete;
      } storage_ {};
 
      // Run-time cache of the active storage base (inline buffer or heap block), refreshed on
      // every state change via \ref refresh_data. The hot accessors (operator[], back, push_back)
      // index through it, so they avoid the per-access `is_heap_` branch that the profile showed
      // dominating add_thread. NOT used during constant evaluation: a pointer to a subobject of
      // *this is not a usable constant across copies, so the constexpr path keeps the is_heap_
      // branch (guarded by std::is_constant_evaluated). static_regex uses static_vec, not
      // small_vec, so this never participates in compile-time matching.
      T* data_ {};
 
      constexpr void refresh_data() noexcept
      {
        if (!std::is_constant_evaluated()) {
          data_ = is_heap_ ? storage_.heap_ptr : inline_data();
        }
      }
 
      [[nodiscard]] constexpr T* inline_data() noexcept
      {
        return &storage_.inline_buffer.elems[0];
      }
 
      [[nodiscard]] constexpr const T* inline_data() const noexcept
      {
        return &storage_.inline_buffer.elems[0];
      }
 
      template <bool Move>
      constexpr void transfer_range(const T   * src,
                                    std::size_t count,
                                    T         * dest)
      {
        if constexpr (std::is_trivially_copyable_v<T>) {
          if (!std::is_constant_evaluated()) {
            std::memcpy(dest, src, count * sizeof(T));
            return;
          }
        }
        // Element-wise transfer: the constexpr path, and the run-time path for a
        // non-trivially-copyable T (the VM's POD element types take the memcpy above).
        for (std::size_t i = 0; i < count; ++i) {
          if constexpr (Move) {
            std::construct_at(&dest[i], std::move(src[i]));
          }
          else {
            std::construct_at(&dest[i], src[i]);
          }
        }
      }
 
      template <bool Move>
      constexpr void transfer_inline_from(const small_vec& other)
      {
        const std::size_t inline_count {other.size_ <= InlineCapacity ? other.size_ : InlineCapacity};
        transfer_range<Move>(other.inline_data(), inline_count, inline_data());
      }
 
      constexpr void cleanup() noexcept
      {
        if (std::is_constant_evaluated()) {
          return;
        }
        if (is_heap_) {
          ::operator delete(storage_.heap_ptr);
        }
      }
 
      void extend_capacity()
      {
        const std::size_t current {capacity_};
        const std::size_t new_cap {(current > (std::size_t)-1 / 2) ? (std::size_t)-1 : current * 2};
        reserve(new_cap);
      }
 
    public:
 
      using value_type = T;           
      using size_type_ = std::size_t; 
 
      constexpr small_vec() noexcept
      {
        refresh_data(); // points data_ at the inline buffer (run time)
      }
 
      constexpr ~small_vec()
      {
        if (!std::is_constant_evaluated()) {
          cleanup();
        }
      }
 
      constexpr void push_back(const T& value)
      {
        if (size_ >= capacity_) {
          if (std::is_constant_evaluated()) {
            throw std::bad_alloc {};
          }
          extend_capacity();
        }
        if (std::is_constant_evaluated()) {
          if (is_heap_) {
            std::construct_at(&storage_.heap_ptr[size_], value);
          }
          else {
            inline_data()[size_] = value;
          }
        }
        else {
          // size_ < capacity_ holds here (checked above); the analyzer cannot relate the active
          // block's allocation size to size_. data_ is the active base (branchless).
          // NOLINTNEXTLINE(clang-analyzer-security.ArrayBound)
          std::construct_at(&data_[size_], value);
        }
        ++size_;
      }
 
      constexpr void assign(std::size_t count,
                            const T&    value)
      {
        clear();
        if (count > capacity_) {
          if (std::is_constant_evaluated()) {
            throw std::bad_alloc {};
          }
          reserve(count);
        }
        for (std::size_t i = 0; i < count; ++i) {
          if (std::is_constant_evaluated()) {
            // Compile time: the inline buffer is value-initialized, so assign through it;
            // the heap path is never taken in a constant expression.
            if (is_heap_) {
              std::construct_at(&storage_.heap_ptr[i], value);
            }
            else {
              inline_data()[i] = value;
            }
          }
          else {
            // Run time: the inline buffer is uninitialized (see \ref Storage), so this is the
            // first write — placement-new begins each element's lifetime. data_ is the active
            // base (inline or heap), branchless like push_back.
            std::construct_at(&data_[i], value);
          }
        }
        size_ = count;
      }
 
      [[nodiscard]] constexpr std::size_t size() const noexcept
      {
        return size_;
      }
 
      [[nodiscard]] constexpr bool empty() const noexcept
      {
        return size_ == 0;
      }
 
      [[nodiscard]] constexpr T& operator[](std::size_t i) noexcept
      {
        if (std::is_constant_evaluated()) {
          return is_heap_ ? storage_.heap_ptr[i] : inline_data()[i];
        }
        return data_[i];
      }
 
      [[nodiscard]] constexpr const T& operator[](std::size_t i) const noexcept
      {
        if (std::is_constant_evaluated()) {
          return is_heap_ ? storage_.heap_ptr[i] : inline_data()[i];
        }
        return data_[i];
      }
 
      constexpr void clear() noexcept
      {
        size_ = 0;
      }
 
      [[nodiscard]] constexpr T& back() noexcept
      {
        assert(size_ > 0 && "back() on an empty small_vec"); // debug precondition; no-op under NDEBUG
        if (std::is_constant_evaluated()) {
          return is_heap_ ? storage_.heap_ptr[size_ - 1] : inline_data()[size_ - 1];
        }
        return data_[size_ - 1];
      }
 
      [[nodiscard]] constexpr const T& back() const noexcept
      {
        assert(size_ > 0 && "back() on an empty small_vec");
        if (std::is_constant_evaluated()) {
          return is_heap_ ? storage_.heap_ptr[size_ - 1] : inline_data()[size_ - 1];
        }
        return data_[size_ - 1];
      }
 
      constexpr void pop_back() noexcept
      {
        assert(size_ > 0 && "pop_back() on an empty small_vec");
        --size_;
      }
 
      constexpr void reserve(std::size_t new_capacity)
      {
        if (new_capacity <= capacity_) {
          return;
        }
        if (std::is_constant_evaluated()) {
          throw std::bad_alloc {};
        }
        T      * new_data {static_cast<T*>(::operator new(new_capacity * sizeof(T)))};
        const T* old_data {is_heap_ ? storage_.heap_ptr : inline_data()};
        transfer_range<false>(old_data, size_, new_data);
        if (is_heap_) {
          ::operator delete(storage_.heap_ptr);
        }
        storage_.heap_ptr = new_data;
        capacity_         = new_capacity;
        is_heap_          = true;
        refresh_data(); // run-time path only (constexpr threw above); data_ now points at the heap block
      }
 
      constexpr small_vec(small_vec&& other) noexcept
        : size_(other.size_),
          capacity_(other.capacity_),
          is_heap_(other.is_heap_)
      {
        if (is_heap_) {
          storage_.heap_ptr       = other.storage_.heap_ptr;
          other.storage_.heap_ptr = nullptr;
          other.is_heap_          = false;
          other.size_             = 0;
          other.capacity_         = InlineCapacity;
        }
        else {
          transfer_inline_from<true>(other);
        }
        refresh_data();
        other.refresh_data(); // other is now empty/inline
      }
 
      constexpr small_vec& operator=(small_vec&& other) noexcept
      {
        if (this != &other) {
          cleanup();
          size_     = other.size_;
          capacity_ = other.capacity_;
          is_heap_  = other.is_heap_;
          if (is_heap_) {
            storage_.heap_ptr       = other.storage_.heap_ptr;
            other.storage_.heap_ptr = nullptr;
            other.is_heap_          = false;
            other.size_             = 0;
            other.capacity_         = InlineCapacity;
          }
          else {
            transfer_inline_from<true>(other);
          }
          refresh_data();
          other.refresh_data(); // other is now empty/inline
        }
        return *this;
      }
 
      constexpr small_vec(const small_vec& other)
        : size_(other.size_),
          capacity_(other.capacity_)
      {
        if (other.is_heap_) {
          if (std::is_constant_evaluated()) {
            throw std::bad_alloc {}; // dynamic heap path not for constexpr (static_regex uses static_vec)
          }
          storage_.heap_ptr = static_cast<T*>(::operator new(other.capacity_ * sizeof(T)));
          transfer_range<false>(other.storage_.heap_ptr, other.size_, storage_.heap_ptr);
          is_heap_  = true;
          capacity_ = other.capacity_;
        }
        else {
          transfer_inline_from<false>(other);
        }
        refresh_data();
      }
 
      constexpr small_vec& operator=(const small_vec& other)
      {
        if (this != &other) {
          cleanup();
          size_ = other.size_;
          if (other.is_heap_) {
            storage_.heap_ptr = static_cast<T*>(::operator new(other.capacity_ * sizeof(T)));
            transfer_range<false>(other.storage_.heap_ptr, other.size_, storage_.heap_ptr);
            is_heap_  = true;
            capacity_ = other.capacity_;
          }
          else {
            is_heap_  = false;
            capacity_ = InlineCapacity;
            transfer_inline_from<false>(other);
          }
          refresh_data();
        }
        return *this;
      }
    };
 
    struct dynamic_storage
    {
      static constexpr bool is_compile_time {}; 
      using slot_storage = small_vec<std::size_t, 32>;
      struct state_type : basic_pike_state<
                            basic_thread_list<small_vec<std::int32_t, 64>,
                                              small_vec<std::size_t, 256>,
                                              std::vector<std::uint64_t>>,
                            small_vec<eps_entry, 32>>
      {
        lookaround_scratch         lookaround;              
        capture_pool               pool;                    
        std::optional<lazy_dfa>    fwd_dfa;                 
        std::optional<reverse_dfa> rev_dfa;                 
        const void*                dfa_program   {nullptr}; 
        std::optional<reverse_dfa> il_prefix_rev;           
        const void*                il_prefix_for {nullptr}; 
        const void*                il_text       {nullptr}; 
        bool                       il_abandoned  {false};   
      };
 
      std::string     pattern_text;                  
      dynamic_program program;                       
      flags           effective_flags {flags::none}; 
 
      mutable detail::regex_immutables immut_ {};
 
      static constexpr dynamic_storage compile(std::string_view pattern,
                                               flags            compile_flags)
      {
        const ast   tree      {detail::parse(pattern, compile_flags)};
        const flags effective {compile_flags | tree.inline_flags};
        return {.pattern_text    = std::string(pattern),
                .program         = detail::compile(tree, effective),
                .effective_flags = effective};
      }
 
      [[nodiscard]] constexpr program_view view() const
      {
        program_view pv {program.view()};
        pv.immut = &immut_; // the router builds/uses the per-regex cache through the view
        return pv;
      }
 
      [[nodiscard]] constexpr std::string_view pattern() const
      {
        return pattern_text;
      }
 
      [[nodiscard]] constexpr flags compiled_flags() const
      {
        return effective_flags;
      }
    };
 
    template <fixed_string Pat, flags F = flags::none>
    struct static_storage
    {
      static constexpr bool is_compile_time {true}; 
 
    private:
 
      static constexpr dynamic_program build()
      {
        const ast       tree {detail::parse(Pat.view(), F)};
        dynamic_program prog {detail::compile(tree, F | tree.inline_flags)};
        if (!prog.lookarounds.empty()) {
          // Honest absence: the constexpr sub-VM is a measured follow-up. A clear compile
          // error (this throw, evaluated at compile time) beats a silent miscompile.
          throw regex_error("static_regex does not support lookarounds yet (use real::regex)", 0);
        }
        return prog;
      }
 
      template <typename T, std::size_t N, typename Vec>
      static constexpr std::array<T, N> take(const Vec& source)
      {
        std::array<T, N> result {};
        for (std::size_t i = 0; i < N; ++i) {
          result[i] = source[i];
        }
        return result;
      }
 
    public:
 
      static constexpr flags         effective_flags            {F | detail::parse(Pat.view(), F).inline_flags}; 
      static constexpr pattern_hints hints                      {build().hints};                                 
      static constexpr std::size_t   code_size                  {build().code.size()};                           
      static constexpr std::size_t   class_count                {build().classes.size()};                        
      static constexpr std::size_t   name_count                 {build().names.size()};                          
      static constexpr std::size_t   cp_class_count             {build().cp_classes.size()};                     
      static constexpr std::size_t   cp_range_count             {build().cp_ranges.size()};                      
      static constexpr std::uint16_t slot_count                 {build().slot_count};                            
 
      static constexpr std::array<instr, code_size>        code {take<instr, code_size>(build().code)};          
      static constexpr std::array<char_class, class_count> classes =
        take<char_class, class_count>(build().classes);                                                          
      static constexpr std::array<named_group, name_count> names =
        take<named_group, name_count>(build().names);                                                            
      static constexpr std::array<cp_class, cp_class_count> cp_classes =
        take<cp_class, cp_class_count>(build().cp_classes);                                                      
      static constexpr std::array<code_range, cp_range_count> cp_ranges =
        take<code_range, cp_range_count>(build().cp_ranges);                                                     
 
      using slot_storage = static_vec<std::size_t, slot_count>;
      // OPT D1: worst-case live capture blocks — every reference (a DFS stack frame or a thread in either
      // list) could point to a distinct block; freed blocks recycle through the pool's free list, so the
      // pool never grows past this. The stack is (3*code_size)+4, each list up to code_size threads.
      static constexpr std::size_t max_blocks {(5 * code_size) + 8};
 
      struct state_type : basic_pike_state<
                            basic_thread_list<static_vec<std::int32_t, code_size>,
                                              static_vec<std::size_t, code_size>,
                                              static_vec<std::uint64_t, code_size>>,
                            static_vec<eps_entry, (3 * code_size) + 4>>
      {
        basic_capture_pool<static_vec<std::size_t, max_blocks * slot_count>,
                           static_vec<std::int32_t, max_blocks>,
                           static_vec<std::uint32_t, max_blocks>> pool; 
      };
 
      [[nodiscard]] constexpr program_view view() const
      {
        return {.code              = code,
                .classes           = classes,
                .names             = names,
                .lookarounds       = {}, // static_regex rejects lookarounds at compile (always empty)
                .cp_classes        = cp_classes,
                .cp_ranges         = cp_ranges,
                .prefix_code       = {}, // IL: static storage builds no prefix program (the route is dynamic-only)
                .prefix_classes    = {},
                .prefix_cp_classes = {},
                .prefix_cp_ranges  = {},
                .slot_count        = slot_count,
                .byte_mode         = has_flag(effective_flags, flags::bytes),
                .unicode_word      = !has_flag(effective_flags, flags::bytes) && !has_flag(effective_flags, flags::ascii),
                .hints             = hints};
      }
 
      [[nodiscard]] constexpr std::string_view pattern() const
      {
        return Pat.view();
      }
 
      [[nodiscard]] constexpr flags compiled_flags() const
      {
        return effective_flags;
      }
    };
  } // namespace detail
} // namespace real
 
#endif // REAL_STORAGE_HPP