This is an archive of the discontinued LLVM Phabricator instance.

[clangd] Elide even more checks in SelectionTree.
ClosedPublic

Authored by sammccall on Jan 12 2022, 5:51 AM.

Details

Summary

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).

Diff Detail

Event Timeline

sammccall created this revision.Jan 12 2022, 5:51 AM
sammccall requested review of this revision.Jan 12 2022, 5:51 AM
nridge added a subscriber: nridge.Jan 12 2022, 9:00 PM
sammccall added inline comments.Jan 12 2022, 11:09 PM
clang-tools-extra/clangd/unittests/SelectionTests.cpp
206

This test isn't strictly related, but it failed with a buggy version of this patch.
(It's extracted from a DefineOutline test which also failed but in a less direct way)

this looks good in general.

clang-tools-extra/clangd/Selection.cpp
288

if it is empty, I think it is more appropriate to return NoTokens (the old behavior)

289

I would suggest rename the member ExpandedTokens, and SpellingTokens to something like AffectedSpelledTokens, AffectedExpandedTokens, I think it is important to express "these are affected-tokens by the selection" in their name

362

this should be true.

385

the same, true.

390

should be End.

sammccall planned changes to this revision.Jan 13 2022, 5:28 AM
sammccall marked 5 inline comments as done.

Thanks! You caught a serious bug, I'm digging into it.

clang-tools-extra/clangd/Selection.cpp
288

Whoops, this was meant to be this->ExpandedTokens.

You're right that in principle ExpandedTokens.empty() should return NoTokens. (We would never actually get here).

Similarly in principle !ExpandedTokens.empty() && SpelledTokens.empty() should return Unselected instead of NoTokens. This could happen but didn't make any difference to observable behavior.

I've fixed all these in any case.

289

ExpandedTokens -> MaybeSelectedExpanded

SpelledTokens -> SelectedSpelled

362

Oh shoot, now the assert is firing, I must have missed some cases :-(
Need to fix this.

sammccall updated this revision to Diff 399643.Jan 13 2022, 5:55 AM
sammccall marked 3 inline comments as done.

Handle EOF

PTAL

clang-tools-extra/clangd/Selection.cpp
362

OK, this was just not handling EOF token location (which offsetInSelFile rejects, correctly I think)

hokein accepted this revision.Jan 13 2022, 11:26 AM

Thanks, this looks great!

clang-tools-extra/clangd/Selection.cpp
364

nit: remove this debug code.

390

and here.

This revision is now accepted and ready to land.Jan 13 2022, 11:26 AM
This revision was automatically updated to reflect the committed changes.
sammccall marked 2 inline comments as done.