1	//===--- CodeComplete.cpp ----------------------------------------*- 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	// Code completion has several moving parts:
10	// - AST-based completions are provided using the completion hooks in Sema.
11	// - external completions are retrieved from the index (using hints from Sema)
12	// - the two sources overlap, and must be merged and overloads bundled
13	// - results must be scored and ranked (see Quality.h) before rendering
14	//
15	// Signature help works in a similar way as code completion, but it is simpler:
16	// it's purely AST-based, and there are few candidates.
17	//
18	//===----------------------------------------------------------------------===//
19
20	#include "CodeComplete.h"
21	#include "AST.h"
22	#include "CodeCompletionStrings.h"
23	#include "Compiler.h"
24	#include "Config.h"
25	#include "ExpectedTypes.h"
26	#include "Feature.h"
27	#include "FileDistance.h"
28	#include "FuzzyMatch.h"
29	#include "Headers.h"
30	#include "Hover.h"
31	#include "Preamble.h"
32	#include "Protocol.h"
33	#include "Quality.h"
34	#include "SourceCode.h"
35	#include "URI.h"
36	#include "index/Index.h"
37	#include "index/Symbol.h"
38	#include "index/SymbolOrigin.h"
39	#include "support/Logger.h"
40	#include "support/Markup.h"
41	#include "support/Threading.h"
42	#include "support/ThreadsafeFS.h"
43	#include "support/Trace.h"
44	#include "clang/AST/Decl.h"
45	#include "clang/AST/DeclBase.h"
46	#include "clang/Basic/CharInfo.h"
47	#include "clang/Basic/LangOptions.h"
48	#include "clang/Basic/SourceLocation.h"
49	#include "clang/Basic/TokenKinds.h"
50	#include "clang/Format/Format.h"
51	#include "clang/Frontend/CompilerInstance.h"
52	#include "clang/Frontend/FrontendActions.h"
53	#include "clang/Lex/ExternalPreprocessorSource.h"
54	#include "clang/Lex/Lexer.h"
55	#include "clang/Lex/Preprocessor.h"
56	#include "clang/Lex/PreprocessorOptions.h"
57	#include "clang/Sema/CodeCompleteConsumer.h"
58	#include "clang/Sema/DeclSpec.h"
59	#include "clang/Sema/Sema.h"
60	#include "llvm/ADT/ArrayRef.h"
61	#include "llvm/ADT/SmallVector.h"
62	#include "llvm/ADT/StringExtras.h"
63	#include "llvm/ADT/StringRef.h"
64	#include "llvm/Support/Casting.h"
65	#include "llvm/Support/Compiler.h"
66	#include "llvm/Support/Debug.h"
67	#include "llvm/Support/Error.h"
68	#include "llvm/Support/FormatVariadic.h"
69	#include "llvm/Support/ScopedPrinter.h"
70	#include <algorithm>
71	#include <iterator>
72	#include <limits>
73	#include <optional>
74	#include <utility>
75
76	// We log detailed candidate here if you run with -debug-only=codecomplete.
77	#define DEBUG_TYPE "CodeComplete"
78
79	namespace clang {
80	namespace clangd {
81
82	#if CLANGD_DECISION_FOREST
83	const CodeCompleteOptions::CodeCompletionRankingModel
84	CodeCompleteOptions::DefaultRankingModel =
85	CodeCompleteOptions::DecisionForest;
86	#else
87	const CodeCompleteOptions::CodeCompletionRankingModel
88	CodeCompleteOptions::DefaultRankingModel = CodeCompleteOptions::Heuristics;
89	#endif
90
91	namespace {
92
93	// Note: changes to this function should also be reflected in the
94	// CodeCompletionResult overload where appropriate.
95	CompletionItemKind
96	toCompletionItemKind(index::SymbolKind Kind,
97	const llvm::StringRef *Signature = nullptr) {
98	using SK = index::SymbolKind;
99	switch (Kind) {
100	case SK::Unknown:
101	return CompletionItemKind::Missing;
102	case SK::Module:
103	case SK::Namespace:
104	case SK::NamespaceAlias:
105	return CompletionItemKind::Module;
106	case SK::Macro:
107	// Use macro signature (if provided) to tell apart function-like and
108	// object-like macros.
109	return Signature && Signature->contains(C: '(') ? CompletionItemKind::Function
110	: CompletionItemKind::Constant;
111	case SK::Enum:
112	return CompletionItemKind::Enum;
113	case SK::Struct:
114	return CompletionItemKind::Struct;
115	case SK::Class:
116	case SK::Extension:
117	case SK::Union:
118	return CompletionItemKind::Class;
119	case SK::Protocol:
120	// Use interface instead of class for differentiation of classes and
121	// protocols with the same name (e.g. @interface NSObject vs. @protocol
122	// NSObject).
123	return CompletionItemKind::Interface;
124	case SK::TypeAlias:
125	// We use the same kind as the VSCode C++ extension.
126	// FIXME: pick a better option when we have one.
127	return CompletionItemKind::Interface;
128	case SK::Using:
129	return CompletionItemKind::Reference;
130	case SK::Function:
131	case SK::ConversionFunction:
132	return CompletionItemKind::Function;
133	case SK::Variable:
134	case SK::Parameter:
135	case SK::NonTypeTemplateParm:
136	return CompletionItemKind::Variable;
137	case SK::Field:
138	return CompletionItemKind::Field;
139	case SK::EnumConstant:
140	return CompletionItemKind::EnumMember;
141	case SK::InstanceMethod:
142	case SK::ClassMethod:
143	case SK::StaticMethod:
144	case SK::Destructor:
145	return CompletionItemKind::Method;
146	case SK::InstanceProperty:
147	case SK::ClassProperty:
148	case SK::StaticProperty:
149	return CompletionItemKind::Property;
150	case SK::Constructor:
151	return CompletionItemKind::Constructor;
152	case SK::TemplateTypeParm:
153	case SK::TemplateTemplateParm:
154	return CompletionItemKind::TypeParameter;
155	case SK::Concept:
156	return CompletionItemKind::Interface;
157	}
158	llvm_unreachable("Unhandled clang::index::SymbolKind.");
159	}
160
161	// Note: changes to this function should also be reflected in the
162	// index::SymbolKind overload where appropriate.
163	CompletionItemKind toCompletionItemKind(const CodeCompletionResult &Res,
164	CodeCompletionContext::Kind CtxKind) {
165	if (Res.Declaration)
166	return toCompletionItemKind(index::getSymbolInfo(Res.Declaration).Kind);
167	if (CtxKind == CodeCompletionContext::CCC_IncludedFile)
168	return CompletionItemKind::File;
169	switch (Res.Kind) {
170	case CodeCompletionResult::RK_Declaration:
171	llvm_unreachable("RK_Declaration without Decl");
172	case CodeCompletionResult::RK_Keyword:
173	return CompletionItemKind::Keyword;
174	case CodeCompletionResult::RK_Macro:
175	// There is no 'Macro' kind in LSP.
176	// Avoid using 'Text' to avoid confusion with client-side word-based
177	// completion proposals.
178	return Res.MacroDefInfo && Res.MacroDefInfo->isFunctionLike()
179	? CompletionItemKind::Function
180	: CompletionItemKind::Constant;
181	case CodeCompletionResult::RK_Pattern:
182	return CompletionItemKind::Snippet;
183	}
184	llvm_unreachable("Unhandled CodeCompletionResult::ResultKind.");
185	}
186
187	// FIXME: find a home for this (that can depend on both markup and Protocol).
188	MarkupContent renderDoc(const markup::Document &Doc, MarkupKind Kind) {
189	MarkupContent Result;
190	Result.kind = Kind;
191	switch (Kind) {
192	case MarkupKind::PlainText:
193	Result.value.append(str: Doc.asPlainText());
194	break;
195	case MarkupKind::Markdown:
196	Result.value.append(str: Doc.asMarkdown());
197	break;
198	}
199	return Result;
200	}
201
202	Symbol::IncludeDirective insertionDirective(const CodeCompleteOptions &Opts) {
203	if (!Opts.ImportInsertions || !Opts.MainFileSignals)
204	return Symbol::IncludeDirective::Include;
205	return Opts.MainFileSignals->InsertionDirective;
206	}
207
208	// Identifier code completion result.
209	struct RawIdentifier {
210	llvm::StringRef Name;
211	unsigned References; // # of usages in file.
212	};
213
214	/// A code completion result, in clang-native form.
215	/// It may be promoted to a CompletionItem if it's among the top-ranked results.
216	struct CompletionCandidate {
217	llvm::StringRef Name; // Used for filtering and sorting.
218	// We may have a result from Sema, from the index, or both.
219	const CodeCompletionResult *SemaResult = nullptr;
220	const Symbol *IndexResult = nullptr;
221	const RawIdentifier *IdentifierResult = nullptr;
222	llvm::SmallVector<SymbolInclude, 1> RankedIncludeHeaders;
223
224	// Returns a token identifying the overload set this is part of.
225	// 0 indicates it's not part of any overload set.
226	size_t overloadSet(const CodeCompleteOptions &Opts, llvm::StringRef FileName,
227	IncludeInserter *Inserter,
228	CodeCompletionContext::Kind CCContextKind) const {
229	if (!Opts.BundleOverloads.value_or(u: false))
230	return 0;
231
232	// Depending on the index implementation, we can see different header
233	// strings (literal or URI) mapping to the same file. We still want to
234	// bundle those, so we must resolve the header to be included here.
235	std::string HeaderForHash;
236	if (Inserter) {
237	if (auto Header = headerToInsertIfAllowed(Opts, ContextKind: CCContextKind)) {
238	if (auto HeaderFile = toHeaderFile(Header: *Header, HintPath: FileName)) {
239	if (auto Spelled =
240	Inserter->calculateIncludePath(InsertedHeader: *HeaderFile, IncludingFile: FileName))
241	HeaderForHash = *Spelled;
242	} else {
243	vlog(Fmt: "Code completion header path manipulation failed {0}",
244	Vals: HeaderFile.takeError());
245	}
246	}
247	}
248
249	llvm::SmallString<256> Scratch;
250	if (IndexResult) {
251	switch (IndexResult->SymInfo.Kind) {
252	case index::SymbolKind::ClassMethod:
253	case index::SymbolKind::InstanceMethod:
254	case index::SymbolKind::StaticMethod:
255	#ifndef NDEBUG
256	llvm_unreachable("Don't expect members from index in code completion");
257	#else
258	[[fallthrough]];
259	#endif
260	case index::SymbolKind::Function:
261	// We can't group overloads together that need different #includes.
262	// This could break #include insertion.
263	return llvm::hash_combine(
264	args: (IndexResult->Scope + IndexResult->Name).toStringRef(Out&: Scratch),
265	args: HeaderForHash);
266	default:
267	return 0;
268	}
269	}
270	if (SemaResult) {
271	// We need to make sure we're consistent with the IndexResult case!
272	const NamedDecl *D = SemaResult->Declaration;
273	if (!D || !D->isFunctionOrFunctionTemplate())
274	return 0;
275	{
276	llvm::raw_svector_ostream OS(Scratch);
277	D->printQualifiedName(OS);
278	}
279	return llvm::hash_combine(args: Scratch, args: HeaderForHash);
280	}
281	assert(IdentifierResult);
282	return 0;
283	}
284
285	bool contextAllowsHeaderInsertion(CodeCompletionContext::Kind Kind) const {
286	// Explicitly disable insertions for forward declarations since they don't
287	// reference the declaration.
288	if (Kind == CodeCompletionContext::CCC_ObjCClassForwardDecl)
289	return false;
290	return true;
291	}
292
293	// The best header to include if include insertion is allowed.
294	std::optional<llvm::StringRef>
295	headerToInsertIfAllowed(const CodeCompleteOptions &Opts,
296	CodeCompletionContext::Kind ContextKind) const {
297	if (Opts.InsertIncludes == Config::HeaderInsertionPolicy::NeverInsert ||
298	RankedIncludeHeaders.empty() ||
299	!contextAllowsHeaderInsertion(Kind: ContextKind))
300	return std::nullopt;
301	if (SemaResult && SemaResult->Declaration) {
302	// Avoid inserting new #include if the declaration is found in the current
303	// file e.g. the symbol is forward declared.
304	auto &SM = SemaResult->Declaration->getASTContext().getSourceManager();
305	for (const Decl *RD : SemaResult->Declaration->redecls())
306	if (SM.isInMainFile(SM.getExpansionLoc(RD->getBeginLoc())))
307	return std::nullopt;
308	}
309	Symbol::IncludeDirective Directive = insertionDirective(Opts);
310	for (const auto &Inc : RankedIncludeHeaders)
311	if ((Inc.Directive & Directive) != 0)
312	return Inc.Header;
313	return std::nullopt;
314	}
315
316	using Bundle = llvm::SmallVector<CompletionCandidate, 4>;
317	};
318	using ScoredBundle =
319	std::pair<CompletionCandidate::Bundle, CodeCompletion::Scores>;
320	struct ScoredBundleGreater {
321	bool operator()(const ScoredBundle &L, const ScoredBundle &R) {
322	if (L.second.Total != R.second.Total)
323	return L.second.Total > R.second.Total;
324	return L.first.front().Name <
325	R.first.front().Name; // Earlier name is better.
326	}
327	};
328
329	// Remove the first template argument from Signature.
330	// If Signature only contains a single argument an empty string is returned.
331	std::string removeFirstTemplateArg(llvm::StringRef Signature) {
332	auto Rest = Signature.split(Separator: ",").second;
333	if (Rest.empty())
334	return "";
335	return ("<" + Rest.ltrim()).str();
336	}
337
338	// Assembles a code completion out of a bundle of >=1 completion candidates.
339	// Many of the expensive strings are only computed at this point, once we know
340	// the candidate bundle is going to be returned.
341	//
342	// Many fields are the same for all candidates in a bundle (e.g. name), and are
343	// computed from the first candidate, in the constructor.
344	// Others vary per candidate, so add() must be called for remaining candidates.
345	struct CodeCompletionBuilder {
346	CodeCompletionBuilder(ASTContext *ASTCtx, const CompletionCandidate &C,
347	CodeCompletionString *SemaCCS,
348	llvm::ArrayRef<std::string> AccessibleScopes,
349	const IncludeInserter &Includes,
350	llvm::StringRef FileName,
351	CodeCompletionContext::Kind ContextKind,
352	const CodeCompleteOptions &Opts,
353	bool IsUsingDeclaration, tok::TokenKind NextTokenKind)
354	: ASTCtx(ASTCtx), ArgumentLists(Opts.ArgumentLists),
355	IsUsingDeclaration(IsUsingDeclaration), NextTokenKind(NextTokenKind) {
356	Completion.Deprecated = true; // cleared by any non-deprecated overload.
357	add(C, SemaCCS, ContextKind);
358	if (C.SemaResult) {
359	assert(ASTCtx);
360	Completion.Origin |= SymbolOrigin::AST;
361	Completion.Name = std::string(llvm::StringRef(SemaCCS->getTypedText()));
362	Completion.FilterText = SemaCCS->getAllTypedText();
363	if (Completion.Scope.empty()) {
364	if ((C.SemaResult->Kind == CodeCompletionResult::RK_Declaration) ||
365	(C.SemaResult->Kind == CodeCompletionResult::RK_Pattern))
366	if (const auto *D = C.SemaResult->getDeclaration())
367	if (const auto *ND = dyn_cast<NamedDecl>(Val: D))
368	Completion.Scope = std::string(
369	splitQualifiedName(QName: printQualifiedName(ND: *ND)).first);
370	}
371	Completion.Kind = toCompletionItemKind(Res: *C.SemaResult, CtxKind: ContextKind);
372	// Sema could provide more info on whether the completion was a file or
373	// folder.
374	if (Completion.Kind == CompletionItemKind::File &&
375	Completion.Name.back() == '/')
376	Completion.Kind = CompletionItemKind::Folder;
377	for (const auto &FixIt : C.SemaResult->FixIts) {
378	Completion.FixIts.push_back(x: toTextEdit(
379	FixIt, M: ASTCtx->getSourceManager(), L: ASTCtx->getLangOpts()));
380	}
381	llvm::sort(C&: Completion.FixIts, Comp: [](const TextEdit &X, const TextEdit &Y) {
382	return std::tie(args: X.range.start.line, args: X.range.start.character) <
383	std::tie(args: Y.range.start.line, args: Y.range.start.character);
384	});
385	}
386	if (C.IndexResult) {
387	Completion.Origin |= C.IndexResult->Origin;
388	if (Completion.Scope.empty())
389	Completion.Scope = std::string(C.IndexResult->Scope);
390	if (Completion.Kind == CompletionItemKind::Missing)
391	Completion.Kind = toCompletionItemKind(Kind: C.IndexResult->SymInfo.Kind,
392	Signature: &C.IndexResult->Signature);
393	if (Completion.Name.empty())
394	Completion.Name = std::string(C.IndexResult->Name);
395	if (Completion.FilterText.empty())
396	Completion.FilterText = Completion.Name;
397	// If the completion was visible to Sema, no qualifier is needed. This
398	// avoids unneeded qualifiers in cases like with `using ns::X`.
399	if (Completion.RequiredQualifier.empty() && !C.SemaResult) {
400	llvm::StringRef ShortestQualifier = C.IndexResult->Scope;
401	for (llvm::StringRef Scope : AccessibleScopes) {
402	llvm::StringRef Qualifier = C.IndexResult->Scope;
403	if (Qualifier.consume_front(Prefix: Scope) &&
404	Qualifier.size() < ShortestQualifier.size())
405	ShortestQualifier = Qualifier;
406	}
407	Completion.RequiredQualifier = std::string(ShortestQualifier);
408	}
409	}
410	if (C.IdentifierResult) {
411	Completion.Origin |= SymbolOrigin::Identifier;
412	Completion.Kind = CompletionItemKind::Text;
413	Completion.Name = std::string(C.IdentifierResult->Name);
414	Completion.FilterText = Completion.Name;
415	}
416
417	// Turn absolute path into a literal string that can be #included.
418	auto Inserted = [&](llvm::StringRef Header)
419	-> llvm::Expected<std::pair<std::string, bool>> {
420	auto ResolvedDeclaring =
421	URI::resolve(FileURI: C.IndexResult->CanonicalDeclaration.FileURI, HintPath: FileName);
422	if (!ResolvedDeclaring)
423	return ResolvedDeclaring.takeError();
424	auto ResolvedInserted = toHeaderFile(Header, HintPath: FileName);
425	if (!ResolvedInserted)
426	return ResolvedInserted.takeError();
427	auto Spelled = Includes.calculateIncludePath(InsertedHeader: *ResolvedInserted, IncludingFile: FileName);
428	if (!Spelled)
429	return error(Fmt: "Header not on include path");
430	return std::make_pair(
431	x: std::move(*Spelled),
432	y: Includes.shouldInsertInclude(DeclaringHeader: *ResolvedDeclaring, InsertedHeader: *ResolvedInserted));
433	};
434	bool ShouldInsert =
435	C.headerToInsertIfAllowed(Opts, ContextKind).has_value();
436	Symbol::IncludeDirective Directive = insertionDirective(Opts);
437	// Calculate include paths and edits for all possible headers.
438	for (const auto &Inc : C.RankedIncludeHeaders) {
439	if ((Inc.Directive & Directive) == 0)
440	continue;
441
442	if (auto ToInclude = Inserted(Inc.Header)) {
443	CodeCompletion::IncludeCandidate Include;
444	Include.Header = ToInclude->first;
445	if (ToInclude->second && ShouldInsert)
446	Include.Insertion = Includes.insert(
447	VerbatimHeader: ToInclude->first, Directive: Directive == Symbol::Import
448	? tooling::IncludeDirective::Import
449	: tooling::IncludeDirective::Include);
450	Completion.Includes.push_back(Elt: std::move(Include));
451	} else
452	log(Fmt: "Failed to generate include insertion edits for adding header "
453	"(FileURI='{0}', IncludeHeader='{1}') into {2}: {3}",
454	Vals: C.IndexResult->CanonicalDeclaration.FileURI, Vals: Inc.Header, Vals&: FileName,
455	Vals: ToInclude.takeError());
456	}
457	// Prefer includes that do not need edits (i.e. already exist).
458	std::stable_partition(first: Completion.Includes.begin(),
459	last: Completion.Includes.end(),
460	pred: [](const CodeCompletion::IncludeCandidate &I) {
461	return !I.Insertion.has_value();
462	});
463	}
464
465	void add(const CompletionCandidate &C, CodeCompletionString *SemaCCS,
466	CodeCompletionContext::Kind ContextKind) {
467	assert(bool(C.SemaResult) == bool(SemaCCS));
468	Bundled.emplace_back();
469	BundledEntry &S = Bundled.back();
470	bool IsConcept = false;
471	if (C.SemaResult) {
472	getSignature(CCS: *SemaCCS, Signature: &S.Signature, Snippet: &S.SnippetSuffix, ResultKind: C.SemaResult->Kind,
473	CursorKind: C.SemaResult->CursorKind,
474	/*IncludeFunctionArguments=*/C.SemaResult->FunctionCanBeCall,
475	/*RequiredQualifiers=*/&Completion.RequiredQualifier);
476	S.ReturnType = getReturnType(CCS: *SemaCCS);
477	if (C.SemaResult->Kind == CodeCompletionResult::RK_Declaration)
478	if (const auto *D = C.SemaResult->getDeclaration())
479	if (isa<ConceptDecl>(Val: D))
480	IsConcept = true;
481	} else if (C.IndexResult) {
482	S.Signature = std::string(C.IndexResult->Signature);
483	S.SnippetSuffix = std::string(C.IndexResult->CompletionSnippetSuffix);
484	S.ReturnType = std::string(C.IndexResult->ReturnType);
485	if (C.IndexResult->SymInfo.Kind == index::SymbolKind::Concept)
486	IsConcept = true;
487	}
488
489	/// When a concept is used as a type-constraint (e.g. `Iterator auto x`),
490	/// and in some other contexts, its first type argument is not written.
491	/// Drop the parameter from the signature.
492	if (IsConcept && ContextKind == CodeCompletionContext::CCC_TopLevel) {
493	S.Signature = removeFirstTemplateArg(Signature: S.Signature);
494	// Dropping the first placeholder from the suffix will leave a $2
495	// with no $1.
496	S.SnippetSuffix = removeFirstTemplateArg(Signature: S.SnippetSuffix);
497	}
498
499	if (!Completion.Documentation) {
500	auto SetDoc = [&](llvm::StringRef Doc) {
501	if (!Doc.empty()) {
502	Completion.Documentation.emplace();
503	parseDocumentation(Input: Doc, Output&: *Completion.Documentation);
504	}
505	};
506	if (C.IndexResult) {
507	SetDoc(C.IndexResult->Documentation);
508	} else if (C.SemaResult) {
509	const auto DocComment = getDocComment(Ctx: *ASTCtx, Result: *C.SemaResult,
510	/*CommentsFromHeaders=*/false);
511	SetDoc(formatDocumentation(CCS: *SemaCCS, DocComment));
512	}
513	}
514	if (Completion.Deprecated) {
515	if (C.SemaResult)
516	Completion.Deprecated &=
517	C.SemaResult->Availability == CXAvailability_Deprecated;
518	if (C.IndexResult)
519	Completion.Deprecated &=
520	bool(C.IndexResult->Flags & Symbol::Deprecated);
521	}
522	}
523
524	CodeCompletion build() {
525	Completion.ReturnType = summarizeReturnType();
526	Completion.Signature = summarizeSignature();
527	Completion.SnippetSuffix = summarizeSnippet();
528	Completion.BundleSize = Bundled.size();
529	return std::move(Completion);
530	}
531
532	private:
533	struct BundledEntry {
534	std::string SnippetSuffix;
535	std::string Signature;
536	std::string ReturnType;
537	};
538
539	// If all BundledEntries have the same value for a property, return it.
540	template <std::string BundledEntry::*Member>
541	const std::string *onlyValue() const {
542	auto B = Bundled.begin(), E = Bundled.end();
543	for (auto *I = B + 1; I != E; ++I)
544	if (I->*Member != B->*Member)
545	return nullptr;
546	return &(B->*Member);
547	}
548
549	template <bool BundledEntry::*Member> const bool *onlyValue() const {
550	auto B = Bundled.begin(), E = Bundled.end();
551	for (auto *I = B + 1; I != E; ++I)
552	if (I->*Member != B->*Member)
553	return nullptr;
554	return &(B->*Member);
555	}
556
557	std::string summarizeReturnType() const {
558	if (auto *RT = onlyValue<&BundledEntry::ReturnType>())
559	return *RT;
560	return "";
561	}
562
563	std::string summarizeSnippet() const {
564	/// localize ArgumentLists tests for better readability
565	const bool None = ArgumentLists == Config::ArgumentListsPolicy::None;
566	const bool Open =
567	ArgumentLists == Config::ArgumentListsPolicy::OpenDelimiter;
568	const bool Delim = ArgumentLists == Config::ArgumentListsPolicy::Delimiters;
569	const bool Full =
570	ArgumentLists == Config::ArgumentListsPolicy::FullPlaceholders ||
571	(!None && !Open && !Delim); // <-- failsafe: Full is default
572
573	if (IsUsingDeclaration)
574	return "";
575	auto *Snippet = onlyValue<&BundledEntry::SnippetSuffix>();
576	if (!Snippet)
577	// All bundles are function calls.
578	// FIXME(ibiryukov): sometimes add template arguments to a snippet, e.g.
579	// we need to complete 'forward<$1>($0)'.
580	return None ? "" : (Open ? "(" : "($0)");
581
582	if (Snippet->empty())
583	return "";
584
585	bool MayHaveArgList = Completion.Kind == CompletionItemKind::Function ||
586	Completion.Kind == CompletionItemKind::Method ||
587	Completion.Kind == CompletionItemKind::Constructor ||
588	Completion.Kind == CompletionItemKind::Text /*Macro*/;
589	// If likely arg list already exists, don't add new parens & placeholders.
590	// Snippet: function(int x, int y)
591	// func^(1,2) -> function(1, 2)
592	// NOT function(int x, int y)(1, 2)
593	if (MayHaveArgList) {
594	// Check for a template argument list in the code.
595	// Snippet: function<class T>(int x)
596	// fu^<int>(1) -> function<int>(1)
597	if (NextTokenKind == tok::less && Snippet->front() == '<')
598	return "";
599	// Potentially followed by regular argument list.
600	if (NextTokenKind == tok::l_paren) {
601	// Snippet: function<class T>(int x)
602	// fu^(1,2) -> function<class T>(1, 2)
603	if (Snippet->front() == '<') {
604	// Find matching '>', handling nested brackets.
605	int Balance = 0;
606	size_t I = 0;
607	do {
608	if (Snippet->at(n: I) == '>')
609	--Balance;
610	else if (Snippet->at(n: I) == '<')
611	++Balance;
612	++I;
613	} while (Balance > 0);
614	return Snippet->substr(pos: 0, n: I);
615	}
616	return "";
617	}
618	}
619	if (Full)
620	return *Snippet;
621
622	// Replace argument snippets with a simplified pattern.
623	if (MayHaveArgList) {
624	// Functions snippets can be of 2 types:
625	// - containing only function arguments, e.g.
626	// foo(${1:int p1}, ${2:int p2});
627	// We transform this pattern to '($0)' or '()'.
628	// - template arguments and function arguments, e.g.
629	// foo<${1:class}>(${2:int p1}).
630	// We transform this pattern to '<$1>()$0' or '<$0>()'.
631
632	bool EmptyArgs = llvm::StringRef(*Snippet).ends_with(Suffix: "()");
633	if (Snippet->front() == '<')
634	return None ? "" : (Open ? "<" : (EmptyArgs ? "<$1>()$0" : "<$1>($0)"));
635	if (Snippet->front() == '(')
636	return None ? "" : (Open ? "(" : (EmptyArgs ? "()" : "($0)"));
637	return *Snippet; // Not an arg snippet?
638	}
639	// 'CompletionItemKind::Interface' matches template type aliases.
640	if (Completion.Kind == CompletionItemKind::Interface ||
641	Completion.Kind == CompletionItemKind::Class ||
642	Completion.Kind == CompletionItemKind::Variable) {
643	if (Snippet->front() != '<')
644	return *Snippet; // Not an arg snippet?
645
646	// Classes and template using aliases can only have template arguments,
647	// e.g. Foo<${1:class}>.
648	if (llvm::StringRef(*Snippet).ends_with(Suffix: "<>"))
649	return "<>"; // can happen with defaulted template arguments.
650	return None ? "" : (Open ? "<" : "<$0>");
651	}
652	return *Snippet;
653	}
654
655	std::string summarizeSignature() const {
656	if (auto *Signature = onlyValue<&BundledEntry::Signature>())
657	return *Signature;
658	// All bundles are function calls.
659	return "(…)";
660	}
661
662	// ASTCtx can be nullptr if not run with sema.
663	ASTContext *ASTCtx;
664	CodeCompletion Completion;
665	llvm::SmallVector<BundledEntry, 1> Bundled;
666	/// the way argument lists are handled.
667	Config::ArgumentListsPolicy ArgumentLists;
668	// No snippets will be generated for using declarations and when the function
669	// arguments are already present.
670	bool IsUsingDeclaration;
671	tok::TokenKind NextTokenKind;
672	};
673
674	// Determine the symbol ID for a Sema code completion result, if possible.
675	SymbolID getSymbolID(const CodeCompletionResult &R, const SourceManager &SM) {
676	switch (R.Kind) {
677	case CodeCompletionResult::RK_Declaration:
678	case CodeCompletionResult::RK_Pattern: {
679	// Computing USR caches linkage, which may change after code completion.
680	if (hasUnstableLinkage(R.Declaration))
681	return {};
682	return clang::clangd::getSymbolID(R.Declaration);
683	}
684	case CodeCompletionResult::RK_Macro:
685	return clang::clangd::getSymbolID(MacroName: R.Macro->getName(), MI: R.MacroDefInfo, SM);
686	case CodeCompletionResult::RK_Keyword:
687	return {};
688	}
689	llvm_unreachable("unknown CodeCompletionResult kind");
690	}
691
692	// Scopes of the partial identifier we're trying to complete.
693	// It is used when we query the index for more completion results.
694	struct SpecifiedScope {
695	// The scopes we should look in, determined by Sema.
696	//
697	// If the qualifier was fully resolved, we look for completions in these
698	// scopes; if there is an unresolved part of the qualifier, it should be
699	// resolved within these scopes.
700	//
701	// Examples of qualified completion:
702	//
703	// "::vec" => {""}
704	// "using namespace std; ::vec^" => {"", "std::"}
705	// "namespace ns {using namespace std;} ns::^" => {"ns::", "std::"}
706	// "std::vec^" => {""} // "std" unresolved
707	//
708	// Examples of unqualified completion:
709	//
710	// "vec^" => {""}
711	// "using namespace std; vec^" => {"", "std::"}
712	// "namespace ns {inline namespace ni { struct Foo {}}}
713	// using namespace ns::ni; Fo^ " => {"", "ns::ni::"}
714	// "using namespace std; namespace ns { vec^ }" => {"ns::", "std::", ""}
715	//
716	// "" for global namespace, "ns::" for normal namespace.
717	std::vector<std::string> AccessibleScopes;
718	// This is an overestimate of AccessibleScopes, e.g. it ignores inline
719	// namespaces, to fetch more relevant symbols from index.
720	std::vector<std::string> QueryScopes;
721	// The full scope qualifier as typed by the user (without the leading "::").
722	// Set if the qualifier is not fully resolved by Sema.
723	std::optional<std::string> UnresolvedQualifier;
724
725	std::optional<std::string> EnclosingNamespace;
726
727	bool AllowAllScopes = false;
728
729	// Scopes that are accessible from current context. Used for dropping
730	// unnecessary namespecifiers.
731	std::vector<std::string> scopesForQualification() {
732	std::set<std::string> Results;
733	for (llvm::StringRef AS : AccessibleScopes)
734	Results.insert(
735	x: (AS + (UnresolvedQualifier ? *UnresolvedQualifier : "")).str());
736	return {Results.begin(), Results.end()};
737	}
738
739	// Construct scopes being queried in indexes. The results are deduplicated.
740	// This method formats the scopes to match the index request representation.
741	std::vector<std::string> scopesForIndexQuery() {
742	// The enclosing namespace must be first, it gets a quality boost.
743	std::vector<std::string> EnclosingAtFront;
744	if (EnclosingNamespace.has_value())
745	EnclosingAtFront.push_back(x: *EnclosingNamespace);
746	std::set<std::string> Deduplicated;
747	for (llvm::StringRef S : QueryScopes)
748	if (S != EnclosingNamespace)
749	Deduplicated.insert(x: (S + UnresolvedQualifier.value_or(u: "")).str());
750
751	EnclosingAtFront.reserve(n: EnclosingAtFront.size() + Deduplicated.size());
752	llvm::copy(Range&: Deduplicated, Out: std::back_inserter(x&: EnclosingAtFront));
753
754	return EnclosingAtFront;
755	}
756	};
757
758	// Get all scopes that will be queried in indexes and whether symbols from
759	// any scope is allowed. The first scope in the list is the preferred scope
760	// (e.g. enclosing namespace).
761	SpecifiedScope getQueryScopes(CodeCompletionContext &CCContext,
762	const Sema &CCSema,
763	const CompletionPrefix &HeuristicPrefix,
764	const CodeCompleteOptions &Opts) {
765	SpecifiedScope Scopes;
766	for (auto *Context : CCContext.getVisitedContexts()) {
767	if (isa<TranslationUnitDecl>(Val: Context)) {
768	Scopes.QueryScopes.push_back(x: "");
769	Scopes.AccessibleScopes.push_back(x: "");
770	} else if (const auto *ND = dyn_cast<NamespaceDecl>(Val: Context)) {
771	Scopes.QueryScopes.push_back(x: printNamespaceScope(DC: *Context));
772	Scopes.AccessibleScopes.push_back(x: printQualifiedName(*ND) + "::");
773	}
774	}
775
776	const CXXScopeSpec *SemaSpecifier =
777	CCContext.getCXXScopeSpecifier().value_or(u: nullptr);
778	// Case 1: unqualified completion.
779	if (!SemaSpecifier) {
780	// Case 2 (exception): sema saw no qualifier, but there appears to be one!
781	// This can happen e.g. in incomplete macro expansions. Use heuristics.
782	if (!HeuristicPrefix.Qualifier.empty()) {
783	vlog(Fmt: "Sema said no scope specifier, but we saw {0} in the source code",
784	Vals: HeuristicPrefix.Qualifier);
785	StringRef SpelledSpecifier = HeuristicPrefix.Qualifier;
786	if (SpelledSpecifier.consume_front(Prefix: "::")) {
787	Scopes.AccessibleScopes = {""};
788	Scopes.QueryScopes = {""};
789	}
790	Scopes.UnresolvedQualifier = std::string(SpelledSpecifier);
791	return Scopes;
792	}
793	/// FIXME: When the enclosing namespace contains an inline namespace,
794	/// it's dropped here. This leads to a behavior similar to
795	/// https://github.com/clangd/clangd/issues/1451
796	Scopes.EnclosingNamespace = printNamespaceScope(DC: *CCSema.CurContext);
797	// Allow AllScopes completion as there is no explicit scope qualifier.
798	Scopes.AllowAllScopes = Opts.AllScopes;
799	return Scopes;
800	}
801	// Case 3: sema saw and resolved a scope qualifier.
802	if (SemaSpecifier && SemaSpecifier->isValid())
803	return Scopes;
804
805	// Case 4: There was a qualifier, and Sema didn't resolve it.
806	Scopes.QueryScopes.push_back(x: ""); // Make sure global scope is included.
807	llvm::StringRef SpelledSpecifier = Lexer::getSourceText(
808	Range: CharSourceRange::getCharRange(R: SemaSpecifier->getRange()),
809	SM: CCSema.SourceMgr, LangOpts: clang::LangOptions());
810	if (SpelledSpecifier.consume_front(Prefix: "::"))
811	Scopes.QueryScopes = {""};
812	Scopes.UnresolvedQualifier = std::string(SpelledSpecifier);
813	// Sema excludes the trailing "::".
814	if (!Scopes.UnresolvedQualifier->empty())
815	*Scopes.UnresolvedQualifier += "::";
816
817	Scopes.AccessibleScopes = Scopes.QueryScopes;
818
819	return Scopes;
820	}
821
822	// Should we perform index-based completion in a context of the specified kind?
823	// FIXME: consider allowing completion, but restricting the result types.
824	bool contextAllowsIndex(enum CodeCompletionContext::Kind K) {
825	switch (K) {
826	case CodeCompletionContext::CCC_TopLevel:
827	case CodeCompletionContext::CCC_ObjCInterface:
828	case CodeCompletionContext::CCC_ObjCImplementation:
829	case CodeCompletionContext::CCC_ObjCIvarList:
830	case CodeCompletionContext::CCC_ClassStructUnion:
831	case CodeCompletionContext::CCC_Statement:
832	case CodeCompletionContext::CCC_Expression:
833	case CodeCompletionContext::CCC_ObjCMessageReceiver:
834	case CodeCompletionContext::CCC_EnumTag:
835	case CodeCompletionContext::CCC_UnionTag:
836	case CodeCompletionContext::CCC_ClassOrStructTag:
837	case CodeCompletionContext::CCC_ObjCProtocolName:
838	case CodeCompletionContext::CCC_Namespace:
839	case CodeCompletionContext::CCC_Type:
840	case CodeCompletionContext::CCC_ParenthesizedExpression:
841	case CodeCompletionContext::CCC_ObjCInterfaceName:
842	case CodeCompletionContext::CCC_Symbol:
843	case CodeCompletionContext::CCC_SymbolOrNewName:
844	case CodeCompletionContext::CCC_ObjCClassForwardDecl:
845	case CodeCompletionContext::CCC_TopLevelOrExpression:
846	return true;
847	case CodeCompletionContext::CCC_OtherWithMacros:
848	case CodeCompletionContext::CCC_DotMemberAccess:
849	case CodeCompletionContext::CCC_ArrowMemberAccess:
850	case CodeCompletionContext::CCC_ObjCCategoryName:
851	case CodeCompletionContext::CCC_ObjCPropertyAccess:
852	case CodeCompletionContext::CCC_MacroName:
853	case CodeCompletionContext::CCC_MacroNameUse:
854	case CodeCompletionContext::CCC_PreprocessorExpression:
855	case CodeCompletionContext::CCC_PreprocessorDirective:
856	case CodeCompletionContext::CCC_SelectorName:
857	case CodeCompletionContext::CCC_TypeQualifiers:
858	case CodeCompletionContext::CCC_ObjCInstanceMessage:
859	case CodeCompletionContext::CCC_ObjCClassMessage:
860	case CodeCompletionContext::CCC_IncludedFile:
861	case CodeCompletionContext::CCC_Attribute:
862	// FIXME: Provide identifier based completions for the following contexts:
863	case CodeCompletionContext::CCC_Other: // Be conservative.
864	case CodeCompletionContext::CCC_NaturalLanguage:
865	case CodeCompletionContext::CCC_Recovery:
866	case CodeCompletionContext::CCC_NewName:
867	return false;
868	}
869	llvm_unreachable("unknown code completion context");
870	}
871
872	static bool isInjectedClass(const NamedDecl &D) {
873	if (auto *R = dyn_cast_or_null<RecordDecl>(Val: &D))
874	if (R->isInjectedClassName())
875	return true;
876	return false;
877	}
878
879	// Some member calls are excluded because they're so rarely useful.
880	static bool isExcludedMember(const NamedDecl &D) {
881	// Destructor completion is rarely useful, and works inconsistently.
882	// (s.^ completes ~string, but s.~st^ is an error).
883	if (D.getKind() == Decl::CXXDestructor)
884	return true;
885	// Injected name may be useful for A::foo(), but who writes A::A::foo()?
886	if (isInjectedClass(D))
887	return true;
888	// Explicit calls to operators are also rare.
889	auto NameKind = D.getDeclName().getNameKind();
890	if (NameKind == DeclarationName::CXXOperatorName ||
891	NameKind == DeclarationName::CXXLiteralOperatorName ||
892	NameKind == DeclarationName::CXXConversionFunctionName)
893	return true;
894	return false;
895	}
896
897	// The CompletionRecorder captures Sema code-complete output, including context.
898	// It filters out ignored results (but doesn't apply fuzzy-filtering yet).
899	// It doesn't do scoring or conversion to CompletionItem yet, as we want to
900	// merge with index results first.
901	// Generally the fields and methods of this object should only be used from
902	// within the callback.
903	struct CompletionRecorder : public CodeCompleteConsumer {
904	CompletionRecorder(const CodeCompleteOptions &Opts,
905	llvm::unique_function<void()> ResultsCallback)
906	: CodeCompleteConsumer(Opts.getClangCompleteOpts()),
907	CCContext(CodeCompletionContext::CCC_Other), Opts(Opts),
908	CCAllocator(std::make_shared<GlobalCodeCompletionAllocator>()),
909	CCTUInfo(CCAllocator), ResultsCallback(std::move(ResultsCallback)) {
910	assert(this->ResultsCallback);
911	}
912
913	std::vector<CodeCompletionResult> Results;
914	CodeCompletionContext CCContext;
915	Sema *CCSema = nullptr; // Sema that created the results.
916	// FIXME: Sema is scary. Can we store ASTContext and Preprocessor, instead?
917
918	void ProcessCodeCompleteResults(class Sema &S, CodeCompletionContext Context,
919	CodeCompletionResult *InResults,
920	unsigned NumResults) final {
921	// Results from recovery mode are generally useless, and the callback after
922	// recovery (if any) is usually more interesting. To make sure we handle the
923	// future callback from sema, we just ignore all callbacks in recovery mode,
924	// as taking only results from recovery mode results in poor completion
925	// results.
926	// FIXME: in case there is no future sema completion callback after the
927	// recovery mode, we might still want to provide some results (e.g. trivial
928	// identifier-based completion).
929	CodeCompletionContext::Kind ContextKind = Context.getKind();
930	if (ContextKind == CodeCompletionContext::CCC_Recovery) {
931	log(Fmt: "Code complete: Ignoring sema code complete callback with Recovery "
932	"context.");
933	return;
934	}
935	// If a callback is called without any sema result and the context does not
936	// support index-based completion, we simply skip it to give way to
937	// potential future callbacks with results.
938	if (NumResults == 0 && !contextAllowsIndex(K: Context.getKind()))
939	return;
940	if (CCSema) {
941	log("Multiple code complete callbacks (parser backtracked?). "
942	"Dropping results from context {0}, keeping results from {1}.",
943	getCompletionKindString(Kind: Context.getKind()),
944	getCompletionKindString(this->CCContext.getKind()));
945	return;
946	}
947	// Record the completion context.
948	CCSema = &S;
949	CCContext = Context;
950
951	// Retain the results we might want.
952	for (unsigned I = 0; I < NumResults; ++I) {
953	auto &Result = InResults[I];
954	if (Config::current().Completion.CodePatterns ==
955	Config::CodePatternsPolicy::None &&
956	Result.Kind == CodeCompletionResult::RK_Pattern &&
957	// keep allowing the include files autocomplete suggestions
958	ContextKind != CodeCompletionContext::CCC_IncludedFile)
959	continue;
960	// Class members that are shadowed by subclasses are usually noise.
961	if (Result.Hidden && Result.Declaration &&
962	Result.Declaration->isCXXClassMember())
963	continue;
964	if (!Opts.IncludeIneligibleResults &&
965	(Result.Availability == CXAvailability_NotAvailable ||
966	Result.Availability == CXAvailability_NotAccessible))
967	continue;
968	if (Result.Declaration &&
969	!Context.getBaseType().isNull() // is this a member-access context?
970	&& isExcludedMember(D: *Result.Declaration))
971	continue;
972	// Skip injected class name when no class scope is not explicitly set.
973	// E.g. show injected A::A in `using A::A^` but not in "A^".
974	if (Result.Declaration && !Context.getCXXScopeSpecifier() &&
975	isInjectedClass(D: *Result.Declaration))
976	continue;
977	// We choose to never append '::' to completion results in clangd.
978	Result.StartsNestedNameSpecifier = false;
979	Results.push_back(x: Result);
980	}
981	ResultsCallback();
982	}
983
984	CodeCompletionAllocator &getAllocator() override { return *CCAllocator; }
985	CodeCompletionTUInfo &getCodeCompletionTUInfo() override { return CCTUInfo; }
986
987	// Returns the filtering/sorting name for Result, which must be from Results.
988	// Returned string is owned by this recorder (or the AST).
989	llvm::StringRef getName(const CodeCompletionResult &Result) {
990	switch (Result.Kind) {
991	case CodeCompletionResult::RK_Declaration:
992	if (auto *ID = Result.Declaration->getIdentifier())
993	return ID->getName();
994	break;
995	case CodeCompletionResult::RK_Keyword:
996	return Result.Keyword;
997	case CodeCompletionResult::RK_Macro:
998	return Result.Macro->getName();
999	case CodeCompletionResult::RK_Pattern:
1000	break;
1001	}
1002	auto *CCS = codeCompletionString(R: Result);
1003	const CodeCompletionString::Chunk *OnlyText = nullptr;
1004	for (auto &C : *CCS) {
1005	if (C.Kind != CodeCompletionString::CK_TypedText)
1006	continue;
1007	if (OnlyText)
1008	return CCAllocator->CopyString(String: CCS->getAllTypedText());
1009	OnlyText = &C;
1010	}
1011	return OnlyText ? OnlyText->Text : llvm::StringRef();
1012	}
1013
1014	// Build a CodeCompletion string for R, which must be from Results.
1015	// The CCS will be owned by this recorder.
1016	CodeCompletionString *codeCompletionString(const CodeCompletionResult &R) {
1017	// CodeCompletionResult doesn't seem to be const-correct. We own it, anyway.
1018	return const_cast<CodeCompletionResult &>(R).CreateCodeCompletionString(
1019	*CCSema, CCContext, *CCAllocator, CCTUInfo,
1020	/*IncludeBriefComments=*/false);
1021	}
1022
1023	private:
1024	CodeCompleteOptions Opts;
1025	std::shared_ptr<GlobalCodeCompletionAllocator> CCAllocator;
1026	CodeCompletionTUInfo CCTUInfo;
1027	llvm::unique_function<void()> ResultsCallback;
1028	};
1029
1030	struct ScoredSignature {
1031	// When not null, requires documentation to be requested from the index with
1032	// this ID.
1033	SymbolID IDForDoc;
1034	SignatureInformation Signature;
1035	SignatureQualitySignals Quality;
1036	};
1037
1038	// Returns the index of the parameter matching argument number "Arg.
1039	// This is usually just "Arg", except for variadic functions/templates, where
1040	// "Arg" might be higher than the number of parameters. When that happens, we
1041	// assume the last parameter is variadic and assume all further args are
1042	// part of it.
1043	int paramIndexForArg(const CodeCompleteConsumer::OverloadCandidate &Candidate,
1044	int Arg) {
1045	int NumParams = Candidate.getNumParams();
1046	if (auto *T = Candidate.getFunctionType()) {
1047	if (auto *Proto = T->getAs<FunctionProtoType>()) {
1048	if (Proto->isVariadic())
1049	++NumParams;
1050	}
1051	}
1052	return std::min(a: Arg, b: std::max(a: NumParams - 1, b: 0));
1053	}
1054
1055	class SignatureHelpCollector final : public CodeCompleteConsumer {
1056	public:
1057	SignatureHelpCollector(const clang::CodeCompleteOptions &CodeCompleteOpts,
1058	MarkupKind DocumentationFormat,
1059	const SymbolIndex *Index, SignatureHelp &SigHelp)
1060	: CodeCompleteConsumer(CodeCompleteOpts), SigHelp(SigHelp),
1061	Allocator(std::make_shared<clang::GlobalCodeCompletionAllocator>()),
1062	CCTUInfo(Allocator), Index(Index),
1063	DocumentationFormat(DocumentationFormat) {}
1064
1065	void ProcessOverloadCandidates(Sema &S, unsigned CurrentArg,
1066	OverloadCandidate *Candidates,
1067	unsigned NumCandidates,
1068	SourceLocation OpenParLoc,
1069	bool Braced) override {
1070	assert(!OpenParLoc.isInvalid());
1071	SourceManager &SrcMgr = S.getSourceManager();
1072	OpenParLoc = SrcMgr.getFileLoc(Loc: OpenParLoc);
1073	if (SrcMgr.isInMainFile(Loc: OpenParLoc))
1074	SigHelp.argListStart = sourceLocToPosition(SM: SrcMgr, Loc: OpenParLoc);
1075	else
1076	elog(Fmt: "Location oustide main file in signature help: {0}",
1077	Vals: OpenParLoc.printToString(SM: SrcMgr));
1078
1079	std::vector<ScoredSignature> ScoredSignatures;
1080	SigHelp.signatures.reserve(n: NumCandidates);
1081	ScoredSignatures.reserve(n: NumCandidates);
1082	// FIXME(rwols): How can we determine the "active overload candidate"?
1083	// Right now the overloaded candidates seem to be provided in a "best fit"
1084	// order, so I'm not too worried about this.
1085	SigHelp.activeSignature = 0;
1086	assert(CurrentArg <= (unsigned)std::numeric_limits<int>::max() &&
1087	"too many arguments");
1088
1089	SigHelp.activeParameter = static_cast<int>(CurrentArg);
1090
1091	for (unsigned I = 0; I < NumCandidates; ++I) {
1092	OverloadCandidate Candidate = Candidates[I];
1093	// We want to avoid showing instantiated signatures, because they may be
1094	// long in some cases (e.g. when 'T' is substituted with 'std::string', we
1095	// would get 'std::basic_string<char>').
1096	if (auto *Func = Candidate.getFunction()) {
1097	if (auto *Pattern = Func->getTemplateInstantiationPattern())
1098	Candidate = OverloadCandidate(Pattern);
1099	}
1100	if (static_cast<int>(I) == SigHelp.activeSignature) {
1101	// The activeParameter in LSP relates to the activeSignature. There is
1102	// another, per-signature field, but we currently do not use it and not
1103	// all clients might support it.
1104	// FIXME: Add support for per-signature activeParameter field.
1105	SigHelp.activeParameter =
1106	paramIndexForArg(Candidate, Arg: SigHelp.activeParameter);
1107	}
1108
1109	const auto *CCS = Candidate.CreateSignatureString(
1110	CurrentArg, S, Allocator&: *Allocator, CCTUInfo,
1111	/*IncludeBriefComments=*/true, Braced);
1112	assert(CCS && "Expected the CodeCompletionString to be non-null");
1113	ScoredSignatures.push_back(x: processOverloadCandidate(
1114	Candidate, CCS: *CCS,
1115	DocComment: Candidate.getFunction()
1116	? getDeclComment(S.getASTContext(), *Candidate.getFunction())
1117	: ""));
1118	}
1119
1120	// Sema does not load the docs from the preamble, so we need to fetch extra
1121	// docs from the index instead.
1122	llvm::DenseMap<SymbolID, std::string> FetchedDocs;
1123	if (Index) {
1124	LookupRequest IndexRequest;
1125	for (const auto &S : ScoredSignatures) {
1126	if (!S.IDForDoc)
1127	continue;
1128	IndexRequest.IDs.insert(V: S.IDForDoc);
1129	}
1130	Index->lookup(Req: IndexRequest, Callback: [&](const Symbol &S) {
1131	if (!S.Documentation.empty())
1132	FetchedDocs[S.ID] = std::string(S.Documentation);
1133	});
1134	vlog(Fmt: "SigHelp: requested docs for {0} symbols from the index, got {1} "
1135	"symbols with non-empty docs in the response",
1136	Vals: IndexRequest.IDs.size(), Vals: FetchedDocs.size());
1137	}
1138
1139	llvm::sort(C&: ScoredSignatures, Comp: [](const ScoredSignature &L,
1140	const ScoredSignature &R) {
1141	// Ordering follows:
1142	// - Less number of parameters is better.
1143	// - Aggregate > Function > FunctionType > FunctionTemplate
1144	// - High score is better.
1145	// - Shorter signature is better.
1146	// - Alphabetically smaller is better.
1147	if (L.Quality.NumberOfParameters != R.Quality.NumberOfParameters)
1148	return L.Quality.NumberOfParameters < R.Quality.NumberOfParameters;
1149	if (L.Quality.NumberOfOptionalParameters !=
1150	R.Quality.NumberOfOptionalParameters)
1151	return L.Quality.NumberOfOptionalParameters <
1152	R.Quality.NumberOfOptionalParameters;
1153	if (L.Quality.Kind != R.Quality.Kind) {
1154	using OC = CodeCompleteConsumer::OverloadCandidate;
1155	auto KindPriority = [&](OC::CandidateKind K) {
1156	switch (K) {
1157	case OC::CK_Aggregate:
1158	return 0;
1159	case OC::CK_Function:
1160	return 1;
1161	case OC::CK_FunctionType:
1162	return 2;
1163	case OC::CK_FunctionProtoTypeLoc:
1164	return 3;
1165	case OC::CK_FunctionTemplate:
1166	return 4;
1167	case OC::CK_Template:
1168	return 5;
1169	}
1170	llvm_unreachable("Unknown overload candidate type.");
1171	};
1172	return KindPriority(L.Quality.Kind) < KindPriority(R.Quality.Kind);
1173	}
1174	if (L.Signature.label.size() != R.Signature.label.size())
1175	return L.Signature.label.size() < R.Signature.label.size();
1176	return L.Signature.label < R.Signature.label;
1177	});
1178
1179	for (auto &SS : ScoredSignatures) {
1180	auto IndexDocIt =
1181	SS.IDForDoc ? FetchedDocs.find(Val: SS.IDForDoc) : FetchedDocs.end();
1182	if (IndexDocIt != FetchedDocs.end()) {
1183	markup::Document SignatureComment;
1184	parseDocumentation(Input: IndexDocIt->second, Output&: SignatureComment);
1185	SS.Signature.documentation =
1186	renderDoc(Doc: SignatureComment, Kind: DocumentationFormat);
1187	}
1188
1189	SigHelp.signatures.push_back(x: std::move(SS.Signature));
1190	}
1191	}
1192
1193	GlobalCodeCompletionAllocator &getAllocator() override { return *Allocator; }
1194
1195	CodeCompletionTUInfo &getCodeCompletionTUInfo() override { return CCTUInfo; }
1196
1197	private:
1198	void processParameterChunk(llvm::StringRef ChunkText,
1199	SignatureInformation &Signature) const {
1200	// (!) this is O(n), should still be fast compared to building ASTs.
1201	unsigned ParamStartOffset = lspLength(Code: Signature.label);
1202	unsigned ParamEndOffset = ParamStartOffset + lspLength(Code: ChunkText);
1203	// A piece of text that describes the parameter that corresponds to
1204	// the code-completion location within a function call, message send,
1205	// macro invocation, etc.
1206	Signature.label += ChunkText;
1207	ParameterInformation Info;
1208	Info.labelOffsets.emplace(args&: ParamStartOffset, args&: ParamEndOffset);
1209	// FIXME: only set 'labelOffsets' when all clients migrate out of it.
1210	Info.labelString = std::string(ChunkText);
1211
1212	Signature.parameters.push_back(x: std::move(Info));
1213	}
1214
1215	void processOptionalChunk(const CodeCompletionString &CCS,
1216	SignatureInformation &Signature,
1217	SignatureQualitySignals &Signal) const {
1218	for (const auto &Chunk : CCS) {
1219	switch (Chunk.Kind) {
1220	case CodeCompletionString::CK_Optional:
1221	assert(Chunk.Optional &&
1222	"Expected the optional code completion string to be non-null.");
1223	processOptionalChunk(CCS: *Chunk.Optional, Signature, Signal);
1224	break;
1225	case CodeCompletionString::CK_VerticalSpace:
1226	break;
1227	case CodeCompletionString::CK_CurrentParameter:
1228	case CodeCompletionString::CK_Placeholder:
1229	processParameterChunk(ChunkText: Chunk.Text, Signature);
1230	Signal.NumberOfOptionalParameters++;
1231	break;
1232	default:
1233	Signature.label += Chunk.Text;
1234	break;
1235	}
1236	}
1237	}
1238
1239	// FIXME(ioeric): consider moving CodeCompletionString logic here to
1240	// CompletionString.h.
1241	ScoredSignature processOverloadCandidate(const OverloadCandidate &Candidate,
1242	const CodeCompletionString &CCS,
1243	llvm::StringRef DocComment) const {
1244	SignatureInformation Signature;
1245	SignatureQualitySignals Signal;
1246	const char *ReturnType = nullptr;
1247
1248	markup::Document OverloadComment;
1249	parseDocumentation(Input: formatDocumentation(CCS, DocComment), Output&: OverloadComment);
1250	Signature.documentation = renderDoc(Doc: OverloadComment, Kind: DocumentationFormat);
1251	Signal.Kind = Candidate.getKind();
1252
1253	for (const auto &Chunk : CCS) {
1254	switch (Chunk.Kind) {
1255	case CodeCompletionString::CK_ResultType:
1256	// A piece of text that describes the type of an entity or,
1257	// for functions and methods, the return type.
1258	assert(!ReturnType && "Unexpected CK_ResultType");
1259	ReturnType = Chunk.Text;
1260	break;
1261	case CodeCompletionString::CK_CurrentParameter:
1262	case CodeCompletionString::CK_Placeholder:
1263	processParameterChunk(ChunkText: Chunk.Text, Signature);
1264	Signal.NumberOfParameters++;
1265	break;
1266	case CodeCompletionString::CK_Optional: {
1267	// The rest of the parameters are defaulted/optional.
1268	assert(Chunk.Optional &&
1269	"Expected the optional code completion string to be non-null.");
1270	processOptionalChunk(CCS: *Chunk.Optional, Signature, Signal);
1271	break;
1272	}
1273	case CodeCompletionString::CK_VerticalSpace:
1274	break;
1275	default:
1276	Signature.label += Chunk.Text;
1277	break;
1278	}
1279	}
1280	if (ReturnType) {
1281	Signature.label += " -> ";
1282	Signature.label += ReturnType;
1283	}
1284	dlog("Signal for {0}: {1}", Signature, Signal);
1285	ScoredSignature Result;
1286	Result.Signature = std::move(Signature);
1287	Result.Quality = Signal;
1288	const FunctionDecl *Func = Candidate.getFunction();
1289	if (Func && Result.Signature.documentation.value.empty()) {
1290	// Computing USR caches linkage, which may change after code completion.
1291	if (!hasUnstableLinkage(Func))
1292	Result.IDForDoc = clangd::getSymbolID(Func);
1293	}
1294	return Result;
1295	}
1296
1297	SignatureHelp &SigHelp;
1298	std::shared_ptr<clang::GlobalCodeCompletionAllocator> Allocator;
1299	CodeCompletionTUInfo CCTUInfo;
1300	const SymbolIndex *Index;
1301	MarkupKind DocumentationFormat;
1302	}; // SignatureHelpCollector
1303
1304	// Used only for completion of C-style comments in function call (i.e.
1305	// /*foo=*/7). Similar to SignatureHelpCollector, but needs to do less work.
1306	class ParamNameCollector final : public CodeCompleteConsumer {
1307	public:
1308	ParamNameCollector(const clang::CodeCompleteOptions &CodeCompleteOpts,
1309	std::set<std::string> &ParamNames)
1310	: CodeCompleteConsumer(CodeCompleteOpts),
1311	Allocator(std::make_shared<clang::GlobalCodeCompletionAllocator>()),
1312	CCTUInfo(Allocator), ParamNames(ParamNames) {}
1313
1314	void ProcessOverloadCandidates(Sema &S, unsigned CurrentArg,
1315	OverloadCandidate *Candidates,
1316	unsigned NumCandidates,
1317	SourceLocation OpenParLoc,
1318	bool Braced) override {
1319	assert(CurrentArg <= (unsigned)std::numeric_limits<int>::max() &&
1320	"too many arguments");
1321
1322	for (unsigned I = 0; I < NumCandidates; ++I) {
1323	if (const NamedDecl *ND = Candidates[I].getParamDecl(N: CurrentArg))
1324	if (const auto *II = ND->getIdentifier())
1325	ParamNames.emplace(args: II->getName());
1326	}
1327	}
1328
1329	private:
1330	GlobalCodeCompletionAllocator &getAllocator() override { return *Allocator; }
1331
1332	CodeCompletionTUInfo &getCodeCompletionTUInfo() override { return CCTUInfo; }
1333
1334	std::shared_ptr<clang::GlobalCodeCompletionAllocator> Allocator;
1335	CodeCompletionTUInfo CCTUInfo;
1336	std::set<std::string> &ParamNames;
1337	};
1338
1339	struct SemaCompleteInput {
1340	PathRef FileName;
1341	size_t Offset;
1342	const PreambleData &Preamble;
1343	const std::optional<PreamblePatch> Patch;
1344	const ParseInputs &ParseInput;
1345	};
1346
1347	void loadMainFilePreambleMacros(const Preprocessor &PP,
1348	const PreambleData &Preamble) {
1349	// The ExternalPreprocessorSource has our macros, if we know where to look.
1350	// We can read all the macros using PreambleMacros->ReadDefinedMacros(),
1351	// but this includes transitively included files, so may deserialize a lot.
1352	ExternalPreprocessorSource *PreambleMacros = PP.getExternalSource();
1353	// As we have the names of the macros, we can look up their IdentifierInfo
1354	// and then use this to load just the macros we want.
1355	const auto &ITable = PP.getIdentifierTable();
1356	IdentifierInfoLookup *PreambleIdentifiers =
1357	ITable.getExternalIdentifierLookup();
1358
1359	if (!PreambleIdentifiers || !PreambleMacros)
1360	return;
1361	for (const auto &MacroName : Preamble.Macros.Names) {
1362	if (ITable.find(MacroName.getKey()) != ITable.end())
1363	continue;
1364	if (auto *II = PreambleIdentifiers->get(Name: MacroName.getKey()))
1365	if (II->isOutOfDate())
1366	PreambleMacros->updateOutOfDateIdentifier(II: *II);
1367	}
1368	}
1369
1370	// Invokes Sema code completion on a file.
1371	// If \p Includes is set, it will be updated based on the compiler invocation.
1372	bool semaCodeComplete(std::unique_ptr<CodeCompleteConsumer> Consumer,
1373	const clang::CodeCompleteOptions &Options,
1374	const SemaCompleteInput &Input,
1375	IncludeStructure *Includes = nullptr) {
1376	trace::Span Tracer("Sema completion");
1377
1378	IgnoreDiagnostics IgnoreDiags;
1379	auto CI = buildCompilerInvocation(Inputs: Input.ParseInput, D&: IgnoreDiags);
1380	if (!CI) {
1381	elog(Fmt: "Couldn't create CompilerInvocation");
1382	return false;
1383	}
1384	auto &FrontendOpts = CI->getFrontendOpts();
1385	FrontendOpts.SkipFunctionBodies = true;
1386	// Disable typo correction in Sema.
1387	CI->getLangOpts().SpellChecking = false;
1388	// Code completion won't trigger in delayed template bodies.
1389	// This is on-by-default in windows to allow parsing SDK headers; we're only
1390	// disabling it for the main-file (not preamble).
1391	CI->getLangOpts().DelayedTemplateParsing = false;
1392	// Setup code completion.
1393	FrontendOpts.CodeCompleteOpts = Options;
1394	FrontendOpts.CodeCompletionAt.FileName = std::string(Input.FileName);
1395	std::tie(args&: FrontendOpts.CodeCompletionAt.Line,
1396	args&: FrontendOpts.CodeCompletionAt.Column) =
1397	offsetToClangLineColumn(Code: Input.ParseInput.Contents, Offset: Input.Offset);
1398
1399	std::unique_ptr<llvm::MemoryBuffer> ContentsBuffer =
1400	llvm::MemoryBuffer::getMemBuffer(InputData: Input.ParseInput.Contents,
1401	BufferName: Input.FileName);
1402	// The diagnostic options must be set before creating a CompilerInstance.
1403	CI->getDiagnosticOpts().IgnoreWarnings = true;
1404	// We reuse the preamble whether it's valid or not. This is a
1405	// correctness/performance tradeoff: building without a preamble is slow, and
1406	// completion is latency-sensitive.
1407	// However, if we're completing *inside* the preamble section of the draft,
1408	// overriding the preamble will break sema completion. Fortunately we can just
1409	// skip all includes in this case; these completions are really simple.
1410	PreambleBounds PreambleRegion =
1411	ComputePreambleBounds(LangOpts: CI->getLangOpts(), Buffer: *ContentsBuffer, MaxLines: 0);
1412	bool CompletingInPreamble = Input.Offset < PreambleRegion.Size ||
1413	(!PreambleRegion.PreambleEndsAtStartOfLine &&
1414	Input.Offset == PreambleRegion.Size);
1415	if (Input.Patch)
1416	Input.Patch->apply(CI&: *CI);
1417	// NOTE: we must call BeginSourceFile after prepareCompilerInstance. Otherwise
1418	// the remapped buffers do not get freed.
1419	llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS =
1420	Input.ParseInput.TFS->view(CWD: Input.ParseInput.CompileCommand.Directory);
1421	if (Input.Preamble.StatCache)
1422	VFS = Input.Preamble.StatCache->getConsumingFS(FS: std::move(VFS));
1423	auto Clang = prepareCompilerInstance(
1424	std::move(CI), !CompletingInPreamble ? &Input.Preamble.Preamble : nullptr,
1425	MainFile: std::move(ContentsBuffer), std::move(VFS), IgnoreDiags);
1426	Clang->getPreprocessorOpts().SingleFileParseMode = CompletingInPreamble;
1427	Clang->setCodeCompletionConsumer(Consumer.release());
1428
1429	if (Input.Preamble.RequiredModules)
1430	Input.Preamble.RequiredModules->adjustHeaderSearchOptions(Options&: Clang->getHeaderSearchOpts());
1431
1432	SyntaxOnlyAction Action;
1433	if (!Action.BeginSourceFile(CI&: *Clang, Input: Clang->getFrontendOpts().Inputs[0])) {
1434	log(Fmt: "BeginSourceFile() failed when running codeComplete for {0}",
1435	Vals: Input.FileName);
1436	return false;
1437	}
1438	// Macros can be defined within the preamble region of the main file.
1439	// They don't fall nicely into our index/Sema dichotomy:
1440	// - they're not indexed for completion (they're not available across files)
1441	// - but Sema code complete won't see them: as part of the preamble, they're
1442	// deserialized only when mentioned.
1443	// Force them to be deserialized so SemaCodeComplete sees them.
1444	loadMainFilePreambleMacros(PP: Clang->getPreprocessor(), Preamble: Input.Preamble);
1445	if (Includes)
1446	Includes->collect(CI: *Clang);
1447	if (llvm::Error Err = Action.Execute()) {
1448	log(Fmt: "Execute() failed when running codeComplete for {0}: {1}",
1449	Vals: Input.FileName, Vals: toString(E: std::move(Err)));
1450	return false;
1451	}
1452	Action.EndSourceFile();
1453
1454	return true;
1455	}
1456
1457	// Should we allow index completions in the specified context?
1458	bool allowIndex(CodeCompletionContext &CC) {
1459	if (!contextAllowsIndex(K: CC.getKind()))
1460	return false;
1461	// We also avoid ClassName::bar (but allow namespace::bar).
1462	auto Scope = CC.getCXXScopeSpecifier();
1463	if (!Scope)
1464	return true;
1465	NestedNameSpecifier *NameSpec = (*Scope)->getScopeRep();
1466	if (!NameSpec)
1467	return true;
1468	// We only query the index when qualifier is a namespace.
1469	// If it's a class, we rely solely on sema completions.
1470	switch (NameSpec->getKind()) {
1471	case NestedNameSpecifier::Global:
1472	case NestedNameSpecifier::Namespace:
1473	case NestedNameSpecifier::NamespaceAlias:
1474	return true;
1475	case NestedNameSpecifier::Super:
1476	case NestedNameSpecifier::TypeSpec:
1477	// Unresolved inside a template.
1478	case NestedNameSpecifier::Identifier:
1479	return false;
1480	}
1481	llvm_unreachable("invalid NestedNameSpecifier kind");
1482	}
1483
1484	// Should we include a symbol from the index given the completion kind?
1485	// FIXME: Ideally we can filter in the fuzzy find request itself.
1486	bool includeSymbolFromIndex(CodeCompletionContext::Kind Kind,
1487	const Symbol &Sym) {
1488	// Objective-C protocols are only useful in ObjC protocol completions,
1489	// in other places they're confusing, especially when they share the same
1490	// identifier with a class.
1491	if (Sym.SymInfo.Kind == index::SymbolKind::Protocol &&
1492	Sym.SymInfo.Lang == index::SymbolLanguage::ObjC)
1493	return Kind == CodeCompletionContext::CCC_ObjCProtocolName;
1494	else if (Kind == CodeCompletionContext::CCC_ObjCProtocolName)
1495	// Don't show anything else in ObjC protocol completions.
1496	return false;
1497
1498	if (Kind == CodeCompletionContext::CCC_ObjCClassForwardDecl)
1499	return Sym.SymInfo.Kind == index::SymbolKind::Class &&
1500	Sym.SymInfo.Lang == index::SymbolLanguage::ObjC;
1501	return true;
1502	}
1503
1504	std::future<std::pair<bool, SymbolSlab>>
1505	startAsyncFuzzyFind(const SymbolIndex &Index, const FuzzyFindRequest &Req) {
1506	return runAsync<std::pair<bool, SymbolSlab>>(Action: [&Index, Req]() {
1507	trace::Span Tracer("Async fuzzyFind");
1508	SymbolSlab::Builder Syms;
1509	bool Incomplete =
1510	Index.fuzzyFind(Req, Callback: [&Syms](const Symbol &Sym) { Syms.insert(S: Sym); });
1511	return std::make_pair(x&: Incomplete, y: std::move(Syms).build());
1512	});
1513	}
1514
1515	// Creates a `FuzzyFindRequest` based on the cached index request from the
1516	// last completion, if any, and the speculated completion filter text in the
1517	// source code.
1518	FuzzyFindRequest speculativeFuzzyFindRequestForCompletion(
1519	FuzzyFindRequest CachedReq, const CompletionPrefix &HeuristicPrefix) {
1520	CachedReq.Query = std::string(HeuristicPrefix.Name);
1521	return CachedReq;
1522	}
1523
1524	// This function is similar to Lexer::findNextToken(), but assumes
1525	// that the input SourceLocation is the completion point (which is
1526	// a case findNextToken() does not handle).
1527	std::optional<Token>
1528	findTokenAfterCompletionPoint(SourceLocation CompletionPoint,
1529	const SourceManager &SM,
1530	const LangOptions &LangOpts) {
1531	SourceLocation Loc = CompletionPoint;
1532	if (Loc.isMacroID()) {
1533	if (!Lexer::isAtEndOfMacroExpansion(loc: Loc, SM, LangOpts, MacroEnd: &Loc))
1534	return std::nullopt;
1535	}
1536
1537	// Advance to the next SourceLocation after the completion point.
1538	// Lexer::findNextToken() would call MeasureTokenLength() here,
1539	// which does not handle the completion point (and can't, because
1540	// the Lexer instance it constructs internally doesn't have a
1541	// Preprocessor and so doesn't know about the completion point).
1542	Loc = Loc.getLocWithOffset(Offset: 1);
1543
1544	// Break down the source location.
1545	std::pair<FileID, unsigned> LocInfo = SM.getDecomposedLoc(Loc);
1546
1547	// Try to load the file buffer.
1548	bool InvalidTemp = false;
1549	StringRef File = SM.getBufferData(FID: LocInfo.first, Invalid: &InvalidTemp);
1550	if (InvalidTemp)
1551	return std::nullopt;
1552
1553	const char *TokenBegin = File.data() + LocInfo.second;
1554
1555	// Lex from the start of the given location.
1556	Lexer TheLexer(SM.getLocForStartOfFile(FID: LocInfo.first), LangOpts, File.begin(),
1557	TokenBegin, File.end());
1558	// Find the token.
1559	Token Tok;
1560	TheLexer.LexFromRawLexer(Result&: Tok);
1561	return Tok;
1562	}
1563
1564	// Runs Sema-based (AST) and Index-based completion, returns merged results.
1565	//
1566	// There are a few tricky considerations:
1567	// - the AST provides information needed for the index query (e.g. which
1568	// namespaces to search in). So Sema must start first.
1569	// - we only want to return the top results (Opts.Limit).
1570	// Building CompletionItems for everything else is wasteful, so we want to
1571	// preserve the "native" format until we're done with scoring.
1572	// - the data underlying Sema completion items is owned by the AST and various
1573	// other arenas, which must stay alive for us to build CompletionItems.
1574	// - we may get duplicate results from Sema and the Index, we need to merge.
1575	//
1576	// So we start Sema completion first, and do all our work in its callback.
1577	// We use the Sema context information to query the index.
1578	// Then we merge the two result sets, producing items that are Sema/Index/Both.
1579	// These items are scored, and the top N are synthesized into the LSP response.
1580	// Finally, we can clean up the data structures created by Sema completion.
1581	//
1582	// Main collaborators are:
1583	// - semaCodeComplete sets up the compiler machinery to run code completion.
1584	// - CompletionRecorder captures Sema completion results, including context.
1585	// - SymbolIndex (Opts.Index) provides index completion results as Symbols
1586	// - CompletionCandidates are the result of merging Sema and Index results.
1587	// Each candidate points to an underlying CodeCompletionResult (Sema), a
1588	// Symbol (Index), or both. It computes the result quality score.
1589	// CompletionCandidate also does conversion to CompletionItem (at the end).
1590	// - FuzzyMatcher scores how the candidate matches the partial identifier.
1591	// This score is combined with the result quality score for the final score.
1592	// - TopN determines the results with the best score.
1593	class CodeCompleteFlow {
1594	PathRef FileName;
1595	IncludeStructure Includes; // Complete once the compiler runs.
1596	SpeculativeFuzzyFind *SpecFuzzyFind; // Can be nullptr.
1597	const CodeCompleteOptions &Opts;
1598
1599	// Sema takes ownership of Recorder. Recorder is valid until Sema cleanup.
1600	CompletionRecorder *Recorder = nullptr;
1601	CodeCompletionContext::Kind CCContextKind = CodeCompletionContext::CCC_Other;
1602	bool IsUsingDeclaration = false;
1603	// The snippets will not be generated if the token following completion
1604	// location is an opening parenthesis (tok::l_paren) because this would add
1605	// extra parenthesis.
1606	tok::TokenKind NextTokenKind = tok::eof;
1607	// Counters for logging.
1608	int NSema = 0, NIndex = 0, NSemaAndIndex = 0, NIdent = 0;
1609	bool Incomplete = false; // Would more be available with a higher limit?
1610	CompletionPrefix HeuristicPrefix;
1611	std::optional<FuzzyMatcher> Filter; // Initialized once Sema runs.
1612	Range ReplacedRange;
1613	std::vector<std::string> QueryScopes; // Initialized once Sema runs.
1614	std::vector<std::string> AccessibleScopes; // Initialized once Sema runs.
1615	// Initialized once QueryScopes is initialized, if there are scopes.
1616	std::optional<ScopeDistance> ScopeProximity;
1617	std::optional<OpaqueType> PreferredType; // Initialized once Sema runs.
1618	// Whether to query symbols from any scope. Initialized once Sema runs.
1619	bool AllScopes = false;
1620	llvm::StringSet<> ContextWords;
1621	// Include-insertion and proximity scoring rely on the include structure.
1622	// This is available after Sema has run.
1623	std::optional<IncludeInserter> Inserter; // Available during runWithSema.
1624	std::optional<URIDistance> FileProximity; // Initialized once Sema runs.
1625	/// Speculative request based on the cached request and the filter text before
1626	/// the cursor.
1627	/// Initialized right before sema run. This is only set if `SpecFuzzyFind` is
1628	/// set and contains a cached request.
1629	std::optional<FuzzyFindRequest> SpecReq;
1630
1631	public:
1632	// A CodeCompleteFlow object is only useful for calling run() exactly once.
1633	CodeCompleteFlow(PathRef FileName, const IncludeStructure &Includes,
1634	SpeculativeFuzzyFind *SpecFuzzyFind,
1635	const CodeCompleteOptions &Opts)
1636	: FileName(FileName), Includes(Includes), SpecFuzzyFind(SpecFuzzyFind),
1637	Opts(Opts) {}
1638
1639	CodeCompleteResult run(const SemaCompleteInput &SemaCCInput) && {
1640	trace::Span Tracer("CodeCompleteFlow");
1641	HeuristicPrefix = guessCompletionPrefix(Content: SemaCCInput.ParseInput.Contents,
1642	Offset: SemaCCInput.Offset);
1643	populateContextWords(Content: SemaCCInput.ParseInput.Contents);
1644	if (Opts.Index && SpecFuzzyFind && SpecFuzzyFind->CachedReq) {
1645	assert(!SpecFuzzyFind->Result.valid());
1646	SpecReq = speculativeFuzzyFindRequestForCompletion(
1647	CachedReq: *SpecFuzzyFind->CachedReq, HeuristicPrefix);
1648	SpecFuzzyFind->Result = startAsyncFuzzyFind(Index: *Opts.Index, Req: *SpecReq);
1649	}
1650
1651	// We run Sema code completion first. It builds an AST and calculates:
1652	// - completion results based on the AST.
1653	// - partial identifier and context. We need these for the index query.
1654	CodeCompleteResult Output;
1655	auto RecorderOwner = std::make_unique<CompletionRecorder>(args: Opts, args: [&]() {
1656	assert(Recorder && "Recorder is not set");
1657	CCContextKind = Recorder->CCContext.getKind();
1658	IsUsingDeclaration = Recorder->CCContext.isUsingDeclaration();
1659	auto Style = getFormatStyleForFile(File: SemaCCInput.FileName,
1660	Content: SemaCCInput.ParseInput.Contents,
1661	TFS: *SemaCCInput.ParseInput.TFS, FormatFile: false);
1662	const auto NextToken = findTokenAfterCompletionPoint(
1663	CompletionPoint: Recorder->CCSema->getPreprocessor().getCodeCompletionLoc(),
1664	SM: Recorder->CCSema->getSourceManager(), LangOpts: Recorder->CCSema->LangOpts);
1665	if (NextToken)
1666	NextTokenKind = NextToken->getKind();
1667	// If preprocessor was run, inclusions from preprocessor callback should
1668	// already be added to Includes.
1669	Inserter.emplace(
1670	args: SemaCCInput.FileName, args: SemaCCInput.ParseInput.Contents, args&: Style,
1671	args: SemaCCInput.ParseInput.CompileCommand.Directory,
1672	args: &Recorder->CCSema->getPreprocessor().getHeaderSearchInfo(),
1673	args: Config::current().Style.QuotedHeaders,
1674	args: Config::current().Style.AngledHeaders);
1675	for (const auto &Inc : Includes.MainFileIncludes)
1676	Inserter->addExisting(Inc);
1677
1678	// Most of the cost of file proximity is in initializing the FileDistance
1679	// structures based on the observed includes, once per query. Conceptually
1680	// that happens here (though the per-URI-scheme initialization is lazy).
1681	// The per-result proximity scoring is (amortized) very cheap.
1682	FileDistanceOptions ProxOpts{}; // Use defaults.
1683	const auto &SM = Recorder->CCSema->getSourceManager();
1684	llvm::StringMap<SourceParams> ProxSources;
1685	auto MainFileID =
1686	Includes.getID(Entry: SM.getFileEntryForID(FID: SM.getMainFileID()));
1687	assert(MainFileID);
1688	for (auto &HeaderIDAndDepth : Includes.includeDepth(Root: *MainFileID)) {
1689	auto &Source =
1690	ProxSources[Includes.getRealPath(ID: HeaderIDAndDepth.getFirst())];
1691	Source.Cost = HeaderIDAndDepth.getSecond() * ProxOpts.IncludeCost;
1692	// Symbols near our transitive includes are good, but only consider
1693	// things in the same directory or below it. Otherwise there can be
1694	// many false positives.
1695	if (HeaderIDAndDepth.getSecond() > 0)
1696	Source.MaxUpTraversals = 1;
1697	}
1698	FileProximity.emplace(args&: ProxSources, args&: ProxOpts);
1699
1700	Output = runWithSema();
1701	Inserter.reset(); // Make sure this doesn't out-live Clang.
1702	SPAN_ATTACH(Tracer, "sema_completion_kind",
1703	getCompletionKindString(CCContextKind));
1704	log("Code complete: sema context {0}, query scopes [{1}] (AnyScope={2}), "
1705	"expected type {3}{4}",
1706	getCompletionKindString(Kind: CCContextKind),
1707	llvm::join(Begin: QueryScopes.begin(), End: QueryScopes.end(), Separator: ","), AllScopes,
1708	PreferredType ? Recorder->CCContext.getPreferredType().getAsString()
1709	: "<none>",
1710	IsUsingDeclaration ? ", inside using declaration" : "");
1711	});
1712
1713	Recorder = RecorderOwner.get();
1714
1715	semaCodeComplete(std::move(RecorderOwner), Opts.getClangCompleteOpts(),
1716	SemaCCInput, &Includes);
1717	logResults(Output, Tracer);
1718	return Output;
1719	}
1720
1721	void logResults(const CodeCompleteResult &Output, const trace::Span &Tracer) {
1722	SPAN_ATTACH(Tracer, "sema_results", NSema);
1723	SPAN_ATTACH(Tracer, "index_results", NIndex);
1724	SPAN_ATTACH(Tracer, "merged_results", NSemaAndIndex);
1725	SPAN_ATTACH(Tracer, "identifier_results", NIdent);
1726	SPAN_ATTACH(Tracer, "returned_results", int64_t(Output.Completions.size()));
1727	SPAN_ATTACH(Tracer, "incomplete", Output.HasMore);
1728	log(Fmt: "Code complete: {0} results from Sema, {1} from Index, "
1729	"{2} matched, {3} from identifiers, {4} returned{5}.",
1730	Vals&: NSema, Vals&: NIndex, Vals&: NSemaAndIndex, Vals&: NIdent, Vals: Output.Completions.size(),
1731	Vals: Output.HasMore ? " (incomplete)" : "");
1732	assert(!Opts.Limit || Output.Completions.size() <= Opts.Limit);
1733	// We don't assert that isIncomplete means we hit a limit.
1734	// Indexes may choose to impose their own limits even if we don't have one.
1735	}
1736
1737	CodeCompleteResult runWithoutSema(llvm::StringRef Content, size_t Offset,
1738	const ThreadsafeFS &TFS) && {
1739	trace::Span Tracer("CodeCompleteWithoutSema");
1740	// Fill in fields normally set by runWithSema()
1741	HeuristicPrefix = guessCompletionPrefix(Content, Offset);
1742	populateContextWords(Content);
1743	CCContextKind = CodeCompletionContext::CCC_Recovery;
1744	IsUsingDeclaration = false;
1745	Filter = FuzzyMatcher(HeuristicPrefix.Name);
1746	auto Pos = offsetToPosition(Code: Content, Offset);
1747	ReplacedRange.start = ReplacedRange.end = Pos;
1748	ReplacedRange.start.character -= HeuristicPrefix.Name.size();
1749
1750	llvm::StringMap<SourceParams> ProxSources;
1751	ProxSources[FileName].Cost = 0;
1752	FileProximity.emplace(args&: ProxSources);
1753
1754	auto Style = getFormatStyleForFile(File: FileName, Content, TFS, FormatFile: false);
1755	// This will only insert verbatim headers.
1756	Inserter.emplace(args&: FileName, args&: Content, args&: Style,
1757	/*BuildDir=*/args: "", /*HeaderSearchInfo=*/args: nullptr,
1758	args: Config::current().Style.QuotedHeaders,
1759	args: Config::current().Style.AngledHeaders);
1760
1761	auto Identifiers = collectIdentifiers(Content, Style);
1762	std::vector<RawIdentifier> IdentifierResults;
1763	for (const auto &IDAndCount : Identifiers) {
1764	RawIdentifier ID;
1765	ID.Name = IDAndCount.first();
1766	ID.References = IDAndCount.second;
1767	// Avoid treating typed filter as an identifier.
1768	if (ID.Name == HeuristicPrefix.Name)
1769	--ID.References;
1770	if (ID.References > 0)
1771	IdentifierResults.push_back(x: std::move(ID));
1772	}
1773
1774	// Simplified version of getQueryScopes():
1775	// - accessible scopes are determined heuristically.
1776	// - all-scopes query if no qualifier was typed (and it's allowed).
1777	SpecifiedScope Scopes;
1778	Scopes.QueryScopes = visibleNamespaces(
1779	Code: Content.take_front(N: Offset), LangOpts: format::getFormattingLangOpts(Style));
1780	for (std::string &S : Scopes.QueryScopes)
1781	if (!S.empty())
1782	S.append(s: "::"); // visibleNamespaces doesn't include trailing ::.
1783	if (HeuristicPrefix.Qualifier.empty())
1784	AllScopes = Opts.AllScopes;
1785	else if (HeuristicPrefix.Qualifier.starts_with(Prefix: "::")) {
1786	Scopes.QueryScopes = {""};
1787	Scopes.UnresolvedQualifier =
1788	std::string(HeuristicPrefix.Qualifier.drop_front(N: 2));
1789	} else
1790	Scopes.UnresolvedQualifier = std::string(HeuristicPrefix.Qualifier);
1791	// First scope is the (modified) enclosing scope.
1792	QueryScopes = Scopes.scopesForIndexQuery();
1793	AccessibleScopes = QueryScopes;
1794	ScopeProximity.emplace(args&: QueryScopes);
1795
1796	SymbolSlab IndexResults = Opts.Index ? queryIndex() : SymbolSlab();
1797
1798	CodeCompleteResult Output = toCodeCompleteResult(Scored: mergeResults(
1799	/*SemaResults=*/{}, IndexResults, IdentifierResults));
1800	Output.RanParser = false;
1801	logResults(Output, Tracer);
1802	return Output;
1803	}
1804
1805	private:
1806	void populateContextWords(llvm::StringRef Content) {
1807	// Take last 3 lines before the completion point.
1808	unsigned RangeEnd = HeuristicPrefix.Qualifier.begin() - Content.data(),
1809	RangeBegin = RangeEnd;
1810	for (size_t I = 0; I < 3 && RangeBegin > 0; ++I) {
1811	auto PrevNL = Content.rfind(C: '\n', From: RangeBegin);
1812	if (PrevNL == StringRef::npos) {
1813	RangeBegin = 0;
1814	break;
1815	}
1816	RangeBegin = PrevNL;
1817	}
1818
1819	ContextWords = collectWords(Content: Content.slice(Start: RangeBegin, End: RangeEnd));
1820	dlog("Completion context words: {0}",
1821	llvm::join(ContextWords.keys(), ", "));
1822	}
1823
1824	// This is called by run() once Sema code completion is done, but before the
1825	// Sema data structures are torn down. It does all the real work.
1826	CodeCompleteResult runWithSema() {
1827	const auto &CodeCompletionRange = CharSourceRange::getCharRange(
1828	R: Recorder->CCSema->getPreprocessor().getCodeCompletionTokenRange());
1829	// When we are getting completions with an empty identifier, for example
1830	// std::vector<int> asdf;
1831	// asdf.^;
1832	// Then the range will be invalid and we will be doing insertion, use
1833	// current cursor position in such cases as range.
1834	if (CodeCompletionRange.isValid()) {
1835	ReplacedRange = halfOpenToRange(SM: Recorder->CCSema->getSourceManager(),
1836	R: CodeCompletionRange);
1837	} else {
1838	const auto &Pos = sourceLocToPosition(
1839	SM: Recorder->CCSema->getSourceManager(),
1840	Loc: Recorder->CCSema->getPreprocessor().getCodeCompletionLoc());
1841	ReplacedRange.start = ReplacedRange.end = Pos;
1842	}
1843	Filter = FuzzyMatcher(
1844	Recorder->CCSema->getPreprocessor().getCodeCompletionFilter());
1845	auto SpecifiedScopes = getQueryScopes(
1846	Recorder->CCContext, *Recorder->CCSema, HeuristicPrefix, Opts);
1847
1848	QueryScopes = SpecifiedScopes.scopesForIndexQuery();
1849	AccessibleScopes = SpecifiedScopes.scopesForQualification();
1850	AllScopes = SpecifiedScopes.AllowAllScopes;
1851	if (!QueryScopes.empty())
1852	ScopeProximity.emplace(args&: QueryScopes);
1853	PreferredType =
1854	OpaqueType::fromType(Ctx&: Recorder->CCSema->getASTContext(),
1855	Type: Recorder->CCContext.getPreferredType());
1856	// Sema provides the needed context to query the index.
1857	// FIXME: in addition to querying for extra/overlapping symbols, we should
1858	// explicitly request symbols corresponding to Sema results.
1859	// We can use their signals even if the index can't suggest them.
1860	// We must copy index results to preserve them, but there are at most Limit.
1861	auto IndexResults = (Opts.Index && allowIndex(Recorder->CCContext))
1862	? queryIndex()
1863	: SymbolSlab();
1864	trace::Span Tracer("Populate CodeCompleteResult");
1865	// Merge Sema and Index results, score them, and pick the winners.
1866	auto Top =
1867	mergeResults(SemaResults: Recorder->Results, IndexResults: IndexResults, /*Identifiers*/ IdentifierResults: {});
1868	return toCodeCompleteResult(Scored: Top);
1869	}
1870
1871	CodeCompleteResult
1872	toCodeCompleteResult(const std::vector<ScoredBundle> &Scored) {
1873	CodeCompleteResult Output;
1874
1875	// Convert the results to final form, assembling the expensive strings.
1876	// If necessary, search the index for documentation comments.
1877	LookupRequest Req;
1878	llvm::DenseMap<SymbolID, uint32_t> SymbolToCompletion;
1879	for (auto &C : Scored) {
1880	Output.Completions.push_back(x: toCodeCompletion(Bundle: C.first));
1881	Output.Completions.back().Score = C.second;
1882	Output.Completions.back().CompletionTokenRange = ReplacedRange;
1883	if (Opts.Index && !Output.Completions.back().Documentation) {
1884	for (auto &Cand : C.first) {
1885	if (Cand.SemaResult &&
1886	Cand.SemaResult->Kind == CodeCompletionResult::RK_Declaration) {
1887	auto ID = clangd::getSymbolID(Cand.SemaResult->getDeclaration());
1888	if (!ID)
1889	continue;
1890	Req.IDs.insert(ID);
1891	SymbolToCompletion[ID] = Output.Completions.size() - 1;
1892	}
1893	}
1894	}
1895	}
1896	Output.HasMore = Incomplete;
1897	Output.Context = CCContextKind;
1898	Output.CompletionRange = ReplacedRange;
1899
1900	// Look up documentation from the index.
1901	if (Opts.Index) {
1902	Opts.Index->lookup(Req, Callback: [&](const Symbol &S) {
1903	if (S.Documentation.empty())
1904	return;
1905	auto &C = Output.Completions[SymbolToCompletion.at(Val: S.ID)];
1906	C.Documentation.emplace();
1907	parseDocumentation(Input: S.Documentation, Output&: *C.Documentation);
1908	});
1909	}
1910
1911	return Output;
1912	}
1913
1914	SymbolSlab queryIndex() {
1915	trace::Span Tracer("Query index");
1916	SPAN_ATTACH(Tracer, "limit", int64_t(Opts.Limit));
1917
1918	// Build the query.
1919	FuzzyFindRequest Req;
1920	if (Opts.Limit)
1921	Req.Limit = Opts.Limit;
1922	Req.Query = std::string(Filter->pattern());
1923	Req.RestrictForCodeCompletion = true;
1924	Req.Scopes = QueryScopes;
1925	Req.AnyScope = AllScopes;
1926	// FIXME: we should send multiple weighted paths here.
1927	Req.ProximityPaths.push_back(x: std::string(FileName));
1928	if (PreferredType)
1929	Req.PreferredTypes.push_back(x: std::string(PreferredType->raw()));
1930	vlog(Fmt: "Code complete: fuzzyFind({0:2})", Vals: toJSON(Request: Req));
1931
1932	if (SpecFuzzyFind)
1933	SpecFuzzyFind->NewReq = Req;
1934	if (SpecFuzzyFind && SpecFuzzyFind->Result.valid() && (*SpecReq == Req)) {
1935	vlog(Fmt: "Code complete: speculative fuzzy request matches the actual index "
1936	"request. Waiting for the speculative index results.");
1937	SPAN_ATTACH(Tracer, "Speculative results", true);
1938
1939	trace::Span WaitSpec("Wait speculative results");
1940	auto SpecRes = SpecFuzzyFind->Result.get();
1941	Incomplete |= SpecRes.first;
1942	return std::move(SpecRes.second);
1943	}
1944
1945	SPAN_ATTACH(Tracer, "Speculative results", false);
1946
1947	// Run the query against the index.
1948	SymbolSlab::Builder ResultsBuilder;
1949	Incomplete |= Opts.Index->fuzzyFind(
1950	Req, Callback: [&](const Symbol &Sym) { ResultsBuilder.insert(S: Sym); });
1951	return std::move(ResultsBuilder).build();
1952	}
1953
1954	// Merges Sema and Index results where possible, to form CompletionCandidates.
1955	// \p Identifiers is raw identifiers that can also be completion candidates.
1956	// Identifiers are not merged with results from index or sema.
1957	// Groups overloads if desired, to form CompletionCandidate::Bundles. The
1958	// bundles are scored and top results are returned, best to worst.
1959	std::vector<ScoredBundle>
1960	mergeResults(const std::vector<CodeCompletionResult> &SemaResults,
1961	const SymbolSlab &IndexResults,
1962	const std::vector<RawIdentifier> &IdentifierResults) {
1963	trace::Span Tracer("Merge and score results");
1964	std::vector<CompletionCandidate::Bundle> Bundles;
1965	llvm::DenseMap<size_t, size_t> BundleLookup;
1966	auto AddToBundles = [&](const CodeCompletionResult *SemaResult,
1967	const Symbol *IndexResult,
1968	const RawIdentifier *IdentifierResult) {
1969	CompletionCandidate C;
1970	C.SemaResult = SemaResult;
1971	C.IndexResult = IndexResult;
1972	C.IdentifierResult = IdentifierResult;
1973	if (C.IndexResult) {
1974	C.Name = IndexResult->Name;
1975	C.RankedIncludeHeaders = getRankedIncludes(Sym: *C.IndexResult);
1976	} else if (C.SemaResult) {
1977	C.Name = Recorder->getName(Result: *SemaResult);
1978	} else {
1979	assert(IdentifierResult);
1980	C.Name = IdentifierResult->Name;
1981	}
1982	if (auto OverloadSet = C.overloadSet(
1983	Opts, FileName, Inserter: Inserter ? &*Inserter : nullptr, CCContextKind)) {
1984	auto Ret = BundleLookup.try_emplace(Key: OverloadSet, Args: Bundles.size());
1985	if (Ret.second)
1986	Bundles.emplace_back();
1987	Bundles[Ret.first->second].push_back(Elt: std::move(C));
1988	} else {
1989	Bundles.emplace_back();
1990	Bundles.back().push_back(Elt: std::move(C));
1991	}
1992	};
1993	llvm::DenseSet<const Symbol *> UsedIndexResults;
1994	auto CorrespondingIndexResult =
1995	[&](const CodeCompletionResult &SemaResult) -> const Symbol * {
1996	if (auto SymID =
1997	getSymbolID(R: SemaResult, SM: Recorder->CCSema->getSourceManager())) {
1998	auto I = IndexResults.find(SymID);
1999	if (I != IndexResults.end()) {
2000	UsedIndexResults.insert(V: &*I);
2001	return &*I;
2002	}
2003	}
2004	return nullptr;
2005	};
2006	// Emit all Sema results, merging them with Index results if possible.
2007	for (auto &SemaResult : SemaResults)
2008	AddToBundles(&SemaResult, CorrespondingIndexResult(SemaResult), nullptr);
2009	// Now emit any Index-only results.
2010	for (const auto &IndexResult : IndexResults) {
2011	if (UsedIndexResults.count(V: &IndexResult))
2012	continue;
2013	if (!includeSymbolFromIndex(Kind: CCContextKind, Sym: IndexResult))
2014	continue;
2015	AddToBundles(/*SemaResult=*/nullptr, &IndexResult, nullptr);
2016	}
2017	// Emit identifier results.
2018	for (const auto &Ident : IdentifierResults)
2019	AddToBundles(/*SemaResult=*/nullptr, /*IndexResult=*/nullptr, &Ident);
2020	// We only keep the best N results at any time, in "native" format.
2021	TopN<ScoredBundle, ScoredBundleGreater> Top(
2022	Opts.Limit == 0 ? std::numeric_limits<size_t>::max() : Opts.Limit);
2023	for (auto &Bundle : Bundles)
2024	addCandidate(Candidates&: Top, Bundle: std::move(Bundle));
2025	return std::move(Top).items();
2026	}
2027
2028	std::optional<float> fuzzyScore(const CompletionCandidate &C) {
2029	// Macros can be very spammy, so we only support prefix completion.
2030	if (((C.SemaResult &&
2031	C.SemaResult->Kind == CodeCompletionResult::RK_Macro) ||
2032	(C.IndexResult &&
2033	C.IndexResult->SymInfo.Kind == index::SymbolKind::Macro)) &&
2034	!C.Name.starts_with_insensitive(Prefix: Filter->pattern()))
2035	return std::nullopt;
2036	return Filter->match(Word: C.Name);
2037	}
2038
2039	CodeCompletion::Scores
2040	evaluateCompletion(const SymbolQualitySignals &Quality,
2041	const SymbolRelevanceSignals &Relevance) {
2042	using RM = CodeCompleteOptions::CodeCompletionRankingModel;
2043	CodeCompletion::Scores Scores;
2044	switch (Opts.RankingModel) {
2045	case RM::Heuristics:
2046	Scores.Quality = Quality.evaluateHeuristics();
2047	Scores.Relevance = Relevance.evaluateHeuristics();
2048	Scores.Total =
2049	evaluateSymbolAndRelevance(SymbolQuality: Scores.Quality, SymbolRelevance: Scores.Relevance);
2050	// NameMatch is in fact a multiplier on total score, so rescoring is
2051	// sound.
2052	Scores.ExcludingName =
2053	Relevance.NameMatch > std::numeric_limits<float>::epsilon()
2054	? Scores.Total / Relevance.NameMatch
2055	: Scores.Quality;
2056	return Scores;
2057
2058	case RM::DecisionForest:
2059	DecisionForestScores DFScores = Opts.DecisionForestScorer(
2060	Quality, Relevance, Opts.DecisionForestBase);
2061	Scores.ExcludingName = DFScores.ExcludingName;
2062	Scores.Total = DFScores.Total;
2063	return Scores;
2064	}
2065	llvm_unreachable("Unhandled CodeCompletion ranking model.");
2066	}
2067
2068	// Scores a candidate and adds it to the TopN structure.
2069	void addCandidate(TopN<ScoredBundle, ScoredBundleGreater> &Candidates,
2070	CompletionCandidate::Bundle Bundle) {
2071	SymbolQualitySignals Quality;
2072	SymbolRelevanceSignals Relevance;
2073	Relevance.Context = CCContextKind;
2074	Relevance.Name = Bundle.front().Name;
2075	Relevance.FilterLength = HeuristicPrefix.Name.size();
2076	Relevance.Query = SymbolRelevanceSignals::CodeComplete;
2077	Relevance.FileProximityMatch = &*FileProximity;
2078	if (ScopeProximity)
2079	Relevance.ScopeProximityMatch = &*ScopeProximity;
2080	if (PreferredType)
2081	Relevance.HadContextType = true;
2082	Relevance.ContextWords = &ContextWords;
2083	Relevance.MainFileSignals = Opts.MainFileSignals;
2084
2085	auto &First = Bundle.front();
2086	if (auto FuzzyScore = fuzzyScore(C: First))
2087	Relevance.NameMatch = *FuzzyScore;
2088	else
2089	return;
2090	SymbolOrigin Origin = SymbolOrigin::Unknown;
2091	bool FromIndex = false;
2092	for (const auto &Candidate : Bundle) {
2093	if (Candidate.IndexResult) {
2094	Quality.merge(IndexResult: *Candidate.IndexResult);
2095	Relevance.merge(IndexResult: *Candidate.IndexResult);
2096	Origin |= Candidate.IndexResult->Origin;
2097	FromIndex = true;
2098	if (!Candidate.IndexResult->Type.empty())
2099	Relevance.HadSymbolType |= true;
2100	if (PreferredType &&
2101	PreferredType->raw() == Candidate.IndexResult->Type) {
2102	Relevance.TypeMatchesPreferred = true;
2103	}
2104	}
2105	if (Candidate.SemaResult) {
2106	Quality.merge(SemaCCResult: *Candidate.SemaResult);
2107	Relevance.merge(SemaResult: *Candidate.SemaResult);
2108	if (PreferredType) {
2109	if (auto CompletionType = OpaqueType::fromCompletionResult(
2110	Ctx&: Recorder->CCSema->getASTContext(), R: *Candidate.SemaResult)) {
2111	Relevance.HadSymbolType |= true;
2112	if (PreferredType == CompletionType)
2113	Relevance.TypeMatchesPreferred = true;
2114	}
2115	}
2116	Origin |= SymbolOrigin::AST;
2117	}
2118	if (Candidate.IdentifierResult) {
2119	Quality.References = Candidate.IdentifierResult->References;
2120	Relevance.Scope = SymbolRelevanceSignals::FileScope;
2121	Origin |= SymbolOrigin::Identifier;
2122	}
2123	}
2124
2125	CodeCompletion::Scores Scores = evaluateCompletion(Quality, Relevance);
2126	if (Opts.RecordCCResult)
2127	Opts.RecordCCResult(toCodeCompletion(Bundle), Quality, Relevance,
2128	Scores.Total);
2129
2130	dlog("CodeComplete: {0} ({1}) = {2}\n{3}{4}\n", First.Name,
2131	llvm::to_string(Origin), Scores.Total, llvm::to_string(Quality),
2132	llvm::to_string(Relevance));
2133
2134	NSema += bool(Origin & SymbolOrigin::AST);
2135	NIndex += FromIndex;
2136	NSemaAndIndex += bool(Origin & SymbolOrigin::AST) && FromIndex;
2137	NIdent += bool(Origin & SymbolOrigin::Identifier);
2138	if (Candidates.push(V: {std::move(Bundle), Scores}))
2139	Incomplete = true;
2140	}
2141
2142	CodeCompletion toCodeCompletion(const CompletionCandidate::Bundle &Bundle) {
2143	std::optional<CodeCompletionBuilder> Builder;
2144	for (const auto &Item : Bundle) {
2145	CodeCompletionString *SemaCCS =
2146	Item.SemaResult ? Recorder->codeCompletionString(R: *Item.SemaResult)
2147	: nullptr;
2148	if (!Builder)
2149	Builder.emplace(args: Recorder ? &Recorder->CCSema->getASTContext() : nullptr,
2150	args: Item, args&: SemaCCS, args&: AccessibleScopes, args&: *Inserter, args&: FileName,
2151	args&: CCContextKind, args: Opts, args&: IsUsingDeclaration, args&: NextTokenKind);
2152	else
2153	Builder->add(C: Item, SemaCCS, ContextKind: CCContextKind);
2154	}
2155	return Builder->build();
2156	}
2157	};
2158
2159	} // namespace
2160
2161	clang::CodeCompleteOptions CodeCompleteOptions::getClangCompleteOpts() const {
2162	clang::CodeCompleteOptions Result;
2163	Result.IncludeCodePatterns =
2164	EnableSnippets && (CodePatterns != Config::CodePatternsPolicy::None);
2165	Result.IncludeMacros = true;
2166	Result.IncludeGlobals = true;
2167	// We choose to include full comments and not do doxygen parsing in
2168	// completion.
2169	// FIXME: ideally, we should support doxygen in some form, e.g. do markdown
2170	// formatting of the comments.
2171	Result.IncludeBriefComments = false;
2172
2173	// When an is used, Sema is responsible for completing the main file,
2174	// the index can provide results from the preamble.
2175	// Tell Sema not to deserialize the preamble to look for results.
2176	Result.LoadExternal = ForceLoadPreamble || !Index;
2177	Result.IncludeFixIts = IncludeFixIts;
2178
2179	return Result;
2180	}
2181
2182	CompletionPrefix guessCompletionPrefix(llvm::StringRef Content,
2183	unsigned Offset) {
2184	assert(Offset <= Content.size());
2185	StringRef Rest = Content.take_front(N: Offset);
2186	CompletionPrefix Result;
2187
2188	// Consume the unqualified name. We only handle ASCII characters.
2189	// isAsciiIdentifierContinue will let us match "0invalid", but we don't mind.
2190	while (!Rest.empty() && isAsciiIdentifierContinue(c: Rest.back()))
2191	Rest = Rest.drop_back();
2192	Result.Name = Content.slice(Start: Rest.size(), End: Offset);
2193
2194	// Consume qualifiers.
2195	while (Rest.consume_back(Suffix: "::") && !Rest.ends_with(Suffix: ":")) // reject ::::
2196	while (!Rest.empty() && isAsciiIdentifierContinue(c: Rest.back()))
2197	Rest = Rest.drop_back();
2198	Result.Qualifier =
2199	Content.slice(Start: Rest.size(), End: Result.Name.begin() - Content.begin());
2200
2201	return Result;
2202	}
2203
2204	// Code complete the argument name on "/*" inside function call.
2205	// Offset should be pointing to the start of the comment, i.e.:
2206	// foo(^/*, rather than foo(/*^) where the cursor probably is.
2207	CodeCompleteResult codeCompleteComment(PathRef FileName, unsigned Offset,
2208	llvm::StringRef Prefix,
2209	const PreambleData *Preamble,
2210	const ParseInputs &ParseInput) {
2211	if (Preamble == nullptr) // Can't run without Sema.
2212	return CodeCompleteResult();
2213
2214	clang::CodeCompleteOptions Options;
2215	Options.IncludeGlobals = false;
2216	Options.IncludeMacros = false;
2217	Options.IncludeCodePatterns = false;
2218	Options.IncludeBriefComments = false;
2219	std::set<std::string> ParamNames;
2220	// We want to see signatures coming from newly introduced includes, hence a
2221	// full patch.
2222	semaCodeComplete(
2223	Consumer: std::make_unique<ParamNameCollector>(args&: Options, args&: ParamNames), Options,
2224	Input: {.FileName: FileName, .Offset: Offset, .Preamble: *Preamble,
2225	.Patch: PreamblePatch::createFullPatch(FileName, Modified: ParseInput, Baseline: *Preamble),
2226	.ParseInput: ParseInput});
2227	if (ParamNames.empty())
2228	return CodeCompleteResult();
2229
2230	CodeCompleteResult Result;
2231	Range CompletionRange;
2232	// Skip /*
2233	Offset += 2;
2234	CompletionRange.start = offsetToPosition(Code: ParseInput.Contents, Offset);
2235	CompletionRange.end =
2236	offsetToPosition(Code: ParseInput.Contents, Offset: Offset + Prefix.size());
2237	Result.CompletionRange = CompletionRange;
2238	Result.Context = CodeCompletionContext::CCC_NaturalLanguage;
2239	for (llvm::StringRef Name : ParamNames) {
2240	if (!Name.starts_with(Prefix))
2241	continue;
2242	CodeCompletion Item;
2243	Item.Name = Name.str() + "=*/";
2244	Item.FilterText = Item.Name;
2245	Item.Kind = CompletionItemKind::Text;
2246	Item.CompletionTokenRange = CompletionRange;
2247	Item.Origin = SymbolOrigin::AST;
2248	Result.Completions.push_back(x: Item);
2249	}
2250
2251	return Result;
2252	}
2253
2254	// If Offset is inside what looks like argument comment (e.g.
2255	// "/*^" or "/* foo^"), returns new offset pointing to the start of the /*
2256	// (place where semaCodeComplete should run).
2257	std::optional<unsigned>
2258	maybeFunctionArgumentCommentStart(llvm::StringRef Content) {
2259	while (!Content.empty() && isAsciiIdentifierContinue(c: Content.back()))
2260	Content = Content.drop_back();
2261	Content = Content.rtrim();
2262	if (Content.ends_with(Suffix: "/*"))
2263	return Content.size() - 2;
2264	return std::nullopt;
2265	}
2266
2267	CodeCompleteResult codeComplete(PathRef FileName, Position Pos,
2268	const PreambleData *Preamble,
2269	const ParseInputs &ParseInput,
2270	CodeCompleteOptions Opts,
2271	SpeculativeFuzzyFind *SpecFuzzyFind) {
2272	auto Offset = positionToOffset(Code: ParseInput.Contents, P: Pos);
2273	if (!Offset) {
2274	elog(Fmt: "Code completion position was invalid {0}", Vals: Offset.takeError());
2275	return CodeCompleteResult();
2276	}
2277
2278	auto Content = llvm::StringRef(ParseInput.Contents).take_front(N: *Offset);
2279	if (auto OffsetBeforeComment = maybeFunctionArgumentCommentStart(Content)) {
2280	// We are doing code completion of a comment, where we currently only
2281	// support completing param names in function calls. To do this, we
2282	// require information from Sema, but Sema's comment completion stops at
2283	// parsing, so we must move back the position before running it, extract
2284	// information we need and construct completion items ourselves.
2285	auto CommentPrefix = Content.substr(Start: *OffsetBeforeComment + 2).trim();
2286	return codeCompleteComment(FileName, Offset: *OffsetBeforeComment, Prefix: CommentPrefix,
2287	Preamble, ParseInput);
2288	}
2289
2290	auto Flow = CodeCompleteFlow(
2291	FileName, Preamble ? Preamble->Includes : IncludeStructure(),
2292	SpecFuzzyFind, Opts);
2293	return (!Preamble || Opts.RunParser == CodeCompleteOptions::NeverParse)
2294	? std::move(Flow).runWithoutSema(Content: ParseInput.Contents, Offset: *Offset,
2295	TFS: *ParseInput.TFS)
2296	: std::move(Flow).run(SemaCCInput: {.FileName: FileName, .Offset: *Offset, .Preamble: *Preamble,
2297	/*PreamblePatch=*/
2298	.Patch: PreamblePatch::createMacroPatch(
2299	FileName, Modified: ParseInput, Baseline: *Preamble),
2300	.ParseInput: ParseInput});
2301	}
2302
2303	SignatureHelp signatureHelp(PathRef FileName, Position Pos,
2304	const PreambleData &Preamble,
2305	const ParseInputs &ParseInput,
2306	MarkupKind DocumentationFormat) {
2307	auto Offset = positionToOffset(Code: ParseInput.Contents, P: Pos);
2308	if (!Offset) {
2309	elog(Fmt: "Signature help position was invalid {0}", Vals: Offset.takeError());
2310	return SignatureHelp();
2311	}
2312	SignatureHelp Result;
2313	clang::CodeCompleteOptions Options;
2314	Options.IncludeGlobals = false;
2315	Options.IncludeMacros = false;
2316	Options.IncludeCodePatterns = false;
2317	Options.IncludeBriefComments = false;
2318	semaCodeComplete(
2319	Consumer: std::make_unique<SignatureHelpCollector>(args&: Options, args&: DocumentationFormat,
2320	args: ParseInput.Index, args&: Result),
2321	Options,
2322	Input: {.FileName: FileName, .Offset: *Offset, .Preamble: Preamble,
2323	.Patch: PreamblePatch::createFullPatch(FileName, Modified: ParseInput, Baseline: Preamble),
2324	.ParseInput: ParseInput});
2325	return Result;
2326	}
2327
2328	bool isIndexedForCodeCompletion(const NamedDecl &ND, ASTContext &ASTCtx) {
2329	auto InTopLevelScope = [](const NamedDecl &ND) {
2330	switch (ND.getDeclContext()->getDeclKind()) {
2331	case Decl::TranslationUnit:
2332	case Decl::Namespace:
2333	case Decl::LinkageSpec:
2334	return true;
2335	default:
2336	break;
2337	};
2338	return false;
2339	};
2340	auto InClassScope = [](const NamedDecl &ND) {
2341	return ND.getDeclContext()->getDeclKind() == Decl::CXXRecord;
2342	};
2343	// We only complete symbol's name, which is the same as the name of the
2344	// *primary* template in case of template specializations.
2345	if (isExplicitTemplateSpecialization(D: &ND))
2346	return false;
2347
2348	// Category decls are not useful on their own outside the interface or
2349	// implementation blocks. Moreover, sema already provides completion for
2350	// these, even if it requires preamble deserialization. So by excluding them
2351	// from the index, we reduce the noise in all the other completion scopes.
2352	if (llvm::isa<ObjCCategoryDecl>(Val: &ND) || llvm::isa<ObjCCategoryImplDecl>(Val: &ND))
2353	return false;
2354
2355	if (InTopLevelScope(ND))
2356	return true;
2357
2358	// Always index enum constants, even if they're not in the top level scope:
2359	// when
2360	// --all-scopes-completion is set, we'll want to complete those as well.
2361	if (const auto *EnumDecl = dyn_cast<clang::EnumDecl>(ND.getDeclContext()))
2362	return (InTopLevelScope(*EnumDecl) || InClassScope(*EnumDecl));
2363
2364	return false;
2365	}
2366
2367	CompletionItem CodeCompletion::render(const CodeCompleteOptions &Opts) const {
2368	CompletionItem LSP;
2369	const auto *InsertInclude = Includes.empty() ? nullptr : &Includes[0];
2370	// We could move our indicators from label into labelDetails->description.
2371	// In VSCode there are rendering issues that prevent these being aligned.
2372	LSP.label = ((InsertInclude && InsertInclude->Insertion)
2373	? Opts.IncludeIndicator.Insert
2374	: Opts.IncludeIndicator.NoInsert) +
2375	(Opts.ShowOrigins ? "[" + llvm::to_string(Value: Origin) + "]" : "") +
2376	RequiredQualifier + Name;
2377	LSP.labelDetails.emplace();
2378	LSP.labelDetails->detail = Signature;
2379
2380	LSP.kind = Kind;
2381	LSP.detail = BundleSize > 1
2382	? std::string(llvm::formatv(Fmt: "[{0} overloads]", Vals: BundleSize))
2383	: ReturnType;
2384	LSP.deprecated = Deprecated;
2385	// Combine header information and documentation in LSP `documentation` field.
2386	// This is not quite right semantically, but tends to display well in editors.
2387	if (InsertInclude || Documentation) {
2388	markup::Document Doc;
2389	if (InsertInclude)
2390	Doc.addParagraph().appendText(Text: "From ").appendCode(Code: InsertInclude->Header);
2391	if (Documentation)
2392	Doc.append(Other: *Documentation);
2393	LSP.documentation = renderDoc(Doc, Kind: Opts.DocumentationFormat);
2394	}
2395	LSP.sortText = sortText(Score: Score.Total, Tiebreak: FilterText);
2396	LSP.filterText = FilterText;
2397	LSP.textEdit = {.range: CompletionTokenRange, .newText: RequiredQualifier + Name, .annotationId: ""};
2398	// Merge continuous additionalTextEdits into main edit. The main motivation
2399	// behind this is to help LSP clients, it seems most of them are confused when
2400	// they are provided with additionalTextEdits that are consecutive to main
2401	// edit.
2402	// Note that we store additional text edits from back to front in a line. That
2403	// is mainly to help LSP clients again, so that changes do not effect each
2404	// other.
2405	for (const auto &FixIt : FixIts) {
2406	if (FixIt.range.end == LSP.textEdit->range.start) {
2407	LSP.textEdit->newText = FixIt.newText + LSP.textEdit->newText;
2408	LSP.textEdit->range.start = FixIt.range.start;
2409	} else {
2410	LSP.additionalTextEdits.push_back(x: FixIt);
2411	}
2412	}
2413	if (Opts.EnableSnippets)
2414	LSP.textEdit->newText += SnippetSuffix;
2415
2416	// FIXME(kadircet): Do not even fill insertText after making sure textEdit is
2417	// compatible with most of the editors.
2418	LSP.insertText = LSP.textEdit->newText;
2419	// Some clients support snippets but work better with plaintext.
2420	// So if the snippet is trivial, let the client know.
2421	// https://github.com/clangd/clangd/issues/922
2422	LSP.insertTextFormat = (Opts.EnableSnippets && !SnippetSuffix.empty())
2423	? InsertTextFormat::Snippet
2424	: InsertTextFormat::PlainText;
2425	if (InsertInclude && InsertInclude->Insertion)
2426	LSP.additionalTextEdits.push_back(x: *InsertInclude->Insertion);
2427
2428	LSP.score = Score.ExcludingName;
2429
2430	return LSP;
2431	}
2432
2433	llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const CodeCompletion &C) {
2434	// For now just lean on CompletionItem.
2435	return OS << C.render(Opts: CodeCompleteOptions());
2436	}
2437
2438	llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
2439	const CodeCompleteResult &R) {
2440	OS << "CodeCompleteResult: " << R.Completions.size() << (R.HasMore ? "+" : "")
2441	<< " (" << getCompletionKindString(Kind: R.Context) << ")"
2442	<< " items:\n";
2443	for (const auto &C : R.Completions)
2444	OS << C << "\n";
2445	return OS;
2446	}
2447
2448	// Heuristically detect whether the `Line` is an unterminated include filename.
2449	bool isIncludeFile(llvm::StringRef Line) {
2450	Line = Line.ltrim();
2451	if (!Line.consume_front(Prefix: "#"))
2452	return false;
2453	Line = Line.ltrim();
2454	if (!(Line.consume_front(Prefix: "include_next") || Line.consume_front(Prefix: "include") ||
2455	Line.consume_front(Prefix: "import")))
2456	return false;
2457	Line = Line.ltrim();
2458	if (Line.consume_front(Prefix: "<"))
2459	return Line.count(C: '>') == 0;
2460	if (Line.consume_front(Prefix: "\""))
2461	return Line.count(C: '"') == 0;
2462	return false;
2463	}
2464
2465	bool allowImplicitCompletion(llvm::StringRef Content, unsigned Offset) {
2466	// Look at last line before completion point only.
2467	Content = Content.take_front(N: Offset);
2468	auto Pos = Content.rfind(C: '\n');
2469	if (Pos != llvm::StringRef::npos)
2470	Content = Content.substr(Start: Pos + 1);
2471
2472	// Complete after scope operators.
2473	if (Content.ends_with(Suffix: ".") || Content.ends_with(Suffix: "->") ||
2474	Content.ends_with(Suffix: "::") || Content.ends_with(Suffix: "/*"))
2475	return true;
2476	// Complete after `#include <` and #include `<foo/`.
2477	if ((Content.ends_with(Suffix: "<") || Content.ends_with(Suffix: "\"") ||
2478	Content.ends_with(Suffix: "/")) &&
2479	isIncludeFile(Line: Content))
2480	return true;
2481
2482	// Complete words. Give non-ascii characters the benefit of the doubt.
2483	return !Content.empty() && (isAsciiIdentifierContinue(c: Content.back()) ||
2484	!llvm::isASCII(C: Content.back()));
2485	}
2486
2487	} // namespace clangd
2488	} // namespace clang
2489