Server : Apache/2.4.41 (Ubuntu) System : Linux absol.cf 5.4.0-198-generic #218-Ubuntu SMP Fri Sep 27 20:18:53 UTC 2024 x86_64 User : www-data ( 33) PHP Version : 7.4.33 Disable Function : pcntl_alarm,pcntl_fork,pcntl_waitpid,pcntl_wait,pcntl_wifexited,pcntl_wifstopped,pcntl_wifsignaled,pcntl_wifcontinued,pcntl_wexitstatus,pcntl_wtermsig,pcntl_wstopsig,pcntl_signal,pcntl_signal_get_handler,pcntl_signal_dispatch,pcntl_get_last_error,pcntl_strerror,pcntl_sigprocmask,pcntl_sigwaitinfo,pcntl_sigtimedwait,pcntl_exec,pcntl_getpriority,pcntl_setpriority,pcntl_async_signals,pcntl_unshare, Directory :  /usr/include/llvm-10/llvm/Support/

Upload File : current_dir [ Writeable ] document_root [ Writeable ]

//===-- TrigramIndex.h - a heuristic for SpecialCaseList --------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//===----------------------------------------------------------------------===//
//
// TrigramIndex implements a heuristic for SpecialCaseList that allows to
// filter out ~99% incoming queries when all regular expressions in the
// SpecialCaseList are simple wildcards with '*' and '.'. If rules are more
// complicated, the check is defeated and it will always pass the queries to a
// full regex.
//
// The basic idea is that in order for a wildcard to match a query, the query
// needs to have all trigrams which occur in the wildcard. We create a trigram
// index (trigram -> list of rules with it) and then count trigrams in the query
// for each rule. If the count for one of the rules reaches the expected value,
// the check passes the query to a regex. If none of the rules got enough
// trigrams, the check tells that the query is definitely not matched by any
// of the rules, and no regex matching is needed.
// A similar idea was used in Google Code Search as described in the blog post:
// https://swtch.com/~rsc/regexp/regexp4.html
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_SUPPORT_TRIGRAMINDEX_H
#define LLVM_SUPPORT_TRIGRAMINDEX_H

#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringMap.h"

#include <string>
#include <unordered_map>
#include <vector>

namespace llvm {
class StringRef;

class TrigramIndex {
 public:
  /// Inserts a new Regex into the index.
  void insert(std::string Regex);

  /// Returns true, if special case list definitely does not have a line
  /// that matches the query. Returns false, if it's not sure.
  bool isDefinitelyOut(StringRef Query) const;

  /// Returned true, iff the heuristic is defeated and not useful.
  /// In this case isDefinitelyOut always returns false.
  bool isDefeated() { return Defeated; }
 private:
  // If true, the rules are too complicated for the check to work, and full
  // regex matching is needed for every rule.
  bool Defeated = false;
  // The minimum number of trigrams which should match for a rule to have a
  // chance to match the query. The number of elements equals the number of
  // regex rules in the SpecialCaseList.
  std::vector<unsigned> Counts;
  // Index holds a list of rules indices for each trigram. The same indices
  // are used in Counts to store per-rule limits.
  // If a trigram is too common (>4 rules with it), we stop tracking it,
  // which increases the probability for a need to match using regex, but
  // decreases the costs in the regular case.
  std::unordered_map<unsigned, SmallVector<size_t, 4>> Index{256};
};

}  // namespace llvm

#endif  // LLVM_SUPPORT_TRIGRAMINDEX_H