How is a StackOverflowException detected?

Question

TL;TR
When I asked the question I assumed a StackOverflowException is a mechanism to prevent applications to run infinitely. This is not true.
A StackOverflowException is not being detected.
It is thrown when the stack does not have the capacity to allocate more memory.

[Original question:]

This is a general question, which may has different answers per programming language.
I am unsure how languages other than C# process a stack overflow.

I was going through exceptions today and kept thinking about how a StackOverflowException can be detected. I believe it is not possible to say f.e. if the stack is 1000 calls deep, then throw the exception. Because maybe in some cases the correct logic will be that deep.

What is the logic behind the detection of an infinite loop in my program?

StackOverflowException class:
https://msdn.microsoft.com/de-de/library/system.stackoverflowexception%28v=vs.110%29.aspx

Cross reference mentioned in the StackOverflowException class documentation:
https://msdn.microsoft.com/de-de/library/system.reflection.emit.opcodes.localloc(v=vs.110).aspx

I just added the stack-overflow tag to this question, and the description says it is being thrown when the call stack consumes too much memory. Does that mean the call stack is some sort of path to the current executing position of my program and if it cannot store more path information, then the exception is thrown?

Answer 1

Stack overflows

I'll make it easy for you; but this is actually quite complex... Note that I will generalize quite a bit here.

As you might know, most languages use the stack for storing call information. See also: https://msdn.microsoft.com/en-us/library/zkwh89ks.aspx for how cdecl works. If you call a method, you push stuff on the stack; if you return, you pop stuff from the stack.

Note that recursion isn't normally 'inlined'. (Note: I explicitly say 'recursion' here and not 'tail recursion'; the latter works like a 'goto' and doesn't grow the stack).

The easiest way to detect a stack overflow is to check your current stack depth (e.g. bytes used) - and if it hits a boundary, give an error. To clarify about this 'boundary check': the way these checks are done is normally by using guard pages; this means boundary checks aren't normally implemented as if-then-else checks (although some implementations exist...).

In most languages, each thread has its own stack.

Detecting infinite loops

Well now, here's a question I haven't heard for a while. :-)

Basically detecting all infinite loops requires you to solve the Halting Problem. Which is by the way an undecidable problem. This is definitely not done by compilers.

This doesn't mean you can't do any analysis; in fact, you can do quite a bit of analysis. However, also note that sometimes you want things to run indefinitely (such as the main loop in a web server).

Other languages

Also interesting... Functional languages use recursion, so they are basically bound by the stack. (That said, functional languages also tend to use tail recursion, which works more or less like a 'goto' and don't grow the stack.)

And then there's Logical languages.. well now, I'm not sure how to loop forever in that - you'll probably end up with something that won't evaluate at all (no solution can be found). (Though, this probably depends on the language... )

Yielding, async, continuations

An interesting concept is you might think of is called continuations. I've heard from Microsoft that when yield was first implemented, real continuations were considered as implementation. Continuations basically allow you to 'save' the stack, continue somewhere else and 'restore' the stack back at a later point... (Again, the details are much more complicated than this; this is just the basic idea).

Unfortunately Microsoft didn't go for this idea (although I can imagine why), but implemented it by using a helper class. Yield and async in C# work by adding a temporary class and interning all the local variables within the class. If you call a method that does a 'yield' or 'async', you actually create a helper class (from within the method you call and push on the stack) that's pushed on the heap. The class that's pushed on the heap has the functionality (e.g. for yield this is the enumeration implementation). The way this is done is by using a state variable, which stores the location (e.g. some state id) where the program should continue when MoveNext is called. A branch (switch) using this ID takes care of the rest. Note that this mechanism does nothing 'special' with the way the stack works itself; you can implement the same by yourself using classes and methods (it just involves more typing :-)).

Solving stack overflows with a manual stack

I always like a good flood fill. A picture will give you a hell of a lot of recursion calls if you do this wrong... say, like this:

public void FloodFill(int x, int y, int color)
{
    // Wait for the crash to happen...
    if (Valid(x,y))
    {
        SetPixel(x, y, color);
        FloodFill(x - 1, y, color);
        FloodFill(x + 1, y, color);
        FloodFill(x, y - 1, color);
        FloodFill(x, y + 1, color);
    }
}

There's nothing wrong with this code though. It does all the work, but our stack gets in the way. Having a manual stack solves this, even though the implementation is basically the same:

public void FloodFill(int x, int y, int color)
{
    Stack<Tuple<int, int>> stack = new Stack<Tuple<int, int>>();
    stack.Push(new Tuple<int, int>(x, y));
    while (stack.Count > 0)
    {
        var current = stack.Pop();

        int x2 = current.Item1;
        int y2 = current.Item2;

        // "Recurse"
        if (Valid(x2, y2))
        {
            SetPixel(x2, y2, color);
            stack.Push(new Tuple<int, int>(x2-1, y2));
            stack.Push(new Tuple<int, int>(x2+1, y2));
            stack.Push(new Tuple<int, int>(x2, y2-1));
            stack.Push(new Tuple<int, int>(x2, y2+1));
        }
    }
}