Why does the C# compiler not even warn about endless recursion?

Question

A legacy app is in an endless loop at startup; I don't know why/how yet (code obfuscation contest candidate), but regarding the method that's being called over and over (which is called from several other methods), I thought, "I wonder if one of the methods that calls this is also calling another method that also calls it?"

I thought: "Nah, the compiler would be able to figure that out, and not allow it, or at least emit a warning!"

So I created a simple app to prove that would be the case:

public partial class Form1 : Form
{
    public Form1()
    {
        InitializeComponent();
    }

    private void button1_Click(object sender, EventArgs e)
    {
        method1();
    }

    private void button2_Click(object sender, EventArgs e)
    {
        method2();
    }

    private void method1()
    {
        MessageBox.Show("method1 called, which will now call method2");
        method2();
    }

    private void method2()
    {
        MessageBox.Show("method2 called, which will now call method1");
        // Note to self: Write an article entitled, "Copy-and-Paste Considered Harmful"
        method1();
    }
}

...but no! It compiles just fine. Why wouldn't the compiler flag this code as questionable at best? If either button is mashed, you are in never-never land!

Okay, sometimes you may want an endless loop (pacemaker code, etc.), but still I think a warning should be emitted.

Answer 1

That's not an endless loop, but an endless recursion. And this is much worse, since they can lead to a stack overflow. Endless recursions are not desired in most languages, unless you are programming malware. Endless loops, however, are often intentional. Services typically run in endless loops.

In order to detect this kind of situation, the compiler would have to analyze the code by following the method calls; however the C# compiler limits this process to the immediate code within the current method. Here, uninitialized or unused variables can be tracked and unreachable code can be detected, for instance. There is a tradeoff to make between the compiling speed and the depth of static analysis and optimizations.

Also it is hardly possible to know the real intention of the programmer.

Imagine that you wrote a method that is perfectly legal. Suddenly because you are calling this method from another place, your compiler complains and tells you that your method is no more legal. I can already see the flood of posts on SO like: "My method compiled yesterday. Today it does not compile any more. But I didn't change it".

Answer 2

1. As you said sometimes people want infinite loops. And the jit-compiler of .net supports tailcall optimization, so you might not even get a stack overflow for endless recursion like you did it.

2. For the general case, predicting whether or not a program is going to terminate at some point or stuck in an infinite loop is impossible in finite time. It's called the halting problem. All a compiler can possibly find are some special cases, where it is easy to decide.

Answer 3

To put it very simply: it's not the compiler's job to question your coding patterns.

You could very well write a Main method that does nothing but throw an Exception. It's a far easier pattern to detect and a much more stupid thing to do; yet the compiler will happily allow your program to compile, run, crash and burn.

With that being said, since technically an endless loop / recursion is perfectly legal as far as the compiler is concerned, there's no reason why it should complain about it.

Actually, it would be very hard to figure out at compile time that the loop can't ever be broken at runtime. An exception could be thrown, user interaction could happen, a state might change somewhere on a specific thread, on a port you are monitoring, etc... there's way too much possibilities for any code analysis tool out there to establish, without any doubt, that a specific recursing code segment will inevitably cause an overflow at runtime.

I think the right way to prevent these situations is through unit testing organization. The more code paths you are covering in your tests, the less likely you are to ever face such a scenario.

Answer 4

Because its nearly impossible to detect!

In the example you gave, it is obvious (to us) that the code will loop forever. But the compiler just sees a function call, it doesn't necessarily know at the time what calls that function, what conditional logic could change the looping behavior etc.

For example, with this slight change you aren't in an infinite loop anymore:

private bool method1called = false;
private void method1()
{
    MessageBox.Show("method1 called, which will now call method2");

    if (!method1called)
       method2();

    method1called = true;
}

private void method2()
{
    MessageBox.Show("method2 called, which will now call method1");
    method1();
}

Without actually running the program, how would you know that it isn't looping? I could potentially see a warning for while (true), but that has enough valid use cases that it also makes sense to not put a warning in for it.

A compiler is just parsing the code and translating to IL (for .NET anyways). You can get limited information like variables not being assigned while doing that (especially since it has to generate the symbol table anyways) but advanced detection like this is generally left to code analysis tools.

Answer 5

I found this on the Infinite Loop Wiki found here: http://en.wikipedia.org/wiki/Infinite_loop#Intentional_looping

There are a few situations when this is desired behavior. For example, the games on cartridge-based game consoles typically have no exit condition in their main loop, as there is no operating system for the program to exit to; the loop runs until the console is powered off.

Antique punchcard-reading unit record equipment would literally halt once a card processing task was completed, since there was no need for the hardware to continue operating, until a new stack of program cards were loaded.

By contrast, modern interactive computers require that the computer constantly be monitoring for user input or device activity, so at some fundamental level there is an infinite processing idle loop that must continue until the device is turned off or reset. In the Apollo Guidance Computer, for example, this outer loop was contained in the Exec program, and if the computer had absolutely no other work to do it would loop running a dummy job that would simply turn off the "computer activity" indicator light.

Modern computers also typically do not halt the processor or motherboard circuit-driving clocks when they crash. Instead they fall back to an error condition displaying messages to the operator, and enter an infinite loop waiting for the user to either respond to a prompt to continue, or to reset the device.

Hope this helps.