Home | History | Annotate | Download | only in i18n
      1 //
      2 //  file:  regexcmp.cpp
      3 //
      4 //  Copyright (C) 2002-2011 International Business Machines Corporation and others.
      5 //  All Rights Reserved.
      6 //
      7 //  This file contains the ICU regular expression compiler, which is responsible
      8 //  for processing a regular expression pattern into the compiled form that
      9 //  is used by the match finding engine.
     10 //
     11 
     12 #include "unicode/utypes.h"
     13 
     14 #if !UCONFIG_NO_REGULAR_EXPRESSIONS
     15 
     16 #include "unicode/ustring.h"
     17 #include "unicode/unistr.h"
     18 #include "unicode/uniset.h"
     19 #include "unicode/uchar.h"
     20 #include "unicode/uchriter.h"
     21 #include "unicode/parsepos.h"
     22 #include "unicode/parseerr.h"
     23 #include "unicode/regex.h"
     24 #include "patternprops.h"
     25 #include "putilimp.h"
     26 #include "cmemory.h"
     27 #include "cstring.h"
     28 #include "uvectr32.h"
     29 #include "uvectr64.h"
     30 #include "uassert.h"
     31 #include "ucln_in.h"
     32 #include "uinvchar.h"
     33 
     34 #include "regeximp.h"
     35 #include "regexcst.h"   // Contains state table for the regex pattern parser.
     36                         //   generated by a Perl script.
     37 #include "regexcmp.h"
     38 #include "regexst.h"
     39 #include "regextxt.h"
     40 
     41 
     42 
     43 U_NAMESPACE_BEGIN
     44 
     45 
     46 //------------------------------------------------------------------------------
     47 //
     48 //  Constructor.
     49 //
     50 //------------------------------------------------------------------------------
     51 RegexCompile::RegexCompile(RegexPattern *rxp, UErrorCode &status) :
     52    fParenStack(status), fSetStack(status), fSetOpStack(status)
     53 {
     54     // Lazy init of all shared global sets (needed for init()'s empty text)
     55     RegexStaticSets::initGlobals(&status);
     56 
     57     fStatus           = &status;
     58 
     59     fRXPat            = rxp;
     60     fScanIndex        = 0;
     61     fLastChar         = -1;
     62     fPeekChar         = -1;
     63     fLineNum          = 1;
     64     fCharNum          = 0;
     65     fQuoteMode        = FALSE;
     66     fInBackslashQuote = FALSE;
     67     fModeFlags        = fRXPat->fFlags | 0x80000000;
     68     fEOLComments      = TRUE;
     69 
     70     fMatchOpenParen   = -1;
     71     fMatchCloseParen  = -1;
     72     fStringOpStart    = -1;
     73 
     74     if (U_SUCCESS(status) && U_FAILURE(rxp->fDeferredStatus)) {
     75         status = rxp->fDeferredStatus;
     76     }
     77 }
     78 
     79 static const UChar      chAmp       = 0x26;      // '&'
     80 static const UChar      chDash      = 0x2d;      // '-'
     81 
     82 
     83 //------------------------------------------------------------------------------
     84 //
     85 //  Destructor
     86 //
     87 //------------------------------------------------------------------------------
     88 RegexCompile::~RegexCompile() {
     89 }
     90 
     91 static inline void addCategory(UnicodeSet *set, int32_t value, UErrorCode& ec) {
     92     set->addAll(UnicodeSet().applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, value, ec));
     93 }
     94 
     95 //------------------------------------------------------------------------------
     96 //
     97 //  Compile regex pattern.   The state machine for rexexp pattern parsing is here.
     98 //                           The state tables are hand-written in the file regexcst.txt,
     99 //                           and converted to the form used here by a perl
    100 //                           script regexcst.pl
    101 //
    102 //------------------------------------------------------------------------------
    103 void    RegexCompile::compile(
    104                          const UnicodeString &pat,   // Source pat to be compiled.
    105                          UParseError &pp,            // Error position info
    106                          UErrorCode &e)              // Error Code
    107 {
    108 	fRXPat->fPatternString = new UnicodeString(pat);
    109     UText patternText = UTEXT_INITIALIZER;
    110     utext_openConstUnicodeString(&patternText, fRXPat->fPatternString, &e);
    111 
    112     if (U_SUCCESS(e)) {
    113         compile(&patternText, pp, e);
    114         utext_close(&patternText);
    115     }
    116 }
    117 
    118 //
    119 //   compile, UText mode
    120 //     All the work is actually done here.
    121 //
    122 void    RegexCompile::compile(
    123                          UText *pat,                 // Source pat to be compiled.
    124                          UParseError &pp,            // Error position info
    125                          UErrorCode &e)              // Error Code
    126 {
    127     fStatus             = &e;
    128     fParseErr           = &pp;
    129     fStackPtr           = 0;
    130     fStack[fStackPtr]   = 0;
    131 
    132     if (U_FAILURE(*fStatus)) {
    133         return;
    134     }
    135 
    136     // There should be no pattern stuff in the RegexPattern object.  They can not be reused.
    137     U_ASSERT(fRXPat->fPattern == NULL || utext_nativeLength(fRXPat->fPattern) == 0);
    138 
    139     // Prepare the RegexPattern object to receive the compiled pattern.
    140     fRXPat->fPattern        = utext_clone(fRXPat->fPattern, pat, FALSE, TRUE, fStatus);
    141     fRXPat->fStaticSets     = RegexStaticSets::gStaticSets->fPropSets;
    142     fRXPat->fStaticSets8    = RegexStaticSets::gStaticSets->fPropSets8;
    143 
    144 
    145     // Initialize the pattern scanning state machine
    146     fPatternLength = utext_nativeLength(pat);
    147     uint16_t                state = 1;
    148     const RegexTableEl      *tableEl;
    149     nextChar(fC);                        // Fetch the first char from the pattern string.
    150 
    151     //
    152     // Main loop for the regex pattern parsing state machine.
    153     //   Runs once per state transition.
    154     //   Each time through optionally performs, depending on the state table,
    155     //      - an advance to the the next pattern char
    156     //      - an action to be performed.
    157     //      - pushing or popping a state to/from the local state return stack.
    158     //   file regexcst.txt is the source for the state table.  The logic behind
    159     //     recongizing the pattern syntax is there, not here.
    160     //
    161     for (;;) {
    162         //  Bail out if anything has gone wrong.
    163         //  Regex pattern parsing stops on the first error encountered.
    164         if (U_FAILURE(*fStatus)) {
    165             break;
    166         }
    167 
    168         U_ASSERT(state != 0);
    169 
    170         // Find the state table element that matches the input char from the pattern, or the
    171         //    class of the input character.  Start with the first table row for this
    172         //    state, then linearly scan forward until we find a row that matches the
    173         //    character.  The last row for each state always matches all characters, so
    174         //    the search will stop there, if not before.
    175         //
    176         tableEl = &gRuleParseStateTable[state];
    177         REGEX_SCAN_DEBUG_PRINTF(("char, line, col = (\'%c\', %d, %d)    state=%s ",
    178             fC.fChar, fLineNum, fCharNum, RegexStateNames[state]));
    179 
    180         for (;;) {    // loop through table rows belonging to this state, looking for one
    181                       //   that matches the current input char.
    182             REGEX_SCAN_DEBUG_PRINTF(("."));
    183             if (tableEl->fCharClass < 127 && fC.fQuoted == FALSE &&   tableEl->fCharClass == fC.fChar) {
    184                 // Table row specified an individual character, not a set, and
    185                 //   the input character is not quoted, and
    186                 //   the input character matched it.
    187                 break;
    188             }
    189             if (tableEl->fCharClass == 255) {
    190                 // Table row specified default, match anything character class.
    191                 break;
    192             }
    193             if (tableEl->fCharClass == 254 && fC.fQuoted)  {
    194                 // Table row specified "quoted" and the char was quoted.
    195                 break;
    196             }
    197             if (tableEl->fCharClass == 253 && fC.fChar == (UChar32)-1)  {
    198                 // Table row specified eof and we hit eof on the input.
    199                 break;
    200             }
    201 
    202             if (tableEl->fCharClass >= 128 && tableEl->fCharClass < 240 &&   // Table specs a char class &&
    203                 fC.fQuoted == FALSE &&                                       //   char is not escaped &&
    204                 fC.fChar != (UChar32)-1) {                                   //   char is not EOF
    205                 if (RegexStaticSets::gStaticSets->fRuleSets[tableEl->fCharClass-128].contains(fC.fChar)) {
    206                     // Table row specified a character class, or set of characters,
    207                     //   and the current char matches it.
    208                     break;
    209                 }
    210             }
    211 
    212             // No match on this row, advance to the next  row for this state,
    213             tableEl++;
    214         }
    215         REGEX_SCAN_DEBUG_PRINTF(("\n"));
    216 
    217         //
    218         // We've found the row of the state table that matches the current input
    219         //   character from the rules string.
    220         // Perform any action specified  by this row in the state table.
    221         if (doParseActions(tableEl->fAction) == FALSE) {
    222             // Break out of the state machine loop if the
    223             //   the action signalled some kind of error, or
    224             //   the action was to exit, occurs on normal end-of-rules-input.
    225             break;
    226         }
    227 
    228         if (tableEl->fPushState != 0) {
    229             fStackPtr++;
    230             if (fStackPtr >= kStackSize) {
    231                 error(U_REGEX_INTERNAL_ERROR);
    232                 REGEX_SCAN_DEBUG_PRINTF(("RegexCompile::parse() - state stack overflow.\n"));
    233                 fStackPtr--;
    234             }
    235             fStack[fStackPtr] = tableEl->fPushState;
    236         }
    237 
    238         //
    239         //  NextChar.  This is where characters are actually fetched from the pattern.
    240         //             Happens under control of the 'n' tag in the state table.
    241         //
    242         if (tableEl->fNextChar) {
    243             nextChar(fC);
    244         }
    245 
    246         // Get the next state from the table entry, or from the
    247         //   state stack if the next state was specified as "pop".
    248         if (tableEl->fNextState != 255) {
    249             state = tableEl->fNextState;
    250         } else {
    251             state = fStack[fStackPtr];
    252             fStackPtr--;
    253             if (fStackPtr < 0) {
    254                 // state stack underflow
    255                 // This will occur if the user pattern has mis-matched parentheses,
    256                 //   with extra close parens.
    257                 //
    258                 fStackPtr++;
    259                 error(U_REGEX_MISMATCHED_PAREN);
    260             }
    261         }
    262 
    263     }
    264 
    265     if (U_FAILURE(*fStatus)) {
    266         // Bail out if the pattern had errors.
    267         //   Set stack cleanup:  a successful compile would have left it empty,
    268         //   but errors can leave temporary sets hanging around.
    269         while (!fSetStack.empty()) {
    270             delete (UnicodeSet *)fSetStack.pop();
    271         }
    272         return;
    273     }
    274 
    275     //
    276     // The pattern has now been read and processed, and the compiled code generated.
    277     //
    278 
    279     //
    280     // Compute the number of digits requried for the largest capture group number.
    281     //
    282     fRXPat->fMaxCaptureDigits = 1;
    283     int32_t  n = 10;
    284     int32_t  groupCount = fRXPat->fGroupMap->size();
    285     while (n <= groupCount) {
    286         fRXPat->fMaxCaptureDigits++;
    287         n *= 10;
    288     }
    289 
    290     //
    291     // The pattern's fFrameSize so far has accumulated the requirements for
    292     //   storage for capture parentheses, counters, etc. that are encountered
    293     //   in the pattern.  Add space for the two variables that are always
    294     //   present in the saved state:  the input string position (int64_t) and
    295     //   the position in the compiled pattern.
    296     //
    297     fRXPat->fFrameSize+=RESTACKFRAME_HDRCOUNT;
    298 
    299     //
    300     // Optimization pass 1: NOPs, back-references, and case-folding
    301     //
    302     stripNOPs();
    303 
    304     //
    305     // Get bounds for the minimum and maximum length of a string that this
    306     //   pattern can match.  Used to avoid looking for matches in strings that
    307     //   are too short.
    308     //
    309     fRXPat->fMinMatchLen = minMatchLength(3, fRXPat->fCompiledPat->size()-1);
    310 
    311     //
    312     // Optimization pass 2: match start type
    313     //
    314     matchStartType();
    315 
    316     //
    317     // Set up fast latin-1 range sets
    318     //
    319     int32_t numSets = fRXPat->fSets->size();
    320     fRXPat->fSets8 = new Regex8BitSet[numSets];
    321     // Null pointer check.
    322     if (fRXPat->fSets8 == NULL) {
    323         e = *fStatus = U_MEMORY_ALLOCATION_ERROR;
    324         return;
    325     }
    326     int32_t i;
    327     for (i=0; i<numSets; i++) {
    328         UnicodeSet *s = (UnicodeSet *)fRXPat->fSets->elementAt(i);
    329         fRXPat->fSets8[i].init(s);
    330     }
    331 
    332 }
    333 
    334 
    335 
    336 
    337 
    338 //------------------------------------------------------------------------------
    339 //
    340 //  doParseAction        Do some action during regex pattern parsing.
    341 //                       Called by the parse state machine.
    342 //
    343 //                       Generation of the match engine PCode happens here, or
    344 //                       in functions called from the parse actions defined here.
    345 //
    346 //
    347 //------------------------------------------------------------------------------
    348 UBool RegexCompile::doParseActions(int32_t action)
    349 {
    350     UBool   returnVal = TRUE;
    351 
    352     switch ((Regex_PatternParseAction)action) {
    353 
    354     case doPatStart:
    355         // Start of pattern compiles to:
    356         //0   SAVE   2        Fall back to position of FAIL
    357         //1   jmp    3
    358         //2   FAIL            Stop if we ever reach here.
    359         //3   NOP             Dummy, so start of pattern looks the same as
    360         //                    the start of an ( grouping.
    361         //4   NOP             Resreved, will be replaced by a save if there are
    362         //                    OR | operators at the top level
    363         fRXPat->fCompiledPat->addElement(URX_BUILD(URX_STATE_SAVE, 2), *fStatus);
    364         fRXPat->fCompiledPat->addElement(URX_BUILD(URX_JMP,  3), *fStatus);
    365         fRXPat->fCompiledPat->addElement(URX_BUILD(URX_FAIL, 0), *fStatus);
    366 
    367         // Standard open nonCapture paren action emits the two NOPs and
    368         //   sets up the paren stack frame.
    369         doParseActions(doOpenNonCaptureParen);
    370         break;
    371 
    372     case doPatFinish:
    373         // We've scanned to the end of the pattern
    374         //  The end of pattern compiles to:
    375         //        URX_END
    376         //    which will stop the runtime match engine.
    377         //  Encountering end of pattern also behaves like a close paren,
    378         //   and forces fixups of the State Save at the beginning of the compiled pattern
    379         //   and of any OR operations at the top level.
    380         //
    381         handleCloseParen();
    382         if (fParenStack.size() > 0) {
    383             // Missing close paren in pattern.
    384             error(U_REGEX_MISMATCHED_PAREN);
    385         }
    386 
    387         // add the END operation to the compiled pattern.
    388         fRXPat->fCompiledPat->addElement(URX_BUILD(URX_END, 0), *fStatus);
    389 
    390         // Terminate the pattern compilation state machine.
    391         returnVal = FALSE;
    392         break;
    393 
    394 
    395 
    396     case doOrOperator:
    397         // Scanning a '|', as in (A|B)
    398         {
    399             // Insert a SAVE operation at the start of the pattern section preceding
    400             //   this OR at this level.  This SAVE will branch the match forward
    401             //   to the right hand side of the OR in the event that the left hand
    402             //   side fails to match and backtracks.  Locate the position for the
    403             //   save from the location on the top of the parentheses stack.
    404             int32_t savePosition = fParenStack.popi();
    405             int32_t op = (int32_t)fRXPat->fCompiledPat->elementAti(savePosition);
    406             U_ASSERT(URX_TYPE(op) == URX_NOP);  // original contents of reserved location
    407             op = URX_BUILD(URX_STATE_SAVE, fRXPat->fCompiledPat->size()+1);
    408             fRXPat->fCompiledPat->setElementAt(op, savePosition);
    409 
    410             // Append an JMP operation into the compiled pattern.  The operand for
    411             //  the JMP will eventually be the location following the ')' for the
    412             //  group.  This will be patched in later, when the ')' is encountered.
    413             op = URX_BUILD(URX_JMP, 0);
    414             fRXPat->fCompiledPat->addElement(op, *fStatus);
    415 
    416             // Push the position of the newly added JMP op onto the parentheses stack.
    417             // This registers if for fixup when this block's close paren is encountered.
    418             fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus);
    419 
    420             // Append a NOP to the compiled pattern.  This is the slot reserved
    421             //   for a SAVE in the event that there is yet another '|' following
    422             //   this one.
    423             fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
    424             fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus);
    425         }
    426         break;
    427 
    428 
    429     case doOpenCaptureParen:
    430         // Open Paren.
    431         //   Compile to a
    432         //      - NOP, which later may be replaced by a save-state if the
    433         //         parenthesized group gets a * quantifier, followed by
    434         //      - START_CAPTURE  n    where n is stack frame offset to the capture group variables.
    435         //      - NOP, which may later be replaced by a save-state if there
    436         //             is an '|' alternation within the parens.
    437         //
    438         //    Each capture group gets three slots in the save stack frame:
    439         //         0: Capture Group start position (in input string being matched.)
    440         //         1: Capture Group end position.
    441         //         2: Start of Match-in-progress.
    442         //    The first two locations are for a completed capture group, and are
    443         //     referred to by back references and the like.
    444         //    The third location stores the capture start position when an START_CAPTURE is
    445         //      encountered.  This will be promoted to a completed capture when (and if) the corresponding
    446         //      END_CAPTURE is encountered.
    447         {
    448             fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
    449             int32_t  varsLoc    = fRXPat->fFrameSize;    // Reserve three slots in match stack frame.
    450             fRXPat->fFrameSize += 3;
    451             int32_t  cop        = URX_BUILD(URX_START_CAPTURE, varsLoc);
    452             fRXPat->fCompiledPat->addElement(cop, *fStatus);
    453             fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
    454 
    455             // On the Parentheses stack, start a new frame and add the postions
    456             //   of the two NOPs.  Depending on what follows in the pattern, the
    457             //   NOPs may be changed to SAVE_STATE or JMP ops, with a target
    458             //   address of the end of the parenthesized group.
    459             fParenStack.push(fModeFlags, *fStatus);                       // Match mode state
    460             fParenStack.push(capturing, *fStatus);                        // Frame type.
    461             fParenStack.push(fRXPat->fCompiledPat->size()-3, *fStatus);   // The first  NOP location
    462             fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus);   // The second NOP loc
    463 
    464             // Save the mapping from group number to stack frame variable position.
    465             fRXPat->fGroupMap->addElement(varsLoc, *fStatus);
    466         }
    467          break;
    468 
    469     case doOpenNonCaptureParen:
    470         // Open non-caputuring (grouping only) Paren.
    471         //   Compile to a
    472         //      - NOP, which later may be replaced by a save-state if the
    473         //         parenthesized group gets a * quantifier, followed by
    474         //      - NOP, which may later be replaced by a save-state if there
    475         //             is an '|' alternation within the parens.
    476         {
    477             fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
    478             fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
    479 
    480             // On the Parentheses stack, start a new frame and add the postions
    481             //   of the two NOPs.
    482             fParenStack.push(fModeFlags, *fStatus);                       // Match mode state
    483             fParenStack.push(plain,      *fStatus);                       // Begin a new frame.
    484             fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus);   // The first  NOP location
    485             fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus);   // The second NOP loc
    486         }
    487          break;
    488 
    489 
    490     case doOpenAtomicParen:
    491         // Open Atomic Paren.  (?>
    492         //   Compile to a
    493         //      - NOP, which later may be replaced if the parenthesized group
    494         //         has a quantifier, followed by
    495         //      - STO_SP  save state stack position, so it can be restored at the ")"
    496         //      - NOP, which may later be replaced by a save-state if there
    497         //             is an '|' alternation within the parens.
    498         {
    499             fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
    500             int32_t  varLoc    = fRXPat->fDataSize;    // Reserve a data location for saving the
    501             fRXPat->fDataSize += 1;                    //  state stack ptr.
    502             int32_t  stoOp     = URX_BUILD(URX_STO_SP, varLoc);
    503             fRXPat->fCompiledPat->addElement(stoOp, *fStatus);
    504             fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
    505 
    506             // On the Parentheses stack, start a new frame and add the postions
    507             //   of the two NOPs.  Depending on what follows in the pattern, the
    508             //   NOPs may be changed to SAVE_STATE or JMP ops, with a target
    509             //   address of the end of the parenthesized group.
    510             fParenStack.push(fModeFlags, *fStatus);                       // Match mode state
    511             fParenStack.push(atomic, *fStatus);                           // Frame type.
    512             fParenStack.push(fRXPat->fCompiledPat->size()-3, *fStatus);   // The first NOP
    513             fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus);   // The second NOP
    514         }
    515         break;
    516 
    517 
    518     case doOpenLookAhead:
    519         // Positive Look-ahead   (?=  stuff  )
    520         //
    521         //   Note:   Addition of transparent input regions, with the need to
    522         //           restore the original regions when failing out of a lookahead
    523         //           block, complicated this sequence.  Some conbined opcodes
    524         //           might make sense - or might not, lookahead aren't that common.
    525         //
    526         //      Caution:  min match length optimization knows about this
    527         //               sequence; don't change without making updates there too.
    528         //
    529         // Compiles to
    530         //    1    START_LA     dataLoc     Saves SP, Input Pos
    531         //    2.   STATE_SAVE   4            on failure of lookahead, goto 4
    532         //    3    JMP          6           continue ...
    533         //
    534         //    4.   LA_END                   Look Ahead failed.  Restore regions.
    535         //    5.   BACKTRACK                and back track again.
    536         //
    537         //    6.   NOP              reserved for use by quantifiers on the block.
    538         //                          Look-ahead can't have quantifiers, but paren stack
    539         //                             compile time conventions require the slot anyhow.
    540         //    7.   NOP              may be replaced if there is are '|' ops in the block.
    541         //    8.     code for parenthesized stuff.
    542         //    9.   LA_END
    543         //
    544         //  Two data slots are reserved, for saving the stack ptr and the input position.
    545         {
    546             int32_t dataLoc = fRXPat->fDataSize;
    547             fRXPat->fDataSize += 2;
    548             int32_t op = URX_BUILD(URX_LA_START, dataLoc);
    549             fRXPat->fCompiledPat->addElement(op, *fStatus);
    550 
    551             op = URX_BUILD(URX_STATE_SAVE, fRXPat->fCompiledPat->size()+ 2);
    552             fRXPat->fCompiledPat->addElement(op, *fStatus);
    553 
    554             op = URX_BUILD(URX_JMP, fRXPat->fCompiledPat->size()+ 3);
    555             fRXPat->fCompiledPat->addElement(op, *fStatus);
    556 
    557             op = URX_BUILD(URX_LA_END, dataLoc);
    558             fRXPat->fCompiledPat->addElement(op, *fStatus);
    559 
    560             op = URX_BUILD(URX_BACKTRACK, 0);
    561             fRXPat->fCompiledPat->addElement(op, *fStatus);
    562 
    563             op = URX_BUILD(URX_NOP, 0);
    564             fRXPat->fCompiledPat->addElement(op, *fStatus);
    565             fRXPat->fCompiledPat->addElement(op, *fStatus);
    566 
    567             // On the Parentheses stack, start a new frame and add the postions
    568             //   of the NOPs.
    569             fParenStack.push(fModeFlags, *fStatus);                       // Match mode state
    570             fParenStack.push(lookAhead, *fStatus);                        // Frame type.
    571             fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus);   // The first  NOP location
    572             fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus);   // The second NOP location
    573         }
    574         break;
    575 
    576     case doOpenLookAheadNeg:
    577         // Negated Lookahead.   (?! stuff )
    578         // Compiles to
    579         //    1.    START_LA    dataloc
    580         //    2.    SAVE_STATE  7         // Fail within look-ahead block restores to this state,
    581         //                                //   which continues with the match.
    582         //    3.    NOP                   // Std. Open Paren sequence, for possible '|'
    583         //    4.       code for parenthesized stuff.
    584         //    5.    END_LA                // Cut back stack, remove saved state from step 2.
    585         //    6.    BACKTRACK             // code in block succeeded, so neg. lookahead fails.
    586         //    7.    END_LA                // Restore match region, in case look-ahead was using
    587         //                                        an alternate (transparent) region.
    588         {
    589             int32_t dataLoc = fRXPat->fDataSize;
    590             fRXPat->fDataSize += 2;
    591             int32_t op = URX_BUILD(URX_LA_START, dataLoc);
    592             fRXPat->fCompiledPat->addElement(op, *fStatus);
    593 
    594             op = URX_BUILD(URX_STATE_SAVE, 0);    // dest address will be patched later.
    595             fRXPat->fCompiledPat->addElement(op, *fStatus);
    596 
    597             op = URX_BUILD(URX_NOP, 0);
    598             fRXPat->fCompiledPat->addElement(op, *fStatus);
    599 
    600             // On the Parentheses stack, start a new frame and add the postions
    601             //   of the StateSave and NOP.
    602             fParenStack.push(fModeFlags, *fStatus);                       // Match mode state
    603             fParenStack.push(negLookAhead, *fStatus);                    // Frame type
    604             fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus);   // The STATE_SAVE location
    605             fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus);   // The second NOP location
    606 
    607             // Instructions #5 - #7 will be added when the ')' is encountered.
    608         }
    609         break;
    610 
    611     case doOpenLookBehind:
    612         {
    613             //   Compile a (?<= look-behind open paren.
    614             //
    615             //          Compiles to
    616             //              0       URX_LB_START     dataLoc
    617             //              1       URX_LB_CONT      dataLoc
    618             //              2                        MinMatchLen
    619             //              3                        MaxMatchLen
    620             //              4       URX_NOP          Standard '(' boilerplate.
    621             //              5       URX_NOP          Reserved slot for use with '|' ops within (block).
    622             //              6         <code for LookBehind expression>
    623             //              7       URX_LB_END       dataLoc    # Check match len, restore input  len
    624             //              8       URX_LA_END       dataLoc    # Restore stack, input pos
    625             //
    626             //          Allocate a block of matcher data, to contain (when running a match)
    627             //              0:    Stack ptr on entry
    628             //              1:    Input Index on entry
    629             //              2:    Start index of match current match attempt.
    630             //              3:    Original Input String len.
    631 
    632             // Allocate data space
    633             int32_t dataLoc = fRXPat->fDataSize;
    634             fRXPat->fDataSize += 4;
    635 
    636             // Emit URX_LB_START
    637             int32_t op = URX_BUILD(URX_LB_START, dataLoc);
    638             fRXPat->fCompiledPat->addElement(op, *fStatus);
    639 
    640             // Emit URX_LB_CONT
    641             op = URX_BUILD(URX_LB_CONT, dataLoc);
    642             fRXPat->fCompiledPat->addElement(op, *fStatus);
    643             fRXPat->fCompiledPat->addElement(0,  *fStatus);    // MinMatchLength.  To be filled later.
    644             fRXPat->fCompiledPat->addElement(0,  *fStatus);    // MaxMatchLength.  To be filled later.
    645 
    646             // Emit the NOP
    647             op = URX_BUILD(URX_NOP, 0);
    648             fRXPat->fCompiledPat->addElement(op, *fStatus);
    649             fRXPat->fCompiledPat->addElement(op, *fStatus);
    650 
    651             // On the Parentheses stack, start a new frame and add the postions
    652             //   of the URX_LB_CONT and the NOP.
    653             fParenStack.push(fModeFlags, *fStatus);                       // Match mode state
    654             fParenStack.push(lookBehind, *fStatus);                       // Frame type
    655             fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus);   // The first NOP location
    656             fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus);   // The 2nd   NOP location
    657 
    658             // The final two instructions will be added when the ')' is encountered.
    659         }
    660 
    661         break;
    662 
    663     case doOpenLookBehindNeg:
    664         {
    665             //   Compile a (?<! negated look-behind open paren.
    666             //
    667             //          Compiles to
    668             //              0       URX_LB_START     dataLoc    # Save entry stack, input len
    669             //              1       URX_LBN_CONT     dataLoc    # Iterate possible match positions
    670             //              2                        MinMatchLen
    671             //              3                        MaxMatchLen
    672             //              4                        continueLoc (9)
    673             //              5       URX_NOP          Standard '(' boilerplate.
    674             //              6       URX_NOP          Reserved slot for use with '|' ops within (block).
    675             //              7         <code for LookBehind expression>
    676             //              8       URX_LBN_END      dataLoc    # Check match len, cause a FAIL
    677             //              9       ...
    678             //
    679             //          Allocate a block of matcher data, to contain (when running a match)
    680             //              0:    Stack ptr on entry
    681             //              1:    Input Index on entry
    682             //              2:    Start index of match current match attempt.
    683             //              3:    Original Input String len.
    684 
    685             // Allocate data space
    686             int32_t dataLoc = fRXPat->fDataSize;
    687             fRXPat->fDataSize += 4;
    688 
    689             // Emit URX_LB_START
    690             int32_t op = URX_BUILD(URX_LB_START, dataLoc);
    691             fRXPat->fCompiledPat->addElement(op, *fStatus);
    692 
    693             // Emit URX_LBN_CONT
    694             op = URX_BUILD(URX_LBN_CONT, dataLoc);
    695             fRXPat->fCompiledPat->addElement(op, *fStatus);
    696             fRXPat->fCompiledPat->addElement(0,  *fStatus);    // MinMatchLength.  To be filled later.
    697             fRXPat->fCompiledPat->addElement(0,  *fStatus);    // MaxMatchLength.  To be filled later.
    698             fRXPat->fCompiledPat->addElement(0,  *fStatus);    // Continue Loc.    To be filled later.
    699 
    700             // Emit the NOP
    701             op = URX_BUILD(URX_NOP, 0);
    702             fRXPat->fCompiledPat->addElement(op, *fStatus);
    703             fRXPat->fCompiledPat->addElement(op, *fStatus);
    704 
    705             // On the Parentheses stack, start a new frame and add the postions
    706             //   of the URX_LB_CONT and the NOP.
    707             fParenStack.push(fModeFlags, *fStatus);                       // Match mode state
    708             fParenStack.push(lookBehindN, *fStatus);                      // Frame type
    709             fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus);   // The first NOP location
    710             fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus);   // The 2nd   NOP location
    711 
    712             // The final two instructions will be added when the ')' is encountered.
    713         }
    714         break;
    715 
    716     case doConditionalExpr:
    717         // Conditionals such as (?(1)a:b)
    718     case doPerlInline:
    719         // Perl inline-condtionals.  (?{perl code}a|b) We're not perl, no way to do them.
    720         error(U_REGEX_UNIMPLEMENTED);
    721         break;
    722 
    723 
    724     case doCloseParen:
    725         handleCloseParen();
    726         if (fParenStack.size() <= 0) {
    727             //  Extra close paren, or missing open paren.
    728             error(U_REGEX_MISMATCHED_PAREN);
    729         }
    730         break;
    731 
    732     case doNOP:
    733         break;
    734 
    735 
    736     case doBadOpenParenType:
    737     case doRuleError:
    738         error(U_REGEX_RULE_SYNTAX);
    739         break;
    740 
    741 
    742     case doMismatchedParenErr:
    743         error(U_REGEX_MISMATCHED_PAREN);
    744         break;
    745 
    746     case doPlus:
    747         //  Normal '+'  compiles to
    748         //     1.   stuff to be repeated  (already built)
    749         //     2.   jmp-sav 1
    750         //     3.   ...
    751         //
    752         //  Or, if the item to be repeated can match a zero length string,
    753         //     1.   STO_INP_LOC  data-loc
    754         //     2.      body of stuff to be repeated
    755         //     3.   JMP_SAV_X    2
    756         //     4.   ...
    757 
    758         //
    759         //  Or, if the item to be repeated is simple
    760         //     1.   Item to be repeated.
    761         //     2.   LOOP_SR_I    set number  (assuming repeated item is a set ref)
    762         //     3.   LOOP_C       stack location
    763         {
    764             int32_t  topLoc = blockTopLoc(FALSE);        // location of item #1
    765             int32_t  frameLoc;
    766 
    767             // Check for simple constructs, which may get special optimized code.
    768             if (topLoc == fRXPat->fCompiledPat->size() - 1) {
    769                 int32_t repeatedOp = (int32_t)fRXPat->fCompiledPat->elementAti(topLoc);
    770 
    771                 if (URX_TYPE(repeatedOp) == URX_SETREF) {
    772                     // Emit optimized code for [char set]+
    773                     int32_t loopOpI = URX_BUILD(URX_LOOP_SR_I, URX_VAL(repeatedOp));
    774                     fRXPat->fCompiledPat->addElement(loopOpI, *fStatus);
    775                     frameLoc = fRXPat->fFrameSize;
    776                     fRXPat->fFrameSize++;
    777                     int32_t loopOpC = URX_BUILD(URX_LOOP_C, frameLoc);
    778                     fRXPat->fCompiledPat->addElement(loopOpC, *fStatus);
    779                     break;
    780                 }
    781 
    782                 if (URX_TYPE(repeatedOp) == URX_DOTANY ||
    783                     URX_TYPE(repeatedOp) == URX_DOTANY_ALL ||
    784                     URX_TYPE(repeatedOp) == URX_DOTANY_UNIX) {
    785                     // Emit Optimized code for .+ operations.
    786                     int32_t loopOpI = URX_BUILD(URX_LOOP_DOT_I, 0);
    787                     if (URX_TYPE(repeatedOp) == URX_DOTANY_ALL) {
    788                         // URX_LOOP_DOT_I operand is a flag indicating ". matches any" mode.
    789                         loopOpI |= 1;
    790                     }
    791                     if (fModeFlags & UREGEX_UNIX_LINES) {
    792                         loopOpI |= 2;
    793                     }
    794                     fRXPat->fCompiledPat->addElement(loopOpI, *fStatus);
    795                     frameLoc = fRXPat->fFrameSize;
    796                     fRXPat->fFrameSize++;
    797                     int32_t loopOpC = URX_BUILD(URX_LOOP_C, frameLoc);
    798                     fRXPat->fCompiledPat->addElement(loopOpC, *fStatus);
    799                     break;
    800                 }
    801 
    802             }
    803 
    804             // General case.
    805 
    806             // Check for minimum match length of zero, which requires
    807             //    extra loop-breaking code.
    808             if (minMatchLength(topLoc, fRXPat->fCompiledPat->size()-1) == 0) {
    809                 // Zero length match is possible.
    810                 // Emit the code sequence that can handle it.
    811                 insertOp(topLoc);
    812                 frameLoc =  fRXPat->fFrameSize;
    813                 fRXPat->fFrameSize++;
    814 
    815                 int32_t op = URX_BUILD(URX_STO_INP_LOC, frameLoc);
    816                 fRXPat->fCompiledPat->setElementAt(op, topLoc);
    817 
    818                 op = URX_BUILD(URX_JMP_SAV_X, topLoc+1);
    819                 fRXPat->fCompiledPat->addElement(op, *fStatus);
    820             } else {
    821                 // Simpler code when the repeated body must match something non-empty
    822                 int32_t  jmpOp  = URX_BUILD(URX_JMP_SAV, topLoc);
    823                 fRXPat->fCompiledPat->addElement(jmpOp, *fStatus);
    824             }
    825         }
    826         break;
    827 
    828     case doNGPlus:
    829         //  Non-greedy '+?'  compiles to
    830         //     1.   stuff to be repeated  (already built)
    831         //     2.   state-save  1
    832         //     3.   ...
    833         {
    834             int32_t topLoc      = blockTopLoc(FALSE);
    835             int32_t saveStateOp = URX_BUILD(URX_STATE_SAVE, topLoc);
    836             fRXPat->fCompiledPat->addElement(saveStateOp, *fStatus);
    837         }
    838         break;
    839 
    840 
    841     case doOpt:
    842         // Normal (greedy) ? quantifier.
    843         //  Compiles to
    844         //     1. state save 3
    845         //     2.    body of optional block
    846         //     3. ...
    847         // Insert the state save into the compiled pattern, and we're done.
    848         {
    849             int32_t   saveStateLoc = blockTopLoc(TRUE);
    850             int32_t   saveStateOp  = URX_BUILD(URX_STATE_SAVE, fRXPat->fCompiledPat->size());
    851             fRXPat->fCompiledPat->setElementAt(saveStateOp, saveStateLoc);
    852         }
    853         break;
    854 
    855     case doNGOpt:
    856         // Non-greedy ?? quantifier
    857         //   compiles to
    858         //    1.  jmp   4
    859         //    2.     body of optional block
    860         //    3   jmp   5
    861         //    4.  state save 2
    862         //    5    ...
    863         //  This code is less than ideal, with two jmps instead of one, because we can only
    864         //  insert one instruction at the top of the block being iterated.
    865         {
    866             int32_t  jmp1_loc = blockTopLoc(TRUE);
    867             int32_t  jmp2_loc = fRXPat->fCompiledPat->size();
    868 
    869             int32_t  jmp1_op  = URX_BUILD(URX_JMP, jmp2_loc+1);
    870             fRXPat->fCompiledPat->setElementAt(jmp1_op, jmp1_loc);
    871 
    872             int32_t  jmp2_op  = URX_BUILD(URX_JMP, jmp2_loc+2);
    873             fRXPat->fCompiledPat->addElement(jmp2_op, *fStatus);
    874 
    875             int32_t  save_op  = URX_BUILD(URX_STATE_SAVE, jmp1_loc+1);
    876             fRXPat->fCompiledPat->addElement(save_op, *fStatus);
    877         }
    878         break;
    879 
    880 
    881     case doStar:
    882         // Normal (greedy) * quantifier.
    883         // Compiles to
    884         //       1.   STATE_SAVE   4
    885         //       2.      body of stuff being iterated over
    886         //       3.   JMP_SAV      2
    887         //       4.   ...
    888         //
    889         // Or, if the body is a simple [Set],
    890         //       1.   LOOP_SR_I    set number
    891         //       2.   LOOP_C       stack location
    892         //       ...
    893         //
    894         // Or if this is a .*
    895         //       1.   LOOP_DOT_I    (. matches all mode flag)
    896         //       2.   LOOP_C        stack location
    897         //
    898         // Or, if the body can match a zero-length string, to inhibit infinite loops,
    899         //       1.   STATE_SAVE   5
    900         //       2.   STO_INP_LOC  data-loc
    901         //       3.      body of stuff
    902         //       4.   JMP_SAV_X    2
    903         //       5.   ...
    904         {
    905             // location of item #1, the STATE_SAVE
    906             int32_t   topLoc = blockTopLoc(FALSE);
    907             int32_t   dataLoc = -1;
    908 
    909             // Check for simple *, where the construct being repeated
    910             //   compiled to single opcode, and might be optimizable.
    911             if (topLoc == fRXPat->fCompiledPat->size() - 1) {
    912                 int32_t repeatedOp = (int32_t)fRXPat->fCompiledPat->elementAti(topLoc);
    913 
    914                 if (URX_TYPE(repeatedOp) == URX_SETREF) {
    915                     // Emit optimized code for a [char set]*
    916                     int32_t loopOpI = URX_BUILD(URX_LOOP_SR_I, URX_VAL(repeatedOp));
    917                     fRXPat->fCompiledPat->setElementAt(loopOpI, topLoc);
    918                     dataLoc = fRXPat->fFrameSize;
    919                     fRXPat->fFrameSize++;
    920                     int32_t loopOpC = URX_BUILD(URX_LOOP_C, dataLoc);
    921                     fRXPat->fCompiledPat->addElement(loopOpC, *fStatus);
    922                     break;
    923                 }
    924 
    925                 if (URX_TYPE(repeatedOp) == URX_DOTANY ||
    926                     URX_TYPE(repeatedOp) == URX_DOTANY_ALL ||
    927                     URX_TYPE(repeatedOp) == URX_DOTANY_UNIX) {
    928                     // Emit Optimized code for .* operations.
    929                     int32_t loopOpI = URX_BUILD(URX_LOOP_DOT_I, 0);
    930                     if (URX_TYPE(repeatedOp) == URX_DOTANY_ALL) {
    931                         // URX_LOOP_DOT_I operand is a flag indicating . matches any mode.
    932                         loopOpI |= 1;
    933                     }
    934                     if ((fModeFlags & UREGEX_UNIX_LINES) != 0) {
    935                         loopOpI |= 2;
    936                     }
    937                     fRXPat->fCompiledPat->setElementAt(loopOpI, topLoc);
    938                     dataLoc = fRXPat->fFrameSize;
    939                     fRXPat->fFrameSize++;
    940                     int32_t loopOpC = URX_BUILD(URX_LOOP_C, dataLoc);
    941                     fRXPat->fCompiledPat->addElement(loopOpC, *fStatus);
    942                     break;
    943                 }
    944             }
    945 
    946             // Emit general case code for this *
    947             // The optimizations did not apply.
    948 
    949             int32_t   saveStateLoc = blockTopLoc(TRUE);
    950             int32_t   jmpOp        = URX_BUILD(URX_JMP_SAV, saveStateLoc+1);
    951 
    952             // Check for minimum match length of zero, which requires
    953             //    extra loop-breaking code.
    954             if (minMatchLength(saveStateLoc, fRXPat->fCompiledPat->size()-1) == 0) {
    955                 insertOp(saveStateLoc);
    956                 dataLoc =  fRXPat->fFrameSize;
    957                 fRXPat->fFrameSize++;
    958 
    959                 int32_t op = URX_BUILD(URX_STO_INP_LOC, dataLoc);
    960                 fRXPat->fCompiledPat->setElementAt(op, saveStateLoc+1);
    961                 jmpOp      = URX_BUILD(URX_JMP_SAV_X, saveStateLoc+2);
    962             }
    963 
    964             // Locate the position in the compiled pattern where the match will continue
    965             //   after completing the *.   (4 or 5 in the comment above)
    966             int32_t continueLoc = fRXPat->fCompiledPat->size()+1;
    967 
    968             // Put together the save state op store it into the compiled code.
    969             int32_t saveStateOp = URX_BUILD(URX_STATE_SAVE, continueLoc);
    970             fRXPat->fCompiledPat->setElementAt(saveStateOp, saveStateLoc);
    971 
    972             // Append the URX_JMP_SAV or URX_JMPX operation to the compiled pattern.
    973             fRXPat->fCompiledPat->addElement(jmpOp, *fStatus);
    974         }
    975         break;
    976 
    977     case doNGStar:
    978         // Non-greedy *? quantifier
    979         // compiles to
    980         //     1.   JMP    3
    981         //     2.      body of stuff being iterated over
    982         //     3.   STATE_SAVE  2
    983         //     4    ...
    984         {
    985             int32_t     jmpLoc  = blockTopLoc(TRUE);                   // loc  1.
    986             int32_t     saveLoc = fRXPat->fCompiledPat->size();        // loc  3.
    987             int32_t     jmpOp   = URX_BUILD(URX_JMP, saveLoc);
    988             int32_t     stateSaveOp = URX_BUILD(URX_STATE_SAVE, jmpLoc+1);
    989             fRXPat->fCompiledPat->setElementAt(jmpOp, jmpLoc);
    990             fRXPat->fCompiledPat->addElement(stateSaveOp, *fStatus);
    991         }
    992         break;
    993 
    994 
    995     case doIntervalInit:
    996         // The '{' opening an interval quantifier was just scanned.
    997         // Init the counter varaiables that will accumulate the values as the digits
    998         //    are scanned.
    999         fIntervalLow = 0;
   1000         fIntervalUpper = -1;
   1001         break;
   1002 
   1003     case doIntevalLowerDigit:
   1004         // Scanned a digit from the lower value of an {lower,upper} interval
   1005         {
   1006             int32_t digitValue = u_charDigitValue(fC.fChar);
   1007             U_ASSERT(digitValue >= 0);
   1008             fIntervalLow = fIntervalLow*10 + digitValue;
   1009             if (fIntervalLow < 0) {
   1010                 error(U_REGEX_NUMBER_TOO_BIG);
   1011             }
   1012         }
   1013         break;
   1014 
   1015     case doIntervalUpperDigit:
   1016         // Scanned a digit from the upper value of an {lower,upper} interval
   1017         {
   1018             if (fIntervalUpper < 0) {
   1019                 fIntervalUpper = 0;
   1020             }
   1021             int32_t digitValue = u_charDigitValue(fC.fChar);
   1022             U_ASSERT(digitValue >= 0);
   1023             fIntervalUpper = fIntervalUpper*10 + digitValue;
   1024             if (fIntervalUpper < 0) {
   1025                 error(U_REGEX_NUMBER_TOO_BIG);
   1026             }
   1027         }
   1028         break;
   1029 
   1030     case doIntervalSame:
   1031         // Scanned a single value interval like {27}.  Upper = Lower.
   1032         fIntervalUpper = fIntervalLow;
   1033         break;
   1034 
   1035     case doInterval:
   1036         // Finished scanning a normal {lower,upper} interval.  Generate the code for it.
   1037         if (compileInlineInterval() == FALSE) {
   1038             compileInterval(URX_CTR_INIT, URX_CTR_LOOP);
   1039         }
   1040         break;
   1041 
   1042     case doPossessiveInterval:
   1043         // Finished scanning a Possessive {lower,upper}+ interval.  Generate the code for it.
   1044         {
   1045             // Remember the loc for the top of the block being looped over.
   1046             //   (Can not reserve a slot in the compiled pattern at this time, because
   1047             //    compileInterval needs to reserve also, and blockTopLoc can only reserve
   1048             //    once per block.)
   1049             int32_t topLoc = blockTopLoc(FALSE);
   1050 
   1051             // Produce normal looping code.
   1052             compileInterval(URX_CTR_INIT, URX_CTR_LOOP);
   1053 
   1054             // Surround the just-emitted normal looping code with a STO_SP ... LD_SP
   1055             //  just as if the loop was inclosed in atomic parentheses.
   1056 
   1057             // First the STO_SP before the start of the loop
   1058             insertOp(topLoc);
   1059             int32_t  varLoc    = fRXPat->fDataSize;    // Reserve a data location for saving the
   1060             fRXPat->fDataSize += 1;                    //  state stack ptr.
   1061             int32_t  op        = URX_BUILD(URX_STO_SP, varLoc);
   1062             fRXPat->fCompiledPat->setElementAt(op, topLoc);
   1063 
   1064             int32_t loopOp = (int32_t)fRXPat->fCompiledPat->popi();
   1065             U_ASSERT(URX_TYPE(loopOp) == URX_CTR_LOOP && URX_VAL(loopOp) == topLoc);
   1066             loopOp++;     // point LoopOp after the just-inserted STO_SP
   1067             fRXPat->fCompiledPat->push(loopOp, *fStatus);
   1068 
   1069             // Then the LD_SP after the end of the loop
   1070             op = URX_BUILD(URX_LD_SP, varLoc);
   1071             fRXPat->fCompiledPat->addElement(op, *fStatus);
   1072         }
   1073 
   1074         break;
   1075 
   1076     case doNGInterval:
   1077         // Finished scanning a non-greedy {lower,upper}? interval.  Generate the code for it.
   1078         compileInterval(URX_CTR_INIT_NG, URX_CTR_LOOP_NG);
   1079         break;
   1080 
   1081     case doIntervalError:
   1082         error(U_REGEX_BAD_INTERVAL);
   1083         break;
   1084 
   1085     case doLiteralChar:
   1086         // We've just scanned a "normal" character from the pattern,
   1087         literalChar(fC.fChar);
   1088         break;
   1089 
   1090 
   1091     case doEscapedLiteralChar:
   1092         // We've just scanned an backslashed escaped character with  no
   1093         //   special meaning.  It represents itself.
   1094         if ((fModeFlags & UREGEX_ERROR_ON_UNKNOWN_ESCAPES) != 0 &&
   1095             ((fC.fChar >= 0x41 && fC.fChar<= 0x5A) ||     // in [A-Z]
   1096             (fC.fChar >= 0x61 && fC.fChar <= 0x7a))) {   // in [a-z]
   1097                error(U_REGEX_BAD_ESCAPE_SEQUENCE);
   1098              }
   1099         literalChar(fC.fChar);
   1100         break;
   1101 
   1102 
   1103     case doDotAny:
   1104         // scanned a ".",  match any single character.
   1105         {
   1106             int32_t   op;
   1107             if (fModeFlags & UREGEX_DOTALL) {
   1108                 op = URX_BUILD(URX_DOTANY_ALL, 0);
   1109             } else if (fModeFlags & UREGEX_UNIX_LINES) {
   1110                 op = URX_BUILD(URX_DOTANY_UNIX, 0);
   1111             } else {
   1112                 op = URX_BUILD(URX_DOTANY, 0);
   1113             }
   1114             fRXPat->fCompiledPat->addElement(op, *fStatus);
   1115         }
   1116         break;
   1117 
   1118     case doCaret:
   1119         {
   1120             int32_t op = 0;
   1121             if (       (fModeFlags & UREGEX_MULTILINE) == 0 && (fModeFlags & UREGEX_UNIX_LINES) == 0) {
   1122                 op = URX_CARET;
   1123             } else if ((fModeFlags & UREGEX_MULTILINE) != 0 && (fModeFlags & UREGEX_UNIX_LINES) == 0) {
   1124                 op = URX_CARET_M;
   1125             } else if ((fModeFlags & UREGEX_MULTILINE) == 0 && (fModeFlags & UREGEX_UNIX_LINES) != 0) {
   1126                 op = URX_CARET;   // Only testing true start of input.
   1127             } else if ((fModeFlags & UREGEX_MULTILINE) != 0 && (fModeFlags & UREGEX_UNIX_LINES) != 0) {
   1128                 op = URX_CARET_M_UNIX;
   1129             }
   1130             fRXPat->fCompiledPat->addElement(URX_BUILD(op, 0), *fStatus);
   1131         }
   1132         break;
   1133 
   1134     case doDollar:
   1135         {
   1136             int32_t op = 0;
   1137             if (       (fModeFlags & UREGEX_MULTILINE) == 0 && (fModeFlags & UREGEX_UNIX_LINES) == 0) {
   1138                 op = URX_DOLLAR;
   1139             } else if ((fModeFlags & UREGEX_MULTILINE) != 0 && (fModeFlags & UREGEX_UNIX_LINES) == 0) {
   1140                 op = URX_DOLLAR_M;
   1141             } else if ((fModeFlags & UREGEX_MULTILINE) == 0 && (fModeFlags & UREGEX_UNIX_LINES) != 0) {
   1142                 op = URX_DOLLAR_D;
   1143             } else if ((fModeFlags & UREGEX_MULTILINE) != 0 && (fModeFlags & UREGEX_UNIX_LINES) != 0) {
   1144                 op = URX_DOLLAR_MD;
   1145             }
   1146             fRXPat->fCompiledPat->addElement(URX_BUILD(op, 0), *fStatus);
   1147         }
   1148         break;
   1149 
   1150     case doBackslashA:
   1151         fRXPat->fCompiledPat->addElement(URX_BUILD(URX_CARET, 0), *fStatus);
   1152         break;
   1153 
   1154     case doBackslashB:
   1155         {
   1156             #if  UCONFIG_NO_BREAK_ITERATION==1
   1157             if (fModeFlags & UREGEX_UWORD) {
   1158                 error(U_UNSUPPORTED_ERROR);
   1159             }
   1160             #endif
   1161             int32_t op = (fModeFlags & UREGEX_UWORD)? URX_BACKSLASH_BU : URX_BACKSLASH_B;
   1162             fRXPat->fCompiledPat->addElement(URX_BUILD(op, 1), *fStatus);
   1163         }
   1164         break;
   1165 
   1166     case doBackslashb:
   1167         {
   1168             #if  UCONFIG_NO_BREAK_ITERATION==1
   1169             if (fModeFlags & UREGEX_UWORD) {
   1170                 error(U_UNSUPPORTED_ERROR);
   1171             }
   1172             #endif
   1173             int32_t op = (fModeFlags & UREGEX_UWORD)? URX_BACKSLASH_BU : URX_BACKSLASH_B;
   1174             fRXPat->fCompiledPat->addElement(URX_BUILD(op, 0), *fStatus);
   1175         }
   1176         break;
   1177 
   1178     case doBackslashD:
   1179         fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_D, 1), *fStatus);
   1180         break;
   1181 
   1182     case doBackslashd:
   1183         fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_D, 0), *fStatus);
   1184         break;
   1185 
   1186     case doBackslashG:
   1187         fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_G, 0), *fStatus);
   1188         break;
   1189 
   1190     case doBackslashS:
   1191         fRXPat->fCompiledPat->addElement(
   1192             URX_BUILD(URX_STAT_SETREF_N, URX_ISSPACE_SET), *fStatus);
   1193         break;
   1194 
   1195     case doBackslashs:
   1196         fRXPat->fCompiledPat->addElement(
   1197             URX_BUILD(URX_STATIC_SETREF, URX_ISSPACE_SET), *fStatus);
   1198         break;
   1199 
   1200     case doBackslashW:
   1201         fRXPat->fCompiledPat->addElement(
   1202             URX_BUILD(URX_STAT_SETREF_N, URX_ISWORD_SET), *fStatus);
   1203         break;
   1204 
   1205     case doBackslashw:
   1206         fRXPat->fCompiledPat->addElement(
   1207             URX_BUILD(URX_STATIC_SETREF, URX_ISWORD_SET), *fStatus);
   1208         break;
   1209 
   1210     case doBackslashX:
   1211         fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_X, 0), *fStatus);
   1212         break;
   1213 
   1214 
   1215     case doBackslashZ:
   1216         fRXPat->fCompiledPat->addElement(URX_BUILD(URX_DOLLAR, 0), *fStatus);
   1217         break;
   1218 
   1219     case doBackslashz:
   1220         fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKSLASH_Z, 0), *fStatus);
   1221         break;
   1222 
   1223     case doEscapeError:
   1224         error(U_REGEX_BAD_ESCAPE_SEQUENCE);
   1225         break;
   1226 
   1227     case doExit:
   1228         returnVal = FALSE;
   1229         break;
   1230 
   1231     case doProperty:
   1232         {
   1233             UnicodeSet *theSet = scanProp();
   1234             compileSet(theSet);
   1235         }
   1236         break;
   1237 
   1238     case doNamedChar:
   1239         {
   1240             UChar32 c = scanNamedChar();
   1241             literalChar(c);
   1242         }
   1243         break;
   1244 
   1245 
   1246     case doBackRef:
   1247         // BackReference.  Somewhat unusual in that the front-end can not completely parse
   1248         //                 the regular expression, because the number of digits to be consumed
   1249         //                 depends on the number of capture groups that have been defined.  So
   1250         //                 we have to do it here instead.
   1251         {
   1252             int32_t  numCaptureGroups = fRXPat->fGroupMap->size();
   1253             int32_t  groupNum = 0;
   1254             UChar32  c        = fC.fChar;
   1255 
   1256             for (;;) {
   1257                 // Loop once per digit, for max allowed number of digits in a back reference.
   1258                 int32_t digit = u_charDigitValue(c);
   1259                 groupNum = groupNum * 10 + digit;
   1260                 if (groupNum >= numCaptureGroups) {
   1261                     break;
   1262                 }
   1263                 c = peekCharLL();
   1264                 if (RegexStaticSets::gStaticSets->fRuleDigitsAlias->contains(c) == FALSE) {
   1265                     break;
   1266                 }
   1267                 nextCharLL();
   1268             }
   1269 
   1270             // Scan of the back reference in the source regexp is complete.  Now generate
   1271             //  the compiled code for it.
   1272             // Because capture groups can be forward-referenced by back-references,
   1273             //  we fill the operand with the capture group number.  At the end
   1274             //  of compilation, it will be changed to the variable's location.
   1275             U_ASSERT(groupNum > 0);
   1276             int32_t  op;
   1277             if (fModeFlags & UREGEX_CASE_INSENSITIVE) {
   1278                 op = URX_BUILD(URX_BACKREF_I, groupNum);
   1279             } else {
   1280                 op = URX_BUILD(URX_BACKREF, groupNum);
   1281             }
   1282             fRXPat->fCompiledPat->addElement(op, *fStatus);
   1283         }
   1284         break;
   1285 
   1286 
   1287     case doPossessivePlus:
   1288         // Possessive ++ quantifier.
   1289         // Compiles to
   1290         //       1.   STO_SP
   1291         //       2.      body of stuff being iterated over
   1292         //       3.   STATE_SAVE 5
   1293         //       4.   JMP        2
   1294         //       5.   LD_SP
   1295         //       6.   ...
   1296         //
   1297         //  Note:  TODO:  This is pretty inefficient.  A mass of saved state is built up
   1298         //                then unconditionally discarded.  Perhaps introduce a new opcode.  Ticket 6056
   1299         //
   1300         {
   1301             // Emit the STO_SP
   1302             int32_t   topLoc = blockTopLoc(TRUE);
   1303             int32_t   stoLoc = fRXPat->fDataSize;
   1304             fRXPat->fDataSize++;       // Reserve the data location for storing save stack ptr.
   1305             int32_t   op     = URX_BUILD(URX_STO_SP, stoLoc);
   1306             fRXPat->fCompiledPat->setElementAt(op, topLoc);
   1307 
   1308             // Emit the STATE_SAVE
   1309             op = URX_BUILD(URX_STATE_SAVE, fRXPat->fCompiledPat->size()+2);
   1310             fRXPat->fCompiledPat->addElement(op, *fStatus);
   1311 
   1312             // Emit the JMP
   1313             op = URX_BUILD(URX_JMP, topLoc+1);
   1314             fRXPat->fCompiledPat->addElement(op, *fStatus);
   1315 
   1316             // Emit the LD_SP
   1317             op = URX_BUILD(URX_LD_SP, stoLoc);
   1318             fRXPat->fCompiledPat->addElement(op, *fStatus);
   1319         }
   1320         break;
   1321 
   1322     case doPossessiveStar:
   1323         // Possessive *+ quantifier.
   1324         // Compiles to
   1325         //       1.   STO_SP       loc
   1326         //       2.   STATE_SAVE   5
   1327         //       3.      body of stuff being iterated over
   1328         //       4.   JMP          2
   1329         //       5.   LD_SP        loc
   1330         //       6    ...
   1331         // TODO:  do something to cut back the state stack each time through the loop.
   1332         {
   1333             // Reserve two slots at the top of the block.
   1334             int32_t   topLoc = blockTopLoc(TRUE);
   1335             insertOp(topLoc);
   1336 
   1337             // emit   STO_SP     loc
   1338             int32_t   stoLoc = fRXPat->fDataSize;
   1339             fRXPat->fDataSize++;       // Reserve the data location for storing save stack ptr.
   1340             int32_t   op     = URX_BUILD(URX_STO_SP, stoLoc);
   1341             fRXPat->fCompiledPat->setElementAt(op, topLoc);
   1342 
   1343             // Emit the SAVE_STATE   5
   1344             int32_t L7 = fRXPat->fCompiledPat->size()+1;
   1345             op = URX_BUILD(URX_STATE_SAVE, L7);
   1346             fRXPat->fCompiledPat->setElementAt(op, topLoc+1);
   1347 
   1348             // Append the JMP operation.
   1349             op = URX_BUILD(URX_JMP, topLoc+1);
   1350             fRXPat->fCompiledPat->addElement(op, *fStatus);
   1351 
   1352             // Emit the LD_SP       loc
   1353             op = URX_BUILD(URX_LD_SP, stoLoc);
   1354             fRXPat->fCompiledPat->addElement(op, *fStatus);
   1355         }
   1356         break;
   1357 
   1358     case doPossessiveOpt:
   1359         // Possessive  ?+ quantifier.
   1360         //  Compiles to
   1361         //     1. STO_SP      loc
   1362         //     2. SAVE_STATE  5
   1363         //     3.    body of optional block
   1364         //     4. LD_SP       loc
   1365         //     5. ...
   1366         //
   1367         {
   1368             // Reserve two slots at the top of the block.
   1369             int32_t   topLoc = blockTopLoc(TRUE);
   1370             insertOp(topLoc);
   1371 
   1372             // Emit the STO_SP
   1373             int32_t   stoLoc = fRXPat->fDataSize;
   1374             fRXPat->fDataSize++;       // Reserve the data location for storing save stack ptr.
   1375             int32_t   op     = URX_BUILD(URX_STO_SP, stoLoc);
   1376             fRXPat->fCompiledPat->setElementAt(op, topLoc);
   1377 
   1378             // Emit the SAVE_STATE
   1379             int32_t   continueLoc = fRXPat->fCompiledPat->size()+1;
   1380             op = URX_BUILD(URX_STATE_SAVE, continueLoc);
   1381             fRXPat->fCompiledPat->setElementAt(op, topLoc+1);
   1382 
   1383             // Emit the LD_SP
   1384             op = URX_BUILD(URX_LD_SP, stoLoc);
   1385             fRXPat->fCompiledPat->addElement(op, *fStatus);
   1386         }
   1387         break;
   1388 
   1389 
   1390     case doBeginMatchMode:
   1391         fNewModeFlags = fModeFlags;
   1392         fSetModeFlag  = TRUE;
   1393         break;
   1394 
   1395     case doMatchMode:   //  (?i)    and similar
   1396         {
   1397             int32_t  bit = 0;
   1398             switch (fC.fChar) {
   1399             case 0x69: /* 'i' */   bit = UREGEX_CASE_INSENSITIVE; break;
   1400             case 0x64: /* 'd' */   bit = UREGEX_UNIX_LINES;       break;
   1401             case 0x6d: /* 'm' */   bit = UREGEX_MULTILINE;        break;
   1402             case 0x73: /* 's' */   bit = UREGEX_DOTALL;           break;
   1403             case 0x75: /* 'u' */   bit = 0; /* Unicode casing */  break;
   1404             case 0x77: /* 'w' */   bit = UREGEX_UWORD;            break;
   1405             case 0x78: /* 'x' */   bit = UREGEX_COMMENTS;         break;
   1406             case 0x2d: /* '-' */   fSetModeFlag = FALSE;          break;
   1407             default:
   1408                 U_ASSERT(FALSE);   // Should never happen.  Other chars are filtered out
   1409                                    // by the scanner.
   1410             }
   1411             if (fSetModeFlag) {
   1412                 fNewModeFlags |= bit;
   1413             } else {
   1414                 fNewModeFlags &= ~bit;
   1415             }
   1416         }
   1417         break;
   1418 
   1419     case doSetMatchMode:
   1420         // We've got a (?i) or similar.  The match mode is being changed, but
   1421         //   the change is not scoped to a parenthesized block.
   1422         U_ASSERT(fNewModeFlags < 0);
   1423         fModeFlags = fNewModeFlags;
   1424 
   1425         // Prevent any string from spanning across the change of match mode.
   1426         //   Otherwise the pattern "abc(?i)def" would make a single string of "abcdef"
   1427         fixLiterals();
   1428         break;
   1429 
   1430 
   1431     case doMatchModeParen:
   1432         // We've got a (?i: or similar.  Begin a parenthesized block, save old
   1433         //   mode flags so they can be restored at the close of the block.
   1434         //
   1435         //   Compile to a
   1436         //      - NOP, which later may be replaced by a save-state if the
   1437         //         parenthesized group gets a * quantifier, followed by
   1438         //      - NOP, which may later be replaced by a save-state if there
   1439         //             is an '|' alternation within the parens.
   1440         {
   1441             fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
   1442             fRXPat->fCompiledPat->addElement(URX_BUILD(URX_NOP, 0), *fStatus);
   1443 
   1444             // On the Parentheses stack, start a new frame and add the postions
   1445             //   of the two NOPs (a normal non-capturing () frame, except for the
   1446             //   saving of the orignal mode flags.)
   1447             fParenStack.push(fModeFlags, *fStatus);
   1448             fParenStack.push(flags, *fStatus);                            // Frame Marker
   1449             fParenStack.push(fRXPat->fCompiledPat->size()-2, *fStatus);   // The first NOP
   1450             fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus);   // The second NOP
   1451 
   1452             // Set the current mode flags to the new values.
   1453             U_ASSERT(fNewModeFlags < 0);
   1454             fModeFlags = fNewModeFlags;
   1455         }
   1456         break;
   1457 
   1458     case doBadModeFlag:
   1459         error(U_REGEX_INVALID_FLAG);
   1460         break;
   1461 
   1462     case doSuppressComments:
   1463         // We have just scanned a '(?'.  We now need to prevent the character scanner from
   1464         // treating a '#' as a to-the-end-of-line comment.
   1465         //   (This Perl compatibility just gets uglier and uglier to do...)
   1466         fEOLComments = FALSE;
   1467         break;
   1468 
   1469 
   1470     case doSetAddAmp:
   1471         {
   1472           UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
   1473           set->add(chAmp);
   1474         }
   1475         break;
   1476 
   1477     case doSetAddDash:
   1478         {
   1479           UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
   1480           set->add(chDash);
   1481         }
   1482         break;
   1483 
   1484      case doSetBackslash_s:
   1485         {
   1486          UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
   1487          set->addAll(*RegexStaticSets::gStaticSets->fPropSets[URX_ISSPACE_SET]);
   1488          break;
   1489         }
   1490 
   1491      case doSetBackslash_S:
   1492         {
   1493             UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
   1494             UnicodeSet SSet(*RegexStaticSets::gStaticSets->fPropSets[URX_ISSPACE_SET]);
   1495             SSet.complement();
   1496             set->addAll(SSet);
   1497             break;
   1498         }
   1499 
   1500     case doSetBackslash_d:
   1501         {
   1502             UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
   1503             // TODO - make a static set, ticket 6058.
   1504             addCategory(set, U_GC_ND_MASK, *fStatus);
   1505             break;
   1506         }
   1507 
   1508     case doSetBackslash_D:
   1509         {
   1510             UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
   1511             UnicodeSet digits;
   1512             // TODO - make a static set, ticket 6058.
   1513             digits.applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, U_GC_ND_MASK, *fStatus);
   1514             digits.complement();
   1515             set->addAll(digits);
   1516             break;
   1517         }
   1518 
   1519     case doSetBackslash_w:
   1520         {
   1521             UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
   1522             set->addAll(*RegexStaticSets::gStaticSets->fPropSets[URX_ISWORD_SET]);
   1523             break;
   1524         }
   1525 
   1526     case doSetBackslash_W:
   1527         {
   1528             UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
   1529             UnicodeSet SSet(*RegexStaticSets::gStaticSets->fPropSets[URX_ISWORD_SET]);
   1530             SSet.complement();
   1531             set->addAll(SSet);
   1532             break;
   1533         }
   1534 
   1535     case doSetBegin:
   1536         fSetStack.push(new UnicodeSet(), *fStatus);
   1537         fSetOpStack.push(setStart, *fStatus);
   1538         if ((fModeFlags & UREGEX_CASE_INSENSITIVE) != 0) {
   1539             fSetOpStack.push(setCaseClose, *fStatus);
   1540         }
   1541         break;
   1542 
   1543     case doSetBeginDifference1:
   1544         //  We have scanned something like [[abc]-[
   1545         //  Set up a new UnicodeSet for the set beginning with the just-scanned '['
   1546         //  Push a Difference operator, which will cause the new set to be subtracted from what
   1547         //    went before once it is created.
   1548         setPushOp(setDifference1);
   1549         fSetOpStack.push(setStart, *fStatus);
   1550         if ((fModeFlags & UREGEX_CASE_INSENSITIVE) != 0) {
   1551             fSetOpStack.push(setCaseClose, *fStatus);
   1552         }
   1553         break;
   1554 
   1555     case doSetBeginIntersection1:
   1556         //  We have scanned something like  [[abc]&[
   1557         //   Need both the '&' operator and the open '[' operator.
   1558         setPushOp(setIntersection1);
   1559         fSetOpStack.push(setStart, *fStatus);
   1560         if ((fModeFlags & UREGEX_CASE_INSENSITIVE) != 0) {
   1561             fSetOpStack.push(setCaseClose, *fStatus);
   1562         }
   1563         break;
   1564 
   1565     case doSetBeginUnion:
   1566         //  We have scanned something like  [[abc][
   1567         //     Need to handle the union operation explicitly [[abc] | [
   1568         setPushOp(setUnion);
   1569         fSetOpStack.push(setStart, *fStatus);
   1570         if ((fModeFlags & UREGEX_CASE_INSENSITIVE) != 0) {
   1571             fSetOpStack.push(setCaseClose, *fStatus);
   1572         }
   1573         break;
   1574 
   1575     case doSetDifference2:
   1576         // We have scanned something like [abc--
   1577         //   Consider this to unambiguously be a set difference operator.
   1578         setPushOp(setDifference2);
   1579         break;
   1580 
   1581     case doSetEnd:
   1582         // Have encountered the ']' that closes a set.
   1583         //    Force the evaluation of any pending operations within this set,
   1584         //    leave the completed set on the top of the set stack.
   1585         setEval(setEnd);
   1586         U_ASSERT(fSetOpStack.peeki()==setStart);
   1587         fSetOpStack.popi();
   1588         break;
   1589 
   1590     case doSetFinish:
   1591         {
   1592         // Finished a complete set expression, including all nested sets.
   1593         //   The close bracket has already triggered clearing out pending set operators,
   1594         //    the operator stack should be empty and the operand stack should have just
   1595         //    one entry, the result set.
   1596         U_ASSERT(fSetOpStack.empty());
   1597         UnicodeSet *theSet = (UnicodeSet *)fSetStack.pop();
   1598         U_ASSERT(fSetStack.empty());
   1599         compileSet(theSet);
   1600         break;
   1601         }
   1602 
   1603     case doSetIntersection2:
   1604         // Have scanned something like [abc&&
   1605         setPushOp(setIntersection2);
   1606         break;
   1607 
   1608     case doSetLiteral:
   1609         // Union the just-scanned literal character into the set being built.
   1610         //    This operation is the highest precedence set operation, so we can always do
   1611         //    it immediately, without waiting to see what follows.  It is necessary to perform
   1612         //    any pending '-' or '&' operation first, because these have the same precedence
   1613         //    as union-ing in a literal'
   1614         {
   1615             setEval(setUnion);
   1616             UnicodeSet *s = (UnicodeSet *)fSetStack.peek();
   1617             s->add(fC.fChar);
   1618             fLastSetLiteral = fC.fChar;
   1619             break;
   1620         }
   1621 
   1622     case doSetLiteralEscaped:
   1623         // A back-slash escaped literal character was encountered.
   1624         // Processing is the same as with setLiteral, above, with the addition of
   1625         //  the optional check for errors on escaped ASCII letters.
   1626         {
   1627             if ((fModeFlags & UREGEX_ERROR_ON_UNKNOWN_ESCAPES) != 0 &&
   1628                 ((fC.fChar >= 0x41 && fC.fChar<= 0x5A) ||     // in [A-Z]
   1629                  (fC.fChar >= 0x61 && fC.fChar <= 0x7a))) {   // in [a-z]
   1630                 error(U_REGEX_BAD_ESCAPE_SEQUENCE);
   1631             }
   1632             setEval(setUnion);
   1633             UnicodeSet *s = (UnicodeSet *)fSetStack.peek();
   1634             s->add(fC.fChar);
   1635             fLastSetLiteral = fC.fChar;
   1636             break;
   1637         }
   1638 
   1639         case doSetNamedChar:
   1640         // Scanning a \N{UNICODE CHARACTER NAME}
   1641         //  Aside from the source of the character, the processing is identical to doSetLiteral,
   1642         //    above.
   1643         {
   1644             UChar32  c = scanNamedChar();
   1645             setEval(setUnion);
   1646             UnicodeSet *s = (UnicodeSet *)fSetStack.peek();
   1647             s->add(c);
   1648             fLastSetLiteral = c;
   1649             break;
   1650         }
   1651 
   1652     case doSetNamedRange:
   1653         // We have scanned literal-\N{CHAR NAME}.  Add the range to the set.
   1654         // The left character is already in the set, and is saved in fLastSetLiteral.
   1655         // The right side needs to be picked up, the scan is at the 'N'.
   1656         // Lower Limit > Upper limit being an error matches both Java
   1657         //        and ICU UnicodeSet behavior.
   1658         {
   1659             UChar32  c = scanNamedChar();
   1660             if (U_SUCCESS(*fStatus) && fLastSetLiteral > c) {
   1661                 error(U_REGEX_INVALID_RANGE);
   1662             }
   1663             UnicodeSet *s = (UnicodeSet *)fSetStack.peek();
   1664             s->add(fLastSetLiteral, c);
   1665             fLastSetLiteral = c;
   1666             break;
   1667         }
   1668 
   1669 
   1670     case  doSetNegate:
   1671         // Scanned a '^' at the start of a set.
   1672         // Push the negation operator onto the set op stack.
   1673         // A twist for case-insensitive matching:
   1674         //   the case closure operation must happen _before_ negation.
   1675         //   But the case closure operation will already be on the stack if it's required.
   1676         //   This requires checking for case closure, and swapping the stack order
   1677         //    if it is present.
   1678         {
   1679             int32_t  tosOp = fSetOpStack.peeki();
   1680             if (tosOp == setCaseClose) {
   1681                 fSetOpStack.popi();
   1682                 fSetOpStack.push(setNegation, *fStatus);
   1683                 fSetOpStack.push(setCaseClose, *fStatus);
   1684             } else {
   1685                 fSetOpStack.push(setNegation, *fStatus);
   1686             }
   1687         }
   1688         break;
   1689 
   1690     case doSetNoCloseError:
   1691         error(U_REGEX_MISSING_CLOSE_BRACKET);
   1692         break;
   1693 
   1694     case doSetOpError:
   1695         error(U_REGEX_RULE_SYNTAX);   //  -- or && at the end of a set.  Illegal.
   1696         break;
   1697 
   1698     case doSetPosixProp:
   1699         {
   1700             UnicodeSet *s = scanPosixProp();
   1701             if (s != NULL) {
   1702                 UnicodeSet *tos = (UnicodeSet *)fSetStack.peek();
   1703                 tos->addAll(*s);
   1704                 delete s;
   1705             }  // else error.  scanProp() reported the error status already.
   1706         }
   1707         break;
   1708 
   1709     case doSetProp:
   1710         //  Scanned a \p \P within [brackets].
   1711         {
   1712             UnicodeSet *s = scanProp();
   1713             if (s != NULL) {
   1714                 UnicodeSet *tos = (UnicodeSet *)fSetStack.peek();
   1715                 tos->addAll(*s);
   1716                 delete s;
   1717             }  // else error.  scanProp() reported the error status already.
   1718         }
   1719         break;
   1720 
   1721 
   1722     case doSetRange:
   1723         // We have scanned literal-literal.  Add the range to the set.
   1724         // The left character is already in the set, and is saved in fLastSetLiteral.
   1725         // The right side is the current character.
   1726         // Lower Limit > Upper limit being an error matches both Java
   1727         //        and ICU UnicodeSet behavior.
   1728         {
   1729         if (fLastSetLiteral > fC.fChar) {
   1730             error(U_REGEX_INVALID_RANGE);
   1731         }
   1732         UnicodeSet *s = (UnicodeSet *)fSetStack.peek();
   1733         s->add(fLastSetLiteral, fC.fChar);
   1734         break;
   1735         }
   1736 
   1737 
   1738     default:
   1739         U_ASSERT(FALSE);
   1740         error(U_REGEX_INTERNAL_ERROR);
   1741         break;
   1742     }
   1743 
   1744     if (U_FAILURE(*fStatus)) {
   1745         returnVal = FALSE;
   1746     }
   1747 
   1748     return returnVal;
   1749 }
   1750 
   1751 
   1752 
   1753 //------------------------------------------------------------------------------
   1754 //
   1755 //   literalChar           We've encountered a literal character from the pattern,
   1756 //                             or an escape sequence that reduces to a character.
   1757 //                         Add it to the string containing all literal chars/strings from
   1758 //                             the pattern.
   1759 //                         If we are in a pattern string already, add the new char to it.
   1760 //                         If we aren't in a pattern string, begin one now.
   1761 //
   1762 //------------------------------------------------------------------------------
   1763 void RegexCompile::literalChar(UChar32 c)  {
   1764     int32_t           op;            // An operation in the compiled pattern.
   1765     int32_t           opType;
   1766     int32_t           patternLoc;   // A position in the compiled pattern.
   1767     int32_t           stringLen;
   1768 
   1769 
   1770     // If the last thing compiled into the pattern was not a literal char,
   1771     //   force this new literal char to begin a new string, and not append to the previous.
   1772     op     = (int32_t)fRXPat->fCompiledPat->lastElementi();
   1773     opType = URX_TYPE(op);
   1774     if (!(opType == URX_STRING_LEN || opType == URX_ONECHAR || opType == URX_ONECHAR_I)) {
   1775         fixLiterals();
   1776     }
   1777 
   1778     if (fStringOpStart == -1) {
   1779         // First char of a string in the pattern.
   1780         // Emit a OneChar op into the compiled pattern.
   1781         emitONE_CHAR(c);
   1782 
   1783         // Mark that we might actually be starting a string here
   1784         fStringOpStart = fRXPat->fLiteralText.length();
   1785         return;
   1786     }
   1787 
   1788     op     = (int32_t)fRXPat->fCompiledPat->lastElementi();
   1789     opType = URX_TYPE(op);
   1790     U_ASSERT(opType == URX_ONECHAR || opType == URX_ONECHAR_I || opType == URX_STRING_LEN);
   1791 
   1792     // If the most recently emitted op is a URX_ONECHAR,
   1793     if (opType == URX_ONECHAR || opType == URX_ONECHAR_I) {
   1794         if (U16_IS_TRAIL(c) && U16_IS_LEAD(URX_VAL(op))) {
   1795             // The most recently emitted op is a ONECHAR that was the first half
   1796             //   of a surrogate pair.  Update the ONECHAR's operand to be the
   1797             //   supplementary code point resulting from both halves of the pair.
   1798             c = U16_GET_SUPPLEMENTARY(URX_VAL(op), c);
   1799             op = URX_BUILD(opType, c);
   1800             patternLoc = fRXPat->fCompiledPat->size() - 1;
   1801             fRXPat->fCompiledPat->setElementAt(op, patternLoc);
   1802             return;
   1803         }
   1804 
   1805         // The most recently emitted op is a ONECHAR.
   1806         //  We've now received another adjacent char.  Change the ONECHAR op
   1807         //   to a string op.
   1808         fRXPat->fLiteralText.append(URX_VAL(op));
   1809 
   1810         if (fModeFlags & UREGEX_CASE_INSENSITIVE) {
   1811             op     = URX_BUILD(URX_STRING_I, fStringOpStart);
   1812         } else {
   1813             op     = URX_BUILD(URX_STRING, fStringOpStart);
   1814         }
   1815         patternLoc = fRXPat->fCompiledPat->size() - 1;
   1816         fRXPat->fCompiledPat->setElementAt(op, patternLoc);
   1817         op         = URX_BUILD(URX_STRING_LEN, 0);
   1818         fRXPat->fCompiledPat->addElement(op, *fStatus);
   1819     }
   1820 
   1821     // We are adding onto an existing string
   1822     fRXPat->fLiteralText.append(c);
   1823 
   1824     // The pattern contains a URX_SRING / URX_STRING_LEN.  Update the
   1825     //  string length to reflect the new char we just added to the string.
   1826     stringLen  = fRXPat->fLiteralText.length() - fStringOpStart;
   1827     op         = URX_BUILD(URX_STRING_LEN, stringLen);
   1828     patternLoc = fRXPat->fCompiledPat->size() - 1;
   1829     fRXPat->fCompiledPat->setElementAt(op, patternLoc);
   1830 }
   1831 
   1832 
   1833 
   1834 //------------------------------------------------------------------------------
   1835 //
   1836 //    emitONE_CHAR         emit a ONE_CHAR op into the generated code.
   1837 //                         Choose cased or uncased version, depending on the
   1838 //                         match mode and whether the character itself is cased.
   1839 //
   1840 //------------------------------------------------------------------------------
   1841 void RegexCompile::emitONE_CHAR(UChar32  c) {
   1842     int32_t op;
   1843     if ((fModeFlags & UREGEX_CASE_INSENSITIVE) &&
   1844         u_hasBinaryProperty(c, UCHAR_CASE_SENSITIVE)) {
   1845         // We have a cased character, and are in case insensitive matching mode.
   1846         //c  = u_foldCase(c, U_FOLD_CASE_DEFAULT);  // !!!: handled in stripNOPs() now
   1847         op = URX_BUILD(URX_ONECHAR_I, c);
   1848     } else {
   1849         // Uncased char, or case sensitive match mode.
   1850         //  Either way, just generate a literal compare of the char.
   1851         op = URX_BUILD(URX_ONECHAR, c);
   1852     }
   1853     fRXPat->fCompiledPat->addElement(op, *fStatus);
   1854 }
   1855 
   1856 
   1857 //------------------------------------------------------------------------------
   1858 //
   1859 //    fixLiterals           When compiling something that can follow a literal
   1860 //                          string in a pattern, we need to "fix" any preceding
   1861 //                          string, which will cause any subsequent literals to
   1862 //                          begin a new string, rather than appending to the
   1863 //                          old one.
   1864 //
   1865 //                          Optionally, split the last char of the string off into
   1866 //                          a single "ONE_CHAR" operation, so that quantifiers can
   1867 //                          apply to that char alone.  Example:   abc*
   1868 //                          The * must apply to the 'c' only.
   1869 //
   1870 //------------------------------------------------------------------------------
   1871 void    RegexCompile::fixLiterals(UBool split) {
   1872     int32_t  stringStart = fStringOpStart;    // start index of the current literal string
   1873     int32_t  op;                              // An op from/for the compiled pattern.
   1874     int32_t  opType;                          // An opcode type from the compiled pattern.
   1875     int32_t  stringLastCharIdx;
   1876     UChar32  lastChar;
   1877     int32_t  stringNextToLastCharIdx;
   1878     UChar32  nextToLastChar;
   1879     int32_t  stringLen;
   1880 
   1881     fStringOpStart = -1;
   1882     if (!split) {
   1883         return;
   1884     }
   1885 
   1886     // Split:  We need to  ensure that the last item in the compiled pattern does
   1887     //   not refer to a literal string of more than one char.  If it does,
   1888     //   separate the last char from the rest of the string.
   1889 
   1890     // If the last operation from the compiled pattern is not a string,
   1891     //   nothing needs to be done
   1892     op     = (int32_t)fRXPat->fCompiledPat->lastElementi();
   1893     opType = URX_TYPE(op);
   1894     if (opType != URX_STRING_LEN) {
   1895         return;
   1896     }
   1897     stringLen = URX_VAL(op);
   1898 
   1899     //
   1900     // Find the position of the last code point in the string  (might be a surrogate pair)
   1901     //
   1902     stringLastCharIdx = fRXPat->fLiteralText.length();
   1903     stringLastCharIdx = fRXPat->fLiteralText.moveIndex32(stringLastCharIdx, -1);
   1904     lastChar          = fRXPat->fLiteralText.char32At(stringLastCharIdx);
   1905 
   1906     // The string should always be at least two code points long, meaning that there
   1907     //   should be something before the last char position that we just found.
   1908     U_ASSERT(stringLastCharIdx > stringStart);
   1909     stringNextToLastCharIdx = fRXPat->fLiteralText.moveIndex32(stringLastCharIdx, -1);
   1910     U_ASSERT(stringNextToLastCharIdx >= stringStart);
   1911     nextToLastChar          = fRXPat->fLiteralText.char32At(stringNextToLastCharIdx);
   1912 
   1913     if (stringNextToLastCharIdx > stringStart) {
   1914         // The length of string remaining after removing one char is two or more.
   1915         // Leave the string in the compiled pattern, shorten it by one char,
   1916         //   and append a URX_ONECHAR op for the last char.
   1917         stringLen -= (fRXPat->fLiteralText.length() - stringLastCharIdx);
   1918         op = URX_BUILD(URX_STRING_LEN, stringLen);
   1919         fRXPat->fCompiledPat->setElementAt(op, fRXPat->fCompiledPat->size() -1);
   1920         emitONE_CHAR(lastChar);
   1921     } else {
   1922         // The original string consisted of exactly two characters.  Replace
   1923         // the existing compiled URX_STRING/URX_STRING_LEN ops with a pair
   1924         // of URX_ONECHARs.
   1925         fRXPat->fCompiledPat->setSize(fRXPat->fCompiledPat->size() -2);
   1926         emitONE_CHAR(nextToLastChar);
   1927         emitONE_CHAR(lastChar);
   1928     }
   1929 }
   1930 
   1931 
   1932 
   1933 
   1934 
   1935 
   1936 //------------------------------------------------------------------------------
   1937 //
   1938 //   insertOp()             Insert a slot for a new opcode into the already
   1939 //                          compiled pattern code.
   1940 //
   1941 //                          Fill the slot with a NOP.  Our caller will replace it
   1942 //                          with what they really wanted.
   1943 //
   1944 //------------------------------------------------------------------------------
   1945 void   RegexCompile::insertOp(int32_t where) {
   1946     UVector64 *code = fRXPat->fCompiledPat;
   1947     U_ASSERT(where>0 && where < code->size());
   1948 
   1949     int32_t  nop = URX_BUILD(URX_NOP, 0);
   1950     code->insertElementAt(nop, where, *fStatus);
   1951 
   1952     // Walk through the pattern, looking for any ops with targets that
   1953     //  were moved down by the insert.  Fix them.
   1954     int32_t loc;
   1955     for (loc=0; loc<code->size(); loc++) {
   1956         int32_t op = (int32_t)code->elementAti(loc);
   1957         int32_t opType = URX_TYPE(op);
   1958         int32_t opValue = URX_VAL(op);
   1959         if ((opType == URX_JMP         ||
   1960             opType == URX_JMPX         ||
   1961             opType == URX_STATE_SAVE   ||
   1962             opType == URX_CTR_LOOP     ||
   1963             opType == URX_CTR_LOOP_NG  ||
   1964             opType == URX_JMP_SAV      ||
   1965             opType == URX_JMP_SAV_X    ||
   1966             opType == URX_RELOC_OPRND)    && opValue > where) {
   1967             // Target location for this opcode is after the insertion point and
   1968             //   needs to be incremented to adjust for the insertion.
   1969             opValue++;
   1970             op = URX_BUILD(opType, opValue);
   1971             code->setElementAt(op, loc);
   1972         }
   1973     }
   1974 
   1975     // Now fix up the parentheses stack.  All positive values in it are locations in
   1976     //  the compiled pattern.   (Negative values are frame boundaries, and don't need fixing.)
   1977     for (loc=0; loc<fParenStack.size(); loc++) {
   1978         int32_t x = fParenStack.elementAti(loc);
   1979         U_ASSERT(x < code->size());
   1980         if (x>where) {
   1981             x++;
   1982             fParenStack.setElementAt(x, loc);
   1983         }
   1984     }
   1985 
   1986     if (fMatchCloseParen > where) {
   1987         fMatchCloseParen++;
   1988     }
   1989     if (fMatchOpenParen > where) {
   1990         fMatchOpenParen++;
   1991     }
   1992 }
   1993 
   1994 
   1995 
   1996 //------------------------------------------------------------------------------
   1997 //
   1998 //   blockTopLoc()          Find or create a location in the compiled pattern
   1999 //                          at the start of the operation or block that has
   2000 //                          just been compiled.  Needed when a quantifier (* or
   2001 //                          whatever) appears, and we need to add an operation
   2002 //                          at the start of the thing being quantified.
   2003 //
   2004 //                          (Parenthesized Blocks) have a slot with a NOP that
   2005 //                          is reserved for this purpose.  .* or similar don't
   2006 //                          and a slot needs to be added.
   2007 //
   2008 //       parameter reserveLoc   :  TRUE -  ensure that there is space to add an opcode
   2009 //                                         at the returned location.
   2010 //                                 FALSE - just return the address,
   2011 //                                         do not reserve a location there.
   2012 //
   2013 //------------------------------------------------------------------------------
   2014 int32_t   RegexCompile::blockTopLoc(UBool reserveLoc) {
   2015     int32_t   theLoc;
   2016     if (fRXPat->fCompiledPat->size() == fMatchCloseParen)
   2017     {
   2018         // The item just processed is a parenthesized block.
   2019         theLoc = fMatchOpenParen;   // A slot is already reserved for us.
   2020         U_ASSERT(theLoc > 0);
   2021         U_ASSERT(URX_TYPE(((uint32_t)fRXPat->fCompiledPat->elementAti(theLoc))) == URX_NOP);
   2022     }
   2023     else {
   2024         // Item just compiled is a single thing, a ".", or a single char, or a set reference.
   2025         // No slot for STATE_SAVE was pre-reserved in the compiled code.
   2026         // We need to make space now.
   2027         fixLiterals(TRUE);  // If last item was a string, separate the last char.
   2028         theLoc = fRXPat->fCompiledPat->size()-1;
   2029         if (reserveLoc) {
   2030             /*int32_t opAtTheLoc = fRXPat->fCompiledPat->elementAti(theLoc);*/
   2031             int32_t  nop = URX_BUILD(URX_NOP, 0);
   2032             fRXPat->fCompiledPat->insertElementAt(nop, theLoc, *fStatus);
   2033         }
   2034     }
   2035     return theLoc;
   2036 }
   2037 
   2038 
   2039 
   2040 //------------------------------------------------------------------------------
   2041 //
   2042 //    handleCloseParen      When compiling a close paren, we need to go back
   2043 //                          and fix up any JMP or SAVE operations within the
   2044 //                          parenthesized block that need to target the end
   2045 //                          of the block.  The locations of these are kept on
   2046 //                          the paretheses stack.
   2047 //
   2048 //                          This function is called both when encountering a
   2049 //                          real ) and at the end of the pattern.
   2050 //
   2051 //------------------------------------------------------------------------------
   2052 void  RegexCompile::handleCloseParen() {
   2053     int32_t   patIdx;
   2054     int32_t   patOp;
   2055     if (fParenStack.size() <= 0) {
   2056         error(U_REGEX_MISMATCHED_PAREN);
   2057         return;
   2058     }
   2059 
   2060     // Force any literal chars that may follow the close paren to start a new string,
   2061     //   and not attach to any preceding it.
   2062     fixLiterals(FALSE);
   2063 
   2064     // Fixup any operations within the just-closed parenthesized group
   2065     //    that need to reference the end of the (block).
   2066     //    (The first one popped from the stack is an unused slot for
   2067     //     alternation (OR) state save, but applying the fixup to it does no harm.)
   2068     for (;;) {
   2069         patIdx = fParenStack.popi();
   2070         if (patIdx < 0) {
   2071             // value < 0 flags the start of the frame on the paren stack.
   2072             break;
   2073         }
   2074         U_ASSERT(patIdx>0 && patIdx <= fRXPat->fCompiledPat->size());
   2075         patOp = (int32_t)fRXPat->fCompiledPat->elementAti(patIdx);
   2076         U_ASSERT(URX_VAL(patOp) == 0);          // Branch target for JMP should not be set.
   2077         patOp |= fRXPat->fCompiledPat->size();  // Set it now.
   2078         fRXPat->fCompiledPat->setElementAt(patOp, patIdx);
   2079         fMatchOpenParen     = patIdx;
   2080     }
   2081 
   2082     //  At the close of any parenthesized block, restore the match mode flags  to
   2083     //  the value they had at the open paren.  Saved value is
   2084     //  at the top of the paren stack.
   2085     fModeFlags = fParenStack.popi();
   2086     U_ASSERT(fModeFlags < 0);
   2087 
   2088     // DO any additional fixups, depending on the specific kind of
   2089     // parentesized grouping this is
   2090 
   2091     switch (patIdx) {
   2092     case plain:
   2093     case flags:
   2094         // No additional fixups required.
   2095         //   (Grouping-only parentheses)
   2096         break;
   2097     case capturing:
   2098         // Capturing Parentheses.
   2099         //   Insert a End Capture op into the pattern.
   2100         //   The frame offset of the variables for this cg is obtained from the
   2101         //       start capture op and put it into the end-capture op.
   2102         {
   2103             int32_t   captureOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen+1);
   2104             U_ASSERT(URX_TYPE(captureOp) == URX_START_CAPTURE);
   2105 
   2106             int32_t   frameVarLocation = URX_VAL(captureOp);
   2107             int32_t   endCaptureOp = URX_BUILD(URX_END_CAPTURE, frameVarLocation);
   2108             fRXPat->fCompiledPat->addElement(endCaptureOp, *fStatus);
   2109         }
   2110         break;
   2111     case atomic:
   2112         // Atomic Parenthesis.
   2113         //   Insert a LD_SP operation to restore the state stack to the position
   2114         //   it was when the atomic parens were entered.
   2115         {
   2116             int32_t   stoOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen+1);
   2117             U_ASSERT(URX_TYPE(stoOp) == URX_STO_SP);
   2118             int32_t   stoLoc = URX_VAL(stoOp);
   2119             int32_t   ldOp   = URX_BUILD(URX_LD_SP, stoLoc);
   2120             fRXPat->fCompiledPat->addElement(ldOp, *fStatus);
   2121         }
   2122         break;
   2123 
   2124     case lookAhead:
   2125         {
   2126             int32_t  startOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen-5);
   2127             U_ASSERT(URX_TYPE(startOp) == URX_LA_START);
   2128             int32_t dataLoc  = URX_VAL(startOp);
   2129             int32_t op       = URX_BUILD(URX_LA_END, dataLoc);
   2130             fRXPat->fCompiledPat->addElement(op, *fStatus);
   2131         }
   2132         break;
   2133 
   2134     case negLookAhead:
   2135         {
   2136             // See comment at doOpenLookAheadNeg
   2137             int32_t  startOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen-1);
   2138             U_ASSERT(URX_TYPE(startOp) == URX_LA_START);
   2139             int32_t dataLoc  = URX_VAL(startOp);
   2140             int32_t op       = URX_BUILD(URX_LA_END, dataLoc);
   2141             fRXPat->fCompiledPat->addElement(op, *fStatus);
   2142             op               = URX_BUILD(URX_BACKTRACK, 0);
   2143             fRXPat->fCompiledPat->addElement(op, *fStatus);
   2144             op               = URX_BUILD(URX_LA_END, dataLoc);
   2145             fRXPat->fCompiledPat->addElement(op, *fStatus);
   2146 
   2147             // Patch the URX_SAVE near the top of the block.
   2148             // The destination of the SAVE is the final LA_END that was just added.
   2149             int32_t saveOp   = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen);
   2150             U_ASSERT(URX_TYPE(saveOp) == URX_STATE_SAVE);
   2151             int32_t dest     = fRXPat->fCompiledPat->size()-1;
   2152             saveOp           = URX_BUILD(URX_STATE_SAVE, dest);
   2153             fRXPat->fCompiledPat->setElementAt(saveOp, fMatchOpenParen);
   2154         }
   2155         break;
   2156 
   2157     case lookBehind:
   2158         {
   2159             // See comment at doOpenLookBehind.
   2160 
   2161             // Append the URX_LB_END and URX_LA_END to the compiled pattern.
   2162             int32_t  startOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen-4);
   2163             U_ASSERT(URX_TYPE(startOp) == URX_LB_START);
   2164             int32_t dataLoc  = URX_VAL(startOp);
   2165             int32_t op       = URX_BUILD(URX_LB_END, dataLoc);
   2166             fRXPat->fCompiledPat->addElement(op, *fStatus);
   2167                     op       = URX_BUILD(URX_LA_END, dataLoc);
   2168             fRXPat->fCompiledPat->addElement(op, *fStatus);
   2169 
   2170             // Determine the min and max bounds for the length of the
   2171             //  string that the pattern can match.
   2172             //  An unbounded upper limit is an error.
   2173             int32_t patEnd   = fRXPat->fCompiledPat->size() - 1;
   2174             int32_t minML    = minMatchLength(fMatchOpenParen, patEnd);
   2175             int32_t maxML    = maxMatchLength(fMatchOpenParen, patEnd);
   2176             if (maxML == INT32_MAX) {
   2177                 error(U_REGEX_LOOK_BEHIND_LIMIT);
   2178                 break;
   2179             }
   2180             U_ASSERT(minML <= maxML);
   2181 
   2182             // Insert the min and max match len bounds into the URX_LB_CONT op that
   2183             //  appears at the top of the look-behind block, at location fMatchOpenParen+1
   2184             fRXPat->fCompiledPat->setElementAt(minML,  fMatchOpenParen-2);
   2185             fRXPat->fCompiledPat->setElementAt(maxML,  fMatchOpenParen-1);
   2186 
   2187         }
   2188         break;
   2189 
   2190 
   2191 
   2192     case lookBehindN:
   2193         {
   2194             // See comment at doOpenLookBehindNeg.
   2195 
   2196             // Append the URX_LBN_END to the compiled pattern.
   2197             int32_t  startOp = (int32_t)fRXPat->fCompiledPat->elementAti(fMatchOpenParen-5);
   2198             U_ASSERT(URX_TYPE(startOp) == URX_LB_START);
   2199             int32_t dataLoc  = URX_VAL(startOp);
   2200             int32_t op       = URX_BUILD(URX_LBN_END, dataLoc);
   2201             fRXPat->fCompiledPat->addElement(op, *fStatus);
   2202 
   2203             // Determine the min and max bounds for the length of the
   2204             //  string that the pattern can match.
   2205             //  An unbounded upper limit is an error.
   2206             int32_t patEnd   = fRXPat->fCompiledPat->size() - 1;
   2207             int32_t minML    = minMatchLength(fMatchOpenParen, patEnd);
   2208             int32_t maxML    = maxMatchLength(fMatchOpenParen, patEnd);
   2209             if (maxML == INT32_MAX) {
   2210                 error(U_REGEX_LOOK_BEHIND_LIMIT);
   2211                 break;
   2212             }
   2213             U_ASSERT(minML <= maxML);
   2214 
   2215             // Insert the min and max match len bounds into the URX_LB_CONT op that
   2216             //  appears at the top of the look-behind block, at location fMatchOpenParen+1
   2217             fRXPat->fCompiledPat->setElementAt(minML,  fMatchOpenParen-3);
   2218             fRXPat->fCompiledPat->setElementAt(maxML,  fMatchOpenParen-2);
   2219 
   2220             // Insert the pattern location to continue at after a successful match
   2221             //  as the last operand of the URX_LBN_CONT
   2222             op = URX_BUILD(URX_RELOC_OPRND, fRXPat->fCompiledPat->size());
   2223             fRXPat->fCompiledPat->setElementAt(op,  fMatchOpenParen-1);
   2224         }
   2225         break;
   2226 
   2227 
   2228 
   2229     default:
   2230         U_ASSERT(FALSE);
   2231     }
   2232 
   2233     // remember the next location in the compiled pattern.
   2234     // The compilation of Quantifiers will look at this to see whether its looping
   2235     //   over a parenthesized block or a single item
   2236     fMatchCloseParen = fRXPat->fCompiledPat->size();
   2237 }
   2238 
   2239 
   2240 
   2241 //------------------------------------------------------------------------------
   2242 //
   2243 //   compileSet       Compile the pattern operations for a reference to a
   2244 //                    UnicodeSet.
   2245 //
   2246 //------------------------------------------------------------------------------
   2247 void        RegexCompile::compileSet(UnicodeSet *theSet)
   2248 {
   2249     if (theSet == NULL) {
   2250         return;
   2251     }
   2252     //  Remove any strings from the set.
   2253     //  There shoudn't be any, but just in case.
   2254     //     (Case Closure can add them; if we had a simple case closure avaialble that
   2255     //      ignored strings, that would be better.)
   2256     theSet->removeAllStrings();
   2257     int32_t  setSize = theSet->size();
   2258 
   2259     switch (setSize) {
   2260     case 0:
   2261         {
   2262             // Set of no elements.   Always fails to match.
   2263             fRXPat->fCompiledPat->addElement(URX_BUILD(URX_BACKTRACK, 0), *fStatus);
   2264             delete theSet;
   2265         }
   2266         break;
   2267 
   2268     case 1:
   2269         {
   2270             // The set contains only a single code point.  Put it into
   2271             //   the compiled pattern as a single char operation rather
   2272             //   than a set, and discard the set itself.
   2273             literalChar(theSet->charAt(0));
   2274             delete theSet;
   2275         }
   2276         break;
   2277 
   2278     default:
   2279         {
   2280             //  The set contains two or more chars.  (the normal case)
   2281             //  Put it into the compiled pattern as a set.
   2282             int32_t setNumber = fRXPat->fSets->size();
   2283             fRXPat->fSets->addElement(theSet, *fStatus);
   2284             int32_t setOp = URX_BUILD(URX_SETREF, setNumber);
   2285             fRXPat->fCompiledPat->addElement(setOp, *fStatus);
   2286         }
   2287     }
   2288 }
   2289 
   2290 
   2291 //------------------------------------------------------------------------------
   2292 //
   2293 //   compileInterval    Generate the code for a {min, max} style interval quantifier.
   2294 //                      Except for the specific opcodes used, the code is the same
   2295 //                      for all three types (greedy, non-greedy, possessive) of
   2296 //                      intervals.  The opcodes are supplied as parameters.
   2297 //
   2298 //                      The code for interval loops has this form:
   2299 //                         0  CTR_INIT   counter loc (in stack frame)
   2300 //                         1             5  patt address of CTR_LOOP at bottom of block
   2301 //                         2             min count
   2302 //                         3             max count   (-1 for unbounded)
   2303 //                         4  ...        block to be iterated over
   2304 //                         5  CTR_LOOP
   2305 //
   2306 //                       In
   2307 //------------------------------------------------------------------------------
   2308 void        RegexCompile::compileInterval(int32_t InitOp,  int32_t LoopOp)
   2309 {
   2310     // The CTR_INIT op at the top of the block with the {n,m} quantifier takes
   2311     //   four slots in the compiled code.  Reserve them.
   2312     int32_t   topOfBlock = blockTopLoc(TRUE);
   2313     insertOp(topOfBlock);
   2314     insertOp(topOfBlock);
   2315     insertOp(topOfBlock);
   2316 
   2317     // The operands for the CTR_INIT opcode include the index in the matcher data
   2318     //   of the counter.  Allocate it now.
   2319     int32_t   counterLoc = fRXPat->fFrameSize;
   2320     fRXPat->fFrameSize++;
   2321 
   2322     int32_t   op = URX_BUILD(InitOp, counterLoc);
   2323     fRXPat->fCompiledPat->setElementAt(op, topOfBlock);
   2324 
   2325     // The second operand of CTR_INIT is the location following the end of the loop.
   2326     //   Must put in as a URX_RELOC_OPRND so that the value will be adjusted if the
   2327     //   compilation of something later on causes the code to grow and the target
   2328     //   position to move.
   2329     int32_t loopEnd = fRXPat->fCompiledPat->size();
   2330     op = URX_BUILD(URX_RELOC_OPRND, loopEnd);
   2331     fRXPat->fCompiledPat->setElementAt(op, topOfBlock+1);
   2332 
   2333     // Followed by the min and max counts.
   2334     fRXPat->fCompiledPat->setElementAt(fIntervalLow, topOfBlock+2);
   2335     fRXPat->fCompiledPat->setElementAt(fIntervalUpper, topOfBlock+3);
   2336 
   2337     // Apend the CTR_LOOP op.  The operand is the location of the CTR_INIT op.
   2338     //   Goes at end of the block being looped over, so just append to the code so far.
   2339     op = URX_BUILD(LoopOp, topOfBlock);
   2340     fRXPat->fCompiledPat->addElement(op, *fStatus);
   2341 
   2342     if ((fIntervalLow & 0xff000000) != 0 ||
   2343         (fIntervalUpper > 0 && (fIntervalUpper & 0xff000000) != 0)) {
   2344             error(U_REGEX_NUMBER_TOO_BIG);
   2345         }
   2346 
   2347     if (fIntervalLow > fIntervalUpper && fIntervalUpper != -1) {
   2348         error(U_REGEX_MAX_LT_MIN);
   2349     }
   2350 }
   2351 
   2352 
   2353 
   2354 UBool RegexCompile::compileInlineInterval() {
   2355     if (fIntervalUpper > 10 || fIntervalUpper < fIntervalLow) {
   2356         // Too big to inline.  Fail, which will cause looping code to be generated.
   2357         //   (Upper < Lower picks up unbounded upper and errors, both.)
   2358         return FALSE;
   2359     }
   2360 
   2361     int32_t   topOfBlock = blockTopLoc(FALSE);
   2362     if (fIntervalUpper == 0) {
   2363         // Pathological case.  Attempt no matches, as if the block doesn't exist.
   2364         fRXPat->fCompiledPat->setSize(topOfBlock);
   2365         return TRUE;
   2366     }
   2367 
   2368     if (topOfBlock != fRXPat->fCompiledPat->size()-1 && fIntervalUpper != 1) {
   2369         // The thing being repeated is not a single op, but some
   2370         //   more complex block.  Do it as a loop, not inlines.
   2371         //   Note that things "repeated" a max of once are handled as inline, because
   2372         //     the one copy of the code already generated is just fine.
   2373         return FALSE;
   2374     }
   2375 
   2376     // Pick up the opcode that is to be repeated
   2377     //
   2378     int32_t op = (int32_t)fRXPat->fCompiledPat->elementAti(topOfBlock);
   2379 
   2380     // Compute the pattern location where the inline sequence
   2381     //   will end, and set up the state save op that will be needed.
   2382     //
   2383     int32_t endOfSequenceLoc = fRXPat->fCompiledPat->size()-1
   2384                                 + fIntervalUpper + (fIntervalUpper-fIntervalLow);
   2385     int32_t saveOp = URX_BUILD(URX_STATE_SAVE, endOfSequenceLoc);
   2386     if (fIntervalLow == 0) {
   2387         insertOp(topOfBlock);
   2388         fRXPat->fCompiledPat->setElementAt(saveOp, topOfBlock);
   2389     }
   2390 
   2391 
   2392 
   2393     //  Loop, emitting the op for the thing being repeated each time.
   2394     //    Loop starts at 1 because one instance of the op already exists in the pattern,
   2395     //    it was put there when it was originally encountered.
   2396     int32_t i;
   2397     for (i=1; i<fIntervalUpper; i++ ) {
   2398         if (i == fIntervalLow) {
   2399             fRXPat->fCompiledPat->addElement(saveOp, *fStatus);
   2400         }
   2401         if (i > fIntervalLow) {
   2402             fRXPat->fCompiledPat->addElement(saveOp, *fStatus);
   2403         }
   2404         fRXPat->fCompiledPat->addElement(op, *fStatus);
   2405     }
   2406     return TRUE;
   2407 }
   2408 
   2409 
   2410 
   2411 //------------------------------------------------------------------------------
   2412 //
   2413 //   matchStartType    Determine how a match can start.
   2414 //                     Used to optimize find() operations.
   2415 //
   2416 //                     Operation is very similar to minMatchLength().  Walk the compiled
   2417 //                     pattern, keeping an on-going minimum-match-length.  For any
   2418 //                     op where the min match coming in is zero, add that ops possible
   2419 //                     starting matches to the possible starts for the overall pattern.
   2420 //
   2421 //------------------------------------------------------------------------------
   2422 void   RegexCompile::matchStartType() {
   2423     if (U_FAILURE(*fStatus)) {
   2424         return;
   2425     }
   2426 
   2427 
   2428     int32_t    loc;                    // Location in the pattern of the current op being processed.
   2429     int32_t    op;                     // The op being processed
   2430     int32_t    opType;                 // The opcode type of the op
   2431     int32_t    currentLen = 0;         // Minimum length of a match to this point (loc) in the pattern
   2432     int32_t    numInitialStrings = 0;  // Number of strings encountered that could match at start.
   2433 
   2434     UBool      atStart = TRUE;         // True if no part of the pattern yet encountered
   2435                                        //   could have advanced the position in a match.
   2436                                        //   (Maximum match length so far == 0)
   2437 
   2438     // forwardedLength is a vector holding minimum-match-length values that
   2439     //   are propagated forward in the pattern by JMP or STATE_SAVE operations.
   2440     //   It must be one longer than the pattern being checked because some  ops
   2441     //   will jmp to a end-of-block+1 location from within a block, and we must
   2442     //   count those when checking the block.
   2443     int32_t end = fRXPat->fCompiledPat->size();
   2444     UVector32  forwardedLength(end+1, *fStatus);
   2445     forwardedLength.setSize(end+1);
   2446     for (loc=3; loc<end; loc++) {
   2447         forwardedLength.setElementAt(INT32_MAX, loc);
   2448     }
   2449 
   2450     for (loc = 3; loc<end; loc++) {
   2451         op = (int32_t)fRXPat->fCompiledPat->elementAti(loc);
   2452         opType = URX_TYPE(op);
   2453 
   2454         // The loop is advancing linearly through the pattern.
   2455         // If the op we are now at was the destination of a branch in the pattern,
   2456         // and that path has a shorter minimum length than the current accumulated value,
   2457         // replace the current accumulated value.
   2458         if (forwardedLength.elementAti(loc) < currentLen) {
   2459             currentLen = forwardedLength.elementAti(loc);
   2460             U_ASSERT(currentLen>=0 && currentLen < INT32_MAX);
   2461         }
   2462 
   2463         switch (opType) {
   2464             // Ops that don't change the total length matched
   2465         case URX_RESERVED_OP:
   2466         case URX_END:
   2467         case URX_FAIL:
   2468         case URX_STRING_LEN:
   2469         case URX_NOP:
   2470         case URX_START_CAPTURE:
   2471         case URX_END_CAPTURE:
   2472         case URX_BACKSLASH_B:
   2473         case URX_BACKSLASH_BU:
   2474         case URX_BACKSLASH_G:
   2475         case URX_BACKSLASH_Z:
   2476         case URX_DOLLAR:
   2477         case URX_DOLLAR_M:
   2478         case URX_DOLLAR_D:
   2479         case URX_DOLLAR_MD:
   2480         case URX_RELOC_OPRND:
   2481         case URX_STO_INP_LOC:
   2482         case URX_BACKREF:         // BackRef.  Must assume that it might be a zero length match
   2483         case URX_BACKREF_I:
   2484 
   2485         case URX_STO_SP:          // Setup for atomic or possessive blocks.  Doesn't change what can match.
   2486         case URX_LD_SP:
   2487             break;
   2488 
   2489         case URX_CARET:
   2490             if (atStart) {
   2491                 fRXPat->fStartType = START_START;
   2492             }
   2493             break;
   2494 
   2495         case URX_CARET_M:
   2496         case URX_CARET_M_UNIX:
   2497             if (atStart) {
   2498                 fRXPat->fStartType = START_LINE;
   2499             }
   2500             break;
   2501 
   2502         case URX_ONECHAR:
   2503             if (currentLen == 0) {
   2504                 // This character could appear at the start of a match.
   2505                 //   Add it to the set of possible starting characters.
   2506                 fRXPat->fInitialChars->add(URX_VAL(op));
   2507                 numInitialStrings += 2;
   2508             }
   2509             currentLen++;
   2510             atStart = FALSE;
   2511             break;
   2512 
   2513 
   2514         case URX_SETREF:
   2515             if (currentLen == 0) {
   2516                 int32_t  sn = URX_VAL(op);
   2517                 U_ASSERT(sn > 0 && sn < fRXPat->fSets->size());
   2518                 const UnicodeSet *s = (UnicodeSet *)fRXPat->fSets->elementAt(sn);
   2519                 fRXPat->fInitialChars->addAll(*s);
   2520                 numInitialStrings += 2;
   2521             }
   2522             currentLen++;
   2523             atStart = FALSE;
   2524             break;
   2525 
   2526         case URX_LOOP_SR_I:
   2527             // [Set]*, like a SETREF, above, in what it can match,
   2528             //  but may not match at all, so currentLen is not incremented.
   2529             if (currentLen == 0) {
   2530                 int32_t  sn = URX_VAL(op);
   2531                 U_ASSERT(sn > 0 && sn < fRXPat->fSets->size());
   2532                 const UnicodeSet *s = (UnicodeSet *)fRXPat->fSets->elementAt(sn);
   2533                 fRXPat->fInitialChars->addAll(*s);
   2534                 numInitialStrings += 2;
   2535             }
   2536             atStart = FALSE;
   2537             break;
   2538 
   2539         case URX_LOOP_DOT_I:
   2540             if (currentLen == 0) {
   2541                 // .* at the start of a pattern.
   2542                 //    Any character can begin the match.
   2543                 fRXPat->fInitialChars->clear();
   2544                 fRXPat->fInitialChars->complement();
   2545                 numInitialStrings += 2;
   2546             }
   2547             atStart = FALSE;
   2548             break;
   2549 
   2550 
   2551         case URX_STATIC_SETREF:
   2552             if (currentLen == 0) {
   2553                 int32_t  sn = URX_VAL(op);
   2554                 U_ASSERT(sn>0 && sn<URX_LAST_SET);
   2555                 const UnicodeSet *s = fRXPat->fStaticSets[sn];
   2556                 fRXPat->fInitialChars->addAll(*s);
   2557                 numInitialStrings += 2;
   2558             }
   2559             currentLen++;
   2560             atStart = FALSE;
   2561             break;
   2562 
   2563 
   2564 
   2565         case URX_STAT_SETREF_N:
   2566             if (currentLen == 0) {
   2567                 int32_t  sn = URX_VAL(op);
   2568                 const UnicodeSet *s = fRXPat->fStaticSets[sn];
   2569                 UnicodeSet sc(*s);
   2570                 sc.complement();
   2571                 fRXPat->fInitialChars->addAll(sc);
   2572                 numInitialStrings += 2;
   2573             }
   2574             currentLen++;
   2575             atStart = FALSE;
   2576             break;
   2577 
   2578 
   2579 
   2580         case URX_BACKSLASH_D:
   2581             // Digit Char
   2582              if (currentLen == 0) {
   2583                  UnicodeSet s;
   2584                  s.applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, U_GC_ND_MASK, *fStatus);
   2585                  if (URX_VAL(op) != 0) {
   2586                      s.complement();
   2587                  }
   2588                  fRXPat->fInitialChars->addAll(s);
   2589                  numInitialStrings += 2;
   2590             }
   2591             currentLen++;
   2592             atStart = FALSE;
   2593             break;
   2594 
   2595 
   2596         case URX_ONECHAR_I:
   2597             // Case Insensitive Single Character.
   2598             if (currentLen == 0) {
   2599                 UChar32  c = URX_VAL(op);
   2600                 if (u_hasBinaryProperty(c, UCHAR_CASE_SENSITIVE)) {
   2601                     // character may have distinct cased forms.  Add all of them
   2602                     //   to the set of possible starting match chars.
   2603                     UnicodeSet s(c, c);
   2604                     s.closeOver(USET_CASE_INSENSITIVE);
   2605                     fRXPat->fInitialChars->addAll(s);
   2606                 } else {
   2607                     // Char has no case variants.  Just add it as-is to the
   2608                     //   set of possible starting chars.
   2609                     fRXPat->fInitialChars->add(c);
   2610                 }
   2611                 numInitialStrings += 2;
   2612             }
   2613             currentLen++;
   2614             atStart = FALSE;
   2615             break;
   2616 
   2617 
   2618         case URX_BACKSLASH_X:   // Grahpeme Cluster.  Minimum is 1, max unbounded.
   2619         case URX_DOTANY_ALL:    // . matches one or two.
   2620         case URX_DOTANY:
   2621         case URX_DOTANY_UNIX:
   2622             if (currentLen == 0) {
   2623                 // These constructs are all bad news when they appear at the start
   2624                 //   of a match.  Any character can begin the match.
   2625                 fRXPat->fInitialChars->clear();
   2626                 fRXPat->fInitialChars->complement();
   2627                 numInitialStrings += 2;
   2628             }
   2629             currentLen++;
   2630             atStart = FALSE;
   2631             break;
   2632 
   2633 
   2634         case URX_JMPX:
   2635             loc++;             // Except for extra operand on URX_JMPX, same as URX_JMP.
   2636         case URX_JMP:
   2637             {
   2638                 int32_t  jmpDest = URX_VAL(op);
   2639                 if (jmpDest < loc) {
   2640                     // Loop of some kind.  Can safely ignore, the worst that will happen
   2641                     //  is that we understate the true minimum length
   2642                     currentLen = forwardedLength.elementAti(loc+1);
   2643 
   2644                 } else {
   2645                     // Forward jump.  Propagate the current min length to the target loc of the jump.
   2646                     U_ASSERT(jmpDest <= end+1);
   2647                     if (forwardedLength.elementAti(jmpDest) > currentLen) {
   2648                         forwardedLength.setElementAt(currentLen, jmpDest);
   2649                     }
   2650                 }
   2651             }
   2652             atStart = FALSE;
   2653             break;
   2654 
   2655         case URX_JMP_SAV:
   2656         case URX_JMP_SAV_X:
   2657             // Combo of state save to the next loc, + jmp backwards.
   2658             //   Net effect on min. length computation is nothing.
   2659             atStart = FALSE;
   2660             break;
   2661 
   2662         case URX_BACKTRACK:
   2663             // Fails are kind of like a branch, except that the min length was
   2664             //   propagated already, by the state save.
   2665             currentLen = forwardedLength.elementAti(loc+1);
   2666             atStart = FALSE;
   2667             break;
   2668 
   2669 
   2670         case URX_STATE_SAVE:
   2671             {
   2672                 // State Save, for forward jumps, propagate the current minimum.
   2673                 //             of the state save.
   2674                 int32_t  jmpDest = URX_VAL(op);
   2675                 if (jmpDest > loc) {
   2676                     if (currentLen < forwardedLength.elementAti(jmpDest)) {
   2677                         forwardedLength.setElementAt(currentLen, jmpDest);
   2678                     }
   2679                 }
   2680             }
   2681             atStart = FALSE;
   2682             break;
   2683 
   2684 
   2685 
   2686 
   2687         case URX_STRING:
   2688             {
   2689                 loc++;
   2690                 int32_t stringLenOp = (int32_t)fRXPat->fCompiledPat->elementAti(loc);
   2691                 int32_t stringLen   = URX_VAL(stringLenOp);
   2692                 U_ASSERT(URX_TYPE(stringLenOp) == URX_STRING_LEN);
   2693                 U_ASSERT(stringLenOp >= 2);
   2694                 if (currentLen == 0) {
   2695                     // Add the starting character of this string to the set of possible starting
   2696                     //   characters for this pattern.
   2697                     int32_t stringStartIdx = URX_VAL(op);
   2698                     UChar32  c = fRXPat->fLiteralText.char32At(stringStartIdx);
   2699                     fRXPat->fInitialChars->add(c);
   2700 
   2701                     // Remember this string.  After the entire pattern has been checked,
   2702                     //  if nothing else is identified that can start a match, we'll use it.
   2703                     numInitialStrings++;
   2704                     fRXPat->fInitialStringIdx = stringStartIdx;
   2705                     fRXPat->fInitialStringLen = stringLen;
   2706                 }
   2707 
   2708                 currentLen += stringLen;
   2709                 atStart = FALSE;
   2710             }
   2711             break;
   2712 
   2713         case URX_STRING_I:
   2714             {
   2715                 // Case-insensitive string.  Unlike exact-match strings, we won't
   2716                 //   attempt a string search for possible match positions.  But we
   2717                 //   do update the set of possible starting characters.
   2718                 loc++;
   2719                 int32_t stringLenOp = (int32_t)fRXPat->fCompiledPat->elementAti(loc);
   2720                 int32_t stringLen   = URX_VAL(stringLenOp);
   2721                 U_ASSERT(URX_TYPE(stringLenOp) == URX_STRING_LEN);
   2722                 U_ASSERT(stringLenOp >= 2);
   2723                 if (currentLen == 0) {
   2724                     // Add the starting character of this string to the set of possible starting
   2725                     //   characters for this pattern.
   2726                     int32_t stringStartIdx = URX_VAL(op);
   2727                     UChar32  c = fRXPat->fLiteralText.char32At(stringStartIdx);
   2728                     UnicodeSet s(c, c);
   2729                     s.closeOver(USET_CASE_INSENSITIVE);
   2730                     fRXPat->fInitialChars->addAll(s);
   2731                     numInitialStrings += 2;  // Matching on an initial string not possible.
   2732                 }
   2733                 currentLen += stringLen;
   2734                 atStart = FALSE;
   2735             }
   2736             break;
   2737 
   2738         case URX_CTR_INIT:
   2739         case URX_CTR_INIT_NG:
   2740             {
   2741                 // Loop Init Ops.  These don't change the min length, but they are 4 word ops
   2742                 //   so location must be updated accordingly.
   2743                 // Loop Init Ops.
   2744                 //   If the min loop count == 0
   2745                 //      move loc forwards to the end of the loop, skipping over the body.
   2746                 //   If the min count is > 0,
   2747                 //      continue normal processing of the body of the loop.
   2748                 int32_t loopEndLoc   = (int32_t)fRXPat->fCompiledPat->elementAti(loc+1);
   2749                         loopEndLoc   = URX_VAL(loopEndLoc);
   2750                 int32_t minLoopCount = (int32_t)fRXPat->fCompiledPat->elementAti(loc+2);
   2751                 if (minLoopCount == 0) {
   2752                     // Min Loop Count of 0, treat like a forward branch and
   2753                     //   move the current minimum length up to the target
   2754                     //   (end of loop) location.
   2755                     U_ASSERT(loopEndLoc <= end+1);
   2756                     if (forwardedLength.elementAti(loopEndLoc) > currentLen) {
   2757                         forwardedLength.setElementAt(currentLen, loopEndLoc);
   2758                     }
   2759                 }
   2760                 loc+=3;  // Skips over operands of CTR_INIT
   2761             }
   2762             atStart = FALSE;
   2763             break;
   2764 
   2765 
   2766         case URX_CTR_LOOP:
   2767         case URX_CTR_LOOP_NG:
   2768             // Loop ops.
   2769             //  The jump is conditional, backwards only.
   2770             atStart = FALSE;
   2771             break;
   2772 
   2773         case URX_LOOP_C:
   2774             // More loop ops.  These state-save to themselves.
   2775             //   don't change the minimum match
   2776             atStart = FALSE;
   2777             break;
   2778 
   2779 
   2780         case URX_LA_START:
   2781         case URX_LB_START:
   2782             {
   2783                 // Look-around.  Scan forward until the matching look-ahead end,
   2784                 //   without processing the look-around block.  This is overly pessimistic.
   2785 
   2786                 // Keep track of the nesting depth of look-around blocks.  Boilerplate code for
   2787                 //   lookahead contains two LA_END instructions, so count goes up by two
   2788                 //   for each LA_START.
   2789                 int32_t  depth = (opType == URX_LA_START? 2: 1);
   2790                 for (;;) {
   2791                     loc++;
   2792                     op = (int32_t)fRXPat->fCompiledPat->elementAti(loc);
   2793                     if (URX_TYPE(op) == URX_LA_START) {
   2794                         depth+=2;
   2795                     }
   2796                     if (URX_TYPE(op) == URX_LB_START) {
   2797                         depth++;
   2798                     }
   2799                     if (URX_TYPE(op) == URX_LA_END || URX_TYPE(op)==URX_LBN_END) {
   2800                         depth--;
   2801                         if (depth == 0) {
   2802                             break;
   2803                         }
   2804                     }
   2805                     if (URX_TYPE(op) == URX_STATE_SAVE) {
   2806                         // Need this because neg lookahead blocks will FAIL to outside
   2807                         //   of the block.
   2808                         int32_t  jmpDest = URX_VAL(op);
   2809                         if (jmpDest > loc) {
   2810                             if (currentLen < forwardedLength.elementAti(jmpDest)) {
   2811                                 forwardedLength.setElementAt(currentLen, jmpDest);
   2812                             }
   2813                         }
   2814                     }
   2815                     U_ASSERT(loc <= end);
   2816                 }
   2817             }
   2818             break;
   2819 
   2820         case URX_LA_END:
   2821         case URX_LB_CONT:
   2822         case URX_LB_END:
   2823         case URX_LBN_CONT:
   2824         case URX_LBN_END:
   2825             U_ASSERT(FALSE);     // Shouldn't get here.  These ops should be
   2826                                  //  consumed by the scan in URX_LA_START and LB_START
   2827 
   2828             break;
   2829 
   2830         default:
   2831             U_ASSERT(FALSE);
   2832             }
   2833 
   2834         }
   2835 
   2836 
   2837     // We have finished walking through the ops.  Check whether some forward jump
   2838     //   propagated a shorter length to location end+1.
   2839     if (forwardedLength.elementAti(end+1) < currentLen) {
   2840         currentLen = forwardedLength.elementAti(end+1);
   2841     }
   2842 
   2843 
   2844     fRXPat->fInitialChars8->init(fRXPat->fInitialChars);
   2845 
   2846 
   2847     // Sort out what we should check for when looking for candidate match start positions.
   2848     // In order of preference,
   2849     //     1.   Start of input text buffer.
   2850     //     2.   A literal string.
   2851     //     3.   Start of line in multi-line mode.
   2852     //     4.   A single literal character.
   2853     //     5.   A character from a set of characters.
   2854     //
   2855     if (fRXPat->fStartType == START_START) {
   2856         // Match only at the start of an input text string.
   2857         //    start type is already set.  We're done.
   2858     } else if (numInitialStrings == 1 && fRXPat->fMinMatchLen > 0) {
   2859         // Match beginning only with a literal string.
   2860         UChar32  c = fRXPat->fLiteralText.char32At(fRXPat->fInitialStringIdx);
   2861         U_ASSERT(fRXPat->fInitialChars->contains(c));
   2862         fRXPat->fStartType   = START_STRING;
   2863         fRXPat->fInitialChar = c;
   2864     } else if (fRXPat->fStartType == START_LINE) {
   2865         // Match at start of line in Multi-Line mode.
   2866         // Nothing to do here; everything is already set.
   2867     } else if (fRXPat->fMinMatchLen == 0) {
   2868         // Zero length match possible.  We could start anywhere.
   2869         fRXPat->fStartType = START_NO_INFO;
   2870     } else if (fRXPat->fInitialChars->size() == 1) {
   2871         // All matches begin with the same char.
   2872         fRXPat->fStartType   = START_CHAR;
   2873         fRXPat->fInitialChar = fRXPat->fInitialChars->charAt(0);
   2874         U_ASSERT(fRXPat->fInitialChar != (UChar32)-1);
   2875     } else if (fRXPat->fInitialChars->contains((UChar32)0, (UChar32)0x10ffff) == FALSE &&
   2876         fRXPat->fMinMatchLen > 0) {
   2877         // Matches start with a set of character smaller than the set of all chars.
   2878         fRXPat->fStartType = START_SET;
   2879     } else {
   2880         // Matches can start with anything
   2881         fRXPat->fStartType = START_NO_INFO;
   2882     }
   2883 
   2884     return;
   2885 }
   2886 
   2887 
   2888 
   2889 //------------------------------------------------------------------------------
   2890 //
   2891 //   minMatchLength    Calculate the length of the shortest string that could
   2892 //                     match the specified pattern.
   2893 //                     Length is in 16 bit code units, not code points.
   2894 //
   2895 //                     The calculated length may not be exact.  The returned
   2896 //                     value may be shorter than the actual minimum; it must
   2897 //                     never be longer.
   2898 //
   2899 //                     start and end are the range of p-code operations to be
   2900 //                     examined.  The endpoints are included in the range.
   2901 //
   2902 //------------------------------------------------------------------------------
   2903 int32_t   RegexCompile::minMatchLength(int32_t start, int32_t end) {
   2904     if (U_FAILURE(*fStatus)) {
   2905         return 0;
   2906     }
   2907 
   2908     U_ASSERT(start <= end);
   2909     U_ASSERT(end < fRXPat->fCompiledPat->size());
   2910 
   2911 
   2912     int32_t    loc;
   2913     int32_t    op;
   2914     int32_t    opType;
   2915     int32_t    currentLen = 0;
   2916 
   2917 
   2918     // forwardedLength is a vector holding minimum-match-length values that
   2919     //   are propagated forward in the pattern by JMP or STATE_SAVE operations.
   2920     //   It must be one longer than the pattern being checked because some  ops
   2921     //   will jmp to a end-of-block+1 location from within a block, and we must
   2922     //   count those when checking the block.
   2923     UVector32  forwardedLength(end+2, *fStatus);
   2924     forwardedLength.setSize(end+2);
   2925     for (loc=start; loc<=end+1; loc++) {
   2926         forwardedLength.setElementAt(INT32_MAX, loc);
   2927     }
   2928 
   2929     for (loc = start; loc<=end; loc++) {
   2930         op = (int32_t)fRXPat->fCompiledPat->elementAti(loc);
   2931         opType = URX_TYPE(op);
   2932 
   2933         // The loop is advancing linearly through the pattern.
   2934         // If the op we are now at was the destination of a branch in the pattern,
   2935         // and that path has a shorter minimum length than the current accumulated value,
   2936         // replace the current accumulated value.
   2937         // U_ASSERT(currentLen>=0 && currentLen < INT32_MAX);  // MinLength == INT32_MAX for some
   2938                                                                //   no-match-possible cases.
   2939         if (forwardedLength.elementAti(loc) < currentLen) {
   2940             currentLen = forwardedLength.elementAti(loc);
   2941             U_ASSERT(currentLen>=0 && currentLen < INT32_MAX);
   2942         }
   2943 
   2944         switch (opType) {
   2945             // Ops that don't change the total length matched
   2946         case URX_RESERVED_OP:
   2947         case URX_END:
   2948         case URX_STRING_LEN:
   2949         case URX_NOP:
   2950         case URX_START_CAPTURE:
   2951         case URX_END_CAPTURE:
   2952         case URX_BACKSLASH_B:
   2953         case URX_BACKSLASH_BU:
   2954         case URX_BACKSLASH_G:
   2955         case URX_BACKSLASH_Z:
   2956         case URX_CARET:
   2957         case URX_DOLLAR:
   2958         case URX_DOLLAR_M:
   2959         case URX_DOLLAR_D:
   2960         case URX_DOLLAR_MD:
   2961         case URX_RELOC_OPRND:
   2962         case URX_STO_INP_LOC:
   2963         case URX_CARET_M:
   2964         case URX_CARET_M_UNIX:
   2965         case URX_BACKREF:         // BackRef.  Must assume that it might be a zero length match
   2966         case URX_BACKREF_I:
   2967 
   2968         case URX_STO_SP:          // Setup for atomic or possessive blocks.  Doesn't change what can match.
   2969         case URX_LD_SP:
   2970 
   2971         case URX_JMP_SAV:
   2972         case URX_JMP_SAV_X:
   2973             break;
   2974 
   2975 
   2976             // Ops that match a minimum of one character (one or two 16 bit code units.)
   2977             //
   2978         case URX_ONECHAR:
   2979         case URX_STATIC_SETREF:
   2980         case URX_STAT_SETREF_N:
   2981         case URX_SETREF:
   2982         case URX_BACKSLASH_D:
   2983         case URX_ONECHAR_I:
   2984         case URX_BACKSLASH_X:   // Grahpeme Cluster.  Minimum is 1, max unbounded.
   2985         case URX_DOTANY_ALL:    // . matches one or two.
   2986         case URX_DOTANY:
   2987         case URX_DOTANY_UNIX:
   2988             currentLen++;
   2989             break;
   2990 
   2991 
   2992         case URX_JMPX:
   2993             loc++;              // URX_JMPX has an extra operand, ignored here,
   2994                                 //   otherwise processed identically to URX_JMP.
   2995         case URX_JMP:
   2996             {
   2997                 int32_t  jmpDest = URX_VAL(op);
   2998                 if (jmpDest < loc) {
   2999                     // Loop of some kind.  Can safely ignore, the worst that will happen
   3000                     //  is that we understate the true minimum length
   3001                     currentLen = forwardedLength.elementAti(loc+1);
   3002                 } else {
   3003                     // Forward jump.  Propagate the current min length to the target loc of the jump.
   3004                     U_ASSERT(jmpDest <= end+1);
   3005                     if (forwardedLength.elementAti(jmpDest) > currentLen) {
   3006                         forwardedLength.setElementAt(currentLen, jmpDest);
   3007                     }
   3008                 }
   3009             }
   3010             break;
   3011 
   3012         case URX_BACKTRACK:
   3013             {
   3014                 // Back-tracks are kind of like a branch, except that the min length was
   3015                 //   propagated already, by the state save.
   3016                 currentLen = forwardedLength.elementAti(loc+1);
   3017             }
   3018             break;
   3019 
   3020 
   3021         case URX_STATE_SAVE:
   3022             {
   3023                 // State Save, for forward jumps, propagate the current minimum.
   3024                 //             of the state save.
   3025                 int32_t  jmpDest = URX_VAL(op);
   3026                 if (jmpDest > loc) {
   3027                     if (currentLen < forwardedLength.elementAti(jmpDest)) {
   3028                         forwardedLength.setElementAt(currentLen, jmpDest);
   3029                     }
   3030                 }
   3031             }
   3032             break;
   3033 
   3034 
   3035         case URX_STRING:
   3036         case URX_STRING_I:
   3037             {
   3038                 loc++;
   3039                 int32_t stringLenOp = (int32_t)fRXPat->fCompiledPat->elementAti(loc);
   3040                 currentLen += URX_VAL(stringLenOp);
   3041             }
   3042             break;
   3043 
   3044 
   3045         case URX_CTR_INIT:
   3046         case URX_CTR_INIT_NG:
   3047             {
   3048                 // Loop Init Ops.
   3049                 //   If the min loop count == 0
   3050                 //      move loc forwards to the end of the loop, skipping over the body.
   3051                 //   If the min count is > 0,
   3052                 //      continue normal processing of the body of the loop.
   3053                 int32_t loopEndLoc   = (int32_t)fRXPat->fCompiledPat->elementAti(loc+1);
   3054                         loopEndLoc   = URX_VAL(loopEndLoc);
   3055                 int32_t minLoopCount = (int32_t)fRXPat->fCompiledPat->elementAti(loc+2);
   3056                 if (minLoopCount == 0) {
   3057                     loc = loopEndLoc;
   3058                 } else {
   3059                     loc+=3;  // Skips over operands of CTR_INIT
   3060                 }
   3061             }
   3062             break;
   3063 
   3064 
   3065         case URX_CTR_LOOP:
   3066         case URX_CTR_LOOP_NG:
   3067             // Loop ops.
   3068             //  The jump is conditional, backwards only.
   3069             break;
   3070 
   3071         case URX_LOOP_SR_I:
   3072         case URX_LOOP_DOT_I:
   3073         case URX_LOOP_C:
   3074             // More loop ops.  These state-save to themselves.
   3075             //   don't change the minimum match - could match nothing at all.
   3076             break;
   3077 
   3078 
   3079         case URX_LA_START:
   3080         case URX_LB_START:
   3081             {
   3082                 // Look-around.  Scan forward until the matching look-ahead end,
   3083                 //   without processing the look-around block.  This is overly pessimistic for look-ahead,
   3084                 //   it assumes that the look-ahead match might be zero-length.
   3085                 //   TODO:  Positive lookahead could recursively do the block, then continue
   3086                 //          with the longer of the block or the value coming in.  Ticket 6060
   3087                 int32_t  depth = (opType == URX_LA_START? 2: 1);;
   3088                 for (;;) {
   3089                     loc++;
   3090                     op = (int32_t)fRXPat->fCompiledPat->elementAti(loc);
   3091                     if (URX_TYPE(op) == URX_LA_START) {
   3092                         // The boilerplate for look-ahead includes two LA_END insturctions,
   3093                         //    Depth will be decremented by each one when it is seen.
   3094                         depth += 2;
   3095                     }
   3096                     if (URX_TYPE(op) == URX_LB_START) {
   3097                         depth++;
   3098                     }
   3099                     if (URX_TYPE(op) == URX_LA_END) {
   3100                         depth--;
   3101                         if (depth == 0) {
   3102                             break;
   3103                         }
   3104                     }
   3105                     if (URX_TYPE(op)==URX_LBN_END) {
   3106                         depth--;
   3107                         if (depth == 0) {
   3108                             break;
   3109                         }
   3110                     }
   3111                     if (URX_TYPE(op) == URX_STATE_SAVE) {
   3112                         // Need this because neg lookahead blocks will FAIL to outside
   3113                         //   of the block.
   3114                         int32_t  jmpDest = URX_VAL(op);
   3115                         if (jmpDest > loc) {
   3116                             if (currentLen < forwardedLength.elementAti(jmpDest)) {
   3117                                 forwardedLength.setElementAt(currentLen, jmpDest);
   3118                             }
   3119                         }
   3120                     }
   3121                     U_ASSERT(loc <= end);
   3122                 }
   3123             }
   3124             break;
   3125 
   3126         case URX_LA_END:
   3127         case URX_LB_CONT:
   3128         case URX_LB_END:
   3129         case URX_LBN_CONT:
   3130         case URX_LBN_END:
   3131             // Only come here if the matching URX_LA_START or URX_LB_START was not in the
   3132             //   range being sized, which happens when measuring size of look-behind blocks.
   3133             break;
   3134 
   3135         default:
   3136             U_ASSERT(FALSE);
   3137             }
   3138 
   3139         }
   3140 
   3141     // We have finished walking through the ops.  Check whether some forward jump
   3142     //   propagated a shorter length to location end+1.
   3143     if (forwardedLength.elementAti(end+1) < currentLen) {
   3144         currentLen = forwardedLength.elementAti(end+1);
   3145         U_ASSERT(currentLen>=0 && currentLen < INT32_MAX);
   3146     }
   3147 
   3148     return currentLen;
   3149 }
   3150 
   3151 
   3152 
   3153 //------------------------------------------------------------------------------
   3154 //
   3155 //   maxMatchLength    Calculate the length of the longest string that could
   3156 //                     match the specified pattern.
   3157 //                     Length is in 16 bit code units, not code points.
   3158 //
   3159 //                     The calculated length may not be exact.  The returned
   3160 //                     value may be longer than the actual maximum; it must
   3161 //                     never be shorter.
   3162 //
   3163 //------------------------------------------------------------------------------
   3164 int32_t   RegexCompile::maxMatchLength(int32_t start, int32_t end) {
   3165     if (U_FAILURE(*fStatus)) {
   3166         return 0;
   3167     }
   3168     U_ASSERT(start <= end);
   3169     U_ASSERT(end < fRXPat->fCompiledPat->size());
   3170 
   3171 
   3172     int32_t    loc;
   3173     int32_t    op;
   3174     int32_t    opType;
   3175     int32_t    currentLen = 0;
   3176     UVector32  forwardedLength(end+1, *fStatus);
   3177     forwardedLength.setSize(end+1);
   3178 
   3179     for (loc=start; loc<=end; loc++) {
   3180         forwardedLength.setElementAt(0, loc);
   3181     }
   3182 
   3183     for (loc = start; loc<=end; loc++) {
   3184         op = (int32_t)fRXPat->fCompiledPat->elementAti(loc);
   3185         opType = URX_TYPE(op);
   3186 
   3187         // The loop is advancing linearly through the pattern.
   3188         // If the op we are now at was the destination of a branch in the pattern,
   3189         // and that path has a longer maximum length than the current accumulated value,
   3190         // replace the current accumulated value.
   3191         if (forwardedLength.elementAti(loc) > currentLen) {
   3192             currentLen = forwardedLength.elementAti(loc);
   3193         }
   3194 
   3195         switch (opType) {
   3196             // Ops that don't change the total length matched
   3197         case URX_RESERVED_OP:
   3198         case URX_END:
   3199         case URX_STRING_LEN:
   3200         case URX_NOP:
   3201         case URX_START_CAPTURE:
   3202         case URX_END_CAPTURE:
   3203         case URX_BACKSLASH_B:
   3204         case URX_BACKSLASH_BU:
   3205         case URX_BACKSLASH_G:
   3206         case URX_BACKSLASH_Z:
   3207         case URX_CARET:
   3208         case URX_DOLLAR:
   3209         case URX_DOLLAR_M:
   3210         case URX_DOLLAR_D:
   3211         case URX_DOLLAR_MD:
   3212         case URX_RELOC_OPRND:
   3213         case URX_STO_INP_LOC:
   3214         case URX_CARET_M:
   3215         case URX_CARET_M_UNIX:
   3216 
   3217         case URX_STO_SP:          // Setup for atomic or possessive blocks.  Doesn't change what can match.
   3218         case URX_LD_SP:
   3219 
   3220         case URX_LB_END:
   3221         case URX_LB_CONT:
   3222         case URX_LBN_CONT:
   3223         case URX_LBN_END:
   3224             break;
   3225 
   3226 
   3227             // Ops that increase that cause an unbounded increase in the length
   3228             //   of a matched string, or that increase it a hard to characterize way.
   3229             //   Call the max length unbounded, and stop further checking.
   3230         case URX_BACKREF:         // BackRef.  Must assume that it might be a zero length match
   3231         case URX_BACKREF_I:
   3232         case URX_BACKSLASH_X:   // Grahpeme Cluster.  Minimum is 1, max unbounded.
   3233             currentLen = INT32_MAX;
   3234             break;
   3235 
   3236 
   3237             // Ops that match a max of one character (possibly two 16 bit code units.)
   3238             //
   3239         case URX_STATIC_SETREF:
   3240         case URX_STAT_SETREF_N:
   3241         case URX_SETREF:
   3242         case URX_BACKSLASH_D:
   3243         case URX_ONECHAR_I:
   3244         case URX_DOTANY_ALL:
   3245         case URX_DOTANY:
   3246         case URX_DOTANY_UNIX:
   3247             currentLen+=2;
   3248             break;
   3249 
   3250             // Single literal character.  Increase current max length by one or two,
   3251             //       depending on whether the char is in the supplementary range.
   3252         case URX_ONECHAR:
   3253             currentLen++;
   3254             if (URX_VAL(op) > 0x10000) {
   3255                 currentLen++;
   3256             }
   3257             break;
   3258 
   3259             // Jumps.
   3260             //
   3261         case URX_JMP:
   3262         case URX_JMPX:
   3263         case URX_JMP_SAV:
   3264         case URX_JMP_SAV_X:
   3265             {
   3266                 int32_t  jmpDest = URX_VAL(op);
   3267                 if (jmpDest < loc) {
   3268                     // Loop of some kind.  Max match length is unbounded.
   3269                     currentLen = INT32_MAX;
   3270                 } else {
   3271                     // Forward jump.  Propagate the current min length to the target loc of the jump.
   3272                     if (forwardedLength.elementAti(jmpDest) < currentLen) {
   3273                         forwardedLength.setElementAt(currentLen, jmpDest);
   3274                     }
   3275                     currentLen = 0;
   3276                 }
   3277             }
   3278             break;
   3279 
   3280         case URX_BACKTRACK:
   3281             // back-tracks are kind of like a branch, except that the max length was
   3282             //   propagated already, by the state save.
   3283             currentLen = forwardedLength.elementAti(loc+1);
   3284             break;
   3285 
   3286 
   3287         case URX_STATE_SAVE:
   3288             {
   3289                 // State Save, for forward jumps, propagate the current minimum.
   3290                 //               of the state save.
   3291                 //             For backwards jumps, they create a loop, maximum
   3292                 //               match length is unbounded.
   3293                 int32_t  jmpDest = URX_VAL(op);
   3294                 if (jmpDest > loc) {
   3295                     if (currentLen > forwardedLength.elementAti(jmpDest)) {
   3296                         forwardedLength.setElementAt(currentLen, jmpDest);
   3297                     }
   3298                 } else {
   3299                     currentLen = INT32_MAX;
   3300                 }
   3301             }
   3302             break;
   3303 
   3304 
   3305 
   3306 
   3307         case URX_STRING:
   3308         case URX_STRING_I:
   3309             {
   3310                 loc++;
   3311                 int32_t stringLenOp = (int32_t)fRXPat->fCompiledPat->elementAti(loc);
   3312                 currentLen += URX_VAL(stringLenOp);
   3313             }
   3314             break;
   3315 
   3316 
   3317         case URX_CTR_INIT:
   3318         case URX_CTR_INIT_NG:
   3319         case URX_CTR_LOOP:
   3320         case URX_CTR_LOOP_NG:
   3321         case URX_LOOP_SR_I:
   3322         case URX_LOOP_DOT_I:
   3323         case URX_LOOP_C:
   3324             // For anything to do with loops, make the match length unbounded.
   3325             //   Note:  INIT instructions are multi-word.  Can ignore because
   3326             //          INT32_MAX length will stop the per-instruction loop.
   3327             currentLen = INT32_MAX;
   3328             break;
   3329 
   3330 
   3331 
   3332         case URX_LA_START:
   3333         case URX_LA_END:
   3334             // Look-ahead.  Just ignore, treat the look-ahead block as if
   3335             // it were normal pattern.  Gives a too-long match length,
   3336             //  but good enough for now.
   3337             break;
   3338 
   3339             // End of look-ahead ops should always be consumed by the processing at
   3340             //  the URX_LA_START op.
   3341             // U_ASSERT(FALSE);
   3342             // break;
   3343 
   3344         case URX_LB_START:
   3345             {
   3346                 // Look-behind.  Scan forward until the matching look-around end,
   3347                 //   without processing the look-behind block.
   3348                 int32_t  depth = 0;
   3349                 for (;;) {
   3350                     loc++;
   3351                     op = (int32_t)fRXPat->fCompiledPat->elementAti(loc);
   3352                     if (URX_TYPE(op) == URX_LA_START || URX_TYPE(op) == URX_LB_START) {
   3353                         depth++;
   3354                     }
   3355                     if (URX_TYPE(op) == URX_LA_END || URX_TYPE(op)==URX_LBN_END) {
   3356                         if (depth == 0) {
   3357                             break;
   3358                         }
   3359                         depth--;
   3360                     }
   3361                     U_ASSERT(loc < end);
   3362                 }
   3363             }
   3364             break;
   3365 
   3366         default:
   3367             U_ASSERT(FALSE);
   3368         }
   3369 
   3370 
   3371         if (currentLen == INT32_MAX) {
   3372             //  The maximum length is unbounded.
   3373             //  Stop further processing of the pattern.
   3374             break;
   3375         }
   3376 
   3377     }
   3378     return currentLen;
   3379 
   3380 }
   3381 
   3382 
   3383 //------------------------------------------------------------------------------
   3384 //
   3385 //   stripNOPs    Remove any NOP operations from the compiled pattern code.
   3386 //                Extra NOPs are inserted for some constructs during the initial
   3387 //                code generation to provide locations that may be patched later.
   3388 //                Many end up unneeded, and are removed by this function.
   3389 //
   3390 //                In order to minimize the number of passes through the pattern,
   3391 //                back-reference fixup is also performed here (adjusting
   3392 //                back-reference operands to point to the correct frame offsets).
   3393 //
   3394 //                In addition, case-insensitive character and string literals are
   3395 //                now case-folded here, rather than when first parsed or at match
   3396 //                time.
   3397 //
   3398 //------------------------------------------------------------------------------
   3399 void RegexCompile::stripNOPs() {
   3400 
   3401     if (U_FAILURE(*fStatus)) {
   3402         return;
   3403     }
   3404 
   3405     int32_t    end = fRXPat->fCompiledPat->size();
   3406     UVector32  deltas(end, *fStatus);
   3407 
   3408     // Make a first pass over the code, computing the amount that things
   3409     //   will be offset at each location in the original code.
   3410     int32_t   loc;
   3411     int32_t   d = 0;
   3412     for (loc=0; loc<end; loc++) {
   3413         deltas.addElement(d, *fStatus);
   3414         int32_t op = (int32_t)fRXPat->fCompiledPat->elementAti(loc);
   3415         if (URX_TYPE(op) == URX_NOP) {
   3416             d++;
   3417         }
   3418     }
   3419 
   3420     UnicodeString caseStringBuffer;
   3421     int32_t stringDelta = 0;
   3422 
   3423     // Make a second pass over the code, removing the NOPs by moving following
   3424     //  code up, and patching operands that refer to code locations that
   3425     //  are being moved.  The array of offsets from the first step is used
   3426     //  to compute the new operand values.
   3427     int32_t src;
   3428     int32_t dst = 0;
   3429     for (src=0; src<end; src++) {
   3430         int32_t op = (int32_t)fRXPat->fCompiledPat->elementAti(src);
   3431         int32_t opType = URX_TYPE(op);
   3432         switch (opType) {
   3433         case URX_NOP:
   3434             break;
   3435 
   3436         case URX_STATE_SAVE:
   3437         case URX_JMP:
   3438         case URX_CTR_LOOP:
   3439         case URX_CTR_LOOP_NG:
   3440         case URX_RELOC_OPRND:
   3441         case URX_JMPX:
   3442         case URX_JMP_SAV:
   3443         case URX_JMP_SAV_X:
   3444             // These are instructions with operands that refer to code locations.
   3445             {
   3446                 int32_t  operandAddress = URX_VAL(op);
   3447                 U_ASSERT(operandAddress>=0 && operandAddress<deltas.size());
   3448                 int32_t fixedOperandAddress = operandAddress - deltas.elementAti(operandAddress);
   3449                 op = URX_BUILD(opType, fixedOperandAddress);
   3450                 fRXPat->fCompiledPat->setElementAt(op, dst);
   3451                 dst++;
   3452                 break;
   3453             }
   3454 
   3455         case URX_ONECHAR_I:
   3456             {
   3457                 UChar32 c = URX_VAL(op);
   3458                 if (u_hasBinaryProperty(c, UCHAR_CASE_SENSITIVE)) {
   3459                     // We have a cased character to fold
   3460                     c  = u_foldCase(c, U_FOLD_CASE_DEFAULT);
   3461                     op = URX_BUILD(URX_ONECHAR_I, c);
   3462                 }
   3463 
   3464                 fRXPat->fCompiledPat->setElementAt(op, dst);
   3465                 dst++;
   3466                 break;
   3467             }
   3468         case URX_STRING_I:
   3469             {
   3470                 op = URX_BUILD(URX_STRING_I, URX_VAL(op)+stringDelta);
   3471 
   3472                 src++;
   3473                 int32_t lengthOp = (int32_t)fRXPat->fCompiledPat->elementAti(src);
   3474 
   3475                 caseStringBuffer.setTo(fRXPat->fLiteralText, URX_VAL(op), URX_VAL(lengthOp));
   3476                 caseStringBuffer.foldCase(U_FOLD_CASE_DEFAULT);
   3477 
   3478                 int32_t newLen = caseStringBuffer.length();
   3479                 if (newLen <= URX_VAL(lengthOp)) {
   3480                     // don't shift if we don't have to, take the tiny memory hit of a smaller string
   3481                     fRXPat->fLiteralText.replace(URX_VAL(op), newLen, caseStringBuffer);
   3482                 } else {
   3483                     // shift other strings over...at least UnicodeString handles this for us!
   3484                     fRXPat->fLiteralText.replace(URX_VAL(op), URX_VAL(lengthOp), caseStringBuffer);
   3485                     stringDelta += newLen - URX_VAL(lengthOp);
   3486                 }
   3487                 lengthOp = URX_BUILD(URX_STRING_LEN, newLen);
   3488 
   3489                 fRXPat->fCompiledPat->setElementAt(op, dst);
   3490                 fRXPat->fCompiledPat->setElementAt(lengthOp, dst+1);
   3491                 dst += 2;
   3492                 break;
   3493             }
   3494         case URX_BACKREF:
   3495         case URX_BACKREF_I:
   3496             {
   3497                 int32_t where = URX_VAL(op);
   3498                 if (where > fRXPat->fGroupMap->size()) {
   3499                     error(U_REGEX_INVALID_BACK_REF);
   3500                     break;
   3501                 }
   3502                 where = fRXPat->fGroupMap->elementAti(where-1);
   3503                 op    = URX_BUILD(opType, where);
   3504                 fRXPat->fCompiledPat->setElementAt(op, dst);
   3505                 dst++;
   3506 
   3507                 fRXPat->fNeedsAltInput = TRUE;
   3508                 break;
   3509             }
   3510         case URX_STRING:
   3511             op = URX_BUILD(URX_STRING, URX_VAL(op)+stringDelta);
   3512             // continue
   3513         case URX_RESERVED_OP:
   3514         case URX_RESERVED_OP_N:
   3515         case URX_BACKTRACK:
   3516         case URX_END:
   3517         case URX_ONECHAR:
   3518         case URX_STRING_LEN:
   3519         case URX_START_CAPTURE:
   3520         case URX_END_CAPTURE:
   3521         case URX_STATIC_SETREF:
   3522         case URX_STAT_SETREF_N:
   3523         case URX_SETREF:
   3524         case URX_DOTANY:
   3525         case URX_FAIL:
   3526         case URX_BACKSLASH_B:
   3527         case URX_BACKSLASH_BU:
   3528         case URX_BACKSLASH_G:
   3529         case URX_BACKSLASH_X:
   3530         case URX_BACKSLASH_Z:
   3531         case URX_DOTANY_ALL:
   3532         case URX_BACKSLASH_D:
   3533         case URX_CARET:
   3534         case URX_DOLLAR:
   3535         case URX_CTR_INIT:
   3536         case URX_CTR_INIT_NG:
   3537         case URX_DOTANY_UNIX:
   3538         case URX_STO_SP:
   3539         case URX_LD_SP:
   3540         case URX_STO_INP_LOC:
   3541         case URX_LA_START:
   3542         case URX_LA_END:
   3543         case URX_DOLLAR_M:
   3544         case URX_CARET_M:
   3545         case URX_CARET_M_UNIX:
   3546         case URX_LB_START:
   3547         case URX_LB_CONT:
   3548         case URX_LB_END:
   3549         case URX_LBN_CONT:
   3550         case URX_LBN_END:
   3551         case URX_LOOP_SR_I:
   3552         case URX_LOOP_DOT_I:
   3553         case URX_LOOP_C:
   3554         case URX_DOLLAR_D:
   3555         case URX_DOLLAR_MD:
   3556             // These instructions are unaltered by the relocation.
   3557             fRXPat->fCompiledPat->setElementAt(op, dst);
   3558             dst++;
   3559             break;
   3560 
   3561         default:
   3562             // Some op is unaccounted for.
   3563             U_ASSERT(FALSE);
   3564             error(U_REGEX_INTERNAL_ERROR);
   3565         }
   3566     }
   3567 
   3568     fRXPat->fCompiledPat->setSize(dst);
   3569 }
   3570 
   3571 
   3572 
   3573 
   3574 //------------------------------------------------------------------------------
   3575 //
   3576 //  Error         Report a rule parse error.
   3577 //                Only report it if no previous error has been recorded.
   3578 //
   3579 //------------------------------------------------------------------------------
   3580 void RegexCompile::error(UErrorCode e) {
   3581     if (U_SUCCESS(*fStatus)) {
   3582         *fStatus = e;
   3583         // Hmm. fParseErr (UParseError) line & offset fields are int32_t in public
   3584         // API (see common/unicode/parseerr.h), while fLineNum and fCharNum are
   3585         // int64_t. If the values of the latter are out of range for the former,
   3586         // set them to the appropriate "field not supported" values.
   3587         if (fLineNum > 0x7FFFFFFF) {
   3588             fParseErr->line   = 0;
   3589             fParseErr->offset = -1;
   3590         } else if (fCharNum > 0x7FFFFFFF) {
   3591             fParseErr->line   = (int32_t)fLineNum;
   3592             fParseErr->offset = -1;
   3593         } else {
   3594             fParseErr->line   = (int32_t)fLineNum;
   3595             fParseErr->offset = (int32_t)fCharNum;
   3596         }
   3597 
   3598         UErrorCode status = U_ZERO_ERROR; // throwaway status for extracting context
   3599 
   3600         // Fill in the context.
   3601         //   Note: extractBetween() pins supplied indicies to the string bounds.
   3602         uprv_memset(fParseErr->preContext,  0, sizeof(fParseErr->preContext));
   3603         uprv_memset(fParseErr->postContext, 0, sizeof(fParseErr->postContext));
   3604         utext_extract(fRXPat->fPattern, fScanIndex-U_PARSE_CONTEXT_LEN+1, fScanIndex, fParseErr->preContext, U_PARSE_CONTEXT_LEN, &status);
   3605         utext_extract(fRXPat->fPattern, fScanIndex, fScanIndex+U_PARSE_CONTEXT_LEN-1, fParseErr->postContext, U_PARSE_CONTEXT_LEN, &status);
   3606     }
   3607 }
   3608 
   3609 
   3610 //
   3611 //  Assorted Unicode character constants.
   3612 //     Numeric because there is no portable way to enter them as literals.
   3613 //     (Think EBCDIC).
   3614 //
   3615 static const UChar      chCR        = 0x0d;      // New lines, for terminating comments.
   3616 static const UChar      chLF        = 0x0a;      // Line Feed
   3617 static const UChar      chPound     = 0x23;      // '#', introduces a comment.
   3618 static const UChar      chDigit0    = 0x30;      // '0'
   3619 static const UChar      chDigit7    = 0x37;      // '9'
   3620 static const UChar      chColon     = 0x3A;      // ':'
   3621 static const UChar      chE         = 0x45;      // 'E'
   3622 static const UChar      chQ         = 0x51;      // 'Q'
   3623 static const UChar      chN         = 0x4E;      // 'N'
   3624 static const UChar      chP         = 0x50;      // 'P'
   3625 static const UChar      chBackSlash = 0x5c;      // '\'  introduces a char escape
   3626 static const UChar      chLBracket  = 0x5b;      // '['
   3627 static const UChar      chRBracket  = 0x5d;      // ']'
   3628 static const UChar      chUp        = 0x5e;      // '^'
   3629 static const UChar      chLowerP    = 0x70;
   3630 static const UChar      chLBrace    = 0x7b;      // '{'
   3631 static const UChar      chRBrace    = 0x7d;      // '}'
   3632 static const UChar      chNEL       = 0x85;      //    NEL newline variant
   3633 static const UChar      chLS        = 0x2028;    //    Unicode Line Separator
   3634 
   3635 
   3636 //------------------------------------------------------------------------------
   3637 //
   3638 //  nextCharLL    Low Level Next Char from the regex pattern.
   3639 //                Get a char from the string, keep track of input position
   3640 //                     for error reporting.
   3641 //
   3642 //------------------------------------------------------------------------------
   3643 UChar32  RegexCompile::nextCharLL() {
   3644     UChar32       ch;
   3645 
   3646     if (fPeekChar != -1) {
   3647         ch = fPeekChar;
   3648         fPeekChar = -1;
   3649         return ch;
   3650     }
   3651 
   3652     // assume we're already in the right place
   3653     ch = UTEXT_NEXT32(fRXPat->fPattern);
   3654     if (ch == U_SENTINEL) {
   3655         return ch;
   3656     }
   3657 
   3658     if (ch == chCR ||
   3659         ch == chNEL ||
   3660         ch == chLS   ||
   3661         (ch == chLF && fLastChar != chCR)) {
   3662         // Character is starting a new line.  Bump up the line number, and
   3663         //  reset the column to 0.
   3664         fLineNum++;
   3665         fCharNum=0;
   3666     }
   3667     else {
   3668         // Character is not starting a new line.  Except in the case of a
   3669         //   LF following a CR, increment the column position.
   3670         if (ch != chLF) {
   3671             fCharNum++;
   3672         }
   3673     }
   3674     fLastChar = ch;
   3675     return ch;
   3676 }
   3677 
   3678 //------------------------------------------------------------------------------
   3679 //
   3680 //   peekCharLL    Low Level Character Scanning, sneak a peek at the next
   3681 //                 character without actually getting it.
   3682 //
   3683 //------------------------------------------------------------------------------
   3684 UChar32  RegexCompile::peekCharLL() {
   3685     if (fPeekChar == -1) {
   3686         fPeekChar = nextCharLL();
   3687     }
   3688     return fPeekChar;
   3689 }
   3690 
   3691 
   3692 //------------------------------------------------------------------------------
   3693 //
   3694 //   nextChar     for pattern scanning.  At this level, we handle stripping
   3695 //                out comments and processing some backslash character escapes.
   3696 //                The rest of the pattern grammar is handled at the next level up.
   3697 //
   3698 //------------------------------------------------------------------------------
   3699 void RegexCompile::nextChar(RegexPatternChar &c) {
   3700 
   3701     fScanIndex = UTEXT_GETNATIVEINDEX(fRXPat->fPattern);
   3702     c.fChar    = nextCharLL();
   3703     c.fQuoted  = FALSE;
   3704 
   3705     if (fQuoteMode) {
   3706         c.fQuoted = TRUE;
   3707         if ((c.fChar==chBackSlash && peekCharLL()==chE) || c.fChar == (UChar32)-1) {
   3708             fQuoteMode = FALSE;  //  Exit quote mode,
   3709             nextCharLL();       // discard the E
   3710             nextChar(c);        // recurse to get the real next char
   3711         }
   3712     }
   3713     else if (fInBackslashQuote) {
   3714         // The current character immediately follows a '\'
   3715         // Don't check for any further escapes, just return it as-is.
   3716         // Don't set c.fQuoted, because that would prevent the state machine from
   3717         //    dispatching on the character.
   3718         fInBackslashQuote = FALSE;
   3719     }
   3720     else
   3721     {
   3722         // We are not in a \Q quoted region \E of the source.
   3723         //
   3724         if (fModeFlags & UREGEX_COMMENTS) {
   3725             //
   3726             // We are in free-spacing and comments mode.
   3727             //  Scan through any white space and comments, until we
   3728             //  reach a significant character or the end of inut.
   3729             for (;;) {
   3730                 if (c.fChar == (UChar32)-1) {
   3731                     break;     // End of Input
   3732                 }
   3733                 if  (c.fChar == chPound && fEOLComments == TRUE) {
   3734                     // Start of a comment.  Consume the rest of it, until EOF or a new line
   3735                     for (;;) {
   3736                         c.fChar = nextCharLL();
   3737                         if (c.fChar == (UChar32)-1 ||  // EOF
   3738                             c.fChar == chCR        ||
   3739                             c.fChar == chLF        ||
   3740                             c.fChar == chNEL       ||
   3741                             c.fChar == chLS)       {
   3742                             break;
   3743                         }
   3744                     }
   3745                 }
   3746                 // TODO:  check what Java & Perl do with non-ASCII white spaces.  Ticket 6061.
   3747                 if (PatternProps::isWhiteSpace(c.fChar) == FALSE) {
   3748                     break;
   3749                 }
   3750                 c.fChar = nextCharLL();
   3751             }
   3752         }
   3753 
   3754         //
   3755         //  check for backslash escaped characters.
   3756         //
   3757         if (c.fChar == chBackSlash) {
   3758             int64_t pos = UTEXT_GETNATIVEINDEX(fRXPat->fPattern);
   3759             if (RegexStaticSets::gStaticSets->fUnescapeCharSet.contains(peekCharLL())) {
   3760                 //
   3761                 // A '\' sequence that is handled by ICU's standard unescapeAt function.
   3762                 //   Includes \uxxxx, \n, \r, many others.
   3763                 //   Return the single equivalent character.
   3764                 //
   3765                 nextCharLL();                 // get & discard the peeked char.
   3766                 c.fQuoted = TRUE;
   3767 
   3768                 if (UTEXT_FULL_TEXT_IN_CHUNK(fRXPat->fPattern, fPatternLength)) {
   3769                     int32_t endIndex = (int32_t)pos;
   3770                     c.fChar = u_unescapeAt(uregex_ucstr_unescape_charAt, &endIndex, (int32_t)fPatternLength, (void *)fRXPat->fPattern->chunkContents);
   3771 
   3772                     if (endIndex == pos) {
   3773                         error(U_REGEX_BAD_ESCAPE_SEQUENCE);
   3774                     }
   3775                     fCharNum += endIndex - pos;
   3776                     UTEXT_SETNATIVEINDEX(fRXPat->fPattern, endIndex);
   3777                 } else {
   3778                     int32_t offset = 0;
   3779                     struct URegexUTextUnescapeCharContext context = U_REGEX_UTEXT_UNESCAPE_CONTEXT(fRXPat->fPattern);
   3780 
   3781                     UTEXT_SETNATIVEINDEX(fRXPat->fPattern, pos);
   3782                     c.fChar = u_unescapeAt(uregex_utext_unescape_charAt, &offset, INT32_MAX, &context);
   3783 
   3784                     if (offset == 0) {
   3785                         error(U_REGEX_BAD_ESCAPE_SEQUENCE);
   3786                     } else if (context.lastOffset == offset) {
   3787                         UTEXT_PREVIOUS32(fRXPat->fPattern);
   3788                     } else if (context.lastOffset != offset-1) {
   3789                         utext_moveIndex32(fRXPat->fPattern, offset - context.lastOffset - 1);
   3790                     }
   3791                     fCharNum += offset;
   3792                 }
   3793             }
   3794             else if (peekCharLL() == chDigit0) {
   3795                 //  Octal Escape, using Java Regexp Conventions
   3796                 //    which are \0 followed by 1-3 octal digits.
   3797                 //    Different from ICU Unescape handling of Octal, which does not
   3798                 //    require the leading 0.
   3799                 //  Java also has the convention of only consuming 2 octal digits if
   3800                 //    the three digit number would be > 0xff
   3801                 //
   3802                 c.fChar = 0;
   3803                 nextCharLL();    // Consume the initial 0.
   3804                 int index;
   3805                 for (index=0; index<3; index++) {
   3806                     int32_t ch = peekCharLL();
   3807                     if (ch<chDigit0 || ch>chDigit7) {
   3808                         if (index==0) {
   3809                            // \0 is not followed by any octal digits.
   3810                            error(U_REGEX_BAD_ESCAPE_SEQUENCE);
   3811                         }
   3812                         break;
   3813                     }
   3814                     c.fChar <<= 3;
   3815                     c.fChar += ch&7;
   3816                     if (c.fChar <= 255) {
   3817                         nextCharLL();
   3818                     } else {
   3819                         // The last digit made the number too big.  Forget we saw it.
   3820                         c.fChar >>= 3;
   3821                     }
   3822                 }
   3823                 c.fQuoted = TRUE;
   3824             }
   3825             else if (peekCharLL() == chQ) {
   3826                 //  "\Q"  enter quote mode, which will continue until "\E"
   3827                 fQuoteMode = TRUE;
   3828                 nextCharLL();       // discard the 'Q'.
   3829                 nextChar(c);        // recurse to get the real next char.
   3830             }
   3831             else
   3832             {
   3833                 // We are in a '\' escape that will be handled by the state table scanner.
   3834                 // Just return the backslash, but remember that the following char is to
   3835                 //  be taken literally.
   3836                 fInBackslashQuote = TRUE;
   3837             }
   3838         }
   3839     }
   3840 
   3841     // re-enable # to end-of-line comments, in case they were disabled.
   3842     // They are disabled by the parser upon seeing '(?', but this lasts for
   3843     //  the fetching of the next character only.
   3844     fEOLComments = TRUE;
   3845 
   3846     // putc(c.fChar, stdout);
   3847 }
   3848 
   3849 
   3850 
   3851 //------------------------------------------------------------------------------
   3852 //
   3853 //  scanNamedChar
   3854  //            Get a UChar32 from a \N{UNICODE CHARACTER NAME} in the pattern.
   3855 //
   3856 //             The scan position will be at the 'N'.  On return
   3857 //             the scan position should be just after the '}'
   3858 //
   3859 //             Return the UChar32
   3860 //
   3861 //------------------------------------------------------------------------------
   3862 UChar32  RegexCompile::scanNamedChar() {
   3863     if (U_FAILURE(*fStatus)) {
   3864         return 0;
   3865     }
   3866 
   3867     nextChar(fC);
   3868     if (fC.fChar != chLBrace) {
   3869         error(U_REGEX_PROPERTY_SYNTAX);
   3870         return 0;
   3871     }
   3872 
   3873     UnicodeString  charName;
   3874     for (;;) {
   3875         nextChar(fC);
   3876         if (fC.fChar == chRBrace) {
   3877             break;
   3878         }
   3879         if (fC.fChar == -1) {
   3880             error(U_REGEX_PROPERTY_SYNTAX);
   3881             return 0;
   3882         }
   3883         charName.append(fC.fChar);
   3884     }
   3885 
   3886     char name[100];
   3887     if (!uprv_isInvariantUString(charName.getBuffer(), charName.length()) ||
   3888          (uint32_t)charName.length()>=sizeof(name)) {
   3889         // All Unicode character names have only invariant characters.
   3890         // The API to get a character, given a name, accepts only char *, forcing us to convert,
   3891         //   which requires this error check
   3892         error(U_REGEX_PROPERTY_SYNTAX);
   3893         return 0;
   3894     }
   3895     charName.extract(0, charName.length(), name, sizeof(name), US_INV);
   3896 
   3897     UChar32  theChar = u_charFromName(U_UNICODE_CHAR_NAME, name, fStatus);
   3898     if (U_FAILURE(*fStatus)) {
   3899         error(U_REGEX_PROPERTY_SYNTAX);
   3900     }
   3901 
   3902     nextChar(fC);      // Continue overall regex pattern processing with char after the '}'
   3903     return theChar;
   3904 }
   3905 
   3906 //------------------------------------------------------------------------------
   3907 //
   3908 //  scanProp   Construct a UnicodeSet from the text at the current scan
   3909 //             position, which will be of the form \p{whaterver}
   3910 //
   3911 //             The scan position will be at the 'p' or 'P'.  On return
   3912 //             the scan position should be just after the '}'
   3913 //
   3914 //             Return a UnicodeSet, constructed from the \P pattern,
   3915 //             or NULL if the pattern is invalid.
   3916 //
   3917 //------------------------------------------------------------------------------
   3918 UnicodeSet *RegexCompile::scanProp() {
   3919     UnicodeSet    *uset = NULL;
   3920 
   3921     if (U_FAILURE(*fStatus)) {
   3922         return NULL;
   3923     }
   3924     U_ASSERT(fC.fChar == chLowerP || fC.fChar == chP);
   3925     UBool negated = (fC.fChar == chP);
   3926 
   3927     UnicodeString propertyName;
   3928     nextChar(fC);
   3929     if (fC.fChar != chLBrace) {
   3930         error(U_REGEX_PROPERTY_SYNTAX);
   3931         return NULL;
   3932     }
   3933     for (;;) {
   3934         nextChar(fC);
   3935         if (fC.fChar == chRBrace) {
   3936             break;
   3937         }
   3938         if (fC.fChar == -1) {
   3939             // Hit the end of the input string without finding the closing '}'
   3940             error(U_REGEX_PROPERTY_SYNTAX);
   3941             return NULL;
   3942         }
   3943         propertyName.append(fC.fChar);
   3944     }
   3945     uset = createSetForProperty(propertyName, negated);
   3946     nextChar(fC);    // Move input scan to position following the closing '}'
   3947     return uset;
   3948 }
   3949 
   3950 //------------------------------------------------------------------------------
   3951 //
   3952 //  scanPosixProp   Construct a UnicodeSet from the text at the current scan
   3953 //             position, which is expected be of the form [:property expression:]
   3954 //
   3955 //             The scan position will be at the opening ':'.  On return
   3956 //             the scan position must be on the closing ']'
   3957 //
   3958 //             Return a UnicodeSet constructed from the pattern,
   3959 //             or NULL if this is not a valid POSIX-style set expression.
   3960 //             If not a property expression, restore the initial scan position
   3961 //                (to the opening ':')
   3962 //
   3963 //               Note:  the opening '[:' is not sufficient to guarantee that
   3964 //                      this is a [:property:] expression.
   3965 //                      [:'+=,] is a perfectly good ordinary set expression that
   3966 //                              happens to include ':' as one of its characters.
   3967 //
   3968 //------------------------------------------------------------------------------
   3969 UnicodeSet *RegexCompile::scanPosixProp() {
   3970     UnicodeSet    *uset = NULL;
   3971 
   3972     if (U_FAILURE(*fStatus)) {
   3973         return NULL;
   3974     }
   3975 
   3976     U_ASSERT(fC.fChar == chColon);
   3977 
   3978     // Save the scanner state.
   3979     // TODO:  move this into the scanner, with the state encapsulated in some way.  Ticket 6062
   3980     int64_t     savedScanIndex        = fScanIndex;
   3981     int64_t     savedNextIndex        = UTEXT_GETNATIVEINDEX(fRXPat->fPattern);
   3982     UBool       savedQuoteMode        = fQuoteMode;
   3983     UBool       savedInBackslashQuote = fInBackslashQuote;
   3984     UBool       savedEOLComments      = fEOLComments;
   3985     int64_t     savedLineNum          = fLineNum;
   3986     int64_t     savedCharNum          = fCharNum;
   3987     UChar32     savedLastChar         = fLastChar;
   3988     UChar32     savedPeekChar         = fPeekChar;
   3989     RegexPatternChar savedfC          = fC;
   3990 
   3991     // Scan for a closing ].   A little tricky because there are some perverse
   3992     //   edge cases possible.  "[:abc\Qdef:] \E]"  is a valid non-property expression,
   3993     //   ending on the second closing ].
   3994 
   3995     UnicodeString propName;
   3996     UBool         negated  = FALSE;
   3997 
   3998     // Check for and consume the '^' in a negated POSIX property, e.g.  [:^Letter:]
   3999     nextChar(fC);
   4000     if (fC.fChar == chUp) {
   4001        negated = TRUE;
   4002        nextChar(fC);
   4003     }
   4004 
   4005     // Scan for the closing ":]", collecting the property name along the way.
   4006     UBool  sawPropSetTerminator = FALSE;
   4007     for (;;) {
   4008         propName.append(fC.fChar);
   4009         nextChar(fC);
   4010         if (fC.fQuoted || fC.fChar == -1) {
   4011             // Escaped characters or end of input - either says this isn't a [:Property:]
   4012             break;
   4013         }
   4014         if (fC.fChar == chColon) {
   4015             nextChar(fC);
   4016             if (fC.fChar == chRBracket) {
   4017                 sawPropSetTerminator = TRUE;
   4018             }
   4019             break;
   4020         }
   4021     }
   4022 
   4023     if (sawPropSetTerminator) {
   4024         uset = createSetForProperty(propName, negated);
   4025     }
   4026     else
   4027     {
   4028         // No closing ":]".
   4029         //  Restore the original scan position.
   4030         //  The main scanner will retry the input as a normal set expression,
   4031         //    not a [:Property:] expression.
   4032         fScanIndex        = savedScanIndex;
   4033         fQuoteMode        = savedQuoteMode;
   4034         fInBackslashQuote = savedInBackslashQuote;
   4035         fEOLComments      = savedEOLComments;
   4036         fLineNum          = savedLineNum;
   4037         fCharNum          = savedCharNum;
   4038         fLastChar         = savedLastChar;
   4039         fPeekChar         = savedPeekChar;
   4040         fC                = savedfC;
   4041         UTEXT_SETNATIVEINDEX(fRXPat->fPattern, savedNextIndex);
   4042     }
   4043     return uset;
   4044 }
   4045 
   4046 static inline void addIdentifierIgnorable(UnicodeSet *set, UErrorCode& ec) {
   4047     set->add(0, 8).add(0x0e, 0x1b).add(0x7f, 0x9f);
   4048     addCategory(set, U_GC_CF_MASK, ec);
   4049 }
   4050 
   4051 //
   4052 //  Create a Unicode Set from a Unicode Property expression.
   4053 //     This is common code underlying both \p{...} ane [:...:] expressions.
   4054 //     Includes trying the Java "properties" that aren't supported as
   4055 //     normal ICU UnicodeSet properties
   4056 //
   4057 static const UChar posSetPrefix[] = {0x5b, 0x5c, 0x70, 0x7b, 0}; // "[\p{"
   4058 static const UChar negSetPrefix[] = {0x5b, 0x5c, 0x50, 0x7b, 0}; // "[\P{"
   4059 UnicodeSet *RegexCompile::createSetForProperty(const UnicodeString &propName, UBool negated) {
   4060     UnicodeString   setExpr;
   4061     UnicodeSet      *set;
   4062     uint32_t        usetFlags = 0;
   4063 
   4064     if (U_FAILURE(*fStatus)) {
   4065         return NULL;
   4066     }
   4067 
   4068     //
   4069     //  First try the property as we received it
   4070     //
   4071     if (negated) {
   4072         setExpr.append(negSetPrefix, -1);
   4073     } else {
   4074         setExpr.append(posSetPrefix, -1);
   4075     }
   4076     setExpr.append(propName);
   4077     setExpr.append(chRBrace);
   4078     setExpr.append(chRBracket);
   4079     if (fModeFlags & UREGEX_CASE_INSENSITIVE) {
   4080         usetFlags |= USET_CASE_INSENSITIVE;
   4081     }
   4082     set = new UnicodeSet(setExpr, usetFlags, NULL, *fStatus);
   4083     if (U_SUCCESS(*fStatus)) {
   4084        return set;
   4085     }
   4086     delete set;
   4087     set = NULL;
   4088 
   4089     //
   4090     //  The property as it was didn't work.
   4091 
   4092     //  Do [:word:]. It is not recognized as a property by UnicodeSet.  "word" not standard POSIX
   4093     //     or standard Java, but many other regular expression packages do recognize it.
   4094 
   4095     if (propName.caseCompare(UNICODE_STRING_SIMPLE("word"), 0) == 0) {
   4096         *fStatus = U_ZERO_ERROR;
   4097         set = new UnicodeSet(*(fRXPat->fStaticSets[URX_ISWORD_SET]));
   4098         if (set == NULL) {
   4099             *fStatus = U_MEMORY_ALLOCATION_ERROR;
   4100             return set;
   4101         }
   4102         if (negated) {
   4103             set->complement();
   4104         }
   4105         return set;
   4106     }
   4107 
   4108 
   4109     //    Do Java fixes -
   4110     //       InGreek -> InGreek or Coptic, that being the official Unicode name for that block.
   4111     //       InCombiningMarksforSymbols -> InCombiningDiacriticalMarksforSymbols.
   4112     //
   4113     //       Note on Spaces:  either "InCombiningMarksForSymbols" or "InCombining Marks for Symbols"
   4114     //                        is accepted by Java.  The property part of the name is compared
   4115     //                        case-insenstively.  The spaces must be exactly as shown, either
   4116     //                        all there, or all omitted, with exactly one at each position
   4117     //                        if they are present.  From checking against JDK 1.6
   4118     //
   4119     //       This code should be removed when ICU properties support the Java  compatibility names
   4120     //          (ICU 4.0?)
   4121     //
   4122     UnicodeString mPropName = propName;
   4123     if (mPropName.caseCompare(UNICODE_STRING_SIMPLE("InGreek"), 0) == 0) {
   4124         mPropName = UNICODE_STRING_SIMPLE("InGreek and Coptic");
   4125     }
   4126     if (mPropName.caseCompare(UNICODE_STRING_SIMPLE("InCombining Marks for Symbols"), 0) == 0 ||
   4127         mPropName.caseCompare(UNICODE_STRING_SIMPLE("InCombiningMarksforSymbols"), 0) == 0) {
   4128         mPropName = UNICODE_STRING_SIMPLE("InCombining Diacritical Marks for Symbols");
   4129     }
   4130     else if (mPropName.compare(UNICODE_STRING_SIMPLE("all")) == 0) {
   4131         mPropName = UNICODE_STRING_SIMPLE("javaValidCodePoint");
   4132     }
   4133 
   4134     //    See if the property looks like a Java "InBlockName", which
   4135     //    we will recast as "Block=BlockName"
   4136     //
   4137     static const UChar IN[] = {0x49, 0x6E, 0};  // "In"
   4138     static const UChar BLOCK[] = {0x42, 0x6C, 0x6f, 0x63, 0x6b, 0x3d, 00};  // "Block="
   4139     if (mPropName.startsWith(IN, 2) && propName.length()>=3) {
   4140         setExpr.truncate(4);   // Leaves "[\p{", or "[\P{"
   4141         setExpr.append(BLOCK, -1);
   4142         setExpr.append(UnicodeString(mPropName, 2));  // Property with the leading "In" removed.
   4143         setExpr.append(chRBrace);
   4144         setExpr.append(chRBracket);
   4145         *fStatus = U_ZERO_ERROR;
   4146         set = new UnicodeSet(setExpr, usetFlags, NULL, *fStatus);
   4147         if (U_SUCCESS(*fStatus)) {
   4148             return set;
   4149         }
   4150         delete set;
   4151         set = NULL;
   4152     }
   4153 
   4154     if (propName.startsWith(UNICODE_STRING_SIMPLE("java")) ||
   4155         propName.compare(UNICODE_STRING_SIMPLE("all")) == 0)
   4156     {
   4157         UErrorCode localStatus = U_ZERO_ERROR;
   4158         //setExpr.remove();
   4159         set = new UnicodeSet();
   4160         //
   4161         //  Try the various Java specific properties.
   4162         //   These all begin with "java"
   4163         //
   4164         if (mPropName.compare(UNICODE_STRING_SIMPLE("javaDefined")) == 0) {
   4165             addCategory(set, U_GC_CN_MASK, localStatus);
   4166             set->complement();
   4167         }
   4168         else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaDigit")) == 0) {
   4169             addCategory(set, U_GC_ND_MASK, localStatus);
   4170         }
   4171         else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaIdentifierIgnorable")) == 0) {
   4172             addIdentifierIgnorable(set, localStatus);
   4173         }
   4174         else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaISOControl")) == 0) {
   4175             set->add(0, 0x1F).add(0x7F, 0x9F);
   4176         }
   4177         else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaJavaIdentifierPart")) == 0) {
   4178             addCategory(set, U_GC_L_MASK, localStatus);
   4179             addCategory(set, U_GC_SC_MASK, localStatus);
   4180             addCategory(set, U_GC_PC_MASK, localStatus);
   4181             addCategory(set, U_GC_ND_MASK, localStatus);
   4182             addCategory(set, U_GC_NL_MASK, localStatus);
   4183             addCategory(set, U_GC_MC_MASK, localStatus);
   4184             addCategory(set, U_GC_MN_MASK, localStatus);
   4185             addIdentifierIgnorable(set, localStatus);
   4186         }
   4187         else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaJavaIdentifierStart")) == 0) {
   4188             addCategory(set, U_GC_L_MASK, localStatus);
   4189             addCategory(set, U_GC_NL_MASK, localStatus);
   4190             addCategory(set, U_GC_SC_MASK, localStatus);
   4191             addCategory(set, U_GC_PC_MASK, localStatus);
   4192         }
   4193         else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaLetter")) == 0) {
   4194             addCategory(set, U_GC_L_MASK, localStatus);
   4195         }
   4196         else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaLetterOrDigit")) == 0) {
   4197             addCategory(set, U_GC_L_MASK, localStatus);
   4198             addCategory(set, U_GC_ND_MASK, localStatus);
   4199         }
   4200         else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaLowerCase")) == 0) {
   4201             addCategory(set, U_GC_LL_MASK, localStatus);
   4202         }
   4203         else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaMirrored")) == 0) {
   4204             set->applyIntPropertyValue(UCHAR_BIDI_MIRRORED, 1, localStatus);
   4205         }
   4206         else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaSpaceChar")) == 0) {
   4207             addCategory(set, U_GC_Z_MASK, localStatus);
   4208         }
   4209         else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaSupplementaryCodePoint")) == 0) {
   4210             set->add(0x10000, UnicodeSet::MAX_VALUE);
   4211         }
   4212         else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaTitleCase")) == 0) {
   4213             addCategory(set, U_GC_LT_MASK, localStatus);
   4214         }
   4215         else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaUnicodeIdentifierStart")) == 0) {
   4216             addCategory(set, U_GC_L_MASK, localStatus);
   4217             addCategory(set, U_GC_NL_MASK, localStatus);
   4218         }
   4219         else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaUnicodeIdentifierPart")) == 0) {
   4220             addCategory(set, U_GC_L_MASK, localStatus);
   4221             addCategory(set, U_GC_PC_MASK, localStatus);
   4222             addCategory(set, U_GC_ND_MASK, localStatus);
   4223             addCategory(set, U_GC_NL_MASK, localStatus);
   4224             addCategory(set, U_GC_MC_MASK, localStatus);
   4225             addCategory(set, U_GC_MN_MASK, localStatus);
   4226             addIdentifierIgnorable(set, localStatus);
   4227         }
   4228         else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaUpperCase")) == 0) {
   4229             addCategory(set, U_GC_LU_MASK, localStatus);
   4230         }
   4231         else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaValidCodePoint")) == 0) {
   4232             set->add(0, UnicodeSet::MAX_VALUE);
   4233         }
   4234         else if (mPropName.compare(UNICODE_STRING_SIMPLE("javaWhitespace")) == 0) {
   4235             addCategory(set, U_GC_Z_MASK, localStatus);
   4236             set->removeAll(UnicodeSet().add(0xa0).add(0x2007).add(0x202f));
   4237             set->add(9, 0x0d).add(0x1c, 0x1f);
   4238         }
   4239         else if (mPropName.compare(UNICODE_STRING_SIMPLE("all")) == 0) {
   4240             set->add(0, UnicodeSet::MAX_VALUE);
   4241         }
   4242 
   4243         if (U_SUCCESS(localStatus) && !set->isEmpty()) {
   4244             *fStatus = U_ZERO_ERROR;
   4245             if (usetFlags & USET_CASE_INSENSITIVE) {
   4246                 set->closeOver(USET_CASE_INSENSITIVE);
   4247             }
   4248             if (negated) {
   4249                 set->complement();
   4250             }
   4251             return set;
   4252         }
   4253         delete set;
   4254         set = NULL;
   4255     }
   4256     error(*fStatus);
   4257     return NULL;
   4258 }
   4259 
   4260 
   4261 
   4262 //
   4263 //  SetEval   Part of the evaluation of [set expressions].
   4264 //            Perform any pending (stacked) operations with precedence
   4265 //            equal or greater to that of the next operator encountered
   4266 //            in the expression.
   4267 //
   4268 void RegexCompile::setEval(int32_t nextOp) {
   4269     UnicodeSet *rightOperand = NULL;
   4270     UnicodeSet *leftOperand  = NULL;
   4271     for (;;) {
   4272         U_ASSERT(fSetOpStack.empty()==FALSE);
   4273         int32_t pendingSetOperation = fSetOpStack.peeki();
   4274         if ((pendingSetOperation&0xffff0000) < (nextOp&0xffff0000)) {
   4275             break;
   4276         }
   4277         fSetOpStack.popi();
   4278         U_ASSERT(fSetStack.empty() == FALSE);
   4279         rightOperand = (UnicodeSet *)fSetStack.peek();
   4280         switch (pendingSetOperation) {
   4281             case setNegation:
   4282                 rightOperand->complement();
   4283                 break;
   4284             case setCaseClose:
   4285                 // TODO: need a simple close function.  Ticket 6065
   4286                 rightOperand->closeOver(USET_CASE_INSENSITIVE);
   4287                 rightOperand->removeAllStrings();
   4288                 break;
   4289             case setDifference1:
   4290             case setDifference2:
   4291                 fSetStack.pop();
   4292                 leftOperand = (UnicodeSet *)fSetStack.peek();
   4293                 leftOperand->removeAll(*rightOperand);
   4294                 delete rightOperand;
   4295                 break;
   4296             case setIntersection1:
   4297             case setIntersection2:
   4298                 fSetStack.pop();
   4299                 leftOperand = (UnicodeSet *)fSetStack.peek();
   4300                 leftOperand->retainAll(*rightOperand);
   4301                 delete rightOperand;
   4302                 break;
   4303             case setUnion:
   4304                 fSetStack.pop();
   4305                 leftOperand = (UnicodeSet *)fSetStack.peek();
   4306                 leftOperand->addAll(*rightOperand);
   4307                 delete rightOperand;
   4308                 break;
   4309             default:
   4310                 U_ASSERT(FALSE);
   4311                 break;
   4312             }
   4313         }
   4314     }
   4315 
   4316 void RegexCompile::setPushOp(int32_t op) {
   4317     setEval(op);
   4318     fSetOpStack.push(op, *fStatus);
   4319     fSetStack.push(new UnicodeSet(), *fStatus);
   4320 }
   4321 
   4322 U_NAMESPACE_END
   4323 #endif  // !UCONFIG_NO_REGULAR_EXPRESSIONS
   4324 
   4325