clang  9.0.0svn
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;
17 
18 namespace {
19 
20 CharSourceRange getLexicalDeclRange(Decl *D, const SourceManager &SM,
21  const LangOptions &LangOpts) {
22  if (!isa<ObjCImplDecl>(D))
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();
28  R.getEnd(), tok::raw_identifier, SM, LangOpts,
29  /*SkipTrailingWhitespaceAndNewLine=*/false);
30  return LocAfterEnd.isValid()
31  ? CharSourceRange::getCharRange(R.getBegin(), LocAfterEnd)
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(
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))
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));
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));
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());
147  if (!SelectionEnd.isValid()) {
148  // Do a quick check when the selection is of length 0.
149  if (SM.isPointWithin(SelectionBegin, Range.getBegin(), End))
152  }
153  bool HasStart = SM.isPointWithin(SelectionBegin, Range.getBegin(), End);
154  bool HasEnd = SM.isPointWithin(SelectionEnd, Range.getBegin(), End);
155  if (HasStart && HasEnd)
157  if (SM.isPointWithin(Range.getBegin(), SelectionBegin, SelectionEnd) &&
158  SM.isPointWithin(End, SelectionBegin, SelectionEnd))
160  // Ensure there's at least some overlap with the 'start'/'end' selection
161  // types.
162  if (HasStart && SelectionBegin != End)
164  if (HasEnd && SelectionEnd != Range.getBegin())
166 
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 
184  SourceRange SelectionRange) {
185  assert(SelectionRange.isValid() &&
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 
201  switch (Kind) {
203  return "none";
205  return "contains-selection";
207  return "contains-selection-start";
209  return "contains-selection-end";
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.
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 {
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.
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.
342  const SelectedASTNode &ASTSelection,
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 
372  const SelectedASTNode &ASTSelection,
376  findDeepestWithKind(ASTSelection, MatchingNodes, Kind, ParentStack);
377 }
378 
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;
386  findDeepestWithKind(ASTSelection, ContainSelection,
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 
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>()) {
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 
442  for (const auto &Parent : llvm::reverse(Parents)) {
443  const DynTypedNode &Node = Parent.get().Node;
444  if (const auto *D = Node.get<Decl>()) {
446  return D;
447  }
448  }
449  return nullptr;
450 }
Expr * getSyntacticForm()
Return the syntactic form of this expression, i.e.
Definition: Expr.h:5627
const char * getDeclKindName() const
Definition: DeclBase.cpp:122
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:49
static void dump(const SelectedASTNode &Node, llvm::raw_ostream &OS, unsigned Indent=0)
Stmt - This represents one statement.
Definition: Stmt.h:65
static CharSourceRange getTokenRange(SourceRange R)
const T * get() const
Retrieve the stored node as type T.
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:88
bool isBeforeInTranslationUnit(SourceLocation LHS, SourceLocation RHS) const
Determines the order of 2 source locations in the translation unit.
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:74
SourceLocation getBegin() const
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:154
virtual SourceRange getSourceRange() const LLVM_READONLY
Source range that this declaration covers.
Definition: DeclBase.h:410
Expr * getSourceExpr() const
The source expression of an opaque value expression is the expression which originally generated the ...
Definition: Expr.h:1036
Keeps track of the various options that can be enabled, which controls the dialect of C or C++ that i...
Definition: LangOptions.h:49
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.
ast_type_traits::DynTypedNode Node
Definition: ASTSelection.h:50
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:191
CompoundStmt - This represents a group of statements like { stmt stmt }.
Definition: Stmt.h:1277
A source range independent of the SourceManager.
Definition: Replacement.h:44
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:770
SourceLocation End
Represents a character-granular source range.
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:1262
bool isImplicit() const
isImplicit - Indicates whether the declaration was implicitly generated by the implementation.
Definition: DeclBase.h:551
SourceLocation getEnd() const
const SourceManager & SM
Definition: Format.cpp:1568
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:978
Kind
PseudoObjectExpr - An expression which accesses a pseudo-object l-value.
Definition: Expr.h:5583
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:94
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
Definition: Stmt.h:1170
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...
bool isTokenRange() const
Return true if the end of this range specifies the start of the last token.
ast_type_traits::DynTypedNode DynTypedNode
ast_type_traits::DynTypedNode Node
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...
std::unique_ptr< DiagnosticConsumer > create(StringRef OutputFile, DiagnosticOptions *Diags, bool MergeChildRecords=false)
Returns a DiagnosticConsumer that serializes diagnostics to a bitcode file.
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
A dynamically typed AST node container.
FileID getFileID(SourceLocation SpellingLoc) const
Return the FileID for a SourceLocation.
static Optional< CodeRangeASTSelection > create(SourceRange SelectionRange, const SelectedASTNode &ASTSelection)
SourceSelectionKind SelectionKind
Definition: ASTSelection.h:51
SourceLocation getEnd() const
SourceManager & getSourceManager()
Definition: ASTContext.h:662
TranslationUnitDecl * getTranslationUnitDecl() const
Definition: ASTContext.h:1004
bool isValid() const
std::reference_wrapper< const SelectedASTNode > ReferenceType
Definition: ASTSelection.h:62
SourceRange getSourceRange() const LLVM_READONLY
SourceLocation tokens are not useful in isolation - they are low level value objects created/interpre...
Definition: Stmt.cpp:251
std::vector< SelectedASTNode > Children
Definition: ASTSelection.h:52
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.
SourceLocation getBegin() const
const LangOptions & getLangOpts() const
Definition: ASTContext.h:707
This class handles loading and caching of source files into memory.
static const char * selectionKindToString(SourceSelectionKind Kind)