Improve the efficiency of bytecode generated for CharClass. Change-Id: Ibf00ad9575ae800eedfc1c0f0a440fae261dce53 Reviewed-on: https://code-review.googlesource.com/4040 Reviewed-by: Russ Cox <rsc@swtch.com> Reviewed-by: Paul Wankadia <junyer@google.com>
diff --git a/re2/compile.cc b/re2/compile.cc index 5037524..9882fef 100644 --- a/re2/compile.cc +++ b/re2/compile.cc
@@ -113,7 +113,7 @@ // Input encodings. enum Encoding { kEncodingUTF8 = 1, // UTF-8 (0-10FFFF) - kEncodingLatin1, // Latin1 (0-FF) + kEncodingLatin1, // Latin-1 (0-FF) }; class Compiler : public Regexp::Walker<Frag> { @@ -193,12 +193,28 @@ void Add_80_10ffff(); // New suffix that matches the byte range lo-hi, then goes to next. - int RuneByteSuffix(uint8 lo, uint8 hi, bool foldcase, int next); int UncachedRuneByteSuffix(uint8 lo, uint8 hi, bool foldcase, int next); + int CachedRuneByteSuffix(uint8 lo, uint8 hi, bool foldcase, int next); + + // Returns true iff the suffix is cached. + bool IsCachedRuneByteSuffix(int id); // Adds a suffix to alternation. void AddSuffix(int id); + // Adds a suffix to the trie starting from the given root node. + // Returns zero iff allocating an instruction fails. Otherwise, returns + // the current root node, which might be different from what was given. + int AddSuffixRecursive(int root, int id); + + // Finds the trie node for the given suffix. Returns a Frag in order to + // distinguish between pointing at the root node directly (end.p == 0) + // and pointing at an Alt's out1 or out (end.p&1 == 1 or 0, respectively). + Frag FindByteRange(int root, int id); + + // Compares two ByteRanges and returns true iff they are equal. + bool ByteRangeEqual(int id1, int id2); + // Returns the alternation of all the added suffixes. Frag EndRange(); @@ -496,21 +512,17 @@ return f.begin; } -int Compiler::RuneByteSuffix(uint8 lo, uint8 hi, bool foldcase, int next) { - // In Latin1 mode, there's no point in caching. - // In forward UTF-8 mode, only need to cache continuation bytes. - if (encoding_ == kEncodingLatin1 || - (encoding_ == kEncodingUTF8 && - !reversed_ && - !(0x80 <= lo && hi <= 0xbf))) { - return UncachedRuneByteSuffix(lo, hi, foldcase, next); - } +static uint64 MakeRuneCacheKey(uint8 lo, uint8 hi, bool foldcase, int next) { + return (uint64)next << 17 | + (uint64)lo << 9 | + (uint64)hi << 1 | + (uint64)foldcase; +} - uint64 key = (uint64)next << 17 | - (uint64)lo << 9 | - (uint64)hi << 1 | - (uint64)foldcase; - map<uint64, int>::iterator it = rune_cache_.find(key); +int Compiler::CachedRuneByteSuffix(uint8 lo, uint8 hi, bool foldcase, + int next) { + uint64 key = MakeRuneCacheKey(lo, hi, foldcase, next); + map<uint64, int>::const_iterator it = rune_cache_.find(key); if (it != rune_cache_.end()) return it->second; int id = UncachedRuneByteSuffix(lo, hi, foldcase, next); @@ -518,12 +530,28 @@ return id; } +bool Compiler::IsCachedRuneByteSuffix(int id) { + uint8 lo = inst_[id].lo_; + uint8 hi = inst_[id].hi_; + bool foldcase = inst_[id].foldcase() != 0; + int next = inst_[id].out(); + + uint64 key = MakeRuneCacheKey(lo, hi, foldcase, next); + return rune_cache_.find(key) != rune_cache_.end(); +} + void Compiler::AddSuffix(int id) { if (rune_range_.begin == 0) { rune_range_.begin = id; return; } + if (encoding_ == kEncodingUTF8) { + // Build a trie in order to reduce fanout. + rune_range_.begin = AddSuffixRecursive(rune_range_.begin, id); + return; + } + int alt = AllocInst(1); if (alt < 0) { rune_range_.begin = 0; @@ -533,6 +561,105 @@ rune_range_.begin = alt; } +int Compiler::AddSuffixRecursive(int root, int id) { + DCHECK(inst_[root].opcode() == kInstAlt || + inst_[root].opcode() == kInstByteRange); + + Frag f = FindByteRange(root, id); + if (IsNoMatch(f)) { + int alt = AllocInst(1); + if (alt < 0) + return 0; + inst_[alt].InitAlt(root, id); + return alt; + } + + int br; + if (f.end.p == 0) + br = root; + else if (f.end.p&1) + br = inst_[f.begin].out1(); + else + br = inst_[f.begin].out(); + + if (IsCachedRuneByteSuffix(br)) { + // We can't fiddle with cached suffixes, so make a clone of the head. + int byterange = AllocInst(1); + if (byterange < 0) + return 0; + inst_[byterange].InitByteRange(inst_[br].lo(), inst_[br].hi(), + inst_[br].foldcase(), inst_[br].out()); + + // Ensure that the parent points to the clone, not to the original. + // Note that this could leave the head unreachable except via the cache. + br = byterange; + if (f.end.p == 0) + root = br; + else if (f.end.p&1) + inst_[f.begin].out1_ = br; + else + inst_[f.begin].set_out(br); + } + + // We just saved one ByteRange instruction. :) + prog_->byte_inst_count_--; + + int out = inst_[id].out(); + if (!IsCachedRuneByteSuffix(id)) { + // The head should be the instruction most recently allocated, so free it + // instead of leaving it unreachable. + DCHECK_EQ(id, inst_len_-1); + inst_[id].out_opcode_ = 0; + inst_[id].out1_ = 0; + inst_len_--; + } + + out = AddSuffixRecursive(inst_[br].out(), out); + if (out == 0) + return 0; + + inst_[br].set_out(out); + return root; +} + +bool Compiler::ByteRangeEqual(int id1, int id2) { + return inst_[id1].lo() == inst_[id2].lo() && + inst_[id1].hi() == inst_[id2].hi() && + inst_[id1].foldcase() == inst_[id2].foldcase(); +} + +Frag Compiler::FindByteRange(int root, int id) { + if (inst_[root].opcode() == kInstByteRange) { + if (ByteRangeEqual(root, id)) + return Frag(root, nullPatchList); + else + return NoMatch(); + } + + while (inst_[root].opcode() == kInstAlt) { + int out1 = inst_[root].out1(); + if (ByteRangeEqual(out1, id)) + return Frag(root, PatchList::Mk((root << 1) | 1)); + + // CharClass is a sorted list of ranges, so if out1 of the root Alt wasn't + // what we're looking for, then we can stop immediately. Unfortunately, we + // can't short-circuit the search in reverse mode. + if (!reversed_) + return NoMatch(); + + int out = inst_[root].out(); + if (inst_[out].opcode() == kInstAlt) + root = out; + else if (ByteRangeEqual(out, id)) + return Frag(root, PatchList::Mk(root << 1)); + else + return NoMatch(); + } + + LOG(DFATAL) << "should never happen"; + return NoMatch(); +} + Frag Compiler::EndRange() { return rune_range_; } @@ -556,13 +683,13 @@ } void Compiler::AddRuneRangeLatin1(Rune lo, Rune hi, bool foldcase) { - // Latin1 is easy: runes *are* bytes. + // Latin-1 is easy: runes *are* bytes. if (lo > hi || lo > 0xFF) return; if (hi > 0xFF) hi = 0xFF; - AddSuffix(RuneByteSuffix(static_cast<uint8>(lo), static_cast<uint8>(hi), - foldcase, 0)); + AddSuffix(UncachedRuneByteSuffix(static_cast<uint8>(lo), + static_cast<uint8>(hi), foldcase, 0)); } // Table describing how to make a UTF-8 matching machine @@ -633,8 +760,8 @@ // ASCII range is always a special case. if (hi < Runeself) { - AddSuffix(RuneByteSuffix(static_cast<uint8>(lo), static_cast<uint8>(hi), - foldcase, 0)); + AddSuffix(UncachedRuneByteSuffix(static_cast<uint8>(lo), + static_cast<uint8>(hi), foldcase, 0)); return; } @@ -662,13 +789,49 @@ (void)m; // USED(m) DCHECK_EQ(n, m); + // The logic below encodes this thinking: + // + // 1. When we have built the whole suffix, we know that it cannot + // possibly be a suffix of anything longer: in forward mode, nothing + // else can occur before the leading byte; in reverse mode, nothing + // else can occur after the last continuation byte or else the leading + // byte would have to change. Thus, there is no benefit to caching + // the first byte of the suffix whereas there is a cost involved in + // cloning it if it begins a common prefix, which is fairly likely. + // + // 2. Conversely, the last byte of the suffix cannot possibly be a + // prefix of anything because next == 0, so we will never want to + // clone it, but it is fairly likely to be a common suffix. Perhaps + // more so in reverse mode than in forward mode because the former is + // "converging" towards lower entropy, but caching is still worthwhile + // for the latter in cases such as 80-BF. + // + // 3. Handling the bytes between the first and the last is less + // straightforward and, again, the approach depends on whether we are + // "converging" towards lower entropy: in forward mode, a single byte + // is unlikely to be part of a common suffix whereas a byte range + // is more likely so; in reverse mode, a byte range is unlikely to + // be part of a common suffix whereas a single byte is more likely + // so. The same benefit versus cost argument applies here. int id = 0; if (reversed_) { - for (int i = 0; i < n; i++) - id = RuneByteSuffix(ulo[i], uhi[i], false, id); + for (int i = 0; i < n; i++) { + // In reverse UTF-8 mode: cache the leading byte; don't cache the last + // continuation byte; cache anything else iff it's a single byte (XX-XX). + if (i == 0 || (ulo[i] == uhi[i] && i != n-1)) + id = CachedRuneByteSuffix(ulo[i], uhi[i], false, id); + else + id = UncachedRuneByteSuffix(ulo[i], uhi[i], false, id); + } } else { - for (int i = n-1; i >= 0; i--) - id = RuneByteSuffix(ulo[i], uhi[i], false, id); + for (int i = n-1; i >= 0; i--) { + // In forward UTF-8 mode: don't cache the leading byte; cache the last + // continuation byte; cache anything else iff it's a byte range (XX-YY). + if (i == n-1 || (ulo[i] < uhi[i] && i != 0)) + id = CachedRuneByteSuffix(ulo[i], uhi[i], false, id); + else + id = UncachedRuneByteSuffix(ulo[i], uhi[i], false, id); + } } AddSuffix(id); }
diff --git a/re2/testing/compile_test.cc b/re2/testing/compile_test.cc index d438b19..dee90a3 100644 --- a/re2/testing/compile_test.cc +++ b/re2/testing/compile_test.cc
@@ -172,4 +172,90 @@ re->Decref(); } +static void Dump(StringPiece pattern, Regexp::ParseFlags flags, + string* forward, string* reverse) { + Regexp* re = Regexp::Parse(pattern, flags, NULL); + EXPECT_TRUE(re != NULL); + + if (forward != NULL) { + Prog* prog = re->CompileToProg(0); + EXPECT_TRUE(prog != NULL); + *forward = prog->Dump(); + delete prog; + } + + if (reverse != NULL) { + Prog* prog = re->CompileToReverseProg(0); + EXPECT_TRUE(prog != NULL); + *reverse = prog->Dump(); + delete prog; + } + + re->Decref(); +} + +TEST(TestCompile, Bug26705922) { + // Bug in the compiler caused inefficient bytecode to be generated for Unicode + // groups: common suffixes were cached, but common prefixes were not factored. + + string forward, reverse; + + Dump("[\\x{10000}\\x{10010}]", Regexp::LikePerl, &forward, &reverse); + EXPECT_EQ("4. byte [f0-f0] -> 3\n" + "3. byte [90-90] -> 2\n" + "2. byte [80-80] -> 6\n" + "6. alt -> 1 | 5\n" + "1. byte [80-80] -> 7\n" + "5. byte [90-90] -> 7\n" + "7. match! 0\n", + forward); + EXPECT_EQ("6. alt -> 4 | 5\n" + "4. byte [80-80] -> 3\n" + "5. byte [90-90] -> 3\n" + "3. byte [80-80] -> 2\n" + "2. byte [90-90] -> 1\n" + "1. byte [f0-f0] -> 7\n" + "7. match! 0\n", + reverse); + + Dump("[\\x{8000}-\\x{10FFF}]", Regexp::LikePerl, &forward, &reverse); + EXPECT_EQ("6. alt -> 3 | 5\n" + "3. byte [e8-ef] -> 2\n" + "5. byte [f0-f0] -> 4\n" + "2. byte [80-bf] -> 1\n" + "4. byte [90-90] -> 2\n" + "1. byte [80-bf] -> 7\n" + "7. match! 0\n", + forward); + EXPECT_EQ("3. byte [80-bf] -> 2\n" + "2. byte [80-bf] -> 6\n" + "6. alt -> 1 | 5\n" + "1. byte [e8-ef] -> 7\n" + "5. byte [90-90] -> 4\n" + "7. match! 0\n" + "4. byte [f0-f0] -> 7\n", + reverse); + + Dump("[\\x{80}-\\x{10FFFF}]", Regexp::LikePerl, NULL, &reverse); + EXPECT_EQ("2. byte [80-bf] -> 8\n" + "8. alt -> 5 | 7\n" + "5. alt -> 1 | 4\n" + "7. byte [80-bf] -> 17\n" + "1. byte [c2-df] -> 18\n" + "4. byte [a0-bf] -> 3\n" + "17. alt -> 14 | 16\n" + "18. match! 0\n" + "3. byte [e0-e0] -> 18\n" + "14. alt -> 11 | 13\n" + "16. byte [80-8f] -> 15\n" + "11. alt -> 6 | 10\n" + "13. byte [80-bf] -> 12\n" + "15. byte [f4-f4] -> 18\n" + "6. byte [e1-ef] -> 18\n" + "10. byte [90-bf] -> 9\n" + "12. byte [f1-f3] -> 18\n" + "9. byte [f0-f0] -> 18\n", + reverse); +} + } // namespace re2