Changeset 3054 for trac/trunk/wiki-macros/TracNav.py

Timestamp:

11/09/05 18:02:56 (8 years ago)

Author:

moschny

Message:

Rewrite the TOC structure parser, using a recursive algorithm instead
of an explicit stack.

The new method accepts table-of-contents with varying amounts of
indentation characters (unlike the current version of Trac itself,
where deeper levels must be indented by exactly two white spaces).

Furthermore, it "repairs" malformed TOCs by inserting dummy
nodes. Trac does this, too, but may insert more dummy nodes than our
method (because of the fixed amount of whitespace expected per level).

In any case, there shouldn't be any differences between Trac's and our
interpretation of the structure for most "well-formed" TOCs.

File:

• trac/trunk/wiki-macros/TracNav.py (modified) (1 diff)

trac/trunk/wiki-macros/TracNav.py

@@ -114 +114 @@
 
 
+def getTocEntryAndNextIndent(g):
+    indent, link, label = g.next()
+    yield indent
+
+    ready = False
+    while not ready:
+        yield link, label
+        try:
+            indent, link, label = g.next()
+        except StopIteration:
+            indent, ready = -1, True
+        yield indent
+
+
+def _parseToc(g, nextIndent, level = 0):
+    list = []
+    if nextIndent > level:
+        subList, nextIndent = _parseToc(g, nextIndent, level + 1)
+        if nextIndent < level:
+            # level is empty
+            return subList, nextIndent
+        else:
+            # broken indentation structure
+            list.append((None, None, subList))
+    while 1:
+        if nextIndent == level:
+            (link, label), nextIndent = g.next(), g.next()
+            if nextIndent > level:
+                subList, nextIndent = _parseToc(g, nextIndent, level + 1)
+                list.append((link, label, subList))
+            else:
+                list.append((link, label, None))
+        else:
+            assert nextIndent < level
+            return list, nextIndent
+
+
 def parseToc(tocText):
-    stack = []
-    for indent, link, label in getTocEntry(tocText):
-
-        if len(stack) == 0:
-            stack.append((indent, []))
-
-        (lastIndent, list) = stack[len(stack) - 1]
-
-        if indent > lastIndent:
-            stack.append((indent, [(link, label, None)]))
-        elif indent == lastIndent:
-            list.append((link, label, None))
-        else:
-            while indent < lastIndent:
-                (_, list) = stack.pop()
-                (lastIndent, topList) = stack[len(stack) - 1]
-                (topLink, topLabel, _) = topList[len(topList) - 1]
-                topList[len(topList) - 1] = (topLink, topLabel, list)
-
-            (lastIndent, list) = stack[len(stack) - 1]
-            list.append((link, label, None))
-                
-    while len(stack) > 1:
-        (_, list) = stack.pop()
-        (_, topList) = stack[len(stack) - 1]
-        (topLink, topLabel, _) = topList[len(topList) - 1]
-        topList[len(topList) - 1] = (topLink, topLabel, list)
-
-    (_, list) = stack.pop()
+    g = getTocEntryAndNextIndent(getTocEntry(tocText))
+    list, _ = _parseToc(g, g.next())
     return list
-
+   
 
 def execute(hdf, args, env):