| //===--- 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; |
| } |