[clangd] Support multiple sema code completion callbacks.

[ioeric]

Summary

Currently, we only handle the first callback from sema code completion
and ignore results from potential following callbacks. This causes
causes loss of completion results when multiple contexts are tried by Sema.

For example, we wouldn't get any completion result in the following completion
as the first attemped context is natural language which has no
candidate. The parser would backtrack and tried a completion with AST
semantic, which would find candidate "::x".

void f(const char*, int);
#define F(x) f(#x, x)
int x;
void main() {
	F(::^);
}

[ilya-biryukov]

clangd/CodeComplete.cpp

457

Could we fix this in the first attempt?
All the code around completion is really not prepared for multiple callbacks: index will be queried multiple times, we will store and log only the last CCContext, not all of them, etc.
I'd argue we should aim to either provide a single-callback completion or rewrite the whole code around completion to properly handle multiple callbacks (i.e. with deduplication and proper merging of the results coming from multiple callbacks, proper logging, no multiple identical requests to the index).

I would suggest the following measures as a hacky intermediate solution:

• Ignore natural language completion. The rationale: VSCode does analogous completion on empty results anyway, AFAIK clang does not provide any useful results on top of that. Other clients that we have can (and should?) probably do the same.
• Only record the first non-natural language completion attempt. Ignore the rest and log the failed attempts.

[ioeric]

clangd/CodeComplete.cpp

457

index will be queried multiple times

Patterns of multi-context callbacks I've seen are:

1. natural language + Name: this happens mostly when parsing macros with stringification.
2. name + name: this happens in the pre-existing unit test case. I don't really understand why and how often this comes up, but I think the duplication should be eliminated.
3. language+recovery: haven't looked into what the recovery context does.

we will store and log only the last CCContext

What's the concern about storing only the last context?

I'd argue we should aim to either provide a single-callback completion or rewrite the whole code around completion to properly handle multiple callbacks (

I'm not sure how we could (fully) get away with one callback without significantly changing sema parsing. This seems to be an expensive approach though.

with deduplication and proper merging of the results coming from multiple callbacks

I agree. My impression is that multiple callbacks are not common and thus not as important (duplicates are better than no results IMO). But I might be wrong thinking this is uncommon. I was going to do this in a followup patch to avoid a big patch, but I'm happy to do the deduplication in the same patch if you prefer.

proper logging

Could you point out what logging is missing?

no multiple identical requests to the index

For context combinations I've seen (natural language + name, natural language + recovery), index is still queries once. If sema does decide to call name multiple times with context that would potentially yield two index queries, we could still need to query indexes twice (don't see a big problems doing this if not a common case). For identical context that is called multiple times, we could cache potentially results.

I would suggest the following measures as a hacky intermediate solution:

I think natural language is only one of the contexts that could result in multiple callbacks, so I don't think this would fully resolve our problems.

[ilya-biryukov]

clangd/CodeComplete.cpp

457

What's the concern about storing only the last context?

If we store just one context, the code might look as if there was only one callback. I was trying to make a point that 1) storing a list of contexts or 2) not storing the context at all, are the two options that seem to be more suitable for multi-callback case.

I'm not sure how we could (fully) get away with one callback without significantly changing sema parsing. This seems to be an expensive approach though.

Yeah, there's certainly no way we can change sema parsing.
What we could do, though, is to not call code completion during tentative parsing. This shouldn't be too hard and that's certainly the only case that can give new interesting results in practice, i.e. doing natural language/recovery twice will certainly not change the results.

Could you point out what logging is missing?

Signalling that there were multiple completion callbacks, showing context for each of those, etc. We seem to log individual callbacks currently, but a small summary of how many callbacks were called would be nice too.

no multiple identical requests to the index

For context combinations I've seen (natural language + name, natural language + recovery), index is still queries once. If sema does decide to call name multiple times with context that would potentially yield two index queries, we could still need to query indexes twice (don't see a big problems doing this if not a common case). For identical context that is called multiple times, we could cache potentially results.

IIUC, multiple callbacks can also happen because of the tentative parsing. It means we could easily get lots of callbacks on ambiguous C++ grammar constructs.
We just need to make sure we don't do identical calls to the index in those cases. Caching index requests in the ongoing completion should definitely do it.

I would suggest the following measures as a hacky intermediate solution:

I think natural language is only one of the contexts that could result in multiple callbacks, so I don't think this would fully resolve our problems.

