• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===--- Selection.cpp ----------------------------------------------------===//
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-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "Selection.h"
10 #include "SourceCode.h"
11 #include "support/Logger.h"
12 #include "support/Trace.h"
13 #include "clang/AST/ASTTypeTraits.h"
14 #include "clang/AST/Decl.h"
15 #include "clang/AST/DeclCXX.h"
16 #include "clang/AST/Expr.h"
17 #include "clang/AST/ExprCXX.h"
18 #include "clang/AST/PrettyPrinter.h"
19 #include "clang/AST/RecursiveASTVisitor.h"
20 #include "clang/AST/TypeLoc.h"
21 #include "clang/Basic/OperatorKinds.h"
22 #include "clang/Basic/SourceLocation.h"
23 #include "clang/Basic/SourceManager.h"
24 #include "clang/Basic/TokenKinds.h"
25 #include "clang/Lex/Lexer.h"
26 #include "clang/Tooling/Syntax/Tokens.h"
27 #include "llvm/ADT/STLExtras.h"
28 #include "llvm/ADT/StringExtras.h"
29 #include "llvm/Support/Casting.h"
30 #include "llvm/Support/raw_ostream.h"
31 #include <algorithm>
32 #include <string>
33 
34 namespace clang {
35 namespace clangd {
36 namespace {
37 using Node = SelectionTree::Node;
38 using ast_type_traits::DynTypedNode;
39 
40 // Measure the fraction of selections that were enabled by recovery AST.
recordMetrics(const SelectionTree & S,const LangOptions & Lang)41 void recordMetrics(const SelectionTree &S, const LangOptions &Lang) {
42   if (!trace::enabled())
43     return;
44   const char *LanguageLabel = Lang.CPlusPlus ? "C++" : Lang.ObjC ? "ObjC" : "C";
45   static constexpr trace::Metric SelectionUsedRecovery(
46       "selection_recovery", trace::Metric::Distribution, "language");
47   static constexpr trace::Metric RecoveryType(
48       "selection_recovery_type", trace::Metric::Distribution, "language");
49   const auto *Common = S.commonAncestor();
50   for (const auto *N = Common; N; N = N->Parent) {
51     if (const auto *RE = N->ASTNode.get<RecoveryExpr>()) {
52       SelectionUsedRecovery.record(1, LanguageLabel); // used recovery ast.
53       RecoveryType.record(RE->isTypeDependent() ? 0 : 1, LanguageLabel);
54       return;
55     }
56   }
57   if (Common)
58     SelectionUsedRecovery.record(0, LanguageLabel); // unused.
59 }
60 
61 // An IntervalSet maintains a set of disjoint subranges of an array.
62 //
63 // Initially, it contains the entire array.
64 //           [-----------------------------------------------------------]
65 //
66 // When a range is erased(), it will typically split the array in two.
67 //  Claim:                     [--------------------]
68 //  after:   [----------------]                      [-------------------]
69 //
70 // erase() returns the segments actually erased. Given the state above:
71 //  Claim:          [---------------------------------------]
72 //  Out:            [---------]                      [------]
73 //  After:   [-----]                                         [-----------]
74 //
75 // It is used to track (expanded) tokens not yet associated with an AST node.
76 // On traversing an AST node, its token range is erased from the unclaimed set.
77 // The tokens actually removed are associated with that node, and hit-tested
78 // against the selection to determine whether the node is selected.
79 template <typename T> class IntervalSet {
80 public:
IntervalSet(llvm::ArrayRef<T> Range)81   IntervalSet(llvm::ArrayRef<T> Range) { UnclaimedRanges.insert(Range); }
82 
83   // Removes the elements of Claim from the set, modifying or removing ranges
84   // that overlap it.
85   // Returns the continuous subranges of Claim that were actually removed.
erase(llvm::ArrayRef<T> Claim)86   llvm::SmallVector<llvm::ArrayRef<T>, 4> erase(llvm::ArrayRef<T> Claim) {
87     llvm::SmallVector<llvm::ArrayRef<T>, 4> Out;
88     if (Claim.empty())
89       return Out;
90 
91     // General case:
92     // Claim:                   [-----------------]
93     // UnclaimedRanges: [-A-] [-B-] [-C-] [-D-] [-E-] [-F-] [-G-]
94     // Overlap:               ^first                  ^second
95     // Ranges C and D are fully included. Ranges B and E must be trimmed.
96     auto Overlap = std::make_pair(
97         UnclaimedRanges.lower_bound({Claim.begin(), Claim.begin()}), // C
98         UnclaimedRanges.lower_bound({Claim.end(), Claim.end()}));    // F
99     // Rewind to cover B.
100     if (Overlap.first != UnclaimedRanges.begin()) {
101       --Overlap.first;
102       // ...unless B isn't selected at all.
103       if (Overlap.first->end() <= Claim.begin())
104         ++Overlap.first;
105     }
106     if (Overlap.first == Overlap.second)
107       return Out;
108 
109     // First, copy all overlapping ranges into the output.
110     auto OutFirst = Out.insert(Out.end(), Overlap.first, Overlap.second);
111     // If any of the overlapping ranges were sliced by the claim, split them:
112     //  - restrict the returned range to the claimed part
113     //  - save the unclaimed part so it can be reinserted
114     llvm::ArrayRef<T> RemainingHead, RemainingTail;
115     if (Claim.begin() > OutFirst->begin()) {
116       RemainingHead = {OutFirst->begin(), Claim.begin()};
117       *OutFirst = {Claim.begin(), OutFirst->end()};
118     }
119     if (Claim.end() < Out.back().end()) {
120       RemainingTail = {Claim.end(), Out.back().end()};
121       Out.back() = {Out.back().begin(), Claim.end()};
122     }
123 
124     // Erase all the overlapping ranges (invalidating all iterators).
125     UnclaimedRanges.erase(Overlap.first, Overlap.second);
126     // Reinsert ranges that were merely trimmed.
127     if (!RemainingHead.empty())
128       UnclaimedRanges.insert(RemainingHead);
129     if (!RemainingTail.empty())
130       UnclaimedRanges.insert(RemainingTail);
131 
132     return Out;
133   }
134 
135 private:
136   using TokenRange = llvm::ArrayRef<T>;
137   struct RangeLess {
operator ()clang::clangd::__anonba3019980111::IntervalSet::RangeLess138     bool operator()(llvm::ArrayRef<T> L, llvm::ArrayRef<T> R) const {
139       return L.begin() < R.begin();
140     }
141   };
142 
143   // Disjoint sorted unclaimed ranges of expanded tokens.
144   std::set<llvm::ArrayRef<T>, RangeLess> UnclaimedRanges;
145 };
146 
147 // Sentinel value for the selectedness of a node where we've seen no tokens yet.
148 // This resolves to Unselected if no tokens are ever seen.
149 // But Unselected + Complete -> Partial, while NoTokens + Complete --> Complete.
150 // This value is never exposed publicly.
151 constexpr SelectionTree::Selection NoTokens =
152     static_cast<SelectionTree::Selection>(
153         static_cast<unsigned char>(SelectionTree::Complete + 1));
154 
155 // Nodes start with NoTokens, and then use this function to aggregate the
156 // selectedness as more tokens are found.
update(SelectionTree::Selection & Result,SelectionTree::Selection New)157 void update(SelectionTree::Selection &Result, SelectionTree::Selection New) {
158   if (New == NoTokens)
159     return;
160   if (Result == NoTokens)
161     Result = New;
162   else if (Result != New)
163     // Can only be completely selected (or unselected) if all tokens are.
164     Result = SelectionTree::Partial;
165 }
166 
167 // As well as comments, don't count semicolons as real tokens.
168 // They're not properly claimed as expr-statement is missing from the AST.
shouldIgnore(const syntax::Token & Tok)169 bool shouldIgnore(const syntax::Token &Tok) {
170   return Tok.kind() == tok::comment || Tok.kind() == tok::semi;
171 }
172 
173 // Determine whether 'Target' is the first expansion of the macro
174 // argument whose top-level spelling location is 'SpellingLoc'.
isFirstExpansion(FileID Target,SourceLocation SpellingLoc,const SourceManager & SM)175 bool isFirstExpansion(FileID Target, SourceLocation SpellingLoc,
176                       const SourceManager &SM) {
177   SourceLocation Prev = SpellingLoc;
178   while (true) {
179     // If the arg is expanded multiple times, getMacroArgExpandedLocation()
180     // returns the first expansion.
181     SourceLocation Next = SM.getMacroArgExpandedLocation(Prev);
182     // So if we reach the target, target is the first-expansion of the
183     // first-expansion ...
184     if (SM.getFileID(Next) == Target)
185       return true;
186 
187     // Otherwise, if the FileID stops changing, we've reached the innermost
188     // macro expansion, and Target was on a different branch.
189     if (SM.getFileID(Next) == SM.getFileID(Prev))
190       return false;
191 
192     Prev = Next;
193   }
194   return false;
195 }
196 
197 // SelectionTester can determine whether a range of tokens from the PP-expanded
198 // stream (corresponding to an AST node) is considered selected.
199 //
200 // When the tokens result from macro expansions, the appropriate tokens in the
201 // main file are examined (macro invocation or args). Similarly for #includes.
202 // However, only the first expansion of a given spelled token is considered
203 // selected.
204 //
205 // It tests each token in the range (not just the endpoints) as contiguous
206 // expanded tokens may not have contiguous spellings (with macros).
207 //
208 // Non-token text, and tokens not modeled in the AST (comments, semicolons)
209 // are ignored when determining selectedness.
210 class SelectionTester {
211 public:
212   // The selection is offsets [SelBegin, SelEnd) in SelFile.
SelectionTester(const syntax::TokenBuffer & Buf,FileID SelFile,unsigned SelBegin,unsigned SelEnd,const SourceManager & SM)213   SelectionTester(const syntax::TokenBuffer &Buf, FileID SelFile,
214                   unsigned SelBegin, unsigned SelEnd, const SourceManager &SM)
215       : SelFile(SelFile), SM(SM) {
216     // Find all tokens (partially) selected in the file.
217     auto AllSpelledTokens = Buf.spelledTokens(SelFile);
218     const syntax::Token *SelFirst =
219         llvm::partition_point(AllSpelledTokens, [&](const syntax::Token &Tok) {
220           return SM.getFileOffset(Tok.endLocation()) <= SelBegin;
221         });
222     const syntax::Token *SelLimit = std::partition_point(
223         SelFirst, AllSpelledTokens.end(), [&](const syntax::Token &Tok) {
224           return SM.getFileOffset(Tok.location()) < SelEnd;
225         });
226     auto Sel = llvm::makeArrayRef(SelFirst, SelLimit);
227     // Find which of these are preprocessed to nothing and should be ignored.
228     std::vector<bool> PPIgnored(Sel.size(), false);
229     for (const syntax::TokenBuffer::Expansion &X :
230          Buf.expansionsOverlapping(Sel)) {
231       if (X.Expanded.empty()) {
232         for (const syntax::Token &Tok : X.Spelled) {
233           if (&Tok >= SelFirst && &Tok < SelLimit)
234             PPIgnored[&Tok - SelFirst] = true;
235         }
236       }
237     }
238     // Precompute selectedness and offset for selected spelled tokens.
239     for (unsigned I = 0; I < Sel.size(); ++I) {
240       if (shouldIgnore(Sel[I]) || PPIgnored[I])
241         continue;
242       SpelledTokens.emplace_back();
243       Tok &S = SpelledTokens.back();
244       S.Offset = SM.getFileOffset(Sel[I].location());
245       if (S.Offset >= SelBegin && S.Offset + Sel[I].length() <= SelEnd)
246         S.Selected = SelectionTree::Complete;
247       else
248         S.Selected = SelectionTree::Partial;
249     }
250   }
251 
252   // Test whether a consecutive range of tokens is selected.
253   // The tokens are taken from the expanded token stream.
254   SelectionTree::Selection
test(llvm::ArrayRef<syntax::Token> ExpandedTokens) const255   test(llvm::ArrayRef<syntax::Token> ExpandedTokens) const {
256     if (SpelledTokens.empty())
257       return NoTokens;
258     SelectionTree::Selection Result = NoTokens;
259     while (!ExpandedTokens.empty()) {
260       // Take consecutive tokens from the same context together for efficiency.
261       FileID FID = SM.getFileID(ExpandedTokens.front().location());
262       auto Batch = ExpandedTokens.take_while([&](const syntax::Token &T) {
263         return SM.getFileID(T.location()) == FID;
264       });
265       assert(!Batch.empty());
266       ExpandedTokens = ExpandedTokens.drop_front(Batch.size());
267 
268       update(Result, testChunk(FID, Batch));
269     }
270     return Result;
271   }
272 
273   // Cheap check whether any of the tokens in R might be selected.
274   // If it returns false, test() will return NoTokens or Unselected.
275   // If it returns true, test() may return any value.
mayHit(SourceRange R) const276   bool mayHit(SourceRange R) const {
277     if (SpelledTokens.empty())
278       return false;
279     auto B = SM.getDecomposedLoc(R.getBegin());
280     auto E = SM.getDecomposedLoc(R.getEnd());
281     if (B.first == SelFile && E.first == SelFile)
282       if (E.second < SpelledTokens.front().Offset ||
283           B.second > SpelledTokens.back().Offset)
284         return false;
285     return true;
286   }
287 
288 private:
289   // Hit-test a consecutive range of tokens from a single file ID.
290   SelectionTree::Selection
testChunk(FileID FID,llvm::ArrayRef<syntax::Token> Batch) const291   testChunk(FileID FID, llvm::ArrayRef<syntax::Token> Batch) const {
292     assert(!Batch.empty());
293     SourceLocation StartLoc = Batch.front().location();
294     // There are several possible categories of FileID depending on how the
295     // preprocessor was used to generate these tokens:
296     //   main file, #included file, macro args, macro bodies.
297     // We need to identify the main-file tokens that represent Batch, and
298     // determine whether we want to exclusively claim them. Regular tokens
299     // represent one AST construct, but a macro invocation can represent many.
300 
301     // Handle tokens written directly in the main file.
302     if (FID == SelFile) {
303       return testTokenRange(SM.getFileOffset(Batch.front().location()),
304                             SM.getFileOffset(Batch.back().location()));
305     }
306 
307     // Handle tokens in another file #included into the main file.
308     // Check if the #include is selected, but don't claim it exclusively.
309     if (StartLoc.isFileID()) {
310       for (SourceLocation Loc = Batch.front().location(); Loc.isValid();
311            Loc = SM.getIncludeLoc(SM.getFileID(Loc))) {
312         if (SM.getFileID(Loc) == SelFile)
313           // FIXME: use whole #include directive, not just the filename string.
314           return testToken(SM.getFileOffset(Loc));
315       }
316       return NoTokens;
317     }
318 
319     assert(StartLoc.isMacroID());
320     // Handle tokens that were passed as a macro argument.
321     SourceLocation ArgStart = SM.getTopMacroCallerLoc(StartLoc);
322     if (SM.getFileID(ArgStart) == SelFile) {
323       if (isFirstExpansion(FID, ArgStart, SM)) {
324         SourceLocation ArgEnd =
325             SM.getTopMacroCallerLoc(Batch.back().location());
326         return testTokenRange(SM.getFileOffset(ArgStart),
327                               SM.getFileOffset(ArgEnd));
328       } else {
329         /* fall through and treat as part of the macro body */
330       }
331     }
332 
333     // Handle tokens produced by non-argument macro expansion.
334     // Check if the macro name is selected, don't claim it exclusively.
335     auto Expansion = SM.getDecomposedExpansionLoc(StartLoc);
336     if (Expansion.first == SelFile)
337       // FIXME: also check ( and ) for function-like macros?
338       return testToken(Expansion.second);
339     else
340       return NoTokens;
341   }
342 
343   // Is the closed token range [Begin, End] selected?
testTokenRange(unsigned Begin,unsigned End) const344   SelectionTree::Selection testTokenRange(unsigned Begin, unsigned End) const {
345     assert(Begin <= End);
346     // Outside the selection entirely?
347     if (End < SpelledTokens.front().Offset ||
348         Begin > SpelledTokens.back().Offset)
349       return SelectionTree::Unselected;
350 
351     // Compute range of tokens.
352     auto B = llvm::partition_point(
353         SpelledTokens, [&](const Tok &T) { return T.Offset < Begin; });
354     auto E = std::partition_point(
355         B, SpelledTokens.end(), [&](const Tok &T) { return T.Offset <= End; });
356 
357     // Aggregate selectedness of tokens in range.
358     bool ExtendsOutsideSelection = Begin < SpelledTokens.front().Offset ||
359                                    End > SpelledTokens.back().Offset;
360     SelectionTree::Selection Result =
361         ExtendsOutsideSelection ? SelectionTree::Unselected : NoTokens;
362     for (auto It = B; It != E; ++It)
363       update(Result, It->Selected);
364     return Result;
365   }
366 
367   // Is the token at `Offset` selected?
testToken(unsigned Offset) const368   SelectionTree::Selection testToken(unsigned Offset) const {
369     // Outside the selection entirely?
370     if (Offset < SpelledTokens.front().Offset ||
371         Offset > SpelledTokens.back().Offset)
372       return SelectionTree::Unselected;
373     // Find the token, if it exists.
374     auto It = llvm::partition_point(
375         SpelledTokens, [&](const Tok &T) { return T.Offset < Offset; });
376     if (It != SpelledTokens.end() && It->Offset == Offset)
377       return It->Selected;
378     return NoTokens;
379   }
380 
381   struct Tok {
382     unsigned Offset;
383     SelectionTree::Selection Selected;
384   };
385   std::vector<Tok> SpelledTokens;
386   FileID SelFile;
387   const SourceManager &SM;
388 };
389 
390 // Show the type of a node for debugging.
printNodeKind(llvm::raw_ostream & OS,const DynTypedNode & N)391 void printNodeKind(llvm::raw_ostream &OS, const DynTypedNode &N) {
392   if (const TypeLoc *TL = N.get<TypeLoc>()) {
393     // TypeLoc is a hierarchy, but has only a single ASTNodeKind.
394     // Synthesize the name from the Type subclass (except for QualifiedTypeLoc).
395     if (TL->getTypeLocClass() == TypeLoc::Qualified)
396       OS << "QualifiedTypeLoc";
397     else
398       OS << TL->getType()->getTypeClassName() << "TypeLoc";
399   } else {
400     OS << N.getNodeKind().asStringRef();
401   }
402 }
403 
404 #ifndef NDEBUG
printNodeToString(const DynTypedNode & N,const PrintingPolicy & PP)405 std::string printNodeToString(const DynTypedNode &N, const PrintingPolicy &PP) {
406   std::string S;
407   llvm::raw_string_ostream OS(S);
408   printNodeKind(OS, N);
409   OS << " ";
410   return std::move(OS.str());
411 }
412 #endif
413 
isImplicit(const Stmt * S)414 bool isImplicit(const Stmt *S) {
415   // Some Stmts are implicit and shouldn't be traversed, but there's no
416   // "implicit" attribute on Stmt/Expr.
417   // Unwrap implicit casts first if present (other nodes too?).
418   if (auto *ICE = llvm::dyn_cast<ImplicitCastExpr>(S))
419     S = ICE->getSubExprAsWritten();
420   // Implicit this in a MemberExpr is not filtered out by RecursiveASTVisitor.
421   // It would be nice if RAV handled this (!shouldTraverseImplicitCode()).
422   if (auto *CTI = llvm::dyn_cast<CXXThisExpr>(S))
423     if (CTI->isImplicit())
424       return true;
425   // Refs to operator() and [] are (almost?) always implicit as part of calls.
426   if (auto *DRE = llvm::dyn_cast<DeclRefExpr>(S)) {
427     if (auto *FD = llvm::dyn_cast<FunctionDecl>(DRE->getDecl())) {
428       switch (FD->getOverloadedOperator()) {
429       case OO_Call:
430       case OO_Subscript:
431         return true;
432       default:
433         break;
434       }
435     }
436   }
437   return false;
438 }
439 
440 // We find the selection by visiting written nodes in the AST, looking for nodes
441 // that intersect with the selected character range.
442 //
443 // While traversing, we maintain a parent stack. As nodes pop off the stack,
444 // we decide whether to keep them or not. To be kept, they must either be
445 // selected or contain some nodes that are.
446 //
447 // For simple cases (not inside macros) we prune subtrees that don't intersect.
448 class SelectionVisitor : public RecursiveASTVisitor<SelectionVisitor> {
449 public:
450   // Runs the visitor to gather selected nodes and their ancestors.
451   // If there is any selection, the root (TUDecl) is the first node.
collect(ASTContext & AST,const syntax::TokenBuffer & Tokens,const PrintingPolicy & PP,unsigned Begin,unsigned End,FileID File)452   static std::deque<Node> collect(ASTContext &AST,
453                                   const syntax::TokenBuffer &Tokens,
454                                   const PrintingPolicy &PP, unsigned Begin,
455                                   unsigned End, FileID File) {
456     SelectionVisitor V(AST, Tokens, PP, Begin, End, File);
457     V.TraverseAST(AST);
458     assert(V.Stack.size() == 1 && "Unpaired push/pop?");
459     assert(V.Stack.top() == &V.Nodes.front());
460     return std::move(V.Nodes);
461   }
462 
463   // We traverse all "well-behaved" nodes the same way:
464   //  - push the node onto the stack
465   //  - traverse its children recursively
466   //  - pop it from the stack
467   //  - hit testing: is intersection(node, selection) - union(children) empty?
468   //  - attach it to the tree if it or any children hit the selection
469   //
470   // Two categories of nodes are not "well-behaved":
471   //  - those without source range information, we don't record those
472   //  - those that can't be stored in DynTypedNode.
473   // We're missing some interesting things like Attr due to the latter.
TraverseDecl(Decl * X)474   bool TraverseDecl(Decl *X) {
475     if (X && isa<TranslationUnitDecl>(X))
476       return Base::TraverseDecl(X); // Already pushed by constructor.
477     // Base::TraverseDecl will suppress children, but not this node itself.
478     if (X && X->isImplicit())
479       return true;
480     return traverseNode(X, [&] { return Base::TraverseDecl(X); });
481   }
TraverseTypeLoc(TypeLoc X)482   bool TraverseTypeLoc(TypeLoc X) {
483     return traverseNode(&X, [&] { return Base::TraverseTypeLoc(X); });
484   }
TraverseTemplateArgumentLoc(const TemplateArgumentLoc & X)485   bool TraverseTemplateArgumentLoc(const TemplateArgumentLoc &X) {
486     return traverseNode(&X,
487                         [&] { return Base::TraverseTemplateArgumentLoc(X); });
488   }
TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc X)489   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc X) {
490     return traverseNode(
491         &X, [&] { return Base::TraverseNestedNameSpecifierLoc(X); });
492   }
TraverseConstructorInitializer(CXXCtorInitializer * X)493   bool TraverseConstructorInitializer(CXXCtorInitializer *X) {
494     return traverseNode(
495         X, [&] { return Base::TraverseConstructorInitializer(X); });
496   }
497   // Stmt is the same, but this form allows the data recursion optimization.
dataTraverseStmtPre(Stmt * X)498   bool dataTraverseStmtPre(Stmt *X) {
499     if (!X || isImplicit(X))
500       return false;
501     auto N = DynTypedNode::create(*X);
502     if (canSafelySkipNode(N))
503       return false;
504     push(std::move(N));
505     if (shouldSkipChildren(X)) {
506       pop();
507       return false;
508     }
509     return true;
510   }
dataTraverseStmtPost(Stmt * X)511   bool dataTraverseStmtPost(Stmt *X) {
512     pop();
513     return true;
514   }
515   // QualifiedTypeLoc is handled strangely in RecursiveASTVisitor: the derived
516   // TraverseTypeLoc is not called for the inner UnqualTypeLoc.
517   // This means we'd never see 'int' in 'const int'! Work around that here.
518   // (The reason for the behavior is to avoid traversing the nested Type twice,
519   // but we ignore TraverseType anyway).
TraverseQualifiedTypeLoc(QualifiedTypeLoc QX)520   bool TraverseQualifiedTypeLoc(QualifiedTypeLoc QX) {
521     return traverseNode<TypeLoc>(
522         &QX, [&] { return TraverseTypeLoc(QX.getUnqualifiedLoc()); });
523   }
524   // Uninteresting parts of the AST that don't have locations within them.
TraverseNestedNameSpecifier(NestedNameSpecifier *)525   bool TraverseNestedNameSpecifier(NestedNameSpecifier *) { return true; }
TraverseType(QualType)526   bool TraverseType(QualType) { return true; }
527 
528   // The DeclStmt for the loop variable claims to cover the whole range
529   // inside the parens, this causes the range-init expression to not be hit.
530   // Traverse the loop VarDecl instead, which has the right source range.
TraverseCXXForRangeStmt(CXXForRangeStmt * S)531   bool TraverseCXXForRangeStmt(CXXForRangeStmt *S) {
532     return traverseNode(S, [&] {
533       return TraverseStmt(S->getInit()) && TraverseDecl(S->getLoopVariable()) &&
534              TraverseStmt(S->getRangeInit()) && TraverseStmt(S->getBody());
535     });
536   }
537   // OpaqueValueExpr blocks traversal, we must explicitly traverse it.
TraverseOpaqueValueExpr(OpaqueValueExpr * E)538   bool TraverseOpaqueValueExpr(OpaqueValueExpr *E) {
539     return traverseNode(E, [&] { return TraverseStmt(E->getSourceExpr()); });
540   }
541   // We only want to traverse the *syntactic form* to understand the selection.
TraversePseudoObjectExpr(PseudoObjectExpr * E)542   bool TraversePseudoObjectExpr(PseudoObjectExpr *E) {
543     return traverseNode(E, [&] { return TraverseStmt(E->getSyntacticForm()); });
544   }
545 
546 private:
547   using Base = RecursiveASTVisitor<SelectionVisitor>;
548 
SelectionVisitor(ASTContext & AST,const syntax::TokenBuffer & Tokens,const PrintingPolicy & PP,unsigned SelBegin,unsigned SelEnd,FileID SelFile)549   SelectionVisitor(ASTContext &AST, const syntax::TokenBuffer &Tokens,
550                    const PrintingPolicy &PP, unsigned SelBegin, unsigned SelEnd,
551                    FileID SelFile)
552       : SM(AST.getSourceManager()), LangOpts(AST.getLangOpts()),
553 #ifndef NDEBUG
554         PrintPolicy(PP),
555 #endif
556         TokenBuf(Tokens), SelChecker(Tokens, SelFile, SelBegin, SelEnd, SM),
557         UnclaimedExpandedTokens(Tokens.expandedTokens()) {
558     // Ensure we have a node for the TU decl, regardless of traversal scope.
559     Nodes.emplace_back();
560     Nodes.back().ASTNode = DynTypedNode::create(*AST.getTranslationUnitDecl());
561     Nodes.back().Parent = nullptr;
562     Nodes.back().Selected = SelectionTree::Unselected;
563     Stack.push(&Nodes.back());
564   }
565 
566   // Generic case of TraverseFoo. Func should be the call to Base::TraverseFoo.
567   // Node is always a pointer so the generic code can handle any null checks.
568   template <typename T, typename Func>
traverseNode(T * Node,const Func & Body)569   bool traverseNode(T *Node, const Func &Body) {
570     if (Node == nullptr)
571       return true;
572     auto N = DynTypedNode::create(*Node);
573     if (canSafelySkipNode(N))
574       return true;
575     push(DynTypedNode::create(*Node));
576     bool Ret = Body();
577     pop();
578     return Ret;
579   }
580 
581   // HIT TESTING
582   //
583   // We do rough hit testing on the way down the tree to avoid traversing
584   // subtrees that don't touch the selection (canSafelySkipNode), but
585   // fine-grained hit-testing is mostly done on the way back up (in pop()).
586   // This means children get to claim parts of the selection first, and parents
587   // are only selected if they own tokens that no child owned.
588   //
589   // Nodes *usually* nest nicely: a child's getSourceRange() lies within the
590   // parent's, and a node (transitively) owns all tokens in its range.
591   //
592   // Exception 1: child range claims tokens that should be owned by the parent.
593   //              e.g. in `void foo(int);`, the FunctionTypeLoc should own
594   //              `void (int)` but the parent FunctionDecl should own `foo`.
595   // To handle this case, certain nodes claim small token ranges *before*
596   // their children are traversed. (see earlySourceRange).
597   //
598   // Exception 2: siblings both claim the same node.
599   //              e.g. `int x, y;` produces two sibling VarDecls.
600   //                    ~~~~~ x
601   //                    ~~~~~~~~ y
602   // Here the first ("leftmost") sibling claims the tokens it wants, and the
603   // other sibling gets what's left. So selecting "int" only includes the left
604   // VarDecl in the selection tree.
605 
606   // An optimization for a common case: nodes outside macro expansions that
607   // don't intersect the selection may be recursively skipped.
canSafelySkipNode(const DynTypedNode & N)608   bool canSafelySkipNode(const DynTypedNode &N) {
609     SourceRange S = N.getSourceRange();
610     if (auto *TL = N.get<TypeLoc>()) {
611       // FIXME: TypeLoc::getBeginLoc()/getEndLoc() are pretty fragile
612       // heuristics. We should consider only pruning critical TypeLoc nodes, to
613       // be more robust.
614 
615       // DeclTypeTypeLoc::getSourceRange() is incomplete, which would lead to
616       // failing
617       // to descend into the child expression.
618       // decltype(2+2);
619       // ~~~~~~~~~~~~~ <-- correct range
620       // ~~~~~~~~      <-- range reported by getSourceRange()
621       // ~~~~~~~~~~~~  <-- range with this hack(i.e, missing closing paren)
622       // FIXME: Alter DecltypeTypeLoc to contain parentheses locations and get
623       // rid of this patch.
624       if (auto DT = TL->getAs<DecltypeTypeLoc>())
625         S.setEnd(DT.getUnderlyingExpr()->getEndLoc());
626       // AttributedTypeLoc may point to the attribute's range, NOT the modified
627       // type's range.
628       if (auto AT = TL->getAs<AttributedTypeLoc>())
629         S = AT.getModifiedLoc().getSourceRange();
630     }
631     if (!SelChecker.mayHit(S)) {
632       dlog("{1}skip: {0}", printNodeToString(N, PrintPolicy), indent());
633       dlog("{1}skipped range = {0}", S.printToString(SM), indent(1));
634       return true;
635     }
636     return false;
637   }
638 
639   // There are certain nodes we want to treat as leaves in the SelectionTree,
640   // although they do have children.
shouldSkipChildren(const Stmt * X) const641   bool shouldSkipChildren(const Stmt *X) const {
642     // UserDefinedLiteral (e.g. 12_i) has two children (12 and _i).
643     // Unfortunately TokenBuffer sees 12_i as one token and can't split it.
644     // So we treat UserDefinedLiteral as a leaf node, owning the token.
645     return llvm::isa<UserDefinedLiteral>(X);
646   }
647 
648   // Pushes a node onto the ancestor stack. Pairs with pop().
649   // Performs early hit detection for some nodes (on the earlySourceRange).
push(DynTypedNode Node)650   void push(DynTypedNode Node) {
651     SourceRange Early = earlySourceRange(Node);
652     dlog("{1}push: {0}", printNodeToString(Node, PrintPolicy), indent());
653     Nodes.emplace_back();
654     Nodes.back().ASTNode = std::move(Node);
655     Nodes.back().Parent = Stack.top();
656     Nodes.back().Selected = NoTokens;
657     Stack.push(&Nodes.back());
658     claimRange(Early, Nodes.back().Selected);
659   }
660 
661   // Pops a node off the ancestor stack, and finalizes it. Pairs with push().
662   // Performs primary hit detection.
pop()663   void pop() {
664     Node &N = *Stack.top();
665     dlog("{1}pop: {0}", printNodeToString(N.ASTNode, PrintPolicy), indent(-1));
666     claimRange(N.ASTNode.getSourceRange(), N.Selected);
667     if (N.Selected == NoTokens)
668       N.Selected = SelectionTree::Unselected;
669     if (N.Selected || !N.Children.empty()) {
670       // Attach to the tree.
671       N.Parent->Children.push_back(&N);
672     } else {
673       // Neither N any children are selected, it doesn't belong in the tree.
674       assert(&N == &Nodes.back());
675       Nodes.pop_back();
676     }
677     Stack.pop();
678   }
679 
680   // Returns the range of tokens that this node will claim directly, and
681   // is not available to the node's children.
682   // Usually empty, but sometimes children cover tokens but shouldn't own them.
earlySourceRange(const DynTypedNode & N)683   SourceRange earlySourceRange(const DynTypedNode &N) {
684     if (const Decl *D = N.get<Decl>()) {
685       // We want constructor name to be claimed by TypeLoc not the constructor
686       // itself. Similar for deduction guides, we rather want to select the
687       // underlying TypeLoc.
688       // FIXME: Unfortunately this doesn't work, even though RecursiveASTVisitor
689       // traverses the underlying TypeLoc inside DeclarationName, it is null for
690       // constructors.
691       if (isa<CXXConstructorDecl>(D) || isa<CXXDeductionGuideDecl>(D))
692         return SourceRange();
693       // This will capture Field, Function, MSProperty, NonTypeTemplateParm and
694       // VarDecls. We want the name in the declarator to be claimed by the decl
695       // and not by any children. For example:
696       // void [[foo]]();
697       // int (*[[s]])();
698       // struct X { int [[hash]] [32]; [[operator]] int();}
699       if (const auto *DD = llvm::dyn_cast<DeclaratorDecl>(D))
700         return DD->getLocation();
701     } else if (const auto *CCI = N.get<CXXCtorInitializer>()) {
702       // : [[b_]](42)
703       return CCI->getMemberLocation();
704     }
705     return SourceRange();
706   }
707 
708   // Perform hit-testing of a complete Node against the selection.
709   // This runs for every node in the AST, and must be fast in common cases.
710   // This is usually called from pop(), so we can take children into account.
711   // The existing state of Result is relevant (early/late claims can interact).
claimRange(SourceRange S,SelectionTree::Selection & Result)712   void claimRange(SourceRange S, SelectionTree::Selection &Result) {
713     for (const auto &ClaimedRange :
714          UnclaimedExpandedTokens.erase(TokenBuf.expandedTokens(S)))
715       update(Result, SelChecker.test(ClaimedRange));
716 
717     if (Result && Result != NoTokens)
718       dlog("{1}hit selection: {0}", S.printToString(SM), indent());
719   }
720 
indent(int Offset=0)721   std::string indent(int Offset = 0) {
722     // Cast for signed arithmetic.
723     int Amount = int(Stack.size()) + Offset;
724     assert(Amount >= 0);
725     return std::string(Amount, ' ');
726   }
727 
728   SourceManager &SM;
729   const LangOptions &LangOpts;
730 #ifndef NDEBUG
731   const PrintingPolicy &PrintPolicy;
732 #endif
733   const syntax::TokenBuffer &TokenBuf;
734   std::stack<Node *> Stack;
735   SelectionTester SelChecker;
736   IntervalSet<syntax::Token> UnclaimedExpandedTokens;
737   std::deque<Node> Nodes; // Stable pointers as we add more nodes.
738 };
739 
740 } // namespace
741 
abbreviatedString(DynTypedNode N,const PrintingPolicy & PP)742 llvm::SmallString<256> abbreviatedString(DynTypedNode N,
743                                          const PrintingPolicy &PP) {
744   llvm::SmallString<256> Result;
745   {
746     llvm::raw_svector_ostream OS(Result);
747     N.print(OS, PP);
748   }
749   auto Pos = Result.find('\n');
750   if (Pos != llvm::StringRef::npos) {
751     bool MoreText =
752         !llvm::all_of(llvm::StringRef(Result).drop_front(Pos), llvm::isSpace);
753     Result.resize(Pos);
754     if (MoreText)
755       Result.append(" …");
756   }
757   return Result;
758 }
759 
print(llvm::raw_ostream & OS,const SelectionTree::Node & N,int Indent) const760 void SelectionTree::print(llvm::raw_ostream &OS, const SelectionTree::Node &N,
761                           int Indent) const {
762   if (N.Selected)
763     OS.indent(Indent - 1) << (N.Selected == SelectionTree::Complete ? '*'
764                                                                     : '.');
765   else
766     OS.indent(Indent);
767   printNodeKind(OS, N.ASTNode);
768   OS << ' ' << abbreviatedString(N.ASTNode, PrintPolicy) << "\n";
769   for (const Node *Child : N.Children)
770     print(OS, *Child, Indent + 2);
771 }
772 
kind() const773 std::string SelectionTree::Node::kind() const {
774   std::string S;
775   llvm::raw_string_ostream OS(S);
776   printNodeKind(OS, ASTNode);
777   return std::move(OS.str());
778 }
779 
780 // Decide which selections emulate a "point" query in between characters.
781 // If it's ambiguous (the neighboring characters are selectable tokens), returns
782 // both possibilities in preference order.
783 // Always returns at least one range - if no tokens touched, and empty range.
784 static llvm::SmallVector<std::pair<unsigned, unsigned>, 2>
pointBounds(unsigned Offset,const syntax::TokenBuffer & Tokens)785 pointBounds(unsigned Offset, const syntax::TokenBuffer &Tokens) {
786   const auto &SM = Tokens.sourceManager();
787   SourceLocation Loc = SM.getComposedLoc(SM.getMainFileID(), Offset);
788   llvm::SmallVector<std::pair<unsigned, unsigned>, 2> Result;
789   // Prefer right token over left.
790   for (const syntax::Token &Tok :
791        llvm::reverse(spelledTokensTouching(Loc, Tokens))) {
792     if (shouldIgnore(Tok))
793       continue;
794     unsigned Offset = Tokens.sourceManager().getFileOffset(Tok.location());
795     Result.emplace_back(Offset, Offset + Tok.length());
796   }
797   if (Result.empty())
798     Result.emplace_back(Offset, Offset);
799   return Result;
800 }
801 
createEach(ASTContext & AST,const syntax::TokenBuffer & Tokens,unsigned Begin,unsigned End,llvm::function_ref<bool (SelectionTree)> Func)802 bool SelectionTree::createEach(ASTContext &AST,
803                                const syntax::TokenBuffer &Tokens,
804                                unsigned Begin, unsigned End,
805                                llvm::function_ref<bool(SelectionTree)> Func) {
806   if (Begin != End)
807     return Func(SelectionTree(AST, Tokens, Begin, End));
808   for (std::pair<unsigned, unsigned> Bounds : pointBounds(Begin, Tokens))
809     if (Func(SelectionTree(AST, Tokens, Bounds.first, Bounds.second)))
810       return true;
811   return false;
812 }
813 
createRight(ASTContext & AST,const syntax::TokenBuffer & Tokens,unsigned int Begin,unsigned int End)814 SelectionTree SelectionTree::createRight(ASTContext &AST,
815                                          const syntax::TokenBuffer &Tokens,
816                                          unsigned int Begin, unsigned int End) {
817   llvm::Optional<SelectionTree> Result;
818   createEach(AST, Tokens, Begin, End, [&](SelectionTree T) {
819     Result = std::move(T);
820     return true;
821   });
822   return std::move(*Result);
823 }
824 
SelectionTree(ASTContext & AST,const syntax::TokenBuffer & Tokens,unsigned Begin,unsigned End)825 SelectionTree::SelectionTree(ASTContext &AST, const syntax::TokenBuffer &Tokens,
826                              unsigned Begin, unsigned End)
827     : PrintPolicy(AST.getLangOpts()) {
828   // No fundamental reason the selection needs to be in the main file,
829   // but that's all clangd has needed so far.
830   const SourceManager &SM = AST.getSourceManager();
831   FileID FID = SM.getMainFileID();
832   PrintPolicy.TerseOutput = true;
833   PrintPolicy.IncludeNewlines = false;
834 
835   dlog("Computing selection for {0}",
836        SourceRange(SM.getComposedLoc(FID, Begin), SM.getComposedLoc(FID, End))
837            .printToString(SM));
838   Nodes = SelectionVisitor::collect(AST, Tokens, PrintPolicy, Begin, End, FID);
839   Root = Nodes.empty() ? nullptr : &Nodes.front();
840   recordMetrics(*this, AST.getLangOpts());
841   dlog("Built selection tree\n{0}", *this);
842 }
843 
commonAncestor() const844 const Node *SelectionTree::commonAncestor() const {
845   const Node *Ancestor = Root;
846   while (Ancestor->Children.size() == 1 && !Ancestor->Selected)
847     Ancestor = Ancestor->Children.front();
848   // Returning nullptr here is a bit unprincipled, but it makes the API safer:
849   // the TranslationUnitDecl contains all of the preamble, so traversing it is a
850   // performance cliff. Callers can check for null and use root() if they want.
851   return Ancestor != Root ? Ancestor : nullptr;
852 }
853 
getDeclContext() const854 const DeclContext &SelectionTree::Node::getDeclContext() const {
855   for (const Node *CurrentNode = this; CurrentNode != nullptr;
856        CurrentNode = CurrentNode->Parent) {
857     if (const Decl *Current = CurrentNode->ASTNode.get<Decl>()) {
858       if (CurrentNode != this)
859         if (auto *DC = dyn_cast<DeclContext>(Current))
860           return *DC;
861       return *Current->getDeclContext();
862     }
863   }
864   llvm_unreachable("A tree must always be rooted at TranslationUnitDecl.");
865 }
866 
ignoreImplicit() const867 const SelectionTree::Node &SelectionTree::Node::ignoreImplicit() const {
868   if (Children.size() == 1 &&
869       Children.front()->ASTNode.getSourceRange() == ASTNode.getSourceRange())
870     return Children.front()->ignoreImplicit();
871   return *this;
872 }
873 
outerImplicit() const874 const SelectionTree::Node &SelectionTree::Node::outerImplicit() const {
875   if (Parent && Parent->ASTNode.getSourceRange() == ASTNode.getSourceRange())
876     return Parent->outerImplicit();
877   return *this;
878 }
879 
880 } // namespace clangd
881 } // namespace clang
882