[clang-tools-extra] NFC: Fix trivial typo in documents and comments
[lldb.git] / 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 "Logger.h"
12 #include "Selection.h"
13 #include "SourceCode.h"
14 #include "XRefs.h"
15 #include "refactor/Tweak.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 ast_type_traits::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   // There are three types of spellings that needs to be qualified in a function
144   // body:
145   // - Types:       Foo                 -> ns::Foo
146   // - DeclRefExpr: ns2::foo()          -> ns1::ns2::foo();
147   // - UsingDecls:
148   //    using ns2::foo      -> using ns1::ns2::foo
149   //    using namespace ns2 -> using namespace ns1::ns2
150   //    using ns3 = ns2     -> using ns3 = ns1::ns2
151   //
152   // Go over all references inside a function body to generate replacements that
153   // will qualify those. So that body can be moved into an arbitrary file.
154   // We perform the qualification by qualifying the first type/decl in a
155   // (un)qualified name. e.g:
156   //    namespace a { namespace b { class Bar{}; void foo(); } }
157   //    b::Bar x; -> a::b::Bar x;
158   //    foo(); -> a::b::foo();
159
160   auto *TargetContext = Target->getLexicalDeclContext();
161   const SourceManager &SM = FD->getASTContext().getSourceManager();
162
163   tooling::Replacements Replacements;
164   bool HadErrors = false;
165   findExplicitReferences(FD->getBody(), [&](ReferenceLoc Ref) {
166     // Since we want to qualify only the first qualifier, skip names with a
167     // qualifier.
168     if (Ref.Qualifier)
169       return;
170     // There might be no decl in dependent contexts, there's nothing much we can
171     // do in such cases.
172     if (Ref.Targets.empty())
173       return;
174     // Do not qualify names introduced by macro expansions.
175     if (Ref.NameLoc.isMacroID())
176       return;
177
178     for (const NamedDecl *ND : Ref.Targets) {
179       if (ND->getDeclContext() != Ref.Targets.front()->getDeclContext()) {
180         elog("define inline: Targets from multiple contexts: {0}, {1}",
181              printQualifiedName(*Ref.Targets.front()), printQualifiedName(*ND));
182         HadErrors = true;
183         return;
184       }
185     }
186     // All Targets are in the same scope, so we can safely chose first one.
187     const NamedDecl *ND = Ref.Targets.front();
188     // Skip anything from a non-namespace scope, these can be:
189     // - Function or Method scopes, which means decl is local and doesn't need
190     //   qualification.
191     // - From Class/Struct/Union scope, which again doesn't need any qualifiers,
192     //   rather the left side of it requires qualification, like:
193     //   namespace a { class Bar { public: static int x; } }
194     //   void foo() { Bar::x; }
195     //                ~~~~~ -> we need to qualify Bar not x.
196     if (!ND->getDeclContext()->isNamespace())
197       return;
198
199     const std::string Qualifier = getQualification(
200         FD->getASTContext(), TargetContext, Target->getBeginLoc(), ND);
201     if (auto Err = Replacements.add(
202             tooling::Replacement(SM, Ref.NameLoc, 0, Qualifier))) {
203       HadErrors = true;
204       elog("define inline: Failed to add quals: {0}", std::move(Err));
205     }
206   });
207
208   if (HadErrors) {
209     return llvm::createStringError(
210         llvm::inconvertibleErrorCode(),
211         "define inline: Failed to compute qualifiers see logs for details.");
212   }
213
214   // Get new begin and end positions for the qualified body.
215   auto OrigBodyRange = toHalfOpenFileRange(
216       SM, FD->getASTContext().getLangOpts(), FD->getBody()->getSourceRange());
217   if (!OrigBodyRange)
218     return llvm::createStringError(llvm::inconvertibleErrorCode(),
219                                    "Couldn't get range func body.");
220
221   unsigned BodyBegin = SM.getFileOffset(OrigBodyRange->getBegin());
222   unsigned BodyEnd = Replacements.getShiftedCodePosition(
223       SM.getFileOffset(OrigBodyRange->getEnd()));
224
225   // Trim the result to function body.
226   auto QualifiedFunc = tooling::applyAllReplacements(
227       SM.getBufferData(SM.getFileID(OrigBodyRange->getBegin())), Replacements);
228   if (!QualifiedFunc)
229     return QualifiedFunc.takeError();
230   return QualifiedFunc->substr(BodyBegin, BodyEnd - BodyBegin + 1);
231 }
232
233 /// Generates Replacements for changing template and function parameter names in
234 /// \p Dest to be the same as in \p Source.
235 llvm::Expected<tooling::Replacements>
236 renameParameters(const FunctionDecl *Dest, const FunctionDecl *Source) {
237   llvm::DenseMap<const Decl *, std::string> ParamToNewName;
238   llvm::DenseMap<const NamedDecl *, std::vector<SourceLocation>> RefLocs;
239   auto HandleParam = [&](const NamedDecl *DestParam,
240                          const NamedDecl *SourceParam) {
241     // No need to rename if parameters already have the same name.
242     if (DestParam->getName() == SourceParam->getName())
243       return;
244     std::string NewName;
245     // Unnamed parameters won't be visited in findExplicitReferences. So add
246     // them here.
247     if (DestParam->getName().empty()) {
248       RefLocs[DestParam].push_back(DestParam->getLocation());
249       // If decl is unnamed in destination we pad the new name to avoid gluing
250       // with previous token, e.g. foo(int^) shouldn't turn into foo(intx).
251       NewName = " ";
252     }
253     NewName.append(std::string(SourceParam->getName()));
254     ParamToNewName[DestParam->getCanonicalDecl()] = std::move(NewName);
255   };
256
257   // Populate mapping for template parameters.
258   auto *DestTempl = Dest->getDescribedFunctionTemplate();
259   auto *SourceTempl = Source->getDescribedFunctionTemplate();
260   assert(bool(DestTempl) == bool(SourceTempl));
261   if (DestTempl) {
262     const auto *DestTPL = DestTempl->getTemplateParameters();
263     const auto *SourceTPL = SourceTempl->getTemplateParameters();
264     assert(DestTPL->size() == SourceTPL->size());
265
266     for (size_t I = 0, EP = DestTPL->size(); I != EP; ++I)
267       HandleParam(DestTPL->getParam(I), SourceTPL->getParam(I));
268   }
269
270   // Populate mapping for function params.
271   assert(Dest->param_size() == Source->param_size());
272   for (size_t I = 0, E = Dest->param_size(); I != E; ++I)
273     HandleParam(Dest->getParamDecl(I), Source->getParamDecl(I));
274
275   const SourceManager &SM = Dest->getASTContext().getSourceManager();
276   const LangOptions &LangOpts = Dest->getASTContext().getLangOpts();
277   // Collect other references in function signature, i.e parameter types and
278   // default arguments.
279   findExplicitReferences(
280       // Use function template in case of templated functions to visit template
281       // parameters.
282       DestTempl ? llvm::dyn_cast<Decl>(DestTempl) : llvm::dyn_cast<Decl>(Dest),
283       [&](ReferenceLoc Ref) {
284         if (Ref.Targets.size() != 1)
285           return;
286         const auto *Target =
287             llvm::cast<NamedDecl>(Ref.Targets.front()->getCanonicalDecl());
288         auto It = ParamToNewName.find(Target);
289         if (It == ParamToNewName.end())
290           return;
291         RefLocs[Target].push_back(Ref.NameLoc);
292       });
293
294   // Now try to generate edits for all the refs.
295   tooling::Replacements Replacements;
296   for (auto &Entry : RefLocs) {
297     const auto *OldDecl = Entry.first;
298     llvm::StringRef OldName = OldDecl->getName();
299     llvm::StringRef NewName = ParamToNewName[OldDecl];
300     for (SourceLocation RefLoc : Entry.second) {
301       CharSourceRange ReplaceRange;
302       // In case of unnamed parameters, we have an empty char range, whereas we
303       // have a tokenrange at RefLoc with named parameters.
304       if (OldName.empty())
305         ReplaceRange = CharSourceRange::getCharRange(RefLoc, RefLoc);
306       else
307         ReplaceRange = CharSourceRange::getTokenRange(RefLoc, RefLoc);
308       // If occurrence is coming from a macro expansion, try to get back to the
309       // file range.
310       if (RefLoc.isMacroID()) {
311         ReplaceRange = Lexer::makeFileCharRange(ReplaceRange, SM, LangOpts);
312         // Bail out if we need to replace macro bodies.
313         if (ReplaceRange.isInvalid()) {
314           auto Err = llvm::createStringError(
315               llvm::inconvertibleErrorCode(),
316               "Cant rename parameter inside macro body.");
317           elog("define inline: {0}", Err);
318           return std::move(Err);
319         }
320       }
321
322       if (auto Err = Replacements.add(
323               tooling::Replacement(SM, ReplaceRange, NewName))) {
324         elog("define inline: Couldn't replace parameter name for {0} to {1}: "
325              "{2}",
326              OldName, NewName, Err);
327         return std::move(Err);
328       }
329     }
330   }
331   return Replacements;
332 }
333
334 // Returns the canonical declaration for the given FunctionDecl. This will
335 // usually be the first declaration in current translation unit with the
336 // exception of template specialization.
337 // For those we return first declaration different than the canonical one.
338 // Because canonical declaration points to template decl instead of
339 // specialization.
340 const FunctionDecl *findTarget(const FunctionDecl *FD) {
341   auto CanonDecl = FD->getCanonicalDecl();
342   if (!FD->isFunctionTemplateSpecialization())
343     return CanonDecl;
344   // For specializations CanonicalDecl is the TemplatedDecl, which is not the
345   // target we want to inline into. Instead we traverse previous decls to find
346   // the first forward decl for this specialization.
347   auto PrevDecl = FD;
348   while (PrevDecl->getPreviousDecl() != CanonDecl) {
349     PrevDecl = PrevDecl->getPreviousDecl();
350     assert(PrevDecl && "Found specialization without template decl");
351   }
352   return PrevDecl;
353 }
354
355 // Returns the beginning location for a FunctionDecl. Returns location of
356 // template keyword for templated functions.
357 const SourceLocation getBeginLoc(const FunctionDecl *FD) {
358   // Include template parameter list.
359   if (auto *FTD = FD->getDescribedFunctionTemplate())
360     return FTD->getBeginLoc();
361   return FD->getBeginLoc();
362 }
363
364 llvm::Optional<tooling::Replacement>
365 addInlineIfInHeader(const FunctionDecl *FD) {
366   // This includes inline functions and constexpr functions.
367   if (FD->isInlined() || llvm::isa<CXXMethodDecl>(FD))
368     return llvm::None;
369   // Primary template doesn't need inline.
370   if (FD->isTemplated() && !FD->isFunctionTemplateSpecialization())
371     return llvm::None;
372
373   const SourceManager &SM = FD->getASTContext().getSourceManager();
374   llvm::StringRef FileName = SM.getFilename(FD->getLocation());
375
376   // If it is not a header we don't need to mark function as "inline".
377   if (!isHeaderFile(FileName, FD->getASTContext().getLangOpts()))
378     return llvm::None;
379
380   return tooling::Replacement(SM, FD->getInnerLocStart(), 0, "inline ");
381 }
382
383 /// Moves definition of a function/method to its declaration location.
384 /// Before:
385 /// a.h:
386 ///   void foo();
387 ///
388 /// a.cc:
389 ///   void foo() { return; }
390 ///
391 /// ------------------------
392 /// After:
393 /// a.h:
394 ///   void foo() { return; }
395 ///
396 /// a.cc:
397 ///
398 class DefineInline : public Tweak {
399 public:
400   const char *id() const override final;
401
402   Intent intent() const override { return Intent::Refactor; }
403   std::string title() const override {
404     return "Move function body to declaration";
405   }
406
407   // Returns true when selection is on a function definition that does not
408   // make use of any internal symbols.
409   bool prepare(const Selection &Sel) override {
410     const SelectionTree::Node *SelNode = Sel.ASTSelection.commonAncestor();
411     if (!SelNode)
412       return false;
413     Source = getSelectedFunction(SelNode);
414     if (!Source || !Source->hasBody())
415       return false;
416     // Only the last level of template parameter locations are not kept in AST,
417     // so if we are inlining a method that is in a templated class, there is no
418     // way to verify template parameter names. Therefore we bail out.
419     if (auto *MD = llvm::dyn_cast<CXXMethodDecl>(Source)) {
420       if (MD->getParent()->isTemplated())
421         return false;
422     }
423     // If function body starts or ends inside a macro, we refuse to move it into
424     // declaration location.
425     if (Source->getBody()->getBeginLoc().isMacroID() ||
426         Source->getBody()->getEndLoc().isMacroID())
427       return false;
428
429     Target = findTarget(Source);
430     if (Target == Source) {
431       // The only declaration is Source. No other declaration to move function
432       // body.
433       // FIXME: If we are in an implementation file, figure out a suitable
434       // location to put declaration. Possibly using other declarations in the
435       // AST.
436       return false;
437     }
438
439     // Check if the decls referenced in function body are visible in the
440     // declaration location.
441     if (!checkDeclsAreVisible(getNonLocalDeclRefs(*Sel.AST, Source), Target,
442                               Sel.AST->getSourceManager()))
443       return false;
444
445     return true;
446   }
447
448   Expected<Effect> apply(const Selection &Sel) override {
449     const auto &AST = Sel.AST->getASTContext();
450     const auto &SM = AST.getSourceManager();
451
452     auto Semicolon = getSemicolonForDecl(Target);
453     if (!Semicolon) {
454       return llvm::createStringError(
455           llvm::inconvertibleErrorCode(),
456           "Couldn't find semicolon for target declaration.");
457     }
458
459     auto AddInlineIfNecessary = addInlineIfInHeader(Target);
460     auto ParamReplacements = renameParameters(Target, Source);
461     if (!ParamReplacements)
462       return ParamReplacements.takeError();
463
464     auto QualifiedBody = qualifyAllDecls(Source, Target);
465     if (!QualifiedBody)
466       return QualifiedBody.takeError();
467
468     const tooling::Replacement SemicolonToFuncBody(SM, *Semicolon, 1,
469                                                    *QualifiedBody);
470     tooling::Replacements TargetFileReplacements(SemicolonToFuncBody);
471     TargetFileReplacements = TargetFileReplacements.merge(*ParamReplacements);
472     if (AddInlineIfNecessary) {
473       if (auto Err = TargetFileReplacements.add(*AddInlineIfNecessary))
474         return std::move(Err);
475     }
476
477     auto DefRange = toHalfOpenFileRange(
478         SM, AST.getLangOpts(),
479         SM.getExpansionRange(CharSourceRange::getCharRange(getBeginLoc(Source),
480                                                            Source->getEndLoc()))
481             .getAsRange());
482     if (!DefRange) {
483       return llvm::createStringError(llvm::inconvertibleErrorCode(),
484                                      "Couldn't get range for the source.");
485     }
486     unsigned int SourceLen = SM.getFileOffset(DefRange->getEnd()) -
487                              SM.getFileOffset(DefRange->getBegin());
488     const tooling::Replacement DeleteFuncBody(SM, DefRange->getBegin(),
489                                               SourceLen, "");
490
491     llvm::SmallVector<std::pair<std::string, Edit>, 2> Edits;
492     // Edit for Target.
493     auto FE = Effect::fileEdit(SM, SM.getFileID(*Semicolon),
494                                std::move(TargetFileReplacements));
495     if (!FE)
496       return FE.takeError();
497     Edits.push_back(std::move(*FE));
498
499     // Edit for Source.
500     if (!SM.isWrittenInSameFile(DefRange->getBegin(),
501                                 SM.getExpansionLoc(Target->getBeginLoc()))) {
502       // Generate a new edit if the Source and Target are in different files.
503       auto FE = Effect::fileEdit(SM, SM.getFileID(Sel.Cursor),
504                                  tooling::Replacements(DeleteFuncBody));
505       if (!FE)
506         return FE.takeError();
507       Edits.push_back(std::move(*FE));
508     } else {
509       // Merge with previous edit if they are in the same file.
510       if (auto Err = Edits.front().second.Replacements.add(DeleteFuncBody))
511         return std::move(Err);
512     }
513
514     Effect E;
515     for (auto &Pair : Edits)
516       E.ApplyEdits.try_emplace(std::move(Pair.first), std::move(Pair.second));
517     return E;
518   }
519
520 private:
521   const FunctionDecl *Source = nullptr;
522   const FunctionDecl *Target = nullptr;
523 };
524
525 REGISTER_TWEAK(DefineInline)
526
527 } // namespace
528 } // namespace clangd
529 } // namespace clang