/*************************************************

*      Perl-Compatible Regular Expressions       *

*************************************************/

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

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

                       Written by Philip Hazel

           Copyright (c) 1997-2005 University of Cambridge

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

-----------------------------------------------------------------------------

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

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

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

      this list of conditions and the following disclaimer.

    * Redistributions in binary form must reproduce the above copyright

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

      documentation and/or other materials provided with the distribution.

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

      contributors may be used to endorse or promote products derived from

      this software without specific prior written permission.

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

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

IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

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

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

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

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

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

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

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

POSSIBILITY OF SUCH DAMAGE.

-----------------------------------------------------------------------------

*/

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

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

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

#include "pcre_internal.h"

/* Avoid warnings on Windows. */

#undef min

#undef max

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

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

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

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

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

typedef struct eptrblock {

  struct eptrblock *epb_prev;

  const pcre_uchar *epb_saved_eptr;

} eptrblock;

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

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

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

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

defined PCRE_ERROR_xxx codes, which are all negative. */

#define MATCH_MATCH        1

#define MATCH_NOMATCH      0

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

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

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

#define REC_STACK_SAVE_MAX 30

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

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

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

#ifdef DEBUG

/*************************************************

*        Debugging function to print chars       *

*************************************************/

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

subject if the requested.

Arguments:

  p           points to characters

  length      number to print

  is_subject  TRUE if printing from within md->start_subject

  md          pointer to matching data block, if is_subject is TRUE

Returns:     nothing

*/

static void

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

{

int c;

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

while (length-- > 0)

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

#if PCRE_UTF16

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

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

#else

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

#endif

}

#endif

/*************************************************

*          Match a back-reference                *

*************************************************/

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

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

Arguments:

  offset      index into the offset vector

  eptr        points into the subject

  length      length to be matched

  md          points to match data block

  ims         the ims flags

Returns:      TRUE if matched

*/

static BOOL

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

  unsigned long int ims)

{

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

#ifdef DEBUG

if (eptr >= md->end_subject)

  printf("matching subject <null>");

else

  {

  printf("matching subject ");

  pchars(eptr, length, TRUE, md);

  }

printf(" against backref ");

pchars(p, length, FALSE, md);

printf("\n");

#endif

/* Always fail if not enough characters left */

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

/* Separate the caselesss case for speed */

if ((ims & PCRE_CASELESS) != 0)

  {

  while (length-- > 0)

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

  }

else

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

return TRUE;

}

/***************************************************************************

****************************************************************************

                   RECURSION IN THE match() FUNCTION

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

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

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

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

works fine.

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

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

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

for decades.) So....

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

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

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

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

always used to.

****************************************************************************

***************************************************************************/

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

#ifndef NO_RECURSE

#define REGISTER register

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

#define RRETURN(ra) return ra

#else

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

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

match(), which never changes. */

#define REGISTER

#ifndef __GNUC__

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

#define RMATCH_WHERE(num) num

#define RRETURN_LABEL RRETURN_SWITCH

#else

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

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

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

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

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

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

#define RRETURN_LABEL *frame->Xwhere

#endif

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

  {\

  heapframe *newframe;\

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

    newframe = frame + 1;\

  else\

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

  frame->Xwhere = RMATCH_WHERE(num);\

  newframe->Xeptr = ra;\

  newframe->Xecode = rb;\

  newframe->Xoffset_top = rc;\

  newframe->Xims = re;\

  newframe->Xeptrb = rf;\

  newframe->Xflags = rg;\

  newframe->Xprevframe = frame;\

  frame = newframe;\

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

  goto HEAP_RECURSE;\

RRETURN_##num:\

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

  frame = md->thisframe;\

  rx = frame->Xresult;\

  }

#define RRETURN(ra)\

  {\

  heapframe *newframe = frame;\

  frame = newframe->Xprevframe;\

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

    (pcre_stack_free)(newframe);\

  if (frame != NULL)\

    {\

    frame->Xresult = ra;\

    md->thisframe = frame;\

    goto RRETURN_LABEL;\

    }\

  return ra;\

  }

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

