Home | History | Annotate | Line # | Download | only in Support 
      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.
     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