What is the maximum depth level of nested For loops in Python 3? [duplicate]

For CPython 3.7 (and previous CPython versions), the limit is 20. But that's a somewhat arbitrary feature of the implementation; it is not required by the Python language definition and other Python implementations (at least Jython) have different limits. See below.

I know that in C the limit is 127

That's not precise. The C standard suggests that a compiler needs to be able to handle a program with blocks nested at least to depth 127, but it doesn't provide any maximum nesting depth. It does say that:

Implementations should avoid imposing fixed translation limits whenever possible.

In fact, the standard doesn't actually say that an implementation must be able to handle any program with block nesting of 127; what it says, is that it must be able to handle "at least one" such program. (Being able to handle any program would be a bit much to ask, because the compiler might choke on some other issue with the program text.)

Python is even less clearly specified.

Of course, you can attempt to figure out the limit by just trying successively deeper nesting levels. It's easy to generate such programs with a bash script (see below) or even with python. But that doesn't tell you anything about the language in abstract. All it tells you is what the limits are in the specific implementation you happen to be using.

You will probably find different limits in a new version of the same language, a different implementation of the same language, or even the same language on a different host.

For example, I used the following bash-function to generate sample python programs:

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

which produces programs which look like (using 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!")

Both Python2 (CPython 2.7.15rc1) and Python3 (CPython 3.6.7) topped out at 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

However, jython (2.7.1) was able to go up to 99 (failing with a stack trace rather than a simple syntax error):

$ 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

Out of curiosity, I tried the same thing with C, using a slightly modified script:

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
}

This produces, for example:

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

(Note that the nesting depth in C is one greater than the number of nested for statements because int main() {...} counts, too. So although the above says its nesting depth 3, it's really depth 4.)

With gcc (v8.3.0), I got up to a nesting depth of 15000. I didn't try any further because the compile times and memory usage were getting out of control. But clang (v7.0.0) produced an error much earlier, albeit with a suggested work-around:

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

Using the suggested command-line option, I was able to reliably get up to a nesting depth of 3574 (i.e. 3573 nested for loops). But higher than that, and things started failing inconsistently. Depth 3575 fails about one in three tries. Depth 3576 fails about half the time. Depth 3577 fails about 80% of the time. The failure is presumably a compiler bug (at least, that's what the compiler prints out after a long stack trace and an even longer list of error messages).

Recommended topics

Hot tags