//
// file: regexcmp.cpp
//
-// Copyright (C) 2002-2010 International Business Machines Corporation and others.
+// Copyright (C) 2002-2013 International Business Machines Corporation and others.
// All Rights Reserved.
//
// This file contains the ICU regular expression compiler, which is responsible
#include "unicode/parsepos.h"
#include "unicode/parseerr.h"
#include "unicode/regex.h"
-#include "util.h"
+#include "unicode/utf.h"
+#include "unicode/utf16.h"
+#include "patternprops.h"
#include "putilimp.h"
#include "cmemory.h"
#include "cstring.h"
fMatchOpenParen = -1;
fMatchCloseParen = -1;
- fStringOpStart = -1;
if (U_SUCCESS(status) && U_FAILURE(rxp->fDeferredStatus)) {
status = rxp->fDeferredStatus;
UParseError &pp, // Error position info
UErrorCode &e) // Error Code
{
- fRXPat->fPatternString = new UnicodeString(pat);
+ fRXPat->fPatternString = new UnicodeString(pat);
UText patternText = UTEXT_INITIALIZER;
utext_openConstUnicodeString(&patternText, fRXPat->fPatternString, &e);
fPatternLength = utext_nativeLength(pat);
uint16_t state = 1;
const RegexTableEl *tableEl;
+
+ // UREGEX_LITERAL force entire pattern to be treated as a literal string.
+ if (fModeFlags & UREGEX_LITERAL) {
+ fQuoteMode = TRUE;
+ }
+
nextChar(fC); // Fetch the first char from the pattern string.
//
if (tableEl->fCharClass >= 128 && tableEl->fCharClass < 240 && // Table specs a char class &&
fC.fQuoted == FALSE && // char is not escaped &&
fC.fChar != (UChar32)-1) { // char is not EOF
+ U_ASSERT(tableEl->fCharClass <= 137);
if (RegexStaticSets::gStaticSets->fRuleSets[tableEl->fCharClass-128].contains(fC.fChar)) {
// Table row specified a character class, or set of characters,
// and the current char matches it.
// present in the saved state: the input string position (int64_t) and
// the position in the compiled pattern.
//
- fRXPat->fFrameSize+=RESTACKFRAME_HDRCOUNT;
+ allocateStackData(RESTACKFRAME_HDRCOUNT);
//
// Optimization pass 1: NOPs, back-references, and case-folding
// the start of an ( grouping.
//4 NOP Resreved, will be replaced by a save if there are
// OR | operators at the top level
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_STATE_SAVE, 2), *fStatus);
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_JMP, 3), *fStatus);
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_FAIL, 0), *fStatus);
+ appendOp(URX_BUILD(URX_STATE_SAVE, 2));
+ appendOp(URX_BUILD(URX_JMP, 3));
+ appendOp(URX_BUILD(URX_FAIL, 0));
// Standard open nonCapture paren action emits the two NOPs and
// sets up the paren stack frame.
}
// add the END operation to the compiled pattern.
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_END, 0), *fStatus);
+ appendOp(URX_BUILD(URX_END, 0));
// Terminate the pattern compilation state machine.
returnVal = FALSE;
case doOrOperator:
// Scanning a '|', as in (A|B)
{
+ // Generate code for any pending literals preceding the '|'
+ fixLiterals(FALSE);
+
// Insert a SAVE operation at the start of the pattern section preceding
// this OR at this level. This SAVE will branch the match forward
// to the right hand side of the OR in the event that the left hand
// the JMP will eventually be the location following the ')' for the
// group. This will be patched in later, when the ')' is encountered.
op = URX_BUILD(URX_JMP, 0);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
// Push the position of the newly added JMP op onto the parentheses stack.
// This registers if for fixup when this block's close paren is encountered.
// Append a NOP to the compiled pattern. This is the slot reserved
// for a SAVE in the event that there is yet another '|' following
// this one.
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
+ appendOp(URX_BUILD(URX_NOP, 0));
fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus);
}
break;
// encountered. This will be promoted to a completed capture when (and if) the corresponding
// END_CAPTURE is encountered.
{
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
- int32_t varsLoc = fRXPat->fFrameSize; // Reserve three slots in match stack frame.
- fRXPat->fFrameSize += 3;
- int32_t cop = URX_BUILD(URX_START_CAPTURE, varsLoc);
- fRXPat->fCompiledPat->addElement(cop, *fStatus);
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
+ fixLiterals();
+ appendOp(URX_BUILD(URX_NOP, 0));
+ int32_t varsLoc = allocateStackData(3); // Reserve three slots in match stack frame.
+ int32_t cop = URX_BUILD(URX_START_CAPTURE, varsLoc);
+ appendOp(cop);
+ appendOp(URX_BUILD(URX_NOP, 0));
// On the Parentheses stack, start a new frame and add the postions
// of the two NOPs. Depending on what follows in the pattern, the
// - NOP, which may later be replaced by a save-state if there
// is an '|' alternation within the parens.
{
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
+ fixLiterals();
+ appendOp(URX_BUILD(URX_NOP, 0));
+ appendOp(URX_BUILD(URX_NOP, 0));
// On the Parentheses stack, start a new frame and add the postions
// of the two NOPs.
// - NOP, which may later be replaced by a save-state if there
// is an '|' alternation within the parens.
{
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
- int32_t varLoc = fRXPat->fDataSize; // Reserve a data location for saving the
- fRXPat->fDataSize += 1; // state stack ptr.
- int32_t stoOp = URX_BUILD(URX_STO_SP, varLoc);
- fRXPat->fCompiledPat->addElement(stoOp, *fStatus);
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
+ fixLiterals();
+ appendOp(URX_BUILD(URX_NOP, 0));
+ int32_t varLoc = allocateData(1); // Reserve a data location for saving the state stack ptr.
+ int32_t stoOp = URX_BUILD(URX_STO_SP, varLoc);
+ appendOp(stoOp);
+ appendOp(URX_BUILD(URX_NOP, 0));
// On the Parentheses stack, start a new frame and add the postions
// of the two NOPs. Depending on what follows in the pattern, the
//
// Two data slots are reserved, for saving the stack ptr and the input position.
{
- int32_t dataLoc = fRXPat->fDataSize;
- fRXPat->fDataSize += 2;
+ fixLiterals();
+ int32_t dataLoc = allocateData(2);
int32_t op = URX_BUILD(URX_LA_START, dataLoc);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
op = URX_BUILD(URX_STATE_SAVE, fRXPat->fCompiledPat->size()+ 2);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
op = URX_BUILD(URX_JMP, fRXPat->fCompiledPat->size()+ 3);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
-
+ appendOp(op);
+
op = URX_BUILD(URX_LA_END, dataLoc);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
op = URX_BUILD(URX_BACKTRACK, 0);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
-
+ appendOp(op);
+
op = URX_BUILD(URX_NOP, 0);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
+ appendOp(op);
// On the Parentheses stack, start a new frame and add the postions
// of the NOPs.
// 7. END_LA // Restore match region, in case look-ahead was using
// an alternate (transparent) region.
{
- int32_t dataLoc = fRXPat->fDataSize;
- fRXPat->fDataSize += 2;
+ fixLiterals();
+ int32_t dataLoc = allocateData(2);
int32_t op = URX_BUILD(URX_LA_START, dataLoc);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
op = URX_BUILD(URX_STATE_SAVE, 0); // dest address will be patched later.
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
op = URX_BUILD(URX_NOP, 0);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
// On the Parentheses stack, start a new frame and add the postions
// of the StateSave and NOP.
// 2: Start index of match current match attempt.
// 3: Original Input String len.
+ // Generate match code for any pending literals.
+ fixLiterals();
+
// Allocate data space
- int32_t dataLoc = fRXPat->fDataSize;
- fRXPat->fDataSize += 4;
+ int32_t dataLoc = allocateData(4);
// Emit URX_LB_START
int32_t op = URX_BUILD(URX_LB_START, dataLoc);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
// Emit URX_LB_CONT
op = URX_BUILD(URX_LB_CONT, dataLoc);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
- fRXPat->fCompiledPat->addElement(0, *fStatus); // MinMatchLength. To be filled later.
- fRXPat->fCompiledPat->addElement(0, *fStatus); // MaxMatchLength. To be filled later.
+ appendOp(op);
+ appendOp(0); // MinMatchLength. To be filled later.
+ appendOp(0); // MaxMatchLength. To be filled later.
// Emit the NOP
op = URX_BUILD(URX_NOP, 0);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
+ appendOp(op);
// On the Parentheses stack, start a new frame and add the postions
// of the URX_LB_CONT and the NOP.
// 2: Start index of match current match attempt.
// 3: Original Input String len.
+ // Generate match code for any pending literals.
+ fixLiterals();
+
// Allocate data space
- int32_t dataLoc = fRXPat->fDataSize;
- fRXPat->fDataSize += 4;
+ int32_t dataLoc = allocateData(4);
// Emit URX_LB_START
int32_t op = URX_BUILD(URX_LB_START, dataLoc);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
// Emit URX_LBN_CONT
op = URX_BUILD(URX_LBN_CONT, dataLoc);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
- fRXPat->fCompiledPat->addElement(0, *fStatus); // MinMatchLength. To be filled later.
- fRXPat->fCompiledPat->addElement(0, *fStatus); // MaxMatchLength. To be filled later.
- fRXPat->fCompiledPat->addElement(0, *fStatus); // Continue Loc. To be filled later.
+ appendOp(op);
+ appendOp(0); // MinMatchLength. To be filled later.
+ appendOp(0); // MaxMatchLength. To be filled later.
+ appendOp(0); // Continue Loc. To be filled later.
// Emit the NOP
op = URX_BUILD(URX_NOP, 0);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
+ appendOp(op);
// On the Parentheses stack, start a new frame and add the postions
// of the URX_LB_CONT and the NOP.
if (URX_TYPE(repeatedOp) == URX_SETREF) {
// Emit optimized code for [char set]+
int32_t loopOpI = URX_BUILD(URX_LOOP_SR_I, URX_VAL(repeatedOp));
- fRXPat->fCompiledPat->addElement(loopOpI, *fStatus);
- frameLoc = fRXPat->fFrameSize;
- fRXPat->fFrameSize++;
+ appendOp(loopOpI);
+ frameLoc = allocateStackData(1);
int32_t loopOpC = URX_BUILD(URX_LOOP_C, frameLoc);
- fRXPat->fCompiledPat->addElement(loopOpC, *fStatus);
+ appendOp(loopOpC);
break;
}
if (fModeFlags & UREGEX_UNIX_LINES) {
loopOpI |= 2;
}
- fRXPat->fCompiledPat->addElement(loopOpI, *fStatus);
- frameLoc = fRXPat->fFrameSize;
- fRXPat->fFrameSize++;
+ appendOp(loopOpI);
+ frameLoc = allocateStackData(1);
int32_t loopOpC = URX_BUILD(URX_LOOP_C, frameLoc);
- fRXPat->fCompiledPat->addElement(loopOpC, *fStatus);
+ appendOp(loopOpC);
break;
}
// Zero length match is possible.
// Emit the code sequence that can handle it.
insertOp(topLoc);
- frameLoc = fRXPat->fFrameSize;
- fRXPat->fFrameSize++;
+ frameLoc = allocateStackData(1);
int32_t op = URX_BUILD(URX_STO_INP_LOC, frameLoc);
fRXPat->fCompiledPat->setElementAt(op, topLoc);
op = URX_BUILD(URX_JMP_SAV_X, topLoc+1);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
} else {
// Simpler code when the repeated body must match something non-empty
int32_t jmpOp = URX_BUILD(URX_JMP_SAV, topLoc);
- fRXPat->fCompiledPat->addElement(jmpOp, *fStatus);
+ appendOp(jmpOp);
}
}
break;
{
int32_t topLoc = blockTopLoc(FALSE);
int32_t saveStateOp = URX_BUILD(URX_STATE_SAVE, topLoc);
- fRXPat->fCompiledPat->addElement(saveStateOp, *fStatus);
+ appendOp(saveStateOp);
}
break;
fRXPat->fCompiledPat->setElementAt(jmp1_op, jmp1_loc);
int32_t jmp2_op = URX_BUILD(URX_JMP, jmp2_loc+2);
- fRXPat->fCompiledPat->addElement(jmp2_op, *fStatus);
+ appendOp(jmp2_op);
int32_t save_op = URX_BUILD(URX_STATE_SAVE, jmp1_loc+1);
- fRXPat->fCompiledPat->addElement(save_op, *fStatus);
+ appendOp(save_op);
}
break;
// Emit optimized code for a [char set]*
int32_t loopOpI = URX_BUILD(URX_LOOP_SR_I, URX_VAL(repeatedOp));
fRXPat->fCompiledPat->setElementAt(loopOpI, topLoc);
- dataLoc = fRXPat->fFrameSize;
- fRXPat->fFrameSize++;
+ dataLoc = allocateStackData(1);
int32_t loopOpC = URX_BUILD(URX_LOOP_C, dataLoc);
- fRXPat->fCompiledPat->addElement(loopOpC, *fStatus);
+ appendOp(loopOpC);
break;
}
loopOpI |= 2;
}
fRXPat->fCompiledPat->setElementAt(loopOpI, topLoc);
- dataLoc = fRXPat->fFrameSize;
- fRXPat->fFrameSize++;
+ dataLoc = allocateStackData(1);
int32_t loopOpC = URX_BUILD(URX_LOOP_C, dataLoc);
- fRXPat->fCompiledPat->addElement(loopOpC, *fStatus);
+ appendOp(loopOpC);
break;
}
}
// extra loop-breaking code.
if (minMatchLength(saveStateLoc, fRXPat->fCompiledPat->size()-1) == 0) {
insertOp(saveStateLoc);
- dataLoc = fRXPat->fFrameSize;
- fRXPat->fFrameSize++;
+ dataLoc = allocateStackData(1);
int32_t op = URX_BUILD(URX_STO_INP_LOC, dataLoc);
fRXPat->fCompiledPat->setElementAt(op, saveStateLoc+1);
fRXPat->fCompiledPat->setElementAt(saveStateOp, saveStateLoc);
// Append the URX_JMP_SAV or URX_JMPX operation to the compiled pattern.
- fRXPat->fCompiledPat->addElement(jmpOp, *fStatus);
+ appendOp(jmpOp);
}
break;
int32_t jmpOp = URX_BUILD(URX_JMP, saveLoc);
int32_t stateSaveOp = URX_BUILD(URX_STATE_SAVE, jmpLoc+1);
fRXPat->fCompiledPat->setElementAt(jmpOp, jmpLoc);
- fRXPat->fCompiledPat->addElement(stateSaveOp, *fStatus);
+ appendOp(stateSaveOp);
}
break;
// First the STO_SP before the start of the loop
insertOp(topLoc);
- int32_t varLoc = fRXPat->fDataSize; // Reserve a data location for saving the
- fRXPat->fDataSize += 1; // state stack ptr.
- int32_t op = URX_BUILD(URX_STO_SP, varLoc);
+
+ int32_t varLoc = allocateData(1); // Reserve a data location for saving the
+ int32_t op = URX_BUILD(URX_STO_SP, varLoc);
fRXPat->fCompiledPat->setElementAt(op, topLoc);
int32_t loopOp = (int32_t)fRXPat->fCompiledPat->popi();
// Then the LD_SP after the end of the loop
op = URX_BUILD(URX_LD_SP, varLoc);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
}
break;
case doDotAny:
// scanned a ".", match any single character.
{
+ fixLiterals(FALSE);
int32_t op;
if (fModeFlags & UREGEX_DOTALL) {
op = URX_BUILD(URX_DOTANY_ALL, 0);
} else {
op = URX_BUILD(URX_DOTANY, 0);
}
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
}
break;
case doCaret:
{
+ fixLiterals(FALSE);
int32_t op = 0;
if ( (fModeFlags & UREGEX_MULTILINE) == 0 && (fModeFlags & UREGEX_UNIX_LINES) == 0) {
op = URX_CARET;
} else if ((fModeFlags & UREGEX_MULTILINE) != 0 && (fModeFlags & UREGEX_UNIX_LINES) != 0) {
op = URX_CARET_M_UNIX;
}
- fRXPat->fCompiledPat->addElement(URX_BUILD(op, 0), *fStatus);
+ appendOp(URX_BUILD(op, 0));
}
break;
case doDollar:
{
+ fixLiterals(FALSE);
int32_t op = 0;
if ( (fModeFlags & UREGEX_MULTILINE) == 0 && (fModeFlags & UREGEX_UNIX_LINES) == 0) {
op = URX_DOLLAR;
} else if ((fModeFlags & UREGEX_MULTILINE) != 0 && (fModeFlags & UREGEX_UNIX_LINES) != 0) {
op = URX_DOLLAR_MD;
}
- fRXPat->fCompiledPat->addElement(URX_BUILD(op, 0), *fStatus);
+ appendOp(URX_BUILD(op, 0));
}
break;
case doBackslashA:
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_CARET, 0), *fStatus);
+ fixLiterals(FALSE);
+ appendOp(URX_BUILD(URX_CARET, 0));
break;
case doBackslashB:
error(U_UNSUPPORTED_ERROR);
}
#endif
+ fixLiterals(FALSE);
int32_t op = (fModeFlags & UREGEX_UWORD)? URX_BACKSLASH_BU : URX_BACKSLASH_B;
- fRXPat->fCompiledPat->addElement(URX_BUILD(op, 1), *fStatus);
+ appendOp(URX_BUILD(op, 1));
}
break;
error(U_UNSUPPORTED_ERROR);
}
#endif
+ fixLiterals(FALSE);
int32_t op = (fModeFlags & UREGEX_UWORD)? URX_BACKSLASH_BU : URX_BACKSLASH_B;
- fRXPat->fCompiledPat->addElement(URX_BUILD(op, 0), *fStatus);
+ appendOp(URX_BUILD(op, 0));
}
break;
case doBackslashD:
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_D, 1), *fStatus);
+ fixLiterals(FALSE);
+ appendOp(URX_BUILD(URX_BACKSLASH_D, 1));
break;
case doBackslashd:
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_D, 0), *fStatus);
+ fixLiterals(FALSE);
+ appendOp(URX_BUILD(URX_BACKSLASH_D, 0));
break;
case doBackslashG:
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_G, 0), *fStatus);
+ fixLiterals(FALSE);
+ appendOp(URX_BUILD(URX_BACKSLASH_G, 0));
break;
case doBackslashS:
- fRXPat->fCompiledPat->addElement(
- URX_BUILD(URX_STAT_SETREF_N, URX_ISSPACE_SET), *fStatus);
+ fixLiterals(FALSE);
+ appendOp(URX_BUILD(URX_STAT_SETREF_N, URX_ISSPACE_SET));
break;
case doBackslashs:
- fRXPat->fCompiledPat->addElement(
- URX_BUILD(URX_STATIC_SETREF, URX_ISSPACE_SET), *fStatus);
+ fixLiterals(FALSE);
+ appendOp(URX_BUILD(URX_STATIC_SETREF, URX_ISSPACE_SET));
break;
case doBackslashW:
- fRXPat->fCompiledPat->addElement(
- URX_BUILD(URX_STAT_SETREF_N, URX_ISWORD_SET), *fStatus);
+ fixLiterals(FALSE);
+ appendOp(URX_BUILD(URX_STAT_SETREF_N, URX_ISWORD_SET));
break;
case doBackslashw:
- fRXPat->fCompiledPat->addElement(
- URX_BUILD(URX_STATIC_SETREF, URX_ISWORD_SET), *fStatus);
+ fixLiterals(FALSE);
+ appendOp(URX_BUILD(URX_STATIC_SETREF, URX_ISWORD_SET));
break;
case doBackslashX:
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_X, 0), *fStatus);
+ fixLiterals(FALSE);
+ appendOp(URX_BUILD(URX_BACKSLASH_X, 0));
break;
case doBackslashZ:
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_DOLLAR, 0), *fStatus);
+ fixLiterals(FALSE);
+ appendOp(URX_BUILD(URX_DOLLAR, 0));
break;
case doBackslashz:
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_Z, 0), *fStatus);
+ fixLiterals(FALSE);
+ appendOp(URX_BUILD(URX_BACKSLASH_Z, 0));
break;
case doEscapeError:
break;
case doExit:
+ fixLiterals(FALSE);
returnVal = FALSE;
break;
case doProperty:
{
+ fixLiterals(FALSE);
UnicodeSet *theSet = scanProp();
compileSet(theSet);
}
// Because capture groups can be forward-referenced by back-references,
// we fill the operand with the capture group number. At the end
// of compilation, it will be changed to the variable's location.
- U_ASSERT(groupNum > 0);
+ U_ASSERT(groupNum > 0); // Shouldn't happen. '\0' begins an octal escape sequence,
+ // and shouldn't enter this code path at all.
+ fixLiterals(FALSE);
int32_t op;
if (fModeFlags & UREGEX_CASE_INSENSITIVE) {
op = URX_BUILD(URX_BACKREF_I, groupNum);
} else {
op = URX_BUILD(URX_BACKREF, groupNum);
}
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
}
break;
{
// Emit the STO_SP
int32_t topLoc = blockTopLoc(TRUE);
- int32_t stoLoc = fRXPat->fDataSize;
- fRXPat->fDataSize++; // Reserve the data location for storing save stack ptr.
+ int32_t stoLoc = allocateData(1); // Reserve the data location for storing save stack ptr.
int32_t op = URX_BUILD(URX_STO_SP, stoLoc);
fRXPat->fCompiledPat->setElementAt(op, topLoc);
// Emit the STATE_SAVE
op = URX_BUILD(URX_STATE_SAVE, fRXPat->fCompiledPat->size()+2);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
// Emit the JMP
op = URX_BUILD(URX_JMP, topLoc+1);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
// Emit the LD_SP
op = URX_BUILD(URX_LD_SP, stoLoc);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
}
break;
insertOp(topLoc);
// emit STO_SP loc
- int32_t stoLoc = fRXPat->fDataSize;
- fRXPat->fDataSize++; // Reserve the data location for storing save stack ptr.
+ int32_t stoLoc = allocateData(1); // Reserve the data location for storing save stack ptr.
int32_t op = URX_BUILD(URX_STO_SP, stoLoc);
fRXPat->fCompiledPat->setElementAt(op, topLoc);
// Append the JMP operation.
op = URX_BUILD(URX_JMP, topLoc+1);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
// Emit the LD_SP loc
op = URX_BUILD(URX_LD_SP, stoLoc);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
}
break;
insertOp(topLoc);
// Emit the STO_SP
- int32_t stoLoc = fRXPat->fDataSize;
- fRXPat->fDataSize++; // Reserve the data location for storing save stack ptr.
+ int32_t stoLoc = allocateData(1); // Reserve the data location for storing save stack ptr.
int32_t op = URX_BUILD(URX_STO_SP, stoLoc);
fRXPat->fCompiledPat->setElementAt(op, topLoc);
// Emit the LD_SP
op = URX_BUILD(URX_LD_SP, stoLoc);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
}
break;
break;
case doSetMatchMode:
+ // Emit code to match any pending literals, using the not-yet changed match mode.
+ fixLiterals();
+
// We've got a (?i) or similar. The match mode is being changed, but
// the change is not scoped to a parenthesized block.
U_ASSERT(fNewModeFlags < 0);
fModeFlags = fNewModeFlags;
- // Prevent any string from spanning across the change of match mode.
- // Otherwise the pattern "abc(?i)def" would make a single string of "abcdef"
- fixLiterals();
break;
// - NOP, which may later be replaced by a save-state if there
// is an '|' alternation within the parens.
{
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
+ fixLiterals(FALSE);
+ appendOp(URX_BUILD(URX_NOP, 0));
+ appendOp(URX_BUILD(URX_NOP, 0));
// On the Parentheses stack, start a new frame and add the postions
// of the two NOPs (a normal non-capturing () frame, except for the
}
case doSetBegin:
+ fixLiterals(FALSE);
fSetStack.push(new UnicodeSet(), *fStatus);
fSetOpStack.push(setStart, *fStatus);
if ((fModeFlags & UREGEX_CASE_INSENSITIVE) != 0) {
break;
}
-
default:
U_ASSERT(FALSE);
error(U_REGEX_INTERNAL_ERROR);
// or an escape sequence that reduces to a character.
// Add it to the string containing all literal chars/strings from
// the pattern.
-// If we are in a pattern string already, add the new char to it.
-// If we aren't in a pattern string, begin one now.
//
//------------------------------------------------------------------------------
void RegexCompile::literalChar(UChar32 c) {
- int32_t op; // An operation in the compiled pattern.
- int32_t opType;
- int32_t patternLoc; // A position in the compiled pattern.
- int32_t stringLen;
-
-
- // If the last thing compiled into the pattern was not a literal char,
- // force this new literal char to begin a new string, and not append to the previous.
- op = (int32_t)fRXPat->fCompiledPat->lastElementi();
- opType = URX_TYPE(op);
- if (!(opType == URX_STRING_LEN || opType == URX_ONECHAR || opType == URX_ONECHAR_I)) {
- fixLiterals();
- }
-
- if (fStringOpStart == -1) {
- // First char of a string in the pattern.
- // Emit a OneChar op into the compiled pattern.
- emitONE_CHAR(c);
-
- // Mark that we might actually be starting a string here
- fStringOpStart = fRXPat->fLiteralText.length();
- return;
- }
-
- op = (int32_t)fRXPat->fCompiledPat->lastElementi();
- opType = URX_TYPE(op);
- U_ASSERT(opType == URX_ONECHAR || opType == URX_ONECHAR_I || opType == URX_STRING_LEN);
-
- // If the most recently emitted op is a URX_ONECHAR,
- if (opType == URX_ONECHAR || opType == URX_ONECHAR_I) {
- if (U16_IS_TRAIL(c) && U16_IS_LEAD(URX_VAL(op))) {
- // The most recently emitted op is a ONECHAR that was the first half
- // of a surrogate pair. Update the ONECHAR's operand to be the
- // supplementary code point resulting from both halves of the pair.
- c = U16_GET_SUPPLEMENTARY(URX_VAL(op), c);
- op = URX_BUILD(opType, c);
- patternLoc = fRXPat->fCompiledPat->size() - 1;
- fRXPat->fCompiledPat->setElementAt(op, patternLoc);
- return;
- }
-
- // The most recently emitted op is a ONECHAR.
- // We've now received another adjacent char. Change the ONECHAR op
- // to a string op.
- fRXPat->fLiteralText.append(URX_VAL(op));
-
- if (fModeFlags & UREGEX_CASE_INSENSITIVE) {
- op = URX_BUILD(URX_STRING_I, fStringOpStart);
- } else {
- op = URX_BUILD(URX_STRING, fStringOpStart);
- }
- patternLoc = fRXPat->fCompiledPat->size() - 1;
- fRXPat->fCompiledPat->setElementAt(op, patternLoc);
- op = URX_BUILD(URX_STRING_LEN, 0);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
- }
-
- // We are adding onto an existing string
- fRXPat->fLiteralText.append(c);
-
- // The pattern contains a URX_SRING / URX_STRING_LEN. Update the
- // string length to reflect the new char we just added to the string.
- stringLen = fRXPat->fLiteralText.length() - fStringOpStart;
- op = URX_BUILD(URX_STRING_LEN, stringLen);
- patternLoc = fRXPat->fCompiledPat->size() - 1;
- fRXPat->fCompiledPat->setElementAt(op, patternLoc);
-}
-
-
-
-//------------------------------------------------------------------------------
-//
-// emitONE_CHAR emit a ONE_CHAR op into the generated code.
-// Choose cased or uncased version, depending on the
-// match mode and whether the character itself is cased.
-//
-//------------------------------------------------------------------------------
-void RegexCompile::emitONE_CHAR(UChar32 c) {
- int32_t op;
- if ((fModeFlags & UREGEX_CASE_INSENSITIVE) &&
- u_hasBinaryProperty(c, UCHAR_CASE_SENSITIVE)) {
- // We have a cased character, and are in case insensitive matching mode.
- //c = u_foldCase(c, U_FOLD_CASE_DEFAULT); // !!!: handled in stripNOPs() now
- op = URX_BUILD(URX_ONECHAR_I, c);
- } else {
- // Uncased char, or case sensitive match mode.
- // Either way, just generate a literal compare of the char.
- op = URX_BUILD(URX_ONECHAR, c);
- }
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ fLiteralChars.append(c);
}
//------------------------------------------------------------------------------
//
// fixLiterals When compiling something that can follow a literal
-// string in a pattern, we need to "fix" any preceding
-// string, which will cause any subsequent literals to
-// begin a new string, rather than appending to the
-// old one.
+// string in a pattern, emit the code to match the
+// accumulated literal string.
//
// Optionally, split the last char of the string off into
// a single "ONE_CHAR" operation, so that quantifiers can
//
//------------------------------------------------------------------------------
void RegexCompile::fixLiterals(UBool split) {
- int32_t stringStart = fStringOpStart; // start index of the current literal string
- int32_t op; // An op from/for the compiled pattern.
- int32_t opType; // An opcode type from the compiled pattern.
- int32_t stringLastCharIdx;
- UChar32 lastChar;
- int32_t stringNextToLastCharIdx;
- UChar32 nextToLastChar;
- int32_t stringLen;
-
- fStringOpStart = -1;
- if (!split) {
+ int32_t op = 0; // An op from/for the compiled pattern.
+
+ // If no literal characters have been scanned but not yet had code generated
+ // for them, nothing needs to be done.
+ if (fLiteralChars.length() == 0) {
return;
}
- // Split: We need to ensure that the last item in the compiled pattern does
- // not refer to a literal string of more than one char. If it does,
- // separate the last char from the rest of the string.
+ int32_t indexOfLastCodePoint = fLiteralChars.moveIndex32(fLiteralChars.length(), -1);
+ UChar32 lastCodePoint = fLiteralChars.char32At(indexOfLastCodePoint);
+
+ // Split: We need to ensure that the last item in the compiled pattern
+ // refers only to the last literal scanned in the pattern, so that
+ // quantifiers (*, +, etc.) affect only it, and not a longer string.
+ // Split before case folding for case insensitive matches.
- // If the last operation from the compiled pattern is not a string,
- // nothing needs to be done
- op = (int32_t)fRXPat->fCompiledPat->lastElementi();
- opType = URX_TYPE(op);
- if (opType != URX_STRING_LEN) {
+ if (split) {
+ fLiteralChars.truncate(indexOfLastCodePoint);
+ fixLiterals(FALSE); // Recursive call, emit code to match the first part of the string.
+ // Note that the truncated literal string may be empty, in which case
+ // nothing will be emitted.
+
+ literalChar(lastCodePoint); // Re-add the last code point as if it were a new literal.
+ fixLiterals(FALSE); // Second recursive call, code for the final code point.
return;
}
- stringLen = URX_VAL(op);
- //
- // Find the position of the last code point in the string (might be a surrogate pair)
- //
- stringLastCharIdx = fRXPat->fLiteralText.length();
- stringLastCharIdx = fRXPat->fLiteralText.moveIndex32(stringLastCharIdx, -1);
- lastChar = fRXPat->fLiteralText.char32At(stringLastCharIdx);
-
- // The string should always be at least two code points long, meaning that there
- // should be something before the last char position that we just found.
- U_ASSERT(stringLastCharIdx > stringStart);
- stringNextToLastCharIdx = fRXPat->fLiteralText.moveIndex32(stringLastCharIdx, -1);
- U_ASSERT(stringNextToLastCharIdx >= stringStart);
- nextToLastChar = fRXPat->fLiteralText.char32At(stringNextToLastCharIdx);
-
- if (stringNextToLastCharIdx > stringStart) {
- // The length of string remaining after removing one char is two or more.
- // Leave the string in the compiled pattern, shorten it by one char,
- // and append a URX_ONECHAR op for the last char.
- stringLen -= (fRXPat->fLiteralText.length() - stringLastCharIdx);
- op = URX_BUILD(URX_STRING_LEN, stringLen);
- fRXPat->fCompiledPat->setElementAt(op, fRXPat->fCompiledPat->size() -1);
- emitONE_CHAR(lastChar);
- } else {
- // The original string consisted of exactly two characters. Replace
- // the existing compiled URX_STRING/URX_STRING_LEN ops with a pair
- // of URX_ONECHARs.
- fRXPat->fCompiledPat->setSize(fRXPat->fCompiledPat->size() -2);
- emitONE_CHAR(nextToLastChar);
- emitONE_CHAR(lastChar);
+ // If we are doing case-insensitive matching, case fold the string. This may expand
+ // the string, e.g. the German sharp-s turns into "ss"
+ if (fModeFlags & UREGEX_CASE_INSENSITIVE) {
+ fLiteralChars.foldCase();
+ indexOfLastCodePoint = fLiteralChars.moveIndex32(fLiteralChars.length(), -1);
+ lastCodePoint = fLiteralChars.char32At(indexOfLastCodePoint);
}
-}
+ if (indexOfLastCodePoint == 0) {
+ // Single character, emit a URX_ONECHAR op to match it.
+ if ((fModeFlags & UREGEX_CASE_INSENSITIVE) &&
+ u_hasBinaryProperty(lastCodePoint, UCHAR_CASE_SENSITIVE)) {
+ op = URX_BUILD(URX_ONECHAR_I, lastCodePoint);
+ } else {
+ op = URX_BUILD(URX_ONECHAR, lastCodePoint);
+ }
+ appendOp(op);
+ } else {
+ // Two or more chars, emit a URX_STRING to match them.
+ if (fModeFlags & UREGEX_CASE_INSENSITIVE) {
+ op = URX_BUILD(URX_STRING_I, fRXPat->fLiteralText.length());
+ } else {
+ // TODO here: add optimization to split case sensitive strings of length two
+ // into two single char ops, for efficiency.
+ op = URX_BUILD(URX_STRING, fRXPat->fLiteralText.length());
+ }
+ appendOp(op);
+ op = URX_BUILD(URX_STRING_LEN, fLiteralChars.length());
+ appendOp(op);
+
+ // Add this string into the accumulated strings of the compiled pattern.
+ // The total size of the accumulated strings must be restricted to 24 bits because
+ // string indexes appear as compiled pattern operand values.
+ // This is the only place that the pattern.fLiteralText string is modified.
+
+ fRXPat->fLiteralText.append(fLiteralChars);
+ if (U_SUCCESS(*fStatus) && fRXPat->fLiteralText.length() > 0x00ffffff) {
+ *fStatus = U_REGEX_PATTERN_TOO_BIG;
+ }
+ }
+ fLiteralChars.remove();
+}
+//------------------------------------------------------------------------------
+//
+// appendOp() Append a new instruction onto the compiled pattern
+// Includes error checking, limiting the size of the
+// pattern to lengths that can be represented in the
+// 24 bit operand field of an instruction.
+//
+//------------------------------------------------------------------------------
+void RegexCompile::appendOp(int32_t op) {
+ fRXPat->fCompiledPat->addElement(op, *fStatus);
+ if ((fRXPat->fCompiledPat->size() > 0x00fffff0) && U_SUCCESS(*fStatus)) {
+ *fStatus = U_REGEX_PATTERN_TOO_BIG;
+ }
+}
//------------------------------------------------------------------------------
}
+//------------------------------------------------------------------------------
+//
+// allocateData() Allocate storage in the matcher's static data area.
+// Return the index for the newly allocated data.
+// The storage won't actually exist until we are running a match
+// operation, but the storage indexes are inserted into various
+// opcodes while compiling the pattern.
+//
+//------------------------------------------------------------------------------
+int32_t RegexCompile::allocateData(int32_t size) {
+ if (U_FAILURE(*fStatus)) {
+ return 0;
+ }
+ if (size <= 0 || size > 0x100 || fRXPat->fDataSize < 0) {
+ *fStatus = U_REGEX_INTERNAL_ERROR;
+ return 0;
+ }
+ int32_t dataIndex = fRXPat->fDataSize;
+ fRXPat->fDataSize += size;
+ if (fRXPat->fDataSize >= 0x00fffff0) {
+ *fStatus = U_REGEX_PATTERN_TOO_BIG;
+ }
+ return dataIndex;
+}
+
+
+//------------------------------------------------------------------------------
+//
+// allocateStackData() Allocate space in the back-tracking stack frame.
+// Return the index for the newly allocated data.
+// The frame indexes are inserted into various
+// opcodes while compiling the pattern, meaning that frame
+// size must be restricted to the size that will fit
+// as an operand (24 bits).
+//
+//------------------------------------------------------------------------------
+int32_t RegexCompile::allocateStackData(int32_t size) {
+ if (U_FAILURE(*fStatus)) {
+ return 0;
+ }
+ if (size <= 0 || size > 0x100 || fRXPat->fFrameSize < 0) {
+ *fStatus = U_REGEX_INTERNAL_ERROR;
+ return 0;
+ }
+ int32_t dataIndex = fRXPat->fFrameSize;
+ fRXPat->fFrameSize += size;
+ if (fRXPat->fFrameSize >= 0x00fffff0) {
+ *fStatus = U_REGEX_PATTERN_TOO_BIG;
+ }
+ return dataIndex;
+}
+
//------------------------------------------------------------------------------
//
//------------------------------------------------------------------------------
int32_t RegexCompile::blockTopLoc(UBool reserveLoc) {
int32_t theLoc;
+ fixLiterals(TRUE); // Emit code for any pending literals.
+ // If last item was a string, emit separate op for the its last char.
if (fRXPat->fCompiledPat->size() == fMatchCloseParen)
{
// The item just processed is a parenthesized block.
U_ASSERT(URX_TYPE(((uint32_t)fRXPat->fCompiledPat->elementAti(theLoc))) == URX_NOP);
}
else {
- // Item just compiled is a single thing, a ".", or a single char, or a set reference.
+ // Item just compiled is a single thing, a ".", or a single char, a string or a set reference.
// No slot for STATE_SAVE was pre-reserved in the compiled code.
// We need to make space now.
- fixLiterals(TRUE); // If last item was a string, separate the last char.
theLoc = fRXPat->fCompiledPat->size()-1;
+ int32_t opAtTheLoc = (int32_t)fRXPat->fCompiledPat->elementAti(theLoc);
+ if (URX_TYPE(opAtTheLoc) == URX_STRING_LEN) {
+ // Strings take two opcode, we want the position of the first one.
+ // We can have a string at this point if a single character case-folded to two.
+ theLoc--;
+ }
if (reserveLoc) {
- /*int32_t opAtTheLoc = fRXPat->fCompiledPat->elementAti(theLoc);*/
int32_t nop = URX_BUILD(URX_NOP, 0);
fRXPat->fCompiledPat->insertElementAt(nop, theLoc, *fStatus);
}
return;
}
- // Force any literal chars that may follow the close paren to start a new string,
- // and not attach to any preceding it.
+ // Emit code for any pending literals.
fixLiterals(FALSE);
// Fixup any operations within the just-closed parenthesized group
int32_t frameVarLocation = URX_VAL(captureOp);
int32_t endCaptureOp = URX_BUILD(URX_END_CAPTURE, frameVarLocation);
- fRXPat->fCompiledPat->addElement(endCaptureOp, *fStatus);
+ appendOp(endCaptureOp);
}
break;
case atomic:
U_ASSERT(URX_TYPE(stoOp) == URX_STO_SP);
int32_t stoLoc = URX_VAL(stoOp);
int32_t ldOp = URX_BUILD(URX_LD_SP, stoLoc);
- fRXPat->fCompiledPat->addElement(ldOp, *fStatus);
+ appendOp(ldOp);
}
break;
U_ASSERT(URX_TYPE(startOp) == URX_LA_START);
int32_t dataLoc = URX_VAL(startOp);
int32_t op = URX_BUILD(URX_LA_END, dataLoc);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
}
break;
U_ASSERT(URX_TYPE(startOp) == URX_LA_START);
int32_t dataLoc = URX_VAL(startOp);
int32_t op = URX_BUILD(URX_LA_END, dataLoc);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
op = URX_BUILD(URX_BACKTRACK, 0);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
op = URX_BUILD(URX_LA_END, dataLoc);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
// Patch the URX_SAVE near the top of the block.
// The destination of the SAVE is the final LA_END that was just added.
U_ASSERT(URX_TYPE(startOp) == URX_LB_START);
int32_t dataLoc = URX_VAL(startOp);
int32_t op = URX_BUILD(URX_LB_END, dataLoc);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
- op = URX_BUILD(URX_LA_END, dataLoc);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
+ op = URX_BUILD(URX_LA_END, dataLoc);
+ appendOp(op);
// Determine the min and max bounds for the length of the
// string that the pattern can match.
int32_t patEnd = fRXPat->fCompiledPat->size() - 1;
int32_t minML = minMatchLength(fMatchOpenParen, patEnd);
int32_t maxML = maxMatchLength(fMatchOpenParen, patEnd);
+ if (URX_TYPE(maxML) != 0) {
+ error(U_REGEX_LOOK_BEHIND_LIMIT);
+ break;
+ }
if (maxML == INT32_MAX) {
error(U_REGEX_LOOK_BEHIND_LIMIT);
break;
U_ASSERT(URX_TYPE(startOp) == URX_LB_START);
int32_t dataLoc = URX_VAL(startOp);
int32_t op = URX_BUILD(URX_LBN_END, dataLoc);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
// Determine the min and max bounds for the length of the
// string that the pattern can match.
int32_t patEnd = fRXPat->fCompiledPat->size() - 1;
int32_t minML = minMatchLength(fMatchOpenParen, patEnd);
int32_t maxML = maxMatchLength(fMatchOpenParen, patEnd);
+ if (URX_TYPE(maxML) != 0) {
+ error(U_REGEX_LOOK_BEHIND_LIMIT);
+ break;
+ }
if (maxML == INT32_MAX) {
error(U_REGEX_LOOK_BEHIND_LIMIT);
break;
case 0:
{
// Set of no elements. Always fails to match.
- fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKTRACK, 0), *fStatus);
+ appendOp(URX_BUILD(URX_BACKTRACK, 0));
delete theSet;
}
break;
int32_t setNumber = fRXPat->fSets->size();
fRXPat->fSets->addElement(theSet, *fStatus);
int32_t setOp = URX_BUILD(URX_SETREF, setNumber);
- fRXPat->fCompiledPat->addElement(setOp, *fStatus);
+ appendOp(setOp);
}
}
}
// Except for the specific opcodes used, the code is the same
// for all three types (greedy, non-greedy, possessive) of
// intervals. The opcodes are supplied as parameters.
+// (There are two sets of opcodes - greedy & possessive use the
+// same ones, while non-greedy has it's own.)
//
// The code for interval loops has this form:
// 0 CTR_INIT counter loc (in stack frame)
insertOp(topOfBlock);
// The operands for the CTR_INIT opcode include the index in the matcher data
- // of the counter. Allocate it now.
- int32_t counterLoc = fRXPat->fFrameSize;
- fRXPat->fFrameSize++;
+ // of the counter. Allocate it now. There are two data items
+ // counterLoc --> Loop counter
+ // +1 --> Input index (for breaking non-progressing loops)
+ // (Only present if unbounded upper limit on loop)
+ int32_t dataSize = fIntervalUpper < 0 ? 2 : 1;
+ int32_t counterLoc = allocateStackData(dataSize);
int32_t op = URX_BUILD(InitOp, counterLoc);
fRXPat->fCompiledPat->setElementAt(op, topOfBlock);
// Apend the CTR_LOOP op. The operand is the location of the CTR_INIT op.
// Goes at end of the block being looped over, so just append to the code so far.
op = URX_BUILD(LoopOp, topOfBlock);
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
if ((fIntervalLow & 0xff000000) != 0 ||
(fIntervalUpper > 0 && (fIntervalUpper & 0xff000000) != 0)) {
int32_t topOfBlock = blockTopLoc(FALSE);
if (fIntervalUpper == 0) {
// Pathological case. Attempt no matches, as if the block doesn't exist.
+ // Discard the generated code for the block.
+ // If the block included parens, discard the info pertaining to them as well.
fRXPat->fCompiledPat->setSize(topOfBlock);
+ if (fMatchOpenParen >= topOfBlock) {
+ fMatchOpenParen = -1;
+ }
+ if (fMatchCloseParen >= topOfBlock) {
+ fMatchCloseParen = -1;
+ }
return TRUE;
}
int32_t i;
for (i=1; i<fIntervalUpper; i++ ) {
if (i == fIntervalLow) {
- fRXPat->fCompiledPat->addElement(saveOp, *fStatus);
+ appendOp(saveOp);
}
if (i > fIntervalLow) {
- fRXPat->fCompiledPat->addElement(saveOp, *fStatus);
+ appendOp(saveOp);
}
- fRXPat->fCompiledPat->addElement(op, *fStatus);
+ appendOp(op);
}
return TRUE;
}
if (currentLen == 0) {
UChar32 c = URX_VAL(op);
if (u_hasBinaryProperty(c, UCHAR_CASE_SENSITIVE)) {
- // character may have distinct cased forms. Add all of them
- // to the set of possible starting match chars.
- UnicodeSet s(c, c);
- s.closeOver(USET_CASE_INSENSITIVE);
- fRXPat->fInitialChars->addAll(s);
+
+ // Disable optimizations on first char of match.
+ // TODO: Compute the set of chars that case fold to this char, or to
+ // a string that begins with this char.
+ // For simple case folding, this code worked:
+ // UnicodeSet s(c, c);
+ // s.closeOver(USET_CASE_INSENSITIVE);
+ // fRXPat->fInitialChars->addAll(s);
+
+ fRXPat->fInitialChars->clear();
+ fRXPat->fInitialChars->complement();
} else {
// Char has no case variants. Just add it as-is to the
// set of possible starting chars.
int32_t stringStartIdx = URX_VAL(op);
UChar32 c = fRXPat->fLiteralText.char32At(stringStartIdx);
UnicodeSet s(c, c);
- s.closeOver(USET_CASE_INSENSITIVE);
+
+ // TODO: compute correct set of starting chars for full case folding.
+ // For the moment, say any char can start.
+ // s.closeOver(USET_CASE_INSENSITIVE);
+ s.clear();
+ s.complement();
+
fRXPat->fInitialChars->addAll(s);
numInitialStrings += 2; // Matching on an initial string not possible.
}
case URX_STRING:
- case URX_STRING_I:
{
loc++;
int32_t stringLenOp = (int32_t)fRXPat->fCompiledPat->elementAti(loc);
break;
+ case URX_STRING_I:
+ {
+ loc++;
+ // TODO: with full case folding, matching input text may be shorter than
+ // the string we have here. More smarts could put some bounds on it.
+ // Assume a min length of one for now. A min length of zero causes
+ // optimization failures for a pattern like "string"+
+ // currentLen += URX_VAL(stringLenOp);
+ currentLen += 1;
+ }
+ break;
+
case URX_CTR_INIT:
case URX_CTR_INIT_NG:
{
return currentLen;
}
+// Increment with overflow check.
+// val and delta will both be positive.
+
+static int32_t safeIncrement(int32_t val, int32_t delta) {
+ if (INT32_MAX - val > delta) {
+ return val + delta;
+ } else {
+ return INT32_MAX;
+ }
+}
//------------------------------------------------------------------------------
case URX_DOTANY_ALL:
case URX_DOTANY:
case URX_DOTANY_UNIX:
- currentLen+=2;
+ currentLen = safeIncrement(currentLen, 2);
break;
// Single literal character. Increase current max length by one or two,
// depending on whether the char is in the supplementary range.
case URX_ONECHAR:
- currentLen++;
+ currentLen = safeIncrement(currentLen, 1);
if (URX_VAL(op) > 0x10000) {
- currentLen++;
+ currentLen = safeIncrement(currentLen, 1);
}
break;
case URX_STRING:
+ {
+ loc++;
+ int32_t stringLenOp = (int32_t)fRXPat->fCompiledPat->elementAti(loc);
+ currentLen = safeIncrement(currentLen, URX_VAL(stringLenOp));
+ break;
+ }
+
case URX_STRING_I:
+ // TODO: This code assumes that any user string that matches will be no longer
+ // than our compiled string, with case insensitive matching.
+ // Our compiled string has been case-folded already.
+ //
+ // Any matching user string will have no more code points than our
+ // compiled (folded) string. Folding may add code points, but
+ // not remove them.
+ //
+ // There is a potential problem if a supplemental code point
+ // case-folds to a BMP code point. In this case our compiled string
+ // could be shorter (in code units) than a matching user string.
+ //
+ // At this time (Unicode 6.1) there are no such characters, and this case
+ // is not being handled. A test, intltest regex/Bug9283, will fail if
+ // any problematic characters are added to Unicode.
+ //
+ // If this happens, we can make a set of the BMP chars that the
+ // troublesome supplementals fold to, scan our string, and bump the
+ // currentLen one extra for each that is found.
+ //
{
loc++;
int32_t stringLenOp = (int32_t)fRXPat->fCompiledPat->elementAti(loc);
- currentLen += URX_VAL(stringLenOp);
+ currentLen = safeIncrement(currentLen, URX_VAL(stringLenOp));
}
break;
-
case URX_CTR_INIT:
case URX_CTR_INIT_NG:
+ // For Loops, recursively call this function on the pattern for the loop body,
+ // then multiply the result by the maximum loop count.
+ {
+ int32_t loopEndLoc = URX_VAL(fRXPat->fCompiledPat->elementAti(loc+1));
+ if (loopEndLoc == loc+4) {
+ // Loop has an empty body. No affect on max match length.
+ // Continue processing with code after the loop end.
+ loc = loopEndLoc;
+ break;
+ }
+
+ int32_t maxLoopCount = fRXPat->fCompiledPat->elementAti(loc+3);
+ if (maxLoopCount == -1) {
+ // Unbounded Loop. No upper bound on match length.
+ currentLen = INT32_MAX;
+ break;
+ }
+
+ U_ASSERT(loopEndLoc >= loc+4);
+ int32_t blockLen = maxMatchLength(loc+4, loopEndLoc-1); // Recursive call.
+ if (blockLen == INT32_MAX) {
+ currentLen = blockLen;
+ break;
+ }
+ currentLen += blockLen * maxLoopCount;
+ loc = loopEndLoc;
+ break;
+ }
+
case URX_CTR_LOOP:
case URX_CTR_LOOP_NG:
+ // These opcodes will be skipped over by code for URX_CRT_INIT.
+ // We shouldn't encounter them here.
+ U_ASSERT(FALSE);
+ break;
+
case URX_LOOP_SR_I:
case URX_LOOP_DOT_I:
case URX_LOOP_C:
// For anything to do with loops, make the match length unbounded.
- // Note: INIT instructions are multi-word. Can ignore because
- // INT32_MAX length will stop the per-instruction loop.
currentLen = INT32_MAX;
break;
// back-reference fixup is also performed here (adjusting
// back-reference operands to point to the correct frame offsets).
//
-// In addition, case-insensitive character and string literals are
-// now case-folded here, rather than when first parsed or at match
-// time.
-//
//------------------------------------------------------------------------------
void RegexCompile::stripNOPs() {
}
UnicodeString caseStringBuffer;
- int32_t stringDelta = 0;
// Make a second pass over the code, removing the NOPs by moving following
// code up, and patching operands that refer to code locations that
break;
}
- case URX_ONECHAR_I:
- {
- UChar32 c = URX_VAL(op);
- if (u_hasBinaryProperty(c, UCHAR_CASE_SENSITIVE)) {
- // We have a cased character to fold
- c = u_foldCase(c, U_FOLD_CASE_DEFAULT);
- op = URX_BUILD(URX_ONECHAR_I, c);
- }
-
- fRXPat->fCompiledPat->setElementAt(op, dst);
- dst++;
- break;
- }
- case URX_STRING_I:
- {
- op = URX_BUILD(URX_STRING_I, URX_VAL(op)+stringDelta);
-
- src++;
- int32_t lengthOp = (int32_t)fRXPat->fCompiledPat->elementAti(src);
-
- caseStringBuffer.setTo(fRXPat->fLiteralText, URX_VAL(op), URX_VAL(lengthOp));
- caseStringBuffer.foldCase(U_FOLD_CASE_DEFAULT);
-
- int32_t newLen = caseStringBuffer.length();
- if (newLen <= URX_VAL(lengthOp)) {
- // don't shift if we don't have to, take the tiny memory hit of a smaller string
- fRXPat->fLiteralText.replace(URX_VAL(op), newLen, caseStringBuffer);
- } else {
- // shift other strings over...at least UnicodeString handles this for us!
- fRXPat->fLiteralText.replace(URX_VAL(op), URX_VAL(lengthOp), caseStringBuffer);
- stringDelta += newLen - URX_VAL(lengthOp);
- }
- lengthOp = URX_BUILD(URX_STRING_LEN, newLen);
-
- fRXPat->fCompiledPat->setElementAt(op, dst);
- fRXPat->fCompiledPat->setElementAt(lengthOp, dst+1);
- dst += 2;
- break;
- }
case URX_BACKREF:
case URX_BACKREF_I:
{
fRXPat->fNeedsAltInput = TRUE;
break;
}
- case URX_STRING:
- op = URX_BUILD(URX_STRING, URX_VAL(op)+stringDelta);
- // continue
case URX_RESERVED_OP:
case URX_RESERVED_OP_N:
case URX_BACKTRACK:
case URX_END:
case URX_ONECHAR:
+ case URX_STRING:
case URX_STRING_LEN:
case URX_START_CAPTURE:
case URX_END_CAPTURE:
case URX_STO_INP_LOC:
case URX_LA_START:
case URX_LA_END:
+ case URX_ONECHAR_I:
+ case URX_STRING_I:
case URX_DOLLAR_M:
case URX_CARET_M:
case URX_CARET_M_UNIX:
static const UChar chColon = 0x3A; // ':'
static const UChar chE = 0x45; // 'E'
static const UChar chQ = 0x51; // 'Q'
-static const UChar chN = 0x4E; // 'N'
+//static const UChar chN = 0x4E; // 'N'
static const UChar chP = 0x50; // 'P'
static const UChar chBackSlash = 0x5c; // '\' introduces a char escape
-static const UChar chLBracket = 0x5b; // '['
+//static const UChar chLBracket = 0x5b; // '['
static const UChar chRBracket = 0x5d; // ']'
static const UChar chUp = 0x5e; // '^'
static const UChar chLowerP = 0x70;
if (fQuoteMode) {
c.fQuoted = TRUE;
- if ((c.fChar==chBackSlash && peekCharLL()==chE) || c.fChar == (UChar32)-1) {
+ if ((c.fChar==chBackSlash && peekCharLL()==chE && ((fModeFlags & UREGEX_LITERAL) == 0)) ||
+ c.fChar == (UChar32)-1) {
fQuoteMode = FALSE; // Exit quote mode,
- nextCharLL(); // discard the E
- nextChar(c); // recurse to get the real next char
+ nextCharLL(); // discard the E
+ nextChar(c); // recurse to get the real next char
}
}
else if (fInBackslashQuote) {
}
}
// TODO: check what Java & Perl do with non-ASCII white spaces. Ticket 6061.
- if (uprv_isRuleWhiteSpace(c.fChar) == FALSE) {
+ if (PatternProps::isWhiteSpace(c.fChar) == FALSE) {
break;
}
c.fChar = nextCharLL();
projects / platform / framework / web / crosswalk.git / blobdiff