icuSources/i18n/rematch.cpp

   1 // © 2016 and later: Unicode, Inc. and others.
   2 // License & terms of use: http://www.unicode.org/copyright.html
   3 /*
   4 **************************************************************************
   5 *   Copyright (C) 2002-2016 International Business Machines Corporation
   6 *   and others. All rights reserved.
   7 **************************************************************************
   8 */
   9 //
  10 //  file:  rematch.cpp
  11 //
  12 //         Contains the implementation of class RegexMatcher,
  13 //         which is one of the main API classes for the ICU regular expression package.
  14 //
  15
  16 #include "unicode/utypes.h"
  17 #if !UCONFIG_NO_REGULAR_EXPRESSIONS
  18
  19 #include "unicode/regex.h"
  20 #include "unicode/uniset.h"
  21 #include "unicode/uchar.h"
  22 #include "unicode/ustring.h"
  23 #include "unicode/rbbi.h"
  24 #include "unicode/utf.h"
  25 #include "unicode/utf16.h"
  26 #include "uassert.h"
  27 #include "cmemory.h"
  28 #include "cstr.h"
  29 #include "uvector.h"
  30 #include "uvectr32.h"
  31 #include "uvectr64.h"
  32 #include "regeximp.h"
  33 #include "regexst.h"
  34 #include "regextxt.h"
  35 #include "ucase.h"
  36
  37 // #include <malloc.h>        // Needed for heapcheck testing
  38
  39
  40 U_NAMESPACE_BEGIN
  41
  42 // Default limit for the size of the back track stack, to avoid system
  43 //    failures causedby heap exhaustion.  Units are in 32 bit words, not bytes.
  44 // This value puts ICU's limits higher than most other regexp implementations,
  45 //    which use recursion rather than the heap, and take more storage per
  46 //    backtrack point.
  47 //
  48 static const int32_t DEFAULT_BACKTRACK_STACK_CAPACITY = 8000000;
  49
  50 // Time limit counter constant.
  51 //   Time limits for expression evaluation are in terms of quanta of work by
  52 //   the engine, each of which is 10,000 state saves.
  53 //   This constant determines that state saves per tick number.
  54 static const int32_t TIMER_INITIAL_VALUE = 10000;
  55
  56
  57 // Test for any of the Unicode line terminating characters.
  58 static inline UBool isLineTerminator(UChar32 c) {
  59     if (c & ~(0x0a | 0x0b | 0x0c | 0x0d | 0x85 | 0x2028 | 0x2029)) {
  60         return false;
  61     }
  62     return (c<=0x0d && c>=0x0a) || c==0x85 || c==0x2028 || c==0x2029;
  63 }
  64
  65 //-----------------------------------------------------------------------------
  66 //
  67 //   Constructor and Destructor
  68 //
  69 //-----------------------------------------------------------------------------
  70 RegexMatcher::RegexMatcher(const RegexPattern *pat)  {
  71     fDeferredStatus = U_ZERO_ERROR;
  72     init(fDeferredStatus);
  73     if (U_FAILURE(fDeferredStatus)) {
  74         return;
  75     }
  76     if (pat==NULL) {
  77         fDeferredStatus = U_ILLEGAL_ARGUMENT_ERROR;
  78         return;
  79     }
  80     fPattern = pat;
  81     init2(RegexStaticSets::gStaticSets->fEmptyText, fDeferredStatus);
  82 }
  83
  84
  85
  86 RegexMatcher::RegexMatcher(const UnicodeString &regexp, const UnicodeString &input,
  87                            uint32_t flags, UErrorCode &status) {
  88     init(status);
  89     if (U_FAILURE(status)) {
  90         return;
  91     }
  92     UParseError    pe;
  93     fPatternOwned      = RegexPattern::compile(regexp, flags, pe, status);
  94     fPattern           = fPatternOwned;
  95
  96     UText inputText = UTEXT_INITIALIZER;
  97     utext_openConstUnicodeString(&inputText, &input, &status);
  98     init2(&inputText, status);
  99     utext_close(&inputText);
 100
 101     fInputUniStrMaybeMutable = TRUE;
 102 }
 103
 104
 105 RegexMatcher::RegexMatcher(UText *regexp, UText *input,
 106                            uint32_t flags, UErrorCode &status) {
 107     init(status);
 108     if (U_FAILURE(status)) {
 109         return;
 110     }
 111     UParseError    pe;
 112     fPatternOwned      = RegexPattern::compile(regexp, flags, pe, status);
 113     if (U_FAILURE(status)) {
 114         return;
 115     }
 116
 117     fPattern           = fPatternOwned;
 118     init2(input, status);
 119 }
 120
 121
 122 RegexMatcher::RegexMatcher(const UnicodeString &regexp,
 123                            uint32_t flags, UErrorCode &status) {
 124     init(status);
 125     if (U_FAILURE(status)) {
 126         return;
 127     }
 128     UParseError    pe;
 129     fPatternOwned      = RegexPattern::compile(regexp, flags, pe, status);
 130     if (U_FAILURE(status)) {
 131         return;
 132     }
 133     fPattern           = fPatternOwned;
 134     init2(RegexStaticSets::gStaticSets->fEmptyText, status);
 135 }
 136
 137 RegexMatcher::RegexMatcher(UText *regexp,
 138                            uint32_t flags, UErrorCode &status) {
 139     init(status);
 140     if (U_FAILURE(status)) {
 141         return;
 142     }
 143     UParseError    pe;
 144     fPatternOwned      = RegexPattern::compile(regexp, flags, pe, status);
 145         if (U_FAILURE(status)) {
 146         return;
 147     }
 148
 149     fPattern           = fPatternOwned;
 150     init2(RegexStaticSets::gStaticSets->fEmptyText, status);
 151 }
 152
 153
 154
 155
 156 RegexMatcher::~RegexMatcher() {
 157     delete fStack;
 158     if (fData != fSmallData) {
 159         uprv_free(fData);
 160         fData = NULL;
 161     }
 162     if (fPatternOwned) {
 163         delete fPatternOwned;
 164         fPatternOwned = NULL;
 165         fPattern = NULL;
 166     }
 167
 168     if (fInput) {
 169         delete fInput;
 170     }
 171     if (fInputText) {
 172         utext_close(fInputText);
 173     }
 174     if (fAltInputText) {
 175         utext_close(fAltInputText);
 176     }
 177
 178     #if UCONFIG_NO_BREAK_ITERATION==0
 179     delete fWordBreakItr;
 180     #endif
 181 }
 182
 183 //
 184 //   init()   common initialization for use by all constructors.
 185 //            Initialize all fields, get the object into a consistent state.
 186 //            This must be done even when the initial status shows an error,
 187 //            so that the object is initialized sufficiently well for the destructor
 188 //            to run safely.
 189 //
 190 void RegexMatcher::init(UErrorCode &status) {
 191     fPattern           = NULL;
 192     fPatternOwned      = NULL;
 193     fFrameSize         = 0;
 194     fRegionStart       = 0;
 195     fRegionLimit       = 0;
 196     fAnchorStart       = 0;
 197     fAnchorLimit       = 0;
 198     fLookStart         = 0;
 199     fLookLimit         = 0;
 200     fActiveStart       = 0;
 201     fActiveLimit       = 0;
 202     fTransparentBounds = FALSE;
 203     fAnchoringBounds   = TRUE;
 204     fMatch             = FALSE;
 205     fMatchStart        = 0;
 206     fMatchEnd          = 0;
 207     fLastMatchEnd      = -1;
 208     fAppendPosition    = 0;
 209     fHitEnd            = FALSE;
 210     fRequireEnd        = FALSE;
 211     fStack             = NULL;
 212     fFrame             = NULL;
 213     fTimeLimit         = 0;
 214     fTime              = 0;
 215     fTickCounter       = 0;
 216     fStackLimit        = DEFAULT_BACKTRACK_STACK_CAPACITY;
 217     fCallbackFn        = NULL;
 218     fCallbackContext   = NULL;
 219     fFindProgressCallbackFn      = NULL;
 220     fFindProgressCallbackContext = NULL;
 221     fTraceDebug        = FALSE;
 222     fDeferredStatus    = status;
 223     fData              = fSmallData;
 224     fWordBreakItr      = NULL;
 225
 226     fStack             = NULL;
 227     fInputText         = NULL;
 228     fAltInputText      = NULL;
 229     fInput             = NULL;
 230     fInputLength       = 0;
 231     fInputUniStrMaybeMutable = FALSE;
 232 }
 233
 234 //
 235 //  init2()   Common initialization for use by RegexMatcher constructors, part 2.
 236 //            This handles the common setup to be done after the Pattern is available.
 237 //
 238 void RegexMatcher::init2(UText *input, UErrorCode &status) {
 239     if (U_FAILURE(status)) {
 240         fDeferredStatus = status;
 241         return;
 242     }
 243
 244     if (fPattern->fDataSize > UPRV_LENGTHOF(fSmallData)) {
 245         fData = (int64_t *)uprv_malloc(fPattern->fDataSize * sizeof(int64_t));
 246         if (fData == NULL) {
 247             status = fDeferredStatus = U_MEMORY_ALLOCATION_ERROR;
 248             return;
 249         }
 250     }
 251
 252     fStack = new UVector64(status);
 253     if (fStack == NULL) {
 254         status = fDeferredStatus = U_MEMORY_ALLOCATION_ERROR;
 255         return;
 256     }
 257
 258     reset(input);
 259     setStackLimit(DEFAULT_BACKTRACK_STACK_CAPACITY, status);
 260     if (U_FAILURE(status)) {
 261         fDeferredStatus = status;
 262         return;
 263     }
 264 }
 265
 266
 267 static const UChar BACKSLASH  = 0x5c;
 268 static const UChar DOLLARSIGN = 0x24;
 269 static const UChar LEFTBRACKET = 0x7b;
 270 static const UChar RIGHTBRACKET = 0x7d;
 271
 272 //--------------------------------------------------------------------------------
 273 //
 274 //    appendReplacement
 275 //
 276 //--------------------------------------------------------------------------------
 277 RegexMatcher &RegexMatcher::appendReplacement(UnicodeString &dest,
 278                                               const UnicodeString &replacement,
 279                                               UErrorCode &status) {
 280     UText replacementText = UTEXT_INITIALIZER;
 281
 282     utext_openConstUnicodeString(&replacementText, &replacement, &status);
 283     if (U_SUCCESS(status)) {
 284         UText resultText = UTEXT_INITIALIZER;
 285         utext_openUnicodeString(&resultText, &dest, &status);
 286
 287         if (U_SUCCESS(status)) {
 288             appendReplacement(&resultText, &replacementText, status);
 289             utext_close(&resultText);
 290         }
 291         utext_close(&replacementText);
 292     }
 293
 294     return *this;
 295 }
 296
 297 //
 298 //    appendReplacement, UText mode
 299 //
 300 RegexMatcher &RegexMatcher::appendReplacement(UText *dest,
 301                                               UText *replacement,
 302                                               UErrorCode &status) {
 303     if (U_FAILURE(status)) {
 304         return *this;
 305     }
 306     if (U_FAILURE(fDeferredStatus)) {
 307         status = fDeferredStatus;
 308         return *this;
 309     }
 310     if (fMatch == FALSE) {
 311         status = U_REGEX_INVALID_STATE;
 312         return *this;
 313     }
 314
 315     // Copy input string from the end of previous match to start of current match
 316     int64_t  destLen = utext_nativeLength(dest);
 317     if (fMatchStart > fAppendPosition) {
 318         if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) {
 319             destLen += utext_replace(dest, destLen, destLen, fInputText->chunkContents+fAppendPosition,
 320                                      (int32_t)(fMatchStart-fAppendPosition), &status);
 321         } else {
 322             int32_t len16;
 323             if (UTEXT_USES_U16(fInputText)) {
 324                 len16 = (int32_t)(fMatchStart-fAppendPosition);
 325             } else {
 326                 UErrorCode lengthStatus = U_ZERO_ERROR;
 327                 len16 = utext_extract(fInputText, fAppendPosition, fMatchStart, NULL, 0, &lengthStatus);
 328             }
 329             UChar *inputChars = (UChar *)uprv_malloc(sizeof(UChar)*(len16+1));
 330             if (inputChars == NULL) {
 331                 status = U_MEMORY_ALLOCATION_ERROR;
 332                 return *this;
 333             }
 334             utext_extract(fInputText, fAppendPosition, fMatchStart, inputChars, len16+1, &status);
 335             destLen += utext_replace(dest, destLen, destLen, inputChars, len16, &status);
 336             uprv_free(inputChars);
 337         }
 338     }
 339     fAppendPosition = fMatchEnd;
 340
 341
 342     // scan the replacement text, looking for substitutions ($n) and \escapes.
 343     //  TODO:  optimize this loop by efficiently scanning for '$' or '\',
 344     //         move entire ranges not containing substitutions.
 345     UTEXT_SETNATIVEINDEX(replacement, 0);
 346     for (UChar32 c = UTEXT_NEXT32(replacement); U_SUCCESS(status) && c != U_SENTINEL;  c = UTEXT_NEXT32(replacement)) {
 347         if (c == BACKSLASH) {
 348             // Backslash Escape.  Copy the following char out without further checks.
 349             //                    Note:  Surrogate pairs don't need any special handling
 350             //                           The second half wont be a '$' or a '\', and
 351             //                           will move to the dest normally on the next
 352             //                           loop iteration.
 353             c = UTEXT_CURRENT32(replacement);
 354             if (c == U_SENTINEL) {
 355                 break;
 356             }
 357
 358             if (c==0x55/*U*/ || c==0x75/*u*/) {
 359                 // We have a \udddd or \Udddddddd escape sequence.
 360                 int32_t offset = 0;
 361                 struct URegexUTextUnescapeCharContext context = U_REGEX_UTEXT_UNESCAPE_CONTEXT(replacement);
 362                 UChar32 escapedChar = u_unescapeAt(uregex_utext_unescape_charAt, &offset, INT32_MAX, &context);
 363                 if (escapedChar != (UChar32)0xFFFFFFFF) {
 364                     if (U_IS_BMP(escapedChar)) {
 365                         UChar c16 = (UChar)escapedChar;
 366                         destLen += utext_replace(dest, destLen, destLen, &c16, 1, &status);
 367                     } else {
 368                         UChar surrogate[2];
 369                         surrogate[0] = U16_LEAD(escapedChar);
 370                         surrogate[1] = U16_TRAIL(escapedChar);
 371                         if (U_SUCCESS(status)) {
 372                             destLen += utext_replace(dest, destLen, destLen, surrogate, 2, &status);
 373                         }
 374                     }
 375                     // TODO:  Report errors for mal-formed \u escapes?
 376                     //        As this is, the original sequence is output, which may be OK.
 377                     if (context.lastOffset == offset) {
 378                         (void)UTEXT_PREVIOUS32(replacement);
 379                     } else if (context.lastOffset != offset-1) {
 380                         utext_moveIndex32(replacement, offset - context.lastOffset - 1);
 381                     }
 382                 }
 383             } else {
 384                 (void)UTEXT_NEXT32(replacement);
 385                 // Plain backslash escape.  Just put out the escaped character.
 386                 if (U_IS_BMP(c)) {
 387                     UChar c16 = (UChar)c;
 388                     destLen += utext_replace(dest, destLen, destLen, &c16, 1, &status);
 389                 } else {
 390                     UChar surrogate[2];
 391                     surrogate[0] = U16_LEAD(c);
 392                     surrogate[1] = U16_TRAIL(c);
 393                     if (U_SUCCESS(status)) {
 394                         destLen += utext_replace(dest, destLen, destLen, surrogate, 2, &status);
 395                     }
 396                 }
 397             }
 398         } else if (c != DOLLARSIGN) {
 399             // Normal char, not a $.  Copy it out without further checks.
 400             if (U_IS_BMP(c)) {
 401                 UChar c16 = (UChar)c;
 402                 destLen += utext_replace(dest, destLen, destLen, &c16, 1, &status);
 403             } else {
 404                 UChar surrogate[2];
 405                 surrogate[0] = U16_LEAD(c);
 406                 surrogate[1] = U16_TRAIL(c);
 407                 if (U_SUCCESS(status)) {
 408                     destLen += utext_replace(dest, destLen, destLen, surrogate, 2, &status);
 409                 }
 410             }
 411         } else {
 412             // We've got a $.  Pick up a capture group name or number if one follows.
 413             // Consume digits so long as the resulting group number <= the number of
 414             // number of capture groups in the pattern.
 415
 416             int32_t groupNum  = 0;
 417             int32_t numDigits = 0;
 418             UChar32 nextChar = utext_current32(replacement);
 419             if (nextChar == LEFTBRACKET) {
 420                 // Scan for a Named Capture Group, ${name}.
 421                 UnicodeString groupName;
 422                 utext_next32(replacement);
 423                 while(U_SUCCESS(status) && nextChar != RIGHTBRACKET) {
 424                     nextChar = utext_next32(replacement);
 425                     if (nextChar == U_SENTINEL) {
 426                         status = U_REGEX_INVALID_CAPTURE_GROUP_NAME;
 427                     } else if ((nextChar >= 0x41 && nextChar <= 0x5a) ||       // A..Z
 428                                (nextChar >= 0x61 && nextChar <= 0x7a) ||       // a..z
 429                                (nextChar >= 0x31 && nextChar <= 0x39)) {       // 0..9
 430                         groupName.append(nextChar);
 431                     } else if (nextChar == RIGHTBRACKET) {
 432                         groupNum = uhash_geti(fPattern->fNamedCaptureMap, &groupName);
 433                         if (groupNum == 0) {
 434                             status = U_REGEX_INVALID_CAPTURE_GROUP_NAME;
 435                         }
 436                     } else {
 437                         // Character was something other than a name char or a closing '}'
 438                         status = U_REGEX_INVALID_CAPTURE_GROUP_NAME;
 439                     }
 440                 }
 441
 442             } else if (u_isdigit(nextChar)) {
 443                 // $n    Scan for a capture group number
 444                 int32_t numCaptureGroups = fPattern->fGroupMap->size();
 445                 for (;;) {
 446                     nextChar = UTEXT_CURRENT32(replacement);
 447                     if (nextChar == U_SENTINEL) {
 448                         break;
 449                     }
 450                     if (u_isdigit(nextChar) == FALSE) {
 451                         break;
 452                     }
 453                     int32_t nextDigitVal = u_charDigitValue(nextChar);
 454                     if (groupNum*10 + nextDigitVal > numCaptureGroups) {
 455                         // Don't consume the next digit if it makes the capture group number too big.
 456                         if (numDigits == 0) {
 457                             status = U_INDEX_OUTOFBOUNDS_ERROR;
 458                         }
 459                         break;
 460                     }
 461                     (void)UTEXT_NEXT32(replacement);
 462                     groupNum=groupNum*10 + nextDigitVal;
 463                     ++numDigits;
 464                 }
 465             } else {
 466                 // $ not followed by capture group name or number.
 467                 status = U_REGEX_INVALID_CAPTURE_GROUP_NAME;
 468             }
 469
 470             if (U_SUCCESS(status)) {
 471                 destLen += appendGroup(groupNum, dest, status);
 472             }
 473         }  // End of $ capture group handling
 474     }  // End of per-character loop through the replacement string.
 475
 476     return *this;
 477 }
 478
 479
 480
 481 //--------------------------------------------------------------------------------
 482 //
 483 //    appendTail     Intended to be used in conjunction with appendReplacement()
 484 //                   To the destination string, append everything following
 485 //                   the last match position from the input string.
 486 //
 487 //                   Note:  Match ranges do not affect appendTail or appendReplacement
 488 //
 489 //--------------------------------------------------------------------------------
 490 UnicodeString &RegexMatcher::appendTail(UnicodeString &dest) {
 491     UErrorCode status = U_ZERO_ERROR;
 492     UText resultText = UTEXT_INITIALIZER;
 493     utext_openUnicodeString(&resultText, &dest, &status);
 494
 495     if (U_SUCCESS(status)) {
 496         appendTail(&resultText, status);
 497         utext_close(&resultText);
 498     }
 499
 500     return dest;
 501 }
 502
 503 //
 504 //   appendTail, UText mode
 505 //
 506 UText *RegexMatcher::appendTail(UText *dest, UErrorCode &status) {
 507     if (U_FAILURE(status)) {
 508         return dest;
 509     }
 510     if (U_FAILURE(fDeferredStatus)) {
 511         status = fDeferredStatus;
 512         return dest;
 513     }
 514
 515     if (fInputLength > fAppendPosition) {
 516         if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) {
 517             int64_t destLen = utext_nativeLength(dest);
 518             utext_replace(dest, destLen, destLen, fInputText->chunkContents+fAppendPosition,
 519                           (int32_t)(fInputLength-fAppendPosition), &status);
 520         } else {
 521             int32_t len16;
 522             if (UTEXT_USES_U16(fInputText)) {
 523                 len16 = (int32_t)(fInputLength-fAppendPosition);
 524             } else {
 525                 len16 = utext_extract(fInputText, fAppendPosition, fInputLength, NULL, 0, &status);
 526                 status = U_ZERO_ERROR; // buffer overflow
 527             }
 528
 529             UChar *inputChars = (UChar *)uprv_malloc(sizeof(UChar)*(len16));
 530             if (inputChars == NULL) {
 531                 fDeferredStatus = U_MEMORY_ALLOCATION_ERROR;
 532             } else {
 533                 utext_extract(fInputText, fAppendPosition, fInputLength, inputChars, len16, &status); // unterminated
 534                 int64_t destLen = utext_nativeLength(dest);
 535                 utext_replace(dest, destLen, destLen, inputChars, len16, &status);
 536                 uprv_free(inputChars);
 537             }
 538         }
 539     }
 540     return dest;
 541 }
 542
 543
 544
 545 //--------------------------------------------------------------------------------
 546 //
 547 //   end
 548 //
 549 //--------------------------------------------------------------------------------
 550 int32_t RegexMatcher::end(UErrorCode &err) const {
 551     return end(0, err);
 552 }
 553
 554 int64_t RegexMatcher::end64(UErrorCode &err) const {
 555     return end64(0, err);
 556 }
 557
 558 int64_t RegexMatcher::end64(int32_t group, UErrorCode &err) const {
 559     if (U_FAILURE(err)) {
 560         return -1;
 561     }
 562     if (fMatch == FALSE) {
 563         err = U_REGEX_INVALID_STATE;
 564         return -1;
 565     }
 566     if (group < 0 || group > fPattern->fGroupMap->size()) {
 567         err = U_INDEX_OUTOFBOUNDS_ERROR;
 568         return -1;
 569     }
 570     int64_t e = -1;
 571     if (group == 0) {
 572         e = fMatchEnd;
 573     } else {
 574         // Get the position within the stack frame of the variables for
 575         //    this capture group.
 576         int32_t groupOffset = fPattern->fGroupMap->elementAti(group-1);
 577         U_ASSERT(groupOffset < fPattern->fFrameSize);
 578         U_ASSERT(groupOffset >= 0);
 579         e = fFrame->fExtra[groupOffset + 1];
 580     }
 581
 582         return e;
 583 }
 584
 585 int32_t RegexMatcher::end(int32_t group, UErrorCode &err) const {
 586     return (int32_t)end64(group, err);
 587 }
 588
 589 //--------------------------------------------------------------------------------
 590 //
 591 //   findProgressInterrupt  This function is called once for each advance in the target
 592 //                          string from the find() function, and calls the user progress callback
 593 //                          function if there is one installed.
 594 //
 595 //         Return:  TRUE if the find operation is to be terminated.
 596 //                  FALSE if the find operation is to continue running.
 597 //
 598 //--------------------------------------------------------------------------------
 599 UBool RegexMatcher::findProgressInterrupt(int64_t pos, UErrorCode &status) {
 600     if (fFindProgressCallbackFn && !(*fFindProgressCallbackFn)(fFindProgressCallbackContext, pos)) {
 601         status = U_REGEX_STOPPED_BY_CALLER;
 602         return TRUE;
 603     }
 604     return FALSE;
 605 }
 606
 607 //--------------------------------------------------------------------------------
 608 //
 609 //   find()
 610 //
 611 //--------------------------------------------------------------------------------
 612 UBool RegexMatcher::find() {
 613     if (U_FAILURE(fDeferredStatus)) {
 614         return FALSE;
 615     }
 616     UErrorCode status = U_ZERO_ERROR;
 617     UBool result = find(status);
 618     return result;
 619 }
 620
 621 //--------------------------------------------------------------------------------
 622 //
 623 //   find()
 624 //
 625 //--------------------------------------------------------------------------------
 626 UBool RegexMatcher::find(UErrorCode &status) {
 627     // Start at the position of the last match end.  (Will be zero if the
 628     //   matcher has been reset.)
 629     //
 630     if (U_FAILURE(status)) {
 631         return FALSE;
 632     }
 633     if (U_FAILURE(fDeferredStatus)) {
 634         status = fDeferredStatus;
 635         return FALSE;
 636     }
 637
 638     if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) {
 639         return findUsingChunk(status);
 640     }
 641
 642     int64_t startPos = fMatchEnd;
 643     if (startPos==0) {
 644         startPos = fActiveStart;
 645     }
 646
 647     if (fMatch) {
 648         // Save the position of any previous successful match.
 649         fLastMatchEnd = fMatchEnd;
 650
 651         if (fMatchStart == fMatchEnd) {
 652             // Previous match had zero length.  Move start position up one position
 653             //  to avoid sending find() into a loop on zero-length matches.
 654             if (startPos >= fActiveLimit) {
 655                 fMatch = FALSE;
 656                 fHitEnd = TRUE;
 657                 return FALSE;
 658             }
 659             UTEXT_SETNATIVEINDEX(fInputText, startPos);
 660             (void)UTEXT_NEXT32(fInputText);
 661             startPos = UTEXT_GETNATIVEINDEX(fInputText);
 662         }
 663     } else {
 664         if (fLastMatchEnd >= 0) {
 665             // A previous find() failed to match.  Don't try again.
 666             //   (without this test, a pattern with a zero-length match
 667             //    could match again at the end of an input string.)
 668             fHitEnd = TRUE;
 669             return FALSE;
 670         }
 671     }
 672
 673
 674     // Compute the position in the input string beyond which a match can not begin, because
 675     //   the minimum length match would extend past the end of the input.
 676     //   Note:  some patterns that cannot match anything will have fMinMatchLength==Max Int.
 677     //          Be aware of possible overflows if making changes here.
 678     int64_t testStartLimit;
 679     if (UTEXT_USES_U16(fInputText)) {
 680         testStartLimit = fActiveLimit - fPattern->fMinMatchLen;
 681         if (startPos > testStartLimit) {
 682             fMatch = FALSE;
 683             fHitEnd = TRUE;
 684             return FALSE;
 685         }
 686     } else {
 687         // We don't know exactly how long the minimum match length is in native characters.
 688         // Treat anything > 0 as 1.
 689         testStartLimit = fActiveLimit - (fPattern->fMinMatchLen > 0 ? 1 : 0);
 690     }
 691
 692     UChar32  c;
 693     U_ASSERT(startPos >= 0);
 694
 695     switch (fPattern->fStartType) {
 696     case START_NO_INFO:
 697         // No optimization was found.
 698         //  Try a match at each input position.
 699         for (;;) {
 700             MatchAt(startPos, FALSE, status);
 701             if (U_FAILURE(status)) {
 702                 return FALSE;
 703             }
 704             if (fMatch) {
 705                 return TRUE;
 706             }
 707             if (startPos >= testStartLimit) {
 708                 fHitEnd = TRUE;
 709                 return FALSE;
 710             }
 711             UTEXT_SETNATIVEINDEX(fInputText, startPos);
 712             (void)UTEXT_NEXT32(fInputText);
 713             startPos = UTEXT_GETNATIVEINDEX(fInputText);
 714             // Note that it's perfectly OK for a pattern to have a zero-length
 715             //   match at the end of a string, so we must make sure that the loop
 716             //   runs with startPos == testStartLimit the last time through.
 717             if  (findProgressInterrupt(startPos, status))
 718                 return FALSE;
 719         }
 720         UPRV_UNREACHABLE;
 721
 722     case START_START:
 723         // Matches are only possible at the start of the input string
 724         //   (pattern begins with ^ or \A)
 725         if (startPos > fActiveStart) {
 726             fMatch = FALSE;
 727             return FALSE;
 728         }
 729         MatchAt(startPos, FALSE, status);
 730         if (U_FAILURE(status)) {
 731             return FALSE;
 732         }
 733         return fMatch;
 734
 735
 736     case START_SET:
 737         {
 738             // Match may start on any char from a pre-computed set.
 739             U_ASSERT(fPattern->fMinMatchLen > 0);
 740             UTEXT_SETNATIVEINDEX(fInputText, startPos);
 741             for (;;) {
 742                 int64_t pos = startPos;
 743                 c = UTEXT_NEXT32(fInputText);
 744                 startPos = UTEXT_GETNATIVEINDEX(fInputText);
 745                 // c will be -1 (U_SENTINEL) at end of text, in which case we
 746                 // skip this next block (so we don't have a negative array index)
 747                 // and handle end of text in the following block.
 748                 if (c >= 0 && ((c<256 && fPattern->fInitialChars8->contains(c)) ||
 749                               (c>=256 && fPattern->fInitialChars->contains(c)))) {
 750                     MatchAt(pos, FALSE, status);
 751                     if (U_FAILURE(status)) {
 752                         return FALSE;
 753                     }
 754                     if (fMatch) {
 755                         return TRUE;
 756                     }
 757                     UTEXT_SETNATIVEINDEX(fInputText, pos);
 758                 }
 759                 if (startPos > testStartLimit) {
 760                     fMatch = FALSE;
 761                     fHitEnd = TRUE;
 762                     return FALSE;
 763                 }
 764                 if  (findProgressInterrupt(startPos, status))
 765                     return FALSE;
 766             }
 767         }
 768         UPRV_UNREACHABLE;
 769
 770     case START_STRING:
 771     case START_CHAR:
 772         {
 773             // Match starts on exactly one char.
 774             U_ASSERT(fPattern->fMinMatchLen > 0);
 775             UChar32 theChar = fPattern->fInitialChar;
 776             UTEXT_SETNATIVEINDEX(fInputText, startPos);
 777             for (;;) {
 778                 int64_t pos = startPos;
 779                 c = UTEXT_NEXT32(fInputText);
 780                 startPos = UTEXT_GETNATIVEINDEX(fInputText);
 781                 if (c == theChar) {
 782                     MatchAt(pos, FALSE, status);
 783                     if (U_FAILURE(status)) {
 784                         return FALSE;
 785                     }
 786                     if (fMatch) {
 787                         return TRUE;
 788                     }
 789                     UTEXT_SETNATIVEINDEX(fInputText, startPos);
 790                 }
 791                 if (startPos > testStartLimit) {
 792                     fMatch = FALSE;
 793                     fHitEnd = TRUE;
 794                     return FALSE;
 795                 }
 796                 if  (findProgressInterrupt(startPos, status))
 797                     return FALSE;
 798            }
 799         }
 800         UPRV_UNREACHABLE;
 801
 802     case START_LINE:
 803         {
 804             UChar32 ch;
 805             if (startPos == fAnchorStart) {
 806                 MatchAt(startPos, FALSE, status);
 807                 if (U_FAILURE(status)) {
 808                     return FALSE;
 809                 }
 810                 if (fMatch) {
 811                     return TRUE;
 812                 }
 813                 UTEXT_SETNATIVEINDEX(fInputText, startPos);
 814                 ch = UTEXT_NEXT32(fInputText);
 815                 startPos = UTEXT_GETNATIVEINDEX(fInputText);
 816             } else {
 817                 UTEXT_SETNATIVEINDEX(fInputText, startPos);
 818                 ch = UTEXT_PREVIOUS32(fInputText);
 819                 UTEXT_SETNATIVEINDEX(fInputText, startPos);
 820             }
 821
 822             if (fPattern->fFlags & UREGEX_UNIX_LINES) {
 823                 for (;;) {
 824                     if (ch == 0x0a) {
 825                             MatchAt(startPos, FALSE, status);
 826                             if (U_FAILURE(status)) {
 827                                 return FALSE;
 828                             }
 829                             if (fMatch) {
 830                                 return TRUE;
 831                             }
 832                             UTEXT_SETNATIVEINDEX(fInputText, startPos);
 833                     }
 834                     if (startPos >= testStartLimit) {
 835                         fMatch = FALSE;
 836                         fHitEnd = TRUE;
 837                         return FALSE;
 838                     }
 839                     ch = UTEXT_NEXT32(fInputText);
 840                     startPos = UTEXT_GETNATIVEINDEX(fInputText);
 841                     // Note that it's perfectly OK for a pattern to have a zero-length
 842                     //   match at the end of a string, so we must make sure that the loop
 843                     //   runs with startPos == testStartLimit the last time through.
 844                     if  (findProgressInterrupt(startPos, status))
 845                         return FALSE;
 846                 }
 847             } else {
 848                 for (;;) {
 849                     if (isLineTerminator(ch)) {
 850                         if (ch == 0x0d && startPos < fActiveLimit && UTEXT_CURRENT32(fInputText) == 0x0a) {
 851                             (void)UTEXT_NEXT32(fInputText);
 852                             startPos = UTEXT_GETNATIVEINDEX(fInputText);
 853                         }
 854                         MatchAt(startPos, FALSE, status);
 855                         if (U_FAILURE(status)) {
 856                             return FALSE;
 857                         }
 858                         if (fMatch) {
 859                             return TRUE;
 860                         }
 861                         UTEXT_SETNATIVEINDEX(fInputText, startPos);
 862                     }
 863                     if (startPos >= testStartLimit) {
 864                         fMatch = FALSE;
 865                         fHitEnd = TRUE;
 866                         return FALSE;
 867                     }
 868                     ch = UTEXT_NEXT32(fInputText);
 869                     startPos = UTEXT_GETNATIVEINDEX(fInputText);
 870                     // Note that it's perfectly OK for a pattern to have a zero-length
 871                     //   match at the end of a string, so we must make sure that the loop
 872                     //   runs with startPos == testStartLimit the last time through.
 873                     if  (findProgressInterrupt(startPos, status))
 874                         return FALSE;
 875                 }
 876             }
 877         }
 878
 879     default:
 880         UPRV_UNREACHABLE;
 881     }
 882
 883     UPRV_UNREACHABLE;
 884 }
 885
 886
 887
 888 UBool RegexMatcher::find(int64_t start, UErrorCode &status) {
 889     if (U_FAILURE(status)) {
 890         return FALSE;
 891     }
 892     if (U_FAILURE(fDeferredStatus)) {
 893         status = fDeferredStatus;
 894         return FALSE;
 895     }
 896     this->reset();                        // Note:  Reset() is specified by Java Matcher documentation.
 897                                           //        This will reset the region to be the full input length.
 898     if (start < 0) {
 899         status = U_INDEX_OUTOFBOUNDS_ERROR;
 900         return FALSE;
 901     }
 902
 903     int64_t nativeStart = start;
 904     if (nativeStart < fActiveStart || nativeStart > fActiveLimit) {
 905         status = U_INDEX_OUTOFBOUNDS_ERROR;
 906         return FALSE;
 907     }
 908     fMatchEnd = nativeStart;
 909     return find(status);
 910 }
 911
 912
 913 //--------------------------------------------------------------------------------
 914 //
 915 //   findUsingChunk() -- like find(), but with the advance knowledge that the
 916 //                       entire string is available in the UText's chunk buffer.
 917 //
 918 //--------------------------------------------------------------------------------
 919 UBool RegexMatcher::findUsingChunk(UErrorCode &status) {
 920     // Start at the position of the last match end.  (Will be zero if the
 921     //   matcher has been reset.
 922     //
 923
 924     int32_t startPos = (int32_t)fMatchEnd;
 925     if (startPos==0) {
 926         startPos = (int32_t)fActiveStart;
 927     }
 928
 929     const UChar *inputBuf = fInputText->chunkContents;
 930
 931     if (fMatch) {
 932         // Save the position of any previous successful match.
 933         fLastMatchEnd = fMatchEnd;
 934
 935         if (fMatchStart == fMatchEnd) {
 936             // Previous match had zero length.  Move start position up one position
 937             //  to avoid sending find() into a loop on zero-length matches.
 938             if (startPos >= fActiveLimit) {
 939                 fMatch = FALSE;
 940                 fHitEnd = TRUE;
 941                 return FALSE;
 942             }
 943             U16_FWD_1(inputBuf, startPos, fInputLength);
 944         }
 945     } else {
 946         if (fLastMatchEnd >= 0) {
 947             // A previous find() failed to match.  Don't try again.
 948             //   (without this test, a pattern with a zero-length match
 949             //    could match again at the end of an input string.)
 950             fHitEnd = TRUE;
 951             return FALSE;
 952         }
 953     }
 954
 955
 956     // Compute the position in the input string beyond which a match can not begin, because
 957     //   the minimum length match would extend past the end of the input.
 958     //   Note:  some patterns that cannot match anything will have fMinMatchLength==Max Int.
 959     //          Be aware of possible overflows if making changes here.
 960     //   Note:  a match can begin at inputBuf + testLen; it is an inclusive limit.
 961     int32_t testLen  = (int32_t)(fActiveLimit - fPattern->fMinMatchLen);
 962     if (startPos > testLen) {
 963         fMatch = FALSE;
 964         fHitEnd = TRUE;
 965         return FALSE;
 966     }
 967
 968     UChar32  c;
 969     U_ASSERT(startPos >= 0);
 970
 971     switch (fPattern->fStartType) {
 972     case START_NO_INFO:
 973         // No optimization was found.
 974         //  Try a match at each input position.
 975         for (;;) {
 976             MatchChunkAt(startPos, FALSE, status);
 977             if (U_FAILURE(status)) {
 978                 return FALSE;
 979             }
 980             if (fMatch) {
 981                 return TRUE;
 982             }
 983             if (startPos >= testLen) {
 984                 fHitEnd = TRUE;
 985                 return FALSE;
 986             }
 987             U16_FWD_1(inputBuf, startPos, fActiveLimit);
 988             // Note that it's perfectly OK for a pattern to have a zero-length
 989             //   match at the end of a string, so we must make sure that the loop
 990             //   runs with startPos == testLen the last time through.
 991             if  (findProgressInterrupt(startPos, status))
 992                 return FALSE;
 993         }
 994         UPRV_UNREACHABLE;
 995
 996     case START_START:
 997         // Matches are only possible at the start of the input string
 998         //   (pattern begins with ^ or \A)
 999         if (startPos > fActiveStart) {
1000             fMatch = FALSE;
1001             return FALSE;
1002         }
1003         MatchChunkAt(startPos, FALSE, status);
1004         if (U_FAILURE(status)) {
1005             return FALSE;
1006         }
1007         return fMatch;
1008
1009
1010     case START_SET:
1011     {
1012         // Match may start on any char from a pre-computed set.
1013         U_ASSERT(fPattern->fMinMatchLen > 0);
1014         for (;;) {
1015             int32_t pos = startPos;
1016             U16_NEXT(inputBuf, startPos, fActiveLimit, c);  // like c = inputBuf[startPos++];
1017             if ((c<256 && fPattern->fInitialChars8->contains(c)) ||
1018                 (c>=256 && fPattern->fInitialChars->contains(c))) {
1019                 MatchChunkAt(pos, FALSE, status);
1020                 if (U_FAILURE(status)) {
1021                     return FALSE;
1022                 }
1023                 if (fMatch) {
1024                     return TRUE;
1025                 }
1026             }
1027             if (startPos > testLen) {
1028                 fMatch = FALSE;
1029                 fHitEnd = TRUE;
1030                 return FALSE;
1031             }
1032             if  (findProgressInterrupt(startPos, status))
1033                 return FALSE;
1034         }
1035     }
1036     UPRV_UNREACHABLE;
1037
1038     case START_STRING:
1039     case START_CHAR:
1040     {
1041         // Match starts on exactly one char.
1042         U_ASSERT(fPattern->fMinMatchLen > 0);
1043         UChar32 theChar = fPattern->fInitialChar;
1044         for (;;) {
1045             int32_t pos = startPos;
1046             U16_NEXT(inputBuf, startPos, fActiveLimit, c);  // like c = inputBuf[startPos++];
1047             if (c == theChar) {
1048                 MatchChunkAt(pos, FALSE, status);
1049                 if (U_FAILURE(status)) {
1050                     return FALSE;
1051                 }
1052                 if (fMatch) {
1053                     return TRUE;
1054                 }
1055             }
1056             if (startPos > testLen) {
1057                 fMatch = FALSE;
1058                 fHitEnd = TRUE;
1059                 return FALSE;
1060             }
1061             if  (findProgressInterrupt(startPos, status))
1062                 return FALSE;
1063         }
1064     }
1065     UPRV_UNREACHABLE;
1066
1067     case START_LINE:
1068     {
1069         UChar32 ch;
1070         if (startPos == fAnchorStart) {
1071             MatchChunkAt(startPos, FALSE, status);
1072             if (U_FAILURE(status)) {
1073                 return FALSE;
1074             }
1075             if (fMatch) {
1076                 return TRUE;
1077             }
1078             // In bug 31063104 which has a zero-length text buffer we get here with
1079             // inputBuf=NULL, startPos=fActiveLimit=0 (and fMatch F) which violates the
1080             // requirement for U16_FWD_1 (utf16.h) that startPos < fActiveLimit. Having
1081             // inputBuf=NULL (chunkContexts NULL) is probably due to an error in the
1082             // CFStringUText functions. Nevertheless, to be defensive, add test below.
1083             if (startPos >= testLen) {
1084                 fHitEnd = TRUE;
1085                 return FALSE;
1086             }
1087             U16_FWD_1(inputBuf, startPos, fActiveLimit);
1088         }
1089
1090         if (fPattern->fFlags & UREGEX_UNIX_LINES) {
1091             for (;;) {
1092                 ch = inputBuf[startPos-1];
1093                 if (ch == 0x0a) {
1094                     MatchChunkAt(startPos, FALSE, status);
1095                     if (U_FAILURE(status)) {
1096                         return FALSE;
1097                     }
1098                     if (fMatch) {
1099                         return TRUE;
1100                     }
1101                 }
1102                 if (startPos >= testLen) {
1103                     fMatch = FALSE;
1104                     fHitEnd = TRUE;
1105                     return FALSE;
1106                 }
1107                 U16_FWD_1(inputBuf, startPos, fActiveLimit);
1108                 // Note that it's perfectly OK for a pattern to have a zero-length
1109                 //   match at the end of a string, so we must make sure that the loop
1110                 //   runs with startPos == testLen the last time through.
1111                 if  (findProgressInterrupt(startPos, status))
1112                     return FALSE;
1113             }
1114         } else {
1115             for (;;) {
1116                 ch = inputBuf[startPos-1];
1117                 if (isLineTerminator(ch)) {
1118                     if (ch == 0x0d && startPos < fActiveLimit && inputBuf[startPos] == 0x0a) {
1119                         startPos++;
1120                     }
1121                     MatchChunkAt(startPos, FALSE, status);
1122                     if (U_FAILURE(status)) {
1123                         return FALSE;
1124                     }
1125                     if (fMatch) {
1126                         return TRUE;
1127                     }
1128                 }
1129                 if (startPos >= testLen) {
1130                     fMatch = FALSE;
1131                     fHitEnd = TRUE;
1132                     return FALSE;
1133                 }
1134                 U16_FWD_1(inputBuf, startPos, fActiveLimit);
1135                 // Note that it's perfectly OK for a pattern to have a zero-length
1136                 //   match at the end of a string, so we must make sure that the loop
1137                 //   runs with startPos == testLen the last time through.
1138                 if  (findProgressInterrupt(startPos, status))
1139                     return FALSE;
1140             }
1141         }
1142     }
1143
1144     default:
1145         UPRV_UNREACHABLE;
1146     }
1147
1148     UPRV_UNREACHABLE;
1149 }
1150
1151
1152
1153 //--------------------------------------------------------------------------------
1154 //
1155 //  group()
1156 //
1157 //--------------------------------------------------------------------------------
1158 UnicodeString RegexMatcher::group(UErrorCode &status) const {
1159     return group(0, status);
1160 }
1161
1162 //  Return immutable shallow clone
1163 UText *RegexMatcher::group(UText *dest, int64_t &group_len, UErrorCode &status) const {
1164     return group(0, dest, group_len, status);
1165 }
1166
1167 //  Return immutable shallow clone
1168 UText *RegexMatcher::group(int32_t groupNum, UText *dest, int64_t &group_len, UErrorCode &status) const {
1169     group_len = 0;
1170     if (U_FAILURE(status)) {
1171         return dest;
1172     }
1173     if (U_FAILURE(fDeferredStatus)) {
1174         status = fDeferredStatus;
1175     } else if (fMatch == FALSE) {
1176         status = U_REGEX_INVALID_STATE;
1177     } else if (groupNum < 0 || groupNum > fPattern->fGroupMap->size()) {
1178         status = U_INDEX_OUTOFBOUNDS_ERROR;
1179     }
1180
1181     if (U_FAILURE(status)) {
1182         return dest;
1183     }
1184
1185     int64_t s, e;
1186     if (groupNum == 0) {
1187         s = fMatchStart;
1188         e = fMatchEnd;
1189     } else {
1190         int32_t groupOffset = fPattern->fGroupMap->elementAti(groupNum-1);
1191         U_ASSERT(groupOffset < fPattern->fFrameSize);
1192         U_ASSERT(groupOffset >= 0);
1193         s = fFrame->fExtra[groupOffset];
1194         e = fFrame->fExtra[groupOffset+1];
1195     }
1196
1197     if (s < 0) {
1198         // A capture group wasn't part of the match
1199         return utext_clone(dest, fInputText, FALSE, TRUE, &status);
1200     }
1201     U_ASSERT(s <= e);
1202     group_len = e - s;
1203
1204     dest = utext_clone(dest, fInputText, FALSE, TRUE, &status);
1205     if (dest)
1206         UTEXT_SETNATIVEINDEX(dest, s);
1207     return dest;
1208 }
1209
1210 UnicodeString RegexMatcher::group(int32_t groupNum, UErrorCode &status) const {
1211     UnicodeString result;
1212     int64_t groupStart = start64(groupNum, status);
1213     int64_t groupEnd = end64(groupNum, status);
1214     if (U_FAILURE(status) || groupStart == -1 || groupStart == groupEnd) {
1215         return result;
1216     }
1217
1218     // Get the group length using a utext_extract preflight.
1219     //    UText is actually pretty efficient at this when underlying encoding is UTF-16.
1220     int32_t length = utext_extract(fInputText, groupStart, groupEnd, NULL, 0, &status);
1221     if (status != U_BUFFER_OVERFLOW_ERROR) {
1222         return result;
1223     }
1224
1225     status = U_ZERO_ERROR;
1226     UChar *buf = result.getBuffer(length);
1227     if (buf == NULL) {
1228         status = U_MEMORY_ALLOCATION_ERROR;
1229     } else {
1230         int32_t extractLength = utext_extract(fInputText, groupStart, groupEnd, buf, length, &status);
1231         result.releaseBuffer(extractLength);
1232         U_ASSERT(length == extractLength);
1233     }
1234     return result;
1235 }
1236
1237
1238 //--------------------------------------------------------------------------------
1239 //
1240 //  appendGroup() -- currently internal only, appends a group to a UText rather
1241 //                   than replacing its contents
1242 //
1243 //--------------------------------------------------------------------------------
1244
1245 int64_t RegexMatcher::appendGroup(int32_t groupNum, UText *dest, UErrorCode &status) const {
1246     if (U_FAILURE(status)) {
1247         return 0;
1248     }
1249     if (U_FAILURE(fDeferredStatus)) {
1250         status = fDeferredStatus;
1251         return 0;
1252     }
1253     int64_t destLen = utext_nativeLength(dest);
1254
1255     if (fMatch == FALSE) {
1256         status = U_REGEX_INVALID_STATE;
1257         return utext_replace(dest, destLen, destLen, NULL, 0, &status);
1258     }
1259     if (groupNum < 0 || groupNum > fPattern->fGroupMap->size()) {
1260         status = U_INDEX_OUTOFBOUNDS_ERROR;
1261         return utext_replace(dest, destLen, destLen, NULL, 0, &status);
1262     }
1263
1264     int64_t s, e;
1265     if (groupNum == 0) {
1266         s = fMatchStart;
1267         e = fMatchEnd;
1268     } else {
1269         int32_t groupOffset = fPattern->fGroupMap->elementAti(groupNum-1);
1270         U_ASSERT(groupOffset < fPattern->fFrameSize);
1271         U_ASSERT(groupOffset >= 0);
1272         s = fFrame->fExtra[groupOffset];
1273         e = fFrame->fExtra[groupOffset+1];
1274     }
1275
1276     if (s < 0) {
1277         // A capture group wasn't part of the match
1278         return utext_replace(dest, destLen, destLen, NULL, 0, &status);
1279     }
1280     U_ASSERT(s <= e);
1281
1282     int64_t deltaLen;
1283     if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) {
1284         U_ASSERT(e <= fInputLength);
1285         deltaLen = utext_replace(dest, destLen, destLen, fInputText->chunkContents+s, (int32_t)(e-s), &status);
1286     } else {
1287         int32_t len16;
1288         if (UTEXT_USES_U16(fInputText)) {
1289             len16 = (int32_t)(e-s);
1290         } else {
1291             UErrorCode lengthStatus = U_ZERO_ERROR;
1292             len16 = utext_extract(fInputText, s, e, NULL, 0, &lengthStatus);
1293         }
1294         UChar *groupChars = (UChar *)uprv_malloc(sizeof(UChar)*(len16+1));
1295         if (groupChars == NULL) {
1296             status = U_MEMORY_ALLOCATION_ERROR;
1297             return 0;
1298         }
1299         utext_extract(fInputText, s, e, groupChars, len16+1, &status);
1300
1301         deltaLen = utext_replace(dest, destLen, destLen, groupChars, len16, &status);
1302         uprv_free(groupChars);
1303     }
1304     return deltaLen;
1305 }
1306
1307
1308
1309 //--------------------------------------------------------------------------------
1310 //
1311 //  groupCount()
1312 //
1313 //--------------------------------------------------------------------------------
1314 int32_t RegexMatcher::groupCount() const {
1315     return fPattern->fGroupMap->size();
1316 }
1317
1318 //--------------------------------------------------------------------------------
1319 //
1320 //  hasAnchoringBounds()
1321 //
1322 //--------------------------------------------------------------------------------
1323 UBool RegexMatcher::hasAnchoringBounds() const {
1324     return fAnchoringBounds;
1325 }
1326
1327
1328 //--------------------------------------------------------------------------------
1329 //
1330 //  hasTransparentBounds()
1331 //
1332 //--------------------------------------------------------------------------------
1333 UBool RegexMatcher::hasTransparentBounds() const {
1334     return fTransparentBounds;
1335 }
1336
1337
1338
1339 //--------------------------------------------------------------------------------
1340 //
1341 //  hitEnd()
1342 //
1343 //--------------------------------------------------------------------------------
1344 UBool RegexMatcher::hitEnd() const {
1345     return fHitEnd;
1346 }
1347
1348
1349 //--------------------------------------------------------------------------------
1350 //
1351 //  input()
1352 //
1353 //--------------------------------------------------------------------------------
1354 const UnicodeString &RegexMatcher::input() const {
1355     if (!fInput) {
1356         UErrorCode status = U_ZERO_ERROR;
1357         int32_t len16;
1358         if (UTEXT_USES_U16(fInputText)) {
1359             len16 = (int32_t)fInputLength;
1360         } else {
1361             len16 = utext_extract(fInputText, 0, fInputLength, NULL, 0, &status);
1362             status = U_ZERO_ERROR; // overflow, length status
1363         }
1364         UnicodeString *result = new UnicodeString(len16, 0, 0);
1365
1366         UChar *inputChars = result->getBuffer(len16);
1367         utext_extract(fInputText, 0, fInputLength, inputChars, len16, &status); // unterminated warning
1368         result->releaseBuffer(len16);
1369
1370         (*(const UnicodeString **)&fInput) = result; // pointer assignment, rather than operator=
1371     }
1372
1373     return *fInput;
1374 }
1375
1376 //--------------------------------------------------------------------------------
1377 //
1378 //  inputText()
1379 //
1380 //--------------------------------------------------------------------------------
1381 UText *RegexMatcher::inputText() const {
1382     return fInputText;
1383 }
1384
1385
1386 //--------------------------------------------------------------------------------
1387 //
1388 //  getInput() -- like inputText(), but makes a clone or copies into another UText
1389 //
1390 //--------------------------------------------------------------------------------
1391 UText *RegexMatcher::getInput (UText *dest, UErrorCode &status) const {
1392     if (U_FAILURE(status)) {
1393         return dest;
1394     }
1395     if (U_FAILURE(fDeferredStatus)) {
1396         status = fDeferredStatus;
1397         return dest;
1398     }
1399
1400     if (dest) {
1401         if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) {
1402             utext_replace(dest, 0, utext_nativeLength(dest), fInputText->chunkContents, (int32_t)fInputLength, &status);
1403         } else {
1404             int32_t input16Len;
1405             if (UTEXT_USES_U16(fInputText)) {
1406                 input16Len = (int32_t)fInputLength;
1407             } else {
1408                 UErrorCode lengthStatus = U_ZERO_ERROR;
1409                 input16Len = utext_extract(fInputText, 0, fInputLength, NULL, 0, &lengthStatus); // buffer overflow error
1410             }
1411             UChar *inputChars = (UChar *)uprv_malloc(sizeof(UChar)*(input16Len));
1412             if (inputChars == NULL) {
1413                 return dest;
1414             }
1415
1416             status = U_ZERO_ERROR;
1417             utext_extract(fInputText, 0, fInputLength, inputChars, input16Len, &status); // not terminated warning
1418             status = U_ZERO_ERROR;
1419             utext_replace(dest, 0, utext_nativeLength(dest), inputChars, input16Len, &status);
1420
1421             uprv_free(inputChars);
1422         }
1423         return dest;
1424     } else {
1425         return utext_clone(NULL, fInputText, FALSE, TRUE, &status);
1426     }
1427 }
1428
1429
1430 static UBool compat_SyncMutableUTextContents(UText *ut);
1431 static UBool compat_SyncMutableUTextContents(UText *ut) {
1432     UBool retVal = FALSE;
1433
1434     //  In the following test, we're really only interested in whether the UText should switch
1435     //  between heap and stack allocation.  If length hasn't changed, we won't, so the chunkContents
1436     //  will still point to the correct data.
1437     if (utext_nativeLength(ut) != ut->nativeIndexingLimit) {
1438         UnicodeString *us=(UnicodeString *)ut->context;
1439
1440         // Update to the latest length.
1441         // For example, (utext_nativeLength(ut) != ut->nativeIndexingLimit).
1442         int32_t newLength = us->length();
1443
1444         // Update the chunk description.
1445         // The buffer may have switched between stack- and heap-based.
1446         ut->chunkContents    = us->getBuffer();
1447         ut->chunkLength      = newLength;
1448         ut->chunkNativeLimit = newLength;
1449         ut->nativeIndexingLimit = newLength;
1450         retVal = TRUE;
1451     }
1452
1453     return retVal;
1454 }
1455
1456 //--------------------------------------------------------------------------------
1457 //
1458 //  lookingAt()
1459 //
1460 //--------------------------------------------------------------------------------
1461 UBool RegexMatcher::lookingAt(UErrorCode &status) {
1462     if (U_FAILURE(status)) {
1463         return FALSE;
1464     }
1465     if (U_FAILURE(fDeferredStatus)) {
1466         status = fDeferredStatus;
1467         return FALSE;
1468     }
1469
1470     if (fInputUniStrMaybeMutable) {
1471         if (compat_SyncMutableUTextContents(fInputText)) {
1472         fInputLength = utext_nativeLength(fInputText);
1473         reset();
1474         }
1475     }
1476     else {
1477         resetPreserveRegion();
1478     }
1479     if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) {
1480         MatchChunkAt((int32_t)fActiveStart, FALSE, status);
1481     } else {
1482         MatchAt(fActiveStart, FALSE, status);
1483     }
1484     return fMatch;
1485 }
1486
1487
1488 UBool RegexMatcher::lookingAt(int64_t start, UErrorCode &status) {
1489     if (U_FAILURE(status)) {
1490         return FALSE;
1491     }
1492     if (U_FAILURE(fDeferredStatus)) {
1493         status = fDeferredStatus;
1494         return FALSE;
1495     }
1496     reset();
1497
1498     if (start < 0) {
1499         status = U_INDEX_OUTOFBOUNDS_ERROR;
1500         return FALSE;
1501     }
1502
1503     if (fInputUniStrMaybeMutable) {
1504         if (compat_SyncMutableUTextContents(fInputText)) {
1505         fInputLength = utext_nativeLength(fInputText);
1506         reset();
1507         }
1508     }
1509
1510     int64_t nativeStart;
1511     nativeStart = start;
1512     if (nativeStart < fActiveStart || nativeStart > fActiveLimit) {
1513         status = U_INDEX_OUTOFBOUNDS_ERROR;
1514         return FALSE;
1515     }
1516
1517     if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) {
1518         MatchChunkAt((int32_t)nativeStart, FALSE, status);
1519     } else {
1520         MatchAt(nativeStart, FALSE, status);
1521     }
1522     return fMatch;
1523 }
1524
1525
1526
1527 //--------------------------------------------------------------------------------
1528 //
1529 //  matches()
1530 //
1531 //--------------------------------------------------------------------------------
1532 UBool RegexMatcher::matches(UErrorCode &status) {
1533     if (U_FAILURE(status)) {
1534         return FALSE;
1535     }
1536     if (U_FAILURE(fDeferredStatus)) {
1537         status = fDeferredStatus;
1538         return FALSE;
1539     }
1540
1541     if (fInputUniStrMaybeMutable) {
1542         if (compat_SyncMutableUTextContents(fInputText)) {
1543         fInputLength = utext_nativeLength(fInputText);
1544         reset();
1545         }
1546     }
1547     else {
1548         resetPreserveRegion();
1549     }
1550
1551     if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) {
1552         MatchChunkAt((int32_t)fActiveStart, TRUE, status);
1553     } else {
1554         MatchAt(fActiveStart, TRUE, status);
1555     }
1556     return fMatch;
1557 }
1558
1559
1560 UBool RegexMatcher::matches(int64_t start, UErrorCode &status) {
1561     if (U_FAILURE(status)) {
1562         return FALSE;
1563     }
1564     if (U_FAILURE(fDeferredStatus)) {
1565         status = fDeferredStatus;
1566         return FALSE;
1567     }
1568     reset();
1569
1570     if (start < 0) {
1571         status = U_INDEX_OUTOFBOUNDS_ERROR;
1572         return FALSE;
1573     }
1574
1575     if (fInputUniStrMaybeMutable) {
1576         if (compat_SyncMutableUTextContents(fInputText)) {
1577         fInputLength = utext_nativeLength(fInputText);
1578         reset();
1579         }
1580     }
1581
1582     int64_t nativeStart;
1583     nativeStart = start;
1584     if (nativeStart < fActiveStart || nativeStart > fActiveLimit) {
1585         status = U_INDEX_OUTOFBOUNDS_ERROR;
1586         return FALSE;
1587     }
1588
1589     if (UTEXT_FULL_TEXT_IN_CHUNK(fInputText, fInputLength)) {
1590         MatchChunkAt((int32_t)nativeStart, TRUE, status);
1591     } else {
1592         MatchAt(nativeStart, TRUE, status);
1593     }
1594     return fMatch;
1595 }
1596
1597
1598
1599 //--------------------------------------------------------------------------------
1600 //
1601 //    pattern
1602 //
1603 //--------------------------------------------------------------------------------
1604 const RegexPattern &RegexMatcher::pattern() const {
1605     return *fPattern;
1606 }
1607
1608
1609
1610 //--------------------------------------------------------------------------------
1611 //
1612 //    region
1613 //
1614 //--------------------------------------------------------------------------------
1615 RegexMatcher &RegexMatcher::region(int64_t regionStart, int64_t regionLimit, int64_t startIndex, UErrorCode &status) {
1616     if (U_FAILURE(status)) {
1617         return *this;
1618     }
1619
1620     if (regionStart>regionLimit || regionStart<0 || regionLimit<0) {
1621         status = U_ILLEGAL_ARGUMENT_ERROR;
1622     }
1623
1624     int64_t nativeStart = regionStart;
1625     int64_t nativeLimit = regionLimit;
1626     if (nativeStart > fInputLength || nativeLimit > fInputLength) {
1627       status = U_ILLEGAL_ARGUMENT_ERROR;
1628     }
1629
1630     if (startIndex == -1)
1631       this->reset();
1632     else
1633       resetPreserveRegion();
1634
1635     fRegionStart = nativeStart;
1636     fRegionLimit = nativeLimit;
1637     fActiveStart = nativeStart;
1638     fActiveLimit = nativeLimit;
1639
1640     if (startIndex != -1) {
1641       if (startIndex < fActiveStart || startIndex > fActiveLimit) {
1642           status = U_INDEX_OUTOFBOUNDS_ERROR;
1643       }
1644       fMatchEnd = startIndex;
1645     }
1646
1647     if (!fTransparentBounds) {
1648         fLookStart = nativeStart;
1649         fLookLimit = nativeLimit;
1650     }
1651     if (fAnchoringBounds) {
1652         fAnchorStart = nativeStart;
1653         fAnchorLimit = nativeLimit;
1654     }
1655     return *this;
1656 }
1657
1658 RegexMatcher &RegexMatcher::region(int64_t start, int64_t limit, UErrorCode &status) {
1659   return region(start, limit, -1, status);
1660 }
1661
1662 //--------------------------------------------------------------------------------
1663 //
1664 //    regionEnd
1665 //
1666 //--------------------------------------------------------------------------------
1667 int32_t RegexMatcher::regionEnd() const {
1668     return (int32_t)fRegionLimit;
1669 }
1670
1671 int64_t RegexMatcher::regionEnd64() const {
1672     return fRegionLimit;
1673 }
1674
1675 //--------------------------------------------------------------------------------
1676 //
1677 //    regionStart
1678 //
1679 //--------------------------------------------------------------------------------
1680 int32_t RegexMatcher::regionStart() const {
1681     return (int32_t)fRegionStart;
1682 }
1683
1684 int64_t RegexMatcher::regionStart64() const {
1685     return fRegionStart;
1686 }
1687
1688
1689 //--------------------------------------------------------------------------------
1690 //
1691 //    replaceAll
1692 //
1693 //--------------------------------------------------------------------------------
1694 UnicodeString RegexMatcher::replaceAll(const UnicodeString &replacement, UErrorCode &status) {
1695     UText replacementText = UTEXT_INITIALIZER;
1696     UText resultText = UTEXT_INITIALIZER;
1697     UnicodeString resultString;
1698     if (U_FAILURE(status)) {
1699         return resultString;
1700     }
1701
1702     utext_openConstUnicodeString(&replacementText, &replacement, &status);
1703     utext_openUnicodeString(&resultText, &resultString, &status);
1704
1705     replaceAll(&replacementText, &resultText, status);
1706
1707     utext_close(&resultText);
1708     utext_close(&replacementText);
1709
1710     return resultString;
1711 }
1712
1713
1714 //
1715 //    replaceAll, UText mode
1716 //
1717 UText *RegexMatcher::replaceAll(UText *replacement, UText *dest, UErrorCode &status) {
1718     if (U_FAILURE(status)) {
1719         return dest;
1720     }
1721     if (U_FAILURE(fDeferredStatus)) {
1722         status = fDeferredStatus;
1723         return dest;
1724     }
1725
1726     if (dest == NULL) {
1727         UnicodeString emptyString;
1728         UText empty = UTEXT_INITIALIZER;
1729
1730         utext_openUnicodeString(&empty, &emptyString, &status);
1731         dest = utext_clone(NULL, &empty, TRUE, FALSE, &status);
1732         utext_close(&empty);
1733     }
1734
1735     if (U_SUCCESS(status)) {
1736         reset();
1737         while (find()) {
1738             appendReplacement(dest, replacement, status);
1739             if (U_FAILURE(status)) {
1740                 break;
1741             }
1742         }
1743         appendTail(dest, status);
1744     }
1745
1746     return dest;
1747 }
1748
1749
1750 //--------------------------------------------------------------------------------
1751 //
1752 //    replaceFirst
1753 //
1754 //--------------------------------------------------------------------------------
1755 UnicodeString RegexMatcher::replaceFirst(const UnicodeString &replacement, UErrorCode &status) {
1756     UText replacementText = UTEXT_INITIALIZER;
1757     UText resultText = UTEXT_INITIALIZER;
1758     UnicodeString resultString;
1759
1760     utext_openConstUnicodeString(&replacementText, &replacement, &status);
1761     utext_openUnicodeString(&resultText, &resultString, &status);
1762
1763     replaceFirst(&replacementText, &resultText, status);
1764
1765     utext_close(&resultText);
1766     utext_close(&replacementText);
1767
1768     return resultString;
1769 }
1770
1771 //
1772 //    replaceFirst, UText mode
1773 //
1774 UText *RegexMatcher::replaceFirst(UText *replacement, UText *dest, UErrorCode &status) {
1775     if (U_FAILURE(status)) {
1776         return dest;
1777     }
1778     if (U_FAILURE(fDeferredStatus)) {
1779         status = fDeferredStatus;
1780         return dest;
1781     }
1782
1783     reset();
1784     if (!find()) {
1785         return getInput(dest, status);
1786     }
1787
1788     if (dest == NULL) {
1789         UnicodeString emptyString;
1790         UText empty = UTEXT_INITIALIZER;
1791
1792         utext_openUnicodeString(&empty, &emptyString, &status);
1793         dest = utext_clone(NULL, &empty, TRUE, FALSE, &status);
1794         utext_close(&empty);
1795     }
1796
1797     appendReplacement(dest, replacement, status);
1798     appendTail(dest, status);
1799
1800     return dest;
1801 }
1802
1803
1804 //--------------------------------------------------------------------------------
1805 //
1806 //     requireEnd
1807 //
1808 //--------------------------------------------------------------------------------
1809 UBool RegexMatcher::requireEnd() const {
1810     return fRequireEnd;
1811 }
1812
1813
1814 //--------------------------------------------------------------------------------
1815 //
1816 //     reset
1817 //
1818 //--------------------------------------------------------------------------------
1819 RegexMatcher &RegexMatcher::reset() {
1820     fRegionStart    = 0;
1821     fRegionLimit    = fInputLength;
1822     fActiveStart    = 0;
1823     fActiveLimit    = fInputLength;
1824     fAnchorStart    = 0;
1825     fAnchorLimit    = fInputLength;
1826     fLookStart      = 0;
1827     fLookLimit      = fInputLength;
1828     resetPreserveRegion();
1829     return *this;
1830 }
1831
1832
1833
1834 void RegexMatcher::resetPreserveRegion() {
1835     fMatchStart     = 0;
1836     fMatchEnd       = 0;
1837     fLastMatchEnd   = -1;
1838     fAppendPosition = 0;
1839     fMatch          = FALSE;
1840     fHitEnd         = FALSE;
1841     fRequireEnd     = FALSE;
1842     fTime           = 0;
1843     fTickCounter    = TIMER_INITIAL_VALUE;
1844     //resetStack(); // more expensive than it looks...
1845 }
1846
1847
1848 RegexMatcher &RegexMatcher::reset(const UnicodeString &input) {
1849     fInputText = utext_openConstUnicodeString(fInputText, &input, &fDeferredStatus);
1850     if (fPattern->fNeedsAltInput) {
1851         fAltInputText = utext_clone(fAltInputText, fInputText, FALSE, TRUE, &fDeferredStatus);
1852     }
1853     if (U_FAILURE(fDeferredStatus)) {
1854         return *this;
1855     }
1856     fInputLength = utext_nativeLength(fInputText);
1857
1858     reset();
1859     delete fInput;
1860     fInput = NULL;
1861
1862     //  Do the following for any UnicodeString.
1863     //  This is for compatibility for those clients who modify the input string "live" during regex operations.
1864     fInputUniStrMaybeMutable = TRUE;
1865
1866     if (fWordBreakItr != NULL) {
1867 #if UCONFIG_NO_BREAK_ITERATION==0
1868         UErrorCode status = U_ZERO_ERROR;
1869         fWordBreakItr->setText(fInputText, status);
1870 #endif
1871     }
1872     return *this;
1873 }
1874
1875
1876 RegexMatcher &RegexMatcher::reset(UText *input) {
1877     if (fInputText != input) {
1878         fInputText = utext_clone(fInputText, input, FALSE, TRUE, &fDeferredStatus);
1879         if (fPattern->fNeedsAltInput) fAltInputText = utext_clone(fAltInputText, fInputText, FALSE, TRUE, &fDeferredStatus);
1880         if (U_FAILURE(fDeferredStatus)) {
1881             return *this;
1882         }
1883         fInputLength = utext_nativeLength(fInputText);
1884
1885         delete fInput;
1886         fInput = NULL;
1887
1888         if (fWordBreakItr != NULL) {
1889 #if UCONFIG_NO_BREAK_ITERATION==0
1890             UErrorCode status = U_ZERO_ERROR;
1891             fWordBreakItr->setText(input, status);
1892 #endif
1893         }
1894     }
1895     reset();
1896     fInputUniStrMaybeMutable = FALSE;
1897
1898     return *this;
1899 }
1900
1901 /*RegexMatcher &RegexMatcher::reset(const UChar *) {
1902     fDeferredStatus = U_INTERNAL_PROGRAM_ERROR;
1903     return *this;
1904 }*/
1905
1906 RegexMatcher &RegexMatcher::reset(int64_t position, UErrorCode &status) {
1907     if (U_FAILURE(status)) {
1908         return *this;
1909     }
1910     reset();       // Reset also resets the region to be the entire string.
1911
1912     if (position < 0 || position > fActiveLimit) {
1913         status = U_INDEX_OUTOFBOUNDS_ERROR;
1914         return *this;
1915     }
1916     fMatchEnd = position;
1917     return *this;
1918 }
1919
1920
1921 //--------------------------------------------------------------------------------
1922 //
1923 //    refresh
1924 //
1925 //--------------------------------------------------------------------------------
1926 RegexMatcher &RegexMatcher::refreshInputText(UText *input, UErrorCode &status) {
1927     if (U_FAILURE(status)) {
1928         return *this;
1929     }
1930     if (input == NULL) {
1931         status = U_ILLEGAL_ARGUMENT_ERROR;
1932         return *this;
1933     }
1934     if (utext_nativeLength(fInputText) != utext_nativeLength(input)) {
1935         status = U_ILLEGAL_ARGUMENT_ERROR;
1936         return *this;
1937     }
1938     int64_t  pos = utext_getNativeIndex(fInputText);
1939     //  Shallow read-only clone of the new UText into the existing input UText
1940     fInputText = utext_clone(fInputText, input, FALSE, TRUE, &status);
1941     if (U_FAILURE(status)) {
1942         return *this;
1943     }
1944     utext_setNativeIndex(fInputText, pos);
1945
1946     if (fAltInputText != NULL) {
1947         pos = utext_getNativeIndex(fAltInputText);
1948         fAltInputText = utext_clone(fAltInputText, input, FALSE, TRUE, &status);
1949         if (U_FAILURE(status)) {
1950             return *this;
1951         }
1952         utext_setNativeIndex(fAltInputText, pos);
1953     }
1954     return *this;
1955 }
1956
1957
1958
1959 //--------------------------------------------------------------------------------
1960 //
1961 //    setTrace
1962 //
1963 //--------------------------------------------------------------------------------
1964 void RegexMatcher::setTrace(UBool state) {
1965     fTraceDebug = state;
1966 }
1967
1968
1969
1970 /**
1971   *  UText, replace entire contents of the destination UText with a substring of the source UText.
1972   *
1973   *     @param src    The source UText
1974   *     @param dest   The destination UText. Must be writable.
1975   *                   May be NULL, in which case a new UText will be allocated.
1976   *     @param start  Start index of source substring.
1977   *     @param limit  Limit index of source substring.
1978   *     @param status An error code.
1979   */
1980 static UText *utext_extract_replace(UText *src, UText *dest, int64_t start, int64_t limit, UErrorCode *status) {
1981     if (U_FAILURE(*status)) {
1982         return dest;
1983     }
1984     if (start == limit) {
1985         if (dest) {
1986             utext_replace(dest, 0, utext_nativeLength(dest), NULL, 0, status);
1987             return dest;
1988         } else {
1989             return utext_openUChars(NULL, NULL, 0, status);
1990         }
1991     }
1992     int32_t length = utext_extract(src, start, limit, NULL, 0, status);
1993     if (*status != U_BUFFER_OVERFLOW_ERROR && U_FAILURE(*status)) {
1994         return dest;
1995     }
1996     *status = U_ZERO_ERROR;
1997     MaybeStackArray<UChar, 40> buffer;
1998     if (length >= buffer.getCapacity()) {
1999         UChar *newBuf = buffer.resize(length+1);   // Leave space for terminating Nul.
2000         if (newBuf == NULL) {
2001             *status = U_MEMORY_ALLOCATION_ERROR;
2002         }
2003     }
2004     utext_extract(src, start, limit, buffer.getAlias(), length+1, status);
2005     if (dest) {
2006         utext_replace(dest, 0, utext_nativeLength(dest), buffer.getAlias(), length, status);
2007         return dest;
2008     }
2009
2010     // Caller did not provide a prexisting UText.
2011     // Open a new one, and have it adopt the text buffer storage.
2012     if (U_FAILURE(*status)) {
2013         return NULL;
2014     }
2015     int32_t ownedLength = 0;
2016     UChar *ownedBuf = buffer.orphanOrClone(length+1, ownedLength);
2017     if (ownedBuf == NULL) {
2018         *status = U_MEMORY_ALLOCATION_ERROR;
2019         return NULL;
2020     }
2021     UText *result = utext_openUChars(NULL, ownedBuf, length, status);
2022     if (U_FAILURE(*status)) {
2023         uprv_free(ownedBuf);
2024         return NULL;
2025     }
2026     result->providerProperties |= (1 << UTEXT_PROVIDER_OWNS_TEXT);
2027     return result;
2028 }
2029
2030
2031 //---------------------------------------------------------------------
2032 //
2033 //   split
2034 //
2035 //---------------------------------------------------------------------
2036 int32_t  RegexMatcher::split(const UnicodeString &input,
2037         UnicodeString    dest[],
2038         int32_t          destCapacity,
2039         UErrorCode      &status)
2040 {
2041     UText inputText = UTEXT_INITIALIZER;
2042     utext_openConstUnicodeString(&inputText, &input, &status);
2043     if (U_FAILURE(status)) {
2044         return 0;
2045     }
2046
2047     UText **destText = (UText **)uprv_malloc(sizeof(UText*)*destCapacity);
2048     if (destText == NULL) {
2049         status = U_MEMORY_ALLOCATION_ERROR;
2050         return 0;
2051     }
2052     int32_t i;
2053     for (i = 0; i < destCapacity; i++) {
2054         destText[i] = utext_openUnicodeString(NULL, &dest[i], &status);
2055     }
2056
2057     int32_t fieldCount = split(&inputText, destText, destCapacity, status);
2058
2059     for (i = 0; i < destCapacity; i++) {
2060         utext_close(destText[i]);
2061     }
2062
2063     uprv_free(destText);
2064     utext_close(&inputText);
2065     return fieldCount;
2066 }
2067
2068 //
2069 //   split, UText mode
2070 //
2071 int32_t  RegexMatcher::split(UText *input,
2072         UText           *dest[],
2073         int32_t          destCapacity,
2074         UErrorCode      &status)
2075 {
2076     //
2077     // Check arguements for validity
2078     //
2079     if (U_FAILURE(status)) {
2080         return 0;
2081     };
2082
2083     if (destCapacity < 1) {
2084         status = U_ILLEGAL_ARGUMENT_ERROR;
2085         return 0;
2086     }
2087
2088     //
2089     // Reset for the input text
2090     //
2091     reset(input);
2092     int64_t   nextOutputStringStart = 0;
2093     if (fActiveLimit == 0) {
2094         return 0;
2095     }
2096
2097     //
2098     // Loop through the input text, searching for the delimiter pattern
2099     //
2100     int32_t i;
2101     int32_t numCaptureGroups = fPattern->fGroupMap->size();
2102     for (i=0; ; i++) {
2103         if (i>=destCapacity-1) {
2104             // There is one or zero output string left.
2105             // Fill the last output string with whatever is left from the input, then exit the loop.
2106             //  ( i will be == destCapacity if we filled the output array while processing
2107             //    capture groups of the delimiter expression, in which case we will discard the
2108             //    last capture group saved in favor of the unprocessed remainder of the
2109             //    input string.)
2110             i = destCapacity-1;
2111             if (fActiveLimit > nextOutputStringStart) {
2112                 if (UTEXT_FULL_TEXT_IN_CHUNK(input, fInputLength)) {
2113                     if (dest[i]) {
2114                         utext_replace(dest[i], 0, utext_nativeLength(dest[i]),
2115                                       input->chunkContents+nextOutputStringStart,
2116                                       (int32_t)(fActiveLimit-nextOutputStringStart), &status);
2117                     } else {
2118                         UText remainingText = UTEXT_INITIALIZER;
2119                         utext_openUChars(&remainingText, input->chunkContents+nextOutputStringStart,
2120                                          fActiveLimit-nextOutputStringStart, &status);
2121                         dest[i] = utext_clone(NULL, &remainingText, TRUE, FALSE, &status);
2122                         utext_close(&remainingText);
2123                     }
2124                 } else {
2125                     UErrorCode lengthStatus = U_ZERO_ERROR;
2126                     int32_t remaining16Length =
2127                         utext_extract(input, nextOutputStringStart, fActiveLimit, NULL, 0, &lengthStatus);
2128                     UChar *remainingChars = (UChar *)uprv_malloc(sizeof(UChar)*(remaining16Length+1));
2129                     if (remainingChars == NULL) {
2130                         status = U_MEMORY_ALLOCATION_ERROR;
2131                         break;
2132                     }
2133
2134                     utext_extract(input, nextOutputStringStart, fActiveLimit, remainingChars, remaining16Length+1, &status);
2135                     if (dest[i]) {
2136                         utext_replace(dest[i], 0, utext_nativeLength(dest[i]), remainingChars, remaining16Length, &status);
2137                     } else {
2138                         UText remainingText = UTEXT_INITIALIZER;
2139                         utext_openUChars(&remainingText, remainingChars, remaining16Length, &status);
2140                         dest[i] = utext_clone(NULL, &remainingText, TRUE, FALSE, &status);
2141                         utext_close(&remainingText);
2142                     }
2143
2144                     uprv_free(remainingChars);
2145                 }
2146             }
2147             break;
2148         }
2149         if (find()) {
2150             // We found another delimiter.  Move everything from where we started looking
2151             //  up until the start of the delimiter into the next output string.
2152             if (UTEXT_FULL_TEXT_IN_CHUNK(input, fInputLength)) {
2153                 if (dest[i]) {
2154                     utext_replace(dest[i], 0, utext_nativeLength(dest[i]),
2155                                   input->chunkContents+nextOutputStringStart,
2156                                   (int32_t)(fMatchStart-nextOutputStringStart), &status);
2157                 } else {
2158                     UText remainingText = UTEXT_INITIALIZER;
2159                     utext_openUChars(&remainingText, input->chunkContents+nextOutputStringStart,
2160                                       fMatchStart-nextOutputStringStart, &status);
2161                     dest[i] = utext_clone(NULL, &remainingText, TRUE, FALSE, &status);
2162                     utext_close(&remainingText);
2163                 }
2164             } else {
2165                 UErrorCode lengthStatus = U_ZERO_ERROR;
2166                 int32_t remaining16Length = utext_extract(input, nextOutputStringStart, fMatchStart, NULL, 0, &lengthStatus);
2167                 UChar *remainingChars = (UChar *)uprv_malloc(sizeof(UChar)*(remaining16Length+1));
2168                 if (remainingChars == NULL) {
2169                     status = U_MEMORY_ALLOCATION_ERROR;
2170                     break;
2171                 }
2172                 utext_extract(input, nextOutputStringStart, fMatchStart, remainingChars, remaining16Length+1, &status);
2173                 if (dest[i]) {
2174                     utext_replace(dest[i], 0, utext_nativeLength(dest[i]), remainingChars, remaining16Length, &status);
2175                 } else {
2176                     UText remainingText = UTEXT_INITIALIZER;
2177                     utext_openUChars(&remainingText, remainingChars, remaining16Length, &status);
2178                     dest[i] = utext_clone(NULL, &remainingText, TRUE, FALSE, &status);
2179                     utext_close(&remainingText);
2180                 }
2181
2182                 uprv_free(remainingChars);
2183             }
2184             nextOutputStringStart = fMatchEnd;
2185
2186             // If the delimiter pattern has capturing parentheses, the captured
2187             //  text goes out into the next n destination strings.
2188             int32_t groupNum;
2189             for (groupNum=1; groupNum<=numCaptureGroups; groupNum++) {
2190                 if (i >= destCapacity-2) {
2191                     // Never fill the last available output string with capture group text.
2192                     // It will filled with the last field, the remainder of the
2193                     //  unsplit input text.
2194                     break;
2195                 }
2196                 i++;
2197                 dest[i] = utext_extract_replace(fInputText, dest[i],
2198                                                start64(groupNum, status), end64(groupNum, status), &status);
2199             }
2200
2201             if (nextOutputStringStart == fActiveLimit) {
2202                 // The delimiter was at the end of the string.  We're done, but first
2203                 // we output one last empty string, for the empty field following
2204                 //   the delimiter at the end of input.
2205                 if (i+1 < destCapacity) {
2206                     ++i;
2207                     if (dest[i] == NULL) {
2208                         dest[i] = utext_openUChars(NULL, NULL, 0, &status);
2209                     } else {
2210                         static const UChar emptyString[] = {(UChar)0};
2211                         utext_replace(dest[i], 0, utext_nativeLength(dest[i]), emptyString, 0, &status);
2212                     }
2213                 }
2214                 break;
2215
2216             }
2217         }
2218         else
2219         {
2220             // We ran off the end of the input while looking for the next delimiter.
2221             // All the remaining text goes into the current output string.
2222             if (UTEXT_FULL_TEXT_IN_CHUNK(input, fInputLength)) {
2223                 if (dest[i]) {
2224                     utext_replace(dest[i], 0, utext_nativeLength(dest[i]),
2225                                   input->chunkContents+nextOutputStringStart,
2226                                   (int32_t)(fActiveLimit-nextOutputStringStart), &status);
2227                 } else {
2228                     UText remainingText = UTEXT_INITIALIZER;
2229                     utext_openUChars(&remainingText, input->chunkContents+nextOutputStringStart,
2230                                      fActiveLimit-nextOutputStringStart, &status);
2231                     dest[i] = utext_clone(NULL, &remainingText, TRUE, FALSE, &status);
2232                     utext_close(&remainingText);
2233                 }
2234             } else {
2235                 UErrorCode lengthStatus = U_ZERO_ERROR;
2236                 int32_t remaining16Length = utext_extract(input, nextOutputStringStart, fActiveLimit, NULL, 0, &lengthStatus);
2237                 UChar *remainingChars = (UChar *)uprv_malloc(sizeof(UChar)*(remaining16Length+1));
2238                 if (remainingChars == NULL) {
2239                     status = U_MEMORY_ALLOCATION_ERROR;
2240                     break;
2241                 }
2242
2243                 utext_extract(input, nextOutputStringStart, fActiveLimit, remainingChars, remaining16Length+1, &status);
2244                 if (dest[i]) {
2245                     utext_replace(dest[i], 0, utext_nativeLength(dest[i]), remainingChars, remaining16Length, &status);
2246                 } else {
2247                     UText remainingText = UTEXT_INITIALIZER;
2248                     utext_openUChars(&remainingText, remainingChars, remaining16Length, &status);
2249                     dest[i] = utext_clone(NULL, &remainingText, TRUE, FALSE, &status);
2250                     utext_close(&remainingText);
2251                 }
2252
2253                 uprv_free(remainingChars);
2254             }
2255             break;
2256         }
2257         if (U_FAILURE(status)) {
2258             break;
2259         }
2260     }   // end of for loop
2261     return i+1;
2262 }
2263
2264
2265 //--------------------------------------------------------------------------------
2266 //
2267 //     start
2268 //
2269 //--------------------------------------------------------------------------------
2270 int32_t RegexMatcher::start(UErrorCode &status) const {
2271     return start(0, status);
2272 }
2273
2274 int64_t RegexMatcher::start64(UErrorCode &status) const {
2275     return start64(0, status);
2276 }
2277
2278 //--------------------------------------------------------------------------------
2279 //
2280 //     start(int32_t group, UErrorCode &status)
2281 //
2282 //--------------------------------------------------------------------------------
2283
2284 int64_t RegexMatcher::start64(int32_t group, UErrorCode &status) const {
2285     if (U_FAILURE(status)) {
2286         return -1;
2287     }
2288     if (U_FAILURE(fDeferredStatus)) {
2289         status = fDeferredStatus;
2290         return -1;
2291     }
2292     if (fMatch == FALSE) {
2293         status = U_REGEX_INVALID_STATE;
2294         return -1;
2295     }
2296     if (group < 0 || group > fPattern->fGroupMap->size()) {
2297         status = U_INDEX_OUTOFBOUNDS_ERROR;
2298         return -1;
2299     }
2300     int64_t s;
2301     if (group == 0) {
2302         s = fMatchStart;
2303     } else {
2304         int32_t groupOffset = fPattern->fGroupMap->elementAti(group-1);
2305         U_ASSERT(groupOffset < fPattern->fFrameSize);
2306         U_ASSERT(groupOffset >= 0);
2307         s = fFrame->fExtra[groupOffset];
2308     }
2309
2310     return s;
2311 }
2312
2313
2314 int32_t RegexMatcher::start(int32_t group, UErrorCode &status) const {
2315     return (int32_t)start64(group, status);
2316 }
2317
2318 //--------------------------------------------------------------------------------
2319 //
2320 //     useAnchoringBounds
2321 //
2322 //--------------------------------------------------------------------------------
2323 RegexMatcher &RegexMatcher::useAnchoringBounds(UBool b) {
2324     fAnchoringBounds = b;
2325     fAnchorStart = (fAnchoringBounds ? fRegionStart : 0);
2326     fAnchorLimit = (fAnchoringBounds ? fRegionLimit : fInputLength);
2327     return *this;
2328 }
2329
2330
2331 //--------------------------------------------------------------------------------
2332 //
2333 //     useTransparentBounds
2334 //
2335 //--------------------------------------------------------------------------------
2336 RegexMatcher &RegexMatcher::useTransparentBounds(UBool b) {
2337     fTransparentBounds = b;
2338     fLookStart = (fTransparentBounds ? 0 : fRegionStart);
2339     fLookLimit = (fTransparentBounds ? fInputLength : fRegionLimit);
2340     return *this;
2341 }
2342
2343 //--------------------------------------------------------------------------------
2344 //
2345 //     setTimeLimit
2346 //
2347 //--------------------------------------------------------------------------------
2348 void RegexMatcher::setTimeLimit(int32_t limit, UErrorCode &status) {
2349     if (U_FAILURE(status)) {
2350         return;
2351     }
2352     if (U_FAILURE(fDeferredStatus)) {
2353         status = fDeferredStatus;
2354         return;
2355     }
2356     if (limit < 0) {
2357         status = U_ILLEGAL_ARGUMENT_ERROR;
2358         return;
2359     }
2360     fTimeLimit = limit;
2361 }
2362
2363
2364 //--------------------------------------------------------------------------------
2365 //
2366 //     getTimeLimit
2367 //
2368 //--------------------------------------------------------------------------------
2369 int32_t RegexMatcher::getTimeLimit() const {
2370     return fTimeLimit;
2371 }
2372
2373
2374 //--------------------------------------------------------------------------------
2375 //
2376 //     setStackLimit
2377 //
2378 //--------------------------------------------------------------------------------
2379 void RegexMatcher::setStackLimit(int32_t limit, UErrorCode &status) {
2380     if (U_FAILURE(status)) {
2381         return;
2382     }
2383     if (U_FAILURE(fDeferredStatus)) {
2384         status = fDeferredStatus;
2385         return;
2386     }
2387     if (limit < 0) {
2388         status = U_ILLEGAL_ARGUMENT_ERROR;
2389         return;
2390     }
2391
2392     // Reset the matcher.  This is needed here in case there is a current match
2393     //    whose final stack frame (containing the match results, pointed to by fFrame)
2394     //    would be lost by resizing to a smaller stack size.
2395     reset();
2396
2397     if (limit == 0) {
2398         // Unlimited stack expansion
2399         fStack->setMaxCapacity(0);
2400     } else {
2401         // Change the units of the limit  from bytes to ints, and bump the size up
2402         //   to be big enough to hold at least one stack frame for the pattern,
2403         //   if it isn't there already.
2404         int32_t adjustedLimit = limit / sizeof(int32_t);
2405         if (adjustedLimit < fPattern->fFrameSize) {
2406             adjustedLimit = fPattern->fFrameSize;
2407         }
2408         fStack->setMaxCapacity(adjustedLimit);
2409     }
2410     fStackLimit = limit;
2411 }
2412
2413
2414 //--------------------------------------------------------------------------------
2415 //
2416 //     getStackLimit
2417 //
2418 //--------------------------------------------------------------------------------
2419 int32_t RegexMatcher::getStackLimit() const {
2420     return fStackLimit;
2421 }
2422
2423
2424 //--------------------------------------------------------------------------------
2425 //
2426 //     setMatchCallback
2427 //
2428 //--------------------------------------------------------------------------------
2429 void RegexMatcher::setMatchCallback(URegexMatchCallback     *callback,
2430                                     const void              *context,
2431                                     UErrorCode              &status) {
2432     if (U_FAILURE(status)) {
2433         return;
2434     }
2435     fCallbackFn = callback;
2436     fCallbackContext = context;
2437 }
2438
2439
2440 //--------------------------------------------------------------------------------
2441 //
2442 //     getMatchCallback
2443 //
2444 //--------------------------------------------------------------------------------
2445 void RegexMatcher::getMatchCallback(URegexMatchCallback   *&callback,
2446                                   const void              *&context,
2447                                   UErrorCode              &status) {
2448     if (U_FAILURE(status)) {
2449        return;
2450     }
2451     callback = fCallbackFn;
2452     context  = fCallbackContext;
2453 }
2454
2455
2456 //--------------------------------------------------------------------------------
2457 //
2458 //     setMatchCallback
2459 //
2460 //--------------------------------------------------------------------------------
2461 void RegexMatcher::setFindProgressCallback(URegexFindProgressCallback      *callback,
2462                                                 const void                      *context,
2463                                                 UErrorCode                      &status) {
2464     if (U_FAILURE(status)) {
2465         return;
2466     }
2467     fFindProgressCallbackFn = callback;
2468     fFindProgressCallbackContext = context;
2469 }
2470
2471
2472 //--------------------------------------------------------------------------------
2473 //
2474 //     getMatchCallback
2475 //
2476 //--------------------------------------------------------------------------------
2477 void RegexMatcher::getFindProgressCallback(URegexFindProgressCallback    *&callback,
2478                                                 const void                    *&context,
2479                                                 UErrorCode                    &status) {
2480     if (U_FAILURE(status)) {
2481        return;
2482     }
2483     callback = fFindProgressCallbackFn;
2484     context  = fFindProgressCallbackContext;
2485 }
2486
2487
2488 //================================================================================
2489 //
2490 //    Code following this point in this file is the internal
2491 //    Match Engine Implementation.
2492 //
2493 //================================================================================
2494
2495
2496 //--------------------------------------------------------------------------------
2497 //
2498 //   resetStack
2499 //           Discard any previous contents of the state save stack, and initialize a
2500 //           new stack frame to all -1.  The -1s are needed for capture group limits,
2501 //           where they indicate that a group has not yet matched anything.
2502 //--------------------------------------------------------------------------------
2503 REStackFrame *RegexMatcher::resetStack() {
2504     // Discard any previous contents of the state save stack, and initialize a
2505     //  new stack frame with all -1 data.  The -1s are needed for capture group limits,
2506     //  where they indicate that a group has not yet matched anything.
2507     fStack->removeAllElements();
2508
2509     REStackFrame *iFrame = (REStackFrame *)fStack->reserveBlock(fPattern->fFrameSize, fDeferredStatus);
2510     if(U_FAILURE(fDeferredStatus)) {
2511         return NULL;
2512     }
2513
2514     int32_t i;
2515     for (i=0; i<fPattern->fFrameSize-RESTACKFRAME_HDRCOUNT; i++) {
2516         iFrame->fExtra[i] = -1;
2517     }
2518     return iFrame;
2519 }
2520
2521
2522
2523 //--------------------------------------------------------------------------------
2524 //
2525 //   isWordBoundary
2526 //                     in perl, "xab..cd..", \b is true at positions 0,3,5,7
2527 //                     For us,
2528 //                       If the current char is a combining mark,
2529 //                          \b is FALSE.
2530 //                       Else Scan backwards to the first non-combining char.
2531 //                            We are at a boundary if the this char and the original chars are
2532 //                               opposite in membership in \w set
2533 //
2534 //          parameters:   pos   - the current position in the input buffer
2535 //
2536 //              TODO:  double-check edge cases at region boundaries.
2537 //
2538 //--------------------------------------------------------------------------------
2539 UBool RegexMatcher::isWordBoundary(int64_t pos) {
2540     UBool isBoundary = FALSE;
2541     UBool cIsWord    = FALSE;
2542
2543     if (pos >= fLookLimit) {
2544         fHitEnd = TRUE;
2545     } else {
2546         // Determine whether char c at current position is a member of the word set of chars.
2547         // If we're off the end of the string, behave as though we're not at a word char.
2548         UTEXT_SETNATIVEINDEX(fInputText, pos);
2549         UChar32  c = UTEXT_CURRENT32(fInputText);
2550         if (u_hasBinaryProperty(c, UCHAR_GRAPHEME_EXTEND) || u_charType(c) == U_FORMAT_CHAR) {
2551             // Current char is a combining one.  Not a boundary.
2552             return FALSE;
2553         }
2554         cIsWord = fPattern->fStaticSets[URX_ISWORD_SET]->contains(c);
2555     }
2556
2557     // Back up until we come to a non-combining char, determine whether
2558     //  that char is a word char.
2559     UBool prevCIsWord = FALSE;
2560     for (;;) {
2561         if (UTEXT_GETNATIVEINDEX(fInputText) <= fLookStart) {
2562             break;
2563         }
2564         UChar32 prevChar = UTEXT_PREVIOUS32(fInputText);
2565         if (!(u_hasBinaryProperty(prevChar, UCHAR_GRAPHEME_EXTEND)
2566               || u_charType(prevChar) == U_FORMAT_CHAR)) {
2567             prevCIsWord = fPattern->fStaticSets[URX_ISWORD_SET]->contains(prevChar);
2568             break;
2569         }
2570     }
2571     isBoundary = cIsWord ^ prevCIsWord;
2572     return isBoundary;
2573 }
2574
2575 UBool RegexMatcher::isChunkWordBoundary(int32_t pos) {
2576     UBool isBoundary = FALSE;
2577     UBool cIsWord    = FALSE;
2578
2579     const UChar *inputBuf = fInputText->chunkContents;
2580
2581     if (pos >= fLookLimit) {
2582         fHitEnd = TRUE;
2583     } else {
2584         // Determine whether char c at current position is a member of the word set of chars.
2585         // If we're off the end of the string, behave as though we're not at a word char.
2586         UChar32 c;
2587         U16_GET(inputBuf, fLookStart, pos, fLookLimit, c);
2588         if (u_hasBinaryProperty(c, UCHAR_GRAPHEME_EXTEND) || u_charType(c) == U_FORMAT_CHAR) {
2589             // Current char is a combining one.  Not a boundary.
2590             return FALSE;
2591         }
2592         cIsWord = fPattern->fStaticSets[URX_ISWORD_SET]->contains(c);
2593     }
2594
2595     // Back up until we come to a non-combining char, determine whether
2596     //  that char is a word char.
2597     UBool prevCIsWord = FALSE;
2598     for (;;) {
2599         if (pos <= fLookStart) {
2600             break;
2601         }
2602         UChar32 prevChar;
2603         U16_PREV(inputBuf, fLookStart, pos, prevChar);
2604         if (!(u_hasBinaryProperty(prevChar, UCHAR_GRAPHEME_EXTEND)
2605               || u_charType(prevChar) == U_FORMAT_CHAR)) {
2606             prevCIsWord = fPattern->fStaticSets[URX_ISWORD_SET]->contains(prevChar);
2607             break;
2608         }
2609     }
2610     isBoundary = cIsWord ^ prevCIsWord;
2611     return isBoundary;
2612 }
2613
2614 //--------------------------------------------------------------------------------
2615 //
2616 //   isUWordBoundary
2617 //
2618 //         Test for a word boundary using RBBI word break.
2619 //
2620 //          parameters:   pos   - the current position in the input buffer
2621 //
2622 //--------------------------------------------------------------------------------
2623 UBool RegexMatcher::isUWordBoundary(int64_t pos) {
2624     UBool       returnVal = FALSE;
2625 #if UCONFIG_NO_BREAK_ITERATION==0
2626
2627     // If we haven't yet created a break iterator for this matcher, do it now.
2628     if (fWordBreakItr == NULL) {
2629         fWordBreakItr =
2630             (RuleBasedBreakIterator *)BreakIterator::createWordInstance(Locale::getEnglish(), fDeferredStatus);
2631         if (U_FAILURE(fDeferredStatus)) {
2632             return FALSE;
2633         }
2634         fWordBreakItr->setText(fInputText, fDeferredStatus);
2635     }
2636
2637     if (pos >= fLookLimit) {
2638         fHitEnd = TRUE;
2639         returnVal = TRUE;   // With Unicode word rules, only positions within the interior of "real"
2640                             //    words are not boundaries.  All non-word chars stand by themselves,
2641                             //    with word boundaries on both sides.
2642     } else {
2643         if (!UTEXT_USES_U16(fInputText)) {
2644             // !!!: Would like a better way to do this!
2645             UErrorCode status = U_ZERO_ERROR;
2646             pos = utext_extract(fInputText, 0, pos, NULL, 0, &status);
2647         }
2648         returnVal = fWordBreakItr->isBoundary((int32_t)pos);
2649     }
2650 #endif
2651     return   returnVal;
2652 }
2653
2654 //--------------------------------------------------------------------------------
2655 //
2656 //   IncrementTime     This function is called once each TIMER_INITIAL_VALUE state
2657 //                     saves. Increment the "time" counter, and call the
2658 //                     user callback function if there is one installed.
2659 //
2660 //                     If the match operation needs to be aborted, either for a time-out
2661 //                     or because the user callback asked for it, just set an error status.
2662 //                     The engine will pick that up and stop in its outer loop.
2663 //
2664 //--------------------------------------------------------------------------------
2665 void RegexMatcher::IncrementTime(UErrorCode &status) {
2666     fTickCounter = TIMER_INITIAL_VALUE;
2667     fTime++;
2668     if (fCallbackFn != NULL) {
2669         if ((*fCallbackFn)(fCallbackContext, fTime) == FALSE) {
2670             status = U_REGEX_STOPPED_BY_CALLER;
2671             return;
2672         }
2673     }
2674     if (fTimeLimit > 0 && fTime >= fTimeLimit) {
2675         status = U_REGEX_TIME_OUT;
2676     }
2677 }
2678
2679 //--------------------------------------------------------------------------------
2680 //
2681 //   StateSave
2682 //       Make a new stack frame, initialized as a copy of the current stack frame.
2683 //       Set the pattern index in the original stack frame from the operand value
2684 //       in the opcode.  Execution of the engine continues with the state in
2685 //       the newly created stack frame
2686 //
2687 //       Note that reserveBlock() may grow the stack, resulting in the
2688 //       whole thing being relocated in memory.
2689 //
2690 //    Parameters:
2691 //       fp           The top frame pointer when called.  At return, a new
2692 //                    fame will be present
2693 //       savePatIdx   An index into the compiled pattern.  Goes into the original
2694 //                    (not new) frame.  If execution ever back-tracks out of the
2695 //                    new frame, this will be where we continue from in the pattern.
2696 //    Return
2697 //                    The new frame pointer.
2698 //
2699 //--------------------------------------------------------------------------------
2700 inline REStackFrame *RegexMatcher::StateSave(REStackFrame *fp, int64_t savePatIdx, UErrorCode &status) {
2701     if (U_FAILURE(status)) {
2702         return fp;
2703     }
2704     // push storage for a new frame.
2705     int64_t *newFP = fStack->reserveBlock(fFrameSize, status);
2706     if (U_FAILURE(status)) {
2707         // Failure on attempted stack expansion.
2708         //   Stack function set some other error code, change it to a more
2709         //   specific one for regular expressions.
2710         status = U_REGEX_STACK_OVERFLOW;
2711         // We need to return a writable stack frame, so just return the
2712         //    previous frame.  The match operation will stop quickly
2713         //    because of the error status, after which the frame will never
2714         //    be looked at again.
2715         return fp;
2716     }
2717     fp = (REStackFrame *)(newFP - fFrameSize);  // in case of realloc of stack.
2718
2719     // New stack frame = copy of old top frame.
2720     int64_t *source = (int64_t *)fp;
2721     int64_t *dest   = newFP;
2722     for (;;) {
2723         *dest++ = *source++;
2724         if (source == newFP) {
2725             break;
2726         }
2727     }
2728
2729     fTickCounter--;
2730     if (fTickCounter <= 0) {
2731        IncrementTime(status);    // Re-initializes fTickCounter
2732     }
2733     fp->fPatIdx = savePatIdx;
2734     return (REStackFrame *)newFP;
2735 }
2736
2737 #if defined(REGEX_DEBUG)
2738 namespace {
2739 UnicodeString StringFromUText(UText *ut) {
2740     UnicodeString result;
2741     for (UChar32 c = utext_next32From(ut, 0); c != U_SENTINEL; c = UTEXT_NEXT32(ut)) {
2742         result.append(c);
2743     }
2744     return result;
2745 }
2746 }
2747 #endif // REGEX_DEBUG
2748
2749
2750 //--------------------------------------------------------------------------------
2751 //
2752 //   MatchAt      This is the actual matching engine.
2753 //
2754 //                  startIdx:    begin matching a this index.
2755 //                  toEnd:       if true, match must extend to end of the input region
2756 //
2757 //--------------------------------------------------------------------------------
2758 void RegexMatcher::MatchAt(int64_t startIdx, UBool toEnd, UErrorCode &status) {
2759     UBool       isMatch  = FALSE;      // True if the we have a match.
2760
2761     int64_t     backSearchIndex = U_INT64_MAX; // used after greedy single-character matches for searching backwards
2762
2763     int32_t     op;                    // Operation from the compiled pattern, split into
2764     int32_t     opType;                //    the opcode
2765     int32_t     opValue;               //    and the operand value.
2766
2767 #ifdef REGEX_RUN_DEBUG
2768     if (fTraceDebug) {
2769         printf("MatchAt(startIdx=%ld)\n", startIdx);
2770         printf("Original Pattern: \"%s\"\n", CStr(StringFromUText(fPattern->fPattern))());
2771         printf("Input String:     \"%s\"\n\n", CStr(StringFromUText(fInputText))());
2772     }
2773 #endif
2774
2775     if (U_FAILURE(status)) {
2776         return;
2777     }
2778
2779     //  Cache frequently referenced items from the compiled pattern
2780     //
2781     int64_t             *pat           = fPattern->fCompiledPat->getBuffer();
2782
2783     const UChar         *litText       = fPattern->fLiteralText.getBuffer();
2784     UVector             *fSets         = fPattern->fSets;
2785
2786     fFrameSize = fPattern->fFrameSize;
2787     REStackFrame        *fp            = resetStack();
2788     if (U_FAILURE(fDeferredStatus)) {
2789         status = fDeferredStatus;
2790         return;
2791     }
2792
2793     fp->fPatIdx   = 0;
2794     fp->fInputIdx = startIdx;
2795
2796     // Zero out the pattern's static data
2797     int32_t i;
2798     for (i = 0; i<fPattern->fDataSize; i++) {
2799         fData[i] = 0;
2800     }
2801
2802     //
2803     //  Main loop for interpreting the compiled pattern.
2804     //  One iteration of the loop per pattern operation performed.
2805     //
2806     for (;;) {
2807         op      = (int32_t)pat[fp->fPatIdx];
2808         opType  = URX_TYPE(op);
2809         opValue = URX_VAL(op);
2810 #ifdef REGEX_RUN_DEBUG
2811         if (fTraceDebug) {
2812             UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
2813             printf("inputIdx=%ld   inputChar=%x   sp=%3ld   activeLimit=%ld  ", fp->fInputIdx,
2814                 UTEXT_CURRENT32(fInputText), (int64_t *)fp-fStack->getBuffer(), fActiveLimit);
2815             fPattern->dumpOp(fp->fPatIdx);
2816         }
2817 #endif
2818         fp->fPatIdx++;
2819
2820         switch (opType) {
2821
2822
2823         case URX_NOP:
2824             break;
2825
2826
2827         case URX_BACKTRACK:
2828             // Force a backtrack.  In some circumstances, the pattern compiler
2829             //   will notice that the pattern can't possibly match anything, and will
2830             //   emit one of these at that point.
2831             fp = (REStackFrame *)fStack->popFrame(fFrameSize);
2832             break;
2833
2834
2835         case URX_ONECHAR:
2836             if (fp->fInputIdx < fActiveLimit) {
2837                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
2838                 UChar32 c = UTEXT_NEXT32(fInputText);
2839                 if (c == opValue) {
2840                     fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
2841                     break;
2842                 }
2843             } else {
2844                 fHitEnd = TRUE;
2845             }
2846             fp = (REStackFrame *)fStack->popFrame(fFrameSize);
2847             break;
2848
2849
2850         case URX_STRING:
2851             {
2852                 // Test input against a literal string.
2853                 // Strings require two slots in the compiled pattern, one for the
2854                 //   offset to the string text, and one for the length.
2855
2856                 int32_t   stringStartIdx = opValue;
2857                 op      = (int32_t)pat[fp->fPatIdx];     // Fetch the second operand
2858                 fp->fPatIdx++;
2859                 opType    = URX_TYPE(op);
2860                 int32_t stringLen = URX_VAL(op);
2861                 U_ASSERT(opType == URX_STRING_LEN);
2862                 U_ASSERT(stringLen >= 2);
2863
2864                 const UChar *patternString = litText+stringStartIdx;
2865                 int32_t patternStringIndex = 0;
2866                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
2867                 UChar32 inputChar;
2868                 UChar32 patternChar;
2869                 UBool success = TRUE;
2870                 while (patternStringIndex < stringLen) {
2871                     if (UTEXT_GETNATIVEINDEX(fInputText) >= fActiveLimit) {
2872                         success = FALSE;
2873                         fHitEnd = TRUE;
2874                         break;
2875                     }
2876                     inputChar = UTEXT_NEXT32(fInputText);
2877                     U16_NEXT(patternString, patternStringIndex, stringLen, patternChar);
2878                     if (patternChar != inputChar) {
2879                         success = FALSE;
2880                         break;
2881                     }
2882                 }
2883
2884                 if (success) {
2885                     fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
2886                 } else {
2887                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
2888                 }
2889             }
2890             break;
2891
2892
2893         case URX_STATE_SAVE:
2894             fp = StateSave(fp, opValue, status);
2895             break;
2896
2897
2898         case URX_END:
2899             // The match loop will exit via this path on a successful match,
2900             //   when we reach the end of the pattern.
2901             if (toEnd && fp->fInputIdx != fActiveLimit) {
2902                 // The pattern matched, but not to the end of input.  Try some more.
2903                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
2904                 break;
2905             }
2906             isMatch = TRUE;
2907             goto  breakFromLoop;
2908
2909         // Start and End Capture stack frame variables are laid out out like this:
2910             //  fp->fExtra[opValue]  - The start of a completed capture group
2911             //             opValue+1 - The end   of a completed capture group
2912             //             opValue+2 - the start of a capture group whose end
2913             //                          has not yet been reached (and might not ever be).
2914         case URX_START_CAPTURE:
2915             U_ASSERT(opValue >= 0 && opValue < fFrameSize-3);
2916             fp->fExtra[opValue+2] = fp->fInputIdx;
2917             break;
2918
2919
2920         case URX_END_CAPTURE:
2921             U_ASSERT(opValue >= 0 && opValue < fFrameSize-3);
2922             U_ASSERT(fp->fExtra[opValue+2] >= 0);            // Start pos for this group must be set.
2923             fp->fExtra[opValue]   = fp->fExtra[opValue+2];   // Tentative start becomes real.
2924             fp->fExtra[opValue+1] = fp->fInputIdx;           // End position
2925             U_ASSERT(fp->fExtra[opValue] <= fp->fExtra[opValue+1]);
2926             break;
2927
2928
2929         case URX_DOLLAR:                   //  $, test for End of line
2930                                            //     or for position before new line at end of input
2931             {
2932                 if (fp->fInputIdx >= fAnchorLimit) {
2933                     // We really are at the end of input.  Success.
2934                     fHitEnd = TRUE;
2935                     fRequireEnd = TRUE;
2936                     break;
2937                 }
2938
2939                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
2940
2941                 // If we are positioned just before a new-line that is located at the
2942                 //   end of input, succeed.
2943                 UChar32 c = UTEXT_NEXT32(fInputText);
2944                 if (UTEXT_GETNATIVEINDEX(fInputText) >= fAnchorLimit) {
2945                     if (isLineTerminator(c)) {
2946                         // If not in the middle of a CR/LF sequence
2947                         if ( !(c==0x0a && fp->fInputIdx>fAnchorStart && ((void)UTEXT_PREVIOUS32(fInputText), UTEXT_PREVIOUS32(fInputText))==0x0d)) {
2948                             // At new-line at end of input. Success
2949                             fHitEnd = TRUE;
2950                             fRequireEnd = TRUE;
2951
2952                             break;
2953                         }
2954                     }
2955                 } else {
2956                     UChar32 nextC = UTEXT_NEXT32(fInputText);
2957                     if (c == 0x0d && nextC == 0x0a && UTEXT_GETNATIVEINDEX(fInputText) >= fAnchorLimit) {
2958                         fHitEnd = TRUE;
2959                         fRequireEnd = TRUE;
2960                         break;                         // At CR/LF at end of input.  Success
2961                     }
2962                 }
2963
2964                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
2965             }
2966             break;
2967
2968
2969          case URX_DOLLAR_D:                   //  $, test for End of Line, in UNIX_LINES mode.
2970             if (fp->fInputIdx >= fAnchorLimit) {
2971                 // Off the end of input.  Success.
2972                 fHitEnd = TRUE;
2973                 fRequireEnd = TRUE;
2974                 break;
2975             } else {
2976                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
2977                 UChar32 c = UTEXT_NEXT32(fInputText);
2978                 // Either at the last character of input, or off the end.
2979                 if (c == 0x0a && UTEXT_GETNATIVEINDEX(fInputText) == fAnchorLimit) {
2980                     fHitEnd = TRUE;
2981                     fRequireEnd = TRUE;
2982                     break;
2983                 }
2984             }
2985
2986             // Not at end of input.  Back-track out.
2987             fp = (REStackFrame *)fStack->popFrame(fFrameSize);
2988             break;
2989
2990
2991          case URX_DOLLAR_M:                //  $, test for End of line in multi-line mode
2992              {
2993                  if (fp->fInputIdx >= fAnchorLimit) {
2994                      // We really are at the end of input.  Success.
2995                      fHitEnd = TRUE;
2996                      fRequireEnd = TRUE;
2997                      break;
2998                  }
2999                  // If we are positioned just before a new-line, succeed.
3000                  // It makes no difference where the new-line is within the input.
3001                  UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3002                  UChar32 c = UTEXT_CURRENT32(fInputText);
3003                  if (isLineTerminator(c)) {
3004                      // At a line end, except for the odd chance of  being in the middle of a CR/LF sequence
3005                      //  In multi-line mode, hitting a new-line just before the end of input does not
3006                      //   set the hitEnd or requireEnd flags
3007                      if ( !(c==0x0a && fp->fInputIdx>fAnchorStart && UTEXT_PREVIOUS32(fInputText)==0x0d)) {
3008                         break;
3009                      }
3010                  }
3011                  // not at a new line.  Fail.
3012                  fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3013              }
3014              break;
3015
3016
3017          case URX_DOLLAR_MD:                //  $, test for End of line in multi-line and UNIX_LINES mode
3018              {
3019                  if (fp->fInputIdx >= fAnchorLimit) {
3020                      // We really are at the end of input.  Success.
3021                      fHitEnd = TRUE;
3022                      fRequireEnd = TRUE;  // Java set requireEnd in this case, even though
3023                      break;               //   adding a new-line would not lose the match.
3024                  }
3025                  // If we are not positioned just before a new-line, the test fails; backtrack out.
3026                  // It makes no difference where the new-line is within the input.
3027                  UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3028                  if (UTEXT_CURRENT32(fInputText) != 0x0a) {
3029                      fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3030                  }
3031              }
3032              break;
3033
3034
3035        case URX_CARET:                    //  ^, test for start of line
3036             if (fp->fInputIdx != fAnchorStart) {
3037                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3038             }
3039             break;
3040
3041
3042        case URX_CARET_M:                   //  ^, test for start of line in mulit-line mode
3043            {
3044                if (fp->fInputIdx == fAnchorStart) {
3045                    // We are at the start input.  Success.
3046                    break;
3047                }
3048                // Check whether character just before the current pos is a new-line
3049                //   unless we are at the end of input
3050                UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3051                UChar32  c = UTEXT_PREVIOUS32(fInputText);
3052                if ((fp->fInputIdx < fAnchorLimit) && isLineTerminator(c)) {
3053                    //  It's a new-line.  ^ is true.  Success.
3054                    //  TODO:  what should be done with positions between a CR and LF?
3055                    break;
3056                }
3057                // Not at the start of a line.  Fail.
3058                fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3059            }
3060            break;
3061
3062
3063        case URX_CARET_M_UNIX:       //  ^, test for start of line in mulit-line + Unix-line mode
3064            {
3065                U_ASSERT(fp->fInputIdx >= fAnchorStart);
3066                if (fp->fInputIdx <= fAnchorStart) {
3067                    // We are at the start input.  Success.
3068                    break;
3069                }
3070                // Check whether character just before the current pos is a new-line
3071                U_ASSERT(fp->fInputIdx <= fAnchorLimit);
3072                UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3073                UChar32  c = UTEXT_PREVIOUS32(fInputText);
3074                if (c != 0x0a) {
3075                    // Not at the start of a line.  Back-track out.
3076                    fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3077                }
3078            }
3079            break;
3080
3081         case URX_BACKSLASH_B:          // Test for word boundaries
3082             {
3083                 UBool success = isWordBoundary(fp->fInputIdx);
3084                 success ^= (UBool)(opValue != 0);     // flip sense for \B
3085                 if (!success) {
3086                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3087                 }
3088             }
3089             break;
3090
3091
3092         case URX_BACKSLASH_BU:          // Test for word boundaries, Unicode-style
3093             {
3094                 UBool success = isUWordBoundary(fp->fInputIdx);
3095                 success ^= (UBool)(opValue != 0);     // flip sense for \B
3096                 if (!success) {
3097                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3098                 }
3099             }
3100             break;
3101
3102
3103         case URX_BACKSLASH_D:            // Test for decimal digit
3104             {
3105                 if (fp->fInputIdx >= fActiveLimit) {
3106                     fHitEnd = TRUE;
3107                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3108                     break;
3109                 }
3110
3111                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3112
3113                 UChar32 c = UTEXT_NEXT32(fInputText);
3114                 int8_t ctype = u_charType(c);     // TODO:  make a unicode set for this.  Will be faster.
3115                 UBool success = (ctype == U_DECIMAL_DIGIT_NUMBER);
3116                 success ^= (UBool)(opValue != 0);        // flip sense for \D
3117                 if (success) {
3118                     fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3119                 } else {
3120                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3121                 }
3122             }
3123             break;
3124
3125
3126         case URX_BACKSLASH_G:          // Test for position at end of previous match
3127             if (!((fMatch && fp->fInputIdx==fMatchEnd) || (fMatch==FALSE && fp->fInputIdx==fActiveStart))) {
3128                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3129             }
3130             break;
3131
3132
3133         case URX_BACKSLASH_H:            // Test for \h, horizontal white space.
3134             {
3135                 if (fp->fInputIdx >= fActiveLimit) {
3136                     fHitEnd = TRUE;
3137                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3138                     break;
3139                 }
3140                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3141                 UChar32 c = UTEXT_NEXT32(fInputText);
3142                 int8_t ctype = u_charType(c);
3143                 UBool success = (ctype == U_SPACE_SEPARATOR || c == 9);  // SPACE_SEPARATOR || TAB
3144                 success ^= (UBool)(opValue != 0);        // flip sense for \H
3145                 if (success) {
3146                     fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3147                 } else {
3148                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3149                 }
3150             }
3151             break;
3152
3153
3154         case URX_BACKSLASH_R:            // Test for \R, any line break sequence.
3155             {
3156                 if (fp->fInputIdx >= fActiveLimit) {
3157                     fHitEnd = TRUE;
3158                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3159                     break;
3160                 }
3161                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3162                 UChar32 c = UTEXT_NEXT32(fInputText);
3163                 if (isLineTerminator(c)) {
3164                     if (c == 0x0d && utext_current32(fInputText) == 0x0a) {
3165                         utext_next32(fInputText);
3166                     }
3167                     fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3168                 } else {
3169                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3170                 }
3171             }
3172             break;
3173
3174
3175         case URX_BACKSLASH_V:            // \v, any single line ending character.
3176             {
3177                 if (fp->fInputIdx >= fActiveLimit) {
3178                     fHitEnd = TRUE;
3179                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3180                     break;
3181                 }
3182                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3183                 UChar32 c = UTEXT_NEXT32(fInputText);
3184                 UBool success = isLineTerminator(c);
3185                 success ^= (UBool)(opValue != 0);        // flip sense for \V
3186                 if (success) {
3187                     fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3188                 } else {
3189                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3190                 }
3191             }
3192             break;
3193
3194
3195         case URX_BACKSLASH_X:
3196             //  Match a Grapheme, as defined by Unicode TR 29.
3197             //  Differs slightly from Perl, which consumes combining marks independently
3198             //    of context.
3199             {
3200
3201                 // Fail if at end of input
3202                 if (fp->fInputIdx >= fActiveLimit) {
3203                     fHitEnd = TRUE;
3204                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3205                     break;
3206                 }
3207
3208                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3209
3210                 // Examine (and consume) the current char.
3211                 //   Dispatch into a little state machine, based on the char.
3212                 UChar32  c;
3213                 c = UTEXT_NEXT32(fInputText);
3214                 fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3215                 UnicodeSet **sets = fPattern->fStaticSets;
3216                 if (sets[URX_GC_NORMAL]->contains(c))  goto GC_Extend;
3217                 if (sets[URX_GC_CONTROL]->contains(c)) goto GC_Control;
3218                 if (sets[URX_GC_L]->contains(c))       goto GC_L;
3219                 if (sets[URX_GC_LV]->contains(c))      goto GC_V;
3220                 if (sets[URX_GC_LVT]->contains(c))     goto GC_T;
3221                 if (sets[URX_GC_V]->contains(c))       goto GC_V;
3222                 if (sets[URX_GC_T]->contains(c))       goto GC_T;
3223                 goto GC_Extend;
3224
3225
3226
3227 GC_L:
3228                 if (fp->fInputIdx >= fActiveLimit)         goto GC_Done;
3229                 c = UTEXT_NEXT32(fInputText);
3230                 fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3231                 if (sets[URX_GC_L]->contains(c))       goto GC_L;
3232                 if (sets[URX_GC_LV]->contains(c))      goto GC_V;
3233                 if (sets[URX_GC_LVT]->contains(c))     goto GC_T;
3234                 if (sets[URX_GC_V]->contains(c))       goto GC_V;
3235                 (void)UTEXT_PREVIOUS32(fInputText);
3236                 fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3237                 goto GC_Extend;
3238
3239 GC_V:
3240                 if (fp->fInputIdx >= fActiveLimit)         goto GC_Done;
3241                 c = UTEXT_NEXT32(fInputText);
3242                 fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3243                 if (sets[URX_GC_V]->contains(c))       goto GC_V;
3244                 if (sets[URX_GC_T]->contains(c))       goto GC_T;
3245                 (void)UTEXT_PREVIOUS32(fInputText);
3246                 fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3247                 goto GC_Extend;
3248
3249 GC_T:
3250                 if (fp->fInputIdx >= fActiveLimit)         goto GC_Done;
3251                 c = UTEXT_NEXT32(fInputText);
3252                 fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3253                 if (sets[URX_GC_T]->contains(c))       goto GC_T;
3254                 (void)UTEXT_PREVIOUS32(fInputText);
3255                 fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3256                 goto GC_Extend;
3257
3258 GC_Extend:
3259                 // Combining characters are consumed here
3260                 for (;;) {
3261                     if (fp->fInputIdx >= fActiveLimit) {
3262                         break;
3263                     }
3264                     c = UTEXT_CURRENT32(fInputText);
3265                     if (sets[URX_GC_EXTEND]->contains(c) == FALSE) {
3266                         break;
3267                     }
3268                     (void)UTEXT_NEXT32(fInputText);
3269                     fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3270                 }
3271                 goto GC_Done;
3272
3273 GC_Control:
3274                 // Most control chars stand alone (don't combine with combining chars),
3275                 //   except for that CR/LF sequence is a single grapheme cluster.
3276                 if (c == 0x0d && fp->fInputIdx < fActiveLimit && UTEXT_CURRENT32(fInputText) == 0x0a) {
3277                     c = UTEXT_NEXT32(fInputText);
3278                     fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3279                 }
3280
3281 GC_Done:
3282                 if (fp->fInputIdx >= fActiveLimit) {
3283                     fHitEnd = TRUE;
3284                 }
3285                 break;
3286             }
3287
3288
3289
3290
3291         case URX_BACKSLASH_Z:          // Test for end of Input
3292             if (fp->fInputIdx < fAnchorLimit) {
3293                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3294             } else {
3295                 fHitEnd = TRUE;
3296                 fRequireEnd = TRUE;
3297             }
3298             break;
3299
3300
3301
3302         case URX_STATIC_SETREF:
3303             {
3304                 // Test input character against one of the predefined sets
3305                 //    (Word Characters, for example)
3306                 // The high bit of the op value is a flag for the match polarity.
3307                 //    0:   success if input char is in set.
3308                 //    1:   success if input char is not in set.
3309                 if (fp->fInputIdx >= fActiveLimit) {
3310                     fHitEnd = TRUE;
3311                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3312                     break;
3313                 }
3314
3315                 UBool success = ((opValue & URX_NEG_SET) == URX_NEG_SET);
3316                 opValue &= ~URX_NEG_SET;
3317                 U_ASSERT(opValue > 0 && opValue < URX_LAST_SET);
3318
3319                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3320                 UChar32 c = UTEXT_NEXT32(fInputText);
3321                 if (c < 256) {
3322                     Regex8BitSet *s8 = &fPattern->fStaticSets8[opValue];
3323                     if (s8->contains(c)) {
3324                         success = !success;
3325                     }
3326                 } else {
3327                     const UnicodeSet *s = fPattern->fStaticSets[opValue];
3328                     if (s->contains(c)) {
3329                         success = !success;
3330                     }
3331                 }
3332                 if (success) {
3333                     fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3334                 } else {
3335                     // the character wasn't in the set.
3336                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3337                 }
3338             }
3339             break;
3340
3341
3342         case URX_STAT_SETREF_N:
3343             {
3344                 // Test input character for NOT being a member of  one of
3345                 //    the predefined sets (Word Characters, for example)
3346                 if (fp->fInputIdx >= fActiveLimit) {
3347                     fHitEnd = TRUE;
3348                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3349                     break;
3350                 }
3351
3352                 U_ASSERT(opValue > 0 && opValue < URX_LAST_SET);
3353
3354                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3355
3356                 UChar32 c = UTEXT_NEXT32(fInputText);
3357                 if (c < 256) {
3358                     Regex8BitSet *s8 = &fPattern->fStaticSets8[opValue];
3359                     if (s8->contains(c) == FALSE) {
3360                         fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3361                         break;
3362                     }
3363                 } else {
3364                     const UnicodeSet *s = fPattern->fStaticSets[opValue];
3365                     if (s->contains(c) == FALSE) {
3366                         fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3367                         break;
3368                     }
3369                 }
3370                 // the character wasn't in the set.
3371                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3372             }
3373             break;
3374
3375
3376         case URX_SETREF:
3377             if (fp->fInputIdx >= fActiveLimit) {
3378                 fHitEnd = TRUE;
3379                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3380                 break;
3381             } else {
3382                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3383
3384                 // There is input left.  Pick up one char and test it for set membership.
3385                 UChar32 c = UTEXT_NEXT32(fInputText);
3386                 U_ASSERT(opValue > 0 && opValue < fSets->size());
3387                 if (c<256) {
3388                     Regex8BitSet *s8 = &fPattern->fSets8[opValue];
3389                     if (s8->contains(c)) {
3390                         fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3391                         break;
3392                     }
3393                 } else {
3394                     UnicodeSet *s = (UnicodeSet *)fSets->elementAt(opValue);
3395                     if (s->contains(c)) {
3396                         // The character is in the set.  A Match.
3397                         fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3398                         break;
3399                     }
3400                 }
3401
3402                 // the character wasn't in the set.
3403                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3404             }
3405             break;
3406
3407
3408         case URX_DOTANY:
3409             {
3410                 // . matches anything, but stops at end-of-line.
3411                 if (fp->fInputIdx >= fActiveLimit) {
3412                     // At end of input.  Match failed.  Backtrack out.
3413                     fHitEnd = TRUE;
3414                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3415                     break;
3416                 }
3417
3418                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3419
3420                 // There is input left.  Advance over one char, unless we've hit end-of-line
3421                 UChar32 c = UTEXT_NEXT32(fInputText);
3422                 if (isLineTerminator(c)) {
3423                     // End of line in normal mode.   . does not match.
3424                         fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3425                     break;
3426                 }
3427                 fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3428             }
3429             break;
3430
3431
3432         case URX_DOTANY_ALL:
3433             {
3434                 // ., in dot-matches-all (including new lines) mode
3435                 if (fp->fInputIdx >= fActiveLimit) {
3436                     // At end of input.  Match failed.  Backtrack out.
3437                     fHitEnd = TRUE;
3438                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3439                     break;
3440                 }
3441
3442                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3443
3444                 // There is input left.  Advance over one char, except if we are
3445                 //   at a cr/lf, advance over both of them.
3446                 UChar32 c;
3447                 c = UTEXT_NEXT32(fInputText);
3448                 fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3449                 if (c==0x0d && fp->fInputIdx < fActiveLimit) {
3450                     // In the case of a CR/LF, we need to advance over both.
3451                     UChar32 nextc = UTEXT_CURRENT32(fInputText);
3452                     if (nextc == 0x0a) {
3453                         (void)UTEXT_NEXT32(fInputText);
3454                         fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3455                     }
3456                 }
3457             }
3458             break;
3459
3460
3461         case URX_DOTANY_UNIX:
3462             {
3463                 // '.' operator, matches all, but stops at end-of-line.
3464                 //   UNIX_LINES mode, so 0x0a is the only recognized line ending.
3465                 if (fp->fInputIdx >= fActiveLimit) {
3466                     // At end of input.  Match failed.  Backtrack out.
3467                     fHitEnd = TRUE;
3468                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3469                     break;
3470                 }
3471
3472                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3473
3474                 // There is input left.  Advance over one char, unless we've hit end-of-line
3475                 UChar32 c = UTEXT_NEXT32(fInputText);
3476                 if (c == 0x0a) {
3477                     // End of line in normal mode.   '.' does not match the \n
3478                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3479                 } else {
3480                     fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3481                 }
3482             }
3483             break;
3484
3485
3486         case URX_JMP:
3487             fp->fPatIdx = opValue;
3488             break;
3489
3490         case URX_FAIL:
3491             isMatch = FALSE;
3492             goto breakFromLoop;
3493
3494         case URX_JMP_SAV:
3495             U_ASSERT(opValue < fPattern->fCompiledPat->size());
3496             fp = StateSave(fp, fp->fPatIdx, status);       // State save to loc following current
3497             fp->fPatIdx = opValue;                         // Then JMP.
3498             break;
3499
3500         case URX_JMP_SAV_X:
3501             // This opcode is used with (x)+, when x can match a zero length string.
3502             // Same as JMP_SAV, except conditional on the match having made forward progress.
3503             // Destination of the JMP must be a URX_STO_INP_LOC, from which we get the
3504             //   data address of the input position at the start of the loop.
3505             {
3506                 U_ASSERT(opValue > 0 && opValue < fPattern->fCompiledPat->size());
3507                 int32_t  stoOp = (int32_t)pat[opValue-1];
3508                 U_ASSERT(URX_TYPE(stoOp) == URX_STO_INP_LOC);
3509                 int32_t  frameLoc = URX_VAL(stoOp);
3510                 U_ASSERT(frameLoc >= 0 && frameLoc < fFrameSize);
3511                 int64_t prevInputIdx = fp->fExtra[frameLoc];
3512                 U_ASSERT(prevInputIdx <= fp->fInputIdx);
3513                 if (prevInputIdx < fp->fInputIdx) {
3514                     // The match did make progress.  Repeat the loop.
3515                     fp = StateSave(fp, fp->fPatIdx, status);  // State save to loc following current
3516                     fp->fPatIdx = opValue;
3517                     fp->fExtra[frameLoc] = fp->fInputIdx;
3518                 }
3519                 // If the input position did not advance, we do nothing here,
3520                 //   execution will fall out of the loop.
3521             }
3522             break;
3523
3524         case URX_CTR_INIT:
3525             {
3526                 U_ASSERT(opValue >= 0 && opValue < fFrameSize-2);
3527                 fp->fExtra[opValue] = 0;                 //  Set the loop counter variable to zero
3528
3529                 // Pick up the three extra operands that CTR_INIT has, and
3530                 //    skip the pattern location counter past
3531                 int32_t instrOperandLoc = (int32_t)fp->fPatIdx;
3532                 fp->fPatIdx += 3;
3533                 int32_t loopLoc  = URX_VAL(pat[instrOperandLoc]);
3534                 int32_t minCount = (int32_t)pat[instrOperandLoc+1];
3535                 int32_t maxCount = (int32_t)pat[instrOperandLoc+2];
3536                 U_ASSERT(minCount>=0);
3537                 U_ASSERT(maxCount>=minCount || maxCount==-1);
3538                 U_ASSERT(loopLoc>=fp->fPatIdx);
3539
3540                 if (minCount == 0) {
3541                     fp = StateSave(fp, loopLoc+1, status);
3542                 }
3543                 if (maxCount == -1) {
3544                     fp->fExtra[opValue+1] = fp->fInputIdx;   //  For loop breaking.
3545                 } else if (maxCount == 0) {
3546                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3547                 }
3548             }
3549             break;
3550
3551         case URX_CTR_LOOP:
3552             {
3553                 U_ASSERT(opValue>0 && opValue < fp->fPatIdx-2);
3554                 int32_t initOp = (int32_t)pat[opValue];
3555                 U_ASSERT(URX_TYPE(initOp) == URX_CTR_INIT);
3556                 int64_t *pCounter = &fp->fExtra[URX_VAL(initOp)];
3557                 int32_t minCount  = (int32_t)pat[opValue+2];
3558                 int32_t maxCount  = (int32_t)pat[opValue+3];
3559                 (*pCounter)++;
3560                 if ((uint64_t)*pCounter >= (uint32_t)maxCount && maxCount != -1) {
3561                     U_ASSERT(*pCounter == maxCount);
3562                     break;
3563                 }
3564                 if (*pCounter >= minCount) {
3565                     if (maxCount == -1) {
3566                         // Loop has no hard upper bound.
3567                         // Check that it is progressing through the input, break if it is not.
3568                         int64_t *pLastInputIdx =  &fp->fExtra[URX_VAL(initOp) + 1];
3569                         if (fp->fInputIdx == *pLastInputIdx) {
3570                             break;
3571                         } else {
3572                             *pLastInputIdx = fp->fInputIdx;
3573                         }
3574                     }
3575                     fp = StateSave(fp, fp->fPatIdx, status);
3576                 } else {
3577                     // Increment time-out counter. (StateSave() does it if count >= minCount)
3578                     fTickCounter--;
3579                     if (fTickCounter <= 0) {
3580                         IncrementTime(status);    // Re-initializes fTickCounter
3581                     }
3582                 }
3583
3584                 fp->fPatIdx = opValue + 4;    // Loop back.
3585             }
3586             break;
3587
3588         case URX_CTR_INIT_NG:
3589             {
3590                 // Initialize a non-greedy loop
3591                 U_ASSERT(opValue >= 0 && opValue < fFrameSize-2);
3592                 fp->fExtra[opValue] = 0;                 //  Set the loop counter variable to zero
3593
3594                 // Pick up the three extra operands that CTR_INIT_NG has, and
3595                 //    skip the pattern location counter past
3596                 int32_t instrOperandLoc = (int32_t)fp->fPatIdx;
3597                 fp->fPatIdx += 3;
3598                 int32_t loopLoc  = URX_VAL(pat[instrOperandLoc]);
3599                 int32_t minCount = (int32_t)pat[instrOperandLoc+1];
3600                 int32_t maxCount = (int32_t)pat[instrOperandLoc+2];
3601                 U_ASSERT(minCount>=0);
3602                 U_ASSERT(maxCount>=minCount || maxCount==-1);
3603                 U_ASSERT(loopLoc>fp->fPatIdx);
3604                 if (maxCount == -1) {
3605                     fp->fExtra[opValue+1] = fp->fInputIdx;   //  Save initial input index for loop breaking.
3606                 }
3607
3608                 if (minCount == 0) {
3609                     if (maxCount != 0) {
3610                         fp = StateSave(fp, fp->fPatIdx, status);
3611                     }
3612                     fp->fPatIdx = loopLoc+1;   // Continue with stuff after repeated block
3613                 }
3614             }
3615             break;
3616
3617         case URX_CTR_LOOP_NG:
3618             {
3619                 // Non-greedy {min, max} loops
3620                 U_ASSERT(opValue>0 && opValue < fp->fPatIdx-2);
3621                 int32_t initOp = (int32_t)pat[opValue];
3622                 U_ASSERT(URX_TYPE(initOp) == URX_CTR_INIT_NG);
3623                 int64_t *pCounter = &fp->fExtra[URX_VAL(initOp)];
3624                 int32_t minCount  = (int32_t)pat[opValue+2];
3625                 int32_t maxCount  = (int32_t)pat[opValue+3];
3626
3627                 (*pCounter)++;
3628                 if ((uint64_t)*pCounter >= (uint32_t)maxCount && maxCount != -1) {
3629                     // The loop has matched the maximum permitted number of times.
3630                     //   Break out of here with no action.  Matching will
3631                     //   continue with the following pattern.
3632                     U_ASSERT(*pCounter == maxCount);
3633                     break;
3634                 }
3635
3636                 if (*pCounter < minCount) {
3637                     // We haven't met the minimum number of matches yet.
3638                     //   Loop back for another one.
3639                     fp->fPatIdx = opValue + 4;    // Loop back.
3640                     // Increment time-out counter. (StateSave() does it if count >= minCount)
3641                     fTickCounter--;
3642                     if (fTickCounter <= 0) {
3643                         IncrementTime(status);    // Re-initializes fTickCounter
3644                     }
3645                 } else {
3646                     // We do have the minimum number of matches.
3647
3648                     // If there is no upper bound on the loop iterations, check that the input index
3649                     // is progressing, and stop the loop if it is not.
3650                     if (maxCount == -1) {
3651                         int64_t *pLastInputIdx =  &fp->fExtra[URX_VAL(initOp) + 1];
3652                         if (fp->fInputIdx == *pLastInputIdx) {
3653                             break;
3654                         }
3655                         *pLastInputIdx = fp->fInputIdx;
3656                     }
3657
3658                     // Loop Continuation: we will fall into the pattern following the loop
3659                     //   (non-greedy, don't execute loop body first), but first do
3660                     //   a state save to the top of the loop, so that a match failure
3661                     //   in the following pattern will try another iteration of the loop.
3662                     fp = StateSave(fp, opValue + 4, status);
3663                 }
3664             }
3665             break;
3666
3667         case URX_STO_SP:
3668             U_ASSERT(opValue >= 0 && opValue < fPattern->fDataSize);
3669             fData[opValue] = fStack->size();
3670             break;
3671
3672         case URX_LD_SP:
3673             {
3674                 U_ASSERT(opValue >= 0 && opValue < fPattern->fDataSize);
3675                 int32_t newStackSize = (int32_t)fData[opValue];
3676                 U_ASSERT(newStackSize <= fStack->size());
3677                 int64_t *newFP = fStack->getBuffer() + newStackSize - fFrameSize;
3678                 if (newFP == (int64_t *)fp) {
3679                     break;
3680                 }
3681                 int32_t j;
3682                 for (j=0; j<fFrameSize; j++) {
3683                     newFP[j] = ((int64_t *)fp)[j];
3684                 }
3685                 fp = (REStackFrame *)newFP;
3686                 fStack->setSize(newStackSize);
3687             }
3688             break;
3689
3690         case URX_BACKREF:
3691             {
3692                 U_ASSERT(opValue < fFrameSize);
3693                 int64_t groupStartIdx = fp->fExtra[opValue];
3694                 int64_t groupEndIdx   = fp->fExtra[opValue+1];
3695                 U_ASSERT(groupStartIdx <= groupEndIdx);
3696                 if (groupStartIdx < 0) {
3697                     // This capture group has not participated in the match thus far,
3698                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);   // FAIL, no match.
3699                     break;
3700                 }
3701                 UTEXT_SETNATIVEINDEX(fAltInputText, groupStartIdx);
3702                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3703
3704                 //   Note: if the capture group match was of an empty string the backref
3705                 //         match succeeds.  Verified by testing:  Perl matches succeed
3706                 //         in this case, so we do too.
3707
3708                 UBool success = TRUE;
3709                 for (;;) {
3710                     if (utext_getNativeIndex(fAltInputText) >= groupEndIdx) {
3711                         success = TRUE;
3712                         break;
3713                     }
3714                     if (utext_getNativeIndex(fInputText) >= fActiveLimit) {
3715                         success = FALSE;
3716                         fHitEnd = TRUE;
3717                         break;
3718                     }
3719                     UChar32 captureGroupChar = utext_next32(fAltInputText);
3720                     UChar32 inputChar = utext_next32(fInputText);
3721                     if (inputChar != captureGroupChar) {
3722                         success = FALSE;
3723                         break;
3724                     }
3725                 }
3726
3727                 if (success) {
3728                     fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3729                 } else {
3730                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3731                 }
3732             }
3733             break;
3734
3735
3736
3737         case URX_BACKREF_I:
3738             {
3739                 U_ASSERT(opValue < fFrameSize);
3740                 int64_t groupStartIdx = fp->fExtra[opValue];
3741                 int64_t groupEndIdx   = fp->fExtra[opValue+1];
3742                 U_ASSERT(groupStartIdx <= groupEndIdx);
3743                 if (groupStartIdx < 0) {
3744                     // This capture group has not participated in the match thus far,
3745                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);   // FAIL, no match.
3746                     break;
3747                 }
3748                 utext_setNativeIndex(fAltInputText, groupStartIdx);
3749                 utext_setNativeIndex(fInputText, fp->fInputIdx);
3750                 CaseFoldingUTextIterator captureGroupItr(*fAltInputText);
3751                 CaseFoldingUTextIterator inputItr(*fInputText);
3752
3753                 //   Note: if the capture group match was of an empty string the backref
3754                 //         match succeeds.  Verified by testing:  Perl matches succeed
3755                 //         in this case, so we do too.
3756
3757                 UBool success = TRUE;
3758                 for (;;) {
3759                     if (!captureGroupItr.inExpansion() && utext_getNativeIndex(fAltInputText) >= groupEndIdx) {
3760                         success = TRUE;
3761                         break;
3762                     }
3763                     if (!inputItr.inExpansion() && utext_getNativeIndex(fInputText) >= fActiveLimit) {
3764                         success = FALSE;
3765                         fHitEnd = TRUE;
3766                         break;
3767                     }
3768                     UChar32 captureGroupChar = captureGroupItr.next();
3769                     UChar32 inputChar = inputItr.next();
3770                     if (inputChar != captureGroupChar) {
3771                         success = FALSE;
3772                         break;
3773                     }
3774                 }
3775
3776                 if (success && inputItr.inExpansion()) {
3777                     // We otained a match by consuming part of a string obtained from
3778                     // case-folding a single code point of the input text.
3779                     // This does not count as an overall match.
3780                     success = FALSE;
3781                 }
3782
3783                 if (success) {
3784                     fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3785                 } else {
3786                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3787                 }
3788
3789             }
3790             break;
3791
3792         case URX_STO_INP_LOC:
3793             {
3794                 U_ASSERT(opValue >= 0 && opValue < fFrameSize);
3795                 fp->fExtra[opValue] = fp->fInputIdx;
3796             }
3797             break;
3798
3799         case URX_JMPX:
3800             {
3801                 int32_t instrOperandLoc = (int32_t)fp->fPatIdx;
3802                 fp->fPatIdx += 1;
3803                 int32_t dataLoc  = URX_VAL(pat[instrOperandLoc]);
3804                 U_ASSERT(dataLoc >= 0 && dataLoc < fFrameSize);
3805                 int64_t savedInputIdx = fp->fExtra[dataLoc];
3806                 U_ASSERT(savedInputIdx <= fp->fInputIdx);
3807                 if (savedInputIdx < fp->fInputIdx) {
3808                     fp->fPatIdx = opValue;                               // JMP
3809                 } else {
3810                      fp = (REStackFrame *)fStack->popFrame(fFrameSize);   // FAIL, no progress in loop.
3811                 }
3812             }
3813             break;
3814
3815         case URX_LA_START:
3816             {
3817                 // Entering a lookahead block.
3818                 // Save Stack Ptr, Input Pos.
3819                 U_ASSERT(opValue>=0 && opValue+1<fPattern->fDataSize);
3820                 fData[opValue]   = fStack->size();
3821                 fData[opValue+1] = fp->fInputIdx;
3822                 fActiveStart     = fLookStart;          // Set the match region change for
3823                 fActiveLimit     = fLookLimit;          //   transparent bounds.
3824             }
3825             break;
3826
3827         case URX_LA_END:
3828             {
3829                 // Leaving a look-ahead block.
3830                 //  restore Stack Ptr, Input Pos to positions they had on entry to block.
3831                 U_ASSERT(opValue>=0 && opValue+1<fPattern->fDataSize);
3832                 int32_t stackSize = fStack->size();
3833                 int32_t newStackSize =(int32_t)fData[opValue];
3834                 U_ASSERT(stackSize >= newStackSize);
3835                 if (stackSize > newStackSize) {
3836                     // Copy the current top frame back to the new (cut back) top frame.
3837                     //   This makes the capture groups from within the look-ahead
3838                     //   expression available.
3839                     int64_t *newFP = fStack->getBuffer() + newStackSize - fFrameSize;
3840                     int32_t j;
3841                     for (j=0; j<fFrameSize; j++) {
3842                         newFP[j] = ((int64_t *)fp)[j];
3843                     }
3844                     fp = (REStackFrame *)newFP;
3845                     fStack->setSize(newStackSize);
3846                 }
3847                 fp->fInputIdx = fData[opValue+1];
3848
3849                 // Restore the active region bounds in the input string; they may have
3850                 //    been changed because of transparent bounds on a Region.
3851                 fActiveStart = fRegionStart;
3852                 fActiveLimit = fRegionLimit;
3853             }
3854             break;
3855
3856         case URX_ONECHAR_I:
3857             // Case insensitive one char.  The char from the pattern is already case folded.
3858             // Input text is not, but case folding the input can not reduce two or more code
3859             // points to one.
3860             if (fp->fInputIdx < fActiveLimit) {
3861                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3862
3863                 UChar32 c = UTEXT_NEXT32(fInputText);
3864                 if (u_foldCase(c, U_FOLD_CASE_DEFAULT) == opValue) {
3865                     fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3866                     break;
3867                 }
3868             } else {
3869                 fHitEnd = TRUE;
3870             }
3871
3872             fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3873             break;
3874
3875         case URX_STRING_I:
3876             {
3877                 // Case-insensitive test input against a literal string.
3878                 // Strings require two slots in the compiled pattern, one for the
3879                 //   offset to the string text, and one for the length.
3880                 //   The compiled string has already been case folded.
3881                 {
3882                     const UChar *patternString = litText + opValue;
3883                     int32_t      patternStringIdx  = 0;
3884
3885                     op      = (int32_t)pat[fp->fPatIdx];
3886                     fp->fPatIdx++;
3887                     opType  = URX_TYPE(op);
3888                     opValue = URX_VAL(op);
3889                     U_ASSERT(opType == URX_STRING_LEN);
3890                     int32_t patternStringLen = opValue;  // Length of the string from the pattern.
3891
3892
3893                     UChar32   cPattern;
3894                     UChar32   cText;
3895                     UBool     success = TRUE;
3896
3897                     UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
3898                     CaseFoldingUTextIterator inputIterator(*fInputText);
3899                     while (patternStringIdx < patternStringLen) {
3900                         if (!inputIterator.inExpansion() && UTEXT_GETNATIVEINDEX(fInputText) >= fActiveLimit) {
3901                             success = FALSE;
3902                             fHitEnd = TRUE;
3903                             break;
3904                         }
3905                         U16_NEXT(patternString, patternStringIdx, patternStringLen, cPattern);
3906                         cText = inputIterator.next();
3907                         if (cText != cPattern) {
3908                             success = FALSE;
3909                             break;
3910                         }
3911                     }
3912                     if (inputIterator.inExpansion()) {
3913                         success = FALSE;
3914                     }
3915
3916                     if (success) {
3917                         fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
3918                     } else {
3919                         fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3920                     }
3921                 }
3922             }
3923             break;
3924
3925         case URX_LB_START:
3926             {
3927                 // Entering a look-behind block.
3928                 // Save Stack Ptr, Input Pos.
3929                 //   TODO:  implement transparent bounds.  Ticket #6067
3930                 U_ASSERT(opValue>=0 && opValue+1<fPattern->fDataSize);
3931                 fData[opValue]   = fStack->size();
3932                 fData[opValue+1] = fp->fInputIdx;
3933                 // Init the variable containing the start index for attempted matches.
3934                 fData[opValue+2] = -1;
3935                 // Save input string length, then reset to pin any matches to end at
3936                 //   the current position.
3937                 fData[opValue+3] = fActiveLimit;
3938                 fActiveLimit     = fp->fInputIdx;
3939             }
3940             break;
3941
3942
3943         case URX_LB_CONT:
3944             {
3945                 // Positive Look-Behind, at top of loop checking for matches of LB expression
3946                 //    at all possible input starting positions.
3947
3948                 // Fetch the min and max possible match lengths.  They are the operands
3949                 //   of this op in the pattern.
3950                 int32_t minML = (int32_t)pat[fp->fPatIdx++];
3951                 int32_t maxML = (int32_t)pat[fp->fPatIdx++];
3952                 if (!UTEXT_USES_U16(fInputText)) {
3953                     // utf-8 fix to maximum match length. The pattern compiler assumes utf-16.
3954                     // The max length need not be exact; it just needs to be >= actual maximum.
3955                     maxML *= 3;
3956                 }
3957                 U_ASSERT(minML <= maxML);
3958                 U_ASSERT(minML >= 0);
3959
3960                 // Fetch (from data) the last input index where a match was attempted.
3961                 U_ASSERT(opValue>=0 && opValue+1<fPattern->fDataSize);
3962                 int64_t  &lbStartIdx = fData[opValue+2];
3963                 if (lbStartIdx < 0) {
3964                     // First time through loop.
3965                     lbStartIdx = fp->fInputIdx - minML;
3966                     if (lbStartIdx > 0) {
3967                         // move index to a code point boudary, if it's not on one already.
3968                         UTEXT_SETNATIVEINDEX(fInputText, lbStartIdx);
3969                         lbStartIdx = UTEXT_GETNATIVEINDEX(fInputText);
3970                     }
3971                 } else {
3972                     // 2nd through nth time through the loop.
3973                     // Back up start position for match by one.
3974                     if (lbStartIdx == 0) {
3975                         (lbStartIdx)--;
3976                     } else {
3977                         UTEXT_SETNATIVEINDEX(fInputText, lbStartIdx);
3978                         (void)UTEXT_PREVIOUS32(fInputText);
3979                         lbStartIdx = UTEXT_GETNATIVEINDEX(fInputText);
3980                     }
3981                 }
3982
3983                 if (lbStartIdx < 0 || lbStartIdx < fp->fInputIdx - maxML) {
3984                     // We have tried all potential match starting points without
3985                     //  getting a match.  Backtrack out, and out of the
3986                     //   Look Behind altogether.
3987                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
3988                     int64_t restoreInputLen = fData[opValue+3];
3989                     U_ASSERT(restoreInputLen >= fActiveLimit);
3990                     U_ASSERT(restoreInputLen <= fInputLength);
3991                     fActiveLimit = restoreInputLen;
3992                     break;
3993                 }
3994
3995                 //    Save state to this URX_LB_CONT op, so failure to match will repeat the loop.
3996                 //      (successful match will fall off the end of the loop.)
3997                 fp = StateSave(fp, fp->fPatIdx-3, status);
3998                 fp->fInputIdx = lbStartIdx;
3999             }
4000             break;
4001
4002         case URX_LB_END:
4003             // End of a look-behind block, after a successful match.
4004             {
4005                 U_ASSERT(opValue>=0 && opValue+1<fPattern->fDataSize);
4006                 if (fp->fInputIdx != fActiveLimit) {
4007                     //  The look-behind expression matched, but the match did not
4008                     //    extend all the way to the point that we are looking behind from.
4009                     //  FAIL out of here, which will take us back to the LB_CONT, which
4010                     //     will retry the match starting at another position or fail
4011                     //     the look-behind altogether, whichever is appropriate.
4012                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4013                     break;
4014                 }
4015
4016                 // Look-behind match is good.  Restore the orignal input string length,
4017                 //   which had been truncated to pin the end of the lookbehind match to the
4018                 //   position being looked-behind.
4019                 int64_t originalInputLen = fData[opValue+3];
4020                 U_ASSERT(originalInputLen >= fActiveLimit);
4021                 U_ASSERT(originalInputLen <= fInputLength);
4022                 fActiveLimit = originalInputLen;
4023             }
4024             break;
4025
4026
4027         case URX_LBN_CONT:
4028             {
4029                 // Negative Look-Behind, at top of loop checking for matches of LB expression
4030                 //    at all possible input starting positions.
4031
4032                 // Fetch the extra parameters of this op.
4033                 int32_t minML       = (int32_t)pat[fp->fPatIdx++];
4034                 int32_t maxML       = (int32_t)pat[fp->fPatIdx++];
4035                 if (!UTEXT_USES_U16(fInputText)) {
4036                     // utf-8 fix to maximum match length. The pattern compiler assumes utf-16.
4037                     // The max length need not be exact; it just needs to be >= actual maximum.
4038                     maxML *= 3;
4039                 }
4040                 int32_t continueLoc = (int32_t)pat[fp->fPatIdx++];
4041                         continueLoc = URX_VAL(continueLoc);
4042                 U_ASSERT(minML <= maxML);
4043                 U_ASSERT(minML >= 0);
4044                 U_ASSERT(continueLoc > fp->fPatIdx);
4045
4046                 // Fetch (from data) the last input index where a match was attempted.
4047                 U_ASSERT(opValue>=0 && opValue+1<fPattern->fDataSize);
4048                 int64_t  &lbStartIdx = fData[opValue+2];
4049                 if (lbStartIdx < 0) {
4050                     // First time through loop.
4051                     lbStartIdx = fp->fInputIdx - minML;
4052                     if (lbStartIdx > 0) {
4053                         // move index to a code point boudary, if it's not on one already.
4054                         UTEXT_SETNATIVEINDEX(fInputText, lbStartIdx);
4055                         lbStartIdx = UTEXT_GETNATIVEINDEX(fInputText);
4056                     }
4057                 } else {
4058                     // 2nd through nth time through the loop.
4059                     // Back up start position for match by one.
4060                     if (lbStartIdx == 0) {
4061                         (lbStartIdx)--;
4062                     } else {
4063                         UTEXT_SETNATIVEINDEX(fInputText, lbStartIdx);
4064                         (void)UTEXT_PREVIOUS32(fInputText);
4065                         lbStartIdx = UTEXT_GETNATIVEINDEX(fInputText);
4066                     }
4067                 }
4068
4069                 if (lbStartIdx < 0 || lbStartIdx < fp->fInputIdx - maxML) {
4070                     // We have tried all potential match starting points without
4071                     //  getting a match, which means that the negative lookbehind as
4072                     //  a whole has succeeded.  Jump forward to the continue location
4073                     int64_t restoreInputLen = fData[opValue+3];
4074                     U_ASSERT(restoreInputLen >= fActiveLimit);
4075                     U_ASSERT(restoreInputLen <= fInputLength);
4076                     fActiveLimit = restoreInputLen;
4077                     fp->fPatIdx = continueLoc;
4078                     break;
4079                 }
4080
4081                 //    Save state to this URX_LB_CONT op, so failure to match will repeat the loop.
4082                 //      (successful match will cause a FAIL out of the loop altogether.)
4083                 fp = StateSave(fp, fp->fPatIdx-4, status);
4084                 fp->fInputIdx = lbStartIdx;
4085             }
4086             break;
4087
4088         case URX_LBN_END:
4089             // End of a negative look-behind block, after a successful match.
4090             {
4091                 U_ASSERT(opValue>=0 && opValue+1<fPattern->fDataSize);
4092                 if (fp->fInputIdx != fActiveLimit) {
4093                     //  The look-behind expression matched, but the match did not
4094                     //    extend all the way to the point that we are looking behind from.
4095                     //  FAIL out of here, which will take us back to the LB_CONT, which
4096                     //     will retry the match starting at another position or succeed
4097                     //     the look-behind altogether, whichever is appropriate.
4098                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4099                     break;
4100                 }
4101
4102                 // Look-behind expression matched, which means look-behind test as
4103                 //   a whole Fails
4104
4105                 //   Restore the orignal input string length, which had been truncated
4106                 //   inorder to pin the end of the lookbehind match
4107                 //   to the position being looked-behind.
4108                 int64_t originalInputLen = fData[opValue+3];
4109                 U_ASSERT(originalInputLen >= fActiveLimit);
4110                 U_ASSERT(originalInputLen <= fInputLength);
4111                 fActiveLimit = originalInputLen;
4112
4113                 // Restore original stack position, discarding any state saved
4114                 //   by the successful pattern match.
4115                 U_ASSERT(opValue>=0 && opValue+1<fPattern->fDataSize);
4116                 int32_t newStackSize = (int32_t)fData[opValue];
4117                 U_ASSERT(fStack->size() > newStackSize);
4118                 fStack->setSize(newStackSize);
4119
4120                 //  FAIL, which will take control back to someplace
4121                 //  prior to entering the look-behind test.
4122                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4123             }
4124             break;
4125
4126
4127         case URX_LOOP_SR_I:
4128             // Loop Initialization for the optimized implementation of
4129             //     [some character set]*
4130             //   This op scans through all matching input.
4131             //   The following LOOP_C op emulates stack unwinding if the following pattern fails.
4132             {
4133                 U_ASSERT(opValue > 0 && opValue < fSets->size());
4134                 Regex8BitSet *s8 = &fPattern->fSets8[opValue];
4135                 UnicodeSet   *s  = (UnicodeSet *)fSets->elementAt(opValue);
4136
4137                 // Loop through input, until either the input is exhausted or
4138                 //   we reach a character that is not a member of the set.
4139                 int64_t ix = fp->fInputIdx;
4140                 UTEXT_SETNATIVEINDEX(fInputText, ix);
4141                 for (;;) {
4142                     if (ix >= fActiveLimit) {
4143                         fHitEnd = TRUE;
4144                         break;
4145                     }
4146                     UChar32 c = UTEXT_NEXT32(fInputText);
4147                     if (c<256) {
4148                         if (s8->contains(c) == FALSE) {
4149                             break;
4150                         }
4151                     } else {
4152                         if (s->contains(c) == FALSE) {
4153                             break;
4154                         }
4155                     }
4156                     ix = UTEXT_GETNATIVEINDEX(fInputText);
4157                 }
4158
4159                 // If there were no matching characters, skip over the loop altogether.
4160                 //   The loop doesn't run at all, a * op always succeeds.
4161                 if (ix == fp->fInputIdx) {
4162                     fp->fPatIdx++;   // skip the URX_LOOP_C op.
4163                     break;
4164                 }
4165
4166                 // Peek ahead in the compiled pattern, to the URX_LOOP_C that
4167                 //   must follow.  It's operand is the stack location
4168                 //   that holds the starting input index for the match of this [set]*
4169                 int32_t loopcOp = (int32_t)pat[fp->fPatIdx];
4170                 U_ASSERT(URX_TYPE(loopcOp) == URX_LOOP_C);
4171                 int32_t stackLoc = URX_VAL(loopcOp);
4172                 U_ASSERT(stackLoc >= 0 && stackLoc < fFrameSize);
4173                 fp->fExtra[stackLoc] = fp->fInputIdx;
4174                 fp->fInputIdx = ix;
4175
4176                 // Save State to the URX_LOOP_C op that follows this one,
4177                 //   so that match failures in the following code will return to there.
4178                 //   Then bump the pattern idx so the LOOP_C is skipped on the way out of here.
4179                 fp = StateSave(fp, fp->fPatIdx, status);
4180                 fp->fPatIdx++;
4181             }
4182             break;
4183
4184
4185         case URX_LOOP_DOT_I:
4186             // Loop Initialization for the optimized implementation of .*
4187             //   This op scans through all remaining input.
4188             //   The following LOOP_C op emulates stack unwinding if the following pattern fails.
4189             {
4190                 // Loop through input until the input is exhausted (we reach an end-of-line)
4191                 // In DOTALL mode, we can just go straight to the end of the input.
4192                 int64_t ix;
4193                 if ((opValue & 1) == 1) {
4194                     // Dot-matches-All mode.  Jump straight to the end of the string.
4195                     ix = fActiveLimit;
4196                     fHitEnd = TRUE;
4197                 } else {
4198                     // NOT DOT ALL mode.  Line endings do not match '.'
4199                     // Scan forward until a line ending or end of input.
4200                     ix = fp->fInputIdx;
4201                     UTEXT_SETNATIVEINDEX(fInputText, ix);
4202                     for (;;) {
4203                         if (ix >= fActiveLimit) {
4204                             fHitEnd = TRUE;
4205                             break;
4206                         }
4207                         UChar32 c = UTEXT_NEXT32(fInputText);
4208                         if ((c & 0x7f) <= 0x29) {          // Fast filter of non-new-line-s
4209                             if ((c == 0x0a) ||             //  0x0a is newline in both modes.
4210                                (((opValue & 2) == 0) &&    // IF not UNIX_LINES mode
4211                                     isLineTerminator(c))) {
4212                                 //  char is a line ending.  Exit the scanning loop.
4213                                 break;
4214                             }
4215                         }
4216                         ix = UTEXT_GETNATIVEINDEX(fInputText);
4217                     }
4218                 }
4219
4220                 // If there were no matching characters, skip over the loop altogether.
4221                 //   The loop doesn't run at all, a * op always succeeds.
4222                 if (ix == fp->fInputIdx) {
4223                     fp->fPatIdx++;   // skip the URX_LOOP_C op.
4224                     break;
4225                 }
4226
4227                 // Peek ahead in the compiled pattern, to the URX_LOOP_C that
4228                 //   must follow.  It's operand is the stack location
4229                 //   that holds the starting input index for the match of this .*
4230                 int32_t loopcOp = (int32_t)pat[fp->fPatIdx];
4231                 U_ASSERT(URX_TYPE(loopcOp) == URX_LOOP_C);
4232                 int32_t stackLoc = URX_VAL(loopcOp);
4233                 U_ASSERT(stackLoc >= 0 && stackLoc < fFrameSize);
4234                 fp->fExtra[stackLoc] = fp->fInputIdx;
4235                 fp->fInputIdx = ix;
4236
4237                 // Save State to the URX_LOOP_C op that follows this one,
4238                 //   so that match failures in the following code will return to there.
4239                 //   Then bump the pattern idx so the LOOP_C is skipped on the way out of here.
4240                 fp = StateSave(fp, fp->fPatIdx, status);
4241                 fp->fPatIdx++;
4242             }
4243             break;
4244
4245
4246         case URX_LOOP_C:
4247             {
4248                 U_ASSERT(opValue>=0 && opValue<fFrameSize);
4249                 backSearchIndex = fp->fExtra[opValue];
4250                 U_ASSERT(backSearchIndex <= fp->fInputIdx);
4251                 if (backSearchIndex == fp->fInputIdx) {
4252                     // We've backed up the input idx to the point that the loop started.
4253                     // The loop is done.  Leave here without saving state.
4254                     //  Subsequent failures won't come back here.
4255                     break;
4256                 }
4257                 // Set up for the next iteration of the loop, with input index
4258                 //   backed up by one from the last time through,
4259                 //   and a state save to this instruction in case the following code fails again.
4260                 //   (We're going backwards because this loop emulates stack unwinding, not
4261                 //    the initial scan forward.)
4262                 U_ASSERT(fp->fInputIdx > 0);
4263                 UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
4264                 UChar32 prevC = UTEXT_PREVIOUS32(fInputText);
4265                 fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
4266
4267                 UChar32 twoPrevC = UTEXT_PREVIOUS32(fInputText);
4268                 if (prevC == 0x0a &&
4269                     fp->fInputIdx > backSearchIndex &&
4270                     twoPrevC == 0x0d) {
4271                     int32_t prevOp = (int32_t)pat[fp->fPatIdx-2];
4272                     if (URX_TYPE(prevOp) == URX_LOOP_DOT_I) {
4273                         // .*, stepping back over CRLF pair.
4274                         fp->fInputIdx = UTEXT_GETNATIVEINDEX(fInputText);
4275                     }
4276                 }
4277
4278
4279                 fp = StateSave(fp, fp->fPatIdx-1, status);
4280             }
4281             break;
4282
4283
4284
4285         default:
4286             // Trouble.  The compiled pattern contains an entry with an
4287             //           unrecognized type tag.
4288             UPRV_UNREACHABLE;
4289         }
4290
4291         if (U_FAILURE(status)) {
4292             isMatch = FALSE;
4293             break;
4294         }
4295     }
4296
4297 breakFromLoop:
4298     fMatch = isMatch;
4299     if (isMatch) {
4300         fLastMatchEnd = fMatchEnd;
4301         fMatchStart   = startIdx;
4302         fMatchEnd     = fp->fInputIdx;
4303     }
4304
4305 #ifdef REGEX_RUN_DEBUG
4306     if (fTraceDebug) {
4307         if (isMatch) {
4308             printf("Match.  start=%ld   end=%ld\n\n", fMatchStart, fMatchEnd);
4309         } else {
4310             printf("No match\n\n");
4311         }
4312     }
4313 #endif
4314
4315     fFrame = fp;                // The active stack frame when the engine stopped.
4316                                 //   Contains the capture group results that we need to
4317                                 //    access later.
4318     return;
4319 }
4320
4321
4322 //--------------------------------------------------------------------------------
4323 //
4324 //   MatchChunkAt   This is the actual matching engine. Like MatchAt, but with the
4325 //                  assumption that the entire string is available in the UText's
4326 //                  chunk buffer. For now, that means we can use int32_t indexes,
4327 //                  except for anything that needs to be saved (like group starts
4328 //                  and ends).
4329 //
4330 //                  startIdx:    begin matching a this index.
4331 //                  toEnd:       if true, match must extend to end of the input region
4332 //
4333 //--------------------------------------------------------------------------------
4334 void RegexMatcher::MatchChunkAt(int32_t startIdx, UBool toEnd, UErrorCode &status) {
4335     UBool       isMatch  = FALSE;      // True if the we have a match.
4336
4337     int32_t     backSearchIndex = INT32_MAX; // used after greedy single-character matches for searching backwards
4338
4339     int32_t     op;                    // Operation from the compiled pattern, split into
4340     int32_t     opType;                //    the opcode
4341     int32_t     opValue;               //    and the operand value.
4342
4343 #ifdef REGEX_RUN_DEBUG
4344     if (fTraceDebug) {
4345         printf("MatchAt(startIdx=%d)\n", startIdx);
4346         printf("Original Pattern: \"%s\"\n", CStr(StringFromUText(fPattern->fPattern))());
4347         printf("Input String:     \"%s\"\n\n", CStr(StringFromUText(fInputText))());
4348     }
4349 #endif
4350
4351     if (U_FAILURE(status)) {
4352         return;
4353     }
4354
4355     //  Cache frequently referenced items from the compiled pattern
4356     //
4357     int64_t             *pat           = fPattern->fCompiledPat->getBuffer();
4358
4359     const UChar         *litText       = fPattern->fLiteralText.getBuffer();
4360     UVector             *fSets         = fPattern->fSets;
4361
4362     const UChar         *inputBuf      = fInputText->chunkContents;
4363
4364     fFrameSize = fPattern->fFrameSize;
4365     REStackFrame        *fp            = resetStack();
4366     if (U_FAILURE(fDeferredStatus)) {
4367         status = fDeferredStatus;
4368         return;
4369     }
4370
4371     fp->fPatIdx   = 0;
4372     fp->fInputIdx = startIdx;
4373
4374     // Zero out the pattern's static data
4375     int32_t i;
4376     for (i = 0; i<fPattern->fDataSize; i++) {
4377         fData[i] = 0;
4378     }
4379
4380     //
4381     //  Main loop for interpreting the compiled pattern.
4382     //  One iteration of the loop per pattern operation performed.
4383     //
4384     for (;;) {
4385         op      = (int32_t)pat[fp->fPatIdx];
4386         opType  = URX_TYPE(op);
4387         opValue = URX_VAL(op);
4388 #ifdef REGEX_RUN_DEBUG
4389         if (fTraceDebug) {
4390             UTEXT_SETNATIVEINDEX(fInputText, fp->fInputIdx);
4391             printf("inputIdx=%ld   inputChar=%x   sp=%3ld   activeLimit=%ld  ", fp->fInputIdx,
4392                    UTEXT_CURRENT32(fInputText), (int64_t *)fp-fStack->getBuffer(), fActiveLimit);
4393             fPattern->dumpOp(fp->fPatIdx);
4394         }
4395 #endif
4396         fp->fPatIdx++;
4397
4398         switch (opType) {
4399
4400
4401         case URX_NOP:
4402             break;
4403
4404
4405         case URX_BACKTRACK:
4406             // Force a backtrack.  In some circumstances, the pattern compiler
4407             //   will notice that the pattern can't possibly match anything, and will
4408             //   emit one of these at that point.
4409             fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4410             break;
4411
4412
4413         case URX_ONECHAR:
4414             if (fp->fInputIdx < fActiveLimit) {
4415                 UChar32 c;
4416                 U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
4417                 if (c == opValue) {
4418                     break;
4419                 }
4420             } else {
4421                 fHitEnd = TRUE;
4422             }
4423             fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4424             break;
4425
4426
4427         case URX_STRING:
4428             {
4429                 // Test input against a literal string.
4430                 // Strings require two slots in the compiled pattern, one for the
4431                 //   offset to the string text, and one for the length.
4432                 int32_t   stringStartIdx = opValue;
4433                 int32_t   stringLen;
4434
4435                 op      = (int32_t)pat[fp->fPatIdx];     // Fetch the second operand
4436                 fp->fPatIdx++;
4437                 opType    = URX_TYPE(op);
4438                 stringLen = URX_VAL(op);
4439                 U_ASSERT(opType == URX_STRING_LEN);
4440                 U_ASSERT(stringLen >= 2);
4441
4442                 const UChar * pInp = inputBuf + fp->fInputIdx;
4443                 const UChar * pInpLimit = inputBuf + fActiveLimit;
4444                 const UChar * pPat = litText+stringStartIdx;
4445                 const UChar * pEnd = pInp + stringLen;
4446                 UBool success = TRUE;
4447                 while (pInp < pEnd) {
4448                     if (pInp >= pInpLimit) {
4449                         fHitEnd = TRUE;
4450                         success = FALSE;
4451                         break;
4452                     }
4453                     if (*pInp++ != *pPat++) {
4454                         success = FALSE;
4455                         break;
4456                     }
4457                 }
4458
4459                 if (success) {
4460                     fp->fInputIdx += stringLen;
4461                 } else {
4462                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4463                 }
4464             }
4465             break;
4466
4467
4468         case URX_STATE_SAVE:
4469             fp = StateSave(fp, opValue, status);
4470             break;
4471
4472
4473         case URX_END:
4474             // The match loop will exit via this path on a successful match,
4475             //   when we reach the end of the pattern.
4476             if (toEnd && fp->fInputIdx != fActiveLimit) {
4477                 // The pattern matched, but not to the end of input.  Try some more.
4478                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4479                 break;
4480             }
4481             isMatch = TRUE;
4482             goto  breakFromLoop;
4483
4484             // Start and End Capture stack frame variables are laid out out like this:
4485             //  fp->fExtra[opValue]  - The start of a completed capture group
4486             //             opValue+1 - The end   of a completed capture group
4487             //             opValue+2 - the start of a capture group whose end
4488             //                          has not yet been reached (and might not ever be).
4489         case URX_START_CAPTURE:
4490             U_ASSERT(opValue >= 0 && opValue < fFrameSize-3);
4491             fp->fExtra[opValue+2] = fp->fInputIdx;
4492             break;
4493
4494
4495         case URX_END_CAPTURE:
4496             U_ASSERT(opValue >= 0 && opValue < fFrameSize-3);
4497             U_ASSERT(fp->fExtra[opValue+2] >= 0);            // Start pos for this group must be set.
4498             fp->fExtra[opValue]   = fp->fExtra[opValue+2];   // Tentative start becomes real.
4499             fp->fExtra[opValue+1] = fp->fInputIdx;           // End position
4500             U_ASSERT(fp->fExtra[opValue] <= fp->fExtra[opValue+1]);
4501             break;
4502
4503
4504         case URX_DOLLAR:                   //  $, test for End of line
4505             //     or for position before new line at end of input
4506             if (fp->fInputIdx < fAnchorLimit-2) {
4507                 // We are no where near the end of input.  Fail.
4508                 //   This is the common case.  Keep it first.
4509                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4510                 break;
4511             }
4512             if (fp->fInputIdx >= fAnchorLimit) {
4513                 // We really are at the end of input.  Success.
4514                 fHitEnd = TRUE;
4515                 fRequireEnd = TRUE;
4516                 break;
4517             }
4518
4519             // If we are positioned just before a new-line that is located at the
4520             //   end of input, succeed.
4521             if (fp->fInputIdx == fAnchorLimit-1) {
4522                 UChar32 c;
4523                 U16_GET(inputBuf, fAnchorStart, fp->fInputIdx, fAnchorLimit, c);
4524
4525                 if (isLineTerminator(c)) {
4526                     if ( !(c==0x0a && fp->fInputIdx>fAnchorStart && inputBuf[fp->fInputIdx-1]==0x0d)) {
4527                         // At new-line at end of input. Success
4528                         fHitEnd = TRUE;
4529                         fRequireEnd = TRUE;
4530                         break;
4531                     }
4532                 }
4533             } else if (fp->fInputIdx == fAnchorLimit-2 &&
4534                 inputBuf[fp->fInputIdx]==0x0d && inputBuf[fp->fInputIdx+1]==0x0a) {
4535                     fHitEnd = TRUE;
4536                     fRequireEnd = TRUE;
4537                     break;                         // At CR/LF at end of input.  Success
4538             }
4539
4540             fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4541
4542             break;
4543
4544
4545         case URX_DOLLAR_D:                   //  $, test for End of Line, in UNIX_LINES mode.
4546             if (fp->fInputIdx >= fAnchorLimit-1) {
4547                 // Either at the last character of input, or off the end.
4548                 if (fp->fInputIdx == fAnchorLimit-1) {
4549                     // At last char of input.  Success if it's a new line.
4550                     if (inputBuf[fp->fInputIdx] == 0x0a) {
4551                         fHitEnd = TRUE;
4552                         fRequireEnd = TRUE;
4553                         break;
4554                     }
4555                 } else {
4556                     // Off the end of input.  Success.
4557                     fHitEnd = TRUE;
4558                     fRequireEnd = TRUE;
4559                     break;
4560                 }
4561             }
4562
4563             // Not at end of input.  Back-track out.
4564             fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4565             break;
4566
4567
4568         case URX_DOLLAR_M:                //  $, test for End of line in multi-line mode
4569             {
4570                 if (fp->fInputIdx >= fAnchorLimit) {
4571                     // We really are at the end of input.  Success.
4572                     fHitEnd = TRUE;
4573                     fRequireEnd = TRUE;
4574                     break;
4575                 }
4576                 // If we are positioned just before a new-line, succeed.
4577                 // It makes no difference where the new-line is within the input.
4578                 UChar32 c = inputBuf[fp->fInputIdx];
4579                 if (isLineTerminator(c)) {
4580                     // At a line end, except for the odd chance of  being in the middle of a CR/LF sequence
4581                     //  In multi-line mode, hitting a new-line just before the end of input does not
4582                     //   set the hitEnd or requireEnd flags
4583                     if ( !(c==0x0a && fp->fInputIdx>fAnchorStart && inputBuf[fp->fInputIdx-1]==0x0d)) {
4584                         break;
4585                     }
4586                 }
4587                 // not at a new line.  Fail.
4588                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4589             }
4590             break;
4591
4592
4593         case URX_DOLLAR_MD:                //  $, test for End of line in multi-line and UNIX_LINES mode
4594             {
4595                 if (fp->fInputIdx >= fAnchorLimit) {
4596                     // We really are at the end of input.  Success.
4597                     fHitEnd = TRUE;
4598                     fRequireEnd = TRUE;  // Java set requireEnd in this case, even though
4599                     break;               //   adding a new-line would not lose the match.
4600                 }
4601                 // If we are not positioned just before a new-line, the test fails; backtrack out.
4602                 // It makes no difference where the new-line is within the input.
4603                 if (inputBuf[fp->fInputIdx] != 0x0a) {
4604                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4605                 }
4606             }
4607             break;
4608
4609
4610         case URX_CARET:                    //  ^, test for start of line
4611             if (fp->fInputIdx != fAnchorStart) {
4612                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4613             }
4614             break;
4615
4616
4617         case URX_CARET_M:                   //  ^, test for start of line in mulit-line mode
4618             {
4619                 if (fp->fInputIdx == fAnchorStart) {
4620                     // We are at the start input.  Success.
4621                     break;
4622                 }
4623                 // Check whether character just before the current pos is a new-line
4624                 //   unless we are at the end of input
4625                 UChar  c = inputBuf[fp->fInputIdx - 1];
4626                 if ((fp->fInputIdx < fAnchorLimit) &&
4627                     isLineTerminator(c)) {
4628                     //  It's a new-line.  ^ is true.  Success.
4629                     //  TODO:  what should be done with positions between a CR and LF?
4630                     break;
4631                 }
4632                 // Not at the start of a line.  Fail.
4633                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4634             }
4635             break;
4636
4637
4638         case URX_CARET_M_UNIX:       //  ^, test for start of line in mulit-line + Unix-line mode
4639             {
4640                 U_ASSERT(fp->fInputIdx >= fAnchorStart);
4641                 if (fp->fInputIdx <= fAnchorStart) {
4642                     // We are at the start input.  Success.
4643                     break;
4644                 }
4645                 // Check whether character just before the current pos is a new-line
4646                 U_ASSERT(fp->fInputIdx <= fAnchorLimit);
4647                 UChar  c = inputBuf[fp->fInputIdx - 1];
4648                 if (c != 0x0a) {
4649                     // Not at the start of a line.  Back-track out.
4650                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4651                 }
4652             }
4653             break;
4654
4655         case URX_BACKSLASH_B:          // Test for word boundaries
4656             {
4657                 UBool success = isChunkWordBoundary((int32_t)fp->fInputIdx);
4658                 success ^= (UBool)(opValue != 0);     // flip sense for \B
4659                 if (!success) {
4660                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4661                 }
4662             }
4663             break;
4664
4665
4666         case URX_BACKSLASH_BU:          // Test for word boundaries, Unicode-style
4667             {
4668                 UBool success = isUWordBoundary(fp->fInputIdx);
4669                 success ^= (UBool)(opValue != 0);     // flip sense for \B
4670                 if (!success) {
4671                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4672                 }
4673             }
4674             break;
4675
4676
4677         case URX_BACKSLASH_D:            // Test for decimal digit
4678             {
4679                 if (fp->fInputIdx >= fActiveLimit) {
4680                     fHitEnd = TRUE;
4681                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4682                     break;
4683                 }
4684
4685                 UChar32 c;
4686                 U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
4687                 int8_t ctype = u_charType(c);     // TODO:  make a unicode set for this.  Will be faster.
4688                 UBool success = (ctype == U_DECIMAL_DIGIT_NUMBER);
4689                 success ^= (UBool)(opValue != 0);        // flip sense for \D
4690                 if (!success) {
4691                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4692                 }
4693             }
4694             break;
4695
4696
4697         case URX_BACKSLASH_G:          // Test for position at end of previous match
4698             if (!((fMatch && fp->fInputIdx==fMatchEnd) || (fMatch==FALSE && fp->fInputIdx==fActiveStart))) {
4699                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4700             }
4701             break;
4702
4703
4704         case URX_BACKSLASH_H:            // Test for \h, horizontal white space.
4705             {
4706                 if (fp->fInputIdx >= fActiveLimit) {
4707                     fHitEnd = TRUE;
4708                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4709                     break;
4710                 }
4711                 UChar32 c;
4712                 U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
4713                 int8_t ctype = u_charType(c);
4714                 UBool success = (ctype == U_SPACE_SEPARATOR || c == 9);  // SPACE_SEPARATOR || TAB
4715                 success ^= (UBool)(opValue != 0);        // flip sense for \H
4716                 if (!success) {
4717                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4718                 }
4719             }
4720             break;
4721
4722
4723         case URX_BACKSLASH_R:            // Test for \R, any line break sequence.
4724             {
4725                 if (fp->fInputIdx >= fActiveLimit) {
4726                     fHitEnd = TRUE;
4727                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4728                     break;
4729                 }
4730                 UChar32 c;
4731                 U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
4732                 if (isLineTerminator(c)) {
4733                     if (c == 0x0d && fp->fInputIdx < fActiveLimit) {
4734                         // Check for CR/LF sequence. Consume both together when found.
4735                         UChar c2;
4736                         U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c2);
4737                         if (c2 != 0x0a) {
4738                             U16_PREV(inputBuf, 0, fp->fInputIdx, c2);
4739                         }
4740                     }
4741                 } else {
4742                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4743                 }
4744             }
4745             break;
4746
4747
4748         case URX_BACKSLASH_V:         // Any single code point line ending.
4749             {
4750                 if (fp->fInputIdx >= fActiveLimit) {
4751                     fHitEnd = TRUE;
4752                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4753                     break;
4754                 }
4755                 UChar32 c;
4756                 U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
4757                 UBool success = isLineTerminator(c);
4758                 success ^= (UBool)(opValue != 0);        // flip sense for \V
4759                 if (!success) {
4760                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4761                 }
4762             }
4763             break;
4764
4765
4766
4767         case URX_BACKSLASH_X:
4768         //  Match a Grapheme, as defined by Unicode TR 29.
4769         //  Differs slightly from Perl, which consumes combining marks independently
4770         //    of context.
4771         {
4772
4773             // Fail if at end of input
4774             if (fp->fInputIdx >= fActiveLimit) {
4775                 fHitEnd = TRUE;
4776                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4777                 break;
4778             }
4779
4780             // Examine (and consume) the current char.
4781             //   Dispatch into a little state machine, based on the char.
4782             UChar32  c;
4783             U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
4784             UnicodeSet **sets = fPattern->fStaticSets;
4785             if (sets[URX_GC_NORMAL]->contains(c))  goto GC_Extend;
4786             if (sets[URX_GC_CONTROL]->contains(c)) goto GC_Control;
4787             if (sets[URX_GC_L]->contains(c))       goto GC_L;
4788             if (sets[URX_GC_LV]->contains(c))      goto GC_V;
4789             if (sets[URX_GC_LVT]->contains(c))     goto GC_T;
4790             if (sets[URX_GC_V]->contains(c))       goto GC_V;
4791             if (sets[URX_GC_T]->contains(c))       goto GC_T;
4792             goto GC_Extend;
4793
4794
4795
4796 GC_L:
4797             if (fp->fInputIdx >= fActiveLimit)         goto GC_Done;
4798             U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
4799             if (sets[URX_GC_L]->contains(c))       goto GC_L;
4800             if (sets[URX_GC_LV]->contains(c))      goto GC_V;
4801             if (sets[URX_GC_LVT]->contains(c))     goto GC_T;
4802             if (sets[URX_GC_V]->contains(c))       goto GC_V;
4803             U16_PREV(inputBuf, 0, fp->fInputIdx, c);
4804             goto GC_Extend;
4805
4806 GC_V:
4807             if (fp->fInputIdx >= fActiveLimit)         goto GC_Done;
4808             U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
4809             if (sets[URX_GC_V]->contains(c))       goto GC_V;
4810             if (sets[URX_GC_T]->contains(c))       goto GC_T;
4811             U16_PREV(inputBuf, 0, fp->fInputIdx, c);
4812             goto GC_Extend;
4813
4814 GC_T:
4815             if (fp->fInputIdx >= fActiveLimit)         goto GC_Done;
4816             U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
4817             if (sets[URX_GC_T]->contains(c))       goto GC_T;
4818             U16_PREV(inputBuf, 0, fp->fInputIdx, c);
4819             goto GC_Extend;
4820
4821 GC_Extend:
4822             // Combining characters are consumed here
4823             for (;;) {
4824                 if (fp->fInputIdx >= fActiveLimit) {
4825                     break;
4826                 }
4827                 U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
4828                 if (sets[URX_GC_EXTEND]->contains(c) == FALSE) {
4829                     U16_BACK_1(inputBuf, 0, fp->fInputIdx);
4830                     break;
4831                 }
4832             }
4833             goto GC_Done;
4834
4835 GC_Control:
4836             // Most control chars stand alone (don't combine with combining chars),
4837             //   except for that CR/LF sequence is a single grapheme cluster.
4838             if (c == 0x0d && fp->fInputIdx < fActiveLimit && inputBuf[fp->fInputIdx] == 0x0a) {
4839                 fp->fInputIdx++;
4840             }
4841
4842 GC_Done:
4843             if (fp->fInputIdx >= fActiveLimit) {
4844                 fHitEnd = TRUE;
4845             }
4846             break;
4847         }
4848
4849
4850
4851
4852         case URX_BACKSLASH_Z:          // Test for end of Input
4853             if (fp->fInputIdx < fAnchorLimit) {
4854                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4855             } else {
4856                 fHitEnd = TRUE;
4857                 fRequireEnd = TRUE;
4858             }
4859             break;
4860
4861
4862
4863         case URX_STATIC_SETREF:
4864             {
4865                 // Test input character against one of the predefined sets
4866                 //    (Word Characters, for example)
4867                 // The high bit of the op value is a flag for the match polarity.
4868                 //    0:   success if input char is in set.
4869                 //    1:   success if input char is not in set.
4870                 if (fp->fInputIdx >= fActiveLimit) {
4871                     fHitEnd = TRUE;
4872                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4873                     break;
4874                 }
4875
4876                 UBool success = ((opValue & URX_NEG_SET) == URX_NEG_SET);
4877                 opValue &= ~URX_NEG_SET;
4878                 U_ASSERT(opValue > 0 && opValue < URX_LAST_SET);
4879
4880                 UChar32 c;
4881                 U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
4882                 if (c < 256) {
4883                     Regex8BitSet *s8 = &fPattern->fStaticSets8[opValue];
4884                     if (s8->contains(c)) {
4885                         success = !success;
4886                     }
4887                 } else {
4888                     const UnicodeSet *s = fPattern->fStaticSets[opValue];
4889                     if (s->contains(c)) {
4890                         success = !success;
4891                     }
4892                 }
4893                 if (!success) {
4894                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4895                 }
4896             }
4897             break;
4898
4899
4900         case URX_STAT_SETREF_N:
4901             {
4902                 // Test input character for NOT being a member of  one of
4903                 //    the predefined sets (Word Characters, for example)
4904                 if (fp->fInputIdx >= fActiveLimit) {
4905                     fHitEnd = TRUE;
4906                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4907                     break;
4908                 }
4909
4910                 U_ASSERT(opValue > 0 && opValue < URX_LAST_SET);
4911
4912                 UChar32  c;
4913                 U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
4914                 if (c < 256) {
4915                     Regex8BitSet *s8 = &fPattern->fStaticSets8[opValue];
4916                     if (s8->contains(c) == FALSE) {
4917                         break;
4918                     }
4919                 } else {
4920                     const UnicodeSet *s = fPattern->fStaticSets[opValue];
4921                     if (s->contains(c) == FALSE) {
4922                         break;
4923                     }
4924                 }
4925                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4926             }
4927             break;
4928
4929
4930         case URX_SETREF:
4931             {
4932                 if (fp->fInputIdx >= fActiveLimit) {
4933                     fHitEnd = TRUE;
4934                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4935                     break;
4936                 }
4937
4938                 U_ASSERT(opValue > 0 && opValue < fSets->size());
4939
4940                 // There is input left.  Pick up one char and test it for set membership.
4941                 UChar32  c;
4942                 U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
4943                 if (c<256) {
4944                     Regex8BitSet *s8 = &fPattern->fSets8[opValue];
4945                     if (s8->contains(c)) {
4946                         // The character is in the set.  A Match.
4947                         break;
4948                     }
4949                 } else {
4950                     UnicodeSet *s = (UnicodeSet *)fSets->elementAt(opValue);
4951                     if (s->contains(c)) {
4952                         // The character is in the set.  A Match.
4953                         break;
4954                     }
4955                 }
4956
4957                 // the character wasn't in the set.
4958                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4959             }
4960             break;
4961
4962
4963         case URX_DOTANY:
4964             {
4965                 // . matches anything, but stops at end-of-line.
4966                 if (fp->fInputIdx >= fActiveLimit) {
4967                     // At end of input.  Match failed.  Backtrack out.
4968                     fHitEnd = TRUE;
4969                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4970                     break;
4971                 }
4972
4973                 // There is input left.  Advance over one char, unless we've hit end-of-line
4974                 UChar32  c;
4975                 U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
4976                 if (isLineTerminator(c)) {
4977                     // End of line in normal mode.   . does not match.
4978                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4979                     break;
4980                 }
4981             }
4982             break;
4983
4984
4985         case URX_DOTANY_ALL:
4986             {
4987                 // . in dot-matches-all (including new lines) mode
4988                 if (fp->fInputIdx >= fActiveLimit) {
4989                     // At end of input.  Match failed.  Backtrack out.
4990                     fHitEnd = TRUE;
4991                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
4992                     break;
4993                 }
4994
4995                 // There is input left.  Advance over one char, except if we are
4996                 //   at a cr/lf, advance over both of them.
4997                 UChar32 c;
4998                 U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
4999                 if (c==0x0d && fp->fInputIdx < fActiveLimit) {
5000                     // In the case of a CR/LF, we need to advance over both.
5001                     if (inputBuf[fp->fInputIdx] == 0x0a) {
5002                         U16_FWD_1(inputBuf, fp->fInputIdx, fActiveLimit);
5003                     }
5004                 }
5005             }
5006             break;
5007
5008
5009         case URX_DOTANY_UNIX:
5010             {
5011                 // '.' operator, matches all, but stops at end-of-line.
5012                 //   UNIX_LINES mode, so 0x0a is the only recognized line ending.
5013                 if (fp->fInputIdx >= fActiveLimit) {
5014                     // At end of input.  Match failed.  Backtrack out.
5015                     fHitEnd = TRUE;
5016                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
5017                     break;
5018                 }
5019
5020                 // There is input left.  Advance over one char, unless we've hit end-of-line
5021                 UChar32 c;
5022                 U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
5023                 if (c == 0x0a) {
5024                     // End of line in normal mode.   '.' does not match the \n
5025                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
5026                 }
5027             }
5028             break;
5029
5030
5031         case URX_JMP:
5032             fp->fPatIdx = opValue;
5033             break;
5034
5035         case URX_FAIL:
5036             isMatch = FALSE;
5037             goto breakFromLoop;
5038
5039         case URX_JMP_SAV:
5040             U_ASSERT(opValue < fPattern->fCompiledPat->size());
5041             fp = StateSave(fp, fp->fPatIdx, status);       // State save to loc following current
5042             fp->fPatIdx = opValue;                         // Then JMP.
5043             break;
5044
5045         case URX_JMP_SAV_X:
5046             // This opcode is used with (x)+, when x can match a zero length string.
5047             // Same as JMP_SAV, except conditional on the match having made forward progress.
5048             // Destination of the JMP must be a URX_STO_INP_LOC, from which we get the
5049             //   data address of the input position at the start of the loop.
5050             {
5051                 U_ASSERT(opValue > 0 && opValue < fPattern->fCompiledPat->size());
5052                 int32_t  stoOp = (int32_t)pat[opValue-1];
5053                 U_ASSERT(URX_TYPE(stoOp) == URX_STO_INP_LOC);
5054                 int32_t  frameLoc = URX_VAL(stoOp);
5055                 U_ASSERT(frameLoc >= 0 && frameLoc < fFrameSize);
5056                 int32_t prevInputIdx = (int32_t)fp->fExtra[frameLoc];
5057                 U_ASSERT(prevInputIdx <= fp->fInputIdx);
5058                 if (prevInputIdx < fp->fInputIdx) {
5059                     // The match did make progress.  Repeat the loop.
5060                     fp = StateSave(fp, fp->fPatIdx, status);  // State save to loc following current
5061                     fp->fPatIdx = opValue;
5062                     fp->fExtra[frameLoc] = fp->fInputIdx;
5063                 }
5064                 // If the input position did not advance, we do nothing here,
5065                 //   execution will fall out of the loop.
5066             }
5067             break;
5068
5069         case URX_CTR_INIT:
5070             {
5071                 U_ASSERT(opValue >= 0 && opValue < fFrameSize-2);
5072                 fp->fExtra[opValue] = 0;                 //  Set the loop counter variable to zero
5073
5074                 // Pick up the three extra operands that CTR_INIT has, and
5075                 //    skip the pattern location counter past
5076                 int32_t instrOperandLoc = (int32_t)fp->fPatIdx;
5077                 fp->fPatIdx += 3;
5078                 int32_t loopLoc  = URX_VAL(pat[instrOperandLoc]);
5079                 int32_t minCount = (int32_t)pat[instrOperandLoc+1];
5080                 int32_t maxCount = (int32_t)pat[instrOperandLoc+2];
5081                 U_ASSERT(minCount>=0);
5082                 U_ASSERT(maxCount>=minCount || maxCount==-1);
5083                 U_ASSERT(loopLoc>=fp->fPatIdx);
5084
5085                 if (minCount == 0) {
5086                     fp = StateSave(fp, loopLoc+1, status);
5087                 }
5088                 if (maxCount == -1) {
5089                     fp->fExtra[opValue+1] = fp->fInputIdx;   //  For loop breaking.
5090                 } else if (maxCount == 0) {
5091                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
5092                 }
5093             }
5094             break;
5095
5096         case URX_CTR_LOOP:
5097             {
5098                 U_ASSERT(opValue>0 && opValue < fp->fPatIdx-2);
5099                 int32_t initOp = (int32_t)pat[opValue];
5100                 U_ASSERT(URX_TYPE(initOp) == URX_CTR_INIT);
5101                 int64_t *pCounter = &fp->fExtra[URX_VAL(initOp)];
5102                 int32_t minCount  = (int32_t)pat[opValue+2];
5103                 int32_t maxCount  = (int32_t)pat[opValue+3];
5104                 (*pCounter)++;
5105                 if ((uint64_t)*pCounter >= (uint32_t)maxCount && maxCount != -1) {
5106                     U_ASSERT(*pCounter == maxCount);
5107                     break;
5108                 }
5109                 if (*pCounter >= minCount) {
5110                     if (maxCount == -1) {
5111                         // Loop has no hard upper bound.
5112                         // Check that it is progressing through the input, break if it is not.
5113                         int64_t *pLastInputIdx =  &fp->fExtra[URX_VAL(initOp) + 1];
5114                         if (fp->fInputIdx == *pLastInputIdx) {
5115                             break;
5116                         } else {
5117                             *pLastInputIdx = fp->fInputIdx;
5118                         }
5119                     }
5120                     fp = StateSave(fp, fp->fPatIdx, status);
5121                 } else {
5122                     // Increment time-out counter. (StateSave() does it if count >= minCount)
5123                     fTickCounter--;
5124                     if (fTickCounter <= 0) {
5125                         IncrementTime(status);    // Re-initializes fTickCounter
5126                     }
5127                 }
5128                 fp->fPatIdx = opValue + 4;    // Loop back.
5129             }
5130             break;
5131
5132         case URX_CTR_INIT_NG:
5133             {
5134                 // Initialize a non-greedy loop
5135                 U_ASSERT(opValue >= 0 && opValue < fFrameSize-2);
5136                 fp->fExtra[opValue] = 0;                 //  Set the loop counter variable to zero
5137
5138                 // Pick up the three extra operands that CTR_INIT_NG has, and
5139                 //    skip the pattern location counter past
5140                 int32_t instrOperandLoc = (int32_t)fp->fPatIdx;
5141                 fp->fPatIdx += 3;
5142                 int32_t loopLoc  = URX_VAL(pat[instrOperandLoc]);
5143                 int32_t minCount = (int32_t)pat[instrOperandLoc+1];
5144                 int32_t maxCount = (int32_t)pat[instrOperandLoc+2];
5145                 U_ASSERT(minCount>=0);
5146                 U_ASSERT(maxCount>=minCount || maxCount==-1);
5147                 U_ASSERT(loopLoc>fp->fPatIdx);
5148                 if (maxCount == -1) {
5149                     fp->fExtra[opValue+1] = fp->fInputIdx;   //  Save initial input index for loop breaking.
5150                 }
5151
5152                 if (minCount == 0) {
5153                     if (maxCount != 0) {
5154                         fp = StateSave(fp, fp->fPatIdx, status);
5155                     }
5156                     fp->fPatIdx = loopLoc+1;   // Continue with stuff after repeated block
5157                 }
5158             }
5159             break;
5160
5161         case URX_CTR_LOOP_NG:
5162             {
5163                 // Non-greedy {min, max} loops
5164                 U_ASSERT(opValue>0 && opValue < fp->fPatIdx-2);
5165                 int32_t initOp = (int32_t)pat[opValue];
5166                 U_ASSERT(URX_TYPE(initOp) == URX_CTR_INIT_NG);
5167                 int64_t *pCounter = &fp->fExtra[URX_VAL(initOp)];
5168                 int32_t minCount  = (int32_t)pat[opValue+2];
5169                 int32_t maxCount  = (int32_t)pat[opValue+3];
5170
5171                 (*pCounter)++;
5172                 if ((uint64_t)*pCounter >= (uint32_t)maxCount && maxCount != -1) {
5173                     // The loop has matched the maximum permitted number of times.
5174                     //   Break out of here with no action.  Matching will
5175                     //   continue with the following pattern.
5176                     U_ASSERT(*pCounter == maxCount);
5177                     break;
5178                 }
5179
5180                 if (*pCounter < minCount) {
5181                     // We haven't met the minimum number of matches yet.
5182                     //   Loop back for another one.
5183                     fp->fPatIdx = opValue + 4;    // Loop back.
5184                     fTickCounter--;
5185                     if (fTickCounter <= 0) {
5186                         IncrementTime(status);    // Re-initializes fTickCounter
5187                     }
5188                 } else {
5189                     // We do have the minimum number of matches.
5190
5191                     // If there is no upper bound on the loop iterations, check that the input index
5192                     // is progressing, and stop the loop if it is not.
5193                     if (maxCount == -1) {
5194                         int64_t *pLastInputIdx =  &fp->fExtra[URX_VAL(initOp) + 1];
5195                         if (fp->fInputIdx == *pLastInputIdx) {
5196                             break;
5197                         }
5198                         *pLastInputIdx = fp->fInputIdx;
5199                     }
5200
5201                     // Loop Continuation: we will fall into the pattern following the loop
5202                     //   (non-greedy, don't execute loop body first), but first do
5203                     //   a state save to the top of the loop, so that a match failure
5204                     //   in the following pattern will try another iteration of the loop.
5205                     fp = StateSave(fp, opValue + 4, status);
5206                 }
5207             }
5208             break;
5209
5210         case URX_STO_SP:
5211             U_ASSERT(opValue >= 0 && opValue < fPattern->fDataSize);
5212             fData[opValue] = fStack->size();
5213             break;
5214
5215         case URX_LD_SP:
5216             {
5217                 U_ASSERT(opValue >= 0 && opValue < fPattern->fDataSize);
5218                 int32_t newStackSize = (int32_t)fData[opValue];
5219                 U_ASSERT(newStackSize <= fStack->size());
5220                 int64_t *newFP = fStack->getBuffer() + newStackSize - fFrameSize;
5221                 if (newFP == (int64_t *)fp) {
5222                     break;
5223                 }
5224                 int32_t j;
5225                 for (j=0; j<fFrameSize; j++) {
5226                     newFP[j] = ((int64_t *)fp)[j];
5227                 }
5228                 fp = (REStackFrame *)newFP;
5229                 fStack->setSize(newStackSize);
5230             }
5231             break;
5232
5233         case URX_BACKREF:
5234             {
5235                 U_ASSERT(opValue < fFrameSize);
5236                 int64_t groupStartIdx = fp->fExtra[opValue];
5237                 int64_t groupEndIdx   = fp->fExtra[opValue+1];
5238                 U_ASSERT(groupStartIdx <= groupEndIdx);
5239                 int64_t inputIndex = fp->fInputIdx;
5240                 if (groupStartIdx < 0) {
5241                     // This capture group has not participated in the match thus far,
5242                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);   // FAIL, no match.
5243                     break;
5244                 }
5245                 UBool success = TRUE;
5246                 for (int64_t groupIndex = groupStartIdx; groupIndex < groupEndIdx; ++groupIndex,++inputIndex) {
5247                     if (inputIndex >= fActiveLimit) {
5248                         success = FALSE;
5249                         fHitEnd = TRUE;
5250                         break;
5251                     }
5252                     if (inputBuf[groupIndex] != inputBuf[inputIndex]) {
5253                         success = FALSE;
5254                         break;
5255                     }
5256                 }
5257                 if (success && groupStartIdx < groupEndIdx && U16_IS_LEAD(inputBuf[groupEndIdx-1]) &&
5258                         inputIndex < fActiveLimit && U16_IS_TRAIL(inputBuf[inputIndex])) {
5259                     // Capture group ended with an unpaired lead surrogate.
5260                     // Back reference is not permitted to match lead only of a surrogatge pair.
5261                     success = FALSE;
5262                 }
5263                 if (success) {
5264                     fp->fInputIdx = inputIndex;
5265                 } else {
5266                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
5267                 }
5268             }
5269             break;
5270
5271         case URX_BACKREF_I:
5272             {
5273                 U_ASSERT(opValue < fFrameSize);
5274                 int64_t groupStartIdx = fp->fExtra[opValue];
5275                 int64_t groupEndIdx   = fp->fExtra[opValue+1];
5276                 U_ASSERT(groupStartIdx <= groupEndIdx);
5277                 if (groupStartIdx < 0) {
5278                     // This capture group has not participated in the match thus far,
5279                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);   // FAIL, no match.
5280                     break;
5281                 }
5282                 CaseFoldingUCharIterator captureGroupItr(inputBuf, groupStartIdx, groupEndIdx);
5283                 CaseFoldingUCharIterator inputItr(inputBuf, fp->fInputIdx, fActiveLimit);
5284
5285                 //   Note: if the capture group match was of an empty string the backref
5286                 //         match succeeds.  Verified by testing:  Perl matches succeed
5287                 //         in this case, so we do too.
5288
5289                 UBool success = TRUE;
5290                 for (;;) {
5291                     UChar32 captureGroupChar = captureGroupItr.next();
5292                     if (captureGroupChar == U_SENTINEL) {
5293                         success = TRUE;
5294                         break;
5295                     }
5296                     UChar32 inputChar = inputItr.next();
5297                     if (inputChar == U_SENTINEL) {
5298                         success = FALSE;
5299                         fHitEnd = TRUE;
5300                         break;
5301                     }
5302                     if (inputChar != captureGroupChar) {
5303                         success = FALSE;
5304                         break;
5305                     }
5306                 }
5307
5308                 if (success && inputItr.inExpansion()) {
5309                     // We otained a match by consuming part of a string obtained from
5310                     // case-folding a single code point of the input text.
5311                     // This does not count as an overall match.
5312                     success = FALSE;
5313                 }
5314
5315                 if (success) {
5316                     fp->fInputIdx = inputItr.getIndex();
5317                 } else {
5318                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
5319                 }
5320             }
5321             break;
5322
5323         case URX_STO_INP_LOC:
5324             {
5325                 U_ASSERT(opValue >= 0 && opValue < fFrameSize);
5326                 fp->fExtra[opValue] = fp->fInputIdx;
5327             }
5328             break;
5329
5330         case URX_JMPX:
5331             {
5332                 int32_t instrOperandLoc = (int32_t)fp->fPatIdx;
5333                 fp->fPatIdx += 1;
5334                 int32_t dataLoc  = URX_VAL(pat[instrOperandLoc]);
5335                 U_ASSERT(dataLoc >= 0 && dataLoc < fFrameSize);
5336                 int32_t savedInputIdx = (int32_t)fp->fExtra[dataLoc];
5337                 U_ASSERT(savedInputIdx <= fp->fInputIdx);
5338                 if (savedInputIdx < fp->fInputIdx) {
5339                     fp->fPatIdx = opValue;                               // JMP
5340                 } else {
5341                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);   // FAIL, no progress in loop.
5342                 }
5343             }
5344             break;
5345
5346         case URX_LA_START:
5347             {
5348                 // Entering a lookahead block.
5349                 // Save Stack Ptr, Input Pos.
5350                 U_ASSERT(opValue>=0 && opValue+1<fPattern->fDataSize);
5351                 fData[opValue]   = fStack->size();
5352                 fData[opValue+1] = fp->fInputIdx;
5353                 fActiveStart     = fLookStart;          // Set the match region change for
5354                 fActiveLimit     = fLookLimit;          //   transparent bounds.
5355             }
5356             break;
5357
5358         case URX_LA_END:
5359             {
5360                 // Leaving a look-ahead block.
5361                 //  restore Stack Ptr, Input Pos to positions they had on entry to block.
5362                 U_ASSERT(opValue>=0 && opValue+1<fPattern->fDataSize);
5363                 int32_t stackSize = fStack->size();
5364                 int32_t newStackSize = (int32_t)fData[opValue];
5365                 U_ASSERT(stackSize >= newStackSize);
5366                 if (stackSize > newStackSize) {
5367                     // Copy the current top frame back to the new (cut back) top frame.
5368                     //   This makes the capture groups from within the look-ahead
5369                     //   expression available.
5370                     int64_t *newFP = fStack->getBuffer() + newStackSize - fFrameSize;
5371                     int32_t j;
5372                     for (j=0; j<fFrameSize; j++) {
5373                         newFP[j] = ((int64_t *)fp)[j];
5374                     }
5375                     fp = (REStackFrame *)newFP;
5376                     fStack->setSize(newStackSize);
5377                 }
5378                 fp->fInputIdx = fData[opValue+1];
5379
5380                 // Restore the active region bounds in the input string; they may have
5381                 //    been changed because of transparent bounds on a Region.
5382                 fActiveStart = fRegionStart;
5383                 fActiveLimit = fRegionLimit;
5384             }
5385             break;
5386
5387         case URX_ONECHAR_I:
5388             if (fp->fInputIdx < fActiveLimit) {
5389                 UChar32 c;
5390                 U16_NEXT(inputBuf, fp->fInputIdx, fActiveLimit, c);
5391                 if (u_foldCase(c, U_FOLD_CASE_DEFAULT) == opValue) {
5392                     break;
5393                 }
5394             } else {
5395                 fHitEnd = TRUE;
5396             }
5397             fp = (REStackFrame *)fStack->popFrame(fFrameSize);
5398             break;
5399
5400         case URX_STRING_I:
5401             // Case-insensitive test input against a literal string.
5402             // Strings require two slots in the compiled pattern, one for the
5403             //   offset to the string text, and one for the length.
5404             //   The compiled string has already been case folded.
5405             {
5406                 const UChar *patternString = litText + opValue;
5407
5408                 op      = (int32_t)pat[fp->fPatIdx];
5409                 fp->fPatIdx++;
5410                 opType  = URX_TYPE(op);
5411                 opValue = URX_VAL(op);
5412                 U_ASSERT(opType == URX_STRING_LEN);
5413                 int32_t patternStringLen = opValue;  // Length of the string from the pattern.
5414
5415                 UChar32      cText;
5416                 UChar32      cPattern;
5417                 UBool        success = TRUE;
5418                 int32_t      patternStringIdx  = 0;
5419                 CaseFoldingUCharIterator inputIterator(inputBuf, fp->fInputIdx, fActiveLimit);
5420                 while (patternStringIdx < patternStringLen) {
5421                     U16_NEXT(patternString, patternStringIdx, patternStringLen, cPattern);
5422                     cText = inputIterator.next();
5423                     if (cText != cPattern) {
5424                         success = FALSE;
5425                         if (cText == U_SENTINEL) {
5426                             fHitEnd = TRUE;
5427                         }
5428                         break;
5429                     }
5430                 }
5431                 if (inputIterator.inExpansion()) {
5432                     success = FALSE;
5433                 }
5434
5435                 if (success) {
5436                     fp->fInputIdx = inputIterator.getIndex();
5437                 } else {
5438                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
5439                 }
5440             }
5441             break;
5442
5443         case URX_LB_START:
5444             {
5445                 // Entering a look-behind block.
5446                 // Save Stack Ptr, Input Pos.
5447                 //   TODO:  implement transparent bounds.  Ticket #6067
5448                 U_ASSERT(opValue>=0 && opValue+1<fPattern->fDataSize);
5449                 fData[opValue]   = fStack->size();
5450                 fData[opValue+1] = fp->fInputIdx;
5451                 // Init the variable containing the start index for attempted matches.
5452                 fData[opValue+2] = -1;
5453                 // Save input string length, then reset to pin any matches to end at
5454                 //   the current position.
5455                 fData[opValue+3] = fActiveLimit;
5456                 fActiveLimit     = fp->fInputIdx;
5457             }
5458             break;
5459
5460
5461         case URX_LB_CONT:
5462             {
5463                 // Positive Look-Behind, at top of loop checking for matches of LB expression
5464                 //    at all possible input starting positions.
5465
5466                 // Fetch the min and max possible match lengths.  They are the operands
5467                 //   of this op in the pattern.
5468                 int32_t minML = (int32_t)pat[fp->fPatIdx++];
5469                 int32_t maxML = (int32_t)pat[fp->fPatIdx++];
5470                 U_ASSERT(minML <= maxML);
5471                 U_ASSERT(minML >= 0);
5472
5473                 // Fetch (from data) the last input index where a match was attempted.
5474                 U_ASSERT(opValue>=0 && opValue+1<fPattern->fDataSize);
5475                 int64_t  &lbStartIdx = fData[opValue+2];
5476                 if (lbStartIdx < 0) {
5477                     // First time through loop.
5478                     lbStartIdx = fp->fInputIdx - minML;
5479                     if (lbStartIdx > 0 && lbStartIdx < fInputLength) {
5480                         U16_SET_CP_START(inputBuf, 0, lbStartIdx);
5481                     }
5482                 } else {
5483                     // 2nd through nth time through the loop.
5484                     // Back up start position for match by one.
5485                     if (lbStartIdx == 0) {
5486                         lbStartIdx--;
5487                     } else {
5488                         U16_BACK_1(inputBuf, 0, lbStartIdx);
5489                     }
5490                 }
5491
5492                 if (lbStartIdx < 0 || lbStartIdx < fp->fInputIdx - maxML) {
5493                     // We have tried all potential match starting points without
5494                     //  getting a match.  Backtrack out, and out of the
5495                     //   Look Behind altogether.
5496                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
5497                     int64_t restoreInputLen = fData[opValue+3];
5498                     U_ASSERT(restoreInputLen >= fActiveLimit);
5499                     U_ASSERT(restoreInputLen <= fInputLength);
5500                     fActiveLimit = restoreInputLen;
5501                     break;
5502                 }
5503
5504                 //    Save state to this URX_LB_CONT op, so failure to match will repeat the loop.
5505                 //      (successful match will fall off the end of the loop.)
5506                 fp = StateSave(fp, fp->fPatIdx-3, status);
5507                 fp->fInputIdx =  lbStartIdx;
5508             }
5509             break;
5510
5511         case URX_LB_END:
5512             // End of a look-behind block, after a successful match.
5513             {
5514                 U_ASSERT(opValue>=0 && opValue+1<fPattern->fDataSize);
5515                 if (fp->fInputIdx != fActiveLimit) {
5516                     //  The look-behind expression matched, but the match did not
5517                     //    extend all the way to the point that we are looking behind from.
5518                     //  FAIL out of here, which will take us back to the LB_CONT, which
5519                     //     will retry the match starting at another position or fail
5520                     //     the look-behind altogether, whichever is appropriate.
5521                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
5522                     break;
5523                 }
5524
5525                 // Look-behind match is good.  Restore the orignal input string length,
5526                 //   which had been truncated to pin the end of the lookbehind match to the
5527                 //   position being looked-behind.
5528                 int64_t originalInputLen = fData[opValue+3];
5529                 U_ASSERT(originalInputLen >= fActiveLimit);
5530                 U_ASSERT(originalInputLen <= fInputLength);
5531                 fActiveLimit = originalInputLen;
5532             }
5533             break;
5534
5535
5536         case URX_LBN_CONT:
5537             {
5538                 // Negative Look-Behind, at top of loop checking for matches of LB expression
5539                 //    at all possible input starting positions.
5540
5541                 // Fetch the extra parameters of this op.
5542                 int32_t minML       = (int32_t)pat[fp->fPatIdx++];
5543                 int32_t maxML       = (int32_t)pat[fp->fPatIdx++];
5544                 int32_t continueLoc = (int32_t)pat[fp->fPatIdx++];
5545                 continueLoc = URX_VAL(continueLoc);
5546                 U_ASSERT(minML <= maxML);
5547                 U_ASSERT(minML >= 0);
5548                 U_ASSERT(continueLoc > fp->fPatIdx);
5549
5550                 // Fetch (from data) the last input index where a match was attempted.
5551                 U_ASSERT(opValue>=0 && opValue+1<fPattern->fDataSize);
5552                 int64_t  &lbStartIdx = fData[opValue+2];
5553                 if (lbStartIdx < 0) {
5554                     // First time through loop.
5555                     lbStartIdx = fp->fInputIdx - minML;
5556                     if (lbStartIdx > 0 && lbStartIdx < fInputLength) {
5557                         U16_SET_CP_START(inputBuf, 0, lbStartIdx);
5558                     }
5559                 } else {
5560                     // 2nd through nth time through the loop.
5561                     // Back up start position for match by one.
5562                     if (lbStartIdx == 0) {
5563                         lbStartIdx--;   // Because U16_BACK is unsafe starting at 0.
5564                     } else {
5565                         U16_BACK_1(inputBuf, 0, lbStartIdx);
5566                     }
5567                 }
5568
5569                 if (lbStartIdx < 0 || lbStartIdx < fp->fInputIdx - maxML) {
5570                     // We have tried all potential match starting points without
5571                     //  getting a match, which means that the negative lookbehind as
5572                     //  a whole has succeeded.  Jump forward to the continue location
5573                     int64_t restoreInputLen = fData[opValue+3];
5574                     U_ASSERT(restoreInputLen >= fActiveLimit);
5575                     U_ASSERT(restoreInputLen <= fInputLength);
5576                     fActiveLimit = restoreInputLen;
5577                     fp->fPatIdx = continueLoc;
5578                     break;
5579                 }
5580
5581                 //    Save state to this URX_LB_CONT op, so failure to match will repeat the loop.
5582                 //      (successful match will cause a FAIL out of the loop altogether.)
5583                 fp = StateSave(fp, fp->fPatIdx-4, status);
5584                 fp->fInputIdx =  lbStartIdx;
5585             }
5586             break;
5587
5588         case URX_LBN_END:
5589             // End of a negative look-behind block, after a successful match.
5590             {
5591                 U_ASSERT(opValue>=0 && opValue+1<fPattern->fDataSize);
5592                 if (fp->fInputIdx != fActiveLimit) {
5593                     //  The look-behind expression matched, but the match did not
5594                     //    extend all the way to the point that we are looking behind from.
5595                     //  FAIL out of here, which will take us back to the LB_CONT, which
5596                     //     will retry the match starting at another position or succeed
5597                     //     the look-behind altogether, whichever is appropriate.
5598                     fp = (REStackFrame *)fStack->popFrame(fFrameSize);
5599                     break;
5600                 }
5601
5602                 // Look-behind expression matched, which means look-behind test as
5603                 //   a whole Fails
5604
5605                 //   Restore the orignal input string length, which had been truncated
5606                 //   inorder to pin the end of the lookbehind match
5607                 //   to the position being looked-behind.
5608                 int64_t originalInputLen = fData[opValue+3];
5609                 U_ASSERT(originalInputLen >= fActiveLimit);
5610                 U_ASSERT(originalInputLen <= fInputLength);
5611                 fActiveLimit = originalInputLen;
5612
5613                 // Restore original stack position, discarding any state saved
5614                 //   by the successful pattern match.
5615                 U_ASSERT(opValue>=0 && opValue+1<fPattern->fDataSize);
5616                 int32_t newStackSize = (int32_t)fData[opValue];
5617                 U_ASSERT(fStack->size() > newStackSize);
5618                 fStack->setSize(newStackSize);
5619
5620                 //  FAIL, which will take control back to someplace
5621                 //  prior to entering the look-behind test.
5622                 fp = (REStackFrame *)fStack->popFrame(fFrameSize);
5623             }
5624             break;
5625
5626
5627         case URX_LOOP_SR_I:
5628             // Loop Initialization for the optimized implementation of
5629             //     [some character set]*
5630             //   This op scans through all matching input.
5631             //   The following LOOP_C op emulates stack unwinding if the following pattern fails.
5632             {
5633                 U_ASSERT(opValue > 0 && opValue < fSets->size());
5634                 Regex8BitSet *s8 = &fPattern->fSets8[opValue];
5635                 UnicodeSet   *s  = (UnicodeSet *)fSets->elementAt(opValue);
5636
5637                 // Loop through input, until either the input is exhausted or
5638                 //   we reach a character that is not a member of the set.
5639                 int32_t ix = (int32_t)fp->fInputIdx;
5640                 for (;;) {
5641                     if (ix >= fActiveLimit) {
5642                         fHitEnd = TRUE;
5643                         break;
5644                     }
5645                     UChar32   c;
5646                     U16_NEXT(inputBuf, ix, fActiveLimit, c);
5647                     if (c<256) {
5648                         if (s8->contains(c) == FALSE) {
5649                             U16_BACK_1(inputBuf, 0, ix);
5650                             break;
5651                         }
5652                     } else {
5653                         if (s->contains(c) == FALSE) {
5654                             U16_BACK_1(inputBuf, 0, ix);
5655                             break;
5656                         }
5657                     }
5658                 }
5659
5660                 // If there were no matching characters, skip over the loop altogether.
5661                 //   The loop doesn't run at all, a * op always succeeds.
5662                 if (ix == fp->fInputIdx) {
5663                     fp->fPatIdx++;   // skip the URX_LOOP_C op.
5664                     break;
5665                 }
5666
5667                 // Peek ahead in the compiled pattern, to the URX_LOOP_C that
5668                 //   must follow.  It's operand is the stack location
5669                 //   that holds the starting input index for the match of this [set]*
5670                 int32_t loopcOp = (int32_t)pat[fp->fPatIdx];
5671                 U_ASSERT(URX_TYPE(loopcOp) == URX_LOOP_C);
5672                 int32_t stackLoc = URX_VAL(loopcOp);
5673                 U_ASSERT(stackLoc >= 0 && stackLoc < fFrameSize);
5674                 fp->fExtra[stackLoc] = fp->fInputIdx;
5675                 fp->fInputIdx = ix;
5676
5677                 // Save State to the URX_LOOP_C op that follows this one,
5678                 //   so that match failures in the following code will return to there.
5679                 //   Then bump the pattern idx so the LOOP_C is skipped on the way out of here.
5680                 fp = StateSave(fp, fp->fPatIdx, status);
5681                 fp->fPatIdx++;
5682             }
5683             break;
5684
5685
5686         case URX_LOOP_DOT_I:
5687             // Loop Initialization for the optimized implementation of .*
5688             //   This op scans through all remaining input.
5689             //   The following LOOP_C op emulates stack unwinding if the following pattern fails.
5690             {
5691                 // Loop through input until the input is exhausted (we reach an end-of-line)
5692                 // In DOTALL mode, we can just go straight to the end of the input.
5693                 int32_t ix;
5694                 if ((opValue & 1) == 1) {
5695                     // Dot-matches-All mode.  Jump straight to the end of the string.
5696                     ix = (int32_t)fActiveLimit;
5697                     fHitEnd = TRUE;
5698                 } else {
5699                     // NOT DOT ALL mode.  Line endings do not match '.'
5700                     // Scan forward until a line ending or end of input.
5701                     ix = (int32_t)fp->fInputIdx;
5702                     for (;;) {
5703                         if (ix >= fActiveLimit) {
5704                             fHitEnd = TRUE;
5705                             break;
5706                         }
5707                         UChar32   c;
5708                         U16_NEXT(inputBuf, ix, fActiveLimit, c);   // c = inputBuf[ix++]
5709                         if ((c & 0x7f) <= 0x29) {          // Fast filter of non-new-line-s
5710                             if ((c == 0x0a) ||             //  0x0a is newline in both modes.
5711                                 (((opValue & 2) == 0) &&    // IF not UNIX_LINES mode
5712                                    isLineTerminator(c))) {
5713                                 //  char is a line ending.  Put the input pos back to the
5714                                 //    line ending char, and exit the scanning loop.
5715                                 U16_BACK_1(inputBuf, 0, ix);
5716                                 break;
5717                             }
5718                         }
5719                     }
5720                 }
5721
5722                 // If there were no matching characters, skip over the loop altogether.
5723                 //   The loop doesn't run at all, a * op always succeeds.
5724                 if (ix == fp->fInputIdx) {
5725                     fp->fPatIdx++;   // skip the URX_LOOP_C op.
5726                     break;
5727                 }
5728
5729                 // Peek ahead in the compiled pattern, to the URX_LOOP_C that
5730                 //   must follow.  It's operand is the stack location
5731                 //   that holds the starting input index for the match of this .*
5732                 int32_t loopcOp = (int32_t)pat[fp->fPatIdx];
5733                 U_ASSERT(URX_TYPE(loopcOp) == URX_LOOP_C);
5734                 int32_t stackLoc = URX_VAL(loopcOp);
5735                 U_ASSERT(stackLoc >= 0 && stackLoc < fFrameSize);
5736                 fp->fExtra[stackLoc] = fp->fInputIdx;
5737                 fp->fInputIdx = ix;
5738
5739                 // Save State to the URX_LOOP_C op that follows this one,
5740                 //   so that match failures in the following code will return to there.
5741                 //   Then bump the pattern idx so the LOOP_C is skipped on the way out of here.
5742                 fp = StateSave(fp, fp->fPatIdx, status);
5743                 fp->fPatIdx++;
5744             }
5745             break;
5746
5747
5748         case URX_LOOP_C:
5749             {
5750                 U_ASSERT(opValue>=0 && opValue<fFrameSize);
5751                 backSearchIndex = (int32_t)fp->fExtra[opValue];
5752                 U_ASSERT(backSearchIndex <= fp->fInputIdx);
5753                 if (backSearchIndex == fp->fInputIdx) {
5754                     // We've backed up the input idx to the point that the loop started.
5755                     // The loop is done.  Leave here without saving state.
5756                     //  Subsequent failures won't come back here.
5757                     break;
5758                 }
5759                 // Set up for the next iteration of the loop, with input index
5760                 //   backed up by one from the last time through,
5761                 //   and a state save to this instruction in case the following code fails again.
5762                 //   (We're going backwards because this loop emulates stack unwinding, not
5763                 //    the initial scan forward.)
5764                 U_ASSERT(fp->fInputIdx > 0);
5765                 UChar32 prevC;
5766                 U16_PREV(inputBuf, 0, fp->fInputIdx, prevC); // !!!: should this 0 be one of f*Limit?
5767
5768                 if (prevC == 0x0a &&
5769                     fp->fInputIdx > backSearchIndex &&
5770                     inputBuf[fp->fInputIdx-1] == 0x0d) {
5771                     int32_t prevOp = (int32_t)pat[fp->fPatIdx-2];
5772                     if (URX_TYPE(prevOp) == URX_LOOP_DOT_I) {
5773                         // .*, stepping back over CRLF pair.
5774                         U16_BACK_1(inputBuf, 0, fp->fInputIdx);
5775                     }
5776                 }
5777
5778
5779                 fp = StateSave(fp, fp->fPatIdx-1, status);
5780             }
5781             break;
5782
5783
5784
5785         default:
5786             // Trouble.  The compiled pattern contains an entry with an
5787             //           unrecognized type tag.
5788             UPRV_UNREACHABLE;
5789         }
5790
5791         if (U_FAILURE(status)) {
5792             isMatch = FALSE;
5793             break;
5794         }
5795     }
5796
5797 breakFromLoop:
5798     fMatch = isMatch;
5799     if (isMatch) {
5800         fLastMatchEnd = fMatchEnd;
5801         fMatchStart   = startIdx;
5802         fMatchEnd     = fp->fInputIdx;
5803     }
5804
5805 #ifdef REGEX_RUN_DEBUG
5806     if (fTraceDebug) {
5807         if (isMatch) {
5808             printf("Match.  start=%ld   end=%ld\n\n", fMatchStart, fMatchEnd);
5809         } else {
5810             printf("No match\n\n");
5811         }
5812     }
5813 #endif
5814
5815     fFrame = fp;                // The active stack frame when the engine stopped.
5816                                 //   Contains the capture group results that we need to
5817                                 //    access later.
5818
5819     return;
5820 }
5821
5822
5823 UOBJECT_DEFINE_RTTI_IMPLEMENTATION(RegexMatcher)
5824
5825 U_NAMESPACE_END
5826
5827 #endif  // !UCONFIG_NO_REGULAR_EXPRESSIONS
5828