From my observations, all sema (i.e. non-recovery/natural lang) contexts provide mostly similar results or don't trigger together, i.e. we won't ever get non-member completion after member completions.
In theory, current completion API can provide results that we're gonna miss if we ignore other contexts.
In practice, I bet we would be fine.

That being said, merging of completion results is also an option that seems good. Albeit, I think that's something clang should handle in its code completion internally and clients shouldn't care about.

[ioeric]

OK, it turned out that there are a few things that I overlooked:

1. Top-N Ranking would be broken among different callbacks. We would need to keep a single TopN for all callbacks.
2. Due to 1), materialization of TopN candidates would happen after all callbacks have finished but before sema is destroyed. The problem is that the lifetime of completion results from one sema callback do not always outlive the callback, which would break our lazy materialization.

I think multi-callback support should require more careful design. And to fix the code completion in macros, I'll do the context filtering (as Ilya suggested) for now.

[ioeric]

Dropping this in favor of D47256

clangd/CodeComplete.cpp

struct CompletionRecorder : public CodeCompleteConsumer {
   std::vector<CodeCompletionResult> Results;
   CodeCompletionContext CCContext;
   Sema *CCSema = nullptr; // Sema that created the results.
   // FIXME: Sema is scary. Can we store ASTContext and Preprocessor, instead?
 
   void ProcessCodeCompleteResults(class Sema &S, CodeCompletionContext Context,
                                   CodeCompletionResult *InResults,
                                   unsigned NumResults) override final {
-    if (CCSema) {
-      log(llvm::formatv(
-          "Multiple code complete callbacks (parser backtracked?). "
-          "Dropping results from context {0}, keeping results from {1}.",
-          getCompletionKindString(this->CCContext.getKind()),
-          getCompletionKindString(Context.getKind())));
-      return;
-    }
+    log("Processing completion results in context " +
+        getCompletionKindString(Context.getKind()));
     // Record the completion context.
     CCSema = &S;
     CCContext = Context;
 
     // Retain the results we might want.
     for (unsigned I = 0; I < NumResults; ++I) {
       auto &Result = InResults[I];
       // Drop hidden items which cannot be found by lookup after completion.
       // Exception: some items can be named by using a qualifier.
       if (Result.Hidden && (!Result.Qualifier || Result.QualifierIsInformative))
         continue;
       if (!Opts.IncludeIneligibleResults &&
           (Result.Availability == CXAvailability_NotAvailable ||
            Result.Availability == CXAvailability_NotAccessible))
         continue;
       // Destructor completion is rarely useful, and works inconsistently.
       // (s.^ completes ~string, but s.~st^ is an error).
       if (dyn_cast_or_null<CXXDestructorDecl>(Result.Declaration))
         continue;
       // We choose to never append '::' to completion results in clangd.
       Result.StartsNestedNameSpecifier = false;
+      // FIXME: the same result can be added multiple times as the callback can
+      // be called more than once. We may want to deduplicate identical results.
       Results.push_back(Result);
     }
     ResultsCallback();
   }
 
   CodeCompletionAllocator &getAllocator() override { return *CCAllocator; }
   CodeCompletionTUInfo &getCodeCompletionTUInfo() override { return CCTUInfo; }
 
Clang->getPreprocessor().addPPCallbacks(collectInclusionsInMainFileCallback(
           Includes->get()->addExisting(std::move(Inc));
         }));
   }
   if (!Action.Execute()) {
     log("Execute() failed when running codeComplete for " + Input.FileName);
     return false;
   }
   Action.EndSourceFile();
