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