/src/librdkafka/src/regexp.c
Line | Count | Source |
1 | | /** |
2 | | * Copyright: public domain |
3 | | * |
4 | | * From https://github.com/ccxvii/minilibs sha |
5 | | * 875c33568b5a4aa4fb3dd0c52ea98f7f0e5ca684: |
6 | | * |
7 | | * These libraries are in the public domain (or the equivalent where that is not |
8 | | * possible). You can do anything you want with them. You have no legal |
9 | | * obligation to do anything else, although I appreciate attribution. |
10 | | */ |
11 | | |
12 | | #include "rd.h" |
13 | | |
14 | | #include <stdlib.h> |
15 | | #include <string.h> |
16 | | #include <setjmp.h> |
17 | | #include <stdio.h> |
18 | | |
19 | | #include "regexp.h" |
20 | | |
21 | 10.3k | #define nelem(a) (sizeof(a) / sizeof(a)[0]) |
22 | | |
23 | | typedef unsigned int Rune; |
24 | | |
25 | 488 | static int isalpharune(Rune c) { |
26 | | /* TODO: Add unicode support */ |
27 | 488 | return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'); |
28 | 488 | } |
29 | | |
30 | 0 | static Rune toupperrune(Rune c) { |
31 | | /* TODO: Add unicode support */ |
32 | 0 | if (c >= 'a' && c <= 'z') |
33 | 0 | return c - 'a' + 'A'; |
34 | 0 | return c; |
35 | 0 | } |
36 | | |
37 | 272k | static int chartorune(Rune *r, const char *s) { |
38 | | /* TODO: Add UTF-8 decoding */ |
39 | 272k | *r = *s; |
40 | 272k | return 1; |
41 | 272k | } |
42 | | |
43 | 29.8k | #define REPINF 255 |
44 | 0 | #define MAXTHREAD 1000 |
45 | 35.2k | #define MAXSUB REG_MAXSUB |
46 | | |
47 | | typedef struct Reclass Reclass; |
48 | | typedef struct Renode Renode; |
49 | | typedef struct Reinst Reinst; |
50 | | typedef struct Rethread Rethread; |
51 | | typedef struct Restate Restate; |
52 | | |
53 | | struct Reclass { |
54 | | Rune *end; |
55 | | Rune spans[64]; |
56 | | }; |
57 | | |
58 | | struct Restate { |
59 | | Reprog *prog; |
60 | | Renode *pstart, *pend; |
61 | | |
62 | | const char *source; |
63 | | unsigned int ncclass; |
64 | | unsigned int nsub; |
65 | | Renode *sub[MAXSUB]; |
66 | | |
67 | | int lookahead; |
68 | | Rune yychar; |
69 | | Reclass *yycc; |
70 | | int yymin, yymax; |
71 | | |
72 | | const char *error; |
73 | | jmp_buf kaboom; |
74 | | }; |
75 | | |
76 | | struct Reprog { |
77 | | Reinst *start, *end; |
78 | | int flags; |
79 | | unsigned int nsub; |
80 | | Reclass cclass[16]; |
81 | | Restate g; /**< Upstream has this as a global variable */ |
82 | | }; |
83 | | |
84 | 1.12k | static void die(Restate *g, const char *message) { |
85 | 1.12k | g->error = message; |
86 | 1.12k | longjmp(g->kaboom, 1); |
87 | 1.12k | } |
88 | | |
89 | 0 | static Rune canon(Rune c) { |
90 | 0 | Rune u = toupperrune(c); |
91 | 0 | if (c >= 128 && u < 128) |
92 | 0 | return c; |
93 | 0 | return u; |
94 | 0 | } |
95 | | |
96 | | /* Scan */ |
97 | | |
98 | | enum { |
99 | | L_CHAR = 256, |
100 | | L_CCLASS, /* character class */ |
101 | | L_NCCLASS, /* negative character class */ |
102 | | L_NC, /* "(?:" no capture */ |
103 | | L_PLA, /* "(?=" positive lookahead */ |
104 | | L_NLA, /* "(?!" negative lookahead */ |
105 | | L_WORD, /* "\b" word boundary */ |
106 | | L_NWORD, /* "\B" non-word boundary */ |
107 | | L_REF, /* "\1" back-reference */ |
108 | | L_COUNT /* {M,N} */ |
109 | | }; |
110 | | |
111 | 10.3k | static int hex(Restate *g, int c) { |
112 | 10.3k | if (c >= '0' && c <= '9') |
113 | 4.04k | return c - '0'; |
114 | 6.32k | if (c >= 'a' && c <= 'f') |
115 | 2.79k | return c - 'a' + 0xA; |
116 | 3.53k | if (c >= 'A' && c <= 'F') |
117 | 3.27k | return c - 'A' + 0xA; |
118 | 265 | die(g, "invalid escape sequence"); |
119 | 265 | return 0; |
120 | 3.53k | } |
121 | | |
122 | 5.41k | static int dec(Restate *g, int c) { |
123 | 5.41k | if (c >= '0' && c <= '9') |
124 | 5.30k | return c - '0'; |
125 | 110 | die(g, "invalid quantifier"); |
126 | 110 | return 0; |
127 | 5.41k | } |
128 | | |
129 | 5.21k | #define ESCAPES "BbDdSsWw^$\\.*+?()[]{}|0123456789" |
130 | | |
131 | 262k | static int nextrune(Restate *g) { |
132 | 262k | g->source += chartorune(&g->yychar, g->source); |
133 | 262k | if (g->yychar == '\\') { |
134 | 9.84k | g->source += chartorune(&g->yychar, g->source); |
135 | 9.84k | switch (g->yychar) { |
136 | 8 | case 0: |
137 | 8 | die(g, "unterminated escape sequence"); |
138 | 277 | case 'f': |
139 | 277 | g->yychar = '\f'; |
140 | 277 | return 0; |
141 | 216 | case 'n': |
142 | 216 | g->yychar = '\n'; |
143 | 216 | return 0; |
144 | 194 | case 'r': |
145 | 194 | g->yychar = '\r'; |
146 | 194 | return 0; |
147 | 194 | case 't': |
148 | 194 | g->yychar = '\t'; |
149 | 194 | return 0; |
150 | 194 | case 'v': |
151 | 194 | g->yychar = '\v'; |
152 | 194 | return 0; |
153 | 195 | case 'c': |
154 | 195 | g->yychar = (*g->source++) & 31; |
155 | 195 | return 0; |
156 | 1.39k | case 'x': |
157 | 1.39k | g->yychar = hex(g, *g->source++) << 4; |
158 | 1.39k | g->yychar += hex(g, *g->source++); |
159 | 1.39k | if (g->yychar == 0) { |
160 | 475 | g->yychar = '0'; |
161 | 475 | return 1; |
162 | 475 | } |
163 | 923 | return 0; |
164 | 1.96k | case 'u': |
165 | 1.96k | g->yychar = hex(g, *g->source++) << 12; |
166 | 1.96k | g->yychar += hex(g, *g->source++) << 8; |
167 | 1.96k | g->yychar += hex(g, *g->source++) << 4; |
168 | 1.96k | g->yychar += hex(g, *g->source++); |
169 | 1.96k | if (g->yychar == 0) { |
170 | 472 | g->yychar = '0'; |
171 | 472 | return 1; |
172 | 472 | } |
173 | 1.49k | return 0; |
174 | 9.84k | } |
175 | 5.21k | if (strchr(ESCAPES, g->yychar)) |
176 | 4.72k | return 1; |
177 | 488 | if (isalpharune(g->yychar) || |
178 | 479 | g->yychar == '_') /* check identity escape */ |
179 | 10 | die(g, "invalid escape character"); |
180 | 488 | return 0; |
181 | 5.21k | } |
182 | 252k | return 0; |
183 | 262k | } |
184 | | |
185 | 1.95k | static int lexcount(Restate *g) { |
186 | 1.95k | g->yychar = *g->source++; |
187 | | |
188 | 1.95k | g->yymin = dec(g, g->yychar); |
189 | 1.95k | g->yychar = *g->source++; |
190 | 3.80k | while (g->yychar != ',' && g->yychar != '}') { |
191 | 1.85k | g->yymin = g->yymin * 10 + dec(g, g->yychar); |
192 | 1.85k | g->yychar = *g->source++; |
193 | 1.85k | } |
194 | 1.95k | if (g->yymin >= REPINF) |
195 | 21 | die(g, "numeric overflow"); |
196 | | |
197 | 1.95k | if (g->yychar == ',') { |
198 | 859 | g->yychar = *g->source++; |
199 | 859 | if (g->yychar == '}') { |
200 | 280 | g->yymax = REPINF; |
201 | 579 | } else { |
202 | 579 | g->yymax = dec(g, g->yychar); |
203 | 579 | g->yychar = *g->source++; |
204 | 1.60k | while (g->yychar != '}') { |
205 | 1.02k | g->yymax = g->yymax * 10 + dec(g, g->yychar); |
206 | 1.02k | g->yychar = *g->source++; |
207 | 1.02k | } |
208 | 579 | if (g->yymax >= REPINF) |
209 | 18 | die(g, "numeric overflow"); |
210 | 579 | } |
211 | 1.09k | } else { |
212 | 1.09k | g->yymax = g->yymin; |
213 | 1.09k | } |
214 | | |
215 | 1.95k | return L_COUNT; |
216 | 1.95k | } |
217 | | |
218 | 1.34k | static void newcclass(Restate *g) { |
219 | 1.34k | if (g->ncclass >= nelem(g->prog->cclass)) |
220 | 7 | die(g, "too many character classes"); |
221 | 1.34k | g->yycc = g->prog->cclass + g->ncclass++; |
222 | 1.34k | g->yycc->end = g->yycc->spans; |
223 | 1.34k | } |
224 | | |
225 | 9.04k | static void addrange(Restate *g, Rune a, Rune b) { |
226 | 9.04k | if (a > b) |
227 | 50 | die(g, "invalid character class range"); |
228 | 9.04k | if (g->yycc->end + 2 == g->yycc->spans + nelem(g->yycc->spans)) |
229 | 45 | die(g, "too many character class ranges"); |
230 | 9.04k | *g->yycc->end++ = a; |
231 | 9.04k | *g->yycc->end++ = b; |
232 | 9.04k | } |
233 | | |
234 | 1.03k | static void addranges_d(Restate *g) { |
235 | 1.03k | addrange(g, '0', '9'); |
236 | 1.03k | } |
237 | | |
238 | 319 | static void addranges_D(Restate *g) { |
239 | 319 | addrange(g, 0, '0' - 1); |
240 | 319 | addrange(g, '9' + 1, 0xFFFF); |
241 | 319 | } |
242 | | |
243 | 466 | static void addranges_s(Restate *g) { |
244 | 466 | addrange(g, 0x9, 0x9); |
245 | 466 | addrange(g, 0xA, 0xD); |
246 | 466 | addrange(g, 0x20, 0x20); |
247 | 466 | addrange(g, 0xA0, 0xA0); |
248 | 466 | addrange(g, 0x2028, 0x2029); |
249 | 466 | addrange(g, 0xFEFF, 0xFEFF); |
250 | 466 | } |
251 | | |
252 | 5 | static void addranges_S(Restate *g) { |
253 | 5 | addrange(g, 0, 0x9 - 1); |
254 | 5 | addrange(g, 0x9 + 1, 0xA - 1); |
255 | 5 | addrange(g, 0xD + 1, 0x20 - 1); |
256 | 5 | addrange(g, 0x20 + 1, 0xA0 - 1); |
257 | 5 | addrange(g, 0xA0 + 1, 0x2028 - 1); |
258 | 5 | addrange(g, 0x2029 + 1, 0xFEFF - 1); |
259 | 5 | addrange(g, 0xFEFF + 1, 0xFFFF); |
260 | 5 | } |
261 | | |
262 | 259 | static void addranges_w(Restate *g) { |
263 | 259 | addrange(g, '0', '9'); |
264 | 259 | addrange(g, 'A', 'Z'); |
265 | 259 | addrange(g, '_', '_'); |
266 | 259 | addrange(g, 'a', 'z'); |
267 | 259 | } |
268 | | |
269 | 85 | static void addranges_W(Restate *g) { |
270 | 85 | addrange(g, 0, '0' - 1); |
271 | 85 | addrange(g, '9' + 1, 'A' - 1); |
272 | 85 | addrange(g, 'Z' + 1, '_' - 1); |
273 | 85 | addrange(g, '_' + 1, 'a' - 1); |
274 | 85 | addrange(g, 'z' + 1, 0xFFFF); |
275 | 85 | } |
276 | | |
277 | 787 | static int lexclass(Restate *g) { |
278 | 787 | int type = L_CCLASS; |
279 | 787 | int quoted, havesave, havedash; |
280 | 787 | Rune save = 0; |
281 | | |
282 | 787 | newcclass(g); |
283 | | |
284 | 787 | quoted = nextrune(g); |
285 | 787 | if (!quoted && g->yychar == '^') { |
286 | 44 | type = L_NCCLASS; |
287 | 44 | quoted = nextrune(g); |
288 | 44 | } |
289 | | |
290 | 787 | havesave = havedash = 0; |
291 | 7.55k | for (;;) { |
292 | 7.55k | if (g->yychar == 0) |
293 | 229 | die(g, "unterminated character class"); |
294 | 7.55k | if (!quoted && g->yychar == ']') |
295 | 461 | break; |
296 | | |
297 | 7.09k | if (!quoted && g->yychar == '-') { |
298 | 2.40k | if (havesave) { |
299 | 1.75k | if (havedash) { |
300 | 539 | addrange(g, save, '-'); |
301 | 539 | havesave = havedash = 0; |
302 | 1.21k | } else { |
303 | 1.21k | havedash = 1; |
304 | 1.21k | } |
305 | 1.75k | } else { |
306 | 647 | save = '-'; |
307 | 647 | havesave = 1; |
308 | 647 | } |
309 | 4.68k | } else if (quoted && strchr("DSWdsw", g->yychar)) { |
310 | 1.62k | if (havesave) { |
311 | 551 | addrange(g, save, save); |
312 | 551 | if (havedash) |
313 | 195 | addrange(g, '-', '-'); |
314 | 551 | } |
315 | 1.62k | switch (g->yychar) { |
316 | 869 | case 'd': |
317 | 869 | addranges_d(g); |
318 | 869 | break; |
319 | 226 | case 's': |
320 | 226 | addranges_s(g); |
321 | 226 | break; |
322 | 120 | case 'w': |
323 | 120 | addranges_w(g); |
324 | 120 | break; |
325 | 319 | case 'D': |
326 | 319 | addranges_D(g); |
327 | 319 | break; |
328 | 5 | case 'S': |
329 | 5 | addranges_S(g); |
330 | 5 | break; |
331 | 85 | case 'W': |
332 | 85 | addranges_W(g); |
333 | 85 | break; |
334 | 1.62k | } |
335 | 1.58k | havesave = havedash = 0; |
336 | 3.06k | } else { |
337 | 3.06k | if (quoted) { |
338 | 672 | if (g->yychar == 'b') |
339 | 194 | g->yychar = '\b'; |
340 | 478 | else if (g->yychar == '0') |
341 | 195 | g->yychar = 0; |
342 | | /* else identity escape */ |
343 | 672 | } |
344 | 3.06k | if (havesave) { |
345 | 1.65k | if (havedash) { |
346 | 428 | addrange(g, save, g->yychar); |
347 | 428 | havesave = havedash = 0; |
348 | 1.22k | } else { |
349 | 1.22k | addrange(g, save, save); |
350 | 1.22k | save = g->yychar; |
351 | 1.22k | } |
352 | 1.65k | } else { |
353 | 1.40k | save = g->yychar; |
354 | 1.40k | havesave = 1; |
355 | 1.40k | } |
356 | 3.06k | } |
357 | | |
358 | 7.05k | quoted = nextrune(g); |
359 | 7.05k | } |
360 | | |
361 | 748 | if (havesave) { |
362 | 170 | addrange(g, save, save); |
363 | 170 | if (havedash) |
364 | 47 | addrange(g, '-', '-'); |
365 | 170 | } |
366 | | |
367 | 748 | return type; |
368 | 787 | } |
369 | | |
370 | 254k | static int lex(Restate *g) { |
371 | 254k | int quoted = nextrune(g); |
372 | 254k | if (quoted) { |
373 | 3.37k | switch (g->yychar) { |
374 | 203 | case 'b': |
375 | 203 | return L_WORD; |
376 | 199 | case 'B': |
377 | 199 | return L_NWORD; |
378 | 63 | case 'd': |
379 | 63 | newcclass(g); |
380 | 63 | addranges_d(g); |
381 | 63 | return L_CCLASS; |
382 | 101 | case 's': |
383 | 101 | newcclass(g); |
384 | 101 | addranges_s(g); |
385 | 101 | return L_CCLASS; |
386 | 89 | case 'w': |
387 | 89 | newcclass(g); |
388 | 89 | addranges_w(g); |
389 | 89 | return L_CCLASS; |
390 | 108 | case 'D': |
391 | 108 | newcclass(g); |
392 | 108 | addranges_d(g); |
393 | 108 | return L_NCCLASS; |
394 | 141 | case 'S': |
395 | 141 | newcclass(g); |
396 | 141 | addranges_s(g); |
397 | 141 | return L_NCCLASS; |
398 | 52 | case 'W': |
399 | 52 | newcclass(g); |
400 | 52 | addranges_w(g); |
401 | 52 | return L_NCCLASS; |
402 | 1.16k | case '0': |
403 | 1.16k | g->yychar = 0; |
404 | 1.16k | return L_CHAR; |
405 | 3.37k | } |
406 | 1.25k | if (g->yychar >= '0' && g->yychar <= '9') { |
407 | 853 | g->yychar -= '0'; |
408 | 853 | if (*g->source >= '0' && *g->source <= '9') |
409 | 203 | g->yychar = g->yychar * 10 + *g->source++ - '0'; |
410 | 853 | return L_REF; |
411 | 853 | } |
412 | 400 | return L_CHAR; |
413 | 1.25k | } |
414 | | |
415 | 251k | switch (g->yychar) { |
416 | 1.13k | case 0: |
417 | 4.44k | case '$': |
418 | 6.66k | case ')': |
419 | 9.96k | case '*': |
420 | 10.6k | case '+': |
421 | 14.6k | case '.': |
422 | 17.7k | case '?': |
423 | 39.4k | case '^': |
424 | 44.3k | case '|': |
425 | 44.3k | return g->yychar; |
426 | 251k | } |
427 | | |
428 | 206k | if (g->yychar == '{') |
429 | 1.95k | return lexcount(g); |
430 | 205k | if (g->yychar == '[') |
431 | 787 | return lexclass(g); |
432 | 204k | if (g->yychar == '(') { |
433 | 3.76k | if (g->source[0] == '?') { |
434 | 2.60k | if (g->source[1] == ':') { |
435 | 785 | g->source += 2; |
436 | 785 | return L_NC; |
437 | 785 | } |
438 | 1.81k | if (g->source[1] == '=') { |
439 | 795 | g->source += 2; |
440 | 795 | return L_PLA; |
441 | 795 | } |
442 | 1.02k | if (g->source[1] == '!') { |
443 | 1.00k | g->source += 2; |
444 | 1.00k | return L_NLA; |
445 | 1.00k | } |
446 | 1.02k | } |
447 | 1.18k | return '('; |
448 | 3.76k | } |
449 | | |
450 | 200k | return L_CHAR; |
451 | 204k | } |
452 | | |
453 | | /* Parse */ |
454 | | |
455 | | enum { |
456 | | P_CAT, |
457 | | P_ALT, |
458 | | P_REP, |
459 | | P_BOL, |
460 | | P_EOL, |
461 | | P_WORD, |
462 | | P_NWORD, |
463 | | P_PAR, |
464 | | P_PLA, |
465 | | P_NLA, |
466 | | P_ANY, |
467 | | P_CHAR, |
468 | | P_CCLASS, |
469 | | P_NCCLASS, |
470 | | P_REF |
471 | | }; |
472 | | |
473 | | struct Renode { |
474 | | unsigned char type; |
475 | | unsigned char ng, m, n; |
476 | | Rune c; |
477 | | Reclass *cc; |
478 | | Renode *x; |
479 | | Renode *y; |
480 | | }; |
481 | | |
482 | 480k | static Renode *newnode(Restate *g, int type) { |
483 | 480k | Renode *node = g->pend++; |
484 | 480k | node->type = type; |
485 | 480k | node->cc = NULL; |
486 | 480k | node->c = 0; |
487 | 480k | node->ng = 0; |
488 | 480k | node->m = 0; |
489 | 480k | node->n = 0; |
490 | 480k | node->x = node->y = NULL; |
491 | 480k | return node; |
492 | 480k | } |
493 | | |
494 | 12.9k | static int empty(Renode *node) { |
495 | 12.9k | if (!node) |
496 | 709 | return 1; |
497 | 12.1k | switch (node->type) { |
498 | 359 | default: |
499 | 359 | return 1; |
500 | 2.61k | case P_CAT: |
501 | 2.61k | return empty(node->x) && empty(node->y); |
502 | 531 | case P_ALT: |
503 | 531 | return empty(node->x) || empty(node->y); |
504 | 959 | case P_REP: |
505 | 959 | return empty(node->x) || node->m == 0; |
506 | 1.80k | case P_PAR: |
507 | 1.80k | return empty(node->x); |
508 | 814 | case P_REF: |
509 | 814 | return empty(node->x); |
510 | 573 | case P_ANY: |
511 | 4.70k | case P_CHAR: |
512 | 4.90k | case P_CCLASS: |
513 | 5.11k | case P_NCCLASS: |
514 | 5.11k | return 0; |
515 | 12.1k | } |
516 | 12.1k | } |
517 | | |
518 | 6.28k | static Renode *newrep(Restate *g, Renode *atom, int ng, int min, int max) { |
519 | 6.28k | Renode *rep = newnode(g, P_REP); |
520 | 6.28k | if (max == REPINF && empty(atom)) |
521 | 43 | die(g, "infinite loop matching the empty string"); |
522 | 6.28k | rep->ng = ng; |
523 | 6.28k | rep->m = min; |
524 | 6.28k | rep->n = max; |
525 | 6.28k | rep->x = atom; |
526 | 6.28k | return rep; |
527 | 6.28k | } |
528 | | |
529 | 254k | static void next(Restate *g) { |
530 | 254k | g->lookahead = lex(g); |
531 | 254k | } |
532 | | |
533 | 1.52M | static int re_accept(Restate *g, int t) { |
534 | 1.52M | if (g->lookahead == t) { |
535 | 47.2k | next(g); |
536 | 47.2k | return 1; |
537 | 47.2k | } |
538 | 1.48M | return 0; |
539 | 1.52M | } |
540 | | |
541 | | static Renode *parsealt(Restate *g); |
542 | | |
543 | 211k | static Renode *parseatom(Restate *g) { |
544 | 211k | Renode *atom; |
545 | 211k | if (g->lookahead == L_CHAR) { |
546 | 202k | atom = newnode(g, P_CHAR); |
547 | 202k | atom->c = g->yychar; |
548 | 202k | next(g); |
549 | 202k | return atom; |
550 | 202k | } |
551 | 9.70k | if (g->lookahead == L_CCLASS) { |
552 | 672 | atom = newnode(g, P_CCLASS); |
553 | 672 | atom->cc = g->yycc; |
554 | 672 | next(g); |
555 | 672 | return atom; |
556 | 672 | } |
557 | 9.03k | if (g->lookahead == L_NCCLASS) { |
558 | 334 | atom = newnode(g, P_NCCLASS); |
559 | 334 | atom->cc = g->yycc; |
560 | 334 | next(g); |
561 | 334 | return atom; |
562 | 334 | } |
563 | 8.70k | if (g->lookahead == L_REF) { |
564 | 852 | atom = newnode(g, P_REF); |
565 | 852 | if (g->yychar == 0 || g->yychar > g->nsub || !g->sub[g->yychar]) |
566 | 31 | die(g, "invalid back-reference"); |
567 | 852 | atom->n = g->yychar; |
568 | 852 | atom->x = g->sub[g->yychar]; |
569 | 852 | next(g); |
570 | 852 | return atom; |
571 | 852 | } |
572 | 7.85k | if (re_accept(g, '.')) |
573 | 3.96k | return newnode(g, P_ANY); |
574 | 3.88k | if (re_accept(g, '(')) { |
575 | 1.18k | atom = newnode(g, P_PAR); |
576 | 1.18k | if (g->nsub == MAXSUB) |
577 | 7 | die(g, "too many captures"); |
578 | 1.18k | atom->n = g->nsub++; |
579 | 1.18k | atom->x = parsealt(g); |
580 | 1.18k | g->sub[atom->n] = atom; |
581 | 1.18k | if (!re_accept(g, ')')) |
582 | 51 | die(g, "unmatched '('"); |
583 | 1.18k | return atom; |
584 | 1.18k | } |
585 | 2.70k | if (re_accept(g, L_NC)) { |
586 | 785 | atom = parsealt(g); |
587 | 785 | if (!re_accept(g, ')')) |
588 | 12 | die(g, "unmatched '('"); |
589 | 785 | return atom; |
590 | 785 | } |
591 | 1.91k | if (re_accept(g, L_PLA)) { |
592 | 795 | atom = newnode(g, P_PLA); |
593 | 795 | atom->x = parsealt(g); |
594 | 795 | if (!re_accept(g, ')')) |
595 | 9 | die(g, "unmatched '('"); |
596 | 795 | return atom; |
597 | 795 | } |
598 | 1.12k | if (re_accept(g, L_NLA)) { |
599 | 1.00k | atom = newnode(g, P_NLA); |
600 | 1.00k | atom->x = parsealt(g); |
601 | 1.00k | if (!re_accept(g, ')')) |
602 | 9 | die(g, "unmatched '('"); |
603 | 1.00k | return atom; |
604 | 1.00k | } |
605 | 118 | die(g, "syntax error"); |
606 | 118 | return NULL; |
607 | 1.12k | } |
608 | | |
609 | 237k | static Renode *parserep(Restate *g) { |
610 | 237k | Renode *atom; |
611 | | |
612 | 237k | if (re_accept(g, '^')) |
613 | 21.7k | return newnode(g, P_BOL); |
614 | 215k | if (re_accept(g, '$')) |
615 | 3.31k | return newnode(g, P_EOL); |
616 | 212k | if (re_accept(g, L_WORD)) |
617 | 203 | return newnode(g, P_WORD); |
618 | 211k | if (re_accept(g, L_NWORD)) |
619 | 199 | return newnode(g, P_NWORD); |
620 | | |
621 | 211k | atom = parseatom(g); |
622 | 211k | if (g->lookahead == L_COUNT) { |
623 | 1.74k | int min = g->yymin, max = g->yymax; |
624 | 1.74k | next(g); |
625 | 1.74k | if (max < min) |
626 | 21 | die(g, "invalid quantifier"); |
627 | 1.74k | return newrep(g, atom, re_accept(g, '?'), min, max); |
628 | 1.74k | } |
629 | 210k | if (re_accept(g, '*')) |
630 | 3.28k | return newrep(g, atom, re_accept(g, '?'), 0, REPINF); |
631 | 206k | if (re_accept(g, '+')) |
632 | 697 | return newrep(g, atom, re_accept(g, '?'), 1, REPINF); |
633 | 206k | if (re_accept(g, '?')) |
634 | 581 | return newrep(g, atom, re_accept(g, '?'), 0, 1); |
635 | 205k | return atom; |
636 | 206k | } |
637 | | |
638 | 10.0k | static Renode *parsecat(Restate *g) { |
639 | 10.0k | Renode *cat, *x; |
640 | 10.0k | if (g->lookahead && g->lookahead != '|' && g->lookahead != ')') { |
641 | 4.57k | cat = parserep(g); |
642 | 237k | while (g->lookahead && g->lookahead != '|' && |
643 | 233k | g->lookahead != ')') { |
644 | 232k | x = cat; |
645 | 232k | cat = newnode(g, P_CAT); |
646 | 232k | cat->x = x; |
647 | 232k | cat->y = parserep(g); |
648 | 232k | } |
649 | 4.57k | return cat; |
650 | 4.57k | } |
651 | 5.50k | return NULL; |
652 | 10.0k | } |
653 | | |
654 | 5.23k | static Renode *parsealt(Restate *g) { |
655 | 5.23k | Renode *alt, *x; |
656 | 5.23k | alt = parsecat(g); |
657 | 10.0k | while (re_accept(g, '|')) { |
658 | 4.84k | x = alt; |
659 | 4.84k | alt = newnode(g, P_ALT); |
660 | 4.84k | alt->x = x; |
661 | 4.84k | alt->y = parsecat(g); |
662 | 4.84k | } |
663 | 5.23k | return alt; |
664 | 5.23k | } |
665 | | |
666 | | /* Compile */ |
667 | | |
668 | | enum { |
669 | | I_END, |
670 | | I_JUMP, |
671 | | I_SPLIT, |
672 | | I_PLA, |
673 | | I_NLA, |
674 | | I_ANYNL, |
675 | | I_ANY, |
676 | | I_CHAR, |
677 | | I_CCLASS, |
678 | | I_NCCLASS, |
679 | | I_REF, |
680 | | I_BOL, |
681 | | I_EOL, |
682 | | I_WORD, |
683 | | I_NWORD, |
684 | | I_LPAR, |
685 | | I_RPAR |
686 | | }; |
687 | | |
688 | | struct Reinst { |
689 | | unsigned char opcode; |
690 | | unsigned char n; |
691 | | Rune c; |
692 | | Reclass *cc; |
693 | | Reinst *x; |
694 | | Reinst *y; |
695 | | }; |
696 | | |
697 | 469k | static unsigned int count(Renode *node) { |
698 | 469k | unsigned int min, max; |
699 | 469k | if (!node) |
700 | 4.73k | return 0; |
701 | 465k | switch (node->type) { |
702 | 227k | default: |
703 | 227k | return 1; |
704 | 226k | case P_CAT: |
705 | 226k | return count(node->x) + count(node->y); |
706 | 4.33k | case P_ALT: |
707 | 4.33k | return count(node->x) + count(node->y) + 2; |
708 | 5.75k | case P_REP: |
709 | 5.75k | min = node->m; |
710 | 5.75k | max = node->n; |
711 | 5.75k | if (min == max) |
712 | 983 | return count(node->x) * min; |
713 | 4.77k | if (max < REPINF) |
714 | 940 | return count(node->x) * max + (max - min); |
715 | 3.83k | return count(node->x) * (min + 1) + 2; |
716 | 553 | case P_PAR: |
717 | 553 | return count(node->x) + 2; |
718 | 468 | case P_PLA: |
719 | 468 | return count(node->x) + 2; |
720 | 439 | case P_NLA: |
721 | 439 | return count(node->x) + 2; |
722 | 465k | } |
723 | 465k | } |
724 | | |
725 | 375k | static Reinst *emit(Reprog *prog, int opcode) { |
726 | 375k | Reinst *inst = prog->end++; |
727 | 375k | inst->opcode = opcode; |
728 | 375k | inst->n = 0; |
729 | 375k | inst->c = 0; |
730 | 375k | inst->cc = NULL; |
731 | 375k | inst->x = inst->y = NULL; |
732 | 375k | return inst; |
733 | 375k | } |
734 | | |
735 | 560k | static void compile(Reprog *prog, Renode *node) { |
736 | 560k | Reinst *inst, *split, *jump; |
737 | 560k | unsigned int i; |
738 | | |
739 | 560k | if (!node) |
740 | 7.12k | return; |
741 | | |
742 | 553k | switch (node->type) { |
743 | 200k | case P_CAT: |
744 | 200k | compile(prog, node->x); |
745 | 200k | compile(prog, node->y); |
746 | 200k | break; |
747 | | |
748 | 5.29k | case P_ALT: |
749 | 5.29k | split = emit(prog, I_SPLIT); |
750 | 5.29k | compile(prog, node->x); |
751 | 5.29k | jump = emit(prog, I_JUMP); |
752 | 5.29k | compile(prog, node->y); |
753 | 5.29k | split->x = split + 1; |
754 | 5.29k | split->y = jump + 1; |
755 | 5.29k | jump->x = prog->end; |
756 | 5.29k | break; |
757 | | |
758 | 7.94k | case P_REP: |
759 | 142k | for (i = 0; i < node->m; ++i) { |
760 | 134k | inst = prog->end; |
761 | 134k | compile(prog, node->x); |
762 | 134k | } |
763 | 7.94k | if (node->m == node->n) |
764 | 2.27k | break; |
765 | 5.67k | if (node->n < REPINF) { |
766 | 5.37k | for (i = node->m; i < node->n; ++i) { |
767 | 4.09k | split = emit(prog, I_SPLIT); |
768 | 4.09k | compile(prog, node->x); |
769 | 4.09k | if (node->ng) { |
770 | 603 | split->y = split + 1; |
771 | 603 | split->x = prog->end; |
772 | 3.49k | } else { |
773 | 3.49k | split->x = split + 1; |
774 | 3.49k | split->y = prog->end; |
775 | 3.49k | } |
776 | 4.09k | } |
777 | 4.39k | } else if (node->m == 0) { |
778 | 2.79k | split = emit(prog, I_SPLIT); |
779 | 2.79k | compile(prog, node->x); |
780 | 2.79k | jump = emit(prog, I_JUMP); |
781 | 2.79k | if (node->ng) { |
782 | 1.29k | split->y = split + 1; |
783 | 1.29k | split->x = prog->end; |
784 | 1.50k | } else { |
785 | 1.50k | split->x = split + 1; |
786 | 1.50k | split->y = prog->end; |
787 | 1.50k | } |
788 | 2.79k | jump->x = split; |
789 | 2.79k | } else { |
790 | 1.59k | split = emit(prog, I_SPLIT); |
791 | 1.59k | if (node->ng) { |
792 | 441 | split->y = inst; |
793 | 441 | split->x = prog->end; |
794 | 1.15k | } else { |
795 | 1.15k | split->x = inst; |
796 | 1.15k | split->y = prog->end; |
797 | 1.15k | } |
798 | 1.59k | } |
799 | 5.67k | break; |
800 | | |
801 | 14.4k | case P_BOL: |
802 | 14.4k | emit(prog, I_BOL); |
803 | 14.4k | break; |
804 | 3.78k | case P_EOL: |
805 | 3.78k | emit(prog, I_EOL); |
806 | 3.78k | break; |
807 | 491 | case P_WORD: |
808 | 491 | emit(prog, I_WORD); |
809 | 491 | break; |
810 | 531 | case P_NWORD: |
811 | 531 | emit(prog, I_NWORD); |
812 | 531 | break; |
813 | | |
814 | 5.82k | case P_PAR: |
815 | 5.82k | inst = emit(prog, I_LPAR); |
816 | 5.82k | inst->n = node->n; |
817 | 5.82k | compile(prog, node->x); |
818 | 5.82k | inst = emit(prog, I_RPAR); |
819 | 5.82k | inst->n = node->n; |
820 | 5.82k | break; |
821 | 832 | case P_PLA: |
822 | 832 | split = emit(prog, I_PLA); |
823 | 832 | compile(prog, node->x); |
824 | 832 | emit(prog, I_END); |
825 | 832 | split->x = split + 1; |
826 | 832 | split->y = prog->end; |
827 | 832 | break; |
828 | 750 | case P_NLA: |
829 | 750 | split = emit(prog, I_NLA); |
830 | 750 | compile(prog, node->x); |
831 | 750 | emit(prog, I_END); |
832 | 750 | split->x = split + 1; |
833 | 750 | split->y = prog->end; |
834 | 750 | break; |
835 | | |
836 | 8.83k | case P_ANY: |
837 | 8.83k | emit(prog, I_ANY); |
838 | 8.83k | break; |
839 | 302k | case P_CHAR: |
840 | 302k | inst = emit(prog, I_CHAR); |
841 | 302k | inst->c = (prog->flags & REG_ICASE) ? canon(node->c) : node->c; |
842 | 302k | break; |
843 | 533 | case P_CCLASS: |
844 | 533 | inst = emit(prog, I_CCLASS); |
845 | 533 | inst->cc = node->cc; |
846 | 533 | break; |
847 | 796 | case P_NCCLASS: |
848 | 796 | inst = emit(prog, I_NCCLASS); |
849 | 796 | inst->cc = node->cc; |
850 | 796 | break; |
851 | 658 | case P_REF: |
852 | 658 | inst = emit(prog, I_REF); |
853 | 658 | inst->n = node->n; |
854 | 658 | break; |
855 | 553k | } |
856 | 553k | } |
857 | | |
858 | | #ifdef TEST |
859 | | static void dumpnode(Renode *node) { |
860 | | Rune *p; |
861 | | if (!node) { |
862 | | printf("Empty"); |
863 | | return; |
864 | | } |
865 | | switch (node->type) { |
866 | | case P_CAT: |
867 | | printf("Cat("); |
868 | | dumpnode(node->x); |
869 | | printf(", "); |
870 | | dumpnode(node->y); |
871 | | printf(")"); |
872 | | break; |
873 | | case P_ALT: |
874 | | printf("Alt("); |
875 | | dumpnode(node->x); |
876 | | printf(", "); |
877 | | dumpnode(node->y); |
878 | | printf(")"); |
879 | | break; |
880 | | case P_REP: |
881 | | printf(node->ng ? "NgRep(%d,%d," : "Rep(%d,%d,", node->m, |
882 | | node->n); |
883 | | dumpnode(node->x); |
884 | | printf(")"); |
885 | | break; |
886 | | case P_BOL: |
887 | | printf("Bol"); |
888 | | break; |
889 | | case P_EOL: |
890 | | printf("Eol"); |
891 | | break; |
892 | | case P_WORD: |
893 | | printf("Word"); |
894 | | break; |
895 | | case P_NWORD: |
896 | | printf("NotWord"); |
897 | | break; |
898 | | case P_PAR: |
899 | | printf("Par(%d,", node->n); |
900 | | dumpnode(node->x); |
901 | | printf(")"); |
902 | | break; |
903 | | case P_PLA: |
904 | | printf("PLA("); |
905 | | dumpnode(node->x); |
906 | | printf(")"); |
907 | | break; |
908 | | case P_NLA: |
909 | | printf("NLA("); |
910 | | dumpnode(node->x); |
911 | | printf(")"); |
912 | | break; |
913 | | case P_ANY: |
914 | | printf("Any"); |
915 | | break; |
916 | | case P_CHAR: |
917 | | printf("Char(%c)", node->c); |
918 | | break; |
919 | | case P_CCLASS: |
920 | | printf("Class("); |
921 | | for (p = node->cc->spans; p < node->cc->end; p += 2) |
922 | | printf("%02X-%02X,", p[0], p[1]); |
923 | | printf(")"); |
924 | | break; |
925 | | case P_NCCLASS: |
926 | | printf("NotClass("); |
927 | | for (p = node->cc->spans; p < node->cc->end; p += 2) |
928 | | printf("%02X-%02X,", p[0], p[1]); |
929 | | printf(")"); |
930 | | break; |
931 | | case P_REF: |
932 | | printf("Ref(%d)", node->n); |
933 | | break; |
934 | | } |
935 | | } |
936 | | |
937 | | static void dumpprog(Reprog *prog) { |
938 | | Reinst *inst; |
939 | | int i; |
940 | | for (i = 0, inst = prog->start; inst < prog->end; ++i, ++inst) { |
941 | | printf("% 5d: ", i); |
942 | | switch (inst->opcode) { |
943 | | case I_END: |
944 | | puts("end"); |
945 | | break; |
946 | | case I_JUMP: |
947 | | printf("jump %d\n", (int)(inst->x - prog->start)); |
948 | | break; |
949 | | case I_SPLIT: |
950 | | printf("split %d %d\n", (int)(inst->x - prog->start), |
951 | | (int)(inst->y - prog->start)); |
952 | | break; |
953 | | case I_PLA: |
954 | | printf("pla %d %d\n", (int)(inst->x - prog->start), |
955 | | (int)(inst->y - prog->start)); |
956 | | break; |
957 | | case I_NLA: |
958 | | printf("nla %d %d\n", (int)(inst->x - prog->start), |
959 | | (int)(inst->y - prog->start)); |
960 | | break; |
961 | | case I_ANY: |
962 | | puts("any"); |
963 | | break; |
964 | | case I_ANYNL: |
965 | | puts("anynl"); |
966 | | break; |
967 | | case I_CHAR: |
968 | | printf(inst->c >= 32 && inst->c < 127 ? "char '%c'\n" |
969 | | : "char U+%04X\n", |
970 | | inst->c); |
971 | | break; |
972 | | case I_CCLASS: |
973 | | puts("cclass"); |
974 | | break; |
975 | | case I_NCCLASS: |
976 | | puts("ncclass"); |
977 | | break; |
978 | | case I_REF: |
979 | | printf("ref %d\n", inst->n); |
980 | | break; |
981 | | case I_BOL: |
982 | | puts("bol"); |
983 | | break; |
984 | | case I_EOL: |
985 | | puts("eol"); |
986 | | break; |
987 | | case I_WORD: |
988 | | puts("word"); |
989 | | break; |
990 | | case I_NWORD: |
991 | | puts("nword"); |
992 | | break; |
993 | | case I_LPAR: |
994 | | printf("lpar %d\n", inst->n); |
995 | | break; |
996 | | case I_RPAR: |
997 | | printf("rpar %d\n", inst->n); |
998 | | break; |
999 | | } |
1000 | | } |
1001 | | } |
1002 | | #endif |
1003 | | |
1004 | 2.07k | Reprog *re_regcomp(const char *pattern, int cflags, const char **errorp) { |
1005 | 2.07k | Reprog *prog; |
1006 | 2.07k | Restate *g; |
1007 | 2.07k | Renode *node; |
1008 | 2.07k | Reinst *split, *jump; |
1009 | 2.07k | int i; |
1010 | 2.07k | unsigned int ncount; |
1011 | 2.07k | size_t pattern_len = strlen(pattern); |
1012 | | |
1013 | 2.07k | if (pattern_len > 10000) { |
1014 | | /* Avoid stack exhaustion in recursive parseatom() et.al. */ |
1015 | 9 | if (errorp) |
1016 | 9 | *errorp = "regexp pattern too long (max 10000)"; |
1017 | 9 | return NULL; |
1018 | 9 | } |
1019 | | |
1020 | 2.07k | prog = rd_calloc(1, sizeof(Reprog)); |
1021 | 2.07k | g = &prog->g; |
1022 | 2.07k | g->prog = prog; |
1023 | 2.07k | g->pstart = g->pend = rd_malloc(sizeof(Renode) * pattern_len * 2); |
1024 | | |
1025 | 2.07k | if (setjmp(g->kaboom)) { |
1026 | 1.12k | if (errorp) |
1027 | 1.12k | *errorp = g->error; |
1028 | 1.12k | rd_free(g->pstart); |
1029 | 1.12k | rd_free(prog); |
1030 | 1.12k | return NULL; |
1031 | 1.12k | } |
1032 | | |
1033 | 942 | g->source = pattern; |
1034 | 942 | g->ncclass = 0; |
1035 | 942 | g->nsub = 1; |
1036 | 34.0k | for (i = 0; i < MAXSUB; ++i) |
1037 | 33.1k | g->sub[i] = 0; |
1038 | | |
1039 | 942 | g->prog->flags = cflags; |
1040 | | |
1041 | 942 | next(g); |
1042 | 942 | node = parsealt(g); |
1043 | 942 | if (g->lookahead == ')') |
1044 | 21 | die(g, "unmatched ')'"); |
1045 | 942 | if (g->lookahead != 0) |
1046 | 0 | die(g, "syntax error"); |
1047 | | |
1048 | 942 | g->prog->nsub = g->nsub; |
1049 | 942 | ncount = count(node); |
1050 | 942 | if (ncount > 10000) |
1051 | 45 | die(g, "regexp graph too large"); |
1052 | 942 | g->prog->start = g->prog->end = |
1053 | 942 | rd_malloc((ncount + 6) * sizeof(Reinst)); |
1054 | | |
1055 | 942 | split = emit(g->prog, I_SPLIT); |
1056 | 942 | split->x = split + 3; |
1057 | 942 | split->y = split + 1; |
1058 | 942 | emit(g->prog, I_ANYNL); |
1059 | 942 | jump = emit(g->prog, I_JUMP); |
1060 | 942 | jump->x = split; |
1061 | 942 | emit(g->prog, I_LPAR); |
1062 | 942 | compile(g->prog, node); |
1063 | 942 | emit(g->prog, I_RPAR); |
1064 | 942 | emit(g->prog, I_END); |
1065 | | |
1066 | | #ifdef TEST |
1067 | | dumpnode(node); |
1068 | | putchar('\n'); |
1069 | | dumpprog(g->prog); |
1070 | | #endif |
1071 | | |
1072 | 942 | rd_free(g->pstart); |
1073 | | |
1074 | 942 | if (errorp) |
1075 | 942 | *errorp = NULL; |
1076 | 942 | return g->prog; |
1077 | 2.07k | } |
1078 | | |
1079 | 942 | void re_regfree(Reprog *prog) { |
1080 | 942 | if (prog) { |
1081 | 942 | rd_free(prog->start); |
1082 | 942 | rd_free(prog); |
1083 | 942 | } |
1084 | 942 | } |
1085 | | |
1086 | | /* Match */ |
1087 | | |
1088 | 0 | static int isnewline(int c) { |
1089 | 0 | return c == 0xA || c == 0xD || c == 0x2028 || c == 0x2029; |
1090 | 0 | } |
1091 | | |
1092 | 0 | static int iswordchar(int c) { |
1093 | 0 | return c == '_' || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || |
1094 | 0 | (c >= '0' && c <= '9'); |
1095 | 0 | } |
1096 | | |
1097 | 0 | static int incclass(Reclass *cc, Rune c) { |
1098 | 0 | Rune *p; |
1099 | 0 | for (p = cc->spans; p < cc->end; p += 2) |
1100 | 0 | if (p[0] <= c && c <= p[1]) |
1101 | 0 | return 1; |
1102 | 0 | return 0; |
1103 | 0 | } |
1104 | | |
1105 | 0 | static int incclasscanon(Reclass *cc, Rune c) { |
1106 | 0 | Rune *p, r; |
1107 | 0 | for (p = cc->spans; p < cc->end; p += 2) |
1108 | 0 | for (r = p[0]; r <= p[1]; ++r) |
1109 | 0 | if (c == canon(r)) |
1110 | 0 | return 1; |
1111 | 0 | return 0; |
1112 | 0 | } |
1113 | | |
1114 | 0 | static int strncmpcanon(const char *a, const char *b, unsigned int n) { |
1115 | 0 | Rune ra, rb; |
1116 | 0 | int c; |
1117 | 0 | while (n--) { |
1118 | 0 | if (!*a) |
1119 | 0 | return -1; |
1120 | 0 | if (!*b) |
1121 | 0 | return 1; |
1122 | 0 | a += chartorune(&ra, a); |
1123 | 0 | b += chartorune(&rb, b); |
1124 | 0 | c = canon(ra) - canon(rb); |
1125 | 0 | if (c) |
1126 | 0 | return c; |
1127 | 0 | } |
1128 | 0 | return 0; |
1129 | 0 | } |
1130 | | |
1131 | | struct Rethread { |
1132 | | Reinst *pc; |
1133 | | const char *sp; |
1134 | | Resub sub; |
1135 | | }; |
1136 | | |
1137 | 0 | static void spawn(Rethread *t, Reinst *pc, const char *sp, Resub *sub) { |
1138 | 0 | t->pc = pc; |
1139 | 0 | t->sp = sp; |
1140 | 0 | memcpy(&t->sub, sub, sizeof t->sub); |
1141 | 0 | } |
1142 | | |
1143 | | static int |
1144 | 0 | match(Reinst *pc, const char *sp, const char *bol, int flags, Resub *out) { |
1145 | 0 | Rethread ready[MAXTHREAD]; |
1146 | 0 | Resub scratch; |
1147 | 0 | Resub sub; |
1148 | 0 | Rune c; |
1149 | 0 | unsigned int nready; |
1150 | 0 | int i; |
1151 | | |
1152 | | /* queue initial thread */ |
1153 | 0 | spawn(ready + 0, pc, sp, out); |
1154 | 0 | nready = 1; |
1155 | | |
1156 | | /* run threads in stack order */ |
1157 | 0 | while (nready > 0) { |
1158 | 0 | --nready; |
1159 | 0 | pc = ready[nready].pc; |
1160 | 0 | sp = ready[nready].sp; |
1161 | 0 | memcpy(&sub, &ready[nready].sub, sizeof sub); |
1162 | 0 | for (;;) { |
1163 | 0 | switch (pc->opcode) { |
1164 | 0 | case I_END: |
1165 | 0 | for (i = 0; i < MAXSUB; ++i) { |
1166 | 0 | out->sub[i].sp = sub.sub[i].sp; |
1167 | 0 | out->sub[i].ep = sub.sub[i].ep; |
1168 | 0 | } |
1169 | 0 | return 1; |
1170 | 0 | case I_JUMP: |
1171 | 0 | pc = pc->x; |
1172 | 0 | continue; |
1173 | 0 | case I_SPLIT: |
1174 | 0 | if (nready >= MAXTHREAD) { |
1175 | 0 | fprintf( |
1176 | 0 | stderr, |
1177 | 0 | "regexec: backtrack overflow!\n"); |
1178 | 0 | return 0; |
1179 | 0 | } |
1180 | 0 | spawn(&ready[nready++], pc->y, sp, &sub); |
1181 | 0 | pc = pc->x; |
1182 | 0 | continue; |
1183 | | |
1184 | 0 | case I_PLA: |
1185 | 0 | if (!match(pc->x, sp, bol, flags, &sub)) |
1186 | 0 | goto dead; |
1187 | 0 | pc = pc->y; |
1188 | 0 | continue; |
1189 | 0 | case I_NLA: |
1190 | 0 | memcpy(&scratch, &sub, sizeof scratch); |
1191 | 0 | if (match(pc->x, sp, bol, flags, &scratch)) |
1192 | 0 | goto dead; |
1193 | 0 | pc = pc->y; |
1194 | 0 | continue; |
1195 | | |
1196 | 0 | case I_ANYNL: |
1197 | 0 | sp += chartorune(&c, sp); |
1198 | 0 | if (c == 0) |
1199 | 0 | goto dead; |
1200 | 0 | break; |
1201 | 0 | case I_ANY: |
1202 | 0 | sp += chartorune(&c, sp); |
1203 | 0 | if (c == 0) |
1204 | 0 | goto dead; |
1205 | 0 | if (isnewline(c)) |
1206 | 0 | goto dead; |
1207 | 0 | break; |
1208 | 0 | case I_CHAR: |
1209 | 0 | sp += chartorune(&c, sp); |
1210 | 0 | if (c == 0) |
1211 | 0 | goto dead; |
1212 | 0 | if (flags & REG_ICASE) |
1213 | 0 | c = canon(c); |
1214 | 0 | if (c != pc->c) |
1215 | 0 | goto dead; |
1216 | 0 | break; |
1217 | 0 | case I_CCLASS: |
1218 | 0 | sp += chartorune(&c, sp); |
1219 | 0 | if (c == 0) |
1220 | 0 | goto dead; |
1221 | 0 | if (flags & REG_ICASE) { |
1222 | 0 | if (!incclasscanon(pc->cc, canon(c))) |
1223 | 0 | goto dead; |
1224 | 0 | } else { |
1225 | 0 | if (!incclass(pc->cc, c)) |
1226 | 0 | goto dead; |
1227 | 0 | } |
1228 | 0 | break; |
1229 | 0 | case I_NCCLASS: |
1230 | 0 | sp += chartorune(&c, sp); |
1231 | 0 | if (c == 0) |
1232 | 0 | goto dead; |
1233 | 0 | if (flags & REG_ICASE) { |
1234 | 0 | if (incclasscanon(pc->cc, canon(c))) |
1235 | 0 | goto dead; |
1236 | 0 | } else { |
1237 | 0 | if (incclass(pc->cc, c)) |
1238 | 0 | goto dead; |
1239 | 0 | } |
1240 | 0 | break; |
1241 | 0 | case I_REF: |
1242 | 0 | i = (int)(sub.sub[pc->n].ep - |
1243 | 0 | sub.sub[pc->n].sp); |
1244 | 0 | if (flags & REG_ICASE) { |
1245 | 0 | if (strncmpcanon(sp, sub.sub[pc->n].sp, |
1246 | 0 | i)) |
1247 | 0 | goto dead; |
1248 | 0 | } else { |
1249 | 0 | if (strncmp(sp, sub.sub[pc->n].sp, i)) |
1250 | 0 | goto dead; |
1251 | 0 | } |
1252 | 0 | if (i > 0) |
1253 | 0 | sp += i; |
1254 | 0 | break; |
1255 | | |
1256 | 0 | case I_BOL: |
1257 | 0 | if (sp == bol && !(flags & REG_NOTBOL)) |
1258 | 0 | break; |
1259 | 0 | if (flags & REG_NEWLINE) |
1260 | 0 | if (sp > bol && isnewline(sp[-1])) |
1261 | 0 | break; |
1262 | 0 | goto dead; |
1263 | 0 | case I_EOL: |
1264 | 0 | if (*sp == 0) |
1265 | 0 | break; |
1266 | 0 | if (flags & REG_NEWLINE) |
1267 | 0 | if (isnewline(*sp)) |
1268 | 0 | break; |
1269 | 0 | goto dead; |
1270 | 0 | case I_WORD: |
1271 | 0 | i = sp > bol && iswordchar(sp[-1]); |
1272 | 0 | i ^= iswordchar(sp[0]); |
1273 | 0 | if (i) |
1274 | 0 | break; |
1275 | 0 | goto dead; |
1276 | 0 | case I_NWORD: |
1277 | 0 | i = sp > bol && iswordchar(sp[-1]); |
1278 | 0 | i ^= iswordchar(sp[0]); |
1279 | 0 | if (!i) |
1280 | 0 | break; |
1281 | 0 | goto dead; |
1282 | | |
1283 | 0 | case I_LPAR: |
1284 | 0 | sub.sub[pc->n].sp = sp; |
1285 | 0 | break; |
1286 | 0 | case I_RPAR: |
1287 | 0 | sub.sub[pc->n].ep = sp; |
1288 | 0 | break; |
1289 | 0 | default: |
1290 | 0 | goto dead; |
1291 | 0 | } |
1292 | 0 | pc = pc + 1; |
1293 | 0 | } |
1294 | 0 | dead:; |
1295 | 0 | } |
1296 | 0 | return 0; |
1297 | 0 | } |
1298 | | |
1299 | 0 | int re_regexec(Reprog *prog, const char *sp, Resub *sub, int eflags) { |
1300 | 0 | Resub scratch; |
1301 | 0 | int i; |
1302 | |
|
1303 | 0 | if (!sub) |
1304 | 0 | sub = &scratch; |
1305 | |
|
1306 | 0 | sub->nsub = prog->nsub; |
1307 | 0 | for (i = 0; i < MAXSUB; ++i) |
1308 | 0 | sub->sub[i].sp = sub->sub[i].ep = NULL; |
1309 | |
|
1310 | 0 | return !match(prog->start, sp, sp, prog->flags | eflags, sub); |
1311 | 0 | } |
1312 | | |
1313 | | #ifdef TEST |
1314 | | int main(int argc, char **argv) { |
1315 | | const char *error; |
1316 | | const char *s; |
1317 | | Reprog *p; |
1318 | | Resub m; |
1319 | | unsigned int i; |
1320 | | |
1321 | | if (argc > 1) { |
1322 | | p = regcomp(argv[1], 0, &error); |
1323 | | if (!p) { |
1324 | | fprintf(stderr, "regcomp: %s\n", error); |
1325 | | return 1; |
1326 | | } |
1327 | | |
1328 | | if (argc > 2) { |
1329 | | s = argv[2]; |
1330 | | printf("nsub = %d\n", p->nsub); |
1331 | | if (!regexec(p, s, &m, 0)) { |
1332 | | for (i = 0; i < m.nsub; ++i) { |
1333 | | int n = m.sub[i].ep - m.sub[i].sp; |
1334 | | if (n > 0) |
1335 | | printf( |
1336 | | "match %d: s=%d e=%d n=%d " |
1337 | | "'%.*s'\n", |
1338 | | i, (int)(m.sub[i].sp - s), |
1339 | | (int)(m.sub[i].ep - s), n, |
1340 | | n, m.sub[i].sp); |
1341 | | else |
1342 | | printf("match %d: n=0 ''\n", i); |
1343 | | } |
1344 | | } else { |
1345 | | printf("no match\n"); |
1346 | | } |
1347 | | } |
1348 | | } |
1349 | | |
1350 | | return 0; |
1351 | | } |
1352 | | #endif |