real.hpp

Go to the documentation of this file.

 
#ifndef REAL_REAL_HPP
#define REAL_REAL_HPP
 
#include "real/version.hpp"
 
#include <iterator>
#include <optional>
#include <span>
#include <string>
#include <string_view>
#include <utility>
#include <vector>
 
#include "real/engine/pike.hpp"
#include "real/core/program.hpp"
#include "real/storage.hpp"
#include "real/unicode/utf8.hpp"
 
namespace real {
 
  template <typename SlotStorage>
  class basic_match_result
  {
  public:
 
    constexpr basic_match_result() = default;
 
    constexpr basic_match_result(std::string_view                     text,
                                 SlotStorage                          slots,
                                 bool                                 matched,
                                 std::string_view                     pattern,
                                 std::span<const detail::named_group> names)
      : text_(text),
        slots_(std::move(slots)),
        matched_(matched),
        pattern_(pattern),
        names_(names)
    {}
 
    template <bool Cascade, typename Vm>
    constexpr bool engine_refill(Vm&                                  vm,
                                 std::string_view                     text,
                                 std::size_t                          pos,
                                 detail::run_mode                     mode,
                                 std::size_t                          forbid,
                                 std::string_view                     pattern,
                                 std::span<const detail::named_group> names)
    {
      const bool ok {vm.template run<Cascade>(text, pos, mode, slots_, forbid)};
      text_    = text;
      matched_ = ok;
      pattern_ = pattern;
      names_   = names;
      return ok;
    }
 
    constexpr void bind_context(std::string_view                     text,
                                std::string_view                     pattern,
                                std::span<const detail::named_group> names)
    {
      text_    = text;
      pattern_ = pattern;
      names_   = names;
    }
 
    template <bool Cascade, typename Vm>
    constexpr bool engine_refill_hot(Vm&              vm,
                                     std::string_view text,
                                     std::size_t      pos,
                                     detail::run_mode mode,
                                     std::size_t      forbid,
                                     match_semantics  sem = match_semantics::first)
    {
      matched_ = vm.template run<Cascade>(text, pos, mode, slots_, forbid, sem);
      return matched_;
    }
 
    [[nodiscard]] constexpr bool matched() const
    {
      return matched_;
    }
 
    constexpr explicit operator bool() const {
      return matched_;
    }
 
    [[nodiscard]] constexpr std::size_t size() const
    {
      return slots_.size() / 2;
    }
 
    [[nodiscard]] constexpr std::size_t start(std::size_t group = 0) const
    {
      return matched_ && group < size() ? slots_[2 * group] : npos;
    }
 
    [[nodiscard]] constexpr std::size_t end(std::size_t group = 0) const
    {
      return matched_ && group < size() ? slots_[(2 * group) + 1] : npos;
    }
 
    [[nodiscard]] constexpr std::string_view operator[](std::size_t group) const
    {
      const std::size_t s {start(group)};
      return s == npos ? std::string_view {} : text_.substr(s, end(group) - s);
    }
 
    [[nodiscard]] constexpr std::size_t group_index(std::string_view name) const
    {
      for (const detail::named_group& named_group : names_) {
        const auto begin  {static_cast<std::size_t>(named_group.begin)};
        const auto length {static_cast<std::size_t>(named_group.end - named_group.begin)};
        if (pattern_.substr(begin, length) == name) {
          return static_cast<std::size_t>(named_group.group);
        }
      }
      return npos;
    }
 
    [[nodiscard]] constexpr std::size_t start(std::string_view name) const
    {
      const std::size_t g {group_index(name)};
      return g == npos ? npos : start(g);
    }
 
    [[nodiscard]] constexpr std::size_t end(std::string_view name) const
    {
      const std::size_t g {group_index(name)};
      return g == npos ? npos : end(g);
    }
 
    [[nodiscard]] constexpr std::string_view operator[](std::string_view name) const
    {
      const std::size_t g {group_index(name)};
      return g == npos ? std::string_view {} : (*this)[g];
    }
 
  private:
 
    std::string_view                     text_;       
    SlotStorage                          slots_;      
    bool                                 matched_ {}; 
    std::string_view                     pattern_;    
    std::span<const detail::named_group> names_;      
  };
 
