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