Make DFA use hints.
Change-Id: I7b7b338a019ea19c4a99072c961dc6aa35c15915
Reviewed-on: https://code-review.googlesource.com/c/re2/+/49950
Reviewed-by: Paul Wankadia <junyer@google.com>
diff --git a/re2/dfa.cc b/re2/dfa.cc
index 816080a..b3b5eca 100644
--- a/re2/dfa.cc
+++ b/re2/dfa.cc
@@ -971,8 +971,21 @@
break;
case kInstByteRange: // can follow if c is in range
- if (ip->Matches(c))
- AddToQueue(newq, ip->out(), flag);
+ if (!ip->Matches(c))
+ break;
+ AddToQueue(newq, ip->out(), flag);
+ if (ip->hint() != 0) {
+ // We have a hint, but we must cancel out the
+ // increment that will occur after the break.
+ i += ip->hint() - 1;
+ } else {
+ // We have no hint, so we must find the end
+ // of the current list and then skip to it.
+ Prog::Inst* ip0 = ip;
+ while (!ip->last())
+ ++ip;
+ i += ip - ip0;
+ }
break;
case kInstMatch: