1 //
2 // Copyright (C) 2002-2010 International Business Machines Corporation
3 // and others. All rights reserved.
4 //
5 // file: regeximp.h
6 //
7 // ICU Regular Expressions,
8 // Definitions of constant values used in the compiled form of
9 // a regular expression pattern.
10 //
11
12 #ifndef _REGEXIMP_H
13 #define _REGEXIMP_H
14
15 #include "cmemory.h"
16
17 U_NAMESPACE_BEGIN
18
19 #ifdef REGEX_DEBUG /* For debugging, define REGEX_DEBUG in regex.h, not here in this file. */
20 //
21 // debugging options. Enable one or more of the three #defines immediately following
22 //
23
24 //#define REGEX_SCAN_DEBUG
25 #define REGEX_DUMP_DEBUG
26 #define REGEX_RUN_DEBUG
27
28 // End of #defines inteded to be directly set.
29
30 #include <stdio.h>
31 #endif
32
33 #ifdef REGEX_SCAN_DEBUG
34 #define REGEX_SCAN_DEBUG_PRINTF(a) printf a
35 #else
36 #define REGEX_SCAN_DEBUG_PRINTF(a)
37 #endif
38
39 #ifdef REGEX_DUMP_DEBUG
40 #define REGEX_DUMP_DEBUG_PRINTF(a) printf a
41 #else
42 #define REGEX_DUMP_DEBUG_PRINTF(a)
43 #endif
44
45 #ifdef REGEX_RUN_DEBUG
46 #define REGEX_RUN_DEBUG_PRINTF(a) printf a
47 #define REGEX_DUMP_DEBUG_PRINTF(a) printf a
48 #else
49 #define REGEX_RUN_DEBUG_PRINTF(a)
50 #endif
51
52
53 //
54 // Opcode types In the compiled form of the regexp, these are the type, or opcodes,
55 // of the entries.
56 //
57 enum {
58 URX_RESERVED_OP = 0, // For multi-operand ops, most non-first words.
59 URX_RESERVED_OP_N = 255, // For multi-operand ops, negative operand values.
60 URX_BACKTRACK = 1, // Force a backtrack, as if a match test had failed.
61 URX_END = 2,
62 URX_ONECHAR = 3, // Value field is the 21 bit unicode char to match
63 URX_STRING = 4, // Value field is index of string start
64 URX_STRING_LEN = 5, // Value field is string length (code units)
65 URX_STATE_SAVE = 6, // Value field is pattern position to push
66 URX_NOP = 7,
67 URX_START_CAPTURE = 8, // Value field is capture group number.
68 URX_END_CAPTURE = 9, // Value field is capture group number
69 URX_STATIC_SETREF = 10, // Value field is index of set in array of sets.
70 URX_SETREF = 11, // Value field is index of set in array of sets.
71 URX_DOTANY = 12,
72 URX_JMP = 13, // Value field is destination position in
73 // the pattern.
74 URX_FAIL = 14, // Stop match operation, No match.
75
76 URX_JMP_SAV = 15, // Operand: JMP destination location
77 URX_BACKSLASH_B = 16, // Value field: 0: \b 1: \B
78 URX_BACKSLASH_G = 17,
79 URX_JMP_SAV_X = 18, // Conditional JMP_SAV,
80 // Used in (x)+, breaks loop on zero length match.
81 // Operand: Jmp destination.
82 URX_BACKSLASH_X = 19,
83 URX_BACKSLASH_Z = 20, // \z Unconditional end of line.
84
85 URX_DOTANY_ALL = 21, // ., in the . matches any mode.
86 URX_BACKSLASH_D = 22, // Value field: 0: \d 1: \D
87 URX_CARET = 23, // Value field: 1: multi-line mode.
88 URX_DOLLAR = 24, // Also for \Z
89
90 URX_CTR_INIT = 25, // Counter Inits for {Interval} loops.
91 URX_CTR_INIT_NG = 26, // 2 kinds, normal and non-greedy.
92 // These are 4 word opcodes. See description.
93 // First Operand: Data loc of counter variable
94 // 2nd Operand: Pat loc of the URX_CTR_LOOPx
95 // at the end of the loop.
96 // 3rd Operand: Minimum count.
97 // 4th Operand: Max count, -1 for unbounded.
98
99 URX_DOTANY_UNIX = 27, // '.' operator in UNIX_LINES mode, only \n marks end of line.
100
101 URX_CTR_LOOP = 28, // Loop Ops for {interval} loops.
102 URX_CTR_LOOP_NG = 29, // Also in three flavors.
103 // Operand is loc of corresponding CTR_INIT.
104
105 URX_CARET_M_UNIX = 30, // '^' operator, test for start of line in multi-line
106 // plus UNIX_LINES mode.
107
108 URX_RELOC_OPRND = 31, // Operand value in multi-operand ops that refers
109 // back into compiled pattern code, and thus must
110 // be relocated when inserting/deleting ops in code.
111
112 URX_STO_SP = 32, // Store the stack ptr. Operand is location within
113 // matcher data (not stack data) to store it.
114 URX_LD_SP = 33, // Load the stack pointer. Operand is location
115 // to load from.
116 URX_BACKREF = 34, // Back Reference. Parameter is the index of the
117 // capture group variables in the state stack frame.
118 URX_STO_INP_LOC = 35, // Store the input location. Operand is location
119 // within the matcher stack frame.
120 URX_JMPX = 36, // Conditional JMP.
121 // First Operand: JMP target location.
122 // Second Operand: Data location containing an
123 // input position. If current input position ==
124 // saved input position, FAIL rather than taking
125 // the JMP
126 URX_LA_START = 37, // Starting a LookAround expression.
127 // Save InputPos and SP in static data.
128 // Operand: Static data offset for the save
129 URX_LA_END = 38, // Ending a Lookaround expression.
130 // Restore InputPos and Stack to saved values.
131 // Operand: Static data offset for saved data.
132 URX_ONECHAR_I = 39, // Test for case-insensitive match of a literal character.
133 // Operand: the literal char.
134 URX_STRING_I = 40, // Case insensitive string compare.
135 // First Operand: Index of start of string in string literals
136 // Second Operand (next word in compiled code):
137 // the length of the string.
138 URX_BACKREF_I = 41, // Case insensitive back reference.
139 // Parameter is the index of the
140 // capture group variables in the state stack frame.
141 URX_DOLLAR_M = 42, // $ in multi-line mode.
142 URX_CARET_M = 43, // ^ in multi-line mode.
143 URX_LB_START = 44, // LookBehind Start.
144 // Paramater is data location
145 URX_LB_CONT = 45, // LookBehind Continue.
146 // Param 0: the data location
147 // Param 1: The minimum length of the look-behind match
148 // Param 2: The max length of the look-behind match
149 URX_LB_END = 46, // LookBehind End.
150 // Parameter is the data location.
151 // Check that match ended at the right spot,
152 // Restore original input string len.
153 URX_LBN_CONT = 47, // Negative LookBehind Continue
154 // Param 0: the data location
155 // Param 1: The minimum length of the look-behind match
156 // Param 2: The max length of the look-behind match
157 // Param 3: The pattern loc following the look-behind block.
158 URX_LBN_END = 48, // Negative LookBehind end
159 // Parameter is the data location.
160 // Check that the match ended at the right spot.
161 URX_STAT_SETREF_N = 49, // Reference to a prebuilt set (e.g. \w), negated
162 // Operand is index of set in array of sets.
163 URX_LOOP_SR_I = 50, // Init a [set]* loop.
164 // Operand is the sets index in array of user sets.
165 URX_LOOP_C = 51, // Continue a [set]* or OneChar* loop.
166 // Operand is a matcher static data location.
167 // Must always immediately follow LOOP_x_I instruction.
168 URX_LOOP_DOT_I = 52, // .*, initialization of the optimized loop.
169 // Operand value:
170 // bit 0:
171 // 0: Normal (. doesn't match new-line) mode.
172 // 1: . matches new-line mode.
173 // bit 1: controls what new-lines are recognized by this operation.
174 // 0: All Unicode New-lines
175 // 1: UNIX_LINES, \u000a only.
176 URX_BACKSLASH_BU = 53, // \b or \B in UREGEX_UWORD mode, using Unicode style
177 // word boundaries.
178 URX_DOLLAR_D = 54, // $ end of input test, in UNIX_LINES mode.
179 URX_DOLLAR_MD = 55 // $ end of input test, in MULTI_LINE and UNIX_LINES mode.
180
181 };
182
183 // Keep this list of opcode names in sync with the above enum
184 // Used for debug printing only.
185 #define URX_OPCODE_NAMES \
186 " ", \
187 "BACKTRACK", \
188 "END", \
189 "ONECHAR", \
190 "STRING", \
191 "STRING_LEN", \
192 "STATE_SAVE", \
193 "NOP", \
194 "START_CAPTURE", \
195 "END_CAPTURE", \
196 "URX_STATIC_SETREF", \
197 "SETREF", \
198 "DOTANY", \
199 "JMP", \
200 "FAIL", \
201 "JMP_SAV", \
202 "BACKSLASH_B", \
203 "BACKSLASH_G", \
204 "JMP_SAV_X", \
205 "BACKSLASH_X", \
206 "BACKSLASH_Z", \
207 "DOTANY_ALL", \
208 "BACKSLASH_D", \
209 "CARET", \
210 "DOLLAR", \
211 "CTR_INIT", \
212 "CTR_INIT_NG", \
213 "DOTANY_UNIX", \
214 "CTR_LOOP", \
215 "CTR_LOOP_NG", \
216 "URX_CARET_M_UNIX", \
217 "RELOC_OPRND", \
218 "STO_SP", \
219 "LD_SP", \
220 "BACKREF", \
221 "STO_INP_LOC", \
222 "JMPX", \
223 "LA_START", \
224 "LA_END", \
225 "ONECHAR_I", \
226 "STRING_I", \
227 "BACKREF_I", \
228 "DOLLAR_M", \
229 "CARET_M", \
230 "LB_START", \
231 "LB_CONT", \
232 "LB_END", \
233 "LBN_CONT", \
234 "LBN_END", \
235 "STAT_SETREF_N", \
236 "LOOP_SR_I", \
237 "LOOP_C", \
238 "LOOP_DOT_I", \
239 "BACKSLASH_BU", \
240 "DOLLAR_D", \
241 "DOLLAR_MD"
242
243
244 //
245 // Convenience macros for assembling and disassembling a compiled operation.
246 //
247 #define URX_BUILD(type, val) (int32_t)((type << 24) | (val))
248 #define URX_TYPE(x) ((uint32_t)(x) >> 24)
249 #define URX_VAL(x) ((x) & 0xffffff)
250
251
252 //
253 // Access to Unicode Sets composite character properties
254 // The sets are accessed by the match engine for things like \w (word boundary)
255 //
256 enum {
257 URX_ISWORD_SET = 1,
258 URX_ISALNUM_SET = 2,
259 URX_ISALPHA_SET = 3,
260 URX_ISSPACE_SET = 4,
261
262 URX_GC_NORMAL, // Sets for finding grapheme cluster boundaries.
263 URX_GC_EXTEND,
264 URX_GC_CONTROL,
265 URX_GC_L,
266 URX_GC_LV,
267 URX_GC_LVT,
268 URX_GC_V,
269 URX_GC_T,
270
271 URX_LAST_SET,
272
273 URX_NEG_SET = 0x800000 // Flag bit to reverse sense of set
274 // membership test.
275 };
276
277
278 //
279 // Match Engine State Stack Frame Layout.
280 //
281 struct REStackFrame {
282 // Header
283 int64_t fInputIdx; // Position of next character in the input string
284 int64_t fPatIdx; // Position of next Op in the compiled pattern
285 // (int64_t for UVector64, values fit in an int32_t)
286 // Remainder
287 int64_t fExtra[1]; // Extra state, for capture group start/ends
288 // atomic parentheses, repeat counts, etc.
289 // Locations assigned at pattern compile time.
290 // Variable-length array.
291 };
292 // number of UVector elements in the header
293 #define RESTACKFRAME_HDRCOUNT 2
294
295 //
296 // Start-Of-Match type. Used by find() to quickly scan to positions where a
297 // match might start before firing up the full match engine.
298 //
299 enum StartOfMatch {
300 START_NO_INFO, // No hint available.
301 START_CHAR, // Match starts with a literal code point.
302 START_SET, // Match starts with something matching a set.
303 START_START, // Match starts at start of buffer only (^ or \A)
304 START_LINE, // Match starts with ^ in multi-line mode.
305 START_STRING // Match starts with a literal string.
306 };
307
308 #define START_OF_MATCH_STR(v) ((v)==START_NO_INFO? "START_NO_INFO" : \
309 (v)==START_CHAR? "START_CHAR" : \
310 (v)==START_SET? "START_SET" : \
311 (v)==START_START? "START_START" : \
312 (v)==START_LINE? "START_LINE" : \
313 (v)==START_STRING? "START_STRING" : \
314 "ILLEGAL")
315
316 //
317 // 8 bit set, to fast-path latin-1 set membership tests.
318 //
319 struct Regex8BitSet : public UMemory {
320 inline Regex8BitSet();
321 inline void operator = (const Regex8BitSet &s);
322 inline void init(const UnicodeSet *src);
323 inline UBool contains(UChar32 c);
324 inline void add(UChar32 c);
325 int8_t d[32];
326 };
327
Regex8BitSet()328 inline Regex8BitSet::Regex8BitSet() {
329 uprv_memset(d, 0, sizeof(d));
330 }
331
contains(UChar32 c)332 inline UBool Regex8BitSet::contains(UChar32 c) {
333 // No bounds checking! This is deliberate.
334 return ((d[c>>3] & 1 <<(c&7)) != 0);
335 }
336
add(UChar32 c)337 inline void Regex8BitSet::add(UChar32 c) {
338 d[c>>3] |= 1 << (c&7);
339 }
340
init(const UnicodeSet * s)341 inline void Regex8BitSet::init(const UnicodeSet *s) {
342 if (s != NULL) {
343 for (int32_t i=0; i<=255; i++) {
344 if (s->contains(i)) {
345 this->add(i);
346 }
347 }
348 }
349 }
350
351 inline void Regex8BitSet::operator = (const Regex8BitSet &s) {
352 uprv_memcpy(d, s.d, sizeof(d));
353 }
354
355 U_NAMESPACE_END
356 #endif
357
358