[clangd] Implement Decl canonicalization rules for rename

[kbobyrev]

Summary

This patch introduces new canonicalization rules which are used for AST-based
rename in Clangd. By comparing two canonical declarations of inspected nodes,
Clangd determines whether both of them belong to the same entity user would
like to rename. Such functionality is relatively concise compared to the
Clang-Rename API that is used right now. It also helps to overcome the
limitations that Clang-Rename originally had and helps to eliminate several
classes of bugs.

Clangd AST-based rename currently relies on Clang-Rename which has design
limitations and also lacks some features. This patch breaks this dependency and
significantly reduces the amount of code to maintain (Clang-Rename is ~2000 LOC,
this patch is just <30 LOC of replacement code).

We eliminate technical debt by simultaneously

• Maintaining feature parity and ensuring no regressions
• Opening a straightforward path to improving existing rename bugs
• Making it possible to add more capabilities to rename feature which would not be possible with Clang-Rename

[kbobyrev]

This is a WIP draft. Few items to address before pushing for a review

• More tests: renaming is a complex feature and I want to make sure there are no regressions/corner-cases I did not handle. It might make sense to adopt a bunch of tests from Clang-Rename and also add a number of new tests.
• Detailed documentation: explanation of AST navigation used here, description of limitations (virtual functions "incorrect" handling, notes on performance, etc).
• Better naming

The logical change after this patch might be changing Clang-Rename to rely on this API and completely removing USR-based approach, because it is no longer maintained and is unlikely to evolve to match the expectations of existing users, but this might require some substantial infrastructure changes and I'm not planning to do that soon.

[merge_guards_bot]

Unit tests: pass. 61107 tests passed, 0 failed and 728 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[kbobyrev]

Continue implementation, integrate more tests from clang-rename.

[kbobyrev]

Store progress.

[kbobyrev]

Finish fields canonicalization.

[kbobyrev]

Still WIP, moving test changes to a separate chain of patches (starts with D91102) to make review easier and start the pipeline.

[kbobyrev]

Reset unittests to HEAD.

[kbobyrev]

Actually reset RenameTests.cpp

[kbobyrev]

Rebase on top of master.

[kbobyrev]

Still WIP.

[kbobyrev]

I think this is the first version that is ready for a review. Let me know if
you have any questions, @hokein!

[kbobyrev]

Use early return in FieldDecl canonicalization.

[hokein]

don't dig into details, first round of comments.

I think the scope is a bit ambiguous, my reading is that it 1) removes old clang-rename API usage *and* 2) fixes some existing bugs. I would suggest just scoping it on 1).

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

251

yeah, this is quite tricky. I'd suggest to defer it to a separate patch.

The behavior you described in https://github.com/clangd/clangd/issues/582 makes sense to me.

Another missing case is about static class members, they are VarDecl in the AST.

283

I'm not sure the motivation of the change, the same as line 244.

299

Looks like we're missing the VarDecl case (looks like a regression). I think we should probably add tests from https://github.com/llvm/llvm-project/commit/1e32df2f91f1aa1f8cd400ce50a621578fa0534e to clangd rename test.

300

we're comparing Decl pointers to check whether they point to the same symbol, I think we should use Candidate->getCanonicalDecl() here.

thinking of a case, in the AST, we have two Decl*s, one points to the forward decl, the other one points to the definition. but they points to the same symbol.

class Foo; // forward decl, this is the canonical decl.

class Foo {
};

307

since we call canonicalRenameDecl in locateDeclAt, I think ND is already canonical, right?

[kbobyrev]

• Handle VarDecl
• Handle FunctionTemplateDecl
• Remove FieldDecl handling (leave for the future patches)
• Simplify code
• Prevent regressions by adding more tests

[kbobyrev]

Add missing user-defined conversion test and a couple of missing cases with
ctor/dtor out-of-line implementation.

[kbobyrev]

Add a test with static class member.

[kbobyrev]

Remove (now) outdated comment.

[kbobyrev]

Completely remove new tests from this patch (to be provided in a different
one).

[kbobyrev]

Remove unused header (was added for llvm_unreachable).

[hokein]

didn't finish all parts (looked at the FunctionDecl and RecordDecl), I think we need more documentation/comments in the code to specify the canonical behavior (templates are tricky).

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

240

the auto + varies canonicalRenameDecl overrides make the code hard to follow.

since these functions are small, I think we can inline them into the main canonicalRenameDecl(const NamedDecl *D)

247

