lib/Support/TrigramIndex.cpp

   1 //===-- TrigramIndex.cpp - a heuristic for SpecialCaseList ----------------===//
   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 //
   9 // TrigramIndex implements a heuristic for SpecialCaseList that allows to
  10 // filter out ~99% incoming queries when all regular expressions in the
  11 // SpecialCaseList are simple wildcards with '*' and '.'. If rules are more
  12 // complicated, the check is defeated and it will always pass the queries to a
  13 // full regex.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Support/TrigramIndex.h"
  18 #include "llvm/ADT/SmallVector.h"
  19
  20 #include <set>
  21 #include <string>
  22 #include <unordered_map>
  23
  24 using namespace llvm;
  25
  26 static const char RegexAdvancedMetachars[] = "()^$|+?[]\\{}";
  27
  28 static bool isAdvancedMetachar(unsigned Char) {
  29   return strchr(RegexAdvancedMetachars, Char) != nullptr;
  30 }
  31
  32 void TrigramIndex::insert(std::string Regex) {
  33   if (Defeated) return;
  34   std::set<unsigned> Was;
  35   unsigned Cnt = 0;
  36   unsigned Tri = 0;
  37   unsigned Len = 0;
  38   bool Escaped = false;
  39   for (unsigned Char : Regex) {
  40     if (!Escaped) {
  41       // Regular expressions allow escaping symbols by preceding it with '\'.
  42       if (Char == '\\') {
  43         Escaped = true;
  44         continue;
  45       }
  46       if (isAdvancedMetachar(Char)) {
  47         // This is a more complicated regex than we can handle here.
  48         Defeated = true;
  49         return;
  50       }
  51       if (Char == '.' || Char == '*') {
  52         Tri = 0;
  53         Len = 0;
  54         continue;
  55       }
  56     }
  57     if (Escaped && Char >= '1' && Char <= '9') {
  58       Defeated = true;
  59       return;
  60     }
  61     // We have already handled escaping and can reset the flag.
  62     Escaped = false;
  63     Tri = ((Tri << 8) + Char) & 0xFFFFFF;
  64     Len++;
  65     if (Len < 3)
  66       continue;
  67     // We don't want the index to grow too much for the popular trigrams,
  68     // as they are weak signals. It's ok to still require them for the
  69     // rules we have already processed. It's just a small additional
  70     // computational cost.
  71     if (Index[Tri].size() >= 4)
  72       continue;
  73     Cnt++;
  74     if (!Was.count(Tri)) {
  75       // Adding the current rule to the index.
  76       Index[Tri].push_back(Counts.size());
  77       Was.insert(Tri);
  78     }
  79   }
  80   if (!Cnt) {
  81     // This rule does not have remarkable trigrams to rely on.
  82     // We have to always call the full regex chain.
  83     Defeated = true;
  84     return;
  85   }
  86   Counts.push_back(Cnt);
  87 }
  88
  89 bool TrigramIndex::isDefinitelyOut(StringRef Query) const {
  90   if (Defeated)
  91     return false;
  92   std::vector<unsigned> CurCounts(Counts.size());
  93   unsigned Tri = 0;
  94   for (size_t I = 0; I < Query.size(); I++) {
  95     Tri = ((Tri << 8) + Query[I]) & 0xFFFFFF;
  96     if (I < 2)
  97       continue;
  98     const auto &II = Index.find(Tri);
  99     if (II == Index.end())
 100       continue;
 101     for (size_t J : II->second) {
 102       CurCounts[J]++;
 103       // If we have reached a desired limit, we have to look at the query
 104       // more closely by running a full regex.
 105       if (CurCounts[J] >= Counts[J])
 106         return false;
 107     }
 108   }
 109   return true;
 110 }