diff options
Diffstat (limited to 'deps/node/deps/icu-small/source/i18n/regexcmp.cpp')
| -rw-r--r-- | deps/node/deps/icu-small/source/i18n/regexcmp.cpp | 4638 |
1 files changed, 0 insertions, 4638 deletions
diff --git a/deps/node/deps/icu-small/source/i18n/regexcmp.cpp b/deps/node/deps/icu-small/source/i18n/regexcmp.cpp deleted file mode 100644 index 0c5fca6f..00000000 --- a/deps/node/deps/icu-small/source/i18n/regexcmp.cpp +++ /dev/null @@ -1,4638 +0,0 @@ -// © 2016 and later: Unicode, Inc. and others. -// License & terms of use: http://www.unicode.org/copyright.html -// -// file: regexcmp.cpp -// -// Copyright (C) 2002-2016 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 "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 "cstr.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. - // 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. - // 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 (c < UCHAR_MIN_VALUE || c > UCHAR_MAX_VALUE) { - // This function should never be called with an invalid input character. - U_ASSERT(FALSE); - starterChars->clear(); - } else 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); - } -} - - -// 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; - } -} - - -//------------------------------------------------------------------------------ -// -// 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 = safeIncrement(currentLen, 1); - 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 = safeIncrement(currentLen, 1); - 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 = safeIncrement(currentLen, 1); - 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 = safeIncrement(currentLen, 1); - 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 = safeIncrement(currentLen, 1); - 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 = safeIncrement(currentLen, 1); - 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 = safeIncrement(currentLen, 1); - 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 = safeIncrement(currentLen, 1); - 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 = safeIncrement(currentLen, 1); - atStart = FALSE; - break; - - - case URX_JMPX: - loc++; // Except for extra operand on URX_JMPX, same as URX_JMP. - U_FALLTHROUGH; - 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 = safeIncrement(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 = safeIncrement(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 = safeIncrement(currentLen, 1); - break; - - - case URX_JMPX: - loc++; // URX_JMPX has an extra operand, ignored here, - // otherwise processed identically to URX_JMP. - U_FALLTHROUGH; - 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 = safeIncrement(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 = safeIncrement(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; -} - -//------------------------------------------------------------------------------ -// -// 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) || e == U_MEMORY_ALLOCATION_ERROR) { - *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 -// -UnicodeSet *RegexCompile::createSetForProperty(const UnicodeString &propName, UBool negated) { - - if (U_FAILURE(*fStatus)) { - return nullptr; - } - LocalPointer<UnicodeSet> set; - UErrorCode status = U_ZERO_ERROR; - - do { // non-loop, exists to allow breaks from the block. - // - // First try the property as we received it - // - UnicodeString setExpr; - uint32_t usetFlags = 0; - setExpr.append(u"[\\p{", -1); - setExpr.append(propName); - setExpr.append(u"}]", -1); - if (fModeFlags & UREGEX_CASE_INSENSITIVE) { - usetFlags |= USET_CASE_INSENSITIVE; - } - set.adoptInsteadAndCheckErrorCode(new UnicodeSet(setExpr, usetFlags, NULL, status), status); - if (U_SUCCESS(status) || status == U_MEMORY_ALLOCATION_ERROR) { - break; - } - - // - // The incoming property wasn't directly recognized by ICU. - - // Check [:word:] and [:all:]. These are not recognized as a properties by ICU UnicodeSet. - // Java accepts 'word' with mixed case. - // Java accepts 'all' only in all lower case. - - status = U_ZERO_ERROR; - if (propName.caseCompare(u"word", -1, 0) == 0) { - set.adoptInsteadAndCheckErrorCode(new UnicodeSet(*(fRXPat->fStaticSets[URX_ISWORD_SET])), status); - break; - } - if (propName.compare(u"all", -1) == 0) { - set.adoptInsteadAndCheckErrorCode(new UnicodeSet(0, 0x10ffff), status); - break; - } - - - // Do Java InBlock expressions - // - UnicodeString mPropName = propName; - if (mPropName.startsWith(u"In", 2) && mPropName.length() >= 3) { - status = U_ZERO_ERROR; - set.adoptInsteadAndCheckErrorCode(new UnicodeSet(), status); - if (U_FAILURE(status)) { - break; - } - UnicodeString blockName(mPropName, 2); // Property with the leading "In" removed. - set->applyPropertyAlias(UnicodeString(u"Block"), blockName, status); - break; - } - - // Check for the Java form "IsBooleanPropertyValue", which we will recast - // as "BooleanPropertyValue". The property value can be either a - // a General Category or a Script Name. - - if (propName.startsWith(u"Is", 2) && propName.length()>=3) { - mPropName.remove(0, 2); // Strip the "Is" - if (mPropName.indexOf(u'=') >= 0) { - // Reject any "Is..." property expression containing an '=', that is, - // any non-binary property expression. - status = U_REGEX_PROPERTY_SYNTAX; - break; - } - - if (mPropName.caseCompare(u"assigned", -1, 0) == 0) { - mPropName.setTo(u"unassigned", -1); - negated = !negated; - } else if (mPropName.caseCompare(u"TitleCase", -1, 0) == 0) { - mPropName.setTo(u"Titlecase_Letter", -1); - } - - mPropName.insert(0, u"[\\p{", -1); - mPropName.append(u"}]", -1); - set.adoptInsteadAndCheckErrorCode(new UnicodeSet(mPropName, *fStatus), status); - - if (U_SUCCESS(status) && !set->isEmpty() && (usetFlags & USET_CASE_INSENSITIVE)) { - set->closeOver(USET_CASE_INSENSITIVE); - } - break; - - } - - if (propName.startsWith(u"java", -1)) { - status = U_ZERO_ERROR; - set.adoptInsteadAndCheckErrorCode(new UnicodeSet(), status); - if (U_FAILURE(status)) { - break; - } - // - // Try the various Java specific properties. - // These all begin with "java" - // - if (propName.compare(u"javaDefined", -1) == 0) { - addCategory(set.getAlias(), U_GC_CN_MASK, status); - set->complement(); - } - else if (propName.compare(u"javaDigit", -1) == 0) { - addCategory(set.getAlias(), U_GC_ND_MASK, status); - } - else if (propName.compare(u"javaIdentifierIgnorable", -1) == 0) { - addIdentifierIgnorable(set.getAlias(), status); - } - else if (propName.compare(u"javaISOControl", -1) == 0) { - set->add(0, 0x1F).add(0x7F, 0x9F); - } - else if (propName.compare(u"javaJavaIdentifierPart", -1) == 0) { - addCategory(set.getAlias(), U_GC_L_MASK, status); - addCategory(set.getAlias(), U_GC_SC_MASK, status); - addCategory(set.getAlias(), U_GC_PC_MASK, status); - addCategory(set.getAlias(), U_GC_ND_MASK, status); - addCategory(set.getAlias(), U_GC_NL_MASK, status); - addCategory(set.getAlias(), U_GC_MC_MASK, status); - addCategory(set.getAlias(), U_GC_MN_MASK, status); - addIdentifierIgnorable(set.getAlias(), status); - } - else if (propName.compare(u"javaJavaIdentifierStart", -1) == 0) { - addCategory(set.getAlias(), U_GC_L_MASK, status); - addCategory(set.getAlias(), U_GC_NL_MASK, status); - addCategory(set.getAlias(), U_GC_SC_MASK, status); - addCategory(set.getAlias(), U_GC_PC_MASK, status); - } - else if (propName.compare(u"javaLetter", -1) == 0) { - addCategory(set.getAlias(), U_GC_L_MASK, status); - } - else if (propName.compare(u"javaLetterOrDigit", -1) == 0) { - addCategory(set.getAlias(), U_GC_L_MASK, status); - addCategory(set.getAlias(), U_GC_ND_MASK, status); - } - else if (propName.compare(u"javaLowerCase", -1) == 0) { - addCategory(set.getAlias(), U_GC_LL_MASK, status); - } - else if (propName.compare(u"javaMirrored", -1) == 0) { - set->applyIntPropertyValue(UCHAR_BIDI_MIRRORED, 1, status); - } - else if (propName.compare(u"javaSpaceChar", -1) == 0) { - addCategory(set.getAlias(), U_GC_Z_MASK, status); - } - else if (propName.compare(u"javaSupplementaryCodePoint", -1) == 0) { - set->add(0x10000, UnicodeSet::MAX_VALUE); - } - else if (propName.compare(u"javaTitleCase", -1) == 0) { - addCategory(set.getAlias(), U_GC_LT_MASK, status); - } - else if (propName.compare(u"javaUnicodeIdentifierStart", -1) == 0) { - addCategory(set.getAlias(), U_GC_L_MASK, status); - addCategory(set.getAlias(), U_GC_NL_MASK, status); - } - else if (propName.compare(u"javaUnicodeIdentifierPart", -1) == 0) { - addCategory(set.getAlias(), U_GC_L_MASK, status); - addCategory(set.getAlias(), U_GC_PC_MASK, status); - addCategory(set.getAlias(), U_GC_ND_MASK, status); - addCategory(set.getAlias(), U_GC_NL_MASK, status); - addCategory(set.getAlias(), U_GC_MC_MASK, status); - addCategory(set.getAlias(), U_GC_MN_MASK, status); - addIdentifierIgnorable(set.getAlias(), status); - } - else if (propName.compare(u"javaUpperCase", -1) == 0) { - addCategory(set.getAlias(), U_GC_LU_MASK, status); - } - else if (propName.compare(u"javaValidCodePoint", -1) == 0) { - set->add(0, UnicodeSet::MAX_VALUE); - } - else if (propName.compare(u"javaWhitespace", -1) == 0) { - addCategory(set.getAlias(), U_GC_Z_MASK, status); - set->removeAll(UnicodeSet().add(0xa0).add(0x2007).add(0x202f)); - set->add(9, 0x0d).add(0x1c, 0x1f); - } else { - status = U_REGEX_PROPERTY_SYNTAX; - } - - if (U_SUCCESS(status) && !set->isEmpty() && (usetFlags & USET_CASE_INSENSITIVE)) { - set->closeOver(USET_CASE_INSENSITIVE); - } - break; - } - - // Unrecognized property. ICU didn't like it as it was, and none of the Java compatibility - // extensions matched it. - status = U_REGEX_PROPERTY_SYNTAX; - } while (false); // End of do loop block. Code above breaks out of the block on success or hard failure. - - if (U_SUCCESS(status)) { - U_ASSERT(set.isValid()); - if (negated) { - set->complement(); - } - return set.orphan(); - } else { - if (status == U_ILLEGAL_ARGUMENT_ERROR) { - status = U_REGEX_PROPERTY_SYNTAX; - } - error(status); - return nullptr; - } -} - - -// -// 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 |