1 // Copyright 2008 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.
5 // A DFA (deterministic finite automaton)-based regular expression search.
7 // The DFA search has two main parts: the construction of the automaton,
8 // which is represented by a graph of State structures, and the execution
9 // of the automaton over a given input string.
11 // The basic idea is that the State graph is constructed so that the
12 // execution can simply start with a state s, and then for each byte c in
13 // the input string, execute "s = s->next[c]", checking at each point whether
14 // the current s represents a matching state.
16 // The simple explanation just given does convey the essence of this code,
17 // but it omits the details of how the State graph gets constructed as well
18 // as some performance-driven optimizations to the execution of the automaton.
19 // All these details are explained in the comments for the code following
20 // the definition of class DFA.
22 // See http://swtch.com/~rsc/regexp/ for a very bare-bones equivalent.
25 #include "re2/stringpiece.h"
26 #include "util/atomicops.h"
27 #include "util/flags.h"
28 #include "util/sparse_set.h"
30 #define NO_THREAD_SAFETY_ANALYSIS
32 DEFINE_bool(re2_dfa_bail_when_slow, true,
33 "Whether the RE2 DFA should bail out early "
34 "if the NFA would be faster (for testing).");
38 #if !defined(__linux__) /* only Linux seems to have memrchr */
39 static void* memrchr(const void* s, int c, size_t n) {
40 const unsigned char* p = (const unsigned char*)s;
41 for (p += n; n > 0; n--)
49 // Changing this to true compiles in prints that trace execution of the DFA.
50 // Generates a lot of output -- only useful for debugging.
51 static const bool DebugDFA = false;
53 // A DFA implementation of a regular expression program.
54 // Since this is entirely a forward declaration mandated by C++,
55 // some of the comments here are better understood after reading
56 // the comments in the sections that follow the DFA definition.
59 DFA(Prog* prog, Prog::MatchKind kind, int64 max_mem);
61 bool ok() const { return !init_failed_; }
62 Prog::MatchKind kind() { return kind_; }
64 // Searches for the regular expression in text, which is considered
65 // as a subsection of context for the purposes of interpreting flags
66 // like ^ and $ and \A and \z.
67 // Returns whether a match was found.
68 // If a match is found, sets *ep to the end point of the best match in text.
69 // If "anchored", the match must begin at the start of text.
70 // If "want_earliest_match", the match that ends first is used, not
71 // necessarily the best one.
72 // If "run_forward" is true, the DFA runs from text.begin() to text.end().
73 // If it is false, the DFA runs from text.end() to text.begin(),
74 // returning the leftmost end of the match instead of the rightmost one.
75 // If the DFA cannot complete the search (for example, if it is out of
76 // memory), it sets *failed and returns false.
77 bool Search(const StringPiece& text, const StringPiece& context,
78 bool anchored, bool want_earliest_match, bool run_forward,
79 bool* failed, const char** ep, vector<int>* matches);
81 // Builds out all states for the entire DFA. FOR TESTING ONLY
82 // Returns number of states.
85 // Computes min and max for matching strings. Won't return strings
86 // bigger than maxlen.
87 bool PossibleMatchRange(string* min, string* max, int maxlen);
89 // These data structures are logically private, but C++ makes it too
90 // difficult to mark them as such.
95 // A single DFA state. The DFA is represented as a graph of these
96 // States, linked by the next_ pointers. If in state s and reading
97 // byte c, the next state should be s->next_[c].
99 inline bool IsMatch() const { return flag_ & kFlagMatch; }
100 void SaveMatch(vector<int>* v);
102 int* inst_; // Instruction pointers in the state.
103 int ninst_; // # of inst_ pointers.
104 uint flag_; // Empty string bitfield flags in effect on the way
105 // into this state, along with kFlagMatch if this
106 // is a matching state.
107 State** next_; // Outgoing arrows from State,
108 // one per input byte class
112 kByteEndText = 256, // imaginary byte at end of text
114 kFlagEmptyMask = 0xFFF, // State.flag_: bits holding kEmptyXXX flags
115 kFlagMatch = 0x1000, // State.flag_: this is a matching state
116 kFlagLastWord = 0x2000, // State.flag_: last byte was a word char
117 kFlagNeedShift = 16, // needed kEmpty bits are or'ed in shifted left
121 // STL function structures for use with unordered_set.
123 bool operator()(const State* a, const State* b) const {
126 if (a == NULL || b == NULL)
128 if (a->ninst_ != b->ninst_)
130 if (a->flag_ != b->flag_)
132 for (int i = 0; i < a->ninst_; i++)
133 if (a->inst_[i] != b->inst_[i])
135 return true; // they're equal
140 size_t operator()(const State* a) const {
143 const char* s = reinterpret_cast<const char*>(a->inst_);
144 int len = a->ninst_ * sizeof a->inst_[0];
145 if (sizeof(size_t) == sizeof(uint32))
146 return Hash32StringWithSeed(s, len, a->flag_);
148 return Hash64StringWithSeed(s, len, a->flag_);
151 // Less than operator.
152 bool operator()(const State* a, const State* b) const {
155 if (a == NULL || b == NULL)
157 if (a->ninst_ != b->ninst_)
158 return a->ninst_ < b->ninst_;
159 if (a->flag_ != b->flag_)
160 return a->flag_ < b->flag_;
161 for (int i = 0; i < a->ninst_; ++i)
162 if (a->inst_[i] != b->inst_[i])
163 return a->inst_[i] < b->inst_[i];
164 return false; // they're equal
166 // The two public members are required by msvc. 4 and 8 are default values.
167 // Reference: http://msdn.microsoft.com/en-us/library/1s1byw77.aspx
168 static const size_t bucket_size = 4;
169 static const size_t min_buckets = 8;
174 typedef unordered_set<State*, StateHash> StateSet;
176 typedef unordered_set<State*, StateHash, StateEqual> StateSet;
181 // Special "firstbyte" values for a state. (Values >= 0 denote actual bytes.)
183 kFbUnknown = -1, // No analysis has been performed.
184 kFbMany = -2, // Many bytes will lead out of this state.
185 kFbNone = -3, // No bytes lead out of this state.
189 // Indices into start_ for unanchored searches.
190 // Add kStartAnchored for anchored searches.
191 kStartBeginText = 0, // text at beginning of context
192 kStartBeginLine = 2, // text at beginning of line
193 kStartAfterWordChar = 4, // text follows a word character
194 kStartAfterNonWordChar = 6, // text follows non-word character
200 // Resets the DFA State cache, flushing all saved State* information.
201 // Releases and reacquires cache_mutex_ via cache_lock, so any
202 // State* existing before the call are not valid after the call.
203 // Use a StateSaver to preserve important states across the call.
204 // cache_mutex_.r <= L < mutex_
205 // After: cache_mutex_.w <= L < mutex_
206 void ResetCache(RWLocker* cache_lock);
208 // Looks up and returns the State corresponding to a Workq.
210 State* WorkqToCachedState(Workq* q, uint flag);
212 // Looks up and returns a State matching the inst, ninst, and flag.
214 State* CachedState(int* inst, int ninst, uint flag);
216 // Clear the cache entirely.
217 // Must hold cache_mutex_.w or be in destructor.
220 // Converts a State into a Workq: the opposite of WorkqToCachedState.
222 static void StateToWorkq(State* s, Workq* q);
224 // Runs a State on a given byte, returning the next state.
225 State* RunStateOnByteUnlocked(State*, int); // cache_mutex_.r <= L < mutex_
226 State* RunStateOnByte(State*, int); // L >= mutex_
228 // Runs a Workq on a given byte followed by a set of empty-string flags,
229 // producing a new Workq in nq. If a match instruction is encountered,
230 // sets *ismatch to true.
232 void RunWorkqOnByte(Workq* q, Workq* nq,
233 int c, uint flag, bool* ismatch,
234 Prog::MatchKind kind,
237 // Runs a Workq on a set of empty-string flags, producing a new Workq in nq.
239 void RunWorkqOnEmptyString(Workq* q, Workq* nq, uint flag);
241 // Adds the instruction id to the Workq, following empty arrows
242 // according to flag.
244 void AddToQueue(Workq* q, int id, uint flag);
246 // For debugging, returns a text representation of State.
247 static string DumpState(State* state);
249 // For debugging, returns a text representation of a Workq.
250 static string DumpWorkq(Workq* q);
253 struct SearchParams {
254 SearchParams(const StringPiece& text, const StringPiece& context,
255 RWLocker* cache_lock)
256 : text(text), context(context),
258 want_earliest_match(false),
261 firstbyte(kFbUnknown),
262 cache_lock(cache_lock),
270 bool want_earliest_match;
274 RWLocker *cache_lock;
275 bool failed; // "out" parameter: whether search gave up
276 const char* ep; // "out" parameter: end pointer for match
277 vector<int>* matches;
280 DISALLOW_EVIL_CONSTRUCTORS(SearchParams);
283 // Before each search, the parameters to Search are analyzed by
284 // AnalyzeSearch to determine the state in which to start and the
285 // "firstbyte" for that state, if any.
287 StartInfo() : start(NULL), firstbyte(kFbUnknown) { }
289 volatile int firstbyte;
292 // Fills in params->start and params->firstbyte using
293 // the other search parameters. Returns true on success,
295 // cache_mutex_.r <= L < mutex_
296 bool AnalyzeSearch(SearchParams* params);
297 bool AnalyzeSearchHelper(SearchParams* params, StartInfo* info, uint flags);
299 // The generic search loop, inlined to create specialized versions.
300 // cache_mutex_.r <= L < mutex_
301 // Might unlock and relock cache_mutex_ via params->cache_lock.
302 inline bool InlinedSearchLoop(SearchParams* params,
304 bool want_earliest_match,
307 // The specialized versions of InlinedSearchLoop. The three letters
308 // at the ends of the name denote the true/false values used as the
309 // last three parameters of InlinedSearchLoop.
310 // cache_mutex_.r <= L < mutex_
311 // Might unlock and relock cache_mutex_ via params->cache_lock.
312 bool SearchFFF(SearchParams* params);
313 bool SearchFFT(SearchParams* params);
314 bool SearchFTF(SearchParams* params);
315 bool SearchFTT(SearchParams* params);
316 bool SearchTFF(SearchParams* params);
317 bool SearchTFT(SearchParams* params);
318 bool SearchTTF(SearchParams* params);
319 bool SearchTTT(SearchParams* params);
321 // The main search loop: calls an appropriate specialized version of
322 // InlinedSearchLoop.
323 // cache_mutex_.r <= L < mutex_
324 // Might unlock and relock cache_mutex_ via params->cache_lock.
325 bool FastSearchLoop(SearchParams* params);
327 // For debugging, a slow search loop that calls InlinedSearchLoop
328 // directly -- because the booleans passed are not constants, the
329 // loop is not specialized like the SearchFFF etc. versions, so it
330 // runs much more slowly. Useful only for debugging.
331 // cache_mutex_.r <= L < mutex_
332 // Might unlock and relock cache_mutex_ via params->cache_lock.
333 bool SlowSearchLoop(SearchParams* params);
335 // Looks up bytes in bytemap_ but handles case c == kByteEndText too.
337 if (c == kByteEndText)
338 return prog_->bytemap_range();
339 return prog_->bytemap()[c];
342 // Constant after initialization.
343 Prog* prog_; // The regular expression program to run.
344 Prog::MatchKind kind_; // The kind of DFA.
345 int start_unanchored_; // start of unanchored program
346 bool init_failed_; // initialization failed (out of memory)
348 Mutex mutex_; // mutex_ >= cache_mutex_.r
350 // Scratch areas, protected by mutex_.
351 Workq* q0_; // Two pre-allocated work queues.
353 int* astack_; // Pre-allocated stack for AddToQueue
356 // State* cache. Many threads use and add to the cache simultaneously,
357 // holding cache_mutex_ for reading and mutex_ (above) when adding.
358 // If the cache fills and needs to be discarded, the discarding is done
359 // while holding cache_mutex_ for writing, to avoid interrupting other
360 // readers. Any State* pointers are only valid while cache_mutex_
363 int64 mem_budget_; // Total memory budget for all States.
364 int64 state_budget_; // Amount of memory remaining for new States.
365 StateSet state_cache_; // All States computed so far.
366 StartInfo start_[kMaxStart];
367 bool cache_warned_; // have printed to LOG(INFO) about the cache
370 // Shorthand for casting to uint8*.
371 static inline const uint8* BytePtr(const void* v) {
372 return reinterpret_cast<const uint8*>(v);
377 // Marks separate thread groups of different priority
378 // in the work queue when in leftmost-longest matching mode.
381 // Internally, the DFA uses a sparse array of
382 // program instruction pointers as a work queue.
383 // In leftmost longest mode, marks separate sections
384 // of workq that started executing at different
385 // locations in the string (earlier locations first).
386 class DFA::Workq : public SparseSet {
388 // Constructor: n is number of normal slots, maxmark number of mark slots.
389 Workq(int n, int maxmark) :
390 SparseSet(n+maxmark),
394 last_was_mark_(true) {
397 bool is_mark(int i) { return i >= n_; }
399 int maxmark() { return maxmark_; }
409 last_was_mark_ = false;
410 SparseSet::insert_new(nextmark_++);
414 return n_ + maxmark_;
417 void insert(int id) {
423 void insert_new(int id) {
424 last_was_mark_ = false;
425 SparseSet::insert_new(id);
429 int n_; // size excluding marks
430 int maxmark_; // maximum number of marks
431 int nextmark_; // id of next mark
432 bool last_was_mark_; // last inserted was mark
433 DISALLOW_EVIL_CONSTRUCTORS(Workq);
436 DFA::DFA(Prog* prog, Prog::MatchKind kind, int64 max_mem)
443 mem_budget_(max_mem),
444 cache_warned_(false) {
446 fprintf(stderr, "\nkind %d\n%s\n", (int)kind_, prog_->DumpUnanchored().c_str());
448 start_unanchored_ = 0;
449 if (kind_ == Prog::kLongestMatch) {
450 nmark = prog->size();
451 start_unanchored_ = prog->start_unanchored();
453 nastack_ = 2 * prog->size() + nmark;
455 // Account for space needed for DFA, q0, q1, astack.
456 mem_budget_ -= sizeof(DFA);
457 mem_budget_ -= (prog_->size() + nmark) *
458 (sizeof(int)+sizeof(int)) * 2; // q0, q1
459 mem_budget_ -= nastack_ * sizeof(int); // astack
460 if (mem_budget_ < 0) {
461 LOG(INFO) << StringPrintf("DFA out of memory: prog size %lld mem %lld",
462 prog_->size(), max_mem);
467 state_budget_ = mem_budget_;
469 // Make sure there is a reasonable amount of working room left.
470 // At minimum, the search requires room for two states in order
471 // to limp along, restarting frequently. We'll get better performance
472 // if there is room for a larger number of states, say 20.
473 int64 one_state = sizeof(State) + (prog_->size()+nmark)*sizeof(int) +
474 (prog_->bytemap_range()+1)*sizeof(State*);
475 if (state_budget_ < 20*one_state) {
476 LOG(INFO) << StringPrintf("DFA out of memory: prog size %lld mem %lld",
477 prog_->size(), max_mem);
482 q0_ = new Workq(prog->size(), nmark);
483 q1_ = new Workq(prog->size(), nmark);
484 astack_ = new int[nastack_];
494 // In the DFA state graph, s->next[c] == NULL means that the
495 // state has not yet been computed and needs to be. We need
496 // a different special value to signal that s->next[c] is a
497 // state that can never lead to a match (and thus the search
498 // can be called off). Hence DeadState.
499 #define DeadState reinterpret_cast<State*>(1)
501 // Signals that the rest of the string matches no matter what it is.
502 #define FullMatchState reinterpret_cast<State*>(2)
504 #define SpecialStateMax FullMatchState
506 // Debugging printouts
508 // For debugging, returns a string representation of the work queue.
509 string DFA::DumpWorkq(Workq* q) {
511 const char* sep = "";
512 for (DFA::Workq::iterator it = q->begin(); it != q->end(); ++it) {
513 if (q->is_mark(*it)) {
514 StringAppendF(&s, "|");
517 StringAppendF(&s, "%s%d", sep, *it);
524 // For debugging, returns a string representation of the state.
525 string DFA::DumpState(State* state) {
528 if (state == DeadState)
530 if (state == FullMatchState)
533 const char* sep = "";
534 StringAppendF(&s, "(%p)", state);
535 for (int i = 0; i < state->ninst_; i++) {
536 if (state->inst_[i] == Mark) {
537 StringAppendF(&s, "|");
540 StringAppendF(&s, "%s%d", sep, state->inst_[i]);
544 StringAppendF(&s, " flag=%#x", state->flag_);
548 //////////////////////////////////////////////////////////////////////
550 // DFA state graph construction.
552 // The DFA state graph is a heavily-linked collection of State* structures.
553 // The state_cache_ is a set of all the State structures ever allocated,
554 // so that if the same state is reached by two different paths,
555 // the same State structure can be used. This reduces allocation
556 // requirements and also avoids duplication of effort across the two
559 // A State is defined by an ordered list of instruction ids and a flag word.
561 // The choice of an ordered list of instructions differs from a typical
562 // textbook DFA implementation, which would use an unordered set.
563 // Textbook descriptions, however, only care about whether
564 // the DFA matches, not where it matches in the text. To decide where the
565 // DFA matches, we need to mimic the behavior of the dominant backtracking
566 // implementations like PCRE, which try one possible regular expression
567 // execution, then another, then another, stopping when one of them succeeds.
568 // The DFA execution tries these many executions in parallel, representing
569 // each by an instruction id. These pointers are ordered in the State.inst_
570 // list in the same order that the executions would happen in a backtracking
571 // search: if a match is found during execution of inst_[2], inst_[i] for i>=3
574 // Textbooks also typically do not consider context-aware empty string operators
575 // like ^ or $. These are handled by the flag word, which specifies the set
576 // of empty-string operators that should be matched when executing at the
577 // current text position. These flag bits are defined in prog.h.
578 // The flag word also contains two DFA-specific bits: kFlagMatch if the state
579 // is a matching state (one that reached a kInstMatch in the program)
580 // and kFlagLastWord if the last processed byte was a word character, for the
581 // implementation of \B and \b.
583 // The flag word also contains, shifted up 16 bits, the bits looked for by
584 // any kInstEmptyWidth instructions in the state. These provide a useful
585 // summary indicating when new flags might be useful.
587 // The permanent representation of a State's instruction ids is just an array,
588 // but while a state is being analyzed, these instruction ids are represented
589 // as a Workq, which is an array that allows iteration in insertion order.
591 // NOTE(rsc): The choice of State construction determines whether the DFA
592 // mimics backtracking implementations (so-called leftmost first matching) or
593 // traditional DFA implementations (so-called leftmost longest matching as
594 // prescribed by POSIX). This implementation chooses to mimic the
595 // backtracking implementations, because we want to replace PCRE. To get
596 // POSIX behavior, the states would need to be considered not as a simple
597 // ordered list of instruction ids, but as a list of unordered sets of instruction
598 // ids. A match by a state in one set would inhibit the running of sets
599 // farther down the list but not other instruction ids in the same set. Each
600 // set would correspond to matches beginning at a given point in the string.
601 // This is implemented by separating different sets with Mark pointers.
603 // Looks in the State cache for a State matching q, flag.
604 // If one is found, returns it. If one is not found, allocates one,
605 // inserts it in the cache, and returns it.
606 DFA::State* DFA::WorkqToCachedState(Workq* q, uint flag) {
610 // Construct array of instruction ids for the new state.
611 // Only ByteRange, EmptyWidth, and Match instructions are useful to keep:
612 // those are the only operators with any effect in
613 // RunWorkqOnEmptyString or RunWorkqOnByte.
614 int* inst = new int[q->size()];
616 uint needflags = 0; // flags needed by kInstEmptyWidth instructions
617 bool sawmatch = false; // whether queue contains guaranteed kInstMatch
618 bool sawmark = false; // whether queue contains a Mark
620 fprintf(stderr, "WorkqToCachedState %s [%#x]", DumpWorkq(q).c_str(), flag);
621 for (Workq::iterator it = q->begin(); it != q->end(); ++it) {
623 if (sawmatch && (kind_ == Prog::kFirstMatch || q->is_mark(id)))
625 if (q->is_mark(id)) {
626 if (n > 0 && inst[n-1] != Mark) {
632 Prog::Inst* ip = prog_->inst(id);
633 switch (ip->opcode()) {
635 // This state will continue to a match no matter what
636 // the rest of the input is. If it is the highest priority match
637 // being considered, return the special FullMatchState
638 // to indicate that it's all matches from here out.
639 if (kind_ != Prog::kManyMatch &&
640 (kind_ != Prog::kFirstMatch ||
641 (it == q->begin() && ip->greedy(prog_))) &&
642 (kind_ != Prog::kLongestMatch || !sawmark) &&
643 (flag & kFlagMatch)) {
646 fprintf(stderr, " -> FullMatchState\n");
647 return FullMatchState;
650 case kInstByteRange: // These are useful.
651 case kInstEmptyWidth:
653 case kInstAlt: // Not useful, but necessary [*]
655 if (ip->opcode() == kInstEmptyWidth)
656 needflags |= ip->empty();
657 if (ip->opcode() == kInstMatch && !prog_->anchor_end())
661 default: // The rest are not.
665 // [*] kInstAlt would seem useless to record in a state, since
666 // we've already followed both its arrows and saved all the
667 // interesting states we can reach from there. The problem
668 // is that one of the empty-width instructions might lead
669 // back to the same kInstAlt (if an empty-width operator is starred),
670 // producing a different evaluation order depending on whether
671 // we keep the kInstAlt to begin with. Sigh.
672 // A specific case that this affects is /(^|a)+/ matching "a".
673 // If we don't save the kInstAlt, we will match the whole "a" (0,1)
674 // but in fact the correct leftmost-first match is the leading "" (0,0).
676 DCHECK_LE(n, q->size());
677 if (n > 0 && inst[n-1] == Mark)
680 // If there are no empty-width instructions waiting to execute,
681 // then the extra flag bits will not be used, so there is no
682 // point in saving them. (Discarding them reduces the number
683 // of distinct states.)
687 // NOTE(rsc): The code above cannot do flag &= needflags,
688 // because if the right flags were present to pass the current
689 // kInstEmptyWidth instructions, new kInstEmptyWidth instructions
690 // might be reached that in turn need different flags.
691 // The only sure thing is that if there are no kInstEmptyWidth
692 // instructions at all, no flags will be needed.
693 // We could do the extra work to figure out the full set of
694 // possibly needed flags by exploring past the kInstEmptyWidth
695 // instructions, but the check above -- are any flags needed
696 // at all? -- handles the most common case. More fine-grained
697 // analysis can only be justified by measurements showing that
698 // too many redundant states are being allocated.
700 // If there are no Insts in the list, it's a dead state,
701 // which is useful to signal with a special pointer so that
702 // the execution loop can stop early. This is only okay
703 // if the state is *not* a matching state.
704 if (n == 0 && flag == 0) {
707 fprintf(stderr, " -> DeadState\n");
711 // If we're in longest match mode, the state is a sequence of
712 // unordered state sets separated by Marks. Sort each set
713 // to canonicalize, to reduce the number of distinct sets stored.
714 if (kind_ == Prog::kLongestMatch) {
719 while (markp < ep && *markp != Mark)
728 // Save the needed empty-width flags in the top bits for use later.
729 flag |= needflags << kFlagNeedShift;
731 State* state = CachedState(inst, n, flag);
736 // Looks in the State cache for a State matching inst, ninst, flag.
737 // If one is found, returns it. If one is not found, allocates one,
738 // inserts it in the cache, and returns it.
739 DFA::State* DFA::CachedState(int* inst, int ninst, uint flag) {
743 // Look in the cache for a pre-existing state.
744 State state = { inst, ninst, flag, NULL };
745 StateSet::iterator it = state_cache_.find(&state);
746 if (it != state_cache_.end()) {
748 fprintf(stderr, " -cached-> %s\n", DumpState(*it).c_str());
752 // Must have enough memory for new state.
753 // In addition to what we're going to allocate,
754 // the state cache hash table seems to incur about 32 bytes per
755 // State*, empirically.
756 const int kStateCacheOverhead = 32;
757 int nnext = prog_->bytemap_range() + 1; // + 1 for kByteEndText slot
758 int mem = sizeof(State) + nnext*sizeof(State*) + ninst*sizeof(int);
759 if (mem_budget_ < mem + kStateCacheOverhead) {
763 mem_budget_ -= mem + kStateCacheOverhead;
765 // Allocate new state, along with room for next and inst.
766 char* space = new char[mem];
767 State* s = reinterpret_cast<State*>(space);
768 s->next_ = reinterpret_cast<State**>(s + 1);
769 s->inst_ = reinterpret_cast<int*>(s->next_ + nnext);
770 memset(s->next_, 0, nnext*sizeof s->next_[0]);
771 memmove(s->inst_, inst, ninst*sizeof s->inst_[0]);
775 fprintf(stderr, " -> %s\n", DumpState(s).c_str());
777 // Put state in cache and return it.
778 state_cache_.insert(s);
782 // Clear the cache. Must hold cache_mutex_.w or be in destructor.
783 void DFA::ClearCache() {
784 // In case state_cache_ doesn't support deleting entries
785 // during iteration, copy into a vector and then delete.
787 v.reserve(state_cache_.size());
788 for (StateSet::iterator it = state_cache_.begin();
789 it != state_cache_.end(); ++it)
791 state_cache_.clear();
792 for (int i = 0; i < v.size(); i++)
793 delete[] reinterpret_cast<const char*>(v[i]);
796 // Copies insts in state s to the work queue q.
797 void DFA::StateToWorkq(State* s, Workq* q) {
799 for (int i = 0; i < s->ninst_; i++) {
800 if (s->inst_[i] == Mark)
803 q->insert_new(s->inst_[i]);
807 // Adds ip to the work queue, following empty arrows according to flag
808 // and expanding kInstAlt instructions (two-target gotos).
809 void DFA::AddToQueue(Workq* q, int id, uint flag) {
811 // Use astack_ to hold our stack of states yet to process.
812 // It is sized to have room for nastack_ == 2*prog->size() + nmark
813 // instructions, which is enough: each instruction can be
814 // processed by the switch below only once, and the processing
815 // pushes at most two instructions plus maybe a mark.
816 // (If we're using marks, nmark == prog->size(); otherwise nmark == 0.)
822 DCHECK_LE(nstk, nastack_);
833 // If ip is already on the queue, nothing to do.
834 // Otherwise add it. We don't actually keep all the ones
835 // that get added -- for example, kInstAlt is ignored
836 // when on a work queue -- but adding all ip's here
837 // increases the likelihood of q->contains(id),
838 // reducing the amount of duplicated work.
843 // Process instruction.
844 Prog::Inst* ip = prog_->inst(id);
845 switch (ip->opcode()) {
846 case kInstFail: // can't happen: discarded above
849 case kInstByteRange: // just save these on the queue
853 case kInstCapture: // DFA treats captures as no-ops.
855 stk[nstk++] = ip->out();
858 case kInstAlt: // two choices: expand both, in order
860 // Want to visit out then out1, so push on stack in reverse order.
861 // This instruction is the [00-FF]* loop at the beginning of
862 // a leftmost-longest unanchored search, separate out from out1
863 // with a Mark, so that out1's threads (which will start farther
864 // to the right in the string being searched) are lower priority
865 // than the current ones.
866 stk[nstk++] = ip->out1();
867 if (q->maxmark() > 0 &&
868 id == prog_->start_unanchored() && id != prog_->start())
870 stk[nstk++] = ip->out();
873 case kInstEmptyWidth:
874 if ((ip->empty() & flag) == ip->empty())
875 stk[nstk++] = ip->out();
881 // Running of work queues. In the work queue, order matters:
882 // the queue is sorted in priority order. If instruction i comes before j,
883 // then the instructions that i produces during the run must come before
884 // the ones that j produces. In order to keep this invariant, all the
885 // work queue runners have to take an old queue to process and then
886 // also a new queue to fill in. It's not acceptable to add to the end of
887 // an existing queue, because new instructions will not end up in the
890 // Runs the work queue, processing the empty strings indicated by flag.
891 // For example, flag == kEmptyBeginLine|kEmptyEndLine means to match
892 // both ^ and $. It is important that callers pass all flags at once:
893 // processing both ^ and $ is not the same as first processing only ^
894 // and then processing only $. Doing the two-step sequence won't match
895 // ^$^$^$ but processing ^ and $ simultaneously will (and is the behavior
896 // exhibited by existing implementations).
897 void DFA::RunWorkqOnEmptyString(Workq* oldq, Workq* newq, uint flag) {
899 for (Workq::iterator i = oldq->begin(); i != oldq->end(); ++i) {
900 if (oldq->is_mark(*i))
901 AddToQueue(newq, Mark, flag);
903 AddToQueue(newq, *i, flag);
907 // Runs the work queue, processing the single byte c followed by any empty
908 // strings indicated by flag. For example, c == 'a' and flag == kEmptyEndLine,
909 // means to match c$. Sets the bool *ismatch to true if the end of the
910 // regular expression program has been reached (the regexp has matched).
911 void DFA::RunWorkqOnByte(Workq* oldq, Workq* newq,
912 int c, uint flag, bool* ismatch,
913 Prog::MatchKind kind,
919 for (Workq::iterator i = oldq->begin(); i != oldq->end(); ++i) {
920 if (oldq->is_mark(*i)) {
927 Prog::Inst* ip = prog_->inst(id);
928 switch (ip->opcode()) {
929 case kInstFail: // never succeeds
930 case kInstCapture: // already followed
931 case kInstNop: // already followed
932 case kInstAlt: // already followed
933 case kInstAltMatch: // already followed
934 case kInstEmptyWidth: // already followed
937 case kInstByteRange: // can follow if c is in range
939 AddToQueue(newq, ip->out(), flag);
943 if (prog_->anchor_end() && c != kByteEndText)
946 if (kind == Prog::kFirstMatch) {
947 // Can stop processing work queue since we found a match.
955 fprintf(stderr, "%s on %d[%#x] -> %s [%d]\n", DumpWorkq(oldq).c_str(),
956 c, flag, DumpWorkq(newq).c_str(), *ismatch);
959 // Processes input byte c in state, returning new state.
960 // Caller does not hold mutex.
961 DFA::State* DFA::RunStateOnByteUnlocked(State* state, int c) {
962 // Keep only one RunStateOnByte going
963 // even if the DFA is being run by multiple threads.
964 MutexLock l(&mutex_);
965 return RunStateOnByte(state, c);
968 // Processes input byte c in state, returning new state.
969 DFA::State* DFA::RunStateOnByte(State* state, int c) {
972 if (state <= SpecialStateMax) {
973 if (state == FullMatchState) {
974 // It is convenient for routines like PossibleMatchRange
975 // if we implement RunStateOnByte for FullMatchState:
976 // once you get into this state you never get out,
977 // so it's pretty easy.
978 return FullMatchState;
980 if (state == DeadState) {
981 LOG(DFATAL) << "DeadState in RunStateOnByte";
985 LOG(DFATAL) << "NULL state in RunStateOnByte";
988 LOG(DFATAL) << "Unexpected special state in RunStateOnByte";
992 // If someone else already computed this, return it.
993 MaybeReadMemoryBarrier(); // On alpha we need to ensure read ordering
994 State* ns = state->next_[ByteMap(c)];
995 ANNOTATE_HAPPENS_AFTER(ns);
999 // Convert state into Workq.
1000 StateToWorkq(state, q0_);
1002 // Flags marking the kinds of empty-width things (^ $ etc)
1003 // around this byte. Before the byte we have the flags recorded
1004 // in the State structure itself. After the byte we have
1005 // nothing yet (but that will change: read on).
1006 uint needflag = state->flag_ >> kFlagNeedShift;
1007 uint beforeflag = state->flag_ & kFlagEmptyMask;
1008 uint oldbeforeflag = beforeflag;
1012 // Insert implicit $ and ^ around \n
1013 beforeflag |= kEmptyEndLine;
1014 afterflag |= kEmptyBeginLine;
1017 if (c == kByteEndText) {
1018 // Insert implicit $ and \z before the fake "end text" byte.
1019 beforeflag |= kEmptyEndLine | kEmptyEndText;
1022 // The state flag kFlagLastWord says whether the last
1023 // byte processed was a word character. Use that info to
1024 // insert empty-width (non-)word boundaries.
1025 bool islastword = state->flag_ & kFlagLastWord;
1026 bool isword = (c != kByteEndText && Prog::IsWordChar(c));
1027 if (isword == islastword)
1028 beforeflag |= kEmptyNonWordBoundary;
1030 beforeflag |= kEmptyWordBoundary;
1032 // Okay, finally ready to run.
1033 // Only useful to rerun on empty string if there are new, useful flags.
1034 if (beforeflag & ~oldbeforeflag & needflag) {
1035 RunWorkqOnEmptyString(q0_, q1_, beforeflag);
1038 bool ismatch = false;
1039 RunWorkqOnByte(q0_, q1_, c, afterflag, &ismatch, kind_, start_unanchored_);
1041 // Most of the time, we build the state from the output of
1042 // RunWorkqOnByte, so swap q0_ and q1_ here. However, so that
1043 // RE2::Set can tell exactly which match instructions
1044 // contributed to the match, don't swap if c is kByteEndText.
1045 // The resulting state wouldn't be correct for further processing
1046 // of the string, but we're at the end of the text so that's okay.
1047 // Leaving q0_ alone preseves the match instructions that led to
1048 // the current setting of ismatch.
1049 if (c != kByteEndText || kind_ != Prog::kManyMatch)
1052 // Save afterflag along with ismatch and isword in new state.
1053 uint flag = afterflag;
1057 flag |= kFlagLastWord;
1059 ns = WorkqToCachedState(q0_, flag);
1061 // Write barrier before updating state->next_ so that the
1062 // main search loop can proceed without any locking, for speed.
1063 // (Otherwise it would need one mutex operation per input byte.)
1064 // The annotations below tell race detectors that:
1065 // a) the access to next_ should be ignored,
1066 // b) 'ns' is properly published.
1067 WriteMemoryBarrier(); // Flush ns before linking to it.
1069 ANNOTATE_IGNORE_WRITES_BEGIN();
1070 ANNOTATE_HAPPENS_BEFORE(ns);
1071 state->next_[ByteMap(c)] = ns;
1072 ANNOTATE_IGNORE_WRITES_END();
1077 //////////////////////////////////////////////////////////////////////
1080 // Reader-writer lock helper.
1082 // The DFA uses a reader-writer mutex to protect the state graph itself.
1083 // Traversing the state graph requires holding the mutex for reading,
1084 // and discarding the state graph and starting over requires holding the
1085 // lock for writing. If a search needs to expand the graph but is out
1086 // of memory, it will need to drop its read lock and then acquire the
1087 // write lock. Since it cannot then atomically downgrade from write lock
1088 // to read lock, it runs the rest of the search holding the write lock.
1089 // (This probably helps avoid repeated contention, but really the decision
1090 // is forced by the Mutex interface.) It's a bit complicated to keep
1091 // track of whether the lock is held for reading or writing and thread
1092 // that through the search, so instead we encapsulate it in the RWLocker
1093 // and pass that around.
1095 class DFA::RWLocker {
1097 explicit RWLocker(Mutex* mu);
1100 // If the lock is only held for reading right now,
1101 // drop the read lock and re-acquire for writing.
1102 // Subsequent calls to LockForWriting are no-ops.
1103 // Notice that the lock is *released* temporarily.
1104 void LockForWriting();
1106 // Returns whether the lock is already held for writing.
1107 bool IsLockedForWriting() {
1115 DISALLOW_EVIL_CONSTRUCTORS(RWLocker);
1118 DFA::RWLocker::RWLocker(Mutex* mu)
1119 : mu_(mu), writing_(false) {
1124 // This function is marked as NO_THREAD_SAFETY_ANALYSIS because the annotations
1125 // does not support lock upgrade.
1126 void DFA::RWLocker::LockForWriting() NO_THREAD_SAFETY_ANALYSIS {
1128 mu_->ReaderUnlock();
1134 DFA::RWLocker::~RWLocker() {
1136 mu_->WriterUnlock();
1138 mu_->ReaderUnlock();
1142 // When the DFA's State cache fills, we discard all the states in the
1143 // cache and start over. Many threads can be using and adding to the
1144 // cache at the same time, so we synchronize using the cache_mutex_
1145 // to keep from stepping on other threads. Specifically, all the
1146 // threads using the current cache hold cache_mutex_ for reading.
1147 // When a thread decides to flush the cache, it drops cache_mutex_
1148 // and then re-acquires it for writing. That ensures there are no
1149 // other threads accessing the cache anymore. The rest of the search
1150 // runs holding cache_mutex_ for writing, avoiding any contention
1151 // with or cache pollution caused by other threads.
1153 void DFA::ResetCache(RWLocker* cache_lock) {
1154 // Re-acquire the cache_mutex_ for writing (exclusive use).
1155 bool was_writing = cache_lock->IsLockedForWriting();
1156 cache_lock->LockForWriting();
1158 // If we already held cache_mutex_ for writing, it means
1159 // this invocation of Search() has already reset the
1160 // cache once already. That's a pretty clear indication
1161 // that the cache is too small. Warn about that, once.
1162 // TODO(rsc): Only warn if state_cache_.size() < some threshold.
1163 if (was_writing && !cache_warned_) {
1164 LOG(INFO) << "DFA memory cache could be too small: "
1165 << "only room for " << state_cache_.size() << " states.";
1166 cache_warned_ = true;
1169 // Clear the cache, reset the memory budget.
1170 for (int i = 0; i < kMaxStart; i++) {
1171 start_[i].start = NULL;
1172 start_[i].firstbyte = kFbUnknown;
1175 mem_budget_ = state_budget_;
1178 // Typically, a couple States do need to be preserved across a cache
1179 // reset, like the State at the current point in the search.
1180 // The StateSaver class helps keep States across cache resets.
1181 // It makes a copy of the state's guts outside the cache (before the reset)
1182 // and then can be asked, after the reset, to recreate the State
1183 // in the new cache. For example, in a DFA method ("this" is a DFA):
1185 // StateSaver saver(this, s);
1186 // ResetCache(cache_lock);
1187 // s = saver.Restore();
1189 // The saver should always have room in the cache to re-create the state,
1190 // because resetting the cache locks out all other threads, and the cache
1191 // is known to have room for at least a couple states (otherwise the DFA
1192 // constructor fails).
1194 class DFA::StateSaver {
1196 explicit StateSaver(DFA* dfa, State* state);
1199 // Recreates and returns a state equivalent to the
1200 // original state passed to the constructor.
1201 // Returns NULL if the cache has filled, but
1202 // since the DFA guarantees to have room in the cache
1203 // for a couple states, should never return NULL
1204 // if used right after ResetCache.
1208 DFA* dfa_; // the DFA to use
1209 int* inst_; // saved info from State
1212 bool is_special_; // whether original state was special
1213 State* special_; // if is_special_, the original state
1215 DISALLOW_EVIL_CONSTRUCTORS(StateSaver);
1218 DFA::StateSaver::StateSaver(DFA* dfa, State* state) {
1220 if (state <= SpecialStateMax) {
1228 is_special_ = false;
1230 flag_ = state->flag_;
1231 ninst_ = state->ninst_;
1232 inst_ = new int[ninst_];
1233 memmove(inst_, state->inst_, ninst_*sizeof inst_[0]);
1236 DFA::StateSaver::~StateSaver() {
1241 DFA::State* DFA::StateSaver::Restore() {
1244 MutexLock l(&dfa_->mutex_);
1245 State* s = dfa_->CachedState(inst_, ninst_, flag_);
1247 LOG(DFATAL) << "StateSaver failed to restore state.";
1252 //////////////////////////////////////////////////////////////////////
1256 // The basic search loop is easy: start in a state s and then for each
1257 // byte c in the input, s = s->next[c].
1259 // This simple description omits a few efficiency-driven complications.
1261 // First, the State graph is constructed incrementally: it is possible
1262 // that s->next[c] is null, indicating that that state has not been
1263 // fully explored. In this case, RunStateOnByte must be invoked to
1264 // determine the next state, which is cached in s->next[c] to save
1265 // future effort. An alternative reason for s->next[c] to be null is
1266 // that the DFA has reached a so-called "dead state", in which any match
1267 // is no longer possible. In this case RunStateOnByte will return NULL
1268 // and the processing of the string can stop early.
1270 // Second, a 256-element pointer array for s->next_ makes each State
1271 // quite large (2kB on 64-bit machines). Instead, dfa->bytemap_[]
1272 // maps from bytes to "byte classes" and then next_ only needs to have
1273 // as many pointers as there are byte classes. A byte class is simply a
1274 // range of bytes that the regexp never distinguishes between.
1275 // A regexp looking for a[abc] would have four byte ranges -- 0 to 'a'-1,
1276 // 'a', 'b' to 'c', and 'c' to 0xFF. The bytemap slows us a little bit
1277 // but in exchange we typically cut the size of a State (and thus our
1278 // memory footprint) by about 5-10x. The comments still refer to
1279 // s->next[c] for simplicity, but code should refer to s->next_[bytemap_[c]].
1281 // Third, it is common for a DFA for an unanchored match to begin in a
1282 // state in which only one particular byte value can take the DFA to a
1283 // different state. That is, s->next[c] != s for only one c. In this
1284 // situation, the DFA can do better than executing the simple loop.
1285 // Instead, it can call memchr to search very quickly for the byte c.
1286 // Whether the start state has this property is determined during a
1287 // pre-compilation pass, and if so, the byte b is passed to the search
1288 // loop as the "firstbyte" argument, along with a boolean "have_firstbyte".
1290 // Fourth, the desired behavior is to search for the leftmost-best match
1291 // (approximately, the same one that Perl would find), which is not
1292 // necessarily the match ending earliest in the string. Each time a
1293 // match is found, it must be noted, but the DFA must continue on in
1294 // hope of finding a higher-priority match. In some cases, the caller only
1295 // cares whether there is any match at all, not which one is found.
1296 // The "want_earliest_match" flag causes the search to stop at the first
1299 // Fifth, one algorithm that uses the DFA needs it to run over the
1300 // input string backward, beginning at the end and ending at the beginning.
1301 // Passing false for the "run_forward" flag causes the DFA to run backward.
1303 // The checks for these last three cases, which in a naive implementation
1304 // would be performed once per input byte, slow the general loop enough
1305 // to merit specialized versions of the search loop for each of the
1306 // eight possible settings of the three booleans. Rather than write
1307 // eight different functions, we write one general implementation and then
1308 // inline it to create the specialized ones.
1310 // Note that matches are delayed by one byte, to make it easier to
1311 // accomodate match conditions depending on the next input byte (like $ and \b).
1312 // When s->next[c]->IsMatch(), it means that there is a match ending just
1315 // The generic search loop. Searches text for a match, returning
1316 // the pointer to the end of the chosen match, or NULL if no match.
1317 // The bools are equal to the same-named variables in params, but
1318 // making them function arguments lets the inliner specialize
1319 // this function to each combination (see two paragraphs above).
1320 inline bool DFA::InlinedSearchLoop(SearchParams* params,
1321 bool have_firstbyte,
1322 bool want_earliest_match,
1324 State* start = params->start;
1325 const uint8* bp = BytePtr(params->text.begin()); // start of text
1326 const uint8* p = bp; // text scanning point
1327 const uint8* ep = BytePtr(params->text.end()); // end of text
1328 const uint8* resetp = NULL; // p at last cache reset
1332 const uint8* bytemap = prog_->bytemap();
1333 const uint8* lastmatch = NULL; // most recent matching position in text
1334 bool matched = false;
1340 if (want_earliest_match) {
1341 params->ep = reinterpret_cast<const char*>(lastmatch);
1348 fprintf(stderr, "@%d: %s\n", static_cast<int>(p - bp),
1349 DumpState(s).c_str());
1350 if (have_firstbyte && s == start) {
1351 // In start state, only way out is to find firstbyte,
1352 // so use optimized assembly in memchr to skip ahead.
1353 // If firstbyte isn't found, we can skip to the end
1356 if ((p = BytePtr(memchr(p, params->firstbyte, ep - p))) == NULL) {
1361 if ((p = BytePtr(memrchr(ep, params->firstbyte, p - ep))) == NULL) {
1375 // Note that multiple threads might be consulting
1376 // s->next_[bytemap[c]] simultaneously.
1377 // RunStateOnByte takes care of the appropriate locking,
1378 // including a memory barrier so that the unlocked access
1379 // (sometimes known as "double-checked locking") is safe.
1380 // The alternative would be either one DFA per thread
1381 // or one mutex operation per input byte.
1383 // ns == DeadState means the state is known to be dead
1384 // (no more matches are possible).
1385 // ns == NULL means the state has not yet been computed
1386 // (need to call RunStateOnByteUnlocked).
1387 // RunStateOnByte returns ns == NULL if it is out of memory.
1388 // ns == FullMatchState means the rest of the string matches.
1390 // Okay to use bytemap[] not ByteMap() here, because
1391 // c is known to be an actual byte and not kByteEndText.
1393 MaybeReadMemoryBarrier(); // On alpha we need to ensure read ordering
1394 State* ns = s->next_[bytemap[c]];
1395 ANNOTATE_HAPPENS_AFTER(ns);
1397 ns = RunStateOnByteUnlocked(s, c);
1399 // After we reset the cache, we hold cache_mutex exclusively,
1400 // so if resetp != NULL, it means we filled the DFA state
1401 // cache with this search alone (without any other threads).
1402 // Benchmarks show that doing a state computation on every
1403 // byte runs at about 0.2 MB/s, while the NFA (nfa.cc) can do the
1404 // same at about 2 MB/s. Unless we're processing an average
1405 // of 10 bytes per state computation, fail so that RE2 can
1406 // fall back to the NFA.
1407 if (FLAGS_re2_dfa_bail_when_slow && resetp != NULL &&
1408 (p - resetp) < 10*state_cache_.size()) {
1409 params->failed = true;
1414 // Prepare to save start and s across the reset.
1415 StateSaver save_start(this, start);
1416 StateSaver save_s(this, s);
1418 // Discard all the States in the cache.
1419 ResetCache(params->cache_lock);
1421 // Restore start and s so we can continue.
1422 if ((start = save_start.Restore()) == NULL ||
1423 (s = save_s.Restore()) == NULL) {
1424 // Restore already did LOG(DFATAL).
1425 params->failed = true;
1428 ns = RunStateOnByteUnlocked(s, c);
1430 LOG(DFATAL) << "RunStateOnByteUnlocked failed after ResetCache";
1431 params->failed = true;
1436 if (ns <= SpecialStateMax) {
1437 if (ns == DeadState) {
1438 params->ep = reinterpret_cast<const char*>(lastmatch);
1442 params->ep = reinterpret_cast<const char*>(ep);
1449 // The DFA notices the match one byte late,
1450 // so adjust p before using it in the match.
1456 fprintf(stderr, "match @%d! [%s]\n",
1457 static_cast<int>(lastmatch - bp),
1458 DumpState(s).c_str());
1460 if (want_earliest_match) {
1461 params->ep = reinterpret_cast<const char*>(lastmatch);
1467 // Process one more byte to see if it triggers a match.
1468 // (Remember, matches are delayed one byte.)
1471 if (params->text.end() == params->context.end())
1472 lastbyte = kByteEndText;
1474 lastbyte = params->text.end()[0] & 0xFF;
1476 if (params->text.begin() == params->context.begin())
1477 lastbyte = kByteEndText;
1479 lastbyte = params->text.begin()[-1] & 0xFF;
1482 MaybeReadMemoryBarrier(); // On alpha we need to ensure read ordering
1483 State* ns = s->next_[ByteMap(lastbyte)];
1484 ANNOTATE_HAPPENS_AFTER(ns);
1486 ns = RunStateOnByteUnlocked(s, lastbyte);
1488 StateSaver save_s(this, s);
1489 ResetCache(params->cache_lock);
1490 if ((s = save_s.Restore()) == NULL) {
1491 params->failed = true;
1494 ns = RunStateOnByteUnlocked(s, lastbyte);
1496 LOG(DFATAL) << "RunStateOnByteUnlocked failed after Reset";
1497 params->failed = true;
1504 fprintf(stderr, "@_: %s\n", DumpState(s).c_str());
1505 if (s == FullMatchState) {
1506 params->ep = reinterpret_cast<const char*>(ep);
1509 if (s > SpecialStateMax && s->IsMatch()) {
1512 if (params->matches && kind_ == Prog::kManyMatch) {
1513 vector<int>* v = params->matches;
1515 for (int i = 0; i < s->ninst_; i++) {
1516 Prog::Inst* ip = prog_->inst(s->inst_[i]);
1517 if (ip->opcode() == kInstMatch)
1518 v->push_back(ip->match_id());
1522 fprintf(stderr, "match @%d! [%s]\n", static_cast<int>(lastmatch - bp),
1523 DumpState(s).c_str());
1525 params->ep = reinterpret_cast<const char*>(lastmatch);
1529 // Inline specializations of the general loop.
1530 bool DFA::SearchFFF(SearchParams* params) {
1531 return InlinedSearchLoop(params, 0, 0, 0);
1533 bool DFA::SearchFFT(SearchParams* params) {
1534 return InlinedSearchLoop(params, 0, 0, 1);
1536 bool DFA::SearchFTF(SearchParams* params) {
1537 return InlinedSearchLoop(params, 0, 1, 0);
1539 bool DFA::SearchFTT(SearchParams* params) {
1540 return InlinedSearchLoop(params, 0, 1, 1);
1542 bool DFA::SearchTFF(SearchParams* params) {
1543 return InlinedSearchLoop(params, 1, 0, 0);
1545 bool DFA::SearchTFT(SearchParams* params) {
1546 return InlinedSearchLoop(params, 1, 0, 1);
1548 bool DFA::SearchTTF(SearchParams* params) {
1549 return InlinedSearchLoop(params, 1, 1, 0);
1551 bool DFA::SearchTTT(SearchParams* params) {
1552 return InlinedSearchLoop(params, 1, 1, 1);
1555 // For debugging, calls the general code directly.
1556 bool DFA::SlowSearchLoop(SearchParams* params) {
1557 return InlinedSearchLoop(params,
1558 params->firstbyte >= 0,
1559 params->want_earliest_match,
1560 params->run_forward);
1563 // For performance, calls the appropriate specialized version
1564 // of InlinedSearchLoop.
1565 bool DFA::FastSearchLoop(SearchParams* params) {
1566 // Because the methods are private, the Searches array
1567 // cannot be declared at top level.
1568 static bool (DFA::*Searches[])(SearchParams*) = {
1579 bool have_firstbyte = (params->firstbyte >= 0);
1580 int index = 4 * have_firstbyte +
1581 2 * params->want_earliest_match +
1582 1 * params->run_forward;
1583 return (this->*Searches[index])(params);
1587 // The discussion of DFA execution above ignored the question of how
1588 // to determine the initial state for the search loop. There are two
1589 // factors that influence the choice of start state.
1591 // The first factor is whether the search is anchored or not.
1592 // The regexp program (Prog*) itself has
1593 // two different entry points: one for anchored searches and one for
1594 // unanchored searches. (The unanchored version starts with a leading ".*?"
1595 // and then jumps to the anchored one.)
1597 // The second factor is where text appears in the larger context, which
1598 // determines which empty-string operators can be matched at the beginning
1599 // of execution. If text is at the very beginning of context, \A and ^ match.
1600 // Otherwise if text is at the beginning of a line, then ^ matches.
1601 // Otherwise it matters whether the character before text is a word character
1602 // or a non-word character.
1604 // The two cases (unanchored vs not) and four cases (empty-string flags)
1605 // combine to make the eight cases recorded in the DFA's begin_text_[2],
1606 // begin_line_[2], after_wordchar_[2], and after_nonwordchar_[2] cached
1607 // StartInfos. The start state for each is filled in the first time it
1608 // is used for an actual search.
1610 // Examines text, context, and anchored to determine the right start
1611 // state for the DFA search loop. Fills in params and returns true on success.
1612 // Returns false on failure.
1613 bool DFA::AnalyzeSearch(SearchParams* params) {
1614 const StringPiece& text = params->text;
1615 const StringPiece& context = params->context;
1617 // Sanity check: make sure that text lies within context.
1618 if (text.begin() < context.begin() || text.end() > context.end()) {
1619 LOG(DFATAL) << "Text is not inside context.";
1620 params->start = DeadState;
1624 // Determine correct search type.
1627 if (params->run_forward) {
1628 if (text.begin() == context.begin()) {
1629 start = kStartBeginText;
1630 flags = kEmptyBeginText|kEmptyBeginLine;
1631 } else if (text.begin()[-1] == '\n') {
1632 start = kStartBeginLine;
1633 flags = kEmptyBeginLine;
1634 } else if (Prog::IsWordChar(text.begin()[-1] & 0xFF)) {
1635 start = kStartAfterWordChar;
1636 flags = kFlagLastWord;
1638 start = kStartAfterNonWordChar;
1642 if (text.end() == context.end()) {
1643 start = kStartBeginText;
1644 flags = kEmptyBeginText|kEmptyBeginLine;
1645 } else if (text.end()[0] == '\n') {
1646 start = kStartBeginLine;
1647 flags = kEmptyBeginLine;
1648 } else if (Prog::IsWordChar(text.end()[0] & 0xFF)) {
1649 start = kStartAfterWordChar;
1650 flags = kFlagLastWord;
1652 start = kStartAfterNonWordChar;
1656 if (params->anchored || prog_->anchor_start())
1657 start |= kStartAnchored;
1658 StartInfo* info = &start_[start];
1660 // Try once without cache_lock for writing.
1661 // Try again after resetting the cache
1662 // (ResetCache will relock cache_lock for writing).
1663 if (!AnalyzeSearchHelper(params, info, flags)) {
1664 ResetCache(params->cache_lock);
1665 if (!AnalyzeSearchHelper(params, info, flags)) {
1666 LOG(DFATAL) << "Failed to analyze start state.";
1667 params->failed = true;
1673 fprintf(stderr, "anchored=%d fwd=%d flags=%#x state=%s firstbyte=%d\n",
1674 params->anchored, params->run_forward, flags,
1675 DumpState(info->start).c_str(), info->firstbyte);
1677 params->start = info->start;
1678 params->firstbyte = ANNOTATE_UNPROTECTED_READ(info->firstbyte);
1683 // Fills in info if needed. Returns true on success, false on failure.
1684 bool DFA::AnalyzeSearchHelper(SearchParams* params, StartInfo* info,
1686 // Quick check; okay because of memory barriers below.
1687 if (ANNOTATE_UNPROTECTED_READ(info->firstbyte) != kFbUnknown) {
1688 ANNOTATE_HAPPENS_AFTER(&info->firstbyte);
1692 MutexLock l(&mutex_);
1693 if (info->firstbyte != kFbUnknown) {
1694 ANNOTATE_HAPPENS_AFTER(&info->firstbyte);
1700 params->anchored ? prog_->start() : prog_->start_unanchored(),
1702 info->start = WorkqToCachedState(q0_, flags);
1703 if (info->start == NULL)
1706 if (info->start == DeadState) {
1707 ANNOTATE_HAPPENS_BEFORE(&info->firstbyte);
1708 WriteMemoryBarrier(); // Synchronize with "quick check" above.
1709 info->firstbyte = kFbNone;
1713 if (info->start == FullMatchState) {
1714 ANNOTATE_HAPPENS_BEFORE(&info->firstbyte);
1715 WriteMemoryBarrier(); // Synchronize with "quick check" above.
1716 info->firstbyte = kFbNone; // will be ignored
1720 // Compute info->firstbyte by running state on all
1721 // possible byte values, looking for a single one that
1722 // leads to a different state.
1723 int firstbyte = kFbNone;
1724 for (int i = 0; i < 256; i++) {
1725 State* s = RunStateOnByte(info->start, i);
1727 ANNOTATE_HAPPENS_BEFORE(&info->firstbyte);
1728 WriteMemoryBarrier(); // Synchronize with "quick check" above.
1729 info->firstbyte = firstbyte;
1732 if (s == info->start)
1734 // Goes to new state...
1735 if (firstbyte == kFbNone) {
1736 firstbyte = i; // ... first one
1738 firstbyte = kFbMany; // ... too many
1742 ANNOTATE_HAPPENS_BEFORE(&info->firstbyte);
1743 WriteMemoryBarrier(); // Synchronize with "quick check" above.
1744 info->firstbyte = firstbyte;
1748 // The actual DFA search: calls AnalyzeSearch and then FastSearchLoop.
1749 bool DFA::Search(const StringPiece& text,
1750 const StringPiece& context,
1752 bool want_earliest_match,
1756 vector<int>* matches) {
1765 fprintf(stderr, "\nprogram:\n%s\n", prog_->DumpUnanchored().c_str());
1766 fprintf(stderr, "text %s anchored=%d earliest=%d fwd=%d kind %d\n",
1767 text.as_string().c_str(), anchored, want_earliest_match,
1768 run_forward, kind_);
1771 RWLocker l(&cache_mutex_);
1772 SearchParams params(text, context, &l);
1773 params.anchored = anchored;
1774 params.want_earliest_match = want_earliest_match;
1775 params.run_forward = run_forward;
1776 params.matches = matches;
1778 if (!AnalyzeSearch(¶ms)) {
1782 if (params.start == DeadState)
1784 if (params.start == FullMatchState) {
1785 if (run_forward == want_earliest_match)
1786 *epp = text.begin();
1792 fprintf(stderr, "start %s\n", DumpState(params.start).c_str());
1793 bool ret = FastSearchLoop(¶ms);
1794 if (params.failed) {
1804 // This is a separate function so that
1805 // prog.h can be used without moving the definition of
1806 // class DFA out of this file. If you set
1807 // prog->dfa_ = dfa;
1808 // then you also have to set
1809 // prog->delete_dfa_ = DeleteDFA;
1810 // so that ~Prog can delete the dfa.
1811 static void DeleteDFA(DFA* dfa) {
1815 DFA* Prog::GetDFA(MatchKind kind) {
1817 if (kind == kFirstMatch || kind == kManyMatch) {
1820 kind = kLongestMatch;
1821 pdfa = &dfa_longest_;
1824 // Quick check; okay because of memory barrier below.
1825 DFA *dfa = ANNOTATE_UNPROTECTED_READ(*pdfa);
1827 ANNOTATE_HAPPENS_AFTER(dfa);
1831 MutexLock l(&dfa_mutex_);
1834 ANNOTATE_HAPPENS_AFTER(dfa);
1838 // For a forward DFA, half the memory goes to each DFA.
1839 // For a reverse DFA, all the memory goes to the
1840 // "longest match" DFA, because RE2 never does reverse
1841 // "first match" searches.
1842 int64 m = dfa_mem_/2;
1844 if (kind == kLongestMatch || kind == kManyMatch)
1849 dfa = new DFA(this, kind, m);
1850 delete_dfa_ = DeleteDFA;
1852 // Synchronize with "quick check" above.
1853 ANNOTATE_HAPPENS_BEFORE(dfa);
1854 WriteMemoryBarrier();
1861 // Executes the regexp program to search in text,
1862 // which itself is inside the larger context. (As a convenience,
1863 // passing a NULL context is equivalent to passing text.)
1864 // Returns true if a match is found, false if not.
1865 // If a match is found, fills in match0->end() to point at the end of the match
1866 // and sets match0->begin() to text.begin(), since the DFA can't track
1867 // where the match actually began.
1869 // This is the only external interface (class DFA only exists in this file).
1871 bool Prog::SearchDFA(const StringPiece& text, const StringPiece& const_context,
1872 Anchor anchor, MatchKind kind,
1873 StringPiece* match0, bool* failed, vector<int>* matches) {
1876 StringPiece context = const_context;
1877 if (context.begin() == NULL)
1879 bool carat = anchor_start();
1880 bool dollar = anchor_end();
1886 if (carat && context.begin() != text.begin())
1888 if (dollar && context.end() != text.end())
1891 // Handle full match by running an anchored longest match
1892 // and then checking if it covers all of text.
1893 bool anchored = anchor == kAnchored || anchor_start() || kind == kFullMatch;
1894 bool endmatch = false;
1895 if (kind == kManyMatch) {
1897 } else if (kind == kFullMatch || anchor_end()) {
1899 kind = kLongestMatch;
1902 // If the caller doesn't care where the match is (just whether one exists),
1903 // then we can stop at the very first match we find, the so-called
1904 // "shortest match".
1905 bool want_shortest_match = false;
1906 if (match0 == NULL && !endmatch) {
1907 want_shortest_match = true;
1908 kind = kLongestMatch;
1911 DFA* dfa = GetDFA(kind);
1913 bool matched = dfa->Search(text, context, anchored,
1914 want_shortest_match, !reversed_,
1915 failed, &ep, matches);
1920 if (endmatch && ep != (reversed_ ? text.begin() : text.end()))
1923 // If caller cares, record the boundary of the match.
1924 // We only know where it ends, so use the boundary of text
1925 // as the beginning.
1928 *match0 = StringPiece(ep, text.end() - ep);
1930 *match0 = StringPiece(text.begin(), ep - text.begin());
1935 // Build out all states in DFA. Returns number of states.
1936 int DFA::BuildAllStates() {
1940 // Pick out start state for unanchored search
1941 // at beginning of text.
1942 RWLocker l(&cache_mutex_);
1943 SearchParams params(NULL, NULL, &l);
1944 params.anchored = false;
1945 if (!AnalyzeSearch(¶ms) || params.start <= SpecialStateMax)
1948 // Add start state to work queue.
1951 queued.insert(params.start);
1952 q.push_back(params.start);
1954 // Flood to expand every state.
1955 for (int i = 0; i < q.size(); i++) {
1957 for (int c = 0; c < 257; c++) {
1958 State* ns = RunStateOnByteUnlocked(s, c);
1959 if (ns > SpecialStateMax && queued.find(ns) == queued.end()) {
1969 // Build out all states in DFA for kind. Returns number of states.
1970 int Prog::BuildEntireDFA(MatchKind kind) {
1971 //LOG(ERROR) << "BuildEntireDFA is only for testing.";
1972 return GetDFA(kind)->BuildAllStates();
1975 // Computes min and max for matching string.
1976 // Won't return strings bigger than maxlen.
1977 bool DFA::PossibleMatchRange(string* min, string* max, int maxlen) {
1981 // NOTE: if future users of PossibleMatchRange want more precision when
1982 // presented with infinitely repeated elements, consider making this a
1983 // parameter to PossibleMatchRange.
1984 static int kMaxEltRepetitions = 0;
1986 // Keep track of the number of times we've visited states previously. We only
1987 // revisit a given state if it's part of a repeated group, so if the value
1988 // portion of the map tuple exceeds kMaxEltRepetitions we bail out and set
1989 // |*max| to |PrefixSuccessor(*max)|.
1991 // Also note that previously_visited_states[UnseenStatePtr] will, in the STL
1992 // tradition, implicitly insert a '0' value at first use. We take advantage
1993 // of that property below.
1994 map<State*, int> previously_visited_states;
1996 // Pick out start state for anchored search at beginning of text.
1997 RWLocker l(&cache_mutex_);
1998 SearchParams params(NULL, NULL, &l);
1999 params.anchored = true;
2000 if (!AnalyzeSearch(¶ms))
2002 if (params.start == DeadState) { // No matching strings
2007 if (params.start == FullMatchState) // Every string matches: no max
2010 // The DFA is essentially a big graph rooted at params.start,
2011 // and paths in the graph correspond to accepted strings.
2012 // Each node in the graph has potentially 256+1 arrows
2013 // coming out, one for each byte plus the magic end of
2014 // text character kByteEndText.
2016 // To find the smallest possible prefix of an accepted
2017 // string, we just walk the graph preferring to follow
2018 // arrows with the lowest bytes possible. To find the
2019 // largest possible prefix, we follow the largest bytes
2022 // The test for whether there is an arrow from s on byte j is
2023 // ns = RunStateOnByteUnlocked(s, j);
2026 // if (ns != DeadState && ns->ninst > 0)
2027 // The RunStateOnByteUnlocked call asks the DFA to build out the graph.
2028 // It returns NULL only if the DFA has run out of memory,
2029 // in which case we can't be sure of anything.
2030 // The second check sees whether there was graph built
2031 // and whether it is interesting graph. Nodes might have
2032 // ns->ninst == 0 if they exist only to represent the fact
2033 // that a match was found on the previous byte.
2035 // Build minimum prefix.
2036 State* s = params.start;
2038 for (int i = 0; i < maxlen; i++) {
2039 if (previously_visited_states[s] > kMaxEltRepetitions) {
2040 VLOG(2) << "Hit kMaxEltRepetitions=" << kMaxEltRepetitions
2041 << " for state s=" << s << " and min=" << CEscape(*min);
2044 previously_visited_states[s]++;
2046 // Stop if min is a match.
2047 State* ns = RunStateOnByteUnlocked(s, kByteEndText);
2048 if (ns == NULL) // DFA out of memory
2050 if (ns != DeadState && (ns == FullMatchState || ns->IsMatch()))
2053 // Try to extend the string with low bytes.
2054 bool extended = false;
2055 for (int j = 0; j < 256; j++) {
2056 ns = RunStateOnByteUnlocked(s, j);
2057 if (ns == NULL) // DFA out of memory
2059 if (ns == FullMatchState ||
2060 (ns > SpecialStateMax && ns->ninst_ > 0)) {
2071 // Build maximum prefix.
2072 previously_visited_states.clear();
2075 for (int i = 0; i < maxlen; i++) {
2076 if (previously_visited_states[s] > kMaxEltRepetitions) {
2077 VLOG(2) << "Hit kMaxEltRepetitions=" << kMaxEltRepetitions
2078 << " for state s=" << s << " and max=" << CEscape(*max);
2081 previously_visited_states[s] += 1;
2083 // Try to extend the string with high bytes.
2084 bool extended = false;
2085 for (int j = 255; j >= 0; j--) {
2086 State* ns = RunStateOnByteUnlocked(s, j);
2089 if (ns == FullMatchState ||
2090 (ns > SpecialStateMax && ns->ninst_ > 0)) {
2098 // Done, no need for PrefixSuccessor.
2103 // Stopped while still adding to *max - round aaaaaaaaaa... to aaaa...b
2104 *max = PrefixSuccessor(*max);
2106 // If there are no bytes left, we have no way to say "there is no maximum
2107 // string". We could make the interface more complicated and be able to
2108 // return "there is no maximum but here is a minimum", but that seems like
2109 // overkill -- the most common no-max case is all possible strings, so not
2110 // telling the caller that the empty string is the minimum match isn't a
2118 // PossibleMatchRange for a Prog.
2119 bool Prog::PossibleMatchRange(string* min, string* max, int maxlen) {
2122 MutexLock l(&dfa_mutex_);
2123 // Have to use dfa_longest_ to get all strings for full matches.
2124 // For example, (a|aa) never matches aa in first-match mode.
2125 if (dfa_longest_ == NULL) {
2126 dfa_longest_ = new DFA(this, Prog::kLongestMatch, dfa_mem_/2);
2127 delete_dfa_ = DeleteDFA;
2131 return dfa->PossibleMatchRange(min, max, maxlen);