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