dealing with region uniquification #127
Description
We have multiple situations where we prove a goal in one context and then later reprove it in a different one and assume that it continues to hold.
When going from typeck to codegen, we rely on instantiation and erasing regions to not change the result.
When going from typeck to borrowck, we rely on region uniquification to not change the result. We replace every region inside of the MIR body with a new unique region variable, even if we used the same region for multiple instances in the HIR. Failing to handle this can result in ambiguity errors during MIR borrowck which result in ICE: #27.
It's important to note that the only place we uniquify is MIR borrowck, which only reproves things proven by HIR typeck. We do not need to worry about uniquification outside of HIR typeck.
Problems we need to deal with if we don't uniquify regions
try_merge_responses
We must not merge candidates with equal responses or prefer trivial candidates over other potentially still ambiguous candidates.
Candidates with equal responses may no longer be equal after uniquification, so this would end up causing ambiguity.
Trivial candidates may result in region constraints after uniquification. At this point the goal will remain ambiguous/overflow as we have to start considering the other candidates to avoid incompleteness.
TypeRelating structural equality fast paths
cc #75. If normalizing an alias is ambiguous or would cause us to hit the overflow limit, then this may cause equality to no longer succeed after uniquification.
This is also relevant for a other optimizations, e.g. in rust-lang/rust#137944 we may want to add a fast path if T: Sized or Alias: Sized is in the env.
Candidate assembly structural equality fast paths
Large ParamEnvs can result in very complex trait solver cycles in cases where trying to use a where-bound requires normalizing it which has to consider all other applicable where-bounds. See github.com//issues/210 and #109.
We can avoid these hangs by not considering other where-bounds if the goal and the where-bound are structurally equal.
What are issues if we do
Uniquification prevents caching of very large goals
Region uniquification during canonicalization prevents us from caching parts of the query input, meaning that we have to walk the entire type. This results in hangs, e.g. for closures if a type is both an upvar and in the signature. It's known to affect itertools so we likely can't avoid it. Trying to reinstate the type length limit in rust-lang/rust#125507 ended up causing breakage for multiple projects, so we've reverted it in rust-lang/rust#127670.
This mostly causes issues during codegen when instantiating generic functions and when revealing the hidden type of opaque types for deeply nested async functions and iterator/future adapters. Importantly, any type which ends up in the MIR body would cause performance issues during MIR borrowck anyways.
This means uniquification during HIR typeck should not cause any major performance issues.