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

*      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-2008 University of Cambridge

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

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. */

#ifdef HAVE_CONFIG_H

#include "config.h"

#endif

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

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

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

#include "pcre_internal.h"

/* Undefine some potentially clashing cpp symbols */

#undef min

#undef max

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

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

#define match_cbegroup       0x02  /* Could-be-empty unlimited repeat 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

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

negative to avoid the external error codes. */

#define MATCH_COMMIT       (-999)

#define MATCH_PRUNE        (-998)

#define MATCH_SKIP         (-997)

#define MATCH_THEN         (-996)

/* 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 uschar *p, int length, BOOL is_subject, match_data *md)

{

unsigned 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); else printf("\\x%02x", c);

}

#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 USPTR eptr, int length, match_data *md,

  unsigned long int ims)

{

USPTR 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 caseless case for speed. In UTF-8 mode we can only do this

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

ASCII characters. */

if ((ims & PCRE_CASELESS) != 0)

  {

#ifdef SUPPORT_UTF8

#ifdef SUPPORT_UCP

  if (md->utf8)

    {

    USPTR endptr = eptr + length;

    while (eptr < endptr)

      {

      int c, d;

      GETCHARINC(c, eptr);

      GETCHARINC(d, p);

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

      }

    }

  else

#endif

#endif

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

  is no UCP support. */

  while (length-- > 0)

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

  }

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

are in UTF-8 mode. */

else

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

return TRUE;

}

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

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

                   RECURSION IN THE match() FUNCTION

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

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

it to recurse to a great depth. 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 some non-Unix-like 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.

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

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

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

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

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

them stand out more clearly.

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

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

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

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

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

variable instead of being passed in the frame.

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

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

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

below must be updated in sync.  */

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

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

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

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

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

       RM51,  RM52, RM53, RM54 };

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

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

actuall used in this definition. */

#ifndef NO_RECURSE

#define REGISTER register

#ifdef DEBUG

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

  { \

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

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

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

  }

#define RRETURN(ra) \

  { \

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

  return ra; \

  }

#else

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

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

#define RRETURN(ra) return ra

#endif

#else

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

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

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

#define REGISTER

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

  {\

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

  frame->Xwhere = rw; \

  newframe->Xeptr = ra;\

  newframe->Xecode = rb;\

  newframe->Xmstart = mstart;\

  newframe->Xoffset_top = rc;\

  newframe->Xims = re;\

  newframe->Xeptrb = rf;\

  newframe->Xflags = rg;\

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

  newframe->Xprevframe = frame;\

  frame = newframe;\

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

  goto HEAP_RECURSE;\

  L_##rw:\

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

  }

#define RRETURN(ra)\

  {\

  heapframe *newframe = frame;\

  frame = newframe->Xprevframe;\

  (pcre_stack_free)(newframe);\

  if (frame != NULL)\

    {\

    rrc = ra;\

    goto HEAP_RETURN;\

    }\

  return ra;\

  }

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

typedef struct heapframe {

  struct heapframe *Xprevframe;

  /* Function arguments that may change */

  const uschar *Xeptr;

  const uschar *Xecode;

  const uschar *Xmstart;

  int Xoffset_top;

  long int Xims;

  eptrblock *Xeptrb;

  int Xflags;

  unsigned int Xrdepth;

  /* Function local variables */

  const uschar *Xcallpat;

  const uschar *Xcharptr;

  const uschar *Xdata;

  const uschar *Xnext;

  const uschar *Xpp;

  const uschar *Xprev;

  const uschar *Xsaved_eptr;

  recursion_info Xnew_recursive;

  BOOL Xcur_is_word;

  BOOL Xcondition;

  BOOL Xprev_is_word;

  unsigned long int Xoriginal_ims;

#ifdef SUPPORT_UCP

  int Xprop_type;

  int Xprop_value;

  int Xprop_fail_result;

  int Xprop_category;

  int Xprop_chartype;

  int Xprop_script;

  int Xoclength;

  uschar Xocchars[8];

#endif

  int Xctype;

  unsigned 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;

  /* Where to jump back to */

  int Xwhere;

} heapframe;

#endif

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

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

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

*         Match from current position            *

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

/* 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 to current character in subject

   ecode       pointer to current position in compiled code

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

                 by encountering \K)

   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_cbegroup - this is the start of an unlimited repeat

                   group that can match an empty string

   rdepth      the recursion depth

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 repeated call or recursion limit)

*/

static int

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

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

  int flags, unsigned int rdepth)

{

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

so they can be ordinary variables in all cases. Mark some of 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 unsigned int c;   /* Character values not kept over RMATCH() calls */

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

BOOL minimize, possessive; /* Quantifier options */

/* 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

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

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

/* Copy in the original argument variables */

frame->Xeptr = eptr;

frame->Xecode = ecode;

frame->Xmstart = mstart;

frame->Xoffset_top = offset_top;

frame->Xims = ims;

frame->Xeptrb = eptrb;

frame->Xflags = flags;

frame->Xrdepth = rdepth;

/* 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 mstart             frame->Xmstart

#define offset_top         frame->Xoffset_top

#define ims                frame->Xims

#define eptrb              frame->Xeptrb

#define flags              frame->Xflags

#define rdepth             frame->Xrdepth

/* 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 prev_is_word       frame->Xprev_is_word

#define original_ims       frame->Xoriginal_ims

#ifdef SUPPORT_UCP

#define prop_type          frame->Xprop_type

#define prop_value         frame->Xprop_value

#define prop_fail_result   frame->Xprop_fail_result

#define prop_category      frame->Xprop_category

#define prop_chartype      frame->Xprop_chartype

#define prop_script        frame->Xprop_script

#define oclength           frame->Xoclength

#define occhars            frame->Xocchars

#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. */