in intl/icu/source/i18n/rematch.cpp [4294:5720]
void RegexMatcher::MatchChunkAt(int32_t startIdx, UBool toEnd, UErrorCode &status) {
UBool isMatch = false; // True if the we have a match.
int32_t backSearchIndex = INT32_MAX; // used after greedy single-character matches for searching backwards
int32_t op; // Operation from the compiled pattern, split into
int32_t opType; // the opcode
int32_t opValue; // and the operand value.
#ifdef REGEX_RUN_DEBUG
if (fTraceDebug) {
printf("MatchAt(startIdx=%d)\n", startIdx);
printf("Original Pattern: \"%s\"\n", CStr(StringFromUText(fPattern->fPattern))());
printf("Input String: \"%s\"\n\n", CStr(StringFromUText(fInputText))());
}
#endif
if (U_FAILURE(status)) {
return;
}
// Cache frequently referenced items from the compiled pattern
//
int64_t *pat = fPattern->fCompiledPat->getBuffer();
const char16_t *litText = fPattern->fLiteralText.getBuffer();
UVector *fSets = fPattern->fSets;
const char16_t *inputBuf = fInputText->chunkContents;
fFrameSize = fPattern->fFrameSize;
REStackFrame *fp = resetStack();
if (U_FAILURE(fDeferredStatus)) {
status = fDeferredStatus;
return;
}
fp->fPatIdx = 0;
fp->fInputIdx = startIdx;
// Zero out the pattern's static data
int32_t i;
for (i = 0; i<fPattern->fDataSize; i++) {
fData[i] = 0;
}
//
// Main loop for interpreting the compiled pattern.
// One iteration of the loop per pattern operation performed.
//
for (;;) {
op = static_cast<int32_t>(pat[fp->fPatIdx]);
opType = URX_TYPE(op);
opValue = URX_VAL(op);
#ifdef REGEX_RUN_DEBUG
if (fTraceDebug) {
UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
printf("inputIdx=%ld inputChar=%x sp=%3ld activeLimit=%ld ", fp->fInputIdx,
UTEXT_CURRENT32(fInputText), (int64_t *)fp-fStack->getBuffer(), fActiveLimit);
fPattern->dumpOp(fp->fPatIdx);
}
#endif
fp->fPatIdx++;
switch (opType) {
case URX_NOP:
break;
case URX_BACKTRACK:
// Force a backtrack. In some circumstances, the pattern compiler
// will notice that the pattern can't possibly match anything, and will
// emit one of these at that point.
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
case URX_ONECHAR:
if (fp->fInputIdx < fActiveLimit) {
UChar32 c;
U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
if (c == opValue) {
break;
}
} else {
fHitEnd = true;
}
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
case URX_STRING:
{
// Test input against a literal string.
// Strings require two slots in the compiled pattern, one for the
// offset to the string text, and one for the length.
int32_t stringStartIdx = opValue;
int32_t stringLen;
op = static_cast<int32_t>(pat[fp->fPatIdx]); // Fetch the second operand
fp->fPatIdx++;
opType = URX_TYPE(op);
stringLen = URX_VAL(op);
U_ASSERT(opType == URX_STRING_LEN);
U_ASSERT(stringLen >= 2);
const char16_t * pInp = inputBuf + fp->fInputIdx;
const char16_t * pInpLimit = inputBuf + fActiveLimit;
const char16_t * pPat = litText+stringStartIdx;
const char16_t * pEnd = pInp + stringLen;
UBool success = true;
while (pInp < pEnd) {
if (pInp >= pInpLimit) {
fHitEnd = true;
success = false;
break;
}
if (*pInp++ != *pPat++) {
success = false;
break;
}
}
if (success) {
fp->fInputIdx += stringLen;
} else {
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
}
break;
case URX_STATE_SAVE:
fp = StateSave(fp, opValue, status);
break;
case URX_END:
// The match loop will exit via this path on a successful match,
// when we reach the end of the pattern.
if (toEnd && fp->fInputIdx != fActiveLimit) {
// The pattern matched, but not to the end of input. Try some more.
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
}
isMatch = true;
goto breakFromLoop;
// Start and End Capture stack frame variables are laid out out like this:
// fp->fExtra[opValue] - The start of a completed capture group
// opValue+1 - The end of a completed capture group
// opValue+2 - the start of a capture group whose end
// has not yet been reached (and might not ever be).
case URX_START_CAPTURE:
U_ASSERT(opValue >= 0 && opValue < fFrameSize-3);
fp->fExtra[opValue+2] = fp->fInputIdx;
break;
case URX_END_CAPTURE:
U_ASSERT(opValue >= 0 && opValue < fFrameSize-3);
U_ASSERT(fp->fExtra[opValue+2] >= 0); // Start pos for this group must be set.
fp->fExtra[opValue] = fp->fExtra[opValue+2]; // Tentative start becomes real.
fp->fExtra[opValue+1] = fp->fInputIdx; // End position
U_ASSERT(fp->fExtra[opValue] <= fp->fExtra[opValue+1]);
break;
case URX_DOLLAR: // $, test for End of line
// or for position before new line at end of input
if (fp->fInputIdx < fAnchorLimit-2) {
// We are no where near the end of input. Fail.
// This is the common case. Keep it first.
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
}
if (fp->fInputIdx >= fAnchorLimit) {
// We really are at the end of input. Success.
fHitEnd = true;
fRequireEnd = true;
break;
}
// If we are positioned just before a new-line that is located at the
// end of input, succeed.
if (fp->fInputIdx == fAnchorLimit-1) {
UChar32 c;
U16_GET(inputBuf, fAnchorStart, fp->fInputIdx, fAnchorLimit, c);
if (isLineTerminator(c)) {
if ( !(c==0x0a && fp->fInputIdx>fAnchorStart && inputBuf[fp->fInputIdx-1]==0x0d)) {
// At new-line at end of input. Success
fHitEnd = true;
fRequireEnd = true;
break;
}
}
} else if (fp->fInputIdx == fAnchorLimit-2 &&
inputBuf[fp->fInputIdx]==0x0d && inputBuf[fp->fInputIdx+1]==0x0a) {
fHitEnd = true;
fRequireEnd = true;
break; // At CR/LF at end of input. Success
}
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
case URX_DOLLAR_D: // $, test for End of Line, in UNIX_LINES mode.
if (fp->fInputIdx >= fAnchorLimit-1) {
// Either at the last character of input, or off the end.
if (fp->fInputIdx == fAnchorLimit-1) {
// At last char of input. Success if it's a new line.
if (inputBuf[fp->fInputIdx] == 0x0a) {
fHitEnd = true;
fRequireEnd = true;
break;
}
} else {
// Off the end of input. Success.
fHitEnd = true;
fRequireEnd = true;
break;
}
}
// Not at end of input. Back-track out.
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
case URX_DOLLAR_M: // $, test for End of line in multi-line mode
{
if (fp->fInputIdx >= fAnchorLimit) {
// We really are at the end of input. Success.
fHitEnd = true;
fRequireEnd = true;
break;
}
// If we are positioned just before a new-line, succeed.
// It makes no difference where the new-line is within the input.
UChar32 c = inputBuf[fp->fInputIdx];
if (isLineTerminator(c)) {
// At a line end, except for the odd chance of being in the middle of a CR/LF sequence
// In multi-line mode, hitting a new-line just before the end of input does not
// set the hitEnd or requireEnd flags
if ( !(c==0x0a && fp->fInputIdx>fAnchorStart && inputBuf[fp->fInputIdx-1]==0x0d)) {
break;
}
}
// not at a new line. Fail.
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
break;
case URX_DOLLAR_MD: // $, test for End of line in multi-line and UNIX_LINES mode
{
if (fp->fInputIdx >= fAnchorLimit) {
// We really are at the end of input. Success.
fHitEnd = true;
fRequireEnd = true; // Java set requireEnd in this case, even though
break; // adding a new-line would not lose the match.
}
// If we are not positioned just before a new-line, the test fails; backtrack out.
// It makes no difference where the new-line is within the input.
if (inputBuf[fp->fInputIdx] != 0x0a) {
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
}
break;
case URX_CARET: // ^, test for start of line
if (fp->fInputIdx != fAnchorStart) {
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
break;
case URX_CARET_M: // ^, test for start of line in mulit-line mode
{
if (fp->fInputIdx == fAnchorStart) {
// We are at the start input. Success.
break;
}
// Check whether character just before the current pos is a new-line
// unless we are at the end of input
char16_t c = inputBuf[fp->fInputIdx - 1];
if ((fp->fInputIdx < fAnchorLimit) &&
isLineTerminator(c)) {
// It's a new-line. ^ is true. Success.
// TODO: what should be done with positions between a CR and LF?
break;
}
// Not at the start of a line. Fail.
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
break;
case URX_CARET_M_UNIX: // ^, test for start of line in mulit-line + Unix-line mode
{
U_ASSERT(fp->fInputIdx >= fAnchorStart);
if (fp->fInputIdx <= fAnchorStart) {
// We are at the start input. Success.
break;
}
// Check whether character just before the current pos is a new-line
U_ASSERT(fp->fInputIdx <= fAnchorLimit);
char16_t c = inputBuf[fp->fInputIdx - 1];
if (c != 0x0a) {
// Not at the start of a line. Back-track out.
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
}
break;
case URX_BACKSLASH_B: // Test for word boundaries
{
UBool success = isChunkWordBoundary(static_cast<int32_t>(fp->fInputIdx));
success ^= static_cast<UBool>(opValue != 0); // flip sense for \B
if (!success) {
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
}
break;
case URX_BACKSLASH_BU: // Test for word boundaries, Unicode-style
{
UBool success = isUWordBoundary(fp->fInputIdx, status);
success ^= static_cast<UBool>(opValue != 0); // flip sense for \B
if (!success) {
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
}
break;
case URX_BACKSLASH_D: // Test for decimal digit
{
if (fp->fInputIdx >= fActiveLimit) {
fHitEnd = true;
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
}
UChar32 c;
U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
int8_t ctype = u_charType(c); // TODO: make a unicode set for this. Will be faster.
UBool success = (ctype == U_DECIMAL_DIGIT_NUMBER);
success ^= static_cast<UBool>(opValue != 0); // flip sense for \D
if (!success) {
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
}
break;
case URX_BACKSLASH_G: // Test for position at end of previous match
if (!((fMatch && fp->fInputIdx==fMatchEnd) || (fMatch==false && fp->fInputIdx==fActiveStart))) {
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
break;
case URX_BACKSLASH_H: // Test for \h, horizontal white space.
{
if (fp->fInputIdx >= fActiveLimit) {
fHitEnd = true;
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
}
UChar32 c;
U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
int8_t ctype = u_charType(c);
UBool success = (ctype == U_SPACE_SEPARATOR || c == 9); // SPACE_SEPARATOR || TAB
success ^= static_cast<UBool>(opValue != 0); // flip sense for \H
if (!success) {
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
}
break;
case URX_BACKSLASH_R: // Test for \R, any line break sequence.
{
if (fp->fInputIdx >= fActiveLimit) {
fHitEnd = true;
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
}
UChar32 c;
U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
if (isLineTerminator(c)) {
if (c == 0x0d && fp->fInputIdx < fActiveLimit) {
// Check for CR/LF sequence. Consume both together when found.
char16_t c2;
U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c2);
if (c2 != 0x0a) {
U16_PREV(inputBuf, 0, fp->fInputIdx, c2);
}
}
} else {
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
}
break;
case URX_BACKSLASH_V: // Any single code point line ending.
{
if (fp->fInputIdx >= fActiveLimit) {
fHitEnd = true;
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
}
UChar32 c;
U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
UBool success = isLineTerminator(c);
success ^= static_cast<UBool>(opValue != 0); // flip sense for \V
if (!success) {
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
}
break;
case URX_BACKSLASH_X:
// Match a Grapheme, as defined by Unicode UAX 29.
// Fail if at end of input
if (fp->fInputIdx >= fActiveLimit) {
fHitEnd = true;
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
}
fp->fInputIdx = followingGCBoundary(fp->fInputIdx, status);
if (fp->fInputIdx >= fActiveLimit) {
fHitEnd = true;
fp->fInputIdx = fActiveLimit;
}
break;
case URX_BACKSLASH_Z: // Test for end of Input
if (fp->fInputIdx < fAnchorLimit) {
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
} else {
fHitEnd = true;
fRequireEnd = true;
}
break;
case URX_STATIC_SETREF:
{
// Test input character against one of the predefined sets
// (Word Characters, for example)
// The high bit of the op value is a flag for the match polarity.
// 0: success if input char is in set.
// 1: success if input char is not in set.
if (fp->fInputIdx >= fActiveLimit) {
fHitEnd = true;
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
}
UBool success = ((opValue & URX_NEG_SET) == URX_NEG_SET);
opValue &= ~URX_NEG_SET;
U_ASSERT(opValue > 0 && opValue < URX_LAST_SET);
UChar32 c;
U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
if (c < 256) {
Regex8BitSet &s8 = RegexStaticSets::gStaticSets->fPropSets8[opValue];
if (s8.contains(c)) {
success = !success;
}
} else {
const UnicodeSet &s = RegexStaticSets::gStaticSets->fPropSets[opValue];
if (s.contains(c)) {
success = !success;
}
}
if (!success) {
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
}
break;
case URX_STAT_SETREF_N:
{
// Test input character for NOT being a member of one of
// the predefined sets (Word Characters, for example)
if (fp->fInputIdx >= fActiveLimit) {
fHitEnd = true;
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
}
U_ASSERT(opValue > 0 && opValue < URX_LAST_SET);
UChar32 c;
U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
if (c < 256) {
Regex8BitSet &s8 = RegexStaticSets::gStaticSets->fPropSets8[opValue];
if (s8.contains(c) == false) {
break;
}
} else {
const UnicodeSet &s = RegexStaticSets::gStaticSets->fPropSets[opValue];
if (s.contains(c) == false) {
break;
}
}
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
break;
case URX_SETREF:
{
if (fp->fInputIdx >= fActiveLimit) {
fHitEnd = true;
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
}
U_ASSERT(opValue > 0 && opValue < fSets->size());
// There is input left. Pick up one char and test it for set membership.
UChar32 c;
U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
if (c<256) {
Regex8BitSet *s8 = &fPattern->fSets8[opValue];
if (s8->contains(c)) {
// The character is in the set. A Match.
break;
}
} else {
UnicodeSet* s = static_cast<UnicodeSet*>(fSets->elementAt(opValue));
if (s->contains(c)) {
// The character is in the set. A Match.
break;
}
}
// the character wasn't in the set.
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
break;
case URX_DOTANY:
{
// . matches anything, but stops at end-of-line.
if (fp->fInputIdx >= fActiveLimit) {
// At end of input. Match failed. Backtrack out.
fHitEnd = true;
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
}
// There is input left. Advance over one char, unless we've hit end-of-line
UChar32 c;
U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
if (isLineTerminator(c)) {
// End of line in normal mode. . does not match.
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
}
}
break;
case URX_DOTANY_ALL:
{
// . in dot-matches-all (including new lines) mode
if (fp->fInputIdx >= fActiveLimit) {
// At end of input. Match failed. Backtrack out.
fHitEnd = true;
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
}
// There is input left. Advance over one char, except if we are
// at a cr/lf, advance over both of them.
UChar32 c;
U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
if (c==0x0d && fp->fInputIdx < fActiveLimit) {
// In the case of a CR/LF, we need to advance over both.
if (inputBuf[fp->fInputIdx] == 0x0a) {
U16_FWD_1(inputBuf, fp->fInputIdx, fActiveLimit);
}
}
}
break;
case URX_DOTANY_UNIX:
{
// '.' operator, matches all, but stops at end-of-line.
// UNIX_LINES mode, so 0x0a is the only recognized line ending.
if (fp->fInputIdx >= fActiveLimit) {
// At end of input. Match failed. Backtrack out.
fHitEnd = true;
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
}
// There is input left. Advance over one char, unless we've hit end-of-line
UChar32 c;
U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
if (c == 0x0a) {
// End of line in normal mode. '.' does not match the \n
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
}
break;
case URX_JMP:
fp->fPatIdx = opValue;
break;
case URX_FAIL:
isMatch = false;
goto breakFromLoop;
case URX_JMP_SAV:
U_ASSERT(opValue < fPattern->fCompiledPat->size());
fp = StateSave(fp, fp->fPatIdx, status); // State save to loc following current
fp->fPatIdx = opValue; // Then JMP.
break;
case URX_JMP_SAV_X:
// This opcode is used with (x)+, when x can match a zero length string.
// Same as JMP_SAV, except conditional on the match having made forward progress.
// Destination of the JMP must be a URX_STO_INP_LOC, from which we get the
// data address of the input position at the start of the loop.
{
U_ASSERT(opValue > 0 && opValue < fPattern->fCompiledPat->size());
int32_t stoOp = static_cast<int32_t>(pat[opValue - 1]);
U_ASSERT(URX_TYPE(stoOp) == URX_STO_INP_LOC);
int32_t frameLoc = URX_VAL(stoOp);
U_ASSERT(frameLoc >= 0 && frameLoc < fFrameSize);
int32_t prevInputIdx = static_cast<int32_t>(fp->fExtra[frameLoc]);
U_ASSERT(prevInputIdx <= fp->fInputIdx);
if (prevInputIdx < fp->fInputIdx) {
// The match did make progress. Repeat the loop.
fp = StateSave(fp, fp->fPatIdx, status); // State save to loc following current
fp->fPatIdx = opValue;
fp->fExtra[frameLoc] = fp->fInputIdx;
}
// If the input position did not advance, we do nothing here,
// execution will fall out of the loop.
}
break;
case URX_CTR_INIT:
{
U_ASSERT(opValue >= 0 && opValue < fFrameSize-2);
fp->fExtra[opValue] = 0; // Set the loop counter variable to zero
// Pick up the three extra operands that CTR_INIT has, and
// skip the pattern location counter past
int32_t instrOperandLoc = static_cast<int32_t>(fp->fPatIdx);
fp->fPatIdx += 3;
int32_t loopLoc = URX_VAL(pat[instrOperandLoc]);
int32_t minCount = static_cast<int32_t>(pat[instrOperandLoc + 1]);
int32_t maxCount = static_cast<int32_t>(pat[instrOperandLoc + 2]);
U_ASSERT(minCount>=0);
U_ASSERT(maxCount>=minCount || maxCount==-1);
U_ASSERT(loopLoc>=fp->fPatIdx);
if (minCount == 0) {
fp = StateSave(fp, loopLoc+1, status);
}
if (maxCount == -1) {
fp->fExtra[opValue+1] = fp->fInputIdx; // For loop breaking.
} else if (maxCount == 0) {
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
}
break;
case URX_CTR_LOOP:
{
U_ASSERT(opValue>0 && opValue < fp->fPatIdx-2);
int32_t initOp = static_cast<int32_t>(pat[opValue]);
U_ASSERT(URX_TYPE(initOp) == URX_CTR_INIT);
int64_t *pCounter = &fp->fExtra[URX_VAL(initOp)];
int32_t minCount = static_cast<int32_t>(pat[opValue + 2]);
int32_t maxCount = static_cast<int32_t>(pat[opValue + 3]);
(*pCounter)++;
if (static_cast<uint64_t>(*pCounter) >= static_cast<uint32_t>(maxCount) && maxCount != -1) {
U_ASSERT(*pCounter == maxCount);
break;
}
if (*pCounter >= minCount) {
if (maxCount == -1) {
// Loop has no hard upper bound.
// Check that it is progressing through the input, break if it is not.
int64_t *pLastInputIdx = &fp->fExtra[URX_VAL(initOp) + 1];
if (fp->fInputIdx == *pLastInputIdx) {
break;
} else {
*pLastInputIdx = fp->fInputIdx;
}
}
fp = StateSave(fp, fp->fPatIdx, status);
} else {
// Increment time-out counter. (StateSave() does it if count >= minCount)
fTickCounter--;
if (fTickCounter <= 0) {
IncrementTime(status); // Re-initializes fTickCounter
}
}
fp->fPatIdx = opValue + 4; // Loop back.
}
break;
case URX_CTR_INIT_NG:
{
// Initialize a non-greedy loop
U_ASSERT(opValue >= 0 && opValue < fFrameSize-2);
fp->fExtra[opValue] = 0; // Set the loop counter variable to zero
// Pick up the three extra operands that CTR_INIT_NG has, and
// skip the pattern location counter past
int32_t instrOperandLoc = static_cast<int32_t>(fp->fPatIdx);
fp->fPatIdx += 3;
int32_t loopLoc = URX_VAL(pat[instrOperandLoc]);
int32_t minCount = static_cast<int32_t>(pat[instrOperandLoc + 1]);
int32_t maxCount = static_cast<int32_t>(pat[instrOperandLoc + 2]);
U_ASSERT(minCount>=0);
U_ASSERT(maxCount>=minCount || maxCount==-1);
U_ASSERT(loopLoc>fp->fPatIdx);
if (maxCount == -1) {
fp->fExtra[opValue+1] = fp->fInputIdx; // Save initial input index for loop breaking.
}
if (minCount == 0) {
if (maxCount != 0) {
fp = StateSave(fp, fp->fPatIdx, status);
}
fp->fPatIdx = loopLoc+1; // Continue with stuff after repeated block
}
}
break;
case URX_CTR_LOOP_NG:
{
// Non-greedy {min, max} loops
U_ASSERT(opValue>0 && opValue < fp->fPatIdx-2);
int32_t initOp = static_cast<int32_t>(pat[opValue]);
U_ASSERT(URX_TYPE(initOp) == URX_CTR_INIT_NG);
int64_t *pCounter = &fp->fExtra[URX_VAL(initOp)];
int32_t minCount = static_cast<int32_t>(pat[opValue + 2]);
int32_t maxCount = static_cast<int32_t>(pat[opValue + 3]);
(*pCounter)++;
if (static_cast<uint64_t>(*pCounter) >= static_cast<uint32_t>(maxCount) && maxCount != -1) {
// The loop has matched the maximum permitted number of times.
// Break out of here with no action. Matching will
// continue with the following pattern.
U_ASSERT(*pCounter == maxCount);
break;
}
if (*pCounter < minCount) {
// We haven't met the minimum number of matches yet.
// Loop back for another one.
fp->fPatIdx = opValue + 4; // Loop back.
fTickCounter--;
if (fTickCounter <= 0) {
IncrementTime(status); // Re-initializes fTickCounter
}
} else {
// We do have the minimum number of matches.
// If there is no upper bound on the loop iterations, check that the input index
// is progressing, and stop the loop if it is not.
if (maxCount == -1) {
int64_t *pLastInputIdx = &fp->fExtra[URX_VAL(initOp) + 1];
if (fp->fInputIdx == *pLastInputIdx) {
break;
}
*pLastInputIdx = fp->fInputIdx;
}
// Loop Continuation: we will fall into the pattern following the loop
// (non-greedy, don't execute loop body first), but first do
// a state save to the top of the loop, so that a match failure
// in the following pattern will try another iteration of the loop.
fp = StateSave(fp, opValue + 4, status);
}
}
break;
case URX_STO_SP:
U_ASSERT(opValue >= 0 && opValue < fPattern->fDataSize);
fData[opValue] = fStack->size();
break;
case URX_LD_SP:
{
U_ASSERT(opValue >= 0 && opValue < fPattern->fDataSize);
int32_t newStackSize = static_cast<int32_t>(fData[opValue]);
U_ASSERT(newStackSize <= fStack->size());
int64_t *newFP = fStack->getBuffer() + newStackSize - fFrameSize;
if (newFP == reinterpret_cast<int64_t*>(fp)) {
break;
}
int32_t j;
for (j=0; j<fFrameSize; j++) {
newFP[j] = reinterpret_cast<int64_t*>(fp)[j];
}
fp = reinterpret_cast<REStackFrame*>(newFP);
fStack->setSize(newStackSize);
}
break;
case URX_BACKREF:
{
U_ASSERT(opValue < fFrameSize);
int64_t groupStartIdx = fp->fExtra[opValue];
int64_t groupEndIdx = fp->fExtra[opValue+1];
U_ASSERT(groupStartIdx <= groupEndIdx);
int64_t inputIndex = fp->fInputIdx;
if (groupStartIdx < 0) {
// This capture group has not participated in the match thus far,
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize)); // FAIL, no match.
break;
}
UBool success = true;
for (int64_t groupIndex = groupStartIdx; groupIndex < groupEndIdx; ++groupIndex,++inputIndex) {
if (inputIndex >= fActiveLimit) {
success = false;
fHitEnd = true;
break;
}
if (inputBuf[groupIndex] != inputBuf[inputIndex]) {
success = false;
break;
}
}
if (success && groupStartIdx < groupEndIdx && U16_IS_LEAD(inputBuf[groupEndIdx-1]) &&
inputIndex < fActiveLimit && U16_IS_TRAIL(inputBuf[inputIndex])) {
// Capture group ended with an unpaired lead surrogate.
// Back reference is not permitted to match lead only of a surrogatge pair.
success = false;
}
if (success) {
fp->fInputIdx = inputIndex;
} else {
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
}
break;
case URX_BACKREF_I:
{
U_ASSERT(opValue < fFrameSize);
int64_t groupStartIdx = fp->fExtra[opValue];
int64_t groupEndIdx = fp->fExtra[opValue+1];
U_ASSERT(groupStartIdx <= groupEndIdx);
if (groupStartIdx < 0) {
// This capture group has not participated in the match thus far,
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize)); // FAIL, no match.
break;
}
CaseFoldingUCharIterator captureGroupItr(inputBuf, groupStartIdx, groupEndIdx);
CaseFoldingUCharIterator inputItr(inputBuf, fp->fInputIdx, fActiveLimit);
// Note: if the capture group match was of an empty string the backref
// match succeeds. Verified by testing: Perl matches succeed
// in this case, so we do too.
UBool success = true;
for (;;) {
UChar32 captureGroupChar = captureGroupItr.next();
if (captureGroupChar == U_SENTINEL) {
success = true;
break;
}
UChar32 inputChar = inputItr.next();
if (inputChar == U_SENTINEL) {
success = false;
fHitEnd = true;
break;
}
if (inputChar != captureGroupChar) {
success = false;
break;
}
}
if (success && inputItr.inExpansion()) {
// We obtained a match by consuming part of a string obtained from
// case-folding a single code point of the input text.
// This does not count as an overall match.
success = false;
}
if (success) {
fp->fInputIdx = inputItr.getIndex();
} else {
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
}
break;
case URX_STO_INP_LOC:
{
U_ASSERT(opValue >= 0 && opValue < fFrameSize);
fp->fExtra[opValue] = fp->fInputIdx;
}
break;
case URX_JMPX:
{
int32_t instrOperandLoc = static_cast<int32_t>(fp->fPatIdx);
fp->fPatIdx += 1;
int32_t dataLoc = URX_VAL(pat[instrOperandLoc]);
U_ASSERT(dataLoc >= 0 && dataLoc < fFrameSize);
int32_t savedInputIdx = static_cast<int32_t>(fp->fExtra[dataLoc]);
U_ASSERT(savedInputIdx <= fp->fInputIdx);
if (savedInputIdx < fp->fInputIdx) {
fp->fPatIdx = opValue; // JMP
} else {
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize)); // FAIL, no progress in loop.
}
}
break;
case URX_LA_START:
{
// Entering a look around block.
// Save Stack Ptr, Input Pos.
U_ASSERT(opValue>=0 && opValue+3<fPattern->fDataSize);
fData[opValue] = fStack->size();
fData[opValue+1] = fp->fInputIdx;
fData[opValue+2] = fActiveStart;
fData[opValue+3] = fActiveLimit;
fActiveStart = fLookStart; // Set the match region change for
fActiveLimit = fLookLimit; // transparent bounds.
}
break;
case URX_LA_END:
{
// Leaving a look around block.
// restore Stack Ptr, Input Pos to positions they had on entry to block.
U_ASSERT(opValue>=0 && opValue+3<fPattern->fDataSize);
int32_t stackSize = fStack->size();
int32_t newStackSize = static_cast<int32_t>(fData[opValue]);
U_ASSERT(stackSize >= newStackSize);
if (stackSize > newStackSize) {
// Copy the current top frame back to the new (cut back) top frame.
// This makes the capture groups from within the look-ahead
// expression available.
int64_t *newFP = fStack->getBuffer() + newStackSize - fFrameSize;
int32_t j;
for (j=0; j<fFrameSize; j++) {
newFP[j] = reinterpret_cast<int64_t*>(fp)[j];
}
fp = reinterpret_cast<REStackFrame*>(newFP);
fStack->setSize(newStackSize);
}
fp->fInputIdx = fData[opValue+1];
// Restore the active region bounds in the input string; they may have
// been changed because of transparent bounds on a Region.
fActiveStart = fData[opValue+2];
fActiveLimit = fData[opValue+3];
U_ASSERT(fActiveStart >= 0);
U_ASSERT(fActiveLimit <= fInputLength);
}
break;
case URX_ONECHAR_I:
if (fp->fInputIdx < fActiveLimit) {
UChar32 c;
U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
if (u_foldCase(c, U_FOLD_CASE_DEFAULT) == opValue) {
break;
}
} else {
fHitEnd = true;
}
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
case URX_STRING_I:
// Case-insensitive test input against a literal string.
// Strings require two slots in the compiled pattern, one for the
// offset to the string text, and one for the length.
// The compiled string has already been case folded.
{
const char16_t *patternString = litText + opValue;
op = static_cast<int32_t>(pat[fp->fPatIdx]);
fp->fPatIdx++;
opType = URX_TYPE(op);
opValue = URX_VAL(op);
U_ASSERT(opType == URX_STRING_LEN);
int32_t patternStringLen = opValue; // Length of the string from the pattern.
UChar32 cText;
UChar32 cPattern;
UBool success = true;
int32_t patternStringIdx = 0;
CaseFoldingUCharIterator inputIterator(inputBuf, fp->fInputIdx, fActiveLimit);
while (patternStringIdx < patternStringLen) {
U16_NEXT(patternString, patternStringIdx, patternStringLen, cPattern);
cText = inputIterator.next();
if (cText != cPattern) {
success = false;
if (cText == U_SENTINEL) {
fHitEnd = true;
}
break;
}
}
if (inputIterator.inExpansion()) {
success = false;
}
if (success) {
fp->fInputIdx = inputIterator.getIndex();
} else {
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
}
break;
case URX_LB_START:
{
// Entering a look-behind block.
// Save Stack Ptr, Input Pos and active input region.
// TODO: implement transparent bounds. Ticket #6067
U_ASSERT(opValue>=0 && opValue+4<fPattern->fDataSize);
fData[opValue] = fStack->size();
fData[opValue+1] = fp->fInputIdx;
// Save input string length, then reset to pin any matches to end at
// the current position.
fData[opValue+2] = fActiveStart;
fData[opValue+3] = fActiveLimit;
fActiveStart = fRegionStart;
fActiveLimit = fp->fInputIdx;
// Init the variable containing the start index for attempted matches.
fData[opValue+4] = -1;
}
break;
case URX_LB_CONT:
{
// Positive Look-Behind, at top of loop checking for matches of LB expression
// at all possible input starting positions.
// Fetch the min and max possible match lengths. They are the operands
// of this op in the pattern.
int32_t minML = static_cast<int32_t>(pat[fp->fPatIdx++]);
int32_t maxML = static_cast<int32_t>(pat[fp->fPatIdx++]);
U_ASSERT(minML <= maxML);
U_ASSERT(minML >= 0);
// Fetch (from data) the last input index where a match was attempted.
U_ASSERT(opValue>=0 && opValue+4<fPattern->fDataSize);
int64_t &lbStartIdx = fData[opValue+4];
if (lbStartIdx < 0) {
// First time through loop.
lbStartIdx = fp->fInputIdx - minML;
if (lbStartIdx > 0 && lbStartIdx < fInputLength) {
U16_SET_CP_START(inputBuf, 0, lbStartIdx);
}
} else {
// 2nd through nth time through the loop.
// Back up start position for match by one.
if (lbStartIdx == 0) {
lbStartIdx--;
} else {
U16_BACK_1(inputBuf, 0, lbStartIdx);
}
}
if (lbStartIdx < 0 || lbStartIdx < fp->fInputIdx - maxML) {
// We have tried all potential match starting points without
// getting a match. Backtrack out, and out of the
// Look Behind altogether.
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
fActiveStart = fData[opValue+2];
fActiveLimit = fData[opValue+3];
U_ASSERT(fActiveStart >= 0);
U_ASSERT(fActiveLimit <= fInputLength);
break;
}
// Save state to this URX_LB_CONT op, so failure to match will repeat the loop.
// (successful match will fall off the end of the loop.)
fp = StateSave(fp, fp->fPatIdx-3, status);
fp->fInputIdx = lbStartIdx;
}
break;
case URX_LB_END:
// End of a look-behind block, after a successful match.
{
U_ASSERT(opValue>=0 && opValue+4<fPattern->fDataSize);
if (fp->fInputIdx != fActiveLimit) {
// The look-behind expression matched, but the match did not
// extend all the way to the point that we are looking behind from.
// FAIL out of here, which will take us back to the LB_CONT, which
// will retry the match starting at another position or fail
// the look-behind altogether, whichever is appropriate.
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
}
// Look-behind match is good. Restore the original input string region,
// which had been truncated to pin the end of the lookbehind match to the
// position being looked-behind.
fActiveStart = fData[opValue+2];
fActiveLimit = fData[opValue+3];
U_ASSERT(fActiveStart >= 0);
U_ASSERT(fActiveLimit <= fInputLength);
}
break;
case URX_LBN_CONT:
{
// Negative Look-Behind, at top of loop checking for matches of LB expression
// at all possible input starting positions.
// Fetch the extra parameters of this op.
int32_t minML = static_cast<int32_t>(pat[fp->fPatIdx++]);
int32_t maxML = static_cast<int32_t>(pat[fp->fPatIdx++]);
int32_t continueLoc = static_cast<int32_t>(pat[fp->fPatIdx++]);
continueLoc = URX_VAL(continueLoc);
U_ASSERT(minML <= maxML);
U_ASSERT(minML >= 0);
U_ASSERT(continueLoc > fp->fPatIdx);
// Fetch (from data) the last input index where a match was attempted.
U_ASSERT(opValue>=0 && opValue+4<fPattern->fDataSize);
int64_t &lbStartIdx = fData[opValue+4];
if (lbStartIdx < 0) {
// First time through loop.
lbStartIdx = fp->fInputIdx - minML;
if (lbStartIdx > 0 && lbStartIdx < fInputLength) {
U16_SET_CP_START(inputBuf, 0, lbStartIdx);
}
} else {
// 2nd through nth time through the loop.
// Back up start position for match by one.
if (lbStartIdx == 0) {
lbStartIdx--; // Because U16_BACK is unsafe starting at 0.
} else {
U16_BACK_1(inputBuf, 0, lbStartIdx);
}
}
if (lbStartIdx < 0 || lbStartIdx < fp->fInputIdx - maxML) {
// We have tried all potential match starting points without
// getting a match, which means that the negative lookbehind as
// a whole has succeeded. Jump forward to the continue location
fActiveStart = fData[opValue+2];
fActiveLimit = fData[opValue+3];
U_ASSERT(fActiveStart >= 0);
U_ASSERT(fActiveLimit <= fInputLength);
fp->fPatIdx = continueLoc;
break;
}
// Save state to this URX_LB_CONT op, so failure to match will repeat the loop.
// (successful match will cause a FAIL out of the loop altogether.)
fp = StateSave(fp, fp->fPatIdx-4, status);
fp->fInputIdx = lbStartIdx;
}
break;
case URX_LBN_END:
// End of a negative look-behind block, after a successful match.
{
U_ASSERT(opValue>=0 && opValue+4<fPattern->fDataSize);
if (fp->fInputIdx != fActiveLimit) {
// The look-behind expression matched, but the match did not
// extend all the way to the point that we are looking behind from.
// FAIL out of here, which will take us back to the LB_CONT, which
// will retry the match starting at another position or succeed
// the look-behind altogether, whichever is appropriate.
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
break;
}
// Look-behind expression matched, which means look-behind test as
// a whole Fails
// Restore the original input string length, which had been truncated
// inorder to pin the end of the lookbehind match
// to the position being looked-behind.
fActiveStart = fData[opValue+2];
fActiveLimit = fData[opValue+3];
U_ASSERT(fActiveStart >= 0);
U_ASSERT(fActiveLimit <= fInputLength);
// Restore original stack position, discarding any state saved
// by the successful pattern match.
U_ASSERT(opValue>=0 && opValue+1<fPattern->fDataSize);
int32_t newStackSize = static_cast<int32_t>(fData[opValue]);
U_ASSERT(fStack->size() > newStackSize);
fStack->setSize(newStackSize);
// FAIL, which will take control back to someplace
// prior to entering the look-behind test.
fp = reinterpret_cast<REStackFrame*>(fStack->popFrame(fFrameSize));
}
break;
case URX_LOOP_SR_I:
// Loop Initialization for the optimized implementation of
// [some character set]*
// This op scans through all matching input.
// The following LOOP_C op emulates stack unwinding if the following pattern fails.
{
U_ASSERT(opValue > 0 && opValue < fSets->size());
Regex8BitSet *s8 = &fPattern->fSets8[opValue];
UnicodeSet* s = static_cast<UnicodeSet*>(fSets->elementAt(opValue));
// Loop through input, until either the input is exhausted or
// we reach a character that is not a member of the set.
int32_t ix = static_cast<int32_t>(fp->fInputIdx);
for (;;) {
if (ix >= fActiveLimit) {
fHitEnd = true;
break;
}
UChar32 c;
U16_NEXT(inputBuf, ix, fActiveLimit, c);
if (c<256) {
if (s8->contains(c) == false) {
U16_BACK_1(inputBuf, 0, ix);
break;
}
} else {
if (s->contains(c) == false) {
U16_BACK_1(inputBuf, 0, ix);
break;
}
}
}
// If there were no matching characters, skip over the loop altogether.
// The loop doesn't run at all, a * op always succeeds.
if (ix == fp->fInputIdx) {
fp->fPatIdx++; // skip the URX_LOOP_C op.
break;
}
// Peek ahead in the compiled pattern, to the URX_LOOP_C that
// must follow. It's operand is the stack location
// that holds the starting input index for the match of this [set]*
int32_t loopcOp = static_cast<int32_t>(pat[fp->fPatIdx]);
U_ASSERT(URX_TYPE(loopcOp) == URX_LOOP_C);
int32_t stackLoc = URX_VAL(loopcOp);
U_ASSERT(stackLoc >= 0 && stackLoc < fFrameSize);
fp->fExtra[stackLoc] = fp->fInputIdx;
fp->fInputIdx = ix;
// Save State to the URX_LOOP_C op that follows this one,
// so that match failures in the following code will return to there.
// Then bump the pattern idx so the LOOP_C is skipped on the way out of here.
fp = StateSave(fp, fp->fPatIdx, status);
fp->fPatIdx++;
}
break;
case URX_LOOP_DOT_I:
// Loop Initialization for the optimized implementation of .*
// This op scans through all remaining input.
// The following LOOP_C op emulates stack unwinding if the following pattern fails.
{
// Loop through input until the input is exhausted (we reach an end-of-line)
// In DOTALL mode, we can just go straight to the end of the input.
int32_t ix;
if ((opValue & 1) == 1) {
// Dot-matches-All mode. Jump straight to the end of the string.
ix = static_cast<int32_t>(fActiveLimit);
fHitEnd = true;
} else {
// NOT DOT ALL mode. Line endings do not match '.'
// Scan forward until a line ending or end of input.
ix = static_cast<int32_t>(fp->fInputIdx);
for (;;) {
if (ix >= fActiveLimit) {
fHitEnd = true;
break;
}
UChar32 c;
U16_NEXT(inputBuf, ix, fActiveLimit, c); // c = inputBuf[ix++]
if ((c & 0x7f) <= 0x29) { // Fast filter of non-new-line-s
if ((c == 0x0a) || // 0x0a is newline in both modes.
(((opValue & 2) == 0) && // IF not UNIX_LINES mode
isLineTerminator(c))) {
// char is a line ending. Put the input pos back to the
// line ending char, and exit the scanning loop.
U16_BACK_1(inputBuf, 0, ix);
break;
}
}
}
}
// If there were no matching characters, skip over the loop altogether.
// The loop doesn't run at all, a * op always succeeds.
if (ix == fp->fInputIdx) {
fp->fPatIdx++; // skip the URX_LOOP_C op.
break;
}
// Peek ahead in the compiled pattern, to the URX_LOOP_C that
// must follow. It's operand is the stack location
// that holds the starting input index for the match of this .*
int32_t loopcOp = static_cast<int32_t>(pat[fp->fPatIdx]);
U_ASSERT(URX_TYPE(loopcOp) == URX_LOOP_C);
int32_t stackLoc = URX_VAL(loopcOp);
U_ASSERT(stackLoc >= 0 && stackLoc < fFrameSize);
fp->fExtra[stackLoc] = fp->fInputIdx;
fp->fInputIdx = ix;
// Save State to the URX_LOOP_C op that follows this one,
// so that match failures in the following code will return to there.
// Then bump the pattern idx so the LOOP_C is skipped on the way out of here.
fp = StateSave(fp, fp->fPatIdx, status);
fp->fPatIdx++;
}
break;
case URX_LOOP_C:
{
U_ASSERT(opValue>=0 && opValue<fFrameSize);
backSearchIndex = static_cast<int32_t>(fp->fExtra[opValue]);
U_ASSERT(backSearchIndex <= fp->fInputIdx);
if (backSearchIndex == fp->fInputIdx) {
// We've backed up the input idx to the point that the loop started.
// The loop is done. Leave here without saving state.
// Subsequent failures won't come back here.
break;
}
// Set up for the next iteration of the loop, with input index
// backed up by one from the last time through,
// and a state save to this instruction in case the following code fails again.
// (We're going backwards because this loop emulates stack unwinding, not
// the initial scan forward.)
U_ASSERT(fp->fInputIdx > 0);
UChar32 prevC;
U16_PREV(inputBuf, 0, fp->fInputIdx, prevC); // !!!: should this 0 be one of f*Limit?
if (prevC == 0x0a &&
fp->fInputIdx > backSearchIndex &&
inputBuf[fp->fInputIdx-1] == 0x0d) {
int32_t prevOp = static_cast<int32_t>(pat[fp->fPatIdx - 2]);
if (URX_TYPE(prevOp) == URX_LOOP_DOT_I) {
// .*, stepping back over CRLF pair.
U16_BACK_1(inputBuf, 0, fp->fInputIdx);
}
}
fp = StateSave(fp, fp->fPatIdx-1, status);
}
break;
default:
// Trouble. The compiled pattern contains an entry with an
// unrecognized type tag.
UPRV_UNREACHABLE_ASSERT;
// Unknown opcode type in opType = URX_TYPE(pat[fp->fPatIdx]). But we have
// reports of this in production code, don't use UPRV_UNREACHABLE_EXIT.
// See ICU-21669.
status = U_INTERNAL_PROGRAM_ERROR;
}
if (U_FAILURE(status)) {
isMatch = false;
break;
}
}
breakFromLoop:
fMatch = isMatch;
if (isMatch) {
fLastMatchEnd = fMatchEnd;
fMatchStart = startIdx;
fMatchEnd = fp->fInputIdx;
}
#ifdef REGEX_RUN_DEBUG
if (fTraceDebug) {
if (isMatch) {
printf("Match. start=%ld end=%ld\n\n", fMatchStart, fMatchEnd);
} else {
printf("No match\n\n");
}
}
#endif
fFrame = fp; // The active stack frame when the engine stopped.
// Contains the capture group results that we need to
// access later.
}