/* This is JavaScriptCore's variant of the PCRE library. While this library

started out as a copy of PCRE, many of the features of PCRE have been

removed. This library now supports only the regular expression features

required by the JavaScript language specification, and has only the functions

needed by JavaScriptCore and the rest of WebKit.

                 Originally written by Philip Hazel

           Copyright (c) 1997-2006 University of Cambridge

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

    Copyright (C) 2007 Eric Seidel <eric@webkit.org>

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

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 the external function jsRegExpExecute(), along with

supporting internal functions that are not used by other modules. */

#include "config.h"

#include "pcre_internal.h"

#include <string.h>

#include <wtf/ASCIICType.h>

#include <wtf/FastMalloc.h>

#include <wtf/FixedArray.h>

using namespace WTF;

/* Negative values for the firstchar and reqchar variables */

#define REQ_UNSET (-2)

#define REQ_NONE  (-1)

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

*      Code parameters and static tables         *

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

/* Maximum number of items on the nested bracket stacks at compile time. This

applies to the nesting of all kinds of parentheses. It does not limit

un-nested, non-capturing parentheses. This number can be made bigger if

necessary - it is used to dimension one int and one unsigned char vector at

compile time. */

#define BRASTACK_SIZE 200

/* Table for handling escaped characters in the range '0'-'z'. Positive returns

are simple data values; negative values are for special things like \d and so

on. Zero means further processing is needed (for things like \x), or the escape

is invalid. */

static const short escapes[] = {

     0,      0,      0,      0,      0,      0,      0,      0,   /* 0 - 7 */

     0,      0,    ':',    ';',    '<',    '=',    '>',    '?',   /* 8 - ? */

   '@',      0, -ESC_B,      0, -ESC_D,      0,      0,      0,   /* @ - G */

     0,      0,      0,      0,      0,      0,      0,      0,   /* H - O */

     0,      0,      0, -ESC_S,      0,      0,      0, -ESC_W,   /* P - W */

     0,      0,      0,    '[',   '\\',    ']',    '^',    '_',   /* X - _ */

   '`',      7, -ESC_b,      0, -ESC_d,      0,   '\f',      0,   /* ` - g */

     0,      0,      0,      0,      0,      0,   '\n',      0,   /* h - o */

     0,      0,    '\r', -ESC_s,   '\t',      0,  '\v', -ESC_w,   /* p - w */

     0,      0,      0                                            /* x - z */

};

/* Error code numbers. They are given names so that they can more easily be

tracked. */

enum ErrorCode {

    ERR0, ERR1, ERR2, ERR3, ERR4, ERR5, ERR6, ERR7, ERR8, ERR9,

    ERR10, ERR11, ERR12, ERR13, ERR14, ERR15, ERR16, ERR17

};

/* The texts of compile-time error messages. These are "char *" because they

are passed to the outside world. */

static const char* errorText(ErrorCode code)

{

    static const char errorTexts[] =

      /* 1 */

      "\\ at end of pattern\0"

      "\\c at end of pattern\0"

      "character value in \\x{...} sequence is too large\0"

      "numbers out of order in {} quantifier\0"

      /* 5 */

      "number too big in {} quantifier\0"

      "missing terminating ] for character class\0"

      "internal error: code overflow\0"

      "range out of order in character class\0"

      "nothing to repeat\0"

      /* 10 */

      "unmatched parentheses\0"

      "internal error: unexpected repeat\0"

      "unrecognized character after (?\0"

      "failed to get memory\0"

      "missing )\0"

      /* 15 */

      "reference to non-existent subpattern\0"

      "regular expression too large\0"

      "parentheses nested too deeply"

    ;

    int i = code;

    const char* text = errorTexts;

    while (i > 1)

        i -= !*text++;

    return text;

}

/* Structure for passing "static" information around between the functions

doing the compiling. */

struct CompileData {

    CompileData() {

        topBackref = 0;

        backrefMap = 0;

        reqVaryOpt = 0;

        needOuterBracket = false;

        numCapturingBrackets = 0;

    }

    int topBackref;            /* Maximum back reference */

    unsigned backrefMap;       /* Bitmap of low back refs */

    int reqVaryOpt;            /* "After variable item" flag for reqByte */

    bool needOuterBracket;

    int numCapturingBrackets;

};

/* Definitions to allow mutual recursion */

static bool compileBracket(int, int*, unsigned char**, const UChar**, const UChar*, ErrorCode*, int, int*, int*, CompileData&);

static bool bracketIsAnchored(const unsigned char* code);

static bool bracketNeedsLineStart(const unsigned char* code, unsigned captureMap, unsigned backrefMap);

static int bracketFindFirstAssertedCharacter(const unsigned char* code, bool inassert);

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

*            Handle escapes                      *

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

