[clangd] Support renaming virtual methods

[tom-anders]

Summary

Fixes https://github.com/clangd/clangd/issues/706

[sammccall]

Sorry for the delay, this patch is really neat!

The only serious thing is it uncovers an existing bug which asserts. As a potential new crash I think we should fix that - LMK whether you feel comfortable adding that fix in here or you'd like me to do it as a separate review.

clang-tools-extra/clangd/refactor/Rename.cpp

245

Unfortunately we've uncovered a bug: this assertion fires (after this patch) on the following code:

template <typename> class Foo { virtual void m(); };
class Bar : Foo<int> { void ^m() override; };

canonicalRenameDecl is supposed to be idempotent. However:canonicalRenameDecl(Bar::m) is Foo<int>::m, but canonicalRenameDecl(Foo<int>::m) is Foo<T>::m.

I think this is because the getInstantiatedFromMemberFunction check comes before the overridden_methods check, so if the override points to a member of an instantiation then it's too late to map it back to the member of the template.

Probably the best fix is to change line 103 to a recursive return canonicalRenameDecl(...), as is done elsewhere in the function.

(Can you please add this case to the tests?)

547

we're already in an anon namespace here

548

The fact that we only need to walk down wasn't obvious to me at first, maybe add a comment on this function? e.g.

Walk down from a virtual method to overriding methods, we rename them as a group.
Note that canonicalRenameDecl() ensures we're starting from the base method.

[ilya-biryukov]

Thanks for the patch! A drive-by comment from me, hopefully useful.

clang-tools-extra/clangd/refactor/Rename.cpp

554

Should we put a limit on the number of requests we send during recursion here?

I see a few obvious failure modes:

• infinite recursion in the relations due to parts of index being stale, corrupted input data or other reasons,
• exponential blow up in hierarchies with multiple inheritance,
• sending a lot of network requests in case of deep inheritance hierarchies for remote index implementations. Since all requests are sequential, the network latency might add up to substantial numbers.

We could address these in some other manner, this just seems to be the simplest option to protect against catastrophic outcomes (running the request indefinitely, crashing due to infinite recursion, etc).

[sammccall]

clang-tools-extra/clangd/refactor/Rename.cpp

548

nit: can pass SymbolID by value, it's 8 bytes

554

exponential blow up in hierarchies with multiple inheritance,

It seems with little loss of readability we could provide some useful bounds:

DenseSet<SymbolID> Pending = {Base};
while (!Pending.empty()) {
  Req = {.Subjects = Pending};
  Pending.clear();
  Index.relations(Req, { IDs.insert(ID); Pending.insert(ID) });
}

in this case the #requests is clearly bounded by the length of the shortest chain to the most distant SymbolID, and is IMO safe with no numeric cap.

whereas the current version could potentially get the same ID in multiple branches and so the bound on #requests is harder to determine.

[ilya-biryukov]

clang-tools-extra/clangd/refactor/Rename.cpp

554

This looks good! Also avoids infinite recursion.
Having a potentially large number of sequential network requests still looks unfortunate, but I doubt this will bite us in practice (at least not for remote indicies for LLVM and Chrome).

To solve it, we could allow recursive requests and implement the recursion inside the index, but this could be done with a follow-up when we actually hit this issue.

[tom-anders]

Add test case that triggers assertion, limit recursion

[tom-anders]

clang-tools-extra/clangd/refactor/Rename.cpp

245

I added the test case for this. However, your suggested fix doesn't seem to stop the assertion from being triggered. I'd be grateful if you can take a closer look at this in a separate review - Should I leave the test case in anyway? Is it okay if the test fails for a while until you found the fix?

554

Done, hope I interpreted your sketch correctly

[tom-anders]

Fix recursivelyInsertRenames()

[tom-anders]

clang-tools-extra/clangd/refactor/Rename.cpp

554

Nope, I totally misunderstood, should be better now

[ilya-biryukov]

A few more NITs from me, but please wait for @sammccall for another round of reviews.

clang-tools-extra/clangd/refactor/Rename.cpp

550

NIT: maybe rename to insertTransitiveOverrides?
This function is not recursive anymore and "transitive" seems to be a more precise term for describing the results of running this function.

561–562

This should protect against infinite loop in case of broken/stale index.

[sammccall]

LG

