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