kakoune

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

regex_vm.cc (60206B)


      1 #include "regex_vm.hh"
      2 
      3 #include "string.hh"
      4 #include "unicode.hh"
      5 #include "unit_tests.hh"
      6 #include "utf8.hh"
      7 #include "utf8_iterator.hh"
      8 #include "format.hh"
      9 #include "optional.hh"
     10 #include "vector.hh"
     11 #include "utils.hh"
     12 #include "ranges.hh"
     13 
     14 #include <cstdio>
     15 #include <cstring>
     16 #include <limits>
     17 
     18 namespace Kakoune
     19 {
     20 
     21 constexpr Codepoint CompiledRegex::StartDesc::count;
     22 
     23 namespace
     24 {
     25 
     26 struct ParsedRegex
     27 {
     28     enum Op : char
     29     {
     30         Literal,
     31         AnyChar,
     32         AnyCharExceptNewLine,
     33         CharClass,
     34         CharType,
     35         Sequence,
     36         Alternation,
     37         LineStart,
     38         LineEnd,
     39         WordBoundary,
     40         NotWordBoundary,
     41         SubjectBegin,
     42         SubjectEnd,
     43         ResetStart,
     44         LookAhead,
     45         NegativeLookAhead,
     46         LookBehind,
     47         NegativeLookBehind,
     48     };
     49 
     50     struct Quantifier
     51     {
     52         static constexpr int16_t infinite = std::numeric_limits<int16_t>::max();
     53 
     54         int16_t min = 0, max = 0;
     55         bool greedy = true;
     56 
     57         bool allows_none() const { return min == 0; }
     58         bool allows_infinite_repeat() const { return max == infinite; };
     59 
     60         friend bool operator==(Quantifier, Quantifier) = default;
     61     };
     62 
     63     using NodeIndex = int16_t;
     64     struct Node
     65     {
     66         Op op;
     67         bool ignore_case;
     68         NodeIndex children_end;
     69         Codepoint value;
     70         Quantifier quantifier;
     71     };
     72 
     73     Vector<Node, MemoryDomain::Regex> nodes;
     74 
     75     Vector<CharacterClass, MemoryDomain::Regex> character_classes;
     76     Vector<CompiledRegex::NamedCapture, MemoryDomain::Regex> named_captures;
     77     uint32_t capture_count;
     78 };
     79 
     80 template<RegexMode mode = RegexMode::Forward>
     81 struct Children
     82 {
     83     static_assert(has_direction(mode));
     84     using Index = ParsedRegex::NodeIndex;
     85     struct Sentinel {};
     86     struct Iterator
     87     {
     88         static constexpr bool forward = mode & RegexMode::Forward;
     89         Iterator(ArrayView<const ParsedRegex::Node> nodes, Index index)
     90           : m_nodes{nodes},
     91             m_pos(forward ? index+1 : find_prev(index, nodes[index].children_end)),
     92             m_end(forward ? nodes[index].children_end : index)
     93         {}
     94 
     95         Iterator& operator++()
     96         {
     97             m_pos = forward ? m_nodes[m_pos].children_end : find_prev(m_end, m_pos);
     98             return *this;
     99         }
    100 
    101         Index operator*() const { return m_pos; }
    102         bool operator!=(Sentinel) const { return m_pos != m_end; }
    103 
    104     private:
    105         Index find_prev(Index parent, Index pos) const
    106         {
    107             Index child = parent+1;
    108             if (child == pos)
    109                 return parent;
    110             while (m_nodes[child].children_end != pos)
    111                 child = m_nodes[child].children_end;
    112             return child;
    113         }
    114 
    115         ArrayView<const ParsedRegex::Node> m_nodes;
    116         Index m_pos;
    117         Index m_end;
    118     };
    119 
    120     Iterator begin() const { return {m_parsed_regex.nodes, m_index}; }
    121     Sentinel end() const { return {}; }
    122 
    123     const ParsedRegex& m_parsed_regex;
    124     const Index m_index;
    125 };
    126 
    127 
    128 // Recursive descent parser based on naming used in the ECMAScript
    129 // standard, although the syntax is not fully compatible.
    130 struct RegexParser
    131 {
    132     static ParsedRegex parse(StringView re) { return RegexParser{re}.m_parsed_regex; }
    133 
    134 private:
    135     RegexParser(StringView re)
    136         : m_regex{re}, m_pos{re.begin(), re}
    137     {
    138         m_parsed_regex.capture_count = 1;
    139         m_parsed_regex.nodes.reserve((size_t)re.length());
    140         NodeIndex root = disjunction(0);
    141         kak_assert(root == 0);
    142     }
    143 
    144     struct InvalidPolicy
    145     {
    146         Codepoint operator()(Codepoint cp) const { throw regex_error{"Invalid utf8 in regex"}; }
    147     };
    148 
    149     enum class Flags
    150     {
    151         None              = 0,
    152         IgnoreCase        = 1 << 0,
    153         DotMatchesNewLine = 1 << 1,
    154     };
    155     friend constexpr bool with_bit_ops(Meta::Type<Flags>) { return true; }
    156 
    157     using Iterator = utf8::iterator<const char*, const char*, Codepoint, int, InvalidPolicy>;
    158     using NodeIndex = ParsedRegex::NodeIndex;
    159 
    160     NodeIndex disjunction(uint32_t capture = -1)
    161     {
    162         NodeIndex index = add_node(ParsedRegex::Alternation, capture);
    163         while (true)
    164         {
    165             alternative(ParsedRegex::Sequence);
    166             if (at_end() or *m_pos != '|')
    167                 break;
    168             ++m_pos;
    169         }
    170         get_node(index).children_end = m_parsed_regex.nodes.size();
    171 
    172         return index;
    173     }
    174 
    175     NodeIndex alternative(ParsedRegex::Op op)
    176     {
    177         NodeIndex index = add_node(op);
    178         while (term())
    179         {}
    180         get_node(index).children_end = m_parsed_regex.nodes.size();
    181 
    182         return index;
    183     }
    184 
    185     Optional<NodeIndex> term()
    186     {
    187         while (modifiers()) // read all modifiers
    188         {}
    189         if (auto node = assertion())
    190             return node;
    191         if (auto node = atom())
    192         {
    193             get_node(*node).quantifier = quantifier();
    194             return node;
    195         }
    196         return {};
    197     }
    198 
    199     bool modifiers()
    200     {
    201         auto it = m_pos.base();
    202         if (m_regex.end() - it >= 4 and *it++ == '(' and *it++ == '?')
    203         {
    204             while (true)
    205             {
    206                 auto m = *it++;
    207                 switch (m)
    208                 {
    209                     case 'i': m_flags |= Flags::IgnoreCase; break;
    210                     case 'I': m_flags &= ~Flags::IgnoreCase; break;
    211                     case 's': m_flags |= Flags::DotMatchesNewLine; break;
    212                     case 'S': m_flags &= ~Flags::DotMatchesNewLine; break;
    213                     case ')':
    214                         m_pos = Iterator{it, m_regex};
    215                         return true;
    216                     default: return false;
    217                 }
    218             }
    219         }
    220         return false;
    221     }
    222 
    223     Optional<NodeIndex> assertion()
    224     {
    225         if (at_end())
    226             return {};
    227 
    228         switch (*m_pos)
    229         {
    230             case '^': ++m_pos; return add_node(ParsedRegex::LineStart);
    231             case '$': ++m_pos; return add_node(ParsedRegex::LineEnd);
    232             case '\\':
    233                 if (m_pos+1 == m_regex.end())
    234                     return {};
    235                 switch (*(m_pos+1))
    236                 {
    237                     case 'b': m_pos += 2; return add_node(ParsedRegex::WordBoundary);
    238                     case 'B': m_pos += 2; return add_node(ParsedRegex::NotWordBoundary);
    239                     case 'A': m_pos += 2; return add_node(ParsedRegex::SubjectBegin);
    240                     case 'z': m_pos += 2; return add_node(ParsedRegex::SubjectEnd);
    241                     case 'K': m_pos += 2; return add_node(ParsedRegex::ResetStart);
    242                 }
    243                 break;
    244             case '(':
    245             {
    246                 auto it = m_pos.base()+1;
    247                 if (m_regex.end() - it <= 2 or *it++ != '?')
    248                     return {};
    249 
    250                 ParsedRegex::Op op;
    251                 switch (*it++)
    252                 {
    253                     case '=': op = ParsedRegex::LookAhead; break;
    254                     case '!': op = ParsedRegex::NegativeLookAhead; break;
    255                     case '<':
    256                     {
    257                         switch (*it++)
    258                         {
    259                             case '=': op = ParsedRegex::LookBehind; break;
    260                             case '!': op = ParsedRegex::NegativeLookBehind; break;
    261                             default: return {};
    262                         }
    263                         break;
    264                     }
    265                     default: return {};
    266                 }
    267                 m_pos = Iterator{it, m_regex};
    268                 NodeIndex lookaround = alternative(op);
    269                 if (auto end_pos = m_pos; at_end() or *m_pos++ != ')')
    270                 {
    271                     if (*end_pos == '|')
    272                         parse_error("Alternations cannot be used in lookarounds");
    273                     parse_error("unclosed parenthesis");
    274                 }
    275                 validate_lookaround(lookaround);
    276                 return lookaround;
    277             }
    278         }
    279         return {};
    280     }
    281 
    282     Optional<NodeIndex> atom()
    283     {
    284         if (at_end())
    285             return {};
    286 
    287         switch (const Codepoint cp = *m_pos)
    288         {
    289             case '.':
    290                 ++m_pos;
    291                 return add_node((m_flags & Flags::DotMatchesNewLine) ? ParsedRegex::AnyChar : ParsedRegex::AnyCharExceptNewLine);
    292             case '(':
    293             {
    294                 uint32_t capture_group = -1;
    295                 const char* it = (++m_pos).base();
    296                 if (m_regex.end() - it < 2 or *it++ != '?')
    297                     capture_group = m_parsed_regex.capture_count++;
    298                 else if (*it == ':')
    299                     m_pos = Iterator{++it, m_regex};
    300                 else if (*it == '<')
    301                 {
    302                     const auto name_start = ++it;
    303                     while (it != m_regex.end() and is_word(*it))
    304                         ++it;
    305                     if (it == m_regex.end() or *it != '>')
    306                         parse_error("named captures should be only ascii word characters");
    307                     capture_group = m_parsed_regex.capture_count++;
    308                     m_parsed_regex.named_captures.push_back({{name_start, it}, capture_group});
    309                     m_pos = Iterator{++it, m_regex};
    310                 }
    311 
    312                 NodeIndex content = disjunction(capture_group);
    313                 if (at_end() or *m_pos++ != ')')
    314                     parse_error("unclosed parenthesis");
    315                 return content;
    316             }
    317             case '\\':
    318                 ++m_pos;
    319                 return atom_escape();
    320             case '[':
    321                 ++m_pos;
    322                 return character_class();
    323             case '|': case ')':
    324                 return {};
    325             default:
    326                 if (contains(StringView{"^$.*+?[]{}"}, cp) or (cp >= 0xF0000 and cp <= 0xFFFFF))
    327                     parse_error(format("unexpected '{}'", cp));
    328                 ++m_pos;
    329                 return add_node(ParsedRegex::Literal, cp);
    330         }
    331     }
    332 
    333     Codepoint read_hex(size_t count)
    334     {
    335         Codepoint res = 0;
    336         for (int i = 0; i < count; ++i)
    337         {
    338             if (at_end())
    339                 parse_error("unterminated hex sequence");
    340             Codepoint digit = *m_pos++;
    341             Codepoint digit_value;
    342             if ('0' <= digit and digit <= '9')
    343                 digit_value = digit - '0';
    344             else if ('a' <= digit and digit <= 'f')
    345                 digit_value = 0xa + digit - 'a';
    346             else if ('A' <= digit and digit <= 'F')
    347                 digit_value = 0xa + digit - 'A';
    348             else
    349                 parse_error(format("invalid hex digit '{}'", digit));
    350 
    351             res = res * 16 + digit_value;
    352         }
    353         return res;
    354     }
    355 
    356     NodeIndex atom_escape()
    357     {
    358         const Codepoint cp = *m_pos++;
    359 
    360         if (cp == 'N')
    361             return add_node(ParsedRegex::AnyCharExceptNewLine);
    362 
    363         if (cp == 'Q')
    364         {
    365             auto escaped_sequence = add_node(ParsedRegex::Sequence);
    366             constexpr StringView end_mark{"\\E"};
    367 
    368             auto quote_end = std::search(m_pos.base(), m_regex.end(), end_mark.begin(), end_mark.end());
    369             while (m_pos != quote_end)
    370                 add_node(ParsedRegex::Literal, *m_pos++);
    371             get_node(escaped_sequence).children_end = m_parsed_regex.nodes.size();
    372 
    373             if (quote_end != m_regex.end())
    374                 m_pos += 2;
    375 
    376             return escaped_sequence;
    377         }
    378 
    379         // CharacterClassEscape
    380         auto class_it = find_if(character_class_escapes, [cp](auto& c) { return c.cp == cp; });
    381         if (class_it != std::end(character_class_escapes))
    382             return add_node(ParsedRegex::CharType, (Codepoint)class_it->ctype);
    383 
    384         // CharacterEscape
    385         for (auto& control : control_escapes)
    386         {
    387             if (control.name == cp)
    388                 return add_node(ParsedRegex::Literal, control.value);
    389         }
    390 
    391         if (cp == '0')
    392             return add_node(ParsedRegex::Literal, '\0');
    393         else if (cp == 'c')
    394         {
    395             if (at_end())
    396                 parse_error("unterminated control escape");
    397             Codepoint ctrl = *m_pos++;
    398             if (('a' <= ctrl and ctrl <= 'z') or ('A' <= ctrl and ctrl <= 'Z'))
    399                 return add_node(ParsedRegex::Literal, ctrl % 32);
    400             parse_error(format("Invalid control escape character '{}'", ctrl));
    401         }
    402         else if (cp == 'x')
    403             return add_node(ParsedRegex::Literal, read_hex(2));
    404         else if (cp == 'u')
    405             return add_node(ParsedRegex::Literal, read_hex(6));
    406 
    407         if (contains("^$\\.*+?()[]{}|", cp)) // SyntaxCharacter
    408             return add_node(ParsedRegex::Literal, cp);
    409         parse_error(format("unknown atom escape '{}'", cp));
    410     }
    411 
    412     static void normalize_ranges(Vector<CharacterClass::Range, MemoryDomain::Regex>& ranges)
    413     {
    414         if (ranges.empty())
    415             return;
    416 
    417         // Sort ranges so that we can use binary search
    418         std::sort(ranges.begin(), ranges.end(),
    419                   [](auto& lhs, auto& rhs) { return lhs.min < rhs.min; });
    420 
    421         // merge overlapping ranges
    422         auto pos = ranges.begin();
    423         for (auto next = pos+1; next != ranges.end(); ++next)
    424         {
    425             if (pos->max + 1 >= next->min)
    426             {
    427                 if (next->max > pos->max)
    428                     pos->max = next->max;
    429             }
    430             else
    431                 *++pos = *next;
    432         }
    433         ranges.erase(pos+1, ranges.end());
    434     }
    435 
    436     NodeIndex character_class()
    437     {
    438         CharacterClass character_class;
    439 
    440         character_class.ignore_case = (m_flags & Flags::IgnoreCase);
    441         character_class.negative = m_pos != m_regex.end() and *m_pos == '^';
    442         if (character_class.negative)
    443             ++m_pos;
    444 
    445         while (m_pos != m_regex.end() and *m_pos != ']')
    446         {
    447             auto cp = *m_pos++;
    448             if (cp == '-')
    449             {
    450                 character_class.ranges.push_back({ '-', '-' });
    451                 continue;
    452             }
    453 
    454             if (at_end())
    455                 break;
    456 
    457             auto read_escaped_char = [this]() {
    458                 Codepoint cp = *m_pos++;
    459                 auto it = find_if(control_escapes, [cp](auto&& t) { return t.name == cp; });
    460                 if (it != std::end(control_escapes))
    461                     return it->value;
    462                 if (cp == 'x')
    463                     return read_hex(2);
    464                 if (cp == 'u')
    465                     return read_hex(6);
    466                 if (not contains("^$\\.*+?()[]{}|-", cp)) // SyntaxCharacter and -
    467                     parse_error(format("unknown character class escape '{}'", cp));
    468                 return cp;
    469             };
    470 
    471             if (cp == '\\')
    472             {
    473                 auto it = find_if(character_class_escapes,
    474                                   [cp = *m_pos](auto&& t) { return t.cp == cp; });
    475                 if (it != std::end(character_class_escapes))
    476                 {
    477                     character_class.ctypes |= it->ctype;
    478                     ++m_pos;
    479                     continue;
    480                 }
    481                 else // its an escaped character
    482                     cp = read_escaped_char();
    483             }
    484 
    485             CharacterClass::Range range = { cp, cp };
    486             if (*m_pos == '-')
    487             {
    488                 if (++m_pos == m_regex.end())
    489                     break;
    490                 if (*m_pos != ']')
    491                 {
    492                     cp = *m_pos++;
    493                     if (cp == '\\')
    494                         cp = read_escaped_char();
    495                     range.max = cp;
    496                     if (range.min > range.max)
    497                         parse_error("invalid range specified");
    498                 }
    499                 else
    500                 {
    501                     character_class.ranges.push_back(range);
    502                     range = { '-', '-' };
    503                 }
    504             }
    505             character_class.ranges.push_back(range);
    506         }
    507         if (at_end())
    508             parse_error("unclosed character class");
    509         ++m_pos;
    510 
    511         if (not character_class.ignore_case)
    512         {
    513             bool could_ignore_case = true;
    514             for (const auto& [min, max] : character_class.ranges)
    515             {
    516                 if (not contains(character_class.ranges, CharacterClass::Range{to_lower(min), to_lower(max)}) or
    517                     not contains(character_class.ranges, CharacterClass::Range{to_upper(min), to_upper(max)}))
    518                     could_ignore_case = false;
    519             }
    520             character_class.ignore_case = could_ignore_case;
    521         }
    522 
    523         if (character_class.ignore_case)
    524         {
    525             for (auto& range : character_class.ranges)
    526             {
    527                 range.min = to_lower(range.min);
    528                 range.max = to_lower(range.max);
    529             }
    530         }
    531 
    532         normalize_ranges(character_class.ranges);
    533 
    534         // Optimize the relatively common case of using a character class to
    535         // escape a character, such as [*]
    536         if (character_class.ctypes == CharacterType::None and not character_class.negative and
    537             character_class.ranges.size() == 1 and
    538             character_class.ranges.front().min == character_class.ranges.front().max)
    539             return add_node(ParsedRegex::Literal, character_class.ranges.front().min, {1,1}, character_class.ignore_case);
    540 
    541         if (character_class.ctypes != CharacterType::None and not character_class.negative and
    542             character_class.ranges.empty())
    543             return add_node(ParsedRegex::CharType, (Codepoint)character_class.ctypes);
    544 
    545         auto it = std::find(m_parsed_regex.character_classes.begin(), m_parsed_regex.character_classes.end(), character_class);
    546         auto class_id = it - m_parsed_regex.character_classes.begin();
    547         if (it == m_parsed_regex.character_classes.end())
    548             m_parsed_regex.character_classes.push_back(std::move(character_class));
    549 
    550         return add_node(ParsedRegex::CharClass, class_id);
    551     }
    552 
    553     ParsedRegex::Quantifier quantifier()
    554     {
    555         if (at_end())
    556             return {1, 1};
    557 
    558         constexpr int max_repeat = 1000;
    559         auto read_bound = [&]() -> Optional<int16_t> {
    560             int16_t res = 0;
    561             for (auto begin = m_pos; m_pos != m_regex.end(); ++m_pos)
    562             {
    563                 const auto cp = *m_pos;
    564                 if (cp < '0' or cp > '9')
    565                     return m_pos == begin ? Optional<int16_t>{} : res;
    566                 res = res * 10 + cp - '0';
    567                 if (res > max_repeat)
    568                     parse_error(format("Explicit quantifier is too big, maximum is {}", max_repeat));
    569             }
    570             return res;
    571         };
    572 
    573         auto check_greedy = [&]() {
    574             if (at_end() or *m_pos != '?')
    575                 return true;
    576             ++m_pos;
    577             return false;
    578         };
    579 
    580         switch (*m_pos)
    581         {
    582             case '*': ++m_pos; return {0, ParsedRegex::Quantifier::infinite, check_greedy()};
    583             case '+': ++m_pos; return {1, ParsedRegex::Quantifier::infinite, check_greedy()};
    584             case '?': ++m_pos; return {0, 1, check_greedy()};
    585             case '{':
    586             {
    587                 ++m_pos;
    588                 const int16_t min = read_bound().value_or(int16_t{});
    589                 int16_t max = min;
    590                 if (*m_pos == ',')
    591                 {
    592                     ++m_pos;
    593                     max = read_bound().value_or(ParsedRegex::Quantifier::infinite);
    594                 }
    595                 if (*m_pos++ != '}')
    596                    parse_error("expected closing bracket");
    597                 return {min, max, check_greedy()};
    598             }
    599             default: return {1, 1};
    600         }
    601     }
    602 
    603     NodeIndex add_node(ParsedRegex::Op op, Codepoint value = -1, ParsedRegex::Quantifier quantifier = {1, 1}, bool ignore_case = false)
    604     {
    605         constexpr auto max_nodes = std::numeric_limits<int16_t>::max();
    606         const NodeIndex res = m_parsed_regex.nodes.size();
    607         if (res == max_nodes)
    608             parse_error(format("regex parsed to more than {} ast nodes", max_nodes));
    609         const NodeIndex next = res+1;
    610         m_parsed_regex.nodes.push_back({op, ignore_case or (m_flags & Flags::IgnoreCase), next, value, quantifier});
    611         return res;
    612     }
    613 
    614     ParsedRegex::Node& get_node(NodeIndex index)
    615     {
    616         return m_parsed_regex.nodes[index];
    617     }
    618 
    619     bool at_end() const { return m_pos == m_regex.end(); }
    620 
    621     [[gnu::noreturn]]
    622     void parse_error(StringView error) const
    623     {
    624         throw regex_error(format("regex parse error: {} at '{}<<<HERE>>>{}'", error,
    625                                  StringView{m_regex.begin(), m_pos.base()},
    626                                  StringView{m_pos.base(), m_regex.end()}));
    627     }
    628 
    629     void validate_lookaround(NodeIndex index)
    630     {
    631         using Lookaround = CompiledRegex::Lookaround;
    632         for (auto child_index : Children<>{m_parsed_regex, index})
    633         {
    634             auto& child = get_node(child_index);
    635             if (child.op != ParsedRegex::Literal and child.op != ParsedRegex::CharClass and
    636                 child.op != ParsedRegex::CharType and child.op != ParsedRegex::AnyChar and
    637                 child.op != ParsedRegex::AnyCharExceptNewLine)
    638                 parse_error("Lookaround can only contain literals, any chars or character classes");
    639             if (child.op == ParsedRegex::Literal and
    640                 to_underlying(Lookaround::OpBegin) <= child.value and
    641                 child.value < to_underlying(Lookaround::OpEnd))
    642                 parse_error("Lookaround does not support literals codepoint between 0xF0000 and 0xFFFFD");
    643             if (child.quantifier != ParsedRegex::Quantifier{1, 1})
    644                 parse_error("Quantifiers cannot be used in lookarounds");
    645         }
    646     }
    647 
    648     ParsedRegex m_parsed_regex;
    649     StringView m_regex;
    650     Iterator m_pos;
    651 
    652     Flags m_flags = Flags::DotMatchesNewLine;
    653 
    654     static constexpr struct CharacterClassEscape {
    655         Codepoint cp;
    656         CharacterType ctype;
    657     } character_class_escapes[] = {
    658         { 'd', CharacterType::Digit },                { 'D', CharacterType::NotDigit },
    659         { 'w', CharacterType::Word },                 { 'W', CharacterType::NotWord },
    660         { 's', CharacterType::Whitespace },           { 'S', CharacterType::NotWhitespace },
    661         { 'h', CharacterType::HorizontalWhitespace }, { 'H', CharacterType::NotHorizontalWhitespace },
    662     };
    663 
    664     static constexpr struct ControlEscape {
    665         Codepoint name;
    666         Codepoint value;
    667     } control_escapes[] = {
    668         { 'f', '\f' },
    669         { 'n', '\n' },
    670         { 'r', '\r' },
    671         { 't', '\t' },
    672         { 'v', '\v' }
    673     };
    674 };
    675 
    676 constexpr RegexParser::CharacterClassEscape RegexParser::character_class_escapes[];
    677 constexpr RegexParser::ControlEscape RegexParser::control_escapes[];
    678 
    679 struct RegexCompiler
    680 {
    681     using OpIndex = int16_t;
    682 
    683     RegexCompiler(ParsedRegex&& parsed_regex, RegexCompileFlags flags)
    684         : m_flags(flags), m_parsed_regex{parsed_regex}
    685     {
    686         kak_assert(not (flags & RegexCompileFlags::NoForward) or flags & RegexCompileFlags::Backward);
    687         // Approximation of the number of instructions generated
    688         m_program.instructions.reserve((parsed_regex.nodes.size() + 1)
    689                                        * (((flags & RegexCompileFlags::Backward) and
    690                                            not (flags & RegexCompileFlags::NoForward)) ? 2 : 1));
    691 
    692         if (not (flags & RegexCompileFlags::NoForward))
    693         {
    694             m_program.forward_start_desc = compute_start_desc<RegexMode::Forward>();
    695             compile_node<RegexMode::Forward>(0);
    696             optimize(0, m_program.instructions.size());
    697             push_inst(CompiledRegex::Match);
    698         }
    699 
    700         if (flags & RegexCompileFlags::Backward)
    701         {
    702             m_program.first_backward_inst = m_program.instructions.size();
    703             m_program.backward_start_desc = compute_start_desc<RegexMode::Backward>();
    704             compile_node<RegexMode::Backward>(0);
    705             optimize(m_program.first_backward_inst, m_program.instructions.size());
    706             push_inst(CompiledRegex::Match);
    707         }
    708         else
    709             m_program.first_backward_inst = -1;
    710 
    711         m_program.character_classes = std::move(m_parsed_regex.character_classes);
    712         m_program.named_captures = std::move(m_parsed_regex.named_captures);
    713         m_program.save_count = m_parsed_regex.capture_count * 2;
    714     }
    715 
    716     CompiledRegex get_compiled_regex() { return std::move(m_program); }
    717 
    718 private:
    719 
    720     template<RegexMode direction>
    721     [[gnu::noinline]]
    722     OpIndex compile_node_inner(ParsedRegex::NodeIndex index)
    723     {
    724         auto& node = get_node(index);
    725 
    726         const OpIndex start_pos = op_count();
    727         const bool ignore_case = node.ignore_case;
    728 
    729         const bool save = (node.op == ParsedRegex::Alternation or node.op == ParsedRegex::Sequence) and
    730                           (node.value == 0 or (node.value != -1 and not (m_flags & RegexCompileFlags::NoSubs)));
    731         constexpr bool forward = direction == RegexMode::Forward;
    732         if (save)
    733             push_inst(CompiledRegex::Save, {.save_index = int16_t(node.value * 2 + (forward ? 0 : 1))});
    734 
    735         Vector<uint32_t> goto_inner_end_offsets;
    736         switch (node.op)
    737         {
    738             case ParsedRegex::Literal:
    739                 push_inst(CompiledRegex::Literal, {.literal={.codepoint=ignore_case ? to_lower(node.value) : node.value, .ignore_case=ignore_case}});
    740                 break;
    741             case ParsedRegex::AnyChar:
    742                 push_inst(CompiledRegex::AnyChar);
    743                 break;
    744             case ParsedRegex::AnyCharExceptNewLine:
    745                 push_inst(CompiledRegex::AnyCharExceptNewLine);
    746                 break;
    747             case ParsedRegex::CharClass:
    748                 if (auto& char_class = m_parsed_regex.character_classes[node.value];
    749                     char_class.ranges.size() == 1 and char_class.ctypes == CharacterType::None and
    750                     char_class.ranges[0].max <= std::numeric_limits<uint8_t>::max())
    751                     push_inst(CompiledRegex::CharRange, {.range={.min=uint8_t(char_class.ranges[0].min),
    752                                                                  .max=uint8_t(char_class.ranges[0].max),
    753                                                                  .ignore_case=char_class.ignore_case,
    754                                                                  .negative=char_class.negative}});
    755                 else
    756                     push_inst(CompiledRegex::CharClass, {.character_class_index=int16_t(node.value)});
    757                 break;
    758             case ParsedRegex::CharType:
    759                 push_inst(CompiledRegex::CharType, {.character_type=CharacterType{(unsigned char)node.value}});
    760                 break;
    761             case ParsedRegex::Sequence:
    762             {
    763                 for (auto child : Children<direction>{m_parsed_regex, index})
    764                     compile_node<direction>(child);
    765                 break;
    766             }
    767             case ParsedRegex::Alternation:
    768             {
    769                 for (auto child : Children<>{m_parsed_regex, index})
    770                 {
    771                     if (child != index+1)
    772                         push_inst(CompiledRegex::Split);
    773                 }
    774                 auto split_pos = op_count();
    775 
    776                 const auto end = node.children_end;
    777                 for (auto child : Children<>{m_parsed_regex, index})
    778                 {
    779                     auto node = compile_node<direction>(child);
    780                     if (child != index+1)
    781                     {
    782                         --split_pos;
    783                         m_program.instructions[split_pos].param.split = {.offset = offset(node, split_pos), .prioritize_parent = true};
    784                     }
    785                     if (get_node(child).children_end != end)
    786                     {
    787                         auto jump = push_inst(CompiledRegex::Jump);
    788                         goto_inner_end_offsets.push_back(jump);
    789                     }
    790                 }
    791                 break;
    792             }
    793             case ParsedRegex::LookAhead:
    794             case ParsedRegex::NegativeLookAhead:
    795                 push_inst(CompiledRegex::LookAround, {.lookaround={
    796                     .index=push_lookaround<RegexMode::Forward>(index, ignore_case),
    797                     .ahead=true,
    798                     .positive=node.op == ParsedRegex::LookAhead,
    799                     .ignore_case=ignore_case}});
    800                 break;
    801             case ParsedRegex::LookBehind:
    802             case ParsedRegex::NegativeLookBehind:
    803                 push_inst(CompiledRegex::LookAround, {.lookaround={
    804                     .index=push_lookaround<RegexMode::Backward>(index, ignore_case),
    805                     .ahead=false,
    806                     .positive=node.op == ParsedRegex::LookBehind,
    807                     .ignore_case=ignore_case}});
    808                 break;
    809             case ParsedRegex::LineStart:
    810                 push_inst(CompiledRegex::LineAssertion, {.line_start=true});
    811                 break;
    812             case ParsedRegex::LineEnd:
    813                 push_inst(CompiledRegex::LineAssertion, {.line_start=false});
    814                 break;
    815             case ParsedRegex::WordBoundary:
    816                 push_inst(CompiledRegex::WordBoundary, {.word_boundary_positive=true});
    817                 break;
    818             case ParsedRegex::NotWordBoundary:
    819                 push_inst(CompiledRegex::WordBoundary, {.word_boundary_positive=false});
    820                 break;
    821             case ParsedRegex::SubjectBegin:
    822                 push_inst(CompiledRegex::SubjectAssertion, {.subject_begin=true});
    823                 break;
    824             case ParsedRegex::SubjectEnd:
    825                 push_inst(CompiledRegex::SubjectAssertion, {.subject_begin=false});
    826                 break;
    827             case ParsedRegex::ResetStart:
    828                 push_inst(CompiledRegex::Save, {.save_index=0});
    829                 break;
    830         }
    831 
    832         for (auto& index : goto_inner_end_offsets)
    833             m_program.instructions[index].param.jump_offset = offset(op_count(), index);
    834 
    835         if (save)
    836             push_inst(CompiledRegex::Save, {.save_index=int16_t(node.value * 2 + (forward ? 1 : 0))});
    837 
    838         return start_pos;
    839     }
    840 
    841     OpIndex op_count() const
    842     {
    843         return static_cast<OpIndex>(m_program.instructions.size());
    844     }
    845 
    846     static OpIndex offset(OpIndex to, OpIndex from)
    847     {
    848         return static_cast<OpIndex>(to - from);
    849     }
    850 
    851     template<RegexMode direction>
    852     OpIndex compile_node(ParsedRegex::NodeIndex index)
    853     {
    854         auto& node = get_node(index);
    855 
    856         const OpIndex start_pos = op_count();
    857         Vector<OpIndex> goto_ends;
    858 
    859         auto& quantifier = node.quantifier;
    860 
    861         if (quantifier.allows_none())
    862         {
    863             auto split_pos = push_inst(CompiledRegex::Split, {.split={.offset=0, .prioritize_parent=quantifier.greedy}});
    864             goto_ends.push_back(split_pos);
    865         }
    866 
    867         auto inner_pos = compile_node_inner<direction>(index);
    868         // Write the node multiple times when we have a min count quantifier
    869         for (int i = 1; i < quantifier.min; ++i)
    870             inner_pos = compile_node_inner<direction>(index);
    871 
    872         if (quantifier.allows_infinite_repeat())
    873             push_inst(CompiledRegex::Split, {.split = {.offset=offset(inner_pos, op_count()), .prioritize_parent=not quantifier.greedy}});
    874         // Write the node as an optional match for the min -> max counts
    875         else for (int i = std::max((int16_t)1, quantifier.min); // STILL UGLY !
    876                   i < quantifier.max; ++i)
    877         {
    878             auto split_pos = push_inst(CompiledRegex::Split, {.split={.offset=0, .prioritize_parent=quantifier.greedy}});
    879             goto_ends.push_back(split_pos);
    880             compile_node_inner<direction>(index);
    881         }
    882 
    883         for (auto index : goto_ends)
    884             m_program.instructions[index].param.split.offset = offset(op_count(), index);
    885 
    886         return start_pos;
    887     }
    888 
    889     OpIndex push_inst(CompiledRegex::Op op, CompiledRegex::Param param = {})
    890     {
    891         constexpr auto max_instructions = std::numeric_limits<OpIndex>::max();
    892         const auto res = op_count();
    893         if (res >= max_instructions)
    894             throw regex_error(format("regex compiled to more than {} instructions", max_instructions));
    895         m_program.instructions.push_back({ op, 0, param });
    896         return OpIndex(res);
    897     }
    898 
    899     template<RegexMode direction>
    900     int16_t push_lookaround(ParsedRegex::NodeIndex index, bool ignore_case)
    901     {
    902         using Lookaround = CompiledRegex::Lookaround;
    903 
    904         const int16_t res = m_program.lookarounds.size();
    905         for (auto child : Children<direction>{m_parsed_regex, index})
    906         {
    907             auto& character = get_node(child);
    908             if (character.op == ParsedRegex::Literal)
    909                 m_program.lookarounds.push_back(
    910                     static_cast<Lookaround>(ignore_case ? to_lower(character.value) : character.value));
    911             else if (character.op == ParsedRegex::AnyChar)
    912                 m_program.lookarounds.push_back(Lookaround::AnyChar);
    913             else if (character.op == ParsedRegex::AnyCharExceptNewLine)
    914                 m_program.lookarounds.push_back(Lookaround::AnyCharExceptNewLine);
    915             else if (character.op == ParsedRegex::CharClass)
    916                 m_program.lookarounds.push_back(static_cast<Lookaround>(to_underlying(Lookaround::CharacterClass) + character.value));
    917             else if (character.op == ParsedRegex::CharType)
    918                 m_program.lookarounds.push_back(static_cast<Lookaround>(to_underlying(Lookaround::CharacterType) | character.value));
    919             else
    920                 kak_assert(false);
    921         }
    922         m_program.lookarounds.push_back(Lookaround::EndOfLookaround);
    923         return res;
    924     }
    925 
    926     // Mutate start_desc with informations on which Codepoint could start a match.
    927     // Returns true if the subsequent nodes are still relevant for computing the
    928     // start desc
    929     template<RegexMode direction>
    930     bool compute_start_desc(ParsedRegex::NodeIndex index,
    931                              CompiledRegex::StartDesc& start_desc) const
    932     {
    933         // fill all bytes that mark the start of an utf8 multi byte sequence
    934         auto add_multi_byte_utf8 = [&] {
    935             std::fill(start_desc.map + 0b11000000, start_desc.map + 0b11111000, true);
    936         };
    937         static constexpr Codepoint single_byte_limit = 128;
    938 
    939         auto& node = get_node(index);
    940         switch (node.op)
    941         {
    942             case ParsedRegex::Literal:
    943                 if (node.value < single_byte_limit)
    944                 {
    945                     if (node.ignore_case)
    946                     {
    947                         start_desc.map[to_lower(node.value)] = true;
    948                         start_desc.map[to_upper(node.value)] = true;
    949                     }
    950                     else
    951                         start_desc.map[node.value] = true;
    952                 }
    953                 else
    954                     add_multi_byte_utf8();
    955                 return node.quantifier.allows_none();
    956             case ParsedRegex::AnyChar:
    957                 if (start_desc.offset + node.quantifier.max <= CompiledRegex::StartDesc::OffsetLimits::max())
    958                 {
    959                     start_desc.offset += node.quantifier.max;
    960                     return true;
    961                 }
    962                 for (auto& b : start_desc.map)
    963                     b = true;
    964                return node.quantifier.allows_none();
    965             case ParsedRegex::AnyCharExceptNewLine:
    966                 if (start_desc.offset + node.quantifier.max <= CompiledRegex::StartDesc::OffsetLimits::max())
    967                 {
    968                     start_desc.offset += node.quantifier.max;
    969                     return true;
    970                 }
    971                 for (Codepoint cp = 0; cp < single_byte_limit; ++cp)
    972                 {
    973                     if (cp != '\n')
    974                         start_desc.map[cp] = true;
    975                 }
    976                return node.quantifier.allows_none();
    977             case ParsedRegex::CharClass:
    978             {
    979                 auto& character_class = m_parsed_regex.character_classes[node.value];
    980                 if (character_class.ctypes == CharacterType::None and
    981                     not character_class.negative and
    982                     not character_class.ignore_case)
    983                 {
    984                     for (auto& range : character_class.ranges)
    985                     {
    986                         const auto clamp = [](Codepoint cp) { return std::min(single_byte_limit, cp); };
    987                         for (auto cp = clamp(range.min), end = clamp(range.max + 1); cp < end; ++cp)
    988                             start_desc.map[cp] = true;
    989                         if (range.max >= single_byte_limit)
    990                             add_multi_byte_utf8();
    991                     }
    992                 }
    993                 else
    994                 {
    995                     for (Codepoint cp = 0; cp < single_byte_limit; ++cp)
    996                     {
    997                         if (start_desc.map[cp] or character_class.matches(cp))
    998                             start_desc.map[cp] = true;
    999                     }
   1000                 }
   1001                 add_multi_byte_utf8();
   1002                 return node.quantifier.allows_none();
   1003             }
   1004             case ParsedRegex::CharType:
   1005             {
   1006                 const CharacterType ctype = (CharacterType)node.value;
   1007                 for (Codepoint cp = 0; cp < single_byte_limit; ++cp)
   1008                 {
   1009                     if (is_ctype(ctype, cp))
   1010                         start_desc.map[cp] = true;
   1011                 }
   1012                 add_multi_byte_utf8();
   1013                 return node.quantifier.allows_none();
   1014             }
   1015             case ParsedRegex::Sequence:
   1016             {
   1017                 for (auto child : Children<direction>{m_parsed_regex, index})
   1018                 {
   1019                     if (not compute_start_desc<direction>(child, start_desc))
   1020                         return node.quantifier.allows_none();
   1021                 }
   1022                 return true;
   1023             }
   1024             case ParsedRegex::Alternation:
   1025             {
   1026                 bool all_consumed = not node.quantifier.allows_none();
   1027                 for (auto child : Children<>{m_parsed_regex, index})
   1028                 {
   1029                     if (compute_start_desc<direction>(child, start_desc))
   1030                         all_consumed = false;
   1031                 }
   1032                 return not all_consumed;
   1033             }
   1034             case ParsedRegex::LineStart:
   1035             case ParsedRegex::LineEnd:
   1036             case ParsedRegex::WordBoundary:
   1037             case ParsedRegex::NotWordBoundary:
   1038             case ParsedRegex::SubjectBegin:
   1039             case ParsedRegex::SubjectEnd:
   1040             case ParsedRegex::ResetStart:
   1041             case ParsedRegex::LookAhead:
   1042             case ParsedRegex::LookBehind:
   1043             case ParsedRegex::NegativeLookAhead:
   1044             case ParsedRegex::NegativeLookBehind:
   1045                 return true;
   1046         }
   1047         return false;
   1048     }
   1049 
   1050     template<RegexMode direction>
   1051     [[gnu::noinline]]
   1052     UniquePtr<CompiledRegex::StartDesc> compute_start_desc() const
   1053     {
   1054         CompiledRegex::StartDesc start_desc{};
   1055         if (compute_start_desc<direction>(0, start_desc) or
   1056             not contains(start_desc.map, false))
   1057             return nullptr;
   1058 
   1059         if (std::count(std::begin(start_desc.map), std::end(start_desc.map), true) == 1)
   1060             start_desc.start_byte = find(start_desc.map, true) - std::begin(start_desc.map);
   1061 
   1062         return make_unique_ptr<CompiledRegex::StartDesc>(start_desc);
   1063     }
   1064 
   1065     void optimize(size_t begin, size_t end)
   1066     {
   1067         if (not (m_flags & RegexCompileFlags::Optimize))
   1068             return;
   1069 
   1070         auto is_jump = [](CompiledRegex::Op op) { return op >= CompiledRegex::Op::Jump and op <= CompiledRegex::Op::Split; };
   1071         for (auto i = begin; i < end; ++i)
   1072         {
   1073             auto& inst = m_program.instructions[i];
   1074             if (is_jump(inst.op))
   1075                 m_program.instructions[i + inst.param.jump_offset].last_step = 0xffff; // tag as jump target
   1076         }
   1077 
   1078         for (auto block_begin = begin; block_begin < end; )
   1079         {
   1080             auto block_end = block_begin + 1;
   1081             while (block_end < end and
   1082                    not is_jump(m_program.instructions[block_end].op) and
   1083                    m_program.instructions[block_end].last_step != 0xffff)
   1084                 ++block_end;
   1085             peephole_optimize(block_begin, block_end);
   1086             block_begin = block_end;
   1087         }
   1088     }
   1089 
   1090     void peephole_optimize(size_t begin, size_t end)
   1091     {
   1092         // Move saves after all assertions on the same character
   1093         auto is_assertion = [](CompiledRegex::Op op) { return op >= CompiledRegex::LineAssertion; };
   1094         for (auto i = begin, j = begin + 1; j < end; ++i, ++j)
   1095         {
   1096             if (m_program.instructions[i].op == CompiledRegex::Save and
   1097                 is_assertion(m_program.instructions[j].op))
   1098                 std::swap(m_program.instructions[i], m_program.instructions[j]);
   1099         }
   1100     }
   1101 
   1102     const ParsedRegex::Node& get_node(ParsedRegex::NodeIndex index) const
   1103     {
   1104         return m_parsed_regex.nodes[index];
   1105     }
   1106 
   1107     CompiledRegex m_program;
   1108     RegexCompileFlags m_flags;
   1109     ParsedRegex& m_parsed_regex;
   1110 };
   1111 
   1112 }
   1113 
   1114 String dump_regex(const CompiledRegex& program)
   1115 {
   1116     String res;
   1117     int index = 0;
   1118     for (auto& inst : program.instructions)
   1119     {
   1120         char buf[20];
   1121         format_to(buf, " {:03}     ", index);
   1122         res += buf;
   1123         switch (inst.op)
   1124         {
   1125             case CompiledRegex::Literal:
   1126                 res += format("literal {}{}\n", inst.param.literal.ignore_case ? "(ignore case) " : "", inst.param.literal.codepoint);
   1127                 break;
   1128             case CompiledRegex::AnyChar:
   1129                 res += "any char\n";
   1130                 break;
   1131             case CompiledRegex::AnyCharExceptNewLine:
   1132                 res += "anything but newline\n";
   1133                 break;
   1134             case CompiledRegex::CharRange:
   1135                 res += format("character range {}[{}{}-{}]\n",
   1136                               inst.param.range.ignore_case ? "(ignore case) " : "",
   1137                               inst.param.range.negative ? "^" : "",
   1138                               inst.param.range.min, inst.param.range.max);
   1139                 break;
   1140             case CompiledRegex::CharType:
   1141                 res += format("character type {}\n", to_underlying(inst.param.character_type));
   1142                 break;
   1143             case CompiledRegex::CharClass:
   1144                 res += format("character class {}\n", inst.param.character_class_index);
   1145                 break;
   1146             case CompiledRegex::Jump:
   1147                 res += format("jump {} ({:03})\n", inst.param.jump_offset, index + inst.param.jump_offset);
   1148                 break;
   1149             case CompiledRegex::Split:
   1150             {
   1151                 res += format("split (prioritize {}) {} ({:03})\n",
   1152                               (inst.param.split.prioritize_parent) ? "parent" : "child",
   1153                               inst.param.split.offset, index + inst.param.split.offset);
   1154                 break;
   1155             }
   1156             case CompiledRegex::Save:
   1157                 res += format("save {}\n", inst.param.save_index);
   1158                 break;
   1159             case CompiledRegex::LineAssertion:
   1160                 res += format("line {}\n", inst.param.line_start ? "start" : "end");;
   1161                 break;
   1162             case CompiledRegex::SubjectAssertion:
   1163                 res += format("subject {}\n", inst.param.subject_begin ? "begin" : "end");
   1164                 break;
   1165             case CompiledRegex::WordBoundary:
   1166                 res += format("{}word boundary\n", inst.param.word_boundary_positive ? "" : "not ");
   1167                 break;
   1168             case CompiledRegex::LookAround:
   1169             {
   1170                 String name;
   1171                 name += inst.param.lookaround.positive ? "" : "negative ";
   1172                 name += "look ";
   1173                 name += inst.param.lookaround.ahead ? "ahead " : "behind ";
   1174                 if (inst.param.lookaround.ignore_case)
   1175                     name += " (ignore case)";
   1176 
   1177                 String str;
   1178                 for (auto it = program.lookarounds.begin() + inst.param.lookaround.index;
   1179                      *it != CompiledRegex::Lookaround::EndOfLookaround; ++it)
   1180                     utf8::dump(std::back_inserter(str), to_underlying(*it));
   1181                 res += format("{} ({})\n", name, str);
   1182                 break;
   1183             }
   1184             case CompiledRegex::Match:
   1185                 res += "match\n";
   1186         }
   1187         ++index;
   1188     }
   1189     auto dump_start_desc = [&](const CompiledRegex::StartDesc& desc, StringView name) {
   1190         res += name + " start desc: [";
   1191         for (size_t c = 0; c < CompiledRegex::StartDesc::count; ++c)
   1192         {
   1193             if (desc.map[c])
   1194             {
   1195                 if (c < 32)
   1196                     res += format("<0x{}>", hex(c));
   1197                 else
   1198                     res += (char)c;
   1199             }
   1200         }
   1201         res += format("]+{}\n", static_cast<int>(desc.offset));
   1202     };
   1203     if (program.forward_start_desc)
   1204         dump_start_desc(*program.forward_start_desc, "forward");
   1205     if (program.backward_start_desc)
   1206         dump_start_desc(*program.backward_start_desc, "backward");
   1207     return res;
   1208 }
   1209 
   1210 CompiledRegex compile_regex(StringView re, RegexCompileFlags flags)
   1211 {
   1212     return RegexCompiler{RegexParser::parse(re), flags}.get_compiled_regex();
   1213 }
   1214 
   1215 bool is_ctype(CharacterType ctype, Codepoint cp)
   1216 {
   1217     auto check = [&](CharacterType bit, CharacterType not_bit, auto&& func) {
   1218         return (ctype & (bit | not_bit)) and func(cp) == (bool)(ctype & bit);
   1219     };
   1220     return check(CharacterType::Word, CharacterType::NotWord, [](Codepoint cp) { return is_word(cp); }) or
   1221            check(CharacterType::Whitespace, CharacterType::NotWhitespace, is_blank) or
   1222            check(CharacterType::HorizontalWhitespace, CharacterType::NotHorizontalWhitespace, is_horizontal_blank) or
   1223            check(CharacterType::Digit, CharacterType::NotDigit, iswdigit);
   1224 }
   1225 
   1226 namespace
   1227 {
   1228 template<RegexMode mode = RegexMode::Forward>
   1229 struct TestVM : CompiledRegex, ThreadedRegexVM<const char*, mode>
   1230 {
   1231     TestVM(StringView re)
   1232       : CompiledRegex{compile_regex(re, mode & RegexMode::Forward ? RegexCompileFlags::None : RegexCompileFlags::Backward)},
   1233         TestVM::ThreadedRegexVM{static_cast<const CompiledRegex&>(*this)}
   1234     {}
   1235 
   1236     bool exec(StringView re, RegexExecFlags flags = RegexExecFlags::None)
   1237     {
   1238         return TestVM::ThreadedRegexVM::exec(re.begin(), re.end(), re.begin(), re.end(), flags);
   1239     }
   1240 
   1241     using TestVM::ThreadedRegexVM::exec;
   1242 };
   1243 }
   1244 
   1245 auto test_regex = UnitTest{[]{
   1246     {
   1247         TestVM<> vm{R"(a*b)"};
   1248         kak_assert(vm.exec("b"));
   1249         kak_assert(vm.exec("ab"));
   1250         kak_assert(vm.exec("aaab"));
   1251         kak_assert(not vm.exec("acb"));
   1252         kak_assert(not vm.exec("abc"));
   1253         kak_assert(not vm.exec(""));
   1254     }
   1255 
   1256     {
   1257         TestVM<> vm{R"(^a.*b$)"};
   1258         kak_assert(vm.exec("afoob"));
   1259         kak_assert(vm.exec("ab"));
   1260         kak_assert(not vm.exec("bab"));
   1261         kak_assert(not vm.exec(""));
   1262     }
   1263 
   1264     {
   1265         TestVM<> vm{R"(^(foo|qux|baz)+(bar)?baz$)"};
   1266         kak_assert(vm.exec("fooquxbarbaz"));
   1267         kak_assert(StringView{vm.captures()[2], vm.captures()[3]} == "qux");
   1268         kak_assert(not vm.exec("fooquxbarbaze"));
   1269         kak_assert(not vm.exec("quxbar"));
   1270         kak_assert(not vm.exec("blahblah"));
   1271         kak_assert(vm.exec("bazbaz"));
   1272         kak_assert(vm.exec("quxbaz"));
   1273     }
   1274 
   1275     {
   1276         TestVM<> vm{R"(.*\b(foo|bar)\b.*)"};
   1277         kak_assert(vm.exec("qux foo baz"));
   1278         kak_assert(StringView{vm.captures()[2], vm.captures()[3]} == "foo");
   1279         kak_assert(not vm.exec("quxfoobaz"));
   1280         kak_assert(vm.exec("bar"));
   1281         kak_assert(not vm.exec("foobar"));
   1282     }
   1283 
   1284     {
   1285         TestVM<> vm{R"((foo|bar))"};
   1286         kak_assert(vm.exec("foo"));
   1287         kak_assert(vm.exec("bar"));
   1288         kak_assert(not vm.exec("foobar"));
   1289     }
   1290 
   1291     {
   1292         TestVM<> vm{R"([aA])"};
   1293         kak_assert(vm.exec("a"));
   1294         kak_assert(vm.exec("A"));
   1295     }
   1296 
   1297     {
   1298         TestVM<> vm{R"(a{3,5}b)"};
   1299         kak_assert(not vm.exec("aab"));
   1300         kak_assert(vm.exec("aaab"));
   1301         kak_assert(not vm.exec("aaaaaab"));
   1302         kak_assert(vm.exec("aaaaab"));
   1303     }
   1304 
   1305     {
   1306         TestVM<> vm{R"(a{3}b)"};
   1307         kak_assert(not vm.exec("aab"));
   1308         kak_assert(vm.exec("aaab"));
   1309         kak_assert(not vm.exec("aaaab"));
   1310     }
   1311 
   1312     {
   1313         TestVM<> vm{R"(a{3,}b)"};
   1314         kak_assert(not vm.exec("aab"));
   1315         kak_assert(vm.exec("aaab"));
   1316         kak_assert(vm.exec("aaaaab"));
   1317     }
   1318 
   1319     {
   1320         TestVM<> vm{R"(a{,3}b)"};
   1321         kak_assert(vm.exec("b"));
   1322         kak_assert(vm.exec("ab"));
   1323         kak_assert(vm.exec("aaab"));
   1324         kak_assert(not vm.exec("aaaab"));
   1325     }
   1326 
   1327     {
   1328         TestVM<RegexMode::Forward | RegexMode::Search> vm{R"(f.*a(.*o))"};
   1329         kak_assert(vm.exec("blahfoobarfoobaz"));
   1330         kak_assert(StringView{vm.captures()[0], vm.captures()[1]} == "foobarfoo");
   1331         kak_assert(StringView{vm.captures()[2], vm.captures()[3]} == "rfoo");
   1332         kak_assert(vm.exec("mais que fais la police"));
   1333         kak_assert(StringView{vm.captures()[0], vm.captures()[1]} == "fais la po");
   1334         kak_assert(StringView{vm.captures()[2], vm.captures()[3]} == " po");
   1335     }
   1336 
   1337     {
   1338         TestVM<> vm{R"([àb-dX-Z-]{3,5})"};
   1339         kak_assert(vm.exec("cà-Y"));
   1340         kak_assert(not vm.exec("àeY"));
   1341         kak_assert(vm.exec("dcbàX"));
   1342         kak_assert(not vm.exec("efg"));
   1343     }
   1344 
   1345     {
   1346         TestVM<> vm{R"((a{3,5})a+)"};
   1347         kak_assert(vm.exec("aaaaaa", RegexExecFlags::None));
   1348         kak_assert(StringView{vm.captures()[2], vm.captures()[3]} == "aaaaa");
   1349     }
   1350 
   1351     {
   1352         TestVM<> vm{R"((a{3,5}?)a+)"};
   1353         kak_assert(vm.exec("aaaaaa", RegexExecFlags::None));
   1354         kak_assert(StringView{vm.captures()[2], vm.captures()[3]} == "aaa");
   1355     }
   1356 
   1357     {
   1358         TestVM<> vm{R"((a{3,5}?)a)"};
   1359         kak_assert(vm.exec("aaaa"));
   1360     }
   1361 
   1362     {
   1363         TestVM<> vm{R"(\d{3})"};
   1364         kak_assert(vm.exec("123"));
   1365         kak_assert(not vm.exec("1x3"));
   1366     }
   1367 
   1368     {
   1369         TestVM<> vm{R"([-\d]+)"};
   1370         kak_assert(vm.exec("123-456"));
   1371         kak_assert(not vm.exec("123_456"));
   1372     }
   1373 
   1374     {
   1375         TestVM<> vm{R"([ \H]+)"};
   1376         kak_assert(vm.exec("abc "));
   1377         kak_assert(not vm.exec("a \t"));
   1378     }
   1379 
   1380     {
   1381         TestVM<> vm{R"(\Q{}[]*+?\Ea+)"};
   1382         kak_assert(vm.exec("{}[]*+?aa"));
   1383     }
   1384 
   1385     {
   1386         TestVM<> vm{R"(\Q...)"};
   1387         kak_assert(vm.exec("..."));
   1388         kak_assert(not vm.exec("bla"));
   1389     }
   1390 
   1391     {
   1392         TestVM<RegexMode::Forward> vm{R"(foo\Kbar)"};
   1393         kak_assert(vm.exec("foobar"));
   1394         kak_assert(StringView{vm.captures()[0], vm.captures()[1]} == "bar");
   1395         kak_assert(not vm.exec("bar"));
   1396     }
   1397     {
   1398         TestVM<RegexMode::Forward | RegexMode::Search> vm{R"(foobaz|foo|foobar)"};
   1399         kak_assert(vm.exec("foobar"));
   1400         kak_assert(StringView{vm.captures()[0], vm.captures()[1]} == "foo");
   1401     }
   1402     {
   1403         TestVM<RegexMode::Forward> vm{R"((fo+?).*)"};
   1404         kak_assert(vm.exec("foooo"));
   1405         kak_assert(StringView{vm.captures()[2], vm.captures()[3]} == "fo");
   1406     }
   1407 
   1408     {
   1409         TestVM<RegexMode::Forward | RegexMode::Search> vm{R"((?=fo[\w]).)"};
   1410         kak_assert(vm.exec("barfoo"));
   1411         kak_assert(StringView{vm.captures()[0], vm.captures()[1]} == "f");
   1412     }
   1413 
   1414     {
   1415         TestVM<> vm{R"((?<!f).)"};
   1416         kak_assert(vm.exec("f"));
   1417     }
   1418 
   1419     {
   1420         TestVM<> vm{R"((?!f[oa]o)...)"};
   1421         kak_assert(not vm.exec("foo"));
   1422         kak_assert(vm.exec("qux"));
   1423     }
   1424 
   1425     {
   1426         TestVM<> vm{R"(...(?<=f\w.))"};
   1427         kak_assert(vm.exec("foo"));
   1428         kak_assert(not vm.exec("qux"));
   1429     }
   1430 
   1431     {
   1432         TestVM<> vm{R"(...(?<!foo))"};
   1433         kak_assert(not vm.exec("foo"));
   1434         kak_assert(vm.exec("qux"));
   1435     }
   1436 
   1437     {
   1438         TestVM<> vm{R"(Foo(?i)f[oB]+)"};
   1439         kak_assert(vm.exec("FooFOoBb"));
   1440     }
   1441 
   1442     {
   1443         TestVM<> vm{R"((?i)[a-z]+)"};
   1444         kak_assert(vm.exec("ABC"));
   1445     }
   1446 
   1447     {
   1448         TestVM<> vm{R"([^\]]+)"};
   1449         kak_assert(not vm.exec("a]c"));
   1450         kak_assert(vm.exec("abc"));
   1451     }
   1452 
   1453     {
   1454         TestVM<> vm{R"([^:\n]+)"};
   1455         kak_assert(not vm.exec("\nbc"));
   1456         kak_assert(vm.exec("abc"));
   1457     }
   1458 
   1459     {
   1460         TestVM<> vm{R"((?:foo)+)"};
   1461         kak_assert(vm.exec("foofoofoo"));
   1462         kak_assert(not vm.exec("barbarbar"));
   1463     }
   1464 
   1465     {
   1466         TestVM<RegexMode::Forward | RegexMode::Search> vm{R"((?<!\\)(?:\\\\)*")"};
   1467         kak_assert(vm.exec("foo\""));
   1468     }
   1469 
   1470     {
   1471         TestVM<RegexMode::Forward | RegexMode::Search> vm{R"($)"};
   1472         kak_assert(vm.exec("foo\n"));
   1473         kak_assert(*vm.captures()[0] == '\n');
   1474     }
   1475 
   1476     {
   1477         TestVM<RegexMode::Backward | RegexMode::Search> vm{R"(fo{1,})"};
   1478         kak_assert(vm.exec("foo1fooo2"));
   1479         kak_assert(*vm.captures()[1] == '2');
   1480     }
   1481 
   1482     {
   1483         TestVM<RegexMode::Backward | RegexMode::Search> vm{R"((?<=f)oo(b[ae]r)?(?=baz))"};
   1484         kak_assert(vm.exec("foobarbazfoobazfooberbaz"));
   1485         kak_assert(StringView{vm.captures()[0], vm.captures()[1]}  == "oober");
   1486         kak_assert(StringView{vm.captures()[2], vm.captures()[3]}  == "ber");
   1487     }
   1488 
   1489     {
   1490         TestVM<RegexMode::Backward | RegexMode::Search> vm{R"((baz|boz|foo|qux)(?<!baz)(?<!o))"};
   1491         kak_assert(vm.exec("quxbozfoobaz"));
   1492         kak_assert(StringView{vm.captures()[0], vm.captures()[1]}  == "boz");
   1493     }
   1494 
   1495     {
   1496         TestVM<RegexMode::Backward | RegexMode::Search> vm{R"(foo)"};
   1497         kak_assert(vm.exec("foofoo"));
   1498         kak_assert(*vm.captures()[1]  == 0);
   1499     }
   1500 
   1501     {
   1502         TestVM<RegexMode::Backward | RegexMode::Search> vm{R"($)"};
   1503         kak_assert(vm.exec("foo\nbar\nbaz\nqux", RegexExecFlags::NotEndOfLine));
   1504         kak_assert(StringView{vm.captures()[0]}  == "\nqux");
   1505         kak_assert(vm.exec("foo\nbar\nbaz\nqux", RegexExecFlags::None));
   1506         kak_assert(StringView{vm.captures()[0]}  == "");
   1507     }
   1508 
   1509     {
   1510         TestVM<RegexMode::Backward | RegexMode::Search> vm{R"(^)"};
   1511         kak_assert(not vm.exec("foo", RegexExecFlags::NotBeginOfLine));
   1512         kak_assert(vm.exec("foo", RegexExecFlags::None));
   1513         kak_assert(vm.exec("foo\nbar", RegexExecFlags::None));
   1514         kak_assert(StringView{vm.captures()[0]}  == "bar");
   1515     }
   1516 
   1517     {
   1518         TestVM<RegexMode::Backward | RegexMode::Search> vm{R"(\A\w+)"};
   1519         kak_assert(vm.exec("foo\nbar\nbaz", RegexExecFlags::None));
   1520         kak_assert(StringView{vm.captures()[0], vm.captures()[1]}  == "foo");
   1521     }
   1522 
   1523     {
   1524         TestVM<RegexMode::Backward | RegexMode::Search> vm{R"(\b\w+\z)"};
   1525         kak_assert(vm.exec("foo\nbar\nbaz", RegexExecFlags::None));
   1526         kak_assert(StringView{vm.captures()[0], vm.captures()[1]}  == "baz");
   1527     }
   1528 
   1529     {
   1530         TestVM<RegexMode::Backward | RegexMode::Search> vm{R"(a[^\n]*\n|\n)"};
   1531         kak_assert(vm.exec("foo\nbar\nb", RegexExecFlags::None));
   1532         kak_assert(StringView{vm.captures()[0], vm.captures()[1]}  == "ar\n");
   1533     }
   1534 
   1535     {
   1536         TestVM<> vm{R"(()*)"};
   1537         kak_assert(not vm.exec(" "));
   1538     }
   1539 
   1540     {
   1541         TestVM<RegexMode::Forward | RegexMode::Search> vm{R"(\b(?<!-)(a|b|)(?!-)\b)"};
   1542         kak_assert(vm.exec("# foo bar", RegexExecFlags::None));
   1543         kak_assert(*vm.captures()[0] == '#');
   1544     }
   1545 
   1546     {
   1547         TestVM<> vm{R"((?=))"};
   1548         kak_assert(vm.exec(""));
   1549     }
   1550 
   1551     {
   1552         TestVM<RegexMode::Forward | RegexMode::Search> vm{R"((?i)FOO)"};
   1553         kak_assert(vm.exec("foo", RegexExecFlags::None));
   1554     }
   1555 
   1556     {
   1557         TestVM<RegexMode::Forward | RegexMode::Search> vm{R"(.?(?=foo))"};
   1558         kak_assert(vm.exec("afoo", RegexExecFlags::None));
   1559         kak_assert(*vm.captures()[0] == 'a');
   1560     }
   1561 
   1562     {
   1563         TestVM<RegexMode::Forward | RegexMode::Search> vm{R"((?i)(?=Foo))"};
   1564         kak_assert(vm.exec("fOO", RegexExecFlags::None));
   1565         kak_assert(*vm.captures()[0] == 'f');
   1566     }
   1567 
   1568     {
   1569         TestVM<> vm{R"(a(?<=\N)\N+(?=.\N)\s(?S)d.+(?!.)\s(?<!\N)g)"};
   1570         kak_assert(vm.exec("abc\ndef\ng"));
   1571         kak_assert(not vm.exec("abc\ndef g"));
   1572     }
   1573 
   1574     {
   1575         TestVM<> vm{R"([d-ea-dcf-k]+)"};
   1576         kak_assert(vm.exec("abcde"));
   1577     }
   1578 
   1579     {
   1580         TestVM<> vm{R"((?i)[a-c]+)"};
   1581         kak_assert(vm.exec("bCa"));
   1582     }
   1583 
   1584     {
   1585         TestVM<> vm{R"([\t-\r]+)"};
   1586         kak_assert(vm.exec("\t\n\v\f\r"));
   1587     }
   1588 
   1589     {
   1590         TestVM<> vm{R"([\t-\r]\h+[\t-\r])"};
   1591         kak_assert(vm.character_classes.size() == 1);
   1592         kak_assert(vm.exec("\n  \f"));
   1593     }
   1594 
   1595     {
   1596         TestVM<> vm{R"([^\x00-\x7F]+)"};
   1597         kak_assert(not vm.exec("ascii"));
   1598         kak_assert(vm.exec("←↑→↓"));
   1599         kak_assert(vm.exec("😄😊😉"));
   1600     }
   1601 
   1602     {
   1603         TestVM<> vm{R"([^\u000000-\u00ffff]+)"};
   1604         kak_assert(not vm.exec("ascii"));
   1605         kak_assert(not vm.exec("←↑→↓"));
   1606         kak_assert(vm.exec("😄😊😉"));
   1607     }
   1608 
   1609     {
   1610         TestVM<RegexMode::Forward | RegexMode::Search> vm{R"(д)"};
   1611         kak_assert(vm.exec("д", RegexExecFlags::None));
   1612     }
   1613 
   1614     {
   1615         TestVM<RegexMode::Forward | RegexMode::Search> vm{"ab"};
   1616         const char str[] = "fa😄ab";
   1617         kak_assert(not vm.exec(str, str+4, str, str + sizeof(str)-1, RegexExecFlags::None));
   1618     }
   1619 
   1620     {
   1621         TestVM<> vm{R"(\0\x0A\u00260e\u00260F)"};
   1622         const char str[] = "\0\n☎☏"; // work around the null byte in the literal
   1623         kak_assert(vm.exec({str, str + sizeof(str)-1}));
   1624     }
   1625 
   1626     {
   1627         TestVM<RegexMode::Forward | RegexMode::Search> vm{".{40}"};
   1628         kak_assert(vm.exec("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx", RegexExecFlags::None));
   1629     }
   1630 
   1631     {
   1632         TestVM<RegexMode::Forward | RegexMode::Search> vm{"(.{3,4}|f)oo"};
   1633         kak_assert(vm.forward_start_desc and vm.forward_start_desc->offset == 4);
   1634         for (int c = 0; c < CompiledRegex::StartDesc::count; ++c)
   1635             kak_assert(vm.forward_start_desc->map[c] == (c == 'f' or c == 'o'));
   1636 
   1637         kak_assert(vm.exec("xxxoo", RegexExecFlags::None));
   1638         kak_assert(vm.exec("xfoo", RegexExecFlags::None));
   1639         kak_assert(not vm.exec("😄xoo", RegexExecFlags::None));
   1640     }
   1641 
   1642     {
   1643         TestVM<RegexMode::Backward | RegexMode::Search> vm{"oo(.{3,4}|f)"};
   1644         kak_assert(vm.backward_start_desc and vm.backward_start_desc->offset == 4);
   1645         for (int c = 0; c < CompiledRegex::StartDesc::count; ++c)
   1646             kak_assert(vm.backward_start_desc->map[c] == (c == 'f' or c == 'o'));
   1647 
   1648         kak_assert(vm.exec("ooxxx", RegexExecFlags::None));
   1649         kak_assert(vm.exec("oofx", RegexExecFlags::None));
   1650         kak_assert(not vm.exec("oox😄", RegexExecFlags::None));
   1651     }
   1652 
   1653     {
   1654         auto eq = [](const CompiledRegex::NamedCapture& lhs,
   1655                      const CompiledRegex::NamedCapture& rhs) {
   1656             return lhs.name == rhs.name and
   1657                    lhs.index == rhs.index;
   1658         };
   1659 
   1660         TestVM<> vm{R"((?<year>\d+)-(?<month>\d+)-(?<day>\d+))"};
   1661         kak_assert(vm.exec("2019-01-03", RegexExecFlags::None));
   1662         kak_assert(StringView{vm.captures()[2], vm.captures()[3]} == "2019");
   1663         kak_assert(StringView{vm.captures()[4], vm.captures()[5]} == "01");
   1664         kak_assert(StringView{vm.captures()[6], vm.captures()[7]} == "03");
   1665         kak_assert(vm.named_captures.size() == 3);
   1666         kak_assert(eq(vm.named_captures[0], {"year", 1}));
   1667         kak_assert(eq(vm.named_captures[1], {"month", 2}));
   1668         kak_assert(eq(vm.named_captures[2], {"day", 3}));
   1669     }
   1670 
   1671     auto check_parse_error = [](StringView re, StringView expected_error) {
   1672         try
   1673         {
   1674             TestVM<>{re};
   1675             kak_assert(false);
   1676         }
   1677         catch (const regex_error& err)
   1678         {
   1679             kak_assert(err.what() == String{"regex parse error: "} + expected_error);
   1680         }
   1681     };
   1682 
   1683     check_parse_error("(?=a*)", "Quantifiers cannot be used in lookarounds at '(?=a*)<<<HERE>>>'");
   1684     check_parse_error("(?=(a))", "Lookaround can only contain literals, any chars or character classes at '(?=(a))<<<HERE>>>'");
   1685     check_parse_error("(?=a|b)", "Alternations cannot be used in lookarounds at '(?=a|<<<HERE>>>b)'");
   1686 }};
   1687 
   1688 }