12ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Copyright 2006 The RE2 Authors.  All Rights Reserved.
22ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Use of this source code is governed by a BSD-style
32ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// license that can be found in the LICENSE file.
42ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
52ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Helper class for traversing Regexps without recursion.
62ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Clients should declare their own subclasses that override
72ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// the PreVisit and PostVisit methods, which are called before
82ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// and after visiting the subexpressions.
92ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
102ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Not quite the Visitor pattern, because (among other things)
112ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// the Visitor pattern is recursive.
122ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
132ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson#ifndef RE2_WALKER_INL_H__
142ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson#define RE2_WALKER_INL_H__
152ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
162ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson#include "re2/regexp.h"
172ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
182ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsonnamespace re2 {
192ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
202ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsontemplate<typename T> struct WalkState;
212ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
222ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsontemplate<typename T> class Regexp::Walker {
232ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson public:
242ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  Walker();
252ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  virtual ~Walker();
262ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
272ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // Virtual method called before visiting re's children.
282ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // PreVisit passes ownership of its return value to its caller.
292ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // The Arg* that PreVisit returns will be passed to PostVisit as pre_arg
302ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // and passed to the child PreVisits and PostVisits as parent_arg.
312ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // At the top-most Regexp, parent_arg is arg passed to walk.
322ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // If PreVisit sets *stop to true, the walk does not recurse
332ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // into the children.  Instead it behaves as though the return
342ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // value from PreVisit is the return value from PostVisit.
352ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // The default PreVisit returns parent_arg.
362ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  virtual T PreVisit(Regexp* re, T parent_arg, bool* stop);
372ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
382ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // Virtual method called after visiting re's children.
392ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // The pre_arg is the T that PreVisit returned.
402ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // The child_args is a vector of the T that the child PostVisits returned.
412ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // PostVisit takes ownership of pre_arg.
422ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // PostVisit takes ownership of the Ts
432ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // in *child_args, but not the vector itself.
442ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // PostVisit passes ownership of its return value
452ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // to its caller.
462ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // The default PostVisit simply returns pre_arg.
472ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  virtual T PostVisit(Regexp* re, T parent_arg, T pre_arg,
482ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson                      T* child_args, int nchild_args);
492ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
502ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // Virtual method called to copy a T,
512ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // when Walk notices that more than one child is the same re.
522ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  virtual T Copy(T arg);
532ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
542ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // Virtual method called to do a "quick visit" of the re,
552ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // but not its children.  Only called once the visit budget
562ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // has been used up and we're trying to abort the walk
572ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // as quickly as possible.  Should return a value that
582ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // makes sense for the parent PostVisits still to be run.
592ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // This function is (hopefully) only called by
602ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // WalkExponential, but must be implemented by all clients,
612ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // just in case.
622ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  virtual T ShortVisit(Regexp* re, T parent_arg) = 0;
632ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
642ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // Walks over a regular expression.
652ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // Top_arg is passed as parent_arg to PreVisit and PostVisit of re.
662ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // Returns the T returned by PostVisit on re.
672ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  T Walk(Regexp* re, T top_arg);
682ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
692ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // Like Walk, but doesn't use Copy.  This can lead to
702ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // exponential runtimes on cross-linked Regexps like the
712ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // ones generated by Simplify.  To help limit this,
722ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // at most max_visits nodes will be visited and then
732ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // the walk will be cut off early.
742ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // If the walk *is* cut off early, ShortVisit(re)
752ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // will be called on regexps that cannot be fully
762ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // visited rather than calling PreVisit/PostVisit.
772ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  T WalkExponential(Regexp* re, T top_arg, int max_visits);
782ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
792ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // Clears the stack.  Should never be necessary, since
802ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // Walk always enters and exits with an empty stack.
812ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // Logs DFATAL if stack is not already clear.
822ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  void Reset();
832ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
842ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // Returns whether walk was cut off.
852ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  bool stopped_early() { return stopped_early_; }
862ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
872ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson private:
882ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // Walk state for the entire traversal.
892ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  stack<WalkState<T> >* stack_;
902ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  bool stopped_early_;
912ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  int max_visits_;
922ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
932ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  T WalkInternal(Regexp* re, T top_arg, bool use_copy);
942ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
952ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  DISALLOW_EVIL_CONSTRUCTORS(Walker);
962ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson};
972ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
982ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsontemplate<typename T> T Regexp::Walker<T>::PreVisit(Regexp* re,
992ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson                                                   T parent_arg,
1002ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson                                                   bool* stop) {
1012ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  return parent_arg;
1022ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson}
1032ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
1042ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsontemplate<typename T> T Regexp::Walker<T>::PostVisit(Regexp* re,
1052ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson                                                    T parent_arg,
1062ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson                                                    T pre_arg,
1072ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson                                                    T* child_args,
1082ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson                                                    int nchild_args) {
1092ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  return pre_arg;
1102ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson}
1112ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
1122ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsontemplate<typename T> T Regexp::Walker<T>::Copy(T arg) {
1132ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  return arg;
1142ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson}
1152ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
1162ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// State about a single level in the traversal.
1172ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsontemplate<typename T> struct WalkState {
1182ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  WalkState<T>(Regexp* re, T parent)
1192ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    : re(re),
1202ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson      n(-1),
1212ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson      parent_arg(parent),
1222ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson      child_args(NULL) { }
1232ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
1242ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  Regexp* re;  // The regexp
1252ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  int n;  // The index of the next child to process; -1 means need to PreVisit
1262ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  T parent_arg;  // Accumulated arguments.
1272ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  T pre_arg;
1282ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  T child_arg;  // One-element buffer for child_args.
1292ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  T* child_args;
1302ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson};
1312ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
1322ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsontemplate<typename T> Regexp::Walker<T>::Walker() {
1332ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  stack_ = new stack<WalkState<T> >;
1342ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  stopped_early_ = false;
1352ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson}
1362ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
1372ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsontemplate<typename T> Regexp::Walker<T>::~Walker() {
1382ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  Reset();
1392ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  delete stack_;
1402ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson}
1412ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
1422ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Clears the stack.  Should never be necessary, since
1432ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Walk always enters and exits with an empty stack.
1442ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Logs DFATAL if stack is not already clear.
1452ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsontemplate<typename T> void Regexp::Walker<T>::Reset() {
1462ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  if (stack_ && stack_->size() > 0) {
1472ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    LOG(DFATAL) << "Stack not empty.";
1482ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    while (stack_->size() > 0) {
1492ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson      delete stack_->top().child_args;
1502ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson      stack_->pop();
1512ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    }
1522ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  }
1532ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson}
1542ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
1552ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsontemplate<typename T> T Regexp::Walker<T>::WalkInternal(Regexp* re, T top_arg,
1562ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson                                                       bool use_copy) {
1572ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  Reset();
1582ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
1592ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  if (re == NULL) {
1602ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    LOG(DFATAL) << "Walk NULL";
1612ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    return top_arg;
1622ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  }
1632ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
1642ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  stack_->push(WalkState<T>(re, top_arg));
1652ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
1662ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  WalkState<T>* s;
1672ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  for (;;) {
1682ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    T t;
1692ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    s = &stack_->top();
1702ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    Regexp* re = s->re;
1712ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    switch (s->n) {
1722ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson      case -1: {
1732ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson        if (--max_visits_ < 0) {
1742ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson          stopped_early_ = true;
1752ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson          t = ShortVisit(re, s->parent_arg);
1762ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson          break;
1772ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson        }
1782ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson        bool stop = false;
1792ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson        s->pre_arg = PreVisit(re, s->parent_arg, &stop);
1802ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson        if (stop) {
1812ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson          t = s->pre_arg;
1822ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson          break;
1832ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson        }
1842ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson        s->n = 0;
1852ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson        s->child_args = NULL;
1862ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson        if (re->nsub_ == 1)
1872ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson          s->child_args = &s->child_arg;
1882ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson        else if (re->nsub_ > 1)
1892ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson          s->child_args = new T[re->nsub_];
1902ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson        // Fall through.
1912ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson      }
1922ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson      default: {
1932ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson        if (re->nsub_ > 0) {
1942ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson          Regexp** sub = re->sub();
1952ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson          if (s->n < re->nsub_) {
1962ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson            if (use_copy && s->n > 0 && sub[s->n - 1] == sub[s->n]) {
1972ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson              s->child_args[s->n] = Copy(s->child_args[s->n - 1]);
1982ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson              s->n++;
1992ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson            } else {
2002ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson              stack_->push(WalkState<T>(sub[s->n], s->pre_arg));
2012ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson            }
2022ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson            continue;
2032ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson          }
2042ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson        }
2052ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
2062ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson        t = PostVisit(re, s->parent_arg, s->pre_arg, s->child_args, s->n);
2072ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson        if (re->nsub_ > 1)
2082ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson          delete[] s->child_args;
2092ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson        break;
2102ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson      }
2112ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    }
2122ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
2132ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    // We've finished stack_->top().
2142ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    // Update next guy down.
2152ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    stack_->pop();
2162ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    if (stack_->size() == 0)
2172ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson      return t;
2182ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    s = &stack_->top();
2192ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    if (s->child_args != NULL)
2202ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson      s->child_args[s->n] = t;
2212ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    else
2222ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson      s->child_arg = t;
2232ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson    s->n++;
2242ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  }
2252ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson}
2262ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
2272ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsontemplate<typename T> T Regexp::Walker<T>::Walk(Regexp* re, T top_arg) {
2282ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // Without the exponential walking behavior,
2292ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // this budget should be more than enough for any
2302ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // regexp, and yet not enough to get us in trouble
2312ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  // as far as CPU time.
2322ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  max_visits_ = 1000000;
2332ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  return WalkInternal(re, top_arg, true);
2342ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson}
2352ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
2362ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsontemplate<typename T> T Regexp::Walker<T>::WalkExponential(Regexp* re, T top_arg,
2372ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson                                                          int max_visits) {
2382ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  max_visits_ = max_visits;
2392ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson  return WalkInternal(re, top_arg, false);
2402ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson}
2412ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
2422ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson}  // namespace re2
2432ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson
2442ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson#endif  // RE2_WALKER_INL_H__
245