Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Deduplicate references when some of them are in macro expansions #16358

Merged
merged 2 commits into from
Feb 19, 2024

Conversation

krobelus
Copy link
Contributor

@krobelus krobelus commented Jan 14, 2024

EDIT: I wonder if this is a regression, I'll try to investigate.

Commit 6a06f6f (Deduplicate reference search results, 2022-11-07)
deduplicates references within each definition.

Apparently our descend_into_macros() stanza returns
one definition for each time a name is used in a macro.
Each of those definitions has the same set of references.
We return them all, leading to many redundant references.

Work around this by deduplicating definitions as well. Perhaps there
is a better fix to not produce duplicate definitions in the first
place.

I discovered this working with the "bitflags" macro from the crate
of the same name.

Fixes #16357

@rustbot rustbot added the S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. label Jan 14, 2024
Comment on lines 123 to 129
Some(
find_defs(sema, &syntax, position.offset)?
.into_iter()
.unique()
.map(search)
.collect(),
)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Hmm, this won't fix the linked issue though. In that issue, all the occurences are different Definitions! We already do deduplicate the results, its just the the resulting NavigationTargets differ in properties that are not relevant to the shown results, so we need to do another deduplication pass when we convert to the requests response.

The deduplication should happen on the references before we return the ReferenceSearchResult here:

});
ReferenceSearchResult { declaration, references }

That is we need to go through all value Vecs of the map, sort, and deduplicate them there.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Hmm, this won't fix the linked issue though.

Good catch - that's because in that case the definitions are actually different, so unique() doesn't eliminate them, and because of the macro weirdness producing a cartesian product of references we also get redundant references along the technically-unique definitions.

The deduplication should happen on the references before we return the ReferenceSearchResult here:

The results of the lambda created by make_searcher are already deduplicated. The problem is that we call said lambda multiple times and concatenate the results.

