LLVM  9.0.0svn
TrigramIndex.h
Go to the documentation of this file.
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
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool isDefinitelyOut(StringRef Query) const
Returns true, if special case list definitely does not have a line that matches the query...
void insert(std::string Regex)
Inserts a new Regex into the index.
bool isDefeated()
Returned true, iff the heuristic is defeated and not useful.
Definition: TrigramIndex.h:50
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48