  using match_result = basic_match_result<std::vector<std::size_t>>;
 
  template <typename Storage>
  class basic_match_iterator
  {
  public:
 
    using value_type        = basic_match_result<typename Storage::slot_storage>; 
    using difference_type   = std::ptrdiff_t;                                     
    using reference         = const value_type&;                                  
    using pointer           = const value_type*;                                  
    using iterator_category = std::forward_iterator_tag;                          
 
    constexpr basic_match_iterator() = default;
 
    constexpr basic_match_iterator(detail::program_view prog,
                                   std::string_view     pattern,
                                   std::string_view     text,
                                   std::size_t          start = 0,
                                   match_semantics      sem   = match_semantics::first)
      : prog_(prog),
        pattern_(pattern),
        text_(text),
        pos_(start),
        done_(false),
        // decided ONCE per walk, never per match. Longest forces the non-cascade variant: like every other
        // fast path, the memchr-cascade class-run is guarded to first mode (the PROTO-kLongest lesson), so a
        // longest walk must run the general loop.
        cascade_(sem == match_semantics::first && prog.hints.stop_set_size >= 1),
        sem_(sem)
    {
      current_.bind_context(text_, pattern_, prog_.names); // invariant across the walk — set once, not per match
      advance();
    }
 
    [[nodiscard]] constexpr const value_type& operator*() const
    {
      return current_;
    }
 
    [[nodiscard]] constexpr const value_type* operator->() const
    {
      return &current_;
    }
 
    constexpr basic_match_iterator& operator++()
    {
      advance();
      return *this;
    }
 
    constexpr basic_match_iterator operator++(int)
    {
      basic_match_iterator previous {*this};
      advance();
      return previous;
    }
 
    [[nodiscard]] constexpr bool operator==(const basic_match_iterator& other) const
    {
      return done_ == other.done_ && (done_ || pos_ == other.pos_);
    }
 
  private:
 
    detail::program_view         prog_;                                        
    std::string_view             pattern_;                                     
    std::string_view             text_;                                        
    std::size_t                  pos_                {};                       
    std::size_t                  forbid_empty_until_ {};                       
    bool                         done_               {true};                   
    bool                         cascade_            {};                       
    match_semantics              sem_                {match_semantics::first}; 
    value_type                   current_;                                     
    typename Storage::state_type state_;                                       
 
    constexpr void advance()
    {
      if (done_ || pos_ > text_.size()) {
        done_ = true;
        return;
      }
      detail::pike_vm vm(prog_, state_);
      // Refresh the one held result in place, reusing its slot buffer (no per-match allocation). The
      // Cascade choice is the iterator's compile-time-dispatched cascade_, fixed once at construction, so
      // the common (non-cascade) walk runs the pre-OPT-C hot path unchanged.
      const bool ok {cascade_
                     ? current_.template engine_refill_hot<true>(vm, text_, pos_, detail::run_mode::search,
                                                                 forbid_empty_until_, sem_)
                     : current_.template engine_refill_hot<false>(vm, text_, pos_, detail::run_mode::search,
                                                                  forbid_empty_until_, sem_)};
      if (!ok) {
        done_ = true;
        return;
      }
      const std::size_t start {current_.start(0)};
      const std::size_t end   {current_.end(0)};
      pos_ = end;
      if (end == start) {
        // CPython 3.7+: after an empty match, the next match may start at the
        // same position only if it is non-empty; another empty match there is
        // skipped. Forbid empty matches up to the next character boundary (a
        // codepoint, or one raw byte in binary mode) so the skip stays aligned.
        forbid_empty_until_ = end >= text_.size()
                              ? text_.size() + 1
                              : end + (prog_.byte_mode ? 1 : detail::codepoint_advance(text_, end));
      }
      else {
        forbid_empty_until_ = 0; // non-empty match: no restriction next time
      }
    }
  };
 
  template <typename Storage>
  class basic_match_range
  {
  public:
 
    constexpr basic_match_range(detail::program_view prog,
                                std::string_view     pattern,
                                std::string_view     text,
                                std::size_t          start = 0,
                                match_semantics      sem   = match_semantics::first)
      : prog_(prog),
        pattern_(pattern),
        text_(text),
        start_(start),
        sem_(sem)
    {}
 
