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

[fmease]

Should we nominate this issue for a T-lang or T-types discussion to settle this?

[axos88]

Joining the discussion, as I have raised a duplicate.

My use case was almost exactly the same - write up an fn, and mark it unimplemented / Todo. This was actually a trait implementation that I have not yet finished.

The error message was a big wtf for me as well, with the same where's () coming from, but the other confusing issue is that adding a dummy value after the panic invocation makes the compiler bark about unreachable code.

So what is the expected way to write an fn that returns an impl T, but is still unimplemented!() ?

[axos88]

Also the most confusing is that while impl Trait should just be more-or-less syntacting sugar for the latter, the explicit code compiles, while the implicit one does not:

trait Foo {}


fn compiles<T: Foo>() -> T {
    todo!()
}

fn breaks() -> impl Foo {
    todo!()
}

[Jules-Bertholet]

Also the most confusing is that while impl Trait should just be more-or-less syntacting sugar for the latter

trait Foo {}


fn compiles<T: Foo>() -> T {
    todo!()
}

fn breaks() -> impl Foo {
    todo!()
}

These are not equivalent. Argument-position impl Trait is sugar for a type parameter, return-position impl Trait is something different.

[Scripter17]

Perhaps a silly question, but is it possible to have the trait bound checker pretend ! satisfies any set of bounds? That way it can effectively implement Iterator<Item=u32> and Iterator<Item=u64> by taking advantage of it not needing an implementation at all

/// If `T` is `!`, always return `true`. Otherwise do normal trait bounds checking.
fn type_satisfies_bounds<T>(bounds: &TraitBounds) -> bool {
    type_is_never::<T>() || normal_type_satisfies_bounds::<T>(bounds)
}

This sidesteps both the question of which traits to implement and, I think, what those traits should have as associated constants/types and type parameters because it pretends to implement any bounds needed of it. Though it also implements self-contradictory bounds like Sync+!Sync which... Should be fine? You never have a ! so you never need to figure out how to handle Sync+!Sync

[fmease]

[Is] it possible to have the trait bound checker pretend ! satisfies any set of bounds? That way it can effectively implement Iterator<Item=u32> and Iterator<Item=u64> by taking advantage of it not needing an implementation at all[?]

A proposition like T: Trait (here a predicate) is not binary, it's not just true or false, it has to be connected to evidence or a witness if it holds in order to make the compiler correctly type-check the rest of a program and for the compiler to be actually able to generate machine code. A witness can be a user-written impl for example which then contains concrete method implementations used for codegen.

For the following code the compiler would need to be able to generate machine code:

trait Trait { fn transmute<'a>(_: &'a str) -> &'static str; }

fn accept<'a, T: Trait>(input: &'a str) -> &'static str { T::transmute(input) }

fn main() { accept::<!>(&String::new()); }

And as I've mentioned above, we could of course introduce a new kind of witness, let's call it Never, where all associated constants and functions would loop {} / diverge¹. The associated types would be set to ! which would only work in general if Never was a witness of all equality constraints, too (which would be necessary to make ! satisfy Iterator<Item=u32> + Iterator<Item=u64> which is what you've proposed), otherwise ! couldn't implement:

trait Trait { type A: Aux<X = u32> + Aux<Y = u64>; }
trait Aux { type X; type Y; } 

Okay, so I couldn't come up with a code snippet that would demonstrate unsoundness but making any sort of equality constraint satisfiable (via Never) looks super unsound to me. I feel like allowing !: Aux<Assoc = A> + Aux<Assoc = B> (same associated type, different projected type) would enable us to encode fn transmute<'a>(s: &'a str) -> &'static str in safe code, not sure if that's true.

Footnotes

1. Disregarding the fact that that'd be super ugly. ↩

[nalply]

would enable us to encode fn transmute<'a>(s: &'a str) -> &'static str in safe code

I don't know, but I imagine any code ! touches is never executed. So it does not matter. This is what I would argue.

For example in the comment @Jules-Bertholet asks (rhetorically):

What number should this print?

It does not print at all.

I know this has been discussed already, for example here by @fmease:

Downstream users would be able to just pass ! everywhere and when they do, they might just get looping consts and fns, yuck.

But if some unsoundness were introduced, does it matter? Any code near that unsoundness will never be executed. I know, ugly, but sound. Right?

[compiler-errors]

You don't need to execute unreachable code to dispatch on methods that would need to be implemented for !, and such methods need to have meaningful bodies since they aren't necessarily diverging themselves:

fn never() -> Option<impl Foo> {
    // This is never run, but it means that `impl Foo := !` above.
    if false {
        let never: Option<!> = Some(loop {});
        return never;
    }

    None
}

trait Foo {
    fn from_option(this: Option<Self>) where Self: Sized;
}

fn main() {
    Foo::from_option(never());
}

[BenWiederhake]

As a quick-and-dirty workaround (after all we're just trying to see whether the structure of the code compiles), I'm now using:

fn foo(&self) -> impl Iterator<Item=&u8> {
    (unimplemented!() as Vec<u8>).iter()
}

This circumvents the problem described by @Jules-Bertholet, by providing "evidence" (as @fmease put it).

Nevertheless, it would be nice to have some kind of support for this, because "just stubbing a function with unimplemented!()" feels like something that should be fundamentally easy.

How about this: Modify the compilation error to be more helpful, like so?

Old:

error[E0277]: `()` is not an iterator
 --> src/lib.rs:2:18
  |
2 | fn foo(&self) -> impl Iterator<Item=&u8> {
  |                  ^^^^^^^^^^^^^^^^^^^^^^^ `()` is not an iterator
  |
  = help: the trait `Iterator` is not implemented for `()`

For more information about this error, try `rustc --explain E0277`.
error: could not compile `playground` (lib) due to 1 previous error

Suggestion:

error[E0277]: `NeverType` is not an iterator
 --> src/lib.rs:2:18
  |
2 | fn foo(&self) -> impl Iterator<Item=&u8> {
  |                  ^^^^^^^^^^^^^^^^^^^^^^^ `NeverType` is not an iterator
  |
  = note: Even in the case of divergent code, a concrete trait implementation must be provided.
  |
3 | -    unimplemented!()
3 | +    unimplemented!() as std::slice::Iter<'static, u8>
help: consider coercing NeverType to an arbitrary implementation

For more information about this error, try `rustc --explain E9999`, or issue #113875.
error: could not compile `playground` (lib) due to 1 previous error