| //===--- 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" | |
| #include <optional> | |
| using namespace clang; | |
| using namespace tooling; | |
| 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)); | |
| } | |
| std::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 std::nullopt; | |
| 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 LookThrough(LookThroughOpaqueValueExprs, true); | |
| return TraverseStmt(E->getSyntacticForm()); | |
| } | |
| bool TraverseOpaqueValueExpr(OpaqueValueExpr *E) { | |
| if (!LookThroughOpaqueValueExprs) | |
| return true; | |
| llvm::SaveAndRestore 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 | |
| std::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->getDeclName() << '"'; | |
| } 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); | |
| } | |
| std::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 std::nullopt; | |
| 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 std::nullopt; | |
| SelectedNodeWithParents &Selected = ContainSelection[0]; | |
| if (!Selected.Node.get().Node.get<Stmt>()) | |
| return std::nullopt; | |
| 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; | |
| } |