1311116Sdim//===-- TrigramIndex.h - a heuristic for SpecialCaseList --------*- C++ -*-===// 2311116Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6311116Sdim//===----------------------------------------------------------------------===// 7311116Sdim// 8311116Sdim// TrigramIndex implements a heuristic for SpecialCaseList that allows to 9311116Sdim// filter out ~99% incoming queries when all regular expressions in the 10311116Sdim// SpecialCaseList are simple wildcards with '*' and '.'. If rules are more 11311116Sdim// complicated, the check is defeated and it will always pass the queries to a 12311116Sdim// full regex. 13311116Sdim// 14311116Sdim// The basic idea is that in order for a wildcard to match a query, the query 15311116Sdim// needs to have all trigrams which occur in the wildcard. We create a trigram 16311116Sdim// index (trigram -> list of rules with it) and then count trigrams in the query 17311116Sdim// for each rule. If the count for one of the rules reaches the expected value, 18311116Sdim// the check passes the query to a regex. If none of the rules got enough 19311116Sdim// trigrams, the check tells that the query is definitely not matched by any 20311116Sdim// of the rules, and no regex matching is needed. 21311116Sdim// A similar idea was used in Google Code Search as described in the blog post: 22311116Sdim// https://swtch.com/~rsc/regexp/regexp4.html 23311116Sdim// 24311116Sdim//===----------------------------------------------------------------------===// 25311116Sdim 26311116Sdim#ifndef LLVM_SUPPORT_TRIGRAMINDEX_H 27311116Sdim#define LLVM_SUPPORT_TRIGRAMINDEX_H 28311116Sdim 29311116Sdim#include "llvm/ADT/SmallVector.h" 30311116Sdim#include "llvm/ADT/StringMap.h" 31311116Sdim 32311116Sdim#include <string> 33311116Sdim#include <unordered_map> 34311116Sdim#include <vector> 35311116Sdim 36311116Sdimnamespace llvm { 37311116Sdimclass StringRef; 38311116Sdim 39311116Sdimclass TrigramIndex { 40311116Sdim public: 41311116Sdim /// Inserts a new Regex into the index. 42311116Sdim void insert(std::string Regex); 43311116Sdim 44311116Sdim /// Returns true, if special case list definitely does not have a line 45311116Sdim /// that matches the query. Returns false, if it's not sure. 46311116Sdim bool isDefinitelyOut(StringRef Query) const; 47311116Sdim 48311116Sdim /// Returned true, iff the heuristic is defeated and not useful. 49311116Sdim /// In this case isDefinitelyOut always returns false. 50311116Sdim bool isDefeated() { return Defeated; } 51311116Sdim private: 52311116Sdim // If true, the rules are too complicated for the check to work, and full 53311116Sdim // regex matching is needed for every rule. 54311116Sdim bool Defeated = false; 55311116Sdim // The minimum number of trigrams which should match for a rule to have a 56311116Sdim // chance to match the query. The number of elements equals the number of 57311116Sdim // regex rules in the SpecialCaseList. 58311116Sdim std::vector<unsigned> Counts; 59311116Sdim // Index holds a list of rules indices for each trigram. The same indices 60311116Sdim // are used in Counts to store per-rule limits. 61311116Sdim // If a trigram is too common (>4 rules with it), we stop tracking it, 62311116Sdim // which increases the probability for a need to match using regex, but 63311116Sdim // decreases the costs in the regular case. 64311116Sdim std::unordered_map<unsigned, SmallVector<size_t, 4>> Index{256}; 65311116Sdim}; 66311116Sdim 67311116Sdim} // namespace llvm 68311116Sdim 69311116Sdim#endif // LLVM_SUPPORT_TRIGRAMINDEX_H 70