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