lib/Tooling/Refactoring/ASTSelection.cpp - clang - Git at Google

 //===--- ASTSelection.cpp - Clang refactoring library ---------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//

 #include "clang/Tooling/Refactoring/ASTSelection.h"
 #include "clang/AST/LexicallyOrderedRecursiveASTVisitor.h"
 #include "clang/Lex/Lexer.h"
 #include "llvm/Support/SaveAndRestore.h"

 using namespace clang;
 using namespace tooling;
 using ast_type_traits::DynTypedNode;

 namespace {

 CharSourceRange getLexicalDeclRange(Decl *D, const SourceManager &SM,
                                     const LangOptions &LangOpts) {
   if (!isa<ObjCImplDecl>(D))
     return CharSourceRange::getTokenRange(D->getSourceRange());
   // Objective-C implementation declarations end at the '@' instead of the 'end'
   // keyword. Use the lexer to find the location right after 'end'.
   SourceRange R = D->getSourceRange();
   SourceLocation LocAfterEnd = Lexer::findLocationAfterToken(
       R.getEnd(), tok::raw_identifier, SM, LangOpts,
       /*SkipTrailingWhitespaceAndNewLine=*/false);
   return LocAfterEnd.isValid()
              ? CharSourceRange::getCharRange(R.getBegin(), LocAfterEnd)
              : CharSourceRange::getTokenRange(R);
 }

 /// Constructs the tree of selected AST nodes that either contain the location
 /// of the cursor or overlap with the selection range.
 class ASTSelectionFinder
     : public LexicallyOrderedRecursiveASTVisitor<ASTSelectionFinder> {
 public:
   ASTSelectionFinder(SourceRange Selection, FileID TargetFile,
                      const ASTContext &Context)
       : LexicallyOrderedRecursiveASTVisitor(Context.getSourceManager()),
         SelectionBegin(Selection.getBegin()),
         SelectionEnd(Selection.getBegin() == Selection.getEnd()
                          ? SourceLocation()
                          : Selection.getEnd()),
         TargetFile(TargetFile), Context(Context) {
     // The TU decl is the root of the selected node tree.
     SelectionStack.push_back(
         SelectedASTNode(DynTypedNode::create(*Context.getTranslationUnitDecl()),
                         SourceSelectionKind::None));
   }

   Optional<SelectedASTNode> getSelectedASTNode() {
     assert(SelectionStack.size() == 1 && "stack was not popped");
     SelectedASTNode Result = std::move(SelectionStack.back());
     SelectionStack.pop_back();
     if (Result.Children.empty())
       return None;
     return std::move(Result);
   }

   bool TraversePseudoObjectExpr(PseudoObjectExpr *E) {
     // Avoid traversing the semantic expressions. They should be handled by
     // looking through the appropriate opaque expressions in order to build
     // a meaningful selection tree.
     llvm::SaveAndRestore<bool> LookThrough(LookThroughOpaqueValueExprs, true);
     return TraverseStmt(E->getSyntacticForm());
   }

   bool TraverseOpaqueValueExpr(OpaqueValueExpr *E) {
     if (!LookThroughOpaqueValueExprs)
       return true;
     llvm::SaveAndRestore<bool> LookThrough(LookThroughOpaqueValueExprs, false);
     return TraverseStmt(E->getSourceExpr());
   }

   bool TraverseDecl(Decl *D) {
     if (isa<TranslationUnitDecl>(D))
       return LexicallyOrderedRecursiveASTVisitor::TraverseDecl(D);
     if (D->isImplicit())
       return true;

     // Check if this declaration is written in the file of interest.
     const SourceRange DeclRange = D->getSourceRange();
     const SourceManager &SM = Context.getSourceManager();
     SourceLocation FileLoc;
     if (DeclRange.getBegin().isMacroID() && !DeclRange.getEnd().isMacroID())
       FileLoc = DeclRange.getEnd();
     else
       FileLoc = SM.getSpellingLoc(DeclRange.getBegin());
     if (SM.getFileID(FileLoc) != TargetFile)
       return true;

     SourceSelectionKind SelectionKind =
         selectionKindFor(getLexicalDeclRange(D, SM, Context.getLangOpts()));
     SelectionStack.push_back(
         SelectedASTNode(DynTypedNode::create(*D), SelectionKind));
     LexicallyOrderedRecursiveASTVisitor::TraverseDecl(D);
     popAndAddToSelectionIfSelected(SelectionKind);

     if (DeclRange.getEnd().isValid() &&
         SM.isBeforeInTranslationUnit(SelectionEnd.isValid() ? SelectionEnd
                                                             : SelectionBegin,
                                      DeclRange.getEnd())) {
       // Stop early when we've reached a declaration after the selection.
       return false;
     }
     return true;
   }

   bool TraverseStmt(Stmt *S) {
     if (!S)
       return true;
     if (auto *Opaque = dyn_cast<OpaqueValueExpr>(S))
       return TraverseOpaqueValueExpr(Opaque);
     // Avoid selecting implicit 'this' expressions.
     if (auto *TE = dyn_cast<CXXThisExpr>(S)) {
       if (TE->isImplicit())
         return true;
     }
     // FIXME (Alex Lorenz): Improve handling for macro locations.
     SourceSelectionKind SelectionKind =
         selectionKindFor(CharSourceRange::getTokenRange(S->getSourceRange()));
     SelectionStack.push_back(
         SelectedASTNode(DynTypedNode::create(*S), SelectionKind));
     LexicallyOrderedRecursiveASTVisitor::TraverseStmt(S);
     popAndAddToSelectionIfSelected(SelectionKind);
     return true;
   }

 private:
   void popAndAddToSelectionIfSelected(SourceSelectionKind SelectionKind) {
     SelectedASTNode Node = std::move(SelectionStack.back());
     SelectionStack.pop_back();
     if (SelectionKind != SourceSelectionKind::None || !Node.Children.empty())
       SelectionStack.back().Children.push_back(std::move(Node));
   }

   SourceSelectionKind selectionKindFor(CharSourceRange Range) {
     SourceLocation End = Range.getEnd();
     const SourceManager &SM = Context.getSourceManager();
     if (Range.isTokenRange())
       End = Lexer::getLocForEndOfToken(End, 0, SM, Context.getLangOpts());
     if (!SourceLocation::isPairOfFileLocations(Range.getBegin(), End))
       return SourceSelectionKind::None;
     if (!SelectionEnd.isValid()) {
       // Do a quick check when the selection is of length 0.
       if (SM.isPointWithin(SelectionBegin, Range.getBegin(), End))
         return SourceSelectionKind::ContainsSelection;
       return SourceSelectionKind::None;
     }
     bool HasStart = SM.isPointWithin(SelectionBegin, Range.getBegin(), End);
     bool HasEnd = SM.isPointWithin(SelectionEnd, Range.getBegin(), End);
     if (HasStart && HasEnd)
       return SourceSelectionKind::ContainsSelection;
     if (SM.isPointWithin(Range.getBegin(), SelectionBegin, SelectionEnd) &&
         SM.isPointWithin(End, SelectionBegin, SelectionEnd))
       return SourceSelectionKind::InsideSelection;
     // Ensure there's at least some overlap with the 'start'/'end' selection
     // types.
     if (HasStart && SelectionBegin != End)
       return SourceSelectionKind::ContainsSelectionStart;
     if (HasEnd && SelectionEnd != Range.getBegin())
       return SourceSelectionKind::ContainsSelectionEnd;

     return SourceSelectionKind::None;
   }

   const SourceLocation SelectionBegin, SelectionEnd;
   FileID TargetFile;
   const ASTContext &Context;
   std::vector<SelectedASTNode> SelectionStack;
   /// Controls whether we can traverse through the OpaqueValueExpr. This is
   /// typically enabled during the traversal of syntactic form for
   /// PseudoObjectExprs.
   bool LookThroughOpaqueValueExprs = false;
 };

 } // end anonymous namespace

 Optional<SelectedASTNode>
 clang::tooling::findSelectedASTNodes(const ASTContext &Context,
                                      SourceRange SelectionRange) {
   assert(SelectionRange.isValid() &&
          SourceLocation::isPairOfFileLocations(SelectionRange.getBegin(),
                                                SelectionRange.getEnd()) &&
          "Expected a file range");
   FileID TargetFile =
       Context.getSourceManager().getFileID(SelectionRange.getBegin());
   assert(Context.getSourceManager().getFileID(SelectionRange.getEnd()) ==
              TargetFile &&
          "selection range must span one file");

   ASTSelectionFinder Visitor(SelectionRange, TargetFile, Context);
   Visitor.TraverseDecl(Context.getTranslationUnitDecl());
   return Visitor.getSelectedASTNode();
 }

 static const char *selectionKindToString(SourceSelectionKind Kind) {
   switch (Kind) {
   case SourceSelectionKind::None:
     return "none";
   case SourceSelectionKind::ContainsSelection:
     return "contains-selection";
   case SourceSelectionKind::ContainsSelectionStart:
     return "contains-selection-start";
   case SourceSelectionKind::ContainsSelectionEnd:
     return "contains-selection-end";
   case SourceSelectionKind::InsideSelection:
     return "inside";
   }
   llvm_unreachable("invalid selection kind");
 }

 static void dump(const SelectedASTNode &Node, llvm::raw_ostream &OS,
                  unsigned Indent = 0) {
   OS.indent(Indent * 2);
   if (const Decl *D = Node.Node.get<Decl>()) {
     OS << D->getDeclKindName() << "Decl";
     if (const auto *ND = dyn_cast<NamedDecl>(D))
       OS << " \"" << ND->getNameAsString() << '"';
   } else if (const Stmt *S = Node.Node.get<Stmt>()) {
     OS << S->getStmtClassName();
   }
   OS << ' ' << selectionKindToString(Node.SelectionKind) << "\n";
   for (const auto &Child : Node.Children)
     dump(Child, OS, Indent + 1);
 }

 void SelectedASTNode::dump(llvm::raw_ostream &OS) const { ::dump(*this, OS); }

 /// Returns true if the given node has any direct children with the following
 /// selection kind.
 ///
 /// Note: The direct children also include children of direct children with the
 /// "None" selection kind.
 static bool hasAnyDirectChildrenWithKind(const SelectedASTNode &Node,
                                          SourceSelectionKind Kind) {
   assert(Kind != SourceSelectionKind::None && "invalid predicate!");
   for (const auto &Child : Node.Children) {
     if (Child.SelectionKind == Kind)
       return true;
     if (Child.SelectionKind == SourceSelectionKind::None)
       return hasAnyDirectChildrenWithKind(Child, Kind);
   }
   return false;
 }

 namespace {
 struct SelectedNodeWithParents {
   SelectedASTNode::ReferenceType Node;
   llvm::SmallVector<SelectedASTNode::ReferenceType, 8> Parents;

   /// Canonicalizes the given selection by selecting different related AST nodes
   /// when it makes sense to do so.
   void canonicalize();
 };

 enum SelectionCanonicalizationAction { KeepSelection, SelectParent };

 /// Returns the canonicalization action which should be applied to the
 /// selected statement.
 SelectionCanonicalizationAction
 getSelectionCanonizalizationAction(const Stmt *S, const Stmt *Parent) {
   // Select the parent expression when:
   // - The string literal in ObjC string literal is selected, e.g.:
   //     @"test"   becomes   @"test"
   //      ~~~~~~             ~~~~~~~
   if (isa<StringLiteral>(S) && isa<ObjCStringLiteral>(Parent))
     return SelectParent;
   // The entire call should be selected when just the member expression
   // that refers to the method or the decl ref that refers to the function
   // is selected.
   //    f.call(args)  becomes  f.call(args)
   //      ~~~~                 ~~~~~~~~~~~~
   //    func(args)  becomes  func(args)
   //    ~~~~                 ~~~~~~~~~~
   else if (const auto *CE = dyn_cast<CallExpr>(Parent)) {
     if ((isa<MemberExpr>(S) || isa<DeclRefExpr>(S)) &&
         CE->getCallee()->IgnoreImpCasts() == S)
       return SelectParent;
   }
   // FIXME: Syntactic form -> Entire pseudo-object expr.
   return KeepSelection;
 }

 } // end anonymous namespace

 void SelectedNodeWithParents::canonicalize() {
   const Stmt *S = Node.get().Node.get<Stmt>();
   assert(S && "non statement selection!");
   const Stmt *Parent = Parents[Parents.size() - 1].get().Node.get<Stmt>();
   if (!Parent)
     return;

   // Look through the implicit casts in the parents.
   unsigned ParentIndex = 1;
   for (; (ParentIndex + 1) <= Parents.size() && isa<ImplicitCastExpr>(Parent);
        ++ParentIndex) {
     const Stmt *NewParent =
         Parents[Parents.size() - ParentIndex - 1].get().Node.get<Stmt>();
     if (!NewParent)
       break;
     Parent = NewParent;
   }

   switch (getSelectionCanonizalizationAction(S, Parent)) {
   case SelectParent:
     Node = Parents[Parents.size() - ParentIndex];
     for (; ParentIndex != 0; --ParentIndex)
       Parents.pop_back();
     break;
   case KeepSelection:
     break;
   }
 }

 /// Finds the set of bottom-most selected AST nodes that are in the selection
 /// tree with the specified selection kind.
 ///
 /// For example, given the following selection tree:
 ///
 /// FunctionDecl "f" contains-selection
 ///   CompoundStmt contains-selection [#1]
 ///     CallExpr inside
 ///     ImplicitCastExpr inside
 ///       DeclRefExpr inside
 ///     IntegerLiteral inside
 ///     IntegerLiteral inside
 /// FunctionDecl "f2" contains-selection
 ///   CompoundStmt contains-selection [#2]
 ///     CallExpr inside
 ///     ImplicitCastExpr inside
 ///       DeclRefExpr inside
 ///     IntegerLiteral inside
 ///     IntegerLiteral inside
 ///
 /// This function will find references to nodes #1 and #2 when searching for the
 /// \c ContainsSelection kind.
 static void findDeepestWithKind(
     const SelectedASTNode &ASTSelection,
     llvm::SmallVectorImpl<SelectedNodeWithParents> &MatchingNodes,
     SourceSelectionKind Kind,
     llvm::SmallVectorImpl<SelectedASTNode::ReferenceType> &ParentStack) {
   if (ASTSelection.Node.get<DeclStmt>()) {
     // Select the entire decl stmt when any of its child declarations is the
     // bottom-most.
     for (const auto &Child : ASTSelection.Children) {
       if (!hasAnyDirectChildrenWithKind(Child, Kind)) {
         MatchingNodes.push_back(SelectedNodeWithParents{
             std::cref(ASTSelection), {ParentStack.begin(), ParentStack.end()}});
         return;
       }
     }
   } else {
     if (!hasAnyDirectChildrenWithKind(ASTSelection, Kind)) {
       // This node is the bottom-most.
       MatchingNodes.push_back(SelectedNodeWithParents{
           std::cref(ASTSelection), {ParentStack.begin(), ParentStack.end()}});
       return;
     }
   }
   // Search in the children.
   ParentStack.push_back(std::cref(ASTSelection));
   for (const auto &Child : ASTSelection.Children)
     findDeepestWithKind(Child, MatchingNodes, Kind, ParentStack);
   ParentStack.pop_back();
 }

 static void findDeepestWithKind(
     const SelectedASTNode &ASTSelection,
     llvm::SmallVectorImpl<SelectedNodeWithParents> &MatchingNodes,
     SourceSelectionKind Kind) {
   llvm::SmallVector<SelectedASTNode::ReferenceType, 16> ParentStack;
   findDeepestWithKind(ASTSelection, MatchingNodes, Kind, ParentStack);
 }

 Optional<CodeRangeASTSelection>
 CodeRangeASTSelection::create(SourceRange SelectionRange,
                               const SelectedASTNode &ASTSelection) {
   // Code range is selected when the selection range is not empty.
   if (SelectionRange.getBegin() == SelectionRange.getEnd())
     return None;
   llvm::SmallVector<SelectedNodeWithParents, 4> ContainSelection;
   findDeepestWithKind(ASTSelection, ContainSelection,
                       SourceSelectionKind::ContainsSelection);
   // We are looking for a selection in one body of code, so let's focus on
   // one matching result.
   if (ContainSelection.size() != 1)
     return None;
   SelectedNodeWithParents &Selected = ContainSelection[0];
   if (!Selected.Node.get().Node.get<Stmt>())
     return None;
   const Stmt *CodeRangeStmt = Selected.Node.get().Node.get<Stmt>();
   if (!isa<CompoundStmt>(CodeRangeStmt)) {
     Selected.canonicalize();
     return CodeRangeASTSelection(Selected.Node, Selected.Parents,
                                  /*AreChildrenSelected=*/false);
   }
   // FIXME (Alex L): First selected SwitchCase means that first case statement.
   // is selected actually
   // (See https://github.com/apple/swift-clang & CompoundStmtRange).

   // FIXME (Alex L): Tweak selection rules for compound statements, see:
   // https://github.com/apple/swift-clang/blob/swift-4.1-branch/lib/Tooling/
   // Refactor/ASTSlice.cpp#L513
   // The user selected multiple statements in a compound statement.
   Selected.Parents.push_back(Selected.Node);
   return CodeRangeASTSelection(Selected.Node, Selected.Parents,
                                /*AreChildrenSelected=*/true);
 }

 static bool isFunctionLikeDeclaration(const Decl *D) {
   // FIXME (Alex L): Test for BlockDecl.
   return isa<FunctionDecl>(D) || isa<ObjCMethodDecl>(D);
 }

 bool CodeRangeASTSelection::isInFunctionLikeBodyOfCode() const {
   bool IsPrevCompound = false;
   // Scan through the parents (bottom-to-top) and check if the selection is
   // contained in a compound statement that's a body of a function/method
   // declaration.
   for (const auto &Parent : llvm::reverse(Parents)) {
     const DynTypedNode &Node = Parent.get().Node;
     if (const auto *D = Node.get<Decl>()) {
       if (isFunctionLikeDeclaration(D))
         return IsPrevCompound;
       // Stop the search at any type declaration to avoid returning true for
       // expressions in type declarations in functions, like:
       // function foo() { struct X {
       //   int m = /*selection:*/ 1 + 2 /*selection end*/; }; };
       if (isa<TypeDecl>(D))
         return false;
     }
     IsPrevCompound = Node.get<CompoundStmt>() != nullptr;
   }
   return false;
 }

 const Decl *CodeRangeASTSelection::getFunctionLikeNearestParent() const {
   for (const auto &Parent : llvm::reverse(Parents)) {
     const DynTypedNode &Node = Parent.get().Node;
     if (const auto *D = Node.get<Decl>()) {
       if (isFunctionLikeDeclaration(D))
         return D;
     }
   }
   return nullptr;
 }
	//===--- ASTSelection.cpp - Clang refactoring library ---------------------===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//

	#include "clang/Tooling/Refactoring/ASTSelection.h"
	#include "clang/AST/LexicallyOrderedRecursiveASTVisitor.h"
	#include "clang/Lex/Lexer.h"
	#include "llvm/Support/SaveAndRestore.h"

	using namespace clang;
	using namespace tooling;
	using ast_type_traits::DynTypedNode;

	namespace {

	CharSourceRange getLexicalDeclRange(Decl *D, const SourceManager &SM,
	const LangOptions &LangOpts) {
	if (!isa<ObjCImplDecl>(D))
	return CharSourceRange::getTokenRange(D->getSourceRange());
	// Objective-C implementation declarations end at the '@' instead of the 'end'
	// keyword. Use the lexer to find the location right after 'end'.
	SourceRange R = D->getSourceRange();
	SourceLocation LocAfterEnd = Lexer::findLocationAfterToken(
	R.getEnd(), tok::raw_identifier, SM, LangOpts,
	/SkipTrailingWhitespaceAndNewLine=/false);
	return LocAfterEnd.isValid()
	? CharSourceRange::getCharRange(R.getBegin(), LocAfterEnd)
	: CharSourceRange::getTokenRange(R);
	}

	/// Constructs the tree of selected AST nodes that either contain the location
	/// of the cursor or overlap with the selection range.
	class ASTSelectionFinder
	: public LexicallyOrderedRecursiveASTVisitor<ASTSelectionFinder> {
	public:
	ASTSelectionFinder(SourceRange Selection, FileID TargetFile,
	const ASTContext &Context)
	: LexicallyOrderedRecursiveASTVisitor(Context.getSourceManager()),
	SelectionBegin(Selection.getBegin()),
	SelectionEnd(Selection.getBegin() == Selection.getEnd()
	? SourceLocation()
	: Selection.getEnd()),
	TargetFile(TargetFile), Context(Context) {
	// The TU decl is the root of the selected node tree.
	SelectionStack.push_back(
	SelectedASTNode(DynTypedNode::create(*Context.getTranslationUnitDecl()),
	SourceSelectionKind::None));
	}

	Optional<SelectedASTNode> getSelectedASTNode() {
	assert(SelectionStack.size() == 1 && "stack was not popped");
	SelectedASTNode Result = std::move(SelectionStack.back());
	SelectionStack.pop_back();
	if (Result.Children.empty())
	return None;
	return std::move(Result);
	}

	bool TraversePseudoObjectExpr(PseudoObjectExpr *E) {
	// Avoid traversing the semantic expressions. They should be handled by
	// looking through the appropriate opaque expressions in order to build
	// a meaningful selection tree.
	llvm::SaveAndRestore<bool> LookThrough(LookThroughOpaqueValueExprs, true);
	return TraverseStmt(E->getSyntacticForm());
	}

	bool TraverseOpaqueValueExpr(OpaqueValueExpr *E) {
	if (!LookThroughOpaqueValueExprs)
	return true;
	llvm::SaveAndRestore<bool> LookThrough(LookThroughOpaqueValueExprs, false);
	return TraverseStmt(E->getSourceExpr());
	}

	bool TraverseDecl(Decl *D) {
	if (isa<TranslationUnitDecl>(D))
	return LexicallyOrderedRecursiveASTVisitor::TraverseDecl(D);
	if (D->isImplicit())
	return true;

	// Check if this declaration is written in the file of interest.
	const SourceRange DeclRange = D->getSourceRange();
	const SourceManager &SM = Context.getSourceManager();
	SourceLocation FileLoc;
	if (DeclRange.getBegin().isMacroID() && !DeclRange.getEnd().isMacroID())
	FileLoc = DeclRange.getEnd();
	else
	FileLoc = SM.getSpellingLoc(DeclRange.getBegin());
	if (SM.getFileID(FileLoc) != TargetFile)
	return true;

	SourceSelectionKind SelectionKind =
	selectionKindFor(getLexicalDeclRange(D, SM, Context.getLangOpts()));
	SelectionStack.push_back(
	SelectedASTNode(DynTypedNode::create(*D), SelectionKind));
	LexicallyOrderedRecursiveASTVisitor::TraverseDecl(D);
	popAndAddToSelectionIfSelected(SelectionKind);

	if (DeclRange.getEnd().isValid() &&
	SM.isBeforeInTranslationUnit(SelectionEnd.isValid() ? SelectionEnd
	: SelectionBegin,
	DeclRange.getEnd())) {
	// Stop early when we've reached a declaration after the selection.
	return false;
	}
	return true;
	}

	bool TraverseStmt(Stmt *S) {
	if (!S)
	return true;
	if (auto *Opaque = dyn_cast<OpaqueValueExpr>(S))
	return TraverseOpaqueValueExpr(Opaque);
	// Avoid selecting implicit 'this' expressions.
	if (auto *TE = dyn_cast<CXXThisExpr>(S)) {
	if (TE->isImplicit())
	return true;
	}
	// FIXME (Alex Lorenz): Improve handling for macro locations.
	SourceSelectionKind SelectionKind =
	selectionKindFor(CharSourceRange::getTokenRange(S->getSourceRange()));
	SelectionStack.push_back(
	SelectedASTNode(DynTypedNode::create(*S), SelectionKind));
	LexicallyOrderedRecursiveASTVisitor::TraverseStmt(S);
	popAndAddToSelectionIfSelected(SelectionKind);
	return true;
	}

	private:
	void popAndAddToSelectionIfSelected(SourceSelectionKind SelectionKind) {
	SelectedASTNode Node = std::move(SelectionStack.back());
	SelectionStack.pop_back();
	if (SelectionKind != SourceSelectionKind::None \|\| !Node.Children.empty())
	SelectionStack.back().Children.push_back(std::move(Node));
	}

	SourceSelectionKind selectionKindFor(CharSourceRange Range) {
	SourceLocation End = Range.getEnd();
	const SourceManager &SM = Context.getSourceManager();
	if (Range.isTokenRange())
	End = Lexer::getLocForEndOfToken(End, 0, SM, Context.getLangOpts());
	if (!SourceLocation::isPairOfFileLocations(Range.getBegin(), End))
	return SourceSelectionKind::None;
	if (!SelectionEnd.isValid()) {
	// Do a quick check when the selection is of length 0.
	if (SM.isPointWithin(SelectionBegin, Range.getBegin(), End))
	return SourceSelectionKind::ContainsSelection;
	return SourceSelectionKind::None;
	}
	bool HasStart = SM.isPointWithin(SelectionBegin, Range.getBegin(), End);
	bool HasEnd = SM.isPointWithin(SelectionEnd, Range.getBegin(), End);
	if (HasStart && HasEnd)
	return SourceSelectionKind::ContainsSelection;
	if (SM.isPointWithin(Range.getBegin(), SelectionBegin, SelectionEnd) &&
	SM.isPointWithin(End, SelectionBegin, SelectionEnd))
	return SourceSelectionKind::InsideSelection;
	// Ensure there's at least some overlap with the 'start'/'end' selection
	// types.
	if (HasStart && SelectionBegin != End)
	return SourceSelectionKind::ContainsSelectionStart;
	if (HasEnd && SelectionEnd != Range.getBegin())
	return SourceSelectionKind::ContainsSelectionEnd;

	return SourceSelectionKind::None;
	}

	const SourceLocation SelectionBegin, SelectionEnd;
	FileID TargetFile;
	const ASTContext &Context;
	std::vector<SelectedASTNode> SelectionStack;
	/// Controls whether we can traverse through the OpaqueValueExpr. This is
	/// typically enabled during the traversal of syntactic form for
	/// PseudoObjectExprs.
	bool LookThroughOpaqueValueExprs = false;
	};

	} // end anonymous namespace

	Optional<SelectedASTNode>
	clang::tooling::findSelectedASTNodes(const ASTContext &Context,
	SourceRange SelectionRange) {
	assert(SelectionRange.isValid() &&
	SourceLocation::isPairOfFileLocations(SelectionRange.getBegin(),
	SelectionRange.getEnd()) &&
	"Expected a file range");
	FileID TargetFile =
	Context.getSourceManager().getFileID(SelectionRange.getBegin());
	assert(Context.getSourceManager().getFileID(SelectionRange.getEnd()) ==
	TargetFile &&
	"selection range must span one file");

	ASTSelectionFinder Visitor(SelectionRange, TargetFile, Context);
	Visitor.TraverseDecl(Context.getTranslationUnitDecl());
	return Visitor.getSelectedASTNode();
	}

	static const char *selectionKindToString(SourceSelectionKind Kind) {
	switch (Kind) {
	case SourceSelectionKind::None:
	return "none";
	case SourceSelectionKind::ContainsSelection:
	return "contains-selection";
	case SourceSelectionKind::ContainsSelectionStart:
	return "contains-selection-start";
	case SourceSelectionKind::ContainsSelectionEnd:
	return "contains-selection-end";
	case SourceSelectionKind::InsideSelection:
	return "inside";
	}
	llvm_unreachable("invalid selection kind");
	}

	static void dump(const SelectedASTNode &Node, llvm::raw_ostream &OS,
	unsigned Indent = 0) {
	OS.indent(Indent * 2);
	if (const Decl *D = Node.Node.get<Decl>()) {
	OS << D->getDeclKindName() << "Decl";
	if (const auto *ND = dyn_cast<NamedDecl>(D))
	OS << " \"" << ND->getNameAsString() << '"';
	} else if (const Stmt *S = Node.Node.get<Stmt>()) {
	OS << S->getStmtClassName();
	}
	OS << ' ' << selectionKindToString(Node.SelectionKind) << "\n";
	for (const auto &Child : Node.Children)
	dump(Child, OS, Indent + 1);
	}

	void SelectedASTNode::dump(llvm::raw_ostream &OS) const { ::dump(*this, OS); }

	/// Returns true if the given node has any direct children with the following
	/// selection kind.
	///
	/// Note: The direct children also include children of direct children with the
	/// "None" selection kind.
	static bool hasAnyDirectChildrenWithKind(const SelectedASTNode &Node,
	SourceSelectionKind Kind) {
	assert(Kind != SourceSelectionKind::None && "invalid predicate!");
	for (const auto &Child : Node.Children) {
	if (Child.SelectionKind == Kind)
	return true;
	if (Child.SelectionKind == SourceSelectionKind::None)
	return hasAnyDirectChildrenWithKind(Child, Kind);
	}
	return false;
	}

	namespace {
	struct SelectedNodeWithParents {
	SelectedASTNode::ReferenceType Node;
	llvm::SmallVector<SelectedASTNode::ReferenceType, 8> Parents;

	/// Canonicalizes the given selection by selecting different related AST nodes
	/// when it makes sense to do so.
	void canonicalize();
	};

	enum SelectionCanonicalizationAction { KeepSelection, SelectParent };

	/// Returns the canonicalization action which should be applied to the
	/// selected statement.
	SelectionCanonicalizationAction
	getSelectionCanonizalizationAction(const Stmt S, const Stmt Parent) {
	// Select the parent expression when:
	// - The string literal in ObjC string literal is selected, e.g.:
	// @"test" becomes @"test"
	// ~~~~~~ ~~~~~~~
	if (isa<StringLiteral>(S) && isa<ObjCStringLiteral>(Parent))
	return SelectParent;
	// The entire call should be selected when just the member expression
	// that refers to the method or the decl ref that refers to the function
	// is selected.
	// f.call(args) becomes f.call(args)
	// ~~~~ ~~~~~~~~~~~~
	// func(args) becomes func(args)
	// ~~~~ ~~~~~~~~~~
	else if (const auto *CE = dyn_cast<CallExpr>(Parent)) {
	if ((isa<MemberExpr>(S) \|\| isa<DeclRefExpr>(S)) &&
	CE->getCallee()->IgnoreImpCasts() == S)
	return SelectParent;
	}
	// FIXME: Syntactic form -> Entire pseudo-object expr.
	return KeepSelection;
	}

	} // end anonymous namespace

	void SelectedNodeWithParents::canonicalize() {
	const Stmt *S = Node.get().Node.get<Stmt>();
	assert(S && "non statement selection!");
	const Stmt *Parent = Parents[Parents.size() - 1].get().Node.get<Stmt>();
	if (!Parent)
	return;

	// Look through the implicit casts in the parents.
	unsigned ParentIndex = 1;
	for (; (ParentIndex + 1) <= Parents.size() && isa<ImplicitCastExpr>(Parent);
	++ParentIndex) {
	const Stmt *NewParent =
	Parents[Parents.size() - ParentIndex - 1].get().Node.get<Stmt>();
	if (!NewParent)
	break;
	Parent = NewParent;
	}

	switch (getSelectionCanonizalizationAction(S, Parent)) {
	case SelectParent:
	Node = Parents[Parents.size() - ParentIndex];
	for (; ParentIndex != 0; --ParentIndex)
	Parents.pop_back();
	break;
	case KeepSelection:
	break;
	}
	}

	/// Finds the set of bottom-most selected AST nodes that are in the selection
	/// tree with the specified selection kind.
	///
	/// For example, given the following selection tree:
	///
	/// FunctionDecl "f" contains-selection
	/// CompoundStmt contains-selection [#1]
	/// CallExpr inside
	/// ImplicitCastExpr inside
	/// DeclRefExpr inside
	/// IntegerLiteral inside
	/// IntegerLiteral inside
	/// FunctionDecl "f2" contains-selection
	/// CompoundStmt contains-selection [#2]
	/// CallExpr inside
	/// ImplicitCastExpr inside
	/// DeclRefExpr inside
	/// IntegerLiteral inside
	/// IntegerLiteral inside
	///
	/// This function will find references to nodes #1 and #2 when searching for the
	/// \c ContainsSelection kind.
	static void findDeepestWithKind(
	const SelectedASTNode &ASTSelection,
	llvm::SmallVectorImpl<SelectedNodeWithParents> &MatchingNodes,
	SourceSelectionKind Kind,
	llvm::SmallVectorImpl<SelectedASTNode::ReferenceType> &ParentStack) {
	if (ASTSelection.Node.get<DeclStmt>()) {
	// Select the entire decl stmt when any of its child declarations is the
	// bottom-most.
	for (const auto &Child : ASTSelection.Children) {
	if (!hasAnyDirectChildrenWithKind(Child, Kind)) {
	MatchingNodes.push_back(SelectedNodeWithParents{
	std::cref(ASTSelection), {ParentStack.begin(), ParentStack.end()}});
	return;
	}
	}
	} else {
	if (!hasAnyDirectChildrenWithKind(ASTSelection, Kind)) {
	// This node is the bottom-most.
	MatchingNodes.push_back(SelectedNodeWithParents{
	std::cref(ASTSelection), {ParentStack.begin(), ParentStack.end()}});
	return;
	}
	}
	// Search in the children.
	ParentStack.push_back(std::cref(ASTSelection));
	for (const auto &Child : ASTSelection.Children)
	findDeepestWithKind(Child, MatchingNodes, Kind, ParentStack);
	ParentStack.pop_back();
	}

	static void findDeepestWithKind(
	const SelectedASTNode &ASTSelection,
	llvm::SmallVectorImpl<SelectedNodeWithParents> &MatchingNodes,
	SourceSelectionKind Kind) {
	llvm::SmallVector<SelectedASTNode::ReferenceType, 16> ParentStack;
	findDeepestWithKind(ASTSelection, MatchingNodes, Kind, ParentStack);
	}

	Optional<CodeRangeASTSelection>
	CodeRangeASTSelection::create(SourceRange SelectionRange,
	const SelectedASTNode &ASTSelection) {
	// Code range is selected when the selection range is not empty.
	if (SelectionRange.getBegin() == SelectionRange.getEnd())
	return None;
	llvm::SmallVector<SelectedNodeWithParents, 4> ContainSelection;
	findDeepestWithKind(ASTSelection, ContainSelection,
	SourceSelectionKind::ContainsSelection);
	// We are looking for a selection in one body of code, so let's focus on
	// one matching result.
	if (ContainSelection.size() != 1)
	return None;
	SelectedNodeWithParents &Selected = ContainSelection[0];
	if (!Selected.Node.get().Node.get<Stmt>())
	return None;
	const Stmt *CodeRangeStmt = Selected.Node.get().Node.get<Stmt>();
	if (!isa<CompoundStmt>(CodeRangeStmt)) {
	Selected.canonicalize();
	return CodeRangeASTSelection(Selected.Node, Selected.Parents,
	/AreChildrenSelected=/false);
	}
	// FIXME (Alex L): First selected SwitchCase means that first case statement.
	// is selected actually
	// (See https://github.com/apple/swift-clang & CompoundStmtRange).

	// FIXME (Alex L): Tweak selection rules for compound statements, see:
	// https://github.com/apple/swift-clang/blob/swift-4.1-branch/lib/Tooling/
	// Refactor/ASTSlice.cpp#L513
	// The user selected multiple statements in a compound statement.
	Selected.Parents.push_back(Selected.Node);
	return CodeRangeASTSelection(Selected.Node, Selected.Parents,
	/AreChildrenSelected=/true);
	}

	static bool isFunctionLikeDeclaration(const Decl *D) {
	// FIXME (Alex L): Test for BlockDecl.
	return isa<FunctionDecl>(D) \|\| isa<ObjCMethodDecl>(D);
	}

	bool CodeRangeASTSelection::isInFunctionLikeBodyOfCode() const {
	bool IsPrevCompound = false;
	// Scan through the parents (bottom-to-top) and check if the selection is
	// contained in a compound statement that's a body of a function/method
	// declaration.
	for (const auto &Parent : llvm::reverse(Parents)) {
	const DynTypedNode &Node = Parent.get().Node;
	if (const auto *D = Node.get<Decl>()) {
	if (isFunctionLikeDeclaration(D))
	return IsPrevCompound;
	// Stop the search at any type declaration to avoid returning true for
	// expressions in type declarations in functions, like:
	// function foo() { struct X {
	// int m = /selection:/ 1 + 2 /selection end/; }; };
	if (isa<TypeDecl>(D))
	return false;
	}
	IsPrevCompound = Node.get<CompoundStmt>() != nullptr;
	}
	return false;
	}

	const Decl *CodeRangeASTSelection::getFunctionLikeNearestParent() const {
	for (const auto &Parent : llvm::reverse(Parents)) {
	const DynTypedNode &Node = Parent.get().Node;
	if (const auto *D = Node.get<Decl>()) {
	if (isFunctionLikeDeclaration(D))
	return D;
	}
	}
	return nullptr;
	}