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