[clangd] Suggest code-completions for overriding base class virtual methods.

[kadircet]

Summary

Whenever a code-completion is triggered within a class/struct/union looks at
base classes and figures out non-overriden virtual functions. Than suggests
completions for those.

[hokein]

I think it is reasonable to make Sema support suggesting override methods, instead of implementing it in clangd side?

clangd/CodeComplete.cpp

206

nit: CR->methods().

210

nit: we can simplify the code like Overrides[Name].push_back(Method).

219

I think we should check whether BR == nullptr here.

1247

It seems that we treat it as a special case, the code path here runs out of the ranking path.

[kadircet]

• Put overrides through scoring and resolve nits.

[kadircet]

clangd/CodeComplete.cpp

1247

Put override suggestions to ranking system.

[ioeric]

In D50898#1205756, @hokein wrote:

I think it is reasonable to make Sema support suggesting override methods, instead of implementing it in clangd side?

drive-by: +1 to this.

[kadircet]

After today's offline discussion I suppose we are not going to implement it within Sema. And also I think getVirtualNonOverridenMethods is a pretty generic function that has no ties to clangd, so it can be easily moved into Sema. Should we still move it into a separate file or leave it there?

[hokein]

Looks good mostly, a few nits. We should make sure all related comments are updated accordingly

clangd/CodeComplete.cpp

198

Since we are returning CodeCompletionResult, maybe naming it like getNonOverridenCompleteionResults is clearer?

222

nit: Can't we use Overrides.find(Method->getName()) and the other places as well?

224

nit: use {} around the body of if -- the one-line for statement is across line, adding {} around it will improve the readability.

1237–1238

nit: we need to update the comment accordingly.

1280–1283

here as well.

1324

IIUC, we are treating the override results the same SemaResult, it is safe as long as Sema doesn't provide these overrides in its code completion results, otherwise we will have duplicated completion items?

I think we probably need a proper comment explaining what's going on here.

[kadircet]

• Resolve discussions.
• Fix a bug inside summarizeOverride.

[hokein]

Thanks, LGTM.

clangd/CodeComplete.cpp

210

nit: here as well, use Overrides[Method->getName()].push_back...

[kadircet]

• Resolve discussions.

[kadircet]

• Resolve discussions.
• Move override generation logic from render to item generation so that internal clients can use it as well, also use a boolean for checking override status of a bundle to be more efficient.
• Change unittests accordingly, get rid of unused IsOverride field.

[hokein]

still LG.

clangd/CodeComplete.h

struct CodeCompletion {
 
   /// Holds information about small corrections that needs to be done. Like
   /// converting '->' to '.' on member access.
   std::vector<TextEdit> FixIts;
 
   /// Holds the range of the token we are going to replace with this completion.
   Range CompletionTokenRange;
 
+  /// Whether this completion is for overriding a virtual method.
+  bool IsOverride = false;
+
   // Scores are used to rank completion items.
   struct Scores {
     // The score that items are ranked by.
     float Total = 0.f;
 
     // The finalScore with the fuzzy name match score excluded.
     // When filtering client-side, editors should calculate the new fuzzy score,
     // whose scale is 0-1 (with 1 = prefix match, special case 2 = exact match),

clangd/CodeComplete.cpp

if (!IncludePath->empty())
     return HeaderFile{std::move(*IncludePath), /*Verbatim=*/true};
 
