Return-position impl Trait is not satisfied by divergent/never type

[wchargin]

I tried this code:

pub fn foo() -> impl Iterator<Item = u32> {
    loop {}
    // or panic!(), etc.
}

// Equivalent code modulo cut elimination
pub fn bar() -> impl Iterator<Item = u32> {
    bar_helper()
}
fn bar_helper() -> std::iter::Empty<u32> {
    loop {}
}

I expected to see this happen:

Module should compile without error. If foo or bar are invoked, they
should diverge. In particular, foo and bar should be equivalent in
terms of both static and dynamic semantics.

In general, fn foo() -> T { loop {} } should compile for any type T,
because loop {} should be at type ! and ! should be a subtype of
every type. This seems to be the case for all proper types that I've
tried, including uninhabited ones like std::convert::Infallible, but
not when T is actually a return-position impl Trait.

Instead, this happened:

error[E0277]: `()` is not an iterator
 --> src/lib.rs:1:17
  |
1 | pub fn foo() -> impl Iterator<Item = u32> {
  |                 ^^^^^^^^^^^^^^^^^^^^^^^^^ `()` is not an iterator
  |
  = help: the trait `Iterator` is not implemented for `()`

This is surprising, because I'm not sure where the unit type is coming
from. If I replace impl Iterator<Item = u32> with impl Default, or
another trait that () does implement, then it compiles without error.
But if I use impl Trait for a trait that () does not implement, then
it raises this compile-time error.

The fact that bar compiles makes it feel especially weird that foo
does not compile, because they should be equivalent. Yes, there's more
type information (I've used std::iter::Empty<u32> as a specific type
implementing Iterator<Item = u32>), but I don't see why that should
matter. The error given by rustc wasn't a "ambiguous type; specify type
annotations" kind of error.

Playground with these examples and a few more:
https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=e8061b7ffb50afef8b230892d458d26b

Meta

rustc --version --verbose:

rustc 1.70.0 (90c541806 2023-05-31)
binary: rustc
commit-hash: 90c541806f23a127002de5b4038be731ba1458ca
commit-date: 2023-05-31
host: x86_64-unknown-linux-gnu
release: 1.70.0
LLVM version: 16.0.2

Also exists in nightly 2023-07-18.

[fmease]

This is surprising, because I'm not sure where the unit type is coming
from.

The fallback for unsolved type variables is () not ! for historical reasons. With #![feature(never_type_fallback)] (which can't be stabilized as-is) you can observe that the error message changes to `!` is not an iterator.

[fmease]

! should be a subtype of
every type

According to the RFC ! is not supposed to be the bottom type / the subtype of every type, it's merely the case that ! can coerce to any type. For example, (!,) cannot be coerced to (T,) for any type T.

[wchargin]

According to the RFC ! is not supposed to be bottom type / the subtype of every type, it's merely the case that ! can coerce to any type. For example, (!,) cannot be coerced to (T,) for any type T.

This is interesting and surprising to me.

In any case, my user-level bug report can be summarized as, "I want to
sketch out a method that returns an impl Iterator<Item = T> and just
return unimplemented!() for now without compile errors, because that's
what unimplemented!() is for and how it works for other (proper)
return types". In the context of this story, the precise type theory is
less important to me, even though it's also interesting in its own
right. :-)

[fmease]

Regarding your main point, personally I'm not qualified enough to answer or to speak for anybody on the Rust team, so take the following with a grain of salt.

To explain a bit what's happening, for a type H to be a valid hidden type for an opaque type impl Bound0 + Bound1 + …, H has to satisfy all the bounds (H: Bound0 + Bound1 + …). And since the never type is a proper type (under #![feature(never_type)]) that means that ! has to implement all possible traits in existence (pseudo: impl<...T, trait Trait<..._>> Trait<...T> for ! { /* magic */ }). This sure isn't something the user could ever write but of course the compiler could just postulate such implementations whenever possible. Spoiler: It's not always possible in Rust's trait system (*).

It's unclear to me if the above could break the language in any major way. It sure feels fishy.

