JavaScriptCore-584.tar.gz

[apple/javascriptcore.git] / pcre / pcre_internal.h

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

-----------------------------------------------------------------------------
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 header contains definitions that are shared between the different
modules, but which are not relevant to the exported API. This includes some
functions whose names all begin with "_pcre_". */

#ifndef PCRE_INTERNAL_H
#define PCRE_INTERNAL_H

/* Bit definitions for entries in the pcre_ctypes table. */

#define ctype_space   0x01
#define ctype_xdigit  0x08
#define ctype_word    0x10   /* alphameric or '_' */

/* Offsets for the bitmap tables in pcre_cbits. Each table contains a set
of bits for a class map. Some classes are built by combining these tables. */

#define cbit_space     0      /* \s */
#define cbit_digit    32      /* \d */
#define cbit_word     64      /* \w */
#define cbit_length   96      /* Length of the cbits table */

/* Offsets of the various tables from the base tables pointer, and
total length. */

#define lcc_offset      0
#define fcc_offset    128
#define cbits_offset  256
#define ctypes_offset (cbits_offset + cbit_length)
#define tables_length (ctypes_offset + 128)

#ifndef DFTABLES

// Change the following to 1 to dump used regular expressions at process exit time.
#define REGEXP_HISTOGRAM 0

#include "Assertions.h"

#if COMPILER(MSVC)
#pragma warning(disable: 4232)
#pragma warning(disable: 4244)
#endif

#include "pcre.h"

/* The value of LINK_SIZE determines the number of bytes used to store links as
offsets within the compiled regex. The default is 2, which allows for compiled
patterns up to 64K long. */

#define LINK_SIZE   3

/* Define DEBUG to get debugging output on stdout. */

#if 0
#define DEBUG
#endif

/* Use a macro for debugging printing, 'cause that eliminates the use of #ifdef
inline, and there are *still* stupid compilers about that don't like indented
pre-processor statements, or at least there were when I first wrote this. After
all, it had only been about 10 years then... */

#ifdef DEBUG
#define DPRINTF(p) printf p
#else
#define DPRINTF(p) /*nothing*/
#endif

/* PCRE keeps offsets in its compiled code as 2-byte quantities (always stored
in big-endian order) by default. These are used, for example, to link from the
start of a subpattern to its alternatives and its end. The use of 2 bytes per
offset limits the size of the compiled regex to around 64K, which is big enough
for almost everybody. However, I received a request for an even bigger limit.
For this reason, and also to make the code easier to maintain, the storing and
loading of offsets from the byte string is now handled by the functions that are
defined here. */

/* PCRE uses some other 2-byte quantities that do not change when the size of
offsets changes. There are used for repeat counts and for other things such as
capturing parenthesis numbers in back references. */

static inline void put2ByteValue(unsigned char* opcodePtr, int value)
{
    ASSERT(value >= 0 && value <= 0xFFFF);
    opcodePtr[0] = value >> 8;
    opcodePtr[1] = value;
}

static inline void put3ByteValue(unsigned char* opcodePtr, int value)
{
    ASSERT(value >= 0 && value <= 0xFFFFFF);
    opcodePtr[0] = value >> 16;
    opcodePtr[1] = value >> 8;
    opcodePtr[2] = value;
}

static inline int get2ByteValue(const unsigned char* opcodePtr)
{
    return (opcodePtr[0] << 8) | opcodePtr[1];
}

static inline int get3ByteValue(const unsigned char* opcodePtr)
{
    return (opcodePtr[0] << 16) | (opcodePtr[1] << 8) | opcodePtr[2];
}

static inline void put2ByteValueAndAdvance(unsigned char*& opcodePtr, int value)
{
    put2ByteValue(opcodePtr, value);
    opcodePtr += 2;
}

static inline void put3ByteValueAndAdvance(unsigned char*& opcodePtr, int value)
{
    put3ByteValue(opcodePtr, value);
    opcodePtr += 3;
}

static inline void putLinkValueAllowZero(unsigned char* opcodePtr, int value)
{
#if LINK_SIZE == 3
    put3ByteValue(opcodePtr, value);
#elif LINK_SIZE == 2
    put2ByteValue(opcodePtr, value);
#else
#   error LINK_SIZE not supported.
#endif
}

static inline int getLinkValueAllowZero(const unsigned char* opcodePtr)
{
#if LINK_SIZE == 3
    return get3ByteValue(opcodePtr);
#elif LINK_SIZE == 2
    return get2ByteValue(opcodePtr);
#else
#   error LINK_SIZE not supported.
#endif
}

#define MAX_PATTERN_SIZE 1024 * 1024 // Derived by empirical testing of compile time in PCRE and WREC.
COMPILE_ASSERT(MAX_PATTERN_SIZE < (1 << (8 * LINK_SIZE)), pcre_max_pattern_fits_in_bytecode);

