Index: include/llvm/Support/Regex.h =================================================================== --- include/llvm/Support/Regex.h +++ include/llvm/Support/Regex.h @@ -90,6 +90,11 @@ /// expression that matches Str and only Str. static bool isLiteralERE(StringRef Str); + /// \brief If this function returns true, Str is a simple wildcard with + /// regular chars and optional star and dot wildcards like foo*b.r. This is a + /// common case for sanitizers blacklists. + static bool isSimpleWildcard(StringRef Str); + /// \brief Turn String into a regex by escaping its special characters. static std::string escape(StringRef String); Index: lib/Support/Regex.cpp =================================================================== --- lib/Support/Regex.cpp +++ lib/Support/Regex.cpp @@ -185,6 +185,7 @@ // These are the special characters matched in functions like "p_ere_exp". static const char RegexMetachars[] = "()^$|*+?.[]\\{}"; +static const char RegexAdvancedMetachars[] = "()^$|+?[]\\{}"; bool Regex::isLiteralERE(StringRef Str) { // Check for regex metacharacters. This list was derived from our regex @@ -193,6 +194,11 @@ return Str.find_first_of(RegexMetachars) == StringRef::npos; } +bool Regex::isSimpleWildcard(StringRef Str) { + // Check for regex metacharacters other than '*' and '.'. + return Str.find_first_of(RegexAdvancedMetachars) == StringRef::npos; +} + std::string Regex::escape(StringRef String) { std::string RegexStr; for (unsigned i = 0, e = String.size(); i != e; ++i) { Index: lib/Support/SpecialCaseList.cpp =================================================================== --- lib/Support/SpecialCaseList.cpp +++ lib/Support/SpecialCaseList.cpp @@ -20,12 +20,110 @@ #include "llvm/ADT/StringSet.h" #include "llvm/Support/MemoryBuffer.h" #include "llvm/Support/Regex.h" +#include +#include #include #include #include namespace llvm { +// TrigramIndex implements a heuristics that allows to filter ~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 exist 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 regexp. 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 +struct TrigramIndex { + // If true, the rules are too complicated for the check to work, and full + // regex matching is needed for every rule. + bool Defeated; + // 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. + // 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; + + TrigramIndex(): Index(256) {} + + void insert(std::string Regex) { + if (Defeated) return; + if (!Regex::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 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; + } +}; + /// Represents a set of regular expressions. Regular expressions which are /// "literal" (i.e. no regex metacharacters) are stored in Strings, while all /// others are represented as a single pipe-separated regex in RegEx. The @@ -33,10 +131,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 +207,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: 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")); +} + }