| // Copyright 2006 The RE2 Authors. All Rights Reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| // Regular expression parser. |
| |
| // The parser is a simple precedence-based parser with a |
| // manual stack. The parsing work is done by the methods |
| // of the ParseState class. The Regexp::Parse function is |
| // essentially just a lexer that calls the ParseState method |
| // for each token. |
| |
| // The parser recognizes POSIX extended regular expressions |
| // excluding backreferences, collating elements, and collating |
| // classes. It also allows the empty string as a regular expression |
| // and recognizes the Perl escape sequences \d, \s, \w, \D, \S, and \W. |
| // See regexp.h for rationale. |
| |
| #include "util/util.h" |
| #include "re2/regexp.h" |
| #include "re2/stringpiece.h" |
| #include "re2/unicode_casefold.h" |
| #include "re2/unicode_groups.h" |
| |
| namespace re2 { |
| |
| // Regular expression parse state. |
| // The list of parsed regexps so far is maintained as a vector of |
| // Regexp pointers called the stack. Left parenthesis and vertical |
| // bar markers are also placed on the stack, as Regexps with |
| // non-standard opcodes. |
| // Scanning a left parenthesis causes the parser to push a left parenthesis |
| // marker on the stack. |
| // Scanning a vertical bar causes the parser to pop the stack until it finds a |
| // vertical bar or left parenthesis marker (not popping the marker), |
| // concatenate all the popped results, and push them back on |
| // the stack (DoConcatenation). |
| // Scanning a right parenthesis causes the parser to act as though it |
| // has seen a vertical bar, which then leaves the top of the stack in the |
| // form LeftParen regexp VerticalBar regexp VerticalBar ... regexp VerticalBar. |
| // The parser pops all this off the stack and creates an alternation of the |
| // regexps (DoAlternation). |
| |
| class Regexp::ParseState { |
| public: |
| ParseState(ParseFlags flags, const StringPiece& whole_regexp, |
| RegexpStatus* status); |
| ~ParseState(); |
| |
| ParseFlags flags() { return flags_; } |
| int rune_max() { return rune_max_; } |
| |
| // Parse methods. All public methods return a bool saying |
| // whether parsing should continue. If a method returns |
| // false, it has set fields in *status_, and the parser |
| // should return NULL. |
| |
| // Pushes the given regular expression onto the stack. |
| // Could check for too much memory used here. |
| bool PushRegexp(Regexp* re); |
| |
| // Pushes the literal rune r onto the stack. |
| bool PushLiteral(Rune r); |
| |
| // Pushes a regexp with the given op (and no args) onto the stack. |
| bool PushSimpleOp(RegexpOp op); |
| |
| // Pushes a ^ onto the stack. |
| bool PushCarat(); |
| |
| // Pushes a \b (word == true) or \B (word == false) onto the stack. |
| bool PushWordBoundary(bool word); |
| |
| // Pushes a $ onto the stack. |
| bool PushDollar(); |
| |
| // Pushes a . onto the stack |
| bool PushDot(); |
| |
| // Pushes a repeat operator regexp onto the stack. |
| // A valid argument for the operator must already be on the stack. |
| // s is the name of the operator, for use in error messages. |
| bool PushRepeatOp(RegexpOp op, const StringPiece& s, bool nongreedy); |
| |
| // Pushes a repetition regexp onto the stack. |
| // A valid argument for the operator must already be on the stack. |
| bool PushRepetition(int min, int max, const StringPiece& s, bool nongreedy); |
| |
| // Checks whether a particular regexp op is a marker. |
| bool IsMarker(RegexpOp op); |
| |
| // Processes a left parenthesis in the input. |
| // Pushes a marker onto the stack. |
| bool DoLeftParen(const StringPiece& name); |
| bool DoLeftParenNoCapture(); |
| |
| // Processes a vertical bar in the input. |
| bool DoVerticalBar(); |
| |
| // Processes a right parenthesis in the input. |
| bool DoRightParen(); |
| |
| // Processes the end of input, returning the final regexp. |
| Regexp* DoFinish(); |
| |
| // Finishes the regexp if necessary, preparing it for use |
| // in a more complicated expression. |
| // If it is a CharClassBuilder, converts into a CharClass. |
| Regexp* FinishRegexp(Regexp*); |
| |
| // These routines don't manipulate the parse stack |
| // directly, but they do need to look at flags_. |
| // ParseCharClass also manipulates the internals of Regexp |
| // while creating *out_re. |
| |
| // Parse a character class into *out_re. |
| // Removes parsed text from s. |
| bool ParseCharClass(StringPiece* s, Regexp** out_re, |
| RegexpStatus* status); |
| |
| // Parse a character class character into *rp. |
| // Removes parsed text from s. |
| bool ParseCCCharacter(StringPiece* s, Rune *rp, |
| const StringPiece& whole_class, |
| RegexpStatus* status); |
| |
| // Parse a character class range into rr. |
| // Removes parsed text from s. |
| bool ParseCCRange(StringPiece* s, RuneRange* rr, |
| const StringPiece& whole_class, |
| RegexpStatus* status); |
| |
| // Parse a Perl flag set or non-capturing group from s. |
| bool ParsePerlFlags(StringPiece* s); |
| |
| |
| // Finishes the current concatenation, |
| // collapsing it into a single regexp on the stack. |
| void DoConcatenation(); |
| |
| // Finishes the current alternation, |
| // collapsing it to a single regexp on the stack. |
| void DoAlternation(); |
| |
| // Generalized DoAlternation/DoConcatenation. |
| void DoCollapse(RegexpOp op); |
| |
| // Maybe concatenate Literals into LiteralString. |
| bool MaybeConcatString(int r, ParseFlags flags); |
| |
| private: |
| ParseFlags flags_; |
| StringPiece whole_regexp_; |
| RegexpStatus* status_; |
| Regexp* stacktop_; |
| int ncap_; // number of capturing parens seen |
| int rune_max_; // maximum char value for this encoding |
| |
| DISALLOW_EVIL_CONSTRUCTORS(ParseState); |
| }; |
| |
| // Pseudo-operators - only on parse stack. |
| const RegexpOp kLeftParen = static_cast<RegexpOp>(kMaxRegexpOp+1); |
| const RegexpOp kVerticalBar = static_cast<RegexpOp>(kMaxRegexpOp+2); |
| |
| Regexp::ParseState::ParseState(ParseFlags flags, |
| const StringPiece& whole_regexp, |
| RegexpStatus* status) |
| : flags_(flags), whole_regexp_(whole_regexp), |
| status_(status), stacktop_(NULL), ncap_(0) { |
| if (flags_ & Latin1) |
| rune_max_ = 0xFF; |
| else |
| rune_max_ = Runemax; |
| } |
| |
| // Cleans up by freeing all the regexps on the stack. |
| Regexp::ParseState::~ParseState() { |
| Regexp* next; |
| for (Regexp* re = stacktop_; re != NULL; re = next) { |
| next = re->down_; |
| re->down_ = NULL; |
| if (re->op() == kLeftParen) |
| delete re->name_; |
| re->Decref(); |
| } |
| } |
| |
| // Finishes the regexp if necessary, preparing it for use in |
| // a more complex expression. |
| // If it is a CharClassBuilder, converts into a CharClass. |
| Regexp* Regexp::ParseState::FinishRegexp(Regexp* re) { |
| if (re == NULL) |
| return NULL; |
| re->down_ = NULL; |
| |
| if (re->op_ == kRegexpCharClass && re->ccb_ != NULL) { |
| CharClassBuilder* ccb = re->ccb_; |
| re->ccb_ = NULL; |
| re->cc_ = ccb->GetCharClass(); |
| delete ccb; |
| } |
| |
| return re; |
| } |
| |
| // Pushes the given regular expression onto the stack. |
| // Could check for too much memory used here. |
| bool Regexp::ParseState::PushRegexp(Regexp* re) { |
| MaybeConcatString(-1, NoParseFlags); |
| |
| // Special case: a character class of one character is just |
| // a literal. This is a common idiom for escaping |
| // single characters (e.g., [.] instead of \.), and some |
| // analysis does better with fewer character classes. |
| // Similarly, [Aa] can be rewritten as a literal A with ASCII case folding. |
| if (re->op_ == kRegexpCharClass) { |
| if (re->ccb_->size() == 1) { |
| Rune r = re->ccb_->begin()->lo; |
| re->Decref(); |
| re = new Regexp(kRegexpLiteral, flags_); |
| re->rune_ = r; |
| } else if (re->ccb_->size() == 2) { |
| Rune r = re->ccb_->begin()->lo; |
| if ('A' <= r && r <= 'Z' && re->ccb_->Contains(r + 'a' - 'A')) { |
| re->Decref(); |
| re = new Regexp(kRegexpLiteral, flags_ | FoldCase); |
| re->rune_ = r + 'a' - 'A'; |
| } |
| } |
| } |
| |
| if (!IsMarker(re->op())) |
| re->simple_ = re->ComputeSimple(); |
| re->down_ = stacktop_; |
| stacktop_ = re; |
| return true; |
| } |
| |
| // Searches the case folding tables and returns the CaseFold* that contains r. |
| // If there isn't one, returns the CaseFold* with smallest f->lo bigger than r. |
| // If there isn't one, returns NULL. |
| CaseFold* LookupCaseFold(CaseFold *f, int n, Rune r) { |
| CaseFold* ef = f + n; |
| |
| // Binary search for entry containing r. |
| while (n > 0) { |
| int m = n/2; |
| if (f[m].lo <= r && r <= f[m].hi) |
| return &f[m]; |
| if (r < f[m].lo) { |
| n = m; |
| } else { |
| f += m+1; |
| n -= m+1; |
| } |
| } |
| |
| // There is no entry that contains r, but f points |
| // where it would have been. Unless f points at |
| // the end of the array, it points at the next entry |
| // after r. |
| if (f < ef) |
| return f; |
| |
| // No entry contains r; no entry contains runes > r. |
| return NULL; |
| } |
| |
| // Returns the result of applying the fold f to the rune r. |
| Rune ApplyFold(CaseFold *f, Rune r) { |
| switch (f->delta) { |
| default: |
| return r + f->delta; |
| |
| case EvenOddSkip: // even <-> odd but only applies to every other |
| if ((r - f->lo) % 2) |
| return r; |
| // fall through |
| case EvenOdd: // even <-> odd |
| if (r%2 == 0) |
| return r + 1; |
| return r - 1; |
| |
| case OddEvenSkip: // odd <-> even but only applies to every other |
| if ((r - f->lo) % 2) |
| return r; |
| // fall through |
| case OddEven: // odd <-> even |
| if (r%2 == 1) |
| return r + 1; |
| return r - 1; |
| } |
| } |
| |
| // Returns the next Rune in r's folding cycle (see unicode_casefold.h). |
| // Examples: |
| // CycleFoldRune('A') = 'a' |
| // CycleFoldRune('a') = 'A' |
| // |
| // CycleFoldRune('K') = 'k' |
| // CycleFoldRune('k') = 0x212A (Kelvin) |
| // CycleFoldRune(0x212A) = 'K' |
| // |
| // CycleFoldRune('?') = '?' |
| Rune CycleFoldRune(Rune r) { |
| CaseFold* f = LookupCaseFold(unicode_casefold, num_unicode_casefold, r); |
| if (f == NULL || r < f->lo) |
| return r; |
| return ApplyFold(f, r); |
| } |
| |
| // Add lo-hi to the class, along with their fold-equivalent characters. |
| // If lo-hi is already in the class, assume that the fold-equivalent |
| // chars are there too, so there's no work to do. |
| static void AddFoldedRange(CharClassBuilder* cc, Rune lo, Rune hi, int depth) { |
| // AddFoldedRange calls itself recursively for each rune in the fold cycle. |
| // Most folding cycles are small: there aren't any bigger than four in the |
| // current Unicode tables. make_unicode_casefold.py checks that |
| // the cycles are not too long, and we double-check here using depth. |
| if (depth > 10) { |
| LOG(DFATAL) << "AddFoldedRange recurses too much."; |
| return; |
| } |
| |
| if (!cc->AddRange(lo, hi)) // lo-hi was already there? we're done |
| return; |
| |
| while (lo <= hi) { |
| CaseFold* f = LookupCaseFold(unicode_casefold, num_unicode_casefold, lo); |
| if (f == NULL) // lo has no fold, nor does anything above lo |
| break; |
| if (lo < f->lo) { // lo has no fold; next rune with a fold is f->lo |
| lo = f->lo; |
| continue; |
| } |
| |
| // Add in the result of folding the range lo - f->hi |
| // and that range's fold, recursively. |
| Rune lo1 = lo; |
| Rune hi1 = min<Rune>(hi, f->hi); |
| switch (f->delta) { |
| default: |
| lo1 += f->delta; |
| hi1 += f->delta; |
| break; |
| case EvenOdd: |
| if (lo1%2 == 1) |
| lo1--; |
| if (hi1%2 == 0) |
| hi1++; |
| break; |
| case OddEven: |
| if (lo1%2 == 0) |
| lo1--; |
| if (hi1%2 == 1) |
| hi1++; |
| break; |
| } |
| AddFoldedRange(cc, lo1, hi1, depth+1); |
| |
| // Pick up where this fold left off. |
| lo = f->hi + 1; |
| } |
| } |
| |
| // Pushes the literal rune r onto the stack. |
| bool Regexp::ParseState::PushLiteral(Rune r) { |
| // Do case folding if needed. |
| if ((flags_ & FoldCase) && CycleFoldRune(r) != r) { |
| Regexp* re = new Regexp(kRegexpCharClass, flags_ & ~FoldCase); |
| re->ccb_ = new CharClassBuilder; |
| Rune r1 = r; |
| do { |
| if (!(flags_ & NeverNL) || r != '\n') { |
| re->ccb_->AddRange(r, r); |
| } |
| r = CycleFoldRune(r); |
| } while (r != r1); |
| re->ccb_->RemoveAbove(rune_max_); |
| return PushRegexp(re); |
| } |
| |
| // Exclude newline if applicable. |
| if ((flags_ & NeverNL) && r == '\n') |
| return PushRegexp(new Regexp(kRegexpNoMatch, flags_)); |
| |
| // No fancy stuff worked. Ordinary literal. |
| if (MaybeConcatString(r, flags_)) |
| return true; |
| |
| Regexp* re = new Regexp(kRegexpLiteral, flags_); |
| re->rune_ = r; |
| return PushRegexp(re); |
| } |
| |
| // Pushes a ^ onto the stack. |
| bool Regexp::ParseState::PushCarat() { |
| if (flags_ & OneLine) { |
| return PushSimpleOp(kRegexpBeginText); |
| } |
| return PushSimpleOp(kRegexpBeginLine); |
| } |
| |
| // Pushes a \b or \B onto the stack. |
| bool Regexp::ParseState::PushWordBoundary(bool word) { |
| if (word) |
| return PushSimpleOp(kRegexpWordBoundary); |
| return PushSimpleOp(kRegexpNoWordBoundary); |
| } |
| |
| // Pushes a $ onto the stack. |
| bool Regexp::ParseState::PushDollar() { |
| if (flags_ & OneLine) { |
| // Clumsy marker so that MimicsPCRE() can tell whether |
| // this kRegexpEndText was a $ and not a \z. |
| Regexp::ParseFlags oflags = flags_; |
| flags_ = flags_ | WasDollar; |
| bool ret = PushSimpleOp(kRegexpEndText); |
| flags_ = oflags; |
| return ret; |
| } |
| return PushSimpleOp(kRegexpEndLine); |
| } |
| |
| // Pushes a . onto the stack. |
| bool Regexp::ParseState::PushDot() { |
| if ((flags_ & DotNL) && !(flags_ & NeverNL)) |
| return PushSimpleOp(kRegexpAnyChar); |
| // Rewrite . into [^\n] |
| Regexp* re = new Regexp(kRegexpCharClass, flags_ & ~FoldCase); |
| re->ccb_ = new CharClassBuilder; |
| re->ccb_->AddRange(0, '\n' - 1); |
| re->ccb_->AddRange('\n' + 1, rune_max_); |
| return PushRegexp(re); |
| } |
| |
| // Pushes a regexp with the given op (and no args) onto the stack. |
| bool Regexp::ParseState::PushSimpleOp(RegexpOp op) { |
| Regexp* re = new Regexp(op, flags_); |
| return PushRegexp(re); |
| } |
| |
| // Pushes a repeat operator regexp onto the stack. |
| // A valid argument for the operator must already be on the stack. |
| // The char c is the name of the operator, for use in error messages. |
| bool Regexp::ParseState::PushRepeatOp(RegexpOp op, const StringPiece& s, |
| bool nongreedy) { |
| if (stacktop_ == NULL || IsMarker(stacktop_->op())) { |
| status_->set_code(kRegexpRepeatArgument); |
| status_->set_error_arg(s); |
| return false; |
| } |
| Regexp::ParseFlags fl = flags_; |
| if (nongreedy) |
| fl = fl ^ NonGreedy; |
| Regexp* re = new Regexp(op, fl); |
| re->AllocSub(1); |
| re->down_ = stacktop_->down_; |
| re->sub()[0] = FinishRegexp(stacktop_); |
| re->simple_ = re->ComputeSimple(); |
| stacktop_ = re; |
| return true; |
| } |
| |
| // Pushes a repetition regexp onto the stack. |
| // A valid argument for the operator must already be on the stack. |
| bool Regexp::ParseState::PushRepetition(int min, int max, |
| const StringPiece& s, |
| bool nongreedy) { |
| if ((max != -1 && max < min) || min > 1000 || max > 1000) { |
| status_->set_code(kRegexpRepeatSize); |
| status_->set_error_arg(s); |
| return false; |
| } |
| if (stacktop_ == NULL || IsMarker(stacktop_->op())) { |
| status_->set_code(kRegexpRepeatArgument); |
| status_->set_error_arg(s); |
| return false; |
| } |
| Regexp::ParseFlags fl = flags_; |
| if (nongreedy) |
| fl = fl ^ NonGreedy; |
| Regexp* re = new Regexp(kRegexpRepeat, fl); |
| re->min_ = min; |
| re->max_ = max; |
| re->AllocSub(1); |
| re->down_ = stacktop_->down_; |
| re->sub()[0] = FinishRegexp(stacktop_); |
| re->simple_ = re->ComputeSimple(); |
| |
| stacktop_ = re; |
| return true; |
| } |
| |
| // Checks whether a particular regexp op is a marker. |
| bool Regexp::ParseState::IsMarker(RegexpOp op) { |
| return op >= kLeftParen; |
| } |
| |
| // Processes a left parenthesis in the input. |
| // Pushes a marker onto the stack. |
| bool Regexp::ParseState::DoLeftParen(const StringPiece& name) { |
| Regexp* re = new Regexp(kLeftParen, flags_); |
| re->cap_ = ++ncap_; |
| if (name.data() != NULL) |
| re->name_ = new string(name.as_string()); |
| return PushRegexp(re); |
| } |
| |
| // Pushes a non-capturing marker onto the stack. |
| bool Regexp::ParseState::DoLeftParenNoCapture() { |
| Regexp* re = new Regexp(kLeftParen, flags_); |
| re->cap_ = -1; |
| return PushRegexp(re); |
| } |
| |
| // Adds r to cc, along with r's upper case if foldascii is set. |
| static void AddLiteral(CharClassBuilder* cc, Rune r, bool foldascii) { |
| cc->AddRange(r, r); |
| if (foldascii && 'a' <= r && r <= 'z') |
| cc->AddRange(r + 'A' - 'a', r + 'A' - 'a'); |
| } |
| |
| // Processes a vertical bar in the input. |
| bool Regexp::ParseState::DoVerticalBar() { |
| MaybeConcatString(-1, NoParseFlags); |
| DoConcatenation(); |
| |
| // Below the vertical bar is a list to alternate. |
| // Above the vertical bar is a list to concatenate. |
| // We just did the concatenation, so either swap |
| // the result below the vertical bar or push a new |
| // vertical bar on the stack. |
| Regexp* r1; |
| Regexp* r2; |
| if ((r1 = stacktop_) != NULL && |
| (r2 = stacktop_->down_) != NULL && |
| r2->op() == kVerticalBar) { |
| // If above and below vertical bar are literal or char class, |
| // can merge into a single char class. |
| Regexp* r3; |
| if ((r1->op() == kRegexpLiteral || |
| r1->op() == kRegexpCharClass || |
| r1->op() == kRegexpAnyChar) && |
| (r3 = r2->down_) != NULL) { |
| Rune rune; |
| switch (r3->op()) { |
| case kRegexpLiteral: // convert to char class |
| rune = r3->rune_; |
| r3->op_ = kRegexpCharClass; |
| r3->cc_ = NULL; |
| r3->ccb_ = new CharClassBuilder; |
| AddLiteral(r3->ccb_, rune, r3->parse_flags_ & Regexp::FoldCase); |
| // fall through |
| case kRegexpCharClass: |
| if (r1->op() == kRegexpLiteral) |
| AddLiteral(r3->ccb_, r1->rune_, |
| r1->parse_flags_ & Regexp::FoldCase); |
| else if (r1->op() == kRegexpCharClass) |
| r3->ccb_->AddCharClass(r1->ccb_); |
| if (r1->op() == kRegexpAnyChar || r3->ccb_->full()) { |
| delete r3->ccb_; |
| r3->ccb_ = NULL; |
| r3->op_ = kRegexpAnyChar; |
| } |
| // fall through |
| case kRegexpAnyChar: |
| // pop r1 |
| stacktop_ = r2; |
| r1->Decref(); |
| return true; |
| default: |
| break; |
| } |
| } |
| |
| // Swap r1 below vertical bar (r2). |
| r1->down_ = r2->down_; |
| r2->down_ = r1; |
| stacktop_ = r2; |
| return true; |
| } |
| return PushSimpleOp(kVerticalBar); |
| } |
| |
| // Processes a right parenthesis in the input. |
| bool Regexp::ParseState::DoRightParen() { |
| // Finish the current concatenation and alternation. |
| DoAlternation(); |
| |
| // The stack should be: LeftParen regexp |
| // Remove the LeftParen, leaving the regexp, |
| // parenthesized. |
| Regexp* r1; |
| Regexp* r2; |
| if ((r1 = stacktop_) == NULL || |
| (r2 = r1->down_) == NULL || |
| r2->op() != kLeftParen) { |
| status_->set_code(kRegexpMissingParen); |
| status_->set_error_arg(whole_regexp_); |
| return false; |
| } |
| |
| // Pop off r1, r2. Will Decref or reuse below. |
| stacktop_ = r2->down_; |
| |
| // Restore flags from when paren opened. |
| Regexp* re = r2; |
| flags_ = re->parse_flags(); |
| |
| // Rewrite LeftParen as capture if needed. |
| if (re->cap_ > 0) { |
| re->op_ = kRegexpCapture; |
| // re->cap_ is already set |
| re->AllocSub(1); |
| re->sub()[0] = FinishRegexp(r1); |
| re->simple_ = re->ComputeSimple(); |
| } else { |
| re->Decref(); |
| re = r1; |
| } |
| return PushRegexp(re); |
| } |
| |
| // Processes the end of input, returning the final regexp. |
| Regexp* Regexp::ParseState::DoFinish() { |
| DoAlternation(); |
| Regexp* re = stacktop_; |
| if (re != NULL && re->down_ != NULL) { |
| status_->set_code(kRegexpMissingParen); |
| status_->set_error_arg(whole_regexp_); |
| return NULL; |
| } |
| stacktop_ = NULL; |
| return FinishRegexp(re); |
| } |
| |
| // Returns the leading regexp that re starts with. |
| // The returned Regexp* points into a piece of re, |
| // so it must not be used after the caller calls re->Decref(). |
| Regexp* Regexp::LeadingRegexp(Regexp* re) { |
| if (re->op() == kRegexpEmptyMatch) |
| return NULL; |
| if (re->op() == kRegexpConcat && re->nsub() >= 2) { |
| Regexp** sub = re->sub(); |
| if (sub[0]->op() == kRegexpEmptyMatch) |
| return NULL; |
| return sub[0]; |
| } |
| return re; |
| } |
| |
| // Removes LeadingRegexp(re) from re and returns what's left. |
| // Consumes the reference to re and may edit it in place. |
| // If caller wants to hold on to LeadingRegexp(re), |
| // must have already Incref'ed it. |
| Regexp* Regexp::RemoveLeadingRegexp(Regexp* re) { |
| if (re->op() == kRegexpEmptyMatch) |
| return re; |
| if (re->op() == kRegexpConcat && re->nsub() >= 2) { |
| Regexp** sub = re->sub(); |
| if (sub[0]->op() == kRegexpEmptyMatch) |
| return re; |
| sub[0]->Decref(); |
| sub[0] = NULL; |
| if (re->nsub() == 2) { |
| // Collapse concatenation to single regexp. |
| Regexp* nre = sub[1]; |
| sub[1] = NULL; |
| re->Decref(); |
| return nre; |
| } |
| // 3 or more -> 2 or more. |
| re->nsub_--; |
| memmove(sub, sub + 1, re->nsub_ * sizeof sub[0]); |
| return re; |
| } |
| Regexp::ParseFlags pf = re->parse_flags(); |
| re->Decref(); |
| return new Regexp(kRegexpEmptyMatch, pf); |
| } |
| |
| // Returns the leading string that re starts with. |
| // The returned Rune* points into a piece of re, |
| // so it must not be used after the caller calls re->Decref(). |
| Rune* Regexp::LeadingString(Regexp* re, int *nrune, |
| Regexp::ParseFlags *flags) { |
| while (re->op() == kRegexpConcat && re->nsub() > 0) |
| re = re->sub()[0]; |
| |
| *flags = static_cast<Regexp::ParseFlags>(re->parse_flags_ & Regexp::FoldCase); |
| |
| if (re->op() == kRegexpLiteral) { |
| *nrune = 1; |
| return &re->rune_; |
| } |
| |
| if (re->op() == kRegexpLiteralString) { |
| *nrune = re->nrunes_; |
| return re->runes_; |
| } |
| |
| *nrune = 0; |
| return NULL; |
| } |
| |
| // Removes the first n leading runes from the beginning of re. |
| // Edits re in place. |
| void Regexp::RemoveLeadingString(Regexp* re, int n) { |
| // Chase down concats to find first string. |
| // For regexps generated by parser, nested concats are |
| // flattened except when doing so would overflow the 16-bit |
| // limit on the size of a concatenation, so we should never |
| // see more than two here. |
| Regexp* stk[4]; |
| int d = 0; |
| while (re->op() == kRegexpConcat) { |
| if (d < arraysize(stk)) |
| stk[d++] = re; |
| re = re->sub()[0]; |
| } |
| |
| // Remove leading string from re. |
| if (re->op() == kRegexpLiteral) { |
| re->rune_ = 0; |
| re->op_ = kRegexpEmptyMatch; |
| } else if (re->op() == kRegexpLiteralString) { |
| if (n >= re->nrunes_) { |
| delete[] re->runes_; |
| re->runes_ = NULL; |
| re->nrunes_ = 0; |
| re->op_ = kRegexpEmptyMatch; |
| } else if (n == re->nrunes_ - 1) { |
| Rune rune = re->runes_[re->nrunes_ - 1]; |
| delete[] re->runes_; |
| re->runes_ = NULL; |
| re->nrunes_ = 0; |
| re->rune_ = rune; |
| re->op_ = kRegexpLiteral; |
| } else { |
| re->nrunes_ -= n; |
| memmove(re->runes_, re->runes_ + n, re->nrunes_ * sizeof re->runes_[0]); |
| } |
| } |
| |
| // If re is now empty, concatenations might simplify too. |
| while (d-- > 0) { |
| re = stk[d]; |
| Regexp** sub = re->sub(); |
| if (sub[0]->op() == kRegexpEmptyMatch) { |
| sub[0]->Decref(); |
| sub[0] = NULL; |
| // Delete first element of concat. |
| switch (re->nsub()) { |
| case 0: |
| case 1: |
| // Impossible. |
| LOG(DFATAL) << "Concat of " << re->nsub(); |
| re->submany_ = NULL; |
| re->op_ = kRegexpEmptyMatch; |
| break; |
| |
| case 2: { |
| // Replace re with sub[1]. |
| Regexp* old = sub[1]; |
| sub[1] = NULL; |
| re->Swap(old); |
| old->Decref(); |
| break; |
| } |
| |
| default: |
| // Slide down. |
| re->nsub_--; |
| memmove(sub, sub + 1, re->nsub_ * sizeof sub[0]); |
| break; |
| } |
| } |
| } |
| } |
| |
| // Factors common prefixes from alternation. |
| // For example, |
| // ABC|ABD|AEF|BCX|BCY |
| // simplifies to |
| // A(B(C|D)|EF)|BC(X|Y) |
| // which the normal parse state routines will further simplify to |
| // A(B[CD]|EF)|BC[XY] |
| // |
| // Rewrites sub to contain simplified list to alternate and returns |
| // the new length of sub. Adjusts reference counts accordingly |
| // (incoming sub[i] decremented, outgoing sub[i] incremented). |
| |
| // It's too much of a pain to write this code with an explicit stack, |
| // so instead we let the caller specify a maximum depth and |
| // don't simplify beyond that. There are around 15 words of local |
| // variables and parameters in the frame, so allowing 8 levels |
| // on a 64-bit machine is still less than a kilobyte of stack and |
| // probably enough benefit for practical uses. |
| const int kFactorAlternationMaxDepth = 8; |
| |
| int Regexp::FactorAlternation( |
| Regexp** sub, int n, |
| Regexp::ParseFlags altflags) { |
| return FactorAlternationRecursive(sub, n, altflags, |
| kFactorAlternationMaxDepth); |
| } |
| |
| int Regexp::FactorAlternationRecursive( |
| Regexp** sub, int n, |
| Regexp::ParseFlags altflags, |
| int maxdepth) { |
| |
| if (maxdepth <= 0) |
| return n; |
| |
| // Round 1: Factor out common literal prefixes. |
| Rune *rune = NULL; |
| int nrune = 0; |
| Regexp::ParseFlags runeflags = Regexp::NoParseFlags; |
| int start = 0; |
| int out = 0; |
| for (int i = 0; i <= n; i++) { |
| // Invariant: what was in sub[0:start] has been Decref'ed |
| // and that space has been reused for sub[0:out] (out <= start). |
| // |
| // Invariant: sub[start:i] consists of regexps that all begin |
| // with the string rune[0:nrune]. |
| |
| Rune* rune_i = NULL; |
| int nrune_i = 0; |
| Regexp::ParseFlags runeflags_i = Regexp::NoParseFlags; |
| if (i < n) { |
| rune_i = LeadingString(sub[i], &nrune_i, &runeflags_i); |
| if (runeflags_i == runeflags) { |
| int same = 0; |
| while (same < nrune && same < nrune_i && rune[same] == rune_i[same]) |
| same++; |
| if (same > 0) { |
| // Matches at least one rune in current range. Keep going around. |
| nrune = same; |
| continue; |
| } |
| } |
| } |
| |
| // Found end of a run with common leading literal string: |
| // sub[start:i] all begin with rune[0:nrune] but sub[i] |
| // does not even begin with rune[0]. |
| // |
| // Factor out common string and append factored expression to sub[0:out]. |
| if (i == start) { |
| // Nothing to do - first iteration. |
| } else if (i == start+1) { |
| // Just one: don't bother factoring. |
| sub[out++] = sub[start]; |
| } else { |
| // Construct factored form: prefix(suffix1|suffix2|...) |
| Regexp* x[2]; // x[0] = prefix, x[1] = suffix1|suffix2|... |
| x[0] = LiteralString(rune, nrune, runeflags); |
| for (int j = start; j < i; j++) |
| RemoveLeadingString(sub[j], nrune); |
| int nn = FactorAlternationRecursive(sub + start, i - start, altflags, |
| maxdepth - 1); |
| x[1] = AlternateNoFactor(sub + start, nn, altflags); |
| sub[out++] = Concat(x, 2, altflags); |
| } |
| |
| // Prepare for next round (if there is one). |
| if (i < n) { |
| start = i; |
| rune = rune_i; |
| nrune = nrune_i; |
| runeflags = runeflags_i; |
| } |
| } |
| n = out; |
| |
| // Round 2: Factor out common complex prefixes, |
| // just the first piece of each concatenation, |
| // whatever it is. This is good enough a lot of the time. |
| start = 0; |
| out = 0; |
| Regexp* first = NULL; |
| for (int i = 0; i <= n; i++) { |
| // Invariant: what was in sub[0:start] has been Decref'ed |
| // and that space has been reused for sub[0:out] (out <= start). |
| // |
| // Invariant: sub[start:i] consists of regexps that all begin with first. |
| |
| Regexp* first_i = NULL; |
| if (i < n) { |
| first_i = LeadingRegexp(sub[i]); |
| if (first != NULL && Regexp::Equal(first, first_i)) { |
| continue; |
| } |
| } |
| |
| // Found end of a run with common leading regexp: |
| // sub[start:i] all begin with first but sub[i] does not. |
| // |
| // Factor out common regexp and append factored expression to sub[0:out]. |
| if (i == start) { |
| // Nothing to do - first iteration. |
| } else if (i == start+1) { |
| // Just one: don't bother factoring. |
| sub[out++] = sub[start]; |
| } else { |
| // Construct factored form: prefix(suffix1|suffix2|...) |
| Regexp* x[2]; // x[0] = prefix, x[1] = suffix1|suffix2|... |
| x[0] = first->Incref(); |
| for (int j = start; j < i; j++) |
| sub[j] = RemoveLeadingRegexp(sub[j]); |
| int nn = FactorAlternationRecursive(sub + start, i - start, altflags, |
| maxdepth - 1); |
| x[1] = AlternateNoFactor(sub + start, nn, altflags); |
| sub[out++] = Concat(x, 2, altflags); |
| } |
| |
| // Prepare for next round (if there is one). |
| if (i < n) { |
| start = i; |
| first = first_i; |
| } |
| } |
| n = out; |
| |
| // Round 3: Collapse runs of single literals into character classes. |
| start = 0; |
| out = 0; |
| for (int i = 0; i <= n; i++) { |
| // Invariant: what was in sub[0:start] has been Decref'ed |
| // and that space has been reused for sub[0:out] (out <= start). |
| // |
| // Invariant: sub[start:i] consists of regexps that are either |
| // literal runes or character classes. |
| |
| if (i < n && |
| (sub[i]->op() == kRegexpLiteral || |
| sub[i]->op() == kRegexpCharClass)) |
| continue; |
| |
| // sub[i] is not a char or char class; |
| // emit char class for sub[start:i]... |
| if (i == start) { |
| // Nothing to do. |
| } else if (i == start+1) { |
| sub[out++] = sub[start]; |
| } else { |
| // Make new char class. |
| CharClassBuilder ccb; |
| for (int j = start; j < i; j++) { |
| Regexp* re = sub[j]; |
| if (re->op() == kRegexpCharClass) { |
| CharClass* cc = re->cc(); |
| for (CharClass::iterator it = cc->begin(); it != cc->end(); ++it) |
| ccb.AddRange(it->lo, it->hi); |
| } else if (re->op() == kRegexpLiteral) { |
| ccb.AddRangeFlags(re->rune(), re->rune(), re->parse_flags()); |
| } else { |
| LOG(DFATAL) << "RE2: unexpected op: " << re->op() << " " |
| << re->ToString(); |
| } |
| re->Decref(); |
| } |
| sub[out++] = NewCharClass(ccb.GetCharClass(), altflags); |
| } |
| |
| // ... and then emit sub[i]. |
| if (i < n) |
| sub[out++] = sub[i]; |
| start = i+1; |
| } |
| n = out; |
| |
| // Round 4: Collapse runs of empty matches into single empty match. |
| start = 0; |
| out = 0; |
| for (int i = 0; i < n; i++) { |
| if (i + 1 < n && |
| sub[i]->op() == kRegexpEmptyMatch && |
| sub[i+1]->op() == kRegexpEmptyMatch) { |
| sub[i]->Decref(); |
| continue; |
| } |
| sub[out++] = sub[i]; |
| } |
| n = out; |
| |
| return n; |
| } |
| |
| // Collapse the regexps on top of the stack, down to the |
| // first marker, into a new op node (op == kRegexpAlternate |
| // or op == kRegexpConcat). |
| void Regexp::ParseState::DoCollapse(RegexpOp op) { |
| // Scan backward to marker, counting children of composite. |
| int n = 0; |
| Regexp* next = NULL; |
| Regexp* sub; |
| for (sub = stacktop_; sub != NULL && !IsMarker(sub->op()); sub = next) { |
| next = sub->down_; |
| if (sub->op_ == op) |
| n += sub->nsub_; |
| else |
| n++; |
| } |
| |
| // If there's just one child, leave it alone. |
| // (Concat of one thing is that one thing; alternate of one thing is same.) |
| if (stacktop_ != NULL && stacktop_->down_ == next) |
| return; |
| |
| // Construct op (alternation or concatenation), flattening op of op. |
| Regexp** subs = new Regexp*[n]; |
| next = NULL; |
| int i = n; |
| for (sub = stacktop_; sub != NULL && !IsMarker(sub->op()); sub = next) { |
| next = sub->down_; |
| if (sub->op_ == op) { |
| Regexp** sub_subs = sub->sub(); |
| for (int k = sub->nsub_ - 1; k >= 0; k--) |
| subs[--i] = sub_subs[k]->Incref(); |
| sub->Decref(); |
| } else { |
| subs[--i] = FinishRegexp(sub); |
| } |
| } |
| |
| Regexp* re = ConcatOrAlternate(op, subs, n, flags_, true); |
| delete[] subs; |
| re->simple_ = re->ComputeSimple(); |
| re->down_ = next; |
| stacktop_ = re; |
| } |
| |
| // Finishes the current concatenation, |
| // collapsing it into a single regexp on the stack. |
| void Regexp::ParseState::DoConcatenation() { |
| Regexp* r1 = stacktop_; |
| if (r1 == NULL || IsMarker(r1->op())) { |
| // empty concatenation is special case |
| Regexp* re = new Regexp(kRegexpEmptyMatch, flags_); |
| PushRegexp(re); |
| } |
| DoCollapse(kRegexpConcat); |
| } |
| |
| // Finishes the current alternation, |
| // collapsing it to a single regexp on the stack. |
| void Regexp::ParseState::DoAlternation() { |
| DoVerticalBar(); |
| // Now stack top is kVerticalBar. |
| Regexp* r1 = stacktop_; |
| stacktop_ = r1->down_; |
| r1->Decref(); |
| DoCollapse(kRegexpAlternate); |
| } |
| |
| // Incremental conversion of concatenated literals into strings. |
| // If top two elements on stack are both literal or string, |
| // collapse into single string. |
| // Don't walk down the stack -- the parser calls this frequently |
| // enough that below the bottom two is known to be collapsed. |
| // Only called when another regexp is about to be pushed |
| // on the stack, so that the topmost literal is not being considered. |
| // (Otherwise ab* would turn into (ab)*.) |
| // If r >= 0, consider pushing a literal r on the stack. |
| // Return whether that happened. |
| bool Regexp::ParseState::MaybeConcatString(int r, ParseFlags flags) { |
| Regexp* re1; |
| Regexp* re2; |
| if ((re1 = stacktop_) == NULL || (re2 = re1->down_) == NULL) |
| return false; |
| |
| if (re1->op_ != kRegexpLiteral && re1->op_ != kRegexpLiteralString) |
| return false; |
| if (re2->op_ != kRegexpLiteral && re2->op_ != kRegexpLiteralString) |
| return false; |
| if ((re1->parse_flags_ & FoldCase) != (re2->parse_flags_ & FoldCase)) |
| return false; |
| |
| if (re2->op_ == kRegexpLiteral) { |
| // convert into string |
| Rune rune = re2->rune_; |
| re2->op_ = kRegexpLiteralString; |
| re2->nrunes_ = 0; |
| re2->runes_ = NULL; |
| re2->AddRuneToString(rune); |
| } |
| |
| // push re1 into re2. |
| if (re1->op_ == kRegexpLiteral) { |
| re2->AddRuneToString(re1->rune_); |
| } else { |
| for (int i = 0; i < re1->nrunes_; i++) |
| re2->AddRuneToString(re1->runes_[i]); |
| re1->nrunes_ = 0; |
| delete[] re1->runes_; |
| re1->runes_ = NULL; |
| } |
| |
| // reuse re1 if possible |
| if (r >= 0) { |
| re1->op_ = kRegexpLiteral; |
| re1->rune_ = r; |
| re1->parse_flags_ = flags; |
| return true; |
| } |
| |
| stacktop_ = re2; |
| re1->Decref(); |
| return false; |
| } |
| |
| // Lexing routines. |
| |
| // Parses a decimal integer, storing it in *n. |
| // Sets *s to span the remainder of the string. |
| // Sets *out_re to the regexp for the class. |
| static bool ParseInteger(StringPiece* s, int* np) { |
| if (s->size() == 0 || !isdigit((*s)[0] & 0xFF)) |
| return false; |
| // Disallow leading zeros. |
| if (s->size() >= 2 && (*s)[0] == '0' && isdigit((*s)[1] & 0xFF)) |
| return false; |
| int n = 0; |
| int c; |
| while (s->size() > 0 && isdigit(c = (*s)[0] & 0xFF)) { |
| // Avoid overflow. |
| if (n >= 100000000) |
| return false; |
| n = n*10 + c - '0'; |
| s->remove_prefix(1); // digit |
| } |
| *np = n; |
| return true; |
| } |
| |
| // Parses a repetition suffix like {1,2} or {2} or {2,}. |
| // Sets *s to span the remainder of the string on success. |
| // Sets *lo and *hi to the given range. |
| // In the case of {2,}, the high number is unbounded; |
| // sets *hi to -1 to signify this. |
| // {,2} is NOT a valid suffix. |
| // The Maybe in the name signifies that the regexp parse |
| // doesn't fail even if ParseRepetition does, so the StringPiece |
| // s must NOT be edited unless MaybeParseRepetition returns true. |
| static bool MaybeParseRepetition(StringPiece* sp, int* lo, int* hi) { |
| StringPiece s = *sp; |
| if (s.size() == 0 || s[0] != '{') |
| return false; |
| s.remove_prefix(1); // '{' |
| if (!ParseInteger(&s, lo)) |
| return false; |
| if (s.size() == 0) |
| return false; |
| if (s[0] == ',') { |
| s.remove_prefix(1); // ',' |
| if (s.size() == 0) |
| return false; |
| if (s[0] == '}') { |
| // {2,} means at least 2 |
| *hi = -1; |
| } else { |
| // {2,4} means 2, 3, or 4. |
| if (!ParseInteger(&s, hi)) |
| return false; |
| } |
| } else { |
| // {2} means exactly two |
| *hi = *lo; |
| } |
| if (s.size() == 0 || s[0] != '}') |
| return false; |
| s.remove_prefix(1); // '}' |
| *sp = s; |
| return true; |
| } |
| |
| // Removes the next Rune from the StringPiece and stores it in *r. |
| // Returns number of bytes removed from sp. |
| // Behaves as though there is a terminating NUL at the end of sp. |
| // Argument order is backwards from usual Google style |
| // but consistent with chartorune. |
| static int StringPieceToRune(Rune *r, StringPiece *sp, RegexpStatus* status) { |
| int n; |
| if (fullrune(sp->data(), sp->size())) { |
| n = chartorune(r, sp->data()); |
| if (!(n == 1 && *r == Runeerror)) { // no decoding error |
| sp->remove_prefix(n); |
| return n; |
| } |
| } |
| |
| status->set_code(kRegexpBadUTF8); |
| status->set_error_arg(NULL); |
| return -1; |
| } |
| |
| // Return whether name is valid UTF-8. |
| // If not, set status to kRegexpBadUTF8. |
| static bool IsValidUTF8(const StringPiece& s, RegexpStatus* status) { |
| StringPiece t = s; |
| Rune r; |
| while (t.size() > 0) { |
| if (StringPieceToRune(&r, &t, status) < 0) |
| return false; |
| } |
| return true; |
| } |
| |
| // Is c a hex digit? |
| static int IsHex(int c) { |
| return ('0' <= c && c <= '9') || |
| ('A' <= c && c <= 'F') || |
| ('a' <= c && c <= 'f'); |
| } |
| |
| // Convert hex digit to value. |
| static int UnHex(int c) { |
| if ('0' <= c && c <= '9') |
| return c - '0'; |
| if ('A' <= c && c <= 'F') |
| return c - 'A' + 10; |
| if ('a' <= c && c <= 'f') |
| return c - 'a' + 10; |
| LOG(DFATAL) << "Bad hex digit " << c; |
| return 0; |
| } |
| |
| // Parse an escape sequence (e.g., \n, \{). |
| // Sets *s to span the remainder of the string. |
| // Sets *rp to the named character. |
| static bool ParseEscape(StringPiece* s, Rune* rp, |
| RegexpStatus* status, int rune_max) { |
| const char* begin = s->begin(); |
| if (s->size() < 1 || (*s)[0] != '\\') { |
| // Should not happen - caller always checks. |
| status->set_code(kRegexpInternalError); |
| status->set_error_arg(NULL); |
| return false; |
| } |
| if (s->size() < 2) { |
| status->set_code(kRegexpTrailingBackslash); |
| status->set_error_arg(NULL); |
| return false; |
| } |
| Rune c, c1; |
| s->remove_prefix(1); // backslash |
| if (StringPieceToRune(&c, s, status) < 0) |
| return false; |
| int code; |
| switch (c) { |
| default: |
| if (c < Runeself && !isalpha(c) && !isdigit(c)) { |
| // Escaped non-word characters are always themselves. |
| // PCRE is not quite so rigorous: it accepts things like |
| // \q, but we don't. We once rejected \_, but too many |
| // programs and people insist on using it, so allow \_. |
| *rp = c; |
| return true; |
| } |
| goto BadEscape; |
| |
| // Octal escapes. |
| case '1': |
| case '2': |
| case '3': |
| case '4': |
| case '5': |
| case '6': |
| case '7': |
| // Single non-zero octal digit is a backreference; not supported. |
| if (s->size() == 0 || (*s)[0] < '0' || (*s)[0] > '7') |
| goto BadEscape; |
| // fall through |
| case '0': |
| // consume up to three octal digits; already have one. |
| code = c - '0'; |
| if (s->size() > 0 && '0' <= (c = (*s)[0]) && c <= '7') { |
| code = code * 8 + c - '0'; |
| s->remove_prefix(1); // digit |
| if (s->size() > 0) { |
| c = (*s)[0]; |
| if ('0' <= c && c <= '7') { |
| code = code * 8 + c - '0'; |
| s->remove_prefix(1); // digit |
| } |
| } |
| } |
| *rp = code; |
| return true; |
| |
| // Hexadecimal escapes |
| case 'x': |
| if (s->size() == 0) |
| goto BadEscape; |
| if (StringPieceToRune(&c, s, status) < 0) |
| return false; |
| if (c == '{') { |
| // Any number of digits in braces. |
| // Update n as we consume the string, so that |
| // the whole thing gets shown in the error message. |
| // Perl accepts any text at all; it ignores all text |
| // after the first non-hex digit. We require only hex digits, |
| // and at least one. |
| if (StringPieceToRune(&c, s, status) < 0) |
| return false; |
| int nhex = 0; |
| code = 0; |
| while (IsHex(c)) { |
| nhex++; |
| code = code * 16 + UnHex(c); |
| if (code > rune_max) |
| goto BadEscape; |
| if (s->size() == 0) |
| goto BadEscape; |
| if (StringPieceToRune(&c, s, status) < 0) |
| return false; |
| } |
| if (c != '}' || nhex == 0) |
| goto BadEscape; |
| *rp = code; |
| return true; |
| } |
| // Easy case: two hex digits. |
| if (s->size() == 0) |
| goto BadEscape; |
| if (StringPieceToRune(&c1, s, status) < 0) |
| return false; |
| if (!IsHex(c) || !IsHex(c1)) |
| goto BadEscape; |
| *rp = UnHex(c) * 16 + UnHex(c1); |
| return true; |
| |
| // C escapes. |
| case 'n': |
| *rp = '\n'; |
| return true; |
| case 'r': |
| *rp = '\r'; |
| return true; |
| case 't': |
| *rp = '\t'; |
| return true; |
| |
| // Less common C escapes. |
| case 'a': |
| *rp = '\a'; |
| return true; |
| case 'f': |
| *rp = '\f'; |
| return true; |
| case 'v': |
| *rp = '\v'; |
| return true; |
| |
| // This code is disabled to avoid misparsing |
| // the Perl word-boundary \b as a backspace |
| // when in POSIX regexp mode. Surprisingly, |
| // in Perl, \b means word-boundary but [\b] |
| // means backspace. We don't support that: |
| // if you want a backspace embed a literal |
| // backspace character or use \x08. |
| // |
| // case 'b': |
| // *rp = '\b'; |
| // return true; |
| } |
| |
| LOG(DFATAL) << "Not reached in ParseEscape."; |
| |
| BadEscape: |
| // Unrecognized escape sequence. |
| status->set_code(kRegexpBadEscape); |
| status->set_error_arg(StringPiece(begin, s->data() - begin)); |
| return false; |
| } |
| |
| // Add a range to the character class, but exclude newline if asked. |
| // Also handle case folding. |
| void CharClassBuilder::AddRangeFlags( |
| Rune lo, Rune hi, Regexp::ParseFlags parse_flags) { |
| |
| // Take out \n if the flags say so. |
| bool cutnl = !(parse_flags & Regexp::ClassNL) || |
| (parse_flags & Regexp::NeverNL); |
| if (cutnl && lo <= '\n' && '\n' <= hi) { |
| if (lo < '\n') |
| AddRangeFlags(lo, '\n' - 1, parse_flags); |
| if (hi > '\n') |
| AddRangeFlags('\n' + 1, hi, parse_flags); |
| return; |
| } |
| |
| // If folding case, add fold-equivalent characters too. |
| if (parse_flags & Regexp::FoldCase) |
| AddFoldedRange(this, lo, hi, 0); |
| else |
| AddRange(lo, hi); |
| } |
| |
| // Look for a group with the given name. |
| static UGroup* LookupGroup(const StringPiece& name, |
| UGroup *groups, int ngroups) { |
| // Simple name lookup. |
| for (int i = 0; i < ngroups; i++) |
| if (StringPiece(groups[i].name) == name) |
| return &groups[i]; |
| return NULL; |
| } |
| |
| // Fake UGroup containing all Runes |
| static URange16 any16[] = { { 0, 65535 } }; |
| static URange32 any32[] = { { 65536, Runemax } }; |
| static UGroup anygroup = { "Any", +1, any16, 1, any32, 1 }; |
| |
| // Look for a POSIX group with the given name (e.g., "[:^alpha:]") |
| static UGroup* LookupPosixGroup(const StringPiece& name) { |
| return LookupGroup(name, posix_groups, num_posix_groups); |
| } |
| |
| static UGroup* LookupPerlGroup(const StringPiece& name) { |
| return LookupGroup(name, perl_groups, num_perl_groups); |
| } |
| |
| // Look for a Unicode group with the given name (e.g., "Han") |
| static UGroup* LookupUnicodeGroup(const StringPiece& name) { |
| // Special case: "Any" means any. |
| if (name == StringPiece("Any")) |
| return &anygroup; |
| return LookupGroup(name, unicode_groups, num_unicode_groups); |
| } |
| |
| // Add a UGroup or its negation to the character class. |
| static void AddUGroup(CharClassBuilder *cc, UGroup *g, int sign, |
| Regexp::ParseFlags parse_flags) { |
| if (sign == +1) { |
| for (int i = 0; i < g->nr16; i++) { |
| cc->AddRangeFlags(g->r16[i].lo, g->r16[i].hi, parse_flags); |
| } |
| for (int i = 0; i < g->nr32; i++) { |
| cc->AddRangeFlags(g->r32[i].lo, g->r32[i].hi, parse_flags); |
| } |
| } else { |
| if (parse_flags & Regexp::FoldCase) { |
| // Normally adding a case-folded group means |
| // adding all the extra fold-equivalent runes too. |
| // But if we're adding the negation of the group, |
| // we have to exclude all the runes that are fold-equivalent |
| // to what's already missing. Too hard, so do in two steps. |
| CharClassBuilder ccb1; |
| AddUGroup(&ccb1, g, +1, parse_flags); |
| // If the flags say to take out \n, put it in, so that negating will take it out. |
| // Normally AddRangeFlags does this, but we're bypassing AddRangeFlags. |
| bool cutnl = !(parse_flags & Regexp::ClassNL) || |
| (parse_flags & Regexp::NeverNL); |
| if (cutnl) { |
| ccb1.AddRange('\n', '\n'); |
| } |
| ccb1.Negate(); |
| cc->AddCharClass(&ccb1); |
| return; |
| } |
| int next = 0; |
| for (int i = 0; i < g->nr16; i++) { |
| if (next < g->r16[i].lo) |
| cc->AddRangeFlags(next, g->r16[i].lo - 1, parse_flags); |
| next = g->r16[i].hi + 1; |
| } |
| for (int i = 0; i < g->nr32; i++) { |
| if (next < g->r32[i].lo) |
| cc->AddRangeFlags(next, g->r32[i].lo - 1, parse_flags); |
| next = g->r32[i].hi + 1; |
| } |
| if (next <= Runemax) |
| cc->AddRangeFlags(next, Runemax, parse_flags); |
| } |
| } |
| |
| // Maybe parse a Perl character class escape sequence. |
| // Only recognizes the Perl character classes (\d \s \w \D \S \W), |
| // not the Perl empty-string classes (\b \B \A \Z \z). |
| // On success, sets *s to span the remainder of the string |
| // and returns the corresponding UGroup. |
| // The StringPiece must *NOT* be edited unless the call succeeds. |
| UGroup* MaybeParsePerlCCEscape(StringPiece* s, Regexp::ParseFlags parse_flags) { |
| if (!(parse_flags & Regexp::PerlClasses)) |
| return NULL; |
| if (s->size() < 2 || (*s)[0] != '\\') |
| return NULL; |
| // Could use StringPieceToRune, but there aren't |
| // any non-ASCII Perl group names. |
| StringPiece name(s->begin(), 2); |
| UGroup *g = LookupPerlGroup(name); |
| if (g == NULL) |
| return NULL; |
| s->remove_prefix(name.size()); |
| return g; |
| } |
| |
| enum ParseStatus { |
| kParseOk, // Did some parsing. |
| kParseError, // Found an error. |
| kParseNothing, // Decided not to parse. |
| }; |
| |
| // Maybe parses a Unicode character group like \p{Han} or \P{Han} |
| // (the latter is a negated group). |
| ParseStatus ParseUnicodeGroup(StringPiece* s, Regexp::ParseFlags parse_flags, |
| CharClassBuilder *cc, |
| RegexpStatus* status) { |
| // Decide whether to parse. |
| if (!(parse_flags & Regexp::UnicodeGroups)) |
| return kParseNothing; |
| if (s->size() < 2 || (*s)[0] != '\\') |
| return kParseNothing; |
| Rune c = (*s)[1]; |
| if (c != 'p' && c != 'P') |
| return kParseNothing; |
| |
| // Committed to parse. Results: |
| int sign = +1; // -1 = negated char class |
| if (c == 'P') |
| sign = -1; |
| StringPiece seq = *s; // \p{Han} or \pL |
| StringPiece name; // Han or L |
| s->remove_prefix(2); // '\\', 'p' |
| |
| if (!StringPieceToRune(&c, s, status)) |
| return kParseError; |
| if (c != '{') { |
| // Name is the bit of string we just skipped over for c. |
| const char* p = seq.begin() + 2; |
| name = StringPiece(p, s->begin() - p); |
| } else { |
| // Name is in braces. Look for closing } |
| int end = s->find('}', 0); |
| if (end == s->npos) { |
| if (!IsValidUTF8(seq, status)) |
| return kParseError; |
| status->set_code(kRegexpBadCharRange); |
| status->set_error_arg(seq); |
| return kParseError; |
| } |
| name = StringPiece(s->begin(), end); // without '}' |
| s->remove_prefix(end + 1); // with '}' |
| if (!IsValidUTF8(name, status)) |
| return kParseError; |
| } |
| |
| // Chop seq where s now begins. |
| seq = StringPiece(seq.begin(), s->begin() - seq.begin()); |
| |
| // Look up group |
| if (name.size() > 0 && name[0] == '^') { |
| sign = -sign; |
| name.remove_prefix(1); // '^' |
| } |
| UGroup *g = LookupUnicodeGroup(name); |
| if (g == NULL) { |
| status->set_code(kRegexpBadCharRange); |
| status->set_error_arg(seq); |
| return kParseError; |
| } |
| |
| AddUGroup(cc, g, sign, parse_flags); |
| return kParseOk; |
| } |
| |
| // Parses a character class name like [:alnum:]. |
| // Sets *s to span the remainder of the string. |
| // Adds the ranges corresponding to the class to ranges. |
| static ParseStatus ParseCCName(StringPiece* s, Regexp::ParseFlags parse_flags, |
| CharClassBuilder *cc, |
| RegexpStatus* status) { |
| // Check begins with [: |
| const char* p = s->data(); |
| const char* ep = s->data() + s->size(); |
| if (ep - p < 2 || p[0] != '[' || p[1] != ':') |
| return kParseNothing; |
| |
| // Look for closing :]. |
| const char* q; |
| for (q = p+2; q <= ep-2 && (*q != ':' || *(q+1) != ']'); q++) |
| ; |
| |
| // If no closing :], then ignore. |
| if (q > ep-2) |
| return kParseNothing; |
| |
| // Got it. Check that it's valid. |
| q += 2; |
| StringPiece name(p, q-p); |
| |
| UGroup *g = LookupPosixGroup(name); |
| if (g == NULL) { |
| status->set_code(kRegexpBadCharRange); |
| status->set_error_arg(name); |
| return kParseError; |
| } |
| |
| s->remove_prefix(name.size()); |
| AddUGroup(cc, g, g->sign, parse_flags); |
| return kParseOk; |
| } |
| |
| // Parses a character inside a character class. |
| // There are fewer special characters here than in the rest of the regexp. |
| // Sets *s to span the remainder of the string. |
| // Sets *rp to the character. |
| bool Regexp::ParseState::ParseCCCharacter(StringPiece* s, Rune *rp, |
| const StringPiece& whole_class, |
| RegexpStatus* status) { |
| if (s->size() == 0) { |
| status->set_code(kRegexpMissingBracket); |
| status->set_error_arg(whole_class); |
| return false; |
| } |
| |
| // Allow regular escape sequences even though |
| // many need not be escaped in this context. |
| if (s->size() >= 1 && (*s)[0] == '\\') |
| return ParseEscape(s, rp, status, rune_max_); |
| |
| // Otherwise take the next rune. |
| return StringPieceToRune(rp, s, status) >= 0; |
| } |
| |
| // Parses a character class character, or, if the character |
| // is followed by a hyphen, parses a character class range. |
| // For single characters, rr->lo == rr->hi. |
| // Sets *s to span the remainder of the string. |
| // Sets *rp to the character. |
| bool Regexp::ParseState::ParseCCRange(StringPiece* s, RuneRange* rr, |
| const StringPiece& whole_class, |
| RegexpStatus* status) { |
| StringPiece os = *s; |
| if (!ParseCCCharacter(s, &rr->lo, whole_class, status)) |
| return false; |
| // [a-] means (a|-), so check for final ]. |
| if (s->size() >= 2 && (*s)[0] == '-' && (*s)[1] != ']') { |
| s->remove_prefix(1); // '-' |
| if (!ParseCCCharacter(s, &rr->hi, whole_class, status)) |
| return false; |
| if (rr->hi < rr->lo) { |
| status->set_code(kRegexpBadCharRange); |
| status->set_error_arg(StringPiece(os.data(), s->data() - os.data())); |
| return false; |
| } |
| } else { |
| rr->hi = rr->lo; |
| } |
| return true; |
| } |
| |
| // Parses a possibly-negated character class expression like [^abx-z[:digit:]]. |
| // Sets *s to span the remainder of the string. |
| // Sets *out_re to the regexp for the class. |
| bool Regexp::ParseState::ParseCharClass(StringPiece* s, |
| Regexp** out_re, |
| RegexpStatus* status) { |
| StringPiece whole_class = *s; |
| if (s->size() == 0 || (*s)[0] != '[') { |
| // Caller checked this. |
| status->set_code(kRegexpInternalError); |
| status->set_error_arg(NULL); |
| return false; |
| } |
| bool negated = false; |
| Regexp* re = new Regexp(kRegexpCharClass, flags_ & ~FoldCase); |
| re->ccb_ = new CharClassBuilder; |
| s->remove_prefix(1); // '[' |
| if (s->size() > 0 && (*s)[0] == '^') { |
| s->remove_prefix(1); // '^' |
| negated = true; |
| if (!(flags_ & ClassNL) || (flags_ & NeverNL)) { |
| // If NL can't match implicitly, then pretend |
| // negated classes include a leading \n. |
| re->ccb_->AddRange('\n', '\n'); |
| } |
| } |
| bool first = true; // ] is okay as first char in class |
| while (s->size() > 0 && ((*s)[0] != ']' || first)) { |
| // - is only okay unescaped as first or last in class. |
| // Except that Perl allows - anywhere. |
| if ((*s)[0] == '-' && !first && !(flags_&PerlX) && |
| (s->size() == 1 || (*s)[1] != ']')) { |
| StringPiece t = *s; |
| t.remove_prefix(1); // '-' |
| Rune r; |
| int n = StringPieceToRune(&r, &t, status); |
| if (n < 0) { |
| re->Decref(); |
| return false; |
| } |
| status->set_code(kRegexpBadCharRange); |
| status->set_error_arg(StringPiece(s->data(), 1+n)); |
| re->Decref(); |
| return false; |
| } |
| first = false; |
| |
| // Look for [:alnum:] etc. |
| if (s->size() > 2 && (*s)[0] == '[' && (*s)[1] == ':') { |
| switch (ParseCCName(s, flags_, re->ccb_, status)) { |
| case kParseOk: |
| continue; |
| case kParseError: |
| re->Decref(); |
| return false; |
| case kParseNothing: |
| break; |
| } |
| } |
| |
| // Look for Unicode character group like \p{Han} |
| if (s->size() > 2 && |
| (*s)[0] == '\\' && |
| ((*s)[1] == 'p' || (*s)[1] == 'P')) { |
| switch (ParseUnicodeGroup(s, flags_, re->ccb_, status)) { |
| case kParseOk: |
| continue; |
| case kParseError: |
| re->Decref(); |
| return false; |
| case kParseNothing: |
| break; |
| } |
| } |
| |
| // Look for Perl character class symbols (extension). |
| UGroup *g = MaybeParsePerlCCEscape(s, flags_); |
| if (g != NULL) { |
| AddUGroup(re->ccb_, g, g->sign, flags_); |
| continue; |
| } |
| |
| // Otherwise assume single character or simple range. |
| RuneRange rr; |
| if (!ParseCCRange(s, &rr, whole_class, status)) { |
| re->Decref(); |
| return false; |
| } |
| // AddRangeFlags is usually called in response to a class like |
| // \p{Foo} or [[:foo:]]; for those, it filters \n out unless |
| // Regexp::ClassNL is set. In an explicit range or singleton |
| // like we just parsed, we do not filter \n out, so set ClassNL |
| // in the flags. |
| re->ccb_->AddRangeFlags(rr.lo, rr.hi, flags_ | Regexp::ClassNL); |
| } |
| if (s->size() == 0) { |
| status->set_code(kRegexpMissingBracket); |
| status->set_error_arg(whole_class); |
| re->Decref(); |
| return false; |
| } |
| s->remove_prefix(1); // ']' |
| |
| if (negated) |
| re->ccb_->Negate(); |
| re->ccb_->RemoveAbove(rune_max_); |
| |
| *out_re = re; |
| return true; |
| } |
| |
| // Is this a valid capture name? [A-Za-z0-9_]+ |
| // PCRE limits names to 32 bytes. |
| // Python rejects names starting with digits. |
| // We don't enforce either of those. |
| static bool IsValidCaptureName(const StringPiece& name) { |
| if (name.size() == 0) |
| return false; |
| for (int i = 0; i < name.size(); i++) { |
| int c = name[i]; |
| if (('0' <= c && c <= '9') || |
| ('a' <= c && c <= 'z') || |
| ('A' <= c && c <= 'Z') || |
| c == '_') |
| continue; |
| return false; |
| } |
| return true; |
| } |
| |
| // Parses a Perl flag setting or non-capturing group or both, |
| // like (?i) or (?: or (?i:. Removes from s, updates parse state. |
| // The caller must check that s begins with "(?". |
| // Returns true on success. If the Perl flag is not |
| // well-formed or not supported, sets status_ and returns false. |
| bool Regexp::ParseState::ParsePerlFlags(StringPiece* s) { |
| StringPiece t = *s; |
| |
| // Caller is supposed to check this. |
| if (!(flags_ & PerlX) || t.size() < 2 || t[0] != '(' || t[1] != '?') { |
| LOG(DFATAL) << "Bad call to ParseState::ParsePerlFlags"; |
| status_->set_code(kRegexpInternalError); |
| return false; |
| } |
| |
| t.remove_prefix(2); // "(?" |
| |
| // Check for named captures, first introduced in Python's regexp library. |
| // As usual, there are three slightly different syntaxes: |
| // |
| // (?P<name>expr) the original, introduced by Python |
| // (?<name>expr) the .NET alteration, adopted by Perl 5.10 |
| // (?'name'expr) another .NET alteration, adopted by Perl 5.10 |
| // |
| // Perl 5.10 gave in and implemented the Python version too, |
| // but they claim that the last two are the preferred forms. |
| // PCRE and languages based on it (specifically, PHP and Ruby) |
| // support all three as well. EcmaScript 4 uses only the Python form. |
| // |
| // In both the open source world (via Code Search) and the |
| // Google source tree, (?P<expr>name) is the dominant form, |
| // so that's the one we implement. One is enough. |
| if (t.size() > 2 && t[0] == 'P' && t[1] == '<') { |
| // Pull out name. |
| int end = t.find('>', 2); |
| if (end == t.npos) { |
| if (!IsValidUTF8(*s, status_)) |
| return false; |
| status_->set_code(kRegexpBadNamedCapture); |
| status_->set_error_arg(*s); |
| return false; |
| } |
| |
| // t is "P<name>...", t[end] == '>' |
| StringPiece capture(t.begin()-2, end+3); // "(?P<name>" |
| StringPiece name(t.begin()+2, end-2); // "name" |
| if (!IsValidUTF8(name, status_)) |
| return false; |
| if (!IsValidCaptureName(name)) { |
| status_->set_code(kRegexpBadNamedCapture); |
| status_->set_error_arg(capture); |
| return false; |
| } |
| |
| if (!DoLeftParen(name)) { |
| // DoLeftParen's failure set status_. |
| return false; |
| } |
| |
| s->remove_prefix(capture.end() - s->begin()); |
| return true; |
| } |
| |
| bool negated = false; |
| bool sawflags = false; |
| int nflags = flags_; |
| Rune c; |
| for (bool done = false; !done; ) { |
| if (t.size() == 0) |
| goto BadPerlOp; |
| if (StringPieceToRune(&c, &t, status_) < 0) |
| return false; |
| switch (c) { |
| default: |
| goto BadPerlOp; |
| |
| // Parse flags. |
| case 'i': |
| sawflags = true; |
| if (negated) |
| nflags &= ~FoldCase; |
| else |
| nflags |= FoldCase; |
| break; |
| |
| case 'm': // opposite of our OneLine |
| sawflags = true; |
| if (negated) |
| nflags |= OneLine; |
| else |
| nflags &= ~OneLine; |
| break; |
| |
| case 's': |
| sawflags = true; |
| if (negated) |
| nflags &= ~DotNL; |
| else |
| nflags |= DotNL; |
| break; |
| |
| case 'U': |
| sawflags = true; |
| if (negated) |
| nflags &= ~NonGreedy; |
| else |
| nflags |= NonGreedy; |
| break; |
| |
| // Negation |
| case '-': |
| if (negated) |
| goto BadPerlOp; |
| negated = true; |
| sawflags = false; |
| break; |
| |
| // Open new group. |
| case ':': |
| if (!DoLeftParenNoCapture()) { |
| // DoLeftParenNoCapture's failure set status_. |
| return false; |
| } |
| done = true; |
| break; |
| |
| // Finish flags. |
| case ')': |
| done = true; |
| break; |
| } |
| } |
| |
| if (negated && !sawflags) |
| goto BadPerlOp; |
| |
| flags_ = static_cast<Regexp::ParseFlags>(nflags); |
| *s = t; |
| return true; |
| |
| BadPerlOp: |
| status_->set_code(kRegexpBadPerlOp); |
| status_->set_error_arg(StringPiece(s->begin(), t.begin() - s->begin())); |
| return false; |
| } |
| |
| // Converts latin1 (assumed to be encoded as Latin1 bytes) |
| // into UTF8 encoding in string. |
| // Can't use EncodingUtils::EncodeLatin1AsUTF8 because it is |
| // deprecated and because it rejects code points 0x80-0x9F. |
| void ConvertLatin1ToUTF8(const StringPiece& latin1, string* utf) { |
| char buf[UTFmax]; |
| |
| utf->clear(); |
| for (int i = 0; i < latin1.size(); i++) { |
| Rune r = latin1[i] & 0xFF; |
| int n = runetochar(buf, &r); |
| utf->append(buf, n); |
| } |
| } |
| |
| // Parses the regular expression given by s, |
| // returning the corresponding Regexp tree. |
| // The caller must Decref the return value when done with it. |
| // Returns NULL on error. |
| Regexp* Regexp::Parse(const StringPiece& s, ParseFlags global_flags, |
| RegexpStatus* status) { |
| // Make status non-NULL (easier on everyone else). |
| RegexpStatus xstatus; |
| if (status == NULL) |
| status = &xstatus; |
| |
| ParseState ps(global_flags, s, status); |
| StringPiece t = s; |
| |
| // Convert regexp to UTF-8 (easier on the rest of the parser). |
| if (global_flags & Latin1) { |
| string* tmp = new string; |
| ConvertLatin1ToUTF8(t, tmp); |
| status->set_tmp(tmp); |
| t = *tmp; |
| } |
| |
| if (global_flags & Literal) { |
| // Special parse loop for literal string. |
| while (t.size() > 0) { |
| Rune r; |
| if (StringPieceToRune(&r, &t, status) < 0) |
| return NULL; |
| if (!ps.PushLiteral(r)) |
| return NULL; |
| } |
| return ps.DoFinish(); |
| } |
| |
| StringPiece lastunary = NULL; |
| while (t.size() > 0) { |
| StringPiece isunary = NULL; |
| switch (t[0]) { |
| default: { |
| Rune r; |
| if (StringPieceToRune(&r, &t, status) < 0) |
| return NULL; |
| if (!ps.PushLiteral(r)) |
| return NULL; |
| break; |
| } |
| |
| case '(': |
| // "(?" introduces Perl escape. |
| if ((ps.flags() & PerlX) && (t.size() >= 2 && t[1] == '?')) { |
| // Flag changes and non-capturing groups. |
| if (!ps.ParsePerlFlags(&t)) |
| return NULL; |
| break; |
| } |
| if (ps.flags() & NeverCapture) { |
| if (!ps.DoLeftParenNoCapture()) |
| return NULL; |
| } else { |
| if (!ps.DoLeftParen(NULL)) |
| return NULL; |
| } |
| t.remove_prefix(1); // '(' |
| break; |
| |
| case '|': |
| if (!ps.DoVerticalBar()) |
| return NULL; |
| t.remove_prefix(1); // '|' |
| break; |
| |
| case ')': |
| if (!ps.DoRightParen()) |
| return NULL; |
| t.remove_prefix(1); // ')' |
| break; |
| |
| case '^': // Beginning of line. |
| if (!ps.PushCarat()) |
| return NULL; |
| t.remove_prefix(1); // '^' |
| break; |
| |
| case '$': // End of line. |
| if (!ps.PushDollar()) |
| return NULL; |
| t.remove_prefix(1); // '$' |
| break; |
| |
| case '.': // Any character (possibly except newline). |
| if (!ps.PushDot()) |
| return NULL; |
| t.remove_prefix(1); // '.' |
| break; |
| |
| case '[': { // Character class. |
| Regexp* re; |
| if (!ps.ParseCharClass(&t, &re, status)) |
| return NULL; |
| if (!ps.PushRegexp(re)) |
| return NULL; |
| break; |
| } |
| |
| case '*': { // Zero or more. |
| RegexpOp op; |
| op = kRegexpStar; |
| goto Rep; |
| case '+': // One or more. |
| op = kRegexpPlus; |
| goto Rep; |
| case '?': // Zero or one. |
| op = kRegexpQuest; |
| goto Rep; |
| Rep: |
| StringPiece opstr = t; |
| bool nongreedy = false; |
| t.remove_prefix(1); // '*' or '+' or '?' |
| if (ps.flags() & PerlX) { |
| if (t.size() > 0 && t[0] == '?') { |
| nongreedy = true; |
| t.remove_prefix(1); // '?' |
| } |
| if (lastunary.size() > 0) { |
| // In Perl it is not allowed to stack repetition operators: |
| // a** is a syntax error, not a double-star. |
| // (and a++ means something else entirely, which we don't support!) |
| status->set_code(kRegexpRepeatOp); |
| status->set_error_arg(StringPiece(lastunary.begin(), |
| t.begin() - lastunary.begin())); |
| return NULL; |
| } |
| } |
| opstr.set(opstr.data(), t.data() - opstr.data()); |
| if (!ps.PushRepeatOp(op, opstr, nongreedy)) |
| return NULL; |
| isunary = opstr; |
| break; |
| } |
| |
| case '{': { // Counted repetition. |
| int lo, hi; |
| StringPiece opstr = t; |
| if (!MaybeParseRepetition(&t, &lo, &hi)) { |
| // Treat like a literal. |
| if (!ps.PushLiteral('{')) |
| return NULL; |
| t.remove_prefix(1); // '{' |
| break; |
| } |
| bool nongreedy = false; |
| if (ps.flags() & PerlX) { |
| if (t.size() > 0 && t[0] == '?') { |
| nongreedy = true; |
| t.remove_prefix(1); // '?' |
| } |
| if (lastunary.size() > 0) { |
| // Not allowed to stack repetition operators. |
| status->set_code(kRegexpRepeatOp); |
| status->set_error_arg(StringPiece(lastunary.begin(), |
| t.begin() - lastunary.begin())); |
| return NULL; |
| } |
| } |
| opstr.set(opstr.data(), t.data() - opstr.data()); |
| if (!ps.PushRepetition(lo, hi, opstr, nongreedy)) |
| return NULL; |
| isunary = opstr; |
| break; |
| } |
| |
| case '\\': { // Escaped character or Perl sequence. |
| // \b and \B: word boundary or not |
| if ((ps.flags() & Regexp::PerlB) && |
| t.size() >= 2 && (t[1] == 'b' || t[1] == 'B')) { |
| if (!ps.PushWordBoundary(t[1] == 'b')) |
| return NULL; |
| t.remove_prefix(2); // '\\', 'b' |
| break; |
| } |
| |
| if ((ps.flags() & Regexp::PerlX) && t.size() >= 2) { |
| if (t[1] == 'A') { |
| if (!ps.PushSimpleOp(kRegexpBeginText)) |
| return NULL; |
| t.remove_prefix(2); // '\\', 'A' |
| break; |
| } |
| if (t[1] == 'z') { |
| if (!ps.PushSimpleOp(kRegexpEndText)) |
| return NULL; |
| t.remove_prefix(2); // '\\', 'z' |
| break; |
| } |
| // Do not recognize \Z, because this library can't |
| // implement the exact Perl/PCRE semantics. |
| // (This library treats "(?-m)$" as \z, even though |
| // in Perl and PCRE it is equivalent to \Z.) |
| |
| if (t[1] == 'C') { // \C: any byte [sic] |
| if (!ps.PushSimpleOp(kRegexpAnyByte)) |
| return NULL; |
| t.remove_prefix(2); // '\\', 'C' |
| break; |
| } |
| |
| if (t[1] == 'Q') { // \Q ... \E: the ... is always literals |
| t.remove_prefix(2); // '\\', 'Q' |
| while (t.size() > 0) { |
| if (t.size() >= 2 && t[0] == '\\' && t[1] == 'E') { |
| t.remove_prefix(2); // '\\', 'E' |
| break; |
| } |
| Rune r; |
| if (StringPieceToRune(&r, &t, status) < 0) |
| return NULL; |
| if (!ps.PushLiteral(r)) |
| return NULL; |
| } |
| break; |
| } |
| } |
| |
| if (t.size() >= 2 && (t[1] == 'p' || t[1] == 'P')) { |
| Regexp* re = new Regexp(kRegexpCharClass, ps.flags() & ~FoldCase); |
| re->ccb_ = new CharClassBuilder; |
| switch (ParseUnicodeGroup(&t, ps.flags(), re->ccb_, status)) { |
| case kParseOk: |
| if (!ps.PushRegexp(re)) |
| return NULL; |
| goto Break2; |
| case kParseError: |
| re->Decref(); |
| return NULL; |
| case kParseNothing: |
| re->Decref(); |
| break; |
| } |
| } |
| |
| UGroup *g = MaybeParsePerlCCEscape(&t, ps.flags()); |
| if (g != NULL) { |
| Regexp* re = new Regexp(kRegexpCharClass, ps.flags() & ~FoldCase); |
| re->ccb_ = new CharClassBuilder; |
| AddUGroup(re->ccb_, g, g->sign, ps.flags()); |
| if (!ps.PushRegexp(re)) |
| return NULL; |
| break; |
| } |
| |
| Rune r; |
| if (!ParseEscape(&t, &r, status, ps.rune_max())) |
| return NULL; |
| if (!ps.PushLiteral(r)) |
| return NULL; |
| break; |
| } |
| } |
| Break2: |
| lastunary = isunary; |
| } |
| return ps.DoFinish(); |
| } |
| |
| } // namespace re2 |