I never intended to write a template system for Moya. Originally, I was going to offer a plugin system to use any template format you wish, with Jinja as the default. Jinja was certainly up to the task; it is blindingly fast, with a comfortable Django-like syntax. But it was never going to work exactly how I wanted it to, and since I don't have to be pragmatic on my hobby projects, I decided to re-invent the wheel. Because otherwise, how do we get better wheels?

The challenge of writing a template language, I discovered, was keeping the code manageable. If you want to make it both flexible and fast, it can quickly descend in to a mass of special cases and compromises. After a few aborted attempts, I worked out a system that was both flexible and reasonable fast. Not as fast as template systems that compile directly in to Python, but not half bad. Moya's template system is about 10-25% faster than Django templates with a similar feature set.

There are a two main steps in rendering a template. First the template needs to be tokenized, i.e. split up in a data structure of text / tags. This part is less interesting I think, because it can be done in advance and cached. The interesting part is the following step that turns that data structure in to HTML output.

This post will explain how Moya renders templates, by implementing a new template system that works the same way.

Let's render the following template:

<h1>Hobbit Index</h1>
<ul>
    {% for hobbit in hobbits %}
    <li{% if hobbit==active %} class="active"{% endif %}>
        {hobbit}
    </li>
    {% endfor %}
</ul>

This somewhat similar to a Django or Moya template. It generates HTML with unordered list of hobbits, one of which has the attribute class="active" on the <li>. You can see there is a loop and conditional in there.

The tokenizer scans the template and generates a hierarchical data structure of text, and tag tokens (markup between {% and %}). Tag tokens consist of a parameters extracted from the tag and children nodes (e.g the tokens between the {% for %} and {% endfor %}).

I'm going to omit the tokenize functionality as an exercise for the reader (sorry, I hate that too). We'll assume that we have implemented the tokenizer, and the end result is a data structure that looks like this:

[
    "<h1>Hobbit Index</h1>",
    "<ul>",
    ForNode(
        {"src": "hobbits", "dst": "hobbit"},
        [
            "<li",
            IfNode(
                {"test": "hobbit==active"},
                [
                    ' class="active"'
                ]
            ),
            ">",
            "{hobbit}",
            "</li>",
        ]
     ),
    "</ul>"
]

Essentially this is a list of strings or nodes, where a node can contain further nested strings and other nodes. A node is defined as a class instance that handles the functionality of a given tag, i.e. IfNode for the {% if %} tag and ForNode for the {% for %} tag.

Nodes have the following trivial base class, which stores the parameters and the list of children:

class Node(object):
    def __init__(self, params, children):
        self.params = params
        self.children = children

Nodes also have an additional method, render, which takes a mapping of the data we want to render (the context). This method should be a generator, which may yield one of two things; either strings containing output text or an iterator that yields further nodes. Let's look at the IfNode first:

class IfNode(Node):
    def render(self, context):
        test = eval(self.params['test'], globals(), context)
        if test:
            yield iter(self.children)

The first thing the render method does is to get the test parameter and evaluate it with the data in the context. If the result of that test is truthy, then the render method yields an iterator of it's children. Essentially all this node object does is render its children (i.e. the template code between {% if %} and {% endif %}) if the test passes.

The ForNode is similar, here's the implementation:

class ForNode(Node):

    def render(self, context):
        src = eval(self.params['src'], globals(), context)
        dst = self.params['dst']
        for obj in src:
            context[dst] = obj
            yield iter(self.children)

The ForNode render method iterates over each item in a sequence, and assigns the value to an intermediate variable. It also yields to its children each pass through the loop. So the code inside the {% for %} tag is rendered once per item in the sequence.

Because we are using generators to handle the state for control structures, we can keep the main render loop free from such logic. This makes the code that renders the template trivially easy to follow:

def render(template, **context):
    output = []
    stack = [iter(template)]

    while stack:
        node = stack.pop()
        if isinstance(node, basestring):
            output.append(node.format(**context))
        elif isinstance(node, Node):
            stack.append(node.render(context))
        else:
            new_node = next(node, None)
            if new_node is not None:
                stack.append(node)
                stack.append(new_node)
    return "".join(output)

The render loop manages a stack of iterators, initialized to the template data structure. Each pass through the loop it pops an item off the stack. If that item is a string, it performs a string format operation with the context data. If the item is a Node, it calls the render method and pushes the generator back on to the stack. When the stack item is an iterator (such as a generator created by Node.render) it gets one value from the iterator and pushes it back on to the stack, or discards it if is empty.

In essence, the inner loop is running the generators and collecting the output. A more naive approach might have the render methods also rendering their children and returning the result as a string. Using generators frees the nodes from having to build strings. Generators also makes error reporting much easier, because exceptions won't be obscured by deeply nested render methods. Consider a node throwing an exception inside a for loop; if ForNode.render was responsible for rendering its children, it would also have to trap and report such errors. The generator system makes error reporting simpler, and confines it to one place.

There is a very similar loop at the heart of Moya's template system. I suspect the main reason that Moya templates are moderately faster than Django's is due to this lean inner loop. See this GutHub gist for the code from this post. You may also find Moya's template implementation interesting.