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 
14 using namespace clang;
15 using namespace tooling;
16 using ast_type_traits::DynTypedNode;
17 
18 namespace {
19 
20 /// Constructs the tree of selected AST nodes that either contain the location
21 /// of the cursor or overlap with the selection range.
22 class ASTSelectionFinder
23     : public LexicallyOrderedRecursiveASTVisitor<ASTSelectionFinder> {
24 public:
25   ASTSelectionFinder(SourceRange Selection, FileID TargetFile,
26                      const ASTContext &Context)
27       : LexicallyOrderedRecursiveASTVisitor(Context.getSourceManager()),
28         SelectionBegin(Selection.getBegin()),
29         SelectionEnd(Selection.getBegin() == Selection.getEnd()
30                          ? SourceLocation()
31                          : Selection.getEnd()),
32         TargetFile(TargetFile), Context(Context) {
33     // The TU decl is the root of the selected node tree.
34     SelectionStack.push_back(
35         SelectedASTNode(DynTypedNode::create(*Context.getTranslationUnitDecl()),
36                         SourceSelectionKind::None));
37   }
38 
39   Optional<SelectedASTNode> getSelectedASTNode() {
40     assert(SelectionStack.size() == 1 && "stack was not popped");
41     SelectedASTNode Result = std::move(SelectionStack.back());
42     SelectionStack.pop_back();
43     if (Result.Children.empty())
44       return None;
45     return std::move(Result);
46   }
47 
48   bool TraverseDecl(Decl *D) {
49     if (isa<TranslationUnitDecl>(D))
50       return LexicallyOrderedRecursiveASTVisitor::TraverseDecl(D);
51     if (D->isImplicit())
52       return true;
53 
54     // Check if this declaration is written in the file of interest.
55     const SourceRange DeclRange = D->getSourceRange();
56     const SourceManager &SM = Context.getSourceManager();
57     SourceLocation FileLoc;
58     if (DeclRange.getBegin().isMacroID() && !DeclRange.getEnd().isMacroID())
59       FileLoc = DeclRange.getEnd();
60     else
61       FileLoc = SM.getSpellingLoc(DeclRange.getBegin());
62     if (SM.getFileID(FileLoc) != TargetFile)
63       return true;
64 
65     // FIXME (Alex Lorenz): Add location adjustment for ObjCImplDecls.
66     SourceSelectionKind SelectionKind =
67         selectionKindFor(CharSourceRange::getTokenRange(D->getSourceRange()));
68     SelectionStack.push_back(
69         SelectedASTNode(DynTypedNode::create(*D), SelectionKind));
70     LexicallyOrderedRecursiveASTVisitor::TraverseDecl(D);
71     popAndAddToSelectionIfSelected(SelectionKind);
72 
73     if (DeclRange.getEnd().isValid() &&
74         SM.isBeforeInTranslationUnit(SelectionEnd.isValid() ? SelectionEnd
75                                                             : SelectionBegin,
76                                      DeclRange.getEnd())) {
77       // Stop early when we've reached a declaration after the selection.
78       return false;
79     }
80     return true;
81   }
82 
83   bool TraverseStmt(Stmt *S) {
84     if (!S)
85       return true;
86     // FIXME (Alex Lorenz): Improve handling for macro locations.
87     SourceSelectionKind SelectionKind =
88         selectionKindFor(CharSourceRange::getTokenRange(S->getSourceRange()));
89     SelectionStack.push_back(
90         SelectedASTNode(DynTypedNode::create(*S), SelectionKind));
91     LexicallyOrderedRecursiveASTVisitor::TraverseStmt(S);
92     popAndAddToSelectionIfSelected(SelectionKind);
93     return true;
94   }
95 
96 private:
97   void popAndAddToSelectionIfSelected(SourceSelectionKind SelectionKind) {
98     SelectedASTNode Node = std::move(SelectionStack.back());
99     SelectionStack.pop_back();
100     if (SelectionKind != SourceSelectionKind::None || !Node.Children.empty())
101       SelectionStack.back().Children.push_back(std::move(Node));
102   }
103 
104   SourceSelectionKind selectionKindFor(CharSourceRange Range) {
105     SourceLocation End = Range.getEnd();
106     const SourceManager &SM = Context.getSourceManager();
107     if (Range.isTokenRange())
108       End = Lexer::getLocForEndOfToken(End, 0, SM, Context.getLangOpts());
109     if (!SourceLocation::isPairOfFileLocations(Range.getBegin(), End))
110       return SourceSelectionKind::None;
111     if (!SelectionEnd.isValid()) {
112       // Do a quick check when the selection is of length 0.
113       if (SM.isPointWithin(SelectionBegin, Range.getBegin(), End))
114         return SourceSelectionKind::ContainsSelection;
115       return SourceSelectionKind::None;
116     }
117     bool HasStart = SM.isPointWithin(SelectionBegin, Range.getBegin(), End);
118     bool HasEnd = SM.isPointWithin(SelectionEnd, Range.getBegin(), End);
119     if (HasStart && HasEnd)
120       return SourceSelectionKind::ContainsSelection;
121     if (SM.isPointWithin(Range.getBegin(), SelectionBegin, SelectionEnd) &&
122         SM.isPointWithin(End, SelectionBegin, SelectionEnd))
123       return SourceSelectionKind::InsideSelection;
124     // Ensure there's at least some overlap with the 'start'/'end' selection
125     // types.
126     if (HasStart && SelectionBegin != End)
127       return SourceSelectionKind::ContainsSelectionStart;
128     if (HasEnd && SelectionEnd != Range.getBegin())
129       return SourceSelectionKind::ContainsSelectionEnd;
130 
131     return SourceSelectionKind::None;
132   }
133 
134   const SourceLocation SelectionBegin, SelectionEnd;
135   FileID TargetFile;
136   const ASTContext &Context;
137   std::vector<SelectedASTNode> SelectionStack;
138 };
139 
140 } // end anonymous namespace
141 
142 Optional<SelectedASTNode>
143 clang::tooling::findSelectedASTNodes(const ASTContext &Context,
144                                      SourceRange SelectionRange) {
145   assert(SelectionRange.isValid() &&
146          SourceLocation::isPairOfFileLocations(SelectionRange.getBegin(),
147                                                SelectionRange.getEnd()) &&
148          "Expected a file range");
149   FileID TargetFile =
150       Context.getSourceManager().getFileID(SelectionRange.getBegin());
151   assert(Context.getSourceManager().getFileID(SelectionRange.getEnd()) ==
152              TargetFile &&
153          "selection range must span one file");
154 
155   ASTSelectionFinder Visitor(SelectionRange, TargetFile, Context);
156   Visitor.TraverseDecl(Context.getTranslationUnitDecl());
157   return Visitor.getSelectedASTNode();
158 }
159 
160 static const char *selectionKindToString(SourceSelectionKind Kind) {
161   switch (Kind) {
162   case SourceSelectionKind::None:
163     return "none";
164   case SourceSelectionKind::ContainsSelection:
165     return "contains-selection";
166   case SourceSelectionKind::ContainsSelectionStart:
167     return "contains-selection-start";
168   case SourceSelectionKind::ContainsSelectionEnd:
169     return "contains-selection-end";
170   case SourceSelectionKind::InsideSelection:
171     return "inside";
172   }
173   llvm_unreachable("invalid selection kind");
174 }
175 
176 static void dump(const SelectedASTNode &Node, llvm::raw_ostream &OS,
177                  unsigned Indent = 0) {
178   OS.indent(Indent * 2);
179   if (const Decl *D = Node.Node.get<Decl>()) {
180     OS << D->getDeclKindName() << "Decl";
181     if (const auto *ND = dyn_cast<NamedDecl>(D))
182       OS << " \"" << ND->getNameAsString() << '"';
183   } else if (const Stmt *S = Node.Node.get<Stmt>()) {
184     OS << S->getStmtClassName();
185   }
186   OS << ' ' << selectionKindToString(Node.SelectionKind) << "\n";
187   for (const auto &Child : Node.Children)
188     dump(Child, OS, Indent + 1);
189 }
190 
191 void SelectedASTNode::dump(llvm::raw_ostream &OS) const { ::dump(*this, OS); }
192