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.