+  if (Includes)
+    Includes->reset(); // Make sure this doesn't out-live Clang.
 
   return true;
 }
 
 // Should we perform index-based completion in a context of the specified kind?
 // FIXME: consider allowing completion, but restricting the result types.
 bool contextAllowsIndex(enum CodeCompletionContext::Kind K) {
   switch (K) {
CompletionList run(const SemaCompleteInput &SemaCCInput) && {
     //   - completion results based on the AST.
     //   - partial identifier and context. We need these for the index query.
     CompletionList Output;
     auto RecorderOwner = llvm::make_unique<CompletionRecorder>(Opts, [&]() {
       assert(Recorder && "Recorder is not set");
       assert(Includes && "Includes is not set");
       // If preprocessor was run, inclusions from preprocessor callback should
       // already be added to Inclusions.
-      Output = runWithSema();
-      Includes.reset(); // Make sure this doesn't out-live Clang.
+      auto Items = runWithSema();
+      Output.items.insert(Output.items.end(),
+                          std::make_move_iterator(Items.begin()),
+                          std::make_move_iterator(Items.end()));
       SPAN_ATTACH(Tracer, "sema_completion_kind",
                   getCompletionKindString(Recorder->CCContext.getKind()));
     });
 
     Recorder = RecorderOwner.get();
     semaCodeComplete(std::move(RecorderOwner), Opts.getClangCompleteOpts(),
                      SemaCCInput, &Includes);
 
     SPAN_ATTACH(Tracer, "sema_results", NSema);
     SPAN_ATTACH(Tracer, "index_results", NIndex);
     SPAN_ATTACH(Tracer, "merged_results", NBoth);
     SPAN_ATTACH(Tracer, "returned_results", Output.items.size());
     SPAN_ATTACH(Tracer, "incomplete", Output.isIncomplete);
     log(llvm::formatv("Code complete: {0} results from Sema, {1} from Index, "
                       "{2} matched, {3} returned{4}.",
                       NSema, NIndex, NBoth, Output.items.size(),
                       Output.isIncomplete ? " (incomplete)" : ""));
     assert(!Opts.Limit || Output.items.size() <= Opts.Limit);
+    Output.isIncomplete = Incomplete;
     // We don't assert that isIncomplete means we hit a limit.
     // Indexes may choose to impose their own limits even if we don't have one.
     return Output;
   }
 
 private:
   // This is called by run() once Sema code completion is done, but before the
   // Sema data structures are torn down. It does all the real work.
-  CompletionList runWithSema() {
+  std::vector<CompletionItem> runWithSema() {
     Filter = FuzzyMatcher(
         Recorder->CCSema->getPreprocessor().getCodeCompletionFilter());
     // Sema provides the needed context to query the index.
     // FIXME: in addition to querying for extra/overlapping symbols, we should
     //        explicitly request symbols corresponding to Sema results.
     //        We can use their signals even if the index can't suggest them.
     // We must copy index results to preserve them, but there are at most Limit.
     auto IndexResults = queryIndex();
     // Merge Sema and Index results, score them, and pick the winners.
     auto Top = mergeResults(Recorder->Results, IndexResults);
     // Convert the results to the desired LSP structs.
-    CompletionList Output;
+    std::vector<CompletionItem> Output;
     for (auto &C : Top)
-      Output.items.push_back(toCompletionItem(C.first, C.second));
-    Output.isIncomplete = Incomplete;
+      Output.push_back(toCompletionItem(C.first, C.second));
     return Output;
   }
 
   SymbolSlab queryIndex() {
     if (!Opts.Index || !allowIndex(Recorder->CCContext))
       return SymbolSlab();
     trace::Span Tracer("Query index");
     SPAN_ATTACH(Tracer, "limit", Opts.Limit);

unittests/clangd/CodeCompleteTests.cpp

auto Results = completions(R"cpp(
     }
   )cpp");
 
   EXPECT_THAT(Results.items, Contains(Labeled("clang")));
   EXPECT_THAT(Results.items, Not(Contains(Labeled("clang::"))));
 }
 
 TEST(CompletionTest, BacktrackCrashes) {
-  // Sema calls code completion callbacks twice in these cases.
   auto Results = completions(R"cpp(
       namespace ns {
       struct FooBarBaz {};
       } // namespace ns
 
      int foo(ns::FooBar^
   )cpp");
 
-  EXPECT_THAT(Results.items, ElementsAre(Labeled("FooBarBaz")));
+  // Sema calls code completion callbacks twice in these cases.
+  // FIXME: deduplicate identical results.
+  EXPECT_THAT(Results.items, Contains(Labeled("FooBarBaz")));
 
   // Check we don't crash in that case too.
   completions(R"cpp(
     struct FooBarBaz {};
     void test() {
       if (FooBarBaz * x^) {}
     }
 )cpp");
 }
 
+TEST(CompletionTest, CompleteInMacroWithStringification) {
+  auto Results = completions(R"cpp(
+void f(const char *, int x);
+#define F(x) f(#x, x)
+
+namespace ns {
+int X;
+int Y;
+}  // namespace ns
+
+int f(int input_num) {
+  F(ns::^)
+}
+    }
+)cpp");
+
+  EXPECT_THAT(Results.items,
+              UnorderedElementsAre(Named("X"), Named("Y")));
+}
+
 TEST(CompletionTest, CompleteInExcludedPPBranch) {
   auto Results = completions(R"cpp(
     int bar(int param_in_bar) {
     }
 
     int foo(int param_in_foo) {
 #if 0
   par^