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-2005 University of Cambridge

    10 

    11     Copyright (C) 2002, 2004, 2006, 2007 Apple Inc. All rights reserved.

    12 

    13 -----------------------------------------------------------------------------

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

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

    16 

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

    18       this list of conditions and the following disclaimer.

    19 

    20     * Redistributions in binary form must reproduce the above copyright

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

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

    23 

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

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

    26       this software without specific prior written permission.

    27 

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

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

    30 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

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

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

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

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

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

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

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

    38 POSSIBILITY OF SUCH DAMAGE.

    39 -----------------------------------------------------------------------------

    40 */

    41 

    42 

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

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

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

    46 

    47 #include "pcre_internal.h"

    48 

    49 /* Avoid warnings on Windows. */

    50 #undef min

    51 #undef max

    52 

    53 /* Structure for building a chain of data that actually lives on the

    54 stack, for holding the values of the subject pointer at the start of each

    55 subpattern, so as to detect when an empty string has been matched by a

    56 subpattern - to break infinite loops. When NO_RECURSE is set, these blocks

    57 are on the heap, not on the stack. */

    58 

    59 typedef struct eptrblock {

    60   struct eptrblock *epb_prev;

    61   const pcre_uchar *epb_saved_eptr;

    62 } eptrblock;

    63 

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

    65 

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

    67 #define match_isgroup      0x02    /* Set if start of bracketed group */

    68 

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

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

    71 

    72 #define MATCH_MATCH        1

    73 #define MATCH_NOMATCH      0

    74 

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

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

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

    78 

    79 #define REC_STACK_SAVE_MAX 30

    80 

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

    82 

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

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

    85 

    86 

    87 

    88 #ifdef DEBUG

    89 /*************************************************

    90 *        Debugging function to print chars       *

    91 *************************************************/

    92 

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

    94 subject if the requested.

    95 

    96 Arguments:

    97   p           points to characters

    98   length      number to print

    99   is_subject  TRUE if printing from within md->start_subject

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

   101 

   102 Returns:     nothing

   103 */

   104 

   105 static void

   106 pchars(const pcre_uchar *p, int length, BOOL is_subject, match_data *md)

   107 {

   108 int c;

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

   110 while (length-- > 0)

   111   if (isprint(c = *(p++))) printf("%c", c);

   112 #if PCRE_UTF16

   113   else if (c < 256) printf("\\x%02x", c);

   114   else printf("\\x{%x}", c);

   115 #else

   116   else printf("\\x%02x", c);

   117 #endif

   118 }

   119 #endif

   120 

   121 

   122 

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

   124 *          Match a back-reference                *

   125 *************************************************/

   126 

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

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

   129 

   130 Arguments:

   131   offset      index into the offset vector

   132   eptr        points into the subject

   133   length      length to be matched

   134   md          points to match data block

   135   ims         the ims flags

   136 

   137 Returns:      TRUE if matched

   138 */

   139 

   140 static BOOL

   141 match_ref(int offset, register const pcre_uchar *eptr, int length, match_data *md,

   142   unsigned long int ims)

   143 {

   144 const pcre_uchar *p = md->start_subject + md->offset_vector[offset];

   145 

   146 #ifdef DEBUG

   147 if (eptr >= md->end_subject)

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

   149 else

   150   {

   151   printf("matching subject ");

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

   153   }

   154 printf(" against backref ");

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

   156 printf("\n");

   157 #endif

   158 

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

   160 

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

   162 

   163 /* Separate the caselesss case for speed */

   164 

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

   166   {

   167   while (length-- > 0)

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

   169   }

   170 else

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

   172 

   173 return TRUE;

   174 }

   175 

   176 

   177 

   178 /***************************************************************************

   179 ****************************************************************************

   180                    RECURSION IN THE match() FUNCTION

   181 

   182 The match() function is highly recursive. Some regular expressions can cause

   183 it to recurse thousands of times. I was writing for Unix, so I just let it

   184 call itself recursively. This uses the stack for saving everything that has

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

   186 works fine.

   187 

   188 It turns out that on non-Unix systems there are problems with programs that

   189 use a lot of stack. (This despite the fact that every last chip has oodles

   190 of memory these days, and techniques for extending the stack have been known

   191 for decades.) So....

   192 

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

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

   195 obtained from malloc instead instead of on the stack. Macros are used to

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

   197 always used to.

   198 ****************************************************************************

   199 ***************************************************************************/

   200 

   201 

   202 /* These versions of the macros use the stack, as normal */

   203 

   204 #ifndef NO_RECURSE

   205 #define REGISTER register

   206 #define RMATCH(num,rx,ra,rb,rc,rd,re,rf,rg) rx = match(ra,rb,rc,rd,re,rf,rg)

   207 #define RRETURN(ra) return ra

   208 #else

   209 

   210 

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

   212 that the rd argument of RMATCH isn't actually used. It's the md argument of

   213 match(), which never changes. */

   214 

   215 #define REGISTER

   216 

   217 #ifndef __GNUC__

   218 

   219 /* Use numbered labels and switch statement at the bottom of the match function. */

   220 

   221 #define RMATCH_WHERE(num) num

   222 #define RRETURN_LABEL RRETURN_SWITCH

   223 

   224 #else

   225 

   226 /* Use GCC's computed goto extension. */

   227 

   228 /* For one test case this is more than 40% faster than the switch statement.

   229 We could avoid the use of the num argument entirely by using local labels,

   230 but using it for the GCC case as well as the non-GCC case allows us to share

   231 a bit more code and notice if we use conflicting numbers.*/

   232 

   233 #define RMATCH_WHERE(num) &&RRETURN_##num

   234 #define RRETURN_LABEL *frame->Xwhere

   235 

   236 #endif

   237 

   238 

   239 #define RMATCH(num,rx,ra,rb,rc,rd,re,rf,rg)\

   240   {\

   241   heapframe *newframe;\

   242   if (frame >= stackframes && frame + 1 < stackframesend)\

   243     newframe = frame + 1;\

   244   else\

   245     newframe = (pcre_stack_malloc)(sizeof(heapframe));\

   246   frame->Xwhere = RMATCH_WHERE(num);\

   247   newframe->Xeptr = ra;\

   248   newframe->Xecode = rb;\

   249   newframe->Xoffset_top = rc;\

   250   newframe->Xims = re;\

   251   newframe->Xeptrb = rf;\

   252   newframe->Xflags = rg;\

   253   newframe->Xprevframe = frame;\

   254   frame = newframe;\

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

   256   goto HEAP_RECURSE;\

   257 RRETURN_##num:\

   258   DPRINTF(("did a goto back to line %d\n", __LINE__));\

   259   frame = md->thisframe;\

   260   rx = frame->Xresult;\

   261   }

   262 

   263 #define RRETURN(ra)\

   264   {\

   265   heapframe *newframe = frame;\

   266   frame = newframe->Xprevframe;\

   267   if (!(newframe >= stackframes && newframe < stackframesend))\

   268     (pcre_stack_free)(newframe);\

   269   if (frame != NULL)\

   270     {\

   271     frame->Xresult = ra;\

   272     md->thisframe = frame;\

   273     goto RRETURN_LABEL;\

   274     }\

   275   return ra;\

   276   }

   277 

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

   279 

   280 typedef struct heapframe {

   281   struct heapframe *Xprevframe;

   282 

   283   /* Function arguments that may change */

   284 

   285   const pcre_uchar *Xeptr;

   286   const uschar *Xecode;

   287   int Xoffset_top;

   288   long int Xims;

   289   eptrblock *Xeptrb;

   290   int Xflags;

   291 

   292   /* Function local variables */

   293 

   294   const uschar *Xcallpat;

   295   const uschar *Xcharptr;

   296   const uschar *Xdata;

   297   const uschar *Xnext;

   298   const pcre_uchar *Xpp;

   299   const uschar *Xprev;

   300   const pcre_uchar *Xsaved_eptr;

   301 

   302   recursion_info Xnew_recursive;

   303 

   304   BOOL Xcur_is_word;

   305   BOOL Xcondition;

   306   BOOL Xminimize;

   307   BOOL Xprev_is_word;

   308 

   309   unsigned long int Xoriginal_ims;

   310 

   311 #ifdef SUPPORT_UCP

   312   int Xprop_type;

   313   int Xprop_fail_result;

   314   int Xprop_category;

   315   int Xprop_chartype;

   316   int Xprop_othercase;

   317   int Xprop_test_against;

   318   int *Xprop_test_variable;

   319 

   320   int Xrepeat_othercase;

   321 #endif

   322 

   323   int Xctype;

   324   int Xfc;

   325   int Xfi;

   326   int Xlength;

   327   int Xmax;

   328   int Xmin;

   329   int Xnumber;

   330   int Xoffset;

   331   int Xop;

   332   int Xsave_capture_last;

   333   int Xsave_offset1, Xsave_offset2, Xsave_offset3;

   334   int Xstacksave[REC_STACK_SAVE_MAX];

   335 

   336   eptrblock Xnewptrb;

   337 

   338   /* Place to pass back result, and where to jump back to */

   339 

   340   int Xresult;

   341 #ifndef __GNUC__

   342   int Xwhere;

   343 #else

   344   void *Xwhere;

   345 #endif

   346 

   347 } heapframe;

   348 

   349 #endif

   350 

   351 

   352 /***************************************************************************

   353 ***************************************************************************/

   354 

   355 

   356 

   357 /*************************************************

   358 *         Match from current position            *

   359 *************************************************/

   360 

   361 /* On entry ecode points to the first opcode, and eptr to the first character

   362 in the subject string, while eptrb holds the value of eptr at the start of the

   363 last bracketed group - used for breaking infinite loops matching zero-length

   364 strings. This function is called recursively in many circumstances. Whenever it

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

   366 same response.

   367 

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

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

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

   371 made performance worse.

   372 

   373 Arguments:

   374    eptr        pointer in subject

   375    ecode       position in code

   376    offset_top  current top pointer

   377    md          pointer to "static" info for the match

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

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

   380                  brackets - for testing for empty matches

   381    flags       can contain

   382                  match_condassert - this is an assertion condition

   383                  match_isgroup - this is the start of a bracketed group

   384 

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

   386                MATCH_NOMATCH if failed to match  )

   387                a negative PCRE_ERROR_xxx value if aborted by an error condition

   388                  (e.g. stopped by recursion limit)

   389 */

   390 

   391 static int

   392 match(REGISTER const pcre_uchar *eptr, REGISTER const uschar *ecode,

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

   394   int flags)

   395 {

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

   397 so they can be ordinary variables in all cases. Mark them with "register"

   398 because they are used a lot in loops. */

   399 

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

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

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

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

   404 

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

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

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

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

   409 

   410 #ifdef NO_RECURSE

   411 

   412 /* The value 16 here is large enough that most regular expressions don't require

   413 any calls to pcre_stack_malloc, yet the amount of stack used for the array is

   414 modest enough that we don't run out of stack. */

   415 heapframe stackframes[16];

   416 heapframe *stackframesend = stackframes + sizeof(stackframes) / sizeof(stackframes[0]);

   417 

   418 heapframe *frame = stackframes;

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

   420 

   421 /* Copy in the original argument variables */

   422 

   423 frame->Xeptr = eptr;

   424 frame->Xecode = ecode;

   425 frame->Xoffset_top = offset_top;

   426 frame->Xims = ims;

   427 frame->Xeptrb = eptrb;

   428 frame->Xflags = flags;

   429 

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

   431 

   432 HEAP_RECURSE:

   433 

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

   435 

   436 #define eptr               frame->Xeptr

   437 #define ecode              frame->Xecode

   438 #define offset_top         frame->Xoffset_top

   439 #define ims                frame->Xims

   440 #define eptrb              frame->Xeptrb

   441 #define flags              frame->Xflags

   442 

   443 /* Ditto for the local variables */

   444 

   445 #ifdef SUPPORT_UTF8

   446 #define charptr            frame->Xcharptr

   447 #endif

   448 #define callpat            frame->Xcallpat

   449 #define data               frame->Xdata

   450 #define next               frame->Xnext

   451 #define pp                 frame->Xpp

   452 #define prev               frame->Xprev

   453 #define saved_eptr         frame->Xsaved_eptr

   454 

   455 #define new_recursive      frame->Xnew_recursive

   456 

   457 #define cur_is_word        frame->Xcur_is_word

   458 #define condition          frame->Xcondition

   459 #define minimize           frame->Xminimize

   460 #define prev_is_word       frame->Xprev_is_word

   461 

   462 #define original_ims       frame->Xoriginal_ims

   463 

   464 #ifdef SUPPORT_UCP

   465 

   466 #define prop_type          frame->Xprop_type

   467 #define prop_fail_result   frame->Xprop_fail_result

   468 #define prop_category      frame->Xprop_category

   469 #define prop_chartype      frame->Xprop_chartype

   470 #define prop_othercase     frame->Xprop_othercase

   471 #define prop_test_against  frame->Xprop_test_against

   472 #define prop_test_variable frame->Xprop_test_variable

   473 

   474 #define repeat_othercase   frame->Xrepeat_othercase

   475 

   476 #endif

   477 

   478 #define ctype              frame->Xctype

   479 #define fc                 frame->Xfc

   480 #define fi                 frame->Xfi

   481 #define length             frame->Xlength

   482 #define max                frame->Xmax

   483 #define min                frame->Xmin

   484 #define number             frame->Xnumber

   485 #define offset             frame->Xoffset

   486 #define op                 frame->Xop

   487 #define save_capture_last  frame->Xsave_capture_last

   488 #define save_offset1       frame->Xsave_offset1

   489 #define save_offset2       frame->Xsave_offset2

   490 #define save_offset3       frame->Xsave_offset3

   491 #define stacksave          frame->Xstacksave

   492 

   493 #define newptrb            frame->Xnewptrb

   494 

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

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

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

   498 

   499 #else

   500 #define fi i

   501 #define fc c

   502 

   503 

   504 #if !PCRE_UTF16

   505 #ifdef SUPPORT_UTF8                /* Many of these variables are used ony */

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

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

   508 #endif

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

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

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

   512 const pcre_uchar *pp;              /* external "stack" implemented on the  */

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

   514 const pcre_uchar *saved_eptr;      /* all here, so the declarations can    */

   515                                    /* be cut out in a block. The only      */

   516 recursion_info new_recursive;      /* declarations within blocks below are */

   517                                    /* for variables that do not have to    */

   518 BOOL cur_is_word;                  /* be preserved over a recursive call   */

   519 BOOL condition;                    /* to RMATCH().                         */

   520 BOOL minimize;

   521 BOOL prev_is_word;

   522 

   523 unsigned long int original_ims;

   524 

   525 #ifdef SUPPORT_UCP

   526 

   527 int prop_type;

   528 int prop_fail_result;

   529 int prop_category;

   530 int prop_chartype;

   531 int prop_othercase;

   532 int prop_test_against;

   533 int *prop_test_variable;

   534 

   535 int repeat_othercase;

   536 

   537 #endif

   538 

   539 int ctype;

   540 int length;

   541 int max;

   542 int min;

   543 int number;

   544 int offset;

   545 int op;

   546 int save_capture_last;

   547 int save_offset1, save_offset2, save_offset3;

   548 int stacksave[REC_STACK_SAVE_MAX];

   549 

   550 eptrblock newptrb;

   551 #endif

   552 

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

   554 variables. */

   555 

   556 #ifdef SUPPORT_UCP

   557 prop_fail_result = 0;

   558 prop_test_against = 0;

   559 prop_test_variable = NULL;

   560 #endif

   561 

   562 /* OK, now we can get on with the real code of the function. Recursion is

   563 specified by the macros RMATCH and RRETURN. When NO_RECURSE is *not* defined,

   564 these just turn into a recursive call to match() and a "return", respectively.

   565 However, RMATCH isn't like a function call because it's quite a complicated

   566 macro. It has to be used in one particular way. This shouldn't, however, impact

   567 performance when true recursion is being used. */

   568 

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

   570 

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

   572 

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

   574 

   575 /* At the start of a bracketed group, add the current subject pointer to the

   576 stack of such pointers, to be re-instated at the end of the group when we hit

   577 the closing ket. When match() is called in other circumstances, we don't add to

   578 this stack. */

   579 

   580 if ((flags & match_isgroup) != 0)

   581   {

   582   newptrb.epb_prev = eptrb;

   583   newptrb.epb_saved_eptr = eptr;

   584   eptrb = &newptrb;

   585   }

   586 

   587 /* Now start processing the operations. */

   588 

   589 for (;;)

   590   {

   591   op = *ecode;

   592   minimize = FALSE;

   593 

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

   595   matching at least one subject character. */

   596 

   597   if (md->partial &&

   598       eptr >= md->end_subject &&

   599       eptr > md->start_match)

   600     md->hitend = TRUE;

   601 

   602   /* Opening capturing bracket. If there is space in the offset vector, save

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

   604   mustn't change the current values of the data slot, because they may be set

   605   from a previous iteration of this group, and be referred to by a reference

   606   inside the group.

   607 

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

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

   610   the same bracket.

   611 

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

   613   non-capturing bracket. Don't worry about setting the flag for the error case

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

   615 

   616   if (op > OP_BRA)

   617     {

   618     number = op - OP_BRA;

   619 

   620     /* For extended extraction brackets (large number), we have to fish out the

   621     number from a dummy opcode at the start. */

   622 

   623     if (number > EXTRACT_BASIC_MAX)

   624       number = GET2(ecode, 2+LINK_SIZE);

   625     offset = number << 1;

   626 

   627 #ifdef DEBUG

   628     printf("start bracket %d subject=", number);

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

   630     printf("\n");

   631 #endif

   632 

   633     if (offset < md->offset_max)

   634       {

   635       save_offset1 = md->offset_vector[offset];

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

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

   638       save_capture_last = md->capture_last;

   639 

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

   641       md->offset_vector[md->offset_end - number] = INT_CAST(eptr - md->start_subject);

   642 

   643       do

   644         {

   645         RMATCH(1, rrc, eptr, ecode + 1 + LINK_SIZE, offset_top, md, ims, eptrb,

   646           match_isgroup);

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

   648         md->capture_last = save_capture_last;

   649         ecode += GET(ecode, 1);

   650         }

   651       while (*ecode == OP_ALT);

   652 

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

   654 

   655       md->offset_vector[offset] = save_offset1;

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

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

   658 

   659       RRETURN(MATCH_NOMATCH);

   660       }

   661 

   662     /* Insufficient room for saving captured contents */

   663 

   664     else op = OP_BRA;

   665     }

   666 

   667   /* Other types of node can be handled by a switch */

   668 

   669   switch(op)

   670     {

   671     case OP_BRA:     /* Non-capturing bracket: optimized */

   672     DPRINTF(("start bracket 0\n"));

   673     do

   674       {

   675       RMATCH(2, rrc, eptr, ecode + 1 + LINK_SIZE, offset_top, md, ims, eptrb,

   676         match_isgroup);

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

   678       ecode += GET(ecode, 1);

   679       }

   680     while (*ecode == OP_ALT);

   681     DPRINTF(("bracket 0 failed\n"));

   682     RRETURN(MATCH_NOMATCH);

   683 

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

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

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

   687     exactly what going to the ket would do. */

   688 

   689     case OP_COND:

   690     if (ecode[LINK_SIZE+1] == OP_CREF) /* Condition extract or recurse test */

   691       {

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

   693       condition = (offset == CREF_RECURSE * 2)?

   694         (md->recursive != NULL) :

   695         (offset < offset_top && md->offset_vector[offset] >= 0);

   696       RMATCH(3, rrc, eptr, ecode + (condition?

   697         (LINK_SIZE + 4) : (LINK_SIZE + 1 + GET(ecode, 1))),

   698         offset_top, md, ims, eptrb, match_isgroup);

   699       RRETURN(rrc);

   700       }

   701 

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

   703     the final argument TRUE causes it to stop at the end of an assertion. */

   704 

   705     else

   706       {

   707       RMATCH(4, rrc, eptr, ecode + 1 + LINK_SIZE, offset_top, md, ims, NULL,

   708           match_condassert | match_isgroup);

   709       if (rrc == MATCH_MATCH)

   710         {

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

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

   713         }

   714       else if (rrc != MATCH_NOMATCH)

   715         {

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

   717         }

   718       else ecode += GET(ecode, 1);

   719       RMATCH(5, rrc, eptr, ecode + 1 + LINK_SIZE, offset_top, md, ims, eptrb,

   720         match_isgroup);

   721       RRETURN(rrc);

   722       }

   723     /* Control never reaches here */

   724 

   725     /* Skip over conditional reference or large extraction number data if

   726     encountered. */

   727 

   728     case OP_CREF:

   729     case OP_BRANUMBER:

   730     ecode += 3;

   731     break;

   732 

   733     /* End of the pattern. If we are in a recursion, we should restore the

   734     offsets appropriately and continue from after the call. */

   735 

   736     case OP_END:

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

   738       {

   739       recursion_info *rec = md->recursive;

   740       DPRINTF(("Hit the end in a (?0) recursion\n"));

   741       md->recursive = rec->prevrec;

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

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

   744       md->start_match = rec->save_start;

   745       ims = original_ims;

   746       ecode = rec->after_call;

   747       break;

   748       }

   749 

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

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

   752 

   753     if (md->notempty && eptr == md->start_match) RRETURN(MATCH_NOMATCH);

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

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

   756     RRETURN(MATCH_MATCH);

   757 

   758     /* Change option settings */

   759 

   760     case OP_OPT:

   761     ims = ecode[1];

   762     ecode += 2;

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

   764     break;

   765 

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

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

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

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

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

   771 

   772     case OP_ASSERT:

   773     case OP_ASSERTBACK:

   774     do

   775       {

   776       RMATCH(6, rrc, eptr, ecode + 1 + LINK_SIZE, offset_top, md, ims, NULL,

   777         match_isgroup);

   778       if (rrc == MATCH_MATCH) break;

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

   780       ecode += GET(ecode, 1);

   781       }

   782     while (*ecode == OP_ALT);

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

   784 

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

   786 

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

   788 

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

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

   791 

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

   793     ecode += 1 + LINK_SIZE;

   794     offset_top = md->end_offset_top;

   795     continue;

   796 

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

   798 

   799     case OP_ASSERT_NOT:

   800     case OP_ASSERTBACK_NOT:

   801     do

   802       {

   803       RMATCH(7, rrc, eptr, ecode + 1 + LINK_SIZE, offset_top, md, ims, NULL,

   804         match_isgroup);

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

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

   807       ecode += GET(ecode,1);

   808       }

   809     while (*ecode == OP_ALT);

   810 

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

   812 

   813     ecode += 1 + LINK_SIZE;

   814     continue;

   815 

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

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

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

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

   820 

   821     case OP_REVERSE:

   822 #ifdef SUPPORT_UTF8

   823     if (utf8)

   824       {

   825       c = GET(ecode,1);

   826       for (i = 0; i < c; i++)

   827         {

   828         eptr--;

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

   830         BACKCHAR(eptr)

   831         }

   832       }

   833     else

   834 #endif

   835 

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

   837 

   838       {

   839       eptr -= GET(ecode,1);

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

   841       }

   842 

   843     /* Skip to next op code */

   844 

   845     ecode += 1 + LINK_SIZE;

   846     break;

   847 

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

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

   850     function is able to force a failure. */

   851 

   852     case OP_CALLOUT:

   853     if (pcre_callout != NULL)

   854       {

   855       pcre_callout_block cb;

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

   857       cb.callout_number   = ecode[1];

   858       cb.offset_vector    = md->offset_vector;

   859       cb.subject          = (const pcre_char *)md->start_subject;

   860       cb.subject_length   = INT_CAST(md->end_subject - md->start_subject);

   861       cb.start_match      = INT_CAST(md->start_match - md->start_subject);

   862       cb.current_position = INT_CAST(eptr - md->start_subject);

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

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

   865       cb.capture_top      = offset_top/2;

   866       cb.capture_last     = md->capture_last;

   867       cb.callout_data     = md->callout_data;

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

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

   870       }

   871     ecode += 2 + 2*LINK_SIZE;

   872     break;

   873 

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

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

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

   877 

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

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

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

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

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

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

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

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

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

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

   888 

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

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

   891     for the original version of this logic. */

   892 

   893     case OP_RECURSE:

   894       {

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

   896       new_recursive.group_num = *callpat - OP_BRA;

   897 

   898       /* For extended extraction brackets (large number), we have to fish out

   899       the number from a dummy opcode at the start. */

   900 

   901       if (new_recursive.group_num > EXTRACT_BASIC_MAX)

   902         new_recursive.group_num = GET2(callpat, 2+LINK_SIZE);

   903 

   904       /* Add to "recursing stack" */

   905 

   906       new_recursive.prevrec = md->recursive;

   907       md->recursive = &new_recursive;

   908 

   909       /* Find where to continue from afterwards */

   910 

   911       ecode += 1 + LINK_SIZE;

   912       new_recursive.after_call = ecode;

   913 

   914       /* Now save the offset data. */

   915 

   916       new_recursive.saved_max = md->offset_end;

   917       if (new_recursive.saved_max <= REC_STACK_SAVE_MAX)

   918         new_recursive.offset_save = stacksave;

   919       else

   920         {

   921         new_recursive.offset_save =

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

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

   924         }

   925 

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

   927             new_recursive.saved_max * sizeof(int));

   928       new_recursive.save_start = md->start_match;

   929       md->start_match = eptr;

   930 

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

   932       restore the offset and recursion data. */

   933 

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

   935       do

   936         {

   937         RMATCH(8, rrc, eptr, callpat + 1 + LINK_SIZE, offset_top, md, ims,

   938             eptrb, match_isgroup);

   939         if (rrc == MATCH_MATCH)

   940           {

   941           md->recursive = new_recursive.prevrec;

   942           if (new_recursive.offset_save != stacksave)

   943             (pcre_free)(new_recursive.offset_save);

   944           RRETURN(MATCH_MATCH);

   945           }

   946         else if (rrc != MATCH_NOMATCH) RRETURN(rrc);

   947 

   948         md->recursive = &new_recursive;

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

   950             new_recursive.saved_max * sizeof(int));

   951         callpat += GET(callpat, 1);

   952         }

   953       while (*callpat == OP_ALT);

   954 

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

   956       md->recursive = new_recursive.prevrec;

   957       if (new_recursive.offset_save != stacksave)

   958         (pcre_free)(new_recursive.offset_save);

   959       RRETURN(MATCH_NOMATCH);

   960       }

   961     /* Control never reaches here */

   962 

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

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

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

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

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

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

   969 

   970     case OP_ONCE:

   971       {

   972       prev = ecode;

   973       saved_eptr = eptr;

   974 

   975       do

   976         {

   977         RMATCH(9, rrc, eptr, ecode + 1 + LINK_SIZE, offset_top, md, ims,

   978           eptrb, match_isgroup);

   979         if (rrc == MATCH_MATCH) break;

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

   981         ecode += GET(ecode,1);

   982         }

   983       while (*ecode == OP_ALT);

   984 

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

   986 

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

   988 

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

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

   991 

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

   993 

   994       offset_top = md->end_offset_top;

   995       eptr = md->end_match_ptr;

   996 

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

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

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

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

  1001       course of events. */

  1002 

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

  1004         {

  1005         ecode += 1+LINK_SIZE;

  1006         break;

  1007         }

  1008 

  1009       /* The repeating kets try the rest of the pattern or restart from the

  1010       preceding bracket, in the appropriate order. We need to reset any options

  1011       that changed within the bracket before re-running it, so check the next

  1012       opcode. */

  1013 

  1014       if (ecode[1+LINK_SIZE] == OP_OPT)

  1015         {

  1016         ims = (ims & ~PCRE_IMS) | ecode[4];

  1017         DPRINTF(("ims set to %02lx at group repeat\n", ims));

  1018         }

  1019 

  1020       if (*ecode == OP_KETRMIN)

  1021         {

  1022         RMATCH(10, rrc, eptr, ecode + 1 + LINK_SIZE, offset_top, md, ims, eptrb, 0);

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

  1024         RMATCH(11, rrc, eptr, prev, offset_top, md, ims, eptrb, match_isgroup);

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

  1026         }

  1027       else  /* OP_KETRMAX */

  1028         {

  1029         RMATCH(12, rrc, eptr, prev, offset_top, md, ims, eptrb, match_isgroup);

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

  1031         RMATCH(13, rrc, eptr, ecode + 1+LINK_SIZE, offset_top, md, ims, eptrb, 0);

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

  1033         }

  1034       }

  1035     RRETURN(MATCH_NOMATCH);

  1036 

  1037     /* An alternation is the end of a branch; scan along to find the end of the

  1038     bracketed group and go to there. */

  1039 

  1040     case OP_ALT:

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

  1042     break;

  1043 

  1044     /* BRAZERO and BRAMINZERO occur just before a bracket group, indicating

  1045     that it may occur zero times. It may repeat infinitely, or not at all -

  1046     i.e. it could be ()* or ()? in the pattern. Brackets with fixed upper

  1047     repeat limits are compiled as a number of copies, with the optional ones

  1048     preceded by BRAZERO or BRAMINZERO. */

  1049 

  1050     case OP_BRAZERO:

  1051       {

  1052       next = ecode+1;

  1053       RMATCH(14, rrc, eptr, next, offset_top, md, ims, eptrb, match_isgroup);

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

  1055       do next += GET(next,1); while (*next == OP_ALT);

  1056       ecode = next + 1+LINK_SIZE;

  1057       }

  1058     break;

  1059 

  1060     case OP_BRAMINZERO:

  1061       {

  1062       next = ecode+1;

  1063       do next += GET(next,1); while (*next == OP_ALT);

  1064       RMATCH(15, rrc, eptr, next + 1+LINK_SIZE, offset_top, md, ims, eptrb,

  1065         match_isgroup);

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

  1067       ecode++;

  1068       }

  1069     break;

  1070 

  1071     /* End of a group, repeated or non-repeating. If we are at the end of

  1072     an assertion "group", stop matching and return MATCH_MATCH, but record the

  1073     current high water mark for use by positive assertions. Do this also

  1074     for the "once" (not-backup up) groups. */

  1075 

  1076     case OP_KET:

  1077     case OP_KETRMIN:

  1078     case OP_KETRMAX:

  1079       {

  1080       prev = ecode - GET(ecode, 1);

  1081       saved_eptr = eptrb->epb_saved_eptr;

  1082 

  1083       /* Back up the stack of bracket start pointers. */

  1084 

  1085       eptrb = eptrb->epb_prev;

  1086 

  1087       if (*prev == OP_ASSERT || *prev == OP_ASSERT_NOT ||

  1088           *prev == OP_ASSERTBACK || *prev == OP_ASSERTBACK_NOT ||

  1089           *prev == OP_ONCE)

  1090         {

  1091         md->end_match_ptr = eptr;      /* For ONCE */

  1092         md->end_offset_top = offset_top;

  1093         RRETURN(MATCH_MATCH);

  1094         }

  1095 

  1096       /* In all other cases except a conditional group we have to check the

  1097       group number back at the start and if necessary complete handling an

  1098       extraction by setting the offsets and bumping the high water mark. */

  1099 

  1100       if (*prev != OP_COND)

  1101         {

  1102         number = *prev - OP_BRA;

  1103 

  1104         /* For extended extraction brackets (large number), we have to fish out

  1105         the number from a dummy opcode at the start. */

  1106 

  1107         if (number > EXTRACT_BASIC_MAX) number = GET2(prev, 2+LINK_SIZE);

  1108         offset = number << 1;

  1109 

  1110 #ifdef DEBUG

  1111         printf("end bracket %d", number);

  1112         printf("\n");

  1113 #endif

  1114 

  1115         /* Test for a numbered group. This includes groups called as a result

  1116         of recursion. Note that whole-pattern recursion is coded as a recurse

  1117         into group 0, so it won't be picked up here. Instead, we catch it when

  1118         the OP_END is reached. */

  1119 

  1120         if (number > 0)

  1121           {

  1122           md->capture_last = number;

  1123           if (offset >= md->offset_max) md->offset_overflow = TRUE; else

  1124             {

  1125             md->offset_vector[offset] =

  1126               md->offset_vector[md->offset_end - number];

  1127             md->offset_vector[offset+1] = INT_CAST(eptr - md->start_subject);

  1128             if (offset_top <= offset) offset_top = offset + 2;

  1129             }

  1130 

  1131           /* Handle a recursively called group. Restore the offsets

  1132           appropriately and continue from after the call. */

  1133 

  1134           if (md->recursive != NULL && md->recursive->group_num == number)