   auto Resolved = URI::resolve(*U, HintPath);
   if (!Resolved)
     return Resolved.takeError();
   return HeaderFile{std::move(*Resolved), /*Verbatim=*/false};
 }
 
+// First traverses all method definitions inside current class/struct/union
+// definition. Than traverses base classes to find virtual methods that haven't
+// been overriden within current context.
+// FIXME(kadircet): Currently we cannot see declarations below completion point.
+// It is because Sema gets run only upto completion point. Need to find a
+// solution to run it for the whole class/struct/union definition.
+static std::vector<CodeCompletionResult>
+getNonOverridenMethodCompletionResults(const DeclContext *DC, Sema *S) {
+  const auto *CR = llvm::dyn_cast<CXXRecordDecl>(DC);
+  // If not inside a class/struct/union return empty.
+  if (!CR)
+    return {};
+  // First store overrides within current class.
+  // These are stored by name to make querying fast in the later step.
+  llvm::StringMap<std::vector<FunctionDecl *>> Overrides;
+  for (auto *Method : CR->methods()) {
+    if (!Method->isVirtual())
+      continue;
+    const std::string Name = Method->getNameAsString();
+    Overrides[Name].push_back(Method);
+  }
+
+  std::vector<CodeCompletionResult> Results;
+  for (const auto &Base : CR->bases()) {
+    const auto *BR = Base.getType().getTypePtr()->getAsCXXRecordDecl();
+    if (!BR)
+      continue;
+    for (auto *Method : BR->methods()) {
+      if (!Method->isVirtual())
+        continue;
+      const auto it = Overrides.find(Method->getName());
+      bool IsOverriden = false;
+      if (it != Overrides.end()) {
+        for (auto *MD : it->second) {
+          // If the method in current body is not an overload of this virtual
+          // function, that it overrides this one.
+          if (!S->IsOverload(MD, Method, false)) {
+            IsOverriden = true;
+            break;
+          }
+        }
+      }
+      if (!IsOverriden)
+        Results.emplace_back(Method, 0);
+    }
+  }
+
+  return Results;
+}
+
 /// A code completion result, in clang-native form.
 /// It may be promoted to a CompletionItem if it's among the top-ranked results.
 struct CompletionCandidate {
   llvm::StringRef Name; // Used for filtering and sorting.
   // We may have a result from Sema, from the index, or both.
   const CodeCompletionResult *SemaResult = nullptr;
   const Symbol *IndexResult = nullptr;
 
+  // States whether this item is an override suggestion.
+  bool IsOverride = false;
+
   // Returns a token identifying the overload set this is part of.
   // 0 indicates it's not part of any overload set.
   size_t overloadSet() const {
     SmallString<256> Scratch;
     if (IndexResult) {
       switch (IndexResult->SymInfo.Kind) {
       case index::SymbolKind::ClassMethod:
       case index::SymbolKind::InstanceMethod:
void add(const CompletionCandidate &C, CodeCompletionString *SemaCCS) {
     }
     if (ExtractDocumentation && Completion.Documentation.empty()) {
       if (C.IndexResult && C.IndexResult->Detail)
         Completion.Documentation = C.IndexResult->Detail->Documentation;
       else if (C.SemaResult)
         Completion.Documentation = getDocComment(ASTCtx, *C.SemaResult,
                                                  /*CommentsFromHeader=*/false);
     }
+    if (C.IsOverride)
+      S.OverrideSuffix = "override";
   }
 
   CodeCompletion build() {
     Completion.ReturnType = summarizeReturnType();
     Completion.Signature = summarizeSignature();
     Completion.SnippetSuffix = summarizeSnippet();
     Completion.BundleSize = Bundled.size();
+    Completion.IsOverride = summarizeOverride();
     return std::move(Completion);
   }
 
 private:
   struct BundledEntry {
     std::string SnippetSuffix;
     std::string Signature;
     std::string ReturnType;
+    std::string OverrideSuffix;
   };
 
   // If all BundledEntrys have the same value for a property, return it.
   template <std::string BundledEntry::*Member>
   const std::string *onlyValue() const {
     auto B = Bundled.begin(), E = Bundled.end();
     for (auto I = B + 1; I != E; ++I)
       if (I->*Member != B->*Member)
private:
 
   std::string summarizeSignature() const {
     if (auto *Signature = onlyValue<&BundledEntry::Signature>())
       return *Signature;
     // All bundles are function calls.
     return "(…)";
   }
 
+  bool summarizeOverride() const {
+    if (auto *OverrideSuffix = onlyValue<&BundledEntry::OverrideSuffix>())
+      return !OverrideSuffix->empty();
+    return false;
+  }
+
   ASTContext &ASTCtx;
   CodeCompletion Completion;
   SmallVector<BundledEntry, 1> Bundled;
   bool ExtractDocumentation;
 };
 
 // Determine the symbol ID for a Sema code completion result, if possible.
 llvm::Optional<SymbolID> getSymbolID(const CodeCompletionResult &R) {
QueryScopes = getQueryScopes(Recorder->CCContext,
                                  Recorder->CCSema->getSourceManager());
     // 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 = (Opts.Index && allowIndex(Recorder->CCContext))
                             ? queryIndex()
                             : SymbolSlab();
-    // Merge Sema and Index results, score them, and pick the winners.
-    auto Top = mergeResults(Recorder->Results, IndexResults);
-    // Convert the results to final form, assembling the expensive strings.
+    // Merge Sema, Index and Override results, score them, and pick the
+    // winners.
+    const auto Overrides = getNonOverridenMethodCompletionResults(
+        Recorder->CCSema->CurContext, Recorder->CCSema);
+    auto Top = mergeResults(Recorder->Results, IndexResults, Overrides);
     CodeCompleteResult Output;
+
+    // Convert the results to final form, assembling the expensive strings.
     for (auto &C : Top) {
       Output.Completions.push_back(toCodeCompletion(C.first));
       Output.Completions.back().Score = C.second;
       Output.Completions.back().CompletionTokenRange = TextEditRange;
     }
     Output.HasMore = Incomplete;
     Output.Context = Recorder->CCContext.getKind();
+
     return Output;
   }
 
   SymbolSlab queryIndex() {
     trace::Span Tracer("Query index");
     SPAN_ATTACH(Tracer, "limit", int64_t(Opts.Limit));
 
     SymbolSlab::Builder ResultsBuilder;
vlog("Code complete: fuzzyFind(\"{0}\", scopes=[{1}])", Req.Query,
          llvm::join(Req.Scopes.begin(), Req.Scopes.end(), ","));
     // Run the query against the index.
     if (Opts.Index->fuzzyFind(
             Req, [&](const Symbol &Sym) { ResultsBuilder.insert(Sym); }))
       Incomplete = true;
     return std::move(ResultsBuilder).build();
   }
 
-  // Merges Sema and Index results where possible, to form CompletionCandidates.
-  // Groups overloads if desired, to form CompletionCandidate::Bundles.
-  // The bundles are scored and top results are returned, best to worst.
+  // Merges Sema, Index and Override results where possible, to form
+  // CompletionCandidates. Groups overloads if desired, to form
+  // CompletionCandidate::Bundles. The bundles are scored and top results are
+  // returned, best to worst.
   std::vector<ScoredBundle>
-      mergeResults(const std::vector<CodeCompletionResult> &SemaResults,
-                   const SymbolSlab &IndexResults) {
+               const SymbolSlab &IndexResults,
+               const std::vector<CodeCompletionResult> &OverrideResults) {
     trace::Span Tracer("Merge and score results");
     std::vector<CompletionCandidate::Bundle> Bundles;
     llvm::DenseMap<size_t, size_t> BundleLookup;
     auto AddToBundles = [&](const CodeCompletionResult *SemaResult,
-                            const Symbol *IndexResult) {
+                            const Symbol *IndexResult,
+                            bool IsOverride = false) {
       CompletionCandidate C;
       C.SemaResult = SemaResult;
       C.IndexResult = IndexResult;
+      C.IsOverride = IsOverride;
       C.Name = IndexResult ? IndexResult->Name : Recorder->getName(*SemaResult);
       if (auto OverloadSet = Opts.BundleOverloads ? C.overloadSet() : 0) {
         auto Ret = BundleLookup.try_emplace(OverloadSet, Bundles.size());
         if (Ret.second)
           Bundles.emplace_back();
         Bundles[Ret.first->second].push_back(std::move(C));
       } else {
         Bundles.emplace_back();
auto CorrespondingIndexResult =
           return &*I;
         }
       }
       return nullptr;
     };
     // Emit all Sema results, merging them with Index results if possible.
     for (auto &SemaResult : Recorder->Results)
       AddToBundles(&SemaResult, CorrespondingIndexResult(SemaResult));
+    // Handle OverrideResults the same way we deal with SemaResults. Since these
+    // results use the same structs as a SemaResult it is safe to do that, but
+    // we need to make sure we dont' duplicate things in future if Sema starts
+    // to provide them as well.
+    for (auto &OverrideResult : OverrideResults)
+      AddToBundles(&OverrideResult, CorrespondingIndexResult(OverrideResult),
+                   true);
     // Now emit any Index-only results.
     for (const auto &IndexResult : IndexResults) {
       if (UsedIndexResults.count(&IndexResult))
         continue;
       AddToBundles(/*SemaResult=*/nullptr, &IndexResult);
     }
     // We only keep the best N results at any time, in "native" format.
     TopN<ScoredBundle, ScoredBundleGreater> Top(
return !match(decl(anyOf(InTopLevelScope,
               .empty();
 }
 
 CompletionItem CodeCompletion::render(const CodeCompleteOptions &Opts) const {
   CompletionItem LSP;
   LSP.label = (HeaderInsertion ? Opts.IncludeIndicator.Insert
                                : Opts.IncludeIndicator.NoInsert) +
               (Opts.ShowOrigins ? "[" + llvm::to_string(Origin) + "]" : "") +
-              RequiredQualifier + Name + Signature;
+              (IsOverride ? ReturnType + " " : "") + RequiredQualifier + Name +
+              Signature + (IsOverride ? " override" : "");
 
   LSP.kind = Kind;
   LSP.detail = BundleSize > 1 ? llvm::formatv("[{0} overloads]", BundleSize)
                               : ReturnType;
   if (!Header.empty())
     LSP.detail += "\n" + Header;
   LSP.documentation = Documentation;
   LSP.sortText = sortText(Score.Total, Name);
   LSP.filterText = Name;
-  LSP.textEdit = {CompletionTokenRange, RequiredQualifier + Name};
+  LSP.textEdit = {CompletionTokenRange,
+                  IsOverride ? llvm::formatv("{0} {1}{2} override", ReturnType,
+                                             Name, Signature)
+                             : RequiredQualifier + Name};
   // Merge continious additionalTextEdits into main edit. The main motivation
   // behind this is to help LSP clients, it seems most of them are confused when
   // they are provided with additionalTextEdits that are consecutive to main
   // edit.
   // Note that we store additional text edits from back to front in a line. That
   // is mainly to help LSP clients again, so that changes do not effect each
   // other.
   for (const auto &FixIt : FixIts) {

unittests/clangd/CodeCompleteTests.cpp

 MATCHER_P(Doc, D, "") { return arg.Documentation == D; }
 MATCHER_P(ReturnType, D, "") { return arg.ReturnType == D; }
 MATCHER_P(InsertInclude, IncludeHeader, "") {
   return arg.Header == IncludeHeader && bool(arg.HeaderInsertion);
 }
 MATCHER(InsertInclude, "") { return bool(arg.HeaderInsertion); }
 MATCHER_P(SnippetSuffix, Text, "") { return arg.SnippetSuffix == Text; }
 MATCHER_P(Origin, OriginSet, "") { return arg.Origin == OriginSet; }
+MATCHER(IsOverride, "") { return bool(arg.IsOverride); }
 
 // Shorthand for Contains(Named(Name)).
 Matcher<const std::vector<CodeCompletion> &> Has(std::string Name) {
   return Contains(Named(std::move(Name)));
 }
 Matcher<const std::vector<CodeCompletion> &> Has(std::string Name,
                                                  CompletionItemKind K) {
   return Contains(AllOf(Named(std::move(Name)), Kind(K)));
Opts.EnableFunctionArgSnippets = false;
     C.Kind = CompletionItemKind::Function;
 
     auto R = C.render(Opts);
     EXPECT_EQ(R.textEdit->newText, "Foo::x(${0})");
     EXPECT_EQ(R.insertTextFormat, InsertTextFormat::Snippet);
   }
 }
 
+TEST(CompletionTest, SuggestOverrides) {
+  constexpr const char *const Text(R"cpp(
+  class A {
+   public:
+    virtual void vfunc(bool param);
+    virtual void vfunc(bool param, int p);
+    void func(bool param);
+  };
+  class B : public A {
+  virtual void ttt(bool param);
+  void vfunc(bool param, int p) override;
+  };
+  class C : public B {
+   public:
+    void vfunc(bool param) override;
+    ^
+  };
+  )cpp");
+  const auto Results = completions(Text);
+  EXPECT_THAT(Results.Completions,
+              AllOf(Contains(AllOf(Named("vfunc"), IsOverride(),
+                                   Labeled("vfunc(bool param, int p)"))),
+                    Contains(AllOf(Named("ttt"), IsOverride(),
+                                   Labeled("ttt(bool param)"))),
+                    Not(Contains(AllOf(Named("vfunc"), IsOverride(),
+                                       Labeled("vfunc(bool param)"))))));
+}
+
+TEST(CompletionTest, RenderOverride) {
+  CodeCompletion C;
+  C.Name = "x";
+  C.Signature = "(bool) const";
+  C.SnippetSuffix = "(${0:bool})";
+  C.ReturnType = "int";
+  C.Documentation = "This is x().";
+  C.Kind = CompletionItemKind::Method;
+  C.Score.Total = 1.0;
+  C.Origin = SymbolOrigin::AST;
+  C.IsOverride = true;
+
+  CodeCompleteOptions Opts;
+  Opts.IncludeIndicator.NoInsert = "";
+  auto R = C.render(Opts);
+  EXPECT_EQ(R.label, "int x(bool) const override");
+  EXPECT_EQ(R.insertText, "int x(bool) const override");
+  EXPECT_EQ(R.insertTextFormat, InsertTextFormat::PlainText);
+  EXPECT_EQ(R.filterText, "x");
+  EXPECT_EQ(R.detail, "int");
+  EXPECT_EQ(R.documentation, "This is x().");
+  EXPECT_THAT(R.additionalTextEdits, IsEmpty());
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang