[Python-checkins] cpython (2.7): Issue #21523: Fix over-pessimistic computation of the stack effect of some

[antoine.pitrou]

http://hg.python.org/cpython/rev/49588a510ed4
changeset:   90798:49588a510ed4
branch:      2.7
parent:      90793:6fc09f30b514
user:        Antoine Pitrou <solipsis at pitrou.net>
date:        Fri May 23 11:46:03 2014 +0200
summary:
  Issue #21523: Fix over-pessimistic computation of the stack effect of some opcodes in the compiler.

This also fixes a quadratic compilation time issue noticeable when compiling
code with a large number of "and" and "or" operators.

files:
  Lib/test/test_compile.py |  43 ++++++++++++++++++++++++++-
  Misc/NEWS                |   5 +++
  Python/compile.c         |   8 +++-
  3 files changed, 52 insertions(+), 4 deletions(-)


diff --git a/Lib/test/test_compile.py b/Lib/test/test_compile.py
--- a/Lib/test/test_compile.py
+++ b/Lib/test/test_compile.py
@@ -1,3 +1,4 @@
+import math
 import unittest
 import sys
 import _ast
@@ -519,8 +520,46 @@
         self.assertRaises(TypeError, compile, ast, '<ast>', 'exec')
 
 
+class TestStackSize(unittest.TestCase):
+    # These tests check that the computed stack size for a code object
+    # stays within reasonable bounds (see issue #21523 for an example
+    # dysfunction).
+    N = 100
+
+    def check_stack_size(self, code):
+        # To assert that the alleged stack size is not O(N), we
+        # check that it is smaller than log(N).
+        if isinstance(code, str):
+            code = compile(code, "<foo>", "single")
+        max_size = math.ceil(math.log(len(code.co_code)))
+        self.assertLessEqual(code.co_stacksize, max_size)
+
+    def test_and(self):
+        self.check_stack_size("x and " * self.N + "x")
+
+    def test_or(self):
+        self.check_stack_size("x or " * self.N + "x")
+
+    def test_and_or(self):
+        self.check_stack_size("x and x or " * self.N + "x")
+
+    def test_chained_comparison(self):
+        self.check_stack_size("x < " * self.N + "x")
+
+    def test_if_else(self):
+        self.check_stack_size("x if x else " * self.N + "x")
+
+    def test_binop(self):
+        self.check_stack_size("x + " * self.N + "x")
+
+    def test_func_and(self):
+        code = "def f(x):\n"
+        code += "   x and x\n" * self.N
+        self.check_stack_size(code)
+
+
 def test_main():
-    test_support.run_unittest(TestSpecifics)
+    test_support.run_unittest(__name__)
 
 if __name__ == "__main__":
-    test_main()
+    unittest.main()
diff --git a/Misc/NEWS b/Misc/NEWS
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -10,6 +10,11 @@
 Core and Builtins
 -----------------
 
+- Issue #21523: Fix over-pessimistic computation of the stack effect of
+  some opcodes in the compiler.  This also fixes a quadratic compilation
+  time issue noticeable when compiling code with a large number of "and"
+  and "or" operators.
+
 Library
 -------
 
diff --git a/Python/compile.c b/Python/compile.c
--- a/Python/compile.c
+++ b/Python/compile.c
@@ -3483,12 +3483,16 @@
             target_depth = depth;
             if (instr->i_opcode == FOR_ITER) {
                 target_depth = depth-2;
-            } else if (instr->i_opcode == SETUP_FINALLY ||
-                       instr->i_opcode == SETUP_EXCEPT) {
+            }
+            else if (instr->i_opcode == SETUP_FINALLY ||
+                     instr->i_opcode == SETUP_EXCEPT) {
                 target_depth = depth+3;
                 if (target_depth > maxdepth)
                     maxdepth = target_depth;
             }
+            else if (instr->i_opcode == JUMP_IF_TRUE_OR_POP ||
+                     instr->i_opcode == JUMP_IF_FALSE_OR_POP)
+                depth = depth - 1;
             maxdepth = stackdepth_walk(c, instr->i_target,
                                        target_depth, maxdepth);
             if (instr->i_opcode == JUMP_ABSOLUTE ||

-- 
Repository URL: http://hg.python.org/cpython