| // | |
| // file: regexcmp.cpp | |
| // | |
| // Copyright (C) 2002-2015 International Business Machines Corporation and others. | |
| // All Rights Reserved. | |
| // | |
| // This file contains the ICU regular expression compiler, which is responsible | |
| // for processing a regular expression pattern into the compiled form that | |
| // is used by the match finding engine. | |
| // | |
| #include "unicode/utypes.h" | |
| #if !UCONFIG_NO_REGULAR_EXPRESSIONS | |
| #include "starboard/client_porting/poem/assert_poem.h" | |
| #include "starboard/client_porting/poem/string_poem.h" | |
| #include "unicode/ustring.h" | |
| #include "unicode/unistr.h" | |
| #include "unicode/uniset.h" | |
| #include "unicode/uchar.h" | |
| #include "unicode/uchriter.h" | |
| #include "unicode/parsepos.h" | |
| #include "unicode/parseerr.h" | |
| #include "unicode/regex.h" | |
| #include "unicode/utf.h" | |
| #include "unicode/utf16.h" | |
| #include "patternprops.h" | |
| #include "putilimp.h" | |
| #include "cmemory.h" | |
| #include "cstring.h" | |
| #include "uvectr32.h" | |
| #include "uvectr64.h" | |
| #include "uassert.h" | |
| #include "uinvchar.h" | |
| #include "regeximp.h" | |
| #include "regexcst.h" // Contains state table for the regex pattern parser. | |
| // generated by a Perl script. | |
| #include "regexcmp.h" | |
| #include "regexst.h" | |
| #include "regextxt.h" | |
| U_NAMESPACE_BEGIN | |
| //------------------------------------------------------------------------------ | |
| // | |
| // Constructor. | |
| // | |
| //------------------------------------------------------------------------------ | |
| RegexCompile::RegexCompile(RegexPattern *rxp, UErrorCode &status) : | |
| fParenStack(status), fSetStack(status), fSetOpStack(status) | |
| { | |
| // Lazy init of all shared global sets (needed for init()'s empty text) | |
| RegexStaticSets::initGlobals(&status); | |
| fStatus = &status; | |
| fRXPat = rxp; | |
| fScanIndex = 0; | |
| fLastChar = -1; | |
| fPeekChar = -1; | |
| fLineNum = 1; | |
| fCharNum = 0; | |
| fQuoteMode = FALSE; | |
| fInBackslashQuote = FALSE; | |
| fModeFlags = fRXPat->fFlags | 0x80000000; | |
| fEOLComments = TRUE; | |
| fMatchOpenParen = -1; | |
| fMatchCloseParen = -1; | |
| fCaptureName = NULL; | |
| fLastSetLiteral = U_SENTINEL; | |
| if (U_SUCCESS(status) && U_FAILURE(rxp->fDeferredStatus)) { | |
| status = rxp->fDeferredStatus; | |
| } | |
| } | |
| static const UChar chAmp = 0x26; // '&' | |
| static const UChar chDash = 0x2d; // '-' | |
| //------------------------------------------------------------------------------ | |
| // | |
| // Destructor | |
| // | |
| //------------------------------------------------------------------------------ | |
| RegexCompile::~RegexCompile() { | |
| delete fCaptureName; // Normally will be NULL, but can exist if pattern | |
| // compilation stops with a syntax error. | |
| } | |
| static inline void addCategory(UnicodeSet *set, int32_t value, UErrorCode& ec) { | |
| set->addAll(UnicodeSet().applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, value, ec)); | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // Compile regex pattern. The state machine for rexexp pattern parsing is here. | |
| // The state tables are hand-written in the file regexcst.txt, | |
| // and converted to the form used here by a perl | |
| // script regexcst.pl | |
| // | |
| //------------------------------------------------------------------------------ | |
| void RegexCompile::compile( | |
| const UnicodeString &pat, // Source pat to be compiled. | |
| UParseError &pp, // Error position info | |
| UErrorCode &e) // Error Code | |
| { | |
| fRXPat->fPatternString = new UnicodeString(pat); | |
| UText patternText = UTEXT_INITIALIZER; | |
| utext_openConstUnicodeString(&patternText, fRXPat->fPatternString, &e); | |
| if (U_SUCCESS(e)) { | |
| compile(&patternText, pp, e); | |
| utext_close(&patternText); | |
| } | |
| } | |
| // | |
| // compile, UText mode | |
| // All the work is actually done here. | |
| // | |
| void RegexCompile::compile( | |
| UText *pat, // Source pat to be compiled. | |
| UParseError &pp, // Error position info | |
| UErrorCode &e) // Error Code | |
| { | |
| fStatus = &e; | |
| fParseErr = &pp; | |
| fStackPtr = 0; | |
| fStack[fStackPtr] = 0; | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| // There should be no pattern stuff in the RegexPattern object. They can not be reused. | |
| U_ASSERT(fRXPat->fPattern == NULL || utext_nativeLength(fRXPat->fPattern) == 0); | |
| // Prepare the RegexPattern object to receive the compiled pattern. | |
| fRXPat->fPattern = utext_clone(fRXPat->fPattern, pat, FALSE, TRUE, fStatus); | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| fRXPat->fStaticSets = RegexStaticSets::gStaticSets->fPropSets; | |
| fRXPat->fStaticSets8 = RegexStaticSets::gStaticSets->fPropSets8; | |
| // Initialize the pattern scanning state machine | |
| fPatternLength = utext_nativeLength(pat); | |
| uint16_t state = 1; | |
| const RegexTableEl *tableEl; | |
| // UREGEX_LITERAL force entire pattern to be treated as a literal string. | |
| if (fModeFlags & UREGEX_LITERAL) { | |
| fQuoteMode = TRUE; | |
| } | |
| nextChar(fC); // Fetch the first char from the pattern string. | |
| // | |
| // Main loop for the regex pattern parsing state machine. | |
| // Runs once per state transition. | |
| // Each time through optionally performs, depending on the state table, | |
| // - an advance to the the next pattern char | |
| // - an action to be performed. | |
| // - pushing or popping a state to/from the local state return stack. | |
| // file regexcst.txt is the source for the state table. The logic behind | |
| // recongizing the pattern syntax is there, not here. | |
| // | |
| for (;;) { | |
| // Bail out if anything has gone wrong. | |
| // Regex pattern parsing stops on the first error encountered. | |
| if (U_FAILURE(*fStatus)) { | |
| break; | |
| } | |
| U_ASSERT(state != 0); | |
| // Find the state table element that matches the input char from the pattern, or the | |
| // class of the input character. Start with the first table row for this | |
| // state, then linearly scan forward until we find a row that matches the | |
| // character. The last row for each state always matches all characters, so | |
| // the search will stop there, if not before. | |
| // | |
| tableEl = &gRuleParseStateTable[state]; | |
| REGEX_SCAN_DEBUG_PRINTF(("char, line, col = (\'%c\', %d, %d) state=%s ", | |
| fC.fChar, fLineNum, fCharNum, RegexStateNames[state])); | |
| for (;;) { // loop through table rows belonging to this state, looking for one | |
| // that matches the current input char. | |
| REGEX_SCAN_DEBUG_PRINTF((".")); | |
| if (tableEl->fCharClass < 127 && fC.fQuoted == FALSE && tableEl->fCharClass == fC.fChar) { | |
| // Table row specified an individual character, not a set, and | |
| // the input character is not quoted, and | |
| // the input character matched it. | |
| break; | |
| } | |
| if (tableEl->fCharClass == 255) { | |
| // Table row specified default, match anything character class. | |
| break; | |
| } | |
| if (tableEl->fCharClass == 254 && fC.fQuoted) { | |
| // Table row specified "quoted" and the char was quoted. | |
| break; | |
| } | |
| if (tableEl->fCharClass == 253 && fC.fChar == (UChar32)-1) { | |
| // Table row specified eof and we hit eof on the input. | |
| break; | |
| } | |
| if (tableEl->fCharClass >= 128 && tableEl->fCharClass < 240 && // Table specs a char class && | |
| fC.fQuoted == FALSE && // char is not escaped && | |
| fC.fChar != (UChar32)-1) { // char is not EOF | |
| U_ASSERT(tableEl->fCharClass <= 137); | |
| if (RegexStaticSets::gStaticSets->fRuleSets[tableEl->fCharClass-128].contains(fC.fChar)) { | |
| // Table row specified a character class, or set of characters, | |
| // and the current char matches it. | |
| break; | |
| } | |
| } | |
| // No match on this row, advance to the next row for this state, | |
| tableEl++; | |
| } | |
| REGEX_SCAN_DEBUG_PRINTF(("\n")); | |
| // | |
| // We've found the row of the state table that matches the current input | |
| // character from the rules string. | |
| // Perform any action specified by this row in the state table. | |
| if (doParseActions(tableEl->fAction) == FALSE) { | |
| // Break out of the state machine loop if the | |
| // the action signalled some kind of error, or | |
| // the action was to exit, occurs on normal end-of-rules-input. | |
| break; | |
| } | |
| if (tableEl->fPushState != 0) { | |
| fStackPtr++; | |
| if (fStackPtr >= kStackSize) { | |
| error(U_REGEX_INTERNAL_ERROR); | |
| REGEX_SCAN_DEBUG_PRINTF(("RegexCompile::parse() - state stack overflow.\n")); | |
| fStackPtr--; | |
| } | |
| fStack[fStackPtr] = tableEl->fPushState; | |
| } | |
| // | |
| // NextChar. This is where characters are actually fetched from the pattern. | |
| // Happens under control of the 'n' tag in the state table. | |
| // | |
| if (tableEl->fNextChar) { | |
| nextChar(fC); | |
| } | |
| // Get the next state from the table entry, or from the | |
| // state stack if the next state was specified as "pop". | |
| if (tableEl->fNextState != 255) { | |
| state = tableEl->fNextState; | |
| } else { | |
| state = fStack[fStackPtr]; | |
| fStackPtr--; | |
| if (fStackPtr < 0) { | |
| // state stack underflow | |
| // This will occur if the user pattern has mis-matched parentheses, | |
| // with extra close parens. | |
| // | |
| fStackPtr++; | |
| error(U_REGEX_MISMATCHED_PAREN); | |
| } | |
| } | |
| } | |
| if (U_FAILURE(*fStatus)) { | |
| // Bail out if the pattern had errors. | |
| // Set stack cleanup: a successful compile would have left it empty, | |
| // but errors can leave temporary sets hanging around. | |
| while (!fSetStack.empty()) { | |
| delete (UnicodeSet *)fSetStack.pop(); | |
| } | |
| return; | |
| } | |
| // | |
| // The pattern has now been read and processed, and the compiled code generated. | |
| // | |
| // | |
| // The pattern's fFrameSize so far has accumulated the requirements for | |
| // storage for capture parentheses, counters, etc. that are encountered | |
| // in the pattern. Add space for the two variables that are always | |
| // present in the saved state: the input string position (int64_t) and | |
| // the position in the compiled pattern. | |
| // | |
| allocateStackData(RESTACKFRAME_HDRCOUNT); | |
| // | |
| // Optimization pass 1: NOPs, back-references, and case-folding | |
| // | |
| stripNOPs(); | |
| // | |
| // Get bounds for the minimum and maximum length of a string that this | |
| // pattern can match. Used to avoid looking for matches in strings that | |
| // are too short. | |
| // | |
| fRXPat->fMinMatchLen = minMatchLength(3, fRXPat->fCompiledPat->size()-1); | |
| // | |
| // Optimization pass 2: match start type | |
| // | |
| matchStartType(); | |
| // | |
| // Set up fast latin-1 range sets | |
| // | |
| int32_t numSets = fRXPat->fSets->size(); | |
| fRXPat->fSets8 = new Regex8BitSet[numSets]; | |
| // Null pointer check. | |
| if (fRXPat->fSets8 == NULL) { | |
| e = *fStatus = U_MEMORY_ALLOCATION_ERROR; | |
| return; | |
| } | |
| int32_t i; | |
| for (i=0; i<numSets; i++) { | |
| UnicodeSet *s = (UnicodeSet *)fRXPat->fSets->elementAt(i); | |
| fRXPat->fSets8[i].init(s); | |
| } | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // doParseAction Do some action during regex pattern parsing. | |
| // Called by the parse state machine. | |
| // | |
| // Generation of the match engine PCode happens here, or | |
| // in functions called from the parse actions defined here. | |
| // | |
| // | |
| //------------------------------------------------------------------------------ | |
| UBool RegexCompile::doParseActions(int32_t action) | |
| { | |
| UBool returnVal = TRUE; | |
| switch ((Regex_PatternParseAction)action) { | |
| case doPatStart: | |
| // Start of pattern compiles to: | |
| //0 SAVE 2 Fall back to position of FAIL | |
| //1 jmp 3 | |
| //2 FAIL Stop if we ever reach here. | |
| //3 NOP Dummy, so start of pattern looks the same as | |
| // the start of an ( grouping. | |
| //4 NOP Resreved, will be replaced by a save if there are | |
| // OR | operators at the top level | |
| appendOp(URX_STATE_SAVE, 2); | |
| appendOp(URX_JMP, 3); | |
| appendOp(URX_FAIL, 0); | |
| // Standard open nonCapture paren action emits the two NOPs and | |
| // sets up the paren stack frame. | |
| doParseActions(doOpenNonCaptureParen); | |
| break; | |
| case doPatFinish: | |
| // We've scanned to the end of the pattern | |
| // The end of pattern compiles to: | |
| // URX_END | |
| // which will stop the runtime match engine. | |
| // Encountering end of pattern also behaves like a close paren, | |
| // and forces fixups of the State Save at the beginning of the compiled pattern | |
| // and of any OR operations at the top level. | |
| // | |
| handleCloseParen(); | |
| if (fParenStack.size() > 0) { | |
| // Missing close paren in pattern. | |
| error(U_REGEX_MISMATCHED_PAREN); | |
| } | |
| // add the END operation to the compiled pattern. | |
| appendOp(URX_END, 0); | |
| // Terminate the pattern compilation state machine. | |
| returnVal = FALSE; | |
| break; | |
| case doOrOperator: | |
| // Scanning a '|', as in (A|B) | |
| { | |
| // Generate code for any pending literals preceding the '|' | |
| fixLiterals(FALSE); | |
| // Insert a SAVE operation at the start of the pattern section preceding | |
| // this OR at this level. This SAVE will branch the match forward | |
| // to the right hand side of the OR in the event that the left hand | |
| // side fails to match and backtracks. Locate the position for the | |
| // save from the location on the top of the parentheses stack. | |
| int32_t savePosition = fParenStack.popi(); | |
| int32_t op = (int32_t)fRXPat->fCompiledPat->elementAti(savePosition); | |
| U_ASSERT(URX_TYPE(op) == URX_NOP); // original contents of reserved location | |
| op = buildOp(URX_STATE_SAVE, fRXPat->fCompiledPat->size()+1); | |
| fRXPat->fCompiledPat->setElementAt(op, savePosition); | |
| // Append an JMP operation into the compiled pattern. The operand for | |
| // the JMP will eventually be the location following the ')' for the | |
| // group. This will be patched in later, when the ')' is encountered. | |
| appendOp(URX_JMP, 0); | |
| // Push the position of the newly added JMP op onto the parentheses stack. | |
| // This registers if for fixup when this block's close paren is encountered. | |
| fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); | |
| // Append a NOP to the compiled pattern. This is the slot reserved | |
| // for a SAVE in the event that there is yet another '|' following | |
| // this one. | |
| appendOp(URX_NOP, 0); | |
| fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); | |
| } | |
| break; | |
| case doBeginNamedCapture: | |
| // Scanning (?<letter. | |
| // The first letter of the name will come through again under doConinueNamedCapture. | |
| fCaptureName = new UnicodeString(); | |
| if (fCaptureName == NULL) { | |
| error(U_MEMORY_ALLOCATION_ERROR); | |
| } | |
| break; | |
| case doContinueNamedCapture: | |
| fCaptureName->append(fC.fChar); | |
| break; | |
| case doBadNamedCapture: | |
| error(U_REGEX_INVALID_CAPTURE_GROUP_NAME); | |
| break; | |
| case doOpenCaptureParen: | |
| // Open Capturing Paren, possibly named. | |
| // Compile to a | |
| // - NOP, which later may be replaced by a save-state if the | |
| // parenthesized group gets a * quantifier, followed by | |
| // - START_CAPTURE n where n is stack frame offset to the capture group variables. | |
| // - NOP, which may later be replaced by a save-state if there | |
| // is an '|' alternation within the parens. | |
| // | |
| // Each capture group gets three slots in the save stack frame: | |
| // 0: Capture Group start position (in input string being matched.) | |
| // 1: Capture Group end position. | |
| // 2: Start of Match-in-progress. | |
| // The first two locations are for a completed capture group, and are | |
| // referred to by back references and the like. | |
| // The third location stores the capture start position when an START_CAPTURE is | |
| // encountered. This will be promoted to a completed capture when (and if) the corresponding | |
| // END_CAPTURE is encountered. | |
| { | |
| fixLiterals(); | |
| appendOp(URX_NOP, 0); | |
| int32_t varsLoc = allocateStackData(3); // Reserve three slots in match stack frame. | |
| appendOp(URX_START_CAPTURE, varsLoc); | |
| appendOp(URX_NOP, 0); | |
| // On the Parentheses stack, start a new frame and add the postions | |
| // of the two NOPs. Depending on what follows in the pattern, the | |
| // NOPs may be changed to SAVE_STATE or JMP ops, with a target | |
| // address of the end of the parenthesized group. | |
| fParenStack.push(fModeFlags, *fStatus); // Match mode state | |
| fParenStack.push(capturing, *fStatus); // Frame type. | |
| fParenStack.push(fRXPat->fCompiledPat->size()-3, *fStatus); // The first NOP location | |
| fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); // The second NOP loc | |
| // Save the mapping from group number to stack frame variable position. | |
| fRXPat->fGroupMap->addElement(varsLoc, *fStatus); | |
| // If this is a named capture group, add the name->group number mapping. | |
| if (fCaptureName != NULL) { | |
| int32_t groupNumber = fRXPat->fGroupMap->size(); | |
| int32_t previousMapping = uhash_puti(fRXPat->fNamedCaptureMap, fCaptureName, groupNumber, fStatus); | |
| fCaptureName = NULL; // hash table takes ownership of the name (key) string. | |
| if (previousMapping > 0 && U_SUCCESS(*fStatus)) { | |
| error(U_REGEX_INVALID_CAPTURE_GROUP_NAME); | |
| } | |
| } | |
| } | |
| break; | |
| case doOpenNonCaptureParen: | |
| // Open non-caputuring (grouping only) Paren. | |
| // Compile to a | |
| // - NOP, which later may be replaced by a save-state if the | |
| // parenthesized group gets a * quantifier, followed by | |
| // - NOP, which may later be replaced by a save-state if there | |
| // is an '|' alternation within the parens. | |
| { | |
| fixLiterals(); | |
| appendOp(URX_NOP, 0); | |
| appendOp(URX_NOP, 0); | |
| // On the Parentheses stack, start a new frame and add the postions | |
| // of the two NOPs. | |
| fParenStack.push(fModeFlags, *fStatus); // Match mode state | |
| fParenStack.push(plain, *fStatus); // Begin a new frame. | |
| fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus); // The first NOP location | |
| fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); // The second NOP loc | |
| } | |
| break; | |
| case doOpenAtomicParen: | |
| // Open Atomic Paren. (?> | |
| // Compile to a | |
| // - NOP, which later may be replaced if the parenthesized group | |
| // has a quantifier, followed by | |
| // - STO_SP save state stack position, so it can be restored at the ")" | |
| // - NOP, which may later be replaced by a save-state if there | |
| // is an '|' alternation within the parens. | |
| { | |
| fixLiterals(); | |
| appendOp(URX_NOP, 0); | |
| int32_t varLoc = allocateData(1); // Reserve a data location for saving the state stack ptr. | |
| appendOp(URX_STO_SP, varLoc); | |
| appendOp(URX_NOP, 0); | |
| // On the Parentheses stack, start a new frame and add the postions | |
| // of the two NOPs. Depending on what follows in the pattern, the | |
| // NOPs may be changed to SAVE_STATE or JMP ops, with a target | |
| // address of the end of the parenthesized group. | |
| fParenStack.push(fModeFlags, *fStatus); // Match mode state | |
| fParenStack.push(atomic, *fStatus); // Frame type. | |
| fParenStack.push(fRXPat->fCompiledPat->size()-3, *fStatus); // The first NOP | |
| fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); // The second NOP | |
| } | |
| break; | |
| case doOpenLookAhead: | |
| // Positive Look-ahead (?= stuff ) | |
| // | |
| // Note: Addition of transparent input regions, with the need to | |
| // restore the original regions when failing out of a lookahead | |
| // block, complicated this sequence. Some conbined opcodes | |
| // might make sense - or might not, lookahead aren't that common. | |
| // | |
| // Caution: min match length optimization knows about this | |
| // sequence; don't change without making updates there too. | |
| // | |
| // Compiles to | |
| // 1 START_LA dataLoc Saves SP, Input Pos | |
| // 2. STATE_SAVE 4 on failure of lookahead, goto 4 | |
| // 3 JMP 6 continue ... | |
| // | |
| // 4. LA_END Look Ahead failed. Restore regions. | |
| // 5. BACKTRACK and back track again. | |
| // | |
| // 6. NOP reserved for use by quantifiers on the block. | |
| // Look-ahead can't have quantifiers, but paren stack | |
| // compile time conventions require the slot anyhow. | |
| // 7. NOP may be replaced if there is are '|' ops in the block. | |
| // 8. code for parenthesized stuff. | |
| // 9. LA_END | |
| // | |
| // Two data slots are reserved, for saving the stack ptr and the input position. | |
| { | |
| fixLiterals(); | |
| int32_t dataLoc = allocateData(2); | |
| appendOp(URX_LA_START, dataLoc); | |
| appendOp(URX_STATE_SAVE, fRXPat->fCompiledPat->size()+ 2); | |
| appendOp(URX_JMP, fRXPat->fCompiledPat->size()+ 3); | |
| appendOp(URX_LA_END, dataLoc); | |
| appendOp(URX_BACKTRACK, 0); | |
| appendOp(URX_NOP, 0); | |
| appendOp(URX_NOP, 0); | |
| // On the Parentheses stack, start a new frame and add the postions | |
| // of the NOPs. | |
| fParenStack.push(fModeFlags, *fStatus); // Match mode state | |
| fParenStack.push(lookAhead, *fStatus); // Frame type. | |
| fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus); // The first NOP location | |
| fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); // The second NOP location | |
| } | |
| break; | |
| case doOpenLookAheadNeg: | |
| // Negated Lookahead. (?! stuff ) | |
| // Compiles to | |
| // 1. START_LA dataloc | |
| // 2. SAVE_STATE 7 // Fail within look-ahead block restores to this state, | |
| // // which continues with the match. | |
| // 3. NOP // Std. Open Paren sequence, for possible '|' | |
| // 4. code for parenthesized stuff. | |
| // 5. END_LA // Cut back stack, remove saved state from step 2. | |
| // 6. BACKTRACK // code in block succeeded, so neg. lookahead fails. | |
| // 7. END_LA // Restore match region, in case look-ahead was using | |
| // an alternate (transparent) region. | |
| { | |
| fixLiterals(); | |
| int32_t dataLoc = allocateData(2); | |
| appendOp(URX_LA_START, dataLoc); | |
| appendOp(URX_STATE_SAVE, 0); // dest address will be patched later. | |
| appendOp(URX_NOP, 0); | |
| // On the Parentheses stack, start a new frame and add the postions | |
| // of the StateSave and NOP. | |
| fParenStack.push(fModeFlags, *fStatus); // Match mode state | |
| fParenStack.push(negLookAhead, *fStatus); // Frame type | |
| fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus); // The STATE_SAVE location | |
| fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); // The second NOP location | |
| // Instructions #5 - #7 will be added when the ')' is encountered. | |
| } | |
| break; | |
| case doOpenLookBehind: | |
| { | |
| // Compile a (?<= look-behind open paren. | |
| // | |
| // Compiles to | |
| // 0 URX_LB_START dataLoc | |
| // 1 URX_LB_CONT dataLoc | |
| // 2 MinMatchLen | |
| // 3 MaxMatchLen | |
| // 4 URX_NOP Standard '(' boilerplate. | |
| // 5 URX_NOP Reserved slot for use with '|' ops within (block). | |
| // 6 <code for LookBehind expression> | |
| // 7 URX_LB_END dataLoc # Check match len, restore input len | |
| // 8 URX_LA_END dataLoc # Restore stack, input pos | |
| // | |
| // Allocate a block of matcher data, to contain (when running a match) | |
| // 0: Stack ptr on entry | |
| // 1: Input Index on entry | |
| // 2: Start index of match current match attempt. | |
| // 3: Original Input String len. | |
| // Generate match code for any pending literals. | |
| fixLiterals(); | |
| // Allocate data space | |
| int32_t dataLoc = allocateData(4); | |
| // Emit URX_LB_START | |
| appendOp(URX_LB_START, dataLoc); | |
| // Emit URX_LB_CONT | |
| appendOp(URX_LB_CONT, dataLoc); | |
| appendOp(URX_RESERVED_OP, 0); // MinMatchLength. To be filled later. | |
| appendOp(URX_RESERVED_OP, 0); // MaxMatchLength. To be filled later. | |
| // Emit the NOPs | |
| appendOp(URX_NOP, 0); | |
| appendOp(URX_NOP, 0); | |
| // On the Parentheses stack, start a new frame and add the postions | |
| // of the URX_LB_CONT and the NOP. | |
| fParenStack.push(fModeFlags, *fStatus); // Match mode state | |
| fParenStack.push(lookBehind, *fStatus); // Frame type | |
| fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus); // The first NOP location | |
| fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); // The 2nd NOP location | |
| // The final two instructions will be added when the ')' is encountered. | |
| } | |
| break; | |
| case doOpenLookBehindNeg: | |
| { | |
| // Compile a (?<! negated look-behind open paren. | |
| // | |
| // Compiles to | |
| // 0 URX_LB_START dataLoc # Save entry stack, input len | |
| // 1 URX_LBN_CONT dataLoc # Iterate possible match positions | |
| // 2 MinMatchLen | |
| // 3 MaxMatchLen | |
| // 4 continueLoc (9) | |
| // 5 URX_NOP Standard '(' boilerplate. | |
| // 6 URX_NOP Reserved slot for use with '|' ops within (block). | |
| // 7 <code for LookBehind expression> | |
| // 8 URX_LBN_END dataLoc # Check match len, cause a FAIL | |
| // 9 ... | |
| // | |
| // Allocate a block of matcher data, to contain (when running a match) | |
| // 0: Stack ptr on entry | |
| // 1: Input Index on entry | |
| // 2: Start index of match current match attempt. | |
| // 3: Original Input String len. | |
| // Generate match code for any pending literals. | |
| fixLiterals(); | |
| // Allocate data space | |
| int32_t dataLoc = allocateData(4); | |
| // Emit URX_LB_START | |
| appendOp(URX_LB_START, dataLoc); | |
| // Emit URX_LBN_CONT | |
| appendOp(URX_LBN_CONT, dataLoc); | |
| appendOp(URX_RESERVED_OP, 0); // MinMatchLength. To be filled later. | |
| appendOp(URX_RESERVED_OP, 0); // MaxMatchLength. To be filled later. | |
| appendOp(URX_RESERVED_OP, 0); // Continue Loc. To be filled later. | |
| // Emit the NOPs | |
| appendOp(URX_NOP, 0); | |
| appendOp(URX_NOP, 0); | |
| // On the Parentheses stack, start a new frame and add the postions | |
| // of the URX_LB_CONT and the NOP. | |
| fParenStack.push(fModeFlags, *fStatus); // Match mode state | |
| fParenStack.push(lookBehindN, *fStatus); // Frame type | |
| fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus); // The first NOP location | |
| fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); // The 2nd NOP location | |
| // The final two instructions will be added when the ')' is encountered. | |
| } | |
| break; | |
| case doConditionalExpr: | |
| // Conditionals such as (?(1)a:b) | |
| case doPerlInline: | |
| // Perl inline-condtionals. (?{perl code}a|b) We're not perl, no way to do them. | |
| error(U_REGEX_UNIMPLEMENTED); | |
| break; | |
| case doCloseParen: | |
| handleCloseParen(); | |
| if (fParenStack.size() <= 0) { | |
| // Extra close paren, or missing open paren. | |
| error(U_REGEX_MISMATCHED_PAREN); | |
| } | |
| break; | |
| case doNOP: | |
| break; | |
| case doBadOpenParenType: | |
| case doRuleError: | |
| error(U_REGEX_RULE_SYNTAX); | |
| break; | |
| case doMismatchedParenErr: | |
| error(U_REGEX_MISMATCHED_PAREN); | |
| break; | |
| case doPlus: | |
| // Normal '+' compiles to | |
| // 1. stuff to be repeated (already built) | |
| // 2. jmp-sav 1 | |
| // 3. ... | |
| // | |
| // Or, if the item to be repeated can match a zero length string, | |
| // 1. STO_INP_LOC data-loc | |
| // 2. body of stuff to be repeated | |
| // 3. JMP_SAV_X 2 | |
| // 4. ... | |
| // | |
| // Or, if the item to be repeated is simple | |
| // 1. Item to be repeated. | |
| // 2. LOOP_SR_I set number (assuming repeated item is a set ref) | |
| // 3. LOOP_C stack location | |
| { | |
| int32_t topLoc = blockTopLoc(FALSE); // location of item #1 | |
| int32_t frameLoc; | |
| // Check for simple constructs, which may get special optimized code. | |
| if (topLoc == fRXPat->fCompiledPat->size() - 1) { | |
| int32_t repeatedOp = (int32_t)fRXPat->fCompiledPat->elementAti(topLoc); | |
| if (URX_TYPE(repeatedOp) == URX_SETREF) { | |
| // Emit optimized code for [char set]+ | |
| appendOp(URX_LOOP_SR_I, URX_VAL(repeatedOp)); | |
| frameLoc = allocateStackData(1); | |
| appendOp(URX_LOOP_C, frameLoc); | |
| break; | |
| } | |
| if (URX_TYPE(repeatedOp) == URX_DOTANY || | |
| URX_TYPE(repeatedOp) == URX_DOTANY_ALL || | |
| URX_TYPE(repeatedOp) == URX_DOTANY_UNIX) { | |
| // Emit Optimized code for .+ operations. | |
| int32_t loopOpI = buildOp(URX_LOOP_DOT_I, 0); | |
| if (URX_TYPE(repeatedOp) == URX_DOTANY_ALL) { | |
| // URX_LOOP_DOT_I operand is a flag indicating ". matches any" mode. | |
| loopOpI |= 1; | |
| } | |
| if (fModeFlags & UREGEX_UNIX_LINES) { | |
| loopOpI |= 2; | |
| } | |
| appendOp(loopOpI); | |
| frameLoc = allocateStackData(1); | |
| appendOp(URX_LOOP_C, frameLoc); | |
| break; | |
| } | |
| } | |
| // General case. | |
| // Check for minimum match length of zero, which requires | |
| // extra loop-breaking code. | |
| if (minMatchLength(topLoc, fRXPat->fCompiledPat->size()-1) == 0) { | |
| // Zero length match is possible. | |
| // Emit the code sequence that can handle it. | |
| insertOp(topLoc); | |
| frameLoc = allocateStackData(1); | |
| int32_t op = buildOp(URX_STO_INP_LOC, frameLoc); | |
| fRXPat->fCompiledPat->setElementAt(op, topLoc); | |
| appendOp(URX_JMP_SAV_X, topLoc+1); | |
| } else { | |
| // Simpler code when the repeated body must match something non-empty | |
| appendOp(URX_JMP_SAV, topLoc); | |
| } | |
| } | |
| break; | |
| case doNGPlus: | |
| // Non-greedy '+?' compiles to | |
| // 1. stuff to be repeated (already built) | |
| // 2. state-save 1 | |
| // 3. ... | |
| { | |
| int32_t topLoc = blockTopLoc(FALSE); | |
| appendOp(URX_STATE_SAVE, topLoc); | |
| } | |
| break; | |
| case doOpt: | |
| // Normal (greedy) ? quantifier. | |
| // Compiles to | |
| // 1. state save 3 | |
| // 2. body of optional block | |
| // 3. ... | |
| // Insert the state save into the compiled pattern, and we're done. | |
| { | |
| int32_t saveStateLoc = blockTopLoc(TRUE); | |
| int32_t saveStateOp = buildOp(URX_STATE_SAVE, fRXPat->fCompiledPat->size()); | |
| fRXPat->fCompiledPat->setElementAt(saveStateOp, saveStateLoc); | |
| } | |
| break; | |
| case doNGOpt: | |
| // Non-greedy ?? quantifier | |
| // compiles to | |
| // 1. jmp 4 | |
| // 2. body of optional block | |
| // 3 jmp 5 | |
| // 4. state save 2 | |
| // 5 ... | |
| // This code is less than ideal, with two jmps instead of one, because we can only | |
| // insert one instruction at the top of the block being iterated. | |
| { | |
| int32_t jmp1_loc = blockTopLoc(TRUE); | |
| int32_t jmp2_loc = fRXPat->fCompiledPat->size(); | |
| int32_t jmp1_op = buildOp(URX_JMP, jmp2_loc+1); | |
| fRXPat->fCompiledPat->setElementAt(jmp1_op, jmp1_loc); | |
| appendOp(URX_JMP, jmp2_loc+2); | |
| appendOp(URX_STATE_SAVE, jmp1_loc+1); | |
| } | |
| break; | |
| case doStar: | |
| // Normal (greedy) * quantifier. | |
| // Compiles to | |
| // 1. STATE_SAVE 4 | |
| // 2. body of stuff being iterated over | |
| // 3. JMP_SAV 2 | |
| // 4. ... | |
| // | |
| // Or, if the body is a simple [Set], | |
| // 1. LOOP_SR_I set number | |
| // 2. LOOP_C stack location | |
| // ... | |
| // | |
| // Or if this is a .* | |
| // 1. LOOP_DOT_I (. matches all mode flag) | |
| // 2. LOOP_C stack location | |
| // | |
| // Or, if the body can match a zero-length string, to inhibit infinite loops, | |
| // 1. STATE_SAVE 5 | |
| // 2. STO_INP_LOC data-loc | |
| // 3. body of stuff | |
| // 4. JMP_SAV_X 2 | |
| // 5. ... | |
| { | |
| // location of item #1, the STATE_SAVE | |
| int32_t topLoc = blockTopLoc(FALSE); | |
| int32_t dataLoc = -1; | |
| // Check for simple *, where the construct being repeated | |
| // compiled to single opcode, and might be optimizable. | |
| if (topLoc == fRXPat->fCompiledPat->size() - 1) { | |
| int32_t repeatedOp = (int32_t)fRXPat->fCompiledPat->elementAti(topLoc); | |
| if (URX_TYPE(repeatedOp) == URX_SETREF) { | |
| // Emit optimized code for a [char set]* | |
| int32_t loopOpI = buildOp(URX_LOOP_SR_I, URX_VAL(repeatedOp)); | |
| fRXPat->fCompiledPat->setElementAt(loopOpI, topLoc); | |
| dataLoc = allocateStackData(1); | |
| appendOp(URX_LOOP_C, dataLoc); | |
| break; | |
| } | |
| if (URX_TYPE(repeatedOp) == URX_DOTANY || | |
| URX_TYPE(repeatedOp) == URX_DOTANY_ALL || | |
| URX_TYPE(repeatedOp) == URX_DOTANY_UNIX) { | |
| // Emit Optimized code for .* operations. | |
| int32_t loopOpI = buildOp(URX_LOOP_DOT_I, 0); | |
| if (URX_TYPE(repeatedOp) == URX_DOTANY_ALL) { | |
| // URX_LOOP_DOT_I operand is a flag indicating . matches any mode. | |
| loopOpI |= 1; | |
| } | |
| if ((fModeFlags & UREGEX_UNIX_LINES) != 0) { | |
| loopOpI |= 2; | |
| } | |
| fRXPat->fCompiledPat->setElementAt(loopOpI, topLoc); | |
| dataLoc = allocateStackData(1); | |
| appendOp(URX_LOOP_C, dataLoc); | |
| break; | |
| } | |
| } | |
| // Emit general case code for this * | |
| // The optimizations did not apply. | |
| int32_t saveStateLoc = blockTopLoc(TRUE); | |
| int32_t jmpOp = buildOp(URX_JMP_SAV, saveStateLoc+1); | |
| // Check for minimum match length of zero, which requires | |
| // extra loop-breaking code. | |
| if (minMatchLength(saveStateLoc, fRXPat->fCompiledPat->size()-1) == 0) { | |
| insertOp(saveStateLoc); | |
| dataLoc = allocateStackData(1); | |
| int32_t op = buildOp(URX_STO_INP_LOC, dataLoc); | |
| fRXPat->fCompiledPat->setElementAt(op, saveStateLoc+1); | |
| jmpOp = buildOp(URX_JMP_SAV_X, saveStateLoc+2); | |
| } | |
| // Locate the position in the compiled pattern where the match will continue | |
| // after completing the *. (4 or 5 in the comment above) | |
| int32_t continueLoc = fRXPat->fCompiledPat->size()+1; | |
| // Put together the save state op and store it into the compiled code. | |
| int32_t saveStateOp = buildOp(URX_STATE_SAVE, continueLoc); | |
| fRXPat->fCompiledPat->setElementAt(saveStateOp, saveStateLoc); | |
| // Append the URX_JMP_SAV or URX_JMPX operation to the compiled pattern. | |
| appendOp(jmpOp); | |
| } | |
| break; | |
| case doNGStar: | |
| // Non-greedy *? quantifier | |
| // compiles to | |
| // 1. JMP 3 | |
| // 2. body of stuff being iterated over | |
| // 3. STATE_SAVE 2 | |
| // 4 ... | |
| { | |
| int32_t jmpLoc = blockTopLoc(TRUE); // loc 1. | |
| int32_t saveLoc = fRXPat->fCompiledPat->size(); // loc 3. | |
| int32_t jmpOp = buildOp(URX_JMP, saveLoc); | |
| fRXPat->fCompiledPat->setElementAt(jmpOp, jmpLoc); | |
| appendOp(URX_STATE_SAVE, jmpLoc+1); | |
| } | |
| break; | |
| case doIntervalInit: | |
| // The '{' opening an interval quantifier was just scanned. | |
| // Init the counter varaiables that will accumulate the values as the digits | |
| // are scanned. | |
| fIntervalLow = 0; | |
| fIntervalUpper = -1; | |
| break; | |
| case doIntevalLowerDigit: | |
| // Scanned a digit from the lower value of an {lower,upper} interval | |
| { | |
| int32_t digitValue = u_charDigitValue(fC.fChar); | |
| U_ASSERT(digitValue >= 0); | |
| int64_t val = (int64_t)fIntervalLow*10 + digitValue; | |
| if (val > INT32_MAX) { | |
| error(U_REGEX_NUMBER_TOO_BIG); | |
| } else { | |
| fIntervalLow = (int32_t)val; | |
| } | |
| } | |
| break; | |
| case doIntervalUpperDigit: | |
| // Scanned a digit from the upper value of an {lower,upper} interval | |
| { | |
| if (fIntervalUpper < 0) { | |
| fIntervalUpper = 0; | |
| } | |
| int32_t digitValue = u_charDigitValue(fC.fChar); | |
| U_ASSERT(digitValue >= 0); | |
| int64_t val = (int64_t)fIntervalUpper*10 + digitValue; | |
| if (val > INT32_MAX) { | |
| error(U_REGEX_NUMBER_TOO_BIG); | |
| } else { | |
| fIntervalUpper = (int32_t)val; | |
| } | |
| } | |
| break; | |
| case doIntervalSame: | |
| // Scanned a single value interval like {27}. Upper = Lower. | |
| fIntervalUpper = fIntervalLow; | |
| break; | |
| case doInterval: | |
| // Finished scanning a normal {lower,upper} interval. Generate the code for it. | |
| if (compileInlineInterval() == FALSE) { | |
| compileInterval(URX_CTR_INIT, URX_CTR_LOOP); | |
| } | |
| break; | |
| case doPossessiveInterval: | |
| // Finished scanning a Possessive {lower,upper}+ interval. Generate the code for it. | |
| { | |
| // Remember the loc for the top of the block being looped over. | |
| // (Can not reserve a slot in the compiled pattern at this time, because | |
| // compileInterval needs to reserve also, and blockTopLoc can only reserve | |
| // once per block.) | |
| int32_t topLoc = blockTopLoc(FALSE); | |
| // Produce normal looping code. | |
| compileInterval(URX_CTR_INIT, URX_CTR_LOOP); | |
| // Surround the just-emitted normal looping code with a STO_SP ... LD_SP | |
| // just as if the loop was inclosed in atomic parentheses. | |
| // First the STO_SP before the start of the loop | |
| insertOp(topLoc); | |
| int32_t varLoc = allocateData(1); // Reserve a data location for saving the | |
| int32_t op = buildOp(URX_STO_SP, varLoc); | |
| fRXPat->fCompiledPat->setElementAt(op, topLoc); | |
| int32_t loopOp = (int32_t)fRXPat->fCompiledPat->popi(); | |
| U_ASSERT(URX_TYPE(loopOp) == URX_CTR_LOOP && URX_VAL(loopOp) == topLoc); | |
| loopOp++; // point LoopOp after the just-inserted STO_SP | |
| fRXPat->fCompiledPat->push(loopOp, *fStatus); | |
| // Then the LD_SP after the end of the loop | |
| appendOp(URX_LD_SP, varLoc); | |
| } | |
| break; | |
| case doNGInterval: | |
| // Finished scanning a non-greedy {lower,upper}? interval. Generate the code for it. | |
| compileInterval(URX_CTR_INIT_NG, URX_CTR_LOOP_NG); | |
| break; | |
| case doIntervalError: | |
| error(U_REGEX_BAD_INTERVAL); | |
| break; | |
| case doLiteralChar: | |
| // We've just scanned a "normal" character from the pattern, | |
| literalChar(fC.fChar); | |
| break; | |
| case doEscapedLiteralChar: | |
| // We've just scanned an backslashed escaped character with no | |
| // special meaning. It represents itself. | |
| if ((fModeFlags & UREGEX_ERROR_ON_UNKNOWN_ESCAPES) != 0 && | |
| ((fC.fChar >= 0x41 && fC.fChar<= 0x5A) || // in [A-Z] | |
| (fC.fChar >= 0x61 && fC.fChar <= 0x7a))) { // in [a-z] | |
| error(U_REGEX_BAD_ESCAPE_SEQUENCE); | |
| } | |
| literalChar(fC.fChar); | |
| break; | |
| case doDotAny: | |
| // scanned a ".", match any single character. | |
| { | |
| fixLiterals(FALSE); | |
| if (fModeFlags & UREGEX_DOTALL) { | |
| appendOp(URX_DOTANY_ALL, 0); | |
| } else if (fModeFlags & UREGEX_UNIX_LINES) { | |
| appendOp(URX_DOTANY_UNIX, 0); | |
| } else { | |
| appendOp(URX_DOTANY, 0); | |
| } | |
| } | |
| break; | |
| case doCaret: | |
| { | |
| fixLiterals(FALSE); | |
| if ( (fModeFlags & UREGEX_MULTILINE) == 0 && (fModeFlags & UREGEX_UNIX_LINES) == 0) { | |
| appendOp(URX_CARET, 0); | |
| } else if ((fModeFlags & UREGEX_MULTILINE) != 0 && (fModeFlags & UREGEX_UNIX_LINES) == 0) { | |
| appendOp(URX_CARET_M, 0); | |
| } else if ((fModeFlags & UREGEX_MULTILINE) == 0 && (fModeFlags & UREGEX_UNIX_LINES) != 0) { | |
| appendOp(URX_CARET, 0); // Only testing true start of input. | |
| } else if ((fModeFlags & UREGEX_MULTILINE) != 0 && (fModeFlags & UREGEX_UNIX_LINES) != 0) { | |
| appendOp(URX_CARET_M_UNIX, 0); | |
| } | |
| } | |
| break; | |
| case doDollar: | |
| { | |
| fixLiterals(FALSE); | |
| if ( (fModeFlags & UREGEX_MULTILINE) == 0 && (fModeFlags & UREGEX_UNIX_LINES) == 0) { | |
| appendOp(URX_DOLLAR, 0); | |
| } else if ((fModeFlags & UREGEX_MULTILINE) != 0 && (fModeFlags & UREGEX_UNIX_LINES) == 0) { | |
| appendOp(URX_DOLLAR_M, 0); | |
| } else if ((fModeFlags & UREGEX_MULTILINE) == 0 && (fModeFlags & UREGEX_UNIX_LINES) != 0) { | |
| appendOp(URX_DOLLAR_D, 0); | |
| } else if ((fModeFlags & UREGEX_MULTILINE) != 0 && (fModeFlags & UREGEX_UNIX_LINES) != 0) { | |
| appendOp(URX_DOLLAR_MD, 0); | |
| } | |
| } | |
| break; | |
| case doBackslashA: | |
| fixLiterals(FALSE); | |
| appendOp(URX_CARET, 0); | |
| break; | |
| case doBackslashB: | |
| { | |
| #if UCONFIG_NO_BREAK_ITERATION==1 | |
| if (fModeFlags & UREGEX_UWORD) { | |
| error(U_UNSUPPORTED_ERROR); | |
| } | |
| #endif | |
| fixLiterals(FALSE); | |
| int32_t op = (fModeFlags & UREGEX_UWORD)? URX_BACKSLASH_BU : URX_BACKSLASH_B; | |
| appendOp(op, 1); | |
| } | |
| break; | |
| case doBackslashb: | |
| { | |
| #if UCONFIG_NO_BREAK_ITERATION==1 | |
| if (fModeFlags & UREGEX_UWORD) { | |
| error(U_UNSUPPORTED_ERROR); | |
| } | |
| #endif | |
| fixLiterals(FALSE); | |
| int32_t op = (fModeFlags & UREGEX_UWORD)? URX_BACKSLASH_BU : URX_BACKSLASH_B; | |
| appendOp(op, 0); | |
| } | |
| break; | |
| case doBackslashD: | |
| fixLiterals(FALSE); | |
| appendOp(URX_BACKSLASH_D, 1); | |
| break; | |
| case doBackslashd: | |
| fixLiterals(FALSE); | |
| appendOp(URX_BACKSLASH_D, 0); | |
| break; | |
| case doBackslashG: | |
| fixLiterals(FALSE); | |
| appendOp(URX_BACKSLASH_G, 0); | |
| break; | |
| case doBackslashH: | |
| fixLiterals(FALSE); | |
| appendOp(URX_BACKSLASH_H, 1); | |
| break; | |
| case doBackslashh: | |
| fixLiterals(FALSE); | |
| appendOp(URX_BACKSLASH_H, 0); | |
| break; | |
| case doBackslashR: | |
| fixLiterals(FALSE); | |
| appendOp(URX_BACKSLASH_R, 0); | |
| break; | |
| case doBackslashS: | |
| fixLiterals(FALSE); | |
| appendOp(URX_STAT_SETREF_N, URX_ISSPACE_SET); | |
| break; | |
| case doBackslashs: | |
| fixLiterals(FALSE); | |
| appendOp(URX_STATIC_SETREF, URX_ISSPACE_SET); | |
| break; | |
| case doBackslashV: | |
| fixLiterals(FALSE); | |
| appendOp(URX_BACKSLASH_V, 1); | |
| break; | |
| case doBackslashv: | |
| fixLiterals(FALSE); | |
| appendOp(URX_BACKSLASH_V, 0); | |
| break; | |
| case doBackslashW: | |
| fixLiterals(FALSE); | |
| appendOp(URX_STAT_SETREF_N, URX_ISWORD_SET); | |
| break; | |
| case doBackslashw: | |
| fixLiterals(FALSE); | |
| appendOp(URX_STATIC_SETREF, URX_ISWORD_SET); | |
| break; | |
| case doBackslashX: | |
| fixLiterals(FALSE); | |
| appendOp(URX_BACKSLASH_X, 0); | |
| break; | |
| case doBackslashZ: | |
| fixLiterals(FALSE); | |
| appendOp(URX_DOLLAR, 0); | |
| break; | |
| case doBackslashz: | |
| fixLiterals(FALSE); | |
| appendOp(URX_BACKSLASH_Z, 0); | |
| break; | |
| case doEscapeError: | |
| error(U_REGEX_BAD_ESCAPE_SEQUENCE); | |
| break; | |
| case doExit: | |
| fixLiterals(FALSE); | |
| returnVal = FALSE; | |
| break; | |
| case doProperty: | |
| { | |
| fixLiterals(FALSE); | |
| UnicodeSet *theSet = scanProp(); | |
| compileSet(theSet); | |
| } | |
| break; | |
| case doNamedChar: | |
| { | |
| UChar32 c = scanNamedChar(); | |
| literalChar(c); | |
| } | |
| break; | |
| case doBackRef: | |
| // BackReference. Somewhat unusual in that the front-end can not completely parse | |
| // the regular expression, because the number of digits to be consumed | |
| // depends on the number of capture groups that have been defined. So | |
| // we have to do it here instead. | |
| { | |
| int32_t numCaptureGroups = fRXPat->fGroupMap->size(); | |
| int32_t groupNum = 0; | |
| UChar32 c = fC.fChar; | |
| for (;;) { | |
| // Loop once per digit, for max allowed number of digits in a back reference. | |
| int32_t digit = u_charDigitValue(c); | |
| groupNum = groupNum * 10 + digit; | |
| if (groupNum >= numCaptureGroups) { | |
| break; | |
| } | |
| c = peekCharLL(); | |
| if (RegexStaticSets::gStaticSets->fRuleDigitsAlias->contains(c) == FALSE) { | |
| break; | |
| } | |
| nextCharLL(); | |
| } | |
| // Scan of the back reference in the source regexp is complete. Now generate | |
| // the compiled code for it. | |
| // Because capture groups can be forward-referenced by back-references, | |
| // we fill the operand with the capture group number. At the end | |
| // of compilation, it will be changed to the variable's location. | |
| U_ASSERT(groupNum > 0); // Shouldn't happen. '\0' begins an octal escape sequence, | |
| // and shouldn't enter this code path at all. | |
| fixLiterals(FALSE); | |
| if (fModeFlags & UREGEX_CASE_INSENSITIVE) { | |
| appendOp(URX_BACKREF_I, groupNum); | |
| } else { | |
| appendOp(URX_BACKREF, groupNum); | |
| } | |
| } | |
| break; | |
| case doBeginNamedBackRef: | |
| U_ASSERT(fCaptureName == NULL); | |
| fCaptureName = new UnicodeString; | |
| if (fCaptureName == NULL) { | |
| error(U_MEMORY_ALLOCATION_ERROR); | |
| } | |
| break; | |
| case doContinueNamedBackRef: | |
| fCaptureName->append(fC.fChar); | |
| break; | |
| case doCompleteNamedBackRef: | |
| { | |
| int32_t groupNumber = uhash_geti(fRXPat->fNamedCaptureMap, fCaptureName); | |
| if (groupNumber == 0) { | |
| // Group name has not been defined. | |
| // Could be a forward reference. If we choose to support them at some | |
| // future time, extra mechanism will be required at this point. | |
| error(U_REGEX_INVALID_CAPTURE_GROUP_NAME); | |
| } else { | |
| // Given the number, handle identically to a \n numbered back reference. | |
| // See comments above, under doBackRef | |
| fixLiterals(FALSE); | |
| if (fModeFlags & UREGEX_CASE_INSENSITIVE) { | |
| appendOp(URX_BACKREF_I, groupNumber); | |
| } else { | |
| appendOp(URX_BACKREF, groupNumber); | |
| } | |
| } | |
| delete fCaptureName; | |
| fCaptureName = NULL; | |
| break; | |
| } | |
| case doPossessivePlus: | |
| // Possessive ++ quantifier. | |
| // Compiles to | |
| // 1. STO_SP | |
| // 2. body of stuff being iterated over | |
| // 3. STATE_SAVE 5 | |
| // 4. JMP 2 | |
| // 5. LD_SP | |
| // 6. ... | |
| // | |
| // Note: TODO: This is pretty inefficient. A mass of saved state is built up | |
| // then unconditionally discarded. Perhaps introduce a new opcode. Ticket 6056 | |
| // | |
| { | |
| // Emit the STO_SP | |
| int32_t topLoc = blockTopLoc(TRUE); | |
| int32_t stoLoc = allocateData(1); // Reserve the data location for storing save stack ptr. | |
| int32_t op = buildOp(URX_STO_SP, stoLoc); | |
| fRXPat->fCompiledPat->setElementAt(op, topLoc); | |
| // Emit the STATE_SAVE | |
| appendOp(URX_STATE_SAVE, fRXPat->fCompiledPat->size()+2); | |
| // Emit the JMP | |
| appendOp(URX_JMP, topLoc+1); | |
| // Emit the LD_SP | |
| appendOp(URX_LD_SP, stoLoc); | |
| } | |
| break; | |
| case doPossessiveStar: | |
| // Possessive *+ quantifier. | |
| // Compiles to | |
| // 1. STO_SP loc | |
| // 2. STATE_SAVE 5 | |
| // 3. body of stuff being iterated over | |
| // 4. JMP 2 | |
| // 5. LD_SP loc | |
| // 6 ... | |
| // TODO: do something to cut back the state stack each time through the loop. | |
| { | |
| // Reserve two slots at the top of the block. | |
| int32_t topLoc = blockTopLoc(TRUE); | |
| insertOp(topLoc); | |
| // emit STO_SP loc | |
| int32_t stoLoc = allocateData(1); // Reserve the data location for storing save stack ptr. | |
| int32_t op = buildOp(URX_STO_SP, stoLoc); | |
| fRXPat->fCompiledPat->setElementAt(op, topLoc); | |
| // Emit the SAVE_STATE 5 | |
| int32_t L7 = fRXPat->fCompiledPat->size()+1; | |
| op = buildOp(URX_STATE_SAVE, L7); | |
| fRXPat->fCompiledPat->setElementAt(op, topLoc+1); | |
| // Append the JMP operation. | |
| appendOp(URX_JMP, topLoc+1); | |
| // Emit the LD_SP loc | |
| appendOp(URX_LD_SP, stoLoc); | |
| } | |
| break; | |
| case doPossessiveOpt: | |
| // Possessive ?+ quantifier. | |
| // Compiles to | |
| // 1. STO_SP loc | |
| // 2. SAVE_STATE 5 | |
| // 3. body of optional block | |
| // 4. LD_SP loc | |
| // 5. ... | |
| // | |
| { | |
| // Reserve two slots at the top of the block. | |
| int32_t topLoc = blockTopLoc(TRUE); | |
| insertOp(topLoc); | |
| // Emit the STO_SP | |
| int32_t stoLoc = allocateData(1); // Reserve the data location for storing save stack ptr. | |
| int32_t op = buildOp(URX_STO_SP, stoLoc); | |
| fRXPat->fCompiledPat->setElementAt(op, topLoc); | |
| // Emit the SAVE_STATE | |
| int32_t continueLoc = fRXPat->fCompiledPat->size()+1; | |
| op = buildOp(URX_STATE_SAVE, continueLoc); | |
| fRXPat->fCompiledPat->setElementAt(op, topLoc+1); | |
| // Emit the LD_SP | |
| appendOp(URX_LD_SP, stoLoc); | |
| } | |
| break; | |
| case doBeginMatchMode: | |
| fNewModeFlags = fModeFlags; | |
| fSetModeFlag = TRUE; | |
| break; | |
| case doMatchMode: // (?i) and similar | |
| { | |
| int32_t bit = 0; | |
| switch (fC.fChar) { | |
| case 0x69: /* 'i' */ bit = UREGEX_CASE_INSENSITIVE; break; | |
| case 0x64: /* 'd' */ bit = UREGEX_UNIX_LINES; break; | |
| case 0x6d: /* 'm' */ bit = UREGEX_MULTILINE; break; | |
| case 0x73: /* 's' */ bit = UREGEX_DOTALL; break; | |
| case 0x75: /* 'u' */ bit = 0; /* Unicode casing */ break; | |
| case 0x77: /* 'w' */ bit = UREGEX_UWORD; break; | |
| case 0x78: /* 'x' */ bit = UREGEX_COMMENTS; break; | |
| case 0x2d: /* '-' */ fSetModeFlag = FALSE; break; | |
| default: | |
| U_ASSERT(FALSE); // Should never happen. Other chars are filtered out | |
| // by the scanner. | |
| } | |
| if (fSetModeFlag) { | |
| fNewModeFlags |= bit; | |
| } else { | |
| fNewModeFlags &= ~bit; | |
| } | |
| } | |
| break; | |
| case doSetMatchMode: | |
| // Emit code to match any pending literals, using the not-yet changed match mode. | |
| fixLiterals(); | |
| // We've got a (?i) or similar. The match mode is being changed, but | |
| // the change is not scoped to a parenthesized block. | |
| U_ASSERT(fNewModeFlags < 0); | |
| fModeFlags = fNewModeFlags; | |
| break; | |
| case doMatchModeParen: | |
| // We've got a (?i: or similar. Begin a parenthesized block, save old | |
| // mode flags so they can be restored at the close of the block. | |
| // | |
| // Compile to a | |
| // - NOP, which later may be replaced by a save-state if the | |
| // parenthesized group gets a * quantifier, followed by | |
| // - NOP, which may later be replaced by a save-state if there | |
| // is an '|' alternation within the parens. | |
| { | |
| fixLiterals(FALSE); | |
| appendOp(URX_NOP, 0); | |
| appendOp(URX_NOP, 0); | |
| // On the Parentheses stack, start a new frame and add the postions | |
| // of the two NOPs (a normal non-capturing () frame, except for the | |
| // saving of the orignal mode flags.) | |
| fParenStack.push(fModeFlags, *fStatus); | |
| fParenStack.push(flags, *fStatus); // Frame Marker | |
| fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus); // The first NOP | |
| fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); // The second NOP | |
| // Set the current mode flags to the new values. | |
| U_ASSERT(fNewModeFlags < 0); | |
| fModeFlags = fNewModeFlags; | |
| } | |
| break; | |
| case doBadModeFlag: | |
| error(U_REGEX_INVALID_FLAG); | |
| break; | |
| case doSuppressComments: | |
| // We have just scanned a '(?'. We now need to prevent the character scanner from | |
| // treating a '#' as a to-the-end-of-line comment. | |
| // (This Perl compatibility just gets uglier and uglier to do...) | |
| fEOLComments = FALSE; | |
| break; | |
| case doSetAddAmp: | |
| { | |
| UnicodeSet *set = (UnicodeSet *)fSetStack.peek(); | |
| set->add(chAmp); | |
| } | |
| break; | |
| case doSetAddDash: | |
| { | |
| UnicodeSet *set = (UnicodeSet *)fSetStack.peek(); | |
| set->add(chDash); | |
| } | |
| break; | |
| case doSetBackslash_s: | |
| { | |
| UnicodeSet *set = (UnicodeSet *)fSetStack.peek(); | |
| set->addAll(*RegexStaticSets::gStaticSets->fPropSets[URX_ISSPACE_SET]); | |
| break; | |
| } | |
| case doSetBackslash_S: | |
| { | |
| UnicodeSet *set = (UnicodeSet *)fSetStack.peek(); | |
| UnicodeSet SSet(*RegexStaticSets::gStaticSets->fPropSets[URX_ISSPACE_SET]); | |
| SSet.complement(); | |
| set->addAll(SSet); | |
| break; | |
| } | |
| case doSetBackslash_d: | |
| { | |
| UnicodeSet *set = (UnicodeSet *)fSetStack.peek(); | |
| // TODO - make a static set, ticket 6058. | |
| addCategory(set, U_GC_ND_MASK, *fStatus); | |
| break; | |
| } | |
| case doSetBackslash_D: | |
| { | |
| UnicodeSet *set = (UnicodeSet *)fSetStack.peek(); | |
| UnicodeSet digits; | |
| // TODO - make a static set, ticket 6058. | |
| digits.applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, U_GC_ND_MASK, *fStatus); | |
| digits.complement(); | |
| set->addAll(digits); | |
| break; | |
| } | |
| case doSetBackslash_h: | |
| { | |
| UnicodeSet *set = (UnicodeSet *)fSetStack.peek(); | |
| UnicodeSet h; | |
| h.applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, U_GC_ZS_MASK, *fStatus); | |
| h.add((UChar32)9); // Tab | |
| set->addAll(h); | |
| break; | |
| } | |
| case doSetBackslash_H: | |
| { | |
| UnicodeSet *set = (UnicodeSet *)fSetStack.peek(); | |
| UnicodeSet h; | |
| h.applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, U_GC_ZS_MASK, *fStatus); | |
| h.add((UChar32)9); // Tab | |
| h.complement(); | |
| set->addAll(h); | |
| break; | |
| } | |
| case doSetBackslash_v: | |
| { | |
| UnicodeSet *set = (UnicodeSet *)fSetStack.peek(); | |
| set->add((UChar32)0x0a, (UChar32)0x0d); // add range | |
| set->add((UChar32)0x85); | |
| set->add((UChar32)0x2028, (UChar32)0x2029); | |
| break; | |
| } | |
| case doSetBackslash_V: | |
| { | |
| UnicodeSet *set = (UnicodeSet *)fSetStack.peek(); | |
| UnicodeSet v; | |
| v.add((UChar32)0x0a, (UChar32)0x0d); // add range | |
| v.add((UChar32)0x85); | |
| v.add((UChar32)0x2028, (UChar32)0x2029); | |
| v.complement(); | |
| set->addAll(v); | |
| break; | |
| } | |
| case doSetBackslash_w: | |
| { | |
| UnicodeSet *set = (UnicodeSet *)fSetStack.peek(); | |
| set->addAll(*RegexStaticSets::gStaticSets->fPropSets[URX_ISWORD_SET]); | |
| break; | |
| } | |
| case doSetBackslash_W: | |
| { | |
| UnicodeSet *set = (UnicodeSet *)fSetStack.peek(); | |
| UnicodeSet SSet(*RegexStaticSets::gStaticSets->fPropSets[URX_ISWORD_SET]); | |
| SSet.complement(); | |
| set->addAll(SSet); | |
| break; | |
| } | |
| case doSetBegin: | |
| fixLiterals(FALSE); | |
| fSetStack.push(new UnicodeSet(), *fStatus); | |
| fSetOpStack.push(setStart, *fStatus); | |
| if ((fModeFlags & UREGEX_CASE_INSENSITIVE) != 0) { | |
| fSetOpStack.push(setCaseClose, *fStatus); | |
| } | |
| break; | |
| case doSetBeginDifference1: | |
| // We have scanned something like [[abc]-[ | |
| // Set up a new UnicodeSet for the set beginning with the just-scanned '[' | |
| // Push a Difference operator, which will cause the new set to be subtracted from what | |
| // went before once it is created. | |
| setPushOp(setDifference1); | |
| fSetOpStack.push(setStart, *fStatus); | |
| if ((fModeFlags & UREGEX_CASE_INSENSITIVE) != 0) { | |
| fSetOpStack.push(setCaseClose, *fStatus); | |
| } | |
| break; | |
| case doSetBeginIntersection1: | |
| // We have scanned something like [[abc]&[ | |
| // Need both the '&' operator and the open '[' operator. | |
| setPushOp(setIntersection1); | |
| fSetOpStack.push(setStart, *fStatus); | |
| if ((fModeFlags & UREGEX_CASE_INSENSITIVE) != 0) { | |
| fSetOpStack.push(setCaseClose, *fStatus); | |
| } | |
| break; | |
| case doSetBeginUnion: | |
| // We have scanned something like [[abc][ | |
| // Need to handle the union operation explicitly [[abc] | [ | |
| setPushOp(setUnion); | |
| fSetOpStack.push(setStart, *fStatus); | |
| if ((fModeFlags & UREGEX_CASE_INSENSITIVE) != 0) { | |
| fSetOpStack.push(setCaseClose, *fStatus); | |
| } | |
| break; | |
| case doSetDifference2: | |
| // We have scanned something like [abc-- | |
| // Consider this to unambiguously be a set difference operator. | |
| setPushOp(setDifference2); | |
| break; | |
| case doSetEnd: | |
| // Have encountered the ']' that closes a set. | |
| // Force the evaluation of any pending operations within this set, | |
| // leave the completed set on the top of the set stack. | |
| setEval(setEnd); | |
| U_ASSERT(fSetOpStack.peeki()==setStart); | |
| fSetOpStack.popi(); | |
| break; | |
| case doSetFinish: | |
| { | |
| // Finished a complete set expression, including all nested sets. | |
| // The close bracket has already triggered clearing out pending set operators, | |
| // the operator stack should be empty and the operand stack should have just | |
| // one entry, the result set. | |
| U_ASSERT(fSetOpStack.empty()); | |
| UnicodeSet *theSet = (UnicodeSet *)fSetStack.pop(); | |
| U_ASSERT(fSetStack.empty()); | |
| compileSet(theSet); | |
| break; | |
| } | |
| case doSetIntersection2: | |
| // Have scanned something like [abc&& | |
| setPushOp(setIntersection2); | |
| break; | |
| case doSetLiteral: | |
| // Union the just-scanned literal character into the set being built. | |
| // This operation is the highest precedence set operation, so we can always do | |
| // it immediately, without waiting to see what follows. It is necessary to perform | |
| // any pending '-' or '&' operation first, because these have the same precedence | |
| // as union-ing in a literal' | |
| { | |
| setEval(setUnion); | |
| UnicodeSet *s = (UnicodeSet *)fSetStack.peek(); | |
| s->add(fC.fChar); | |
| fLastSetLiteral = fC.fChar; | |
| break; | |
| } | |
| case doSetLiteralEscaped: | |
| // A back-slash escaped literal character was encountered. | |
| // Processing is the same as with setLiteral, above, with the addition of | |
| // the optional check for errors on escaped ASCII letters. | |
| { | |
| if ((fModeFlags & UREGEX_ERROR_ON_UNKNOWN_ESCAPES) != 0 && | |
| ((fC.fChar >= 0x41 && fC.fChar<= 0x5A) || // in [A-Z] | |
| (fC.fChar >= 0x61 && fC.fChar <= 0x7a))) { // in [a-z] | |
| error(U_REGEX_BAD_ESCAPE_SEQUENCE); | |
| } | |
| setEval(setUnion); | |
| UnicodeSet *s = (UnicodeSet *)fSetStack.peek(); | |
| s->add(fC.fChar); | |
| fLastSetLiteral = fC.fChar; | |
| break; | |
| } | |
| case doSetNamedChar: | |
| // Scanning a \N{UNICODE CHARACTER NAME} | |
| // Aside from the source of the character, the processing is identical to doSetLiteral, | |
| // above. | |
| { | |
| UChar32 c = scanNamedChar(); | |
| setEval(setUnion); | |
| UnicodeSet *s = (UnicodeSet *)fSetStack.peek(); | |
| s->add(c); | |
| fLastSetLiteral = c; | |
| break; | |
| } | |
| case doSetNamedRange: | |
| // We have scanned literal-\N{CHAR NAME}. Add the range to the set. | |
| // The left character is already in the set, and is saved in fLastSetLiteral. | |
| // Nonetheless, check if |fLastSetLiteral| is indeed set because it's | |
| // not set in some edge cases. | |
| // The right side needs to be picked up, the scan is at the 'N'. | |
| // Lower Limit > Upper limit being an error matches both Java | |
| // and ICU UnicodeSet behavior. | |
| { | |
| UChar32 c = scanNamedChar(); | |
| if (U_SUCCESS(*fStatus) && (fLastSetLiteral == U_SENTINEL || fLastSetLiteral > c)) { | |
| error(U_REGEX_INVALID_RANGE); | |
| } | |
| UnicodeSet *s = (UnicodeSet *)fSetStack.peek(); | |
| s->add(fLastSetLiteral, c); | |
| fLastSetLiteral = c; | |
| break; | |
| } | |
| case doSetNegate: | |
| // Scanned a '^' at the start of a set. | |
| // Push the negation operator onto the set op stack. | |
| // A twist for case-insensitive matching: | |
| // the case closure operation must happen _before_ negation. | |
| // But the case closure operation will already be on the stack if it's required. | |
| // This requires checking for case closure, and swapping the stack order | |
| // if it is present. | |
| { | |
| int32_t tosOp = fSetOpStack.peeki(); | |
| if (tosOp == setCaseClose) { | |
| fSetOpStack.popi(); | |
| fSetOpStack.push(setNegation, *fStatus); | |
| fSetOpStack.push(setCaseClose, *fStatus); | |
| } else { | |
| fSetOpStack.push(setNegation, *fStatus); | |
| } | |
| } | |
| break; | |
| case doSetNoCloseError: | |
| error(U_REGEX_MISSING_CLOSE_BRACKET); | |
| break; | |
| case doSetOpError: | |
| error(U_REGEX_RULE_SYNTAX); // -- or && at the end of a set. Illegal. | |
| break; | |
| case doSetPosixProp: | |
| { | |
| UnicodeSet *s = scanPosixProp(); | |
| if (s != NULL) { | |
| UnicodeSet *tos = (UnicodeSet *)fSetStack.peek(); | |
| tos->addAll(*s); | |
| delete s; | |
| } // else error. scanProp() reported the error status already. | |
| } | |
| break; | |
| case doSetProp: | |
| // Scanned a \p \P within [brackets]. | |
| { | |
| UnicodeSet *s = scanProp(); | |
| if (s != NULL) { | |
| UnicodeSet *tos = (UnicodeSet *)fSetStack.peek(); | |
| tos->addAll(*s); | |
| delete s; | |
| } // else error. scanProp() reported the error status already. | |
| } | |
| break; | |
| case doSetRange: | |
| // We have scanned literal-literal. Add the range to the set. | |
| // The left character is already in the set, and is saved in fLastSetLiteral. | |
| // Nonetheless, check if |fLastSetLiteral| is indeed set because it's | |
| // not set in some edge cases. | |
| // The right side is the current character. | |
| // Lower Limit > Upper limit being an error matches both Java | |
| // and ICU UnicodeSet behavior. | |
| { | |
| if (fLastSetLiteral == U_SENTINEL || fLastSetLiteral > fC.fChar) { | |
| error(U_REGEX_INVALID_RANGE); | |
| } | |
| UnicodeSet *s = (UnicodeSet *)fSetStack.peek(); | |
| s->add(fLastSetLiteral, fC.fChar); | |
| break; | |
| } | |
| default: | |
| U_ASSERT(FALSE); | |
| error(U_REGEX_INTERNAL_ERROR); | |
| break; | |
| } | |
| if (U_FAILURE(*fStatus)) { | |
| returnVal = FALSE; | |
| } | |
| return returnVal; | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // literalChar We've encountered a literal character from the pattern, | |
| // or an escape sequence that reduces to a character. | |
| // Add it to the string containing all literal chars/strings from | |
| // the pattern. | |
| // | |
| //------------------------------------------------------------------------------ | |
| void RegexCompile::literalChar(UChar32 c) { | |
| fLiteralChars.append(c); | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // fixLiterals When compiling something that can follow a literal | |
| // string in a pattern, emit the code to match the | |
| // accumulated literal string. | |
| // | |
| // Optionally, split the last char of the string off into | |
| // a single "ONE_CHAR" operation, so that quantifiers can | |
| // apply to that char alone. Example: abc* | |
| // The * must apply to the 'c' only. | |
| // | |
| //------------------------------------------------------------------------------ | |
| void RegexCompile::fixLiterals(UBool split) { | |
| // If no literal characters have been scanned but not yet had code generated | |
| // for them, nothing needs to be done. | |
| if (fLiteralChars.length() == 0) { | |
| return; | |
| } | |
| int32_t indexOfLastCodePoint = fLiteralChars.moveIndex32(fLiteralChars.length(), -1); | |
| UChar32 lastCodePoint = fLiteralChars.char32At(indexOfLastCodePoint); | |
| // Split: We need to ensure that the last item in the compiled pattern | |
| // refers only to the last literal scanned in the pattern, so that | |
| // quantifiers (*, +, etc.) affect only it, and not a longer string. | |
| // Split before case folding for case insensitive matches. | |
| if (split) { | |
| fLiteralChars.truncate(indexOfLastCodePoint); | |
| fixLiterals(FALSE); // Recursive call, emit code to match the first part of the string. | |
| // Note that the truncated literal string may be empty, in which case | |
| // nothing will be emitted. | |
| literalChar(lastCodePoint); // Re-add the last code point as if it were a new literal. | |
| fixLiterals(FALSE); // Second recursive call, code for the final code point. | |
| return; | |
| } | |
| // If we are doing case-insensitive matching, case fold the string. This may expand | |
| // the string, e.g. the German sharp-s turns into "ss" | |
| if (fModeFlags & UREGEX_CASE_INSENSITIVE) { | |
| fLiteralChars.foldCase(); | |
| indexOfLastCodePoint = fLiteralChars.moveIndex32(fLiteralChars.length(), -1); | |
| lastCodePoint = fLiteralChars.char32At(indexOfLastCodePoint); | |
| } | |
| if (indexOfLastCodePoint == 0) { | |
| // Single character, emit a URX_ONECHAR op to match it. | |
| if ((fModeFlags & UREGEX_CASE_INSENSITIVE) && | |
| u_hasBinaryProperty(lastCodePoint, UCHAR_CASE_SENSITIVE)) { | |
| appendOp(URX_ONECHAR_I, lastCodePoint); | |
| } else { | |
| appendOp(URX_ONECHAR, lastCodePoint); | |
| } | |
| } else { | |
| // Two or more chars, emit a URX_STRING to match them. | |
| if (fLiteralChars.length() > 0x00ffffff || fRXPat->fLiteralText.length() > 0x00ffffff) { | |
| error(U_REGEX_PATTERN_TOO_BIG); | |
| } | |
| if (fModeFlags & UREGEX_CASE_INSENSITIVE) { | |
| appendOp(URX_STRING_I, fRXPat->fLiteralText.length()); | |
| } else { | |
| // TODO here: add optimization to split case sensitive strings of length two | |
| // into two single char ops, for efficiency. | |
| appendOp(URX_STRING, fRXPat->fLiteralText.length()); | |
| } | |
| appendOp(URX_STRING_LEN, fLiteralChars.length()); | |
| // Add this string into the accumulated strings of the compiled pattern. | |
| fRXPat->fLiteralText.append(fLiteralChars); | |
| } | |
| fLiteralChars.remove(); | |
| } | |
| int32_t RegexCompile::buildOp(int32_t type, int32_t val) { | |
| if (U_FAILURE(*fStatus)) { | |
| return 0; | |
| } | |
| if (type < 0 || type > 255) { | |
| U_ASSERT(FALSE); | |
| error(U_REGEX_INTERNAL_ERROR); | |
| type = URX_RESERVED_OP; | |
| } | |
| if (val > 0x00ffffff) { | |
| U_ASSERT(FALSE); | |
| error(U_REGEX_INTERNAL_ERROR); | |
| val = 0; | |
| } | |
| if (val < 0) { | |
| if (!(type == URX_RESERVED_OP_N || type == URX_RESERVED_OP)) { | |
| U_ASSERT(FALSE); | |
| error(U_REGEX_INTERNAL_ERROR); | |
| return -1; | |
| } | |
| if (URX_TYPE(val) != 0xff) { | |
| U_ASSERT(FALSE); | |
| error(U_REGEX_INTERNAL_ERROR); | |
| return -1; | |
| } | |
| type = URX_RESERVED_OP_N; | |
| } | |
| return (type << 24) | val; | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // appendOp() Append a new instruction onto the compiled pattern | |
| // Includes error checking, limiting the size of the | |
| // pattern to lengths that can be represented in the | |
| // 24 bit operand field of an instruction. | |
| // | |
| //------------------------------------------------------------------------------ | |
| void RegexCompile::appendOp(int32_t op) { | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| fRXPat->fCompiledPat->addElement(op, *fStatus); | |
| if ((fRXPat->fCompiledPat->size() > 0x00fffff0) && U_SUCCESS(*fStatus)) { | |
| error(U_REGEX_PATTERN_TOO_BIG); | |
| } | |
| } | |
| void RegexCompile::appendOp(int32_t type, int32_t val) { | |
| appendOp(buildOp(type, val)); | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // insertOp() Insert a slot for a new opcode into the already | |
| // compiled pattern code. | |
| // | |
| // Fill the slot with a NOP. Our caller will replace it | |
| // with what they really wanted. | |
| // | |
| //------------------------------------------------------------------------------ | |
| void RegexCompile::insertOp(int32_t where) { | |
| UVector64 *code = fRXPat->fCompiledPat; | |
| U_ASSERT(where>0 && where < code->size()); | |
| int32_t nop = buildOp(URX_NOP, 0); | |
| code->insertElementAt(nop, where, *fStatus); | |
| // Walk through the pattern, looking for any ops with targets that | |
| // were moved down by the insert. Fix them. | |
| int32_t loc; | |
| for (loc=0; loc<code->size(); loc++) { | |
| int32_t op = (int32_t)code->elementAti(loc); | |
| int32_t opType = URX_TYPE(op); | |
| int32_t opValue = URX_VAL(op); | |
| if ((opType == URX_JMP || | |
| opType == URX_JMPX || | |
| opType == URX_STATE_SAVE || | |
| opType == URX_CTR_LOOP || | |
| opType == URX_CTR_LOOP_NG || | |
| opType == URX_JMP_SAV || | |
| opType == URX_JMP_SAV_X || | |
| opType == URX_RELOC_OPRND) && opValue > where) { | |
| // Target location for this opcode is after the insertion point and | |
| // needs to be incremented to adjust for the insertion. | |
| opValue++; | |
| op = buildOp(opType, opValue); | |
| code->setElementAt(op, loc); | |
| } | |
| } | |
| // Now fix up the parentheses stack. All positive values in it are locations in | |
| // the compiled pattern. (Negative values are frame boundaries, and don't need fixing.) | |
| for (loc=0; loc<fParenStack.size(); loc++) { | |
| int32_t x = fParenStack.elementAti(loc); | |
| U_ASSERT(x < code->size()); | |
| if (x>where) { | |
| x++; | |
| fParenStack.setElementAt(x, loc); | |
| } | |
| } | |
| if (fMatchCloseParen > where) { | |
| fMatchCloseParen++; | |
| } | |
| if (fMatchOpenParen > where) { | |
| fMatchOpenParen++; | |
| } | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // allocateData() Allocate storage in the matcher's static data area. | |
| // Return the index for the newly allocated data. | |
| // The storage won't actually exist until we are running a match | |
| // operation, but the storage indexes are inserted into various | |
| // opcodes while compiling the pattern. | |
| // | |
| //------------------------------------------------------------------------------ | |
| int32_t RegexCompile::allocateData(int32_t size) { | |
| if (U_FAILURE(*fStatus)) { | |
| return 0; | |
| } | |
| if (size <= 0 || size > 0x100 || fRXPat->fDataSize < 0) { | |
| error(U_REGEX_INTERNAL_ERROR); | |
| return 0; | |
| } | |
| int32_t dataIndex = fRXPat->fDataSize; | |
| fRXPat->fDataSize += size; | |
| if (fRXPat->fDataSize >= 0x00fffff0) { | |
| error(U_REGEX_INTERNAL_ERROR); | |
| } | |
| return dataIndex; | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // allocateStackData() Allocate space in the back-tracking stack frame. | |
| // Return the index for the newly allocated data. | |
| // The frame indexes are inserted into various | |
| // opcodes while compiling the pattern, meaning that frame | |
| // size must be restricted to the size that will fit | |
| // as an operand (24 bits). | |
| // | |
| //------------------------------------------------------------------------------ | |
| int32_t RegexCompile::allocateStackData(int32_t size) { | |
| if (U_FAILURE(*fStatus)) { | |
| return 0; | |
| } | |
| if (size <= 0 || size > 0x100 || fRXPat->fFrameSize < 0) { | |
| error(U_REGEX_INTERNAL_ERROR); | |
| return 0; | |
| } | |
| int32_t dataIndex = fRXPat->fFrameSize; | |
| fRXPat->fFrameSize += size; | |
| if (fRXPat->fFrameSize >= 0x00fffff0) { | |
| error(U_REGEX_PATTERN_TOO_BIG); | |
| } | |
| return dataIndex; | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // blockTopLoc() Find or create a location in the compiled pattern | |
| // at the start of the operation or block that has | |
| // just been compiled. Needed when a quantifier (* or | |
| // whatever) appears, and we need to add an operation | |
| // at the start of the thing being quantified. | |
| // | |
| // (Parenthesized Blocks) have a slot with a NOP that | |
| // is reserved for this purpose. .* or similar don't | |
| // and a slot needs to be added. | |
| // | |
| // parameter reserveLoc : TRUE - ensure that there is space to add an opcode | |
| // at the returned location. | |
| // FALSE - just return the address, | |
| // do not reserve a location there. | |
| // | |
| //------------------------------------------------------------------------------ | |
| int32_t RegexCompile::blockTopLoc(UBool reserveLoc) { | |
| int32_t theLoc; | |
| fixLiterals(TRUE); // Emit code for any pending literals. | |
| // If last item was a string, emit separate op for the its last char. | |
| if (fRXPat->fCompiledPat->size() == fMatchCloseParen) | |
| { | |
| // The item just processed is a parenthesized block. | |
| theLoc = fMatchOpenParen; // A slot is already reserved for us. | |
| U_ASSERT(theLoc > 0); | |
| U_ASSERT(URX_TYPE(((uint32_t)fRXPat->fCompiledPat->elementAti(theLoc))) == URX_NOP); | |
| } | |
| else { | |
| // Item just compiled is a single thing, a ".", or a single char, a string or a set reference. | |
| // No slot for STATE_SAVE was pre-reserved in the compiled code. | |
| // We need to make space now. | |
| theLoc = fRXPat->fCompiledPat->size()-1; | |
| int32_t opAtTheLoc = (int32_t)fRXPat->fCompiledPat->elementAti(theLoc); | |
| if (URX_TYPE(opAtTheLoc) == URX_STRING_LEN) { | |
| // Strings take two opcode, we want the position of the first one. | |
| // We can have a string at this point if a single character case-folded to two. | |
| theLoc--; | |
| } | |
| if (reserveLoc) { | |
| int32_t nop = buildOp(URX_NOP, 0); | |
| fRXPat->fCompiledPat->insertElementAt(nop, theLoc, *fStatus); | |
| } | |
| } | |
| return theLoc; | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // handleCloseParen When compiling a close paren, we need to go back | |
| // and fix up any JMP or SAVE operations within the | |
| // parenthesized block that need to target the end | |
| // of the block. The locations of these are kept on | |
| // the paretheses stack. | |
| // | |
| // This function is called both when encountering a | |
| // real ) and at the end of the pattern. | |
| // | |
| //------------------------------------------------------------------------------ | |
| void RegexCompile::handleCloseParen() { | |
| int32_t patIdx; | |
| int32_t patOp; | |
| if (fParenStack.size() <= 0) { | |
| error(U_REGEX_MISMATCHED_PAREN); | |
| return; | |
| } | |
| // Emit code for any pending literals. | |
| fixLiterals(FALSE); | |
| // Fixup any operations within the just-closed parenthesized group | |
| // that need to reference the end of the (block). | |
| // (The first one popped from the stack is an unused slot for | |
| // alternation (OR) state save, but applying the fixup to it does no harm.) | |
| for (;;) { | |
| patIdx = fParenStack.popi(); | |
| if (patIdx < 0) { | |
| // value < 0 flags the start of the frame on the paren stack. | |
| break; | |
| } | |
| U_ASSERT(patIdx>0 && patIdx <= fRXPat->fCompiledPat->size()); | |
| patOp = (int32_t)fRXPat->fCompiledPat->elementAti(patIdx); | |
| U_ASSERT(URX_VAL(patOp) == 0); // Branch target for JMP should not be set. | |
| patOp |= fRXPat->fCompiledPat->size(); // Set it now. | |
| fRXPat->fCompiledPat->setElementAt(patOp, patIdx); | |
| fMatchOpenParen = patIdx; | |
| } | |
| // At the close of any parenthesized block, restore the match mode flags to | |
| // the value they had at the open paren. Saved value is | |
| // at the top of the paren stack. | |
| fModeFlags = fParenStack.popi(); | |
| U_ASSERT(fModeFlags < 0); | |
| // DO any additional fixups, depending on the specific kind of | |
| // parentesized grouping this is | |
| switch (patIdx) { | |
| case plain: | |
| case flags: | |
| // No additional fixups required. | |
| // (Grouping-only parentheses) | |
| break; | |
| case capturing: | |
| // Capturing Parentheses. | |
| // Insert a End Capture op into the pattern. | |
| // The frame offset of the variables for this cg is obtained from the | |
| // start capture op and put it into the end-capture op. | |
| { | |
| int32_t captureOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen+1); | |
| U_ASSERT(URX_TYPE(captureOp) == URX_START_CAPTURE); | |
| int32_t frameVarLocation = URX_VAL(captureOp); | |
| appendOp(URX_END_CAPTURE, frameVarLocation); | |
| } | |
| break; | |
| case atomic: | |
| // Atomic Parenthesis. | |
| // Insert a LD_SP operation to restore the state stack to the position | |
| // it was when the atomic parens were entered. | |
| { | |
| int32_t stoOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen+1); | |
| U_ASSERT(URX_TYPE(stoOp) == URX_STO_SP); | |
| int32_t stoLoc = URX_VAL(stoOp); | |
| appendOp(URX_LD_SP, stoLoc); | |
| } | |
| break; | |
| case lookAhead: | |
| { | |
| int32_t startOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen-5); | |
| U_ASSERT(URX_TYPE(startOp) == URX_LA_START); | |
| int32_t dataLoc = URX_VAL(startOp); | |
| appendOp(URX_LA_END, dataLoc); | |
| } | |
| break; | |
| case negLookAhead: | |
| { | |
| // See comment at doOpenLookAheadNeg | |
| int32_t startOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen-1); | |
| U_ASSERT(URX_TYPE(startOp) == URX_LA_START); | |
| int32_t dataLoc = URX_VAL(startOp); | |
| appendOp(URX_LA_END, dataLoc); | |
| appendOp(URX_BACKTRACK, 0); | |
| appendOp(URX_LA_END, dataLoc); | |
| // Patch the URX_SAVE near the top of the block. | |
| // The destination of the SAVE is the final LA_END that was just added. | |
| int32_t saveOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen); | |
| U_ASSERT(URX_TYPE(saveOp) == URX_STATE_SAVE); | |
| int32_t dest = fRXPat->fCompiledPat->size()-1; | |
| saveOp = buildOp(URX_STATE_SAVE, dest); | |
| fRXPat->fCompiledPat->setElementAt(saveOp, fMatchOpenParen); | |
| } | |
| break; | |
| case lookBehind: | |
| { | |
| // See comment at doOpenLookBehind. | |
| // Append the URX_LB_END and URX_LA_END to the compiled pattern. | |
| int32_t startOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen-4); | |
| U_ASSERT(URX_TYPE(startOp) == URX_LB_START); | |
| int32_t dataLoc = URX_VAL(startOp); | |
| appendOp(URX_LB_END, dataLoc); | |
| appendOp(URX_LA_END, dataLoc); | |
| // Determine the min and max bounds for the length of the | |
| // string that the pattern can match. | |
| // An unbounded upper limit is an error. | |
| int32_t patEnd = fRXPat->fCompiledPat->size() - 1; | |
| int32_t minML = minMatchLength(fMatchOpenParen, patEnd); | |
| int32_t maxML = maxMatchLength(fMatchOpenParen, patEnd); | |
| if (URX_TYPE(maxML) != 0) { | |
| error(U_REGEX_LOOK_BEHIND_LIMIT); | |
| break; | |
| } | |
| if (maxML == INT32_MAX) { | |
| error(U_REGEX_LOOK_BEHIND_LIMIT); | |
| break; | |
| } | |
| U_ASSERT(minML <= maxML); | |
| // Insert the min and max match len bounds into the URX_LB_CONT op that | |
| // appears at the top of the look-behind block, at location fMatchOpenParen+1 | |
| fRXPat->fCompiledPat->setElementAt(minML, fMatchOpenParen-2); | |
| fRXPat->fCompiledPat->setElementAt(maxML, fMatchOpenParen-1); | |
| } | |
| break; | |
| case lookBehindN: | |
| { | |
| // See comment at doOpenLookBehindNeg. | |
| // Append the URX_LBN_END to the compiled pattern. | |
| int32_t startOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen-5); | |
| U_ASSERT(URX_TYPE(startOp) == URX_LB_START); | |
| int32_t dataLoc = URX_VAL(startOp); | |
| appendOp(URX_LBN_END, dataLoc); | |
| // Determine the min and max bounds for the length of the | |
| // string that the pattern can match. | |
| // An unbounded upper limit is an error. | |
| int32_t patEnd = fRXPat->fCompiledPat->size() - 1; | |
| int32_t minML = minMatchLength(fMatchOpenParen, patEnd); | |
| int32_t maxML = maxMatchLength(fMatchOpenParen, patEnd); | |
| if (URX_TYPE(maxML) != 0) { | |
| error(U_REGEX_LOOK_BEHIND_LIMIT); | |
| break; | |
| } | |
| if (maxML == INT32_MAX) { | |
| error(U_REGEX_LOOK_BEHIND_LIMIT); | |
| break; | |
| } | |
| U_ASSERT(minML <= maxML); | |
| // Insert the min and max match len bounds into the URX_LB_CONT op that | |
| // appears at the top of the look-behind block, at location fMatchOpenParen+1 | |
| fRXPat->fCompiledPat->setElementAt(minML, fMatchOpenParen-3); | |
| fRXPat->fCompiledPat->setElementAt(maxML, fMatchOpenParen-2); | |
| // Insert the pattern location to continue at after a successful match | |
| // as the last operand of the URX_LBN_CONT | |
| int32_t op = buildOp(URX_RELOC_OPRND, fRXPat->fCompiledPat->size()); | |
| fRXPat->fCompiledPat->setElementAt(op, fMatchOpenParen-1); | |
| } | |
| break; | |
| default: | |
| U_ASSERT(FALSE); | |
| } | |
| // remember the next location in the compiled pattern. | |
| // The compilation of Quantifiers will look at this to see whether its looping | |
| // over a parenthesized block or a single item | |
| fMatchCloseParen = fRXPat->fCompiledPat->size(); | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // compileSet Compile the pattern operations for a reference to a | |
| // UnicodeSet. | |
| // | |
| //------------------------------------------------------------------------------ | |
| void RegexCompile::compileSet(UnicodeSet *theSet) | |
| { | |
| if (theSet == NULL) { | |
| return; | |
| } | |
| // Remove any strings from the set. | |
| // There shoudn't be any, but just in case. | |
| // (Case Closure can add them; if we had a simple case closure avaialble that | |
| // ignored strings, that would be better.) | |
| theSet->removeAllStrings(); | |
| int32_t setSize = theSet->size(); | |
| switch (setSize) { | |
| case 0: | |
| { | |
| // Set of no elements. Always fails to match. | |
| appendOp(URX_BACKTRACK, 0); | |
| delete theSet; | |
| } | |
| break; | |
| case 1: | |
| { | |
| // The set contains only a single code point. Put it into | |
| // the compiled pattern as a single char operation rather | |
| // than a set, and discard the set itself. | |
| literalChar(theSet->charAt(0)); | |
| delete theSet; | |
| } | |
| break; | |
| default: | |
| { | |
| // The set contains two or more chars. (the normal case) | |
| // Put it into the compiled pattern as a set. | |
| int32_t setNumber = fRXPat->fSets->size(); | |
| fRXPat->fSets->addElement(theSet, *fStatus); | |
| appendOp(URX_SETREF, setNumber); | |
| } | |
| } | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // compileInterval Generate the code for a {min, max} style interval quantifier. | |
| // Except for the specific opcodes used, the code is the same | |
| // for all three types (greedy, non-greedy, possessive) of | |
| // intervals. The opcodes are supplied as parameters. | |
| // (There are two sets of opcodes - greedy & possessive use the | |
| // same ones, while non-greedy has it's own.) | |
| // | |
| // The code for interval loops has this form: | |
| // 0 CTR_INIT counter loc (in stack frame) | |
| // 1 5 patt address of CTR_LOOP at bottom of block | |
| // 2 min count | |
| // 3 max count (-1 for unbounded) | |
| // 4 ... block to be iterated over | |
| // 5 CTR_LOOP | |
| // | |
| // In | |
| //------------------------------------------------------------------------------ | |
| void RegexCompile::compileInterval(int32_t InitOp, int32_t LoopOp) | |
| { | |
| // The CTR_INIT op at the top of the block with the {n,m} quantifier takes | |
| // four slots in the compiled code. Reserve them. | |
| int32_t topOfBlock = blockTopLoc(TRUE); | |
| insertOp(topOfBlock); | |
| insertOp(topOfBlock); | |
| insertOp(topOfBlock); | |
| // The operands for the CTR_INIT opcode include the index in the matcher data | |
| // of the counter. Allocate it now. There are two data items | |
| // counterLoc --> Loop counter | |
| // +1 --> Input index (for breaking non-progressing loops) | |
| // (Only present if unbounded upper limit on loop) | |
| int32_t dataSize = fIntervalUpper < 0 ? 2 : 1; | |
| int32_t counterLoc = allocateStackData(dataSize); | |
| int32_t op = buildOp(InitOp, counterLoc); | |
| fRXPat->fCompiledPat->setElementAt(op, topOfBlock); | |
| // The second operand of CTR_INIT is the location following the end of the loop. | |
| // Must put in as a URX_RELOC_OPRND so that the value will be adjusted if the | |
| // compilation of something later on causes the code to grow and the target | |
| // position to move. | |
| int32_t loopEnd = fRXPat->fCompiledPat->size(); | |
| op = buildOp(URX_RELOC_OPRND, loopEnd); | |
| fRXPat->fCompiledPat->setElementAt(op, topOfBlock+1); | |
| // Followed by the min and max counts. | |
| fRXPat->fCompiledPat->setElementAt(fIntervalLow, topOfBlock+2); | |
| fRXPat->fCompiledPat->setElementAt(fIntervalUpper, topOfBlock+3); | |
| // Apend the CTR_LOOP op. The operand is the location of the CTR_INIT op. | |
| // Goes at end of the block being looped over, so just append to the code so far. | |
| appendOp(LoopOp, topOfBlock); | |
| if ((fIntervalLow & 0xff000000) != 0 || | |
| (fIntervalUpper > 0 && (fIntervalUpper & 0xff000000) != 0)) { | |
| error(U_REGEX_NUMBER_TOO_BIG); | |
| } | |
| if (fIntervalLow > fIntervalUpper && fIntervalUpper != -1) { | |
| error(U_REGEX_MAX_LT_MIN); | |
| } | |
| } | |
| UBool RegexCompile::compileInlineInterval() { | |
| if (fIntervalUpper > 10 || fIntervalUpper < fIntervalLow) { | |
| // Too big to inline. Fail, which will cause looping code to be generated. | |
| // (Upper < Lower picks up unbounded upper and errors, both.) | |
| return FALSE; | |
| } | |
| int32_t topOfBlock = blockTopLoc(FALSE); | |
| if (fIntervalUpper == 0) { | |
| // Pathological case. Attempt no matches, as if the block doesn't exist. | |
| // Discard the generated code for the block. | |
| // If the block included parens, discard the info pertaining to them as well. | |
| fRXPat->fCompiledPat->setSize(topOfBlock); | |
| if (fMatchOpenParen >= topOfBlock) { | |
| fMatchOpenParen = -1; | |
| } | |
| if (fMatchCloseParen >= topOfBlock) { | |
| fMatchCloseParen = -1; | |
| } | |
| return TRUE; | |
| } | |
| if (topOfBlock != fRXPat->fCompiledPat->size()-1 && fIntervalUpper != 1) { | |
| // The thing being repeated is not a single op, but some | |
| // more complex block. Do it as a loop, not inlines. | |
| // Note that things "repeated" a max of once are handled as inline, because | |
| // the one copy of the code already generated is just fine. | |
| return FALSE; | |
| } | |
| // Pick up the opcode that is to be repeated | |
| // | |
| int32_t op = (int32_t)fRXPat->fCompiledPat->elementAti(topOfBlock); | |
| // Compute the pattern location where the inline sequence | |
| // will end, and set up the state save op that will be needed. | |
| // | |
| int32_t endOfSequenceLoc = fRXPat->fCompiledPat->size()-1 | |
| + fIntervalUpper + (fIntervalUpper-fIntervalLow); | |
| int32_t saveOp = buildOp(URX_STATE_SAVE, endOfSequenceLoc); | |
| if (fIntervalLow == 0) { | |
| insertOp(topOfBlock); | |
| fRXPat->fCompiledPat->setElementAt(saveOp, topOfBlock); | |
| } | |
| // Loop, emitting the op for the thing being repeated each time. | |
| // Loop starts at 1 because one instance of the op already exists in the pattern, | |
| // it was put there when it was originally encountered. | |
| int32_t i; | |
| for (i=1; i<fIntervalUpper; i++ ) { | |
| if (i >= fIntervalLow) { | |
| appendOp(saveOp); | |
| } | |
| appendOp(op); | |
| } | |
| return TRUE; | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // caseInsensitiveStart given a single code point from a pattern string, determine the | |
| // set of characters that could potentially begin a case-insensitive | |
| // match of a string beginning with that character, using full Unicode | |
| // case insensitive matching. | |
| // | |
| // This is used in optimizing find(). | |
| // | |
| // closeOver(USET_CASE_INSENSITIVE) does most of what is needed, but | |
| // misses cases like this: | |
| // A string from the pattern begins with 'ss' (although all we know | |
| // in this context is that it begins with 's') | |
| // The pattern could match a string beginning with a German sharp-s | |
| // | |
| // To the ordinary case closure for a character c, we add all other | |
| // characters cx where the case closure of cx incudes a string form that begins | |
| // with the original character c. | |
| // | |
| // This function could be made smarter. The full pattern string is available | |
| // and it would be possible to verify that the extra characters being added | |
| // to the starting set fully match, rather than having just a first-char of the | |
| // folded form match. | |
| // | |
| //------------------------------------------------------------------------------ | |
| void RegexCompile::findCaseInsensitiveStarters(UChar32 c, UnicodeSet *starterChars) { | |
| // Machine Generated below. | |
| // It may need updating with new versions of Unicode. | |
| // Intltest test RegexTest::TestCaseInsensitiveStarters will fail if an update is needed. | |
| // The update tool is here: svn+ssh://source.icu-project.org/repos/icu/tools/trunk/unicode/c/genregexcasing | |
| // Machine Generated Data. Do not hand edit. | |
| static const UChar32 RECaseFixCodePoints[] = { | |
| 0x61, 0x66, 0x68, 0x69, 0x6a, 0x73, 0x74, 0x77, 0x79, 0x2bc, | |
| 0x3ac, 0x3ae, 0x3b1, 0x3b7, 0x3b9, 0x3c1, 0x3c5, 0x3c9, 0x3ce, 0x565, | |
| 0x574, 0x57e, 0x1f00, 0x1f01, 0x1f02, 0x1f03, 0x1f04, 0x1f05, 0x1f06, 0x1f07, | |
| 0x1f20, 0x1f21, 0x1f22, 0x1f23, 0x1f24, 0x1f25, 0x1f26, 0x1f27, 0x1f60, 0x1f61, | |
| 0x1f62, 0x1f63, 0x1f64, 0x1f65, 0x1f66, 0x1f67, 0x1f70, 0x1f74, 0x1f7c, 0x110000}; | |
| static const int16_t RECaseFixStringOffsets[] = { | |
| 0x0, 0x1, 0x6, 0x7, 0x8, 0x9, 0xd, 0xe, 0xf, 0x10, | |
| 0x11, 0x12, 0x13, 0x17, 0x1b, 0x20, 0x21, 0x2a, 0x2e, 0x2f, | |
| 0x30, 0x34, 0x35, 0x37, 0x39, 0x3b, 0x3d, 0x3f, 0x41, 0x43, | |
| 0x45, 0x47, 0x49, 0x4b, 0x4d, 0x4f, 0x51, 0x53, 0x55, 0x57, | |
| 0x59, 0x5b, 0x5d, 0x5f, 0x61, 0x63, 0x65, 0x66, 0x67, 0}; | |
| static const int16_t RECaseFixCounts[] = { | |
| 0x1, 0x5, 0x1, 0x1, 0x1, 0x4, 0x1, 0x1, 0x1, 0x1, | |
| 0x1, 0x1, 0x4, 0x4, 0x5, 0x1, 0x9, 0x4, 0x1, 0x1, | |
| 0x4, 0x1, 0x2, 0x2, 0x2, 0x2, 0x2, 0x2, 0x2, 0x2, | |
| 0x2, 0x2, 0x2, 0x2, 0x2, 0x2, 0x2, 0x2, 0x2, 0x2, | |
| 0x2, 0x2, 0x2, 0x2, 0x2, 0x2, 0x1, 0x1, 0x1, 0}; | |
| static const UChar RECaseFixData[] = { | |
| 0x1e9a, 0xfb00, 0xfb01, 0xfb02, 0xfb03, 0xfb04, 0x1e96, 0x130, 0x1f0, 0xdf, | |
| 0x1e9e, 0xfb05, 0xfb06, 0x1e97, 0x1e98, 0x1e99, 0x149, 0x1fb4, 0x1fc4, 0x1fb3, | |
| 0x1fb6, 0x1fb7, 0x1fbc, 0x1fc3, 0x1fc6, 0x1fc7, 0x1fcc, 0x390, 0x1fd2, 0x1fd3, | |
| 0x1fd6, 0x1fd7, 0x1fe4, 0x3b0, 0x1f50, 0x1f52, 0x1f54, 0x1f56, 0x1fe2, 0x1fe3, | |
| 0x1fe6, 0x1fe7, 0x1ff3, 0x1ff6, 0x1ff7, 0x1ffc, 0x1ff4, 0x587, 0xfb13, 0xfb14, | |
| 0xfb15, 0xfb17, 0xfb16, 0x1f80, 0x1f88, 0x1f81, 0x1f89, 0x1f82, 0x1f8a, 0x1f83, | |
| 0x1f8b, 0x1f84, 0x1f8c, 0x1f85, 0x1f8d, 0x1f86, 0x1f8e, 0x1f87, 0x1f8f, 0x1f90, | |
| 0x1f98, 0x1f91, 0x1f99, 0x1f92, 0x1f9a, 0x1f93, 0x1f9b, 0x1f94, 0x1f9c, 0x1f95, | |
| 0x1f9d, 0x1f96, 0x1f9e, 0x1f97, 0x1f9f, 0x1fa0, 0x1fa8, 0x1fa1, 0x1fa9, 0x1fa2, | |
| 0x1faa, 0x1fa3, 0x1fab, 0x1fa4, 0x1fac, 0x1fa5, 0x1fad, 0x1fa6, 0x1fae, 0x1fa7, | |
| 0x1faf, 0x1fb2, 0x1fc2, 0x1ff2, 0}; | |
| // End of machine generated data. | |
| if (u_hasBinaryProperty(c, UCHAR_CASE_SENSITIVE)) { | |
| UChar32 caseFoldedC = u_foldCase(c, U_FOLD_CASE_DEFAULT); | |
| starterChars->set(caseFoldedC, caseFoldedC); | |
| int32_t i; | |
| for (i=0; RECaseFixCodePoints[i]<c ; i++) { | |
| // Simple linear search through the sorted list of interesting code points. | |
| } | |
| if (RECaseFixCodePoints[i] == c) { | |
| int32_t dataIndex = RECaseFixStringOffsets[i]; | |
| int32_t numCharsToAdd = RECaseFixCounts[i]; | |
| UChar32 cpToAdd = 0; | |
| for (int32_t j=0; j<numCharsToAdd; j++) { | |
| U16_NEXT_UNSAFE(RECaseFixData, dataIndex, cpToAdd); | |
| starterChars->add(cpToAdd); | |
| } | |
| } | |
| starterChars->closeOver(USET_CASE_INSENSITIVE); | |
| starterChars->removeAllStrings(); | |
| } else { | |
| // Not a cased character. Just return it alone. | |
| starterChars->set(c, c); | |
| } | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // matchStartType Determine how a match can start. | |
| // Used to optimize find() operations. | |
| // | |
| // Operation is very similar to minMatchLength(). Walk the compiled | |
| // pattern, keeping an on-going minimum-match-length. For any | |
| // op where the min match coming in is zero, add that ops possible | |
| // starting matches to the possible starts for the overall pattern. | |
| // | |
| //------------------------------------------------------------------------------ | |
| void RegexCompile::matchStartType() { | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| int32_t loc; // Location in the pattern of the current op being processed. | |
| int32_t op; // The op being processed | |
| int32_t opType; // The opcode type of the op | |
| int32_t currentLen = 0; // Minimum length of a match to this point (loc) in the pattern | |
| int32_t numInitialStrings = 0; // Number of strings encountered that could match at start. | |
| UBool atStart = TRUE; // True if no part of the pattern yet encountered | |
| // could have advanced the position in a match. | |
| // (Maximum match length so far == 0) | |
| // forwardedLength is a vector holding minimum-match-length values that | |
| // are propagated forward in the pattern by JMP or STATE_SAVE operations. | |
| // It must be one longer than the pattern being checked because some ops | |
| // will jmp to a end-of-block+1 location from within a block, and we must | |
| // count those when checking the block. | |
| int32_t end = fRXPat->fCompiledPat->size(); | |
| UVector32 forwardedLength(end+1, *fStatus); | |
| forwardedLength.setSize(end+1); | |
| for (loc=3; loc<end; loc++) { | |
| forwardedLength.setElementAt(INT32_MAX, loc); | |
| } | |
| for (loc = 3; loc<end; loc++) { | |
| op = (int32_t)fRXPat->fCompiledPat->elementAti(loc); | |
| opType = URX_TYPE(op); | |
| // The loop is advancing linearly through the pattern. | |
| // If the op we are now at was the destination of a branch in the pattern, | |
| // and that path has a shorter minimum length than the current accumulated value, | |
| // replace the current accumulated value. | |
| if (forwardedLength.elementAti(loc) < currentLen) { | |
| currentLen = forwardedLength.elementAti(loc); | |
| U_ASSERT(currentLen>=0 && currentLen < INT32_MAX); | |
| } | |
| switch (opType) { | |
| // Ops that don't change the total length matched | |
| case URX_RESERVED_OP: | |
| case URX_END: | |
| case URX_FAIL: | |
| case URX_STRING_LEN: | |
| case URX_NOP: | |
| case URX_START_CAPTURE: | |
| case URX_END_CAPTURE: | |
| case URX_BACKSLASH_B: | |
| case URX_BACKSLASH_BU: | |
| case URX_BACKSLASH_G: | |
| case URX_BACKSLASH_Z: | |
| case URX_DOLLAR: | |
| case URX_DOLLAR_M: | |
| case URX_DOLLAR_D: | |
| case URX_DOLLAR_MD: | |
| case URX_RELOC_OPRND: | |
| case URX_STO_INP_LOC: | |
| case URX_BACKREF: // BackRef. Must assume that it might be a zero length match | |
| case URX_BACKREF_I: | |
| case URX_STO_SP: // Setup for atomic or possessive blocks. Doesn't change what can match. | |
| case URX_LD_SP: | |
| break; | |
| case URX_CARET: | |
| if (atStart) { | |
| fRXPat->fStartType = START_START; | |
| } | |
| break; | |
| case URX_CARET_M: | |
| case URX_CARET_M_UNIX: | |
| if (atStart) { | |
| fRXPat->fStartType = START_LINE; | |
| } | |
| break; | |
| case URX_ONECHAR: | |
| if (currentLen == 0) { | |
| // This character could appear at the start of a match. | |
| // Add it to the set of possible starting characters. | |
| fRXPat->fInitialChars->add(URX_VAL(op)); | |
| numInitialStrings += 2; | |
| } | |
| currentLen++; | |
| atStart = FALSE; | |
| break; | |
| case URX_SETREF: | |
| if (currentLen == 0) { | |
| int32_t sn = URX_VAL(op); | |
| U_ASSERT(sn > 0 && sn < fRXPat->fSets->size()); | |
| const UnicodeSet *s = (UnicodeSet *)fRXPat->fSets->elementAt(sn); | |
| fRXPat->fInitialChars->addAll(*s); | |
| numInitialStrings += 2; | |
| } | |
| currentLen++; | |
| atStart = FALSE; | |
| break; | |
| case URX_LOOP_SR_I: | |
| // [Set]*, like a SETREF, above, in what it can match, | |
| // but may not match at all, so currentLen is not incremented. | |
| if (currentLen == 0) { | |
| int32_t sn = URX_VAL(op); | |
| U_ASSERT(sn > 0 && sn < fRXPat->fSets->size()); | |
| const UnicodeSet *s = (UnicodeSet *)fRXPat->fSets->elementAt(sn); | |
| fRXPat->fInitialChars->addAll(*s); | |
| numInitialStrings += 2; | |
| } | |
| atStart = FALSE; | |
| break; | |
| case URX_LOOP_DOT_I: | |
| if (currentLen == 0) { | |
| // .* at the start of a pattern. | |
| // Any character can begin the match. | |
| fRXPat->fInitialChars->clear(); | |
| fRXPat->fInitialChars->complement(); | |
| numInitialStrings += 2; | |
| } | |
| atStart = FALSE; | |
| break; | |
| case URX_STATIC_SETREF: | |
| if (currentLen == 0) { | |
| int32_t sn = URX_VAL(op); | |
| U_ASSERT(sn>0 && sn<URX_LAST_SET); | |
| const UnicodeSet *s = fRXPat->fStaticSets[sn]; | |
| fRXPat->fInitialChars->addAll(*s); | |
| numInitialStrings += 2; | |
| } | |
| currentLen++; | |
| atStart = FALSE; | |
| break; | |
| case URX_STAT_SETREF_N: | |
| if (currentLen == 0) { | |
| int32_t sn = URX_VAL(op); | |
| const UnicodeSet *s = fRXPat->fStaticSets[sn]; | |
| UnicodeSet sc(*s); | |
| sc.complement(); | |
| fRXPat->fInitialChars->addAll(sc); | |
| numInitialStrings += 2; | |
| } | |
| currentLen++; | |
| atStart = FALSE; | |
| break; | |
| case URX_BACKSLASH_D: | |
| // Digit Char | |
| if (currentLen == 0) { | |
| UnicodeSet s; | |
| s.applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, U_GC_ND_MASK, *fStatus); | |
| if (URX_VAL(op) != 0) { | |
| s.complement(); | |
| } | |
| fRXPat->fInitialChars->addAll(s); | |
| numInitialStrings += 2; | |
| } | |
| currentLen++; | |
| atStart = FALSE; | |
| break; | |
| case URX_BACKSLASH_H: | |
| // Horiz white space | |
| if (currentLen == 0) { | |
| UnicodeSet s; | |
| s.applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, U_GC_ZS_MASK, *fStatus); | |
| s.add((UChar32)9); // Tab | |
| if (URX_VAL(op) != 0) { | |
| s.complement(); | |
| } | |
| fRXPat->fInitialChars->addAll(s); | |
| numInitialStrings += 2; | |
| } | |
| currentLen++; | |
| atStart = FALSE; | |
| break; | |
| case URX_BACKSLASH_R: // Any line ending sequence | |
| case URX_BACKSLASH_V: // Any line ending code point, with optional negation | |
| if (currentLen == 0) { | |
| UnicodeSet s; | |
| s.add((UChar32)0x0a, (UChar32)0x0d); // add range | |
| s.add((UChar32)0x85); | |
| s.add((UChar32)0x2028, (UChar32)0x2029); | |
| if (URX_VAL(op) != 0) { | |
| // Complement option applies to URX_BACKSLASH_V only. | |
| s.complement(); | |
| } | |
| fRXPat->fInitialChars->addAll(s); | |
| numInitialStrings += 2; | |
| } | |
| currentLen++; | |
| atStart = FALSE; | |
| break; | |
| case URX_ONECHAR_I: | |
| // Case Insensitive Single Character. | |
| if (currentLen == 0) { | |
| UChar32 c = URX_VAL(op); | |
| if (u_hasBinaryProperty(c, UCHAR_CASE_SENSITIVE)) { | |
| UnicodeSet starters(c, c); | |
| starters.closeOver(USET_CASE_INSENSITIVE); | |
| // findCaseInsensitiveStarters(c, &starters); | |
| // For ONECHAR_I, no need to worry about text chars that expand on folding into strings. | |
| // The expanded folding can't match the pattern. | |
| fRXPat->fInitialChars->addAll(starters); | |
| } else { | |
| // Char has no case variants. Just add it as-is to the | |
| // set of possible starting chars. | |
| fRXPat->fInitialChars->add(c); | |
| } | |
| numInitialStrings += 2; | |
| } | |
| currentLen++; | |
| atStart = FALSE; | |
| break; | |
| case URX_BACKSLASH_X: // Grahpeme Cluster. Minimum is 1, max unbounded. | |
| case URX_DOTANY_ALL: // . matches one or two. | |
| case URX_DOTANY: | |
| case URX_DOTANY_UNIX: | |
| if (currentLen == 0) { | |
| // These constructs are all bad news when they appear at the start | |
| // of a match. Any character can begin the match. | |
| fRXPat->fInitialChars->clear(); | |
| fRXPat->fInitialChars->complement(); | |
| numInitialStrings += 2; | |
| } | |
| currentLen++; | |
| atStart = FALSE; | |
| break; | |
| case URX_JMPX: | |
| loc++; // Except for extra operand on URX_JMPX, same as URX_JMP. | |
| case URX_JMP: | |
| { | |
| int32_t jmpDest = URX_VAL(op); | |
| if (jmpDest < loc) { | |
| // Loop of some kind. Can safely ignore, the worst that will happen | |
| // is that we understate the true minimum length | |
| currentLen = forwardedLength.elementAti(loc+1); | |
| } else { | |
| // Forward jump. Propagate the current min length to the target loc of the jump. | |
| U_ASSERT(jmpDest <= end+1); | |
| if (forwardedLength.elementAti(jmpDest) > currentLen) { | |
| forwardedLength.setElementAt(currentLen, jmpDest); | |
| } | |
| } | |
| } | |
| atStart = FALSE; | |
| break; | |
| case URX_JMP_SAV: | |
| case URX_JMP_SAV_X: | |
| // Combo of state save to the next loc, + jmp backwards. | |
| // Net effect on min. length computation is nothing. | |
| atStart = FALSE; | |
| break; | |
| case URX_BACKTRACK: | |
| // Fails are kind of like a branch, except that the min length was | |
| // propagated already, by the state save. | |
| currentLen = forwardedLength.elementAti(loc+1); | |
| atStart = FALSE; | |
| break; | |
| case URX_STATE_SAVE: | |
| { | |
| // State Save, for forward jumps, propagate the current minimum. | |
| // of the state save. | |
| int32_t jmpDest = URX_VAL(op); | |
| if (jmpDest > loc) { | |
| if (currentLen < forwardedLength.elementAti(jmpDest)) { | |
| forwardedLength.setElementAt(currentLen, jmpDest); | |
| } | |
| } | |
| } | |
| atStart = FALSE; | |
| break; | |
| case URX_STRING: | |
| { | |
| loc++; | |
| int32_t stringLenOp = (int32_t)fRXPat->fCompiledPat->elementAti(loc); | |
| int32_t stringLen = URX_VAL(stringLenOp); | |
| U_ASSERT(URX_TYPE(stringLenOp) == URX_STRING_LEN); | |
| U_ASSERT(stringLenOp >= 2); | |
| if (currentLen == 0) { | |
| // Add the starting character of this string to the set of possible starting | |
| // characters for this pattern. | |
| int32_t stringStartIdx = URX_VAL(op); | |
| UChar32 c = fRXPat->fLiteralText.char32At(stringStartIdx); | |
| fRXPat->fInitialChars->add(c); | |
| // Remember this string. After the entire pattern has been checked, | |
| // if nothing else is identified that can start a match, we'll use it. | |
| numInitialStrings++; | |
| fRXPat->fInitialStringIdx = stringStartIdx; | |
| fRXPat->fInitialStringLen = stringLen; | |
| } | |
| currentLen += stringLen; | |
| atStart = FALSE; | |
| } | |
| break; | |
| case URX_STRING_I: | |
| { | |
| // Case-insensitive string. Unlike exact-match strings, we won't | |
| // attempt a string search for possible match positions. But we | |
| // do update the set of possible starting characters. | |
| loc++; | |
| int32_t stringLenOp = (int32_t)fRXPat->fCompiledPat->elementAti(loc); | |
| int32_t stringLen = URX_VAL(stringLenOp); | |
| U_ASSERT(URX_TYPE(stringLenOp) == URX_STRING_LEN); | |
| U_ASSERT(stringLenOp >= 2); | |
| if (currentLen == 0) { | |
| // Add the starting character of this string to the set of possible starting | |
| // characters for this pattern. | |
| int32_t stringStartIdx = URX_VAL(op); | |
| UChar32 c = fRXPat->fLiteralText.char32At(stringStartIdx); | |
| UnicodeSet s; | |
| findCaseInsensitiveStarters(c, &s); | |
| fRXPat->fInitialChars->addAll(s); | |
| numInitialStrings += 2; // Matching on an initial string not possible. | |
| } | |
| currentLen += stringLen; | |
| atStart = FALSE; | |
| } | |
| break; | |
| case URX_CTR_INIT: | |
| case URX_CTR_INIT_NG: | |
| { | |
| // Loop Init Ops. These don't change the min length, but they are 4 word ops | |
| // so location must be updated accordingly. | |
| // Loop Init Ops. | |
| // If the min loop count == 0 | |
| // move loc forwards to the end of the loop, skipping over the body. | |
| // If the min count is > 0, | |
| // continue normal processing of the body of the loop. | |
| int32_t loopEndLoc = (int32_t)fRXPat->fCompiledPat->elementAti(loc+1); | |
| loopEndLoc = URX_VAL(loopEndLoc); | |
| int32_t minLoopCount = (int32_t)fRXPat->fCompiledPat->elementAti(loc+2); | |
| if (minLoopCount == 0) { | |
| // Min Loop Count of 0, treat like a forward branch and | |
| // move the current minimum length up to the target | |
| // (end of loop) location. | |
| U_ASSERT(loopEndLoc <= end+1); | |
| if (forwardedLength.elementAti(loopEndLoc) > currentLen) { | |
| forwardedLength.setElementAt(currentLen, loopEndLoc); | |
| } | |
| } | |
| loc+=3; // Skips over operands of CTR_INIT | |
| } | |
| atStart = FALSE; | |
| break; | |
| case URX_CTR_LOOP: | |
| case URX_CTR_LOOP_NG: | |
| // Loop ops. | |
| // The jump is conditional, backwards only. | |
| atStart = FALSE; | |
| break; | |
| case URX_LOOP_C: | |
| // More loop ops. These state-save to themselves. | |
| // don't change the minimum match | |
| atStart = FALSE; | |
| break; | |
| case URX_LA_START: | |
| case URX_LB_START: | |
| { | |
| // Look-around. Scan forward until the matching look-ahead end, | |
| // without processing the look-around block. This is overly pessimistic. | |
| // Keep track of the nesting depth of look-around blocks. Boilerplate code for | |
| // lookahead contains two LA_END instructions, so count goes up by two | |
| // for each LA_START. | |
| int32_t depth = (opType == URX_LA_START? 2: 1); | |
| for (;;) { | |
| loc++; | |
| op = (int32_t)fRXPat->fCompiledPat->elementAti(loc); | |
| if (URX_TYPE(op) == URX_LA_START) { | |
| depth+=2; | |
| } | |
| if (URX_TYPE(op) == URX_LB_START) { | |
| depth++; | |
| } | |
| if (URX_TYPE(op) == URX_LA_END || URX_TYPE(op)==URX_LBN_END) { | |
| depth--; | |
| if (depth == 0) { | |
| break; | |
| } | |
| } | |
| if (URX_TYPE(op) == URX_STATE_SAVE) { | |
| // Need this because neg lookahead blocks will FAIL to outside | |
| // of the block. | |
| int32_t jmpDest = URX_VAL(op); | |
| if (jmpDest > loc) { | |
| if (currentLen < forwardedLength.elementAti(jmpDest)) { | |
| forwardedLength.setElementAt(currentLen, jmpDest); | |
| } | |
| } | |
| } | |
| U_ASSERT(loc <= end); | |
| } | |
| } | |
| break; | |
| case URX_LA_END: | |
| case URX_LB_CONT: | |
| case URX_LB_END: | |
| case URX_LBN_CONT: | |
| case URX_LBN_END: | |
| U_ASSERT(FALSE); // Shouldn't get here. These ops should be | |
| // consumed by the scan in URX_LA_START and LB_START | |
| break; | |
| default: | |
| U_ASSERT(FALSE); | |
| } | |
| } | |
| // We have finished walking through the ops. Check whether some forward jump | |
| // propagated a shorter length to location end+1. | |
| if (forwardedLength.elementAti(end+1) < currentLen) { | |
| currentLen = forwardedLength.elementAti(end+1); | |
| } | |
| fRXPat->fInitialChars8->init(fRXPat->fInitialChars); | |
| // Sort out what we should check for when looking for candidate match start positions. | |
| // In order of preference, | |
| // 1. Start of input text buffer. | |
| // 2. A literal string. | |
| // 3. Start of line in multi-line mode. | |
| // 4. A single literal character. | |
| // 5. A character from a set of characters. | |
| // | |
| if (fRXPat->fStartType == START_START) { | |
| // Match only at the start of an input text string. | |
| // start type is already set. We're done. | |
| } else if (numInitialStrings == 1 && fRXPat->fMinMatchLen > 0) { | |
| // Match beginning only with a literal string. | |
| UChar32 c = fRXPat->fLiteralText.char32At(fRXPat->fInitialStringIdx); | |
| U_ASSERT(fRXPat->fInitialChars->contains(c)); | |
| fRXPat->fStartType = START_STRING; | |
| fRXPat->fInitialChar = c; | |
| } else if (fRXPat->fStartType == START_LINE) { | |
| // Match at start of line in Multi-Line mode. | |
| // Nothing to do here; everything is already set. | |
| } else if (fRXPat->fMinMatchLen == 0) { | |
| // Zero length match possible. We could start anywhere. | |
| fRXPat->fStartType = START_NO_INFO; | |
| } else if (fRXPat->fInitialChars->size() == 1) { | |
| // All matches begin with the same char. | |
| fRXPat->fStartType = START_CHAR; | |
| fRXPat->fInitialChar = fRXPat->fInitialChars->charAt(0); | |
| U_ASSERT(fRXPat->fInitialChar != (UChar32)-1); | |
| } else if (fRXPat->fInitialChars->contains((UChar32)0, (UChar32)0x10ffff) == FALSE && | |
| fRXPat->fMinMatchLen > 0) { | |
| // Matches start with a set of character smaller than the set of all chars. | |
| fRXPat->fStartType = START_SET; | |
| } else { | |
| // Matches can start with anything | |
| fRXPat->fStartType = START_NO_INFO; | |
| } | |
| return; | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // minMatchLength Calculate the length of the shortest string that could | |
| // match the specified pattern. | |
| // Length is in 16 bit code units, not code points. | |
| // | |
| // The calculated length may not be exact. The returned | |
| // value may be shorter than the actual minimum; it must | |
| // never be longer. | |
| // | |
| // start and end are the range of p-code operations to be | |
| // examined. The endpoints are included in the range. | |
| // | |
| //------------------------------------------------------------------------------ | |
| int32_t RegexCompile::minMatchLength(int32_t start, int32_t end) { | |
| if (U_FAILURE(*fStatus)) { | |
| return 0; | |
| } | |
| U_ASSERT(start <= end); | |
| U_ASSERT(end < fRXPat->fCompiledPat->size()); | |
| int32_t loc; | |
| int32_t op; | |
| int32_t opType; | |
| int32_t currentLen = 0; | |
| // forwardedLength is a vector holding minimum-match-length values that | |
| // are propagated forward in the pattern by JMP or STATE_SAVE operations. | |
| // It must be one longer than the pattern being checked because some ops | |
| // will jmp to a end-of-block+1 location from within a block, and we must | |
| // count those when checking the block. | |
| UVector32 forwardedLength(end+2, *fStatus); | |
| forwardedLength.setSize(end+2); | |
| for (loc=start; loc<=end+1; loc++) { | |
| forwardedLength.setElementAt(INT32_MAX, loc); | |
| } | |
| for (loc = start; loc<=end; loc++) { | |
| op = (int32_t)fRXPat->fCompiledPat->elementAti(loc); | |
| opType = URX_TYPE(op); | |
| // The loop is advancing linearly through the pattern. | |
| // If the op we are now at was the destination of a branch in the pattern, | |
| // and that path has a shorter minimum length than the current accumulated value, | |
| // replace the current accumulated value. | |
| // U_ASSERT(currentLen>=0 && currentLen < INT32_MAX); // MinLength == INT32_MAX for some | |
| // no-match-possible cases. | |
| if (forwardedLength.elementAti(loc) < currentLen) { | |
| currentLen = forwardedLength.elementAti(loc); | |
| U_ASSERT(currentLen>=0 && currentLen < INT32_MAX); | |
| } | |
| switch (opType) { | |
| // Ops that don't change the total length matched | |
| case URX_RESERVED_OP: | |
| case URX_END: | |
| case URX_STRING_LEN: | |
| case URX_NOP: | |
| case URX_START_CAPTURE: | |
| case URX_END_CAPTURE: | |
| case URX_BACKSLASH_B: | |
| case URX_BACKSLASH_BU: | |
| case URX_BACKSLASH_G: | |
| case URX_BACKSLASH_Z: | |
| case URX_CARET: | |
| case URX_DOLLAR: | |
| case URX_DOLLAR_M: | |
| case URX_DOLLAR_D: | |
| case URX_DOLLAR_MD: | |
| case URX_RELOC_OPRND: | |
| case URX_STO_INP_LOC: | |
| case URX_CARET_M: | |
| case URX_CARET_M_UNIX: | |
| case URX_BACKREF: // BackRef. Must assume that it might be a zero length match | |
| case URX_BACKREF_I: | |
| case URX_STO_SP: // Setup for atomic or possessive blocks. Doesn't change what can match. | |
| case URX_LD_SP: | |
| case URX_JMP_SAV: | |
| case URX_JMP_SAV_X: | |
| break; | |
| // Ops that match a minimum of one character (one or two 16 bit code units.) | |
| // | |
| case URX_ONECHAR: | |
| case URX_STATIC_SETREF: | |
| case URX_STAT_SETREF_N: | |
| case URX_SETREF: | |
| case URX_BACKSLASH_D: | |
| case URX_BACKSLASH_H: | |
| case URX_BACKSLASH_R: | |
| case URX_BACKSLASH_V: | |
| case URX_ONECHAR_I: | |
| case URX_BACKSLASH_X: // Grahpeme Cluster. Minimum is 1, max unbounded. | |
| case URX_DOTANY_ALL: // . matches one or two. | |
| case URX_DOTANY: | |
| case URX_DOTANY_UNIX: | |
| currentLen++; | |
| break; | |
| case URX_JMPX: | |
| loc++; // URX_JMPX has an extra operand, ignored here, | |
| // otherwise processed identically to URX_JMP. | |
| case URX_JMP: | |
| { | |
| int32_t jmpDest = URX_VAL(op); | |
| if (jmpDest < loc) { | |
| // Loop of some kind. Can safely ignore, the worst that will happen | |
| // is that we understate the true minimum length | |
| currentLen = forwardedLength.elementAti(loc+1); | |
| } else { | |
| // Forward jump. Propagate the current min length to the target loc of the jump. | |
| U_ASSERT(jmpDest <= end+1); | |
| if (forwardedLength.elementAti(jmpDest) > currentLen) { | |
| forwardedLength.setElementAt(currentLen, jmpDest); | |
| } | |
| } | |
| } | |
| break; | |
| case URX_BACKTRACK: | |
| { | |
| // Back-tracks are kind of like a branch, except that the min length was | |
| // propagated already, by the state save. | |
| currentLen = forwardedLength.elementAti(loc+1); | |
| } | |
| break; | |
| case URX_STATE_SAVE: | |
| { | |
| // State Save, for forward jumps, propagate the current minimum. | |
| // of the state save. | |
| int32_t jmpDest = URX_VAL(op); | |
| if (jmpDest > loc) { | |
| if (currentLen < forwardedLength.elementAti(jmpDest)) { | |
| forwardedLength.setElementAt(currentLen, jmpDest); | |
| } | |
| } | |
| } | |
| break; | |
| case URX_STRING: | |
| { | |
| loc++; | |
| int32_t stringLenOp = (int32_t)fRXPat->fCompiledPat->elementAti(loc); | |
| currentLen += URX_VAL(stringLenOp); | |
| } | |
| break; | |
| case URX_STRING_I: | |
| { | |
| loc++; | |
| // TODO: with full case folding, matching input text may be shorter than | |
| // the string we have here. More smarts could put some bounds on it. | |
| // Assume a min length of one for now. A min length of zero causes | |
| // optimization failures for a pattern like "string"+ | |
| // currentLen += URX_VAL(stringLenOp); | |
| currentLen += 1; | |
| } | |
| break; | |
| case URX_CTR_INIT: | |
| case URX_CTR_INIT_NG: | |
| { | |
| // Loop Init Ops. | |
| // If the min loop count == 0 | |
| // move loc forwards to the end of the loop, skipping over the body. | |
| // If the min count is > 0, | |
| // continue normal processing of the body of the loop. | |
| int32_t loopEndLoc = (int32_t)fRXPat->fCompiledPat->elementAti(loc+1); | |
| loopEndLoc = URX_VAL(loopEndLoc); | |
| int32_t minLoopCount = (int32_t)fRXPat->fCompiledPat->elementAti(loc+2); | |
| if (minLoopCount == 0) { | |
| loc = loopEndLoc; | |
| } else { | |
| loc+=3; // Skips over operands of CTR_INIT | |
| } | |
| } | |
| break; | |
| case URX_CTR_LOOP: | |
| case URX_CTR_LOOP_NG: | |
| // Loop ops. | |
| // The jump is conditional, backwards only. | |
| break; | |
| case URX_LOOP_SR_I: | |
| case URX_LOOP_DOT_I: | |
| case URX_LOOP_C: | |
| // More loop ops. These state-save to themselves. | |
| // don't change the minimum match - could match nothing at all. | |
| break; | |
| case URX_LA_START: | |
| case URX_LB_START: | |
| { | |
| // Look-around. Scan forward until the matching look-ahead end, | |
| // without processing the look-around block. This is overly pessimistic for look-ahead, | |
| // it assumes that the look-ahead match might be zero-length. | |
| // TODO: Positive lookahead could recursively do the block, then continue | |
| // with the longer of the block or the value coming in. Ticket 6060 | |
| int32_t depth = (opType == URX_LA_START? 2: 1);; | |
| for (;;) { | |
| loc++; | |
| op = (int32_t)fRXPat->fCompiledPat->elementAti(loc); | |
| if (URX_TYPE(op) == URX_LA_START) { | |
| // The boilerplate for look-ahead includes two LA_END insturctions, | |
| // Depth will be decremented by each one when it is seen. | |
| depth += 2; | |
| } | |
| if (URX_TYPE(op) == URX_LB_START) { | |
| depth++; | |
| } | |
| if (URX_TYPE(op) == URX_LA_END) { | |
| depth--; | |
| if (depth == 0) { | |
| break; | |
| } | |
| } | |
| if (URX_TYPE(op)==URX_LBN_END) { | |
| depth--; | |
| if (depth == 0) { | |
| break; | |
| } | |
| } | |
| if (URX_TYPE(op) == URX_STATE_SAVE) { | |
| // Need this because neg lookahead blocks will FAIL to outside | |
| // of the block. | |
| int32_t jmpDest = URX_VAL(op); | |
| if (jmpDest > loc) { | |
| if (currentLen < forwardedLength.elementAti(jmpDest)) { | |
| forwardedLength.setElementAt(currentLen, jmpDest); | |
| } | |
| } | |
| } | |
| U_ASSERT(loc <= end); | |
| } | |
| } | |
| break; | |
| case URX_LA_END: | |
| case URX_LB_CONT: | |
| case URX_LB_END: | |
| case URX_LBN_CONT: | |
| case URX_LBN_END: | |
| // Only come here if the matching URX_LA_START or URX_LB_START was not in the | |
| // range being sized, which happens when measuring size of look-behind blocks. | |
| break; | |
| default: | |
| U_ASSERT(FALSE); | |
| } | |
| } | |
| // We have finished walking through the ops. Check whether some forward jump | |
| // propagated a shorter length to location end+1. | |
| if (forwardedLength.elementAti(end+1) < currentLen) { | |
| currentLen = forwardedLength.elementAti(end+1); | |
| U_ASSERT(currentLen>=0 && currentLen < INT32_MAX); | |
| } | |
| return currentLen; | |
| } | |
| // Increment with overflow check. | |
| // val and delta will both be positive. | |
| static int32_t safeIncrement(int32_t val, int32_t delta) { | |
| if (INT32_MAX - val > delta) { | |
| return val + delta; | |
| } else { | |
| return INT32_MAX; | |
| } | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // maxMatchLength Calculate the length of the longest string that could | |
| // match the specified pattern. | |
| // Length is in 16 bit code units, not code points. | |
| // | |
| // The calculated length may not be exact. The returned | |
| // value may be longer than the actual maximum; it must | |
| // never be shorter. | |
| // | |
| //------------------------------------------------------------------------------ | |
| int32_t RegexCompile::maxMatchLength(int32_t start, int32_t end) { | |
| if (U_FAILURE(*fStatus)) { | |
| return 0; | |
| } | |
| U_ASSERT(start <= end); | |
| U_ASSERT(end < fRXPat->fCompiledPat->size()); | |
| int32_t loc; | |
| int32_t op; | |
| int32_t opType; | |
| int32_t currentLen = 0; | |
| UVector32 forwardedLength(end+1, *fStatus); | |
| forwardedLength.setSize(end+1); | |
| for (loc=start; loc<=end; loc++) { | |
| forwardedLength.setElementAt(0, loc); | |
| } | |
| for (loc = start; loc<=end; loc++) { | |
| op = (int32_t)fRXPat->fCompiledPat->elementAti(loc); | |
| opType = URX_TYPE(op); | |
| // The loop is advancing linearly through the pattern. | |
| // If the op we are now at was the destination of a branch in the pattern, | |
| // and that path has a longer maximum length than the current accumulated value, | |
| // replace the current accumulated value. | |
| if (forwardedLength.elementAti(loc) > currentLen) { | |
| currentLen = forwardedLength.elementAti(loc); | |
| } | |
| switch (opType) { | |
| // Ops that don't change the total length matched | |
| case URX_RESERVED_OP: | |
| case URX_END: | |
| case URX_STRING_LEN: | |
| case URX_NOP: | |
| case URX_START_CAPTURE: | |
| case URX_END_CAPTURE: | |
| case URX_BACKSLASH_B: | |
| case URX_BACKSLASH_BU: | |
| case URX_BACKSLASH_G: | |
| case URX_BACKSLASH_Z: | |
| case URX_CARET: | |
| case URX_DOLLAR: | |
| case URX_DOLLAR_M: | |
| case URX_DOLLAR_D: | |
| case URX_DOLLAR_MD: | |
| case URX_RELOC_OPRND: | |
| case URX_STO_INP_LOC: | |
| case URX_CARET_M: | |
| case URX_CARET_M_UNIX: | |
| case URX_STO_SP: // Setup for atomic or possessive blocks. Doesn't change what can match. | |
| case URX_LD_SP: | |
| case URX_LB_END: | |
| case URX_LB_CONT: | |
| case URX_LBN_CONT: | |
| case URX_LBN_END: | |
| break; | |
| // Ops that increase that cause an unbounded increase in the length | |
| // of a matched string, or that increase it a hard to characterize way. | |
| // Call the max length unbounded, and stop further checking. | |
| case URX_BACKREF: // BackRef. Must assume that it might be a zero length match | |
| case URX_BACKREF_I: | |
| case URX_BACKSLASH_X: // Grahpeme Cluster. Minimum is 1, max unbounded. | |
| currentLen = INT32_MAX; | |
| break; | |
| // Ops that match a max of one character (possibly two 16 bit code units.) | |
| // | |
| case URX_STATIC_SETREF: | |
| case URX_STAT_SETREF_N: | |
| case URX_SETREF: | |
| case URX_BACKSLASH_D: | |
| case URX_BACKSLASH_H: | |
| case URX_BACKSLASH_R: | |
| case URX_BACKSLASH_V: | |
| case URX_ONECHAR_I: | |
| case URX_DOTANY_ALL: | |
| case URX_DOTANY: | |
| case URX_DOTANY_UNIX: | |
| currentLen = safeIncrement(currentLen, 2); | |
| break; | |
| // Single literal character. Increase current max length by one or two, | |
| // depending on whether the char is in the supplementary range. | |
| case URX_ONECHAR: | |
| currentLen = safeIncrement(currentLen, 1); | |
| if (URX_VAL(op) > 0x10000) { | |
| currentLen = safeIncrement(currentLen, 1); | |
| } | |
| break; | |
| // Jumps. | |
| // | |
| case URX_JMP: | |
| case URX_JMPX: | |
| case URX_JMP_SAV: | |
| case URX_JMP_SAV_X: | |
| { | |
| int32_t jmpDest = URX_VAL(op); | |
| if (jmpDest < loc) { | |
| // Loop of some kind. Max match length is unbounded. | |
| currentLen = INT32_MAX; | |
| } else { | |
| // Forward jump. Propagate the current min length to the target loc of the jump. | |
| if (forwardedLength.elementAti(jmpDest) < currentLen) { | |
| forwardedLength.setElementAt(currentLen, jmpDest); | |
| } | |
| currentLen = 0; | |
| } | |
| } | |
| break; | |
| case URX_BACKTRACK: | |
| // back-tracks are kind of like a branch, except that the max length was | |
| // propagated already, by the state save. | |
| currentLen = forwardedLength.elementAti(loc+1); | |
| break; | |
| case URX_STATE_SAVE: | |
| { | |
| // State Save, for forward jumps, propagate the current minimum. | |
| // of the state save. | |
| // For backwards jumps, they create a loop, maximum | |
| // match length is unbounded. | |
| int32_t jmpDest = URX_VAL(op); | |
| if (jmpDest > loc) { | |
| if (currentLen > forwardedLength.elementAti(jmpDest)) { | |
| forwardedLength.setElementAt(currentLen, jmpDest); | |
| } | |
| } else { | |
| currentLen = INT32_MAX; | |
| } | |
| } | |
| break; | |
| case URX_STRING: | |
| { | |
| loc++; | |
| int32_t stringLenOp = (int32_t)fRXPat->fCompiledPat->elementAti(loc); | |
| currentLen = safeIncrement(currentLen, URX_VAL(stringLenOp)); | |
| break; | |
| } | |
| case URX_STRING_I: | |
| // TODO: This code assumes that any user string that matches will be no longer | |
| // than our compiled string, with case insensitive matching. | |
| // Our compiled string has been case-folded already. | |
| // | |
| // Any matching user string will have no more code points than our | |
| // compiled (folded) string. Folding may add code points, but | |
| // not remove them. | |
| // | |
| // There is a potential problem if a supplemental code point | |
| // case-folds to a BMP code point. In this case our compiled string | |
| // could be shorter (in code units) than a matching user string. | |
| // | |
| // At this time (Unicode 6.1) there are no such characters, and this case | |
| // is not being handled. A test, intltest regex/Bug9283, will fail if | |
| // any problematic characters are added to Unicode. | |
| // | |
| // If this happens, we can make a set of the BMP chars that the | |
| // troublesome supplementals fold to, scan our string, and bump the | |
| // currentLen one extra for each that is found. | |
| // | |
| { | |
| loc++; | |
| int32_t stringLenOp = (int32_t)fRXPat->fCompiledPat->elementAti(loc); | |
| currentLen = safeIncrement(currentLen, URX_VAL(stringLenOp)); | |
| } | |
| break; | |
| case URX_CTR_INIT: | |
| case URX_CTR_INIT_NG: | |
| // For Loops, recursively call this function on the pattern for the loop body, | |
| // then multiply the result by the maximum loop count. | |
| { | |
| int32_t loopEndLoc = URX_VAL(fRXPat->fCompiledPat->elementAti(loc+1)); | |
| if (loopEndLoc == loc+4) { | |
| // Loop has an empty body. No affect on max match length. | |
| // Continue processing with code after the loop end. | |
| loc = loopEndLoc; | |
| break; | |
| } | |
| int32_t maxLoopCount = static_cast<int32_t>(fRXPat->fCompiledPat->elementAti(loc+3)); | |
| if (maxLoopCount == -1) { | |
| // Unbounded Loop. No upper bound on match length. | |
| currentLen = INT32_MAX; | |
| break; | |
| } | |
| U_ASSERT(loopEndLoc >= loc+4); | |
| int64_t blockLen = maxMatchLength(loc+4, loopEndLoc-1); // Recursive call. | |
| int64_t updatedLen = (int64_t)currentLen + blockLen * maxLoopCount; | |
| if (updatedLen >= INT32_MAX) { | |
| currentLen = INT32_MAX; | |
| break; | |
| } | |
| currentLen = (int32_t)updatedLen; | |
| loc = loopEndLoc; | |
| break; | |
| } | |
| case URX_CTR_LOOP: | |
| case URX_CTR_LOOP_NG: | |
| // These opcodes will be skipped over by code for URX_CRT_INIT. | |
| // We shouldn't encounter them here. | |
| U_ASSERT(FALSE); | |
| break; | |
| case URX_LOOP_SR_I: | |
| case URX_LOOP_DOT_I: | |
| case URX_LOOP_C: | |
| // For anything to do with loops, make the match length unbounded. | |
| currentLen = INT32_MAX; | |
| break; | |
| case URX_LA_START: | |
| case URX_LA_END: | |
| // Look-ahead. Just ignore, treat the look-ahead block as if | |
| // it were normal pattern. Gives a too-long match length, | |
| // but good enough for now. | |
| break; | |
| // End of look-ahead ops should always be consumed by the processing at | |
| // the URX_LA_START op. | |
| // U_ASSERT(FALSE); | |
| // break; | |
| case URX_LB_START: | |
| { | |
| // Look-behind. Scan forward until the matching look-around end, | |
| // without processing the look-behind block. | |
| int32_t depth = 0; | |
| for (;;) { | |
| loc++; | |
| op = (int32_t)fRXPat->fCompiledPat->elementAti(loc); | |
| if (URX_TYPE(op) == URX_LA_START || URX_TYPE(op) == URX_LB_START) { | |
| depth++; | |
| } | |
| if (URX_TYPE(op) == URX_LA_END || URX_TYPE(op)==URX_LBN_END) { | |
| if (depth == 0) { | |
| break; | |
| } | |
| depth--; | |
| } | |
| U_ASSERT(loc < end); | |
| } | |
| } | |
| break; | |
| default: | |
| U_ASSERT(FALSE); | |
| } | |
| if (currentLen == INT32_MAX) { | |
| // The maximum length is unbounded. | |
| // Stop further processing of the pattern. | |
| break; | |
| } | |
| } | |
| return currentLen; | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // stripNOPs Remove any NOP operations from the compiled pattern code. | |
| // Extra NOPs are inserted for some constructs during the initial | |
| // code generation to provide locations that may be patched later. | |
| // Many end up unneeded, and are removed by this function. | |
| // | |
| // In order to minimize the number of passes through the pattern, | |
| // back-reference fixup is also performed here (adjusting | |
| // back-reference operands to point to the correct frame offsets). | |
| // | |
| //------------------------------------------------------------------------------ | |
| void RegexCompile::stripNOPs() { | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| int32_t end = fRXPat->fCompiledPat->size(); | |
| UVector32 deltas(end, *fStatus); | |
| // Make a first pass over the code, computing the amount that things | |
| // will be offset at each location in the original code. | |
| int32_t loc; | |
| int32_t d = 0; | |
| for (loc=0; loc<end; loc++) { | |
| deltas.addElement(d, *fStatus); | |
| int32_t op = (int32_t)fRXPat->fCompiledPat->elementAti(loc); | |
| if (URX_TYPE(op) == URX_NOP) { | |
| d++; | |
| } | |
| } | |
| UnicodeString caseStringBuffer; | |
| // Make a second pass over the code, removing the NOPs by moving following | |
| // code up, and patching operands that refer to code locations that | |
| // are being moved. The array of offsets from the first step is used | |
| // to compute the new operand values. | |
| int32_t src; | |
| int32_t dst = 0; | |
| for (src=0; src<end; src++) { | |
| int32_t op = (int32_t)fRXPat->fCompiledPat->elementAti(src); | |
| int32_t opType = URX_TYPE(op); | |
| switch (opType) { | |
| case URX_NOP: | |
| break; | |
| case URX_STATE_SAVE: | |
| case URX_JMP: | |
| case URX_CTR_LOOP: | |
| case URX_CTR_LOOP_NG: | |
| case URX_RELOC_OPRND: | |
| case URX_JMPX: | |
| case URX_JMP_SAV: | |
| case URX_JMP_SAV_X: | |
| // These are instructions with operands that refer to code locations. | |
| { | |
| int32_t operandAddress = URX_VAL(op); | |
| U_ASSERT(operandAddress>=0 && operandAddress<deltas.size()); | |
| int32_t fixedOperandAddress = operandAddress - deltas.elementAti(operandAddress); | |
| op = buildOp(opType, fixedOperandAddress); | |
| fRXPat->fCompiledPat->setElementAt(op, dst); | |
| dst++; | |
| break; | |
| } | |
| case URX_BACKREF: | |
| case URX_BACKREF_I: | |
| { | |
| int32_t where = URX_VAL(op); | |
| if (where > fRXPat->fGroupMap->size()) { | |
| error(U_REGEX_INVALID_BACK_REF); | |
| break; | |
| } | |
| where = fRXPat->fGroupMap->elementAti(where-1); | |
| op = buildOp(opType, where); | |
| fRXPat->fCompiledPat->setElementAt(op, dst); | |
| dst++; | |
| fRXPat->fNeedsAltInput = TRUE; | |
| break; | |
| } | |
| case URX_RESERVED_OP: | |
| case URX_RESERVED_OP_N: | |
| case URX_BACKTRACK: | |
| case URX_END: | |
| case URX_ONECHAR: | |
| case URX_STRING: | |
| case URX_STRING_LEN: | |
| case URX_START_CAPTURE: | |
| case URX_END_CAPTURE: | |
| case URX_STATIC_SETREF: | |
| case URX_STAT_SETREF_N: | |
| case URX_SETREF: | |
| case URX_DOTANY: | |
| case URX_FAIL: | |
| case URX_BACKSLASH_B: | |
| case URX_BACKSLASH_BU: | |
| case URX_BACKSLASH_G: | |
| case URX_BACKSLASH_X: | |
| case URX_BACKSLASH_Z: | |
| case URX_DOTANY_ALL: | |
| case URX_BACKSLASH_D: | |
| case URX_CARET: | |
| case URX_DOLLAR: | |
| case URX_CTR_INIT: | |
| case URX_CTR_INIT_NG: | |
| case URX_DOTANY_UNIX: | |
| case URX_STO_SP: | |
| case URX_LD_SP: | |
| case URX_STO_INP_LOC: | |
| case URX_LA_START: | |
| case URX_LA_END: | |
| case URX_ONECHAR_I: | |
| case URX_STRING_I: | |
| case URX_DOLLAR_M: | |
| case URX_CARET_M: | |
| case URX_CARET_M_UNIX: | |
| case URX_LB_START: | |
| case URX_LB_CONT: | |
| case URX_LB_END: | |
| case URX_LBN_CONT: | |
| case URX_LBN_END: | |
| case URX_LOOP_SR_I: | |
| case URX_LOOP_DOT_I: | |
| case URX_LOOP_C: | |
| case URX_DOLLAR_D: | |
| case URX_DOLLAR_MD: | |
| case URX_BACKSLASH_H: | |
| case URX_BACKSLASH_R: | |
| case URX_BACKSLASH_V: | |
| // These instructions are unaltered by the relocation. | |
| fRXPat->fCompiledPat->setElementAt(op, dst); | |
| dst++; | |
| break; | |
| default: | |
| // Some op is unaccounted for. | |
| U_ASSERT(FALSE); | |
| error(U_REGEX_INTERNAL_ERROR); | |
| } | |
| } | |
| fRXPat->fCompiledPat->setSize(dst); | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // Error Report a rule parse error. | |
| // Only report it if no previous error has been recorded. | |
| // | |
| //------------------------------------------------------------------------------ | |
| void RegexCompile::error(UErrorCode e) { | |
| if (U_SUCCESS(*fStatus)) { | |
| *fStatus = e; | |
| // Hmm. fParseErr (UParseError) line & offset fields are int32_t in public | |
| // API (see common/unicode/parseerr.h), while fLineNum and fCharNum are | |
| // int64_t. If the values of the latter are out of range for the former, | |
| // set them to the appropriate "field not supported" values. | |
| if (fLineNum > 0x7FFFFFFF) { | |
| fParseErr->line = 0; | |
| fParseErr->offset = -1; | |
| } else if (fCharNum > 0x7FFFFFFF) { | |
| fParseErr->line = (int32_t)fLineNum; | |
| fParseErr->offset = -1; | |
| } else { | |
| fParseErr->line = (int32_t)fLineNum; | |
| fParseErr->offset = (int32_t)fCharNum; | |
| } | |
| UErrorCode status = U_ZERO_ERROR; // throwaway status for extracting context | |
| // Fill in the context. | |
| // Note: extractBetween() pins supplied indicies to the string bounds. | |
| uprv_memset(fParseErr->preContext, 0, sizeof(fParseErr->preContext)); | |
| uprv_memset(fParseErr->postContext, 0, sizeof(fParseErr->postContext)); | |
| utext_extract(fRXPat->fPattern, fScanIndex-U_PARSE_CONTEXT_LEN+1, fScanIndex, fParseErr->preContext, U_PARSE_CONTEXT_LEN, &status); | |
| utext_extract(fRXPat->fPattern, fScanIndex, fScanIndex+U_PARSE_CONTEXT_LEN-1, fParseErr->postContext, U_PARSE_CONTEXT_LEN, &status); | |
| } | |
| } | |
| // | |
| // Assorted Unicode character constants. | |
| // Numeric because there is no portable way to enter them as literals. | |
| // (Think EBCDIC). | |
| // | |
| static const UChar chCR = 0x0d; // New lines, for terminating comments. | |
| static const UChar chLF = 0x0a; // Line Feed | |
| static const UChar chPound = 0x23; // '#', introduces a comment. | |
| static const UChar chDigit0 = 0x30; // '0' | |
| static const UChar chDigit7 = 0x37; // '9' | |
| static const UChar chColon = 0x3A; // ':' | |
| static const UChar chE = 0x45; // 'E' | |
| static const UChar chQ = 0x51; // 'Q' | |
| //static const UChar chN = 0x4E; // 'N' | |
| static const UChar chP = 0x50; // 'P' | |
| static const UChar chBackSlash = 0x5c; // '\' introduces a char escape | |
| //static const UChar chLBracket = 0x5b; // '[' | |
| static const UChar chRBracket = 0x5d; // ']' | |
| static const UChar chUp = 0x5e; // '^' | |
| static const UChar chLowerP = 0x70; | |
| static const UChar chLBrace = 0x7b; // '{' | |
| static const UChar chRBrace = 0x7d; // '}' | |
| static const UChar chNEL = 0x85; // NEL newline variant | |
| static const UChar chLS = 0x2028; // Unicode Line Separator | |
| //------------------------------------------------------------------------------ | |
| // | |
| // nextCharLL Low Level Next Char from the regex pattern. | |
| // Get a char from the string, keep track of input position | |
| // for error reporting. | |
| // | |
| //------------------------------------------------------------------------------ | |
| UChar32 RegexCompile::nextCharLL() { | |
| UChar32 ch; | |
| if (fPeekChar != -1) { | |
| ch = fPeekChar; | |
| fPeekChar = -1; | |
| return ch; | |
| } | |
| // assume we're already in the right place | |
| ch = UTEXT_NEXT32(fRXPat->fPattern); | |
| if (ch == U_SENTINEL) { | |
| return ch; | |
| } | |
| if (ch == chCR || | |
| ch == chNEL || | |
| ch == chLS || | |
| (ch == chLF && fLastChar != chCR)) { | |
| // Character is starting a new line. Bump up the line number, and | |
| // reset the column to 0. | |
| fLineNum++; | |
| fCharNum=0; | |
| } | |
| else { | |
| // Character is not starting a new line. Except in the case of a | |
| // LF following a CR, increment the column position. | |
| if (ch != chLF) { | |
| fCharNum++; | |
| } | |
| } | |
| fLastChar = ch; | |
| return ch; | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // peekCharLL Low Level Character Scanning, sneak a peek at the next | |
| // character without actually getting it. | |
| // | |
| //------------------------------------------------------------------------------ | |
| UChar32 RegexCompile::peekCharLL() { | |
| if (fPeekChar == -1) { | |
| fPeekChar = nextCharLL(); | |
| } | |
| return fPeekChar; | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // nextChar for pattern scanning. At this level, we handle stripping | |
| // out comments and processing some backslash character escapes. | |
| // The rest of the pattern grammar is handled at the next level up. | |
| // | |
| //------------------------------------------------------------------------------ | |
| void RegexCompile::nextChar(RegexPatternChar &c) { | |
| fScanIndex = UTEXT_GETNATIVEINDEX(fRXPat->fPattern); | |
| c.fChar = nextCharLL(); | |
| c.fQuoted = FALSE; | |
| if (fQuoteMode) { | |
| c.fQuoted = TRUE; | |
| if ((c.fChar==chBackSlash && peekCharLL()==chE && ((fModeFlags & UREGEX_LITERAL) == 0)) || | |
| c.fChar == (UChar32)-1) { | |
| fQuoteMode = FALSE; // Exit quote mode, | |
| nextCharLL(); // discard the E | |
| nextChar(c); // recurse to get the real next char | |
| } | |
| } | |
| else if (fInBackslashQuote) { | |
| // The current character immediately follows a '\' | |
| // Don't check for any further escapes, just return it as-is. | |
| // Don't set c.fQuoted, because that would prevent the state machine from | |
| // dispatching on the character. | |
| fInBackslashQuote = FALSE; | |
| } | |
| else | |
| { | |
| // We are not in a \Q quoted region \E of the source. | |
| // | |
| if (fModeFlags & UREGEX_COMMENTS) { | |
| // | |
| // We are in free-spacing and comments mode. | |
| // Scan through any white space and comments, until we | |
| // reach a significant character or the end of inut. | |
| for (;;) { | |
| if (c.fChar == (UChar32)-1) { | |
| break; // End of Input | |
| } | |
| if (c.fChar == chPound && fEOLComments == TRUE) { | |
| // Start of a comment. Consume the rest of it, until EOF or a new line | |
| for (;;) { | |
| c.fChar = nextCharLL(); | |
| if (c.fChar == (UChar32)-1 || // EOF | |
| c.fChar == chCR || | |
| c.fChar == chLF || | |
| c.fChar == chNEL || | |
| c.fChar == chLS) { | |
| break; | |
| } | |
| } | |
| } | |
| // TODO: check what Java & Perl do with non-ASCII white spaces. Ticket 6061. | |
| if (PatternProps::isWhiteSpace(c.fChar) == FALSE) { | |
| break; | |
| } | |
| c.fChar = nextCharLL(); | |
| } | |
| } | |
| // | |
| // check for backslash escaped characters. | |
| // | |
| if (c.fChar == chBackSlash) { | |
| int64_t pos = UTEXT_GETNATIVEINDEX(fRXPat->fPattern); | |
| if (RegexStaticSets::gStaticSets->fUnescapeCharSet.contains(peekCharLL())) { | |
| // | |
| // A '\' sequence that is handled by ICU's standard unescapeAt function. | |
| // Includes \uxxxx, \n, \r, many others. | |
| // Return the single equivalent character. | |
| // | |
| nextCharLL(); // get & discard the peeked char. | |
| c.fQuoted = TRUE; | |
| if (UTEXT_FULL_TEXT_IN_CHUNK(fRXPat->fPattern, fPatternLength)) { | |
| int32_t endIndex = (int32_t)pos; | |
| c.fChar = u_unescapeAt(uregex_ucstr_unescape_charAt, &endIndex, (int32_t)fPatternLength, (void *)fRXPat->fPattern->chunkContents); | |
| if (endIndex == pos) { | |
| error(U_REGEX_BAD_ESCAPE_SEQUENCE); | |
| } | |
| fCharNum += endIndex - pos; | |
| UTEXT_SETNATIVEINDEX(fRXPat->fPattern, endIndex); | |
| } else { | |
| int32_t offset = 0; | |
| struct URegexUTextUnescapeCharContext context = U_REGEX_UTEXT_UNESCAPE_CONTEXT(fRXPat->fPattern); | |
| UTEXT_SETNATIVEINDEX(fRXPat->fPattern, pos); | |
| c.fChar = u_unescapeAt(uregex_utext_unescape_charAt, &offset, INT32_MAX, &context); | |
| if (offset == 0) { | |
| error(U_REGEX_BAD_ESCAPE_SEQUENCE); | |
| } else if (context.lastOffset == offset) { | |
| UTEXT_PREVIOUS32(fRXPat->fPattern); | |
| } else if (context.lastOffset != offset-1) { | |
| utext_moveIndex32(fRXPat->fPattern, offset - context.lastOffset - 1); | |
| } | |
| fCharNum += offset; | |
| } | |
| } | |
| else if (peekCharLL() == chDigit0) { | |
| // Octal Escape, using Java Regexp Conventions | |
| // which are \0 followed by 1-3 octal digits. | |
| // Different from ICU Unescape handling of Octal, which does not | |
| // require the leading 0. | |
| // Java also has the convention of only consuming 2 octal digits if | |
| // the three digit number would be > 0xff | |
| // | |
| c.fChar = 0; | |
| nextCharLL(); // Consume the initial 0. | |
| int index; | |
| for (index=0; index<3; index++) { | |
| int32_t ch = peekCharLL(); | |
| if (ch<chDigit0 || ch>chDigit7) { | |
| if (index==0) { | |
| // \0 is not followed by any octal digits. | |
| error(U_REGEX_BAD_ESCAPE_SEQUENCE); | |
| } | |
| break; | |
| } | |
| c.fChar <<= 3; | |
| c.fChar += ch&7; | |
| if (c.fChar <= 255) { | |
| nextCharLL(); | |
| } else { | |
| // The last digit made the number too big. Forget we saw it. | |
| c.fChar >>= 3; | |
| } | |
| } | |
| c.fQuoted = TRUE; | |
| } | |
| else if (peekCharLL() == chQ) { | |
| // "\Q" enter quote mode, which will continue until "\E" | |
| fQuoteMode = TRUE; | |
| nextCharLL(); // discard the 'Q'. | |
| nextChar(c); // recurse to get the real next char. | |
| } | |
| else | |
| { | |
| // We are in a '\' escape that will be handled by the state table scanner. | |
| // Just return the backslash, but remember that the following char is to | |
| // be taken literally. | |
| fInBackslashQuote = TRUE; | |
| } | |
| } | |
| } | |
| // re-enable # to end-of-line comments, in case they were disabled. | |
| // They are disabled by the parser upon seeing '(?', but this lasts for | |
| // the fetching of the next character only. | |
| fEOLComments = TRUE; | |
| // putc(c.fChar, stdout); | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // scanNamedChar | |
| // Get a UChar32 from a \N{UNICODE CHARACTER NAME} in the pattern. | |
| // | |
| // The scan position will be at the 'N'. On return | |
| // the scan position should be just after the '}' | |
| // | |
| // Return the UChar32 | |
| // | |
| //------------------------------------------------------------------------------ | |
| UChar32 RegexCompile::scanNamedChar() { | |
| if (U_FAILURE(*fStatus)) { | |
| return 0; | |
| } | |
| nextChar(fC); | |
| if (fC.fChar != chLBrace) { | |
| error(U_REGEX_PROPERTY_SYNTAX); | |
| return 0; | |
| } | |
| UnicodeString charName; | |
| for (;;) { | |
| nextChar(fC); | |
| if (fC.fChar == chRBrace) { | |
| break; | |
| } | |
| if (fC.fChar == -1) { | |
| error(U_REGEX_PROPERTY_SYNTAX); | |
| return 0; | |
| } | |
| charName.append(fC.fChar); | |
| } | |
| char name[100]; | |
| if (!uprv_isInvariantUString(charName.getBuffer(), charName.length()) || | |
| (uint32_t)charName.length()>=sizeof(name)) { | |
| // All Unicode character names have only invariant characters. | |
| // The API to get a character, given a name, accepts only char *, forcing us to convert, | |
| // which requires this error check | |
| error(U_REGEX_PROPERTY_SYNTAX); | |
| return 0; | |
| } | |
| charName.extract(0, charName.length(), name, sizeof(name), US_INV); | |
| UChar32 theChar = u_charFromName(U_UNICODE_CHAR_NAME, name, fStatus); | |
| if (U_FAILURE(*fStatus)) { | |
| error(U_REGEX_PROPERTY_SYNTAX); | |
| } | |
| nextChar(fC); // Continue overall regex pattern processing with char after the '}' | |
| return theChar; | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // scanProp Construct a UnicodeSet from the text at the current scan | |
| // position, which will be of the form \p{whaterver} | |
| // | |
| // The scan position will be at the 'p' or 'P'. On return | |
| // the scan position should be just after the '}' | |
| // | |
| // Return a UnicodeSet, constructed from the \P pattern, | |
| // or NULL if the pattern is invalid. | |
| // | |
| //------------------------------------------------------------------------------ | |
| UnicodeSet *RegexCompile::scanProp() { | |
| UnicodeSet *uset = NULL; | |
| if (U_FAILURE(*fStatus)) { | |
| return NULL; | |
| } | |
| (void)chLowerP; // Suppress compiler unused variable warning. | |
| U_ASSERT(fC.fChar == chLowerP || fC.fChar == chP); | |
| UBool negated = (fC.fChar == chP); | |
| UnicodeString propertyName; | |
| nextChar(fC); | |
| if (fC.fChar != chLBrace) { | |
| error(U_REGEX_PROPERTY_SYNTAX); | |
| return NULL; | |
| } | |
| for (;;) { | |
| nextChar(fC); | |
| if (fC.fChar == chRBrace) { | |
| break; | |
| } | |
| if (fC.fChar == -1) { | |
| // Hit the end of the input string without finding the closing '}' | |
| error(U_REGEX_PROPERTY_SYNTAX); | |
| return NULL; | |
| } | |
| propertyName.append(fC.fChar); | |
| } | |
| uset = createSetForProperty(propertyName, negated); | |
| nextChar(fC); // Move input scan to position following the closing '}' | |
| return uset; | |
| } | |
| //------------------------------------------------------------------------------ | |
| // | |
| // scanPosixProp Construct a UnicodeSet from the text at the current scan | |
| // position, which is expected be of the form [:property expression:] | |
| // | |
| // The scan position will be at the opening ':'. On return | |
| // the scan position must be on the closing ']' | |
| // | |
| // Return a UnicodeSet constructed from the pattern, | |
| // or NULL if this is not a valid POSIX-style set expression. | |
| // If not a property expression, restore the initial scan position | |
| // (to the opening ':') | |
| // | |
| // Note: the opening '[:' is not sufficient to guarantee that | |
| // this is a [:property:] expression. | |
| // [:'+=,] is a perfectly good ordinary set expression that | |
| // happens to include ':' as one of its characters. | |
| // | |
| //------------------------------------------------------------------------------ | |
| UnicodeSet *RegexCompile::scanPosixProp() { | |
| UnicodeSet *uset = NULL; | |
| if (U_FAILURE(*fStatus)) { | |
| return NULL; | |
| } | |
| U_ASSERT(fC.fChar == chColon); | |
| // Save the scanner state. | |
| // TODO: move this into the scanner, with the state encapsulated in some way. Ticket 6062 | |
| int64_t savedScanIndex = fScanIndex; | |
| int64_t savedNextIndex = UTEXT_GETNATIVEINDEX(fRXPat->fPattern); | |
| UBool savedQuoteMode = fQuoteMode; | |
| UBool savedInBackslashQuote = fInBackslashQuote; | |
| UBool savedEOLComments = fEOLComments; | |
| int64_t savedLineNum = fLineNum; | |
| int64_t savedCharNum = fCharNum; | |
| UChar32 savedLastChar = fLastChar; | |
| UChar32 savedPeekChar = fPeekChar; | |
| RegexPatternChar savedfC = fC; | |
| // Scan for a closing ]. A little tricky because there are some perverse | |
| // edge cases possible. "[:abc\Qdef:] \E]" is a valid non-property expression, | |
| // ending on the second closing ]. | |
| UnicodeString propName; | |
| UBool negated = FALSE; | |
| // Check for and consume the '^' in a negated POSIX property, e.g. [:^Letter:] | |
| nextChar(fC); | |
| if (fC.fChar == chUp) { | |
| negated = TRUE; | |
| nextChar(fC); | |
| } | |
| // Scan for the closing ":]", collecting the property name along the way. | |
| UBool sawPropSetTerminator = FALSE; | |
| for (;;) { | |
| propName.append(fC.fChar); | |
| nextChar(fC); | |
| if (fC.fQuoted || fC.fChar == -1) { | |
| // Escaped characters or end of input - either says this isn't a [:Property:] | |
| break; | |
| } | |
| if (fC.fChar == chColon) { | |
| nextChar(fC); | |
| if (fC.fChar == chRBracket) { | |
| sawPropSetTerminator = TRUE; | |
| } | |
| break; | |
| } | |
| } | |
| if (sawPropSetTerminator) { | |
| uset = createSetForProperty(propName, negated); | |
| } | |
| else | |
| { | |
| // No closing ":]". | |
| // Restore the original scan position. | |
| // The main scanner will retry the input as a normal set expression, | |
| // not a [:Property:] expression. | |
| fScanIndex = savedScanIndex; | |
| fQuoteMode = savedQuoteMode; | |
| fInBackslashQuote = savedInBackslashQuote; | |
| fEOLComments = savedEOLComments; | |
| fLineNum = savedLineNum; | |
| fCharNum = savedCharNum; | |
| fLastChar = savedLastChar; | |
| fPeekChar = savedPeekChar; | |
| fC = savedfC; | |
| UTEXT_SETNATIVEINDEX(fRXPat->fPattern, savedNextIndex); | |
| } | |
| return uset; | |
| } | |
| static inline void addIdentifierIgnorable(UnicodeSet *set, UErrorCode& ec) { | |
| set->add(0, 8).add(0x0e, 0x1b).add(0x7f, 0x9f); | |
| addCategory(set, U_GC_CF_MASK, ec); | |
| } | |
| // | |
| // Create a Unicode Set from a Unicode Property expression. | |
| // This is common code underlying both \p{...} ane [:...:] expressions. | |
| // Includes trying the Java "properties" that aren't supported as | |
| // normal ICU UnicodeSet properties | |
| // | |
| static const UChar posSetPrefix[] = {0x5b, 0x5c, 0x70, 0x7b, 0}; // "[\p{" | |
| static const UChar negSetPrefix[] = {0x5b, 0x5c, 0x50, 0x7b, 0}; // "[\P{" | |
| UnicodeSet *RegexCompile::createSetForProperty(const UnicodeString &propName, UBool negated) { | |
| UnicodeString setExpr; | |
| UnicodeSet *set; | |
| uint32_t usetFlags = 0; | |
| if (U_FAILURE(*fStatus)) { | |
| return NULL; | |
| } | |
| // | |
| // First try the property as we received it | |
| // | |
| if (negated) { | |
| setExpr.append(negSetPrefix, -1); | |
| } else { | |
| setExpr.append(posSetPrefix, -1); | |
| } | |
| setExpr.append(propName); | |
| setExpr.append(chRBrace); | |
| setExpr.append(chRBracket); | |
| if (fModeFlags & UREGEX_CASE_INSENSITIVE) { | |
| usetFlags |= USET_CASE_INSENSITIVE; | |
| } | |
| set = new UnicodeSet(setExpr, usetFlags, NULL, *fStatus); | |
| if (U_SUCCESS(*fStatus)) { | |
| return set; | |
| } | |
| delete set; | |
| set = NULL; | |
| // | |
| // The property as it was didn't work. | |
| // Do [:word:]. It is not recognized as a property by UnicodeSet. "word" not standard POSIX | |
| // or standard Java, but many other regular expression packages do recognize it. | |
| if (propName.caseCompare(UNICODE_STRING_SIMPLE("word"), 0) == 0) { | |
| *fStatus = U_ZERO_ERROR; | |
| set = new UnicodeSet(*(fRXPat->fStaticSets[URX_ISWORD_SET])); | |
| if (set == NULL) { | |
| *fStatus = U_MEMORY_ALLOCATION_ERROR; | |
| return set; | |
| } | |
| if (negated) { | |
| set->complement(); | |
| } | |
| return set; | |
| } | |
| // Do Java fixes - | |
| // InGreek -> InGreek or Coptic, that being the official Unicode name for that block. | |
| // InCombiningMarksforSymbols -> InCombiningDiacriticalMarksforSymbols. | |
| // | |
| // Note on Spaces: either "InCombiningMarksForSymbols" or "InCombining Marks for Symbols" | |
| // is accepted by Java. The property part of the name is compared | |
| // case-insenstively. The spaces must be exactly as shown, either | |
| // all there, or all omitted, with exactly one at each position | |
| // if they are present. From checking against JDK 1.6 | |
| // | |
| // This code should be removed when ICU properties support the Java compatibility names | |
| // (ICU 4.0?) | |
| // | |
| UnicodeString mPropName = propName; | |
| if (mPropName.caseCompare(UNICODE_STRING_SIMPLE("InGreek"), 0) == 0) { | |
| mPropName = UNICODE_STRING_SIMPLE("InGreek and Coptic"); | |
| } | |
| if (mPropName.caseCompare(UNICODE_STRING_SIMPLE("InCombining Marks for Symbols"), 0) == 0 || | |
| mPropName.caseCompare(UNICODE_STRING_SIMPLE("InCombiningMarksforSymbols"), 0) == 0) { | |
| mPropName = UNICODE_STRING_SIMPLE("InCombining Diacritical Marks for Symbols"); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("all")) == 0) { | |
| mPropName = UNICODE_STRING_SIMPLE("javaValidCodePoint"); | |
| } | |
| // See if the property looks like a Java "InBlockName", which | |
| // we will recast as "Block=BlockName" | |
| // | |
| static const UChar IN[] = {0x49, 0x6E, 0}; // "In" | |
| static const UChar BLOCK[] = {0x42, 0x6C, 0x6f, 0x63, 0x6b, 0x3d, 00}; // "Block=" | |
| if (mPropName.startsWith(IN, 2) && propName.length()>=3) { | |
| setExpr.truncate(4); // Leaves "[\p{", or "[\P{" | |
| setExpr.append(BLOCK, -1); | |
| setExpr.append(UnicodeString(mPropName, 2)); // Property with the leading "In" removed. | |
| setExpr.append(chRBrace); | |
| setExpr.append(chRBracket); | |
| *fStatus = U_ZERO_ERROR; | |
| set = new UnicodeSet(setExpr, usetFlags, NULL, *fStatus); | |
| if (U_SUCCESS(*fStatus)) { | |
| return set; | |
| } | |
| delete set; | |
| set = NULL; | |
| } | |
| if (propName.startsWith(UNICODE_STRING_SIMPLE("java")) || | |
| propName.compare(UNICODE_STRING_SIMPLE("all")) == 0) | |
| { | |
| UErrorCode localStatus = U_ZERO_ERROR; | |
| //setExpr.remove(); | |
| set = new UnicodeSet(); | |
| // | |
| // Try the various Java specific properties. | |
| // These all begin with "java" | |
| // | |
| if (mPropName.compare(UNICODE_STRING_SIMPLE("javaDefined")) == 0) { | |
| addCategory(set, U_GC_CN_MASK, localStatus); | |
| set->complement(); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaDigit")) == 0) { | |
| addCategory(set, U_GC_ND_MASK, localStatus); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaIdentifierIgnorable")) == 0) { | |
| addIdentifierIgnorable(set, localStatus); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaISOControl")) == 0) { | |
| set->add(0, 0x1F).add(0x7F, 0x9F); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaJavaIdentifierPart")) == 0) { | |
| addCategory(set, U_GC_L_MASK, localStatus); | |
| addCategory(set, U_GC_SC_MASK, localStatus); | |
| addCategory(set, U_GC_PC_MASK, localStatus); | |
| addCategory(set, U_GC_ND_MASK, localStatus); | |
| addCategory(set, U_GC_NL_MASK, localStatus); | |
| addCategory(set, U_GC_MC_MASK, localStatus); | |
| addCategory(set, U_GC_MN_MASK, localStatus); | |
| addIdentifierIgnorable(set, localStatus); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaJavaIdentifierStart")) == 0) { | |
| addCategory(set, U_GC_L_MASK, localStatus); | |
| addCategory(set, U_GC_NL_MASK, localStatus); | |
| addCategory(set, U_GC_SC_MASK, localStatus); | |
| addCategory(set, U_GC_PC_MASK, localStatus); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaLetter")) == 0) { | |
| addCategory(set, U_GC_L_MASK, localStatus); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaLetterOrDigit")) == 0) { | |
| addCategory(set, U_GC_L_MASK, localStatus); | |
| addCategory(set, U_GC_ND_MASK, localStatus); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaLowerCase")) == 0) { | |
| addCategory(set, U_GC_LL_MASK, localStatus); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaMirrored")) == 0) { | |
| set->applyIntPropertyValue(UCHAR_BIDI_MIRRORED, 1, localStatus); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaSpaceChar")) == 0) { | |
| addCategory(set, U_GC_Z_MASK, localStatus); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaSupplementaryCodePoint")) == 0) { | |
| set->add(0x10000, UnicodeSet::MAX_VALUE); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaTitleCase")) == 0) { | |
| addCategory(set, U_GC_LT_MASK, localStatus); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaUnicodeIdentifierStart")) == 0) { | |
| addCategory(set, U_GC_L_MASK, localStatus); | |
| addCategory(set, U_GC_NL_MASK, localStatus); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaUnicodeIdentifierPart")) == 0) { | |
| addCategory(set, U_GC_L_MASK, localStatus); | |
| addCategory(set, U_GC_PC_MASK, localStatus); | |
| addCategory(set, U_GC_ND_MASK, localStatus); | |
| addCategory(set, U_GC_NL_MASK, localStatus); | |
| addCategory(set, U_GC_MC_MASK, localStatus); | |
| addCategory(set, U_GC_MN_MASK, localStatus); | |
| addIdentifierIgnorable(set, localStatus); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaUpperCase")) == 0) { | |
| addCategory(set, U_GC_LU_MASK, localStatus); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaValidCodePoint")) == 0) { | |
| set->add(0, UnicodeSet::MAX_VALUE); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaWhitespace")) == 0) { | |
| addCategory(set, U_GC_Z_MASK, localStatus); | |
| set->removeAll(UnicodeSet().add(0xa0).add(0x2007).add(0x202f)); | |
| set->add(9, 0x0d).add(0x1c, 0x1f); | |
| } | |
| else if (mPropName.compare(UNICODE_STRING_SIMPLE("all")) == 0) { | |
| set->add(0, UnicodeSet::MAX_VALUE); | |
| } | |
| if (U_SUCCESS(localStatus) && !set->isEmpty()) { | |
| *fStatus = U_ZERO_ERROR; | |
| if (usetFlags & USET_CASE_INSENSITIVE) { | |
| set->closeOver(USET_CASE_INSENSITIVE); | |
| } | |
| if (negated) { | |
| set->complement(); | |
| } | |
| return set; | |
| } | |
| delete set; | |
| set = NULL; | |
| } | |
| error(*fStatus); | |
| return NULL; | |
| } | |
| // | |
| // SetEval Part of the evaluation of [set expressions]. | |
| // Perform any pending (stacked) operations with precedence | |
| // equal or greater to that of the next operator encountered | |
| // in the expression. | |
| // | |
| void RegexCompile::setEval(int32_t nextOp) { | |
| UnicodeSet *rightOperand = NULL; | |
| UnicodeSet *leftOperand = NULL; | |
| for (;;) { | |
| U_ASSERT(fSetOpStack.empty()==FALSE); | |
| int32_t pendingSetOperation = fSetOpStack.peeki(); | |
| if ((pendingSetOperation&0xffff0000) < (nextOp&0xffff0000)) { | |
| break; | |
| } | |
| fSetOpStack.popi(); | |
| U_ASSERT(fSetStack.empty() == FALSE); | |
| rightOperand = (UnicodeSet *)fSetStack.peek(); | |
| switch (pendingSetOperation) { | |
| case setNegation: | |
| rightOperand->complement(); | |
| break; | |
| case setCaseClose: | |
| // TODO: need a simple close function. Ticket 6065 | |
| rightOperand->closeOver(USET_CASE_INSENSITIVE); | |
| rightOperand->removeAllStrings(); | |
| break; | |
| case setDifference1: | |
| case setDifference2: | |
| fSetStack.pop(); | |
| leftOperand = (UnicodeSet *)fSetStack.peek(); | |
| leftOperand->removeAll(*rightOperand); | |
| delete rightOperand; | |
| break; | |
| case setIntersection1: | |
| case setIntersection2: | |
| fSetStack.pop(); | |
| leftOperand = (UnicodeSet *)fSetStack.peek(); | |
| leftOperand->retainAll(*rightOperand); | |
| delete rightOperand; | |
| break; | |
| case setUnion: | |
| fSetStack.pop(); | |
| leftOperand = (UnicodeSet *)fSetStack.peek(); | |
| leftOperand->addAll(*rightOperand); | |
| delete rightOperand; | |
| break; | |
| default: | |
| U_ASSERT(FALSE); | |
| break; | |
| } | |
| } | |
| } | |
| void RegexCompile::setPushOp(int32_t op) { | |
| setEval(op); | |
| fSetOpStack.push(op, *fStatus); | |
| fSetStack.push(new UnicodeSet(), *fStatus); | |
| } | |
| U_NAMESPACE_END | |
| #endif // !UCONFIG_NO_REGULAR_EXPRESSIONS | |