This write-up documents the effects of the new "lazy TAIT" inference algorithm implemented in PR #94081.
It begins with a write-up explaining the algorithm "from first principles" -- i.e., how a user should understand it. It then explains some of the implications, and cases where this differences from the current stabilized behavior.
When you define an impl trait in "existential" position:
type Foo = impl Debug;
fn foo() -> Foo { 22_u32 }
// Or, (mostly) equivalently:
fn foo() -> impl Debug { 22_u32 }this corresponds to an "opaque type" O. For each opaque type, the compiler has the job of determining exactly what type T_hidden it represents (u32, in our example). This is called the hidden type of O. T_hidden is called the hidden type because, for the most part, other code cannot rely on it. Instead, that code treats O opaquely -- i.e., as "some type that implements Debug". This means that it can determine that O: Debug, but not that O: Eq, even though u32: Eq is true. The only exception is with autotraits: other code can figure out that O: Send because u32: Send. This is called "auto trait leakage", and it will be discussed later.
How the compiler infers the hidden type
The compiler infers the hidden type for an opaque type by looking at how that opaque type is used within its defining scope. The defining scope is defined as all code within whatever "container" declared the opaque type:
- For type-alias-impl-trait (
type Foo = impl Debug), the defining scope is the enclosing function, module, or impl. - For return-position-impl-trait (
fn foo() -> impl Debug), the defining scope is the body of the functionfoo.
For the remainder of this discussion, we'll work with the example of a type-alias-impl-trait like so:
type Foo = impl Debug;When type-checking code within the defining scope of Foo, we may encounter variables or values that are declared to be of type Foo, like the local variable x in this example:
type Foo = impl Debug;
fn example() {
let x: Foo = 22_u32;
...
}To be well-typed, this code requires that u32 be a subtype of Foo. Outside of the defining scope, that would be an error -- but inside the defining scope, it is instead adopted as a constraint on what type Foo can represent. Therefore, example constrains Foo's hidden type to be u32 in this case.
The same applies to the more common case of a function whose return type is declared as an opaque type:
type Foo = impl Debug;
fn make_foo() -> Foo {
22_u32
}make_foo also constrains Foo's hidden type to be u32.
Another way to get a value of an opaque type is through a recursive call, or through a call to another function within the defining scope:
type Foo = impl Debug;
fn make_foo() -> Foo {
let mut x: Foo = make_foo();
x = 22_u32;
x
}
fn make_bar() -> Foo {
let x: Foo = make_foo();
22_u32
}These functions both constrain Foo to be equal to u32.
When a function imposes a constraint, it must be a complete type:
type Foo = impl Debug;
fn insufficient() {
// ERROR: Requires `Foo = Option<T>`, but what is `T`?
let x: Foo = None;
}Note though that the function can apply multiple constraints, which together suffice to fully specify the hidden type:
type Foo = impl Debug;
// Constrains `Foo = Result<u32, i32>`
fn sufficient() {
let x: Foo = Ok(22_u32); // Requires `Result<u32, _>`
let y: Foo = Err(22_i32); // Requires `Result<_, i32>`
}This does not work across functions. Every function must declare a full hidden type. The following example will thus not work:
type Foo = impl Debug;
fn foo() -> Foo { Ok(42) }
fn bar() -> Foo { Err(69) }Even within the defining scope, it is possible for a function to reference values of the type Foo without imposing any constraints on them:
type Foo = impl Debug;
fn take_foo(f: Foo) {
// Requires that `Foo: Debug`, but that is given
// from the declared constraints.
println!("{f:?}");
}When an opaque type is defined at the module level, it is possible for there to be multiple functions which each constrain the same opaque type:
type Foo = impl Debug;
fn example() { let x: Foo = 22_u32; } // Adds constraint: `Foo = u32`
fn make_foo() -> Foo { 22_u32 } // Adds constraint: `Foo = u32`
fn take_foo(f: Foo) { println!("{f:?}"); } // No constraint.This is allowed, so long as all of the following are true:
- all functions impose the same constraint
- each function imposes a complete constraint without type variables
- there is at least one constraint
Examples that do not meet those rules:
type Foo = impl Debug;
fn make_u32() -> Foo { 22_u32 }
fn make_i32() -> Foo { 22_i32 }When the compiler tries to decide if an opaque type Foo implements a trait, it does so based on the declared bounds (the one exception is auto traits; see below). The hidden type is never used. This means that we sometimes get errors where the hidden type would have worked:
type Foo = impl Debug;
fn is_display<T: Display>() { }
fn example() {
let f: Foo = u32;
is_display::<Foo>(); // Error: Foo is not known to be display
}This can be surprising when using APIs like Default or collect:
fn foo() {
let x: Foo = 42_i32;
let y: Foo = Default::default(); // Error Foo: Default not satisfied
}You can fix code like the above by specifying the type manually:
fn foo() {
let y: Foo = <i32>::default(); // OK
let z: i32 = Default::default();
let z: Foo = z; // Also OK
}
When some code f inside the defining scope attempts to determine whether an opaque type like Foo implements an auto-trait, this is considered to be adding a "constraint" on the hidden type. In other words, to show that Foo: Send, f must constrain Foo to be some hidden type H which implements Send.
Example:
type Foo = impl Debug;
fn is_send<T: Send>() { }
fn not_good() {
// Error: this function does not constrain `Foo` to any particular
// hidden type, so it cannot rely on `Send` being true.
is_send::<Foo>();
}
fn ok() {
// Constrain `Foo = u32`
let x: Foo = 22_u32;
// No problem `Foo = u32` and `u32: Send`
is_send::<Foo>();
}When code outside the defining scope attempts to determine whether some opaque type Foo implements an auto-trait, the code can "reveal" the hidden type, as shown here:
mod defining_scope {
pub type Foo = impl Debug;
pub fn ok() -> Foo { 22_u32 }
}
fn is_send<T: Send>() { }
fn example() {
// OK: Reveals the hidden type for the purposes of checking `Send`
is_send::<defining_scope::Foo>();
}Revealing the hidden type forces all code in the defining scope to be type-checked; it is a fatal compilation error if this results in a cycle:
// Results in a cycle error.
fn is_send<T: Send>() { }
mod defining_scope1 {
pub type Foo = impl Debug;
pub fn ok() -> Foo {
is_send::<crate::defining_scope2::Bar>();
22_u32
}
}
mod defining_scope2 {
pub type Bar = impl Debug;
pub fn ok() -> Foo {
is_send::<crate::defining_scope1::Foo>();
22_u32
}
}- Because each function must impose a complete constraint, and because auto-trait leakage within the defining scope, all functions within the defining scope are checkable independently.
- This is good for the compiler, but it also means that users can remove a function and their code continues to compile, as long as it was not the only constraint.
Consider this example:
fn bar(b: bool) -> impl std::fmt::Debug {
if b {
return 42
}
let x: u32 = bar(false); // this errors on stable
99
}On stable today, this function fails to compile:
error[E0308]: mismatched types
--> src/lib.rs:5:18
|
1 | fn bar(b: bool) -> impl std::fmt::Debug {
| -------------------- the found opaque type
...
5 | let x: u32 = bar(false); // this errors on stable
| --- ^^^^^^^^^^ expected `u32`, found opaque type
| |
| expected due to this
|
= note: expected type `u32`
found opaque type `impl Debug`
On the new branch, that code would be accepted. The recursive call to bar returns the opaque type, which is then constrained to be equal to u32. This constraint is accepted because it occurs within the defining scope (bar).
In principle, these two definitions of foo should be equivalent, apart from defining the type Foo:
mod tait {
pub type Foo: Debug;
pub fn foo() -> Foo { .. }
}
mod rpit {
pub fn foo() -> impl Debug { .. }
}However, crater testing revealed some cases where stable code (i.e., code using RPIT) was behaving in ways that the TAIT algorithm did not accept. Therefore, we added some "special cases" for RPIT notation. We need to decide (in follow-up PRs) how to align the behavior of TAIT and RPIT in these cases. The current choices were made to allow for maximum future flexibility.
return statements and the trailing return expression are special with RPIT (but not TAIT). So while this TAIT program fails to compile
#![feature(type_alias_impl_trait)]
type Foo = impl std::fmt::Debug;
fn foo(b: bool) -> Foo {
if b {
return vec![42];
}
std::iter::empty().collect() //~ ERROR `Foo` cannot be built from an iterator
}The equivalent RPIT code works just fine:
fn bar(b: bool) -> impl std::fmt::Debug {
if b {
return vec![42]
}
std::iter::empty().collect() // Works, magic
}The RFCs do not mention such cases and there are no tests in the Rust test suite excercising this behavior.
Note that in the new insta stable case mentioned earlier, when we are working with the return value of a recursive call, both RPIT and TAIT get errors (on this branch and later):
type Foo = impl std::fmt::Debug;
fn foo(b: bool) -> Foo {
if b {
return vec![];
}
let mut x = foo(false);
x = std::iter::empty().collect(); //~ ERROR `Foo` cannot be built from an iterator
vec![]
}
fn bar(b: bool) -> impl std::fmt::Debug {
if b {
return vec![];
}
let mut x = bar(false);
x = std::iter::empty().collect(); //~ ERROR `impl Debug` cannot be built from an iterator
vec![]
}Similar from the user perspective but very different on the compiler side, TAITs do not allow type inference across branches of an if or match:
type Foo = impl std::fmt::Debug;
fn foo(b: bool) -> Foo {
if b {
vec![42_i32]
} else {
std::iter::empty().collect()
//~^ ERROR `Foo` cannot be built from an iterator over elements of type `_`
}
}The equivalent RPIT example works just fine.
It is easy to support, but we should make an explicit decision to include the additional complexity in the implementation (it's not much, see a721052457cf513487fb4266e3ade65c29b272d2 which needs to be reverted to enable this).
For closures the opposite is true:
fn bar(b: bool) -> impl std::ops::FnOnce(String) -> usize {
if b {
|x| x.len() //~ ERROR type annotations needed
} else {
panic!()
}
}does not work on stable, even though
fn bar1(b: bool) -> impl std::ops::FnOnce(String) -> usize {
|x| x.len()
}does work.
The equivalent code with TAIT works just fine with lazy TAIT, because the opaque type stays opaque right until it is compared against the closure, thus giving the maximum amount of information to the closure.
type Foo = impl std::ops::FnOnce(String) -> usize;
fn foo(b: bool) -> Foo {
if b {
|x| x.len()
} else {
panic!()
}
}
type Foo1 = impl std::ops::FnOnce(String) -> usize;
fn foo1(b: bool) -> Foo1 {
|x| x.len()
}