@Veykril Veykril added S-waiting-on-author Status: This is awaiting some action (such as code changes or more information) from the author. and removed S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. labels Jan 16, 2024
}
fn test() {
let name = ();
use_name!(name$0);
Copy link
Contributor Author

@krobelus krobelus Jan 16, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Apparently our descend_into_macros() stanza returns one definition for
each time a name is used in a macro.

Sorry this was misleading. It's not about definitions but all references.

Given

macro_rules! use_name {
    ($name:ident) => {
        println!("{}", $name);
        println!("{}", $name);
        println!("{}", $name);
    };
}
fn test() {
    let name = 123;
    use_name!(name);
    println!("{}", name);
    println!("{}", name);
}

so 3 references inside the macro, and 4 outside;
this will produce 12 references; it's the product. Not sure if this is expected but I guess I haven't seen another problem with it.

It only surfaced when there was a definition inside a macro because we already deduplicate the per-definition references.

I think your suggestion makes sense; I'll try it and maybe get rid of the other two unique() calls.

@krobelus krobelus force-pushed the fix-redundant-references-with-macros branch from 0fa227a to 02d551c Compare January 17, 2024 07:28
Copy link
Member

@Veykril Veykril left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ah okay, now I see the general problem. In that case, find_all_refs is working correctly. We already deduplicate references per Definition, and these definitions have more semantic information so we don't wanna deduplicate any further at this stage. What we do wanna do is deduplicate at the LSP layer, as that's where most of this info becomes useless.

That is we want to deduplicate here https://github.com/veykril/rust-analyzer/blob/4cab41156ac820c83e7eb3488efd2be43f9fc7a7/crates/rust-analyzer/src/handlers/request.rs#L1067-L1090 and here https://github.com/veykril/rust-analyzer/blob/4cab41156ac820c83e7eb3488efd2be43f9fc7a7/crates/rust-analyzer/src/handlers/request.rs#L1807-L1815

@krobelus krobelus force-pushed the fix-redundant-references-with-macros branch from 02d551c to 131b649 Compare January 28, 2024 19:14
@krobelus
Copy link
Contributor Author

ok that makes sense

Comment on lines 1097 to 1107
fn deduplicate_declarations(refs: &mut Vec<ReferenceSearchResult>) {
if refs.iter().filter(|decl| decl.declaration.is_some()).take(2).count() > 1 {
let mut seen_declarations = HashSet::new();
refs.retain(|res| {
res.declaration.as_ref().is_none_or(|decl| seen_declarations.insert(decl.nav.clone()))
});
}
}

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This may still end up with multiple overlapping links, we need to do the filtering after we turned the ReferenceSearchResults into Locations, then dedup on those locations (this transformation, to_proto::location is where we lose the unnecessary data that prevented the deduplication from working as intended in the first place).

That's why I linked to specify lines in my earlier review, sorry that I wasn't clear enough with that.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

we should probably find a test case. My variable name seen_declarations is misleading because we actually insert navigation targets here, which should be what we want to duplicate on?

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

No we do not want to deduplicate NavigationTargets, we want to deduplicate lsp Locations. The nav targets haave a lot of info that differs even though the pointed to ranges are the same hence why deduplicating them is non trivial (and also wrong!). once we transformed them to locations we lose all the differing info of the nav targets that are irrelevant for the feature so now the deduplication does meaningful work (and is trivial to implement).

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We should probably do the same for goto_definition_response

@krobelus krobelus force-pushed the fix-redundant-references-with-macros branch from 131b649 to 27ed99b Compare January 29, 2024 16:38
@Veykril Veykril force-pushed the fix-redundant-references-with-macros branch from 27ed99b to daaa791 Compare February 19, 2024 11:22
krobelus and others added 2 commits February 19, 2024 12:23
Commit 6a06f6f (Deduplicate reference search results, 2022-11-07) deduplicates references
within each definition.

There is an edge case when requesting references of a macro argument.  Apparently, our
descend_into_macros() stanza in references.rs produces a cartesian product of
- references inside the macro times
- times references outside the macro.

Since the above deduplication only applies to the references within a single definition, we
return them all, leading to many redundant references.

Work around this by deduplicating definitions as well.  Perhaps there is a better fix to not
produce this cartesian product in the first place; but I think at least for definitions the
problem would remain; a macro can contain multiple definitions of the same name, but since the
navigation target will be the unresolved location, it's the same for all of them.

We can't use unique() because we don't want to drop references that don't have a declaration
(though I dont' have an example for this case).

I discovered this working with the "bitflags" macro from the crate of the same name.

Fixes rust-lang#16357
@Veykril Veykril force-pushed the fix-redundant-references-with-macros branch from daaa791 to 91a8f34 Compare February 19, 2024 11:24
@Veykril
Copy link
Member

Veykril commented Feb 19, 2024

Thanks!
@bors r+

@bors
Copy link
Contributor

bors commented Feb 19, 2024

📌 Commit 91a8f34 has been approved by Veykril

It is now in the queue for this repository.

@bors
Copy link
Contributor

bors commented Feb 19, 2024

⌛ Testing commit 91a8f34 with merge d8c8ccc...

@bors
Copy link
Contributor

bors commented Feb 19, 2024

☀️ Test successful - checks-actions
Approved by: Veykril
Pushing d8c8ccc to master...

@bors bors merged commit d8c8ccc into rust-lang:master Feb 19, 2024
11 checks passed
@krobelus
Copy link
Contributor Author

Deduplicating unconditionally seems not very elegant to me, that's why I prefer for a targeted fix.
I'd be surprised if there was a case where the extra deduplication helps.
For goto the original problem doesn't happen, probably because it only returns the definition that is active at the macro call site.
Unfortunately I haven't had time to dive into this

@Veykril
Copy link
Member

Veykril commented Feb 19, 2024

Deduplicating unconditionally seems not very elegant to me, that's why I prefer for a targeted fix.

I personally find this approach a lot cleaner (and more importantly simpler!). We want to prevent to send duplicate entries in the LSP response from appearing, so it only makes sense to deduplicate at that layer, not prior to the lossy transformation. Deduplicating before we discard the unimportant bits means we might not deduplicate something that ends up the same post-lsp transformation. This doesn't mean it is necessarily the case right now (though I am fairly sure that can be achieved), but if NavigationTarget gets another new field in the future this could change.

Unfortunately I haven't had time to dive into this

No worries, I am currently aggressively going through the open PRs to lower the number, otherwise I would've left this open until you had time to get back to this.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
S-waiting-on-author Status: This is awaiting some action (such as code changes or more information) from the author.
Projects
None yet
Development

Successfully merging this pull request may close these issues.

References expanded from macros are redundant
4 participants