typedef struct heapframe {

  struct heapframe *Xprevframe;

  /* Function arguments that may change */

  const pcre_uchar *Xeptr;

  const uschar *Xecode;

  int Xoffset_top;

  long int Xims;

  eptrblock *Xeptrb;

  int Xflags;

  /* Function local variables */

  const uschar *Xcallpat;

  const uschar *Xcharptr;

  const uschar *Xdata;

  const uschar *Xnext;

  const pcre_uchar *Xpp;

  const uschar *Xprev;

  const pcre_uchar *Xsaved_eptr;

  recursion_info Xnew_recursive;

  BOOL Xcur_is_word;

  BOOL Xcondition;

  BOOL Xminimize;

  BOOL Xprev_is_word;

  unsigned long int Xoriginal_ims;

#ifdef SUPPORT_UCP

  int Xprop_type;

  int Xprop_fail_result;

  int Xprop_category;

  int Xprop_chartype;

  int Xprop_othercase;

  int Xprop_test_against;

  int *Xprop_test_variable;

  int Xrepeat_othercase;

#endif

  int Xctype;

  int Xfc;

  int Xfi;

  int Xlength;

  int Xmax;

  int Xmin;

  int Xnumber;

  int Xoffset;

  int Xop;

  int Xsave_capture_last;

  int Xsave_offset1, Xsave_offset2, Xsave_offset3;

  int Xstacksave[REC_STACK_SAVE_MAX];

  eptrblock Xnewptrb;

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

  int Xresult;

#ifndef __GNUC__

  int Xwhere;

#else

  void *Xwhere;

#endif

} heapframe;

#endif

/***************************************************************************

***************************************************************************/

/*************************************************

*         Match from current position            *

*************************************************/

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

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

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

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

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

same response.

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

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

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

made performance worse.

Arguments:

   eptr        pointer in subject

   ecode       position in code

   offset_top  current top pointer

   md          pointer to "static" info for the match

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

   eptrb       pointer to chain of blocks containing eptr at start of

                 brackets - for testing for empty matches

   flags       can contain

                 match_condassert - this is an assertion condition

                 match_isgroup - this is the start of a bracketed group

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

               MATCH_NOMATCH if failed to match  )

               a negative PCRE_ERROR_xxx value if aborted by an error condition

                 (e.g. stopped by recursion limit)

*/

static int

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

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

  int flags)

{

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

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

because they are used a lot in loops. */

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

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

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

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

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

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

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

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

#ifdef NO_RECURSE

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

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

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

heapframe stackframes[16];

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

heapframe *frame = stackframes;

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

/* Copy in the original argument variables */

frame->Xeptr = eptr;

frame->Xecode = ecode;

frame->Xoffset_top = offset_top;

frame->Xims = ims;

frame->Xeptrb = eptrb;

frame->Xflags = flags;

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

HEAP_RECURSE:

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

#define eptr               frame->Xeptr

#define ecode              frame->Xecode

#define offset_top         frame->Xoffset_top

#define ims                frame->Xims

#define eptrb              frame->Xeptrb

#define flags              frame->Xflags

/* Ditto for the local variables */

#ifdef SUPPORT_UTF8

#define charptr            frame->Xcharptr

#endif

#define callpat            frame->Xcallpat

#define data               frame->Xdata

#define next               frame->Xnext

#define pp                 frame->Xpp

#define prev               frame->Xprev

#define saved_eptr         frame->Xsaved_eptr

#define new_recursive      frame->Xnew_recursive

#define cur_is_word        frame->Xcur_is_word

#define condition          frame->Xcondition

#define minimize           frame->Xminimize

#define prev_is_word       frame->Xprev_is_word

#define original_ims       frame->Xoriginal_ims

#ifdef SUPPORT_UCP

#define prop_type          frame->Xprop_type

#define prop_fail_result   frame->Xprop_fail_result

#define prop_category      frame->Xprop_category

#define prop_chartype      frame->Xprop_chartype

#define prop_othercase     frame->Xprop_othercase

#define prop_test_against  frame->Xprop_test_against

#define prop_test_variable frame->Xprop_test_variable

#define repeat_othercase   frame->Xrepeat_othercase

#endif

#define ctype              frame->Xctype

#define fc                 frame->Xfc

#define fi                 frame->Xfi

#define length             frame->Xlength

#define max                frame->Xmax

#define min                frame->Xmin

#define number             frame->Xnumber

#define offset             frame->Xoffset

#define op                 frame->Xop

#define save_capture_last  frame->Xsave_capture_last

#define save_offset1       frame->Xsave_offset1

#define save_offset2       frame->Xsave_offset2

#define save_offset3       frame->Xsave_offset3

#define stacksave          frame->Xstacksave

#define newptrb            frame->Xnewptrb

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

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

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

#else

#define fi i

#define fc c

#if !PCRE_UTF16

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

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

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

#endif

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

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

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

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

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

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

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

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

                                   /* for variables that do not have to    */

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

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

BOOL minimize;

BOOL prev_is_word;

unsigned long int original_ims;

#ifdef SUPPORT_UCP

int prop_type;

int prop_fail_result;