didn't quite follow the code here, the code looks like we get the FunctionTemplateDecl back via the code path (FunctionTemplateDecl -> FunctionDecl -> FunctionTemplateDecl), and it looks like we're not using the specialized declaration as the canonical decl.

256

want to confirm my understanding:

given the example below:

template<typename T>
class Foo {};

template<>
class Foo<int> {};

the AST is like:

ClassTemplateDecl
  |-CXXRecordDecl (Foo definition) -> (1)
  |-ClassTemplateSpecialization. 

ClassTemplateSpecializationDecl -> call canonicalRenameDecl on it.
  |-Template Argument int
  |-CXXRecordDecl -> (2)

if we pass ClassTemplateSpecializationDecl to this function, this function will return (2)?

262

I think the motivation is for merely renaming the explicit template specialization, but not the primary template?

627

getCanonicalDecl is not needed now.

[kbobyrev]

Resolve some comments, simplify the code.

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

240

I removed autos but I believe merging them into a single function would not be great for two reasons:

• Some classes are already handled by the same function outside of the main one: ctor/dtor's parent CXXRecordDecl, etc: in the main function we'd have to have a weird logic behind extracting those and this is likely to result in more code
• Some functions call other ones (e.g. here we have canonicalRenameDecl(Template) - sure, right now it's just D->getTemplatedDecl() but if we decide to change something and when we introduce more code it'd be easy to forget and code duplication is not really a good idea).

WDYT?

247

Uh, good catch, thanks. This one is simply not needed because we handle TemplateDecl which does the right thing for FunctionTemplateDecl.

256

No, this will return (1): getSpecializedTemplate() returns ClassTemplateDecl and then getTemplatedDecl() gets to CXXRecordDecl in it.

262

How come? The specialized template is the primary template, am I missing something?

[kbobyrev]

Remove leftover test.

[hokein]

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

240

this is more about encapsulation -- my understanding is that canonicalRenameDecl(const NamedDecl) should be the only main entry, others are just implementation details, so we expect client just calls the main function, but not other overrides. The current state leaks these implementation details outside of the world.

Some classes are already handled by the same function outside of the main one: ctor/dtor's parent CXXRecordDecl, etc: in the main function we'd have to have a weird logic behind extracting those and this is likely to result in more code

don't follow this, for ctor/dtor's parent CXXRecordDecl, I think just calling the main canonicalRenameDecl recursively on the parent should be enough?

Some functions call other ones (e.g. here we have canonicalRenameDecl(Template) - sure, right now it's just D->getTemplatedDecl() but if we decide to change something and when we introduce more code it'd be easy to forget and code duplication is not really a good idea).

I agree your points. Given the current code, I think inlining them seems quite straight-forward and clearer to me (the only case is FunctionDecl, which calls the canonicalRenameDecl(const TemplateDecl *D), but we can just call getTemplatedDecl as well).

