michael@0: /* michael@0: ************************************************************************** michael@0: * Copyright (C) 2002-2013 International Business Machines Corporation * michael@0: * and others. All rights reserved. * michael@0: ************************************************************************** michael@0: */ michael@0: // michael@0: // file: rematch.cpp michael@0: // michael@0: // Contains the implementation of class RegexMatcher, michael@0: // which is one of the main API classes for the ICU regular expression package. michael@0: // michael@0: michael@0: #include "unicode/utypes.h" michael@0: #if !UCONFIG_NO_REGULAR_EXPRESSIONS michael@0: michael@0: #include "unicode/regex.h" michael@0: #include "unicode/uniset.h" michael@0: #include "unicode/uchar.h" michael@0: #include "unicode/ustring.h" michael@0: #include "unicode/rbbi.h" michael@0: #include "unicode/utf.h" michael@0: #include "unicode/utf16.h" michael@0: #include "uassert.h" michael@0: #include "cmemory.h" michael@0: #include "uvector.h" michael@0: #include "uvectr32.h" michael@0: #include "uvectr64.h" michael@0: #include "regeximp.h" michael@0: #include "regexst.h" michael@0: #include "regextxt.h" michael@0: #include "ucase.h" michael@0: michael@0: // #include // Needed for heapcheck testing michael@0: michael@0: michael@0: // Find progress callback michael@0: // ---------------------- michael@0: // Macro to inline test & call to ReportFindProgress(). Eliminates unnecessary function call. michael@0: // michael@0: #define REGEXFINDPROGRESS_INTERRUPT(pos, status) \ michael@0: (fFindProgressCallbackFn != NULL) && (ReportFindProgress(pos, status) == FALSE) michael@0: michael@0: michael@0: // Smart Backtracking michael@0: // ------------------ michael@0: // When a failure would go back to a LOOP_C instruction, michael@0: // strings, characters, and setrefs scan backwards for a valid start michael@0: // character themselves, pop the stack, and save state, emulating the michael@0: // LOOP_C's effect but assured that the next character of input is a michael@0: // possible matching character. michael@0: // michael@0: // Good idea in theory; unfortunately it only helps out a few specific michael@0: // cases and slows the engine down a little in the rest. michael@0: michael@0: U_NAMESPACE_BEGIN michael@0: michael@0: // Default limit for the size of the back track stack, to avoid system michael@0: // failures causedby heap exhaustion. Units are in 32 bit words, not bytes. michael@0: // This value puts ICU's limits higher than most other regexp implementations, michael@0: // which use recursion rather than the heap, and take more storage per michael@0: // backtrack point. michael@0: // michael@0: static const int32_t DEFAULT_BACKTRACK_STACK_CAPACITY = 8000000; michael@0: michael@0: // Time limit counter constant. michael@0: // Time limits for expression evaluation are in terms of quanta of work by michael@0: // the engine, each of which is 10,000 state saves. michael@0: // This constant determines that state saves per tick number. michael@0: static const int32_t TIMER_INITIAL_VALUE = 10000; michael@0: michael@0: //----------------------------------------------------------------------------- michael@0: // michael@0: // Constructor and Destructor michael@0: // michael@0: //----------------------------------------------------------------------------- michael@0: RegexMatcher::RegexMatcher(const RegexPattern *pat) { michael@0: fDeferredStatus = U_ZERO_ERROR; michael@0: init(fDeferredStatus); michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: return; michael@0: } michael@0: if (pat==NULL) { michael@0: fDeferredStatus = U_ILLEGAL_ARGUMENT_ERROR; michael@0: return; michael@0: } michael@0: fPattern = pat; michael@0: init2(RegexStaticSets::gStaticSets->fEmptyText, fDeferredStatus); michael@0: } michael@0: michael@0: michael@0: michael@0: RegexMatcher::RegexMatcher(const UnicodeString ®exp, const UnicodeString &input, michael@0: uint32_t flags, UErrorCode &status) { michael@0: init(status); michael@0: if (U_FAILURE(status)) { michael@0: return; michael@0: } michael@0: UParseError pe; michael@0: fPatternOwned = RegexPattern::compile(regexp, flags, pe, status); michael@0: fPattern = fPatternOwned; michael@0: michael@0: UText inputText = UTEXT_INITIALIZER; michael@0: utext_openConstUnicodeString(&inputText, &input, &status); michael@0: init2(&inputText, status); michael@0: utext_close(&inputText); michael@0: michael@0: fInputUniStrMaybeMutable = TRUE; michael@0: } michael@0: michael@0: michael@0: RegexMatcher::RegexMatcher(UText *regexp, UText *input, michael@0: uint32_t flags, UErrorCode &status) { michael@0: init(status); michael@0: if (U_FAILURE(status)) { michael@0: return; michael@0: } michael@0: UParseError pe; michael@0: fPatternOwned = RegexPattern::compile(regexp, flags, pe, status); michael@0: if (U_FAILURE(status)) { michael@0: return; michael@0: } michael@0: michael@0: fPattern = fPatternOwned; michael@0: init2(input, status); michael@0: } michael@0: michael@0: michael@0: RegexMatcher::RegexMatcher(const UnicodeString ®exp, michael@0: uint32_t flags, UErrorCode &status) { michael@0: init(status); michael@0: if (U_FAILURE(status)) { michael@0: return; michael@0: } michael@0: UParseError pe; michael@0: fPatternOwned = RegexPattern::compile(regexp, flags, pe, status); michael@0: if (U_FAILURE(status)) { michael@0: return; michael@0: } michael@0: fPattern = fPatternOwned; michael@0: init2(RegexStaticSets::gStaticSets->fEmptyText, status); michael@0: } michael@0: michael@0: RegexMatcher::RegexMatcher(UText *regexp, michael@0: uint32_t flags, UErrorCode &status) { michael@0: init(status); michael@0: if (U_FAILURE(status)) { michael@0: return; michael@0: } michael@0: UParseError pe; michael@0: fPatternOwned = RegexPattern::compile(regexp, flags, pe, status); michael@0: if (U_FAILURE(status)) { michael@0: return; michael@0: } michael@0: michael@0: fPattern = fPatternOwned; michael@0: init2(RegexStaticSets::gStaticSets->fEmptyText, status); michael@0: } michael@0: michael@0: michael@0: michael@0: michael@0: RegexMatcher::~RegexMatcher() { michael@0: delete fStack; michael@0: if (fData != fSmallData) { michael@0: uprv_free(fData); michael@0: fData = NULL; michael@0: } michael@0: if (fPatternOwned) { michael@0: delete fPatternOwned; michael@0: fPatternOwned = NULL; michael@0: fPattern = NULL; michael@0: } michael@0: michael@0: if (fInput) { michael@0: delete fInput; michael@0: } michael@0: if (fInputText) { michael@0: utext_close(fInputText); michael@0: } michael@0: if (fAltInputText) { michael@0: utext_close(fAltInputText); michael@0: } michael@0: michael@0: #if UCONFIG_NO_BREAK_ITERATION==0 michael@0: delete fWordBreakItr; michael@0: #endif michael@0: } michael@0: michael@0: // michael@0: // init() common initialization for use by all constructors. michael@0: // Initialize all fields, get the object into a consistent state. michael@0: // This must be done even when the initial status shows an error, michael@0: // so that the object is initialized sufficiently well for the destructor michael@0: // to run safely. michael@0: // michael@0: void RegexMatcher::init(UErrorCode &status) { michael@0: fPattern = NULL; michael@0: fPatternOwned = NULL; michael@0: fFrameSize = 0; michael@0: fRegionStart = 0; michael@0: fRegionLimit = 0; michael@0: fAnchorStart = 0; michael@0: fAnchorLimit = 0; michael@0: fLookStart = 0; michael@0: fLookLimit = 0; michael@0: fActiveStart = 0; michael@0: fActiveLimit = 0; michael@0: fTransparentBounds = FALSE; michael@0: fAnchoringBounds = TRUE; michael@0: fMatch = FALSE; michael@0: fMatchStart = 0; michael@0: fMatchEnd = 0; michael@0: fLastMatchEnd = -1; michael@0: fAppendPosition = 0; michael@0: fHitEnd = FALSE; michael@0: fRequireEnd = FALSE; michael@0: fStack = NULL; michael@0: fFrame = NULL; michael@0: fTimeLimit = 0; michael@0: fTime = 0; michael@0: fTickCounter = 0; michael@0: fStackLimit = DEFAULT_BACKTRACK_STACK_CAPACITY; michael@0: fCallbackFn = NULL; michael@0: fCallbackContext = NULL; michael@0: fFindProgressCallbackFn = NULL; michael@0: fFindProgressCallbackContext = NULL; michael@0: fTraceDebug = FALSE; michael@0: fDeferredStatus = status; michael@0: fData = fSmallData; michael@0: fWordBreakItr = NULL; michael@0: michael@0: fStack = NULL; michael@0: fInputText = NULL; michael@0: fAltInputText = NULL; michael@0: fInput = NULL; michael@0: fInputLength = 0; michael@0: fInputUniStrMaybeMutable = FALSE; michael@0: michael@0: if (U_FAILURE(status)) { michael@0: fDeferredStatus = status; michael@0: } michael@0: } michael@0: michael@0: // michael@0: // init2() Common initialization for use by RegexMatcher constructors, part 2. michael@0: // This handles the common setup to be done after the Pattern is available. michael@0: // michael@0: void RegexMatcher::init2(UText *input, UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: fDeferredStatus = status; michael@0: return; michael@0: } michael@0: michael@0: if (fPattern->fDataSize > (int32_t)(sizeof(fSmallData)/sizeof(fSmallData[0]))) { michael@0: fData = (int64_t *)uprv_malloc(fPattern->fDataSize * sizeof(int64_t)); michael@0: if (fData == NULL) { michael@0: status = fDeferredStatus = U_MEMORY_ALLOCATION_ERROR; michael@0: return; michael@0: } michael@0: } michael@0: michael@0: fStack = new UVector64(status); michael@0: if (fStack == NULL) { michael@0: status = fDeferredStatus = U_MEMORY_ALLOCATION_ERROR; michael@0: return; michael@0: } michael@0: michael@0: reset(input); michael@0: setStackLimit(DEFAULT_BACKTRACK_STACK_CAPACITY, status); michael@0: if (U_FAILURE(status)) { michael@0: fDeferredStatus = status; michael@0: return; michael@0: } michael@0: } michael@0: michael@0: michael@0: static const UChar BACKSLASH = 0x5c; michael@0: static const UChar DOLLARSIGN = 0x24; michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // appendReplacement michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: RegexMatcher &RegexMatcher::appendReplacement(UnicodeString &dest, michael@0: const UnicodeString &replacement, michael@0: UErrorCode &status) { michael@0: UText replacementText = UTEXT_INITIALIZER; michael@0: michael@0: utext_openConstUnicodeString(&replacementText, &replacement, &status); michael@0: if (U_SUCCESS(status)) { michael@0: UText resultText = UTEXT_INITIALIZER; michael@0: utext_openUnicodeString(&resultText, &dest, &status); michael@0: michael@0: if (U_SUCCESS(status)) { michael@0: appendReplacement(&resultText, &replacementText, status); michael@0: utext_close(&resultText); michael@0: } michael@0: utext_close(&replacementText); michael@0: } michael@0: michael@0: return *this; michael@0: } michael@0: michael@0: // michael@0: // appendReplacement, UText mode michael@0: // michael@0: RegexMatcher &RegexMatcher::appendReplacement(UText *dest, michael@0: UText *replacement, michael@0: UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: return *this; michael@0: } michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: status = fDeferredStatus; michael@0: return *this; michael@0: } michael@0: if (fMatch == FALSE) { michael@0: status = U_REGEX_INVALID_STATE; michael@0: return *this; michael@0: } michael@0: michael@0: // Copy input string from the end of previous match to start of current match michael@0: int64_t destLen = utext_nativeLength(dest); michael@0: if (fMatchStart > fAppendPosition) { michael@0: if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) { michael@0: destLen += utext_replace(dest, destLen, destLen, fInputText->chunkContents+fAppendPosition, michael@0: (int32_t)(fMatchStart-fAppendPosition), &status); michael@0: } else { michael@0: int32_t len16; michael@0: if (UTEXT_USES_U16(fInputText)) { michael@0: len16 = (int32_t)(fMatchStart-fAppendPosition); michael@0: } else { michael@0: UErrorCode lengthStatus = U_ZERO_ERROR; michael@0: len16 = utext_extract(fInputText, fAppendPosition, fMatchStart, NULL, 0, &lengthStatus); michael@0: } michael@0: UChar *inputChars = (UChar *)uprv_malloc(sizeof(UChar)*(len16+1)); michael@0: if (inputChars == NULL) { michael@0: status = U_MEMORY_ALLOCATION_ERROR; michael@0: return *this; michael@0: } michael@0: utext_extract(fInputText, fAppendPosition, fMatchStart, inputChars, len16+1, &status); michael@0: destLen += utext_replace(dest, destLen, destLen, inputChars, len16, &status); michael@0: uprv_free(inputChars); michael@0: } michael@0: } michael@0: fAppendPosition = fMatchEnd; michael@0: michael@0: michael@0: // scan the replacement text, looking for substitutions ($n) and \escapes. michael@0: // TODO: optimize this loop by efficiently scanning for '$' or '\', michael@0: // move entire ranges not containing substitutions. michael@0: UTEXT_SETNATIVEINDEX(replacement, 0); michael@0: UChar32 c = UTEXT_NEXT32(replacement); michael@0: while (c != U_SENTINEL) { michael@0: if (c == BACKSLASH) { michael@0: // Backslash Escape. Copy the following char out without further checks. michael@0: // Note: Surrogate pairs don't need any special handling michael@0: // The second half wont be a '$' or a '\', and michael@0: // will move to the dest normally on the next michael@0: // loop iteration. michael@0: c = UTEXT_CURRENT32(replacement); michael@0: if (c == U_SENTINEL) { michael@0: break; michael@0: } michael@0: michael@0: if (c==0x55/*U*/ || c==0x75/*u*/) { michael@0: // We have a \udddd or \Udddddddd escape sequence. michael@0: int32_t offset = 0; michael@0: struct URegexUTextUnescapeCharContext context = U_REGEX_UTEXT_UNESCAPE_CONTEXT(replacement); michael@0: UChar32 escapedChar = u_unescapeAt(uregex_utext_unescape_charAt, &offset, INT32_MAX, &context); michael@0: if (escapedChar != (UChar32)0xFFFFFFFF) { michael@0: if (U_IS_BMP(escapedChar)) { michael@0: UChar c16 = (UChar)escapedChar; michael@0: destLen += utext_replace(dest, destLen, destLen, &c16, 1, &status); michael@0: } else { michael@0: UChar surrogate[2]; michael@0: surrogate[0] = U16_LEAD(escapedChar); michael@0: surrogate[1] = U16_TRAIL(escapedChar); michael@0: if (U_SUCCESS(status)) { michael@0: destLen += utext_replace(dest, destLen, destLen, surrogate, 2, &status); michael@0: } michael@0: } michael@0: // TODO: Report errors for mal-formed \u escapes? michael@0: // As this is, the original sequence is output, which may be OK. michael@0: if (context.lastOffset == offset) { michael@0: (void)UTEXT_PREVIOUS32(replacement); michael@0: } else if (context.lastOffset != offset-1) { michael@0: utext_moveIndex32(replacement, offset - context.lastOffset - 1); michael@0: } michael@0: } michael@0: } else { michael@0: (void)UTEXT_NEXT32(replacement); michael@0: // Plain backslash escape. Just put out the escaped character. michael@0: if (U_IS_BMP(c)) { michael@0: UChar c16 = (UChar)c; michael@0: destLen += utext_replace(dest, destLen, destLen, &c16, 1, &status); michael@0: } else { michael@0: UChar surrogate[2]; michael@0: surrogate[0] = U16_LEAD(c); michael@0: surrogate[1] = U16_TRAIL(c); michael@0: if (U_SUCCESS(status)) { michael@0: destLen += utext_replace(dest, destLen, destLen, surrogate, 2, &status); michael@0: } michael@0: } michael@0: } michael@0: } else if (c != DOLLARSIGN) { michael@0: // Normal char, not a $. Copy it out without further checks. michael@0: if (U_IS_BMP(c)) { michael@0: UChar c16 = (UChar)c; michael@0: destLen += utext_replace(dest, destLen, destLen, &c16, 1, &status); michael@0: } else { michael@0: UChar surrogate[2]; michael@0: surrogate[0] = U16_LEAD(c); michael@0: surrogate[1] = U16_TRAIL(c); michael@0: if (U_SUCCESS(status)) { michael@0: destLen += utext_replace(dest, destLen, destLen, surrogate, 2, &status); michael@0: } michael@0: } michael@0: } else { michael@0: // We've got a $. Pick up a capture group number if one follows. michael@0: // Consume at most the number of digits necessary for the largest capture michael@0: // number that is valid for this pattern. michael@0: michael@0: int32_t numDigits = 0; michael@0: int32_t groupNum = 0; michael@0: UChar32 digitC; michael@0: for (;;) { michael@0: digitC = UTEXT_CURRENT32(replacement); michael@0: if (digitC == U_SENTINEL) { michael@0: break; michael@0: } michael@0: if (u_isdigit(digitC) == FALSE) { michael@0: break; michael@0: } michael@0: (void)UTEXT_NEXT32(replacement); michael@0: groupNum=groupNum*10 + u_charDigitValue(digitC); michael@0: numDigits++; michael@0: if (numDigits >= fPattern->fMaxCaptureDigits) { michael@0: break; michael@0: } michael@0: } michael@0: michael@0: michael@0: if (numDigits == 0) { michael@0: // The $ didn't introduce a group number at all. michael@0: // Treat it as just part of the substitution text. michael@0: UChar c16 = DOLLARSIGN; michael@0: destLen += utext_replace(dest, destLen, destLen, &c16, 1, &status); michael@0: } else { michael@0: // Finally, append the capture group data to the destination. michael@0: destLen += appendGroup(groupNum, dest, status); michael@0: if (U_FAILURE(status)) { michael@0: // Can fail if group number is out of range. michael@0: break; michael@0: } michael@0: } michael@0: } michael@0: michael@0: if (U_FAILURE(status)) { michael@0: break; michael@0: } else { michael@0: c = UTEXT_NEXT32(replacement); michael@0: } michael@0: } michael@0: michael@0: return *this; michael@0: } michael@0: michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // appendTail Intended to be used in conjunction with appendReplacement() michael@0: // To the destination string, append everything following michael@0: // the last match position from the input string. michael@0: // michael@0: // Note: Match ranges do not affect appendTail or appendReplacement michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: UnicodeString &RegexMatcher::appendTail(UnicodeString &dest) { michael@0: UErrorCode status = U_ZERO_ERROR; michael@0: UText resultText = UTEXT_INITIALIZER; michael@0: utext_openUnicodeString(&resultText, &dest, &status); michael@0: michael@0: if (U_SUCCESS(status)) { michael@0: appendTail(&resultText, status); michael@0: utext_close(&resultText); michael@0: } michael@0: michael@0: return dest; michael@0: } michael@0: michael@0: // michael@0: // appendTail, UText mode michael@0: // michael@0: UText *RegexMatcher::appendTail(UText *dest, UErrorCode &status) { michael@0: UBool bailOut = FALSE; michael@0: if (U_FAILURE(status)) { michael@0: bailOut = TRUE; michael@0: } michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: status = fDeferredStatus; michael@0: bailOut = TRUE; michael@0: } michael@0: michael@0: if (bailOut) { michael@0: // dest must not be NULL michael@0: if (dest) { michael@0: utext_replace(dest, utext_nativeLength(dest), utext_nativeLength(dest), NULL, 0, &status); michael@0: return dest; michael@0: } michael@0: } michael@0: michael@0: if (fInputLength > fAppendPosition) { michael@0: if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) { michael@0: int64_t destLen = utext_nativeLength(dest); michael@0: utext_replace(dest, destLen, destLen, fInputText->chunkContents+fAppendPosition, michael@0: (int32_t)(fInputLength-fAppendPosition), &status); michael@0: } else { michael@0: int32_t len16; michael@0: if (UTEXT_USES_U16(fInputText)) { michael@0: len16 = (int32_t)(fInputLength-fAppendPosition); michael@0: } else { michael@0: len16 = utext_extract(fInputText, fAppendPosition, fInputLength, NULL, 0, &status); michael@0: status = U_ZERO_ERROR; // buffer overflow michael@0: } michael@0: michael@0: UChar *inputChars = (UChar *)uprv_malloc(sizeof(UChar)*(len16)); michael@0: if (inputChars == NULL) { michael@0: fDeferredStatus = U_MEMORY_ALLOCATION_ERROR; michael@0: } else { michael@0: utext_extract(fInputText, fAppendPosition, fInputLength, inputChars, len16, &status); // unterminated michael@0: int64_t destLen = utext_nativeLength(dest); michael@0: utext_replace(dest, destLen, destLen, inputChars, len16, &status); michael@0: uprv_free(inputChars); michael@0: } michael@0: } michael@0: } michael@0: return dest; michael@0: } michael@0: michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // end michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: int32_t RegexMatcher::end(UErrorCode &err) const { michael@0: return end(0, err); michael@0: } michael@0: michael@0: int64_t RegexMatcher::end64(UErrorCode &err) const { michael@0: return end64(0, err); michael@0: } michael@0: michael@0: int64_t RegexMatcher::end64(int32_t group, UErrorCode &err) const { michael@0: if (U_FAILURE(err)) { michael@0: return -1; michael@0: } michael@0: if (fMatch == FALSE) { michael@0: err = U_REGEX_INVALID_STATE; michael@0: return -1; michael@0: } michael@0: if (group < 0 || group > fPattern->fGroupMap->size()) { michael@0: err = U_INDEX_OUTOFBOUNDS_ERROR; michael@0: return -1; michael@0: } michael@0: int64_t e = -1; michael@0: if (group == 0) { michael@0: e = fMatchEnd; michael@0: } else { michael@0: // Get the position within the stack frame of the variables for michael@0: // this capture group. michael@0: int32_t groupOffset = fPattern->fGroupMap->elementAti(group-1); michael@0: U_ASSERT(groupOffset < fPattern->fFrameSize); michael@0: U_ASSERT(groupOffset >= 0); michael@0: e = fFrame->fExtra[groupOffset + 1]; michael@0: } michael@0: michael@0: return e; michael@0: } michael@0: michael@0: int32_t RegexMatcher::end(int32_t group, UErrorCode &err) const { michael@0: return (int32_t)end64(group, err); michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // find() michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: UBool RegexMatcher::find() { michael@0: // Start at the position of the last match end. (Will be zero if the michael@0: // matcher has been reset.) michael@0: // michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: return FALSE; michael@0: } michael@0: michael@0: if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) { michael@0: return findUsingChunk(); michael@0: } michael@0: michael@0: int64_t startPos = fMatchEnd; michael@0: if (startPos==0) { michael@0: startPos = fActiveStart; michael@0: } michael@0: michael@0: if (fMatch) { michael@0: // Save the position of any previous successful match. michael@0: fLastMatchEnd = fMatchEnd; michael@0: michael@0: if (fMatchStart == fMatchEnd) { michael@0: // Previous match had zero length. Move start position up one position michael@0: // to avoid sending find() into a loop on zero-length matches. michael@0: if (startPos >= fActiveLimit) { michael@0: fMatch = FALSE; michael@0: fHitEnd = TRUE; michael@0: return FALSE; michael@0: } michael@0: UTEXT_SETNATIVEINDEX(fInputText, startPos); michael@0: (void)UTEXT_NEXT32(fInputText); michael@0: startPos = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } michael@0: } else { michael@0: if (fLastMatchEnd >= 0) { michael@0: // A previous find() failed to match. Don't try again. michael@0: // (without this test, a pattern with a zero-length match michael@0: // could match again at the end of an input string.) michael@0: fHitEnd = TRUE; michael@0: return FALSE; michael@0: } michael@0: } michael@0: michael@0: michael@0: // Compute the position in the input string beyond which a match can not begin, because michael@0: // the minimum length match would extend past the end of the input. michael@0: // Note: some patterns that cannot match anything will have fMinMatchLength==Max Int. michael@0: // Be aware of possible overflows if making changes here. michael@0: int64_t testStartLimit; michael@0: if (UTEXT_USES_U16(fInputText)) { michael@0: testStartLimit = fActiveLimit - fPattern->fMinMatchLen; michael@0: if (startPos > testStartLimit) { michael@0: fMatch = FALSE; michael@0: fHitEnd = TRUE; michael@0: return FALSE; michael@0: } michael@0: } else { michael@0: // For now, let the matcher discover that it can't match on its own michael@0: // We don't know how long the match len is in native characters michael@0: testStartLimit = fActiveLimit; michael@0: } michael@0: michael@0: UChar32 c; michael@0: U_ASSERT(startPos >= 0); michael@0: michael@0: switch (fPattern->fStartType) { michael@0: case START_NO_INFO: michael@0: // No optimization was found. michael@0: // Try a match at each input position. michael@0: for (;;) { michael@0: MatchAt(startPos, FALSE, fDeferredStatus); michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: return FALSE; michael@0: } michael@0: if (fMatch) { michael@0: return TRUE; michael@0: } michael@0: if (startPos >= testStartLimit) { michael@0: fHitEnd = TRUE; michael@0: return FALSE; michael@0: } michael@0: UTEXT_SETNATIVEINDEX(fInputText, startPos); michael@0: (void)UTEXT_NEXT32(fInputText); michael@0: startPos = UTEXT_GETNATIVEINDEX(fInputText); michael@0: // Note that it's perfectly OK for a pattern to have a zero-length michael@0: // match at the end of a string, so we must make sure that the loop michael@0: // runs with startPos == testStartLimit the last time through. michael@0: if (REGEXFINDPROGRESS_INTERRUPT(startPos, fDeferredStatus)) michael@0: return FALSE; michael@0: } michael@0: U_ASSERT(FALSE); michael@0: michael@0: case START_START: michael@0: // Matches are only possible at the start of the input string michael@0: // (pattern begins with ^ or \A) michael@0: if (startPos > fActiveStart) { michael@0: fMatch = FALSE; michael@0: return FALSE; michael@0: } michael@0: MatchAt(startPos, FALSE, fDeferredStatus); michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: return FALSE; michael@0: } michael@0: return fMatch; michael@0: michael@0: michael@0: case START_SET: michael@0: { michael@0: // Match may start on any char from a pre-computed set. michael@0: U_ASSERT(fPattern->fMinMatchLen > 0); michael@0: int64_t pos; michael@0: UTEXT_SETNATIVEINDEX(fInputText, startPos); michael@0: for (;;) { michael@0: c = UTEXT_NEXT32(fInputText); michael@0: pos = UTEXT_GETNATIVEINDEX(fInputText); michael@0: // c will be -1 (U_SENTINEL) at end of text, in which case we michael@0: // skip this next block (so we don't have a negative array index) michael@0: // and handle end of text in the following block. michael@0: if (c >= 0 && ((c<256 && fPattern->fInitialChars8->contains(c)) || michael@0: (c>=256 && fPattern->fInitialChars->contains(c)))) { michael@0: MatchAt(startPos, FALSE, fDeferredStatus); michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: return FALSE; michael@0: } michael@0: if (fMatch) { michael@0: return TRUE; michael@0: } michael@0: UTEXT_SETNATIVEINDEX(fInputText, pos); michael@0: } michael@0: if (startPos >= testStartLimit) { michael@0: fMatch = FALSE; michael@0: fHitEnd = TRUE; michael@0: return FALSE; michael@0: } michael@0: startPos = pos; michael@0: if (REGEXFINDPROGRESS_INTERRUPT(startPos, fDeferredStatus)) michael@0: return FALSE; michael@0: } michael@0: } michael@0: U_ASSERT(FALSE); michael@0: michael@0: case START_STRING: michael@0: case START_CHAR: michael@0: { michael@0: // Match starts on exactly one char. michael@0: U_ASSERT(fPattern->fMinMatchLen > 0); michael@0: UChar32 theChar = fPattern->fInitialChar; michael@0: int64_t pos; michael@0: UTEXT_SETNATIVEINDEX(fInputText, startPos); michael@0: for (;;) { michael@0: c = UTEXT_NEXT32(fInputText); michael@0: pos = UTEXT_GETNATIVEINDEX(fInputText); michael@0: if (c == theChar) { michael@0: MatchAt(startPos, FALSE, fDeferredStatus); michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: return FALSE; michael@0: } michael@0: if (fMatch) { michael@0: return TRUE; michael@0: } michael@0: UTEXT_SETNATIVEINDEX(fInputText, pos); michael@0: } michael@0: if (startPos >= testStartLimit) { michael@0: fMatch = FALSE; michael@0: fHitEnd = TRUE; michael@0: return FALSE; michael@0: } michael@0: startPos = pos; michael@0: if (REGEXFINDPROGRESS_INTERRUPT(startPos, fDeferredStatus)) michael@0: return FALSE; michael@0: } michael@0: } michael@0: U_ASSERT(FALSE); michael@0: michael@0: case START_LINE: michael@0: { michael@0: UChar32 c; michael@0: if (startPos == fAnchorStart) { michael@0: MatchAt(startPos, FALSE, fDeferredStatus); michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: return FALSE; michael@0: } michael@0: if (fMatch) { michael@0: return TRUE; michael@0: } michael@0: UTEXT_SETNATIVEINDEX(fInputText, startPos); michael@0: c = UTEXT_NEXT32(fInputText); michael@0: startPos = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } else { michael@0: UTEXT_SETNATIVEINDEX(fInputText, startPos); michael@0: c = UTEXT_PREVIOUS32(fInputText); michael@0: UTEXT_SETNATIVEINDEX(fInputText, startPos); michael@0: } michael@0: michael@0: if (fPattern->fFlags & UREGEX_UNIX_LINES) { michael@0: for (;;) { michael@0: if (c == 0x0a) { michael@0: MatchAt(startPos, FALSE, fDeferredStatus); michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: return FALSE; michael@0: } michael@0: if (fMatch) { michael@0: return TRUE; michael@0: } michael@0: UTEXT_SETNATIVEINDEX(fInputText, startPos); michael@0: } michael@0: if (startPos >= testStartLimit) { michael@0: fMatch = FALSE; michael@0: fHitEnd = TRUE; michael@0: return FALSE; michael@0: } michael@0: c = UTEXT_NEXT32(fInputText); michael@0: startPos = UTEXT_GETNATIVEINDEX(fInputText); michael@0: // Note that it's perfectly OK for a pattern to have a zero-length michael@0: // match at the end of a string, so we must make sure that the loop michael@0: // runs with startPos == testStartLimit the last time through. michael@0: if (REGEXFINDPROGRESS_INTERRUPT(startPos, fDeferredStatus)) michael@0: return FALSE; michael@0: } michael@0: } else { michael@0: for (;;) { michael@0: if (((c & 0x7f) <= 0x29) && // First quickly bypass as many chars as possible michael@0: ((c<=0x0d && c>=0x0a) || c==0x85 ||c==0x2028 || c==0x2029 )) { michael@0: if (c == 0x0d && startPos < fActiveLimit && UTEXT_CURRENT32(fInputText) == 0x0a) { michael@0: (void)UTEXT_NEXT32(fInputText); michael@0: startPos = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } michael@0: MatchAt(startPos, FALSE, fDeferredStatus); michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: return FALSE; michael@0: } michael@0: if (fMatch) { michael@0: return TRUE; michael@0: } michael@0: UTEXT_SETNATIVEINDEX(fInputText, startPos); michael@0: } michael@0: if (startPos >= testStartLimit) { michael@0: fMatch = FALSE; michael@0: fHitEnd = TRUE; michael@0: return FALSE; michael@0: } michael@0: c = UTEXT_NEXT32(fInputText); michael@0: startPos = UTEXT_GETNATIVEINDEX(fInputText); michael@0: // Note that it's perfectly OK for a pattern to have a zero-length michael@0: // match at the end of a string, so we must make sure that the loop michael@0: // runs with startPos == testStartLimit the last time through. michael@0: if (REGEXFINDPROGRESS_INTERRUPT(startPos, fDeferredStatus)) michael@0: return FALSE; michael@0: } michael@0: } michael@0: } michael@0: michael@0: default: michael@0: U_ASSERT(FALSE); michael@0: } michael@0: michael@0: U_ASSERT(FALSE); michael@0: return FALSE; michael@0: } michael@0: michael@0: michael@0: michael@0: UBool RegexMatcher::find(int64_t start, UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: return FALSE; michael@0: } michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: status = fDeferredStatus; michael@0: return FALSE; michael@0: } michael@0: this->reset(); // Note: Reset() is specified by Java Matcher documentation. michael@0: // This will reset the region to be the full input length. michael@0: if (start < 0) { michael@0: status = U_INDEX_OUTOFBOUNDS_ERROR; michael@0: return FALSE; michael@0: } michael@0: michael@0: int64_t nativeStart = start; michael@0: if (nativeStart < fActiveStart || nativeStart > fActiveLimit) { michael@0: status = U_INDEX_OUTOFBOUNDS_ERROR; michael@0: return FALSE; michael@0: } michael@0: fMatchEnd = nativeStart; michael@0: return find(); michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // findUsingChunk() -- like find(), but with the advance knowledge that the michael@0: // entire string is available in the UText's chunk buffer. michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: UBool RegexMatcher::findUsingChunk() { michael@0: // Start at the position of the last match end. (Will be zero if the michael@0: // matcher has been reset. michael@0: // michael@0: michael@0: int32_t startPos = (int32_t)fMatchEnd; michael@0: if (startPos==0) { michael@0: startPos = (int32_t)fActiveStart; michael@0: } michael@0: michael@0: const UChar *inputBuf = fInputText->chunkContents; michael@0: michael@0: if (fMatch) { michael@0: // Save the position of any previous successful match. michael@0: fLastMatchEnd = fMatchEnd; michael@0: michael@0: if (fMatchStart == fMatchEnd) { michael@0: // Previous match had zero length. Move start position up one position michael@0: // to avoid sending find() into a loop on zero-length matches. michael@0: if (startPos >= fActiveLimit) { michael@0: fMatch = FALSE; michael@0: fHitEnd = TRUE; michael@0: return FALSE; michael@0: } michael@0: U16_FWD_1(inputBuf, startPos, fInputLength); michael@0: } michael@0: } else { michael@0: if (fLastMatchEnd >= 0) { michael@0: // A previous find() failed to match. Don't try again. michael@0: // (without this test, a pattern with a zero-length match michael@0: // could match again at the end of an input string.) michael@0: fHitEnd = TRUE; michael@0: return FALSE; michael@0: } michael@0: } michael@0: michael@0: michael@0: // Compute the position in the input string beyond which a match can not begin, because michael@0: // the minimum length match would extend past the end of the input. michael@0: // Note: some patterns that cannot match anything will have fMinMatchLength==Max Int. michael@0: // Be aware of possible overflows if making changes here. michael@0: int32_t testLen = (int32_t)(fActiveLimit - fPattern->fMinMatchLen); michael@0: if (startPos > testLen) { michael@0: fMatch = FALSE; michael@0: fHitEnd = TRUE; michael@0: return FALSE; michael@0: } michael@0: michael@0: UChar32 c; michael@0: U_ASSERT(startPos >= 0); michael@0: michael@0: switch (fPattern->fStartType) { michael@0: case START_NO_INFO: michael@0: // No optimization was found. michael@0: // Try a match at each input position. michael@0: for (;;) { michael@0: MatchChunkAt(startPos, FALSE, fDeferredStatus); michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: return FALSE; michael@0: } michael@0: if (fMatch) { michael@0: return TRUE; michael@0: } michael@0: if (startPos >= testLen) { michael@0: fHitEnd = TRUE; michael@0: return FALSE; michael@0: } michael@0: U16_FWD_1(inputBuf, startPos, fActiveLimit); michael@0: // Note that it's perfectly OK for a pattern to have a zero-length michael@0: // match at the end of a string, so we must make sure that the loop michael@0: // runs with startPos == testLen the last time through. michael@0: if (REGEXFINDPROGRESS_INTERRUPT(startPos, fDeferredStatus)) michael@0: return FALSE; michael@0: } michael@0: U_ASSERT(FALSE); michael@0: michael@0: case START_START: michael@0: // Matches are only possible at the start of the input string michael@0: // (pattern begins with ^ or \A) michael@0: if (startPos > fActiveStart) { michael@0: fMatch = FALSE; michael@0: return FALSE; michael@0: } michael@0: MatchChunkAt(startPos, FALSE, fDeferredStatus); michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: return FALSE; michael@0: } michael@0: return fMatch; michael@0: michael@0: michael@0: case START_SET: michael@0: { michael@0: // Match may start on any char from a pre-computed set. michael@0: U_ASSERT(fPattern->fMinMatchLen > 0); michael@0: for (;;) { michael@0: int32_t pos = startPos; michael@0: U16_NEXT(inputBuf, startPos, fActiveLimit, c); // like c = inputBuf[startPos++]; michael@0: if ((c<256 && fPattern->fInitialChars8->contains(c)) || michael@0: (c>=256 && fPattern->fInitialChars->contains(c))) { michael@0: MatchChunkAt(pos, FALSE, fDeferredStatus); michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: return FALSE; michael@0: } michael@0: if (fMatch) { michael@0: return TRUE; michael@0: } michael@0: } michael@0: if (pos >= testLen) { michael@0: fMatch = FALSE; michael@0: fHitEnd = TRUE; michael@0: return FALSE; michael@0: } michael@0: if (REGEXFINDPROGRESS_INTERRUPT(startPos, fDeferredStatus)) michael@0: return FALSE; michael@0: } michael@0: } michael@0: U_ASSERT(FALSE); michael@0: michael@0: case START_STRING: michael@0: case START_CHAR: michael@0: { michael@0: // Match starts on exactly one char. michael@0: U_ASSERT(fPattern->fMinMatchLen > 0); michael@0: UChar32 theChar = fPattern->fInitialChar; michael@0: for (;;) { michael@0: int32_t pos = startPos; michael@0: U16_NEXT(inputBuf, startPos, fActiveLimit, c); // like c = inputBuf[startPos++]; michael@0: if (c == theChar) { michael@0: MatchChunkAt(pos, FALSE, fDeferredStatus); michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: return FALSE; michael@0: } michael@0: if (fMatch) { michael@0: return TRUE; michael@0: } michael@0: } michael@0: if (pos >= testLen) { michael@0: fMatch = FALSE; michael@0: fHitEnd = TRUE; michael@0: return FALSE; michael@0: } michael@0: if (REGEXFINDPROGRESS_INTERRUPT(startPos, fDeferredStatus)) michael@0: return FALSE; michael@0: } michael@0: } michael@0: U_ASSERT(FALSE); michael@0: michael@0: case START_LINE: michael@0: { michael@0: UChar32 c; michael@0: if (startPos == fAnchorStart) { michael@0: MatchChunkAt(startPos, FALSE, fDeferredStatus); michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: return FALSE; michael@0: } michael@0: if (fMatch) { michael@0: return TRUE; michael@0: } michael@0: U16_FWD_1(inputBuf, startPos, fActiveLimit); michael@0: } michael@0: michael@0: if (fPattern->fFlags & UREGEX_UNIX_LINES) { michael@0: for (;;) { michael@0: c = inputBuf[startPos-1]; michael@0: if (c == 0x0a) { michael@0: MatchChunkAt(startPos, FALSE, fDeferredStatus); michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: return FALSE; michael@0: } michael@0: if (fMatch) { michael@0: return TRUE; michael@0: } michael@0: } michael@0: if (startPos >= testLen) { michael@0: fMatch = FALSE; michael@0: fHitEnd = TRUE; michael@0: return FALSE; michael@0: } michael@0: U16_FWD_1(inputBuf, startPos, fActiveLimit); michael@0: // Note that it's perfectly OK for a pattern to have a zero-length michael@0: // match at the end of a string, so we must make sure that the loop michael@0: // runs with startPos == testLen the last time through. michael@0: if (REGEXFINDPROGRESS_INTERRUPT(startPos, fDeferredStatus)) michael@0: return FALSE; michael@0: } michael@0: } else { michael@0: for (;;) { michael@0: c = inputBuf[startPos-1]; michael@0: if (((c & 0x7f) <= 0x29) && // First quickly bypass as many chars as possible michael@0: ((c<=0x0d && c>=0x0a) || c==0x85 ||c==0x2028 || c==0x2029 )) { michael@0: if (c == 0x0d && startPos < fActiveLimit && inputBuf[startPos] == 0x0a) { michael@0: startPos++; michael@0: } michael@0: MatchChunkAt(startPos, FALSE, fDeferredStatus); michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: return FALSE; michael@0: } michael@0: if (fMatch) { michael@0: return TRUE; michael@0: } michael@0: } michael@0: if (startPos >= testLen) { michael@0: fMatch = FALSE; michael@0: fHitEnd = TRUE; michael@0: return FALSE; michael@0: } michael@0: U16_FWD_1(inputBuf, startPos, fActiveLimit); michael@0: // Note that it's perfectly OK for a pattern to have a zero-length michael@0: // match at the end of a string, so we must make sure that the loop michael@0: // runs with startPos == testLen the last time through. michael@0: if (REGEXFINDPROGRESS_INTERRUPT(startPos, fDeferredStatus)) michael@0: return FALSE; michael@0: } michael@0: } michael@0: } michael@0: michael@0: default: michael@0: U_ASSERT(FALSE); michael@0: } michael@0: michael@0: U_ASSERT(FALSE); michael@0: return FALSE; michael@0: } michael@0: michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // group() michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: UnicodeString RegexMatcher::group(UErrorCode &status) const { michael@0: return group(0, status); michael@0: } michael@0: michael@0: // Return immutable shallow clone michael@0: UText *RegexMatcher::group(UText *dest, int64_t &group_len, UErrorCode &status) const { michael@0: return group(0, dest, group_len, status); michael@0: } michael@0: michael@0: // Return immutable shallow clone michael@0: UText *RegexMatcher::group(int32_t groupNum, UText *dest, int64_t &group_len, UErrorCode &status) const { michael@0: group_len = 0; michael@0: UBool bailOut = FALSE; michael@0: if (U_FAILURE(status)) { michael@0: return dest; michael@0: } michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: status = fDeferredStatus; michael@0: bailOut = TRUE; michael@0: } michael@0: if (fMatch == FALSE) { michael@0: status = U_REGEX_INVALID_STATE; michael@0: bailOut = TRUE; michael@0: } michael@0: if (groupNum < 0 || groupNum > fPattern->fGroupMap->size()) { michael@0: status = U_INDEX_OUTOFBOUNDS_ERROR; michael@0: bailOut = TRUE; michael@0: } michael@0: michael@0: if (bailOut) { michael@0: return (dest) ? dest : utext_openUChars(NULL, NULL, 0, &status); michael@0: } michael@0: michael@0: int64_t s, e; michael@0: if (groupNum == 0) { michael@0: s = fMatchStart; michael@0: e = fMatchEnd; michael@0: } else { michael@0: int32_t groupOffset = fPattern->fGroupMap->elementAti(groupNum-1); michael@0: U_ASSERT(groupOffset < fPattern->fFrameSize); michael@0: U_ASSERT(groupOffset >= 0); michael@0: s = fFrame->fExtra[groupOffset]; michael@0: e = fFrame->fExtra[groupOffset+1]; michael@0: } michael@0: michael@0: if (s < 0) { michael@0: // A capture group wasn't part of the match michael@0: return utext_clone(dest, fInputText, FALSE, TRUE, &status); michael@0: } michael@0: U_ASSERT(s <= e); michael@0: group_len = e - s; michael@0: michael@0: dest = utext_clone(dest, fInputText, FALSE, TRUE, &status); michael@0: if (dest) michael@0: UTEXT_SETNATIVEINDEX(dest, s); michael@0: return dest; michael@0: } michael@0: michael@0: UnicodeString RegexMatcher::group(int32_t groupNum, UErrorCode &status) const { michael@0: UnicodeString result; michael@0: if (U_FAILURE(status)) { michael@0: return result; michael@0: } michael@0: UText resultText = UTEXT_INITIALIZER; michael@0: utext_openUnicodeString(&resultText, &result, &status); michael@0: group(groupNum, &resultText, status); michael@0: utext_close(&resultText); michael@0: return result; michael@0: } michael@0: michael@0: michael@0: // Return deep (mutable) clone michael@0: // Technology Preview (as an API), but note that the UnicodeString API is implemented michael@0: // using this function. michael@0: UText *RegexMatcher::group(int32_t groupNum, UText *dest, UErrorCode &status) const { michael@0: UBool bailOut = FALSE; michael@0: if (U_FAILURE(status)) { michael@0: return dest; michael@0: } michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: status = fDeferredStatus; michael@0: bailOut = TRUE; michael@0: } michael@0: michael@0: if (fMatch == FALSE) { michael@0: status = U_REGEX_INVALID_STATE; michael@0: bailOut = TRUE; michael@0: } michael@0: if (groupNum < 0 || groupNum > fPattern->fGroupMap->size()) { michael@0: status = U_INDEX_OUTOFBOUNDS_ERROR; michael@0: bailOut = TRUE; michael@0: } michael@0: michael@0: if (bailOut) { michael@0: if (dest) { michael@0: utext_replace(dest, 0, utext_nativeLength(dest), NULL, 0, &status); michael@0: return dest; michael@0: } else { michael@0: return utext_openUChars(NULL, NULL, 0, &status); michael@0: } michael@0: } michael@0: michael@0: int64_t s, e; michael@0: if (groupNum == 0) { michael@0: s = fMatchStart; michael@0: e = fMatchEnd; michael@0: } else { michael@0: int32_t groupOffset = fPattern->fGroupMap->elementAti(groupNum-1); michael@0: U_ASSERT(groupOffset < fPattern->fFrameSize); michael@0: U_ASSERT(groupOffset >= 0); michael@0: s = fFrame->fExtra[groupOffset]; michael@0: e = fFrame->fExtra[groupOffset+1]; michael@0: } michael@0: michael@0: if (s < 0) { michael@0: // A capture group wasn't part of the match michael@0: if (dest) { michael@0: utext_replace(dest, 0, utext_nativeLength(dest), NULL, 0, &status); michael@0: return dest; michael@0: } else { michael@0: return utext_openUChars(NULL, NULL, 0, &status); michael@0: } michael@0: } michael@0: U_ASSERT(s <= e); michael@0: michael@0: if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) { michael@0: U_ASSERT(e <= fInputLength); michael@0: if (dest) { michael@0: utext_replace(dest, 0, utext_nativeLength(dest), fInputText->chunkContents+s, (int32_t)(e-s), &status); michael@0: } else { michael@0: UText groupText = UTEXT_INITIALIZER; michael@0: utext_openUChars(&groupText, fInputText->chunkContents+s, e-s, &status); michael@0: dest = utext_clone(NULL, &groupText, TRUE, FALSE, &status); michael@0: utext_close(&groupText); michael@0: } michael@0: } else { michael@0: int32_t len16; michael@0: if (UTEXT_USES_U16(fInputText)) { michael@0: len16 = (int32_t)(e-s); michael@0: } else { michael@0: UErrorCode lengthStatus = U_ZERO_ERROR; michael@0: len16 = utext_extract(fInputText, s, e, NULL, 0, &lengthStatus); michael@0: } michael@0: UChar *groupChars = (UChar *)uprv_malloc(sizeof(UChar)*(len16+1)); michael@0: if (groupChars == NULL) { michael@0: status = U_MEMORY_ALLOCATION_ERROR; michael@0: return dest; michael@0: } michael@0: utext_extract(fInputText, s, e, groupChars, len16+1, &status); michael@0: michael@0: if (dest) { michael@0: utext_replace(dest, 0, utext_nativeLength(dest), groupChars, len16, &status); michael@0: } else { michael@0: UText groupText = UTEXT_INITIALIZER; michael@0: utext_openUChars(&groupText, groupChars, len16, &status); michael@0: dest = utext_clone(NULL, &groupText, TRUE, FALSE, &status); michael@0: utext_close(&groupText); michael@0: } michael@0: michael@0: uprv_free(groupChars); michael@0: } michael@0: return dest; michael@0: } michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // appendGroup() -- currently internal only, appends a group to a UText rather michael@0: // than replacing its contents michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: michael@0: int64_t RegexMatcher::appendGroup(int32_t groupNum, UText *dest, UErrorCode &status) const { michael@0: if (U_FAILURE(status)) { michael@0: return 0; michael@0: } michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: status = fDeferredStatus; michael@0: return 0; michael@0: } michael@0: int64_t destLen = utext_nativeLength(dest); michael@0: michael@0: if (fMatch == FALSE) { michael@0: status = U_REGEX_INVALID_STATE; michael@0: return utext_replace(dest, destLen, destLen, NULL, 0, &status); michael@0: } michael@0: if (groupNum < 0 || groupNum > fPattern->fGroupMap->size()) { michael@0: status = U_INDEX_OUTOFBOUNDS_ERROR; michael@0: return utext_replace(dest, destLen, destLen, NULL, 0, &status); michael@0: } michael@0: michael@0: int64_t s, e; michael@0: if (groupNum == 0) { michael@0: s = fMatchStart; michael@0: e = fMatchEnd; michael@0: } else { michael@0: int32_t groupOffset = fPattern->fGroupMap->elementAti(groupNum-1); michael@0: U_ASSERT(groupOffset < fPattern->fFrameSize); michael@0: U_ASSERT(groupOffset >= 0); michael@0: s = fFrame->fExtra[groupOffset]; michael@0: e = fFrame->fExtra[groupOffset+1]; michael@0: } michael@0: michael@0: if (s < 0) { michael@0: // A capture group wasn't part of the match michael@0: return utext_replace(dest, destLen, destLen, NULL, 0, &status); michael@0: } michael@0: U_ASSERT(s <= e); michael@0: michael@0: int64_t deltaLen; michael@0: if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) { michael@0: U_ASSERT(e <= fInputLength); michael@0: deltaLen = utext_replace(dest, destLen, destLen, fInputText->chunkContents+s, (int32_t)(e-s), &status); michael@0: } else { michael@0: int32_t len16; michael@0: if (UTEXT_USES_U16(fInputText)) { michael@0: len16 = (int32_t)(e-s); michael@0: } else { michael@0: UErrorCode lengthStatus = U_ZERO_ERROR; michael@0: len16 = utext_extract(fInputText, s, e, NULL, 0, &lengthStatus); michael@0: } michael@0: UChar *groupChars = (UChar *)uprv_malloc(sizeof(UChar)*(len16+1)); michael@0: if (groupChars == NULL) { michael@0: status = U_MEMORY_ALLOCATION_ERROR; michael@0: return 0; michael@0: } michael@0: utext_extract(fInputText, s, e, groupChars, len16+1, &status); michael@0: michael@0: deltaLen = utext_replace(dest, destLen, destLen, groupChars, len16, &status); michael@0: uprv_free(groupChars); michael@0: } michael@0: return deltaLen; michael@0: } michael@0: michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // groupCount() michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: int32_t RegexMatcher::groupCount() const { michael@0: return fPattern->fGroupMap->size(); michael@0: } michael@0: michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // hasAnchoringBounds() michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: UBool RegexMatcher::hasAnchoringBounds() const { michael@0: return fAnchoringBounds; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // hasTransparentBounds() michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: UBool RegexMatcher::hasTransparentBounds() const { michael@0: return fTransparentBounds; michael@0: } michael@0: michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // hitEnd() michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: UBool RegexMatcher::hitEnd() const { michael@0: return fHitEnd; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // input() michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: const UnicodeString &RegexMatcher::input() const { michael@0: if (!fInput) { michael@0: UErrorCode status = U_ZERO_ERROR; michael@0: int32_t len16; michael@0: if (UTEXT_USES_U16(fInputText)) { michael@0: len16 = (int32_t)fInputLength; michael@0: } else { michael@0: len16 = utext_extract(fInputText, 0, fInputLength, NULL, 0, &status); michael@0: status = U_ZERO_ERROR; // overflow, length status michael@0: } michael@0: UnicodeString *result = new UnicodeString(len16, 0, 0); michael@0: michael@0: UChar *inputChars = result->getBuffer(len16); michael@0: utext_extract(fInputText, 0, fInputLength, inputChars, len16, &status); // unterminated warning michael@0: result->releaseBuffer(len16); michael@0: michael@0: (*(const UnicodeString **)&fInput) = result; // pointer assignment, rather than operator= michael@0: } michael@0: michael@0: return *fInput; michael@0: } michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // inputText() michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: UText *RegexMatcher::inputText() const { michael@0: return fInputText; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // getInput() -- like inputText(), but makes a clone or copies into another UText michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: UText *RegexMatcher::getInput (UText *dest, UErrorCode &status) const { michael@0: UBool bailOut = FALSE; michael@0: if (U_FAILURE(status)) { michael@0: return dest; michael@0: } michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: status = fDeferredStatus; michael@0: bailOut = TRUE; michael@0: } michael@0: michael@0: if (bailOut) { michael@0: if (dest) { michael@0: utext_replace(dest, 0, utext_nativeLength(dest), NULL, 0, &status); michael@0: return dest; michael@0: } else { michael@0: return utext_clone(NULL, fInputText, FALSE, TRUE, &status); michael@0: } michael@0: } michael@0: michael@0: if (dest) { michael@0: if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) { michael@0: utext_replace(dest, 0, utext_nativeLength(dest), fInputText->chunkContents, (int32_t)fInputLength, &status); michael@0: } else { michael@0: int32_t input16Len; michael@0: if (UTEXT_USES_U16(fInputText)) { michael@0: input16Len = (int32_t)fInputLength; michael@0: } else { michael@0: UErrorCode lengthStatus = U_ZERO_ERROR; michael@0: input16Len = utext_extract(fInputText, 0, fInputLength, NULL, 0, &lengthStatus); // buffer overflow error michael@0: } michael@0: UChar *inputChars = (UChar *)uprv_malloc(sizeof(UChar)*(input16Len)); michael@0: if (inputChars == NULL) { michael@0: return dest; michael@0: } michael@0: michael@0: status = U_ZERO_ERROR; michael@0: utext_extract(fInputText, 0, fInputLength, inputChars, input16Len, &status); // not terminated warning michael@0: status = U_ZERO_ERROR; michael@0: utext_replace(dest, 0, utext_nativeLength(dest), inputChars, input16Len, &status); michael@0: michael@0: uprv_free(inputChars); michael@0: } michael@0: return dest; michael@0: } else { michael@0: return utext_clone(NULL, fInputText, FALSE, TRUE, &status); michael@0: } michael@0: } michael@0: michael@0: michael@0: static UBool compat_SyncMutableUTextContents(UText *ut); michael@0: static UBool compat_SyncMutableUTextContents(UText *ut) { michael@0: UBool retVal = FALSE; michael@0: michael@0: // In the following test, we're really only interested in whether the UText should switch michael@0: // between heap and stack allocation. If length hasn't changed, we won't, so the chunkContents michael@0: // will still point to the correct data. michael@0: if (utext_nativeLength(ut) != ut->nativeIndexingLimit) { michael@0: UnicodeString *us=(UnicodeString *)ut->context; michael@0: michael@0: // Update to the latest length. michael@0: // For example, (utext_nativeLength(ut) != ut->nativeIndexingLimit). michael@0: int32_t newLength = us->length(); michael@0: michael@0: // Update the chunk description. michael@0: // The buffer may have switched between stack- and heap-based. michael@0: ut->chunkContents = us->getBuffer(); michael@0: ut->chunkLength = newLength; michael@0: ut->chunkNativeLimit = newLength; michael@0: ut->nativeIndexingLimit = newLength; michael@0: retVal = TRUE; michael@0: } michael@0: michael@0: return retVal; michael@0: } michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // lookingAt() michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: UBool RegexMatcher::lookingAt(UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: return FALSE; michael@0: } michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: status = fDeferredStatus; michael@0: return FALSE; michael@0: } michael@0: michael@0: if (fInputUniStrMaybeMutable) { michael@0: if (compat_SyncMutableUTextContents(fInputText)) { michael@0: fInputLength = utext_nativeLength(fInputText); michael@0: reset(); michael@0: } michael@0: } michael@0: else { michael@0: resetPreserveRegion(); michael@0: } michael@0: if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) { michael@0: MatchChunkAt((int32_t)fActiveStart, FALSE, status); michael@0: } else { michael@0: MatchAt(fActiveStart, FALSE, status); michael@0: } michael@0: return fMatch; michael@0: } michael@0: michael@0: michael@0: UBool RegexMatcher::lookingAt(int64_t start, UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: return FALSE; michael@0: } michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: status = fDeferredStatus; michael@0: return FALSE; michael@0: } michael@0: reset(); michael@0: michael@0: if (start < 0) { michael@0: status = U_INDEX_OUTOFBOUNDS_ERROR; michael@0: return FALSE; michael@0: } michael@0: michael@0: if (fInputUniStrMaybeMutable) { michael@0: if (compat_SyncMutableUTextContents(fInputText)) { michael@0: fInputLength = utext_nativeLength(fInputText); michael@0: reset(); michael@0: } michael@0: } michael@0: michael@0: int64_t nativeStart; michael@0: nativeStart = start; michael@0: if (nativeStart < fActiveStart || nativeStart > fActiveLimit) { michael@0: status = U_INDEX_OUTOFBOUNDS_ERROR; michael@0: return FALSE; michael@0: } michael@0: michael@0: if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) { michael@0: MatchChunkAt((int32_t)nativeStart, FALSE, status); michael@0: } else { michael@0: MatchAt(nativeStart, FALSE, status); michael@0: } michael@0: return fMatch; michael@0: } michael@0: michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // matches() michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: UBool RegexMatcher::matches(UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: return FALSE; michael@0: } michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: status = fDeferredStatus; michael@0: return FALSE; michael@0: } michael@0: michael@0: if (fInputUniStrMaybeMutable) { michael@0: if (compat_SyncMutableUTextContents(fInputText)) { michael@0: fInputLength = utext_nativeLength(fInputText); michael@0: reset(); michael@0: } michael@0: } michael@0: else { michael@0: resetPreserveRegion(); michael@0: } michael@0: michael@0: if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) { michael@0: MatchChunkAt((int32_t)fActiveStart, TRUE, status); michael@0: } else { michael@0: MatchAt(fActiveStart, TRUE, status); michael@0: } michael@0: return fMatch; michael@0: } michael@0: michael@0: michael@0: UBool RegexMatcher::matches(int64_t start, UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: return FALSE; michael@0: } michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: status = fDeferredStatus; michael@0: return FALSE; michael@0: } michael@0: reset(); michael@0: michael@0: if (start < 0) { michael@0: status = U_INDEX_OUTOFBOUNDS_ERROR; michael@0: return FALSE; michael@0: } michael@0: michael@0: if (fInputUniStrMaybeMutable) { michael@0: if (compat_SyncMutableUTextContents(fInputText)) { michael@0: fInputLength = utext_nativeLength(fInputText); michael@0: reset(); michael@0: } michael@0: } michael@0: michael@0: int64_t nativeStart; michael@0: nativeStart = start; michael@0: if (nativeStart < fActiveStart || nativeStart > fActiveLimit) { michael@0: status = U_INDEX_OUTOFBOUNDS_ERROR; michael@0: return FALSE; michael@0: } michael@0: michael@0: if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) { michael@0: MatchChunkAt((int32_t)nativeStart, TRUE, status); michael@0: } else { michael@0: MatchAt(nativeStart, TRUE, status); michael@0: } michael@0: return fMatch; michael@0: } michael@0: michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // pattern michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: const RegexPattern &RegexMatcher::pattern() const { michael@0: return *fPattern; michael@0: } michael@0: michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // region michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: RegexMatcher &RegexMatcher::region(int64_t regionStart, int64_t regionLimit, int64_t startIndex, UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: return *this; michael@0: } michael@0: michael@0: if (regionStart>regionLimit || regionStart<0 || regionLimit<0) { michael@0: status = U_ILLEGAL_ARGUMENT_ERROR; michael@0: } michael@0: michael@0: int64_t nativeStart = regionStart; michael@0: int64_t nativeLimit = regionLimit; michael@0: if (nativeStart > fInputLength || nativeLimit > fInputLength) { michael@0: status = U_ILLEGAL_ARGUMENT_ERROR; michael@0: } michael@0: michael@0: if (startIndex == -1) michael@0: this->reset(); michael@0: else michael@0: resetPreserveRegion(); michael@0: michael@0: fRegionStart = nativeStart; michael@0: fRegionLimit = nativeLimit; michael@0: fActiveStart = nativeStart; michael@0: fActiveLimit = nativeLimit; michael@0: michael@0: if (startIndex != -1) { michael@0: if (startIndex < fActiveStart || startIndex > fActiveLimit) { michael@0: status = U_INDEX_OUTOFBOUNDS_ERROR; michael@0: } michael@0: fMatchEnd = startIndex; michael@0: } michael@0: michael@0: if (!fTransparentBounds) { michael@0: fLookStart = nativeStart; michael@0: fLookLimit = nativeLimit; michael@0: } michael@0: if (fAnchoringBounds) { michael@0: fAnchorStart = nativeStart; michael@0: fAnchorLimit = nativeLimit; michael@0: } michael@0: return *this; michael@0: } michael@0: michael@0: RegexMatcher &RegexMatcher::region(int64_t start, int64_t limit, UErrorCode &status) { michael@0: return region(start, limit, -1, status); michael@0: } michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // regionEnd michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: int32_t RegexMatcher::regionEnd() const { michael@0: return (int32_t)fRegionLimit; michael@0: } michael@0: michael@0: int64_t RegexMatcher::regionEnd64() const { michael@0: return fRegionLimit; michael@0: } michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // regionStart michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: int32_t RegexMatcher::regionStart() const { michael@0: return (int32_t)fRegionStart; michael@0: } michael@0: michael@0: int64_t RegexMatcher::regionStart64() const { michael@0: return fRegionStart; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // replaceAll michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: UnicodeString RegexMatcher::replaceAll(const UnicodeString &replacement, UErrorCode &status) { michael@0: UText replacementText = UTEXT_INITIALIZER; michael@0: UText resultText = UTEXT_INITIALIZER; michael@0: UnicodeString resultString; michael@0: if (U_FAILURE(status)) { michael@0: return resultString; michael@0: } michael@0: michael@0: utext_openConstUnicodeString(&replacementText, &replacement, &status); michael@0: utext_openUnicodeString(&resultText, &resultString, &status); michael@0: michael@0: replaceAll(&replacementText, &resultText, status); michael@0: michael@0: utext_close(&resultText); michael@0: utext_close(&replacementText); michael@0: michael@0: return resultString; michael@0: } michael@0: michael@0: michael@0: // michael@0: // replaceAll, UText mode michael@0: // michael@0: UText *RegexMatcher::replaceAll(UText *replacement, UText *dest, UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: return dest; michael@0: } michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: status = fDeferredStatus; michael@0: return dest; michael@0: } michael@0: michael@0: if (dest == NULL) { michael@0: UnicodeString emptyString; michael@0: UText empty = UTEXT_INITIALIZER; michael@0: michael@0: utext_openUnicodeString(&empty, &emptyString, &status); michael@0: dest = utext_clone(NULL, &empty, TRUE, FALSE, &status); michael@0: utext_close(&empty); michael@0: } michael@0: michael@0: if (U_SUCCESS(status)) { michael@0: reset(); michael@0: while (find()) { michael@0: appendReplacement(dest, replacement, status); michael@0: if (U_FAILURE(status)) { michael@0: break; michael@0: } michael@0: } michael@0: appendTail(dest, status); michael@0: } michael@0: michael@0: return dest; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // replaceFirst michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: UnicodeString RegexMatcher::replaceFirst(const UnicodeString &replacement, UErrorCode &status) { michael@0: UText replacementText = UTEXT_INITIALIZER; michael@0: UText resultText = UTEXT_INITIALIZER; michael@0: UnicodeString resultString; michael@0: michael@0: utext_openConstUnicodeString(&replacementText, &replacement, &status); michael@0: utext_openUnicodeString(&resultText, &resultString, &status); michael@0: michael@0: replaceFirst(&replacementText, &resultText, status); michael@0: michael@0: utext_close(&resultText); michael@0: utext_close(&replacementText); michael@0: michael@0: return resultString; michael@0: } michael@0: michael@0: // michael@0: // replaceFirst, UText mode michael@0: // michael@0: UText *RegexMatcher::replaceFirst(UText *replacement, UText *dest, UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: return dest; michael@0: } michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: status = fDeferredStatus; michael@0: return dest; michael@0: } michael@0: michael@0: reset(); michael@0: if (!find()) { michael@0: return getInput(dest, status); michael@0: } michael@0: michael@0: if (dest == NULL) { michael@0: UnicodeString emptyString; michael@0: UText empty = UTEXT_INITIALIZER; michael@0: michael@0: utext_openUnicodeString(&empty, &emptyString, &status); michael@0: dest = utext_clone(NULL, &empty, TRUE, FALSE, &status); michael@0: utext_close(&empty); michael@0: } michael@0: michael@0: appendReplacement(dest, replacement, status); michael@0: appendTail(dest, status); michael@0: michael@0: return dest; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // requireEnd michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: UBool RegexMatcher::requireEnd() const { michael@0: return fRequireEnd; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // reset michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: RegexMatcher &RegexMatcher::reset() { michael@0: fRegionStart = 0; michael@0: fRegionLimit = fInputLength; michael@0: fActiveStart = 0; michael@0: fActiveLimit = fInputLength; michael@0: fAnchorStart = 0; michael@0: fAnchorLimit = fInputLength; michael@0: fLookStart = 0; michael@0: fLookLimit = fInputLength; michael@0: resetPreserveRegion(); michael@0: return *this; michael@0: } michael@0: michael@0: michael@0: michael@0: void RegexMatcher::resetPreserveRegion() { michael@0: fMatchStart = 0; michael@0: fMatchEnd = 0; michael@0: fLastMatchEnd = -1; michael@0: fAppendPosition = 0; michael@0: fMatch = FALSE; michael@0: fHitEnd = FALSE; michael@0: fRequireEnd = FALSE; michael@0: fTime = 0; michael@0: fTickCounter = TIMER_INITIAL_VALUE; michael@0: //resetStack(); // more expensive than it looks... michael@0: } michael@0: michael@0: michael@0: RegexMatcher &RegexMatcher::reset(const UnicodeString &input) { michael@0: fInputText = utext_openConstUnicodeString(fInputText, &input, &fDeferredStatus); michael@0: if (fPattern->fNeedsAltInput) { michael@0: fAltInputText = utext_clone(fAltInputText, fInputText, FALSE, TRUE, &fDeferredStatus); michael@0: } michael@0: fInputLength = utext_nativeLength(fInputText); michael@0: michael@0: reset(); michael@0: delete fInput; michael@0: fInput = NULL; michael@0: michael@0: // Do the following for any UnicodeString. michael@0: // This is for compatibility for those clients who modify the input string "live" during regex operations. michael@0: fInputUniStrMaybeMutable = TRUE; michael@0: michael@0: if (fWordBreakItr != NULL) { michael@0: #if UCONFIG_NO_BREAK_ITERATION==0 michael@0: UErrorCode status = U_ZERO_ERROR; michael@0: fWordBreakItr->setText(fInputText, status); michael@0: #endif michael@0: } michael@0: return *this; michael@0: } michael@0: michael@0: michael@0: RegexMatcher &RegexMatcher::reset(UText *input) { michael@0: if (fInputText != input) { michael@0: fInputText = utext_clone(fInputText, input, FALSE, TRUE, &fDeferredStatus); michael@0: if (fPattern->fNeedsAltInput) fAltInputText = utext_clone(fAltInputText, fInputText, FALSE, TRUE, &fDeferredStatus); michael@0: fInputLength = utext_nativeLength(fInputText); michael@0: michael@0: delete fInput; michael@0: fInput = NULL; michael@0: michael@0: if (fWordBreakItr != NULL) { michael@0: #if UCONFIG_NO_BREAK_ITERATION==0 michael@0: UErrorCode status = U_ZERO_ERROR; michael@0: fWordBreakItr->setText(input, status); michael@0: #endif michael@0: } michael@0: } michael@0: reset(); michael@0: fInputUniStrMaybeMutable = FALSE; michael@0: michael@0: return *this; michael@0: } michael@0: michael@0: /*RegexMatcher &RegexMatcher::reset(const UChar *) { michael@0: fDeferredStatus = U_INTERNAL_PROGRAM_ERROR; michael@0: return *this; michael@0: }*/ michael@0: michael@0: RegexMatcher &RegexMatcher::reset(int64_t position, UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: return *this; michael@0: } michael@0: reset(); // Reset also resets the region to be the entire string. michael@0: michael@0: if (position < 0 || position > fActiveLimit) { michael@0: status = U_INDEX_OUTOFBOUNDS_ERROR; michael@0: return *this; michael@0: } michael@0: fMatchEnd = position; michael@0: return *this; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // refresh michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: RegexMatcher &RegexMatcher::refreshInputText(UText *input, UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: return *this; michael@0: } michael@0: if (input == NULL) { michael@0: status = U_ILLEGAL_ARGUMENT_ERROR; michael@0: return *this; michael@0: } michael@0: if (utext_nativeLength(fInputText) != utext_nativeLength(input)) { michael@0: status = U_ILLEGAL_ARGUMENT_ERROR; michael@0: return *this; michael@0: } michael@0: int64_t pos = utext_getNativeIndex(fInputText); michael@0: // Shallow read-only clone of the new UText into the existing input UText michael@0: fInputText = utext_clone(fInputText, input, FALSE, TRUE, &status); michael@0: if (U_FAILURE(status)) { michael@0: return *this; michael@0: } michael@0: utext_setNativeIndex(fInputText, pos); michael@0: michael@0: if (fAltInputText != NULL) { michael@0: pos = utext_getNativeIndex(fAltInputText); michael@0: fAltInputText = utext_clone(fAltInputText, input, FALSE, TRUE, &status); michael@0: if (U_FAILURE(status)) { michael@0: return *this; michael@0: } michael@0: utext_setNativeIndex(fAltInputText, pos); michael@0: } michael@0: return *this; michael@0: } michael@0: michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // setTrace michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: void RegexMatcher::setTrace(UBool state) { michael@0: fTraceDebug = state; michael@0: } michael@0: michael@0: michael@0: michael@0: //--------------------------------------------------------------------- michael@0: // michael@0: // split michael@0: // michael@0: //--------------------------------------------------------------------- michael@0: int32_t RegexMatcher::split(const UnicodeString &input, michael@0: UnicodeString dest[], michael@0: int32_t destCapacity, michael@0: UErrorCode &status) michael@0: { michael@0: UText inputText = UTEXT_INITIALIZER; michael@0: utext_openConstUnicodeString(&inputText, &input, &status); michael@0: if (U_FAILURE(status)) { michael@0: return 0; michael@0: } michael@0: michael@0: UText **destText = (UText **)uprv_malloc(sizeof(UText*)*destCapacity); michael@0: if (destText == NULL) { michael@0: status = U_MEMORY_ALLOCATION_ERROR; michael@0: return 0; michael@0: } michael@0: int32_t i; michael@0: for (i = 0; i < destCapacity; i++) { michael@0: destText[i] = utext_openUnicodeString(NULL, &dest[i], &status); michael@0: } michael@0: michael@0: int32_t fieldCount = split(&inputText, destText, destCapacity, status); michael@0: michael@0: for (i = 0; i < destCapacity; i++) { michael@0: utext_close(destText[i]); michael@0: } michael@0: michael@0: uprv_free(destText); michael@0: utext_close(&inputText); michael@0: return fieldCount; michael@0: } michael@0: michael@0: // michael@0: // split, UText mode michael@0: // michael@0: int32_t RegexMatcher::split(UText *input, michael@0: UText *dest[], michael@0: int32_t destCapacity, michael@0: UErrorCode &status) michael@0: { michael@0: // michael@0: // Check arguements for validity michael@0: // michael@0: if (U_FAILURE(status)) { michael@0: return 0; michael@0: }; michael@0: michael@0: if (destCapacity < 1) { michael@0: status = U_ILLEGAL_ARGUMENT_ERROR; michael@0: return 0; michael@0: } michael@0: michael@0: // michael@0: // Reset for the input text michael@0: // michael@0: reset(input); michael@0: int64_t nextOutputStringStart = 0; michael@0: if (fActiveLimit == 0) { michael@0: return 0; michael@0: } michael@0: michael@0: // michael@0: // Loop through the input text, searching for the delimiter pattern michael@0: // michael@0: int32_t i; michael@0: int32_t numCaptureGroups = fPattern->fGroupMap->size(); michael@0: for (i=0; ; i++) { michael@0: if (i>=destCapacity-1) { michael@0: // There is one or zero output string left. michael@0: // Fill the last output string with whatever is left from the input, then exit the loop. michael@0: // ( i will be == destCapacity if we filled the output array while processing michael@0: // capture groups of the delimiter expression, in which case we will discard the michael@0: // last capture group saved in favor of the unprocessed remainder of the michael@0: // input string.) michael@0: i = destCapacity-1; michael@0: if (fActiveLimit > nextOutputStringStart) { michael@0: if (UTEXT_FULL_TEXT_IN_CHUNK(input, fInputLength)) { michael@0: if (dest[i]) { michael@0: utext_replace(dest[i], 0, utext_nativeLength(dest[i]), michael@0: input->chunkContents+nextOutputStringStart, michael@0: (int32_t)(fActiveLimit-nextOutputStringStart), &status); michael@0: } else { michael@0: UText remainingText = UTEXT_INITIALIZER; michael@0: utext_openUChars(&remainingText, input->chunkContents+nextOutputStringStart, michael@0: fActiveLimit-nextOutputStringStart, &status); michael@0: dest[i] = utext_clone(NULL, &remainingText, TRUE, FALSE, &status); michael@0: utext_close(&remainingText); michael@0: } michael@0: } else { michael@0: UErrorCode lengthStatus = U_ZERO_ERROR; michael@0: int32_t remaining16Length = michael@0: utext_extract(input, nextOutputStringStart, fActiveLimit, NULL, 0, &lengthStatus); michael@0: UChar *remainingChars = (UChar *)uprv_malloc(sizeof(UChar)*(remaining16Length+1)); michael@0: if (remainingChars == NULL) { michael@0: status = U_MEMORY_ALLOCATION_ERROR; michael@0: break; michael@0: } michael@0: michael@0: utext_extract(input, nextOutputStringStart, fActiveLimit, remainingChars, remaining16Length+1, &status); michael@0: if (dest[i]) { michael@0: utext_replace(dest[i], 0, utext_nativeLength(dest[i]), remainingChars, remaining16Length, &status); michael@0: } else { michael@0: UText remainingText = UTEXT_INITIALIZER; michael@0: utext_openUChars(&remainingText, remainingChars, remaining16Length, &status); michael@0: dest[i] = utext_clone(NULL, &remainingText, TRUE, FALSE, &status); michael@0: utext_close(&remainingText); michael@0: } michael@0: michael@0: uprv_free(remainingChars); michael@0: } michael@0: } michael@0: break; michael@0: } michael@0: if (find()) { michael@0: // We found another delimiter. Move everything from where we started looking michael@0: // up until the start of the delimiter into the next output string. michael@0: if (UTEXT_FULL_TEXT_IN_CHUNK(input, fInputLength)) { michael@0: if (dest[i]) { michael@0: utext_replace(dest[i], 0, utext_nativeLength(dest[i]), michael@0: input->chunkContents+nextOutputStringStart, michael@0: (int32_t)(fMatchStart-nextOutputStringStart), &status); michael@0: } else { michael@0: UText remainingText = UTEXT_INITIALIZER; michael@0: utext_openUChars(&remainingText, input->chunkContents+nextOutputStringStart, michael@0: fMatchStart-nextOutputStringStart, &status); michael@0: dest[i] = utext_clone(NULL, &remainingText, TRUE, FALSE, &status); michael@0: utext_close(&remainingText); michael@0: } michael@0: } else { michael@0: UErrorCode lengthStatus = U_ZERO_ERROR; michael@0: int32_t remaining16Length = utext_extract(input, nextOutputStringStart, fMatchStart, NULL, 0, &lengthStatus); michael@0: UChar *remainingChars = (UChar *)uprv_malloc(sizeof(UChar)*(remaining16Length+1)); michael@0: if (remainingChars == NULL) { michael@0: status = U_MEMORY_ALLOCATION_ERROR; michael@0: break; michael@0: } michael@0: utext_extract(input, nextOutputStringStart, fMatchStart, remainingChars, remaining16Length+1, &status); michael@0: if (dest[i]) { michael@0: utext_replace(dest[i], 0, utext_nativeLength(dest[i]), remainingChars, remaining16Length, &status); michael@0: } else { michael@0: UText remainingText = UTEXT_INITIALIZER; michael@0: utext_openUChars(&remainingText, remainingChars, remaining16Length, &status); michael@0: dest[i] = utext_clone(NULL, &remainingText, TRUE, FALSE, &status); michael@0: utext_close(&remainingText); michael@0: } michael@0: michael@0: uprv_free(remainingChars); michael@0: } michael@0: nextOutputStringStart = fMatchEnd; michael@0: michael@0: // If the delimiter pattern has capturing parentheses, the captured michael@0: // text goes out into the next n destination strings. michael@0: int32_t groupNum; michael@0: for (groupNum=1; groupNum<=numCaptureGroups; groupNum++) { michael@0: if (i >= destCapacity-2) { michael@0: // Never fill the last available output string with capture group text. michael@0: // It will filled with the last field, the remainder of the michael@0: // unsplit input text. michael@0: break; michael@0: } michael@0: i++; michael@0: dest[i] = group(groupNum, dest[i], status); michael@0: } michael@0: michael@0: if (nextOutputStringStart == fActiveLimit) { michael@0: // The delimiter was at the end of the string. We're done, but first michael@0: // we output one last empty string, for the empty field following michael@0: // the delimiter at the end of input. michael@0: if (i+1 < destCapacity) { michael@0: ++i; michael@0: if (dest[i] == NULL) { michael@0: dest[i] = utext_openUChars(NULL, NULL, 0, &status); michael@0: } else { michael@0: static UChar emptyString[] = {(UChar)0}; michael@0: utext_replace(dest[i], 0, utext_nativeLength(dest[i]), emptyString, 0, &status); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: } michael@0: } michael@0: else michael@0: { michael@0: // We ran off the end of the input while looking for the next delimiter. michael@0: // All the remaining text goes into the current output string. michael@0: if (UTEXT_FULL_TEXT_IN_CHUNK(input, fInputLength)) { michael@0: if (dest[i]) { michael@0: utext_replace(dest[i], 0, utext_nativeLength(dest[i]), michael@0: input->chunkContents+nextOutputStringStart, michael@0: (int32_t)(fActiveLimit-nextOutputStringStart), &status); michael@0: } else { michael@0: UText remainingText = UTEXT_INITIALIZER; michael@0: utext_openUChars(&remainingText, input->chunkContents+nextOutputStringStart, michael@0: fActiveLimit-nextOutputStringStart, &status); michael@0: dest[i] = utext_clone(NULL, &remainingText, TRUE, FALSE, &status); michael@0: utext_close(&remainingText); michael@0: } michael@0: } else { michael@0: UErrorCode lengthStatus = U_ZERO_ERROR; michael@0: int32_t remaining16Length = utext_extract(input, nextOutputStringStart, fActiveLimit, NULL, 0, &lengthStatus); michael@0: UChar *remainingChars = (UChar *)uprv_malloc(sizeof(UChar)*(remaining16Length+1)); michael@0: if (remainingChars == NULL) { michael@0: status = U_MEMORY_ALLOCATION_ERROR; michael@0: break; michael@0: } michael@0: michael@0: utext_extract(input, nextOutputStringStart, fActiveLimit, remainingChars, remaining16Length+1, &status); michael@0: if (dest[i]) { michael@0: utext_replace(dest[i], 0, utext_nativeLength(dest[i]), remainingChars, remaining16Length, &status); michael@0: } else { michael@0: UText remainingText = UTEXT_INITIALIZER; michael@0: utext_openUChars(&remainingText, remainingChars, remaining16Length, &status); michael@0: dest[i] = utext_clone(NULL, &remainingText, TRUE, FALSE, &status); michael@0: utext_close(&remainingText); michael@0: } michael@0: michael@0: uprv_free(remainingChars); michael@0: } michael@0: break; michael@0: } michael@0: if (U_FAILURE(status)) { michael@0: break; michael@0: } michael@0: } // end of for loop michael@0: return i+1; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // start michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: int32_t RegexMatcher::start(UErrorCode &status) const { michael@0: return start(0, status); michael@0: } michael@0: michael@0: int64_t RegexMatcher::start64(UErrorCode &status) const { michael@0: return start64(0, status); michael@0: } michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // start(int32_t group, UErrorCode &status) michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: michael@0: int64_t RegexMatcher::start64(int32_t group, UErrorCode &status) const { michael@0: if (U_FAILURE(status)) { michael@0: return -1; michael@0: } michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: status = fDeferredStatus; michael@0: return -1; michael@0: } michael@0: if (fMatch == FALSE) { michael@0: status = U_REGEX_INVALID_STATE; michael@0: return -1; michael@0: } michael@0: if (group < 0 || group > fPattern->fGroupMap->size()) { michael@0: status = U_INDEX_OUTOFBOUNDS_ERROR; michael@0: return -1; michael@0: } michael@0: int64_t s; michael@0: if (group == 0) { michael@0: s = fMatchStart; michael@0: } else { michael@0: int32_t groupOffset = fPattern->fGroupMap->elementAti(group-1); michael@0: U_ASSERT(groupOffset < fPattern->fFrameSize); michael@0: U_ASSERT(groupOffset >= 0); michael@0: s = fFrame->fExtra[groupOffset]; michael@0: } michael@0: michael@0: return s; michael@0: } michael@0: michael@0: michael@0: int32_t RegexMatcher::start(int32_t group, UErrorCode &status) const { michael@0: return (int32_t)start64(group, status); michael@0: } michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // useAnchoringBounds michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: RegexMatcher &RegexMatcher::useAnchoringBounds(UBool b) { michael@0: fAnchoringBounds = b; michael@0: fAnchorStart = (fAnchoringBounds ? fRegionStart : 0); michael@0: fAnchorLimit = (fAnchoringBounds ? fRegionLimit : fInputLength); michael@0: return *this; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // useTransparentBounds michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: RegexMatcher &RegexMatcher::useTransparentBounds(UBool b) { michael@0: fTransparentBounds = b; michael@0: fLookStart = (fTransparentBounds ? 0 : fRegionStart); michael@0: fLookLimit = (fTransparentBounds ? fInputLength : fRegionLimit); michael@0: return *this; michael@0: } michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // setTimeLimit michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: void RegexMatcher::setTimeLimit(int32_t limit, UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: return; michael@0: } michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: status = fDeferredStatus; michael@0: return; michael@0: } michael@0: if (limit < 0) { michael@0: status = U_ILLEGAL_ARGUMENT_ERROR; michael@0: return; michael@0: } michael@0: fTimeLimit = limit; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // getTimeLimit michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: int32_t RegexMatcher::getTimeLimit() const { michael@0: return fTimeLimit; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // setStackLimit michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: void RegexMatcher::setStackLimit(int32_t limit, UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: return; michael@0: } michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: status = fDeferredStatus; michael@0: return; michael@0: } michael@0: if (limit < 0) { michael@0: status = U_ILLEGAL_ARGUMENT_ERROR; michael@0: return; michael@0: } michael@0: michael@0: // Reset the matcher. This is needed here in case there is a current match michael@0: // whose final stack frame (containing the match results, pointed to by fFrame) michael@0: // would be lost by resizing to a smaller stack size. michael@0: reset(); michael@0: michael@0: if (limit == 0) { michael@0: // Unlimited stack expansion michael@0: fStack->setMaxCapacity(0); michael@0: } else { michael@0: // Change the units of the limit from bytes to ints, and bump the size up michael@0: // to be big enough to hold at least one stack frame for the pattern, michael@0: // if it isn't there already. michael@0: int32_t adjustedLimit = limit / sizeof(int32_t); michael@0: if (adjustedLimit < fPattern->fFrameSize) { michael@0: adjustedLimit = fPattern->fFrameSize; michael@0: } michael@0: fStack->setMaxCapacity(adjustedLimit); michael@0: } michael@0: fStackLimit = limit; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // getStackLimit michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: int32_t RegexMatcher::getStackLimit() const { michael@0: return fStackLimit; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // setMatchCallback michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: void RegexMatcher::setMatchCallback(URegexMatchCallback *callback, michael@0: const void *context, michael@0: UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: return; michael@0: } michael@0: fCallbackFn = callback; michael@0: fCallbackContext = context; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // getMatchCallback michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: void RegexMatcher::getMatchCallback(URegexMatchCallback *&callback, michael@0: const void *&context, michael@0: UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: return; michael@0: } michael@0: callback = fCallbackFn; michael@0: context = fCallbackContext; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // setMatchCallback michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: void RegexMatcher::setFindProgressCallback(URegexFindProgressCallback *callback, michael@0: const void *context, michael@0: UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: return; michael@0: } michael@0: fFindProgressCallbackFn = callback; michael@0: fFindProgressCallbackContext = context; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // getMatchCallback michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: void RegexMatcher::getFindProgressCallback(URegexFindProgressCallback *&callback, michael@0: const void *&context, michael@0: UErrorCode &status) { michael@0: if (U_FAILURE(status)) { michael@0: return; michael@0: } michael@0: callback = fFindProgressCallbackFn; michael@0: context = fFindProgressCallbackContext; michael@0: } michael@0: michael@0: michael@0: //================================================================================ michael@0: // michael@0: // Code following this point in this file is the internal michael@0: // Match Engine Implementation. michael@0: // michael@0: //================================================================================ michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // resetStack michael@0: // Discard any previous contents of the state save stack, and initialize a michael@0: // new stack frame to all -1. The -1s are needed for capture group limits, michael@0: // where they indicate that a group has not yet matched anything. michael@0: //-------------------------------------------------------------------------------- michael@0: REStackFrame *RegexMatcher::resetStack() { michael@0: // Discard any previous contents of the state save stack, and initialize a michael@0: // new stack frame with all -1 data. The -1s are needed for capture group limits, michael@0: // where they indicate that a group has not yet matched anything. michael@0: fStack->removeAllElements(); michael@0: michael@0: REStackFrame *iFrame = (REStackFrame *)fStack->reserveBlock(fPattern->fFrameSize, fDeferredStatus); michael@0: int32_t i; michael@0: for (i=0; ifFrameSize-RESTACKFRAME_HDRCOUNT; i++) { michael@0: iFrame->fExtra[i] = -1; michael@0: } michael@0: return iFrame; michael@0: } michael@0: michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // isWordBoundary michael@0: // in perl, "xab..cd..", \b is true at positions 0,3,5,7 michael@0: // For us, michael@0: // If the current char is a combining mark, michael@0: // \b is FALSE. michael@0: // Else Scan backwards to the first non-combining char. michael@0: // We are at a boundary if the this char and the original chars are michael@0: // opposite in membership in \w set michael@0: // michael@0: // parameters: pos - the current position in the input buffer michael@0: // michael@0: // TODO: double-check edge cases at region boundaries. michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: UBool RegexMatcher::isWordBoundary(int64_t pos) { michael@0: UBool isBoundary = FALSE; michael@0: UBool cIsWord = FALSE; michael@0: michael@0: if (pos >= fLookLimit) { michael@0: fHitEnd = TRUE; michael@0: } else { michael@0: // Determine whether char c at current position is a member of the word set of chars. michael@0: // If we're off the end of the string, behave as though we're not at a word char. michael@0: UTEXT_SETNATIVEINDEX(fInputText, pos); michael@0: UChar32 c = UTEXT_CURRENT32(fInputText); michael@0: if (u_hasBinaryProperty(c, UCHAR_GRAPHEME_EXTEND) || u_charType(c) == U_FORMAT_CHAR) { michael@0: // Current char is a combining one. Not a boundary. michael@0: return FALSE; michael@0: } michael@0: cIsWord = fPattern->fStaticSets[URX_ISWORD_SET]->contains(c); michael@0: } michael@0: michael@0: // Back up until we come to a non-combining char, determine whether michael@0: // that char is a word char. michael@0: UBool prevCIsWord = FALSE; michael@0: for (;;) { michael@0: if (UTEXT_GETNATIVEINDEX(fInputText) <= fLookStart) { michael@0: break; michael@0: } michael@0: UChar32 prevChar = UTEXT_PREVIOUS32(fInputText); michael@0: if (!(u_hasBinaryProperty(prevChar, UCHAR_GRAPHEME_EXTEND) michael@0: || u_charType(prevChar) == U_FORMAT_CHAR)) { michael@0: prevCIsWord = fPattern->fStaticSets[URX_ISWORD_SET]->contains(prevChar); michael@0: break; michael@0: } michael@0: } michael@0: isBoundary = cIsWord ^ prevCIsWord; michael@0: return isBoundary; michael@0: } michael@0: michael@0: UBool RegexMatcher::isChunkWordBoundary(int32_t pos) { michael@0: UBool isBoundary = FALSE; michael@0: UBool cIsWord = FALSE; michael@0: michael@0: const UChar *inputBuf = fInputText->chunkContents; michael@0: michael@0: if (pos >= fLookLimit) { michael@0: fHitEnd = TRUE; michael@0: } else { michael@0: // Determine whether char c at current position is a member of the word set of chars. michael@0: // If we're off the end of the string, behave as though we're not at a word char. michael@0: UChar32 c; michael@0: U16_GET(inputBuf, fLookStart, pos, fLookLimit, c); michael@0: if (u_hasBinaryProperty(c, UCHAR_GRAPHEME_EXTEND) || u_charType(c) == U_FORMAT_CHAR) { michael@0: // Current char is a combining one. Not a boundary. michael@0: return FALSE; michael@0: } michael@0: cIsWord = fPattern->fStaticSets[URX_ISWORD_SET]->contains(c); michael@0: } michael@0: michael@0: // Back up until we come to a non-combining char, determine whether michael@0: // that char is a word char. michael@0: UBool prevCIsWord = FALSE; michael@0: for (;;) { michael@0: if (pos <= fLookStart) { michael@0: break; michael@0: } michael@0: UChar32 prevChar; michael@0: U16_PREV(inputBuf, fLookStart, pos, prevChar); michael@0: if (!(u_hasBinaryProperty(prevChar, UCHAR_GRAPHEME_EXTEND) michael@0: || u_charType(prevChar) == U_FORMAT_CHAR)) { michael@0: prevCIsWord = fPattern->fStaticSets[URX_ISWORD_SET]->contains(prevChar); michael@0: break; michael@0: } michael@0: } michael@0: isBoundary = cIsWord ^ prevCIsWord; michael@0: return isBoundary; michael@0: } michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // isUWordBoundary michael@0: // michael@0: // Test for a word boundary using RBBI word break. michael@0: // michael@0: // parameters: pos - the current position in the input buffer michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: UBool RegexMatcher::isUWordBoundary(int64_t pos) { michael@0: UBool returnVal = FALSE; michael@0: #if UCONFIG_NO_BREAK_ITERATION==0 michael@0: michael@0: // If we haven't yet created a break iterator for this matcher, do it now. michael@0: if (fWordBreakItr == NULL) { michael@0: fWordBreakItr = michael@0: (RuleBasedBreakIterator *)BreakIterator::createWordInstance(Locale::getEnglish(), fDeferredStatus); michael@0: if (U_FAILURE(fDeferredStatus)) { michael@0: return FALSE; michael@0: } michael@0: fWordBreakItr->setText(fInputText, fDeferredStatus); michael@0: } michael@0: michael@0: if (pos >= fLookLimit) { michael@0: fHitEnd = TRUE; michael@0: returnVal = TRUE; // With Unicode word rules, only positions within the interior of "real" michael@0: // words are not boundaries. All non-word chars stand by themselves, michael@0: // with word boundaries on both sides. michael@0: } else { michael@0: if (!UTEXT_USES_U16(fInputText)) { michael@0: // !!!: Would like a better way to do this! michael@0: UErrorCode status = U_ZERO_ERROR; michael@0: pos = utext_extract(fInputText, 0, pos, NULL, 0, &status); michael@0: } michael@0: returnVal = fWordBreakItr->isBoundary((int32_t)pos); michael@0: } michael@0: #endif michael@0: return returnVal; michael@0: } michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // IncrementTime This function is called once each TIMER_INITIAL_VALUE state michael@0: // saves. Increment the "time" counter, and call the michael@0: // user callback function if there is one installed. michael@0: // michael@0: // If the match operation needs to be aborted, either for a time-out michael@0: // or because the user callback asked for it, just set an error status. michael@0: // The engine will pick that up and stop in its outer loop. michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: void RegexMatcher::IncrementTime(UErrorCode &status) { michael@0: fTickCounter = TIMER_INITIAL_VALUE; michael@0: fTime++; michael@0: if (fCallbackFn != NULL) { michael@0: if ((*fCallbackFn)(fCallbackContext, fTime) == FALSE) { michael@0: status = U_REGEX_STOPPED_BY_CALLER; michael@0: return; michael@0: } michael@0: } michael@0: if (fTimeLimit > 0 && fTime >= fTimeLimit) { michael@0: status = U_REGEX_TIME_OUT; michael@0: } michael@0: } michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // ReportFindProgress This function is called once for each advance in the target michael@0: // string from the find() function, and calls the user progress callback michael@0: // function if there is one installed. michael@0: // michael@0: // NOTE: michael@0: // michael@0: // If the match operation needs to be aborted because the user michael@0: // callback asked for it, just set an error status. michael@0: // The engine will pick that up and stop in its outer loop. michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: UBool RegexMatcher::ReportFindProgress(int64_t matchIndex, UErrorCode &status) { michael@0: if (fFindProgressCallbackFn != NULL) { michael@0: if ((*fFindProgressCallbackFn)(fFindProgressCallbackContext, matchIndex) == FALSE) { michael@0: status = U_ZERO_ERROR /*U_REGEX_STOPPED_BY_CALLER*/; michael@0: return FALSE; michael@0: } michael@0: } michael@0: return TRUE; michael@0: } michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // StateSave michael@0: // Make a new stack frame, initialized as a copy of the current stack frame. michael@0: // Set the pattern index in the original stack frame from the operand value michael@0: // in the opcode. Execution of the engine continues with the state in michael@0: // the newly created stack frame michael@0: // michael@0: // Note that reserveBlock() may grow the stack, resulting in the michael@0: // whole thing being relocated in memory. michael@0: // michael@0: // Parameters: michael@0: // fp The top frame pointer when called. At return, a new michael@0: // fame will be present michael@0: // savePatIdx An index into the compiled pattern. Goes into the original michael@0: // (not new) frame. If execution ever back-tracks out of the michael@0: // new frame, this will be where we continue from in the pattern. michael@0: // Return michael@0: // The new frame pointer. michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: inline REStackFrame *RegexMatcher::StateSave(REStackFrame *fp, int64_t savePatIdx, UErrorCode &status) { michael@0: // push storage for a new frame. michael@0: int64_t *newFP = fStack->reserveBlock(fFrameSize, status); michael@0: if (newFP == NULL) { michael@0: // Failure on attempted stack expansion. michael@0: // Stack function set some other error code, change it to a more michael@0: // specific one for regular expressions. michael@0: status = U_REGEX_STACK_OVERFLOW; michael@0: // We need to return a writable stack frame, so just return the michael@0: // previous frame. The match operation will stop quickly michael@0: // because of the error status, after which the frame will never michael@0: // be looked at again. michael@0: return fp; michael@0: } michael@0: fp = (REStackFrame *)(newFP - fFrameSize); // in case of realloc of stack. michael@0: michael@0: // New stack frame = copy of old top frame. michael@0: int64_t *source = (int64_t *)fp; michael@0: int64_t *dest = newFP; michael@0: for (;;) { michael@0: *dest++ = *source++; michael@0: if (source == newFP) { michael@0: break; michael@0: } michael@0: } michael@0: michael@0: fTickCounter--; michael@0: if (fTickCounter <= 0) { michael@0: IncrementTime(status); // Re-initializes fTickCounter michael@0: } michael@0: fp->fPatIdx = savePatIdx; michael@0: return (REStackFrame *)newFP; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // MatchAt This is the actual matching engine. michael@0: // michael@0: // startIdx: begin matching a this index. michael@0: // toEnd: if true, match must extend to end of the input region michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: void RegexMatcher::MatchAt(int64_t startIdx, UBool toEnd, UErrorCode &status) { michael@0: UBool isMatch = FALSE; // True if the we have a match. michael@0: michael@0: int64_t backSearchIndex = U_INT64_MAX; // used after greedy single-character matches for searching backwards michael@0: michael@0: int32_t op; // Operation from the compiled pattern, split into michael@0: int32_t opType; // the opcode michael@0: int32_t opValue; // and the operand value. michael@0: michael@0: #ifdef REGEX_RUN_DEBUG michael@0: if (fTraceDebug) michael@0: { michael@0: printf("MatchAt(startIdx=%ld)\n", startIdx); michael@0: printf("Original Pattern: "); michael@0: UChar32 c = utext_next32From(fPattern->fPattern, 0); michael@0: while (c != U_SENTINEL) { michael@0: if (c<32 || c>256) { michael@0: c = '.'; michael@0: } michael@0: REGEX_DUMP_DEBUG_PRINTF(("%c", c)); michael@0: michael@0: c = UTEXT_NEXT32(fPattern->fPattern); michael@0: } michael@0: printf("\n"); michael@0: printf("Input String: "); michael@0: c = utext_next32From(fInputText, 0); michael@0: while (c != U_SENTINEL) { michael@0: if (c<32 || c>256) { michael@0: c = '.'; michael@0: } michael@0: printf("%c", c); michael@0: michael@0: c = UTEXT_NEXT32(fInputText); michael@0: } michael@0: printf("\n"); michael@0: printf("\n"); michael@0: } michael@0: #endif michael@0: michael@0: if (U_FAILURE(status)) { michael@0: return; michael@0: } michael@0: michael@0: // Cache frequently referenced items from the compiled pattern michael@0: // michael@0: int64_t *pat = fPattern->fCompiledPat->getBuffer(); michael@0: michael@0: const UChar *litText = fPattern->fLiteralText.getBuffer(); michael@0: UVector *sets = fPattern->fSets; michael@0: michael@0: fFrameSize = fPattern->fFrameSize; michael@0: REStackFrame *fp = resetStack(); michael@0: michael@0: fp->fPatIdx = 0; michael@0: fp->fInputIdx = startIdx; michael@0: michael@0: // Zero out the pattern's static data michael@0: int32_t i; michael@0: for (i = 0; ifDataSize; i++) { michael@0: fData[i] = 0; michael@0: } michael@0: michael@0: // michael@0: // Main loop for interpreting the compiled pattern. michael@0: // One iteration of the loop per pattern operation performed. michael@0: // michael@0: for (;;) { michael@0: #if 0 michael@0: if (_heapchk() != _HEAPOK) { michael@0: fprintf(stderr, "Heap Trouble\n"); michael@0: } michael@0: #endif michael@0: michael@0: op = (int32_t)pat[fp->fPatIdx]; michael@0: opType = URX_TYPE(op); michael@0: opValue = URX_VAL(op); michael@0: #ifdef REGEX_RUN_DEBUG michael@0: if (fTraceDebug) { michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: printf("inputIdx=%ld inputChar=%x sp=%3ld activeLimit=%ld ", fp->fInputIdx, michael@0: UTEXT_CURRENT32(fInputText), (int64_t *)fp-fStack->getBuffer(), fActiveLimit); michael@0: fPattern->dumpOp(fp->fPatIdx); michael@0: } michael@0: #endif michael@0: fp->fPatIdx++; michael@0: michael@0: switch (opType) { michael@0: michael@0: michael@0: case URX_NOP: michael@0: break; michael@0: michael@0: michael@0: case URX_BACKTRACK: michael@0: // Force a backtrack. In some circumstances, the pattern compiler michael@0: // will notice that the pattern can't possibly match anything, and will michael@0: // emit one of these at that point. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: michael@0: michael@0: case URX_ONECHAR: michael@0: if (fp->fInputIdx < fActiveLimit) { michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: UChar32 c = UTEXT_NEXT32(fInputText); michael@0: if (c == opValue) { michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: break; michael@0: } michael@0: } else { michael@0: fHitEnd = TRUE; michael@0: } michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: michael@0: michael@0: case URX_STRING: michael@0: { michael@0: // Test input against a literal string. michael@0: // Strings require two slots in the compiled pattern, one for the michael@0: // offset to the string text, and one for the length. michael@0: michael@0: int32_t stringStartIdx = opValue; michael@0: op = (int32_t)pat[fp->fPatIdx]; // Fetch the second operand michael@0: fp->fPatIdx++; michael@0: opType = URX_TYPE(op); michael@0: int32_t stringLen = URX_VAL(op); michael@0: U_ASSERT(opType == URX_STRING_LEN); michael@0: U_ASSERT(stringLen >= 2); michael@0: michael@0: const UChar *patternString = litText+stringStartIdx; michael@0: int32_t patternStringIndex = 0; michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: UChar32 inputChar; michael@0: UChar32 patternChar; michael@0: UBool success = TRUE; michael@0: while (patternStringIndex < stringLen) { michael@0: if (UTEXT_GETNATIVEINDEX(fInputText) >= fActiveLimit) { michael@0: success = FALSE; michael@0: fHitEnd = TRUE; michael@0: break; michael@0: } michael@0: inputChar = UTEXT_NEXT32(fInputText); michael@0: U16_NEXT(patternString, patternStringIndex, stringLen, patternChar); michael@0: if (patternChar != inputChar) { michael@0: success = FALSE; michael@0: break; michael@0: } michael@0: } michael@0: michael@0: if (success) { michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } else { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_STATE_SAVE: michael@0: fp = StateSave(fp, opValue, status); michael@0: break; michael@0: michael@0: michael@0: case URX_END: michael@0: // The match loop will exit via this path on a successful match, michael@0: // when we reach the end of the pattern. michael@0: if (toEnd && fp->fInputIdx != fActiveLimit) { michael@0: // The pattern matched, but not to the end of input. Try some more. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: isMatch = TRUE; michael@0: goto breakFromLoop; michael@0: michael@0: // Start and End Capture stack frame variables are laid out out like this: michael@0: // fp->fExtra[opValue] - The start of a completed capture group michael@0: // opValue+1 - The end of a completed capture group michael@0: // opValue+2 - the start of a capture group whose end michael@0: // has not yet been reached (and might not ever be). michael@0: case URX_START_CAPTURE: michael@0: U_ASSERT(opValue >= 0 && opValue < fFrameSize-3); michael@0: fp->fExtra[opValue+2] = fp->fInputIdx; michael@0: break; michael@0: michael@0: michael@0: case URX_END_CAPTURE: michael@0: U_ASSERT(opValue >= 0 && opValue < fFrameSize-3); michael@0: U_ASSERT(fp->fExtra[opValue+2] >= 0); // Start pos for this group must be set. michael@0: fp->fExtra[opValue] = fp->fExtra[opValue+2]; // Tentative start becomes real. michael@0: fp->fExtra[opValue+1] = fp->fInputIdx; // End position michael@0: U_ASSERT(fp->fExtra[opValue] <= fp->fExtra[opValue+1]); michael@0: break; michael@0: michael@0: michael@0: case URX_DOLLAR: // $, test for End of line michael@0: // or for position before new line at end of input michael@0: { michael@0: if (fp->fInputIdx >= fAnchorLimit) { michael@0: // We really are at the end of input. Success. michael@0: fHitEnd = TRUE; michael@0: fRequireEnd = TRUE; michael@0: break; michael@0: } michael@0: michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: michael@0: // If we are positioned just before a new-line that is located at the michael@0: // end of input, succeed. michael@0: UChar32 c = UTEXT_NEXT32(fInputText); michael@0: if (UTEXT_GETNATIVEINDEX(fInputText) >= fAnchorLimit) { michael@0: if ((c>=0x0a && c<=0x0d) || c==0x85 || c==0x2028 || c==0x2029) { michael@0: // If not in the middle of a CR/LF sequence michael@0: if ( !(c==0x0a && fp->fInputIdx>fAnchorStart && ((void)UTEXT_PREVIOUS32(fInputText), UTEXT_PREVIOUS32(fInputText))==0x0d)) { michael@0: // At new-line at end of input. Success michael@0: fHitEnd = TRUE; michael@0: fRequireEnd = TRUE; michael@0: michael@0: break; michael@0: } michael@0: } michael@0: } else { michael@0: UChar32 nextC = UTEXT_NEXT32(fInputText); michael@0: if (c == 0x0d && nextC == 0x0a && UTEXT_GETNATIVEINDEX(fInputText) >= fAnchorLimit) { michael@0: fHitEnd = TRUE; michael@0: fRequireEnd = TRUE; michael@0: break; // At CR/LF at end of input. Success michael@0: } michael@0: } michael@0: michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_DOLLAR_D: // $, test for End of Line, in UNIX_LINES mode. michael@0: if (fp->fInputIdx >= fAnchorLimit) { michael@0: // Off the end of input. Success. michael@0: fHitEnd = TRUE; michael@0: fRequireEnd = TRUE; michael@0: break; michael@0: } else { michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: UChar32 c = UTEXT_NEXT32(fInputText); michael@0: // Either at the last character of input, or off the end. michael@0: if (c == 0x0a && UTEXT_GETNATIVEINDEX(fInputText) == fAnchorLimit) { michael@0: fHitEnd = TRUE; michael@0: fRequireEnd = TRUE; michael@0: break; michael@0: } michael@0: } michael@0: michael@0: // Not at end of input. Back-track out. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: michael@0: michael@0: case URX_DOLLAR_M: // $, test for End of line in multi-line mode michael@0: { michael@0: if (fp->fInputIdx >= fAnchorLimit) { michael@0: // We really are at the end of input. Success. michael@0: fHitEnd = TRUE; michael@0: fRequireEnd = TRUE; michael@0: break; michael@0: } michael@0: // If we are positioned just before a new-line, succeed. michael@0: // It makes no difference where the new-line is within the input. michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: UChar32 c = UTEXT_CURRENT32(fInputText); michael@0: if ((c>=0x0a && c<=0x0d) || c==0x85 ||c==0x2028 || c==0x2029) { michael@0: // At a line end, except for the odd chance of being in the middle of a CR/LF sequence michael@0: // In multi-line mode, hitting a new-line just before the end of input does not michael@0: // set the hitEnd or requireEnd flags michael@0: if ( !(c==0x0a && fp->fInputIdx>fAnchorStart && UTEXT_PREVIOUS32(fInputText)==0x0d)) { michael@0: break; michael@0: } michael@0: } michael@0: // not at a new line. Fail. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_DOLLAR_MD: // $, test for End of line in multi-line and UNIX_LINES mode michael@0: { michael@0: if (fp->fInputIdx >= fAnchorLimit) { michael@0: // We really are at the end of input. Success. michael@0: fHitEnd = TRUE; michael@0: fRequireEnd = TRUE; // Java set requireEnd in this case, even though michael@0: break; // adding a new-line would not lose the match. michael@0: } michael@0: // If we are not positioned just before a new-line, the test fails; backtrack out. michael@0: // It makes no difference where the new-line is within the input. michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: if (UTEXT_CURRENT32(fInputText) != 0x0a) { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_CARET: // ^, test for start of line michael@0: if (fp->fInputIdx != fAnchorStart) { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_CARET_M: // ^, test for start of line in mulit-line mode michael@0: { michael@0: if (fp->fInputIdx == fAnchorStart) { michael@0: // We are at the start input. Success. michael@0: break; michael@0: } michael@0: // Check whether character just before the current pos is a new-line michael@0: // unless we are at the end of input michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: UChar32 c = UTEXT_PREVIOUS32(fInputText); michael@0: if ((fp->fInputIdx < fAnchorLimit) && michael@0: ((c<=0x0d && c>=0x0a) || c==0x85 ||c==0x2028 || c==0x2029)) { michael@0: // It's a new-line. ^ is true. Success. michael@0: // TODO: what should be done with positions between a CR and LF? michael@0: break; michael@0: } michael@0: // Not at the start of a line. Fail. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_CARET_M_UNIX: // ^, test for start of line in mulit-line + Unix-line mode michael@0: { michael@0: U_ASSERT(fp->fInputIdx >= fAnchorStart); michael@0: if (fp->fInputIdx <= fAnchorStart) { michael@0: // We are at the start input. Success. michael@0: break; michael@0: } michael@0: // Check whether character just before the current pos is a new-line michael@0: U_ASSERT(fp->fInputIdx <= fAnchorLimit); michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: UChar32 c = UTEXT_PREVIOUS32(fInputText); michael@0: if (c != 0x0a) { michael@0: // Not at the start of a line. Back-track out. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: case URX_BACKSLASH_B: // Test for word boundaries michael@0: { michael@0: UBool success = isWordBoundary(fp->fInputIdx); michael@0: success ^= (UBool)(opValue != 0); // flip sense for \B michael@0: if (!success) { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_BACKSLASH_BU: // Test for word boundaries, Unicode-style michael@0: { michael@0: UBool success = isUWordBoundary(fp->fInputIdx); michael@0: success ^= (UBool)(opValue != 0); // flip sense for \B michael@0: if (!success) { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_BACKSLASH_D: // Test for decimal digit michael@0: { michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: fHitEnd = TRUE; michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: michael@0: UChar32 c = UTEXT_NEXT32(fInputText); michael@0: int8_t ctype = u_charType(c); // TODO: make a unicode set for this. Will be faster. michael@0: UBool success = (ctype == U_DECIMAL_DIGIT_NUMBER); michael@0: success ^= (UBool)(opValue != 0); // flip sense for \D michael@0: if (success) { michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } else { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_BACKSLASH_G: // Test for position at end of previous match michael@0: if (!((fMatch && fp->fInputIdx==fMatchEnd) || (fMatch==FALSE && fp->fInputIdx==fActiveStart))) { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_BACKSLASH_X: michael@0: // Match a Grapheme, as defined by Unicode TR 29. michael@0: // Differs slightly from Perl, which consumes combining marks independently michael@0: // of context. michael@0: { michael@0: michael@0: // Fail if at end of input michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: fHitEnd = TRUE; michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: michael@0: // Examine (and consume) the current char. michael@0: // Dispatch into a little state machine, based on the char. michael@0: UChar32 c; michael@0: c = UTEXT_NEXT32(fInputText); michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: UnicodeSet **sets = fPattern->fStaticSets; michael@0: if (sets[URX_GC_NORMAL]->contains(c)) goto GC_Extend; michael@0: if (sets[URX_GC_CONTROL]->contains(c)) goto GC_Control; michael@0: if (sets[URX_GC_L]->contains(c)) goto GC_L; michael@0: if (sets[URX_GC_LV]->contains(c)) goto GC_V; michael@0: if (sets[URX_GC_LVT]->contains(c)) goto GC_T; michael@0: if (sets[URX_GC_V]->contains(c)) goto GC_V; michael@0: if (sets[URX_GC_T]->contains(c)) goto GC_T; michael@0: goto GC_Extend; michael@0: michael@0: michael@0: michael@0: GC_L: michael@0: if (fp->fInputIdx >= fActiveLimit) goto GC_Done; michael@0: c = UTEXT_NEXT32(fInputText); michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: if (sets[URX_GC_L]->contains(c)) goto GC_L; michael@0: if (sets[URX_GC_LV]->contains(c)) goto GC_V; michael@0: if (sets[URX_GC_LVT]->contains(c)) goto GC_T; michael@0: if (sets[URX_GC_V]->contains(c)) goto GC_V; michael@0: (void)UTEXT_PREVIOUS32(fInputText); michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: goto GC_Extend; michael@0: michael@0: GC_V: michael@0: if (fp->fInputIdx >= fActiveLimit) goto GC_Done; michael@0: c = UTEXT_NEXT32(fInputText); michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: if (sets[URX_GC_V]->contains(c)) goto GC_V; michael@0: if (sets[URX_GC_T]->contains(c)) goto GC_T; michael@0: (void)UTEXT_PREVIOUS32(fInputText); michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: goto GC_Extend; michael@0: michael@0: GC_T: michael@0: if (fp->fInputIdx >= fActiveLimit) goto GC_Done; michael@0: c = UTEXT_NEXT32(fInputText); michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: if (sets[URX_GC_T]->contains(c)) goto GC_T; michael@0: (void)UTEXT_PREVIOUS32(fInputText); michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: goto GC_Extend; michael@0: michael@0: GC_Extend: michael@0: // Combining characters are consumed here michael@0: for (;;) { michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: break; michael@0: } michael@0: c = UTEXT_CURRENT32(fInputText); michael@0: if (sets[URX_GC_EXTEND]->contains(c) == FALSE) { michael@0: break; michael@0: } michael@0: (void)UTEXT_NEXT32(fInputText); michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } michael@0: goto GC_Done; michael@0: michael@0: GC_Control: michael@0: // Most control chars stand alone (don't combine with combining chars), michael@0: // except for that CR/LF sequence is a single grapheme cluster. michael@0: if (c == 0x0d && fp->fInputIdx < fActiveLimit && UTEXT_CURRENT32(fInputText) == 0x0a) { michael@0: c = UTEXT_NEXT32(fInputText); michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } michael@0: michael@0: GC_Done: michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: fHitEnd = TRUE; michael@0: } michael@0: break; michael@0: } michael@0: michael@0: michael@0: michael@0: michael@0: case URX_BACKSLASH_Z: // Test for end of Input michael@0: if (fp->fInputIdx < fAnchorLimit) { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } else { michael@0: fHitEnd = TRUE; michael@0: fRequireEnd = TRUE; michael@0: } michael@0: break; michael@0: michael@0: michael@0: michael@0: case URX_STATIC_SETREF: michael@0: { michael@0: // Test input character against one of the predefined sets michael@0: // (Word Characters, for example) michael@0: // The high bit of the op value is a flag for the match polarity. michael@0: // 0: success if input char is in set. michael@0: // 1: success if input char is not in set. michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: fHitEnd = TRUE; michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: UBool success = ((opValue & URX_NEG_SET) == URX_NEG_SET); michael@0: opValue &= ~URX_NEG_SET; michael@0: U_ASSERT(opValue > 0 && opValue < URX_LAST_SET); michael@0: michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: UChar32 c = UTEXT_NEXT32(fInputText); michael@0: if (c < 256) { michael@0: Regex8BitSet *s8 = &fPattern->fStaticSets8[opValue]; michael@0: if (s8->contains(c)) { michael@0: success = !success; michael@0: } michael@0: } else { michael@0: const UnicodeSet *s = fPattern->fStaticSets[opValue]; michael@0: if (s->contains(c)) { michael@0: success = !success; michael@0: } michael@0: } michael@0: if (success) { michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } else { michael@0: // the character wasn't in the set. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_STAT_SETREF_N: michael@0: { michael@0: // Test input character for NOT being a member of one of michael@0: // the predefined sets (Word Characters, for example) michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: fHitEnd = TRUE; michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: U_ASSERT(opValue > 0 && opValue < URX_LAST_SET); michael@0: michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: michael@0: UChar32 c = UTEXT_NEXT32(fInputText); michael@0: if (c < 256) { michael@0: Regex8BitSet *s8 = &fPattern->fStaticSets8[opValue]; michael@0: if (s8->contains(c) == FALSE) { michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: break; michael@0: } michael@0: } else { michael@0: const UnicodeSet *s = fPattern->fStaticSets[opValue]; michael@0: if (s->contains(c) == FALSE) { michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: break; michael@0: } michael@0: } michael@0: // the character wasn't in the set. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_SETREF: michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: fHitEnd = TRUE; michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } else { michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: michael@0: // There is input left. Pick up one char and test it for set membership. michael@0: UChar32 c = UTEXT_NEXT32(fInputText); michael@0: U_ASSERT(opValue > 0 && opValue < sets->size()); michael@0: if (c<256) { michael@0: Regex8BitSet *s8 = &fPattern->fSets8[opValue]; michael@0: if (s8->contains(c)) { michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: break; michael@0: } michael@0: } else { michael@0: UnicodeSet *s = (UnicodeSet *)sets->elementAt(opValue); michael@0: if (s->contains(c)) { michael@0: // The character is in the set. A Match. michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: break; michael@0: } michael@0: } michael@0: michael@0: // the character wasn't in the set. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_DOTANY: michael@0: { michael@0: // . matches anything, but stops at end-of-line. michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: // At end of input. Match failed. Backtrack out. michael@0: fHitEnd = TRUE; michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: michael@0: // There is input left. Advance over one char, unless we've hit end-of-line michael@0: UChar32 c = UTEXT_NEXT32(fInputText); michael@0: if (((c & 0x7f) <= 0x29) && // First quickly bypass as many chars as possible michael@0: ((c<=0x0d && c>=0x0a) || c==0x85 ||c==0x2028 || c==0x2029)) { michael@0: // End of line in normal mode. . does not match. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_DOTANY_ALL: michael@0: { michael@0: // ., in dot-matches-all (including new lines) mode michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: // At end of input. Match failed. Backtrack out. michael@0: fHitEnd = TRUE; michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: michael@0: // There is input left. Advance over one char, except if we are michael@0: // at a cr/lf, advance over both of them. michael@0: UChar32 c; michael@0: c = UTEXT_NEXT32(fInputText); michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: if (c==0x0d && fp->fInputIdx < fActiveLimit) { michael@0: // In the case of a CR/LF, we need to advance over both. michael@0: UChar32 nextc = UTEXT_CURRENT32(fInputText); michael@0: if (nextc == 0x0a) { michael@0: (void)UTEXT_NEXT32(fInputText); michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_DOTANY_UNIX: michael@0: { michael@0: // '.' operator, matches all, but stops at end-of-line. michael@0: // UNIX_LINES mode, so 0x0a is the only recognized line ending. michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: // At end of input. Match failed. Backtrack out. michael@0: fHitEnd = TRUE; michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: michael@0: // There is input left. Advance over one char, unless we've hit end-of-line michael@0: UChar32 c = UTEXT_NEXT32(fInputText); michael@0: if (c == 0x0a) { michael@0: // End of line in normal mode. '.' does not match the \n michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } else { michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_JMP: michael@0: fp->fPatIdx = opValue; michael@0: break; michael@0: michael@0: case URX_FAIL: michael@0: isMatch = FALSE; michael@0: goto breakFromLoop; michael@0: michael@0: case URX_JMP_SAV: michael@0: U_ASSERT(opValue < fPattern->fCompiledPat->size()); michael@0: fp = StateSave(fp, fp->fPatIdx, status); // State save to loc following current michael@0: fp->fPatIdx = opValue; // Then JMP. michael@0: break; michael@0: michael@0: case URX_JMP_SAV_X: michael@0: // This opcode is used with (x)+, when x can match a zero length string. michael@0: // Same as JMP_SAV, except conditional on the match having made forward progress. michael@0: // Destination of the JMP must be a URX_STO_INP_LOC, from which we get the michael@0: // data address of the input position at the start of the loop. michael@0: { michael@0: U_ASSERT(opValue > 0 && opValue < fPattern->fCompiledPat->size()); michael@0: int32_t stoOp = (int32_t)pat[opValue-1]; michael@0: U_ASSERT(URX_TYPE(stoOp) == URX_STO_INP_LOC); michael@0: int32_t frameLoc = URX_VAL(stoOp); michael@0: U_ASSERT(frameLoc >= 0 && frameLoc < fFrameSize); michael@0: int64_t prevInputIdx = fp->fExtra[frameLoc]; michael@0: U_ASSERT(prevInputIdx <= fp->fInputIdx); michael@0: if (prevInputIdx < fp->fInputIdx) { michael@0: // The match did make progress. Repeat the loop. michael@0: fp = StateSave(fp, fp->fPatIdx, status); // State save to loc following current michael@0: fp->fPatIdx = opValue; michael@0: fp->fExtra[frameLoc] = fp->fInputIdx; michael@0: } michael@0: // If the input position did not advance, we do nothing here, michael@0: // execution will fall out of the loop. michael@0: } michael@0: break; michael@0: michael@0: case URX_CTR_INIT: michael@0: { michael@0: U_ASSERT(opValue >= 0 && opValue < fFrameSize-2); michael@0: fp->fExtra[opValue] = 0; // Set the loop counter variable to zero michael@0: michael@0: // Pick up the three extra operands that CTR_INIT has, and michael@0: // skip the pattern location counter past michael@0: int32_t instrOperandLoc = (int32_t)fp->fPatIdx; michael@0: fp->fPatIdx += 3; michael@0: int32_t loopLoc = URX_VAL(pat[instrOperandLoc]); michael@0: int32_t minCount = (int32_t)pat[instrOperandLoc+1]; michael@0: int32_t maxCount = (int32_t)pat[instrOperandLoc+2]; michael@0: U_ASSERT(minCount>=0); michael@0: U_ASSERT(maxCount>=minCount || maxCount==-1); michael@0: U_ASSERT(loopLoc>=fp->fPatIdx); michael@0: michael@0: if (minCount == 0) { michael@0: fp = StateSave(fp, loopLoc+1, status); michael@0: } michael@0: if (maxCount == -1) { michael@0: fp->fExtra[opValue+1] = fp->fInputIdx; // For loop breaking. michael@0: } else if (maxCount == 0) { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: case URX_CTR_LOOP: michael@0: { michael@0: U_ASSERT(opValue>0 && opValue < fp->fPatIdx-2); michael@0: int32_t initOp = (int32_t)pat[opValue]; michael@0: U_ASSERT(URX_TYPE(initOp) == URX_CTR_INIT); michael@0: int64_t *pCounter = &fp->fExtra[URX_VAL(initOp)]; michael@0: int32_t minCount = (int32_t)pat[opValue+2]; michael@0: int32_t maxCount = (int32_t)pat[opValue+3]; michael@0: (*pCounter)++; michael@0: if ((uint64_t)*pCounter >= (uint32_t)maxCount && maxCount != -1) { michael@0: U_ASSERT(*pCounter == maxCount); michael@0: break; michael@0: } michael@0: if (*pCounter >= minCount) { michael@0: if (maxCount == -1) { michael@0: // Loop has no hard upper bound. michael@0: // Check that it is progressing through the input, break if it is not. michael@0: int64_t *pLastInputIdx = &fp->fExtra[URX_VAL(initOp) + 1]; michael@0: if (fp->fInputIdx == *pLastInputIdx) { michael@0: break; michael@0: } else { michael@0: *pLastInputIdx = fp->fInputIdx; michael@0: } michael@0: } michael@0: fp = StateSave(fp, fp->fPatIdx, status); michael@0: } michael@0: fp->fPatIdx = opValue + 4; // Loop back. michael@0: } michael@0: break; michael@0: michael@0: case URX_CTR_INIT_NG: michael@0: { michael@0: // Initialize a non-greedy loop michael@0: U_ASSERT(opValue >= 0 && opValue < fFrameSize-2); michael@0: fp->fExtra[opValue] = 0; // Set the loop counter variable to zero michael@0: michael@0: // Pick up the three extra operands that CTR_INIT_NG has, and michael@0: // skip the pattern location counter past michael@0: int32_t instrOperandLoc = (int32_t)fp->fPatIdx; michael@0: fp->fPatIdx += 3; michael@0: int32_t loopLoc = URX_VAL(pat[instrOperandLoc]); michael@0: int32_t minCount = (int32_t)pat[instrOperandLoc+1]; michael@0: int32_t maxCount = (int32_t)pat[instrOperandLoc+2]; michael@0: U_ASSERT(minCount>=0); michael@0: U_ASSERT(maxCount>=minCount || maxCount==-1); michael@0: U_ASSERT(loopLoc>fp->fPatIdx); michael@0: if (maxCount == -1) { michael@0: fp->fExtra[opValue+1] = fp->fInputIdx; // Save initial input index for loop breaking. michael@0: } michael@0: michael@0: if (minCount == 0) { michael@0: if (maxCount != 0) { michael@0: fp = StateSave(fp, fp->fPatIdx, status); michael@0: } michael@0: fp->fPatIdx = loopLoc+1; // Continue with stuff after repeated block michael@0: } michael@0: } michael@0: break; michael@0: michael@0: case URX_CTR_LOOP_NG: michael@0: { michael@0: // Non-greedy {min, max} loops michael@0: U_ASSERT(opValue>0 && opValue < fp->fPatIdx-2); michael@0: int32_t initOp = (int32_t)pat[opValue]; michael@0: U_ASSERT(URX_TYPE(initOp) == URX_CTR_INIT_NG); michael@0: int64_t *pCounter = &fp->fExtra[URX_VAL(initOp)]; michael@0: int32_t minCount = (int32_t)pat[opValue+2]; michael@0: int32_t maxCount = (int32_t)pat[opValue+3]; michael@0: michael@0: (*pCounter)++; michael@0: if ((uint64_t)*pCounter >= (uint32_t)maxCount && maxCount != -1) { michael@0: // The loop has matched the maximum permitted number of times. michael@0: // Break out of here with no action. Matching will michael@0: // continue with the following pattern. michael@0: U_ASSERT(*pCounter == maxCount); michael@0: break; michael@0: } michael@0: michael@0: if (*pCounter < minCount) { michael@0: // We haven't met the minimum number of matches yet. michael@0: // Loop back for another one. michael@0: fp->fPatIdx = opValue + 4; // Loop back. michael@0: } else { michael@0: // We do have the minimum number of matches. michael@0: michael@0: // If there is no upper bound on the loop iterations, check that the input index michael@0: // is progressing, and stop the loop if it is not. michael@0: if (maxCount == -1) { michael@0: int64_t *pLastInputIdx = &fp->fExtra[URX_VAL(initOp) + 1]; michael@0: if (fp->fInputIdx == *pLastInputIdx) { michael@0: break; michael@0: } michael@0: *pLastInputIdx = fp->fInputIdx; michael@0: } michael@0: michael@0: // Loop Continuation: we will fall into the pattern following the loop michael@0: // (non-greedy, don't execute loop body first), but first do michael@0: // a state save to the top of the loop, so that a match failure michael@0: // in the following pattern will try another iteration of the loop. michael@0: fp = StateSave(fp, opValue + 4, status); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: case URX_STO_SP: michael@0: U_ASSERT(opValue >= 0 && opValue < fPattern->fDataSize); michael@0: fData[opValue] = fStack->size(); michael@0: break; michael@0: michael@0: case URX_LD_SP: michael@0: { michael@0: U_ASSERT(opValue >= 0 && opValue < fPattern->fDataSize); michael@0: int32_t newStackSize = (int32_t)fData[opValue]; michael@0: U_ASSERT(newStackSize <= fStack->size()); michael@0: int64_t *newFP = fStack->getBuffer() + newStackSize - fFrameSize; michael@0: if (newFP == (int64_t *)fp) { michael@0: break; michael@0: } michael@0: int32_t i; michael@0: for (i=0; isetSize(newStackSize); michael@0: } michael@0: break; michael@0: michael@0: case URX_BACKREF: michael@0: { michael@0: U_ASSERT(opValue < fFrameSize); michael@0: int64_t groupStartIdx = fp->fExtra[opValue]; michael@0: int64_t groupEndIdx = fp->fExtra[opValue+1]; michael@0: U_ASSERT(groupStartIdx <= groupEndIdx); michael@0: if (groupStartIdx < 0) { michael@0: // This capture group has not participated in the match thus far, michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); // FAIL, no match. michael@0: break; michael@0: } michael@0: UTEXT_SETNATIVEINDEX(fAltInputText, groupStartIdx); michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: michael@0: // Note: if the capture group match was of an empty string the backref michael@0: // match succeeds. Verified by testing: Perl matches succeed michael@0: // in this case, so we do too. michael@0: michael@0: UBool success = TRUE; michael@0: for (;;) { michael@0: if (utext_getNativeIndex(fAltInputText) >= groupEndIdx) { michael@0: success = TRUE; michael@0: break; michael@0: } michael@0: if (utext_getNativeIndex(fInputText) >= fActiveLimit) { michael@0: success = FALSE; michael@0: fHitEnd = TRUE; michael@0: break; michael@0: } michael@0: UChar32 captureGroupChar = utext_next32(fAltInputText); michael@0: UChar32 inputChar = utext_next32(fInputText); michael@0: if (inputChar != captureGroupChar) { michael@0: success = FALSE; michael@0: break; michael@0: } michael@0: } michael@0: michael@0: if (success) { michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } else { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: michael@0: case URX_BACKREF_I: michael@0: { michael@0: U_ASSERT(opValue < fFrameSize); michael@0: int64_t groupStartIdx = fp->fExtra[opValue]; michael@0: int64_t groupEndIdx = fp->fExtra[opValue+1]; michael@0: U_ASSERT(groupStartIdx <= groupEndIdx); michael@0: if (groupStartIdx < 0) { michael@0: // This capture group has not participated in the match thus far, michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); // FAIL, no match. michael@0: break; michael@0: } michael@0: utext_setNativeIndex(fAltInputText, groupStartIdx); michael@0: utext_setNativeIndex(fInputText, fp->fInputIdx); michael@0: CaseFoldingUTextIterator captureGroupItr(*fAltInputText); michael@0: CaseFoldingUTextIterator inputItr(*fInputText); michael@0: michael@0: // Note: if the capture group match was of an empty string the backref michael@0: // match succeeds. Verified by testing: Perl matches succeed michael@0: // in this case, so we do too. michael@0: michael@0: UBool success = TRUE; michael@0: for (;;) { michael@0: if (!captureGroupItr.inExpansion() && utext_getNativeIndex(fAltInputText) >= groupEndIdx) { michael@0: success = TRUE; michael@0: break; michael@0: } michael@0: if (!inputItr.inExpansion() && utext_getNativeIndex(fInputText) >= fActiveLimit) { michael@0: success = FALSE; michael@0: fHitEnd = TRUE; michael@0: break; michael@0: } michael@0: UChar32 captureGroupChar = captureGroupItr.next(); michael@0: UChar32 inputChar = inputItr.next(); michael@0: if (inputChar != captureGroupChar) { michael@0: success = FALSE; michael@0: break; michael@0: } michael@0: } michael@0: michael@0: if (success && inputItr.inExpansion()) { michael@0: // We otained a match by consuming part of a string obtained from michael@0: // case-folding a single code point of the input text. michael@0: // This does not count as an overall match. michael@0: success = FALSE; michael@0: } michael@0: michael@0: if (success) { michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } else { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: michael@0: } michael@0: break; michael@0: michael@0: case URX_STO_INP_LOC: michael@0: { michael@0: U_ASSERT(opValue >= 0 && opValue < fFrameSize); michael@0: fp->fExtra[opValue] = fp->fInputIdx; michael@0: } michael@0: break; michael@0: michael@0: case URX_JMPX: michael@0: { michael@0: int32_t instrOperandLoc = (int32_t)fp->fPatIdx; michael@0: fp->fPatIdx += 1; michael@0: int32_t dataLoc = URX_VAL(pat[instrOperandLoc]); michael@0: U_ASSERT(dataLoc >= 0 && dataLoc < fFrameSize); michael@0: int64_t savedInputIdx = fp->fExtra[dataLoc]; michael@0: U_ASSERT(savedInputIdx <= fp->fInputIdx); michael@0: if (savedInputIdx < fp->fInputIdx) { michael@0: fp->fPatIdx = opValue; // JMP michael@0: } else { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); // FAIL, no progress in loop. michael@0: } michael@0: } michael@0: break; michael@0: michael@0: case URX_LA_START: michael@0: { michael@0: // Entering a lookahead block. michael@0: // Save Stack Ptr, Input Pos. michael@0: U_ASSERT(opValue>=0 && opValue+1fDataSize); michael@0: fData[opValue] = fStack->size(); michael@0: fData[opValue+1] = fp->fInputIdx; michael@0: fActiveStart = fLookStart; // Set the match region change for michael@0: fActiveLimit = fLookLimit; // transparent bounds. michael@0: } michael@0: break; michael@0: michael@0: case URX_LA_END: michael@0: { michael@0: // Leaving a look-ahead block. michael@0: // restore Stack Ptr, Input Pos to positions they had on entry to block. michael@0: U_ASSERT(opValue>=0 && opValue+1fDataSize); michael@0: int32_t stackSize = fStack->size(); michael@0: int32_t newStackSize =(int32_t)fData[opValue]; michael@0: U_ASSERT(stackSize >= newStackSize); michael@0: if (stackSize > newStackSize) { michael@0: // Copy the current top frame back to the new (cut back) top frame. michael@0: // This makes the capture groups from within the look-ahead michael@0: // expression available. michael@0: int64_t *newFP = fStack->getBuffer() + newStackSize - fFrameSize; michael@0: int32_t i; michael@0: for (i=0; isetSize(newStackSize); michael@0: } michael@0: fp->fInputIdx = fData[opValue+1]; michael@0: michael@0: // Restore the active region bounds in the input string; they may have michael@0: // been changed because of transparent bounds on a Region. michael@0: fActiveStart = fRegionStart; michael@0: fActiveLimit = fRegionLimit; michael@0: } michael@0: break; michael@0: michael@0: case URX_ONECHAR_I: michael@0: // Case insensitive one char. The char from the pattern is already case folded. michael@0: // Input text is not, but case folding the input can not reduce two or more code michael@0: // points to one. michael@0: if (fp->fInputIdx < fActiveLimit) { michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: michael@0: UChar32 c = UTEXT_NEXT32(fInputText); michael@0: if (u_foldCase(c, U_FOLD_CASE_DEFAULT) == opValue) { michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: break; michael@0: } michael@0: } else { michael@0: fHitEnd = TRUE; michael@0: } michael@0: michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: michael@0: case URX_STRING_I: michael@0: { michael@0: // Case-insensitive test input against a literal string. michael@0: // Strings require two slots in the compiled pattern, one for the michael@0: // offset to the string text, and one for the length. michael@0: // The compiled string has already been case folded. michael@0: { michael@0: const UChar *patternString = litText + opValue; michael@0: int32_t patternStringIdx = 0; michael@0: michael@0: op = (int32_t)pat[fp->fPatIdx]; michael@0: fp->fPatIdx++; michael@0: opType = URX_TYPE(op); michael@0: opValue = URX_VAL(op); michael@0: U_ASSERT(opType == URX_STRING_LEN); michael@0: int32_t patternStringLen = opValue; // Length of the string from the pattern. michael@0: michael@0: michael@0: UChar32 cPattern; michael@0: UChar32 cText; michael@0: UBool success = TRUE; michael@0: michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: CaseFoldingUTextIterator inputIterator(*fInputText); michael@0: while (patternStringIdx < patternStringLen) { michael@0: if (!inputIterator.inExpansion() && UTEXT_GETNATIVEINDEX(fInputText) >= fActiveLimit) { michael@0: success = FALSE; michael@0: fHitEnd = TRUE; michael@0: break; michael@0: } michael@0: U16_NEXT(patternString, patternStringIdx, patternStringLen, cPattern); michael@0: cText = inputIterator.next(); michael@0: if (cText != cPattern) { michael@0: success = FALSE; michael@0: break; michael@0: } michael@0: } michael@0: if (inputIterator.inExpansion()) { michael@0: success = FALSE; michael@0: } michael@0: michael@0: if (success) { michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } else { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: } michael@0: break; michael@0: michael@0: case URX_LB_START: michael@0: { michael@0: // Entering a look-behind block. michael@0: // Save Stack Ptr, Input Pos. michael@0: // TODO: implement transparent bounds. Ticket #6067 michael@0: U_ASSERT(opValue>=0 && opValue+1fDataSize); michael@0: fData[opValue] = fStack->size(); michael@0: fData[opValue+1] = fp->fInputIdx; michael@0: // Init the variable containing the start index for attempted matches. michael@0: fData[opValue+2] = -1; michael@0: // Save input string length, then reset to pin any matches to end at michael@0: // the current position. michael@0: fData[opValue+3] = fActiveLimit; michael@0: fActiveLimit = fp->fInputIdx; michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_LB_CONT: michael@0: { michael@0: // Positive Look-Behind, at top of loop checking for matches of LB expression michael@0: // at all possible input starting positions. michael@0: michael@0: // Fetch the min and max possible match lengths. They are the operands michael@0: // of this op in the pattern. michael@0: int32_t minML = (int32_t)pat[fp->fPatIdx++]; michael@0: int32_t maxML = (int32_t)pat[fp->fPatIdx++]; michael@0: U_ASSERT(minML <= maxML); michael@0: U_ASSERT(minML >= 0); michael@0: michael@0: // Fetch (from data) the last input index where a match was attempted. michael@0: U_ASSERT(opValue>=0 && opValue+1fDataSize); michael@0: int64_t *lbStartIdx = &fData[opValue+2]; michael@0: if (*lbStartIdx < 0) { michael@0: // First time through loop. michael@0: *lbStartIdx = fp->fInputIdx - minML; michael@0: } else { michael@0: // 2nd through nth time through the loop. michael@0: // Back up start position for match by one. michael@0: if (*lbStartIdx == 0) { michael@0: (*lbStartIdx)--; michael@0: } else { michael@0: UTEXT_SETNATIVEINDEX(fInputText, *lbStartIdx); michael@0: (void)UTEXT_PREVIOUS32(fInputText); michael@0: *lbStartIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } michael@0: } michael@0: michael@0: if (*lbStartIdx < 0 || *lbStartIdx < fp->fInputIdx - maxML) { michael@0: // We have tried all potential match starting points without michael@0: // getting a match. Backtrack out, and out of the michael@0: // Look Behind altogether. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: int64_t restoreInputLen = fData[opValue+3]; michael@0: U_ASSERT(restoreInputLen >= fActiveLimit); michael@0: U_ASSERT(restoreInputLen <= fInputLength); michael@0: fActiveLimit = restoreInputLen; michael@0: break; michael@0: } michael@0: michael@0: // Save state to this URX_LB_CONT op, so failure to match will repeat the loop. michael@0: // (successful match will fall off the end of the loop.) michael@0: fp = StateSave(fp, fp->fPatIdx-3, status); michael@0: fp->fInputIdx = *lbStartIdx; michael@0: } michael@0: break; michael@0: michael@0: case URX_LB_END: michael@0: // End of a look-behind block, after a successful match. michael@0: { michael@0: U_ASSERT(opValue>=0 && opValue+1fDataSize); michael@0: if (fp->fInputIdx != fActiveLimit) { michael@0: // The look-behind expression matched, but the match did not michael@0: // extend all the way to the point that we are looking behind from. michael@0: // FAIL out of here, which will take us back to the LB_CONT, which michael@0: // will retry the match starting at another position or fail michael@0: // the look-behind altogether, whichever is appropriate. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: // Look-behind match is good. Restore the orignal input string length, michael@0: // which had been truncated to pin the end of the lookbehind match to the michael@0: // position being looked-behind. michael@0: int64_t originalInputLen = fData[opValue+3]; michael@0: U_ASSERT(originalInputLen >= fActiveLimit); michael@0: U_ASSERT(originalInputLen <= fInputLength); michael@0: fActiveLimit = originalInputLen; michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_LBN_CONT: michael@0: { michael@0: // Negative Look-Behind, at top of loop checking for matches of LB expression michael@0: // at all possible input starting positions. michael@0: michael@0: // Fetch the extra parameters of this op. michael@0: int32_t minML = (int32_t)pat[fp->fPatIdx++]; michael@0: int32_t maxML = (int32_t)pat[fp->fPatIdx++]; michael@0: int32_t continueLoc = (int32_t)pat[fp->fPatIdx++]; michael@0: continueLoc = URX_VAL(continueLoc); michael@0: U_ASSERT(minML <= maxML); michael@0: U_ASSERT(minML >= 0); michael@0: U_ASSERT(continueLoc > fp->fPatIdx); michael@0: michael@0: // Fetch (from data) the last input index where a match was attempted. michael@0: U_ASSERT(opValue>=0 && opValue+1fDataSize); michael@0: int64_t *lbStartIdx = &fData[opValue+2]; michael@0: if (*lbStartIdx < 0) { michael@0: // First time through loop. michael@0: *lbStartIdx = fp->fInputIdx - minML; michael@0: } else { michael@0: // 2nd through nth time through the loop. michael@0: // Back up start position for match by one. michael@0: if (*lbStartIdx == 0) { michael@0: (*lbStartIdx)--; michael@0: } else { michael@0: UTEXT_SETNATIVEINDEX(fInputText, *lbStartIdx); michael@0: (void)UTEXT_PREVIOUS32(fInputText); michael@0: *lbStartIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } michael@0: } michael@0: michael@0: if (*lbStartIdx < 0 || *lbStartIdx < fp->fInputIdx - maxML) { michael@0: // We have tried all potential match starting points without michael@0: // getting a match, which means that the negative lookbehind as michael@0: // a whole has succeeded. Jump forward to the continue location michael@0: int64_t restoreInputLen = fData[opValue+3]; michael@0: U_ASSERT(restoreInputLen >= fActiveLimit); michael@0: U_ASSERT(restoreInputLen <= fInputLength); michael@0: fActiveLimit = restoreInputLen; michael@0: fp->fPatIdx = continueLoc; michael@0: break; michael@0: } michael@0: michael@0: // Save state to this URX_LB_CONT op, so failure to match will repeat the loop. michael@0: // (successful match will cause a FAIL out of the loop altogether.) michael@0: fp = StateSave(fp, fp->fPatIdx-4, status); michael@0: fp->fInputIdx = *lbStartIdx; michael@0: } michael@0: break; michael@0: michael@0: case URX_LBN_END: michael@0: // End of a negative look-behind block, after a successful match. michael@0: { michael@0: U_ASSERT(opValue>=0 && opValue+1fDataSize); michael@0: if (fp->fInputIdx != fActiveLimit) { michael@0: // The look-behind expression matched, but the match did not michael@0: // extend all the way to the point that we are looking behind from. michael@0: // FAIL out of here, which will take us back to the LB_CONT, which michael@0: // will retry the match starting at another position or succeed michael@0: // the look-behind altogether, whichever is appropriate. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: // Look-behind expression matched, which means look-behind test as michael@0: // a whole Fails michael@0: michael@0: // Restore the orignal input string length, which had been truncated michael@0: // inorder to pin the end of the lookbehind match michael@0: // to the position being looked-behind. michael@0: int64_t originalInputLen = fData[opValue+3]; michael@0: U_ASSERT(originalInputLen >= fActiveLimit); michael@0: U_ASSERT(originalInputLen <= fInputLength); michael@0: fActiveLimit = originalInputLen; michael@0: michael@0: // Restore original stack position, discarding any state saved michael@0: // by the successful pattern match. michael@0: U_ASSERT(opValue>=0 && opValue+1fDataSize); michael@0: int32_t newStackSize = (int32_t)fData[opValue]; michael@0: U_ASSERT(fStack->size() > newStackSize); michael@0: fStack->setSize(newStackSize); michael@0: michael@0: // FAIL, which will take control back to someplace michael@0: // prior to entering the look-behind test. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_LOOP_SR_I: michael@0: // Loop Initialization for the optimized implementation of michael@0: // [some character set]* michael@0: // This op scans through all matching input. michael@0: // The following LOOP_C op emulates stack unwinding if the following pattern fails. michael@0: { michael@0: U_ASSERT(opValue > 0 && opValue < sets->size()); michael@0: Regex8BitSet *s8 = &fPattern->fSets8[opValue]; michael@0: UnicodeSet *s = (UnicodeSet *)sets->elementAt(opValue); michael@0: michael@0: // Loop through input, until either the input is exhausted or michael@0: // we reach a character that is not a member of the set. michael@0: int64_t ix = fp->fInputIdx; michael@0: UTEXT_SETNATIVEINDEX(fInputText, ix); michael@0: for (;;) { michael@0: if (ix >= fActiveLimit) { michael@0: fHitEnd = TRUE; michael@0: break; michael@0: } michael@0: UChar32 c = UTEXT_NEXT32(fInputText); michael@0: if (c<256) { michael@0: if (s8->contains(c) == FALSE) { michael@0: break; michael@0: } michael@0: } else { michael@0: if (s->contains(c) == FALSE) { michael@0: break; michael@0: } michael@0: } michael@0: ix = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } michael@0: michael@0: // If there were no matching characters, skip over the loop altogether. michael@0: // The loop doesn't run at all, a * op always succeeds. michael@0: if (ix == fp->fInputIdx) { michael@0: fp->fPatIdx++; // skip the URX_LOOP_C op. michael@0: break; michael@0: } michael@0: michael@0: // Peek ahead in the compiled pattern, to the URX_LOOP_C that michael@0: // must follow. It's operand is the stack location michael@0: // that holds the starting input index for the match of this [set]* michael@0: int32_t loopcOp = (int32_t)pat[fp->fPatIdx]; michael@0: U_ASSERT(URX_TYPE(loopcOp) == URX_LOOP_C); michael@0: int32_t stackLoc = URX_VAL(loopcOp); michael@0: U_ASSERT(stackLoc >= 0 && stackLoc < fFrameSize); michael@0: fp->fExtra[stackLoc] = fp->fInputIdx; michael@0: fp->fInputIdx = ix; michael@0: michael@0: // Save State to the URX_LOOP_C op that follows this one, michael@0: // so that match failures in the following code will return to there. michael@0: // Then bump the pattern idx so the LOOP_C is skipped on the way out of here. michael@0: fp = StateSave(fp, fp->fPatIdx, status); michael@0: fp->fPatIdx++; michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_LOOP_DOT_I: michael@0: // Loop Initialization for the optimized implementation of .* michael@0: // This op scans through all remaining input. michael@0: // The following LOOP_C op emulates stack unwinding if the following pattern fails. michael@0: { michael@0: // Loop through input until the input is exhausted (we reach an end-of-line) michael@0: // In DOTALL mode, we can just go straight to the end of the input. michael@0: int64_t ix; michael@0: if ((opValue & 1) == 1) { michael@0: // Dot-matches-All mode. Jump straight to the end of the string. michael@0: ix = fActiveLimit; michael@0: fHitEnd = TRUE; michael@0: } else { michael@0: // NOT DOT ALL mode. Line endings do not match '.' michael@0: // Scan forward until a line ending or end of input. michael@0: ix = fp->fInputIdx; michael@0: UTEXT_SETNATIVEINDEX(fInputText, ix); michael@0: for (;;) { michael@0: if (ix >= fActiveLimit) { michael@0: fHitEnd = TRUE; michael@0: break; michael@0: } michael@0: UChar32 c = UTEXT_NEXT32(fInputText); michael@0: if ((c & 0x7f) <= 0x29) { // Fast filter of non-new-line-s michael@0: if ((c == 0x0a) || // 0x0a is newline in both modes. michael@0: (((opValue & 2) == 0) && // IF not UNIX_LINES mode michael@0: (c<=0x0d && c>=0x0a)) || c==0x85 ||c==0x2028 || c==0x2029) { michael@0: // char is a line ending. Exit the scanning loop. michael@0: break; michael@0: } michael@0: } michael@0: ix = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } michael@0: } michael@0: michael@0: // If there were no matching characters, skip over the loop altogether. michael@0: // The loop doesn't run at all, a * op always succeeds. michael@0: if (ix == fp->fInputIdx) { michael@0: fp->fPatIdx++; // skip the URX_LOOP_C op. michael@0: break; michael@0: } michael@0: michael@0: // Peek ahead in the compiled pattern, to the URX_LOOP_C that michael@0: // must follow. It's operand is the stack location michael@0: // that holds the starting input index for the match of this .* michael@0: int32_t loopcOp = (int32_t)pat[fp->fPatIdx]; michael@0: U_ASSERT(URX_TYPE(loopcOp) == URX_LOOP_C); michael@0: int32_t stackLoc = URX_VAL(loopcOp); michael@0: U_ASSERT(stackLoc >= 0 && stackLoc < fFrameSize); michael@0: fp->fExtra[stackLoc] = fp->fInputIdx; michael@0: fp->fInputIdx = ix; michael@0: michael@0: // Save State to the URX_LOOP_C op that follows this one, michael@0: // so that match failures in the following code will return to there. michael@0: // Then bump the pattern idx so the LOOP_C is skipped on the way out of here. michael@0: fp = StateSave(fp, fp->fPatIdx, status); michael@0: fp->fPatIdx++; michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_LOOP_C: michael@0: { michael@0: U_ASSERT(opValue>=0 && opValuefExtra[opValue]; michael@0: U_ASSERT(backSearchIndex <= fp->fInputIdx); michael@0: if (backSearchIndex == fp->fInputIdx) { michael@0: // We've backed up the input idx to the point that the loop started. michael@0: // The loop is done. Leave here without saving state. michael@0: // Subsequent failures won't come back here. michael@0: break; michael@0: } michael@0: // Set up for the next iteration of the loop, with input index michael@0: // backed up by one from the last time through, michael@0: // and a state save to this instruction in case the following code fails again. michael@0: // (We're going backwards because this loop emulates stack unwinding, not michael@0: // the initial scan forward.) michael@0: U_ASSERT(fp->fInputIdx > 0); michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: UChar32 prevC = UTEXT_PREVIOUS32(fInputText); michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: michael@0: UChar32 twoPrevC = UTEXT_PREVIOUS32(fInputText); michael@0: if (prevC == 0x0a && michael@0: fp->fInputIdx > backSearchIndex && michael@0: twoPrevC == 0x0d) { michael@0: int32_t prevOp = (int32_t)pat[fp->fPatIdx-2]; michael@0: if (URX_TYPE(prevOp) == URX_LOOP_DOT_I) { michael@0: // .*, stepping back over CRLF pair. michael@0: fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText); michael@0: } michael@0: } michael@0: michael@0: michael@0: fp = StateSave(fp, fp->fPatIdx-1, status); michael@0: } michael@0: break; michael@0: michael@0: michael@0: michael@0: default: michael@0: // Trouble. The compiled pattern contains an entry with an michael@0: // unrecognized type tag. michael@0: U_ASSERT(FALSE); michael@0: } michael@0: michael@0: if (U_FAILURE(status)) { michael@0: isMatch = FALSE; michael@0: break; michael@0: } michael@0: } michael@0: michael@0: breakFromLoop: michael@0: fMatch = isMatch; michael@0: if (isMatch) { michael@0: fLastMatchEnd = fMatchEnd; michael@0: fMatchStart = startIdx; michael@0: fMatchEnd = fp->fInputIdx; michael@0: if (fTraceDebug) { michael@0: REGEX_RUN_DEBUG_PRINTF(("Match. start=%ld end=%ld\n\n", fMatchStart, fMatchEnd)); michael@0: } michael@0: } michael@0: else michael@0: { michael@0: if (fTraceDebug) { michael@0: REGEX_RUN_DEBUG_PRINTF(("No match\n\n")); michael@0: } michael@0: } michael@0: michael@0: fFrame = fp; // The active stack frame when the engine stopped. michael@0: // Contains the capture group results that we need to michael@0: // access later. michael@0: return; michael@0: } michael@0: michael@0: michael@0: //-------------------------------------------------------------------------------- michael@0: // michael@0: // MatchChunkAt This is the actual matching engine. Like MatchAt, but with the michael@0: // assumption that the entire string is available in the UText's michael@0: // chunk buffer. For now, that means we can use int32_t indexes, michael@0: // except for anything that needs to be saved (like group starts michael@0: // and ends). michael@0: // michael@0: // startIdx: begin matching a this index. michael@0: // toEnd: if true, match must extend to end of the input region michael@0: // michael@0: //-------------------------------------------------------------------------------- michael@0: void RegexMatcher::MatchChunkAt(int32_t startIdx, UBool toEnd, UErrorCode &status) { michael@0: UBool isMatch = FALSE; // True if the we have a match. michael@0: michael@0: int32_t backSearchIndex = INT32_MAX; // used after greedy single-character matches for searching backwards michael@0: michael@0: int32_t op; // Operation from the compiled pattern, split into michael@0: int32_t opType; // the opcode michael@0: int32_t opValue; // and the operand value. michael@0: michael@0: #ifdef REGEX_RUN_DEBUG michael@0: if (fTraceDebug) michael@0: { michael@0: printf("MatchAt(startIdx=%d)\n", startIdx); michael@0: printf("Original Pattern: "); michael@0: UChar32 c = utext_next32From(fPattern->fPattern, 0); michael@0: while (c != U_SENTINEL) { michael@0: if (c<32 || c>256) { michael@0: c = '.'; michael@0: } michael@0: REGEX_DUMP_DEBUG_PRINTF(("%c", c)); michael@0: michael@0: c = UTEXT_NEXT32(fPattern->fPattern); michael@0: } michael@0: printf("\n"); michael@0: printf("Input String: "); michael@0: c = utext_next32From(fInputText, 0); michael@0: while (c != U_SENTINEL) { michael@0: if (c<32 || c>256) { michael@0: c = '.'; michael@0: } michael@0: printf("%c", c); michael@0: michael@0: c = UTEXT_NEXT32(fInputText); michael@0: } michael@0: printf("\n"); michael@0: printf("\n"); michael@0: } michael@0: #endif michael@0: michael@0: if (U_FAILURE(status)) { michael@0: return; michael@0: } michael@0: michael@0: // Cache frequently referenced items from the compiled pattern michael@0: // michael@0: int64_t *pat = fPattern->fCompiledPat->getBuffer(); michael@0: michael@0: const UChar *litText = fPattern->fLiteralText.getBuffer(); michael@0: UVector *sets = fPattern->fSets; michael@0: michael@0: const UChar *inputBuf = fInputText->chunkContents; michael@0: michael@0: fFrameSize = fPattern->fFrameSize; michael@0: REStackFrame *fp = resetStack(); michael@0: michael@0: fp->fPatIdx = 0; michael@0: fp->fInputIdx = startIdx; michael@0: michael@0: // Zero out the pattern's static data michael@0: int32_t i; michael@0: for (i = 0; ifDataSize; i++) { michael@0: fData[i] = 0; michael@0: } michael@0: michael@0: // michael@0: // Main loop for interpreting the compiled pattern. michael@0: // One iteration of the loop per pattern operation performed. michael@0: // michael@0: for (;;) { michael@0: #if 0 michael@0: if (_heapchk() != _HEAPOK) { michael@0: fprintf(stderr, "Heap Trouble\n"); michael@0: } michael@0: #endif michael@0: michael@0: op = (int32_t)pat[fp->fPatIdx]; michael@0: opType = URX_TYPE(op); michael@0: opValue = URX_VAL(op); michael@0: #ifdef REGEX_RUN_DEBUG michael@0: if (fTraceDebug) { michael@0: UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx); michael@0: printf("inputIdx=%ld inputChar=%x sp=%3ld activeLimit=%ld ", fp->fInputIdx, michael@0: UTEXT_CURRENT32(fInputText), (int64_t *)fp-fStack->getBuffer(), fActiveLimit); michael@0: fPattern->dumpOp(fp->fPatIdx); michael@0: } michael@0: #endif michael@0: fp->fPatIdx++; michael@0: michael@0: switch (opType) { michael@0: michael@0: michael@0: case URX_NOP: michael@0: break; michael@0: michael@0: michael@0: case URX_BACKTRACK: michael@0: // Force a backtrack. In some circumstances, the pattern compiler michael@0: // will notice that the pattern can't possibly match anything, and will michael@0: // emit one of these at that point. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: michael@0: michael@0: case URX_ONECHAR: michael@0: if (fp->fInputIdx < fActiveLimit) { michael@0: UChar32 c; michael@0: U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c); michael@0: if (c == opValue) { michael@0: break; michael@0: } michael@0: } else { michael@0: fHitEnd = TRUE; michael@0: } michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: michael@0: michael@0: case URX_STRING: michael@0: { michael@0: // Test input against a literal string. michael@0: // Strings require two slots in the compiled pattern, one for the michael@0: // offset to the string text, and one for the length. michael@0: int32_t stringStartIdx = opValue; michael@0: int32_t stringLen; michael@0: michael@0: op = (int32_t)pat[fp->fPatIdx]; // Fetch the second operand michael@0: fp->fPatIdx++; michael@0: opType = URX_TYPE(op); michael@0: stringLen = URX_VAL(op); michael@0: U_ASSERT(opType == URX_STRING_LEN); michael@0: U_ASSERT(stringLen >= 2); michael@0: michael@0: const UChar * pInp = inputBuf + fp->fInputIdx; michael@0: const UChar * pInpLimit = inputBuf + fActiveLimit; michael@0: const UChar * pPat = litText+stringStartIdx; michael@0: const UChar * pEnd = pInp + stringLen; michael@0: UBool success = TRUE; michael@0: while (pInp < pEnd) { michael@0: if (pInp >= pInpLimit) { michael@0: fHitEnd = TRUE; michael@0: success = FALSE; michael@0: break; michael@0: } michael@0: if (*pInp++ != *pPat++) { michael@0: success = FALSE; michael@0: break; michael@0: } michael@0: } michael@0: michael@0: if (success) { michael@0: fp->fInputIdx += stringLen; michael@0: } else { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_STATE_SAVE: michael@0: fp = StateSave(fp, opValue, status); michael@0: break; michael@0: michael@0: michael@0: case URX_END: michael@0: // The match loop will exit via this path on a successful match, michael@0: // when we reach the end of the pattern. michael@0: if (toEnd && fp->fInputIdx != fActiveLimit) { michael@0: // The pattern matched, but not to the end of input. Try some more. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: isMatch = TRUE; michael@0: goto breakFromLoop; michael@0: michael@0: // Start and End Capture stack frame variables are laid out out like this: michael@0: // fp->fExtra[opValue] - The start of a completed capture group michael@0: // opValue+1 - The end of a completed capture group michael@0: // opValue+2 - the start of a capture group whose end michael@0: // has not yet been reached (and might not ever be). michael@0: case URX_START_CAPTURE: michael@0: U_ASSERT(opValue >= 0 && opValue < fFrameSize-3); michael@0: fp->fExtra[opValue+2] = fp->fInputIdx; michael@0: break; michael@0: michael@0: michael@0: case URX_END_CAPTURE: michael@0: U_ASSERT(opValue >= 0 && opValue < fFrameSize-3); michael@0: U_ASSERT(fp->fExtra[opValue+2] >= 0); // Start pos for this group must be set. michael@0: fp->fExtra[opValue] = fp->fExtra[opValue+2]; // Tentative start becomes real. michael@0: fp->fExtra[opValue+1] = fp->fInputIdx; // End position michael@0: U_ASSERT(fp->fExtra[opValue] <= fp->fExtra[opValue+1]); michael@0: break; michael@0: michael@0: michael@0: case URX_DOLLAR: // $, test for End of line michael@0: // or for position before new line at end of input michael@0: if (fp->fInputIdx < fAnchorLimit-2) { michael@0: // We are no where near the end of input. Fail. michael@0: // This is the common case. Keep it first. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: if (fp->fInputIdx >= fAnchorLimit) { michael@0: // We really are at the end of input. Success. michael@0: fHitEnd = TRUE; michael@0: fRequireEnd = TRUE; michael@0: break; michael@0: } michael@0: michael@0: // If we are positioned just before a new-line that is located at the michael@0: // end of input, succeed. michael@0: if (fp->fInputIdx == fAnchorLimit-1) { michael@0: UChar32 c; michael@0: U16_GET(inputBuf, fAnchorStart, fp->fInputIdx, fAnchorLimit, c); michael@0: michael@0: if ((c>=0x0a && c<=0x0d) || c==0x85 || c==0x2028 || c==0x2029) { michael@0: if ( !(c==0x0a && fp->fInputIdx>fAnchorStart && inputBuf[fp->fInputIdx-1]==0x0d)) { michael@0: // At new-line at end of input. Success michael@0: fHitEnd = TRUE; michael@0: fRequireEnd = TRUE; michael@0: break; michael@0: } michael@0: } michael@0: } else if (fp->fInputIdx == fAnchorLimit-2 && michael@0: inputBuf[fp->fInputIdx]==0x0d && inputBuf[fp->fInputIdx+1]==0x0a) { michael@0: fHitEnd = TRUE; michael@0: fRequireEnd = TRUE; michael@0: break; // At CR/LF at end of input. Success michael@0: } michael@0: michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: michael@0: break; michael@0: michael@0: michael@0: case URX_DOLLAR_D: // $, test for End of Line, in UNIX_LINES mode. michael@0: if (fp->fInputIdx >= fAnchorLimit-1) { michael@0: // Either at the last character of input, or off the end. michael@0: if (fp->fInputIdx == fAnchorLimit-1) { michael@0: // At last char of input. Success if it's a new line. michael@0: if (inputBuf[fp->fInputIdx] == 0x0a) { michael@0: fHitEnd = TRUE; michael@0: fRequireEnd = TRUE; michael@0: break; michael@0: } michael@0: } else { michael@0: // Off the end of input. Success. michael@0: fHitEnd = TRUE; michael@0: fRequireEnd = TRUE; michael@0: break; michael@0: } michael@0: } michael@0: michael@0: // Not at end of input. Back-track out. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: michael@0: michael@0: case URX_DOLLAR_M: // $, test for End of line in multi-line mode michael@0: { michael@0: if (fp->fInputIdx >= fAnchorLimit) { michael@0: // We really are at the end of input. Success. michael@0: fHitEnd = TRUE; michael@0: fRequireEnd = TRUE; michael@0: break; michael@0: } michael@0: // If we are positioned just before a new-line, succeed. michael@0: // It makes no difference where the new-line is within the input. michael@0: UChar32 c = inputBuf[fp->fInputIdx]; michael@0: if ((c>=0x0a && c<=0x0d) || c==0x85 ||c==0x2028 || c==0x2029) { michael@0: // At a line end, except for the odd chance of being in the middle of a CR/LF sequence michael@0: // In multi-line mode, hitting a new-line just before the end of input does not michael@0: // set the hitEnd or requireEnd flags michael@0: if ( !(c==0x0a && fp->fInputIdx>fAnchorStart && inputBuf[fp->fInputIdx-1]==0x0d)) { michael@0: break; michael@0: } michael@0: } michael@0: // not at a new line. Fail. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_DOLLAR_MD: // $, test for End of line in multi-line and UNIX_LINES mode michael@0: { michael@0: if (fp->fInputIdx >= fAnchorLimit) { michael@0: // We really are at the end of input. Success. michael@0: fHitEnd = TRUE; michael@0: fRequireEnd = TRUE; // Java set requireEnd in this case, even though michael@0: break; // adding a new-line would not lose the match. michael@0: } michael@0: // If we are not positioned just before a new-line, the test fails; backtrack out. michael@0: // It makes no difference where the new-line is within the input. michael@0: if (inputBuf[fp->fInputIdx] != 0x0a) { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_CARET: // ^, test for start of line michael@0: if (fp->fInputIdx != fAnchorStart) { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_CARET_M: // ^, test for start of line in mulit-line mode michael@0: { michael@0: if (fp->fInputIdx == fAnchorStart) { michael@0: // We are at the start input. Success. michael@0: break; michael@0: } michael@0: // Check whether character just before the current pos is a new-line michael@0: // unless we are at the end of input michael@0: UChar c = inputBuf[fp->fInputIdx - 1]; michael@0: if ((fp->fInputIdx < fAnchorLimit) && michael@0: ((c<=0x0d && c>=0x0a) || c==0x85 ||c==0x2028 || c==0x2029)) { michael@0: // It's a new-line. ^ is true. Success. michael@0: // TODO: what should be done with positions between a CR and LF? michael@0: break; michael@0: } michael@0: // Not at the start of a line. Fail. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_CARET_M_UNIX: // ^, test for start of line in mulit-line + Unix-line mode michael@0: { michael@0: U_ASSERT(fp->fInputIdx >= fAnchorStart); michael@0: if (fp->fInputIdx <= fAnchorStart) { michael@0: // We are at the start input. Success. michael@0: break; michael@0: } michael@0: // Check whether character just before the current pos is a new-line michael@0: U_ASSERT(fp->fInputIdx <= fAnchorLimit); michael@0: UChar c = inputBuf[fp->fInputIdx - 1]; michael@0: if (c != 0x0a) { michael@0: // Not at the start of a line. Back-track out. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: case URX_BACKSLASH_B: // Test for word boundaries michael@0: { michael@0: UBool success = isChunkWordBoundary((int32_t)fp->fInputIdx); michael@0: success ^= (UBool)(opValue != 0); // flip sense for \B michael@0: if (!success) { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_BACKSLASH_BU: // Test for word boundaries, Unicode-style michael@0: { michael@0: UBool success = isUWordBoundary(fp->fInputIdx); michael@0: success ^= (UBool)(opValue != 0); // flip sense for \B michael@0: if (!success) { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_BACKSLASH_D: // Test for decimal digit michael@0: { michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: fHitEnd = TRUE; michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: UChar32 c; michael@0: U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c); michael@0: int8_t ctype = u_charType(c); // TODO: make a unicode set for this. Will be faster. michael@0: UBool success = (ctype == U_DECIMAL_DIGIT_NUMBER); michael@0: success ^= (UBool)(opValue != 0); // flip sense for \D michael@0: if (!success) { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_BACKSLASH_G: // Test for position at end of previous match michael@0: if (!((fMatch && fp->fInputIdx==fMatchEnd) || (fMatch==FALSE && fp->fInputIdx==fActiveStart))) { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_BACKSLASH_X: michael@0: // Match a Grapheme, as defined by Unicode TR 29. michael@0: // Differs slightly from Perl, which consumes combining marks independently michael@0: // of context. michael@0: { michael@0: michael@0: // Fail if at end of input michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: fHitEnd = TRUE; michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: // Examine (and consume) the current char. michael@0: // Dispatch into a little state machine, based on the char. michael@0: UChar32 c; michael@0: U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c); michael@0: UnicodeSet **sets = fPattern->fStaticSets; michael@0: if (sets[URX_GC_NORMAL]->contains(c)) goto GC_Extend; michael@0: if (sets[URX_GC_CONTROL]->contains(c)) goto GC_Control; michael@0: if (sets[URX_GC_L]->contains(c)) goto GC_L; michael@0: if (sets[URX_GC_LV]->contains(c)) goto GC_V; michael@0: if (sets[URX_GC_LVT]->contains(c)) goto GC_T; michael@0: if (sets[URX_GC_V]->contains(c)) goto GC_V; michael@0: if (sets[URX_GC_T]->contains(c)) goto GC_T; michael@0: goto GC_Extend; michael@0: michael@0: michael@0: michael@0: GC_L: michael@0: if (fp->fInputIdx >= fActiveLimit) goto GC_Done; michael@0: U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c); michael@0: if (sets[URX_GC_L]->contains(c)) goto GC_L; michael@0: if (sets[URX_GC_LV]->contains(c)) goto GC_V; michael@0: if (sets[URX_GC_LVT]->contains(c)) goto GC_T; michael@0: if (sets[URX_GC_V]->contains(c)) goto GC_V; michael@0: U16_PREV(inputBuf, 0, fp->fInputIdx, c); michael@0: goto GC_Extend; michael@0: michael@0: GC_V: michael@0: if (fp->fInputIdx >= fActiveLimit) goto GC_Done; michael@0: U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c); michael@0: if (sets[URX_GC_V]->contains(c)) goto GC_V; michael@0: if (sets[URX_GC_T]->contains(c)) goto GC_T; michael@0: U16_PREV(inputBuf, 0, fp->fInputIdx, c); michael@0: goto GC_Extend; michael@0: michael@0: GC_T: michael@0: if (fp->fInputIdx >= fActiveLimit) goto GC_Done; michael@0: U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c); michael@0: if (sets[URX_GC_T]->contains(c)) goto GC_T; michael@0: U16_PREV(inputBuf, 0, fp->fInputIdx, c); michael@0: goto GC_Extend; michael@0: michael@0: GC_Extend: michael@0: // Combining characters are consumed here michael@0: for (;;) { michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: break; michael@0: } michael@0: U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c); michael@0: if (sets[URX_GC_EXTEND]->contains(c) == FALSE) { michael@0: U16_BACK_1(inputBuf, 0, fp->fInputIdx); michael@0: break; michael@0: } michael@0: } michael@0: goto GC_Done; michael@0: michael@0: GC_Control: michael@0: // Most control chars stand alone (don't combine with combining chars), michael@0: // except for that CR/LF sequence is a single grapheme cluster. michael@0: if (c == 0x0d && fp->fInputIdx < fActiveLimit && inputBuf[fp->fInputIdx] == 0x0a) { michael@0: fp->fInputIdx++; michael@0: } michael@0: michael@0: GC_Done: michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: fHitEnd = TRUE; michael@0: } michael@0: break; michael@0: } michael@0: michael@0: michael@0: michael@0: michael@0: case URX_BACKSLASH_Z: // Test for end of Input michael@0: if (fp->fInputIdx < fAnchorLimit) { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } else { michael@0: fHitEnd = TRUE; michael@0: fRequireEnd = TRUE; michael@0: } michael@0: break; michael@0: michael@0: michael@0: michael@0: case URX_STATIC_SETREF: michael@0: { michael@0: // Test input character against one of the predefined sets michael@0: // (Word Characters, for example) michael@0: // The high bit of the op value is a flag for the match polarity. michael@0: // 0: success if input char is in set. michael@0: // 1: success if input char is not in set. michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: fHitEnd = TRUE; michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: UBool success = ((opValue & URX_NEG_SET) == URX_NEG_SET); michael@0: opValue &= ~URX_NEG_SET; michael@0: U_ASSERT(opValue > 0 && opValue < URX_LAST_SET); michael@0: michael@0: UChar32 c; michael@0: U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c); michael@0: if (c < 256) { michael@0: Regex8BitSet *s8 = &fPattern->fStaticSets8[opValue]; michael@0: if (s8->contains(c)) { michael@0: success = !success; michael@0: } michael@0: } else { michael@0: const UnicodeSet *s = fPattern->fStaticSets[opValue]; michael@0: if (s->contains(c)) { michael@0: success = !success; michael@0: } michael@0: } michael@0: if (!success) { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_STAT_SETREF_N: michael@0: { michael@0: // Test input character for NOT being a member of one of michael@0: // the predefined sets (Word Characters, for example) michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: fHitEnd = TRUE; michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: U_ASSERT(opValue > 0 && opValue < URX_LAST_SET); michael@0: michael@0: UChar32 c; michael@0: U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c); michael@0: if (c < 256) { michael@0: Regex8BitSet *s8 = &fPattern->fStaticSets8[opValue]; michael@0: if (s8->contains(c) == FALSE) { michael@0: break; michael@0: } michael@0: } else { michael@0: const UnicodeSet *s = fPattern->fStaticSets[opValue]; michael@0: if (s->contains(c) == FALSE) { michael@0: break; michael@0: } michael@0: } michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_SETREF: michael@0: { michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: fHitEnd = TRUE; michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: U_ASSERT(opValue > 0 && opValue < sets->size()); michael@0: michael@0: // There is input left. Pick up one char and test it for set membership. michael@0: UChar32 c; michael@0: U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c); michael@0: if (c<256) { michael@0: Regex8BitSet *s8 = &fPattern->fSets8[opValue]; michael@0: if (s8->contains(c)) { michael@0: // The character is in the set. A Match. michael@0: break; michael@0: } michael@0: } else { michael@0: UnicodeSet *s = (UnicodeSet *)sets->elementAt(opValue); michael@0: if (s->contains(c)) { michael@0: // The character is in the set. A Match. michael@0: break; michael@0: } michael@0: } michael@0: michael@0: // the character wasn't in the set. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_DOTANY: michael@0: { michael@0: // . matches anything, but stops at end-of-line. michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: // At end of input. Match failed. Backtrack out. michael@0: fHitEnd = TRUE; michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: // There is input left. Advance over one char, unless we've hit end-of-line michael@0: UChar32 c; michael@0: U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c); michael@0: if (((c & 0x7f) <= 0x29) && // First quickly bypass as many chars as possible michael@0: ((c<=0x0d && c>=0x0a) || c==0x85 ||c==0x2028 || c==0x2029)) { michael@0: // End of line in normal mode. . does not match. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_DOTANY_ALL: michael@0: { michael@0: // . in dot-matches-all (including new lines) mode michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: // At end of input. Match failed. Backtrack out. michael@0: fHitEnd = TRUE; michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: // There is input left. Advance over one char, except if we are michael@0: // at a cr/lf, advance over both of them. michael@0: UChar32 c; michael@0: U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c); michael@0: if (c==0x0d && fp->fInputIdx < fActiveLimit) { michael@0: // In the case of a CR/LF, we need to advance over both. michael@0: if (inputBuf[fp->fInputIdx] == 0x0a) { michael@0: U16_FWD_1(inputBuf, fp->fInputIdx, fActiveLimit); michael@0: } michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_DOTANY_UNIX: michael@0: { michael@0: // '.' operator, matches all, but stops at end-of-line. michael@0: // UNIX_LINES mode, so 0x0a is the only recognized line ending. michael@0: if (fp->fInputIdx >= fActiveLimit) { michael@0: // At end of input. Match failed. Backtrack out. michael@0: fHitEnd = TRUE; michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: // There is input left. Advance over one char, unless we've hit end-of-line michael@0: UChar32 c; michael@0: U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c); michael@0: if (c == 0x0a) { michael@0: // End of line in normal mode. '.' does not match the \n michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_JMP: michael@0: fp->fPatIdx = opValue; michael@0: break; michael@0: michael@0: case URX_FAIL: michael@0: isMatch = FALSE; michael@0: goto breakFromLoop; michael@0: michael@0: case URX_JMP_SAV: michael@0: U_ASSERT(opValue < fPattern->fCompiledPat->size()); michael@0: fp = StateSave(fp, fp->fPatIdx, status); // State save to loc following current michael@0: fp->fPatIdx = opValue; // Then JMP. michael@0: break; michael@0: michael@0: case URX_JMP_SAV_X: michael@0: // This opcode is used with (x)+, when x can match a zero length string. michael@0: // Same as JMP_SAV, except conditional on the match having made forward progress. michael@0: // Destination of the JMP must be a URX_STO_INP_LOC, from which we get the michael@0: // data address of the input position at the start of the loop. michael@0: { michael@0: U_ASSERT(opValue > 0 && opValue < fPattern->fCompiledPat->size()); michael@0: int32_t stoOp = (int32_t)pat[opValue-1]; michael@0: U_ASSERT(URX_TYPE(stoOp) == URX_STO_INP_LOC); michael@0: int32_t frameLoc = URX_VAL(stoOp); michael@0: U_ASSERT(frameLoc >= 0 && frameLoc < fFrameSize); michael@0: int32_t prevInputIdx = (int32_t)fp->fExtra[frameLoc]; michael@0: U_ASSERT(prevInputIdx <= fp->fInputIdx); michael@0: if (prevInputIdx < fp->fInputIdx) { michael@0: // The match did make progress. Repeat the loop. michael@0: fp = StateSave(fp, fp->fPatIdx, status); // State save to loc following current michael@0: fp->fPatIdx = opValue; michael@0: fp->fExtra[frameLoc] = fp->fInputIdx; michael@0: } michael@0: // If the input position did not advance, we do nothing here, michael@0: // execution will fall out of the loop. michael@0: } michael@0: break; michael@0: michael@0: case URX_CTR_INIT: michael@0: { michael@0: U_ASSERT(opValue >= 0 && opValue < fFrameSize-2); michael@0: fp->fExtra[opValue] = 0; // Set the loop counter variable to zero michael@0: michael@0: // Pick up the three extra operands that CTR_INIT has, and michael@0: // skip the pattern location counter past michael@0: int32_t instrOperandLoc = (int32_t)fp->fPatIdx; michael@0: fp->fPatIdx += 3; michael@0: int32_t loopLoc = URX_VAL(pat[instrOperandLoc]); michael@0: int32_t minCount = (int32_t)pat[instrOperandLoc+1]; michael@0: int32_t maxCount = (int32_t)pat[instrOperandLoc+2]; michael@0: U_ASSERT(minCount>=0); michael@0: U_ASSERT(maxCount>=minCount || maxCount==-1); michael@0: U_ASSERT(loopLoc>=fp->fPatIdx); michael@0: michael@0: if (minCount == 0) { michael@0: fp = StateSave(fp, loopLoc+1, status); michael@0: } michael@0: if (maxCount == -1) { michael@0: fp->fExtra[opValue+1] = fp->fInputIdx; // For loop breaking. michael@0: } else if (maxCount == 0) { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: case URX_CTR_LOOP: michael@0: { michael@0: U_ASSERT(opValue>0 && opValue < fp->fPatIdx-2); michael@0: int32_t initOp = (int32_t)pat[opValue]; michael@0: U_ASSERT(URX_TYPE(initOp) == URX_CTR_INIT); michael@0: int64_t *pCounter = &fp->fExtra[URX_VAL(initOp)]; michael@0: int32_t minCount = (int32_t)pat[opValue+2]; michael@0: int32_t maxCount = (int32_t)pat[opValue+3]; michael@0: (*pCounter)++; michael@0: if ((uint64_t)*pCounter >= (uint32_t)maxCount && maxCount != -1) { michael@0: U_ASSERT(*pCounter == maxCount); michael@0: break; michael@0: } michael@0: if (*pCounter >= minCount) { michael@0: if (maxCount == -1) { michael@0: // Loop has no hard upper bound. michael@0: // Check that it is progressing through the input, break if it is not. michael@0: int64_t *pLastInputIdx = &fp->fExtra[URX_VAL(initOp) + 1]; michael@0: if (fp->fInputIdx == *pLastInputIdx) { michael@0: break; michael@0: } else { michael@0: *pLastInputIdx = fp->fInputIdx; michael@0: } michael@0: } michael@0: fp = StateSave(fp, fp->fPatIdx, status); michael@0: } michael@0: fp->fPatIdx = opValue + 4; // Loop back. michael@0: } michael@0: break; michael@0: michael@0: case URX_CTR_INIT_NG: michael@0: { michael@0: // Initialize a non-greedy loop michael@0: U_ASSERT(opValue >= 0 && opValue < fFrameSize-2); michael@0: fp->fExtra[opValue] = 0; // Set the loop counter variable to zero michael@0: michael@0: // Pick up the three extra operands that CTR_INIT_NG has, and michael@0: // skip the pattern location counter past michael@0: int32_t instrOperandLoc = (int32_t)fp->fPatIdx; michael@0: fp->fPatIdx += 3; michael@0: int32_t loopLoc = URX_VAL(pat[instrOperandLoc]); michael@0: int32_t minCount = (int32_t)pat[instrOperandLoc+1]; michael@0: int32_t maxCount = (int32_t)pat[instrOperandLoc+2]; michael@0: U_ASSERT(minCount>=0); michael@0: U_ASSERT(maxCount>=minCount || maxCount==-1); michael@0: U_ASSERT(loopLoc>fp->fPatIdx); michael@0: if (maxCount == -1) { michael@0: fp->fExtra[opValue+1] = fp->fInputIdx; // Save initial input index for loop breaking. michael@0: } michael@0: michael@0: if (minCount == 0) { michael@0: if (maxCount != 0) { michael@0: fp = StateSave(fp, fp->fPatIdx, status); michael@0: } michael@0: fp->fPatIdx = loopLoc+1; // Continue with stuff after repeated block michael@0: } michael@0: } michael@0: break; michael@0: michael@0: case URX_CTR_LOOP_NG: michael@0: { michael@0: // Non-greedy {min, max} loops michael@0: U_ASSERT(opValue>0 && opValue < fp->fPatIdx-2); michael@0: int32_t initOp = (int32_t)pat[opValue]; michael@0: U_ASSERT(URX_TYPE(initOp) == URX_CTR_INIT_NG); michael@0: int64_t *pCounter = &fp->fExtra[URX_VAL(initOp)]; michael@0: int32_t minCount = (int32_t)pat[opValue+2]; michael@0: int32_t maxCount = (int32_t)pat[opValue+3]; michael@0: michael@0: (*pCounter)++; michael@0: if ((uint64_t)*pCounter >= (uint32_t)maxCount && maxCount != -1) { michael@0: // The loop has matched the maximum permitted number of times. michael@0: // Break out of here with no action. Matching will michael@0: // continue with the following pattern. michael@0: U_ASSERT(*pCounter == maxCount); michael@0: break; michael@0: } michael@0: michael@0: if (*pCounter < minCount) { michael@0: // We haven't met the minimum number of matches yet. michael@0: // Loop back for another one. michael@0: fp->fPatIdx = opValue + 4; // Loop back. michael@0: } else { michael@0: // We do have the minimum number of matches. michael@0: michael@0: // If there is no upper bound on the loop iterations, check that the input index michael@0: // is progressing, and stop the loop if it is not. michael@0: if (maxCount == -1) { michael@0: int64_t *pLastInputIdx = &fp->fExtra[URX_VAL(initOp) + 1]; michael@0: if (fp->fInputIdx == *pLastInputIdx) { michael@0: break; michael@0: } michael@0: *pLastInputIdx = fp->fInputIdx; michael@0: } michael@0: michael@0: // Loop Continuation: we will fall into the pattern following the loop michael@0: // (non-greedy, don't execute loop body first), but first do michael@0: // a state save to the top of the loop, so that a match failure michael@0: // in the following pattern will try another iteration of the loop. michael@0: fp = StateSave(fp, opValue + 4, status); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: case URX_STO_SP: michael@0: U_ASSERT(opValue >= 0 && opValue < fPattern->fDataSize); michael@0: fData[opValue] = fStack->size(); michael@0: break; michael@0: michael@0: case URX_LD_SP: michael@0: { michael@0: U_ASSERT(opValue >= 0 && opValue < fPattern->fDataSize); michael@0: int32_t newStackSize = (int32_t)fData[opValue]; michael@0: U_ASSERT(newStackSize <= fStack->size()); michael@0: int64_t *newFP = fStack->getBuffer() + newStackSize - fFrameSize; michael@0: if (newFP == (int64_t *)fp) { michael@0: break; michael@0: } michael@0: int32_t i; michael@0: for (i=0; isetSize(newStackSize); michael@0: } michael@0: break; michael@0: michael@0: case URX_BACKREF: michael@0: { michael@0: U_ASSERT(opValue < fFrameSize); michael@0: int64_t groupStartIdx = fp->fExtra[opValue]; michael@0: int64_t groupEndIdx = fp->fExtra[opValue+1]; michael@0: U_ASSERT(groupStartIdx <= groupEndIdx); michael@0: int64_t inputIndex = fp->fInputIdx; michael@0: if (groupStartIdx < 0) { michael@0: // This capture group has not participated in the match thus far, michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); // FAIL, no match. michael@0: break; michael@0: } michael@0: UBool success = TRUE; michael@0: for (int64_t groupIndex = groupStartIdx; groupIndex < groupEndIdx; ++groupIndex,++inputIndex) { michael@0: if (inputIndex >= fActiveLimit) { michael@0: success = FALSE; michael@0: fHitEnd = TRUE; michael@0: break; michael@0: } michael@0: if (inputBuf[groupIndex] != inputBuf[inputIndex]) { michael@0: success = FALSE; michael@0: break; michael@0: } michael@0: } michael@0: if (success) { michael@0: fp->fInputIdx = inputIndex; michael@0: } else { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: case URX_BACKREF_I: michael@0: { michael@0: U_ASSERT(opValue < fFrameSize); michael@0: int64_t groupStartIdx = fp->fExtra[opValue]; michael@0: int64_t groupEndIdx = fp->fExtra[opValue+1]; michael@0: U_ASSERT(groupStartIdx <= groupEndIdx); michael@0: if (groupStartIdx < 0) { michael@0: // This capture group has not participated in the match thus far, michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); // FAIL, no match. michael@0: break; michael@0: } michael@0: CaseFoldingUCharIterator captureGroupItr(inputBuf, groupStartIdx, groupEndIdx); michael@0: CaseFoldingUCharIterator inputItr(inputBuf, fp->fInputIdx, fActiveLimit); michael@0: michael@0: // Note: if the capture group match was of an empty string the backref michael@0: // match succeeds. Verified by testing: Perl matches succeed michael@0: // in this case, so we do too. michael@0: michael@0: UBool success = TRUE; michael@0: for (;;) { michael@0: UChar32 captureGroupChar = captureGroupItr.next(); michael@0: if (captureGroupChar == U_SENTINEL) { michael@0: success = TRUE; michael@0: break; michael@0: } michael@0: UChar32 inputChar = inputItr.next(); michael@0: if (inputChar == U_SENTINEL) { michael@0: success = FALSE; michael@0: fHitEnd = TRUE; michael@0: break; michael@0: } michael@0: if (inputChar != captureGroupChar) { michael@0: success = FALSE; michael@0: break; michael@0: } michael@0: } michael@0: michael@0: if (success && inputItr.inExpansion()) { michael@0: // We otained a match by consuming part of a string obtained from michael@0: // case-folding a single code point of the input text. michael@0: // This does not count as an overall match. michael@0: success = FALSE; michael@0: } michael@0: michael@0: if (success) { michael@0: fp->fInputIdx = inputItr.getIndex(); michael@0: } else { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: case URX_STO_INP_LOC: michael@0: { michael@0: U_ASSERT(opValue >= 0 && opValue < fFrameSize); michael@0: fp->fExtra[opValue] = fp->fInputIdx; michael@0: } michael@0: break; michael@0: michael@0: case URX_JMPX: michael@0: { michael@0: int32_t instrOperandLoc = (int32_t)fp->fPatIdx; michael@0: fp->fPatIdx += 1; michael@0: int32_t dataLoc = URX_VAL(pat[instrOperandLoc]); michael@0: U_ASSERT(dataLoc >= 0 && dataLoc < fFrameSize); michael@0: int32_t savedInputIdx = (int32_t)fp->fExtra[dataLoc]; michael@0: U_ASSERT(savedInputIdx <= fp->fInputIdx); michael@0: if (savedInputIdx < fp->fInputIdx) { michael@0: fp->fPatIdx = opValue; // JMP michael@0: } else { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); // FAIL, no progress in loop. michael@0: } michael@0: } michael@0: break; michael@0: michael@0: case URX_LA_START: michael@0: { michael@0: // Entering a lookahead block. michael@0: // Save Stack Ptr, Input Pos. michael@0: U_ASSERT(opValue>=0 && opValue+1fDataSize); michael@0: fData[opValue] = fStack->size(); michael@0: fData[opValue+1] = fp->fInputIdx; michael@0: fActiveStart = fLookStart; // Set the match region change for michael@0: fActiveLimit = fLookLimit; // transparent bounds. michael@0: } michael@0: break; michael@0: michael@0: case URX_LA_END: michael@0: { michael@0: // Leaving a look-ahead block. michael@0: // restore Stack Ptr, Input Pos to positions they had on entry to block. michael@0: U_ASSERT(opValue>=0 && opValue+1fDataSize); michael@0: int32_t stackSize = fStack->size(); michael@0: int32_t newStackSize = (int32_t)fData[opValue]; michael@0: U_ASSERT(stackSize >= newStackSize); michael@0: if (stackSize > newStackSize) { michael@0: // Copy the current top frame back to the new (cut back) top frame. michael@0: // This makes the capture groups from within the look-ahead michael@0: // expression available. michael@0: int64_t *newFP = fStack->getBuffer() + newStackSize - fFrameSize; michael@0: int32_t i; michael@0: for (i=0; isetSize(newStackSize); michael@0: } michael@0: fp->fInputIdx = fData[opValue+1]; michael@0: michael@0: // Restore the active region bounds in the input string; they may have michael@0: // been changed because of transparent bounds on a Region. michael@0: fActiveStart = fRegionStart; michael@0: fActiveLimit = fRegionLimit; michael@0: } michael@0: break; michael@0: michael@0: case URX_ONECHAR_I: michael@0: if (fp->fInputIdx < fActiveLimit) { michael@0: UChar32 c; michael@0: U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c); michael@0: if (u_foldCase(c, U_FOLD_CASE_DEFAULT) == opValue) { michael@0: break; michael@0: } michael@0: } else { michael@0: fHitEnd = TRUE; michael@0: } michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: michael@0: case URX_STRING_I: michael@0: // Case-insensitive test input against a literal string. michael@0: // Strings require two slots in the compiled pattern, one for the michael@0: // offset to the string text, and one for the length. michael@0: // The compiled string has already been case folded. michael@0: { michael@0: const UChar *patternString = litText + opValue; michael@0: michael@0: op = (int32_t)pat[fp->fPatIdx]; michael@0: fp->fPatIdx++; michael@0: opType = URX_TYPE(op); michael@0: opValue = URX_VAL(op); michael@0: U_ASSERT(opType == URX_STRING_LEN); michael@0: int32_t patternStringLen = opValue; // Length of the string from the pattern. michael@0: michael@0: UChar32 cText; michael@0: UChar32 cPattern; michael@0: UBool success = TRUE; michael@0: int32_t patternStringIdx = 0; michael@0: CaseFoldingUCharIterator inputIterator(inputBuf, fp->fInputIdx, fActiveLimit); michael@0: while (patternStringIdx < patternStringLen) { michael@0: U16_NEXT(patternString, patternStringIdx, patternStringLen, cPattern); michael@0: cText = inputIterator.next(); michael@0: if (cText != cPattern) { michael@0: success = FALSE; michael@0: if (cText == U_SENTINEL) { michael@0: fHitEnd = TRUE; michael@0: } michael@0: break; michael@0: } michael@0: } michael@0: if (inputIterator.inExpansion()) { michael@0: success = FALSE; michael@0: } michael@0: michael@0: if (success) { michael@0: fp->fInputIdx = inputIterator.getIndex(); michael@0: } else { michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: } michael@0: break; michael@0: michael@0: case URX_LB_START: michael@0: { michael@0: // Entering a look-behind block. michael@0: // Save Stack Ptr, Input Pos. michael@0: // TODO: implement transparent bounds. Ticket #6067 michael@0: U_ASSERT(opValue>=0 && opValue+1fDataSize); michael@0: fData[opValue] = fStack->size(); michael@0: fData[opValue+1] = fp->fInputIdx; michael@0: // Init the variable containing the start index for attempted matches. michael@0: fData[opValue+2] = -1; michael@0: // Save input string length, then reset to pin any matches to end at michael@0: // the current position. michael@0: fData[opValue+3] = fActiveLimit; michael@0: fActiveLimit = fp->fInputIdx; michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_LB_CONT: michael@0: { michael@0: // Positive Look-Behind, at top of loop checking for matches of LB expression michael@0: // at all possible input starting positions. michael@0: michael@0: // Fetch the min and max possible match lengths. They are the operands michael@0: // of this op in the pattern. michael@0: int32_t minML = (int32_t)pat[fp->fPatIdx++]; michael@0: int32_t maxML = (int32_t)pat[fp->fPatIdx++]; michael@0: U_ASSERT(minML <= maxML); michael@0: U_ASSERT(minML >= 0); michael@0: michael@0: // Fetch (from data) the last input index where a match was attempted. michael@0: U_ASSERT(opValue>=0 && opValue+1fDataSize); michael@0: int64_t *lbStartIdx = &fData[opValue+2]; michael@0: if (*lbStartIdx < 0) { michael@0: // First time through loop. michael@0: *lbStartIdx = fp->fInputIdx - minML; michael@0: } else { michael@0: // 2nd through nth time through the loop. michael@0: // Back up start position for match by one. michael@0: if (*lbStartIdx == 0) { michael@0: (*lbStartIdx)--; michael@0: } else { michael@0: U16_BACK_1(inputBuf, 0, *lbStartIdx); michael@0: } michael@0: } michael@0: michael@0: if (*lbStartIdx < 0 || *lbStartIdx < fp->fInputIdx - maxML) { michael@0: // We have tried all potential match starting points without michael@0: // getting a match. Backtrack out, and out of the michael@0: // Look Behind altogether. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: int64_t restoreInputLen = fData[opValue+3]; michael@0: U_ASSERT(restoreInputLen >= fActiveLimit); michael@0: U_ASSERT(restoreInputLen <= fInputLength); michael@0: fActiveLimit = restoreInputLen; michael@0: break; michael@0: } michael@0: michael@0: // Save state to this URX_LB_CONT op, so failure to match will repeat the loop. michael@0: // (successful match will fall off the end of the loop.) michael@0: fp = StateSave(fp, fp->fPatIdx-3, status); michael@0: fp->fInputIdx = *lbStartIdx; michael@0: } michael@0: break; michael@0: michael@0: case URX_LB_END: michael@0: // End of a look-behind block, after a successful match. michael@0: { michael@0: U_ASSERT(opValue>=0 && opValue+1fDataSize); michael@0: if (fp->fInputIdx != fActiveLimit) { michael@0: // The look-behind expression matched, but the match did not michael@0: // extend all the way to the point that we are looking behind from. michael@0: // FAIL out of here, which will take us back to the LB_CONT, which michael@0: // will retry the match starting at another position or fail michael@0: // the look-behind altogether, whichever is appropriate. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: // Look-behind match is good. Restore the orignal input string length, michael@0: // which had been truncated to pin the end of the lookbehind match to the michael@0: // position being looked-behind. michael@0: int64_t originalInputLen = fData[opValue+3]; michael@0: U_ASSERT(originalInputLen >= fActiveLimit); michael@0: U_ASSERT(originalInputLen <= fInputLength); michael@0: fActiveLimit = originalInputLen; michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_LBN_CONT: michael@0: { michael@0: // Negative Look-Behind, at top of loop checking for matches of LB expression michael@0: // at all possible input starting positions. michael@0: michael@0: // Fetch the extra parameters of this op. michael@0: int32_t minML = (int32_t)pat[fp->fPatIdx++]; michael@0: int32_t maxML = (int32_t)pat[fp->fPatIdx++]; michael@0: int32_t continueLoc = (int32_t)pat[fp->fPatIdx++]; michael@0: continueLoc = URX_VAL(continueLoc); michael@0: U_ASSERT(minML <= maxML); michael@0: U_ASSERT(minML >= 0); michael@0: U_ASSERT(continueLoc > fp->fPatIdx); michael@0: michael@0: // Fetch (from data) the last input index where a match was attempted. michael@0: U_ASSERT(opValue>=0 && opValue+1fDataSize); michael@0: int64_t *lbStartIdx = &fData[opValue+2]; michael@0: if (*lbStartIdx < 0) { michael@0: // First time through loop. michael@0: *lbStartIdx = fp->fInputIdx - minML; michael@0: } else { michael@0: // 2nd through nth time through the loop. michael@0: // Back up start position for match by one. michael@0: if (*lbStartIdx == 0) { michael@0: (*lbStartIdx)--; // Because U16_BACK is unsafe starting at 0. michael@0: } else { michael@0: U16_BACK_1(inputBuf, 0, *lbStartIdx); michael@0: } michael@0: } michael@0: michael@0: if (*lbStartIdx < 0 || *lbStartIdx < fp->fInputIdx - maxML) { michael@0: // We have tried all potential match starting points without michael@0: // getting a match, which means that the negative lookbehind as michael@0: // a whole has succeeded. Jump forward to the continue location michael@0: int64_t restoreInputLen = fData[opValue+3]; michael@0: U_ASSERT(restoreInputLen >= fActiveLimit); michael@0: U_ASSERT(restoreInputLen <= fInputLength); michael@0: fActiveLimit = restoreInputLen; michael@0: fp->fPatIdx = continueLoc; michael@0: break; michael@0: } michael@0: michael@0: // Save state to this URX_LB_CONT op, so failure to match will repeat the loop. michael@0: // (successful match will cause a FAIL out of the loop altogether.) michael@0: fp = StateSave(fp, fp->fPatIdx-4, status); michael@0: fp->fInputIdx = *lbStartIdx; michael@0: } michael@0: break; michael@0: michael@0: case URX_LBN_END: michael@0: // End of a negative look-behind block, after a successful match. michael@0: { michael@0: U_ASSERT(opValue>=0 && opValue+1fDataSize); michael@0: if (fp->fInputIdx != fActiveLimit) { michael@0: // The look-behind expression matched, but the match did not michael@0: // extend all the way to the point that we are looking behind from. michael@0: // FAIL out of here, which will take us back to the LB_CONT, which michael@0: // will retry the match starting at another position or succeed michael@0: // the look-behind altogether, whichever is appropriate. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: break; michael@0: } michael@0: michael@0: // Look-behind expression matched, which means look-behind test as michael@0: // a whole Fails michael@0: michael@0: // Restore the orignal input string length, which had been truncated michael@0: // inorder to pin the end of the lookbehind match michael@0: // to the position being looked-behind. michael@0: int64_t originalInputLen = fData[opValue+3]; michael@0: U_ASSERT(originalInputLen >= fActiveLimit); michael@0: U_ASSERT(originalInputLen <= fInputLength); michael@0: fActiveLimit = originalInputLen; michael@0: michael@0: // Restore original stack position, discarding any state saved michael@0: // by the successful pattern match. michael@0: U_ASSERT(opValue>=0 && opValue+1fDataSize); michael@0: int32_t newStackSize = (int32_t)fData[opValue]; michael@0: U_ASSERT(fStack->size() > newStackSize); michael@0: fStack->setSize(newStackSize); michael@0: michael@0: // FAIL, which will take control back to someplace michael@0: // prior to entering the look-behind test. michael@0: fp = (REStackFrame *)fStack->popFrame(fFrameSize); michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_LOOP_SR_I: michael@0: // Loop Initialization for the optimized implementation of michael@0: // [some character set]* michael@0: // This op scans through all matching input. michael@0: // The following LOOP_C op emulates stack unwinding if the following pattern fails. michael@0: { michael@0: U_ASSERT(opValue > 0 && opValue < sets->size()); michael@0: Regex8BitSet *s8 = &fPattern->fSets8[opValue]; michael@0: UnicodeSet *s = (UnicodeSet *)sets->elementAt(opValue); michael@0: michael@0: // Loop through input, until either the input is exhausted or michael@0: // we reach a character that is not a member of the set. michael@0: int32_t ix = (int32_t)fp->fInputIdx; michael@0: for (;;) { michael@0: if (ix >= fActiveLimit) { michael@0: fHitEnd = TRUE; michael@0: break; michael@0: } michael@0: UChar32 c; michael@0: U16_NEXT(inputBuf, ix, fActiveLimit, c); michael@0: if (c<256) { michael@0: if (s8->contains(c) == FALSE) { michael@0: U16_BACK_1(inputBuf, 0, ix); michael@0: break; michael@0: } michael@0: } else { michael@0: if (s->contains(c) == FALSE) { michael@0: U16_BACK_1(inputBuf, 0, ix); michael@0: break; michael@0: } michael@0: } michael@0: } michael@0: michael@0: // If there were no matching characters, skip over the loop altogether. michael@0: // The loop doesn't run at all, a * op always succeeds. michael@0: if (ix == fp->fInputIdx) { michael@0: fp->fPatIdx++; // skip the URX_LOOP_C op. michael@0: break; michael@0: } michael@0: michael@0: // Peek ahead in the compiled pattern, to the URX_LOOP_C that michael@0: // must follow. It's operand is the stack location michael@0: // that holds the starting input index for the match of this [set]* michael@0: int32_t loopcOp = (int32_t)pat[fp->fPatIdx]; michael@0: U_ASSERT(URX_TYPE(loopcOp) == URX_LOOP_C); michael@0: int32_t stackLoc = URX_VAL(loopcOp); michael@0: U_ASSERT(stackLoc >= 0 && stackLoc < fFrameSize); michael@0: fp->fExtra[stackLoc] = fp->fInputIdx; michael@0: fp->fInputIdx = ix; michael@0: michael@0: // Save State to the URX_LOOP_C op that follows this one, michael@0: // so that match failures in the following code will return to there. michael@0: // Then bump the pattern idx so the LOOP_C is skipped on the way out of here. michael@0: fp = StateSave(fp, fp->fPatIdx, status); michael@0: fp->fPatIdx++; michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_LOOP_DOT_I: michael@0: // Loop Initialization for the optimized implementation of .* michael@0: // This op scans through all remaining input. michael@0: // The following LOOP_C op emulates stack unwinding if the following pattern fails. michael@0: { michael@0: // Loop through input until the input is exhausted (we reach an end-of-line) michael@0: // In DOTALL mode, we can just go straight to the end of the input. michael@0: int32_t ix; michael@0: if ((opValue & 1) == 1) { michael@0: // Dot-matches-All mode. Jump straight to the end of the string. michael@0: ix = (int32_t)fActiveLimit; michael@0: fHitEnd = TRUE; michael@0: } else { michael@0: // NOT DOT ALL mode. Line endings do not match '.' michael@0: // Scan forward until a line ending or end of input. michael@0: ix = (int32_t)fp->fInputIdx; michael@0: for (;;) { michael@0: if (ix >= fActiveLimit) { michael@0: fHitEnd = TRUE; michael@0: break; michael@0: } michael@0: UChar32 c; michael@0: U16_NEXT(inputBuf, ix, fActiveLimit, c); // c = inputBuf[ix++] michael@0: if ((c & 0x7f) <= 0x29) { // Fast filter of non-new-line-s michael@0: if ((c == 0x0a) || // 0x0a is newline in both modes. michael@0: (((opValue & 2) == 0) && // IF not UNIX_LINES mode michael@0: ((c<=0x0d && c>=0x0a) || c==0x85 || c==0x2028 || c==0x2029))) { michael@0: // char is a line ending. Put the input pos back to the michael@0: // line ending char, and exit the scanning loop. michael@0: U16_BACK_1(inputBuf, 0, ix); michael@0: break; michael@0: } michael@0: } michael@0: } michael@0: } michael@0: michael@0: // If there were no matching characters, skip over the loop altogether. michael@0: // The loop doesn't run at all, a * op always succeeds. michael@0: if (ix == fp->fInputIdx) { michael@0: fp->fPatIdx++; // skip the URX_LOOP_C op. michael@0: break; michael@0: } michael@0: michael@0: // Peek ahead in the compiled pattern, to the URX_LOOP_C that michael@0: // must follow. It's operand is the stack location michael@0: // that holds the starting input index for the match of this .* michael@0: int32_t loopcOp = (int32_t)pat[fp->fPatIdx]; michael@0: U_ASSERT(URX_TYPE(loopcOp) == URX_LOOP_C); michael@0: int32_t stackLoc = URX_VAL(loopcOp); michael@0: U_ASSERT(stackLoc >= 0 && stackLoc < fFrameSize); michael@0: fp->fExtra[stackLoc] = fp->fInputIdx; michael@0: fp->fInputIdx = ix; michael@0: michael@0: // Save State to the URX_LOOP_C op that follows this one, michael@0: // so that match failures in the following code will return to there. michael@0: // Then bump the pattern idx so the LOOP_C is skipped on the way out of here. michael@0: fp = StateSave(fp, fp->fPatIdx, status); michael@0: fp->fPatIdx++; michael@0: } michael@0: break; michael@0: michael@0: michael@0: case URX_LOOP_C: michael@0: { michael@0: U_ASSERT(opValue>=0 && opValuefExtra[opValue]; michael@0: U_ASSERT(backSearchIndex <= fp->fInputIdx); michael@0: if (backSearchIndex == fp->fInputIdx) { michael@0: // We've backed up the input idx to the point that the loop started. michael@0: // The loop is done. Leave here without saving state. michael@0: // Subsequent failures won't come back here. michael@0: break; michael@0: } michael@0: // Set up for the next iteration of the loop, with input index michael@0: // backed up by one from the last time through, michael@0: // and a state save to this instruction in case the following code fails again. michael@0: // (We're going backwards because this loop emulates stack unwinding, not michael@0: // the initial scan forward.) michael@0: U_ASSERT(fp->fInputIdx > 0); michael@0: UChar32 prevC; michael@0: U16_PREV(inputBuf, 0, fp->fInputIdx, prevC); // !!!: should this 0 be one of f*Limit? michael@0: michael@0: if (prevC == 0x0a && michael@0: fp->fInputIdx > backSearchIndex && michael@0: inputBuf[fp->fInputIdx-1] == 0x0d) { michael@0: int32_t prevOp = (int32_t)pat[fp->fPatIdx-2]; michael@0: if (URX_TYPE(prevOp) == URX_LOOP_DOT_I) { michael@0: // .*, stepping back over CRLF pair. michael@0: U16_BACK_1(inputBuf, 0, fp->fInputIdx); michael@0: } michael@0: } michael@0: michael@0: michael@0: fp = StateSave(fp, fp->fPatIdx-1, status); michael@0: } michael@0: break; michael@0: michael@0: michael@0: michael@0: default: michael@0: // Trouble. The compiled pattern contains an entry with an michael@0: // unrecognized type tag. michael@0: U_ASSERT(FALSE); michael@0: } michael@0: michael@0: if (U_FAILURE(status)) { michael@0: isMatch = FALSE; michael@0: break; michael@0: } michael@0: } michael@0: michael@0: breakFromLoop: michael@0: fMatch = isMatch; michael@0: if (isMatch) { michael@0: fLastMatchEnd = fMatchEnd; michael@0: fMatchStart = startIdx; michael@0: fMatchEnd = fp->fInputIdx; michael@0: if (fTraceDebug) { michael@0: REGEX_RUN_DEBUG_PRINTF(("Match. start=%ld end=%ld\n\n", fMatchStart, fMatchEnd)); michael@0: } michael@0: } michael@0: else michael@0: { michael@0: if (fTraceDebug) { michael@0: REGEX_RUN_DEBUG_PRINTF(("No match\n\n")); michael@0: } michael@0: } michael@0: michael@0: fFrame = fp; // The active stack frame when the engine stopped. michael@0: // Contains the capture group results that we need to michael@0: // access later. michael@0: michael@0: return; michael@0: } michael@0: michael@0: michael@0: UOBJECT_DEFINE_RTTI_IMPLEMENTATION(RegexMatcher) michael@0: michael@0: U_NAMESPACE_END michael@0: michael@0: #endif // !UCONFIG_NO_REGULAR_EXPRESSIONS