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