Issue #366 Recursion error in toc ext

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.

1 files 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