kakoune

Fork of kakoune, an acceptable text editor
git clone git://git.laack.co/kakoune.git
Log | Files | Refs

regex_vm.hh (26040B)


      1 #ifndef regex_vm_hh_INCLUDED
      2 #define regex_vm_hh_INCLUDED
      3 
      4 #include "exception.hh"
      5 #include "flags.hh"
      6 #include "unicode.hh"
      7 #include "utf8.hh"
      8 #include "vector.hh"
      9 #include "utils.hh"
     10 #include "unique_ptr.hh"
     11 
     12 #include <bit>
     13 #include <algorithm>
     14 
     15 namespace Kakoune
     16 {
     17 
     18 struct regex_error : runtime_error
     19 {
     20     using runtime_error::runtime_error;
     21 };
     22 
     23 enum class CharacterType : unsigned char
     24 {
     25     None                    = 0,
     26     Whitespace              = 1 << 0,
     27     HorizontalWhitespace    = 1 << 1,
     28     Word                    = 1 << 2,
     29     Digit                   = 1 << 3,
     30     NotWhitespace           = 1 << 4,
     31     NotHorizontalWhitespace = 1 << 5,
     32     NotWord                 = 1 << 6,
     33     NotDigit                = 1 << 7
     34 };
     35 constexpr bool with_bit_ops(Meta::Type<CharacterType>) { return true; }
     36 
     37 bool is_ctype(CharacterType ctype, Codepoint cp);
     38 
     39 struct CharacterClass
     40 {
     41     struct Range
     42     {
     43         Codepoint min, max;
     44         friend bool operator==(const Range&, const Range&) = default;
     45     };
     46 
     47     Vector<Range, MemoryDomain::Regex> ranges;
     48     CharacterType ctypes = CharacterType::None;
     49     bool negative = false;
     50     bool ignore_case = false;
     51 
     52     friend bool operator==(const CharacterClass&, const CharacterClass&) = default;
     53 
     54     bool matches(Codepoint cp) const
     55     {
     56         if (ignore_case)
     57             cp = to_lower(cp);
     58 
     59         for (auto& [min, max] : ranges)
     60         {
     61             if (cp < min)
     62                 break;
     63             else if (cp <= max)
     64                 return not negative;
     65         }
     66 
     67         return (ctypes != CharacterType::None and is_ctype(ctypes, cp)) != negative;
     68     }
     69 
     70 };
     71 
     72 struct CompiledRegex : UseMemoryDomain<MemoryDomain::Regex>
     73 {
     74     enum Op : char
     75     {
     76         Match,
     77         Literal,
     78         AnyChar,
     79         AnyCharExceptNewLine,
     80         CharRange,
     81         CharType,
     82         CharClass,
     83         Jump,
     84         Split,
     85         Save,
     86         LineAssertion,
     87         SubjectAssertion,
     88         WordBoundary,
     89         LookAround,
     90     };
     91 
     92     enum class Lookaround : Codepoint
     93     {
     94         OpBegin              = 0xF0000,
     95         AnyChar              = 0xF0000,
     96         AnyCharExceptNewLine = 0xF0001,
     97         CharacterClass       = 0xF0002,
     98         CharacterType        = 0xF8000,
     99         OpEnd                = 0xFFFFF,
    100         EndOfLookaround      = static_cast<Codepoint>(-1)
    101     };
    102 
    103     union Param
    104     {
    105         using bool_t = uint8_t; // on ppc bool can be 4 bytes, which breaks packing of this union
    106 
    107         struct Literal
    108         {
    109             uint32_t codepoint : 24;
    110             bool_t ignore_case : 1;
    111         } literal;
    112         struct CharRange
    113         {
    114             uint8_t min;
    115             uint8_t max;
    116             bool_t ignore_case : 1;
    117             bool_t negative;
    118         } range;
    119         CharacterType character_type;
    120         int16_t character_class_index;
    121         int16_t jump_offset;
    122         int16_t save_index;
    123         struct Split
    124         {
    125             int16_t offset;
    126             bool_t prioritize_parent : 1;
    127         } split;
    128         bool_t line_start;
    129         bool_t subject_begin;
    130         bool_t word_boundary_positive;
    131         struct Lookaround
    132         {
    133             int16_t index;
    134             bool_t ahead : 1;
    135             bool_t positive : 1;
    136             bool_t ignore_case : 1;
    137         } lookaround;
    138     };
    139     static_assert(sizeof(Param) == 4);
    140 
    141     struct Instruction
    142     {
    143         Op op;
    144         mutable uint16_t last_step; // mutable as used during execution
    145         Param param;
    146     };
    147     static_assert(sizeof(Instruction) == 8);
    148 
    149     explicit operator bool() const { return not instructions.empty(); }
    150 
    151     struct NamedCapture
    152     {
    153         String name;
    154         uint32_t index;
    155     };
    156 
    157     Vector<Instruction, MemoryDomain::Regex> instructions;
    158     Vector<CharacterClass, MemoryDomain::Regex> character_classes;
    159     Vector<Lookaround, MemoryDomain::Regex> lookarounds;
    160     Vector<NamedCapture, MemoryDomain::Regex> named_captures;
    161     uint32_t first_backward_inst; // -1 if no backward support, 0 if only backward, >0 if both forward and backward
    162     uint32_t save_count;
    163 
    164     struct StartDesc : UseMemoryDomain<MemoryDomain::Regex>
    165     {
    166         static constexpr Codepoint count = 256;
    167         using OffsetLimits = std::numeric_limits<uint8_t>;
    168         char start_byte = 0;
    169         uint8_t offset = 0;
    170         bool map[count];
    171     };
    172 
    173     UniquePtr<StartDesc> forward_start_desc;
    174     UniquePtr<StartDesc> backward_start_desc;
    175 };
    176 
    177 String dump_regex(const CompiledRegex& program);
    178 
    179 enum class RegexCompileFlags
    180 {
    181     None     = 0,
    182     NoSubs   = 1 << 0,
    183     Optimize = 1 << 1,
    184     Backward = 1 << 2,
    185     NoForward = 1 << 3,
    186 };
    187 constexpr bool with_bit_ops(Meta::Type<RegexCompileFlags>) { return true; }
    188 
    189 CompiledRegex compile_regex(StringView re, RegexCompileFlags flags);
    190 
    191 enum class RegexExecFlags
    192 {
    193     None              = 0,
    194     NotBeginOfLine    = 1 << 1,
    195     NotEndOfLine      = 1 << 2,
    196     NotBeginOfWord    = 1 << 3,
    197     NotEndOfWord      = 1 << 4,
    198     NotInitialNull    = 1 << 5,
    199 };
    200 
    201 constexpr bool with_bit_ops(Meta::Type<RegexExecFlags>) { return true; }
    202 
    203 enum class RegexMode
    204 {
    205     Forward  = 1 << 0,
    206     Backward = 1 << 1,
    207     Search   = 1 << 2,
    208     AnyMatch = 1 << 3,
    209     NoSaves  = 1 << 4,
    210 };
    211 constexpr bool with_bit_ops(Meta::Type<RegexMode>) { return true; }
    212 constexpr bool has_direction(RegexMode mode)
    213 {
    214     return (bool)(mode & RegexMode::Forward) xor
    215            (bool)(mode & RegexMode::Backward);
    216 }
    217 
    218 constexpr bool is_direction(RegexMode mode)
    219 {
    220     return has_direction(mode) and
    221            (mode & ~(RegexMode::Forward | RegexMode::Backward)) == RegexMode{0};
    222 }
    223 
    224 template<typename It>
    225 struct SentinelType { using Type = It; };
    226 
    227 template<typename It>
    228     requires requires { typename It::Sentinel; }
    229 struct SentinelType<It> { using Type = typename It::Sentinel; };
    230 
    231 template<typename Iterator, RegexMode mode>
    232     requires (has_direction(mode))
    233 class ThreadedRegexVM
    234 {
    235 public:
    236     ThreadedRegexVM(const CompiledRegex& program)
    237       : m_program{program}
    238     {
    239         kak_assert((forward and program.first_backward_inst != 0) or
    240                    (not forward and program.first_backward_inst != -1));
    241     }
    242 
    243     ThreadedRegexVM(ThreadedRegexVM&&) = default;
    244     ThreadedRegexVM& operator=(ThreadedRegexVM&&) = default;
    245     ThreadedRegexVM(const ThreadedRegexVM&) = delete;
    246     ThreadedRegexVM& operator=(const ThreadedRegexVM&) = delete;
    247 
    248     ~ThreadedRegexVM()
    249     {
    250         for (auto& saves : m_saves)
    251         {
    252             for (int i = m_program.save_count-1; i >= 0; --i)
    253                 saves.pos[i].~Iterator();
    254             operator delete(saves.pos, m_program.save_count * sizeof(Iterator));
    255         }
    256     }
    257 
    258     bool exec(const Iterator& begin, const Iterator& end,
    259               const Iterator& subject_begin, const Iterator& subject_end,
    260               RegexExecFlags flags)
    261     {
    262         return exec(begin, end, subject_begin, subject_end, flags, []{});
    263     }
    264 
    265     bool exec(const Iterator& begin, const Iterator& end,
    266               const Iterator& subject_begin, const Iterator& subject_end,
    267               RegexExecFlags flags, auto&& idle_func)
    268     {
    269         if (flags & RegexExecFlags::NotInitialNull and begin == end)
    270             return false;
    271 
    272         const ExecConfig config{
    273             Sentinel{forward ? begin : end},
    274             Sentinel{forward ? end : begin},
    275             Sentinel{subject_begin},
    276             Sentinel{subject_end},
    277             flags
    278         };
    279 
    280         exec_program(forward ? begin : end, config, idle_func);
    281 
    282         while (not m_threads.next_is_empty())
    283             release_saves(m_threads.pop_next().saves);
    284         return m_found_match;
    285     }
    286 
    287     ArrayView<const Iterator> captures() const
    288     {
    289         if (m_captures >= 0)
    290         {
    291             auto& saves = m_saves[m_captures];
    292             for (int i = 0; i < m_program.save_count; ++i)
    293             {
    294                 if ((saves.valid_mask & (1 << i)) == 0)
    295                     saves.pos[i] = Iterator{};
    296             }
    297             return { saves.pos, m_program.save_count };
    298         }
    299         return {};
    300     }
    301 
    302 private:
    303     struct Saves
    304     {
    305         int32_t refcount;
    306         union {
    307             int32_t next_free;
    308             uint32_t valid_mask;
    309         };
    310         Iterator* pos;
    311     };
    312 
    313     template<bool copy>
    314     int16_t new_saves(Iterator* pos, uint32_t valid_mask)
    315     {
    316         kak_assert(not copy or pos != nullptr);
    317         const auto count = m_program.save_count;
    318         if (m_first_free >= 0)
    319         {
    320             const int16_t res = m_first_free;
    321             Saves& saves = m_saves[res];
    322             m_first_free = saves.next_free;
    323             kak_assert(saves.refcount == 1);
    324             if constexpr (copy)
    325                 std::copy_n(pos, std::bit_width(valid_mask), saves.pos);
    326             saves.valid_mask = valid_mask;
    327             return res;
    328         }
    329 
    330         auto* new_pos = reinterpret_cast<Iterator*>(operator new (count * sizeof(Iterator)));
    331         for (size_t i = 0; i < count; ++i)
    332             new (new_pos+i) Iterator{copy ? pos[i] : Iterator{}};
    333         m_saves.push_back({1, {.valid_mask=valid_mask}, new_pos});
    334         return static_cast<int16_t>(m_saves.size() - 1);
    335     }
    336 
    337     void release_saves(int16_t index)
    338     {
    339         if (index < 0)
    340             return;
    341         auto& saves = m_saves[index];
    342         if (saves.refcount == 1)
    343         {
    344             saves.next_free = m_first_free;
    345             m_first_free = index;
    346         }
    347         else
    348             --saves.refcount;
    349     };
    350 
    351     struct Thread
    352     {
    353         const CompiledRegex::Instruction* inst;
    354         int saves;
    355     };
    356 
    357     using StartDesc = CompiledRegex::StartDesc;
    358     using Sentinel = typename SentinelType<Iterator>::Type;
    359     struct ExecConfig
    360     {
    361         const Sentinel begin;
    362         const Sentinel end;
    363         const Sentinel subject_begin;
    364         const Sentinel subject_end;
    365         const RegexExecFlags flags;
    366     };
    367 
    368     // Steps a thread until it consumes the current character, matches or fail
    369     [[gnu::always_inline]]
    370     void step_current_thread(const Iterator& pos, Codepoint cp, uint16_t current_step, const ExecConfig& config)
    371     {
    372         Thread thread = m_threads.pop_current();
    373         auto failed   = [&] { release_saves(thread.saves); };
    374         auto consumed = [&] { m_threads.push_next(thread); };
    375 
    376         while (true)
    377         {
    378             auto* inst = thread.inst++;
    379             auto [op, last_step, param] = *inst;
    380             // if this instruction was already executed for this step in another thread,
    381             // then this thread is redundant and can be dropped
    382             if (last_step == current_step)
    383                 return failed();
    384             inst->last_step = current_step;
    385 
    386             switch (op)
    387             {
    388                 case CompiledRegex::Match:
    389                     if ((pos != config.end and not (mode & RegexMode::Search)) or
    390                         (config.flags & RegexExecFlags::NotInitialNull and pos == config.begin))
    391                         return failed();
    392 
    393                     release_saves(m_captures);
    394                     m_captures = thread.saves;
    395                     m_found_match = true;
    396 
    397                     // remove lower priority threads
    398                     while (not m_threads.current_is_empty())
    399                         release_saves(m_threads.pop_current().saves);
    400                     return;
    401                 case CompiledRegex::Literal:
    402                     if (pos != config.end and
    403                         param.literal.codepoint == (param.literal.ignore_case ? to_lower(cp) : cp))
    404                         return consumed();
    405                     return failed();
    406                 case CompiledRegex::AnyChar:
    407                     return consumed();
    408                 case CompiledRegex::AnyCharExceptNewLine:
    409                     if (pos != config.end and cp != '\n')
    410                         return consumed();
    411                     return failed();
    412                 case CompiledRegex::CharRange:
    413                     if (auto actual_cp = (param.range.ignore_case ? to_lower(cp) : cp);
    414                         pos != config.end and
    415                         (actual_cp >= param.range.min and actual_cp <= param.range.max) != param.range.negative)
    416                         return consumed();
    417                     return failed();
    418                 case CompiledRegex::CharType:
    419                     if (pos != config.end and is_ctype(param.character_type, cp))
    420                         return consumed();
    421                     return failed();
    422                 case CompiledRegex::CharClass:
    423                     if (pos != config.end and
    424                         m_program.character_classes[param.character_class_index].matches(cp))
    425                         return consumed();
    426                     return failed();
    427                 case CompiledRegex::Jump:
    428                     thread.inst = inst + param.jump_offset;
    429                     break;
    430                 case CompiledRegex::Split:
    431                     if (auto* target = inst + param.split.offset;
    432                         target->last_step != current_step)
    433                     {
    434                         if (thread.saves >= 0)
    435                             ++m_saves[thread.saves].refcount;
    436                         if (not param.split.prioritize_parent)
    437                             std::swap(thread.inst, target);
    438                         m_threads.push_current({target, thread.saves});
    439                     }
    440                     break;
    441                 case CompiledRegex::Save:
    442                     if constexpr (mode & RegexMode::NoSaves)
    443                         break;
    444                     if (thread.saves < 0)
    445                         thread.saves = new_saves<false>(nullptr, 0);
    446                     else if (auto& saves = m_saves[thread.saves]; saves.refcount > 1)
    447                     {
    448                         --saves.refcount;
    449                         thread.saves = new_saves<true>(saves.pos, saves.valid_mask);
    450                     }
    451                     m_saves[thread.saves].pos[param.save_index] = pos;
    452                     m_saves[thread.saves].valid_mask |= (1 << param.save_index);
    453                     break;
    454                 case CompiledRegex::LineAssertion:
    455                     if (not (param.line_start ? is_line_start(pos, config) : is_line_end(pos, config)))
    456                         return failed();
    457                     break;
    458                 case CompiledRegex::SubjectAssertion:
    459                     if (pos != (param.subject_begin ? config.subject_begin : config.subject_end))
    460                         return failed();
    461                     break;
    462                 case CompiledRegex::WordBoundary:
    463                     if (is_word_boundary(pos, config) != param.word_boundary_positive)
    464                         return failed();
    465                     break;
    466                 case CompiledRegex::LookAround:
    467                     if (lookaround(param.lookaround, pos, config) != param.lookaround.positive)
    468                         return failed();
    469                     break;
    470             }
    471         }
    472         return failed();
    473     }
    474 
    475     void exec_program(const Iterator& start, const ExecConfig& config, auto&& idle_func)
    476     {
    477         kak_assert(m_threads.current_is_empty() and m_threads.next_is_empty());
    478         m_threads.ensure_initial_capacity();
    479         release_saves(m_captures);
    480         m_captures = -1;
    481         m_found_match = false;
    482 
    483         const auto* start_desc = (forward ? m_program.forward_start_desc : m_program.backward_start_desc).get();
    484         Iterator next_start = start;
    485         if (start_desc)
    486         {
    487             if constexpr (mode & RegexMode::Search)
    488                 next_start = find_next_start(start, config.end, *start_desc);
    489             if (next_start == config.end or // Non null start_desc means we consume at least one char
    490                 (not (mode & RegexMode::Search) and
    491                   not start_desc->map[static_cast<unsigned char>(forward ? *start : *std::prev(start))]))
    492                 return;
    493         }
    494 
    495         const auto insts = forward ? ArrayView(m_program.instructions).subrange(0, m_program.first_backward_inst)
    496                                    : ArrayView(m_program.instructions).subrange(m_program.first_backward_inst);
    497         m_threads.push_current({insts.begin(), -1});
    498 
    499         uint16_t current_step = -1;
    500         uint8_t idle_count = 0; // Run idle loop every 256 * 65536 == 16M codepoints
    501         Iterator pos = next_start;
    502         while (pos != config.end)
    503         {
    504             if (++current_step == 0)
    505             {
    506                 if (++idle_count == 0)
    507                     idle_func();
    508 
    509                 // We wrapped, avoid potential collision on inst.last_step by resetting them
    510                 for (auto& inst : insts)
    511                     inst.last_step = 0;
    512                 current_step = 1; // step 0 is never valid
    513             }
    514 
    515             auto next = pos;
    516             Codepoint cp = codepoint(next, config);
    517 
    518             while (not m_threads.current_is_empty())
    519                 step_current_thread(pos, cp, current_step, config);
    520 
    521             if ((mode & RegexMode::Search) and not m_found_match)
    522             {
    523                 if (start_desc)
    524                 {
    525                     if (pos == next_start)
    526                         next_start = find_next_start(next, config.end, *start_desc);
    527                     if (m_threads.next_is_empty())
    528                         next = next_start;
    529                 }
    530                 if (not start_desc or next == next_start)
    531                     m_threads.push_next({insts.begin(), -1});
    532             }
    533             else if (m_threads.next_is_empty() or (m_found_match and (mode & RegexMode::AnyMatch)))
    534                 return;
    535 
    536             pos = next;
    537             m_threads.swap_next();
    538         }
    539 
    540         if (++current_step == 0)
    541         {
    542             for (auto& inst : insts)
    543                 inst.last_step = 0;
    544             current_step = 1; // step 0 is never valid
    545         }
    546         while (not m_threads.current_is_empty())
    547             step_current_thread(pos, -1, current_step, config);
    548     }
    549 
    550     static Iterator find_next_start(const Iterator& start, const Sentinel& end, const StartDesc& start_desc)
    551     {
    552         auto pos = start;
    553         if (char start_byte = start_desc.start_byte)
    554         {
    555             while (pos != end)
    556             {
    557                 if constexpr (forward)
    558                 {
    559                     if (*pos == start_byte)
    560                        return utf8::advance(pos, start, -CharCount(start_desc.offset));
    561                     ++pos;
    562                 }
    563                 else
    564                 {
    565                     auto prev = utf8::previous(pos, end);
    566                     if (*prev == start_byte)
    567                        return utf8::advance(pos, start, CharCount(start_desc.offset));
    568                     pos = prev;
    569                 }
    570             }
    571         }
    572 
    573         while (pos != end)
    574         {
    575             static_assert(StartDesc::count <= 256, "start desc should be ascii only");
    576             if constexpr (forward)
    577             {
    578                 if (start_desc.map[static_cast<unsigned char>(*pos)])
    579                     return utf8::advance(pos, start, -CharCount(start_desc.offset));
    580                 ++pos;
    581             }
    582             else
    583             {
    584                 auto prev = utf8::previous(pos, end);
    585                 if (start_desc.map[static_cast<unsigned char>(*prev)])
    586                     return utf8::advance(pos, start, CharCount(start_desc.offset));
    587                 pos = prev;
    588             }
    589         }
    590         return pos;
    591     }
    592 
    593     bool lookaround(CompiledRegex::Param::Lookaround param, Iterator pos, const ExecConfig& config) const
    594     {
    595         using Lookaround = CompiledRegex::Lookaround;
    596 
    597         if (not param.ahead)
    598         {
    599             if (pos == config.subject_begin)
    600                 return m_program.lookarounds[param.index] == Lookaround::EndOfLookaround;
    601             utf8::to_previous(pos, config.subject_begin);
    602         }
    603 
    604         for (auto it = m_program.lookarounds.begin() + param.index; *it != Lookaround::EndOfLookaround; ++it)
    605         {
    606             if (param.ahead and pos == config.subject_end)
    607                 return false;
    608 
    609             Codepoint cp = utf8::codepoint(pos, config.subject_end);
    610             if (param.ignore_case)
    611                 cp = to_lower(cp);
    612 
    613             const Lookaround op = *it;
    614             if (op == Lookaround::AnyChar)
    615             {} // any character matches
    616             else if (op == Lookaround::AnyCharExceptNewLine)
    617             {
    618                 if (cp == '\n')
    619                     return false;
    620             }
    621             else if (op >= Lookaround::CharacterClass and op < Lookaround::CharacterType)
    622             {
    623                 auto index = to_underlying(op) - to_underlying(Lookaround::CharacterClass);
    624                 if (not m_program.character_classes[index].matches(cp))
    625                     return false;
    626             }
    627             else if (op >= Lookaround::CharacterType and op < Lookaround::OpEnd)
    628             {
    629                 auto ctype = static_cast<CharacterType>(to_underlying(op) & 0xFF);
    630                 if (not is_ctype(ctype, cp))
    631                     return false;
    632             }
    633             else if (static_cast<Codepoint>(op) != cp)
    634                 return false;
    635 
    636             if (not param.ahead and pos == config.subject_begin)
    637                 return *++it == Lookaround::EndOfLookaround;
    638 
    639             param.ahead ? utf8::to_next(pos, config.subject_end)
    640                         : utf8::to_previous(pos, config.subject_begin);
    641         }
    642         return true;
    643     }
    644 
    645     static bool is_line_start(const Iterator& pos, const ExecConfig& config)
    646     {
    647         if (pos == config.subject_begin)
    648             return not (config.flags & RegexExecFlags::NotBeginOfLine);
    649         return *(pos-1) == '\n';
    650     }
    651 
    652     static bool is_line_end(const Iterator& pos, const ExecConfig& config)
    653     {
    654         if (pos == config.subject_end)
    655             return not (config.flags & RegexExecFlags::NotEndOfLine);
    656         return *pos == '\n';
    657     }
    658 
    659     static bool is_word_boundary(const Iterator& pos, const ExecConfig& config)
    660     {
    661         if (pos == config.subject_begin)
    662             return not (config.flags & RegexExecFlags::NotBeginOfWord);
    663         if (pos == config.subject_end)
    664             return not (config.flags & RegexExecFlags::NotEndOfWord);
    665         return is_word(utf8::codepoint(utf8::previous(pos, config.subject_begin), config.subject_end)) !=
    666                is_word(utf8::codepoint(pos, config.subject_end));
    667     }
    668 
    669     [[gnu::flatten]]
    670     static Codepoint codepoint(Iterator& it, const ExecConfig& config)
    671     {
    672         if constexpr (forward)
    673         {
    674             return utf8::read_codepoint(it, config.end);
    675         }
    676         else
    677         {
    678             utf8::to_previous(it, config.end);
    679             return utf8::codepoint(it, config.begin);
    680         }
    681     }
    682 
    683     // This stores both the current thread stack and next thread stack in a ring buffer
    684     // current threads go from m_current to m_next_begin (pushing decrements m_current)
    685     // next thrads go from m_next_begin to m_next_end (pushing increments m_next_end)
    686     struct DualThreadStack
    687     {
    688         bool current_is_empty() const { return m_current == m_next_begin; }
    689         bool next_is_empty() const { return m_next_end == m_next_begin; }
    690 
    691         [[gnu::always_inline]]
    692         void push_current(Thread thread) { m_data[decrement(m_current)] = thread; grow_ifn(true); }
    693         [[gnu::always_inline]]
    694         Thread pop_current() { return m_data[post_increment(m_current)]; }
    695 
    696         [[gnu::always_inline]]
    697         void push_next(Thread thread) { m_data[post_increment(m_next_end)] = thread; grow_ifn(false); }
    698         [[gnu::always_inline]]
    699         Thread pop_next() { return m_data[decrement(m_next_end)]; }
    700 
    701         void swap_next()
    702         {
    703             m_current = m_next_begin;
    704             m_next_begin = m_next_end;
    705         }
    706 
    707         void ensure_initial_capacity()
    708         {
    709             if (m_capacity_mask != 0)
    710                 return;
    711 
    712             constexpr uint32_t initial_capacity = 64 / sizeof(Thread);
    713             static_assert(initial_capacity >= 4 and std::has_single_bit(initial_capacity));
    714             m_data.reset(new Thread[initial_capacity]);
    715             m_capacity_mask = initial_capacity-1;
    716         }
    717 
    718         [[gnu::always_inline]]
    719         void grow_ifn(bool pushed_current)
    720         {
    721             if (m_current == m_next_end)
    722                 grow(pushed_current);
    723         }
    724 
    725         [[gnu::noinline]]
    726         void grow(bool pushed_current)
    727         {
    728             auto capacity = m_capacity_mask + 1;
    729             const auto new_capacity = capacity * 2;
    730             Thread* new_data = new Thread[new_capacity];
    731             Thread* old_data = m_data.get();
    732             // copy the whole data to avoid having to consider either stack wrapping around
    733             std::rotate_copy(old_data, old_data + m_current, old_data + capacity, new_data);
    734             m_next_begin = (m_next_begin - m_current) & m_capacity_mask;
    735             if (pushed_current and m_next_begin == 0)
    736                 m_next_begin = capacity;
    737             m_next_end = capacity;
    738             m_current = 0;
    739 
    740             m_data.reset(new_data);
    741             kak_assert(std::has_single_bit(new_capacity));
    742             m_capacity_mask = new_capacity-1;
    743         }
    744 
    745     private:
    746         uint32_t decrement(uint32_t& index)
    747         {
    748             index = (index - 1) & m_capacity_mask;
    749             return index;
    750         }
    751 
    752         uint32_t post_increment(uint32_t& index)
    753         {
    754             auto res = index;
    755             index = (index + 1) & m_capacity_mask;
    756             return res;
    757         }
    758 
    759         UniquePtr<Thread[]> m_data;
    760         uint32_t m_capacity_mask = 0; // Maximum capacity should be 2*instruction count, so 65536
    761         uint32_t m_current = 0;
    762         uint32_t m_next_begin = 0;
    763         uint32_t m_next_end = 0;
    764     };
    765 
    766     static constexpr bool forward = mode & RegexMode::Forward;
    767 
    768     const CompiledRegex& m_program;
    769     DualThreadStack m_threads;
    770     Vector<Saves, MemoryDomain::Regex> m_saves;
    771     int16_t m_first_free = -1;
    772     int16_t m_captures = -1;
    773     bool m_found_match = false;
    774 };
    775 
    776 }
    777 
    778 #endif // regex_vm_hh_INCLUDED