diff --git a/clang-tools-extra/clangd/Selection.cpp b/clang-tools-extra/clangd/Selection.cpp --- a/clang-tools-extra/clangd/Selection.cpp +++ b/clang-tools-extra/clangd/Selection.cpp @@ -271,6 +271,7 @@ else S.Selected = SelectionTree::Partial; } + ExpandedTokens = computeExpandedTokens(Buf); } // Test whether a consecutive range of tokens is selected. @@ -279,6 +280,18 @@ test(llvm::ArrayRef ExpandedTokens) const { if (SpelledTokens.empty()) return NoTokens; + // Cheap (pointer) check whether any of the tokens could touch selection. + // In most cases, the node's overall source range touches ExpandedTokens, + // or we would have failed mayHit(). However now we're only considering + // the *unclaimed* spans of expanded tokens. + // This is a significant performance improvement when a lot of nodes + // surround the selection, including when generated by macros. + if (ExpandedTokens.empty() || + &ExpandedTokens.front() > &this->ExpandedTokens.back() || + &ExpandedTokens.back() < &this->ExpandedTokens.front()) { + return SelectionTree::Unselected; + } + SelectionTree::Selection Result = NoTokens; while (!ExpandedTokens.empty()) { // Take consecutive tokens from the same context together for efficiency. @@ -301,7 +314,7 @@ // If it returns false, test() will return NoTokens or Unselected. // If it returns true, test() may return any value. bool mayHit(SourceRange R) const { - if (SpelledTokens.empty()) + if (SpelledTokens.empty() || ExpandedTokens.empty()) return false; auto B = offsetInSelFile(R.getBegin()); auto E = offsetInSelFile(R.getEnd()); @@ -312,6 +325,62 @@ } private: + // Plausible expanded tokens that might be affected by the selection. + // This is an overestimate, it may contain tokens that are not selected. + // The point is to allow cheap pruning in test() + llvm::ArrayRef + computeExpandedTokens(const syntax::TokenBuffer &Toks) { + if (SpelledTokens.empty()) + return {}; + + bool StartInvalid = false; + const syntax::Token *Start = llvm::partition_point( + Toks.expandedTokens(), + [&, First = SpelledTokens.front().Offset](const syntax::Token &Tok) { + // Implausible if upperbound(Tok) < First. + SourceLocation Loc = Tok.location(); + auto Offset = offsetInSelFile(Loc); + while (Loc.isValid() && !Offset) { + Loc = Loc.isMacroID() ? SM.getImmediateExpansionRange(Loc).getEnd() + : SM.getIncludeLoc(SM.getFileID(Loc)); + Offset = offsetInSelFile(Loc); + } + if (Offset) + return *Offset < First; + StartInvalid = false; + return false; + }); + if (StartInvalid) { + assert(false && "Expanded tokens could not be resolved to main file!"); + Start = Toks.expandedTokens().begin(); + } + + bool EndInvalid = false; + const syntax::Token *End = llvm::partition_point( + Toks.expandedTokens(), + [&, Last = SpelledTokens.back().Offset](const syntax::Token &Tok) { + // Plausible if lowerbound(Tok) <= Last. + SourceLocation Loc = Tok.location(); + auto Offset = offsetInSelFile(Loc); + while (Loc.isValid() && !Offset) { + Loc = Loc.isMacroID() + ? SM.getImmediateExpansionRange(Loc).getBegin() + : SM.getIncludeLoc(SM.getFileID(Loc)); + Offset = offsetInSelFile(Loc); + } + if (Offset) + return *Offset <= Last; + EndInvalid = false; + return true; + }); + if (EndInvalid) { + assert(false && "Expanded tokens could not be resolved to main file!"); + Start = Toks.expandedTokens().end(); + } + + return llvm::makeArrayRef(Start, End); + } + // Hit-test a consecutive range of tokens from a single file ID. SelectionTree::Selection testChunk(FileID FID, llvm::ArrayRef Batch) const { @@ -418,6 +487,7 @@ SelectionTree::Selection Selected; }; std::vector SpelledTokens; + llvm::ArrayRef ExpandedTokens; FileID SelFile; SourceRange SelFileBounds; const SourceManager &SM; diff --git a/clang-tools-extra/clangd/unittests/SelectionTests.cpp b/clang-tools-extra/clangd/unittests/SelectionTests.cpp --- a/clang-tools-extra/clangd/unittests/SelectionTests.cpp +++ b/clang-tools-extra/clangd/unittests/SelectionTests.cpp @@ -201,6 +201,13 @@ )cpp", nullptr, }, + { + R"cpp( + #define TARGET void foo() + [[TAR^GET{ return; }]] + )cpp", + "FunctionDecl", + }, { R"cpp( struct S { S(const char*); };