1 //===-- TrigramIndex.h - a heuristic for SpecialCaseList --------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 //===----------------------------------------------------------------------===// 8 // 9 // TrigramIndex implements a heuristic for SpecialCaseList that allows to 10 // filter out ~99% incoming queries when all regular expressions in the 11 // SpecialCaseList are simple wildcards with '*' and '.'. If rules are more 12 // complicated, the check is defeated and it will always pass the queries to a 13 // full regex. 14 // 15 // The basic idea is that in order for a wildcard to match a query, the query 16 // needs to have all trigrams which occur in the wildcard. We create a trigram 17 // index (trigram -> list of rules with it) and then count trigrams in the query 18 // for each rule. If the count for one of the rules reaches the expected value, 19 // the check passes the query to a regex. If none of the rules got enough 20 // trigrams, the check tells that the query is definitely not matched by any 21 // of the rules, and no regex matching is needed. 22 // A similar idea was used in Google Code Search as described in the blog post: 23 // https://swtch.com/~rsc/regexp/regexp4.html 24 // 25 //===----------------------------------------------------------------------===// 26 27 #ifndef LLVM_SUPPORT_TRIGRAMINDEX_H 28 #define LLVM_SUPPORT_TRIGRAMINDEX_H 29 30 #include "llvm/ADT/SmallVector.h" 31 #include "llvm/ADT/StringMap.h" 32 33 #include <string> 34 #include <unordered_map> 35 #include <vector> 36 37 namespace llvm { 38 class StringRef; 39 40 class TrigramIndex { 41 public: 42 /// Inserts a new Regex into the index. 43 void insert(std::string Regex); 44 45 /// Returns true, if special case list definitely does not have a line 46 /// that matches the query. Returns false, if it's not sure. 47 bool isDefinitelyOut(StringRef Query) const; 48 49 /// Returned true, iff the heuristic is defeated and not useful. 50 /// In this case isDefinitelyOut always returns false. isDefeated()51 bool isDefeated() { return Defeated; } 52 private: 53 // If true, the rules are too complicated for the check to work, and full 54 // regex matching is needed for every rule. 55 bool Defeated = false; 56 // The minimum number of trigrams which should match for a rule to have a 57 // chance to match the query. The number of elements equals the number of 58 // regex rules in the SpecialCaseList. 59 std::vector<unsigned> Counts; 60 // Index holds a list of rules indices for each trigram. The same indices 61 // are used in Counts to store per-rule limits. 62 // If a trigram is too common (>4 rules with it), we stop tracking it, 63 // which increases the probability for a need to match using regex, but 64 // decreases the costs in the regular case. 65 std::unordered_map<unsigned, SmallVector<size_t, 4>> Index{256}; 66 }; 67 68 } // namespace llvm 69 70 #endif // LLVM_SUPPORT_TRIGRAMINDEX_H 71