ICU 56 update step 1

source/i18n/regexcmp.cpp

 //
 //  file:  regexcmp.cpp
 //
-//  Copyright (C) 2002-2014 International Business Machines Corporation and others.
+//  Copyright (C) 2002-2015 International Business Machines Corporation and others.
 //  All Rights Reserved.
 //
 //  This file contains the ICU regular expression compiler, which is responsible
 //  for processing a regular expression pattern into the compiled form that
 //  is used by the match finding engine.
 //
 
 #include "unicode/utypes.h"
 
 #if !UCONFIG_NO_REGULAR_EXPRESSIONS
@@ skipping 48 matching lines @@
     fPeekChar         = -1;
     fLineNum          = 1;
     fCharNum          = 0;
     fQuoteMode        = FALSE;
     fInBackslashQuote = FALSE;
     fModeFlags        = fRXPat->fFlags | 0x80000000;
     fEOLComments      = TRUE;
 
     fMatchOpenParen   = -1;
     fMatchCloseParen  = -1;
+    fCaptureName      = NULL;
 
     if (U_SUCCESS(status) && U_FAILURE(rxp->fDeferredStatus)) {
         status = rxp->fDeferredStatus;
     }
 }
 
 static const UChar      chAmp       = 0x26;      // '&'
 static const UChar      chDash      = 0x2d;      // '-'
 
 
 //------------------------------------------------------------------------------
 //
 //  Destructor
 //
 //------------------------------------------------------------------------------
 RegexCompile::~RegexCompile() {
+    delete fCaptureName;         // Normally will be NULL, but can exist if pattern
+                                 //   compilation stops with a syntax error.
 }
 
 static inline void addCategory(UnicodeSet *set, int32_t value, UErrorCode& ec) {
     set->addAll(UnicodeSet().applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, value, ec));
 }
 
 //------------------------------------------------------------------------------
 //
 //  Compile regex pattern.   The state machine for rexexp pattern parsing is here.
 //                           The state tables are hand-written in the file regexcst.txt,
@@ skipping 32 matching lines @@
 
     if (U_FAILURE(*fStatus)) {
         return;
     }
 
     // There should be no pattern stuff in the RegexPattern object.  They can not be reused.
     U_ASSERT(fRXPat->fPattern == NULL || utext_nativeLength(fRXPat->fPattern) == 0);
 
     // Prepare the RegexPattern object to receive the compiled pattern.
     fRXPat->fPattern        = utext_clone(fRXPat->fPattern, pat, FALSE, TRUE, fStatus);
+    if (U_FAILURE(*fStatus)) {
+        return;
+    }
     fRXPat->fStaticSets     = RegexStaticSets::gStaticSets->fPropSets;
     fRXPat->fStaticSets8    = RegexStaticSets::gStaticSets->fPropSets8;
 
 
     // Initialize the pattern scanning state machine
     fPatternLength = utext_nativeLength(pat);
     uint16_t                state = 1;
     const RegexTableEl      *tableEl;
 
     // UREGEX_LITERAL force entire pattern to be treated as a literal string.
@@ skipping 126 matching lines @@
             delete (UnicodeSet *)fSetStack.pop();
         }
         return;
     }
 
     //
     // The pattern has now been read and processed, and the compiled code generated.
     //
 
     //
-    // Compute the number of digits requried for the largest capture group number.
-    //
-    fRXPat->fMaxCaptureDigits = 1;
-    int32_t  n = 10;
-    int32_t  groupCount = fRXPat->fGroupMap->size();
-    while (n <= groupCount) {
-        fRXPat->fMaxCaptureDigits++;
-        n *= 10;
-    }
-
-    //
     // The pattern's fFrameSize so far has accumulated the requirements for
     //   storage for capture parentheses, counters, etc. that are encountered
     //   in the pattern.  Add space for the two variables that are always
     //   present in the saved state:  the input string position (int64_t) and
     //   the position in the compiled pattern.
     //
     allocateStackData(RESTACKFRAME_HDRCOUNT);
 
     //
     // Optimization pass 1: NOPs, back-references, and case-folding
