[clangd] Elide even more checks in SelectionTree.
authorSam McCall <sam.mccall@gmail.com>
Wed, 12 Jan 2022 13:50:55 +0000 (14:50 +0100)
committerSam McCall <sam.mccall@gmail.com>
Thu, 13 Jan 2022 21:27:51 +0000 (22:27 +0100)
commit07f9fb8b51417ec3e6f46508e1b5ef78287b32ad
treeb40c4b5c39cb242dce0588da4ece407676125d57
parent004acbb47d61ffcc52da0c85ef6e6747a7cc7c14
[clangd] Elide even more checks in SelectionTree.

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

Differential Revision: https://reviews.llvm.org/D117107
clang-tools-extra/clangd/Selection.cpp
clang-tools-extra/clangd/unittests/SelectionTests.cpp