/* This function is called when a \ has been encountered. It either returns a

positive value for a simple escape such as \n, or a negative value which

encodes one of the more complicated things such as \d. When UTF-8 is enabled,

a positive value greater than 255 may be returned. On entry, ptr is pointing at

the \. On exit, it is on the final character of the escape sequence.

Arguments:

  ptrPtr         points to the pattern position pointer

  errorCodePtr   points to the errorcode variable

  bracount       number of previous extracting brackets

  options        the options bits

  isClass        true if inside a character class

Returns:         zero or positive => a data character

                 negative => a special escape sequence

                 on error, errorPtr is set

*/

static int checkEscape(const UChar** ptrPtr, const UChar* patternEnd, ErrorCode* errorCodePtr, int bracount, bool isClass)

{

    const UChar* ptr = *ptrPtr + 1;

    /* If backslash is at the end of the pattern, it's an error. */

    if (ptr == patternEnd) {

        *errorCodePtr = ERR1;

        *ptrPtr = ptr;

        return 0;

    }

    int c = *ptr;

    /* Non-alphamerics are literals. For digits or letters, do an initial lookup in

     a table. A non-zero result is something that can be returned immediately.

     Otherwise further processing may be required. */

    if (c < '0' || c > 'z') { /* Not alphameric */

    } else if (int escapeValue = escapes[c - '0']) {

        c = escapeValue;

        if (isClass) {

            if (-c == ESC_b)

                c = '\b'; /* \b is backslash in a class */

            else if (-c == ESC_B)

                c = 'B'; /* and \B is a capital B in a class (in browsers event though ECMAScript 15.10.2.19 says it raises an error) */

        }

    /* Escapes that need further processing, or are illegal. */

    } else {

        switch (c) {

            case '1':

            case '2':

            case '3':

            case '4':

            case '5':

            case '6':

            case '7':

            case '8':

            case '9':

                /* Escape sequences starting with a non-zero digit are backreferences,

                 unless there are insufficient brackets, in which case they are octal

                 escape sequences. Those sequences end on the first non-octal character

                 or when we overflow 0-255, whichever comes first. */

                if (!isClass) {

                    const UChar* oldptr = ptr;

                    c -= '0';

                    while ((ptr + 1 < patternEnd) && isASCIIDigit(ptr[1]) && c <= bracount)

                        c = c * 10 + *(++ptr) - '0';

                    if (c <= bracount) {

                        c = -(ESC_REF + c);

                        break;

                    }

                    ptr = oldptr;      /* Put the pointer back and fall through */

                }

                /* Handle an octal number following \. If the first digit is 8 or 9,

                 this is not octal. */

                if ((c = *ptr) >= '8') {

                    c = '\\';

                    ptr -= 1;

                    break;

                }

            /* \0 always starts an octal number, but we may drop through to here with a

             larger first octal digit. */

            case '0': {

                c -= '0';

                int i;

                for (i = 1; i <= 2; ++i) {

                    if (ptr + i >= patternEnd || ptr[i] < '0' || ptr[i] > '7')

                        break;

                    int cc = c * 8 + ptr[i] - '0';

                    if (cc > 255)

                        break;

                    c = cc;

                }

                ptr += i - 1;

                break;

            }

            case 'x': {

                c = 0;

                int i;

                for (i = 1; i <= 2; ++i) {

                    if (ptr + i >= patternEnd || !isASCIIHexDigit(ptr[i])) {

                        c = 'x';

                        i = 1;

                        break;

                    }

                    int cc = ptr[i];

                    if (cc >= 'a')

                        cc -= 32;             /* Convert to upper case */

                    c = c * 16 + cc - ((cc < 'A') ? '0' : ('A' - 10));

                }

                ptr += i - 1;

                break;

            }

            case 'u': {

                c = 0;

                int i;

                for (i = 1; i <= 4; ++i) {

                    if (ptr + i >= patternEnd || !isASCIIHexDigit(ptr[i])) {

                        c = 'u';

                        i = 1;

                        break;

                    }

                    int cc = ptr[i];

                    if (cc >= 'a')

                        cc -= 32;             /* Convert to upper case */

                    c = c * 16 + cc - ((cc < 'A') ? '0' : ('A' - 10));

                }

                ptr += i - 1;

                break;

            }

            case 'c':

                if (++ptr == patternEnd) {

                    *errorCodePtr = ERR2;

                    return 0;

                }

                c = *ptr;

                /* To match Firefox, inside a character class, we also accept

                   numbers and '_' as control characters */

                if ((!isClass && !isASCIIAlpha(c)) || (!isASCIIAlphanumeric(c) && c != '_')) {

                    c = '\\';

                    ptr -= 2;

                    break;

                }

                /* A letter is upper-cased; then the 0x40 bit is flipped. This coding

                 is ASCII-specific, but then the whole concept of \cx is ASCII-specific. */

                c = toASCIIUpper(c) ^ 0x40;

                break;

            }

    }

    *ptrPtr = ptr;

    return c;

}

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

*            Check for counted repeat            *

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

