Why does the C# compiler go mad on this nested LINQ query?

I believe that it’s related to type inference and/or lambda generation (when type inference has to go in the opposite direction to normal), combined with overload resolution. Unfortunately, just supplying the type parameters doesn’t help the situation (where it presumably still has to perform the type checking).

The following code, which should logically be the equivalent code from yours, after lambdas have been analyzed, compiles without issue:

static void Main()
{
    var x = Enumerable.Range(0, 1).Sum(a);
}

private static int a(int a)
{
    return Enumerable.Range(0, 1).Sum(b);
}
private static int b(int b)
{
    return Enumerable.Range(0, 1).Sum(c);
}
private static int c(int c)
{
    return Enumerable.Range(0, 1).Sum(d);
}
private static int d(int d)
{
    return Enumerable.Range(0, 1).Sum(e);
}
private static int e(int e)
{
    return Enumerable.Range(0, 1).Sum(f);
}
private static int f(int f)
{
    return Enumerable.Range(0, 1).Count(g);
}
private static bool g(int g)
{
    return true;
}

I believe Eric Lippert has posted before that type inference is one of the places in the C# compiler where (certain problems) may force the compiler to try to solve an NP-Complete problem and its only real strategy (as here) is brute force. If I can find the relevant references, I’ll add them here.

The best reference I can find is here where Eric’s discussing the fact that it’s the overload resolution work that causes the real cost – remember, Enumerable.Sum has 10 overloads that accept a lambda/method.