    [[nodiscard]] constexpr basic_match_iterator<Storage> begin() const
    {
      return {prog_, pattern_, text_, start_, sem_};
    }
 
    [[nodiscard]] constexpr basic_match_iterator<Storage> end() const
    {
      return {};
    }
 
  private:
 
    detail::program_view prog_;                           
    std::string_view     pattern_;                        
    std::string_view     text_;                           
    std::size_t          start_ {};                       
    match_semantics      sem_   {match_semantics::first}; 
  };
 
  template <typename Storage>
  class basic_regex
  {
  public:
 
    using result_type = basic_match_result<typename Storage::slot_storage>; 
 
    constexpr explicit basic_regex(std::string_view pattern,
                                   flags            compile_flags = flags::none)
    requires(!Storage::is_compile_time)
      : program_(Storage::compile(pattern, compile_flags))
    {}
 
    constexpr basic_regex()
    requires(Storage::is_compile_time)
    = default;
 
    [[nodiscard]] constexpr result_type match(std::string_view text) const
    {
      return run(text, detail::run_mode::prefix);
    }
 
    [[nodiscard]] constexpr result_type fullmatch(std::string_view text) const
    {
      return run(text, detail::run_mode::full);
    }
 
    [[nodiscard]] constexpr result_type search(std::string_view text) const
    {
      return run(text, detail::run_mode::search);
    }
 
    [[nodiscard]] constexpr result_type match(std::string_view text,
                                              std::size_t      pos,
                                              std::size_t      endpos = npos) const
    {
      return run(text, pos, endpos, detail::run_mode::prefix);
    }
 
    [[nodiscard]] constexpr result_type fullmatch(std::string_view text,
                                                  std::size_t      pos,
                                                  std::size_t      endpos = npos) const
    {
      return run(text, pos, endpos, detail::run_mode::full);
    }
 
    [[nodiscard]] constexpr result_type search(std::string_view text,
                                               std::size_t      pos,
                                               std::size_t      endpos = npos) const
    {
      return run(text, pos, endpos, detail::run_mode::search);
    }
 
    [[nodiscard]] constexpr result_type match(const char* text) const
    {
      return match(std::string_view(text));
    }
 
    [[nodiscard]] constexpr result_type fullmatch(const char* text) const
    {
      return fullmatch(std::string_view(text));
    }
 
    [[nodiscard]] constexpr result_type search(const char* text) const
    {
      return search(std::string_view(text));
    }
 
    [[nodiscard]] constexpr basic_match_range<Storage> find_iter(std::string_view text) const&
    {
      return {program_.view(), pattern(), text};
    }
 
    [[nodiscard]] constexpr basic_match_range<Storage> find_iter(const char* text) const&
    {
      return find_iter(std::string_view(text));
    }
 
    [[nodiscard]] constexpr basic_match_range<Storage> find_iter(std::string_view text,
                                                                 std::size_t      pos,
                                                                 std::size_t      endpos = npos) const&
    {
      const std::size_t end {endpos < text.size() ? endpos : text.size()};
      return {program_.view(), pattern(), text.substr(0, end), pos};
    }
 
    [[nodiscard]] constexpr basic_match_range<Storage> find_iter_longest(std::string_view text,
                                                                         std::size_t      pos    = 0,
                                                                         std::size_t      endpos = npos) const&
    {
      const std::size_t end {endpos < text.size() ? endpos : text.size()};
      return {program_.view(), pattern(), text.substr(0, end), pos, match_semantics::longest};
    }
 
    [[nodiscard]] basic_match_range<Storage> find_iter_longest(std::string_view, std::size_t,
                                                               std::size_t) const&& = delete;
 
    [[nodiscard]] basic_match_range<Storage> find_iter(std::string_view text) const&& = delete;
    [[nodiscard]] basic_match_range<Storage> find_iter(const char* text) const&& = delete;
    [[nodiscard]] basic_match_range<Storage> find_iter(std::string_view text, std::size_t,
                                                       std::size_t = npos) const&& = delete;
 
    [[nodiscard]] constexpr std::vector<result_type> find_all(std::string_view text) const&
    {
      std::vector<result_type> result;
      for (const result_type& match : find_iter(text)) {
        result.push_back(match);
      }
      return result;
    }
 
