1 /* vi:set ts=8 sts=4 sw=4 noet: 2 * 3 * NFA regular expression implementation. 4 * 5 * This file is included in "regexp.c". 6 */ 7 8 /* 9 * Logging of NFA engine. 10 * 11 * The NFA engine can write four log files: 12 * - Error log: Contains NFA engine's fatal errors. 13 * - Dump log: Contains compiled NFA state machine's information. 14 * - Run log: Contains information of matching procedure. 15 * - Debug log: Contains detailed information of matching procedure. Can be 16 * disabled by undefining NFA_REGEXP_DEBUG_LOG. 17 * The first one can also be used without debug mode. 18 * The last three are enabled when compiled as debug mode and individually 19 * disabled by commenting them out. 20 * The log files can get quite big! 21 * Do disable all of this when compiling Vim for debugging, undefine DEBUG in 22 * regexp.c 23 */ 24 #ifdef DEBUG 25 # define NFA_REGEXP_ERROR_LOG "nfa_regexp_error.log" 26 # define ENABLE_LOG 27 # define NFA_REGEXP_DUMP_LOG "nfa_regexp_dump.log" 28 # define NFA_REGEXP_RUN_LOG "nfa_regexp_run.log" 29 # define NFA_REGEXP_DEBUG_LOG "nfa_regexp_debug.log" 30 #endif 31 32 /* Added to NFA_ANY - NFA_NUPPER_IC to include a NL. */ 33 #define NFA_ADD_NL 31 34 35 enum 36 { 37 NFA_SPLIT = -1024, 38 NFA_MATCH, 39 NFA_EMPTY, /* matches 0-length */ 40 41 NFA_START_COLL, /* [abc] start */ 42 NFA_END_COLL, /* [abc] end */ 43 NFA_START_NEG_COLL, /* [^abc] start */ 44 NFA_END_NEG_COLL, /* [^abc] end (postfix only) */ 45 NFA_RANGE, /* range of the two previous items 46 * (postfix only) */ 47 NFA_RANGE_MIN, /* low end of a range */ 48 NFA_RANGE_MAX, /* high end of a range */ 49 50 NFA_CONCAT, /* concatenate two previous items (postfix 51 * only) */ 52 NFA_OR, /* \| (postfix only) */ 53 NFA_STAR, /* greedy * (postfix only) */ 54 NFA_STAR_NONGREEDY, /* non-greedy * (postfix only) */ 55 NFA_QUEST, /* greedy \? (postfix only) */ 56 NFA_QUEST_NONGREEDY, /* non-greedy \? (postfix only) */ 57 58 NFA_BOL, /* ^ Begin line */ 59 NFA_EOL, /* $ End line */ 60 NFA_BOW, /* \< Begin word */ 61 NFA_EOW, /* \> End word */ 62 NFA_BOF, /* \%^ Begin file */ 63 NFA_EOF, /* \%$ End file */ 64 NFA_NEWL, 65 NFA_ZSTART, /* Used for \zs */ 66 NFA_ZEND, /* Used for \ze */ 67 NFA_NOPEN, /* Start of subexpression marked with \%( */ 68 NFA_NCLOSE, /* End of subexpr. marked with \%( ... \) */ 69 NFA_START_INVISIBLE, 70 NFA_START_INVISIBLE_FIRST, 71 NFA_START_INVISIBLE_NEG, 72 NFA_START_INVISIBLE_NEG_FIRST, 73 NFA_START_INVISIBLE_BEFORE, 74 NFA_START_INVISIBLE_BEFORE_FIRST, 75 NFA_START_INVISIBLE_BEFORE_NEG, 76 NFA_START_INVISIBLE_BEFORE_NEG_FIRST, 77 NFA_START_PATTERN, 78 NFA_END_INVISIBLE, 79 NFA_END_INVISIBLE_NEG, 80 NFA_END_PATTERN, 81 NFA_COMPOSING, /* Next nodes in NFA are part of the 82 composing multibyte char */ 83 NFA_END_COMPOSING, /* End of a composing char in the NFA */ 84 NFA_ANY_COMPOSING, /* \%C: Any composing characters. */ 85 NFA_OPT_CHARS, /* \%[abc] */ 86 87 /* The following are used only in the postfix form, not in the NFA */ 88 NFA_PREV_ATOM_NO_WIDTH, /* Used for \@= */ 89 NFA_PREV_ATOM_NO_WIDTH_NEG, /* Used for \@! */ 90 NFA_PREV_ATOM_JUST_BEFORE, /* Used for \@<= */ 91 NFA_PREV_ATOM_JUST_BEFORE_NEG, /* Used for \@<! */ 92 NFA_PREV_ATOM_LIKE_PATTERN, /* Used for \@> */ 93 94 NFA_BACKREF1, /* \1 */ 95 NFA_BACKREF2, /* \2 */ 96 NFA_BACKREF3, /* \3 */ 97 NFA_BACKREF4, /* \4 */ 98 NFA_BACKREF5, /* \5 */ 99 NFA_BACKREF6, /* \6 */ 100 NFA_BACKREF7, /* \7 */ 101 NFA_BACKREF8, /* \8 */ 102 NFA_BACKREF9, /* \9 */ 103 #ifdef FEAT_SYN_HL 104 NFA_ZREF1, /* \z1 */ 105 NFA_ZREF2, /* \z2 */ 106 NFA_ZREF3, /* \z3 */ 107 NFA_ZREF4, /* \z4 */ 108 NFA_ZREF5, /* \z5 */ 109 NFA_ZREF6, /* \z6 */ 110 NFA_ZREF7, /* \z7 */ 111 NFA_ZREF8, /* \z8 */ 112 NFA_ZREF9, /* \z9 */ 113 #endif 114 NFA_SKIP, /* Skip characters */ 115 116 NFA_MOPEN, 117 NFA_MOPEN1, 118 NFA_MOPEN2, 119 NFA_MOPEN3, 120 NFA_MOPEN4, 121 NFA_MOPEN5, 122 NFA_MOPEN6, 123 NFA_MOPEN7, 124 NFA_MOPEN8, 125 NFA_MOPEN9, 126 127 NFA_MCLOSE, 128 NFA_MCLOSE1, 129 NFA_MCLOSE2, 130 NFA_MCLOSE3, 131 NFA_MCLOSE4, 132 NFA_MCLOSE5, 133 NFA_MCLOSE6, 134 NFA_MCLOSE7, 135 NFA_MCLOSE8, 136 NFA_MCLOSE9, 137 138 #ifdef FEAT_SYN_HL 139 NFA_ZOPEN, 140 NFA_ZOPEN1, 141 NFA_ZOPEN2, 142 NFA_ZOPEN3, 143 NFA_ZOPEN4, 144 NFA_ZOPEN5, 145 NFA_ZOPEN6, 146 NFA_ZOPEN7, 147 NFA_ZOPEN8, 148 NFA_ZOPEN9, 149 150 NFA_ZCLOSE, 151 NFA_ZCLOSE1, 152 NFA_ZCLOSE2, 153 NFA_ZCLOSE3, 154 NFA_ZCLOSE4, 155 NFA_ZCLOSE5, 156 NFA_ZCLOSE6, 157 NFA_ZCLOSE7, 158 NFA_ZCLOSE8, 159 NFA_ZCLOSE9, 160 #endif 161 162 /* NFA_FIRST_NL */ 163 NFA_ANY, /* Match any one character. */ 164 NFA_IDENT, /* Match identifier char */ 165 NFA_SIDENT, /* Match identifier char but no digit */ 166 NFA_KWORD, /* Match keyword char */ 167 NFA_SKWORD, /* Match word char but no digit */ 168 NFA_FNAME, /* Match file name char */ 169 NFA_SFNAME, /* Match file name char but no digit */ 170 NFA_PRINT, /* Match printable char */ 171 NFA_SPRINT, /* Match printable char but no digit */ 172 NFA_WHITE, /* Match whitespace char */ 173 NFA_NWHITE, /* Match non-whitespace char */ 174 NFA_DIGIT, /* Match digit char */ 175 NFA_NDIGIT, /* Match non-digit char */ 176 NFA_HEX, /* Match hex char */ 177 NFA_NHEX, /* Match non-hex char */ 178 NFA_OCTAL, /* Match octal char */ 179 NFA_NOCTAL, /* Match non-octal char */ 180 NFA_WORD, /* Match word char */ 181 NFA_NWORD, /* Match non-word char */ 182 NFA_HEAD, /* Match head char */ 183 NFA_NHEAD, /* Match non-head char */ 184 NFA_ALPHA, /* Match alpha char */ 185 NFA_NALPHA, /* Match non-alpha char */ 186 NFA_LOWER, /* Match lowercase char */ 187 NFA_NLOWER, /* Match non-lowercase char */ 188 NFA_UPPER, /* Match uppercase char */ 189 NFA_NUPPER, /* Match non-uppercase char */ 190 NFA_LOWER_IC, /* Match [a-z] */ 191 NFA_NLOWER_IC, /* Match [^a-z] */ 192 NFA_UPPER_IC, /* Match [A-Z] */ 193 NFA_NUPPER_IC, /* Match [^A-Z] */ 194 195 NFA_FIRST_NL = NFA_ANY + NFA_ADD_NL, 196 NFA_LAST_NL = NFA_NUPPER_IC + NFA_ADD_NL, 197 198 NFA_CURSOR, /* Match cursor pos */ 199 NFA_LNUM, /* Match line number */ 200 NFA_LNUM_GT, /* Match > line number */ 201 NFA_LNUM_LT, /* Match < line number */ 202 NFA_COL, /* Match cursor column */ 203 NFA_COL_GT, /* Match > cursor column */ 204 NFA_COL_LT, /* Match < cursor column */ 205 NFA_VCOL, /* Match cursor virtual column */ 206 NFA_VCOL_GT, /* Match > cursor virtual column */ 207 NFA_VCOL_LT, /* Match < cursor virtual column */ 208 NFA_MARK, /* Match mark */ 209 NFA_MARK_GT, /* Match > mark */ 210 NFA_MARK_LT, /* Match < mark */ 211 NFA_VISUAL, /* Match Visual area */ 212 213 /* Character classes [:alnum:] etc */ 214 NFA_CLASS_ALNUM, 215 NFA_CLASS_ALPHA, 216 NFA_CLASS_BLANK, 217 NFA_CLASS_CNTRL, 218 NFA_CLASS_DIGIT, 219 NFA_CLASS_GRAPH, 220 NFA_CLASS_LOWER, 221 NFA_CLASS_PRINT, 222 NFA_CLASS_PUNCT, 223 NFA_CLASS_SPACE, 224 NFA_CLASS_UPPER, 225 NFA_CLASS_XDIGIT, 226 NFA_CLASS_TAB, 227 NFA_CLASS_RETURN, 228 NFA_CLASS_BACKSPACE, 229 NFA_CLASS_ESCAPE, 230 NFA_CLASS_IDENT, 231 NFA_CLASS_KEYWORD, 232 NFA_CLASS_FNAME 233 }; 234 235 /* Keep in sync with classchars. */ 236 static int nfa_classcodes[] = { 237 NFA_ANY, NFA_IDENT, NFA_SIDENT, NFA_KWORD,NFA_SKWORD, 238 NFA_FNAME, NFA_SFNAME, NFA_PRINT, NFA_SPRINT, 239 NFA_WHITE, NFA_NWHITE, NFA_DIGIT, NFA_NDIGIT, 240 NFA_HEX, NFA_NHEX, NFA_OCTAL, NFA_NOCTAL, 241 NFA_WORD, NFA_NWORD, NFA_HEAD, NFA_NHEAD, 242 NFA_ALPHA, NFA_NALPHA, NFA_LOWER, NFA_NLOWER, 243 NFA_UPPER, NFA_NUPPER 244 }; 245 246 static char_u e_nul_found[] = N_("E865: (NFA) Regexp end encountered prematurely"); 247 static char_u e_misplaced[] = N_("E866: (NFA regexp) Misplaced %c"); 248 static char_u e_ill_char_class[] = N_("E877: (NFA regexp) Invalid character class: %ld"); 249 250 // Variables only used in nfa_regcomp() and descendants. 251 static int nfa_re_flags; // re_flags passed to nfa_regcomp() 252 static int *post_start; // holds the postfix form of r.e. 253 static int *post_end; 254 static int *post_ptr; 255 static int nstate; // Number of states in the NFA. 256 static int istate; // Index in the state vector, used in alloc_state() 257 258 /* If not NULL match must end at this position */ 259 static save_se_T *nfa_endp = NULL; 260 261 /* 0 for first call to nfa_regmatch(), 1 for recursive call. */ 262 static int nfa_ll_index = 0; 263 264 static int realloc_post_list(void); 265 static int nfa_reg(int paren); 266 #ifdef DEBUG 267 static void nfa_print_state2(FILE *debugf, nfa_state_T *state, garray_T *indent); 268 #endif 269 static int match_follows(nfa_state_T *startstate, int depth); 270 static int failure_chance(nfa_state_T *state, int depth); 271 272 /* helper functions used when doing re2post() ... regatom() parsing */ 273 #define EMIT(c) do { \ 274 if (post_ptr >= post_end && realloc_post_list() == FAIL) \ 275 return FAIL; \ 276 *post_ptr++ = c; \ 277 } while (0) 278 279 /* 280 * Initialize internal variables before NFA compilation. 281 * Return OK on success, FAIL otherwise. 282 */ 283 static int 284 nfa_regcomp_start( 285 char_u *expr, 286 int re_flags) /* see vim_regcomp() */ 287 { 288 size_t postfix_size; 289 int nstate_max; 290 291 nstate = 0; 292 istate = 0; 293 /* A reasonable estimation for maximum size */ 294 nstate_max = (int)(STRLEN(expr) + 1) * 25; 295 296 /* Some items blow up in size, such as [A-z]. Add more space for that. 297 * When it is still not enough realloc_post_list() will be used. */ 298 nstate_max += 1000; 299 300 /* Size for postfix representation of expr. */ 301 postfix_size = sizeof(int) * nstate_max; 302 303 post_start = (int *)lalloc(postfix_size, TRUE); 304 if (post_start == NULL) 305 return FAIL; 306 post_ptr = post_start; 307 post_end = post_start + nstate_max; 308 rex.nfa_has_zend = FALSE; 309 rex.nfa_has_backref = FALSE; 310 311 /* shared with BT engine */ 312 regcomp_start(expr, re_flags); 313 314 return OK; 315 } 316 317 /* 318 * Figure out if the NFA state list starts with an anchor, must match at start 319 * of the line. 320 */ 321 static int 322 nfa_get_reganch(nfa_state_T *start, int depth) 323 { 324 nfa_state_T *p = start; 325 326 if (depth > 4) 327 return 0; 328 329 while (p != NULL) 330 { 331 switch (p->c) 332 { 333 case NFA_BOL: 334 case NFA_BOF: 335 return 1; /* yes! */ 336 337 case NFA_ZSTART: 338 case NFA_ZEND: 339 case NFA_CURSOR: 340 case NFA_VISUAL: 341 342 case NFA_MOPEN: 343 case NFA_MOPEN1: 344 case NFA_MOPEN2: 345 case NFA_MOPEN3: 346 case NFA_MOPEN4: 347 case NFA_MOPEN5: 348 case NFA_MOPEN6: 349 case NFA_MOPEN7: 350 case NFA_MOPEN8: 351 case NFA_MOPEN9: 352 case NFA_NOPEN: 353 #ifdef FEAT_SYN_HL 354 case NFA_ZOPEN: 355 case NFA_ZOPEN1: 356 case NFA_ZOPEN2: 357 case NFA_ZOPEN3: 358 case NFA_ZOPEN4: 359 case NFA_ZOPEN5: 360 case NFA_ZOPEN6: 361 case NFA_ZOPEN7: 362 case NFA_ZOPEN8: 363 case NFA_ZOPEN9: 364 #endif 365 p = p->out; 366 break; 367 368 case NFA_SPLIT: 369 return nfa_get_reganch(p->out, depth + 1) 370 && nfa_get_reganch(p->out1, depth + 1); 371 372 default: 373 return 0; /* noooo */ 374 } 375 } 376 return 0; 377 } 378 379 /* 380 * Figure out if the NFA state list starts with a character which must match 381 * at start of the match. 382 */ 383 static int 384 nfa_get_regstart(nfa_state_T *start, int depth) 385 { 386 nfa_state_T *p = start; 387 388 if (depth > 4) 389 return 0; 390 391 while (p != NULL) 392 { 393 switch (p->c) 394 { 395 /* all kinds of zero-width matches */ 396 case NFA_BOL: 397 case NFA_BOF: 398 case NFA_BOW: 399 case NFA_EOW: 400 case NFA_ZSTART: 401 case NFA_ZEND: 402 case NFA_CURSOR: 403 case NFA_VISUAL: 404 case NFA_LNUM: 405 case NFA_LNUM_GT: 406 case NFA_LNUM_LT: 407 case NFA_COL: 408 case NFA_COL_GT: 409 case NFA_COL_LT: 410 case NFA_VCOL: 411 case NFA_VCOL_GT: 412 case NFA_VCOL_LT: 413 case NFA_MARK: 414 case NFA_MARK_GT: 415 case NFA_MARK_LT: 416 417 case NFA_MOPEN: 418 case NFA_MOPEN1: 419 case NFA_MOPEN2: 420 case NFA_MOPEN3: 421 case NFA_MOPEN4: 422 case NFA_MOPEN5: 423 case NFA_MOPEN6: 424 case NFA_MOPEN7: 425 case NFA_MOPEN8: 426 case NFA_MOPEN9: 427 case NFA_NOPEN: 428 #ifdef FEAT_SYN_HL 429 case NFA_ZOPEN: 430 case NFA_ZOPEN1: 431 case NFA_ZOPEN2: 432 case NFA_ZOPEN3: 433 case NFA_ZOPEN4: 434 case NFA_ZOPEN5: 435 case NFA_ZOPEN6: 436 case NFA_ZOPEN7: 437 case NFA_ZOPEN8: 438 case NFA_ZOPEN9: 439 #endif 440 p = p->out; 441 break; 442 443 case NFA_SPLIT: 444 { 445 int c1 = nfa_get_regstart(p->out, depth + 1); 446 int c2 = nfa_get_regstart(p->out1, depth + 1); 447 448 if (c1 == c2) 449 return c1; /* yes! */ 450 return 0; 451 } 452 453 default: 454 if (p->c > 0) 455 return p->c; /* yes! */ 456 return 0; 457 } 458 } 459 return 0; 460 } 461 462 /* 463 * Figure out if the NFA state list contains just literal text and nothing 464 * else. If so return a string in allocated memory with what must match after 465 * regstart. Otherwise return NULL. 466 */ 467 static char_u * 468 nfa_get_match_text(nfa_state_T *start) 469 { 470 nfa_state_T *p = start; 471 int len = 0; 472 char_u *ret; 473 char_u *s; 474 475 if (p->c != NFA_MOPEN) 476 return NULL; /* just in case */ 477 p = p->out; 478 while (p->c > 0) 479 { 480 len += MB_CHAR2LEN(p->c); 481 p = p->out; 482 } 483 if (p->c != NFA_MCLOSE || p->out->c != NFA_MATCH) 484 return NULL; 485 486 ret = alloc(len); 487 if (ret != NULL) 488 { 489 p = start->out->out; /* skip first char, it goes into regstart */ 490 s = ret; 491 while (p->c > 0) 492 { 493 if (has_mbyte) 494 s += (*mb_char2bytes)(p->c, s); 495 else 496 *s++ = p->c; 497 p = p->out; 498 } 499 *s = NUL; 500 } 501 return ret; 502 } 503 504 /* 505 * Allocate more space for post_start. Called when 506 * running above the estimated number of states. 507 */ 508 static int 509 realloc_post_list(void) 510 { 511 int nstate_max = (int)(post_end - post_start); 512 int new_max = nstate_max + 1000; 513 int *new_start; 514 int *old_start; 515 516 new_start = (int *)lalloc(new_max * sizeof(int), TRUE); 517 if (new_start == NULL) 518 return FAIL; 519 mch_memmove(new_start, post_start, nstate_max * sizeof(int)); 520 old_start = post_start; 521 post_start = new_start; 522 post_ptr = new_start + (post_ptr - old_start); 523 post_end = post_start + new_max; 524 vim_free(old_start); 525 return OK; 526 } 527 528 /* 529 * Search between "start" and "end" and try to recognize a 530 * character class in expanded form. For example [0-9]. 531 * On success, return the id the character class to be emitted. 532 * On failure, return 0 (=FAIL) 533 * Start points to the first char of the range, while end should point 534 * to the closing brace. 535 * Keep in mind that 'ignorecase' applies at execution time, thus [a-z] may 536 * need to be interpreted as [a-zA-Z]. 537 */ 538 static int 539 nfa_recognize_char_class(char_u *start, char_u *end, int extra_newl) 540 { 541 # define CLASS_not 0x80 542 # define CLASS_af 0x40 543 # define CLASS_AF 0x20 544 # define CLASS_az 0x10 545 # define CLASS_AZ 0x08 546 # define CLASS_o7 0x04 547 # define CLASS_o9 0x02 548 # define CLASS_underscore 0x01 549 550 int newl = FALSE; 551 char_u *p; 552 int config = 0; 553 554 if (extra_newl == TRUE) 555 newl = TRUE; 556 557 if (*end != ']') 558 return FAIL; 559 p = start; 560 if (*p == '^') 561 { 562 config |= CLASS_not; 563 p++; 564 } 565 566 while (p < end) 567 { 568 if (p + 2 < end && *(p + 1) == '-') 569 { 570 switch (*p) 571 { 572 case '0': 573 if (*(p + 2) == '9') 574 { 575 config |= CLASS_o9; 576 break; 577 } 578 if (*(p + 2) == '7') 579 { 580 config |= CLASS_o7; 581 break; 582 } 583 return FAIL; 584 585 case 'a': 586 if (*(p + 2) == 'z') 587 { 588 config |= CLASS_az; 589 break; 590 } 591 if (*(p + 2) == 'f') 592 { 593 config |= CLASS_af; 594 break; 595 } 596 return FAIL; 597 598 case 'A': 599 if (*(p + 2) == 'Z') 600 { 601 config |= CLASS_AZ; 602 break; 603 } 604 if (*(p + 2) == 'F') 605 { 606 config |= CLASS_AF; 607 break; 608 } 609 return FAIL; 610 611 default: 612 return FAIL; 613 } 614 p += 3; 615 } 616 else if (p + 1 < end && *p == '\\' && *(p + 1) == 'n') 617 { 618 newl = TRUE; 619 p += 2; 620 } 621 else if (*p == '_') 622 { 623 config |= CLASS_underscore; 624 p ++; 625 } 626 else if (*p == '\n') 627 { 628 newl = TRUE; 629 p ++; 630 } 631 else 632 return FAIL; 633 } /* while (p < end) */ 634 635 if (p != end) 636 return FAIL; 637 638 if (newl == TRUE) 639 extra_newl = NFA_ADD_NL; 640 641 switch (config) 642 { 643 case CLASS_o9: 644 return extra_newl + NFA_DIGIT; 645 case CLASS_not | CLASS_o9: 646 return extra_newl + NFA_NDIGIT; 647 case CLASS_af | CLASS_AF | CLASS_o9: 648 return extra_newl + NFA_HEX; 649 case CLASS_not | CLASS_af | CLASS_AF | CLASS_o9: 650 return extra_newl + NFA_NHEX; 651 case CLASS_o7: 652 return extra_newl + NFA_OCTAL; 653 case CLASS_not | CLASS_o7: 654 return extra_newl + NFA_NOCTAL; 655 case CLASS_az | CLASS_AZ | CLASS_o9 | CLASS_underscore: 656 return extra_newl + NFA_WORD; 657 case CLASS_not | CLASS_az | CLASS_AZ | CLASS_o9 | CLASS_underscore: 658 return extra_newl + NFA_NWORD; 659 case CLASS_az | CLASS_AZ | CLASS_underscore: 660 return extra_newl + NFA_HEAD; 661 case CLASS_not | CLASS_az | CLASS_AZ | CLASS_underscore: 662 return extra_newl + NFA_NHEAD; 663 case CLASS_az | CLASS_AZ: 664 return extra_newl + NFA_ALPHA; 665 case CLASS_not | CLASS_az | CLASS_AZ: 666 return extra_newl + NFA_NALPHA; 667 case CLASS_az: 668 return extra_newl + NFA_LOWER_IC; 669 case CLASS_not | CLASS_az: 670 return extra_newl + NFA_NLOWER_IC; 671 case CLASS_AZ: 672 return extra_newl + NFA_UPPER_IC; 673 case CLASS_not | CLASS_AZ: 674 return extra_newl + NFA_NUPPER_IC; 675 } 676 return FAIL; 677 } 678 679 /* 680 * Produce the bytes for equivalence class "c". 681 * Currently only handles latin1, latin9 and utf-8. 682 * Emits bytes in postfix notation: 'a,b,NFA_OR,c,NFA_OR' is 683 * equivalent to 'a OR b OR c' 684 * 685 * NOTE! When changing this function, also update reg_equi_class() 686 */ 687 static int 688 nfa_emit_equi_class(int c) 689 { 690 #define EMIT2(c) EMIT(c); EMIT(NFA_CONCAT); 691 #define EMITMBC(c) EMIT(c); EMIT(NFA_CONCAT); 692 693 if (enc_utf8 || STRCMP(p_enc, "latin1") == 0 694 || STRCMP(p_enc, "iso-8859-15") == 0) 695 { 696 #ifdef EBCDIC 697 # define A_circumflex 0x62 698 # define A_diaeresis 0x63 699 # define A_grave 0x64 700 # define A_acute 0x65 701 # define A_virguilla 0x66 702 # define A_ring 0x67 703 # define C_cedilla 0x68 704 # define E_acute 0x71 705 # define E_circumflex 0x72 706 # define E_diaeresis 0x73 707 # define E_grave 0x74 708 # define I_acute 0x75 709 # define I_circumflex 0x76 710 # define I_diaeresis 0x77 711 # define I_grave 0x78 712 # define N_virguilla 0x69 713 # define O_circumflex 0xeb 714 # define O_diaeresis 0xec 715 # define O_grave 0xed 716 # define O_acute 0xee 717 # define O_virguilla 0xef 718 # define O_slash 0x80 719 # define U_circumflex 0xfb 720 # define U_diaeresis 0xfc 721 # define U_grave 0xfd 722 # define U_acute 0xfe 723 # define Y_acute 0xba 724 # define a_grave 0x42 725 # define a_acute 0x43 726 # define a_circumflex 0x44 727 # define a_virguilla 0x45 728 # define a_diaeresis 0x46 729 # define a_ring 0x47 730 # define c_cedilla 0x48 731 # define e_grave 0x51 732 # define e_acute 0x52 733 # define e_circumflex 0x53 734 # define e_diaeresis 0x54 735 # define i_grave 0x55 736 # define i_acute 0x56 737 # define i_circumflex 0x57 738 # define i_diaeresis 0x58 739 # define n_virguilla 0x49 740 # define o_grave 0xcb 741 # define o_acute 0xcc 742 # define o_circumflex 0xcd 743 # define o_virguilla 0xce 744 # define o_diaeresis 0xcf 745 # define o_slash 0x70 746 # define u_grave 0xdb 747 # define u_acute 0xdc 748 # define u_circumflex 0xdd 749 # define u_diaeresis 0xde 750 # define y_acute 0x8d 751 # define y_diaeresis 0xdf 752 #else 753 # define A_grave 0xc0 754 # define A_acute 0xc1 755 # define A_circumflex 0xc2 756 # define A_virguilla 0xc3 757 # define A_diaeresis 0xc4 758 # define A_ring 0xc5 759 # define C_cedilla 0xc7 760 # define E_grave 0xc8 761 # define E_acute 0xc9 762 # define E_circumflex 0xca 763 # define E_diaeresis 0xcb 764 # define I_grave 0xcc 765 # define I_acute 0xcd 766 # define I_circumflex 0xce 767 # define I_diaeresis 0xcf 768 # define N_virguilla 0xd1 769 # define O_grave 0xd2 770 # define O_acute 0xd3 771 # define O_circumflex 0xd4 772 # define O_virguilla 0xd5 773 # define O_diaeresis 0xd6 774 # define O_slash 0xd8 775 # define U_grave 0xd9 776 # define U_acute 0xda 777 # define U_circumflex 0xdb 778 # define U_diaeresis 0xdc 779 # define Y_acute 0xdd 780 # define a_grave 0xe0 781 # define a_acute 0xe1 782 # define a_circumflex 0xe2 783 # define a_virguilla 0xe3 784 # define a_diaeresis 0xe4 785 # define a_ring 0xe5 786 # define c_cedilla 0xe7 787 # define e_grave 0xe8 788 # define e_acute 0xe9 789 # define e_circumflex 0xea 790 # define e_diaeresis 0xeb 791 # define i_grave 0xec 792 # define i_acute 0xed 793 # define i_circumflex 0xee 794 # define i_diaeresis 0xef 795 # define n_virguilla 0xf1 796 # define o_grave 0xf2 797 # define o_acute 0xf3 798 # define o_circumflex 0xf4 799 # define o_virguilla 0xf5 800 # define o_diaeresis 0xf6 801 # define o_slash 0xf8 802 # define u_grave 0xf9 803 # define u_acute 0xfa 804 # define u_circumflex 0xfb 805 # define u_diaeresis 0xfc 806 # define y_acute 0xfd 807 # define y_diaeresis 0xff 808 #endif 809 switch (c) 810 { 811 case 'A': case A_grave: case A_acute: case A_circumflex: 812 case A_virguilla: case A_diaeresis: case A_ring: 813 CASEMBC(0x100) CASEMBC(0x102) CASEMBC(0x104) 814 CASEMBC(0x1cd) CASEMBC(0x1de) CASEMBC(0x1e0) 815 CASEMBC(0x1ea2) 816 EMIT2('A'); EMIT2(A_grave); EMIT2(A_acute); 817 EMIT2(A_circumflex); EMIT2(A_virguilla); 818 EMIT2(A_diaeresis); EMIT2(A_ring); 819 EMITMBC(0x100) EMITMBC(0x102) EMITMBC(0x104) 820 EMITMBC(0x1cd) EMITMBC(0x1de) EMITMBC(0x1e0) 821 EMITMBC(0x1ea2) 822 return OK; 823 824 case 'B': CASEMBC(0x1e02) CASEMBC(0x1e06) 825 EMIT2('B'); EMITMBC(0x1e02) EMITMBC(0x1e06) 826 return OK; 827 828 case 'C': case C_cedilla: CASEMBC(0x106) CASEMBC(0x108) 829 CASEMBC(0x10a) CASEMBC(0x10c) 830 EMIT2('C'); EMIT2(C_cedilla); 831 EMITMBC(0x106) EMITMBC(0x108) 832 EMITMBC(0x10a) EMITMBC(0x10c) 833 return OK; 834 835 case 'D': CASEMBC(0x10e) CASEMBC(0x110) CASEMBC(0x1e0a) 836 CASEMBC(0x1e0e) CASEMBC(0x1e10) 837 EMIT2('D'); EMITMBC(0x10e) EMITMBC(0x110) EMITMBC(0x1e0a) 838 EMITMBC(0x1e0e) EMITMBC(0x1e10) 839 return OK; 840 841 case 'E': case E_grave: case E_acute: case E_circumflex: 842 case E_diaeresis: CASEMBC(0x112) CASEMBC(0x114) 843 CASEMBC(0x116) CASEMBC(0x118) CASEMBC(0x11a) 844 CASEMBC(0x1eba) CASEMBC(0x1ebc) 845 EMIT2('E'); EMIT2(E_grave); EMIT2(E_acute); 846 EMIT2(E_circumflex); EMIT2(E_diaeresis); 847 EMITMBC(0x112) EMITMBC(0x114) EMITMBC(0x116) 848 EMITMBC(0x118) EMITMBC(0x11a) EMITMBC(0x1eba) 849 EMITMBC(0x1ebc) 850 return OK; 851 852 case 'F': CASEMBC(0x1e1e) 853 EMIT2('F'); EMITMBC(0x1e1e) 854 return OK; 855 856 case 'G': CASEMBC(0x11c) CASEMBC(0x11e) CASEMBC(0x120) 857 CASEMBC(0x122) CASEMBC(0x1e4) CASEMBC(0x1e6) 858 CASEMBC(0x1f4) CASEMBC(0x1e20) 859 EMIT2('G'); EMITMBC(0x11c) EMITMBC(0x11e) EMITMBC(0x120) 860 EMITMBC(0x122) EMITMBC(0x1e4) EMITMBC(0x1e6) 861 EMITMBC(0x1f4) EMITMBC(0x1e20) 862 return OK; 863 864 case 'H': CASEMBC(0x124) CASEMBC(0x126) CASEMBC(0x1e22) 865 CASEMBC(0x1e26) CASEMBC(0x1e28) 866 EMIT2('H'); EMITMBC(0x124) EMITMBC(0x126) EMITMBC(0x1e22) 867 EMITMBC(0x1e26) EMITMBC(0x1e28) 868 return OK; 869 870 case 'I': case I_grave: case I_acute: case I_circumflex: 871 case I_diaeresis: CASEMBC(0x128) CASEMBC(0x12a) 872 CASEMBC(0x12c) CASEMBC(0x12e) CASEMBC(0x130) 873 CASEMBC(0x1cf) CASEMBC(0x1ec8) 874 EMIT2('I'); EMIT2(I_grave); EMIT2(I_acute); 875 EMIT2(I_circumflex); EMIT2(I_diaeresis); 876 EMITMBC(0x128) EMITMBC(0x12a) 877 EMITMBC(0x12c) EMITMBC(0x12e) EMITMBC(0x130) 878 EMITMBC(0x1cf) EMITMBC(0x1ec8) 879 return OK; 880 881 case 'J': CASEMBC(0x134) 882 EMIT2('J'); EMITMBC(0x134) 883 return OK; 884 885 case 'K': CASEMBC(0x136) CASEMBC(0x1e8) CASEMBC(0x1e30) 886 CASEMBC(0x1e34) 887 EMIT2('K'); EMITMBC(0x136) EMITMBC(0x1e8) EMITMBC(0x1e30) 888 EMITMBC(0x1e34) 889 return OK; 890 891 case 'L': CASEMBC(0x139) CASEMBC(0x13b) CASEMBC(0x13d) 892 CASEMBC(0x13f) CASEMBC(0x141) CASEMBC(0x1e3a) 893 EMIT2('L'); EMITMBC(0x139) EMITMBC(0x13b) EMITMBC(0x13d) 894 EMITMBC(0x13f) EMITMBC(0x141) EMITMBC(0x1e3a) 895 return OK; 896 897 case 'M': CASEMBC(0x1e3e) CASEMBC(0x1e40) 898 EMIT2('M'); EMITMBC(0x1e3e) EMITMBC(0x1e40) 899 return OK; 900 901 case 'N': case N_virguilla: CASEMBC(0x143) CASEMBC(0x145) 902 CASEMBC(0x147) CASEMBC(0x1e44) CASEMBC(0x1e48) 903 EMIT2('N'); EMIT2(N_virguilla); 904 EMITMBC(0x143) EMITMBC(0x145) 905 EMITMBC(0x147) EMITMBC(0x1e44) EMITMBC(0x1e48) 906 return OK; 907 908 case 'O': case O_grave: case O_acute: case O_circumflex: 909 case O_virguilla: case O_diaeresis: case O_slash: 910 CASEMBC(0x14c) CASEMBC(0x14e) CASEMBC(0x150) 911 CASEMBC(0x1a0) CASEMBC(0x1d1) CASEMBC(0x1ea) 912 CASEMBC(0x1ec) CASEMBC(0x1ece) 913 EMIT2('O'); EMIT2(O_grave); EMIT2(O_acute); 914 EMIT2(O_circumflex); EMIT2(O_virguilla); 915 EMIT2(O_diaeresis); EMIT2(O_slash); 916 EMITMBC(0x14c) EMITMBC(0x14e) EMITMBC(0x150) 917 EMITMBC(0x1a0) EMITMBC(0x1d1) EMITMBC(0x1ea) 918 EMITMBC(0x1ec) EMITMBC(0x1ece) 919 return OK; 920 921 case 'P': case 0x1e54: case 0x1e56: 922 EMIT2('P'); EMITMBC(0x1e54) EMITMBC(0x1e56) 923 return OK; 924 925 case 'R': CASEMBC(0x154) CASEMBC(0x156) CASEMBC(0x158) 926 CASEMBC(0x1e58) CASEMBC(0x1e5e) 927 EMIT2('R'); EMITMBC(0x154) EMITMBC(0x156) EMITMBC(0x158) 928 EMITMBC(0x1e58) EMITMBC(0x1e5e) 929 return OK; 930 931 case 'S': CASEMBC(0x15a) CASEMBC(0x15c) CASEMBC(0x15e) 932 CASEMBC(0x160) CASEMBC(0x1e60) 933 EMIT2('S'); EMITMBC(0x15a) EMITMBC(0x15c) EMITMBC(0x15e) 934 EMITMBC(0x160) EMITMBC(0x1e60) 935 return OK; 936 937 case 'T': CASEMBC(0x162) CASEMBC(0x164) CASEMBC(0x166) 938 CASEMBC(0x1e6a) CASEMBC(0x1e6e) 939 EMIT2('T'); EMITMBC(0x162) EMITMBC(0x164) EMITMBC(0x166) 940 EMITMBC(0x1e6a) EMITMBC(0x1e6e) 941 return OK; 942 943 case 'U': case U_grave: case U_acute: case U_diaeresis: 944 case U_circumflex: CASEMBC(0x168) CASEMBC(0x16a) 945 CASEMBC(0x16c) CASEMBC(0x16e) CASEMBC(0x170) 946 CASEMBC(0x172) CASEMBC(0x1af) CASEMBC(0x1d3) 947 CASEMBC(0x1ee6) 948 EMIT2('U'); EMIT2(U_grave); EMIT2(U_acute); 949 EMIT2(U_diaeresis); EMIT2(U_circumflex); 950 EMITMBC(0x168) EMITMBC(0x16a) 951 EMITMBC(0x16c) EMITMBC(0x16e) EMITMBC(0x170) 952 EMITMBC(0x172) EMITMBC(0x1af) EMITMBC(0x1d3) 953 EMITMBC(0x1ee6) 954 return OK; 955 956 case 'V': CASEMBC(0x1e7c) 957 EMIT2('V'); EMITMBC(0x1e7c) 958 return OK; 959 960 case 'W': CASEMBC(0x174) CASEMBC(0x1e80) CASEMBC(0x1e82) 961 CASEMBC(0x1e84) CASEMBC(0x1e86) 962 EMIT2('W'); EMITMBC(0x174) EMITMBC(0x1e80) EMITMBC(0x1e82) 963 EMITMBC(0x1e84) EMITMBC(0x1e86) 964 return OK; 965 966 case 'X': CASEMBC(0x1e8a) CASEMBC(0x1e8c) 967 EMIT2('X'); EMITMBC(0x1e8a) EMITMBC(0x1e8c) 968 return OK; 969 970 case 'Y': case Y_acute: CASEMBC(0x176) CASEMBC(0x178) 971 CASEMBC(0x1e8e) CASEMBC(0x1ef2) CASEMBC(0x1ef6) 972 CASEMBC(0x1ef8) 973 EMIT2('Y'); EMIT2(Y_acute); 974 EMITMBC(0x176) EMITMBC(0x178) 975 EMITMBC(0x1e8e) EMITMBC(0x1ef2) EMITMBC(0x1ef6) 976 EMITMBC(0x1ef8) 977 return OK; 978 979 case 'Z': CASEMBC(0x179) CASEMBC(0x17b) CASEMBC(0x17d) 980 CASEMBC(0x1b5) CASEMBC(0x1e90) CASEMBC(0x1e94) 981 EMIT2('Z'); EMITMBC(0x179) EMITMBC(0x17b) EMITMBC(0x17d) 982 EMITMBC(0x1b5) EMITMBC(0x1e90) EMITMBC(0x1e94) 983 return OK; 984 985 case 'a': case a_grave: case a_acute: case a_circumflex: 986 case a_virguilla: case a_diaeresis: case a_ring: 987 CASEMBC(0x101) CASEMBC(0x103) CASEMBC(0x105) 988 CASEMBC(0x1ce) CASEMBC(0x1df) CASEMBC(0x1e1) 989 CASEMBC(0x1ea3) 990 EMIT2('a'); EMIT2(a_grave); EMIT2(a_acute); 991 EMIT2(a_circumflex); EMIT2(a_virguilla); 992 EMIT2(a_diaeresis); EMIT2(a_ring); 993 EMITMBC(0x101) EMITMBC(0x103) EMITMBC(0x105) 994 EMITMBC(0x1ce) EMITMBC(0x1df) EMITMBC(0x1e1) 995 EMITMBC(0x1ea3) 996 return OK; 997 998 case 'b': CASEMBC(0x1e03) CASEMBC(0x1e07) 999 EMIT2('b'); EMITMBC(0x1e03) EMITMBC(0x1e07) 1000 return OK; 1001 1002 case 'c': case c_cedilla: CASEMBC(0x107) CASEMBC(0x109) 1003 CASEMBC(0x10b) CASEMBC(0x10d) 1004 EMIT2('c'); EMIT2(c_cedilla); 1005 EMITMBC(0x107) EMITMBC(0x109) 1006 EMITMBC(0x10b) EMITMBC(0x10d) 1007 return OK; 1008 1009 case 'd': CASEMBC(0x10f) CASEMBC(0x111) CASEMBC(0x1e0b) 1010 CASEMBC(0x1e0f) CASEMBC(0x1e11) 1011 EMIT2('d'); EMITMBC(0x10f) EMITMBC(0x111) 1012 EMITMBC(0x1e0b) EMITMBC(0x1e0f) EMITMBC(0x1e11) 1013 return OK; 1014 1015 case 'e': case e_grave: case e_acute: case e_circumflex: 1016 case e_diaeresis: CASEMBC(0x113) CASEMBC(0x115) 1017 CASEMBC(0x117) CASEMBC(0x119) CASEMBC(0x11b) 1018 CASEMBC(0x1ebb) CASEMBC(0x1ebd) 1019 EMIT2('e'); EMIT2(e_grave); EMIT2(e_acute); 1020 EMIT2(e_circumflex); EMIT2(e_diaeresis); 1021 EMITMBC(0x113) EMITMBC(0x115) 1022 EMITMBC(0x117) EMITMBC(0x119) EMITMBC(0x11b) 1023 EMITMBC(0x1ebb) EMITMBC(0x1ebd) 1024 return OK; 1025 1026 case 'f': CASEMBC(0x1e1f) 1027 EMIT2('f'); EMITMBC(0x1e1f) 1028 return OK; 1029 1030 case 'g': CASEMBC(0x11d) CASEMBC(0x11f) CASEMBC(0x121) 1031 CASEMBC(0x123) CASEMBC(0x1e5) CASEMBC(0x1e7) 1032 CASEMBC(0x1f5) CASEMBC(0x1e21) 1033 EMIT2('g'); EMITMBC(0x11d) EMITMBC(0x11f) EMITMBC(0x121) 1034 EMITMBC(0x123) EMITMBC(0x1e5) EMITMBC(0x1e7) 1035 EMITMBC(0x1f5) EMITMBC(0x1e21) 1036 return OK; 1037 1038 case 'h': CASEMBC(0x125) CASEMBC(0x127) CASEMBC(0x1e23) 1039 CASEMBC(0x1e27) CASEMBC(0x1e29) CASEMBC(0x1e96) 1040 EMIT2('h'); EMITMBC(0x125) EMITMBC(0x127) EMITMBC(0x1e23) 1041 EMITMBC(0x1e27) EMITMBC(0x1e29) EMITMBC(0x1e96) 1042 return OK; 1043 1044 case 'i': case i_grave: case i_acute: case i_circumflex: 1045 case i_diaeresis: CASEMBC(0x129) CASEMBC(0x12b) 1046 CASEMBC(0x12d) CASEMBC(0x12f) CASEMBC(0x1d0) 1047 CASEMBC(0x1ec9) 1048 EMIT2('i'); EMIT2(i_grave); EMIT2(i_acute); 1049 EMIT2(i_circumflex); EMIT2(i_diaeresis); 1050 EMITMBC(0x129) EMITMBC(0x12b) 1051 EMITMBC(0x12d) EMITMBC(0x12f) EMITMBC(0x1d0) 1052 EMITMBC(0x1ec9) 1053 return OK; 1054 1055 case 'j': CASEMBC(0x135) CASEMBC(0x1f0) 1056 EMIT2('j'); EMITMBC(0x135) EMITMBC(0x1f0) 1057 return OK; 1058 1059 case 'k': CASEMBC(0x137) CASEMBC(0x1e9) CASEMBC(0x1e31) 1060 CASEMBC(0x1e35) 1061 EMIT2('k'); EMITMBC(0x137) EMITMBC(0x1e9) EMITMBC(0x1e31) 1062 EMITMBC(0x1e35) 1063 return OK; 1064 1065 case 'l': CASEMBC(0x13a) CASEMBC(0x13c) CASEMBC(0x13e) 1066 CASEMBC(0x140) CASEMBC(0x142) CASEMBC(0x1e3b) 1067 EMIT2('l'); EMITMBC(0x13a) EMITMBC(0x13c) EMITMBC(0x13e) 1068 EMITMBC(0x140) EMITMBC(0x142) EMITMBC(0x1e3b) 1069 return OK; 1070 1071 case 'm': CASEMBC(0x1e3f) CASEMBC(0x1e41) 1072 EMIT2('m'); EMITMBC(0x1e3f) EMITMBC(0x1e41) 1073 return OK; 1074 1075 case 'n': case n_virguilla: CASEMBC(0x144) CASEMBC(0x146) 1076 CASEMBC(0x148) CASEMBC(0x149) CASEMBC(0x1e45) 1077 CASEMBC(0x1e49) 1078 EMIT2('n'); EMIT2(n_virguilla); 1079 EMITMBC(0x144) EMITMBC(0x146) 1080 EMITMBC(0x148) EMITMBC(0x149) EMITMBC(0x1e45) 1081 EMITMBC(0x1e49) 1082 return OK; 1083 1084 case 'o': case o_grave: case o_acute: case o_circumflex: 1085 case o_virguilla: case o_diaeresis: case o_slash: 1086 CASEMBC(0x14d) CASEMBC(0x14f) CASEMBC(0x151) 1087 CASEMBC(0x1a1) CASEMBC(0x1d2) CASEMBC(0x1eb) 1088 CASEMBC(0x1ed) CASEMBC(0x1ecf) 1089 EMIT2('o'); EMIT2(o_grave); EMIT2(o_acute); 1090 EMIT2(o_circumflex); EMIT2(o_virguilla); 1091 EMIT2(o_diaeresis); EMIT2(o_slash); 1092 EMITMBC(0x14d) EMITMBC(0x14f) EMITMBC(0x151) 1093 EMITMBC(0x1a1) EMITMBC(0x1d2) EMITMBC(0x1eb) 1094 EMITMBC(0x1ed) EMITMBC(0x1ecf) 1095 return OK; 1096 1097 case 'p': CASEMBC(0x1e55) CASEMBC(0x1e57) 1098 EMIT2('p'); EMITMBC(0x1e55) EMITMBC(0x1e57) 1099 return OK; 1100 1101 case 'r': CASEMBC(0x155) CASEMBC(0x157) CASEMBC(0x159) 1102 CASEMBC(0x1e59) CASEMBC(0x1e5f) 1103 EMIT2('r'); EMITMBC(0x155) EMITMBC(0x157) EMITMBC(0x159) 1104 EMITMBC(0x1e59) EMITMBC(0x1e5f) 1105 return OK; 1106 1107 case 's': CASEMBC(0x15b) CASEMBC(0x15d) CASEMBC(0x15f) 1108 CASEMBC(0x161) CASEMBC(0x1e61) 1109 EMIT2('s'); EMITMBC(0x15b) EMITMBC(0x15d) EMITMBC(0x15f) 1110 EMITMBC(0x161) EMITMBC(0x1e61) 1111 return OK; 1112 1113 case 't': CASEMBC(0x163) CASEMBC(0x165) CASEMBC(0x167) 1114 CASEMBC(0x1e6b) CASEMBC(0x1e6f) CASEMBC(0x1e97) 1115 EMIT2('t'); EMITMBC(0x163) EMITMBC(0x165) EMITMBC(0x167) 1116 EMITMBC(0x1e6b) EMITMBC(0x1e6f) EMITMBC(0x1e97) 1117 return OK; 1118 1119 case 'u': case u_grave: case u_acute: case u_circumflex: 1120 case u_diaeresis: CASEMBC(0x169) CASEMBC(0x16b) 1121 CASEMBC(0x16d) CASEMBC(0x16f) CASEMBC(0x171) 1122 CASEMBC(0x173) CASEMBC(0x1b0) CASEMBC(0x1d4) 1123 CASEMBC(0x1ee7) 1124 EMIT2('u'); EMIT2(u_grave); EMIT2(u_acute); 1125 EMIT2(u_circumflex); EMIT2(u_diaeresis); 1126 EMITMBC(0x169) EMITMBC(0x16b) 1127 EMITMBC(0x16d) EMITMBC(0x16f) EMITMBC(0x171) 1128 EMITMBC(0x173) EMITMBC(0x1b0) EMITMBC(0x1d4) 1129 EMITMBC(0x1ee7) 1130 return OK; 1131 1132 case 'v': CASEMBC(0x1e7d) 1133 EMIT2('v'); EMITMBC(0x1e7d) 1134 return OK; 1135 1136 case 'w': CASEMBC(0x175) CASEMBC(0x1e81) CASEMBC(0x1e83) 1137 CASEMBC(0x1e85) CASEMBC(0x1e87) CASEMBC(0x1e98) 1138 EMIT2('w'); EMITMBC(0x175) EMITMBC(0x1e81) EMITMBC(0x1e83) 1139 EMITMBC(0x1e85) EMITMBC(0x1e87) EMITMBC(0x1e98) 1140 return OK; 1141 1142 case 'x': CASEMBC(0x1e8b) CASEMBC(0x1e8d) 1143 EMIT2('x'); EMITMBC(0x1e8b) EMITMBC(0x1e8d) 1144 return OK; 1145 1146 case 'y': case y_acute: case y_diaeresis: CASEMBC(0x177) 1147 CASEMBC(0x1e8f) CASEMBC(0x1e99) CASEMBC(0x1ef3) 1148 CASEMBC(0x1ef7) CASEMBC(0x1ef9) 1149 EMIT2('y'); EMIT2(y_acute); EMIT2(y_diaeresis); 1150 EMITMBC(0x177) 1151 EMITMBC(0x1e8f) EMITMBC(0x1e99) EMITMBC(0x1ef3) 1152 EMITMBC(0x1ef7) EMITMBC(0x1ef9) 1153 return OK; 1154 1155 case 'z': CASEMBC(0x17a) CASEMBC(0x17c) CASEMBC(0x17e) 1156 CASEMBC(0x1b6) CASEMBC(0x1e91) CASEMBC(0x1e95) 1157 EMIT2('z'); EMITMBC(0x17a) EMITMBC(0x17c) EMITMBC(0x17e) 1158 EMITMBC(0x1b6) EMITMBC(0x1e91) EMITMBC(0x1e95) 1159 return OK; 1160 1161 /* default: character itself */ 1162 } 1163 } 1164 1165 EMIT2(c); 1166 return OK; 1167 #undef EMIT2 1168 #undef EMITMBC 1169 } 1170 1171 /* 1172 * Code to parse regular expression. 1173 * 1174 * We try to reuse parsing functions in regexp.c to 1175 * minimize surprise and keep the syntax consistent. 1176 */ 1177 1178 /* 1179 * Parse the lowest level. 1180 * 1181 * An atom can be one of a long list of items. Many atoms match one character 1182 * in the text. It is often an ordinary character or a character class. 1183 * Braces can be used to make a pattern into an atom. The "\z(\)" construct 1184 * is only for syntax highlighting. 1185 * 1186 * atom ::= ordinary-atom 1187 * or \( pattern \) 1188 * or \%( pattern \) 1189 * or \z( pattern \) 1190 */ 1191 static int 1192 nfa_regatom(void) 1193 { 1194 int c; 1195 int charclass; 1196 int equiclass; 1197 int collclass; 1198 int got_coll_char; 1199 char_u *p; 1200 char_u *endp; 1201 char_u *old_regparse = regparse; 1202 int extra = 0; 1203 int emit_range; 1204 int negated; 1205 int result; 1206 int startc = -1; 1207 int endc = -1; 1208 int oldstartc = -1; 1209 int save_prev_at_start = prev_at_start; 1210 1211 c = getchr(); 1212 switch (c) 1213 { 1214 case NUL: 1215 EMSG_RET_FAIL(_(e_nul_found)); 1216 1217 case Magic('^'): 1218 EMIT(NFA_BOL); 1219 break; 1220 1221 case Magic('$'): 1222 EMIT(NFA_EOL); 1223 #if defined(FEAT_SYN_HL) || defined(PROTO) 1224 had_eol = TRUE; 1225 #endif 1226 break; 1227 1228 case Magic('<'): 1229 EMIT(NFA_BOW); 1230 break; 1231 1232 case Magic('>'): 1233 EMIT(NFA_EOW); 1234 break; 1235 1236 case Magic('_'): 1237 c = no_Magic(getchr()); 1238 if (c == NUL) 1239 EMSG_RET_FAIL(_(e_nul_found)); 1240 1241 if (c == '^') /* "\_^" is start-of-line */ 1242 { 1243 EMIT(NFA_BOL); 1244 break; 1245 } 1246 if (c == '$') /* "\_$" is end-of-line */ 1247 { 1248 EMIT(NFA_EOL); 1249 #if defined(FEAT_SYN_HL) || defined(PROTO) 1250 had_eol = TRUE; 1251 #endif 1252 break; 1253 } 1254 1255 extra = NFA_ADD_NL; 1256 1257 /* "\_[" is collection plus newline */ 1258 if (c == '[') 1259 goto collection; 1260 1261 /* "\_x" is character class plus newline */ 1262 /* FALLTHROUGH */ 1263 1264 /* 1265 * Character classes. 1266 */ 1267 case Magic('.'): 1268 case Magic('i'): 1269 case Magic('I'): 1270 case Magic('k'): 1271 case Magic('K'): 1272 case Magic('f'): 1273 case Magic('F'): 1274 case Magic('p'): 1275 case Magic('P'): 1276 case Magic('s'): 1277 case Magic('S'): 1278 case Magic('d'): 1279 case Magic('D'): 1280 case Magic('x'): 1281 case Magic('X'): 1282 case Magic('o'): 1283 case Magic('O'): 1284 case Magic('w'): 1285 case Magic('W'): 1286 case Magic('h'): 1287 case Magic('H'): 1288 case Magic('a'): 1289 case Magic('A'): 1290 case Magic('l'): 1291 case Magic('L'): 1292 case Magic('u'): 1293 case Magic('U'): 1294 p = vim_strchr(classchars, no_Magic(c)); 1295 if (p == NULL) 1296 { 1297 if (extra == NFA_ADD_NL) 1298 { 1299 semsg(_(e_ill_char_class), c); 1300 rc_did_emsg = TRUE; 1301 return FAIL; 1302 } 1303 siemsg("INTERNAL: Unknown character class char: %d", c); 1304 return FAIL; 1305 } 1306 1307 /* When '.' is followed by a composing char ignore the dot, so that 1308 * the composing char is matched here. */ 1309 if (enc_utf8 && c == Magic('.') && utf_iscomposing(peekchr())) 1310 { 1311 old_regparse = regparse; 1312 c = getchr(); 1313 goto nfa_do_multibyte; 1314 } 1315 EMIT(nfa_classcodes[p - classchars]); 1316 if (extra == NFA_ADD_NL) 1317 { 1318 EMIT(NFA_NEWL); 1319 EMIT(NFA_OR); 1320 regflags |= RF_HASNL; 1321 } 1322 break; 1323 1324 case Magic('n'): 1325 if (reg_string) 1326 /* In a string "\n" matches a newline character. */ 1327 EMIT(NL); 1328 else 1329 { 1330 /* In buffer text "\n" matches the end of a line. */ 1331 EMIT(NFA_NEWL); 1332 regflags |= RF_HASNL; 1333 } 1334 break; 1335 1336 case Magic('('): 1337 if (nfa_reg(REG_PAREN) == FAIL) 1338 return FAIL; /* cascaded error */ 1339 break; 1340 1341 case Magic('|'): 1342 case Magic('&'): 1343 case Magic(')'): 1344 semsg(_(e_misplaced), no_Magic(c)); 1345 return FAIL; 1346 1347 case Magic('='): 1348 case Magic('?'): 1349 case Magic('+'): 1350 case Magic('@'): 1351 case Magic('*'): 1352 case Magic('{'): 1353 /* these should follow an atom, not form an atom */ 1354 semsg(_(e_misplaced), no_Magic(c)); 1355 return FAIL; 1356 1357 case Magic('~'): 1358 { 1359 char_u *lp; 1360 1361 /* Previous substitute pattern. 1362 * Generated as "\%(pattern\)". */ 1363 if (reg_prev_sub == NULL) 1364 { 1365 emsg(_(e_nopresub)); 1366 return FAIL; 1367 } 1368 for (lp = reg_prev_sub; *lp != NUL; MB_CPTR_ADV(lp)) 1369 { 1370 EMIT(PTR2CHAR(lp)); 1371 if (lp != reg_prev_sub) 1372 EMIT(NFA_CONCAT); 1373 } 1374 EMIT(NFA_NOPEN); 1375 break; 1376 } 1377 1378 case Magic('1'): 1379 case Magic('2'): 1380 case Magic('3'): 1381 case Magic('4'): 1382 case Magic('5'): 1383 case Magic('6'): 1384 case Magic('7'): 1385 case Magic('8'): 1386 case Magic('9'): 1387 { 1388 int refnum = no_Magic(c) - '1'; 1389 1390 if (!seen_endbrace(refnum + 1)) 1391 return FAIL; 1392 EMIT(NFA_BACKREF1 + refnum); 1393 rex.nfa_has_backref = TRUE; 1394 } 1395 break; 1396 1397 case Magic('z'): 1398 c = no_Magic(getchr()); 1399 switch (c) 1400 { 1401 case 's': 1402 EMIT(NFA_ZSTART); 1403 if (re_mult_next("\\zs") == FAIL) 1404 return FAIL; 1405 break; 1406 case 'e': 1407 EMIT(NFA_ZEND); 1408 rex.nfa_has_zend = TRUE; 1409 if (re_mult_next("\\ze") == FAIL) 1410 return FAIL; 1411 break; 1412 #ifdef FEAT_SYN_HL 1413 case '1': 1414 case '2': 1415 case '3': 1416 case '4': 1417 case '5': 1418 case '6': 1419 case '7': 1420 case '8': 1421 case '9': 1422 /* \z1...\z9 */ 1423 if ((reg_do_extmatch & REX_USE) == 0) 1424 EMSG_RET_FAIL(_(e_z1_not_allowed)); 1425 EMIT(NFA_ZREF1 + (no_Magic(c) - '1')); 1426 /* No need to set rex.nfa_has_backref, the sub-matches don't 1427 * change when \z1 .. \z9 matches or not. */ 1428 re_has_z = REX_USE; 1429 break; 1430 case '(': 1431 /* \z( */ 1432 if ((reg_do_extmatch & REX_SET) == 0) 1433 EMSG_RET_FAIL(_(e_z_not_allowed)); 1434 if (nfa_reg(REG_ZPAREN) == FAIL) 1435 return FAIL; /* cascaded error */ 1436 re_has_z = REX_SET; 1437 break; 1438 #endif 1439 default: 1440 semsg(_("E867: (NFA) Unknown operator '\\z%c'"), 1441 no_Magic(c)); 1442 return FAIL; 1443 } 1444 break; 1445 1446 case Magic('%'): 1447 c = no_Magic(getchr()); 1448 switch (c) 1449 { 1450 /* () without a back reference */ 1451 case '(': 1452 if (nfa_reg(REG_NPAREN) == FAIL) 1453 return FAIL; 1454 EMIT(NFA_NOPEN); 1455 break; 1456 1457 case 'd': /* %d123 decimal */ 1458 case 'o': /* %o123 octal */ 1459 case 'x': /* %xab hex 2 */ 1460 case 'u': /* %uabcd hex 4 */ 1461 case 'U': /* %U1234abcd hex 8 */ 1462 { 1463 long nr; 1464 1465 switch (c) 1466 { 1467 case 'd': nr = getdecchrs(); break; 1468 case 'o': nr = getoctchrs(); break; 1469 case 'x': nr = gethexchrs(2); break; 1470 case 'u': nr = gethexchrs(4); break; 1471 case 'U': nr = gethexchrs(8); break; 1472 default: nr = -1; break; 1473 } 1474 1475 if (nr < 0) 1476 EMSG2_RET_FAIL( 1477 _("E678: Invalid character after %s%%[dxouU]"), 1478 reg_magic == MAGIC_ALL); 1479 /* A NUL is stored in the text as NL */ 1480 /* TODO: what if a composing character follows? */ 1481 EMIT(nr == 0 ? 0x0a : nr); 1482 } 1483 break; 1484 1485 /* Catch \%^ and \%$ regardless of where they appear in the 1486 * pattern -- regardless of whether or not it makes sense. */ 1487 case '^': 1488 EMIT(NFA_BOF); 1489 break; 1490 1491 case '$': 1492 EMIT(NFA_EOF); 1493 break; 1494 1495 case '#': 1496 EMIT(NFA_CURSOR); 1497 break; 1498 1499 case 'V': 1500 EMIT(NFA_VISUAL); 1501 break; 1502 1503 case 'C': 1504 EMIT(NFA_ANY_COMPOSING); 1505 break; 1506 1507 case '[': 1508 { 1509 int n; 1510 1511 /* \%[abc] */ 1512 for (n = 0; (c = peekchr()) != ']'; ++n) 1513 { 1514 if (c == NUL) 1515 EMSG2_RET_FAIL(_(e_missing_sb), 1516 reg_magic == MAGIC_ALL); 1517 /* recursive call! */ 1518 if (nfa_regatom() == FAIL) 1519 return FAIL; 1520 } 1521 getchr(); /* get the ] */ 1522 if (n == 0) 1523 EMSG2_RET_FAIL(_(e_empty_sb), 1524 reg_magic == MAGIC_ALL); 1525 EMIT(NFA_OPT_CHARS); 1526 EMIT(n); 1527 1528 /* Emit as "\%(\%[abc]\)" to be able to handle 1529 * "\%[abc]*" which would cause the empty string to be 1530 * matched an unlimited number of times. NFA_NOPEN is 1531 * added only once at a position, while NFA_SPLIT is 1532 * added multiple times. This is more efficient than 1533 * not allowing NFA_SPLIT multiple times, it is used 1534 * a lot. */ 1535 EMIT(NFA_NOPEN); 1536 break; 1537 } 1538 1539 default: 1540 { 1541 long n = 0; 1542 int cmp = c; 1543 1544 if (c == '<' || c == '>') 1545 c = getchr(); 1546 while (VIM_ISDIGIT(c)) 1547 { 1548 n = n * 10 + (c - '0'); 1549 c = getchr(); 1550 } 1551 if (c == 'l' || c == 'c' || c == 'v') 1552 { 1553 if (c == 'l') 1554 { 1555 /* \%{n}l \%{n}<l \%{n}>l */ 1556 EMIT(cmp == '<' ? NFA_LNUM_LT : 1557 cmp == '>' ? NFA_LNUM_GT : NFA_LNUM); 1558 if (save_prev_at_start) 1559 at_start = TRUE; 1560 } 1561 else if (c == 'c') 1562 /* \%{n}c \%{n}<c \%{n}>c */ 1563 EMIT(cmp == '<' ? NFA_COL_LT : 1564 cmp == '>' ? NFA_COL_GT : NFA_COL); 1565 else 1566 /* \%{n}v \%{n}<v \%{n}>v */ 1567 EMIT(cmp == '<' ? NFA_VCOL_LT : 1568 cmp == '>' ? NFA_VCOL_GT : NFA_VCOL); 1569 #if VIM_SIZEOF_INT < VIM_SIZEOF_LONG 1570 if (n > INT_MAX) 1571 { 1572 emsg(_("E951: \\% value too large")); 1573 return FAIL; 1574 } 1575 #endif 1576 EMIT((int)n); 1577 break; 1578 } 1579 else if (c == '\'' && n == 0) 1580 { 1581 /* \%'m \%<'m \%>'m */ 1582 EMIT(cmp == '<' ? NFA_MARK_LT : 1583 cmp == '>' ? NFA_MARK_GT : NFA_MARK); 1584 EMIT(getchr()); 1585 break; 1586 } 1587 } 1588 semsg(_("E867: (NFA) Unknown operator '\\%%%c'"), 1589 no_Magic(c)); 1590 return FAIL; 1591 } 1592 break; 1593 1594 case Magic('['): 1595 collection: 1596 /* 1597 * [abc] uses NFA_START_COLL - NFA_END_COLL 1598 * [^abc] uses NFA_START_NEG_COLL - NFA_END_NEG_COLL 1599 * Each character is produced as a regular state, using 1600 * NFA_CONCAT to bind them together. 1601 * Besides normal characters there can be: 1602 * - character classes NFA_CLASS_* 1603 * - ranges, two characters followed by NFA_RANGE. 1604 */ 1605 1606 p = regparse; 1607 endp = skip_anyof(p); 1608 if (*endp == ']') 1609 { 1610 /* 1611 * Try to reverse engineer character classes. For example, 1612 * recognize that [0-9] stands for \d and [A-Za-z_] for \h, 1613 * and perform the necessary substitutions in the NFA. 1614 */ 1615 result = nfa_recognize_char_class(regparse, endp, 1616 extra == NFA_ADD_NL); 1617 if (result != FAIL) 1618 { 1619 if (result >= NFA_FIRST_NL && result <= NFA_LAST_NL) 1620 { 1621 EMIT(result - NFA_ADD_NL); 1622 EMIT(NFA_NEWL); 1623 EMIT(NFA_OR); 1624 } 1625 else 1626 EMIT(result); 1627 regparse = endp; 1628 MB_PTR_ADV(regparse); 1629 return OK; 1630 } 1631 /* 1632 * Failed to recognize a character class. Use the simple 1633 * version that turns [abc] into 'a' OR 'b' OR 'c' 1634 */ 1635 startc = endc = oldstartc = -1; 1636 negated = FALSE; 1637 if (*regparse == '^') /* negated range */ 1638 { 1639 negated = TRUE; 1640 MB_PTR_ADV(regparse); 1641 EMIT(NFA_START_NEG_COLL); 1642 } 1643 else 1644 EMIT(NFA_START_COLL); 1645 if (*regparse == '-') 1646 { 1647 startc = '-'; 1648 EMIT(startc); 1649 EMIT(NFA_CONCAT); 1650 MB_PTR_ADV(regparse); 1651 } 1652 /* Emit the OR branches for each character in the [] */ 1653 emit_range = FALSE; 1654 while (regparse < endp) 1655 { 1656 oldstartc = startc; 1657 startc = -1; 1658 got_coll_char = FALSE; 1659 if (*regparse == '[') 1660 { 1661 /* Check for [: :], [= =], [. .] */ 1662 equiclass = collclass = 0; 1663 charclass = get_char_class(®parse); 1664 if (charclass == CLASS_NONE) 1665 { 1666 equiclass = get_equi_class(®parse); 1667 if (equiclass == 0) 1668 collclass = get_coll_element(®parse); 1669 } 1670 1671 /* Character class like [:alpha:] */ 1672 if (charclass != CLASS_NONE) 1673 { 1674 switch (charclass) 1675 { 1676 case CLASS_ALNUM: 1677 EMIT(NFA_CLASS_ALNUM); 1678 break; 1679 case CLASS_ALPHA: 1680 EMIT(NFA_CLASS_ALPHA); 1681 break; 1682 case CLASS_BLANK: 1683 EMIT(NFA_CLASS_BLANK); 1684 break; 1685 case CLASS_CNTRL: 1686 EMIT(NFA_CLASS_CNTRL); 1687 break; 1688 case CLASS_DIGIT: 1689 EMIT(NFA_CLASS_DIGIT); 1690 break; 1691 case CLASS_GRAPH: 1692 EMIT(NFA_CLASS_GRAPH); 1693 break; 1694 case CLASS_LOWER: 1695 EMIT(NFA_CLASS_LOWER); 1696 break; 1697 case CLASS_PRINT: 1698 EMIT(NFA_CLASS_PRINT); 1699 break; 1700 case CLASS_PUNCT: 1701 EMIT(NFA_CLASS_PUNCT); 1702 break; 1703 case CLASS_SPACE: 1704 EMIT(NFA_CLASS_SPACE); 1705 break; 1706 case CLASS_UPPER: 1707 EMIT(NFA_CLASS_UPPER); 1708 break; 1709 case CLASS_XDIGIT: 1710 EMIT(NFA_CLASS_XDIGIT); 1711 break; 1712 case CLASS_TAB: 1713 EMIT(NFA_CLASS_TAB); 1714 break; 1715 case CLASS_RETURN: 1716 EMIT(NFA_CLASS_RETURN); 1717 break; 1718 case CLASS_BACKSPACE: 1719 EMIT(NFA_CLASS_BACKSPACE); 1720 break; 1721 case CLASS_ESCAPE: 1722 EMIT(NFA_CLASS_ESCAPE); 1723 break; 1724 case CLASS_IDENT: 1725 EMIT(NFA_CLASS_IDENT); 1726 break; 1727 case CLASS_KEYWORD: 1728 EMIT(NFA_CLASS_KEYWORD); 1729 break; 1730 case CLASS_FNAME: 1731 EMIT(NFA_CLASS_FNAME); 1732 break; 1733 } 1734 EMIT(NFA_CONCAT); 1735 continue; 1736 } 1737 /* Try equivalence class [=a=] and the like */ 1738 if (equiclass != 0) 1739 { 1740 result = nfa_emit_equi_class(equiclass); 1741 if (result == FAIL) 1742 { 1743 /* should never happen */ 1744 EMSG_RET_FAIL(_("E868: Error building NFA with equivalence class!")); 1745 } 1746 continue; 1747 } 1748 /* Try collating class like [. .] */ 1749 if (collclass != 0) 1750 { 1751 startc = collclass; /* allow [.a.]-x as a range */ 1752 /* Will emit the proper atom at the end of the 1753 * while loop. */ 1754 } 1755 } 1756 /* Try a range like 'a-x' or '\t-z'. Also allows '-' as a 1757 * start character. */ 1758 if (*regparse == '-' && oldstartc != -1) 1759 { 1760 emit_range = TRUE; 1761 startc = oldstartc; 1762 MB_PTR_ADV(regparse); 1763 continue; /* reading the end of the range */ 1764 } 1765 1766 /* Now handle simple and escaped characters. 1767 * Only "\]", "\^", "\]" and "\\" are special in Vi. Vim 1768 * accepts "\t", "\e", etc., but only when the 'l' flag in 1769 * 'cpoptions' is not included. 1770 * Posix doesn't recognize backslash at all. 1771 */ 1772 if (*regparse == '\\' 1773 && !reg_cpo_bsl 1774 && regparse + 1 <= endp 1775 && (vim_strchr(REGEXP_INRANGE, regparse[1]) != NULL 1776 || (!reg_cpo_lit 1777 && vim_strchr(REGEXP_ABBR, regparse[1]) 1778 != NULL) 1779 ) 1780 ) 1781 { 1782 MB_PTR_ADV(regparse); 1783 1784 if (*regparse == 'n') 1785 startc = reg_string ? NL : NFA_NEWL; 1786 else 1787 if (*regparse == 'd' 1788 || *regparse == 'o' 1789 || *regparse == 'x' 1790 || *regparse == 'u' 1791 || *regparse == 'U' 1792 ) 1793 { 1794 /* TODO(RE) This needs more testing */ 1795 startc = coll_get_char(); 1796 got_coll_char = TRUE; 1797 MB_PTR_BACK(old_regparse, regparse); 1798 } 1799 else 1800 { 1801 /* \r,\t,\e,\b */ 1802 startc = backslash_trans(*regparse); 1803 } 1804 } 1805 1806 /* Normal printable char */ 1807 if (startc == -1) 1808 startc = PTR2CHAR(regparse); 1809 1810 /* Previous char was '-', so this char is end of range. */ 1811 if (emit_range) 1812 { 1813 endc = startc; 1814 startc = oldstartc; 1815 if (startc > endc) 1816 EMSG_RET_FAIL(_(e_reverse_range)); 1817 1818 if (endc > startc + 2) 1819 { 1820 /* Emit a range instead of the sequence of 1821 * individual characters. */ 1822 if (startc == 0) 1823 /* \x00 is translated to \x0a, start at \x01. */ 1824 EMIT(1); 1825 else 1826 --post_ptr; /* remove NFA_CONCAT */ 1827 EMIT(endc); 1828 EMIT(NFA_RANGE); 1829 EMIT(NFA_CONCAT); 1830 } 1831 else if (has_mbyte && ((*mb_char2len)(startc) > 1 1832 || (*mb_char2len)(endc) > 1)) 1833 { 1834 /* Emit the characters in the range. 1835 * "startc" was already emitted, so skip it. 1836 * */ 1837 for (c = startc + 1; c <= endc; c++) 1838 { 1839 EMIT(c); 1840 EMIT(NFA_CONCAT); 1841 } 1842 } 1843 else 1844 { 1845 #ifdef EBCDIC 1846 int alpha_only = FALSE; 1847 1848 /* for alphabetical range skip the gaps 1849 * 'i'-'j', 'r'-'s', 'I'-'J' and 'R'-'S'. */ 1850 if (isalpha(startc) && isalpha(endc)) 1851 alpha_only = TRUE; 1852 #endif 1853 /* Emit the range. "startc" was already emitted, so 1854 * skip it. */ 1855 for (c = startc + 1; c <= endc; c++) 1856 #ifdef EBCDIC 1857 if (!alpha_only || isalpha(startc)) 1858 #endif 1859 { 1860 EMIT(c); 1861 EMIT(NFA_CONCAT); 1862 } 1863 } 1864 emit_range = FALSE; 1865 startc = -1; 1866 } 1867 else 1868 { 1869 /* This char (startc) is not part of a range. Just 1870 * emit it. 1871 * Normally, simply emit startc. But if we get char 1872 * code=0 from a collating char, then replace it with 1873 * 0x0a. 1874 * This is needed to completely mimic the behaviour of 1875 * the backtracking engine. */ 1876 if (startc == NFA_NEWL) 1877 { 1878 /* Line break can't be matched as part of the 1879 * collection, add an OR below. But not for negated 1880 * range. */ 1881 if (!negated) 1882 extra = NFA_ADD_NL; 1883 } 1884 else 1885 { 1886 if (got_coll_char == TRUE && startc == 0) 1887 EMIT(0x0a); 1888 else 1889 EMIT(startc); 1890 EMIT(NFA_CONCAT); 1891 } 1892 } 1893 1894 MB_PTR_ADV(regparse); 1895 } /* while (p < endp) */ 1896 1897 MB_PTR_BACK(old_regparse, regparse); 1898 if (*regparse == '-') /* if last, '-' is just a char */ 1899 { 1900 EMIT('-'); 1901 EMIT(NFA_CONCAT); 1902 } 1903 1904 /* skip the trailing ] */ 1905 regparse = endp; 1906 MB_PTR_ADV(regparse); 1907 1908 /* Mark end of the collection. */ 1909 if (negated == TRUE) 1910 EMIT(NFA_END_NEG_COLL); 1911 else 1912 EMIT(NFA_END_COLL); 1913 1914 /* \_[] also matches \n but it's not negated */ 1915 if (extra == NFA_ADD_NL) 1916 { 1917 EMIT(reg_string ? NL : NFA_NEWL); 1918 EMIT(NFA_OR); 1919 } 1920 1921 return OK; 1922 } /* if exists closing ] */ 1923 1924 if (reg_strict) 1925 EMSG_RET_FAIL(_(e_missingbracket)); 1926 /* FALLTHROUGH */ 1927 1928 default: 1929 { 1930 int plen; 1931 1932 nfa_do_multibyte: 1933 /* plen is length of current char with composing chars */ 1934 if (enc_utf8 && ((*mb_char2len)(c) 1935 != (plen = utfc_ptr2len(old_regparse)) 1936 || utf_iscomposing(c))) 1937 { 1938 int i = 0; 1939 1940 /* A base character plus composing characters, or just one 1941 * or more composing characters. 1942 * This requires creating a separate atom as if enclosing 1943 * the characters in (), where NFA_COMPOSING is the ( and 1944 * NFA_END_COMPOSING is the ). Note that right now we are 1945 * building the postfix form, not the NFA itself; 1946 * a composing char could be: a, b, c, NFA_COMPOSING 1947 * where 'b' and 'c' are chars with codes > 256. */ 1948 for (;;) 1949 { 1950 EMIT(c); 1951 if (i > 0) 1952 EMIT(NFA_CONCAT); 1953 if ((i += utf_char2len(c)) >= plen) 1954 break; 1955 c = utf_ptr2char(old_regparse + i); 1956 } 1957 EMIT(NFA_COMPOSING); 1958 regparse = old_regparse + plen; 1959 } 1960 else 1961 { 1962 c = no_Magic(c); 1963 EMIT(c); 1964 } 1965 return OK; 1966 } 1967 } 1968 1969 return OK; 1970 } 1971 1972 /* 1973 * Parse something followed by possible [*+=]. 1974 * 1975 * A piece is an atom, possibly followed by a multi, an indication of how many 1976 * times the atom can be matched. Example: "a*" matches any sequence of "a" 1977 * characters: "", "a", "aa", etc. 1978 * 1979 * piece ::= atom 1980 * or atom multi 1981 */ 1982 static int 1983 nfa_regpiece(void) 1984 { 1985 int i; 1986 int op; 1987 int ret; 1988 long minval, maxval; 1989 int greedy = TRUE; /* Braces are prefixed with '-' ? */ 1990 parse_state_T old_state; 1991 parse_state_T new_state; 1992 long c2; 1993 int old_post_pos; 1994 int my_post_start; 1995 int quest; 1996 1997 /* Save the current parse state, so that we can use it if <atom>{m,n} is 1998 * next. */ 1999 save_parse_state(&old_state); 2000 2001 /* store current pos in the postfix form, for \{m,n} involving 0s */ 2002 my_post_start = (int)(post_ptr - post_start); 2003 2004 ret = nfa_regatom(); 2005 if (ret == FAIL) 2006 return FAIL; /* cascaded error */ 2007 2008 op = peekchr(); 2009 if (re_multi_type(op) == NOT_MULTI) 2010 return OK; 2011 2012 skipchr(); 2013 switch (op) 2014 { 2015 case Magic('*'): 2016 EMIT(NFA_STAR); 2017 break; 2018 2019 case Magic('+'): 2020 /* 2021 * Trick: Normally, (a*)\+ would match the whole input "aaa". The 2022 * first and only submatch would be "aaa". But the backtracking 2023 * engine interprets the plus as "try matching one more time", and 2024 * a* matches a second time at the end of the input, the empty 2025 * string. 2026 * The submatch will be the empty string. 2027 * 2028 * In order to be consistent with the old engine, we replace 2029 * <atom>+ with <atom><atom>* 2030 */ 2031 restore_parse_state(&old_state); 2032 curchr = -1; 2033 if (nfa_regatom() == FAIL) 2034 return FAIL; 2035 EMIT(NFA_STAR); 2036 EMIT(NFA_CONCAT); 2037 skipchr(); /* skip the \+ */ 2038 break; 2039 2040 case Magic('@'): 2041 c2 = getdecchrs(); 2042 op = no_Magic(getchr()); 2043 i = 0; 2044 switch(op) 2045 { 2046 case '=': 2047 /* \@= */ 2048 i = NFA_PREV_ATOM_NO_WIDTH; 2049 break; 2050 case '!': 2051 /* \@! */ 2052 i = NFA_PREV_ATOM_NO_WIDTH_NEG; 2053 break; 2054 case '<': 2055 op = no_Magic(getchr()); 2056 if (op == '=') 2057 /* \@<= */ 2058 i = NFA_PREV_ATOM_JUST_BEFORE; 2059 else if (op == '!') 2060 /* \@<! */ 2061 i = NFA_PREV_ATOM_JUST_BEFORE_NEG; 2062 break; 2063 case '>': 2064 /* \@> */ 2065 i = NFA_PREV_ATOM_LIKE_PATTERN; 2066 break; 2067 } 2068 if (i == 0) 2069 { 2070 semsg(_("E869: (NFA) Unknown operator '\\@%c'"), op); 2071 return FAIL; 2072 } 2073 EMIT(i); 2074 if (i == NFA_PREV_ATOM_JUST_BEFORE 2075 || i == NFA_PREV_ATOM_JUST_BEFORE_NEG) 2076 EMIT(c2); 2077 break; 2078 2079 case Magic('?'): 2080 case Magic('='): 2081 EMIT(NFA_QUEST); 2082 break; 2083 2084 case Magic('{'): 2085 /* a{2,5} will expand to 'aaa?a?a?' 2086 * a{-1,3} will expand to 'aa??a??', where ?? is the nongreedy 2087 * version of '?' 2088 * \v(ab){2,3} will expand to '(ab)(ab)(ab)?', where all the 2089 * parenthesis have the same id 2090 */ 2091 2092 greedy = TRUE; 2093 c2 = peekchr(); 2094 if (c2 == '-' || c2 == Magic('-')) 2095 { 2096 skipchr(); 2097 greedy = FALSE; 2098 } 2099 if (!read_limits(&minval, &maxval)) 2100 EMSG_RET_FAIL(_("E870: (NFA regexp) Error reading repetition limits")); 2101 2102 /* <atom>{0,inf}, <atom>{0,} and <atom>{} are equivalent to 2103 * <atom>* */ 2104 if (minval == 0 && maxval == MAX_LIMIT) 2105 { 2106 if (greedy) /* { { (match the braces) */ 2107 /* \{}, \{0,} */ 2108 EMIT(NFA_STAR); 2109 else /* { { (match the braces) */ 2110 /* \{-}, \{-0,} */ 2111 EMIT(NFA_STAR_NONGREEDY); 2112 break; 2113 } 2114 2115 /* Special case: x{0} or x{-0} */ 2116 if (maxval == 0) 2117 { 2118 /* Ignore result of previous call to nfa_regatom() */ 2119 post_ptr = post_start + my_post_start; 2120 /* NFA_EMPTY is 0-length and works everywhere */ 2121 EMIT(NFA_EMPTY); 2122 return OK; 2123 } 2124 2125 /* The engine is very inefficient (uses too many states) when the 2126 * maximum is much larger than the minimum and when the maximum is 2127 * large. Bail out if we can use the other engine. */ 2128 if ((nfa_re_flags & RE_AUTO) 2129 && (maxval > 500 || maxval > minval + 200)) 2130 return FAIL; 2131 2132 /* Ignore previous call to nfa_regatom() */ 2133 post_ptr = post_start + my_post_start; 2134 /* Save parse state after the repeated atom and the \{} */ 2135 save_parse_state(&new_state); 2136 2137 quest = (greedy == TRUE? NFA_QUEST : NFA_QUEST_NONGREEDY); 2138 for (i = 0; i < maxval; i++) 2139 { 2140 /* Goto beginning of the repeated atom */ 2141 restore_parse_state(&old_state); 2142 old_post_pos = (int)(post_ptr - post_start); 2143 if (nfa_regatom() == FAIL) 2144 return FAIL; 2145 /* after "minval" times, atoms are optional */ 2146 if (i + 1 > minval) 2147 { 2148 if (maxval == MAX_LIMIT) 2149 { 2150 if (greedy) 2151 EMIT(NFA_STAR); 2152 else 2153 EMIT(NFA_STAR_NONGREEDY); 2154 } 2155 else 2156 EMIT(quest); 2157 } 2158 if (old_post_pos != my_post_start) 2159 EMIT(NFA_CONCAT); 2160 if (i + 1 > minval && maxval == MAX_LIMIT) 2161 break; 2162 } 2163 2164 /* Go to just after the repeated atom and the \{} */ 2165 restore_parse_state(&new_state); 2166 curchr = -1; 2167 2168 break; 2169 2170 2171 default: 2172 break; 2173 } /* end switch */ 2174 2175 if (re_multi_type(peekchr()) != NOT_MULTI) 2176 /* Can't have a multi follow a multi. */ 2177 EMSG_RET_FAIL(_("E871: (NFA regexp) Can't have a multi follow a multi")); 2178 2179 return OK; 2180 } 2181 2182 /* 2183 * Parse one or more pieces, concatenated. It matches a match for the 2184 * first piece, followed by a match for the second piece, etc. Example: 2185 * "f[0-9]b", first matches "f", then a digit and then "b". 2186 * 2187 * concat ::= piece 2188 * or piece piece 2189 * or piece piece piece 2190 * etc. 2191 */ 2192 static int 2193 nfa_regconcat(void) 2194 { 2195 int cont = TRUE; 2196 int first = TRUE; 2197 2198 while (cont) 2199 { 2200 switch (peekchr()) 2201 { 2202 case NUL: 2203 case Magic('|'): 2204 case Magic('&'): 2205 case Magic(')'): 2206 cont = FALSE; 2207 break; 2208 2209 case Magic('Z'): 2210 regflags |= RF_ICOMBINE; 2211 skipchr_keepstart(); 2212 break; 2213 case Magic('c'): 2214 regflags |= RF_ICASE; 2215 skipchr_keepstart(); 2216 break; 2217 case Magic('C'): 2218 regflags |= RF_NOICASE; 2219 skipchr_keepstart(); 2220 break; 2221 case Magic('v'): 2222 reg_magic = MAGIC_ALL; 2223 skipchr_keepstart(); 2224 curchr = -1; 2225 break; 2226 case Magic('m'): 2227 reg_magic = MAGIC_ON; 2228 skipchr_keepstart(); 2229 curchr = -1; 2230 break; 2231 case Magic('M'): 2232 reg_magic = MAGIC_OFF; 2233 skipchr_keepstart(); 2234 curchr = -1; 2235 break; 2236 case Magic('V'): 2237 reg_magic = MAGIC_NONE; 2238 skipchr_keepstart(); 2239 curchr = -1; 2240 break; 2241 2242 default: 2243 if (nfa_regpiece() == FAIL) 2244 return FAIL; 2245 if (first == FALSE) 2246 EMIT(NFA_CONCAT); 2247 else 2248 first = FALSE; 2249 break; 2250 } 2251 } 2252 2253 return OK; 2254 } 2255 2256 /* 2257 * Parse a branch, one or more concats, separated by "\&". It matches the 2258 * last concat, but only if all the preceding concats also match at the same 2259 * position. Examples: 2260 * "foobeep\&..." matches "foo" in "foobeep". 2261 * ".*Peter\&.*Bob" matches in a line containing both "Peter" and "Bob" 2262 * 2263 * branch ::= concat 2264 * or concat \& concat 2265 * or concat \& concat \& concat 2266 * etc. 2267 */ 2268 static int 2269 nfa_regbranch(void) 2270 { 2271 int old_post_pos; 2272 2273 old_post_pos = (int)(post_ptr - post_start); 2274 2275 /* First branch, possibly the only one */ 2276 if (nfa_regconcat() == FAIL) 2277 return FAIL; 2278 2279 /* Try next concats */ 2280 while (peekchr() == Magic('&')) 2281 { 2282 skipchr(); 2283 /* if concat is empty do emit a node */ 2284 if (old_post_pos == (int)(post_ptr - post_start)) 2285 EMIT(NFA_EMPTY); 2286 EMIT(NFA_NOPEN); 2287 EMIT(NFA_PREV_ATOM_NO_WIDTH); 2288 old_post_pos = (int)(post_ptr - post_start); 2289 if (nfa_regconcat() == FAIL) 2290 return FAIL; 2291 /* if concat is empty do emit a node */ 2292 if (old_post_pos == (int)(post_ptr - post_start)) 2293 EMIT(NFA_EMPTY); 2294 EMIT(NFA_CONCAT); 2295 } 2296 2297 /* if a branch is empty, emit one node for it */ 2298 if (old_post_pos == (int)(post_ptr - post_start)) 2299 EMIT(NFA_EMPTY); 2300 2301 return OK; 2302 } 2303 2304 /* 2305 * Parse a pattern, one or more branches, separated by "\|". It matches 2306 * anything that matches one of the branches. Example: "foo\|beep" matches 2307 * "foo" and matches "beep". If more than one branch matches, the first one 2308 * is used. 2309 * 2310 * pattern ::= branch 2311 * or branch \| branch 2312 * or branch \| branch \| branch 2313 * etc. 2314 */ 2315 static int 2316 nfa_reg( 2317 int paren) /* REG_NOPAREN, REG_PAREN, REG_NPAREN or REG_ZPAREN */ 2318 { 2319 int parno = 0; 2320 2321 if (paren == REG_PAREN) 2322 { 2323 if (regnpar >= NSUBEXP) /* Too many `(' */ 2324 EMSG_RET_FAIL(_("E872: (NFA regexp) Too many '('")); 2325 parno = regnpar++; 2326 } 2327 #ifdef FEAT_SYN_HL 2328 else if (paren == REG_ZPAREN) 2329 { 2330 /* Make a ZOPEN node. */ 2331 if (regnzpar >= NSUBEXP) 2332 EMSG_RET_FAIL(_("E879: (NFA regexp) Too many \\z(")); 2333 parno = regnzpar++; 2334 } 2335 #endif 2336 2337 if (nfa_regbranch() == FAIL) 2338 return FAIL; /* cascaded error */ 2339 2340 while (peekchr() == Magic('|')) 2341 { 2342 skipchr(); 2343 if (nfa_regbranch() == FAIL) 2344 return FAIL; /* cascaded error */ 2345 EMIT(NFA_OR); 2346 } 2347 2348 /* Check for proper termination. */ 2349 if (paren != REG_NOPAREN && getchr() != Magic(')')) 2350 { 2351 if (paren == REG_NPAREN) 2352 EMSG2_RET_FAIL(_(e_unmatchedpp), reg_magic == MAGIC_ALL); 2353 else 2354 EMSG2_RET_FAIL(_(e_unmatchedp), reg_magic == MAGIC_ALL); 2355 } 2356 else if (paren == REG_NOPAREN && peekchr() != NUL) 2357 { 2358 if (peekchr() == Magic(')')) 2359 EMSG2_RET_FAIL(_(e_unmatchedpar), reg_magic == MAGIC_ALL); 2360 else 2361 EMSG_RET_FAIL(_("E873: (NFA regexp) proper termination error")); 2362 } 2363 /* 2364 * Here we set the flag allowing back references to this set of 2365 * parentheses. 2366 */ 2367 if (paren == REG_PAREN) 2368 { 2369 had_endbrace[parno] = TRUE; /* have seen the close paren */ 2370 EMIT(NFA_MOPEN + parno); 2371 } 2372 #ifdef FEAT_SYN_HL 2373 else if (paren == REG_ZPAREN) 2374 EMIT(NFA_ZOPEN + parno); 2375 #endif 2376 2377 return OK; 2378 } 2379 2380 #ifdef DEBUG 2381 static char_u code[50]; 2382 2383 static void 2384 nfa_set_code(int c) 2385 { 2386 int addnl = FALSE; 2387 2388 if (c >= NFA_FIRST_NL && c <= NFA_LAST_NL) 2389 { 2390 addnl = TRUE; 2391 c -= NFA_ADD_NL; 2392 } 2393 2394 STRCPY(code, ""); 2395 switch (c) 2396 { 2397 case NFA_MATCH: STRCPY(code, "NFA_MATCH "); break; 2398 case NFA_SPLIT: STRCPY(code, "NFA_SPLIT "); break; 2399 case NFA_CONCAT: STRCPY(code, "NFA_CONCAT "); break; 2400 case NFA_NEWL: STRCPY(code, "NFA_NEWL "); break; 2401 case NFA_ZSTART: STRCPY(code, "NFA_ZSTART"); break; 2402 case NFA_ZEND: STRCPY(code, "NFA_ZEND"); break; 2403 2404 case NFA_BACKREF1: STRCPY(code, "NFA_BACKREF1"); break; 2405 case NFA_BACKREF2: STRCPY(code, "NFA_BACKREF2"); break; 2406 case NFA_BACKREF3: STRCPY(code, "NFA_BACKREF3"); break; 2407 case NFA_BACKREF4: STRCPY(code, "NFA_BACKREF4"); break; 2408 case NFA_BACKREF5: STRCPY(code, "NFA_BACKREF5"); break; 2409 case NFA_BACKREF6: STRCPY(code, "NFA_BACKREF6"); break; 2410 case NFA_BACKREF7: STRCPY(code, "NFA_BACKREF7"); break; 2411 case NFA_BACKREF8: STRCPY(code, "NFA_BACKREF8"); break; 2412 case NFA_BACKREF9: STRCPY(code, "NFA_BACKREF9"); break; 2413 #ifdef FEAT_SYN_HL 2414 case NFA_ZREF1: STRCPY(code, "NFA_ZREF1"); break; 2415 case NFA_ZREF2: STRCPY(code, "NFA_ZREF2"); break; 2416 case NFA_ZREF3: STRCPY(code, "NFA_ZREF3"); break; 2417 case NFA_ZREF4: STRCPY(code, "NFA_ZREF4"); break; 2418 case NFA_ZREF5: STRCPY(code, "NFA_ZREF5"); break; 2419 case NFA_ZREF6: STRCPY(code, "NFA_ZREF6"); break; 2420 case NFA_ZREF7: STRCPY(code, "NFA_ZREF7"); break; 2421 case NFA_ZREF8: STRCPY(code, "NFA_ZREF8"); break; 2422 case NFA_ZREF9: STRCPY(code, "NFA_ZREF9"); break; 2423 #endif 2424 case NFA_SKIP: STRCPY(code, "NFA_SKIP"); break; 2425 2426 case NFA_PREV_ATOM_NO_WIDTH: 2427 STRCPY(code, "NFA_PREV_ATOM_NO_WIDTH"); break; 2428 case NFA_PREV_ATOM_NO_WIDTH_NEG: 2429 STRCPY(code, "NFA_PREV_ATOM_NO_WIDTH_NEG"); break; 2430 case NFA_PREV_ATOM_JUST_BEFORE: 2431 STRCPY(code, "NFA_PREV_ATOM_JUST_BEFORE"); break; 2432 case NFA_PREV_ATOM_JUST_BEFORE_NEG: 2433 STRCPY(code, "NFA_PREV_ATOM_JUST_BEFORE_NEG"); break; 2434 case NFA_PREV_ATOM_LIKE_PATTERN: 2435 STRCPY(code, "NFA_PREV_ATOM_LIKE_PATTERN"); break; 2436 2437 case NFA_NOPEN: STRCPY(code, "NFA_NOPEN"); break; 2438 case NFA_NCLOSE: STRCPY(code, "NFA_NCLOSE"); break; 2439 case NFA_START_INVISIBLE: STRCPY(code, "NFA_START_INVISIBLE"); break; 2440 case NFA_START_INVISIBLE_FIRST: 2441 STRCPY(code, "NFA_START_INVISIBLE_FIRST"); break; 2442 case NFA_START_INVISIBLE_NEG: 2443 STRCPY(code, "NFA_START_INVISIBLE_NEG"); break; 2444 case NFA_START_INVISIBLE_NEG_FIRST: 2445 STRCPY(code, "NFA_START_INVISIBLE_NEG_FIRST"); break; 2446 case NFA_START_INVISIBLE_BEFORE: 2447 STRCPY(code, "NFA_START_INVISIBLE_BEFORE"); break; 2448 case NFA_START_INVISIBLE_BEFORE_FIRST: 2449 STRCPY(code, "NFA_START_INVISIBLE_BEFORE_FIRST"); break; 2450 case NFA_START_INVISIBLE_BEFORE_NEG: 2451 STRCPY(code, "NFA_START_INVISIBLE_BEFORE_NEG"); break; 2452 case NFA_START_INVISIBLE_BEFORE_NEG_FIRST: 2453 STRCPY(code, "NFA_START_INVISIBLE_BEFORE_NEG_FIRST"); break; 2454 case NFA_START_PATTERN: STRCPY(code, "NFA_START_PATTERN"); break; 2455 case NFA_END_INVISIBLE: STRCPY(code, "NFA_END_INVISIBLE"); break; 2456 case NFA_END_INVISIBLE_NEG: STRCPY(code, "NFA_END_INVISIBLE_NEG"); break; 2457 case NFA_END_PATTERN: STRCPY(code, "NFA_END_PATTERN"); break; 2458 2459 case NFA_COMPOSING: STRCPY(code, "NFA_COMPOSING"); break; 2460 case NFA_END_COMPOSING: STRCPY(code, "NFA_END_COMPOSING"); break; 2461 case NFA_OPT_CHARS: STRCPY(code, "NFA_OPT_CHARS"); break; 2462 2463 case NFA_MOPEN: 2464 case NFA_MOPEN1: 2465 case NFA_MOPEN2: 2466 case NFA_MOPEN3: 2467 case NFA_MOPEN4: 2468 case NFA_MOPEN5: 2469 case NFA_MOPEN6: 2470 case NFA_MOPEN7: 2471 case NFA_MOPEN8: 2472 case NFA_MOPEN9: 2473 STRCPY(code, "NFA_MOPEN(x)"); 2474 code[10] = c - NFA_MOPEN + '0'; 2475 break; 2476 case NFA_MCLOSE: 2477 case NFA_MCLOSE1: 2478 case NFA_MCLOSE2: 2479 case NFA_MCLOSE3: 2480 case NFA_MCLOSE4: 2481 case NFA_MCLOSE5: 2482 case NFA_MCLOSE6: 2483 case NFA_MCLOSE7: 2484 case NFA_MCLOSE8: 2485 case NFA_MCLOSE9: 2486 STRCPY(code, "NFA_MCLOSE(x)"); 2487 code[11] = c - NFA_MCLOSE + '0'; 2488 break; 2489 #ifdef FEAT_SYN_HL 2490 case NFA_ZOPEN: 2491 case NFA_ZOPEN1: 2492 case NFA_ZOPEN2: 2493 case NFA_ZOPEN3: 2494 case NFA_ZOPEN4: 2495 case NFA_ZOPEN5: 2496 case NFA_ZOPEN6: 2497 case NFA_ZOPEN7: 2498 case NFA_ZOPEN8: 2499 case NFA_ZOPEN9: 2500 STRCPY(code, "NFA_ZOPEN(x)"); 2501 code[10] = c - NFA_ZOPEN + '0'; 2502 break; 2503 case NFA_ZCLOSE: 2504 case NFA_ZCLOSE1: 2505 case NFA_ZCLOSE2: 2506 case NFA_ZCLOSE3: 2507 case NFA_ZCLOSE4: 2508 case NFA_ZCLOSE5: 2509 case NFA_ZCLOSE6: 2510 case NFA_ZCLOSE7: 2511 case NFA_ZCLOSE8: 2512 case NFA_ZCLOSE9: 2513 STRCPY(code, "NFA_ZCLOSE(x)"); 2514 code[11] = c - NFA_ZCLOSE + '0'; 2515 break; 2516 #endif 2517 case NFA_EOL: STRCPY(code, "NFA_EOL "); break; 2518 case NFA_BOL: STRCPY(code, "NFA_BOL "); break; 2519 case NFA_EOW: STRCPY(code, "NFA_EOW "); break; 2520 case NFA_BOW: STRCPY(code, "NFA_BOW "); break; 2521 case NFA_EOF: STRCPY(code, "NFA_EOF "); break; 2522 case NFA_BOF: STRCPY(code, "NFA_BOF "); break; 2523 case NFA_LNUM: STRCPY(code, "NFA_LNUM "); break; 2524 case NFA_LNUM_GT: STRCPY(code, "NFA_LNUM_GT "); break; 2525 case NFA_LNUM_LT: STRCPY(code, "NFA_LNUM_LT "); break; 2526 case NFA_COL: STRCPY(code, "NFA_COL "); break; 2527 case NFA_COL_GT: STRCPY(code, "NFA_COL_GT "); break; 2528 case NFA_COL_LT: STRCPY(code, "NFA_COL_LT "); break; 2529 case NFA_VCOL: STRCPY(code, "NFA_VCOL "); break; 2530 case NFA_VCOL_GT: STRCPY(code, "NFA_VCOL_GT "); break; 2531 case NFA_VCOL_LT: STRCPY(code, "NFA_VCOL_LT "); break; 2532 case NFA_MARK: STRCPY(code, "NFA_MARK "); break; 2533 case NFA_MARK_GT: STRCPY(code, "NFA_MARK_GT "); break; 2534 case NFA_MARK_LT: STRCPY(code, "NFA_MARK_LT "); break; 2535 case NFA_CURSOR: STRCPY(code, "NFA_CURSOR "); break; 2536 case NFA_VISUAL: STRCPY(code, "NFA_VISUAL "); break; 2537 case NFA_ANY_COMPOSING: STRCPY(code, "NFA_ANY_COMPOSING "); break; 2538 2539 case NFA_STAR: STRCPY(code, "NFA_STAR "); break; 2540 case NFA_STAR_NONGREEDY: STRCPY(code, "NFA_STAR_NONGREEDY "); break; 2541 case NFA_QUEST: STRCPY(code, "NFA_QUEST"); break; 2542 case NFA_QUEST_NONGREEDY: STRCPY(code, "NFA_QUEST_NON_GREEDY"); break; 2543 case NFA_EMPTY: STRCPY(code, "NFA_EMPTY"); break; 2544 case NFA_OR: STRCPY(code, "NFA_OR"); break; 2545 2546 case NFA_START_COLL: STRCPY(code, "NFA_START_COLL"); break; 2547 case NFA_END_COLL: STRCPY(code, "NFA_END_COLL"); break; 2548 case NFA_START_NEG_COLL: STRCPY(code, "NFA_START_NEG_COLL"); break; 2549 case NFA_END_NEG_COLL: STRCPY(code, "NFA_END_NEG_COLL"); break; 2550 case NFA_RANGE: STRCPY(code, "NFA_RANGE"); break; 2551 case NFA_RANGE_MIN: STRCPY(code, "NFA_RANGE_MIN"); break; 2552 case NFA_RANGE_MAX: STRCPY(code, "NFA_RANGE_MAX"); break; 2553 2554 case NFA_CLASS_ALNUM: STRCPY(code, "NFA_CLASS_ALNUM"); break; 2555 case NFA_CLASS_ALPHA: STRCPY(code, "NFA_CLASS_ALPHA"); break; 2556 case NFA_CLASS_BLANK: STRCPY(code, "NFA_CLASS_BLANK"); break; 2557 case NFA_CLASS_CNTRL: STRCPY(code, "NFA_CLASS_CNTRL"); break; 2558 case NFA_CLASS_DIGIT: STRCPY(code, "NFA_CLASS_DIGIT"); break; 2559 case NFA_CLASS_GRAPH: STRCPY(code, "NFA_CLASS_GRAPH"); break; 2560 case NFA_CLASS_LOWER: STRCPY(code, "NFA_CLASS_LOWER"); break; 2561 case NFA_CLASS_PRINT: STRCPY(code, "NFA_CLASS_PRINT"); break; 2562 case NFA_CLASS_PUNCT: STRCPY(code, "NFA_CLASS_PUNCT"); break; 2563 case NFA_CLASS_SPACE: STRCPY(code, "NFA_CLASS_SPACE"); break; 2564 case NFA_CLASS_UPPER: STRCPY(code, "NFA_CLASS_UPPER"); break; 2565 case NFA_CLASS_XDIGIT: STRCPY(code, "NFA_CLASS_XDIGIT"); break; 2566 case NFA_CLASS_TAB: STRCPY(code, "NFA_CLASS_TAB"); break; 2567 case NFA_CLASS_RETURN: STRCPY(code, "NFA_CLASS_RETURN"); break; 2568 case NFA_CLASS_BACKSPACE: STRCPY(code, "NFA_CLASS_BACKSPACE"); break; 2569 case NFA_CLASS_ESCAPE: STRCPY(code, "NFA_CLASS_ESCAPE"); break; 2570 case NFA_CLASS_IDENT: STRCPY(code, "NFA_CLASS_IDENT"); break; 2571 case NFA_CLASS_KEYWORD: STRCPY(code, "NFA_CLASS_KEYWORD"); break; 2572 case NFA_CLASS_FNAME: STRCPY(code, "NFA_CLASS_FNAME"); break; 2573 2574 case NFA_ANY: STRCPY(code, "NFA_ANY"); break; 2575 case NFA_IDENT: STRCPY(code, "NFA_IDENT"); break; 2576 case NFA_SIDENT:STRCPY(code, "NFA_SIDENT"); break; 2577 case NFA_KWORD: STRCPY(code, "NFA_KWORD"); break; 2578 case NFA_SKWORD:STRCPY(code, "NFA_SKWORD"); break; 2579 case NFA_FNAME: STRCPY(code, "NFA_FNAME"); break; 2580 case NFA_SFNAME:STRCPY(code, "NFA_SFNAME"); break; 2581 case NFA_PRINT: STRCPY(code, "NFA_PRINT"); break; 2582 case NFA_SPRINT:STRCPY(code, "NFA_SPRINT"); break; 2583 case NFA_WHITE: STRCPY(code, "NFA_WHITE"); break; 2584 case NFA_NWHITE:STRCPY(code, "NFA_NWHITE"); break; 2585 case NFA_DIGIT: STRCPY(code, "NFA_DIGIT"); break; 2586 case NFA_NDIGIT:STRCPY(code, "NFA_NDIGIT"); break; 2587 case NFA_HEX: STRCPY(code, "NFA_HEX"); break; 2588 case NFA_NHEX: STRCPY(code, "NFA_NHEX"); break; 2589 case NFA_OCTAL: STRCPY(code, "NFA_OCTAL"); break; 2590 case NFA_NOCTAL:STRCPY(code, "NFA_NOCTAL"); break; 2591 case NFA_WORD: STRCPY(code, "NFA_WORD"); break; 2592 case NFA_NWORD: STRCPY(code, "NFA_NWORD"); break; 2593 case NFA_HEAD: STRCPY(code, "NFA_HEAD"); break; 2594 case NFA_NHEAD: STRCPY(code, "NFA_NHEAD"); break; 2595 case NFA_ALPHA: STRCPY(code, "NFA_ALPHA"); break; 2596 case NFA_NALPHA:STRCPY(code, "NFA_NALPHA"); break; 2597 case NFA_LOWER: STRCPY(code, "NFA_LOWER"); break; 2598 case NFA_NLOWER:STRCPY(code, "NFA_NLOWER"); break; 2599 case NFA_UPPER: STRCPY(code, "NFA_UPPER"); break; 2600 case NFA_NUPPER:STRCPY(code, "NFA_NUPPER"); break; 2601 case NFA_LOWER_IC: STRCPY(code, "NFA_LOWER_IC"); break; 2602 case NFA_NLOWER_IC: STRCPY(code, "NFA_NLOWER_IC"); break; 2603 case NFA_UPPER_IC: STRCPY(code, "NFA_UPPER_IC"); break; 2604 case NFA_NUPPER_IC: STRCPY(code, "NFA_NUPPER_IC"); break; 2605 2606 default: 2607 STRCPY(code, "CHAR(x)"); 2608 code[5] = c; 2609 } 2610 2611 if (addnl == TRUE) 2612 STRCAT(code, " + NEWLINE "); 2613 2614 } 2615 2616 #ifdef ENABLE_LOG 2617 static FILE *log_fd; 2618 static char_u e_log_open_failed[] = N_("Could not open temporary log file for writing, displaying on stderr... "); 2619 2620 /* 2621 * Print the postfix notation of the current regexp. 2622 */ 2623 static void 2624 nfa_postfix_dump(char_u *expr, int retval) 2625 { 2626 int *p; 2627 FILE *f; 2628 2629 f = fopen(NFA_REGEXP_DUMP_LOG, "a"); 2630 if (f != NULL) 2631 { 2632 fprintf(f, "\n-------------------------\n"); 2633 if (retval == FAIL) 2634 fprintf(f, ">>> NFA engine failed... \n"); 2635 else if (retval == OK) 2636 fprintf(f, ">>> NFA engine succeeded !\n"); 2637 fprintf(f, "Regexp: \"%s\"\nPostfix notation (char): \"", expr); 2638 for (p = post_start; *p && p < post_ptr; p++) 2639 { 2640 nfa_set_code(*p); 2641 fprintf(f, "%s, ", code); 2642 } 2643 fprintf(f, "\"\nPostfix notation (int): "); 2644 for (p = post_start; *p && p < post_ptr; p++) 2645 fprintf(f, "%d ", *p); 2646 fprintf(f, "\n\n"); 2647 fclose(f); 2648 } 2649 } 2650 2651 /* 2652 * Print the NFA starting with a root node "state". 2653 */ 2654 static void 2655 nfa_print_state(FILE *debugf, nfa_state_T *state) 2656 { 2657 garray_T indent; 2658 2659 ga_init2(&indent, 1, 64); 2660 ga_append(&indent, '\0'); 2661 nfa_print_state2(debugf, state, &indent); 2662 ga_clear(&indent); 2663 } 2664 2665 static void 2666 nfa_print_state2(FILE *debugf, nfa_state_T *state, garray_T *indent) 2667 { 2668 char_u *p; 2669 2670 if (state == NULL) 2671 return; 2672 2673 fprintf(debugf, "(%2d)", abs(state->id)); 2674 2675 /* Output indent */ 2676 p = (char_u *)indent->ga_data; 2677 if (indent->ga_len >= 3) 2678 { 2679 int last = indent->ga_len - 3; 2680 char_u save[2]; 2681 2682 STRNCPY(save, &p[last], 2); 2683 STRNCPY(&p[last], "+-", 2); 2684 fprintf(debugf, " %s", p); 2685 STRNCPY(&p[last], save, 2); 2686 } 2687 else 2688 fprintf(debugf, " %s", p); 2689 2690 nfa_set_code(state->c); 2691 fprintf(debugf, "%s (%d) (id=%d) val=%d\n", 2692 code, 2693 state->c, 2694 abs(state->id), 2695 state->val); 2696 if (state->id < 0) 2697 return; 2698 2699 state->id = abs(state->id) * -1; 2700 2701 /* grow indent for state->out */ 2702 indent->ga_len -= 1; 2703 if (state->out1) 2704 ga_concat(indent, (char_u *)"| "); 2705 else 2706 ga_concat(indent, (char_u *)" "); 2707 ga_append(indent, '\0'); 2708 2709 nfa_print_state2(debugf, state->out, indent); 2710 2711 /* replace last part of indent for state->out1 */ 2712 indent->ga_len -= 3; 2713 ga_concat(indent, (char_u *)" "); 2714 ga_append(indent, '\0'); 2715 2716 nfa_print_state2(debugf, state->out1, indent); 2717 2718 /* shrink indent */ 2719 indent->ga_len -= 3; 2720 ga_append(indent, '\0'); 2721 } 2722 2723 /* 2724 * Print the NFA state machine. 2725 */ 2726 static void 2727 nfa_dump(nfa_regprog_T *prog) 2728 { 2729 FILE *debugf = fopen(NFA_REGEXP_DUMP_LOG, "a"); 2730 2731 if (debugf != NULL) 2732 { 2733 nfa_print_state(debugf, prog->start); 2734 2735 if (prog->reganch) 2736 fprintf(debugf, "reganch: %d\n", prog->reganch); 2737 if (prog->regstart != NUL) 2738 fprintf(debugf, "regstart: %c (decimal: %d)\n", 2739 prog->regstart, prog->regstart); 2740 if (prog->match_text != NULL) 2741 fprintf(debugf, "match_text: \"%s\"\n", prog->match_text); 2742 2743 fclose(debugf); 2744 } 2745 } 2746 #endif /* ENABLE_LOG */ 2747 #endif /* DEBUG */ 2748 2749 /* 2750 * Parse r.e. @expr and convert it into postfix form. 2751 * Return the postfix string on success, NULL otherwise. 2752 */ 2753 static int * 2754 re2post(void) 2755 { 2756 if (nfa_reg(REG_NOPAREN) == FAIL) 2757 return NULL; 2758 EMIT(NFA_MOPEN); 2759 return post_start; 2760 } 2761 2762 /* NB. Some of the code below is inspired by Russ's. */ 2763 2764 /* 2765 * Represents an NFA state plus zero or one or two arrows exiting. 2766 * if c == MATCH, no arrows out; matching state. 2767 * If c == SPLIT, unlabeled arrows to out and out1 (if != NULL). 2768 * If c < 256, labeled arrow with character c to out. 2769 */ 2770 2771 static nfa_state_T *state_ptr; /* points to nfa_prog->state */ 2772 2773 /* 2774 * Allocate and initialize nfa_state_T. 2775 */ 2776 static nfa_state_T * 2777 alloc_state(int c, nfa_state_T *out, nfa_state_T *out1) 2778 { 2779 nfa_state_T *s; 2780 2781 if (istate >= nstate) 2782 return NULL; 2783 2784 s = &state_ptr[istate++]; 2785 2786 s->c = c; 2787 s->out = out; 2788 s->out1 = out1; 2789 s->val = 0; 2790 2791 s->id = istate; 2792 s->lastlist[0] = 0; 2793 s->lastlist[1] = 0; 2794 2795 return s; 2796 } 2797 2798 /* 2799 * A partially built NFA without the matching state filled in. 2800 * Frag_T.start points at the start state. 2801 * Frag_T.out is a list of places that need to be set to the 2802 * next state for this fragment. 2803 */ 2804 2805 /* Since the out pointers in the list are always 2806 * uninitialized, we use the pointers themselves 2807 * as storage for the Ptrlists. */ 2808 typedef union Ptrlist Ptrlist; 2809 union Ptrlist 2810 { 2811 Ptrlist *next; 2812 nfa_state_T *s; 2813 }; 2814 2815 struct Frag 2816 { 2817 nfa_state_T *start; 2818 Ptrlist *out; 2819 }; 2820 typedef struct Frag Frag_T; 2821 2822 /* 2823 * Initialize a Frag_T struct and return it. 2824 */ 2825 static Frag_T 2826 frag(nfa_state_T *start, Ptrlist *out) 2827 { 2828 Frag_T n; 2829 2830 n.start = start; 2831 n.out = out; 2832 return n; 2833 } 2834 2835 /* 2836 * Create singleton list containing just outp. 2837 */ 2838 static Ptrlist * 2839 list1( 2840 nfa_state_T **outp) 2841 { 2842 Ptrlist *l; 2843 2844 l = (Ptrlist *)outp; 2845 l->next = NULL; 2846 return l; 2847 } 2848 2849 /* 2850 * Patch the list of states at out to point to start. 2851 */ 2852 static void 2853 patch(Ptrlist *l, nfa_state_T *s) 2854 { 2855 Ptrlist *next; 2856 2857 for (; l; l = next) 2858 { 2859 next = l->next; 2860 l->s = s; 2861 } 2862 } 2863 2864 2865 /* 2866 * Join the two lists l1 and l2, returning the combination. 2867 */ 2868 static Ptrlist * 2869 append(Ptrlist *l1, Ptrlist *l2) 2870 { 2871 Ptrlist *oldl1; 2872 2873 oldl1 = l1; 2874 while (l1->next) 2875 l1 = l1->next; 2876 l1->next = l2; 2877 return oldl1; 2878 } 2879 2880 /* 2881 * Stack used for transforming postfix form into NFA. 2882 */ 2883 static Frag_T empty; 2884 2885 static void 2886 st_error(int *postfix UNUSED, int *end UNUSED, int *p UNUSED) 2887 { 2888 #ifdef NFA_REGEXP_ERROR_LOG 2889 FILE *df; 2890 int *p2; 2891 2892 df = fopen(NFA_REGEXP_ERROR_LOG, "a"); 2893 if (df) 2894 { 2895 fprintf(df, "Error popping the stack!\n"); 2896 # ifdef DEBUG 2897 fprintf(df, "Current regexp is \"%s\"\n", nfa_regengine.expr); 2898 # endif 2899 fprintf(df, "Postfix form is: "); 2900 # ifdef DEBUG 2901 for (p2 = postfix; p2 < end; p2++) 2902 { 2903 nfa_set_code(*p2); 2904 fprintf(df, "%s, ", code); 2905 } 2906 nfa_set_code(*p); 2907 fprintf(df, "\nCurrent position is: "); 2908 for (p2 = postfix; p2 <= p; p2 ++) 2909 { 2910 nfa_set_code(*p2); 2911 fprintf(df, "%s, ", code); 2912 } 2913 # else 2914 for (p2 = postfix; p2 < end; p2++) 2915 { 2916 fprintf(df, "%d, ", *p2); 2917 } 2918 fprintf(df, "\nCurrent position is: "); 2919 for (p2 = postfix; p2 <= p; p2 ++) 2920 { 2921 fprintf(df, "%d, ", *p2); 2922 } 2923 # endif 2924 fprintf(df, "\n--------------------------\n"); 2925 fclose(df); 2926 } 2927 #endif 2928 emsg(_("E874: (NFA) Could not pop the stack!")); 2929 } 2930 2931 /* 2932 * Push an item onto the stack. 2933 */ 2934 static void 2935 st_push(Frag_T s, Frag_T **p, Frag_T *stack_end) 2936 { 2937 Frag_T *stackp = *p; 2938 2939 if (stackp >= stack_end) 2940 return; 2941 *stackp = s; 2942 *p = *p + 1; 2943 } 2944 2945 /* 2946 * Pop an item from the stack. 2947 */ 2948 static Frag_T 2949 st_pop(Frag_T **p, Frag_T *stack) 2950 { 2951 Frag_T *stackp; 2952 2953 *p = *p - 1; 2954 stackp = *p; 2955 if (stackp < stack) 2956 return empty; 2957 return **p; 2958 } 2959 2960 /* 2961 * Estimate the maximum byte length of anything matching "state". 2962 * When unknown or unlimited return -1. 2963 */ 2964 static int 2965 nfa_max_width(nfa_state_T *startstate, int depth) 2966 { 2967 int l, r; 2968 nfa_state_T *state = startstate; 2969 int len = 0; 2970 2971 /* detect looping in a NFA_SPLIT */ 2972 if (depth > 4) 2973 return -1; 2974 2975 while (state != NULL) 2976 { 2977 switch (state->c) 2978 { 2979 case NFA_END_INVISIBLE: 2980 case NFA_END_INVISIBLE_NEG: 2981 /* the end, return what we have */ 2982 return len; 2983 2984 case NFA_SPLIT: 2985 /* two alternatives, use the maximum */ 2986 l = nfa_max_width(state->out, depth + 1); 2987 r = nfa_max_width(state->out1, depth + 1); 2988 if (l < 0 || r < 0) 2989 return -1; 2990 return len + (l > r ? l : r); 2991 2992 case NFA_ANY: 2993 case NFA_START_COLL: 2994 case NFA_START_NEG_COLL: 2995 /* matches some character, including composing chars */ 2996 if (enc_utf8) 2997 len += MB_MAXBYTES; 2998 else if (has_mbyte) 2999 len += 2; 3000 else 3001 ++len; 3002 if (state->c != NFA_ANY) 3003 { 3004 /* skip over the characters */ 3005 state = state->out1->out; 3006 continue; 3007 } 3008 break; 3009 3010 case NFA_DIGIT: 3011 case NFA_WHITE: 3012 case NFA_HEX: 3013 case NFA_OCTAL: 3014 /* ascii */ 3015 ++len; 3016 break; 3017 3018 case NFA_IDENT: 3019 case NFA_SIDENT: 3020 case NFA_KWORD: 3021 case NFA_SKWORD: 3022 case NFA_FNAME: 3023 case NFA_SFNAME: 3024 case NFA_PRINT: 3025 case NFA_SPRINT: 3026 case NFA_NWHITE: 3027 case NFA_NDIGIT: 3028 case NFA_NHEX: 3029 case NFA_NOCTAL: 3030 case NFA_WORD: 3031 case NFA_NWORD: 3032 case NFA_HEAD: 3033 case NFA_NHEAD: 3034 case NFA_ALPHA: 3035 case NFA_NALPHA: 3036 case NFA_LOWER: 3037 case NFA_NLOWER: 3038 case NFA_UPPER: 3039 case NFA_NUPPER: 3040 case NFA_LOWER_IC: 3041 case NFA_NLOWER_IC: 3042 case NFA_UPPER_IC: 3043 case NFA_NUPPER_IC: 3044 case NFA_ANY_COMPOSING: 3045 /* possibly non-ascii */ 3046 if (has_mbyte) 3047 len += 3; 3048 else 3049 ++len; 3050 break; 3051 3052 case NFA_START_INVISIBLE: 3053 case NFA_START_INVISIBLE_NEG: 3054 case NFA_START_INVISIBLE_BEFORE: 3055 case NFA_START_INVISIBLE_BEFORE_NEG: 3056 /* zero-width, out1 points to the END state */ 3057 state = state->out1->out; 3058 continue; 3059 3060 case NFA_BACKREF1: 3061 case NFA_BACKREF2: 3062 case NFA_BACKREF3: 3063 case NFA_BACKREF4: 3064 case NFA_BACKREF5: 3065 case NFA_BACKREF6: 3066 case NFA_BACKREF7: 3067 case NFA_BACKREF8: 3068 case NFA_BACKREF9: 3069 #ifdef FEAT_SYN_HL 3070 case NFA_ZREF1: 3071 case NFA_ZREF2: 3072 case NFA_ZREF3: 3073 case NFA_ZREF4: 3074 case NFA_ZREF5: 3075 case NFA_ZREF6: 3076 case NFA_ZREF7: 3077 case NFA_ZREF8: 3078 case NFA_ZREF9: 3079 #endif 3080 case NFA_NEWL: 3081 case NFA_SKIP: 3082 /* unknown width */ 3083 return -1; 3084 3085 case NFA_BOL: 3086 case NFA_EOL: 3087 case NFA_BOF: 3088 case NFA_EOF: 3089 case NFA_BOW: 3090 case NFA_EOW: 3091 case NFA_MOPEN: 3092 case NFA_MOPEN1: 3093 case NFA_MOPEN2: 3094 case NFA_MOPEN3: 3095 case NFA_MOPEN4: 3096 case NFA_MOPEN5: 3097 case NFA_MOPEN6: 3098 case NFA_MOPEN7: 3099 case NFA_MOPEN8: 3100 case NFA_MOPEN9: 3101 #ifdef FEAT_SYN_HL 3102 case NFA_ZOPEN: 3103 case NFA_ZOPEN1: 3104 case NFA_ZOPEN2: 3105 case NFA_ZOPEN3: 3106 case NFA_ZOPEN4: 3107 case NFA_ZOPEN5: 3108 case NFA_ZOPEN6: 3109 case NFA_ZOPEN7: 3110 case NFA_ZOPEN8: 3111 case NFA_ZOPEN9: 3112 case NFA_ZCLOSE: 3113 case NFA_ZCLOSE1: 3114 case NFA_ZCLOSE2: 3115 case NFA_ZCLOSE3: 3116 case NFA_ZCLOSE4: 3117 case NFA_ZCLOSE5: 3118 case NFA_ZCLOSE6: 3119 case NFA_ZCLOSE7: 3120 case NFA_ZCLOSE8: 3121 case NFA_ZCLOSE9: 3122 #endif 3123 case NFA_MCLOSE: 3124 case NFA_MCLOSE1: 3125 case NFA_MCLOSE2: 3126 case NFA_MCLOSE3: 3127 case NFA_MCLOSE4: 3128 case NFA_MCLOSE5: 3129 case NFA_MCLOSE6: 3130 case NFA_MCLOSE7: 3131 case NFA_MCLOSE8: 3132 case NFA_MCLOSE9: 3133 case NFA_NOPEN: 3134 case NFA_NCLOSE: 3135 3136 case NFA_LNUM_GT: 3137 case NFA_LNUM_LT: 3138 case NFA_COL_GT: 3139 case NFA_COL_LT: 3140 case NFA_VCOL_GT: 3141 case NFA_VCOL_LT: 3142 case NFA_MARK_GT: 3143 case NFA_MARK_LT: 3144 case NFA_VISUAL: 3145 case NFA_LNUM: 3146 case NFA_CURSOR: 3147 case NFA_COL: 3148 case NFA_VCOL: 3149 case NFA_MARK: 3150 3151 case NFA_ZSTART: 3152 case NFA_ZEND: 3153 case NFA_OPT_CHARS: 3154 case NFA_EMPTY: 3155 case NFA_START_PATTERN: 3156 case NFA_END_PATTERN: 3157 case NFA_COMPOSING: 3158 case NFA_END_COMPOSING: 3159 /* zero-width */ 3160 break; 3161 3162 default: 3163 if (state->c < 0) 3164 /* don't know what this is */ 3165 return -1; 3166 /* normal character */ 3167 len += MB_CHAR2LEN(state->c); 3168 break; 3169 } 3170 3171 /* normal way to continue */ 3172 state = state->out; 3173 } 3174 3175 /* unrecognized, "cannot happen" */ 3176 return -1; 3177 } 3178 3179 /* 3180 * Convert a postfix form into its equivalent NFA. 3181 * Return the NFA start state on success, NULL otherwise. 3182 */ 3183 static nfa_state_T * 3184 post2nfa(int *postfix, int *end, int nfa_calc_size) 3185 { 3186 int *p; 3187 int mopen; 3188 int mclose; 3189 Frag_T *stack = NULL; 3190 Frag_T *stackp = NULL; 3191 Frag_T *stack_end = NULL; 3192 Frag_T e1; 3193 Frag_T e2; 3194 Frag_T e; 3195 nfa_state_T *s; 3196 nfa_state_T *s1; 3197 nfa_state_T *matchstate; 3198 nfa_state_T *ret = NULL; 3199 3200 if (postfix == NULL) 3201 return NULL; 3202 3203 #define PUSH(s) st_push((s), &stackp, stack_end) 3204 #define POP() st_pop(&stackp, stack); \ 3205 if (stackp < stack) \ 3206 { \ 3207 st_error(postfix, end, p); \ 3208 vim_free(stack); \ 3209 return NULL; \ 3210 } 3211 3212 if (nfa_calc_size == FALSE) 3213 { 3214 // Allocate space for the stack. Max states on the stack: "nstate'. 3215 stack = (Frag_T *)lalloc((nstate + 1) * sizeof(Frag_T), TRUE); 3216 if (stack == NULL) 3217 return NULL; 3218 stackp = stack; 3219 stack_end = stack + (nstate + 1); 3220 } 3221 3222 for (p = postfix; p < end; ++p) 3223 { 3224 switch (*p) 3225 { 3226 case NFA_CONCAT: 3227 /* Concatenation. 3228 * Pay attention: this operator does not exist in the r.e. itself 3229 * (it is implicit, really). It is added when r.e. is translated 3230 * to postfix form in re2post(). */ 3231 if (nfa_calc_size == TRUE) 3232 { 3233 /* nstate += 0; */ 3234 break; 3235 } 3236 e2 = POP(); 3237 e1 = POP(); 3238 patch(e1.out, e2.start); 3239 PUSH(frag(e1.start, e2.out)); 3240 break; 3241 3242 case NFA_OR: 3243 /* Alternation */ 3244 if (nfa_calc_size == TRUE) 3245 { 3246 nstate++; 3247 break; 3248 } 3249 e2 = POP(); 3250 e1 = POP(); 3251 s = alloc_state(NFA_SPLIT, e1.start, e2.start); 3252 if (s == NULL) 3253 goto theend; 3254 PUSH(frag(s, append(e1.out, e2.out))); 3255 break; 3256 3257 case NFA_STAR: 3258 /* Zero or more, prefer more */ 3259 if (nfa_calc_size == TRUE) 3260 { 3261 nstate++; 3262 break; 3263 } 3264 e = POP(); 3265 s = alloc_state(NFA_SPLIT, e.start, NULL); 3266 if (s == NULL) 3267 goto theend; 3268 patch(e.out, s); 3269 PUSH(frag(s, list1(&s->out1))); 3270 break; 3271 3272 case NFA_STAR_NONGREEDY: 3273 /* Zero or more, prefer zero */ 3274 if (nfa_calc_size == TRUE) 3275 { 3276 nstate++; 3277 break; 3278 } 3279 e = POP(); 3280 s = alloc_state(NFA_SPLIT, NULL, e.start); 3281 if (s == NULL) 3282 goto theend; 3283 patch(e.out, s); 3284 PUSH(frag(s, list1(&s->out))); 3285 break; 3286 3287 case NFA_QUEST: 3288 /* one or zero atoms=> greedy match */ 3289 if (nfa_calc_size == TRUE) 3290 { 3291 nstate++; 3292 break; 3293 } 3294 e = POP(); 3295 s = alloc_state(NFA_SPLIT, e.start, NULL); 3296 if (s == NULL) 3297 goto theend; 3298 PUSH(frag(s, append(e.out, list1(&s->out1)))); 3299 break; 3300 3301 case NFA_QUEST_NONGREEDY: 3302 /* zero or one atoms => non-greedy match */ 3303 if (nfa_calc_size == TRUE) 3304 { 3305 nstate++; 3306 break; 3307 } 3308 e = POP(); 3309 s = alloc_state(NFA_SPLIT, NULL, e.start); 3310 if (s == NULL) 3311 goto theend; 3312 PUSH(frag(s, append(e.out, list1(&s->out)))); 3313 break; 3314 3315 case NFA_END_COLL: 3316 case NFA_END_NEG_COLL: 3317 /* On the stack is the sequence starting with NFA_START_COLL or 3318 * NFA_START_NEG_COLL and all possible characters. Patch it to 3319 * add the output to the start. */ 3320 if (nfa_calc_size == TRUE) 3321 { 3322 nstate++; 3323 break; 3324 } 3325 e = POP(); 3326 s = alloc_state(NFA_END_COLL, NULL, NULL); 3327 if (s == NULL) 3328 goto theend; 3329 patch(e.out, s); 3330 e.start->out1 = s; 3331 PUSH(frag(e.start, list1(&s->out))); 3332 break; 3333 3334 case NFA_RANGE: 3335 /* Before this are two characters, the low and high end of a 3336 * range. Turn them into two states with MIN and MAX. */ 3337 if (nfa_calc_size == TRUE) 3338 { 3339 /* nstate += 0; */ 3340 break; 3341 } 3342 e2 = POP(); 3343 e1 = POP(); 3344 e2.start->val = e2.start->c; 3345 e2.start->c = NFA_RANGE_MAX; 3346 e1.start->val = e1.start->c; 3347 e1.start->c = NFA_RANGE_MIN; 3348 patch(e1.out, e2.start); 3349 PUSH(frag(e1.start, e2.out)); 3350 break; 3351 3352 case NFA_EMPTY: 3353 /* 0-length, used in a repetition with max/min count of 0 */ 3354 if (nfa_calc_size == TRUE) 3355 { 3356 nstate++; 3357 break; 3358 } 3359 s = alloc_state(NFA_EMPTY, NULL, NULL); 3360 if (s == NULL) 3361 goto theend; 3362 PUSH(frag(s, list1(&s->out))); 3363 break; 3364 3365 case NFA_OPT_CHARS: 3366 { 3367 int n; 3368 3369 /* \%[abc] implemented as: 3370 * NFA_SPLIT 3371 * +-CHAR(a) 3372 * | +-NFA_SPLIT 3373 * | +-CHAR(b) 3374 * | | +-NFA_SPLIT 3375 * | | +-CHAR(c) 3376 * | | | +-next 3377 * | | +- next 3378 * | +- next 3379 * +- next 3380 */ 3381 n = *++p; /* get number of characters */ 3382 if (nfa_calc_size == TRUE) 3383 { 3384 nstate += n; 3385 break; 3386 } 3387 s = NULL; /* avoid compiler warning */ 3388 e1.out = NULL; /* stores list with out1's */ 3389 s1 = NULL; /* previous NFA_SPLIT to connect to */ 3390 while (n-- > 0) 3391 { 3392 e = POP(); /* get character */ 3393 s = alloc_state(NFA_SPLIT, e.start, NULL); 3394 if (s == NULL) 3395 goto theend; 3396 if (e1.out == NULL) 3397 e1 = e; 3398 patch(e.out, s1); 3399 append(e1.out, list1(&s->out1)); 3400 s1 = s; 3401 } 3402 PUSH(frag(s, e1.out)); 3403 break; 3404 } 3405 3406 case NFA_PREV_ATOM_NO_WIDTH: 3407 case NFA_PREV_ATOM_NO_WIDTH_NEG: 3408 case NFA_PREV_ATOM_JUST_BEFORE: 3409 case NFA_PREV_ATOM_JUST_BEFORE_NEG: 3410 case NFA_PREV_ATOM_LIKE_PATTERN: 3411 { 3412 int before = (*p == NFA_PREV_ATOM_JUST_BEFORE 3413 || *p == NFA_PREV_ATOM_JUST_BEFORE_NEG); 3414 int pattern = (*p == NFA_PREV_ATOM_LIKE_PATTERN); 3415 int start_state; 3416 int end_state; 3417 int n = 0; 3418 nfa_state_T *zend; 3419 nfa_state_T *skip; 3420 3421 switch (*p) 3422 { 3423 case NFA_PREV_ATOM_NO_WIDTH: 3424 start_state = NFA_START_INVISIBLE; 3425 end_state = NFA_END_INVISIBLE; 3426 break; 3427 case NFA_PREV_ATOM_NO_WIDTH_NEG: 3428 start_state = NFA_START_INVISIBLE_NEG; 3429 end_state = NFA_END_INVISIBLE_NEG; 3430 break; 3431 case NFA_PREV_ATOM_JUST_BEFORE: 3432 start_state = NFA_START_INVISIBLE_BEFORE; 3433 end_state = NFA_END_INVISIBLE; 3434 break; 3435 case NFA_PREV_ATOM_JUST_BEFORE_NEG: 3436 start_state = NFA_START_INVISIBLE_BEFORE_NEG; 3437 end_state = NFA_END_INVISIBLE_NEG; 3438 break; 3439 default: /* NFA_PREV_ATOM_LIKE_PATTERN: */ 3440 start_state = NFA_START_PATTERN; 3441 end_state = NFA_END_PATTERN; 3442 break; 3443 } 3444 3445 if (before) 3446 n = *++p; /* get the count */ 3447 3448 /* The \@= operator: match the preceding atom with zero width. 3449 * The \@! operator: no match for the preceding atom. 3450 * The \@<= operator: match for the preceding atom. 3451 * The \@<! operator: no match for the preceding atom. 3452 * Surrounds the preceding atom with START_INVISIBLE and 3453 * END_INVISIBLE, similarly to MOPEN. */ 3454 3455 if (nfa_calc_size == TRUE) 3456 { 3457 nstate += pattern ? 4 : 2; 3458 break; 3459 } 3460 e = POP(); 3461 s1 = alloc_state(end_state, NULL, NULL); 3462 if (s1 == NULL) 3463 goto theend; 3464 3465 s = alloc_state(start_state, e.start, s1); 3466 if (s == NULL) 3467 goto theend; 3468 if (pattern) 3469 { 3470 /* NFA_ZEND -> NFA_END_PATTERN -> NFA_SKIP -> what follows. */ 3471 skip = alloc_state(NFA_SKIP, NULL, NULL); 3472 if (skip == NULL) 3473 goto theend; 3474 zend = alloc_state(NFA_ZEND, s1, NULL); 3475 if (zend == NULL) 3476 goto theend; 3477 s1->out= skip; 3478 patch(e.out, zend); 3479 PUSH(frag(s, list1(&skip->out))); 3480 } 3481 else 3482 { 3483 patch(e.out, s1); 3484 PUSH(frag(s, list1(&s1->out))); 3485 if (before) 3486 { 3487 if (n <= 0) 3488 /* See if we can guess the maximum width, it avoids a 3489 * lot of pointless tries. */ 3490 n = nfa_max_width(e.start, 0); 3491 s->val = n; /* store the count */ 3492 } 3493 } 3494 break; 3495 } 3496 3497 case NFA_COMPOSING: /* char with composing char */ 3498 #if 0 3499 /* TODO */ 3500 if (regflags & RF_ICOMBINE) 3501 { 3502 /* use the base character only */ 3503 } 3504 #endif 3505 /* FALLTHROUGH */ 3506 3507 case NFA_MOPEN: /* \( \) Submatch */ 3508 case NFA_MOPEN1: 3509 case NFA_MOPEN2: 3510 case NFA_MOPEN3: 3511 case NFA_MOPEN4: 3512 case NFA_MOPEN5: 3513 case NFA_MOPEN6: 3514 case NFA_MOPEN7: 3515 case NFA_MOPEN8: 3516 case NFA_MOPEN9: 3517 #ifdef FEAT_SYN_HL 3518 case NFA_ZOPEN: /* \z( \) Submatch */ 3519 case NFA_ZOPEN1: 3520 case NFA_ZOPEN2: 3521 case NFA_ZOPEN3: 3522 case NFA_ZOPEN4: 3523 case NFA_ZOPEN5: 3524 case NFA_ZOPEN6: 3525 case NFA_ZOPEN7: 3526 case NFA_ZOPEN8: 3527 case NFA_ZOPEN9: 3528 #endif 3529 case NFA_NOPEN: /* \%( \) "Invisible Submatch" */ 3530 if (nfa_calc_size == TRUE) 3531 { 3532 nstate += 2; 3533 break; 3534 } 3535 3536 mopen = *p; 3537 switch (*p) 3538 { 3539 case NFA_NOPEN: mclose = NFA_NCLOSE; break; 3540 #ifdef FEAT_SYN_HL 3541 case NFA_ZOPEN: mclose = NFA_ZCLOSE; break; 3542 case NFA_ZOPEN1: mclose = NFA_ZCLOSE1; break; 3543 case NFA_ZOPEN2: mclose = NFA_ZCLOSE2; break; 3544 case NFA_ZOPEN3: mclose = NFA_ZCLOSE3; break; 3545 case NFA_ZOPEN4: mclose = NFA_ZCLOSE4; break; 3546 case NFA_ZOPEN5: mclose = NFA_ZCLOSE5; break; 3547 case NFA_ZOPEN6: mclose = NFA_ZCLOSE6; break; 3548 case NFA_ZOPEN7: mclose = NFA_ZCLOSE7; break; 3549 case NFA_ZOPEN8: mclose = NFA_ZCLOSE8; break; 3550 case NFA_ZOPEN9: mclose = NFA_ZCLOSE9; break; 3551 #endif 3552 case NFA_COMPOSING: mclose = NFA_END_COMPOSING; break; 3553 default: 3554 /* NFA_MOPEN, NFA_MOPEN1 .. NFA_MOPEN9 */ 3555 mclose = *p + NSUBEXP; 3556 break; 3557 } 3558 3559 /* Allow "NFA_MOPEN" as a valid postfix representation for 3560 * the empty regexp "". In this case, the NFA will be 3561 * NFA_MOPEN -> NFA_MCLOSE. Note that this also allows 3562 * empty groups of parenthesis, and empty mbyte chars */ 3563 if (stackp == stack) 3564 { 3565 s = alloc_state(mopen, NULL, NULL); 3566 if (s == NULL) 3567 goto theend; 3568 s1 = alloc_state(mclose, NULL, NULL); 3569 if (s1 == NULL) 3570 goto theend; 3571 patch(list1(&s->out), s1); 3572 PUSH(frag(s, list1(&s1->out))); 3573 break; 3574 } 3575 3576 /* At least one node was emitted before NFA_MOPEN, so 3577 * at least one node will be between NFA_MOPEN and NFA_MCLOSE */ 3578 e = POP(); 3579 s = alloc_state(mopen, e.start, NULL); /* `(' */ 3580 if (s == NULL) 3581 goto theend; 3582 3583 s1 = alloc_state(mclose, NULL, NULL); /* `)' */ 3584 if (s1 == NULL) 3585 goto theend; 3586 patch(e.out, s1); 3587 3588 if (mopen == NFA_COMPOSING) 3589 /* COMPOSING->out1 = END_COMPOSING */ 3590 patch(list1(&s->out1), s1); 3591 3592 PUSH(frag(s, list1(&s1->out))); 3593 break; 3594 3595 case NFA_BACKREF1: 3596 case NFA_BACKREF2: 3597 case NFA_BACKREF3: 3598 case NFA_BACKREF4: 3599 case NFA_BACKREF5: 3600 case NFA_BACKREF6: 3601 case NFA_BACKREF7: 3602 case NFA_BACKREF8: 3603 case NFA_BACKREF9: 3604 #ifdef FEAT_SYN_HL 3605 case NFA_ZREF1: 3606 case NFA_ZREF2: 3607 case NFA_ZREF3: 3608 case NFA_ZREF4: 3609 case NFA_ZREF5: 3610 case NFA_ZREF6: 3611 case NFA_ZREF7: 3612 case NFA_ZREF8: 3613 case NFA_ZREF9: 3614 #endif 3615 if (nfa_calc_size == TRUE) 3616 { 3617 nstate += 2; 3618 break; 3619 } 3620 s = alloc_state(*p, NULL, NULL); 3621 if (s == NULL) 3622 goto theend; 3623 s1 = alloc_state(NFA_SKIP, NULL, NULL); 3624 if (s1 == NULL) 3625 goto theend; 3626 patch(list1(&s->out), s1); 3627 PUSH(frag(s, list1(&s1->out))); 3628 break; 3629 3630 case NFA_LNUM: 3631 case NFA_LNUM_GT: 3632 case NFA_LNUM_LT: 3633 case NFA_VCOL: 3634 case NFA_VCOL_GT: 3635 case NFA_VCOL_LT: 3636 case NFA_COL: 3637 case NFA_COL_GT: 3638 case NFA_COL_LT: 3639 case NFA_MARK: 3640 case NFA_MARK_GT: 3641 case NFA_MARK_LT: 3642 { 3643 int n = *++p; /* lnum, col or mark name */ 3644 3645 if (nfa_calc_size == TRUE) 3646 { 3647 nstate += 1; 3648 break; 3649 } 3650 s = alloc_state(p[-1], NULL, NULL); 3651 if (s == NULL) 3652 goto theend; 3653 s->val = n; 3654 PUSH(frag(s, list1(&s->out))); 3655 break; 3656 } 3657 3658 case NFA_ZSTART: 3659 case NFA_ZEND: 3660 default: 3661 /* Operands */ 3662 if (nfa_calc_size == TRUE) 3663 { 3664 nstate++; 3665 break; 3666 } 3667 s = alloc_state(*p, NULL, NULL); 3668 if (s == NULL) 3669 goto theend; 3670 PUSH(frag(s, list1(&s->out))); 3671 break; 3672 3673 } /* switch(*p) */ 3674 3675 } /* for(p = postfix; *p; ++p) */ 3676 3677 if (nfa_calc_size == TRUE) 3678 { 3679 nstate++; 3680 goto theend; /* Return value when counting size is ignored anyway */ 3681 } 3682 3683 e = POP(); 3684 if (stackp != stack) 3685 { 3686 vim_free(stack); 3687 EMSG_RET_NULL(_("E875: (NFA regexp) (While converting from postfix to NFA), too many states left on stack")); 3688 } 3689 3690 if (istate >= nstate) 3691 { 3692 vim_free(stack); 3693 EMSG_RET_NULL(_("E876: (NFA regexp) Not enough space to store the whole NFA ")); 3694 } 3695 3696 matchstate = &state_ptr[istate++]; /* the match state */ 3697 matchstate->c = NFA_MATCH; 3698 matchstate->out = matchstate->out1 = NULL; 3699 matchstate->id = 0; 3700 3701 patch(e.out, matchstate); 3702 ret = e.start; 3703 3704 theend: 3705 vim_free(stack); 3706 return ret; 3707 3708 #undef POP1 3709 #undef PUSH1 3710 #undef POP2 3711 #undef PUSH2 3712 #undef POP 3713 #undef PUSH 3714 } 3715 3716 /* 3717 * After building the NFA program, inspect it to add optimization hints. 3718 */ 3719 static void 3720 nfa_postprocess(nfa_regprog_T *prog) 3721 { 3722 int i; 3723 int c; 3724 3725 for (i = 0; i < prog->nstate; ++i) 3726 { 3727 c = prog->state[i].c; 3728 if (c == NFA_START_INVISIBLE 3729 || c == NFA_START_INVISIBLE_NEG 3730 || c == NFA_START_INVISIBLE_BEFORE 3731 || c == NFA_START_INVISIBLE_BEFORE_NEG) 3732 { 3733 int directly; 3734 3735 /* Do it directly when what follows is possibly the end of the 3736 * match. */ 3737 if (match_follows(prog->state[i].out1->out, 0)) 3738 directly = TRUE; 3739 else 3740 { 3741 int ch_invisible = failure_chance(prog->state[i].out, 0); 3742 int ch_follows = failure_chance(prog->state[i].out1->out, 0); 3743 3744 /* Postpone when the invisible match is expensive or has a 3745 * lower chance of failing. */ 3746 if (c == NFA_START_INVISIBLE_BEFORE 3747 || c == NFA_START_INVISIBLE_BEFORE_NEG) 3748 { 3749 /* "before" matches are very expensive when 3750 * unbounded, always prefer what follows then, 3751 * unless what follows will always match. 3752 * Otherwise strongly prefer what follows. */ 3753 if (prog->state[i].val <= 0 && ch_follows > 0) 3754 directly = FALSE; 3755 else 3756 directly = ch_follows * 10 < ch_invisible; 3757 } 3758 else 3759 { 3760 /* normal invisible, first do the one with the 3761 * highest failure chance */ 3762 directly = ch_follows < ch_invisible; 3763 } 3764 } 3765 if (directly) 3766 /* switch to the _FIRST state */ 3767 ++prog->state[i].c; 3768 } 3769 } 3770 } 3771 3772 /**************************************************************** 3773 * NFA execution code. 3774 ****************************************************************/ 3775 3776 typedef struct 3777 { 3778 int in_use; /* number of subexpr with useful info */ 3779 3780 /* When REG_MULTI is TRUE list.multi is used, otherwise list.line. */ 3781 union 3782 { 3783 struct multipos 3784 { 3785 linenr_T start_lnum; 3786 linenr_T end_lnum; 3787 colnr_T start_col; 3788 colnr_T end_col; 3789 } multi[NSUBEXP]; 3790 struct linepos 3791 { 3792 char_u *start; 3793 char_u *end; 3794 } line[NSUBEXP]; 3795 } list; 3796 } regsub_T; 3797 3798 typedef struct 3799 { 3800 regsub_T norm; /* \( .. \) matches */ 3801 #ifdef FEAT_SYN_HL 3802 regsub_T synt; /* \z( .. \) matches */ 3803 #endif 3804 } regsubs_T; 3805 3806 /* nfa_pim_T stores a Postponed Invisible Match. */ 3807 typedef struct nfa_pim_S nfa_pim_T; 3808 struct nfa_pim_S 3809 { 3810 int result; /* NFA_PIM_*, see below */ 3811 nfa_state_T *state; /* the invisible match start state */ 3812 regsubs_T subs; /* submatch info, only party used */ 3813 union 3814 { 3815 lpos_T pos; 3816 char_u *ptr; 3817 } end; /* where the match must end */ 3818 }; 3819 3820 /* Values for done in nfa_pim_T. */ 3821 #define NFA_PIM_UNUSED 0 /* pim not used */ 3822 #define NFA_PIM_TODO 1 /* pim not done yet */ 3823 #define NFA_PIM_MATCH 2 /* pim executed, matches */ 3824 #define NFA_PIM_NOMATCH 3 /* pim executed, no match */ 3825 3826 3827 /* nfa_thread_T contains execution information of a NFA state */ 3828 typedef struct 3829 { 3830 nfa_state_T *state; 3831 int count; 3832 nfa_pim_T pim; /* if pim.result != NFA_PIM_UNUSED: postponed 3833 * invisible match */ 3834 regsubs_T subs; /* submatch info, only party used */ 3835 } nfa_thread_T; 3836 3837 /* nfa_list_T contains the alternative NFA execution states. */ 3838 typedef struct 3839 { 3840 nfa_thread_T *t; /* allocated array of states */ 3841 int n; /* nr of states currently in "t" */ 3842 int len; /* max nr of states in "t" */ 3843 int id; /* ID of the list */ 3844 int has_pim; /* TRUE when any state has a PIM */ 3845 } nfa_list_T; 3846 3847 #ifdef ENABLE_LOG 3848 static void log_subexpr(regsub_T *sub); 3849 3850 static void 3851 log_subsexpr(regsubs_T *subs) 3852 { 3853 log_subexpr(&subs->norm); 3854 # ifdef FEAT_SYN_HL 3855 if (rex.nfa_has_zsubexpr) 3856 log_subexpr(&subs->synt); 3857 # endif 3858 } 3859 3860 static void 3861 log_subexpr(regsub_T *sub) 3862 { 3863 int j; 3864 3865 for (j = 0; j < sub->in_use; j++) 3866 if (REG_MULTI) 3867 fprintf(log_fd, "*** group %d, start: c=%d, l=%d, end: c=%d, l=%d\n", 3868 j, 3869 sub->list.multi[j].start_col, 3870 (int)sub->list.multi[j].start_lnum, 3871 sub->list.multi[j].end_col, 3872 (int)sub->list.multi[j].end_lnum); 3873 else 3874 { 3875 char *s = (char *)sub->list.line[j].start; 3876 char *e = (char *)sub->list.line[j].end; 3877 3878 fprintf(log_fd, "*** group %d, start: \"%s\", end: \"%s\"\n", 3879 j, 3880 s == NULL ? "NULL" : s, 3881 e == NULL ? "NULL" : e); 3882 } 3883 } 3884 3885 static char * 3886 pim_info(nfa_pim_T *pim) 3887 { 3888 static char buf[30]; 3889 3890 if (pim == NULL || pim->result == NFA_PIM_UNUSED) 3891 buf[0] = NUL; 3892 else 3893 { 3894 sprintf(buf, " PIM col %d", REG_MULTI ? (int)pim->end.pos.col 3895 : (int)(pim->end.ptr - rex.input)); 3896 } 3897 return buf; 3898 } 3899 3900 #endif 3901 3902 /* Used during execution: whether a match has been found. */ 3903 static int nfa_match; 3904 #ifdef FEAT_RELTIME 3905 static proftime_T *nfa_time_limit; 3906 static int *nfa_timed_out; 3907 static int nfa_time_count; 3908 #endif 3909 3910 static void copy_sub(regsub_T *to, regsub_T *from); 3911 static int pim_equal(nfa_pim_T *one, nfa_pim_T *two); 3912 3913 /* 3914 * Copy postponed invisible match info from "from" to "to". 3915 */ 3916 static void 3917 copy_pim(nfa_pim_T *to, nfa_pim_T *from) 3918 { 3919 to->result = from->result; 3920 to->state = from->state; 3921 copy_sub(&to->subs.norm, &from->subs.norm); 3922 #ifdef FEAT_SYN_HL 3923 if (rex.nfa_has_zsubexpr) 3924 copy_sub(&to->subs.synt, &from->subs.synt); 3925 #endif 3926 to->end = from->end; 3927 } 3928 3929 static void 3930 clear_sub(regsub_T *sub) 3931 { 3932 if (REG_MULTI) 3933 /* Use 0xff to set lnum to -1 */ 3934 vim_memset(sub->list.multi, 0xff, 3935 sizeof(struct multipos) * rex.nfa_nsubexpr); 3936 else 3937 vim_memset(sub->list.line, 0, 3938 sizeof(struct linepos) * rex.nfa_nsubexpr); 3939 sub->in_use = 0; 3940 } 3941 3942 /* 3943 * Copy the submatches from "from" to "to". 3944 */ 3945 static void 3946 copy_sub(regsub_T *to, regsub_T *from) 3947 { 3948 to->in_use = from->in_use; 3949 if (from->in_use > 0) 3950 { 3951 /* Copy the match start and end positions. */ 3952 if (REG_MULTI) 3953 mch_memmove(&to->list.multi[0], 3954 &from->list.multi[0], 3955 sizeof(struct multipos) * from->in_use); 3956 else 3957 mch_memmove(&to->list.line[0], 3958 &from->list.line[0], 3959 sizeof(struct linepos) * from->in_use); 3960 } 3961 } 3962 3963 /* 3964 * Like copy_sub() but exclude the main match. 3965 */ 3966 static void 3967 copy_sub_off(regsub_T *to, regsub_T *from) 3968 { 3969 if (to->in_use < from->in_use) 3970 to->in_use = from->in_use; 3971 if (from->in_use > 1) 3972 { 3973 /* Copy the match start and end positions. */ 3974 if (REG_MULTI) 3975 mch_memmove(&to->list.multi[1], 3976 &from->list.multi[1], 3977 sizeof(struct multipos) * (from->in_use - 1)); 3978 else 3979 mch_memmove(&to->list.line[1], 3980 &from->list.line[1], 3981 sizeof(struct linepos) * (from->in_use - 1)); 3982 } 3983 } 3984 3985 /* 3986 * Like copy_sub() but only do the end of the main match if \ze is present. 3987 */ 3988 static void 3989 copy_ze_off(regsub_T *to, regsub_T *from) 3990 { 3991 if (rex.nfa_has_zend) 3992 { 3993 if (REG_MULTI) 3994 { 3995 if (from->list.multi[0].end_lnum >= 0) 3996 { 3997 to->list.multi[0].end_lnum = from->list.multi[0].end_lnum; 3998 to->list.multi[0].end_col = from->list.multi[0].end_col; 3999 } 4000 } 4001 else 4002 { 4003 if (from->list.line[0].end != NULL) 4004 to->list.line[0].end = from->list.line[0].end; 4005 } 4006 } 4007 } 4008 4009 /* 4010 * Return TRUE if "sub1" and "sub2" have the same start positions. 4011 * When using back-references also check the end position. 4012 */ 4013 static int 4014 sub_equal(regsub_T *sub1, regsub_T *sub2) 4015 { 4016 int i; 4017 int todo; 4018 linenr_T s1; 4019 linenr_T s2; 4020 char_u *sp1; 4021 char_u *sp2; 4022 4023 todo = sub1->in_use > sub2->in_use ? sub1->in_use : sub2->in_use; 4024 if (REG_MULTI) 4025 { 4026 for (i = 0; i < todo; ++i) 4027 { 4028 if (i < sub1->in_use) 4029 s1 = sub1->list.multi[i].start_lnum; 4030 else 4031 s1 = -1; 4032 if (i < sub2->in_use) 4033 s2 = sub2->list.multi[i].start_lnum; 4034 else 4035 s2 = -1; 4036 if (s1 != s2) 4037 return FALSE; 4038 if (s1 != -1 && sub1->list.multi[i].start_col 4039 != sub2->list.multi[i].start_col) 4040 return FALSE; 4041 4042 if (rex.nfa_has_backref) 4043 { 4044 if (i < sub1->in_use) 4045 s1 = sub1->list.multi[i].end_lnum; 4046 else 4047 s1 = -1; 4048 if (i < sub2->in_use) 4049 s2 = sub2->list.multi[i].end_lnum; 4050 else 4051 s2 = -1; 4052 if (s1 != s2) 4053 return FALSE; 4054 if (s1 != -1 && sub1->list.multi[i].end_col 4055 != sub2->list.multi[i].end_col) 4056 return FALSE; 4057 } 4058 } 4059 } 4060 else 4061 { 4062 for (i = 0; i < todo; ++i) 4063 { 4064 if (i < sub1->in_use) 4065 sp1 = sub1->list.line[i].start; 4066 else 4067 sp1 = NULL; 4068 if (i < sub2->in_use) 4069 sp2 = sub2->list.line[i].start; 4070 else 4071 sp2 = NULL; 4072 if (sp1 != sp2) 4073 return FALSE; 4074 if (rex.nfa_has_backref) 4075 { 4076 if (i < sub1->in_use) 4077 sp1 = sub1->list.line[i].end; 4078 else 4079 sp1 = NULL; 4080 if (i < sub2->in_use) 4081 sp2 = sub2->list.line[i].end; 4082 else 4083 sp2 = NULL; 4084 if (sp1 != sp2) 4085 return FALSE; 4086 } 4087 } 4088 } 4089 4090 return TRUE; 4091 } 4092 4093 #ifdef ENABLE_LOG 4094 static void 4095 report_state(char *action, 4096 regsub_T *sub, 4097 nfa_state_T *state, 4098 int lid, 4099 nfa_pim_T *pim) 4100 { 4101 int col; 4102 4103 if (sub->in_use <= 0) 4104 col = -1; 4105 else if (REG_MULTI) 4106 col = sub->list.multi[0].start_col; 4107 else 4108 col = (int)(sub->list.line[0].start - rex.line); 4109 nfa_set_code(state->c); 4110 fprintf(log_fd, "> %s state %d to list %d. char %d: %s (start col %d)%s\n", 4111 action, abs(state->id), lid, state->c, code, col, 4112 pim_info(pim)); 4113 } 4114 #endif 4115 4116 /* 4117 * Return TRUE if the same state is already in list "l" with the same 4118 * positions as "subs". 4119 */ 4120 static int 4121 has_state_with_pos( 4122 nfa_list_T *l, /* runtime state list */ 4123 nfa_state_T *state, /* state to update */ 4124 regsubs_T *subs, /* pointers to subexpressions */ 4125 nfa_pim_T *pim) /* postponed match or NULL */ 4126 { 4127 nfa_thread_T *thread; 4128 int i; 4129 4130 for (i = 0; i < l->n; ++i) 4131 { 4132 thread = &l->t[i]; 4133 if (thread->state->id == state->id 4134 && sub_equal(&thread->subs.norm, &subs->norm) 4135 #ifdef FEAT_SYN_HL 4136 && (!rex.nfa_has_zsubexpr 4137 || sub_equal(&thread->subs.synt, &subs->synt)) 4138 #endif 4139 && pim_equal(&thread->pim, pim)) 4140 return TRUE; 4141 } 4142 return FALSE; 4143 } 4144 4145 /* 4146 * Return TRUE if "one" and "two" are equal. That includes when both are not 4147 * set. 4148 */ 4149 static int 4150 pim_equal(nfa_pim_T *one, nfa_pim_T *two) 4151 { 4152 int one_unused = (one == NULL || one->result == NFA_PIM_UNUSED); 4153 int two_unused = (two == NULL || two->result == NFA_PIM_UNUSED); 4154 4155 if (one_unused) 4156 /* one is unused: equal when two is also unused */ 4157 return two_unused; 4158 if (two_unused) 4159 /* one is used and two is not: not equal */ 4160 return FALSE; 4161 /* compare the state id */ 4162 if (one->state->id != two->state->id) 4163 return FALSE; 4164 /* compare the position */ 4165 if (REG_MULTI) 4166 return one->end.pos.lnum == two->end.pos.lnum 4167 && one->end.pos.col == two->end.pos.col; 4168 return one->end.ptr == two->end.ptr; 4169 } 4170 4171 /* 4172 * Return TRUE if "state" leads to a NFA_MATCH without advancing the input. 4173 */ 4174 static int 4175 match_follows(nfa_state_T *startstate, int depth) 4176 { 4177 nfa_state_T *state = startstate; 4178 4179 /* avoid too much recursion */ 4180 if (depth > 10) 4181 return FALSE; 4182 4183 while (state != NULL) 4184 { 4185 switch (state->c) 4186 { 4187 case NFA_MATCH: 4188 case NFA_MCLOSE: 4189 case NFA_END_INVISIBLE: 4190 case NFA_END_INVISIBLE_NEG: 4191 case NFA_END_PATTERN: 4192 return TRUE; 4193 4194 case NFA_SPLIT: 4195 return match_follows(state->out, depth + 1) 4196 || match_follows(state->out1, depth + 1); 4197 4198 case NFA_START_INVISIBLE: 4199 case NFA_START_INVISIBLE_FIRST: 4200 case NFA_START_INVISIBLE_BEFORE: 4201 case NFA_START_INVISIBLE_BEFORE_FIRST: 4202 case NFA_START_INVISIBLE_NEG: 4203 case NFA_START_INVISIBLE_NEG_FIRST: 4204 case NFA_START_INVISIBLE_BEFORE_NEG: 4205 case NFA_START_INVISIBLE_BEFORE_NEG_FIRST: 4206 case NFA_COMPOSING: 4207 /* skip ahead to next state */ 4208 state = state->out1->out; 4209 continue; 4210 4211 case NFA_ANY: 4212 case NFA_ANY_COMPOSING: 4213 case NFA_IDENT: 4214 case NFA_SIDENT: 4215 case NFA_KWORD: 4216 case NFA_SKWORD: 4217 case NFA_FNAME: 4218 case NFA_SFNAME: 4219 case NFA_PRINT: 4220 case NFA_SPRINT: 4221 case NFA_WHITE: 4222 case NFA_NWHITE: 4223 case NFA_DIGIT: 4224 case NFA_NDIGIT: 4225 case NFA_HEX: 4226 case NFA_NHEX: 4227 case NFA_OCTAL: 4228 case NFA_NOCTAL: 4229 case NFA_WORD: 4230 case NFA_NWORD: 4231 case NFA_HEAD: 4232 case NFA_NHEAD: 4233 case NFA_ALPHA: 4234 case NFA_NALPHA: 4235 case NFA_LOWER: 4236 case NFA_NLOWER: 4237 case NFA_UPPER: 4238 case NFA_NUPPER: 4239 case NFA_LOWER_IC: 4240 case NFA_NLOWER_IC: 4241 case NFA_UPPER_IC: 4242 case NFA_NUPPER_IC: 4243 case NFA_START_COLL: 4244 case NFA_START_NEG_COLL: 4245 case NFA_NEWL: 4246 /* state will advance input */ 4247 return FALSE; 4248 4249 default: 4250 if (state->c > 0) 4251 /* state will advance input */ 4252 return FALSE; 4253 4254 /* Others: zero-width or possibly zero-width, might still find 4255 * a match at the same position, keep looking. */ 4256 break; 4257 } 4258 state = state->out; 4259 } 4260 return FALSE; 4261 } 4262 4263 4264 /* 4265 * Return TRUE if "state" is already in list "l". 4266 */ 4267 static int 4268 state_in_list( 4269 nfa_list_T *l, /* runtime state list */ 4270 nfa_state_T *state, /* state to update */ 4271 regsubs_T *subs) /* pointers to subexpressions */ 4272 { 4273 if (state->lastlist[nfa_ll_index] == l->id) 4274 { 4275 if (!rex.nfa_has_backref || has_state_with_pos(l, state, subs, NULL)) 4276 return TRUE; 4277 } 4278 return FALSE; 4279 } 4280 4281 /* Offset used for "off" by addstate_here(). */ 4282 #define ADDSTATE_HERE_OFFSET 10 4283 4284 /* 4285 * Add "state" and possibly what follows to state list ".". 4286 * Returns "subs_arg", possibly copied into temp_subs. 4287 */ 4288 static regsubs_T * 4289 addstate( 4290 nfa_list_T *l, /* runtime state list */ 4291 nfa_state_T *state, /* state to update */ 4292 regsubs_T *subs_arg, /* pointers to subexpressions */ 4293 nfa_pim_T *pim, /* postponed look-behind match */ 4294 int off_arg) /* byte offset, when -1 go to next line */ 4295 { 4296 int subidx; 4297 int off = off_arg; 4298 int add_here = FALSE; 4299 int listindex = 0; 4300 int k; 4301 int found = FALSE; 4302 nfa_thread_T *thread; 4303 struct multipos save_multipos; 4304 int save_in_use; 4305 char_u *save_ptr; 4306 int i; 4307 regsub_T *sub; 4308 regsubs_T *subs = subs_arg; 4309 static regsubs_T temp_subs; 4310 #ifdef ENABLE_LOG 4311 int did_print = FALSE; 4312 #endif 4313 4314 if (off_arg <= -ADDSTATE_HERE_OFFSET) 4315 { 4316 add_here = TRUE; 4317 off = 0; 4318 listindex = -(off_arg + ADDSTATE_HERE_OFFSET); 4319 } 4320 4321 switch (state->c) 4322 { 4323 case NFA_NCLOSE: 4324 case NFA_MCLOSE: 4325 case NFA_MCLOSE1: 4326 case NFA_MCLOSE2: 4327 case NFA_MCLOSE3: 4328 case NFA_MCLOSE4: 4329 case NFA_MCLOSE5: 4330 case NFA_MCLOSE6: 4331 case NFA_MCLOSE7: 4332 case NFA_MCLOSE8: 4333 case NFA_MCLOSE9: 4334 #ifdef FEAT_SYN_HL 4335 case NFA_ZCLOSE: 4336 case NFA_ZCLOSE1: 4337 case NFA_ZCLOSE2: 4338 case NFA_ZCLOSE3: 4339 case NFA_ZCLOSE4: 4340 case NFA_ZCLOSE5: 4341 case NFA_ZCLOSE6: 4342 case NFA_ZCLOSE7: 4343 case NFA_ZCLOSE8: 4344 case NFA_ZCLOSE9: 4345 #endif 4346 case NFA_MOPEN: 4347 case NFA_ZEND: 4348 case NFA_SPLIT: 4349 case NFA_EMPTY: 4350 /* These nodes are not added themselves but their "out" and/or 4351 * "out1" may be added below. */ 4352 break; 4353 4354 case NFA_BOL: 4355 case NFA_BOF: 4356 /* "^" won't match past end-of-line, don't bother trying. 4357 * Except when at the end of the line, or when we are going to the 4358 * next line for a look-behind match. */ 4359 if (rex.input > rex.line 4360 && *rex.input != NUL 4361 && (nfa_endp == NULL 4362 || !REG_MULTI 4363 || rex.lnum == nfa_endp->se_u.pos.lnum)) 4364 goto skip_add; 4365 /* FALLTHROUGH */ 4366 4367 case NFA_MOPEN1: 4368 case NFA_MOPEN2: 4369 case NFA_MOPEN3: 4370 case NFA_MOPEN4: 4371 case NFA_MOPEN5: 4372 case NFA_MOPEN6: 4373 case NFA_MOPEN7: 4374 case NFA_MOPEN8: 4375 case NFA_MOPEN9: 4376 #ifdef FEAT_SYN_HL 4377 case NFA_ZOPEN: 4378 case NFA_ZOPEN1: 4379 case NFA_ZOPEN2: 4380 case NFA_ZOPEN3: 4381 case NFA_ZOPEN4: 4382 case NFA_ZOPEN5: 4383 case NFA_ZOPEN6: 4384 case NFA_ZOPEN7: 4385 case NFA_ZOPEN8: 4386 case NFA_ZOPEN9: 4387 #endif 4388 case NFA_NOPEN: 4389 case NFA_ZSTART: 4390 /* These nodes need to be added so that we can bail out when it 4391 * was added to this list before at the same position to avoid an 4392 * endless loop for "\(\)*" */ 4393 4394 default: 4395 if (state->lastlist[nfa_ll_index] == l->id && state->c != NFA_SKIP) 4396 { 4397 /* This state is already in the list, don't add it again, 4398 * unless it is an MOPEN that is used for a backreference or 4399 * when there is a PIM. For NFA_MATCH check the position, 4400 * lower position is preferred. */ 4401 if (!rex.nfa_has_backref && pim == NULL && !l->has_pim 4402 && state->c != NFA_MATCH) 4403 { 4404 /* When called from addstate_here() do insert before 4405 * existing states. */ 4406 if (add_here) 4407 { 4408 for (k = 0; k < l->n && k < listindex; ++k) 4409 if (l->t[k].state->id == state->id) 4410 { 4411 found = TRUE; 4412 break; 4413 } 4414 } 4415 if (!add_here || found) 4416 { 4417 skip_add: 4418 #ifdef ENABLE_LOG 4419 nfa_set_code(state->c); 4420 fprintf(log_fd, "> Not adding state %d to list %d. char %d: %s pim: %s has_pim: %d found: %d\n", 4421 abs(state->id), l->id, state->c, code, 4422 pim == NULL ? "NULL" : "yes", l->has_pim, found); 4423 #endif 4424 return subs; 4425 } 4426 } 4427 4428 /* Do not add the state again when it exists with the same 4429 * positions. */ 4430 if (has_state_with_pos(l, state, subs, pim)) 4431 goto skip_add; 4432 } 4433 4434 /* When there are backreferences or PIMs the number of states may 4435 * be (a lot) bigger than anticipated. */ 4436 if (l->n == l->len) 4437 { 4438 int newlen = l->len * 3 / 2 + 50; 4439 4440 if (subs != &temp_subs) 4441 { 4442 /* "subs" may point into the current array, need to make a 4443 * copy before it becomes invalid. */ 4444 copy_sub(&temp_subs.norm, &subs->norm); 4445 #ifdef FEAT_SYN_HL 4446 if (rex.nfa_has_zsubexpr) 4447 copy_sub(&temp_subs.synt, &subs->synt); 4448 #endif 4449 subs = &temp_subs; 4450 } 4451 4452 /* TODO: check for vim_realloc() returning NULL. */ 4453 l->t = vim_realloc(l->t, newlen * sizeof(nfa_thread_T)); 4454 l->len = newlen; 4455 } 4456 4457 /* add the state to the list */ 4458 state->lastlist[nfa_ll_index] = l->id; 4459 thread = &l->t[l->n++]; 4460 thread->state = state; 4461 if (pim == NULL) 4462 thread->pim.result = NFA_PIM_UNUSED; 4463 else 4464 { 4465 copy_pim(&thread->pim, pim); 4466 l->has_pim = TRUE; 4467 } 4468 copy_sub(&thread->subs.norm, &subs->norm); 4469 #ifdef FEAT_SYN_HL 4470 if (rex.nfa_has_zsubexpr) 4471 copy_sub(&thread->subs.synt, &subs->synt); 4472 #endif 4473 #ifdef ENABLE_LOG 4474 report_state("Adding", &thread->subs.norm, state, l->id, pim); 4475 did_print = TRUE; 4476 #endif 4477 } 4478 4479 #ifdef ENABLE_LOG 4480 if (!did_print) 4481 report_state("Processing", &subs->norm, state, l->id, pim); 4482 #endif 4483 switch (state->c) 4484 { 4485 case NFA_MATCH: 4486 break; 4487 4488 case NFA_SPLIT: 4489 /* order matters here */ 4490 subs = addstate(l, state->out, subs, pim, off_arg); 4491 subs = addstate(l, state->out1, subs, pim, off_arg); 4492 break; 4493 4494 case NFA_EMPTY: 4495 case NFA_NOPEN: 4496 case NFA_NCLOSE: 4497 subs = addstate(l, state->out, subs, pim, off_arg); 4498 break; 4499 4500 case NFA_MOPEN: 4501 case NFA_MOPEN1: 4502 case NFA_MOPEN2: 4503 case NFA_MOPEN3: 4504 case NFA_MOPEN4: 4505 case NFA_MOPEN5: 4506 case NFA_MOPEN6: 4507 case NFA_MOPEN7: 4508 case NFA_MOPEN8: 4509 case NFA_MOPEN9: 4510 #ifdef FEAT_SYN_HL 4511 case NFA_ZOPEN: 4512 case NFA_ZOPEN1: 4513 case NFA_ZOPEN2: 4514 case NFA_ZOPEN3: 4515 case NFA_ZOPEN4: 4516 case NFA_ZOPEN5: 4517 case NFA_ZOPEN6: 4518 case NFA_ZOPEN7: 4519 case NFA_ZOPEN8: 4520 case NFA_ZOPEN9: 4521 #endif 4522 case NFA_ZSTART: 4523 if (state->c == NFA_ZSTART) 4524 { 4525 subidx = 0; 4526 sub = &subs->norm; 4527 } 4528 #ifdef FEAT_SYN_HL 4529 else if (state->c >= NFA_ZOPEN && state->c <= NFA_ZOPEN9) 4530 { 4531 subidx = state->c - NFA_ZOPEN; 4532 sub = &subs->synt; 4533 } 4534 #endif 4535 else 4536 { 4537 subidx = state->c - NFA_MOPEN; 4538 sub = &subs->norm; 4539 } 4540 4541 /* avoid compiler warnings */ 4542 save_ptr = NULL; 4543 vim_memset(&save_multipos, 0, sizeof(save_multipos)); 4544 4545 /* Set the position (with "off" added) in the subexpression. Save 4546 * and restore it when it was in use. Otherwise fill any gap. */ 4547 if (REG_MULTI) 4548 { 4549 if (subidx < sub->in_use) 4550 { 4551 save_multipos = sub->list.multi[subidx]; 4552 save_in_use = -1; 4553 } 4554 else 4555 { 4556 save_in_use = sub->in_use; 4557 for (i = sub->in_use; i < subidx; ++i) 4558 { 4559 sub->list.multi[i].start_lnum = -1; 4560 sub->list.multi[i].end_lnum = -1; 4561 } 4562 sub->in_use = subidx + 1; 4563 } 4564 if (off == -1) 4565 { 4566 sub->list.multi[subidx].start_lnum = rex.lnum + 1; 4567 sub->list.multi[subidx].start_col = 0; 4568 } 4569 else 4570 { 4571 sub->list.multi[subidx].start_lnum = rex.lnum; 4572 sub->list.multi[subidx].start_col = 4573 (colnr_T)(rex.input - rex.line + off); 4574 } 4575 sub->list.multi[subidx].end_lnum = -1; 4576 } 4577 else 4578 { 4579 if (subidx < sub->in_use) 4580 { 4581 save_ptr = sub->list.line[subidx].start; 4582 save_in_use = -1; 4583 } 4584 else 4585 { 4586 save_in_use = sub->in_use; 4587 for (i = sub->in_use; i < subidx; ++i) 4588 { 4589 sub->list.line[i].start = NULL; 4590 sub->list.line[i].end = NULL; 4591 } 4592 sub->in_use = subidx + 1; 4593 } 4594 sub->list.line[subidx].start = rex.input + off; 4595 } 4596 4597 subs = addstate(l, state->out, subs, pim, off_arg); 4598 /* "subs" may have changed, need to set "sub" again */ 4599 #ifdef FEAT_SYN_HL 4600 if (state->c >= NFA_ZOPEN && state->c <= NFA_ZOPEN9) 4601 sub = &subs->synt; 4602 else 4603 #endif 4604 sub = &subs->norm; 4605 4606 if (save_in_use == -1) 4607 { 4608 if (REG_MULTI) 4609 sub->list.multi[subidx] = save_multipos; 4610 else 4611 sub->list.line[subidx].start = save_ptr; 4612 } 4613 else 4614 sub->in_use = save_in_use; 4615 break; 4616 4617 case NFA_MCLOSE: 4618 if (rex.nfa_has_zend && (REG_MULTI 4619 ? subs->norm.list.multi[0].end_lnum >= 0 4620 : subs->norm.list.line[0].end != NULL)) 4621 { 4622 /* Do not overwrite the position set by \ze. */ 4623 subs = addstate(l, state->out, subs, pim, off_arg); 4624 break; 4625 } 4626 /* FALLTHROUGH */ 4627 case NFA_MCLOSE1: 4628 case NFA_MCLOSE2: 4629 case NFA_MCLOSE3: 4630 case NFA_MCLOSE4: 4631 case NFA_MCLOSE5: 4632 case NFA_MCLOSE6: 4633 case NFA_MCLOSE7: 4634 case NFA_MCLOSE8: 4635 case NFA_MCLOSE9: 4636 #ifdef FEAT_SYN_HL 4637 case NFA_ZCLOSE: 4638 case NFA_ZCLOSE1: 4639 case NFA_ZCLOSE2: 4640 case NFA_ZCLOSE3: 4641 case NFA_ZCLOSE4: 4642 case NFA_ZCLOSE5: 4643 case NFA_ZCLOSE6: 4644 case NFA_ZCLOSE7: 4645 case NFA_ZCLOSE8: 4646 case NFA_ZCLOSE9: 4647 #endif 4648 case NFA_ZEND: 4649 if (state->c == NFA_ZEND) 4650 { 4651 subidx = 0; 4652 sub = &subs->norm; 4653 } 4654 #ifdef FEAT_SYN_HL 4655 else if (state->c >= NFA_ZCLOSE && state->c <= NFA_ZCLOSE9) 4656 { 4657 subidx = state->c - NFA_ZCLOSE; 4658 sub = &subs->synt; 4659 } 4660 #endif 4661 else 4662 { 4663 subidx = state->c - NFA_MCLOSE; 4664 sub = &subs->norm; 4665 } 4666 4667 /* We don't fill in gaps here, there must have been an MOPEN that 4668 * has done that. */ 4669 save_in_use = sub->in_use; 4670 if (sub->in_use <= subidx) 4671 sub->in_use = subidx + 1; 4672 if (REG_MULTI) 4673 { 4674 save_multipos = sub->list.multi[subidx]; 4675 if (off == -1) 4676 { 4677 sub->list.multi[subidx].end_lnum = rex.lnum + 1; 4678 sub->list.multi[subidx].end_col = 0; 4679 } 4680 else 4681 { 4682 sub->list.multi[subidx].end_lnum = rex.lnum; 4683 sub->list.multi[subidx].end_col = 4684 (colnr_T)(rex.input - rex.line + off); 4685 } 4686 /* avoid compiler warnings */ 4687 save_ptr = NULL; 4688 } 4689 else 4690 { 4691 save_ptr = sub->list.line[subidx].end; 4692 sub->list.line[subidx].end = rex.input + off; 4693 /* avoid compiler warnings */ 4694 vim_memset(&save_multipos, 0, sizeof(save_multipos)); 4695 } 4696 4697 subs = addstate(l, state->out, subs, pim, off_arg); 4698 /* "subs" may have changed, need to set "sub" again */ 4699 #ifdef FEAT_SYN_HL 4700 if (state->c >= NFA_ZCLOSE && state->c <= NFA_ZCLOSE9) 4701 sub = &subs->synt; 4702 else 4703 #endif 4704 sub = &subs->norm; 4705 4706 if (REG_MULTI) 4707 sub->list.multi[subidx] = save_multipos; 4708 else 4709 sub->list.line[subidx].end = save_ptr; 4710 sub->in_use = save_in_use; 4711 break; 4712 } 4713 return subs; 4714 } 4715 4716 /* 4717 * Like addstate(), but the new state(s) are put at position "*ip". 4718 * Used for zero-width matches, next state to use is the added one. 4719 * This makes sure the order of states to be tried does not change, which 4720 * matters for alternatives. 4721 */ 4722 static void 4723 addstate_here( 4724 nfa_list_T *l, /* runtime state list */ 4725 nfa_state_T *state, /* state to update */ 4726 regsubs_T *subs, /* pointers to subexpressions */ 4727 nfa_pim_T *pim, /* postponed look-behind match */ 4728 int *ip) 4729 { 4730 int tlen = l->n; 4731 int count; 4732 int listidx = *ip; 4733 4734 /* First add the state(s) at the end, so that we know how many there are. 4735 * Pass the listidx as offset (avoids adding another argument to 4736 * addstate(). */ 4737 addstate(l, state, subs, pim, -listidx - ADDSTATE_HERE_OFFSET); 4738 4739 /* when "*ip" was at the end of the list, nothing to do */ 4740 if (listidx + 1 == tlen) 4741 return; 4742 4743 /* re-order to put the new state at the current position */ 4744 count = l->n - tlen; 4745 if (count == 0) 4746 return; /* no state got added */ 4747 if (count == 1) 4748 { 4749 /* overwrite the current state */ 4750 l->t[listidx] = l->t[l->n - 1]; 4751 } 4752 else if (count > 1) 4753 { 4754 if (l->n + count - 1 >= l->len) 4755 { 4756 /* not enough space to move the new states, reallocate the list 4757 * and move the states to the right position */ 4758 nfa_thread_T *newl; 4759 4760 l->len = l->len * 3 / 2 + 50; 4761 newl = (nfa_thread_T *)alloc(l->len * sizeof(nfa_thread_T)); 4762 if (newl == NULL) 4763 return; 4764 mch_memmove(&(newl[0]), 4765 &(l->t[0]), 4766 sizeof(nfa_thread_T) * listidx); 4767 mch_memmove(&(newl[listidx]), 4768 &(l->t[l->n - count]), 4769 sizeof(nfa_thread_T) * count); 4770 mch_memmove(&(newl[listidx + count]), 4771 &(l->t[listidx + 1]), 4772 sizeof(nfa_thread_T) * (l->n - count - listidx - 1)); 4773 vim_free(l->t); 4774 l->t = newl; 4775 } 4776 else 4777 { 4778 /* make space for new states, then move them from the 4779 * end to the current position */ 4780 mch_memmove(&(l->t[listidx + count]), 4781 &(l->t[listidx + 1]), 4782 sizeof(nfa_thread_T) * (l->n - listidx - 1)); 4783 mch_memmove(&(l->t[listidx]), 4784 &(l->t[l->n - 1]), 4785 sizeof(nfa_thread_T) * count); 4786 } 4787 } 4788 --l->n; 4789 *ip = listidx - 1; 4790 } 4791 4792 /* 4793 * Check character class "class" against current character c. 4794 */ 4795 static int 4796 check_char_class(int class, int c) 4797 { 4798 switch (class) 4799 { 4800 case NFA_CLASS_ALNUM: 4801 if (c >= 1 && c < 128 && isalnum(c)) 4802 return OK; 4803 break; 4804 case NFA_CLASS_ALPHA: 4805 if (c >= 1 && c < 128 && isalpha(c)) 4806 return OK; 4807 break; 4808 case NFA_CLASS_BLANK: 4809 if (c == ' ' || c == '\t') 4810 return OK; 4811 break; 4812 case NFA_CLASS_CNTRL: 4813 if (c >= 1 && c <= 127 && iscntrl(c)) 4814 return OK; 4815 break; 4816 case NFA_CLASS_DIGIT: 4817 if (VIM_ISDIGIT(c)) 4818 return OK; 4819 break; 4820 case NFA_CLASS_GRAPH: 4821 if (c >= 1 && c <= 127 && isgraph(c)) 4822 return OK; 4823 break; 4824 case NFA_CLASS_LOWER: 4825 if (MB_ISLOWER(c) && c != 170 && c != 186) 4826 return OK; 4827 break; 4828 case NFA_CLASS_PRINT: 4829 if (vim_isprintc(c)) 4830 return OK; 4831 break; 4832 case NFA_CLASS_PUNCT: 4833 if (c >= 1 && c < 128 && ispunct(c)) 4834 return OK; 4835 break; 4836 case NFA_CLASS_SPACE: 4837 if ((c >= 9 && c <= 13) || (c == ' ')) 4838 return OK; 4839 break; 4840 case NFA_CLASS_UPPER: 4841 if (MB_ISUPPER(c)) 4842 return OK; 4843 break; 4844 case NFA_CLASS_XDIGIT: 4845 if (vim_isxdigit(c)) 4846 return OK; 4847 break; 4848 case NFA_CLASS_TAB: 4849 if (c == '\t') 4850 return OK; 4851 break; 4852 case NFA_CLASS_RETURN: 4853 if (c == '\r') 4854 return OK; 4855 break; 4856 case NFA_CLASS_BACKSPACE: 4857 if (c == '\b') 4858 return OK; 4859 break; 4860 case NFA_CLASS_ESCAPE: 4861 if (c == '\033') 4862 return OK; 4863 break; 4864 case NFA_CLASS_IDENT: 4865 if (vim_isIDc(c)) 4866 return OK; 4867 break; 4868 case NFA_CLASS_KEYWORD: 4869 if (reg_iswordc(c)) 4870 return OK; 4871 break; 4872 case NFA_CLASS_FNAME: 4873 if (vim_isfilec(c)) 4874 return OK; 4875 break; 4876 4877 default: 4878 /* should not be here :P */ 4879 siemsg(_(e_ill_char_class), class); 4880 return FAIL; 4881 } 4882 return FAIL; 4883 } 4884 4885 /* 4886 * Check for a match with subexpression "subidx". 4887 * Return TRUE if it matches. 4888 */ 4889 static int 4890 match_backref( 4891 regsub_T *sub, /* pointers to subexpressions */ 4892 int subidx, 4893 int *bytelen) /* out: length of match in bytes */ 4894 { 4895 int len; 4896 4897 if (sub->in_use <= subidx) 4898 { 4899 retempty: 4900 /* backref was not set, match an empty string */ 4901 *bytelen = 0; 4902 return TRUE; 4903 } 4904 4905 if (REG_MULTI) 4906 { 4907 if (sub->list.multi[subidx].start_lnum < 0 4908 || sub->list.multi[subidx].end_lnum < 0) 4909 goto retempty; 4910 if (sub->list.multi[subidx].start_lnum == rex.lnum 4911 && sub->list.multi[subidx].end_lnum == rex.lnum) 4912 { 4913 len = sub->list.multi[subidx].end_col 4914 - sub->list.multi[subidx].start_col; 4915 if (cstrncmp(rex.line + sub->list.multi[subidx].start_col, 4916 rex.input, &len) == 0) 4917 { 4918 *bytelen = len; 4919 return TRUE; 4920 } 4921 } 4922 else 4923 { 4924 if (match_with_backref( 4925 sub->list.multi[subidx].start_lnum, 4926 sub->list.multi[subidx].start_col, 4927 sub->list.multi[subidx].end_lnum, 4928 sub->list.multi[subidx].end_col, 4929 bytelen) == RA_MATCH) 4930 return TRUE; 4931 } 4932 } 4933 else 4934 { 4935 if (sub->list.line[subidx].start == NULL 4936 || sub->list.line[subidx].end == NULL) 4937 goto retempty; 4938 len = (int)(sub->list.line[subidx].end - sub->list.line[subidx].start); 4939 if (cstrncmp(sub->list.line[subidx].start, rex.input, &len) == 0) 4940 { 4941 *bytelen = len; 4942 return TRUE; 4943 } 4944 } 4945 return FALSE; 4946 } 4947 4948 #ifdef FEAT_SYN_HL 4949 4950 /* 4951 * Check for a match with \z subexpression "subidx". 4952 * Return TRUE if it matches. 4953 */ 4954 static int 4955 match_zref( 4956 int subidx, 4957 int *bytelen) /* out: length of match in bytes */ 4958 { 4959 int len; 4960 4961 cleanup_zsubexpr(); 4962 if (re_extmatch_in == NULL || re_extmatch_in->matches[subidx] == NULL) 4963 { 4964 /* backref was not set, match an empty string */ 4965 *bytelen = 0; 4966 return TRUE; 4967 } 4968 4969 len = (int)STRLEN(re_extmatch_in->matches[subidx]); 4970 if (cstrncmp(re_extmatch_in->matches[subidx], rex.input, &len) == 0) 4971 { 4972 *bytelen = len; 4973 return TRUE; 4974 } 4975 return FALSE; 4976 } 4977 #endif 4978 4979 /* 4980 * Save list IDs for all NFA states of "prog" into "list". 4981 * Also reset the IDs to zero. 4982 * Only used for the recursive value lastlist[1]. 4983 */ 4984 static void 4985 nfa_save_listids(nfa_regprog_T *prog, int *list) 4986 { 4987 int i; 4988 nfa_state_T *p; 4989 4990 /* Order in the list is reverse, it's a bit faster that way. */ 4991 p = &prog->state[0]; 4992 for (i = prog->nstate; --i >= 0; ) 4993 { 4994 list[i] = p->lastlist[1]; 4995 p->lastlist[1] = 0; 4996 ++p; 4997 } 4998 } 4999 5000 /* 5001 * Restore list IDs from "list" to all NFA states. 5002 */ 5003 static void 5004 nfa_restore_listids(nfa_regprog_T *prog, int *list) 5005 { 5006 int i; 5007 nfa_state_T *p; 5008 5009 p = &prog->state[0]; 5010 for (i = prog->nstate; --i >= 0; ) 5011 { 5012 p->lastlist[1] = list[i]; 5013 ++p; 5014 } 5015 } 5016 5017 static int 5018 nfa_re_num_cmp(long_u val, int op, long_u pos) 5019 { 5020 if (op == 1) return pos > val; 5021 if (op == 2) return pos < val; 5022 return val == pos; 5023 } 5024 5025 static int nfa_regmatch(nfa_regprog_T *prog, nfa_state_T *start, regsubs_T *submatch, regsubs_T *m); 5026 5027 /* 5028 * Recursively call nfa_regmatch() 5029 * "pim" is NULL or contains info about a Postponed Invisible Match (start 5030 * position). 5031 */ 5032 static int 5033 recursive_regmatch( 5034 nfa_state_T *state, 5035 nfa_pim_T *pim, 5036 nfa_regprog_T *prog, 5037 regsubs_T *submatch, 5038 regsubs_T *m, 5039 int **listids, 5040 int *listids_len) 5041 { 5042 int save_reginput_col = (int)(rex.input - rex.line); 5043 int save_reglnum = rex.lnum; 5044 int save_nfa_match = nfa_match; 5045 int save_nfa_listid = rex.nfa_listid; 5046 save_se_T *save_nfa_endp = nfa_endp; 5047 save_se_T endpos; 5048 save_se_T *endposp = NULL; 5049 int result; 5050 int need_restore = FALSE; 5051 5052 if (pim != NULL) 5053 { 5054 /* start at the position where the postponed match was */ 5055 if (REG_MULTI) 5056 rex.input = rex.line + pim->end.pos.col; 5057 else 5058 rex.input = pim->end.ptr; 5059 } 5060 5061 if (state->c == NFA_START_INVISIBLE_BEFORE 5062 || state->c == NFA_START_INVISIBLE_BEFORE_FIRST 5063 || state->c == NFA_START_INVISIBLE_BEFORE_NEG 5064 || state->c == NFA_START_INVISIBLE_BEFORE_NEG_FIRST) 5065 { 5066 /* The recursive match must end at the current position. When "pim" is 5067 * not NULL it specifies the current position. */ 5068 endposp = &endpos; 5069 if (REG_MULTI) 5070 { 5071 if (pim == NULL) 5072 { 5073 endpos.se_u.pos.col = (int)(rex.input - rex.line); 5074 endpos.se_u.pos.lnum = rex.lnum; 5075 } 5076 else 5077 endpos.se_u.pos = pim->end.pos; 5078 } 5079 else 5080 { 5081 if (pim == NULL) 5082 endpos.se_u.ptr = rex.input; 5083 else 5084 endpos.se_u.ptr = pim->end.ptr; 5085 } 5086 5087 /* Go back the specified number of bytes, or as far as the 5088 * start of the previous line, to try matching "\@<=" or 5089 * not matching "\@<!". This is very inefficient, limit the number of 5090 * bytes if possible. */ 5091 if (state->val <= 0) 5092 { 5093 if (REG_MULTI) 5094 { 5095 rex.line = reg_getline(--rex.lnum); 5096 if (rex.line == NULL) 5097 /* can't go before the first line */ 5098 rex.line = reg_getline(++rex.lnum); 5099 } 5100 rex.input = rex.line; 5101 } 5102 else 5103 { 5104 if (REG_MULTI && (int)(rex.input - rex.line) < state->val) 5105 { 5106 /* Not enough bytes in this line, go to end of 5107 * previous line. */ 5108 rex.line = reg_getline(--rex.lnum); 5109 if (rex.line == NULL) 5110 { 5111 /* can't go before the first line */ 5112 rex.line = reg_getline(++rex.lnum); 5113 rex.input = rex.line; 5114 } 5115 else 5116 rex.input = rex.line + STRLEN(rex.line); 5117 } 5118 if ((int)(rex.input - rex.line) >= state->val) 5119 { 5120 rex.input -= state->val; 5121 if (has_mbyte) 5122 rex.input -= mb_head_off(rex.line, rex.input); 5123 } 5124 else 5125 rex.input = rex.line; 5126 } 5127 } 5128 5129 #ifdef ENABLE_LOG 5130 if (log_fd != stderr) 5131 fclose(log_fd); 5132 log_fd = NULL; 5133 #endif 5134 /* Have to clear the lastlist field of the NFA nodes, so that 5135 * nfa_regmatch() and addstate() can run properly after recursion. */ 5136 if (nfa_ll_index == 1) 5137 { 5138 /* Already calling nfa_regmatch() recursively. Save the lastlist[1] 5139 * values and clear them. */ 5140 if (*listids == NULL || *listids_len < prog->nstate) 5141 { 5142 vim_free(*listids); 5143 *listids = (int *)lalloc(sizeof(int) * prog->nstate, TRUE); 5144 if (*listids == NULL) 5145 { 5146 emsg(_("E878: (NFA) Could not allocate memory for branch traversal!")); 5147 return 0; 5148 } 5149 *listids_len = prog->nstate; 5150 } 5151 nfa_save_listids(prog, *listids); 5152 need_restore = TRUE; 5153 /* any value of rex.nfa_listid will do */ 5154 } 5155 else 5156 { 5157 /* First recursive nfa_regmatch() call, switch to the second lastlist 5158 * entry. Make sure rex.nfa_listid is different from a previous 5159 * recursive call, because some states may still have this ID. */ 5160 ++nfa_ll_index; 5161 if (rex.nfa_listid <= rex.nfa_alt_listid) 5162 rex.nfa_listid = rex.nfa_alt_listid; 5163 } 5164 5165 /* Call nfa_regmatch() to check if the current concat matches at this 5166 * position. The concat ends with the node NFA_END_INVISIBLE */ 5167 nfa_endp = endposp; 5168 result = nfa_regmatch(prog, state->out, submatch, m); 5169 5170 if (need_restore) 5171 nfa_restore_listids(prog, *listids); 5172 else 5173 { 5174 --nfa_ll_index; 5175 rex.nfa_alt_listid = rex.nfa_listid; 5176 } 5177 5178 /* restore position in input text */ 5179 rex.lnum = save_reglnum; 5180 if (REG_MULTI) 5181 rex.line = reg_getline(rex.lnum); 5182 rex.input = rex.line + save_reginput_col; 5183 if (result != NFA_TOO_EXPENSIVE) 5184 { 5185 nfa_match = save_nfa_match; 5186 rex.nfa_listid = save_nfa_listid; 5187 } 5188 nfa_endp = save_nfa_endp; 5189 5190 #ifdef ENABLE_LOG 5191 log_fd = fopen(NFA_REGEXP_RUN_LOG, "a"); 5192 if (log_fd != NULL) 5193 { 5194 fprintf(log_fd, "****************************\n"); 5195 fprintf(log_fd, "FINISHED RUNNING nfa_regmatch() recursively\n"); 5196 fprintf(log_fd, "MATCH = %s\n", result == TRUE ? "OK" : "FALSE"); 5197 fprintf(log_fd, "****************************\n"); 5198 } 5199 else 5200 { 5201 emsg(_(e_log_open_failed)); 5202 log_fd = stderr; 5203 } 5204 #endif 5205 5206 return result; 5207 } 5208 5209 /* 5210 * Estimate the chance of a match with "state" failing. 5211 * empty match: 0 5212 * NFA_ANY: 1 5213 * specific character: 99 5214 */ 5215 static int 5216 failure_chance(nfa_state_T *state, int depth) 5217 { 5218 int c = state->c; 5219 int l, r; 5220 5221 /* detect looping */ 5222 if (depth > 4) 5223 return 1; 5224 5225 switch (c) 5226 { 5227 case NFA_SPLIT: 5228 if (state->out->c == NFA_SPLIT || state->out1->c == NFA_SPLIT) 5229 /* avoid recursive stuff */ 5230 return 1; 5231 /* two alternatives, use the lowest failure chance */ 5232 l = failure_chance(state->out, depth + 1); 5233 r = failure_chance(state->out1, depth + 1); 5234 return l < r ? l : r; 5235 5236 case NFA_ANY: 5237 /* matches anything, unlikely to fail */ 5238 return 1; 5239 5240 case NFA_MATCH: 5241 case NFA_MCLOSE: 5242 case NFA_ANY_COMPOSING: 5243 /* empty match works always */ 5244 return 0; 5245 5246 case NFA_START_INVISIBLE: 5247 case NFA_START_INVISIBLE_FIRST: 5248 case NFA_START_INVISIBLE_NEG: 5249 case NFA_START_INVISIBLE_NEG_FIRST: 5250 case NFA_START_INVISIBLE_BEFORE: 5251 case NFA_START_INVISIBLE_BEFORE_FIRST: 5252 case NFA_START_INVISIBLE_BEFORE_NEG: 5253 case NFA_START_INVISIBLE_BEFORE_NEG_FIRST: 5254 case NFA_START_PATTERN: 5255 /* recursive regmatch is expensive, use low failure chance */ 5256 return 5; 5257 5258 case NFA_BOL: 5259 case NFA_EOL: 5260 case NFA_BOF: 5261 case NFA_EOF: 5262 case NFA_NEWL: 5263 return 99; 5264 5265 case NFA_BOW: 5266 case NFA_EOW: 5267 return 90; 5268 5269 case NFA_MOPEN: 5270 case NFA_MOPEN1: 5271 case NFA_MOPEN2: 5272 case NFA_MOPEN3: 5273 case NFA_MOPEN4: 5274 case NFA_MOPEN5: 5275 case NFA_MOPEN6: 5276 case NFA_MOPEN7: 5277 case NFA_MOPEN8: 5278 case NFA_MOPEN9: 5279 #ifdef FEAT_SYN_HL 5280 case NFA_ZOPEN: 5281 case NFA_ZOPEN1: 5282 case NFA_ZOPEN2: 5283 case NFA_ZOPEN3: 5284 case NFA_ZOPEN4: 5285 case NFA_ZOPEN5: 5286 case NFA_ZOPEN6: 5287 case NFA_ZOPEN7: 5288 case NFA_ZOPEN8: 5289 case NFA_ZOPEN9: 5290 case NFA_ZCLOSE: 5291 case NFA_ZCLOSE1: 5292 case NFA_ZCLOSE2: 5293 case NFA_ZCLOSE3: 5294 case NFA_ZCLOSE4: 5295 case NFA_ZCLOSE5: 5296 case NFA_ZCLOSE6: 5297 case NFA_ZCLOSE7: 5298 case NFA_ZCLOSE8: 5299 case NFA_ZCLOSE9: 5300 #endif 5301 case NFA_NOPEN: 5302 case NFA_MCLOSE1: 5303 case NFA_MCLOSE2: 5304 case NFA_MCLOSE3: 5305 case NFA_MCLOSE4: 5306 case NFA_MCLOSE5: 5307 case NFA_MCLOSE6: 5308 case NFA_MCLOSE7: 5309 case NFA_MCLOSE8: 5310 case NFA_MCLOSE9: 5311 case NFA_NCLOSE: 5312 return failure_chance(state->out, depth + 1); 5313 5314 case NFA_BACKREF1: 5315 case NFA_BACKREF2: 5316 case NFA_BACKREF3: 5317 case NFA_BACKREF4: 5318 case NFA_BACKREF5: 5319 case NFA_BACKREF6: 5320 case NFA_BACKREF7: 5321 case NFA_BACKREF8: 5322 case NFA_BACKREF9: 5323 #ifdef FEAT_SYN_HL 5324 case NFA_ZREF1: 5325 case NFA_ZREF2: 5326 case NFA_ZREF3: 5327 case NFA_ZREF4: 5328 case NFA_ZREF5: 5329 case NFA_ZREF6: 5330 case NFA_ZREF7: 5331 case NFA_ZREF8: 5332 case NFA_ZREF9: 5333 #endif 5334 /* backreferences don't match in many places */ 5335 return 94; 5336 5337 case NFA_LNUM_GT: 5338 case NFA_LNUM_LT: 5339 case NFA_COL_GT: 5340 case NFA_COL_LT: 5341 case NFA_VCOL_GT: 5342 case NFA_VCOL_LT: 5343 case NFA_MARK_GT: 5344 case NFA_MARK_LT: 5345 case NFA_VISUAL: 5346 /* before/after positions don't match very often */ 5347 return 85; 5348 5349 case NFA_LNUM: 5350 return 90; 5351 5352 case NFA_CURSOR: 5353 case NFA_COL: 5354 case NFA_VCOL: 5355 case NFA_MARK: 5356 /* specific positions rarely match */ 5357 return 98; 5358 5359 case NFA_COMPOSING: 5360 return 95; 5361 5362 default: 5363 if (c > 0) 5364 /* character match fails often */ 5365 return 95; 5366 } 5367 5368 /* something else, includes character classes */ 5369 return 50; 5370 } 5371 5372 /* 5373 * Skip until the char "c" we know a match must start with. 5374 */ 5375 static int 5376 skip_to_start(int c, colnr_T *colp) 5377 { 5378 char_u *s; 5379 5380 /* Used often, do some work to avoid call overhead. */ 5381 if (!rex.reg_ic && !has_mbyte) 5382 s = vim_strbyte(rex.line + *colp, c); 5383 else 5384 s = cstrchr(rex.line + *colp, c); 5385 if (s == NULL) 5386 return FAIL; 5387 *colp = (int)(s - rex.line); 5388 return OK; 5389 } 5390 5391 /* 5392 * Check for a match with match_text. 5393 * Called after skip_to_start() has found regstart. 5394 * Returns zero for no match, 1 for a match. 5395 */ 5396 static long 5397 find_match_text(colnr_T startcol, int regstart, char_u *match_text) 5398 { 5399 colnr_T col = startcol; 5400 int c1, c2; 5401 int len1, len2; 5402 int match; 5403 5404 for (;;) 5405 { 5406 match = TRUE; 5407 len2 = MB_CHAR2LEN(regstart); /* skip regstart */ 5408 for (len1 = 0; match_text[len1] != NUL; len1 += MB_CHAR2LEN(c1)) 5409 { 5410 c1 = PTR2CHAR(match_text + len1); 5411 c2 = PTR2CHAR(rex.line + col + len2); 5412 if (c1 != c2 && (!rex.reg_ic || MB_TOLOWER(c1) != MB_TOLOWER(c2))) 5413 { 5414 match = FALSE; 5415 break; 5416 } 5417 len2 += MB_CHAR2LEN(c2); 5418 } 5419 if (match 5420 /* check that no composing char follows */ 5421 && !(enc_utf8 5422 && utf_iscomposing(PTR2CHAR(rex.line + col + len2)))) 5423 { 5424 cleanup_subexpr(); 5425 if (REG_MULTI) 5426 { 5427 rex.reg_startpos[0].lnum = rex.lnum; 5428 rex.reg_startpos[0].col = col; 5429 rex.reg_endpos[0].lnum = rex.lnum; 5430 rex.reg_endpos[0].col = col + len2; 5431 } 5432 else 5433 { 5434 rex.reg_startp[0] = rex.line + col; 5435 rex.reg_endp[0] = rex.line + col + len2; 5436 } 5437 return 1L; 5438 } 5439 5440 /* Try finding regstart after the current match. */ 5441 col += MB_CHAR2LEN(regstart); /* skip regstart */ 5442 if (skip_to_start(regstart, &col) == FAIL) 5443 break; 5444 } 5445 return 0L; 5446 } 5447 5448 #ifdef FEAT_RELTIME 5449 static int 5450 nfa_did_time_out() 5451 { 5452 if (nfa_time_limit != NULL && profile_passed_limit(nfa_time_limit)) 5453 { 5454 if (nfa_timed_out != NULL) 5455 *nfa_timed_out = TRUE; 5456 return TRUE; 5457 } 5458 return FALSE; 5459 } 5460 #endif 5461 5462 /* 5463 * Main matching routine. 5464 * 5465 * Run NFA to determine whether it matches rex.input. 5466 * 5467 * When "nfa_endp" is not NULL it is a required end-of-match position. 5468 * 5469 * Return TRUE if there is a match, FALSE otherwise. 5470 * When there is a match "submatch" contains the positions. 5471 * Note: Caller must ensure that: start != NULL. 5472 */ 5473 static int 5474 nfa_regmatch( 5475 nfa_regprog_T *prog, 5476 nfa_state_T *start, 5477 regsubs_T *submatch, 5478 regsubs_T *m) 5479 { 5480 int result; 5481 size_t size = 0; 5482 int flag = 0; 5483 int go_to_nextline = FALSE; 5484 nfa_thread_T *t; 5485 nfa_list_T list[2]; 5486 int listidx; 5487 nfa_list_T *thislist; 5488 nfa_list_T *nextlist; 5489 int *listids = NULL; 5490 int listids_len = 0; 5491 nfa_state_T *add_state; 5492 int add_here; 5493 int add_count; 5494 int add_off = 0; 5495 int toplevel = start->c == NFA_MOPEN; 5496 #ifdef NFA_REGEXP_DEBUG_LOG 5497 FILE *debug; 5498 #endif 5499 5500 /* Some patterns may take a long time to match, especially when using 5501 * recursive_regmatch(). Allow interrupting them with CTRL-C. */ 5502 fast_breakcheck(); 5503 if (got_int) 5504 return FALSE; 5505 #ifdef FEAT_RELTIME 5506 if (nfa_did_time_out()) 5507 return FALSE; 5508 #endif 5509 5510 #ifdef NFA_REGEXP_DEBUG_LOG 5511 debug = fopen(NFA_REGEXP_DEBUG_LOG, "a"); 5512 if (debug == NULL) 5513 { 5514 semsg("(NFA) COULD NOT OPEN %s!", NFA_REGEXP_DEBUG_LOG); 5515 return FALSE; 5516 } 5517 #endif 5518 nfa_match = FALSE; 5519 5520 /* Allocate memory for the lists of nodes. */ 5521 size = (prog->nstate + 1) * sizeof(nfa_thread_T); 5522 5523 list[0].t = (nfa_thread_T *)lalloc(size, TRUE); 5524 list[0].len = prog->nstate + 1; 5525 list[1].t = (nfa_thread_T *)lalloc(size, TRUE); 5526 list[1].len = prog->nstate + 1; 5527 if (list[0].t == NULL || list[1].t == NULL) 5528 goto theend; 5529 5530 #ifdef ENABLE_LOG 5531 log_fd = fopen(NFA_REGEXP_RUN_LOG, "a"); 5532 if (log_fd != NULL) 5533 { 5534 fprintf(log_fd, "**********************************\n"); 5535 nfa_set_code(start->c); 5536 fprintf(log_fd, " RUNNING nfa_regmatch() starting with state %d, code %s\n", 5537 abs(start->id), code); 5538 fprintf(log_fd, "**********************************\n"); 5539 } 5540 else 5541 { 5542 emsg(_(e_log_open_failed)); 5543 log_fd = stderr; 5544 } 5545 #endif 5546 5547 thislist = &list[0]; 5548 thislist->n = 0; 5549 thislist->has_pim = FALSE; 5550 nextlist = &list[1]; 5551 nextlist->n = 0; 5552 nextlist->has_pim = FALSE; 5553 #ifdef ENABLE_LOG 5554 fprintf(log_fd, "(---) STARTSTATE first\n"); 5555 #endif 5556 thislist->id = rex.nfa_listid + 1; 5557 5558 /* Inline optimized code for addstate(thislist, start, m, 0) if we know 5559 * it's the first MOPEN. */ 5560 if (toplevel) 5561 { 5562 if (REG_MULTI) 5563 { 5564 m->norm.list.multi[0].start_lnum = rex.lnum; 5565 m->norm.list.multi[0].start_col = (colnr_T)(rex.input - rex.line); 5566 } 5567 else 5568 m->norm.list.line[0].start = rex.input; 5569 m->norm.in_use = 1; 5570 addstate(thislist, start->out, m, NULL, 0); 5571 } 5572 else 5573 addstate(thislist, start, m, NULL, 0); 5574 5575 #define ADD_STATE_IF_MATCH(state) \ 5576 if (result) { \ 5577 add_state = state->out; \ 5578 add_off = clen; \ 5579 } 5580 5581 /* 5582 * Run for each character. 5583 */ 5584 for (;;) 5585 { 5586 int curc; 5587 int clen; 5588 5589 if (has_mbyte) 5590 { 5591 curc = (*mb_ptr2char)(rex.input); 5592 clen = (*mb_ptr2len)(rex.input); 5593 } 5594 else 5595 { 5596 curc = *rex.input; 5597 clen = 1; 5598 } 5599 if (curc == NUL) 5600 { 5601 clen = 0; 5602 go_to_nextline = FALSE; 5603 } 5604 5605 /* swap lists */ 5606 thislist = &list[flag]; 5607 nextlist = &list[flag ^= 1]; 5608 nextlist->n = 0; /* clear nextlist */ 5609 nextlist->has_pim = FALSE; 5610 ++rex.nfa_listid; 5611 if (prog->re_engine == AUTOMATIC_ENGINE 5612 && (rex.nfa_listid >= NFA_MAX_STATES 5613 # ifdef FEAT_EVAL 5614 || nfa_fail_for_testing 5615 # endif 5616 )) 5617 { 5618 /* too many states, retry with old engine */ 5619 nfa_match = NFA_TOO_EXPENSIVE; 5620 goto theend; 5621 } 5622 5623 thislist->id = rex.nfa_listid; 5624 nextlist->id = rex.nfa_listid + 1; 5625 5626 #ifdef ENABLE_LOG 5627 fprintf(log_fd, "------------------------------------------\n"); 5628 fprintf(log_fd, ">>> Reginput is \"%s\"\n", rex.input); 5629 fprintf(log_fd, ">>> Advanced one character... Current char is %c (code %d) \n", curc, (int)curc); 5630 fprintf(log_fd, ">>> Thislist has %d states available: ", thislist->n); 5631 { 5632 int i; 5633 5634 for (i = 0; i < thislist->n; i++) 5635 fprintf(log_fd, "%d ", abs(thislist->t[i].state->id)); 5636 } 5637 fprintf(log_fd, "\n"); 5638 #endif 5639 5640 #ifdef NFA_REGEXP_DEBUG_LOG 5641 fprintf(debug, "\n-------------------\n"); 5642 #endif 5643 /* 5644 * If the state lists are empty we can stop. 5645 */ 5646 if (thislist->n == 0) 5647 break; 5648 5649 /* compute nextlist */ 5650 for (listidx = 0; listidx < thislist->n; ++listidx) 5651 { 5652 /* If the list gets very long there probably is something wrong. 5653 * At least allow interrupting with CTRL-C. */ 5654 fast_breakcheck(); 5655 if (got_int) 5656 break; 5657 #ifdef FEAT_RELTIME 5658 if (nfa_time_limit != NULL && ++nfa_time_count == 20) 5659 { 5660 nfa_time_count = 0; 5661 if (nfa_did_time_out()) 5662 break; 5663 } 5664 #endif 5665 t = &thislist->t[listidx]; 5666 5667 #ifdef NFA_REGEXP_DEBUG_LOG 5668 nfa_set_code(t->state->c); 5669 fprintf(debug, "%s, ", code); 5670 #endif 5671 #ifdef ENABLE_LOG 5672 { 5673 int col; 5674 5675 if (t->subs.norm.in_use <= 0) 5676 col = -1; 5677 else if (REG_MULTI) 5678 col = t->subs.norm.list.multi[0].start_col; 5679 else 5680 col = (int)(t->subs.norm.list.line[0].start - rex.line); 5681 nfa_set_code(t->state->c); 5682 fprintf(log_fd, "(%d) char %d %s (start col %d)%s... \n", 5683 abs(t->state->id), (int)t->state->c, code, col, 5684 pim_info(&t->pim)); 5685 } 5686 #endif 5687 5688 /* 5689 * Handle the possible codes of the current state. 5690 * The most important is NFA_MATCH. 5691 */ 5692 add_state = NULL; 5693 add_here = FALSE; 5694 add_count = 0; 5695 switch (t->state->c) 5696 { 5697 case NFA_MATCH: 5698 { 5699 /* If the match ends before a composing characters and 5700 * rex.reg_icombine is not set, that is not really a match. */ 5701 if (enc_utf8 && !rex.reg_icombine && utf_iscomposing(curc)) 5702 break; 5703 5704 nfa_match = TRUE; 5705 copy_sub(&submatch->norm, &t->subs.norm); 5706 #ifdef FEAT_SYN_HL 5707 if (rex.nfa_has_zsubexpr) 5708 copy_sub(&submatch->synt, &t->subs.synt); 5709 #endif 5710 #ifdef ENABLE_LOG 5711 log_subsexpr(&t->subs); 5712 #endif 5713 /* Found the left-most longest match, do not look at any other 5714 * states at this position. When the list of states is going 5715 * to be empty quit without advancing, so that "rex.input" is 5716 * correct. */ 5717 if (nextlist->n == 0) 5718 clen = 0; 5719 goto nextchar; 5720 } 5721 5722 case NFA_END_INVISIBLE: 5723 case NFA_END_INVISIBLE_NEG: 5724 case NFA_END_PATTERN: 5725 /* 5726 * This is only encountered after a NFA_START_INVISIBLE or 5727 * NFA_START_INVISIBLE_BEFORE node. 5728 * They surround a zero-width group, used with "\@=", "\&", 5729 * "\@!", "\@<=" and "\@<!". 5730 * If we got here, it means that the current "invisible" group 5731 * finished successfully, so return control to the parent 5732 * nfa_regmatch(). For a look-behind match only when it ends 5733 * in the position in "nfa_endp". 5734 * Submatches are stored in *m, and used in the parent call. 5735 */ 5736 #ifdef ENABLE_LOG 5737 if (nfa_endp != NULL) 5738 { 5739 if (REG_MULTI) 5740 fprintf(log_fd, "Current lnum: %d, endp lnum: %d; current col: %d, endp col: %d\n", 5741 (int)rex.lnum, 5742 (int)nfa_endp->se_u.pos.lnum, 5743 (int)(rex.input - rex.line), 5744 nfa_endp->se_u.pos.col); 5745 else 5746 fprintf(log_fd, "Current col: %d, endp col: %d\n", 5747 (int)(rex.input - rex.line), 5748 (int)(nfa_endp->se_u.ptr - rex.input)); 5749 } 5750 #endif 5751 /* If "nfa_endp" is set it's only a match if it ends at 5752 * "nfa_endp" */ 5753 if (nfa_endp != NULL && (REG_MULTI 5754 ? (rex.lnum != nfa_endp->se_u.pos.lnum 5755 || (int)(rex.input - rex.line) 5756 != nfa_endp->se_u.pos.col) 5757 : rex.input != nfa_endp->se_u.ptr)) 5758 break; 5759 5760 /* do not set submatches for \@! */ 5761 if (t->state->c != NFA_END_INVISIBLE_NEG) 5762 { 5763 copy_sub(&m->norm, &t->subs.norm); 5764 #ifdef FEAT_SYN_HL 5765 if (rex.nfa_has_zsubexpr) 5766 copy_sub(&m->synt, &t->subs.synt); 5767 #endif 5768 } 5769 #ifdef ENABLE_LOG 5770 fprintf(log_fd, "Match found:\n"); 5771 log_subsexpr(m); 5772 #endif 5773 nfa_match = TRUE; 5774 /* See comment above at "goto nextchar". */ 5775 if (nextlist->n == 0) 5776 clen = 0; 5777 goto nextchar; 5778 5779 case NFA_START_INVISIBLE: 5780 case NFA_START_INVISIBLE_FIRST: 5781 case NFA_START_INVISIBLE_NEG: 5782 case NFA_START_INVISIBLE_NEG_FIRST: 5783 case NFA_START_INVISIBLE_BEFORE: 5784 case NFA_START_INVISIBLE_BEFORE_FIRST: 5785 case NFA_START_INVISIBLE_BEFORE_NEG: 5786 case NFA_START_INVISIBLE_BEFORE_NEG_FIRST: 5787 { 5788 #ifdef ENABLE_LOG 5789 fprintf(log_fd, "Failure chance invisible: %d, what follows: %d\n", 5790 failure_chance(t->state->out, 0), 5791 failure_chance(t->state->out1->out, 0)); 5792 #endif 5793 /* Do it directly if there already is a PIM or when 5794 * nfa_postprocess() detected it will work better. */ 5795 if (t->pim.result != NFA_PIM_UNUSED 5796 || t->state->c == NFA_START_INVISIBLE_FIRST 5797 || t->state->c == NFA_START_INVISIBLE_NEG_FIRST 5798 || t->state->c == NFA_START_INVISIBLE_BEFORE_FIRST 5799 || t->state->c == NFA_START_INVISIBLE_BEFORE_NEG_FIRST) 5800 { 5801 int in_use = m->norm.in_use; 5802 5803 /* Copy submatch info for the recursive call, opposite 5804 * of what happens on success below. */ 5805 copy_sub_off(&m->norm, &t->subs.norm); 5806 #ifdef FEAT_SYN_HL 5807 if (rex.nfa_has_zsubexpr) 5808 copy_sub_off(&m->synt, &t->subs.synt); 5809 #endif 5810 5811 /* 5812 * First try matching the invisible match, then what 5813 * follows. 5814 */ 5815 result = recursive_regmatch(t->state, NULL, prog, 5816 submatch, m, &listids, &listids_len); 5817 if (result == NFA_TOO_EXPENSIVE) 5818 { 5819 nfa_match = result; 5820 goto theend; 5821 } 5822 5823 /* for \@! and \@<! it is a match when the result is 5824 * FALSE */ 5825 if (result != (t->state->c == NFA_START_INVISIBLE_NEG 5826 || t->state->c == NFA_START_INVISIBLE_NEG_FIRST 5827 || t->state->c 5828 == NFA_START_INVISIBLE_BEFORE_NEG 5829 || t->state->c 5830 == NFA_START_INVISIBLE_BEFORE_NEG_FIRST)) 5831 { 5832 /* Copy submatch info from the recursive call */ 5833 copy_sub_off(&t->subs.norm, &m->norm); 5834 #ifdef FEAT_SYN_HL 5835 if (rex.nfa_has_zsubexpr) 5836 copy_sub_off(&t->subs.synt, &m->synt); 5837 #endif 5838 /* If the pattern has \ze and it matched in the 5839 * sub pattern, use it. */ 5840 copy_ze_off(&t->subs.norm, &m->norm); 5841 5842 /* t->state->out1 is the corresponding 5843 * END_INVISIBLE node; Add its out to the current 5844 * list (zero-width match). */ 5845 add_here = TRUE; 5846 add_state = t->state->out1->out; 5847 } 5848 m->norm.in_use = in_use; 5849 } 5850 else 5851 { 5852 nfa_pim_T pim; 5853 5854 /* 5855 * First try matching what follows. Only if a match 5856 * is found verify the invisible match matches. Add a 5857 * nfa_pim_T to the following states, it contains info 5858 * about the invisible match. 5859 */ 5860 pim.state = t->state; 5861 pim.result = NFA_PIM_TODO; 5862 pim.subs.norm.in_use = 0; 5863 #ifdef FEAT_SYN_HL 5864 pim.subs.synt.in_use = 0; 5865 #endif 5866 if (REG_MULTI) 5867 { 5868 pim.end.pos.col = (int)(rex.input - rex.line); 5869 pim.end.pos.lnum = rex.lnum; 5870 } 5871 else 5872 pim.end.ptr = rex.input; 5873 5874 /* t->state->out1 is the corresponding END_INVISIBLE 5875 * node; Add its out to the current list (zero-width 5876 * match). */ 5877 addstate_here(thislist, t->state->out1->out, &t->subs, 5878 &pim, &listidx); 5879 } 5880 } 5881 break; 5882 5883 case NFA_START_PATTERN: 5884 { 5885 nfa_state_T *skip = NULL; 5886 #ifdef ENABLE_LOG 5887 int skip_lid = 0; 5888 #endif 5889 5890 /* There is no point in trying to match the pattern if the 5891 * output state is not going to be added to the list. */ 5892 if (state_in_list(nextlist, t->state->out1->out, &t->subs)) 5893 { 5894 skip = t->state->out1->out; 5895 #ifdef ENABLE_LOG 5896 skip_lid = nextlist->id; 5897 #endif 5898 } 5899 else if (state_in_list(nextlist, 5900 t->state->out1->out->out, &t->subs)) 5901 { 5902 skip = t->state->out1->out->out; 5903 #ifdef ENABLE_LOG 5904 skip_lid = nextlist->id; 5905 #endif 5906 } 5907 else if (state_in_list(thislist, 5908 t->state->out1->out->out, &t->subs)) 5909 { 5910 skip = t->state->out1->out->out; 5911 #ifdef ENABLE_LOG 5912 skip_lid = thislist->id; 5913 #endif 5914 } 5915 if (skip != NULL) 5916 { 5917 #ifdef ENABLE_LOG 5918 nfa_set_code(skip->c); 5919 fprintf(log_fd, "> Not trying to match pattern, output state %d is already in list %d. char %d: %s\n", 5920 abs(skip->id), skip_lid, skip->c, code); 5921 #endif 5922 break; 5923 } 5924 /* Copy submatch info to the recursive call, opposite of what 5925 * happens afterwards. */ 5926 copy_sub_off(&m->norm, &t->subs.norm); 5927 #ifdef FEAT_SYN_HL 5928 if (rex.nfa_has_zsubexpr) 5929 copy_sub_off(&m->synt, &t->subs.synt); 5930 #endif 5931 5932 /* First try matching the pattern. */ 5933 result = recursive_regmatch(t->state, NULL, prog, 5934 submatch, m, &listids, &listids_len); 5935 if (result == NFA_TOO_EXPENSIVE) 5936 { 5937 nfa_match = result; 5938 goto theend; 5939 } 5940 if (result) 5941 { 5942 int bytelen; 5943 5944 #ifdef ENABLE_LOG 5945 fprintf(log_fd, "NFA_START_PATTERN matches:\n"); 5946 log_subsexpr(m); 5947 #endif 5948 /* Copy submatch info from the recursive call */ 5949 copy_sub_off(&t->subs.norm, &m->norm); 5950 #ifdef FEAT_SYN_HL 5951 if (rex.nfa_has_zsubexpr) 5952 copy_sub_off(&t->subs.synt, &m->synt); 5953 #endif 5954 /* Now we need to skip over the matched text and then 5955 * continue with what follows. */ 5956 if (REG_MULTI) 5957 /* TODO: multi-line match */ 5958 bytelen = m->norm.list.multi[0].end_col 5959 - (int)(rex.input - rex.line); 5960 else 5961 bytelen = (int)(m->norm.list.line[0].end - rex.input); 5962 5963 #ifdef ENABLE_LOG 5964 fprintf(log_fd, "NFA_START_PATTERN length: %d\n", bytelen); 5965 #endif 5966 if (bytelen == 0) 5967 { 5968 /* empty match, output of corresponding 5969 * NFA_END_PATTERN/NFA_SKIP to be used at current 5970 * position */ 5971 add_here = TRUE; 5972 add_state = t->state->out1->out->out; 5973 } 5974 else if (bytelen <= clen) 5975 { 5976 /* match current character, output of corresponding 5977 * NFA_END_PATTERN to be used at next position. */ 5978 add_state = t->state->out1->out->out; 5979 add_off = clen; 5980 } 5981 else 5982 { 5983 /* skip over the matched characters, set character 5984 * count in NFA_SKIP */ 5985 add_state = t->state->out1->out; 5986 add_off = bytelen; 5987 add_count = bytelen - clen; 5988 } 5989 } 5990 break; 5991 } 5992 5993 case NFA_BOL: 5994 if (rex.input == rex.line) 5995 { 5996 add_here = TRUE; 5997 add_state = t->state->out; 5998 } 5999 break; 6000 6001 case NFA_EOL: 6002 if (curc == NUL) 6003 { 6004 add_here = TRUE; 6005 add_state = t->state->out; 6006 } 6007 break; 6008 6009 case NFA_BOW: 6010 result = TRUE; 6011 6012 if (curc == NUL) 6013 result = FALSE; 6014 else if (has_mbyte) 6015 { 6016 int this_class; 6017 6018 /* Get class of current and previous char (if it exists). */ 6019 this_class = mb_get_class_buf(rex.input, rex.reg_buf); 6020 if (this_class <= 1) 6021 result = FALSE; 6022 else if (reg_prev_class() == this_class) 6023 result = FALSE; 6024 } 6025 else if (!vim_iswordc_buf(curc, rex.reg_buf) 6026 || (rex.input > rex.line 6027 && vim_iswordc_buf(rex.input[-1], rex.reg_buf))) 6028 result = FALSE; 6029 if (result) 6030 { 6031 add_here = TRUE; 6032 add_state = t->state->out; 6033 } 6034 break; 6035 6036 case NFA_EOW: 6037 result = TRUE; 6038 if (rex.input == rex.line) 6039 result = FALSE; 6040 else if (has_mbyte) 6041 { 6042 int this_class, prev_class; 6043 6044 /* Get class of current and previous char (if it exists). */ 6045 this_class = mb_get_class_buf(rex.input, rex.reg_buf); 6046 prev_class = reg_prev_class(); 6047 if (this_class == prev_class 6048 || prev_class == 0 || prev_class == 1) 6049 result = FALSE; 6050 } 6051 else if (!vim_iswordc_buf(rex.input[-1], rex.reg_buf) 6052 || (rex.input[0] != NUL 6053 && vim_iswordc_buf(curc, rex.reg_buf))) 6054 result = FALSE; 6055 if (result) 6056 { 6057 add_here = TRUE; 6058 add_state = t->state->out; 6059 } 6060 break; 6061 6062 case NFA_BOF: 6063 if (rex.lnum == 0 && rex.input == rex.line 6064 && (!REG_MULTI || rex.reg_firstlnum == 1)) 6065 { 6066 add_here = TRUE; 6067 add_state = t->state->out; 6068 } 6069 break; 6070 6071 case NFA_EOF: 6072 if (rex.lnum == rex.reg_maxline && curc == NUL) 6073 { 6074 add_here = TRUE; 6075 add_state = t->state->out; 6076 } 6077 break; 6078 6079 case NFA_COMPOSING: 6080 { 6081 int mc = curc; 6082 int len = 0; 6083 nfa_state_T *end; 6084 nfa_state_T *sta; 6085 int cchars[MAX_MCO]; 6086 int ccount = 0; 6087 int j; 6088 6089 sta = t->state->out; 6090 len = 0; 6091 if (utf_iscomposing(sta->c)) 6092 { 6093 /* Only match composing character(s), ignore base 6094 * character. Used for ".{composing}" and "{composing}" 6095 * (no preceding character). */ 6096 len += mb_char2len(mc); 6097 } 6098 if (rex.reg_icombine && len == 0) 6099 { 6100 /* If \Z was present, then ignore composing characters. 6101 * When ignoring the base character this always matches. */ 6102 if (sta->c != curc) 6103 result = FAIL; 6104 else 6105 result = OK; 6106 while (sta->c != NFA_END_COMPOSING) 6107 sta = sta->out; 6108 } 6109 6110 /* Check base character matches first, unless ignored. */ 6111 else if (len > 0 || mc == sta->c) 6112 { 6113 if (len == 0) 6114 { 6115 len += mb_char2len(mc); 6116 sta = sta->out; 6117 } 6118 6119 /* We don't care about the order of composing characters. 6120 * Get them into cchars[] first. */ 6121 while (len < clen) 6122 { 6123 mc = mb_ptr2char(rex.input + len); 6124 cchars[ccount++] = mc; 6125 len += mb_char2len(mc); 6126 if (ccount == MAX_MCO) 6127 break; 6128 } 6129 6130 /* Check that each composing char in the pattern matches a 6131 * composing char in the text. We do not check if all 6132 * composing chars are matched. */ 6133 result = OK; 6134 while (sta->c != NFA_END_COMPOSING) 6135 { 6136 for (j = 0; j < ccount; ++j) 6137 if (cchars[j] == sta->c) 6138 break; 6139 if (j == ccount) 6140 { 6141 result = FAIL; 6142 break; 6143 } 6144 sta = sta->out; 6145 } 6146 } 6147 else 6148 result = FAIL; 6149 6150 end = t->state->out1; /* NFA_END_COMPOSING */ 6151 ADD_STATE_IF_MATCH(end); 6152 break; 6153 } 6154 6155 case NFA_NEWL: 6156 if (curc == NUL && !rex.reg_line_lbr && REG_MULTI 6157 && rex.lnum <= rex.reg_maxline) 6158 { 6159 go_to_nextline = TRUE; 6160 /* Pass -1 for the offset, which means taking the position 6161 * at the start of the next line. */ 6162 add_state = t->state->out; 6163 add_off = -1; 6164 } 6165 else if (curc == '\n' && rex.reg_line_lbr) 6166 { 6167 /* match \n as if it is an ordinary character */ 6168 add_state = t->state->out; 6169 add_off = 1; 6170 } 6171 break; 6172 6173 case NFA_START_COLL: 6174 case NFA_START_NEG_COLL: 6175 { 6176 /* What follows is a list of characters, until NFA_END_COLL. 6177 * One of them must match or none of them must match. */ 6178 nfa_state_T *state; 6179 int result_if_matched; 6180 int c1, c2; 6181 6182 /* Never match EOL. If it's part of the collection it is added 6183 * as a separate state with an OR. */ 6184 if (curc == NUL) 6185 break; 6186 6187 state = t->state->out; 6188 result_if_matched = (t->state->c == NFA_START_COLL); 6189 for (;;) 6190 { 6191 if (state->c == NFA_END_COLL) 6192 { 6193 result = !result_if_matched; 6194 break; 6195 } 6196 if (state->c == NFA_RANGE_MIN) 6197 { 6198 c1 = state->val; 6199 state = state->out; /* advance to NFA_RANGE_MAX */ 6200 c2 = state->val; 6201 #ifdef ENABLE_LOG 6202 fprintf(log_fd, "NFA_RANGE_MIN curc=%d c1=%d c2=%d\n", 6203 curc, c1, c2); 6204 #endif 6205 if (curc >= c1 && curc <= c2) 6206 { 6207 result = result_if_matched; 6208 break; 6209 } 6210 if (rex.reg_ic) 6211 { 6212 int curc_low = MB_TOLOWER(curc); 6213 int done = FALSE; 6214 6215 for ( ; c1 <= c2; ++c1) 6216 if (MB_TOLOWER(c1) == curc_low) 6217 { 6218 result = result_if_matched; 6219 done = TRUE; 6220 break; 6221 } 6222 if (done) 6223 break; 6224 } 6225 } 6226 else if (state->c < 0 ? check_char_class(state->c, curc) 6227 : (curc == state->c 6228 || (rex.reg_ic && MB_TOLOWER(curc) 6229 == MB_TOLOWER(state->c)))) 6230 { 6231 result = result_if_matched; 6232 break; 6233 } 6234 state = state->out; 6235 } 6236 if (result) 6237 { 6238 /* next state is in out of the NFA_END_COLL, out1 of 6239 * START points to the END state */ 6240 add_state = t->state->out1->out; 6241 add_off = clen; 6242 } 6243 break; 6244 } 6245 6246 case NFA_ANY: 6247 /* Any char except '\0', (end of input) does not match. */ 6248 if (curc > 0) 6249 { 6250 add_state = t->state->out; 6251 add_off = clen; 6252 } 6253 break; 6254 6255 case NFA_ANY_COMPOSING: 6256 /* On a composing character skip over it. Otherwise do 6257 * nothing. Always matches. */ 6258 if (enc_utf8 && utf_iscomposing(curc)) 6259 { 6260 add_off = clen; 6261 } 6262 else 6263 { 6264 add_here = TRUE; 6265 add_off = 0; 6266 } 6267 add_state = t->state->out; 6268 break; 6269 6270 /* 6271 * Character classes like \a for alpha, \d for digit etc. 6272 */ 6273 case NFA_IDENT: /* \i */ 6274 result = vim_isIDc(curc); 6275 ADD_STATE_IF_MATCH(t->state); 6276 break; 6277 6278 case NFA_SIDENT: /* \I */ 6279 result = !VIM_ISDIGIT(curc) && vim_isIDc(curc); 6280 ADD_STATE_IF_MATCH(t->state); 6281 break; 6282 6283 case NFA_KWORD: /* \k */ 6284 result = vim_iswordp_buf(rex.input, rex.reg_buf); 6285 ADD_STATE_IF_MATCH(t->state); 6286 break; 6287 6288 case NFA_SKWORD: /* \K */ 6289 result = !VIM_ISDIGIT(curc) 6290 && vim_iswordp_buf(rex.input, rex.reg_buf); 6291 ADD_STATE_IF_MATCH(t->state); 6292 break; 6293 6294 case NFA_FNAME: /* \f */ 6295 result = vim_isfilec(curc); 6296 ADD_STATE_IF_MATCH(t->state); 6297 break; 6298 6299 case NFA_SFNAME: /* \F */ 6300 result = !VIM_ISDIGIT(curc) && vim_isfilec(curc); 6301 ADD_STATE_IF_MATCH(t->state); 6302 break; 6303 6304 case NFA_PRINT: /* \p */ 6305 result = vim_isprintc(PTR2CHAR(rex.input)); 6306 ADD_STATE_IF_MATCH(t->state); 6307 break; 6308 6309 case NFA_SPRINT: /* \P */ 6310 result = !VIM_ISDIGIT(curc) && vim_isprintc(PTR2CHAR(rex.input)); 6311 ADD_STATE_IF_MATCH(t->state); 6312 break; 6313 6314 case NFA_WHITE: /* \s */ 6315 result = VIM_ISWHITE(curc); 6316 ADD_STATE_IF_MATCH(t->state); 6317 break; 6318 6319 case NFA_NWHITE: /* \S */ 6320 result = curc != NUL && !VIM_ISWHITE(curc); 6321 ADD_STATE_IF_MATCH(t->state); 6322 break; 6323 6324 case NFA_DIGIT: /* \d */ 6325 result = ri_digit(curc); 6326 ADD_STATE_IF_MATCH(t->state); 6327 break; 6328 6329 case NFA_NDIGIT: /* \D */ 6330 result = curc != NUL && !ri_digit(curc); 6331 ADD_STATE_IF_MATCH(t->state); 6332 break; 6333 6334 case NFA_HEX: /* \x */ 6335 result = ri_hex(curc); 6336 ADD_STATE_IF_MATCH(t->state); 6337 break; 6338 6339 case NFA_NHEX: /* \X */ 6340 result = curc != NUL && !ri_hex(curc); 6341 ADD_STATE_IF_MATCH(t->state); 6342 break; 6343 6344 case NFA_OCTAL: /* \o */ 6345 result = ri_octal(curc); 6346 ADD_STATE_IF_MATCH(t->state); 6347 break; 6348 6349 case NFA_NOCTAL: /* \O */ 6350 result = curc != NUL && !ri_octal(curc); 6351 ADD_STATE_IF_MATCH(t->state); 6352 break; 6353 6354 case NFA_WORD: /* \w */ 6355 result = ri_word(curc); 6356 ADD_STATE_IF_MATCH(t->state); 6357 break; 6358 6359 case NFA_NWORD: /* \W */ 6360 result = curc != NUL && !ri_word(curc); 6361 ADD_STATE_IF_MATCH(t->state); 6362 break; 6363 6364 case NFA_HEAD: /* \h */ 6365 result = ri_head(curc); 6366 ADD_STATE_IF_MATCH(t->state); 6367 break; 6368 6369 case NFA_NHEAD: /* \H */ 6370 result = curc != NUL && !ri_head(curc); 6371 ADD_STATE_IF_MATCH(t->state); 6372 break; 6373 6374 case NFA_ALPHA: /* \a */ 6375 result = ri_alpha(curc); 6376 ADD_STATE_IF_MATCH(t->state); 6377 break; 6378 6379 case NFA_NALPHA: /* \A */ 6380 result = curc != NUL && !ri_alpha(curc); 6381 ADD_STATE_IF_MATCH(t->state); 6382 break; 6383 6384 case NFA_LOWER: /* \l */ 6385 result = ri_lower(curc); 6386 ADD_STATE_IF_MATCH(t->state); 6387 break; 6388 6389 case NFA_NLOWER: /* \L */ 6390 result = curc != NUL && !ri_lower(curc); 6391 ADD_STATE_IF_MATCH(t->state); 6392 break; 6393 6394 case NFA_UPPER: /* \u */ 6395 result = ri_upper(curc); 6396 ADD_STATE_IF_MATCH(t->state); 6397 break; 6398 6399 case NFA_NUPPER: /* \U */ 6400 result = curc != NUL && !ri_upper(curc); 6401 ADD_STATE_IF_MATCH(t->state); 6402 break; 6403 6404 case NFA_LOWER_IC: /* [a-z] */ 6405 result = ri_lower(curc) || (rex.reg_ic && ri_upper(curc)); 6406 ADD_STATE_IF_MATCH(t->state); 6407 break; 6408 6409 case NFA_NLOWER_IC: /* [^a-z] */ 6410 result = curc != NUL 6411 && !(ri_lower(curc) || (rex.reg_ic && ri_upper(curc))); 6412 ADD_STATE_IF_MATCH(t->state); 6413 break; 6414 6415 case NFA_UPPER_IC: /* [A-Z] */ 6416 result = ri_upper(curc) || (rex.reg_ic && ri_lower(curc)); 6417 ADD_STATE_IF_MATCH(t->state); 6418 break; 6419 6420 case NFA_NUPPER_IC: /* ^[A-Z] */ 6421 result = curc != NUL 6422 && !(ri_upper(curc) || (rex.reg_ic && ri_lower(curc))); 6423 ADD_STATE_IF_MATCH(t->state); 6424 break; 6425 6426 case NFA_BACKREF1: 6427 case NFA_BACKREF2: 6428 case NFA_BACKREF3: 6429 case NFA_BACKREF4: 6430 case NFA_BACKREF5: 6431 case NFA_BACKREF6: 6432 case NFA_BACKREF7: 6433 case NFA_BACKREF8: 6434 case NFA_BACKREF9: 6435 #ifdef FEAT_SYN_HL 6436 case NFA_ZREF1: 6437 case NFA_ZREF2: 6438 case NFA_ZREF3: 6439 case NFA_ZREF4: 6440 case NFA_ZREF5: 6441 case NFA_ZREF6: 6442 case NFA_ZREF7: 6443 case NFA_ZREF8: 6444 case NFA_ZREF9: 6445 #endif 6446 /* \1 .. \9 \z1 .. \z9 */ 6447 { 6448 int subidx; 6449 int bytelen; 6450 6451 if (t->state->c <= NFA_BACKREF9) 6452 { 6453 subidx = t->state->c - NFA_BACKREF1 + 1; 6454 result = match_backref(&t->subs.norm, subidx, &bytelen); 6455 } 6456 #ifdef FEAT_SYN_HL 6457 else 6458 { 6459 subidx = t->state->c - NFA_ZREF1 + 1; 6460 result = match_zref(subidx, &bytelen); 6461 } 6462 #endif 6463 6464 if (result) 6465 { 6466 if (bytelen == 0) 6467 { 6468 /* empty match always works, output of NFA_SKIP to be 6469 * used next */ 6470 add_here = TRUE; 6471 add_state = t->state->out->out; 6472 } 6473 else if (bytelen <= clen) 6474 { 6475 /* match current character, jump ahead to out of 6476 * NFA_SKIP */ 6477 add_state = t->state->out->out; 6478 add_off = clen; 6479 } 6480 else 6481 { 6482 /* skip over the matched characters, set character 6483 * count in NFA_SKIP */ 6484 add_state = t->state->out; 6485 add_off = bytelen; 6486 add_count = bytelen - clen; 6487 } 6488 } 6489 break; 6490 } 6491 case NFA_SKIP: 6492 /* character of previous matching \1 .. \9 or \@> */ 6493 if (t->count - clen <= 0) 6494 { 6495 /* end of match, go to what follows */ 6496 add_state = t->state->out; 6497 add_off = clen; 6498 } 6499 else 6500 { 6501 /* add state again with decremented count */ 6502 add_state = t->state; 6503 add_off = 0; 6504 add_count = t->count - clen; 6505 } 6506 break; 6507 6508 case NFA_LNUM: 6509 case NFA_LNUM_GT: 6510 case NFA_LNUM_LT: 6511 result = (REG_MULTI && 6512 nfa_re_num_cmp(t->state->val, t->state->c - NFA_LNUM, 6513 (long_u)(rex.lnum + rex.reg_firstlnum))); 6514 if (result) 6515 { 6516 add_here = TRUE; 6517 add_state = t->state->out; 6518 } 6519 break; 6520 6521 case NFA_COL: 6522 case NFA_COL_GT: 6523 case NFA_COL_LT: 6524 result = nfa_re_num_cmp(t->state->val, t->state->c - NFA_COL, 6525 (long_u)(rex.input - rex.line) + 1); 6526 if (result) 6527 { 6528 add_here = TRUE; 6529 add_state = t->state->out; 6530 } 6531 break; 6532 6533 case NFA_VCOL: 6534 case NFA_VCOL_GT: 6535 case NFA_VCOL_LT: 6536 { 6537 int op = t->state->c - NFA_VCOL; 6538 colnr_T col = (colnr_T)(rex.input - rex.line); 6539 win_T *wp = rex.reg_win == NULL ? curwin : rex.reg_win; 6540 6541 /* Bail out quickly when there can't be a match, avoid the 6542 * overhead of win_linetabsize() on long lines. */ 6543 if (op != 1 && col > t->state->val 6544 * (has_mbyte ? MB_MAXBYTES : 1)) 6545 break; 6546 result = FALSE; 6547 if (op == 1 && col - 1 > t->state->val && col > 100) 6548 { 6549 int ts = wp->w_buffer->b_p_ts; 6550 6551 /* Guess that a character won't use more columns than 6552 * 'tabstop', with a minimum of 4. */ 6553 if (ts < 4) 6554 ts = 4; 6555 result = col > t->state->val * ts; 6556 } 6557 if (!result) 6558 result = nfa_re_num_cmp(t->state->val, op, 6559 (long_u)win_linetabsize(wp, rex.line, col) + 1); 6560 if (result) 6561 { 6562 add_here = TRUE; 6563 add_state = t->state->out; 6564 } 6565 } 6566 break; 6567 6568 case NFA_MARK: 6569 case NFA_MARK_GT: 6570 case NFA_MARK_LT: 6571 { 6572 pos_T *pos = getmark_buf(rex.reg_buf, t->state->val, FALSE); 6573 6574 /* Compare the mark position to the match position. */ 6575 result = (pos != NULL /* mark doesn't exist */ 6576 && pos->lnum > 0 /* mark isn't set in reg_buf */ 6577 && (pos->lnum == rex.lnum + rex.reg_firstlnum 6578 ? (pos->col == (colnr_T)(rex.input - rex.line) 6579 ? t->state->c == NFA_MARK 6580 : (pos->col < (colnr_T)(rex.input - rex.line) 6581 ? t->state->c == NFA_MARK_GT 6582 : t->state->c == NFA_MARK_LT)) 6583 : (pos->lnum < rex.lnum + rex.reg_firstlnum 6584 ? t->state->c == NFA_MARK_GT 6585 : t->state->c == NFA_MARK_LT))); 6586 if (result) 6587 { 6588 add_here = TRUE; 6589 add_state = t->state->out; 6590 } 6591 break; 6592 } 6593 6594 case NFA_CURSOR: 6595 result = (rex.reg_win != NULL 6596 && (rex.lnum + rex.reg_firstlnum 6597 == rex.reg_win->w_cursor.lnum) 6598 && ((colnr_T)(rex.input - rex.line) 6599 == rex.reg_win->w_cursor.col)); 6600 if (result) 6601 { 6602 add_here = TRUE; 6603 add_state = t->state->out; 6604 } 6605 break; 6606 6607 case NFA_VISUAL: 6608 result = reg_match_visual(); 6609 if (result) 6610 { 6611 add_here = TRUE; 6612 add_state = t->state->out; 6613 } 6614 break; 6615 6616 case NFA_MOPEN1: 6617 case NFA_MOPEN2: 6618 case NFA_MOPEN3: 6619 case NFA_MOPEN4: 6620 case NFA_MOPEN5: 6621 case NFA_MOPEN6: 6622 case NFA_MOPEN7: 6623 case NFA_MOPEN8: 6624 case NFA_MOPEN9: 6625 #ifdef FEAT_SYN_HL 6626 case NFA_ZOPEN: 6627 case NFA_ZOPEN1: 6628 case NFA_ZOPEN2: 6629 case NFA_ZOPEN3: 6630 case NFA_ZOPEN4: 6631 case NFA_ZOPEN5: 6632 case NFA_ZOPEN6: 6633 case NFA_ZOPEN7: 6634 case NFA_ZOPEN8: 6635 case NFA_ZOPEN9: 6636 #endif 6637 case NFA_NOPEN: 6638 case NFA_ZSTART: 6639 /* These states are only added to be able to bail out when 6640 * they are added again, nothing is to be done. */ 6641 break; 6642 6643 default: /* regular character */ 6644 { 6645 int c = t->state->c; 6646 6647 #ifdef DEBUG 6648 if (c < 0) 6649 siemsg("INTERNAL: Negative state char: %ld", c); 6650 #endif 6651 result = (c == curc); 6652 6653 if (!result && rex.reg_ic) 6654 result = MB_TOLOWER(c) == MB_TOLOWER(curc); 6655 /* If rex.reg_icombine is not set only skip over the character 6656 * itself. When it is set skip over composing characters. */ 6657 if (result && enc_utf8 && !rex.reg_icombine) 6658 clen = utf_ptr2len(rex.input); 6659 ADD_STATE_IF_MATCH(t->state); 6660 break; 6661 } 6662 6663 } /* switch (t->state->c) */ 6664 6665 if (add_state != NULL) 6666 { 6667 nfa_pim_T *pim; 6668 nfa_pim_T pim_copy; 6669 6670 if (t->pim.result == NFA_PIM_UNUSED) 6671 pim = NULL; 6672 else 6673 pim = &t->pim; 6674 6675 /* Handle the postponed invisible match if the match might end 6676 * without advancing and before the end of the line. */ 6677 if (pim != NULL && (clen == 0 || match_follows(add_state, 0))) 6678 { 6679 if (pim->result == NFA_PIM_TODO) 6680 { 6681 #ifdef ENABLE_LOG 6682 fprintf(log_fd, "\n"); 6683 fprintf(log_fd, "==================================\n"); 6684 fprintf(log_fd, "Postponed recursive nfa_regmatch()\n"); 6685 fprintf(log_fd, "\n"); 6686 #endif 6687 result = recursive_regmatch(pim->state, pim, 6688 prog, submatch, m, &listids, &listids_len); 6689 pim->result = result ? NFA_PIM_MATCH : NFA_PIM_NOMATCH; 6690 /* for \@! and \@<! it is a match when the result is 6691 * FALSE */ 6692 if (result != (pim->state->c == NFA_START_INVISIBLE_NEG 6693 || pim->state->c == NFA_START_INVISIBLE_NEG_FIRST 6694 || pim->state->c 6695 == NFA_START_INVISIBLE_BEFORE_NEG 6696 || pim->state->c 6697 == NFA_START_INVISIBLE_BEFORE_NEG_FIRST)) 6698 { 6699 /* Copy submatch info from the recursive call */ 6700 copy_sub_off(&pim->subs.norm, &m->norm); 6701 #ifdef FEAT_SYN_HL 6702 if (rex.nfa_has_zsubexpr) 6703 copy_sub_off(&pim->subs.synt, &m->synt); 6704 #endif 6705 } 6706 } 6707 else 6708 { 6709 result = (pim->result == NFA_PIM_MATCH); 6710 #ifdef ENABLE_LOG 6711 fprintf(log_fd, "\n"); 6712 fprintf(log_fd, "Using previous recursive nfa_regmatch() result, result == %d\n", pim->result); 6713 fprintf(log_fd, "MATCH = %s\n", result == TRUE ? "OK" : "FALSE"); 6714 fprintf(log_fd, "\n"); 6715 #endif 6716 } 6717 6718 /* for \@! and \@<! it is a match when result is FALSE */ 6719 if (result != (pim->state->c == NFA_START_INVISIBLE_NEG 6720 || pim->state->c == NFA_START_INVISIBLE_NEG_FIRST 6721 || pim->state->c 6722 == NFA_START_INVISIBLE_BEFORE_NEG 6723 || pim->state->c 6724 == NFA_START_INVISIBLE_BEFORE_NEG_FIRST)) 6725 { 6726 /* Copy submatch info from the recursive call */ 6727 copy_sub_off(&t->subs.norm, &pim->subs.norm); 6728 #ifdef FEAT_SYN_HL 6729 if (rex.nfa_has_zsubexpr) 6730 copy_sub_off(&t->subs.synt, &pim->subs.synt); 6731 #endif 6732 } 6733 else 6734 /* look-behind match failed, don't add the state */ 6735 continue; 6736 6737 /* Postponed invisible match was handled, don't add it to 6738 * following states. */ 6739 pim = NULL; 6740 } 6741 6742 /* If "pim" points into l->t it will become invalid when 6743 * adding the state causes the list to be reallocated. Make a 6744 * local copy to avoid that. */ 6745 if (pim == &t->pim) 6746 { 6747 copy_pim(&pim_copy, pim); 6748 pim = &pim_copy; 6749 } 6750 6751 if (add_here) 6752 addstate_here(thislist, add_state, &t->subs, pim, &listidx); 6753 else 6754 { 6755 addstate(nextlist, add_state, &t->subs, pim, add_off); 6756 if (add_count > 0) 6757 nextlist->t[nextlist->n - 1].count = add_count; 6758 } 6759 } 6760 6761 } /* for (thislist = thislist; thislist->state; thislist++) */ 6762 6763 /* Look for the start of a match in the current position by adding the 6764 * start state to the list of states. 6765 * The first found match is the leftmost one, thus the order of states 6766 * matters! 6767 * Do not add the start state in recursive calls of nfa_regmatch(), 6768 * because recursive calls should only start in the first position. 6769 * Unless "nfa_endp" is not NULL, then we match the end position. 6770 * Also don't start a match past the first line. */ 6771 if (nfa_match == FALSE 6772 && ((toplevel 6773 && rex.lnum == 0 6774 && clen != 0 6775 && (rex.reg_maxcol == 0 6776 || (colnr_T)(rex.input - rex.line) < rex.reg_maxcol)) 6777 || (nfa_endp != NULL 6778 && (REG_MULTI 6779 ? (rex.lnum < nfa_endp->se_u.pos.lnum 6780 || (rex.lnum == nfa_endp->se_u.pos.lnum 6781 && (int)(rex.input - rex.line) 6782 < nfa_endp->se_u.pos.col)) 6783 : rex.input < nfa_endp->se_u.ptr)))) 6784 { 6785 #ifdef ENABLE_LOG 6786 fprintf(log_fd, "(---) STARTSTATE\n"); 6787 #endif 6788 /* Inline optimized code for addstate() if we know the state is 6789 * the first MOPEN. */ 6790 if (toplevel) 6791 { 6792 int add = TRUE; 6793 int c; 6794 6795 if (prog->regstart != NUL && clen != 0) 6796 { 6797 if (nextlist->n == 0) 6798 { 6799 colnr_T col = (colnr_T)(rex.input - rex.line) + clen; 6800 6801 /* Nextlist is empty, we can skip ahead to the 6802 * character that must appear at the start. */ 6803 if (skip_to_start(prog->regstart, &col) == FAIL) 6804 break; 6805 #ifdef ENABLE_LOG 6806 fprintf(log_fd, " Skipping ahead %d bytes to regstart\n", 6807 col - ((colnr_T)(rex.input - rex.line) + clen)); 6808 #endif 6809 rex.input = rex.line + col - clen; 6810 } 6811 else 6812 { 6813 /* Checking if the required start character matches is 6814 * cheaper than adding a state that won't match. */ 6815 c = PTR2CHAR(rex.input + clen); 6816 if (c != prog->regstart && (!rex.reg_ic 6817 || MB_TOLOWER(c) != MB_TOLOWER(prog->regstart))) 6818 { 6819 #ifdef ENABLE_LOG 6820 fprintf(log_fd, " Skipping start state, regstart does not match\n"); 6821 #endif 6822 add = FALSE; 6823 } 6824 } 6825 } 6826 6827 if (add) 6828 { 6829 if (REG_MULTI) 6830 m->norm.list.multi[0].start_col = 6831 (colnr_T)(rex.input - rex.line) + clen; 6832 else 6833 m->norm.list.line[0].start = rex.input + clen; 6834 addstate(nextlist, start->out, m, NULL, clen); 6835 } 6836 } 6837 else 6838 addstate(nextlist, start, m, NULL, clen); 6839 } 6840 6841 #ifdef ENABLE_LOG 6842 fprintf(log_fd, ">>> Thislist had %d states available: ", thislist->n); 6843 { 6844 int i; 6845 6846 for (i = 0; i < thislist->n; i++) 6847 fprintf(log_fd, "%d ", abs(thislist->t[i].state->id)); 6848 } 6849 fprintf(log_fd, "\n"); 6850 #endif 6851 6852 nextchar: 6853 /* Advance to the next character, or advance to the next line, or 6854 * finish. */ 6855 if (clen != 0) 6856 rex.input += clen; 6857 else if (go_to_nextline || (nfa_endp != NULL && REG_MULTI 6858 && rex.lnum < nfa_endp->se_u.pos.lnum)) 6859 reg_nextline(); 6860 else 6861 break; 6862 6863 /* Allow interrupting with CTRL-C. */ 6864 line_breakcheck(); 6865 if (got_int) 6866 break; 6867 #ifdef FEAT_RELTIME 6868 /* Check for timeout once in a twenty times to avoid overhead. */ 6869 if (nfa_time_limit != NULL && ++nfa_time_count == 20) 6870 { 6871 nfa_time_count = 0; 6872 if (nfa_did_time_out()) 6873 break; 6874 } 6875 #endif 6876 } 6877 6878 #ifdef ENABLE_LOG 6879 if (log_fd != stderr) 6880 fclose(log_fd); 6881 log_fd = NULL; 6882 #endif 6883 6884 theend: 6885 /* Free memory */ 6886 vim_free(list[0].t); 6887 vim_free(list[1].t); 6888 vim_free(listids); 6889 #undef ADD_STATE_IF_MATCH 6890 #ifdef NFA_REGEXP_DEBUG_LOG 6891 fclose(debug); 6892 #endif 6893 6894 return nfa_match; 6895 } 6896 6897 /* 6898 * Try match of "prog" with at rex.line["col"]. 6899 * Returns <= 0 for failure, number of lines contained in the match otherwise. 6900 */ 6901 static long 6902 nfa_regtry( 6903 nfa_regprog_T *prog, 6904 colnr_T col, 6905 proftime_T *tm UNUSED, /* timeout limit or NULL */ 6906 int *timed_out UNUSED) /* flag set on timeout or NULL */ 6907 { 6908 int i; 6909 regsubs_T subs, m; 6910 nfa_state_T *start = prog->start; 6911 int result; 6912 #ifdef ENABLE_LOG 6913 FILE *f; 6914 #endif 6915 6916 rex.input = rex.line + col; 6917 #ifdef FEAT_RELTIME 6918 nfa_time_limit = tm; 6919 nfa_timed_out = timed_out; 6920 nfa_time_count = 0; 6921 #endif 6922 6923 #ifdef ENABLE_LOG 6924 f = fopen(NFA_REGEXP_RUN_LOG, "a"); 6925 if (f != NULL) 6926 { 6927 fprintf(f, "\n\n\t=======================================================\n"); 6928 #ifdef DEBUG 6929 fprintf(f, "\tRegexp is \"%s\"\n", nfa_regengine.expr); 6930 #endif 6931 fprintf(f, "\tInput text is \"%s\" \n", rex.input); 6932 fprintf(f, "\t=======================================================\n\n"); 6933 nfa_print_state(f, start); 6934 fprintf(f, "\n\n"); 6935 fclose(f); 6936 } 6937 else 6938 emsg("Could not open temporary log file for writing"); 6939 #endif 6940 6941 clear_sub(&subs.norm); 6942 clear_sub(&m.norm); 6943 #ifdef FEAT_SYN_HL 6944 clear_sub(&subs.synt); 6945 clear_sub(&m.synt); 6946 #endif 6947 6948 result = nfa_regmatch(prog, start, &subs, &m); 6949 if (result == FALSE) 6950 return 0; 6951 else if (result == NFA_TOO_EXPENSIVE) 6952 return result; 6953 6954 cleanup_subexpr(); 6955 if (REG_MULTI) 6956 { 6957 for (i = 0; i < subs.norm.in_use; i++) 6958 { 6959 rex.reg_startpos[i].lnum = subs.norm.list.multi[i].start_lnum; 6960 rex.reg_startpos[i].col = subs.norm.list.multi[i].start_col; 6961 6962 rex.reg_endpos[i].lnum = subs.norm.list.multi[i].end_lnum; 6963 rex.reg_endpos[i].col = subs.norm.list.multi[i].end_col; 6964 } 6965 6966 if (rex.reg_startpos[0].lnum < 0) 6967 { 6968 rex.reg_startpos[0].lnum = 0; 6969 rex.reg_startpos[0].col = col; 6970 } 6971 if (rex.reg_endpos[0].lnum < 0) 6972 { 6973 /* pattern has a \ze but it didn't match, use current end */ 6974 rex.reg_endpos[0].lnum = rex.lnum; 6975 rex.reg_endpos[0].col = (int)(rex.input - rex.line); 6976 } 6977 else 6978 /* Use line number of "\ze". */ 6979 rex.lnum = rex.reg_endpos[0].lnum; 6980 } 6981 else 6982 { 6983 for (i = 0; i < subs.norm.in_use; i++) 6984 { 6985 rex.reg_startp[i] = subs.norm.list.line[i].start; 6986 rex.reg_endp[i] = subs.norm.list.line[i].end; 6987 } 6988 6989 if (rex.reg_startp[0] == NULL) 6990 rex.reg_startp[0] = rex.line + col; 6991 if (rex.reg_endp[0] == NULL) 6992 rex.reg_endp[0] = rex.input; 6993 } 6994 6995 #ifdef FEAT_SYN_HL 6996 /* Package any found \z(...\) matches for export. Default is none. */ 6997 unref_extmatch(re_extmatch_out); 6998 re_extmatch_out = NULL; 6999 7000 if (prog->reghasz == REX_SET) 7001 { 7002 cleanup_zsubexpr(); 7003 re_extmatch_out = make_extmatch(); 7004 /* Loop over \z1, \z2, etc. There is no \z0. */ 7005 for (i = 1; i < subs.synt.in_use; i++) 7006 { 7007 if (REG_MULTI) 7008 { 7009 struct multipos *mpos = &subs.synt.list.multi[i]; 7010 7011 /* Only accept single line matches that are valid. */ 7012 if (mpos->start_lnum >= 0 7013 && mpos->start_lnum == mpos->end_lnum 7014 && mpos->end_col >= mpos->start_col) 7015 re_extmatch_out->matches[i] = 7016 vim_strnsave(reg_getline(mpos->start_lnum) 7017 + mpos->start_col, 7018 mpos->end_col - mpos->start_col); 7019 } 7020 else 7021 { 7022 struct linepos *lpos = &subs.synt.list.line[i]; 7023 7024 if (lpos->start != NULL && lpos->end != NULL) 7025 re_extmatch_out->matches[i] = 7026 vim_strnsave(lpos->start, 7027 (int)(lpos->end - lpos->start)); 7028 } 7029 } 7030 } 7031 #endif 7032 7033 return 1 + rex.lnum; 7034 } 7035 7036 /* 7037 * Match a regexp against a string ("line" points to the string) or multiple 7038 * lines ("line" is NULL, use reg_getline()). 7039 * 7040 * Returns <= 0 for failure, number of lines contained in the match otherwise. 7041 */ 7042 static long 7043 nfa_regexec_both( 7044 char_u *line, 7045 colnr_T startcol, /* column to start looking for match */ 7046 proftime_T *tm, /* timeout limit or NULL */ 7047 int *timed_out) /* flag set on timeout or NULL */ 7048 { 7049 nfa_regprog_T *prog; 7050 long retval = 0L; 7051 int i; 7052 colnr_T col = startcol; 7053 7054 if (REG_MULTI) 7055 { 7056 prog = (nfa_regprog_T *)rex.reg_mmatch->regprog; 7057 line = reg_getline((linenr_T)0); /* relative to the cursor */ 7058 rex.reg_startpos = rex.reg_mmatch->startpos; 7059 rex.reg_endpos = rex.reg_mmatch->endpos; 7060 } 7061 else 7062 { 7063 prog = (nfa_regprog_T *)rex.reg_match->regprog; 7064 rex.reg_startp = rex.reg_match->startp; 7065 rex.reg_endp = rex.reg_match->endp; 7066 } 7067 7068 /* Be paranoid... */ 7069 if (prog == NULL || line == NULL) 7070 { 7071 emsg(_(e_null)); 7072 goto theend; 7073 } 7074 7075 /* If pattern contains "\c" or "\C": overrule value of rex.reg_ic */ 7076 if (prog->regflags & RF_ICASE) 7077 rex.reg_ic = TRUE; 7078 else if (prog->regflags & RF_NOICASE) 7079 rex.reg_ic = FALSE; 7080 7081 /* If pattern contains "\Z" overrule value of rex.reg_icombine */ 7082 if (prog->regflags & RF_ICOMBINE) 7083 rex.reg_icombine = TRUE; 7084 7085 rex.line = line; 7086 rex.lnum = 0; /* relative to line */ 7087 7088 rex.nfa_has_zend = prog->has_zend; 7089 rex.nfa_has_backref = prog->has_backref; 7090 rex.nfa_nsubexpr = prog->nsubexp; 7091 rex.nfa_listid = 1; 7092 rex.nfa_alt_listid = 2; 7093 #ifdef DEBUG 7094 nfa_regengine.expr = prog->pattern; 7095 #endif 7096 7097 if (prog->reganch && col > 0) 7098 return 0L; 7099 7100 rex.need_clear_subexpr = TRUE; 7101 #ifdef FEAT_SYN_HL 7102 /* Clear the external match subpointers if necessary. */ 7103 if (prog->reghasz == REX_SET) 7104 { 7105 rex.nfa_has_zsubexpr = TRUE; 7106 rex.need_clear_zsubexpr = TRUE; 7107 } 7108 else 7109 { 7110 rex.nfa_has_zsubexpr = FALSE; 7111 rex.need_clear_zsubexpr = FALSE; 7112 } 7113 #endif 7114 7115 if (prog->regstart != NUL) 7116 { 7117 /* Skip ahead until a character we know the match must start with. 7118 * When there is none there is no match. */ 7119 if (skip_to_start(prog->regstart, &col) == FAIL) 7120 return 0L; 7121 7122 /* If match_text is set it contains the full text that must match. 7123 * Nothing else to try. Doesn't handle combining chars well. */ 7124 if (prog->match_text != NULL && !rex.reg_icombine) 7125 return find_match_text(col, prog->regstart, prog->match_text); 7126 } 7127 7128 /* If the start column is past the maximum column: no need to try. */ 7129 if (rex.reg_maxcol > 0 && col >= rex.reg_maxcol) 7130 goto theend; 7131 7132 // Set the "nstate" used by nfa_regcomp() to zero to trigger an error when 7133 // it's accidentally used during execution. 7134 nstate = 0; 7135 for (i = 0; i < prog->nstate; ++i) 7136 { 7137 prog->state[i].id = i; 7138 prog->state[i].lastlist[0] = 0; 7139 prog->state[i].lastlist[1] = 0; 7140 } 7141 7142 retval = nfa_regtry(prog, col, tm, timed_out); 7143 7144 #ifdef DEBUG 7145 nfa_regengine.expr = NULL; 7146 #endif 7147 7148 theend: 7149 return retval; 7150 } 7151 7152 /* 7153 * Compile a regular expression into internal code for the NFA matcher. 7154 * Returns the program in allocated space. Returns NULL for an error. 7155 */ 7156 static regprog_T * 7157 nfa_regcomp(char_u *expr, int re_flags) 7158 { 7159 nfa_regprog_T *prog = NULL; 7160 size_t prog_size; 7161 int *postfix; 7162 7163 if (expr == NULL) 7164 return NULL; 7165 7166 #ifdef DEBUG 7167 nfa_regengine.expr = expr; 7168 #endif 7169 nfa_re_flags = re_flags; 7170 7171 init_class_tab(); 7172 7173 if (nfa_regcomp_start(expr, re_flags) == FAIL) 7174 return NULL; 7175 7176 /* Build postfix form of the regexp. Needed to build the NFA 7177 * (and count its size). */ 7178 postfix = re2post(); 7179 if (postfix == NULL) 7180 { 7181 /* TODO: only give this error for debugging? */ 7182 if (post_ptr >= post_end) 7183 siemsg("Internal error: estimated max number of states insufficient: %ld", post_end - post_start); 7184 goto fail; /* Cascaded (syntax?) error */ 7185 } 7186 7187 /* 7188 * In order to build the NFA, we parse the input regexp twice: 7189 * 1. first pass to count size (so we can allocate space) 7190 * 2. second to emit code 7191 */ 7192 #ifdef ENABLE_LOG 7193 { 7194 FILE *f = fopen(NFA_REGEXP_RUN_LOG, "a"); 7195 7196 if (f != NULL) 7197 { 7198 fprintf(f, "\n*****************************\n\n\n\n\tCompiling regexp \"%s\"... hold on !\n", expr); 7199 fclose(f); 7200 } 7201 } 7202 #endif 7203 7204 /* 7205 * PASS 1 7206 * Count number of NFA states in "nstate". Do not build the NFA. 7207 */ 7208 post2nfa(postfix, post_ptr, TRUE); 7209 7210 /* allocate the regprog with space for the compiled regexp */ 7211 prog_size = sizeof(nfa_regprog_T) + sizeof(nfa_state_T) * (nstate - 1); 7212 prog = (nfa_regprog_T *)lalloc(prog_size, TRUE); 7213 if (prog == NULL) 7214 goto fail; 7215 state_ptr = prog->state; 7216 prog->re_in_use = FALSE; 7217 7218 /* 7219 * PASS 2 7220 * Build the NFA 7221 */ 7222 prog->start = post2nfa(postfix, post_ptr, FALSE); 7223 if (prog->start == NULL) 7224 goto fail; 7225 7226 prog->regflags = regflags; 7227 prog->engine = &nfa_regengine; 7228 prog->nstate = nstate; 7229 prog->has_zend = rex.nfa_has_zend; 7230 prog->has_backref = rex.nfa_has_backref; 7231 prog->nsubexp = regnpar; 7232 7233 nfa_postprocess(prog); 7234 7235 prog->reganch = nfa_get_reganch(prog->start, 0); 7236 prog->regstart = nfa_get_regstart(prog->start, 0); 7237 prog->match_text = nfa_get_match_text(prog->start); 7238 7239 #ifdef ENABLE_LOG 7240 nfa_postfix_dump(expr, OK); 7241 nfa_dump(prog); 7242 #endif 7243 #ifdef FEAT_SYN_HL 7244 /* Remember whether this pattern has any \z specials in it. */ 7245 prog->reghasz = re_has_z; 7246 #endif 7247 prog->pattern = vim_strsave(expr); 7248 #ifdef DEBUG 7249 nfa_regengine.expr = NULL; 7250 #endif 7251 7252 out: 7253 VIM_CLEAR(post_start); 7254 post_ptr = post_end = NULL; 7255 state_ptr = NULL; 7256 return (regprog_T *)prog; 7257 7258 fail: 7259 VIM_CLEAR(prog); 7260 #ifdef ENABLE_LOG 7261 nfa_postfix_dump(expr, FAIL); 7262 #endif 7263 #ifdef DEBUG 7264 nfa_regengine.expr = NULL; 7265 #endif 7266 goto out; 7267 } 7268 7269 /* 7270 * Free a compiled regexp program, returned by nfa_regcomp(). 7271 */ 7272 static void 7273 nfa_regfree(regprog_T *prog) 7274 { 7275 if (prog != NULL) 7276 { 7277 vim_free(((nfa_regprog_T *)prog)->match_text); 7278 vim_free(((nfa_regprog_T *)prog)->pattern); 7279 vim_free(prog); 7280 } 7281 } 7282 7283 /* 7284 * Match a regexp against a string. 7285 * "rmp->regprog" is a compiled regexp as returned by nfa_regcomp(). 7286 * Uses curbuf for line count and 'iskeyword'. 7287 * If "line_lbr" is TRUE consider a "\n" in "line" to be a line break. 7288 * 7289 * Returns <= 0 for failure, number of lines contained in the match otherwise. 7290 */ 7291 static int 7292 nfa_regexec_nl( 7293 regmatch_T *rmp, 7294 char_u *line, /* string to match against */ 7295 colnr_T col, /* column to start looking for match */ 7296 int line_lbr) 7297 { 7298 rex.reg_match = rmp; 7299 rex.reg_mmatch = NULL; 7300 rex.reg_maxline = 0; 7301 rex.reg_line_lbr = line_lbr; 7302 rex.reg_buf = curbuf; 7303 rex.reg_win = NULL; 7304 rex.reg_ic = rmp->rm_ic; 7305 rex.reg_icombine = FALSE; 7306 rex.reg_maxcol = 0; 7307 return nfa_regexec_both(line, col, NULL, NULL); 7308 } 7309 7310 7311 /* 7312 * Match a regexp against multiple lines. 7313 * "rmp->regprog" is a compiled regexp as returned by vim_regcomp(). 7314 * Uses curbuf for line count and 'iskeyword'. 7315 * 7316 * Return <= 0 if there is no match. Return number of lines contained in the 7317 * match otherwise. 7318 * 7319 * Note: the body is the same as bt_regexec() except for nfa_regexec_both() 7320 * 7321 * ! Also NOTE : match may actually be in another line. e.g.: 7322 * when r.e. is \nc, cursor is at 'a' and the text buffer looks like 7323 * 7324 * +-------------------------+ 7325 * |a | 7326 * |b | 7327 * |c | 7328 * | | 7329 * +-------------------------+ 7330 * 7331 * then nfa_regexec_multi() returns 3. while the original 7332 * vim_regexec_multi() returns 0 and a second call at line 2 will return 2. 7333 * 7334 * FIXME if this behavior is not compatible. 7335 */ 7336 static long 7337 nfa_regexec_multi( 7338 regmmatch_T *rmp, 7339 win_T *win, /* window in which to search or NULL */ 7340 buf_T *buf, /* buffer in which to search */ 7341 linenr_T lnum, /* nr of line to start looking for match */ 7342 colnr_T col, /* column to start looking for match */ 7343 proftime_T *tm, /* timeout limit or NULL */ 7344 int *timed_out) /* flag set on timeout or NULL */ 7345 { 7346 rex.reg_match = NULL; 7347 rex.reg_mmatch = rmp; 7348 rex.reg_buf = buf; 7349 rex.reg_win = win; 7350 rex.reg_firstlnum = lnum; 7351 rex.reg_maxline = rex.reg_buf->b_ml.ml_line_count - lnum; 7352 rex.reg_line_lbr = FALSE; 7353 rex.reg_ic = rmp->rmm_ic; 7354 rex.reg_icombine = FALSE; 7355 rex.reg_maxcol = rmp->rmm_maxcol; 7356 7357 return nfa_regexec_both(NULL, col, tm, timed_out); 7358 } 7359 7360 #ifdef DEBUG 7361 # undef ENABLE_LOG 7362 #endif 7363