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

   1 //===--- DefineOutline.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 "HeaderSourceSwitch.h"
  12 #include "ParsedAST.h"
  13 #include "Selection.h"
  14 #include "SourceCode.h"
  15 #include "refactor/Tweak.h"
  16 #include "support/Logger.h"
  17 #include "support/Path.h"
  18 #include "clang/AST/ASTTypeTraits.h"
  19 #include "clang/AST/Attr.h"
  20 #include "clang/AST/Decl.h"
  21 #include "clang/AST/DeclBase.h"
  22 #include "clang/AST/DeclCXX.h"
  23 #include "clang/AST/DeclTemplate.h"
  24 #include "clang/AST/Stmt.h"
  25 #include "clang/Basic/SourceLocation.h"
  26 #include "clang/Basic/SourceManager.h"
  27 #include "clang/Basic/TokenKinds.h"
  28 #include "clang/Tooling/Core/Replacement.h"
  29 #include "clang/Tooling/Syntax/Tokens.h"
  30 #include "llvm/ADT/STLExtras.h"
  31 #include "llvm/ADT/StringRef.h"
  32 #include "llvm/Support/Casting.h"
  33 #include "llvm/Support/Error.h"
  34 #include <cstddef>
  35 #include <optional>
  36 #include <string>
  37
  38 namespace clang {
  39 namespace clangd {
  40 namespace {
  41
  42 // Deduces the FunctionDecl from a selection. Requires either the function body
  43 // or the function decl to be selected. Returns null if none of the above
  44 // criteria is met.
  45 // FIXME: This is shared with define inline, move them to a common header once
  46 // we have a place for such.
  47 const FunctionDecl *getSelectedFunction(const SelectionTree::Node *SelNode) {
  48   if (!SelNode)
  49     return nullptr;
  50   const DynTypedNode &AstNode = SelNode->ASTNode;
  51   if (const FunctionDecl *FD = AstNode.get<FunctionDecl>())
  52     return FD;
  53   if (AstNode.get<CompoundStmt>() &&
  54       SelNode->Selected == SelectionTree::Complete) {
  55     if (const SelectionTree::Node *P = SelNode->Parent)
  56       return P->ASTNode.get<FunctionDecl>();
  57   }
  58   return nullptr;
  59 }
  60
  61 std::optional<Path> getSourceFile(llvm::StringRef FileName,
  62                                   const Tweak::Selection &Sel) {
  63   assert(Sel.FS);
  64   if (auto Source = getCorrespondingHeaderOrSource(FileName, Sel.FS))
  65     return *Source;
  66   return getCorrespondingHeaderOrSource(FileName, *Sel.AST, Sel.Index);
  67 }
  68
  69 // Synthesize a DeclContext for TargetNS from CurContext. TargetNS must be empty
  70 // for global namespace, and endwith "::" otherwise.
  71 // Returns std::nullopt if TargetNS is not a prefix of CurContext.
  72 std::optional<const DeclContext *>
  73 findContextForNS(llvm::StringRef TargetNS, const DeclContext *CurContext) {
  74   assert(TargetNS.empty() || TargetNS.endswith("::"));
  75   // Skip any non-namespace contexts, e.g. TagDecls, functions/methods.
  76   CurContext = CurContext->getEnclosingNamespaceContext();
  77   // If TargetNS is empty, it means global ns, which is translation unit.
  78   if (TargetNS.empty()) {
  79     while (!CurContext->isTranslationUnit())
  80       CurContext = CurContext->getParent();
  81     return CurContext;
  82   }
  83   // Otherwise we need to drop any trailing namespaces from CurContext until
  84   // we reach TargetNS.
  85   std::string TargetContextNS =
  86       CurContext->isNamespace()
  87           ? llvm::cast<NamespaceDecl>(CurContext)->getQualifiedNameAsString()
  88           : "";
  89   TargetContextNS.append("::");
  90
  91   llvm::StringRef CurrentContextNS(TargetContextNS);
  92   // If TargetNS is not a prefix of CurrentContext, there's no way to reach
  93   // it.
  94   if (!CurrentContextNS.startswith(TargetNS))
  95     return std::nullopt;
  96
  97   while (CurrentContextNS != TargetNS) {
  98     CurContext = CurContext->getParent();
  99     // These colons always exists since TargetNS is a prefix of
 100     // CurrentContextNS, it ends with "::" and they are not equal.
 101     CurrentContextNS = CurrentContextNS.take_front(
 102         CurrentContextNS.drop_back(2).rfind("::") + 2);
 103   }
 104   return CurContext;
 105 }
 106
 107 // Returns source code for FD after applying Replacements.
 108 // FIXME: Make the function take a parameter to return only the function body,
 109 // afterwards it can be shared with define-inline code action.
 110 llvm::Expected<std::string>
 111 getFunctionSourceAfterReplacements(const FunctionDecl *FD,
 112                                    const tooling::Replacements &Replacements) {
 113   const auto &SM = FD->getASTContext().getSourceManager();
 114   auto OrigFuncRange = toHalfOpenFileRange(
 115       SM, FD->getASTContext().getLangOpts(), FD->getSourceRange());
 116   if (!OrigFuncRange)
 117     return error("Couldn't get range for function.");
 118   assert(!FD->getDescribedFunctionTemplate() &&
 119          "Define out-of-line doesn't apply to function templates.");
 120
 121   // Get new begin and end positions for the qualified function definition.
 122   unsigned FuncBegin = SM.getFileOffset(OrigFuncRange->getBegin());
 123   unsigned FuncEnd = Replacements.getShiftedCodePosition(
 124       SM.getFileOffset(OrigFuncRange->getEnd()));
 125
 126   // Trim the result to function definition.
 127   auto QualifiedFunc = tooling::applyAllReplacements(
 128       SM.getBufferData(SM.getMainFileID()), Replacements);
 129   if (!QualifiedFunc)
 130     return QualifiedFunc.takeError();
 131   return QualifiedFunc->substr(FuncBegin, FuncEnd - FuncBegin + 1);
 132 }
 133
 134 // Returns replacements to delete tokens with kind `Kind` in the range
 135 // `FromRange`. Removes matching instances of given token preceeding the
 136 // function defition.
 137 llvm::Expected<tooling::Replacements>
 138 deleteTokensWithKind(const syntax::TokenBuffer &TokBuf, tok::TokenKind Kind,
 139                      SourceRange FromRange) {
 140   tooling::Replacements DelKeywordCleanups;
 141   llvm::Error Errors = llvm::Error::success();
 142   bool FoundAny = false;
 143   for (const auto &Tok : TokBuf.expandedTokens(FromRange)) {
 144     if (Tok.kind() != Kind)
 145       continue;
 146     FoundAny = true;
 147     auto Spelling = TokBuf.spelledForExpanded(llvm::ArrayRef(Tok));
 148     if (!Spelling) {
 149       Errors = llvm::joinErrors(
 150           std::move(Errors),
 151           error("define outline: couldn't remove `{0}` keyword.",
 152                 tok::getKeywordSpelling(Kind)));
 153       break;
 154     }
 155     auto &SM = TokBuf.sourceManager();
 156     CharSourceRange DelRange =
 157         syntax::Token::range(SM, Spelling->front(), Spelling->back())
 158             .toCharRange(SM);
 159     if (auto Err =
 160             DelKeywordCleanups.add(tooling::Replacement(SM, DelRange, "")))
 161       Errors = llvm::joinErrors(std::move(Errors), std::move(Err));
 162   }
 163   if (!FoundAny) {
 164     Errors = llvm::joinErrors(
 165         std::move(Errors),
 166         error("define outline: couldn't find `{0}` keyword to remove.",
 167               tok::getKeywordSpelling(Kind)));
 168   }
 169
 170   if (Errors)
 171     return std::move(Errors);
 172   return DelKeywordCleanups;
 173 }
 174
 175 // Creates a modified version of function definition that can be inserted at a
 176 // different location, qualifies return value and function name to achieve that.
 177 // Contains function signature, except defaulted parameter arguments, body and
 178 // template parameters if applicable. No need to qualify parameters, as they are
 179 // looked up in the context containing the function/method.
 180 // FIXME: Drop attributes in function signature.
 181 llvm::Expected<std::string>
 182 getFunctionSourceCode(const FunctionDecl *FD, llvm::StringRef TargetNamespace,
 183                       const syntax::TokenBuffer &TokBuf,
 184                       const HeuristicResolver *Resolver) {
 185   auto &AST = FD->getASTContext();
 186   auto &SM = AST.getSourceManager();
 187   auto TargetContext = findContextForNS(TargetNamespace, FD->getDeclContext());
 188   if (!TargetContext)
 189     return error("define outline: couldn't find a context for target");
 190
 191   llvm::Error Errors = llvm::Error::success();
 192   tooling::Replacements DeclarationCleanups;
 193
 194   // Finds the first unqualified name in function return type and name, then
 195   // qualifies those to be valid in TargetContext.
 196   findExplicitReferences(
 197       FD,
 198       [&](ReferenceLoc Ref) {
 199         // It is enough to qualify the first qualifier, so skip references with
 200         // a qualifier. Also we can't do much if there are no targets or name is
 201         // inside a macro body.
 202         if (Ref.Qualifier || Ref.Targets.empty() || Ref.NameLoc.isMacroID())
 203           return;
 204         // Only qualify return type and function name.
 205         if (Ref.NameLoc != FD->getReturnTypeSourceRange().getBegin() &&
 206             Ref.NameLoc != FD->getLocation())
 207           return;
 208
 209         for (const NamedDecl *ND : Ref.Targets) {
 210           if (ND->getDeclContext() != Ref.Targets.front()->getDeclContext()) {
 211             elog("Targets from multiple contexts: {0}, {1}",
 212                  printQualifiedName(*Ref.Targets.front()),
 213                  printQualifiedName(*ND));
 214             return;
 215           }
 216         }
 217         const NamedDecl *ND = Ref.Targets.front();
 218         const std::string Qualifier =
 219             getQualification(AST, *TargetContext,
 220                              SM.getLocForStartOfFile(SM.getMainFileID()), ND);
 221         if (auto Err = DeclarationCleanups.add(
 222                 tooling::Replacement(SM, Ref.NameLoc, 0, Qualifier)))
 223           Errors = llvm::joinErrors(std::move(Errors), std::move(Err));
 224       },
 225       Resolver);
 226
 227   // findExplicitReferences doesn't provide references to
 228   // constructor/destructors, it only provides references to type names inside
 229   // them.
 230   // this works for constructors, but doesn't work for destructor as type name
 231   // doesn't cover leading `~`, so handle it specially.
 232   if (const auto *Destructor = llvm::dyn_cast<CXXDestructorDecl>(FD)) {
 233     if (auto Err = DeclarationCleanups.add(tooling::Replacement(
 234             SM, Destructor->getLocation(), 0,
 235             getQualification(AST, *TargetContext,
 236                              SM.getLocForStartOfFile(SM.getMainFileID()),
 237                              Destructor))))
 238       Errors = llvm::joinErrors(std::move(Errors), std::move(Err));
 239   }
 240
 241   // Get rid of default arguments, since they should not be specified in
 242   // out-of-line definition.
 243   for (const auto *PVD : FD->parameters()) {
 244     if (!PVD->hasDefaultArg())
 245       continue;
 246     // Deletion range spans the initializer, usually excluding the `=`.
 247     auto DelRange = CharSourceRange::getTokenRange(PVD->getDefaultArgRange());
 248     // Get all tokens before the default argument.
 249     auto Tokens = TokBuf.expandedTokens(PVD->getSourceRange())
 250                       .take_while([&SM, &DelRange](const syntax::Token &Tok) {
 251                         return SM.isBeforeInTranslationUnit(
 252                             Tok.location(), DelRange.getBegin());
 253                       });
 254     if (TokBuf.expandedTokens(DelRange.getAsRange()).front().kind() !=
 255         tok::equal) {
 256       // Find the last `=` if it isn't included in the initializer, and update
 257       // the DelRange to include it.
 258       auto Tok =
 259           llvm::find_if(llvm::reverse(Tokens), [](const syntax::Token &Tok) {
 260             return Tok.kind() == tok::equal;
 261           });
 262       assert(Tok != Tokens.rend());
 263       DelRange.setBegin(Tok->location());
 264     }
 265     if (auto Err =
 266             DeclarationCleanups.add(tooling::Replacement(SM, DelRange, "")))
 267       Errors = llvm::joinErrors(std::move(Errors), std::move(Err));
 268   }
 269
 270   auto DelAttr = [&](const Attr *A) {
 271     if (!A)
 272       return;
 273     auto AttrTokens =
 274         TokBuf.spelledForExpanded(TokBuf.expandedTokens(A->getRange()));
 275     assert(A->getLocation().isValid());
 276     if (!AttrTokens || AttrTokens->empty()) {
 277       Errors = llvm::joinErrors(
 278           std::move(Errors), error("define outline: Can't move out of line as "
 279                                    "function has a macro `{0}` specifier.",
 280                                    A->getSpelling()));
 281       return;
 282     }
 283     CharSourceRange DelRange =
 284         syntax::Token::range(SM, AttrTokens->front(), AttrTokens->back())
 285             .toCharRange(SM);
 286     if (auto Err =
 287             DeclarationCleanups.add(tooling::Replacement(SM, DelRange, "")))
 288       Errors = llvm::joinErrors(std::move(Errors), std::move(Err));
 289   };
 290
 291   DelAttr(FD->getAttr<OverrideAttr>());
 292   DelAttr(FD->getAttr<FinalAttr>());
 293
 294   auto DelKeyword = [&](tok::TokenKind Kind, SourceRange FromRange) {
 295     auto DelKeywords = deleteTokensWithKind(TokBuf, Kind, FromRange);
 296     if (!DelKeywords) {
 297       Errors = llvm::joinErrors(std::move(Errors), DelKeywords.takeError());
 298       return;
 299     }
 300     DeclarationCleanups = DeclarationCleanups.merge(*DelKeywords);
 301   };
 302
 303   if (FD->isInlineSpecified())
 304     DelKeyword(tok::kw_inline, {FD->getBeginLoc(), FD->getLocation()});
 305   if (const auto *MD = dyn_cast<CXXMethodDecl>(FD)) {
 306     if (MD->isVirtualAsWritten())
 307       DelKeyword(tok::kw_virtual, {FD->getBeginLoc(), FD->getLocation()});
 308     if (MD->isStatic())
 309       DelKeyword(tok::kw_static, {FD->getBeginLoc(), FD->getLocation()});
 310   }
 311   if (const auto *CD = dyn_cast<CXXConstructorDecl>(FD)) {
 312     if (CD->isExplicit())
 313       DelKeyword(tok::kw_explicit, {FD->getBeginLoc(), FD->getLocation()});
 314   }
 315
 316   if (Errors)
 317     return std::move(Errors);
 318   return getFunctionSourceAfterReplacements(FD, DeclarationCleanups);
 319 }
 320
 321 struct InsertionPoint {
 322   std::string EnclosingNamespace;
 323   size_t Offset;
 324 };
 325 // Returns the most natural insertion point for \p QualifiedName in \p Contents.
 326 // This currently cares about only the namespace proximity, but in feature it
 327 // should also try to follow ordering of declarations. For example, if decls
 328 // come in order `foo, bar, baz` then this function should return some point
 329 // between foo and baz for inserting bar.
 330 llvm::Expected<InsertionPoint> getInsertionPoint(llvm::StringRef Contents,
 331                                                  llvm::StringRef QualifiedName,
 332                                                  const LangOptions &LangOpts) {
 333   auto Region = getEligiblePoints(Contents, QualifiedName, LangOpts);
 334
 335   assert(!Region.EligiblePoints.empty());
 336   // FIXME: This selection can be made smarter by looking at the definition
 337   // locations for adjacent decls to Source. Unfortunately pseudo parsing in
 338   // getEligibleRegions only knows about namespace begin/end events so we
 339   // can't match function start/end positions yet.
 340   auto Offset = positionToOffset(Contents, Region.EligiblePoints.back());
 341   if (!Offset)
 342     return Offset.takeError();
 343   return InsertionPoint{Region.EnclosingNamespace, *Offset};
 344 }
 345
 346 // Returns the range that should be deleted from declaration, which always
 347 // contains function body. In addition to that it might contain constructor
 348 // initializers.
 349 SourceRange getDeletionRange(const FunctionDecl *FD,
 350                              const syntax::TokenBuffer &TokBuf) {
 351   auto DeletionRange = FD->getBody()->getSourceRange();
 352   if (auto *CD = llvm::dyn_cast<CXXConstructorDecl>(FD)) {
 353     // AST doesn't contain the location for ":" in ctor initializers. Therefore
 354     // we find it by finding the first ":" before the first ctor initializer.
 355     SourceLocation InitStart;
 356     // Find the first initializer.
 357     for (const auto *CInit : CD->inits()) {
 358       // SourceOrder is -1 for implicit initializers.
 359       if (CInit->getSourceOrder() != 0)
 360         continue;
 361       InitStart = CInit->getSourceLocation();
 362       break;
 363     }
 364     if (InitStart.isValid()) {
 365       auto Toks = TokBuf.expandedTokens(CD->getSourceRange());
 366       // Drop any tokens after the initializer.
 367       Toks = Toks.take_while([&TokBuf, &InitStart](const syntax::Token &Tok) {
 368         return TokBuf.sourceManager().isBeforeInTranslationUnit(Tok.location(),
 369                                                                 InitStart);
 370       });
 371       // Look for the first colon.
 372       auto Tok =
 373           llvm::find_if(llvm::reverse(Toks), [](const syntax::Token &Tok) {
 374             return Tok.kind() == tok::colon;
 375           });
 376       assert(Tok != Toks.rend());
 377       DeletionRange.setBegin(Tok->location());
 378     }
 379   }
 380   return DeletionRange;
 381 }
 382
 383 /// Moves definition of a function/method to an appropriate implementation file.
 384 ///
 385 /// Before:
 386 /// a.h
 387 ///   void foo() { return; }
 388 /// a.cc
 389 ///   #include "a.h"
 390 ///
 391 /// ----------------
 392 ///
 393 /// After:
 394 /// a.h
 395 ///   void foo();
 396 /// a.cc
 397 ///   #include "a.h"
 398 ///   void foo() { return; }
 399 class DefineOutline : public Tweak {
 400 public:
 401   const char *id() const override;
 402
 403   bool hidden() const override { return false; }
 404   llvm::StringLiteral kind() const override {
 405     return CodeAction::REFACTOR_KIND;
 406   }
 407   std::string title() const override {
 408     return "Move function body to out-of-line";
 409   }
 410
 411   bool prepare(const Selection &Sel) override {
 412     // Bail out if we are not in a header file.
 413     // FIXME: We might want to consider moving method definitions below class
 414     // definition even if we are inside a source file.
 415     if (!isHeaderFile(Sel.AST->getSourceManager().getFilename(Sel.Cursor),
 416                       Sel.AST->getLangOpts()))
 417       return false;
 418
 419     Source = getSelectedFunction(Sel.ASTSelection.commonAncestor());
 420     // Bail out if the selection is not a in-line function definition.
 421     if (!Source || !Source->doesThisDeclarationHaveABody() ||
 422         Source->isOutOfLine())
 423       return false;
 424
 425     // Bail out if this is a function template or specialization, as their
 426     // definitions need to be visible in all including translation units.
 427     if (Source->getDescribedFunctionTemplate())
 428       return false;
 429     if (Source->getTemplateSpecializationInfo())
 430       return false;
 431
 432     if (auto *MD = llvm::dyn_cast<CXXMethodDecl>(Source)) {
 433       // Bail out in templated classes, as it is hard to spell the class name,
 434       // i.e if the template parameter is unnamed.
 435       if (MD->getParent()->isTemplated())
 436         return false;
 437
 438       // The refactoring is meaningless for unnamed classes and definitions
 439       // within unnamed namespaces.
 440       for (const DeclContext *DC = MD->getParent(); DC; DC = DC->getParent()) {
 441         if (auto *ND = llvm::dyn_cast<NamedDecl>(DC)) {
 442           if (ND->getDeclName().isEmpty())
 443             return false;
 444         }
 445       }
 446     }
 447
 448     // Note that we don't check whether an implementation file exists or not in
 449     // the prepare, since performing disk IO on each prepare request might be
 450     // expensive.
 451     return true;
 452   }
 453
 454   Expected<Effect> apply(const Selection &Sel) override {
 455     const SourceManager &SM = Sel.AST->getSourceManager();
 456     auto CCFile = getSourceFile(Sel.AST->tuPath(), Sel);
 457
 458     if (!CCFile)
 459       return error("Couldn't find a suitable implementation file.");
 460     assert(Sel.FS && "FS Must be set in apply");
 461     auto Buffer = Sel.FS->getBufferForFile(*CCFile);
 462     // FIXME: Maybe we should consider creating the implementation file if it
 463     // doesn't exist?
 464     if (!Buffer)
 465       return llvm::errorCodeToError(Buffer.getError());
 466     auto Contents = Buffer->get()->getBuffer();
 467     auto InsertionPoint = getInsertionPoint(
 468         Contents, Source->getQualifiedNameAsString(), Sel.AST->getLangOpts());
 469     if (!InsertionPoint)
 470       return InsertionPoint.takeError();
 471
 472     auto FuncDef = getFunctionSourceCode(
 473         Source, InsertionPoint->EnclosingNamespace, Sel.AST->getTokens(),
 474         Sel.AST->getHeuristicResolver());
 475     if (!FuncDef)
 476       return FuncDef.takeError();
 477
 478     SourceManagerForFile SMFF(*CCFile, Contents);
 479     const tooling::Replacement InsertFunctionDef(
 480         *CCFile, InsertionPoint->Offset, 0, *FuncDef);
 481     auto Effect = Effect::mainFileEdit(
 482         SMFF.get(), tooling::Replacements(InsertFunctionDef));
 483     if (!Effect)
 484       return Effect.takeError();
 485
 486     tooling::Replacements HeaderUpdates(tooling::Replacement(
 487         Sel.AST->getSourceManager(),
 488         CharSourceRange::getTokenRange(*toHalfOpenFileRange(
 489             SM, Sel.AST->getLangOpts(),
 490             getDeletionRange(Source, Sel.AST->getTokens()))),
 491         ";"));
 492
 493     if (Source->isInlineSpecified()) {
 494       auto DelInline =
 495           deleteTokensWithKind(Sel.AST->getTokens(), tok::kw_inline,
 496                                {Source->getBeginLoc(), Source->getLocation()});
 497       if (!DelInline)
 498         return DelInline.takeError();
 499       HeaderUpdates = HeaderUpdates.merge(*DelInline);
 500     }
 501
 502     auto HeaderFE = Effect::fileEdit(SM, SM.getMainFileID(), HeaderUpdates);
 503     if (!HeaderFE)
 504       return HeaderFE.takeError();
 505
 506     Effect->ApplyEdits.try_emplace(HeaderFE->first,
 507                                    std::move(HeaderFE->second));
 508     return std::move(*Effect);
 509   }
 510
 511 private:
 512   const FunctionDecl *Source = nullptr;
 513 };
 514
 515 REGISTER_TWEAK(DefineOutline)
 516
 517 } // namespace
 518 } // namespace clangd
 519 } // namespace clang