Index: include/llvm/Support/TrigramIndex.h =================================================================== --- /dev/null +++ include/llvm/Support/TrigramIndex.h @@ -0,0 +1,70 @@ +//===-- TrigramIndex.h - a heuristic for SpecialCaseList --------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +//===----------------------------------------------------------------------===// +// +// TrigramIndex implements a heuristic for SpecialCaseList that allows to +// filter out ~99% incoming queries when all regular expressions in the +// SpecialCaseList are simple wildcards with '*' and '.'. If rules are more +// complicated, the check is defeated and it will always pass the queries to a +// full regex. +// +// The basic idea is that in order for a wildcard to match a query, the query +// needs to have all trigrams which occur in the wildcard. We create a trigram +// index (trigram -> list of rules with it) and then count trigrams in the query +// for each rule. If the count for one of the rules reaches the expected value, +// the check passes the query to a regex. If none of the rules got enough +// trigrams, the check tells that the query is definitely not matched by any +// of the rules, and no regex matching is needed. +// A similar idea was used in Google Code Search as described in the blog post: +// https://swtch.com/~rsc/regexp/regexp4.html +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_TRIGRAMINDEX_H +#define LLVM_SUPPORT_TRIGRAMINDEX_H + +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringMap.h" + +#include +#include +#include + +namespace llvm { +class StringRef; + +class TrigramIndex { + public: + /// Inserts a new Regex into the index. + void insert(std::string Regex); + + /// Returns true, if special case list definitely does not have a line + /// that matches the query. Returns false, if it's not sure. + bool isDefinitelyOut(StringRef Query) const; + + /// Returned true, iff the heuristic is defeated and not useful. + /// In this case isDefinitelyOut always returns false. + bool isDefeated() { return Defeated; } + private: + // If true, the rules are too complicated for the check to work, and full + // regex matching is needed for every rule. + bool Defeated = false; + // The minimum number of trigrams which should match for a rule to have a + // chance to match the query. The number of elements equals the number of + // regex rules in the SpecialCaseList. + std::vector Counts; + // Index holds a list of rules indices for each trigram. The same indices + // are used in Counts to store per-rule limits. + // If a trigram is too common (>4 rules with it), we stop tracking it, + // which increases the probability for a need to match using regex, but + // decreases the costs in the regular case. + std::unordered_map> Index{256}; +}; + +} // namespace llvm + +#endif // LLVM_SUPPORT_TRIGRAMINDEX_H Index: lib/Support/CMakeLists.txt =================================================================== --- lib/Support/CMakeLists.txt +++ lib/Support/CMakeLists.txt @@ -94,6 +94,7 @@ ThreadPool.cpp Timer.cpp ToolOutputFile.cpp + TrigramIndex.cpp Triple.cpp Twine.cpp Unicode.cpp Index: lib/Support/SpecialCaseList.cpp =================================================================== --- lib/Support/SpecialCaseList.cpp +++ lib/Support/SpecialCaseList.cpp @@ -15,6 +15,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Support/SpecialCaseList.h" +#include "llvm/Support/TrigramIndex.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringSet.h" @@ -33,10 +34,15 @@ /// literal strings than Regex. struct SpecialCaseList::Entry { StringSet<> Strings; + TrigramIndex Trigrams; std::unique_ptr RegEx; bool match(StringRef Query) const { - return Strings.count(Query) || (RegEx && RegEx->match(Query)); + if (Strings.count(Query)) + return true; + if (Trigrams.isDefinitelyOut(Query)) + return false; + return RegEx && RegEx->match(Query); } }; @@ -104,10 +110,12 @@ StringRef Category = SplitRegexp.second; // See if we can store Regexp in Strings. + auto &Entry = Entries[Prefix][Category]; if (Regex::isLiteralERE(Regexp)) { - Entries[Prefix][Category].Strings.insert(Regexp); + Entry.Strings.insert(Regexp); continue; } + Entry.Trigrams.insert(Regexp); // Replace * with .* for (size_t pos = 0; (pos = Regexp.find('*', pos)) != std::string::npos; Index: lib/Support/TrigramIndex.cpp =================================================================== --- /dev/null +++ lib/Support/TrigramIndex.cpp @@ -0,0 +1,98 @@ +//===-- TrigramIndex.cpp - a heuristic for SpecialCaseList ----------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// TrigramIndex implements a heuristic for SpecialCaseList that allows to +// filter out ~99% incoming queries when all regular expressions in the +// SpecialCaseList are simple wildcards with '*' and '.'. If rules are more +// complicated, the check is defeated and it will always pass the queries to a +// full regex. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Support/TrigramIndex.h" +#include "llvm/ADT/SmallVector.h" + +#include +#include +#include + +using namespace llvm; + +static const char RegexAdvancedMetachars[] = "()^$|+?[]\\{}"; + +static bool isSimpleWildcard(StringRef Str) { + // Check for regex metacharacters other than '*' and '.'. + return Str.find_first_of(RegexAdvancedMetachars) == StringRef::npos; +} + +void TrigramIndex::insert(std::string Regex) { + if (Defeated) return; + if (!isSimpleWildcard(Regex)) { + Defeated = true; + return; + } + + std::set Was; + unsigned Cnt = 0; + unsigned Tri = 0; + unsigned Len = 0; + for (unsigned Char : Regex) { + if (Char == '.' || Char == '*') { + Tri = 0; + Len = 0; + continue; + } + Tri = ((Tri << 8) + Char) & 0xFFFFFF; + Len++; + if (Len < 3) + continue; + // We don't want the index to grow too much for the popular trigrams, + // as they are weak signals. It's ok to still require them for the + // rules we have already processed. It's just a small additional + // computational cost. + if (Index[Tri].size() >= 4) + continue; + Cnt++; + if (!Was.count(Tri)) { + // Adding the current rule to the index. + Index[Tri].push_back(Counts.size()); + Was.insert(Tri); + } + } + if (!Cnt) { + // This rule does not have remarkable trigrams to rely on. + // We have to always call the full regex chain. + Defeated = true; + return; + } + Counts.push_back(Cnt); +} + +bool TrigramIndex::isDefinitelyOut(StringRef Query) const { + if (Defeated) + return false; + std::vector CurCounts(Counts.size()); + unsigned Tri = 0; + for (size_t I = 0; I < Query.size(); I++) { + Tri = ((Tri << 8) + Query[I]) & 0xFFFFFF; + if (I < 2) + continue; + const auto &II = Index.find(Tri); + if (II == Index.end()) + continue; + for (size_t J : II->second) { + CurCounts[J]++; + // If we have reached a desired limit, we have to look at the query + // more closely by running a full regex. + if (CurCounts[J] >= Counts[J]) + return false; + } + } + return true; +} Index: unittests/Support/CMakeLists.txt =================================================================== --- unittests/Support/CMakeLists.txt +++ unittests/Support/CMakeLists.txt @@ -48,6 +48,7 @@ TimerTest.cpp TypeNameTest.cpp TrailingObjectsTest.cpp + TrigramIndexTest.cpp UnicodeTest.cpp YAMLIOTest.cpp YAMLParserTest.cpp Index: unittests/Support/SpecialCaseListTest.cpp =================================================================== --- unittests/Support/SpecialCaseListTest.cpp +++ unittests/Support/SpecialCaseListTest.cpp @@ -134,4 +134,48 @@ sys::fs::remove(Path); } +TEST_F(SpecialCaseListTest, NoTrigramsInRules) { + std::unique_ptr SCL = makeSpecialCaseList("fun:b.r\n" + "fun:za*az\n"); + EXPECT_TRUE(SCL->inSection("fun", "bar")); + EXPECT_FALSE(SCL->inSection("fun", "baz")); + EXPECT_TRUE(SCL->inSection("fun", "zakaz")); + EXPECT_FALSE(SCL->inSection("fun", "zaraza")); +} + +TEST_F(SpecialCaseListTest, NoTrigramsInARule) { + std::unique_ptr SCL = makeSpecialCaseList("fun:*bar*\n" + "fun:za*az\n"); + EXPECT_TRUE(SCL->inSection("fun", "abara")); + EXPECT_FALSE(SCL->inSection("fun", "bor")); + EXPECT_TRUE(SCL->inSection("fun", "zakaz")); + EXPECT_FALSE(SCL->inSection("fun", "zaraza")); +} + +TEST_F(SpecialCaseListTest, RepetitiveRule) { + std::unique_ptr SCL = makeSpecialCaseList("fun:*bar*bar*bar*bar*\n" + "fun:bar*\n"); + EXPECT_TRUE(SCL->inSection("fun", "bara")); + EXPECT_FALSE(SCL->inSection("fun", "abara")); + EXPECT_TRUE(SCL->inSection("fun", "barbarbarbar")); + EXPECT_TRUE(SCL->inSection("fun", "abarbarbarbar")); + EXPECT_FALSE(SCL->inSection("fun", "abarbarbar")); +} + +TEST_F(SpecialCaseListTest, SpecialSymbolRule) { + std::unique_ptr SCL = makeSpecialCaseList("src:*c\\+\\+abi*\n"); + EXPECT_TRUE(SCL->inSection("src", "c++abi")); + EXPECT_FALSE(SCL->inSection("src", "c\\+\\+abi")); +} + +TEST_F(SpecialCaseListTest, PopularTrigram) { + std::unique_ptr SCL = makeSpecialCaseList("fun:*aaaaaa*\n" + "fun:*aaaaa*\n" + "fun:*aaaa*\n" + "fun:*aaa*\n"); + EXPECT_TRUE(SCL->inSection("fun", "aaa")); + EXPECT_TRUE(SCL->inSection("fun", "aaaa")); + EXPECT_TRUE(SCL->inSection("fun", "aaaabbbaaa")); +} + } Index: unittests/Support/TrigramIndexTest.cpp =================================================================== --- /dev/null +++ unittests/Support/TrigramIndexTest.cpp @@ -0,0 +1,112 @@ +//===- TrigramIndexTest.cpp - Unit tests for TrigramIndex -----------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/STLExtras.h" +#include "llvm/Support/TrigramIndex.h" +#include "gtest/gtest.h" + +#include +#include + +using namespace llvm; + +namespace { + +class TrigramIndexTest : public ::testing::Test { +protected: + std::unique_ptr makeTrigramIndex( + std::vector Rules) { + std::unique_ptr TI = + make_unique(); + for (auto &Rule : Rules) + TI->insert(Rule); + return TI; + } +}; + +TEST_F(TrigramIndexTest, Empty) { + std::unique_ptr TI = + makeTrigramIndex({}); + EXPECT_FALSE(TI->isDefeated()); + EXPECT_TRUE(TI->isDefinitelyOut("foo")); +} + +TEST_F(TrigramIndexTest, Basic) { + std::unique_ptr TI = + makeTrigramIndex({"*hello*", "*wor.d*"}); + EXPECT_FALSE(TI->isDefeated()); + EXPECT_TRUE(TI->isDefinitelyOut("foo")); +} + +TEST_F(TrigramIndexTest, NoTrigramsInRules) { + std::unique_ptr TI = + makeTrigramIndex({"b.r", "za*az"}); + EXPECT_TRUE(TI->isDefeated()); + EXPECT_FALSE(TI->isDefinitelyOut("foo")); + EXPECT_FALSE(TI->isDefinitelyOut("bar")); + EXPECT_FALSE(TI->isDefinitelyOut("zakaz")); +} + +TEST_F(TrigramIndexTest, NoTrigramsInARule) { + std::unique_ptr TI = + makeTrigramIndex({"*hello*", "*wo.ld*"}); + EXPECT_TRUE(TI->isDefeated()); + EXPECT_FALSE(TI->isDefinitelyOut("foo")); +} + +TEST_F(TrigramIndexTest, RepetitiveRule) { + std::unique_ptr TI = + makeTrigramIndex({"*bar*bar*bar*bar*bar", "bar*bar"}); + EXPECT_FALSE(TI->isDefeated()); + EXPECT_TRUE(TI->isDefinitelyOut("foo")); + EXPECT_TRUE(TI->isDefinitelyOut("bar")); + EXPECT_FALSE(TI->isDefinitelyOut("barbara")); + EXPECT_FALSE(TI->isDefinitelyOut("bar+bar")); +} + +TEST_F(TrigramIndexTest, PopularTrigram) { + std::unique_ptr TI = + makeTrigramIndex({"*aaa*", "*aaaa*", "*aaaaa*", "*aaaaa*", "*aaaaaa*"}); + EXPECT_TRUE(TI->isDefeated()); +} + +TEST_F(TrigramIndexTest, PopularTrigram2) { + std::unique_ptr TI = + makeTrigramIndex({"class1.h", "class2.h", "class3.h", "class4.h", "class.h"}); + EXPECT_TRUE(TI->isDefeated()); +} + +TEST_F(TrigramIndexTest, TooComplicatedRegex) { + std::unique_ptr TI = + makeTrigramIndex({"[0-9]+"}); + EXPECT_TRUE(TI->isDefeated()); +} + +TEST_F(TrigramIndexTest, TooComplicatedRegex2) { + std::unique_ptr TI = + makeTrigramIndex({"foo|bar"}); + EXPECT_TRUE(TI->isDefeated()); +} + +TEST_F(TrigramIndexTest, SpecialSymbol) { + std::unique_ptr TI = + makeTrigramIndex({"*c\\+\\+*"}); + EXPECT_TRUE(TI->isDefeated()); +} + +TEST_F(TrigramIndexTest, Sequence) { + std::unique_ptr TI = + makeTrigramIndex({"class1.h", "class2.h", "class3.h", "class4.h"}); + EXPECT_FALSE(TI->isDefeated()); + EXPECT_FALSE(TI->isDefinitelyOut("class1")); + EXPECT_TRUE(TI->isDefinitelyOut("class.h")); + EXPECT_TRUE(TI->isDefinitelyOut("class")); +} + +} // namespace