Const generics cannot be used to implement type-level if-then-else

[HadrienG2]

So, as part of a mad science experiment, I am trying to define the following trait in Rust:

// This is Rust-ish pseudocode, not valid Rust
trait ConstLenIterator<const LEN: usize> {
    type Item;
    fn next(self) -> if LEN > 0 {
        (Self::Item, impl ConstLenIterator<{LEN-1}, Item=Self::Item>)
    } else
        ()
    };
}

Now, Rust would clearly need new language features such as type-level if and impl Trait in trait fns for this pseudocode to actually work as-is. But as discussed in this internals thread, it seems that const generics could enable a decent library-based approximation of the desired behavior:

#![feature(const_generics)]
#![feature(const_saturating_int_methods)]

// Machinery for type level if-then-else
struct Bool<const B: bool>;
trait Select<T, F> { type Out; }
impl<T, F> Select<T, F> for Bool<{true }> { type Out = T; }
impl<T, F> Select<T, F> for Bool<{false}> { type Out = F; }

// if B then T, else F.
type If<T, F, const B: bool> = <Bool<{B}> as Select<T, F>>::Out;

trait ConstLenIterator<const LEN: usize> {
    type Item;
    type Next: ConstLenIterator<{LEN.saturating_sub(1)}, Item = Self::Item>;
    fn next(self) -> If<(Self::Item, Self::Next), (), {LEN > 0}>;
}

Unfortunately, this does not compile:

error[E0277]: the trait bound `Bool<{LEN > 0}>: Select<(<Self as ConstLenIterator<LEN>>::Item, <Self as ConstLenIterator<LEN>>::Next), ()>` is not satisfied
  --> src/lib.rs:16:5
   |
16 |     fn next(self) -> If<(Self::Item, Self::Next), (), {LEN > 0}>;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `Select<(<Self as ConstLenIterator<LEN>>::Item, <Self as ConstLenIterator<LEN>>::Next), ()>` is not implemented for `Bool<{LEN > 0}>`
   |
   = help: the following implementations were found:
             <Bool<false> as Select<T, F>>
             <Bool<true> as Select<T, F>>

I have managed to reduce it to the following, admittedly silly, test case...

#![feature(const_generics)]

struct Bool<const B: bool>;
trait Identity { const B: bool; }
impl Identity for Bool<{true }> { const B: bool = true; }
impl Identity for Bool<{false}> { const B: bool = false; }

fn should_work<const B: bool>() -> bool {
    <Bool<{B}> as Identity>::B
}

...which fails with...

error[E0277]: the trait bound `Bool<B>: Identity` is not satisfied
 --> src/lib.rs:9:5
  |
9 |     <Bool<{B}> as Identity>::B
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `Identity` is not implemented for `Bool<B>`
  |
  = help: the following implementations were found:
            <Bool<false> as Identity>
            <Bool<true> as Identity>
note: required by `Identity::B`
 --> src/lib.rs:4:18
  |
4 | trait Identity { const B: bool; }
  |                  ^^^^^^^^^^^^^^

It seems to me that this could be resolved by introducing some kind of impl exhaustiveness checking so that the compiler can prove that the Identity trait is implemented for all variants of Bool.

[HadrienG2]

Note that impl exhaustiveness checking could also enable the following:

struct Bool<const B: bool>;
impl Bool<{true }> { const B: bool = true; }
impl Bool<{false}> { const B: bool = false; }

fn should_work<const B: bool>() -> bool {
    Bool::<{B}>::B
}

But whether it should is obviously a different question.

[varkor]

This is really a feature request, and deserves its own RFC. However, implementation doesn't seem implausible, as we already have exhaustiveness checking in other locations, so we could reuse that mechanism.

[HadrienG2]

@varkor Agreed, figured out as much while trying to reduce the case further and discovering that contrary to what I thought, this cannot be merely implemented as evaluating Bool<B> to either Bool<true> or Bool<false> once B is known, because in Rust the compiler must prove that use of Bool<B> is correct for all values of B.

[HadrienG2]

Let's discuss this further, then.

[Dylan-DPC-zz]

The error message now is:

error[E0391]: cycle detected when const-evaluating + checking `ConstLenIterator::Next::{{constant}}#0`
  --> src/lib.rs:15:33
   |
15 |     type Next: ConstLenIterator<{LEN.saturating_sub(1)}, Item = Self::Item>;
   |                                 ^^^^^^^^^^^^^^^^^^^^^^^
   |
note: ...which requires const-evaluating + checking `ConstLenIterator::Next::{{constant}}#0`...
  --> src/lib.rs:15:33
   |
15 |     type Next: ConstLenIterator<{LEN.saturating_sub(1)}, Item = Self::Item>;
   |                                 ^^^^^^^^^^^^^^^^^^^^^^^
note: ...which requires const-evaluating `ConstLenIterator::Next::{{constant}}#0`...
  --> src/lib.rs:15:33
   |
15 |     type Next: ConstLenIterator<{LEN.saturating_sub(1)}, Item = Self::Item>;
   |                                 ^^^^^^^^^^^^^^^^^^^^^^^
note: ...which requires type-checking `ConstLenIterator::Next::{{constant}}#0`...
  --> src/lib.rs:15:33
   |
15 |     type Next: ConstLenIterator<{LEN.saturating_sub(1)}, Item = Self::Item>;
   |                                 ^^^^^^^^^^^^^^^^^^^^^^^
note: ...which requires processing `ConstLenIterator::Next::{{constant}}#0`...
  --> src/lib.rs:15:33
   |
15 |     type Next: ConstLenIterator<{LEN.saturating_sub(1)}, Item = Self::Item>;
   |                                 ^^^^^^^^^^^^^^^^^^^^^^^
   = note: ...which again requires const-evaluating + checking `ConstLenIterator::Next::{{constant}}#0`, completing the cycle
note: cycle used when processing `ConstLenIterator`
  --> src/lib.rs:13:1
   |
13 | trait ConstLenIterator<const LEN: usize> {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error: aborting due to previous error

[dalcde]

In the same vein, the following does not work but "should":

trait Tr<const B: bool> {}
struct Ty;

impl Tr<true> for Ty {}
impl Tr<false> for Ty {}

struct Test<const B: bool, T: Tr<B>>(T);
struct Test2<const B: bool>(Test<B, Ty>);

Rust is unable to infer that Ty: Tr<B> for all B.

[lcnr]

this is mostly tracked by https://github.com/rust-lang/project-const-generics/issues/26 and can also achieved by using specialization (by adding an impl which covers the whole type).

Adding if to the type level is something I've also previously thought before, but probably isn't something we should add for Rust rn and would definitely require a lang mcp or rfc.

closing this issue