clang/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 #include <optional>
  14
  15 using namespace clang;
  16 using namespace tooling;
  17
  18 namespace {
  19
  20 CharSourceRange 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.
  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(
  50         SelectedASTNode(DynTypedNode::create(*Context.getTranslationUnitDecl()),
  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))
  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
 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());
 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
 182 std::optional<SelectedASTNode>
 183 clang::tooling::findSelectedASTNodes(const ASTContext &Context,
 184                                      SourceRange SelectionRange) {
 185   assert(SelectionRange.isValid() &&
 186          SourceLocation::isPairOfFileLocations(SelectionRange.getBegin(),
 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
 200 static 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
 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->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
 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.
 238 static bool hasAnyDirectChildrenWithKind(const SelectedASTNode &Node,
 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
 250 namespace {
 251 struct 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
 260 enum SelectionCanonicalizationAction { KeepSelection, SelectParent };
 261
 262 /// Returns the canonicalization action which should be applied to the
 263 /// selected statement.
 264 SelectionCanonicalizationAction
 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.
 341 static 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
 371 static 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
 379 std::optional<CodeRangeASTSelection>
 380 CodeRangeASTSelection::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 std::nullopt;
 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 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
 414 static bool isFunctionLikeDeclaration(const Decl *D) {
 415   // FIXME (Alex L): Test for BlockDecl.
 416   return isa<FunctionDecl>(D) || isa<ObjCMethodDecl>(D);
 417 }
 418
 419 bool 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
 441 const 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 }