Ruby 1.9.2p136(2010-12-25revision30365)

- Main Page
- Modules
- Data Structures
- Files

- File List
- Globals

# regexec.c

Go to the documentation of this file.

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