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"
Private()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
533