Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(167)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: third_party/re2/re2/parse.cc

Issue 10575037: Include RE2 library (Closed) Base URL: svn://svn.chromium.org/chrome/trunk/src
Patch Set: Less intrusive fix for Android Created 8 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « third_party/re2/re2/onepass.cc ('k') | third_party/re2/re2/perl_groups.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: third_party/re2/re2/parse.cc
diff --git a/third_party/re2/re2/parse.cc b/third_party/re2/re2/parse.cc
new file mode 100644
index 0000000000000000000000000000000000000000..551555a9ceb960c5079f943bee94105771d9592b
--- /dev/null
+++ b/third_party/re2/re2/parse.cc
@@ -0,0 +1,2204 @@
+// 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 <ctype.h>
+
+#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);
+ 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.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
« no previous file with comments | « third_party/re2/re2/onepass.cc ('k') | third_party/re2/re2/perl_groups.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698