Implement outgoing calls

[jrwrigh]

Stemming from this discussion: #162 (comment) (apologies if a discussion has already be created for this and I missed it).

There's an old patch for it here

Other related issues are #162 and #867.

And here's a good example/justification for the feature: #162 (comment)

[qchateau]

If that feature is deemed useful and my old patch is good enough, I don't mind taking the time to rebase it.

[HighCommander4]

Appreciated!

Before you spend time on that, it would be good to establish a consensus that the patch would be accepted.

@sam-mccall @kadircet @hokein, what do you think?

My understanding is the main objection is (from this comment):

the sticking point is that the patch adds 5-10% to the size of the in-memory representation of a typical project's index, and it was not clear if the feature is worth this cost

My opinion is that given that this feature is a part of LSP and several users have asked for it, clangd should support it, but it could be behind a flag if we're concerned about the footprint.

[yoav-za]

If it helps, I want to add to the consensus. I find outgoing call graphs to be extremely helpful, especially when navigating a big code base, as it helps you to get the big picture without the need to read every function on the way.
It is not by accident that other code indexing and reverse engineering tools give you the ability to map outgoing call hierarchies. SciTools' Understand, Source Insight, Hex Rays' IDA and NSA's Ghidra all have it for a long time by now.

Also, I agree with @HighCommander4 - if memory is the issue here, adding this behind an opt-in flag sounds to me like a good solution.

[jrwrigh]

Any update on this? Or are we still waiting on feedback from @sam-mccall @kadircet @hokein?

[HighCommander4]

Appreciated!

Before you spend time on that, it would be good to establish a consensus that the patch would be accepted.

@sam-mccall @kadircet @hokein, what do you think?

My understanding is the main objection is (from this comment):

the sticking point is that the patch adds 5-10% to the size of the in-memory representation of a typical project's index, and it was not clear if the feature is worth this cost

My opinion is that given that this feature is a part of LSP and several users have asked for it, clangd should support it, but it could be behind a flag if we're concerned about the footprint.

@sam-mccall @kadircet @hokein, ping on the above question :) Given the user interest in the feature, some direction would be appreciated.

[pidgeon777]

@HighCommander4 Yes it's a pity that a working implementation exists but is not being merged... In my opinion, a flag to let the user enable/disable it could eventually be a good compromise.

Or, if memory usage is not a big concern, it could be just added?

[pidgeon777]

I also would like to ask if there is any news. Hopefully outgoing calls will be implemented, ccls is already doing that and it doesn't make sense to enable both clangd and ccls just for the call hierarchy function.

[pidgeon777]

Hello, I would like to ask if any update is available. We think this is one of the missing "big" features, unfortunately not available yet.

[pidgeon777]

I add this should be technically doable because ccls is already implementing it.

[qchateau]

It is doable, but my current implementation requires extra memory. So the question is: is it worth it ?

[pidgeon777]

Maybe we could open a poll or something to take a decision?

Or, maybe your new implementation could be disabled by simply setting a compiler flag if a developer wishes to do so?

[sam-mccall]

Sorry for the silence here, I haven't been able to be so active in general. Discussed a bit with @kadircet today.
TL;DR: +1 if we can get the memory usage down (we can!) and the limitations of the index are OK.

Concerns here:

• how useful is the feature - clearly some people want it, if we can make it cheap-ish this seems addressed
• clarity of scope: it would be neat if this could e.g. understand calls inside template instantiations, but it won't (unless someone is proposing something really radical!). It's ~a different UI over browsing the code with go-to-definition, not a more abstract/powerful code model. Is it still useful?
• memory usage for a niche feature: I think we can actually squeeze this way down to the point we don't have to care about it, if Quentin or others have appetite to do so. Detailed comments on the review.
• added interface complexity: my biggest concern here is adding new methods to SymbolIndex. But it's just another view on the same data, this doesn't seem too bad.

[jrwrigh]

it would be neat if this could e.g. understand calls inside template instantiations, but it won't (unless someone is proposing something really radical!).

I'm personally only interested on the C side of things, rather than C++. So I don' think there are too many of those issues for that.

It's ~a different UI over browsing the code with go-to-definition, not a more abstract/powerful code model. Is it still useful?

I'd say that go-to-definition vs call hierarchy is somewhat analogous to comparing the index vs table of contents for a textbook. If you have a specific topic (function, variable, class, whatever else) you want to get information on, find it in the index (use go-to-definition). If you want answer "what information does this book cover?" or "Does this chapter describe this aspect of the topic?", then the table of contents is going to be a much nicer way of answering that question.

Also, regarding it being "just" a different UI, re-contextualization of data is quite useful, even if it's just the same data.

[HighCommander4]

It's ~a different UI over browsing the code with go-to-definition, not a more abstract/powerful code model. Is it still useful?

As a practical matter, consider the use case of wanting to know where a particular call site ultimately calls into an interesting code layer (like, say, makes a system call). Let's say the answer is 6 layers of function calls deep from the call site.

With go-to-definition, if the files containing the intermediate call sites aren't already open, my latency of arriving at this answer includes 6 AST build times, which in a large codebase can take multiple seconds each. (And that's assuming at each step I know the correct function call to follow and don't have to backtrack.)

With call hierarchy, I can see the answer at a glance by looking over the tree of calls.

So, while it may technically be just a different UI, I think the performance improvement over the alternative (go-to-def based) workflow makes it a useful ability.

[peng-wang-cn]

This is definitely a must-have feature. Eclipse CDT has already had it for many years. As @yoav-za pointed out, it's very useful when navigating an unfamiliar large code base. Given the fact that Eclipse CDT has historical architectural disadvantage at effectively parsing compile_commands.json, adding this outgoing call hierarchy feature will give me (and many more like me maybe) the last reason to abandon Eclipse and use vscode/clangd for any C++ code base.

[HALOCORE]

I recently bumped into a problem to create wrapper functions for all the functions (including library functions and syscalls) directly or indirectly called by a function. It seems that clangd doesn't have the outgoing call feature. However, Microsoft's C++ language server can correctly list all the outgoing calls. Really hope the same feature is available in clangd.

[pidgeon777]

Bump hoping for good news

[HighCommander4]

I have some :) A few weeks ago, I took over Quentin's patch (https://reviews.llvm.org/D93829), updated it to hopefully address the memory usage concerns, and re-submitted it for review. You can follow the review for updates.

[pidgeon777]

Great! So at the time, what the next steps would be?

Also, would the outgoing calls report just the single definitions of all the functions called inside the parent function, or it will return all of the occurrences of the called functions?

[HighCommander4]

what the next steps would be?

The next step is for @sam-mccall to review my patch :) (Hi Sam!)

Also, would the outgoing calls report just the single definitions of all the functions called inside the parent function, or it will return all of the occurrences of the called functions?

At the protocol level, the server does return information about each occurrence of the called function. (You can see in the specification that CallHierarchyOutgoingCall has a fromRanges field which is an array.)

It's up to clients how they visualize this. The VSCode behaviour is to show a single tree item for the callee in the call hierarchy tree view, but when that tree item is selected, all associated source ranges are highlighted in the editor. Please see the attached screenshot for an illustration.

[pidgeon777]

So, if I understand correctly, if caller() also calls let's say callee2(), then the protocol would return the 2 occurrences of callee() and the one of callee2(), specifying line and column of those occurrences?

[HighCommander4]

Yep, that's right.

[pidgeon777]

Still hoping for an update 😅

[HighCommander4]

The review of the patch has moved to Github, you can follow it here: llvm/llvm-project#77556