1 /*************************************************

     2 *      Perl-Compatible Regular Expressions       *

     3 *************************************************/

     4 

     5 /* PCRE is a library of functions to support regular expressions whose syntax

     6 and semantics are as close as possible to those of the Perl 5 language.

     7 

     8                        Written by Philip Hazel

     9            Copyright (c) 1997-2008 University of Cambridge

    10 

    11 -----------------------------------------------------------------------------

    12 Redistribution and use in source and binary forms, with or without

    13 modification, are permitted provided that the following conditions are met:

    14 

    15     * Redistributions of source code must retain the above copyright notice,

    16       this list of conditions and the following disclaimer.

    17 

    18     * Redistributions in binary form must reproduce the above copyright

    19       notice, this list of conditions and the following disclaimer in the

    20       documentation and/or other materials provided with the distribution.

    21 

    22     * Neither the name of the University of Cambridge nor the names of its

    23       contributors may be used to endorse or promote products derived from

    24       this software without specific prior written permission.

    25 

    26 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

    27 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    28 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

    29 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE

    30 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

    31 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

    32 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

    33 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

    34 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

    35 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

    36 POSSIBILITY OF SUCH DAMAGE.

    37 -----------------------------------------------------------------------------

    38 */

    39 

    40 

    41 /* This module contains pcre_exec(), the externally visible function that does

    42 pattern matching using an NFA algorithm, trying to mimic Perl as closely as

    43 possible. There are also some static supporting functions. */

    44 

    45 #ifdef HAVE_CONFIG_H

    46 #include "config.h"

    47 #endif

    48 

    49 #define NLBLOCK md             /* Block containing newline information */

    50 #define PSSTART start_subject  /* Field containing processed string start */

    51 #define PSEND   end_subject    /* Field containing processed string end */

    52 

    53 #include "pcre_internal.h"

    54 

    55 /* Undefine some potentially clashing cpp symbols */

    56 

    57 #undef min

    58 #undef max

    59 

    60 /* Flag bits for the match() function */

    61 

    62 #define match_condassert     0x01  /* Called to check a condition assertion */

    63 #define match_cbegroup       0x02  /* Could-be-empty unlimited repeat group */

    64 

    65 /* Non-error returns from the match() function. Error returns are externally

    66 defined PCRE_ERROR_xxx codes, which are all negative. */

    67 

    68 #define MATCH_MATCH        1

    69 #define MATCH_NOMATCH      0

    70 

    71 /* Special internal returns from the match() function. Make them sufficiently

    72 negative to avoid the external error codes. */

    73 

    74 #define MATCH_COMMIT       (-999)

    75 #define MATCH_PRUNE        (-998)

    76 #define MATCH_SKIP         (-997)

    77 #define MATCH_THEN         (-996)

    78 

    79 /* Maximum number of ints of offset to save on the stack for recursive calls.

    80 If the offset vector is bigger, malloc is used. This should be a multiple of 3,

    81 because the offset vector is always a multiple of 3 long. */

    82 

    83 #define REC_STACK_SAVE_MAX 30

    84 

    85 /* Min and max values for the common repeats; for the maxima, 0 => infinity */

    86 

    87 static const char rep_min[] = { 0, 0, 1, 1, 0, 0 };

    88 static const char rep_max[] = { 0, 0, 0, 0, 1, 1 };

    89 

    90 

    91 

    92 #ifdef DEBUG

    93 /*************************************************

    94 *        Debugging function to print chars       *

    95 *************************************************/

    96 

    97 /* Print a sequence of chars in printable format, stopping at the end of the

    98 subject if the requested.

    99 

   100 Arguments:

   101   p           points to characters

   102   length      number to print

   103   is_subject  TRUE if printing from within md->start_subject

   104   md          pointer to matching data block, if is_subject is TRUE

   105 

   106 Returns:     nothing

   107 */

   108 

   109 static void

   110 pchars(const uschar *p, int length, BOOL is_subject, match_data *md)

   111 {

   112 unsigned int c;

   113 if (is_subject && length > md->end_subject - p) length = md->end_subject - p;

   114 while (length-- > 0)

   115   if (isprint(c = *(p++))) printf("%c", c); else printf("\\x%02x", c);

   116 }

   117 #endif

   118 

   119 

   120 

   121 /*************************************************

   122 *          Match a back-reference                *

   123 *************************************************/

   124 

   125 /* If a back reference hasn't been set, the length that is passed is greater

   126 than the number of characters left in the string, so the match fails.

   127 

   128 Arguments:

   129   offset      index into the offset vector

   130   eptr        points into the subject

   131   length      length to be matched

   132   md          points to match data block

   133   ims         the ims flags

   134 

   135 Returns:      TRUE if matched

   136 */

   137 

   138 static BOOL

   139 match_ref(int offset, register USPTR eptr, int length, match_data *md,

   140   unsigned long int ims)

   141 {

   142 USPTR p = md->start_subject + md->offset_vector[offset];

   143 

   144 #ifdef DEBUG

   145 if (eptr >= md->end_subject)

   146   printf("matching subject <null>");

   147 else

   148   {

   149   printf("matching subject ");

   150   pchars(eptr, length, TRUE, md);

   151   }

   152 printf(" against backref ");

   153 pchars(p, length, FALSE, md);

   154 printf("\n");

   155 #endif

   156 

   157 /* Always fail if not enough characters left */

   158 

   159 if (length > md->end_subject - eptr) return FALSE;

   160 

   161 /* Separate the caseless case for speed. In UTF-8 mode we can only do this

   162 properly if Unicode properties are supported. Otherwise, we can check only

   163 ASCII characters. */

   164 

   165 if ((ims & PCRE_CASELESS) != 0)

   166   {

   167 #ifdef SUPPORT_UTF8

   168 #ifdef SUPPORT_UCP

   169   if (md->utf8)

   170     {

   171     USPTR endptr = eptr + length;

   172     while (eptr < endptr)

   173       {

   174       int c, d;

   175       GETCHARINC(c, eptr);

   176       GETCHARINC(d, p);

   177       if (c != d && c != UCD_OTHERCASE(d)) return FALSE;

   178       }

   179     }

   180   else

   181 #endif

   182 #endif

   183 

   184   /* The same code works when not in UTF-8 mode and in UTF-8 mode when there

   185   is no UCP support. */

   186 

   187   while (length-- > 0)

   188     { if (md->lcc[*p++] != md->lcc[*eptr++]) return FALSE; }

   189   }

   190 

   191 /* In the caseful case, we can just compare the bytes, whether or not we

   192 are in UTF-8 mode. */

   193 

   194 else

   195   { while (length-- > 0) if (*p++ != *eptr++) return FALSE; }

   196 

   197 return TRUE;

   198 }

   199 

   200 

   201 

   202 /***************************************************************************

   203 ****************************************************************************

   204                    RECURSION IN THE match() FUNCTION

   205 

   206 The match() function is highly recursive, though not every recursive call

   207 increases the recursive depth. Nevertheless, some regular expressions can cause

   208 it to recurse to a great depth. I was writing for Unix, so I just let it call

   209 itself recursively. This uses the stack for saving everything that has to be

   210 saved for a recursive call. On Unix, the stack can be large, and this works

   211 fine.

   212 

   213 It turns out that on some non-Unix-like systems there are problems with

   214 programs that use a lot of stack. (This despite the fact that every last chip

   215 has oodles of memory these days, and techniques for extending the stack have

   216 been known for decades.) So....

   217 

   218 There is a fudge, triggered by defining NO_RECURSE, which avoids recursive

   219 calls by keeping local variables that need to be preserved in blocks of memory

   220 obtained from malloc() instead instead of on the stack. Macros are used to

   221 achieve this so that the actual code doesn't look very different to what it

   222 always used to.

   223 

   224 The original heap-recursive code used longjmp(). However, it seems that this

   225 can be very slow on some operating systems. Following a suggestion from Stan

   226 Switzer, the use of longjmp() has been abolished, at the cost of having to

   227 provide a unique number for each call to RMATCH. There is no way of generating

   228 a sequence of numbers at compile time in C. I have given them names, to make

   229 them stand out more clearly.

   230 

   231 Crude tests on x86 Linux show a small speedup of around 5-8%. However, on

   232 FreeBSD, avoiding longjmp() more than halves the time taken to run the standard

   233 tests. Furthermore, not using longjmp() means that local dynamic variables

   234 don't have indeterminate values; this has meant that the frame size can be

   235 reduced because the result can be "passed back" by straight setting of the

   236 variable instead of being passed in the frame.

   237 ****************************************************************************

   238 ***************************************************************************/

   239 

   240 /* Numbers for RMATCH calls. When this list is changed, the code at HEAP_RETURN

   241 below must be updated in sync.  */

   242 

   243 enum { RM1=1, RM2,  RM3,  RM4,  RM5,  RM6,  RM7,  RM8,  RM9,  RM10,

   244        RM11,  RM12, RM13, RM14, RM15, RM16, RM17, RM18, RM19, RM20,

   245        RM21,  RM22, RM23, RM24, RM25, RM26, RM27, RM28, RM29, RM30,

   246        RM31,  RM32, RM33, RM34, RM35, RM36, RM37, RM38, RM39, RM40,

   247        RM41,  RM42, RM43, RM44, RM45, RM46, RM47, RM48, RM49, RM50,

   248        RM51,  RM52, RM53, RM54 };

   249 

   250 /* These versions of the macros use the stack, as normal. There are debugging

   251 versions and production versions. Note that the "rw" argument of RMATCH isn't

   252 actuall used in this definition. */

   253 

   254 #ifndef NO_RECURSE

   255 #define REGISTER register

   256 

   257 #ifdef DEBUG

   258 #define RMATCH(ra,rb,rc,rd,re,rf,rg,rw) \

   259   { \

   260   printf("match() called in line %d\n", __LINE__); \

   261   rrc = match(ra,rb,mstart,rc,rd,re,rf,rg,rdepth+1); \

   262   printf("to line %d\n", __LINE__); \

   263   }

   264 #define RRETURN(ra) \

   265   { \

   266   printf("match() returned %d from line %d ", ra, __LINE__); \

   267   return ra; \

   268   }

   269 #else

   270 #define RMATCH(ra,rb,rc,rd,re,rf,rg,rw) \

   271   rrc = match(ra,rb,mstart,rc,rd,re,rf,rg,rdepth+1)

   272 #define RRETURN(ra) return ra

   273 #endif

   274 

   275 #else

   276 

   277 

   278 /* These versions of the macros manage a private stack on the heap. Note that

   279 the "rd" argument of RMATCH isn't actually used in this definition. It's the md

   280 argument of match(), which never changes. */

   281 

   282 #define REGISTER

   283 

   284 #define RMATCH(ra,rb,rc,rd,re,rf,rg,rw)\

   285   {\

   286   heapframe *newframe = (pcre_stack_malloc)(sizeof(heapframe));\

   287   frame->Xwhere = rw; \

   288   newframe->Xeptr = ra;\

   289   newframe->Xecode = rb;\

   290   newframe->Xmstart = mstart;\

   291   newframe->Xoffset_top = rc;\

   292   newframe->Xims = re;\

   293   newframe->Xeptrb = rf;\

   294   newframe->Xflags = rg;\

   295   newframe->Xrdepth = frame->Xrdepth + 1;\

   296   newframe->Xprevframe = frame;\

   297   frame = newframe;\

   298   DPRINTF(("restarting from line %d\n", __LINE__));\

   299   goto HEAP_RECURSE;\

   300   L_##rw:\

   301   DPRINTF(("jumped back to line %d\n", __LINE__));\

   302   }

   303 

   304 #define RRETURN(ra)\

   305   {\

   306   heapframe *newframe = frame;\

   307   frame = newframe->Xprevframe;\

   308   (pcre_stack_free)(newframe);\

   309   if (frame != NULL)\

   310     {\

   311     rrc = ra;\

   312     goto HEAP_RETURN;\

   313     }\

   314   return ra;\

   315   }

   316 

   317 

   318 /* Structure for remembering the local variables in a private frame */

   319 

   320 typedef struct heapframe {

   321   struct heapframe *Xprevframe;

   322 

   323   /* Function arguments that may change */

   324 

   325   const uschar *Xeptr;

   326   const uschar *Xecode;

   327   const uschar *Xmstart;

   328   int Xoffset_top;

   329   long int Xims;

   330   eptrblock *Xeptrb;

   331   int Xflags;

   332   unsigned int Xrdepth;

   333 

   334   /* Function local variables */

   335 

   336   const uschar *Xcallpat;

   337   const uschar *Xcharptr;

   338   const uschar *Xdata;

   339   const uschar *Xnext;

   340   const uschar *Xpp;

   341   const uschar *Xprev;

   342   const uschar *Xsaved_eptr;

   343 

   344   recursion_info Xnew_recursive;

   345 

   346   BOOL Xcur_is_word;

   347   BOOL Xcondition;

   348   BOOL Xprev_is_word;

   349 

   350   unsigned long int Xoriginal_ims;

   351 

   352 #ifdef SUPPORT_UCP

   353   int Xprop_type;

   354   int Xprop_value;

   355   int Xprop_fail_result;

   356   int Xprop_category;

   357   int Xprop_chartype;

   358   int Xprop_script;

   359   int Xoclength;

   360   uschar Xocchars[8];

   361 #endif

   362 

   363   int Xctype;

   364   unsigned int Xfc;

   365   int Xfi;

   366   int Xlength;

   367   int Xmax;

   368   int Xmin;

   369   int Xnumber;

   370   int Xoffset;

   371   int Xop;

   372   int Xsave_capture_last;

   373   int Xsave_offset1, Xsave_offset2, Xsave_offset3;

   374   int Xstacksave[REC_STACK_SAVE_MAX];

   375 

   376   eptrblock Xnewptrb;

   377 

   378   /* Where to jump back to */

   379 

   380   int Xwhere;

   381 

   382 } heapframe;

   383 

   384 #endif

   385 

   386 

   387 /***************************************************************************

   388 ***************************************************************************/

   389 

   390 

   391 

   392 /*************************************************

   393 *         Match from current position            *

   394 *************************************************/

   395 

   396 /* This function is called recursively in many circumstances. Whenever it

   397 returns a negative (error) response, the outer incarnation must also return the

   398 same response.

   399 

   400 Performance note: It might be tempting to extract commonly used fields from the

   401 md structure (e.g. utf8, end_subject) into individual variables to improve

   402 performance. Tests using gcc on a SPARC disproved this; in the first case, it

   403 made performance worse.

   404 

   405 Arguments:

   406    eptr        pointer to current character in subject

   407    ecode       pointer to current position in compiled code

   408    mstart      pointer to the current match start position (can be modified

   409                  by encountering \K)

   410    offset_top  current top pointer

   411    md          pointer to "static" info for the match

   412    ims         current /i, /m, and /s options

   413    eptrb       pointer to chain of blocks containing eptr at start of

   414                  brackets - for testing for empty matches

   415    flags       can contain

   416                  match_condassert - this is an assertion condition

   417                  match_cbegroup - this is the start of an unlimited repeat

   418                    group that can match an empty string

   419    rdepth      the recursion depth

   420 

   421 Returns:       MATCH_MATCH if matched            )  these values are >= 0

   422                MATCH_NOMATCH if failed to match  )

   423                a negative PCRE_ERROR_xxx value if aborted by an error condition

   424                  (e.g. stopped by repeated call or recursion limit)

   425 */

   426 

   427 static int

   428 match(REGISTER USPTR eptr, REGISTER const uschar *ecode, const uschar *mstart,

   429   int offset_top, match_data *md, unsigned long int ims, eptrblock *eptrb,

   430   int flags, unsigned int rdepth)

   431 {

   432 /* These variables do not need to be preserved over recursion in this function,

   433 so they can be ordinary variables in all cases. Mark some of them with

   434 "register" because they are used a lot in loops. */

   435 

   436 register int  rrc;         /* Returns from recursive calls */

   437 register int  i;           /* Used for loops not involving calls to RMATCH() */

   438 register unsigned int c;   /* Character values not kept over RMATCH() calls */

   439 register BOOL utf8;        /* Local copy of UTF-8 flag for speed */

   440 

   441 BOOL minimize, possessive; /* Quantifier options */

   442 

   443 /* When recursion is not being used, all "local" variables that have to be

   444 preserved over calls to RMATCH() are part of a "frame" which is obtained from

   445 heap storage. Set up the top-level frame here; others are obtained from the

   446 heap whenever RMATCH() does a "recursion". See the macro definitions above. */

   447 

   448 #ifdef NO_RECURSE

   449 heapframe *frame = (pcre_stack_malloc)(sizeof(heapframe));

   450 frame->Xprevframe = NULL;            /* Marks the top level */

   451 

   452 /* Copy in the original argument variables */

   453 

   454 frame->Xeptr = eptr;

   455 frame->Xecode = ecode;

   456 frame->Xmstart = mstart;

   457 frame->Xoffset_top = offset_top;

   458 frame->Xims = ims;

   459 frame->Xeptrb = eptrb;

   460 frame->Xflags = flags;

   461 frame->Xrdepth = rdepth;

   462 

   463 /* This is where control jumps back to to effect "recursion" */

   464 

   465 HEAP_RECURSE:

   466 

   467 /* Macros make the argument variables come from the current frame */

   468 

   469 #define eptr               frame->Xeptr

   470 #define ecode              frame->Xecode

   471 #define mstart             frame->Xmstart

   472 #define offset_top         frame->Xoffset_top

   473 #define ims                frame->Xims

   474 #define eptrb              frame->Xeptrb

   475 #define flags              frame->Xflags

   476 #define rdepth             frame->Xrdepth

   477 

   478 /* Ditto for the local variables */

   479 

   480 #ifdef SUPPORT_UTF8

   481 #define charptr            frame->Xcharptr

   482 #endif

   483 #define callpat            frame->Xcallpat

   484 #define data               frame->Xdata

   485 #define next               frame->Xnext

   486 #define pp                 frame->Xpp

   487 #define prev               frame->Xprev

   488 #define saved_eptr         frame->Xsaved_eptr

   489 

   490 #define new_recursive      frame->Xnew_recursive

   491 

   492 #define cur_is_word        frame->Xcur_is_word

   493 #define condition          frame->Xcondition

   494 #define prev_is_word       frame->Xprev_is_word

   495 

   496 #define original_ims       frame->Xoriginal_ims

   497 

   498 #ifdef SUPPORT_UCP

   499 #define prop_type          frame->Xprop_type

   500 #define prop_value         frame->Xprop_value

   501 #define prop_fail_result   frame->Xprop_fail_result

   502 #define prop_category      frame->Xprop_category

   503 #define prop_chartype      frame->Xprop_chartype

   504 #define prop_script        frame->Xprop_script

   505 #define oclength           frame->Xoclength

   506 #define occhars            frame->Xocchars

   507 #endif

   508 

   509 #define ctype              frame->Xctype

   510 #define fc                 frame->Xfc

   511 #define fi                 frame->Xfi

   512 #define length             frame->Xlength

   513 #define max                frame->Xmax

   514 #define min                frame->Xmin

   515 #define number             frame->Xnumber

   516 #define offset             frame->Xoffset

   517 #define op                 frame->Xop

   518 #define save_capture_last  frame->Xsave_capture_last

   519 #define save_offset1       frame->Xsave_offset1

   520 #define save_offset2       frame->Xsave_offset2

   521 #define save_offset3       frame->Xsave_offset3

   522 #define stacksave          frame->Xstacksave

   523 

   524 #define newptrb            frame->Xnewptrb

   525 

   526 /* When recursion is being used, local variables are allocated on the stack and

   527 get preserved during recursion in the normal way. In this environment, fi and

   528 i, and fc and c, can be the same variables. */

   529 

   530 #else         /* NO_RECURSE not defined */

   531 #define fi i

   532 #define fc c

   533 

   534 

   535 #ifdef SUPPORT_UTF8                /* Many of these variables are used only  */

   536 const uschar *charptr;             /* in small blocks of the code. My normal */

   537 #endif                             /* style of coding would have declared    */

   538 const uschar *callpat;             /* them within each of those blocks.      */

   539 const uschar *data;                /* However, in order to accommodate the   */

   540 const uschar *next;                /* version of this code that uses an      */

   541 USPTR         pp;                  /* external "stack" implemented on the    */

   542 const uschar *prev;                /* heap, it is easier to declare them all */

   543 USPTR         saved_eptr;          /* here, so the declarations can be cut   */

   544                                    /* out in a block. The only declarations  */

   545 recursion_info new_recursive;      /* within blocks below are for variables  */

   546                                    /* that do not have to be preserved over  */

   547 BOOL cur_is_word;                  /* a recursive call to RMATCH().          */

   548 BOOL condition;

   549 BOOL prev_is_word;

   550 

   551 unsigned long int original_ims;

   552 

   553 #ifdef SUPPORT_UCP

   554 int prop_type;

   555 int prop_value;

   556 int prop_fail_result;

   557 int prop_category;

   558 int prop_chartype;

   559 int prop_script;

   560 int oclength;

   561 uschar occhars[8];

   562 #endif

   563 

   564 int ctype;

   565 int length;

   566 int max;

   567 int min;

   568 int number;

   569 int offset;

   570 int op;

   571 int save_capture_last;

   572 int save_offset1, save_offset2, save_offset3;

   573 int stacksave[REC_STACK_SAVE_MAX];

   574 

   575 eptrblock newptrb;

   576 #endif     /* NO_RECURSE */

   577 

   578 /* These statements are here to stop the compiler complaining about unitialized

   579 variables. */

   580 

   581 #ifdef SUPPORT_UCP

   582 prop_value = 0;

   583 prop_fail_result = 0;

   584 #endif

   585 

   586 

   587 /* This label is used for tail recursion, which is used in a few cases even

   588 when NO_RECURSE is not defined, in order to reduce the amount of stack that is

   589 used. Thanks to Ian Taylor for noticing this possibility and sending the

   590 original patch. */

   591 

   592 TAIL_RECURSE:

   593 

   594 /* OK, now we can get on with the real code of the function. Recursive calls

   595 are specified by the macro RMATCH and RRETURN is used to return. When

   596 NO_RECURSE is *not* defined, these just turn into a recursive call to match()

   597 and a "return", respectively (possibly with some debugging if DEBUG is

   598 defined). However, RMATCH isn't like a function call because it's quite a

   599 complicated macro. It has to be used in one particular way. This shouldn't,

   600 however, impact performance when true recursion is being used. */

   601 

   602 #ifdef SUPPORT_UTF8

   603 utf8 = md->utf8;       /* Local copy of the flag */

   604 #else

   605 utf8 = FALSE;

   606 #endif

   607 

   608 /* First check that we haven't called match() too many times, or that we

   609 haven't exceeded the recursive call limit. */

   610 

   611 if (md->match_call_count++ >= md->match_limit) RRETURN(PCRE_ERROR_MATCHLIMIT);

   612 if (rdepth >= md->match_limit_recursion) RRETURN(PCRE_ERROR_RECURSIONLIMIT);

   613 

   614 original_ims = ims;    /* Save for resetting on ')' */

   615 

   616 /* At the start of a group with an unlimited repeat that may match an empty

   617 string, the match_cbegroup flag is set. When this is the case, add the current

   618 subject pointer to the chain of such remembered pointers, to be checked when we

   619 hit the closing ket, in order to break infinite loops that match no characters.

   620 When match() is called in other circumstances, don't add to the chain. The

   621 match_cbegroup flag must NOT be used with tail recursion, because the memory

   622 block that is used is on the stack, so a new one may be required for each

   623 match(). */

   624 

   625 if ((flags & match_cbegroup) != 0)

   626   {

   627   newptrb.epb_saved_eptr = eptr;

   628   newptrb.epb_prev = eptrb;

   629   eptrb = &newptrb;

   630   }

   631 

   632 /* Now start processing the opcodes. */

   633 

   634 for (;;)

   635   {

   636   minimize = possessive = FALSE;

   637   op = *ecode;

   638 

   639   /* For partial matching, remember if we ever hit the end of the subject after

   640   matching at least one subject character. */

   641 

   642   if (md->partial &&

   643       eptr >= md->end_subject &&

   644       eptr > mstart)

   645     md->hitend = TRUE;

   646 

   647   switch(op)

   648     {

   649     case OP_FAIL:

   650     RRETURN(MATCH_NOMATCH);

   651 

   652     case OP_PRUNE:

   653     RMATCH(eptr, ecode + _pcre_OP_lengths[*ecode], offset_top, md,

   654       ims, eptrb, flags, RM51);

   655     if (rrc != MATCH_NOMATCH) RRETURN(rrc);

   656     RRETURN(MATCH_PRUNE);

   657 

   658     case OP_COMMIT:

   659     RMATCH(eptr, ecode + _pcre_OP_lengths[*ecode], offset_top, md,

   660       ims, eptrb, flags, RM52);

   661     if (rrc != MATCH_NOMATCH) RRETURN(rrc);

   662     RRETURN(MATCH_COMMIT);

   663 

   664     case OP_SKIP:

   665     RMATCH(eptr, ecode + _pcre_OP_lengths[*ecode], offset_top, md,

   666       ims, eptrb, flags, RM53);

   667     if (rrc != MATCH_NOMATCH) RRETURN(rrc);

   668     md->start_match_ptr = eptr;   /* Pass back current position */

   669     RRETURN(MATCH_SKIP);

   670 

   671     case OP_THEN:

   672     RMATCH(eptr, ecode + _pcre_OP_lengths[*ecode], offset_top, md,

   673       ims, eptrb, flags, RM54);

   674     if (rrc != MATCH_NOMATCH) RRETURN(rrc);

   675     RRETURN(MATCH_THEN);

   676 

   677     /* Handle a capturing bracket. If there is space in the offset vector, save

   678     the current subject position in the working slot at the top of the vector.

   679     We mustn't change the current values of the data slot, because they may be

   680     set from a previous iteration of this group, and be referred to by a

   681     reference inside the group.

   682 

   683     If the bracket fails to match, we need to restore this value and also the

   684     values of the final offsets, in case they were set by a previous iteration

   685     of the same bracket.

   686 

   687     If there isn't enough space in the offset vector, treat this as if it were

   688     a non-capturing bracket. Don't worry about setting the flag for the error

   689     case here; that is handled in the code for KET. */

   690 

   691     case OP_CBRA:

   692     case OP_SCBRA:

   693     number = GET2(ecode, 1+LINK_SIZE);

   694     offset = number << 1;

   695 

   696 #ifdef DEBUG

   697     printf("start bracket %d\n", number);

   698     printf("subject=");

   699     pchars(eptr, 16, TRUE, md);

   700     printf("\n");

   701 #endif

   702 

   703     if (offset < md->offset_max)

   704       {

   705       save_offset1 = md->offset_vector[offset];

   706       save_offset2 = md->offset_vector[offset+1];

   707       save_offset3 = md->offset_vector[md->offset_end - number];

   708       save_capture_last = md->capture_last;

   709 

   710       DPRINTF(("saving %d %d %d\n", save_offset1, save_offset2, save_offset3));

   711       md->offset_vector[md->offset_end - number] = eptr - md->start_subject;

   712 

   713       flags = (op == OP_SCBRA)? match_cbegroup : 0;

   714       do

   715         {

   716         RMATCH(eptr, ecode + _pcre_OP_lengths[*ecode], offset_top, md,

   717           ims, eptrb, flags, RM1);

   718         if (rrc != MATCH_NOMATCH && rrc != MATCH_THEN) RRETURN(rrc);

   719         md->capture_last = save_capture_last;

   720         ecode += GET(ecode, 1);

   721         }

   722       while (*ecode == OP_ALT);

   723 

   724       DPRINTF(("bracket %d failed\n", number));

   725 

   726       md->offset_vector[offset] = save_offset1;

   727       md->offset_vector[offset+1] = save_offset2;

   728       md->offset_vector[md->offset_end - number] = save_offset3;

   729 

   730       RRETURN(MATCH_NOMATCH);

   731       }

   732 

   733     /* FALL THROUGH ... Insufficient room for saving captured contents. Treat

   734     as a non-capturing bracket. */

   735 

   736     /* VVVVVVVVVVVVVVVVVVVVVVVVV */

   737     /* VVVVVVVVVVVVVVVVVVVVVVVVV */

   738 

   739     DPRINTF(("insufficient capture room: treat as non-capturing\n"));

   740 

   741     /* VVVVVVVVVVVVVVVVVVVVVVVVV */

   742     /* VVVVVVVVVVVVVVVVVVVVVVVVV */

   743 

   744     /* Non-capturing bracket. Loop for all the alternatives. When we get to the

   745     final alternative within the brackets, we would return the result of a

   746     recursive call to match() whatever happened. We can reduce stack usage by

   747     turning this into a tail recursion, except in the case when match_cbegroup

   748     is set.*/

   749 

   750     case OP_BRA:

   751     case OP_SBRA:

   752     DPRINTF(("start non-capturing bracket\n"));

   753     flags = (op >= OP_SBRA)? match_cbegroup : 0;

   754     for (;;)

   755       {

   756       if (ecode[GET(ecode, 1)] != OP_ALT)   /* Final alternative */

   757         {

   758         if (flags == 0)    /* Not a possibly empty group */

   759           {

   760           ecode += _pcre_OP_lengths[*ecode];

   761           DPRINTF(("bracket 0 tail recursion\n"));

   762           goto TAIL_RECURSE;

   763           }

   764 

   765         /* Possibly empty group; can't use tail recursion. */

   766 

   767         RMATCH(eptr, ecode + _pcre_OP_lengths[*ecode], offset_top, md, ims,

   768           eptrb, flags, RM48);

   769         RRETURN(rrc);

   770         }

   771 

   772       /* For non-final alternatives, continue the loop for a NOMATCH result;

   773       otherwise return. */

   774 

   775       RMATCH(eptr, ecode + _pcre_OP_lengths[*ecode], offset_top, md, ims,

   776         eptrb, flags, RM2);

   777       if (rrc != MATCH_NOMATCH && rrc != MATCH_THEN) RRETURN(rrc);

   778       ecode += GET(ecode, 1);

   779       }

   780     /* Control never reaches here. */

   781 

   782     /* Conditional group: compilation checked that there are no more than

   783     two branches. If the condition is false, skipping the first branch takes us

   784     past the end if there is only one branch, but that's OK because that is

   785     exactly what going to the ket would do. As there is only one branch to be

   786     obeyed, we can use tail recursion to avoid using another stack frame. */

   787 

   788     case OP_COND:

   789     case OP_SCOND:

   790     if (ecode[LINK_SIZE+1] == OP_RREF)         /* Recursion test */

   791       {

   792       offset = GET2(ecode, LINK_SIZE + 2);     /* Recursion group number*/

   793       condition = md->recursive != NULL &&

   794         (offset == RREF_ANY || offset == md->recursive->group_num);

   795       ecode += condition? 3 : GET(ecode, 1);

   796       }

   797 

   798     else if (ecode[LINK_SIZE+1] == OP_CREF)    /* Group used test */

   799       {

   800       offset = GET2(ecode, LINK_SIZE+2) << 1;  /* Doubled ref number */

   801       condition = offset < offset_top && md->offset_vector[offset] >= 0;

   802       ecode += condition? 3 : GET(ecode, 1);

   803       }

   804 

   805     else if (ecode[LINK_SIZE+1] == OP_DEF)     /* DEFINE - always false */

   806       {

   807       condition = FALSE;

   808       ecode += GET(ecode, 1);

   809       }

   810 

   811     /* The condition is an assertion. Call match() to evaluate it - setting

   812     the final argument match_condassert causes it to stop at the end of an

   813     assertion. */

   814 

   815     else

   816       {

   817       RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, ims, NULL,

   818           match_condassert, RM3);

   819       if (rrc == MATCH_MATCH)

   820         {

   821         condition = TRUE;

   822         ecode += 1 + LINK_SIZE + GET(ecode, LINK_SIZE + 2);

   823         while (*ecode == OP_ALT) ecode += GET(ecode, 1);

   824         }

   825       else if (rrc != MATCH_NOMATCH && rrc != MATCH_THEN)

   826         {

   827         RRETURN(rrc);         /* Need braces because of following else */

   828         }

   829       else

   830         {

   831         condition = FALSE;

   832         ecode += GET(ecode, 1);

   833         }

   834       }

   835 

   836     /* We are now at the branch that is to be obeyed. As there is only one,

   837     we can use tail recursion to avoid using another stack frame, except when

   838     match_cbegroup is required for an unlimited repeat of a possibly empty

   839     group. If the second alternative doesn't exist, we can just plough on. */

   840 

   841     if (condition || *ecode == OP_ALT)

   842       {

   843       ecode += 1 + LINK_SIZE;

   844       if (op == OP_SCOND)        /* Possibly empty group */

   845         {

   846         RMATCH(eptr, ecode, offset_top, md, ims, eptrb, match_cbegroup, RM49);

   847         RRETURN(rrc);

   848         }

   849       else                       /* Group must match something */

   850         {

   851         flags = 0;

   852         goto TAIL_RECURSE;

   853         }

   854       }

   855     else                         /* Condition false & no 2nd alternative */

   856       {

   857       ecode += 1 + LINK_SIZE;

   858       }

   859     break;

   860 

   861 

   862     /* End of the pattern, either real or forced. If we are in a top-level

   863     recursion, we should restore the offsets appropriately and continue from

   864     after the call. */

   865 

   866     case OP_ACCEPT:

   867     case OP_END:

   868     if (md->recursive != NULL && md->recursive->group_num == 0)

   869       {

   870       recursion_info *rec = md->recursive;

   871       DPRINTF(("End of pattern in a (?0) recursion\n"));

   872       md->recursive = rec->prevrec;

   873       memmove(md->offset_vector, rec->offset_save,

   874         rec->saved_max * sizeof(int));

   875       mstart = rec->save_start;

   876       ims = original_ims;

   877       ecode = rec->after_call;

   878       break;

   879       }

   880 

   881     /* Otherwise, if PCRE_NOTEMPTY is set, fail if we have matched an empty

   882     string - backtracking will then try other alternatives, if any. */

   883 

   884     if (md->notempty && eptr == mstart) RRETURN(MATCH_NOMATCH);

   885     md->end_match_ptr = eptr;           /* Record where we ended */

   886     md->end_offset_top = offset_top;    /* and how many extracts were taken */

   887     md->start_match_ptr = mstart;       /* and the start (\K can modify) */

   888     RRETURN(MATCH_MATCH);

   889 

   890     /* Change option settings */

   891 

   892     case OP_OPT:

   893     ims = ecode[1];

   894     ecode += 2;

   895     DPRINTF(("ims set to %02lx\n", ims));

   896     break;

   897 

   898     /* Assertion brackets. Check the alternative branches in turn - the

   899     matching won't pass the KET for an assertion. If any one branch matches,

   900     the assertion is true. Lookbehind assertions have an OP_REVERSE item at the

   901     start of each branch to move the current point backwards, so the code at

   902     this level is identical to the lookahead case. */

   903 

   904     case OP_ASSERT:

   905     case OP_ASSERTBACK:

   906     do

   907       {

   908       RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, ims, NULL, 0,

   909         RM4);

   910       if (rrc == MATCH_MATCH) break;

   911       if (rrc != MATCH_NOMATCH && rrc != MATCH_THEN) RRETURN(rrc);

   912       ecode += GET(ecode, 1);

   913       }

   914     while (*ecode == OP_ALT);

   915     if (*ecode == OP_KET) RRETURN(MATCH_NOMATCH);

   916 

   917     /* If checking an assertion for a condition, return MATCH_MATCH. */

   918 

   919     if ((flags & match_condassert) != 0) RRETURN(MATCH_MATCH);

   920 

   921     /* Continue from after the assertion, updating the offsets high water

   922     mark, since extracts may have been taken during the assertion. */

   923 

   924     do ecode += GET(ecode,1); while (*ecode == OP_ALT);

   925     ecode += 1 + LINK_SIZE;

   926     offset_top = md->end_offset_top;

   927     continue;

   928 

   929     /* Negative assertion: all branches must fail to match */

   930 

   931     case OP_ASSERT_NOT:

   932     case OP_ASSERTBACK_NOT:

   933     do

   934       {

   935       RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, ims, NULL, 0,

   936         RM5);

   937       if (rrc == MATCH_MATCH) RRETURN(MATCH_NOMATCH);

   938       if (rrc != MATCH_NOMATCH && rrc != MATCH_THEN) RRETURN(rrc);

   939       ecode += GET(ecode,1);

   940       }

   941     while (*ecode == OP_ALT);

   942 

   943     if ((flags & match_condassert) != 0) RRETURN(MATCH_MATCH);

   944 

   945     ecode += 1 + LINK_SIZE;

   946     continue;

   947 

   948     /* Move the subject pointer back. This occurs only at the start of

   949     each branch of a lookbehind assertion. If we are too close to the start to

   950     move back, this match function fails. When working with UTF-8 we move

   951     back a number of characters, not bytes. */

   952 

   953     case OP_REVERSE:

   954 #ifdef SUPPORT_UTF8

   955     if (utf8)

   956       {

   957       i = GET(ecode, 1);

   958       while (i-- > 0)

   959         {

   960         eptr--;

   961         if (eptr < md->start_subject) RRETURN(MATCH_NOMATCH);

   962         BACKCHAR(eptr);

   963         }

   964       }

   965     else

   966 #endif

   967 

   968     /* No UTF-8 support, or not in UTF-8 mode: count is byte count */

   969 

   970       {

   971       eptr -= GET(ecode, 1);

   972       if (eptr < md->start_subject) RRETURN(MATCH_NOMATCH);

   973       }

   974 

   975     /* Skip to next op code */

   976 

   977     ecode += 1 + LINK_SIZE;

   978     break;

   979 

   980     /* The callout item calls an external function, if one is provided, passing

   981     details of the match so far. This is mainly for debugging, though the

   982     function is able to force a failure. */

   983 

   984     case OP_CALLOUT:

   985     if (pcre_callout != NULL)

   986       {

   987       pcre_callout_block cb;

   988       cb.version          = 1;   /* Version 1 of the callout block */

   989       cb.callout_number   = ecode[1];

   990       cb.offset_vector    = md->offset_vector;

   991       cb.subject          = (PCRE_SPTR)md->start_subject;

   992       cb.subject_length   = md->end_subject - md->start_subject;

   993       cb.start_match      = mstart - md->start_subject;

   994       cb.current_position = eptr - md->start_subject;

   995       cb.pattern_position = GET(ecode, 2);

   996       cb.next_item_length = GET(ecode, 2 + LINK_SIZE);

   997       cb.capture_top      = offset_top/2;

   998       cb.capture_last     = md->capture_last;

   999       cb.callout_data     = md->callout_data;

  1000       if ((rrc = (*pcre_callout)(&cb)) > 0) RRETURN(MATCH_NOMATCH);

  1001       if (rrc < 0) RRETURN(rrc);

  1002       }

  1003     ecode += 2 + 2*LINK_SIZE;

  1004     break;

  1005 

  1006     /* Recursion either matches the current regex, or some subexpression. The

  1007     offset data is the offset to the starting bracket from the start of the

  1008     whole pattern. (This is so that it works from duplicated subpatterns.)

  1009 

  1010     If there are any capturing brackets started but not finished, we have to

  1011     save their starting points and reinstate them after the recursion. However,

  1012     we don't know how many such there are (offset_top records the completed

  1013     total) so we just have to save all the potential data. There may be up to

  1014     65535 such values, which is too large to put on the stack, but using malloc

  1015     for small numbers seems expensive. As a compromise, the stack is used when

  1016     there are no more than REC_STACK_SAVE_MAX values to store; otherwise malloc

  1017     is used. A problem is what to do if the malloc fails ... there is no way of

  1018     returning to the top level with an error. Save the top REC_STACK_SAVE_MAX

  1019     values on the stack, and accept that the rest may be wrong.

  1020 

  1021     There are also other values that have to be saved. We use a chained

  1022     sequence of blocks that actually live on the stack. Thanks to Robin Houston

  1023     for the original version of this logic. */

  1024 

  1025     case OP_RECURSE:

  1026       {

  1027       callpat = md->start_code + GET(ecode, 1);

  1028       new_recursive.group_num = (callpat == md->start_code)? 0 :

  1029         GET2(callpat, 1 + LINK_SIZE);

  1030 

  1031       /* Add to "recursing stack" */

  1032 

  1033       new_recursive.prevrec = md->recursive;

  1034       md->recursive = &new_recursive;

  1035 

  1036       /* Find where to continue from afterwards */

  1037 

  1038       ecode += 1 + LINK_SIZE;

  1039       new_recursive.after_call = ecode;

  1040 

  1041       /* Now save the offset data. */

  1042 

  1043       new_recursive.saved_max = md->offset_end;

  1044       if (new_recursive.saved_max <= REC_STACK_SAVE_MAX)

  1045         new_recursive.offset_save = stacksave;

  1046       else

  1047         {

  1048         new_recursive.offset_save =

  1049           (int *)(pcre_malloc)(new_recursive.saved_max * sizeof(int));

  1050         if (new_recursive.offset_save == NULL) RRETURN(PCRE_ERROR_NOMEMORY);

  1051         }

  1052 

  1053       memcpy(new_recursive.offset_save, md->offset_vector,

  1054             new_recursive.saved_max * sizeof(int));

  1055       new_recursive.save_start = mstart;

  1056       mstart = eptr;

  1057 

  1058       /* OK, now we can do the recursion. For each top-level alternative we

  1059       restore the offset and recursion data. */

  1060 

  1061       DPRINTF(("Recursing into group %d\n", new_recursive.group_num));

  1062       flags = (*callpat >= OP_SBRA)? match_cbegroup : 0;

  1063       do

  1064         {

  1065         RMATCH(eptr, callpat + _pcre_OP_lengths[*callpat], offset_top,

  1066           md, ims, eptrb, flags, RM6);

  1067         if (rrc == MATCH_MATCH)

  1068           {

  1069           DPRINTF(("Recursion matched\n"));

  1070           md->recursive = new_recursive.prevrec;

  1071           if (new_recursive.offset_save != stacksave)

  1072             (pcre_free)(new_recursive.offset_save);

  1073           RRETURN(MATCH_MATCH);

  1074           }

  1075         else if (rrc != MATCH_NOMATCH && rrc != MATCH_THEN)

  1076           {

  1077           DPRINTF(("Recursion gave error %d\n", rrc));

  1078           RRETURN(rrc);

  1079           }

  1080 

  1081         md->recursive = &new_recursive;

  1082         memcpy(md->offset_vector, new_recursive.offset_save,

  1083             new_recursive.saved_max * sizeof(int));

  1084         callpat += GET(callpat, 1);

  1085         }

  1086       while (*callpat == OP_ALT);

  1087 

  1088       DPRINTF(("Recursion didn't match\n"));

  1089       md->recursive = new_recursive.prevrec;

  1090       if (new_recursive.offset_save != stacksave)

  1091         (pcre_free)(new_recursive.offset_save);

  1092       RRETURN(MATCH_NOMATCH);

  1093       }

  1094     /* Control never reaches here */

  1095 

  1096     /* "Once" brackets are like assertion brackets except that after a match,

  1097     the point in the subject string is not moved back. Thus there can never be

  1098     a move back into the brackets. Friedl calls these "atomic" subpatterns.

  1099     Check the alternative branches in turn - the matching won't pass the KET

  1100     for this kind of subpattern. If any one branch matches, we carry on as at

  1101     the end of a normal bracket, leaving the subject pointer. */

  1102 

  1103     case OP_ONCE:

  1104     prev = ecode;

  1105     saved_eptr = eptr;

  1106 

  1107     do

  1108       {

  1109       RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, ims, eptrb, 0, RM7);

  1110       if (rrc == MATCH_MATCH) break;

  1111       if (rrc != MATCH_NOMATCH && rrc != MATCH_THEN) RRETURN(rrc);

  1112       ecode += GET(ecode,1);

  1113       }

  1114     while (*ecode == OP_ALT);

  1115 

  1116     /* If hit the end of the group (which could be repeated), fail */

  1117 

  1118     if (*ecode != OP_ONCE && *ecode != OP_ALT) RRETURN(MATCH_NOMATCH);

  1119 

  1120     /* Continue as from after the assertion, updating the offsets high water

  1121     mark, since extracts may have been taken. */

  1122 

  1123     do ecode += GET(ecode, 1); while (*ecode == OP_ALT);

  1124 

  1125     offset_top = md->end_offset_top;

  1126     eptr = md->end_match_ptr;

  1127 

  1128     /* For a non-repeating ket, just continue at this level. This also

  1129     happens for a repeating ket if no characters were matched in the group.

  1130     This is the forcible breaking of infinite loops as implemented in Perl

  1131     5.005. If there is an options reset, it will get obeyed in the normal

  1132     course of events. */

  1133 

  1134     if (*ecode == OP_KET || eptr == saved_eptr)

  1135       {