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

Leave a Reply

Your email address will not be published. Required fields are marked *