static inline void putLinkValue(unsigned char* opcodePtr, int value)
{
    ASSERT(value);
    putLinkValueAllowZero(opcodePtr, value);
}

static inline int getLinkValue(const unsigned char* opcodePtr)
{
    int value = getLinkValueAllowZero(opcodePtr);
    ASSERT(value);
    return value;
}

static inline void putLinkValueAndAdvance(unsigned char*& opcodePtr, int value)
{
    putLinkValue(opcodePtr, value);
    opcodePtr += LINK_SIZE;
}

static inline void putLinkValueAllowZeroAndAdvance(unsigned char*& opcodePtr, int value)
{
    putLinkValueAllowZero(opcodePtr, value);
    opcodePtr += LINK_SIZE;
}

// FIXME: These are really more of a "compiled regexp state" than "regexp options"
enum RegExpOptions {
    UseFirstByteOptimizationOption = 0x40000000,  /* firstByte is set */
    UseRequiredByteOptimizationOption = 0x20000000,  /* reqByte is set */
    UseMultiLineFirstByteOptimizationOption = 0x10000000,  /* start after \n for multiline */
    IsAnchoredOption = 0x02000000,  /* can't use partial with this regex */
    IgnoreCaseOption = 0x00000001,
    MatchAcrossMultipleLinesOption = 0x00000002
};

/* Flags added to firstByte or reqByte; a "non-literal" item is either a
variable-length repeat, or a anything other than literal characters. */

#define REQ_IGNORE_CASE 0x0100    /* indicates should ignore case */
#define REQ_VARY     0x0200    /* reqByte followed non-literal item */

/* Miscellaneous definitions */

/* Flag bits and data types for the extended class (OP_XCLASS) for classes that
contain UTF-8 characters with values greater than 255. */

#define XCL_NOT    0x01    /* Flag: this is a negative class */
#define XCL_MAP    0x02    /* Flag: a 32-byte map is present */

#define XCL_END       0    /* Marks end of individual items */
#define XCL_SINGLE    1    /* Single item (one multibyte char) follows */
#define XCL_RANGE     2    /* A range (two multibyte chars) follows */

/* These are escaped items that aren't just an encoding of a particular data
value such as \n. They must have non-zero values, as check_escape() returns
their negation. Also, they must appear in the same order as in the opcode
definitions below, up to ESC_w. The final one must be
ESC_REF as subsequent values are used for \1, \2, \3, etc. There is are two
tests in the code for an escape > ESC_b and <= ESC_w to
detect the types that may be repeated. These are the types that consume
characters. If any new escapes are put in between that don't consume a
character, that code will have to change. */

enum { ESC_B = 1, ESC_b, ESC_D, ESC_d, ESC_S, ESC_s, ESC_W, ESC_w, ESC_REF };

/* Opcode table: OP_BRA must be last, as all values >= it are used for brackets
that extract substrings. Starting from 1 (i.e. after OP_END), the values up to
OP_EOD must correspond in order to the list of escapes immediately above.
Note that whenever this list is updated, the two macro definitions that follow
must also be updated to match. */

#define FOR_EACH_OPCODE(macro) \
    macro(END) \
    \
    macro(NOT_WORD_BOUNDARY) \
    macro(WORD_BOUNDARY) \
    macro(NOT_DIGIT) \
    macro(DIGIT) \
    macro(NOT_WHITESPACE) \
    macro(WHITESPACE) \
    macro(NOT_WORDCHAR) \
    macro(WORDCHAR) \
    \
    macro(NOT_NEWLINE) \
    \
    macro(CIRC) \
    macro(DOLL) \
    macro(BOL) \
    macro(EOL) \
    macro(CHAR) \
    macro(CHAR_IGNORING_CASE) \
    macro(ASCII_CHAR) \
    macro(ASCII_LETTER_IGNORING_CASE) \
    macro(NOT) \
    \
    macro(STAR) \
    macro(MINSTAR) \
    macro(PLUS) \
    macro(MINPLUS) \
    macro(QUERY) \
    macro(MINQUERY) \
    macro(UPTO) \
    macro(MINUPTO) \
    macro(EXACT) \
    \
    macro(NOTSTAR) \
    macro(NOTMINSTAR) \
    macro(NOTPLUS) \
    macro(NOTMINPLUS) \
    macro(NOTQUERY) \
    macro(NOTMINQUERY) \
    macro(NOTUPTO) \
    macro(NOTMINUPTO) \
    macro(NOTEXACT) \
    \
    macro(TYPESTAR) \
    macro(TYPEMINSTAR) \
    macro(TYPEPLUS) \
    macro(TYPEMINPLUS) \
    macro(TYPEQUERY) \
    macro(TYPEMINQUERY) \
    macro(TYPEUPTO) \
    macro(TYPEMINUPTO) \
    macro(TYPEEXACT) \
    \
    macro(CRSTAR) \
    macro(CRMINSTAR) \
    macro(CRPLUS) \
    macro(CRMINPLUS) \
    macro(CRQUERY) \
    macro(CRMINQUERY) \
    macro(CRRANGE) \
    macro(CRMINRANGE) \
    \
    macro(CLASS) \
    macro(NCLASS) \
    macro(XCLASS) \
    \
    macro(REF) \
    \
    macro(ALT) \
    macro(KET) \
    macro(KETRMAX) \
    macro(KETRMIN) \
    \
    macro(ASSERT) \
    macro(ASSERT_NOT) \
    \
    macro(BRAZERO) \
    macro(BRAMINZERO) \
    macro(BRANUMBER) \
    macro(BRA)

