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