# Never types and inference

**URL:** <https://internals.rust-lang.org/t/never-types-and-inference/8924>\
**Category:** language design\
**Created:** [November 29, 2018, 1:50pm UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924 "2018-11-29T13:50:16Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![derekdreery](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/derekdreery/32/2632_2.png) [@derekdreery](https://internals.rust-lang.org/u/derekdreery)\
**Post date:** [November 29, 2018, 1:50pm UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/1 "2018-11-29T13:50:16Z")

</div>

Take the function

```rust
fn run() -> Result<(), impl Error> {
    Ok(())
}

```

where the error type is unbounded. The compiler currently rejects this. When we have the never type I think this should pass - as long as there is `impl Error for !`, we can monomorphise this to `fn run() -> Result<(), !>`. Will this work like this?

Sorry for the poorly worded question.

---

<div class="post-metadata">

**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\
**Post date:** [November 30, 2018, 12:18am UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/2 "2018-11-30T00:18:49Z")

</div>

I think `never_type` used to do something like this, inferring never-set inference variables to `!`, but that change got dropped because it was a breaking change in some cases where it used to give `()` instead. I can’t find the issue about that right now, though…

---

<div class="post-metadata">

**Author:** ![canndrew](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/canndrew/32/1676_2.png) [@canndrew](https://internals.rust-lang.org/u/canndrew)\
**Post date:** [November 30, 2018, 10:24am UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/3 "2018-11-30T10:24:23Z")

</div>

There are some cases where the compiler would reject it and other cases where it would (wrongly) infer `()`. The plan was to change the latter cases to make it infer `!` instead, possibly only in the 2018 edition since it’s a breaking change, though that change got put on the back-burner at some point.

I think it would be nice if the compiler could infer a type in more of these situations. In OP’s example it should infer `!` since we have `!: Error`, though where there are other trait bounds a good mechanism might be to have “default” types for traits, eg. have a new kind of declaration which looks like this:

```rust
default<T> IntoIterator<Item = T> + Extend<T> + Default = Vec<T>;

```

This says that whenever there’s an inferred type which needs to satisfy the bound `IntoIterator<Item = T> + Extend<T> + Default` then the compiler should infer the type `Vec<T>`.

**Edit:** Elaborating on that idea a bit:

There would be a base declaration of `default ?Sized = !;` built into the language. Crates can then add their own `default SomeTrait = SomeType;` declarations where coherence rules apply to `SomeTrait` (eg. `SomeTrait` must be defined in the same crate, or at least part of it must be in the case of `SomeTrait + SomeOtherTrait`). Default type declarations can override other default type declarations by being more specific, similar to how impl specialization works, and the compiler will always pick the most specific declaration which satisfies the required bounds. For example, we could have the declarations:

```rust
default TraitA = A;
default TraitA + TraitB = B;

```

Then if the compiler needs to pick a type which satisfies `TraitA + TraitB + TraitC`, it will first check if `B: TraitA + TraitB + TraitC`, then if `A: TraitA + TraitB + TraitC`, then if `!: TraitA + TraitB + TraitC` before failing if none of them fit. The compiler should always mark these inferred types as being inferred in case they ever appear in error messages, and should be able to point the user to the rule that was used to infer the type.

**Edit 2:** In case anyone needs a motivating example for this: `!` can’t implement `Future` without picking some specific `Output` type. This means it can’t be used as the inferred type where we have a trait bound of `Future<Output = SomeOtherConcreteType>`. We could, however, have this instead:

```rust
enum NeverOutput<T> {}

impl<T> Future for NeverOutput<T> {
    type Output = T;

    ...
}

default<T> Future<Output = T> = NeverOutput<T>;

```

Then we would be allowed to write:

```rust
fn foo() -> impl Future<Output = String> {
    unimplemented!()
}

```

---

<div class="post-metadata">

**Author:** ![derekdreery](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/derekdreery/32/2632_2.png) [@derekdreery](https://internals.rust-lang.org/u/derekdreery)\
**Post date:** [November 30, 2018, 12:49pm UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/4 "2018-11-30T12:49:02Z")

</div>

It would be nice to solve the unimplemented problem one way or another.

---

<div class="post-metadata">

**Author:** ![derekdreery](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/derekdreery/32/2632_2.png) [@derekdreery](https://internals.rust-lang.org/u/derekdreery)\
**Post date:** [December 7, 2018, 6:36pm UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/5 "2018-12-07T18:36:25Z")

</div>

I ran into another similar issue today while doing [aoc](https://adventofcode.com/2018/):

```rust
fn iter(&self) -> impl Iterator<Item=Point2d> {
    unimplemented!()
}

```

gives

```nohighlight
error[E0277]: `()` is not an iterator

```

the type should be `!`, not `()`, I think.

---

<div class="post-metadata">

**Author:** ![H2CO3](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/h2co3/32/2849_2.png) [@H2CO3](https://internals.rust-lang.org/u/H2CO3)\
**Post date:** [December 7, 2018, 7:31pm UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/6 "2018-12-07T19:31:18Z")

</div>

I don’t fully understand why solving this needs to generate random throw-away types. Why can’t it just be that `!` simply satisfies any and all traits?

---

<div class="post-metadata">

**Author:** ![CAD97](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cad97/32/3460_2.png) [@CAD97](https://internals.rust-lang.org/u/CAD97)\
**Post date:** [December 7, 2018, 8:32pm UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/7 "2018-12-07T20:32:01Z")

</div>

`!` cannot satisfy all traits, otherwise you could do `<! as Default>::default()`. The same basically goes for any other trait fn that doesn’t take `self`, and is in fact more important for those that also don’t return `Self`, as they may even have a valid nonpanicking implementation.

---

<div class="post-metadata">

**Author:** ![H2CO3](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/h2co3/32/2849_2.png) [@H2CO3](https://internals.rust-lang.org/u/H2CO3)\
**Post date:** [December 7, 2018, 8:54pm UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/8 "2018-12-07T20:54:21Z")

</div>

Oh, that’s right, I didn’t think it through fully…

Still, I think we should think of a better solution, just trying to assume something potentially surprising seems flaky in any case.

---

<div class="post-metadata">

**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\
**Post date:** [December 8, 2018, 12:02am UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/9 "2018-12-08T00:02:20Z")

</div>

> [@derekdreery](#):
>
> the type should be `!` , not `()` , I think.

It is if you do

```rust
#![feature(never_type)]
fn iter() -> impl Iterator<Item=i32> {
    unimplemented!()
}

```

There's been a bunch of discussion about this; see [Tracking issue for promoting `!` to a type (RFC 1216) · Issue #35121 · rust-lang/rust · GitHub](https://github.com/rust-lang/rust/issues/35121) and sub-issues.

---

<div class="post-metadata">

**Author:** ![kennytm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/kennytm/32/161_2.png) [@kennytm](https://internals.rust-lang.org/u/kennytm)\
**Post date:** [December 8, 2018, 6:12am UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/10 "2018-12-08T06:12:51Z")

</div>

`!: Default` isn’t the big issue if we disregard the internals of `default()`. A more fundamental problem is that you can’t simultaneously support

```rust
!: Iterator<Item = u8>,
!: Iterator<Item = u16>,

```

Allowing this breaks the assumption in the _type system_ which the associated type is a one-to-one relationship, as mentioned in [Never types and inference](https://internals.rust-lang.org/t/never-types-and-inference/8924/3) and also [Draft RFC: default types for traits](https://internals.rust-lang.org/t/draft-rfc-default-types-for-traits/8948/8).

(Note: I don’t think `default trait = type` is the correct answer to this problem)

---

<div class="post-metadata">

**Author:** ![canndrew](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/canndrew/32/1676_2.png) [@canndrew](https://internals.rust-lang.org/u/canndrew)\
**Post date:** [December 8, 2018, 1:42pm UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/11 "2018-12-08T13:42:30Z")

</div>

> [@kennytm](#):
>
> `!: Default` isn’t the big issue if we disregard the internals of `default()` . A more fundamental problem is that you can’t simultaneously support
> 
> ```rust
> !: Iterator<Item = u8>,
> !: Iterator<Item = u16>,
> 
> ```
> 
> Allowing this breaks the assumption in the _type system_ which the associated type is a one-to-one relationship, as mentioned in [Never types and inference](https://internals.rust-lang.org/t/never-types-and-inference/8924/3) and also [Draft RFC: default types for traits](https://internals.rust-lang.org/t/draft-rfc-default-types-for-traits/8948/8).
> 
> (Note: I don’t think `default trait = type` is the correct answer to this problem)

Well the other idea mentioned in that thread is to allow trait impls to be generic in their associate types. eg. allow impls like this:

```rust
// T not used on Future or !, just on the associated type.
impl<T> Future for ! {
    type Output = T;
    ...
}

```

Which would make `<! as Future>::Output` a type variable which can unify with anything. I don't know if this is sound though.

---

<div class="post-metadata">

**Author:** ![kennytm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/kennytm/32/161_2.png) [@kennytm](https://internals.rust-lang.org/u/kennytm)\
**Post date:** [December 8, 2018, 9:03pm UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/12 "2018-12-08T21:03:09Z")

</div>

> [@canndrew](#):
>
> Which would make `<! as Future>::Output` a type variable which can unify with anything. I don’t know if this is sound though.

I don't think it is sound. If this is allowed, then we can't make any assumption about `<U as Future>::Output` as `U == !` is also possible.

```rust
fn g<U: Future>() {
    let a: U::Output;
    let b: U::Output;
    // a and b can be of different type?
}
g::<!>();

```

---

<div class="post-metadata">

**Author:** ![Centril](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/centril/32/3334_2.png) [@Centril](https://internals.rust-lang.org/u/Centril)\
**Post date:** [December 8, 2018, 9:27pm UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/13 "2018-12-08T21:27:45Z")

</div>

> [@canndrew](#):
>
> Which would make `<! as Future>::Output` a type variable which can unify with anything. I don’t know if this is sound though.

It's unsound.

Remember that associated types are type-level functions, wherefore the type-system may assume `X ~ Y => <X as F>::Out ~ <Y as F>::Out`.

Adding your idea to the type system lets us then derive:

```rust
fn transmute<T, U>(x: T) -> U {
    struct Input;
    trait Function { type Output; }
    // Your added rule:
    impl<S> Input { type Output = S; }

    // Legal because `Output ~ ?S1` so specifically `T ~ Output`:
    let tmp: <Input as Function>::Output = x;
    // Legal because `Output ~ ?S2` so specifically `Output ~ U`:
    let tmp: U = tmp;
    // And we have bricked the type-system:
    tmp
}

```

---

<div class="post-metadata">

**Author:** ![canndrew](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/canndrew/32/1676_2.png) [@canndrew](https://internals.rust-lang.org/u/canndrew)\
**Post date:** [December 9, 2018, 3:55am UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/14 "2018-12-09T03:55:39Z")

</div>

@Centril: I disagree that that should type-check.

```rust
let tmp: <Input as Function>::Output = x;

```

On this line, `<Input as Function>::Output` will initially be a type variable and will then unify with the type of `x` to give `tmp: T`. However on the next line `tmp` gets used and will cause that same type variable to try and unify with `U`. So it should fail with `U != T`.

---

<div class="post-metadata">

**Author:** ![canndrew](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/canndrew/32/1676_2.png) [@canndrew](https://internals.rust-lang.org/u/canndrew)\
**Post date:** [December 9, 2018, 3:59am UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/15 "2018-12-09T03:59:19Z")

</div>

@kennytm

```rust
fn g<U: Future>() {
   let a: U::Output;
   let b: U::Output;
   // a and b can be of different type?
}
g::<!>();

```

I think the `U: Future` in the function’s type parameters implies that a specific `U: Future` impl has been passed to the function. In other words, no, there will be one type variable and `a` and `b` will both have that type.

---

<div class="post-metadata">

**Author:** ![canndrew](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/canndrew/32/1676_2.png) [@canndrew](https://internals.rust-lang.org/u/canndrew)\
**Post date:** [December 9, 2018, 4:00am UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/16 "2018-12-09T04:00:41Z")

</div>

@nikomatsakis: You probably know the most about traits and soundness, given your work on chalk. What’s your opinion on the last 6 posts in this thread?

---

<div class="post-metadata">

**Author:** ![arthrowpod](https://avatars.discourse-cdn.com/v4/letter/a/df788c/32.png) [@arthrowpod](https://internals.rust-lang.org/u/arthrowpod)\
**Post date:** [December 14, 2018, 1:57am UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/17 "2018-12-14T01:57:37Z")

</div>

Not niko, but I don’t see any way this could be sound. The whole reason associated types exist in the first place is to serve as type-level functions that guarantee uniqueness. Otherwise they’re exactly the same as type parameters. Allowing multiple impls of the same trait where the associated types are different would violate some very fundamental assumptions about the type system.

---

<div class="post-metadata">

**Author:** ![felix.s](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/felix.s/32/8073_2.png) [@felix.s](https://internals.rust-lang.org/u/felix.s)\
**Post date:** [December 14, 2018, 8:47am UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/18 "2018-12-14T08:47:19Z")

</div>

I don’t see how this should be any more unsound than allowing multiple impls per a (type, trait) pair, and subjecting the choice of impl to inference. The general case may be problematic because type inference may be insufficient to disambiguate between two different impls, but for the natural, vacuous impls for `!` the compiler can exploit the fact that they are all functionally identical, so the choice doesn’t matter.

But even though I don’t think this would be necessarily unsound, I’m not sure this feature would fit Rust very well; it’s quite incongruous with the rest of the type system, where a (type, trait) pair is supposed to determine the impl unambiguously, if one exists. If we add [impl relevance](https://ncatlab.org/nlab/show/proof+relevance) for traits, I’d rather have it available for all types, not just the empty type.

---

<div class="post-metadata">

**Author:** ![ExpHP](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/exphp/32/6208_2.png) [@ExpHP](https://internals.rust-lang.org/u/ExpHP)\
**Post date:** [December 14, 2018, 1:53pm UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/19 "2018-12-14T13:53:13Z")

</div>

I am very not keen on using reasoning like “the impls are vacuous.” You’re talking as if having a `!` appear as a type argument is a logical contradiction… but `!` is merely an empty set of _values,_ not an empty set of _types._

---

<div class="post-metadata">

**Author:** ![felix.s](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/felix.s/32/8073_2.png) [@felix.s](https://internals.rust-lang.org/u/felix.s)\
**Post date:** [December 14, 2018, 10:14pm UTC](https://internals.rust-lang.org/t/never-types-and-inference/8924/20 "2018-12-14T22:14:28Z")

</div>

No, having `!` as a type argument is not a contradiction. But having a `!`-typed value as a function argument _is_ a contradiction.

`!` has an empty set of possible values. Therefore, it is possible to write an implementation for any function taking a `!`-typed argument, and any two such implementations will vacuously have the same computational content. Implementing a trait for a type is mostly a matter of implementing the trait’s methods; thus, any trait for which all methods take a `Self`-typed\* argument can be implemented for `!`, and any two such implementations will behave identically (that is to say, not behave at all, because their methods cannot be invoked in the first place). This property doesn’t hold for all traits (`Default` is the usual counterexample), but for many of them it does.

\* or `&Self`-typed, `&mut Self`-typed, etc.

[Next page](https://internals.rust-lang.org/t/never-types-and-inference/8924.md?page=2)