LLVM  14.0.0git
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/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
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
StringRef.h
llvm::TrigramIndex::insert
void insert(const std::string &Regex)
Inserts a new Regex into the index.
Definition: TrigramIndex.cpp:28
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
llvm::TrigramIndex::isDefinitelyOut
bool isDefinitelyOut(StringRef Query) const
Returns true, if special case list definitely does not have a line that matches the query.
Definition: TrigramIndex.cpp:85
SmallVector.h
llvm::Regex
Definition: Regex.h:28
llvm::TrigramIndex
Definition: TrigramIndex.h:38
llvm::TrigramIndex::isDefeated
bool isDefeated()
Returned true, iff the heuristic is defeated and not useful.
Definition: TrigramIndex.h:49