michael@0: // michael@0: // Copyright (C) 2002-2012 International Business Machines Corporation michael@0: // and others. All rights reserved. michael@0: // michael@0: // file: regeximp.h michael@0: // michael@0: // ICU Regular Expressions, michael@0: // Definitions of constant values used in the compiled form of michael@0: // a regular expression pattern. michael@0: // michael@0: michael@0: #ifndef _REGEXIMP_H michael@0: #define _REGEXIMP_H michael@0: michael@0: #include "unicode/utypes.h" michael@0: #include "unicode/uobject.h" michael@0: #include "unicode/uniset.h" michael@0: #include "unicode/utext.h" michael@0: michael@0: #include "cmemory.h" michael@0: #include "ucase.h" michael@0: michael@0: U_NAMESPACE_BEGIN michael@0: michael@0: // For debugging, define REGEX_DEBUG michael@0: // To define with configure, michael@0: // ./runConfigureICU --enable-debug --disable-release Linux CPPFLAGS="-DREGEX_DEBUG" michael@0: michael@0: #ifdef REGEX_DEBUG michael@0: // michael@0: // debugging options. Enable one or more of the three #defines immediately following michael@0: // michael@0: michael@0: //#define REGEX_SCAN_DEBUG michael@0: #define REGEX_DUMP_DEBUG michael@0: #define REGEX_RUN_DEBUG michael@0: michael@0: // End of #defines inteded to be directly set. michael@0: michael@0: #include michael@0: #endif michael@0: michael@0: #ifdef REGEX_SCAN_DEBUG michael@0: #define REGEX_SCAN_DEBUG_PRINTF(a) printf a michael@0: #else michael@0: #define REGEX_SCAN_DEBUG_PRINTF(a) michael@0: #endif michael@0: michael@0: #ifdef REGEX_DUMP_DEBUG michael@0: #define REGEX_DUMP_DEBUG_PRINTF(a) printf a michael@0: #else michael@0: #define REGEX_DUMP_DEBUG_PRINTF(a) michael@0: #endif michael@0: michael@0: #ifdef REGEX_RUN_DEBUG michael@0: #define REGEX_RUN_DEBUG_PRINTF(a) printf a michael@0: #define REGEX_DUMP_DEBUG_PRINTF(a) printf a michael@0: #else michael@0: #define REGEX_RUN_DEBUG_PRINTF(a) michael@0: #endif michael@0: michael@0: michael@0: // michael@0: // Opcode types In the compiled form of the regexp, these are the type, or opcodes, michael@0: // of the entries. michael@0: // michael@0: enum { michael@0: URX_RESERVED_OP = 0, // For multi-operand ops, most non-first words. michael@0: URX_RESERVED_OP_N = 255, // For multi-operand ops, negative operand values. michael@0: URX_BACKTRACK = 1, // Force a backtrack, as if a match test had failed. michael@0: URX_END = 2, michael@0: URX_ONECHAR = 3, // Value field is the 21 bit unicode char to match michael@0: URX_STRING = 4, // Value field is index of string start michael@0: URX_STRING_LEN = 5, // Value field is string length (code units) michael@0: URX_STATE_SAVE = 6, // Value field is pattern position to push michael@0: URX_NOP = 7, michael@0: URX_START_CAPTURE = 8, // Value field is capture group number. michael@0: URX_END_CAPTURE = 9, // Value field is capture group number michael@0: URX_STATIC_SETREF = 10, // Value field is index of set in array of sets. michael@0: URX_SETREF = 11, // Value field is index of set in array of sets. michael@0: URX_DOTANY = 12, michael@0: URX_JMP = 13, // Value field is destination position in michael@0: // the pattern. michael@0: URX_FAIL = 14, // Stop match operation, No match. michael@0: michael@0: URX_JMP_SAV = 15, // Operand: JMP destination location michael@0: URX_BACKSLASH_B = 16, // Value field: 0: \b 1: \B michael@0: URX_BACKSLASH_G = 17, michael@0: URX_JMP_SAV_X = 18, // Conditional JMP_SAV, michael@0: // Used in (x)+, breaks loop on zero length match. michael@0: // Operand: Jmp destination. michael@0: URX_BACKSLASH_X = 19, michael@0: URX_BACKSLASH_Z = 20, // \z Unconditional end of line. michael@0: michael@0: URX_DOTANY_ALL = 21, // ., in the . matches any mode. michael@0: URX_BACKSLASH_D = 22, // Value field: 0: \d 1: \D michael@0: URX_CARET = 23, // Value field: 1: multi-line mode. michael@0: URX_DOLLAR = 24, // Also for \Z michael@0: michael@0: URX_CTR_INIT = 25, // Counter Inits for {Interval} loops. michael@0: URX_CTR_INIT_NG = 26, // 2 kinds, normal and non-greedy. michael@0: // These are 4 word opcodes. See description. michael@0: // First Operand: Data loc of counter variable michael@0: // 2nd Operand: Pat loc of the URX_CTR_LOOPx michael@0: // at the end of the loop. michael@0: // 3rd Operand: Minimum count. michael@0: // 4th Operand: Max count, -1 for unbounded. michael@0: michael@0: URX_DOTANY_UNIX = 27, // '.' operator in UNIX_LINES mode, only \n marks end of line. michael@0: michael@0: URX_CTR_LOOP = 28, // Loop Ops for {interval} loops. michael@0: URX_CTR_LOOP_NG = 29, // Also in three flavors. michael@0: // Operand is loc of corresponding CTR_INIT. michael@0: michael@0: URX_CARET_M_UNIX = 30, // '^' operator, test for start of line in multi-line michael@0: // plus UNIX_LINES mode. michael@0: michael@0: URX_RELOC_OPRND = 31, // Operand value in multi-operand ops that refers michael@0: // back into compiled pattern code, and thus must michael@0: // be relocated when inserting/deleting ops in code. michael@0: michael@0: URX_STO_SP = 32, // Store the stack ptr. Operand is location within michael@0: // matcher data (not stack data) to store it. michael@0: URX_LD_SP = 33, // Load the stack pointer. Operand is location michael@0: // to load from. michael@0: URX_BACKREF = 34, // Back Reference. Parameter is the index of the michael@0: // capture group variables in the state stack frame. michael@0: URX_STO_INP_LOC = 35, // Store the input location. Operand is location michael@0: // within the matcher stack frame. michael@0: URX_JMPX = 36, // Conditional JMP. michael@0: // First Operand: JMP target location. michael@0: // Second Operand: Data location containing an michael@0: // input position. If current input position == michael@0: // saved input position, FAIL rather than taking michael@0: // the JMP michael@0: URX_LA_START = 37, // Starting a LookAround expression. michael@0: // Save InputPos and SP in static data. michael@0: // Operand: Static data offset for the save michael@0: URX_LA_END = 38, // Ending a Lookaround expression. michael@0: // Restore InputPos and Stack to saved values. michael@0: // Operand: Static data offset for saved data. michael@0: URX_ONECHAR_I = 39, // Test for case-insensitive match of a literal character. michael@0: // Operand: the literal char. michael@0: URX_STRING_I = 40, // Case insensitive string compare. michael@0: // First Operand: Index of start of string in string literals michael@0: // Second Operand (next word in compiled code): michael@0: // the length of the string. michael@0: URX_BACKREF_I = 41, // Case insensitive back reference. michael@0: // Parameter is the index of the michael@0: // capture group variables in the state stack frame. michael@0: URX_DOLLAR_M = 42, // $ in multi-line mode. michael@0: URX_CARET_M = 43, // ^ in multi-line mode. michael@0: URX_LB_START = 44, // LookBehind Start. michael@0: // Paramater is data location michael@0: URX_LB_CONT = 45, // LookBehind Continue. michael@0: // Param 0: the data location michael@0: // Param 1: The minimum length of the look-behind match michael@0: // Param 2: The max length of the look-behind match michael@0: URX_LB_END = 46, // LookBehind End. michael@0: // Parameter is the data location. michael@0: // Check that match ended at the right spot, michael@0: // Restore original input string len. michael@0: URX_LBN_CONT = 47, // Negative LookBehind Continue michael@0: // Param 0: the data location michael@0: // Param 1: The minimum length of the look-behind match michael@0: // Param 2: The max length of the look-behind match michael@0: // Param 3: The pattern loc following the look-behind block. michael@0: URX_LBN_END = 48, // Negative LookBehind end michael@0: // Parameter is the data location. michael@0: // Check that the match ended at the right spot. michael@0: URX_STAT_SETREF_N = 49, // Reference to a prebuilt set (e.g. \w), negated michael@0: // Operand is index of set in array of sets. michael@0: URX_LOOP_SR_I = 50, // Init a [set]* loop. michael@0: // Operand is the sets index in array of user sets. michael@0: URX_LOOP_C = 51, // Continue a [set]* or OneChar* loop. michael@0: // Operand is a matcher static data location. michael@0: // Must always immediately follow LOOP_x_I instruction. michael@0: URX_LOOP_DOT_I = 52, // .*, initialization of the optimized loop. michael@0: // Operand value: michael@0: // bit 0: michael@0: // 0: Normal (. doesn't match new-line) mode. michael@0: // 1: . matches new-line mode. michael@0: // bit 1: controls what new-lines are recognized by this operation. michael@0: // 0: All Unicode New-lines michael@0: // 1: UNIX_LINES, \u000a only. michael@0: URX_BACKSLASH_BU = 53, // \b or \B in UREGEX_UWORD mode, using Unicode style michael@0: // word boundaries. michael@0: URX_DOLLAR_D = 54, // $ end of input test, in UNIX_LINES mode. michael@0: URX_DOLLAR_MD = 55 // $ end of input test, in MULTI_LINE and UNIX_LINES mode. michael@0: michael@0: }; michael@0: michael@0: // Keep this list of opcode names in sync with the above enum michael@0: // Used for debug printing only. michael@0: #define URX_OPCODE_NAMES \ michael@0: " ", \ michael@0: "BACKTRACK", \ michael@0: "END", \ michael@0: "ONECHAR", \ michael@0: "STRING", \ michael@0: "STRING_LEN", \ michael@0: "STATE_SAVE", \ michael@0: "NOP", \ michael@0: "START_CAPTURE", \ michael@0: "END_CAPTURE", \ michael@0: "URX_STATIC_SETREF", \ michael@0: "SETREF", \ michael@0: "DOTANY", \ michael@0: "JMP", \ michael@0: "FAIL", \ michael@0: "JMP_SAV", \ michael@0: "BACKSLASH_B", \ michael@0: "BACKSLASH_G", \ michael@0: "JMP_SAV_X", \ michael@0: "BACKSLASH_X", \ michael@0: "BACKSLASH_Z", \ michael@0: "DOTANY_ALL", \ michael@0: "BACKSLASH_D", \ michael@0: "CARET", \ michael@0: "DOLLAR", \ michael@0: "CTR_INIT", \ michael@0: "CTR_INIT_NG", \ michael@0: "DOTANY_UNIX", \ michael@0: "CTR_LOOP", \ michael@0: "CTR_LOOP_NG", \ michael@0: "URX_CARET_M_UNIX", \ michael@0: "RELOC_OPRND", \ michael@0: "STO_SP", \ michael@0: "LD_SP", \ michael@0: "BACKREF", \ michael@0: "STO_INP_LOC", \ michael@0: "JMPX", \ michael@0: "LA_START", \ michael@0: "LA_END", \ michael@0: "ONECHAR_I", \ michael@0: "STRING_I", \ michael@0: "BACKREF_I", \ michael@0: "DOLLAR_M", \ michael@0: "CARET_M", \ michael@0: "LB_START", \ michael@0: "LB_CONT", \ michael@0: "LB_END", \ michael@0: "LBN_CONT", \ michael@0: "LBN_END", \ michael@0: "STAT_SETREF_N", \ michael@0: "LOOP_SR_I", \ michael@0: "LOOP_C", \ michael@0: "LOOP_DOT_I", \ michael@0: "BACKSLASH_BU", \ michael@0: "DOLLAR_D", \ michael@0: "DOLLAR_MD" michael@0: michael@0: michael@0: // michael@0: // Convenience macros for assembling and disassembling a compiled operation. michael@0: // michael@0: #define URX_BUILD(type, val) (int32_t)((type << 24) | (val)) michael@0: #define URX_TYPE(x) ((uint32_t)(x) >> 24) michael@0: #define URX_VAL(x) ((x) & 0xffffff) michael@0: michael@0: michael@0: // michael@0: // Access to Unicode Sets composite character properties michael@0: // The sets are accessed by the match engine for things like \w (word boundary) michael@0: // michael@0: enum { michael@0: URX_ISWORD_SET = 1, michael@0: URX_ISALNUM_SET = 2, michael@0: URX_ISALPHA_SET = 3, michael@0: URX_ISSPACE_SET = 4, michael@0: michael@0: URX_GC_NORMAL, // Sets for finding grapheme cluster boundaries. michael@0: URX_GC_EXTEND, michael@0: URX_GC_CONTROL, michael@0: URX_GC_L, michael@0: URX_GC_LV, michael@0: URX_GC_LVT, michael@0: URX_GC_V, michael@0: URX_GC_T, michael@0: michael@0: URX_LAST_SET, michael@0: michael@0: URX_NEG_SET = 0x800000 // Flag bit to reverse sense of set michael@0: // membership test. michael@0: }; michael@0: michael@0: michael@0: // michael@0: // Match Engine State Stack Frame Layout. michael@0: // michael@0: struct REStackFrame { michael@0: // Header michael@0: int64_t fInputIdx; // Position of next character in the input string michael@0: int64_t fPatIdx; // Position of next Op in the compiled pattern michael@0: // (int64_t for UVector64, values fit in an int32_t) michael@0: // Remainder michael@0: int64_t fExtra[1]; // Extra state, for capture group start/ends michael@0: // atomic parentheses, repeat counts, etc. michael@0: // Locations assigned at pattern compile time. michael@0: // Variable-length array. michael@0: }; michael@0: // number of UVector elements in the header michael@0: #define RESTACKFRAME_HDRCOUNT 2 michael@0: michael@0: // michael@0: // Start-Of-Match type. Used by find() to quickly scan to positions where a michael@0: // match might start before firing up the full match engine. michael@0: // michael@0: enum StartOfMatch { michael@0: START_NO_INFO, // No hint available. michael@0: START_CHAR, // Match starts with a literal code point. michael@0: START_SET, // Match starts with something matching a set. michael@0: START_START, // Match starts at start of buffer only (^ or \A) michael@0: START_LINE, // Match starts with ^ in multi-line mode. michael@0: START_STRING // Match starts with a literal string. michael@0: }; michael@0: michael@0: #define START_OF_MATCH_STR(v) ((v)==START_NO_INFO? "START_NO_INFO" : \ michael@0: (v)==START_CHAR? "START_CHAR" : \ michael@0: (v)==START_SET? "START_SET" : \ michael@0: (v)==START_START? "START_START" : \ michael@0: (v)==START_LINE? "START_LINE" : \ michael@0: (v)==START_STRING? "START_STRING" : \ michael@0: "ILLEGAL") michael@0: michael@0: // michael@0: // 8 bit set, to fast-path latin-1 set membership tests. michael@0: // michael@0: struct Regex8BitSet : public UMemory { michael@0: inline Regex8BitSet(); michael@0: inline void operator = (const Regex8BitSet &s); michael@0: inline void init(const UnicodeSet *src); michael@0: inline UBool contains(UChar32 c); michael@0: inline void add(UChar32 c); michael@0: int8_t d[32]; michael@0: }; michael@0: michael@0: inline Regex8BitSet::Regex8BitSet() { michael@0: uprv_memset(d, 0, sizeof(d)); michael@0: } michael@0: michael@0: inline UBool Regex8BitSet::contains(UChar32 c) { michael@0: // No bounds checking! This is deliberate. michael@0: return ((d[c>>3] & 1 <<(c&7)) != 0); michael@0: } michael@0: michael@0: inline void Regex8BitSet::add(UChar32 c) { michael@0: d[c>>3] |= 1 << (c&7); michael@0: } michael@0: michael@0: inline void Regex8BitSet::init(const UnicodeSet *s) { michael@0: if (s != NULL) { michael@0: for (int32_t i=0; i<=255; i++) { michael@0: if (s->contains(i)) { michael@0: this->add(i); michael@0: } michael@0: } michael@0: } michael@0: } michael@0: michael@0: inline void Regex8BitSet::operator = (const Regex8BitSet &s) { michael@0: uprv_memcpy(d, s.d, sizeof(d)); michael@0: } michael@0: michael@0: michael@0: // Case folded UText Iterator helper class. michael@0: // Wraps a UText, provides a case-folded enumeration over its contents. michael@0: // Used in implementing case insensitive matching constructs. michael@0: // Implementation in rematch.cpp michael@0: michael@0: class CaseFoldingUTextIterator: public UMemory { michael@0: public: michael@0: CaseFoldingUTextIterator(UText &text); michael@0: ~CaseFoldingUTextIterator(); michael@0: michael@0: UChar32 next(); // Next case folded character michael@0: michael@0: UBool inExpansion(); // True if last char returned from next() and the michael@0: // next to be returned both originated from a string michael@0: // folding of the same code point from the orignal UText. michael@0: private: michael@0: UText &fUText; michael@0: const UCaseProps *fcsp; michael@0: const UChar *fFoldChars; michael@0: int32_t fFoldLength; michael@0: int32_t fFoldIndex; michael@0: michael@0: }; michael@0: michael@0: michael@0: // Case folded UChar * string iterator. michael@0: // Wraps a UChar *, provides a case-folded enumeration over its contents. michael@0: // Used in implementing case insensitive matching constructs. michael@0: // Implementation in rematch.cpp michael@0: michael@0: class CaseFoldingUCharIterator: public UMemory { michael@0: public: michael@0: CaseFoldingUCharIterator(const UChar *chars, int64_t start, int64_t limit); michael@0: ~CaseFoldingUCharIterator(); michael@0: michael@0: UChar32 next(); // Next case folded character michael@0: michael@0: UBool inExpansion(); // True if last char returned from next() and the michael@0: // next to be returned both originated from a string michael@0: // folding of the same code point from the orignal UText. michael@0: michael@0: int64_t getIndex(); // Return the current input buffer index. michael@0: michael@0: private: michael@0: const UChar *fChars; michael@0: int64_t fIndex; michael@0: int64_t fLimit; michael@0: const UCaseProps *fcsp; michael@0: const UChar *fFoldChars; michael@0: int32_t fFoldLength; michael@0: int32_t fFoldIndex; michael@0: michael@0: }; michael@0: michael@0: U_NAMESPACE_END michael@0: #endif michael@0: