//===--- Trigram.h - Trigram generation for Fuzzy Matching ------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Trigrams are attributes of the symbol unqualified name used to effectively
// extract symbols which can be fuzzy-matched given user query from the inverted
// index. To match query with the extracted set of trigrams Q, the set of
// generated trigrams T for identifier (unqualified symbol name) should contain
// all items of Q, i.e. Q ⊆ T.
//
// Trigram sets extracted from unqualified name and from query are different:
// the set of query trigrams only contains consecutive sequences of three
// characters (which is only a subset of all trigrams generated for an
// identifier).
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_DEX_TRIGRAM_H
#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_DEX_TRIGRAM_H

#include "Token.h"

#include <string>

namespace clang {
namespace clangd {
namespace dex {

/// Returns list of unique fuzzy-search trigrams from unqualified symbol.
///
/// First, given Identifier (unqualified symbol name) is segmented using
/// FuzzyMatch API and lowercased. After segmentation, the following technique
/// is applied for generating trigrams: for each letter or digit in the input
/// string the algorithms looks for the possible next and skip-1-next symbols
/// which can be jumped to during fuzzy matching. Each combination of such three
/// symbols is inserted into the result.
///
/// Trigrams can start at any character in the input. Then we can choose to move
/// to the next character, move to the start of the next segment, or skip over a
/// segment.
///
/// Note: the returned list of trigrams does not have duplicates, if any trigram
/// belongs to more than one class it is only inserted once.
std::vector<Token> generateIdentifierTrigrams(llvm::StringRef Identifier);

/// Returns list of unique fuzzy-search trigrams given a query.
///
/// Query is segmented using FuzzyMatch API and downcasted to lowercase. Then,
/// the simplest trigrams - sequences of three consecutive letters and digits
/// are extracted and returned after deduplication.
std::vector<Token> generateQueryTrigrams(llvm::StringRef Query);

} // namespace dex
} // namespace clangd
} // namespace clang

#endif