1 //===--- ASTSelection.cpp - Clang refactoring library ---------------------===//
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 "clang/Tooling/Refactoring/ASTSelection.h"
10 #include "clang/AST/LexicallyOrderedRecursiveASTVisitor.h"
11 #include "clang/Lex/Lexer.h"
12 #include "llvm/Support/SaveAndRestore.h"
13 
14 using namespace clang;
15 using namespace tooling;
16 using ast_type_traits::DynTypedNode;
17 
18 namespace {
19 
20 CharSourceRange getLexicalDeclRange(Decl *D, const SourceManager &SM,
21                                     const LangOptions &LangOpts) {
22   if (!isa<ObjCImplDecl>(D))
23     return CharSourceRange::getTokenRange(D->getSourceRange());
24   // Objective-C implementation declarations end at the '@' instead of the 'end'
25   // keyword. Use the lexer to find the location right after 'end'.
26   SourceRange R = D->getSourceRange();
27   SourceLocation LocAfterEnd = Lexer::findLocationAfterToken(
28       R.getEnd(), tok::raw_identifier, SM, LangOpts,
29       /*SkipTrailingWhitespaceAndNewLine=*/false);
30   return LocAfterEnd.isValid()
31              ? CharSourceRange::getCharRange(R.getBegin(), LocAfterEnd)
32              : CharSourceRange::getTokenRange(R);
33 }
34 
35 /// Constructs the tree of selected AST nodes that either contain the location
36 /// of the cursor or overlap with the selection range.
37 class ASTSelectionFinder
38     : public LexicallyOrderedRecursiveASTVisitor<ASTSelectionFinder> {
39 public:
40   ASTSelectionFinder(SourceRange Selection, FileID TargetFile,
41                      const ASTContext &Context)
42       : LexicallyOrderedRecursiveASTVisitor(Context.getSourceManager()),
43         SelectionBegin(Selection.getBegin()),
44         SelectionEnd(Selection.getBegin() == Selection.getEnd()
45                          ? SourceLocation()
46                          : Selection.getEnd()),
47         TargetFile(TargetFile), Context(Context) {
48     // The TU decl is the root of the selected node tree.
49     SelectionStack.push_back(
50         SelectedASTNode(DynTypedNode::create(*Context.getTranslationUnitDecl()),
51                         SourceSelectionKind::None));
52   }
53 
54   Optional<SelectedASTNode> getSelectedASTNode() {
55     assert(SelectionStack.size() == 1 && "stack was not popped");
56     SelectedASTNode Result = std::move(SelectionStack.back());
57     SelectionStack.pop_back();
58     if (Result.Children.empty())
59       return None;
60     return std::move(Result);
61   }
62 
63   bool TraversePseudoObjectExpr(PseudoObjectExpr *E) {
64     // Avoid traversing the semantic expressions. They should be handled by
65     // looking through the appropriate opaque expressions in order to build
66     // a meaningful selection tree.
67     llvm::SaveAndRestore<bool> LookThrough(LookThroughOpaqueValueExprs, true);
68     return TraverseStmt(E->getSyntacticForm());
69   }
70 
71   bool TraverseOpaqueValueExpr(OpaqueValueExpr *E) {
72     if (!LookThroughOpaqueValueExprs)
73       return true;
74     llvm::SaveAndRestore<bool> LookThrough(LookThroughOpaqueValueExprs, false);
75     return TraverseStmt(E->getSourceExpr());
76   }
77 
78   bool TraverseDecl(Decl *D) {
79     if (isa<TranslationUnitDecl>(D))
80       return LexicallyOrderedRecursiveASTVisitor::TraverseDecl(D);
81     if (D->isImplicit())
82       return true;
83 
84     // Check if this declaration is written in the file of interest.
85     const SourceRange DeclRange = D->getSourceRange();
86     const SourceManager &SM = Context.getSourceManager();
87     SourceLocation FileLoc;
88     if (DeclRange.getBegin().isMacroID() && !DeclRange.getEnd().isMacroID())
89       FileLoc = DeclRange.getEnd();
90     else
91       FileLoc = SM.getSpellingLoc(DeclRange.getBegin());
92     if (SM.getFileID(FileLoc) != TargetFile)
93       return true;
94 
95     SourceSelectionKind SelectionKind =
96         selectionKindFor(getLexicalDeclRange(D, SM, Context.getLangOpts()));
97     SelectionStack.push_back(
98         SelectedASTNode(DynTypedNode::create(*D), SelectionKind));
99     LexicallyOrderedRecursiveASTVisitor::TraverseDecl(D);
100     popAndAddToSelectionIfSelected(SelectionKind);
101 
102     if (DeclRange.getEnd().isValid() &&
103         SM.isBeforeInTranslationUnit(SelectionEnd.isValid() ? SelectionEnd
104                                                             : SelectionBegin,
105                                      DeclRange.getEnd())) {
106       // Stop early when we've reached a declaration after the selection.
107       return false;
108     }
109     return true;
110   }
111 
112   bool TraverseStmt(Stmt *S) {
113     if (!S)
114       return true;
115     if (auto *Opaque = dyn_cast<OpaqueValueExpr>(S))
116       return TraverseOpaqueValueExpr(Opaque);
117     // Avoid selecting implicit 'this' expressions.
118     if (auto *TE = dyn_cast<CXXThisExpr>(S)) {
119       if (TE->isImplicit())
120         return true;
121     }
122     // FIXME (Alex Lorenz): Improve handling for macro locations.
123     SourceSelectionKind SelectionKind =
124         selectionKindFor(CharSourceRange::getTokenRange(S->getSourceRange()));
125     SelectionStack.push_back(
126         SelectedASTNode(DynTypedNode::create(*S), SelectionKind));
127     LexicallyOrderedRecursiveASTVisitor::TraverseStmt(S);
128     popAndAddToSelectionIfSelected(SelectionKind);
129     return true;
130   }
131 
132 private:
133   void popAndAddToSelectionIfSelected(SourceSelectionKind SelectionKind) {
134     SelectedASTNode Node = std::move(SelectionStack.back());
135     SelectionStack.pop_back();
136     if (SelectionKind != SourceSelectionKind::None || !Node.Children.empty())
137       SelectionStack.back().Children.push_back(std::move(Node));
138   }
139 
140   SourceSelectionKind selectionKindFor(CharSourceRange Range) {
141     SourceLocation End = Range.getEnd();
142     const SourceManager &SM = Context.getSourceManager();
143     if (Range.isTokenRange())
144       End = Lexer::getLocForEndOfToken(End, 0, SM, Context.getLangOpts());
145     if (!SourceLocation::isPairOfFileLocations(Range.getBegin(), End))
146       return SourceSelectionKind::None;
147     if (!SelectionEnd.isValid()) {
148       // Do a quick check when the selection is of length 0.
149       if (SM.isPointWithin(SelectionBegin, Range.getBegin(), End))
150         return SourceSelectionKind::ContainsSelection;
151       return SourceSelectionKind::None;
152     }
153     bool HasStart = SM.isPointWithin(SelectionBegin, Range.getBegin(), End);
154     bool HasEnd = SM.isPointWithin(SelectionEnd, Range.getBegin(), End);
155     if (HasStart && HasEnd)
156       return SourceSelectionKind::ContainsSelection;
157     if (SM.isPointWithin(Range.getBegin(), SelectionBegin, SelectionEnd) &&
158         SM.isPointWithin(End, SelectionBegin, SelectionEnd))
159       return SourceSelectionKind::InsideSelection;
160     // Ensure there's at least some overlap with the 'start'/'end' selection
161     // types.
162     if (HasStart && SelectionBegin != End)
163       return SourceSelectionKind::ContainsSelectionStart;
164     if (HasEnd && SelectionEnd != Range.getBegin())
165       return SourceSelectionKind::ContainsSelectionEnd;
166 
167     return SourceSelectionKind::None;
168   }
169 
170   const SourceLocation SelectionBegin, SelectionEnd;
171   FileID TargetFile;
172   const ASTContext &Context;
173   std::vector<SelectedASTNode> SelectionStack;
174   /// Controls whether we can traverse through the OpaqueValueExpr. This is
175   /// typically enabled during the traversal of syntactic form for
176   /// PseudoObjectExprs.
177   bool LookThroughOpaqueValueExprs = false;
178 };
179 
180 } // end anonymous namespace
181 
182 Optional<SelectedASTNode>
183 clang::tooling::findSelectedASTNodes(const ASTContext &Context,
184                                      SourceRange SelectionRange) {
185   assert(SelectionRange.isValid() &&
186          SourceLocation::isPairOfFileLocations(SelectionRange.getBegin(),
187                                                SelectionRange.getEnd()) &&
188          "Expected a file range");
189   FileID TargetFile =
190       Context.getSourceManager().getFileID(SelectionRange.getBegin());
191   assert(Context.getSourceManager().getFileID(SelectionRange.getEnd()) ==
192              TargetFile &&
193          "selection range must span one file");
194 
195   ASTSelectionFinder Visitor(SelectionRange, TargetFile, Context);
196   Visitor.TraverseDecl(Context.getTranslationUnitDecl());
197   return Visitor.getSelectedASTNode();
198 }
199 
200 static const char *selectionKindToString(SourceSelectionKind Kind) {
201   switch (Kind) {
202   case SourceSelectionKind::None:
203     return "none";
204   case SourceSelectionKind::ContainsSelection:
205     return "contains-selection";
206   case SourceSelectionKind::ContainsSelectionStart:
207     return "contains-selection-start";
208   case SourceSelectionKind::ContainsSelectionEnd:
209     return "contains-selection-end";
210   case SourceSelectionKind::InsideSelection:
211     return "inside";
212   }
213   llvm_unreachable("invalid selection kind");
214 }
215 
216 static void dump(const SelectedASTNode &Node, llvm::raw_ostream &OS,
217                  unsigned Indent = 0) {
218   OS.indent(Indent * 2);
219   if (const Decl *D = Node.Node.get<Decl>()) {
220     OS << D->getDeclKindName() << "Decl";
221     if (const auto *ND = dyn_cast<NamedDecl>(D))
222       OS << " \"" << ND->getNameAsString() << '"';
223   } else if (const Stmt *S = Node.Node.get<Stmt>()) {
224     OS << S->getStmtClassName();
225   }
226   OS << ' ' << selectionKindToString(Node.SelectionKind) << "\n";
227   for (const auto &Child : Node.Children)
228     dump(Child, OS, Indent + 1);
229 }
230 
231 void SelectedASTNode::dump(llvm::raw_ostream &OS) const { ::dump(*this, OS); }
232 
233 /// Returns true if the given node has any direct children with the following
234 /// selection kind.
235 ///
236 /// Note: The direct children also include children of direct children with the
237 /// "None" selection kind.
238 static bool hasAnyDirectChildrenWithKind(const SelectedASTNode &Node,
239                                          SourceSelectionKind Kind) {
240   assert(Kind != SourceSelectionKind::None && "invalid predicate!");
241   for (const auto &Child : Node.Children) {
242     if (Child.SelectionKind == Kind)
243       return true;
244     if (Child.SelectionKind == SourceSelectionKind::None)
245       return hasAnyDirectChildrenWithKind(Child, Kind);
246   }
247   return false;
248 }
249 
250 namespace {
251 struct SelectedNodeWithParents {
252   SelectedASTNode::ReferenceType Node;
253   llvm::SmallVector<SelectedASTNode::ReferenceType, 8> Parents;
254 
255   /// Canonicalizes the given selection by selecting different related AST nodes
256   /// when it makes sense to do so.
257   void canonicalize();
258 };
259 
260 enum SelectionCanonicalizationAction { KeepSelection, SelectParent };
261 
262 /// Returns the canonicalization action which should be applied to the
263 /// selected statement.
264 SelectionCanonicalizationAction
265 getSelectionCanonizalizationAction(const Stmt *S, const Stmt *Parent) {
266   // Select the parent expression when:
267   // - The string literal in ObjC string literal is selected, e.g.:
268   //     @"test"   becomes   @"test"
269   //      ~~~~~~             ~~~~~~~
270   if (isa<StringLiteral>(S) && isa<ObjCStringLiteral>(Parent))
271     return SelectParent;
272   // The entire call should be selected when just the member expression
273   // that refers to the method or the decl ref that refers to the function
274   // is selected.
275   //    f.call(args)  becomes  f.call(args)
276   //      ~~~~                 ~~~~~~~~~~~~
277   //    func(args)  becomes  func(args)
278   //    ~~~~                 ~~~~~~~~~~
279   else if (const auto *CE = dyn_cast<CallExpr>(Parent)) {
280     if ((isa<MemberExpr>(S) || isa<DeclRefExpr>(S)) &&
281         CE->getCallee()->IgnoreImpCasts() == S)
282       return SelectParent;
283   }
284   // FIXME: Syntactic form -> Entire pseudo-object expr.
285   return KeepSelection;
286 }
287 
288 } // end anonymous namespace
289 
290 void SelectedNodeWithParents::canonicalize() {
291   const Stmt *S = Node.get().Node.get<Stmt>();
292   assert(S && "non statement selection!");
293   const Stmt *Parent = Parents[Parents.size() - 1].get().Node.get<Stmt>();
294   if (!Parent)
295     return;
296 
297   // Look through the implicit casts in the parents.
298   unsigned ParentIndex = 1;
299   for (; (ParentIndex + 1) <= Parents.size() && isa<ImplicitCastExpr>(Parent);
300        ++ParentIndex) {
301     const Stmt *NewParent =
302         Parents[Parents.size() - ParentIndex - 1].get().Node.get<Stmt>();
303     if (!NewParent)
304       break;
305     Parent = NewParent;
306   }
307 
308   switch (getSelectionCanonizalizationAction(S, Parent)) {
309   case SelectParent:
310     Node = Parents[Parents.size() - ParentIndex];
311     for (; ParentIndex != 0; --ParentIndex)
312       Parents.pop_back();
313     break;
314   case KeepSelection:
315     break;
316   }
317 }
318 
319 /// Finds the set of bottom-most selected AST nodes that are in the selection
320 /// tree with the specified selection kind.
321 ///
322 /// For example, given the following selection tree:
323 ///
324 /// FunctionDecl "f" contains-selection
325 ///   CompoundStmt contains-selection [#1]
326 ///     CallExpr inside
327 ///     ImplicitCastExpr inside
328 ///       DeclRefExpr inside
329 ///     IntegerLiteral inside
330 ///     IntegerLiteral inside
331 /// FunctionDecl "f2" contains-selection
332 ///   CompoundStmt contains-selection [#2]
333 ///     CallExpr inside
334 ///     ImplicitCastExpr inside
335 ///       DeclRefExpr inside
336 ///     IntegerLiteral inside
337 ///     IntegerLiteral inside
338 ///
339 /// This function will find references to nodes #1 and #2 when searching for the
340 /// \c ContainsSelection kind.
341 static void findDeepestWithKind(
342     const SelectedASTNode &ASTSelection,
343     llvm::SmallVectorImpl<SelectedNodeWithParents> &MatchingNodes,
344     SourceSelectionKind Kind,
345     llvm::SmallVectorImpl<SelectedASTNode::ReferenceType> &ParentStack) {
346   if (ASTSelection.Node.get<DeclStmt>()) {
347     // Select the entire decl stmt when any of its child declarations is the
348     // bottom-most.
349     for (const auto &Child : ASTSelection.Children) {
350       if (!hasAnyDirectChildrenWithKind(Child, Kind)) {
351         MatchingNodes.push_back(SelectedNodeWithParents{
352             std::cref(ASTSelection), {ParentStack.begin(), ParentStack.end()}});
353         return;
354       }
355     }
356   } else {
357     if (!hasAnyDirectChildrenWithKind(ASTSelection, Kind)) {
358       // This node is the bottom-most.
359       MatchingNodes.push_back(SelectedNodeWithParents{
360           std::cref(ASTSelection), {ParentStack.begin(), ParentStack.end()}});
361       return;
362     }
363   }
364   // Search in the children.
365   ParentStack.push_back(std::cref(ASTSelection));
366   for (const auto &Child : ASTSelection.Children)
367     findDeepestWithKind(Child, MatchingNodes, Kind, ParentStack);
368   ParentStack.pop_back();
369 }
370 
371 static void findDeepestWithKind(
372     const SelectedASTNode &ASTSelection,
373     llvm::SmallVectorImpl<SelectedNodeWithParents> &MatchingNodes,
374     SourceSelectionKind Kind) {
375   llvm::SmallVector<SelectedASTNode::ReferenceType, 16> ParentStack;
376   findDeepestWithKind(ASTSelection, MatchingNodes, Kind, ParentStack);
377 }
378 
379 Optional<CodeRangeASTSelection>
380 CodeRangeASTSelection::create(SourceRange SelectionRange,
381                               const SelectedASTNode &ASTSelection) {
382   // Code range is selected when the selection range is not empty.
383   if (SelectionRange.getBegin() == SelectionRange.getEnd())
384     return None;
385   llvm::SmallVector<SelectedNodeWithParents, 4> ContainSelection;
386   findDeepestWithKind(ASTSelection, ContainSelection,
387                       SourceSelectionKind::ContainsSelection);
388   // We are looking for a selection in one body of code, so let's focus on
389   // one matching result.
390   if (ContainSelection.size() != 1)
391     return None;
392   SelectedNodeWithParents &Selected = ContainSelection[0];
393   if (!Selected.Node.get().Node.get<Stmt>())
394     return None;
395   const Stmt *CodeRangeStmt = Selected.Node.get().Node.get<Stmt>();
396   if (!isa<CompoundStmt>(CodeRangeStmt)) {
397     Selected.canonicalize();
398     return CodeRangeASTSelection(Selected.Node, Selected.Parents,
399                                  /*AreChildrenSelected=*/false);
400   }
401   // FIXME (Alex L): First selected SwitchCase means that first case statement.
402   // is selected actually
403   // (See https://github.com/apple/swift-clang & CompoundStmtRange).
404 
405   // FIXME (Alex L): Tweak selection rules for compound statements, see:
406   // https://github.com/apple/swift-clang/blob/swift-4.1-branch/lib/Tooling/
407   // Refactor/ASTSlice.cpp#L513
408   // The user selected multiple statements in a compound statement.
409   Selected.Parents.push_back(Selected.Node);
410   return CodeRangeASTSelection(Selected.Node, Selected.Parents,
411                                /*AreChildrenSelected=*/true);
412 }
413 
414 static bool isFunctionLikeDeclaration(const Decl *D) {
415   // FIXME (Alex L): Test for BlockDecl.
416   return isa<FunctionDecl>(D) || isa<ObjCMethodDecl>(D);
417 }
418 
419 bool CodeRangeASTSelection::isInFunctionLikeBodyOfCode() const {
420   bool IsPrevCompound = false;
421   // Scan through the parents (bottom-to-top) and check if the selection is
422   // contained in a compound statement that's a body of a function/method
423   // declaration.
424   for (const auto &Parent : llvm::reverse(Parents)) {
425     const DynTypedNode &Node = Parent.get().Node;
426     if (const auto *D = Node.get<Decl>()) {
427       if (isFunctionLikeDeclaration(D))
428         return IsPrevCompound;
429       // Stop the search at any type declaration to avoid returning true for
430       // expressions in type declarations in functions, like:
431       // function foo() { struct X {
432       //   int m = /*selection:*/ 1 + 2 /*selection end*/; }; };
433       if (isa<TypeDecl>(D))
434         return false;
435     }
436     IsPrevCompound = Node.get<CompoundStmt>() != nullptr;
437   }
438   return false;
439 }
440 
441 const Decl *CodeRangeASTSelection::getFunctionLikeNearestParent() const {
442   for (const auto &Parent : llvm::reverse(Parents)) {
443     const DynTypedNode &Node = Parent.get().Node;
444     if (const auto *D = Node.get<Decl>()) {
445       if (isFunctionLikeDeclaration(D))
446         return D;
447     }
448   }
449   return nullptr;
450 }
451