    [[nodiscard]] constexpr std::vector<result_type> find_all(const char* text) const&
    {
      return find_all(std::string_view(text));
    }
 
    [[nodiscard]] std::vector<result_type> find_all(std::string_view text) const&& = delete;
    [[nodiscard]] std::vector<result_type> find_all(const char* text) const&& = delete;
 
    [[nodiscard]] constexpr std::string replace(std::string_view text,
                                                std::string_view replacement,
                                                std::size_t      max_count = 0) const
    {
      std::string result;
      std::size_t last {};
      std::size_t done {};
      for (const result_type& match : find_iter(text)) {
        if (max_count != 0 && done == max_count) {
          break;
        }
        result.append(text.substr(last, match.start() - last));
        expand_replacement(result, match, replacement);
        last = match.end();
        ++done;
      }
      result.append(text.substr(last));
      return result;
    }
 
    [[nodiscard]] constexpr std::vector<std::string_view> split(std::string_view text,
                                                                std::size_t      max_splits = 0) const
    {
      std::vector<std::string_view> result;
      std::size_t                   last {};
      std::size_t                   done {};
      for (const result_type& match : find_iter(text)) {
        if (max_splits != 0 && done == max_splits) {
          break;
        }
        result.push_back(text.substr(last, match.start() - last));
        for (std::size_t group = 1; group < match.size(); ++group) {
          result.push_back(match[group]);
        }
        last = match.end();
        ++done;
      }
      result.push_back(text.substr(last));
      return result;
    }
 
    [[nodiscard]] constexpr std::vector<std::string_view> split(const char* text,
                                                                std::size_t max_splits = 0) const
    {
      return split(std::string_view(text), max_splits);
    }
 
    // Searched text must outlive the result: reject temporary std::string.
    [[nodiscard]] result_type                   match(const std::string&& text) const           = delete;                            
    [[nodiscard]] result_type                   fullmatch(const std::string&& text) const       = delete;                            
    [[nodiscard]] result_type                   search(const std::string&& text) const          = delete;                            
    [[nodiscard]] result_type match(const std::string && text, std::size_t, std::size_t     = npos) const     = delete;              
    [[nodiscard]] result_type fullmatch(const std::string && text, std::size_t, std::size_t = npos) const = delete;                  
    [[nodiscard]] result_type search(const std::string && text, std::size_t, std::size_t    = npos) const    = delete;               
    [[nodiscard]] basic_match_range<Storage>    find_iter(const std::string&& text) const&      = delete;                            
    [[nodiscard]] basic_match_range<Storage>    find_iter(const std::string && text, std::size_t,
                                                          std::size_t                           = npos) const&             = delete; 
    [[nodiscard]] std::vector<result_type>      find_all(const std::string&& text) const&       = delete;                            
    [[nodiscard]] std::vector<std::string_view> split(const std::string&& text,
                                                      std::size_t         max_splits = 0) const = delete;                            
 
    [[nodiscard]] constexpr std::string_view pattern() const
    {
      return program_.pattern();
    }
 
    [[nodiscard]] constexpr flags compile_flags() const
    {
      return program_.compiled_flags();
    }
 
    [[nodiscard]] constexpr std::size_t group_count() const
    {
      return (program_.view().slot_count / 2) - 1;
    }
 
    [[nodiscard]] constexpr detail::program_view raw_program() const
    {
      return program_.view();
    }
 
    [[nodiscard]] constexpr bool has_first_byte_set() const noexcept
    {
      return raw_program().hints.first_bytes_valid;
    }
 
    [[nodiscard]] constexpr std::optional<unsigned char> unique_first_byte() const noexcept
    {
      const int first {raw_program().hints.single_first};
      return first < 0 ? std::nullopt : std::optional<unsigned char>(static_cast<unsigned char>(first));
    }
 
    [[nodiscard]] constexpr bool may_start_with(unsigned char byte) const noexcept
    {
      const detail::program_view view {raw_program()};
      return !view.hints.first_bytes_valid || view.hints.first_bytes.test(byte);
    }
 
    [[nodiscard]] constexpr std::size_t group_index(std::string_view name) const
    {
      for (const detail::named_group& named_group : program_.view().names) {
        if (name_of(named_group) == name) {
          return static_cast<std::size_t>(named_group.group);
        }
      }
      return npos;
    }
 