/* This function is called when a '{' is encountered in a place where it might

start a quantifier. It looks ahead to see if it really is a quantifier or not.

It is only a quantifier if it is one of the forms {ddd} {ddd,} or {ddd,ddd}

where the ddds are digits.

Arguments:

  p         pointer to the first char after '{'

Returns:    true or false

*/

static bool isCountedRepeat(const UChar* p, const UChar* patternEnd)

{

    if (p >= patternEnd || !isASCIIDigit(*p))

        return false;

    p++;

    while (p < patternEnd && isASCIIDigit(*p))

        p++;

    if (p < patternEnd && *p == '}')

        return true;

    if (p >= patternEnd || *p++ != ',')

        return false;

    if (p < patternEnd && *p == '}')

        return true;

    if (p >= patternEnd || !isASCIIDigit(*p))

        return false;

    p++;

    while (p < patternEnd && isASCIIDigit(*p))

        p++;

    return (p < patternEnd && *p == '}');

}

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

*         Read repeat counts                     *

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

/* Read an item of the form {n,m} and return the values. This is called only

after isCountedRepeat() has confirmed that a repeat-count quantifier exists,

so the syntax is guaranteed to be correct, but we need to check the values.

Arguments:

  p              pointer to first char after '{'

  minp           pointer to int for min

  maxp           pointer to int for max

                 returned as -1 if no max

  errorCodePtr   points to error code variable

Returns:         pointer to '}' on success;

                 current ptr on error, with errorCodePtr set non-zero

*/

static const UChar* readRepeatCounts(const UChar* p, int* minp, int* maxp, ErrorCode* errorCodePtr)

{

    int min = 0;

    int max = -1;

    /* Read the minimum value and do a paranoid check: a negative value indicates

     an integer overflow. */

    while (isASCIIDigit(*p))

        min = min * 10 + *p++ - '0';

    if (min < 0 || min > 65535) {

        *errorCodePtr = ERR5;

        return p;

    }

    /* Read the maximum value if there is one, and again do a paranoid on its size.

     Also, max must not be less than min. */

    if (*p == '}')

        max = min;

    else {

        if (*(++p) != '}') {

            max = 0;

            while (isASCIIDigit(*p))

                max = max * 10 + *p++ - '0';

            if (max < 0 || max > 65535) {

                *errorCodePtr = ERR5;

                return p;

            }

            if (max < min) {

                *errorCodePtr = ERR4;

                return p;

            }

        }

    }

    /* Fill in the required variables, and pass back the pointer to the terminating

     '}'. */

    *minp = min;

    *maxp = max;

    return p;

}

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

*      Find first significant op code            *

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

/* This is called by several functions that scan a compiled expression looking

for a fixed first character, or an anchoring op code etc. It skips over things

that do not influence this.

Arguments:

  code         pointer to the start of the group

Returns:       pointer to the first significant opcode

*/

static const unsigned char* firstSignificantOpcode(const unsigned char* code)

{

    while (*code == OP_BRANUMBER)

        code += 3;

    return code;

}

static const unsigned char* firstSignificantOpcodeSkippingAssertions(const unsigned char* code)

{

    while (true) {

        switch (*code) {

            case OP_ASSERT_NOT:

                advanceToEndOfBracket(code);

                code += 1 + LINK_SIZE;

                break;

            case OP_WORD_BOUNDARY:

            case OP_NOT_WORD_BOUNDARY:

                ++code;

                break;

            case OP_BRANUMBER:

                code += 3;

                break;

            default:

                return code;

        }

    }

}

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

*           Get othercase range                  *

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

/* This function is passed the start and end of a class range, in UTF-8 mode

with UCP support. It searches up the characters, looking for internal ranges of

characters in the "other" case. Each call returns the next one, updating the

start address.

Arguments:

  cptr        points to starting character value; updated

  d           end value

  ocptr       where to put start of othercase range

  odptr       where to put end of othercase range

Yield:        true when range returned; false when no more

*/

static bool getOthercaseRange(int* cptr, int d, int* ocptr, int* odptr)

{

    int c, othercase = 0;

    for (c = *cptr; c <= d; c++) {

        if ((othercase = jsc_pcre_ucp_othercase(c)) >= 0)

            break;

    }

    if (c > d)

        return false;

    *ocptr = othercase;

    int next = othercase + 1;

    for (++c; c <= d; c++) {

        if (jsc_pcre_ucp_othercase(c) != next)

            break;

        next++;

    }

    *odptr = next - 1;

    *cptr = c;

    return true;

}

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

 *       Convert character value to UTF-8         *

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

/* This function takes an integer value in the range 0 - 0x7fffffff

 and encodes it as a UTF-8 character in 0 to 6 bytes.

 Arguments:

 cvalue     the character value

 buffer     pointer to buffer for result - at least 6 bytes long

 Returns:     number of characters placed in the buffer

 */

static int encodeUTF8(int cvalue, unsigned char *buffer)