Try-finally block prevents StackOverflowError

Question

Take a look at the following two methods:

public static void foo() {
    try {
        foo();
    } finally {
        foo();
    }
}

public static void bar() {
    bar();
}

Running bar() clearly results in a StackOverflowError, but running foo() does not (the program just seems to run indefinitely). Why is that?

Does the JVM not allow tail-call optimization? That would convert the infinite recursion into an infinite loop. — dan04, Sep 15 '12 at 16:40
Formally, the program will eventually stop because errors thrown during the processing of the `finally` clause will propagate to the next level up. But don't hold your breath; the number of steps taken will be about 2 to the (maximum stack depth) and the throwing of exceptions isn't exactly cheap either. — Donal Fellows, Sep 15 '12 at 16:41
@dan04 While it might allow it, what makes you think that it's a correct optimization in this case? (Hint: it isn't, as the end of the `finally` block isn't free.) — Donal Fellows, Sep 15 '12 at 16:43
@dan04: Java doesn't do TCO, IIRC to ensure having full stack traces, and for something related to reflection (probably having to do with stack traces as well). — ninjalj, Sep 15 '12 at 16:47
Interestingly enough when I tried this out on .Net (using Mono), the program crashed with a StackOverflow error without ever calling finally. — Kibbee, Sep 15 '12 at 18:55
@Kibbee different runtime library altogether. I'm 99% sure that in .NET you can't catch stack overflows. — Matthew Scharley, Sep 16 '12 at 03:19
@Kibbee That's by design. From [StackOverflowException](http://msdn.microsoft.com/en-us/library/system.stackoverflowexception.aspx): "Starting with the .NET Framework version 2.0, a StackOverflowException object cannot be caught by a try-catch block and the corresponding process is terminated by default." In .NET 1.1 I believe you would get the same behaviour as Java. — verdesmarald, Sep 16 '12 at 06:28
this is one of the puzzles in `Java™ Puzzlers: Traps, Pitfalls, and Corner Cases` book — Prince John Wesley, Sep 16 '12 at 08:45

Peter Lawrey · Accepted Answer · 2012-09-15T17:17:52.150

332

It doesn't run forever. Each stack overflow causes the code to move to the finally block. The problem is that it will take a really, really long time. The order of time is O(2^N) where N is the maximum stack depth.

Imagine the maximum depth is 5

foo() calls
    foo() calls
       foo() calls
           foo() calls
              foo() which fails to call foo()
           finally calls
              foo() which fails to call foo()
       finally
           foo() calls
              foo() which fails to call foo()
           finally calls
              foo() which fails to call foo()
    finally calls
       foo() calls
           foo() calls
              foo() which fails to call foo()
           finally calls
              foo() which fails to call foo()
       finally
           foo() calls
              foo() which fails to call foo()
           finally calls
              foo() which fails to call foo()
finally calls
    foo() calls
       foo() calls
           foo() calls
              foo() which fails to call foo()
           finally calls
              foo() which fails to call foo()
       finally
           foo() calls
              foo() which fails to call foo()
           finally calls
              foo() which fails to call foo()
    finally calls
       foo() calls
           foo() calls
              foo() which fails to call foo()
           finally calls
              foo() which fails to call foo()
       finally
           foo() calls
              foo() which fails to call foo()
           finally calls
              foo() which fails to call foo()

To work each level into the finally block take twice as long an the stack depth could be 10,000 or more. If you can make 10,000,000 calls per second, this will take 10^3003 seconds or longer than the age of the universe.

edited Sep 15 '12 at 17:17

answered Sep 15 '12 at 16:25

Peter Lawrey

525,659
79
751
1,130

4

Nice, even if I try to make the stack as small as possible via `-Xss`, I get a depth of [150 - 210], so 2^n ends up being a [47 - 65] digits number. Not going to wait that long, that is near enough to infinity for me. – ninjalj Sep 15 '12 at 17:05
64

@oldrinb Just for you, I increased the depth to 5. ;) – Peter Lawrey Sep 15 '12 at 17:18
4

So, at the end of the day when `foo` finally does terminate, it will result in a `StackOverflowError`? – arshajii Sep 15 '12 at 21:29
5

following the math, yup. the last stack overflow from the last finally which failed to stack overflow will exit with... stack overflow =P. couldn't resist. – WhozCraig Sep 15 '12 at 23:13
no doubt. I posted a synthesized version of this dump toward the end of this question page in another answer, but it is there only to support Peter's point. If you want to up-vote it, I ask you to up-vote his answer instead. – WhozCraig Sep 17 '12 at 06:30
1

So does this actually mean even that try catch code also should end up in stackoverflow error?? – LPD Jan 04 '13 at 13:33
1

Its infinite to me, I get 10528 foo calls, then 'finally' takes it back to 10524, then back to 10528, then back to 10524 & so on.... Very interesting however. – Stu Whyte Mar 07 '14 at 15:41
@StuWhyte That shouldn't be the case, I would check your numbers. – Peter Lawrey Mar 07 '14 at 21:54
1