@@ skipping 120 matching lines @@
 
             // Append a NOP to the compiled pattern.  This is the slot reserved
             //   for a SAVE in the event that there is yet another '|' following
             //   this one.
             appendOp(URX_NOP, 0);
             fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus);
         }
         break;
 
 
+    case doBeginNamedCapture:
+        // Scanning (?<letter.
+        //   The first letter of the name will come through again under doConinueNamedCapture.
+        fCaptureName = new UnicodeString();
+        if (fCaptureName == NULL) {
+            error(U_MEMORY_ALLOCATION_ERROR);
+        }
+        break;
+
+    case  doContinueNamedCapture:
+        fCaptureName->append(fC.fChar);
+        break;
+
+    case doBadNamedCapture:
+        error(U_REGEX_INVALID_CAPTURE_GROUP_NAME);
+        break;
+        
     case doOpenCaptureParen:
-        // Open Paren.
+        // Open Capturing Paren, possibly named.
         //   Compile to a
         //      - NOP, which later may be replaced by a save-state if the
         //         parenthesized group gets a * quantifier, followed by
         //      - START_CAPTURE  n    where n is stack frame offset to the capture group variables.
         //      - NOP, which may later be replaced by a save-state if there
         //             is an '|' alternation within the parens.
         //
         //    Each capture group gets three slots in the save stack frame:
         //         0: Capture Group start position (in input string being matched.)
         //         1: Capture Group end position.
@@ skipping 14 matching lines @@
             //   of the two NOPs.  Depending on what follows in the pattern, the
             //   NOPs may be changed to SAVE_STATE or JMP ops, with a target
             //   address of the end of the parenthesized group.
             fParenStack.push(fModeFlags, *fStatus);                       // Match mode state
             fParenStack.push(capturing, *fStatus);                        // Frame type.
             fParenStack.push(fRXPat->fCompiledPat->size()-3, *fStatus);   // The first  NOP location
             fParenStack.push(fRXPat->fCompiledPat->size()-1, *fStatus);   // The second NOP loc
 
             // Save the mapping from group number to stack frame variable position.
             fRXPat->fGroupMap->addElement(varsLoc, *fStatus);
+
+            // If this is a named capture group, add the name->group number mapping.
+            if (fCaptureName != NULL) {
+                int32_t groupNumber = fRXPat->fGroupMap->size();
+                int32_t previousMapping = uhash_puti(fRXPat->fNamedCaptureMap, fCaptureName, groupNumber, fStatus);
+                fCaptureName = NULL;    // hash table takes ownership of the name (key) string.
+                if (previousMapping > 0 && U_SUCCESS(*fStatus)) {
+                    error(U_REGEX_INVALID_CAPTURE_GROUP_NAME);
+                }
+            }
         }
