clang-tools  10.0.0svn
Trigram.h
Go to the documentation of this file.
1 //===--- Trigram.h - Trigram generation for Fuzzy Matching ------*- C++ -*-===//
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 /// \file
10 /// Trigrams are attributes of the symbol unqualified name used to effectively
11 /// extract symbols which can be fuzzy-matched given user query from the
12 /// inverted index. To match query with the extracted set of trigrams Q, the set
13 /// of generated trigrams T for identifier (unqualified symbol name) should
14 /// contain all items of Q, i.e. Q ⊆ T.
15 ///
16 /// Trigram sets extracted from unqualified name and from query are different:
17 /// the set of query trigrams only contains consecutive sequences of three
18 /// characters (which is only a subset of all trigrams generated for an
19 /// identifier).
20 ///
21 //===----------------------------------------------------------------------===//
22 
23 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_DEX_TRIGRAM_H
24 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_DEX_TRIGRAM_H
25 
26 #include "Token.h"
27 
28 #include <string>
29 
30 namespace clang {
31 namespace clangd {
32 namespace dex {
33 
34 /// Returns list of unique fuzzy-search trigrams from unqualified symbol.
35 /// The trigrams give the 3-character query substrings this symbol can match.
36 ///
37 /// The symbol's name is broken into segments, e.g. "FooBar" has two segments.
38 /// Trigrams can start at any character in the input. Then we can choose to move
39 /// to the next character or to the start of the next segment.
40 ///
41 /// Short trigrams (length 1-2) are used for short queries. These are:
42 /// - prefixes of the identifier, of length 1 and 2
43 /// - the first character + next head character
44 ///
45 /// For "FooBar" we get the following trigrams:
46 /// {f, fo, fb, foo, fob, fba, oob, oba, bar}.
47 ///
48 /// Trigrams are lowercase, as trigram matching is case-insensitive.
49 /// Trigrams in the returned list are deduplicated.
50 std::vector<Token> generateIdentifierTrigrams(llvm::StringRef Identifier);
51 
52 /// Returns list of unique fuzzy-search trigrams given a query.
53 ///
54 /// Query is segmented using FuzzyMatch API and downcasted to lowercase. Then,
55 /// the simplest trigrams - sequences of three consecutive letters and digits
56 /// are extracted and returned after deduplication.
57 ///
58 /// For short queries (less than 3 characters with Head or Tail roles in Fuzzy
59 /// Matching segmentation) this returns a single trigram with the first
60 /// characters (up to 3) to perform prefix match.
61 std::vector<Token> generateQueryTrigrams(llvm::StringRef Query);
62 
63 } // namespace dex
64 } // namespace clangd
65 } // namespace clang
66 
67 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_DEX_TRIGRAM_H
std::vector< Token > generateIdentifierTrigrams(llvm::StringRef Identifier)
Returns list of unique fuzzy-search trigrams from unqualified symbol.
Definition: Trigram.cpp:23
std::vector< Token > generateQueryTrigrams(llvm::StringRef Query)
Returns list of unique fuzzy-search trigrams given a query.
Definition: Trigram.cpp:86
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Token objects represent a characteristic of a symbol, which can be used to perform efficient search...