1 // Copyright 2006 The RE2 Authors. All Rights Reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
5 // Regular expression parser.
7 // The parser is a simple precedence-based parser with a
8 // manual stack. The parsing work is done by the methods
9 // of the ParseState class. The Regexp::Parse function is
10 // essentially just a lexer that calls the ParseState method
13 // The parser recognizes POSIX extended regular expressions
14 // excluding backreferences, collating elements, and collating
15 // classes. It also allows the empty string as a regular expression
16 // and recognizes the Perl escape sequences \d, \s, \w, \D, \S, and \W.
17 // See regexp.h for rationale.
19 #include "util/util.h"
20 #include "re2/regexp.h"
21 #include "re2/stringpiece.h"
22 #include "re2/unicode_casefold.h"
23 #include "re2/unicode_groups.h"
27 // Regular expression parse state.
28 // The list of parsed regexps so far is maintained as a vector of
29 // Regexp pointers called the stack. Left parenthesis and vertical
30 // bar markers are also placed on the stack, as Regexps with
31 // non-standard opcodes.
32 // Scanning a left parenthesis causes the parser to push a left parenthesis
33 // marker on the stack.
34 // Scanning a vertical bar causes the parser to pop the stack until it finds a
35 // vertical bar or left parenthesis marker (not popping the marker),
36 // concatenate all the popped results, and push them back on
37 // the stack (DoConcatenation).
38 // Scanning a right parenthesis causes the parser to act as though it
39 // has seen a vertical bar, which then leaves the top of the stack in the
40 // form LeftParen regexp VerticalBar regexp VerticalBar ... regexp VerticalBar.
41 // The parser pops all this off the stack and creates an alternation of the
42 // regexps (DoAlternation).
44 class Regexp::ParseState {
46 ParseState(ParseFlags flags, const StringPiece& whole_regexp,
47 RegexpStatus* status);
50 ParseFlags flags() { return flags_; }
51 int rune_max() { return rune_max_; }
53 // Parse methods. All public methods return a bool saying
54 // whether parsing should continue. If a method returns
55 // false, it has set fields in *status_, and the parser
56 // should return NULL.
58 // Pushes the given regular expression onto the stack.
59 // Could check for too much memory used here.
60 bool PushRegexp(Regexp* re);
62 // Pushes the literal rune r onto the stack.
63 bool PushLiteral(Rune r);
65 // Pushes a regexp with the given op (and no args) onto the stack.
66 bool PushSimpleOp(RegexpOp op);
68 // Pushes a ^ onto the stack.
71 // Pushes a \b (word == true) or \B (word == false) onto the stack.
72 bool PushWordBoundary(bool word);
74 // Pushes a $ onto the stack.
77 // Pushes a . onto the stack
80 // Pushes a repeat operator regexp onto the stack.
81 // A valid argument for the operator must already be on the stack.
82 // s is the name of the operator, for use in error messages.
83 bool PushRepeatOp(RegexpOp op, const StringPiece& s, bool nongreedy);
85 // Pushes a repetition regexp onto the stack.
86 // A valid argument for the operator must already be on the stack.
87 bool PushRepetition(int min, int max, const StringPiece& s, bool nongreedy);
89 // Checks whether a particular regexp op is a marker.
90 bool IsMarker(RegexpOp op);
92 // Processes a left parenthesis in the input.
93 // Pushes a marker onto the stack.
94 bool DoLeftParen(const StringPiece& name);
95 bool DoLeftParenNoCapture();
97 // Processes a vertical bar in the input.
100 // Processes a right parenthesis in the input.
103 // Processes the end of input, returning the final regexp.
106 // Finishes the regexp if necessary, preparing it for use
107 // in a more complicated expression.
108 // If it is a CharClassBuilder, converts into a CharClass.
109 Regexp* FinishRegexp(Regexp*);
111 // These routines don't manipulate the parse stack
112 // directly, but they do need to look at flags_.
113 // ParseCharClass also manipulates the internals of Regexp
114 // while creating *out_re.
116 // Parse a character class into *out_re.
117 // Removes parsed text from s.
118 bool ParseCharClass(StringPiece* s, Regexp** out_re,
119 RegexpStatus* status);
121 // Parse a character class character into *rp.
122 // Removes parsed text from s.
123 bool ParseCCCharacter(StringPiece* s, Rune *rp,
124 const StringPiece& whole_class,
125 RegexpStatus* status);
127 // Parse a character class range into rr.
128 // Removes parsed text from s.
129 bool ParseCCRange(StringPiece* s, RuneRange* rr,
130 const StringPiece& whole_class,
131 RegexpStatus* status);
133 // Parse a Perl flag set or non-capturing group from s.
134 bool ParsePerlFlags(StringPiece* s);
137 // Finishes the current concatenation,
138 // collapsing it into a single regexp on the stack.
139 void DoConcatenation();
141 // Finishes the current alternation,
142 // collapsing it to a single regexp on the stack.
143 void DoAlternation();
145 // Generalized DoAlternation/DoConcatenation.
146 void DoCollapse(RegexpOp op);
148 // Maybe concatenate Literals into LiteralString.
149 bool MaybeConcatString(int r, ParseFlags flags);
153 StringPiece whole_regexp_;
154 RegexpStatus* status_;
156 int ncap_; // number of capturing parens seen
157 int rune_max_; // maximum char value for this encoding
159 DISALLOW_EVIL_CONSTRUCTORS(ParseState);
162 // Pseudo-operators - only on parse stack.
163 const RegexpOp kLeftParen = static_cast<RegexpOp>(kMaxRegexpOp+1);
164 const RegexpOp kVerticalBar = static_cast<RegexpOp>(kMaxRegexpOp+2);
166 Regexp::ParseState::ParseState(ParseFlags flags,
167 const StringPiece& whole_regexp,
168 RegexpStatus* status)
169 : flags_(flags), whole_regexp_(whole_regexp),
170 status_(status), stacktop_(NULL), ncap_(0) {
177 // Cleans up by freeing all the regexps on the stack.
178 Regexp::ParseState::~ParseState() {
180 for (Regexp* re = stacktop_; re != NULL; re = next) {
183 if (re->op() == kLeftParen)
189 // Finishes the regexp if necessary, preparing it for use in
190 // a more complex expression.
191 // If it is a CharClassBuilder, converts into a CharClass.
192 Regexp* Regexp::ParseState::FinishRegexp(Regexp* re) {
197 if (re->op_ == kRegexpCharClass && re->ccb_ != NULL) {
198 CharClassBuilder* ccb = re->ccb_;
200 re->cc_ = ccb->GetCharClass();
207 // Pushes the given regular expression onto the stack.
208 // Could check for too much memory used here.
209 bool Regexp::ParseState::PushRegexp(Regexp* re) {
210 MaybeConcatString(-1, NoParseFlags);
212 // Special case: a character class of one character is just
213 // a literal. This is a common idiom for escaping
214 // single characters (e.g., [.] instead of \.), and some
215 // analysis does better with fewer character classes.
216 // Similarly, [Aa] can be rewritten as a literal A with ASCII case folding.
217 if (re->op_ == kRegexpCharClass) {
218 if (re->ccb_->size() == 1) {
219 Rune r = re->ccb_->begin()->lo;
221 re = new Regexp(kRegexpLiteral, flags_);
223 } else if (re->ccb_->size() == 2) {
224 Rune r = re->ccb_->begin()->lo;
225 if ('A' <= r && r <= 'Z' && re->ccb_->Contains(r + 'a' - 'A')) {
227 re = new Regexp(kRegexpLiteral, flags_ | FoldCase);
228 re->rune_ = r + 'a' - 'A';
233 if (!IsMarker(re->op()))
234 re->simple_ = re->ComputeSimple();
235 re->down_ = stacktop_;
240 // Searches the case folding tables and returns the CaseFold* that contains r.
241 // If there isn't one, returns the CaseFold* with smallest f->lo bigger than r.
242 // If there isn't one, returns NULL.
243 CaseFold* LookupCaseFold(CaseFold *f, int n, Rune r) {
244 CaseFold* ef = f + n;
246 // Binary search for entry containing r.
249 if (f[m].lo <= r && r <= f[m].hi)
259 // There is no entry that contains r, but f points
260 // where it would have been. Unless f points at
261 // the end of the array, it points at the next entry
266 // No entry contains r; no entry contains runes > r.
270 // Returns the result of applying the fold f to the rune r.
271 Rune ApplyFold(CaseFold *f, Rune r) {
276 case EvenOddSkip: // even <-> odd but only applies to every other
280 case EvenOdd: // even <-> odd
285 case OddEvenSkip: // odd <-> even but only applies to every other
289 case OddEven: // odd <-> even
296 // Returns the next Rune in r's folding cycle (see unicode_casefold.h).
298 // CycleFoldRune('A') = 'a'
299 // CycleFoldRune('a') = 'A'
301 // CycleFoldRune('K') = 'k'
302 // CycleFoldRune('k') = 0x212A (Kelvin)
303 // CycleFoldRune(0x212A) = 'K'
305 // CycleFoldRune('?') = '?'
306 Rune CycleFoldRune(Rune r) {
307 CaseFold* f = LookupCaseFold(unicode_casefold, num_unicode_casefold, r);
308 if (f == NULL || r < f->lo)
310 return ApplyFold(f, r);
313 // Add lo-hi to the class, along with their fold-equivalent characters.
314 // If lo-hi is already in the class, assume that the fold-equivalent
315 // chars are there too, so there's no work to do.
316 static void AddFoldedRange(CharClassBuilder* cc, Rune lo, Rune hi, int depth) {
317 // AddFoldedRange calls itself recursively for each rune in the fold cycle.
318 // Most folding cycles are small: there aren't any bigger than four in the
319 // current Unicode tables. make_unicode_casefold.py checks that
320 // the cycles are not too long, and we double-check here using depth.
322 LOG(DFATAL) << "AddFoldedRange recurses too much.";
326 if (!cc->AddRange(lo, hi)) // lo-hi was already there? we're done
330 CaseFold* f = LookupCaseFold(unicode_casefold, num_unicode_casefold, lo);
331 if (f == NULL) // lo has no fold, nor does anything above lo
333 if (lo < f->lo) { // lo has no fold; next rune with a fold is f->lo
338 // Add in the result of folding the range lo - f->hi
339 // and that range's fold, recursively.
341 Rune hi1 = min<Rune>(hi, f->hi);
360 AddFoldedRange(cc, lo1, hi1, depth+1);
362 // Pick up where this fold left off.
367 // Pushes the literal rune r onto the stack.
368 bool Regexp::ParseState::PushLiteral(Rune r) {
369 // Do case folding if needed.
370 if ((flags_ & FoldCase) && CycleFoldRune(r) != r) {
371 Regexp* re = new Regexp(kRegexpCharClass, flags_ & ~FoldCase);
372 re->ccb_ = new CharClassBuilder;
375 if (!(flags_ & NeverNL) || r != '\n') {
376 re->ccb_->AddRange(r, r);
378 r = CycleFoldRune(r);
380 re->ccb_->RemoveAbove(rune_max_);
381 return PushRegexp(re);
384 // Exclude newline if applicable.
385 if ((flags_ & NeverNL) && r == '\n')
386 return PushRegexp(new Regexp(kRegexpNoMatch, flags_));
388 // No fancy stuff worked. Ordinary literal.
389 if (MaybeConcatString(r, flags_))
392 Regexp* re = new Regexp(kRegexpLiteral, flags_);
394 return PushRegexp(re);
397 // Pushes a ^ onto the stack.
398 bool Regexp::ParseState::PushCarat() {
399 if (flags_ & OneLine) {
400 return PushSimpleOp(kRegexpBeginText);
402 return PushSimpleOp(kRegexpBeginLine);
405 // Pushes a \b or \B onto the stack.
406 bool Regexp::ParseState::PushWordBoundary(bool word) {
408 return PushSimpleOp(kRegexpWordBoundary);
409 return PushSimpleOp(kRegexpNoWordBoundary);
412 // Pushes a $ onto the stack.
413 bool Regexp::ParseState::PushDollar() {
414 if (flags_ & OneLine) {
415 // Clumsy marker so that MimicsPCRE() can tell whether
416 // this kRegexpEndText was a $ and not a \z.
417 Regexp::ParseFlags oflags = flags_;
418 flags_ = flags_ | WasDollar;
419 bool ret = PushSimpleOp(kRegexpEndText);
423 return PushSimpleOp(kRegexpEndLine);
426 // Pushes a . onto the stack.
427 bool Regexp::ParseState::PushDot() {
428 if ((flags_ & DotNL) && !(flags_ & NeverNL))
429 return PushSimpleOp(kRegexpAnyChar);
430 // Rewrite . into [^\n]
431 Regexp* re = new Regexp(kRegexpCharClass, flags_ & ~FoldCase);
432 re->ccb_ = new CharClassBuilder;
433 re->ccb_->AddRange(0, '\n' - 1);
434 re->ccb_->AddRange('\n' + 1, rune_max_);
435 return PushRegexp(re);
438 // Pushes a regexp with the given op (and no args) onto the stack.
439 bool Regexp::ParseState::PushSimpleOp(RegexpOp op) {
440 Regexp* re = new Regexp(op, flags_);
441 return PushRegexp(re);
444 // Pushes a repeat operator regexp onto the stack.
445 // A valid argument for the operator must already be on the stack.
446 // The char c is the name of the operator, for use in error messages.
447 bool Regexp::ParseState::PushRepeatOp(RegexpOp op, const StringPiece& s,
449 if (stacktop_ == NULL || IsMarker(stacktop_->op())) {
450 status_->set_code(kRegexpRepeatArgument);
451 status_->set_error_arg(s);
454 Regexp::ParseFlags fl = flags_;
457 Regexp* re = new Regexp(op, fl);
459 re->down_ = stacktop_->down_;
460 re->sub()[0] = FinishRegexp(stacktop_);
461 re->simple_ = re->ComputeSimple();
466 // Pushes a repetition regexp onto the stack.
467 // A valid argument for the operator must already be on the stack.
468 bool Regexp::ParseState::PushRepetition(int min, int max,
469 const StringPiece& s,
471 if ((max != -1 && max < min) || min > 1000 || max > 1000) {
472 status_->set_code(kRegexpRepeatSize);
473 status_->set_error_arg(s);
476 if (stacktop_ == NULL || IsMarker(stacktop_->op())) {
477 status_->set_code(kRegexpRepeatArgument);
478 status_->set_error_arg(s);
481 Regexp::ParseFlags fl = flags_;
484 Regexp* re = new Regexp(kRegexpRepeat, fl);
488 re->down_ = stacktop_->down_;
489 re->sub()[0] = FinishRegexp(stacktop_);
490 re->simple_ = re->ComputeSimple();
496 // Checks whether a particular regexp op is a marker.
497 bool Regexp::ParseState::IsMarker(RegexpOp op) {
498 return op >= kLeftParen;
501 // Processes a left parenthesis in the input.
502 // Pushes a marker onto the stack.
503 bool Regexp::ParseState::DoLeftParen(const StringPiece& name) {
504 Regexp* re = new Regexp(kLeftParen, flags_);
506 if (name.data() != NULL)
507 re->name_ = new string(name.as_string());
508 return PushRegexp(re);
511 // Pushes a non-capturing marker onto the stack.
512 bool Regexp::ParseState::DoLeftParenNoCapture() {
513 Regexp* re = new Regexp(kLeftParen, flags_);
515 return PushRegexp(re);
518 // Adds r to cc, along with r's upper case if foldascii is set.
519 static void AddLiteral(CharClassBuilder* cc, Rune r, bool foldascii) {
521 if (foldascii && 'a' <= r && r <= 'z')
522 cc->AddRange(r + 'A' - 'a', r + 'A' - 'a');
525 // Processes a vertical bar in the input.
526 bool Regexp::ParseState::DoVerticalBar() {
527 MaybeConcatString(-1, NoParseFlags);
530 // Below the vertical bar is a list to alternate.
531 // Above the vertical bar is a list to concatenate.
532 // We just did the concatenation, so either swap
533 // the result below the vertical bar or push a new
534 // vertical bar on the stack.
537 if ((r1 = stacktop_) != NULL &&
538 (r2 = stacktop_->down_) != NULL &&
539 r2->op() == kVerticalBar) {
540 // If above and below vertical bar are literal or char class,
541 // can merge into a single char class.
543 if ((r1->op() == kRegexpLiteral ||
544 r1->op() == kRegexpCharClass ||
545 r1->op() == kRegexpAnyChar) &&
546 (r3 = r2->down_) != NULL) {
549 case kRegexpLiteral: // convert to char class
551 r3->op_ = kRegexpCharClass;
553 r3->ccb_ = new CharClassBuilder;
554 AddLiteral(r3->ccb_, rune, r3->parse_flags_ & Regexp::FoldCase);
556 case kRegexpCharClass:
557 if (r1->op() == kRegexpLiteral)
558 AddLiteral(r3->ccb_, r1->rune_,
559 r1->parse_flags_ & Regexp::FoldCase);
560 else if (r1->op() == kRegexpCharClass)
561 r3->ccb_->AddCharClass(r1->ccb_);
562 if (r1->op() == kRegexpAnyChar || r3->ccb_->full()) {
565 r3->op_ = kRegexpAnyChar;
578 // Swap r1 below vertical bar (r2).
579 r1->down_ = r2->down_;
584 return PushSimpleOp(kVerticalBar);
587 // Processes a right parenthesis in the input.
588 bool Regexp::ParseState::DoRightParen() {
589 // Finish the current concatenation and alternation.
592 // The stack should be: LeftParen regexp
593 // Remove the LeftParen, leaving the regexp,
597 if ((r1 = stacktop_) == NULL ||
598 (r2 = r1->down_) == NULL ||
599 r2->op() != kLeftParen) {
600 status_->set_code(kRegexpMissingParen);
601 status_->set_error_arg(whole_regexp_);
605 // Pop off r1, r2. Will Decref or reuse below.
606 stacktop_ = r2->down_;
608 // Restore flags from when paren opened.
610 flags_ = re->parse_flags();
612 // Rewrite LeftParen as capture if needed.
614 re->op_ = kRegexpCapture;
615 // re->cap_ is already set
617 re->sub()[0] = FinishRegexp(r1);
618 re->simple_ = re->ComputeSimple();
623 return PushRegexp(re);
626 // Processes the end of input, returning the final regexp.
627 Regexp* Regexp::ParseState::DoFinish() {
629 Regexp* re = stacktop_;
630 if (re != NULL && re->down_ != NULL) {
631 status_->set_code(kRegexpMissingParen);
632 status_->set_error_arg(whole_regexp_);
636 return FinishRegexp(re);
639 // Returns the leading regexp that re starts with.
640 // The returned Regexp* points into a piece of re,
641 // so it must not be used after the caller calls re->Decref().
642 Regexp* Regexp::LeadingRegexp(Regexp* re) {
643 if (re->op() == kRegexpEmptyMatch)
645 if (re->op() == kRegexpConcat && re->nsub() >= 2) {
646 Regexp** sub = re->sub();
647 if (sub[0]->op() == kRegexpEmptyMatch)
654 // Removes LeadingRegexp(re) from re and returns what's left.
655 // Consumes the reference to re and may edit it in place.
656 // If caller wants to hold on to LeadingRegexp(re),
657 // must have already Incref'ed it.
658 Regexp* Regexp::RemoveLeadingRegexp(Regexp* re) {
659 if (re->op() == kRegexpEmptyMatch)
661 if (re->op() == kRegexpConcat && re->nsub() >= 2) {
662 Regexp** sub = re->sub();
663 if (sub[0]->op() == kRegexpEmptyMatch)
667 if (re->nsub() == 2) {
668 // Collapse concatenation to single regexp.
669 Regexp* nre = sub[1];
674 // 3 or more -> 2 or more.
676 memmove(sub, sub + 1, re->nsub_ * sizeof sub[0]);
679 Regexp::ParseFlags pf = re->parse_flags();
681 return new Regexp(kRegexpEmptyMatch, pf);
684 // Returns the leading string that re starts with.
685 // The returned Rune* points into a piece of re,
686 // so it must not be used after the caller calls re->Decref().
687 Rune* Regexp::LeadingString(Regexp* re, int *nrune,
688 Regexp::ParseFlags *flags) {
689 while (re->op() == kRegexpConcat && re->nsub() > 0)
692 *flags = static_cast<Regexp::ParseFlags>(re->parse_flags_ & Regexp::FoldCase);
694 if (re->op() == kRegexpLiteral) {
699 if (re->op() == kRegexpLiteralString) {
700 *nrune = re->nrunes_;
708 // Removes the first n leading runes from the beginning of re.
709 // Edits re in place.
710 void Regexp::RemoveLeadingString(Regexp* re, int n) {
711 // Chase down concats to find first string.
712 // For regexps generated by parser, nested concats are
713 // flattened except when doing so would overflow the 16-bit
714 // limit on the size of a concatenation, so we should never
715 // see more than two here.
718 while (re->op() == kRegexpConcat) {
719 if (d < arraysize(stk))
724 // Remove leading string from re.
725 if (re->op() == kRegexpLiteral) {
727 re->op_ = kRegexpEmptyMatch;
728 } else if (re->op() == kRegexpLiteralString) {
729 if (n >= re->nrunes_) {
733 re->op_ = kRegexpEmptyMatch;
734 } else if (n == re->nrunes_ - 1) {
735 Rune rune = re->runes_[re->nrunes_ - 1];
740 re->op_ = kRegexpLiteral;
743 memmove(re->runes_, re->runes_ + n, re->nrunes_ * sizeof re->runes_[0]);
747 // If re is now empty, concatenations might simplify too.
750 Regexp** sub = re->sub();
751 if (sub[0]->op() == kRegexpEmptyMatch) {
754 // Delete first element of concat.
755 switch (re->nsub()) {
759 LOG(DFATAL) << "Concat of " << re->nsub();
761 re->op_ = kRegexpEmptyMatch;
765 // Replace re with sub[1].
766 Regexp* old = sub[1];
776 memmove(sub, sub + 1, re->nsub_ * sizeof sub[0]);
783 // Factors common prefixes from alternation.
785 // ABC|ABD|AEF|BCX|BCY
787 // A(B(C|D)|EF)|BC(X|Y)
788 // which the normal parse state routines will further simplify to
789 // A(B[CD]|EF)|BC[XY]
791 // Rewrites sub to contain simplified list to alternate and returns
792 // the new length of sub. Adjusts reference counts accordingly
793 // (incoming sub[i] decremented, outgoing sub[i] incremented).
795 // It's too much of a pain to write this code with an explicit stack,
796 // so instead we let the caller specify a maximum depth and
797 // don't simplify beyond that. There are around 15 words of local
798 // variables and parameters in the frame, so allowing 8 levels
799 // on a 64-bit machine is still less than a kilobyte of stack and
800 // probably enough benefit for practical uses.
801 const int kFactorAlternationMaxDepth = 8;
803 int Regexp::FactorAlternation(
805 Regexp::ParseFlags altflags) {
806 return FactorAlternationRecursive(sub, n, altflags,
807 kFactorAlternationMaxDepth);
810 int Regexp::FactorAlternationRecursive(
812 Regexp::ParseFlags altflags,
818 // Round 1: Factor out common literal prefixes.
821 Regexp::ParseFlags runeflags = Regexp::NoParseFlags;
824 for (int i = 0; i <= n; i++) {
825 // Invariant: what was in sub[0:start] has been Decref'ed
826 // and that space has been reused for sub[0:out] (out <= start).
828 // Invariant: sub[start:i] consists of regexps that all begin
829 // with the string rune[0:nrune].
833 Regexp::ParseFlags runeflags_i = Regexp::NoParseFlags;
835 rune_i = LeadingString(sub[i], &nrune_i, &runeflags_i);
836 if (runeflags_i == runeflags) {
838 while (same < nrune && same < nrune_i && rune[same] == rune_i[same])
841 // Matches at least one rune in current range. Keep going around.
848 // Found end of a run with common leading literal string:
849 // sub[start:i] all begin with rune[0:nrune] but sub[i]
850 // does not even begin with rune[0].
852 // Factor out common string and append factored expression to sub[0:out].
854 // Nothing to do - first iteration.
855 } else if (i == start+1) {
856 // Just one: don't bother factoring.
857 sub[out++] = sub[start];
859 // Construct factored form: prefix(suffix1|suffix2|...)
860 Regexp* x[2]; // x[0] = prefix, x[1] = suffix1|suffix2|...
861 x[0] = LiteralString(rune, nrune, runeflags);
862 for (int j = start; j < i; j++)
863 RemoveLeadingString(sub[j], nrune);
864 int nn = FactorAlternationRecursive(sub + start, i - start, altflags,
866 x[1] = AlternateNoFactor(sub + start, nn, altflags);
867 sub[out++] = Concat(x, 2, altflags);
870 // Prepare for next round (if there is one).
875 runeflags = runeflags_i;
880 // Round 2: Factor out common complex prefixes,
881 // just the first piece of each concatenation,
882 // whatever it is. This is good enough a lot of the time.
885 Regexp* first = NULL;
886 for (int i = 0; i <= n; i++) {
887 // Invariant: what was in sub[0:start] has been Decref'ed
888 // and that space has been reused for sub[0:out] (out <= start).
890 // Invariant: sub[start:i] consists of regexps that all begin with first.
892 Regexp* first_i = NULL;
894 first_i = LeadingRegexp(sub[i]);
895 if (first != NULL && Regexp::Equal(first, first_i)) {
900 // Found end of a run with common leading regexp:
901 // sub[start:i] all begin with first but sub[i] does not.
903 // Factor out common regexp and append factored expression to sub[0:out].
905 // Nothing to do - first iteration.
906 } else if (i == start+1) {
907 // Just one: don't bother factoring.
908 sub[out++] = sub[start];
910 // Construct factored form: prefix(suffix1|suffix2|...)
911 Regexp* x[2]; // x[0] = prefix, x[1] = suffix1|suffix2|...
912 x[0] = first->Incref();
913 for (int j = start; j < i; j++)
914 sub[j] = RemoveLeadingRegexp(sub[j]);
915 int nn = FactorAlternationRecursive(sub + start, i - start, altflags,
917 x[1] = AlternateNoFactor(sub + start, nn, altflags);
918 sub[out++] = Concat(x, 2, altflags);
921 // Prepare for next round (if there is one).
929 // Round 3: Collapse runs of single literals into character classes.
932 for (int i = 0; i <= n; i++) {
933 // Invariant: what was in sub[0:start] has been Decref'ed
934 // and that space has been reused for sub[0:out] (out <= start).
936 // Invariant: sub[start:i] consists of regexps that are either
937 // literal runes or character classes.
940 (sub[i]->op() == kRegexpLiteral ||
941 sub[i]->op() == kRegexpCharClass))
944 // sub[i] is not a char or char class;
945 // emit char class for sub[start:i]...
948 } else if (i == start+1) {
949 sub[out++] = sub[start];
951 // Make new char class.
952 CharClassBuilder ccb;
953 for (int j = start; j < i; j++) {
955 if (re->op() == kRegexpCharClass) {
956 CharClass* cc = re->cc();
957 for (CharClass::iterator it = cc->begin(); it != cc->end(); ++it)
958 ccb.AddRange(it->lo, it->hi);
959 } else if (re->op() == kRegexpLiteral) {
960 ccb.AddRangeFlags(re->rune(), re->rune(), re->parse_flags());
962 LOG(DFATAL) << "RE2: unexpected op: " << re->op() << " "
967 sub[out++] = NewCharClass(ccb.GetCharClass(), altflags);
970 // ... and then emit sub[i].
977 // Round 4: Collapse runs of empty matches into single empty match.
980 for (int i = 0; i < n; i++) {
982 sub[i]->op() == kRegexpEmptyMatch &&
983 sub[i+1]->op() == kRegexpEmptyMatch) {
994 // Collapse the regexps on top of the stack, down to the
995 // first marker, into a new op node (op == kRegexpAlternate
996 // or op == kRegexpConcat).
997 void Regexp::ParseState::DoCollapse(RegexpOp op) {
998 // Scan backward to marker, counting children of composite.
1000 Regexp* next = NULL;
1002 for (sub = stacktop_; sub != NULL && !IsMarker(sub->op()); sub = next) {
1010 // If there's just one child, leave it alone.
1011 // (Concat of one thing is that one thing; alternate of one thing is same.)
1012 if (stacktop_ != NULL && stacktop_->down_ == next)
1015 // Construct op (alternation or concatenation), flattening op of op.
1016 Regexp** subs = new Regexp*[n];
1019 for (sub = stacktop_; sub != NULL && !IsMarker(sub->op()); sub = next) {
1021 if (sub->op_ == op) {
1022 Regexp** sub_subs = sub->sub();
1023 for (int k = sub->nsub_ - 1; k >= 0; k--)
1024 subs[--i] = sub_subs[k]->Incref();
1027 subs[--i] = FinishRegexp(sub);
1031 Regexp* re = ConcatOrAlternate(op, subs, n, flags_, true);
1033 re->simple_ = re->ComputeSimple();
1038 // Finishes the current concatenation,
1039 // collapsing it into a single regexp on the stack.
1040 void Regexp::ParseState::DoConcatenation() {
1041 Regexp* r1 = stacktop_;
1042 if (r1 == NULL || IsMarker(r1->op())) {
1043 // empty concatenation is special case
1044 Regexp* re = new Regexp(kRegexpEmptyMatch, flags_);
1047 DoCollapse(kRegexpConcat);
1050 // Finishes the current alternation,
1051 // collapsing it to a single regexp on the stack.
1052 void Regexp::ParseState::DoAlternation() {
1054 // Now stack top is kVerticalBar.
1055 Regexp* r1 = stacktop_;
1056 stacktop_ = r1->down_;
1058 DoCollapse(kRegexpAlternate);
1061 // Incremental conversion of concatenated literals into strings.
1062 // If top two elements on stack are both literal or string,
1063 // collapse into single string.
1064 // Don't walk down the stack -- the parser calls this frequently
1065 // enough that below the bottom two is known to be collapsed.
1066 // Only called when another regexp is about to be pushed
1067 // on the stack, so that the topmost literal is not being considered.
1068 // (Otherwise ab* would turn into (ab)*.)
1069 // If r >= 0, consider pushing a literal r on the stack.
1070 // Return whether that happened.
1071 bool Regexp::ParseState::MaybeConcatString(int r, ParseFlags flags) {
1074 if ((re1 = stacktop_) == NULL || (re2 = re1->down_) == NULL)
1077 if (re1->op_ != kRegexpLiteral && re1->op_ != kRegexpLiteralString)
1079 if (re2->op_ != kRegexpLiteral && re2->op_ != kRegexpLiteralString)
1081 if ((re1->parse_flags_ & FoldCase) != (re2->parse_flags_ & FoldCase))
1084 if (re2->op_ == kRegexpLiteral) {
1085 // convert into string
1086 Rune rune = re2->rune_;
1087 re2->op_ = kRegexpLiteralString;
1090 re2->AddRuneToString(rune);
1093 // push re1 into re2.
1094 if (re1->op_ == kRegexpLiteral) {
1095 re2->AddRuneToString(re1->rune_);
1097 for (int i = 0; i < re1->nrunes_; i++)
1098 re2->AddRuneToString(re1->runes_[i]);
1100 delete[] re1->runes_;
1104 // reuse re1 if possible
1106 re1->op_ = kRegexpLiteral;
1108 re1->parse_flags_ = flags;
1119 // Parses a decimal integer, storing it in *n.
1120 // Sets *s to span the remainder of the string.
1121 // Sets *out_re to the regexp for the class.
1122 static bool ParseInteger(StringPiece* s, int* np) {
1123 if (s->size() == 0 || !isdigit((*s)[0] & 0xFF))
1125 // Disallow leading zeros.
1126 if (s->size() >= 2 && (*s)[0] == '0' && isdigit((*s)[1] & 0xFF))
1130 while (s->size() > 0 && isdigit(c = (*s)[0] & 0xFF)) {
1135 s->remove_prefix(1); // digit
1141 // Parses a repetition suffix like {1,2} or {2} or {2,}.
1142 // Sets *s to span the remainder of the string on success.
1143 // Sets *lo and *hi to the given range.
1144 // In the case of {2,}, the high number is unbounded;
1145 // sets *hi to -1 to signify this.
1146 // {,2} is NOT a valid suffix.
1147 // The Maybe in the name signifies that the regexp parse
1148 // doesn't fail even if ParseRepetition does, so the StringPiece
1149 // s must NOT be edited unless MaybeParseRepetition returns true.
1150 static bool MaybeParseRepetition(StringPiece* sp, int* lo, int* hi) {
1151 StringPiece s = *sp;
1152 if (s.size() == 0 || s[0] != '{')
1154 s.remove_prefix(1); // '{'
1155 if (!ParseInteger(&s, lo))
1160 s.remove_prefix(1); // ','
1164 // {2,} means at least 2
1167 // {2,4} means 2, 3, or 4.
1168 if (!ParseInteger(&s, hi))
1172 // {2} means exactly two
1175 if (s.size() == 0 || s[0] != '}')
1177 s.remove_prefix(1); // '}'
1182 // Removes the next Rune from the StringPiece and stores it in *r.
1183 // Returns number of bytes removed from sp.
1184 // Behaves as though there is a terminating NUL at the end of sp.
1185 // Argument order is backwards from usual Google style
1186 // but consistent with chartorune.
1187 static int StringPieceToRune(Rune *r, StringPiece *sp, RegexpStatus* status) {
1189 if (fullrune(sp->data(), sp->size())) {
1190 n = chartorune(r, sp->data());
1191 if (!(n == 1 && *r == Runeerror)) { // no decoding error
1192 sp->remove_prefix(n);
1197 status->set_code(kRegexpBadUTF8);
1198 status->set_error_arg(NULL);
1202 // Return whether name is valid UTF-8.
1203 // If not, set status to kRegexpBadUTF8.
1204 static bool IsValidUTF8(const StringPiece& s, RegexpStatus* status) {
1207 while (t.size() > 0) {
1208 if (StringPieceToRune(&r, &t, status) < 0)
1214 // Is c a hex digit?
1215 static int IsHex(int c) {
1216 return ('0' <= c && c <= '9') ||
1217 ('A' <= c && c <= 'F') ||
1218 ('a' <= c && c <= 'f');
1221 // Convert hex digit to value.
1222 static int UnHex(int c) {
1223 if ('0' <= c && c <= '9')
1225 if ('A' <= c && c <= 'F')
1226 return c - 'A' + 10;
1227 if ('a' <= c && c <= 'f')
1228 return c - 'a' + 10;
1229 LOG(DFATAL) << "Bad hex digit " << c;
1233 // Parse an escape sequence (e.g., \n, \{).
1234 // Sets *s to span the remainder of the string.
1235 // Sets *rp to the named character.
1236 static bool ParseEscape(StringPiece* s, Rune* rp,
1237 RegexpStatus* status, int rune_max) {
1238 const char* begin = s->begin();
1239 if (s->size() < 1 || (*s)[0] != '\\') {
1240 // Should not happen - caller always checks.
1241 status->set_code(kRegexpInternalError);
1242 status->set_error_arg(NULL);
1245 if (s->size() < 2) {
1246 status->set_code(kRegexpTrailingBackslash);
1247 status->set_error_arg(NULL);
1251 s->remove_prefix(1); // backslash
1252 if (StringPieceToRune(&c, s, status) < 0)
1257 if (c < Runeself && !isalpha(c) && !isdigit(c)) {
1258 // Escaped non-word characters are always themselves.
1259 // PCRE is not quite so rigorous: it accepts things like
1260 // \q, but we don't. We once rejected \_, but too many
1261 // programs and people insist on using it, so allow \_.
1275 // Single non-zero octal digit is a backreference; not supported.
1276 if (s->size() == 0 || (*s)[0] < '0' || (*s)[0] > '7')
1280 // consume up to three octal digits; already have one.
1282 if (s->size() > 0 && '0' <= (c = (*s)[0]) && c <= '7') {
1283 code = code * 8 + c - '0';
1284 s->remove_prefix(1); // digit
1285 if (s->size() > 0) {
1287 if ('0' <= c && c <= '7') {
1288 code = code * 8 + c - '0';
1289 s->remove_prefix(1); // digit
1296 // Hexadecimal escapes
1300 if (StringPieceToRune(&c, s, status) < 0)
1303 // Any number of digits in braces.
1304 // Update n as we consume the string, so that
1305 // the whole thing gets shown in the error message.
1306 // Perl accepts any text at all; it ignores all text
1307 // after the first non-hex digit. We require only hex digits,
1308 // and at least one.
1309 if (StringPieceToRune(&c, s, status) < 0)
1315 code = code * 16 + UnHex(c);
1316 if (code > rune_max)
1320 if (StringPieceToRune(&c, s, status) < 0)
1323 if (c != '}' || nhex == 0)
1328 // Easy case: two hex digits.
1331 if (StringPieceToRune(&c1, s, status) < 0)
1333 if (!IsHex(c) || !IsHex(c1))
1335 *rp = UnHex(c) * 16 + UnHex(c1);
1349 // Less common C escapes.
1360 // This code is disabled to avoid misparsing
1361 // the Perl word-boundary \b as a backspace
1362 // when in POSIX regexp mode. Surprisingly,
1363 // in Perl, \b means word-boundary but [\b]
1364 // means backspace. We don't support that:
1365 // if you want a backspace embed a literal
1366 // backspace character or use \x08.
1373 LOG(DFATAL) << "Not reached in ParseEscape.";
1376 // Unrecognized escape sequence.
1377 status->set_code(kRegexpBadEscape);
1378 status->set_error_arg(StringPiece(begin, s->data() - begin));
1382 // Add a range to the character class, but exclude newline if asked.
1383 // Also handle case folding.
1384 void CharClassBuilder::AddRangeFlags(
1385 Rune lo, Rune hi, Regexp::ParseFlags parse_flags) {
1387 // Take out \n if the flags say so.
1388 bool cutnl = !(parse_flags & Regexp::ClassNL) ||
1389 (parse_flags & Regexp::NeverNL);
1390 if (cutnl && lo <= '\n' && '\n' <= hi) {
1392 AddRangeFlags(lo, '\n' - 1, parse_flags);
1394 AddRangeFlags('\n' + 1, hi, parse_flags);
1398 // If folding case, add fold-equivalent characters too.
1399 if (parse_flags & Regexp::FoldCase)
1400 AddFoldedRange(this, lo, hi, 0);
1405 // Look for a group with the given name.
1406 static UGroup* LookupGroup(const StringPiece& name,
1407 UGroup *groups, int ngroups) {
1408 // Simple name lookup.
1409 for (int i = 0; i < ngroups; i++)
1410 if (StringPiece(groups[i].name) == name)
1415 // Fake UGroup containing all Runes
1416 static URange16 any16[] = { { 0, 65535 } };
1417 static URange32 any32[] = { { 65536, Runemax } };
1418 static UGroup anygroup = { "Any", +1, any16, 1, any32, 1 };
1420 // Look for a POSIX group with the given name (e.g., "[:^alpha:]")
1421 static UGroup* LookupPosixGroup(const StringPiece& name) {
1422 return LookupGroup(name, posix_groups, num_posix_groups);
1425 static UGroup* LookupPerlGroup(const StringPiece& name) {
1426 return LookupGroup(name, perl_groups, num_perl_groups);
1429 // Look for a Unicode group with the given name (e.g., "Han")
1430 static UGroup* LookupUnicodeGroup(const StringPiece& name) {
1431 // Special case: "Any" means any.
1432 if (name == StringPiece("Any"))
1434 return LookupGroup(name, unicode_groups, num_unicode_groups);
1437 // Add a UGroup or its negation to the character class.
1438 static void AddUGroup(CharClassBuilder *cc, UGroup *g, int sign,
1439 Regexp::ParseFlags parse_flags) {
1441 for (int i = 0; i < g->nr16; i++) {
1442 cc->AddRangeFlags(g->r16[i].lo, g->r16[i].hi, parse_flags);
1444 for (int i = 0; i < g->nr32; i++) {
1445 cc->AddRangeFlags(g->r32[i].lo, g->r32[i].hi, parse_flags);
1448 if (parse_flags & Regexp::FoldCase) {
1449 // Normally adding a case-folded group means
1450 // adding all the extra fold-equivalent runes too.
1451 // But if we're adding the negation of the group,
1452 // we have to exclude all the runes that are fold-equivalent
1453 // to what's already missing. Too hard, so do in two steps.
1454 CharClassBuilder ccb1;
1455 AddUGroup(&ccb1, g, +1, parse_flags);
1456 // If the flags say to take out \n, put it in, so that negating will take it out.
1457 // Normally AddRangeFlags does this, but we're bypassing AddRangeFlags.
1458 bool cutnl = !(parse_flags & Regexp::ClassNL) ||
1459 (parse_flags & Regexp::NeverNL);
1461 ccb1.AddRange('\n', '\n');
1464 cc->AddCharClass(&ccb1);
1468 for (int i = 0; i < g->nr16; i++) {
1469 if (next < g->r16[i].lo)
1470 cc->AddRangeFlags(next, g->r16[i].lo - 1, parse_flags);
1471 next = g->r16[i].hi + 1;
1473 for (int i = 0; i < g->nr32; i++) {
1474 if (next < g->r32[i].lo)
1475 cc->AddRangeFlags(next, g->r32[i].lo - 1, parse_flags);
1476 next = g->r32[i].hi + 1;
1478 if (next <= Runemax)
1479 cc->AddRangeFlags(next, Runemax, parse_flags);
1483 // Maybe parse a Perl character class escape sequence.
1484 // Only recognizes the Perl character classes (\d \s \w \D \S \W),
1485 // not the Perl empty-string classes (\b \B \A \Z \z).
1486 // On success, sets *s to span the remainder of the string
1487 // and returns the corresponding UGroup.
1488 // The StringPiece must *NOT* be edited unless the call succeeds.
1489 UGroup* MaybeParsePerlCCEscape(StringPiece* s, Regexp::ParseFlags parse_flags) {
1490 if (!(parse_flags & Regexp::PerlClasses))
1492 if (s->size() < 2 || (*s)[0] != '\\')
1494 // Could use StringPieceToRune, but there aren't
1495 // any non-ASCII Perl group names.
1496 StringPiece name(s->begin(), 2);
1497 UGroup *g = LookupPerlGroup(name);
1500 s->remove_prefix(name.size());
1505 kParseOk, // Did some parsing.
1506 kParseError, // Found an error.
1507 kParseNothing, // Decided not to parse.
1510 // Maybe parses a Unicode character group like \p{Han} or \P{Han}
1511 // (the latter is a negated group).
1512 ParseStatus ParseUnicodeGroup(StringPiece* s, Regexp::ParseFlags parse_flags,
1513 CharClassBuilder *cc,
1514 RegexpStatus* status) {
1515 // Decide whether to parse.
1516 if (!(parse_flags & Regexp::UnicodeGroups))
1517 return kParseNothing;
1518 if (s->size() < 2 || (*s)[0] != '\\')
1519 return kParseNothing;
1521 if (c != 'p' && c != 'P')
1522 return kParseNothing;
1524 // Committed to parse. Results:
1525 int sign = +1; // -1 = negated char class
1528 StringPiece seq = *s; // \p{Han} or \pL
1529 StringPiece name; // Han or L
1530 s->remove_prefix(2); // '\\', 'p'
1532 if (!StringPieceToRune(&c, s, status))
1535 // Name is the bit of string we just skipped over for c.
1536 const char* p = seq.begin() + 2;
1537 name = StringPiece(p, s->begin() - p);
1539 // Name is in braces. Look for closing }
1540 int end = s->find('}', 0);
1541 if (end == s->npos) {
1542 if (!IsValidUTF8(seq, status))
1544 status->set_code(kRegexpBadCharRange);
1545 status->set_error_arg(seq);
1548 name = StringPiece(s->begin(), end); // without '}'
1549 s->remove_prefix(end + 1); // with '}'
1550 if (!IsValidUTF8(name, status))
1554 // Chop seq where s now begins.
1555 seq = StringPiece(seq.begin(), s->begin() - seq.begin());
1558 if (name.size() > 0 && name[0] == '^') {
1560 name.remove_prefix(1); // '^'
1562 UGroup *g = LookupUnicodeGroup(name);
1564 status->set_code(kRegexpBadCharRange);
1565 status->set_error_arg(seq);
1569 AddUGroup(cc, g, sign, parse_flags);
1573 // Parses a character class name like [:alnum:].
1574 // Sets *s to span the remainder of the string.
1575 // Adds the ranges corresponding to the class to ranges.
1576 static ParseStatus ParseCCName(StringPiece* s, Regexp::ParseFlags parse_flags,
1577 CharClassBuilder *cc,
1578 RegexpStatus* status) {
1579 // Check begins with [:
1580 const char* p = s->data();
1581 const char* ep = s->data() + s->size();
1582 if (ep - p < 2 || p[0] != '[' || p[1] != ':')
1583 return kParseNothing;
1585 // Look for closing :].
1587 for (q = p+2; q <= ep-2 && (*q != ':' || *(q+1) != ']'); q++)
1590 // If no closing :], then ignore.
1592 return kParseNothing;
1594 // Got it. Check that it's valid.
1596 StringPiece name(p, q-p);
1598 UGroup *g = LookupPosixGroup(name);
1600 status->set_code(kRegexpBadCharRange);
1601 status->set_error_arg(name);
1605 s->remove_prefix(name.size());
1606 AddUGroup(cc, g, g->sign, parse_flags);
1610 // Parses a character inside a character class.
1611 // There are fewer special characters here than in the rest of the regexp.
1612 // Sets *s to span the remainder of the string.
1613 // Sets *rp to the character.
1614 bool Regexp::ParseState::ParseCCCharacter(StringPiece* s, Rune *rp,
1615 const StringPiece& whole_class,
1616 RegexpStatus* status) {
1617 if (s->size() == 0) {
1618 status->set_code(kRegexpMissingBracket);
1619 status->set_error_arg(whole_class);
1623 // Allow regular escape sequences even though
1624 // many need not be escaped in this context.
1625 if (s->size() >= 1 && (*s)[0] == '\\')
1626 return ParseEscape(s, rp, status, rune_max_);
1628 // Otherwise take the next rune.
1629 return StringPieceToRune(rp, s, status) >= 0;
1632 // Parses a character class character, or, if the character
1633 // is followed by a hyphen, parses a character class range.
1634 // For single characters, rr->lo == rr->hi.
1635 // Sets *s to span the remainder of the string.
1636 // Sets *rp to the character.
1637 bool Regexp::ParseState::ParseCCRange(StringPiece* s, RuneRange* rr,
1638 const StringPiece& whole_class,
1639 RegexpStatus* status) {
1640 StringPiece os = *s;
1641 if (!ParseCCCharacter(s, &rr->lo, whole_class, status))
1643 // [a-] means (a|-), so check for final ].
1644 if (s->size() >= 2 && (*s)[0] == '-' && (*s)[1] != ']') {
1645 s->remove_prefix(1); // '-'
1646 if (!ParseCCCharacter(s, &rr->hi, whole_class, status))
1648 if (rr->hi < rr->lo) {
1649 status->set_code(kRegexpBadCharRange);
1650 status->set_error_arg(StringPiece(os.data(), s->data() - os.data()));
1659 // Parses a possibly-negated character class expression like [^abx-z[:digit:]].
1660 // Sets *s to span the remainder of the string.
1661 // Sets *out_re to the regexp for the class.
1662 bool Regexp::ParseState::ParseCharClass(StringPiece* s,
1664 RegexpStatus* status) {
1665 StringPiece whole_class = *s;
1666 if (s->size() == 0 || (*s)[0] != '[') {
1667 // Caller checked this.
1668 status->set_code(kRegexpInternalError);
1669 status->set_error_arg(NULL);
1672 bool negated = false;
1673 Regexp* re = new Regexp(kRegexpCharClass, flags_ & ~FoldCase);
1674 re->ccb_ = new CharClassBuilder;
1675 s->remove_prefix(1); // '['
1676 if (s->size() > 0 && (*s)[0] == '^') {
1677 s->remove_prefix(1); // '^'
1679 if (!(flags_ & ClassNL) || (flags_ & NeverNL)) {
1680 // If NL can't match implicitly, then pretend
1681 // negated classes include a leading \n.
1682 re->ccb_->AddRange('\n', '\n');
1685 bool first = true; // ] is okay as first char in class
1686 while (s->size() > 0 && ((*s)[0] != ']' || first)) {
1687 // - is only okay unescaped as first or last in class.
1688 // Except that Perl allows - anywhere.
1689 if ((*s)[0] == '-' && !first && !(flags_&PerlX) &&
1690 (s->size() == 1 || (*s)[1] != ']')) {
1692 t.remove_prefix(1); // '-'
1694 int n = StringPieceToRune(&r, &t, status);
1699 status->set_code(kRegexpBadCharRange);
1700 status->set_error_arg(StringPiece(s->data(), 1+n));
1706 // Look for [:alnum:] etc.
1707 if (s->size() > 2 && (*s)[0] == '[' && (*s)[1] == ':') {
1708 switch (ParseCCName(s, flags_, re->ccb_, status)) {
1719 // Look for Unicode character group like \p{Han}
1720 if (s->size() > 2 &&
1722 ((*s)[1] == 'p' || (*s)[1] == 'P')) {
1723 switch (ParseUnicodeGroup(s, flags_, re->ccb_, status)) {
1734 // Look for Perl character class symbols (extension).
1735 UGroup *g = MaybeParsePerlCCEscape(s, flags_);
1737 AddUGroup(re->ccb_, g, g->sign, flags_);
1741 // Otherwise assume single character or simple range.
1743 if (!ParseCCRange(s, &rr, whole_class, status)) {
1747 // AddRangeFlags is usually called in response to a class like
1748 // \p{Foo} or [[:foo:]]; for those, it filters \n out unless
1749 // Regexp::ClassNL is set. In an explicit range or singleton
1750 // like we just parsed, we do not filter \n out, so set ClassNL
1752 re->ccb_->AddRangeFlags(rr.lo, rr.hi, flags_ | Regexp::ClassNL);
1754 if (s->size() == 0) {
1755 status->set_code(kRegexpMissingBracket);
1756 status->set_error_arg(whole_class);
1760 s->remove_prefix(1); // ']'
1764 re->ccb_->RemoveAbove(rune_max_);
1770 // Is this a valid capture name? [A-Za-z0-9_]+
1771 // PCRE limits names to 32 bytes.
1772 // Python rejects names starting with digits.
1773 // We don't enforce either of those.
1774 static bool IsValidCaptureName(const StringPiece& name) {
1775 if (name.size() == 0)
1777 for (int i = 0; i < name.size(); i++) {
1779 if (('0' <= c && c <= '9') ||
1780 ('a' <= c && c <= 'z') ||
1781 ('A' <= c && c <= 'Z') ||
1789 // Parses a Perl flag setting or non-capturing group or both,
1790 // like (?i) or (?: or (?i:. Removes from s, updates parse state.
1791 // The caller must check that s begins with "(?".
1792 // Returns true on success. If the Perl flag is not
1793 // well-formed or not supported, sets status_ and returns false.
1794 bool Regexp::ParseState::ParsePerlFlags(StringPiece* s) {
1797 // Caller is supposed to check this.
1798 if (!(flags_ & PerlX) || t.size() < 2 || t[0] != '(' || t[1] != '?') {
1799 LOG(DFATAL) << "Bad call to ParseState::ParsePerlFlags";
1800 status_->set_code(kRegexpInternalError);
1804 t.remove_prefix(2); // "(?"
1806 // Check for named captures, first introduced in Python's regexp library.
1807 // As usual, there are three slightly different syntaxes:
1809 // (?P<name>expr) the original, introduced by Python
1810 // (?<name>expr) the .NET alteration, adopted by Perl 5.10
1811 // (?'name'expr) another .NET alteration, adopted by Perl 5.10
1813 // Perl 5.10 gave in and implemented the Python version too,
1814 // but they claim that the last two are the preferred forms.
1815 // PCRE and languages based on it (specifically, PHP and Ruby)
1816 // support all three as well. EcmaScript 4 uses only the Python form.
1818 // In both the open source world (via Code Search) and the
1819 // Google source tree, (?P<expr>name) is the dominant form,
1820 // so that's the one we implement. One is enough.
1821 if (t.size() > 2 && t[0] == 'P' && t[1] == '<') {
1823 int end = t.find('>', 2);
1824 if (end == t.npos) {
1825 if (!IsValidUTF8(*s, status_))
1827 status_->set_code(kRegexpBadNamedCapture);
1828 status_->set_error_arg(*s);
1832 // t is "P<name>...", t[end] == '>'
1833 StringPiece capture(t.begin()-2, end+3); // "(?P<name>"
1834 StringPiece name(t.begin()+2, end-2); // "name"
1835 if (!IsValidUTF8(name, status_))
1837 if (!IsValidCaptureName(name)) {
1838 status_->set_code(kRegexpBadNamedCapture);
1839 status_->set_error_arg(capture);
1843 if (!DoLeftParen(name)) {
1844 // DoLeftParen's failure set status_.
1848 s->remove_prefix(capture.end() - s->begin());
1852 bool negated = false;
1853 bool sawflags = false;
1854 int nflags = flags_;
1856 for (bool done = false; !done; ) {
1859 if (StringPieceToRune(&c, &t, status_) < 0)
1869 nflags &= ~FoldCase;
1874 case 'm': // opposite of our OneLine
1893 nflags &= ~NonGreedy;
1895 nflags |= NonGreedy;
1908 if (!DoLeftParenNoCapture()) {
1909 // DoLeftParenNoCapture's failure set status_.
1922 if (negated && !sawflags)
1925 flags_ = static_cast<Regexp::ParseFlags>(nflags);
1930 status_->set_code(kRegexpBadPerlOp);
1931 status_->set_error_arg(StringPiece(s->begin(), t.begin() - s->begin()));
1935 // Converts latin1 (assumed to be encoded as Latin1 bytes)
1936 // into UTF8 encoding in string.
1937 // Can't use EncodingUtils::EncodeLatin1AsUTF8 because it is
1938 // deprecated and because it rejects code points 0x80-0x9F.
1939 void ConvertLatin1ToUTF8(const StringPiece& latin1, string* utf) {
1943 for (int i = 0; i < latin1.size(); i++) {
1944 Rune r = latin1[i] & 0xFF;
1945 int n = runetochar(buf, &r);
1946 utf->append(buf, n);
1950 // Parses the regular expression given by s,
1951 // returning the corresponding Regexp tree.
1952 // The caller must Decref the return value when done with it.
1953 // Returns NULL on error.
1954 Regexp* Regexp::Parse(const StringPiece& s, ParseFlags global_flags,
1955 RegexpStatus* status) {
1956 // Make status non-NULL (easier on everyone else).
1957 RegexpStatus xstatus;
1961 ParseState ps(global_flags, s, status);
1964 // Convert regexp to UTF-8 (easier on the rest of the parser).
1965 if (global_flags & Latin1) {
1966 string* tmp = new string;
1967 ConvertLatin1ToUTF8(t, tmp);
1968 status->set_tmp(tmp);
1972 if (global_flags & Literal) {
1973 // Special parse loop for literal string.
1974 while (t.size() > 0) {
1976 if (StringPieceToRune(&r, &t, status) < 0)
1978 if (!ps.PushLiteral(r))
1981 return ps.DoFinish();
1984 StringPiece lastunary = NULL;
1985 while (t.size() > 0) {
1986 StringPiece isunary = NULL;
1990 if (StringPieceToRune(&r, &t, status) < 0)
1992 if (!ps.PushLiteral(r))
1998 // "(?" introduces Perl escape.
1999 if ((ps.flags() & PerlX) && (t.size() >= 2 && t[1] == '?')) {
2000 // Flag changes and non-capturing groups.
2001 if (!ps.ParsePerlFlags(&t))
2005 if (ps.flags() & NeverCapture) {
2006 if (!ps.DoLeftParenNoCapture())
2009 if (!ps.DoLeftParen(NULL))
2012 t.remove_prefix(1); // '('
2016 if (!ps.DoVerticalBar())
2018 t.remove_prefix(1); // '|'
2022 if (!ps.DoRightParen())
2024 t.remove_prefix(1); // ')'
2027 case '^': // Beginning of line.
2028 if (!ps.PushCarat())
2030 t.remove_prefix(1); // '^'
2033 case '$': // End of line.
2034 if (!ps.PushDollar())
2036 t.remove_prefix(1); // '$'
2039 case '.': // Any character (possibly except newline).
2042 t.remove_prefix(1); // '.'
2045 case '[': { // Character class.
2047 if (!ps.ParseCharClass(&t, &re, status))
2049 if (!ps.PushRegexp(re))
2054 case '*': { // Zero or more.
2058 case '+': // One or more.
2061 case '?': // Zero or one.
2065 StringPiece opstr = t;
2066 bool nongreedy = false;
2067 t.remove_prefix(1); // '*' or '+' or '?'
2068 if (ps.flags() & PerlX) {
2069 if (t.size() > 0 && t[0] == '?') {
2071 t.remove_prefix(1); // '?'
2073 if (lastunary.size() > 0) {
2074 // In Perl it is not allowed to stack repetition operators:
2075 // a** is a syntax error, not a double-star.
2076 // (and a++ means something else entirely, which we don't support!)
2077 status->set_code(kRegexpRepeatOp);
2078 status->set_error_arg(StringPiece(lastunary.begin(),
2079 t.begin() - lastunary.begin()));
2083 opstr.set(opstr.data(), t.data() - opstr.data());
2084 if (!ps.PushRepeatOp(op, opstr, nongreedy))
2090 case '{': { // Counted repetition.
2092 StringPiece opstr = t;
2093 if (!MaybeParseRepetition(&t, &lo, &hi)) {
2094 // Treat like a literal.
2095 if (!ps.PushLiteral('{'))
2097 t.remove_prefix(1); // '{'
2100 bool nongreedy = false;
2101 if (ps.flags() & PerlX) {
2102 if (t.size() > 0 && t[0] == '?') {
2104 t.remove_prefix(1); // '?'
2106 if (lastunary.size() > 0) {
2107 // Not allowed to stack repetition operators.
2108 status->set_code(kRegexpRepeatOp);
2109 status->set_error_arg(StringPiece(lastunary.begin(),
2110 t.begin() - lastunary.begin()));
2114 opstr.set(opstr.data(), t.data() - opstr.data());
2115 if (!ps.PushRepetition(lo, hi, opstr, nongreedy))
2121 case '\\': { // Escaped character or Perl sequence.
2122 // \b and \B: word boundary or not
2123 if ((ps.flags() & Regexp::PerlB) &&
2124 t.size() >= 2 && (t[1] == 'b' || t[1] == 'B')) {
2125 if (!ps.PushWordBoundary(t[1] == 'b'))
2127 t.remove_prefix(2); // '\\', 'b'
2131 if ((ps.flags() & Regexp::PerlX) && t.size() >= 2) {
2133 if (!ps.PushSimpleOp(kRegexpBeginText))
2135 t.remove_prefix(2); // '\\', 'A'
2139 if (!ps.PushSimpleOp(kRegexpEndText))
2141 t.remove_prefix(2); // '\\', 'z'
2144 // Do not recognize \Z, because this library can't
2145 // implement the exact Perl/PCRE semantics.
2146 // (This library treats "(?-m)$" as \z, even though
2147 // in Perl and PCRE it is equivalent to \Z.)
2149 if (t[1] == 'C') { // \C: any byte [sic]
2150 if (!ps.PushSimpleOp(kRegexpAnyByte))
2152 t.remove_prefix(2); // '\\', 'C'
2156 if (t[1] == 'Q') { // \Q ... \E: the ... is always literals
2157 t.remove_prefix(2); // '\\', 'Q'
2158 while (t.size() > 0) {
2159 if (t.size() >= 2 && t[0] == '\\' && t[1] == 'E') {
2160 t.remove_prefix(2); // '\\', 'E'
2164 if (StringPieceToRune(&r, &t, status) < 0)
2166 if (!ps.PushLiteral(r))
2173 if (t.size() >= 2 && (t[1] == 'p' || t[1] == 'P')) {
2174 Regexp* re = new Regexp(kRegexpCharClass, ps.flags() & ~FoldCase);
2175 re->ccb_ = new CharClassBuilder;
2176 switch (ParseUnicodeGroup(&t, ps.flags(), re->ccb_, status)) {
2178 if (!ps.PushRegexp(re))
2190 UGroup *g = MaybeParsePerlCCEscape(&t, ps.flags());
2192 Regexp* re = new Regexp(kRegexpCharClass, ps.flags() & ~FoldCase);
2193 re->ccb_ = new CharClassBuilder;
2194 AddUGroup(re->ccb_, g, g->sign, ps.flags());
2195 if (!ps.PushRegexp(re))
2201 if (!ParseEscape(&t, &r, status, ps.rune_max()))
2203 if (!ps.PushLiteral(r))
2209 lastunary = isunary;
2211 return ps.DoFinish();