• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright 2006 The RE2 Authors.  All Rights Reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4 
5 // Regular expression parser.
6 
7 // The parser is a simple precedence-based parser with a
8 // manual stack.  The parsing work is done by the methods
9 // of the ParseState class.  The Regexp::Parse function is
10 // essentially just a lexer that calls the ParseState method
11 // for each token.
12 
13 // The parser recognizes POSIX extended regular expressions
14 // excluding backreferences, collating elements, and collating
15 // classes.  It also allows the empty string as a regular expression
16 // and recognizes the Perl escape sequences \d, \s, \w, \D, \S, and \W.
17 // See regexp.h for rationale.
18 
19 #include "util/util.h"
20 #include "re2/regexp.h"
21 #include "re2/stringpiece.h"
22 #include "re2/unicode_casefold.h"
23 #include "re2/unicode_groups.h"
24 
25 namespace re2 {
26 
27 // Regular expression parse state.
28 // The list of parsed regexps so far is maintained as a vector of
29 // Regexp pointers called the stack.  Left parenthesis and vertical
30 // bar markers are also placed on the stack, as Regexps with
31 // non-standard opcodes.
32 // Scanning a left parenthesis causes the parser to push a left parenthesis
33 // marker on the stack.
34 // Scanning a vertical bar causes the parser to pop the stack until it finds a
35 // vertical bar or left parenthesis marker (not popping the marker),
36 // concatenate all the popped results, and push them back on
37 // the stack (DoConcatenation).
38 // Scanning a right parenthesis causes the parser to act as though it
39 // has seen a vertical bar, which then leaves the top of the stack in the
40 // form LeftParen regexp VerticalBar regexp VerticalBar ... regexp VerticalBar.
41 // The parser pops all this off the stack and creates an alternation of the
42 // regexps (DoAlternation).
43 
44 class Regexp::ParseState {
45  public:
46   ParseState(ParseFlags flags, const StringPiece& whole_regexp,
47              RegexpStatus* status);
48   ~ParseState();
49 
flags()50   ParseFlags flags() { return flags_; }
rune_max()51   int rune_max() { return rune_max_; }
52 
53   // Parse methods.  All public methods return a bool saying
54   // whether parsing should continue.  If a method returns
55   // false, it has set fields in *status_, and the parser
56   // should return NULL.
57 
58   // Pushes the given regular expression onto the stack.
59   // Could check for too much memory used here.
60   bool PushRegexp(Regexp* re);
61 
62   // Pushes the literal rune r onto the stack.
63   bool PushLiteral(Rune r);
64 
65   // Pushes a regexp with the given op (and no args) onto the stack.
66   bool PushSimpleOp(RegexpOp op);
67 
68   // Pushes a ^ onto the stack.
69   bool PushCarat();
70 
71   // Pushes a \b (word == true) or \B (word == false) onto the stack.
72   bool PushWordBoundary(bool word);
73 
74   // Pushes a $ onto the stack.
75   bool PushDollar();
76 
77   // Pushes a . onto the stack
78   bool PushDot();
79 
80   // Pushes a repeat operator regexp onto the stack.
81   // A valid argument for the operator must already be on the stack.
82   // s is the name of the operator, for use in error messages.
83   bool PushRepeatOp(RegexpOp op, const StringPiece& s, bool nongreedy);
84 
85   // Pushes a repetition regexp onto the stack.
86   // A valid argument for the operator must already be on the stack.
87   bool PushRepetition(int min, int max, const StringPiece& s, bool nongreedy);
88 
89   // Checks whether a particular regexp op is a marker.
90   bool IsMarker(RegexpOp op);
91 
92   // Processes a left parenthesis in the input.
93   // Pushes a marker onto the stack.
94   bool DoLeftParen(const StringPiece& name);
95   bool DoLeftParenNoCapture();
96 
97   // Processes a vertical bar in the input.
98   bool DoVerticalBar();
99 
100   // Processes a right parenthesis in the input.
101   bool DoRightParen();
102 
103   // Processes the end of input, returning the final regexp.
104   Regexp* DoFinish();
105 
106   // Finishes the regexp if necessary, preparing it for use
107   // in a more complicated expression.
108   // If it is a CharClassBuilder, converts into a CharClass.
109   Regexp* FinishRegexp(Regexp*);
110 
111   // These routines don't manipulate the parse stack
112   // directly, but they do need to look at flags_.
113   // ParseCharClass also manipulates the internals of Regexp
114   // while creating *out_re.
115 
116   // Parse a character class into *out_re.
117   // Removes parsed text from s.
118   bool ParseCharClass(StringPiece* s, Regexp** out_re,
119                       RegexpStatus* status);
120 
121   // Parse a character class character into *rp.
122   // Removes parsed text from s.
123   bool ParseCCCharacter(StringPiece* s, Rune *rp,
124                         const StringPiece& whole_class,
125                         RegexpStatus* status);
126 
127   // Parse a character class range into rr.
128   // Removes parsed text from s.
129   bool ParseCCRange(StringPiece* s, RuneRange* rr,
130                     const StringPiece& whole_class,
131                     RegexpStatus* status);
132 
133   // Parse a Perl flag set or non-capturing group from s.
134   bool ParsePerlFlags(StringPiece* s);
135 
136 
137   // Finishes the current concatenation,
138   // collapsing it into a single regexp on the stack.
139   void DoConcatenation();
140 
141   // Finishes the current alternation,
142   // collapsing it to a single regexp on the stack.
143   void DoAlternation();
144 
145   // Generalized DoAlternation/DoConcatenation.
146   void DoCollapse(RegexpOp op);
147 
148   // Maybe concatenate Literals into LiteralString.
149   bool MaybeConcatString(int r, ParseFlags flags);
150 
151 private:
152   ParseFlags flags_;
153   StringPiece whole_regexp_;
154   RegexpStatus* status_;
155   Regexp* stacktop_;
156   int ncap_;  // number of capturing parens seen
157   int rune_max_;  // maximum char value for this encoding
158 
159   DISALLOW_EVIL_CONSTRUCTORS(ParseState);
160 };
161 
162 // Pseudo-operators - only on parse stack.
163 const RegexpOp kLeftParen = static_cast<RegexpOp>(kMaxRegexpOp+1);
164 const RegexpOp kVerticalBar = static_cast<RegexpOp>(kMaxRegexpOp+2);
165 
ParseState(ParseFlags flags,const StringPiece & whole_regexp,RegexpStatus * status)166 Regexp::ParseState::ParseState(ParseFlags flags,
167                                const StringPiece& whole_regexp,
168                                RegexpStatus* status)
169   : flags_(flags), whole_regexp_(whole_regexp),
170     status_(status), stacktop_(NULL), ncap_(0) {
171   if (flags_ & Latin1)
172     rune_max_ = 0xFF;
173   else
174     rune_max_ = Runemax;
175 }
176 
177 // Cleans up by freeing all the regexps on the stack.
~ParseState()178 Regexp::ParseState::~ParseState() {
179   Regexp* next;
180   for (Regexp* re = stacktop_; re != NULL; re = next) {
181     next = re->down_;
182     re->down_ = NULL;
183     if (re->op() == kLeftParen)
184       delete re->name_;
185     re->Decref();
186   }
187 }
188 
189 // Finishes the regexp if necessary, preparing it for use in
190 // a more complex expression.
191 // If it is a CharClassBuilder, converts into a CharClass.
FinishRegexp(Regexp * re)192 Regexp* Regexp::ParseState::FinishRegexp(Regexp* re) {
193   if (re == NULL)
194     return NULL;
195   re->down_ = NULL;
196 
197   if (re->op_ == kRegexpCharClass && re->ccb_ != NULL) {
198     CharClassBuilder* ccb = re->ccb_;
199     re->ccb_ = NULL;
200     re->cc_ = ccb->GetCharClass();
201     delete ccb;
202   }
203 
204   return re;
205 }
206 
207 // Pushes the given regular expression onto the stack.
208 // Could check for too much memory used here.
PushRegexp(Regexp * re)209 bool Regexp::ParseState::PushRegexp(Regexp* re) {
210   MaybeConcatString(-1, NoParseFlags);
211 
212   // Special case: a character class of one character is just
213   // a literal.  This is a common idiom for escaping
214   // single characters (e.g., [.] instead of \.), and some
215   // analysis does better with fewer character classes.
216   // Similarly, [Aa] can be rewritten as a literal A with ASCII case folding.
217   if (re->op_ == kRegexpCharClass) {
218     if (re->ccb_->size() == 1) {
219       Rune r = re->ccb_->begin()->lo;
220       re->Decref();
221       re = new Regexp(kRegexpLiteral, flags_);
222       re->rune_ = r;
223     } else if (re->ccb_->size() == 2) {
224       Rune r = re->ccb_->begin()->lo;
225       if ('A' <= r && r <= 'Z' && re->ccb_->Contains(r + 'a' - 'A')) {
226         re->Decref();
227         re = new Regexp(kRegexpLiteral, flags_ | FoldCase);
228         re->rune_ = r + 'a' - 'A';
229       }
230     }
231   }
232 
233   if (!IsMarker(re->op()))
234     re->simple_ = re->ComputeSimple();
235   re->down_ = stacktop_;
236   stacktop_ = re;
237   return true;
238 }
239 
240 // Searches the case folding tables and returns the CaseFold* that contains r.
241 // If there isn't one, returns the CaseFold* with smallest f->lo bigger than r.
242 // If there isn't one, returns NULL.
LookupCaseFold(CaseFold * f,int n,Rune r)243 CaseFold* LookupCaseFold(CaseFold *f, int n, Rune r) {
244   CaseFold* ef = f + n;
245 
246   // Binary search for entry containing r.
247   while (n > 0) {
248     int m = n/2;
249     if (f[m].lo <= r && r <= f[m].hi)
250       return &f[m];
251     if (r < f[m].lo) {
252       n = m;
253     } else {
254       f += m+1;
255       n -= m+1;
256     }
257   }
258 
259   // There is no entry that contains r, but f points
260   // where it would have been.  Unless f points at
261   // the end of the array, it points at the next entry
262   // after r.
263   if (f < ef)
264     return f;
265 
266   // No entry contains r; no entry contains runes > r.
267   return NULL;
268 }
269 
270 // Returns the result of applying the fold f to the rune r.
ApplyFold(CaseFold * f,Rune r)271 Rune ApplyFold(CaseFold *f, Rune r) {
272   switch (f->delta) {
273     default:
274       return r + f->delta;
275 
276     case EvenOddSkip:  // even <-> odd but only applies to every other
277       if ((r - f->lo) % 2)
278         return r;
279       // fall through
280     case EvenOdd:  // even <-> odd
281       if (r%2 == 0)
282         return r + 1;
283       return r - 1;
284 
285     case OddEvenSkip:  // odd <-> even but only applies to every other
286       if ((r - f->lo) % 2)
287         return r;
288       // fall through
289     case OddEven:  // odd <-> even
290       if (r%2 == 1)
291         return r + 1;
292       return r - 1;
293   }
294 }
295 
296 // Returns the next Rune in r's folding cycle (see unicode_casefold.h).
297 // Examples:
298 //   CycleFoldRune('A') = 'a'
299 //   CycleFoldRune('a') = 'A'
300 //
301 //   CycleFoldRune('K') = 'k'
302 //   CycleFoldRune('k') = 0x212A (Kelvin)
303 //   CycleFoldRune(0x212A) = 'K'
304 //
305 //   CycleFoldRune('?') = '?'
CycleFoldRune(Rune r)306 Rune CycleFoldRune(Rune r) {
307   CaseFold* f = LookupCaseFold(unicode_casefold, num_unicode_casefold, r);
308   if (f == NULL || r < f->lo)
309     return r;
310   return ApplyFold(f, r);
311 }
312 
313 // Add lo-hi to the class, along with their fold-equivalent characters.
314 // If lo-hi is already in the class, assume that the fold-equivalent
315 // chars are there too, so there's no work to do.
AddFoldedRange(CharClassBuilder * cc,Rune lo,Rune hi,int depth)316 static void AddFoldedRange(CharClassBuilder* cc, Rune lo, Rune hi, int depth) {
317   // AddFoldedRange calls itself recursively for each rune in the fold cycle.
318   // Most folding cycles are small: there aren't any bigger than four in the
319   // current Unicode tables.  make_unicode_casefold.py checks that
320   // the cycles are not too long, and we double-check here using depth.
321   if (depth > 10) {
322     LOG(DFATAL) << "AddFoldedRange recurses too much.";
323     return;
324   }
325 
326   if (!cc->AddRange(lo, hi))  // lo-hi was already there? we're done
327     return;
328 
329   while (lo <= hi) {
330     CaseFold* f = LookupCaseFold(unicode_casefold, num_unicode_casefold, lo);
331     if (f == NULL)  // lo has no fold, nor does anything above lo
332       break;
333     if (lo < f->lo) {  // lo has no fold; next rune with a fold is f->lo
334       lo = f->lo;
335       continue;
336     }
337 
338     // Add in the result of folding the range lo - f->hi
339     // and that range's fold, recursively.
340     Rune lo1 = lo;
341     Rune hi1 = min<Rune>(hi, f->hi);
342     switch (f->delta) {
343       default:
344         lo1 += f->delta;
345         hi1 += f->delta;
346         break;
347       case EvenOdd:
348         if (lo1%2 == 1)
349           lo1--;
350         if (hi1%2 == 0)
351           hi1++;
352         break;
353       case OddEven:
354         if (lo1%2 == 0)
355           lo1--;
356         if (hi1%2 == 1)
357           hi1++;
358         break;
359     }
360     AddFoldedRange(cc, lo1, hi1, depth+1);
361 
362     // Pick up where this fold left off.
363     lo = f->hi + 1;
364   }
365 }
366 
367 // Pushes the literal rune r onto the stack.
PushLiteral(Rune r)368 bool Regexp::ParseState::PushLiteral(Rune r) {
369   // Do case folding if needed.
370   if ((flags_ & FoldCase) && CycleFoldRune(r) != r) {
371     Regexp* re = new Regexp(kRegexpCharClass, flags_ & ~FoldCase);
372     re->ccb_ = new CharClassBuilder;
373     Rune r1 = r;
374     do {
375       if (!(flags_ & NeverNL) || r != '\n') {
376         re->ccb_->AddRange(r, r);
377       }
378       r = CycleFoldRune(r);
379     } while (r != r1);
380     re->ccb_->RemoveAbove(rune_max_);
381     return PushRegexp(re);
382   }
383 
384   // Exclude newline if applicable.
385   if ((flags_ & NeverNL) && r == '\n')
386     return PushRegexp(new Regexp(kRegexpNoMatch, flags_));
387 
388   // No fancy stuff worked.  Ordinary literal.
389   if (MaybeConcatString(r, flags_))
390     return true;
391 
392   Regexp* re = new Regexp(kRegexpLiteral, flags_);
393   re->rune_ = r;
394   return PushRegexp(re);
395 }
396 
397 // Pushes a ^ onto the stack.
PushCarat()398 bool Regexp::ParseState::PushCarat() {
399   if (flags_ & OneLine) {
400     return PushSimpleOp(kRegexpBeginText);
401   }
402   return PushSimpleOp(kRegexpBeginLine);
403 }
404 
405 // Pushes a \b or \B onto the stack.
PushWordBoundary(bool word)406 bool Regexp::ParseState::PushWordBoundary(bool word) {
407   if (word)
408     return PushSimpleOp(kRegexpWordBoundary);
409   return PushSimpleOp(kRegexpNoWordBoundary);
410 }
411 
412 // Pushes a $ onto the stack.
PushDollar()413 bool Regexp::ParseState::PushDollar() {
414   if (flags_ & OneLine) {
415     // Clumsy marker so that MimicsPCRE() can tell whether
416     // this kRegexpEndText was a $ and not a \z.
417     Regexp::ParseFlags oflags = flags_;
418     flags_ = flags_ | WasDollar;
419     bool ret = PushSimpleOp(kRegexpEndText);
420     flags_ = oflags;
421     return ret;
422   }
423   return PushSimpleOp(kRegexpEndLine);
424 }
425 
426 // Pushes a . onto the stack.
PushDot()427 bool Regexp::ParseState::PushDot() {
428   if ((flags_ & DotNL) && !(flags_ & NeverNL))
429     return PushSimpleOp(kRegexpAnyChar);
430   // Rewrite . into [^\n]
431   Regexp* re = new Regexp(kRegexpCharClass, flags_ & ~FoldCase);
432   re->ccb_ = new CharClassBuilder;
433   re->ccb_->AddRange(0, '\n' - 1);
434   re->ccb_->AddRange('\n' + 1, rune_max_);
435   return PushRegexp(re);
436 }
437 
438 // Pushes a regexp with the given op (and no args) onto the stack.
PushSimpleOp(RegexpOp op)439 bool Regexp::ParseState::PushSimpleOp(RegexpOp op) {
440   Regexp* re = new Regexp(op, flags_);
441   return PushRegexp(re);
442 }
443 
444 // Pushes a repeat operator regexp onto the stack.
445 // A valid argument for the operator must already be on the stack.
446 // The char c is the name of the operator, for use in error messages.
PushRepeatOp(RegexpOp op,const StringPiece & s,bool nongreedy)447 bool Regexp::ParseState::PushRepeatOp(RegexpOp op, const StringPiece& s,
448                                       bool nongreedy) {
449   if (stacktop_ == NULL || IsMarker(stacktop_->op())) {
450     status_->set_code(kRegexpRepeatArgument);
451     status_->set_error_arg(s);
452     return false;
453   }
454   Regexp::ParseFlags fl = flags_;
455   if (nongreedy)
456     fl = fl ^ NonGreedy;
457   Regexp* re = new Regexp(op, fl);
458   re->AllocSub(1);
459   re->down_ = stacktop_->down_;
460   re->sub()[0] = FinishRegexp(stacktop_);
461   re->simple_ = re->ComputeSimple();
462   stacktop_ = re;
463   return true;
464 }
465 
466 // Pushes a repetition regexp onto the stack.
467 // A valid argument for the operator must already be on the stack.
PushRepetition(int min,int max,const StringPiece & s,bool nongreedy)468 bool Regexp::ParseState::PushRepetition(int min, int max,
469                                         const StringPiece& s,
470                                         bool nongreedy) {
471   if ((max != -1 && max < min) || min > 1000 || max > 1000) {
472     status_->set_code(kRegexpRepeatSize);
473     status_->set_error_arg(s);
474     return false;
475   }
476   if (stacktop_ == NULL || IsMarker(stacktop_->op())) {
477     status_->set_code(kRegexpRepeatArgument);
478     status_->set_error_arg(s);
479     return false;
480   }
481   Regexp::ParseFlags fl = flags_;
482   if (nongreedy)
483     fl = fl ^ NonGreedy;
484   Regexp* re = new Regexp(kRegexpRepeat, fl);
485   re->min_ = min;
486   re->max_ = max;
487   re->AllocSub(1);
488   re->down_ = stacktop_->down_;
489   re->sub()[0] = FinishRegexp(stacktop_);
490   re->simple_ = re->ComputeSimple();
491 
492   stacktop_ = re;
493   return true;
494 }
495 
496 // Checks whether a particular regexp op is a marker.
IsMarker(RegexpOp op)497 bool Regexp::ParseState::IsMarker(RegexpOp op) {
498   return op >= kLeftParen;
499 }
500 
501 // Processes a left parenthesis in the input.
502 // Pushes a marker onto the stack.
DoLeftParen(const StringPiece & name)503 bool Regexp::ParseState::DoLeftParen(const StringPiece& name) {
504   Regexp* re = new Regexp(kLeftParen, flags_);
505   re->cap_ = ++ncap_;
506   if (name.data() != NULL)
507     re->name_ = new string(name.as_string());
508   return PushRegexp(re);
509 }
510 
511 // Pushes a non-capturing marker onto the stack.
DoLeftParenNoCapture()512 bool Regexp::ParseState::DoLeftParenNoCapture() {
513   Regexp* re = new Regexp(kLeftParen, flags_);
514   re->cap_ = -1;
515   return PushRegexp(re);
516 }
517 
518 // Adds r to cc, along with r's upper case if foldascii is set.
AddLiteral(CharClassBuilder * cc,Rune r,bool foldascii)519 static void AddLiteral(CharClassBuilder* cc, Rune r, bool foldascii) {
520   cc->AddRange(r, r);
521   if (foldascii && 'a' <= r && r <= 'z')
522     cc->AddRange(r + 'A' - 'a', r + 'A' - 'a');
523 }
524 
525 // Processes a vertical bar in the input.
DoVerticalBar()526 bool Regexp::ParseState::DoVerticalBar() {
527   MaybeConcatString(-1, NoParseFlags);
528   DoConcatenation();
529 
530   // Below the vertical bar is a list to alternate.
531   // Above the vertical bar is a list to concatenate.
532   // We just did the concatenation, so either swap
533   // the result below the vertical bar or push a new
534   // vertical bar on the stack.
535   Regexp* r1;
536   Regexp* r2;
537   if ((r1 = stacktop_) != NULL &&
538       (r2 = stacktop_->down_) != NULL &&
539       r2->op() == kVerticalBar) {
540     // If above and below vertical bar are literal or char class,
541     // can merge into a single char class.
542     Regexp* r3;
543     if ((r1->op() == kRegexpLiteral ||
544          r1->op() == kRegexpCharClass ||
545          r1->op() == kRegexpAnyChar) &&
546         (r3 = r2->down_) != NULL) {
547       Rune rune;
548       switch (r3->op()) {
549         case kRegexpLiteral:  // convert to char class
550           rune = r3->rune_;
551           r3->op_ = kRegexpCharClass;
552           r3->cc_ = NULL;
553           r3->ccb_ = new CharClassBuilder;
554           AddLiteral(r3->ccb_, rune, r3->parse_flags_ & Regexp::FoldCase);
555           // fall through
556         case kRegexpCharClass:
557           if (r1->op() == kRegexpLiteral)
558             AddLiteral(r3->ccb_, r1->rune_,
559                        r1->parse_flags_ & Regexp::FoldCase);
560           else if (r1->op() == kRegexpCharClass)
561             r3->ccb_->AddCharClass(r1->ccb_);
562           if (r1->op() == kRegexpAnyChar || r3->ccb_->full()) {
563             delete r3->ccb_;
564             r3->ccb_ = NULL;
565             r3->op_ = kRegexpAnyChar;
566           }
567           // fall through
568         case kRegexpAnyChar:
569           // pop r1
570           stacktop_ = r2;
571           r1->Decref();
572           return true;
573         default:
574           break;
575       }
576     }
577 
578     // Swap r1 below vertical bar (r2).
579     r1->down_ = r2->down_;
580     r2->down_ = r1;
581     stacktop_ = r2;
582     return true;
583   }
584   return PushSimpleOp(kVerticalBar);
585 }
586 
587 // Processes a right parenthesis in the input.
DoRightParen()588 bool Regexp::ParseState::DoRightParen() {
589   // Finish the current concatenation and alternation.
590   DoAlternation();
591 
592   // The stack should be: LeftParen regexp
593   // Remove the LeftParen, leaving the regexp,
594   // parenthesized.
595   Regexp* r1;
596   Regexp* r2;
597   if ((r1 = stacktop_) == NULL ||
598       (r2 = r1->down_) == NULL ||
599       r2->op() != kLeftParen) {
600     status_->set_code(kRegexpMissingParen);
601     status_->set_error_arg(whole_regexp_);
602     return false;
603   }
604 
605   // Pop off r1, r2.  Will Decref or reuse below.
606   stacktop_ = r2->down_;
607 
608   // Restore flags from when paren opened.
609   Regexp* re = r2;
610   flags_ = re->parse_flags();
611 
612   // Rewrite LeftParen as capture if needed.
613   if (re->cap_ > 0) {
614     re->op_ = kRegexpCapture;
615     // re->cap_ is already set
616     re->AllocSub(1);
617     re->sub()[0] = FinishRegexp(r1);
618     re->simple_ = re->ComputeSimple();
619   } else {
620     re->Decref();
621     re = r1;
622   }
623   return PushRegexp(re);
624 }
625 
626 // Processes the end of input, returning the final regexp.
DoFinish()627 Regexp* Regexp::ParseState::DoFinish() {
628   DoAlternation();
629   Regexp* re = stacktop_;
630   if (re != NULL && re->down_ != NULL) {
631     status_->set_code(kRegexpMissingParen);
632     status_->set_error_arg(whole_regexp_);
633     return NULL;
634   }
635   stacktop_ = NULL;
636   return FinishRegexp(re);
637 }
638 
639 // Returns the leading regexp that re starts with.
640 // The returned Regexp* points into a piece of re,
641 // so it must not be used after the caller calls re->Decref().
LeadingRegexp(Regexp * re)642 Regexp* Regexp::LeadingRegexp(Regexp* re) {
643   if (re->op() == kRegexpEmptyMatch)
644     return NULL;
645   if (re->op() == kRegexpConcat && re->nsub() >= 2) {
646     Regexp** sub = re->sub();
647     if (sub[0]->op() == kRegexpEmptyMatch)
648       return NULL;
649     return sub[0];
650   }
651   return re;
652 }
653 
654 // Removes LeadingRegexp(re) from re and returns what's left.
655 // Consumes the reference to re and may edit it in place.
656 // If caller wants to hold on to LeadingRegexp(re),
657 // must have already Incref'ed it.
RemoveLeadingRegexp(Regexp * re)658 Regexp* Regexp::RemoveLeadingRegexp(Regexp* re) {
659   if (re->op() == kRegexpEmptyMatch)
660     return re;
661   if (re->op() == kRegexpConcat && re->nsub() >= 2) {
662     Regexp** sub = re->sub();
663     if (sub[0]->op() == kRegexpEmptyMatch)
664       return re;
665     sub[0]->Decref();
666     sub[0] = NULL;
667     if (re->nsub() == 2) {
668       // Collapse concatenation to single regexp.
669       Regexp* nre = sub[1];
670       sub[1] = NULL;
671       re->Decref();
672       return nre;
673     }
674     // 3 or more -> 2 or more.
675     re->nsub_--;
676     memmove(sub, sub + 1, re->nsub_ * sizeof sub[0]);
677     return re;
678   }
679   Regexp::ParseFlags pf = re->parse_flags();
680   re->Decref();
681   return new Regexp(kRegexpEmptyMatch, pf);
682 }
683 
684 // Returns the leading string that re starts with.
685 // The returned Rune* points into a piece of re,
686 // so it must not be used after the caller calls re->Decref().
LeadingString(Regexp * re,int * nrune,Regexp::ParseFlags * flags)687 Rune* Regexp::LeadingString(Regexp* re, int *nrune,
688                             Regexp::ParseFlags *flags) {
689   while (re->op() == kRegexpConcat && re->nsub() > 0)
690     re = re->sub()[0];
691 
692   *flags = static_cast<Regexp::ParseFlags>(re->parse_flags_ & Regexp::FoldCase);
693 
694   if (re->op() == kRegexpLiteral) {
695     *nrune = 1;
696     return &re->rune_;
697   }
698 
699   if (re->op() == kRegexpLiteralString) {
700     *nrune = re->nrunes_;
701     return re->runes_;
702   }
703 
704   *nrune = 0;
705   return NULL;
706 }
707 
708 // Removes the first n leading runes from the beginning of re.
709 // Edits re in place.
RemoveLeadingString(Regexp * re,int n)710 void Regexp::RemoveLeadingString(Regexp* re, int n) {
711   // Chase down concats to find first string.
712   // For regexps generated by parser, nested concats are
713   // flattened except when doing so would overflow the 16-bit
714   // limit on the size of a concatenation, so we should never
715   // see more than two here.
716   Regexp* stk[4];
717   int d = 0;
718   while (re->op() == kRegexpConcat) {
719     if (d < arraysize(stk))
720       stk[d++] = re;
721     re = re->sub()[0];
722   }
723 
724   // Remove leading string from re.
725   if (re->op() == kRegexpLiteral) {
726     re->rune_ = 0;
727     re->op_ = kRegexpEmptyMatch;
728   } else if (re->op() == kRegexpLiteralString) {
729     if (n >= re->nrunes_) {
730       delete[] re->runes_;
731       re->runes_ = NULL;
732       re->nrunes_ = 0;
733       re->op_ = kRegexpEmptyMatch;
734     } else if (n == re->nrunes_ - 1) {
735       Rune rune = re->runes_[re->nrunes_ - 1];
736       delete[] re->runes_;
737       re->runes_ = NULL;
738       re->nrunes_ = 0;
739       re->rune_ = rune;
740       re->op_ = kRegexpLiteral;
741     } else {
742       re->nrunes_ -= n;
743       memmove(re->runes_, re->runes_ + n, re->nrunes_ * sizeof re->runes_[0]);
744     }
745   }
746 
747   // If re is now empty, concatenations might simplify too.
748   while (d-- > 0) {
749     re = stk[d];
750     Regexp** sub = re->sub();
751     if (sub[0]->op() == kRegexpEmptyMatch) {
752       sub[0]->Decref();
753       sub[0] = NULL;
754       // Delete first element of concat.
755       switch (re->nsub()) {
756         case 0:
757         case 1:
758           // Impossible.
759           LOG(DFATAL) << "Concat of " << re->nsub();
760           re->submany_ = NULL;
761           re->op_ = kRegexpEmptyMatch;
762           break;
763 
764         case 2: {
765           // Replace re with sub[1].
766           Regexp* old = sub[1];
767           sub[1] = NULL;
768           re->Swap(old);
769           old->Decref();
770           break;
771         }
772 
773         default:
774           // Slide down.
775           re->nsub_--;
776           memmove(sub, sub + 1, re->nsub_ * sizeof sub[0]);
777           break;
778       }
779     }
780   }
781 }
782 
783 // Factors common prefixes from alternation.
784 // For example,
785 //     ABC|ABD|AEF|BCX|BCY
786 // simplifies to
787 //     A(B(C|D)|EF)|BC(X|Y)
788 // which the normal parse state routines will further simplify to
789 //     A(B[CD]|EF)|BC[XY]
790 //
791 // Rewrites sub to contain simplified list to alternate and returns
792 // the new length of sub.  Adjusts reference counts accordingly
793 // (incoming sub[i] decremented, outgoing sub[i] incremented).
794 
795 // It's too much of a pain to write this code with an explicit stack,
796 // so instead we let the caller specify a maximum depth and
797 // don't simplify beyond that.  There are around 15 words of local
798 // variables and parameters in the frame, so allowing 8 levels
799 // on a 64-bit machine is still less than a kilobyte of stack and
800 // probably enough benefit for practical uses.
801 const int kFactorAlternationMaxDepth = 8;
802 
FactorAlternation(Regexp ** sub,int n,Regexp::ParseFlags altflags)803 int Regexp::FactorAlternation(
804     Regexp** sub, int n,
805     Regexp::ParseFlags altflags) {
806   return FactorAlternationRecursive(sub, n, altflags,
807                                     kFactorAlternationMaxDepth);
808 }
809 
FactorAlternationRecursive(Regexp ** sub,int n,Regexp::ParseFlags altflags,int maxdepth)810 int Regexp::FactorAlternationRecursive(
811     Regexp** sub, int n,
812     Regexp::ParseFlags altflags,
813     int maxdepth) {
814 
815   if (maxdepth <= 0)
816     return n;
817 
818   // Round 1: Factor out common literal prefixes.
819   Rune *rune = NULL;
820   int nrune = 0;
821   Regexp::ParseFlags runeflags = Regexp::NoParseFlags;
822   int start = 0;
823   int out = 0;
824   for (int i = 0; i <= n; i++) {
825     // Invariant: what was in sub[0:start] has been Decref'ed
826     // and that space has been reused for sub[0:out] (out <= start).
827     //
828     // Invariant: sub[start:i] consists of regexps that all begin
829     // with the string rune[0:nrune].
830 
831     Rune* rune_i = NULL;
832     int nrune_i = 0;
833     Regexp::ParseFlags runeflags_i = Regexp::NoParseFlags;
834     if (i < n) {
835       rune_i = LeadingString(sub[i], &nrune_i, &runeflags_i);
836       if (runeflags_i == runeflags) {
837         int same = 0;
838         while (same < nrune && same < nrune_i && rune[same] == rune_i[same])
839           same++;
840         if (same > 0) {
841           // Matches at least one rune in current range.  Keep going around.
842           nrune = same;
843           continue;
844         }
845       }
846     }
847 
848     // Found end of a run with common leading literal string:
849     // sub[start:i] all begin with rune[0:nrune] but sub[i]
850     // does not even begin with rune[0].
851     //
852     // Factor out common string and append factored expression to sub[0:out].
853     if (i == start) {
854       // Nothing to do - first iteration.
855     } else if (i == start+1) {
856       // Just one: don't bother factoring.
857       sub[out++] = sub[start];
858     } else {
859       // Construct factored form: prefix(suffix1|suffix2|...)
860       Regexp* x[2];  // x[0] = prefix, x[1] = suffix1|suffix2|...
861       x[0] = LiteralString(rune, nrune, runeflags);
862       for (int j = start; j < i; j++)
863         RemoveLeadingString(sub[j], nrune);
864       int nn = FactorAlternationRecursive(sub + start, i - start, altflags,
865                                           maxdepth - 1);
866       x[1] = AlternateNoFactor(sub + start, nn, altflags);
867       sub[out++] = Concat(x, 2, altflags);
868     }
869 
870     // Prepare for next round (if there is one).
871     if (i < n) {
872       start = i;
873       rune = rune_i;
874       nrune = nrune_i;
875       runeflags = runeflags_i;
876     }
877   }
878   n = out;
879 
880   // Round 2: Factor out common complex prefixes,
881   // just the first piece of each concatenation,
882   // whatever it is.  This is good enough a lot of the time.
883   start = 0;
884   out = 0;
885   Regexp* first = NULL;
886   for (int i = 0; i <= n; i++) {
887     // Invariant: what was in sub[0:start] has been Decref'ed
888     // and that space has been reused for sub[0:out] (out <= start).
889     //
890     // Invariant: sub[start:i] consists of regexps that all begin with first.
891 
892     Regexp* first_i = NULL;
893     if (i < n) {
894       first_i = LeadingRegexp(sub[i]);
895       if (first != NULL && Regexp::Equal(first, first_i)) {
896         continue;
897       }
898     }
899 
900     // Found end of a run with common leading regexp:
901     // sub[start:i] all begin with first but sub[i] does not.
902     //
903     // Factor out common regexp and append factored expression to sub[0:out].
904     if (i == start) {
905       // Nothing to do - first iteration.
906     } else if (i == start+1) {
907       // Just one: don't bother factoring.
908       sub[out++] = sub[start];
909     } else {
910       // Construct factored form: prefix(suffix1|suffix2|...)
911       Regexp* x[2];  // x[0] = prefix, x[1] = suffix1|suffix2|...
912       x[0] = first->Incref();
913       for (int j = start; j < i; j++)
914         sub[j] = RemoveLeadingRegexp(sub[j]);
915       int nn = FactorAlternationRecursive(sub + start, i - start, altflags,
916                                    maxdepth - 1);
917       x[1] = AlternateNoFactor(sub + start, nn, altflags);
918       sub[out++] = Concat(x, 2, altflags);
919     }
920 
921     // Prepare for next round (if there is one).
922     if (i < n) {
923       start = i;
924       first = first_i;
925     }
926   }
927   n = out;
928 
929   // Round 3: Collapse runs of single literals into character classes.
930   start = 0;
931   out = 0;
932   for (int i = 0; i <= n; i++) {
933     // Invariant: what was in sub[0:start] has been Decref'ed
934     // and that space has been reused for sub[0:out] (out <= start).
935     //
936     // Invariant: sub[start:i] consists of regexps that are either
937     // literal runes or character classes.
938 
939     if (i < n &&
940         (sub[i]->op() == kRegexpLiteral ||
941          sub[i]->op() == kRegexpCharClass))
942       continue;
943 
944     // sub[i] is not a char or char class;
945     // emit char class for sub[start:i]...
946     if (i == start) {
947       // Nothing to do.
948     } else if (i == start+1) {
949       sub[out++] = sub[start];
950     } else {
951       // Make new char class.
952       CharClassBuilder ccb;
953       for (int j = start; j < i; j++) {
954         Regexp* re = sub[j];
955         if (re->op() == kRegexpCharClass) {
956           CharClass* cc = re->cc();
957           for (CharClass::iterator it = cc->begin(); it != cc->end(); ++it)
958             ccb.AddRange(it->lo, it->hi);
959         } else if (re->op() == kRegexpLiteral) {
960           ccb.AddRangeFlags(re->rune(), re->rune(), re->parse_flags());
961         } else {
962           LOG(DFATAL) << "RE2: unexpected op: " << re->op() << " "
963                       << re->ToString();
964         }
965         re->Decref();
966       }
967       sub[out++] = NewCharClass(ccb.GetCharClass(), altflags);
968     }
969 
970     // ... and then emit sub[i].
971     if (i < n)
972       sub[out++] = sub[i];
973     start = i+1;
974   }
975   n = out;
976 
977   // Round 4: Collapse runs of empty matches into single empty match.
978   start = 0;
979   out = 0;
980   for (int i = 0; i < n; i++) {
981     if (i + 1 < n &&
982         sub[i]->op() == kRegexpEmptyMatch &&
983         sub[i+1]->op() == kRegexpEmptyMatch) {
984       sub[i]->Decref();
985       continue;
986     }
987     sub[out++] = sub[i];
988   }
989   n = out;
990 
991   return n;
992 }
993 
994 // Collapse the regexps on top of the stack, down to the
995 // first marker, into a new op node (op == kRegexpAlternate
996 // or op == kRegexpConcat).
DoCollapse(RegexpOp op)997 void Regexp::ParseState::DoCollapse(RegexpOp op) {
998   // Scan backward to marker, counting children of composite.
999   int n = 0;
1000   Regexp* next = NULL;
1001   Regexp* sub;
1002   for (sub = stacktop_; sub != NULL && !IsMarker(sub->op()); sub = next) {
1003     next = sub->down_;
1004     if (sub->op_ == op)
1005       n += sub->nsub_;
1006     else
1007       n++;
1008   }
1009 
1010   // If there's just one child, leave it alone.
1011   // (Concat of one thing is that one thing; alternate of one thing is same.)
1012   if (stacktop_ != NULL && stacktop_->down_ == next)
1013     return;
1014 
1015   // Construct op (alternation or concatenation), flattening op of op.
1016   Regexp** subs = new Regexp*[n];
1017   next = NULL;
1018   int i = n;
1019   for (sub = stacktop_; sub != NULL && !IsMarker(sub->op()); sub = next) {
1020     next = sub->down_;
1021     if (sub->op_ == op) {
1022       Regexp** sub_subs = sub->sub();
1023       for (int k = sub->nsub_ - 1; k >= 0; k--)
1024         subs[--i] = sub_subs[k]->Incref();
1025       sub->Decref();
1026     } else {
1027       subs[--i] = FinishRegexp(sub);
1028     }
1029   }
1030 
1031   Regexp* re = ConcatOrAlternate(op, subs, n, flags_, true);
1032   delete[] subs;
1033   re->simple_ = re->ComputeSimple();
1034   re->down_ = next;
1035   stacktop_ = re;
1036 }
1037 
1038 // Finishes the current concatenation,
1039 // collapsing it into a single regexp on the stack.
DoConcatenation()1040 void Regexp::ParseState::DoConcatenation() {
1041   Regexp* r1 = stacktop_;
1042   if (r1 == NULL || IsMarker(r1->op())) {
1043     // empty concatenation is special case
1044     Regexp* re = new Regexp(kRegexpEmptyMatch, flags_);
1045     PushRegexp(re);
1046   }
1047   DoCollapse(kRegexpConcat);
1048 }
1049 
1050 // Finishes the current alternation,
1051 // collapsing it to a single regexp on the stack.
DoAlternation()1052 void Regexp::ParseState::DoAlternation() {
1053   DoVerticalBar();
1054   // Now stack top is kVerticalBar.
1055   Regexp* r1 = stacktop_;
1056   stacktop_ = r1->down_;
1057   r1->Decref();
1058   DoCollapse(kRegexpAlternate);
1059 }
1060 
1061 // Incremental conversion of concatenated literals into strings.
1062 // If top two elements on stack are both literal or string,
1063 // collapse into single string.
1064 // Don't walk down the stack -- the parser calls this frequently
1065 // enough that below the bottom two is known to be collapsed.
1066 // Only called when another regexp is about to be pushed
1067 // on the stack, so that the topmost literal is not being considered.
1068 // (Otherwise ab* would turn into (ab)*.)
1069 // If r >= 0, consider pushing a literal r on the stack.
1070 // Return whether that happened.
MaybeConcatString(int r,ParseFlags flags)1071 bool Regexp::ParseState::MaybeConcatString(int r, ParseFlags flags) {
1072   Regexp* re1;
1073   Regexp* re2;
1074   if ((re1 = stacktop_) == NULL || (re2 = re1->down_) == NULL)
1075     return false;
1076 
1077   if (re1->op_ != kRegexpLiteral && re1->op_ != kRegexpLiteralString)
1078     return false;
1079   if (re2->op_ != kRegexpLiteral && re2->op_ != kRegexpLiteralString)
1080     return false;
1081   if ((re1->parse_flags_ & FoldCase) != (re2->parse_flags_ & FoldCase))
1082     return false;
1083 
1084   if (re2->op_ == kRegexpLiteral) {
1085     // convert into string
1086     Rune rune = re2->rune_;
1087     re2->op_ = kRegexpLiteralString;
1088     re2->nrunes_ = 0;
1089     re2->runes_ = NULL;
1090     re2->AddRuneToString(rune);
1091   }
1092 
1093   // push re1 into re2.
1094   if (re1->op_ == kRegexpLiteral) {
1095     re2->AddRuneToString(re1->rune_);
1096   } else {
1097     for (int i = 0; i < re1->nrunes_; i++)
1098       re2->AddRuneToString(re1->runes_[i]);
1099     re1->nrunes_ = 0;
1100     delete[] re1->runes_;
1101     re1->runes_ = NULL;
1102   }
1103 
1104   // reuse re1 if possible
1105   if (r >= 0) {
1106     re1->op_ = kRegexpLiteral;
1107     re1->rune_ = r;
1108     re1->parse_flags_ = flags;
1109     return true;
1110   }
1111 
1112   stacktop_ = re2;
1113   re1->Decref();
1114   return false;
1115 }
1116 
1117 // Lexing routines.
1118 
1119 // Parses a decimal integer, storing it in *n.
1120 // Sets *s to span the remainder of the string.
1121 // Sets *out_re to the regexp for the class.
ParseInteger(StringPiece * s,int * np)1122 static bool ParseInteger(StringPiece* s, int* np) {
1123   if (s->size() == 0 || !isdigit((*s)[0] & 0xFF))
1124     return false;
1125   // Disallow leading zeros.
1126   if (s->size() >= 2 && (*s)[0] == '0' && isdigit((*s)[1] & 0xFF))
1127     return false;
1128   int n = 0;
1129   int c;
1130   while (s->size() > 0 && isdigit(c = (*s)[0] & 0xFF)) {
1131     // Avoid overflow.
1132     if (n >= 100000000)
1133       return false;
1134     n = n*10 + c - '0';
1135     s->remove_prefix(1);  // digit
1136   }
1137   *np = n;
1138   return true;
1139 }
1140 
1141 // Parses a repetition suffix like {1,2} or {2} or {2,}.
1142 // Sets *s to span the remainder of the string on success.
1143 // Sets *lo and *hi to the given range.
1144 // In the case of {2,}, the high number is unbounded;
1145 // sets *hi to -1 to signify this.
1146 // {,2} is NOT a valid suffix.
1147 // The Maybe in the name signifies that the regexp parse
1148 // doesn't fail even if ParseRepetition does, so the StringPiece
1149 // s must NOT be edited unless MaybeParseRepetition returns true.
MaybeParseRepetition(StringPiece * sp,int * lo,int * hi)1150 static bool MaybeParseRepetition(StringPiece* sp, int* lo, int* hi) {
1151   StringPiece s = *sp;
1152   if (s.size() == 0 || s[0] != '{')
1153     return false;
1154   s.remove_prefix(1);  // '{'
1155   if (!ParseInteger(&s, lo))
1156     return false;
1157   if (s.size() == 0)
1158     return false;
1159   if (s[0] == ',') {
1160     s.remove_prefix(1);  // ','
1161     if (s.size() == 0)
1162       return false;
1163     if (s[0] == '}') {
1164       // {2,} means at least 2
1165       *hi = -1;
1166     } else {
1167       // {2,4} means 2, 3, or 4.
1168       if (!ParseInteger(&s, hi))
1169         return false;
1170     }
1171   } else {
1172     // {2} means exactly two
1173     *hi = *lo;
1174   }
1175   if (s.size() == 0 || s[0] != '}')
1176     return false;
1177   s.remove_prefix(1);  // '}'
1178   *sp = s;
1179   return true;
1180 }
1181 
1182 // Removes the next Rune from the StringPiece and stores it in *r.
1183 // Returns number of bytes removed from sp.
1184 // Behaves as though there is a terminating NUL at the end of sp.
1185 // Argument order is backwards from usual Google style
1186 // but consistent with chartorune.
StringPieceToRune(Rune * r,StringPiece * sp,RegexpStatus * status)1187 static int StringPieceToRune(Rune *r, StringPiece *sp, RegexpStatus* status) {
1188   int n;
1189   if (fullrune(sp->data(), sp->size())) {
1190     n = chartorune(r, sp->data());
1191     if (!(n == 1 && *r == Runeerror)) {  // no decoding error
1192       sp->remove_prefix(n);
1193       return n;
1194     }
1195   }
1196 
1197   status->set_code(kRegexpBadUTF8);
1198   status->set_error_arg(NULL);
1199   return -1;
1200 }
1201 
1202 // Return whether name is valid UTF-8.
1203 // If not, set status to kRegexpBadUTF8.
IsValidUTF8(const StringPiece & s,RegexpStatus * status)1204 static bool IsValidUTF8(const StringPiece& s, RegexpStatus* status) {
1205   StringPiece t = s;
1206   Rune r;
1207   while (t.size() > 0) {
1208     if (StringPieceToRune(&r, &t, status) < 0)
1209       return false;
1210   }
1211   return true;
1212 }
1213 
1214 // Is c a hex digit?
IsHex(int c)1215 static int IsHex(int c) {
1216   return ('0' <= c && c <= '9') ||
1217          ('A' <= c && c <= 'F') ||
1218          ('a' <= c && c <= 'f');
1219 }
1220 
1221 // Convert hex digit to value.
UnHex(int c)1222 static int UnHex(int c) {
1223   if ('0' <= c && c <= '9')
1224     return c - '0';
1225   if ('A' <= c && c <= 'F')
1226     return c - 'A' + 10;
1227   if ('a' <= c && c <= 'f')
1228     return c - 'a' + 10;
1229   LOG(DFATAL) << "Bad hex digit " << c;
1230   return 0;
1231 }
1232 
1233 // Parse an escape sequence (e.g., \n, \{).
1234 // Sets *s to span the remainder of the string.
1235 // Sets *rp to the named character.
ParseEscape(StringPiece * s,Rune * rp,RegexpStatus * status,int rune_max)1236 static bool ParseEscape(StringPiece* s, Rune* rp,
1237                         RegexpStatus* status, int rune_max) {
1238   const char* begin = s->begin();
1239   if (s->size() < 1 || (*s)[0] != '\\') {
1240     // Should not happen - caller always checks.
1241     status->set_code(kRegexpInternalError);
1242     status->set_error_arg(NULL);
1243     return false;
1244   }
1245   if (s->size() < 2) {
1246     status->set_code(kRegexpTrailingBackslash);
1247     status->set_error_arg(NULL);
1248     return false;
1249   }
1250   Rune c, c1;
1251   s->remove_prefix(1);  // backslash
1252   if (StringPieceToRune(&c, s, status) < 0)
1253     return false;
1254   int code;
1255   switch (c) {
1256     default:
1257       if (c < Runeself && !isalpha(c) && !isdigit(c)) {
1258         // Escaped non-word characters are always themselves.
1259         // PCRE is not quite so rigorous: it accepts things like
1260         // \q, but we don't.  We once rejected \_, but too many
1261         // programs and people insist on using it, so allow \_.
1262         *rp = c;
1263         return true;
1264       }
1265       goto BadEscape;
1266 
1267     // Octal escapes.
1268     case '1':
1269     case '2':
1270     case '3':
1271     case '4':
1272     case '5':
1273     case '6':
1274     case '7':
1275       // Single non-zero octal digit is a backreference; not supported.
1276       if (s->size() == 0 || (*s)[0] < '0' || (*s)[0] > '7')
1277         goto BadEscape;
1278       // fall through
1279     case '0':
1280       // consume up to three octal digits; already have one.
1281       code = c - '0';
1282       if (s->size() > 0 && '0' <= (c = (*s)[0]) && c <= '7') {
1283         code = code * 8 + c - '0';
1284         s->remove_prefix(1);  // digit
1285         if (s->size() > 0) {
1286           c = (*s)[0];
1287           if ('0' <= c && c <= '7') {
1288             code = code * 8 + c - '0';
1289             s->remove_prefix(1);  // digit
1290           }
1291         }
1292       }
1293       *rp = code;
1294       return true;
1295 
1296     // Hexadecimal escapes
1297     case 'x':
1298       if (s->size() == 0)
1299         goto BadEscape;
1300       if (StringPieceToRune(&c, s, status) < 0)
1301         return false;
1302       if (c == '{') {
1303         // Any number of digits in braces.
1304         // Update n as we consume the string, so that
1305         // the whole thing gets shown in the error message.
1306         // Perl accepts any text at all; it ignores all text
1307         // after the first non-hex digit.  We require only hex digits,
1308         // and at least one.
1309         if (StringPieceToRune(&c, s, status) < 0)
1310           return false;
1311         int nhex = 0;
1312         code = 0;
1313         while (IsHex(c)) {
1314           nhex++;
1315           code = code * 16 + UnHex(c);
1316           if (code > rune_max)
1317             goto BadEscape;
1318           if (s->size() == 0)
1319             goto BadEscape;
1320           if (StringPieceToRune(&c, s, status) < 0)
1321             return false;
1322         }
1323         if (c != '}' || nhex == 0)
1324           goto BadEscape;
1325         *rp = code;
1326         return true;
1327       }
1328       // Easy case: two hex digits.
1329       if (s->size() == 0)
1330         goto BadEscape;
1331       if (StringPieceToRune(&c1, s, status) < 0)
1332         return false;
1333       if (!IsHex(c) || !IsHex(c1))
1334         goto BadEscape;
1335       *rp = UnHex(c) * 16 + UnHex(c1);
1336       return true;
1337 
1338     // C escapes.
1339     case 'n':
1340       *rp = '\n';
1341       return true;
1342     case 'r':
1343       *rp = '\r';
1344       return true;
1345     case 't':
1346       *rp = '\t';
1347       return true;
1348 
1349     // Less common C escapes.
1350     case 'a':
1351       *rp = '\a';
1352       return true;
1353     case 'f':
1354       *rp = '\f';
1355       return true;
1356     case 'v':
1357       *rp = '\v';
1358       return true;
1359 
1360     // This code is disabled to avoid misparsing
1361     // the Perl word-boundary \b as a backspace
1362     // when in POSIX regexp mode.  Surprisingly,
1363     // in Perl, \b means word-boundary but [\b]
1364     // means backspace.  We don't support that:
1365     // if you want a backspace embed a literal
1366     // backspace character or use \x08.
1367     //
1368     // case 'b':
1369     //   *rp = '\b';
1370     //   return true;
1371   }
1372 
1373   LOG(DFATAL) << "Not reached in ParseEscape.";
1374 
1375 BadEscape:
1376   // Unrecognized escape sequence.
1377   status->set_code(kRegexpBadEscape);
1378   status->set_error_arg(StringPiece(begin, s->data() - begin));
1379   return false;
1380 }
1381 
1382 // Add a range to the character class, but exclude newline if asked.
1383 // Also handle case folding.
AddRangeFlags(Rune lo,Rune hi,Regexp::ParseFlags parse_flags)1384 void CharClassBuilder::AddRangeFlags(
1385     Rune lo, Rune hi, Regexp::ParseFlags parse_flags) {
1386 
1387   // Take out \n if the flags say so.
1388   bool cutnl = !(parse_flags & Regexp::ClassNL) ||
1389                (parse_flags & Regexp::NeverNL);
1390   if (cutnl && lo <= '\n' && '\n' <= hi) {
1391     if (lo < '\n')
1392       AddRangeFlags(lo, '\n' - 1, parse_flags);
1393     if (hi > '\n')
1394       AddRangeFlags('\n' + 1, hi, parse_flags);
1395     return;
1396   }
1397 
1398   // If folding case, add fold-equivalent characters too.
1399   if (parse_flags & Regexp::FoldCase)
1400     AddFoldedRange(this, lo, hi, 0);
1401   else
1402     AddRange(lo, hi);
1403 }
1404 
1405 // Look for a group with the given name.
LookupGroup(const StringPiece & name,UGroup * groups,int ngroups)1406 static UGroup* LookupGroup(const StringPiece& name,
1407                            UGroup *groups, int ngroups) {
1408   // Simple name lookup.
1409   for (int i = 0; i < ngroups; i++)
1410     if (StringPiece(groups[i].name) == name)
1411       return &groups[i];
1412   return NULL;
1413 }
1414 
1415 // Fake UGroup containing all Runes
1416 static URange16 any16[] = { { 0, 65535 } };
1417 static URange32 any32[] = { { 65536, Runemax } };
1418 static UGroup anygroup = { "Any", +1, any16, 1, any32, 1 };
1419 
1420 // Look for a POSIX group with the given name (e.g., "[:^alpha:]")
LookupPosixGroup(const StringPiece & name)1421 static UGroup* LookupPosixGroup(const StringPiece& name) {
1422   return LookupGroup(name, posix_groups, num_posix_groups);
1423 }
1424 
LookupPerlGroup(const StringPiece & name)1425 static UGroup* LookupPerlGroup(const StringPiece& name) {
1426   return LookupGroup(name, perl_groups, num_perl_groups);
1427 }
1428 
1429 // Look for a Unicode group with the given name (e.g., "Han")
LookupUnicodeGroup(const StringPiece & name)1430 static UGroup* LookupUnicodeGroup(const StringPiece& name) {
1431   // Special case: "Any" means any.
1432   if (name == StringPiece("Any"))
1433     return &anygroup;
1434   return LookupGroup(name, unicode_groups, num_unicode_groups);
1435 }
1436 
1437 // Add a UGroup or its negation to the character class.
AddUGroup(CharClassBuilder * cc,UGroup * g,int sign,Regexp::ParseFlags parse_flags)1438 static void AddUGroup(CharClassBuilder *cc, UGroup *g, int sign,
1439                       Regexp::ParseFlags parse_flags) {
1440   if (sign == +1) {
1441     for (int i = 0; i < g->nr16; i++) {
1442       cc->AddRangeFlags(g->r16[i].lo, g->r16[i].hi, parse_flags);
1443     }
1444     for (int i = 0; i < g->nr32; i++) {
1445       cc->AddRangeFlags(g->r32[i].lo, g->r32[i].hi, parse_flags);
1446     }
1447   } else {
1448     if (parse_flags & Regexp::FoldCase) {
1449       // Normally adding a case-folded group means
1450       // adding all the extra fold-equivalent runes too.
1451       // But if we're adding the negation of the group,
1452       // we have to exclude all the runes that are fold-equivalent
1453       // to what's already missing.  Too hard, so do in two steps.
1454       CharClassBuilder ccb1;
1455       AddUGroup(&ccb1, g, +1, parse_flags);
1456       // If the flags say to take out \n, put it in, so that negating will take it out.
1457       // Normally AddRangeFlags does this, but we're bypassing AddRangeFlags.
1458       bool cutnl = !(parse_flags & Regexp::ClassNL) ||
1459                    (parse_flags & Regexp::NeverNL);
1460       if (cutnl) {
1461         ccb1.AddRange('\n', '\n');
1462       }
1463       ccb1.Negate();
1464       cc->AddCharClass(&ccb1);
1465       return;
1466     }
1467     int next = 0;
1468     for (int i = 0; i < g->nr16; i++) {
1469       if (next < g->r16[i].lo)
1470         cc->AddRangeFlags(next, g->r16[i].lo - 1, parse_flags);
1471       next = g->r16[i].hi + 1;
1472     }
1473     for (int i = 0; i < g->nr32; i++) {
1474       if (next < g->r32[i].lo)
1475         cc->AddRangeFlags(next, g->r32[i].lo - 1, parse_flags);
1476       next = g->r32[i].hi + 1;
1477     }
1478     if (next <= Runemax)
1479       cc->AddRangeFlags(next, Runemax, parse_flags);
1480   }
1481 }
1482 
1483 // Maybe parse a Perl character class escape sequence.
1484 // Only recognizes the Perl character classes (\d \s \w \D \S \W),
1485 // not the Perl empty-string classes (\b \B \A \Z \z).
1486 // On success, sets *s to span the remainder of the string
1487 // and returns the corresponding UGroup.
1488 // The StringPiece must *NOT* be edited unless the call succeeds.
MaybeParsePerlCCEscape(StringPiece * s,Regexp::ParseFlags parse_flags)1489 UGroup* MaybeParsePerlCCEscape(StringPiece* s, Regexp::ParseFlags parse_flags) {
1490   if (!(parse_flags & Regexp::PerlClasses))
1491     return NULL;
1492   if (s->size() < 2 || (*s)[0] != '\\')
1493     return NULL;
1494   // Could use StringPieceToRune, but there aren't
1495   // any non-ASCII Perl group names.
1496   StringPiece name(s->begin(), 2);
1497   UGroup *g = LookupPerlGroup(name);
1498   if (g == NULL)
1499     return NULL;
1500   s->remove_prefix(name.size());
1501   return g;
1502 }
1503 
1504 enum ParseStatus {
1505   kParseOk,  // Did some parsing.
1506   kParseError,  // Found an error.
1507   kParseNothing,  // Decided not to parse.
1508 };
1509 
1510 // Maybe parses a Unicode character group like \p{Han} or \P{Han}
1511 // (the latter is a negated group).
ParseUnicodeGroup(StringPiece * s,Regexp::ParseFlags parse_flags,CharClassBuilder * cc,RegexpStatus * status)1512 ParseStatus ParseUnicodeGroup(StringPiece* s, Regexp::ParseFlags parse_flags,
1513                               CharClassBuilder *cc,
1514                               RegexpStatus* status) {
1515   // Decide whether to parse.
1516   if (!(parse_flags & Regexp::UnicodeGroups))
1517     return kParseNothing;
1518   if (s->size() < 2 || (*s)[0] != '\\')
1519     return kParseNothing;
1520   Rune c = (*s)[1];
1521   if (c != 'p' && c != 'P')
1522     return kParseNothing;
1523 
1524   // Committed to parse.  Results:
1525   int sign = +1;  // -1 = negated char class
1526   if (c == 'P')
1527     sign = -1;
1528   StringPiece seq = *s;  // \p{Han} or \pL
1529   StringPiece name;  // Han or L
1530   s->remove_prefix(2);  // '\\', 'p'
1531 
1532   if (!StringPieceToRune(&c, s, status))
1533     return kParseError;
1534   if (c != '{') {
1535     // Name is the bit of string we just skipped over for c.
1536     const char* p = seq.begin() + 2;
1537     name = StringPiece(p, s->begin() - p);
1538   } else {
1539     // Name is in braces. Look for closing }
1540     int end = s->find('}', 0);
1541     if (end == s->npos) {
1542       if (!IsValidUTF8(seq, status))
1543         return kParseError;
1544       status->set_code(kRegexpBadCharRange);
1545       status->set_error_arg(seq);
1546       return kParseError;
1547     }
1548     name = StringPiece(s->begin(), end);  // without '}'
1549     s->remove_prefix(end + 1);  // with '}'
1550     if (!IsValidUTF8(name, status))
1551       return kParseError;
1552   }
1553 
1554   // Chop seq where s now begins.
1555   seq = StringPiece(seq.begin(), s->begin() - seq.begin());
1556 
1557   // Look up group
1558   if (name.size() > 0 && name[0] == '^') {
1559     sign = -sign;
1560     name.remove_prefix(1);  // '^'
1561   }
1562   UGroup *g = LookupUnicodeGroup(name);
1563   if (g == NULL) {
1564     status->set_code(kRegexpBadCharRange);
1565     status->set_error_arg(seq);
1566     return kParseError;
1567   }
1568 
1569   AddUGroup(cc, g, sign, parse_flags);
1570   return kParseOk;
1571 }
1572 
1573 // Parses a character class name like [:alnum:].
1574 // Sets *s to span the remainder of the string.
1575 // Adds the ranges corresponding to the class to ranges.
ParseCCName(StringPiece * s,Regexp::ParseFlags parse_flags,CharClassBuilder * cc,RegexpStatus * status)1576 static ParseStatus ParseCCName(StringPiece* s, Regexp::ParseFlags parse_flags,
1577                                CharClassBuilder *cc,
1578                                RegexpStatus* status) {
1579   // Check begins with [:
1580   const char* p = s->data();
1581   const char* ep = s->data() + s->size();
1582   if (ep - p < 2 || p[0] != '[' || p[1] != ':')
1583     return kParseNothing;
1584 
1585   // Look for closing :].
1586   const char* q;
1587   for (q = p+2; q <= ep-2 && (*q != ':' || *(q+1) != ']'); q++)
1588     ;
1589 
1590   // If no closing :], then ignore.
1591   if (q > ep-2)
1592     return kParseNothing;
1593 
1594   // Got it.  Check that it's valid.
1595   q += 2;
1596   StringPiece name(p, q-p);
1597 
1598   UGroup *g = LookupPosixGroup(name);
1599   if (g == NULL) {
1600     status->set_code(kRegexpBadCharRange);
1601     status->set_error_arg(name);
1602     return kParseError;
1603   }
1604 
1605   s->remove_prefix(name.size());
1606   AddUGroup(cc, g, g->sign, parse_flags);
1607   return kParseOk;
1608 }
1609 
1610 // Parses a character inside a character class.
1611 // There are fewer special characters here than in the rest of the regexp.
1612 // Sets *s to span the remainder of the string.
1613 // Sets *rp to the character.
ParseCCCharacter(StringPiece * s,Rune * rp,const StringPiece & whole_class,RegexpStatus * status)1614 bool Regexp::ParseState::ParseCCCharacter(StringPiece* s, Rune *rp,
1615                                           const StringPiece& whole_class,
1616                                           RegexpStatus* status) {
1617   if (s->size() == 0) {
1618     status->set_code(kRegexpMissingBracket);
1619     status->set_error_arg(whole_class);
1620     return false;
1621   }
1622 
1623   // Allow regular escape sequences even though
1624   // many need not be escaped in this context.
1625   if (s->size() >= 1 && (*s)[0] == '\\')
1626     return ParseEscape(s, rp, status, rune_max_);
1627 
1628   // Otherwise take the next rune.
1629   return StringPieceToRune(rp, s, status) >= 0;
1630 }
1631 
1632 // Parses a character class character, or, if the character
1633 // is followed by a hyphen, parses a character class range.
1634 // For single characters, rr->lo == rr->hi.
1635 // Sets *s to span the remainder of the string.
1636 // Sets *rp to the character.
ParseCCRange(StringPiece * s,RuneRange * rr,const StringPiece & whole_class,RegexpStatus * status)1637 bool Regexp::ParseState::ParseCCRange(StringPiece* s, RuneRange* rr,
1638                                       const StringPiece& whole_class,
1639                                       RegexpStatus* status) {
1640   StringPiece os = *s;
1641   if (!ParseCCCharacter(s, &rr->lo, whole_class, status))
1642     return false;
1643   // [a-] means (a|-), so check for final ].
1644   if (s->size() >= 2 && (*s)[0] == '-' && (*s)[1] != ']') {
1645     s->remove_prefix(1);  // '-'
1646     if (!ParseCCCharacter(s, &rr->hi, whole_class, status))
1647       return false;
1648     if (rr->hi < rr->lo) {
1649       status->set_code(kRegexpBadCharRange);
1650       status->set_error_arg(StringPiece(os.data(), s->data() - os.data()));
1651       return false;
1652     }
1653   } else {
1654     rr->hi = rr->lo;
1655   }
1656   return true;
1657 }
1658 
1659 // Parses a possibly-negated character class expression like [^abx-z[:digit:]].
1660 // Sets *s to span the remainder of the string.
1661 // Sets *out_re to the regexp for the class.
ParseCharClass(StringPiece * s,Regexp ** out_re,RegexpStatus * status)1662 bool Regexp::ParseState::ParseCharClass(StringPiece* s,
1663                                         Regexp** out_re,
1664                                         RegexpStatus* status) {
1665   StringPiece whole_class = *s;
1666   if (s->size() == 0 || (*s)[0] != '[') {
1667     // Caller checked this.
1668     status->set_code(kRegexpInternalError);
1669     status->set_error_arg(NULL);
1670     return false;
1671   }
1672   bool negated = false;
1673   Regexp* re = new Regexp(kRegexpCharClass, flags_ & ~FoldCase);
1674   re->ccb_ = new CharClassBuilder;
1675   s->remove_prefix(1);  // '['
1676   if (s->size() > 0 && (*s)[0] == '^') {
1677     s->remove_prefix(1);  // '^'
1678     negated = true;
1679     if (!(flags_ & ClassNL) || (flags_ & NeverNL)) {
1680       // If NL can't match implicitly, then pretend
1681       // negated classes include a leading \n.
1682       re->ccb_->AddRange('\n', '\n');
1683     }
1684   }
1685   bool first = true;  // ] is okay as first char in class
1686   while (s->size() > 0 && ((*s)[0] != ']' || first)) {
1687     // - is only okay unescaped as first or last in class.
1688     // Except that Perl allows - anywhere.
1689     if ((*s)[0] == '-' && !first && !(flags_&PerlX) &&
1690         (s->size() == 1 || (*s)[1] != ']')) {
1691       StringPiece t = *s;
1692       t.remove_prefix(1);  // '-'
1693       Rune r;
1694       int n = StringPieceToRune(&r, &t, status);
1695       if (n < 0) {
1696         re->Decref();
1697         return false;
1698       }
1699       status->set_code(kRegexpBadCharRange);
1700       status->set_error_arg(StringPiece(s->data(), 1+n));
1701       re->Decref();
1702       return false;
1703     }
1704     first = false;
1705 
1706     // Look for [:alnum:] etc.
1707     if (s->size() > 2 && (*s)[0] == '[' && (*s)[1] == ':') {
1708       switch (ParseCCName(s, flags_, re->ccb_, status)) {
1709         case kParseOk:
1710           continue;
1711         case kParseError:
1712           re->Decref();
1713           return false;
1714         case kParseNothing:
1715           break;
1716       }
1717     }
1718 
1719     // Look for Unicode character group like \p{Han}
1720     if (s->size() > 2 &&
1721         (*s)[0] == '\\' &&
1722         ((*s)[1] == 'p' || (*s)[1] == 'P')) {
1723       switch (ParseUnicodeGroup(s, flags_, re->ccb_, status)) {
1724         case kParseOk:
1725           continue;
1726         case kParseError:
1727           re->Decref();
1728           return false;
1729         case kParseNothing:
1730           break;
1731       }
1732     }
1733 
1734     // Look for Perl character class symbols (extension).
1735     UGroup *g = MaybeParsePerlCCEscape(s, flags_);
1736     if (g != NULL) {
1737       AddUGroup(re->ccb_, g, g->sign, flags_);
1738       continue;
1739     }
1740 
1741     // Otherwise assume single character or simple range.
1742     RuneRange rr;
1743     if (!ParseCCRange(s, &rr, whole_class, status)) {
1744       re->Decref();
1745       return false;
1746     }
1747     // AddRangeFlags is usually called in response to a class like
1748     // \p{Foo} or [[:foo:]]; for those, it filters \n out unless
1749     // Regexp::ClassNL is set.  In an explicit range or singleton
1750     // like we just parsed, we do not filter \n out, so set ClassNL
1751     // in the flags.
1752     re->ccb_->AddRangeFlags(rr.lo, rr.hi, flags_ | Regexp::ClassNL);
1753   }
1754   if (s->size() == 0) {
1755     status->set_code(kRegexpMissingBracket);
1756     status->set_error_arg(whole_class);
1757     re->Decref();
1758     return false;
1759   }
1760   s->remove_prefix(1);  // ']'
1761 
1762   if (negated)
1763     re->ccb_->Negate();
1764   re->ccb_->RemoveAbove(rune_max_);
1765 
1766   *out_re = re;
1767   return true;
1768 }
1769 
1770 // Is this a valid capture name?  [A-Za-z0-9_]+
1771 // PCRE limits names to 32 bytes.
1772 // Python rejects names starting with digits.
1773 // We don't enforce either of those.
IsValidCaptureName(const StringPiece & name)1774 static bool IsValidCaptureName(const StringPiece& name) {
1775   if (name.size() == 0)
1776     return false;
1777   for (int i = 0; i < name.size(); i++) {
1778     int c = name[i];
1779     if (('0' <= c && c <= '9') ||
1780         ('a' <= c && c <= 'z') ||
1781         ('A' <= c && c <= 'Z') ||
1782         c == '_')
1783       continue;
1784     return false;
1785   }
1786   return true;
1787 }
1788 
1789 // Parses a Perl flag setting or non-capturing group or both,
1790 // like (?i) or (?: or (?i:.  Removes from s, updates parse state.
1791 // The caller must check that s begins with "(?".
1792 // Returns true on success.  If the Perl flag is not
1793 // well-formed or not supported, sets status_ and returns false.
ParsePerlFlags(StringPiece * s)1794 bool Regexp::ParseState::ParsePerlFlags(StringPiece* s) {
1795   StringPiece t = *s;
1796 
1797   // Caller is supposed to check this.
1798   if (!(flags_ & PerlX) || t.size() < 2 || t[0] != '(' || t[1] != '?') {
1799     LOG(DFATAL) << "Bad call to ParseState::ParsePerlFlags";
1800     status_->set_code(kRegexpInternalError);
1801     return false;
1802   }
1803 
1804   t.remove_prefix(2);  // "(?"
1805 
1806   // Check for named captures, first introduced in Python's regexp library.
1807   // As usual, there are three slightly different syntaxes:
1808   //
1809   //   (?P<name>expr)   the original, introduced by Python
1810   //   (?<name>expr)    the .NET alteration, adopted by Perl 5.10
1811   //   (?'name'expr)    another .NET alteration, adopted by Perl 5.10
1812   //
1813   // Perl 5.10 gave in and implemented the Python version too,
1814   // but they claim that the last two are the preferred forms.
1815   // PCRE and languages based on it (specifically, PHP and Ruby)
1816   // support all three as well.  EcmaScript 4 uses only the Python form.
1817   //
1818   // In both the open source world (via Code Search) and the
1819   // Google source tree, (?P<expr>name) is the dominant form,
1820   // so that's the one we implement.  One is enough.
1821   if (t.size() > 2 && t[0] == 'P' && t[1] == '<') {
1822     // Pull out name.
1823     int end = t.find('>', 2);
1824     if (end == t.npos) {
1825       if (!IsValidUTF8(*s, status_))
1826         return false;
1827       status_->set_code(kRegexpBadNamedCapture);
1828       status_->set_error_arg(*s);
1829       return false;
1830     }
1831 
1832     // t is "P<name>...", t[end] == '>'
1833     StringPiece capture(t.begin()-2, end+3);  // "(?P<name>"
1834     StringPiece name(t.begin()+2, end-2);     // "name"
1835     if (!IsValidUTF8(name, status_))
1836       return false;
1837     if (!IsValidCaptureName(name)) {
1838       status_->set_code(kRegexpBadNamedCapture);
1839       status_->set_error_arg(capture);
1840       return false;
1841     }
1842 
1843     if (!DoLeftParen(name)) {
1844       // DoLeftParen's failure set status_.
1845       return false;
1846     }
1847 
1848     s->remove_prefix(capture.end() - s->begin());
1849     return true;
1850   }
1851 
1852   bool negated = false;
1853   bool sawflags = false;
1854   int nflags = flags_;
1855   Rune c;
1856   for (bool done = false; !done; ) {
1857     if (t.size() == 0)
1858       goto BadPerlOp;
1859     if (StringPieceToRune(&c, &t, status_) < 0)
1860       return false;
1861     switch (c) {
1862       default:
1863         goto BadPerlOp;
1864 
1865       // Parse flags.
1866       case 'i':
1867         sawflags = true;
1868         if (negated)
1869           nflags &= ~FoldCase;
1870         else
1871           nflags |= FoldCase;
1872         break;
1873 
1874       case 'm':  // opposite of our OneLine
1875         sawflags = true;
1876         if (negated)
1877           nflags |= OneLine;
1878         else
1879           nflags &= ~OneLine;
1880         break;
1881 
1882       case 's':
1883         sawflags = true;
1884         if (negated)
1885           nflags &= ~DotNL;
1886         else
1887           nflags |= DotNL;
1888         break;
1889 
1890       case 'U':
1891         sawflags = true;
1892         if (negated)
1893           nflags &= ~NonGreedy;
1894         else
1895           nflags |= NonGreedy;
1896         break;
1897 
1898       // Negation
1899       case '-':
1900         if (negated)
1901           goto BadPerlOp;
1902         negated = true;
1903         sawflags = false;
1904         break;
1905 
1906       // Open new group.
1907       case ':':
1908         if (!DoLeftParenNoCapture()) {
1909           // DoLeftParenNoCapture's failure set status_.
1910           return false;
1911         }
1912         done = true;
1913         break;
1914 
1915       // Finish flags.
1916       case ')':
1917         done = true;
1918         break;
1919     }
1920   }
1921 
1922   if (negated && !sawflags)
1923     goto BadPerlOp;
1924 
1925   flags_ = static_cast<Regexp::ParseFlags>(nflags);
1926   *s = t;
1927   return true;
1928 
1929 BadPerlOp:
1930   status_->set_code(kRegexpBadPerlOp);
1931   status_->set_error_arg(StringPiece(s->begin(), t.begin() - s->begin()));
1932   return false;
1933 }
1934 
1935 // Converts latin1 (assumed to be encoded as Latin1 bytes)
1936 // into UTF8 encoding in string.
1937 // Can't use EncodingUtils::EncodeLatin1AsUTF8 because it is
1938 // deprecated and because it rejects code points 0x80-0x9F.
ConvertLatin1ToUTF8(const StringPiece & latin1,string * utf)1939 void ConvertLatin1ToUTF8(const StringPiece& latin1, string* utf) {
1940   char buf[UTFmax];
1941 
1942   utf->clear();
1943   for (int i = 0; i < latin1.size(); i++) {
1944     Rune r = latin1[i] & 0xFF;
1945     int n = runetochar(buf, &r);
1946     utf->append(buf, n);
1947   }
1948 }
1949 
1950 // Parses the regular expression given by s,
1951 // returning the corresponding Regexp tree.
1952 // The caller must Decref the return value when done with it.
1953 // Returns NULL on error.
Parse(const StringPiece & s,ParseFlags global_flags,RegexpStatus * status)1954 Regexp* Regexp::Parse(const StringPiece& s, ParseFlags global_flags,
1955                       RegexpStatus* status) {
1956   // Make status non-NULL (easier on everyone else).
1957   RegexpStatus xstatus;
1958   if (status == NULL)
1959     status = &xstatus;
1960 
1961   ParseState ps(global_flags, s, status);
1962   StringPiece t = s;
1963 
1964   // Convert regexp to UTF-8 (easier on the rest of the parser).
1965   if (global_flags & Latin1) {
1966     string* tmp = new string;
1967     ConvertLatin1ToUTF8(t, tmp);
1968     status->set_tmp(tmp);
1969     t = *tmp;
1970   }
1971 
1972   if (global_flags & Literal) {
1973     // Special parse loop for literal string.
1974     while (t.size() > 0) {
1975       Rune r;
1976       if (StringPieceToRune(&r, &t, status) < 0)
1977         return NULL;
1978       if (!ps.PushLiteral(r))
1979         return NULL;
1980     }
1981     return ps.DoFinish();
1982   }
1983 
1984   StringPiece lastunary = NULL;
1985   while (t.size() > 0) {
1986     StringPiece isunary = NULL;
1987     switch (t[0]) {
1988       default: {
1989         Rune r;
1990         if (StringPieceToRune(&r, &t, status) < 0)
1991           return NULL;
1992         if (!ps.PushLiteral(r))
1993           return NULL;
1994         break;
1995       }
1996 
1997       case '(':
1998         // "(?" introduces Perl escape.
1999         if ((ps.flags() & PerlX) && (t.size() >= 2 && t[1] == '?')) {
2000           // Flag changes and non-capturing groups.
2001           if (!ps.ParsePerlFlags(&t))
2002             return NULL;
2003           break;
2004         }
2005         if (ps.flags() & NeverCapture) {
2006           if (!ps.DoLeftParenNoCapture())
2007             return NULL;
2008         } else {
2009           if (!ps.DoLeftParen(NULL))
2010             return NULL;
2011         }
2012         t.remove_prefix(1);  // '('
2013         break;
2014 
2015       case '|':
2016         if (!ps.DoVerticalBar())
2017           return NULL;
2018         t.remove_prefix(1);  // '|'
2019         break;
2020 
2021       case ')':
2022         if (!ps.DoRightParen())
2023           return NULL;
2024         t.remove_prefix(1);  // ')'
2025         break;
2026 
2027       case '^':  // Beginning of line.
2028         if (!ps.PushCarat())
2029           return NULL;
2030         t.remove_prefix(1);  // '^'
2031         break;
2032 
2033       case '$':  // End of line.
2034         if (!ps.PushDollar())
2035           return NULL;
2036         t.remove_prefix(1);  // '$'
2037         break;
2038 
2039       case '.':  // Any character (possibly except newline).
2040         if (!ps.PushDot())
2041           return NULL;
2042         t.remove_prefix(1);  // '.'
2043         break;
2044 
2045       case '[': {  // Character class.
2046         Regexp* re;
2047         if (!ps.ParseCharClass(&t, &re, status))
2048           return NULL;
2049         if (!ps.PushRegexp(re))
2050           return NULL;
2051         break;
2052       }
2053 
2054       case '*': {  // Zero or more.
2055         RegexpOp op;
2056         op = kRegexpStar;
2057         goto Rep;
2058       case '+':  // One or more.
2059         op = kRegexpPlus;
2060         goto Rep;
2061       case '?':  // Zero or one.
2062         op = kRegexpQuest;
2063         goto Rep;
2064       Rep:
2065         StringPiece opstr = t;
2066         bool nongreedy = false;
2067         t.remove_prefix(1);  // '*' or '+' or '?'
2068         if (ps.flags() & PerlX) {
2069           if (t.size() > 0 && t[0] == '?') {
2070             nongreedy = true;
2071             t.remove_prefix(1);  // '?'
2072           }
2073           if (lastunary.size() > 0) {
2074             // In Perl it is not allowed to stack repetition operators:
2075             //   a** is a syntax error, not a double-star.
2076             // (and a++ means something else entirely, which we don't support!)
2077             status->set_code(kRegexpRepeatOp);
2078             status->set_error_arg(StringPiece(lastunary.begin(),
2079                                               t.begin() - lastunary.begin()));
2080             return NULL;
2081           }
2082         }
2083         opstr.set(opstr.data(), t.data() - opstr.data());
2084         if (!ps.PushRepeatOp(op, opstr, nongreedy))
2085           return NULL;
2086         isunary = opstr;
2087         break;
2088       }
2089 
2090       case '{': {  // Counted repetition.
2091         int lo, hi;
2092         StringPiece opstr = t;
2093         if (!MaybeParseRepetition(&t, &lo, &hi)) {
2094           // Treat like a literal.
2095           if (!ps.PushLiteral('{'))
2096             return NULL;
2097           t.remove_prefix(1);  // '{'
2098           break;
2099         }
2100         bool nongreedy = false;
2101         if (ps.flags() & PerlX) {
2102           if (t.size() > 0 && t[0] == '?') {
2103             nongreedy = true;
2104             t.remove_prefix(1);  // '?'
2105           }
2106           if (lastunary.size() > 0) {
2107             // Not allowed to stack repetition operators.
2108             status->set_code(kRegexpRepeatOp);
2109             status->set_error_arg(StringPiece(lastunary.begin(),
2110                                               t.begin() - lastunary.begin()));
2111             return NULL;
2112           }
2113         }
2114         opstr.set(opstr.data(), t.data() - opstr.data());
2115         if (!ps.PushRepetition(lo, hi, opstr, nongreedy))
2116           return NULL;
2117         isunary = opstr;
2118         break;
2119       }
2120 
2121       case '\\': {  // Escaped character or Perl sequence.
2122         // \b and \B: word boundary or not
2123         if ((ps.flags() & Regexp::PerlB) &&
2124             t.size() >= 2 && (t[1] == 'b' || t[1] == 'B')) {
2125           if (!ps.PushWordBoundary(t[1] == 'b'))
2126             return NULL;
2127           t.remove_prefix(2);  // '\\', 'b'
2128           break;
2129         }
2130 
2131         if ((ps.flags() & Regexp::PerlX) && t.size() >= 2) {
2132           if (t[1] == 'A') {
2133             if (!ps.PushSimpleOp(kRegexpBeginText))
2134               return NULL;
2135             t.remove_prefix(2);  // '\\', 'A'
2136             break;
2137           }
2138           if (t[1] == 'z') {
2139             if (!ps.PushSimpleOp(kRegexpEndText))
2140               return NULL;
2141             t.remove_prefix(2);  // '\\', 'z'
2142             break;
2143           }
2144           // Do not recognize \Z, because this library can't
2145           // implement the exact Perl/PCRE semantics.
2146           // (This library treats "(?-m)$" as \z, even though
2147           // in Perl and PCRE it is equivalent to \Z.)
2148 
2149           if (t[1] == 'C') {  // \C: any byte [sic]
2150             if (!ps.PushSimpleOp(kRegexpAnyByte))
2151               return NULL;
2152             t.remove_prefix(2);  // '\\', 'C'
2153             break;
2154           }
2155 
2156           if (t[1] == 'Q') {  // \Q ... \E: the ... is always literals
2157             t.remove_prefix(2);  // '\\', 'Q'
2158             while (t.size() > 0) {
2159               if (t.size() >= 2 && t[0] == '\\' && t[1] == 'E') {
2160                 t.remove_prefix(2);  // '\\', 'E'
2161                 break;
2162               }
2163               Rune r;
2164               if (StringPieceToRune(&r, &t, status) < 0)
2165                 return NULL;
2166               if (!ps.PushLiteral(r))
2167                 return NULL;
2168             }
2169             break;
2170           }
2171         }
2172 
2173         if (t.size() >= 2 && (t[1] == 'p' || t[1] == 'P')) {
2174           Regexp* re = new Regexp(kRegexpCharClass, ps.flags() & ~FoldCase);
2175           re->ccb_ = new CharClassBuilder;
2176           switch (ParseUnicodeGroup(&t, ps.flags(), re->ccb_, status)) {
2177             case kParseOk:
2178               if (!ps.PushRegexp(re))
2179                 return NULL;
2180               goto Break2;
2181             case kParseError:
2182               re->Decref();
2183               return NULL;
2184             case kParseNothing:
2185               re->Decref();
2186               break;
2187           }
2188         }
2189 
2190         UGroup *g = MaybeParsePerlCCEscape(&t, ps.flags());
2191         if (g != NULL) {
2192           Regexp* re = new Regexp(kRegexpCharClass, ps.flags() & ~FoldCase);
2193           re->ccb_ = new CharClassBuilder;
2194           AddUGroup(re->ccb_, g, g->sign, ps.flags());
2195           if (!ps.PushRegexp(re))
2196             return NULL;
2197           break;
2198         }
2199 
2200         Rune r;
2201         if (!ParseEscape(&t, &r, status, ps.rune_max()))
2202           return NULL;
2203         if (!ps.PushLiteral(r))
2204           return NULL;
2205         break;
2206       }
2207     }
2208   Break2:
2209     lastunary = isunary;
2210   }
2211   return ps.DoFinish();
2212 }
2213 
2214 }  // namespace re2
2215