python - Python 3 中嵌套 For 循环的最大深度是多少？

Question

我想知道是否存在这样的“水平”。我知道 C 中的限制是 127，但我找不到任何有关 Python 的信息。

例如:

for True:                       # level 0
    for True:                   # level 1
        ...                  
        for True:               # level max
            print("something")

Answer 1

对于 CPython 3.7(以及之前的 CPython 版本)，限制为 20。但这在实现上是一个有点任意的特性； Python 语言定义不需要它，其他 Python 实现(至少 Jython)有不同的限制。见下文。

---

I know that in C the limit is 127

这不准确。 C 标准建议编译器需要能够处理嵌套深度至少为 127 的 block 的程序，但它不提供任何最大嵌套深度。它确实说:

Implementations should avoid imposing fixed translation limits whenever possible.

事实上，该标准实际上并没有规定实现必须能够处理任何 block 嵌套为 127 的程序；它所说的是它必须能够处理“至少一个”这样的程序。 (能够处理任何程序可能有点过分了，因为编译器可能会因程序文本的其他问题而卡住。)

Python 的规定更不明确。

当然，您可以通过连续尝试更深的嵌套级别来尝试找出限制。使用 bash 脚本(见下文)甚至使用 python 很容易生成此类程序。但这并没有告诉你任何关于抽象语言的信息。它告诉您的只是您正在使用的特定实现的限制。

您可能会发现同一语言的新版本、同一语言的不同实现，甚至不同主机上的同一语言存在不同的限制。

例如，我使用以下 bash 函数来生成示例 python 程序:

genpython () { 
    "${2:-python}" -c "$(
          for ((i=0; i<$1; ++i)); do
            printf "%*sfor i%d in range(1):\n" $i "" $i;
          done;
          printf '%*sprint("Nested %d worked!")\n' $1 "" $1;
        )"
}

它生成的程序看起来像(使用genpython 10):

for i0 in range(1):
 for i1 in range(1):
  for i2 in range(1):
   for i3 in range(1):
    for i4 in range(1):
     for i5 in range(1):
      for i6 in range(1):
       for i7 in range(1):
        for i8 in range(1):
         for i9 in range(1):
          print("Nested 10 worked!")

Python2 (CPython 2.7.15rc1) 和 Python3 (CPython 3.6.7) 均获得了 20 分的最高成绩:

$ genpython 20 python2
Nested 20 worked!
$ genpython 21 python2
SyntaxError: too many statically nested blocks

$ genpython 20 python3
Nested 20 worked!
$ genpython 21 python3
SyntaxError: too many statically nested blocks

但是，jython (2.7.1) 能够达到 99(因堆栈跟踪而不是简单的语法错误而失败):

$ genpython 99 jython
Nested 99 worked!
$ genpython 100 jython
java.lang.ArrayIndexOutOfBoundsException: Index 100 out of bounds for length 100
        at org.python.antlr.PythonTokenSource.push(PythonTokenSource.java:323)
        at org.python.antlr.PythonTokenSource.handleIndents(PythonTokenSource.java:288)
        at org.python.antlr.PythonTokenSource.insertImaginaryIndentDedentTokens(PythonTokenSource.java:222)
        at org.python.antlr.PythonTokenSource.nextToken(PythonTokenSource.java:143)
        at org.antlr.runtime.CommonTokenStream.fillBuffer(CommonTokenStream.java:119)
        at org.antlr.runtime.CommonTokenStream.LT(CommonTokenStream.java:238)
        at org.python.antlr.PythonParser.file_input(PythonParser.java:560)
        at org.python.antlr.BaseParser.parseModule(BaseParser.java:77)
        at org.python.core.CompileMode$3.dispatch(CompileMode.java:22)
        at org.python.core.ParserFacade.parse(ParserFacade.java:158)
        at org.python.core.ParserFacade.parse(ParserFacade.java:203)
        at org.python.core.Py.compile_flags(Py.java:2205)
        at org.python.util.PythonInterpreter.exec(PythonInterpreter.java:267)
        at org.python.util.jython.run(jython.java:394)
        at org.python.util.jython.main(jython.java:142)
java.lang.ArrayIndexOutOfBoundsException: java.lang.ArrayIndexOutOfBoundsException: Index 100 out of bounds for length 100

出于好奇，我用 C 语言尝试了同样的事情，使用了稍微修改过的脚本:

genc () { 
    { 
        echo '#include <stdio.h>'
        echo 'int main(void) {';
        for ((i=0; i<$1; ++i)); do
            printf "%*s for (int i%d=0; i%d==0; ++i%d) {\n" $i "" $i $i $i;
        done;
        printf '%*s puts("Nested %d worked!");\n' $1 "" $1;
        for ((i=$1; i-->0; 1)); do
            printf "%*s }\n" $i "";
        done;
        echo ' return 0;'
        echo '}'
    } | ${2:-gcc} "${@:3}" -std=c11 -x c - && ./a.out
}

这会产生，例如:

#include <stdio.h>
int main(void) {
 for (int i0=0; i0==0; ++i0) {
  for (int i1=0; i1==0; ++i1) {
   for (int i2=0; i2==0; ++i2) {
    puts("Nested 3 worked!");
   }
  }
 }
 return 0;
}

(请注意，C 中的嵌套深度比嵌套 for 语句的数量大 1，因为 int main() {...} 也计数。因此虽然上面说的是嵌套深度3，但实际上是深度4。)

使用 gcc (v8.3.0)，我的嵌套深度达到了 15000。我没有进一步尝试，因为编译时间和内存使用已经失去控制。但是 clang (v7.0.0) 更早地产生了错误，尽管有建议的解决方法:

$ genc 255 clang
Nested 255 worked!
$ genc 256 clang
<stdin>:258:291: fatal error: bracket nesting level exceeded maximum of 256
  ...for (int i255=0; i255==0; ++i255) {
                                       ^
<stdin>:258:291: note: use -fbracket-depth=N to increase maximum nesting level
1 error generated.

使用建议的命令行选项，我能够可靠地达到 3574 的嵌套深度(即 3573 个嵌套 for 循环)。但除此之外，事情开始不一致地失败。深度 3575 大约有三分之一的尝试失败。深度 3576 大约有一半的时间会失败。深度 3577 大约 80% 的时间都会失败。该失败可能是编译器错误(至少，这是编译器在长堆栈跟踪和更长的错误消息列表后打印出来的内容)。