2

I'm writing a type level Fibonacci sequence. I've already written a type level addition, which works fine. Every number is represented as Inc<Inc<...<Zero>...>>. There is a trait Add, then the structure Bop<Left, Right> (binary operation) implements the Add trait. The usage is that <Bop<Inc<Inc<Inc<Zero>>>, Inc<Inc<Zero>>> as Add>::Get will be Inc<Inc<Inc<Inc<Inc<Zero>>>>>, that is 3 + 2 = 5.

Then I write a Fibonacci sequence based on the addition:

use std::marker::PhantomData;
struct Zero {}
struct Inc<T> {
    _phantom: PhantomData<T>,
}

struct Bop<Left, Right> {
    _phantom_l: PhantomData<Left>,
    _phantom_r: PhantomData<Right>,
}

trait Add {
    type Get;
}

impl<Left> Add for Bop<Left, Zero> {
    type Get = Left;
}

impl<Left, RightInner> Add for Bop<Left, Inc<RightInner>>
where
    Bop<Left, RightInner>: Add,
{
    type Get = Inc<<Bop<Left, RightInner> as Add>::Get>;
}

type One = Inc<Zero>;
type Two = Inc<One>;
type Three = Inc<Two>;
type Four = Inc<Three>;
type Five = Inc<Four>;
// then <Bop<Three, Two> as Add>::Get will be type Five

// 0 1 2 3 4 5 6 7
// 0 1 1 2 3 5 8 13
// usage: <Inc<Inc<Inc<Zero>>> as Fib>::Get should be the third fib number,
// i.e. 2, or Inc<Inc<Zero>>
trait Fib {
    type Get;
}
impl Fib for Zero {
    type Get = Zero;
}
impl Fib for One {
    type Get = One;
}

impl<T> Fib for Inc<Inc<T>>
where
    T: Fib,
    Inc<T>: Fib,
    Bop<<T as Fib>::Get, <Inc<T> as Fib>::Get>: Add,
{
    type Get = <Bop<<T as Fib>::Get, <Inc<T> as Fib>::Get> as Add>::Get;
}

fn main() {}

complete example

The compiler has trouble figuring out the impl<T> Fib for Uop<Inc<Inc<T>>> part, it complains:

error[E0275]: overflow evaluating the requirement `Inc<_>: Fib`
  |
  = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
  = note: required because of the requirements on the impl of `Fib` for `Inc<Inc<_>>`
  = note: required because of the requirements on the impl of `Fib` for `Inc<Inc<Inc<_>>>`
  = note: required because of the requirements on the impl of `Fib` for `Inc<Inc<Inc<Inc<_>>>>`
  = note: required because of the requirements on the impl of `Fib` for `Inc<Inc<Inc<Inc<Inc<_>>>>>`
  = note: required because of the requirements on the impl of `Fib` for `Inc<Inc<Inc<Inc<Inc<Inc<_>>>>>>`
  = note: required because of the requirements on the impl of `Fib` for `Inc<Inc<Inc<Inc<Inc<Inc<Inc<_>>>>>>>`
  = note: required because of the requirements on the impl of `Fib` for `Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<_>>>>>>>>`
  = note: required because of the requirements on the impl of `Fib` for `Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<_>>>>>>>>>`
  = note: required because of the requirements on the impl of `Fib` for `Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<_>>>>>>>>>>`
  = note: required because of the requirements on the impl of `Fib` for `Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<_>>>>>>>>>>>`
  = note: required because of the requirements on the impl of `Fib` for `Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<_>>>>>>>>>>>>`
  = note: required because of the requirements on the impl of `Fib` for `Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<_>>>>>>>>>>>>>`
  = note: required because of the requirements on the impl of `Fib` for `Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<Inc<_>>>>>>>>>>>>>>`

// cut off more

What's the reason of the error? How to resolve it?

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
user10739302
  • 53
  • 1
  • 5
  • To me, this looks like the type checker runs into an infinite loop somehow. Maybe you can narrow down your problem by (temporarily) eliminating `Uop`, setting all `type Get=Zero`, and selectively uncommenting type requirements. – phimuemue Dec 09 '18 at 12:41
  • Your code looks correct. I would not expect this to overflow. – Peter Hall Dec 09 '18 at 12:44
  • @phimuemue I think this is a compiler bug. Each type only ever depends on a simpler type, so there is no reason for it to explode. – Peter Hall Dec 09 '18 at 12:47
  • @PeterHall The code caused overflow is at `Bop<::Get, as Fib>::Get>: Add,` constraint. IDK why the compiler will go to the opposite side to evaluate a more nested type. – user10739302 Dec 09 '18 at 12:56
  • Consider creating a bug report at: https://github.com/rust-lang/rust/issues – Peter Hall Dec 09 '18 at 13:11
  • See also [What does “Overflow evaluating the requirement” mean and how can I fix it](https://stackoverflow.com/q/31196422/155423); ["Overflow evaluating the requirement” but that kind of recursion should not happen at all](https://stackoverflow.com/q/39397157/155423); [Curiously recurring generic trait pattern: overflow evaluating the requirement](https://stackoverflow.com/q/50657585/155423); [What's going on with this bizarre recursive type error in Rust?](https://stackoverflow.com/q/53405287/155423). – Shepmaster Dec 09 '18 at 16:27
  • The solution seems to be to introduce temporary type variables for shared type structures: https://users.rust-lang.org/t/type-level-fibonacci-sequence-results-in-overflow-evaluating-the-requirement/23058/6 – starblue Dec 10 '18 at 10:29

0 Answers0