1 //===-- TrigramIndex.cpp - a heuristic for SpecialCaseList ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // TrigramIndex implements a heuristic for SpecialCaseList that allows to
11 // filter out ~99% incoming queries when all regular expressions in the
12 // SpecialCaseList are simple wildcards with '*' and '.'. If rules are more
13 // complicated, the check is defeated and it will always pass the queries to a
16 //===----------------------------------------------------------------------===//
18 #include "llvm/Support/TrigramIndex.h"
19 #include "llvm/ADT/SmallVector.h"
21 #include <unordered_map>
27 static const char RegexAdvancedMetachars[] = "()^$|+?[]\\{}";
29 static bool isAdvancedMetachar(unsigned Char) {
30 return strchr(RegexAdvancedMetachars, Char) != nullptr;
33 void TrigramIndex::insert(std::string Regex) {
35 std::set<unsigned> Was;
40 for (unsigned Char : Regex) {
42 // Regular expressions allow escaping symbols by preceding it with '\'.
47 if (isAdvancedMetachar(Char)) {
48 // This is a more complicated regex than we can handle here.
52 if (Char == '.' || Char == '*') {
58 if (Escaped && Char >= '1' && Char <= '9') {
62 // We have already handled escaping and can reset the flag.
64 Tri = ((Tri << 8) + Char) & 0xFFFFFF;
68 // We don't want the index to grow too much for the popular trigrams,
69 // as they are weak signals. It's ok to still require them for the
70 // rules we have already processed. It's just a small additional
71 // computational cost.
72 if (Index[Tri].size() >= 4)
75 if (!Was.count(Tri)) {
76 // Adding the current rule to the index.
77 Index[Tri].push_back(Counts.size());
82 // This rule does not have remarkable trigrams to rely on.
83 // We have to always call the full regex chain.
87 Counts.push_back(Cnt);
90 bool TrigramIndex::isDefinitelyOut(StringRef Query) const {
93 std::vector<unsigned> CurCounts(Counts.size());
95 for (size_t I = 0; I < Query.size(); I++) {
96 Tri = ((Tri << 8) + Query[I]) & 0xFFFFFF;
99 const auto &II = Index.find(Tri);
100 if (II == Index.end())
102 for (size_t J : II->second) {
104 // If we have reached a desired limit, we have to look at the query
105 // more closely by running a full regex.
106 if (CurCounts[J] >= Counts[J])