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