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     // FIXME (Alex Lorenz): Improve handling for macro locations.
119     SourceSelectionKind SelectionKind =
120         selectionKindFor(CharSourceRange::getTokenRange(S->getSourceRange()));
121     SelectionStack.push_back(
122         SelectedASTNode(DynTypedNode::create(*S), SelectionKind));
123     LexicallyOrderedRecursiveASTVisitor::TraverseStmt(S);
124     popAndAddToSelectionIfSelected(SelectionKind);
125     return true;
126   }
127 
128 private:
129   void popAndAddToSelectionIfSelected(SourceSelectionKind SelectionKind) {
130     SelectedASTNode Node = std::move(SelectionStack.back());
131     SelectionStack.pop_back();
132     if (SelectionKind != SourceSelectionKind::None || !Node.Children.empty())
133       SelectionStack.back().Children.push_back(std::move(Node));
134   }
135 
136   SourceSelectionKind selectionKindFor(CharSourceRange Range) {
137     SourceLocation End = Range.getEnd();
138     const SourceManager &SM = Context.getSourceManager();
139     if (Range.isTokenRange())
140       End = Lexer::getLocForEndOfToken(End, 0, SM, Context.getLangOpts());
141     if (!SourceLocation::isPairOfFileLocations(Range.getBegin(), End))
142       return SourceSelectionKind::None;
143     if (!SelectionEnd.isValid()) {
144       // Do a quick check when the selection is of length 0.
145       if (SM.isPointWithin(SelectionBegin, Range.getBegin(), End))
146         return SourceSelectionKind::ContainsSelection;
147       return SourceSelectionKind::None;
148     }
149     bool HasStart = SM.isPointWithin(SelectionBegin, Range.getBegin(), End);
150     bool HasEnd = SM.isPointWithin(SelectionEnd, Range.getBegin(), End);
151     if (HasStart && HasEnd)
152       return SourceSelectionKind::ContainsSelection;
153     if (SM.isPointWithin(Range.getBegin(), SelectionBegin, SelectionEnd) &&
154         SM.isPointWithin(End, SelectionBegin, SelectionEnd))
155       return SourceSelectionKind::InsideSelection;
156     // Ensure there's at least some overlap with the 'start'/'end' selection
157     // types.
158     if (HasStart && SelectionBegin != End)
159       return SourceSelectionKind::ContainsSelectionStart;
160     if (HasEnd && SelectionEnd != Range.getBegin())
161       return SourceSelectionKind::ContainsSelectionEnd;
162 
163     return SourceSelectionKind::None;
164   }
165 
166   const SourceLocation SelectionBegin, SelectionEnd;
167   FileID TargetFile;
168   const ASTContext &Context;
169   std::vector<SelectedASTNode> SelectionStack;
170   /// Controls whether we can traverse through the OpaqueValueExpr. This is
171   /// typically enabled during the traversal of syntactic form for
172   /// PseudoObjectExprs.
173   bool LookThroughOpaqueValueExprs = false;
174 };
175 
176 } // end anonymous namespace
177 
178 Optional<SelectedASTNode>
179 clang::tooling::findSelectedASTNodes(const ASTContext &Context,
180                                      SourceRange SelectionRange) {
181   assert(SelectionRange.isValid() &&
182          SourceLocation::isPairOfFileLocations(SelectionRange.getBegin(),
183                                                SelectionRange.getEnd()) &&
184          "Expected a file range");
185   FileID TargetFile =
186       Context.getSourceManager().getFileID(SelectionRange.getBegin());
187   assert(Context.getSourceManager().getFileID(SelectionRange.getEnd()) ==
188              TargetFile &&
189          "selection range must span one file");
190 
191   ASTSelectionFinder Visitor(SelectionRange, TargetFile, Context);
192   Visitor.TraverseDecl(Context.getTranslationUnitDecl());
193   return Visitor.getSelectedASTNode();
194 }
195 
196 static const char *selectionKindToString(SourceSelectionKind Kind) {
197   switch (Kind) {
198   case SourceSelectionKind::None:
199     return "none";
200   case SourceSelectionKind::ContainsSelection:
201     return "contains-selection";
202   case SourceSelectionKind::ContainsSelectionStart:
203     return "contains-selection-start";
204   case SourceSelectionKind::ContainsSelectionEnd:
205     return "contains-selection-end";
206   case SourceSelectionKind::InsideSelection:
207     return "inside";
208   }
209   llvm_unreachable("invalid selection kind");
210 }
211 
212 static void dump(const SelectedASTNode &Node, llvm::raw_ostream &OS,
213                  unsigned Indent = 0) {
214   OS.indent(Indent * 2);
215   if (const Decl *D = Node.Node.get<Decl>()) {
216     OS << D->getDeclKindName() << "Decl";
217     if (const auto *ND = dyn_cast<NamedDecl>(D))
218       OS << " \"" << ND->getNameAsString() << '"';
219   } else if (const Stmt *S = Node.Node.get<Stmt>()) {
220     OS << S->getStmtClassName();
221   }
222   OS << ' ' << selectionKindToString(Node.SelectionKind) << "\n";
223   for (const auto &Child : Node.Children)
224     dump(Child, OS, Indent + 1);
225 }
226 
227 void SelectedASTNode::dump(llvm::raw_ostream &OS) const { ::dump(*this, OS); }
228