Back to index

php5  5.3.10
regexec.c
Go to the documentation of this file.
00001 /**********************************************************************
00002   regexec.c -  Oniguruma (regular expression library)
00003 **********************************************************************/
00004 /*-
00005  * Copyright (c) 2002-2007  K.Kosako  <sndgk393 AT ybb DOT ne DOT jp>
00006  * All rights reserved.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions
00010  * are met:
00011  * 1. Redistributions of source code must retain the above copyright
00012  *    notice, this list of conditions and the following disclaimer.
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice, this list of conditions and the following disclaimer in the
00015  *    documentation and/or other materials provided with the distribution.
00016  *
00017  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
00018  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00019  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00020  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
00021  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00022  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00023  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00024  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00025  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00026  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00027  * SUCH DAMAGE.
00028  */
00029 
00030 #include "regint.h"
00031 
00032 #ifdef USE_CRNL_AS_LINE_TERMINATOR
00033 #define ONIGENC_IS_MBC_CRNL(enc,p,end) \
00034   (ONIGENC_MBC_TO_CODE(enc,p,end) == 13 && \
00035    ONIGENC_IS_MBC_NEWLINE(enc,(p+enc_len(enc,p)),end))
00036 #endif
00037 
00038 #ifdef USE_CAPTURE_HISTORY
00039 static void history_tree_free(OnigCaptureTreeNode* node);
00040 
00041 static void
00042 history_tree_clear(OnigCaptureTreeNode* node)
00043 {
00044   int i;
00045 
00046   if (IS_NOT_NULL(node)) {
00047     for (i = 0; i < node->num_childs; i++) {
00048       if (IS_NOT_NULL(node->childs[i])) {
00049         history_tree_free(node->childs[i]);
00050       }
00051     }
00052     for (i = 0; i < node->allocated; i++) {
00053       node->childs[i] = (OnigCaptureTreeNode* )0;
00054     }
00055     node->num_childs = 0;
00056     node->beg = ONIG_REGION_NOTPOS;
00057     node->end = ONIG_REGION_NOTPOS;
00058     node->group = -1;
00059   }
00060 }
00061 
00062 static void
00063 history_tree_free(OnigCaptureTreeNode* node)
00064 {
00065   history_tree_clear(node);
00066   xfree(node);
00067 }
00068 
00069 static void
00070 history_root_free(OnigRegion* r)
00071 {
00072   if (IS_NOT_NULL(r->history_root)) {
00073     history_tree_free(r->history_root);
00074     r->history_root = (OnigCaptureTreeNode* )0;
00075   }
00076 }
00077 
00078 static OnigCaptureTreeNode*
00079 history_node_new(void)
00080 {
00081   OnigCaptureTreeNode* node;
00082 
00083   node = (OnigCaptureTreeNode* )xmalloc(sizeof(OnigCaptureTreeNode));
00084   CHECK_NULL_RETURN(node);
00085   node->childs     = (OnigCaptureTreeNode** )0;
00086   node->allocated  = 0;
00087   node->num_childs = 0;
00088   node->group      = -1;
00089   node->beg        = ONIG_REGION_NOTPOS;
00090   node->end        = ONIG_REGION_NOTPOS;
00091 
00092   return node;
00093 }
00094 
00095 static int
00096 history_tree_add_child(OnigCaptureTreeNode* parent, OnigCaptureTreeNode* child)
00097 {
00098 #define HISTORY_TREE_INIT_ALLOC_SIZE  8
00099 
00100   if (parent->num_childs >= parent->allocated) {
00101     int n, i;
00102 
00103     if (IS_NULL(parent->childs)) {
00104       n = HISTORY_TREE_INIT_ALLOC_SIZE;
00105       parent->childs =
00106         (OnigCaptureTreeNode** )xmalloc(sizeof(OnigCaptureTreeNode*) * n);
00107     }
00108     else {
00109       n = parent->allocated * 2;
00110       parent->childs =
00111         (OnigCaptureTreeNode** )xrealloc(parent->childs,
00112                                          sizeof(OnigCaptureTreeNode*) * n);
00113     }
00114     CHECK_NULL_RETURN_VAL(parent->childs, ONIGERR_MEMORY);
00115     for (i = parent->allocated; i < n; i++) {
00116       parent->childs[i] = (OnigCaptureTreeNode* )0;
00117     }
00118     parent->allocated = n;
00119   }
00120 
00121   parent->childs[parent->num_childs] = child;
00122   parent->num_childs++;
00123   return 0;
00124 }
00125 
00126 static OnigCaptureTreeNode*
00127 history_tree_clone(OnigCaptureTreeNode* node)
00128 {
00129   int i;
00130   OnigCaptureTreeNode *clone, *child;
00131 
00132   clone = history_node_new();
00133   CHECK_NULL_RETURN(clone);
00134 
00135   clone->beg = node->beg;
00136   clone->end = node->end;
00137   for (i = 0; i < node->num_childs; i++) {
00138     child = history_tree_clone(node->childs[i]);
00139     if (IS_NULL(child)) {
00140       history_tree_free(clone);
00141       return (OnigCaptureTreeNode* )0;
00142     }
00143     history_tree_add_child(clone, child);
00144   }
00145 
00146   return clone;
00147 }
00148 
00149 extern  OnigCaptureTreeNode*
00150 onig_get_capture_tree(OnigRegion* region)
00151 {
00152   return region->history_root;
00153 }
00154 #endif /* USE_CAPTURE_HISTORY */
00155 
00156 extern void
00157 onig_region_clear(OnigRegion* region)
00158 {
00159   int i;
00160 
00161   for (i = 0; i < region->num_regs; i++) {
00162     region->beg[i] = region->end[i] = ONIG_REGION_NOTPOS;
00163   }
00164 #ifdef USE_CAPTURE_HISTORY
00165   history_root_free(region);
00166 #endif
00167 }
00168 
00169 extern int
00170 onig_region_resize(OnigRegion* region, int n)
00171 {
00172   region->num_regs = n;
00173 
00174   if (n < ONIG_NREGION)
00175     n = ONIG_NREGION;
00176 
00177   if (region->allocated == 0) {
00178     region->beg = (int* )xmalloc(n * sizeof(int));
00179     region->end = (int* )xmalloc(n * sizeof(int));
00180 
00181     if (region->beg == 0 || region->end == 0)
00182       return ONIGERR_MEMORY;
00183 
00184     region->allocated = n;
00185   }
00186   else if (region->allocated < n) {
00187     region->beg = (int* )xrealloc(region->beg, n * sizeof(int));
00188     region->end = (int* )xrealloc(region->end, n * sizeof(int));
00189 
00190     if (region->beg == 0 || region->end == 0)
00191       return ONIGERR_MEMORY;
00192 
00193     region->allocated = n;
00194   }
00195 
00196   return 0;
00197 }
00198 
00199 extern int
00200 onig_region_resize_clear(OnigRegion* region, int n)
00201 {
00202   int r;
00203   
00204   r = onig_region_resize(region, n);
00205   if (r != 0) return r;
00206   onig_region_clear(region);
00207   return 0;
00208 }
00209     
00210 extern int
00211 onig_region_set(OnigRegion* region, int at, int beg, int end)
00212 {
00213   if (at < 0) return ONIGERR_INVALID_ARGUMENT;
00214 
00215   if (at >= region->allocated) {
00216     int r = onig_region_resize(region, at + 1);
00217     if (r < 0) return r;
00218   }
00219   
00220   region->beg[at] = beg;
00221   region->end[at] = end;
00222   return 0;
00223 }
00224 
00225 extern void
00226 onig_region_init(OnigRegion* region)
00227 {
00228   region->num_regs     = 0;
00229   region->allocated    = 0;
00230   region->beg          = (int* )0;
00231   region->end          = (int* )0;
00232   region->history_root = (OnigCaptureTreeNode* )0;
00233 }
00234 
00235 extern OnigRegion*
00236 onig_region_new(void)
00237 {
00238   OnigRegion* r;
00239 
00240   r = (OnigRegion* )xmalloc(sizeof(OnigRegion));
00241   onig_region_init(r);
00242   return r;
00243 }
00244 
00245 extern void
00246 onig_region_free(OnigRegion* r, int free_self)
00247 {
00248   if (r) {
00249     if (r->allocated > 0) {
00250       if (r->beg) xfree(r->beg);
00251       if (r->end) xfree(r->end);
00252       r->allocated = 0;
00253     }
00254 #ifdef USE_CAPTURE_HISTORY
00255     history_root_free(r);
00256 #endif
00257     if (free_self) xfree(r);
00258   }
00259 }
00260 
00261 extern void
00262 onig_region_copy(OnigRegion* to, OnigRegion* from)
00263 {
00264 #define RREGC_SIZE   (sizeof(int) * from->num_regs)
00265   int i;
00266 
00267   if (to == from) return;
00268 
00269   if (to->allocated == 0) {
00270     if (from->num_regs > 0) {
00271       to->beg = (int* )xmalloc(RREGC_SIZE);
00272       to->end = (int* )xmalloc(RREGC_SIZE);
00273       to->allocated = from->num_regs;
00274     }
00275   }
00276   else if (to->allocated < from->num_regs) {
00277     to->beg = (int* )xrealloc(to->beg, RREGC_SIZE);
00278     to->end = (int* )xrealloc(to->end, RREGC_SIZE);
00279     to->allocated = from->num_regs;
00280   }
00281 
00282   for (i = 0; i < from->num_regs; i++) {
00283     to->beg[i] = from->beg[i];
00284     to->end[i] = from->end[i];
00285   }
00286   to->num_regs = from->num_regs;
00287 
00288 #ifdef USE_CAPTURE_HISTORY
00289   history_root_free(to);
00290 
00291   if (IS_NOT_NULL(from->history_root)) {
00292     to->history_root = history_tree_clone(from->history_root);
00293   }
00294 #endif
00295 }
00296 
00297 
00299 #define INVALID_STACK_INDEX   -1
00300 typedef long StackIndex;
00301 
00302 typedef struct _StackType {
00303   unsigned int type;
00304   union {
00305     struct {
00306       UChar *pcode;      /* byte code position */
00307       UChar *pstr;       /* string position */
00308       UChar *pstr_prev;  /* previous char position of pstr */
00309 #ifdef USE_COMBINATION_EXPLOSION_CHECK
00310       unsigned int state_check;
00311 #endif
00312     } state;
00313     struct {
00314       int   count;       /* for OP_REPEAT_INC, OP_REPEAT_INC_NG */
00315       UChar *pcode;      /* byte code position (head of repeated target) */
00316       int   num;         /* repeat id */
00317     } repeat;
00318     struct {
00319       StackIndex si;     /* index of stack */
00320     } repeat_inc;
00321     struct {
00322       int num;           /* memory num */
00323       UChar *pstr;       /* start/end position */
00324       /* Following information is setted, if this stack type is MEM-START */
00325       StackIndex start;  /* prev. info (for backtrack  "(...)*" ) */
00326       StackIndex end;    /* prev. info (for backtrack  "(...)*" ) */
00327     } mem;
00328     struct {
00329       int num;           /* null check id */
00330       UChar *pstr;       /* start position */
00331     } null_check;
00332 #ifdef USE_SUBEXP_CALL
00333     struct {
00334       UChar *ret_addr;   /* byte code position */
00335       int    num;        /* null check id */
00336       UChar *pstr;       /* string position */
00337     } call_frame;
00338 #endif
00339   } u;
00340 } StackType;
00341 
00342 /* stack type */
00343 /* used by normal-POP */
00344 #define STK_ALT                    0x0001
00345 #define STK_LOOK_BEHIND_NOT        0x0002
00346 #define STK_POS_NOT                0x0003
00347 /* handled by normal-POP */
00348 #define STK_MEM_START              0x0100
00349 #define STK_MEM_END                0x8200
00350 #define STK_REPEAT_INC             0x0300
00351 #define STK_STATE_CHECK_MARK       0x1000
00352 /* avoided by normal-POP */
00353 #define STK_NULL_CHECK_START       0x3000
00354 #define STK_NULL_CHECK_END         0x5000  /* for recursive call */
00355 #define STK_MEM_END_MARK           0x8400
00356 #define STK_POS                    0x0500  /* used when POP-POS */
00357 #define STK_STOP_BT                0x0600  /* mark for "(?>...)" */
00358 #define STK_REPEAT                 0x0700
00359 #define STK_CALL_FRAME             0x0800
00360 #define STK_RETURN                 0x0900
00361 #define STK_VOID                   0x0a00  /* for fill a blank */
00362 
00363 /* stack type check mask */
00364 #define STK_MASK_POP_USED          0x00ff
00365 #define STK_MASK_TO_VOID_TARGET    0x10ff
00366 #define STK_MASK_MEM_END_OR_MARK   0x8000  /* MEM_END or MEM_END_MARK */
00367 
00368 typedef struct {
00369   void* stack_p;
00370   int   stack_n;
00371   OnigOptionType options;
00372   OnigRegion*    region;
00373   const UChar* start;   /* search start position (for \G: BEGIN_POSITION) */
00374 #ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
00375   int    best_len;      /* for ONIG_OPTION_FIND_LONGEST */
00376   UChar* best_s;
00377 #endif
00378 #ifdef USE_COMBINATION_EXPLOSION_CHECK
00379   void* state_check_buff;
00380   int   state_check_buff_size;
00381 #endif
00382 } MatchArg;
00383 
00384 #ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
00385 #define MATCH_ARG_INIT(msa, arg_option, arg_region, arg_start) do {\
00386   (msa).stack_p  = (void* )0;\
00387   (msa).options  = (arg_option);\
00388   (msa).region   = (arg_region);\
00389   (msa).start    = (arg_start);\
00390   (msa).best_len = ONIG_MISMATCH;\
00391 } while (0)
00392 #else
00393 #define MATCH_ARG_INIT(msa, arg_option, arg_region, arg_start) do {\
00394   (msa).stack_p  = (void* )0;\
00395   (msa).options  = (arg_option);\
00396   (msa).region   = (arg_region);\
00397   (msa).start    = (arg_start);\
00398 } while (0)
00399 #endif
00400 
00401 #ifdef USE_COMBINATION_EXPLOSION_CHECK
00402 
00403 #define STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE  16
00404 
00405 #define STATE_CHECK_BUFF_INIT(msa, str_len, offset, state_num) do {   \
00406   if ((state_num) > 0 && str_len >= STATE_CHECK_STRING_THRESHOLD_LEN) {\
00407     unsigned int size = (unsigned int )(((str_len) + 1) * (state_num) + 7) >> 3;\
00408     offset = ((offset) * (state_num)) >> 3;\
00409     if (size > 0 && offset < size && size < STATE_CHECK_BUFF_MAX_SIZE) {\
00410       if (size >= STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE) \
00411         (msa).state_check_buff = (void* )xmalloc(size);\
00412       else \
00413         (msa).state_check_buff = (void* )xalloca(size);\
00414       xmemset(((char* )((msa).state_check_buff)+(offset)), 0, \
00415               (size_t )(size - (offset))); \
00416       (msa).state_check_buff_size = size;\
00417     }\
00418     else {\
00419       (msa).state_check_buff = (void* )0;\
00420       (msa).state_check_buff_size = 0;\
00421     }\
00422   }\
00423   else {\
00424     (msa).state_check_buff = (void* )0;\
00425     (msa).state_check_buff_size = 0;\
00426   }\
00427 } while (0)
00428 
00429 #define MATCH_ARG_FREE(msa) do {\
00430   if ((msa).stack_p) xfree((msa).stack_p);\
00431   if ((msa).state_check_buff_size >= STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE) { \
00432     if ((msa).state_check_buff) xfree((msa).state_check_buff);\
00433   }\
00434 } while (0);
00435 #else
00436 #define STATE_CHECK_BUFF_INIT(msa, str_len, offset, state_num)
00437 #define MATCH_ARG_FREE(msa)  if ((msa).stack_p) xfree((msa).stack_p)
00438 #endif
00439 
00440 
00441 
00442 #define STACK_INIT(alloc_addr, ptr_num, stack_num)  do {\
00443   if (msa->stack_p) {\
00444     alloc_addr = (char* )xalloca(sizeof(char*) * (ptr_num));\
00445     stk_alloc  = (StackType* )(msa->stack_p);\
00446     stk_base   = stk_alloc;\
00447     stk        = stk_base;\
00448     stk_end    = stk_base + msa->stack_n;\
00449   }\
00450   else {\
00451     alloc_addr = (char* )xalloca(sizeof(char*) * (ptr_num)\
00452                      + sizeof(StackType) * (stack_num));\
00453     stk_alloc  = (StackType* )(alloc_addr + sizeof(char*) * (ptr_num));\
00454     stk_base   = stk_alloc;\
00455     stk        = stk_base;\
00456     stk_end    = stk_base + (stack_num);\
00457   }\
00458 } while(0)
00459 
00460 #define STACK_SAVE do{\
00461   if (stk_base != stk_alloc) {\
00462     msa->stack_p = stk_base;\
00463     msa->stack_n = stk_end - stk_base;\
00464   };\
00465 } while(0)
00466 
00467 static unsigned int MatchStackLimitSize = DEFAULT_MATCH_STACK_LIMIT_SIZE;
00468 
00469 extern unsigned int
00470 onig_get_match_stack_limit_size(void)
00471 {
00472   return MatchStackLimitSize;
00473 }
00474 
00475 extern int
00476 onig_set_match_stack_limit_size(unsigned int size)
00477 {
00478   MatchStackLimitSize = size;
00479   return 0;
00480 }
00481 
00482 static int
00483 stack_double(StackType** arg_stk_base, StackType** arg_stk_end,
00484             StackType** arg_stk, StackType* stk_alloc, MatchArg* msa)
00485 {
00486   unsigned int n;
00487   StackType *x, *stk_base, *stk_end, *stk;
00488 
00489   stk_base = *arg_stk_base;
00490   stk_end  = *arg_stk_end;
00491   stk      = *arg_stk;
00492 
00493   n = stk_end - stk_base;
00494   if (stk_base == stk_alloc && IS_NULL(msa->stack_p)) {
00495     x = (StackType* )xmalloc(sizeof(StackType) * n * 2);
00496     if (IS_NULL(x)) {
00497       STACK_SAVE;
00498       return ONIGERR_MEMORY;
00499     }
00500     xmemcpy(x, stk_base, n * sizeof(StackType));
00501     n *= 2;
00502   }
00503   else {
00504     n *= 2;
00505     if (MatchStackLimitSize != 0 && n > MatchStackLimitSize) {
00506       if ((unsigned int )(stk_end - stk_base) == MatchStackLimitSize)
00507         return ONIGERR_MATCH_STACK_LIMIT_OVER;
00508       else
00509         n = MatchStackLimitSize;
00510     }
00511     x = (StackType* )xrealloc(stk_base, sizeof(StackType) * n);
00512     if (IS_NULL(x)) {
00513       STACK_SAVE;
00514       return ONIGERR_MEMORY;
00515     }
00516   }
00517   *arg_stk      = x + (stk - stk_base);
00518   *arg_stk_base = x;
00519   *arg_stk_end  = x + n;
00520   return 0;
00521 }
00522 
00523 #define STACK_ENSURE(n)     do {\
00524   if (stk_end - stk < (n)) {\
00525     int r = stack_double(&stk_base, &stk_end, &stk, stk_alloc, msa);\
00526     if (r != 0) { STACK_SAVE; return r; } \
00527   }\
00528 } while(0)
00529 
00530 #define STACK_AT(index)        (stk_base + (index))
00531 #define GET_STACK_INDEX(stk)   ((stk) - stk_base)
00532 
00533 #define STACK_PUSH_TYPE(stack_type) do {\
00534   STACK_ENSURE(1);\
00535   stk->type = (stack_type);\
00536   STACK_INC;\
00537 } while(0)
00538 
00539 #define IS_TO_VOID_TARGET(stk) (((stk)->type & STK_MASK_TO_VOID_TARGET) != 0)
00540 
00541 #ifdef USE_COMBINATION_EXPLOSION_CHECK
00542 #define STATE_CHECK_POS(s,snum) \
00543   (((s) - str) * num_comb_exp_check + ((snum) - 1))
00544 #define STATE_CHECK_VAL(v,snum) do {\
00545   if (state_check_buff != NULL) {\
00546     int x = STATE_CHECK_POS(s,snum);\
00547     (v) = state_check_buff[x/8] & (1<<(x%8));\
00548   }\
00549   else (v) = 0;\
00550 } while(0)
00551 
00552 
00553 #define ELSE_IF_STATE_CHECK_MARK(stk) \
00554   else if ((stk)->type == STK_STATE_CHECK_MARK) { \
00555     int x = STATE_CHECK_POS(stk->u.state.pstr, stk->u.state.state_check);\
00556     state_check_buff[x/8] |= (1<<(x%8));                       \
00557   }
00558 
00559 #define STACK_PUSH(stack_type,pat,s,sprev) do {\
00560   STACK_ENSURE(1);\
00561   stk->type = (stack_type);\
00562   stk->u.state.pcode     = (pat);\
00563   stk->u.state.pstr      = (s);\
00564   stk->u.state.pstr_prev = (sprev);\
00565   stk->u.state.state_check = 0;\
00566   STACK_INC;\
00567 } while(0)
00568 
00569 #define STACK_PUSH_ENSURED(stack_type,pat) do {\
00570   stk->type = (stack_type);\
00571   stk->u.state.pcode = (pat);\
00572   stk->u.state.state_check = 0;\
00573   STACK_INC;\
00574 } while(0)
00575 
00576 #define STACK_PUSH_ALT_WITH_STATE_CHECK(pat,s,sprev,snum) do {\
00577   STACK_ENSURE(1);\
00578   stk->type = STK_ALT;\
00579   stk->u.state.pcode     = (pat);\
00580   stk->u.state.pstr      = (s);\
00581   stk->u.state.pstr_prev = (sprev);\
00582   stk->u.state.state_check = ((state_check_buff != NULL) ? (snum) : 0);\
00583   STACK_INC;\
00584 } while(0)
00585 
00586 #define STACK_PUSH_STATE_CHECK(s,snum) do {\
00587   if (state_check_buff != NULL) {\
00588     STACK_ENSURE(1);\
00589     stk->type = STK_STATE_CHECK_MARK;\
00590     stk->u.state.pstr = (s);\
00591     stk->u.state.state_check = (snum);\
00592     STACK_INC;\
00593   }\
00594 } while(0)
00595 
00596 #else /* USE_COMBINATION_EXPLOSION_CHECK */
00597 
00598 #define ELSE_IF_STATE_CHECK_MARK(stk)
00599 
00600 #define STACK_PUSH(stack_type,pat,s,sprev) do {\
00601   STACK_ENSURE(1);\
00602   stk->type = (stack_type);\
00603   stk->u.state.pcode     = (pat);\
00604   stk->u.state.pstr      = (s);\
00605   stk->u.state.pstr_prev = (sprev);\
00606   STACK_INC;\
00607 } while(0)
00608 
00609 #define STACK_PUSH_ENSURED(stack_type,pat) do {\
00610   stk->type = (stack_type);\
00611   stk->u.state.pcode = (pat);\
00612   STACK_INC;\
00613 } while(0)
00614 #endif /* USE_COMBINATION_EXPLOSION_CHECK */
00615 
00616 #define STACK_PUSH_ALT(pat,s,sprev)     STACK_PUSH(STK_ALT,pat,s,sprev)
00617 #define STACK_PUSH_POS(s,sprev)         STACK_PUSH(STK_POS,NULL_UCHARP,s,sprev)
00618 #define STACK_PUSH_POS_NOT(pat,s,sprev) STACK_PUSH(STK_POS_NOT,pat,s,sprev)
00619 #define STACK_PUSH_STOP_BT              STACK_PUSH_TYPE(STK_STOP_BT)
00620 #define STACK_PUSH_LOOK_BEHIND_NOT(pat,s,sprev) \
00621         STACK_PUSH(STK_LOOK_BEHIND_NOT,pat,s,sprev)
00622 
00623 #define STACK_PUSH_REPEAT(id, pat) do {\
00624   STACK_ENSURE(1);\
00625   stk->type = STK_REPEAT;\
00626   stk->u.repeat.num    = (id);\
00627   stk->u.repeat.pcode  = (pat);\
00628   stk->u.repeat.count  = 0;\
00629   STACK_INC;\
00630 } while(0)
00631 
00632 #define STACK_PUSH_REPEAT_INC(sindex) do {\
00633   STACK_ENSURE(1);\
00634   stk->type = STK_REPEAT_INC;\
00635   stk->u.repeat_inc.si  = (sindex);\
00636   STACK_INC;\
00637 } while(0)
00638 
00639 #define STACK_PUSH_MEM_START(mnum, s) do {\
00640   STACK_ENSURE(1);\
00641   stk->type = STK_MEM_START;\
00642   stk->u.mem.num      = (mnum);\
00643   stk->u.mem.pstr     = (s);\
00644   stk->u.mem.start    = mem_start_stk[mnum];\
00645   stk->u.mem.end      = mem_end_stk[mnum];\
00646   mem_start_stk[mnum] = GET_STACK_INDEX(stk);\
00647   mem_end_stk[mnum]   = INVALID_STACK_INDEX;\
00648   STACK_INC;\
00649 } while(0)
00650 
00651 #define STACK_PUSH_MEM_END(mnum, s) do {\
00652   STACK_ENSURE(1);\
00653   stk->type = STK_MEM_END;\
00654   stk->u.mem.num    = (mnum);\
00655   stk->u.mem.pstr   = (s);\
00656   stk->u.mem.start  = mem_start_stk[mnum];\
00657   stk->u.mem.end    = mem_end_stk[mnum];\
00658   mem_end_stk[mnum] = GET_STACK_INDEX(stk);\
00659   STACK_INC;\
00660 } while(0)
00661 
00662 #define STACK_PUSH_MEM_END_MARK(mnum) do {\
00663   STACK_ENSURE(1);\
00664   stk->type = STK_MEM_END_MARK;\
00665   stk->u.mem.num = (mnum);\
00666   STACK_INC;\
00667 } while(0)
00668 
00669 #define STACK_GET_MEM_START(mnum, k) do {\
00670   int level = 0;\
00671   k = stk;\
00672   while (k > stk_base) {\
00673     k--;\
00674     if ((k->type & STK_MASK_MEM_END_OR_MARK) != 0 \
00675       && k->u.mem.num == (mnum)) {\
00676       level++;\
00677     }\
00678     else if (k->type == STK_MEM_START && k->u.mem.num == (mnum)) {\
00679       if (level == 0) break;\
00680       level--;\
00681     }\
00682   }\
00683 } while (0)
00684 
00685 #define STACK_GET_MEM_RANGE(k, mnum, start, end) do {\
00686   int level = 0;\
00687   while (k < stk) {\
00688     if (k->type == STK_MEM_START && k->u.mem.num == (mnum)) {\
00689       if (level == 0) (start) = k->u.mem.pstr;\
00690       level++;\
00691     }\
00692     else if (k->type == STK_MEM_END && k->u.mem.num == (mnum)) {\
00693       level--;\
00694       if (level == 0) {\
00695         (end) = k->u.mem.pstr;\
00696         break;\
00697       }\
00698     }\
00699     k++;\
00700   }\
00701 } while (0)
00702 
00703 #define STACK_PUSH_NULL_CHECK_START(cnum, s) do {\
00704   STACK_ENSURE(1);\
00705   stk->type = STK_NULL_CHECK_START;\
00706   stk->u.null_check.num  = (cnum);\
00707   stk->u.null_check.pstr = (s);\
00708   STACK_INC;\
00709 } while(0)
00710 
00711 #define STACK_PUSH_NULL_CHECK_END(cnum) do {\
00712   STACK_ENSURE(1);\
00713   stk->type = STK_NULL_CHECK_END;\
00714   stk->u.null_check.num  = (cnum);\
00715   STACK_INC;\
00716 } while(0)
00717 
00718 #define STACK_PUSH_CALL_FRAME(pat) do {\
00719   STACK_ENSURE(1);\
00720   stk->type = STK_CALL_FRAME;\
00721   stk->u.call_frame.ret_addr = (pat);\
00722   STACK_INC;\
00723 } while(0)
00724 
00725 #define STACK_PUSH_RETURN do {\
00726   STACK_ENSURE(1);\
00727   stk->type = STK_RETURN;\
00728   STACK_INC;\
00729 } while(0)
00730 
00731 
00732 #ifdef ONIG_DEBUG
00733 #define STACK_BASE_CHECK(p, at) \
00734   if ((p) < stk_base) {\
00735     fprintf(stderr, "at %s\n", at);\
00736     goto stack_error;\
00737   }
00738 #else
00739 #define STACK_BASE_CHECK(p, at)
00740 #endif
00741 
00742 #define STACK_POP_ONE do {\
00743   stk--;\
00744   STACK_BASE_CHECK(stk, "STACK_POP_ONE"); \
00745 } while(0)
00746 
00747 #define STACK_POP  do {\
00748   switch (pop_level) {\
00749   case STACK_POP_LEVEL_FREE:\
00750     while (1) {\
00751       stk--;\
00752       STACK_BASE_CHECK(stk, "STACK_POP"); \
00753       if ((stk->type & STK_MASK_POP_USED) != 0)  break;\
00754       ELSE_IF_STATE_CHECK_MARK(stk);\
00755     }\
00756     break;\
00757   case STACK_POP_LEVEL_MEM_START:\
00758     while (1) {\
00759       stk--;\
00760       STACK_BASE_CHECK(stk, "STACK_POP 2"); \
00761       if ((stk->type & STK_MASK_POP_USED) != 0)  break;\
00762       else if (stk->type == STK_MEM_START) {\
00763         mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
00764         mem_end_stk[stk->u.mem.num]   = stk->u.mem.end;\
00765       }\
00766       ELSE_IF_STATE_CHECK_MARK(stk);\
00767     }\
00768     break;\
00769   default:\
00770     while (1) {\
00771       stk--;\
00772       STACK_BASE_CHECK(stk, "STACK_POP 3"); \
00773       if ((stk->type & STK_MASK_POP_USED) != 0)  break;\
00774       else if (stk->type == STK_MEM_START) {\
00775         mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
00776         mem_end_stk[stk->u.mem.num]   = stk->u.mem.end;\
00777       }\
00778       else if (stk->type == STK_REPEAT_INC) {\
00779         STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\
00780       }\
00781       else if (stk->type == STK_MEM_END) {\
00782         mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
00783         mem_end_stk[stk->u.mem.num]   = stk->u.mem.end;\
00784       }\
00785       ELSE_IF_STATE_CHECK_MARK(stk);\
00786     }\
00787     break;\
00788   }\
00789 } while(0)
00790 
00791 #define STACK_POP_TIL_POS_NOT  do {\
00792   while (1) {\
00793     stk--;\
00794     STACK_BASE_CHECK(stk, "STACK_POP_TIL_POS_NOT"); \
00795     if (stk->type == STK_POS_NOT) break;\
00796     else if (stk->type == STK_MEM_START) {\
00797       mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
00798       mem_end_stk[stk->u.mem.num]   = stk->u.mem.end;\
00799     }\
00800     else if (stk->type == STK_REPEAT_INC) {\
00801       STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\
00802     }\
00803     else if (stk->type == STK_MEM_END) {\
00804       mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
00805       mem_end_stk[stk->u.mem.num]   = stk->u.mem.end;\
00806     }\
00807     ELSE_IF_STATE_CHECK_MARK(stk);\
00808   }\
00809 } while(0)
00810 
00811 #define STACK_POP_TIL_LOOK_BEHIND_NOT  do {\
00812   while (1) {\
00813     stk--;\
00814     STACK_BASE_CHECK(stk, "STACK_POP_TIL_LOOK_BEHIND_NOT"); \
00815     if (stk->type == STK_LOOK_BEHIND_NOT) break;\
00816     else if (stk->type == STK_MEM_START) {\
00817       mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
00818       mem_end_stk[stk->u.mem.num]   = stk->u.mem.end;\
00819     }\
00820     else if (stk->type == STK_REPEAT_INC) {\
00821       STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\
00822     }\
00823     else if (stk->type == STK_MEM_END) {\
00824       mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
00825       mem_end_stk[stk->u.mem.num]   = stk->u.mem.end;\
00826     }\
00827     ELSE_IF_STATE_CHECK_MARK(stk);\
00828   }\
00829 } while(0)
00830 
00831 #define STACK_POS_END(k) do {\
00832   k = stk;\
00833   while (1) {\
00834     k--;\
00835     STACK_BASE_CHECK(k, "STACK_POS_END"); \
00836     if (IS_TO_VOID_TARGET(k)) {\
00837       k->type = STK_VOID;\
00838     }\
00839     else if (k->type == STK_POS) {\
00840       k->type = STK_VOID;\
00841       break;\
00842     }\
00843   }\
00844 } while(0)
00845 
00846 #define STACK_STOP_BT_END do {\
00847   StackType *k = stk;\
00848   while (1) {\
00849     k--;\
00850     STACK_BASE_CHECK(k, "STACK_STOP_BT_END"); \
00851     if (IS_TO_VOID_TARGET(k)) {\
00852       k->type = STK_VOID;\
00853     }\
00854     else if (k->type == STK_STOP_BT) {\
00855       k->type = STK_VOID;\
00856       break;\
00857     }\
00858   }\
00859 } while(0)
00860 
00861 #define STACK_NULL_CHECK(isnull,id,s) do {\
00862   StackType* k = stk;\
00863   while (1) {\
00864     k--;\
00865     STACK_BASE_CHECK(k, "STACK_NULL_CHECK"); \
00866     if (k->type == STK_NULL_CHECK_START) {\
00867       if (k->u.null_check.num == (id)) {\
00868         (isnull) = (k->u.null_check.pstr == (s));\
00869         break;\
00870       }\
00871     }\
00872   }\
00873 } while(0)
00874 
00875 #define STACK_NULL_CHECK_REC(isnull,id,s) do {\
00876   int level = 0;\
00877   StackType* k = stk;\
00878   while (1) {\
00879     k--;\
00880     STACK_BASE_CHECK(k, "STACK_NULL_CHECK_REC"); \
00881     if (k->type == STK_NULL_CHECK_START) {\
00882       if (k->u.null_check.num == (id)) {\
00883         if (level == 0) {\
00884           (isnull) = (k->u.null_check.pstr == (s));\
00885           break;\
00886         }\
00887         else level--;\
00888       }\
00889     }\
00890     else if (k->type == STK_NULL_CHECK_END) {\
00891       level++;\
00892     }\
00893   }\
00894 } while(0)
00895 
00896 #define STACK_NULL_CHECK_MEMST(isnull,id,s,reg) do {\
00897   StackType* k = stk;\
00898   while (1) {\
00899     k--;\
00900     STACK_BASE_CHECK(k, "STACK_NULL_CHECK_MEMST"); \
00901     if (k->type == STK_NULL_CHECK_START) {\
00902       if (k->u.null_check.num == (id)) {\
00903         if (k->u.null_check.pstr != (s)) {\
00904           (isnull) = 0;\
00905           break;\
00906         }\
00907         else {\
00908           UChar* endp;\
00909           (isnull) = 1;\
00910           while (k < stk) {\
00911             if (k->type == STK_MEM_START) {\
00912               if (k->u.mem.end == INVALID_STACK_INDEX) {\
00913                 (isnull) = 0; break;\
00914               }\
00915               if (BIT_STATUS_AT(reg->bt_mem_end, k->u.mem.num))\
00916                 endp = STACK_AT(k->u.mem.end)->u.mem.pstr;\
00917               else\
00918                 endp = (UChar* )k->u.mem.end;\
00919               if (STACK_AT(k->u.mem.start)->u.mem.pstr != endp) {\
00920                 (isnull) = 0; break;\
00921               }\
00922               else if (endp != s) {\
00923                 (isnull) = -1; /* empty, but position changed */ \
00924               }\
00925             }\
00926             k++;\
00927           }\
00928          break;\
00929         }\
00930       }\
00931     }\
00932   }\
00933 } while(0)
00934 
00935 #define STACK_NULL_CHECK_MEMST_REC(isnull,id,s,reg) do {\
00936   int level = 0;\
00937   StackType* k = stk;\
00938   while (1) {\
00939     k--;\
00940     STACK_BASE_CHECK(k, "STACK_NULL_CHECK_MEMST_REC"); \
00941     if (k->type == STK_NULL_CHECK_START) {\
00942       if (k->u.null_check.num == (id)) {\
00943         if (level == 0) {\
00944           if (k->u.null_check.pstr != (s)) {\
00945             (isnull) = 0;\
00946             break;\
00947           }\
00948           else {\
00949             UChar* endp;\
00950             (isnull) = 1;\
00951             while (k < stk) {\
00952               if (k->type == STK_MEM_START) {\
00953                 if (k->u.mem.end == INVALID_STACK_INDEX) {\
00954                   (isnull) = 0; break;\
00955                 }\
00956                 if (BIT_STATUS_AT(reg->bt_mem_end, k->u.mem.num))\
00957                   endp = STACK_AT(k->u.mem.end)->u.mem.pstr;\
00958                 else\
00959                   endp = (UChar* )k->u.mem.end;\
00960                 if (STACK_AT(k->u.mem.start)->u.mem.pstr != endp) {\
00961                   (isnull) = 0; break;\
00962                 }\
00963                 else if (endp != s) {\
00964                   (isnull) = -1; /* empty, but position changed */ \
00965                 }\
00966               }\
00967               k++;\
00968             }\
00969            break;\
00970           }\
00971         }\
00972         else {\
00973           level--;\
00974         }\
00975       }\
00976     }\
00977     else if (k->type == STK_NULL_CHECK_END) {\
00978       if (k->u.null_check.num == (id)) level++;\
00979     }\
00980   }\
00981 } while(0)
00982 
00983 #define STACK_GET_REPEAT(id, k) do {\
00984   int level = 0;\
00985   k = stk;\
00986   while (1) {\
00987     k--;\
00988     STACK_BASE_CHECK(k, "STACK_GET_REPEAT"); \
00989     if (k->type == STK_REPEAT) {\
00990       if (level == 0) {\
00991         if (k->u.repeat.num == (id)) {\
00992           break;\
00993         }\
00994       }\
00995     }\
00996     else if (k->type == STK_CALL_FRAME) level--;\
00997     else if (k->type == STK_RETURN)     level++;\
00998   }\
00999 } while (0)
01000 
01001 #define STACK_RETURN(addr)  do {\
01002   int level = 0;\
01003   StackType* k = stk;\
01004   while (1) {\
01005     k--;\
01006     STACK_BASE_CHECK(k, "STACK_RETURN"); \
01007     if (k->type == STK_CALL_FRAME) {\
01008       if (level == 0) {\
01009         (addr) = k->u.call_frame.ret_addr;\
01010         break;\
01011       }\
01012       else level--;\
01013     }\
01014     else if (k->type == STK_RETURN)\
01015       level++;\
01016   }\
01017 } while(0)
01018 
01019 
01020 #define STRING_CMP(s1,s2,len) do {\
01021   while (len-- > 0) {\
01022     if (*s1++ != *s2++) goto fail;\
01023   }\
01024 } while(0)
01025 
01026 #define STRING_CMP_IC(ambig_flag,s1,ps2,len) do {\
01027   if (string_cmp_ic(encode, ambig_flag, s1, ps2, len) == 0) \
01028     goto fail; \
01029 } while(0)
01030 
01031 static int string_cmp_ic(OnigEncoding enc, int ambig_flag,
01032                       UChar* s1, UChar** ps2, int mblen)
01033 {
01034   UChar buf1[ONIGENC_MBC_NORMALIZE_MAXLEN];
01035   UChar buf2[ONIGENC_MBC_NORMALIZE_MAXLEN];
01036   UChar *p1, *p2, *end, *s2, *end2;
01037   int len1, len2;
01038 
01039   s2   = *ps2;
01040   end  = s1 + mblen;
01041   end2 = s2 + mblen;
01042   while (s1 < end) {
01043     len1 = ONIGENC_MBC_TO_NORMALIZE(enc, ambig_flag, &s1, end, buf1);
01044     len2 = ONIGENC_MBC_TO_NORMALIZE(enc, ambig_flag, &s2, end2, buf2);
01045     if (len1 != len2) return 0;
01046     p1 = buf1;
01047     p2 = buf2;
01048     while (len1-- > 0) {
01049       if (*p1 != *p2) return 0;
01050       p1++;
01051       p2++;
01052     }
01053   }
01054 
01055   *ps2 = s2;
01056   return 1;
01057 }
01058 
01059 #define STRING_CMP_VALUE(s1,s2,len,is_fail) do {\
01060   is_fail = 0;\
01061   while (len-- > 0) {\
01062     if (*s1++ != *s2++) {\
01063       is_fail = 1; break;\
01064     }\
01065   }\
01066 } while(0)
01067 
01068 #define STRING_CMP_VALUE_IC(ambig_flag,s1,ps2,len,is_fail) do {\
01069   if (string_cmp_ic(encode, ambig_flag, s1, ps2, len) == 0) \
01070     is_fail = 1; \
01071   else \
01072     is_fail = 0; \
01073 } while(0)
01074 
01075 
01076 #define ON_STR_BEGIN(s)  ((s) == str)
01077 #define ON_STR_END(s)    ((s) == end)
01078 #define IS_EMPTY_STR     (str == end)
01079 
01080 #define DATA_ENSURE(n) \
01081   if (s + (n) > end) goto fail
01082 
01083 #define DATA_ENSURE_CHECK(n)   (s + (n) <= end)
01084 
01085 #ifdef USE_CAPTURE_HISTORY
01086 static int
01087 make_capture_history_tree(OnigCaptureTreeNode* node, StackType** kp,
01088                           StackType* stk_top, UChar* str, regex_t* reg)
01089 {
01090   int n, r;
01091   OnigCaptureTreeNode* child;
01092   StackType* k = *kp;
01093 
01094   while (k < stk_top) {
01095     if (k->type == STK_MEM_START) {
01096       n = k->u.mem.num;
01097       if (n <= ONIG_MAX_CAPTURE_HISTORY_GROUP &&
01098           BIT_STATUS_AT(reg->capture_history, n) != 0) {
01099         child = history_node_new();
01100         CHECK_NULL_RETURN_VAL(child, ONIGERR_MEMORY);
01101         child->group = n;
01102         child->beg = (int )(k->u.mem.pstr - str);
01103         r = history_tree_add_child(node, child);
01104         if (r != 0) return r;
01105         *kp = (k + 1);
01106         r = make_capture_history_tree(child, kp, stk_top, str, reg);
01107         if (r != 0) return r;
01108 
01109         k = *kp;
01110         child->end = (int )(k->u.mem.pstr - str);
01111       }
01112     }
01113     else if (k->type == STK_MEM_END) {
01114       if (k->u.mem.num == node->group) {
01115         node->end = (int )(k->u.mem.pstr - str);
01116         *kp = k;
01117         return 0;
01118       }
01119     }
01120     k++;
01121   }
01122 
01123   return 1; /* 1: root node ending. */
01124 }
01125 #endif
01126 
01127 #ifdef USE_BACKREF_AT_LEVEL
01128 static int mem_is_in_memp(int mem, int num, UChar* memp)
01129 {
01130   int i;
01131   MemNumType m;
01132 
01133   for (i = 0; i < num; i++) {
01134     GET_MEMNUM_INC(m, memp);
01135     if (mem == (int )m) return 1;
01136   }
01137   return 0;
01138 }
01139 
01140 static int backref_match_at_nested_level(regex_t* reg
01141         , StackType* top, StackType* stk_base
01142         , int ignore_case, int ambig_flag
01143         , int nest, int mem_num, UChar* memp, UChar** s, const UChar* send)
01144 {
01145   UChar *ss, *p, *pstart, *pend = NULL_UCHARP;
01146   int level;
01147   StackType* k;
01148 
01149   level = 0;
01150   k = top;
01151   k--;
01152   while (k >= stk_base) {
01153     if (k->type == STK_CALL_FRAME) {
01154       level--;
01155     }
01156     else if (k->type == STK_RETURN) {
01157       level++;
01158     }
01159     else if (level == nest) {
01160       if (k->type == STK_MEM_START) {
01161        if (mem_is_in_memp(k->u.mem.num, mem_num, memp)) {
01162          pstart = k->u.mem.pstr;
01163          if (pend != NULL_UCHARP) {
01164            if (pend - pstart > send - *s) return 0; /* or goto next_mem; */
01165            p  = pstart;
01166            ss = *s;
01167 
01168            if (ignore_case != 0) {
01169              if (string_cmp_ic(reg->enc, ambig_flag,
01170                             pstart, &ss, (int )(pend - pstart)) == 0)
01171               return 0; /* or goto next_mem; */
01172            }
01173            else {
01174              while (p < pend) {
01175               if (*p++ != *ss++) return 0; /* or goto next_mem; */
01176              }
01177            }
01178 
01179            *s = ss;
01180            return 1;
01181          }
01182        }
01183       }
01184       else if (k->type == STK_MEM_END) {
01185        if (mem_is_in_memp(k->u.mem.num, mem_num, memp)) {
01186          pend = k->u.mem.pstr;
01187        }
01188       }
01189     }
01190     k--;
01191   }
01192 
01193   return 0;
01194 }
01195 #endif /* USE_BACKREF_AT_LEVEL */
01196 
01197 
01198 #ifdef RUBY_PLATFORM
01199 
01200 typedef struct {
01201   int state;
01202   regex_t*  reg;
01203   MatchArg* msa;
01204   StackType* stk_base;
01205 } TrapEnsureArg;
01206 
01207 static VALUE
01208 trap_ensure(VALUE arg)
01209 {
01210   TrapEnsureArg* ta = (TrapEnsureArg* )arg;
01211 
01212   if (ta->state == 0) { /* trap_exec() is not normal return */
01213     ONIG_STATE_DEC_THREAD(ta->reg);
01214     if (! IS_NULL(ta->msa->stack_p) && ta->stk_base != ta->msa->stack_p)
01215       xfree(ta->stk_base);
01216 
01217     MATCH_ARG_FREE(*(ta->msa));
01218   }
01219 
01220   return Qnil;
01221 }
01222 
01223 static VALUE
01224 trap_exec(VALUE arg)
01225 {
01226   TrapEnsureArg* ta;
01227 
01228   rb_trap_exec();
01229 
01230   ta = (TrapEnsureArg* )arg;
01231   ta->state = 1; /* normal return */
01232   return Qnil;
01233 }
01234 
01235 extern void
01236 onig_exec_trap(regex_t* reg, MatchArg* msa, StackType* stk_base)
01237 {
01238   VALUE arg;
01239   TrapEnsureArg ta;
01240 
01241   ta.state    = 0;
01242   ta.reg      = reg;
01243   ta.msa      = msa;
01244   ta.stk_base = stk_base;
01245   arg = (VALUE )(&ta);
01246   rb_ensure(trap_exec, arg, trap_ensure, arg);
01247 }
01248 
01249 #define CHECK_INTERRUPT_IN_MATCH_AT do {\
01250   if (rb_trap_pending) {\
01251     if (! rb_prohibit_interrupt) {\
01252       onig_exec_trap(reg, msa, stk_base);\
01253     }\
01254   }\
01255 } while (0)
01256 #else
01257 #define CHECK_INTERRUPT_IN_MATCH_AT
01258 #endif /* RUBY_PLATFORM */
01259 
01260 #ifdef ONIG_DEBUG_STATISTICS
01261 
01262 #define USE_TIMEOFDAY
01263 
01264 #ifdef USE_TIMEOFDAY
01265 #ifdef HAVE_SYS_TIME_H
01266 #include <sys/time.h>
01267 #endif
01268 #ifdef HAVE_UNISTD_H
01269 #include <unistd.h>
01270 #endif
01271 static struct timeval ts, te;
01272 #define GETTIME(t)        gettimeofday(&(t), (struct timezone* )0)
01273 #define TIMEDIFF(te,ts)   (((te).tv_usec - (ts).tv_usec) + \
01274                            (((te).tv_sec - (ts).tv_sec)*1000000))
01275 #else
01276 #ifdef HAVE_SYS_TIMES_H
01277 #include <sys/times.h>
01278 #endif
01279 static struct tms ts, te;
01280 #define GETTIME(t)         times(&(t))
01281 #define TIMEDIFF(te,ts)   ((te).tms_utime - (ts).tms_utime)
01282 #endif
01283 
01284 static int OpCounter[256];
01285 static int OpPrevCounter[256];
01286 static unsigned long OpTime[256];
01287 static int OpCurr = OP_FINISH;
01288 static int OpPrevTarget = OP_FAIL;
01289 static int MaxStackDepth = 0;
01290 
01291 #define STAT_OP_IN(opcode) do {\
01292   if (opcode == OpPrevTarget) OpPrevCounter[OpCurr]++;\
01293   OpCurr = opcode;\
01294   OpCounter[opcode]++;\
01295   GETTIME(ts);\
01296 } while (0)
01297 
01298 #define STAT_OP_OUT do {\
01299   GETTIME(te);\
01300   OpTime[OpCurr] += TIMEDIFF(te, ts);\
01301 } while (0)
01302 
01303 #ifdef RUBY_PLATFORM
01304 
01305 /*
01306  * :nodoc:
01307  */
01308 static VALUE onig_stat_print(void)
01309 {
01310   onig_print_statistics(stderr);
01311   return Qnil;
01312 }
01313 #endif
01314 
01315 extern void onig_statistics_init(void)
01316 {
01317   int i;
01318   for (i = 0; i < 256; i++) {
01319     OpCounter[i] = OpPrevCounter[i] = 0; OpTime[i] = 0;
01320   }
01321   MaxStackDepth = 0;
01322 
01323 #ifdef RUBY_PLATFORM
01324   rb_define_global_function("onig_stat_print", onig_stat_print, 0);
01325 #endif
01326 }
01327 
01328 extern void
01329 onig_print_statistics(FILE* f)
01330 {
01331   int i;
01332   fprintf(f, "   count      prev        time\n");
01333   for (i = 0; OnigOpInfo[i].opcode >= 0; i++) {
01334     fprintf(f, "%8d: %8d: %10ld: %s\n",
01335            OpCounter[i], OpPrevCounter[i], OpTime[i], OnigOpInfo[i].name);
01336   }
01337   fprintf(f, "\nmax stack depth: %d\n", MaxStackDepth);
01338 }
01339 
01340 #define STACK_INC do {\
01341   stk++;\
01342   if (stk - stk_base > MaxStackDepth) \
01343     MaxStackDepth = stk - stk_base;\
01344 } while (0)
01345 
01346 #else
01347 #define STACK_INC     stk++
01348 
01349 #define STAT_OP_IN(opcode)
01350 #define STAT_OP_OUT
01351 #endif
01352 
01353 extern int
01354 onig_is_in_code_range(const UChar* p, OnigCodePoint code)
01355 {
01356   OnigCodePoint n, *data;
01357   OnigCodePoint low, high, x;
01358 
01359   GET_CODE_POINT(n, p);
01360   data = (OnigCodePoint* )p;
01361   data++;
01362 
01363   for (low = 0, high = n; low < high; ) {
01364     x = (low + high) >> 1;
01365     if (code > data[x * 2 + 1])
01366       low = x + 1;
01367     else
01368       high = x;
01369   }
01370 
01371   return ((low < n && code >= data[low * 2]) ? 1 : 0);
01372 }
01373 
01374 static int
01375 is_code_in_cc(int enclen, OnigCodePoint code, CClassNode* cc)
01376 {
01377   int found;
01378 
01379   if (enclen > 1 || (code >= SINGLE_BYTE_SIZE)) {
01380     if (IS_NULL(cc->mbuf)) {
01381       found = 0;
01382     }
01383     else {
01384       found = (onig_is_in_code_range(cc->mbuf->p, code) != 0 ? 1 : 0);
01385     }
01386   }
01387   else {
01388     found = (BITSET_AT(cc->bs, code) == 0 ? 0 : 1);
01389   }
01390 
01391   if (IS_CCLASS_NOT(cc))
01392     return !found;
01393   else
01394     return found;
01395 }
01396 
01397 extern int
01398 onig_is_code_in_cc(OnigEncoding enc, OnigCodePoint code, CClassNode* cc)
01399 {
01400   int len;
01401 
01402   if (ONIGENC_MBC_MINLEN(enc) > 1) {
01403     len = 2;
01404   }
01405   else {
01406     len = ONIGENC_CODE_TO_MBCLEN(enc, code);
01407   }
01408   return is_code_in_cc(len, code, cc);
01409 }
01410 
01411 
01412 /* matching region of POSIX API */
01413 typedef int regoff_t;
01414 
01415 typedef struct {
01416   regoff_t  rm_so;
01417   regoff_t  rm_eo;
01418 } posix_regmatch_t;
01419 
01420 /* match data(str - end) from position (sstart). */
01421 /* if sstart == str then set sprev to NULL. */
01422 static int
01423 match_at(regex_t* reg, const UChar* str, const UChar* end, const UChar* sstart,
01424         UChar* sprev, MatchArg* msa)
01425 {
01426   static UChar FinishCode[] = { OP_FINISH };
01427 
01428   int i, n, num_mem, best_len, pop_level;
01429   LengthType tlen, tlen2;
01430   MemNumType mem;
01431   RelAddrType addr;
01432   OnigOptionType option = reg->options;
01433   OnigEncoding encode = reg->enc;
01434   OnigAmbigType ambig_flag = reg->ambig_flag;
01435   UChar *s, *q, *sbegin;
01436   UChar *p = reg->p;
01437   char *alloca_base;
01438   StackType *stk_alloc, *stk_base, *stk, *stk_end;
01439   StackType *stkp; /* used as any purpose. */
01440   StackIndex si;
01441   StackIndex *repeat_stk;
01442   StackIndex *mem_start_stk, *mem_end_stk;
01443 #ifdef USE_COMBINATION_EXPLOSION_CHECK
01444   int scv;
01445   unsigned char* state_check_buff = msa->state_check_buff;
01446   int num_comb_exp_check = reg->num_comb_exp_check;
01447 #endif
01448   n = reg->num_repeat + reg->num_mem * 2;
01449 
01450   STACK_INIT(alloca_base, n, INIT_MATCH_STACK_SIZE);
01451   pop_level = reg->stack_pop_level;
01452   num_mem = reg->num_mem;
01453   repeat_stk = (StackIndex* )alloca_base;
01454 
01455   mem_start_stk = (StackIndex* )(repeat_stk + reg->num_repeat);
01456   mem_end_stk   = mem_start_stk + num_mem;
01457   mem_start_stk--; /* for index start from 1,
01458                     mem_start_stk[1]..mem_start_stk[num_mem] */
01459   mem_end_stk--;   /* for index start from 1,
01460                     mem_end_stk[1]..mem_end_stk[num_mem] */
01461   for (i = 1; i <= num_mem; i++) {
01462     mem_start_stk[i] = mem_end_stk[i] = INVALID_STACK_INDEX;
01463   }
01464 
01465 #ifdef ONIG_DEBUG_MATCH
01466   fprintf(stderr, "match_at: str: %d, end: %d, start: %d, sprev: %d\n",
01467          (int )str, (int )end, (int )sstart, (int )sprev);
01468   fprintf(stderr, "size: %d, start offset: %d\n",
01469          (int )(end - str), (int )(sstart - str));
01470 #endif
01471 
01472   STACK_PUSH_ENSURED(STK_ALT, FinishCode);  /* bottom stack */
01473   best_len = ONIG_MISMATCH;
01474   s = (UChar* )sstart;
01475   while (1) {
01476 #ifdef ONIG_DEBUG_MATCH
01477     {
01478       UChar *q, *bp, buf[50];
01479       int len;
01480       fprintf(stderr, "%4d> \"", (int )(s - str));
01481       bp = buf;
01482       for (i = 0, q = s; i < 7 && q < end; i++) {
01483        len = enc_len(encode, q);
01484        while (len-- > 0) *bp++ = *q++;
01485       }
01486       if (q < end) { xmemcpy(bp, "...\"", 4); bp += 4; }
01487       else         { xmemcpy(bp, "\"",    1); bp += 1; }
01488       *bp = 0;
01489       fputs(buf, stderr);
01490       for (i = 0; i < 20 - (bp - buf); i++) fputc(' ', stderr);
01491       onig_print_compiled_byte_code(stderr, p, NULL, encode);
01492       fprintf(stderr, "\n");
01493     }
01494 #endif
01495 
01496     sbegin = s;
01497     switch (*p++) {
01498     case OP_END:  STAT_OP_IN(OP_END);
01499       n = s - sstart;
01500       if (n > best_len) {
01501        OnigRegion* region;
01502 #ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
01503        if (IS_FIND_LONGEST(option)) {
01504          if (n > msa->best_len) {
01505            msa->best_len = n;
01506            msa->best_s   = (UChar* )sstart;
01507          }
01508          else
01509            goto end_best_len;
01510         }
01511 #endif
01512        best_len = n;
01513        region = msa->region;
01514        if (region) {
01515 #ifdef USE_POSIX_REGION_OPTION
01516          if (IS_POSIX_REGION(msa->options)) {
01517            posix_regmatch_t* rmt = (posix_regmatch_t* )region;
01518 
01519            rmt[0].rm_so = sstart - str;
01520            rmt[0].rm_eo = s      - str;
01521            for (i = 1; i <= num_mem; i++) {
01522              if (mem_end_stk[i] != INVALID_STACK_INDEX) {
01523               if (BIT_STATUS_AT(reg->bt_mem_start, i))
01524                 rmt[i].rm_so = STACK_AT(mem_start_stk[i])->u.mem.pstr - str;
01525               else
01526                 rmt[i].rm_so = (UChar* )((void* )(mem_start_stk[i])) - str;
01527 
01528               rmt[i].rm_eo = (BIT_STATUS_AT(reg->bt_mem_end, i)
01529                             ? STACK_AT(mem_end_stk[i])->u.mem.pstr
01530                             : (UChar* )((void* )mem_end_stk[i])) - str;
01531              }
01532              else {
01533               rmt[i].rm_so = rmt[i].rm_eo = ONIG_REGION_NOTPOS;
01534              }
01535            }
01536          }
01537          else {
01538 #endif /* USE_POSIX_REGION_OPTION */
01539            region->beg[0] = sstart - str;
01540            region->end[0] = s      - str;
01541            for (i = 1; i <= num_mem; i++) {
01542              if (mem_end_stk[i] != INVALID_STACK_INDEX) {
01543               if (BIT_STATUS_AT(reg->bt_mem_start, i))
01544                 region->beg[i] = STACK_AT(mem_start_stk[i])->u.mem.pstr - str;
01545               else
01546                 region->beg[i] = (UChar* )((void* )mem_start_stk[i]) - str;
01547 
01548               region->end[i] = (BIT_STATUS_AT(reg->bt_mem_end, i)
01549                               ? STACK_AT(mem_end_stk[i])->u.mem.pstr
01550                               : (UChar* )((void* )mem_end_stk[i])) - str;
01551              }
01552              else {
01553               region->beg[i] = region->end[i] = ONIG_REGION_NOTPOS;
01554              }
01555            }
01556 
01557 #ifdef USE_CAPTURE_HISTORY
01558            if (reg->capture_history != 0) {
01559               int r;
01560               OnigCaptureTreeNode* node;
01561 
01562               if (IS_NULL(region->history_root)) {
01563                 region->history_root = node = history_node_new();
01564                 CHECK_NULL_RETURN_VAL(node, ONIGERR_MEMORY);
01565               }
01566               else {
01567                 node = region->history_root;
01568                 history_tree_clear(node);
01569               }
01570 
01571               node->group = 0;
01572               node->beg   = sstart - str;
01573               node->end   = s      - str;
01574 
01575               stkp = stk_base;
01576               r = make_capture_history_tree(region->history_root, &stkp,
01577                                             stk, (UChar* )str, reg);
01578               if (r < 0) {
01579                 best_len = r; /* error code */
01580                 goto finish;
01581               }
01582            }
01583 #endif /* USE_CAPTURE_HISTORY */
01584 #ifdef USE_POSIX_REGION_OPTION
01585          } /* else IS_POSIX_REGION() */
01586 #endif
01587        } /* if (region) */
01588       } /* n > best_len */
01589 
01590 #ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
01591     end_best_len:
01592 #endif
01593       STAT_OP_OUT;
01594 
01595       if (IS_FIND_CONDITION(option)) {
01596        if (IS_FIND_NOT_EMPTY(option) && s == sstart) {
01597          best_len = ONIG_MISMATCH;
01598          goto fail; /* for retry */
01599        }
01600        if (IS_FIND_LONGEST(option) && s < end) {
01601          goto fail; /* for retry */
01602        }
01603       }
01604 
01605       /* default behavior: return first-matching result. */
01606       goto finish;
01607       break;
01608 
01609     case OP_EXACT1:  STAT_OP_IN(OP_EXACT1);
01610 #if 0
01611       DATA_ENSURE(1);
01612       if (*p != *s) goto fail;
01613       p++; s++;
01614 #endif
01615       if (*p != *s++) goto fail;
01616       DATA_ENSURE(0);
01617       p++;
01618       STAT_OP_OUT;
01619       break;
01620 
01621     case OP_EXACT1_IC:  STAT_OP_IN(OP_EXACT1_IC);
01622       {
01623        int len;
01624        UChar *q, *ss, *sp, lowbuf[ONIGENC_MBC_NORMALIZE_MAXLEN];
01625 
01626        DATA_ENSURE(1);
01627         ss = s;
01628         sp = p;
01629 
01630        len = ONIGENC_MBC_TO_NORMALIZE(encode, ambig_flag, &s, end, lowbuf);
01631        DATA_ENSURE(0);
01632        q = lowbuf;
01633        while (len-- > 0) {
01634          if (*p != *q) {
01635             goto fail;
01636           }
01637          p++; q++;
01638        }
01639       }
01640       STAT_OP_OUT;
01641       break;
01642 
01643     case OP_EXACT2:  STAT_OP_IN(OP_EXACT2);
01644       DATA_ENSURE(2);
01645       if (*p != *s) goto fail;
01646       p++; s++;
01647       if (*p != *s) goto fail;
01648       sprev = s;
01649       p++; s++;
01650       STAT_OP_OUT;
01651       continue;
01652       break;
01653 
01654     case OP_EXACT3:  STAT_OP_IN(OP_EXACT3);
01655       DATA_ENSURE(3);
01656       if (*p != *s) goto fail;
01657       p++; s++;
01658       if (*p != *s) goto fail;
01659       p++; s++;
01660       if (*p != *s) goto fail;
01661       sprev = s;
01662       p++; s++;
01663       STAT_OP_OUT;
01664       continue;
01665       break;
01666 
01667     case OP_EXACT4:  STAT_OP_IN(OP_EXACT4);
01668       DATA_ENSURE(4);
01669       if (*p != *s) goto fail;
01670       p++; s++;
01671       if (*p != *s) goto fail;
01672       p++; s++;
01673       if (*p != *s) goto fail;
01674       p++; s++;
01675       if (*p != *s) goto fail;
01676       sprev = s;
01677       p++; s++;
01678       STAT_OP_OUT;
01679       continue;
01680       break;
01681 
01682     case OP_EXACT5:  STAT_OP_IN(OP_EXACT5);
01683       DATA_ENSURE(5);
01684       if (*p != *s) goto fail;
01685       p++; s++;
01686       if (*p != *s) goto fail;
01687       p++; s++;
01688       if (*p != *s) goto fail;
01689       p++; s++;
01690       if (*p != *s) goto fail;
01691       p++; s++;
01692       if (*p != *s) goto fail;
01693       sprev = s;
01694       p++; s++;
01695       STAT_OP_OUT;
01696       continue;
01697       break;
01698 
01699     case OP_EXACTN:  STAT_OP_IN(OP_EXACTN);
01700       GET_LENGTH_INC(tlen, p);
01701       DATA_ENSURE(tlen);
01702       while (tlen-- > 0) {
01703        if (*p++ != *s++) goto fail;
01704       }
01705       sprev = s - 1;
01706       STAT_OP_OUT;
01707       continue;
01708       break;
01709 
01710     case OP_EXACTN_IC:  STAT_OP_IN(OP_EXACTN_IC);
01711       {
01712        int len;
01713        UChar *ss, *sp, *q, *endp, lowbuf[ONIGENC_MBC_NORMALIZE_MAXLEN];
01714 
01715        GET_LENGTH_INC(tlen, p);
01716        endp = p + tlen;
01717 
01718        while (p < endp) {
01719          sprev = s;
01720          DATA_ENSURE(1);
01721           ss = s;
01722           sp = p;
01723 
01724          len = ONIGENC_MBC_TO_NORMALIZE(encode, ambig_flag, &s, end, lowbuf);
01725          DATA_ENSURE(0);
01726          q = lowbuf;
01727          while (len-- > 0) {
01728            if (*p != *q) {
01729               goto fail;
01730             }
01731            p++; q++;
01732          }
01733        }
01734       }
01735 
01736       STAT_OP_OUT;
01737       continue;
01738       break;
01739 
01740     case OP_EXACTMB2N1:  STAT_OP_IN(OP_EXACTMB2N1);
01741       DATA_ENSURE(2);
01742       if (*p != *s) goto fail;
01743       p++; s++;
01744       if (*p != *s) goto fail;
01745       p++; s++;
01746       STAT_OP_OUT;
01747       break;
01748 
01749     case OP_EXACTMB2N2:  STAT_OP_IN(OP_EXACTMB2N2);
01750       DATA_ENSURE(4);
01751       if (*p != *s) goto fail;
01752       p++; s++;
01753       if (*p != *s) goto fail;
01754       p++; s++;
01755       sprev = s;
01756       if (*p != *s) goto fail;
01757       p++; s++;
01758       if (*p != *s) goto fail;
01759       p++; s++;
01760       STAT_OP_OUT;
01761       continue;
01762       break;
01763 
01764     case OP_EXACTMB2N3:  STAT_OP_IN(OP_EXACTMB2N3);
01765       DATA_ENSURE(6);
01766       if (*p != *s) goto fail;
01767       p++; s++;
01768       if (*p != *s) goto fail;
01769       p++; s++;
01770       if (*p != *s) goto fail;
01771       p++; s++;
01772       if (*p != *s) goto fail;
01773       p++; s++;
01774       sprev = s;
01775       if (*p != *s) goto fail;
01776       p++; s++;
01777       if (*p != *s) goto fail;
01778       p++; s++;
01779       STAT_OP_OUT;
01780       continue;
01781       break;
01782 
01783     case OP_EXACTMB2N:  STAT_OP_IN(OP_EXACTMB2N);
01784       GET_LENGTH_INC(tlen, p);
01785       DATA_ENSURE(tlen * 2);
01786       while (tlen-- > 0) {
01787        if (*p != *s) goto fail;
01788        p++; s++;
01789        if (*p != *s) goto fail;
01790        p++; s++;
01791       }
01792       sprev = s - 2;
01793       STAT_OP_OUT;
01794       continue;
01795       break;
01796 
01797     case OP_EXACTMB3N:  STAT_OP_IN(OP_EXACTMB3N);
01798       GET_LENGTH_INC(tlen, p);
01799       DATA_ENSURE(tlen * 3);
01800       while (tlen-- > 0) {
01801        if (*p != *s) goto fail;
01802        p++; s++;
01803        if (*p != *s) goto fail;
01804        p++; s++;
01805        if (*p != *s) goto fail;
01806        p++; s++;
01807       }
01808       sprev = s - 3;
01809       STAT_OP_OUT;
01810       continue;
01811       break;
01812 
01813     case OP_EXACTMBN:  STAT_OP_IN(OP_EXACTMBN);
01814       GET_LENGTH_INC(tlen,  p);  /* mb-len */
01815       GET_LENGTH_INC(tlen2, p);  /* string len */
01816       tlen2 *= tlen;
01817       DATA_ENSURE(tlen2);
01818       while (tlen2-- > 0) {
01819        if (*p != *s) goto fail;
01820        p++; s++;
01821       }
01822       sprev = s - tlen;
01823       STAT_OP_OUT;
01824       continue;
01825       break;
01826 
01827     case OP_CCLASS:  STAT_OP_IN(OP_CCLASS);
01828       DATA_ENSURE(1);
01829       if (BITSET_AT(((BitSetRef )p), *s) == 0) goto fail;
01830       p += SIZE_BITSET;
01831       s += enc_len(encode, s);   /* OP_CCLASS can match mb-code. \D, \S */
01832       STAT_OP_OUT;
01833       break;
01834 
01835     case OP_CCLASS_MB:  STAT_OP_IN(OP_CCLASS_MB);
01836       if (! ONIGENC_IS_MBC_HEAD(encode, s)) goto fail;
01837 
01838     cclass_mb:
01839       GET_LENGTH_INC(tlen, p);
01840       {
01841        OnigCodePoint code;
01842        UChar *ss;
01843        int mb_len;
01844 
01845        DATA_ENSURE(1);
01846        mb_len = enc_len(encode, s);
01847        DATA_ENSURE(mb_len);
01848        ss = s;
01849        s += mb_len;
01850        code = ONIGENC_MBC_TO_CODE(encode, ss, s);
01851 
01852 #ifdef PLATFORM_UNALIGNED_WORD_ACCESS
01853        if (! onig_is_in_code_range(p, code)) goto fail;
01854 #else
01855        q = p;
01856        ALIGNMENT_RIGHT(q);
01857        if (! onig_is_in_code_range(q, code)) goto fail;
01858 #endif
01859       }
01860       p += tlen;
01861       STAT_OP_OUT;
01862       break;
01863 
01864     case OP_CCLASS_MIX:  STAT_OP_IN(OP_CCLASS_MIX);
01865       DATA_ENSURE(1);
01866       if (ONIGENC_IS_MBC_HEAD(encode, s)) {
01867        p += SIZE_BITSET;
01868        goto cclass_mb;
01869       }
01870       else {
01871        if (BITSET_AT(((BitSetRef )p), *s) == 0)
01872          goto fail;
01873 
01874        p += SIZE_BITSET;
01875        GET_LENGTH_INC(tlen, p);
01876        p += tlen;
01877        s++;
01878       }
01879       STAT_OP_OUT;
01880       break;
01881 
01882     case OP_CCLASS_NOT:  STAT_OP_IN(OP_CCLASS_NOT);
01883       DATA_ENSURE(1);
01884       if (BITSET_AT(((BitSetRef )p), *s) != 0) goto fail;
01885       p += SIZE_BITSET;
01886       s += enc_len(encode, s);
01887       STAT_OP_OUT;
01888       break;
01889 
01890     case OP_CCLASS_MB_NOT:  STAT_OP_IN(OP_CCLASS_MB_NOT);
01891       DATA_ENSURE(1);
01892       if (! ONIGENC_IS_MBC_HEAD(encode, s)) {
01893        s++;
01894        GET_LENGTH_INC(tlen, p);
01895        p += tlen;
01896        goto cc_mb_not_success;
01897       }
01898 
01899     cclass_mb_not:
01900       GET_LENGTH_INC(tlen, p);
01901       {
01902        OnigCodePoint code;
01903        UChar *ss;
01904        int mb_len = enc_len(encode, s);
01905 
01906        if (s + mb_len > end) {
01907           DATA_ENSURE(1);
01908          s = (UChar* )end;
01909          p += tlen;
01910          goto cc_mb_not_success;
01911        }
01912 
01913        ss = s;
01914        s += mb_len;
01915        code = ONIGENC_MBC_TO_CODE(encode, ss, s);
01916 
01917 #ifdef PLATFORM_UNALIGNED_WORD_ACCESS
01918        if (onig_is_in_code_range(p, code)) goto fail;
01919 #else
01920        q = p;
01921        ALIGNMENT_RIGHT(q);
01922        if (onig_is_in_code_range(q, code)) goto fail;
01923 #endif
01924       }
01925       p += tlen;
01926 
01927     cc_mb_not_success:
01928       STAT_OP_OUT;
01929       break;
01930 
01931     case OP_CCLASS_MIX_NOT:  STAT_OP_IN(OP_CCLASS_MIX_NOT);
01932       DATA_ENSURE(1);
01933       if (ONIGENC_IS_MBC_HEAD(encode, s)) {
01934        p += SIZE_BITSET;
01935        goto cclass_mb_not;
01936       }
01937       else {
01938        if (BITSET_AT(((BitSetRef )p), *s) != 0)
01939          goto fail;
01940 
01941        p += SIZE_BITSET;
01942        GET_LENGTH_INC(tlen, p);
01943        p += tlen;
01944        s++;
01945       }
01946       STAT_OP_OUT;
01947       break;
01948 
01949     case OP_CCLASS_NODE:  STAT_OP_IN(OP_CCLASS_NODE);
01950       {
01951        OnigCodePoint code;
01952         void *node;
01953         int mb_len;
01954         UChar *ss;
01955 
01956         DATA_ENSURE(1);
01957         GET_POINTER_INC(node, p);
01958        mb_len = enc_len(encode, s);
01959        ss = s;
01960        s += mb_len;
01961        DATA_ENSURE(0);
01962        code = ONIGENC_MBC_TO_CODE(encode, ss, s);
01963        if (is_code_in_cc(mb_len, code, node) == 0) goto fail;
01964       }
01965       STAT_OP_OUT;
01966       break;
01967 
01968     case OP_ANYCHAR:  STAT_OP_IN(OP_ANYCHAR);
01969       DATA_ENSURE(1);
01970       n = enc_len(encode, s);
01971       DATA_ENSURE(n);
01972       if (ONIGENC_IS_MBC_NEWLINE(encode, s, end)) goto fail;
01973       s += n;
01974       STAT_OP_OUT;
01975       break;
01976 
01977     case OP_ANYCHAR_ML:  STAT_OP_IN(OP_ANYCHAR_ML);
01978       DATA_ENSURE(1);
01979       n = enc_len(encode, s);
01980       DATA_ENSURE(n);
01981       s += n;
01982       STAT_OP_OUT;
01983       break;
01984 
01985     case OP_ANYCHAR_STAR:  STAT_OP_IN(OP_ANYCHAR_STAR);
01986       while (s < end) {
01987        STACK_PUSH_ALT(p, s, sprev);
01988        n = enc_len(encode, s);
01989         DATA_ENSURE(n);
01990         if (ONIGENC_IS_MBC_NEWLINE(encode, s, end))  goto fail;
01991         sprev = s;
01992         s += n;
01993       }
01994       STAT_OP_OUT;
01995       break;
01996 
01997     case OP_ANYCHAR_ML_STAR:  STAT_OP_IN(OP_ANYCHAR_ML_STAR);
01998       while (s < end) {
01999        STACK_PUSH_ALT(p, s, sprev);
02000        n = enc_len(encode, s);
02001        if (n > 1) {
02002          DATA_ENSURE(n);
02003          sprev = s;
02004          s += n;
02005        }
02006        else {
02007          sprev = s;
02008          s++;
02009        }
02010       }
02011       STAT_OP_OUT;
02012       break;
02013 
02014     case OP_ANYCHAR_STAR_PEEK_NEXT:  STAT_OP_IN(OP_ANYCHAR_STAR_PEEK_NEXT);
02015       while (s < end) {
02016        if (*p == *s) {
02017          STACK_PUSH_ALT(p + 1, s, sprev);
02018        }
02019        n = enc_len(encode, s);
02020         DATA_ENSURE(n);
02021         if (ONIGENC_IS_MBC_NEWLINE(encode, s, end))  goto fail;
02022         sprev = s;
02023         s += n;
02024       }
02025       p++;
02026       STAT_OP_OUT;
02027       break;
02028 
02029     case OP_ANYCHAR_ML_STAR_PEEK_NEXT:STAT_OP_IN(OP_ANYCHAR_ML_STAR_PEEK_NEXT);
02030       while (s < end) {
02031        if (*p == *s) {
02032          STACK_PUSH_ALT(p + 1, s, sprev);
02033        }
02034        n = enc_len(encode, s);
02035        if (n >1) {
02036          DATA_ENSURE(n);
02037          sprev = s;
02038          s += n;
02039        }
02040        else {
02041          sprev = s;
02042          s++;
02043        }
02044       }
02045       p++;
02046       STAT_OP_OUT;
02047       break;
02048 
02049 #ifdef USE_COMBINATION_EXPLOSION_CHECK
02050     case OP_STATE_CHECK_ANYCHAR_STAR:  STAT_OP_IN(OP_STATE_CHECK_ANYCHAR_STAR);
02051       GET_STATE_CHECK_NUM_INC(mem, p);
02052       while (s < end) {
02053        STATE_CHECK_VAL(scv, mem);
02054        if (scv) goto fail;
02055 
02056        STACK_PUSH_ALT_WITH_STATE_CHECK(p, s, sprev, mem);
02057        n = enc_len(encode, s);
02058         DATA_ENSURE(n);
02059         if (ONIGENC_IS_MBC_NEWLINE(encode, s, end))  goto fail;
02060         sprev = s;
02061         s += n;
02062       }
02063       STAT_OP_OUT;
02064       break;
02065 
02066     case OP_STATE_CHECK_ANYCHAR_ML_STAR:
02067       STAT_OP_IN(OP_STATE_CHECK_ANYCHAR_ML_STAR);
02068 
02069       GET_STATE_CHECK_NUM_INC(mem, p);
02070       while (s < end) {
02071        STATE_CHECK_VAL(scv, mem);
02072        if (scv) goto fail;
02073 
02074        STACK_PUSH_ALT_WITH_STATE_CHECK(p, s, sprev, mem);
02075        n = enc_len(encode, s);
02076        if (n > 1) {
02077          DATA_ENSURE(n);
02078          sprev = s;
02079          s += n;
02080        }
02081        else {
02082          sprev = s;
02083          s++;
02084        }
02085       }
02086       STAT_OP_OUT;
02087       break;
02088 #endif /* USE_COMBINATION_EXPLOSION_CHECK */
02089 
02090     case OP_WORD:  STAT_OP_IN(OP_WORD);
02091       DATA_ENSURE(1);
02092       if (! ONIGENC_IS_MBC_WORD(encode, s, end))
02093        goto fail;
02094 
02095       s += enc_len(encode, s);
02096       STAT_OP_OUT;
02097       break;
02098 
02099     case OP_NOT_WORD:  STAT_OP_IN(OP_NOT_WORD);
02100       DATA_ENSURE(1);
02101       if (ONIGENC_IS_MBC_WORD(encode, s, end))
02102        goto fail;
02103 
02104       s += enc_len(encode, s);
02105       STAT_OP_OUT;
02106       break;
02107 
02108     case OP_WORD_BOUND:  STAT_OP_IN(OP_WORD_BOUND);
02109       if (ON_STR_BEGIN(s)) {
02110        DATA_ENSURE(1);
02111        if (! ONIGENC_IS_MBC_WORD(encode, s, end))
02112          goto fail;
02113       }
02114       else if (ON_STR_END(s)) {
02115        if (! ONIGENC_IS_MBC_WORD(encode, sprev, end))
02116          goto fail;
02117       }
02118       else {
02119        if (ONIGENC_IS_MBC_WORD(encode, s, end)
02120            == ONIGENC_IS_MBC_WORD(encode, sprev, end))
02121          goto fail;
02122       }
02123       STAT_OP_OUT;
02124       continue;
02125       break;
02126 
02127     case OP_NOT_WORD_BOUND:  STAT_OP_IN(OP_NOT_WORD_BOUND);
02128       if (ON_STR_BEGIN(s)) {
02129        if (DATA_ENSURE_CHECK(1) && ONIGENC_IS_MBC_WORD(encode, s, end))
02130          goto fail;
02131       }
02132       else if (ON_STR_END(s)) {
02133        if (ONIGENC_IS_MBC_WORD(encode, sprev, end))
02134          goto fail;
02135       }
02136       else {
02137        if (ONIGENC_IS_MBC_WORD(encode, s, end)
02138            != ONIGENC_IS_MBC_WORD(encode, sprev, end))
02139          goto fail;
02140       }
02141       STAT_OP_OUT;
02142       continue;
02143       break;
02144 
02145 #ifdef USE_WORD_BEGIN_END
02146     case OP_WORD_BEGIN:  STAT_OP_IN(OP_WORD_BEGIN);
02147       if (DATA_ENSURE_CHECK(1) && ONIGENC_IS_MBC_WORD(encode, s, end)) {
02148        if (ON_STR_BEGIN(s) || !ONIGENC_IS_MBC_WORD(encode, sprev, end)) {
02149          STAT_OP_OUT;
02150          continue;
02151        }
02152       }
02153       goto fail;
02154       break;
02155 
02156     case OP_WORD_END:  STAT_OP_IN(OP_WORD_END);
02157       if (!ON_STR_BEGIN(s) && ONIGENC_IS_MBC_WORD(encode, sprev, end)) {
02158        if (ON_STR_END(s) || !ONIGENC_IS_MBC_WORD(encode, s, end)) {
02159          STAT_OP_OUT;
02160          continue;
02161        }
02162       }
02163       goto fail;
02164       break;
02165 #endif
02166 
02167     case OP_BEGIN_BUF:  STAT_OP_IN(OP_BEGIN_BUF);
02168       if (! ON_STR_BEGIN(s)) goto fail;
02169 
02170       STAT_OP_OUT;
02171       continue;
02172       break;
02173 
02174     case OP_END_BUF:  STAT_OP_IN(OP_END_BUF);
02175       if (! ON_STR_END(s)) goto fail;
02176 
02177       STAT_OP_OUT;
02178       continue;
02179       break;
02180 
02181     case OP_BEGIN_LINE:  STAT_OP_IN(OP_BEGIN_LINE);
02182       if (ON_STR_BEGIN(s)) {
02183        if (IS_NOTBOL(msa->options)) goto fail;
02184        STAT_OP_OUT;
02185        continue;
02186       }
02187       else if (ONIGENC_IS_MBC_NEWLINE(encode, sprev, end) && !ON_STR_END(s)) {
02188        STAT_OP_OUT;
02189        continue;
02190       }
02191       goto fail;
02192       break;
02193 
02194     case OP_END_LINE:  STAT_OP_IN(OP_END_LINE);
02195       if (ON_STR_END(s)) {
02196 #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
02197        if (IS_EMPTY_STR || !ONIGENC_IS_MBC_NEWLINE(encode, sprev, end)) {
02198 #endif
02199          if (IS_NOTEOL(msa->options)) goto fail;
02200          STAT_OP_OUT;
02201          continue;
02202 #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
02203        }
02204 #endif
02205       }
02206       else if (ONIGENC_IS_MBC_NEWLINE(encode, s, end)) {
02207        STAT_OP_OUT;
02208        continue;
02209       }
02210 #ifdef USE_CRNL_AS_LINE_TERMINATOR
02211       else if (ONIGENC_IS_MBC_CRNL(encode, s, end)) {
02212        STAT_OP_OUT;
02213        continue;
02214       }
02215 #endif
02216       goto fail;
02217       break;
02218 
02219     case OP_SEMI_END_BUF:  STAT_OP_IN(OP_SEMI_END_BUF);
02220       if (ON_STR_END(s)) {
02221 #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
02222        if (IS_EMPTY_STR || !ONIGENC_IS_MBC_NEWLINE(encode, sprev, end)) {
02223 #endif
02224          if (IS_NOTEOL(msa->options)) goto fail;   /* Is it needed? */
02225          STAT_OP_OUT;
02226          continue;
02227 #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
02228        }
02229 #endif
02230       }
02231       else if (ONIGENC_IS_MBC_NEWLINE(encode, s, end) &&
02232               ON_STR_END(s + enc_len(encode, s))) {
02233        STAT_OP_OUT;
02234        continue;
02235       }
02236 #ifdef USE_CRNL_AS_LINE_TERMINATOR
02237       else if (ONIGENC_IS_MBC_CRNL(encode, s, end)) {
02238         UChar* ss = s + enc_len(encode, s);
02239         if (ON_STR_END(ss + enc_len(encode, ss))) {
02240           STAT_OP_OUT;
02241           continue;
02242         }
02243       }
02244 #endif
02245       goto fail;
02246       break;
02247 
02248     case OP_BEGIN_POSITION:  STAT_OP_IN(OP_BEGIN_POSITION);
02249       if (s != msa->start)
02250        goto fail;
02251 
02252       STAT_OP_OUT;
02253       continue;
02254       break;
02255 
02256     case OP_MEMORY_START_PUSH:  STAT_OP_IN(OP_MEMORY_START_PUSH);
02257       GET_MEMNUM_INC(mem, p);
02258       STACK_PUSH_MEM_START(mem, s);
02259       STAT_OP_OUT;
02260       continue;
02261       break;
02262 
02263     case OP_MEMORY_START:  STAT_OP_IN(OP_MEMORY_START);
02264       GET_MEMNUM_INC(mem, p);
02265       mem_start_stk[mem] = (StackIndex )((void* )s);
02266       STAT_OP_OUT;
02267       continue;
02268       break;
02269 
02270     case OP_MEMORY_END_PUSH:  STAT_OP_IN(OP_MEMORY_END_PUSH);
02271       GET_MEMNUM_INC(mem, p);
02272       STACK_PUSH_MEM_END(mem, s);
02273       STAT_OP_OUT;
02274       continue;
02275       break;
02276 
02277     case OP_MEMORY_END:  STAT_OP_IN(OP_MEMORY_END);
02278       GET_MEMNUM_INC(mem, p);
02279       mem_end_stk[mem] = (StackIndex )((void* )s);
02280       STAT_OP_OUT;
02281       continue;
02282       break;
02283 
02284 #ifdef USE_SUBEXP_CALL
02285     case OP_MEMORY_END_PUSH_REC:  STAT_OP_IN(OP_MEMORY_END_PUSH_REC);
02286       GET_MEMNUM_INC(mem, p);
02287       STACK_GET_MEM_START(mem, stkp); /* should be before push mem-end. */
02288       STACK_PUSH_MEM_END(mem, s);
02289       mem_start_stk[mem] = GET_STACK_INDEX(stkp);
02290       STAT_OP_OUT;
02291       continue;
02292       break;
02293 
02294     case OP_MEMORY_END_REC:  STAT_OP_IN(OP_MEMORY_END_REC);
02295       GET_MEMNUM_INC(mem, p);
02296       mem_end_stk[mem] = (StackIndex )((void* )s);
02297       STACK_GET_MEM_START(mem, stkp);
02298 
02299       if (BIT_STATUS_AT(reg->bt_mem_start, mem))
02300        mem_start_stk[mem] = GET_STACK_INDEX(stkp);
02301       else
02302        mem_start_stk[mem] = (StackIndex )((void* )stkp->u.mem.pstr);
02303 
02304       STACK_PUSH_MEM_END_MARK(mem);
02305       STAT_OP_OUT;
02306       continue;
02307       break;
02308 #endif
02309 
02310     case OP_BACKREF1:  STAT_OP_IN(OP_BACKREF1);
02311       mem = 1;
02312       goto backref;
02313       break;
02314 
02315     case OP_BACKREF2:  STAT_OP_IN(OP_BACKREF2);
02316       mem = 2;
02317       goto backref;
02318       break;
02319 
02320     case OP_BACKREFN:  STAT_OP_IN(OP_BACKREFN);
02321       GET_MEMNUM_INC(mem, p);
02322     backref:
02323       {
02324        int len;
02325        UChar *pstart, *pend;
02326 
02327        /* if you want to remove following line, 
02328           you should check in parse and compile time. */
02329        if (mem > num_mem) goto fail;
02330        if (mem_end_stk[mem]   == INVALID_STACK_INDEX) goto fail;
02331        if (mem_start_stk[mem] == INVALID_STACK_INDEX) goto fail;
02332 
02333        if (BIT_STATUS_AT(reg->bt_mem_start, mem))
02334          pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;
02335        else
02336          pstart = (UChar* )((void* )mem_start_stk[mem]);
02337 
02338        pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)
02339               ? STACK_AT(mem_end_stk[mem])->u.mem.pstr
02340               : (UChar* )((void* )mem_end_stk[mem]));
02341        n = pend - pstart;
02342        DATA_ENSURE(n);
02343        sprev = s;
02344        STRING_CMP(pstart, s, n);
02345        while (sprev + (len = enc_len(encode, sprev)) < s)
02346          sprev += len;
02347 
02348        STAT_OP_OUT;
02349        continue;
02350       }
02351       break;
02352 
02353     case OP_BACKREFN_IC:  STAT_OP_IN(OP_BACKREFN_IC);
02354       GET_MEMNUM_INC(mem, p);
02355       {
02356        int len;
02357        UChar *pstart, *pend;
02358 
02359        /* if you want to remove following line, 
02360           you should check in parse and compile time. */
02361        if (mem > num_mem) goto fail;
02362        if (mem_end_stk[mem]   == INVALID_STACK_INDEX) goto fail;
02363        if (mem_start_stk[mem] == INVALID_STACK_INDEX) goto fail;
02364 
02365        if (BIT_STATUS_AT(reg->bt_mem_start, mem))
02366          pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;
02367        else
02368          pstart = (UChar* )((void* )mem_start_stk[mem]);
02369 
02370        pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)
02371               ? STACK_AT(mem_end_stk[mem])->u.mem.pstr
02372               : (UChar* )((void* )mem_end_stk[mem]));
02373        n = pend - pstart;
02374        DATA_ENSURE(n);
02375        sprev = s;
02376        STRING_CMP_IC(ambig_flag, pstart, &s, n);
02377        while (sprev + (len = enc_len(encode, sprev)) < s)
02378          sprev += len;
02379 
02380        STAT_OP_OUT;
02381        continue;
02382       }
02383       break;
02384 
02385     case OP_BACKREF_MULTI:  STAT_OP_IN(OP_BACKREF_MULTI);
02386       {
02387        int len, is_fail;
02388        UChar *pstart, *pend, *swork;
02389 
02390        GET_LENGTH_INC(tlen, p);
02391        for (i = 0; i < tlen; i++) {
02392          GET_MEMNUM_INC(mem, p);
02393 
02394          if (mem_end_stk[mem]   == INVALID_STACK_INDEX) continue;
02395          if (mem_start_stk[mem] == INVALID_STACK_INDEX) continue;
02396 
02397          if (BIT_STATUS_AT(reg->bt_mem_start, mem))
02398            pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;
02399          else
02400            pstart = (UChar* )((void* )mem_start_stk[mem]);
02401 
02402          pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)
02403                 ? STACK_AT(mem_end_stk[mem])->u.mem.pstr
02404                 : (UChar* )((void* )mem_end_stk[mem]));
02405          n = pend - pstart;
02406          DATA_ENSURE(n);
02407          sprev = s;
02408          swork = s;
02409          STRING_CMP_VALUE(pstart, swork, n, is_fail);
02410          if (is_fail) continue;
02411          s = swork;
02412          while (sprev + (len = enc_len(encode, sprev)) < s)
02413            sprev += len;
02414 
02415          p += (SIZE_MEMNUM * (tlen - i - 1));
02416          break; /* success */
02417        }
02418        if (i == tlen) goto fail;
02419        STAT_OP_OUT;
02420        continue;
02421       }
02422       break;
02423 
02424     case OP_BACKREF_MULTI_IC:  STAT_OP_IN(OP_BACKREF_MULTI_IC);
02425       {
02426        int len, is_fail;
02427        UChar *pstart, *pend, *swork;
02428 
02429        GET_LENGTH_INC(tlen, p);
02430        for (i = 0; i < tlen; i++) {
02431          GET_MEMNUM_INC(mem, p);
02432 
02433          if (mem_end_stk[mem]   == INVALID_STACK_INDEX) continue;
02434          if (mem_start_stk[mem] == INVALID_STACK_INDEX) continue;
02435 
02436          if (BIT_STATUS_AT(reg->bt_mem_start, mem))
02437            pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;
02438          else
02439            pstart = (UChar* )((void* )mem_start_stk[mem]);
02440 
02441          pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)
02442                 ? STACK_AT(mem_end_stk[mem])->u.mem.pstr
02443                 : (UChar* )((void* )mem_end_stk[mem]));
02444          n = pend - pstart;
02445          DATA_ENSURE(n);
02446          sprev = s;
02447          swork = s;
02448          STRING_CMP_VALUE_IC(ambig_flag, pstart, &swork, n, is_fail);
02449          if (is_fail) continue;
02450          s = swork;
02451          while (sprev + (len = enc_len(encode, sprev)) < s)
02452            sprev += len;
02453 
02454          p += (SIZE_MEMNUM * (tlen - i - 1));
02455          break; /* success */
02456        }
02457        if (i == tlen) goto fail;
02458        STAT_OP_OUT;
02459        continue;
02460       }
02461       break;
02462 
02463 #ifdef USE_BACKREF_AT_LEVEL
02464     case OP_BACKREF_AT_LEVEL:
02465       {
02466        int len;
02467        OnigOptionType ic;
02468        LengthType level;
02469 
02470        GET_OPTION_INC(ic,    p);
02471        GET_LENGTH_INC(level, p);
02472        GET_LENGTH_INC(tlen,  p);
02473 
02474        sprev = s;
02475        if (backref_match_at_nested_level(reg, stk, stk_base, ic, ambig_flag
02476                               , (int )level, (int )tlen, p, &s, end)) {
02477          while (sprev + (len = enc_len(encode, sprev)) < s)
02478            sprev += len;
02479 
02480          p += (SIZE_MEMNUM * tlen);
02481        }
02482        else
02483          goto fail;
02484 
02485        STAT_OP_OUT;
02486        continue;
02487       }
02488       
02489       break;
02490 #endif
02491     
02492     case OP_SET_OPTION_PUSH:  STAT_OP_IN(OP_SET_OPTION_PUSH);
02493       GET_OPTION_INC(option, p);
02494       STACK_PUSH_ALT(p, s, sprev);
02495       p += SIZE_OP_SET_OPTION + SIZE_OP_FAIL;
02496       STAT_OP_OUT;
02497       continue;
02498       break;
02499 
02500     case OP_SET_OPTION:  STAT_OP_IN(OP_SET_OPTION);
02501       GET_OPTION_INC(option, p);
02502       STAT_OP_OUT;
02503       continue;
02504       break;
02505 
02506     case OP_NULL_CHECK_START:  STAT_OP_IN(OP_NULL_CHECK_START);
02507       GET_MEMNUM_INC(mem, p);    /* mem: null check id */
02508       STACK_PUSH_NULL_CHECK_START(mem, s);
02509       STAT_OP_OUT;
02510       continue;
02511       break;
02512 
02513     case OP_NULL_CHECK_END:  STAT_OP_IN(OP_NULL_CHECK_END);
02514       {
02515        int isnull;
02516 
02517        GET_MEMNUM_INC(mem, p); /* mem: null check id */
02518        STACK_NULL_CHECK(isnull, mem, s);
02519        if (isnull) {
02520 #ifdef ONIG_DEBUG_MATCH
02521          fprintf(stderr, "NULL_CHECK_END: skip  id:%d, s:%d\n",
02522                 (int )mem, (int )s);
02523 #endif
02524        null_check_found:
02525          /* empty loop founded, skip next instruction */
02526          switch (*p++) {
02527          case OP_JUMP:
02528          case OP_PUSH:
02529            p += SIZE_RELADDR;
02530            break;
02531          case OP_REPEAT_INC:
02532          case OP_REPEAT_INC_NG:
02533          case OP_REPEAT_INC_SG:
02534          case OP_REPEAT_INC_NG_SG:
02535            p += SIZE_MEMNUM;
02536            break;
02537          default:
02538            goto unexpected_bytecode_error;
02539            break;
02540          }
02541        }
02542       }
02543       STAT_OP_OUT;
02544       continue;
02545       break;
02546 
02547 #ifdef USE_INFINITE_REPEAT_MONOMANIAC_MEM_STATUS_CHECK
02548     case OP_NULL_CHECK_END_MEMST:  STAT_OP_IN(OP_NULL_CHECK_END_MEMST);
02549       {
02550        int isnull;
02551 
02552        GET_MEMNUM_INC(mem, p); /* mem: null check id */
02553        STACK_NULL_CHECK_MEMST(isnull, mem, s, reg);
02554        if (isnull) {
02555 #ifdef ONIG_DEBUG_MATCH
02556          fprintf(stderr, "NULL_CHECK_END_MEMST: skip  id:%d, s:%d\n",
02557                 (int )mem, (int )s);
02558 #endif
02559          if (isnull == -1) goto fail;
02560          goto        null_check_found;
02561        }
02562       }
02563       STAT_OP_OUT;
02564       continue;
02565       break;
02566 #endif
02567 
02568 #ifdef USE_SUBEXP_CALL
02569     case OP_NULL_CHECK_END_MEMST_PUSH:
02570       STAT_OP_IN(OP_NULL_CHECK_END_MEMST_PUSH);
02571       {
02572        int isnull;
02573 
02574        GET_MEMNUM_INC(mem, p); /* mem: null check id */
02575 #ifdef USE_INFINITE_REPEAT_MONOMANIAC_MEM_STATUS_CHECK
02576        STACK_NULL_CHECK_MEMST_REC(isnull, mem, s, reg);
02577 #else
02578        STACK_NULL_CHECK_REC(isnull, mem, s);
02579 #endif
02580        if (isnull) {
02581 #ifdef ONIG_DEBUG_MATCH
02582          fprintf(stderr, "NULL_CHECK_END_MEMST_PUSH: skip  id:%d, s:%d\n",
02583                 (int )mem, (int )s);
02584 #endif
02585          if (isnull == -1) goto fail;
02586          goto        null_check_found;
02587        }
02588        else {
02589          STACK_PUSH_NULL_CHECK_END(mem);
02590        }
02591       }
02592       STAT_OP_OUT;
02593       continue;
02594       break;
02595 #endif
02596 
02597     case OP_JUMP:  STAT_OP_IN(OP_JUMP);
02598       GET_RELADDR_INC(addr, p);
02599       p += addr;
02600       STAT_OP_OUT;
02601       CHECK_INTERRUPT_IN_MATCH_AT;
02602       continue;
02603       break;
02604 
02605     case OP_PUSH:  STAT_OP_IN(OP_PUSH);
02606       GET_RELADDR_INC(addr, p);
02607       STACK_PUSH_ALT(p + addr, s, sprev);
02608       STAT_OP_OUT;
02609       continue;
02610       break;
02611 
02612 #ifdef USE_COMBINATION_EXPLOSION_CHECK
02613     case OP_STATE_CHECK_PUSH:  STAT_OP_IN(OP_STATE_CHECK_PUSH);
02614       GET_STATE_CHECK_NUM_INC(mem, p);
02615       STATE_CHECK_VAL(scv, mem);
02616       if (scv) goto fail;
02617 
02618       GET_RELADDR_INC(addr, p);
02619       STACK_PUSH_ALT_WITH_STATE_CHECK(p + addr, s, sprev, mem);
02620       STAT_OP_OUT;
02621       continue;
02622       break;
02623 
02624     case OP_STATE_CHECK_PUSH_OR_JUMP:  STAT_OP_IN(OP_STATE_CHECK_PUSH_OR_JUMP);
02625       GET_STATE_CHECK_NUM_INC(mem, p);
02626       GET_RELADDR_INC(addr, p);
02627       STATE_CHECK_VAL(scv, mem);
02628       if (scv) {
02629        p += addr;
02630       }
02631       else {
02632        STACK_PUSH_ALT_WITH_STATE_CHECK(p + addr, s, sprev, mem);
02633       }
02634       STAT_OP_OUT;
02635       continue;
02636       break;
02637 
02638     case OP_STATE_CHECK:  STAT_OP_IN(OP_STATE_CHECK);
02639       GET_STATE_CHECK_NUM_INC(mem, p);
02640       STATE_CHECK_VAL(scv, mem);
02641       if (scv) goto fail;
02642 
02643       STACK_PUSH_STATE_CHECK(s, mem);
02644       STAT_OP_OUT;
02645       continue;
02646       break;
02647 #endif /* USE_COMBINATION_EXPLOSION_CHECK */
02648 
02649     case OP_POP:  STAT_OP_IN(OP_POP);
02650       STACK_POP_ONE;
02651       STAT_OP_OUT;
02652       continue;
02653       break;
02654 
02655     case OP_PUSH_OR_JUMP_EXACT1:  STAT_OP_IN(OP_PUSH_OR_JUMP_EXACT1);
02656       GET_RELADDR_INC(addr, p);
02657       if (*p == *s && DATA_ENSURE_CHECK(1)) {
02658        p++;
02659        STACK_PUSH_ALT(p + addr, s, sprev);
02660        STAT_OP_OUT;
02661        continue;
02662       }
02663       p += (addr + 1);
02664       STAT_OP_OUT;
02665       continue;
02666       break;
02667 
02668     case OP_PUSH_IF_PEEK_NEXT:  STAT_OP_IN(OP_PUSH_IF_PEEK_NEXT);
02669       GET_RELADDR_INC(addr, p);
02670       if (*p == *s) {
02671        p++;
02672        STACK_PUSH_ALT(p + addr, s, sprev);
02673        STAT_OP_OUT;
02674        continue;
02675       }
02676       p++;
02677       STAT_OP_OUT;
02678       continue;
02679       break;
02680 
02681     case OP_REPEAT:  STAT_OP_IN(OP_REPEAT);
02682       {
02683        GET_MEMNUM_INC(mem, p);    /* mem: OP_REPEAT ID */
02684        GET_RELADDR_INC(addr, p);
02685 
02686        STACK_ENSURE(1);
02687        repeat_stk[mem] = GET_STACK_INDEX(stk);
02688        STACK_PUSH_REPEAT(mem, p);
02689 
02690        if (reg->repeat_range[mem].lower == 0) {
02691          STACK_PUSH_ALT(p + addr, s, sprev);
02692        }
02693       }
02694       STAT_OP_OUT;
02695       continue;
02696       break;
02697 
02698     case OP_REPEAT_NG:  STAT_OP_IN(OP_REPEAT_NG);
02699       {
02700        GET_MEMNUM_INC(mem, p);    /* mem: OP_REPEAT ID */
02701        GET_RELADDR_INC(addr, p);
02702 
02703        STACK_ENSURE(1);
02704        repeat_stk[mem] = GET_STACK_INDEX(stk);
02705        STACK_PUSH_REPEAT(mem, p);
02706 
02707        if (reg->repeat_range[mem].lower == 0) {
02708          STACK_PUSH_ALT(p, s, sprev);
02709          p += addr;
02710        }
02711       }
02712       STAT_OP_OUT;
02713       continue;
02714       break;
02715 
02716     case OP_REPEAT_INC:  STAT_OP_IN(OP_REPEAT_INC);
02717       GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
02718       si = repeat_stk[mem];
02719       stkp = STACK_AT(si);
02720 
02721     repeat_inc:
02722       stkp->u.repeat.count++;
02723       if (stkp->u.repeat.count >= reg->repeat_range[mem].upper) {
02724         /* end of repeat. Nothing to do. */
02725       }
02726       else if (stkp->u.repeat.count >= reg->repeat_range[mem].lower) {
02727         STACK_PUSH_ALT(p, s, sprev);
02728         p = STACK_AT(si)->u.repeat.pcode; /* Don't use stkp after PUSH. */
02729       }
02730       else {
02731         p = stkp->u.repeat.pcode;
02732       }
02733       STACK_PUSH_REPEAT_INC(si);
02734       STAT_OP_OUT;
02735       CHECK_INTERRUPT_IN_MATCH_AT;
02736       continue;
02737       break;
02738 
02739     case OP_REPEAT_INC_SG:  STAT_OP_IN(OP_REPEAT_INC_SG);
02740       GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
02741       STACK_GET_REPEAT(mem, stkp);
02742       si = GET_STACK_INDEX(stkp);
02743       goto repeat_inc;
02744       break;
02745 
02746     case OP_REPEAT_INC_NG:  STAT_OP_IN(OP_REPEAT_INC_NG);
02747       GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
02748       si = repeat_stk[mem];
02749       stkp = STACK_AT(si);
02750 
02751     repeat_inc_ng:
02752       stkp->u.repeat.count++;
02753       if (stkp->u.repeat.count < reg->repeat_range[mem].upper) {
02754         if (stkp->u.repeat.count >= reg->repeat_range[mem].lower) {
02755           UChar* pcode = stkp->u.repeat.pcode;
02756 
02757           STACK_PUSH_REPEAT_INC(si);
02758           STACK_PUSH_ALT(pcode, s, sprev);
02759         }
02760         else {
02761           p = stkp->u.repeat.pcode;
02762           STACK_PUSH_REPEAT_INC(si);
02763         }
02764       }
02765       else if (stkp->u.repeat.count == reg->repeat_range[mem].upper) {
02766         STACK_PUSH_REPEAT_INC(si);
02767       }
02768       STAT_OP_OUT;
02769       CHECK_INTERRUPT_IN_MATCH_AT;
02770       continue;
02771       break;
02772 
02773     case OP_REPEAT_INC_NG_SG:  STAT_OP_IN(OP_REPEAT_INC_NG_SG);
02774       GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
02775       STACK_GET_REPEAT(mem, stkp);
02776       si = GET_STACK_INDEX(stkp);
02777       goto repeat_inc_ng;
02778       break;
02779 
02780     case OP_PUSH_POS:  STAT_OP_IN(OP_PUSH_POS);
02781       STACK_PUSH_POS(s, sprev);
02782       STAT_OP_OUT;
02783       continue;
02784       break;
02785 
02786     case OP_POP_POS:  STAT_OP_IN(OP_POP_POS);
02787       {
02788        STACK_POS_END(stkp);
02789        s     = stkp->u.state.pstr;
02790        sprev = stkp->u.state.pstr_prev;
02791       }
02792       STAT_OP_OUT;
02793       continue;
02794       break;
02795 
02796     case OP_PUSH_POS_NOT:  STAT_OP_IN(OP_PUSH_POS_NOT);
02797       GET_RELADDR_INC(addr, p);
02798       STACK_PUSH_POS_NOT(p + addr, s, sprev);
02799       STAT_OP_OUT;
02800       continue;
02801       break;
02802 
02803     case OP_FAIL_POS:  STAT_OP_IN(OP_FAIL_POS);
02804       STACK_POP_TIL_POS_NOT;
02805       goto fail;
02806       break;
02807 
02808     case OP_PUSH_STOP_BT:  STAT_OP_IN(OP_PUSH_STOP_BT);
02809       STACK_PUSH_STOP_BT;
02810       STAT_OP_OUT;
02811       continue;
02812       break;
02813 
02814     case OP_POP_STOP_BT:  STAT_OP_IN(OP_POP_STOP_BT);
02815       STACK_STOP_BT_END;
02816       STAT_OP_OUT;
02817       continue;
02818       break;
02819 
02820     case OP_LOOK_BEHIND:  STAT_OP_IN(OP_LOOK_BEHIND);
02821       GET_LENGTH_INC(tlen, p);
02822       s = (UChar* )ONIGENC_STEP_BACK(encode, str, s, (int )tlen);
02823       if (IS_NULL(s)) goto fail;
02824       sprev = (UChar* )onigenc_get_prev_char_head(encode, str, s);
02825       STAT_OP_OUT;
02826       continue;
02827       break;
02828 
02829     case OP_PUSH_LOOK_BEHIND_NOT:  STAT_OP_IN(OP_PUSH_LOOK_BEHIND_NOT);
02830       GET_RELADDR_INC(addr, p);
02831       GET_LENGTH_INC(tlen, p);
02832       q = (UChar* )ONIGENC_STEP_BACK(encode, str, s, (int )tlen);
02833       if (IS_NULL(q)) {
02834        /* too short case -> success. ex. /(?<!XXX)a/.match("a")
02835           If you want to change to fail, replace following line. */
02836        p += addr;
02837        /* goto fail; */
02838       }
02839       else {
02840        STACK_PUSH_LOOK_BEHIND_NOT(p + addr, s, sprev);
02841        s = q;
02842        sprev = (UChar* )onigenc_get_prev_char_head(encode, str, s);
02843       }
02844       STAT_OP_OUT;
02845       continue;
02846       break;
02847 
02848     case OP_FAIL_LOOK_BEHIND_NOT:  STAT_OP_IN(OP_FAIL_LOOK_BEHIND_NOT);
02849       STACK_POP_TIL_LOOK_BEHIND_NOT;
02850       goto fail;
02851       break;
02852 
02853 #ifdef USE_SUBEXP_CALL
02854     case OP_CALL:  STAT_OP_IN(OP_CALL);
02855       GET_ABSADDR_INC(addr, p);
02856       STACK_PUSH_CALL_FRAME(p);
02857       p = reg->p + addr;
02858       STAT_OP_OUT;
02859       continue;
02860       break;
02861 
02862     case OP_RETURN:  STAT_OP_IN(OP_RETURN);
02863       STACK_RETURN(p);
02864       STACK_PUSH_RETURN;
02865       STAT_OP_OUT;
02866       continue;
02867       break;
02868 #endif
02869 
02870     case OP_FINISH:
02871       goto finish;
02872       break;
02873 
02874     fail:
02875       STAT_OP_OUT;
02876       /* fall */
02877     case OP_FAIL:  STAT_OP_IN(OP_FAIL);
02878       STACK_POP;
02879       p     = stk->u.state.pcode;
02880       s     = stk->u.state.pstr;
02881       sprev = stk->u.state.pstr_prev;
02882 
02883 #ifdef USE_COMBINATION_EXPLOSION_CHECK
02884       if (stk->u.state.state_check != 0) {
02885         stk->type = STK_STATE_CHECK_MARK;
02886         stk++;
02887       }
02888 #endif
02889 
02890       STAT_OP_OUT;
02891       continue;
02892       break;
02893 
02894     default:
02895       goto bytecode_error;
02896 
02897     } /* end of switch */
02898     sprev = sbegin;
02899   } /* end of while(1) */
02900 
02901  finish:
02902   STACK_SAVE;
02903   return best_len;
02904 
02905 #ifdef ONIG_DEBUG
02906  stack_error:
02907   STACK_SAVE;
02908   return ONIGERR_STACK_BUG;
02909 #endif
02910 
02911  bytecode_error:
02912   STACK_SAVE;
02913   return ONIGERR_UNDEFINED_BYTECODE;
02914 
02915  unexpected_bytecode_error:
02916   STACK_SAVE;
02917   return ONIGERR_UNEXPECTED_BYTECODE;
02918 }
02919 
02920 
02921 static UChar*
02922 slow_search(OnigEncoding enc, UChar* target, UChar* target_end,
02923            const UChar* text, const UChar* text_end, UChar* text_range)
02924 {
02925   UChar *t, *p, *s, *end;
02926 
02927   end = (UChar* )text_end;
02928   end -= target_end - target - 1;
02929   if (end > text_range)
02930     end = text_range;
02931 
02932   s = (UChar* )text;
02933 
02934   while (s < end) {
02935     if (*s == *target) {
02936       p = s + 1;
02937       t = target + 1;
02938       while (t < target_end) {
02939        if (*t != *p++)
02940          break;
02941        t++;
02942       }
02943       if (t == target_end)
02944        return s;
02945     }
02946     s += enc_len(enc, s);
02947   }
02948 
02949   return (UChar* )NULL;
02950 }
02951 
02952 static int
02953 str_lower_case_match(OnigEncoding enc, int ambig_flag,
02954                      const UChar* t, const UChar* tend,
02955                    const UChar* p, const UChar* end)
02956 {
02957   int lowlen;
02958   UChar *q, lowbuf[ONIGENC_MBC_NORMALIZE_MAXLEN];
02959   const UChar* tsave;
02960   const UChar* psave;
02961 
02962   tsave = t;
02963   psave = p;
02964 
02965   while (t < tend) {
02966     lowlen = ONIGENC_MBC_TO_NORMALIZE(enc, ambig_flag, &p, end, lowbuf);
02967     q = lowbuf;
02968     while (lowlen > 0) {
02969       if (*t++ != *q++) {
02970        return 0;
02971       }
02972       lowlen--;
02973     }
02974   }
02975 
02976   return 1;
02977 }
02978 
02979 static UChar*
02980 slow_search_ic(OnigEncoding enc, int ambig_flag,
02981               UChar* target, UChar* target_end,
02982               const UChar* text, const UChar* text_end, UChar* text_range)
02983 {
02984   UChar *s, *end;
02985 
02986   end = (UChar* )text_end;
02987   end -= target_end - target - 1;
02988   if (end > text_range)
02989     end = text_range;
02990 
02991   s = (UChar* )text;
02992 
02993   while (s < end) {
02994     if (str_lower_case_match(enc, ambig_flag, target, target_end, s, text_end))
02995       return s;
02996 
02997     s += enc_len(enc, s);
02998   }
02999 
03000   return (UChar* )NULL;
03001 }
03002 
03003 static UChar*
03004 slow_search_backward(OnigEncoding enc, UChar* target, UChar* target_end,
03005                    const UChar* text, const UChar* adjust_text,
03006                    const UChar* text_end, const UChar* text_start)
03007 {
03008   UChar *t, *p, *s;
03009 
03010   s = (UChar* )text_end;
03011   s -= (target_end - target);
03012   if (s > text_start)
03013     s = (UChar* )text_start;
03014   else
03015     s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(enc, adjust_text, s);
03016 
03017   while (s >= text) {
03018     if (*s == *target) {
03019       p = s + 1;
03020       t = target + 1;
03021       while (t < target_end) {
03022        if (*t != *p++)
03023          break;
03024        t++;
03025       }
03026       if (t == target_end)
03027        return s;
03028     }
03029     s = (UChar* )onigenc_get_prev_char_head(enc, adjust_text, s);
03030   }
03031 
03032   return (UChar* )NULL;
03033 }
03034 
03035 static UChar*
03036 slow_search_backward_ic(OnigEncoding enc, int ambig_flag,
03037                      UChar* target, UChar* target_end,
03038                      const UChar* text, const UChar* adjust_text,
03039                      const UChar* text_end, const UChar* text_start)
03040 {
03041   UChar *s;
03042 
03043   s = (UChar* )text_end;
03044   s -= (target_end - target);
03045   if (s > text_start)
03046     s = (UChar* )text_start;
03047   else
03048     s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(enc, adjust_text, s);
03049 
03050   while (s >= text) {
03051     if (str_lower_case_match(enc, ambig_flag,
03052                              target, target_end, s, text_end))
03053       return s;
03054 
03055     s = (UChar* )onigenc_get_prev_char_head(enc, adjust_text, s);
03056   }
03057 
03058   return (UChar* )NULL;
03059 }
03060 
03061 static UChar*
03062 bm_search_notrev(regex_t* reg, const UChar* target, const UChar* target_end,
03063                const UChar* text, const UChar* text_end,
03064                const UChar* text_range)
03065 {
03066   const UChar *s, *se, *t, *p, *end;
03067   const UChar *tail;
03068   int skip, tlen1;
03069 
03070 #ifdef ONIG_DEBUG_SEARCH
03071   fprintf(stderr, "bm_search_notrev: text: %d, text_end: %d, text_range: %d\n",
03072          (int )text, (int )text_end, (int )text_range);
03073 #endif
03074 
03075   tail = target_end - 1;
03076   tlen1 = tail - target;
03077   end = text_range;
03078   if (end + tlen1 > text_end)
03079     end = text_end - tlen1;
03080 
03081   s = text;
03082 
03083   if (IS_NULL(reg->int_map)) {
03084     while (s < end) {
03085       p = se = s + tlen1;
03086       t = tail;
03087       while (t >= target && *p == *t) {
03088         p--; t--;
03089       }
03090       if (t < target) return (UChar* )s;
03091 
03092       skip = reg->map[*se];
03093       t = s;
03094       do {
03095         s += enc_len(reg->enc, s);
03096       } while ((s - t) < skip && s < end);
03097     }
03098   }
03099   else {
03100     while (s < end) {
03101       p = se = s + tlen1;
03102       t = tail;
03103       while (t >= target && *p == *t) {
03104         p--; t--;
03105       }
03106       if (t < target) return (UChar* )s;
03107 
03108       skip = reg->int_map[*se];
03109       t = s;
03110       do {
03111         s += enc_len(reg->enc, s);
03112       } while ((s - t) < skip && s < end);
03113     }
03114   }
03115 
03116   return (UChar* )NULL;
03117 }
03118 
03119 static UChar*
03120 bm_search(regex_t* reg, const UChar* target, const UChar* target_end,
03121          const UChar* text, const UChar* text_end, const UChar* text_range)
03122 {
03123   const UChar *s, *t, *p, *end;
03124   const UChar *tail;
03125 
03126   end = text_range + (target_end - target) - 1;
03127   if (end > text_end)
03128     end = text_end;
03129 
03130   tail = target_end - 1;
03131   s = text + (target_end - target) - 1;
03132   if (IS_NULL(reg->int_map)) {
03133     while (s < end) {
03134       p = s;
03135       t = tail;
03136       while (t >= target && *p == *t) {
03137        p--; t--;
03138       }
03139       if (t < target) return (UChar* )(p + 1);
03140       s += reg->map[*s];
03141     }
03142   }
03143   else { /* see int_map[] */
03144     while (s < end) {
03145       p = s;
03146       t = tail;
03147       while (t >= target && *p == *t) {
03148        p--; t--;
03149       }
03150       if (t < target) return (UChar* )(p + 1);
03151       s += reg->int_map[*s];
03152     }
03153   }
03154   return (UChar* )NULL;
03155 }
03156 
03157 static int
03158 set_bm_backward_skip(UChar* s, UChar* end, OnigEncoding enc, int** skip)
03159                    
03160 {
03161   int i, len;
03162 
03163   if (IS_NULL(*skip)) {
03164     *skip = (int* )xmalloc(sizeof(int) * ONIG_CHAR_TABLE_SIZE);
03165     if (IS_NULL(*skip)) return ONIGERR_MEMORY;
03166   }
03167 
03168   len = end - s;
03169   for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++)
03170     (*skip)[i] = len;
03171 
03172   for (i = len - 1; i > 0; i--)
03173     (*skip)[s[i]] = i;
03174 
03175   return 0;
03176 }
03177 
03178 static UChar*
03179 bm_search_backward(regex_t* reg, const UChar* target, const UChar* target_end,
03180                  const UChar* text, const UChar* adjust_text,
03181                  const UChar* text_end, const UChar* text_start)
03182 {
03183   const UChar *s, *t, *p;
03184 
03185   s = text_end - (target_end - target);
03186   if (text_start < s)
03187     s = text_start;
03188   else
03189     s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, adjust_text, s);
03190 
03191   while (s >= text) {
03192     p = s;
03193     t = target;
03194     while (t < target_end && *p == *t) {
03195       p++; t++;
03196     }
03197     if (t == target_end)
03198       return (UChar* )s;
03199 
03200     s -= reg->int_map_backward[*s];
03201     s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, adjust_text, s);
03202   }
03203 
03204   return (UChar* )NULL;
03205 }
03206 
03207 static UChar*
03208 map_search(OnigEncoding enc, UChar map[],
03209           const UChar* text, const UChar* text_range)
03210 {
03211   const UChar *s = text;
03212 
03213   while (s < text_range) {
03214     if (map[*s]) return (UChar* )s;
03215 
03216     s += enc_len(enc, s);
03217   }
03218   return (UChar* )NULL;
03219 }
03220 
03221 static UChar*
03222 map_search_backward(OnigEncoding enc, UChar map[],
03223                   const UChar* text, const UChar* adjust_text,
03224                   const UChar* text_start)
03225 {
03226   const UChar *s = text_start;
03227 
03228   while (s >= text) {
03229     if (map[*s]) return (UChar* )s;
03230 
03231     s = onigenc_get_prev_char_head(enc, adjust_text, s);
03232   }
03233   return (UChar* )NULL;
03234 }
03235 
03236 extern int
03237 onig_match(regex_t* reg, const UChar* str, const UChar* end, const UChar* at, OnigRegion* region,
03238            OnigOptionType option)
03239 {
03240   int r;
03241   UChar *prev;
03242   MatchArg msa;
03243 
03244 #if defined(USE_RECOMPILE_API) && defined(USE_MULTI_THREAD_SYSTEM)
03245  start:
03246   THREAD_ATOMIC_START;
03247   if (ONIG_STATE(reg) >= ONIG_STATE_NORMAL) {
03248     ONIG_STATE_INC(reg);
03249     if (IS_NOT_NULL(reg->chain) && ONIG_STATE(reg) == ONIG_STATE_NORMAL) {
03250       onig_chain_reduce(reg);
03251       ONIG_STATE_INC(reg);
03252     }
03253   }
03254   else {
03255     int n;
03256 
03257     THREAD_ATOMIC_END;
03258     n = 0;
03259     while (ONIG_STATE(reg) < ONIG_STATE_NORMAL) {
03260       if (++n > THREAD_PASS_LIMIT_COUNT)
03261        return ONIGERR_OVER_THREAD_PASS_LIMIT_COUNT;
03262       THREAD_PASS;
03263     }
03264     goto start;
03265   }
03266   THREAD_ATOMIC_END;
03267 #endif /* USE_RECOMPILE_API && USE_MULTI_THREAD_SYSTEM */
03268 
03269   MATCH_ARG_INIT(msa, option, region, at);
03270 #ifdef USE_COMBINATION_EXPLOSION_CHECK
03271   {
03272     int offset = at - str;
03273     STATE_CHECK_BUFF_INIT(msa, end - str, offset, reg->num_comb_exp_check);
03274   }
03275 #endif
03276 
03277   if (region
03278 #ifdef USE_POSIX_REGION_OPTION
03279       && !IS_POSIX_REGION(option)
03280 #endif
03281       ) {
03282     r = onig_region_resize_clear(region, reg->num_mem + 1);
03283   }
03284   else
03285     r = 0;
03286 
03287   if (r == 0) {
03288     prev = (UChar* )onigenc_get_prev_char_head(reg->enc, str, at);
03289     r = match_at(reg, str, end, at, prev, &msa);
03290   }
03291 
03292   MATCH_ARG_FREE(msa);
03293   ONIG_STATE_DEC_THREAD(reg);
03294   return r;
03295 }
03296 
03297 static int
03298 forward_search_range(regex_t* reg, const UChar* str, const UChar* end, UChar* s,
03299                    UChar* range, UChar** low, UChar** high, UChar** low_prev)
03300 {
03301   UChar *p, *pprev = (UChar* )NULL;
03302 
03303 #ifdef ONIG_DEBUG_SEARCH
03304   fprintf(stderr, "forward_search_range: str: %d, end: %d, s: %d, range: %d\n",
03305          (int )str, (int )end, (int )s, (int )range);
03306 #endif
03307 
03308   p = s;
03309   if (reg->dmin > 0) {
03310     if (ONIGENC_IS_SINGLEBYTE(reg->enc)) {
03311       p += reg->dmin;
03312     }
03313     else {
03314       UChar *q = p + reg->dmin;
03315       while (p < q) p += enc_len(reg->enc, p);
03316     }
03317   }
03318 
03319  retry:
03320   switch (reg->optimize) {
03321   case ONIG_OPTIMIZE_EXACT:
03322     p = slow_search(reg->enc, reg->exact, reg->exact_end, p, end, range);
03323     break;
03324   case ONIG_OPTIMIZE_EXACT_IC:
03325     p = slow_search_ic(reg->enc, reg->ambig_flag,
03326                        reg->exact, reg->exact_end, p, end, range);
03327     break;
03328 
03329   case ONIG_OPTIMIZE_EXACT_BM:
03330     p = bm_search(reg, reg->exact, reg->exact_end, p, end, range);
03331     break;
03332 
03333   case ONIG_OPTIMIZE_EXACT_BM_NOT_REV:
03334     p = bm_search_notrev(reg, reg->exact, reg->exact_end, p, end, range);
03335     break;
03336 
03337   case ONIG_OPTIMIZE_MAP:
03338     p = map_search(reg->enc, reg->map, p, range);
03339     break;
03340   }
03341 
03342   if (p && p < range) {
03343     if (p - reg->dmin < s) {
03344     retry_gate:
03345       pprev = p;
03346       p += enc_len(reg->enc, p);
03347       goto retry;
03348     }
03349 
03350     if (reg->sub_anchor) {
03351       UChar* prev;
03352 
03353       switch (reg->sub_anchor) {
03354       case ANCHOR_BEGIN_LINE:
03355        if (!ON_STR_BEGIN(p)) {
03356          prev = onigenc_get_prev_char_head(reg->enc,
03357                                        (pprev ? pprev : str), p);
03358          if (!ONIGENC_IS_MBC_NEWLINE(reg->enc, prev, end))
03359            goto retry_gate;
03360        }
03361        break;
03362 
03363       case ANCHOR_END_LINE:
03364        if (ON_STR_END(p)) {
03365          prev = (UChar* )onigenc_get_prev_char_head(reg->enc,
03366                                        (pprev ? pprev : str), p);
03367          if (prev && ONIGENC_IS_MBC_NEWLINE(reg->enc, prev, end))
03368            goto retry_gate;
03369        }
03370        else if (! ONIGENC_IS_MBC_NEWLINE(reg->enc, p, end)
03371 #ifdef USE_CRNL_AS_LINE_TERMINATOR
03372               && ! ONIGENC_IS_MBC_CRNL(reg->enc, p, end)
03373 #endif
03374                 )
03375          goto retry_gate;
03376        break;
03377       }
03378     }
03379 
03380     if (reg->dmax == 0) {
03381       *low = p;
03382       if (low_prev) {
03383        if (*low > s)
03384          *low_prev = onigenc_get_prev_char_head(reg->enc, s, p);
03385        else
03386          *low_prev = onigenc_get_prev_char_head(reg->enc,
03387                                            (pprev ? pprev : str), p);
03388       }
03389     }
03390     else {
03391       if (reg->dmax != ONIG_INFINITE_DISTANCE) {
03392        *low = p - reg->dmax;
03393        if (*low > s) {
03394          *low = onigenc_get_right_adjust_char_head_with_prev(reg->enc, s,
03395                                                        *low, (const UChar** )low_prev);
03396          if (low_prev && IS_NULL(*low_prev))
03397            *low_prev = onigenc_get_prev_char_head(reg->enc,
03398                                              (pprev ? pprev : s), *low);
03399        }
03400        else {
03401          if (low_prev)
03402            *low_prev = onigenc_get_prev_char_head(reg->enc,
03403                                           (pprev ? pprev : str), *low);
03404        }
03405       }
03406     }
03407     /* no needs to adjust *high, *high is used as range check only */
03408     *high = p - reg->dmin;
03409 
03410 #ifdef ONIG_DEBUG_SEARCH
03411     fprintf(stderr,
03412     "forward_search_range success: low: %d, high: %d, dmin: %d, dmax: %d\n",
03413            (int )(*low - str), (int )(*high - str), reg->dmin, reg->dmax);
03414 #endif
03415     return 1; /* success */
03416   }
03417 
03418   return 0; /* fail */
03419 }
03420 
03421 static int set_bm_backward_skip P_((UChar* s, UChar* end, OnigEncoding enc,
03422                                 int** skip));
03423 
03424 #define BM_BACKWARD_SEARCH_LENGTH_THRESHOLD   100
03425 
03426 static int
03427 backward_search_range(regex_t* reg, const UChar* str, const UChar* end,
03428                     UChar* s, const UChar* range, UChar* adjrange,
03429                     UChar** low, UChar** high)
03430 {
03431   int r;
03432   UChar *p;
03433 
03434   range += reg->dmin;
03435   p = s;
03436 
03437  retry:
03438   switch (reg->optimize) {
03439   case ONIG_OPTIMIZE_EXACT:
03440   exact_method:
03441     p = slow_search_backward(reg->enc, reg->exact, reg->exact_end,
03442                           range, adjrange, end, p);
03443     break;
03444 
03445   case ONIG_OPTIMIZE_EXACT_IC:
03446     p = slow_search_backward_ic(reg->enc, reg->ambig_flag,
03447                                 reg->exact, reg->exact_end,
03448                                 range, adjrange, end, p);
03449     break;
03450 
03451   case ONIG_OPTIMIZE_EXACT_BM:
03452   case ONIG_OPTIMIZE_EXACT_BM_NOT_REV:
03453     if (IS_NULL(reg->int_map_backward)) {
03454       if (s - range < BM_BACKWARD_SEARCH_LENGTH_THRESHOLD)
03455        goto exact_method;
03456 
03457       r = set_bm_backward_skip(reg->exact, reg->exact_end, reg->enc,
03458                             &(reg->int_map_backward));
03459       if (r) return r;
03460     }
03461     p = bm_search_backward(reg, reg->exact, reg->exact_end, range, adjrange,
03462                         end, p);
03463     break;
03464 
03465   case ONIG_OPTIMIZE_MAP:
03466     p = map_search_backward(reg->enc, reg->map, range, adjrange, p);
03467     break;
03468   }
03469 
03470   if (p) {
03471     if (reg->sub_anchor) {
03472       UChar* prev;
03473 
03474       switch (reg->sub_anchor) {
03475       case ANCHOR_BEGIN_LINE:
03476        if (!ON_STR_BEGIN(p)) {
03477          prev = onigenc_get_prev_char_head(reg->enc, str, p);
03478          if (!ONIGENC_IS_MBC_NEWLINE(reg->enc, prev, end)) {
03479            p = prev;
03480            goto retry;
03481          }
03482        }
03483        break;
03484 
03485       case ANCHOR_END_LINE:
03486        if (ON_STR_END(p)) {
03487          prev = onigenc_get_prev_char_head(reg->enc, adjrange, p);
03488          if (IS_NULL(prev)) goto fail;
03489          if (ONIGENC_IS_MBC_NEWLINE(reg->enc, prev, end)) {
03490            p = prev;
03491            goto retry;
03492          }
03493        }
03494        else if (! ONIGENC_IS_MBC_NEWLINE(reg->enc, p, end)
03495 #ifdef USE_CRNL_AS_LINE_TERMINATOR
03496               && ! ONIGENC_IS_MBC_CRNL(reg->enc, p, end)
03497 #endif
03498                 ) {
03499          p = onigenc_get_prev_char_head(reg->enc, adjrange, p);
03500          if (IS_NULL(p)) goto fail;
03501          goto retry;
03502        }
03503        break;
03504       }
03505     }
03506 
03507     /* no needs to adjust *high, *high is used as range check only */
03508     if (reg->dmax != ONIG_INFINITE_DISTANCE) {
03509       *low  = p - reg->dmax;
03510       *high = p - reg->dmin;
03511       *high = onigenc_get_right_adjust_char_head(reg->enc, adjrange, *high);
03512     }
03513 
03514 #ifdef ONIG_DEBUG_SEARCH
03515     fprintf(stderr, "backward_search_range: low: %d, high: %d\n",
03516            (int )(*low - str), (int )(*high - str));
03517 #endif
03518     return 1; /* success */
03519   }
03520 
03521  fail:
03522 #ifdef ONIG_DEBUG_SEARCH
03523   fprintf(stderr, "backward_search_range: fail.\n");
03524 #endif
03525   return 0; /* fail */
03526 }
03527 
03528 
03529 extern int
03530 onig_search(regex_t* reg, const UChar* str, const UChar* end,
03531            const UChar* start, const UChar* range, OnigRegion* region, OnigOptionType option)
03532 {
03533   int r;
03534   UChar *s, *prev;
03535   MatchArg msa;
03536   const UChar *orig_start = start;
03537 
03538 #if defined(USE_RECOMPILE_API) && defined(USE_MULTI_THREAD_SYSTEM)
03539  start:
03540   THREAD_ATOMIC_START;
03541   if (ONIG_STATE(reg) >= ONIG_STATE_NORMAL) {
03542     ONIG_STATE_INC(reg);
03543     if (IS_NOT_NULL(reg->chain) && ONIG_STATE(reg) == ONIG_STATE_NORMAL) {
03544       onig_chain_reduce(reg);
03545       ONIG_STATE_INC(reg);
03546     }
03547   }
03548   else {
03549     int n;
03550 
03551     THREAD_ATOMIC_END;
03552     n = 0;
03553     while (ONIG_STATE(reg) < ONIG_STATE_NORMAL) {
03554       if (++n > THREAD_PASS_LIMIT_COUNT)
03555        return ONIGERR_OVER_THREAD_PASS_LIMIT_COUNT;
03556       THREAD_PASS;
03557     }
03558     goto start;
03559   }
03560   THREAD_ATOMIC_END;
03561 #endif /* USE_RECOMPILE_API && USE_MULTI_THREAD_SYSTEM */
03562 
03563 #ifdef ONIG_DEBUG_SEARCH
03564   fprintf(stderr,
03565      "onig_search (entry point): str: %d, end: %d, start: %d, range: %d\n",
03566      (int )str, (int )(end - str), (int )(start - str), (int )(range - str));
03567 #endif
03568 
03569   if (region
03570 #ifdef USE_POSIX_REGION_OPTION
03571       && !IS_POSIX_REGION(option)
03572 #endif
03573       ) {
03574     r = onig_region_resize_clear(region, reg->num_mem + 1);
03575     if (r) goto finish_no_msa;
03576   }
03577 
03578   if (start > end || start < str) goto mismatch_no_msa;
03579 
03580 #ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
03581 #define MATCH_AND_RETURN_CHECK \
03582   r = match_at(reg, str, end, s, prev, &msa);\
03583   if (r != ONIG_MISMATCH) {\
03584     if (r >= 0) {\
03585       if (! IS_FIND_LONGEST(reg->options)) {\
03586         goto match;\
03587       }\
03588     }\
03589     else goto finish; /* error */ \
03590   }
03591 #else
03592 #define MATCH_AND_RETURN_CHECK \
03593   r = match_at(reg, str, end, s, prev, &msa);\
03594   if (r != ONIG_MISMATCH) {\
03595     if (r >= 0) {\
03596       goto match;\
03597     }\
03598     else goto finish; /* error */ \
03599   }
03600 #endif
03601 
03602   /* anchor optimize: resume search range */
03603   if (reg->anchor != 0 && str < end) {
03604     UChar *min_semi_end, *max_semi_end;
03605 
03606     if (reg->anchor & ANCHOR_BEGIN_POSITION) {
03607       /* search start-position only */
03608     begin_position:
03609       if (range > start)
03610        range = start + 1;
03611       else
03612        range = start;
03613     }
03614     else if (reg->anchor & ANCHOR_BEGIN_BUF) {
03615       /* search str-position only */
03616       if (range > start) {
03617        if (start != str) goto mismatch_no_msa;
03618        range = str + 1;
03619       }
03620       else {
03621        if (range <= str) {
03622          start = str;
03623          range = str;
03624        }
03625        else
03626          goto mismatch_no_msa;
03627       }
03628     }
03629     else if (reg->anchor & ANCHOR_END_BUF) {
03630       min_semi_end = max_semi_end = (UChar* )end;
03631 
03632     end_buf:
03633       if ((OnigDistance )(max_semi_end - str) < reg->anchor_dmin)
03634        goto mismatch_no_msa;
03635 
03636       if (range > start) {
03637        if ((OnigDistance )(min_semi_end - start) > reg->anchor_dmax) {
03638          start = min_semi_end - reg->anchor_dmax;
03639          if (start < end)
03640            start = onigenc_get_right_adjust_char_head(reg->enc, str, start);
03641          else { /* match with empty at end */
03642            start = onigenc_get_prev_char_head(reg->enc, str, end);
03643          }
03644        }
03645        if ((OnigDistance )(max_semi_end - (range - 1)) < reg->anchor_dmin) {
03646          range = max_semi_end - reg->anchor_dmin + 1;
03647        }
03648 
03649        if (start >= range) goto mismatch_no_msa;
03650       }
03651       else {
03652        if ((OnigDistance )(min_semi_end - range) > reg->anchor_dmax) {
03653          range = min_semi_end - reg->anchor_dmax;
03654        }
03655        if ((OnigDistance )(max_semi_end - start) < reg->anchor_dmin) {
03656          start = max_semi_end - reg->anchor_dmin;
03657          start = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, str, start);
03658        }
03659        if (range > start) goto mismatch_no_msa;
03660       }
03661     }
03662     else if (reg->anchor & ANCHOR_SEMI_END_BUF) {
03663       UChar* pre_end = ONIGENC_STEP_BACK(reg->enc, str, end, 1);
03664 
03665       max_semi_end = (UChar* )end;
03666       if (ONIGENC_IS_MBC_NEWLINE(reg->enc, pre_end, end)) {
03667        min_semi_end = pre_end;
03668 
03669 #ifdef USE_CRNL_AS_LINE_TERMINATOR
03670        pre_end = ONIGENC_STEP_BACK(reg->enc, str, pre_end, 1);
03671        if (IS_NOT_NULL(pre_end) &&
03672            ONIGENC_IS_MBC_CRNL(reg->enc, pre_end, end)) {
03673          min_semi_end = pre_end;
03674        }
03675 #endif
03676        if (min_semi_end > str && start <= min_semi_end) {
03677          goto end_buf;
03678        }
03679       }
03680       else {
03681        min_semi_end = (UChar* )end;
03682        goto end_buf;
03683       }
03684     }
03685     else if ((reg->anchor & ANCHOR_ANYCHAR_STAR_ML)) {
03686       goto begin_position;
03687     }
03688   }
03689   else if (str == end) { /* empty string */
03690     static const UChar* address_for_empty_string = (UChar* )"";
03691 
03692 #ifdef ONIG_DEBUG_SEARCH
03693     fprintf(stderr, "onig_search: empty string.\n");
03694 #endif
03695 
03696     if (reg->threshold_len == 0) {
03697       start = end = str = address_for_empty_string;
03698       s = (UChar* )start;
03699       prev = (UChar* )NULL;
03700 
03701       MATCH_ARG_INIT(msa, option, region, start);
03702 #ifdef USE_COMBINATION_EXPLOSION_CHECK
03703       msa.state_check_buff      = (void* )0;
03704       msa.state_check_buff_size = 0;
03705 #endif
03706       MATCH_AND_RETURN_CHECK;
03707       goto mismatch;
03708     }
03709     goto mismatch_no_msa;
03710   }
03711 
03712 #ifdef ONIG_DEBUG_SEARCH
03713   fprintf(stderr, "onig_search(apply anchor): end: %d, start: %d, range: %d\n",
03714          (int )(end - str), (int )(start - str), (int )(range - str));
03715 #endif
03716 
03717   MATCH_ARG_INIT(msa, option, region, orig_start);
03718 #ifdef USE_COMBINATION_EXPLOSION_CHECK
03719   {
03720     int offset = (MIN(start, range) - str);
03721     STATE_CHECK_BUFF_INIT(msa, end - str, offset, reg->num_comb_exp_check);
03722   }
03723 #endif
03724 
03725   s = (UChar* )start;
03726   if (range > start) {   /* forward search */
03727     if (s > str)
03728       prev = onigenc_get_prev_char_head(reg->enc, str, s);
03729     else
03730       prev = (UChar* )NULL;
03731 
03732     if (reg->optimize != ONIG_OPTIMIZE_NONE) {
03733       UChar *sch_range, *low, *high, *low_prev;
03734 
03735       sch_range = (UChar* )range;
03736       if (reg->dmax != 0) {
03737        if (reg->dmax == ONIG_INFINITE_DISTANCE)
03738          sch_range = (UChar* )end;
03739        else {
03740          sch_range += reg->dmax;
03741          if (sch_range > end) sch_range = (UChar* )end;
03742        }
03743       }
03744 
03745       if ((end - start) < reg->threshold_len)
03746         goto mismatch;
03747 
03748       if (reg->dmax != ONIG_INFINITE_DISTANCE) {
03749        do {
03750          if (! forward_search_range(reg, str, end, s, sch_range,
03751                                  &low, &high, &low_prev)) goto mismatch;
03752          if (s < low) {
03753            s    = low;
03754            prev = low_prev;
03755          }
03756          while (s <= high) {
03757            MATCH_AND_RETURN_CHECK;
03758            prev = s;
03759            s += enc_len(reg->enc, s);
03760          }
03761        } while (s < range);
03762        goto mismatch;
03763       }
03764       else { /* check only. */
03765        if (! forward_search_range(reg, str, end, s, sch_range,
03766                                &low, &high, (UChar** )NULL)) goto mismatch;
03767 
03768         if ((reg->anchor & ANCHOR_ANYCHAR_STAR) != 0) {
03769           do {
03770             MATCH_AND_RETURN_CHECK;
03771             prev = s;
03772             s += enc_len(reg->enc, s);
03773 
03774             while (!ONIGENC_IS_MBC_NEWLINE(reg->enc, prev, end) && s < range) {
03775               prev = s;
03776               s += enc_len(reg->enc, s);
03777             }
03778           } while (s < range);
03779           goto mismatch;
03780         }
03781       }
03782     }
03783 
03784     do {
03785       MATCH_AND_RETURN_CHECK;
03786       prev = s;
03787       s += enc_len(reg->enc, s);
03788     } while (s < range);
03789 
03790     if (s == range) { /* because empty match with /$/. */
03791       MATCH_AND_RETURN_CHECK;
03792     }
03793   }
03794   else {  /* backward search */
03795     if (reg->optimize != ONIG_OPTIMIZE_NONE) {
03796       UChar *low, *high, *adjrange, *sch_start;
03797 
03798       if (range < end)
03799        adjrange = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, str, range);
03800       else
03801        adjrange = (UChar* )end;
03802 
03803       if (reg->dmax != ONIG_INFINITE_DISTANCE &&
03804          (end - range) >= reg->threshold_len) {
03805        do {
03806          sch_start = s + reg->dmax;
03807          if (sch_start > end) sch_start = (UChar* )end;
03808          if (backward_search_range(reg, str, end, sch_start, range, adjrange,
03809                                 &low, &high) <= 0)
03810            goto mismatch;
03811 
03812          if (s > high)
03813            s = high;
03814 
03815          while (s >= low) {
03816            prev = onigenc_get_prev_char_head(reg->enc, str, s);
03817            MATCH_AND_RETURN_CHECK;
03818            s = prev;
03819          }
03820        } while (s >= range);
03821        goto mismatch;
03822       }
03823       else { /* check only. */
03824        if ((end - range) < reg->threshold_len) goto mismatch;
03825 
03826        sch_start = s;
03827        if (reg->dmax != 0) {
03828          if (reg->dmax == ONIG_INFINITE_DISTANCE)
03829            sch_start = (UChar* )end;
03830          else {
03831            sch_start += reg->dmax;
03832            if (sch_start > end) sch_start = (UChar* )end;
03833            else
03834              sch_start = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc,
03835                                               start, sch_start);
03836          }
03837        }
03838        if (backward_search_range(reg, str, end, sch_start, range, adjrange,
03839                               &low, &high) <= 0) goto mismatch;
03840       }
03841     }
03842 
03843     do {
03844       prev = onigenc_get_prev_char_head(reg->enc, str, s);
03845       MATCH_AND_RETURN_CHECK;
03846       s = prev;
03847     } while (s >= range);
03848   }
03849 
03850  mismatch:
03851 #ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
03852   if (IS_FIND_LONGEST(reg->options)) {
03853     if (msa.best_len >= 0) {
03854       s = msa.best_s;
03855       goto match;
03856     }
03857   }
03858 #endif
03859   r = ONIG_MISMATCH;
03860 
03861  finish:
03862   MATCH_ARG_FREE(msa);
03863   ONIG_STATE_DEC_THREAD(reg);
03864 
03865   /* If result is mismatch and no FIND_NOT_EMPTY option,
03866      then the region is not setted in match_at(). */
03867   if (IS_FIND_NOT_EMPTY(reg->options) && region
03868 #ifdef USE_POSIX_REGION_OPTION
03869       && !IS_POSIX_REGION(option)
03870 #endif
03871       ) {
03872     onig_region_clear(region);
03873   }
03874 
03875 #ifdef ONIG_DEBUG
03876   if (r != ONIG_MISMATCH)
03877     fprintf(stderr, "onig_search: error %d\n", r);
03878 #endif
03879   return r;
03880 
03881  mismatch_no_msa:
03882   r = ONIG_MISMATCH;
03883  finish_no_msa:
03884   ONIG_STATE_DEC_THREAD(reg);
03885 #ifdef ONIG_DEBUG
03886   if (r != ONIG_MISMATCH)
03887     fprintf(stderr, "onig_search: error %d\n", r);
03888 #endif
03889   return r;
03890 
03891  match:
03892   ONIG_STATE_DEC_THREAD(reg);
03893   MATCH_ARG_FREE(msa);
03894   return s - str;
03895 }
03896 
03897 extern OnigEncoding
03898 onig_get_encoding(regex_t* reg)
03899 {
03900   return reg->enc;
03901 }
03902 
03903 extern OnigOptionType
03904 onig_get_options(regex_t* reg)
03905 {
03906   return reg->options;
03907 }
03908 
03909 extern  OnigAmbigType
03910 onig_get_ambig_flag(regex_t* reg)
03911 {
03912   return reg->ambig_flag;
03913 }
03914 
03915 extern OnigSyntaxType*
03916 onig_get_syntax(regex_t* reg)
03917 {
03918   return reg->syntax;
03919 }
03920 
03921 extern int
03922 onig_number_of_captures(regex_t* reg)
03923 {
03924   return reg->num_mem;
03925 }
03926 
03927 extern int
03928 onig_number_of_capture_histories(regex_t* reg)
03929 {
03930 #ifdef USE_CAPTURE_HISTORY
03931   int i, n;
03932 
03933   n = 0;
03934   for (i = 0; i <= ONIG_MAX_CAPTURE_HISTORY_GROUP; i++) {
03935     if (BIT_STATUS_AT(reg->capture_history, i) != 0)
03936       n++;
03937   }
03938   return n;
03939 #else
03940   return 0;
03941 #endif
03942 }
03943 
03944 extern void
03945 onig_copy_encoding(OnigEncoding to, OnigEncoding from)
03946 {
03947   *to = *from;
03948 }
03949