451 lines · 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-exception6//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 15using namespace clang;16using namespace tooling;17 18namespace {19 20CharSourceRange 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 location36/// of the cursor or overlap with the selection range.37class ASTSelectionFinder38 : public LexicallyOrderedRecursiveASTVisitor<ASTSelectionFinder> {39public: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 by65 // looking through the appropriate opaque expressions in order to build66 // 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 else91 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() ? SelectionEnd104 : 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 132private: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' selection161 // 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 is175 /// typically enabled during the traversal of syntactic form for176 /// PseudoObjectExprs.177 bool LookThroughOpaqueValueExprs = false;178};179 180} // end anonymous namespace181 182std::optional<SelectedASTNode>183clang::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 200static 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 216static 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 231void SelectedASTNode::dump(llvm::raw_ostream &OS) const { ::dump(*this, OS); }232 233/// Returns true if the given node has any direct children with the following234/// selection kind.235///236/// Note: The direct children also include children of direct children with the237/// "None" selection kind.238static 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 250namespace {251struct SelectedNodeWithParents {252 SelectedASTNode::ReferenceType Node;253 llvm::SmallVector<SelectedASTNode::ReferenceType, 8> Parents;254 255 /// Canonicalizes the given selection by selecting different related AST nodes256 /// when it makes sense to do so.257 void canonicalize();258};259 260enum SelectionCanonicalizationAction { KeepSelection, SelectParent };261 262/// Returns the canonicalization action which should be applied to the263/// selected statement.264SelectionCanonicalizationAction265getSelectionCanonizalizationAction(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 expression273 // that refers to the method or the decl ref that refers to the function274 // 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 namespace289 290void 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 selection320/// tree with the specified selection kind.321///322/// For example, given the following selection tree:323///324/// FunctionDecl "f" contains-selection325/// CompoundStmt contains-selection [#1]326/// CallExpr inside327/// ImplicitCastExpr inside328/// DeclRefExpr inside329/// IntegerLiteral inside330/// IntegerLiteral inside331/// FunctionDecl "f2" contains-selection332/// CompoundStmt contains-selection [#2]333/// CallExpr inside334/// ImplicitCastExpr inside335/// DeclRefExpr inside336/// IntegerLiteral inside337/// IntegerLiteral inside338///339/// This function will find references to nodes #1 and #2 when searching for the340/// \c ContainsSelection kind.341static 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 the348 // 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 371static 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 379std::optional<CodeRangeASTSelection>380CodeRangeASTSelection::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 on389 // 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 actually403 // (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#L513408 // 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 414static bool isFunctionLikeDeclaration(const Decl *D) {415 // FIXME (Alex L): Test for BlockDecl.416 return isa<FunctionDecl>(D) || isa<ObjCMethodDecl>(D);417}418 419bool CodeRangeASTSelection::isInFunctionLikeBodyOfCode() const {420 bool IsPrevCompound = false;421 // Scan through the parents (bottom-to-top) and check if the selection is422 // contained in a compound statement that's a body of a function/method423 // 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 for430 // 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 441const 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}451