Page MenuHomePhabricator

[clangd] Address limitations in SelectionTree:

Authored by sammccall on Jun 25 2019, 4:29 AM.


  • nodes can have special-cased hit ranges including "holes" (FunctionTypeLoc in void foo())
  • token conflicts between siblings (int a,b;) are resolved in favor of left sibling
  • parent/child overlap is handled statefully rather than explicitly by comparing parent/child ranges (this lets us share a mechanism with sibling conflicts)

Diff Detail


Event Timeline

sammccall created this revision.Jun 25 2019, 4:29 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 25 2019, 4:29 AM

Also there were some offline discussions around, handling of "invisible nodes"(e.g, ExprWithCleanups) and other types of typelocs like ParenTypeLocs and owner of '=' sign in copy/move assignment constructors

54 ↗(On Diff #206413)

assume we have inserted the range [1,5] and then tried inserting {[1,5], [2,3]}.
In that case IsCovered would return false for [2,3]. And add would return true, but all of the newranges were contained in the RangeSet

Also if we are going to store possibly-overlapping OffsetRanges why are we trying to remove those?

136 ↗(On Diff #206413)

what about moving this to top of the file?

137 ↗(On Diff #206413)

already defined at top

221 ↗(On Diff #206413)

what happens to parentheses in this case?

sammccall planned changes to this revision.Jun 25 2019, 9:34 AM
sammccall marked 2 inline comments as done.

Thanks for the comments here and the offline discussion.

The problems identified were:

    • when a node's range is adjusted, then invisible parents (like ExprWithCleanups) don't adjust to match and end up owning tokens.
  • it would be nice if CXXConstructExpr claimed the = when copy-assigning, so it would be a go-to-definition target.
    • the FunctionTypeLoc handling is naive, and won't treat void (*s)() correctly where the identifier is wrapped in a further typeloc

The best solution to the latter appears to be to lean even more on traversal order and the "already claimed" mechanism: claim the identifier for the VarDecl on the way down, before the children are traversed.

I believe this will eliminate the last case where CXXConstructExpr actually needs special bounds: Type() will have Type claimed by a sibling typeloc, Type t() will have t claimed by the parent vardecl, etc.
Removing the special bounds will make = owned by the CXXConstructExpr, and sidestep the invisible-nodes problem.

And obviously it will simplify the code to have a single range for nodes (once again). So I'll fold it into this patch.

54 ↗(On Diff #206413)

I forgot to mention the NewRanges must be disjoint, which (I think) makes this always correct.

Why remove the covered ranges? Just to avoid growing Ranges, since the algorithm is linear in that. Not important, but we're doing the check anyway.

There's no good reason to copy, remove in place, and copy again though, I'll fix that.

221 ↗(On Diff #206413)

There are none; we handled the parens case two lines up :-)

sammccall updated this revision to Diff 206531.Jun 25 2019, 1:58 PM
sammccall marked 2 inline comments as done.

Revert multi-range support. Add early hit detection (before children) instead.
Add more tests.

kadircet accepted this revision.Jun 26 2019, 6:01 AM

LGTM, thanks!

45 ↗(On Diff #206531)

I suppose comment should be [Begin, R.first). Could you also change the order within condition?

48 ↗(On Diff #206531)

nit: maybe move this check into previous condition? i.e:

if (Begin < R.second) {
      Begin = R.second; // Prefix is covered, truncate the range.
      if (Begin >= End)
        return true;
236 ↗(On Diff #206531)

also called from push() now

170 ↗(On Diff #206531)

could you also add a test case with cursor on identifier(i.e, s)

This revision is now accepted and ready to land.Jun 26 2019, 6:01 AM
This revision was automatically updated to reflect the committed changes.
sammccall marked 4 inline comments as done.
Herald added a project: Restricted Project. · View Herald TranscriptJun 27 2019, 4:20 AM