IIRC Tom doesn't have commit access, so I'll apply the last trivial changes and commit to avoid another round trip.
(Please LMK if i'm wrong about this!)

clang-tools-extra/clangd/refactor/Rename.cpp

245

Thanks for adding the test, and sorry about the bad guess at a fix. We can't turn the buildbots red, so I'll comment out the test and fix+enable it separately.

561–562

Good catch!

[tom-anders]

In D132797#3774138, @sammccall wrote:

LG

IIRC Tom doesn't have commit access, so I'll apply the last trivial changes and commit to avoid another round trip.
(Please LMK if i'm wrong about this!)

I actually have commit access now, but thanks :) looking forward to your follow-up

clang-tools-extra/clangd/refactor/Rename.cpp

llvm::Optional<ReasonToReject> renameable(const NamedDecl &RenameDecl,
   else if (!DeclaredInMainFile)
     IsMainFileOnly = false;
   // If the symbol is not indexable, we disallow rename.
   if (!SymbolCollector::shouldCollectSymbol(
           RenameDecl, RenameDecl.getASTContext(), SymbolCollector::Options(),
           IsMainFileOnly))
     return ReasonToReject::NonIndexable;
 
-
-  // FIXME: Renaming virtual methods requires to rename all overridens in
-  // subclasses, our index doesn't have this information.
-  if (const auto *S = llvm::dyn_cast<CXXMethodDecl>(&RenameDecl)) {
-    if (S->isVirtual())
-      return ReasonToReject::UnsupportedSymbol;
-  }
   return None;
 }
 
 llvm::Error makeError(ReasonToReject Reason) {
   auto Message = [](ReasonToReject Reason) {
     switch (Reason) {
     case ReasonToReject::NoSymbolFound:
       return "there is no symbol at the given location";
llvm::Error makeError(ReasonToReject Reason) {
   };
   return error("Cannot rename symbol: {0}", Message(Reason));
 }
 
 // Return all rename occurrences in the main file.
 std::vector<SourceLocation> findOccurrencesWithinFile(ParsedAST &AST,
                                                       const NamedDecl &ND) {
   trace::Span Tracer("FindOccurrencesWithinFile");
   assert(canonicalRenameDecl(&ND) == &ND &&
          "ND should be already canonicalized.");
 
   std::vector<SourceLocation> Results;
   for (Decl *TopLevelDecl : AST.getLocalTopLevelDecls()) {
     findExplicitReferences(
         TopLevelDecl,
         [&](ReferenceLoc Ref) {
           if (Ref.Targets.empty())
Range toRange(const SymbolLocation &L) {
   Range R;
   R.start.line = L.Start.line();
   R.start.character = L.Start.column();
   R.end.line = L.End.line();
   R.end.character = L.End.column();
   return R;
 }
 
+// Walk down from a virtual method to overriding methods, we rename them as a
+// group. Note that canonicalRenameDecl() ensures we're starting from the base
+// method.
+void insertTransitiveOverrides(SymbolID Base, llvm::DenseSet<SymbolID> &IDs,
+                               const SymbolIndex &Index) {
+  RelationsRequest Req;
+  Req.Predicate = RelationKind::OverriddenBy;
+
+  llvm::DenseSet<SymbolID> Pending = {Base};
+  while (!Pending.empty()) {
+    Req.Subjects = std::move(Pending);
+    Pending.clear();
+
+    Index.relations(Req, [&](const SymbolID &, const Symbol &Override) {
+      if (IDs.insert(Override.ID).second)
+        Pending.insert(Override.ID);
+    });
+  }
+}
+
 // Return all rename occurrences (using the index) outside of the main file,
 // grouped by the absolute file path.
 llvm::Expected<llvm::StringMap<std::vector<Range>>>
 findOccurrencesOutsideFile(const NamedDecl &RenameDecl,
                            llvm::StringRef MainFile, const SymbolIndex &Index,
                            size_t MaxLimitFiles) {
   trace::Span Tracer("FindOccurrencesOutsideFile");
   RefsRequest RQuest;
   RQuest.IDs.insert(getSymbolID(&RenameDecl));
 
+  if (const auto *MethodDecl = llvm::dyn_cast<CXXMethodDecl>(&RenameDecl))
+    if (MethodDecl->isVirtual())
+      insertTransitiveOverrides(*RQuest.IDs.begin(), RQuest.IDs, Index);
+
   // Absolute file path => rename occurrences in that file.
   llvm::StringMap<std::vector<Range>> AffectedFiles;
   bool HasMore = Index.refs(RQuest, [&](const Ref &R) {
     if (AffectedFiles.size() >= MaxLimitFiles)
       return;
     if ((R.Kind & RefKind::Spelled) == RefKind::Unknown)
       return;
     if (auto RefFilePath = filePath(R.Location, /*HintFilePath=*/MainFile)) {

clang-tools-extra/clangd/unittests/RenameTests.cpp

Case Cases[] = {
           "no symbol", HeaderFile},
 
       {R"cpp(// disallow rename on non-normal identifiers.
          @interface Foo {}
          -(int) fo^o:(int)x; // Token is an identifier, but declaration name isn't a simple identifier.
          @end
        )cpp",
        "not a supported kind", HeaderFile},
-      {R"cpp(// FIXME: rename virtual/override methods is not supported yet.
-         struct A {
-          virtual void f^oo() {}
-         };
-      )cpp",
-       "not a supported kind", !HeaderFile},
       {R"cpp(
          void foo(int);
          void foo(char);
          template <typename T> void f(T t) {
            fo^o(t);
          })cpp",
        "multiple symbols", !HeaderFile},
 
llvm::StringRef FooCC;
         void Foo::[[foo]]() {}
 
         void func(Foo* p) {
           p->[[foo]]();
         }
       )cpp",
       },
       {
+          // virtual methods.
+          R"cpp(
+        class Base {
+          virtual void [[foo]]();
+        };
+        class Derived1 : public Base {
+          void [[f^oo]]() override;
+        };
+        class NotDerived {
+          void foo() {};
+        }
+      )cpp",
+          R"cpp(
+        #include "foo.h"
+        void Base::[[foo]]() {}
+        void Derived1::[[foo]]() {}
+
+        class Derived2 : public Derived1 {
+          void [[foo]]() override {};
+        };
+
+        void func(Base* b, Derived1* d1, 
+                  Derived2* d2, NotDerived* nd) {
+          b->[[foo]]();
+          d1->[[foo]]();
+          d2->[[foo]]();
+          nd->foo();
+        }
+      )cpp",
+      },
+      // FIXME: triggers an assertion failure due to a bug in canonicalization.
+      // See https://reviews.llvm.org/D132797
+#if 0
+      {
+          // virtual templated method
+          R"cpp(
+        template <typename> class Foo { virtual void [[m]](); };
+        class Bar : Foo<int> { void [[^m]]() override; };
+      )cpp", ""
+      },
+#endif
+      {
           // rename on constructor and destructor.
           R"cpp(
         class [[Foo]] {
           [[^Foo]]();
           ~[[Foo^]]();
         };
       )cpp",
           R"cpp(