Regarding your concerns, I think we can always find ways to extend the code when we need to enhance the TemplateDecl case (what kind of enhancement we'll do for templateDecl?)

256

I see. thanks for the explanation. I misunderstood the getSpecializedTemplate.

262

ah, you're right, sorry -- I was confused by the term "specialized template", I thought it is the specialization decl.

I'd suggest using "primary template", I think it is clearer than the specialized decl., and would be nice to have some concrete example in comments explaining these tricky cases.

275

I think we should call getCanonicalDecl before returning the final result (calling it at the beginning doesn't guarantee the final result is canonical).

627

nit: llvm::cast is not needed, just const NamedDecl &RenameDecl = *(*DeclsUnderCursor.begin());

[kbobyrev]

Need to address the comments.

[kbobyrev]

Resolve review comments.

[hokein]

Thanks, this looks nicer now.

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

248

ctor & dtor is one of the kinds of CXXMethodDecl, I think we can merge the ctor & dtor cases into the if (const auto *Method = dyn_cast<CXXMethodDecl>(D)) {.

258

using else if would be more clear -- as now we modify D is the preceding if, if the D is assigned to a CXXMethodDecl in the preceding if, then it may fall into this branch.

263

oh, it is a tricky case where a method overrides > 1 virtual methods. Looks like we will regress this case in this patch, e.g.

class Foo {
  virtual void foo();
};

class Bar {
  virtual void foo();
};

class C : public Foo, Bar {
  void foo() override; // -> rename foo => bar
};

prior to the patch, both Foo::foo and Bar::foo will be renamed, after this patch, only one of them will be renamed (with within-file rename)? I think it is ok, but probably need some comments here.

266

the same, else

IIUC, CXXMethodDecl must be processed before FunctionDecl, I think we can add an assertion (the FunctionDecl must not be CXXMethodDecl).

[kbobyrev]

Resolve comments.

[kbobyrev]

Make use of TemplatedDecl.

[hokein]

Thanks, this looks great now.

I think we can get rid of the clangToolingRefactoring dependence from clangd CMake files, clangd now should have no use of any functions there, could you take a look?

[hokein]

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

78

nit: maybe we can just move the function definition to here.

[kbobyrev]

Get rid of forward declaration.

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

 #include "Selection.h"
 #include "SourceCode.h"
 #include "index/SymbolCollector.h"
 #include "support/Logger.h"
 #include "support/Trace.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/Basic/SourceLocation.h"
-#include "clang/Tooling/Refactoring/Rename/USRFindingAction.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FormatVariadic.h"
 #include <algorithm>
 
Index.refs(Req, [&](const Ref &R) {
     if (auto RefFilePath = filePath(R.Location, /*HintFilePath=*/MainFile)) {
       if (*RefFilePath != MainFile)
         OtherFile = *RefFilePath;
     }
   });
   return OtherFile;
 }
 
+const NamedDecl *canonicalRenameDecl(const NamedDecl *D);
+
 llvm::DenseSet<const NamedDecl *> locateDeclAt(ParsedAST &AST,
                                                SourceLocation TokenStartLoc) {
   unsigned Offset =
       AST.getSourceManager().getDecomposedSpellingLoc(TokenStartLoc).second;
 
   SelectionTree Selection = SelectionTree::createRight(
       AST.getASTContext(), AST.getTokens(), Offset, Offset);
   const SelectionTree::Node *SelectedNode = Selection.commonAncestor();
   if (!SelectedNode)
     return {};
 
   llvm::DenseSet<const NamedDecl *> Result;
   for (const NamedDecl *D :
        targetDecl(SelectedNode->ASTNode,
                   DeclRelation::Alias | DeclRelation::TemplatePattern)) {
     // Get to CXXRecordDecl from constructor or destructor.
-    D = tooling::getCanonicalSymbolDeclaration(D);
-    Result.insert(D);
+    Result.insert(canonicalRenameDecl(D));
   }
   return Result;
 }
 
 // By default, we exclude C++ standard symbols and protobuf symbols as rename
 // these symbols would change system/generated files which are unlikely to be
 // modified.
 bool isExcluded(const NamedDecl &RenameDecl) {
auto Message = [](ReasonToReject Reason) {
     case ReasonToReject::SameName:
       return "new name is the same as the old name";
     }
     llvm_unreachable("unhandled reason kind");
   };
   return error("Cannot rename symbol: {0}", Message(Reason));
 }
 
+const NamedDecl *canonicalRenameDecl(const ClassTemplateSpecializationDecl *D) {
+  return D->getSpecializedTemplate()->getTemplatedDecl();
+}
+
+const NamedDecl *canonicalRenameDecl(const TemplateDecl *D) {
+  return D->getTemplatedDecl();
+}
+
+const NamedDecl *canonicalRenameDecl(const CXXMethodDecl *D) {
+  const auto *Result = D;
+  if (const auto *InstantiatedMethod = D->getInstantiatedFromMemberFunction())
+    Result = cast<CXXMethodDecl>(InstantiatedMethod);
+  while (Result->isVirtual() && Result->size_overridden_methods())
+    Result = *Result->overridden_methods().begin();
+  return Result;
+}
+
+const NamedDecl *canonicalRenameDecl(const FunctionDecl *D) {
+  const auto *Definition = D->getDefinition();
+  const auto *Candidate = Definition ? Definition : D->getMostRecentDecl();
+  return Candidate->isTemplateInstantiation()
+             ? Candidate->getPrimaryTemplate()->getTemplatedDecl()
+             : Candidate;
+}
+
+const NamedDecl *canonicalRenameDecl(const FieldDecl *D) {
+  // This is a hacky way to do something like
+  // CXXMethodDecl::getINstantiatedFromMemberFunction for the field because
+  // Clang AST does not store relevant information about the field that is
+  // instantiated.
+  const auto *TemplateSpec =
+      dyn_cast<ClassTemplateSpecializationDecl>(D->getParent());
+  if (!TemplateSpec)
+    return D;
+  const auto *FieldParent = TemplateSpec->getTemplateInstantiationPattern();
+  if (!FieldParent)
+    return D;
+  for (const auto *Field : FieldParent->fields()) {
+    if (Field->getFieldIndex() == D->getFieldIndex()) {
+      assert(Field->getLocation() == D->getLocation() &&
+             "D should be generated from Field so it has the same location.");
+      return Field;
+    }
+  }
+  return D;
+}
+
+// Canonical declarations help simplify the process of renaming. Examples:
+// - Given a constructor/destructor, canonical declaration is the parent
+//   CXXRecordDecl
+// - Specializations should point to the specialized declaration.
+// - Instantiations should point to instantiated declaration.
+// Some cases require recursive canonicalization: e.g. constructor -> parent
+// class instantiation -> instantiated class.
+const NamedDecl *canonicalRenameDecl(const NamedDecl *D) {
+  const auto *Candidate = D;
+  if (const auto *RD = dyn_cast<RecordDecl>(Candidate)) {
+    const auto *Definition = RD->getDefinition();
+    Candidate = Definition ? Definition : RD->getMostRecentDecl();
+  }
+  if (const auto *Constructor = dyn_cast<CXXConstructorDecl>(Candidate))
+    return canonicalRenameDecl(Constructor->getParent());
+  if (const auto *Destructor = dyn_cast<CXXDestructorDecl>(Candidate))
+    return canonicalRenameDecl(Destructor->getParent());
+  if (const auto *Template = dyn_cast<TemplateDecl>(Candidate))
+    return canonicalRenameDecl(Template);
+  if (const auto *ClassTemplateSpecialization =
+          dyn_cast<ClassTemplateSpecializationDecl>(Candidate))
+    return canonicalRenameDecl(ClassTemplateSpecialization);
+  if (const auto *Method = dyn_cast<CXXMethodDecl>(Candidate))
+    return canonicalRenameDecl(Method);
+  if (const auto *Function = dyn_cast<FunctionDecl>(Candidate))
+    return canonicalRenameDecl(Function);
+  if (const auto *Field = dyn_cast<FieldDecl>(Candidate))
+    return canonicalRenameDecl(Field);
+  return Candidate;
+}
+
 // Return all rename occurrences in the main file.
 std::vector<SourceLocation> findOccurrencesWithinFile(ParsedAST &AST,
                                                       const NamedDecl &ND) {
   trace::Span Tracer("FindOccurrencesWithinFile");
-  // If the cursor is at the underlying CXXRecordDecl of the
-  // ClassTemplateDecl, ND will be the CXXRecordDecl. In this case, we need to
-  // get the primary template manually.
-  // getUSRsForDeclaration will find other related symbols, e.g. virtual and its
-  // overriddens, primary template and all explicit specializations.
-  // FIXME: Get rid of the remaining tooling APIs.
-  const auto *RenameDecl =
-      ND.getDescribedTemplate() ? ND.getDescribedTemplate() : &ND;
-  std::vector<std::string> RenameUSRs =
-      tooling::getUSRsForDeclaration(RenameDecl, AST.getASTContext());
-  llvm::DenseSet<SymbolID> TargetIDs;
-  for (auto &USR : RenameUSRs)
-    TargetIDs.insert(SymbolID(USR));
+  const auto *RenameDecl = canonicalRenameDecl(&ND);
 
   std::vector<SourceLocation> Results;
   for (Decl *TopLevelDecl : AST.getLocalTopLevelDecls()) {
     findExplicitReferences(TopLevelDecl, [&](ReferenceLoc Ref) {
       if (Ref.Targets.empty())
         return;
       for (const auto *Target : Ref.Targets) {
-        auto ID = getSymbolID(Target);
-        if (!ID || TargetIDs.find(ID) == TargetIDs.end())
+        if (canonicalRenameDecl(Target) == RenameDecl) {
+          Results.push_back(Ref.NameLoc);
           return;
         }
-      Results.push_back(Ref.NameLoc);
+      }
     });
   }
 
   return Results;
 }
 
 // Lookup the declarations (if any) with the given Name in the context of
 // RenameDecl.
if (locateMacroAt(*IdentifierToken, AST.getPreprocessor()))
     return makeError(ReasonToReject::UnsupportedSymbol);
 
   auto DeclsUnderCursor = locateDeclAt(AST, IdentifierToken->location());
   if (DeclsUnderCursor.empty())
     return makeError(ReasonToReject::NoSymbolFound);
   if (DeclsUnderCursor.size() > 1)
     return makeError(ReasonToReject::AmbiguousSymbol);
   const auto &RenameDecl =
       llvm::cast<NamedDecl>(*(*DeclsUnderCursor.begin())->getCanonicalDecl());
   if (RenameDecl.getName() == RInputs.NewName)
     return makeError(ReasonToReject::SameName);
   auto Invalid = checkName(RenameDecl, RInputs.NewName);
   if (Invalid)
     return makeError(*Invalid);
 
   auto Reject = renameable(RenameDecl, RInputs.MainFilePath, RInputs.Index,
                            Opts.AllowCrossFile);

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

llvm::StringRef Tests[] = {
 
         [[Old^Alias]] old_alias;
         }
 
         void bar() {
           ns::[[Old^Alias]] Bar;
         }
       )cpp",
