clang  12.0.0git
ASTSelection.cpp
Go to the documentation of this file.
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 
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))
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();
27  R.getEnd(), tok::raw_identifier, SM, LangOpts,
28  /*SkipTrailingWhitespaceAndNewLine=*/false);
29  return LocAfterEnd.isValid()
30  ? CharSourceRange::getCharRange(R.getBegin(), LocAfterEnd)
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()),
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))
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));
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));
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());
146  if (!SelectionEnd.isValid()) {
147  // Do a quick check when the selection is of length 0.
148  if (SM.isPointWithin(SelectionBegin, Range.getBegin(), End))
151  }
152  bool HasStart = SM.isPointWithin(SelectionBegin, Range.getBegin(), End);
153  bool HasEnd = SM.isPointWithin(SelectionEnd, Range.getBegin(), End);
154  if (HasStart && HasEnd)
156  if (SM.isPointWithin(Range.getBegin(), SelectionBegin, SelectionEnd) &&
157  SM.isPointWithin(End, SelectionBegin, SelectionEnd))
159  // Ensure there's at least some overlap with the 'start'/'end' selection
160  // types.
161  if (HasStart && SelectionBegin != End)
163  if (HasEnd && SelectionEnd != Range.getBegin())
165 
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 
183  SourceRange SelectionRange) {
184  assert(SelectionRange.isValid() &&
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 
200  switch (Kind) {
202  return "none";
204  return "contains-selection";
206  return "contains-selection-start";
208  return "contains-selection-end";
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->getNameAsString() << '"';
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,
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 {
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.
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.
341  const SelectedASTNode &ASTSelection,
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 
371  const SelectedASTNode &ASTSelection,
375  findDeepestWithKind(ASTSelection, MatchingNodes, Kind, ParentStack);
376 }
377 
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;
385  findDeepestWithKind(ASTSelection, ContainSelection,
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 
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>()) {
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 
441  for (const auto &Parent : llvm::reverse(Parents)) {
442  const DynTypedNode &Node = Parent.get().Node;
443  if (const auto *D = Node.get<Decl>()) {
445  return D;
446  }
447  }
448  return nullptr;
449 }
Expr * getSyntacticForm()
Return the syntactic form of this expression, i.e.
Definition: Expr.h:5970
const char * getDeclKindName() const
Definition: DeclBase.cpp:123
static void findDeepestWithKind(const SelectedASTNode &ASTSelection, llvm::SmallVectorImpl< SelectedNodeWithParents > &MatchingNodes, SourceSelectionKind Kind, llvm::SmallVectorImpl< SelectedASTNode::ReferenceType > &ParentStack)
Finds the set of bottom-most selected AST nodes that are in the selection tree with the specified sel...
Represents a selected AST node.
Definition: ASTSelection.h:51
static void dump(const SelectedASTNode &Node, llvm::raw_ostream &OS, unsigned Indent=0)
Stmt - This represents one statement.
Definition: Stmt.h:68
static CharSourceRange getTokenRange(SourceRange R)
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:89
bool isBeforeInTranslationUnit(SourceLocation LHS, SourceLocation RHS) const
Determines the order of 2 source locations in the translation unit.
static DynTypedNode create(const T &Node)
Creates a DynTypedNode from Node.
bool TraverseDecl(Decl *D)
Recursively visit a declaration, by dispatching to Traverse*Decl() based on the argument&#39;s dynamic ty...
const char * getStmtClassName() const
Definition: Stmt.cpp:76
SourceLocation getBegin() const
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:174
virtual SourceRange getSourceRange() const LLVM_READONLY
Source range that this declaration covers.
Definition: DeclBase.h:418
Expr * getSourceExpr() const
The source expression of an opaque value expression is the expression which originally generated the ...
Definition: Expr.h:1152
Keeps track of the various options that can be enabled, which controls the dialect of C or C++ that i...
Definition: LangOptions.h:54
A node that&#39;s considered to be selected because the whole selection range is inside of its source ran...
Optional< SelectedASTNode > findSelectedASTNodes(const ASTContext &Context, SourceRange SelectionRange)
Traverses the given ASTContext and creates a tree of selected AST nodes.
SourceLocation getSpellingLoc(SourceLocation Loc) const
Given a SourceLocation object, return the spelling location referenced by the ID. ...
void dump(llvm::raw_ostream &OS=llvm::errs()) const
NodeId Parent
Definition: ASTDiff.cpp:192
CompoundStmt - This represents a group of statements like { stmt stmt }.
Definition: Stmt.h:1364
const Decl * getFunctionLikeNearestParent() const
Returns the nearest function-like parent declaration or null if such declaration doesn&#39;t exist...
static SourceLocation getLocForEndOfToken(SourceLocation Loc, unsigned Offset, const SourceManager &SM, const LangOptions &LangOpts)
Computes the source location just past the end of the token at this source location.
Definition: Lexer.cpp:779
SourceLocation End
Represents a character-granular source range.
DynTypedNode Node
static SourceLocation findLocationAfterToken(SourceLocation loc, tok::TokenKind TKind, const SourceManager &SM, const LangOptions &LangOpts, bool SkipTrailingWhitespaceAndNewLine)
Checks that the given token is the first token that occurs after the given location (this excludes co...
Definition: Lexer.cpp:1271
bool isImplicit() const
isImplicit - Indicates whether the declaration was implicitly generated by the implementation.
Definition: DeclBase.h:563
SourceLocation getEnd() const
#define SM(sm)
Definition: Cuda.cpp:62
static CharSourceRange getCharRange(SourceRange R)
static bool hasAnyDirectChildrenWithKind(const SelectedASTNode &Node, SourceSelectionKind Kind)
Returns true if the given node has any direct children with the following selection kind...
OpaqueValueExpr - An expression referring to an opaque object of a fixed type and value class...
Definition: Expr.h:1102
Kind
PseudoObjectExpr - An expression which accesses a pseudo-object l-value.
Definition: Expr.h:5926
Encodes a location in the source.
An AST selection value that corresponds to a selection of a set of statements that belong to one body...
Definition: ASTSelection.h:95
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
Definition: Stmt.h:1257
A node that&#39;s considered to be selected because the start of the selection range is inside its source...
bool TraverseStmt(Stmt *S, DataRecursionQueue *Queue=nullptr)
Recursively visit a statement or expression, by dispatching to Traverse*() based on the argument&#39;s dy...
A node that&#39;s considered to be selected because the node is entirely in the selection range...
A RecursiveASTVisitor subclass that guarantees that AST traversal is performed in a lexical order (i...
A dynamically typed AST node container.
bool isTokenRange() const
Return true if the end of this range specifies the start of the last token.
An opaque identifier used by SourceManager which refers to a source file (MemoryBuffer) along with it...
Dataflow Directional Tag Classes.
static bool isPairOfFileLocations(SourceLocation Start, SourceLocation End)
bool isValid() const
Return true if this is a valid SourceLocation object.
A node that&#39;s considered to be selected because the end of the selection range is inside its source r...
static bool isFunctionLikeDeclaration(const Decl *D)
bool isInFunctionLikeBodyOfCode() const
Returns true when a selected code range is in a function-like body of code, like a function...
bool isMacroID() const
FileID getFileID(SourceLocation SpellingLoc) const
Return the FileID for a SourceLocation.
static Optional< CodeRangeASTSelection > create(SourceRange SelectionRange, const SelectedASTNode &ASTSelection)
SourceLocation getEnd() const
SourceManager & getSourceManager()
Definition: ASTContext.h:619
TranslationUnitDecl * getTranslationUnitDecl() const
Definition: ASTContext.h:935
bool isValid() const
std::reference_wrapper< const SelectedASTNode > ReferenceType
Definition: ASTSelection.h:63
SourceRange getSourceRange() const LLVM_READONLY
SourceLocation tokens are not useful in isolation - they are low level value objects created/interpre...
Definition: Stmt.cpp:263
raw_ostream & Indent(raw_ostream &Out, const unsigned int Space, bool IsDot)
Definition: JsonSupport.h:20
bool isPointWithin(SourceLocation Location, SourceLocation Start, SourceLocation End) const
Return true if the Point is within Start and End.
SelectionCanonicalizationAction
A node that&#39;s not selected.
A trivial tuple used to represent a source range.
const T * get() const
Retrieve the stored node as type T.
SourceLocation getBegin() const
const LangOptions & getLangOpts() const
Definition: ASTContext.h:664
This class handles loading and caching of source files into memory.
static const char * selectionKindToString(SourceSelectionKind Kind)