clang-tools-extra/clangd/refactor/tweaks/DefineInline.cpp

   1 //===--- DefineInline.cpp ----------------------------------------*- C++-*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "AST.h"
  10 #include "FindTarget.h"
  11 #include "Selection.h"
  12 #include "SourceCode.h"
  13 #include "XRefs.h"
  14 #include "refactor/Tweak.h"
  15 #include "support/Logger.h"
  16 #include "clang/AST/ASTContext.h"
  17 #include "clang/AST/ASTTypeTraits.h"
  18 #include "clang/AST/Decl.h"
  19 #include "clang/AST/DeclBase.h"
  20 #include "clang/AST/DeclCXX.h"
  21 #include "clang/AST/DeclTemplate.h"
  22 #include "clang/AST/NestedNameSpecifier.h"
  23 #include "clang/AST/Stmt.h"
  24 #include "clang/Basic/LangOptions.h"
  25 #include "clang/Basic/SourceLocation.h"
  26 #include "clang/Basic/SourceManager.h"
  27 #include "clang/Basic/TokenKinds.h"
  28 #include "clang/Lex/Lexer.h"
  29 #include "clang/Lex/Token.h"
  30 #include "clang/Sema/Lookup.h"
  31 #include "clang/Sema/Sema.h"
  32 #include "clang/Tooling/Core/Replacement.h"
  33 #include "llvm/ADT/DenseMap.h"
  34 #include "llvm/ADT/DenseSet.h"
  35 #include "llvm/ADT/SmallVector.h"
  36 #include "llvm/ADT/StringRef.h"
  37 #include "llvm/Support/Casting.h"
  38 #include "llvm/Support/Error.h"
  39 #include "llvm/Support/raw_ostream.h"
  40 #include <cstddef>
  41 #include <optional>
  42 #include <set>
  43 #include <string>
  44 #include <unordered_map>
  45 #include <utility>
  46 #include <vector>
  47
  48 namespace clang {
  49 namespace clangd {
  50 namespace {
  51
  52 // Returns semicolon location for the given FD. Since AST doesn't contain that
  53 // information, searches for a semicolon by lexing from end of function decl
  54 // while skipping comments.
  55 std::optional<SourceLocation> getSemicolonForDecl(const FunctionDecl *FD) {
  56   const SourceManager &SM = FD->getASTContext().getSourceManager();
  57   const LangOptions &LangOpts = FD->getASTContext().getLangOpts();
  58
  59   SourceLocation CurLoc = FD->getEndLoc();
  60   auto NextTok = Lexer::findNextToken(CurLoc, SM, LangOpts);
  61   if (!NextTok || !NextTok->is(tok::semi))
  62     return std::nullopt;
  63   return NextTok->getLocation();
  64 }
  65
  66 // Deduces the FunctionDecl from a selection. Requires either the function body
  67 // or the function decl to be selected. Returns null if none of the above
  68 // criteria is met.
  69 const FunctionDecl *getSelectedFunction(const SelectionTree::Node *SelNode) {
  70   const DynTypedNode &AstNode = SelNode->ASTNode;
  71   if (const FunctionDecl *FD = AstNode.get<FunctionDecl>())
  72     return FD;
  73   if (AstNode.get<CompoundStmt>() &&
  74       SelNode->Selected == SelectionTree::Complete) {
  75     if (const SelectionTree::Node *P = SelNode->Parent)
  76       return P->ASTNode.get<FunctionDecl>();
  77   }
  78   return nullptr;
  79 }
  80
  81 // Checks the decls mentioned in Source are visible in the context of Target.
  82 // Achieves that by checking declarations occur before target location in
  83 // translation unit or declared in the same class.
  84 bool checkDeclsAreVisible(const llvm::DenseSet<const Decl *> &DeclRefs,
  85                           const FunctionDecl *Target, const SourceManager &SM) {
  86   SourceLocation TargetLoc = Target->getLocation();
  87   // To be used in visibility check below, decls in a class are visible
  88   // independent of order.
  89   const RecordDecl *Class = nullptr;
  90   if (const auto *MD = llvm::dyn_cast<CXXMethodDecl>(Target))
  91     Class = MD->getParent();
  92
  93   for (const auto *DR : DeclRefs) {
  94     // Use canonical decl, since having one decl before target is enough.
  95     const Decl *D = DR->getCanonicalDecl();
  96     if (D == Target)
  97       continue;
  98     SourceLocation DeclLoc = D->getLocation();
  99
 100     // FIXME: Allow declarations from different files with include insertion.
 101     if (!SM.isWrittenInSameFile(DeclLoc, TargetLoc))
 102       return false;
 103
 104     // If declaration is before target, then it is visible.
 105     if (SM.isBeforeInTranslationUnit(DeclLoc, TargetLoc))
 106       continue;
 107
 108     // Otherwise they need to be in same class
 109     if (!Class)
 110       return false;
 111     const RecordDecl *Parent = nullptr;
 112     if (const auto *MD = llvm::dyn_cast<CXXMethodDecl>(D))
 113       Parent = MD->getParent();
 114     else if (const auto *FD = llvm::dyn_cast<FieldDecl>(D))
 115       Parent = FD->getParent();
 116     if (Parent != Class)
 117       return false;
 118   }
 119   return true;
 120 }
 121
 122 // Rewrites body of FD by re-spelling all of the names to make sure they are
 123 // still valid in context of Target.
 124 llvm::Expected<std::string> qualifyAllDecls(const FunctionDecl *FD,
 125                                             const FunctionDecl *Target,
 126                                             const HeuristicResolver *Resolver) {
 127   // There are three types of spellings that needs to be qualified in a function
 128   // body:
 129   // - Types:       Foo                 -> ns::Foo
 130   // - DeclRefExpr: ns2::foo()          -> ns1::ns2::foo();
 131   // - UsingDecls:
 132   //    using ns2::foo      -> using ns1::ns2::foo
 133   //    using namespace ns2 -> using namespace ns1::ns2
 134   //    using ns3 = ns2     -> using ns3 = ns1::ns2
 135   //
 136   // Go over all references inside a function body to generate replacements that
 137   // will qualify those. So that body can be moved into an arbitrary file.
 138   // We perform the qualification by qualifying the first type/decl in a
 139   // (un)qualified name. e.g:
 140   //    namespace a { namespace b { class Bar{}; void foo(); } }
 141   //    b::Bar x; -> a::b::Bar x;
 142   //    foo(); -> a::b::foo();
 143
 144   auto *TargetContext = Target->getLexicalDeclContext();
 145   const SourceManager &SM = FD->getASTContext().getSourceManager();
 146
 147   tooling::Replacements Replacements;
 148   bool HadErrors = false;
 149   findExplicitReferences(
 150       FD->getBody(),
 151       [&](ReferenceLoc Ref) {
 152         // Since we want to qualify only the first qualifier, skip names with a
 153         // qualifier.
 154         if (Ref.Qualifier)
 155           return;
 156         // There might be no decl in dependent contexts, there's nothing much we
 157         // can do in such cases.
 158         if (Ref.Targets.empty())
 159           return;
 160         // Do not qualify names introduced by macro expansions.
 161         if (Ref.NameLoc.isMacroID())
 162           return;
 163
 164         for (const NamedDecl *ND : Ref.Targets) {
 165           if (ND->getDeclContext() != Ref.Targets.front()->getDeclContext()) {
 166             elog("define inline: Targets from multiple contexts: {0}, {1}",
 167                  printQualifiedName(*Ref.Targets.front()),
 168                  printQualifiedName(*ND));
 169             HadErrors = true;
 170             return;
 171           }
 172         }
 173         // All Targets are in the same scope, so we can safely chose first one.
 174         const NamedDecl *ND = Ref.Targets.front();
 175         // Skip anything from a non-namespace scope, these can be:
 176         // - Function or Method scopes, which means decl is local and doesn't
 177         // need
 178         //   qualification.
 179         // - From Class/Struct/Union scope, which again doesn't need any
 180         // qualifiers,
 181         //   rather the left side of it requires qualification, like:
 182         //   namespace a { class Bar { public: static int x; } }
 183         //   void foo() { Bar::x; }
 184         //                ~~~~~ -> we need to qualify Bar not x.
 185         if (!ND->getDeclContext()->isNamespace())
 186           return;
 187
 188         const std::string Qualifier = getQualification(
 189             FD->getASTContext(), TargetContext, Target->getBeginLoc(), ND);
 190         if (auto Err = Replacements.add(
 191                 tooling::Replacement(SM, Ref.NameLoc, 0, Qualifier))) {
 192           HadErrors = true;
 193           elog("define inline: Failed to add quals: {0}", std::move(Err));
 194         }
 195       },
 196       Resolver);
 197
 198   if (HadErrors)
 199     return error(
 200         "define inline: Failed to compute qualifiers. See logs for details.");
 201
 202   // Get new begin and end positions for the qualified body.
 203   auto OrigBodyRange = toHalfOpenFileRange(
 204       SM, FD->getASTContext().getLangOpts(), FD->getBody()->getSourceRange());
 205   if (!OrigBodyRange)
 206     return error("Couldn't get range func body.");
 207
 208   unsigned BodyBegin = SM.getFileOffset(OrigBodyRange->getBegin());
 209   unsigned BodyEnd = Replacements.getShiftedCodePosition(
 210       SM.getFileOffset(OrigBodyRange->getEnd()));
 211
 212   // Trim the result to function body.
 213   auto QualifiedFunc = tooling::applyAllReplacements(
 214       SM.getBufferData(SM.getFileID(OrigBodyRange->getBegin())), Replacements);
 215   if (!QualifiedFunc)
 216     return QualifiedFunc.takeError();
 217   return QualifiedFunc->substr(BodyBegin, BodyEnd - BodyBegin + 1);
 218 }
 219
 220 /// Generates Replacements for changing template and function parameter names in
 221 /// \p Dest to be the same as in \p Source.
 222 llvm::Expected<tooling::Replacements>
 223 renameParameters(const FunctionDecl *Dest, const FunctionDecl *Source,
 224                  const HeuristicResolver *Resolver) {
 225   llvm::DenseMap<const Decl *, std::string> ParamToNewName;
 226   llvm::DenseMap<const NamedDecl *, std::vector<SourceLocation>> RefLocs;
 227   auto HandleParam = [&](const NamedDecl *DestParam,
 228                          const NamedDecl *SourceParam) {
 229     // No need to rename if parameters already have the same name.
 230     if (DestParam->getName() == SourceParam->getName())
 231       return;
 232     std::string NewName;
 233     // Unnamed parameters won't be visited in findExplicitReferences. So add
 234     // them here.
 235     if (DestParam->getName().empty()) {
 236       RefLocs[DestParam].push_back(DestParam->getLocation());
 237       // If decl is unnamed in destination we pad the new name to avoid gluing
 238       // with previous token, e.g. foo(int^) shouldn't turn into foo(intx).
 239       NewName = " ";
 240     }
 241     NewName.append(std::string(SourceParam->getName()));
 242     ParamToNewName[DestParam->getCanonicalDecl()] = std::move(NewName);
 243   };
 244
 245   // Populate mapping for template parameters.
 246   auto *DestTempl = Dest->getDescribedFunctionTemplate();
 247   auto *SourceTempl = Source->getDescribedFunctionTemplate();
 248   assert(bool(DestTempl) == bool(SourceTempl));
 249   if (DestTempl) {
 250     const auto *DestTPL = DestTempl->getTemplateParameters();
 251     const auto *SourceTPL = SourceTempl->getTemplateParameters();
 252     assert(DestTPL->size() == SourceTPL->size());
 253
 254     for (size_t I = 0, EP = DestTPL->size(); I != EP; ++I)
 255       HandleParam(DestTPL->getParam(I), SourceTPL->getParam(I));
 256   }
 257
 258   // Populate mapping for function params.
 259   assert(Dest->param_size() == Source->param_size());
 260   for (size_t I = 0, E = Dest->param_size(); I != E; ++I)
 261     HandleParam(Dest->getParamDecl(I), Source->getParamDecl(I));
 262
 263   const SourceManager &SM = Dest->getASTContext().getSourceManager();
 264   const LangOptions &LangOpts = Dest->getASTContext().getLangOpts();
 265   // Collect other references in function signature, i.e parameter types and
 266   // default arguments.
 267   findExplicitReferences(
 268       // Use function template in case of templated functions to visit template
 269       // parameters.
 270       DestTempl ? llvm::dyn_cast<Decl>(DestTempl) : llvm::dyn_cast<Decl>(Dest),
 271       [&](ReferenceLoc Ref) {
 272         if (Ref.Targets.size() != 1)
 273           return;
 274         const auto *Target =
 275             llvm::cast<NamedDecl>(Ref.Targets.front()->getCanonicalDecl());
 276         auto It = ParamToNewName.find(Target);
 277         if (It == ParamToNewName.end())
 278           return;
 279         RefLocs[Target].push_back(Ref.NameLoc);
 280       },
 281       Resolver);
 282
 283   // Now try to generate edits for all the refs.
 284   tooling::Replacements Replacements;
 285   for (auto &Entry : RefLocs) {
 286     const auto *OldDecl = Entry.first;
 287     llvm::StringRef OldName = OldDecl->getName();
 288     llvm::StringRef NewName = ParamToNewName[OldDecl];
 289     for (SourceLocation RefLoc : Entry.second) {
 290       CharSourceRange ReplaceRange;
 291       // In case of unnamed parameters, we have an empty char range, whereas we
 292       // have a tokenrange at RefLoc with named parameters.
 293       if (OldName.empty())
 294         ReplaceRange = CharSourceRange::getCharRange(RefLoc, RefLoc);
 295       else
 296         ReplaceRange = CharSourceRange::getTokenRange(RefLoc, RefLoc);
 297       // If occurrence is coming from a macro expansion, try to get back to the
 298       // file range.
 299       if (RefLoc.isMacroID()) {
 300         ReplaceRange = Lexer::makeFileCharRange(ReplaceRange, SM, LangOpts);
 301         // Bail out if we need to replace macro bodies.
 302         if (ReplaceRange.isInvalid()) {
 303           auto Err = error("Cant rename parameter inside macro body.");
 304           elog("define inline: {0}", Err);
 305           return std::move(Err);
 306         }
 307       }
 308
 309       if (auto Err = Replacements.add(
 310               tooling::Replacement(SM, ReplaceRange, NewName))) {
 311         elog("define inline: Couldn't replace parameter name for {0} to {1}: "
 312              "{2}",
 313              OldName, NewName, Err);
 314         return std::move(Err);
 315       }
 316     }
 317   }
 318   return Replacements;
 319 }
 320
 321 // Returns the canonical declaration for the given FunctionDecl. This will
 322 // usually be the first declaration in current translation unit with the
 323 // exception of template specialization.
 324 // For those we return first declaration different than the canonical one.
 325 // Because canonical declaration points to template decl instead of
 326 // specialization.
 327 const FunctionDecl *findTarget(const FunctionDecl *FD) {
 328   auto *CanonDecl = FD->getCanonicalDecl();
 329   if (!FD->isFunctionTemplateSpecialization() || CanonDecl == FD)
 330     return CanonDecl;
 331   // For specializations CanonicalDecl is the TemplatedDecl, which is not the
 332   // target we want to inline into. Instead we traverse previous decls to find
 333   // the first forward decl for this specialization.
 334   auto *PrevDecl = FD;
 335   while (PrevDecl->getPreviousDecl() != CanonDecl) {
 336     PrevDecl = PrevDecl->getPreviousDecl();
 337     assert(PrevDecl && "Found specialization without template decl");
 338   }
 339   return PrevDecl;
 340 }
 341
 342 // Returns the beginning location for a FunctionDecl. Returns location of
 343 // template keyword for templated functions.
 344 const SourceLocation getBeginLoc(const FunctionDecl *FD) {
 345   // Include template parameter list.
 346   if (auto *FTD = FD->getDescribedFunctionTemplate())
 347     return FTD->getBeginLoc();
 348   return FD->getBeginLoc();
 349 }
 350
 351 std::optional<tooling::Replacement>
 352 addInlineIfInHeader(const FunctionDecl *FD) {
 353   // This includes inline functions and constexpr functions.
 354   if (FD->isInlined() || llvm::isa<CXXMethodDecl>(FD))
 355     return std::nullopt;
 356   // Primary template doesn't need inline.
 357   if (FD->isTemplated() && !FD->isFunctionTemplateSpecialization())
 358     return std::nullopt;
 359
 360   const SourceManager &SM = FD->getASTContext().getSourceManager();
 361   llvm::StringRef FileName = SM.getFilename(FD->getLocation());
 362
 363   // If it is not a header we don't need to mark function as "inline".
 364   if (!isHeaderFile(FileName, FD->getASTContext().getLangOpts()))
 365     return std::nullopt;
 366
 367   return tooling::Replacement(SM, FD->getInnerLocStart(), 0, "inline ");
 368 }
 369
 370 /// Moves definition of a function/method to its declaration location.
 371 /// Before:
 372 /// a.h:
 373 ///   void foo();
 374 ///
 375 /// a.cc:
 376 ///   void foo() { return; }
 377 ///
 378 /// ------------------------
 379 /// After:
 380 /// a.h:
 381 ///   void foo() { return; }
 382 ///
 383 /// a.cc:
 384 ///
 385 class DefineInline : public Tweak {
 386 public:
 387   const char *id() const final;
 388
 389   llvm::StringLiteral kind() const override {
 390     return CodeAction::REFACTOR_KIND;
 391   }
 392   std::string title() const override {
 393     return "Move function body to declaration";
 394   }
 395
 396   // Returns true when selection is on a function definition that does not
 397   // make use of any internal symbols.
 398   bool prepare(const Selection &Sel) override {
 399     const SelectionTree::Node *SelNode = Sel.ASTSelection.commonAncestor();
 400     if (!SelNode)
 401       return false;
 402     Source = getSelectedFunction(SelNode);
 403     if (!Source || !Source->hasBody())
 404       return false;
 405     // Only the last level of template parameter locations are not kept in AST,
 406     // so if we are inlining a method that is in a templated class, there is no
 407     // way to verify template parameter names. Therefore we bail out.
 408     if (auto *MD = llvm::dyn_cast<CXXMethodDecl>(Source)) {
 409       if (MD->getParent()->isTemplated())
 410         return false;
 411     }
 412     // If function body starts or ends inside a macro, we refuse to move it into
 413     // declaration location.
 414     if (Source->getBody()->getBeginLoc().isMacroID() ||
 415         Source->getBody()->getEndLoc().isMacroID())
 416       return false;
 417
 418     Target = findTarget(Source);
 419     if (Target == Source) {
 420       // The only declaration is Source. No other declaration to move function
 421       // body.
 422       // FIXME: If we are in an implementation file, figure out a suitable
 423       // location to put declaration. Possibly using other declarations in the
 424       // AST.
 425       return false;
 426     }
 427
 428     // Check if the decls referenced in function body are visible in the
 429     // declaration location.
 430     if (!checkDeclsAreVisible(getNonLocalDeclRefs(*Sel.AST, Source), Target,
 431                               Sel.AST->getSourceManager()))
 432       return false;
 433
 434     return true;
 435   }
 436
 437   Expected<Effect> apply(const Selection &Sel) override {
 438     const auto &AST = Sel.AST->getASTContext();
 439     const auto &SM = AST.getSourceManager();
 440
 441     auto Semicolon = getSemicolonForDecl(Target);
 442     if (!Semicolon)
 443       return error("Couldn't find semicolon for target declaration.");
 444
 445     auto AddInlineIfNecessary = addInlineIfInHeader(Target);
 446     auto ParamReplacements =
 447         renameParameters(Target, Source, Sel.AST->getHeuristicResolver());
 448     if (!ParamReplacements)
 449       return ParamReplacements.takeError();
 450
 451     auto QualifiedBody =
 452         qualifyAllDecls(Source, Target, Sel.AST->getHeuristicResolver());
 453     if (!QualifiedBody)
 454       return QualifiedBody.takeError();
 455
 456     const tooling::Replacement SemicolonToFuncBody(SM, *Semicolon, 1,
 457                                                    *QualifiedBody);
 458     tooling::Replacements TargetFileReplacements(SemicolonToFuncBody);
 459     TargetFileReplacements = TargetFileReplacements.merge(*ParamReplacements);
 460     if (AddInlineIfNecessary) {
 461       if (auto Err = TargetFileReplacements.add(*AddInlineIfNecessary))
 462         return std::move(Err);
 463     }
 464
 465     auto DefRange = toHalfOpenFileRange(
 466         SM, AST.getLangOpts(),
 467         SM.getExpansionRange(CharSourceRange::getCharRange(getBeginLoc(Source),
 468                                                            Source->getEndLoc()))
 469             .getAsRange());
 470     if (!DefRange)
 471       return error("Couldn't get range for the source.");
 472     unsigned int SourceLen = SM.getFileOffset(DefRange->getEnd()) -
 473                              SM.getFileOffset(DefRange->getBegin());
 474     const tooling::Replacement DeleteFuncBody(SM, DefRange->getBegin(),
 475                                               SourceLen, "");
 476
 477     llvm::SmallVector<std::pair<std::string, Edit>> Edits;
 478     // Edit for Target.
 479     auto FE = Effect::fileEdit(SM, SM.getFileID(*Semicolon),
 480                                std::move(TargetFileReplacements));
 481     if (!FE)
 482       return FE.takeError();
 483     Edits.push_back(std::move(*FE));
 484
 485     // Edit for Source.
 486     if (!SM.isWrittenInSameFile(DefRange->getBegin(),
 487                                 SM.getExpansionLoc(Target->getBeginLoc()))) {
 488       // Generate a new edit if the Source and Target are in different files.
 489       auto FE = Effect::fileEdit(SM, SM.getFileID(Sel.Cursor),
 490                                  tooling::Replacements(DeleteFuncBody));
 491       if (!FE)
 492         return FE.takeError();
 493       Edits.push_back(std::move(*FE));
 494     } else {
 495       // Merge with previous edit if they are in the same file.
 496       if (auto Err = Edits.front().second.Replacements.add(DeleteFuncBody))
 497         return std::move(Err);
 498     }
 499
 500     Effect E;
 501     for (auto &Pair : Edits)
 502       E.ApplyEdits.try_emplace(std::move(Pair.first), std::move(Pair.second));
 503     return E;
 504   }
 505
 506 private:
 507   const FunctionDecl *Source = nullptr;
 508   const FunctionDecl *Target = nullptr;
 509 };
 510
 511 REGISTER_TWEAK(DefineInline)
 512
 513 } // namespace
 514 } // namespace clangd
 515 } // namespace clang