LLVM 17.0.0git
Go to the documentation of this file.
1//===-- TrigramIndex.h - a heuristic for SpecialCaseList --------*- C++ -*-===//
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
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.
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
30#include <string>
31#include <unordered_map>
32#include <vector>
34namespace llvm {
35class StringRef;
38 public:
39 /// Inserts a new Regex into the index.
40 void insert(const std::string &Regex);
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;
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};
65} // namespace llvm
This file defines the SmallVector class.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
bool isDefeated()
Returned true, iff the heuristic is defeated and not useful.
Definition: TrigramIndex.h:48
bool isDefinitelyOut(StringRef Query) const
Returns true, if special case list definitely does not have a line that matches the query.
void insert(const std::string &Regex)
Inserts a new Regex into the index.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18