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  // FIXME (Alex Lorenz): Improve handling for macro locations.
119  SourceSelectionKind SelectionKind =
120  selectionKindFor(CharSourceRange::getTokenRange(S->getSourceRange()));
121  SelectionStack.push_back(
122  SelectedASTNode(DynTypedNode::create(*S), SelectionKind));
124  popAndAddToSelectionIfSelected(SelectionKind);
125  return true;
126  }
127 
128 private:
129  void popAndAddToSelectionIfSelected(SourceSelectionKind SelectionKind) {
130  SelectedASTNode Node = std::move(SelectionStack.back());
131  SelectionStack.pop_back();
132  if (SelectionKind != SourceSelectionKind::None || !Node.Children.empty())
133  SelectionStack.back().Children.push_back(std::move(Node));
134  }
135 
136  SourceSelectionKind selectionKindFor(CharSourceRange Range) {
137  SourceLocation End = Range.getEnd();
138  const SourceManager &SM = Context.getSourceManager();
139  if (Range.isTokenRange())
140  End = Lexer::getLocForEndOfToken(End, 0, SM, Context.getLangOpts());
143  if (!SelectionEnd.isValid()) {
144  // Do a quick check when the selection is of length 0.
145  if (SM.isPointWithin(SelectionBegin, Range.getBegin(), End))
148  }
149  bool HasStart = SM.isPointWithin(SelectionBegin, Range.getBegin(), End);
150  bool HasEnd = SM.isPointWithin(SelectionEnd, Range.getBegin(), End);
151  if (HasStart && HasEnd)
153  if (SM.isPointWithin(Range.getBegin(), SelectionBegin, SelectionEnd) &&
154  SM.isPointWithin(End, SelectionBegin, SelectionEnd))
156  // Ensure there's at least some overlap with the 'start'/'end' selection
157  // types.
158  if (HasStart && SelectionBegin != End)
160  if (HasEnd && SelectionEnd != Range.getBegin())
162 
164  }
165 
166  const SourceLocation SelectionBegin, SelectionEnd;
167  FileID TargetFile;
168  const ASTContext &Context;
169  std::vector<SelectedASTNode> SelectionStack;
170  /// Controls whether we can traverse through the OpaqueValueExpr. This is
171  /// typically enabled during the traversal of syntactic form for
172  /// PseudoObjectExprs.
173  bool LookThroughOpaqueValueExprs = false;
174 };
175 
176 } // end anonymous namespace
177 
180  SourceRange SelectionRange) {
181  assert(SelectionRange.isValid() &&
183  SelectionRange.getEnd()) &&
184  "Expected a file range");
185  FileID TargetFile =
186  Context.getSourceManager().getFileID(SelectionRange.getBegin());
187  assert(Context.getSourceManager().getFileID(SelectionRange.getEnd()) ==
188  TargetFile &&
189  "selection range must span one file");
190 
191  ASTSelectionFinder Visitor(SelectionRange, TargetFile, Context);
192  Visitor.TraverseDecl(Context.getTranslationUnitDecl());
193  return Visitor.getSelectedASTNode();
194 }
195 
197  switch (Kind) {
199  return "none";
201  return "contains-selection";
203  return "contains-selection-start";
205  return "contains-selection-end";
207  return "inside";
208  }
209  llvm_unreachable("invalid selection kind");
210 }
211 
212 static void dump(const SelectedASTNode &Node, llvm::raw_ostream &OS,
213  unsigned Indent = 0) {
214  OS.indent(Indent * 2);
215  if (const Decl *D = Node.Node.get<Decl>()) {
216  OS << D->getDeclKindName() << "Decl";
217  if (const auto *ND = dyn_cast<NamedDecl>(D))
218  OS << " \"" << ND->getNameAsString() << '"';
219  } else if (const Stmt *S = Node.Node.get<Stmt>()) {
220  OS << S->getStmtClassName();
221  }
222  OS << ' ' << selectionKindToString(Node.SelectionKind) << "\n";
223  for (const auto &Child : Node.Children)
224  dump(Child, OS, Indent + 1);
225 }
226 
227 void SelectedASTNode::dump(llvm::raw_ostream &OS) const { ::dump(*this, OS); }
228 
229 /// Returns true if the given node has any direct children with the following
230 /// selection kind.
231 ///
232 /// Note: The direct children also include children of direct children with the
233 /// "None" selection kind.
236  assert(Kind != SourceSelectionKind::None && "invalid predicate!");
237  for (const auto &Child : Node.Children) {
238  if (Child.SelectionKind == Kind)
239  return true;
240  if (Child.SelectionKind == SourceSelectionKind::None)
241  return hasAnyDirectChildrenWithKind(Child, Kind);
242  }
243  return false;
244 }
245 
246 namespace {
247 struct SelectedNodeWithParents {
248  SelectedNodeWithParents(SelectedNodeWithParents &&) = default;
249  SelectedNodeWithParents &operator=(SelectedNodeWithParents &&) = default;
252 };
253 } // end anonymous namespace
254 
255 /// Finds the set of bottom-most selected AST nodes that are in the selection
256 /// tree with the specified selection kind.
257 ///
258 /// For example, given the following selection tree:
259 ///
260 /// FunctionDecl "f" contains-selection
261 /// CompoundStmt contains-selection [#1]
262 /// CallExpr inside
263 /// ImplicitCastExpr inside
264 /// DeclRefExpr inside
265 /// IntegerLiteral inside
266 /// IntegerLiteral inside
267 /// FunctionDecl "f2" contains-selection
268 /// CompoundStmt contains-selection [#2]
269 /// CallExpr inside
270 /// ImplicitCastExpr inside
271 /// DeclRefExpr inside
272 /// IntegerLiteral inside
273 /// IntegerLiteral inside
274 ///
275 /// This function will find references to nodes #1 and #2 when searching for the
276 /// \c ContainsSelection kind.
278  const SelectedASTNode &ASTSelection,
282  if (!hasAnyDirectChildrenWithKind(ASTSelection, Kind)) {
283  // This node is the bottom-most.
284  MatchingNodes.push_back(SelectedNodeWithParents{
285  std::cref(ASTSelection), {ParentStack.begin(), ParentStack.end()}});
286  return;
287  }
288  // Search in the children.
289  ParentStack.push_back(std::cref(ASTSelection));
290  for (const auto &Child : ASTSelection.Children)
291  findDeepestWithKind(Child, MatchingNodes, Kind, ParentStack);
292  ParentStack.pop_back();
293 }
294 
296  const SelectedASTNode &ASTSelection,
300  findDeepestWithKind(ASTSelection, MatchingNodes, Kind, ParentStack);
301 }
302 
305  const SelectedASTNode &ASTSelection) {
306  // Code range is selected when the selection range is not empty.
307  if (SelectionRange.getBegin() == SelectionRange.getEnd())
308  return None;
310  findDeepestWithKind(ASTSelection, ContainSelection,
312  // We are looking for a selection in one body of code, so let's focus on
313  // one matching result.
314  if (ContainSelection.size() != 1)
315  return None;
316  SelectedNodeWithParents &Selected = ContainSelection[0];
317  if (!Selected.Node.get().Node.get<Stmt>())
318  return None;
319  const Stmt *CodeRangeStmt = Selected.Node.get().Node.get<Stmt>();
320  if (!isa<CompoundStmt>(CodeRangeStmt)) {
321  // FIXME (Alex L): Canonicalize.
322  return CodeRangeASTSelection(Selected.Node, Selected.Parents,
323  /*AreChildrenSelected=*/false);
324  }
325  // FIXME (Alex L): Tweak selection rules for compound statements, see:
326  // https://github.com/apple/swift-clang/blob/swift-4.1-branch/lib/Tooling/
327  // Refactor/ASTSlice.cpp#L513
328  // The user selected multiple statements in a compound statement.
329  Selected.Parents.push_back(Selected.Node);
330  return CodeRangeASTSelection(Selected.Node, Selected.Parents,
331  /*AreChildrenSelected=*/true);
332 }
Expr * getSyntacticForm()
Return the syntactic form of this expression, i.e.
Definition: Expr.h:5014
const char * getDeclKindName() const
Definition: DeclBase.cpp:103
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:60
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:81
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:58
SourceLocation getBegin() const
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:128
virtual SourceRange getSourceRange() const LLVM_READONLY
Source range that this declaration covers.
Definition: DeclBase.h:397
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
A source range independent of the SourceManager.
Definition: Replacement.h:42
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:755
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:1219
bool isImplicit() const
isImplicit - Indicates whether the declaration was implicitly generated by the implementation.
Definition: DeclBase.h:537
SourceLocation getEnd() const
const SourceManager & SM
Definition: Format.cpp:1308
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:4970
Encodes a location in the source.
std::string getNameAsString() const
getNameAsString - Get a human-readable name for the declaration, even if it is one of the special kin...
Definition: Decl.h:252
An AST selection value that corresponds to a selection of a set of statements that belong to one body...
Definition: ASTSelection.h:95
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.
bool isMacroID() const
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:618
TranslationUnitDecl * getTranslationUnitDecl() const
Definition: ASTContext.h:958
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:245
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.
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:661
This class handles loading and caching of source files into memory.
static const char * selectionKindToString(SourceSelectionKind Kind)