Repository: Python-Markdown/markdown (python)

Issue:
Parsing >>>>>>… takes quadratic time and eventually crashes with recursion error
```pycon
>>> import markdown, timeit
>>> num, dur = timeit.Timer(lambda: markdown.markdown(">" * 100)).autorange(); dur / num
0.004344235559692607
>>> num, dur = timeit.Timer(lambda: markdown.markdown(">" * 200)).autorange(); dur / num
0.016907797248859425
>>> num, dur = timeit.Timer(lambda: markdown.markdown(">" * 300)).autorange(); dur / num
0.05682634799741208
>>> markdown.markdown(">" * 331)
…
RecursionError: maximum recursion depth exceeded while calling a Python object
```

Same results in 3.0.1 and master.

Pull request description:
Limit depth of blockquotes using Python's recursion limit.
If the Python stack comes within 100 frames of the recursion limit,
then the nesting limit of blockquotes is met. Any remaining text,
including angle brackets, are simply wrapped in a paragraph. To
increasing the nesting depth, increase Python's recursion limit.
However, be aware that each level of recursion will likely result in
multiple frames being added to the Python stack. Therefore, the
recursion depth and nesting depth are not one-to-one.

Performance is an concern here. However, the current solution seems like
a reasonable compromise. It doesn't slow things down too much, but also
avoids Markdown input resulting in an error. This is mostly only a concern
with contrived input anyway. For the average Markdown document, this will
likely never be an issue.

Fixes #799.

Patch:
diff --git a/docs/change_log/release-3.3.md b/docs/change_log/release-3.3.md
index 752564d..339c98c 100644
--- a/docs/change_log/release-3.3.md
+++ b/docs/change_log/release-3.3.md
@@ -53,6 +53,7 @@ The following new features have been included in the 3.3 release:
 
 The following bug fixes are included in the 3.3 release:
 
+* Avoid a `RecursionError` from deeply nested blockquotes (#799).
 * Fix issues with complex emphasis (#979).
 * Limitations of `attr_list` extension are Documented (#965).
 
diff --git a/markdown/blockprocessors.py b/markdown/blockprocessors.py
index 60baca1..88ebb62 100644
--- a/markdown/blockprocessors.py
+++ b/markdown/blockprocessors.py
@@ -276,7 +276,7 @@ class BlockQuoteProcessor(BlockProcessor):
     RE = re.compile(r'(^|\n)[ ]{0,3}>[ ]?(.*)')
 
     def test(self, parent, block):
-        return bool(self.RE.search(block))
+        return bool(self.RE.search(block)) and not util.nearing_recursion_limit()
 
     def run(self, parent, blocks):
         block = blocks.pop(0)
diff --git a/markdown/util.py b/markdown/util.py
index a8db7bd..a49486b 100644
--- a/markdown/util.py
+++ b/markdown/util.py
@@ -26,6 +26,7 @@ from functools import wraps
 import warnings
 import xml.etree.ElementTree
 from .pep562 import Pep562
+from itertools import count
 
 try:
     from importlib import metadata
@@ -156,6 +157,23 @@ def code_escape(text):
     return text
 
 
+def _get_stack_depth(size=2):
+    """Get stack size for caller's frame.
+    See https://stackoverflow.com/a/47956089/866026
+    """
+    frame = sys._getframe(size)
+
+    for size in count(size):
+        frame = frame.f_back
+        if not frame:
+            return size
+
+
+def nearing_recursion_limit():
+    """Return true if current stack depth is withing 100 of maximum limit."""
+    return sys.getrecursionlimit() - _get_stack_depth() < 100
+
+
 """
 MISC AUXILIARY CLASSES
 =============================================================================


Test patch:
diff --git a/markdown/test_tools.py b/markdown/test_tools.py
index be7bbf1..fb407bb 100644
--- a/markdown/test_tools.py
+++ b/markdown/test_tools.py
@@ -20,9 +20,10 @@ License: BSD (see LICENSE.md for details).
 """
 
 import os
+import sys
 import unittest
 import textwrap
-from . import markdown
+from . import markdown, util
 
 try:
     import tidylib
@@ -73,6 +74,32 @@ class TestCase(unittest.TestCase):
         return textwrap.dedent(text).strip()
 
 
+class recursionlimit:
+    """
+    A context manager which temporarily modifies the Python recursion limit.
+
+    The testing framework, coverage, etc. may add an arbitrary number of levels to the depth. To maintain consistency
+    in the tests, the current stack depth is determined when called, then added to the provided limit.
+
+    Example usage:
+
+        with recursionlimit(20):
+            # test code here
+
+    See https://stackoverflow.com/a/50120316/866026
+    """
+
+    def __init__(self, limit):
+        self.limit = util._get_stack_depth() + limit
+        self.old_limit = sys.getrecursionlimit()
+
+    def __enter__(self):
+        sys.setrecursionlimit(self.limit)
+
+    def __exit__(self, type, value, tb):
+        sys.setrecursionlimit(self.old_limit)
+
+
 #########################
 # Legacy Test Framework #
 #########################
diff --git a/tests/test_syntax/blocks/test_blockquotes.py b/tests/test_syntax/blocks/test_blockquotes.py
new file mode 100644
index 0000000..42eea33
--- /dev/null
+++ b/tests/test_syntax/blocks/test_blockquotes.py
@@ -0,0 +1,51 @@
+"""
+Python Markdown
+
+A Python implementation of John Gruber's Markdown.
+
+Documentation: https://python-markdown.github.io/
+GitHub: https://github.com/Python-Markdown/markdown/
+PyPI: https://pypi.org/project/Markdown/
+
+Started by Manfred Stienstra (http://www.dwerg.net/).
+Maintained for a few years by Yuri Takhteyev (http://www.freewisdom.org).
+Currently maintained by Waylan Limberg (https://github.com/waylan),
+Dmitry Shachnev (https://github.com/mitya57) and Isaac Muse (https://github.com/facelessuser).
+
+Copyright 2007-2020 The Python Markdown Project (v. 1.7 and later)
+Copyright 2004, 2005, 2006 Yuri Takhteyev (v. 0.2-1.6b)
+Copyright 2004 Manfred Stienstra (the original version)
+
+License: BSD (see LICENSE.md for details).
+"""
+
+from markdown.test_tools import TestCase, recursionlimit
+
+
+class TestBlockquoteBlocks(TestCase):
+
+    # TODO: Move legacy tests here
+
+    def test_nesting_limit(self):
+        # Test that the nesting limit is within 100 levels of recursion limit. Future code changes could cause the
+        # recursion limit to need adjusted here. We need to acocunt for all of Markdown's internal calls. Finally, we
+        # need to account for the 100 level cushion which we are testing.
+        with recursionlimit(120):
+            self.assertMarkdownRenders(
+                '>>>>>>>>>>',
+                self.dedent(
+                    """
+                    <blockquote>
+                    <blockquote>
+                    <blockquote>
+                    <blockquote>
+                    <blockquote>
+                    <p>&gt;&gt;&gt;&gt;&gt;</p>
+                    </blockquote>
+                    </blockquote>
+                    </blockquote>
+                    </blockquote>
+                    </blockquote>
+                    """
+                )
+            )