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