Mercurial > vim
annotate src/regexp_nfa.c @ 4539:532c2e850256 v7.3.1017
updated for version 7.3.1017
Problem: Zero width match changes length of match.
Solution: For a zero width match put new states in the current position in
the state list.
| author | Bram Moolenaar <bram@vim.org> |
|---|---|
| date | Sat, 25 May 2013 20:19:50 +0200 |
| parents | 5cc98a5898cf |
| children | 80170d61a85c |
| rev | line source |
|---|---|
| 4444 | 1 /* vi:set ts=8 sts=4 sw=4: |
| 2 * | |
| 3 * NFA regular expression implementation. | |
| 4 * | |
| 5 * This file is included in "regexp.c". | |
| 6 */ | |
| 7 | |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
8 /* |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
9 * Logging of NFA engine. |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
10 * |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
11 * The NFA engine can write four log files: |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
12 * - Error log: Contains NFA engine's fatal errors. |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
13 * - Dump log: Contains compiled NFA state machine's information. |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
14 * - Run log: Contains information of matching procedure. |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
15 * - Debug log: Contains detailed information of matching procedure. Can be |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
16 * disabled by undefining NFA_REGEXP_DEBUG_LOG. |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
17 * The first one can also be used without debug mode. |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
18 * The last three are enabled when compiled as debug mode and individually |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
19 * disabled by commenting them out. |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
20 * The log files can get quite big! |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
21 * Do disable all of this when compiling Vim for debugging, undefine DEBUG in |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
22 * regexp.c |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
23 */ |
| 4444 | 24 #ifdef DEBUG |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
25 # define NFA_REGEXP_ERROR_LOG "nfa_regexp_error.log" |
| 4444 | 26 # define ENABLE_LOG |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
27 # define NFA_REGEXP_DUMP_LOG "nfa_regexp_dump.log" |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
28 # define NFA_REGEXP_RUN_LOG "nfa_regexp_run.log" |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
29 # define NFA_REGEXP_DEBUG_LOG "nfa_regexp_debug.log" |
| 4444 | 30 #endif |
| 31 | |
| 32 /* Upper limit allowed for {m,n} repetitions handled by NFA */ | |
| 33 #define NFA_BRACES_MAXLIMIT 10 | |
| 34 /* For allocating space for the postfix representation */ | |
| 35 #define NFA_POSTFIX_MULTIPLIER (NFA_BRACES_MAXLIMIT + 2)*2 | |
| 36 | |
| 37 enum | |
| 38 { | |
| 39 NFA_SPLIT = -1024, | |
| 40 NFA_MATCH, | |
| 41 NFA_SKIP_CHAR, /* matches a 0-length char */ | |
| 42 NFA_END_NEG_RANGE, /* Used when expanding [^ab] */ | |
| 43 | |
| 44 NFA_CONCAT, | |
| 45 NFA_OR, | |
| 46 NFA_STAR, | |
| 47 NFA_PLUS, | |
| 48 NFA_QUEST, | |
| 49 NFA_QUEST_NONGREEDY, /* Non-greedy version of \? */ | |
| 50 NFA_NOT, /* used for [^ab] negated char ranges */ | |
| 51 | |
| 52 NFA_BOL, /* ^ Begin line */ | |
| 53 NFA_EOL, /* $ End line */ | |
| 54 NFA_BOW, /* \< Begin word */ | |
| 55 NFA_EOW, /* \> End word */ | |
| 56 NFA_BOF, /* \%^ Begin file */ | |
| 57 NFA_EOF, /* \%$ End file */ | |
| 58 NFA_NEWL, | |
| 59 NFA_ZSTART, /* Used for \zs */ | |
| 60 NFA_ZEND, /* Used for \ze */ | |
| 61 NFA_NOPEN, /* Start of subexpression marked with \%( */ | |
| 62 NFA_NCLOSE, /* End of subexpr. marked with \%( ... \) */ | |
| 63 NFA_START_INVISIBLE, | |
| 64 NFA_END_INVISIBLE, | |
| 65 NFA_COMPOSING, /* Next nodes in NFA are part of the | |
| 66 composing multibyte char */ | |
| 67 NFA_END_COMPOSING, /* End of a composing char in the NFA */ | |
| 68 | |
| 69 /* The following are used only in the postfix form, not in the NFA */ | |
| 70 NFA_PREV_ATOM_NO_WIDTH, /* Used for \@= */ | |
| 71 NFA_PREV_ATOM_NO_WIDTH_NEG, /* Used for \@! */ | |
| 72 NFA_PREV_ATOM_JUST_BEFORE, /* Used for \@<= */ | |
| 73 NFA_PREV_ATOM_JUST_BEFORE_NEG, /* Used for \@<! */ | |
| 74 NFA_PREV_ATOM_LIKE_PATTERN, /* Used for \@> */ | |
| 75 | |
| 76 NFA_MOPEN, | |
| 77 NFA_MCLOSE = NFA_MOPEN + NSUBEXP, | |
| 78 | |
| 79 /* NFA_FIRST_NL */ | |
| 80 NFA_ANY = NFA_MCLOSE + NSUBEXP, /* Match any one character. */ | |
| 81 NFA_ANYOF, /* Match any character in this string. */ | |
| 82 NFA_ANYBUT, /* Match any character not in this string. */ | |
| 83 NFA_IDENT, /* Match identifier char */ | |
| 84 NFA_SIDENT, /* Match identifier char but no digit */ | |
| 85 NFA_KWORD, /* Match keyword char */ | |
| 86 NFA_SKWORD, /* Match word char but no digit */ | |
| 87 NFA_FNAME, /* Match file name char */ | |
| 88 NFA_SFNAME, /* Match file name char but no digit */ | |
| 89 NFA_PRINT, /* Match printable char */ | |
| 90 NFA_SPRINT, /* Match printable char but no digit */ | |
| 91 NFA_WHITE, /* Match whitespace char */ | |
| 92 NFA_NWHITE, /* Match non-whitespace char */ | |
| 93 NFA_DIGIT, /* Match digit char */ | |
| 94 NFA_NDIGIT, /* Match non-digit char */ | |
| 95 NFA_HEX, /* Match hex char */ | |
| 96 NFA_NHEX, /* Match non-hex char */ | |
| 97 NFA_OCTAL, /* Match octal char */ | |
| 98 NFA_NOCTAL, /* Match non-octal char */ | |
| 99 NFA_WORD, /* Match word char */ | |
| 100 NFA_NWORD, /* Match non-word char */ | |
| 101 NFA_HEAD, /* Match head char */ | |
| 102 NFA_NHEAD, /* Match non-head char */ | |
| 103 NFA_ALPHA, /* Match alpha char */ | |
| 104 NFA_NALPHA, /* Match non-alpha char */ | |
| 105 NFA_LOWER, /* Match lowercase char */ | |
| 106 NFA_NLOWER, /* Match non-lowercase char */ | |
| 107 NFA_UPPER, /* Match uppercase char */ | |
| 108 NFA_NUPPER, /* Match non-uppercase char */ | |
| 109 NFA_FIRST_NL = NFA_ANY + ADD_NL, | |
| 110 NFA_LAST_NL = NFA_NUPPER + ADD_NL, | |
| 111 | |
| 112 /* Character classes [:alnum:] etc */ | |
| 113 NFA_CLASS_ALNUM, | |
| 114 NFA_CLASS_ALPHA, | |
| 115 NFA_CLASS_BLANK, | |
| 116 NFA_CLASS_CNTRL, | |
| 117 NFA_CLASS_DIGIT, | |
| 118 NFA_CLASS_GRAPH, | |
| 119 NFA_CLASS_LOWER, | |
| 120 NFA_CLASS_PRINT, | |
| 121 NFA_CLASS_PUNCT, | |
| 122 NFA_CLASS_SPACE, | |
| 123 NFA_CLASS_UPPER, | |
| 124 NFA_CLASS_XDIGIT, | |
| 125 NFA_CLASS_TAB, | |
| 126 NFA_CLASS_RETURN, | |
| 127 NFA_CLASS_BACKSPACE, | |
| 128 NFA_CLASS_ESCAPE | |
| 129 }; | |
| 130 | |
| 131 /* Keep in sync with classchars. */ | |
| 132 static int nfa_classcodes[] = { | |
| 133 NFA_ANY, NFA_IDENT, NFA_SIDENT, NFA_KWORD,NFA_SKWORD, | |
| 134 NFA_FNAME, NFA_SFNAME, NFA_PRINT, NFA_SPRINT, | |
| 135 NFA_WHITE, NFA_NWHITE, NFA_DIGIT, NFA_NDIGIT, | |
| 136 NFA_HEX, NFA_NHEX, NFA_OCTAL, NFA_NOCTAL, | |
| 137 NFA_WORD, NFA_NWORD, NFA_HEAD, NFA_NHEAD, | |
| 138 NFA_ALPHA, NFA_NALPHA, NFA_LOWER, NFA_NLOWER, | |
| 139 NFA_UPPER, NFA_NUPPER | |
| 140 }; | |
| 141 | |
| 142 static char_u e_misplaced[] = N_("E866: (NFA regexp) Misplaced %c"); | |
| 143 | |
| 144 /* | |
| 145 * NFA errors can be of 3 types: | |
| 146 * *** NFA runtime errors, when something unknown goes wrong. The NFA fails | |
| 147 * silently and revert the to backtracking engine. | |
| 148 * syntax_error = FALSE; | |
| 149 * *** Regexp syntax errors, when the input regexp is not syntactically correct. | |
| 150 * The NFA engine displays an error message, and nothing else happens. | |
| 151 * syntax_error = TRUE | |
| 152 * *** Unsupported features, when the input regexp uses an operator that is not | |
| 153 * implemented in the NFA. The NFA engine fails silently, and reverts to the | |
| 154 * old backtracking engine. | |
| 155 * syntax_error = FALSE | |
| 156 * "The NFA fails" means that "compiling the regexp with the NFA fails": | |
| 157 * nfa_regcomp() returns FAIL. | |
| 158 */ | |
| 159 static int syntax_error = FALSE; | |
| 160 | |
| 161 /* NFA regexp \ze operator encountered. */ | |
| 162 static int nfa_has_zend = FALSE; | |
| 163 | |
| 164 static int *post_start; /* holds the postfix form of r.e. */ | |
| 165 static int *post_end; | |
| 166 static int *post_ptr; | |
| 167 | |
| 168 static int nstate; /* Number of states in the NFA. */ | |
| 169 static int istate; /* Index in the state vector, used in new_state() */ | |
| 170 static int nstate_max; /* Upper bound of estimated number of states. */ | |
| 171 | |
| 172 | |
| 173 static int nfa_regcomp_start __ARGS((char_u*expr, int re_flags)); | |
| 174 static int nfa_recognize_char_class __ARGS((char_u *start, char_u *end, int extra_newl)); | |
| 175 static int nfa_emit_equi_class __ARGS((int c, int neg)); | |
| 176 static void nfa_inc __ARGS((char_u **p)); | |
| 177 static void nfa_dec __ARGS((char_u **p)); | |
| 178 static int nfa_regatom __ARGS((void)); | |
| 179 static int nfa_regpiece __ARGS((void)); | |
| 180 static int nfa_regconcat __ARGS((void)); | |
| 181 static int nfa_regbranch __ARGS((void)); | |
| 182 static int nfa_reg __ARGS((int paren)); | |
| 183 #ifdef DEBUG | |
| 184 static void nfa_set_code __ARGS((int c)); | |
| 185 static void nfa_postfix_dump __ARGS((char_u *expr, int retval)); | |
|
4533
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
186 static void nfa_print_state __ARGS((FILE *debugf, nfa_state_T *state)); |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
187 static void nfa_print_state2 __ARGS((FILE *debugf, nfa_state_T *state, garray_T *indent)); |
| 4444 | 188 static void nfa_dump __ARGS((nfa_regprog_T *prog)); |
| 189 #endif | |
| 190 static int *re2post __ARGS((void)); | |
| 191 static nfa_state_T *new_state __ARGS((int c, nfa_state_T *out, nfa_state_T *out1)); | |
| 192 static nfa_state_T *post2nfa __ARGS((int *postfix, int *end, int nfa_calc_size)); | |
| 193 static int check_char_class __ARGS((int class, int c)); | |
| 194 static void st_error __ARGS((int *postfix, int *end, int *p)); | |
| 195 static void nfa_save_listids __ARGS((nfa_state_T *start, int *list)); | |
| 196 static void nfa_restore_listids __ARGS((nfa_state_T *start, int *list)); | |
| 197 static void nfa_set_null_listids __ARGS((nfa_state_T *start)); | |
| 198 static void nfa_set_neg_listids __ARGS((nfa_state_T *start)); | |
| 199 static long nfa_regtry __ARGS((nfa_state_T *start, colnr_T col)); | |
| 200 static long nfa_regexec_both __ARGS((char_u *line, colnr_T col)); | |
| 201 static regprog_T *nfa_regcomp __ARGS((char_u *expr, int re_flags)); | |
| 202 static int nfa_regexec __ARGS((regmatch_T *rmp, char_u *line, colnr_T col)); | |
| 203 static long nfa_regexec_multi __ARGS((regmmatch_T *rmp, win_T *win, buf_T *buf, linenr_T lnum, colnr_T col, proftime_T *tm)); | |
| 204 | |
| 205 /* helper functions used when doing re2post() ... regatom() parsing */ | |
| 206 #define EMIT(c) do { \ | |
| 207 if (post_ptr >= post_end) \ | |
| 208 return FAIL; \ | |
| 209 *post_ptr++ = c; \ | |
| 210 } while (0) | |
| 211 | |
| 212 /* | |
| 213 * Initialize internal variables before NFA compilation. | |
| 214 * Return OK on success, FAIL otherwise. | |
| 215 */ | |
| 216 static int | |
| 217 nfa_regcomp_start(expr, re_flags) | |
| 218 char_u *expr; | |
| 219 int re_flags; /* see vim_regcomp() */ | |
| 220 { | |
| 4458 | 221 size_t postfix_size; |
| 4444 | 222 |
| 223 nstate = 0; | |
| 224 istate = 0; | |
| 225 /* A reasonable estimation for size */ | |
| 4458 | 226 nstate_max = (int)(STRLEN(expr) + 1) * NFA_POSTFIX_MULTIPLIER; |
| 4444 | 227 |
| 4454 | 228 /* Some items blow up in size, such as [A-z]. Add more space for that. |
| 229 * TODO: some patterns may still fail. */ | |
| 4458 | 230 nstate_max += 1000; |
| 4454 | 231 |
| 232 /* Size for postfix representation of expr. */ | |
| 4444 | 233 postfix_size = sizeof(*post_start) * nstate_max; |
| 4454 | 234 |
| 4444 | 235 post_start = (int *)lalloc(postfix_size, TRUE); |
| 236 if (post_start == NULL) | |
| 237 return FAIL; | |
| 238 vim_memset(post_start, 0, postfix_size); | |
| 239 post_ptr = post_start; | |
| 4454 | 240 post_end = post_start + nstate_max; |
| 4444 | 241 nfa_has_zend = FALSE; |
| 242 | |
| 243 regcomp_start(expr, re_flags); | |
| 244 | |
| 245 return OK; | |
| 246 } | |
| 247 | |
| 248 /* | |
| 249 * Search between "start" and "end" and try to recognize a | |
| 250 * character class in expanded form. For example [0-9]. | |
| 251 * On success, return the id the character class to be emitted. | |
| 252 * On failure, return 0 (=FAIL) | |
| 253 * Start points to the first char of the range, while end should point | |
| 254 * to the closing brace. | |
| 255 */ | |
| 256 static int | |
| 257 nfa_recognize_char_class(start, end, extra_newl) | |
| 258 char_u *start; | |
| 259 char_u *end; | |
| 260 int extra_newl; | |
| 261 { | |
| 262 int i; | |
| 263 /* Each of these variables takes up a char in "config[]", | |
| 264 * in the order they are here. */ | |
| 265 int not = FALSE, af = FALSE, AF = FALSE, az = FALSE, AZ = FALSE, | |
| 266 o7 = FALSE, o9 = FALSE, underscore = FALSE, newl = FALSE; | |
| 267 char_u *p; | |
| 268 #define NCONFIGS 16 | |
| 269 int classid[NCONFIGS] = { | |
| 270 NFA_DIGIT, NFA_NDIGIT, NFA_HEX, NFA_NHEX, | |
| 271 NFA_OCTAL, NFA_NOCTAL, NFA_WORD, NFA_NWORD, | |
| 272 NFA_HEAD, NFA_NHEAD, NFA_ALPHA, NFA_NALPHA, | |
| 273 NFA_LOWER, NFA_NLOWER, NFA_UPPER, NFA_NUPPER | |
| 274 }; | |
| 4450 | 275 char_u myconfig[10]; |
| 4444 | 276 char_u config[NCONFIGS][9] = { |
| 277 "000000100", /* digit */ | |
| 278 "100000100", /* non digit */ | |
| 279 "011000100", /* hex-digit */ | |
| 280 "111000100", /* non hex-digit */ | |
| 281 "000001000", /* octal-digit */ | |
| 282 "100001000", /* [^0-7] */ | |
| 283 "000110110", /* [0-9A-Za-z_] */ | |
| 284 "100110110", /* [^0-9A-Za-z_] */ | |
| 285 "000110010", /* head of word */ | |
| 286 "100110010", /* not head of word */ | |
| 287 "000110000", /* alphabetic char a-z */ | |
| 288 "100110000", /* non alphabetic char */ | |
| 289 "000100000", /* lowercase letter */ | |
| 290 "100100000", /* non lowercase */ | |
| 291 "000010000", /* uppercase */ | |
| 292 "100010000" /* non uppercase */ | |
| 293 }; | |
| 294 | |
| 295 if (extra_newl == TRUE) | |
| 296 newl = TRUE; | |
| 297 | |
| 298 if (*end != ']') | |
| 299 return FAIL; | |
| 300 p = start; | |
| 301 if (*p == '^') | |
| 302 { | |
| 303 not = TRUE; | |
| 304 p ++; | |
| 305 } | |
| 306 | |
| 307 while (p < end) | |
| 308 { | |
| 309 if (p + 2 < end && *(p + 1) == '-') | |
| 310 { | |
| 311 switch (*p) | |
| 312 { | |
| 313 case '0': | |
| 314 if (*(p + 2) == '9') | |
| 315 { | |
| 316 o9 = TRUE; | |
| 317 break; | |
| 318 } | |
| 319 else | |
| 320 if (*(p + 2) == '7') | |
| 321 { | |
| 322 o7 = TRUE; | |
| 323 break; | |
| 324 } | |
| 325 case 'a': | |
| 326 if (*(p + 2) == 'z') | |
| 327 { | |
| 328 az = TRUE; | |
| 329 break; | |
| 330 } | |
| 331 else | |
| 332 if (*(p + 2) == 'f') | |
| 333 { | |
| 334 af = TRUE; | |
| 335 break; | |
| 336 } | |
| 337 case 'A': | |
| 338 if (*(p + 2) == 'Z') | |
| 339 { | |
| 340 AZ = TRUE; | |
| 341 break; | |
| 342 } | |
| 343 else | |
| 344 if (*(p + 2) == 'F') | |
| 345 { | |
| 346 AF = TRUE; | |
| 347 break; | |
| 348 } | |
| 349 /* FALLTHROUGH */ | |
| 350 default: | |
| 351 return FAIL; | |
| 352 } | |
| 353 p += 3; | |
| 354 } | |
| 355 else if (p + 1 < end && *p == '\\' && *(p + 1) == 'n') | |
| 356 { | |
| 357 newl = TRUE; | |
| 358 p += 2; | |
| 359 } | |
| 360 else if (*p == '_') | |
| 361 { | |
| 362 underscore = TRUE; | |
| 363 p ++; | |
| 364 } | |
| 365 else if (*p == '\n') | |
| 366 { | |
| 367 newl = TRUE; | |
| 368 p ++; | |
| 369 } | |
| 370 else | |
| 371 return FAIL; | |
| 372 } /* while (p < end) */ | |
| 373 | |
| 374 if (p != end) | |
| 375 return FAIL; | |
| 376 | |
| 377 /* build the config that represents the ranges we gathered */ | |
| 378 STRCPY(myconfig, "000000000"); | |
| 379 if (not == TRUE) | |
| 380 myconfig[0] = '1'; | |
| 381 if (af == TRUE) | |
| 382 myconfig[1] = '1'; | |
| 383 if (AF == TRUE) | |
| 384 myconfig[2] = '1'; | |
| 385 if (az == TRUE) | |
| 386 myconfig[3] = '1'; | |
| 387 if (AZ == TRUE) | |
| 388 myconfig[4] = '1'; | |
| 389 if (o7 == TRUE) | |
| 390 myconfig[5] = '1'; | |
| 391 if (o9 == TRUE) | |
| 392 myconfig[6] = '1'; | |
| 393 if (underscore == TRUE) | |
| 394 myconfig[7] = '1'; | |
| 395 if (newl == TRUE) | |
| 396 { | |
| 397 myconfig[8] = '1'; | |
| 398 extra_newl = ADD_NL; | |
| 399 } | |
| 400 /* try to recognize character classes */ | |
| 401 for (i = 0; i < NCONFIGS; i++) | |
| 4450 | 402 if (STRNCMP(myconfig, config[i], 8) == 0) |
| 4444 | 403 return classid[i] + extra_newl; |
| 404 | |
| 405 /* fallthrough => no success so far */ | |
| 406 return FAIL; | |
| 407 | |
| 408 #undef NCONFIGS | |
| 409 } | |
| 410 | |
| 411 /* | |
| 412 * Produce the bytes for equivalence class "c". | |
| 413 * Currently only handles latin1, latin9 and utf-8. | |
| 414 * Emits bytes in postfix notation: 'a,b,NFA_OR,c,NFA_OR' is | |
| 415 * equivalent to 'a OR b OR c' | |
| 416 * | |
| 417 * NOTE! When changing this function, also update reg_equi_class() | |
| 418 */ | |
| 419 static int | |
| 420 nfa_emit_equi_class(c, neg) | |
| 421 int c; | |
| 422 int neg; | |
| 423 { | |
| 424 int first = TRUE; | |
| 425 int glue = neg == TRUE ? NFA_CONCAT : NFA_OR; | |
| 426 #define EMIT2(c) \ | |
| 427 EMIT(c); \ | |
| 428 if (neg == TRUE) { \ | |
| 429 EMIT(NFA_NOT); \ | |
| 430 } \ | |
| 431 if (first == FALSE) \ | |
| 432 EMIT(glue); \ | |
| 433 else \ | |
| 434 first = FALSE; \ | |
| 435 | |
| 436 #ifdef FEAT_MBYTE | |
| 437 if (enc_utf8 || STRCMP(p_enc, "latin1") == 0 | |
| 438 || STRCMP(p_enc, "iso-8859-15") == 0) | |
| 439 #endif | |
| 440 { | |
| 441 switch (c) | |
| 442 { | |
| 443 case 'A': case '\300': case '\301': case '\302': | |
| 444 case '\303': case '\304': case '\305': | |
| 445 EMIT2('A'); EMIT2('\300'); EMIT2('\301'); | |
| 446 EMIT2('\302'); EMIT2('\303'); EMIT2('\304'); | |
| 447 EMIT2('\305'); | |
| 448 return OK; | |
| 449 | |
| 450 case 'C': case '\307': | |
| 451 EMIT2('C'); EMIT2('\307'); | |
| 452 return OK; | |
| 453 | |
| 454 case 'E': case '\310': case '\311': case '\312': case '\313': | |
| 455 EMIT2('E'); EMIT2('\310'); EMIT2('\311'); | |
| 456 EMIT2('\312'); EMIT2('\313'); | |
| 457 return OK; | |
| 458 | |
| 459 case 'I': case '\314': case '\315': case '\316': case '\317': | |
| 460 EMIT2('I'); EMIT2('\314'); EMIT2('\315'); | |
| 461 EMIT2('\316'); EMIT2('\317'); | |
| 462 return OK; | |
| 463 | |
| 464 case 'N': case '\321': | |
| 465 EMIT2('N'); EMIT2('\321'); | |
| 466 return OK; | |
| 467 | |
| 468 case 'O': case '\322': case '\323': case '\324': case '\325': | |
| 469 case '\326': | |
| 470 EMIT2('O'); EMIT2('\322'); EMIT2('\323'); | |
| 471 EMIT2('\324'); EMIT2('\325'); EMIT2('\326'); | |
| 472 return OK; | |
| 473 | |
| 474 case 'U': case '\331': case '\332': case '\333': case '\334': | |
| 475 EMIT2('U'); EMIT2('\331'); EMIT2('\332'); | |
| 476 EMIT2('\333'); EMIT2('\334'); | |
| 477 return OK; | |
| 478 | |
| 479 case 'Y': case '\335': | |
| 480 EMIT2('Y'); EMIT2('\335'); | |
| 481 return OK; | |
| 482 | |
| 483 case 'a': case '\340': case '\341': case '\342': | |
| 484 case '\343': case '\344': case '\345': | |
| 485 EMIT2('a'); EMIT2('\340'); EMIT2('\341'); | |
| 486 EMIT2('\342'); EMIT2('\343'); EMIT2('\344'); | |
| 487 EMIT2('\345'); | |
| 488 return OK; | |
| 489 | |
| 490 case 'c': case '\347': | |
| 491 EMIT2('c'); EMIT2('\347'); | |
| 492 return OK; | |
| 493 | |
| 494 case 'e': case '\350': case '\351': case '\352': case '\353': | |
| 495 EMIT2('e'); EMIT2('\350'); EMIT2('\351'); | |
| 496 EMIT2('\352'); EMIT2('\353'); | |
| 497 return OK; | |
| 498 | |
| 499 case 'i': case '\354': case '\355': case '\356': case '\357': | |
| 500 EMIT2('i'); EMIT2('\354'); EMIT2('\355'); | |
| 501 EMIT2('\356'); EMIT2('\357'); | |
| 502 return OK; | |
| 503 | |
| 504 case 'n': case '\361': | |
| 505 EMIT2('n'); EMIT2('\361'); | |
| 506 return OK; | |
| 507 | |
| 508 case 'o': case '\362': case '\363': case '\364': case '\365': | |
| 509 case '\366': | |
| 510 EMIT2('o'); EMIT2('\362'); EMIT2('\363'); | |
| 511 EMIT2('\364'); EMIT2('\365'); EMIT2('\366'); | |
| 512 return OK; | |
| 513 | |
| 514 case 'u': case '\371': case '\372': case '\373': case '\374': | |
| 515 EMIT2('u'); EMIT2('\371'); EMIT2('\372'); | |
| 516 EMIT2('\373'); EMIT2('\374'); | |
| 517 return OK; | |
| 518 | |
| 519 case 'y': case '\375': case '\377': | |
| 520 EMIT2('y'); EMIT2('\375'); EMIT2('\377'); | |
| 521 return OK; | |
| 522 | |
| 523 default: | |
| 524 return FAIL; | |
| 525 } | |
| 526 } | |
| 527 | |
| 528 EMIT(c); | |
| 529 return OK; | |
| 530 #undef EMIT2 | |
| 531 } | |
| 532 | |
| 533 /* | |
| 534 * Code to parse regular expression. | |
| 535 * | |
| 536 * We try to reuse parsing functions in regexp.c to | |
| 537 * minimize surprise and keep the syntax consistent. | |
| 538 */ | |
| 539 | |
| 540 /* | |
| 541 * Increments the pointer "p" by one (multi-byte) character. | |
| 542 */ | |
| 543 static void | |
| 544 nfa_inc(p) | |
| 545 char_u **p; | |
| 546 { | |
| 547 #ifdef FEAT_MBYTE | |
| 548 if (has_mbyte) | |
| 549 mb_ptr2char_adv(p); | |
| 550 else | |
| 551 #endif | |
| 552 *p = *p + 1; | |
| 553 } | |
| 554 | |
| 555 /* | |
| 556 * Decrements the pointer "p" by one (multi-byte) character. | |
| 557 */ | |
| 558 static void | |
| 559 nfa_dec(p) | |
| 560 char_u **p; | |
| 561 { | |
| 562 #ifdef FEAT_MBYTE | |
| 563 char_u *p2, *oldp; | |
| 564 | |
| 565 if (has_mbyte) | |
| 566 { | |
| 567 oldp = *p; | |
| 568 /* Try to find the multibyte char that advances to the current | |
| 569 * position. */ | |
| 570 do | |
| 571 { | |
| 572 *p = *p - 1; | |
| 573 p2 = *p; | |
| 574 mb_ptr2char_adv(&p2); | |
| 575 } while (p2 != oldp); | |
| 576 } | |
| 577 #else | |
| 578 *p = *p - 1; | |
| 579 #endif | |
| 580 } | |
| 581 | |
| 582 /* | |
| 583 * Parse the lowest level. | |
| 584 * | |
| 585 * An atom can be one of a long list of items. Many atoms match one character | |
| 586 * in the text. It is often an ordinary character or a character class. | |
| 587 * Braces can be used to make a pattern into an atom. The "\z(\)" construct | |
| 588 * is only for syntax highlighting. | |
| 589 * | |
| 590 * atom ::= ordinary-atom | |
| 591 * or \( pattern \) | |
| 592 * or \%( pattern \) | |
| 593 * or \z( pattern \) | |
| 594 */ | |
| 595 static int | |
| 596 nfa_regatom() | |
| 597 { | |
| 598 int c; | |
| 599 int charclass; | |
| 600 int equiclass; | |
| 601 int collclass; | |
| 602 int got_coll_char; | |
| 603 char_u *p; | |
| 604 char_u *endp; | |
| 605 #ifdef FEAT_MBYTE | |
| 606 char_u *old_regparse = regparse; | |
| 607 int clen; | |
| 608 int i; | |
| 609 #endif | |
| 610 int extra = 0; | |
| 611 int first; | |
| 612 int emit_range; | |
| 613 int negated; | |
| 614 int result; | |
| 615 int startc = -1; | |
| 616 int endc = -1; | |
| 617 int oldstartc = -1; | |
| 618 int cpo_lit; /* 'cpoptions' contains 'l' flag */ | |
| 619 int cpo_bsl; /* 'cpoptions' contains '\' flag */ | |
| 620 int glue; /* ID that will "glue" nodes together */ | |
| 621 | |
| 622 cpo_lit = vim_strchr(p_cpo, CPO_LITERAL) != NULL; | |
| 623 cpo_bsl = vim_strchr(p_cpo, CPO_BACKSL) != NULL; | |
| 624 | |
| 625 c = getchr(); | |
| 626 | |
| 627 #ifdef FEAT_MBYTE | |
| 628 /* clen has the length of the current char, without composing chars */ | |
| 629 clen = (*mb_char2len)(c); | |
| 630 if (has_mbyte && clen > 1) | |
| 631 goto nfa_do_multibyte; | |
| 632 #endif | |
| 633 switch (c) | |
| 634 { | |
| 635 case Magic('^'): | |
| 636 EMIT(NFA_BOL); | |
| 637 break; | |
| 638 | |
| 639 case Magic('$'): | |
| 640 EMIT(NFA_EOL); | |
| 641 #if defined(FEAT_SYN_HL) || defined(PROTO) | |
| 642 had_eol = TRUE; | |
| 643 #endif | |
| 644 break; | |
| 645 | |
| 646 case Magic('<'): | |
| 647 EMIT(NFA_BOW); | |
| 648 break; | |
| 649 | |
| 650 case Magic('>'): | |
| 651 EMIT(NFA_EOW); | |
| 652 break; | |
| 653 | |
| 654 case Magic('_'): | |
| 655 c = no_Magic(getchr()); | |
| 656 if (c == '^') /* "\_^" is start-of-line */ | |
| 657 { | |
| 658 EMIT(NFA_BOL); | |
| 659 break; | |
| 660 } | |
| 661 if (c == '$') /* "\_$" is end-of-line */ | |
| 662 { | |
| 663 EMIT(NFA_EOL); | |
| 664 #if defined(FEAT_SYN_HL) || defined(PROTO) | |
| 665 had_eol = TRUE; | |
| 666 #endif | |
| 667 break; | |
| 668 } | |
| 669 | |
| 670 extra = ADD_NL; | |
| 671 | |
| 672 /* "\_[" is collection plus newline */ | |
| 673 if (c == '[') | |
|
4517
9a2183bd8295
updated for version 7.3.1006
Bram Moolenaar <bram@vim.org>
parents:
4515
diff
changeset
|
674 goto collection; |
| 4444 | 675 |
| 676 /* "\_x" is character class plus newline */ | |
| 677 /*FALLTHROUGH*/ | |
| 678 | |
| 679 /* | |
| 680 * Character classes. | |
| 681 */ | |
| 682 case Magic('.'): | |
| 683 case Magic('i'): | |
| 684 case Magic('I'): | |
| 685 case Magic('k'): | |
| 686 case Magic('K'): | |
| 687 case Magic('f'): | |
| 688 case Magic('F'): | |
| 689 case Magic('p'): | |
| 690 case Magic('P'): | |
| 691 case Magic('s'): | |
| 692 case Magic('S'): | |
| 693 case Magic('d'): | |
| 694 case Magic('D'): | |
| 695 case Magic('x'): | |
| 696 case Magic('X'): | |
| 697 case Magic('o'): | |
| 698 case Magic('O'): | |
| 699 case Magic('w'): | |
| 700 case Magic('W'): | |
| 701 case Magic('h'): | |
| 702 case Magic('H'): | |
| 703 case Magic('a'): | |
| 704 case Magic('A'): | |
| 705 case Magic('l'): | |
| 706 case Magic('L'): | |
| 707 case Magic('u'): | |
| 708 case Magic('U'): | |
| 709 p = vim_strchr(classchars, no_Magic(c)); | |
| 710 if (p == NULL) | |
| 711 { | |
| 712 return FAIL; /* runtime error */ | |
| 713 } | |
| 714 #ifdef FEAT_MBYTE | |
| 715 /* When '.' is followed by a composing char ignore the dot, so that | |
| 716 * the composing char is matched here. */ | |
| 717 if (enc_utf8 && c == Magic('.') && utf_iscomposing(peekchr())) | |
| 718 { | |
|
4535
45f97c349537
updated for version 7.3.1015
Bram Moolenaar <bram@vim.org>
parents:
4533
diff
changeset
|
719 old_regparse = regparse; |
| 4444 | 720 c = getchr(); |
| 721 goto nfa_do_multibyte; | |
| 722 } | |
| 723 #endif | |
| 724 EMIT(nfa_classcodes[p - classchars]); | |
| 725 if (extra == ADD_NL) | |
| 726 { | |
| 727 EMIT(NFA_NEWL); | |
| 728 EMIT(NFA_OR); | |
| 729 regflags |= RF_HASNL; | |
| 730 } | |
| 731 break; | |
| 732 | |
| 733 case Magic('n'): | |
| 734 if (reg_string) | |
| 735 /* In a string "\n" matches a newline character. */ | |
| 736 EMIT(NL); | |
| 737 else | |
| 738 { | |
| 739 /* In buffer text "\n" matches the end of a line. */ | |
| 740 EMIT(NFA_NEWL); | |
| 741 regflags |= RF_HASNL; | |
| 742 } | |
| 743 break; | |
| 744 | |
| 745 case Magic('('): | |
| 746 if (nfa_reg(REG_PAREN) == FAIL) | |
| 747 return FAIL; /* cascaded error */ | |
| 748 break; | |
| 749 | |
| 750 case NUL: | |
| 751 syntax_error = TRUE; | |
| 752 EMSG_RET_FAIL(_("E865: (NFA) Regexp end encountered prematurely")); | |
| 753 | |
| 754 case Magic('|'): | |
| 755 case Magic('&'): | |
| 756 case Magic(')'): | |
| 757 syntax_error = TRUE; | |
| 4450 | 758 EMSGN(_(e_misplaced), no_Magic(c)); |
| 4444 | 759 return FAIL; |
| 760 | |
| 761 case Magic('='): | |
| 762 case Magic('?'): | |
| 763 case Magic('+'): | |
| 764 case Magic('@'): | |
| 765 case Magic('*'): | |
| 766 case Magic('{'): | |
| 767 /* these should follow an atom, not form an atom */ | |
| 768 syntax_error = TRUE; | |
| 4450 | 769 EMSGN(_(e_misplaced), no_Magic(c)); |
| 4444 | 770 return FAIL; |
| 771 | |
| 772 case Magic('~'): /* previous substitute pattern */ | |
| 773 /* Not supported yet */ | |
| 774 return FAIL; | |
| 775 | |
| 776 case Magic('1'): | |
| 777 case Magic('2'): | |
| 778 case Magic('3'): | |
| 779 case Magic('4'): | |
| 780 case Magic('5'): | |
| 781 case Magic('6'): | |
| 782 case Magic('7'): | |
| 783 case Magic('8'): | |
| 784 case Magic('9'): | |
| 785 /* not supported yet */ | |
| 786 return FAIL; | |
| 787 | |
| 788 case Magic('z'): | |
| 789 c = no_Magic(getchr()); | |
| 790 switch (c) | |
| 791 { | |
| 792 case 's': | |
| 793 EMIT(NFA_ZSTART); | |
| 794 break; | |
| 795 case 'e': | |
| 796 EMIT(NFA_ZEND); | |
| 797 nfa_has_zend = TRUE; | |
| 798 /* TODO: Currently \ze does not work properly. */ | |
| 799 return FAIL; | |
| 800 /* break; */ | |
| 801 case '1': | |
| 802 case '2': | |
| 803 case '3': | |
| 804 case '4': | |
| 805 case '5': | |
| 806 case '6': | |
| 807 case '7': | |
| 808 case '8': | |
| 809 case '9': | |
| 810 case '(': | |
| 811 /* \z1...\z9 and \z( not yet supported */ | |
| 812 return FAIL; | |
| 813 default: | |
| 814 syntax_error = TRUE; | |
| 4450 | 815 EMSGN(_("E867: (NFA) Unknown operator '\\z%c'"), |
| 4444 | 816 no_Magic(c)); |
| 817 return FAIL; | |
| 818 } | |
| 819 break; | |
| 820 | |
| 821 case Magic('%'): | |
| 822 c = no_Magic(getchr()); | |
| 823 switch (c) | |
| 824 { | |
| 825 /* () without a back reference */ | |
| 826 case '(': | |
| 827 if (nfa_reg(REG_NPAREN) == FAIL) | |
| 828 return FAIL; | |
| 829 EMIT(NFA_NOPEN); | |
| 830 break; | |
| 831 | |
| 832 case 'd': /* %d123 decimal */ | |
| 833 case 'o': /* %o123 octal */ | |
| 834 case 'x': /* %xab hex 2 */ | |
| 835 case 'u': /* %uabcd hex 4 */ | |
| 836 case 'U': /* %U1234abcd hex 8 */ | |
| 837 /* Not yet supported */ | |
| 838 return FAIL; | |
| 839 | |
| 840 c = coll_get_char(); | |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
841 EMIT(c); |
| 4444 | 842 break; |
| 843 | |
| 844 /* Catch \%^ and \%$ regardless of where they appear in the | |
| 845 * pattern -- regardless of whether or not it makes sense. */ | |
| 846 case '^': | |
| 847 EMIT(NFA_BOF); | |
| 848 /* Not yet supported */ | |
| 849 return FAIL; | |
| 850 break; | |
| 851 | |
| 852 case '$': | |
| 853 EMIT(NFA_EOF); | |
| 854 /* Not yet supported */ | |
| 855 return FAIL; | |
| 856 break; | |
| 857 | |
| 858 case '#': | |
| 859 /* not supported yet */ | |
| 860 return FAIL; | |
| 861 break; | |
| 862 | |
| 863 case 'V': | |
| 864 /* not supported yet */ | |
| 865 return FAIL; | |
| 866 break; | |
| 867 | |
| 868 case '[': | |
| 869 /* \%[abc] not supported yet */ | |
| 870 return FAIL; | |
| 871 | |
| 872 default: | |
| 873 /* not supported yet */ | |
| 874 return FAIL; | |
| 875 } | |
| 876 break; | |
| 877 | |
| 878 case Magic('['): | |
|
4517
9a2183bd8295
updated for version 7.3.1006
Bram Moolenaar <bram@vim.org>
parents:
4515
diff
changeset
|
879 collection: |
| 4444 | 880 /* |
| 881 * Glue is emitted between several atoms from the []. | |
| 882 * It is either NFA_OR, or NFA_CONCAT. | |
| 883 * | |
| 884 * [abc] expands to 'a b NFA_OR c NFA_OR' (in postfix notation) | |
| 885 * [^abc] expands to 'a NFA_NOT b NFA_NOT NFA_CONCAT c NFA_NOT | |
| 886 * NFA_CONCAT NFA_END_NEG_RANGE NFA_CONCAT' (in postfix | |
| 887 * notation) | |
| 888 * | |
| 889 */ | |
| 890 | |
| 891 | |
| 892 /* Emit negation atoms, if needed. | |
| 893 * The CONCAT below merges the NOT with the previous node. */ | |
| 894 #define TRY_NEG() \ | |
| 895 if (negated == TRUE) \ | |
| 896 { \ | |
| 897 EMIT(NFA_NOT); \ | |
| 898 } | |
| 899 | |
| 900 /* Emit glue between important nodes : CONCAT or OR. */ | |
| 901 #define EMIT_GLUE() \ | |
| 902 if (first == FALSE) \ | |
| 903 EMIT(glue); \ | |
| 904 else \ | |
| 905 first = FALSE; | |
| 906 | |
| 907 p = regparse; | |
| 908 endp = skip_anyof(p); | |
| 909 if (*endp == ']') | |
| 910 { | |
| 911 /* | |
| 912 * Try to reverse engineer character classes. For example, | |
| 913 * recognize that [0-9] stands for \d and [A-Za-z_] with \h, | |
| 914 * and perform the necessary substitutions in the NFA. | |
| 915 */ | |
| 916 result = nfa_recognize_char_class(regparse, endp, | |
| 917 extra == ADD_NL); | |
| 918 if (result != FAIL) | |
| 919 { | |
| 920 if (result >= NFA_DIGIT && result <= NFA_NUPPER) | |
| 921 EMIT(result); | |
| 922 else /* must be char class + newline */ | |
| 923 { | |
| 924 EMIT(result - ADD_NL); | |
| 925 EMIT(NFA_NEWL); | |
| 926 EMIT(NFA_OR); | |
| 927 } | |
| 928 regparse = endp; | |
| 929 nfa_inc(®parse); | |
| 930 return OK; | |
| 931 } | |
| 932 /* | |
| 933 * Failed to recognize a character class. Use the simple | |
| 934 * version that turns [abc] into 'a' OR 'b' OR 'c' | |
| 935 */ | |
| 936 startc = endc = oldstartc = -1; | |
| 937 first = TRUE; /* Emitting first atom in this sequence? */ | |
| 938 negated = FALSE; | |
| 939 glue = NFA_OR; | |
| 940 if (*regparse == '^') /* negated range */ | |
| 941 { | |
| 942 negated = TRUE; | |
| 943 glue = NFA_CONCAT; | |
| 944 nfa_inc(®parse); | |
| 945 } | |
| 946 if (*regparse == '-') | |
| 947 { | |
| 948 startc = '-'; | |
| 949 EMIT(startc); | |
| 950 TRY_NEG(); | |
| 951 EMIT_GLUE(); | |
| 952 nfa_inc(®parse); | |
| 953 } | |
| 954 /* Emit the OR branches for each character in the [] */ | |
| 955 emit_range = FALSE; | |
| 956 while (regparse < endp) | |
| 957 { | |
| 958 oldstartc = startc; | |
| 959 startc = -1; | |
| 960 got_coll_char = FALSE; | |
| 961 if (*regparse == '[') | |
| 962 { | |
| 963 /* Check for [: :], [= =], [. .] */ | |
| 964 equiclass = collclass = 0; | |
| 965 charclass = get_char_class(®parse); | |
| 966 if (charclass == CLASS_NONE) | |
| 967 { | |
| 968 equiclass = get_equi_class(®parse); | |
| 969 if (equiclass == 0) | |
| 970 collclass = get_coll_element(®parse); | |
| 971 } | |
| 972 | |
| 973 /* Character class like [:alpha:] */ | |
| 974 if (charclass != CLASS_NONE) | |
| 975 { | |
| 976 switch (charclass) | |
| 977 { | |
| 978 case CLASS_ALNUM: | |
| 979 EMIT(NFA_CLASS_ALNUM); | |
| 980 break; | |
| 981 case CLASS_ALPHA: | |
| 982 EMIT(NFA_CLASS_ALPHA); | |
| 983 break; | |
| 984 case CLASS_BLANK: | |
| 985 EMIT(NFA_CLASS_BLANK); | |
| 986 break; | |
| 987 case CLASS_CNTRL: | |
| 988 EMIT(NFA_CLASS_CNTRL); | |
| 989 break; | |
| 990 case CLASS_DIGIT: | |
| 991 EMIT(NFA_CLASS_DIGIT); | |
| 992 break; | |
| 993 case CLASS_GRAPH: | |
| 994 EMIT(NFA_CLASS_GRAPH); | |
| 995 break; | |
| 996 case CLASS_LOWER: | |
| 997 EMIT(NFA_CLASS_LOWER); | |
| 998 break; | |
| 999 case CLASS_PRINT: | |
| 1000 EMIT(NFA_CLASS_PRINT); | |
| 1001 break; | |
| 1002 case CLASS_PUNCT: | |
| 1003 EMIT(NFA_CLASS_PUNCT); | |
| 1004 break; | |
| 1005 case CLASS_SPACE: | |
| 1006 EMIT(NFA_CLASS_SPACE); | |
| 1007 break; | |
| 1008 case CLASS_UPPER: | |
| 1009 EMIT(NFA_CLASS_UPPER); | |
| 1010 break; | |
| 1011 case CLASS_XDIGIT: | |
| 1012 EMIT(NFA_CLASS_XDIGIT); | |
| 1013 break; | |
| 1014 case CLASS_TAB: | |
| 1015 EMIT(NFA_CLASS_TAB); | |
| 1016 break; | |
| 1017 case CLASS_RETURN: | |
| 1018 EMIT(NFA_CLASS_RETURN); | |
| 1019 break; | |
| 1020 case CLASS_BACKSPACE: | |
| 1021 EMIT(NFA_CLASS_BACKSPACE); | |
| 1022 break; | |
| 1023 case CLASS_ESCAPE: | |
| 1024 EMIT(NFA_CLASS_ESCAPE); | |
| 1025 break; | |
| 1026 } | |
| 1027 TRY_NEG(); | |
| 1028 EMIT_GLUE(); | |
| 1029 continue; | |
| 1030 } | |
| 1031 /* Try equivalence class [=a=] and the like */ | |
| 1032 if (equiclass != 0) | |
| 1033 { | |
| 1034 result = nfa_emit_equi_class(equiclass, negated); | |
| 1035 if (result == FAIL) | |
| 1036 { | |
| 1037 /* should never happen */ | |
| 1038 EMSG_RET_FAIL(_("E868: Error building NFA with equivalence class!")); | |
| 1039 } | |
| 1040 EMIT_GLUE(); | |
| 1041 continue; | |
| 1042 } | |
| 1043 /* Try collating class like [. .] */ | |
| 1044 if (collclass != 0) | |
| 1045 { | |
| 1046 startc = collclass; /* allow [.a.]-x as a range */ | |
| 1047 /* Will emit the proper atom at the end of the | |
| 1048 * while loop. */ | |
| 1049 } | |
| 1050 } | |
| 1051 /* Try a range like 'a-x' or '\t-z' */ | |
| 1052 if (*regparse == '-') | |
| 1053 { | |
| 1054 emit_range = TRUE; | |
| 1055 startc = oldstartc; | |
| 1056 nfa_inc(®parse); | |
| 1057 continue; /* reading the end of the range */ | |
| 1058 } | |
| 1059 | |
| 1060 /* Now handle simple and escaped characters. | |
| 1061 * Only "\]", "\^", "\]" and "\\" are special in Vi. Vim | |
| 1062 * accepts "\t", "\e", etc., but only when the 'l' flag in | |
| 1063 * 'cpoptions' is not included. | |
| 1064 * Posix doesn't recognize backslash at all. | |
| 1065 */ | |
| 1066 if (*regparse == '\\' | |
| 1067 && !cpo_bsl | |
| 1068 && regparse + 1 <= endp | |
| 1069 && (vim_strchr(REGEXP_INRANGE, regparse[1]) != NULL | |
| 1070 || (!cpo_lit | |
| 1071 && vim_strchr(REGEXP_ABBR, regparse[1]) | |
| 1072 != NULL) | |
| 1073 ) | |
| 1074 ) | |
| 1075 { | |
| 1076 nfa_inc(®parse); | |
| 1077 | |
|
4507
9dbbddb2ed10
updated for version 7.3.1001
Bram Moolenaar <bram@vim.org>
parents:
4503
diff
changeset
|
1078 if (*regparse == 'n') |
| 4444 | 1079 startc = reg_string ? NL : NFA_NEWL; |
| 1080 else | |
| 1081 if (*regparse == 'd' | |
| 1082 || *regparse == 'o' | |
| 1083 || *regparse == 'x' | |
| 1084 || *regparse == 'u' | |
| 1085 || *regparse == 'U' | |
| 1086 ) | |
| 1087 { | |
| 1088 /* TODO(RE) This needs more testing */ | |
| 1089 startc = coll_get_char(); | |
| 1090 got_coll_char = TRUE; | |
| 1091 nfa_dec(®parse); | |
| 1092 } | |
| 1093 else | |
| 1094 { | |
| 1095 /* \r,\t,\e,\b */ | |
| 1096 startc = backslash_trans(*regparse); | |
| 1097 } | |
| 1098 } | |
| 1099 | |
| 1100 /* Normal printable char */ | |
| 1101 if (startc == -1) | |
| 1102 #ifdef FEAT_MBYTE | |
| 1103 startc = (*mb_ptr2char)(regparse); | |
| 1104 #else | |
| 1105 startc = *regparse; | |
| 1106 #endif | |
| 1107 | |
| 1108 /* Previous char was '-', so this char is end of range. */ | |
| 1109 if (emit_range) | |
| 1110 { | |
| 1111 endc = startc; startc = oldstartc; | |
| 1112 if (startc > endc) | |
| 1113 EMSG_RET_FAIL(_(e_invrange)); | |
| 1114 #ifdef FEAT_MBYTE | |
| 1115 if (has_mbyte && ((*mb_char2len)(startc) > 1 | |
| 1116 || (*mb_char2len)(endc) > 1)) | |
| 1117 { | |
| 1118 if (endc > startc + 256) | |
| 1119 EMSG_RET_FAIL(_(e_invrange)); | |
| 1120 /* Emit the range. "startc" was already emitted, so | |
| 1121 * skip it. */ | |
| 1122 for (c = startc + 1; c <= endc; c++) | |
| 1123 { | |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
1124 EMIT(c); |
| 4444 | 1125 TRY_NEG(); |
| 1126 EMIT_GLUE(); | |
| 1127 } | |
| 1128 emit_range = FALSE; | |
| 1129 } | |
| 1130 else | |
| 1131 #endif | |
| 1132 { | |
| 1133 #ifdef EBCDIC | |
| 1134 int alpha_only = FALSE; | |
| 1135 | |
| 1136 /* for alphabetical range skip the gaps | |
| 1137 * 'i'-'j', 'r'-'s', 'I'-'J' and 'R'-'S'. */ | |
| 1138 if (isalpha(startc) && isalpha(endc)) | |
| 1139 alpha_only = TRUE; | |
| 1140 #endif | |
| 1141 /* Emit the range. "startc" was already emitted, so | |
| 1142 * skip it. */ | |
| 1143 for (c = startc + 1; c <= endc; c++) | |
| 1144 #ifdef EBCDIC | |
| 1145 if (!alpha_only || isalpha(startc)) | |
| 1146 #endif | |
| 1147 { | |
| 1148 EMIT(c); | |
| 1149 TRY_NEG(); | |
| 1150 EMIT_GLUE(); | |
| 1151 } | |
| 1152 emit_range = FALSE; | |
| 1153 } | |
| 1154 } | |
| 1155 else | |
| 1156 { | |
| 1157 /* | |
| 1158 * This char (startc) is not part of a range. Just | |
| 1159 * emit it. | |
| 1160 * | |
| 1161 * Normally, simply emit startc. But if we get char | |
| 1162 * code=0 from a collating char, then replace it with | |
| 1163 * 0x0a. | |
| 1164 * | |
| 1165 * This is needed to completely mimic the behaviour of | |
| 1166 * the backtracking engine. | |
| 1167 */ | |
| 1168 if (got_coll_char == TRUE && startc == 0) | |
| 1169 EMIT(0x0a); | |
| 1170 else | |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
1171 EMIT(startc); |
| 4444 | 1172 TRY_NEG(); |
| 1173 EMIT_GLUE(); | |
| 1174 } | |
| 1175 | |
| 1176 nfa_inc(®parse); | |
| 1177 } /* while (p < endp) */ | |
| 1178 | |
| 1179 nfa_dec(®parse); | |
| 1180 if (*regparse == '-') /* if last, '-' is just a char */ | |
| 1181 { | |
| 1182 EMIT('-'); | |
| 1183 TRY_NEG(); | |
| 1184 EMIT_GLUE(); | |
| 1185 } | |
| 1186 nfa_inc(®parse); | |
| 1187 | |
| 1188 if (extra == ADD_NL) /* \_[] also matches \n */ | |
| 1189 { | |
| 1190 EMIT(reg_string ? NL : NFA_NEWL); | |
| 1191 TRY_NEG(); | |
| 1192 EMIT_GLUE(); | |
| 1193 } | |
| 1194 | |
| 1195 /* skip the trailing ] */ | |
| 1196 regparse = endp; | |
| 1197 nfa_inc(®parse); | |
| 1198 if (negated == TRUE) | |
| 1199 { | |
| 1200 /* Mark end of negated char range */ | |
| 1201 EMIT(NFA_END_NEG_RANGE); | |
| 1202 EMIT(NFA_CONCAT); | |
| 1203 } | |
| 1204 return OK; | |
|
4529
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
1205 } /* if exists closing ] */ |
|
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
1206 |
|
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
1207 if (reg_strict) |
| 4444 | 1208 { |
| 1209 syntax_error = TRUE; | |
| 1210 EMSG_RET_FAIL(_(e_missingbracket)); | |
| 1211 } | |
|
4529
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
1212 /* FALLTHROUGH */ |
|
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
1213 |
| 4444 | 1214 default: |
| 1215 { | |
| 1216 #ifdef FEAT_MBYTE | |
| 1217 int plen; | |
| 1218 | |
| 1219 nfa_do_multibyte: | |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
1220 /* Length of current char with composing chars. */ |
|
4535
45f97c349537
updated for version 7.3.1015
Bram Moolenaar <bram@vim.org>
parents:
4533
diff
changeset
|
1221 if (enc_utf8 && (clen != (plen = (*mb_ptr2len)(old_regparse)) |
|
45f97c349537
updated for version 7.3.1015
Bram Moolenaar <bram@vim.org>
parents:
4533
diff
changeset
|
1222 || utf_iscomposing(c))) |
| 4444 | 1223 { |
|
4535
45f97c349537
updated for version 7.3.1015
Bram Moolenaar <bram@vim.org>
parents:
4533
diff
changeset
|
1224 /* A base character plus composing characters, or just one |
|
45f97c349537
updated for version 7.3.1015
Bram Moolenaar <bram@vim.org>
parents:
4533
diff
changeset
|
1225 * or more composing characters. |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
1226 * This requires creating a separate atom as if enclosing |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
1227 * the characters in (), where NFA_COMPOSING is the ( and |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
1228 * NFA_END_COMPOSING is the ). Note that right now we are |
| 4444 | 1229 * building the postfix form, not the NFA itself; |
| 1230 * a composing char could be: a, b, c, NFA_COMPOSING | |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
1231 * where 'b' and 'c' are chars with codes > 256. */ |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
1232 i = 0; |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
1233 for (;;) |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
1234 { |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
1235 EMIT(c); |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
1236 if (i > 0) |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
1237 EMIT(NFA_CONCAT); |
|
4529
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
1238 if ((i += utf_char2len(c)) >= plen) |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
1239 break; |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
1240 c = utf_ptr2char(old_regparse + i); |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
1241 } |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
1242 EMIT(NFA_COMPOSING); |
| 4444 | 1243 regparse = old_regparse + plen; |
| 1244 } | |
| 1245 else | |
| 1246 #endif | |
| 1247 { | |
| 1248 c = no_Magic(c); | |
| 1249 EMIT(c); | |
| 1250 } | |
| 1251 return OK; | |
| 1252 } | |
| 1253 } | |
| 1254 | |
| 1255 #undef TRY_NEG | |
| 1256 #undef EMIT_GLUE | |
| 1257 | |
| 1258 return OK; | |
| 1259 } | |
| 1260 | |
| 1261 /* | |
| 1262 * Parse something followed by possible [*+=]. | |
| 1263 * | |
| 1264 * A piece is an atom, possibly followed by a multi, an indication of how many | |
| 1265 * times the atom can be matched. Example: "a*" matches any sequence of "a" | |
| 1266 * characters: "", "a", "aa", etc. | |
| 1267 * | |
| 1268 * piece ::= atom | |
| 1269 * or atom multi | |
| 1270 */ | |
| 1271 static int | |
| 1272 nfa_regpiece() | |
| 1273 { | |
| 1274 int i; | |
| 1275 int op; | |
| 1276 int ret; | |
| 1277 long minval, maxval; | |
| 1278 int greedy = TRUE; /* Braces are prefixed with '-' ? */ | |
| 1279 char_u *old_regparse, *new_regparse; | |
| 1280 int c2; | |
| 1281 int *old_post_ptr, *my_post_start; | |
| 1282 int old_regnpar; | |
| 1283 int quest; | |
| 1284 | |
| 1285 /* Save the current position in the regexp, so that we can use it if | |
| 1286 * <atom>{m,n} is next. */ | |
| 1287 old_regparse = regparse; | |
| 1288 /* Save current number of open parenthesis, so we can use it if | |
| 1289 * <atom>{m,n} is next */ | |
| 1290 old_regnpar = regnpar; | |
| 1291 /* store current pos in the postfix form, for \{m,n} involving 0s */ | |
| 1292 my_post_start = post_ptr; | |
| 1293 | |
| 1294 ret = nfa_regatom(); | |
| 1295 if (ret == FAIL) | |
| 1296 return FAIL; /* cascaded error */ | |
| 1297 | |
| 1298 op = peekchr(); | |
| 1299 if (re_multi_type(op) == NOT_MULTI) | |
| 1300 return OK; | |
| 1301 | |
| 1302 skipchr(); | |
| 1303 switch (op) | |
| 1304 { | |
| 1305 case Magic('*'): | |
| 1306 EMIT(NFA_STAR); | |
| 1307 break; | |
| 1308 | |
| 1309 case Magic('+'): | |
| 1310 /* | |
| 1311 * Trick: Normally, (a*)\+ would match the whole input "aaa". The | |
| 1312 * first and only submatch would be "aaa". But the backtracking | |
| 1313 * engine interprets the plus as "try matching one more time", and | |
| 1314 * a* matches a second time at the end of the input, the empty | |
| 1315 * string. | |
| 1316 * The submatch will the empty string. | |
| 1317 * | |
| 1318 * In order to be consistent with the old engine, we disable | |
| 1319 * NFA_PLUS, and replace <atom>+ with <atom><atom>* | |
| 1320 */ | |
| 1321 /* EMIT(NFA_PLUS); */ | |
| 1322 regnpar = old_regnpar; | |
| 1323 regparse = old_regparse; | |
| 1324 curchr = -1; | |
| 1325 if (nfa_regatom() == FAIL) | |
| 1326 return FAIL; | |
| 1327 EMIT(NFA_STAR); | |
| 1328 EMIT(NFA_CONCAT); | |
| 1329 skipchr(); /* skip the \+ */ | |
| 1330 break; | |
| 1331 | |
| 1332 case Magic('@'): | |
| 1333 op = no_Magic(getchr()); | |
| 1334 switch(op) | |
| 1335 { | |
| 1336 case '=': | |
| 1337 EMIT(NFA_PREV_ATOM_NO_WIDTH); | |
| 1338 break; | |
| 1339 case '!': | |
| 1340 case '<': | |
| 1341 case '>': | |
| 1342 /* Not supported yet */ | |
| 1343 return FAIL; | |
| 1344 default: | |
| 1345 syntax_error = TRUE; | |
| 4450 | 1346 EMSGN(_("E869: (NFA) Unknown operator '\\@%c'"), op); |
| 4444 | 1347 return FAIL; |
| 1348 } | |
| 1349 break; | |
| 1350 | |
| 1351 case Magic('?'): | |
| 1352 case Magic('='): | |
| 1353 EMIT(NFA_QUEST); | |
| 1354 break; | |
| 1355 | |
| 1356 case Magic('{'): | |
| 1357 /* a{2,5} will expand to 'aaa?a?a?' | |
| 1358 * a{-1,3} will expand to 'aa??a??', where ?? is the nongreedy | |
| 1359 * version of '?' | |
| 1360 * \v(ab){2,3} will expand to '(ab)(ab)(ab)?', where all the | |
| 1361 * parenthesis have the same id | |
| 1362 */ | |
| 1363 | |
| 1364 greedy = TRUE; | |
| 1365 c2 = peekchr(); | |
| 1366 if (c2 == '-' || c2 == Magic('-')) | |
| 1367 { | |
| 1368 skipchr(); | |
| 1369 greedy = FALSE; | |
| 1370 } | |
| 1371 if (!read_limits(&minval, &maxval)) | |
| 1372 { | |
| 1373 syntax_error = TRUE; | |
| 1374 EMSG_RET_FAIL(_("E870: (NFA regexp) Error reading repetition limits")); | |
| 1375 } | |
| 1376 /* <atom>{0,inf}, <atom>{0,} and <atom>{} are equivalent to | |
| 1377 * <atom>* */ | |
| 1378 if (minval == 0 && maxval == MAX_LIMIT && greedy) | |
| 1379 { | |
| 1380 EMIT(NFA_STAR); | |
| 1381 break; | |
| 1382 } | |
| 1383 | |
| 1384 if (maxval > NFA_BRACES_MAXLIMIT) | |
| 1385 { | |
| 1386 /* This would yield a huge automaton and use too much memory. | |
| 1387 * Revert to old engine */ | |
| 1388 return FAIL; | |
| 1389 } | |
| 1390 | |
| 1391 /* Special case: x{0} or x{-0} */ | |
| 1392 if (maxval == 0) | |
| 1393 { | |
| 1394 /* Ignore result of previous call to nfa_regatom() */ | |
| 1395 post_ptr = my_post_start; | |
| 1396 /* NFA_SKIP_CHAR has 0-length and works everywhere */ | |
| 1397 EMIT(NFA_SKIP_CHAR); | |
| 1398 return OK; | |
| 1399 } | |
| 1400 | |
| 1401 /* Ignore previous call to nfa_regatom() */ | |
| 1402 post_ptr = my_post_start; | |
| 1403 /* Save pos after the repeated atom and the \{} */ | |
| 1404 new_regparse = regparse; | |
| 1405 | |
| 1406 quest = (greedy == TRUE? NFA_QUEST : NFA_QUEST_NONGREEDY); | |
| 1407 for (i = 0; i < maxval; i++) | |
| 1408 { | |
| 1409 /* Goto beginning of the repeated atom */ | |
| 1410 regparse = old_regparse; | |
| 1411 curchr = -1; | |
| 1412 /* Restore count of parenthesis */ | |
| 1413 regnpar = old_regnpar; | |
| 1414 old_post_ptr = post_ptr; | |
| 1415 if (nfa_regatom() == FAIL) | |
| 1416 return FAIL; | |
| 1417 /* after "minval" times, atoms are optional */ | |
| 1418 if (i + 1 > minval) | |
| 1419 EMIT(quest); | |
| 1420 if (old_post_ptr != my_post_start) | |
| 1421 EMIT(NFA_CONCAT); | |
| 1422 } | |
| 1423 | |
| 1424 /* Go to just after the repeated atom and the \{} */ | |
| 1425 regparse = new_regparse; | |
| 1426 curchr = -1; | |
| 1427 | |
| 1428 break; | |
| 1429 | |
| 1430 | |
| 1431 default: | |
| 1432 break; | |
| 1433 } /* end switch */ | |
| 1434 | |
| 1435 if (re_multi_type(peekchr()) != NOT_MULTI) | |
| 1436 { | |
| 1437 /* Can't have a multi follow a multi. */ | |
| 1438 syntax_error = TRUE; | |
| 1439 EMSG_RET_FAIL(_("E871: (NFA regexp) Can't have a multi follow a multi !")); | |
| 1440 } | |
| 1441 | |
| 1442 return OK; | |
| 1443 } | |
| 1444 | |
| 1445 /* | |
| 1446 * Parse one or more pieces, concatenated. It matches a match for the | |
| 1447 * first piece, followed by a match for the second piece, etc. Example: | |
| 1448 * "f[0-9]b", first matches "f", then a digit and then "b". | |
| 1449 * | |
| 1450 * concat ::= piece | |
| 1451 * or piece piece | |
| 1452 * or piece piece piece | |
| 1453 * etc. | |
| 1454 */ | |
| 1455 static int | |
| 1456 nfa_regconcat() | |
| 1457 { | |
| 1458 int cont = TRUE; | |
| 1459 int first = TRUE; | |
| 1460 | |
| 1461 while (cont) | |
| 1462 { | |
| 1463 switch (peekchr()) | |
| 1464 { | |
| 1465 case NUL: | |
| 1466 case Magic('|'): | |
| 1467 case Magic('&'): | |
| 1468 case Magic(')'): | |
| 1469 cont = FALSE; | |
| 1470 break; | |
| 1471 | |
| 1472 case Magic('Z'): | |
| 1473 #ifdef FEAT_MBYTE | |
| 1474 regflags |= RF_ICOMBINE; | |
| 1475 #endif | |
| 1476 skipchr_keepstart(); | |
| 1477 break; | |
| 1478 case Magic('c'): | |
| 1479 regflags |= RF_ICASE; | |
| 1480 skipchr_keepstart(); | |
| 1481 break; | |
| 1482 case Magic('C'): | |
| 1483 regflags |= RF_NOICASE; | |
| 1484 skipchr_keepstart(); | |
| 1485 break; | |
| 1486 case Magic('v'): | |
| 1487 reg_magic = MAGIC_ALL; | |
| 1488 skipchr_keepstart(); | |
| 1489 curchr = -1; | |
| 1490 break; | |
| 1491 case Magic('m'): | |
| 1492 reg_magic = MAGIC_ON; | |
| 1493 skipchr_keepstart(); | |
| 1494 curchr = -1; | |
| 1495 break; | |
| 1496 case Magic('M'): | |
| 1497 reg_magic = MAGIC_OFF; | |
| 1498 skipchr_keepstart(); | |
| 1499 curchr = -1; | |
| 1500 break; | |
| 1501 case Magic('V'): | |
| 1502 reg_magic = MAGIC_NONE; | |
| 1503 skipchr_keepstart(); | |
| 1504 curchr = -1; | |
| 1505 break; | |
| 1506 | |
| 1507 default: | |
| 1508 if (nfa_regpiece() == FAIL) | |
| 1509 return FAIL; | |
| 1510 if (first == FALSE) | |
| 1511 EMIT(NFA_CONCAT); | |
| 1512 else | |
| 1513 first = FALSE; | |
| 1514 break; | |
| 1515 } | |
| 1516 } | |
| 1517 | |
| 1518 return OK; | |
| 1519 } | |
| 1520 | |
| 1521 /* | |
| 1522 * Parse a branch, one or more concats, separated by "\&". It matches the | |
| 1523 * last concat, but only if all the preceding concats also match at the same | |
| 1524 * position. Examples: | |
| 1525 * "foobeep\&..." matches "foo" in "foobeep". | |
| 1526 * ".*Peter\&.*Bob" matches in a line containing both "Peter" and "Bob" | |
| 1527 * | |
| 1528 * branch ::= concat | |
| 1529 * or concat \& concat | |
| 1530 * or concat \& concat \& concat | |
| 1531 * etc. | |
| 1532 */ | |
| 1533 static int | |
| 1534 nfa_regbranch() | |
| 1535 { | |
| 1536 int ch; | |
| 1537 int *old_post_ptr; | |
| 1538 | |
| 1539 old_post_ptr = post_ptr; | |
| 1540 | |
| 1541 /* First branch, possibly the only one */ | |
| 1542 if (nfa_regconcat() == FAIL) | |
| 1543 return FAIL; | |
| 1544 | |
| 1545 ch = peekchr(); | |
| 1546 /* Try next concats */ | |
| 1547 while (ch == Magic('&')) | |
| 1548 { | |
| 1549 skipchr(); | |
| 1550 EMIT(NFA_NOPEN); | |
| 1551 EMIT(NFA_PREV_ATOM_NO_WIDTH); | |
| 1552 old_post_ptr = post_ptr; | |
| 1553 if (nfa_regconcat() == FAIL) | |
| 1554 return FAIL; | |
| 1555 /* if concat is empty, skip a input char. But do emit a node */ | |
| 1556 if (old_post_ptr == post_ptr) | |
| 1557 EMIT(NFA_SKIP_CHAR); | |
| 1558 EMIT(NFA_CONCAT); | |
| 1559 ch = peekchr(); | |
| 1560 } | |
| 1561 | |
| 1562 /* Even if a branch is empty, emit one node for it */ | |
| 1563 if (old_post_ptr == post_ptr) | |
| 1564 EMIT(NFA_SKIP_CHAR); | |
| 1565 | |
| 1566 return OK; | |
| 1567 } | |
| 1568 | |
| 1569 /* | |
| 1570 * Parse a pattern, one or more branches, separated by "\|". It matches | |
| 1571 * anything that matches one of the branches. Example: "foo\|beep" matches | |
| 1572 * "foo" and matches "beep". If more than one branch matches, the first one | |
| 1573 * is used. | |
| 1574 * | |
| 1575 * pattern ::= branch | |
| 1576 * or branch \| branch | |
| 1577 * or branch \| branch \| branch | |
| 1578 * etc. | |
| 1579 */ | |
| 1580 static int | |
| 1581 nfa_reg(paren) | |
| 1582 int paren; /* REG_NOPAREN, REG_PAREN, REG_NPAREN or REG_ZPAREN */ | |
| 1583 { | |
| 1584 int parno = 0; | |
| 1585 | |
| 1586 #ifdef FEAT_SYN_HL | |
| 1587 #endif | |
| 1588 if (paren == REG_PAREN) | |
| 1589 { | |
| 1590 if (regnpar >= NSUBEXP) /* Too many `(' */ | |
| 1591 { | |
| 1592 syntax_error = TRUE; | |
| 1593 EMSG_RET_FAIL(_("E872: (NFA regexp) Too many '('")); | |
| 1594 } | |
| 1595 parno = regnpar++; | |
| 1596 } | |
| 1597 | |
| 1598 if (nfa_regbranch() == FAIL) | |
| 1599 return FAIL; /* cascaded error */ | |
| 1600 | |
| 1601 while (peekchr() == Magic('|')) | |
| 1602 { | |
| 1603 skipchr(); | |
| 1604 if (nfa_regbranch() == FAIL) | |
| 1605 return FAIL; /* cascaded error */ | |
| 1606 EMIT(NFA_OR); | |
| 1607 } | |
| 1608 | |
| 1609 /* Check for proper termination. */ | |
| 1610 if (paren != REG_NOPAREN && getchr() != Magic(')')) | |
| 1611 { | |
| 1612 syntax_error = TRUE; | |
| 1613 if (paren == REG_NPAREN) | |
| 1614 EMSG2_RET_FAIL(_(e_unmatchedpp), reg_magic == MAGIC_ALL); | |
| 1615 else | |
| 1616 EMSG2_RET_FAIL(_(e_unmatchedp), reg_magic == MAGIC_ALL); | |
| 1617 } | |
| 1618 else if (paren == REG_NOPAREN && peekchr() != NUL) | |
| 1619 { | |
| 1620 syntax_error = TRUE; | |
| 1621 if (peekchr() == Magic(')')) | |
| 1622 EMSG2_RET_FAIL(_(e_unmatchedpar), reg_magic == MAGIC_ALL); | |
| 1623 else | |
| 1624 EMSG_RET_FAIL(_("E873: (NFA regexp) proper termination error")); | |
| 1625 } | |
| 1626 /* | |
| 1627 * Here we set the flag allowing back references to this set of | |
| 1628 * parentheses. | |
| 1629 */ | |
| 1630 if (paren == REG_PAREN) | |
| 1631 { | |
| 1632 had_endbrace[parno] = TRUE; /* have seen the close paren */ | |
| 1633 EMIT(NFA_MOPEN + parno); | |
| 1634 } | |
| 1635 | |
| 1636 return OK; | |
| 1637 } | |
| 1638 | |
| 1639 typedef struct | |
| 1640 { | |
| 1641 char_u *start[NSUBEXP]; | |
| 1642 char_u *end[NSUBEXP]; | |
| 1643 lpos_T startpos[NSUBEXP]; | |
| 1644 lpos_T endpos[NSUBEXP]; | |
| 1645 } regsub_T; | |
| 1646 | |
| 1647 static int nfa_regmatch __ARGS((nfa_state_T *start, regsub_T *submatch, regsub_T *m)); | |
| 1648 | |
| 1649 #ifdef DEBUG | |
| 1650 static char_u code[50]; | |
| 1651 | |
| 1652 static void | |
| 1653 nfa_set_code(c) | |
| 1654 int c; | |
| 1655 { | |
| 1656 int addnl = FALSE; | |
| 1657 | |
| 1658 if (c >= NFA_FIRST_NL && c <= NFA_LAST_NL) | |
| 1659 { | |
| 1660 addnl = TRUE; | |
| 1661 c -= ADD_NL; | |
| 1662 } | |
| 1663 | |
| 1664 STRCPY(code, ""); | |
| 1665 switch (c) | |
| 1666 { | |
| 1667 case NFA_MATCH: STRCPY(code, "NFA_MATCH "); break; | |
| 1668 case NFA_SPLIT: STRCPY(code, "NFA_SPLIT "); break; | |
| 1669 case NFA_CONCAT: STRCPY(code, "NFA_CONCAT "); break; | |
| 1670 case NFA_NEWL: STRCPY(code, "NFA_NEWL "); break; | |
| 1671 case NFA_ZSTART: STRCPY(code, "NFA_ZSTART"); break; | |
| 1672 case NFA_ZEND: STRCPY(code, "NFA_ZEND"); break; | |
| 1673 | |
| 1674 case NFA_PREV_ATOM_NO_WIDTH: | |
| 1675 STRCPY(code, "NFA_PREV_ATOM_NO_WIDTH"); break; | |
| 1676 case NFA_NOPEN: STRCPY(code, "NFA_MOPEN_INVISIBLE"); break; | |
| 1677 case NFA_NCLOSE: STRCPY(code, "NFA_MCLOSE_INVISIBLE"); break; | |
| 1678 case NFA_START_INVISIBLE: STRCPY(code, "NFA_START_INVISIBLE"); break; | |
| 1679 case NFA_END_INVISIBLE: STRCPY(code, "NFA_END_INVISIBLE"); break; | |
| 1680 | |
| 1681 case NFA_COMPOSING: STRCPY(code, "NFA_COMPOSING"); break; | |
| 1682 case NFA_END_COMPOSING: STRCPY(code, "NFA_END_COMPOSING"); break; | |
| 1683 | |
| 1684 case NFA_MOPEN + 0: | |
| 1685 case NFA_MOPEN + 1: | |
| 1686 case NFA_MOPEN + 2: | |
| 1687 case NFA_MOPEN + 3: | |
| 1688 case NFA_MOPEN + 4: | |
| 1689 case NFA_MOPEN + 5: | |
| 1690 case NFA_MOPEN + 6: | |
| 1691 case NFA_MOPEN + 7: | |
| 1692 case NFA_MOPEN + 8: | |
| 1693 case NFA_MOPEN + 9: | |
| 1694 STRCPY(code, "NFA_MOPEN(x)"); | |
| 1695 code[10] = c - NFA_MOPEN + '0'; | |
| 1696 break; | |
| 1697 case NFA_MCLOSE + 0: | |
| 1698 case NFA_MCLOSE + 1: | |
| 1699 case NFA_MCLOSE + 2: | |
| 1700 case NFA_MCLOSE + 3: | |
| 1701 case NFA_MCLOSE + 4: | |
| 1702 case NFA_MCLOSE + 5: | |
| 1703 case NFA_MCLOSE + 6: | |
| 1704 case NFA_MCLOSE + 7: | |
| 1705 case NFA_MCLOSE + 8: | |
| 1706 case NFA_MCLOSE + 9: | |
| 1707 STRCPY(code, "NFA_MCLOSE(x)"); | |
| 1708 code[11] = c - NFA_MCLOSE + '0'; | |
| 1709 break; | |
| 1710 case NFA_EOL: STRCPY(code, "NFA_EOL "); break; | |
| 1711 case NFA_BOL: STRCPY(code, "NFA_BOL "); break; | |
| 1712 case NFA_EOW: STRCPY(code, "NFA_EOW "); break; | |
| 1713 case NFA_BOW: STRCPY(code, "NFA_BOW "); break; | |
| 1714 case NFA_STAR: STRCPY(code, "NFA_STAR "); break; | |
| 1715 case NFA_PLUS: STRCPY(code, "NFA_PLUS "); break; | |
| 1716 case NFA_NOT: STRCPY(code, "NFA_NOT "); break; | |
| 1717 case NFA_SKIP_CHAR: STRCPY(code, "NFA_SKIP_CHAR"); break; | |
| 1718 case NFA_OR: STRCPY(code, "NFA_OR"); break; | |
| 1719 case NFA_QUEST: STRCPY(code, "NFA_QUEST"); break; | |
| 1720 case NFA_QUEST_NONGREEDY: STRCPY(code, "NFA_QUEST_NON_GREEDY"); break; | |
| 1721 case NFA_END_NEG_RANGE: STRCPY(code, "NFA_END_NEG_RANGE"); break; | |
| 1722 case NFA_CLASS_ALNUM: STRCPY(code, "NFA_CLASS_ALNUM"); break; | |
| 1723 case NFA_CLASS_ALPHA: STRCPY(code, "NFA_CLASS_ALPHA"); break; | |
| 1724 case NFA_CLASS_BLANK: STRCPY(code, "NFA_CLASS_BLANK"); break; | |
| 1725 case NFA_CLASS_CNTRL: STRCPY(code, "NFA_CLASS_CNTRL"); break; | |
| 1726 case NFA_CLASS_DIGIT: STRCPY(code, "NFA_CLASS_DIGIT"); break; | |
| 1727 case NFA_CLASS_GRAPH: STRCPY(code, "NFA_CLASS_GRAPH"); break; | |
| 1728 case NFA_CLASS_LOWER: STRCPY(code, "NFA_CLASS_LOWER"); break; | |
| 1729 case NFA_CLASS_PRINT: STRCPY(code, "NFA_CLASS_PRINT"); break; | |
| 1730 case NFA_CLASS_PUNCT: STRCPY(code, "NFA_CLASS_PUNCT"); break; | |
| 1731 case NFA_CLASS_SPACE: STRCPY(code, "NFA_CLASS_SPACE"); break; | |
| 1732 case NFA_CLASS_UPPER: STRCPY(code, "NFA_CLASS_UPPER"); break; | |
| 1733 case NFA_CLASS_XDIGIT: STRCPY(code, "NFA_CLASS_XDIGIT"); break; | |
| 1734 case NFA_CLASS_TAB: STRCPY(code, "NFA_CLASS_TAB"); break; | |
| 1735 case NFA_CLASS_RETURN: STRCPY(code, "NFA_CLASS_RETURN"); break; | |
| 1736 case NFA_CLASS_BACKSPACE: STRCPY(code, "NFA_CLASS_BACKSPACE"); break; | |
| 1737 case NFA_CLASS_ESCAPE: STRCPY(code, "NFA_CLASS_ESCAPE"); break; | |
| 1738 | |
| 1739 case NFA_ANY: STRCPY(code, "NFA_ANY"); break; | |
| 1740 case NFA_IDENT: STRCPY(code, "NFA_IDENT"); break; | |
| 1741 case NFA_SIDENT:STRCPY(code, "NFA_SIDENT"); break; | |
| 1742 case NFA_KWORD: STRCPY(code, "NFA_KWORD"); break; | |
| 1743 case NFA_SKWORD:STRCPY(code, "NFA_SKWORD"); break; | |
| 1744 case NFA_FNAME: STRCPY(code, "NFA_FNAME"); break; | |
| 1745 case NFA_SFNAME:STRCPY(code, "NFA_SFNAME"); break; | |
| 1746 case NFA_PRINT: STRCPY(code, "NFA_PRINT"); break; | |
| 1747 case NFA_SPRINT:STRCPY(code, "NFA_SPRINT"); break; | |
| 1748 case NFA_WHITE: STRCPY(code, "NFA_WHITE"); break; | |
| 1749 case NFA_NWHITE:STRCPY(code, "NFA_NWHITE"); break; | |
| 1750 case NFA_DIGIT: STRCPY(code, "NFA_DIGIT"); break; | |
| 1751 case NFA_NDIGIT:STRCPY(code, "NFA_NDIGIT"); break; | |
| 1752 case NFA_HEX: STRCPY(code, "NFA_HEX"); break; | |
| 1753 case NFA_NHEX: STRCPY(code, "NFA_NHEX"); break; | |
| 1754 case NFA_OCTAL: STRCPY(code, "NFA_OCTAL"); break; | |
| 1755 case NFA_NOCTAL:STRCPY(code, "NFA_NOCTAL"); break; | |
| 1756 case NFA_WORD: STRCPY(code, "NFA_WORD"); break; | |
| 1757 case NFA_NWORD: STRCPY(code, "NFA_NWORD"); break; | |
| 1758 case NFA_HEAD: STRCPY(code, "NFA_HEAD"); break; | |
| 1759 case NFA_NHEAD: STRCPY(code, "NFA_NHEAD"); break; | |
| 1760 case NFA_ALPHA: STRCPY(code, "NFA_ALPHA"); break; | |
| 1761 case NFA_NALPHA:STRCPY(code, "NFA_NALPHA"); break; | |
| 1762 case NFA_LOWER: STRCPY(code, "NFA_LOWER"); break; | |
| 1763 case NFA_NLOWER:STRCPY(code, "NFA_NLOWER"); break; | |
| 1764 case NFA_UPPER: STRCPY(code, "NFA_UPPER"); break; | |
| 1765 case NFA_NUPPER:STRCPY(code, "NFA_NUPPER"); break; | |
| 1766 | |
| 1767 default: | |
| 1768 STRCPY(code, "CHAR(x)"); | |
| 1769 code[5] = c; | |
| 1770 } | |
| 1771 | |
| 1772 if (addnl == TRUE) | |
| 1773 STRCAT(code, " + NEWLINE "); | |
| 1774 | |
| 1775 } | |
| 1776 | |
| 1777 #ifdef ENABLE_LOG | |
| 1778 static FILE *log_fd; | |
| 1779 | |
| 1780 /* | |
| 1781 * Print the postfix notation of the current regexp. | |
| 1782 */ | |
| 1783 static void | |
| 1784 nfa_postfix_dump(expr, retval) | |
| 1785 char_u *expr; | |
| 1786 int retval; | |
| 1787 { | |
| 1788 int *p; | |
| 1789 FILE *f; | |
| 1790 | |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
1791 f = fopen(NFA_REGEXP_DUMP_LOG, "a"); |
| 4444 | 1792 if (f != NULL) |
| 1793 { | |
| 1794 fprintf(f, "\n-------------------------\n"); | |
| 1795 if (retval == FAIL) | |
| 1796 fprintf(f, ">>> NFA engine failed ... \n"); | |
| 1797 else if (retval == OK) | |
| 1798 fprintf(f, ">>> NFA engine succeeded !\n"); | |
| 1799 fprintf(f, "Regexp: \"%s\"\nPostfix notation (char): \"", expr); | |
| 4464 | 1800 for (p = post_start; *p && p < post_end; p++) |
| 4444 | 1801 { |
| 1802 nfa_set_code(*p); | |
| 1803 fprintf(f, "%s, ", code); | |
| 1804 } | |
| 1805 fprintf(f, "\"\nPostfix notation (int): "); | |
| 4464 | 1806 for (p = post_start; *p && p < post_end; p++) |
| 4444 | 1807 fprintf(f, "%d ", *p); |
| 1808 fprintf(f, "\n\n"); | |
| 1809 fclose(f); | |
| 1810 } | |
| 1811 } | |
| 1812 | |
| 1813 /* | |
| 1814 * Print the NFA starting with a root node "state". | |
| 1815 */ | |
| 1816 static void | |
|
4533
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1817 nfa_print_state(debugf, state) |
| 4444 | 1818 FILE *debugf; |
| 1819 nfa_state_T *state; | |
| 1820 { | |
|
4533
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1821 garray_T indent; |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1822 |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1823 ga_init2(&indent, 1, 64); |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1824 ga_append(&indent, '\0'); |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1825 nfa_print_state2(debugf, state, &indent); |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1826 ga_clear(&indent); |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1827 } |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1828 |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1829 static void |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1830 nfa_print_state2(debugf, state, indent) |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1831 FILE *debugf; |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1832 nfa_state_T *state; |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1833 garray_T *indent; |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1834 { |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1835 char_u *p; |
| 4444 | 1836 |
| 1837 if (state == NULL) | |
| 1838 return; | |
| 1839 | |
| 1840 fprintf(debugf, "(%2d)", abs(state->id)); | |
|
4533
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1841 |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1842 /* Output indent */ |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1843 p = (char_u *)indent->ga_data; |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1844 if (indent->ga_len >= 3) |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1845 { |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1846 int last = indent->ga_len - 3; |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1847 char_u save[2]; |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1848 |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1849 STRNCPY(save, &p[last], 2); |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1850 STRNCPY(&p[last], "+-", 2); |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1851 fprintf(debugf, " %s", p); |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1852 STRNCPY(&p[last], save, 2); |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1853 } |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1854 else |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1855 fprintf(debugf, " %s", p); |
| 4444 | 1856 |
| 1857 nfa_set_code(state->c); | |
|
4533
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1858 fprintf(debugf, "%s%s (%d) (id=%d)\n", |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1859 state->negated ? "NOT " : "", code, state->c, abs(state->id)); |
| 4444 | 1860 if (state->id < 0) |
| 1861 return; | |
| 1862 | |
| 1863 state->id = abs(state->id) * -1; | |
|
4533
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1864 |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1865 /* grow indent for state->out */ |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1866 indent->ga_len -= 1; |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1867 if (state->out1) |
|
4537
5cc98a5898cf
updated for version 7.3.1016
Bram Moolenaar <bram@vim.org>
parents:
4535
diff
changeset
|
1868 ga_concat(indent, (char_u *)"| "); |
|
4533
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1869 else |
|
4537
5cc98a5898cf
updated for version 7.3.1016
Bram Moolenaar <bram@vim.org>
parents:
4535
diff
changeset
|
1870 ga_concat(indent, (char_u *)" "); |
|
4533
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1871 ga_append(indent, '\0'); |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1872 |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1873 nfa_print_state2(debugf, state->out, indent); |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1874 |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1875 /* replace last part of indent for state->out1 */ |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1876 indent->ga_len -= 3; |
|
4537
5cc98a5898cf
updated for version 7.3.1016
Bram Moolenaar <bram@vim.org>
parents:
4535
diff
changeset
|
1877 ga_concat(indent, (char_u *)" "); |
|
4533
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1878 ga_append(indent, '\0'); |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1879 |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1880 nfa_print_state2(debugf, state->out1, indent); |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1881 |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1882 /* shrink indent */ |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1883 indent->ga_len -= 3; |
|
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1884 ga_append(indent, '\0'); |
| 4444 | 1885 } |
| 1886 | |
| 1887 /* | |
| 1888 * Print the NFA state machine. | |
| 1889 */ | |
| 1890 static void | |
| 1891 nfa_dump(prog) | |
| 1892 nfa_regprog_T *prog; | |
| 1893 { | |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
1894 FILE *debugf = fopen(NFA_REGEXP_DUMP_LOG, "a"); |
| 4444 | 1895 |
| 1896 if (debugf != NULL) | |
| 1897 { | |
|
4533
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
1898 nfa_print_state(debugf, prog->start); |
| 4444 | 1899 fclose(debugf); |
| 1900 } | |
| 1901 } | |
| 1902 #endif /* ENABLE_LOG */ | |
| 1903 #endif /* DEBUG */ | |
| 1904 | |
| 1905 /* | |
| 1906 * Parse r.e. @expr and convert it into postfix form. | |
| 1907 * Return the postfix string on success, NULL otherwise. | |
| 1908 */ | |
| 1909 static int * | |
| 1910 re2post() | |
| 1911 { | |
| 1912 if (nfa_reg(REG_NOPAREN) == FAIL) | |
| 1913 return NULL; | |
| 1914 EMIT(NFA_MOPEN); | |
| 1915 return post_start; | |
| 1916 } | |
| 1917 | |
| 1918 /* NB. Some of the code below is inspired by Russ's. */ | |
| 1919 | |
| 1920 /* | |
| 1921 * Represents an NFA state plus zero or one or two arrows exiting. | |
| 1922 * if c == MATCH, no arrows out; matching state. | |
| 1923 * If c == SPLIT, unlabeled arrows to out and out1 (if != NULL). | |
| 1924 * If c < 256, labeled arrow with character c to out. | |
| 1925 */ | |
| 1926 | |
| 1927 static nfa_state_T *state_ptr; /* points to nfa_prog->state */ | |
| 1928 | |
| 1929 /* | |
| 1930 * Allocate and initialize nfa_state_T. | |
| 1931 */ | |
| 1932 static nfa_state_T * | |
| 1933 new_state(c, out, out1) | |
| 1934 int c; | |
| 1935 nfa_state_T *out; | |
| 1936 nfa_state_T *out1; | |
| 1937 { | |
| 1938 nfa_state_T *s; | |
| 1939 | |
| 1940 if (istate >= nstate) | |
| 1941 return NULL; | |
| 1942 | |
| 1943 s = &state_ptr[istate++]; | |
| 1944 | |
| 1945 s->c = c; | |
| 1946 s->out = out; | |
| 1947 s->out1 = out1; | |
| 1948 | |
| 1949 s->id = istate; | |
| 1950 s->lastlist = 0; | |
| 1951 s->visits = 0; | |
| 1952 s->negated = FALSE; | |
| 1953 | |
| 1954 return s; | |
| 1955 } | |
| 1956 | |
| 1957 /* | |
| 1958 * A partially built NFA without the matching state filled in. | |
| 1959 * Frag_T.start points at the start state. | |
| 1960 * Frag_T.out is a list of places that need to be set to the | |
| 1961 * next state for this fragment. | |
| 1962 */ | |
| 1963 typedef union Ptrlist Ptrlist; | |
| 1964 struct Frag | |
| 1965 { | |
| 1966 nfa_state_T *start; | |
| 1967 Ptrlist *out; | |
| 1968 }; | |
| 1969 typedef struct Frag Frag_T; | |
| 1970 | |
| 1971 static Frag_T frag __ARGS((nfa_state_T *start, Ptrlist *out)); | |
| 1972 static Ptrlist *list1 __ARGS((nfa_state_T **outp)); | |
| 1973 static void patch __ARGS((Ptrlist *l, nfa_state_T *s)); | |
| 1974 static Ptrlist *append __ARGS((Ptrlist *l1, Ptrlist *l2)); | |
| 1975 static void st_push __ARGS((Frag_T s, Frag_T **p, Frag_T *stack_end)); | |
| 1976 static Frag_T st_pop __ARGS((Frag_T **p, Frag_T *stack)); | |
| 1977 | |
| 1978 /* | |
| 4456 | 1979 * Initialize a Frag_T struct and return it. |
| 4444 | 1980 */ |
| 1981 static Frag_T | |
| 1982 frag(start, out) | |
| 1983 nfa_state_T *start; | |
| 1984 Ptrlist *out; | |
| 1985 { | |
| 4456 | 1986 Frag_T n; |
| 1987 | |
| 1988 n.start = start; | |
| 1989 n.out = out; | |
| 4444 | 1990 return n; |
| 1991 } | |
| 1992 | |
| 1993 /* | |
| 1994 * Since the out pointers in the list are always | |
| 1995 * uninitialized, we use the pointers themselves | |
| 1996 * as storage for the Ptrlists. | |
| 1997 */ | |
| 1998 union Ptrlist | |
| 1999 { | |
| 2000 Ptrlist *next; | |
| 2001 nfa_state_T *s; | |
| 2002 }; | |
| 2003 | |
| 2004 /* | |
| 2005 * Create singleton list containing just outp. | |
| 2006 */ | |
| 2007 static Ptrlist * | |
| 2008 list1(outp) | |
| 2009 nfa_state_T **outp; | |
| 2010 { | |
| 2011 Ptrlist *l; | |
| 2012 | |
| 2013 l = (Ptrlist *)outp; | |
| 2014 l->next = NULL; | |
| 2015 return l; | |
| 2016 } | |
| 2017 | |
| 2018 /* | |
| 2019 * Patch the list of states at out to point to start. | |
| 2020 */ | |
| 2021 static void | |
| 2022 patch(l, s) | |
| 2023 Ptrlist *l; | |
| 2024 nfa_state_T *s; | |
| 2025 { | |
| 2026 Ptrlist *next; | |
| 2027 | |
| 2028 for (; l; l = next) | |
| 2029 { | |
| 2030 next = l->next; | |
| 2031 l->s = s; | |
| 2032 } | |
| 2033 } | |
| 2034 | |
| 2035 | |
| 2036 /* | |
| 2037 * Join the two lists l1 and l2, returning the combination. | |
| 2038 */ | |
| 2039 static Ptrlist * | |
| 2040 append(l1, l2) | |
| 2041 Ptrlist *l1; | |
| 2042 Ptrlist *l2; | |
| 2043 { | |
| 2044 Ptrlist *oldl1; | |
| 2045 | |
| 2046 oldl1 = l1; | |
| 2047 while (l1->next) | |
| 2048 l1 = l1->next; | |
| 2049 l1->next = l2; | |
| 2050 return oldl1; | |
| 2051 } | |
| 2052 | |
| 2053 /* | |
| 2054 * Stack used for transforming postfix form into NFA. | |
| 2055 */ | |
| 2056 static Frag_T empty; | |
| 2057 | |
| 2058 static void | |
| 2059 st_error(postfix, end, p) | |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
2060 int *postfix UNUSED; |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
2061 int *end UNUSED; |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
2062 int *p UNUSED; |
| 4444 | 2063 { |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
2064 #ifdef NFA_REGEXP_ERROR_LOG |
| 4444 | 2065 FILE *df; |
| 2066 int *p2; | |
| 2067 | |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
2068 df = fopen(NFA_REGEXP_ERROR_LOG, "a"); |
| 4444 | 2069 if (df) |
| 2070 { | |
| 2071 fprintf(df, "Error popping the stack!\n"); | |
| 2072 #ifdef DEBUG | |
| 2073 fprintf(df, "Current regexp is \"%s\"\n", nfa_regengine.expr); | |
| 2074 #endif | |
| 2075 fprintf(df, "Postfix form is: "); | |
| 2076 #ifdef DEBUG | |
| 2077 for (p2 = postfix; p2 < end; p2++) | |
| 2078 { | |
| 2079 nfa_set_code(*p2); | |
| 2080 fprintf(df, "%s, ", code); | |
| 2081 } | |
| 2082 nfa_set_code(*p); | |
| 2083 fprintf(df, "\nCurrent position is: "); | |
| 2084 for (p2 = postfix; p2 <= p; p2 ++) | |
| 2085 { | |
| 2086 nfa_set_code(*p2); | |
| 2087 fprintf(df, "%s, ", code); | |
| 2088 } | |
| 2089 #else | |
| 2090 for (p2 = postfix; p2 < end; p2++) | |
| 2091 { | |
| 2092 fprintf(df, "%d, ", *p2); | |
| 2093 } | |
| 2094 fprintf(df, "\nCurrent position is: "); | |
| 2095 for (p2 = postfix; p2 <= p; p2 ++) | |
| 2096 { | |
| 2097 fprintf(df, "%d, ", *p2); | |
| 2098 } | |
| 2099 #endif | |
| 2100 fprintf(df, "\n--------------------------\n"); | |
| 2101 fclose(df); | |
| 2102 } | |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
2103 #endif |
| 4444 | 2104 EMSG(_("E874: (NFA) Could not pop the stack !")); |
| 2105 } | |
| 2106 | |
| 2107 /* | |
| 2108 * Push an item onto the stack. | |
| 2109 */ | |
| 2110 static void | |
| 2111 st_push(s, p, stack_end) | |
| 2112 Frag_T s; | |
| 2113 Frag_T **p; | |
| 2114 Frag_T *stack_end; | |
| 2115 { | |
| 2116 Frag_T *stackp = *p; | |
| 2117 | |
| 2118 if (stackp >= stack_end) | |
| 2119 return; | |
| 2120 *stackp = s; | |
| 2121 *p = *p + 1; | |
| 2122 } | |
| 2123 | |
| 2124 /* | |
| 2125 * Pop an item from the stack. | |
| 2126 */ | |
| 2127 static Frag_T | |
| 2128 st_pop(p, stack) | |
| 2129 Frag_T **p; | |
| 2130 Frag_T *stack; | |
| 2131 { | |
| 2132 Frag_T *stackp; | |
| 2133 | |
| 2134 *p = *p - 1; | |
| 2135 stackp = *p; | |
| 2136 if (stackp < stack) | |
| 2137 return empty; | |
| 2138 return **p; | |
| 2139 } | |
| 2140 | |
| 2141 /* | |
| 2142 * Convert a postfix form into its equivalent NFA. | |
| 2143 * Return the NFA start state on success, NULL otherwise. | |
| 2144 */ | |
| 2145 static nfa_state_T * | |
| 2146 post2nfa(postfix, end, nfa_calc_size) | |
| 2147 int *postfix; | |
| 2148 int *end; | |
| 2149 int nfa_calc_size; | |
| 2150 { | |
| 2151 int *p; | |
| 2152 int mopen; | |
| 2153 int mclose; | |
| 2154 Frag_T *stack = NULL; | |
| 2155 Frag_T *stackp = NULL; | |
| 2156 Frag_T *stack_end = NULL; | |
| 2157 Frag_T e1; | |
| 2158 Frag_T e2; | |
| 2159 Frag_T e; | |
| 2160 nfa_state_T *s; | |
| 2161 nfa_state_T *s1; | |
| 2162 nfa_state_T *matchstate; | |
| 4484 | 2163 nfa_state_T *ret = NULL; |
| 4444 | 2164 |
| 2165 if (postfix == NULL) | |
| 2166 return NULL; | |
| 2167 | |
| 4456 | 2168 #define PUSH(s) st_push((s), &stackp, stack_end) |
| 4444 | 2169 #define POP() st_pop(&stackp, stack); \ |
| 2170 if (stackp < stack) \ | |
| 2171 { \ | |
| 2172 st_error(postfix, end, p); \ | |
| 2173 return NULL; \ | |
| 2174 } | |
| 2175 | |
| 2176 if (nfa_calc_size == FALSE) | |
| 2177 { | |
| 2178 /* Allocate space for the stack. Max states on the stack : nstate */ | |
| 4462 | 2179 stack = (Frag_T *) lalloc((nstate + 1) * sizeof(Frag_T), TRUE); |
| 4444 | 2180 stackp = stack; |
| 4462 | 2181 stack_end = stack + (nstate + 1); |
| 4444 | 2182 } |
| 2183 | |
| 2184 for (p = postfix; p < end; ++p) | |
| 2185 { | |
| 2186 switch (*p) | |
| 2187 { | |
| 2188 case NFA_CONCAT: | |
| 2189 /* Catenation. | |
| 2190 * Pay attention: this operator does not exist | |
| 2191 * in the r.e. itself (it is implicit, really). | |
| 2192 * It is added when r.e. is translated to postfix | |
| 2193 * form in re2post(). | |
| 2194 * | |
| 2195 * No new state added here. */ | |
| 2196 if (nfa_calc_size == TRUE) | |
| 2197 { | |
| 4458 | 2198 /* nstate += 0; */ |
| 4444 | 2199 break; |
| 2200 } | |
| 2201 e2 = POP(); | |
| 2202 e1 = POP(); | |
| 2203 patch(e1.out, e2.start); | |
| 2204 PUSH(frag(e1.start, e2.out)); | |
| 2205 break; | |
| 2206 | |
| 2207 case NFA_NOT: | |
| 2208 /* Negation of a character */ | |
| 2209 if (nfa_calc_size == TRUE) | |
| 2210 { | |
| 4458 | 2211 /* nstate += 0; */ |
| 4444 | 2212 break; |
| 2213 } | |
| 2214 e1 = POP(); | |
| 2215 e1.start->negated = TRUE; | |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
2216 #ifdef FEAT_MBYTE |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
2217 if (e1.start->c == NFA_COMPOSING) |
| 4444 | 2218 e1.start->out1->negated = TRUE; |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
2219 #endif |
| 4444 | 2220 PUSH(e1); |
| 2221 break; | |
| 2222 | |
| 2223 case NFA_OR: | |
| 2224 /* Alternation */ | |
| 2225 if (nfa_calc_size == TRUE) | |
| 2226 { | |
| 4458 | 2227 nstate++; |
| 4444 | 2228 break; |
| 2229 } | |
| 2230 e2 = POP(); | |
| 2231 e1 = POP(); | |
| 2232 s = new_state(NFA_SPLIT, e1.start, e2.start); | |
| 2233 if (s == NULL) | |
| 4484 | 2234 goto theend; |
| 4444 | 2235 PUSH(frag(s, append(e1.out, e2.out))); |
| 2236 break; | |
| 2237 | |
| 2238 case NFA_STAR: | |
| 2239 /* Zero or more */ | |
| 2240 if (nfa_calc_size == TRUE) | |
| 2241 { | |
| 4458 | 2242 nstate++; |
| 4444 | 2243 break; |
| 2244 } | |
| 2245 e = POP(); | |
| 2246 s = new_state(NFA_SPLIT, e.start, NULL); | |
| 2247 if (s == NULL) | |
| 4484 | 2248 goto theend; |
| 4444 | 2249 patch(e.out, s); |
| 2250 PUSH(frag(s, list1(&s->out1))); | |
| 2251 break; | |
| 2252 | |
| 2253 case NFA_QUEST: | |
| 2254 /* one or zero atoms=> greedy match */ | |
| 2255 if (nfa_calc_size == TRUE) | |
| 2256 { | |
| 4458 | 2257 nstate++; |
| 4444 | 2258 break; |
| 2259 } | |
| 2260 e = POP(); | |
| 2261 s = new_state(NFA_SPLIT, e.start, NULL); | |
| 2262 if (s == NULL) | |
| 4484 | 2263 goto theend; |
| 4444 | 2264 PUSH(frag(s, append(e.out, list1(&s->out1)))); |
| 2265 break; | |
| 2266 | |
| 2267 case NFA_QUEST_NONGREEDY: | |
| 2268 /* zero or one atoms => non-greedy match */ | |
| 2269 if (nfa_calc_size == TRUE) | |
| 2270 { | |
| 4458 | 2271 nstate++; |
| 4444 | 2272 break; |
| 2273 } | |
| 2274 e = POP(); | |
| 2275 s = new_state(NFA_SPLIT, NULL, e.start); | |
| 2276 if (s == NULL) | |
| 4484 | 2277 goto theend; |
| 4444 | 2278 PUSH(frag(s, append(e.out, list1(&s->out)))); |
| 2279 break; | |
| 2280 | |
| 2281 case NFA_PLUS: | |
| 2282 /* One or more */ | |
| 2283 if (nfa_calc_size == TRUE) | |
| 2284 { | |
| 4458 | 2285 nstate++; |
| 4444 | 2286 break; |
| 2287 } | |
| 2288 e = POP(); | |
| 2289 s = new_state(NFA_SPLIT, e.start, NULL); | |
| 2290 if (s == NULL) | |
| 4484 | 2291 goto theend; |
| 4444 | 2292 patch(e.out, s); |
| 2293 PUSH(frag(e.start, list1(&s->out1))); | |
| 2294 break; | |
| 2295 | |
| 2296 case NFA_SKIP_CHAR: | |
| 2297 /* Symbol of 0-length, Used in a repetition | |
| 2298 * with max/min count of 0 */ | |
| 2299 if (nfa_calc_size == TRUE) | |
| 2300 { | |
| 4458 | 2301 nstate++; |
| 4444 | 2302 break; |
| 2303 } | |
| 2304 s = new_state(NFA_SKIP_CHAR, NULL, NULL); | |
| 2305 if (s == NULL) | |
| 4484 | 2306 goto theend; |
| 4444 | 2307 PUSH(frag(s, list1(&s->out))); |
| 2308 break; | |
| 2309 | |
| 2310 case NFA_PREV_ATOM_NO_WIDTH: | |
| 2311 /* The \@= operator: match the preceding atom with 0 width. | |
| 2312 * Surrounds the preceding atom with START_INVISIBLE and | |
| 2313 * END_INVISIBLE, similarly to MOPEN. | |
| 2314 */ | |
| 2315 /* TODO: Maybe this drops the speed? */ | |
| 4484 | 2316 goto theend; |
| 4444 | 2317 |
| 2318 if (nfa_calc_size == TRUE) | |
| 2319 { | |
| 2320 nstate += 2; | |
| 2321 break; | |
| 2322 } | |
| 2323 e = POP(); | |
| 2324 s1 = new_state(NFA_END_INVISIBLE, NULL, NULL); | |
| 2325 if (s1 == NULL) | |
| 4484 | 2326 goto theend; |
| 4444 | 2327 patch(e.out, s1); |
| 2328 | |
| 2329 s = new_state(NFA_START_INVISIBLE, e.start, s1); | |
| 2330 if (s == NULL) | |
| 4484 | 2331 goto theend; |
| 4444 | 2332 PUSH(frag(s, list1(&s1->out))); |
| 2333 break; | |
| 2334 | |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
2335 #ifdef FEAT_MBYTE |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
2336 case NFA_COMPOSING: /* char with composing char */ |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
2337 #if 0 |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
2338 /* TODO */ |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
2339 if (regflags & RF_ICOMBINE) |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
2340 { |
|
4529
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
2341 /* use the base character only */ |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
2342 } |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
2343 #endif |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
2344 /* FALLTHROUGH */ |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
2345 #endif |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
2346 |
| 4444 | 2347 case NFA_MOPEN + 0: /* Submatch */ |
| 2348 case NFA_MOPEN + 1: | |
| 2349 case NFA_MOPEN + 2: | |
| 2350 case NFA_MOPEN + 3: | |
| 2351 case NFA_MOPEN + 4: | |
| 2352 case NFA_MOPEN + 5: | |
| 2353 case NFA_MOPEN + 6: | |
| 2354 case NFA_MOPEN + 7: | |
| 2355 case NFA_MOPEN + 8: | |
| 2356 case NFA_MOPEN + 9: | |
| 2357 case NFA_NOPEN: /* \%( "Invisible Submatch" */ | |
| 2358 if (nfa_calc_size == TRUE) | |
| 2359 { | |
| 2360 nstate += 2; | |
| 2361 break; | |
| 2362 } | |
| 2363 | |
| 2364 mopen = *p; | |
| 2365 switch (*p) | |
| 2366 { | |
| 2367 case NFA_NOPEN: | |
| 2368 mclose = NFA_NCLOSE; | |
| 2369 break; | |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
2370 #ifdef FEAT_MBYTE |
| 4444 | 2371 case NFA_COMPOSING: |
| 2372 mclose = NFA_END_COMPOSING; | |
| 2373 break; | |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
2374 #endif |
| 4444 | 2375 default: |
| 2376 /* NFA_MOPEN(0) ... NFA_MOPEN(9) */ | |
| 2377 mclose = *p + NSUBEXP; | |
| 2378 break; | |
| 2379 } | |
| 2380 | |
| 2381 /* Allow "NFA_MOPEN" as a valid postfix representation for | |
| 2382 * the empty regexp "". In this case, the NFA will be | |
| 2383 * NFA_MOPEN -> NFA_MCLOSE. Note that this also allows | |
| 2384 * empty groups of parenthesis, and empty mbyte chars */ | |
| 2385 if (stackp == stack) | |
| 2386 { | |
| 2387 s = new_state(mopen, NULL, NULL); | |
| 2388 if (s == NULL) | |
| 4484 | 2389 goto theend; |
| 4444 | 2390 s1 = new_state(mclose, NULL, NULL); |
| 2391 if (s1 == NULL) | |
| 4484 | 2392 goto theend; |
| 4444 | 2393 patch(list1(&s->out), s1); |
| 2394 PUSH(frag(s, list1(&s1->out))); | |
| 2395 break; | |
| 2396 } | |
| 2397 | |
| 2398 /* At least one node was emitted before NFA_MOPEN, so | |
| 2399 * at least one node will be between NFA_MOPEN and NFA_MCLOSE */ | |
| 2400 e = POP(); | |
| 2401 s = new_state(mopen, e.start, NULL); /* `(' */ | |
| 2402 if (s == NULL) | |
| 4484 | 2403 goto theend; |
| 4444 | 2404 |
| 2405 s1 = new_state(mclose, NULL, NULL); /* `)' */ | |
| 2406 if (s1 == NULL) | |
| 4484 | 2407 goto theend; |
| 4444 | 2408 patch(e.out, s1); |
| 2409 | |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
2410 #ifdef FEAT_MBYTE |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
2411 if (mopen == NFA_COMPOSING) |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
2412 /* COMPOSING->out1 = END_COMPOSING */ |
| 4444 | 2413 patch(list1(&s->out1), s1); |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
2414 #endif |
| 4444 | 2415 |
| 2416 PUSH(frag(s, list1(&s1->out))); | |
| 2417 break; | |
| 2418 | |
| 2419 case NFA_ZSTART: | |
| 2420 case NFA_ZEND: | |
| 2421 default: | |
| 2422 /* Operands */ | |
| 2423 if (nfa_calc_size == TRUE) | |
| 2424 { | |
| 4458 | 2425 nstate++; |
| 4444 | 2426 break; |
| 2427 } | |
| 2428 s = new_state(*p, NULL, NULL); | |
| 2429 if (s == NULL) | |
| 4484 | 2430 goto theend; |
| 4444 | 2431 PUSH(frag(s, list1(&s->out))); |
| 2432 break; | |
| 2433 | |
| 2434 } /* switch(*p) */ | |
| 2435 | |
| 2436 } /* for(p = postfix; *p; ++p) */ | |
| 2437 | |
| 2438 if (nfa_calc_size == TRUE) | |
| 2439 { | |
| 4458 | 2440 nstate++; |
| 4484 | 2441 goto theend; /* Return value when counting size is ignored anyway */ |
| 4444 | 2442 } |
| 2443 | |
| 2444 e = POP(); | |
| 2445 if (stackp != stack) | |
| 2446 EMSG_RET_NULL(_("E875: (NFA regexp) (While converting from postfix to NFA), too many states left on stack")); | |
| 2447 | |
| 2448 if (istate >= nstate) | |
| 2449 EMSG_RET_NULL(_("E876: (NFA regexp) Not enough space to store the whole NFA ")); | |
| 2450 | |
| 2451 matchstate = &state_ptr[istate++]; /* the match state */ | |
| 2452 matchstate->c = NFA_MATCH; | |
| 2453 matchstate->out = matchstate->out1 = NULL; | |
| 2454 | |
| 2455 patch(e.out, matchstate); | |
| 4484 | 2456 ret = e.start; |
| 2457 | |
| 2458 theend: | |
| 2459 vim_free(stack); | |
| 2460 return ret; | |
| 4444 | 2461 |
| 2462 #undef POP1 | |
| 2463 #undef PUSH1 | |
| 2464 #undef POP2 | |
| 2465 #undef PUSH2 | |
| 2466 #undef POP | |
| 2467 #undef PUSH | |
| 2468 } | |
| 2469 | |
| 2470 /**************************************************************** | |
| 2471 * NFA execution code. | |
| 2472 ****************************************************************/ | |
| 2473 | |
|
4539
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2474 /* nfa_thread_T contains runtime information of a NFA state */ |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2475 typedef struct |
| 4444 | 2476 { |
| 2477 nfa_state_T *state; | |
|
4539
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2478 regsub_T sub; /* Submatch info. TODO: expensive! */ |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2479 } nfa_thread_T; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2480 |
| 4444 | 2481 |
| 2482 typedef struct | |
| 2483 { | |
|
4539
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2484 nfa_thread_T *t; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2485 int n; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2486 } nfa_list_T; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2487 |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2488 static void addstate __ARGS((nfa_list_T *l, nfa_state_T *state, regsub_T *m, int off, int lid, int *match)); |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2489 |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2490 static void addstate_here __ARGS((nfa_list_T *l, nfa_state_T *state, regsub_T *m, int lid, int *match, int *ip)); |
| 4444 | 2491 |
| 2492 static void | |
| 2493 addstate(l, state, m, off, lid, match) | |
|
4539
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2494 nfa_list_T *l; /* runtime state list */ |
| 4444 | 2495 nfa_state_T *state; /* state to update */ |
| 2496 regsub_T *m; /* pointers to subexpressions */ | |
|
4515
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2497 int off; /* byte offset, when -1 go to next line */ |
| 4444 | 2498 int lid; |
| 2499 int *match; /* found match? */ | |
| 2500 { | |
| 2501 regsub_T save; | |
| 2502 int subidx = 0; | |
|
4539
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2503 nfa_thread_T *lastthread; |
| 4444 | 2504 |
| 2505 if (l == NULL || state == NULL) | |
| 2506 return; | |
| 2507 | |
| 2508 switch (state->c) | |
| 2509 { | |
| 2510 case NFA_SPLIT: | |
| 2511 case NFA_NOT: | |
| 2512 case NFA_NOPEN: | |
| 2513 case NFA_NCLOSE: | |
| 2514 case NFA_MCLOSE: | |
| 2515 case NFA_MCLOSE + 1: | |
| 2516 case NFA_MCLOSE + 2: | |
| 2517 case NFA_MCLOSE + 3: | |
| 2518 case NFA_MCLOSE + 4: | |
| 2519 case NFA_MCLOSE + 5: | |
| 2520 case NFA_MCLOSE + 6: | |
| 2521 case NFA_MCLOSE + 7: | |
| 2522 case NFA_MCLOSE + 8: | |
| 2523 case NFA_MCLOSE + 9: | |
| 2524 /* Do not remember these nodes in list "thislist" or "nextlist" */ | |
| 2525 break; | |
| 2526 | |
| 2527 default: | |
| 2528 if (state->lastlist == lid) | |
| 2529 { | |
| 2530 if (++state->visits > 2) | |
| 2531 return; | |
| 2532 } | |
| 2533 else | |
| 2534 { | |
| 2535 /* add the state to the list */ | |
| 2536 state->lastlist = lid; | |
|
4537
5cc98a5898cf
updated for version 7.3.1016
Bram Moolenaar <bram@vim.org>
parents:
4535
diff
changeset
|
2537 lastthread = &l->t[l->n++]; |
|
5cc98a5898cf
updated for version 7.3.1016
Bram Moolenaar <bram@vim.org>
parents:
4535
diff
changeset
|
2538 lastthread->state = state; |
|
4539
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2539 lastthread->sub = *m; /* TODO: expensive! */ |
| 4444 | 2540 } |
| 2541 } | |
| 2542 | |
| 2543 #ifdef ENABLE_LOG | |
| 2544 nfa_set_code(state->c); | |
| 2545 fprintf(log_fd, "> Adding state %d to list. Character %s, code %d\n", | |
| 2546 abs(state->id), code, state->c); | |
| 2547 #endif | |
| 2548 switch (state->c) | |
| 2549 { | |
| 2550 case NFA_MATCH: | |
| 2551 *match = TRUE; | |
| 2552 break; | |
| 2553 | |
| 2554 case NFA_SPLIT: | |
| 2555 addstate(l, state->out, m, off, lid, match); | |
| 2556 addstate(l, state->out1, m, off, lid, match); | |
| 2557 break; | |
| 2558 | |
| 2559 case NFA_SKIP_CHAR: | |
| 2560 addstate(l, state->out, m, off, lid, match); | |
| 2561 break; | |
| 2562 | |
| 2563 #if 0 | |
| 2564 case NFA_END_NEG_RANGE: | |
| 2565 /* Nothing to handle here. nfa_regmatch() will take care of it */ | |
| 2566 break; | |
| 2567 | |
| 2568 case NFA_NOT: | |
| 2569 EMSG(_("E999: (NFA regexp internal error) Should not process NOT node !")); | |
| 2570 #ifdef ENABLE_LOG | |
| 2571 fprintf(f, "\n\n>>> E999: Added state NFA_NOT to a list ... Something went wrong ! Why wasn't it processed already? \n\n"); | |
| 2572 #endif | |
| 2573 break; | |
| 2574 | |
| 2575 case NFA_COMPOSING: | |
| 2576 /* nfa_regmatch() will match all the bytes of this composing char. */ | |
| 2577 break; | |
| 2578 #endif | |
| 2579 | |
| 2580 case NFA_NOPEN: | |
| 2581 case NFA_NCLOSE: | |
| 2582 addstate(l, state->out, m, off, lid, match); | |
| 2583 break; | |
| 2584 | |
| 2585 /* If this state is reached, then a recursive call of nfa_regmatch() | |
| 2586 * succeeded. the next call saves the found submatches in the | |
| 2587 * first state after the "invisible" branch. */ | |
| 2588 #if 0 | |
| 2589 case NFA_END_INVISIBLE: | |
| 2590 break; | |
| 2591 #endif | |
| 2592 | |
| 2593 case NFA_MOPEN + 0: | |
| 2594 case NFA_MOPEN + 1: | |
| 2595 case NFA_MOPEN + 2: | |
| 2596 case NFA_MOPEN + 3: | |
| 2597 case NFA_MOPEN + 4: | |
| 2598 case NFA_MOPEN + 5: | |
| 2599 case NFA_MOPEN + 6: | |
| 2600 case NFA_MOPEN + 7: | |
| 2601 case NFA_MOPEN + 8: | |
| 2602 case NFA_MOPEN + 9: | |
| 2603 case NFA_ZSTART: | |
| 2604 subidx = state->c - NFA_MOPEN; | |
| 2605 if (state->c == NFA_ZSTART) | |
| 2606 subidx = 0; | |
| 2607 | |
| 2608 if (REG_MULTI) | |
| 2609 { | |
| 2610 save.startpos[subidx] = m->startpos[subidx]; | |
| 2611 save.endpos[subidx] = m->endpos[subidx]; | |
|
4515
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2612 if (off == -1) |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2613 { |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2614 m->startpos[subidx].lnum = reglnum + 1; |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2615 m->startpos[subidx].col = 0; |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2616 } |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2617 else |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2618 { |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2619 m->startpos[subidx].lnum = reglnum; |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2620 m->startpos[subidx].col = |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2621 (colnr_T)(reginput - regline + off); |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2622 } |
| 4444 | 2623 } |
| 2624 else | |
| 2625 { | |
| 2626 save.start[subidx] = m->start[subidx]; | |
| 2627 save.end[subidx] = m->end[subidx]; | |
| 2628 m->start[subidx] = reginput + off; | |
| 2629 } | |
| 2630 | |
| 2631 addstate(l, state->out, m, off, lid, match); | |
| 2632 | |
| 2633 if (REG_MULTI) | |
| 2634 { | |
| 2635 m->startpos[subidx] = save.startpos[subidx]; | |
| 2636 m->endpos[subidx] = save.endpos[subidx]; | |
| 2637 } | |
| 2638 else | |
| 2639 { | |
| 2640 m->start[subidx] = save.start[subidx]; | |
| 2641 m->end[subidx] = save.end[subidx]; | |
| 2642 } | |
| 2643 break; | |
| 2644 | |
| 2645 case NFA_MCLOSE + 0: | |
| 2646 if (nfa_has_zend == TRUE) | |
| 2647 { | |
| 2648 addstate(l, state->out, m, off, lid, match); | |
| 2649 break; | |
| 2650 } | |
| 2651 case NFA_MCLOSE + 1: | |
| 2652 case NFA_MCLOSE + 2: | |
| 2653 case NFA_MCLOSE + 3: | |
| 2654 case NFA_MCLOSE + 4: | |
| 2655 case NFA_MCLOSE + 5: | |
| 2656 case NFA_MCLOSE + 6: | |
| 2657 case NFA_MCLOSE + 7: | |
| 2658 case NFA_MCLOSE + 8: | |
| 2659 case NFA_MCLOSE + 9: | |
| 2660 case NFA_ZEND: | |
| 2661 subidx = state->c - NFA_MCLOSE; | |
| 2662 if (state->c == NFA_ZEND) | |
| 2663 subidx = 0; | |
| 2664 | |
| 2665 if (REG_MULTI) | |
| 2666 { | |
| 2667 save.startpos[subidx] = m->startpos[subidx]; | |
| 2668 save.endpos[subidx] = m->endpos[subidx]; | |
|
4515
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2669 if (off == -1) |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2670 { |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2671 m->endpos[subidx].lnum = reglnum + 1; |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2672 m->endpos[subidx].col = 0; |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2673 } |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2674 else |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2675 { |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2676 m->endpos[subidx].lnum = reglnum; |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2677 m->endpos[subidx].col = (colnr_T)(reginput - regline + off); |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
2678 } |
| 4444 | 2679 } |
| 2680 else | |
| 2681 { | |
| 2682 save.start[subidx] = m->start[subidx]; | |
| 2683 save.end[subidx] = m->end[subidx]; | |
| 2684 m->end[subidx] = reginput + off; | |
| 2685 } | |
| 2686 | |
| 2687 addstate(l, state->out, m, off, lid, match); | |
| 2688 | |
| 2689 if (REG_MULTI) | |
| 2690 { | |
| 2691 m->startpos[subidx] = save.startpos[subidx]; | |
| 2692 m->endpos[subidx] = save.endpos[subidx]; | |
| 2693 } | |
| 2694 else | |
| 2695 { | |
| 2696 m->start[subidx] = save.start[subidx]; | |
| 2697 m->end[subidx] = save.end[subidx]; | |
| 2698 } | |
| 2699 break; | |
| 2700 } | |
| 2701 } | |
| 2702 | |
| 2703 /* | |
|
4539
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2704 * Like addstate(), but the new state(s) are put at position "*ip". |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2705 * Used for zero-width matches, next state to use is the added one. |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2706 * This makes sure the order of states to be tried does not change, which |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2707 * matters for alternatives. |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2708 */ |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2709 static void |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2710 addstate_here(l, state, m, lid, matchp, ip) |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2711 nfa_list_T *l; /* runtime state list */ |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2712 nfa_state_T *state; /* state to update */ |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2713 regsub_T *m; /* pointers to subexpressions */ |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2714 int lid; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2715 int *matchp; /* found match? */ |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2716 int *ip; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2717 { |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2718 int tlen = l->n; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2719 int count; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2720 int i = *ip; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2721 |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2722 /* first add the state(s) at the end, so that we know how many there are */ |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2723 addstate(l, state, m, 0, lid, matchp); |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2724 |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2725 /* when "*ip" was at the end of the list, nothing to do */ |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2726 if (i + 1 == tlen) |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2727 return; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2728 |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2729 /* re-order to put the new state at the current position */ |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2730 count = l->n - tlen; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2731 if (count > 1) |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2732 { |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2733 /* make space for new states, then move them from the |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2734 * end to the current position */ |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2735 mch_memmove(&(l->t[i + count]), |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2736 &(l->t[i + 1]), |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2737 sizeof(nfa_thread_T) * (l->n - i - 1)); |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2738 mch_memmove(&(l->t[i]), |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2739 &(l->t[l->n - 1]), |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2740 sizeof(nfa_thread_T) * count); |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2741 } |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2742 else |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2743 { |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2744 /* overwrite the current state */ |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2745 l->t[i] = l->t[l->n - 1]; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2746 } |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2747 --l->n; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2748 *ip = i - 1; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2749 } |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2750 |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2751 /* |
| 4444 | 2752 * Check character class "class" against current character c. |
| 2753 */ | |
| 2754 static int | |
| 2755 check_char_class(class, c) | |
| 2756 int class; | |
| 2757 int c; | |
| 2758 { | |
| 2759 switch (class) | |
| 2760 { | |
| 2761 case NFA_CLASS_ALNUM: | |
| 4464 | 2762 if (c >= 1 && c <= 255 && isalnum(c)) |
| 4444 | 2763 return OK; |
| 2764 break; | |
| 2765 case NFA_CLASS_ALPHA: | |
| 4464 | 2766 if (c >= 1 && c <= 255 && isalpha(c)) |
| 4444 | 2767 return OK; |
| 2768 break; | |
| 2769 case NFA_CLASS_BLANK: | |
| 2770 if (c == ' ' || c == '\t') | |
| 2771 return OK; | |
| 2772 break; | |
| 2773 case NFA_CLASS_CNTRL: | |
| 4464 | 2774 if (c >= 1 && c <= 255 && iscntrl(c)) |
| 4444 | 2775 return OK; |
| 2776 break; | |
| 2777 case NFA_CLASS_DIGIT: | |
| 2778 if (VIM_ISDIGIT(c)) | |
| 2779 return OK; | |
| 2780 break; | |
| 2781 case NFA_CLASS_GRAPH: | |
| 4464 | 2782 if (c >= 1 && c <= 255 && isgraph(c)) |
| 4444 | 2783 return OK; |
| 2784 break; | |
| 2785 case NFA_CLASS_LOWER: | |
| 2786 if (MB_ISLOWER(c)) | |
| 2787 return OK; | |
| 2788 break; | |
| 2789 case NFA_CLASS_PRINT: | |
| 2790 if (vim_isprintc(c)) | |
| 2791 return OK; | |
| 2792 break; | |
| 2793 case NFA_CLASS_PUNCT: | |
| 4464 | 2794 if (c >= 1 && c <= 255 && ispunct(c)) |
| 4444 | 2795 return OK; |
| 2796 break; | |
| 2797 case NFA_CLASS_SPACE: | |
| 2798 if ((c >=9 && c <= 13) || (c == ' ')) | |
| 2799 return OK; | |
| 2800 break; | |
| 2801 case NFA_CLASS_UPPER: | |
| 2802 if (MB_ISUPPER(c)) | |
| 2803 return OK; | |
| 2804 break; | |
| 2805 case NFA_CLASS_XDIGIT: | |
| 2806 if (vim_isxdigit(c)) | |
| 2807 return OK; | |
| 2808 break; | |
| 2809 case NFA_CLASS_TAB: | |
| 2810 if (c == '\t') | |
| 2811 return OK; | |
| 2812 break; | |
| 2813 case NFA_CLASS_RETURN: | |
| 2814 if (c == '\r') | |
| 2815 return OK; | |
| 2816 break; | |
| 2817 case NFA_CLASS_BACKSPACE: | |
| 2818 if (c == '\b') | |
| 2819 return OK; | |
| 2820 break; | |
| 2821 case NFA_CLASS_ESCAPE: | |
| 2822 if (c == '\033') | |
| 2823 return OK; | |
| 2824 break; | |
| 2825 | |
| 2826 default: | |
| 2827 /* should not be here :P */ | |
| 2828 EMSG_RET_FAIL(_("E877: (NFA regexp) Invalid character class ")); | |
| 2829 } | |
| 2830 return FAIL; | |
| 2831 } | |
| 2832 | |
| 2833 /* | |
| 2834 * Set all NFA nodes' list ID equal to -1. | |
| 2835 */ | |
| 2836 static void | |
| 2837 nfa_set_neg_listids(start) | |
| 2838 nfa_state_T *start; | |
| 2839 { | |
| 2840 if (start == NULL) | |
| 2841 return; | |
| 2842 if (start->lastlist >= 0) | |
| 2843 { | |
| 2844 start->lastlist = -1; | |
| 2845 nfa_set_neg_listids(start->out); | |
| 2846 nfa_set_neg_listids(start->out1); | |
| 2847 } | |
| 2848 } | |
| 2849 | |
| 2850 /* | |
| 2851 * Set all NFA nodes' list ID equal to 0. | |
| 2852 */ | |
| 2853 static void | |
| 2854 nfa_set_null_listids(start) | |
| 2855 nfa_state_T *start; | |
| 2856 { | |
| 2857 if (start == NULL) | |
| 2858 return; | |
| 2859 if (start->lastlist == -1) | |
| 2860 { | |
| 2861 start->lastlist = 0; | |
| 2862 nfa_set_null_listids(start->out); | |
| 2863 nfa_set_null_listids(start->out1); | |
| 2864 } | |
| 2865 } | |
| 2866 | |
| 2867 /* | |
| 2868 * Save list IDs for all NFA states in "list". | |
| 2869 */ | |
| 2870 static void | |
| 2871 nfa_save_listids(start, list) | |
| 2872 nfa_state_T *start; | |
| 2873 int *list; | |
| 2874 { | |
| 2875 if (start == NULL) | |
| 2876 return; | |
| 2877 if (start->lastlist != -1) | |
| 2878 { | |
| 2879 list[abs(start->id)] = start->lastlist; | |
| 2880 start->lastlist = -1; | |
| 2881 nfa_save_listids(start->out, list); | |
| 2882 nfa_save_listids(start->out1, list); | |
| 2883 } | |
| 2884 } | |
| 2885 | |
| 2886 /* | |
| 2887 * Restore list IDs from "list" to all NFA states. | |
| 2888 */ | |
| 2889 static void | |
| 2890 nfa_restore_listids(start, list) | |
| 2891 nfa_state_T *start; | |
| 2892 int *list; | |
| 2893 { | |
| 2894 if (start == NULL) | |
| 2895 return; | |
| 2896 if (start->lastlist == -1) | |
| 2897 { | |
| 2898 start->lastlist = list[abs(start->id)]; | |
| 2899 nfa_restore_listids(start->out, list); | |
| 2900 nfa_restore_listids(start->out1, list); | |
| 2901 } | |
| 2902 } | |
| 2903 | |
| 2904 /* | |
| 2905 * Main matching routine. | |
| 2906 * | |
| 2907 * Run NFA to determine whether it matches reginput. | |
| 2908 * | |
| 2909 * Return TRUE if there is a match, FALSE otherwise. | |
| 2910 * Note: Caller must ensure that: start != NULL. | |
| 2911 */ | |
| 2912 static int | |
| 2913 nfa_regmatch(start, submatch, m) | |
| 2914 nfa_state_T *start; | |
| 2915 regsub_T *submatch; | |
| 2916 regsub_T *m; | |
| 2917 { | |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
2918 int c; |
| 4444 | 2919 int n; |
| 2920 int i = 0; | |
| 2921 int result; | |
| 2922 int size = 0; | |
| 2923 int match = FALSE; | |
| 2924 int flag = 0; | |
| 2925 int old_reglnum = -1; | |
|
4539
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2926 int go_to_nextline = FALSE; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2927 nfa_thread_T *t; |
| 4444 | 2928 char_u *old_reginput = NULL; |
| 2929 char_u *old_regline = NULL; | |
|
4539
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2930 nfa_list_T list[3]; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2931 nfa_list_T *listtbl[2][2]; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2932 nfa_list_T *ll; |
| 4444 | 2933 int listid = 1; |
|
4539
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2934 nfa_list_T *thislist; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2935 nfa_list_T *nextlist; |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2936 nfa_list_T *neglist; |
| 4444 | 2937 int *listids = NULL; |
| 2938 int j = 0; | |
| 4460 | 2939 #ifdef NFA_REGEXP_DEBUG_LOG |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
2940 FILE *debug = fopen(NFA_REGEXP_DEBUG_LOG, "a"); |
| 4444 | 2941 |
| 2942 if (debug == NULL) | |
| 2943 { | |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
2944 EMSG2(_("(NFA) COULD NOT OPEN %s !"), NFA_REGEXP_DEBUG_LOG); |
| 4444 | 2945 return FALSE; |
| 2946 } | |
| 2947 #endif | |
| 2948 | |
| 2949 /* Allocate memory for the lists of nodes */ | |
|
4539
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2950 size = (nstate + 1) * sizeof(nfa_thread_T); |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2951 list[0].t = (nfa_thread_T *)lalloc(size, TRUE); |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2952 list[1].t = (nfa_thread_T *)lalloc(size, TRUE); |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
2953 list[2].t = (nfa_thread_T *)lalloc(size, TRUE); |
| 4444 | 2954 if (list[0].t == NULL || list[1].t == NULL || list[2].t == NULL) |
| 2955 goto theend; | |
| 2956 vim_memset(list[0].t, 0, size); | |
| 2957 vim_memset(list[1].t, 0, size); | |
| 2958 vim_memset(list[2].t, 0, size); | |
| 2959 | |
| 2960 #ifdef ENABLE_LOG | |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
2961 log_fd = fopen(NFA_REGEXP_RUN_LOG, "a"); |
| 4444 | 2962 if (log_fd != NULL) |
| 2963 { | |
| 2964 fprintf(log_fd, "**********************************\n"); | |
| 2965 nfa_set_code(start->c); | |
| 2966 fprintf(log_fd, " RUNNING nfa_regmatch() starting with state %d, code %s\n", | |
| 2967 abs(start->id), code); | |
| 2968 fprintf(log_fd, "**********************************\n"); | |
| 2969 } | |
| 2970 else | |
| 2971 { | |
| 2972 EMSG(_("Could not open temporary log file for writing, displaying on stderr ... ")); | |
| 2973 log_fd = stderr; | |
| 2974 } | |
| 2975 #endif | |
| 2976 | |
| 2977 thislist = &list[0]; | |
| 2978 thislist->n = 0; | |
| 2979 nextlist = &list[1]; | |
| 2980 nextlist->n = 0; | |
| 2981 neglist = &list[2]; | |
| 2982 neglist->n = 0; | |
| 2983 #ifdef ENABLE_LOG | |
| 2984 fprintf(log_fd, "(---) STARTSTATE\n"); | |
| 2985 #endif | |
| 2986 addstate(thislist, start, m, 0, listid, &match); | |
| 2987 | |
| 2988 /* There are two cases when the NFA advances: 1. input char matches the | |
| 2989 * NFA node and 2. input char does not match the NFA node, but the next | |
| 2990 * node is NFA_NOT. The following macro calls addstate() according to | |
| 2991 * these rules. It is used A LOT, so use the "listtbl" table for speed */ | |
| 2992 listtbl[0][0] = NULL; | |
| 2993 listtbl[0][1] = neglist; | |
| 2994 listtbl[1][0] = nextlist; | |
| 2995 listtbl[1][1] = NULL; | |
| 2996 #define ADD_POS_NEG_STATE(node) \ | |
| 2997 ll = listtbl[result ? 1 : 0][node->negated]; \ | |
| 2998 if (ll != NULL) \ | |
| 2999 addstate(ll, node->out , &t->sub, n, listid + 1, &match); | |
| 3000 | |
| 3001 | |
| 3002 /* | |
| 3003 * Run for each character. | |
| 3004 */ | |
|
4515
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3005 for (;;) |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3006 { |
| 4444 | 3007 #ifdef FEAT_MBYTE |
| 3008 if (has_mbyte) | |
| 3009 { | |
| 3010 c = (*mb_ptr2char)(reginput); | |
| 3011 n = (*mb_ptr2len)(reginput); | |
| 3012 } | |
| 3013 else | |
| 3014 #endif | |
| 3015 { | |
| 3016 c = *reginput; | |
| 3017 n = 1; | |
| 3018 } | |
| 3019 if (c == NUL) | |
|
4515
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3020 { |
| 4444 | 3021 n = 0; |
|
4515
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3022 go_to_nextline = FALSE; |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3023 } |
| 4444 | 3024 |
| 3025 /* swap lists */ | |
| 3026 thislist = &list[flag]; | |
| 3027 nextlist = &list[flag ^= 1]; | |
| 3028 nextlist->n = 0; /* `clear' nextlist */ | |
| 3029 listtbl[1][0] = nextlist; | |
| 3030 ++listid; | |
| 3031 | |
| 3032 #ifdef ENABLE_LOG | |
| 3033 fprintf(log_fd, "------------------------------------------\n"); | |
| 3034 fprintf(log_fd, ">>> Reginput is \"%s\"\n", reginput); | |
| 3035 fprintf(log_fd, ">>> Advanced one character ... Current char is %c (code %d) \n", c, (int)c); | |
| 3036 fprintf(log_fd, ">>> Thislist has %d states available: ", thislist->n); | |
|
4537
5cc98a5898cf
updated for version 7.3.1016
Bram Moolenaar <bram@vim.org>
parents:
4535
diff
changeset
|
3037 for (i = 0; i < thislist->n; i++) |
| 4444 | 3038 fprintf(log_fd, "%d ", abs(thislist->t[i].state->id)); |
| 3039 fprintf(log_fd, "\n"); | |
| 3040 #endif | |
| 3041 | |
| 4460 | 3042 #ifdef NFA_REGEXP_DEBUG_LOG |
| 4444 | 3043 fprintf(debug, "\n-------------------\n"); |
| 3044 #endif | |
| 4480 | 3045 /* |
| 3046 * If the state lists are empty we can stop. | |
| 3047 */ | |
| 3048 if (thislist->n == 0 && neglist->n == 0) | |
| 3049 break; | |
| 4444 | 3050 |
| 3051 /* compute nextlist */ | |
| 3052 for (i = 0; i < thislist->n || neglist->n > 0; ++i) | |
| 3053 { | |
| 3054 if (neglist->n > 0) | |
| 3055 { | |
| 3056 t = &neglist->t[0]; | |
| 4468 | 3057 neglist->n--; |
| 4444 | 3058 i--; |
| 3059 } | |
| 3060 else | |
| 3061 t = &thislist->t[i]; | |
| 3062 | |
| 4460 | 3063 #ifdef NFA_REGEXP_DEBUG_LOG |
| 4444 | 3064 nfa_set_code(t->state->c); |
| 3065 fprintf(debug, "%s, ", code); | |
| 3066 #endif | |
| 3067 #ifdef ENABLE_LOG | |
| 3068 nfa_set_code(t->state->c); | |
| 3069 fprintf(log_fd, "(%d) %s, code %d ... \n", abs(t->state->id), | |
| 3070 code, (int)t->state->c); | |
| 3071 #endif | |
| 3072 | |
| 3073 /* | |
| 3074 * Handle the possible codes of the current state. | |
| 3075 * The most important is NFA_MATCH. | |
| 3076 */ | |
| 3077 switch (t->state->c) | |
| 3078 { | |
| 3079 case NFA_MATCH: | |
| 3080 match = TRUE; | |
| 3081 *submatch = t->sub; | |
| 3082 #ifdef ENABLE_LOG | |
| 3083 for (j = 0; j < 4; j++) | |
| 3084 if (REG_MULTI) | |
| 3085 fprintf(log_fd, "\n *** group %d, start: c=%d, l=%d, end: c=%d, l=%d", | |
| 3086 j, | |
| 3087 t->sub.startpos[j].col, | |
| 3088 (int)t->sub.startpos[j].lnum, | |
| 3089 t->sub.endpos[j].col, | |
| 3090 (int)t->sub.endpos[j].lnum); | |
| 3091 else | |
| 3092 fprintf(log_fd, "\n *** group %d, start: \"%s\", end: \"%s\"", | |
| 3093 j, | |
| 3094 (char *)t->sub.start[j], | |
| 3095 (char *)t->sub.end[j]); | |
| 3096 fprintf(log_fd, "\n"); | |
| 3097 #endif | |
|
4515
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3098 /* Found the left-most longest match, do not look at any other |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3099 * states at this position. */ |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3100 goto nextchar; |
| 4444 | 3101 |
| 3102 case NFA_END_INVISIBLE: | |
| 3103 /* This is only encountered after a NFA_START_INVISIBLE node. | |
| 3104 * They surround a zero-width group, used with "\@=" and "\&". | |
| 3105 * If we got here, it means that the current "invisible" group | |
| 3106 * finished successfully, so return control to the parent | |
| 3107 * nfa_regmatch(). Submatches are stored in *m, and used in | |
| 3108 * the parent call. */ | |
| 3109 if (start->c == NFA_MOPEN + 0) | |
|
4539
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
3110 addstate_here(thislist, t->state->out, &t->sub, listid, |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
3111 &match, &i); |
| 4444 | 3112 else |
| 3113 { | |
| 3114 *m = t->sub; | |
| 3115 match = TRUE; | |
| 3116 } | |
| 3117 break; | |
| 3118 | |
| 3119 case NFA_START_INVISIBLE: | |
| 3120 /* Save global variables, and call nfa_regmatch() to check if | |
| 3121 * the current concat matches at this position. The concat | |
| 3122 * ends with the node NFA_END_INVISIBLE */ | |
| 3123 old_reginput = reginput; | |
| 3124 old_regline = regline; | |
| 3125 old_reglnum = reglnum; | |
| 3126 if (listids == NULL) | |
| 3127 { | |
| 3128 listids = (int *) lalloc(sizeof(int) * nstate, TRUE); | |
| 3129 if (listids == NULL) | |
| 3130 { | |
| 3131 EMSG(_("E878: (NFA) Could not allocate memory for branch traversal!")); | |
| 3132 return 0; | |
| 3133 } | |
| 3134 } | |
| 3135 #ifdef ENABLE_LOG | |
| 3136 if (log_fd != stderr) | |
| 3137 fclose(log_fd); | |
| 3138 log_fd = NULL; | |
| 3139 #endif | |
| 3140 /* Have to clear the listid field of the NFA nodes, so that | |
| 3141 * nfa_regmatch() and addstate() can run properly after | |
| 3142 * recursion. */ | |
| 3143 nfa_save_listids(start, listids); | |
| 3144 nfa_set_null_listids(start); | |
| 3145 result = nfa_regmatch(t->state->out, submatch, m); | |
| 3146 nfa_set_neg_listids(start); | |
| 3147 nfa_restore_listids(start, listids); | |
| 3148 | |
| 3149 #ifdef ENABLE_LOG | |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
3150 log_fd = fopen(NFA_REGEXP_RUN_LOG, "a"); |
| 4444 | 3151 if (log_fd != NULL) |
| 3152 { | |
| 3153 fprintf(log_fd, "****************************\n"); | |
| 3154 fprintf(log_fd, "FINISHED RUNNING nfa_regmatch() recursively\n"); | |
| 3155 fprintf(log_fd, "MATCH = %s\n", result == TRUE ? "OK" : "FALSE"); | |
| 3156 fprintf(log_fd, "****************************\n"); | |
| 3157 } | |
| 3158 else | |
| 3159 { | |
| 3160 EMSG(_("Could not open temporary log file for writing, displaying on stderr ... ")); | |
| 3161 log_fd = stderr; | |
| 3162 } | |
| 3163 #endif | |
| 3164 if (result == TRUE) | |
| 3165 { | |
| 3166 /* Restore position in input text */ | |
| 3167 reginput = old_reginput; | |
| 3168 regline = old_regline; | |
| 3169 reglnum = old_reglnum; | |
| 3170 /* Copy submatch info from the recursive call */ | |
| 3171 if (REG_MULTI) | |
| 3172 for (j = 1; j < NSUBEXP; j++) | |
| 3173 { | |
| 3174 t->sub.startpos[j] = m->startpos[j]; | |
| 3175 t->sub.endpos[j] = m->endpos[j]; | |
| 3176 } | |
| 3177 else | |
| 3178 for (j = 1; j < NSUBEXP; j++) | |
| 3179 { | |
| 3180 t->sub.start[j] = m->start[j]; | |
| 3181 t->sub.end[j] = m->end[j]; | |
| 3182 } | |
| 3183 /* t->state->out1 is the corresponding END_INVISIBLE node */ | |
|
4539
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
3184 addstate_here(thislist, t->state->out1->out, &t->sub, |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
3185 listid, &match, &i); |
| 4444 | 3186 } |
| 3187 else | |
| 3188 { | |
| 3189 /* continue with next input char */ | |
| 3190 reginput = old_reginput; | |
| 3191 } | |
| 3192 break; | |
| 3193 | |
| 3194 case NFA_BOL: | |
| 3195 if (reginput == regline) | |
|
4539
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
3196 addstate_here(thislist, t->state->out, &t->sub, listid, |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
3197 &match, &i); |
| 4444 | 3198 break; |
| 3199 | |
| 3200 case NFA_EOL: | |
| 3201 if (c == NUL) | |
|
4539
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
3202 addstate_here(thislist, t->state->out, &t->sub, listid, |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
3203 &match, &i); |
| 4444 | 3204 break; |
| 3205 | |
| 3206 case NFA_BOW: | |
| 3207 { | |
| 3208 int bow = TRUE; | |
| 3209 | |
| 3210 if (c == NUL) | |
| 3211 bow = FALSE; | |
| 3212 #ifdef FEAT_MBYTE | |
| 3213 else if (has_mbyte) | |
| 3214 { | |
| 3215 int this_class; | |
| 3216 | |
| 3217 /* Get class of current and previous char (if it exists). */ | |
| 4503 | 3218 this_class = mb_get_class_buf(reginput, reg_buf); |
| 4444 | 3219 if (this_class <= 1) |
| 3220 bow = FALSE; | |
| 3221 else if (reg_prev_class() == this_class) | |
| 3222 bow = FALSE; | |
| 3223 } | |
| 3224 #endif | |
| 4503 | 3225 else if (!vim_iswordc_buf(c, reg_buf) |
| 3226 || (reginput > regline | |
| 3227 && vim_iswordc_buf(reginput[-1], reg_buf))) | |
| 4444 | 3228 bow = FALSE; |
| 3229 if (bow) | |
|
4539
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
3230 addstate_here(thislist, t->state->out, &t->sub, listid, |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
3231 &match, &i); |
| 4444 | 3232 break; |
| 3233 } | |
| 3234 | |
| 3235 case NFA_EOW: | |
| 3236 { | |
| 3237 int eow = TRUE; | |
| 3238 | |
| 3239 if (reginput == regline) | |
| 3240 eow = FALSE; | |
| 3241 #ifdef FEAT_MBYTE | |
| 3242 else if (has_mbyte) | |
| 3243 { | |
| 3244 int this_class, prev_class; | |
| 3245 | |
| 3246 /* Get class of current and previous char (if it exists). */ | |
| 4503 | 3247 this_class = mb_get_class_buf(reginput, reg_buf); |
| 4444 | 3248 prev_class = reg_prev_class(); |
| 3249 if (this_class == prev_class | |
| 3250 || prev_class == 0 || prev_class == 1) | |
| 3251 eow = FALSE; | |
| 3252 } | |
| 3253 #endif | |
| 4503 | 3254 else if (!vim_iswordc_buf(reginput[-1], reg_buf) |
| 3255 || (reginput[0] != NUL && vim_iswordc_buf(c, reg_buf))) | |
| 4444 | 3256 eow = FALSE; |
| 3257 if (eow) | |
|
4539
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
3258 addstate_here(thislist, t->state->out, &t->sub, listid, |
|
532c2e850256
updated for version 7.3.1017
Bram Moolenaar <bram@vim.org>
parents:
4537
diff
changeset
|
3259 &match, &i); |
| 4444 | 3260 break; |
| 3261 } | |
| 3262 | |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
3263 #ifdef FEAT_MBYTE |
| 4444 | 3264 case NFA_COMPOSING: |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
3265 { |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
3266 int mc = c; |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
3267 int len = 0; |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
3268 nfa_state_T *end; |
|
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
3269 nfa_state_T *sta; |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
3270 |
| 4444 | 3271 result = OK; |
| 3272 sta = t->state->out; | |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
3273 len = 0; |
|
4535
45f97c349537
updated for version 7.3.1015
Bram Moolenaar <bram@vim.org>
parents:
4533
diff
changeset
|
3274 if (utf_iscomposing(sta->c)) |
|
45f97c349537
updated for version 7.3.1015
Bram Moolenaar <bram@vim.org>
parents:
4533
diff
changeset
|
3275 { |
|
45f97c349537
updated for version 7.3.1015
Bram Moolenaar <bram@vim.org>
parents:
4533
diff
changeset
|
3276 /* Only match composing character(s), ignore base |
|
45f97c349537
updated for version 7.3.1015
Bram Moolenaar <bram@vim.org>
parents:
4533
diff
changeset
|
3277 * character. Used for ".{composing}" and "{composing}" |
|
45f97c349537
updated for version 7.3.1015
Bram Moolenaar <bram@vim.org>
parents:
4533
diff
changeset
|
3278 * (no preceding character). */ |
|
45f97c349537
updated for version 7.3.1015
Bram Moolenaar <bram@vim.org>
parents:
4533
diff
changeset
|
3279 len += mb_char2len(c); |
|
45f97c349537
updated for version 7.3.1015
Bram Moolenaar <bram@vim.org>
parents:
4533
diff
changeset
|
3280 } |
|
4529
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
3281 if (ireg_icombine) |
| 4444 | 3282 { |
|
4535
45f97c349537
updated for version 7.3.1015
Bram Moolenaar <bram@vim.org>
parents:
4533
diff
changeset
|
3283 /* If \Z was present, then ignore composing characters. |
|
45f97c349537
updated for version 7.3.1015
Bram Moolenaar <bram@vim.org>
parents:
4533
diff
changeset
|
3284 * When ignoring the base character this always matches. */ |
|
4529
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
3285 /* TODO: How about negated? */ |
|
4535
45f97c349537
updated for version 7.3.1015
Bram Moolenaar <bram@vim.org>
parents:
4533
diff
changeset
|
3286 if (len == 0 && sta->c != c) |
|
4529
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
3287 result = FAIL; |
|
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
3288 len = n; |
|
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
3289 while (sta->c != NFA_END_COMPOSING) |
|
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
3290 sta = sta->out; |
| 4444 | 3291 } |
|
4529
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
3292 else |
|
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
3293 while (sta->c != NFA_END_COMPOSING && len < n) |
|
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
3294 { |
|
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
3295 if (len > 0) |
|
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
3296 mc = mb_ptr2char(reginput + len); |
|
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
3297 if (mc != sta->c) |
|
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
3298 break; |
|
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
3299 len += mb_char2len(mc); |
|
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
3300 sta = sta->out; |
|
432a6b8c7d93
updated for version 7.3.1012
Bram Moolenaar <bram@vim.org>
parents:
4527
diff
changeset
|
3301 } |
| 4444 | 3302 |
| 3303 /* if input char length doesn't match regexp char length */ | |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
3304 if (len < n || sta->c != NFA_END_COMPOSING) |
|
4525
36ddcf4cecbc
updated for version 7.3.1010
Bram Moolenaar <bram@vim.org>
parents:
4517
diff
changeset
|
3305 result = FAIL; |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
3306 end = t->state->out1; /* NFA_END_COMPOSING */ |
| 4444 | 3307 ADD_POS_NEG_STATE(end); |
| 3308 break; | |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
3309 } |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
3310 #endif |
| 4444 | 3311 |
| 3312 case NFA_NEWL: | |
| 3313 if (!reg_line_lbr && REG_MULTI | |
|
4515
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3314 && c == NUL && reglnum <= reg_maxline) |
| 4444 | 3315 { |
|
4515
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3316 go_to_nextline = TRUE; |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3317 /* Pass -1 for the offset, which means taking the position |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3318 * at the start of the next line. */ |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3319 addstate(nextlist, t->state->out, &t->sub, -1, |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3320 listid + 1, &match); |
| 4444 | 3321 } |
| 3322 break; | |
| 3323 | |
| 3324 case NFA_CLASS_ALNUM: | |
| 3325 case NFA_CLASS_ALPHA: | |
| 3326 case NFA_CLASS_BLANK: | |
| 3327 case NFA_CLASS_CNTRL: | |
| 3328 case NFA_CLASS_DIGIT: | |
| 3329 case NFA_CLASS_GRAPH: | |
| 3330 case NFA_CLASS_LOWER: | |
| 3331 case NFA_CLASS_PRINT: | |
| 3332 case NFA_CLASS_PUNCT: | |
| 3333 case NFA_CLASS_SPACE: | |
| 3334 case NFA_CLASS_UPPER: | |
| 3335 case NFA_CLASS_XDIGIT: | |
| 3336 case NFA_CLASS_TAB: | |
| 3337 case NFA_CLASS_RETURN: | |
| 3338 case NFA_CLASS_BACKSPACE: | |
| 3339 case NFA_CLASS_ESCAPE: | |
| 3340 result = check_char_class(t->state->c, c); | |
| 3341 ADD_POS_NEG_STATE(t->state); | |
| 3342 break; | |
| 3343 | |
| 3344 case NFA_END_NEG_RANGE: | |
| 3345 /* This follows a series of negated nodes, like: | |
| 3346 * CHAR(x), NFA_NOT, CHAR(y), NFA_NOT etc. */ | |
| 3347 if (c > 0) | |
| 3348 addstate(nextlist, t->state->out, &t->sub, n, listid + 1, | |
| 3349 &match); | |
| 3350 break; | |
| 3351 | |
| 3352 case NFA_ANY: | |
|
4515
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3353 /* Any char except '\0', (end of input) does not match. */ |
| 4444 | 3354 if (c > 0) |
| 3355 addstate(nextlist, t->state->out, &t->sub, n, listid + 1, | |
| 3356 &match); | |
| 3357 break; | |
| 3358 | |
| 3359 /* | |
| 3360 * Character classes like \a for alpha, \d for digit etc. | |
| 3361 */ | |
| 3362 case NFA_IDENT: /* \i */ | |
| 3363 result = vim_isIDc(c); | |
| 3364 ADD_POS_NEG_STATE(t->state); | |
| 3365 break; | |
| 3366 | |
| 3367 case NFA_SIDENT: /* \I */ | |
| 3368 result = !VIM_ISDIGIT(c) && vim_isIDc(c); | |
| 3369 ADD_POS_NEG_STATE(t->state); | |
| 3370 break; | |
| 3371 | |
| 3372 case NFA_KWORD: /* \k */ | |
| 4503 | 3373 result = vim_iswordp_buf(reginput, reg_buf); |
| 4444 | 3374 ADD_POS_NEG_STATE(t->state); |
| 3375 break; | |
| 3376 | |
| 3377 case NFA_SKWORD: /* \K */ | |
| 4503 | 3378 result = !VIM_ISDIGIT(c) && vim_iswordp_buf(reginput, reg_buf); |
| 4444 | 3379 ADD_POS_NEG_STATE(t->state); |
| 3380 break; | |
| 3381 | |
| 3382 case NFA_FNAME: /* \f */ | |
| 3383 result = vim_isfilec(c); | |
| 3384 ADD_POS_NEG_STATE(t->state); | |
| 3385 break; | |
| 3386 | |
| 3387 case NFA_SFNAME: /* \F */ | |
| 3388 result = !VIM_ISDIGIT(c) && vim_isfilec(c); | |
| 3389 ADD_POS_NEG_STATE(t->state); | |
| 3390 break; | |
| 3391 | |
| 3392 case NFA_PRINT: /* \p */ | |
| 4470 | 3393 result = ptr2cells(reginput) == 1; |
| 4444 | 3394 ADD_POS_NEG_STATE(t->state); |
| 3395 break; | |
| 3396 | |
| 3397 case NFA_SPRINT: /* \P */ | |
| 4470 | 3398 result = !VIM_ISDIGIT(c) && ptr2cells(reginput) == 1; |
| 4444 | 3399 ADD_POS_NEG_STATE(t->state); |
| 3400 break; | |
| 3401 | |
| 3402 case NFA_WHITE: /* \s */ | |
| 3403 result = vim_iswhite(c); | |
| 3404 ADD_POS_NEG_STATE(t->state); | |
| 3405 break; | |
| 3406 | |
| 3407 case NFA_NWHITE: /* \S */ | |
| 3408 result = c != NUL && !vim_iswhite(c); | |
| 3409 ADD_POS_NEG_STATE(t->state); | |
| 3410 break; | |
| 3411 | |
| 3412 case NFA_DIGIT: /* \d */ | |
| 3413 result = ri_digit(c); | |
| 3414 ADD_POS_NEG_STATE(t->state); | |
| 3415 break; | |
| 3416 | |
| 3417 case NFA_NDIGIT: /* \D */ | |
| 3418 result = c != NUL && !ri_digit(c); | |
| 3419 ADD_POS_NEG_STATE(t->state); | |
| 3420 break; | |
| 3421 | |
| 3422 case NFA_HEX: /* \x */ | |
| 3423 result = ri_hex(c); | |
| 3424 ADD_POS_NEG_STATE(t->state); | |
| 3425 break; | |
| 3426 | |
| 3427 case NFA_NHEX: /* \X */ | |
| 3428 result = c != NUL && !ri_hex(c); | |
| 3429 ADD_POS_NEG_STATE(t->state); | |
| 3430 break; | |
| 3431 | |
| 3432 case NFA_OCTAL: /* \o */ | |
| 3433 result = ri_octal(c); | |
| 3434 ADD_POS_NEG_STATE(t->state); | |
| 3435 break; | |
| 3436 | |
| 3437 case NFA_NOCTAL: /* \O */ | |
| 3438 result = c != NUL && !ri_octal(c); | |
| 3439 ADD_POS_NEG_STATE(t->state); | |
| 3440 break; | |
| 3441 | |
| 3442 case NFA_WORD: /* \w */ | |
| 3443 result = ri_word(c); | |
| 3444 ADD_POS_NEG_STATE(t->state); | |
| 3445 break; | |
| 3446 | |
| 3447 case NFA_NWORD: /* \W */ | |
| 3448 result = c != NUL && !ri_word(c); | |
| 3449 ADD_POS_NEG_STATE(t->state); | |
| 3450 break; | |
| 3451 | |
| 3452 case NFA_HEAD: /* \h */ | |
| 3453 result = ri_head(c); | |
| 3454 ADD_POS_NEG_STATE(t->state); | |
| 3455 break; | |
| 3456 | |
| 3457 case NFA_NHEAD: /* \H */ | |
| 3458 result = c != NUL && !ri_head(c); | |
| 3459 ADD_POS_NEG_STATE(t->state); | |
| 3460 break; | |
| 3461 | |
| 3462 case NFA_ALPHA: /* \a */ | |
| 3463 result = ri_alpha(c); | |
| 3464 ADD_POS_NEG_STATE(t->state); | |
| 3465 break; | |
| 3466 | |
| 3467 case NFA_NALPHA: /* \A */ | |
| 3468 result = c != NUL && !ri_alpha(c); | |
| 3469 ADD_POS_NEG_STATE(t->state); | |
| 3470 break; | |
| 3471 | |
| 3472 case NFA_LOWER: /* \l */ | |
| 3473 result = ri_lower(c); | |
| 3474 ADD_POS_NEG_STATE(t->state); | |
| 3475 break; | |
| 3476 | |
| 3477 case NFA_NLOWER: /* \L */ | |
| 3478 result = c != NUL && !ri_lower(c); | |
| 3479 ADD_POS_NEG_STATE(t->state); | |
| 3480 break; | |
| 3481 | |
| 3482 case NFA_UPPER: /* \u */ | |
| 3483 result = ri_upper(c); | |
| 3484 ADD_POS_NEG_STATE(t->state); | |
| 3485 break; | |
| 3486 | |
| 3487 case NFA_NUPPER: /* \U */ | |
| 3488 result = c != NUL && !ri_upper(c); | |
| 3489 ADD_POS_NEG_STATE(t->state); | |
| 3490 break; | |
| 3491 | |
| 4482 | 3492 case NFA_MOPEN + 0: |
| 3493 case NFA_MOPEN + 1: | |
| 3494 case NFA_MOPEN + 2: | |
| 3495 case NFA_MOPEN + 3: | |
| 3496 case NFA_MOPEN + 4: | |
| 3497 case NFA_MOPEN + 5: | |
| 3498 case NFA_MOPEN + 6: | |
| 3499 case NFA_MOPEN + 7: | |
| 3500 case NFA_MOPEN + 8: | |
| 3501 case NFA_MOPEN + 9: | |
| 3502 /* handled below */ | |
| 3503 break; | |
| 3504 | |
| 3505 case NFA_SKIP_CHAR: | |
| 3506 case NFA_ZSTART: | |
| 3507 /* TODO: should not happen? */ | |
| 3508 break; | |
| 3509 | |
| 4444 | 3510 default: /* regular character */ |
| 4482 | 3511 /* TODO: put this in #ifdef later */ |
| 3512 if (t->state->c < -256) | |
| 3513 EMSGN("INTERNAL: Negative state char: %ld", t->state->c); | |
| 4444 | 3514 result = (no_Magic(t->state->c) == c); |
| 4482 | 3515 |
| 4444 | 3516 if (!result) |
| 3517 result = ireg_ic == TRUE | |
| 3518 && MB_TOLOWER(t->state->c) == MB_TOLOWER(c); | |
|
4527
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
3519 #ifdef FEAT_MBYTE |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
3520 /* If there is a composing character which is not being |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
3521 * ignored there can be no match. Match with composing |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
3522 * character uses NFA_COMPOSING above. */ |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
3523 if (result && enc_utf8 && !ireg_icombine |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
3524 && n != utf_char2len(c)) |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
3525 result = FALSE; |
|
55bcaa1d2749
updated for version 7.3.1011
Bram Moolenaar <bram@vim.org>
parents:
4525
diff
changeset
|
3526 #endif |
| 4444 | 3527 ADD_POS_NEG_STATE(t->state); |
| 3528 break; | |
| 3529 } | |
| 3530 | |
| 3531 } /* for (thislist = thislist; thislist->state; thislist++) */ | |
| 3532 | |
| 3533 /* The first found match is the leftmost one, but there may be a | |
| 3534 * longer one. Keep running the NFA, but don't start from the | |
| 3535 * beginning. Also, do not add the start state in recursive calls of | |
| 3536 * nfa_regmatch(), because recursive calls should only start in the | |
| 3537 * first position. */ | |
| 3538 if (match == FALSE && start->c == NFA_MOPEN + 0) | |
| 3539 { | |
| 3540 #ifdef ENABLE_LOG | |
| 3541 fprintf(log_fd, "(---) STARTSTATE\n"); | |
| 3542 #endif | |
| 3543 addstate(nextlist, start, m, n, listid + 1, &match); | |
| 3544 } | |
| 3545 | |
| 3546 #ifdef ENABLE_LOG | |
| 3547 fprintf(log_fd, ">>> Thislist had %d states available: ", thislist->n); | |
| 3548 for (i = 0; i< thislist->n; i++) | |
| 3549 fprintf(log_fd, "%d ", abs(thislist->t[i].state->id)); | |
| 3550 fprintf(log_fd, "\n"); | |
| 3551 #endif | |
| 3552 | |
| 3553 nextchar: | |
|
4515
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3554 /* Advance to the next character, or advance to the next line, or |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3555 * finish. */ |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3556 if (n != 0) |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3557 reginput += n; |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3558 else if (go_to_nextline) |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3559 reg_nextline(); |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3560 else |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3561 break; |
|
90e9917d4114
updated for version 7.3.1005
Bram Moolenaar <bram@vim.org>
parents:
4507
diff
changeset
|
3562 } |
| 4444 | 3563 |
| 3564 #ifdef ENABLE_LOG | |
| 3565 if (log_fd != stderr) | |
| 3566 fclose(log_fd); | |
| 3567 log_fd = NULL; | |
| 3568 #endif | |
| 3569 | |
| 3570 theend: | |
| 3571 /* Free memory */ | |
| 3572 vim_free(list[0].t); | |
| 3573 vim_free(list[1].t); | |
| 3574 vim_free(list[2].t); | |
| 3575 list[0].t = list[1].t = list[2].t = NULL; | |
| 3576 if (listids != NULL) | |
| 3577 vim_free(listids); | |
| 3578 #undef ADD_POS_NEG_STATE | |
| 4460 | 3579 #ifdef NFA_REGEXP_DEBUG_LOG |
| 4444 | 3580 fclose(debug); |
| 3581 #endif | |
| 3582 | |
| 3583 return match; | |
| 3584 } | |
| 3585 | |
| 3586 /* | |
| 3587 * Try match of "prog" with at regline["col"]. | |
| 3588 * Returns 0 for failure, number of lines contained in the match otherwise. | |
| 3589 */ | |
| 3590 static long | |
| 3591 nfa_regtry(start, col) | |
| 3592 nfa_state_T *start; | |
| 3593 colnr_T col; | |
| 3594 { | |
| 3595 int i; | |
| 3596 regsub_T sub, m; | |
| 3597 #ifdef ENABLE_LOG | |
| 3598 FILE *f; | |
| 3599 #endif | |
| 3600 | |
| 3601 reginput = regline + col; | |
| 3602 need_clear_subexpr = TRUE; | |
| 3603 | |
| 3604 #ifdef ENABLE_LOG | |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
3605 f = fopen(NFA_REGEXP_RUN_LOG, "a"); |
| 4444 | 3606 if (f != NULL) |
| 3607 { | |
| 3608 fprintf(f, "\n\n\n\n\n\n\t\t=======================================================\n"); | |
| 3609 fprintf(f, " =======================================================\n"); | |
| 3610 #ifdef DEBUG | |
| 3611 fprintf(f, "\tRegexp is \"%s\"\n", nfa_regengine.expr); | |
| 3612 #endif | |
| 3613 fprintf(f, "\tInput text is \"%s\" \n", reginput); | |
| 3614 fprintf(f, " =======================================================\n\n\n\n\n\n\n"); | |
|
4533
6a2005efa02b
updated for version 7.3.1014
Bram Moolenaar <bram@vim.org>
parents:
4531
diff
changeset
|
3615 nfa_print_state(f, start); |
| 4444 | 3616 fprintf(f, "\n\n"); |
| 3617 fclose(f); | |
| 3618 } | |
| 3619 else | |
| 3620 EMSG(_("Could not open temporary log file for writing ")); | |
| 3621 #endif | |
| 3622 | |
| 3623 if (REG_MULTI) | |
| 3624 { | |
| 3625 /* Use 0xff to set lnum to -1 */ | |
| 3626 vim_memset(sub.startpos, 0xff, sizeof(lpos_T) * NSUBEXP); | |
| 3627 vim_memset(sub.endpos, 0xff, sizeof(lpos_T) * NSUBEXP); | |
| 3628 vim_memset(m.startpos, 0xff, sizeof(lpos_T) * NSUBEXP); | |
| 3629 vim_memset(m.endpos, 0xff, sizeof(lpos_T) * NSUBEXP); | |
| 3630 } | |
| 3631 else | |
| 3632 { | |
| 3633 vim_memset(sub.start, 0, sizeof(char_u *) * NSUBEXP); | |
| 3634 vim_memset(sub.end, 0, sizeof(char_u *) * NSUBEXP); | |
| 3635 vim_memset(m.start, 0, sizeof(char_u *) * NSUBEXP); | |
| 3636 vim_memset(m.end, 0, sizeof(char_u *) * NSUBEXP); | |
| 3637 } | |
| 3638 | |
| 3639 if (nfa_regmatch(start, &sub, &m) == FALSE) | |
| 3640 return 0; | |
| 3641 | |
| 3642 cleanup_subexpr(); | |
| 3643 if (REG_MULTI) | |
| 3644 { | |
| 3645 for (i = 0; i < NSUBEXP; i++) | |
| 3646 { | |
| 3647 reg_startpos[i] = sub.startpos[i]; | |
| 3648 reg_endpos[i] = sub.endpos[i]; | |
| 3649 } | |
| 3650 | |
| 3651 if (reg_startpos[0].lnum < 0) | |
| 3652 { | |
| 3653 reg_startpos[0].lnum = 0; | |
| 3654 reg_startpos[0].col = col; | |
| 3655 } | |
| 3656 if (reg_endpos[0].lnum < 0) | |
| 3657 { | |
| 3658 reg_endpos[0].lnum = reglnum; | |
| 3659 reg_endpos[0].col = (int)(reginput - regline); | |
| 3660 } | |
| 3661 else | |
| 3662 /* Use line number of "\ze". */ | |
| 3663 reglnum = reg_endpos[0].lnum; | |
| 3664 } | |
| 3665 else | |
| 3666 { | |
| 3667 for (i = 0; i < NSUBEXP; i++) | |
| 3668 { | |
| 3669 reg_startp[i] = sub.start[i]; | |
| 3670 reg_endp[i] = sub.end[i]; | |
| 3671 } | |
| 3672 | |
| 3673 if (reg_startp[0] == NULL) | |
| 3674 reg_startp[0] = regline + col; | |
| 3675 if (reg_endp[0] == NULL) | |
| 3676 reg_endp[0] = reginput; | |
| 3677 } | |
| 3678 | |
| 3679 return 1 + reglnum; | |
| 3680 } | |
| 3681 | |
| 3682 /* | |
| 3683 * Match a regexp against a string ("line" points to the string) or multiple | |
| 3684 * lines ("line" is NULL, use reg_getline()). | |
| 3685 * | |
| 3686 * Returns 0 for failure, number of lines contained in the match otherwise. | |
| 3687 */ | |
| 3688 static long | |
| 3689 nfa_regexec_both(line, col) | |
| 3690 char_u *line; | |
| 3691 colnr_T col; /* column to start looking for match */ | |
| 3692 { | |
| 3693 nfa_regprog_T *prog; | |
| 3694 long retval = 0L; | |
| 3695 int i; | |
| 3696 | |
| 3697 if (REG_MULTI) | |
| 3698 { | |
| 3699 prog = (nfa_regprog_T *)reg_mmatch->regprog; | |
| 3700 line = reg_getline((linenr_T)0); /* relative to the cursor */ | |
| 3701 reg_startpos = reg_mmatch->startpos; | |
| 3702 reg_endpos = reg_mmatch->endpos; | |
| 3703 } | |
| 3704 else | |
| 3705 { | |
| 3706 prog = (nfa_regprog_T *)reg_match->regprog; | |
| 3707 reg_startp = reg_match->startp; | |
| 3708 reg_endp = reg_match->endp; | |
| 3709 } | |
| 3710 | |
| 3711 /* Be paranoid... */ | |
| 3712 if (prog == NULL || line == NULL) | |
| 3713 { | |
| 3714 EMSG(_(e_null)); | |
| 3715 goto theend; | |
| 3716 } | |
| 3717 | |
| 3718 /* If the start column is past the maximum column: no need to try. */ | |
| 3719 if (ireg_maxcol > 0 && col >= ireg_maxcol) | |
| 3720 goto theend; | |
| 3721 | |
| 3722 /* If pattern contains "\c" or "\C": overrule value of ireg_ic */ | |
| 3723 if (prog->regflags & RF_ICASE) | |
| 3724 ireg_ic = TRUE; | |
| 3725 else if (prog->regflags & RF_NOICASE) | |
| 3726 ireg_ic = FALSE; | |
| 3727 | |
| 3728 #ifdef FEAT_MBYTE | |
| 3729 /* If pattern contains "\Z" overrule value of ireg_icombine */ | |
| 3730 if (prog->regflags & RF_ICOMBINE) | |
| 3731 ireg_icombine = TRUE; | |
| 3732 #endif | |
| 3733 | |
| 3734 regline = line; | |
| 3735 reglnum = 0; /* relative to line */ | |
| 3736 | |
| 3737 nstate = prog->nstate; | |
| 3738 | |
| 3739 for (i = 0; i < nstate; ++i) | |
| 3740 { | |
| 3741 prog->state[i].id = i; | |
| 3742 prog->state[i].lastlist = 0; | |
| 3743 prog->state[i].visits = 0; | |
| 3744 } | |
| 3745 | |
| 3746 retval = nfa_regtry(prog->start, col); | |
| 3747 | |
| 3748 theend: | |
| 3749 return retval; | |
| 3750 } | |
| 3751 | |
| 3752 /* | |
| 3753 * Compile a regular expression into internal code for the NFA matcher. | |
| 3754 * Returns the program in allocated space. Returns NULL for an error. | |
| 3755 */ | |
| 3756 static regprog_T * | |
| 3757 nfa_regcomp(expr, re_flags) | |
| 3758 char_u *expr; | |
| 3759 int re_flags; | |
| 3760 { | |
| 3761 nfa_regprog_T *prog; | |
| 4458 | 3762 size_t prog_size; |
| 4444 | 3763 int *postfix; |
| 3764 | |
| 3765 if (expr == NULL) | |
| 3766 return NULL; | |
| 3767 | |
| 3768 #ifdef DEBUG | |
| 3769 nfa_regengine.expr = expr; | |
| 3770 #endif | |
| 3771 | |
| 3772 init_class_tab(); | |
| 3773 | |
| 3774 if (nfa_regcomp_start(expr, re_flags) == FAIL) | |
| 3775 return NULL; | |
| 3776 | |
| 3777 /* Space for compiled regexp */ | |
| 3778 prog_size = sizeof(nfa_regprog_T) + sizeof(nfa_state_T) * nstate_max; | |
| 3779 prog = (nfa_regprog_T *)lalloc(prog_size, TRUE); | |
| 3780 if (prog == NULL) | |
| 3781 goto fail; | |
| 3782 vim_memset(prog, 0, prog_size); | |
| 3783 | |
| 3784 /* Build postfix form of the regexp. Needed to build the NFA | |
| 3785 * (and count its size) */ | |
| 3786 postfix = re2post(); | |
| 3787 if (postfix == NULL) | |
| 3788 goto fail; /* Cascaded (syntax?) error */ | |
| 3789 | |
| 3790 /* | |
| 3791 * In order to build the NFA, we parse the input regexp twice: | |
| 3792 * 1. first pass to count size (so we can allocate space) | |
| 3793 * 2. second to emit code | |
| 3794 */ | |
| 3795 #ifdef ENABLE_LOG | |
| 3796 { | |
|
4531
1be43c095aff
updated for version 7.3.1013
Bram Moolenaar <bram@vim.org>
parents:
4529
diff
changeset
|
3797 FILE *f = fopen(NFA_REGEXP_RUN_LOG, "a"); |
| 4444 | 3798 |
| 3799 if (f != NULL) | |
| 3800 { | |
| 3801 fprintf(f, "\n*****************************\n\n\n\n\tCompiling regexp \"%s\" ... hold on !\n", expr); | |
| 3802 fclose(f); | |
| 3803 } | |
| 3804 } | |
| 3805 #endif | |
| 3806 | |
| 3807 /* | |
| 3808 * PASS 1 | |
| 3809 * Count number of NFA states in "nstate". Do not build the NFA. | |
| 3810 */ | |
| 3811 post2nfa(postfix, post_ptr, TRUE); | |
| 3812 state_ptr = prog->state; | |
| 3813 | |
| 3814 /* | |
| 3815 * PASS 2 | |
| 3816 * Build the NFA | |
| 3817 */ | |
| 3818 prog->start = post2nfa(postfix, post_ptr, FALSE); | |
| 3819 if (prog->start == NULL) | |
| 3820 goto fail; | |
| 3821 | |
| 3822 prog->regflags = regflags; | |
| 3823 prog->engine = &nfa_regengine; | |
| 3824 prog->nstate = nstate; | |
| 3825 #ifdef ENABLE_LOG | |
| 3826 nfa_postfix_dump(expr, OK); | |
| 3827 nfa_dump(prog); | |
| 3828 #endif | |
| 3829 | |
| 3830 out: | |
| 3831 vim_free(post_start); | |
| 3832 post_start = post_ptr = post_end = NULL; | |
| 3833 state_ptr = NULL; | |
| 3834 return (regprog_T *)prog; | |
| 3835 | |
| 3836 fail: | |
| 3837 vim_free(prog); | |
| 3838 prog = NULL; | |
| 3839 #ifdef ENABLE_LOG | |
| 3840 nfa_postfix_dump(expr, FAIL); | |
| 3841 #endif | |
| 3842 #ifdef DEBUG | |
| 3843 nfa_regengine.expr = NULL; | |
| 3844 #endif | |
| 3845 goto out; | |
| 3846 } | |
| 3847 | |
| 3848 | |
| 3849 /* | |
| 3850 * Match a regexp against a string. | |
| 3851 * "rmp->regprog" is a compiled regexp as returned by nfa_regcomp(). | |
| 3852 * Uses curbuf for line count and 'iskeyword'. | |
| 3853 * | |
| 3854 * Return TRUE if there is a match, FALSE if not. | |
| 3855 */ | |
| 3856 static int | |
| 3857 nfa_regexec(rmp, line, col) | |
| 3858 regmatch_T *rmp; | |
| 3859 char_u *line; /* string to match against */ | |
| 3860 colnr_T col; /* column to start looking for match */ | |
| 3861 { | |
| 3862 reg_match = rmp; | |
| 3863 reg_mmatch = NULL; | |
| 3864 reg_maxline = 0; | |
| 3865 reg_line_lbr = FALSE; | |
| 3866 reg_buf = curbuf; | |
| 3867 reg_win = NULL; | |
| 3868 ireg_ic = rmp->rm_ic; | |
| 3869 #ifdef FEAT_MBYTE | |
| 3870 ireg_icombine = FALSE; | |
| 3871 #endif | |
| 3872 ireg_maxcol = 0; | |
| 3873 return (nfa_regexec_both(line, col) != 0); | |
| 3874 } | |
| 3875 | |
| 3876 #if defined(FEAT_MODIFY_FNAME) || defined(FEAT_EVAL) \ | |
| 3877 || defined(FIND_REPLACE_DIALOG) || defined(PROTO) | |
| 3878 | |
| 3879 static int nfa_regexec_nl __ARGS((regmatch_T *rmp, char_u *line, colnr_T col)); | |
| 3880 | |
| 3881 /* | |
| 3882 * Like nfa_regexec(), but consider a "\n" in "line" to be a line break. | |
| 3883 */ | |
| 3884 static int | |
| 3885 nfa_regexec_nl(rmp, line, col) | |
| 3886 regmatch_T *rmp; | |
| 3887 char_u *line; /* string to match against */ | |
| 3888 colnr_T col; /* column to start looking for match */ | |
| 3889 { | |
| 3890 reg_match = rmp; | |
| 3891 reg_mmatch = NULL; | |
| 3892 reg_maxline = 0; | |
| 3893 reg_line_lbr = TRUE; | |
| 3894 reg_buf = curbuf; | |
| 3895 reg_win = NULL; | |
| 3896 ireg_ic = rmp->rm_ic; | |
| 3897 #ifdef FEAT_MBYTE | |
| 3898 ireg_icombine = FALSE; | |
| 3899 #endif | |
| 3900 ireg_maxcol = 0; | |
| 3901 return (nfa_regexec_both(line, col) != 0); | |
| 3902 } | |
| 3903 #endif | |
| 3904 | |
| 3905 | |
| 3906 /* | |
| 3907 * Match a regexp against multiple lines. | |
| 3908 * "rmp->regprog" is a compiled regexp as returned by vim_regcomp(). | |
| 3909 * Uses curbuf for line count and 'iskeyword'. | |
| 3910 * | |
| 3911 * Return zero if there is no match. Return number of lines contained in the | |
| 3912 * match otherwise. | |
| 3913 * | |
| 3914 * Note: the body is the same as bt_regexec() except for nfa_regexec_both() | |
| 3915 * | |
| 3916 * ! Also NOTE : match may actually be in another line. e.g.: | |
| 3917 * when r.e. is \nc, cursor is at 'a' and the text buffer looks like | |
| 3918 * | |
| 3919 * +-------------------------+ | |
| 3920 * |a | | |
| 3921 * |b | | |
| 3922 * |c | | |
| 3923 * | | | |
| 3924 * +-------------------------+ | |
| 3925 * | |
| 3926 * then nfa_regexec_multi() returns 3. while the original | |
| 3927 * vim_regexec_multi() returns 0 and a second call at line 2 will return 2. | |
| 3928 * | |
| 3929 * FIXME if this behavior is not compatible. | |
| 3930 */ | |
| 3931 static long | |
| 3932 nfa_regexec_multi(rmp, win, buf, lnum, col, tm) | |
| 3933 regmmatch_T *rmp; | |
| 3934 win_T *win; /* window in which to search or NULL */ | |
| 3935 buf_T *buf; /* buffer in which to search */ | |
| 3936 linenr_T lnum; /* nr of line to start looking for match */ | |
| 3937 colnr_T col; /* column to start looking for match */ | |
| 3938 proftime_T *tm UNUSED; /* timeout limit or NULL */ | |
| 3939 { | |
| 3940 reg_match = NULL; | |
| 3941 reg_mmatch = rmp; | |
| 3942 reg_buf = buf; | |
| 3943 reg_win = win; | |
| 3944 reg_firstlnum = lnum; | |
| 3945 reg_maxline = reg_buf->b_ml.ml_line_count - lnum; | |
| 3946 reg_line_lbr = FALSE; | |
| 3947 ireg_ic = rmp->rmm_ic; | |
| 3948 #ifdef FEAT_MBYTE | |
| 3949 ireg_icombine = FALSE; | |
| 3950 #endif | |
| 3951 ireg_maxcol = rmp->rmm_maxcol; | |
| 3952 | |
| 4503 | 3953 return nfa_regexec_both(NULL, col); |
| 4444 | 3954 } |
| 3955 | |
| 3956 #ifdef DEBUG | |
| 3957 # undef ENABLE_LOG | |
| 3958 #endif |