Issue #5765: Apply a hard recursion limit in the compiler

Previously, excessive nesting in expressions would blow the
stack and segfault the interpreter. Now, a hard limit based
on the configured recursion limit and a hardcoded scaling
factor is applied.

7 files changed, 106 insertions, 42 deletions

diff --git a/Include/symtable.h b/Include/symtable.h
index 82f6269..6ed3a2b 100644
--- a/Include/symtable.h
+++ b/Include/symtable.h
@@ -30,6 +30,8 @@ struct symtable {
     PyObject *st_private;           /* name of current class or NULL */
     PyFutureFeatures *st_future;    /* module's future features that affect
                                        the symbol table */
+    int recursion_depth;            /* current recursion depth */
+    int recursion_limit;            /* recursion limit */
 };
 
 typedef struct _symtable_entry {
diff --git a/Lib/test/crashers/compiler_recursion.py b/Lib/test/crashers/compiler_recursion.py
deleted file mode 100644
index 31f28a9..0000000
--- a/Lib/test/crashers/compiler_recursion.py
+++ /dev/null
@@ -1,13 +0,0 @@
-"""
-The compiler (>= 2.5) recurses happily until it blows the stack.
-
-Recorded on the tracker as http://bugs.python.org/issue11383
-"""
-
-# The variant below blows up in compiler_call, but there are assorted
-# other variations that blow up in other functions
-# e.g. '1*'*10**5+'1' will die in compiler_visit_expr
-
-# The exact limit to destroy the stack will vary by platform
-# but 10M should do the trick even with huge stack allocations
-compile('()'*10**7, '?', 'exec')
diff --git a/Lib/test/test_compile.py b/Lib/test/test_compile.py
index 72342f8..1071f4a 100644
--- a/Lib/test/test_compile.py
+++ b/Lib/test/test_compile.py
@@ -474,6 +474,33 @@ if 1:
         self.assertInvalidSingle('f()\nxy # blah\nblah()')
         self.assertInvalidSingle('x = 5 # comment\nx = 6\n')
 
+    @support.cpython_only
+    def test_compiler_recursion_limit(self):
+        # Expected limit is sys.getrecursionlimit() * the scaling factor
+        # in symtable.c (currently 3)
+        # We expect to fail *at* that limit, because we use up some of
+        # the stack depth limit in the test suite code
+        # So we check the expected limit and 75% of that
+        # XXX (ncoghlan): duplicating the scaling factor here is a little
+        # ugly. Perhaps it should be exposed somewhere...
+        fail_depth = sys.getrecursionlimit() * 3
+        success_depth = int(fail_depth * 0.75)
+
+        def check_limit(prefix, repeated):
+            expect_ok = prefix + repeated * success_depth
+            self.compile_single(expect_ok)
+            broken = prefix + repeated * fail_depth
+            details = "Compiling ({!r} + {!r} * {})".format(
+                         prefix, repeated, fail_depth)
+            with self.assertRaises(RuntimeError, msg=details):
+                self.compile_single(broken)
+
+        check_limit("a", "()")
+        check_limit("a", ".b")
+        check_limit("a", "[0]")
+        check_limit("a", "*a")
+
+
 def test_main():
     support.run_unittest(TestSpecifics)
 
diff --git a/Misc/ACKS b/Misc/ACKS
index 81ed27c..abf4a5d 100644
--- a/Misc/ACKS
+++ b/Misc/ACKS
@@ -431,6 +431,7 @@ Hans de Graaff
 Nathaniel Gray
 Eddy De Greef
 Grant Griffin
+Andrea Griffini
 Duncan Grisby
 Fabian Groffen
 Eric Groo
diff --git a/Misc/NEWS b/Misc/NEWS
index 89124da..cfa3bbe 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -12,6 +12,9 @@ What's New in Python 3.3.1?
 Core and Builtins
 -----------------
 
+- Issue #5765: Apply a hard recursion limit in the compiler instead of
+  blowing the stack and segfaulting.
+
 - Issue #16402: When slicing a range, fix shadowing of exceptions from
   __index__.
 
diff --git a/Python/compile.c b/Python/compile.c
index ff55220..5016f99 100644
--- a/Python/compile.c
+++ b/Python/compile.c
@@ -141,6 +141,11 @@ struct compiler_unit {
 The u pointer points to the current compilation unit, while units
 for enclosing blocks are stored in c_stack.     The u and c_stack are
 managed by compiler_enter_scope() and compiler_exit_scope().
+
+Note that we don't track recursion levels during compilation - the
+task of detecting and rejecting excessive levels of nesting is
+handled by the symbol analysis pass.
+
 */
 
 struct compiler {
diff --git a/Python/symtable.c b/Python/symtable.c
index ff6e8b7..9dde908 100644
--- a/Python/symtable.c
+++ b/Python/symtable.c
@@ -220,17 +220,40 @@ symtable_new(void)
     return NULL;
 }
 
+/* When compiling the use of C stack is probably going to be a lot
+   lighter than when executing Python code but still can overflow
+   and causing a Python crash if not checked (e.g. eval("()"*300000)).
+   Using the current recursion limit for the compiler seems too
+   restrictive (it caused at least one test to fail) so a factor is
+   used to allow deeper recursion when compiling an expression.
+
+   Using a scaling factor means this should automatically adjust when
+   the recursion limit is adjusted for small or large C stack allocations.
+*/
+#define COMPILER_STACK_FRAME_SCALE 3
+
 struct symtable *
 PySymtable_Build(mod_ty mod, const char *filename, PyFutureFeatures *future)
 {
     struct symtable *st = symtable_new();
     asdl_seq *seq;
     int i;
+    PyThreadState *tstate;
 
     if (st == NULL)
         return st;
     st->st_filename = filename;
     st->st_future = future;
+
+    /* Setup recursion depth check counters */
+    tstate = PyThreadState_GET();
+    if (!tstate) {
+        PySymtable_Free(st);
+        return NULL;
+    }
+    st->recursion_depth = tstate->recursion_depth * COMPILER_STACK_FRAME_SCALE;
+    st->recursion_limit = Py_GetRecursionLimit() * COMPILER_STACK_FRAME_SCALE;
+
     /* Make the initial symbol information gathering pass */
     if (!GET_IDENTIFIER(top) ||
         !symtable_enter_block(st, top, ModuleBlock, (void *)mod, 0, 0)) {
@@ -1013,11 +1036,17 @@ error:
 
    VISIT_SEQ_TAIL permits the start of an ASDL sequence to be skipped, which is
    useful if the first node in the sequence requires special treatment.
+
+   VISIT_QUIT macro returns the specified value exiting from the function but
+   first adjusts current recursion counter depth.
 */
 
+#define VISIT_QUIT(ST, X) \
+    return --(ST)->recursion_depth,(X)
+
 #define VISIT(ST, TYPE, V) \
     if (!symtable_visit_ ## TYPE((ST), (V))) \
-        return 0;
+        VISIT_QUIT((ST), 0);
 
 #define VISIT_SEQ(ST, TYPE, SEQ) { \
     int i; \
@@ -1025,7 +1054,7 @@ error:
     for (i = 0; i < asdl_seq_LEN(seq); i++) { \
         TYPE ## _ty elt = (TYPE ## _ty)asdl_seq_GET(seq, i); \
         if (!symtable_visit_ ## TYPE((ST), elt)) \
-            return 0; \
+            VISIT_QUIT((ST), 0);                 \
     } \
 }
 
@@ -1035,7 +1064,7 @@ error:
     for (i = (START); i < asdl_seq_LEN(seq); i++) { \
         TYPE ## _ty elt = (TYPE ## _ty)asdl_seq_GET(seq, i); \
         if (!symtable_visit_ ## TYPE((ST), elt)) \
-            return 0; \
+            VISIT_QUIT((ST), 0);                 \
     } \
 }
 
@@ -1046,7 +1075,7 @@ error:
         expr_ty elt = (expr_ty)asdl_seq_GET(seq, i); \
         if (!elt) continue; /* can be NULL */ \
         if (!symtable_visit_expr((ST), elt)) \
-            return 0; \
+            VISIT_QUIT((ST), 0);             \
     } \
 }
 
@@ -1071,32 +1100,37 @@ symtable_new_tmpname(struct symtable *st)
 static int
 symtable_visit_stmt(struct symtable *st, stmt_ty s)
 {
+    if (++st->recursion_depth > st->recursion_limit) {
+        PyErr_SetString(PyExc_RuntimeError,
+                        "maximum recursion depth exceeded during compilation");
+        VISIT_QUIT(st, 0);
+    }
     switch (s->kind) {
     case FunctionDef_kind:
         if (!symtable_add_def(st, s->v.FunctionDef.name, DEF_LOCAL))
-            return 0;
+            VISIT_QUIT(st, 0);
         if (s->v.FunctionDef.args->defaults)
             VISIT_SEQ(st, expr, s->v.FunctionDef.args->defaults);
         if (s->v.FunctionDef.args->kw_defaults)
             VISIT_KWONLYDEFAULTS(st,
                                s->v.FunctionDef.args->kw_defaults);
         if (!symtable_visit_annotations(st, s))
-            return 0;
+            VISIT_QUIT(st, 0);
         if (s->v.FunctionDef.decorator_list)
             VISIT_SEQ(st, expr, s->v.FunctionDef.decorator_list);
         if (!symtable_enter_block(st, s->v.FunctionDef.name,
                                   FunctionBlock, (void *)s, s->lineno,
                                   s->col_offset))
-            return 0;
+            VISIT_QUIT(st, 0);
         VISIT(st, arguments, s->v.FunctionDef.args);
         VISIT_SEQ(st, stmt, s->v.FunctionDef.body);
         if (!symtable_exit_block(st, s))
-            return 0;
+            VISIT_QUIT(st, 0);
         break;
     case ClassDef_kind: {
         PyObject *tmp;
         if (!symtable_add_def(st, s->v.ClassDef.name, DEF_LOCAL))
-            return 0;
+            VISIT_QUIT(st, 0);
         VISIT_SEQ(st, expr, s->v.ClassDef.bases);
         VISIT_SEQ(st, keyword, s->v.ClassDef.keywords);
         if (s->v.ClassDef.starargs)
@@ -1107,20 +1141,20 @@ symtable_visit_stmt(struct symtable *st, stmt_ty s)
             VISIT_SEQ(st, expr, s->v.ClassDef.decorator_list);
         if (!symtable_enter_block(st, s->v.ClassDef.name, ClassBlock,
                                   (void *)s, s->lineno, s->col_offset))
-            return 0;
+            VISIT_QUIT(st, 0);
         if (!GET_IDENTIFIER(__class__) ||
             !symtable_add_def(st, __class__, DEF_LOCAL) ||
             !GET_IDENTIFIER(__locals__) ||
             !symtable_add_def(st, __locals__, DEF_PARAM)) {
             symtable_exit_block(st, s);
-            return 0;
+            VISIT_QUIT(st, 0);
         }
         tmp = st->st_private;
         st->st_private = s->v.ClassDef.name;
         VISIT_SEQ(st, stmt, s->v.ClassDef.body);
         st->st_private = tmp;
         if (!symtable_exit_block(st, s))
-            return 0;
+            VISIT_QUIT(st, 0);
         break;
     }
     case Return_kind:
@@ -1204,7 +1238,7 @@ symtable_visit_stmt(struct symtable *st, stmt_ty s)
             identifier name = (identifier)asdl_seq_GET(seq, i);
             long cur = symtable_lookup(st, name);
             if (cur < 0)
-                return 0;
+                VISIT_QUIT(st, 0);
             if (cur & (DEF_LOCAL | USE)) {
                 char buf[256];
                 char *c_name = _PyUnicode_AsString(name);
@@ -1219,10 +1253,10 @@ symtable_visit_stmt(struct symtable *st, stmt_ty s)
                                   GLOBAL_AFTER_USE,
                                   c_name);
                 if (!symtable_warn(st, buf, s->lineno))
-                    return 0;
+                    VISIT_QUIT(st, 0);
             }
             if (!symtable_add_def(st, name, DEF_GLOBAL))
-                return 0;
+                VISIT_QUIT(st, 0);
         }
         break;
     }
@@ -1233,7 +1267,7 @@ symtable_visit_stmt(struct symtable *st, stmt_ty s)
             identifier name = (identifier)asdl_seq_GET(seq, i);
             long cur = symtable_lookup(st, name);
             if (cur < 0)
-                return 0;
+                VISIT_QUIT(st, 0);
             if (cur & (DEF_LOCAL | USE)) {
                 char buf[256];
                 char *c_name = _PyUnicode_AsString(name);
@@ -1248,10 +1282,10 @@ symtable_visit_stmt(struct symtable *st, stmt_ty s)
                                   NONLOCAL_AFTER_USE,
                                   c_name);
                 if (!symtable_warn(st, buf, s->lineno))
-                    return 0;
+                    VISIT_QUIT(st, 0);
             }
             if (!symtable_add_def(st, name, DEF_NONLOCAL))
-                return 0;
+                VISIT_QUIT(st, 0);
         }
         break;
     }
