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/StringMap.h" 31 32#include <string> 33#include <unordered_map> 34#include <vector> 35 36namespace llvm { 37class StringRef; 38 39class TrigramIndex { 40 public: 41 /// Inserts a new Regex into the index. 42 void insert(std::string Regex); 43 44 /// Returns true, if special case list definitely does not have a line 45 /// that matches the query. Returns false, if it's not sure. 46 bool isDefinitelyOut(StringRef Query) const; 47 48 /// Returned true, iff the heuristic is defeated and not useful. 49 /// In this case isDefinitelyOut always returns false. 50 bool isDefeated() { return Defeated; } 51 private: 52 // If true, the rules are too complicated for the check to work, and full 53 // regex matching is needed for every rule. 54 bool Defeated = false; 55 // The minimum number of trigrams which should match for a rule to have a 56 // chance to match the query. The number of elements equals the number of 57 // regex rules in the SpecialCaseList. 58 std::vector<unsigned> Counts; 59 // Index holds a list of rules indices for each trigram. The same indices 60 // are used in Counts to store per-rule limits. 61 // If a trigram is too common (>4 rules with it), we stop tracking it, 62 // which increases the probability for a need to match using regex, but 63 // decreases the costs in the regular case. 64 std::unordered_map<unsigned, SmallVector<size_t, 4>> Index{256}; 65}; 66 67} // namespace llvm 68 69#endif // LLVM_SUPPORT_TRIGRAMINDEX_H 70