Page MenuHomePhabricator

[clangd] Support outgoing calls in call hierarchy
Needs ReviewPublic

Authored by qchateau on Dec 26 2020, 2:31 PM.

Details

Reviewers
sammccall
Summary

The implementation is very close the the incoming
calls implementation. The results of the outgoing
calls are expected to be the exact symmetry of the
incoming calls.

Diff Detail

Event Timeline

qchateau created this revision.Dec 26 2020, 2:31 PM
qchateau requested review of this revision.Dec 26 2020, 2:31 PM
qchateau updated this revision to Diff 313767.Dec 26 2020, 4:24 PM
  • Fix tests
qchateau updated this revision to Diff 313776.Dec 27 2020, 3:53 AM
  • Smaller reversed refs memory usage
  • Fix Dex::estimateMemoryUsage

Note: Build fails due to clang-tidy warnings in tests. I chose to keep the naming consistent with what's already in place rather than fix the clang-tidy warning.

nridge added a subscriber: nridge.Jan 10 2021, 2:18 PM

Thanks for working on this!

I haven't looked at the whole patch in detail, but I looked at some parts (mainly the SymbolIndex API and what in-memory structures we store to implement it) and wrote a few thoughts.

clang-tools-extra/clangd/XRefs.cpp
1843

If memory usage of Dex::RevRefs becomes a concern, we could consider only storing the references that would pass this filter in the first place. That would trade off time spent building the reverse lookup (we'd have to do symbol lookups or keep around extra state to track the symbol kinds) for space savings.

clang-tools-extra/clangd/index/Index.h
85

As the protocol wants the outgoing calls grouped by symbol, we could consider storing them (and having the SymbolIndex API expose them) in that way.

The main motivation would be space savings on the storage side (Dex::RevRefs), as in the case of multiple calls to the same function we only need to store the target SymbolID once.

However, it may not be worth doing this, as having a large number of outgoing calls to the same target inside a given function is likely to be rare, and vectors have their own overhead. (It's also not clear to what extent the details of the LSP protocol should dictate the shape of the SymbolIndex API.)

133

Perhaps we should have a distinct request structure, for future extensibility?

clang-tools-extra/clangd/index/MemIndex.cpp
97

Looping over all refs seems expensive even for MemIndex. Perhaps we should have a reverse lookup table similar to RevRefs here as well?

qchateau added inline comments.Jan 11 2021, 12:25 AM
clang-tools-extra/clangd/XRefs.cpp
1843

I've used tried this patch with the whole llvm project indexed. If I remember correctly it's something in the like of 100MB, around 5-10% même usage of clangd. As such it's not very high but it's definitely not negligible, especially for a feature that's not used very often.

clang-tools-extra/clangd/index/Index.h
85

I indeed believe that I'd use more memory than it would save, but I did not try it.
Anyway I think the difference would be minimal, and I'd say we should choose what gives the "best" API

133

Sure, that makes sense

clang-tools-extra/clangd/index/MemIndex.cpp
97

That's pretty fast even on my laptop IIRC, and only used for outgoing calls atm.

Thanks for looking into this feature!

I do have to ask a fairly naive question though - what's it useful for, beyond protocol completeness? The obvious alternative to a user is looking at a function's implementation, which is an extra context switch but also provides a lot more information. I'm having trouble understanding when this could be better enough to justify much extra complexity/resources.

(Adding a new method to the index interface seems like a fairly substantial thing, and 5-10% to index memory usage is substantial as you say).

I think that, as with incoming calls, the incremental value is in seeing the tree at a glance. So, you might query the outgoing calls for a function, expand the tree, and look over the transitive callees to see if the function ends up performing a certain type of operation (say, a filesystem access).

That said, I will admit that in ~10 years of using Eclipse CDT, which supports both incoming calls and outgoing calls, I can't recall using outgoing calls even once (whereas I did use incoming calls). Of course, other users' experiences may vary.

You're right, I probably got carried away for the sake of completeness. Allocating extra memory for a feature nobody is going to use is definitely not worth it. Though maybe we can take advantage of what's already been done and if we remove the RevRefs map, and pay the full price of iterating all refs when refersTo is called, we still have this feature. Although slower, it shouldn't take more than a few 100's of milliseconds even on a big project. Which means the feature is usable, at least for most small to medium sized projects, at no extra cost for people who do not use it.

Would this be acceptable ?

For what it's worth, outgoing call is useful for looking at grand children and jump immediately. Also, clangd doesn't runs on embedded devices, so extra memory allocation isn't a concern at all for most users. @sammccall which part of the code do you find very complex/concerning?

Herald added a project: Restricted Project. · View Herald TranscriptNov 11 2021, 2:27 PM