JavaScriptCore/pcre/pcre_internal.h

   1 /* This is JavaScriptCore's variant of the PCRE library. While this library
   2 started out as a copy of PCRE, many of the features of PCRE have been
   3 removed. This library now supports only the regular expression features
   4 required by the JavaScript language specification, and has only the functions
   5 needed by JavaScriptCore and the rest of WebKit.
   6
   7                  Originally written by Philip Hazel
   8            Copyright (c) 1997-2006 University of Cambridge
   9     Copyright (C) 2002, 2004, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
  10
  11 -----------------------------------------------------------------------------
  12 Redistribution and use in source and binary forms, with or without
  13 modification, are permitted provided that the following conditions are met:
  14
  15     * Redistributions of source code must retain the above copyright notice,
  16       this list of conditions and the following disclaimer.
  17
  18     * Redistributions in binary form must reproduce the above copyright
  19       notice, this list of conditions and the following disclaimer in the
  20       documentation and/or other materials provided with the distribution.
  21
  22     * Neither the name of the University of Cambridge nor the names of its
  23       contributors may be used to endorse or promote products derived from
  24       this software without specific prior written permission.
  25
  26 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  27 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  30 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  31 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  32 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  33 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  34 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  35 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  36 POSSIBILITY OF SUCH DAMAGE.
  37 -----------------------------------------------------------------------------
  38 */
  39
  40 /* This header contains definitions that are shared between the different
  41 modules, but which are not relevant to the exported API. This includes some
  42 functions whose names all begin with "_pcre_". */
  43
  44 #ifndef PCRE_INTERNAL_H
  45 #define PCRE_INTERNAL_H
  46
  47 /* Bit definitions for entries in the pcre_ctypes table. */
  48
  49 #define ctype_space   0x01
  50 #define ctype_xdigit  0x08
  51 #define ctype_word    0x10   /* alphameric or '_' */
  52
  53 /* Offsets for the bitmap tables in pcre_cbits. Each table contains a set
  54 of bits for a class map. Some classes are built by combining these tables. */
  55
  56 #define cbit_space     0      /* \s */
  57 #define cbit_digit    32      /* \d */
  58 #define cbit_word     64      /* \w */
  59 #define cbit_length   96      /* Length of the cbits table */
  60
  61 /* Offsets of the various tables from the base tables pointer, and
  62 total length. */
  63
  64 #define lcc_offset      0
  65 #define fcc_offset    128
  66 #define cbits_offset  256
  67 #define ctypes_offset (cbits_offset + cbit_length)
  68 #define tables_length (ctypes_offset + 128)
  69
  70 #ifndef DFTABLES
  71
  72 // Change the following to 1 to dump used regular expressions at process exit time.
  73 #define REGEXP_HISTOGRAM 0
  74
  75 #include "Assertions.h"
  76
  77 #if COMPILER(MSVC)
  78 #pragma warning(disable: 4232)
  79 #pragma warning(disable: 4244)
  80 #endif
  81
  82 #include "pcre.h"
  83
  84 /* The value of LINK_SIZE determines the number of bytes used to store links as
  85 offsets within the compiled regex. The default is 2, which allows for compiled
  86 patterns up to 64K long. */
  87
  88 #define LINK_SIZE   3
  89
  90 /* Define DEBUG to get debugging output on stdout. */
  91
  92 #if 0
  93 #define DEBUG
  94 #endif
  95
  96 /* Use a macro for debugging printing, 'cause that eliminates the use of #ifdef
  97 inline, and there are *still* stupid compilers about that don't like indented
  98 pre-processor statements, or at least there were when I first wrote this. After
  99 all, it had only been about 10 years then... */
 100
 101 #ifdef DEBUG
 102 #define DPRINTF(p) printf p
 103 #else
 104 #define DPRINTF(p) /*nothing*/
 105 #endif
 106
 107 /* PCRE keeps offsets in its compiled code as 2-byte quantities (always stored
 108 in big-endian order) by default. These are used, for example, to link from the
 109 start of a subpattern to its alternatives and its end. The use of 2 bytes per
 110 offset limits the size of the compiled regex to around 64K, which is big enough
 111 for almost everybody. However, I received a request for an even bigger limit.
 112 For this reason, and also to make the code easier to maintain, the storing and
 113 loading of offsets from the byte string is now handled by the functions that are
 114 defined here. */
 115
 116 /* PCRE uses some other 2-byte quantities that do not change when the size of
 117 offsets changes. There are used for repeat counts and for other things such as
 118 capturing parenthesis numbers in back references. */
 119
 120 static inline void put2ByteValue(unsigned char* opcodePtr, int value)
 121 {
 122     ASSERT(value >= 0 && value <= 0xFFFF);
 123     opcodePtr[0] = value >> 8;
 124     opcodePtr[1] = value;
 125 }
 126
 127 static inline void put3ByteValue(unsigned char* opcodePtr, int value)
 128 {
 129     ASSERT(value >= 0 && value <= 0xFFFFFF);
 130     opcodePtr[0] = value >> 16;
 131     opcodePtr[1] = value >> 8;
 132     opcodePtr[2] = value;
 133 }
 134
 135 static inline int get2ByteValue(const unsigned char* opcodePtr)
 136 {
 137     return (opcodePtr[0] << 8) | opcodePtr[1];
 138 }
 139
 140 static inline int get3ByteValue(const unsigned char* opcodePtr)
 141 {
 142     return (opcodePtr[0] << 16) | (opcodePtr[1] << 8) | opcodePtr[2];
 143 }
 144
 145 static inline void put2ByteValueAndAdvance(unsigned char*& opcodePtr, int value)
 146 {
 147     put2ByteValue(opcodePtr, value);
 148     opcodePtr += 2;
 149 }
 150
 151 static inline void put3ByteValueAndAdvance(unsigned char*& opcodePtr, int value)
 152 {
 153     put3ByteValue(opcodePtr, value);
 154     opcodePtr += 3;
 155 }
 156
 157 static inline void putLinkValueAllowZero(unsigned char* opcodePtr, int value)
 158 {
 159 #if LINK_SIZE == 3
 160     put3ByteValue(opcodePtr, value);
 161 #elif LINK_SIZE == 2
 162     put2ByteValue(opcodePtr, value);
 163 #else
 164 #   error LINK_SIZE not supported.
 165 #endif
 166 }
 167
 168 static inline int getLinkValueAllowZero(const unsigned char* opcodePtr)
 169 {
 170 #if LINK_SIZE == 3
 171     return get3ByteValue(opcodePtr);
 172 #elif LINK_SIZE == 2
 173     return get2ByteValue(opcodePtr);
 174 #else
 175 #   error LINK_SIZE not supported.
 176 #endif
 177 }
 178
 179 #define MAX_PATTERN_SIZE 1024 * 1024 // Derived by empirical testing of compile time in PCRE and WREC.
 180 COMPILE_ASSERT(MAX_PATTERN_SIZE < (1 << (8 * LINK_SIZE)), pcre_max_pattern_fits_in_bytecode);
 181
 182 static inline void putLinkValue(unsigned char* opcodePtr, int value)
 183 {
 184     ASSERT(value);
 185     putLinkValueAllowZero(opcodePtr, value);
 186 }
 187
 188 static inline int getLinkValue(const unsigned char* opcodePtr)
 189 {
 190     int value = getLinkValueAllowZero(opcodePtr);
 191     ASSERT(value);
 192     return value;
 193 }
 194
 195 static inline void putLinkValueAndAdvance(unsigned char*& opcodePtr, int value)
 196 {
 197     putLinkValue(opcodePtr, value);
 198     opcodePtr += LINK_SIZE;
 199 }
 200
 201 static inline void putLinkValueAllowZeroAndAdvance(unsigned char*& opcodePtr, int value)
 202 {
 203     putLinkValueAllowZero(opcodePtr, value);
 204     opcodePtr += LINK_SIZE;
 205 }
 206
 207 // FIXME: These are really more of a "compiled regexp state" than "regexp options"
 208 enum RegExpOptions {
 209     UseFirstByteOptimizationOption = 0x40000000,  /* firstByte is set */
 210     UseRequiredByteOptimizationOption = 0x20000000,  /* reqByte is set */
 211     UseMultiLineFirstByteOptimizationOption = 0x10000000,  /* start after \n for multiline */
 212     IsAnchoredOption = 0x02000000,  /* can't use partial with this regex */
 213     IgnoreCaseOption = 0x00000001,
 214     MatchAcrossMultipleLinesOption = 0x00000002
 215 };
 216
 217 /* Flags added to firstByte or reqByte; a "non-literal" item is either a
 218 variable-length repeat, or a anything other than literal characters. */
 219
 220 #define REQ_IGNORE_CASE 0x0100    /* indicates should ignore case */
 221 #define REQ_VARY     0x0200    /* reqByte followed non-literal item */
 222
 223 /* Miscellaneous definitions */
 224
 225 /* Flag bits and data types for the extended class (OP_XCLASS) for classes that
 226 contain UTF-8 characters with values greater than 255. */
 227
 228 #define XCL_NOT    0x01    /* Flag: this is a negative class */
 229 #define XCL_MAP    0x02    /* Flag: a 32-byte map is present */
 230
 231 #define XCL_END       0    /* Marks end of individual items */
 232 #define XCL_SINGLE    1    /* Single item (one multibyte char) follows */
 233 #define XCL_RANGE     2    /* A range (two multibyte chars) follows */
 234
 235 /* These are escaped items that aren't just an encoding of a particular data
 236 value such as \n. They must have non-zero values, as check_escape() returns
 237 their negation. Also, they must appear in the same order as in the opcode
 238 definitions below, up to ESC_w. The final one must be
 239 ESC_REF as subsequent values are used for \1, \2, \3, etc. There is are two
 240 tests in the code for an escape > ESC_b and <= ESC_w to
 241 detect the types that may be repeated. These are the types that consume
 242 characters. If any new escapes are put in between that don't consume a
 243 character, that code will have to change. */
 244
 245 enum { ESC_B = 1, ESC_b, ESC_D, ESC_d, ESC_S, ESC_s, ESC_W, ESC_w, ESC_REF };
 246
 247 /* Opcode table: OP_BRA must be last, as all values >= it are used for brackets
 248 that extract substrings. Starting from 1 (i.e. after OP_END), the values up to
 249 OP_EOD must correspond in order to the list of escapes immediately above.
 250 Note that whenever this list is updated, the two macro definitions that follow
 251 must also be updated to match. */
 252
 253 #define FOR_EACH_OPCODE(macro) \
 254     macro(END) \
 255     \
 256     macro(NOT_WORD_BOUNDARY) \
 257     macro(WORD_BOUNDARY) \
 258     macro(NOT_DIGIT) \
 259     macro(DIGIT) \
 260     macro(NOT_WHITESPACE) \
 261     macro(WHITESPACE) \
 262     macro(NOT_WORDCHAR) \
 263     macro(WORDCHAR) \
 264     \
 265     macro(NOT_NEWLINE) \
 266     \
 267     macro(CIRC) \
 268     macro(DOLL) \
 269     macro(BOL) \
 270     macro(EOL) \
 271     macro(CHAR) \
 272     macro(CHAR_IGNORING_CASE) \
 273     macro(ASCII_CHAR) \
 274     macro(ASCII_LETTER_IGNORING_CASE) \
 275     macro(NOT) \
 276     \
 277     macro(STAR) \
 278     macro(MINSTAR) \
 279     macro(PLUS) \
 280     macro(MINPLUS) \
 281     macro(QUERY) \
 282     macro(MINQUERY) \
 283     macro(UPTO) \
 284     macro(MINUPTO) \
 285     macro(EXACT) \
 286     \
 287     macro(NOTSTAR) \
 288     macro(NOTMINSTAR) \
 289     macro(NOTPLUS) \
 290     macro(NOTMINPLUS) \
 291     macro(NOTQUERY) \
 292     macro(NOTMINQUERY) \
 293     macro(NOTUPTO) \
 294     macro(NOTMINUPTO) \
 295     macro(NOTEXACT) \
 296     \
 297     macro(TYPESTAR) \
 298     macro(TYPEMINSTAR) \
 299     macro(TYPEPLUS) \
 300     macro(TYPEMINPLUS) \
 301     macro(TYPEQUERY) \
 302     macro(TYPEMINQUERY) \
 303     macro(TYPEUPTO) \
 304     macro(TYPEMINUPTO) \
 305     macro(TYPEEXACT) \
 306     \
 307     macro(CRSTAR) \
 308     macro(CRMINSTAR) \
 309     macro(CRPLUS) \
 310     macro(CRMINPLUS) \
 311     macro(CRQUERY) \
 312     macro(CRMINQUERY) \
 313     macro(CRRANGE) \
 314     macro(CRMINRANGE) \
 315     \
 316     macro(CLASS) \
 317     macro(NCLASS) \
 318     macro(XCLASS) \
 319     \
 320     macro(REF) \
 321     \
 322     macro(ALT) \
 323     macro(KET) \
 324     macro(KETRMAX) \
 325     macro(KETRMIN) \
 326     \
 327     macro(ASSERT) \
 328     macro(ASSERT_NOT) \
 329     \
 330     macro(BRAZERO) \
 331     macro(BRAMINZERO) \
 332     macro(BRANUMBER) \
 333     macro(BRA)
 334
 335 #define OPCODE_ENUM_VALUE(opcode) OP_##opcode,
 336 enum { FOR_EACH_OPCODE(OPCODE_ENUM_VALUE) };
 337
 338 /* WARNING WARNING WARNING: There is an implicit assumption in pcre.c and
 339 study.c that all opcodes are less than 128 in value. This makes handling UTF-8
 340 character sequences easier. */
 341
 342 /* The highest extraction number before we have to start using additional
 343 bytes. (Originally PCRE didn't have support for extraction counts higher than
 344 this number.) The value is limited by the number of opcodes left after OP_BRA,
 345 i.e. 255 - OP_BRA. We actually set it a bit lower to leave room for additional
 346 opcodes. */
 347
 348 /* FIXME: Note that OP_BRA + 100 is > 128, so the two comments above
 349 are in conflict! */
 350
 351 #define EXTRACT_BASIC_MAX  100
 352
 353 /* The code vector runs on as long as necessary after the end. */
 354
 355 struct JSRegExp {
 356     unsigned options;
 357
 358     unsigned short topBracket;
 359     unsigned short topBackref;
 360
 361     unsigned short firstByte;
 362     unsigned short reqByte;
 363
 364 #if REGEXP_HISTOGRAM
 365     size_t stringOffset;
 366     size_t stringLength;
 367 #endif
 368 };
 369
 370 /* Internal shared data tables. These are tables that are used by more than one
 371  of the exported public functions. They have to be "external" in the C sense,
 372  but are not part of the PCRE public API. The data for these tables is in the
 373  pcre_tables.c module. */
 374
 375 #define jsc_pcre_utf8_table1_size 6
 376
 377 extern const int    jsc_pcre_utf8_table1[6];
 378 extern const int    jsc_pcre_utf8_table2[6];
 379 extern const int    jsc_pcre_utf8_table3[6];
 380 extern const unsigned char jsc_pcre_utf8_table4[0x40];
 381
 382 extern const unsigned char jsc_pcre_default_tables[tables_length];
 383
 384 static inline unsigned char toLowerCase(unsigned char c)
 385 {
 386     static const unsigned char* lowerCaseChars = jsc_pcre_default_tables + lcc_offset;
 387     return lowerCaseChars[c];
 388 }
 389
 390 static inline unsigned char flipCase(unsigned char c)
 391 {
 392     static const unsigned char* flippedCaseChars = jsc_pcre_default_tables + fcc_offset;
 393     return flippedCaseChars[c];
 394 }
 395
 396 static inline unsigned char classBitmapForChar(unsigned char c)
 397 {
 398     static const unsigned char* charClassBitmaps = jsc_pcre_default_tables + cbits_offset;
 399     return charClassBitmaps[c];
 400 }
 401
 402 static inline unsigned char charTypeForChar(unsigned char c)
 403 {
 404     const unsigned char* charTypeMap = jsc_pcre_default_tables + ctypes_offset;
 405     return charTypeMap[c];
 406 }
 407
 408 static inline bool isWordChar(UChar c)
 409 {
 410     return c < 128 && (charTypeForChar(c) & ctype_word);
 411 }
 412
 413 static inline bool isSpaceChar(UChar c)
 414 {
 415     return (c < 128 && (charTypeForChar(c) & ctype_space)) || c == 0x00A0;
 416 }
 417
 418 static inline bool isNewline(UChar nl)
 419 {
 420     return (nl == 0xA || nl == 0xD || nl == 0x2028 || nl == 0x2029);
 421 }
 422
 423 static inline bool isBracketStartOpcode(unsigned char opcode)
 424 {
 425     if (opcode >= OP_BRA)
 426         return true;
 427     switch (opcode) {
 428         case OP_ASSERT:
 429         case OP_ASSERT_NOT:
 430             return true;
 431         default:
 432             return false;
 433     }
 434 }
 435
 436 static inline void advanceToEndOfBracket(const unsigned char*& opcodePtr)
 437 {
 438     ASSERT(isBracketStartOpcode(*opcodePtr) || *opcodePtr == OP_ALT);
 439     do
 440         opcodePtr += getLinkValue(opcodePtr + 1);
 441     while (*opcodePtr == OP_ALT);
 442 }
 443
 444 /* Internal shared functions. These are functions that are used in more
 445 that one of the source files. They have to have external linkage, but
 446 but are not part of the public API and so not exported from the library. */
 447
 448 extern int jsc_pcre_ucp_othercase(unsigned);
 449 extern bool jsc_pcre_xclass(int, const unsigned char*);
 450
 451 #endif
 452
 453 #endif
 454
 455 /* End of pcre_internal.h */