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