From 69fd8b4871f3c027b78072af88bb8a62202bc7e7 Mon Sep 17 00:00:00 2001
From: facelessuser <faceless.shop@gmail.com>
Date: Mon, 17 Nov 2014 18:44:08 -0700
Subject: Issue #366 Recursion error in toc ext
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

This reworks the toc ordering to be done in a single pass with no
recursion.  Very long documents with lots of headers can actually
exceed Python’s max recursion limit.  By handling the toc ordering with
no recursion, large documents can no longer cause toc to fail with
recursion erros.
---
 markdown/extensions/toc.py | 95 +++++++++++++++++++++++-----------------------
 1 file changed, 47 insertions(+), 48 deletions(-)

diff --git a/markdown/extensions/toc.py b/markdown/extensions/toc.py
index d21ea96..f7fb675 100644
--- a/markdown/extensions/toc.py
+++ b/markdown/extensions/toc.py
@@ -27,60 +27,59 @@ def order_toc_list(toc_list):
     [{'level': 1}, {'level': 2}]
     =>
     [{'level': 1, 'children': [{'level': 2, 'children': []}]}]
-    
+
     A wrong list is also converted:
     [{'level': 2}, {'level': 1}]
     =>
     [{'level': 2, 'children': []}, {'level': 1, 'children': []}]
     """
-    
-    def build_correct(remaining_list, prev_elements=[{'level': 1000}]):
-        
-        if not remaining_list:
-            return [], []
-        
-        current = remaining_list.pop(0)
-        if not 'children' in current.keys():
-            current['children'] = []
-        
-        if not prev_elements:
-            # This happens for instance with [8, 1, 1], ie. when some
-            # header level is outside a scope. We treat it as a
-            # top-level
-            next_elements, children = build_correct(remaining_list, [current])
-            current['children'].append(children)
-            return [current] + next_elements, []
-        
-        prev_element = prev_elements.pop()
-        children = []
-        next_elements = []
-        # Is current part of the child list or next list?
-        if current['level'] > prev_element['level']:
-            #print "%d is a child of %d" % (current['level'], prev_element['level'])
-            prev_elements.append(prev_element)
-            prev_elements.append(current)
-            prev_element['children'].append(current)
-            next_elements2, children2 = build_correct(remaining_list, prev_elements)
-            children += children2
-            next_elements += next_elements2
-        else:
-            #print "%d is ancestor of %d" % (current['level'], prev_element['level'])
-            if not prev_elements:
-                #print "No previous elements, so appending to the next set"
-                next_elements.append(current)
-                prev_elements = [current]
-                next_elements2, children2 = build_correct(remaining_list, prev_elements)
-                current['children'].extend(children2)
+
+    ordered_list = []
+    if len(toc_list):
+        # Initialize everything by processing the first entry
+        last = toc_list.pop(0)
+        last['children'] = []
+        levels = [last['level']]
+        ordered_list.append(last)
+        parents = []
+
+        # Walk the rest nesting the entries properly
+        while toc_list:
+            t = toc_list.pop(0)
+            current_level = t['level']
+            t['children'] = []
+
+            # Reduce depth if current level < last item's level
+            if current_level < levels[-1]:
+                # Pop last level since we know we are less than it
+                levels.pop()
+
+                # Pop parents and levels we are less than or equal to
+                to_pop = 0
+                for p in reversed(parents):
+                    if current_level <= p['level']:
+                        to_pop += 1
+                    else:
+                        break
+                if to_pop:
+                    levels = levels[:-to_pop]
+                    parents = parents[:-to_pop]
+
+                # Note current level as last
+                levels.append(current_level)
+
+            # Level is the same, so append to the current parent (if available)
+            if current_level == levels[-1]:
+                (parents[-1]['children'] if parents else ordered_list).append(t)
+
+            # Current level is > last item's level,
+            # So make last item a parent and append current as child
             else:
-                #print "Previous elements, comparing to those first"
-                remaining_list.insert(0, current)
-                next_elements2, children2 = build_correct(remaining_list, prev_elements)
-                children.extend(children2)
-            next_elements += next_elements2
-        
-        return next_elements, children
-    
-    ordered_list, __ = build_correct(toc_list)
+                last['children'].append(t)
+                parents.append(last)
+                levels.append(current_level)
+            last = t
+
     return ordered_list
 
 
-- 
cgit v1.2.3