Writing an reconciliation algorithm for markup fragments

In my previous post about isomorphic javascript, I explored a way of rendering a mustache template multiple times and updating a portion of the dom (document object model). This exposed a potential weakness in the technique, entire portions of the dom could get replaced when templates were -re-rendered and the content simply replaced in the dom.

What I wanted to explore was a technique for comparing two pieces of markup (or their document node equivalents) and applying the minimum set of changes to make the dom equivalent to the rendered markup. I later found out this is exactly how Facebook’s React works in a process called dom reconciliation.

The following examples show how such an algorithm could work. It assumes that most changes will be simple and works backwards to more complex multiple dom manipulation scenarios. Click on the tabs above each example to show or hide the html markup, script and screen output.

Example 1 – Test Flights Table

JS BinThis example takes an array of test flight data and renders it via the template as an html table. When you press update, the table is re-rendered using the existing template and the table is replaced in the dom with the new one. If you look closely in fact all that has changed is that the altitude in the second row of the table has changed.

We need a way to figure out how to detect the small difference between the two pieces of markup, and only apply those changes to the dom. With this technique, we wouldn’t have to reapply event handlers, plugins etc, and we could feel confident we weren’t destroying large parts of our dom, every time our model data changed.

Example 2 – Simple reconciliation example

JS Bin

This example functions in exactly the same way, but under the hood (the javascript tab to be precise), the implementation is different. The initial content is still rendered (I suggest this would normally be done on the server), but the updated markup is now merged into the dom instead of replacing it. This is done by loading the markup into a container div and passing the two nodes to compare to the reconciliation algorithm.

In this case, the algorithm works out that only a text change is required and applies this change to the dom. You can view the message in the console tab (open this on jsbin before running the example). You should see a message “> Updating comment/text value – source:51.4 miles, target:41.4 miles”.

This is quite a trivial example but you can view more complicated cases with multiple attribute and element changes in the test code located on Github together with the algorithm.

Example 3 – Sorting the table

JS Bin

Run the example with the console open and press the Sort by Altitude button. You should see the unintended side effect that sorting the table nodes has. Although we have only swapped the position of two rows in the table, the algorithm has no idea this has occurred. Viewing the console shows that all 8 table cells have been updated. It would be preferable that the reconciliation algorithm simply swapped the position of the nodes in the dom instead.

Fortunately we let the algorithm identify nodes by placing an id on nodes we’d like to track in the dom (as long as they remain under the same parent). Internally this isn’t very different from how the algorithm determines if nodes have been inserted or deleted – if the element has no id, one is created from the tag name and its occurrence amongst it’s siblings. By applying an id to the table row, it should be possible to determine that it has simply moved, instead of replacing all the content of each row that has changed.

Example 4 – More intelligent dom node tracking

JS Bin

This example is no different other than we add the flight id to the table row. The algorithm can now track that the dom nodes have switched position. If you run the example with the console tab open, you get the following message: “^ Move node with id:flight-77 before:[object HTMLTableRowElement]”. That was all that was required to apply the updated template to the dom.

Summary

This algorithm shows that in principle it is possible to take any two pieces of markup and to update a dom representation of one by comparing it to the dom tree created from the other. With a small amount of information of how the algorithm works, a developer could apply changes by simply changing an object model and remain confident that the dom would stay more or less intact. This makes pushing updates to a web page incredibly quick and simple and could form the basis of an isomorphic approach with mustache (or any templating language that produces html markup) that may be practical in more real world scenarios.

Get the code on GitHub

Writing an reconciliation algorithm for markup fragments

Isomorphic Javascript using Mustache Templates

Mustache is my goto html templating engine. I find it incredibly simple and expressive and I guess authors of Angular and Ember also felt the same way – both frameworks use similar syntax.

But there is a price. A big problem with both these frameworks is the requirement for javascript to be enabled, and the potential for the flash of content as the templates get compiled and populated from the model. Pages can also take a long time to load. Meh.

The increasing popularity of isometric frameworks such as React got me thinking – what if we could get all the productivity and simplicity of Mustache templates, without the associated problems? In other words, is it possible to render the template on the server (the isomorphic part), and use progressive enhancement to re-render any  content using mustache on-the-fly?

The following examples (Example 1 and Example 2) show the problem. Example 3 demonstrates how an isomorphic approach could work. Click on the tabs above each example to show or hide the html markup, script and screen output.

Example 1 – simple mustache template

JS BinThe purpose of this example is to render a mustache template that has been defined directly in the page markup. A template is turned into content using the following phases: parsing -> tokens -> rendering. To achieve this, the javascript takes the html inside the test-flight element, compiles the template into a set of tokens, renders the tokens with our sample model, and replaces the template markup with the rendered version. This is a pretty common approach – but why is it so bad? First, you may experience a horrible flash of un-rendered content as the template gets replaced by the rendered content. You can work round this, but you sacrifice performance – it can be significantly longer before your page is viewable. Other potential problems I can think of are possible search engine indexing issues. I think this blog post Don’t depend on your javascript to render your page sums up the argument nicely. So how can we do this better? First let’s set up this example so it makes sense for us to want to render the template on the server as well as the client.

Example 2 – client side render and re-render

JS Bin

Press the update button to re-render the view of our updated model data.

All we are doing here is rendering the template with two different models e.g. parsing -> tokens -> render -> render. Note – this example is still bad for the same reasons as before, but now we have a reason to make this example isomorphic, as opposed to just rendering the content on the server.

To make this isomorphic, we need to render the first pass on the server and, since we have now replaced our template with rendered content, transfer the template to the client, so that our client script can carry on using the template as normal. Lucky then that Mustache js was written in a way that its really easy to convert the tokens created from the mustache template to JSON, which can then be sent down to the browser.

Example 3 – initial server render with client update

Isomorphic Javascript with Mustache | Example 3

I didn’t actually need to write any server code, but instead added the markup that would have been rendered by any standard Mustache library on the server, and then included the template tokens as a JSON variable in the javascript – as if it had been loaded via ajax or some other mechanism. It may as well be a plain html page that we are starting with in the browser because it kind of is.

This feels a lot better to me. We can add mustache templates to our markup, knowing that these will get processed by the server and delivered to the client if we need to update the markup later. In the browser, the libraries and application code for doing this can now be loaded after initial page view, off of the critical path. In this basic example, this code is required only by the time the user is presses the update button.

Pro’s

For me the biggest win here is that you can use mustache templates as your view logic without worrying about performance on the client or any nasty flashes of text. You progressively enhance the page delivered from the server as per best practices. There is no need for <script type=”x-mustache”> hacks in your markup either, because the template is rendered by the server using e.g. Node.js. With a bit of work, this technique could become a pretty seamless way of moving data from your model to your view, no matter if that code is running on the server or browser.

Con’s

If you bind event handlers to the generated markup those are going to get lost every time you replace the innerHtml with your new markup – unless you use event delegation on the container element (which is no bad thing).

Template parsing is expensive for the server and tokens may end up being quite large, so possibly you would need to write the code so that the template tokens are cached until they change. You could also follow the Hogan model and precompile your templates as a build step, and distribute them with your application code, but theres less need for that now that startup performance is no longer an issue.

In my next post, I’ll also explore a dom reconciliation algorithm to more intelligently merge any changes rendered by the template into the dom. This will remove the worry about the impact of replacing large sections of the dom using the innerHtml technique and make this part of the process less of a hack. This is also the approach React takes and it was a whole lot of fun to figure out.

Get the code on GitHub

Isomorphic Javascript using Mustache Templates