contrib/llvm/tools/clang/lib/Tooling/Refactoring/ASTSelection.cpp

   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
  10 #include "clang/Tooling/Refactoring/ASTSelection.h"
  11 #include "clang/AST/LexicallyOrderedRecursiveASTVisitor.h"
  12 #include "clang/Lex/Lexer.h"
  13 #include "llvm/Support/SaveAndRestore.h"
  14
  15 using namespace clang;
  16 using namespace tooling;
  17 using ast_type_traits::DynTypedNode;
  18
  19 namespace {
  20
  21 CharSourceRange getLexicalDeclRange(Decl *D, const SourceManager &SM,
  22                                     const LangOptions &LangOpts) {
  23   if (!isa<ObjCImplDecl>(D))
  24     return CharSourceRange::getTokenRange(D->getSourceRange());
  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();
  28   SourceLocation LocAfterEnd = Lexer::findLocationAfterToken(
  29       R.getEnd(), tok::raw_identifier, SM, LangOpts,
  30       /*SkipTrailingWhitespaceAndNewLine=*/false);
  31   return LocAfterEnd.isValid()
  32              ? CharSourceRange::getCharRange(R.getBegin(), LocAfterEnd)
  33              : CharSourceRange::getTokenRange(R);
  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(
  51         SelectedASTNode(DynTypedNode::create(*Context.getTranslationUnitDecl()),
  52                         SourceSelectionKind::None));
  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))
  81       return LexicallyOrderedRecursiveASTVisitor::TraverseDecl(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));
 100     LexicallyOrderedRecursiveASTVisitor::TraverseDecl(D);
 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));
 128     LexicallyOrderedRecursiveASTVisitor::TraverseStmt(S);
 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());
 146     if (!SourceLocation::isPairOfFileLocations(Range.getBegin(), End))
 147       return SourceSelectionKind::None;
 148     if (!SelectionEnd.isValid()) {
 149       // Do a quick check when the selection is of length 0.
 150       if (SM.isPointWithin(SelectionBegin, Range.getBegin(), End))
 151         return SourceSelectionKind::ContainsSelection;
 152       return SourceSelectionKind::None;
 153     }
 154     bool HasStart = SM.isPointWithin(SelectionBegin, Range.getBegin(), End);
 155     bool HasEnd = SM.isPointWithin(SelectionEnd, Range.getBegin(), End);
 156     if (HasStart && HasEnd)
 157       return SourceSelectionKind::ContainsSelection;
 158     if (SM.isPointWithin(Range.getBegin(), SelectionBegin, SelectionEnd) &&
 159         SM.isPointWithin(End, SelectionBegin, SelectionEnd))
 160       return SourceSelectionKind::InsideSelection;
 161     // Ensure there's at least some overlap with the 'start'/'end' selection
 162     // types.
 163     if (HasStart && SelectionBegin != End)
 164       return SourceSelectionKind::ContainsSelectionStart;
 165     if (HasEnd && SelectionEnd != Range.getBegin())
 166       return SourceSelectionKind::ContainsSelectionEnd;
 167
 168     return SourceSelectionKind::None;
 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
 183 Optional<SelectedASTNode>
 184 clang::tooling::findSelectedASTNodes(const ASTContext &Context,
 185                                      SourceRange SelectionRange) {
 186   assert(SelectionRange.isValid() &&
 187          SourceLocation::isPairOfFileLocations(SelectionRange.getBegin(),
 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
 201 static const char *selectionKindToString(SourceSelectionKind Kind) {
 202   switch (Kind) {
 203   case SourceSelectionKind::None:
 204     return "none";
 205   case SourceSelectionKind::ContainsSelection:
 206     return "contains-selection";
 207   case SourceSelectionKind::ContainsSelectionStart:
 208     return "contains-selection-start";
 209   case SourceSelectionKind::ContainsSelectionEnd:
 210     return "contains-selection-end";
 211   case SourceSelectionKind::InsideSelection:
 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.
 239 static bool hasAnyDirectChildrenWithKind(const SelectedASTNode &Node,
 240                                          SourceSelectionKind 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;
 255   SelectedASTNode::ReferenceType Node;
 256   llvm::SmallVector<SelectedASTNode::ReferenceType, 8> Parents;
 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.
 267 SelectionCanonicalizationAction
 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.
 344 static void findDeepestWithKind(
 345     const SelectedASTNode &ASTSelection,
 346     llvm::SmallVectorImpl<SelectedNodeWithParents> &MatchingNodes,
 347     SourceSelectionKind Kind,
 348     llvm::SmallVectorImpl<SelectedASTNode::ReferenceType> &ParentStack) {
 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
 374 static void findDeepestWithKind(
 375     const SelectedASTNode &ASTSelection,
 376     llvm::SmallVectorImpl<SelectedNodeWithParents> &MatchingNodes,
 377     SourceSelectionKind Kind) {
 378   llvm::SmallVector<SelectedASTNode::ReferenceType, 16> ParentStack;
 379   findDeepestWithKind(ASTSelection, MatchingNodes, Kind, ParentStack);
 380 }
 381
 382 Optional<CodeRangeASTSelection>
 383 CodeRangeASTSelection::create(SourceRange SelectionRange,
 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;
 388   llvm::SmallVector<SelectedNodeWithParents, 4> ContainSelection;
 389   findDeepestWithKind(ASTSelection, ContainSelection,
 390                       SourceSelectionKind::ContainsSelection);
 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
 422 bool CodeRangeASTSelection::isInFunctionLikeBodyOfCode() const {
 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>()) {
 430       if (isFunctionLikeDeclaration(D))
 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
 444 const Decl *CodeRangeASTSelection::getFunctionLikeNearestParent() const {
 445   for (const auto &Parent : llvm::reverse(Parents)) {
 446     const DynTypedNode &Node = Parent.get().Node;
 447     if (const auto *D = Node.get<Decl>()) {
 448       if (isFunctionLikeDeclaration(D))
 449         return D;
 450     }
 451   }
 452   return nullptr;
 453 }