lib/Support/TrigramIndex.cpp

   1 //===-- TrigramIndex.cpp - a heuristic for SpecialCaseList ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  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
  14 // full regex.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "llvm/Support/TrigramIndex.h"
  19 #include "llvm/ADT/SmallVector.h"
  20
  21 #include <set>
  22 #include <string>
  23 #include <unordered_map>
  24
  25 using namespace llvm;
  26
  27 static const char RegexAdvancedMetachars[] = "()^$|+?[]\\{}";
  28
  29 static bool isAdvancedMetachar(unsigned Char) {
  30   return strchr(RegexAdvancedMetachars, Char) != nullptr;
  31 }
  32
  33 void TrigramIndex::insert(std::string Regex) {
  34   if (Defeated) return;
  35   std::set<unsigned> Was;
  36   unsigned Cnt = 0;
  37   unsigned Tri = 0;
  38   unsigned Len = 0;
  39   bool Escaped = false;
  40   for (unsigned Char : Regex) {
  41     if (!Escaped) {
  42       // Regular expressions allow escaping symbols by preceding it with '\'.
  43       if (Char == '\\') {
  44         Escaped = true;
  45         continue;
  46       }
  47       if (isAdvancedMetachar(Char)) {
  48         // This is a more complicated regex than we can handle here.
  49         Defeated = true;
  50         return;
  51       }
  52       if (Char == '.' || Char == '*') {
  53         Tri = 0;
  54         Len = 0;
  55         continue;
  56       }
  57     }
  58     if (Escaped && Char >= '1' && Char <= '9') {
  59       Defeated = true;
  60       return;
  61     }
  62     // We have already handled escaping and can reset the flag.
  63     Escaped = false;
  64     Tri = ((Tri << 8) + Char) & 0xFFFFFF;
  65     Len++;
  66     if (Len < 3)
  67       continue;
  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)
  73       continue;
  74     Cnt++;
  75     if (!Was.count(Tri)) {
  76       // Adding the current rule to the index.
  77       Index[Tri].push_back(Counts.size());
  78       Was.insert(Tri);
  79     }
  80   }
  81   if (!Cnt) {
  82     // This rule does not have remarkable trigrams to rely on.
  83     // We have to always call the full regex chain.
  84     Defeated = true;
  85     return;
  86   }
  87   Counts.push_back(Cnt);
  88 }
  89
  90 bool TrigramIndex::isDefinitelyOut(StringRef Query) const {
  91   if (Defeated)
  92     return false;
  93   std::vector<unsigned> CurCounts(Counts.size());
  94   unsigned Tri = 0;
  95   for (size_t I = 0; I < Query.size(); I++) {
  96     Tri = ((Tri << 8) + Query[I]) & 0xFFFFFF;
  97     if (I < 2)
  98       continue;
  99     const auto &II = Index.find(Tri);
 100     if (II == Index.end())
 101       continue;
 102     for (size_t J : II->second) {
 103       CurCounts[J]++;
 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])
 107         return false;
 108     }
 109   }
 110   return true;
 111 }