Clang Project

clang_source_code/lib/Tooling/Refactoring/ASTSelection.cpp
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
9#include "clang/Tooling/Refactoring/ASTSelection.h"
10#include "clang/AST/LexicallyOrderedRecursiveASTVisitor.h"
11#include "clang/Lex/Lexer.h"
12#include "llvm/Support/SaveAndRestore.h"
13
14using namespace clang;
15using namespace tooling;
16using ast_type_traits::DynTypedNode;
17
18namespace {
19
20CharSourceRange getLexicalDeclRange(Decl *D, const SourceManager &SM,
21                                    const LangOptions &LangOpts) {
22  if (!isa<ObjCImplDecl>(D))
23    return CharSourceRange::getTokenRange(D->getSourceRange());
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();
27  SourceLocation LocAfterEnd = Lexer::findLocationAfterToken(
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()
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(
50        SelectedASTNode(DynTypedNode::create(*Context.getTranslationUnitDecl()),
51                        SourceSelectionKind::None));
52  }
53
54  Optional<SelectedASTNode> getSelectedASTNode() {
55     (0) . __assert_fail ("SelectionStack.size() == 1 && \"stack was not popped\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/Refactoring/ASTSelection.cpp", 55, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">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))
80      return LexicallyOrderedRecursiveASTVisitor::TraverseDecl(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));
99    LexicallyOrderedRecursiveASTVisitor::TraverseDecl(D);
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));
127    LexicallyOrderedRecursiveASTVisitor::TraverseStmt(S);
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
182Optional<SelectedASTNode>
183clang::tooling::findSelectedASTNodes(const ASTContext &Context,
184                                     SourceRange SelectionRange) {
185   (0) . __assert_fail ("SelectionRange.isValid() && SourceLocation..isPairOfFileLocations(SelectionRange.getBegin(), SelectionRange.getEnd()) && \"Expected a file range\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/Refactoring/ASTSelection.cpp", 188, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(SelectionRange.isValid() &&
186 (0) . __assert_fail ("SelectionRange.isValid() && SourceLocation..isPairOfFileLocations(SelectionRange.getBegin(), SelectionRange.getEnd()) && \"Expected a file range\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/Refactoring/ASTSelection.cpp", 188, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">         SourceLocation::isPairOfFileLocations(SelectionRange.getBegin(),
187 (0) . __assert_fail ("SelectionRange.isValid() && SourceLocation..isPairOfFileLocations(SelectionRange.getBegin(), SelectionRange.getEnd()) && \"Expected a file range\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/Refactoring/ASTSelection.cpp", 188, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">                                               SelectionRange.getEnd()) &&
188 (0) . __assert_fail ("SelectionRange.isValid() && SourceLocation..isPairOfFileLocations(SelectionRange.getBegin(), SelectionRange.getEnd()) && \"Expected a file range\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/Refactoring/ASTSelection.cpp", 188, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">         "Expected a file range");
189  FileID TargetFile =
190      Context.getSourceManager().getFileID(SelectionRange.getBegin());
191   (0) . __assert_fail ("Context.getSourceManager().getFileID(SelectionRange.getEnd()) == TargetFile && \"selection range must span one file\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/Refactoring/ASTSelection.cpp", 193, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(Context.getSourceManager().getFileID(SelectionRange.getEnd()) ==
192 (0) . __assert_fail ("Context.getSourceManager().getFileID(SelectionRange.getEnd()) == TargetFile && \"selection range must span one file\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/Refactoring/ASTSelection.cpp", 193, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">             TargetFile &&
193 (0) . __assert_fail ("Context.getSourceManager().getFileID(SelectionRange.getEnd()) == TargetFile && \"selection range must span one file\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/Refactoring/ASTSelection.cpp", 193, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">         "selection range must span one file");
194
195  ASTSelectionFinder Visitor(SelectionRange, TargetFile, Context);
196  Visitor.TraverseDecl(Context.getTranslationUnitDecl());
197  return Visitor.getSelectedASTNode();
198}
199
200static const char *selectionKindToString(SourceSelectionKind Kind) {
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->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
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.
238static bool hasAnyDirectChildrenWithKind(const SelectedASTNode &Node,
239                                         SourceSelectionKind Kind) {
240   (0) . __assert_fail ("Kind != SourceSelectionKind..None && \"invalid predicate!\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/Refactoring/ASTSelection.cpp", 240, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">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 {
252  SelectedASTNode::ReferenceType Node;
253  llvm::SmallVector<SelectedASTNode::ReferenceType, 8> Parents;
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   (0) . __assert_fail ("S && \"non statement selection!\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/Refactoring/ASTSelection.cpp", 292, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">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.
341static void findDeepestWithKind(
342    const SelectedASTNode &ASTSelection,
343    llvm::SmallVectorImpl<SelectedNodeWithParents> &MatchingNodes,
344    SourceSelectionKind Kind,
345    llvm::SmallVectorImpl<SelectedASTNode::ReferenceType> &ParentStack) {
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
371static void findDeepestWithKind(
372    const SelectedASTNode &ASTSelection,
373    llvm::SmallVectorImpl<SelectedNodeWithParents> &MatchingNodes,
374    SourceSelectionKind Kind) {
375  llvm::SmallVector<SelectedASTNode::ReferenceType, 16> ParentStack;
376  findDeepestWithKind(ASTSelection, MatchingNodes, Kind, ParentStack);
377}
378
379Optional<CodeRangeASTSelection>
380CodeRangeASTSelection::create(SourceRange SelectionRange,
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;
385  llvm::SmallVector<SelectedNodeWithParents, 4> ContainSelection;
386  findDeepestWithKind(ASTSelection, ContainSelection,
387                      SourceSelectionKind::ContainsSelection);
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
414static bool isFunctionLikeDeclaration(const Decl *D) {
415  // FIXME (Alex L): Test for BlockDecl.
416  return isa<FunctionDecl>(D) || isa<ObjCMethodDecl>(D);
417}
418
419bool CodeRangeASTSelection::isInFunctionLikeBodyOfCode() const {
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>()) {
427      if (isFunctionLikeDeclaration(D))
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
441const Decl *CodeRangeASTSelection::getFunctionLikeNearestParent() const {
442  for (const auto &Parent : llvm::reverse(Parents)) {
443    const DynTypedNode &Node = Parent.get().Node;
444    if (const auto *D = Node.get<Decl>()) {
445      if (isFunctionLikeDeclaration(D))
446        return D;
447    }
448  }
449  return nullptr;
450}
451
clang::tooling::SelectedASTNode::dump
clang::tooling::CodeRangeASTSelection::create
clang::tooling::CodeRangeASTSelection::isInFunctionLikeBodyOfCode
clang::tooling::CodeRangeASTSelection::getFunctionLikeNearestParent
CodeThinker, Enjoy your reading code