opaque types: consider yeeting structural lookup

[lcnr]

We currently lookup opaque types in the opaque type storage by storing the key in a hashmap
https://github.com/rust-lang/rust/blob/b2fabe39bde5174e8d728bb85f2b8d0572c35b74/compiler/rustc_infer/src/infer/opaque_types/table.rs#L13-L14

This is annoying and brittle if the key contains inference variables or regions. If we make inference progress keys end up overlapping without us noticing. This is especially annoying for the bivariant lifetime parameters of the opaque, though that could be solved by replacing them with 'erased before putting them in storage.

One of the cases where this comes up is

fn foo() -> impl Sized {
    if false {
        let _: (u32, _)  = foo();
    }

    (Default::default(), 1i32)
}

fn bar<'a>() -> impl Sized {
    if false {
        let _: (u32, _)  = bar();
    }

    (Default::default(), 1i32) // error: can't use inference constraints from `bar()` as the regions differ
}

We also need to have the list of duplicate_entries anyways, because we do resolve infer vars in keys when returning them from canonical queries (or when canonicalizing the query input)

This has a lot of interesting side-effects and additional considerations. The opaque type storage will be more different between typing modes.

In HIR typeck

• don't need to store the currently getting inferred opaque types in the storage in general, we just keep these goals as ambiguous until we know the "definition site type" for the opaque, and then it's just eq
• do need to store a map from infer var to the opaque type keys (other way around than what we currently do), to enable <impl Iterator<Item = u32> as Iterator>::Item to normalize to u32 even while the type is still unknown
• need to store the "defining site type" once it's inferred
• when normalizing an opaque, try to eagerly compute the "definition site type" if the key is fully known.

In MIR borrowck

• the goal normalizing opaque types need to succeed right away, MIR borrowck can't delay them until we've inferred the definition site type considering regions
• this means we should just return every defining use in a list, without even trying to unify them

---

This should mostly work because outside of recursive calls, we should pretty much always eagerly normalize the opaque to its underlying type and only ever use that one. The opaque storage has only one entry in nearly all cases

I don't know how this will work at the edges and while it seems simpler, it also has some odd behavior.

Have been thinking about this as e.g. agda does not try to unify its constraints for higher kinded infer vars this way, and doing so is quite jank: It means adding a new lifetime to your function can potentially result in really odd errors (it still does as it may change it from defining to non-defining, but that's less often a problem, as returning from the function is pretty much always the defining use you want)

I would love to experiment with this and worry that by waiting until after we stabilized the new solver, doing so is significantly harder.

[lcnr]

One question is what to do with opaque<T> = Vec<?x> should we partially infer the definition site type from this to Vec<what_do_we_put_here>. If we go all the way towards supporting higher kinded infer vars, we could do

definition_site_ty: Vec<?y[T]>
`?y[T] = ?x`

creating unconstrained type variables generally sucks and I would like to avoid this

[lcnr]

one thought about borrowck, rn every defining use creates new existential regions, but again, we could have higher kinded region inference variables here and start out the opaque as

for<'a, 'b, 'c> opaque<'a, 'b, 'c> = MyType<?0['a, 'b, 'c], ?1['a, 'b, 'c]>

if we then have opaque<'static, 'static, '4> = MyType<'3, '4, '5> this succeeds, and instead of returning stuff via the opaque type storage returns ?0['static, 'static, 'c] = '3 as a constraint

member constraints are now just entirely distinct from the way opaque types are handled. To check whether there was a defining use, we just try to resolve the higher kinded region infer vars at the end of borrowck and error if we can't do so

[lcnr]

we can support both the foo and bar from the initial example as a use of opaque<'infer> = (u32, ?t) means we get the definition site type for<'a> opaque<'a> = (u32, ?fresh['a]) with a ?fresh['infer] = ?t constraint

what we won't support by doing this is

type Tait<T> = impl Sized;
fn foo<T>() -> Tait<T> {
    let x: u32 = foo::<u32>();
    let y = foo::<u32>();
    y.abs();
    1u32
}

Tait<u32> = u32 either maps to for<T> Tait<T> = T or for<T> Tait<T> = u32. Only compiles currently as normalizing the type of y gets the type of x from the storage. This already breaks if they had different region vars, so it is very brittle and not really desirable.

Very similar to the issue with ambiguous associated types #215

supporting higher kinded infer vars for all generic args also gives us a more general concept than member constraints: we can have constraints on higher kinded region infer vars, and we can just solve them without caring about opaque types.

---

MIR borrowck would start out with for<'a, 'b, T> opaque<'a, 'b, T> = Type<'?infer0['a, 'b, T], '?infer1['a, 'b, T]> and then a use opaque<'4, '7, u32> = Type<'8, '9> would give us the constraints '?infer0['4, '7, u32] = '8 and '?infer1['4, '7, u32] = '9. These constraints are then just put into the external constraints of the trait solver and we know that '?infer1['4, '7, u32] has to be one of '4, '7, or 'static, which is exactly what the current member constraints algorithm does

[lcnr]

I think higher kinded region inference vars only need to take regions are arguments 🤔 I don't think there's any way for type or consts to impact the value of the region, even in theory.

[lcnr]

cc https://rust-lang.zulipchat.com/#narrow/channel/144729-t-types/topic/higher-kinded.20inference.20and.20opaques/with/578882618

[lcnr]

Taken from https://hackmd.io/uHIc3vcTQluEahwDywzOQg.

This change significantly simplifies the implementation of opaque types. Most notably, it means handling opaque types involving placeholders a lot nicer, fixing higher-ranked opaque type goals are scuffed.

[lcnr]

Quick notes on how this diverges from the current next-solver impl (relevant in case doing this change is hard)

• the current behavior is weird and kinda broken for opaques involving placeholders higher-ranked opaque type goals are scuffed #242, don't think there's much that works rn which would break after the change
• we have structural lookup for non-universal users, meaning that two separate constraints on opaque<u32> constrain each other if there isn't a fully universal use yet, see opaque types: consider yeeting structural lookup #271 (comment)
• we have a special hacks to guide inference for fully unconstrained hidden types of opaques, by making more eager inference progress, this hack will apply less frequently. By not unifying non-universal uses with the same args, we will have more of this inference guidance. We should write examples here, I can't judge how much of a problem that is