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
25namespace 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
44class Regexp::ParseState {
45 public:
46  ParseState(ParseFlags flags, const StringPiece& whole_regexp,
47             RegexpStatus* status);
48  ~ParseState();
49
50  ParseFlags flags() { return flags_; }
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
151private:
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.
163const RegexpOp kLeftParen = static_cast<RegexpOp>(kMaxRegexpOp+1);
164const RegexpOp kVerticalBar = static_cast<RegexpOp>(kMaxRegexpOp+2);
165
166Regexp::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.
178Regexp::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.
192Regexp* 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.
209bool 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.
243CaseFold* 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.
271Rune 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('?') = '?'
306Rune 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.
316static 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.
368bool 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.
398bool 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.
406bool Regexp::ParseState::PushWordBoundary(bool word) {
407  if (word)
408    return PushSimpleOp(kRegexpWordBoundary);
409  return PushSimpleOp(kRegexpNoWordBoundary);
410}
411
412// Pushes a $ onto the stack.
413bool 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.
427bool 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.
439bool 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.
447bool 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.
468bool 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.
497bool 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.
503bool 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.
512bool 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.
519static 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.
526bool 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.
588bool 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.
627Regexp* 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().
642Regexp* 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.
658Regexp* 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().
687Rune* 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.
710void 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.
801const int kFactorAlternationMaxDepth = 8;
802
803int Regexp::FactorAlternation(
804    Regexp** sub, int n,
805    Regexp::ParseFlags altflags) {
806  return FactorAlternationRecursive(sub, n, altflags,
807                                    kFactorAlternationMaxDepth);
808}
809
810int 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).
997void 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.
1040void 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.
1052void 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.
1071bool 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.
1122static 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.
1150static 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.
1187static 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.
1204static 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?
1215static 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.
1222static 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.
1236static 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
1375BadEscape:
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.
1384void 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.
1406static 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
1416static URange16 any16[] = { { 0, 65535 } };
1417static URange32 any32[] = { { 65536, Runemax } };
1418static UGroup anygroup = { "Any", +1, any16, 1, any32, 1 };
1419
1420// Look for a POSIX group with the given name (e.g., "[:^alpha:]")
1421static UGroup* LookupPosixGroup(const StringPiece& name) {
1422  return LookupGroup(name, posix_groups, num_posix_groups);
1423}
1424
1425static 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")
1430static 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.
1438static 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.
1489UGroup* 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
1504enum 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).
1512ParseStatus 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.
1576static 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.
1614bool 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.
1637bool 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.
1662bool 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.
1774static 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.
1794bool 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
1929BadPerlOp:
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.
1939void 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.
1954Regexp* 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