Solving closure goal keeps expanding lifetimes #688
Description
Found in rust-analyzer#7796:
When trying to solve this goal:
Implemented({closure:ClosureId(3)}<[?0 := () for<0> [
?0 := (&'static 2<[?0 := ^1.0, ?1 := (&'static ^1.1)]>),
?1 := (&'static 2<[?0 := ^1.2, ?1 := ^1.1]>),
?2 := Ordering<[]>]
]> : FnMut<2<[
?0 := (&'static 2<[?0 := ^0.3, ?1 := ^0.4]>),
?1 := (&'static 2<[?0 := ^0.3, ?1 := ^0.4]>)
]>>)Chalk keeps expanding the query when trying to normalize this:
Normalize(<{closure:ClosureId(3)}<[?0 := () for<0> [
?0 := (&'static 2<[?0 := ^1.0, ?1 := EXPAND_1]>),
?1 := (&'static 2<[?0 := ^1.36, ?1 := EXPAND_2]>),
?2 := Ordering<[]>]
]> as FnOnce<2<[
?0 := (&'static 2<[?0 := ^0.38, ?1 := EXPAND_3]>),
?1 := (&'static 2<[?0 := ^0.38, ?1 := EXPAND_3)]>)
]>>>::Output -> Ordering<[]>)
EXPAND_1 = (&'^1.1 (&'^1.2 (&'^1.3 ... (&'^1.34 ^1.35))))
EXPAND_2 = (&'^1.2 (&'^1.3 (&'^1.4 ... (&'^1.34 ^1.37))))
EXPAND_3 = (&'static (&'static ... (&'static ^0.39)))It's tricky to translate the rust-analyzer example to a chalk test case because closures are involved, but hopefully this should be enough info to make the problem clear.
Metadata
Metadata
Assignees
Type
Projects
Milestone
Relationships
Development
No branches or pull requests
Participants
Activity
detrumi commentedon Feb 27, 2021
rust-analyzer#7680 might also be related, as that keeps expanding nested queries with dyn/AliasEq, again inside a closure substitution.
chore: fix so rust_analyzer works again
jackh726 commentedon Mar 14, 2021
I'm still having trouble creating a chalk test case that repros this. @detrumi do you think you could capture a
CHALK_DEBUGlog up to a couple rounds of expansion?I have a feeling this might be caused by the difference in representation between the chalk-integration closure substs and rust-analyzer/rustc closure substs
detrumi commentedon Mar 14, 2021
@jackh726 Sure! It's a lot of output, but I think this shows the first few repeats:
The full ist of solve queries that happened before might also be useful:
Full output for completeness, which also shows chalk programs:
https://gist.github.com/detrumi/a7112751e901bbbd864a83e011f93cae
For reference, this was output from the following:
flodiebold commentedon Mar 14, 2021
I think the difference that's likely the source of problems is that rust-analyzer (and I think I got this from rustc) puts the closure signature in a function pointer type in the substs. (rustc puts some more stuff in there, we currently only have the signature.)
Especially the fact that it's in a function pointer may be relevant, since that's caused problems because of variance already.
flodiebold commentedon Mar 14, 2021
It's also worth noting that rust-analyzer never passes any lifetimes except
'staticto Chalk.jackh726 commentedon Mar 14, 2021
@detrumi so the output there only shows
chalk_recursivetracing output, which isn't super helpful. Haven't looked into how rust-analyzer enables the logging, but I would expect to also seechalk_solveoutput.@flodiebold yeah, I'm wondering if we're relating all the substs somewhere that we should only be relating the "function substitution"
jackh726 commentedon Mar 14, 2021
Yeah, actually, I bet this is happening because we call
generalize_substitutionon the whole closure substitutionanalysis-statshangs with fixed-point combinator rust-analyzer#9813JakobDegen commentedon Nov 15, 2021
After #733 this reproduces as
on the recursive solver only
jackh726 commentedon Nov 28, 2021
@JakobDegen just now finding some time to look at this and #733. Sorry for the delay. Shouldn't the repro for this end up with a hang, instead of an answer?
JakobDegen commentedon Nov 28, 2021
Yeah should have clarified, that test does hang on the recursive solver on my branch; the answer in the test is needed so that this passes the SLG solver, as otherwise the recursive solver doesn't even run.
jackh726 commentedon Nov 28, 2021
Ah okay. For future reference, you can use
} yields[SolverChoice::recursive_default()] {to restrict to only the recursive solver!Are you up for trying to fix this? (The work done in #733 is great, but I need to go through it more thoroughly; can definitely work on fixing the actual problem concurrently though). If so, feel free to reach out on Zulip if you have questions or run into problems :)
JakobDegen commentedon Nov 29, 2021
That's good to know, thanks!
I am definitely interested in it, but time is currently a bit of an issue for me. I'm hoping to get around to looking at chalk more within the next two weeks; I'll claim the issue at that point if no one else has gotten started before then.