sammccall created this revision.
sammccall added a reviewer: hokein.
Herald added subscribers: usaxena95, kadircet, arphaman.
sammccall requested review of this revision.
Herald added subscribers: cfe-commits, MaskRay, ilya-biryukov.
Herald added a project: clang-tools-extra.
During pop() we convert nodes into spans of expanded syntax::Tokens.
If we precompute a range of plausible (expanded) tokens, then we can do an
extremely cheap approximate hit-test against it, because syntax::Tokens are
ordered by pointer.
This would seem not to buy anything (we don't enter nodes unless they overlap
the selection), but in fact the spans we have are for *newly* claimed ranges
(i.e. those unclaimed by any child node).
So if you have:
{ { [[2+2]]; } }
then all of the CompoundStmts pass the hit test and are pushed, but we skip
full hit-testing of the brackets during pop() as they lie outside the range.
This is ~10x average speedup for selectiontree on a bad case I've seen
(large gtest file).
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D117107
Files:
clang-tools-extra/clangd/Selection.cpp
clang-tools-extra/clangd/unittests/SelectionTests.cpp
Index: clang-tools-extra/clangd/unittests/SelectionTests.cpp
===================================================================
--- clang-tools-extra/clangd/unittests/SelectionTests.cpp
+++ 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*); };
Index: clang-tools-extra/clangd/Selection.cpp
===================================================================
--- clang-tools-extra/clangd/Selection.cpp
+++ 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<syntax::Token> 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<syntax::Token>
+ 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<syntax::Token> Batch) const {
@@ -418,6 +487,7 @@
SelectionTree::Selection Selected;
};
std::vector<Tok> SpelledTokens;
+ llvm::ArrayRef<syntax::Token> ExpandedTokens;
FileID SelFile;
SourceRange SelFileBounds;
const SourceManager &SM;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
