LLVM  16.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 <string>
31 #include <unordered_map>
32 #include <vector>
33 
34 namespace llvm {
35 class StringRef;
36 
37 class TrigramIndex {
38  public:
39  /// Inserts a new Regex into the index.
40  void insert(const std::string &Regex);
41 
42  /// Returns true, if special case list definitely does not have a line
43  /// that matches the query. Returns false, if it's not sure.
44  bool isDefinitelyOut(StringRef Query) const;
45 
46  /// Returned true, iff the heuristic is defeated and not useful.
47  /// In this case isDefinitelyOut always returns false.
48  bool isDefeated() { return Defeated; }
49  private:
50  // If true, the rules are too complicated for the check to work, and full
51  // regex matching is needed for every rule.
52  bool Defeated = false;
53  // The minimum number of trigrams which should match for a rule to have a
54  // chance to match the query. The number of elements equals the number of
55  // regex rules in the SpecialCaseList.
56  std::vector<unsigned> Counts;
57  // Index holds a list of rules indices for each trigram. The same indices
58  // are used in Counts to store per-rule limits.
59  // If a trigram is too common (>4 rules with it), we stop tracking it,
60  // which increases the probability for a need to match using regex, but
61  // decreases the costs in the regular case.
62  std::unordered_map<unsigned, SmallVector<size_t, 4>> Index{256};
63 };
64 
65 } // namespace llvm
66 
67 #endif // LLVM_SUPPORT_TRIGRAMINDEX_H
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::dwarf::Index
Index
Definition: Dwarf.h:490
llvm::TrigramIndex::insert
void insert(const std::string &Regex)
Inserts a new Regex into the index.
Definition: TrigramIndex.cpp:29
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
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:86
SmallVector.h
llvm::Regex
Definition: Regex.h:28
llvm::TrigramIndex
Definition: TrigramIndex.h:37
llvm::TrigramIndex::isDefeated
bool isDefeated()
Returned true, iff the heuristic is defeated and not useful.
Definition: TrigramIndex.h:48