// Copyright 2008 The RE2 Authors. All Rights Reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Tested by search_test.cc, exhaustive_test.cc, tester.cc
// Prog::SearchBitState is a regular expression search with submatch
// tracking for small regular expressions and texts. Similarly to
// testing/backtrack.cc, it allocates a bitmap with (count of
// lists) * (length of text) bits to make sure it never explores the
// same (instruction list, character position) multiple times. This
// limits the search to run in time linear in the length of the text.
//
// Unlike testing/backtrack.cc, SearchBitState is not recursive
// on the text.
//
// SearchBitState is a fast replacement for the NFA code on small
// regexps and texts when SearchOnePass cannot be used.
#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include <limits>
#include <utility>
#include "util/logging.h"
#include "re2/pod_array.h"
#include "re2/prog.h"
#include "re2/regexp.h"
namespace re2 {
struct Job {
int id;
int rle; // run length encoding
const char* p;
};
class BitState {
public:
explicit BitState(Prog* prog);
// The usual Search prototype.
// Can only call Search once per BitState.
bool Search(const StringPiece& text, const StringPiece& context,
bool anchored, bool longest,
StringPiece* submatch, int nsubmatch);
private:
inline bool ShouldVisit(int id, const char* p);
void Push(int id, const char* p);
void GrowStack();
bool TrySearch(int id, const char* p);
// Search parameters
Prog* prog_; // program being run
StringPiece text_; // text being searched
StringPiece context_; // greater context of text being searched
bool anchored_; // whether search is anchored at text.begin()
bool longest_; // whether search wants leftmost-longest match
bool endmatch_; // whether match must end at text.end()
StringPiece* submatch_; // submatches to fill in
int nsubmatch_; // # of submatches to fill in
// Search state
static constexpr int kVisitedBits = 64;
PODArray<uint64_t> visited_; // bitmap: (list ID, char*) pairs visited
PODArray<const char*> cap_; // capture registers
PODArray<Job> job_; // stack of text positions to explore
int njob_; // stack size
BitState(const BitState&) = delete;
BitState& operator=(const BitState&) = delete;
};
BitState::BitState(Prog* prog)
: prog_(prog),
anchored_(false),
longest_(false),
endmatch_(false),
submatch_(NULL),
nsubmatch_(0),
njob_(0) {
}
// Given id, which *must* be a list head, we can look up its list ID.
// Then the question is: Should the search visit the (list ID, p) pair?
// If so, remember that it was visited so that the next time,
// we don't repeat the visit.
bool BitState::ShouldVisit(int id, const char* p) {
int n = prog_->list_heads()[id] * static_cast<int>(text_.size()+1) +
static_cast<int>(p-text_.data());
if (visited_[n/kVisitedBits] & (uint64_t{1} << (n & (kVisitedBits-1))))
return false;
visited_[n/kVisitedBits] |= uint64_t{1} << (n & (kVisitedBits-1));
return true;
}
// Grow the stack.
void BitState::GrowStack() {
PODArray<Job> tmp(2*job_.size());
memmove(tmp.data(), job_.data(), njob_*sizeof job_[0]);
job_ = std::move(tmp);
}
// Push (id, p) onto the stack, growing it if necessary.
void BitState::Push(int id, const char* p) {
if (njob_ >= job_.size()) {
GrowStack();
if (njob_ >= job_.size()) {
LOG(DFATAL) << "GrowStack() failed: "
<< "njob_ = " << njob_ << ", "
<< "job_.size() = " << job_.size();
return;
}
}
// If id < 0, it's undoing a Capture,
// so we mustn't interfere with that.
if (id >= 0 && njob_ > 0) {
Job* top = &job_[njob_-1];
if (id == top->id &&
p == top->p + top->rle + 1 &&
top->rle < std::numeric_limits<int>::max()) {
++top->rle;
return;
}
}
Job* top = &job_[njob_++];
top->id = id;
top->rle = 0;
top->p = p;
}
// Try a search from instruction id0 in state p0.
// Return whether it succeeded.
bool BitState::TrySearch(int id0, const char* p0) {
bool matched = false;
const char* end = text_.data() + text_.size();
njob_ = 0;
// Push() no longer checks ShouldVisit(),
// so we must perform the check ourselves.
if (ShouldVisit(id0, p0))
Push(id0, p0);
while (njob_ > 0) {
// Pop job off stack.
--njob_;
int id = job_[njob_].id;
int& rle = job_[njob_].rle;
const char* p = job_[njob_].p;
if (id < 0) {
// Undo the Capture.
cap_[prog_->inst(-id)->cap()] = p;
continue;
}
if (rle > 0) {
p += rle;
// Revivify job on stack.
--rle;
++njob_;
}
Loop:
// Visit id, p.
Prog::Inst* ip = prog_->inst(id);
switch (ip->opcode()) {
default:
LOG(DFATAL) << "Unexpected opcode: " << ip->opcode();
return false;
case kInstFail:
break;
case kInstAltMatch:
if (ip->greedy(prog_)) {
// out1 is the Match instruction.
id = ip->out1();
p = end;
goto Loop;
}
if (longest_) {
// ip must be non-greedy...
// out is the Match instruction.
id = ip->out();
p = end;
goto Loop;
}
goto Next;
case kInstByteRange: {
int c = -1;
if (p < end)
c = *p & 0xFF;
if (!ip->Matches(c))
goto Next;
if (ip->hint() != 0)
Push(id+ip->hint(), p); // try the next when we're done
id = ip->out();
p++;
goto CheckAndLoop;
}
case kInstCapture:
if (!ip->last())
Push(id+1, p); // try the next when we're done
if (0 <= ip->cap() && ip->cap() < cap_.size()) {
// Capture p to register, but save old value first.
Push(-id, cap_[ip->cap()]); // undo when we're done
cap_[ip->cap()] = p;
}
id = ip->out();
goto CheckAndLoop;
case kInstEmptyWidth:
if (ip->empty() & ~Prog::EmptyFlags(context_, p))
goto Next;
if (!ip->last())
Push(id+1, p); // try the next when we're done
id = ip->out();
goto CheckAndLoop;
case kInstNop:
if (!ip->last())
Push(id+1, p); // try the next when we're done
id = ip->out();
CheckAndLoop:
// Sanity check: id is the head of its list, which must
// be the case if id-1 is the last of *its* list. :)
DCHECK(id == 0 || prog_->inst(id-1)->last());
if (ShouldVisit(id, p))
goto Loop;
break;
case kInstMatch: {
if (endmatch_ && p != end)
goto Next;
// We found a match. If the caller doesn't care
// where the match is, no point going further.
if (nsubmatch_ == 0)
return true;
// Record best match so far.
// Only need to check end point, because this entire
// call is only considering one start position.
matched = true;
cap_[1] = p;
if (submatch_[0].data() == NULL ||
(longest_ && p > submatch_[0].data() + submatch_[0].size())) {
for (int i = 0; i < nsubmatch_; i++)
submatch_[i] =
StringPiece(cap_[2 * i],
static_cast<size_t>(cap_[2 * i + 1] - cap_[2 * i]));
}
// If going for first match, we're done.
if (!longest_)
return true;
// If we used the entire text, no longer match is possible.
if (p == end)
return true;
// Otherwise, continue on in hope of a longer match.
// Note the absence of the ShouldVisit() check here
// due to execution remaining in the same list.
Next:
if (!ip->last()) {
id++;
goto Loop;
}
break;
}
}
}
return matched;
}
// Search text (within context) for prog_.
bool BitState::Search(const StringPiece& text, const StringPiece& context,
bool anchored, bool longest,
StringPiece* submatch, int nsubmatch) {
// Search parameters.
text_ = text;
context_ = context;
if (context_.data() == NULL)
context_ = text;
if (prog_->anchor_start() && BeginPtr(context_) != BeginPtr(text))
return false;
if (prog_->anchor_end() && EndPtr(context_) != EndPtr(text))
return false;
anchored_ = anchored || prog_->anchor_start();
longest_ = longest || prog_->anchor_end();
endmatch_ = prog_->anchor_end();
submatch_ = submatch;
nsubmatch_ = nsubmatch;
for (int i = 0; i < nsubmatch_; i++)
submatch_[i] = StringPiece();
// Allocate scratch space.
int nvisited = prog_->list_count() * static_cast<int>(text.size()+1);
nvisited = (nvisited + kVisitedBits-1) / kVisitedBits;
visited_ = PODArray<uint64_t>(nvisited);
memset(visited_.data(), 0, nvisited*sizeof visited_[0]);
int ncap = 2*nsubmatch;
if (ncap < 2)
ncap = 2;
cap_ = PODArray<const char*>(ncap);
memset(cap_.data(), 0, ncap*sizeof cap_[0]);
// When sizeof(Job) == 16, we start with a nice round 1KiB. :)
job_ = PODArray<Job>(64);
// Anchored search must start at text.begin().
if (anchored_) {
cap_[0] = text.data();
return TrySearch(prog_->start(), text.data());
}
// Unanchored search, starting from each possible text position.
// Notice that we have to try the empty string at the end of
// the text, so the loop condition is p <= text.end(), not p < text.end().
// This looks like it's quadratic in the size of the text,
// but we are not clearing visited_ between calls to TrySearch,
// so no work is duplicated and it ends up still being linear.
const char* etext = text.data() + text.size();
for (const char* p = text.data(); p <= etext; p++) {
// Try to use prefix accel (e.g. memchr) to skip ahead.
if (p < etext && prog_->can_prefix_accel()) {
p = reinterpret_cast<const char*>(prog_->PrefixAccel(p, etext - p));
if (p == NULL)
p = etext;
}
cap_[0] = p;
if (TrySearch(prog_->start(), p)) // Match must be leftmost; done.
return true;
// Avoid invoking undefined behavior (arithmetic on a null pointer)
// by simply not continuing the loop.
if (p == NULL)
break;
}
return false;
}
// Bit-state search.
bool Prog::SearchBitState(const StringPiece& text,
const StringPiece& context,
Anchor anchor,
MatchKind kind,
StringPiece* match,
int nmatch) {
// If full match, we ask for an anchored longest match
// and then check that match[0] == text.
// So make sure match[0] exists.
StringPiece sp0;
if (kind == kFullMatch) {
anchor = kAnchored;
if (nmatch < 1) {
match = &sp0;
nmatch = 1;
}
}
// Run the search.
BitState b(this);
bool anchored = anchor == kAnchored;
bool longest = kind != kFirstMatch;
if (!b.Search(text, context, anchored, longest, match, nmatch))
return false;
if (kind == kFullMatch && EndPtr(match[0]) != EndPtr(text))
return false;
return true;
}
} // namespace re2