include/llvm/Support/TrigramIndex.h

   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
  36 namespace llvm {
  37 class StringRef;
  38
  39 class 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