Better error message for polymorphic recursion

[migmit]

Can't compile:

enum Nil {Nil}
struct Cons<T> {head:int, tail:T}
trait Dot {fn dot(other:self) -> int;}
impl Nil:Dot {
  fn dot(_:Nil) -> int {0}
}
impl<T:Dot> Cons<T>:Dot {
  fn dot(other:Cons<T>) -> int {
    self.head * other.head + self.tail.dot(other.tail)
  }
}
fn test<T:Dot> (n:int, i:int, first:T, second:T) ->int {
  match n {
    0 => {first.dot(second)}
    _ => {test (n-1, i+1, Cons {head:2*i+1, tail:first}, Cons{head:i*i, tail:second})}
  }
}
fn main() {
  let n = test(5, 0, Nil, Nil);
  io::println(fmt!("%d", n));
}

Same code in Java, C# or Haskell works.

[jesse99]

After adding extern mod std; the error I get is:

test.rs:27:0: 34:1 error: overly deep expansion of inlined function
test.rs:27 fn test<T:Dot> (n: int, i: int, first: T, second: T) ->int
test.rs:28 {
test.rs:29  match n
test.rs:30  {
test.rs:31      0 => {first.dot(second)}
test.rs:32      _ => {test (n-1, i+1, Cons {head:2*i+1, tail:first}, Cons{head:i*i, tail:second})}

I was not able to fix this by adding #[inline(never)] to test.

[migmit]

In fact, I know of one other language that fails this test (well... Basic surely doesn't fail it, because this test is meaningless for Basic) — it's C++.

[catamorphism]

As far as I know, Rust doesn't support polymorphic recursion and there aren't any plans to change that.

The error message should probably be more informative, though (this isn't really about inlining, that's an implementation detail). It shouldn't be too hard to check for this in typeck.

(I changed the issue title to reflect what the issue is.)

[migmit]

That's a shame. I was really hoping that Rust is going to be something like "low-level Haskell". Seems like generics are really just C++ templates (without certain advantages).

[catamorphism]

Is there a particular application you had in mind where you would need polymorphic recursion?

Generics are unlike C++ templates because they're typechecked before expansion; this makes a huge difference in usability since type error messages refer to the code you wrote, not the code the compiler expanded. However, it's true that generics are less powerful than Haskell- or ML-style polymorphic, because Rust has no polymorphic types; items rather than types have type parameters. This was a design decision made very early on and so far there's been no particular reason we've seen to change it.

[nikomatsakis]

@migmit In many ways, Rust is like low-level Haskell. That's why this test doesn't work! Because we are operating at a low level, we don't have uniform representation and implicit boxing and so forth. Therefore, like C++, we monomorphize generic functions---this implies that we would require an infinite set of functions to deal with recursive functions like the one you wrote here (note that other cases of polymorphic recursion work just fine, so long as they don't generate an infinite stream of types). I am going to close this as "not a bug, working as designed".

[catamorphism]

@nikomatsakis I agree that it's working as designed, but I still think we should have a better error message than "overly deep expansion of inlined function", which doesn't say what the problem is.

[emberian]

Someone came in IRC recently with this exact same problem (but I think they were just testing the limits of the language rather than trying to do anything serious)

[emberian]

The usecase was encoding a complete binary tree as a type.

[carl-eastlund]

I think it's worth clarifying here that in the two closed bugs immediately above, Rust isn't triggering an error at all, so polymorphic recursion sometimes goes completely unnoticed and just causes compilation to diverge. It doesn't always even trigger an inlining error. This makes it very hard to track down, so any improvement in detection and reporting would be greatly appreciated.

Thanks, guys!

[pnkfelix]

assigning P-low. not 1.0 blocker.

[bombless]

Modern form of the example code give us new output now (play).

enum Nil {Nil}
struct Cons<T> {head: i32, tail: T}
trait Dot {fn dot(self, other: Self) -> i32;}
impl Dot for Nil {
  fn dot(self, _:Nil) -> i32 {0}
}
impl<T:Dot> Dot for Cons<T> {
  fn dot(self, other: Cons<T>) -> i32 {
    self.head * other.head + self.tail.dot(other.tail)
  }
}
fn test<T:Dot> (n: i32, i: i32, first: T, second: T) ->i32 {
  match n {
    0 => {first.dot(second)}
    _ => {test (n-1, i+1, Cons {head:2*i+1, tail:first}, Cons{head:i*i, tail:second})}
  }
}
fn main() {
  let n = test(5, 0, Nil::Nil, Nil::Nil);
  println!("{}", n)
}

https://gist.github.com/pnkfelix/db9c9fc7a971289c17c7

---

pnkfelix: I took the liberty of moving the original content into a gist (linked above) because it was 200 lines of very regular output.

[DemiMarie]

Should this be closed now?

[bombless]

I believe the error message here is still waiting to be improved.

[birkenfeld]

New (and sole) message in nightly:

<anon>:12:1: 17:2 error: reached the recursion limit while instantiating `test::<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Nil>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
<anon>:12 fn test<T:Dot> (n: i32, i: i32, first: T, second: T) ->i32 {
<anon>:13   match n {
<anon>:14     0 => {first.dot(second)}
<anon>:15     _ => {test (n-1, i+1, Cons {head:2*i+1, tail:first}, Cons{head:i*i, tail:second})}
<anon>:16   }
<anon>:17 }

Not pretty, but much better than before. Fixed?

[pnkfelix]

I don't consider this fixed, because I don't think the error message is good enough in most cases.

Ideally we would detect polymorphic recursion explicitly (rather than having it caught by our other safe-guards against infinite-regression), and explain the origin of it in the source program.

E.g. say something like (off the top of my head):

The program cannot be compiled, because it has a cycle of calls that would require the function fn test<T:Dot>(n: i32, i: i32, first: T, second: T) -> i32 to be instantiated infinitely often, starting with with the instantiations T=Nil, T=Cons<Nil>, T=Cons<Cons<Nil>> ...

---

In this case it is a cycle of function calls that exposes polymorphic recursion, but in other cases like #33545, the polymorphic recursion arises more directly in a type like:

enum E1<T> {
    V1(T),
    V2(Box<E1<E2<T>>>)
}

where the type E1<T> requires instantiations E1<E2<T>>, E1<E2<E2<T>>, E1<E2<E2<E2<T>>>

(so the error message would need to be adjusted accordingly for such cases.)

---

In case its not clear, I still regard this as a low priority work item, but something that ideally would be addressed eventually.

[DemiMarie]

An even better approach (from the user's perspective) would be to allow polymorphic recursion so long as the sizes and operations matched, such that the types could be erased – i.e. polymorphic recursion is accepted as long as it could be compiled. But I think that would be very much not worth it.

[durka]

@birkenfeld not fixed because it doesn't always detect the recursion. The complete binary tree still hangs (with no output) during typeck, if you instantiate it:

enum Perfect<T> { Tip(T), Fork(Box<Perfect<(T, T)>>) }

fn main() {
    let _ = Perfect::Tip(42);
}

(cc @antalsz @RalfJung)

[tupshin]

I just ran into the hanging version of this in my own code. took a long time to figure out how to change it enough so that I would actually get the overflow error

[nikomatsakis]

Hmm, @arielb1 added a kind of "maximum size of a type" check a while back, perhaps it could be used to cause compilation to abort sooner here? @arielb1, what do you think?

[steveklabnik]

Triage: no change

[varkor]

This issue was recently discussed on Zulip.

[DemiMarie]

The best option I can think of is to report an error if type checking takes too long.

[RalfJung]

(Rust typechecking being undecidable is not really a bug -- with a trait system as expressive as ours, this is to be expected.)

[RalfJung]

Yes, hanging is a bug -- something there clearly needs a counter or so, similar to recursion_limit.

I was just commenting on the undecidable aspect.

[camelid]

I updated the code to be modern Rust and I formatted it (playground):

enum Nil {
    Nil,
}

struct Cons<T> {
    head: i32,
    tail: T,
}

trait Dot: Sized {
    fn dot(self, other: Self) -> i32;
}

impl Dot for Nil {
    fn dot(self, _: Nil) -> i32 {
        0
    }
}

impl<T: Dot> Dot for Cons<T> {
    fn dot(self, other: Cons<T>) -> i32 {
        self.head * other.head + self.tail.dot(other.tail)
    }
}

fn test<T: Dot>(n: i32, i: i32, first: T, second: T) -> i32 {
    match n {
        0 => first.dot(second),
        _ => test(
            n - 1,
            i + 1,
            Cons {
                head: 2 * i + 1,
                tail: first,
            },
            Cons {
                head: i * i,
                tail: second,
            },
        ),
    }
}

fn main() {
    let n = test(5, 0, Nil::Nil, Nil::Nil);
    println!("{}", n);
}

Here's the current rustc output:

   Compiling playground v0.0.1 (/playground)
error: overflow while checking whether `Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Nil>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>` requires drop

error: reached the recursion limit while instantiating `test::<Cons<Cons<Cons<Cons<Cons<...>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
  --> src/main.rs:29:14
   |
29 |           _ => test(
   |  ______________^
30 | |             n - 1,
31 | |             i + 1,
32 | |             Cons {
...  |
39 | |             },
40 | |         ),
   | |_________^
   |
note: `test` defined here
  --> src/main.rs:26:1
   |
26 | fn test<T: Dot>(n: i32, i: i32, first: T, second: T) -> i32 {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: the full type name has been written to '/playground/target/debug/deps/playground-bb452379b09dd6b8.long-type.txt'

error: aborting due to 2 previous errors

error: could not compile `playground`

To learn more, run the command again with --verbose.

[jyn514]

The best option I can think of is to report an error if type checking takes too long.
Yes, hanging is a bug -- something there clearly needs a counter or so, similar to recursion_limit.

I'm going to close this since it now gives a type-length-limit error.

[camelid]

It might still be a good idea to add a note: that Rust doesn't support polymorphic recursion though.