blob: b17ef53c93d73df4603bf422b1a619a0c085c5b8 [file] [log] [blame]
<
//
// file: regexcmp.cpp
//
// Copyright (C) 2002-2012 International Business Machines Corporation and others.
// All Rights Reserved.
//
// This file contains the ICU regular expression compiler, which is responsible
// for processing a regular expression pattern into the compiled form that
// is used by the match finding engine.
//
#include "unicode/utypes.h"
#if !UCONFIG_NO_REGULAR_EXPRESSIONS
#include "unicode/ustring.h"
#include "unicode/unistr.h"
#include "unicode/uniset.h"
#include "unicode/uchar.h"
#include "unicode/uchriter.h"
#include "unicode/parsepos.h"
#include "unicode/parseerr.h"
#include "unicode/regex.h"
#include "unicode/utf.h"
#include "unicode/utf16.h"
#include "patternprops.h"
#include "putilimp.h"
#include "cmemory.h"
#include "cstring.h"
#include "uvectr32.h"
#include "uvectr64.h"
#include "uassert.h"
#include "ucln_in.h"
#include "uinvchar.h"
#include "regeximp.h"
#include "regexcst.h" // Contains state table for the regex pattern parser.
// generated by a Perl script.
#include "regexcmp.h"
#include "regexst.h"
#include "regextxt.h"
U_NAMESPACE_BEGIN
//------------------------------------------------------------------------------
//
// Constructor.
//
//------------------------------------------------------------------------------
RegexCompile::RegexCompile(RegexPattern *rxp, UErrorCode &status) :
fParenStack(status), fSetStack(status), fSetOpStack(status)
{
// Lazy init of all shared global sets (needed for init()'s empty text)
RegexStaticSets::initGlobals(&status);
fStatus = &status;
fRXPat = rxp;
fScanIndex = 0;
fLastChar = -1;
fPeekChar = -1;
fLineNum = 1;
fCharNum = 0;
fQuoteMode = FALSE;
fInBackslashQuote = FALSE;
fModeFlags = fRXPat->fFlags | 0x80000000;
fEOLComments = TRUE;
fMatchOpenParen = -1;
fMatchCloseParen = -1;
if (U_SUCCESS(status) && U_FAILURE(rxp->fDeferredStatus)) {
status = rxp->fDeferredStatus;
}
}
static const UChar chAmp = 0x26; // '&'
static const UChar chDash = 0x2d; // '-'
//------------------------------------------------------------------------------
//
// Destructor
//
//------------------------------------------------------------------------------
RegexCompile::~RegexCompile() {
}
static inline void addCategory(UnicodeSet *set, int32_t value, UErrorCode& ec) {
set->addAll(UnicodeSet().applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, value, ec));
}
//------------------------------------------------------------------------------
//
// Compile regex pattern. The state machine for rexexp pattern parsing is here.
// The state tables are hand-written in the file regexcst.txt,
// and converted to the form used here by a perl
// script regexcst.pl
//
//------------------------------------------------------------------------------
void RegexCompile::compile(
const UnicodeString &pat, // Source pat to be compiled.
UParseError &pp, // Error position info
UErrorCode &e) // Error Code
{
fRXPat->fPatternString = new UnicodeString(pat);
UText patternText = UTEXT_INITIALIZER;
utext_openConstUnicodeString(&patternText, fRXPat->fPatternString, &e);
if (U_SUCCESS(e)) {
compile(&patternText, pp, e);
utext_close(&patternText);
}
}
//
// compile, UText mode
// All the work is actually done here.
//
void RegexCompile::compile(
UText *pat, // Source pat to be compiled.
UParseError &pp, // Error position info
UErrorCode &e) // Error Code
{
fStatus = &e;
fParseErr = &pp;
fStackPtr = 0;
fStack[fStackPtr] = 0;
if (U_FAILURE(*fStatus)) {
return;
}
// There should be no pattern stuff in the RegexPattern object. They can not be reused.
U_ASSERT(fRXPat->fPattern == NULL || utext_nativeLength(fRXPat->fPattern) == 0);
// Prepare the RegexPattern object to receive the compiled pattern.
fRXPat->fPattern = utext_clone(fRXPat->fPattern, pat, FALSE, TRUE, fStatus);
fRXPat->fStaticSets = RegexStaticSets::gStaticSets->fPropSets;
fRXPat->fStaticSets8 = RegexStaticSets::gStaticSets->fPropSets8;
// Initialize the pattern scanning state machine
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.
//
// Main loop for the regex pattern parsing state machine.
// Runs once per state transition.
// Each time through optionally performs, depending on the state table,
// - an advance to the the next pattern char
// - an action to be performed.
// - pushing or popping a state to/from the local state return stack.
// file regexcst.txt is the source for the state table. The logic behind
// recongizing the pattern syntax is there, not here.
//
for (;;) {
// Bail out if anything has gone wrong.
// Regex pattern parsing stops on the first error encountered.
if (U_FAILURE(*fStatus)) {
break;
}
U_ASSERT(state != 0);
// Find the state table element that matches the input char from the pattern, or the
// class of the input character. Start with the first table row for this
// state, then linearly scan forward until we find a row that matches the
// character. The last row for each state always matches all characters, so
// the search will stop there, if not before.
//
tableEl = &gRuleParseStateTable[state];
REGEX_SCAN_DEBUG_PRINTF(("char, line, col = (\'%c\', %d, %d) state=%s ",
fC.fChar, fLineNum, fCharNum, RegexStateNames[state]));
for (;;) { // loop through table rows belonging to this state, looking for one
// that matches the current input char.
REGEX_SCAN_DEBUG_PRINTF(("."));
if (tableEl->fCharClass < 127 && fC.fQuoted == FALSE && tableEl->fCharClass == fC.fChar) {
// Table row specified an individual character, not a set, and
// the input character is not quoted, and
// the input character matched it.
break;
}
if (tableEl->fCharClass == 255) {
// Table row specified default, match anything character class.
break;
}
if (tableEl->fCharClass == 254 && fC.fQuoted) {
// Table row specified "quoted" and the char was quoted.
break;
}
if (tableEl->fCharClass == 253 && fC.fChar == (UChar32)-1) {
// Table row specified eof and we hit eof on the input.
break;
}
if (tableEl->fCharClass >= 128 && tableEl->fCharClass < 240 && // Table specs a char class &&
fC.fQuoted == FALSE && // char is not escaped &&
fC.fChar != (UChar32)-1) { // char is not EOF
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.
break;
}
}
// No match on this row, advance to the next row for this state,
tableEl++;
}
REGEX_SCAN_DEBUG_PRINTF(("\n"));
//
// We've found the row of the state table that matches the current input
// character from the rules string.
// Perform any action specified by this row in the state table.
if (doParseActions(tableEl->fAction) == FALSE) {
// Break out of the state machine loop if the
// the action signalled some kind of error, or
// the action was to exit, occurs on normal end-of-rules-input.
break;
}
if (tableEl->fPushState != 0) {
fStackPtr++;
if (fStackPtr >= kStackSize) {
error(U_REGEX_INTERNAL_ERROR);
REGEX_SCAN_DEBUG_PRINTF(("RegexCompile::parse() - state stack overflow.\n"));
fStackPtr--;
}
fStack[fStackPtr] = tableEl->fPushState;
}
//
// NextChar. This is where characters are actually fetched from the pattern.
// Happens under control of the 'n' tag in the state table.
//
if (tableEl->fNextChar) {
nextChar(fC);
}
// Get the next state from the table entry, or from the
// state stack if the next state was specified as "pop".
if (tableEl->fNextState != 255) {
state = tableEl->fNextState;
} else {
state = fStack[fStackPtr];
fStackPtr--;
if (fStackPtr < 0) {
// state stack underflow
// This will occur if the user pattern has mis-matched parentheses,
// with extra close parens.
//
fStackPtr++;
error(U_REGEX_MISMATCHED_PAREN);
}
}
}
if (U_FAILURE(*fStatus)) {
// Bail out if the pattern had errors.
// Set stack cleanup: a successful compile would have left it empty,
// but errors can leave temporary sets hanging around.
while (!fSetStack.empty()) {
delete (UnicodeSet *)fSetStack.pop();
}
return;
}
//
// The pattern has now been read and processed, and the compiled code generated.
//
//
// Compute the number of digits requried for the largest capture group number.
//
fRXPat->fMaxCaptureDigits = 1;
int32_t n = 10;
int32_t groupCount = fRXPat->fGroupMap->size();
while (n <= groupCount) {
fRXPat->fMaxCaptureDigits++;
n *= 10;
}
//
// The pattern's fFrameSize so far has accumulated the requirements for
// storage for capture parentheses, counters, etc. that are encountered
// in the pattern. Add space for the two variables that are always
// present in the saved state: the input string position (int64_t) and
// the position in the compiled pattern.
//
fRXPat->fFrameSize+=RESTACKFRAME_HDRCOUNT;
//
// Optimization pass 1: NOPs, back-references, and case-folding
//
stripNOPs();
//
// Get bounds for the minimum and maximum length of a string that this
// pattern can match. Used to avoid looking for matches in strings that
// are too short.
//
fRXPat->fMinMatchLen = minMatchLength(3, fRXPat->fCompiledPat->size()-1);
//
// Optimization pass 2: match start type
//
matchStartType();
//
// Set up fast latin-1 range sets
//
int32_t numSets = fRXPat->fSets->size();
fRXPat->fSets8 = new Regex8BitSet[numSets];
// Null pointer check.
if (fRXPat->fSets8 == NULL) {
e = *fStatus = U_MEMORY_ALLOCATION_ERROR;
return;
}
int32_t i;
for (i=0; i<numSets; i++) {
UnicodeSet *s = (UnicodeSet *)fRXPat->fSets->elementAt(i);
fRXPat->fSets8[i].init(s);
}
}
//------------------------------------------------------------------------------
//
// doParseAction Do some action during regex pattern parsing.
// Called by the parse state machine.
//
// Generation of the match engine PCode happens here, or
// in functions called from the parse actions defined here.
//
//
//------------------------------------------------------------------------------
UBool RegexCompile::doParseActions(int32_t action)
{
UBool returnVal = TRUE;
switch ((Regex_PatternParseAction)action) {
case doPatStart:
// Start of pattern compiles to:
//0 SAVE 2 Fall back to position of FAIL
//1 jmp 3
//2 FAIL Stop if we ever reach here.
//3 NOP Dummy, so start of pattern looks the same as
// the start of an ( grouping.
//4 NOP Resreved, will be replaced by a save if there are
// OR | operators at the top level
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_STATE_SAVE, 2), *fStatus);
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_JMP, 3), *fStatus);
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_FAIL, 0), *fStatus);
// Standard open nonCapture paren action emits the two NOPs and
// sets up the paren stack frame.
doParseActions(doOpenNonCaptureParen);
break;
case doPatFinish:
// We've scanned to the end of the pattern
// The end of pattern compiles to:
// URX_END
// which will stop the runtime match engine.
// Encountering end of pattern also behaves like a close paren,
// and forces fixups of the State Save at the beginning of the compiled pattern
// and of any OR operations at the top level.
//
handleCloseParen();
if (fParenStack.size() > 0) {
// Missing close paren in pattern.
error(U_REGEX_MISMATCHED_PAREN);
}
// add the END operation to the compiled pattern.
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_END, 0), *fStatus);
// Terminate the pattern compilation state machine.
returnVal = FALSE;
break;
case doOrOperator:
// Scanning a '|', as in (A|B)
{
// 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
// side fails to match and backtracks. Locate the position for the
// save from the location on the top of the parentheses stack.
int32_t savePosition = fParenStack.popi();
int32_t op = (int32_t)fRXPat->fCompiledPat->elementAti(savePosition);
U_ASSERT(URX_TYPE(op) == URX_NOP); // original contents of reserved location
op = URX_BUILD(URX_STATE_SAVE, fRXPat->fCompiledPat->size()+1);
fRXPat->fCompiledPat->setElementAt(op, savePosition);
// Append an JMP operation into the compiled pattern. The operand for
// the JMP will eventually be the location following the ')' for the
// group. This will be patched in later, when the ')' is encountered.
op = URX_BUILD(URX_JMP, 0);
fRXPat->fCompiledPat->addElement(op, *fStatus);
// Push the position of the newly added JMP op onto the parentheses stack.
// This registers if for fixup when this block's close paren is encountered.
fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus);
// Append a NOP to the compiled pattern. This is the slot reserved
// for a SAVE in the event that there is yet another '|' following
// this one.
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus);
}
break;
case doOpenCaptureParen:
// Open Paren.
// Compile to a
// - NOP, which later may be replaced by a save-state if the
// parenthesized group gets a * quantifier, followed by
// - START_CAPTURE n where n is stack frame offset to the capture group variables.
// - NOP, which may later be replaced by a save-state if there
// is an '|' alternation within the parens.
//
// Each capture group gets three slots in the save stack frame:
// 0: Capture Group start position (in input string being matched.)
// 1: Capture Group end position.
// 2: Start of Match-in-progress.
// The first two locations are for a completed capture group, and are
// referred to by back references and the like.
// The third location stores the capture start position when an START_CAPTURE is
// encountered. This will be promoted to a completed capture when (and if) the corresponding
// END_CAPTURE is encountered.
{
fixLiterals();
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
int32_t varsLoc = fRXPat->fFrameSize; // Reserve three slots in match stack frame.
fRXPat->fFrameSize += 3;
int32_t cop = URX_BUILD(URX_START_CAPTURE, varsLoc);
fRXPat->fCompiledPat->addElement(cop, *fStatus);
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
// On the Parentheses stack, start a new frame and add the postions
// of the two NOPs. Depending on what follows in the pattern, the
// NOPs may be changed to SAVE_STATE or JMP ops, with a target
// address of the end of the parenthesized group.
fParenStack.push(fModeFlags, *fStatus); // Match mode state
fParenStack.push(capturing, *fStatus); // Frame type.
fParenStack.push(fRXPat->fCompiledPat->size()-3, *fStatus); // The first NOP location
fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); // The second NOP loc
// Save the mapping from group number to stack frame variable position.
fRXPat->fGroupMap->addElement(varsLoc, *fStatus);
}
break;
case doOpenNonCaptureParen:
// Open non-caputuring (grouping only) Paren.
// Compile to a
// - NOP, which later may be replaced by a save-state if the
// parenthesized group gets a * quantifier, followed by
// - NOP, which may later be replaced by a save-state if there
// is an '|' alternation within the parens.
{
fixLiterals();
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
// On the Parentheses stack, start a new frame and add the postions
// of the two NOPs.
fParenStack.push(fModeFlags, *fStatus); // Match mode state
fParenStack.push(plain, *fStatus); // Begin a new frame.
fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus); // The first NOP location
fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); // The second NOP loc
}
break;
case doOpenAtomicParen:
// Open Atomic Paren. (?>
// Compile to a
// - NOP, which later may be replaced if the parenthesized group
// has a quantifier, followed by
// - STO_SP save state stack position, so it can be restored at the ")"
// - NOP, which may later be replaced by a save-state if there
// is an '|' alternation within the parens.
{
fixLiterals();
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
int32_t varLoc = fRXPat->fDataSize; // Reserve a data location for saving the
fRXPat->fDataSize += 1; // state stack ptr.
int32_t stoOp = URX_BUILD(URX_STO_SP, varLoc);
fRXPat->fCompiledPat->addElement(stoOp, *fStatus);
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
// On the Parentheses stack, start a new frame and add the postions
// of the two NOPs. Depending on what follows in the pattern, the
// NOPs may be changed to SAVE_STATE or JMP ops, with a target
// address of the end of the parenthesized group.
fParenStack.push(fModeFlags, *fStatus); // Match mode state
fParenStack.push(atomic, *fStatus); // Frame type.
fParenStack.push(fRXPat->fCompiledPat->size()-3, *fStatus); // The first NOP
fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); // The second NOP
}
break;
case doOpenLookAhead:
// Positive Look-ahead (?= stuff )
//
// Note: Addition of transparent input regions, with the need to
// restore the original regions when failing out of a lookahead
// block, complicated this sequence. Some conbined opcodes
// might make sense - or might not, lookahead aren't that common.
//
// Caution: min match length optimization knows about this
// sequence; don't change without making updates there too.
//
// Compiles to
// 1 START_LA dataLoc Saves SP, Input Pos
// 2. STATE_SAVE 4 on failure of lookahead, goto 4
// 3 JMP 6 continue ...
//
// 4. LA_END Look Ahead failed. Restore regions.
// 5. BACKTRACK and back track again.
//
// 6. NOP reserved for use by quantifiers on the block.
// Look-ahead can't have quantifiers, but paren stack
// compile time conventions require the slot anyhow.
// 7. NOP may be replaced if there is are '|' ops in the block.
// 8. code for parenthesized stuff.
// 9. LA_END
//
// Two data slots are reserved, for saving the stack ptr and the input position.
{
fixLiterals();
int32_t dataLoc = fRXPat->fDataSize;
fRXPat->fDataSize += 2;
int32_t op = URX_BUILD(URX_LA_START, dataLoc);
fRXPat->fCompiledPat->addElement(op, *fStatus);
op = URX_BUILD(URX_STATE_SAVE, fRXPat->fCompiledPat->size()+ 2);
fRXPat->fCompiledPat->addElement(op, *fStatus);
op = URX_BUILD(URX_JMP, fRXPat->fCompiledPat->size()+ 3);
fRXPat->fCompiledPat->addElement(op, *fStatus);
op = URX_BUILD(URX_LA_END, dataLoc);
fRXPat->fCompiledPat->addElement(op, *fStatus);
op = URX_BUILD(URX_BACKTRACK, 0);
fRXPat->fCompiledPat->addElement(op, *fStatus);
op = URX_BUILD(URX_NOP, 0);
fRXPat->fCompiledPat->addElement(op, *fStatus);
fRXPat->fCompiledPat->addElement(op, *fStatus);
// On the Parentheses stack, start a new frame and add the postions
// of the NOPs.
fParenStack.push(fModeFlags, *fStatus); // Match mode state
fParenStack.push(lookAhead, *fStatus); // Frame type.
fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus); // The first NOP location
fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); // The second NOP location
}
break;
case doOpenLookAheadNeg:
// Negated Lookahead. (?! stuff )
// Compiles to
// 1. START_LA dataloc
// 2. SAVE_STATE 7 // Fail within look-ahead block restores to this state,
// // which continues with the match.
// 3. NOP // Std. Open Paren sequence, for possible '|'
// 4. code for parenthesized stuff.
// 5. END_LA // Cut back stack, remove saved state from step 2.
// 6. BACKTRACK // code in block succeeded, so neg. lookahead fails.
// 7. END_LA // Restore match region, in case look-ahead was using
// an alternate (transparent) region.
{
fixLiterals();
int32_t dataLoc = fRXPat->fDataSize;
fRXPat->fDataSize += 2;
int32_t op = URX_BUILD(URX_LA_START, dataLoc);
fRXPat->fCompiledPat->addElement(op, *fStatus);
op = URX_BUILD(URX_STATE_SAVE, 0); // dest address will be patched later.
fRXPat->fCompiledPat->addElement(op, *fStatus);
op = URX_BUILD(URX_NOP, 0);
fRXPat->fCompiledPat->addElement(op, *fStatus);
// On the Parentheses stack, start a new frame and add the postions
// of the StateSave and NOP.
fParenStack.push(fModeFlags, *fStatus); // Match mode state
fParenStack.push(negLookAhead, *fStatus); // Frame type
fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus); // The STATE_SAVE location
fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); // The second NOP location
// Instructions #5 - #7 will be added when the ')' is encountered.
}
break;
case doOpenLookBehind:
{
// Compile a (?<= look-behind open paren.
//
// Compiles to
// 0 URX_LB_START dataLoc
// 1 URX_LB_CONT dataLoc
// 2 MinMatchLen
// 3 MaxMatchLen
// 4 URX_NOP Standard '(' boilerplate.
// 5 URX_NOP Reserved slot for use with '|' ops within (block).
// 6 <code for LookBehind expression>
// 7 URX_LB_END dataLoc # Check match len, restore input len
// 8 URX_LA_END dataLoc # Restore stack, input pos
//
// Allocate a block of matcher data, to contain (when running a match)
// 0: Stack ptr on entry
// 1: Input Index on entry
// 2: Start index of match current match attempt.
// 3: Original Input String len.
// Generate match code for any pending literals.
fixLiterals();
// Allocate data space
int32_t dataLoc = fRXPat->fDataSize;
fRXPat->fDataSize += 4;
// Emit URX_LB_START
int32_t op = URX_BUILD(URX_LB_START, dataLoc);
fRXPat->fCompiledPat->addElement(op, *fStatus);
// Emit URX_LB_CONT
op = URX_BUILD(URX_LB_CONT, dataLoc);
fRXPat->fCompiledPat->addElement(op, *fStatus);
fRXPat->fCompiledPat->addElement(0, *fStatus); // MinMatchLength. To be filled later.
fRXPat->fCompiledPat->addElement(0, *fStatus); // MaxMatchLength. To be filled later.
// Emit the NOP
op = URX_BUILD(URX_NOP, 0);
fRXPat->fCompiledPat->addElement(op, *fStatus);
fRXPat->fCompiledPat->addElement(op, *fStatus);
// On the Parentheses stack, start a new frame and add the postions
// of the URX_LB_CONT and the NOP.
fParenStack.push(fModeFlags, *fStatus); // Match mode state
fParenStack.push(lookBehind, *fStatus); // Frame type
fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus); // The first NOP location
fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); // The 2nd NOP location
// The final two instructions will be added when the ')' is encountered.
}
break;
case doOpenLookBehindNeg:
{
// Compile a (?<! negated look-behind open paren.
//
// Compiles to
// 0 URX_LB_START dataLoc # Save entry stack, input len
// 1 URX_LBN_CONT dataLoc # Iterate possible match positions
// 2 MinMatchLen
// 3 MaxMatchLen
// 4 continueLoc (9)
// 5 URX_NOP Standard '(' boilerplate.
// 6 URX_NOP Reserved slot for use with '|' ops within (block).
// 7 <code for LookBehind expression>
// 8 URX_LBN_END dataLoc # Check match len, cause a FAIL
// 9 ...
//
// Allocate a block of matcher data, to contain (when running a match)
// 0: Stack ptr on entry
// 1: Input Index on entry
// 2: Start index of match current match attempt.
// 3: Original Input String len.
// Generate match code for any pending literals.
fixLiterals();
// Allocate data space
int32_t dataLoc = fRXPat->fDataSize;
fRXPat->fDataSize += 4;
// Emit URX_LB_START
int32_t op = URX_BUILD(URX_LB_START, dataLoc);
fRXPat->fCompiledPat->addElement(op, *fStatus);
// Emit URX_LBN_CONT
op = URX_BUILD(URX_LBN_CONT, dataLoc);
fRXPat->fCompiledPat->addElement(op, *fStatus);
fRXPat->fCompiledPat->addElement(0, *fStatus); // MinMatchLength. To be filled later.
fRXPat->fCompiledPat->addElement(0, *fStatus); // MaxMatchLength. To be filled later.
fRXPat->fCompiledPat->addElement(0, *fStatus); // Continue Loc. To be filled later.
// Emit the NOP
op = URX_BUILD(URX_NOP, 0);
fRXPat->fCompiledPat->addElement(op, *fStatus);
fRXPat->fCompiledPat->addElement(op, *fStatus);
// On the Parentheses stack, start a new frame and add the postions
// of the URX_LB_CONT and the NOP.
fParenStack.push(fModeFlags, *fStatus); // Match mode state
fParenStack.push(lookBehindN, *fStatus); // Frame type
fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus); // The first NOP location
fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); // The 2nd NOP location
// The final two instructions will be added when the ')' is encountered.
}
break;
case doConditionalExpr:
// Conditionals such as (?(1)a:b)
case doPerlInline:
// Perl inline-condtionals. (?{perl code}a|b) We're not perl, no way to do them.
error(U_REGEX_UNIMPLEMENTED);
break;
case doCloseParen:
handleCloseParen();
if (fParenStack.size() <= 0) {
// Extra close paren, or missing open paren.
error(U_REGEX_MISMATCHED_PAREN);
}
break;
case doNOP:
break;
case doBadOpenParenType:
case doRuleError:
error(U_REGEX_RULE_SYNTAX);
break;
case doMismatchedParenErr:
error(U_REGEX_MISMATCHED_PAREN);
break;
case doPlus:
// Normal '+' compiles to
// 1. stuff to be repeated (already built)
// 2. jmp-sav 1
// 3. ...
//
// Or, if the item to be repeated can match a zero length string,
// 1. STO_INP_LOC data-loc
// 2. body of stuff to be repeated
// 3. JMP_SAV_X 2
// 4. ...
//
// Or, if the item to be repeated is simple
// 1. Item to be repeated.
// 2. LOOP_SR_I set number (assuming repeated item is a set ref)
// 3. LOOP_C stack location
{
int32_t topLoc = blockTopLoc(FALSE); // location of item #1
int32_t frameLoc;
// Check for simple constructs, which may get special optimized code.
if (topLoc == fRXPat->fCompiledPat->size() - 1) {
int32_t repeatedOp = (int32_t)fRXPat->fCompiledPat->elementAti(topLoc);
if (URX_TYPE(repeatedOp) == URX_SETREF) {
// Emit optimized code for [char set]+
int32_t loopOpI = URX_BUILD(URX_LOOP_SR_I, URX_VAL(repeatedOp));
fRXPat->fCompiledPat->addElement(loopOpI, *fStatus);
frameLoc = fRXPat->fFrameSize;
fRXPat->fFrameSize++;
int32_t loopOpC = URX_BUILD(URX_LOOP_C, frameLoc);
fRXPat->fCompiledPat->addElement(loopOpC, *fStatus);
break;
}
if (URX_TYPE(repeatedOp) == URX_DOTANY ||
URX_TYPE(repeatedOp) == URX_DOTANY_ALL ||
URX_TYPE(repeatedOp) == URX_DOTANY_UNIX) {
// Emit Optimized code for .+ operations.
int32_t loopOpI = URX_BUILD(URX_LOOP_DOT_I, 0);
if (URX_TYPE(repeatedOp) == URX_DOTANY_ALL) {
// URX_LOOP_DOT_I operand is a flag indicating ". matches any" mode.
loopOpI |= 1;
}
if (fModeFlags & UREGEX_UNIX_LINES) {
loopOpI |= 2;
}
fRXPat->fCompiledPat->addElement(loopOpI, *fStatus);
frameLoc = fRXPat->fFrameSize;
fRXPat->fFrameSize++;
int32_t loopOpC = URX_BUILD(URX_LOOP_C, frameLoc);
fRXPat->fCompiledPat->addElement(loopOpC, *fStatus);
break;
}
}
// General case.
// Check for minimum match length of zero, which requires
// extra loop-breaking code.
if (minMatchLength(topLoc, fRXPat->fCompiledPat->size()-1) == 0) {
// Zero length match is possible.
// Emit the code sequence that can handle it.
insertOp(topLoc);
frameLoc = fRXPat->fFrameSize;
fRXPat->fFrameSize++;
int32_t op = URX_BUILD(URX_STO_INP_LOC, frameLoc);
fRXPat->fCompiledPat->setElementAt(op, topLoc);
op = URX_BUILD(URX_JMP_SAV_X, topLoc+1);
fRXPat->fCompiledPat->addElement(op, *fStatus);
} else {
// Simpler code when the repeated body must match something non-empty
int32_t jmpOp = URX_BUILD(URX_JMP_SAV, topLoc);
fRXPat->fCompiledPat->addElement(jmpOp, *fStatus);
}
}
break;
case doNGPlus:
// Non-greedy '+?' compiles to
// 1. stuff to be repeated (already built)
// 2. state-save 1
// 3. ...
{
int32_t topLoc = blockTopLoc(FALSE);
int32_t saveStateOp = URX_BUILD(URX_STATE_SAVE, topLoc);
fRXPat->fCompiledPat->addElement(saveStateOp, *fStatus);
}
break;
case doOpt:
// Normal (greedy) ? quantifier.
// Compiles to
// 1. state save 3
// 2. body of optional block
// 3. ...
// Insert the state save into the compiled pattern, and we're done.
{
int32_t saveStateLoc = blockTopLoc(TRUE);
int32_t saveStateOp = URX_BUILD(URX_STATE_SAVE, fRXPat->fCompiledPat->size());
fRXPat->fCompiledPat->setElementAt(saveStateOp, saveStateLoc);
}
break;
case doNGOpt:
// Non-greedy ?? quantifier
// compiles to
// 1. jmp 4
// 2. body of optional block
// 3 jmp 5
// 4. state save 2
// 5 ...
// This code is less than ideal, with two jmps instead of one, because we can only
// insert one instruction at the top of the block being iterated.
{
int32_t jmp1_loc = blockTopLoc(TRUE);
int32_t jmp2_loc = fRXPat->fCompiledPat->size();
int32_t jmp1_op = URX_BUILD(URX_JMP, jmp2_loc+1);
fRXPat->fCompiledPat->setElementAt(jmp1_op, jmp1_loc);
int32_t jmp2_op = URX_BUILD(URX_JMP, jmp2_loc+2);
fRXPat->fCompiledPat->addElement(jmp2_op, *fStatus);
int32_t save_op = URX_BUILD(URX_STATE_SAVE, jmp1_loc+1);
fRXPat->fCompiledPat->addElement(save_op, *fStatus);
}
break;
case doStar:
// Normal (greedy) * quantifier.
// Compiles to
// 1. STATE_SAVE 4
// 2. body of stuff being iterated over
// 3. JMP_SAV 2
// 4. ...
//
// Or, if the body is a simple [Set],
// 1. LOOP_SR_I set number
// 2. LOOP_C stack location
// ...
//
// Or if this is a .*
// 1. LOOP_DOT_I (. matches all mode flag)
// 2. LOOP_C stack location
//
// Or, if the body can match a zero-length string, to inhibit infinite loops,
// 1. STATE_SAVE 5
// 2. STO_INP_LOC data-loc
// 3. body of stuff
// 4. JMP_SAV_X 2
// 5. ...
{
// location of item #1, the STATE_SAVE
int32_t topLoc = blockTopLoc(FALSE);
int32_t dataLoc = -1;
// Check for simple *, where the construct being repeated
// compiled to single opcode, and might be optimizable.
if (topLoc == fRXPat->fCompiledPat->size() - 1) {
int32_t repeatedOp = (int32_t)fRXPat->fCompiledPat->elementAti(topLoc);
if (URX_TYPE(repeatedOp) == URX_SETREF) {
// Emit optimized code for a [char set]*
int32_t loopOpI = URX_BUILD(URX_LOOP_SR_I, URX_VAL(repeatedOp));
fRXPat->fCompiledPat->setElementAt(loopOpI, topLoc);
dataLoc = fRXPat->fFrameSize;
fRXPat->fFrameSize++;
int32_t loopOpC = URX_BUILD(URX_LOOP_C, dataLoc);
fRXPat->fCompiledPat->addElement(loopOpC, *fStatus);
break;
}
if (URX_TYPE(repeatedOp) == URX_DOTANY ||
URX_TYPE(repeatedOp) == URX_DOTANY_ALL ||
URX_TYPE(repeatedOp) == URX_DOTANY_UNIX) {
// Emit Optimized code for .* operations.
int32_t loopOpI = URX_BUILD(URX_LOOP_DOT_I, 0);
if (URX_TYPE(repeatedOp) == URX_DOTANY_ALL) {
// URX_LOOP_DOT_I operand is a flag indicating . matches any mode.
loopOpI |= 1;
}
if ((fModeFlags & UREGEX_UNIX_LINES) != 0) {
loopOpI |= 2;
}
fRXPat->fCompiledPat->setElementAt(loopOpI, topLoc);
dataLoc = fRXPat->fFrameSize;
fRXPat->fFrameSize++;
int32_t loopOpC = URX_BUILD(URX_LOOP_C, dataLoc);
fRXPat->fCompiledPat->addElement(loopOpC, *fStatus);
break;
}
}
// Emit general case code for this *
// The optimizations did not apply.
int32_t saveStateLoc = blockTopLoc(TRUE);
int32_t jmpOp = URX_BUILD(URX_JMP_SAV, saveStateLoc+1);
// Check for minimum match length of zero, which requires
// extra loop-breaking code.
if (minMatchLength(saveStateLoc, fRXPat->fCompiledPat->size()-1) == 0) {
insertOp(saveStateLoc);
dataLoc = fRXPat->fFrameSize;
fRXPat->fFrameSize++;
int32_t op = URX_BUILD(URX_STO_INP_LOC, dataLoc);
fRXPat->fCompiledPat->setElementAt(op, saveStateLoc+1);
jmpOp = URX_BUILD(URX_JMP_SAV_X, saveStateLoc+2);
}
// Locate the position in the compiled pattern where the match will continue
// after completing the *. (4 or 5 in the comment above)
int32_t continueLoc = fRXPat->fCompiledPat->size()+1;
// Put together the save state op store it into the compiled code.
int32_t saveStateOp = URX_BUILD(URX_STATE_SAVE, continueLoc);
fRXPat->fCompiledPat->setElementAt(saveStateOp, saveStateLoc);
// Append the URX_JMP_SAV or URX_JMPX operation to the compiled pattern.
fRXPat->fCompiledPat->addElement(jmpOp, *fStatus);
}
break;
case doNGStar:
// Non-greedy *? quantifier
// compiles to
// 1. JMP 3
// 2. body of stuff being iterated over
// 3. STATE_SAVE 2
// 4 ...
{
int32_t jmpLoc = blockTopLoc(TRUE); // loc 1.
int32_t saveLoc = fRXPat->fCompiledPat->size(); // loc 3.
int32_t jmpOp = URX_BUILD(URX_JMP, saveLoc);
int32_t stateSaveOp = URX_BUILD(URX_STATE_SAVE, jmpLoc+1);
fRXPat->fCompiledPat->setElementAt(jmpOp, jmpLoc);
fRXPat->fCompiledPat->addElement(stateSaveOp, *fStatus);
}
break;
case doIntervalInit:
// The '{' opening an interval quantifier was just scanned.
// Init the counter varaiables that will accumulate the values as the digits
// are scanned.
fIntervalLow = 0;
fIntervalUpper = -1;
break;
case doIntevalLowerDigit:
// Scanned a digit from the lower value of an {lower,upper} interval
{
int32_t digitValue = u_charDigitValue(fC.fChar);
U_ASSERT(digitValue >= 0);
fIntervalLow = fIntervalLow*10 + digitValue;
if (fIntervalLow < 0) {
error(U_REGEX_NUMBER_TOO_BIG);
}
}
break;
case doIntervalUpperDigit:
// Scanned a digit from the upper value of an {lower,upper} interval
{
if (fIntervalUpper < 0) {
fIntervalUpper = 0;
}
int32_t digitValue = u_charDigitValue(fC.fChar);
U_ASSERT(digitValue >= 0);
fIntervalUpper = fIntervalUpper*10 + digitValue;
if (fIntervalUpper < 0) {
error(U_REGEX_NUMBER_TOO_BIG);
}
}
break;
case doIntervalSame:
// Scanned a single value interval like {27}. Upper = Lower.
fIntervalUpper = fIntervalLow;
break;
case doInterval:
// Finished scanning a normal {lower,upper} interval. Generate the code for it.
if (compileInlineInterval() == FALSE) {
compileInterval(URX_CTR_INIT, URX_CTR_LOOP);
}
break;
case doPossessiveInterval:
// Finished scanning a Possessive {lower,upper}+ interval. Generate the code for it.
{
// Remember the loc for the top of the block being looped over.
// (Can not reserve a slot in the compiled pattern at this time, because
// compileInterval needs to reserve also, and blockTopLoc can only reserve
// once per block.)
int32_t topLoc = blockTopLoc(FALSE);
// Produce normal looping code.
compileInterval(URX_CTR_INIT, URX_CTR_LOOP);
// Surround the just-emitted normal looping code with a STO_SP ... LD_SP
// just as if the loop was inclosed in atomic parentheses.
// First the STO_SP before the start of the loop
insertOp(topLoc);
int32_t varLoc = fRXPat->fDataSize; // Reserve a data location for saving the
fRXPat->fDataSize += 1; // state stack ptr.
int32_t op = URX_BUILD(URX_STO_SP, varLoc);
fRXPat->fCompiledPat->setElementAt(op, topLoc);
int32_t loopOp = (int32_t)fRXPat->fCompiledPat->popi();
U_ASSERT(URX_TYPE(loopOp) == URX_CTR_LOOP && URX_VAL(loopOp) == topLoc);
loopOp++; // point LoopOp after the just-inserted STO_SP
fRXPat->fCompiledPat->push(loopOp, *fStatus);
// Then the LD_SP after the end of the loop
op = URX_BUILD(URX_LD_SP, varLoc);
fRXPat->fCompiledPat->addElement(op, *fStatus);
}
break;
case doNGInterval:
// Finished scanning a non-greedy {lower,upper}? interval. Generate the code for it.
compileInterval(URX_CTR_INIT_NG, URX_CTR_LOOP_NG);
break;
case doIntervalError:
error(U_REGEX_BAD_INTERVAL);
break;
case doLiteralChar:
// We've just scanned a "normal" character from the pattern,
literalChar(fC.fChar);
break;
case doEscapedLiteralChar:
// We've just scanned an backslashed escaped character with no
// special meaning. It represents itself.
if ((fModeFlags & UREGEX_ERROR_ON_UNKNOWN_ESCAPES) != 0 &&
((fC.fChar >= 0x41 && fC.fChar<= 0x5A) || // in [A-Z]
(fC.fChar >= 0x61 && fC.fChar <= 0x7a))) { // in [a-z]
error(U_REGEX_BAD_ESCAPE_SEQUENCE);
}
literalChar(fC.fChar);
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 if (fModeFlags & UREGEX_UNIX_LINES) {
op = URX_BUILD(URX_DOTANY_UNIX, 0);
} else {
op = URX_BUILD(URX_DOTANY, 0);
}
fRXPat->fCompiledPat->addElement(op, *fStatus);
}
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;
} else if ((fModeFlags & UREGEX_MULTILINE) == 0 && (fModeFlags & UREGEX_UNIX_LINES) != 0) {
op = URX_CARET; // Only testing true start of input.
} else if ((fModeFlags & UREGEX_MULTILINE) != 0 && (fModeFlags & UREGEX_UNIX_LINES) != 0) {
op = URX_CARET_M_UNIX;
}
fRXPat->fCompiledPat->addElement(URX_BUILD(op, 0), *fStatus);
}
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_M;
} else if ((fModeFlags & UREGEX_MULTILINE) == 0 && (fModeFlags & UREGEX_UNIX_LINES) != 0) {
op = URX_DOLLAR_D;
} else if ((fModeFlags & UREGEX_MULTILINE) != 0 && (fModeFlags & UREGEX_UNIX_LINES) != 0) {
op = URX_DOLLAR_MD;
}
fRXPat->fCompiledPat->addElement(URX_BUILD(op, 0), *fStatus);
}
break;
case doBackslashA:
fixLiterals(FALSE);
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_CARET, 0), *fStatus);
break;
case doBackslashB:
{
#if UCONFIG_NO_BREAK_ITERATION==1
if (fModeFlags & UREGEX_UWORD) {
error(U_UNSUPPORTED_ERROR);
}
#endif
fixLiterals(FALSE);
int32_t op = (fModeFlags & UREGEX_UWORD)? URX_BACKSLASH_BU : URX_BACKSLASH_B;
fRXPat->fCompiledPat->addElement(URX_BUILD(op, 1), *fStatus);
}
break;
case doBackslashb:
{
#if UCONFIG_NO_BREAK_ITERATION==1
if (fModeFlags & UREGEX_UWORD) {
error(U_UNSUPPORTED_ERROR);
}
#endif
fixLiterals(FALSE);
int32_t op = (fModeFlags & UREGEX_UWORD)? URX_BACKSLASH_BU : URX_BACKSLASH_B;
fRXPat->fCompiledPat->addElement(URX_BUILD(op, 0), *fStatus);
}
break;
case doBackslashD:
fixLiterals(FALSE);
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_D, 1), *fStatus);
break;
case doBackslashd:
fixLiterals(FALSE);
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_D, 0), *fStatus);
break;
case doBackslashG:
fixLiterals(FALSE);
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_G, 0), *fStatus);
break;
case doBackslashS:
fixLiterals(FALSE);
fRXPat->fCompiledPat->addElement(
URX_BUILD(URX_STAT_SETREF_N, URX_ISSPACE_SET), *fStatus);
break;
case doBackslashs:
fixLiterals(FALSE);
fRXPat->fCompiledPat->addElement(
URX_BUILD(URX_STATIC_SETREF, URX_ISSPACE_SET), *fStatus);
break;
case doBackslashW:
fixLiterals(FALSE);
fRXPat->fCompiledPat->addElement(
URX_BUILD(URX_STAT_SETREF_N, URX_ISWORD_SET), *fStatus);
break;
case doBackslashw:
fixLiterals(FALSE);
fRXPat->fCompiledPat->addElement(
URX_BUILD(URX_STATIC_SETREF, URX_ISWORD_SET), *fStatus);
break;
case doBackslashX:
fixLiterals(FALSE);
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_X, 0), *fStatus);
break;
case doBackslashZ:
fixLiterals(FALSE);
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_DOLLAR, 0), *fStatus);
break;
case doBackslashz:
fixLiterals(FALSE);
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_Z, 0), *fStatus);
break;
case doEscapeError:
error(U_REGEX_BAD_ESCAPE_SEQUENCE);
break;
case doExit:
fixLiterals(FALSE);
returnVal = FALSE;
break;
case doProperty:
{
fixLiterals(FALSE);
UnicodeSet *theSet = scanProp();
compileSet(theSet);
}
break;
case doNamedChar:
{
UChar32 c = scanNamedChar();
literalChar(c);
}
break;
case doBackRef:
// BackReference. Somewhat unusual in that the front-end can not completely parse
// the regular expression, because the number of digits to be consumed
// depends on the number of capture groups that have been defined. So
// we have to do it here instead.
{
int32_t numCaptureGroups = fRXPat->fGroupMap->size();
int32_t groupNum = 0;
UChar32 c = fC.fChar;
for (;;) {
// Loop once per digit, for max allowed number of digits in a back reference.
int32_t digit = u_charDigitValue(c);
groupNum = groupNum * 10 + digit;
if (groupNum >= numCaptureGroups) {
break;
}
c = peekCharLL();
if (RegexStaticSets::gStaticSets->fRuleDigitsAlias->contains(c) == FALSE) {
break;
}
nextCharLL();
}
// Scan of the back reference in the source regexp is complete. Now generate
// the compiled code for it.
// Because capture groups can be forward-referenced by back-references,
// we fill the operand with the capture group number. At the end
// of compilation, it will be changed to the variable's location.
U_ASSERT(groupNum > 0); // 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);
}
break;
case doPossessivePlus:
// Possessive ++ quantifier.
// Compiles to
// 1. STO_SP
// 2. body of stuff being iterated over
// 3. STATE_SAVE 5
// 4. JMP 2
// 5. LD_SP
// 6. ...
//
// Note: TODO: This is pretty inefficient. A mass of saved state is built up
// then unconditionally discarded. Perhaps introduce a new opcode. Ticket 6056
//
{
// Emit the STO_SP
int32_t topLoc = blockTopLoc(TRUE);
int32_t stoLoc = fRXPat->fDataSize;
fRXPat->fDataSize++; // Reserve the data location for storing save stack ptr.
int32_t op = URX_BUILD(URX_STO_SP, stoLoc);
fRXPat->fCompiledPat->setElementAt(op, topLoc);
// Emit the STATE_SAVE
op = URX_BUILD(URX_STATE_SAVE, fRXPat->fCompiledPat->size()+2);
fRXPat->fCompiledPat->addElement(op, *fStatus);
// Emit the JMP
op = URX_BUILD(URX_JMP, topLoc+1);
fRXPat->fCompiledPat->addElement(op, *fStatus);
// Emit the LD_SP
op = URX_BUILD(URX_LD_SP, stoLoc);
fRXPat->fCompiledPat->addElement(op, *fStatus);
}
break;
case doPossessiveStar:
// Possessive *+ quantifier.
// Compiles to
// 1. STO_SP loc
// 2. STATE_SAVE 5
// 3. body of stuff being iterated over
// 4. JMP 2
// 5. LD_SP loc
// 6 ...
// TODO: do something to cut back the state stack each time through the loop.
{
// Reserve two slots at the top of the block.
int32_t topLoc = blockTopLoc(TRUE);
insertOp(topLoc);
// emit STO_SP loc
int32_t stoLoc = fRXPat->fDataSize;
fRXPat->fDataSize++; // Reserve the data location for storing save stack ptr.
int32_t op = URX_BUILD(URX_STO_SP, stoLoc);
fRXPat->fCompiledPat->setElementAt(op, topLoc);
// Emit the SAVE_STATE 5
int32_t L7 = fRXPat->fCompiledPat->size()+1;
op = URX_BUILD(URX_STATE_SAVE, L7);
fRXPat->fCompiledPat->setElementAt(op, topLoc+1);
// Append the JMP operation.
op = URX_BUILD(URX_JMP, topLoc+1);
fRXPat->fCompiledPat->addElement(op, *fStatus);
// Emit the LD_SP loc
op = URX_BUILD(URX_LD_SP, stoLoc);
fRXPat->fCompiledPat->addElement(op, *fStatus);
}
break;
case doPossessiveOpt:
// Possessive ?+ quantifier.
// Compiles to
// 1. STO_SP loc
// 2. SAVE_STATE 5
// 3. body of optional block
// 4. LD_SP loc
// 5. ...
//
{
// Reserve two slots at the top of the block.
int32_t topLoc = blockTopLoc(TRUE);
insertOp(topLoc);
// Emit the STO_SP
int32_t stoLoc = fRXPat->fDataSize;
fRXPat->fDataSize++; // Reserve the data location for storing save stack ptr.
int32_t op = URX_BUILD(URX_STO_SP, stoLoc);
fRXPat->fCompiledPat->setElementAt(op, topLoc);
// Emit the SAVE_STATE
int32_t continueLoc = fRXPat->fCompiledPat->size()+1;
op = URX_BUILD(URX_STATE_SAVE, continueLoc);
fRXPat->fCompiledPat->setElementAt(op, topLoc+1);
// Emit the LD_SP
op = URX_BUILD(URX_LD_SP, stoLoc);
fRXPat->fCompiledPat->addElement(op, *fStatus);
}
break;
case doBeginMatchMode:
fNewModeFlags = fModeFlags;
fSetModeFlag = TRUE;
break;
case doMatchMode: // (?i) and similar
{
int32_t bit = 0;
switch (fC.fChar) {
case 0x69: /* 'i' */ bit = UREGEX_CASE_INSENSITIVE; break;
case 0x64: /* 'd' */ bit = UREGEX_UNIX_LINES; break;
case 0x6d: /* 'm' */ bit = UREGEX_MULTILINE; break;
case 0x73: /* 's' */ bit = UREGEX_DOTALL; break;
case 0x75: /* 'u' */ bit = 0; /* Unicode casing */ break;
case 0x77: /* 'w' */ bit = UREGEX_UWORD; break;
case 0x78: /* 'x' */ bit = UREGEX_COMMENTS; break;
case 0x2d: /* '-' */ fSetModeFlag = FALSE; break;
default:
U_ASSERT(FALSE); // Should never happen. Other chars are filtered out
// by the scanner.
}
if (fSetModeFlag) {
fNewModeFlags |= bit;
} else {
fNewModeFlags &= ~bit;
}
}
break;
case doSetMatchMode:
// 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;
break;
case doMatchModeParen:
// We've got a (?i: or similar. Begin a parenthesized block, save old
// mode flags so they can be restored at the close of the block.
//
// Compile to a
// - NOP, which later may be replaced by a save-state if the
// parenthesized group gets a * quantifier, followed by
// - NOP, which may later be replaced by a save-state if there
// is an '|' alternation within the parens.
{
fixLiterals(FALSE);
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
// On the Parentheses stack, start a new frame and add the postions
// of the two NOPs (a normal non-capturing () frame, except for the
// saving of the orignal mode flags.)
fParenStack.push(fModeFlags, *fStatus);
fParenStack.push(flags, *fStatus); // Frame Marker
fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus); // The first NOP
fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus); // The second NOP
// Set the current mode flags to the new values.
U_ASSERT(fNewModeFlags < 0);
fModeFlags = fNewModeFlags;
}
break;
case doBadModeFlag:
error(U_REGEX_INVALID_FLAG);
break;
case doSuppressComments:
// We have just scanned a '(?'. We now need to prevent the character scanner from
// treating a '#' as a to-the-end-of-line comment.
// (This Perl compatibility just gets uglier and uglier to do...)
fEOLComments = FALSE;
break;
case doSetAddAmp:
{
UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
set->add(chAmp);
}
break;
case doSetAddDash:
{
UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
set->add(chDash);
}
break;
case doSetBackslash_s:
{
UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
set->addAll(*RegexStaticSets::gStaticSets->fPropSets[URX_ISSPACE_SET]);
break;
}
case doSetBackslash_S:
{
UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
UnicodeSet SSet(*RegexStaticSets::gStaticSets->fPropSets[URX_ISSPACE_SET]);
SSet.complement();
set->addAll(SSet);
break;
}
case doSetBackslash_d:
{
UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
// TODO - make a static set, ticket 6058.
addCategory(set, U_GC_ND_MASK, *fStatus);
break;
}
case doSetBackslash_D:
{
UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
UnicodeSet digits;
// TODO - make a static set, ticket 6058.
digits.applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, U_GC_ND_MASK, *fStatus);
digits.complement();
set->addAll(digits);
break;
}
case doSetBackslash_w:
{
UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
set->addAll(*RegexStaticSets::gStaticSets->fPropSets[URX_ISWORD_SET]);
break;
}
case doSetBackslash_W:
{
UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
UnicodeSet SSet(*RegexStaticSets::gStaticSets->fPropSets[URX_ISWORD_SET]);
SSet.complement();
set->addAll(SSet);
break;
}
case doSetBegin:
fixLiterals(FALSE);
fSetStack.push(new UnicodeSet(), *fStatus);
fSetOpStack.push(setStart, *fStatus);
if ((fModeFlags & UREGEX_CASE_INSENSITIVE) != 0) {
fSetOpStack.push(setCaseClose, *fStatus);
}
break;
case doSetBeginDifference1:
// We have scanned something like [[abc]-[
// Set up a new UnicodeSet for the set beginning with the just-scanned '['
// Push a Difference operator, which will cause the new set to be subtracted from what
// went before once it is created.
setPushOp(setDifference1);
fSetOpStack.push(setStart, *fStatus);
if ((fModeFlags & UREGEX_CASE_INSENSITIVE) != 0) {
fSetOpStack.push(setCaseClose, *fStatus);
}
break;
case doSetBeginIntersection1:
// We have scanned something like [[abc]&[
// Need both the '&' operator and the open '[' operator.
setPushOp(setIntersection1);
fSetOpStack.push(setStart, *fStatus);
if ((fModeFlags & UREGEX_CASE_INSENSITIVE) != 0) {
fSetOpStack.push(setCaseClose, *fStatus);
}
break;
case doSetBeginUnion:
// We have scanned something like [[abc][
// Need to handle the union operation explicitly [[abc] | [
setPushOp(setUnion);
fSetOpStack.push(setStart, *fStatus);
if ((fModeFlags & UREGEX_CASE_INSENSITIVE) != 0) {
fSetOpStack.push(setCaseClose, *fStatus);
}
break;
case doSetDifference2:
// We have scanned something like [abc--
// Consider this to unambiguously be a set difference operator.
setPushOp(setDifference2);
break;
case doSetEnd:
// Have encountered the ']' that closes a set.
// Force the evaluation of any pending operations within this set,
// leave the completed set on the top of the set stack.
setEval(setEnd);
U_ASSERT(fSetOpStack.peeki()==setStart);
fSetOpStack.popi();
break;
case doSetFinish:
{
// Finished a complete set expression, including all nested sets.
// The close bracket has already triggered clearing out pending set operators,
// the operator stack should be empty and the operand stack should have just
// one entry, the result set.
U_ASSERT(fSetOpStack.empty());
UnicodeSet *theSet = (UnicodeSet *)fSetStack.pop();
U_ASSERT(fSetStack.empty());
compileSet(theSet);
break;
}
case doSetIntersection2:
// Have scanned something like [abc&&
setPushOp(setIntersection2);
break;
case doSetLiteral:
// Union the just-scanned literal character into the set being built.
// This operation is the highest precedence set operation, so we can always do
// it immediately, without waiting to see what follows. It is necessary to perform
// any pending '-' or '&' operation first, because these have the same precedence
// as union-ing in a literal'
{
setEval(setUnion);
UnicodeSet *s = (UnicodeSet *)fSetStack.peek();
s->add(fC.fChar);
fLastSetLiteral = fC.fChar;
break;
}
case doSetLiteralEscaped:
// A back-slash escaped literal character was encountered.
// Processing is the same as with setLiteral, above, with the addition of
// the optional check for errors on escaped ASCII letters.
{
if ((fModeFlags & UREGEX_ERROR_ON_UNKNOWN_ESCAPES) != 0 &&
((fC.fChar >= 0x41 && fC.fChar<= 0x5A) || // in [A-Z]
(fC.fChar >= 0x61 && fC.fChar <= 0x7a))) { // in [a-z]
error(U_REGEX_BAD_ESCAPE_SEQUENCE);
}
setEval(setUnion);
UnicodeSet *s = (UnicodeSet *)fSetStack.peek();
s->add(fC.fChar);
fLastSetLiteral = fC.fChar;
break;
}
case doSetNamedChar:
// Scanning a \N{UNICODE CHARACTER NAME}
// Aside from the source of the character, the processing is identical to doSetLiteral,
// above.
{
UChar32 c = scanNamedChar();
setEval(setUnion);
UnicodeSet *s = (UnicodeSet *)fSetStack.peek();
s->add(c);
fLastSetLiteral = c;
break;
}
case doSetNamedRange:
// We have scanned literal-\N{CHAR NAME}. Add the range to the set.
// The left character is already in the set, and is saved in fLastSetLiteral.
// The right side needs to be picked up, the scan is at the 'N'.
// Lower Limit > Upper limit being an error matches both Java
// and ICU UnicodeSet behavior.
{
UChar32 c = scanNamedChar();
if (U_SUCCESS(*fStatus) && fLastSetLiteral > c) {
error(U_REGEX_INVALID_RANGE);
}
UnicodeSet *s = (UnicodeSet *)fSetStack.peek();
s->add(fLastSetLiteral, c);
fLastSetLiteral = c;
break;
}
case doSetNegate:
// Scanned a '^' at the start of a set.
// Push the negation operator onto the set op stack.
// A twist for case-insensitive matching:
// the case closure operation must happen _before_ negation.
// But the case closure operation will already be on the stack if it's required.
// This requires checking for case closure, and swapping the stack order
// if it is present.
{
int32_t tosOp = fSetOpStack.peeki();
if (tosOp == setCaseClose) {
fSetOpStack.popi();
fSetOpStack.push(setNegation, *fStatus);
fSetOpStack.push(setCaseClose, *fStatus);
} else {
fSetOpStack.push(setNegation, *fStatus);
}
}
break;
case doSetNoCloseError:
error(U_REGEX_MISSING_CLOSE_BRACKET);
break;
case doSetOpError:
error(U_REGEX_RULE_SYNTAX); // -- or && at the end of a set. Illegal.
break;
case doSetPosixProp:
{
UnicodeSet *s = scanPosixProp();
if (s != NULL) {
UnicodeSet *tos = (UnicodeSet *)fSetStack.peek();
tos->addAll(*s);
delete s;
} // else error. scanProp() reported the error status already.
}
break;
case doSetProp:
// Scanned a \p \P within [brackets].
{
UnicodeSet *s = scanProp();
if (s != NULL) {
UnicodeSet *tos = (UnicodeSet *)fSetStack.peek();
tos->addAll(*s);
delete s;
} // else error. scanProp() reported the error status already.
}
break;
case doSetRange:
// We have scanned literal-literal. Add the range to the set.
// The left character is already in the set, and is saved in fLastSetLiteral.
// The right side is the current character.
// Lower Limit > Upper limit being an error matches both Java
// and ICU UnicodeSet behavior.
{
if (fLastSetLiteral > fC.fChar) {
error(U_REGEX_INVALID_RANGE);
}
UnicodeSet *s = (UnicodeSet *)fSetStack.peek();
s->add(fLastSetLiteral, fC.fChar);
break;
}
default:
U_ASSERT(FALSE);
error(U_REGEX_INTERNAL_ERROR);
break;
}
if (U_FAILURE(*fStatus)) {
returnVal = FALSE;
}
return returnVal;
}
//------------------------------------------------------------------------------
//
// literalChar We've encountered a literal character from the pattern,
// or an escape sequence that reduces to a character.
// Add it to the string containing all literal chars/strings from
// the pattern.
//
//------------------------------------------------------------------------------
void RegexCompile::literalChar(UChar32 c) {
fLiteralChars.append(c);
}
//------------------------------------------------------------------------------
//
// fixLiterals When compiling something that can follow a literal
// 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
// apply to that char alone. Example: abc*
// The * must apply to the 'c' only.
//
//------------------------------------------------------------------------------
void RegexCompile::fixLiterals(UBool 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;
}
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 (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;
}
// 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);
}
fRXPat->fCompiledPat->addElement(op, *fStatus);
} 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());
}
fRXPat->fCompiledPat->addElement(op, *fStatus);
op = URX_BUILD(URX_STRING_LEN, fLiteralChars.length());
fRXPat->fCompiledPat->addElement(op, *fStatus);
// Add this string into the accumulated strings of the compiled pattern.
fRXPat->fLiteralText.append(fLiteralChars);
}
fLiteralChars.remove();
}
//------------------------------------------------------------------------------
//
// insertOp() Insert a slot for a new opcode into the already
// compiled pattern code.
//
// Fill the slot with a NOP. Our caller will replace it
// with what they really wanted.
//
//------------------------------------------------------------------------------
void RegexCompile::insertOp(int32_t where) {
UVector64 *code = fRXPat->fCompiledPat;
U_ASSERT(where>0 && where < code->size());
int32_t nop = URX_BUILD(URX_NOP, 0);
code->insertElementAt(nop, where, *fStatus);
// Walk through the pattern, looking for any ops with targets that
// were moved down by the insert. Fix them.
int32_t loc;
for (loc=0; loc<code->size(); loc++) {
int32_t op = (int32_t)code->elementAti(loc);
int32_t opType = URX_TYPE(op);
int32_t opValue = URX_VAL(op);
if ((opType == URX_JMP ||
opType == URX_JMPX ||
opType == URX_STATE_SAVE ||
opType == URX_CTR_LOOP ||
opType == URX_CTR_LOOP_NG ||
opType == URX_JMP_SAV ||
opType == URX_JMP_SAV_X ||
opType == URX_RELOC_OPRND) && opValue > where) {
// Target location for this opcode is after the insertion point and
// needs to be incremented to adjust for the insertion.
opValue++;
op = URX_BUILD(opType, opValue);
code->setElementAt(op, loc);
}
}
// Now fix up the parentheses stack. All positive values in it are locations in
// the compiled pattern. (Negative values are frame boundaries, and don't need fixing.)
for (loc=0; loc<fParenStack.size(); loc++) {
int32_t x = fParenStack.elementAti(loc);
U_ASSERT(x < code->size());
if (x>where) {
x++;
fParenStack.setElementAt(x, loc);
}
}
if (fMatchCloseParen > where) {
fMatchCloseParen++;
}
if (fMatchOpenParen > where) {
fMatchOpenParen++;
}
}
//------------------------------------------------------------------------------
//
// blockTopLoc() Find or create a location in the compiled pattern
// at the start of the operation or block that has
// just been compiled. Needed when a quantifier (* or
// whatever) appears, and we need to add an operation
// at the start of the thing being quantified.
//
// (Parenthesized Blocks) have a slot with a NOP that
// is reserved for this purpose. .* or similar don't
// and a slot needs to be added.
//
// parameter reserveLoc : TRUE - ensure that there is space to add an opcode
// at the returned location.
// FALSE - just return the address,
// do not reserve a location there.
//
//------------------------------------------------------------------------------
int32_t RegexCompile::blockTopLoc(UBool reserveLoc) {
int32_t theLoc;
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.
theLoc = fMatchOpenParen; // A slot is already reserved for us.
U_ASSERT(theLoc > 0);
U_ASSERT(URX_TYPE(((uint32_t)fRXPat->fCompiledPat->elementAti(theLoc))) == URX_NOP);
}
else {
// Item just compiled is a single thing, a ".", or a single char, a string or a set reference.
// No slot for STATE_SAVE was pre-reserved in the compiled code.
// We need to make space now.
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 nop = URX_BUILD(URX_NOP, 0);
fRXPat->fCompiledPat->insertElementAt(nop, theLoc, *fStatus);
}
}
return theLoc;
}
//------------------------------------------------------------------------------
//
// handleCloseParen When compiling a close paren, we need to go back
// and fix up any JMP or SAVE operations within the
// parenthesized block that need to target the end
// of the block. The locations of these are kept on
// the paretheses stack.
//
// This function is called both when encountering a
// real ) and at the end of the pattern.
//
//------------------------------------------------------------------------------
void RegexCompile::handleCloseParen() {
int32_t patIdx;
int32_t patOp;
if (fParenStack.size() <= 0) {
error(U_REGEX_MISMATCHED_PAREN);
return;
}
// Emit code for any pending literals.
fixLiterals(FALSE);
// Fixup any operations within the just-closed parenthesized group
// that need to reference the end of the (block).
// (The first one popped from the stack is an unused slot for
// alternation (OR) state save, but applying the fixup to it does no harm.)
for (;;) {
patIdx = fParenStack.popi();
if (patIdx < 0) {
// value < 0 flags the start of the frame on the paren stack.
break;
}
U_ASSERT(patIdx>0 && patIdx <= fRXPat->fCompiledPat->size());
patOp = (int32_t)fRXPat->fCompiledPat->elementAti(patIdx);
U_ASSERT(URX_VAL(patOp) == 0); // Branch target for JMP should not be set.
patOp |= fRXPat->fCompiledPat->size(); // Set it now.
fRXPat->fCompiledPat->setElementAt(patOp, patIdx);
fMatchOpenParen = patIdx;
}
// At the close of any parenthesized block, restore the match mode flags to
// the value they had at the open paren. Saved value is
// at the top of the paren stack.
fModeFlags = fParenStack.popi();
U_ASSERT(fModeFlags < 0);
// DO any additional fixups, depending on the specific kind of
// parentesized grouping this is
switch (patIdx) {
case plain:
case flags:
// No additional fixups required.
// (Grouping-only parentheses)
break;
case capturing:
// Capturing Parentheses.
// Insert a End Capture op into the pattern.
// The frame offset of the variables for this cg is obtained from the
// start capture op and put it into the end-capture op.
{
int32_t captureOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen+1);
U_ASSERT(URX_TYPE(captureOp) == URX_START_CAPTURE);
int32_t frameVarLocation = URX_VAL(captureOp);
int32_t endCaptureOp = URX_BUILD(URX_END_CAPTURE, frameVarLocation);
fRXPat->fCompiledPat->addElement(endCaptureOp, *fStatus);
}
break;
case atomic:
// Atomic Parenthesis.
// Insert a LD_SP operation to restore the state stack to the position
// it was when the atomic parens were entered.
{
int32_t stoOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen+1);
U_ASSERT(URX_TYPE(stoOp) == URX_STO_SP);
int32_t stoLoc = URX_VAL(stoOp);
int32_t ldOp = URX_BUILD(URX_LD_SP, stoLoc);
fRXPat->fCompiledPat->addElement(ldOp, *fStatus);
}
break;
case lookAhead:
{
int32_t startOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen-5);
U_ASSERT(URX_TYPE(startOp) == URX_LA_START);
int32_t dataLoc = URX_VAL(startOp);
int32_t op = URX_BUILD(URX_LA_END, dataLoc);
fRXPat->fCompiledPat->addElement(op, *fStatus);
}
break;
case negLookAhead:
{
// See comment at doOpenLookAheadNeg
int32_t startOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen-1);
U_ASSERT(URX_TYPE(startOp) == URX_LA_START);
int32_t dataLoc = URX_VAL(startOp);
int32_t op = URX_BUILD(URX_LA_END, dataLoc);
fRXPat->fCompiledPat->addElement(op, *fStatus);
op = URX_BUILD(URX_BACKTRACK, 0);
fRXPat->fCompiledPat->addElement(op, *fStatus);
op = URX_BUILD(URX_LA_END, dataLoc);
fRXPat->fCompiledPat->addElement(op, *fStatus);
// Patch the URX_SAVE near the top of the block.
// The destination of the SAVE is the final LA_END that was just added.
int32_t saveOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen);
U_ASSERT(URX_TYPE(saveOp) == URX_STATE_SAVE);
int32_t dest = fRXPat->fCompiledPat->size()-1;
saveOp = URX_BUILD(URX_STATE_SAVE, dest);
fRXPat->fCompiledPat->setElementAt(saveOp, fMatchOpenParen);
}
break;
case lookBehind:
{
// See comment at doOpenLookBehind.
// Append the URX_LB_END and URX_LA_END to the compiled pattern.
int32_t startOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen-4);
U_ASSERT(URX_TYPE(startOp) == URX_LB_START);
int32_t dataLoc = URX_VAL(startOp);
int32_t op = URX_BUILD(URX_LB_END, dataLoc);
fRXPat->fCompiledPat->addElement(op, *fStatus);
op = URX_BUILD(URX_LA_END, dataLoc);
fRXPat->fCompiledPat->addElement(op, *fStatus);
// Determine the min and max bounds for the length of the
// string that the pattern can match.
// An unbounded upper limit is an error.
int32_t patEnd = fRXPat->fCompiledPat->size() - 1;
int32_t minML = minMatchLength(fMatchOpenParen, patEnd);
int32_t maxML = maxMatchLength(fMatchOpenParen, patEnd);
if (maxML == INT32_MAX) {
error(U_REGEX_LOOK_BEHIND_LIMIT);
break;
}
U_ASSERT(minML <= maxML);
// Insert the min and max match len bounds into the URX_LB_CONT op that
// appears at the top of the look-behind block, at location fMatchOpenParen+1
fRXPat->fCompiledPat->setElementAt(minML, fMatchOpenParen-2);
fRXPat->fCompiledPat->setElementAt(maxML, fMatchOpenParen-1);
}
break;
case lookBehindN:
{
// See comment at doOpenLookBehindNeg.
// Append the URX_LBN_END to the compiled pattern.
int32_t startOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen-5);
U_ASSERT(URX_TYPE(startOp) == URX_LB_START);
int32_t dataLoc = URX_VAL(startOp);
int32_t op = URX_BUILD(URX_LBN_END, dataLoc);
fRXPat->fCompiledPat->addElement(op, *fStatus);
// Determine the min and max bounds for the length of the
// string that the pattern can match.
// An unbounded upper limit is an error.
int32_t patEnd = fRXPat->fCompiledPat->size() - 1;
int32_t minML = minMatchLength(fMatchOpenParen, patEnd);
int32_t maxML = maxMatchLength(fMatchOpenParen, patEnd);
if (maxML == INT32_MAX) {
error(U_REGEX_LOOK_BEHIND_LIMIT);
break;
}
U_ASSERT(minML <= maxML);
// Insert the min and max match len bounds into the URX_LB_CONT op that
// appears at the top of the look-behind block, at location fMatchOpenParen+1
fRXPat->fCompiledPat->setElementAt(minML, fMatchOpenParen-3);
fRXPat->fCompiledPat->setElementAt(maxML, fMatchOpenParen-2);
// Insert the pattern location to continue at after a successful match
// as the last operand of the URX_LBN_CONT
op = URX_BUILD(URX_RELOC_OPRND, fRXPat->fCompiledPat->size());
fRXPat->fCompiledPat->setElementAt(op, fMatchOpenParen-1);
}
break;
default:
U_ASSERT(FALSE);
}
// remember the next location in the compiled pattern.
// The compilation of Quantifiers will look at this to see whether its looping
// over a parenthesized block or a single item
fMatchCloseParen = fRXPat->fCompiledPat->size();
}
//------------------------------------------------------------------------------
//
// compileSet Compile the pattern operations for a reference to a
// UnicodeSet.
//
//------------------------------------------------------------------------------
void RegexCompile::compileSet(UnicodeSet *theSet)
{
if (theSet == NULL) {
return;
}
// Remove any strings from the set.
// There shoudn't be any, but just in case.
// (Case Closure can add them; if we had a simple case closure avaialble that
// ignored strings, that would be better.)
theSet->removeAllStrings();
int32_t setSize = theSet->size();
switch (setSize) {
case 0:
{
// Set of no elements. Always fails to match.
fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKTRACK, 0), *fStatus);
delete theSet;
}
break;
case 1:
{
// The set contains only a single code point. Put it into
// the compiled pattern as a single char operation rather
// than a set, and discard the set itself.
literalChar(theSet->charAt(0));
delete theSet;
}
break;
default:
{
// The set contains two or more chars. (the normal case)
// Put it into the compiled pattern as a set.
int32_t setNumber = fRXPat->fSets->size();
fRXPat->fSets->addElement(theSet, *fStatus);
int32_t setOp = URX_BUILD(URX_SETREF, setNumber);
fRXPat->fCompiledPat->addElement(setOp, *fStatus);
}
}
}
//------------------------------------------------------------------------------
//
// compileInterval Generate the code for a {min, max} style interval quantifier.
// Except for the specific opcodes used, the code is the same
// for all three types (greedy, non-greedy, possessive) of
// intervals. The opcodes are supplied as parameters.
//
// The code for interval loops has this form:
// 0 CTR_INIT counter loc (in stack frame)
// 1 5 patt address of CTR_LOOP at bottom of block
// 2 min count
// 3 max count (-1 for unbounded)
// 4 ... block to be iterated over
// 5 CTR_LOOP
//
// In
//------------------------------------------------------------------------------
void RegexCompile::compileInterval(int32_t InitOp, int32_t LoopOp)
{
// The CTR_INIT op at the top of the block with the {n,m} quantifier takes
// four slots in the compiled code. Reserve them.
int32_t topOfBlock = blockTopLoc(TRUE);
insertOp(topOfBlock);
insertOp(topOfBlock);
insertOp(topOfBlock);
// The operands for the CTR_INIT opcode include the index in the matcher data
// of the counter. Allocate it now.
int32_t counterLoc = fRXPat->fFrameSize;
fRXPat->fFrameSize++;
int32_t op = URX_BUILD(InitOp, counterLoc);
fRXPat->fCompiledPat->setElementAt(op, topOfBlock);
// The second operand of CTR_INIT is the location following the end of the loop.
// Must put in as a URX_RELOC_OPRND so that the value will be adjusted if the
// compilation of something later on causes the code to grow and the target
// position to move.
int32_t loopEnd = fRXPat->fCompiledPat->size();
op = URX_BUILD(URX_RELOC_OPRND, loopEnd);
fRXPat->fCompiledPat->setElementAt(op, topOfBlock+1);
// Followed by the min and max counts.
fRXPat->fCompiledPat->setElementAt(fIntervalLow, topOfBlock+2);
fRXPat->fCompiledPat->setElementAt(fIntervalUpper, topOfBlock+3);
// Apend the CTR_LOOP op. The operand is the location of the CTR_INIT op.
// Goes at end of the block being looped over, so just append to the code so far.
op = URX_BUILD(LoopOp, topOfBlock);
fRXPat->fCompiledPat->addElement(op, *fStatus);
if ((fIntervalLow & 0xff000000) != 0 ||
(fIntervalUpper > 0 && (fIntervalUpper & 0xff000000) != 0)) {
error(U_REGEX_NUMBER_TOO_BIG);
}
if (fIntervalLow > fIntervalUpper && fIntervalUpper != -1) {
error(U_REGEX_MAX_LT_MIN);
}
}
UBool RegexCompile::compileInlineInterval() {
if (fIntervalUpper > 10 || fIntervalUpper < fIntervalLow) {
// Too big to inline. Fail, which will cause looping code to be generated.
// (Upper < Lower picks up unbounded upper and errors, both.)
return FALSE;
}
int32_t topOfBlock = blockTopLoc(FALSE);
if (fIntervalUpper == 0) {
// Pathological case. Attempt no matches, as if the block doesn't exist.
fRXPat->fCompiledPat->setSize(topOfBlock);
return TRUE;
}
if (topOfBlock != fRXPat->fCompiledPat->size()-1 && fIntervalUpper != 1) {
// The thing being repeated is not a single op, but some
// more complex block. Do it as a loop, not inlines.
// Note that things "repeated" a max of once are handled as inline, because
// the one copy of the code already generated is just fine.
return FALSE;
}
// Pick up the opcode that is to be repeated
//
int32_t op = (int32_t)fRXPat->fCompiledPat->elementAti(topOfBlock);
// Compute the pattern location where the inline sequence
// will end, and set up the state save op that will be needed.
//
int32_t endOfSequenceLoc = fRXPat->fCompiledPat->size()-1
+ fIntervalUpper + (fIntervalUpper-fIntervalLow);
int32_t saveOp = URX_BUILD(URX_STATE_SAVE, endOfSequenceLoc);
if (fIntervalLow == 0) {
insertOp(topOfBlock);
fRXPat->fCompiledPat->setElementAt(saveOp, topOfBlock);
}
// Loop, emitting the op for the thing being repeated each time.
// Loop starts at 1 because one instance of the op already exists in the pattern,
// it was put there when it was originally encountered.
int32_t i;
for (i=1; i<fIntervalUpper; i++ ) {
if (i == fIntervalLow) {
fRXPat->fCompiledPat->addElement(saveOp, *fStatus);
}
if (i > fIntervalLow) {
fRXPat->fCompiledPat->addElement(saveOp, *fStatus);
}
fRXPat->fCompiledPat->addElement(op, *fStatus);
}
return TRUE;
}
//------------------------------------------------------------------------------
//
// matchStartType Determine how a match can start.
// Used to optimize find() operations.
//
// Operation is very similar to minMatchLength(). Walk the compiled
// pattern, keeping an on-going minimum-match-length. For any
// op where the min match coming in is zero, add that ops possible
// starting matches to the possible starts for the overall pattern.
//
//------------------------------------------------------------------------------
void RegexCompile::matchStartType() {
if (U_FAILURE(*fStatus)) {
return;
}
int32_t loc; // Location in the pattern of the current op being processed.
int32_t op; // The op being processed
int32_t opType; // The opcode type of the op
int32_t currentLen = 0; // Minimum length of a match to this point (loc) in the pattern
int32_t numInitialStrings = 0; // Number of strings encountered that could match at start.
UBool atStart = TRUE; // True if no part of the pattern yet encountered
// could have advanced the position in a match.
// (Maximum match length so far == 0)
// forwardedLength is a vector holding minimum-match-length values that
// are propagated forward in the pattern by JMP or STATE_SAVE operations.
// It must be one longer than the pattern being checked because some ops
// will jmp to a end-of-block+1 location from within a block, and we must
// count those when checking the block.
int32_t end = fRXPat->fCompiledPat->size();
UVector32 forwardedLength(end+1, *fStatus);
forwardedLength.setSize(end+1);
for (loc=3; loc<end; loc++) {
forwardedLength.setElementAt(INT32_MAX, loc);
}
for (loc = 3; loc<end; loc++) {
op = (int32_t)fRXPat->fCompiledPat->elementAti(loc);
opType = URX_TYPE(op);
// The loop is advancing linearly through the pattern.
// If the op we are now at was the destination of a branch in the pattern,
// and that path has a shorter minimum length than the current accumulated value,
// replace the current accumulated value.
if (forwardedLength.elementAti(loc) < currentLen) {
currentLen = forwardedLength.elementAti(loc);
U_ASSERT(currentLen>=0 && currentLen < INT32_MAX);
}
switch (opType) {
// Ops that don't change the total length matched
case URX_RESERVED_OP:
case URX_END:
case URX_FAIL:
case URX_STRING_LEN:
case URX_NOP:
case URX_START_CAPTURE:
case URX_END_CAPTURE:
case URX_BACKSLASH_B:
case URX_BACKSLASH_BU:
case URX_BACKSLASH_G:
case URX_BACKSLASH_Z:
case URX_DOLLAR:
case URX_DOLLAR_M:
case URX_DOLLAR_D:
case URX_DOLLAR_MD:
case URX_RELOC_OPRND:
case URX_STO_INP_LOC:
case URX_BACKREF: // BackRef. Must assume that it might be a zero length match
case URX_BACKREF_I:
case URX_STO_SP: // Setup for atomic or possessive blocks. Doesn't change what can match.
case URX_LD_SP:
break;
case URX_CARET:
if (atStart) {
fRXPat->fStartType = START_START;
}
break;
case URX_CARET_M:
case URX_CARET_M_UNIX:
if (atStart) {
fRXPat->fStartType = START_LINE;
}
break;
case URX_ONECHAR:
if (currentLen == 0) {
// This character could appear at the start of a match.
// Add it to the set of possible starting characters.
fRXPat->fInitialChars->add(URX_VAL(op));
numInitialStrings += 2;
}
currentLen++;
atStart = FALSE;
break;
case URX_SETREF:
if (currentLen == 0) {
int32_t sn = URX_VAL(op);
U_ASSERT(sn > 0 && sn < fRXPat->fSets->size());
const UnicodeSet *s = (UnicodeSet *)fRXPat->fSets->elementAt(sn);
fRXPat->fInitialChars->addAll(*s);
numInitialStrings += 2;
}
currentLen++;
atStart = FALSE;
break;
case URX_LOOP_SR_I:
// [Set]*, like a SETREF, above, in what it can match,
// but may not match at all, so currentLen is not incremented.
if (currentLen == 0) {
int32_t sn = URX_VAL(op);
U_ASSERT(sn > 0 && sn < fRXPat->fSets->size());
const UnicodeSet *s = (UnicodeSet *)fRXPat->fSets->elementAt(sn);
fRXPat->fInitialChars->addAll(*s);
numInitialStrings += 2;
}
atStart = FALSE;
break;
case URX_LOOP_DOT_I:
if (currentLen == 0) {
// .* at the start of a pattern.
// Any character can begin the match.
fRXPat->fInitialChars->clear();
fRXPat->fInitialChars->complement();
numInitialStrings += 2;
}
atStart = FALSE;
break;
case URX_STATIC_SETREF:
if (currentLen == 0) {
int32_t sn = URX_VAL(op);
U_ASSERT(sn>0 && sn<URX_LAST_SET);
const UnicodeSet *s = fRXPat->fStaticSets[sn];
fRXPat->fInitialChars->addAll(*s);
numInitialStrings += 2;
}
currentLen++;
atStart = FALSE;
break;
case URX_STAT_SETREF_N:
if (currentLen == 0) {
int32_t sn = URX_VAL(op);
const UnicodeSet *s = fRXPat->fStaticSets[sn];
UnicodeSet sc(*s);
sc.complement();
fRXPat->fInitialChars->addAll(sc);
numInitialStrings += 2;
}
currentLen++;
atStart = FALSE;
break;
case URX_BACKSLASH_D:
// Digit Char
if (currentLen == 0) {
UnicodeSet s;
s.applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, U_GC_ND_MASK, *fStatus);
if (URX_VAL(op) != 0) {
s.complement();
}
fRXPat->fInitialChars->addAll(s);
numInitialStrings += 2;
}
currentLen++;
atStart = FALSE;
break;
case URX_ONECHAR_I:
// Case Insensitive Single Character.
if (currentLen == 0) {
UChar32 c = URX_VAL(op);
if (u_hasBinaryProperty(c, UCHAR_CASE_SENSITIVE)) {
// 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.
fRXPat->fInitialChars->add(c);
}
numInitialStrings += 2;
}
currentLen++;
atStart = FALSE;
break;
case URX_BACKSLASH_X: // Grahpeme Cluster. Minimum is 1, max unbounded.
case URX_DOTANY_ALL: // . matches one or two.
case URX_DOTANY:
case URX_DOTANY_UNIX:
if (currentLen == 0) {
// These constructs are all bad news when they appear at the start
// of a match. Any character can begin the match.
fRXPat->fInitialChars->clear();
fRXPat->fInitialChars->complement();
numInitialStrings += 2;
}
currentLen++;
atStart = FALSE;
break;
case URX_JMPX:
loc++; // Except for extra operand on URX_JMPX, same as URX_JMP.
case URX_JMP:
{
int32_t jmpDest = URX_VAL(op);
if (jmpDest < loc) {
// Loop of some kind. Can safely ignore, the worst that will happen
// is that we understate the true minimum length
currentLen = forwardedLength.elementAti(loc+1);
} else {
// Forward jump. Propagate the current min length to the target loc of the jump.
U_ASSERT(jmpDest <= end+1);
if (forwardedLength.elementAti(jmpDest) > currentLen) {
forwardedLength.setElementAt(currentLen, jmpDest);
}
}
}
atStart = FALSE;
break;
case URX_JMP_SAV:
case URX_JMP_SAV_X:
// Combo of state save to the next loc, + jmp backwards.
// Net effect on min. length computation is nothing.
atStart = FALSE;
break;
case URX_BACKTRACK:
// Fails are kind of like a branch, except that the min length was
// propagated already, by the state save.
currentLen = forwardedLength.elementAti(loc+1);
atStart = FALSE;
break;
case URX_STATE_SAVE:
{
// State Save, for forward jumps, propagate the current minimum.
// of the state save.
int32_t jmpDest = URX_VAL(op);
if (jmpDest > loc) {
if (currentLen < forwardedLength.elementAti(jmpDest)) {
forwardedLength.setElementAt(currentLen, jmpDest);
}
}
}
atStart = FALSE;
break;
case URX_STRING:
{
loc++;
int32_t stringLenOp = (int32_t)fRXPat->fCompiledPat->elementAti(loc);
int32_t stringLen = URX_VAL(stringLenOp);
U_ASSERT(URX_TYPE(stringLenOp) == URX_STRING_LEN);
U_ASSERT(stringLenOp >= 2);
if (currentLen == 0) {
// Add the starting character of this string to the set of possible starting
// characters for this pattern.
int32_t stringStartIdx = URX_VAL(op);
UChar32 c = fRXPat->fLiteralText.char32At(stringStartIdx);
fRXPat->fInitialChars->add(c);
// Remember this string. After the entire pattern has been checked,
// if nothing else is identified that can start a match, we'll use it.
numInitialStrings++;
fRXPat->fInitialStringIdx = stringStartIdx;
fRXPat->fInitialStringLen = stringLen;
}
currentLen += stringLen;
atStart = FALSE;
}
break;
case URX_STRING_I:
{
// Case-insensitive string. Unlike exact-match strings, we won't
// attempt a string search for possible match positions. But we
// do update the set of possible starting characters.
loc++;
int32_t stringLenOp = (int32_t)fRXPat->fCompiledPat->elementAti(loc);
int32_t stringLen = URX_VAL(stringLenOp);
U_ASSERT(URX_TYPE(stringLenOp) == URX_STRING_LEN);
U_ASSERT(stringLenOp >= 2);
if (currentLen == 0) {
// Add the starting character of this string to the set of possible starting
// characters for this pattern.
int32_t stringStartIdx = URX_VAL(op);
UChar32 c = fRXPat->fLiteralText.char32At(stringStartIdx);
UnicodeSet s(c, c);
// 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.
}
currentLen += stringLen;
atStart = FALSE;
}
break;
case URX_CTR_INIT:
case URX_CTR_INIT_NG:
{
// Loop Init Ops. These don't change the min length, but they are 4 word ops
// so location must be updated accordingly.
// Loop Init Ops.
// If the min loop count == 0
// move loc forwards to the end of the loop, skipping over the body.
// If the min count is > 0,
// continue normal processing of the body of the loop.
int32_t loopEndLoc = (int32_t)fRXPat->fCompiledPat->elementAti(loc+1);
loopEndLoc = URX_VAL(loopEndLoc);
int32_t minLoopCount = (int32_t)fRXPat->fCompiledPat->elementAti(loc+2);
if (minLoopCount == 0) {
// Min Loop Count of 0, treat like a forward branch and
// move the current minimum length up to the target
// (end of loop) location.
U_ASSERT(loopEndLoc <= end+1);
if (forwardedLength.elementAti(loopEndLoc) > currentLen) {
forwardedLength.setElementAt(currentLen, loopEndLoc);
}
}
loc+=3; // Skips over operands of CTR_INIT
}
atStart = FALSE;
break;
case URX_CTR_LOOP:
case URX_CTR_LOOP_NG:
// Loop ops.
// The jump is conditional, backwards only.
atStart = FALSE;
break;
case URX_LOOP_C:
// More loop ops. These state-save to themselves.
// don't change the minimum match
atStart = FALSE;
break;