0016bb56d5f382d32875fb9737a7f56d05f1440a
[WebKit-https.git] / Source / 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 */