clang-tools  16.0.0git
Selection.cpp
Go to the documentation of this file.
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 "AST.h"
11 #include "support/Logger.h"
12 #include "support/Trace.h"
13 #include "clang/AST/ASTConcept.h"
14 #include "clang/AST/ASTTypeTraits.h"
15 #include "clang/AST/Decl.h"
16 #include "clang/AST/DeclCXX.h"
17 #include "clang/AST/Expr.h"
18 #include "clang/AST/ExprCXX.h"
19 #include "clang/AST/PrettyPrinter.h"
20 #include "clang/AST/RecursiveASTVisitor.h"
21 #include "clang/AST/TypeLoc.h"
22 #include "clang/Basic/OperatorKinds.h"
23 #include "clang/Basic/SourceLocation.h"
24 #include "clang/Basic/SourceManager.h"
25 #include "clang/Basic/TokenKinds.h"
26 #include "clang/Lex/Lexer.h"
27 #include "clang/Tooling/Syntax/Tokens.h"
28 #include "llvm/ADT/BitVector.h"
29 #include "llvm/ADT/STLExtras.h"
30 #include "llvm/ADT/StringExtras.h"
31 #include "llvm/Support/Casting.h"
32 #include "llvm/Support/raw_ostream.h"
33 #include <algorithm>
34 #include <set>
35 #include <string>
36 
37 namespace clang {
38 namespace clangd {
39 namespace {
40 using Node = SelectionTree::Node;
41 
42 // Measure the fraction of selections that were enabled by recovery AST.
43 void recordMetrics(const SelectionTree &S, const LangOptions &Lang) {
44  if (!trace::enabled())
45  return;
46  const char *LanguageLabel = Lang.CPlusPlus ? "C++" : Lang.ObjC ? "ObjC" : "C";
47  static constexpr trace::Metric SelectionUsedRecovery(
48  "selection_recovery", trace::Metric::Distribution, "language");
49  static constexpr trace::Metric RecoveryType(
50  "selection_recovery_type", trace::Metric::Distribution, "language");
51  const auto *Common = S.commonAncestor();
52  for (const auto *N = Common; N; N = N->Parent) {
53  if (const auto *RE = N->ASTNode.get<RecoveryExpr>()) {
54  SelectionUsedRecovery.record(1, LanguageLabel); // used recovery ast.
55  RecoveryType.record(RE->isTypeDependent() ? 0 : 1, LanguageLabel);
56  return;
57  }
58  }
59  if (Common)
60  SelectionUsedRecovery.record(0, LanguageLabel); // unused.
61 }
62 
63 // Return the range covering a node and all its children.
64 SourceRange getSourceRange(const DynTypedNode &N) {
65  // MemberExprs to implicitly access anonymous fields should not claim any
66  // tokens for themselves. Given:
67  // struct A { struct { int b; }; };
68  // The clang AST reports the following nodes for an access to b:
69  // A().b;
70  // [----] MemberExpr, base = A().<anonymous>, member = b
71  // [----] MemberExpr: base = A(), member = <anonymous>
72  // [-] CXXConstructExpr
73  // For our purposes, we don't want the second MemberExpr to own any tokens,
74  // so we reduce its range to match the CXXConstructExpr.
75  // (It's not clear that changing the clang AST would be correct in general).
76  if (const auto *ME = N.get<MemberExpr>()) {
77  if (!ME->getMemberDecl()->getDeclName())
78  return ME->getBase()
79  ? getSourceRange(DynTypedNode::create(*ME->getBase()))
80  : SourceRange();
81  }
82  return N.getSourceRange();
83 }
84 
85 // An IntervalSet maintains a set of disjoint subranges of an array.
86 //
87 // Initially, it contains the entire array.
88 // [-----------------------------------------------------------]
89 //
90 // When a range is erased(), it will typically split the array in two.
91 // Claim: [--------------------]
92 // after: [----------------] [-------------------]
93 //
94 // erase() returns the segments actually erased. Given the state above:
95 // Claim: [---------------------------------------]
96 // Out: [---------] [------]
97 // After: [-----] [-----------]
98 //
99 // It is used to track (expanded) tokens not yet associated with an AST node.
100 // On traversing an AST node, its token range is erased from the unclaimed set.
101 // The tokens actually removed are associated with that node, and hit-tested
102 // against the selection to determine whether the node is selected.
103 template <typename T> class IntervalSet {
104 public:
105  IntervalSet(llvm::ArrayRef<T> Range) { UnclaimedRanges.insert(Range); }
106 
107  // Removes the elements of Claim from the set, modifying or removing ranges
108  // that overlap it.
109  // Returns the continuous subranges of Claim that were actually removed.
110  llvm::SmallVector<llvm::ArrayRef<T>> erase(llvm::ArrayRef<T> Claim) {
111  llvm::SmallVector<llvm::ArrayRef<T>> Out;
112  if (Claim.empty())
113  return Out;
114 
115  // General case:
116  // Claim: [-----------------]
117  // UnclaimedRanges: [-A-] [-B-] [-C-] [-D-] [-E-] [-F-] [-G-]
118  // Overlap: ^first ^second
119  // Ranges C and D are fully included. Ranges B and E must be trimmed.
120  auto Overlap = std::make_pair(
121  UnclaimedRanges.lower_bound({Claim.begin(), Claim.begin()}), // C
122  UnclaimedRanges.lower_bound({Claim.end(), Claim.end()})); // F
123  // Rewind to cover B.
124  if (Overlap.first != UnclaimedRanges.begin()) {
125  --Overlap.first;
126  // ...unless B isn't selected at all.
127  if (Overlap.first->end() <= Claim.begin())
128  ++Overlap.first;
129  }
130  if (Overlap.first == Overlap.second)
131  return Out;
132 
133  // First, copy all overlapping ranges into the output.
134  auto OutFirst = Out.insert(Out.end(), Overlap.first, Overlap.second);
135  // If any of the overlapping ranges were sliced by the claim, split them:
136  // - restrict the returned range to the claimed part
137  // - save the unclaimed part so it can be reinserted
138  llvm::ArrayRef<T> RemainingHead, RemainingTail;
139  if (Claim.begin() > OutFirst->begin()) {
140  RemainingHead = {OutFirst->begin(), Claim.begin()};
141  *OutFirst = {Claim.begin(), OutFirst->end()};
142  }
143  if (Claim.end() < Out.back().end()) {
144  RemainingTail = {Claim.end(), Out.back().end()};
145  Out.back() = {Out.back().begin(), Claim.end()};
146  }
147 
148  // Erase all the overlapping ranges (invalidating all iterators).
149  UnclaimedRanges.erase(Overlap.first, Overlap.second);
150  // Reinsert ranges that were merely trimmed.
151  if (!RemainingHead.empty())
152  UnclaimedRanges.insert(RemainingHead);
153  if (!RemainingTail.empty())
154  UnclaimedRanges.insert(RemainingTail);
155 
156  return Out;
157  }
158 
159 private:
160  using TokenRange = llvm::ArrayRef<T>;
161  struct RangeLess {
162  bool operator()(llvm::ArrayRef<T> L, llvm::ArrayRef<T> R) const {
163  return L.begin() < R.begin();
164  }
165  };
166 
167  // Disjoint sorted unclaimed ranges of expanded tokens.
168  std::set<llvm::ArrayRef<T>, RangeLess> UnclaimedRanges;
169 };
170 
171 // Sentinel value for the selectedness of a node where we've seen no tokens yet.
172 // This resolves to Unselected if no tokens are ever seen.
173 // But Unselected + Complete -> Partial, while NoTokens + Complete --> Complete.
174 // This value is never exposed publicly.
175 constexpr SelectionTree::Selection NoTokens =
176  static_cast<SelectionTree::Selection>(
177  static_cast<unsigned char>(SelectionTree::Complete + 1));
178 
179 // Nodes start with NoTokens, and then use this function to aggregate the
180 // selectedness as more tokens are found.
181 void update(SelectionTree::Selection &Result, SelectionTree::Selection New) {
182  if (New == NoTokens)
183  return;
184  if (Result == NoTokens)
185  Result = New;
186  else if (Result != New)
187  // Can only be completely selected (or unselected) if all tokens are.
188  Result = SelectionTree::Partial;
189 }
190 
191 // As well as comments, don't count semicolons as real tokens.
192 // They're not properly claimed as expr-statement is missing from the AST.
193 bool shouldIgnore(const syntax::Token &Tok) {
194  switch (Tok.kind()) {
195  // Even "attached" comments are not considered part of a node's range.
196  case tok::comment:
197  // The AST doesn't directly store locations for terminating semicolons.
198  case tok::semi:
199  // We don't have locations for cvr-qualifiers: see QualifiedTypeLoc.
200  case tok::kw_const:
201  case tok::kw_volatile:
202  case tok::kw_restrict:
203  return true;
204  default:
205  return false;
206  }
207 }
208 
209 // Determine whether 'Target' is the first expansion of the macro
210 // argument whose top-level spelling location is 'SpellingLoc'.
211 bool isFirstExpansion(FileID Target, SourceLocation SpellingLoc,
212  const SourceManager &SM) {
213  SourceLocation Prev = SpellingLoc;
214  while (true) {
215  // If the arg is expanded multiple times, getMacroArgExpandedLocation()
216  // returns the first expansion.
217  SourceLocation Next = SM.getMacroArgExpandedLocation(Prev);
218  // So if we reach the target, target is the first-expansion of the
219  // first-expansion ...
220  if (SM.getFileID(Next) == Target)
221  return true;
222 
223  // Otherwise, if the FileID stops changing, we've reached the innermost
224  // macro expansion, and Target was on a different branch.
225  if (SM.getFileID(Next) == SM.getFileID(Prev))
226  return false;
227 
228  Prev = Next;
229  }
230  return false;
231 }
232 
233 // SelectionTester can determine whether a range of tokens from the PP-expanded
234 // stream (corresponding to an AST node) is considered selected.
235 //
236 // When the tokens result from macro expansions, the appropriate tokens in the
237 // main file are examined (macro invocation or args). Similarly for #includes.
238 // However, only the first expansion of a given spelled token is considered
239 // selected.
240 //
241 // It tests each token in the range (not just the endpoints) as contiguous
242 // expanded tokens may not have contiguous spellings (with macros).
243 //
244 // Non-token text, and tokens not modeled in the AST (comments, semicolons)
245 // are ignored when determining selectedness.
246 class SelectionTester {
247 public:
248  // The selection is offsets [SelBegin, SelEnd) in SelFile.
249  SelectionTester(const syntax::TokenBuffer &Buf, FileID SelFile,
250  unsigned SelBegin, unsigned SelEnd, const SourceManager &SM)
251  : SelFile(SelFile), SelFileBounds(SM.getLocForStartOfFile(SelFile),
252  SM.getLocForEndOfFile(SelFile)),
253  SM(SM) {
254  // Find all tokens (partially) selected in the file.
255  auto AllSpelledTokens = Buf.spelledTokens(SelFile);
256  const syntax::Token *SelFirst =
257  llvm::partition_point(AllSpelledTokens, [&](const syntax::Token &Tok) {
258  return SM.getFileOffset(Tok.endLocation()) <= SelBegin;
259  });
260  const syntax::Token *SelLimit = std::partition_point(
261  SelFirst, AllSpelledTokens.end(), [&](const syntax::Token &Tok) {
262  return SM.getFileOffset(Tok.location()) < SelEnd;
263  });
264  auto Sel = llvm::makeArrayRef(SelFirst, SelLimit);
265  // Find which of these are preprocessed to nothing and should be ignored.
266  llvm::BitVector PPIgnored(Sel.size(), false);
267  for (const syntax::TokenBuffer::Expansion &X :
268  Buf.expansionsOverlapping(Sel)) {
269  if (X.Expanded.empty()) {
270  for (const syntax::Token &Tok : X.Spelled) {
271  if (&Tok >= SelFirst && &Tok < SelLimit)
272  PPIgnored[&Tok - SelFirst] = true;
273  }
274  }
275  }
276  // Precompute selectedness and offset for selected spelled tokens.
277  for (unsigned I = 0; I < Sel.size(); ++I) {
278  if (shouldIgnore(Sel[I]) || PPIgnored[I])
279  continue;
280  SelectedSpelled.emplace_back();
281  Tok &S = SelectedSpelled.back();
282  S.Offset = SM.getFileOffset(Sel[I].location());
283  if (S.Offset >= SelBegin && S.Offset + Sel[I].length() <= SelEnd)
284  S.Selected = SelectionTree::Complete;
285  else
286  S.Selected = SelectionTree::Partial;
287  }
288  MaybeSelectedExpanded = computeMaybeSelectedExpandedTokens(Buf);
289  }
290 
291  // Test whether a consecutive range of tokens is selected.
292  // The tokens are taken from the expanded token stream.
294  test(llvm::ArrayRef<syntax::Token> ExpandedTokens) const {
295  if (ExpandedTokens.empty())
296  return NoTokens;
297  if (SelectedSpelled.empty())
299  // Cheap (pointer) check whether any of the tokens could touch selection.
300  // In most cases, the node's overall source range touches ExpandedTokens,
301  // or we would have failed mayHit(). However now we're only considering
302  // the *unclaimed* spans of expanded tokens.
303  // This is a significant performance improvement when a lot of nodes
304  // surround the selection, including when generated by macros.
305  if (MaybeSelectedExpanded.empty() ||
306  &ExpandedTokens.front() > &MaybeSelectedExpanded.back() ||
307  &ExpandedTokens.back() < &MaybeSelectedExpanded.front()) {
309  }
310 
311  // The eof token is used as a sentinel.
312  // In general, source range from an AST node should not claim the eof token,
313  // but it could occur for unmatched-bracket cases.
314  // FIXME: fix it in TokenBuffer, expandedTokens(SourceRange) should not
315  // return the eof token.
316  if (ExpandedTokens.back().kind() == tok::eof)
317  ExpandedTokens = ExpandedTokens.drop_back();
318 
319  SelectionTree::Selection Result = NoTokens;
320  while (!ExpandedTokens.empty()) {
321  // Take consecutive tokens from the same context together for efficiency.
322  SourceLocation Start = ExpandedTokens.front().location();
323  FileID FID = SM.getFileID(Start);
324  // Comparing SourceLocations against bounds is cheaper than getFileID().
325  SourceLocation Limit = SM.getComposedLoc(FID, SM.getFileIDSize(FID));
326  auto Batch = ExpandedTokens.take_while([&](const syntax::Token &T) {
327  return T.location() >= Start && T.location() < Limit;
328  });
329  assert(!Batch.empty());
330  ExpandedTokens = ExpandedTokens.drop_front(Batch.size());
331 
332  update(Result, testChunk(FID, Batch));
333  }
334  return Result;
335  }
336 
337  // Cheap check whether any of the tokens in R might be selected.
338  // If it returns false, test() will return NoTokens or Unselected.
339  // If it returns true, test() may return any value.
340  bool mayHit(SourceRange R) const {
341  if (SelectedSpelled.empty() || MaybeSelectedExpanded.empty())
342  return false;
343  // If the node starts after the selection ends, it is not selected.
344  // Tokens a macro location might claim are >= its expansion start.
345  // So if the expansion start > last selected token, we can prune it.
346  // (This is particularly helpful for GTest's TEST macro).
347  if (auto B = offsetInSelFile(getExpansionStart(R.getBegin())))
348  if (*B > SelectedSpelled.back().Offset)
349  return false;
350  // If the node ends before the selection begins, it is not selected.
351  SourceLocation EndLoc = R.getEnd();
352  while (EndLoc.isMacroID())
353  EndLoc = SM.getImmediateExpansionRange(EndLoc).getEnd();
354  // In the rare case that the expansion range is a char range, EndLoc is
355  // ~one token too far to the right. We may fail to prune, that's OK.
356  if (auto E = offsetInSelFile(EndLoc))
357  if (*E < SelectedSpelled.front().Offset)
358  return false;
359  return true;
360  }
361 
362 private:
363  // Plausible expanded tokens that might be affected by the selection.
364  // This is an overestimate, it may contain tokens that are not selected.
365  // The point is to allow cheap pruning in test()
366  llvm::ArrayRef<syntax::Token>
367  computeMaybeSelectedExpandedTokens(const syntax::TokenBuffer &Toks) {
368  if (SelectedSpelled.empty())
369  return {};
370 
371  auto LastAffectedToken = [&](SourceLocation Loc) {
372  auto Offset = offsetInSelFile(Loc);
373  while (Loc.isValid() && !Offset) {
374  Loc = Loc.isMacroID() ? SM.getImmediateExpansionRange(Loc).getEnd()
375  : SM.getIncludeLoc(SM.getFileID(Loc));
376  Offset = offsetInSelFile(Loc);
377  }
378  return Offset;
379  };
380  auto FirstAffectedToken = [&](SourceLocation Loc) {
381  auto Offset = offsetInSelFile(Loc);
382  while (Loc.isValid() && !Offset) {
383  Loc = Loc.isMacroID() ? SM.getImmediateExpansionRange(Loc).getBegin()
384  : SM.getIncludeLoc(SM.getFileID(Loc));
385  Offset = offsetInSelFile(Loc);
386  }
387  return Offset;
388  };
389 
390  const syntax::Token *Start = llvm::partition_point(
391  Toks.expandedTokens(),
392  [&, First = SelectedSpelled.front().Offset](const syntax::Token &Tok) {
393  if (Tok.kind() == tok::eof)
394  return false;
395  // Implausible if upperbound(Tok) < First.
396  if (auto Offset = LastAffectedToken(Tok.location()))
397  return *Offset < First;
398  // A prefix of the expanded tokens may be from an implicit
399  // inclusion (e.g. preamble patch, or command-line -include).
400  return true;
401  });
402 
403  bool EndInvalid = false;
404  const syntax::Token *End = std::partition_point(
405  Start, Toks.expandedTokens().end(),
406  [&, Last = SelectedSpelled.back().Offset](const syntax::Token &Tok) {
407  if (Tok.kind() == tok::eof)
408  return false;
409  // Plausible if lowerbound(Tok) <= Last.
410  if (auto Offset = FirstAffectedToken(Tok.location()))
411  return *Offset <= Last;
412  // Shouldn't happen: once we've seen tokens traceable to the main
413  // file, there shouldn't be any more implicit inclusions.
414  assert(false && "Expanded token could not be resolved to main file!");
415  EndInvalid = true;
416  return true; // conservatively assume this token can overlap
417  });
418  if (EndInvalid)
419  End = Toks.expandedTokens().end();
420 
421  return llvm::makeArrayRef(Start, End);
422  }
423 
424  // Hit-test a consecutive range of tokens from a single file ID.
426  testChunk(FileID FID, llvm::ArrayRef<syntax::Token> Batch) const {
427  assert(!Batch.empty());
428  SourceLocation StartLoc = Batch.front().location();
429  // There are several possible categories of FileID depending on how the
430  // preprocessor was used to generate these tokens:
431  // main file, #included file, macro args, macro bodies.
432  // We need to identify the main-file tokens that represent Batch, and
433  // determine whether we want to exclusively claim them. Regular tokens
434  // represent one AST construct, but a macro invocation can represent many.
435 
436  // Handle tokens written directly in the main file.
437  if (FID == SelFile) {
438  return testTokenRange(*offsetInSelFile(Batch.front().location()),
439  *offsetInSelFile(Batch.back().location()));
440  }
441 
442  // Handle tokens in another file #included into the main file.
443  // Check if the #include is selected, but don't claim it exclusively.
444  if (StartLoc.isFileID()) {
445  for (SourceLocation Loc = Batch.front().location(); Loc.isValid();
446  Loc = SM.getIncludeLoc(SM.getFileID(Loc))) {
447  if (auto Offset = offsetInSelFile(Loc))
448  // FIXME: use whole #include directive, not just the filename string.
449  return testToken(*Offset);
450  }
451  return NoTokens;
452  }
453 
454  assert(StartLoc.isMacroID());
455  // Handle tokens that were passed as a macro argument.
456  SourceLocation ArgStart = SM.getTopMacroCallerLoc(StartLoc);
457  if (auto ArgOffset = offsetInSelFile(ArgStart)) {
458  if (isFirstExpansion(FID, ArgStart, SM)) {
459  SourceLocation ArgEnd =
460  SM.getTopMacroCallerLoc(Batch.back().location());
461  return testTokenRange(*ArgOffset, *offsetInSelFile(ArgEnd));
462  } else { // NOLINT(llvm-else-after-return)
463  /* fall through and treat as part of the macro body */
464  }
465  }
466 
467  // Handle tokens produced by non-argument macro expansion.
468  // Check if the macro name is selected, don't claim it exclusively.
469  if (auto ExpansionOffset = offsetInSelFile(getExpansionStart(StartLoc)))
470  // FIXME: also check ( and ) for function-like macros?
471  return testToken(*ExpansionOffset);
472  return NoTokens;
473  }
474 
475  // Is the closed token range [Begin, End] selected?
476  SelectionTree::Selection testTokenRange(unsigned Begin, unsigned End) const {
477  assert(Begin <= End);
478  // Outside the selection entirely?
479  if (End < SelectedSpelled.front().Offset ||
480  Begin > SelectedSpelled.back().Offset)
482 
483  // Compute range of tokens.
484  auto B = llvm::partition_point(
485  SelectedSpelled, [&](const Tok &T) { return T.Offset < Begin; });
486  auto E = std::partition_point(B, SelectedSpelled.end(), [&](const Tok &T) {
487  return T.Offset <= End;
488  });
489 
490  // Aggregate selectedness of tokens in range.
491  bool ExtendsOutsideSelection = Begin < SelectedSpelled.front().Offset ||
492  End > SelectedSpelled.back().Offset;
493  SelectionTree::Selection Result =
494  ExtendsOutsideSelection ? SelectionTree::Unselected : NoTokens;
495  for (auto It = B; It != E; ++It)
496  update(Result, It->Selected);
497  return Result;
498  }
499 
500  // Is the token at `Offset` selected?
501  SelectionTree::Selection testToken(unsigned Offset) const {
502  // Outside the selection entirely?
503  if (Offset < SelectedSpelled.front().Offset ||
504  Offset > SelectedSpelled.back().Offset)
506  // Find the token, if it exists.
507  auto It = llvm::partition_point(
508  SelectedSpelled, [&](const Tok &T) { return T.Offset < Offset; });
509  if (It != SelectedSpelled.end() && It->Offset == Offset)
510  return It->Selected;
511  return NoTokens;
512  }
513 
514  // Decomposes Loc and returns the offset if the file ID is SelFile.
515  llvm::Optional<unsigned> offsetInSelFile(SourceLocation Loc) const {
516  // Decoding Loc with SM.getDecomposedLoc is relatively expensive.
517  // But SourceLocations for a file are numerically contiguous, so we
518  // can use cheap integer operations instead.
519  if (Loc < SelFileBounds.getBegin() || Loc >= SelFileBounds.getEnd())
520  return llvm::None;
521  // FIXME: subtracting getRawEncoding() is dubious, move this logic into SM.
522  return Loc.getRawEncoding() - SelFileBounds.getBegin().getRawEncoding();
523  }
524 
525  SourceLocation getExpansionStart(SourceLocation Loc) const {
526  while (Loc.isMacroID())
527  Loc = SM.getImmediateExpansionRange(Loc).getBegin();
528  return Loc;
529  }
530 
531  struct Tok {
532  unsigned Offset;
534  };
535  std::vector<Tok> SelectedSpelled;
536  llvm::ArrayRef<syntax::Token> MaybeSelectedExpanded;
537  FileID SelFile;
538  SourceRange SelFileBounds;
539  const SourceManager &SM;
540 };
541 
542 // Show the type of a node for debugging.
543 void printNodeKind(llvm::raw_ostream &OS, const DynTypedNode &N) {
544  if (const TypeLoc *TL = N.get<TypeLoc>()) {
545  // TypeLoc is a hierarchy, but has only a single ASTNodeKind.
546  // Synthesize the name from the Type subclass (except for QualifiedTypeLoc).
547  if (TL->getTypeLocClass() == TypeLoc::Qualified)
548  OS << "QualifiedTypeLoc";
549  else
550  OS << TL->getType()->getTypeClassName() << "TypeLoc";
551  } else {
552  OS << N.getNodeKind().asStringRef();
553  }
554 }
555 
556 #ifndef NDEBUG
557 std::string printNodeToString(const DynTypedNode &N, const PrintingPolicy &PP) {
558  std::string S;
559  llvm::raw_string_ostream OS(S);
560  printNodeKind(OS, N);
561  return std::move(OS.str());
562 }
563 #endif
564 
565 bool isImplicit(const Stmt *S) {
566  // Some Stmts are implicit and shouldn't be traversed, but there's no
567  // "implicit" attribute on Stmt/Expr.
568  // Unwrap implicit casts first if present (other nodes too?).
569  if (auto *ICE = llvm::dyn_cast<ImplicitCastExpr>(S))
570  S = ICE->getSubExprAsWritten();
571  // Implicit this in a MemberExpr is not filtered out by RecursiveASTVisitor.
572  // It would be nice if RAV handled this (!shouldTraverseImplicitCode()).
573  if (auto *CTI = llvm::dyn_cast<CXXThisExpr>(S))
574  if (CTI->isImplicit())
575  return true;
576  // Make sure implicit access of anonymous structs don't end up owning tokens.
577  if (auto *ME = llvm::dyn_cast<MemberExpr>(S)) {
578  if (auto *FD = llvm::dyn_cast<FieldDecl>(ME->getMemberDecl()))
579  if (FD->isAnonymousStructOrUnion())
580  // If Base is an implicit CXXThis, then the whole MemberExpr has no
581  // tokens. If it's a normal e.g. DeclRef, we treat the MemberExpr like
582  // an implicit cast.
583  return isImplicit(ME->getBase());
584  }
585  // Refs to operator() and [] are (almost?) always implicit as part of calls.
586  if (auto *DRE = llvm::dyn_cast<DeclRefExpr>(S)) {
587  if (auto *FD = llvm::dyn_cast<FunctionDecl>(DRE->getDecl())) {
588  switch (FD->getOverloadedOperator()) {
589  case OO_Call:
590  case OO_Subscript:
591  return true;
592  default:
593  break;
594  }
595  }
596  }
597  return false;
598 }
599 
600 // We find the selection by visiting written nodes in the AST, looking for nodes
601 // that intersect with the selected character range.
602 //
603 // While traversing, we maintain a parent stack. As nodes pop off the stack,
604 // we decide whether to keep them or not. To be kept, they must either be
605 // selected or contain some nodes that are.
606 //
607 // For simple cases (not inside macros) we prune subtrees that don't intersect.
608 class SelectionVisitor : public RecursiveASTVisitor<SelectionVisitor> {
609 public:
610  // Runs the visitor to gather selected nodes and their ancestors.
611  // If there is any selection, the root (TUDecl) is the first node.
612  static std::deque<Node> collect(ASTContext &AST,
613  const syntax::TokenBuffer &Tokens,
614  const PrintingPolicy &PP, unsigned Begin,
615  unsigned End, FileID File) {
616  SelectionVisitor V(AST, Tokens, PP, Begin, End, File);
617  V.TraverseAST(AST);
618  assert(V.Stack.size() == 1 && "Unpaired push/pop?");
619  assert(V.Stack.top() == &V.Nodes.front());
620  return std::move(V.Nodes);
621  }
622 
623  // We traverse all "well-behaved" nodes the same way:
624  // - push the node onto the stack
625  // - traverse its children recursively
626  // - pop it from the stack
627  // - hit testing: is intersection(node, selection) - union(children) empty?
628  // - attach it to the tree if it or any children hit the selection
629  //
630  // Two categories of nodes are not "well-behaved":
631  // - those without source range information, we don't record those
632  // - those that can't be stored in DynTypedNode.
633  bool TraverseDecl(Decl *X) {
634  if (llvm::isa_and_nonnull<TranslationUnitDecl>(X))
635  return Base::TraverseDecl(X); // Already pushed by constructor.
636  // Base::TraverseDecl will suppress children, but not this node itself.
637  if (X && X->isImplicit())
638  return true;
639  return traverseNode(X, [&] { return Base::TraverseDecl(X); });
640  }
641  bool TraverseTypeLoc(TypeLoc X) {
642  return traverseNode(&X, [&] { return Base::TraverseTypeLoc(X); });
643  }
644  bool TraverseTemplateArgumentLoc(const TemplateArgumentLoc &X) {
645  return traverseNode(&X,
646  [&] { return Base::TraverseTemplateArgumentLoc(X); });
647  }
648  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc X) {
649  return traverseNode(
650  &X, [&] { return Base::TraverseNestedNameSpecifierLoc(X); });
651  }
652  bool TraverseConstructorInitializer(CXXCtorInitializer *X) {
653  return traverseNode(
654  X, [&] { return Base::TraverseConstructorInitializer(X); });
655  }
656  bool TraverseCXXBaseSpecifier(const CXXBaseSpecifier &X) {
657  return traverseNode(&X, [&] { return Base::TraverseCXXBaseSpecifier(X); });
658  }
659  bool TraverseAttr(Attr *X) {
660  return traverseNode(X, [&] { return Base::TraverseAttr(X); });
661  }
662  // Stmt is the same, but this form allows the data recursion optimization.
663  bool dataTraverseStmtPre(Stmt *X) {
664  if (!X || isImplicit(X))
665  return false;
666  auto N = DynTypedNode::create(*X);
667  if (canSafelySkipNode(N))
668  return false;
669  push(std::move(N));
670  if (shouldSkipChildren(X)) {
671  pop();
672  return false;
673  }
674  return true;
675  }
676  bool dataTraverseStmtPost(Stmt *X) {
677  pop();
678  return true;
679  }
680  // QualifiedTypeLoc is handled strangely in RecursiveASTVisitor: the derived
681  // TraverseTypeLoc is not called for the inner UnqualTypeLoc.
682  // This means we'd never see 'int' in 'const int'! Work around that here.
683  // (The reason for the behavior is to avoid traversing the nested Type twice,
684  // but we ignore TraverseType anyway).
685  bool TraverseQualifiedTypeLoc(QualifiedTypeLoc QX) {
686  return traverseNode<TypeLoc>(
687  &QX, [&] { return TraverseTypeLoc(QX.getUnqualifiedLoc()); });
688  }
689  bool TraverseObjCProtocolLoc(ObjCProtocolLoc PL) {
690  return traverseNode(&PL, [&] { return Base::TraverseObjCProtocolLoc(PL); });
691  }
692  // Uninteresting parts of the AST that don't have locations within them.
693  bool TraverseNestedNameSpecifier(NestedNameSpecifier *) { return true; }
694  bool TraverseType(QualType) { return true; }
695 
696  // The DeclStmt for the loop variable claims to cover the whole range
697  // inside the parens, this causes the range-init expression to not be hit.
698  // Traverse the loop VarDecl instead, which has the right source range.
699  bool TraverseCXXForRangeStmt(CXXForRangeStmt *S) {
700  return traverseNode(S, [&] {
701  return TraverseStmt(S->getInit()) && TraverseDecl(S->getLoopVariable()) &&
702  TraverseStmt(S->getRangeInit()) && TraverseStmt(S->getBody());
703  });
704  }
705  // OpaqueValueExpr blocks traversal, we must explicitly traverse it.
706  bool TraverseOpaqueValueExpr(OpaqueValueExpr *E) {
707  return traverseNode(E, [&] { return TraverseStmt(E->getSourceExpr()); });
708  }
709  // We only want to traverse the *syntactic form* to understand the selection.
710  bool TraversePseudoObjectExpr(PseudoObjectExpr *E) {
711  return traverseNode(E, [&] { return TraverseStmt(E->getSyntacticForm()); });
712  }
713  bool TraverseTypeConstraint(const TypeConstraint *C) {
714  if (auto *E = C->getImmediatelyDeclaredConstraint()) {
715  // Technically this expression is 'implicit' and not traversed by the RAV.
716  // However, the range is correct, so we visit expression to avoid adding
717  // an extra kind to 'DynTypeNode' that hold 'TypeConstraint'.
718  return TraverseStmt(E);
719  }
720  return Base::TraverseTypeConstraint(C);
721  }
722 
723  // Override child traversal for certain node types.
724  using RecursiveASTVisitor::getStmtChildren;
725  // PredefinedExpr like __func__ has a StringLiteral child for its value.
726  // It's not written, so don't traverse it.
727  Stmt::child_range getStmtChildren(PredefinedExpr *) {
728  return {StmtIterator{}, StmtIterator{}};
729  }
730 
731 private:
733 
734  SelectionVisitor(ASTContext &AST, const syntax::TokenBuffer &Tokens,
735  const PrintingPolicy &PP, unsigned SelBegin, unsigned SelEnd,
736  FileID SelFile)
737  : SM(AST.getSourceManager()), LangOpts(AST.getLangOpts()),
738 #ifndef NDEBUG
739  PrintPolicy(PP),
740 #endif
741  TokenBuf(Tokens), SelChecker(Tokens, SelFile, SelBegin, SelEnd, SM),
742  UnclaimedExpandedTokens(Tokens.expandedTokens()) {
743  // Ensure we have a node for the TU decl, regardless of traversal scope.
744  Nodes.emplace_back();
745  Nodes.back().ASTNode = DynTypedNode::create(*AST.getTranslationUnitDecl());
746  Nodes.back().Parent = nullptr;
747  Nodes.back().Selected = SelectionTree::Unselected;
748  Stack.push(&Nodes.back());
749  }
750 
751  // Generic case of TraverseFoo. Func should be the call to Base::TraverseFoo.
752  // Node is always a pointer so the generic code can handle any null checks.
753  template <typename T, typename Func>
754  bool traverseNode(T *Node, const Func &Body) {
755  if (Node == nullptr)
756  return true;
757  auto N = DynTypedNode::create(*Node);
758  if (canSafelySkipNode(N))
759  return true;
760  push(DynTypedNode::create(*Node));
761  bool Ret = Body();
762  pop();
763  return Ret;
764  }
765 
766  // HIT TESTING
767  //
768  // We do rough hit testing on the way down the tree to avoid traversing
769  // subtrees that don't touch the selection (canSafelySkipNode), but
770  // fine-grained hit-testing is mostly done on the way back up (in pop()).
771  // This means children get to claim parts of the selection first, and parents
772  // are only selected if they own tokens that no child owned.
773  //
774  // Nodes *usually* nest nicely: a child's getSourceRange() lies within the
775  // parent's, and a node (transitively) owns all tokens in its range.
776  //
777  // Exception 1: when declarators nest, *inner* declarator is the *outer* type.
778  // e.g. void foo[5](int) is an array of functions.
779  // To handle this case, declarators are careful to only claim the tokens they
780  // own, rather than claim a range and rely on claim ordering.
781  //
782  // Exception 2: siblings both claim the same node.
783  // e.g. `int x, y;` produces two sibling VarDecls.
784  // ~~~~~ x
785  // ~~~~~~~~ y
786  // Here the first ("leftmost") sibling claims the tokens it wants, and the
787  // other sibling gets what's left. So selecting "int" only includes the left
788  // VarDecl in the selection tree.
789 
790  // An optimization for a common case: nodes outside macro expansions that
791  // don't intersect the selection may be recursively skipped.
792  bool canSafelySkipNode(const DynTypedNode &N) {
793  SourceRange S = getSourceRange(N);
794  if (auto *TL = N.get<TypeLoc>()) {
795  // FIXME: TypeLoc::getBeginLoc()/getEndLoc() are pretty fragile
796  // heuristics. We should consider only pruning critical TypeLoc nodes, to
797  // be more robust.
798 
799  // AttributedTypeLoc may point to the attribute's range, NOT the modified
800  // type's range.
801  if (auto AT = TL->getAs<AttributedTypeLoc>())
802  S = AT.getModifiedLoc().getSourceRange();
803  }
804  // SourceRange often doesn't manage to accurately cover attributes.
805  // Fortunately, attributes are rare.
806  if (llvm::any_of(getAttributes(N),
807  [](const Attr *A) { return !A->isImplicit(); }))
808  return false;
809  if (!SelChecker.mayHit(S)) {
810  dlog("{2}skip: {0} {1}", printNodeToString(N, PrintPolicy),
811  S.printToString(SM), indent());
812  return true;
813  }
814  return false;
815  }
816 
817  // There are certain nodes we want to treat as leaves in the SelectionTree,
818  // although they do have children.
819  bool shouldSkipChildren(const Stmt *X) const {
820  // UserDefinedLiteral (e.g. 12_i) has two children (12 and _i).
821  // Unfortunately TokenBuffer sees 12_i as one token and can't split it.
822  // So we treat UserDefinedLiteral as a leaf node, owning the token.
823  return llvm::isa<UserDefinedLiteral>(X);
824  }
825 
826  // Pushes a node onto the ancestor stack. Pairs with pop().
827  // Performs early hit detection for some nodes (on the earlySourceRange).
828  void push(DynTypedNode Node) {
829  SourceRange Early = earlySourceRange(Node);
830  dlog("{2}push: {0} {1}", printNodeToString(Node, PrintPolicy),
831  Node.getSourceRange().printToString(SM), indent());
832  Nodes.emplace_back();
833  Nodes.back().ASTNode = std::move(Node);
834  Nodes.back().Parent = Stack.top();
835  Nodes.back().Selected = NoTokens;
836  Stack.push(&Nodes.back());
837  claimRange(Early, Nodes.back().Selected);
838  }
839 
840  // Pops a node off the ancestor stack, and finalizes it. Pairs with push().
841  // Performs primary hit detection.
842  void pop() {
843  Node &N = *Stack.top();
844  dlog("{1}pop: {0}", printNodeToString(N.ASTNode, PrintPolicy), indent(-1));
845  claimTokensFor(N.ASTNode, N.Selected);
846  if (N.Selected == NoTokens)
847  N.Selected = SelectionTree::Unselected;
848  if (N.Selected || !N.Children.empty()) {
849  // Attach to the tree.
850  N.Parent->Children.push_back(&N);
851  } else {
852  // Neither N any children are selected, it doesn't belong in the tree.
853  assert(&N == &Nodes.back());
854  Nodes.pop_back();
855  }
856  Stack.pop();
857  }
858 
859  // Returns the range of tokens that this node will claim directly, and
860  // is not available to the node's children.
861  // Usually empty, but sometimes children cover tokens but shouldn't own them.
862  SourceRange earlySourceRange(const DynTypedNode &N) {
863  if (const Decl *VD = N.get<VarDecl>()) {
864  // We want the name in the var-decl to be claimed by the decl itself and
865  // not by any children. Ususally, we don't need this, because source
866  // ranges of children are not overlapped with their parent's.
867  // An exception is lambda captured var decl, where AutoTypeLoc is
868  // overlapped with the name loc.
869  // auto fun = [bar = foo]() { ... }
870  // ~~~~~~~~~ VarDecl
871  // ~~~ |- AutoTypeLoc
872  return VD->getLocation();
873  }
874 
875  // When referring to a destructor ~Foo(), attribute Foo to the destructor
876  // rather than the TypeLoc nested inside it.
877  // We still traverse the TypeLoc, because it may contain other targeted
878  // things like the T in ~Foo<T>().
879  if (const auto *CDD = N.get<CXXDestructorDecl>())
880  return CDD->getNameInfo().getNamedTypeInfo()->getTypeLoc().getBeginLoc();
881  if (const auto *ME = N.get<MemberExpr>()) {
882  auto NameInfo = ME->getMemberNameInfo();
883  if (NameInfo.getName().getNameKind() ==
884  DeclarationName::CXXDestructorName)
885  return NameInfo.getNamedTypeInfo()->getTypeLoc().getBeginLoc();
886  }
887 
888  return SourceRange();
889  }
890 
891  // Claim tokens for N, after processing its children.
892  // By default this claims all unclaimed tokens in getSourceRange().
893  // We override this if we want to claim fewer tokens (e.g. there are gaps).
894  void claimTokensFor(const DynTypedNode &N, SelectionTree::Selection &Result) {
895  // CXXConstructExpr often shows implicit construction, like `string s;`.
896  // Don't associate any tokens with it unless there's some syntax like {}.
897  // This prevents it from claiming 's', its primary location.
898  if (const auto *CCE = N.get<CXXConstructExpr>()) {
899  claimRange(CCE->getParenOrBraceRange(), Result);
900  return;
901  }
902  // ExprWithCleanups is always implicit. It often wraps CXXConstructExpr.
903  // Prevent it claiming 's' in the case above.
904  if (N.get<ExprWithCleanups>())
905  return;
906 
907  // Declarators nest "inside out", with parent types inside child ones.
908  // Instead of claiming the whole range (clobbering parent tokens), carefully
909  // claim the tokens owned by this node and non-declarator children.
910  // (We could manipulate traversal order instead, but this is easier).
911  //
912  // Non-declarator types nest normally, and are handled like other nodes.
913  //
914  // Example:
915  // Vec<R<int>(*[2])(A<char>)> is a Vec of arrays of pointers to functions,
916  // which accept A<char> and return R<int>.
917  // The TypeLoc hierarchy:
918  // Vec<R<int>(*[2])(A<char>)> m;
919  // Vec<#####################> TemplateSpecialization Vec
920  // --------[2]---------- `-Array
921  // -------*------------- `-Pointer
922  // ------(----)--------- `-Paren
923  // ------------(#######) `-Function
924  // R<###> |-TemplateSpecialization R
925  // int | `-Builtin int
926  // A<####> `-TemplateSpecialization A
927  // char `-Builtin char
928  //
929  // In each row
930  // --- represents unclaimed parts of the SourceRange.
931  // ### represents parts that children already claimed.
932  if (const auto *TL = N.get<TypeLoc>()) {
933  if (auto PTL = TL->getAs<ParenTypeLoc>()) {
934  claimRange(PTL.getLParenLoc(), Result);
935  claimRange(PTL.getRParenLoc(), Result);
936  return;
937  }
938  if (auto ATL = TL->getAs<ArrayTypeLoc>()) {
939  claimRange(ATL.getBracketsRange(), Result);
940  return;
941  }
942  if (auto PTL = TL->getAs<PointerTypeLoc>()) {
943  claimRange(PTL.getStarLoc(), Result);
944  return;
945  }
946  if (auto FTL = TL->getAs<FunctionTypeLoc>()) {
947  claimRange(SourceRange(FTL.getLParenLoc(), FTL.getEndLoc()), Result);
948  return;
949  }
950  }
951  claimRange(getSourceRange(N), Result);
952  }
953 
954  // Perform hit-testing of a complete Node against the selection.
955  // This runs for every node in the AST, and must be fast in common cases.
956  // This is usually called from pop(), so we can take children into account.
957  // The existing state of Result is relevant.
958  void claimRange(SourceRange S, SelectionTree::Selection &Result) {
959  for (const auto &ClaimedRange :
960  UnclaimedExpandedTokens.erase(TokenBuf.expandedTokens(S)))
961  update(Result, SelChecker.test(ClaimedRange));
962 
963  if (Result && Result != NoTokens)
964  dlog("{1}hit selection: {0}", S.printToString(SM), indent());
965  }
966 
967  std::string indent(int Offset = 0) {
968  // Cast for signed arithmetic.
969  int Amount = int(Stack.size()) + Offset;
970  assert(Amount >= 0);
971  return std::string(Amount, ' ');
972  }
973 
974  SourceManager &SM;
975  const LangOptions &LangOpts;
976 #ifndef NDEBUG
977  const PrintingPolicy &PrintPolicy;
978 #endif
979  const syntax::TokenBuffer &TokenBuf;
980  std::stack<Node *> Stack;
981  SelectionTester SelChecker;
982  IntervalSet<syntax::Token> UnclaimedExpandedTokens;
983  std::deque<Node> Nodes; // Stable pointers as we add more nodes.
984 };
985 
986 } // namespace
987 
988 llvm::SmallString<256> abbreviatedString(DynTypedNode N,
989  const PrintingPolicy &PP) {
990  llvm::SmallString<256> Result;
991  {
992  llvm::raw_svector_ostream OS(Result);
993  N.print(OS, PP);
994  }
995  auto Pos = Result.find('\n');
996  if (Pos != llvm::StringRef::npos) {
997  bool MoreText = !llvm::all_of(Result.str().drop_front(Pos), llvm::isSpace);
998  Result.resize(Pos);
999  if (MoreText)
1000  Result.append(" …");
1001  }
1002  return Result;
1003 }
1004 
1005 void SelectionTree::print(llvm::raw_ostream &OS, const SelectionTree::Node &N,
1006  int Indent) const {
1007  if (N.Selected)
1008  OS.indent(Indent - 1) << (N.Selected == SelectionTree::Complete ? '*'
1009  : '.');
1010  else
1011  OS.indent(Indent);
1012  printNodeKind(OS, N.ASTNode);
1013  OS << ' ' << abbreviatedString(N.ASTNode, PrintPolicy) << "\n";
1014  for (const Node *Child : N.Children)
1015  print(OS, *Child, Indent + 2);
1016 }
1017 
1018 std::string SelectionTree::Node::kind() const {
1019  std::string S;
1020  llvm::raw_string_ostream OS(S);
1021  printNodeKind(OS, ASTNode);
1022  return std::move(OS.str());
1023 }
1024 
1025 // Decide which selections emulate a "point" query in between characters.
1026 // If it's ambiguous (the neighboring characters are selectable tokens), returns
1027 // both possibilities in preference order.
1028 // Always returns at least one range - if no tokens touched, and empty range.
1029 static llvm::SmallVector<std::pair<unsigned, unsigned>, 2>
1030 pointBounds(unsigned Offset, const syntax::TokenBuffer &Tokens) {
1031  const auto &SM = Tokens.sourceManager();
1032  SourceLocation Loc = SM.getComposedLoc(SM.getMainFileID(), Offset);
1033  llvm::SmallVector<std::pair<unsigned, unsigned>, 2> Result;
1034  // Prefer right token over left.
1035  for (const syntax::Token &Tok :
1036  llvm::reverse(spelledTokensTouching(Loc, Tokens))) {
1037  if (shouldIgnore(Tok))
1038  continue;
1039  unsigned Offset = Tokens.sourceManager().getFileOffset(Tok.location());
1040  Result.emplace_back(Offset, Offset + Tok.length());
1041  }
1042  if (Result.empty())
1043  Result.emplace_back(Offset, Offset);
1044  return Result;
1045 }
1046 
1047 bool SelectionTree::createEach(ASTContext &AST,
1048  const syntax::TokenBuffer &Tokens,
1049  unsigned Begin, unsigned End,
1050  llvm::function_ref<bool(SelectionTree)> Func) {
1051  if (Begin != End)
1052  return Func(SelectionTree(AST, Tokens, Begin, End));
1053  for (std::pair<unsigned, unsigned> Bounds : pointBounds(Begin, Tokens))
1054  if (Func(SelectionTree(AST, Tokens, Bounds.first, Bounds.second)))
1055  return true;
1056  return false;
1057 }
1058 
1060  const syntax::TokenBuffer &Tokens,
1061  unsigned int Begin, unsigned int End) {
1062  llvm::Optional<SelectionTree> Result;
1063  createEach(AST, Tokens, Begin, End, [&](SelectionTree T) {
1064  Result = std::move(T);
1065  return true;
1066  });
1067  return std::move(*Result);
1068 }
1069 
1070 SelectionTree::SelectionTree(ASTContext &AST, const syntax::TokenBuffer &Tokens,
1071  unsigned Begin, unsigned End)
1072  : PrintPolicy(AST.getLangOpts()) {
1073  // No fundamental reason the selection needs to be in the main file,
1074  // but that's all clangd has needed so far.
1075  const SourceManager &SM = AST.getSourceManager();
1076  FileID FID = SM.getMainFileID();
1077  PrintPolicy.TerseOutput = true;
1078  PrintPolicy.IncludeNewlines = false;
1079 
1080  dlog("Computing selection for {0}",
1081  SourceRange(SM.getComposedLoc(FID, Begin), SM.getComposedLoc(FID, End))
1082  .printToString(SM));
1083  Nodes = SelectionVisitor::collect(AST, Tokens, PrintPolicy, Begin, End, FID);
1084  Root = Nodes.empty() ? nullptr : &Nodes.front();
1085  recordMetrics(*this, AST.getLangOpts());
1086  dlog("Built selection tree\n{0}", *this);
1087 }
1088 
1090  const Node *Ancestor = Root;
1091  while (Ancestor->Children.size() == 1 && !Ancestor->Selected)
1092  Ancestor = Ancestor->Children.front();
1093  // Returning nullptr here is a bit unprincipled, but it makes the API safer:
1094  // the TranslationUnitDecl contains all of the preamble, so traversing it is a
1095  // performance cliff. Callers can check for null and use root() if they want.
1096  return Ancestor != Root ? Ancestor : nullptr;
1097 }
1098 
1099 const DeclContext &SelectionTree::Node::getDeclContext() const {
1100  for (const Node *CurrentNode = this; CurrentNode != nullptr;
1101  CurrentNode = CurrentNode->Parent) {
1102  if (const Decl *Current = CurrentNode->ASTNode.get<Decl>()) {
1103  if (CurrentNode != this)
1104  if (auto *DC = dyn_cast<DeclContext>(Current))
1105  return *DC;
1106  return *Current->getLexicalDeclContext();
1107  }
1108  }
1109  llvm_unreachable("A tree must always be rooted at TranslationUnitDecl.");
1110 }
1111 
1113  if (Children.size() == 1 &&
1114  getSourceRange(Children.front()->ASTNode) == getSourceRange(ASTNode))
1115  return Children.front()->ignoreImplicit();
1116  return *this;
1117 }
1118 
1120  if (Parent && getSourceRange(Parent->ASTNode) == getSourceRange(ASTNode))
1121  return Parent->outerImplicit();
1122  return *this;
1123 }
1124 
1125 } // namespace clangd
1126 } // namespace clang
dlog
#define dlog(...)
Definition: Logger.h:101
Range
CharSourceRange Range
SourceRange for the file name.
Definition: IncludeOrderCheck.cpp:39
Loc
SourceLocation Loc
Definition: KernelNameRestrictionCheck.cpp:45
Base
std::unique_ptr< GlobalCompilationDatabase > Base
Definition: GlobalCompilationDatabaseTests.cpp:85
clang::clangd::SelectionTree::Node::kind
std::string kind() const
Definition: Selection.cpp:1018
RecursiveASTVisitor
Selection.h
E
const Expr * E
Definition: AvoidBindCheck.cpp:88
clang::clangd::SelectionTree::Node::ignoreImplicit
const Node & ignoreImplicit() const
Definition: Selection.cpp:1112
clang::clangd::SelectionTree::createEach
static bool createEach(ASTContext &AST, const syntax::TokenBuffer &Tokens, unsigned Begin, unsigned End, llvm::function_ref< bool(SelectionTree)> Func)
Definition: Selection.cpp:1047
clang::clangd::SelectionTree::Node::Selected
Selection Selected
Definition: Selection.h:130
clang::clangd::pointBounds
static llvm::SmallVector< std::pair< unsigned, unsigned >, 2 > pointBounds(unsigned Offset, const syntax::TokenBuffer &Tokens)
Definition: Selection.cpp:1030
clang::clangd::X
static URISchemeRegistry::Add< TestScheme > X(TestScheme::Scheme, "Test schema")
Trace.h
Selected
SelectionTree::Selection Selected
Definition: Selection.cpp:533
clang::clangd::SelectionTree::Node::outerImplicit
const Node & outerImplicit() const
Definition: Selection.cpp:1119
clang::clangd::SelectionTree::Node::ASTNode
DynTypedNode ASTNode
Definition: Selection.h:128
Pos
size_t Pos
Definition: NoLintDirectiveHandler.cpp:97
clang::clangd::SelectionTree::Complete
@ Complete
Definition: Selection.h:118
Children
std::vector< std::unique_ptr< HTMLNode > > Children
Definition: HTMLGenerator.cpp:91
ns1::ns2::A
@ A
Definition: CategoricalFeature.h:3
clang::clangd::SelectionTree::Node::Children
llvm::SmallVector< const Node * > Children
Definition: Selection.h:126
Offset
unsigned Offset
Definition: Selection.cpp:532
clang::clangd::abbreviatedString
llvm::SmallString< 256 > abbreviatedString(DynTypedNode N, const PrintingPolicy &PP)
Definition: Selection.cpp:988
Decl
const FunctionDecl * Decl
Definition: AvoidBindCheck.cpp:100
clang::clangd::SelectionTree::createRight
static SelectionTree createRight(ASTContext &AST, const syntax::TokenBuffer &Tokens, unsigned Begin, unsigned End)
Definition: Selection.cpp:1059
clang::clangd::trace::enabled
bool enabled()
Returns true if there is an active tracer.
Definition: Trace.cpp:283
Logger.h
Bounds
PreambleBounds Bounds
Definition: Preamble.cpp:298
clang::clangd::trace::Metric::Distribution
@ Distribution
A distribution of values with a meaningful mean and count.
Definition: Trace.h:52
clang::clangd::SelectionTree
Definition: Selection.h:76
clang::clangd::SelectionTree::Node
Definition: Selection.h:122
clang::tidy::bugprone::PP
static Preprocessor * PP
Definition: BadSignalToKillThreadCheck.cpp:29
clang::clangd::SelectionTree::Node::Parent
Node * Parent
Definition: Selection.h:124
Parent
const Node * Parent
Definition: ExtractFunction.cpp:157
clang::clangd::SelectionTree::commonAncestor
const Node * commonAncestor() const
Definition: Selection.cpp:1089
C
const Criteria C
Definition: FunctionCognitiveComplexityCheck.cpp:93
clang::clangd::SelectionTree::SelectionTree
SelectionTree(const SelectionTree &)=delete
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
OS
llvm::raw_string_ostream OS
Definition: TraceTests.cpp:160
LangOpts
const LangOptions * LangOpts
Definition: ExtractFunction.cpp:375
clang::clangd::SelectionTree::Unselected
@ Unselected
Definition: Selection.h:114
clang::clangd::SelectionTree::Partial
@ Partial
Definition: Selection.h:116
ns1::ns2::B
@ B
Definition: CategoricalFeature.h:3
Out
CompiledFragmentImpl & Out
Definition: ConfigCompile.cpp:99
clang::clangd::getAttributes
std::vector< const Attr * > getAttributes(const DynTypedNode &N)
Return attributes attached directly to a node.
Definition: AST.cpp:617
clang::clangd::SelectionTree::Node::getDeclContext
const DeclContext & getDeclContext() const
Definition: Selection.cpp:1099
clang::clangd::ASTNode
Simplified description of a clang AST node.
Definition: Protocol.h:1840
AST.h
clang::clangd::SelectionTree::Selection
Selection
Definition: Selection.h:106