** Here is a draft of what is intended to be rustc-dev-guide chapter, Please feel free to edit.**

# Opaque types region inference

In this section we discuss the various restrictions we impose on the generic arguments of opaque types when defining their hidden types
`Opaque<'a, 'b, .., A, B, ..> := SomeHiddenType`.

## Background: type arguments
For type arguments, two restrictions are necessary: each type argument must be (1) a type parameter and (2) is unique among the generic arguments.
Example of case (1):

type Opaque<X> = impl Sized;

// `T` is a type paramter.
// Opaque<T> := ();
fn good<T>() -> Opaque<T> {}

// `()` is not a type parameter.
// Opaque<()> := ();
fn bad() -> Opaque<()> {} //~ ERROR

Example of case (2):

type Opaque<X, Y> = impl Sized;

// `T` and `U` are unique in the generic args.
// Opaque<T, U> := T;
fn good<T, U>(t: T, _u: U) -> Opaque<T, U> { t }

// `T` appears twice in the generic args.
// Opaque<T, T> := T;
fn bad<T>(t: T) -> Opaque<T, T> { t } //~ ERROR

**Motivation:** In the first case `Opaque<()> := ()`, the hidden type is ambiguous because it is compatible with two different interpretaions: `Opaque<X> := X` and `Opaque<X> := ()`. Similarily for the second case `Opaque<T, T> := T`, it is ambiguous whether it should be interpreted as `Opaque<X, Y> := X` or as `Opaque<X, Y> := Y`. Because of this ambiguity, both cases are rejected as invalid defining use.

## Uniqueness restriction

> With the exception below, all lifetime args must be unique in the arguments list and must not be `'static`. This is in order to avoid an ambiguity with hidden type inference similar to the case of type parameters. For example, the invalid defining use below `Opaque<'static> := Inv<'static>` is compatible with both `Opaque<'x> := Inv<'static>` and `Opaque<'x> := Inv<'x>`.

type Opaque<'x> = impl Sized + 'x;
type Inv<'a> = Option<*mut &'a ()>;

fn good<'a>() -> Opaque<'a> { Inv::<'static>::None }

fn bad() -> Opaque<'static> { Inv::<'static>::None }
//~^ ERROR

// This is also invalid because `'a` is *semantically* equal to `'static`.
fn still_bad<'a: 'static>() -> Opaque<'a> { Inv::<'static>::None }
//~^ Should error!

type Opaque<'x, 'y> = impl Trait<'x, 'y>;

fn good<'a, 'b>() -> Opaque<'a, 'b> {}

fn bad<'a>() -> Opaque<'a, 'a> {}
//~^ ERROR

// This is also invalid because `'a` and `'b` are *semantically* equal.
fn still_bad<'a: 'b, 'b: 'a>() -> Opaque<'a, 'b> {}
//~^ Should error!

