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