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 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 #include "Assertions.h"
  73
  74 #if COMPILER(MSVC)
  75 #pragma warning(disable: 4232)
  76 #pragma warning(disable: 4244)
  77 #endif
  78
  79 #include "pcre.h"
  80
  81 /* The value of LINK_SIZE determines the number of bytes used to store links as
  82 offsets within the compiled regex. The default is 2, which allows for compiled
  83 patterns up to 64K long. */
  84
  85 #define LINK_SIZE   2
  86
  87 /* Define DEBUG to get debugging output on stdout. */
  88
  89 #if 0
  90 #define DEBUG
  91 #endif
  92
  93 /* Use a macro for debugging printing, 'cause that eliminates the use of #ifdef
  94 inline, and there are *still* stupid compilers about that don't like indented
  95 pre-processor statements, or at least there were when I first wrote this. After
  96 all, it had only been about 10 years then... */
  97
  98 #ifdef DEBUG
  99 #define DPRINTF(p) printf p
 100 #else
 101 #define DPRINTF(p) /*nothing*/
 102 #endif
 103
 104 /* PCRE keeps offsets in its compiled code as 2-byte quantities (always stored
 105 in big-endian order) by default. These are used, for example, to link from the
 106 start of a subpattern to its alternatives and its end. The use of 2 bytes per
 107 offset limits the size of the compiled regex to around 64K, which is big enough
 108 for almost everybody. However, I received a request for an even bigger limit.
 109 For this reason, and also to make the code easier to maintain, the storing and
 110 loading of offsets from the byte string is now handled by the functions that are
 111 defined here. */
 112
 113 /* PCRE uses some other 2-byte quantities that do not change when the size of
 114 offsets changes. There are used for repeat counts and for other things such as
 115 capturing parenthesis numbers in back references. */
 116
 117 static inline void put2ByteValue(unsigned char* opcodePtr, int value)
 118 {
 119     ASSERT(value >= 0 && value <= 0xFFFF);
 120     opcodePtr[0] = value >> 8;
 121     opcodePtr[1] = value;
 122 }
 123
 124 static inline int get2ByteValue(const unsigned char* opcodePtr)
 125 {
 126     return (opcodePtr[0] << 8) | opcodePtr[1];
 127 }
 128
 129 static inline void put2ByteValueAndAdvance(unsigned char*& opcodePtr, int value)
 130 {
 131     put2ByteValue(opcodePtr, value);
 132     opcodePtr += 2;
 133 }
 134
 135 static inline void putLinkValueAllowZero(unsigned char* opcodePtr, int value)
 136 {
 137     put2ByteValue(opcodePtr, value);
 138 }
 139
 140 static inline int getLinkValueAllowZero(const unsigned char* opcodePtr)
 141 {
 142     return get2ByteValue(opcodePtr);
 143 }
 144
 145 #define MAX_PATTERN_SIZE (1 << 16)
 146
 147 static inline void putLinkValue(unsigned char* opcodePtr, int value)
 148 {
 149     ASSERT(value);
 150     putLinkValueAllowZero(opcodePtr, value);
 151 }
 152
 153 static inline int getLinkValue(const unsigned char* opcodePtr)
 154 {
 155     int value = getLinkValueAllowZero(opcodePtr);
 156     ASSERT(value);
 157     return value;
 158 }
 159
 160 static inline void putLinkValueAndAdvance(unsigned char*& opcodePtr, int value)
 161 {
 162     putLinkValue(opcodePtr, value);
 163     opcodePtr += LINK_SIZE;
 164 }
 165
 166 static inline void putLinkValueAllowZeroAndAdvance(unsigned char*& opcodePtr, int value)
 167 {
 168     putLinkValueAllowZero(opcodePtr, value);
 169     opcodePtr += LINK_SIZE;
 170 }
 171
 172 // FIXME: These are really more of a "compiled regexp state" than "regexp options"
 173 enum RegExpOptions {
 174     UseFirstByteOptimizationOption = 0x40000000,  /* first_byte is set */
 175     UseRequiredByteOptimizationOption = 0x20000000,  /* req_byte is set */
 176     UseMultiLineFirstByteOptimizationOption = 0x10000000,  /* start after \n for multiline */
 177     IsAnchoredOption = 0x02000000,  /* can't use partial with this regex */
 178     IgnoreCaseOption = 0x00000001,
 179     MatchAcrossMultipleLinesOption = 0x00000002
 180 };
 181
 182 /* Flags added to firstbyte or reqbyte; a "non-literal" item is either a
 183 variable-length repeat, or a anything other than literal characters. */
 184
 185 #define REQ_IGNORE_CASE 0x0100    /* indicates should ignore case */
 186 #define REQ_VARY     0x0200    /* reqbyte followed non-literal item */
 187
 188 /* Miscellaneous definitions */
 189
 190 /* Flag bits and data types for the extended class (OP_XCLASS) for classes that
 191 contain UTF-8 characters with values greater than 255. */
 192
 193 #define XCL_NOT    0x01    /* Flag: this is a negative class */
 194 #define XCL_MAP    0x02    /* Flag: a 32-byte map is present */
 195
 196 #define XCL_END       0    /* Marks end of individual items */
 197 #define XCL_SINGLE    1    /* Single item (one multibyte char) follows */
 198 #define XCL_RANGE     2    /* A range (two multibyte chars) follows */
 199
 200 /* These are escaped items that aren't just an encoding of a particular data
 201 value such as \n. They must have non-zero values, as check_escape() returns
 202 their negation. Also, they must appear in the same order as in the opcode
 203 definitions below, up to ESC_w. The final one must be
 204 ESC_REF as subsequent values are used for \1, \2, \3, etc. There is are two
 205 tests in the code for an escape > ESC_b and <= ESC_w to
 206 detect the types that may be repeated. These are the types that consume
 207 characters. If any new escapes are put in between that don't consume a
 208 character, that code will have to change. */
 209
 210 enum { ESC_B = 1, ESC_b, ESC_D, ESC_d, ESC_S, ESC_s, ESC_W, ESC_w, ESC_REF };
 211
 212 /* Opcode table: OP_BRA must be last, as all values >= it are used for brackets
 213 that extract substrings. Starting from 1 (i.e. after OP_END), the values up to
 214 OP_EOD must correspond in order to the list of escapes immediately above.
 215 Note that whenever this list is updated, the two macro definitions that follow
 216 must also be updated to match. */
 217
 218 #define FOR_EACH_OPCODE(macro) \
 219     macro(END) \
 220     \
 221     macro(NOT_WORD_BOUNDARY) \
 222     macro(WORD_BOUNDARY) \
 223     macro(NOT_DIGIT) \
 224     macro(DIGIT) \
 225     macro(NOT_WHITESPACE) \
 226     macro(WHITESPACE) \
 227     macro(NOT_WORDCHAR) \
 228     macro(WORDCHAR) \
 229     \
 230     macro(NOT_NEWLINE) \
 231     \
 232     macro(CIRC) \
 233     macro(DOLL) \
 234     macro(CHAR) \
 235     macro(CHAR_IGNORING_CASE) \
 236     macro(ASCII_CHAR) \
 237     macro(ASCII_LETTER_IGNORING_CASE) \
 238     macro(NOT) \
 239     \
 240     macro(STAR) \
 241     macro(MINSTAR) \
 242     macro(PLUS) \
 243     macro(MINPLUS) \
 244     macro(QUERY) \
 245     macro(MINQUERY) \
 246     macro(UPTO) \
 247     macro(MINUPTO) \
 248     macro(EXACT) \
 249     \
 250     macro(NOTSTAR) \
 251     macro(NOTMINSTAR) \
 252     macro(NOTPLUS) \
 253     macro(NOTMINPLUS) \
 254     macro(NOTQUERY) \
 255     macro(NOTMINQUERY) \
 256     macro(NOTUPTO) \
 257     macro(NOTMINUPTO) \
 258     macro(NOTEXACT) \
 259     \
 260     macro(TYPESTAR) \
 261     macro(TYPEMINSTAR) \
 262     macro(TYPEPLUS) \
 263     macro(TYPEMINPLUS) \
 264     macro(TYPEQUERY) \
 265     macro(TYPEMINQUERY) \
 266     macro(TYPEUPTO) \
 267     macro(TYPEMINUPTO) \
 268     macro(TYPEEXACT) \
 269     \
 270     macro(CRSTAR) \
 271     macro(CRMINSTAR) \
 272     macro(CRPLUS) \
 273     macro(CRMINPLUS) \
 274     macro(CRQUERY) \
 275     macro(CRMINQUERY) \
 276     macro(CRRANGE) \
 277     macro(CRMINRANGE) \
 278     \
 279     macro(CLASS) \
 280     macro(NCLASS) \
 281     macro(XCLASS) \
 282     \
 283     macro(REF) \
 284     \
 285     macro(ALT) \
 286     macro(KET) \
 287     macro(KETRMAX) \
 288     macro(KETRMIN) \
 289     \
 290     macro(ASSERT) \
 291     macro(ASSERT_NOT) \
 292     \
 293     macro(BRAZERO) \
 294     macro(BRAMINZERO) \
 295     macro(BRANUMBER) \
 296     macro(BRA)
 297
 298 #define OPCODE_ENUM_VALUE(opcode) OP_##opcode,
 299 enum { FOR_EACH_OPCODE(OPCODE_ENUM_VALUE) };
 300
 301 /* WARNING WARNING WARNING: There is an implicit assumption in pcre.c and
 302 study.c that all opcodes are less than 128 in value. This makes handling UTF-8
 303 character sequences easier. */
 304
 305 /* The highest extraction number before we have to start using additional
 306 bytes. (Originally PCRE didn't have support for extraction counts higher than
 307 this number.) The value is limited by the number of opcodes left after OP_BRA,
 308 i.e. 255 - OP_BRA. We actually set it a bit lower to leave room for additional
 309 opcodes. */
 310
 311 /* FIXME: Note that OP_BRA + 100 is > 128, so the two comments above
 312 are in conflict! */
 313
 314 #define EXTRACT_BASIC_MAX  100
 315
 316 /* The index of names and the
 317 code vector run on as long as necessary after the end. We store an explicit
 318 offset to the name table so that if a regex is compiled on one host, saved, and
 319 then run on another where the size of pointers is different, all might still
 320 be well. For the case of compiled-on-4 and run-on-8, we include an extra
 321 pointer that is always NULL.
 322 */
 323
 324 struct JSRegExp {
 325     unsigned options;
 326
 327     unsigned short top_bracket;
 328     unsigned short top_backref;
 329
 330     unsigned short first_byte;
 331     unsigned short req_byte;
 332 };
 333
 334 /* Internal shared data tables. These are tables that are used by more than one
 335  of the exported public functions. They have to be "external" in the C sense,
 336  but are not part of the PCRE public API. The data for these tables is in the
 337  pcre_tables.c module. */
 338
 339 #define kjs_pcre_utf8_table1_size 6
 340
 341 extern const int    kjs_pcre_utf8_table1[6];
 342 extern const int    kjs_pcre_utf8_table2[6];
 343 extern const int    kjs_pcre_utf8_table3[6];
 344 extern const unsigned char kjs_pcre_utf8_table4[0x40];
 345
 346 extern const unsigned char kjs_pcre_default_tables[tables_length];
 347
 348 static inline unsigned char toLowerCase(unsigned char c)
 349 {
 350     static const unsigned char* lowerCaseChars = kjs_pcre_default_tables + lcc_offset;
 351     return lowerCaseChars[c];
 352 }
 353
 354 static inline unsigned char flipCase(unsigned char c)
 355 {
 356     static const unsigned char* flippedCaseChars = kjs_pcre_default_tables + fcc_offset;
 357     return flippedCaseChars[c];
 358 }
 359
 360 static inline unsigned char classBitmapForChar(unsigned char c)
 361 {
 362     static const unsigned char* charClassBitmaps = kjs_pcre_default_tables + cbits_offset;
 363     return charClassBitmaps[c];
 364 }
 365
 366 static inline unsigned char charTypeForChar(unsigned char c)
 367 {
 368     const unsigned char* charTypeMap = kjs_pcre_default_tables + ctypes_offset;
 369     return charTypeMap[c];
 370 }
 371
 372 static inline bool isWordChar(UChar c)
 373 {
 374     return c < 128 && (charTypeForChar(c) & ctype_word);
 375 }
 376
 377 static inline bool isSpaceChar(UChar c)
 378 {
 379     return c < 128 && (charTypeForChar(c) & ctype_space);
 380 }
 381
 382 static inline bool isNewline(UChar nl)
 383 {
 384     return (nl == 0xA || nl == 0xD || nl == 0x2028 || nl == 0x2029);
 385 }
 386
 387 static inline bool isBracketStartOpcode(unsigned char opcode)
 388 {
 389     if (opcode >= OP_BRA)
 390         return true;
 391     switch (opcode) {
 392         case OP_ASSERT:
 393         case OP_ASSERT_NOT:
 394             return true;
 395         default:
 396             return false;
 397     }
 398 }
 399
 400 static inline void advanceToEndOfBracket(const unsigned char*& opcodePtr)
 401 {
 402     ASSERT(isBracketStartOpcode(*opcodePtr) || *opcodePtr == OP_ALT);
 403     do
 404         opcodePtr += getLinkValue(opcodePtr + 1);
 405     while (*opcodePtr == OP_ALT);
 406 }
 407
 408 /* Internal shared functions. These are functions that are used in more
 409 that one of the source files. They have to have external linkage, but
 410 but are not part of the public API and so not exported from the library. */
 411
 412 extern int kjs_pcre_ucp_othercase(unsigned);
 413 extern bool kjs_pcre_xclass(int, const unsigned char*);
 414
 415 #endif
 416
 417 #endif
 418
 419 /* End of pcre_internal.h */