**Status:**
- [ ] For TAIT, semantic equality of lifetimes are not always used in this check. This leads to the surprising behavior in [#112841][].
- [ ] For RPIT, this check is not implemented at all (see next section for why).

[#112841]: https://github.com/rust-lang/rust/issues/112841

## A proposed exception to uniqueness rule

- An exception to the uniqueness rule above is when the bounds on opaque type's **definition** requires that a lifetime parameter be equal to another one or to the `'static` lifetime.

// The definition requires `'x` to be equal to `'static`.
type Opaque<'x: 'static> = impl Sized + 'x;

fn good() -> Opaque<'static> {}

**Motivation:** an attempt to implement the uniqueness restriction for RPITs resulted in a [breakage found via crater]( https://github.com/rust-lang/rust/pull/112842#issuecomment-1610057887). This can be mitigated by this exception to the rule. An example of the the code that would otherwise break:

struct Type<'a>(&'a ());
impl<'a> Type<'a> {
    // `'b == 'a`
    fn do_stuff<'b: 'a>(&'b self) -> impl Trait<'a, 'b> {}
}

**Why this is correct:** for such a defining use like Opaque<'a, 'a> := &'a str, it can be interpreted in either way—either as Opaque<'x, 'y> := &'x str or as Opaque<'x, 'y> := &'y str and it wouldn't matter because every use of `Opaque` will guarantee that both parameters are equal as per the well-formedness rules.

**Status:**
- [ ] Not implemented. Issue #113916.

## Universal lifetimes restriction

- Only universally quantified lifetimes are allowed in the opaque type arguments. This includes lifetime parameters and placeholders.

type Opaque<'x> = impl Sized + 'x;

fn test<'a>() -> Opaque<'a> {
    // `Opaque<'empty> := ()`
    let _: Opaque<'_> = ();
    //~^ ERROR
}

**Motivation:** This makes the lifetime and type argums behave consistently but this is only as a bonus. The real reason behind this restriction is purely technical, as the "member constraints" algorithm faces a fundamental limitation: When encountering an opaque type definition `Opaque<'?1> := &'?2 u8`, a member constraint `'?2 :belongs_to: ['static, '?1]` is registered. In order for the algorithm to pick the right choice, the *complete* set of "outlives" relationships between the choice regions `['static, '?1]` must already be known *before* doing the region inference. This can be satisfied only if each choice region is either:
1. a universal region, i.e. `RegionKind::Re{EarlyParam,LateParam,Placeholder,Static}`, because the relations between universal regions are completely known, prior to region inference, from the explicit and implied bounds.
1. or an existential region that is "strictly equal" to a universal region. Strict lifetime equality is defined below and is required here because it is the only type of equality that can be evaluated prior to full region inference.

**Strict lifetime equality:** We say that two lifetimes are strictly equal if there are bidirectional outlives constraints between them. In NLL terms we say that the lifetimes are part of the same [SCC]. Importantly this type of equality can be evaluated prior to full region inference (but of course after constraint collection). The other type of equality is when region inference ends up giving two lifetimes variables the same value even if they are not strictly equal. See [#113971] for how we currently mess this up.

**Status:**
- [ ] Strict lifetime equality is not yet enforced and this gives rise to arguably behavior (see [#113971][]).
- [ ] For RPIT, if the lifetime is not universal the compiler panics with message `opaque type with non-universal region substs` [#110726](https://github.com/rust-lang/rust/issues/110726)

[#113971]: https://github.com/rust-lang/rust/issues/113971

**interaction with "once modulo regions" restriction** In the example above, note the opaque type in the signature is `Opaque<'a>` and the one in the invalid defining use is `Opaque<'empty>`. In the proposed MiniTAIT plan, namely the ["once modulo regions"][#116935] rule, we already disallow this.
Although it might appear that "universal lifetimes" restriction becomes redundant as it logically follows from "MiniTAIT" restrictions, the subsequent related discussion on lifetime equality and closures remains relevant.

[#116935]: https://github.com/rust-lang/rust/pull/116935

## Closure restrictions

- When the opaque type is defined in a closure/coroutine/inline-const body, universal lifetimes that are "external" to the closure are not allowed in the opaque type arguments. External regions are defined in [`RegionClassification::External`](https://github.com/rust-lang/rust/blob/caf730043232affb6b10d1393895998cb4968520/compiler/rustc_borrowck/src/universal_regions.rs#L201).

Example: (This one happens to compile in the current nightly but more practical examples are already rejected with confusing errors. See [#105498][] for more).

type Opaque<'x> = impl Sized + 'x;

fn test<'a>() -> Opaque<'a> {
    let _ = || {
        // `'a` is external to the closure
        let _: Opaque<'a> = ();
        //~^ Should be an error!
    };
    ()
}

**Motivation:** In closure bodies, external lifetimes, although being categorized as "universal" lifetimes, behave more like existential lifetimes in that the relations between them are not known ahead of time, instead their values are inferred just like existential lifetimes and the requirements are propagated back to the parent fn. This breaks the member constraints algorithm as described above:
> In order for [the algorithm] to pick the right choice, the complete set of “outlives” relationships between the choice regions ['static, '?1] must already be known before doing the region inference

Here is an example that details how

type Opaque<'x, 'y> = impl Sized;

// 
fn test<'a, 'b>(s: &'a str) -> impl FnOnce() -> Opaque<'a, 'b> {
    move || { s }
    //~^ ERROR hidden type for `Opaque<'_, '_>` captures lifetime that does not appear in bounds
}

// The above closure body is desugared into something like:
fn test::{closure#0}(_upvar: &'?8 str) -> Opaque<'?6, '?7> {
    return _upvar
}

// where `['?8, '?6, ?7] are universal lifetimes *external* to the closure.
// There are no known relations between them *inside* the closure.
// But in the parent fn it is known that `'?6: '?8`.
//
// When encountering an opaque definition `Opaque<'?6, '?7> := &'8 str`,
// The member constraints algotithm does not know enough to safely make `?8 = '?6`.
// For this reason, it errors with a sensible message:
// "hidden type captures lifetime that does not appear in bounds".

Without this restrictions error messages are consfusing and, more impotantly, there is a risk that we accept code the we would likely break in the future because member constraints are super broken in closures.

**Status:**
- [ ] Unimplemented, leading to surprising behavior and risking forward compatibility. [#105498][]

[#105498]: https://github.com/rust-lang/rust/issues/105498

**Output types:** I believe the most common scenario where this causes issues in real-world code is with closure/async-block output types. It is worth noting that there is a discrepancy betweeen closures and async blocks that further demonstrates this issue and is attributed to the [hack of `replace_opaque_types_with_inference_vars`](https://github.com/rust-lang/rust/blob/9cf18e98f82d85fa41141391d54485b8747da46f/compiler/rustc_hir_typeck/src/closure.rs#L743), which is applied to futures only.

type Opaque<'x> = impl Sized + 'x;
fn test<'a>() -> impl FnOnce() -> Opaque<'a> {
    // Output type of the closure is Opaque<'a>
    // -> hidden type definition happens *inside* the closure
    // -> rejected.
    move || {}
    //~^ ERROR expected generic lifetime parameter, found `'_`
}

use std::future::Future;
type Opaque<'x> = impl Sized + 'x;
fn test<'a>() -> impl Future<Output = Opaque<'a>> {
    // Output type of the async block is unit `()`
    // -> hidden type definition happens in the parent fn
    // -> accepted.
    async move {}
}