[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

278–279

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

300

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.

332

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

348

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.

349

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 {
};

[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

289

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)

296

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.

305

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)?

311

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

598

getCanonicalDecl is not needed now.

[kbobyrev]

Resolve some comments, simplify the code.

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

289

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?

296

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

305

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

311

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

289

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?)

305

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

311

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.

324

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

598

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

297

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)) {.

307

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.

312

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.

315

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;
 }
 
+// Canonical declarations help simplify the process of renaming. Examples:
+// - Template's canonical decl is the templated declaration (i.e.
+//   ClassTemplateDecl is canonicalized to its child CXXRecordDecl,
+//   FunctionTemplateDecl - to child FunctionDecl)
+// - Given a constructor/destructor, canonical declaration is the parent
+//   CXXRecordDecl because we want to rename both type name and its ctor/dtor.
+// - All specializations are canonicalized to the primary template. For example:
+//
+//    template <typename T, int U>
+//    bool Foo = true; (1)
+//
+//    template <typename T>
+//    bool Foo<T, 0> = true; (2)
+//
+//    template <>
+//    bool Foo<int, 0> = true; (3)
+//
+// Here, both partial (2) and full (3) specializations are canonicalized to (1)
+// which ensures all three of them are renamed.
+const NamedDecl *canonicalRenameDecl(const NamedDecl *D) {
+  if (const auto *VarTemplate = dyn_cast<VarTemplateSpecializationDecl>(D))
+    return canonicalRenameDecl(
+        VarTemplate->getSpecializedTemplate()->getTemplatedDecl());
+  if (const auto *Template = dyn_cast<TemplateDecl>(D))
+    if (const NamedDecl *TemplatedDecl = Template->getTemplatedDecl())
+      return canonicalRenameDecl(TemplatedDecl);
+  if (const auto *ClassTemplateSpecialization =
+          dyn_cast<ClassTemplateSpecializationDecl>(D))
+    return canonicalRenameDecl(
+        ClassTemplateSpecialization->getSpecializedTemplate()
+            ->getTemplatedDecl());
+  if (const auto *Method = dyn_cast<CXXMethodDecl>(D)) {
+    if (Method->getDeclKind() == Decl::Kind::CXXConstructor ||
+        Method->getDeclKind() == Decl::Kind::CXXDestructor)
+      return canonicalRenameDecl(Method->getParent());
+    if (const FunctionDecl *InstantiatedMethod =
+            Method->getInstantiatedFromMemberFunction())
+      Method = cast<CXXMethodDecl>(InstantiatedMethod);
+    // FIXME(kirillbobyrev): For virtual methods with
+    // size_overridden_methods() > 1, this will not rename all functions it
+    // overrides, because this code assumes there is a single canonical
+    // declaration.
+    while (Method->isVirtual() && Method->size_overridden_methods())
+      Method = *Method->overridden_methods().begin();
+    return dyn_cast<NamedDecl>(Method->getCanonicalDecl());
+  }
+  if (const auto *Function = dyn_cast<FunctionDecl>(D))
+    if (const FunctionTemplateDecl *Template = Function->getPrimaryTemplate())
+      return canonicalRenameDecl(Template);
+  return dyn_cast<NamedDecl>(D->getCanonicalDecl());
+}
+
 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) {
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");
-  // 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));
+  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())
         return;
       for (const auto *Target : Ref.Targets) {
-        auto ID = getSymbolID(Target);
-        if (!ID || TargetIDs.find(ID) == TargetIDs.end())
+        if (canonicalRenameDecl(Target) == &ND) {
+          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.
 const NamedDecl *lookupSiblingWithName(const ASTContext &Ctx,
                                        const NamedDecl &RenamedDecl,
                                        llvm::StringRef Name) {
   const auto &II = Ctx.Idents.get(Name);
   DeclarationName LookupName(&II);
   DeclContextLookupResult LookupResult;
   const auto *DC = RenamedDecl.getDeclContext();
   while (DC && DC->isTransparentContext())
     DC = DC->getParent();
   switch (DC->getDeclKind()) {
   // The enclosing DeclContext may not be the enclosing scope, it might have
   // false positives and negatives, so we only choose "confident" DeclContexts
   // that don't have any subscopes that are neither DeclContexts nor
   // transparent.
   //
   // Notably, FunctionDecl is excluded -- because local variables are not scoped
   // to the function, but rather to the CompoundStmt that is its body. Lookup
   // will not find function-local variables.
   case Decl::TranslationUnit:
   case Decl::Namespace:
   case Decl::Record:
   case Decl::Enum:
   case Decl::CXXRecord:
     LookupResult = DC->lookup(LookupName);
     break;
   default:
     break;
   }
   // Lookup may contain the RenameDecl itself, exclude it.
   for (const auto *D : LookupResult)
     if (D->getCanonicalDecl() != RenamedDecl.getCanonicalDecl())
       return D;
   return nullptr;
 }
 
 struct InvalidName {
   enum Kind {
     Keywords,
     Conflict,
   };
   Kind K;
   std::string Details;
 };
 
 llvm::Error makeError(InvalidName Reason) {
   auto Message = [](InvalidName Reason) {
     switch (Reason.K) {
     case InvalidName::Keywords:
       return llvm::formatv("the chosen name \"{0}\" is a keyword",
                            Reason.Details);
     case InvalidName::Conflict:
       return llvm::formatv("conflict with the symbol in {0}", Reason.Details);
     }
     llvm_unreachable("unhandled InvalidName kind");
   };
   return error("invalid name: {0}", Message(Reason));
 }
 
llvm::Expected<RenameResult> rename(const RenameInputs &RInputs) {
   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());
+  const auto &RenameDecl = **DeclsUnderCursor.begin();
   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);