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