1 //===--- USRLocFinder.cpp - Clang refactoring library ---------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// \brief Methods for finding all instances of a USR. Our strategy is very
12 /// simple; we just compare the USR at every relevant AST node with the one
13 /// provided.
14 ///
15 //===----------------------------------------------------------------------===//
16 
17 #include "clang/Tooling/Refactoring/Rename/USRLocFinder.h"
18 #include "clang/AST/ASTContext.h"
19 #include "clang/AST/RecursiveASTVisitor.h"
20 #include "clang/Basic/LLVM.h"
21 #include "clang/Basic/SourceLocation.h"
22 #include "clang/Basic/SourceManager.h"
23 #include "clang/Lex/Lexer.h"
24 #include "clang/Tooling/Core/Lookup.h"
25 #include "clang/Tooling/Refactoring/RecursiveSymbolVisitor.h"
26 #include "clang/Tooling/Refactoring/Rename/SymbolName.h"
27 #include "clang/Tooling/Refactoring/Rename/USRFinder.h"
28 #include "llvm/ADT/StringRef.h"
29 #include "llvm/Support/Casting.h"
30 #include <cstddef>
31 #include <set>
32 #include <string>
33 #include <vector>
34 
35 using namespace llvm;
36 
37 namespace clang {
38 namespace tooling {
39 
40 namespace {
41 
42 // \brief This visitor recursively searches for all instances of a USR in a
43 // translation unit and stores them for later usage.
44 class USRLocFindingASTVisitor
45     : public RecursiveSymbolVisitor<USRLocFindingASTVisitor> {
46 public:
47   explicit USRLocFindingASTVisitor(const std::vector<std::string> &USRs,
48                                    StringRef PrevName,
49                                    const ASTContext &Context)
50       : RecursiveSymbolVisitor(Context.getSourceManager(),
51                                Context.getLangOpts()),
52         USRSet(USRs.begin(), USRs.end()), PrevName(PrevName), Context(Context) {
53   }
54 
55   bool visitSymbolOccurrence(const NamedDecl *ND,
56                              ArrayRef<SourceRange> NameRanges) {
57     if (USRSet.find(getUSRForDecl(ND)) != USRSet.end()) {
58       assert(NameRanges.size() == 1 &&
59              "Multiple name pieces are not supported yet!");
60       SourceLocation Loc = NameRanges[0].getBegin();
61       const SourceManager &SM = Context.getSourceManager();
62       // TODO: Deal with macro occurrences correctly.
63       if (Loc.isMacroID())
64         Loc = SM.getSpellingLoc(Loc);
65       checkAndAddLocation(Loc);
66     }
67     return true;
68   }
69 
70   // Non-visitors:
71 
72   /// \brief Returns a set of unique symbol occurrences. Duplicate or
73   /// overlapping occurrences are erroneous and should be reported!
74   SymbolOccurrences takeOccurrences() { return std::move(Occurrences); }
75 
76 private:
77   void checkAndAddLocation(SourceLocation Loc) {
78     const SourceLocation BeginLoc = Loc;
79     const SourceLocation EndLoc = Lexer::getLocForEndOfToken(
80         BeginLoc, 0, Context.getSourceManager(), Context.getLangOpts());
81     StringRef TokenName =
82         Lexer::getSourceText(CharSourceRange::getTokenRange(BeginLoc, EndLoc),
83                              Context.getSourceManager(), Context.getLangOpts());
84     size_t Offset = TokenName.find(PrevName.getNamePieces()[0]);
85 
86     // The token of the source location we find actually has the old
87     // name.
88     if (Offset != StringRef::npos)
89       Occurrences.emplace_back(PrevName, SymbolOccurrence::MatchingSymbol,
90                                BeginLoc.getLocWithOffset(Offset));
91   }
92 
93   const std::set<std::string> USRSet;
94   const SymbolName PrevName;
95   SymbolOccurrences Occurrences;
96   const ASTContext &Context;
97 };
98 
99 SourceLocation StartLocationForType(TypeLoc TL) {
100   // For elaborated types (e.g. `struct a::A`) we want the portion after the
101   // `struct` but including the namespace qualifier, `a::`.
102   if (auto ElaboratedTypeLoc = TL.getAs<clang::ElaboratedTypeLoc>()) {
103     NestedNameSpecifierLoc NestedNameSpecifier =
104         ElaboratedTypeLoc.getQualifierLoc();
105     if (NestedNameSpecifier.getNestedNameSpecifier())
106       return NestedNameSpecifier.getBeginLoc();
107     TL = TL.getNextTypeLoc();
108   }
109   return TL.getLocStart();
110 }
111 
112 SourceLocation EndLocationForType(TypeLoc TL) {
113   // Dig past any namespace or keyword qualifications.
114   while (TL.getTypeLocClass() == TypeLoc::Elaborated ||
115          TL.getTypeLocClass() == TypeLoc::Qualified)
116     TL = TL.getNextTypeLoc();
117 
118   // The location for template specializations (e.g. Foo<int>) includes the
119   // templated types in its location range.  We want to restrict this to just
120   // before the `<` character.
121   if (TL.getTypeLocClass() == TypeLoc::TemplateSpecialization) {
122     return TL.castAs<TemplateSpecializationTypeLoc>()
123         .getLAngleLoc()
124         .getLocWithOffset(-1);
125   }
126   return TL.getEndLoc();
127 }
128 
129 NestedNameSpecifier *GetNestedNameForType(TypeLoc TL) {
130   // Dig past any keyword qualifications.
131   while (TL.getTypeLocClass() == TypeLoc::Qualified)
132     TL = TL.getNextTypeLoc();
133 
134   // For elaborated types (e.g. `struct a::A`) we want the portion after the
135   // `struct` but including the namespace qualifier, `a::`.
136   if (auto ElaboratedTypeLoc = TL.getAs<clang::ElaboratedTypeLoc>())
137     return ElaboratedTypeLoc.getQualifierLoc().getNestedNameSpecifier();
138   return nullptr;
139 }
140 
141 // Find all locations identified by the given USRs for rename.
142 //
143 // This class will traverse the AST and find every AST node whose USR is in the
144 // given USRs' set.
145 class RenameLocFinder : public RecursiveASTVisitor<RenameLocFinder> {
146 public:
147   RenameLocFinder(llvm::ArrayRef<std::string> USRs, ASTContext &Context)
148       : USRSet(USRs.begin(), USRs.end()), Context(Context) {}
149 
150   // A structure records all information of a symbol reference being renamed.
151   // We try to add as few prefix qualifiers as possible.
152   struct RenameInfo {
153     // The begin location of a symbol being renamed.
154     SourceLocation Begin;
155     // The end location of a symbol being renamed.
156     SourceLocation End;
157     // The declaration of a symbol being renamed (can be nullptr).
158     const NamedDecl *FromDecl;
159     // The declaration in which the nested name is contained (can be nullptr).
160     const Decl *Context;
161     // The nested name being replaced (can be nullptr).
162     const NestedNameSpecifier *Specifier;
163     // Determine whether the prefix qualifiers of the NewName should be ignored.
164     // Normally, we set it to true for the symbol declaration and definition to
165     // avoid adding prefix qualifiers.
166     // For example, if it is true and NewName is "a::b::foo", then the symbol
167     // occurrence which the RenameInfo points to will be renamed to "foo".
168     bool IgnorePrefixQualifers;
169   };
170 
171   bool VisitNamedDecl(const NamedDecl *Decl) {
172     // UsingDecl has been handled in other place.
173     if (llvm::isa<UsingDecl>(Decl))
174       return true;
175 
176     // DestructorDecl has been handled in Typeloc.
177     if (llvm::isa<CXXDestructorDecl>(Decl))
178       return true;
179 
180     if (Decl->isImplicit())
181       return true;
182 
183     if (isInUSRSet(Decl)) {
184       RenameInfo Info = {Decl->getLocation(),
185                          Decl->getLocation(),
186                          /*FromDecl=*/nullptr,
187                          /*Context=*/nullptr,
188                          /*Specifier=*/nullptr,
189                          /*IgnorePrefixQualifers=*/true};
190       RenameInfos.push_back(Info);
191     }
192     return true;
193   }
194 
195   bool VisitDeclRefExpr(const DeclRefExpr *Expr) {
196     const NamedDecl *Decl = Expr->getFoundDecl();
197     // Get the underlying declaration of the shadow declaration introduced by a
198     // using declaration.
199     if (auto* UsingShadow = llvm::dyn_cast<UsingShadowDecl>(Decl)) {
200       Decl = UsingShadow->getTargetDecl();
201     }
202 
203     if (isInUSRSet(Decl)) {
204       RenameInfo Info = {Expr->getSourceRange().getBegin(),
205                          Expr->getSourceRange().getEnd(),
206                          Decl,
207                          getClosestAncestorDecl(*Expr),
208                          Expr->getQualifier(),
209                          /*IgnorePrefixQualifers=*/false};
210       RenameInfos.push_back(Info);
211     }
212 
213     return true;
214   }
215 
216   bool VisitUsingDecl(const UsingDecl *Using) {
217     for (const auto *UsingShadow : Using->shadows()) {
218       if (isInUSRSet(UsingShadow->getTargetDecl())) {
219         UsingDecls.push_back(Using);
220         break;
221       }
222     }
223     return true;
224   }
225 
226   bool VisitNestedNameSpecifierLocations(NestedNameSpecifierLoc NestedLoc) {
227     if (!NestedLoc.getNestedNameSpecifier()->getAsType())
228       return true;
229     if (IsTypeAliasWhichWillBeRenamedElsewhere(NestedLoc.getTypeLoc()))
230       return true;
231 
232     if (const auto *TargetDecl =
233             getSupportedDeclFromTypeLoc(NestedLoc.getTypeLoc())) {
234       if (isInUSRSet(TargetDecl)) {
235         RenameInfo Info = {NestedLoc.getBeginLoc(),
236                            EndLocationForType(NestedLoc.getTypeLoc()),
237                            TargetDecl,
238                            getClosestAncestorDecl(NestedLoc),
239                            NestedLoc.getNestedNameSpecifier()->getPrefix(),
240                            /*IgnorePrefixQualifers=*/false};
241         RenameInfos.push_back(Info);
242       }
243     }
244     return true;
245   }
246 
247   bool VisitTypeLoc(TypeLoc Loc) {
248     if (IsTypeAliasWhichWillBeRenamedElsewhere(Loc))
249       return true;
250 
251     auto Parents = Context.getParents(Loc);
252     TypeLoc ParentTypeLoc;
253     if (!Parents.empty()) {
254       // Handle cases of nested name specificier locations.
255       //
256       // The VisitNestedNameSpecifierLoc interface is not impelmented in
257       // RecursiveASTVisitor, we have to handle it explicitly.
258       if (const auto *NSL = Parents[0].get<NestedNameSpecifierLoc>()) {
259         VisitNestedNameSpecifierLocations(*NSL);
260         return true;
261       }
262 
263       if (const auto *TL = Parents[0].get<TypeLoc>())
264         ParentTypeLoc = *TL;
265     }
266 
267     // Handle the outermost TypeLoc which is directly linked to the interesting
268     // declaration and don't handle nested name specifier locations.
269     if (const auto *TargetDecl = getSupportedDeclFromTypeLoc(Loc)) {
270       if (isInUSRSet(TargetDecl)) {
271         // Only handle the outermost typeLoc.
272         //
273         // For a type like "a::Foo", there will be two typeLocs for it.
274         // One ElaboratedType, the other is RecordType:
275         //
276         //   ElaboratedType 0x33b9390 'a::Foo' sugar
277         //   `-RecordType 0x338fef0 'class a::Foo'
278         //     `-CXXRecord 0x338fe58 'Foo'
279         //
280         // Skip if this is an inner typeLoc.
281         if (!ParentTypeLoc.isNull() &&
282             isInUSRSet(getSupportedDeclFromTypeLoc(ParentTypeLoc)))
283           return true;
284         RenameInfo Info = {StartLocationForType(Loc),
285                            EndLocationForType(Loc),
286                            TargetDecl,
287                            getClosestAncestorDecl(Loc),
288                            GetNestedNameForType(Loc),
289                            /*IgnorePrefixQualifers=*/false};
290         RenameInfos.push_back(Info);
291         return true;
292       }
293     }
294 
295     // Handle specific template class specialiation cases.
296     if (const auto *TemplateSpecType =
297             dyn_cast<TemplateSpecializationType>(Loc.getType())) {
298       TypeLoc TargetLoc = Loc;
299       if (!ParentTypeLoc.isNull()) {
300         if (llvm::isa<ElaboratedType>(ParentTypeLoc.getType()))
301           TargetLoc = ParentTypeLoc;
302       }
303 
304       if (isInUSRSet(TemplateSpecType->getTemplateName().getAsTemplateDecl())) {
305         TypeLoc TargetLoc = Loc;
306         // FIXME: Find a better way to handle this case.
307         // For the qualified template class specification type like
308         // "ns::Foo<int>" in "ns::Foo<int>& f();", we want the parent typeLoc
309         // (ElaboratedType) of the TemplateSpecializationType in order to
310         // catch the prefix qualifiers "ns::".
311         if (!ParentTypeLoc.isNull() &&
312             llvm::isa<ElaboratedType>(ParentTypeLoc.getType()))
313           TargetLoc = ParentTypeLoc;
314         RenameInfo Info = {
315             StartLocationForType(TargetLoc),
316             EndLocationForType(TargetLoc),
317             TemplateSpecType->getTemplateName().getAsTemplateDecl(),
318             getClosestAncestorDecl(
319                 ast_type_traits::DynTypedNode::create(TargetLoc)),
320             GetNestedNameForType(TargetLoc),
321             /*IgnorePrefixQualifers=*/false};
322         RenameInfos.push_back(Info);
323       }
324     }
325     return true;
326   }
327 
328   // Returns a list of RenameInfo.
329   const std::vector<RenameInfo> &getRenameInfos() const { return RenameInfos; }
330 
331   // Returns a list of using declarations which are needed to update.
332   const std::vector<const UsingDecl *> &getUsingDecls() const {
333     return UsingDecls;
334   }
335 
336 private:
337   // FIXME: This method may not be suitable for renaming other types like alias
338   // types. Need to figure out a way to handle it.
339   bool IsTypeAliasWhichWillBeRenamedElsewhere(TypeLoc TL) const {
340     while (!TL.isNull()) {
341       // SubstTemplateTypeParm is the TypeLocation class for a substituted type
342       // inside a template expansion so we ignore these.  For example:
343       //
344       // template<typename T> struct S {
345       //   T t;  // <-- this T becomes a TypeLoc(int) with class
346       //         //     SubstTemplateTypeParm when S<int> is instantiated
347       // }
348       if (TL.getTypeLocClass() == TypeLoc::SubstTemplateTypeParm)
349         return true;
350 
351       // Typedef is the TypeLocation class for a type which is a typedef to the
352       // type we want to replace.  We ignore the use of the typedef as we will
353       // replace the definition of it.  For example:
354       //
355       // typedef int T;
356       // T a;  // <---  This T is a TypeLoc(int) with class Typedef.
357       if (TL.getTypeLocClass() == TypeLoc::Typedef)
358         return true;
359       TL = TL.getNextTypeLoc();
360     }
361     return false;
362   }
363 
364   // Get the supported declaration from a given typeLoc. If the declaration type
365   // is not supported, returns nullptr.
366   //
367   // FIXME: support more types, e.g. enum, type alias.
368   const NamedDecl *getSupportedDeclFromTypeLoc(TypeLoc Loc) {
369     if (const auto *RD = Loc.getType()->getAsCXXRecordDecl())
370       return RD;
371     return nullptr;
372   }
373 
374   // Get the closest ancester which is a declaration of a given AST node.
375   template <typename ASTNodeType>
376   const Decl *getClosestAncestorDecl(const ASTNodeType &Node) {
377     auto Parents = Context.getParents(Node);
378     // FIXME: figure out how to handle it when there are multiple parents.
379     if (Parents.size() != 1)
380       return nullptr;
381     if (ast_type_traits::ASTNodeKind::getFromNodeKind<Decl>().isBaseOf(
382             Parents[0].getNodeKind()))
383       return Parents[0].template get<Decl>();
384     return getClosestAncestorDecl(Parents[0]);
385   }
386 
387   // Get the parent typeLoc of a given typeLoc. If there is no such parent,
388   // return nullptr.
389   const TypeLoc *getParentTypeLoc(TypeLoc Loc) const {
390     auto Parents = Context.getParents(Loc);
391     // FIXME: figure out how to handle it when there are multiple parents.
392     if (Parents.size() != 1)
393       return nullptr;
394     return Parents[0].get<TypeLoc>();
395   }
396 
397   // Check whether the USR of a given Decl is in the USRSet.
398   bool isInUSRSet(const Decl *Decl) const {
399     auto USR = getUSRForDecl(Decl);
400     if (USR.empty())
401       return false;
402     return llvm::is_contained(USRSet, USR);
403   }
404 
405   const std::set<std::string> USRSet;
406   ASTContext &Context;
407   std::vector<RenameInfo> RenameInfos;
408   // Record all interested using declarations which contains the using-shadow
409   // declarations of the symbol declarations being renamed.
410   std::vector<const UsingDecl *> UsingDecls;
411 };
412 
413 } // namespace
414 
415 SymbolOccurrences getOccurrencesOfUSRs(ArrayRef<std::string> USRs,
416                                        StringRef PrevName, Decl *Decl) {
417   USRLocFindingASTVisitor Visitor(USRs, PrevName, Decl->getASTContext());
418   Visitor.TraverseDecl(Decl);
419   return Visitor.takeOccurrences();
420 }
421 
422 std::vector<tooling::AtomicChange>
423 createRenameAtomicChanges(llvm::ArrayRef<std::string> USRs,
424                           llvm::StringRef NewName, Decl *TranslationUnitDecl) {
425   RenameLocFinder Finder(USRs, TranslationUnitDecl->getASTContext());
426   Finder.TraverseDecl(TranslationUnitDecl);
427 
428   const SourceManager &SM =
429       TranslationUnitDecl->getASTContext().getSourceManager();
430 
431   std::vector<tooling::AtomicChange> AtomicChanges;
432   auto Replace = [&](SourceLocation Start, SourceLocation End,
433                      llvm::StringRef Text) {
434     tooling::AtomicChange ReplaceChange = tooling::AtomicChange(SM, Start);
435     llvm::Error Err = ReplaceChange.replace(
436         SM, CharSourceRange::getTokenRange(Start, End), Text);
437     if (Err) {
438       llvm::errs() << "Faile to add replacement to AtomicChange: "
439                    << llvm::toString(std::move(Err)) << "\n";
440       return;
441     }
442     AtomicChanges.push_back(std::move(ReplaceChange));
443   };
444 
445   for (const auto &RenameInfo : Finder.getRenameInfos()) {
446     std::string ReplacedName = NewName.str();
447     if (RenameInfo.IgnorePrefixQualifers) {
448       // Get the name without prefix qualifiers from NewName.
449       size_t LastColonPos = NewName.find_last_of(':');
450       if (LastColonPos != std::string::npos)
451         ReplacedName = NewName.substr(LastColonPos + 1);
452     } else {
453       if (RenameInfo.FromDecl && RenameInfo.Context) {
454         if (!llvm::isa<clang::TranslationUnitDecl>(
455                 RenameInfo.Context->getDeclContext())) {
456           ReplacedName = tooling::replaceNestedName(
457               RenameInfo.Specifier, RenameInfo.Context->getDeclContext(),
458               RenameInfo.FromDecl,
459               NewName.startswith("::") ? NewName.str()
460                                        : ("::" + NewName).str());
461         } else {
462           // This fixes the case where type `T` is a parameter inside a function
463           // type (e.g. `std::function<void(T)>`) and the DeclContext of `T`
464           // becomes the translation unit. As a workaround, we simply use
465           // fully-qualified name here for all references whose `DeclContext` is
466           // the translation unit and ignore the possible existence of
467           // using-decls (in the global scope) that can shorten the replaced
468           // name.
469           llvm::StringRef ActualName = Lexer::getSourceText(
470               CharSourceRange::getTokenRange(
471                   SourceRange(RenameInfo.Begin, RenameInfo.End)),
472               SM, TranslationUnitDecl->getASTContext().getLangOpts());
473           // Add the leading "::" back if the name written in the code contains
474           // it.
475           if (ActualName.startswith("::") && !NewName.startswith("::")) {
476             ReplacedName = "::" + NewName.str();
477           }
478         }
479       }
480       // If the NewName contains leading "::", add it back.
481       if (NewName.startswith("::") && NewName.substr(2) == ReplacedName)
482         ReplacedName = NewName.str();
483     }
484     Replace(RenameInfo.Begin, RenameInfo.End, ReplacedName);
485   }
486 
487   // Hanlde using declarations explicitly as "using a::Foo" don't trigger
488   // typeLoc for "a::Foo".
489   for (const auto *Using : Finder.getUsingDecls())
490     Replace(Using->getLocStart(), Using->getLocEnd(), "using " + NewName.str());
491 
492   return AtomicChanges;
493 }
494 
495 } // end namespace tooling
496 } // end namespace clang
497