Detect recursive instantiation of generic functions

[dtolnay]

We currently have a quite helpful diagnostic for unconditionally recursive functions:

pub fn recur() {
    recur();
}

warning: function cannot return without recurring
 --> src/main.rs:1:1
  |
1 | pub fn recur() {
  | ^^^^^^^^^^^^^^ cannot return without recurring
2 |     recur();
  |     ------- recursive call site
  |
  = note: #[warn(unconditional_recursion)] on by default
  = help: a `loop` may express intention better if this is on purpose

And infinitely sized recursive types:

pub struct S {
    s: S,
}

error[E0072]: recursive type `S` has infinite size
 --> src/main.rs:1:1
  |
1 | pub struct S {
  | ^^^^^^^^^^^^ recursive type has infinite size
2 |     s: S,
  |     ---- recursive without indirection
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `S` representable

But no good error for infinite instantiation of generic functions.

The following is minimized from @LPGhatguy's syntax tree library (original playground).

trait Serializer {
    type Associated;
    fn leaf() -> Self::Associated { unimplemented!() }
}

pub enum Expression {
    Leaf,
    Node(Box<Expression>),
}

fn print<S: Serializer>(e: Expression) {
    match e {
        Expression::Leaf => drop(S::leaf()),
        Expression::Node(e) => print::<Wrapper<S>>(*e),
    }
}

use std::marker::PhantomData as Wrapper;
impl<S: Serializer> Serializer for Wrapper<S> {
    type Associated = S::Associated;
}

enum Json {}
impl Serializer for Json {
    type Associated = ();
}

fn main() {
    print::<Json>(Expression::Leaf);
}

Here the instantiation of print::<Json> requires instantiating print::<Wrapper<Json>> which calls print::<Wrapper<Wrapper<Json>> which calls print::<Wrapper<Wrapper<Wrapper<Json>>>... (The use case in this example is noteworthy because it is conceptually sensible; the trouble happens only when combined with Rust's approach of monomorphizing generic functions. Analogous code in Swift where generics are not monomorphized does not hit the same overflow.)

As of rustc 1.27.0-nightly we get an unhelpful message with a recommendation that can't work. It would be better to detect this pattern of a generic function generating a tower of recursive instantiations.

error[E0275]: overflow evaluating the requirement `<Json as Serializer>::Associated`
  |
  = help: consider adding a `#![recursion_limit="128"]` attribute to your crate

error: aborting due to previous error

[ishitatsuyuki]

I think we'll be able to reason about recursion once we integrate the new logic based trait resolver, aka chalk.

[estebank]

Current output:

error: reached the recursion limit while instantiating `print::<PhantomData<PhantomData<...>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
  --> src/main.rs:14:32
   |
14 |         Expression::Node(e) => print::<Wrapper<S>>(*e),
   |                                ^^^^^^^^^^^^^^^^^^^^^^^
   |
note: `print` defined here
  --> src/main.rs:11:1
   |
11 | fn print<S: Serializer>(e: Expression) {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: the full type name has been written to '/playground/target/debug/deps/playground-07b5fd22867752b9.long-type.txt'

Still not great.

[estebank]

Another example from #42154:

fn fold<F:FnMut(usize, u8) -> usize>(recurse: bool, mut init: usize, mut f: F) -> usize {
    if recurse {
        for i in 0..2 {
            init = f(init, i);
            init = fold(false, init, &mut f)
        }
        init
    } else {
        init
    }
}

fn main() {
    fold(true, 0, |a, b| a + (b as usize));
}

[estebank]

Another case from #51486:

enum Foo<T> {
    A(T),
    B(Box<Foo<T>>, Box<Foo<T>>),
}

impl<T> Foo<T> {
    fn map<F, T2>(self, mut f: F) -> Foo<T2>
    where
        F: FnMut(T) -> T2,
    {
        match self {
            Foo::A(x) => Foo::A(f(x)),
            Foo::B(x, y) => Foo::B(Box::new(x.map(&mut f)), Box::new(y.map(&mut f))),
        }
    }
}

fn main() {
    Foo::A(0).map(|x| x + 1);
}