-         break;
+        break;
 
     case doOpenNonCaptureParen:
         // Open non-caputuring (grouping only) Paren.
         //   Compile to a
         //      - NOP, which later may be replaced by a save-state if the
         //         parenthesized group gets a * quantifier, followed by
         //      - NOP, which may later be replaced by a save-state if there
         //             is an '|' alternation within the parens.
         {
             fixLiterals();
@@ skipping 485 matching lines @@
         //    are scanned.
         fIntervalLow = 0;
         fIntervalUpper = -1;
         break;
 
     case doIntevalLowerDigit:
         // Scanned a digit from the lower value of an {lower,upper} interval
         {
             int32_t digitValue = u_charDigitValue(fC.fChar);
             U_ASSERT(digitValue >= 0);
-            fIntervalLow = fIntervalLow*10 + digitValue;
-            if (fIntervalLow < 0) {
+            int64_t val = (int64_t)fIntervalLow*10 + digitValue;
+            if (val > INT32_MAX) {
                 error(U_REGEX_NUMBER_TOO_BIG);
+            } else {
+                fIntervalLow = (int32_t)val;
             }
         }
         break;
 
     case doIntervalUpperDigit:
         // Scanned a digit from the upper value of an {lower,upper} interval
         {
             if (fIntervalUpper < 0) {
                 fIntervalUpper = 0;
             }
             int32_t digitValue = u_charDigitValue(fC.fChar);
             U_ASSERT(digitValue >= 0);
-            fIntervalUpper = fIntervalUpper*10 + digitValue;
-            if (fIntervalUpper < 0) {
+            int64_t val = (int64_t)fIntervalUpper*10 + digitValue;
+            if (val > INT32_MAX) {
                 error(U_REGEX_NUMBER_TOO_BIG);
+            } else {
+                fIntervalUpper = (int32_t)val;
             }
         }
         break;
 
     case doIntervalSame:
         // Scanned a single value interval like {27}.  Upper = Lower.
         fIntervalUpper = fIntervalLow;
         break;
 
     case doInterval:
@@ skipping 146 matching lines @@
     case doBackslashd:
         fixLiterals(FALSE);
         appendOp(URX_BACKSLASH_D, 0);
         break;
 
     case doBackslashG:
         fixLiterals(FALSE);
         appendOp(URX_BACKSLASH_G, 0);
         break;
 
+    case doBackslashH:
+        fixLiterals(FALSE);
+        appendOp(URX_BACKSLASH_H, 1);
+        break;
+
+    case doBackslashh:
+        fixLiterals(FALSE);
+        appendOp(URX_BACKSLASH_H, 0);
+        break;
+
+    case doBackslashR:
+        fixLiterals(FALSE);
+        appendOp(URX_BACKSLASH_R, 0);
+        break;
+
     case doBackslashS:
         fixLiterals(FALSE);
         appendOp(URX_STAT_SETREF_N, URX_ISSPACE_SET);
         break;
 
     case doBackslashs:
         fixLiterals(FALSE);
         appendOp(URX_STATIC_SETREF, URX_ISSPACE_SET);
         break;
 
+    case doBackslashV:
+        fixLiterals(FALSE);
+        appendOp(URX_BACKSLASH_V, 1);
+        break;
+
+    case doBackslashv:
+        fixLiterals(FALSE);
+        appendOp(URX_BACKSLASH_V, 0);
+        break;
+
     case doBackslashW:
         fixLiterals(FALSE);
         appendOp(URX_STAT_SETREF_N, URX_ISWORD_SET);
         break;
 
     case doBackslashw:
         fixLiterals(FALSE);
         appendOp(URX_STATIC_SETREF, URX_ISWORD_SET);
         break;
 
@@ skipping 71 matching lines @@
                                      //    and shouldn't enter this code path at all.
             fixLiterals(FALSE);
             if (fModeFlags & UREGEX_CASE_INSENSITIVE) {
                 appendOp(URX_BACKREF_I, groupNum);
             } else {
                 appendOp(URX_BACKREF, groupNum);
             }
         }
         break;
 
+    case doBeginNamedBackRef:
+        U_ASSERT(fCaptureName == NULL);
+        fCaptureName = new UnicodeString;
+        if (fCaptureName == NULL) {
+            error(U_MEMORY_ALLOCATION_ERROR);
+        }
+        break;
+            
+    case doContinueNamedBackRef:
+        fCaptureName->append(fC.fChar);
+        break;
 
+    case doCompleteNamedBackRef:
+        {
+        int32_t groupNumber = uhash_geti(fRXPat->fNamedCaptureMap, fCaptureName);
+        if (groupNumber == 0) {
+            // Group name has not been defined.
+            //   Could be a forward reference. If we choose to support them at some
+            //   future time, extra mechanism will be required at this point.
+            error(U_REGEX_INVALID_CAPTURE_GROUP_NAME);
+        } else {
+            // Given the number, handle identically to a \n numbered back reference.
+            // See comments above, under doBackRef
+            fixLiterals(FALSE);
+            if (fModeFlags & UREGEX_CASE_INSENSITIVE) {
+                appendOp(URX_BACKREF_I, groupNumber);
+            } else {
+                appendOp(URX_BACKREF, groupNumber);
+            }
+        }
+        delete fCaptureName;
+        fCaptureName = NULL;
+        break;
+        }
+       
     case doPossessivePlus:
         // Possessive ++ quantifier.
         // Compiles to
         //       1.   STO_SP
         //       2.      body of stuff being iterated over
         //       3.   STATE_SAVE 5
         //       4.   JMP        2
         //       5.   LD_SP
         //       6.   ...
         //
@@ skipping 204 matching lines @@
         {
             UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
             UnicodeSet digits;
             // TODO - make a static set, ticket 6058.
             digits.applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, U_GC_ND_MASK, *fStatus);
             digits.complement();
             set->addAll(digits);
             break;
         }
 
+    case doSetBackslash_h:
+        {
+            UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
+            UnicodeSet h;
+            h.applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, U_GC_ZS_MASK, *fStatus);
+            h.add((UChar32)9);   // Tab
+            set->addAll(h);
+            break;
+        }
+
+    case doSetBackslash_H:
+        {
+            UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
+            UnicodeSet h;
+            h.applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, U_GC_ZS_MASK, *fStatus);
+            h.add((UChar32)9);   // Tab
+            h.complement();
+            set->addAll(h);
+            break;
+        }
+
+    case doSetBackslash_v:
+        {
+            UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
+            set->add((UChar32)0x0a, (UChar32)0x0d);  // add range
+            set->add((UChar32)0x85);
+            set->add((UChar32)0x2028, (UChar32)0x2029);
+            break;
+        }
+
+    case doSetBackslash_V:
+        {
+            UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
+            UnicodeSet v;
+            v.add((UChar32)0x0a, (UChar32)0x0d);  // add range
+            v.add((UChar32)0x85);
+            v.add((UChar32)0x2028, (UChar32)0x2029);
+            v.complement();
+            set->addAll(v);
+            break;
+        }
+
     case doSetBackslash_w:
         {
             UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
             set->addAll(*RegexStaticSets::gStaticSets->fPropSets[URX_ISWORD_SET]);
             break;
         }
 
     case doSetBackslash_W:
         {
             UnicodeSet *set = (UnicodeSet *)fSetStack.peek();
@@ skipping 1181 matching lines @@
                      s.complement();
                  }
                  fRXPat->fInitialChars->addAll(s);
                  numInitialStrings += 2;
             }
             currentLen++;
             atStart = FALSE;
             break;
 
 
