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 }