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 // Tested by search_test.cc, exhaustive_test.cc, tester.cc
7 // Prog::SearchBitState is a regular expression search with submatch
8 // tracking for small regular expressions and texts. Like
9 // testing/backtrack.cc, it allocates a bit vector with (length of
10 // text) * (length of prog) bits, to make sure it never explores the
11 // same (character position, instruction) state multiple times. This
12 // limits the search to run in time linear in the length of the text.
14 // Unlike testing/backtrack.cc, SearchBitState is not recursive
17 // SearchBitState is a fast replacement for the NFA code on small
18 // regexps and texts when SearchOnePass cannot be used.
21 #include "re2/regexp.h"
33 explicit BitState(Prog* prog);
36 // The usual Search prototype.
37 // Can only call Search once per BitState.
38 bool Search(const StringPiece& text, const StringPiece& context,
39 bool anchored, bool longest,
40 StringPiece* submatch, int nsubmatch);
43 inline bool ShouldVisit(int id, const char* p);
44 void Push(int id, const char* p, int arg);
46 bool TrySearch(int id, const char* p);
49 Prog* prog_; // program being run
50 StringPiece text_; // text being searched
51 StringPiece context_; // greater context of text being searched
52 bool anchored_; // whether search is anchored at text.begin()
53 bool longest_; // whether search wants leftmost-longest match
54 bool endmatch_; // whether match must end at text.end()
55 StringPiece *submatch_; // submatches to fill in
56 int nsubmatch_; // # of submatches to fill in
59 const char** cap_; // capture registers
62 static const int VisitedBits = 32;
63 uint32 *visited_; // bitmap: (Inst*, char*) pairs already backtracked
64 int nvisited_; // # of words in bitmap
66 Job *job_; // stack of text positions to explore
71 BitState::BitState(Prog* prog)
87 BitState::~BitState() {
93 // Should the search visit the pair ip, p?
94 // If so, remember that it was visited so that the next time,
95 // we don't repeat the visit.
96 bool BitState::ShouldVisit(int id, const char* p) {
97 uint n = id * (text_.size() + 1) + (p - text_.begin());
98 if (visited_[n/VisitedBits] & (1 << (n & (VisitedBits-1))))
100 visited_[n/VisitedBits] |= 1 << (n & (VisitedBits-1));
105 bool BitState::GrowStack() {
106 // VLOG(0) << "Reallocate.";
108 Job* newjob = new Job[maxjob_];
109 memmove(newjob, job_, njob_*sizeof job_[0]);
112 if (njob_ >= maxjob_) {
113 LOG(DFATAL) << "Job stack overflow.";
119 // Push the triple (id, p, arg) onto the stack, growing it if necessary.
120 void BitState::Push(int id, const char* p, int arg) {
121 if (njob_ >= maxjob_) {
125 int op = prog_->inst(id)->opcode();
129 // Only check ShouldVisit when arg == 0.
130 // When arg > 0, we are continuing a previous visit.
131 if (arg == 0 && !ShouldVisit(id, p))
134 Job* j = &job_[njob_++];
140 // Try a search from instruction id0 in state p0.
141 // Return whether it succeeded.
142 bool BitState::TrySearch(int id0, const char* p0) {
143 bool matched = false;
144 const char* end = text_.end();
148 // Pop job off stack.
150 int id = job_[njob_].id;
151 const char* p = job_[njob_].p;
152 int arg = job_[njob_].arg;
154 // Optimization: rather than push and pop,
155 // code that is going to Push and continue
156 // the loop simply updates ip, p, and arg
157 // and jumps to CheckAndLoop. We have to
158 // do the ShouldVisit check that Push
159 // would have, but we avoid the stack
163 if (!ShouldVisit(id, p))
168 // VLOG(0) << "Job: " << ip->id() << " "
169 // << (p - text_.begin()) << " " << arg;
170 Prog::Inst* ip = prog_->inst(id);
171 switch (ip->opcode()) {
174 LOG(DFATAL) << "Unexpected opcode: " << ip->opcode() << " arg " << arg;
179 // Push(ip->out1(), p, 0);
180 // Push(ip->out(), p, 0);
181 // If, during the processing of ip->out(), we encounter
182 // ip->out1() via another path, we want to process it then.
183 // Pushing it here will inhibit that. Instead, re-push
184 // ip with arg==1 as a reminder to push ip->out1() later.
187 Push(id, p, 1); // come back when we're done
192 // Finished ip->out(); try ip->out1().
197 LOG(DFATAL) << "Bad arg in kInstCapture: " << arg;
201 // One opcode is byte range; the other leads to match.
202 if (ip->greedy(prog_)) {
204 Push(ip->out1(), p, 0);
209 // out is the match - non-greedy
210 Push(ip->out(), end, 0);
214 case kInstByteRange: {
218 if (ip->Matches(c)) {
229 if (0 <= ip->cap() && ip->cap() < ncap_) {
230 // Capture p to register, but save old value.
231 Push(id, cap_[ip->cap()], 1); // come back when we're done
238 // Finished ip->out(); restore the old value.
242 LOG(DFATAL) << "Bad arg in kInstCapture: " << arg;
245 case kInstEmptyWidth:
246 if (ip->empty() & ~Prog::EmptyFlags(context_, p))
256 if (endmatch_ && p != text_.end())
259 // VLOG(0) << "Found match.";
260 // We found a match. If the caller doesn't care
261 // where the match is, no point going further.
265 // Record best match so far.
266 // Only need to check end point, because this entire
267 // call is only considering one start position.
270 if (submatch_[0].data() == NULL ||
271 (longest_ && p > submatch_[0].end())) {
272 for (int i = 0; i < nsubmatch_; i++)
273 submatch_[i] = StringPiece(cap_[2*i], cap_[2*i+1] - cap_[2*i]);
276 // If going for first match, we're done.
280 // If we used the entire text, no longer match is possible.
281 if (p == text_.end())
284 // Otherwise, continue on in hope of a longer match.
292 // Search text (within context) for prog_.
293 bool BitState::Search(const StringPiece& text, const StringPiece& context,
294 bool anchored, bool longest,
295 StringPiece* submatch, int nsubmatch) {
296 // Search parameters.
299 if (context_.begin() == NULL)
301 if (prog_->anchor_start() && context_.begin() != text.begin())
303 if (prog_->anchor_end() && context_.end() != text.end())
305 anchored_ = anchored || prog_->anchor_start();
306 longest_ = longest || prog_->anchor_end();
307 endmatch_ = prog_->anchor_end();
308 submatch_ = submatch;
309 nsubmatch_ = nsubmatch;
310 for (int i = 0; i < nsubmatch_; i++)
313 // Allocate scratch space.
314 nvisited_ = (prog_->size() * (text.size()+1) + VisitedBits-1) / VisitedBits;
315 visited_ = new uint32[nvisited_];
316 memset(visited_, 0, nvisited_*sizeof visited_[0]);
317 // VLOG(0) << "nvisited_ = " << nvisited_;
322 cap_ = new const char*[ncap_];
323 memset(cap_, 0, ncap_*sizeof cap_[0]);
326 job_ = new Job[maxjob_];
328 // Anchored search must start at text.begin().
330 cap_[0] = text.begin();
331 return TrySearch(prog_->start(), text.begin());
334 // Unanchored search, starting from each possible text position.
335 // Notice that we have to try the empty string at the end of
336 // the text, so the loop condition is p <= text.end(), not p < text.end().
337 // This looks like it's quadratic in the size of the text,
338 // but we are not clearing visited_ between calls to TrySearch,
339 // so no work is duplicated and it ends up still being linear.
340 for (const char* p = text.begin(); p <= text.end(); p++) {
342 if (TrySearch(prog_->start(), p)) // Match must be leftmost; done.
349 bool Prog::SearchBitState(const StringPiece& text,
350 const StringPiece& context,
355 // If full match, we ask for an anchored longest match
356 // and then check that match[0] == text.
357 // So make sure match[0] exists.
359 if (kind == kFullMatch) {
369 bool anchored = anchor == kAnchored;
370 bool longest = kind != kFirstMatch;
371 if (!b.Search(text, context, anchored, longest, match, nmatch))
373 if (kind == kFullMatch && match[0].end() != text.end())