regeximp.h (17346B)
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 intended 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, SP and active region 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 // Parameter 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 332 inline Regex8BitSet::Regex8BitSet() { 333 uprv_memset(d, 0, sizeof(d)); 334 } 335 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 341 inline void Regex8BitSet::add(UChar32 c) { 342 d[c>>3] |= 1 << (c&7); 343 } 344 345 inline void Regex8BitSet::init(const UnicodeSet *s) { 346 if (s != nullptr) { 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 if (this != &s) { 357 uprv_memcpy(d, s.d, sizeof(d)); 358 } 359 } 360 361 362 // Case folded UText Iterator helper class. 363 // Wraps a UText, provides a case-folded enumeration over its contents. 364 // Used in implementing case insensitive matching constructs. 365 // Implementation in rematch.cpp 366 367 class CaseFoldingUTextIterator: public UMemory { 368 public: 369 CaseFoldingUTextIterator(UText &text); 370 ~CaseFoldingUTextIterator(); 371 372 UChar32 next(); // Next case folded character 373 374 UBool inExpansion(); // True if last char returned from next() and the 375 // next to be returned both originated from a string 376 // folding of the same code point from the original UText. 377 private: 378 UText &fUText; 379 const char16_t *fFoldChars; 380 int32_t fFoldLength; 381 int32_t fFoldIndex; 382 383 }; 384 385 386 // Case folded char16_t * string iterator. 387 // Wraps a char16_t *, provides a case-folded enumeration over its contents. 388 // Used in implementing case insensitive matching constructs. 389 // Implementation in rematch.cpp 390 391 class CaseFoldingUCharIterator: public UMemory { 392 public: 393 CaseFoldingUCharIterator(const char16_t *chars, int64_t start, int64_t limit); 394 ~CaseFoldingUCharIterator(); 395 396 UChar32 next(); // Next case folded character 397 398 UBool inExpansion(); // True if last char returned from next() and the 399 // next to be returned both originated from a string 400 // folding of the same code point from the original UText. 401 402 int64_t getIndex(); // Return the current input buffer index. 403 404 private: 405 const char16_t *fChars; 406 int64_t fIndex; 407 int64_t fLimit; 408 const char16_t *fFoldChars; 409 int32_t fFoldLength; 410 int32_t fFoldIndex; 411 412 }; 413 414 U_NAMESPACE_END 415 #endif