    [[nodiscard]] constexpr std::vector<std::pair<std::string_view, std::size_t>>
    named_groups() const
    {
      std::vector<std::pair<std::string_view, std::size_t>> result;
      for (const detail::named_group& named_group : program_.view().names) {
        result.emplace_back(name_of(named_group), static_cast<std::size_t>(named_group.group));
      }
      return result;
    }
 
  private:
 
    Storage program_; 
 
    [[nodiscard]] constexpr std::string_view name_of(const detail::named_group& named_group) const
    {
      return pattern().substr(static_cast<std::size_t>(named_group.begin),
                              static_cast<std::size_t>(named_group.end - named_group.begin));
    }
 
    constexpr void expand_replacement(std::string&       out,
                                      const result_type& match,
                                      std::string_view   replacement) const
    {
      std::size_t i {};
      while (i < replacement.size()) {
        const char ch {replacement[i]};
        if (ch != '$') {
          out.push_back(ch);
          ++i;
          continue;
        }
        ++i;
        if (i >= replacement.size()) {
          throw regex_error("dangling $ in replacement", i - 1);
        }
        const char next_ch {replacement[i]};
        if (next_ch == '$') {
          out.push_back('$');
          ++i;
        }
        else if (next_ch == '&') {
          out.append(match[0]);
          ++i;
        }
        else if (next_ch >= '0' && next_ch <= '9') {
          std::size_t group {};
          while (i < replacement.size() && replacement[i] >= '0' &&
                 replacement[i] <= '9') {
            group = (group * 10) + static_cast<std::size_t>(replacement[i] - '0');
            ++i;
          }
          if (group >= match.size()) {
            throw regex_error("invalid group reference in replacement", i);
          }
          out.append(match[group]);
        }
        else if (next_ch == '{') {
          const std::size_t name_begin {i + 1};
          std::size_t       j          {name_begin};
          while (j < replacement.size() && replacement[j] != '}') {
            ++j;
          }
          if (j == replacement.size() || j == name_begin) {
            throw regex_error("malformed ${name} in replacement", i);
          }
          const std::size_t group =
            match.group_index(replacement.substr(name_begin, j - name_begin));
          if (group == npos) {
            throw regex_error("unknown group name in replacement", i);
          }
          out.append(match[group]);
          i = j + 1;
        }
        else {
          throw regex_error("invalid $ escape in replacement", i);
        }
      }
    }
 
    [[nodiscard]] constexpr result_type run(std::string_view text,
                                            detail::run_mode mode) const
    {
      return run(text, 0, npos, mode);
    }
 
    [[nodiscard]] constexpr result_type run(std::string_view        text,
                                            std::size_t             pos,
                                            std::size_t             endpos,
                                            detail::run_mode        mode,
                                            match_semantics         sem = match_semantics::first) const
    {
      const std::size_t              end {endpos < text.size() ? endpos : text.size()};
      typename Storage::state_type   state;
      typename Storage::slot_storage slots;
      const detail::program_view     prog    {program_.view()};
      detail::pike_vm                vm(prog, state);
      // OPT-C Cascade is chosen once here (a single search), never in the per-byte scan.
      const bool matched {prog.hints.stop_set_size >= 1
                          ? vm.template run<true>(text.substr(0, end), pos, mode, slots, 0, sem)
                          : vm.template run<false>(text.substr(0, end), pos, mode, slots, 0, sem)};
      return {text, std::move(slots), matched, pattern(), prog.names};
    }
 
  public:
 
    [[nodiscard]] result_type search_longest(std::string_view text) const
    {
      return run(text, 0, npos, detail::run_mode::search, match_semantics::longest);
    }
 
    [[nodiscard]] result_type search_longest(std::string_view text,
                                             std::size_t      pos,
                                             std::size_t      endpos = npos) const
    {
      return run(text, pos, endpos, detail::run_mode::search, match_semantics::longest);
    }
  };
 
  using regex = basic_regex<detail::dynamic_storage>;
 
  template <fixed_string Pattern, flags F = flags::none>
  using static_regex = basic_regex<detail::static_storage<Pattern, F>>;
} // namespace real
 
#endif // REAL_REAL_HPP