@@ -1268,12 +1302,17 @@ symtable_visit_stmt(struct symtable *st, stmt_ty s)
         VISIT_SEQ(st, stmt, s->v.With.body);
         break;
     }
-    return 1;
+    VISIT_QUIT(st, 1);
 }
 
 static int
 symtable_visit_expr(struct symtable *st, expr_ty e)
 {
+    if (++st->recursion_depth > st->recursion_limit) {
+        PyErr_SetString(PyExc_RuntimeError,
+                        "maximum recursion depth exceeded during compilation");
+        VISIT_QUIT(st, 0);
+    }
     switch (e->kind) {
     case BoolOp_kind:
         VISIT_SEQ(st, expr, e->v.BoolOp.values);
@@ -1287,7 +1326,7 @@ symtable_visit_expr(struct symtable *st, expr_ty e)
         break;
     case Lambda_kind: {
         if (!GET_IDENTIFIER(lambda))
-            return 0;
+            VISIT_QUIT(st, 0);
         if (e->v.Lambda.args->defaults)
             VISIT_SEQ(st, expr, e->v.Lambda.args->defaults);
         if (e->v.Lambda.args->kw_defaults)
@@ -1296,11 +1335,11 @@ symtable_visit_expr(struct symtable *st, expr_ty e)
         if (!symtable_enter_block(st, lambda,
                                   FunctionBlock, (void *)e, e->lineno,
                                   e->col_offset))
-            return 0;
+            VISIT_QUIT(st, 0);
         VISIT(st, arguments, e->v.Lambda.args);
         VISIT(st, expr, e->v.Lambda.body);
         if (!symtable_exit_block(st, (void *)e))
-            return 0;
+            VISIT_QUIT(st, 0);
         break;
     }
     case IfExp_kind:
@@ -1317,19 +1356,19 @@ symtable_visit_expr(struct symtable *st, expr_ty e)
         break;
     case GeneratorExp_kind:
         if (!symtable_visit_genexp(st, e))
-            return 0;
+            VISIT_QUIT(st, 0);
         break;
     case ListComp_kind:
         if (!symtable_visit_listcomp(st, e))
-            return 0;
+            VISIT_QUIT(st, 0);
         break;
     case SetComp_kind:
         if (!symtable_visit_setcomp(st, e))
-            return 0;
+            VISIT_QUIT(st, 0);
         break;
     case DictComp_kind:
         if (!symtable_visit_dictcomp(st, e))
-            return 0;
+            VISIT_QUIT(st, 0);
         break;
     case Yield_kind:
     case YieldFrom_kind: {
@@ -1373,14 +1412,14 @@ symtable_visit_expr(struct symtable *st, expr_ty e)
     case Name_kind:
         if (!symtable_add_def(st, e->v.Name.id,
                               e->v.Name.ctx == Load ? USE : DEF_LOCAL))
-            return 0;
+            VISIT_QUIT(st, 0);
         /* Special-case super: it counts as a use of __class__ */
         if (e->v.Name.ctx == Load &&
             st->st_cur->ste_type == FunctionBlock &&
             !PyUnicode_CompareWithASCIIString(e->v.Name.id, "super")) {
             if (!GET_IDENTIFIER(__class__) ||
                 !symtable_add_def(st, __class__, USE))
-                return 0;
+                VISIT_QUIT(st, 0);
         }
         break;
     /* child nodes of List and Tuple will have expr_context set */
@@ -1391,7 +1430,7 @@ symtable_visit_expr(struct symtable *st, expr_ty e)
         VISIT_SEQ(st, expr, e->v.Tuple.elts);
         break;
     }
-    return 1;
+    VISIT_QUIT(st, 1);
 }
 
 static int