Find usages

[matklad]

We should support find usages (aka reference search).

This is a feature where IDE and compiler work differently. Compiler typically eagerly walks all code in top-down manner, and can collect usages along the way.

IDE should use a lazy bottom-up approach. So, to handle find usages, we need to implement classic trick of dong text search to find a superset of usages, and than pruning them with precise resolve.

Here's how find usages should work:

1. First, given an element, we should compute SearchScope: an overopraximating filter on files that might contain references for this element. For things like local variables the search scope is just a function. for pub(crate) things it's a crate, and for pub things it's crate + dependant crates.

2. Then, we should process all files from the search scopes and look for text occurrences of the identifier. For a first implementation, just going through each file will be good enough. Ideally, this should be speed up with a use of a trigram index.

3. For each of the potential matches, we invoke "goto definition" to check if it is indeed a usage and not a random match

[umanwizard]

How do you know for sure a text search will find all uses?

E.g. https://doc.rust-lang.org/std/macro.concat_idents.html

[matklad]

Two options:

• search in macro expanded code as well
• don't treat as a usage

It's unclear what would be the best for the user. Ideally, for macros, we should find usages in definition of a macro, but that's impossible because macro definitions are more or less opaque for IDEs.

[umanwizard]

@matklad One more question - wouldn't it also work to build an index during (top-down) compilation/analysis ? I.e., every time a name is resolved, add the current source location as a "use" of that name. Then when the action is invoked, you could return that list of locations, doing no work.

I am not sure, but I think this is how cquery works.

[lnicola]

I think that's basically what happens, but RA is lazy and only parses the files when it needs to. See #1650 for a discussion related to that.

[matklad]

@umanwizard top-down processing is O(total size of all files), while bottom up approach is O(number of usages). The latter is much more efficient if you search only for some names, and that's what IDEs typically do (all IntelliJ based ones, and TypeScript as well). Note that, even if you have a ton of usages (like for something like From::from), you typically show only the first n in the UI, so bottom up wins even in this case.

I'd be curious to learn more about how cquery does this. Is there any document that describes how it works?

[umanwizard]

Yes, building the initial index is O(total size of all files) and can take hours on a large enough codebase. Once the index is built however, looking things up in it is instant.

Showing only the first n references is not useful, IMO -- there should at least be a flag to turn on showing all possible references. Not sure about cquery, but clangd at least supports this (with an optional flag), and even things with thousands of references work fine and instantly.

[matklad]

The main problem with such an index is not that it takes long to build it, but that it is hard to keep it up-to-date as the code changes. I think it is somewhat easier to do in C++, where there is no dependencies between .cc files, but even there, chaining an .h file will require quite a bit of work.

Showing only the first n references is not useful, IMO -- there should at least be a flag to turn on showing all possible references.

I mean that the UI that shows the results should be paginated anyway: you can't show more references than there are pixels on the screen :) For a typical IDE usage, I find such streamed/paginated results are quite handy.

It's true that for purely code-browsing purposes, building a top-down index is a better approach, but I do feel that for IDE being able to react to code changes swiftly is more important than getting instant search results for references with huge number of usages.

[umanwizard]

Thanks, I think I understand the difference in perspective better now. For me, the main value is in a tool for browsing static code -- I spend more time reading code and trying to understand it than I do editing. But I do understand your point of why a top-down approach is not ideal for the editing use-case.

[matklad]

@umanwizard for reading, specifically, there's a cool https://github.com/rust-dev-tools/cargo-src project.

[Geobert]

Does this issue has any link with #907 ?

[matklad]

#907 is subset of this, yeah, but it should work close to how find usages for local variables works now, and not like the generic search infra described here.

[viorina]

I'd like to give it a go.