#define OPCODE_ENUM_VALUE(opcode) OP_##opcode,
enum { FOR_EACH_OPCODE(OPCODE_ENUM_VALUE) };

/* WARNING WARNING WARNING: There is an implicit assumption in pcre.c and
study.c that all opcodes are less than 128 in value. This makes handling UTF-8
character sequences easier. */

/* The highest extraction number before we have to start using additional
bytes. (Originally PCRE didn't have support for extraction counts higher than
this number.) The value is limited by the number of opcodes left after OP_BRA,
i.e. 255 - OP_BRA. We actually set it a bit lower to leave room for additional
opcodes. */

/* FIXME: Note that OP_BRA + 100 is > 128, so the two comments above
are in conflict! */

#define EXTRACT_BASIC_MAX  100

/* The code vector runs on as long as necessary after the end. */

struct JSRegExp {
    unsigned options;

    unsigned short topBracket;
    unsigned short topBackref;
    
    unsigned short firstByte;
    unsigned short reqByte;

#if REGEXP_HISTOGRAM
    size_t stringOffset;
    size_t stringLength;
#endif
};

/* Internal shared data tables. These are tables that are used by more than one
 of the exported public functions. They have to be "external" in the C sense,
 but are not part of the PCRE public API. The data for these tables is in the
 pcre_tables.c module. */

#define jsc_pcre_utf8_table1_size 6

extern const int    jsc_pcre_utf8_table1[6];
extern const int    jsc_pcre_utf8_table2[6];
extern const int    jsc_pcre_utf8_table3[6];
extern const unsigned char jsc_pcre_utf8_table4[0x40];

extern const unsigned char jsc_pcre_default_tables[tables_length];

static inline unsigned char toLowerCase(unsigned char c)
{
    static const unsigned char* lowerCaseChars = jsc_pcre_default_tables + lcc_offset;
    return lowerCaseChars[c];
}

static inline unsigned char flipCase(unsigned char c)
{
    static const unsigned char* flippedCaseChars = jsc_pcre_default_tables + fcc_offset;
    return flippedCaseChars[c];
}

static inline unsigned char classBitmapForChar(unsigned char c)
{
    static const unsigned char* charClassBitmaps = jsc_pcre_default_tables + cbits_offset;
    return charClassBitmaps[c];
}

static inline unsigned char charTypeForChar(unsigned char c)
{
    const unsigned char* charTypeMap = jsc_pcre_default_tables + ctypes_offset;
    return charTypeMap[c];
}

static inline bool isWordChar(UChar c)
{
    return c < 128 && (charTypeForChar(c) & ctype_word);
}

static inline bool isSpaceChar(UChar c)
{
    return (c < 128 && (charTypeForChar(c) & ctype_space)) || c == 0x00A0;
}

static inline bool isNewline(UChar nl)
{
    return (nl == 0xA || nl == 0xD || nl == 0x2028 || nl == 0x2029);
}

static inline bool isBracketStartOpcode(unsigned char opcode)
{
    if (opcode >= OP_BRA)
        return true;
    switch (opcode) {
        case OP_ASSERT:
        case OP_ASSERT_NOT:
            return true;
        default:
            return false;
    }
}

static inline void advanceToEndOfBracket(const unsigned char*& opcodePtr)
{
    ASSERT(isBracketStartOpcode(*opcodePtr) || *opcodePtr == OP_ALT);
    do
        opcodePtr += getLinkValue(opcodePtr + 1);
    while (*opcodePtr == OP_ALT);
}

/* Internal shared functions. These are functions that are used in more
that one of the source files. They have to have external linkage, but
but are not part of the public API and so not exported from the library. */

extern int jsc_pcre_ucp_othercase(unsigned);
extern bool jsc_pcre_xclass(int, const unsigned char*);

#endif

#endif

/* End of pcre_internal.h */