clang 17.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#include <optional>
14
15using namespace clang;
16using namespace tooling;
17
18namespace {
19
20CharSourceRange 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'.
28 R.getEnd(), tok::raw_identifier, SM, LangOpts,
29 /*SkipTrailingWhitespaceAndNewLine=*/false);
30 return LocAfterEnd.isValid()
31 ? CharSourceRange::getCharRange(R.getBegin(), LocAfterEnd)
32 : CharSourceRange::getTokenRange(R);
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.
37class ASTSelectionFinder
38 : public LexicallyOrderedRecursiveASTVisitor<ASTSelectionFinder> {
39public:
40 ASTSelectionFinder(SourceRange Selection, FileID TargetFile,
41 const ASTContext &Context)
42 : LexicallyOrderedRecursiveASTVisitor(Context.getSourceManager()),
43 SelectionBegin(Selection.getBegin()),
44 SelectionEnd(Selection.getBegin() == Selection.getEnd()
46 : Selection.getEnd()),
47 TargetFile(TargetFile), Context(Context) {
48 // The TU decl is the root of the selected node tree.
49 SelectionStack.push_back(
51 SourceSelectionKind::None));
52 }
53
54 std::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 std::nullopt;
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 LookThrough(LookThroughOpaqueValueExprs, true);
68 return TraverseStmt(E->getSyntacticForm());
69 }
70
71 bool TraverseOpaqueValueExpr(OpaqueValueExpr *E) {
72 if (!LookThroughOpaqueValueExprs)
73 return true;
74 llvm::SaveAndRestore 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
132private:
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());
145 if (!SourceLocation::isPairOfFileLocations(Range.getBegin(), End))
146 return SourceSelectionKind::None;
147 if (!SelectionEnd.isValid()) {
148 // Do a quick check when the selection is of length 0.
149 if (SM.isPointWithin(SelectionBegin, Range.getBegin(), End))
150 return SourceSelectionKind::ContainsSelection;
151 return SourceSelectionKind::None;
152 }
153 bool HasStart = SM.isPointWithin(SelectionBegin, Range.getBegin(), End);
154 bool HasEnd = SM.isPointWithin(SelectionEnd, Range.getBegin(), End);
155 if (HasStart && HasEnd)
156 return SourceSelectionKind::ContainsSelection;
157 if (SM.isPointWithin(Range.getBegin(), SelectionBegin, SelectionEnd) &&
158 SM.isPointWithin(End, SelectionBegin, SelectionEnd))
159 return SourceSelectionKind::InsideSelection;
160 // Ensure there's at least some overlap with the 'start'/'end' selection
161 // types.
162 if (HasStart && SelectionBegin != End)
163 return SourceSelectionKind::ContainsSelectionStart;
164 if (HasEnd && SelectionEnd != Range.getBegin())
165 return SourceSelectionKind::ContainsSelectionEnd;
166
167 return SourceSelectionKind::None;
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
182std::optional<SelectedASTNode>
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) {
202 case SourceSelectionKind::None:
203 return "none";
204 case SourceSelectionKind::ContainsSelection:
205 return "contains-selection";
206 case SourceSelectionKind::ContainsSelectionStart:
207 return "contains-selection-start";
208 case SourceSelectionKind::ContainsSelectionEnd:
209 return "contains-selection-end";
210 case SourceSelectionKind::InsideSelection:
211 return "inside";
212 }
213 llvm_unreachable("invalid selection kind");
214}
215
216static 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->getDeclName() << '"';
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
231void 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.
239 SourceSelectionKind 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
250namespace {
251struct 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
260enum SelectionCanonicalizationAction { KeepSelection, SelectParent };
261
262/// Returns the canonicalization action which should be applied to the
263/// selected statement.
264SelectionCanonicalizationAction
265getSelectionCanonizalizationAction(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
290void 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,
374 SourceSelectionKind Kind) {
376 findDeepestWithKind(ASTSelection, MatchingNodes, Kind, ParentStack);
377}
378
379std::optional<CodeRangeASTSelection>
381 const SelectedASTNode &ASTSelection) {
382 // Code range is selected when the selection range is not empty.
383 if (SelectionRange.getBegin() == SelectionRange.getEnd())
384 return std::nullopt;
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 std::nullopt;
392 SelectedNodeWithParents &Selected = ContainSelection[0];
393 if (!Selected.Node.get().Node.get<Stmt>())
394 return std::nullopt;
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
414static 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}
NodeId Parent
Definition: ASTDiff.cpp:191
DynTypedNode Node
static bool isFunctionLikeDeclaration(const Decl *D)
static const char * selectionKindToString(SourceSelectionKind Kind)
static void dump(const SelectedASTNode &Node, llvm::raw_ostream &OS, unsigned Indent=0)
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...
static bool hasAnyDirectChildrenWithKind(const SelectedASTNode &Node, SourceSelectionKind Kind)
Returns true if the given node has any direct children with the following selection kind.
#define SM(sm)
Definition: Cuda.cpp:78
llvm::raw_ostream & OS
Definition: Logger.cpp:24
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:182
SourceManager & getSourceManager()
Definition: ASTContext.h:692
TranslationUnitDecl * getTranslationUnitDecl() const
Definition: ASTContext.h:1060
const LangOptions & getLangOpts() const
Definition: ASTContext.h:762
Represents a character-granular source range.
static CharSourceRange getCharRange(SourceRange R)
static CharSourceRange getTokenRange(SourceRange R)
CompoundStmt - This represents a group of statements like { stmt stmt }.
Definition: Stmt.h:1420
DeclStmt - Adaptor class for mixing declarations with statements and expressions.
Definition: Stmt.h:1311
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:83
bool isImplicit() const
isImplicit - Indicates whether the declaration was implicitly generated by the implementation.
Definition: DeclBase.h:576
const char * getDeclKindName() const
Definition: DeclBase.cpp:123
virtual SourceRange getSourceRange() const LLVM_READONLY
Source range that this declaration covers.
Definition: DeclBase.h:420
A dynamically typed AST node container.
const T * get() const
Retrieve the stored node as type T.
static DynTypedNode create(const T &Node)
Creates a DynTypedNode from Node.
An opaque identifier used by SourceManager which refers to a source file (MemoryBuffer) along with it...
Keeps track of the various options that can be enabled, which controls the dialect of C or C++ that i...
Definition: LangOptions.h:82
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:1294
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:786
A RecursiveASTVisitor subclass that guarantees that AST traversal is performed in a lexical order (i....
OpaqueValueExpr - An expression referring to an opaque object of a fixed type and value class.
Definition: Expr.h:1146
Expr * getSourceExpr() const
The source expression of an opaque value expression is the expression which originally generated the ...
Definition: Expr.h:1196
PseudoObjectExpr - An expression which accesses a pseudo-object l-value.
Definition: Expr.h:6107
Expr * getSyntacticForm()
Return the syntactic form of this expression, i.e.
Definition: Expr.h:6149
bool TraverseStmt(Stmt *S, DataRecursionQueue *Queue=nullptr)
Recursively visit a statement or expression, by dispatching to Traverse*() based on the argument's dy...
bool TraverseDecl(Decl *D)
Recursively visit a declaration, by dispatching to Traverse*Decl() based on the argument's dynamic ty...
Encodes a location in the source.
static bool isPairOfFileLocations(SourceLocation Start, SourceLocation End)
bool isValid() const
Return true if this is a valid SourceLocation object.
This class handles loading and caching of source files into memory.
FileID getFileID(SourceLocation SpellingLoc) const
Return the FileID for a SourceLocation.
A trivial tuple used to represent a source range.
SourceLocation getEnd() const
SourceLocation getBegin() const
bool isValid() const
Stmt - This represents one statement.
Definition: Stmt.h:72
An AST selection value that corresponds to a selection of a set of statements that belong to one body...
Definition: ASTSelection.h:96
const Decl * getFunctionLikeNearestParent() const
Returns the nearest function-like parent declaration or null if such declaration doesn't exist.
bool isInFunctionLikeBodyOfCode() const
Returns true when a selected code range is in a function-like body of code, like a function,...
static std::optional< CodeRangeASTSelection > create(SourceRange SelectionRange, const SelectedASTNode &ASTSelection)
A source range independent of the SourceManager.
Definition: Replacement.h:44
std::optional< SelectedASTNode > findSelectedASTNodes(const ASTContext &Context, SourceRange SelectionRange)
Traverses the given ASTContext and creates a tree of selected AST nodes.
@ ContainsSelection
A node that's considered to be selected because the whole selection range is inside of its source ran...
@ None
A node that's not selected.
Represents a selected AST node.
Definition: ASTSelection.h:52
std::vector< SelectedASTNode > Children
Definition: ASTSelection.h:55
void dump(llvm::raw_ostream &OS=llvm::errs()) const
std::reference_wrapper< const SelectedASTNode > ReferenceType
Definition: ASTSelection.h:64