diff options
Diffstat (limited to 'Build/source/libs/icu/icu-xetex/i18n/regexcmp.cpp')
| -rw-r--r-- | Build/source/libs/icu/icu-xetex/i18n/regexcmp.cpp | 3529 |
1 files changed, 3529 insertions, 0 deletions
diff --git a/Build/source/libs/icu/icu-xetex/i18n/regexcmp.cpp b/Build/source/libs/icu/icu-xetex/i18n/regexcmp.cpp new file mode 100644 index 00000000000..558f80b6c48 --- /dev/null +++ b/Build/source/libs/icu/icu-xetex/i18n/regexcmp.cpp @@ -0,0 +1,3529 @@ + +// +// file: regexcmp.cpp +// +// Copyright (C) 2002-2007 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/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 "util.h" +#include "cmemory.h" +#include "cstring.h" +#include "uvectr32.h" +#include "uassert.h" +#include "ucln_in.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" + + + +U_NAMESPACE_BEGIN + + + + + +//------------------------------------------------------------------------------ +// +// Constructor. +// +//------------------------------------------------------------------------------ +RegexCompile::RegexCompile(RegexPattern *rxp, UErrorCode &status) : fParenStack(status) +{ + fStatus = &status; + + fRXPat = rxp; + fScanIndex = 0; + fNextIndex = 0; + fPeekChar = -1; + fLineNum = 1; + fCharNum = 0; + fQuoteMode = FALSE; + fInBackslashQuote = FALSE; + fModeFlags = fRXPat->fFlags | 0x80000000; + fEOLComments = TRUE; + + fMatchOpenParen = -1; + fMatchCloseParen = -1; + fStringOpStart = -1; + + if (U_SUCCESS(status) && U_FAILURE(rxp->fDeferredStatus)) { + status = rxp->fDeferredStatus; + } +} + + + +//------------------------------------------------------------------------------ +// +// Destructor +// +//------------------------------------------------------------------------------ +RegexCompile::~RegexCompile() { +} + +//------------------------------------------------------------------------------ +// +// 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 +{ + 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.length() == 0); + + // Prepare the RegexPattern object to receive the compiled pattern. + // TODO: remove per-instance field, and just use globals directly. (But check perf) + fRXPat->fPattern = pat; + fRXPat->fStaticSets = RegexStaticSets::gStaticSets->fPropSets; + fRXPat->fStaticSets8 = RegexStaticSets::gStaticSets->fPropSets8; + + + // Initialize the pattern scanning state machine + fPatternLength = pat.length(); + uint16_t state = 1; + const RegexTableEl *tableEl; + 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 + UnicodeSet *uniset = RegexStaticSets::gStaticSets->fRuleSets[tableEl->fCharClass-128]; + if (uniset->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); + } + } + + } + + // + // The pattern has now been read and processed, and the compiled code generated. + // + + // Back-reference fixup + // + int32_t loc; + for (loc=0; loc<fRXPat->fCompiledPat->size(); loc++) { + int32_t op = fRXPat->fCompiledPat->elementAti(loc); + int32_t opType = URX_TYPE(op); + if (opType == URX_BACKREF || opType == 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 = URX_BUILD(opType, where); + fRXPat->fCompiledPat->setElementAt(op, loc); + } + } + + + // + // Compute the number of digits requried for the largest capture group number. + // + fRXPat->fMaxCaptureDigits = 1; + int32_t n = 10; + for (;;) { + if (n > fRXPat->fGroupMap->size()) { + break; + } + fRXPat->fMaxCaptureDigits++; + n *= 10; + } + + // + // 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 and the + // position in the compiled pattern. + // + fRXPat->fFrameSize+=2; + + // + // 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 passes + // + matchStartType(); + OptDotStar(); + stripNOPs(); + + // + // Set up fast latin-1 range sets + // + int32_t numSets = fRXPat->fSets->size(); + fRXPat->fSets8 = new Regex8BitSet[numSets]; + 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 + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_STATE_SAVE, 2), *fStatus); + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_JMP, 3), *fStatus); + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_FAIL, 0), *fStatus); + + // 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. + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_END, 0), *fStatus); + + // Terminate the pattern compilation state machine. + returnVal = FALSE; + break; + + + + case doOrOperator: + // Scanning a '|', as in (A|B) + { + // 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 = fRXPat->fCompiledPat->elementAti(savePosition); + U_ASSERT(URX_TYPE(op) == URX_NOP); // original contents of reserved location + op = URX_BUILD(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. + op = URX_BUILD(URX_JMP, 0); + fRXPat->fCompiledPat->addElement(op, *fStatus); + + // 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. + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus); + fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); + } + break; + + + case doOpenCaptureParen: + // Open Paren. + // 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 positino. + // 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_CAPure is encountered. + { + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus); + int32_t varsLoc = fRXPat->fFrameSize; // Reserve three slots in match stack frame. + fRXPat->fFrameSize += 3; + int32_t cop = URX_BUILD(URX_START_CAPTURE, varsLoc); + fRXPat->fCompiledPat->addElement(cop, *fStatus); + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus); + + // 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); + } + 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. + { + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus); + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus); + + // 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. + { + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus); + int32_t varLoc = fRXPat->fDataSize; // Reserve a data location for saving the + fRXPat->fDataSize += 1; // state stack ptr. + int32_t stoOp = URX_BUILD(URX_STO_SP, varLoc); + fRXPat->fCompiledPat->addElement(stoOp, *fStatus); + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus); + + // 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 ) + // Compiles to + // 1 START_LA dataLoc + // 2. 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. + // 3. NOP may be replaced if there is are '|' ops in the block. + // 4. code for parenthesized stuff. + // 5. ENDLA + // + // Two data slots are reserved, for saving the stack ptr and the input position. + { + int32_t dataLoc = fRXPat->fDataSize; + fRXPat->fDataSize += 2; + int32_t op = URX_BUILD(URX_LA_START, dataLoc); + fRXPat->fCompiledPat->addElement(op, *fStatus); + + op = URX_BUILD(URX_NOP, 0); + fRXPat->fCompiledPat->addElement(op, *fStatus); + fRXPat->fCompiledPat->addElement(op, *fStatus); + + // 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. FAIL // code in block succeeded, so neg. lookahead fails. + // 7. ... + { + int32_t dataLoc = fRXPat->fDataSize; + fRXPat->fDataSize += 2; + int32_t op = URX_BUILD(URX_LA_START, dataLoc); + fRXPat->fCompiledPat->addElement(op, *fStatus); + + op = URX_BUILD(URX_STATE_SAVE, 0); // dest address will be patched later. + fRXPat->fCompiledPat->addElement(op, *fStatus); + + op = URX_BUILD(URX_NOP, 0); + fRXPat->fCompiledPat->addElement(op, *fStatus); + + // 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 and #6 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. + + // Allocate data space + int32_t dataLoc = fRXPat->fDataSize; + fRXPat->fDataSize += 4; + + // Emit URX_LB_START + int32_t op = URX_BUILD(URX_LB_START, dataLoc); + fRXPat->fCompiledPat->addElement(op, *fStatus); + + // Emit URX_LB_CONT + op = URX_BUILD(URX_LB_CONT, dataLoc); + fRXPat->fCompiledPat->addElement(op, *fStatus); + fRXPat->fCompiledPat->addElement(0, *fStatus); // MinMatchLength. To be filled later. + fRXPat->fCompiledPat->addElement(0, *fStatus); // MaxMatchLength. To be filled later. + + // Emit the NOP + op = URX_BUILD(URX_NOP, 0); + fRXPat->fCompiledPat->addElement(op, *fStatus); + fRXPat->fCompiledPat->addElement(op, *fStatus); + + // 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. + + // Allocate data space + int32_t dataLoc = fRXPat->fDataSize; + fRXPat->fDataSize += 4; + + // Emit URX_LB_START + int32_t op = URX_BUILD(URX_LB_START, dataLoc); + fRXPat->fCompiledPat->addElement(op, *fStatus); + + // Emit URX_LBN_CONT + op = URX_BUILD(URX_LBN_CONT, dataLoc); + fRXPat->fCompiledPat->addElement(op, *fStatus); + fRXPat->fCompiledPat->addElement(0, *fStatus); // MinMatchLength. To be filled later. + fRXPat->fCompiledPat->addElement(0, *fStatus); // MaxMatchLength. To be filled later. + fRXPat->fCompiledPat->addElement(0, *fStatus); // Continue Loc. To be filled later. + + // Emit the NOP + op = URX_BUILD(URX_NOP, 0); + fRXPat->fCompiledPat->addElement(op, *fStatus); + fRXPat->fCompiledPat->addElement(op, *fStatus); + + // 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 = fRXPat->fCompiledPat->elementAti(topLoc); + + if (URX_TYPE(repeatedOp) == URX_SETREF) { + // Emit optimized code for [char set]+ + int32_t loopOpI = URX_BUILD(URX_LOOP_SR_I, URX_VAL(repeatedOp)); + fRXPat->fCompiledPat->addElement(loopOpI, *fStatus); + frameLoc = fRXPat->fFrameSize; + fRXPat->fFrameSize++; + int32_t loopOpC = URX_BUILD(URX_LOOP_C, frameLoc); + fRXPat->fCompiledPat->addElement(loopOpC, *fStatus); + break; + } + + if (URX_TYPE(repeatedOp) == URX_DOTANY || + URX_TYPE(repeatedOp) == URX_DOTANY_ALL) { + // Emit Optimized code for .+ operations. + int32_t loopOpI = URX_BUILD(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; + } + fRXPat->fCompiledPat->addElement(loopOpI, *fStatus); + frameLoc = fRXPat->fFrameSize; + fRXPat->fFrameSize++; + int32_t loopOpC = URX_BUILD(URX_LOOP_C, frameLoc); + fRXPat->fCompiledPat->addElement(loopOpC, *fStatus); + 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 = fRXPat->fFrameSize; + fRXPat->fFrameSize++; + + int32_t op = URX_BUILD(URX_STO_INP_LOC, frameLoc); + fRXPat->fCompiledPat->setElementAt(op, topLoc); + + op = URX_BUILD(URX_JMP_SAV_X, topLoc+1); + fRXPat->fCompiledPat->addElement(op, *fStatus); + } else { + // Simpler code when the repeated body must match something non-empty + int32_t jmpOp = URX_BUILD(URX_JMP_SAV, topLoc); + fRXPat->fCompiledPat->addElement(jmpOp, *fStatus); + } + } + break; + + case doNGPlus: + // Non-greedy '+?' compiles to + // 1. stuff to be repeated (already built) + // 2. state-save 1 + // 3. ... + { + int32_t topLoc = blockTopLoc(FALSE); + int32_t saveStateOp = URX_BUILD(URX_STATE_SAVE, topLoc); + fRXPat->fCompiledPat->addElement(saveStateOp, *fStatus); + } + 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 = URX_BUILD(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 = URX_BUILD(URX_JMP, jmp2_loc+1); + fRXPat->fCompiledPat->setElementAt(jmp1_op, jmp1_loc); + + int32_t jmp2_op = URX_BUILD(URX_JMP, jmp2_loc+2); + fRXPat->fCompiledPat->addElement(jmp2_op, *fStatus); + + int32_t save_op = URX_BUILD(URX_STATE_SAVE, jmp1_loc+1); + fRXPat->fCompiledPat->addElement(save_op, *fStatus); + } + 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 = fRXPat->fCompiledPat->elementAti(topLoc); + + if (URX_TYPE(repeatedOp) == URX_SETREF) { + // Emit optimized code for a [char set]* + int32_t loopOpI = URX_BUILD(URX_LOOP_SR_I, URX_VAL(repeatedOp)); + fRXPat->fCompiledPat->setElementAt(loopOpI, topLoc); + dataLoc = fRXPat->fFrameSize; + fRXPat->fFrameSize++; + int32_t loopOpC = URX_BUILD(URX_LOOP_C, dataLoc); + fRXPat->fCompiledPat->addElement(loopOpC, *fStatus); + break; + } + + if (URX_TYPE(repeatedOp) == URX_DOTANY || + URX_TYPE(repeatedOp) == URX_DOTANY_ALL) { + // Emit Optimized code for .* operations. + int32_t loopOpI = URX_BUILD(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; + } + fRXPat->fCompiledPat->setElementAt(loopOpI, topLoc); + dataLoc = fRXPat->fFrameSize; + fRXPat->fFrameSize++; + int32_t loopOpC = URX_BUILD(URX_LOOP_C, dataLoc); + fRXPat->fCompiledPat->addElement(loopOpC, *fStatus); + break; + } + } + + // Emit general case code for this * + // The optimizations did not apply. + + int32_t saveStateLoc = blockTopLoc(TRUE); + int32_t jmpOp = URX_BUILD(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 = fRXPat->fFrameSize; + fRXPat->fFrameSize++; + + int32_t op = URX_BUILD(URX_STO_INP_LOC, dataLoc); + fRXPat->fCompiledPat->setElementAt(op, saveStateLoc+1); + jmpOp = URX_BUILD(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 store it into the compiled code. + int32_t saveStateOp = URX_BUILD(URX_STATE_SAVE, continueLoc); + fRXPat->fCompiledPat->setElementAt(saveStateOp, saveStateLoc); + + // Append the URX_JMP_SAV or URX_JMPX operation to the compiled pattern. + fRXPat->fCompiledPat->addElement(jmpOp, *fStatus); + } + 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 = URX_BUILD(URX_JMP, saveLoc); + int32_t stateSaveOp = URX_BUILD(URX_STATE_SAVE, jmpLoc+1); + fRXPat->fCompiledPat->setElementAt(jmpOp, jmpLoc); + fRXPat->fCompiledPat->addElement(stateSaveOp, *fStatus); + } + 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); + fIntervalLow = fIntervalLow*10 + digitValue; + if (fIntervalLow < 0) { + error(U_REGEX_NUMBER_TOO_BIG); + } + } + 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); + fIntervalUpper = fIntervalUpper*10 + digitValue; + if (fIntervalUpper < 0) { + error(U_REGEX_NUMBER_TOO_BIG); + } + } + 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, becuase + // 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 = fRXPat->fDataSize; // Reserve a data location for saving the + fRXPat->fDataSize += 1; // state stack ptr. + int32_t op = URX_BUILD(URX_STO_SP, varLoc); + fRXPat->fCompiledPat->setElementAt(op, topLoc); + + int32_t loopOp = 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 + op = URX_BUILD(URX_LD_SP, varLoc); + fRXPat->fCompiledPat->addElement(op, *fStatus); + } + + 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 doDotAny: + // scanned a ".", match any single character. + { + int32_t op; + if (fModeFlags & UREGEX_DOTALL) { + op = URX_BUILD(URX_DOTANY_ALL, 0); + } else { + op = URX_BUILD(URX_DOTANY, 0); + } + fRXPat->fCompiledPat->addElement(op, *fStatus); + } + break; + + case doCaret: + { + int32_t op = (fModeFlags & UREGEX_MULTILINE)? URX_CARET_M : URX_CARET; + fRXPat->fCompiledPat->addElement(URX_BUILD(op, 0), *fStatus); + } + break; + + + case doDollar: + { + int32_t op = (fModeFlags & UREGEX_MULTILINE)? URX_DOLLAR_M : URX_DOLLAR; + fRXPat->fCompiledPat->addElement(URX_BUILD(op, 0), *fStatus); + } + break; + + case doBackslashA: + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_CARET, 0), *fStatus); + break; + + case doBackslashB: + { + #if UCONFIG_NO_BREAK_ITERATION==1 + if (fModeFlags & UREGEX_UWORD) { + error(U_UNSUPPORTED_ERROR); + } + #endif + int32_t op = (fModeFlags & UREGEX_UWORD)? URX_BACKSLASH_BU : URX_BACKSLASH_B; + fRXPat->fCompiledPat->addElement(URX_BUILD(op, 1), *fStatus); + } + break; + + case doBackslashb: + { + #if UCONFIG_NO_BREAK_ITERATION==1 + if (fModeFlags & UREGEX_UWORD) { + error(U_UNSUPPORTED_ERROR); + } + #endif + int32_t op = (fModeFlags & UREGEX_UWORD)? URX_BACKSLASH_BU : URX_BACKSLASH_B; + fRXPat->fCompiledPat->addElement(URX_BUILD(op, 0), *fStatus); + } + break; + + case doBackslashD: + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_D, 1), *fStatus); + break; + + case doBackslashd: + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_D, 0), *fStatus); + break; + + case doBackslashG: + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_G, 0), *fStatus); + break; + + case doBackslashS: + fRXPat->fCompiledPat->addElement( + URX_BUILD(URX_STAT_SETREF_N, URX_ISSPACE_SET), *fStatus); + break; + + case doBackslashs: + fRXPat->fCompiledPat->addElement( + URX_BUILD(URX_STATIC_SETREF, URX_ISSPACE_SET), *fStatus); + break; + + case doBackslashW: + fRXPat->fCompiledPat->addElement( + URX_BUILD(URX_STAT_SETREF_N, URX_ISWORD_SET), *fStatus); + break; + + case doBackslashw: + fRXPat->fCompiledPat->addElement( + URX_BUILD(URX_STATIC_SETREF, URX_ISWORD_SET), *fStatus); + break; + + case doBackslashX: + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_X, 0), *fStatus); + break; + + + case doBackslashZ: + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_DOLLAR, 0), *fStatus); + break; + + case doBackslashz: + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_Z, 0), *fStatus); + break; + + case doEscapeError: + error(U_REGEX_BAD_ESCAPE_SEQUENCE); + break; + + case doExit: + returnVal = FALSE; + break; + + case doProperty: + { + UnicodeSet *theSet = scanProp(); + compileSet(theSet); + } + break; + + + case doScanUnicodeSet: + { + UnicodeSet *theSet = scanSet(); + compileSet(theSet); + } + break; + + case doEnterQuoteMode: + // Just scanned a \Q. Put character scanner into quote mode. + fQuoteMode = TRUE; + 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); + int32_t op; + if (fModeFlags & UREGEX_CASE_INSENSITIVE) { + op = URX_BUILD(URX_BACKREF_I, groupNum); + } else { + op = URX_BUILD(URX_BACKREF, groupNum); + } + fRXPat->fCompiledPat->addElement(op, *fStatus); + } + 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 + // + { + // Emit the STO_SP + int32_t topLoc = blockTopLoc(TRUE); + int32_t stoLoc = fRXPat->fDataSize; + fRXPat->fDataSize++; // Reserve the data location for storing save stack ptr. + int32_t op = URX_BUILD(URX_STO_SP, stoLoc); + fRXPat->fCompiledPat->setElementAt(op, topLoc); + + // Emit the STATE_SAVE + op = URX_BUILD(URX_STATE_SAVE, fRXPat->fCompiledPat->size()+2); + fRXPat->fCompiledPat->addElement(op, *fStatus); + + // Emit the JMP + op = URX_BUILD(URX_JMP, topLoc+1); + fRXPat->fCompiledPat->addElement(op, *fStatus); + + // Emit the LD_SP + op = URX_BUILD(URX_LD_SP, stoLoc); + fRXPat->fCompiledPat->addElement(op, *fStatus); + } + 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 = fRXPat->fDataSize; + fRXPat->fDataSize++; // Reserve the data location for storing save stack ptr. + int32_t op = URX_BUILD(URX_STO_SP, stoLoc); + fRXPat->fCompiledPat->setElementAt(op, topLoc); + + // Emit the SAVE_STATE 5 + int32_t L7 = fRXPat->fCompiledPat->size()+1; + op = URX_BUILD(URX_STATE_SAVE, L7); + fRXPat->fCompiledPat->setElementAt(op, topLoc+1); + + // Append the JMP operation. + op = URX_BUILD(URX_JMP, topLoc+1); + fRXPat->fCompiledPat->addElement(op, *fStatus); + + // Emit the LD_SP loc + op = URX_BUILD(URX_LD_SP, stoLoc); + fRXPat->fCompiledPat->addElement(op, *fStatus); + } + 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 = fRXPat->fDataSize; + fRXPat->fDataSize++; // Reserve the data location for storing save stack ptr. + int32_t op = URX_BUILD(URX_STO_SP, stoLoc); + fRXPat->fCompiledPat->setElementAt(op, topLoc); + + // Emit the SAVE_STATE + int32_t continueLoc = fRXPat->fCompiledPat->size()+1; + op = URX_BUILD(URX_STATE_SAVE, continueLoc); + fRXPat->fCompiledPat->setElementAt(op, topLoc+1); + + // Emit the LD_SP + op = URX_BUILD(URX_LD_SP, stoLoc); + fRXPat->fCompiledPat->addElement(op, *fStatus); + } + 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 0x6d: /* 'm' */ bit = UREGEX_MULTILINE; break; + case 0x73: /* 's' */ bit = UREGEX_DOTALL; 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: + // 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; + + // Prevent any string from spanning across the change of match mode. + // Otherwise the pattern "abc(?i)def" would make a single string of "abcdef" + fixLiterals(); + 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. + { + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus); + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus); + + // 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; + + + + 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. +// If we are in a pattern string already, add the new char to it. +// If we aren't in a pattern string, begin one now. +// +//------------------------------------------------------------------------------ +void RegexCompile::literalChar(UChar32 c) { + int32_t op; // An operation in the compiled pattern. + int32_t opType; + int32_t patternLoc; // A position in the compiled pattern. + int32_t stringLen; + + + // If the last thing compiled into the pattern was not a literal char, + // force this new literal char to begin a new string, and not append to the previous. + op = fRXPat->fCompiledPat->lastElementi(); + opType = URX_TYPE(op); + if (!(opType == URX_STRING_LEN || opType == URX_ONECHAR || opType == URX_ONECHAR_I)) { + fixLiterals(); + } + + if (fStringOpStart == -1) { + // First char of a string in the pattern. + // Emit a OneChar op into the compiled pattern. + emitONE_CHAR(c); + + // Also add it to the string pool, in case we get a second adjacent literal + // and want to change form ONE_CHAR to STRING + fStringOpStart = fRXPat->fLiteralText.length(); + fRXPat->fLiteralText.append(c); + return; + } + + // We are adding onto an existing string + fRXPat->fLiteralText.append(c); + + op = fRXPat->fCompiledPat->lastElementi(); + opType = URX_TYPE(op); + U_ASSERT(opType == URX_ONECHAR || opType == URX_ONECHAR_I || opType == URX_STRING_LEN); + + // If the most recently emitted op is a URX_ONECHAR, + if (opType == URX_ONECHAR || opType == URX_ONECHAR_I) { + if (U16_IS_TRAIL(c) && U16_IS_LEAD(URX_VAL(op))) { + // The most recently emitted op is a ONECHAR that was the first half + // of a surrogate pair. Update the ONECHAR's operand to be the + // supplementary code point resulting from both halves of the pair. + c = U16_GET_SUPPLEMENTARY(URX_VAL(op), c); + op = URX_BUILD(opType, c); + patternLoc = fRXPat->fCompiledPat->size() - 1; + fRXPat->fCompiledPat->setElementAt(op, patternLoc); + return; + } + + // The most recently emitted op is a ONECHAR. + // We've now received another adjacent char. Change the ONECHAR op + // to a string op. + if (fModeFlags & UREGEX_CASE_INSENSITIVE) { + op = URX_BUILD(URX_STRING_I, fStringOpStart); + } else { + op = URX_BUILD(URX_STRING, fStringOpStart); + } + patternLoc = fRXPat->fCompiledPat->size() - 1; + fRXPat->fCompiledPat->setElementAt(op, patternLoc); + op = URX_BUILD(URX_STRING_LEN, 0); + fRXPat->fCompiledPat->addElement(op, *fStatus); + } + + // The pattern contains a URX_SRING / URX_STRING_LEN. Update the + // string length to reflect the new char we just added to the string. + stringLen = fRXPat->fLiteralText.length() - fStringOpStart; + op = URX_BUILD(URX_STRING_LEN, stringLen); + patternLoc = fRXPat->fCompiledPat->size() - 1; + fRXPat->fCompiledPat->setElementAt(op, patternLoc); +} + + + +//------------------------------------------------------------------------------ +// +// emitONE_CHAR emit a ONE_CHAR op into the generated code. +// Choose cased or uncased version, depending on the +// match mode and whether the character itself is cased. +// +//------------------------------------------------------------------------------ +void RegexCompile::emitONE_CHAR(UChar32 c) { + int32_t op; + if ((fModeFlags & UREGEX_CASE_INSENSITIVE) && + u_hasBinaryProperty(c, UCHAR_CASE_SENSITIVE)) { + // We have a cased character, and are in case insensitive matching mode. + c = u_foldCase(c, U_FOLD_CASE_DEFAULT); + op = URX_BUILD(URX_ONECHAR_I, c); + } else { + // Uncased char, or case sensitive match mode. + // Either way, just generate a literal compare of the char. + op = URX_BUILD(URX_ONECHAR, c); + } + fRXPat->fCompiledPat->addElement(op, *fStatus); +} + + +//------------------------------------------------------------------------------ +// +// fixLiterals When compiling something that can follow a literal +// string in a pattern, we need to "fix" any preceding +// string, which will cause any subsequent literals to +// begin a new string, rather than appending to the +// old one. +// +// 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) { + int32_t stringStart = fStringOpStart; // start index of the current literal string + int32_t op; // An op from/for the compiled pattern. + int32_t opType; // An opcode type from the compiled pattern. + int32_t stringLastCharIdx; + UChar32 lastChar; + int32_t stringNextToLastCharIdx; + UChar32 nextToLastChar; + int32_t stringLen; + + fStringOpStart = -1; + if (!split) { + return; + } + + // Split: We need to ensure that the last item in the compiled pattern does + // not refer to a literal string of more than one char. If it does, + // separate the last char from the rest of the string. + + // If the last operation from the compiled pattern is not a string, + // nothing needs to be done + op = fRXPat->fCompiledPat->lastElementi(); + opType = URX_TYPE(op); + if (opType != URX_STRING_LEN) { + return; + } + stringLen = URX_VAL(op); + + // + // Find the position of the last code point in the string (might be a surrogate pair) + // + stringLastCharIdx = fRXPat->fLiteralText.length(); + stringLastCharIdx = fRXPat->fLiteralText.moveIndex32(stringLastCharIdx, -1); + lastChar = fRXPat->fLiteralText.char32At(stringLastCharIdx); + + // The string should always be at least two code points long, meaning that there + // should be something before the last char position that we just found. + U_ASSERT(stringLastCharIdx > stringStart); + stringNextToLastCharIdx = fRXPat->fLiteralText.moveIndex32(stringLastCharIdx, -1); + U_ASSERT(stringNextToLastCharIdx >= stringStart); + nextToLastChar = fRXPat->fLiteralText.char32At(stringNextToLastCharIdx); + + if (stringNextToLastCharIdx > stringStart) { + // The length of string remaining after removing one char is two or more. + // Leave the string in the compiled pattern, shorten it by one char, + // and append a URX_ONECHAR op for the last char. + stringLen -= (fRXPat->fLiteralText.length() - stringLastCharIdx); + op = URX_BUILD(URX_STRING_LEN, stringLen); + fRXPat->fCompiledPat->setElementAt(op, fRXPat->fCompiledPat->size() -1); + emitONE_CHAR(lastChar); + } else { + // The original string consisted of exactly two characters. Replace + // the existing compiled URX_STRING/URX_STRING_LEN ops with a pair + // of URX_ONECHARs. + fRXPat->fCompiledPat->setSize(fRXPat->fCompiledPat->size() -2); + emitONE_CHAR(nextToLastChar); + emitONE_CHAR(lastChar); + } +} + + + + + + +//------------------------------------------------------------------------------ +// +// 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) { + UVector32 *code = fRXPat->fCompiledPat; + U_ASSERT(where>0 && where < code->size()); + + int32_t nop = URX_BUILD(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 = 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_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 = URX_BUILD(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++; + } +} + + + +//------------------------------------------------------------------------------ +// +// 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; + 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, or a set reference. + // No slot for STATE_SAVE was pre-reserved in the compiled code. + // We need to make space now. + fixLiterals(TRUE); // If last item was a string, separate the last char. + theLoc = fRXPat->fCompiledPat->size()-1; + if (reserveLoc) { + /*int32_t opAtTheLoc = fRXPat->fCompiledPat->elementAti(theLoc);*/ + int32_t nop = URX_BUILD(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; + } + + // Force any literal chars that may follow the close paren to start a new string, + // and not attach to any preceding it. + 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 = 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 = fRXPat->fCompiledPat->elementAti(fMatchOpenParen+1); + U_ASSERT(URX_TYPE(captureOp) == URX_START_CAPTURE); + + int32_t frameVarLocation = URX_VAL(captureOp); + int32_t endCaptureOp = URX_BUILD(URX_END_CAPTURE, frameVarLocation); + fRXPat->fCompiledPat->addElement(endCaptureOp, *fStatus); + } + 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 = fRXPat->fCompiledPat->elementAti(fMatchOpenParen+1); + U_ASSERT(URX_TYPE(stoOp) == URX_STO_SP); + int32_t stoLoc = URX_VAL(stoOp); + int32_t ldOp = URX_BUILD(URX_LD_SP, stoLoc); + fRXPat->fCompiledPat->addElement(ldOp, *fStatus); + } + break; + + case lookAhead: + { + int32_t startOp = fRXPat->fCompiledPat->elementAti(fMatchOpenParen-1); + U_ASSERT(URX_TYPE(startOp) == URX_LA_START); + int32_t dataLoc = URX_VAL(startOp); + int32_t op = URX_BUILD(URX_LA_END, dataLoc); + fRXPat->fCompiledPat->addElement(op, *fStatus); + } + break; + + case negLookAhead: + { + // See comment at doOpenLookAheadNeg + int32_t startOp = fRXPat->fCompiledPat->elementAti(fMatchOpenParen-1); + U_ASSERT(URX_TYPE(startOp) == URX_LA_START); + int32_t dataLoc = URX_VAL(startOp); + int32_t op = URX_BUILD(URX_LA_END, dataLoc); + fRXPat->fCompiledPat->addElement(op, *fStatus); + op = URX_BUILD(URX_FAIL, 0); + fRXPat->fCompiledPat->addElement(op, *fStatus); + + // Patch the URX_SAVE near the top of the block. + int32_t saveOp = fRXPat->fCompiledPat->elementAti(fMatchOpenParen); + U_ASSERT(URX_TYPE(saveOp) == URX_STATE_SAVE); + int32_t dest = fRXPat->fCompiledPat->size(); + saveOp = URX_BUILD(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 = fRXPat->fCompiledPat->elementAti(fMatchOpenParen-4); + U_ASSERT(URX_TYPE(startOp) == URX_LB_START); + int32_t dataLoc = URX_VAL(startOp); + int32_t op = URX_BUILD(URX_LB_END, dataLoc); + fRXPat->fCompiledPat->addElement(op, *fStatus); + op = URX_BUILD(URX_LA_END, dataLoc); + fRXPat->fCompiledPat->addElement(op, *fStatus); + + // 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 (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 = fRXPat->fCompiledPat->elementAti(fMatchOpenParen-5); + U_ASSERT(URX_TYPE(startOp) == URX_LB_START); + int32_t dataLoc = URX_VAL(startOp); + int32_t op = URX_BUILD(URX_LBN_END, dataLoc); + fRXPat->fCompiledPat->addElement(op, *fStatus); + + // 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 (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 + op = URX_BUILD(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; + } + int32_t setSize = theSet->size(); + UChar32 firstSetChar = theSet->charAt(0); + if (firstSetChar == -1) { + // Sets that contain only strings, but no individual chars, + // will end up here. + error(U_REGEX_SET_CONTAINS_STRING); + setSize = 0; + } + + switch (setSize) { + case 0: + { + // Set of no elements. Always fails to match. + fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKTRACK, 0), *fStatus); + 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(firstSetChar); + 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); + int32_t setOp = URX_BUILD(URX_SETREF, setNumber); + fRXPat->fCompiledPat->addElement(setOp, *fStatus); + } + } +} + + +//------------------------------------------------------------------------------ +// +// 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. +// +// 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. + int32_t counterLoc = fRXPat->fFrameSize; + fRXPat->fFrameSize++; + + int32_t op = URX_BUILD(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 = URX_BUILD(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. + op = URX_BUILD(LoopOp, topOfBlock); + fRXPat->fCompiledPat->addElement(op, *fStatus); + + 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. + fRXPat->fCompiledPat->setSize(topOfBlock); + 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 = 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 = URX_BUILD(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) { + fRXPat->fCompiledPat->addElement(saveOp, *fStatus); + } + if (i > fIntervalLow) { + fRXPat->fCompiledPat->addElement(saveOp, *fStatus); + } + fRXPat->fCompiledPat->addElement(op, *fStatus); + } + return TRUE; +} + + + +//------------------------------------------------------------------------------ +// +// 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 = 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); + 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_DOLLAR: + case URX_RELOC_OPRND: + case URX_STO_INP_LOC: + case URX_DOLLAR_M: + case URX_BACKTRACK: + 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: + if (atStart) { + fRXPat->fStartType = START_LINE; + } + break; + + case URX_ONECHAR: + if (currentLen == 0) { + // This character could appear at the start of a match. + // Add it to the set of possible starting characters. + fRXPat->fInitialChars->add(URX_VAL(op)); + numInitialStrings += 2; + } + currentLen++; + atStart = FALSE; + break; + + + case URX_SETREF: + if (currentLen == 0) { + int32_t sn = URX_VAL(op); + U_ASSERT(sn > 0 && sn < fRXPat->fSets->size()); + const UnicodeSet *s = (UnicodeSet *)fRXPat->fSets->elementAt(sn); + fRXPat->fInitialChars->addAll(*s); + numInitialStrings += 2; + } + currentLen++; + atStart = FALSE; + break; + + case URX_LOOP_SR_I: + // [Set]*, like a SETREF, above, in what it can match, + // but may not match at all, so currentLen is not incremented. + if (currentLen == 0) { + int32_t sn = URX_VAL(op); + U_ASSERT(sn > 0 && sn < fRXPat->fSets->size()); + const UnicodeSet *s = (UnicodeSet *)fRXPat->fSets->elementAt(sn); + fRXPat->fInitialChars->addAll(*s); + numInitialStrings += 2; + } + atStart = FALSE; + break; + + case URX_LOOP_DOT_I: + if (currentLen == 0) { + // .* at the start of a pattern. + // Any character can begin the match. + fRXPat->fInitialChars->clear(); + fRXPat->fInitialChars->complement(); + numInitialStrings += 2; + } + atStart = FALSE; + break; + + + case URX_STATIC_SETREF: + if (currentLen == 0) { + int32_t sn = URX_VAL(op); + U_ASSERT(sn>0 && sn<URX_LAST_SET); + const UnicodeSet *s = fRXPat->fStaticSets[sn]; + fRXPat->fInitialChars->addAll(*s); + numInitialStrings += 2; + } + currentLen++; + atStart = FALSE; + break; + + + + case URX_STAT_SETREF_N: + if (currentLen == 0) { + int32_t sn = URX_VAL(op); + const UnicodeSet *s = fRXPat->fStaticSets[sn]; + UnicodeSet sc(*s); + sc.complement(); + fRXPat->fInitialChars->addAll(sc); + numInitialStrings += 2; + } + currentLen++; + atStart = FALSE; + break; + + + + case URX_BACKSLASH_D: + // Digit Char + if (currentLen == 0) { + UnicodeSet s; + s.applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, U_GC_ND_MASK, *fStatus); + if (URX_VAL(op) != 0) { + s.complement(); + } + fRXPat->fInitialChars->addAll(s); + numInitialStrings += 2; + } + currentLen++; + atStart = FALSE; + break; + + + case URX_ONECHAR_I: + // Case Insensitive Single Character. + if (currentLen == 0) { + UChar32 c = URX_VAL(op); + if (u_hasBinaryProperty(c, UCHAR_CASE_SENSITIVE)) { + // character may have distinct cased forms. Add all of them + // to the set of possible starting match chars. + UnicodeSet s(c, c); + s.closeOver(USET_CASE_INSENSITIVE); + fRXPat->fInitialChars->addAll(s); + } else { + // Char has no case variants. Just add it as-is to the + // set of possible starting chars. + fRXPat->fInitialChars->add(c); + } + numInitialStrings += 2; + } + currentLen++; + atStart = FALSE; + break; + + + case URX_BACKSLASH_X: // Grahpeme Cluster. Minimum is 1, max unbounded. + case URX_DOTANY_ALL: // . matches one or two. + case URX_DOTANY: + case URX_DOTANY_ALL_PL: + case URX_DOTANY_PL: + if (currentLen == 0) { + // These constructs are all bad news when they appear at the start + // of a match. Any character can begin the match. + fRXPat->fInitialChars->clear(); + fRXPat->fInitialChars->complement(); + numInitialStrings += 2; + } + currentLen++; + atStart = FALSE; + break; + + + case URX_JMPX: + loc++; // Except for extra operand on URX_JMPX, same as URX_JMP. + case URX_JMP: + { + int32_t jmpDest = URX_VAL(op); + if (jmpDest < loc) { + // Loop of some kind. Can safely ignore, the worst that will happen + // is that we understate the true minimum length + currentLen = forwardedLength.elementAti(loc+1); + + } else { + // Forward jump. Propagate the current min length to the target loc of the jump. + U_ASSERT(jmpDest <= end+1); + if (forwardedLength.elementAti(jmpDest) > currentLen) { + forwardedLength.setElementAt(currentLen, jmpDest); + } + } + } + atStart = FALSE; + break; + + case URX_JMP_SAV: + case URX_JMP_SAV_X: + // Combo of state save to the next loc, + jmp backwards. + // Net effect on min. length computation is nothing. + atStart = FALSE; + break; + + case URX_FAIL: + // 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 = fRXPat->fCompiledPat->elementAti(loc); + int32_t stringLen = URX_VAL(stringLenOp); + U_ASSERT(URX_TYPE(stringLenOp) == URX_STRING_LEN); + U_ASSERT(stringLenOp >= 2); + if (currentLen == 0) { + // Add the starting character of this string to the set of possible starting + // characters for this pattern. + int32_t stringStartIdx = URX_VAL(op); + UChar32 c = fRXPat->fLiteralText.char32At(stringStartIdx); + fRXPat->fInitialChars->add(c); + + // Remember this string. After the entire pattern has been checked, + // if nothing else is identified that can start a match, we'll use it. + numInitialStrings++; + fRXPat->fInitialStringIdx = stringStartIdx; + fRXPat->fInitialStringLen = stringLen; + } + + currentLen += stringLen; + atStart = FALSE; + } + break; + + case URX_STRING_I: + { + // Case-insensitive string. Unlike exact-match strings, we won't + // attempt a string search for possible match positions. But we + // do update the set of possible starting characters. + loc++; + int32_t stringLenOp = 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(c, c); + s.closeOver(USET_CASE_INSENSITIVE); + fRXPat->fInitialChars->addAll(s); + numInitialStrings += 2; // Matching on an initial string not possible. + } + currentLen += stringLen; + atStart = FALSE; + } + break; + + case URX_CTR_INIT: + case URX_CTR_INIT_NG: + { + // Loop Init Ops. These don't change the min length, but they are 4 word ops + // so location must be updated accordingly. + // Loop Init Ops. + // If the min loop count == 0 + // move loc forwards to the end of the loop, skipping over the body. + // If the min count is > 0, + // continue normal processing of the body of the loop. + int32_t loopEndLoc = fRXPat->fCompiledPat->elementAti(loc+1); + loopEndLoc = URX_VAL(loopEndLoc); + int32_t minLoopCount = 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. + int32_t depth = 0; + for (;;) { + loc++; + op = 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--; + } + 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 = 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); + 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_RELOC_OPRND: + case URX_STO_INP_LOC: + case URX_DOLLAR_M: + case URX_CARET_M: + case URX_BACKTRACK: + 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_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_PL: + case URX_DOTANY_ALL_PL: + currentLen++; + break; + + + case URX_JMPX: + loc++; // URX_JMPX has an extra operand, ignored here, + // otherwise processed identically to URX_JMP. + case URX_JMP: + { + int32_t jmpDest = URX_VAL(op); + if (jmpDest < loc) { + // Loop of some kind. Can safely ignore, the worst that will happen + // is that we understate the true minimum length + currentLen = forwardedLength.elementAti(loc+1); + } else { + // Forward jump. Propagate the current min length to the target loc of the jump. + U_ASSERT(jmpDest <= end+1); + if (forwardedLength.elementAti(jmpDest) > currentLen) { + forwardedLength.setElementAt(currentLen, jmpDest); + } + } + } + break; + + case URX_FAIL: + { + // Fails are kind of like a branch, except that the min length was + // propagated already, by the state save. + currentLen = forwardedLength.elementAti(loc+1); + U_ASSERT(currentLen>=0 && currentLen < INT32_MAX); + } + 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: + case URX_STRING_I: + { + loc++; + int32_t stringLenOp = fRXPat->fCompiledPat->elementAti(loc); + currentLen += URX_VAL(stringLenOp); + } + 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 = fRXPat->fCompiledPat->elementAti(loc+1); + loopEndLoc = URX_VAL(loopEndLoc); + int32_t minLoopCount = 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. + // TODO: Positive lookahead could recursively do the block, then continue + // with the longer of the block or the value coming in. + int32_t depth = 0; + for (;;) { + loc++; + op = 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--; + } + 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 = 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_RELOC_OPRND: + case URX_STO_INP_LOC: + case URX_DOLLAR_M: + case URX_CARET_M: + case URX_BACKTRACK: + + 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. + case URX_DOTANY_PL: + case URX_DOTANY_ALL_PL: + 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_ONECHAR_I: + case URX_DOTANY_ALL: + case URX_DOTANY: + 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++; + if (URX_VAL(op) > 0x10000) { + currentLen++; + } + 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_FAIL: + // Fails 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: + case URX_STRING_I: + { + loc++; + int32_t stringLenOp = fRXPat->fCompiledPat->elementAti(loc); + currentLen += URX_VAL(stringLenOp); + } + break; + + + case URX_CTR_INIT: + case URX_CTR_INIT_NG: + case URX_CTR_LOOP: + case URX_CTR_LOOP_NG: + 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. + // Note: INIT instructions are multi-word. Can ignore because + // INT32_MAX length will stop the per-instruction loop. + 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 = 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. +// +//------------------------------------------------------------------------------ +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 = fRXPat->fCompiledPat->elementAti(loc); + if (URX_TYPE(op) == URX_NOP) { + d++; + } + } + + // 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 = 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 = URX_BUILD(opType, fixedOperandAddress); + fRXPat->fCompiledPat->setElementAt(op, dst); + dst++; + 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_DOTANY_ALL_PL: + case URX_DOTANY_PL: + case URX_BACKSLASH_D: + case URX_CARET: + case URX_DOLLAR: + case URX_CTR_INIT: + case URX_CTR_INIT_NG: + case URX_STO_SP: + case URX_LD_SP: + case URX_BACKREF: + case URX_STO_INP_LOC: + case URX_LA_START: + case URX_LA_END: + case URX_ONECHAR_I: + case URX_STRING_I: + case URX_BACKREF_I: + case URX_DOLLAR_M: + case URX_CARET_M: + 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: + // 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); +} + + + + +//------------------------------------------------------------------------------ +// +// OptDotStar Optimize patterns that end with a '.*' or '.+' to +// just advance the input to the end. +// +// Transform this compiled sequence +// [DOT_ANY | DOT_ANY_ALL] +// JMP_SAV to previous instruction +// [NOP | END_CAPTURE | DOLLAR | BACKSLASH_Z]* +// END +// +// To +// NOP +// [DOT_ANY_PL | DOT_ANY_ALL_PL] +// [NOP | END_CAPTURE | DOLLAR | BACKSLASH_Z]* +// END +// +//------------------------------------------------------------------------------ +void RegexCompile::OptDotStar() { + // Scan backwards in the pattern, looking for a JMP_SAV near the end. + int32_t jmpLoc; + int32_t op = 0; + int32_t opType; + for (jmpLoc=fRXPat->fCompiledPat->size(); jmpLoc--;) { + U_ASSERT(jmpLoc>0); + op = fRXPat->fCompiledPat->elementAti(jmpLoc); + opType = URX_TYPE(op); + switch(opType) { + + + case URX_END: + case URX_NOP: + case URX_END_CAPTURE: + case URX_DOLLAR_M: + case URX_DOLLAR: + case URX_BACKSLASH_Z: + // These ops may follow the JMP_SAV without preventing us from + // doing this optimization. + continue; + + case URX_JMP_SAV: + // Got a trailing JMP_SAV that's a candidate for optimization. + break; + + default: + // This optimization not possible. + return; + } + break; // from the for loop. + } + + // We found in URX_JMP_SAV near the end that is a candidate for optimizing. + // Is the target address the previous instruction? + // Is the previous instruction a flavor of URX_DOTANY + int32_t loopTopLoc = URX_VAL(op); + if (loopTopLoc != jmpLoc-1) { + return; + } + int32_t newOp; + int32_t oldOp = fRXPat->fCompiledPat->elementAti(loopTopLoc); + int32_t oldOpType = opType = URX_TYPE(oldOp); + if (oldOpType == URX_DOTANY) { + newOp = URX_BUILD(URX_DOTANY_PL, 0); + } + else if (oldOpType == URX_DOTANY_ALL) { + newOp = URX_BUILD(URX_DOTANY_ALL_PL, 0); + } else { + return; // Sequence we were looking for isn't there. + } + + // Substitute the new instructions into the pattern. + // The NOP will be removed in a later optimization step. + fRXPat->fCompiledPat->setElementAt(URX_BUILD(URX_NOP, 0), loopTopLoc); + fRXPat->fCompiledPat->setElementAt(newOp, jmpLoc); +} + + +//------------------------------------------------------------------------------ +// +// Error Report a rule parse error. +// Only report it if no previous error has been recorded. +// +//------------------------------------------------------------------------------ +void RegexCompile::error(UErrorCode e) { + if (U_SUCCESS(*fStatus)) { + *fStatus = e; + fParseErr->line = fLineNum; + fParseErr->offset = fCharNum; + + // 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)); + fRXPat->fPattern.extractBetween(fScanIndex-U_PARSE_CONTEXT_LEN+1, fScanIndex, + fParseErr->preContext, 0); + fRXPat->fPattern.extractBetween(fScanIndex, fScanIndex+U_PARSE_CONTEXT_LEN-1, + fParseErr->postContext, 0); + } +} + + +// +// 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; +static const UChar chNEL = 0x85; // NEL newline variant +static const UChar chLS = 0x2028; // Unicode Line Separator +static const UChar chPound = 0x23; // '#', introduces a comment. +static const UChar chE = 0x45; // 'E' +static const UChar chUpperN = 0x4E; +static const UChar chLowerP = 0x70; +static const UChar chUpperP = 0x50; +static const UChar chBackSlash = 0x5c; // '\' introduces a char escape +static const UChar chLBracket = 0x5b; +static const UChar chRBracket = 0x5d; +static const UChar chRBrace = 0x7d; + + +//------------------------------------------------------------------------------ +// +// 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; + UnicodeString &pattern = fRXPat->fPattern; + + if (fPeekChar != -1) { + ch = fPeekChar; + fPeekChar = -1; + return ch; + } + if (fPatternLength==0 || fNextIndex >= fPatternLength) { + return (UChar32)-1; + } + ch = pattern.char32At(fNextIndex); + fNextIndex = pattern.moveIndex32(fNextIndex, 1); + + 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; + if (fQuoteMode) { + error(U_REGEX_RULE_SYNTAX); + fQuoteMode = FALSE; + } + } + 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 = fNextIndex; + c.fChar = nextCharLL(); + c.fQuoted = FALSE; + + if (fQuoteMode) { + c.fQuoted = TRUE; + if ((c.fChar==chBackSlash && peekCharLL()==chE) || 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; + } + } + } + if (uprv_isRuleWhiteSpace(c.fChar) == FALSE) { + break; + } + c.fChar = nextCharLL(); + } + } + + // + // check for backslash escaped characters. + // + int32_t startX = fNextIndex; // start and end positions of the + int32_t endX = fNextIndex; // sequence following the '\' + if (c.fChar == chBackSlash) { + 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; + c.fChar = fRXPat->fPattern.unescapeAt(endX); + if (startX == endX) { + error(U_REGEX_BAD_ESCAPE_SEQUENCE); + } + fCharNum += endX - startX; + fNextIndex = endX; + } + 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. TODO: this is awkward, think about alternatives. + 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); +} + + + +//------------------------------------------------------------------------------ +// +// scanSet Construct a UnicodeSet from the text at the current scan +// position. Advance the scan position to the first character +// after the set. +// +// The scan position is normally under the control of the state machine +// that controls pattern parsing. UnicodeSets, however, are parsed by +// the UnicodeSet constructor, not by the Regex pattern parser. +// +//------------------------------------------------------------------------------ +UnicodeSet *RegexCompile::scanSet() { + UnicodeSet *uset = NULL; + ParsePosition pos; + int i; + + if (U_FAILURE(*fStatus)) { + return NULL; + } + + pos.setIndex(fScanIndex); + UErrorCode localStatus = U_ZERO_ERROR; + uint32_t usetFlags = 0; + if (fModeFlags & UREGEX_CASE_INSENSITIVE) { + usetFlags |= USET_CASE_INSENSITIVE; + } + if (fModeFlags & UREGEX_COMMENTS) { + usetFlags |= USET_IGNORE_SPACE; + } + + uset = new UnicodeSet(fRXPat->fPattern, pos, + usetFlags, NULL, localStatus); + if (U_FAILURE(localStatus)) { + // TODO: Get more accurate position of the error from UnicodeSet's return info. + // UnicodeSet appears to not be reporting correctly at this time. + REGEX_SCAN_DEBUG_PRINTF(("UnicodeSet parse postion.ErrorIndex = %d\n", pos.getIndex())); + error(localStatus); + delete uset; + return NULL; + } + + // Advance the current scan postion over the UnicodeSet. + // Don't just set fScanIndex because the line/char positions maintained + // for error reporting would be thrown off. + i = pos.getIndex(); + for (;;) { + if (fNextIndex >= i) { + break; + } + nextCharLL(); + } + + return uset; +} + + +//------------------------------------------------------------------------------ +// +// 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; + } + + U_ASSERT(fC.fChar == chLowerP || fC.fChar == chUpperP || fC.fChar == chUpperN); + + // enclose the \p{property} from the regex pattern source in [brackets] + UnicodeString setPattern; + setPattern.append(chLBracket); + setPattern.append(chBackSlash); + for (;;) { + setPattern.append(fC.fChar); + if (fC.fChar == chRBrace) { + break; + } + nextChar(fC); + if (fC.fChar == -1) { + // Hit the end of the input string without finding the closing '}' + error(U_REGEX_PROPERTY_SYNTAX); + return NULL; + } + } + setPattern.append(chRBracket); + + uint32_t usetFlags = 0; + if (fModeFlags & UREGEX_CASE_INSENSITIVE) { + usetFlags |= USET_CASE_INSENSITIVE; + } + if (fModeFlags & UREGEX_COMMENTS) { + usetFlags |= USET_IGNORE_SPACE; + } + + // Build the UnicodeSet from the set pattern we just built up in a string. + uset = new UnicodeSet(setPattern, usetFlags, NULL, *fStatus); + if (U_FAILURE(*fStatus)) { + delete uset; + uset = NULL; + } + + nextChar(fC); // Continue overall regex pattern processing with char after the '}' + return uset; +} + +U_NAMESPACE_END +#endif // !UCONFIG_NO_REGULAR_EXPRESSIONS + |