(*) If we assume that such a synthesized implementation still needs to follow normal rules and if in such impl associated types are set to !, associated constants and the bodies of associated functions to loop {}, then we can't impl the following trait for ! in a straightforward and mechanical manner:

trait Main { type P: Auxiliary<Q = u64>; }
trait Auxiliary { type Q; }

In a hypothetical different language that allows ⊥ (bottom) to inhabit a trait implementation, things would be easier but such a language would be quite different (esp. in regards to runtime behavior).

In any case, somebody with more background knowledge probably has a more well-grounded answer than me.

[Jules-Bertholet]

Here's an example of why this can't be supported in general:

trait Foo {
    const ASSOC: i32;
}

fn print_assoc<T: Foo>(_: fn() -> T) {
    println!("{}", <T as Foo>::ASSOC);
}

fn get_foo() -> impl Foo {
    loop {}
}

fn main() {
    // What number should this print?
    print_assoc(get_foo);
}

[fmease]

Well, as I've described above T::ASSOC could be loop {} if we automatically generated impl Foo for ! that way. Definitely wouldn't be pretty and doesn't generalize easily (cf. the snippet I posted above).

Edit: Of course, that would be horrible for type trait safety, this was just me rambling about one possible design. Making ! impl every single trait, basically means introducing null into the trait system. Every single trait bound gets an extra inhabitant even if not asked for. Shouldn't break stuff but it's kinda ugly. Downstream users would be able to just pass ! everywhere and when they do, they might just get looping consts and fns, yuck.

[compiler-errors]

@fmease is correct, and I don't think this should be classified as a bug. Unfortunately, ! isn't the default fallback type, but even if we did fall back to !, I think it would be a mistake (and also plain impossible) to make ! implement all traits in Rust.

[wchargin]

@Jules-Bertholet: Thanks for the clear and concise example. I see that
RFC 1216 lists an "Unresolved question" of

! has a unique impl of any trait whose only items are non-static
methods. It would be nice if there was a way to automate the creation
of these impls. Should ! automatically satisfy any such trait?

which seems clearly related. I also note that, even if we did that,
Iterator is not actually such a trait, because of its type Item. Yet
even with this hurdle, it still seems that loop {} should satisfy
impl Iterator<Item = u32>, because the constraint Item = u32 removes
the ambiguity. That is, while ! doesn't have a unique impl for
Iterator, it does have a unique impl for "Iterator<Item = u32>".

I guess there is more lurking behind this unimplemented!() than I had
expected. :-) I still think that it "should" work to panic or loop in
such a method (i.e., it has a unique, sensible semantics and also it
would be useful), but I can see better now why it's tricky.

[fmease]

That is, while ! doesn't have a unique impl for
Iterator, it does have a unique impl for "Iterator<Item = u32>".

If we assume ! had an impl for Iterator<Item = u32> (to allow fn f() -> impl Iterator<Item = u32> { todo!() }), then it cannot have another impl for Iterator<Item = &'static str> (to allow fn g() -> impl Iterator<Item = &'static str> { todo!() }) which would defeat the whole purpose. Iterator is a trait ! could implement, Iterator<Item = U> – more precisely T: Iterator<Item = U> – is not a trait, it's syntactic sugar for two bounds: T: Iterator and <T as Iterator>::Item == U.

I still think that it "should" work to panic or loop in
such a method

I think I understand where you are coming from. In a dynamically typed or in an “untyped” (unityped) language, it's possible to just diverge inside the function body showing complete disregard for the (dynamic) return type.

In a statically typed language on the other hand, every single (unevaluated) expression and value has to be of a certain type. This means we have to be able to assign a type to unimplemented!(), there's no choice.

Even if we start out with unimplemented!() : ?0 (where ?0 is an inference variable), the inference variable has to be solved for the type-checker to even begin to consider your program well-typed. Once it comes to the conclusion that ?0 is () or ! (depending on the presence of #![feature(never_type_fallback)]), the type checker has to check (or has to have checked) that (): Iterator / !: Iterator holds (which is currently not the case rendering your program ill-typed in the end).

This explains why I was mostly talking about ! above.

@rustbot label -needs-triage