As [shown here](https://stackoverflow.com/a/27047776/2711488), the maximum recursion depth depends heavily on the state of compilation/optimization, and that’s for a method that does something (counting). The impact of optimization can be even higher for a method that is actually a no-op (besides the recursion). Since running as-if having an infinite stack is a legal execution, it is possible that the optimized code runs forever. Or runs a much longer time than expected. – Holger Feb 12 '18 at 11:10
@Holger while not infinite, the run time could be longer than the age of the universe, or the time the earth has left. – Peter Lawrey Feb 12 '18 at 12:18
@PeterLawrey and running as long as the computer’s remaining lifetime is already enough to make the difference irrelevant… – Holger Feb 12 '18 at 12:26

ninjalj · Answer 2 · 2012-09-15T17:02:32.583

40

When you get an exception from the invocation of foo() inside the try, you call foo() from finally and start recursing again. When that causes another exception, you'll call foo() from another inner finally(), and so on almost ad infinitum.

edited Sep 15 '12 at 17:02

answered Sep 15 '12 at 15:53

ninjalj

42,493
9
106
148

5

Presumably, a StackOverflowError (SOE) is sent when there is no more space on the stack to call new methods. How can `foo()` be called from finally *after* a SOE? – assylias Sep 15 '12 at 16:02
4

@assylias: if there's not enough space, you will return from the latest `foo()` invocation, and invoke `foo()` in the `finally` block of your current `foo()` invocation. – ninjalj Sep 15 '12 at 16:10
+1 to ninjalj. You will not call foo from *anywhere* once you cannot call foo due to the overflow condition. this includes from the finally block, which is why this will, eventually (age of the universe) terminate. – WhozCraig Sep 16 '12 at 06:00

score 38 · Answer 3 · answered Sep 15 '12 at 15:54

Try running the following code:

    try {
        throw new Exception("TEST!");
    } finally {
        System.out.println("Finally");
    }

You will find that the finally block executes before throwing an Exception up to the level above it. (Output:

Finally

Exception in thread "main" java.lang.Exception: TEST! at test.main(test.java:6)

This makes sense, as finally is called right before exiting the method. This means, however, that once you get that first StackOverflowError, it will try to throw it, but the finally must execute first, so it runs foo() again, which gets another stack overflow, and as such runs finally again. This keeps happening forever, so the exception is never actually printed.

In your bar method however, as soon as the exception occurs, it is just thrown straight up to the level above, and will be printed

Downvote. "keeps happening forever" is wrong. See other answers. — jcsahnwaldt Reinstate Monica, Jul 26 '18 at 14:48

WhozCraig · Answer 4 · 2012-09-18T22:08:17.073

In effort to provide reasonable evidence that this WILL eventually terminate, I offer the following rather meaningless code. Note: Java is NOT my language, by any stretch of the most vivid imagination. I proffer this up only to support Peter's answer, which is the correct answer to the question.

This attempts to simulate the conditions of what happens when an invoke can NOT happen because it would introduce a stack overflow. It seems to me the hardest thing people are failing to grasp in that the invoke does not happen when it cannot happen.

public class Main
{
    public static void main(String[] args)
    {
        try
        {   // invoke foo() with a simulated call depth
            Main.foo(1,5);
        }
        catch(Exception ex)
        {
            System.out.println(ex.toString());
        }
    }

    public static void foo(int n, int limit) throws Exception
    {
        try
        {   // simulate a depth limited call stack
            System.out.println(n + " - Try");
            if (n < limit)
                foo(n+1,limit);
            else
                throw new Exception("StackOverflow@try("+n+")");
        }
        finally
        {
            System.out.println(n + " - Finally");
            if (n < limit)
                foo(n+1,limit);
            else
                throw new Exception("StackOverflow@finally("+n+")");
        }
    }
}

The output of this little pointless pile of goo is the following, and the actual exception caught may come as a surprise; Oh, and 32 try-calls (2^5), which is entirely expected:

1 - Try
2 - Try
3 - Try
4 - Try
5 - Try
5 - Finally
4 - Finally
5 - Try
5 - Finally
3 - Finally
4 - Try
5 - Try
5 - Finally
4 - Finally
5 - Try
5 - Finally
2 - Finally
3 - Try
4 - Try
5 - Try
5 - Finally
4 - Finally
5 - Try
5 - Finally
3 - Finally
4 - Try
5 - Try
5 - Finally
4 - Finally
5 - Try
5 - Finally
1 - Finally
2 - Try
3 - Try
4 - Try
5 - Try
5 - Finally
4 - Finally
5 - Try
5 - Finally
3 - Finally
4 - Try
5 - Try
5 - Finally
4 - Finally
5 - Try
5 - Finally
2 - Finally
3 - Try
4 - Try
5 - Try
5 - Finally
4 - Finally
5 - Try
5 - Finally
3 - Finally
4 - Try
5 - Try
5 - Finally
4 - Finally
5 - Try
5 - Finally
java.lang.Exception: StackOverflow@finally(5)

Karoly Horvath · Answer 5 · 2012-09-15T16:14:31.227

23

Learn to trace your program:

public static void foo(int x) {
    System.out.println("foo " + x);
    try {
        foo(x+1);
    } 
    finally {
        System.out.println("Finally " + x);
        foo(x+1);
    }
}

This is the output I see:

[...]
foo 3439
foo 3440
foo 3441
foo 3442
foo 3443
foo 3444
Finally 3443
foo 3444
Finally 3442
foo 3443
foo 3444
Finally 3443
foo 3444
Finally 3441
foo 3442
foo 3443
foo 3444
[...]

As you can see the StackOverFlow is thrown at some layers above, so you can do additional recursion steps till you hit another exception, and so on. This is an infinite "loop".

edited Sep 15 '12 at 16:14

answered Sep 15 '12 at 16:07

Karoly Horvath

94,607
11
117
176

11

it's not actually infinite loop, if you're patient enough it will eventually terminate. I won't hold my breath for it though. – Lie Ryan Sep 15 '12 at 17:19
4

I would posit that it is infinite. Each time it reaches the maximum stack depth it throws an exception and unwinds the stack. However in the finally it calls Foo again causing it to again reuse the stack space it has just recovered. It will go back and forth throwing exceptions and then going back Dow the stack until it happens again. Forever. – Kibbee Sep 15 '12 at 18:24
Also, you'll want that first system.out.println to be in the try statement, otherwise it will unwind the loop further than it should. possibly causing it to halt. – Kibbee Sep 15 '12 at 18:38
1

@Kibbee The problem with your argument is that when it calls `foo` the second time, in the `finally` block, it is no longer in a `try`. So while it will go back down the stack and create more stack overflows once, the second time it will just rethrow the error produced by the second call to `foo`, instead of re-deepening. – amalloy Aug 20 '15 at 02:48

score 1 · Answer 6 · answered Apr 11 '18 at 00:08

The program merely seems to run forever; it actually terminates, but it takes exponentially more time the more stack space you have. To prove that it finishes, I wrote a program that first depletes most of the available stack space, and then calls foo, and finally writes a trace of what happened:

foo 1
  foo 2
    foo 3
    Finally 3
  Finally 2
    foo 3
    Finally 3
Finally 1
  foo 2
    foo 3
    Finally 3
  Finally 2
    foo 3
    Finally 3
Exception in thread "main" java.lang.StackOverflowError
    at Main.foo(Main.java:39)
    at Main.foo(Main.java:45)
    at Main.foo(Main.java:45)
    at Main.foo(Main.java:45)
    at Main.consumeAlmostAllStack(Main.java:26)
    at Main.consumeAlmostAllStack(Main.java:21)
    at Main.consumeAlmostAllStack(Main.java:21)
    ...

The code:

import java.util.Arrays;
import java.util.Collections;
public class Main {
  static int[] orderOfOperations = new int[2048];
  static int operationsCount = 0;
  static StackOverflowError fooKiller;
  static Error wontReachHere = new Error("Won't reach here");
  static RuntimeException done = new RuntimeException();
  public static void main(String[] args) {
    try {
      consumeAlmostAllStack();
    } catch (RuntimeException e) {
      if (e != done) throw wontReachHere;
      printResults();
      throw fooKiller;
    }
    throw wontReachHere;
  }
  public static int consumeAlmostAllStack() {
    try {
      int stackDepthRemaining = consumeAlmostAllStack();
      if (stackDepthRemaining < 9) {
        return stackDepthRemaining + 1;
      } else {
        try {
          foo(1);
          throw wontReachHere;
        } catch (StackOverflowError e) {
          fooKiller = e;
          throw done; //not enough stack space to construct a new exception
        }
      }
    } catch (StackOverflowError e) {
      return 0;
    }
  }
  public static void foo(int depth) {
    //System.out.println("foo " + depth); Not enough stack space to do this...
    orderOfOperations[operationsCount++] = depth;
    try {
      foo(depth + 1);
    } finally {
      //System.out.println("Finally " + depth);
      orderOfOperations[operationsCount++] = -depth;
      foo(depth + 1);
    }
    throw wontReachHere;
  }
  public static String indent(int depth) {
    return String.join("", Collections.nCopies(depth, "  "));
  }
  public static void printResults() {
    Arrays.stream(orderOfOperations, 0, operationsCount).forEach(depth -> {
      if (depth > 0) {
        System.out.println(indent(depth - 1) + "foo " + depth);
      } else {
        System.out.println(indent(-depth - 1) + "Finally " + -depth);
      }
    });
  }
}

You can try it online! (Some runs might call foo more or fewer times than others)

Try-finally block prevents StackOverflowError

6 Answers6

Linked

Related