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