]> git.proxmox.com Git - mirror_edk2.git/blame - MdeModulePkg/Universal/RegularExpressionDxe/Oniguruma/regexec.c
projects / mirror_edk2.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
MdeModulePkg: Regular expression protocol
[mirror_edk2.git] / MdeModulePkg / Universal / RegularExpressionDxe / Oniguruma / regexec.c
CommitLineData
db3b92b4
CS		 1/**********************************************************************\r
2 regexec.c - Oniguruma (regular expression library)\r
3**********************************************************************/\r
4/*-\r
5 * Copyright (c) 2002-2008 K.Kosako <sndgk393 AT ybb DOT ne DOT jp>\r
6 * All rights reserved.\r
7 *\r
8 * Copyright (c) 2015, Hewlett Packard Enterprise Development, L.P.<BR>\r
9 *\r
10 * Redistribution and use in source and binary forms, with or without\r
11 * modification, are permitted provided that the following conditions\r
12 * are met:\r
13 * 1. Redistributions of source code must retain the above copyright\r
14 * notice, this list of conditions and the following disclaimer.\r
15 * 2. Redistributions in binary form must reproduce the above copyright\r
16 * notice, this list of conditions and the following disclaimer in the\r
17 * documentation and/or other materials provided with the distribution.\r
18 *\r
19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND\r
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE\r
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\r
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE\r
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL\r
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS\r
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)\r
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT\r
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY\r
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF\r
29 * SUCH DAMAGE.\r
30 */\r
31\r
32#include "regint.h"\r
33\r
34#define USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE\r
35\r
36#ifdef USE_CRNL_AS_LINE_TERMINATOR\r
37#define ONIGENC_IS_MBC_CRNL(enc,p,end) \\r
38 (ONIGENC_MBC_TO_CODE(enc,p,end) == 13 && \\r
39 ONIGENC_IS_MBC_NEWLINE(enc,(p+enclen(enc,p)),end))\r
40#endif\r
41\r
42#ifdef USE_CAPTURE_HISTORY\r
43static void history_tree_free(OnigCaptureTreeNode* node);\r
44\r
45static void\r
46history_tree_clear(OnigCaptureTreeNode* node)\r
47{\r
48 int i;\r
49\r
50 if (IS_NOT_NULL(node)) {\r
51 for (i = 0; i < node->num_childs; i++) {\r
52 if (IS_NOT_NULL(node->childs[i])) {\r
53 history_tree_free(node->childs[i]);\r
54 }\r
55 }\r
56 for (i = 0; i < node->allocated; i++) {\r
57 node->childs[i] = (OnigCaptureTreeNode* )0;\r
58 }\r
59 node->num_childs = 0;\r
60 node->beg = ONIG_REGION_NOTPOS;\r
61 node->end = ONIG_REGION_NOTPOS;\r
62 node->group = -1;\r
63 }\r
64}\r
65\r
66static void\r
67history_tree_free(OnigCaptureTreeNode* node)\r
68{\r
69 history_tree_clear(node);\r
70 xfree(node);\r
71}\r
72\r
73static void\r
74history_root_free(OnigRegion* r)\r
75{\r
76 if (IS_NOT_NULL(r->history_root)) {\r
77 history_tree_free(r->history_root);\r
78 r->history_root = (OnigCaptureTreeNode* )0;\r
79 }\r
80}\r
81\r
82static OnigCaptureTreeNode*\r
83history_node_new(void)\r
84{\r
85 OnigCaptureTreeNode* node;\r
86\r
87 node = (OnigCaptureTreeNode* )xmalloc(sizeof(OnigCaptureTreeNode));\r
88 CHECK_NULL_RETURN(node);\r
89 node->childs = (OnigCaptureTreeNode** )0;\r
90 node->allocated = 0;\r
91 node->num_childs = 0;\r
92 node->group = -1;\r
93 node->beg = ONIG_REGION_NOTPOS;\r
94 node->end = ONIG_REGION_NOTPOS;\r
95\r
96 return node;\r
97}\r
98\r
99static int\r
100history_tree_add_child(OnigCaptureTreeNode* parent, OnigCaptureTreeNode* child)\r
101{\r
102#define HISTORY_TREE_INIT_ALLOC_SIZE 8\r
103\r
104 if (parent->num_childs >= parent->allocated) {\r
105 int n, i;\r
106\r
107 if (IS_NULL(parent->childs)) {\r
108 n = HISTORY_TREE_INIT_ALLOC_SIZE;\r
109 parent->childs =\r
110 (OnigCaptureTreeNode** )xmalloc(sizeof(OnigCaptureTreeNode*) * n);\r
111 }\r
112 else {\r
113 n = parent->allocated * 2;\r
114 parent->childs =\r
115 (OnigCaptureTreeNode** )xrealloc(parent->childs,\r
116 sizeof(OnigCaptureTreeNode*) * n,\r
117 sizeof(OnigCaptureTreeNode*) * parent->allocated);\r
118 }\r
119 CHECK_NULL_RETURN_MEMERR(parent->childs);\r
120 for (i = parent->allocated; i < n; i++) {\r
121 parent->childs[i] = (OnigCaptureTreeNode* )0;\r
122 }\r
123 parent->allocated = n;\r
124 }\r
125\r
126 parent->childs[parent->num_childs] = child;\r
127 parent->num_childs++;\r
128 return 0;\r
129}\r
130\r
131static OnigCaptureTreeNode*\r
132history_tree_clone(OnigCaptureTreeNode* node)\r
133{\r
134 int i;\r
135 OnigCaptureTreeNode *clone, *child;\r
136\r
137 clone = history_node_new();\r
138 CHECK_NULL_RETURN(clone);\r
139\r
140 clone->beg = node->beg;\r
141 clone->end = node->end;\r
142 for (i = 0; i < node->num_childs; i++) {\r
143 child = history_tree_clone(node->childs[i]);\r
144 if (IS_NULL(child)) {\r
145 history_tree_free(clone);\r
146 return (OnigCaptureTreeNode* )0;\r
147 }\r
148 history_tree_add_child(clone, child);\r
149 }\r
150\r
151 return clone;\r
152}\r
153\r
154extern OnigCaptureTreeNode*\r
155onig_get_capture_tree(OnigRegion* region)\r
156{\r
157 return region->history_root;\r
158}\r
159#endif /* USE_CAPTURE_HISTORY */\r
160\r
161extern void\r
162onig_region_clear(OnigRegion* region)\r
163{\r
164 int i;\r
165\r
166 for (i = 0; i < region->num_regs; i++) {\r
167 region->beg[i] = region->end[i] = ONIG_REGION_NOTPOS;\r
168 }\r
169#ifdef USE_CAPTURE_HISTORY\r
170 history_root_free(region);\r
171#endif\r
172}\r
173\r
174extern int\r
175onig_region_resize(OnigRegion* region, int n)\r
176{\r
177 region->num_regs = n;\r
178\r
179 if (n < ONIG_NREGION)\r
180 n = ONIG_NREGION;\r
181\r
182 if (region->allocated == 0) {\r
183 region->beg = (int* )xmalloc(n * sizeof(int));\r
184 region->end = (int* )xmalloc(n * sizeof(int));\r
185\r
186 if (region->beg == 0 || region->end == 0)\r
187 return ONIGERR_MEMORY;\r
188\r
189 region->allocated = n;\r
190 }\r
191 else if (region->allocated < n) {\r
192 region->beg = (int* )xrealloc(region->beg, n * sizeof(int), region->allocated * sizeof(int));\r
193 region->end = (int* )xrealloc(region->end, n * sizeof(int), region->allocated * sizeof(int));\r
194\r
195 if (region->beg == 0 || region->end == 0)\r
196 return ONIGERR_MEMORY;\r
197\r
198 region->allocated = n;\r
199 }\r
200\r
201 return 0;\r
202}\r
203\r
204static int\r
205onig_region_resize_clear(OnigRegion* region, int n)\r
206{\r
207 int r;\r
208 \r
209 r = onig_region_resize(region, n);\r
210 if (r != 0) return r;\r
211 onig_region_clear(region);\r
212 return 0;\r
213}\r
214 \r
215extern int\r
216onig_region_set(OnigRegion* region, int at, int beg, int end)\r
217{\r
218 if (at < 0) return ONIGERR_INVALID_ARGUMENT;\r
219\r
220 if (at >= region->allocated) {\r
221 int r = onig_region_resize(region, at + 1);\r
222 if (r < 0) return r;\r
223 }\r
224 \r
225 region->beg[at] = beg;\r
226 region->end[at] = end;\r
227 return 0;\r
228}\r
229\r
230extern void\r
231onig_region_init(OnigRegion* region)\r
232{\r
233 region->num_regs = 0;\r
234 region->allocated = 0;\r
235 region->beg = (int* )0;\r
236 region->end = (int* )0;\r
237 region->history_root = (OnigCaptureTreeNode* )0;\r
238}\r
239\r
240extern OnigRegion*\r
241onig_region_new(void)\r
242{\r
243 OnigRegion* r;\r
244\r
245 r = (OnigRegion* )xmalloc(sizeof(OnigRegion));\r
246 onig_region_init(r);\r
247 return r;\r
248}\r
249\r
250extern void\r
251onig_region_free(OnigRegion* r, int free_self)\r
252{\r
253 if (r) {\r
254 if (r->allocated > 0) {\r
255 if (r->beg) xfree(r->beg);\r
256 if (r->end) xfree(r->end);\r
257 r->allocated = 0;\r
258 }\r
259#ifdef USE_CAPTURE_HISTORY\r
260 history_root_free(r);\r
261#endif\r
262 if (free_self) xfree(r);\r
263 }\r
264}\r
265\r
266extern void\r
267onig_region_copy(OnigRegion* to, OnigRegion* from)\r
268{\r
269#define RREGC_SIZE (sizeof(int) * from->num_regs)\r
270 int i;\r
271\r
272 if (to == from) return;\r
273\r
274 if (to->allocated == 0) {\r
275 if (from->num_regs > 0) {\r
276 to->beg = (int* )xmalloc(RREGC_SIZE);\r
277 to->end = (int* )xmalloc(RREGC_SIZE);\r
278 to->allocated = from->num_regs;\r
279 }\r
280 }\r
281 else if (to->allocated < from->num_regs) {\r
282 to->beg = (int* )xrealloc(to->beg, RREGC_SIZE, sizeof(int) * to->allocated);\r
283 to->end = (int* )xrealloc(to->end, RREGC_SIZE, sizeof(int) * to->allocated);\r
284 to->allocated = from->num_regs;\r
285 }\r
286\r
287 for (i = 0; i < from->num_regs; i++) {\r
288 to->beg[i] = from->beg[i];\r
289 to->end[i] = from->end[i];\r
290 }\r
291 to->num_regs = from->num_regs;\r
292\r
293#ifdef USE_CAPTURE_HISTORY\r
294 history_root_free(to);\r
295\r
296 if (IS_NOT_NULL(from->history_root)) {\r
297 to->history_root = history_tree_clone(from->history_root);\r
298 }\r
299#endif\r
300}\r
301\r
302\r
303/** stack **/\r
304#define INVALID_STACK_INDEX -1\r
305\r
306/* stack type */\r
307/* used by normal-POP */\r
308#define STK_ALT 0x0001\r
309#define STK_LOOK_BEHIND_NOT 0x0002\r
310#define STK_POS_NOT 0x0003\r
311/* handled by normal-POP */\r
312#define STK_MEM_START 0x0100\r
313#define STK_MEM_END 0x8200\r
314#define STK_REPEAT_INC 0x0300\r
315#define STK_STATE_CHECK_MARK 0x1000\r
316/* avoided by normal-POP */\r
317#define STK_NULL_CHECK_START 0x3000\r
318#define STK_NULL_CHECK_END 0x5000 /* for recursive call */\r
319#define STK_MEM_END_MARK 0x8400\r
320#define STK_POS 0x0500 /* used when POP-POS */\r
321#define STK_STOP_BT 0x0600 /* mark for "(?>...)" */\r
322#define STK_REPEAT 0x0700\r
323#define STK_CALL_FRAME 0x0800\r
324#define STK_RETURN 0x0900\r
325#define STK_VOID 0x0a00 /* for fill a blank */\r
326\r
327/* stack type check mask */\r
328#define STK_MASK_POP_USED 0x00ff\r
329#define STK_MASK_TO_VOID_TARGET 0x10ff\r
330#define STK_MASK_MEM_END_OR_MARK 0x8000 /* MEM_END or MEM_END_MARK */\r
331\r
332#ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE\r
333#define MATCH_ARG_INIT(msa, arg_option, arg_region, arg_start) do {\\r
334 (msa).stack_p = (void* )0;\\r
335 (msa).options = (arg_option);\\r
336 (msa).region = (arg_region);\\r
337 (msa).start = (arg_start);\\r
338 (msa).best_len = ONIG_MISMATCH;\\r
339} while(0)\r
340#else\r
341#define MATCH_ARG_INIT(msa, arg_option, arg_region, arg_start) do {\\r
342 (msa).stack_p = (void* )0;\\r
343 (msa).options = (arg_option);\\r
344 (msa).region = (arg_region);\\r
345 (msa).start = (arg_start);\\r
346} while(0)\r
347#endif\r
348\r
349#ifdef USE_COMBINATION_EXPLOSION_CHECK\r
350\r
351#define STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE 16\r
352\r
353#define STATE_CHECK_BUFF_INIT(msa, str_len, offset, state_num) do { \\r
354 if ((state_num) > 0 && str_len >= STATE_CHECK_STRING_THRESHOLD_LEN) {\\r
355 unsigned int size = (unsigned int )(((str_len) + 1) * (state_num) + 7) >> 3;\\r
356 offset = ((offset) * (state_num)) >> 3;\\r
357 if (size > 0 && offset < size && size < STATE_CHECK_BUFF_MAX_SIZE) {\\r
358 if (size >= STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE) \\r
359 (msa).state_check_buff = (void* )xmalloc(size);\\r
360 else \\r
361 (msa).state_check_buff = (void* )xalloca(size);\\r
362 xmemset(((char* )((msa).state_check_buff)+(offset)), 0, \\r
363 (size_t )(size - (offset))); \\r
364 (msa).state_check_buff_size = size;\\r
365 }\\r
366 else {\\r
367 (msa).state_check_buff = (void* )0;\\r
368 (msa).state_check_buff_size = 0;\\r
369 }\\r
370 }\\r
371 else {\\r
372 (msa).state_check_buff = (void* )0;\\r
373 (msa).state_check_buff_size = 0;\\r
374 }\\r
375 } while(0)\r
376\r
377#define MATCH_ARG_FREE(msa) do {\\r
378 if ((msa).stack_p) xfree((msa).stack_p);\\r
379 if ((msa).state_check_buff_size >= STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE) { \\r
380 if ((msa).state_check_buff) xfree((msa).state_check_buff);\\r
381 }\\r
382} while(0)\r
383#else\r
384#define STATE_CHECK_BUFF_INIT(msa, str_len, offset, state_num)\r
385#define MATCH_ARG_FREE(msa) if ((msa).stack_p) xfree((msa).stack_p)\r
386#endif\r
387\r
388\r
389\r
390#define STACK_INIT(alloc_addr, ptr_num, stack_num) do {\\r
391 if (msa->stack_p) {\\r
392 alloc_addr = (char* )xmalloc(sizeof(char*) * (ptr_num));\\r
393 stk_alloc = (OnigStackType* )(msa->stack_p);\\r
394 stk_base = stk_alloc;\\r
395 stk = stk_base;\\r
396 stk_end = stk_base + msa->stack_n;\\r
397 }\\r
398 else {\\r
399 alloc_addr = (char* )xmalloc(sizeof(char*) * (ptr_num)\\r
400 + sizeof(OnigStackType) * (stack_num));\\r
401 stk_alloc = (OnigStackType* )(alloc_addr + sizeof(char*) * (ptr_num));\\r
402 stk_base = stk_alloc;\\r
403 stk = stk_base;\\r
404 stk_end = stk_base + (stack_num);\\r
405 }\\r
406} while(0)\r
407\r
408#define STACK_SAVE do{\\r
409 if (stk_base != stk_alloc) {\\r
410 msa->stack_p = stk_base;\\r
411 msa->stack_n = (int)(stk_end - stk_base);\\r
412 };\\r
413} while(0)\r
414\r
415static unsigned int MatchStackLimitSize = DEFAULT_MATCH_STACK_LIMIT_SIZE;\r
416\r
417extern unsigned int\r
418onig_get_match_stack_limit_size(void)\r
419{\r
420 return MatchStackLimitSize;\r
421}\r
422\r
423extern int\r
424onig_set_match_stack_limit_size(unsigned int size)\r
425{\r
426 MatchStackLimitSize = size;\r
427 return 0;\r
428}\r
429\r
430static int\r
431stack_double(OnigStackType** arg_stk_base, OnigStackType** arg_stk_end,\r
432 OnigStackType** arg_stk, OnigStackType* stk_alloc, OnigMatchArg* msa)\r
433{\r
434 unsigned int n;\r
435 OnigStackType *x, *stk_base, *stk_end, *stk;\r
436\r
437 stk_base = *arg_stk_base;\r
438 stk_end = *arg_stk_end;\r
439 stk = *arg_stk;\r
440\r
441 n = (unsigned int)(stk_end - stk_base);\r
442 if (stk_base == stk_alloc && IS_NULL(msa->stack_p)) {\r
443 x = (OnigStackType* )xmalloc(sizeof(OnigStackType) * n * 2);\r
444 if (IS_NULL(x)) {\r
445 STACK_SAVE;\r
446 return ONIGERR_MEMORY;\r
447 }\r
448 xmemcpy(x, stk_base, n * sizeof(OnigStackType));\r
449 n *= 2;\r
450 }\r
451 else {\r
452 n *= 2;\r
453 if (MatchStackLimitSize != 0 && n > MatchStackLimitSize) {\r
454 if ((unsigned int )(stk_end - stk_base) == MatchStackLimitSize)\r
455 return ONIGERR_MATCH_STACK_LIMIT_OVER;\r
456 else\r
457 n = MatchStackLimitSize;\r
458 }\r
459 x = (OnigStackType* )xrealloc(stk_base, sizeof(OnigStackType) * n, sizeof(OnigStackType) * (stk_end - stk_base));\r
460 if (IS_NULL(x)) {\r
461 STACK_SAVE;\r
462 return ONIGERR_MEMORY;\r
463 }\r
464 }\r
465 *arg_stk = x + (stk - stk_base);\r
466 *arg_stk_base = x;\r
467 *arg_stk_end = x + n;\r
468 return 0;\r
469}\r
470\r
471#define STACK_ENSURE(n) do {\\r
472 if (stk_end - stk < (n)) {\\r
473 int r = stack_double(&stk_base, &stk_end, &stk, stk_alloc, msa);\\r
474 if (r != 0) { STACK_SAVE; return r; } \\r
475 }\\r
476} while(0)\r
477\r
478#define STACK_AT(index) (stk_base + (index))\r
479#define GET_STACK_INDEX(stk) ((OnigStackIndex)((stk) - stk_base))\r
480\r
481#define STACK_PUSH_TYPE(stack_type) do {\\r
482 STACK_ENSURE(1);\\r
483 stk->type = (stack_type);\\r
484 STACK_INC;\\r
485} while(0)\r
486\r
487#define IS_TO_VOID_TARGET(stk) (((stk)->type & STK_MASK_TO_VOID_TARGET) != 0)\r
488\r
489#ifdef USE_COMBINATION_EXPLOSION_CHECK\r
490#define STATE_CHECK_POS(s,snum) \\r
491 (((s) - str) * num_comb_exp_check + ((snum) - 1))\r
492#define STATE_CHECK_VAL(v,snum) do {\\r
493 if (state_check_buff != NULL) {\\r
494 int x = STATE_CHECK_POS(s,snum);\\r
495 (v) = state_check_buff[x/8] & (1<<(x%8));\\r
496 }\\r
497 else (v) = 0;\\r
498} while(0)\r
499\r
500\r
501#define ELSE_IF_STATE_CHECK_MARK(stk) \\r
502 else if ((stk)->type == STK_STATE_CHECK_MARK) { \\r
503 int x = STATE_CHECK_POS(stk->u.state.pstr, stk->u.state.state_check);\\r
504 state_check_buff[x/8] |= (1<<(x%8)); \\r
505 }\r
506\r
507#define STACK_PUSH(stack_type,pat,s,sprev) do {\\r
508 STACK_ENSURE(1);\\r
509 stk->type = (stack_type);\\r
510 stk->u.state.pcode = (pat);\\r
511 stk->u.state.pstr = (s);\\r
512 stk->u.state.pstr_prev = (sprev);\\r
513 stk->u.state.state_check = 0;\\r
514 STACK_INC;\\r
515} while(0)\r
516\r
517#define STACK_PUSH_ENSURED(stack_type,pat) do {\\r
518 stk->type = (stack_type);\\r
519 stk->u.state.pcode = (pat);\\r
520 stk->u.state.state_check = 0;\\r
521 STACK_INC;\\r
522} while(0)\r
523\r
524#define STACK_PUSH_ALT_WITH_STATE_CHECK(pat,s,sprev,snum) do {\\r
525 STACK_ENSURE(1);\\r
526 stk->type = STK_ALT;\\r
527 stk->u.state.pcode = (pat);\\r
528 stk->u.state.pstr = (s);\\r
529 stk->u.state.pstr_prev = (sprev);\\r
530 stk->u.state.state_check = ((state_check_buff != NULL) ? (snum) : 0);\\r
531 STACK_INC;\\r
532} while(0)\r
533\r
534#define STACK_PUSH_STATE_CHECK(s,snum) do {\\r
535 if (state_check_buff != NULL) {\\r
536 STACK_ENSURE(1);\\r
537 stk->type = STK_STATE_CHECK_MARK;\\r
538 stk->u.state.pstr = (s);\\r
539 stk->u.state.state_check = (snum);\\r
540 STACK_INC;\\r
541 }\\r
542} while(0)\r
543\r
544#else /* USE_COMBINATION_EXPLOSION_CHECK */\r
545\r
546#define ELSE_IF_STATE_CHECK_MARK(stk)\r
547\r
548#define STACK_PUSH(stack_type,pat,s,sprev) do {\\r
549 STACK_ENSURE(1);\\r
550 stk->type = (stack_type);\\r
551 stk->u.state.pcode = (pat);\\r
552 stk->u.state.pstr = (s);\\r
553 stk->u.state.pstr_prev = (sprev);\\r
554 STACK_INC;\\r
555} while(0)\r
556\r
557#define STACK_PUSH_ENSURED(stack_type,pat) do {\\r
558 stk->type = (stack_type);\\r
559 stk->u.state.pcode = (pat);\\r
560 STACK_INC;\\r
561} while(0)\r
562#endif /* USE_COMBINATION_EXPLOSION_CHECK */\r
563\r
564#define STACK_PUSH_ALT(pat,s,sprev) STACK_PUSH(STK_ALT,pat,s,sprev)\r
565#define STACK_PUSH_POS(s,sprev) STACK_PUSH(STK_POS,NULL_UCHARP,s,sprev)\r
566#define STACK_PUSH_POS_NOT(pat,s,sprev) STACK_PUSH(STK_POS_NOT,pat,s,sprev)\r
567#define STACK_PUSH_STOP_BT STACK_PUSH_TYPE(STK_STOP_BT)\r
568#define STACK_PUSH_LOOK_BEHIND_NOT(pat,s,sprev) \\r
569 STACK_PUSH(STK_LOOK_BEHIND_NOT,pat,s,sprev)\r
570\r
571#define STACK_PUSH_REPEAT(id, pat) do {\\r
572 STACK_ENSURE(1);\\r
573 stk->type = STK_REPEAT;\\r
574 stk->u.repeat.num = (id);\\r
575 stk->u.repeat.pcode = (pat);\\r
576 stk->u.repeat.count = 0;\\r
577 STACK_INC;\\r
578} while(0)\r
579\r
580#define STACK_PUSH_REPEAT_INC(sindex) do {\\r
581 STACK_ENSURE(1);\\r
582 stk->type = STK_REPEAT_INC;\\r
583 stk->u.repeat_inc.si = (sindex);\\r
584 STACK_INC;\\r
585} while(0)\r
586\r
587#define STACK_PUSH_MEM_START(mnum, s) do {\\r
588 STACK_ENSURE(1);\\r
589 stk->type = STK_MEM_START;\\r
590 stk->u.mem.num = (int)(mnum);\\r
591 stk->u.mem.pstr = (s);\\r
592 stk->u.mem.start = mem_start_stk[mnum];\\r
593 stk->u.mem.end = mem_end_stk[mnum];\\r
594 mem_start_stk[mnum] = GET_STACK_INDEX(stk);\\r
595 mem_end_stk[mnum] = INVALID_STACK_INDEX;\\r
596 STACK_INC;\\r
597} while(0)\r
598\r
599#define STACK_PUSH_MEM_END(mnum, s) do {\\r
600 STACK_ENSURE(1);\\r
601 stk->type = STK_MEM_END;\\r
602 stk->u.mem.num = (mnum);\\r
603 stk->u.mem.pstr = (s);\\r
604 stk->u.mem.start = mem_start_stk[mnum];\\r
605 stk->u.mem.end = mem_end_stk[mnum];\\r
606 mem_end_stk[mnum] = GET_STACK_INDEX(stk);\\r
607 STACK_INC;\\r
608} while(0)\r
609\r
610#define STACK_PUSH_MEM_END_MARK(mnum) do {\\r
611 STACK_ENSURE(1);\\r
612 stk->type = STK_MEM_END_MARK;\\r
613 stk->u.mem.num = (mnum);\\r
614 STACK_INC;\\r
615} while(0)\r
616\r
617#define STACK_GET_MEM_START(mnum, k) do {\\r
618 int level = 0;\\r
619 k = stk;\\r
620 while (k > stk_base) {\\r
621 k--;\\r
622 if ((k->type & STK_MASK_MEM_END_OR_MARK) != 0 \\r
623 && k->u.mem.num == (mnum)) {\\r
624 level++;\\r
625 }\\r
626 else if (k->type == STK_MEM_START && k->u.mem.num == (mnum)) {\\r
627 if (level == 0) break;\\r
628 level--;\\r
629 }\\r
630 }\\r
631} while(0)\r
632\r
633#define STACK_GET_MEM_RANGE(k, mnum, start, end) do {\\r
634 int level = 0;\\r
635 while (k < stk) {\\r
636 if (k->type == STK_MEM_START && k->u.mem.num == (mnum)) {\\r
637 if (level == 0) (start) = k->u.mem.pstr;\\r
638 level++;\\r
639 }\\r
640 else if (k->type == STK_MEM_END && k->u.mem.num == (mnum)) {\\r
641 level--;\\r
642 if (level == 0) {\\r
643 (end) = k->u.mem.pstr;\\r
644 break;\\r
645 }\\r
646 }\\r
647 k++;\\r
648 }\\r
649} while(0)\r
650\r
651#define STACK_PUSH_NULL_CHECK_START(cnum, s) do {\\r
652 STACK_ENSURE(1);\\r
653 stk->type = STK_NULL_CHECK_START;\\r
654 stk->u.null_check.num = (cnum);\\r
655 stk->u.null_check.pstr = (s);\\r
656 STACK_INC;\\r
657} while(0)\r
658\r
659#define STACK_PUSH_NULL_CHECK_END(cnum) do {\\r
660 STACK_ENSURE(1);\\r
661 stk->type = STK_NULL_CHECK_END;\\r
662 stk->u.null_check.num = (cnum);\\r
663 STACK_INC;\\r
664} while(0)\r
665\r
666#define STACK_PUSH_CALL_FRAME(pat) do {\\r
667 STACK_ENSURE(1);\\r
668 stk->type = STK_CALL_FRAME;\\r
669 stk->u.call_frame.ret_addr = (pat);\\r
670 STACK_INC;\\r
671} while(0)\r
672\r
673#define STACK_PUSH_RETURN do {\\r
674 STACK_ENSURE(1);\\r
675 stk->type = STK_RETURN;\\r
676 STACK_INC;\\r
677} while(0)\r
678\r
679\r
680#ifdef ONIG_DEBUG\r
681#define STACK_BASE_CHECK(p, at) \\r
682 if ((p) < stk_base) {\\r
683 fprintf(stderr, "at %s\n", at);\\r
684 goto stack_error;\\r
685 }\r
686#else\r
687#define STACK_BASE_CHECK(p, at)\r
688#endif\r
689\r
690#define STACK_POP_ONE do {\\r
691 stk--;\\r
692 STACK_BASE_CHECK(stk, "STACK_POP_ONE"); \\r
693} while(0)\r
694\r
695#define STACK_POP do {\\r
696 switch (pop_level) {\\r
697 case STACK_POP_LEVEL_FREE:\\r
698 while (1) {\\r
699 stk--;\\r
700 STACK_BASE_CHECK(stk, "STACK_POP"); \\r
701 if ((stk->type & STK_MASK_POP_USED) != 0) break;\\r
702 ELSE_IF_STATE_CHECK_MARK(stk);\\r
703 }\\r
704 break;\\r
705 case STACK_POP_LEVEL_MEM_START:\\r
706 while (1) {\\r
707 stk--;\\r
708 STACK_BASE_CHECK(stk, "STACK_POP 2"); \\r
709 if ((stk->type & STK_MASK_POP_USED) != 0) break;\\r
710 else if (stk->type == STK_MEM_START) {\\r
711 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\\r
712 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\\r
713 }\\r
714 ELSE_IF_STATE_CHECK_MARK(stk);\\r
715 }\\r
716 break;\\r
717 default:\\r
718 while (1) {\\r
719 stk--;\\r
720 STACK_BASE_CHECK(stk, "STACK_POP 3"); \\r
721 if ((stk->type & STK_MASK_POP_USED) != 0) break;\\r
722 else if (stk->type == STK_MEM_START) {\\r
723 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\\r
724 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\\r
725 }\\r
726 else if (stk->type == STK_REPEAT_INC) {\\r
727 STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\\r
728 }\\r
729 else if (stk->type == STK_MEM_END) {\\r
730 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\\r
731 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\\r
732 }\\r
733 ELSE_IF_STATE_CHECK_MARK(stk);\\r
734 }\\r
735 break;\\r
736 }\\r
737} while(0)\r
738\r
739#define STACK_POP_TIL_POS_NOT do {\\r
740 while (1) {\\r
741 stk--;\\r
742 STACK_BASE_CHECK(stk, "STACK_POP_TIL_POS_NOT"); \\r
743 if (stk->type == STK_POS_NOT) break;\\r
744 else if (stk->type == STK_MEM_START) {\\r
745 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\\r
746 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\\r
747 }\\r
748 else if (stk->type == STK_REPEAT_INC) {\\r
749 STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\\r
750 }\\r
751 else if (stk->type == STK_MEM_END) {\\r
752 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\\r
753 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\\r
754 }\\r
755 ELSE_IF_STATE_CHECK_MARK(stk);\\r
756 }\\r
757} while(0)\r
758\r
759#define STACK_POP_TIL_LOOK_BEHIND_NOT do {\\r
760 while (1) {\\r
761 stk--;\\r
762 STACK_BASE_CHECK(stk, "STACK_POP_TIL_LOOK_BEHIND_NOT"); \\r
763 if (stk->type == STK_LOOK_BEHIND_NOT) break;\\r
764 else if (stk->type == STK_MEM_START) {\\r
765 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\\r
766 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\\r
767 }\\r
768 else if (stk->type == STK_REPEAT_INC) {\\r
769 STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\\r
770 }\\r
771 else if (stk->type == STK_MEM_END) {\\r
772 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\\r
773 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\\r
774 }\\r
775 ELSE_IF_STATE_CHECK_MARK(stk);\\r
776 }\\r
777} while(0)\r
778\r
779#define STACK_POS_END(k) do {\\r
780 k = stk;\\r
781 while (1) {\\r
782 k--;\\r
783 STACK_BASE_CHECK(k, "STACK_POS_END"); \\r
784 if (IS_TO_VOID_TARGET(k)) {\\r
785 k->type = STK_VOID;\\r
786 }\\r
787 else if (k->type == STK_POS) {\\r
788 k->type = STK_VOID;\\r
789 break;\\r
790 }\\r
791 }\\r
792} while(0)\r
793\r
794#define STACK_STOP_BT_END do {\\r
795 OnigStackType *k = stk;\\r
796 while (1) {\\r
797 k--;\\r
798 STACK_BASE_CHECK(k, "STACK_STOP_BT_END"); \\r
799 if (IS_TO_VOID_TARGET(k)) {\\r
800 k->type = STK_VOID;\\r
801 }\\r
802 else if (k->type == STK_STOP_BT) {\\r
803 k->type = STK_VOID;\\r
804 break;\\r
805 }\\r
806 }\\r
807} while(0)\r
808\r
809#define STACK_NULL_CHECK(isnull,id,s) do {\\r
810 OnigStackType* k = stk;\\r
811 while (1) {\\r
812 k--;\\r
813 STACK_BASE_CHECK(k, "STACK_NULL_CHECK"); \\r
814 if (k->type == STK_NULL_CHECK_START) {\\r
815 if (k->u.null_check.num == (id)) {\\r
816 (isnull) = (k->u.null_check.pstr == (s));\\r
817 break;\\r
818 }\\r
819 }\\r
820 }\\r
821} while(0)\r
822\r
823#define STACK_NULL_CHECK_REC(isnull,id,s) do {\\r
824 int level = 0;\\r
825 OnigStackType* k = stk;\\r
826 while (1) {\\r
827 k--;\\r
828 STACK_BASE_CHECK(k, "STACK_NULL_CHECK_REC"); \\r
829 if (k->type == STK_NULL_CHECK_START) {\\r
830 if (k->u.null_check.num == (id)) {\\r
831 if (level == 0) {\\r
832 (isnull) = (k->u.null_check.pstr == (s));\\r
833 break;\\r
834 }\\r
835 else level--;\\r
836 }\\r
837 }\\r
838 else if (k->type == STK_NULL_CHECK_END) {\\r
839 level++;\\r
840 }\\r
841 }\\r
842} while(0)\r
843\r
844#define STACK_NULL_CHECK_MEMST(isnull,id,s,reg) do {\\r
845 OnigStackType* k = stk;\\r
846 while (1) {\\r
847 k--;\\r
848 STACK_BASE_CHECK(k, "STACK_NULL_CHECK_MEMST"); \\r
849 if (k->type == STK_NULL_CHECK_START) {\\r
850 if (k->u.null_check.num == (id)) {\\r
851 if (k->u.null_check.pstr != (s)) {\\r
852 (isnull) = 0;\\r
853 break;\\r
854 }\\r
855 else {\\r
856 UChar* endp;\\r
857 (isnull) = 1;\\r
858 while (k < stk) {\\r
859 if (k->type == STK_MEM_START) {\\r
860 if (k->u.mem.end == INVALID_STACK_INDEX) {\\r
861 (isnull) = 0; break;\\r
862 }\\r
863 if (BIT_STATUS_AT(reg->bt_mem_end, k->u.mem.num))\\r
864 endp = STACK_AT(k->u.mem.end)->u.mem.pstr;\\r
865 else\\r
866 endp = (UChar* )k->u.mem.end;\\r
867 if (STACK_AT(k->u.mem.start)->u.mem.pstr != endp) {\\r
868 (isnull) = 0; break;\\r
869 }\\r
870 else if (endp != s) {\\r
871 (isnull) = -1; /* empty, but position changed */ \\r
872 }\\r
873 }\\r
874 k++;\\r
875 }\\r
876 break;\\r
877 }\\r
878 }\\r
879 }\\r
880 }\\r
881} while(0)\r
882\r
883#define STACK_NULL_CHECK_MEMST_REC(isnull,id,s,reg) do {\\r
884 int level = 0;\\r
885 OnigStackType* k = stk;\\r
886 while (1) {\\r
887 k--;\\r
888 STACK_BASE_CHECK(k, "STACK_NULL_CHECK_MEMST_REC"); \\r
889 if (k->type == STK_NULL_CHECK_START) {\\r
890 if (k->u.null_check.num == (id)) {\\r
891 if (level == 0) {\\r
892 if (k->u.null_check.pstr != (s)) {\\r
893 (isnull) = 0;\\r
894 break;\\r
895 }\\r
896 else {\\r
897 UChar* endp;\\r
898 (isnull) = 1;\\r
899 while (k < stk) {\\r
900 if (k->type == STK_MEM_START) {\\r
901 if (k->u.mem.end == INVALID_STACK_INDEX) {\\r
902 (isnull) = 0; break;\\r
903 }\\r
904 if (BIT_STATUS_AT(reg->bt_mem_end, k->u.mem.num))\\r
905 endp = STACK_AT(k->u.mem.end)->u.mem.pstr;\\r
906 else\\r
907 endp = (UChar* )k->u.mem.end;\\r
908 if (STACK_AT(k->u.mem.start)->u.mem.pstr != endp) {\\r
909 (isnull) = 0; break;\\r
910 }\\r
911 else if (endp != s) {\\r
912 (isnull) = -1; /* empty, but position changed */ \\r
913 }\\r
914 }\\r
915 k++;\\r
916 }\\r
917 break;\\r
918 }\\r
919 }\\r
920 else {\\r
921 level--;\\r
922 }\\r
923 }\\r
924 }\\r
925 else if (k->type == STK_NULL_CHECK_END) {\\r
926 if (k->u.null_check.num == (id)) level++;\\r
927 }\\r
928 }\\r
929} while(0)\r
930\r
931#define STACK_GET_REPEAT(id, k) do {\\r
932 int level = 0;\\r
933 k = stk;\\r
934 while (1) {\\r
935 k--;\\r
936 STACK_BASE_CHECK(k, "STACK_GET_REPEAT"); \\r
937 if (k->type == STK_REPEAT) {\\r
938 if (level == 0) {\\r
939 if (k->u.repeat.num == (id)) {\\r
940 break;\\r
941 }\\r
942 }\\r
943 }\\r
944 else if (k->type == STK_CALL_FRAME) level--;\\r
945 else if (k->type == STK_RETURN) level++;\\r
946 }\\r
947} while(0)\r
948\r
949#define STACK_RETURN(addr) do {\\r
950 int level = 0;\\r
951 OnigStackType* k = stk;\\r
952 while (1) {\\r
953 k--;\\r
954 STACK_BASE_CHECK(k, "STACK_RETURN"); \\r
955 if (k->type == STK_CALL_FRAME) {\\r
956 if (level == 0) {\\r
957 (addr) = k->u.call_frame.ret_addr;\\r
958 break;\\r
959 }\\r
960 else level--;\\r
961 }\\r
962 else if (k->type == STK_RETURN)\\r
963 level++;\\r
964 }\\r
965} while(0)\r
966\r
967\r
968#define STRING_CMP(s1,s2,len) do {\\r
969 while (len-- > 0) {\\r
970 if (*s1++ != *s2++) goto fail;\\r
971 }\\r
972} while(0)\r
973\r
974#define STRING_CMP_IC(case_fold_flag,s1,ps2,len) do {\\r
975 if (string_cmp_ic(encode, case_fold_flag, s1, ps2, len) == 0) \\r
976 goto fail; \\r
977} while(0)\r
978\r
979static int string_cmp_ic(OnigEncoding enc, int case_fold_flag,\r
980 UChar* s1, UChar** ps2, int mblen)\r
981{\r
982 UChar buf1[ONIGENC_MBC_CASE_FOLD_MAXLEN];\r
983 UChar buf2[ONIGENC_MBC_CASE_FOLD_MAXLEN];\r
984 UChar *p1, *p2, *end1, *s2, *end2;\r
985 int len1, len2;\r
986\r
987 s2 = *ps2;\r
988 end1 = s1 + mblen;\r
989 end2 = s2 + mblen;\r
990 while (s1 < end1) {\r
991 len1 = ONIGENC_MBC_CASE_FOLD(enc, case_fold_flag, &s1, end1, buf1);\r
992 len2 = ONIGENC_MBC_CASE_FOLD(enc, case_fold_flag, &s2, end2, buf2);\r
993 if (len1 != len2) return 0;\r
994 p1 = buf1;\r
995 p2 = buf2;\r
996 while (len1-- > 0) {\r
997 if (*p1 != *p2) return 0;\r
998 p1++;\r
999 p2++;\r
1000 }\r
1001 }\r
1002\r
1003 *ps2 = s2;\r
1004 return 1;\r
1005}\r
1006\r
1007#define STRING_CMP_VALUE(s1,s2,len,is_fail) do {\\r
1008 is_fail = 0;\\r
1009 while (len-- > 0) {\\r
1010 if (*s1++ != *s2++) {\\r
1011 is_fail = 1; break;\\r
1012 }\\r
1013 }\\r
1014} while(0)\r
1015\r
1016#define STRING_CMP_VALUE_IC(case_fold_flag,s1,ps2,len,is_fail) do {\\r
1017 if (string_cmp_ic(encode, case_fold_flag, s1, ps2, len) == 0) \\r
1018 is_fail = 1; \\r
1019 else \\r
1020 is_fail = 0; \\r
1021} while(0)\r
1022\r
1023\r
1024#define IS_EMPTY_STR (str == end)\r
1025#define ON_STR_BEGIN(s) ((s) == str)\r
1026#define ON_STR_END(s) ((s) == end)\r
1027#ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE\r
1028#define DATA_ENSURE_CHECK1 (s < right_range)\r
1029#define DATA_ENSURE_CHECK(n) (s + (n) <= right_range)\r
1030#define DATA_ENSURE(n) if (s + (n) > right_range) goto fail\r
1031#else\r
1032#define DATA_ENSURE_CHECK1 (s < end)\r
1033#define DATA_ENSURE_CHECK(n) (s + (n) <= end)\r
1034#define DATA_ENSURE(n) if (s + (n) > end) goto fail\r
1035#endif /* USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE */\r
1036\r
1037\r
1038#ifdef USE_CAPTURE_HISTORY\r
1039static int\r
1040make_capture_history_tree(OnigCaptureTreeNode* node, OnigStackType** kp,\r
1041 OnigStackType* stk_top, UChar* str, regex_t* reg)\r
1042{\r
1043 int n, r;\r
1044 OnigCaptureTreeNode* child;\r
1045 OnigStackType* k = *kp;\r
1046\r
1047 while (k < stk_top) {\r
1048 if (k->type == STK_MEM_START) {\r
1049 n = k->u.mem.num;\r
1050 if (n <= ONIG_MAX_CAPTURE_HISTORY_GROUP &&\r
1051 BIT_STATUS_AT(reg->capture_history, n) != 0) {\r
1052 child = history_node_new();\r
1053 CHECK_NULL_RETURN_MEMERR(child);\r
1054 child->group = n;\r
1055 child->beg = (int )(k->u.mem.pstr - str);\r
1056 r = history_tree_add_child(node, child);\r
1057 if (r != 0) return r;\r
1058 *kp = (k + 1);\r
1059 r = make_capture_history_tree(child, kp, stk_top, str, reg);\r
1060 if (r != 0) return r;\r
1061\r
1062 k = *kp;\r
1063 child->end = (int )(k->u.mem.pstr - str);\r
1064 }\r
1065 }\r
1066 else if (k->type == STK_MEM_END) {\r
1067 if (k->u.mem.num == node->group) {\r
1068 node->end = (int )(k->u.mem.pstr - str);\r
1069 *kp = k;\r
1070 return 0;\r
1071 }\r
1072 }\r
1073 k++;\r
1074 }\r
1075\r
1076 return 1; /* 1: root node ending. */\r
1077}\r
1078#endif\r
1079\r
1080#ifdef USE_BACKREF_WITH_LEVEL\r
1081static int mem_is_in_memp(int mem, int num, UChar* memp)\r
1082{\r
1083 int i;\r
1084 MemNumType m;\r
1085\r
1086 for (i = 0; i < num; i++) {\r
1087 GET_MEMNUM_INC(m, memp);\r
1088 if (mem == (int )m) return 1;\r
1089 }\r
1090 return 0;\r
1091}\r
1092\r
1093static int backref_match_at_nested_level(regex_t* reg\r
1094 , OnigStackType* top, OnigStackType* stk_base\r
1095 , int ignore_case, int case_fold_flag\r
1096 , int nest, int mem_num, UChar* memp, UChar** s, const UChar* send)\r
1097{\r
1098 UChar *ss, *p, *pstart, *pend = NULL_UCHARP;\r
1099 int level;\r
1100 OnigStackType* k;\r
1101\r
1102 level = 0;\r
1103 k = top;\r
1104 k--;\r
1105 while (k >= stk_base) {\r
1106 if (k->type == STK_CALL_FRAME) {\r
1107 level--;\r
1108 }\r
1109 else if (k->type == STK_RETURN) {\r
1110 level++;\r
1111 }\r
1112 else if (level == nest) {\r
1113 if (k->type == STK_MEM_START) {\r
1114 if (mem_is_in_memp(k->u.mem.num, mem_num, memp)) {\r
1115 pstart = k->u.mem.pstr;\r
1116 if (pend != NULL_UCHARP) {\r
1117 if (pend - pstart > send - *s) return 0; /* or goto next_mem; */\r
1118 p = pstart;\r
1119 ss = *s;\r
1120\r
1121 if (ignore_case != 0) {\r
1122 if (string_cmp_ic(reg->enc, case_fold_flag,\r
1123 pstart, &ss, (int )(pend - pstart)) == 0)\r
1124 return 0; /* or goto next_mem; */\r
1125 }\r
1126 else {\r
1127 while (p < pend) {\r
1128 if (*p++ != *ss++) return 0; /* or goto next_mem; */\r
1129 }\r
1130 }\r
1131\r
1132 *s = ss;\r
1133 return 1;\r
1134 }\r
1135 }\r
1136 }\r
1137 else if (k->type == STK_MEM_END) {\r
1138 if (mem_is_in_memp(k->u.mem.num, mem_num, memp)) {\r
1139 pend = k->u.mem.pstr;\r
1140 }\r
1141 }\r
1142 }\r
1143 k--;\r
1144 }\r
1145\r
1146 return 0;\r
1147}\r
1148#endif /* USE_BACKREF_WITH_LEVEL */\r
1149\r
1150\r
1151#ifdef ONIG_DEBUG_STATISTICS\r
1152\r
1153#define USE_TIMEOFDAY\r
1154\r
1155#ifdef USE_TIMEOFDAY\r
1156#ifdef HAVE_SYS_TIME_H\r
1157#include <sys/time.h>\r
1158#endif\r
1159#ifdef HAVE_UNISTD_H\r
1160#include <unistd.h>\r
1161#endif\r
1162static struct timeval ts, te;\r
1163#define GETTIME(t) gettimeofday(&(t), (struct timezone* )0)\r
1164#define TIMEDIFF(te,ts) (((te).tv_usec - (ts).tv_usec) + \\r
1165 (((te).tv_sec - (ts).tv_sec)*1000000))\r
1166#else\r
1167#ifdef HAVE_SYS_TIMES_H\r
1168#include <sys/times.h>\r
1169#endif\r
1170static struct tms ts, te;\r
1171#define GETTIME(t) times(&(t))\r
1172#define TIMEDIFF(te,ts) ((te).tms_utime - (ts).tms_utime)\r
1173#endif\r
1174\r
1175static int OpCounter[256];\r
1176static int OpPrevCounter[256];\r
1177static unsigned long OpTime[256];\r
1178static int OpCurr = OP_FINISH;\r
1179static int OpPrevTarget = OP_FAIL;\r
1180static int MaxStackDepth = 0;\r
1181\r
1182#define MOP_IN(opcode) do {\\r
1183 if (opcode == OpPrevTarget) OpPrevCounter[OpCurr]++;\\r
1184 OpCurr = opcode;\\r
1185 OpCounter[opcode]++;\\r
1186 GETTIME(ts);\\r
1187} while(0)\r
1188\r
1189#define MOP_OUT do {\\r
1190 GETTIME(te);\\r
1191 OpTime[OpCurr] += TIMEDIFF(te, ts);\\r
1192} while(0)\r
1193\r
1194extern void\r
1195onig_statistics_init(void)\r
1196{\r
1197 int i;\r
1198 for (i = 0; i < 256; i++) {\r
1199 OpCounter[i] = OpPrevCounter[i] = 0; OpTime[i] = 0;\r
1200 }\r
1201 MaxStackDepth = 0;\r
1202}\r
1203\r
1204extern void\r
1205onig_print_statistics(FILE* f)\r
1206{\r
1207 int i;\r
1208 fprintf(f, " count prev time\n");\r
1209 for (i = 0; OnigOpInfo[i].opcode >= 0; i++) {\r
1210 fprintf(f, "%8d: %8d: %10ld: %s\n",\r
1211 OpCounter[i], OpPrevCounter[i], OpTime[i], OnigOpInfo[i].name);\r
1212 }\r
1213 fprintf(f, "\nmax stack depth: %d\n", MaxStackDepth);\r
1214}\r
1215\r
1216#define STACK_INC do {\\r
1217 stk++;\\r
1218 if (stk - stk_base > MaxStackDepth) \\r
1219 MaxStackDepth = stk - stk_base;\\r
1220} while(0)\r
1221\r
1222#else\r
1223#define STACK_INC stk++\r
1224\r
1225#define MOP_IN(opcode)\r
1226#define MOP_OUT\r
1227#endif\r
1228\r
1229\r
1230/* matching region of POSIX API */\r
1231typedef int regoff_t;\r
1232\r
1233typedef struct {\r
1234 regoff_t rm_so;\r
1235 regoff_t rm_eo;\r
1236} posix_regmatch_t;\r
1237\r
1238/* match data(str - end) from position (sstart). */\r
1239/* if sstart == str then set sprev to NULL. */\r
1240static int\r
1241match_at(regex_t* reg, const UChar* str, const UChar* end,\r
1242#ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE\r
1243 const UChar* right_range,\r
1244#endif\r
1245 const UChar* sstart, UChar* sprev, OnigMatchArg* msa)\r
1246{\r
1247 static UChar FinishCode[] = { OP_FINISH };\r
1248\r
1249 int i, n, num_mem, best_len, pop_level;\r
1250 LengthType tlen, tlen2;\r
1251 MemNumType mem;\r
1252 RelAddrType addr;\r
1253 OnigOptionType option = reg->options;\r
1254 OnigEncoding encode = reg->enc;\r
1255 OnigCaseFoldType case_fold_flag = reg->case_fold_flag;\r
1256 UChar *s, *q, *sbegin;\r
1257 UChar *p = reg->p;\r
1258 char *alloca_base;\r
1259 OnigStackType *stk_alloc, *stk_base, *stk, *stk_end;\r
1260 OnigStackType *stkp; /* used as any purpose. */\r
1261 OnigStackIndex si;\r
1262 OnigStackIndex *repeat_stk;\r
1263 OnigStackIndex *mem_start_stk, *mem_end_stk;\r
1264#ifdef USE_COMBINATION_EXPLOSION_CHECK\r
1265 int scv;\r
1266 unsigned char* state_check_buff = msa->state_check_buff;\r
1267 int num_comb_exp_check = reg->num_comb_exp_check;\r
1268#endif\r
1269 n = reg->num_repeat + reg->num_mem * 2;\r
1270\r
1271 STACK_INIT(alloca_base, n, INIT_MATCH_STACK_SIZE);\r
1272 pop_level = reg->stack_pop_level;\r
1273 num_mem = reg->num_mem;\r
1274 repeat_stk = (OnigStackIndex* )alloca_base;\r
1275\r
1276 mem_start_stk = (OnigStackIndex* )(repeat_stk + reg->num_repeat);\r
1277 mem_end_stk = mem_start_stk + num_mem;\r
1278 mem_start_stk--; /* for index start from 1,\r
1279 mem_start_stk[1]..mem_start_stk[num_mem] */\r
1280 mem_end_stk--; /* for index start from 1,\r
1281 mem_end_stk[1]..mem_end_stk[num_mem] */\r
1282 for (i = 1; i <= num_mem; i++) {\r
1283 mem_start_stk[i] = mem_end_stk[i] = INVALID_STACK_INDEX;\r
1284 }\r
1285\r
1286#ifdef ONIG_DEBUG_MATCH\r
1287 fprintf(stderr, "match_at: str: %d, end: %d, start: %d, sprev: %d\n",\r
1288 (int )str, (int )end, (int )sstart, (int )sprev);\r
1289 fprintf(stderr, "size: %d, start offset: %d\n",\r
1290 (int )(end - str), (int )(sstart - str));\r
1291#endif\r
1292\r
1293 STACK_PUSH_ENSURED(STK_ALT, FinishCode); /* bottom stack */\r
1294 best_len = ONIG_MISMATCH;\r
1295 s = (UChar* )sstart;\r
1296 while (1) {\r
1297#ifdef ONIG_DEBUG_MATCH\r
1298 {\r
1299 UChar *q, *bp, buf[50];\r
1300 int len;\r
1301 fprintf(stderr, "%4d> \"", (int )(s - str));\r
1302 bp = buf;\r
1303 for (i = 0, q = s; i < 7 && q < end; i++) {\r
1304 len = enclen(encode, q);\r
1305 while (len-- > 0) *bp++ = *q++;\r
1306 }\r
1307 if (q < end) { xmemcpy(bp, "...\"", 4); bp += 4; }\r
1308 else { xmemcpy(bp, "\"", 1); bp += 1; }\r
1309 *bp = 0;\r
1310 fputs((char* )buf, stderr);\r
1311 for (i = 0; i < 20 - (bp - buf); i++) fputc(' ', stderr);\r
1312 onig_print_compiled_byte_code(stderr, p, NULL, encode);\r
1313 fprintf(stderr, "\n");\r
1314 }\r
1315#endif\r
1316\r
1317 sbegin = s;\r
1318 switch (*p++) {\r
1319 case OP_END: MOP_IN(OP_END);\r
1320 n = (int)(s - sstart);\r
1321 if (n > best_len) {\r
1322 OnigRegion* region;\r
1323#ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE\r
1324 if (IS_FIND_LONGEST(option)) {\r
1325 if (n > msa->best_len) {\r
1326 msa->best_len = n;\r
1327 msa->best_s = (UChar* )sstart;\r
1328 }\r
1329 else\r
1330 goto end_best_len;\r
1331 }\r
1332#endif\r
1333 best_len = n;\r
1334 region = msa->region;\r
1335 if (region) {\r
1336#ifdef USE_POSIX_API_REGION_OPTION\r
1337 if (IS_POSIX_REGION(msa->options)) {\r
1338 posix_regmatch_t* rmt = (posix_regmatch_t* )region;\r
1339\r
1340 rmt[0].rm_so = (regoff_t)(sstart - str);\r
1341 rmt[0].rm_eo = (regoff_t)(s - str);\r
1342 for (i = 1; i <= num_mem; i++) {\r
1343 if (mem_end_stk[i] != INVALID_STACK_INDEX) {\r
1344 if (BIT_STATUS_AT(reg->bt_mem_start, i))\r
1345 rmt[i].rm_so = (regoff_t)(STACK_AT(mem_start_stk[i])->u.mem.pstr - str);\r
1346 else\r
1347 rmt[i].rm_so = (regoff_t)((UChar* )((void* )(mem_start_stk[i])) - str);\r
1348\r
1349 rmt[i].rm_eo = (regoff_t)((BIT_STATUS_AT(reg->bt_mem_end, i)\r
1350 ? STACK_AT(mem_end_stk[i])->u.mem.pstr\r
1351 : (UChar* )((void* )mem_end_stk[i])) - str);\r
1352 }\r
1353 else {\r
1354 rmt[i].rm_so = rmt[i].rm_eo = ONIG_REGION_NOTPOS;\r
1355 }\r
1356 }\r
1357 }\r
1358 else {\r
1359#endif /* USE_POSIX_API_REGION_OPTION */\r
1360 region->beg[0] = (int)(sstart - str);\r
1361 region->end[0] = (int)(s - str);\r
1362 for (i = 1; i <= num_mem; i++) {\r
1363 if (mem_end_stk[i] != INVALID_STACK_INDEX) {\r
1364 if (BIT_STATUS_AT(reg->bt_mem_start, i))\r
1365 region->beg[i] = (int)(STACK_AT(mem_start_stk[i])->u.mem.pstr - str);\r
1366 else\r
1367 region->beg[i] = (int)((UChar* )((void* )mem_start_stk[i]) - str);\r
1368\r
1369 region->end[i] = (int)((BIT_STATUS_AT(reg->bt_mem_end, i)\r
1370 ? STACK_AT(mem_end_stk[i])->u.mem.pstr\r
1371 : (UChar* )((void* )mem_end_stk[i])) - str);\r
1372 }\r
1373 else {\r
1374 region->beg[i] = region->end[i] = ONIG_REGION_NOTPOS;\r
1375 }\r
1376 }\r
1377\r
1378#ifdef USE_CAPTURE_HISTORY\r
1379 if (reg->capture_history != 0) {\r
1380 int r;\r
1381 OnigCaptureTreeNode* node;\r
1382\r
1383 if (IS_NULL(region->history_root)) {\r
1384 region->history_root = node = history_node_new();\r
1385 CHECK_NULL_RETURN_MEMERR(node);\r
1386 }\r
1387 else {\r
1388 node = region->history_root;\r
1389 history_tree_clear(node);\r
1390 }\r
1391\r
1392 node->group = 0;\r
1393 node->beg = (int)(sstart - str);\r
1394 node->end = (int)(s - str);\r
1395\r
1396 stkp = stk_base;\r
1397 r = make_capture_history_tree(region->history_root, &stkp,\r
1398 stk, (UChar* )str, reg);\r
1399 if (r < 0) {\r
1400 best_len = r; /* error code */\r
1401 goto finish;\r
1402 }\r
1403 }\r
1404#endif /* USE_CAPTURE_HISTORY */\r
1405#ifdef USE_POSIX_API_REGION_OPTION\r
1406 } /* else IS_POSIX_REGION() */\r
1407#endif\r
1408 } /* if (region) */\r
1409 } /* n > best_len */\r
1410\r
1411#ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE\r
1412 end_best_len:\r
1413#endif\r
1414 MOP_OUT;\r
1415\r
1416 if (IS_FIND_CONDITION(option)) {\r
1417 if (IS_FIND_NOT_EMPTY(option) && s == sstart) {\r
1418 best_len = ONIG_MISMATCH;\r
1419 goto fail; /* for retry */\r
1420 }\r
1421 if (IS_FIND_LONGEST(option) && DATA_ENSURE_CHECK1) {\r
1422 goto fail; /* for retry */\r
1423 }\r
1424 }\r
1425\r
1426 /* default behavior: return first-matching result. */\r
1427 goto finish;\r
1428 break;\r
1429\r
1430 case OP_EXACT1: MOP_IN(OP_EXACT1);\r
1431#if 0\r
1432 DATA_ENSURE(1);\r
1433 if (*p != *s) goto fail;\r
1434 p++; s++;\r
1435#endif\r
1436 if (*p != *s++) goto fail;\r
1437 DATA_ENSURE(0);\r
1438 p++;\r
1439 MOP_OUT;\r
1440 break;\r
1441\r
1442 case OP_EXACT1_IC: MOP_IN(OP_EXACT1_IC);\r
1443 {\r
1444 int len;\r
1445 UChar *q, lowbuf[ONIGENC_MBC_CASE_FOLD_MAXLEN];\r
1446\r
1447 DATA_ENSURE(1);\r
1448 len = ONIGENC_MBC_CASE_FOLD(encode,\r
1449 /* DISABLE_CASE_FOLD_MULTI_CHAR(case_fold_flag), */\r
1450 case_fold_flag,\r
1451 &s, end, lowbuf);\r
1452 DATA_ENSURE(0);\r
1453 q = lowbuf;\r
1454 while (len-- > 0) {\r
1455 if (*p != *q) {\r
1456 goto fail;\r
1457 }\r
1458 p++; q++;\r
1459 }\r
1460 }\r
1461 MOP_OUT;\r
1462 break;\r
1463\r
1464 case OP_EXACT2: MOP_IN(OP_EXACT2);\r
1465 DATA_ENSURE(2);\r
1466 if (*p != *s) goto fail;\r
1467 p++; s++;\r
1468 if (*p != *s) goto fail;\r
1469 sprev = s;\r
1470 p++; s++;\r
1471 MOP_OUT;\r
1472 continue;\r
1473 break;\r
1474\r
1475 case OP_EXACT3: MOP_IN(OP_EXACT3);\r
1476 DATA_ENSURE(3);\r
1477 if (*p != *s) goto fail;\r
1478 p++; s++;\r
1479 if (*p != *s) goto fail;\r
1480 p++; s++;\r
1481 if (*p != *s) goto fail;\r
1482 sprev = s;\r
1483 p++; s++;\r
1484 MOP_OUT;\r
1485 continue;\r
1486 break;\r
1487\r
1488 case OP_EXACT4: MOP_IN(OP_EXACT4);\r
1489 DATA_ENSURE(4);\r
1490 if (*p != *s) goto fail;\r
1491 p++; s++;\r
1492 if (*p != *s) goto fail;\r
1493 p++; s++;\r
1494 if (*p != *s) goto fail;\r
1495 p++; s++;\r
1496 if (*p != *s) goto fail;\r
1497 sprev = s;\r
1498 p++; s++;\r
1499 MOP_OUT;\r
1500 continue;\r
1501 break;\r
1502\r
1503 case OP_EXACT5: MOP_IN(OP_EXACT5);\r
1504 DATA_ENSURE(5);\r
1505 if (*p != *s) goto fail;\r
1506 p++; s++;\r
1507 if (*p != *s) goto fail;\r
1508 p++; s++;\r
1509 if (*p != *s) goto fail;\r
1510 p++; s++;\r
1511 if (*p != *s) goto fail;\r
1512 p++; s++;\r
1513 if (*p != *s) goto fail;\r
1514 sprev = s;\r
1515 p++; s++;\r
1516 MOP_OUT;\r
1517 continue;\r
1518 break;\r
1519\r
1520 case OP_EXACTN: MOP_IN(OP_EXACTN);\r
1521 GET_LENGTH_INC(tlen, p);\r
1522 DATA_ENSURE(tlen);\r
1523 while (tlen-- > 0) {\r
1524 if (*p++ != *s++) goto fail;\r
1525 }\r
1526 sprev = s - 1;\r
1527 MOP_OUT;\r
1528 continue;\r
1529 break;\r
1530\r
1531 case OP_EXACTN_IC: MOP_IN(OP_EXACTN_IC);\r
1532 {\r
1533 int len;\r
1534 UChar *q, *endp, lowbuf[ONIGENC_MBC_CASE_FOLD_MAXLEN];\r
1535\r
1536 GET_LENGTH_INC(tlen, p);\r
1537 endp = p + tlen;\r
1538\r
1539 while (p < endp) {\r
1540 sprev = s;\r
1541 DATA_ENSURE(1);\r
1542 len = ONIGENC_MBC_CASE_FOLD(encode,\r
1543 /* DISABLE_CASE_FOLD_MULTI_CHAR(case_fold_flag), */\r
1544 case_fold_flag,\r
1545 &s, end, lowbuf);\r
1546 DATA_ENSURE(0);\r
1547 q = lowbuf;\r
1548 while (len-- > 0) {\r
1549 if (*p != *q) goto fail;\r
1550 p++; q++;\r
1551 }\r
1552 }\r
1553 }\r
1554\r
1555 MOP_OUT;\r
1556 continue;\r
1557 break;\r
1558\r
1559 case OP_EXACTMB2N1: MOP_IN(OP_EXACTMB2N1);\r
1560 DATA_ENSURE(2);\r
1561 if (*p != *s) goto fail;\r
1562 p++; s++;\r
1563 if (*p != *s) goto fail;\r
1564 p++; s++;\r
1565 MOP_OUT;\r
1566 break;\r
1567\r
1568 case OP_EXACTMB2N2: MOP_IN(OP_EXACTMB2N2);\r
1569 DATA_ENSURE(4);\r
1570 if (*p != *s) goto fail;\r
1571 p++; s++;\r
1572 if (*p != *s) goto fail;\r
1573 p++; s++;\r
1574 sprev = s;\r
1575 if (*p != *s) goto fail;\r
1576 p++; s++;\r
1577 if (*p != *s) goto fail;\r
1578 p++; s++;\r
1579 MOP_OUT;\r
1580 continue;\r
1581 break;\r
1582\r
1583 case OP_EXACTMB2N3: MOP_IN(OP_EXACTMB2N3);\r
1584 DATA_ENSURE(6);\r
1585 if (*p != *s) goto fail;\r
1586 p++; s++;\r
1587 if (*p != *s) goto fail;\r
1588 p++; s++;\r
1589 if (*p != *s) goto fail;\r
1590 p++; s++;\r
1591 if (*p != *s) goto fail;\r
1592 p++; s++;\r
1593 sprev = s;\r
1594 if (*p != *s) goto fail;\r
1595 p++; s++;\r
1596 if (*p != *s) goto fail;\r
1597 p++; s++;\r
1598 MOP_OUT;\r
1599 continue;\r
1600 break;\r
1601\r
1602 case OP_EXACTMB2N: MOP_IN(OP_EXACTMB2N);\r
1603 GET_LENGTH_INC(tlen, p);\r
1604 DATA_ENSURE(tlen * 2);\r
1605 while (tlen-- > 0) {\r
1606 if (*p != *s) goto fail;\r
1607 p++; s++;\r
1608 if (*p != *s) goto fail;\r
1609 p++; s++;\r
1610 }\r
1611 sprev = s - 2;\r
1612 MOP_OUT;\r
1613 continue;\r
1614 break;\r
1615\r
1616 case OP_EXACTMB3N: MOP_IN(OP_EXACTMB3N);\r
1617 GET_LENGTH_INC(tlen, p);\r
1618 DATA_ENSURE(tlen * 3);\r
1619 while (tlen-- > 0) {\r
1620 if (*p != *s) goto fail;\r
1621 p++; s++;\r
1622 if (*p != *s) goto fail;\r
1623 p++; s++;\r
1624 if (*p != *s) goto fail;\r
1625 p++; s++;\r
1626 }\r
1627 sprev = s - 3;\r
1628 MOP_OUT;\r
1629 continue;\r
1630 break;\r
1631\r
1632 case OP_EXACTMBN: MOP_IN(OP_EXACTMBN);\r
1633 GET_LENGTH_INC(tlen, p); /* mb-len */\r
1634 GET_LENGTH_INC(tlen2, p); /* string len */\r
1635 tlen2 *= tlen;\r
1636 DATA_ENSURE(tlen2);\r
1637 while (tlen2-- > 0) {\r
1638 if (*p != *s) goto fail;\r
1639 p++; s++;\r
1640 }\r
1641 sprev = s - tlen;\r
1642 MOP_OUT;\r
1643 continue;\r
1644 break;\r
1645\r
1646 case OP_CCLASS: MOP_IN(OP_CCLASS);\r
1647 DATA_ENSURE(1);\r
1648 if (BITSET_AT(((BitSetRef )p), *s) == 0) goto fail;\r
1649 p += SIZE_BITSET;\r
1650 s += enclen(encode, s); /* OP_CCLASS can match mb-code. \D, \S */\r
1651 MOP_OUT;\r
1652 break;\r
1653\r
1654 case OP_CCLASS_MB: MOP_IN(OP_CCLASS_MB);\r
1655 if (! ONIGENC_IS_MBC_HEAD(encode, s)) goto fail;\r
1656\r
1657 cclass_mb:\r
1658 GET_LENGTH_INC(tlen, p);\r
1659 {\r
1660 OnigCodePoint code;\r
1661 UChar *ss;\r
1662 int mb_len;\r
1663\r
1664 DATA_ENSURE(1);\r
1665 mb_len = enclen(encode, s);\r
1666 DATA_ENSURE(mb_len);\r
1667 ss = s;\r
1668 s += mb_len;\r
1669 code = ONIGENC_MBC_TO_CODE(encode, ss, s);\r
1670\r
1671#ifdef PLATFORM_UNALIGNED_WORD_ACCESS\r
1672 if (! onig_is_in_code_range(p, code)) goto fail;\r
1673#else\r
1674 q = p;\r
1675 ALIGNMENT_RIGHT(q);\r
1676 if (! onig_is_in_code_range(q, code)) goto fail;\r
1677#endif\r
1678 }\r
1679 p += tlen;\r
1680 MOP_OUT;\r
1681 break;\r
1682\r
1683 case OP_CCLASS_MIX: MOP_IN(OP_CCLASS_MIX);\r
1684 DATA_ENSURE(1);\r
1685 if (ONIGENC_IS_MBC_HEAD(encode, s)) {\r
1686 p += SIZE_BITSET;\r
1687 goto cclass_mb;\r
1688 }\r
1689 else {\r
1690 if (BITSET_AT(((BitSetRef )p), *s) == 0)\r
1691 goto fail;\r
1692\r
1693 p += SIZE_BITSET;\r
1694 GET_LENGTH_INC(tlen, p);\r
1695 p += tlen;\r
1696 s++;\r
1697 }\r
1698 MOP_OUT;\r
1699 break;\r
1700\r
1701 case OP_CCLASS_NOT: MOP_IN(OP_CCLASS_NOT);\r
1702 DATA_ENSURE(1);\r
1703 if (BITSET_AT(((BitSetRef )p), *s) != 0) goto fail;\r
1704 p += SIZE_BITSET;\r
1705 s += enclen(encode, s);\r
1706 MOP_OUT;\r
1707 break;\r
1708\r
1709 case OP_CCLASS_MB_NOT: MOP_IN(OP_CCLASS_MB_NOT);\r
1710 DATA_ENSURE(1);\r
1711 if (! ONIGENC_IS_MBC_HEAD(encode, s)) {\r
1712 s++;\r
1713 GET_LENGTH_INC(tlen, p);\r
1714 p += tlen;\r
1715 goto cc_mb_not_success;\r
1716 }\r
1717\r
1718 cclass_mb_not:\r
1719 GET_LENGTH_INC(tlen, p);\r
1720 {\r
1721 OnigCodePoint code;\r
1722 UChar *ss;\r
1723 int mb_len = enclen(encode, s);\r
1724\r
1725 if (! DATA_ENSURE_CHECK(mb_len)) {\r
1726 DATA_ENSURE(1);\r
1727 s = (UChar* )end;\r
1728 p += tlen;\r
1729 goto cc_mb_not_success;\r
1730 }\r
1731\r
1732 ss = s;\r
1733 s += mb_len;\r
1734 code = ONIGENC_MBC_TO_CODE(encode, ss, s);\r
1735\r
1736#ifdef PLATFORM_UNALIGNED_WORD_ACCESS\r
1737 if (onig_is_in_code_range(p, code)) goto fail;\r
1738#else\r
1739 q = p;\r
1740 ALIGNMENT_RIGHT(q);\r
1741 if (onig_is_in_code_range(q, code)) goto fail;\r
1742#endif\r
1743 }\r
1744 p += tlen;\r
1745\r
1746 cc_mb_not_success:\r
1747 MOP_OUT;\r
1748 break;\r
1749\r
1750 case OP_CCLASS_MIX_NOT: MOP_IN(OP_CCLASS_MIX_NOT);\r
1751 DATA_ENSURE(1);\r
1752 if (ONIGENC_IS_MBC_HEAD(encode, s)) {\r
1753 p += SIZE_BITSET;\r
1754 goto cclass_mb_not;\r
1755 }\r
1756 else {\r
1757 if (BITSET_AT(((BitSetRef )p), *s) != 0)\r
1758 goto fail;\r
1759\r
1760 p += SIZE_BITSET;\r
1761 GET_LENGTH_INC(tlen, p);\r
1762 p += tlen;\r
1763 s++;\r
1764 }\r
1765 MOP_OUT;\r
1766 break;\r
1767\r
1768 case OP_CCLASS_NODE: MOP_IN(OP_CCLASS_NODE);\r
1769 {\r
1770 OnigCodePoint code;\r
1771 void *node;\r
1772 int mb_len;\r
1773 UChar *ss;\r
1774\r
1775 DATA_ENSURE(1);\r
1776 GET_POINTER_INC(node, p);\r
1777 mb_len = enclen(encode, s);\r
1778 ss = s;\r
1779 s += mb_len;\r
1780 DATA_ENSURE(0);\r
1781 code = ONIGENC_MBC_TO_CODE(encode, ss, s);\r
1782 if (onig_is_code_in_cc_len(mb_len, code, node) == 0) goto fail;\r
1783 }\r
1784 MOP_OUT;\r
1785 break;\r
1786\r
1787 case OP_ANYCHAR: MOP_IN(OP_ANYCHAR);\r
1788 DATA_ENSURE(1);\r
1789 n = enclen(encode, s);\r
1790 DATA_ENSURE(n);\r
1791 if (ONIGENC_IS_MBC_NEWLINE(encode, s, end)) goto fail;\r
1792 s += n;\r
1793 MOP_OUT;\r
1794 break;\r
1795\r
1796 case OP_ANYCHAR_ML: MOP_IN(OP_ANYCHAR_ML);\r
1797 DATA_ENSURE(1);\r
1798 n = enclen(encode, s);\r
1799 DATA_ENSURE(n);\r
1800 s += n;\r
1801 MOP_OUT;\r
1802 break;\r
1803\r
1804 case OP_ANYCHAR_STAR: MOP_IN(OP_ANYCHAR_STAR);\r
1805 while (DATA_ENSURE_CHECK1) {\r
1806 STACK_PUSH_ALT(p, s, sprev);\r
1807 n = enclen(encode, s);\r
1808 DATA_ENSURE(n);\r
1809 if (ONIGENC_IS_MBC_NEWLINE(encode, s, end)) goto fail;\r
1810 sprev = s;\r
1811 s += n;\r
1812 }\r
1813 MOP_OUT;\r
1814 break;\r
1815\r
1816 case OP_ANYCHAR_ML_STAR: MOP_IN(OP_ANYCHAR_ML_STAR);\r
1817 while (DATA_ENSURE_CHECK1) {\r
1818 STACK_PUSH_ALT(p, s, sprev);\r
1819 n = enclen(encode, s);\r
1820 if (n > 1) {\r
1821 DATA_ENSURE(n);\r
1822 sprev = s;\r
1823 s += n;\r
1824 }\r
1825 else {\r
1826 sprev = s;\r
1827 s++;\r
1828 }\r
1829 }\r
1830 MOP_OUT;\r
1831 break;\r
1832\r
1833 case OP_ANYCHAR_STAR_PEEK_NEXT: MOP_IN(OP_ANYCHAR_STAR_PEEK_NEXT);\r
1834 while (DATA_ENSURE_CHECK1) {\r
1835 if (*p == *s) {\r
1836 STACK_PUSH_ALT(p + 1, s, sprev);\r
1837 }\r
1838 n = enclen(encode, s);\r
1839 DATA_ENSURE(n);\r
1840 if (ONIGENC_IS_MBC_NEWLINE(encode, s, end)) goto fail;\r
1841 sprev = s;\r
1842 s += n;\r
1843 }\r
1844 p++;\r
1845 MOP_OUT;\r
1846 break;\r
1847\r
1848 case OP_ANYCHAR_ML_STAR_PEEK_NEXT:MOP_IN(OP_ANYCHAR_ML_STAR_PEEK_NEXT);\r
1849 while (DATA_ENSURE_CHECK1) {\r
1850 if (*p == *s) {\r
1851 STACK_PUSH_ALT(p + 1, s, sprev);\r
1852 }\r
1853 n = enclen(encode, s);\r
1854 if (n > 1) {\r
1855 DATA_ENSURE(n);\r
1856 sprev = s;\r
1857 s += n;\r
1858 }\r
1859 else {\r
1860 sprev = s;\r
1861 s++;\r
1862 }\r
1863 }\r
1864 p++;\r
1865 MOP_OUT;\r
1866 break;\r
1867\r
1868#ifdef USE_COMBINATION_EXPLOSION_CHECK\r
1869 case OP_STATE_CHECK_ANYCHAR_STAR: MOP_IN(OP_STATE_CHECK_ANYCHAR_STAR);\r
1870 GET_STATE_CHECK_NUM_INC(mem, p);\r
1871 while (DATA_ENSURE_CHECK1) {\r
1872 STATE_CHECK_VAL(scv, mem);\r
1873 if (scv) goto fail;\r
1874\r
1875 STACK_PUSH_ALT_WITH_STATE_CHECK(p, s, sprev, mem);\r
1876 n = enclen(encode, s);\r
1877 DATA_ENSURE(n);\r
1878 if (ONIGENC_IS_MBC_NEWLINE(encode, s, end)) goto fail;\r
1879 sprev = s;\r
1880 s += n;\r
1881 }\r
1882 MOP_OUT;\r
1883 break;\r
1884\r
1885 case OP_STATE_CHECK_ANYCHAR_ML_STAR:\r
1886 MOP_IN(OP_STATE_CHECK_ANYCHAR_ML_STAR);\r
1887\r
1888 GET_STATE_CHECK_NUM_INC(mem, p);\r
1889 while (DATA_ENSURE_CHECK1) {\r
1890 STATE_CHECK_VAL(scv, mem);\r
1891 if (scv) goto fail;\r
1892\r
1893 STACK_PUSH_ALT_WITH_STATE_CHECK(p, s, sprev, mem);\r
1894 n = enclen(encode, s);\r
1895 if (n > 1) {\r
1896 DATA_ENSURE(n);\r
1897 sprev = s;\r
1898 s += n;\r
1899 }\r
1900 else {\r
1901 sprev = s;\r
1902 s++;\r
1903 }\r
1904 }\r
1905 MOP_OUT;\r
1906 break;\r
1907#endif /* USE_COMBINATION_EXPLOSION_CHECK */\r
1908\r
1909 case OP_WORD: MOP_IN(OP_WORD);\r
1910 DATA_ENSURE(1);\r
1911 if (! ONIGENC_IS_MBC_WORD(encode, s, end))\r
1912 goto fail;\r
1913\r
1914 s += enclen(encode, s);\r
1915 MOP_OUT;\r
1916 break;\r
1917\r
1918 case OP_NOT_WORD: MOP_IN(OP_NOT_WORD);\r
1919 DATA_ENSURE(1);\r
1920 if (ONIGENC_IS_MBC_WORD(encode, s, end))\r
1921 goto fail;\r
1922\r
1923 s += enclen(encode, s);\r
1924 MOP_OUT;\r
1925 break;\r
1926\r
1927 case OP_WORD_BOUND: MOP_IN(OP_WORD_BOUND);\r
1928 if (ON_STR_BEGIN(s)) {\r
1929 DATA_ENSURE(1);\r
1930 if (! ONIGENC_IS_MBC_WORD(encode, s, end))\r
1931 goto fail;\r
1932 }\r
1933 else if (ON_STR_END(s)) {\r
1934 if (! ONIGENC_IS_MBC_WORD(encode, sprev, end))\r
1935 goto fail;\r
1936 }\r
1937 else {\r
1938 if (ONIGENC_IS_MBC_WORD(encode, s, end)\r
1939 == ONIGENC_IS_MBC_WORD(encode, sprev, end))\r
1940 goto fail;\r
1941 }\r
1942 MOP_OUT;\r
1943 continue;\r
1944 break;\r
1945\r
1946 case OP_NOT_WORD_BOUND: MOP_IN(OP_NOT_WORD_BOUND);\r
1947 if (ON_STR_BEGIN(s)) {\r
1948 if (DATA_ENSURE_CHECK1 && ONIGENC_IS_MBC_WORD(encode, s, end))\r
1949 goto fail;\r
1950 }\r
1951 else if (ON_STR_END(s)) {\r
1952 if (ONIGENC_IS_MBC_WORD(encode, sprev, end))\r
1953 goto fail;\r
1954 }\r
1955 else {\r
1956 if (ONIGENC_IS_MBC_WORD(encode, s, end)\r
1957 != ONIGENC_IS_MBC_WORD(encode, sprev, end))\r
1958 goto fail;\r
1959 }\r
1960 MOP_OUT;\r
1961 continue;\r
1962 break;\r
1963\r
1964#ifdef USE_WORD_BEGIN_END\r
1965 case OP_WORD_BEGIN: MOP_IN(OP_WORD_BEGIN);\r
1966 if (DATA_ENSURE_CHECK1 && ONIGENC_IS_MBC_WORD(encode, s, end)) {\r
1967 if (ON_STR_BEGIN(s) || !ONIGENC_IS_MBC_WORD(encode, sprev, end)) {\r
1968 MOP_OUT;\r
1969 continue;\r
1970 }\r
1971 }\r
1972 goto fail;\r
1973 break;\r
1974\r
1975 case OP_WORD_END: MOP_IN(OP_WORD_END);\r
1976 if (!ON_STR_BEGIN(s) && ONIGENC_IS_MBC_WORD(encode, sprev, end)) {\r
1977 if (ON_STR_END(s) || !ONIGENC_IS_MBC_WORD(encode, s, end)) {\r
1978 MOP_OUT;\r
1979 continue;\r
1980 }\r
1981 }\r
1982 goto fail;\r
1983 break;\r
1984#endif\r
1985\r
1986 case OP_BEGIN_BUF: MOP_IN(OP_BEGIN_BUF);\r
1987 if (! ON_STR_BEGIN(s)) goto fail;\r
1988\r
1989 MOP_OUT;\r
1990 continue;\r
1991 break;\r
1992\r
1993 case OP_END_BUF: MOP_IN(OP_END_BUF);\r
1994 if (! ON_STR_END(s)) goto fail;\r
1995\r
1996 MOP_OUT;\r
1997 continue;\r
1998 break;\r
1999\r
2000 case OP_BEGIN_LINE: MOP_IN(OP_BEGIN_LINE);\r
2001 if (ON_STR_BEGIN(s)) {\r
2002 if (IS_NOTBOL(msa->options)) goto fail;\r
2003 MOP_OUT;\r
2004 continue;\r
2005 }\r
2006 else if (ONIGENC_IS_MBC_NEWLINE(encode, sprev, end) && !ON_STR_END(s)) {\r
2007 MOP_OUT;\r
2008 continue;\r
2009 }\r
2010 goto fail;\r
2011 break;\r
2012\r
2013 case OP_END_LINE: MOP_IN(OP_END_LINE);\r
2014 if (ON_STR_END(s)) {\r
2015#ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE\r
2016 if (IS_EMPTY_STR || !ONIGENC_IS_MBC_NEWLINE(encode, sprev, end)) {\r
2017#endif\r
2018 if (IS_NOTEOL(msa->options)) goto fail;\r
2019 MOP_OUT;\r
2020 continue;\r
2021#ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE\r
2022 }\r
2023#endif\r
2024 }\r
2025 else if (ONIGENC_IS_MBC_NEWLINE(encode, s, end)) {\r
2026 MOP_OUT;\r
2027 continue;\r
2028 }\r
2029#ifdef USE_CRNL_AS_LINE_TERMINATOR\r
2030 else if (ONIGENC_IS_MBC_CRNL(encode, s, end)) {\r
2031 MOP_OUT;\r
2032 continue;\r
2033 }\r
2034#endif\r
2035 goto fail;\r
2036 break;\r
2037\r
2038 case OP_SEMI_END_BUF: MOP_IN(OP_SEMI_END_BUF);\r
2039 if (ON_STR_END(s)) {\r
2040#ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE\r
2041 if (IS_EMPTY_STR || !ONIGENC_IS_MBC_NEWLINE(encode, sprev, end)) {\r
2042#endif\r
2043 if (IS_NOTEOL(msa->options)) goto fail;\r
2044 MOP_OUT;\r
2045 continue;\r
2046#ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE\r
2047 }\r
2048#endif\r
2049 }\r
2050 else if (ONIGENC_IS_MBC_NEWLINE(encode, s, end) &&\r
2051 ON_STR_END(s + enclen(encode, s))) {\r
2052 MOP_OUT;\r
2053 continue;\r
2054 }\r
2055#ifdef USE_CRNL_AS_LINE_TERMINATOR\r
2056 else if (ONIGENC_IS_MBC_CRNL(encode, s, end)) {\r
2057 UChar* ss = s + enclen(encode, s);\r
2058 ss += enclen(encode, ss);\r
2059 if (ON_STR_END(ss)) {\r
2060 MOP_OUT;\r
2061 continue;\r
2062 }\r
2063 }\r
2064#endif\r
2065 goto fail;\r
2066 break;\r
2067\r
2068 case OP_BEGIN_POSITION: MOP_IN(OP_BEGIN_POSITION);\r
2069 if (s != msa->start)\r
2070 goto fail;\r
2071\r
2072 MOP_OUT;\r
2073 continue;\r
2074 break;\r
2075\r
2076 case OP_MEMORY_START_PUSH: MOP_IN(OP_MEMORY_START_PUSH);\r
2077 GET_MEMNUM_INC(mem, p);\r
2078 STACK_PUSH_MEM_START(mem, s);\r
2079 MOP_OUT;\r
2080 continue;\r
2081 break;\r
2082\r
2083 case OP_MEMORY_START: MOP_IN(OP_MEMORY_START);\r
2084 GET_MEMNUM_INC(mem, p);\r
2085 mem_start_stk[mem] = (OnigStackIndex )((void* )s);\r
2086 MOP_OUT;\r
2087 continue;\r
2088 break;\r
2089\r
2090 case OP_MEMORY_END_PUSH: MOP_IN(OP_MEMORY_END_PUSH);\r
2091 GET_MEMNUM_INC(mem, p);\r
2092 STACK_PUSH_MEM_END(mem, s);\r
2093 MOP_OUT;\r
2094 continue;\r
2095 break;\r
2096\r
2097 case OP_MEMORY_END: MOP_IN(OP_MEMORY_END);\r
2098 GET_MEMNUM_INC(mem, p);\r
2099 mem_end_stk[mem] = (OnigStackIndex )((void* )s);\r
2100 MOP_OUT;\r
2101 continue;\r
2102 break;\r
2103\r
2104#ifdef USE_SUBEXP_CALL\r
2105 case OP_MEMORY_END_PUSH_REC: MOP_IN(OP_MEMORY_END_PUSH_REC);\r
2106 GET_MEMNUM_INC(mem, p);\r
2107 STACK_GET_MEM_START(mem, stkp); /* should be before push mem-end. */\r
2108 STACK_PUSH_MEM_END(mem, s);\r
2109 mem_start_stk[mem] = GET_STACK_INDEX(stkp);\r
2110 MOP_OUT;\r
2111 continue;\r
2112 break;\r
2113\r
2114 case OP_MEMORY_END_REC: MOP_IN(OP_MEMORY_END_REC);\r
2115 GET_MEMNUM_INC(mem, p);\r
2116 mem_end_stk[mem] = (OnigStackIndex )((void* )s);\r
2117 STACK_GET_MEM_START(mem, stkp);\r
2118\r
2119 if (BIT_STATUS_AT(reg->bt_mem_start, mem))\r
2120 mem_start_stk[mem] = GET_STACK_INDEX(stkp);\r
2121 else\r
2122 mem_start_stk[mem] = (OnigStackIndex )((void* )stkp->u.mem.pstr);\r
2123\r
2124 STACK_PUSH_MEM_END_MARK(mem);\r
2125 MOP_OUT;\r
2126 continue;\r
2127 break;\r
2128#endif\r
2129\r
2130 case OP_BACKREF1: MOP_IN(OP_BACKREF1);\r
2131 mem = 1;\r
2132 goto backref;\r
2133 break;\r
2134\r
2135 case OP_BACKREF2: MOP_IN(OP_BACKREF2);\r
2136 mem = 2;\r
2137 goto backref;\r
2138 break;\r
2139\r
2140 case OP_BACKREFN: MOP_IN(OP_BACKREFN);\r
2141 GET_MEMNUM_INC(mem, p);\r
2142 backref:\r
2143 {\r
2144 int len;\r
2145 UChar *pstart, *pend;\r
2146\r
2147 /* if you want to remove following line, \r
2148 you should check in parse and compile time. */\r
2149 if (mem > num_mem) goto fail;\r
2150 if (mem_end_stk[mem] == INVALID_STACK_INDEX) goto fail;\r
2151 if (mem_start_stk[mem] == INVALID_STACK_INDEX) goto fail;\r
2152\r
2153 if (BIT_STATUS_AT(reg->bt_mem_start, mem))\r
2154 pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;\r
2155 else\r
2156 pstart = (UChar* )((void* )mem_start_stk[mem]);\r
2157\r
2158 pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)\r
2159 ? STACK_AT(mem_end_stk[mem])->u.mem.pstr\r
2160 : (UChar* )((void* )mem_end_stk[mem]));\r
2161 n = (int)(pend - pstart);\r
2162 DATA_ENSURE(n);\r
2163 sprev = s;\r
2164 STRING_CMP(pstart, s, n);\r
2165 while (sprev + (len = enclen(encode, sprev)) < s)\r
2166 sprev += len;\r
2167\r
2168 MOP_OUT;\r
2169 continue;\r
2170 }\r
2171 break;\r
2172\r
2173 case OP_BACKREFN_IC: MOP_IN(OP_BACKREFN_IC);\r
2174 GET_MEMNUM_INC(mem, p);\r
2175 {\r
2176 int len;\r
2177 UChar *pstart, *pend;\r
2178\r
2179 /* if you want to remove following line, \r
2180 you should check in parse and compile time. */\r
2181 if (mem > num_mem) goto fail;\r
2182 if (mem_end_stk[mem] == INVALID_STACK_INDEX) goto fail;\r
2183 if (mem_start_stk[mem] == INVALID_STACK_INDEX) goto fail;\r
2184\r
2185 if (BIT_STATUS_AT(reg->bt_mem_start, mem))\r
2186 pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;\r
2187 else\r
2188 pstart = (UChar* )((void* )mem_start_stk[mem]);\r
2189\r
2190 pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)\r
2191 ? STACK_AT(mem_end_stk[mem])->u.mem.pstr\r
2192 : (UChar* )((void* )mem_end_stk[mem]));\r
2193 n = (int)(pend - pstart);\r
2194 DATA_ENSURE(n);\r
2195 sprev = s;\r
2196 STRING_CMP_IC(case_fold_flag, pstart, &s, n);\r
2197 while (sprev + (len = enclen(encode, sprev)) < s)\r
2198 sprev += len;\r
2199\r
2200 MOP_OUT;\r
2201 continue;\r
2202 }\r
2203 break;\r
2204\r
2205 case OP_BACKREF_MULTI: MOP_IN(OP_BACKREF_MULTI);\r
2206 {\r
2207 int len, is_fail;\r
2208 UChar *pstart, *pend, *swork;\r
2209\r
2210 GET_LENGTH_INC(tlen, p);\r
2211 for (i = 0; i < tlen; i++) {\r
2212 GET_MEMNUM_INC(mem, p);\r
2213\r
2214 if (mem_end_stk[mem] == INVALID_STACK_INDEX) continue;\r
2215 if (mem_start_stk[mem] == INVALID_STACK_INDEX) continue;\r
2216\r
2217 if (BIT_STATUS_AT(reg->bt_mem_start, mem))\r
2218 pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;\r
2219 else\r
2220 pstart = (UChar* )((void* )mem_start_stk[mem]);\r
2221\r
2222 pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)\r
2223 ? STACK_AT(mem_end_stk[mem])->u.mem.pstr\r
2224 : (UChar* )((void* )mem_end_stk[mem]));\r
2225 n = (int)(pend - pstart);\r
2226 DATA_ENSURE(n);\r
2227 sprev = s;\r
2228 swork = s;\r
2229 STRING_CMP_VALUE(pstart, swork, n, is_fail);\r
2230 if (is_fail) continue;\r
2231 s = swork;\r
2232 while (sprev + (len = enclen(encode, sprev)) < s)\r
2233 sprev += len;\r
2234\r
2235 p += (SIZE_MEMNUM * (tlen - i - 1));\r
2236 break; /* success */\r
2237 }\r
2238 if (i == tlen) goto fail;\r
2239 MOP_OUT;\r
2240 continue;\r
2241 }\r
2242 break;\r
2243\r
2244 case OP_BACKREF_MULTI_IC: MOP_IN(OP_BACKREF_MULTI_IC);\r
2245 {\r
2246 int len, is_fail;\r
2247 UChar *pstart, *pend, *swork;\r
2248\r
2249 GET_LENGTH_INC(tlen, p);\r
2250 for (i = 0; i < tlen; i++) {\r
2251 GET_MEMNUM_INC(mem, p);\r
2252\r
2253 if (mem_end_stk[mem] == INVALID_STACK_INDEX) continue;\r
2254 if (mem_start_stk[mem] == INVALID_STACK_INDEX) continue;\r
2255\r
2256 if (BIT_STATUS_AT(reg->bt_mem_start, mem))\r
2257 pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;\r
2258 else\r
2259 pstart = (UChar* )((void* )mem_start_stk[mem]);\r
2260\r
2261 pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)\r
2262 ? STACK_AT(mem_end_stk[mem])->u.mem.pstr\r
2263 : (UChar* )((void* )mem_end_stk[mem]));\r
2264 n = (int)(pend - pstart);\r
2265 DATA_ENSURE(n);\r
2266 sprev = s;\r
2267 swork = s;\r
2268 STRING_CMP_VALUE_IC(case_fold_flag, pstart, &swork, n, is_fail);\r
2269 if (is_fail) continue;\r
2270 s = swork;\r
2271 while (sprev + (len = enclen(encode, sprev)) < s)\r
2272 sprev += len;\r
2273\r
2274 p += (SIZE_MEMNUM * (tlen - i - 1));\r
2275 break; /* success */\r
2276 }\r
2277 if (i == tlen) goto fail;\r
2278 MOP_OUT;\r
2279 continue;\r
2280 }\r
2281 break;\r
2282\r
2283#ifdef USE_BACKREF_WITH_LEVEL\r
2284 case OP_BACKREF_WITH_LEVEL:\r
2285 {\r
2286 int len;\r
2287 OnigOptionType ic;\r
2288 LengthType level;\r
2289\r
2290 GET_OPTION_INC(ic, p);\r
2291 GET_LENGTH_INC(level, p);\r
2292 GET_LENGTH_INC(tlen, p);\r
2293\r
2294 sprev = s;\r
2295 if (backref_match_at_nested_level(reg, stk, stk_base, ic\r
2296 , case_fold_flag, (int )level, (int )tlen, p, &s, end)) {\r
2297 while (sprev + (len = enclen(encode, sprev)) < s)\r
2298 sprev += len;\r
2299\r
2300 p += (SIZE_MEMNUM * tlen);\r
2301 }\r
2302 else\r
2303 goto fail;\r
2304\r
2305 MOP_OUT;\r
2306 continue;\r
2307 }\r
2308 \r
2309 break;\r
2310#endif\r
2311\r
2312#if 0 /* no need: IS_DYNAMIC_OPTION() == 0 */\r
2313 case OP_SET_OPTION_PUSH: MOP_IN(OP_SET_OPTION_PUSH);\r
2314 GET_OPTION_INC(option, p);\r
2315 STACK_PUSH_ALT(p, s, sprev);\r
2316 p += SIZE_OP_SET_OPTION + SIZE_OP_FAIL;\r
2317 MOP_OUT;\r
2318 continue;\r
2319 break;\r
2320\r
2321 case OP_SET_OPTION: MOP_IN(OP_SET_OPTION);\r
2322 GET_OPTION_INC(option, p);\r
2323 MOP_OUT;\r
2324 continue;\r
2325 break;\r
2326#endif\r
2327\r
2328 case OP_NULL_CHECK_START: MOP_IN(OP_NULL_CHECK_START);\r
2329 GET_MEMNUM_INC(mem, p); /* mem: null check id */\r
2330 STACK_PUSH_NULL_CHECK_START(mem, s);\r
2331 MOP_OUT;\r
2332 continue;\r
2333 break;\r
2334\r
2335 case OP_NULL_CHECK_END: MOP_IN(OP_NULL_CHECK_END);\r
2336 {\r
2337 int isnull;\r
2338\r
2339 GET_MEMNUM_INC(mem, p); /* mem: null check id */\r
2340 STACK_NULL_CHECK(isnull, mem, s);\r
2341 if (isnull) {\r
2342#ifdef ONIG_DEBUG_MATCH\r
2343 fprintf(stderr, "NULL_CHECK_END: skip id:%d, s:%d\n",\r
2344 (int )mem, (int )s);\r
2345#endif\r
2346 null_check_found:\r
2347 /* empty loop founded, skip next instruction */\r
2348 switch (*p++) {\r
2349 case OP_JUMP:\r
2350 case OP_PUSH:\r
2351 p += SIZE_RELADDR;\r
2352 break;\r
2353 case OP_REPEAT_INC:\r
2354 case OP_REPEAT_INC_NG:\r
2355 case OP_REPEAT_INC_SG:\r
2356 case OP_REPEAT_INC_NG_SG:\r
2357 p += SIZE_MEMNUM;\r
2358 break;\r
2359 default:\r
2360 goto unexpected_bytecode_error;\r
2361 break;\r
2362 }\r
2363 }\r
2364 }\r
2365 MOP_OUT;\r
2366 continue;\r
2367 break;\r
2368\r
2369#ifdef USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT\r
2370 case OP_NULL_CHECK_END_MEMST: MOP_IN(OP_NULL_CHECK_END_MEMST);\r
2371 {\r
2372 int isnull;\r
2373\r
2374 GET_MEMNUM_INC(mem, p); /* mem: null check id */\r
2375 STACK_NULL_CHECK_MEMST(isnull, mem, s, reg);\r
2376 if (isnull) {\r
2377#ifdef ONIG_DEBUG_MATCH\r
2378 fprintf(stderr, "NULL_CHECK_END_MEMST: skip id:%d, s:%d\n",\r
2379 (int )mem, (int )s);\r
2380#endif\r
2381 if (isnull == -1) goto fail;\r
2382 goto null_check_found;\r
2383 }\r
2384 }\r
2385 MOP_OUT;\r
2386 continue;\r
2387 break;\r
2388#endif\r
2389\r
2390#ifdef USE_SUBEXP_CALL\r
2391 case OP_NULL_CHECK_END_MEMST_PUSH:\r
2392 MOP_IN(OP_NULL_CHECK_END_MEMST_PUSH);\r
2393 {\r
2394 int isnull;\r
2395\r
2396 GET_MEMNUM_INC(mem, p); /* mem: null check id */\r
2397#ifdef USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT\r
2398 STACK_NULL_CHECK_MEMST_REC(isnull, mem, s, reg);\r
2399#else\r
2400 STACK_NULL_CHECK_REC(isnull, mem, s);\r
2401#endif\r
2402 if (isnull) {\r
2403#ifdef ONIG_DEBUG_MATCH\r
2404 fprintf(stderr, "NULL_CHECK_END_MEMST_PUSH: skip id:%d, s:%d\n",\r
2405 (int )mem, (int )s);\r
2406#endif\r
2407 if (isnull == -1) goto fail;\r
2408 goto null_check_found;\r
2409 }\r
2410 else {\r
2411 STACK_PUSH_NULL_CHECK_END(mem);\r
2412 }\r
2413 }\r
2414 MOP_OUT;\r
2415 continue;\r
2416 break;\r
2417#endif\r
2418\r
2419 case OP_JUMP: MOP_IN(OP_JUMP);\r
2420 GET_RELADDR_INC(addr, p);\r
2421 p += addr;\r
2422 MOP_OUT;\r
2423 CHECK_INTERRUPT_IN_MATCH_AT;\r
2424 continue;\r
2425 break;\r
2426\r
2427 case OP_PUSH: MOP_IN(OP_PUSH);\r
2428 GET_RELADDR_INC(addr, p);\r
2429 STACK_PUSH_ALT(p + addr, s, sprev);\r
2430 MOP_OUT;\r
2431 continue;\r
2432 break;\r
2433\r
2434#ifdef USE_COMBINATION_EXPLOSION_CHECK\r
2435 case OP_STATE_CHECK_PUSH: MOP_IN(OP_STATE_CHECK_PUSH);\r
2436 GET_STATE_CHECK_NUM_INC(mem, p);\r
2437 STATE_CHECK_VAL(scv, mem);\r
2438 if (scv) goto fail;\r
2439\r
2440 GET_RELADDR_INC(addr, p);\r
2441 STACK_PUSH_ALT_WITH_STATE_CHECK(p + addr, s, sprev, mem);\r
2442 MOP_OUT;\r
2443 continue;\r
2444 break;\r
2445\r
2446 case OP_STATE_CHECK_PUSH_OR_JUMP: MOP_IN(OP_STATE_CHECK_PUSH_OR_JUMP);\r
2447 GET_STATE_CHECK_NUM_INC(mem, p);\r
2448 GET_RELADDR_INC(addr, p);\r
2449 STATE_CHECK_VAL(scv, mem);\r
2450 if (scv) {\r
2451 p += addr;\r
2452 }\r
2453 else {\r
2454 STACK_PUSH_ALT_WITH_STATE_CHECK(p + addr, s, sprev, mem);\r
2455 }\r
2456 MOP_OUT;\r
2457 continue;\r
2458 break;\r
2459\r
2460 case OP_STATE_CHECK: MOP_IN(OP_STATE_CHECK);\r
2461 GET_STATE_CHECK_NUM_INC(mem, p);\r
2462 STATE_CHECK_VAL(scv, mem);\r
2463 if (scv) goto fail;\r
2464\r
2465 STACK_PUSH_STATE_CHECK(s, mem);\r
2466 MOP_OUT;\r
2467 continue;\r
2468 break;\r
2469#endif /* USE_COMBINATION_EXPLOSION_CHECK */\r
2470\r
2471 case OP_POP: MOP_IN(OP_POP);\r
2472 STACK_POP_ONE;\r
2473 MOP_OUT;\r
2474 continue;\r
2475 break;\r
2476\r
2477 case OP_PUSH_OR_JUMP_EXACT1: MOP_IN(OP_PUSH_OR_JUMP_EXACT1);\r
2478 GET_RELADDR_INC(addr, p);\r
2479 if (*p == *s && DATA_ENSURE_CHECK1) {\r
2480 p++;\r
2481 STACK_PUSH_ALT(p + addr, s, sprev);\r
2482 MOP_OUT;\r
2483 continue;\r
2484 }\r
2485 p += (addr + 1);\r
2486 MOP_OUT;\r
2487 continue;\r
2488 break;\r
2489\r
2490 case OP_PUSH_IF_PEEK_NEXT: MOP_IN(OP_PUSH_IF_PEEK_NEXT);\r
2491 GET_RELADDR_INC(addr, p);\r
2492 if (*p == *s) {\r
2493 p++;\r
2494 STACK_PUSH_ALT(p + addr, s, sprev);\r
2495 MOP_OUT;\r
2496 continue;\r
2497 }\r
2498 p++;\r
2499 MOP_OUT;\r
2500 continue;\r
2501 break;\r
2502\r
2503 case OP_REPEAT: MOP_IN(OP_REPEAT);\r
2504 {\r
2505 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */\r
2506 GET_RELADDR_INC(addr, p);\r
2507\r
2508 STACK_ENSURE(1);\r
2509 repeat_stk[mem] = GET_STACK_INDEX(stk);\r
2510 STACK_PUSH_REPEAT(mem, p);\r
2511\r
2512 if (reg->repeat_range[mem].lower == 0) {\r
2513 STACK_PUSH_ALT(p + addr, s, sprev);\r
2514 }\r
2515 }\r
2516 MOP_OUT;\r
2517 continue;\r
2518 break;\r
2519\r
2520 case OP_REPEAT_NG: MOP_IN(OP_REPEAT_NG);\r
2521 {\r
2522 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */\r
2523 GET_RELADDR_INC(addr, p);\r
2524\r
2525 STACK_ENSURE(1);\r
2526 repeat_stk[mem] = GET_STACK_INDEX(stk);\r
2527 STACK_PUSH_REPEAT(mem, p);\r
2528\r
2529 if (reg->repeat_range[mem].lower == 0) {\r
2530 STACK_PUSH_ALT(p, s, sprev);\r
2531 p += addr;\r
2532 }\r
2533 }\r
2534 MOP_OUT;\r
2535 continue;\r
2536 break;\r
2537\r
2538 case OP_REPEAT_INC: MOP_IN(OP_REPEAT_INC);\r
2539 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */\r
2540 si = repeat_stk[mem];\r
2541 stkp = STACK_AT(si);\r
2542\r
2543 repeat_inc:\r
2544 stkp->u.repeat.count++;\r
2545 if (stkp->u.repeat.count >= reg->repeat_range[mem].upper) {\r
2546 /* end of repeat. Nothing to do. */\r
2547 }\r
2548 else if (stkp->u.repeat.count >= reg->repeat_range[mem].lower) {\r
2549 STACK_PUSH_ALT(p, s, sprev);\r
2550 p = STACK_AT(si)->u.repeat.pcode; /* Don't use stkp after PUSH. */\r
2551 }\r
2552 else {\r
2553 p = stkp->u.repeat.pcode;\r
2554 }\r
2555 STACK_PUSH_REPEAT_INC(si);\r
2556 MOP_OUT;\r
2557 CHECK_INTERRUPT_IN_MATCH_AT;\r
2558 continue;\r
2559 break;\r
2560\r
2561 case OP_REPEAT_INC_SG: MOP_IN(OP_REPEAT_INC_SG);\r
2562 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */\r
2563 STACK_GET_REPEAT(mem, stkp);\r
2564 si = GET_STACK_INDEX(stkp);\r
2565 goto repeat_inc;\r
2566 break;\r
2567\r
2568 case OP_REPEAT_INC_NG: MOP_IN(OP_REPEAT_INC_NG);\r
2569 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */\r
2570 si = repeat_stk[mem];\r
2571 stkp = STACK_AT(si);\r
2572\r
2573 repeat_inc_ng:\r
2574 stkp->u.repeat.count++;\r
2575 if (stkp->u.repeat.count < reg->repeat_range[mem].upper) {\r
2576 if (stkp->u.repeat.count >= reg->repeat_range[mem].lower) {\r
2577 UChar* pcode = stkp->u.repeat.pcode;\r
2578\r
2579 STACK_PUSH_REPEAT_INC(si);\r
2580 STACK_PUSH_ALT(pcode, s, sprev);\r
2581 }\r
2582 else {\r
2583 p = stkp->u.repeat.pcode;\r
2584 STACK_PUSH_REPEAT_INC(si);\r
2585 }\r
2586 }\r
2587 else if (stkp->u.repeat.count == reg->repeat_range[mem].upper) {\r
2588 STACK_PUSH_REPEAT_INC(si);\r
2589 }\r
2590 MOP_OUT;\r
2591 CHECK_INTERRUPT_IN_MATCH_AT;\r
2592 continue;\r
2593 break;\r
2594\r
2595 case OP_REPEAT_INC_NG_SG: MOP_IN(OP_REPEAT_INC_NG_SG);\r
2596 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */\r
2597 STACK_GET_REPEAT(mem, stkp);\r
2598 si = GET_STACK_INDEX(stkp);\r
2599 goto repeat_inc_ng;\r
2600 break;\r
2601\r
2602 case OP_PUSH_POS: MOP_IN(OP_PUSH_POS);\r
2603 STACK_PUSH_POS(s, sprev);\r
2604 MOP_OUT;\r
2605 continue;\r
2606 break;\r
2607\r
2608 case OP_POP_POS: MOP_IN(OP_POP_POS);\r
2609 {\r
2610 STACK_POS_END(stkp);\r
2611 s = stkp->u.state.pstr;\r
2612 sprev = stkp->u.state.pstr_prev;\r
2613 }\r
2614 MOP_OUT;\r
2615 continue;\r
2616 break;\r
2617\r
2618 case OP_PUSH_POS_NOT: MOP_IN(OP_PUSH_POS_NOT);\r
2619 GET_RELADDR_INC(addr, p);\r
2620 STACK_PUSH_POS_NOT(p + addr, s, sprev);\r
2621 MOP_OUT;\r
2622 continue;\r
2623 break;\r
2624\r
2625 case OP_FAIL_POS: MOP_IN(OP_FAIL_POS);\r
2626 STACK_POP_TIL_POS_NOT;\r
2627 goto fail;\r
2628 break;\r
2629\r
2630 case OP_PUSH_STOP_BT: MOP_IN(OP_PUSH_STOP_BT);\r
2631 STACK_PUSH_STOP_BT;\r
2632 MOP_OUT;\r
2633 continue;\r
2634 break;\r
2635\r
2636 case OP_POP_STOP_BT: MOP_IN(OP_POP_STOP_BT);\r
2637 STACK_STOP_BT_END;\r
2638 MOP_OUT;\r
2639 continue;\r
2640 break;\r
2641\r
2642 case OP_LOOK_BEHIND: MOP_IN(OP_LOOK_BEHIND);\r
2643 GET_LENGTH_INC(tlen, p);\r
2644 s = (UChar* )ONIGENC_STEP_BACK(encode, str, s, (int )tlen);\r
2645 if (IS_NULL(s)) goto fail;\r
2646 sprev = (UChar* )onigenc_get_prev_char_head(encode, str, s);\r
2647 MOP_OUT;\r
2648 continue;\r
2649 break;\r
2650\r
2651 case OP_PUSH_LOOK_BEHIND_NOT: MOP_IN(OP_PUSH_LOOK_BEHIND_NOT);\r
2652 GET_RELADDR_INC(addr, p);\r
2653 GET_LENGTH_INC(tlen, p);\r
2654 q = (UChar* )ONIGENC_STEP_BACK(encode, str, s, (int )tlen);\r
2655 if (IS_NULL(q)) {\r
2656 /* too short case -> success. ex. /(?<!XXX)a/.match("a")\r
2657 If you want to change to fail, replace following line. */\r
2658 p += addr;\r
2659 /* goto fail; */\r
2660 }\r
2661 else {\r
2662 STACK_PUSH_LOOK_BEHIND_NOT(p + addr, s, sprev);\r
2663 s = q;\r
2664 sprev = (UChar* )onigenc_get_prev_char_head(encode, str, s);\r
2665 }\r
2666 MOP_OUT;\r
2667 continue;\r
2668 break;\r
2669\r
2670 case OP_FAIL_LOOK_BEHIND_NOT: MOP_IN(OP_FAIL_LOOK_BEHIND_NOT);\r
2671 STACK_POP_TIL_LOOK_BEHIND_NOT;\r
2672 goto fail;\r
2673 break;\r
2674\r
2675#ifdef USE_SUBEXP_CALL\r
2676 case OP_CALL: MOP_IN(OP_CALL);\r
2677 GET_ABSADDR_INC(addr, p);\r
2678 STACK_PUSH_CALL_FRAME(p);\r
2679 p = reg->p + addr;\r
2680 MOP_OUT;\r
2681 continue;\r
2682 break;\r
2683\r
2684 case OP_RETURN: MOP_IN(OP_RETURN);\r
2685 STACK_RETURN(p);\r
2686 STACK_PUSH_RETURN;\r
2687 MOP_OUT;\r
2688 continue;\r
2689 break;\r
2690#endif\r
2691\r
2692 case OP_FINISH:\r
2693 goto finish;\r
2694 break;\r
2695\r
2696 fail:\r
2697 MOP_OUT;\r
2698 /* fall */\r
2699 case OP_FAIL: MOP_IN(OP_FAIL);\r
2700 STACK_POP;\r
2701 p = stk->u.state.pcode;\r
2702 s = stk->u.state.pstr;\r
2703 sprev = stk->u.state.pstr_prev;\r
2704\r
2705#ifdef USE_COMBINATION_EXPLOSION_CHECK\r
2706 if (stk->u.state.state_check != 0) {\r
2707 stk->type = STK_STATE_CHECK_MARK;\r
2708 stk++;\r
2709 }\r
2710#endif\r
2711\r
2712 MOP_OUT;\r
2713 continue;\r
2714 break;\r
2715\r
2716 default:\r
2717 goto bytecode_error;\r
2718\r
2719 } /* end of switch */\r
2720 sprev = sbegin;\r
2721 } /* end of while(1) */\r
2722\r
2723 finish:\r
2724 STACK_SAVE;\r
2725 xfree(alloca_base);\r
2726 return best_len;\r
2727\r
2728#ifdef ONIG_DEBUG\r
2729 stack_error:\r
2730 STACK_SAVE;\r
2731 xfree(alloca_base);\r
2732 return ONIGERR_STACK_BUG;\r
2733#endif\r
2734\r
2735 bytecode_error:\r
2736 STACK_SAVE;\r
2737 xfree(alloca_base);\r
2738 return ONIGERR_UNDEFINED_BYTECODE;\r
2739\r
2740 unexpected_bytecode_error:\r
2741 STACK_SAVE;\r
2742 xfree(alloca_base);\r
2743 return ONIGERR_UNEXPECTED_BYTECODE;\r
2744}\r
2745\r
2746\r
2747static UChar*\r
2748slow_search(OnigEncoding enc, UChar* target, UChar* target_end,\r
2749 const UChar* text, const UChar* text_end, UChar* text_range)\r
2750{\r
2751 UChar *t, *p, *s, *end;\r
2752\r
2753 end = (UChar* )text_end;\r
2754 end -= target_end - target - 1;\r
2755 if (end > text_range)\r
2756 end = text_range;\r
2757\r
2758 s = (UChar* )text;\r
2759\r
2760 while (s < end) {\r
2761 if (*s == *target) {\r
2762 p = s + 1;\r
2763 t = target + 1;\r
2764 while (t < target_end) {\r
2765 if (*t != *p++)\r
2766 break;\r
2767 t++;\r
2768 }\r
2769 if (t == target_end)\r
2770 return s;\r
2771 }\r
2772 s += enclen(enc, s);\r
2773 }\r
2774\r
2775 return (UChar* )NULL;\r
2776}\r
2777\r
2778static int\r
2779str_lower_case_match(OnigEncoding enc, int case_fold_flag,\r
2780 const UChar* t, const UChar* tend,\r
2781 const UChar* p, const UChar* end)\r
2782{\r
2783 int lowlen;\r
2784 UChar *q, lowbuf[ONIGENC_MBC_CASE_FOLD_MAXLEN];\r
2785\r
2786 while (t < tend) {\r
2787 lowlen = ONIGENC_MBC_CASE_FOLD(enc, case_fold_flag, &p, end, lowbuf);\r
2788 q = lowbuf;\r
2789 while (lowlen > 0) {\r
2790 if (*t++ != *q++) return 0;\r
2791 lowlen--;\r
2792 }\r
2793 }\r
2794\r
2795 return 1;\r
2796}\r
2797\r
2798static UChar*\r
2799slow_search_ic(OnigEncoding enc, int case_fold_flag,\r
2800 UChar* target, UChar* target_end,\r
2801 const UChar* text, const UChar* text_end, UChar* text_range)\r
2802{\r
2803 UChar *s, *end;\r
2804\r
2805 end = (UChar* )text_end;\r
2806 end -= target_end - target - 1;\r
2807 if (end > text_range)\r
2808 end = text_range;\r
2809\r
2810 s = (UChar* )text;\r
2811\r
2812 while (s < end) {\r
2813 if (str_lower_case_match(enc, case_fold_flag, target, target_end,\r
2814 s, text_end))\r
2815 return s;\r
2816\r
2817 s += enclen(enc, s);\r
2818 }\r
2819\r
2820 return (UChar* )NULL;\r
2821}\r
2822\r
2823static UChar*\r
2824slow_search_backward(OnigEncoding enc, UChar* target, UChar* target_end,\r
2825 const UChar* text, const UChar* adjust_text,\r
2826 const UChar* text_end, const UChar* text_start)\r
2827{\r
2828 UChar *t, *p, *s;\r
2829\r
2830 s = (UChar* )text_end;\r
2831 s -= (target_end - target);\r
2832 if (s > text_start)\r
2833 s = (UChar* )text_start;\r
2834 else\r
2835 s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(enc, adjust_text, s);\r
2836\r
2837 while (s >= text) {\r
2838 if (*s == *target) {\r
2839 p = s + 1;\r
2840 t = target + 1;\r
2841 while (t < target_end) {\r
2842 if (*t != *p++)\r
2843 break;\r
2844 t++;\r
2845 }\r
2846 if (t == target_end)\r
2847 return s;\r
2848 }\r
2849 s = (UChar* )onigenc_get_prev_char_head(enc, adjust_text, s);\r
2850 }\r
2851\r
2852 return (UChar* )NULL;\r
2853}\r
2854\r
2855static UChar*\r
2856slow_search_backward_ic(OnigEncoding enc, int case_fold_flag,\r
2857 UChar* target, UChar* target_end,\r
2858 const UChar* text, const UChar* adjust_text,\r
2859 const UChar* text_end, const UChar* text_start)\r
2860{\r
2861 UChar *s;\r
2862\r
2863 s = (UChar* )text_end;\r
2864 s -= (target_end - target);\r
2865 if (s > text_start)\r
2866 s = (UChar* )text_start;\r
2867 else\r
2868 s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(enc, adjust_text, s);\r
2869\r
2870 while (s >= text) {\r
2871 if (str_lower_case_match(enc, case_fold_flag,\r
2872 target, target_end, s, text_end))\r
2873 return s;\r
2874\r
2875 s = (UChar* )onigenc_get_prev_char_head(enc, adjust_text, s);\r
2876 }\r
2877\r
2878 return (UChar* )NULL;\r
2879}\r
2880\r
2881static UChar*\r
2882bm_search_notrev(regex_t* reg, const UChar* target, const UChar* target_end,\r
2883 const UChar* text, const UChar* text_end,\r
2884 const UChar* text_range)\r
2885{\r
2886 const UChar *s, *se, *t, *p, *end;\r
2887 const UChar *tail;\r
2888 int skip, tlen1;\r
2889\r
2890#ifdef ONIG_DEBUG_SEARCH\r
2891 fprintf(stderr, "bm_search_notrev: text: %d, text_end: %d, text_range: %d\n",\r
2892 (int )text, (int )text_end, (int )text_range);\r
2893#endif\r
2894\r
2895 tail = target_end - 1;\r
2896 tlen1 = (int)(tail - target);\r
2897 end = text_range;\r
2898 if (end + tlen1 > text_end)\r
2899 end = text_end - tlen1;\r
2900\r
2901 s = text;\r
2902\r
2903 if (IS_NULL(reg->int_map)) {\r
2904 while (s < end) {\r
2905 p = se = s + tlen1;\r
2906 t = tail;\r
2907 while (*p == *t) {\r
2908 if (t == target) return (UChar* )s;\r
2909 p--; t--;\r
2910 }\r
2911 skip = reg->map[*se];\r
2912 t = s;\r
2913 do {\r
2914 s += enclen(reg->enc, s);\r
2915 } while ((s - t) < skip && s < end);\r
2916 }\r
2917 }\r
2918 else {\r
2919 while (s < end) {\r
2920 p = se = s + tlen1;\r
2921 t = tail;\r
2922 while (*p == *t) {\r
2923 if (t == target) return (UChar* )s;\r
2924 p--; t--;\r
2925 }\r
2926 skip = reg->int_map[*se];\r
2927 t = s;\r
2928 do {\r
2929 s += enclen(reg->enc, s);\r
2930 } while ((s - t) < skip && s < end);\r
2931 }\r
2932 }\r
2933\r
2934 return (UChar* )NULL;\r
2935}\r
2936\r
2937static UChar*\r
2938bm_search(regex_t* reg, const UChar* target, const UChar* target_end,\r
2939 const UChar* text, const UChar* text_end, const UChar* text_range)\r
2940{\r
2941 const UChar *s, *t, *p, *end;\r
2942 const UChar *tail;\r
2943\r
2944 end = text_range + (target_end - target) - 1;\r
2945 if (end > text_end)\r
2946 end = text_end;\r
2947\r
2948 tail = target_end - 1;\r
2949 s = text + (target_end - target) - 1;\r
2950 if (IS_NULL(reg->int_map)) {\r
2951 while (s < end) {\r
2952 p = s;\r
2953 t = tail;\r
2954 while (*p == *t) {\r
2955 if (t == target) return (UChar* )p;\r
2956 p--; t--;\r
2957 }\r
2958 s += reg->map[*s];\r
2959 }\r
2960 }\r
2961 else { /* see int_map[] */\r
2962 while (s < end) {\r
2963 p = s;\r
2964 t = tail;\r
2965 while (*p == *t) {\r
2966 if (t == target) return (UChar* )p;\r
2967 p--; t--;\r
2968 }\r
2969 s += reg->int_map[*s];\r
2970 }\r
2971 }\r
2972 return (UChar* )NULL;\r
2973}\r
2974\r
2975static int\r
2976set_bm_backward_skip(UChar* s, UChar* end, OnigEncoding enc ARG_UNUSED,\r
2977 int** skip)\r
2978 \r
2979{\r
2980 int i, len;\r
2981\r
2982 if (IS_NULL(*skip)) {\r
2983 *skip = (int* )xmalloc(sizeof(int) * ONIG_CHAR_TABLE_SIZE);\r
2984 if (IS_NULL(*skip)) return ONIGERR_MEMORY;\r
2985 }\r
2986\r
2987 len = (int)(end - s);\r
2988 for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++)\r
2989 (*skip)[i] = len;\r
2990\r
2991 for (i = len - 1; i > 0; i--)\r
2992 (*skip)[s[i]] = i;\r
2993\r
2994 return 0;\r
2995}\r
2996\r
2997static UChar*\r
2998bm_search_backward(regex_t* reg, const UChar* target, const UChar* target_end,\r
2999 const UChar* text, const UChar* adjust_text,\r
3000 const UChar* text_end, const UChar* text_start)\r
3001{\r
3002 const UChar *s, *t, *p;\r
3003\r
3004 s = text_end - (target_end - target);\r
3005 if (text_start < s)\r
3006 s = text_start;\r
3007 else\r
3008 s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, adjust_text, s);\r
3009\r
3010 while (s >= text) {\r
3011 p = s;\r
3012 t = target;\r
3013 while (t < target_end && *p == *t) {\r
3014 p++; t++;\r
3015 }\r
3016 if (t == target_end)\r
3017 return (UChar* )s;\r
3018\r
3019 s -= reg->int_map_backward[*s];\r
3020 s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, adjust_text, s);\r
3021 }\r
3022\r
3023 return (UChar* )NULL;\r
3024}\r
3025\r
3026static UChar*\r
3027map_search(OnigEncoding enc, UChar map[],\r
3028 const UChar* text, const UChar* text_range)\r
3029{\r
3030 const UChar *s = text;\r
3031\r
3032 while (s < text_range) {\r
3033 if (map[*s]) return (UChar* )s;\r
3034\r
3035 s += enclen(enc, s);\r
3036 }\r
3037 return (UChar* )NULL;\r
3038}\r
3039\r
3040static UChar*\r
3041map_search_backward(OnigEncoding enc, UChar map[],\r
3042 const UChar* text, const UChar* adjust_text,\r
3043 const UChar* text_start)\r
3044{\r
3045 const UChar *s = text_start;\r
3046\r
3047 while (s >= text) {\r
3048 if (map[*s]) return (UChar* )s;\r
3049\r
3050 s = onigenc_get_prev_char_head(enc, adjust_text, s);\r
3051 }\r
3052 return (UChar* )NULL;\r
3053}\r
3054\r
3055extern int\r
3056onig_match(regex_t* reg, const UChar* str, const UChar* end, const UChar* at, OnigRegion* region,\r
3057 OnigOptionType option)\r
3058{\r
3059 int r;\r
3060 UChar *prev;\r
3061 OnigMatchArg msa;\r
3062\r
3063#if defined(USE_RECOMPILE_API) && defined(USE_MULTI_THREAD_SYSTEM)\r
3064 start:\r
3065 THREAD_ATOMIC_START;\r
3066 if (ONIG_STATE(reg) >= ONIG_STATE_NORMAL) {\r
3067 ONIG_STATE_INC(reg);\r
3068 if (IS_NOT_NULL(reg->chain) && ONIG_STATE(reg) == ONIG_STATE_NORMAL) {\r
3069 onig_chain_reduce(reg);\r
3070 ONIG_STATE_INC(reg);\r
3071 }\r
3072 }\r
3073 else {\r
3074 int n;\r
3075\r
3076 THREAD_ATOMIC_END;\r
3077 n = 0;\r
3078 while (ONIG_STATE(reg) < ONIG_STATE_NORMAL) {\r
3079 if (++n > THREAD_PASS_LIMIT_COUNT)\r
3080 return ONIGERR_OVER_THREAD_PASS_LIMIT_COUNT;\r
3081 THREAD_PASS;\r
3082 }\r
3083 goto start;\r
3084 }\r
3085 THREAD_ATOMIC_END;\r
3086#endif /* USE_RECOMPILE_API && USE_MULTI_THREAD_SYSTEM */\r
3087\r
3088 MATCH_ARG_INIT(msa, option, region, at);\r
3089#ifdef USE_COMBINATION_EXPLOSION_CHECK\r
3090 {\r
3091 int offset = at - str;\r
3092 STATE_CHECK_BUFF_INIT(msa, end - str, offset, reg->num_comb_exp_check);\r
3093 }\r
3094#endif\r
3095\r
3096 if (region\r
3097#ifdef USE_POSIX_API_REGION_OPTION\r
3098 && !IS_POSIX_REGION(option)\r
3099#endif\r
3100 ) {\r
3101 r = onig_region_resize_clear(region, reg->num_mem + 1);\r
3102 }\r
3103 else\r
3104 r = 0;\r
3105\r
3106 if (r == 0) {\r
3107 prev = (UChar* )onigenc_get_prev_char_head(reg->enc, str, at);\r
3108 r = match_at(reg, str, end,\r
3109#ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE\r
3110 end,\r
3111#endif\r
3112 at, prev, &msa);\r
3113 }\r
3114\r
3115 MATCH_ARG_FREE(msa);\r
3116 ONIG_STATE_DEC_THREAD(reg);\r
3117 return r;\r
3118}\r
3119\r
3120static int\r
3121forward_search_range(regex_t* reg, const UChar* str, const UChar* end, UChar* s,\r
3122 UChar* range, UChar** low, UChar** high, UChar** low_prev)\r
3123{\r
3124 UChar *p, *pprev = (UChar* )NULL;\r
3125\r
3126#ifdef ONIG_DEBUG_SEARCH\r
3127 fprintf(stderr, "forward_search_range: str: %d, end: %d, s: %d, range: %d\n",\r
3128 (int )str, (int )end, (int )s, (int )range);\r
3129#endif\r
3130\r
3131 p = s;\r
3132 if (reg->dmin > 0) {\r
3133 if (ONIGENC_IS_SINGLEBYTE(reg->enc)) {\r
3134 p += reg->dmin;\r
3135 }\r
3136 else {\r
3137 UChar *q = p + reg->dmin;\r
3138 while (p < q) p += enclen(reg->enc, p);\r
3139 }\r
3140 }\r
3141\r
3142 retry:\r
3143 switch (reg->optimize) {\r
3144 case ONIG_OPTIMIZE_EXACT:\r
3145 p = slow_search(reg->enc, reg->exact, reg->exact_end, p, end, range);\r
3146 break;\r
3147 case ONIG_OPTIMIZE_EXACT_IC:\r
3148 p = slow_search_ic(reg->enc, reg->case_fold_flag,\r
3149 reg->exact, reg->exact_end, p, end, range);\r
3150 break;\r
3151\r
3152 case ONIG_OPTIMIZE_EXACT_BM:\r
3153 p = bm_search(reg, reg->exact, reg->exact_end, p, end, range);\r
3154 break;\r
3155\r
3156 case ONIG_OPTIMIZE_EXACT_BM_NOT_REV:\r
3157 p = bm_search_notrev(reg, reg->exact, reg->exact_end, p, end, range);\r
3158 break;\r
3159\r
3160 case ONIG_OPTIMIZE_MAP:\r
3161 p = map_search(reg->enc, reg->map, p, range);\r
3162 break;\r
3163 }\r
3164\r
3165 if (p && p < range) {\r
3166 if (p - reg->dmin < s) {\r
3167 retry_gate:\r
3168 pprev = p;\r
3169 p += enclen(reg->enc, p);\r
3170 goto retry;\r
3171 }\r
3172\r
3173 if (reg->sub_anchor) {\r
3174 UChar* prev;\r
3175\r
3176 switch (reg->sub_anchor) {\r
3177 case ANCHOR_BEGIN_LINE:\r
3178 if (!ON_STR_BEGIN(p)) {\r
3179 prev = onigenc_get_prev_char_head(reg->enc,\r
3180 (pprev ? pprev : str), p);\r
3181 if (!ONIGENC_IS_MBC_NEWLINE(reg->enc, prev, end))\r
3182 goto retry_gate;\r
3183 }\r
3184 break;\r
3185\r
3186 case ANCHOR_END_LINE:\r
3187 if (ON_STR_END(p)) {\r
3188#ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE\r
3189 prev = (UChar* )onigenc_get_prev_char_head(reg->enc,\r
3190 (pprev ? pprev : str), p);\r
3191 if (prev && ONIGENC_IS_MBC_NEWLINE(reg->enc, prev, end))\r
3192 goto retry_gate;\r
3193#endif\r
3194 }\r
3195 else if (! ONIGENC_IS_MBC_NEWLINE(reg->enc, p, end)\r
3196#ifdef USE_CRNL_AS_LINE_TERMINATOR\r
3197 && ! ONIGENC_IS_MBC_CRNL(reg->enc, p, end)\r
3198#endif\r
3199 )\r
3200 goto retry_gate;\r
3201 break;\r
3202 }\r
3203 }\r
3204\r
3205 if (reg->dmax == 0) {\r
3206 *low = p;\r
3207 if (low_prev) {\r
3208 if (*low > s)\r
3209 *low_prev = onigenc_get_prev_char_head(reg->enc, s, p);\r
3210 else\r
3211 *low_prev = onigenc_get_prev_char_head(reg->enc,\r
3212 (pprev ? pprev : str), p);\r
3213 }\r
3214 }\r
3215 else {\r
3216 if (reg->dmax != ONIG_INFINITE_DISTANCE) {\r
3217 *low = p - reg->dmax;\r
3218 if (*low > s) {\r
3219 *low = onigenc_get_right_adjust_char_head_with_prev(reg->enc, s,\r
3220 *low, (const UChar** )low_prev);\r
3221 if (low_prev && IS_NULL(*low_prev))\r
3222 *low_prev = onigenc_get_prev_char_head(reg->enc,\r
3223 (pprev ? pprev : s), *low);\r
3224 }\r
3225 else {\r
3226 if (low_prev)\r
3227 *low_prev = onigenc_get_prev_char_head(reg->enc,\r
3228 (pprev ? pprev : str), *low);\r
3229 }\r
3230 }\r
3231 }\r
3232 /* no needs to adjust *high, *high is used as range check only */\r
3233 *high = p - reg->dmin;\r
3234\r
3235#ifdef ONIG_DEBUG_SEARCH\r
3236 fprintf(stderr,\r
3237 "forward_search_range success: low: %d, high: %d, dmin: %d, dmax: %d\n",\r
3238 (int )(*low - str), (int )(*high - str), reg->dmin, reg->dmax);\r
3239#endif\r
3240 return 1; /* success */\r
3241 }\r
3242\r
3243 return 0; /* fail */\r
3244}\r
3245\r
3246static int set_bm_backward_skip P_((UChar* s, UChar* end, OnigEncoding enc,\r
3247 int** skip));\r
3248\r
3249#define BM_BACKWARD_SEARCH_LENGTH_THRESHOLD 100\r
3250\r
3251static int\r
3252backward_search_range(regex_t* reg, const UChar* str, const UChar* end,\r
3253 UChar* s, const UChar* range, UChar* adjrange,\r
3254 UChar** low, UChar** high)\r
3255{\r
3256 int r;\r
3257 UChar *p;\r
3258\r
3259 range += reg->dmin;\r
3260 p = s;\r
3261\r
3262 retry:\r
3263 switch (reg->optimize) {\r
3264 case ONIG_OPTIMIZE_EXACT:\r
3265 exact_method:\r
3266 p = slow_search_backward(reg->enc, reg->exact, reg->exact_end,\r
3267 range, adjrange, end, p);\r
3268 break;\r
3269\r
3270 case ONIG_OPTIMIZE_EXACT_IC:\r
3271 p = slow_search_backward_ic(reg->enc, reg->case_fold_flag,\r
3272 reg->exact, reg->exact_end,\r
3273 range, adjrange, end, p);\r
3274 break;\r
3275\r
3276 case ONIG_OPTIMIZE_EXACT_BM:\r
3277 case ONIG_OPTIMIZE_EXACT_BM_NOT_REV:\r
3278 if (IS_NULL(reg->int_map_backward)) {\r
3279 if (s - range < BM_BACKWARD_SEARCH_LENGTH_THRESHOLD)\r
3280 goto exact_method;\r
3281\r
3282 r = set_bm_backward_skip(reg->exact, reg->exact_end, reg->enc,\r
3283 &(reg->int_map_backward));\r
3284 if (r) return r;\r
3285 }\r
3286 p = bm_search_backward(reg, reg->exact, reg->exact_end, range, adjrange,\r
3287 end, p);\r
3288 break;\r
3289\r
3290 case ONIG_OPTIMIZE_MAP:\r
3291 p = map_search_backward(reg->enc, reg->map, range, adjrange, p);\r
3292 break;\r
3293 }\r
3294\r
3295 if (p) {\r
3296 if (reg->sub_anchor) {\r
3297 UChar* prev;\r
3298\r
3299 switch (reg->sub_anchor) {\r
3300 case ANCHOR_BEGIN_LINE:\r
3301 if (!ON_STR_BEGIN(p)) {\r
3302 prev = onigenc_get_prev_char_head(reg->enc, str, p);\r
3303 if (!ONIGENC_IS_MBC_NEWLINE(reg->enc, prev, end)) {\r
3304 p = prev;\r
3305 goto retry;\r
3306 }\r
3307 }\r
3308 break;\r
3309\r
3310 case ANCHOR_END_LINE:\r
3311 if (ON_STR_END(p)) {\r
3312#ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE\r
3313 prev = onigenc_get_prev_char_head(reg->enc, adjrange, p);\r
3314 if (IS_NULL(prev)) goto fail;\r
3315 if (ONIGENC_IS_MBC_NEWLINE(reg->enc, prev, end)) {\r
3316 p = prev;\r
3317 goto retry;\r
3318 }\r
3319#endif\r
3320 }\r
3321 else if (! ONIGENC_IS_MBC_NEWLINE(reg->enc, p, end)\r
3322#ifdef USE_CRNL_AS_LINE_TERMINATOR\r
3323 && ! ONIGENC_IS_MBC_CRNL(reg->enc, p, end)\r
3324#endif\r
3325 ) {\r
3326 p = onigenc_get_prev_char_head(reg->enc, adjrange, p);\r
3327 if (IS_NULL(p)) goto fail;\r
3328 goto retry;\r
3329 }\r
3330 break;\r
3331 }\r
3332 }\r
3333\r
3334 /* no needs to adjust *high, *high is used as range check only */\r
3335 if (reg->dmax != ONIG_INFINITE_DISTANCE) {\r
3336 *low = p - reg->dmax;\r
3337 *high = p - reg->dmin;\r
3338 *high = onigenc_get_right_adjust_char_head(reg->enc, adjrange, *high);\r
3339 }\r
3340\r
3341#ifdef ONIG_DEBUG_SEARCH\r
3342 fprintf(stderr, "backward_search_range: low: %d, high: %d\n",\r
3343 (int )(*low - str), (int )(*high - str));\r
3344#endif\r
3345 return 1; /* success */\r
3346 }\r
3347\r
3348 fail:\r
3349#ifdef ONIG_DEBUG_SEARCH\r
3350 fprintf(stderr, "backward_search_range: fail.\n");\r
3351#endif\r
3352 return 0; /* fail */\r
3353}\r
3354\r
3355\r
3356extern int\r
3357onig_search(regex_t* reg, const UChar* str, const UChar* end,\r
3358 const UChar* start, const UChar* range, OnigRegion* region, OnigOptionType option)\r
3359{\r
3360 int r;\r
3361 UChar *s, *prev;\r
3362 OnigMatchArg msa;\r
3363 const UChar *orig_start = start;\r
3364#ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE\r
3365 const UChar *orig_range = range;\r
3366#endif\r
3367\r
3368#if defined(USE_RECOMPILE_API) && defined(USE_MULTI_THREAD_SYSTEM)\r
3369 start:\r
3370 THREAD_ATOMIC_START;\r
3371 if (ONIG_STATE(reg) >= ONIG_STATE_NORMAL) {\r
3372 ONIG_STATE_INC(reg);\r
3373 if (IS_NOT_NULL(reg->chain) && ONIG_STATE(reg) == ONIG_STATE_NORMAL) {\r
3374 onig_chain_reduce(reg);\r
3375 ONIG_STATE_INC(reg);\r
3376 }\r
3377 }\r
3378 else {\r
3379 int n;\r
3380\r
3381 THREAD_ATOMIC_END;\r
3382 n = 0;\r
3383 while (ONIG_STATE(reg) < ONIG_STATE_NORMAL) {\r
3384 if (++n > THREAD_PASS_LIMIT_COUNT)\r
3385 return ONIGERR_OVER_THREAD_PASS_LIMIT_COUNT;\r
3386 THREAD_PASS;\r
3387 }\r
3388 goto start;\r
3389 }\r
3390 THREAD_ATOMIC_END;\r
3391#endif /* USE_RECOMPILE_API && USE_MULTI_THREAD_SYSTEM */\r
3392\r
3393#ifdef ONIG_DEBUG_SEARCH\r
3394 fprintf(stderr,\r
3395 "onig_search (entry point): str: %d, end: %d, start: %d, range: %d\n",\r
3396 (int )str, (int )(end - str), (int )(start - str), (int )(range - str));\r
3397#endif\r
3398\r
3399 if (region\r
3400#ifdef USE_POSIX_API_REGION_OPTION\r
3401 && !IS_POSIX_REGION(option)\r
3402#endif\r
3403 ) {\r
3404 r = onig_region_resize_clear(region, reg->num_mem + 1);\r
3405 if (r) goto finish_no_msa;\r
3406 }\r
3407\r
3408 if (start > end || start < str) goto mismatch_no_msa;\r
3409\r
3410\r
3411#ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE\r
3412#ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE\r
3413#define MATCH_AND_RETURN_CHECK(upper_range) \\r
3414 r = match_at(reg, str, end, (upper_range), s, prev, &msa); \\r
3415 if (r != ONIG_MISMATCH) {\\r
3416 if (r >= 0) {\\r
3417 if (! IS_FIND_LONGEST(reg->options)) {\\r
3418 goto match;\\r
3419 }\\r
3420 }\\r
3421 else goto finish; /* error */ \\r
3422 }\r
3423#else\r
3424#define MATCH_AND_RETURN_CHECK(upper_range) \\r
3425 r = match_at(reg, str, end, (upper_range), s, prev, &msa); \\r
3426 if (r != ONIG_MISMATCH) {\\r
3427 if (r >= 0) {\\r
3428 goto match;\\r
3429 }\\r
3430 else goto finish; /* error */ \\r
3431 }\r
3432#endif /* USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE */\r
3433#else\r
3434#ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE\r
3435#define MATCH_AND_RETURN_CHECK(none) \\r
3436 r = match_at(reg, str, end, s, prev, &msa);\\r
3437 if (r != ONIG_MISMATCH) {\\r
3438 if (r >= 0) {\\r
3439 if (! IS_FIND_LONGEST(reg->options)) {\\r
3440 goto match;\\r
3441 }\\r
3442 }\\r
3443 else goto finish; /* error */ \\r
3444 }\r
3445#else\r
3446#define MATCH_AND_RETURN_CHECK(none) \\r
3447 r = match_at(reg, str, end, s, prev, &msa);\\r
3448 if (r != ONIG_MISMATCH) {\\r
3449 if (r >= 0) {\\r
3450 goto match;\\r
3451 }\\r
3452 else goto finish; /* error */ \\r
3453 }\r
3454#endif /* USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE */\r
3455#endif /* USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE */\r
3456\r
3457\r
3458 /* anchor optimize: resume search range */\r
3459 if (reg->anchor != 0 && str < end) {\r
3460 UChar *min_semi_end, *max_semi_end;\r
3461\r
3462 if (reg->anchor & ANCHOR_BEGIN_POSITION) {\r
3463 /* search start-position only */\r
3464 begin_position:\r
3465 if (range > start)\r
3466 range = start + 1;\r
3467 else\r
3468 range = start;\r
3469 }\r
3470 else if (reg->anchor & ANCHOR_BEGIN_BUF) {\r
3471 /* search str-position only */\r
3472 if (range > start) {\r
3473 if (start != str) goto mismatch_no_msa;\r
3474 range = str + 1;\r
3475 }\r
3476 else {\r
3477 if (range <= str) {\r
3478 start = str;\r
3479 range = str;\r
3480 }\r
3481 else\r
3482 goto mismatch_no_msa;\r
3483 }\r
3484 }\r
3485 else if (reg->anchor & ANCHOR_END_BUF) {\r
3486 min_semi_end = max_semi_end = (UChar* )end;\r
3487\r
3488 end_buf:\r
3489 if ((OnigDistance )(max_semi_end - str) < reg->anchor_dmin)\r
3490 goto mismatch_no_msa;\r
3491\r
3492 if (range > start) {\r
3493 if ((OnigDistance )(min_semi_end - start) > reg->anchor_dmax) {\r
3494 start = min_semi_end - reg->anchor_dmax;\r
3495 if (start < end)\r
3496 start = onigenc_get_right_adjust_char_head(reg->enc, str, start);\r
3497 else { /* match with empty at end */\r
3498 start = onigenc_get_prev_char_head(reg->enc, str, end);\r
3499 }\r
3500 }\r
3501 if ((OnigDistance )(max_semi_end - (range - 1)) < reg->anchor_dmin) {\r
3502 range = max_semi_end - reg->anchor_dmin + 1;\r
3503 }\r
3504\r
3505 if (start >= range) goto mismatch_no_msa;\r
3506 }\r
3507 else {\r
3508 if ((OnigDistance )(min_semi_end - range) > reg->anchor_dmax) {\r
3509 range = min_semi_end - reg->anchor_dmax;\r
3510 }\r
3511 if ((OnigDistance )(max_semi_end - start) < reg->anchor_dmin) {\r
3512 start = max_semi_end - reg->anchor_dmin;\r
3513 start = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, str, start);\r
3514 }\r
3515 if (range > start) goto mismatch_no_msa;\r
3516 }\r
3517 }\r
3518 else if (reg->anchor & ANCHOR_SEMI_END_BUF) {\r
3519 UChar* pre_end = ONIGENC_STEP_BACK(reg->enc, str, end, 1);\r
3520\r
3521 max_semi_end = (UChar* )end;\r
3522 if (ONIGENC_IS_MBC_NEWLINE(reg->enc, pre_end, end)) {\r
3523 min_semi_end = pre_end;\r
3524\r
3525#ifdef USE_CRNL_AS_LINE_TERMINATOR\r
3526 pre_end = ONIGENC_STEP_BACK(reg->enc, str, pre_end, 1);\r
3527 if (IS_NOT_NULL(pre_end) &&\r
3528 ONIGENC_IS_MBC_CRNL(reg->enc, pre_end, end)) {\r
3529 min_semi_end = pre_end;\r
3530 }\r
3531#endif\r
3532 if (min_semi_end > str && start <= min_semi_end) {\r
3533 goto end_buf;\r
3534 }\r
3535 }\r
3536 else {\r
3537 min_semi_end = (UChar* )end;\r
3538 goto end_buf;\r
3539 }\r
3540 }\r
3541 else if ((reg->anchor & ANCHOR_ANYCHAR_STAR_ML)) {\r
3542 goto begin_position;\r
3543 }\r
3544 }\r
3545 else if (str == end) { /* empty string */\r
3546 static const UChar* address_for_empty_string = (UChar* )"";\r
3547\r
3548#ifdef ONIG_DEBUG_SEARCH\r
3549 fprintf(stderr, "onig_search: empty string.\n");\r
3550#endif\r
3551\r
3552 if (reg->threshold_len == 0) {\r
3553 start = end = str = address_for_empty_string;\r
3554 s = (UChar* )start;\r
3555 prev = (UChar* )NULL;\r
3556\r
3557 MATCH_ARG_INIT(msa, option, region, start);\r
3558#ifdef USE_COMBINATION_EXPLOSION_CHECK\r
3559 msa.state_check_buff = (void* )0;\r
3560 msa.state_check_buff_size = 0; /* NO NEED, for valgrind */\r
3561#endif\r
3562 MATCH_AND_RETURN_CHECK(end);\r
3563 goto mismatch;\r
3564 }\r
3565 goto mismatch_no_msa;\r
3566 }\r
3567\r
3568#ifdef ONIG_DEBUG_SEARCH\r
3569 fprintf(stderr, "onig_search(apply anchor): end: %d, start: %d, range: %d\n",\r
3570 (int )(end - str), (int )(start - str), (int )(range - str));\r
3571#endif\r
3572\r
3573 MATCH_ARG_INIT(msa, option, region, orig_start);\r
3574#ifdef USE_COMBINATION_EXPLOSION_CHECK\r
3575 {\r
3576 int offset = (MIN(start, range) - str);\r
3577 STATE_CHECK_BUFF_INIT(msa, end - str, offset, reg->num_comb_exp_check);\r
3578 }\r
3579#endif\r
3580\r
3581 s = (UChar* )start;\r
3582 if (range > start) { /* forward search */\r
3583 if (s > str)\r
3584 prev = onigenc_get_prev_char_head(reg->enc, str, s);\r
3585 else\r
3586 prev = (UChar* )NULL;\r
3587\r
3588 if (reg->optimize != ONIG_OPTIMIZE_NONE) {\r
3589 UChar *sch_range, *low, *high, *low_prev;\r
3590\r
3591 sch_range = (UChar* )range;\r
3592 if (reg->dmax != 0) {\r
3593 if (reg->dmax == ONIG_INFINITE_DISTANCE)\r
3594 sch_range = (UChar* )end;\r
3595 else {\r
3596 sch_range += reg->dmax;\r
3597 if (sch_range > end) sch_range = (UChar* )end;\r
3598 }\r
3599 }\r
3600\r
3601 if ((end - start) < reg->threshold_len)\r
3602 goto mismatch;\r
3603\r
3604 if (reg->dmax != ONIG_INFINITE_DISTANCE) {\r
3605 do {\r
3606 if (! forward_search_range(reg, str, end, s, sch_range,\r
3607 &low, &high, &low_prev)) goto mismatch;\r
3608 if (s < low) {\r
3609 s = low;\r
3610 prev = low_prev;\r
3611 }\r
3612 while (s <= high) {\r
3613 MATCH_AND_RETURN_CHECK(orig_range);\r
3614 prev = s;\r
3615 s += enclen(reg->enc, s);\r
3616 }\r
3617 } while (s < range);\r
3618 goto mismatch;\r
3619 }\r
3620 else { /* check only. */\r
3621 if (! forward_search_range(reg, str, end, s, sch_range,\r
3622 &low, &high, (UChar** )NULL)) goto mismatch;\r
3623\r
3624 if ((reg->anchor & ANCHOR_ANYCHAR_STAR) != 0) {\r
3625 do {\r
3626 MATCH_AND_RETURN_CHECK(orig_range);\r
3627 prev = s;\r
3628 s += enclen(reg->enc, s);\r
3629\r
3630 while (!ONIGENC_IS_MBC_NEWLINE(reg->enc, prev, end) && s < range) {\r
3631 prev = s;\r
3632 s += enclen(reg->enc, s);\r
3633 }\r
3634 } while (s < range);\r
3635 goto mismatch;\r
3636 }\r
3637 }\r
3638 }\r
3639\r
3640 do {\r
3641 MATCH_AND_RETURN_CHECK(orig_range);\r
3642 prev = s;\r
3643 s += enclen(reg->enc, s);\r
3644 } while (s < range);\r
3645\r
3646 if (s == range) { /* because empty match with /$/. */\r
3647 MATCH_AND_RETURN_CHECK(orig_range);\r
3648 }\r
3649 }\r
3650 else { /* backward search */\r
3651#ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE\r
3652 if (orig_start < end)\r
3653 orig_start += enclen(reg->enc, orig_start); /* is upper range */\r
3654#endif\r
3655\r
3656 if (reg->optimize != ONIG_OPTIMIZE_NONE) {\r
3657 UChar *low, *high, *adjrange, *sch_start;\r
3658\r
3659 if (range < end)\r
3660 adjrange = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, str, range);\r
3661 else\r
3662 adjrange = (UChar* )end;\r
3663\r
3664 if (reg->dmax != ONIG_INFINITE_DISTANCE &&\r
3665 (end - range) >= reg->threshold_len) {\r
3666 do {\r
3667 sch_start = s + reg->dmax;\r
3668 if (sch_start > end) sch_start = (UChar* )end;\r
3669 if (backward_search_range(reg, str, end, sch_start, range, adjrange,\r
3670 &low, &high) <= 0)\r
3671 goto mismatch;\r
3672\r
3673 if (s > high)\r
3674 s = high;\r
3675\r
3676 while (s >= low) {\r
3677 prev = onigenc_get_prev_char_head(reg->enc, str, s);\r
3678 MATCH_AND_RETURN_CHECK(orig_start);\r
3679 s = prev;\r
3680 }\r
3681 } while (s >= range);\r
3682 goto mismatch;\r
3683 }\r
3684 else { /* check only. */\r
3685 if ((end - range) < reg->threshold_len) goto mismatch;\r
3686\r
3687 sch_start = s;\r
3688 if (reg->dmax != 0) {\r
3689 if (reg->dmax == ONIG_INFINITE_DISTANCE)\r
3690 sch_start = (UChar* )end;\r
3691 else {\r
3692 sch_start += reg->dmax;\r
3693 if (sch_start > end) sch_start = (UChar* )end;\r
3694 else\r
3695 sch_start = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc,\r
3696 start, sch_start);\r
3697 }\r
3698 }\r
3699 if (backward_search_range(reg, str, end, sch_start, range, adjrange,\r
3700 &low, &high) <= 0) goto mismatch;\r
3701 }\r
3702 }\r
3703\r
3704 do {\r
3705 prev = onigenc_get_prev_char_head(reg->enc, str, s);\r
3706 MATCH_AND_RETURN_CHECK(orig_start);\r
3707 s = prev;\r
3708 } while (s >= range);\r
3709 }\r
3710\r
3711 mismatch:\r
3712#ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE\r
3713 if (IS_FIND_LONGEST(reg->options)) {\r
3714 if (msa.best_len >= 0) {\r
3715 s = msa.best_s;\r
3716 goto match;\r
3717 }\r
3718 }\r
3719#endif\r
3720 r = ONIG_MISMATCH;\r
3721\r
3722 finish:\r
3723 MATCH_ARG_FREE(msa);\r
3724 ONIG_STATE_DEC_THREAD(reg);\r
3725\r
3726 /* If result is mismatch and no FIND_NOT_EMPTY option,\r
3727 then the region is not setted in match_at(). */\r
3728 if (IS_FIND_NOT_EMPTY(reg->options) && region\r
3729#ifdef USE_POSIX_API_REGION_OPTION\r
3730 && !IS_POSIX_REGION(option)\r
3731#endif\r
3732 ) {\r
3733 onig_region_clear(region);\r
3734 }\r
3735\r
3736#ifdef ONIG_DEBUG\r
3737 if (r != ONIG_MISMATCH)\r
3738 fprintf(stderr, "onig_search: error %d\n", r);\r
3739#endif\r
3740 return r;\r
3741\r
3742 mismatch_no_msa:\r
3743 r = ONIG_MISMATCH;\r
3744 finish_no_msa:\r
3745 ONIG_STATE_DEC_THREAD(reg);\r
3746#ifdef ONIG_DEBUG\r
3747 if (r != ONIG_MISMATCH)\r
3748 fprintf(stderr, "onig_search: error %d\n", r);\r
3749#endif\r
3750 return r;\r
3751\r
3752 match:\r
3753 ONIG_STATE_DEC_THREAD(reg);\r
3754 MATCH_ARG_FREE(msa);\r
3755 return (int)(s - str);\r
3756}\r
3757\r
3758extern OnigEncoding\r
3759onig_get_encoding(regex_t* reg)\r
3760{\r
3761 return reg->enc;\r
3762}\r
3763\r
3764extern OnigOptionType\r
3765onig_get_options(regex_t* reg)\r
3766{\r
3767 return reg->options;\r
3768}\r
3769\r
3770extern OnigCaseFoldType\r
3771onig_get_case_fold_flag(regex_t* reg)\r
3772{\r
3773 return reg->case_fold_flag;\r
3774}\r
3775\r
3776extern OnigSyntaxType*\r
3777onig_get_syntax(regex_t* reg)\r
3778{\r
3779 return reg->syntax;\r
3780}\r
3781\r
3782extern int\r
3783onig_number_of_captures(regex_t* reg)\r
3784{\r
3785 return reg->num_mem;\r
3786}\r
3787\r
3788extern int\r
3789onig_number_of_capture_histories(regex_t* reg)\r
3790{\r
3791#ifdef USE_CAPTURE_HISTORY\r
3792 int i, n;\r
3793\r
3794 n = 0;\r
3795 for (i = 0; i <= ONIG_MAX_CAPTURE_HISTORY_GROUP; i++) {\r
3796 if (BIT_STATUS_AT(reg->capture_history, i) != 0)\r
3797 n++;\r
3798 }\r
3799 return n;\r
3800#else\r
3801 return 0;\r
3802#endif\r
3803}\r
3804\r
3805extern void\r
3806onig_copy_encoding(OnigEncoding to, OnigEncoding from)\r
3807{\r
3808 *to = *from;\r
3809}\r
3810\r
EFI Development Kit II mirror for PVE