Вопрос по recursion, try-finally, stack-overflow, java – Блок Try-finally предотвращает StackOverflowError

324

Взгляните на следующие два метода:

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

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

Бегbar() явно приводит кStackOverflowError, но работаетfoo() нет (программа, кажется, работает бесконечно).Why is that?

Это было бы "правильно" заbar(), хоть. dan04
@ dan04: Java не выполняет TCO, IIRC, чтобы гарантировать наличие полных трасс стека и что-то, связанное с отражением (вероятно, также имеющее отношение к трассировкам стека). ninjalj
Интересно, что когда я попробовал это в .Net (используя Mono), программа потерпела крах с ошибкой StackOverflow, не вызывая окончательно. Kibbee
Это худший кусок кода, который я когда-либо видел :) poitroae
Формально программа в конечном итоге остановится, потому что при обработкеfinally пункт будет распространяться на следующий уровень вверх. Но не задерживай дыхание; количество предпринятых шагов будет составлять примерно 2 (максимальная глубина стека), и выбрасывание исключений также не совсем дешево. Donal Fellows

Ваш Ответ

6   ответов
0

это фактически завершается, но это занимает экспоненциально больше времени, чем больше у вас стекового пространства. Чтобы доказать, что это заканчивается, я написал программу, которая сначала истощает большую часть доступного пространства стека, а затем вызываетfooи, наконец, пишет след того, что произошло:

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)
    ...

Код:

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);
      }
    });
  }
}

Вы можетепопробуйте это онлайн! (Некоторые пробеги могут вызватьfoo больше или меньше, чем другие)

23

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

Это вывод, который я вижу:

[...]
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
[...]

Как вы можете видеть, StackOverFlow создается на нескольких уровнях выше, поэтому вы можете выполнять дополнительные шаги рекурсии, пока не достигнете другого исключения, и так далее. Это бесконечный «цикл».

это на самом деле не бесконечный цикл, если вы достаточно терпеливы, он в конце концов прекратится. Я не задерживаю дыхание для этого все же.
Я бы сказал, что это бесконечно. Каждый раз, когда он достигает максимальной глубины стека, он генерирует исключение и раскручивает стек. Однако в конечном итоге он снова вызывает Foo, заставляя его снова использовать пространство стека, которое он только что восстановил. Он будет перебрасывать исключения, а затем возвращаться в стек до тех пор, пока это не произойдет снова. Навсегда.
Кроме того, вы захотите, чтобы первый system.out.println был в операторе try, иначе он размотает цикл дальше, чем следовало бы. возможно, заставляя его остановиться.
@ Kibbee Проблема с вашим аргументом в том, что когда он вызываетfoo во второй раз, вfinally блок, это больше не вtry, Таким образом, хотя он будет возвращаться обратно в стек и создавать дополнительные переполнения стека один раз, во второй раз он просто сбросит ошибку, вызванную вторым вызовомfooвместо повторного углубления.
327

блок finally. Проблема в том, что это займет очень много времени. Порядок времени O (2 ^ N), где N - максимальная глубина стека.

Представьте себе максимальную глубину 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()

Чтобы проработать каждый уровень в блоке finally, потребуется вдвое больше времени, а глубина стека может быть 10000 или больше. Если вы можете делать 10 000 000 вызовов в секунду, это займет 10 ^ 3003 секунды или дольше, чем возраст вселенной.

Хорошо, даже если я пытаюсь сделать стек как можно меньше с помощью-Xss, Я получаю глубину [150 - 210], так что 2 ^ n в конечном итоге становится числом [47 - 65] цифр. Я не собираюсь ждать так долго, это достаточно близко к бесконечности для меня.
@oldrinb Только для вас я увеличил глубину до 5.;)
Можете ли вы показать дерево на максимальной глубине 5?
Итак, в конце дня, когдаfoo наконец, завершается, это приведет кStackOverflowError? arshajii
после математики, да последнее переполнение стека от последнего finally, которому не удалось переполнить стек, завершится с ... переполнением стека = P. не смог устоять.
26

что это в конечном итоге прекратится, я предлагаю следующий довольно бессмысленный код. Примечание: Java не является моим языком, как ни крути. Я предлагаю это только для того, чтобы поддержать ответ Питера, которыйthe правильный ответ на вопрос.

Это попытка смоделировать условия того, что происходит, когда не может произойти вызов, потому что это приведет к переполнению стека. Мне кажется, что самое трудное, что люди не могут понять, это то, что призыв не происходит, когдаcannot бывает.

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("[email protected]("+n+")");
        }
        finally
        {
            System.out.println(n + " - Finally");
            if (n < limit)
                foo(n+1,limit);
            else
                throw new Exception("[email protected]("+n+")");
        }
    }
}

Результат этой маленькой бессмысленной груды слизи следующий, и фактическое обнаруженное исключение может стать неожиданностью; Да, и 32 попытки вызова (2 ^ 5), что вполне ожидаемо:

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: [email protected](5)
37

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

Вы обнаружите, что блок finally выполняется, прежде чем выбросить исключение на уровень выше него. (Выход:

Finally

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

Это имеет смысл, так как, наконец, вызывается перед выходом из метода. , Это означает, однако, что, как только вы получите это первымStackOverflowError, он попытается выбросить его, но, наконец, должен сначала выполнить, поэтому он работаетfoo() снова, который получает другое переполнение стека, и, как таковой, выполняется, наконец, снова. Это происходит вечно, поэтому исключение никогда не печатается.

Однако в вашем методе bar, как только возникает исключение, оно просто выбрасывается прямо на уровень выше и будет напечатано

Downvote. & quot; продолжается вечно & quot; неправильно. Смотрите другие ответы.
40

foo() внутриtry, ты звонишьfoo() отfinally и начать возвращаться снова. Когда это вызывает другое исключение, вы позвонитеfoo() из другого внутреннегоfinally()и так далее почтиad infinitum.

@assylias: если места недостаточно, вы вернетесь с последнейfoo() вызов и вызовfoo() вfinally блок вашего текущегоfoo() призывание.
+1 к ниндзялю Вы не будете звонить изanywhere как только вы не можете вызвать foo из-за условия переполнения. это включает в себя блок finally, поэтому он, в конце концов, (возраст вселенной) закончится.
Предположительно, StackOverflowError (SOE) отправляется, когда в стеке больше нет места для вызова новых методов. Как можетfoo() быть призванным в конце концовafter SOE?
@assylias читать дальшеfinally семантика.

Похожие вопросы