This was probably just about the gnarliest little problem I've ever wrocked my brains over in a long time. I was using the Treebeard library for a materialized path tree, and the problem came down to how to render it. The obvious solution was lists of lists, but... how?

I'm not going to explain Treebeard trees here. That's a different topic. Suffice it to say that MP_trees maintain the full path to every node in the tree within each node, so looking up parents and roots is a cheap operation. Insertions are slightly expensive, but not tragically so.

Okay, if you understand trees and why you need them, and you understand Django, then you understand why the two don't go great together: Django's templating mechanism has no appreciation at all for the complexities of recursion, and trees are nothing but recursive structures. You start with a node drawing loop: either you're rendering a leaf node, in which case there is no more processing to be done, or you're rendering a branch node, whereby you must recursively call node drawing loop with the list of nodes under the branch. Django templates don't do this sort of thinking at all.

Ah, but there are ways around any problem. Especially in Python. The solution here is twofold: create a recursive function that would generate the branches and leaf lists of the tree, and then coerce the templating mechanism into calling the recursive function. The solution is evil, but worth a look for all that. It takes three templates: a container for the page, a simple one for a leaf, and the one that shows the branch and then recurses down into it. Here's the code:

def index(request):
    def index_maker():
        rootnodes = Tag.get_root_nodes()
        def _index(nodes):
            for node in nodes:
                if node.is_leaf():
                    yield loader.render_to_string('p_leaf.html',
                                                  {'node': node.name})
                    continue
                yield loader.render_to_string('p_branch.html',
                                              {'node': node.name,
                                               'content': _index(node.get_children())})
        return _index(rootnodes)

    return render_to_response('index.html',
                              {'content': index_maker()})

I've made extensive use of a generator here: each time you dereference the 'content' object is the response dictionary, you get a generator, which Django mistakes for an iterator (they have the same interface, so that's understandable).

Here's the content of p_leaf.html (yeah, I used 'p' for partial; I'm not a rails partisan, but I can understand this logic):

<li>{{ node }}</li>

Yeah, that's not very exciting. Here's p_branch.html:

<li>{{ node }}<ul>{% for c in content %}{{ c }}{% endfor %}</ul></li>

And the money part of index.html:

<ul>{% for c in content %}{{ c }}{% endfor %}</ul>

Thus this rendering becomes choreography between the iterator handler in the template engine, and the generator in the index() function. Each call to dereference the dictionary key "content" causes the template engine to dereference another, deeper frame of the _index() generator, and each time that's called the template engine's loader.render_to_string() may be called upon to generate a template that calls on yet a deeper frame, until the branch is exhausted, the recursion stack unwinds, and a generator frame with more content inside it's content loop proceeds, until the entire tree is exhausted.

My solution is highly entertaining, and has the nice side effect of delaying all of the processing until it's time to hand the contents over to the renderer. This doesn't eliminate any bottlenecks but it does mean that the existing bottlenecks exist for as brief a lifespan as possible.

This was fun. Whee!