clang  6.0.0svn
ASTSelection.cpp
Go to the documentation of this file.
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 
12 #include "clang/Lex/Lexer.h"
13 #include "llvm/Support/SaveAndRestore.h"
14 
15 using namespace clang;
16 using namespace tooling;
18 
19 namespace {
20 
21 CharSourceRange getLexicalDeclRange(Decl *D, const SourceManager &SM,
22  const LangOptions &LangOpts) {
23  if (!isa<ObjCImplDecl>(D))
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();
29  R.getEnd(), tok::raw_identifier, SM, LangOpts,
30  /*SkipTrailingWhitespaceAndNewLine=*/false);
31  return LocAfterEnd.isValid()
32  ? CharSourceRange::getCharRange(R.getBegin(), LocAfterEnd)
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(
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))
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));
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));
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());
148  if (!SelectionEnd.isValid()) {
149  // Do a quick check when the selection is of length 0.
150  if (SM.isPointWithin(SelectionBegin, Range.getBegin(), End))
153  }
154  bool HasStart = SM.isPointWithin(SelectionBegin, Range.getBegin(), End);
155  bool HasEnd = SM.isPointWithin(SelectionEnd, Range.getBegin(), End);
156  if (HasStart && HasEnd)
158  if (SM.isPointWithin(Range.getBegin(), SelectionBegin, SelectionEnd) &&
159  SM.isPointWithin(End, SelectionBegin, SelectionEnd))
161  // Ensure there's at least some overlap with the 'start'/'end' selection
162  // types.
163  if (HasStart && SelectionBegin != End)
165  if (HasEnd && SelectionEnd != Range.getBegin())
167 
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 
185  SourceRange SelectionRange) {
186  assert(SelectionRange.isValid() &&
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 
202  switch (Kind) {
204  return "none";
206  return "contains-selection";
208  return "contains-selection-start";
210  return "contains-selection-end";
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.
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;
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.
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.
345  const SelectedASTNode &ASTSelection,
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 
375  const SelectedASTNode &ASTSelection,
379  findDeepestWithKind(ASTSelection, MatchingNodes, Kind, ParentStack);
380 }
381 
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;
389  findDeepestWithKind(ASTSelection, ContainSelection,
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 
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>()) {
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 
445  for (const auto &Parent : llvm::reverse(Parents)) {
446  const DynTypedNode &Node = Parent.get().Node;
447  if (const auto *D = Node.get<Decl>()) {
449  return D;
450  }
451  }
452  return nullptr;
453 }
Expr * getSyntacticForm()
Return the syntactic form of this expression, i.e.
Definition: Expr.h:5013
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:50
static void dump(const SelectedASTNode &Node, llvm::raw_ostream &OS, unsigned Indent=0)
Stmt - This represents one statement.
Definition: Stmt.h:66
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:86
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:149
virtual SourceRange getSourceRange() const LLVM_READONLY
Source range that this declaration covers.
Definition: DeclBase.h:404
Expr * getSourceExpr() const
The source expression of an opaque value expression is the expression which originally generated the ...
Definition: Expr.h:926
Keeps track of the various options that can be enabled, which controls the dialect of C or C++ that i...
Definition: LangOptions.h:48
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:51
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:595
A source range independent of the SourceManager.
Definition: Replacement.h:42
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:773
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:1266
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:1337
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:868
Kind
PseudoObjectExpr - An expression which accesses a pseudo-object l-value.
Definition: Expr.h:4969
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:487
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:52
SourceLocation getEnd() const
SourceManager & getSourceManager()
Definition: ASTContext.h:643
TranslationUnitDecl * getTranslationUnitDecl() const
Definition: ASTContext.h:989
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:265
std::vector< SelectedASTNode > Children
Definition: ASTSelection.h:53
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:688
This class handles loading and caching of source files into memory.
static const char * selectionKindToString(SourceSelectionKind Kind)