blob: 08a8981865de5879bdfc745c95f31e75a4b1a45e [file] [log] [blame]
//===--- Quality.h - Ranking alternatives for ambiguous queries --*- C++-*-===//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
/// Some operations such as code completion produce a set of candidates.
/// Usually the user can choose between them, but we should put the best options
/// at the top (they're easier to select, and more likely to be seen).
/// This file defines building blocks for ranking candidates.
/// It's used by the features directly and also in the implementation of
/// indexes, as indexes also need to heuristically limit their results.
/// The facilities here are:
/// - retrieving scoring signals from e.g. indexes, AST, CodeCompletionString
/// These are structured in a way that they can be debugged, and are fairly
/// consistent regardless of the source.
/// - compute scores from scoring signals. These are suitable for sorting.
/// - sorting utilities like the TopN container.
/// These could be split up further to isolate dependencies if we care.
#include "ExpectedTypes.h"
#include "FileDistance.h"
#include "TUScheduler.h"
#include "clang/Sema/CodeCompleteConsumer.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/StringSet.h"
#include <algorithm>
#include <functional>
#include <vector>
namespace llvm {
class raw_ostream;
} // namespace llvm
namespace clang {
class CodeCompletionResult;
namespace clangd {
struct Symbol;
class URIDistance;
// Signals structs are designed to be aggregated from 0 or more sources.
// A default instance has neutral signals, and sources are merged into it.
// They can be dumped for debugging, and evaluate()d into a score.
/// Attributes of a symbol that affect how much we like it.
struct SymbolQualitySignals {
bool Deprecated = false;
bool ReservedName = false; // __foo, _Foo are usually implementation details.
// FIXME: make these findable once user types _.
bool ImplementationDetail = false;
unsigned References = 0;
enum SymbolCategory {
Unknown = 0,
} Category = Unknown;
void merge(const CodeCompletionResult &SemaCCResult);
void merge(const Symbol &IndexResult);
// Condense these signals down to a single number, higher is better.
float evaluateHeuristics() const;
llvm::raw_ostream &operator<<(llvm::raw_ostream &,
const SymbolQualitySignals &);
/// Attributes of a symbol-query pair that affect how much we like it.
struct SymbolRelevanceSignals {
/// The name of the symbol (for ContextWords). Must be explicitly assigned.
llvm::StringRef Name;
/// 0-1+ fuzzy-match score for unqualified name. Must be explicitly assigned.
float NameMatch = 1;
/// Lowercase words relevant to the context (e.g. near the completion point).
llvm::StringSet<>* ContextWords = nullptr;
bool Forbidden = false; // Unavailable (e.g const) or inaccessible (private).
/// Whether fixits needs to be applied for that completion or not.
bool NeedsFixIts = false;
bool InBaseClass = false; // A member from base class of the accessed class.
URIDistance *FileProximityMatch = nullptr;
/// These are used to calculate proximity between the index symbol and the
/// query.
llvm::StringRef SymbolURI;
/// FIXME: unify with index proximity score - signals should be
/// source-independent.
/// Proximity between best declaration and the query. [0-1], 1 is closest.
float SemaFileProximityScore = 0;
// Scope proximity is only considered (both index and sema) when this is set.
ScopeDistance *ScopeProximityMatch = nullptr;
llvm::Optional<llvm::StringRef> SymbolScope;
// A symbol from sema should be accessible from the current scope.
bool SemaSaysInScope = false;
// An approximate measure of where we expect the symbol to be used.
enum AccessibleScope {
} Scope = GlobalScope;
enum QueryType {
} Query = Generic;
CodeCompletionContext::Kind Context = CodeCompletionContext::CCC_Other;
// Whether symbol is an instance member of a class.
bool IsInstanceMember = false;
// Whether clang provided a preferred type in the completion context.
bool HadContextType = false;
// Whether a source completion item or a symbol had a type information.
bool HadSymbolType = false;
// Whether the item matches the type expected in the completion context.
bool TypeMatchesPreferred = false;
/// Length of the unqualified partial name of Symbol typed in
/// CompletionPrefix.
unsigned FilterLength = 0;
const ASTSignals *MainFileSignals = nullptr;
/// Number of references to the candidate in the main file.
unsigned MainFileRefs = 0;
/// Number of unique symbols in the main file which belongs to candidate's
/// namespace. This indicates how relevant the namespace is in the current
/// file.
unsigned ScopeRefsInFile = 0;
/// Set of derived signals computed by calculateDerivedSignals(). Must not be
/// set explicitly.
struct DerivedSignals {
/// Whether Name contains some word from context.
bool NameMatchesContext = false;
/// Min distance between SymbolURI and all the headers included by the TU.
unsigned FileProximityDistance = FileDistance::Unreachable;
/// Min distance between SymbolScope and all the available scopes.
unsigned ScopeProximityDistance = FileDistance::Unreachable;
DerivedSignals calculateDerivedSignals() const;
void merge(const CodeCompletionResult &SemaResult);
void merge(const Symbol &IndexResult);
void computeASTSignals(const CodeCompletionResult &SemaResult);
// Condense these signals down to a single number, higher is better.
float evaluateHeuristics() const;
llvm::raw_ostream &operator<<(llvm::raw_ostream &,
const SymbolRelevanceSignals &);
/// Combine symbol quality and relevance into a single score.
float evaluateSymbolAndRelevance(float SymbolQuality, float SymbolRelevance);
/// Same semantics as CodeComplete::Score. Quality score and Relevance score
/// have been removed since DecisionForest cannot assign individual scores to
/// Quality and Relevance signals.
struct DecisionForestScores {
float Total = 0.f;
float ExcludingName = 0.f;
evaluateDecisionForest(const SymbolQualitySignals &Quality,
const SymbolRelevanceSignals &Relevance, float Base);
/// TopN<T> is a lossy container that preserves only the "best" N elements.
template <typename T, typename Compare = std::greater<T>> class TopN {
using value_type = T;
TopN(size_t N, Compare Greater = Compare())
: N(N), Greater(std::move(Greater)) {}
// Adds a candidate to the set.
// Returns true if a candidate was dropped to get back under N.
bool push(value_type &&V) {
bool Dropped = false;
if (Heap.size() >= N) {
Dropped = true;
if (N > 0 && Greater(V, Heap.front())) {
std::pop_heap(Heap.begin(), Heap.end(), Greater);
Heap.back() = std::move(V);
std::push_heap(Heap.begin(), Heap.end(), Greater);
} else {
std::push_heap(Heap.begin(), Heap.end(), Greater);
assert(Heap.size() <= N);
assert(std::is_heap(Heap.begin(), Heap.end(), Greater));
return Dropped;
// Returns candidates from best to worst.
std::vector<value_type> items() && {
std::sort_heap(Heap.begin(), Heap.end(), Greater);
assert(Heap.size() <= N);
return std::move(Heap);
const size_t N;
std::vector<value_type> Heap; // Min-heap, comparator is Greater.
Compare Greater;
/// Returns a string that sorts in the same order as (-Score, Tiebreak), for
/// LSP. (The highest score compares smallest so it sorts at the top).
std::string sortText(float Score, llvm::StringRef Tiebreak = "");
struct SignatureQualitySignals {
uint32_t NumberOfParameters = 0;
uint32_t NumberOfOptionalParameters = 0;
CodeCompleteConsumer::OverloadCandidate::CandidateKind Kind =
llvm::raw_ostream &operator<<(llvm::raw_ostream &,
const SignatureQualitySignals &);
} // namespace clangd
} // namespace clang