+        case URX_BACKSLASH_H:
+            // Horiz white space
+            if (currentLen == 0) {
+                UnicodeSet s;
+                s.applyIntPropertyValue(UCHAR_GENERAL_CATEGORY_MASK, U_GC_ZS_MASK, *fStatus);
+                s.add((UChar32)9);   // Tab
+                if (URX_VAL(op) != 0) {
+                    s.complement();
+                }
+                fRXPat->fInitialChars->addAll(s);
+                numInitialStrings += 2;
+            }
+            currentLen++;
+            atStart = FALSE;
+            break;
+
+
+        case URX_BACKSLASH_R:       // Any line ending sequence
+        case URX_BACKSLASH_V:       // Any line ending code point, with optional negation
+            if (currentLen == 0) {
+                UnicodeSet s;
+                s.add((UChar32)0x0a, (UChar32)0x0d);  // add range
+                s.add((UChar32)0x85);
+                s.add((UChar32)0x2028, (UChar32)0x2029);
+                if (URX_VAL(op) != 0) {
+                     // Complement option applies to URX_BACKSLASH_V only.
+                     s.complement();
+                }
+                fRXPat->fInitialChars->addAll(s);
+                numInitialStrings += 2;
+            }
+            currentLen++;
+            atStart = FALSE;
+            break;
+
+
+
         case URX_ONECHAR_I:
             // Case Insensitive Single Character.
             if (currentLen == 0) {
                 UChar32  c = URX_VAL(op);
                 if (u_hasBinaryProperty(c, UCHAR_CASE_SENSITIVE)) {
                     UnicodeSet starters(c, c);
                     starters.closeOver(USET_CASE_INSENSITIVE);
                     // findCaseInsensitiveStarters(c, &starters);
                     //   For ONECHAR_I, no need to worry about text chars that expand on folding into strings.
                     //   The expanded folding can't match the pattern.
@@ skipping 368 matching lines @@
             break;
 
 
             // Ops that match a minimum of one character (one or two 16 bit code units.)
             //
         case URX_ONECHAR:
         case URX_STATIC_SETREF:
         case URX_STAT_SETREF_N:
         case URX_SETREF:
         case URX_BACKSLASH_D:
+        case URX_BACKSLASH_H:
+        case URX_BACKSLASH_R:
+        case URX_BACKSLASH_V:
         case URX_ONECHAR_I:
         case URX_BACKSLASH_X:   // Grahpeme Cluster.  Minimum is 1, max unbounded.
         case URX_DOTANY_ALL:    // . matches one or two.
         case URX_DOTANY:
         case URX_DOTANY_UNIX:
             currentLen++;
             break;
 
 
         case URX_JMPX:
@@ skipping 261 matching lines @@
             currentLen = INT32_MAX;
             break;
 
 
             // Ops that match a max of one character (possibly two 16 bit code units.)
             //
         case URX_STATIC_SETREF:
         case URX_STAT_SETREF_N:
         case URX_SETREF:
         case URX_BACKSLASH_D:
+        case URX_BACKSLASH_H:
+        case URX_BACKSLASH_R:
+        case URX_BACKSLASH_V:
         case URX_ONECHAR_I:
         case URX_DOTANY_ALL:
         case URX_DOTANY:
         case URX_DOTANY_UNIX:
             currentLen = safeIncrement(currentLen, 2);
             break;
 
             // Single literal character.  Increase current max length by one or two,
             //       depending on whether the char is in the supplementary range.
         case URX_ONECHAR:
@@ skipping 101 matching lines @@
                 }
 
                 int32_t maxLoopCount = static_cast<int32_t>(fRXPat->fCompiledPat->elementAti(loc+3));
                 if (maxLoopCount == -1) {
                     // Unbounded Loop. No upper bound on match length.
                     currentLen = INT32_MAX;
                     break;
                 }
 
                 U_ASSERT(loopEndLoc >= loc+4);
-                int32_t  blockLen = maxMatchLength(loc+4, loopEndLoc-1);  // Recursive call.
-                if (blockLen == INT32_MAX) {
-                    currentLen = blockLen;
+                int64_t blockLen = maxMatchLength(loc+4, loopEndLoc-1);  // Recursive call.
+                int64_t updatedLen = (int64_t)currentLen + blockLen * maxLoopCount; 
+                if (updatedLen >= INT32_MAX) {
+                    currentLen = INT32_MAX;
                     break;
                 }
-                currentLen += blockLen * maxLoopCount;
+                currentLen = (int32_t)updatedLen;
                 loc = loopEndLoc;
                 break;
             }
 
         case URX_CTR_LOOP:
         case URX_CTR_LOOP_NG:
             // These opcodes will be skipped over by code for URX_CRT_INIT.
             // We shouldn't encounter them here.
             U_ASSERT(FALSE);
             break;
@@ skipping 180 matching lines @@
         case URX_LB_START:
         case URX_LB_CONT:
         case URX_LB_END:
         case URX_LBN_CONT:
         case URX_LBN_END:
         case URX_LOOP_SR_I:
         case URX_LOOP_DOT_I:
         case URX_LOOP_C:
         case URX_DOLLAR_D:
         case URX_DOLLAR_MD:
+        case URX_BACKSLASH_H:
+        case URX_BACKSLASH_R:
+        case URX_BACKSLASH_V:
             // These instructions are unaltered by the relocation.
             fRXPat->fCompiledPat->setElementAt(op, dst);
             dst++;
             break;
 
         default:
             // Some op is unaccounted for.
             U_ASSERT(FALSE);
             error(U_REGEX_INTERNAL_ERROR);
         }
@@ skipping 751 matching lines @@
 
 void RegexCompile::setPushOp(int32_t op) {
     setEval(op);
     fSetOpStack.push(op, *fStatus);
     fSetStack.push(new UnicodeSet(), *fStatus);
 }
 
 U_NAMESPACE_END
 #endif  // !UCONFIG_NO_REGULAR_EXPRESSIONS