---
tags: weekly-meeting
---

# 2023-06-12 meeting - opaque type implementation

## goals

Walk through the implementation of opaque types in the new trait solver. Explore where this differs from the old solver and whether these changes are desirable:
- if yes, how can we prevent breaking changes when switching to the new solver
- if no, how can we have a sound impl which does not allow these

## how the new solver handles opaque types

### general idea

Opaque types are generally handled in the same way as projections.

When relating an opaque with another type, we emit a deferred `AliasRelate` goal [[source](https://github.com/rust-lang/rust/blob/77dba225c1048e5585b2cdefb7f8588bd2d2741/compiler/rustc_infer/src/infer/combine.rs#L116-L119)]. `AliasRelate` is implemented by mostly trying 3 different candidates [[source](https://github.com/rust-lang/rust/blob/77dba225c1048e5585b2cdefb7f8588bd2d2741/compiler/rustc_trait_selection/src/solve/alias_relate.rs#L15)]:
- `normalizes-to(lhs.alias_ty()?, rhs)`
- `normalizes-to(rhs.alias_ty()?, lhs)`
- `equate(lhs.alias_ty()?, rhs.alias_ty()?)` (relates the generic arguments of opaques with equal `DefId`, we prefer this over `normalizes-to` outside of coherence to guide inference)

`normalizes-to` is *where the magic happens* [[source](https://github.com/rust-lang/rust/blob/77dba225c1048e5585b2cdefb7f8588bd2d2741b/compiler/rustc_trait_selection/src/solve/opaques.rs#L10-L13)]. We check if we're in `Reveal::UserFacing`, in the defining scope of the opaque, and the opaque has [unique generic parameters as arguments](https://github.com/rust-lang/rust/blob/77dba225c1048e5585b2cdefb7f8588bd2d2741b/compiler/rustc_middle/src/ty/util.rs#L513-L516). If so, we either try to unify the `term` with the existing value for the hidden type or insert it as a new one. We then always prove the item bounds of the opaque type for the newly set hidden type.

When proving a trait or projection goal, e.g. `impl Trait: SomeTrait` or `<impl Trait as SomeTrait>::Assoc == Type`, we check all the candidates for `impl Trait` directly, without normalizing, but also use [`assemble_candidates_after_normalizing_self_ty`](https://github.com/rust-lang/rust/blob/fd0a3313f7a64cb16533030e49a271db449368c3/compiler/rustc_trait_selection/src/solve/assembly/mod.rs#L329-L333). This first tries to prove `normalizes-to(impl Trait, ?new_infer)` and then assembles candidates using `?new_infer` as the self-type instead.

At the end of HIR typeck we write the hidden types into the `TypeckResults` [[source](https://github.com/rust-lang/rust/blob/77dba225c1048e5585b2cdefb7f8588bd2d2741b/compiler/rustc_hir_typeck/src/writeback.rs#L546)]. At the start of MIR typeck we prepopulate the hidden type storage of our inference context [[source](https://github.com/rust-lang/rust/blob/77dba225c1048e5585b2cdefb7f8588bd2d2741b/compiler/rustc_borrowck/src/type_check/mod.rs#L1030)]. At the end of MIR typeck we remap opaque types to their definition parameters and store them for use by `type_of` [[source](https://github.com/rust-lang/rust/blob/77dba225c1048e5585b2cdefb7f8588bd2d2741b/compiler/rustc_borrowck/src/region_infer/opaque_types.rs#L61-L65)]. This only differs from the old implementation in that we prepopulate the opaque types in MIR typeck.

### tracking the defining scope

The defining scope for opaques is tracked via the `DefiningAnchor`, an immutable field of the `InferCtxt`, set at creation time.

Unlike the existing implementation, the new implementation does not use `DefiningAnchor::Bubble` and we instead pass the `DefiningAnchor` and all previously defined hidden types into canonical queries as an argument [[source](https://github.com/rust-lang/rust/blob/77dba225c1048e5585b2cdefb7f8588bd2d2741b/compiler/rustc_middle/src/traits/solve.rs#L99-L104)]. We then return only the newly added opaque types in the query response [[source](https://github.com/rust-lang/rust/blob/77dba225c1048e5585b2cdefb7f8588bd2d2741b/compiler/rustc_middle/src/traits/solve.rs#L151)]. Inference constraints on the previously defined opaque are returned via changes to the [`CanonicalVarInfos`](https://github.com/rust-lang/rust/blob/77dba225c1048e5585b2cdefb7f8588bd2d2741b/compiler/rustc_middle/src/infer/canonical.rs#L40).

### MIR typeck and nll region variables

There are some subtleties on how we deal with existential region variables, going to skip them for now as these aren't yet fully fleshed out. This will probably result in breakage when defining the same opaque with different lifetimes, but I don't expect this to be significant (https://github.com/rust-lang/trait-system-refactor-initiative/issues/17).

### replacing `DefiningAnchor::Bubble` in the remaining uses

The old solver currently uses `DefiningAnchor::Bubble` outside of canonical queries. These uses are inside of a body, after HIR typeck, but before `Reveal::All`. This means that they may encounter unnormalized opaque types defined by typechecking this body. The plan for the new solver is to instead use `DefiningAnchor::Error` there, but prepopulate the opaque type storage using the types from either HIR or MIR typeck. [[source](https://github.com/rust-lang/rust/blob/77dba225c1048e5585b2cdefb7f8588bd2d2741b/compiler/rustc_borrowck/src/region_infer/opaque_types.rs#L308)] [[source](https://github.com/rust-lang/rust/blob/77dba225c1048e5585b2cdefb7f8588bd2d2741b/compiler/rustc_const_eval/src/util/compare_types.rs#L44-L45)] [[source](https://github.com/rust-lang/rust/blob/77dba225c1048e5585b2cdefb7f8588bd2d2741b/compiler/rustc_traits/src/codegen.rs#L32-L36)]

We can then remove `DefiningAnchor::Bubble` and may end up only using `DefiningAnchor::Bind` in HIR typeck, prepopulating the storage everywhere else. This isn't yet fully implemented

## changes from the existing implementation

errs wrote a doc tracking the currently failing tests with opaque types https://docs.google.com/spreadsheets/d/1x0O4_uhl6jOpquI9sfKYmoniZZ7YFETbBk3di2Z7k0s/edit#gid=0. A lot of these are still bugs of the current impl and not actual breakage.

### trait solving constraining opaque types

`DefineOpaqueTypes::No` in the existing solver causes relate to treat opaque types as rigid [[source](https://github.com/rust-lang/rust/blob/77dba225c1048e5585b2cdefb7f8588bd2d2741b/compiler/rustc_infer/src/infer/equate.rs#L104-L107)]. This is used pretty much everywhere inside of the old trait solver. The new solver always allows opaques in the defining scope to be defined. Emulating the existing behavior of the old solver would require some hacks. While the old behavior mostly exists for `DefiningAnchor::Bubble`, it does result in some behavior change.

This is incompatible in both directions:

// passes with the new impl, fails with the old one.
trait Trait {}
impl Trait for Vec<u32> {}
fn impls_trait<T: Trait>(x: T) -> T { x }

fn foo(b: bool) -> impl Sized {
    if b {
        impls_trait(foo(false))
       //[old]~^ ERROR the trait bound `impl Sized: Trait` is not satisfied
    } else {
        Vec::new()
    }
}

and

// passes with the old impl, ambiguous with the new one.
#![feature(type_alias_impl_trait)]
trait Trait<T> {}

impl Trait<u32> for u32 {}

impl<T> Trait<i32> for T {}

type Tait = impl Sized;

fn impls_trait<T: Trait<U>, U>(x: T) {}

fn foo(x: Tait) {
    let _: u32 = x;
    impls_trait(x);
    //[new]~^ ERROR type annotations needed
    //[new]~| NOTE cannot infer type of the type parameter `U` declared on the function `impls_trait`
}

### normalizes-to ambiguity

// passes with old impl, ambiguous with the new one.
#![feature(type_alias_impl_trait)]
trait Trait {
    type Assoc;
}
impl<T: Copy> Trait for T {
    type Assoc = T;
}
fn needs_trait<T: Trait<Assoc = T>>() {}

type Tait = impl Copy;

fn define() -> Tait {}

fn check() {
    needs_trait::<Tait>();
    //[new]~^ ERROR type annotations needed
    //[new]~| NOTE cannot satisfy `<Tait as Trait>::Assoc == Tait`
}

fn main() {}

If we have a trait or projection goal with an opaque type as the self type in the defining scope, the old impl treats the opaque completely opaquely. In the new impl we also try to normalize the opaque to its hidden type and then assemble candidate for that. Given that the hidden type isn't constrained in any other way, we end up with `?hidden_ty_infer_var: Trait` which is ambiguous.

For trait goals this doesn't cause issues, as using `impl<T: Copy> Trait for T` without normalizing `Tait` is trivially true, so we simply prefer that over the ambiguity after normalizing the self type.

This is different for projection goals, proving `Projection(<Tait as Trait>::Assoc, Tait)` tries to prove `Projection(<Tait as Trait>::Assoc, ?unconstrained_var)` [[source](https://github.com/rust-lang/rust/blob/fd0a3313f7a64cb16533030e49a271db449368c3/compiler/rustc_trait_selection/src/solve/project_goals.rs#L28-L56)]. This means that the impl candidate also guides inference: it constrains `?unconstrained_var` to `Tait`. We therefore have 2 ambiguous candidates and fail to make progress.

While this exact issues may be fixable, I expect the more general case of "trait solving forces an opaque type in the defining scope to actually get defined, resulting in ambiguity" will remain at least a theoretically breaking change.

### relating opaques to other opaques doesn't error anymore

The desired behavior when relating two opaques in their defining scope is subtle, so the old implementation always emits a hard error in this case [[source](https://github.com/rust-lang/rust/blob/fd0a3313f7a64cb16533030e49a271db449368c3/compiler/rustc_infer/src/infer/opaque_types.rs#L151-L166)]. There is no such check in the new solver (and we would be missing the span to sensibly emit that error without a non-trivial implementation effort). This means that the following code will compile with the new implementation:

#![feature(type_alias_impl_trait)]
struct Bar;
type A = impl Sized;
type B = impl Sized;

fn muh(x: A) -> B {
    if false {
        return Bar; // B's hidden type is Bar
    }
    x // A's hidden type is `Bar`, because all the hidden types of `B` are compared with each other
}

I feel comfortable allowing this as it "falls out" of the implementation in the new solver.

## summary

The list of changes is probably incomplete and we will find more issues via crater. I am less worried about the old implementation after writing that doc, at least based on the issues found while writing it.

I would like to emulate the behavior of https://hackmd.io/llGcGMR7SvCP1C1MulcDQw#MIR-typeck-and-nll-region-variables in the old solver as well:

trait Trait<'a, 'b> {}
impl<'a, 'b, T> Trait<'a, 'b> for T {}

#[derive(Copy, Clone)]
struct Inv<'a>(*mut &'a ());

// `foo` defines both `impl Trait<'a, 'b>` and `impl Trait<'b, 'a>`.
// 
// We could change the final collection of opaque types in the old
// implementation to equate all defining uses which only differ in
// region parameters. This will cause this example to fail in both
// the new and the old implementation.
fn foo<'a, 'b>(x: Inv<'a>, y: Inv<'b>, b: bool) -> impl Trait<'a, 'b> {
    if b {
        let _: Inv<'b> = foo(y, x, false);
    }

    x
}

### how do define opaques during trait solving in the old impl

I am more worried about trait solving now defining opaque types and would like to move the existing impl towards this. I do not think that we should change the new solver here. I cannot think of a good implementation which 1) does not eagerly replace opaque types with inference variables and 2) does not infer opaque types via trait solving.

#### the straightforward approach

Stop using `DefineOpaqueTypes::No` in as many places as possible. Equating an opaque type in its defining scope should not treat that type as rigid. This does not work with `DefiningAnchor::Bubble` as we still have to treat foreign opaque types as rigid.

This also causes issues because the selection cache currently does not track the defining scope which will get a lot easier to trigger. ||It is already broken, just harder to trigger :<||. We should try only caching goals in the `InferCtxt::selection_cache` if they mentioned an opaque type [[old trait solver caches doc](https://hackmd.io/1OmN5Oj4SL-PzAYsJyktwA)].

For this, we also want to end up not using `Bubble` in queries but instead pass in the defining anchor. With https://github.com/rust-lang/rust/issues/112453 the performance hit from doing this may not be too bad. We can even filter opaque types which are unreachable.

## Comments and questions

### I have a question or comment, what do I do?

Add a new header to this section and write your question or comment here.

### clarification on final example

nikomatsakis: The final example includes this:

fn foo<'a, 'b>(x: Inv<'a>, y: Inv<'b>, b: bool) -> impl Trait<'a, 'b> {

and suggests that it fails in the new implementation -- does it not fail in the old implementation? It's not stated explicitly.

lcnr: yes, works in old, fails in new, defines `impl Trait<'a, 'b> = Inv<'a>` and `impl Trait<'b, 'a> = Inv<'b>` separately which are equal after remapping generic arguments into the context of the opaque type itself.

### clarification: defining anchor bubble and friends

[Zulip](https://rust-lang.zulipchat.com/#narrow/stream/326132-t-types.2Fmeetings/topic/2023-06-12.20TAIT.20in.20new.20solver/near/365584064)

nikomatsakis: I'm not 100% sure this is worth covering, but I don't really know what the different "defining anchor" modes mean

### summarizing the new approach

nikomatsakis: I'm going to take a stab at summarizing the high-level strategy for the new solver as I understood it from reading this document. Can you clarify if it is correct?

* Inference context contains, and canonicalization therefore is extended to include,
* a set of TAITs *and RPIT* that are being defined by current item
* for a subset of the above, a set of definitions, mapping from "Projection -> Type"
* this projection I *think* is not higher-ranked? i.e., if we constrain `Trait<X> = X`, it would store `Tait<X> = X`, not `for<T> Tait<T> = T`.
* In trait solving:
* we attempt to normalize TAITs that have a definition (lcnr: all of them, existing definitions only change the normalized-to type)
* and maybe even those that don't? sounds like at lease some of the time we would normalize to an unbound inference variable
* you can solve a trait or projection based either on the TAIT bounds or by the new normalized form

Implications:

* Slower performance (see below) as a result of poor cache performance from canonicalization?
* can't deduplicate quite as much by making the defined opaques part of the cache key
* Trait solver is willing to normalize which yields
* *some cases work* because we will reveal the normalized form and can also do things like equate one TAIT to another
* *some cases are more ambiguous* because before we only worked on the opaque form
* lcnr: :thumbsup:

### lcnr: what perf hit with old solver is acceptable

I think removing bubble, even with https://github.com/rust-lang/rust/issues/112453 will end up causing a ~5-10% regression in async heavy crates. This is acceptable to me and I would like your vibes here.

### What are we deciding today?

[Zulip](https://rust-lang.zulipchat.com/#narrow/stream/326132-t-types.2Fmeetings/topic/2023-06-12.20TAIT.20in.20new.20solver/near/365586002)

nikomatsakis: I want to clarify the role of this meeting.