+
+      // Templated method instantiation.
+      R"cpp(
+        template<typename T>
+        class Foo {
+        public:
+          static T [[f^oo]]() {}
+        };
+
+        void bar() {
+          Foo<int>::[[f^oo]]();
+        }
+      )cpp",
+      R"cpp(
+        template<typename T>
+        class Foo {
+        public:
+          T [[f^oo]]() {}
+        };
+
+        void bar() {
+          Foo<int>().[[f^oo]]();
+        }
+      )cpp",
+
+      // Templated class specialization.
+      R"cpp(
+        template<typename T, typename U=bool>
+        class [[Foo^]];
+
+        template<typename T, typename U>
+        class [[Foo^]] {};
+
+        template<typename T=int, typename U>
+        class [[Foo^]];
+      )cpp",
+      R"cpp(
+        template<typename T=float, typename U=int>
+        class [[Foo^]];
+
+        template<typename T, typename U>
+        class [[Foo^]] {};
+      )cpp",
+
+      // Function template specialization.
+      R"cpp(
+        template<typename T=int, typename U=bool>
+        U [[foo^]]();
+
+        template<typename T, typename U>
+        U [[foo^]]() {};
+      )cpp",
+      R"cpp(
+        template<typename T, typename U>
+        U [[foo^]]() {};
+
+        template<typename T=int, typename U=bool>
+        U [[foo^]]();
+      )cpp",
+      R"cpp(
+        template<typename T=int, typename U=bool>
+        U [[foo^]]();
+
+        template<typename T, typename U>
+        U [[foo^]]();
+      )cpp",
+
+      // Fields in classes & partial and full specialiations.
+      R"cpp(
+        class Foo {
+        public:
+          Foo(int Variable) : [[Variabl^e]](Variable) {}
+
+          int [[Va^riable]] = 42;
+
+        private:
+          void foo() { ++[[Vari^able]]; }
+        };
+
+        void bar() {
+          Foo f(9000);
+          f.[[Variable^]] = -1;
+        }
+      )cpp",
+      R"cpp(
+        template<typename T>
+        struct Foo {
+          T [[Vari^able]] = 42;
+        };
+
+        void foo() {
+          Foo<int> f;
+          f.[[Varia^ble]] = 9000;
+        }
+      )cpp",
+      R"cpp(
+        template<typename T, typename U>
+        struct Foo {
+          T Variable[42];
+          U Another;
+
+          void bar() {}
+        };
+
+        template<typename T>
+        struct Foo<T, bool> {
+          T [[Var^iable]];
+          void bar() { ++[[Var^iable]]; }
+        };
+
+        void foo() {
+          Foo<unsigned, bool> f;
+          f.[[Var^iable]] = 9000;
+        }
+      )cpp",
+      R"cpp(
+        template<typename T, typename U>
+        struct Foo {
+          T Variable[42];
+          U Another;
+
+          void bar() {}
+        };
+
+        template<typename T>
+        struct Foo<T, bool> {
+          T Variable;
+          void bar() { ++Variable; }
+        };
+
+        template<>
+        struct Foo<unsigned, bool> {
+          unsigned [[Var^iable]];
+          void bar() { ++[[Var^iable]]; }
+        };
+
+        void foo() {
+          Foo<unsigned, bool> f;
+          f.[[Var^iable]] = 9000;
+        }
+      )cpp",
   };
   llvm::StringRef NewName = "NewName";
   for (llvm::StringRef T : Tests) {
     SCOPED_TRACE(T);
     Annotations Code(T);
     auto TU = TestTU::withCode(Code.code());
     TU.ExtraArgs.push_back("-fno-delayed-template-parsing");
     auto AST = TU.build();