Apply stack churn/size tweaks to Prog::IsOnePass().
Change-Id: I46f449bb6564888aa1eb386bbb9171354c038d06
Reviewed-on: https://code-review.googlesource.com/4841
Reviewed-by: Paul Wankadia <junyer@google.com>
diff --git a/re2/onepass.cc b/re2/onepass.cc
index 7b83a79..1d745d4 100644
--- a/re2/onepass.cc
+++ b/re2/onepass.cc
@@ -392,9 +392,12 @@
// Flood the graph starting at the start state, and check
// that in each reachable state, each possible byte leads
// to a unique next state.
- int size = this->size();
- InstCond *stack = new InstCond[size];
+ int stacksize = inst_count(kInstCapture) +
+ inst_count(kInstEmptyWidth) +
+ inst_count(kInstNop) + 1; // + 1 for start inst
+ InstCond* stack = new InstCond[stacksize];
+ int size = this->size();
int* nodebyid = new int[size]; // indexed by ip
memset(nodebyid, 0xFF, size*sizeof nodebyid[0]);
@@ -424,8 +427,10 @@
stack[nstack++].cond = 0;
while (nstack > 0) {
int id = stack[--nstack].id;
- Prog::Inst* ip = inst(id);
uint32 cond = stack[nstack].cond;
+
+ Loop:
+ Prog::Inst* ip = inst(id);
switch (ip->opcode()) {
default:
LOG(DFATAL) << "unhandled opcode: " << ip->opcode();
@@ -438,26 +443,16 @@
// If already on work queue, (1) is violated: bail out.
if (!AddQ(&workq, id+1))
goto fail;
- stack[nstack].id = id+1;
- stack[nstack++].cond = cond;
- break;
+ id = id+1;
+ goto Loop;
case kInstByteRange: {
- if (!ip->last()) {
- // If already on work queue, (1) is violated: bail out.
- if (!AddQ(&workq, id+1))
- goto fail;
- stack[nstack].id = id+1;
- stack[nstack++].cond = cond;
- }
-
int nextindex = nodebyid[ip->out()];
if (nextindex == -1) {
if (nalloc >= maxnodes) {
if (Debug)
- LOG(ERROR)
- << StringPrintf("Not OnePass: hit node limit %d > %d",
- nalloc, maxnodes);
+ LOG(ERROR) << StringPrintf(
+ "Not OnePass: hit node limit %d > %d", nalloc, maxnodes);
goto fail;
}
nextindex = nalloc;
@@ -466,8 +461,6 @@
nalloc++;
AddQ(&tovisit, ip->out());
}
- if (matched)
- cond |= kMatchWins;
for (int c = ip->lo(); c <= ip->hi(); c++) {
int b = bytemap_[c];
// Skip any bytes immediately after c that are also in b.
@@ -475,14 +468,14 @@
c++;
uint32 act = node->action[b];
uint32 newact = (nextindex << kIndexShift) | cond;
+ if (matched)
+ newact |= kMatchWins;
if ((act & kImpossible) == kImpossible) {
node->action[b] = newact;
} else if (act != newact) {
if (Debug) {
- LOG(ERROR)
- << StringPrintf("Not OnePass: conflict on byte "
- "%#x at state %d",
- c, *it);
+ LOG(ERROR) << StringPrintf(
+ "Not OnePass: conflict on byte %#x at state %d", c, *it);
}
goto fail;
}
@@ -497,20 +490,27 @@
c++;
uint32 act = node->action[b];
uint32 newact = (nextindex << kIndexShift) | cond;
+ if (matched)
+ newact |= kMatchWins;
if ((act & kImpossible) == kImpossible) {
node->action[b] = newact;
} else if (act != newact) {
if (Debug) {
- LOG(ERROR)
- << StringPrintf("Not OnePass: conflict on byte "
- "%#x at state %d",
- c, *it);
+ LOG(ERROR) << StringPrintf(
+ "Not OnePass: conflict on byte %#x at state %d", c, *it);
}
goto fail;
}
}
}
- break;
+
+ if (ip->last())
+ break;
+ // If already on work queue, (1) is violated: bail out.
+ if (!AddQ(&workq, id+1))
+ goto fail;
+ id = id+1;
+ goto Loop;
}
case kInstCapture:
@@ -538,36 +538,33 @@
// If already on work queue, (1) is violated: bail out.
if (!AddQ(&workq, ip->out())) {
if (Debug) {
- LOG(ERROR) << StringPrintf("Not OnePass: multiple paths"
- " %d -> %d\n",
- *it, ip->out());
+ LOG(ERROR) << StringPrintf(
+ "Not OnePass: multiple paths %d -> %d\n", *it, ip->out());
}
goto fail;
}
- stack[nstack].id = ip->out();
- stack[nstack++].cond = cond;
- break;
+ id = ip->out();
+ goto Loop;
case kInstMatch:
- if (!ip->last()) {
- // If already on work queue, (1) is violated: bail out.
- if (!AddQ(&workq, id+1))
- goto fail;
- stack[nstack].id = id+1;
- stack[nstack++].cond = cond;
- }
-
if (matched) {
// (3) is violated
if (Debug) {
- LOG(ERROR) << StringPrintf("Not OnePass: multiple matches"
- " from %d\n", *it);
+ LOG(ERROR) << StringPrintf(
+ "Not OnePass: multiple matches from %d\n", *it);
}
goto fail;
}
matched = true;
node->matchcond = cond;
- break;
+
+ if (ip->last())
+ break;
+ // If already on work queue, (1) is violated: bail out.
+ if (!AddQ(&workq, id+1))
+ goto fail;
+ id = id+1;
+ goto Loop;
case kInstFail:
break;
@@ -576,28 +573,21 @@
}
if (Debug) { // For debugging, dump one-pass NFA to LOG(ERROR).
- string dump = "prog dump:\n" + Dump() + "node dump\n";
+ LOG(ERROR) << "bytemap:\n" << DumpByteMap();
+ LOG(ERROR) << "prog:\n" << Dump();
+
map<int, int> idmap;
for (int i = 0; i < size; i++)
if (nodebyid[i] != -1)
idmap[nodebyid[i]] = i;
- StringAppendF(&dump, "byte ranges:\n");
- int i = 0;
- for (int b = 0; b < bytemap_range_; b++) {
- int lo = i;
- while (bytemap_[i] == b)
- i++;
- StringAppendF(&dump, "\t%d: %#x-%#x\n", b, lo, i - 1);
- }
-
+ string dump;
for (Instq::iterator it = tovisit.begin(); it != tovisit.end(); ++it) {
int id = *it;
int nodeindex = nodebyid[id];
if (nodeindex == -1)
- continue;
+ continue;
OneState* node = IndexToNode(nodes, statesize, nodeindex);
- string s;
StringAppendF(&dump, "node %d id=%d: matchcond=%#x\n",
nodeindex, id, node->matchcond);
for (int i = 0; i < bytemap_range_; i++) {
@@ -609,7 +599,7 @@
idmap[node->action[i] >> kIndexShift]);
}
}
- LOG(ERROR) << dump;
+ LOG(ERROR) << "nodes:\n" << dump;
}
// Overallocated earlier; cut down to actual size.
