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
put2ByteValue(unsigned char * opcodePtr,int value)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
put3ByteValue(unsigned char * opcodePtr,int value)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
get2ByteValue(const unsigned char * opcodePtr)135 static inline int get2ByteValue(const unsigned char* opcodePtr)
136 {
137 return (opcodePtr[0] << 8) | opcodePtr[1];
138 }
139
get3ByteValue(const unsigned char * opcodePtr)140 static inline int get3ByteValue(const unsigned char* opcodePtr)
141 {
142 return (opcodePtr[0] << 16) | (opcodePtr[1] << 8) | opcodePtr[2];
143 }
144
put2ByteValueAndAdvance(unsigned char * & opcodePtr,int value)145 static inline void put2ByteValueAndAdvance(unsigned char*& opcodePtr, int value)
146 {
147 put2ByteValue(opcodePtr, value);
148 opcodePtr += 2;
149 }
150
put3ByteValueAndAdvance(unsigned char * & opcodePtr,int value)151 static inline void put3ByteValueAndAdvance(unsigned char*& opcodePtr, int value)
152 {
153 put3ByteValue(opcodePtr, value);
154 opcodePtr += 3;
155 }
156
putLinkValueAllowZero(unsigned char * opcodePtr,int value)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
getLinkValueAllowZero(const unsigned char * opcodePtr)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
putLinkValue(unsigned char * opcodePtr,int value)182 static inline void putLinkValue(unsigned char* opcodePtr, int value)
183 {
184 ASSERT(value);
185 putLinkValueAllowZero(opcodePtr, value);
186 }
187
getLinkValue(const unsigned char * opcodePtr)188 static inline int getLinkValue(const unsigned char* opcodePtr)
189 {
190 int value = getLinkValueAllowZero(opcodePtr);
191 ASSERT(value);
192 return value;
193 }
194
putLinkValueAndAdvance(unsigned char * & opcodePtr,int value)195 static inline void putLinkValueAndAdvance(unsigned char*& opcodePtr, int value)
196 {
197 putLinkValue(opcodePtr, value);
198 opcodePtr += LINK_SIZE;
199 }
200
putLinkValueAllowZeroAndAdvance(unsigned char * & opcodePtr,int value)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
toLowerCase(unsigned char c)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
flipCase(unsigned char c)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
classBitmapForChar(unsigned char c)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
charTypeForChar(unsigned char c)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
isWordChar(UChar c)408 static inline bool isWordChar(UChar c)
409 {
410 return c < 128 && (charTypeForChar(c) & ctype_word);
411 }
412
isSpaceChar(UChar c)413 static inline bool isSpaceChar(UChar c)
414 {
415 return (c < 128 && (charTypeForChar(c) & ctype_space)) || c == 0x00A0;
416 }
417
isNewline(UChar nl)418 static inline bool isNewline(UChar nl)
419 {
420 return (nl == 0xA || nl == 0xD || nl == 0x2028 || nl == 0x2029);
421 }
422
isBracketStartOpcode(unsigned char opcode)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
advanceToEndOfBracket(const unsigned char * & opcodePtr)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 */
456