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.
4
5 // A DFA (deterministic finite automaton)-based regular expression search.
6 //
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.
10 //
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.
15 //
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.
21 //
22 // See http://swtch.com/~rsc/regexp/ for a very bare-bones equivalent.
23
24 #include <stddef.h>
25 #include <stdint.h>
26 #include <stdio.h>
27 #include <string.h>
28 #include <algorithm>
29 #include <atomic>
30 #include <deque>
31 #include <mutex>
32 #include <new>
33 #include <string>
34 #include <unordered_map>
35 #include <unordered_set>
36 #include <utility>
37 #include <vector>
38
39 #include "util/logging.h"
40 #include "util/mix.h"
41 #include "util/mutex.h"
42 #include "util/strutil.h"
43 #include "re2/pod_array.h"
44 #include "re2/prog.h"
45 #include "re2/re2.h"
46 #include "re2/sparse_set.h"
47 #include "re2/stringpiece.h"
48
49 // Silence "zero-sized array in struct/union" warning for DFA::State::next_.
50 #ifdef _MSC_VER
51 #pragma warning(disable: 4200)
52 #endif
53
54 namespace re2 {
55
56 #if !defined(__linux__) /* only Linux seems to have memrchr */
memrchr(const void * s,int c,size_t n)57 static void* memrchr(const void* s, int c, size_t n) {
58 const unsigned char* p = (const unsigned char*)s;
59 for (p += n; n > 0; n--)
60 if (*--p == c)
61 return (void*)p;
62
63 return NULL;
64 }
65 #endif
66
67 // Controls whether the DFA should bail out early if the NFA would be faster.
68 static bool dfa_should_bail_when_slow = true;
69
70 // Changing this to true compiles in prints that trace execution of the DFA.
71 // Generates a lot of output -- only useful for debugging.
72 static const bool ExtraDebug = false;
73
74 // A DFA implementation of a regular expression program.
75 // Since this is entirely a forward declaration mandated by C++,
76 // some of the comments here are better understood after reading
77 // the comments in the sections that follow the DFA definition.
78 class DFA {
79 public:
80 DFA(Prog* prog, Prog::MatchKind kind, int64_t max_mem);
81 ~DFA();
ok() const82 bool ok() const { return !init_failed_; }
kind()83 Prog::MatchKind kind() { return kind_; }
84
85 // Searches for the regular expression in text, which is considered
86 // as a subsection of context for the purposes of interpreting flags
87 // like ^ and $ and \A and \z.
88 // Returns whether a match was found.
89 // If a match is found, sets *ep to the end point of the best match in text.
90 // If "anchored", the match must begin at the start of text.
91 // If "want_earliest_match", the match that ends first is used, not
92 // necessarily the best one.
93 // If "run_forward" is true, the DFA runs from text.begin() to text.end().
94 // If it is false, the DFA runs from text.end() to text.begin(),
95 // returning the leftmost end of the match instead of the rightmost one.
96 // If the DFA cannot complete the search (for example, if it is out of
97 // memory), it sets *failed and returns false.
98 bool Search(const StringPiece& text, const StringPiece& context,
99 bool anchored, bool want_earliest_match, bool run_forward,
100 bool* failed, const char** ep, SparseSet* matches);
101
102 // Builds out all states for the entire DFA.
103 // If cb is not empty, it receives one callback per state built.
104 // Returns the number of states built.
105 // FOR TESTING OR EXPERIMENTAL PURPOSES ONLY.
106 int BuildAllStates(const Prog::DFAStateCallback& cb);
107
108 // Computes min and max for matching strings. Won't return strings
109 // bigger than maxlen.
110 bool PossibleMatchRange(std::string* min, std::string* max, int maxlen);
111
112 // These data structures are logically private, but C++ makes it too
113 // difficult to mark them as such.
114 class RWLocker;
115 class StateSaver;
116 class Workq;
117
118 // A single DFA state. The DFA is represented as a graph of these
119 // States, linked by the next_ pointers. If in state s and reading
120 // byte c, the next state should be s->next_[c].
121 struct State {
IsMatchre2::DFA::State122 inline bool IsMatch() const { return (flag_ & kFlagMatch) != 0; }
123
124 int* inst_; // Instruction pointers in the state.
125 int ninst_; // # of inst_ pointers.
126 uint32_t flag_; // Empty string bitfield flags in effect on the way
127 // into this state, along with kFlagMatch if this
128 // is a matching state.
129
130 // Work around the bug affecting flexible array members in GCC 6.x (for x >= 1).
131 // (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=70932)
132 #if !defined(__clang__) && defined(__GNUC__) && __GNUC__ == 6 && __GNUC_MINOR__ >= 1
133 std::atomic<State*> next_[0]; // Outgoing arrows from State,
134 #else
135 std::atomic<State*> next_[]; // Outgoing arrows from State,
136 #endif
137
138 // one per input byte class
139 };
140
141 enum {
142 kByteEndText = 256, // imaginary byte at end of text
143
144 kFlagEmptyMask = 0xFF, // State.flag_: bits holding kEmptyXXX flags
145 kFlagMatch = 0x0100, // State.flag_: this is a matching state
146 kFlagLastWord = 0x0200, // State.flag_: last byte was a word char
147 kFlagNeedShift = 16, // needed kEmpty bits are or'ed in shifted left
148 };
149
150 struct StateHash {
operator ()re2::DFA::StateHash151 size_t operator()(const State* a) const {
152 DCHECK(a != NULL);
153 HashMix mix(a->flag_);
154 for (int i = 0; i < a->ninst_; i++)
155 mix.Mix(a->inst_[i]);
156 mix.Mix(0);
157 return mix.get();
158 }
159 };
160
161 struct StateEqual {
operator ()re2::DFA::StateEqual162 bool operator()(const State* a, const State* b) const {
163 DCHECK(a != NULL);
164 DCHECK(b != NULL);
165 if (a == b)
166 return true;
167 if (a->flag_ != b->flag_)
168 return false;
169 if (a->ninst_ != b->ninst_)
170 return false;
171 for (int i = 0; i < a->ninst_; i++)
172 if (a->inst_[i] != b->inst_[i])
173 return false;
174 return true;
175 }
176 };
177
178 typedef std::unordered_set<State*, StateHash, StateEqual> StateSet;
179
180 private:
181 // Special "first_byte" values for a state. (Values >= 0 denote actual bytes.)
182 enum {
183 kFbUnknown = -1, // No analysis has been performed.
184 kFbNone = -2, // The first-byte trick cannot be used.
185 };
186
187 enum {
188 // Indices into start_ for unanchored searches.
189 // Add kStartAnchored for anchored searches.
190 kStartBeginText = 0, // text at beginning of context
191 kStartBeginLine = 2, // text at beginning of line
192 kStartAfterWordChar = 4, // text follows a word character
193 kStartAfterNonWordChar = 6, // text follows non-word character
194 kMaxStart = 8,
195
196 kStartAnchored = 1,
197 };
198
199 // Resets the DFA State cache, flushing all saved State* information.
200 // Releases and reacquires cache_mutex_ via cache_lock, so any
201 // State* existing before the call are not valid after the call.
202 // Use a StateSaver to preserve important states across the call.
203 // cache_mutex_.r <= L < mutex_
204 // After: cache_mutex_.w <= L < mutex_
205 void ResetCache(RWLocker* cache_lock);
206
207 // Looks up and returns the State corresponding to a Workq.
208 // L >= mutex_
209 State* WorkqToCachedState(Workq* q, Workq* mq, uint32_t flag);
210
211 // Looks up and returns a State matching the inst, ninst, and flag.
212 // L >= mutex_
213 State* CachedState(int* inst, int ninst, uint32_t flag);
214
215 // Clear the cache entirely.
216 // Must hold cache_mutex_.w or be in destructor.
217 void ClearCache();
218
219 // Converts a State into a Workq: the opposite of WorkqToCachedState.
220 // L >= mutex_
221 void StateToWorkq(State* s, Workq* q);
222
223 // Runs a State on a given byte, returning the next state.
224 State* RunStateOnByteUnlocked(State*, int); // cache_mutex_.r <= L < mutex_
225 State* RunStateOnByte(State*, int); // L >= mutex_
226
227 // Runs a Workq on a given byte followed by a set of empty-string flags,
228 // producing a new Workq in nq. If a match instruction is encountered,
229 // sets *ismatch to true.
230 // L >= mutex_
231 void RunWorkqOnByte(Workq* q, Workq* nq,
232 int c, uint32_t flag, bool* ismatch);
233
234 // Runs a Workq on a set of empty-string flags, producing a new Workq in nq.
235 // L >= mutex_
236 void RunWorkqOnEmptyString(Workq* q, Workq* nq, uint32_t flag);
237
238 // Adds the instruction id to the Workq, following empty arrows
239 // according to flag.
240 // L >= mutex_
241 void AddToQueue(Workq* q, int id, uint32_t flag);
242
243 // For debugging, returns a text representation of State.
244 static std::string DumpState(State* state);
245
246 // For debugging, returns a text representation of a Workq.
247 static std::string DumpWorkq(Workq* q);
248
249 // Search parameters
250 struct SearchParams {
SearchParamsre2::DFA::SearchParams251 SearchParams(const StringPiece& text, const StringPiece& context,
252 RWLocker* cache_lock)
253 : text(text), context(context),
254 anchored(false),
255 want_earliest_match(false),
256 run_forward(false),
257 start(NULL),
258 first_byte(kFbUnknown),
259 cache_lock(cache_lock),
260 failed(false),
261 ep(NULL),
262 matches(NULL) { }
263
264 StringPiece text;
265 StringPiece context;
266 bool anchored;
267 bool want_earliest_match;
268 bool run_forward;
269 State* start;
270 int first_byte;
271 RWLocker *cache_lock;
272 bool failed; // "out" parameter: whether search gave up
273 const char* ep; // "out" parameter: end pointer for match
274 SparseSet* matches;
275
276 private:
277 SearchParams(const SearchParams&) = delete;
278 SearchParams& operator=(const SearchParams&) = delete;
279 };
280
281 // Before each search, the parameters to Search are analyzed by
282 // AnalyzeSearch to determine the state in which to start and the
283 // "first_byte" for that state, if any.
284 struct StartInfo {
StartInfore2::DFA::StartInfo285 StartInfo() : start(NULL), first_byte(kFbUnknown) {}
286 State* start;
287 std::atomic<int> first_byte;
288 };
289
290 // Fills in params->start and params->first_byte using
291 // the other search parameters. Returns true on success,
292 // false on failure.
293 // cache_mutex_.r <= L < mutex_
294 bool AnalyzeSearch(SearchParams* params);
295 bool AnalyzeSearchHelper(SearchParams* params, StartInfo* info,
296 uint32_t flags);
297
298 // The generic search loop, inlined to create specialized versions.
299 // cache_mutex_.r <= L < mutex_
300 // Might unlock and relock cache_mutex_ via params->cache_lock.
301 inline bool InlinedSearchLoop(SearchParams* params,
302 bool have_first_byte,
303 bool want_earliest_match,
304 bool run_forward);
305
306 // The specialized versions of InlinedSearchLoop. The three letters
307 // at the ends of the name denote the true/false values used as the
308 // last three parameters of InlinedSearchLoop.
309 // cache_mutex_.r <= L < mutex_
310 // Might unlock and relock cache_mutex_ via params->cache_lock.
311 bool SearchFFF(SearchParams* params);
312 bool SearchFFT(SearchParams* params);
313 bool SearchFTF(SearchParams* params);
314 bool SearchFTT(SearchParams* params);
315 bool SearchTFF(SearchParams* params);
316 bool SearchTFT(SearchParams* params);
317 bool SearchTTF(SearchParams* params);
318 bool SearchTTT(SearchParams* params);
319
320 // The main search loop: calls an appropriate specialized version of
321 // InlinedSearchLoop.
322 // cache_mutex_.r <= L < mutex_
323 // Might unlock and relock cache_mutex_ via params->cache_lock.
324 bool FastSearchLoop(SearchParams* params);
325
326 // For debugging, a slow search loop that calls InlinedSearchLoop
327 // directly -- because the booleans passed are not constants, the
328 // loop is not specialized like the SearchFFF etc. versions, so it
329 // runs much more slowly. Useful only for debugging.
330 // cache_mutex_.r <= L < mutex_
331 // Might unlock and relock cache_mutex_ via params->cache_lock.
332 bool SlowSearchLoop(SearchParams* params);
333
334 // Looks up bytes in bytemap_ but handles case c == kByteEndText too.
ByteMap(int c)335 int ByteMap(int c) {
336 if (c == kByteEndText)
337 return prog_->bytemap_range();
338 return prog_->bytemap()[c];
339 }
340
341 // Constant after initialization.
342 Prog* prog_; // The regular expression program to run.
343 Prog::MatchKind kind_; // The kind of DFA.
344 bool init_failed_; // initialization failed (out of memory)
345
346 Mutex mutex_; // mutex_ >= cache_mutex_.r
347
348 // Scratch areas, protected by mutex_.
349 Workq* q0_; // Two pre-allocated work queues.
350 Workq* q1_;
351 PODArray<int> stack_; // Pre-allocated stack for AddToQueue
352
353 // State* cache. Many threads use and add to the cache simultaneously,
354 // holding cache_mutex_ for reading and mutex_ (above) when adding.
355 // If the cache fills and needs to be discarded, the discarding is done
356 // while holding cache_mutex_ for writing, to avoid interrupting other
357 // readers. Any State* pointers are only valid while cache_mutex_
358 // is held.
359 Mutex cache_mutex_;
360 int64_t mem_budget_; // Total memory budget for all States.
361 int64_t state_budget_; // Amount of memory remaining for new States.
362 StateSet state_cache_; // All States computed so far.
363 StartInfo start_[kMaxStart];
364 };
365
366 // Shorthand for casting to uint8_t*.
BytePtr(const void * v)367 static inline const uint8_t* BytePtr(const void* v) {
368 return reinterpret_cast<const uint8_t*>(v);
369 }
370
371 // Work queues
372
373 // Marks separate thread groups of different priority
374 // in the work queue when in leftmost-longest matching mode.
375 #define Mark (-1)
376
377 // Separates the match IDs from the instructions in inst_.
378 // Used only for "many match" DFA states.
379 #define MatchSep (-2)
380
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 {
387 public:
388 // Constructor: n is number of normal slots, maxmark number of mark slots.
Workq(int n,int maxmark)389 Workq(int n, int maxmark) :
390 SparseSet(n+maxmark),
391 n_(n),
392 maxmark_(maxmark),
393 nextmark_(n),
394 last_was_mark_(true) {
395 }
396
is_mark(int i)397 bool is_mark(int i) { return i >= n_; }
398
maxmark()399 int maxmark() { return maxmark_; }
400
clear()401 void clear() {
402 SparseSet::clear();
403 nextmark_ = n_;
404 }
405
mark()406 void mark() {
407 if (last_was_mark_)
408 return;
409 last_was_mark_ = false;
410 SparseSet::insert_new(nextmark_++);
411 }
412
size()413 int size() {
414 return n_ + maxmark_;
415 }
416
insert(int id)417 void insert(int id) {
418 if (contains(id))
419 return;
420 insert_new(id);
421 }
422
insert_new(int id)423 void insert_new(int id) {
424 last_was_mark_ = false;
425 SparseSet::insert_new(id);
426 }
427
428 private:
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
434 Workq(const Workq&) = delete;
435 Workq& operator=(const Workq&) = delete;
436 };
437
DFA(Prog * prog,Prog::MatchKind kind,int64_t max_mem)438 DFA::DFA(Prog* prog, Prog::MatchKind kind, int64_t max_mem)
439 : prog_(prog),
440 kind_(kind),
441 init_failed_(false),
442 q0_(NULL),
443 q1_(NULL),
444 mem_budget_(max_mem) {
445 if (ExtraDebug)
446 fprintf(stderr, "\nkind %d\n%s\n", kind_, prog_->DumpUnanchored().c_str());
447 int nmark = 0;
448 if (kind_ == Prog::kLongestMatch)
449 nmark = prog_->size();
450 // See DFA::AddToQueue() for why this is so.
451 int nstack = prog_->inst_count(kInstCapture) +
452 prog_->inst_count(kInstEmptyWidth) +
453 prog_->inst_count(kInstNop) +
454 nmark + 1; // + 1 for start inst
455
456 // Account for space needed for DFA, q0, q1, stack.
457 mem_budget_ -= sizeof(DFA);
458 mem_budget_ -= (prog_->size() + nmark) *
459 (sizeof(int)+sizeof(int)) * 2; // q0, q1
460 mem_budget_ -= nstack * sizeof(int); // stack
461 if (mem_budget_ < 0) {
462 init_failed_ = true;
463 return;
464 }
465
466 state_budget_ = mem_budget_;
467
468 // Make sure there is a reasonable amount of working room left.
469 // At minimum, the search requires room for two states in order
470 // to limp along, restarting frequently. We'll get better performance
471 // if there is room for a larger number of states, say 20.
472 // Note that a state stores list heads only, so we use the program
473 // list count for the upper bound, not the program size.
474 int nnext = prog_->bytemap_range() + 1; // + 1 for kByteEndText slot
475 int64_t one_state = sizeof(State) + nnext*sizeof(std::atomic<State*>) +
476 (prog_->list_count()+nmark)*sizeof(int);
477 if (state_budget_ < 20*one_state) {
478 init_failed_ = true;
479 return;
480 }
481
482 q0_ = new Workq(prog_->size(), nmark);
483 q1_ = new Workq(prog_->size(), nmark);
484 stack_ = PODArray<int>(nstack);
485 }
486
~DFA()487 DFA::~DFA() {
488 delete q0_;
489 delete q1_;
490 ClearCache();
491 }
492
493 // In the DFA state graph, s->next[c] == NULL means that the
494 // state has not yet been computed and needs to be. We need
495 // a different special value to signal that s->next[c] is a
496 // state that can never lead to a match (and thus the search
497 // can be called off). Hence DeadState.
498 #define DeadState reinterpret_cast<State*>(1)
499
500 // Signals that the rest of the string matches no matter what it is.
501 #define FullMatchState reinterpret_cast<State*>(2)
502
503 #define SpecialStateMax FullMatchState
504
505 // Debugging printouts
506
507 // For debugging, returns a string representation of the work queue.
DumpWorkq(Workq * q)508 std::string DFA::DumpWorkq(Workq* q) {
509 std::string s;
510 const char* sep = "";
511 for (Workq::iterator it = q->begin(); it != q->end(); ++it) {
512 if (q->is_mark(*it)) {
513 s += "|";
514 sep = "";
515 } else {
516 s += StringPrintf("%s%d", sep, *it);
517 sep = ",";
518 }
519 }
520 return s;
521 }
522
523 // For debugging, returns a string representation of the state.
DumpState(State * state)524 std::string DFA::DumpState(State* state) {
525 if (state == NULL)
526 return "_";
527 if (state == DeadState)
528 return "X";
529 if (state == FullMatchState)
530 return "*";
531 std::string s;
532 const char* sep = "";
533 s += StringPrintf("(%p)", state);
534 for (int i = 0; i < state->ninst_; i++) {
535 if (state->inst_[i] == Mark) {
536 s += "|";
537 sep = "";
538 } else if (state->inst_[i] == MatchSep) {
539 s += "||";
540 sep = "";
541 } else {
542 s += StringPrintf("%s%d", sep, state->inst_[i]);
543 sep = ",";
544 }
545 }
546 s += StringPrintf(" flag=%#x", state->flag_);
547 return s;
548 }
549
550 //////////////////////////////////////////////////////////////////////
551 //
552 // DFA state graph construction.
553 //
554 // The DFA state graph is a heavily-linked collection of State* structures.
555 // The state_cache_ is a set of all the State structures ever allocated,
556 // so that if the same state is reached by two different paths,
557 // the same State structure can be used. This reduces allocation
558 // requirements and also avoids duplication of effort across the two
559 // identical states.
560 //
561 // A State is defined by an ordered list of instruction ids and a flag word.
562 //
563 // The choice of an ordered list of instructions differs from a typical
564 // textbook DFA implementation, which would use an unordered set.
565 // Textbook descriptions, however, only care about whether
566 // the DFA matches, not where it matches in the text. To decide where the
567 // DFA matches, we need to mimic the behavior of the dominant backtracking
568 // implementations like PCRE, which try one possible regular expression
569 // execution, then another, then another, stopping when one of them succeeds.
570 // The DFA execution tries these many executions in parallel, representing
571 // each by an instruction id. These pointers are ordered in the State.inst_
572 // list in the same order that the executions would happen in a backtracking
573 // search: if a match is found during execution of inst_[2], inst_[i] for i>=3
574 // can be discarded.
575 //
576 // Textbooks also typically do not consider context-aware empty string operators
577 // like ^ or $. These are handled by the flag word, which specifies the set
578 // of empty-string operators that should be matched when executing at the
579 // current text position. These flag bits are defined in prog.h.
580 // The flag word also contains two DFA-specific bits: kFlagMatch if the state
581 // is a matching state (one that reached a kInstMatch in the program)
582 // and kFlagLastWord if the last processed byte was a word character, for the
583 // implementation of \B and \b.
584 //
585 // The flag word also contains, shifted up 16 bits, the bits looked for by
586 // any kInstEmptyWidth instructions in the state. These provide a useful
587 // summary indicating when new flags might be useful.
588 //
589 // The permanent representation of a State's instruction ids is just an array,
590 // but while a state is being analyzed, these instruction ids are represented
591 // as a Workq, which is an array that allows iteration in insertion order.
592
593 // NOTE(rsc): The choice of State construction determines whether the DFA
594 // mimics backtracking implementations (so-called leftmost first matching) or
595 // traditional DFA implementations (so-called leftmost longest matching as
596 // prescribed by POSIX). This implementation chooses to mimic the
597 // backtracking implementations, because we want to replace PCRE. To get
598 // POSIX behavior, the states would need to be considered not as a simple
599 // ordered list of instruction ids, but as a list of unordered sets of instruction
600 // ids. A match by a state in one set would inhibit the running of sets
601 // farther down the list but not other instruction ids in the same set. Each
602 // set would correspond to matches beginning at a given point in the string.
603 // This is implemented by separating different sets with Mark pointers.
604
605 // Looks in the State cache for a State matching q, flag.
606 // If one is found, returns it. If one is not found, allocates one,
607 // inserts it in the cache, and returns it.
608 // If mq is not null, MatchSep and the match IDs in mq will be appended
609 // to the State.
WorkqToCachedState(Workq * q,Workq * mq,uint32_t flag)610 DFA::State* DFA::WorkqToCachedState(Workq* q, Workq* mq, uint32_t flag) {
611 //mutex_.AssertHeld();
612
613 // Construct array of instruction ids for the new state.
614 // Only ByteRange, EmptyWidth, and Match instructions are useful to keep:
615 // those are the only operators with any effect in
616 // RunWorkqOnEmptyString or RunWorkqOnByte.
617 int* inst = new int[q->size()];
618 int n = 0;
619 uint32_t needflags = 0; // flags needed by kInstEmptyWidth instructions
620 bool sawmatch = false; // whether queue contains guaranteed kInstMatch
621 bool sawmark = false; // whether queue contains a Mark
622 if (ExtraDebug)
623 fprintf(stderr, "WorkqToCachedState %s [%#x]", DumpWorkq(q).c_str(), flag);
624 for (Workq::iterator it = q->begin(); it != q->end(); ++it) {
625 int id = *it;
626 if (sawmatch && (kind_ == Prog::kFirstMatch || q->is_mark(id)))
627 break;
628 if (q->is_mark(id)) {
629 if (n > 0 && inst[n-1] != Mark) {
630 sawmark = true;
631 inst[n++] = Mark;
632 }
633 continue;
634 }
635 Prog::Inst* ip = prog_->inst(id);
636 switch (ip->opcode()) {
637 case kInstAltMatch:
638 // This state will continue to a match no matter what
639 // the rest of the input is. If it is the highest priority match
640 // being considered, return the special FullMatchState
641 // to indicate that it's all matches from here out.
642 if (kind_ != Prog::kManyMatch &&
643 (kind_ != Prog::kFirstMatch ||
644 (it == q->begin() && ip->greedy(prog_))) &&
645 (kind_ != Prog::kLongestMatch || !sawmark) &&
646 (flag & kFlagMatch)) {
647 delete[] inst;
648 if (ExtraDebug)
649 fprintf(stderr, " -> FullMatchState\n");
650 return FullMatchState;
651 }
652 FALLTHROUGH_INTENDED;
653 default:
654 // Record iff id is the head of its list, which must
655 // be the case if id-1 is the last of *its* list. :)
656 if (prog_->inst(id-1)->last())
657 inst[n++] = *it;
658 if (ip->opcode() == kInstEmptyWidth)
659 needflags |= ip->empty();
660 if (ip->opcode() == kInstMatch && !prog_->anchor_end())
661 sawmatch = true;
662 break;
663 }
664 }
665 DCHECK_LE(n, q->size());
666 if (n > 0 && inst[n-1] == Mark)
667 n--;
668
669 // If there are no empty-width instructions waiting to execute,
670 // then the extra flag bits will not be used, so there is no
671 // point in saving them. (Discarding them reduces the number
672 // of distinct states.)
673 if (needflags == 0)
674 flag &= kFlagMatch;
675
676 // NOTE(rsc): The code above cannot do flag &= needflags,
677 // because if the right flags were present to pass the current
678 // kInstEmptyWidth instructions, new kInstEmptyWidth instructions
679 // might be reached that in turn need different flags.
680 // The only sure thing is that if there are no kInstEmptyWidth
681 // instructions at all, no flags will be needed.
682 // We could do the extra work to figure out the full set of
683 // possibly needed flags by exploring past the kInstEmptyWidth
684 // instructions, but the check above -- are any flags needed
685 // at all? -- handles the most common case. More fine-grained
686 // analysis can only be justified by measurements showing that
687 // too many redundant states are being allocated.
688
689 // If there are no Insts in the list, it's a dead state,
690 // which is useful to signal with a special pointer so that
691 // the execution loop can stop early. This is only okay
692 // if the state is *not* a matching state.
693 if (n == 0 && flag == 0) {
694 delete[] inst;
695 if (ExtraDebug)
696 fprintf(stderr, " -> DeadState\n");
697 return DeadState;
698 }
699
700 // If we're in longest match mode, the state is a sequence of
701 // unordered state sets separated by Marks. Sort each set
702 // to canonicalize, to reduce the number of distinct sets stored.
703 if (kind_ == Prog::kLongestMatch) {
704 int* ip = inst;
705 int* ep = ip + n;
706 while (ip < ep) {
707 int* markp = ip;
708 while (markp < ep && *markp != Mark)
709 markp++;
710 std::sort(ip, markp);
711 if (markp < ep)
712 markp++;
713 ip = markp;
714 }
715 }
716
717 // If we're in many match mode, canonicalize for similar reasons:
718 // we have an unordered set of states (i.e. we don't have Marks)
719 // and sorting will reduce the number of distinct sets stored.
720 if (kind_ == Prog::kManyMatch) {
721 int* ip = inst;
722 int* ep = ip + n;
723 std::sort(ip, ep);
724 }
725
726 // Append MatchSep and the match IDs in mq if necessary.
727 if (mq != NULL) {
728 inst[n++] = MatchSep;
729 for (Workq::iterator i = mq->begin(); i != mq->end(); ++i) {
730 int id = *i;
731 Prog::Inst* ip = prog_->inst(id);
732 if (ip->opcode() == kInstMatch)
733 inst[n++] = ip->match_id();
734 }
735 }
736
737 // Save the needed empty-width flags in the top bits for use later.
738 flag |= needflags << kFlagNeedShift;
739
740 State* state = CachedState(inst, n, flag);
741 delete[] inst;
742 return state;
743 }
744
745 // Looks in the State cache for a State matching inst, ninst, flag.
746 // If one is found, returns it. If one is not found, allocates one,
747 // inserts it in the cache, and returns it.
CachedState(int * inst,int ninst,uint32_t flag)748 DFA::State* DFA::CachedState(int* inst, int ninst, uint32_t flag) {
749 //mutex_.AssertHeld();
750
751 // Look in the cache for a pre-existing state.
752 // We have to initialise the struct like this because otherwise
753 // MSVC will complain about the flexible array member. :(
754 State state;
755 state.inst_ = inst;
756 state.ninst_ = ninst;
757 state.flag_ = flag;
758 StateSet::iterator it = state_cache_.find(&state);
759 if (it != state_cache_.end()) {
760 if (ExtraDebug)
761 fprintf(stderr, " -cached-> %s\n", DumpState(*it).c_str());
762 return *it;
763 }
764
765 // Must have enough memory for new state.
766 // In addition to what we're going to allocate,
767 // the state cache hash table seems to incur about 40 bytes per
768 // State*, empirically.
769 const int kStateCacheOverhead = 40;
770 int nnext = prog_->bytemap_range() + 1; // + 1 for kByteEndText slot
771 int mem = sizeof(State) + nnext*sizeof(std::atomic<State*>) +
772 ninst*sizeof(int);
773 if (mem_budget_ < mem + kStateCacheOverhead) {
774 mem_budget_ = -1;
775 return NULL;
776 }
777 mem_budget_ -= mem + kStateCacheOverhead;
778
779 // Allocate new state along with room for next_ and inst_.
780 char* space = std::allocator<char>().allocate(mem);
781 State* s = new (space) State;
782 (void) new (s->next_) std::atomic<State*>[nnext];
783 // Work around a unfortunate bug in older versions of libstdc++.
784 // (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64658)
785 for (int i = 0; i < nnext; i++)
786 (void) new (s->next_ + i) std::atomic<State*>(NULL);
787 s->inst_ = new (s->next_ + nnext) int[ninst];
788 memmove(s->inst_, inst, ninst*sizeof s->inst_[0]);
789 s->ninst_ = ninst;
790 s->flag_ = flag;
791 if (ExtraDebug)
792 fprintf(stderr, " -> %s\n", DumpState(s).c_str());
793
794 // Put state in cache and return it.
795 state_cache_.insert(s);
796 return s;
797 }
798
799 // Clear the cache. Must hold cache_mutex_.w or be in destructor.
ClearCache()800 void DFA::ClearCache() {
801 StateSet::iterator begin = state_cache_.begin();
802 StateSet::iterator end = state_cache_.end();
803 while (begin != end) {
804 StateSet::iterator tmp = begin;
805 ++begin;
806 // Deallocate the blob of memory that we allocated in DFA::CachedState().
807 // We recompute mem in order to benefit from sized delete where possible.
808 int ninst = (*tmp)->ninst_;
809 int nnext = prog_->bytemap_range() + 1; // + 1 for kByteEndText slot
810 int mem = sizeof(State) + nnext*sizeof(std::atomic<State*>) +
811 ninst*sizeof(int);
812 std::allocator<char>().deallocate(reinterpret_cast<char*>(*tmp), mem);
813 }
814 state_cache_.clear();
815 }
816
817 // Copies insts in state s to the work queue q.
StateToWorkq(State * s,Workq * q)818 void DFA::StateToWorkq(State* s, Workq* q) {
819 q->clear();
820 for (int i = 0; i < s->ninst_; i++) {
821 if (s->inst_[i] == Mark) {
822 q->mark();
823 } else if (s->inst_[i] == MatchSep) {
824 // Nothing after this is an instruction!
825 break;
826 } else {
827 // Explore from the head of the list.
828 AddToQueue(q, s->inst_[i], s->flag_ & kFlagEmptyMask);
829 }
830 }
831 }
832
833 // Adds ip to the work queue, following empty arrows according to flag.
AddToQueue(Workq * q,int id,uint32_t flag)834 void DFA::AddToQueue(Workq* q, int id, uint32_t flag) {
835
836 // Use stack_ to hold our stack of instructions yet to process.
837 // It was preallocated as follows:
838 // one entry per Capture;
839 // one entry per EmptyWidth; and
840 // one entry per Nop.
841 // This reflects the maximum number of stack pushes that each can
842 // perform. (Each instruction can be processed at most once.)
843 // When using marks, we also added nmark == prog_->size().
844 // (Otherwise, nmark == 0.)
845 int* stk = stack_.data();
846 int nstk = 0;
847
848 stk[nstk++] = id;
849 while (nstk > 0) {
850 DCHECK_LE(nstk, stack_.size());
851 id = stk[--nstk];
852
853 Loop:
854 if (id == Mark) {
855 q->mark();
856 continue;
857 }
858
859 if (id == 0)
860 continue;
861
862 // If ip is already on the queue, nothing to do.
863 // Otherwise add it. We don't actually keep all the
864 // ones that get added, but adding all of them here
865 // increases the likelihood of q->contains(id),
866 // reducing the amount of duplicated work.
867 if (q->contains(id))
868 continue;
869 q->insert_new(id);
870
871 // Process instruction.
872 Prog::Inst* ip = prog_->inst(id);
873 switch (ip->opcode()) {
874 default:
875 LOG(DFATAL) << "unhandled opcode: " << ip->opcode();
876 break;
877
878 case kInstByteRange: // just save these on the queue
879 case kInstMatch:
880 if (ip->last())
881 break;
882 id = id+1;
883 goto Loop;
884
885 case kInstCapture: // DFA treats captures as no-ops.
886 case kInstNop:
887 if (!ip->last())
888 stk[nstk++] = id+1;
889
890 // If this instruction is the [00-FF]* loop at the beginning of
891 // a leftmost-longest unanchored search, separate with a Mark so
892 // that future threads (which will start farther to the right in
893 // the input string) are lower priority than current threads.
894 if (ip->opcode() == kInstNop && q->maxmark() > 0 &&
895 id == prog_->start_unanchored() && id != prog_->start())
896 stk[nstk++] = Mark;
897 id = ip->out();
898 goto Loop;
899
900 case kInstAltMatch:
901 DCHECK(!ip->last());
902 id = id+1;
903 goto Loop;
904
905 case kInstEmptyWidth:
906 if (!ip->last())
907 stk[nstk++] = id+1;
908
909 // Continue on if we have all the right flag bits.
910 if (ip->empty() & ~flag)
911 break;
912 id = ip->out();
913 goto Loop;
914 }
915 }
916 }
917
918 // Running of work queues. In the work queue, order matters:
919 // the queue is sorted in priority order. If instruction i comes before j,
920 // then the instructions that i produces during the run must come before
921 // the ones that j produces. In order to keep this invariant, all the
922 // work queue runners have to take an old queue to process and then
923 // also a new queue to fill in. It's not acceptable to add to the end of
924 // an existing queue, because new instructions will not end up in the
925 // correct position.
926
927 // Runs the work queue, processing the empty strings indicated by flag.
928 // For example, flag == kEmptyBeginLine|kEmptyEndLine means to match
929 // both ^ and $. It is important that callers pass all flags at once:
930 // processing both ^ and $ is not the same as first processing only ^
931 // and then processing only $. Doing the two-step sequence won't match
932 // ^$^$^$ but processing ^ and $ simultaneously will (and is the behavior
933 // exhibited by existing implementations).
RunWorkqOnEmptyString(Workq * oldq,Workq * newq,uint32_t flag)934 void DFA::RunWorkqOnEmptyString(Workq* oldq, Workq* newq, uint32_t flag) {
935 newq->clear();
936 for (Workq::iterator i = oldq->begin(); i != oldq->end(); ++i) {
937 if (oldq->is_mark(*i))
938 AddToQueue(newq, Mark, flag);
939 else
940 AddToQueue(newq, *i, flag);
941 }
942 }
943
944 // Runs the work queue, processing the single byte c followed by any empty
945 // strings indicated by flag. For example, c == 'a' and flag == kEmptyEndLine,
946 // means to match c$. Sets the bool *ismatch to true if the end of the
947 // regular expression program has been reached (the regexp has matched).
RunWorkqOnByte(Workq * oldq,Workq * newq,int c,uint32_t flag,bool * ismatch)948 void DFA::RunWorkqOnByte(Workq* oldq, Workq* newq,
949 int c, uint32_t flag, bool* ismatch) {
950 //mutex_.AssertHeld();
951
952 newq->clear();
953 for (Workq::iterator i = oldq->begin(); i != oldq->end(); ++i) {
954 if (oldq->is_mark(*i)) {
955 if (*ismatch)
956 return;
957 newq->mark();
958 continue;
959 }
960 int id = *i;
961 Prog::Inst* ip = prog_->inst(id);
962 switch (ip->opcode()) {
963 default:
964 LOG(DFATAL) << "unhandled opcode: " << ip->opcode();
965 break;
966
967 case kInstFail: // never succeeds
968 case kInstCapture: // already followed
969 case kInstNop: // already followed
970 case kInstAltMatch: // already followed
971 case kInstEmptyWidth: // already followed
972 break;
973
974 case kInstByteRange: // can follow if c is in range
975 if (!ip->Matches(c))
976 break;
977 AddToQueue(newq, ip->out(), flag);
978 if (ip->hint() != 0) {
979 // We have a hint, but we must cancel out the
980 // increment that will occur after the break.
981 i += ip->hint() - 1;
982 } else {
983 // We have no hint, so we must find the end
984 // of the current list and then skip to it.
985 Prog::Inst* ip0 = ip;
986 while (!ip->last())
987 ++ip;
988 i += ip - ip0;
989 }
990 break;
991
992 case kInstMatch:
993 if (prog_->anchor_end() && c != kByteEndText &&
994 kind_ != Prog::kManyMatch)
995 break;
996 *ismatch = true;
997 if (kind_ == Prog::kFirstMatch) {
998 // Can stop processing work queue since we found a match.
999 return;
1000 }
1001 break;
1002 }
1003 }
1004
1005 if (ExtraDebug)
1006 fprintf(stderr, "%s on %d[%#x] -> %s [%d]\n",
1007 DumpWorkq(oldq).c_str(), c, flag, DumpWorkq(newq).c_str(), *ismatch);
1008 }
1009
1010 // Processes input byte c in state, returning new state.
1011 // Caller does not hold mutex.
RunStateOnByteUnlocked(State * state,int c)1012 DFA::State* DFA::RunStateOnByteUnlocked(State* state, int c) {
1013 // Keep only one RunStateOnByte going
1014 // even if the DFA is being run by multiple threads.
1015 MutexLock l(&mutex_);
1016 return RunStateOnByte(state, c);
1017 }
1018
1019 // Processes input byte c in state, returning new state.
RunStateOnByte(State * state,int c)1020 DFA::State* DFA::RunStateOnByte(State* state, int c) {
1021 //mutex_.AssertHeld();
1022
1023 if (state <= SpecialStateMax) {
1024 if (state == FullMatchState) {
1025 // It is convenient for routines like PossibleMatchRange
1026 // if we implement RunStateOnByte for FullMatchState:
1027 // once you get into this state you never get out,
1028 // so it's pretty easy.
1029 return FullMatchState;
1030 }
1031 if (state == DeadState) {
1032 LOG(DFATAL) << "DeadState in RunStateOnByte";
1033 return NULL;
1034 }
1035 if (state == NULL) {
1036 LOG(DFATAL) << "NULL state in RunStateOnByte";
1037 return NULL;
1038 }
1039 LOG(DFATAL) << "Unexpected special state in RunStateOnByte";
1040 return NULL;
1041 }
1042
1043 // If someone else already computed this, return it.
1044 State* ns = state->next_[ByteMap(c)].load(std::memory_order_relaxed);
1045 if (ns != NULL)
1046 return ns;
1047
1048 // Convert state into Workq.
1049 StateToWorkq(state, q0_);
1050
1051 // Flags marking the kinds of empty-width things (^ $ etc)
1052 // around this byte. Before the byte we have the flags recorded
1053 // in the State structure itself. After the byte we have
1054 // nothing yet (but that will change: read on).
1055 uint32_t needflag = state->flag_ >> kFlagNeedShift;
1056 uint32_t beforeflag = state->flag_ & kFlagEmptyMask;
1057 uint32_t oldbeforeflag = beforeflag;
1058 uint32_t afterflag = 0;
1059
1060 if (c == '\n') {
1061 // Insert implicit $ and ^ around \n
1062 beforeflag |= kEmptyEndLine;
1063 afterflag |= kEmptyBeginLine;
1064 }
1065
1066 if (c == kByteEndText) {
1067 // Insert implicit $ and \z before the fake "end text" byte.
1068 beforeflag |= kEmptyEndLine | kEmptyEndText;
1069 }
1070
1071 // The state flag kFlagLastWord says whether the last
1072 // byte processed was a word character. Use that info to
1073 // insert empty-width (non-)word boundaries.
1074 bool islastword = (state->flag_ & kFlagLastWord) != 0;
1075 bool isword = c != kByteEndText && Prog::IsWordChar(static_cast<uint8_t>(c));
1076 if (isword == islastword)
1077 beforeflag |= kEmptyNonWordBoundary;
1078 else
1079 beforeflag |= kEmptyWordBoundary;
1080
1081 // Okay, finally ready to run.
1082 // Only useful to rerun on empty string if there are new, useful flags.
1083 if (beforeflag & ~oldbeforeflag & needflag) {
1084 RunWorkqOnEmptyString(q0_, q1_, beforeflag);
1085 using std::swap;
1086 swap(q0_, q1_);
1087 }
1088 bool ismatch = false;
1089 RunWorkqOnByte(q0_, q1_, c, afterflag, &ismatch);
1090 using std::swap;
1091 swap(q0_, q1_);
1092
1093 // Save afterflag along with ismatch and isword in new state.
1094 uint32_t flag = afterflag;
1095 if (ismatch)
1096 flag |= kFlagMatch;
1097 if (isword)
1098 flag |= kFlagLastWord;
1099
1100 if (ismatch && kind_ == Prog::kManyMatch)
1101 ns = WorkqToCachedState(q0_, q1_, flag);
1102 else
1103 ns = WorkqToCachedState(q0_, NULL, flag);
1104
1105 // Flush ns before linking to it.
1106 // Write barrier before updating state->next_ so that the
1107 // main search loop can proceed without any locking, for speed.
1108 // (Otherwise it would need one mutex operation per input byte.)
1109 state->next_[ByteMap(c)].store(ns, std::memory_order_release);
1110 return ns;
1111 }
1112
1113
1114 //////////////////////////////////////////////////////////////////////
1115 // DFA cache reset.
1116
1117 // Reader-writer lock helper.
1118 //
1119 // The DFA uses a reader-writer mutex to protect the state graph itself.
1120 // Traversing the state graph requires holding the mutex for reading,
1121 // and discarding the state graph and starting over requires holding the
1122 // lock for writing. If a search needs to expand the graph but is out
1123 // of memory, it will need to drop its read lock and then acquire the
1124 // write lock. Since it cannot then atomically downgrade from write lock
1125 // to read lock, it runs the rest of the search holding the write lock.
1126 // (This probably helps avoid repeated contention, but really the decision
1127 // is forced by the Mutex interface.) It's a bit complicated to keep
1128 // track of whether the lock is held for reading or writing and thread
1129 // that through the search, so instead we encapsulate it in the RWLocker
1130 // and pass that around.
1131
1132 class DFA::RWLocker {
1133 public:
1134 explicit RWLocker(Mutex* mu);
1135 ~RWLocker();
1136
1137 // If the lock is only held for reading right now,
1138 // drop the read lock and re-acquire for writing.
1139 // Subsequent calls to LockForWriting are no-ops.
1140 // Notice that the lock is *released* temporarily.
1141 void LockForWriting();
1142
1143 private:
1144 Mutex* mu_;
1145 bool writing_;
1146
1147 RWLocker(const RWLocker&) = delete;
1148 RWLocker& operator=(const RWLocker&) = delete;
1149 };
1150
RWLocker(Mutex * mu)1151 DFA::RWLocker::RWLocker(Mutex* mu) : mu_(mu), writing_(false) {
1152 mu_->ReaderLock();
1153 }
1154
1155 // This function is marked as NO_THREAD_SAFETY_ANALYSIS because
1156 // the annotations don't support lock upgrade.
LockForWriting()1157 void DFA::RWLocker::LockForWriting() NO_THREAD_SAFETY_ANALYSIS {
1158 if (!writing_) {
1159 mu_->ReaderUnlock();
1160 mu_->WriterLock();
1161 writing_ = true;
1162 }
1163 }
1164
~RWLocker()1165 DFA::RWLocker::~RWLocker() {
1166 if (!writing_)
1167 mu_->ReaderUnlock();
1168 else
1169 mu_->WriterUnlock();
1170 }
1171
1172
1173 // When the DFA's State cache fills, we discard all the states in the
1174 // cache and start over. Many threads can be using and adding to the
1175 // cache at the same time, so we synchronize using the cache_mutex_
1176 // to keep from stepping on other threads. Specifically, all the
1177 // threads using the current cache hold cache_mutex_ for reading.
1178 // When a thread decides to flush the cache, it drops cache_mutex_
1179 // and then re-acquires it for writing. That ensures there are no
1180 // other threads accessing the cache anymore. The rest of the search
1181 // runs holding cache_mutex_ for writing, avoiding any contention
1182 // with or cache pollution caused by other threads.
1183
ResetCache(RWLocker * cache_lock)1184 void DFA::ResetCache(RWLocker* cache_lock) {
1185 // Re-acquire the cache_mutex_ for writing (exclusive use).
1186 cache_lock->LockForWriting();
1187
1188 hooks::GetDFAStateCacheResetHook()({
1189 state_budget_,
1190 state_cache_.size(),
1191 });
1192
1193 // Clear the cache, reset the memory budget.
1194 for (int i = 0; i < kMaxStart; i++) {
1195 start_[i].start = NULL;
1196 start_[i].first_byte.store(kFbUnknown, std::memory_order_relaxed);
1197 }
1198 ClearCache();
1199 mem_budget_ = state_budget_;
1200 }
1201
1202 // Typically, a couple States do need to be preserved across a cache
1203 // reset, like the State at the current point in the search.
1204 // The StateSaver class helps keep States across cache resets.
1205 // It makes a copy of the state's guts outside the cache (before the reset)
1206 // and then can be asked, after the reset, to recreate the State
1207 // in the new cache. For example, in a DFA method ("this" is a DFA):
1208 //
1209 // StateSaver saver(this, s);
1210 // ResetCache(cache_lock);
1211 // s = saver.Restore();
1212 //
1213 // The saver should always have room in the cache to re-create the state,
1214 // because resetting the cache locks out all other threads, and the cache
1215 // is known to have room for at least a couple states (otherwise the DFA
1216 // constructor fails).
1217
1218 class DFA::StateSaver {
1219 public:
1220 explicit StateSaver(DFA* dfa, State* state);
1221 ~StateSaver();
1222
1223 // Recreates and returns a state equivalent to the
1224 // original state passed to the constructor.
1225 // Returns NULL if the cache has filled, but
1226 // since the DFA guarantees to have room in the cache
1227 // for a couple states, should never return NULL
1228 // if used right after ResetCache.
1229 State* Restore();
1230
1231 private:
1232 DFA* dfa_; // the DFA to use
1233 int* inst_; // saved info from State
1234 int ninst_;
1235 uint32_t flag_;
1236 bool is_special_; // whether original state was special
1237 State* special_; // if is_special_, the original state
1238
1239 StateSaver(const StateSaver&) = delete;
1240 StateSaver& operator=(const StateSaver&) = delete;
1241 };
1242
StateSaver(DFA * dfa,State * state)1243 DFA::StateSaver::StateSaver(DFA* dfa, State* state) {
1244 dfa_ = dfa;
1245 if (state <= SpecialStateMax) {
1246 inst_ = NULL;
1247 ninst_ = 0;
1248 flag_ = 0;
1249 is_special_ = true;
1250 special_ = state;
1251 return;
1252 }
1253 is_special_ = false;
1254 special_ = NULL;
1255 flag_ = state->flag_;
1256 ninst_ = state->ninst_;
1257 inst_ = new int[ninst_];
1258 memmove(inst_, state->inst_, ninst_*sizeof inst_[0]);
1259 }
1260
~StateSaver()1261 DFA::StateSaver::~StateSaver() {
1262 if (!is_special_)
1263 delete[] inst_;
1264 }
1265
Restore()1266 DFA::State* DFA::StateSaver::Restore() {
1267 if (is_special_)
1268 return special_;
1269 MutexLock l(&dfa_->mutex_);
1270 State* s = dfa_->CachedState(inst_, ninst_, flag_);
1271 if (s == NULL)
1272 LOG(DFATAL) << "StateSaver failed to restore state.";
1273 return s;
1274 }
1275
1276
1277 //////////////////////////////////////////////////////////////////////
1278 //
1279 // DFA execution.
1280 //
1281 // The basic search loop is easy: start in a state s and then for each
1282 // byte c in the input, s = s->next[c].
1283 //
1284 // This simple description omits a few efficiency-driven complications.
1285 //
1286 // First, the State graph is constructed incrementally: it is possible
1287 // that s->next[c] is null, indicating that that state has not been
1288 // fully explored. In this case, RunStateOnByte must be invoked to
1289 // determine the next state, which is cached in s->next[c] to save
1290 // future effort. An alternative reason for s->next[c] to be null is
1291 // that the DFA has reached a so-called "dead state", in which any match
1292 // is no longer possible. In this case RunStateOnByte will return NULL
1293 // and the processing of the string can stop early.
1294 //
1295 // Second, a 256-element pointer array for s->next_ makes each State
1296 // quite large (2kB on 64-bit machines). Instead, dfa->bytemap_[]
1297 // maps from bytes to "byte classes" and then next_ only needs to have
1298 // as many pointers as there are byte classes. A byte class is simply a
1299 // range of bytes that the regexp never distinguishes between.
1300 // A regexp looking for a[abc] would have four byte ranges -- 0 to 'a'-1,
1301 // 'a', 'b' to 'c', and 'c' to 0xFF. The bytemap slows us a little bit
1302 // but in exchange we typically cut the size of a State (and thus our
1303 // memory footprint) by about 5-10x. The comments still refer to
1304 // s->next[c] for simplicity, but code should refer to s->next_[bytemap_[c]].
1305 //
1306 // Third, it is common for a DFA for an unanchored match to begin in a
1307 // state in which only one particular byte value can take the DFA to a
1308 // different state. That is, s->next[c] != s for only one c. In this
1309 // situation, the DFA can do better than executing the simple loop.
1310 // Instead, it can call memchr to search very quickly for the byte c.
1311 // Whether the start state has this property is determined during a
1312 // pre-compilation pass, and if so, the byte b is passed to the search
1313 // loop as the "first_byte" argument, along with a boolean "have_first_byte".
1314 //
1315 // Fourth, the desired behavior is to search for the leftmost-best match
1316 // (approximately, the same one that Perl would find), which is not
1317 // necessarily the match ending earliest in the string. Each time a
1318 // match is found, it must be noted, but the DFA must continue on in
1319 // hope of finding a higher-priority match. In some cases, the caller only
1320 // cares whether there is any match at all, not which one is found.
1321 // The "want_earliest_match" flag causes the search to stop at the first
1322 // match found.
1323 //
1324 // Fifth, one algorithm that uses the DFA needs it to run over the
1325 // input string backward, beginning at the end and ending at the beginning.
1326 // Passing false for the "run_forward" flag causes the DFA to run backward.
1327 //
1328 // The checks for these last three cases, which in a naive implementation
1329 // would be performed once per input byte, slow the general loop enough
1330 // to merit specialized versions of the search loop for each of the
1331 // eight possible settings of the three booleans. Rather than write
1332 // eight different functions, we write one general implementation and then
1333 // inline it to create the specialized ones.
1334 //
1335 // Note that matches are delayed by one byte, to make it easier to
1336 // accomodate match conditions depending on the next input byte (like $ and \b).
1337 // When s->next[c]->IsMatch(), it means that there is a match ending just
1338 // *before* byte c.
1339
1340 // The generic search loop. Searches text for a match, returning
1341 // the pointer to the end of the chosen match, or NULL if no match.
1342 // The bools are equal to the same-named variables in params, but
1343 // making them function arguments lets the inliner specialize
1344 // this function to each combination (see two paragraphs above).
InlinedSearchLoop(SearchParams * params,bool have_first_byte,bool want_earliest_match,bool run_forward)1345 inline bool DFA::InlinedSearchLoop(SearchParams* params,
1346 bool have_first_byte,
1347 bool want_earliest_match,
1348 bool run_forward) {
1349 State* start = params->start;
1350 const uint8_t* bp = BytePtr(params->text.data()); // start of text
1351 const uint8_t* p = bp; // text scanning point
1352 const uint8_t* ep = BytePtr(params->text.data() +
1353 params->text.size()); // end of text
1354 const uint8_t* resetp = NULL; // p at last cache reset
1355 if (!run_forward) {
1356 using std::swap;
1357 swap(p, ep);
1358 }
1359
1360 const uint8_t* bytemap = prog_->bytemap();
1361 const uint8_t* lastmatch = NULL; // most recent matching position in text
1362 bool matched = false;
1363
1364 State* s = start;
1365 if (ExtraDebug)
1366 fprintf(stderr, "@stx: %s\n", DumpState(s).c_str());
1367
1368 if (s->IsMatch()) {
1369 matched = true;
1370 lastmatch = p;
1371 if (ExtraDebug)
1372 fprintf(stderr, "match @stx! [%s]\n", DumpState(s).c_str());
1373 if (params->matches != NULL && kind_ == Prog::kManyMatch) {
1374 for (int i = s->ninst_ - 1; i >= 0; i--) {
1375 int id = s->inst_[i];
1376 if (id == MatchSep)
1377 break;
1378 params->matches->insert(id);
1379 }
1380 }
1381 if (want_earliest_match) {
1382 params->ep = reinterpret_cast<const char*>(lastmatch);
1383 return true;
1384 }
1385 }
1386
1387 while (p != ep) {
1388 if (ExtraDebug)
1389 fprintf(stderr, "@%td: %s\n", p - bp, DumpState(s).c_str());
1390
1391 if (have_first_byte && s == start) {
1392 // In start state, only way out is to find first_byte,
1393 // so use optimized assembly in memchr to skip ahead.
1394 // If first_byte isn't found, we can skip to the end
1395 // of the string.
1396 if (run_forward) {
1397 if ((p = BytePtr(memchr(p, params->first_byte, ep - p))) == NULL) {
1398 p = ep;
1399 break;
1400 }
1401 } else {
1402 if ((p = BytePtr(memrchr(ep, params->first_byte, p - ep))) == NULL) {
1403 p = ep;
1404 break;
1405 }
1406 p++;
1407 }
1408 }
1409
1410 int c;
1411 if (run_forward)
1412 c = *p++;
1413 else
1414 c = *--p;
1415
1416 // Note that multiple threads might be consulting
1417 // s->next_[bytemap[c]] simultaneously.
1418 // RunStateOnByte takes care of the appropriate locking,
1419 // including a memory barrier so that the unlocked access
1420 // (sometimes known as "double-checked locking") is safe.
1421 // The alternative would be either one DFA per thread
1422 // or one mutex operation per input byte.
1423 //
1424 // ns == DeadState means the state is known to be dead
1425 // (no more matches are possible).
1426 // ns == NULL means the state has not yet been computed
1427 // (need to call RunStateOnByteUnlocked).
1428 // RunStateOnByte returns ns == NULL if it is out of memory.
1429 // ns == FullMatchState means the rest of the string matches.
1430 //
1431 // Okay to use bytemap[] not ByteMap() here, because
1432 // c is known to be an actual byte and not kByteEndText.
1433
1434 State* ns = s->next_[bytemap[c]].load(std::memory_order_acquire);
1435 if (ns == NULL) {
1436 ns = RunStateOnByteUnlocked(s, c);
1437 if (ns == NULL) {
1438 // After we reset the cache, we hold cache_mutex exclusively,
1439 // so if resetp != NULL, it means we filled the DFA state
1440 // cache with this search alone (without any other threads).
1441 // Benchmarks show that doing a state computation on every
1442 // byte runs at about 0.2 MB/s, while the NFA (nfa.cc) can do the
1443 // same at about 2 MB/s. Unless we're processing an average
1444 // of 10 bytes per state computation, fail so that RE2 can
1445 // fall back to the NFA. However, RE2::Set cannot fall back,
1446 // so we just have to keep on keeping on in that case.
1447 if (dfa_should_bail_when_slow && resetp != NULL &&
1448 static_cast<size_t>(p - resetp) < 10*state_cache_.size() &&
1449 kind_ != Prog::kManyMatch) {
1450 params->failed = true;
1451 return false;
1452 }
1453 resetp = p;
1454
1455 // Prepare to save start and s across the reset.
1456 StateSaver save_start(this, start);
1457 StateSaver save_s(this, s);
1458
1459 // Discard all the States in the cache.
1460 ResetCache(params->cache_lock);
1461
1462 // Restore start and s so we can continue.
1463 if ((start = save_start.Restore()) == NULL ||
1464 (s = save_s.Restore()) == NULL) {
1465 // Restore already did LOG(DFATAL).
1466 params->failed = true;
1467 return false;
1468 }
1469 ns = RunStateOnByteUnlocked(s, c);
1470 if (ns == NULL) {
1471 LOG(DFATAL) << "RunStateOnByteUnlocked failed after ResetCache";
1472 params->failed = true;
1473 return false;
1474 }
1475 }
1476 }
1477 if (ns <= SpecialStateMax) {
1478 if (ns == DeadState) {
1479 params->ep = reinterpret_cast<const char*>(lastmatch);
1480 return matched;
1481 }
1482 // FullMatchState
1483 params->ep = reinterpret_cast<const char*>(ep);
1484 return true;
1485 }
1486
1487 s = ns;
1488 if (s->IsMatch()) {
1489 matched = true;
1490 // The DFA notices the match one byte late,
1491 // so adjust p before using it in the match.
1492 if (run_forward)
1493 lastmatch = p - 1;
1494 else
1495 lastmatch = p + 1;
1496 if (ExtraDebug)
1497 fprintf(stderr, "match @%td! [%s]\n", lastmatch - bp, DumpState(s).c_str());
1498 if (params->matches != NULL && kind_ == Prog::kManyMatch) {
1499 for (int i = s->ninst_ - 1; i >= 0; i--) {
1500 int id = s->inst_[i];
1501 if (id == MatchSep)
1502 break;
1503 params->matches->insert(id);
1504 }
1505 }
1506 if (want_earliest_match) {
1507 params->ep = reinterpret_cast<const char*>(lastmatch);
1508 return true;
1509 }
1510 }
1511 }
1512
1513 // Process one more byte to see if it triggers a match.
1514 // (Remember, matches are delayed one byte.)
1515 if (ExtraDebug)
1516 fprintf(stderr, "@etx: %s\n", DumpState(s).c_str());
1517
1518 int lastbyte;
1519 if (run_forward) {
1520 if (params->text.end() == params->context.end())
1521 lastbyte = kByteEndText;
1522 else
1523 lastbyte = params->text.end()[0] & 0xFF;
1524 } else {
1525 if (params->text.begin() == params->context.begin())
1526 lastbyte = kByteEndText;
1527 else
1528 lastbyte = params->text.begin()[-1] & 0xFF;
1529 }
1530
1531 State* ns = s->next_[ByteMap(lastbyte)].load(std::memory_order_acquire);
1532 if (ns == NULL) {
1533 ns = RunStateOnByteUnlocked(s, lastbyte);
1534 if (ns == NULL) {
1535 StateSaver save_s(this, s);
1536 ResetCache(params->cache_lock);
1537 if ((s = save_s.Restore()) == NULL) {
1538 params->failed = true;
1539 return false;
1540 }
1541 ns = RunStateOnByteUnlocked(s, lastbyte);
1542 if (ns == NULL) {
1543 LOG(DFATAL) << "RunStateOnByteUnlocked failed after Reset";
1544 params->failed = true;
1545 return false;
1546 }
1547 }
1548 }
1549 if (ns <= SpecialStateMax) {
1550 if (ns == DeadState) {
1551 params->ep = reinterpret_cast<const char*>(lastmatch);
1552 return matched;
1553 }
1554 // FullMatchState
1555 params->ep = reinterpret_cast<const char*>(ep);
1556 return true;
1557 }
1558
1559 s = ns;
1560 if (s->IsMatch()) {
1561 matched = true;
1562 lastmatch = p;
1563 if (ExtraDebug)
1564 fprintf(stderr, "match @etx! [%s]\n", DumpState(s).c_str());
1565 if (params->matches != NULL && kind_ == Prog::kManyMatch) {
1566 for (int i = s->ninst_ - 1; i >= 0; i--) {
1567 int id = s->inst_[i];
1568 if (id == MatchSep)
1569 break;
1570 params->matches->insert(id);
1571 }
1572 }
1573 }
1574
1575 params->ep = reinterpret_cast<const char*>(lastmatch);
1576 return matched;
1577 }
1578
1579 // Inline specializations of the general loop.
SearchFFF(SearchParams * params)1580 bool DFA::SearchFFF(SearchParams* params) {
1581 return InlinedSearchLoop(params, 0, 0, 0);
1582 }
SearchFFT(SearchParams * params)1583 bool DFA::SearchFFT(SearchParams* params) {
1584 return InlinedSearchLoop(params, 0, 0, 1);
1585 }
SearchFTF(SearchParams * params)1586 bool DFA::SearchFTF(SearchParams* params) {
1587 return InlinedSearchLoop(params, 0, 1, 0);
1588 }
SearchFTT(SearchParams * params)1589 bool DFA::SearchFTT(SearchParams* params) {
1590 return InlinedSearchLoop(params, 0, 1, 1);
1591 }
SearchTFF(SearchParams * params)1592 bool DFA::SearchTFF(SearchParams* params) {
1593 return InlinedSearchLoop(params, 1, 0, 0);
1594 }
SearchTFT(SearchParams * params)1595 bool DFA::SearchTFT(SearchParams* params) {
1596 return InlinedSearchLoop(params, 1, 0, 1);
1597 }
SearchTTF(SearchParams * params)1598 bool DFA::SearchTTF(SearchParams* params) {
1599 return InlinedSearchLoop(params, 1, 1, 0);
1600 }
SearchTTT(SearchParams * params)1601 bool DFA::SearchTTT(SearchParams* params) {
1602 return InlinedSearchLoop(params, 1, 1, 1);
1603 }
1604
1605 // For debugging, calls the general code directly.
SlowSearchLoop(SearchParams * params)1606 bool DFA::SlowSearchLoop(SearchParams* params) {
1607 return InlinedSearchLoop(params,
1608 params->first_byte >= 0,
1609 params->want_earliest_match,
1610 params->run_forward);
1611 }
1612
1613 // For performance, calls the appropriate specialized version
1614 // of InlinedSearchLoop.
FastSearchLoop(SearchParams * params)1615 bool DFA::FastSearchLoop(SearchParams* params) {
1616 // Because the methods are private, the Searches array
1617 // cannot be declared at top level.
1618 static bool (DFA::*Searches[])(SearchParams*) = {
1619 &DFA::SearchFFF,
1620 &DFA::SearchFFT,
1621 &DFA::SearchFTF,
1622 &DFA::SearchFTT,
1623 &DFA::SearchTFF,
1624 &DFA::SearchTFT,
1625 &DFA::SearchTTF,
1626 &DFA::SearchTTT,
1627 };
1628
1629 bool have_first_byte = params->first_byte >= 0;
1630 int index = 4 * have_first_byte +
1631 2 * params->want_earliest_match +
1632 1 * params->run_forward;
1633 return (this->*Searches[index])(params);
1634 }
1635
1636
1637 // The discussion of DFA execution above ignored the question of how
1638 // to determine the initial state for the search loop. There are two
1639 // factors that influence the choice of start state.
1640 //
1641 // The first factor is whether the search is anchored or not.
1642 // The regexp program (Prog*) itself has
1643 // two different entry points: one for anchored searches and one for
1644 // unanchored searches. (The unanchored version starts with a leading ".*?"
1645 // and then jumps to the anchored one.)
1646 //
1647 // The second factor is where text appears in the larger context, which
1648 // determines which empty-string operators can be matched at the beginning
1649 // of execution. If text is at the very beginning of context, \A and ^ match.
1650 // Otherwise if text is at the beginning of a line, then ^ matches.
1651 // Otherwise it matters whether the character before text is a word character
1652 // or a non-word character.
1653 //
1654 // The two cases (unanchored vs not) and four cases (empty-string flags)
1655 // combine to make the eight cases recorded in the DFA's begin_text_[2],
1656 // begin_line_[2], after_wordchar_[2], and after_nonwordchar_[2] cached
1657 // StartInfos. The start state for each is filled in the first time it
1658 // is used for an actual search.
1659
1660 // Examines text, context, and anchored to determine the right start
1661 // state for the DFA search loop. Fills in params and returns true on success.
1662 // Returns false on failure.
AnalyzeSearch(SearchParams * params)1663 bool DFA::AnalyzeSearch(SearchParams* params) {
1664 const StringPiece& text = params->text;
1665 const StringPiece& context = params->context;
1666
1667 // Sanity check: make sure that text lies within context.
1668 if (text.begin() < context.begin() || text.end() > context.end()) {
1669 LOG(DFATAL) << "context does not contain text";
1670 params->start = DeadState;
1671 return true;
1672 }
1673
1674 // Determine correct search type.
1675 int start;
1676 uint32_t flags;
1677 if (params->run_forward) {
1678 if (text.begin() == context.begin()) {
1679 start = kStartBeginText;
1680 flags = kEmptyBeginText|kEmptyBeginLine;
1681 } else if (text.begin()[-1] == '\n') {
1682 start = kStartBeginLine;
1683 flags = kEmptyBeginLine;
1684 } else if (Prog::IsWordChar(text.begin()[-1] & 0xFF)) {
1685 start = kStartAfterWordChar;
1686 flags = kFlagLastWord;
1687 } else {
1688 start = kStartAfterNonWordChar;
1689 flags = 0;
1690 }
1691 } else {
1692 if (text.end() == context.end()) {
1693 start = kStartBeginText;
1694 flags = kEmptyBeginText|kEmptyBeginLine;
1695 } else if (text.end()[0] == '\n') {
1696 start = kStartBeginLine;
1697 flags = kEmptyBeginLine;
1698 } else if (Prog::IsWordChar(text.end()[0] & 0xFF)) {
1699 start = kStartAfterWordChar;
1700 flags = kFlagLastWord;
1701 } else {
1702 start = kStartAfterNonWordChar;
1703 flags = 0;
1704 }
1705 }
1706 if (params->anchored)
1707 start |= kStartAnchored;
1708 StartInfo* info = &start_[start];
1709
1710 // Try once without cache_lock for writing.
1711 // Try again after resetting the cache
1712 // (ResetCache will relock cache_lock for writing).
1713 if (!AnalyzeSearchHelper(params, info, flags)) {
1714 ResetCache(params->cache_lock);
1715 if (!AnalyzeSearchHelper(params, info, flags)) {
1716 LOG(DFATAL) << "Failed to analyze start state.";
1717 params->failed = true;
1718 return false;
1719 }
1720 }
1721
1722 if (ExtraDebug)
1723 fprintf(stderr, "anchored=%d fwd=%d flags=%#x state=%s first_byte=%d\n",
1724 params->anchored, params->run_forward, flags,
1725 DumpState(info->start).c_str(), info->first_byte.load());
1726
1727 params->start = info->start;
1728 params->first_byte = info->first_byte.load(std::memory_order_acquire);
1729
1730 return true;
1731 }
1732
1733 // Fills in info if needed. Returns true on success, false on failure.
AnalyzeSearchHelper(SearchParams * params,StartInfo * info,uint32_t flags)1734 bool DFA::AnalyzeSearchHelper(SearchParams* params, StartInfo* info,
1735 uint32_t flags) {
1736 // Quick check.
1737 int fb = info->first_byte.load(std::memory_order_acquire);
1738 if (fb != kFbUnknown)
1739 return true;
1740
1741 MutexLock l(&mutex_);
1742 fb = info->first_byte.load(std::memory_order_relaxed);
1743 if (fb != kFbUnknown)
1744 return true;
1745
1746 q0_->clear();
1747 AddToQueue(q0_,
1748 params->anchored ? prog_->start() : prog_->start_unanchored(),
1749 flags);
1750 info->start = WorkqToCachedState(q0_, NULL, flags);
1751 if (info->start == NULL)
1752 return false;
1753
1754 if (info->start == DeadState) {
1755 // Synchronize with "quick check" above.
1756 info->first_byte.store(kFbNone, std::memory_order_release);
1757 return true;
1758 }
1759
1760 if (info->start == FullMatchState) {
1761 // Synchronize with "quick check" above.
1762 info->first_byte.store(kFbNone, std::memory_order_release); // will be ignored
1763 return true;
1764 }
1765
1766 // Even if we have a first_byte, we cannot use it when anchored and,
1767 // less obviously, we cannot use it when we are going to need flags.
1768 // This trick works only when there is a single byte that leads to a
1769 // different state!
1770 int first_byte = prog_->first_byte();
1771 if (first_byte == -1 ||
1772 params->anchored ||
1773 info->start->flag_ >> kFlagNeedShift != 0)
1774 first_byte = kFbNone;
1775
1776 // Synchronize with "quick check" above.
1777 info->first_byte.store(first_byte, std::memory_order_release);
1778 return true;
1779 }
1780
1781 // The actual DFA search: calls AnalyzeSearch and then FastSearchLoop.
Search(const StringPiece & text,const StringPiece & context,bool anchored,bool want_earliest_match,bool run_forward,bool * failed,const char ** epp,SparseSet * matches)1782 bool DFA::Search(const StringPiece& text,
1783 const StringPiece& context,
1784 bool anchored,
1785 bool want_earliest_match,
1786 bool run_forward,
1787 bool* failed,
1788 const char** epp,
1789 SparseSet* matches) {
1790 *epp = NULL;
1791 if (!ok()) {
1792 *failed = true;
1793 return false;
1794 }
1795 *failed = false;
1796
1797 if (ExtraDebug) {
1798 fprintf(stderr, "\nprogram:\n%s\n", prog_->DumpUnanchored().c_str());
1799 fprintf(stderr, "text %s anchored=%d earliest=%d fwd=%d kind %d\n",
1800 std::string(text).c_str(), anchored, want_earliest_match, run_forward, kind_);
1801 }
1802
1803 RWLocker l(&cache_mutex_);
1804 SearchParams params(text, context, &l);
1805 params.anchored = anchored;
1806 params.want_earliest_match = want_earliest_match;
1807 params.run_forward = run_forward;
1808 params.matches = matches;
1809
1810 if (!AnalyzeSearch(¶ms)) {
1811 *failed = true;
1812 return false;
1813 }
1814 if (params.start == DeadState)
1815 return false;
1816 if (params.start == FullMatchState) {
1817 if (run_forward == want_earliest_match)
1818 *epp = text.data();
1819 else
1820 *epp = text.data() + text.size();
1821 return true;
1822 }
1823 if (ExtraDebug)
1824 fprintf(stderr, "start %s\n", DumpState(params.start).c_str());
1825 bool ret = FastSearchLoop(¶ms);
1826 if (params.failed) {
1827 *failed = true;
1828 return false;
1829 }
1830 *epp = params.ep;
1831 return ret;
1832 }
1833
GetDFA(MatchKind kind)1834 DFA* Prog::GetDFA(MatchKind kind) {
1835 // For a forward DFA, half the memory goes to each DFA.
1836 // However, if it is a "many match" DFA, then there is
1837 // no counterpart with which the memory must be shared.
1838 //
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 if (kind == kFirstMatch) {
1843 std::call_once(dfa_first_once_, [](Prog* prog) {
1844 prog->dfa_first_ = new DFA(prog, kFirstMatch, prog->dfa_mem_ / 2);
1845 }, this);
1846 return dfa_first_;
1847 } else if (kind == kManyMatch) {
1848 std::call_once(dfa_first_once_, [](Prog* prog) {
1849 prog->dfa_first_ = new DFA(prog, kManyMatch, prog->dfa_mem_);
1850 }, this);
1851 return dfa_first_;
1852 } else {
1853 std::call_once(dfa_longest_once_, [](Prog* prog) {
1854 if (!prog->reversed_)
1855 prog->dfa_longest_ = new DFA(prog, kLongestMatch, prog->dfa_mem_ / 2);
1856 else
1857 prog->dfa_longest_ = new DFA(prog, kLongestMatch, prog->dfa_mem_);
1858 }, this);
1859 return dfa_longest_;
1860 }
1861 }
1862
DeleteDFA(DFA * dfa)1863 void Prog::DeleteDFA(DFA* dfa) {
1864 delete dfa;
1865 }
1866
1867 // Executes the regexp program to search in text,
1868 // which itself is inside the larger context. (As a convenience,
1869 // passing a NULL context is equivalent to passing text.)
1870 // Returns true if a match is found, false if not.
1871 // If a match is found, fills in match0->end() to point at the end of the match
1872 // and sets match0->begin() to text.begin(), since the DFA can't track
1873 // where the match actually began.
1874 //
1875 // This is the only external interface (class DFA only exists in this file).
1876 //
SearchDFA(const StringPiece & text,const StringPiece & const_context,Anchor anchor,MatchKind kind,StringPiece * match0,bool * failed,SparseSet * matches)1877 bool Prog::SearchDFA(const StringPiece& text, const StringPiece& const_context,
1878 Anchor anchor, MatchKind kind, StringPiece* match0,
1879 bool* failed, SparseSet* matches) {
1880 *failed = false;
1881
1882 StringPiece context = const_context;
1883 if (context.data() == NULL)
1884 context = text;
1885 bool carat = anchor_start();
1886 bool dollar = anchor_end();
1887 if (reversed_) {
1888 using std::swap;
1889 swap(carat, dollar);
1890 }
1891 if (carat && context.begin() != text.begin())
1892 return false;
1893 if (dollar && context.end() != text.end())
1894 return false;
1895
1896 // Handle full match by running an anchored longest match
1897 // and then checking if it covers all of text.
1898 bool anchored = anchor == kAnchored || anchor_start() || kind == kFullMatch;
1899 bool endmatch = false;
1900 if (kind == kManyMatch) {
1901 // This is split out in order to avoid clobbering kind.
1902 } else if (kind == kFullMatch || anchor_end()) {
1903 endmatch = true;
1904 kind = kLongestMatch;
1905 }
1906
1907 // If the caller doesn't care where the match is (just whether one exists),
1908 // then we can stop at the very first match we find, the so-called
1909 // "earliest match".
1910 bool want_earliest_match = false;
1911 if (kind == kManyMatch) {
1912 // This is split out in order to avoid clobbering kind.
1913 if (matches == NULL) {
1914 want_earliest_match = true;
1915 }
1916 } else if (match0 == NULL && !endmatch) {
1917 want_earliest_match = true;
1918 kind = kLongestMatch;
1919 }
1920
1921 DFA* dfa = GetDFA(kind);
1922 const char* ep;
1923 bool matched = dfa->Search(text, context, anchored,
1924 want_earliest_match, !reversed_,
1925 failed, &ep, matches);
1926 if (*failed) {
1927 hooks::GetDFASearchFailureHook()({
1928 // Nothing yet...
1929 });
1930 return false;
1931 }
1932 if (!matched)
1933 return false;
1934 if (endmatch && ep != (reversed_ ? text.data() : text.data() + text.size()))
1935 return false;
1936
1937 // If caller cares, record the boundary of the match.
1938 // We only know where it ends, so use the boundary of text
1939 // as the beginning.
1940 if (match0) {
1941 if (reversed_)
1942 *match0 =
1943 StringPiece(ep, static_cast<size_t>(text.data() + text.size() - ep));
1944 else
1945 *match0 =
1946 StringPiece(text.data(), static_cast<size_t>(ep - text.data()));
1947 }
1948 return true;
1949 }
1950
1951 // Build out all states in DFA. Returns number of states.
BuildAllStates(const Prog::DFAStateCallback & cb)1952 int DFA::BuildAllStates(const Prog::DFAStateCallback& cb) {
1953 if (!ok())
1954 return 0;
1955
1956 // Pick out start state for unanchored search
1957 // at beginning of text.
1958 RWLocker l(&cache_mutex_);
1959 SearchParams params(StringPiece(), StringPiece(), &l);
1960 params.anchored = false;
1961 if (!AnalyzeSearch(¶ms) ||
1962 params.start == NULL ||
1963 params.start == DeadState)
1964 return 0;
1965
1966 // Add start state to work queue.
1967 // Note that any State* that we handle here must point into the cache,
1968 // so we can simply depend on pointer-as-a-number hashing and equality.
1969 std::unordered_map<State*, int> m;
1970 std::deque<State*> q;
1971 m.emplace(params.start, static_cast<int>(m.size()));
1972 q.push_back(params.start);
1973
1974 // Compute the input bytes needed to cover all of the next pointers.
1975 int nnext = prog_->bytemap_range() + 1; // + 1 for kByteEndText slot
1976 std::vector<int> input(nnext);
1977 for (int c = 0; c < 256; c++) {
1978 int b = prog_->bytemap()[c];
1979 while (c < 256-1 && prog_->bytemap()[c+1] == b)
1980 c++;
1981 input[b] = c;
1982 }
1983 input[prog_->bytemap_range()] = kByteEndText;
1984
1985 // Scratch space for the output.
1986 std::vector<int> output(nnext);
1987
1988 // Flood to expand every state.
1989 bool oom = false;
1990 while (!q.empty()) {
1991 State* s = q.front();
1992 q.pop_front();
1993 for (int c : input) {
1994 State* ns = RunStateOnByteUnlocked(s, c);
1995 if (ns == NULL) {
1996 oom = true;
1997 break;
1998 }
1999 if (ns == DeadState) {
2000 output[ByteMap(c)] = -1;
2001 continue;
2002 }
2003 if (m.find(ns) == m.end()) {
2004 m.emplace(ns, static_cast<int>(m.size()));
2005 q.push_back(ns);
2006 }
2007 output[ByteMap(c)] = m[ns];
2008 }
2009 if (cb)
2010 cb(oom ? NULL : output.data(),
2011 s == FullMatchState || s->IsMatch());
2012 if (oom)
2013 break;
2014 }
2015
2016 return static_cast<int>(m.size());
2017 }
2018
2019 // Build out all states in DFA for kind. Returns number of states.
BuildEntireDFA(MatchKind kind,const DFAStateCallback & cb)2020 int Prog::BuildEntireDFA(MatchKind kind, const DFAStateCallback& cb) {
2021 return GetDFA(kind)->BuildAllStates(cb);
2022 }
2023
TEST_dfa_should_bail_when_slow(bool b)2024 void Prog::TEST_dfa_should_bail_when_slow(bool b) {
2025 dfa_should_bail_when_slow = b;
2026 }
2027
2028 // Computes min and max for matching string.
2029 // Won't return strings bigger than maxlen.
PossibleMatchRange(std::string * min,std::string * max,int maxlen)2030 bool DFA::PossibleMatchRange(std::string* min, std::string* max, int maxlen) {
2031 if (!ok())
2032 return false;
2033
2034 // NOTE: if future users of PossibleMatchRange want more precision when
2035 // presented with infinitely repeated elements, consider making this a
2036 // parameter to PossibleMatchRange.
2037 static int kMaxEltRepetitions = 0;
2038
2039 // Keep track of the number of times we've visited states previously. We only
2040 // revisit a given state if it's part of a repeated group, so if the value
2041 // portion of the map tuple exceeds kMaxEltRepetitions we bail out and set
2042 // |*max| to |PrefixSuccessor(*max)|.
2043 //
2044 // Also note that previously_visited_states[UnseenStatePtr] will, in the STL
2045 // tradition, implicitly insert a '0' value at first use. We take advantage
2046 // of that property below.
2047 std::unordered_map<State*, int> previously_visited_states;
2048
2049 // Pick out start state for anchored search at beginning of text.
2050 RWLocker l(&cache_mutex_);
2051 SearchParams params(StringPiece(), StringPiece(), &l);
2052 params.anchored = true;
2053 if (!AnalyzeSearch(¶ms))
2054 return false;
2055 if (params.start == DeadState) { // No matching strings
2056 *min = "";
2057 *max = "";
2058 return true;
2059 }
2060 if (params.start == FullMatchState) // Every string matches: no max
2061 return false;
2062
2063 // The DFA is essentially a big graph rooted at params.start,
2064 // and paths in the graph correspond to accepted strings.
2065 // Each node in the graph has potentially 256+1 arrows
2066 // coming out, one for each byte plus the magic end of
2067 // text character kByteEndText.
2068
2069 // To find the smallest possible prefix of an accepted
2070 // string, we just walk the graph preferring to follow
2071 // arrows with the lowest bytes possible. To find the
2072 // largest possible prefix, we follow the largest bytes
2073 // possible.
2074
2075 // The test for whether there is an arrow from s on byte j is
2076 // ns = RunStateOnByteUnlocked(s, j);
2077 // if (ns == NULL)
2078 // return false;
2079 // if (ns != DeadState && ns->ninst > 0)
2080 // The RunStateOnByteUnlocked call asks the DFA to build out the graph.
2081 // It returns NULL only if the DFA has run out of memory,
2082 // in which case we can't be sure of anything.
2083 // The second check sees whether there was graph built
2084 // and whether it is interesting graph. Nodes might have
2085 // ns->ninst == 0 if they exist only to represent the fact
2086 // that a match was found on the previous byte.
2087
2088 // Build minimum prefix.
2089 State* s = params.start;
2090 min->clear();
2091 MutexLock lock(&mutex_);
2092 for (int i = 0; i < maxlen; i++) {
2093 if (previously_visited_states[s] > kMaxEltRepetitions)
2094 break;
2095 previously_visited_states[s]++;
2096
2097 // Stop if min is a match.
2098 State* ns = RunStateOnByte(s, kByteEndText);
2099 if (ns == NULL) // DFA out of memory
2100 return false;
2101 if (ns != DeadState && (ns == FullMatchState || ns->IsMatch()))
2102 break;
2103
2104 // Try to extend the string with low bytes.
2105 bool extended = false;
2106 for (int j = 0; j < 256; j++) {
2107 ns = RunStateOnByte(s, j);
2108 if (ns == NULL) // DFA out of memory
2109 return false;
2110 if (ns == FullMatchState ||
2111 (ns > SpecialStateMax && ns->ninst_ > 0)) {
2112 extended = true;
2113 min->append(1, static_cast<char>(j));
2114 s = ns;
2115 break;
2116 }
2117 }
2118 if (!extended)
2119 break;
2120 }
2121
2122 // Build maximum prefix.
2123 previously_visited_states.clear();
2124 s = params.start;
2125 max->clear();
2126 for (int i = 0; i < maxlen; i++) {
2127 if (previously_visited_states[s] > kMaxEltRepetitions)
2128 break;
2129 previously_visited_states[s] += 1;
2130
2131 // Try to extend the string with high bytes.
2132 bool extended = false;
2133 for (int j = 255; j >= 0; j--) {
2134 State* ns = RunStateOnByte(s, j);
2135 if (ns == NULL)
2136 return false;
2137 if (ns == FullMatchState ||
2138 (ns > SpecialStateMax && ns->ninst_ > 0)) {
2139 extended = true;
2140 max->append(1, static_cast<char>(j));
2141 s = ns;
2142 break;
2143 }
2144 }
2145 if (!extended) {
2146 // Done, no need for PrefixSuccessor.
2147 return true;
2148 }
2149 }
2150
2151 // Stopped while still adding to *max - round aaaaaaaaaa... to aaaa...b
2152 PrefixSuccessor(max);
2153
2154 // If there are no bytes left, we have no way to say "there is no maximum
2155 // string". We could make the interface more complicated and be able to
2156 // return "there is no maximum but here is a minimum", but that seems like
2157 // overkill -- the most common no-max case is all possible strings, so not
2158 // telling the caller that the empty string is the minimum match isn't a
2159 // great loss.
2160 if (max->empty())
2161 return false;
2162
2163 return true;
2164 }
2165
2166 // PossibleMatchRange for a Prog.
PossibleMatchRange(std::string * min,std::string * max,int maxlen)2167 bool Prog::PossibleMatchRange(std::string* min, std::string* max, int maxlen) {
2168 // Have to use dfa_longest_ to get all strings for full matches.
2169 // For example, (a|aa) never matches aa in first-match mode.
2170 return GetDFA(kLongestMatch)->PossibleMatchRange(min, max, maxlen);
2171 }
2172
2173 } // namespace re2
2174