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

Responsive design – a simpler approach

If you’ve spent a bit of time working on responsive websites, you’ll have hit two problems or frustrations …

1. Scrolling up and down your css file comparing values between media query sections
2. Using mediaListeners, or checking body width just to work out what media query / display mode your page is currently using.

Inspired by libraries like moderniser or templates like html5 boilerplate that places classes in the head or body tag, I thought it would make life easier if you could place a class on an element (usually the body tag but any element is supported) and then go forth and style and code as usual.

The result is the mediaQuery plug-in for jQuery. If you want to use this plug-in you need to be comfortable with the following: you are already going to use jQuery, and you don’t mind your site being non-responsive for non-javascript users.

On the positive side, the plug-in includes polyfills for css media queries and the matchMedia and addEventListener javascript functions – so you wont need to include any other code to support responsive across all browsers.

Usage is really simple:


$('body').mediaQuery({
  w320: 'only screen and (min-width: 320px)',
  w480: 'only screen and (min-width: 480px) ',
  w768: 'only screen and (min-width: 768px)',
  w1024: 'only screen and (min-width: 1024px)'
});

This code will add the classes w320, w480, w768, w1024 to the body tag depending on each of the corresponding media queries matching.

Your css is then as simple as this eg:


.w320 .content p {
  background-color:#d45354;
}

.w480 .content p {
font-size:3em;
width:360px;
height:360px;
line-height:360px;
background-color:#818b85;
}

Checking for different media queries is now as simple as this line of jQuery code:


if ($(element).hasClass('w1024')) ...

You can view an example of the technique here: http://jameswestgate.github.com/mediaQuery/examples/

Responsive design – a simpler approach

Responsively adding webP images

Whilst working out an approach to selectively loading responsive images, I realised I had finally found a place for the webP format. A quick feature detect confirmed this would be possible. This post wraps everything up in the responsive images series by combining the feature detect with the responsive images code to provide a hearty complete solution to your responsive image needs.

If you view the page at http://opencomponents.com/flexible/ using the latest Opera or Chrome client, and inspect the images, you should notice that the image paths end in the .webp extension. This saves up to 50% download size on the larger images without any loss in quality.

On the smaller version of the images it was interesting to note that at default quality, the images were actually bigger. If I dropped the quality slightly, a more modest 20% gain was usually found. Must say though that the quality is still excellent.

Responsively adding webP images

Altering image sizes responsively in all browsers

If you view the responsive web page page by Ethan Marcott in IE8, you’ll notice that it doesn’t work in the same way as modern browsers. This is because IE8 and below doesn’t support media queries – the smart bit of css we use to conditionally style our page based on current or device width. We also need to evaluate media queries to set our img tag through javascript using windows.matchMedia and media query list addListener– this isn’t supported in IE9 or less.

We need another polyfill – to add media queries to IE8 and below and to add media query matching and listening in IE9 (as well as any other unsupported platforms). The responsive polyfill I’ve written combines elements of Scott Jehl’s respond.js polyfill for media queries, Paul Irish’s matchMedia.js polyfill and my own code for media query listeners whilst keeping performance a priority.

This allows us to use code to detect when to change the image or image size in the browser and set the correct image path on initial page load. We thus take the following steps:

– set up a media query to detect changes at a width of 600 pixels
– read the contents of noscript tags and add an image to the dom depending on the media query
– listen to the media query so that when it changes we can modify the image path accordingly.

var mql = window.matchMedia('only screen and (max-width: 600px)');
var elements;
	
//Get contents of noscript tags 
var tags = document.getElementsByTagName("noscript");

//Add image to dom depending on media query
for (var i=0, len=tags.length; i<len; i++) {
  var markup = tags[i].textContent.trim();

  if (mql.matches) markup = markup.replace("/large/", "/small/");
  tags[i].insertAdjacentHTML('afterend', markup);
}

//Scale up to large / down to small when media query changes
mql.addListener(function() {

  if (!elements) elements = document.getElementsByTagName("img");
		
  var from = (mql.matches) ? "/large/" : "/small/";
  var to = (mql.matches) ? "/small/" : "/large/";

  for (var i=0, len=elements.length; i<len; i++) {
    if (elements[i].className.indexOf("responsive") > -1)
      elements[i].src = elements[i].src.replace(from, to);
  }
});

View the example

Thoughts on this technique

It should be pointed out that strictly speaking, once we have the large image we dont need the small image - it is better just to scale it down. However I also think that the smaller image in a responsive design may often be different - perhaps a more cropped version - anyway this page exists to demonstrate the basic technique only.

We also dont use a jQuery style document.ready type approach - this is simply not needed for such a simple example - placing the code in the footer is more than sufficient. However - because the images are loaded fairly late in the day you can see the image 'waterfall' as they are loaded. A more advanced technique may only display them once they are fully loaded, perhaps with css such as

img.responsive {display:none}
noscript img.responsive {display:block}

Is it worth the extra script vs the reduced download? Probably. Certainly the noscript code is small. Making IE9 and below fully responsive may not be worth it however.

PS. The responsive script doesn't currently read style tags in the parent document - it could easily be modified to do so however.

Altering image sizes responsively in all browsers

Progressive enhancement of NOSCRIPT tags containing images

For the 2nd of our 4 part plan to solve the problem of responsive images using current browser standards, we need to put our noscript textContent polyfill to work. What better than to refactor the seminal responsive design original from A List Apart by Ethan Marcotte.

To start with, all we do is move the 6 character images into noscript tags, add our polyfill ot the bottom of the body and run a small amount of cross browser script to append the content of the noscript tag after itself. You can see the results here.


<script type="text/javascript" src="js/noscript.min.js"></script>
<script type="text/javascript">
var tags = document.getElementsByTagName("noscript");
for (var i=0, len=tags.length; i<len; i++) {
  var tag = tags[i];
  tag.insertAdjacentHTML('afterend', tag.textContent);
}
</script>


 
This provides us with the hook we need to dynamically modify image paths before they are added to the DOM.

Progressive enhancement of NOSCRIPT tags containing images

Read noscript tag content reliably in all browsers

The first step in our 4 part plan to solve the problem of responsive images using current browser standards is to reliably access the content inside a noscript tag. Modern browsers support access to the content of the noscript tag through either the innerHTML property or the textContent property. Since innerHTML is encoded, and is also read-only in IE<9, and textContent seems to contain markup perfectly in supported browser, it is the property we will polyfill.

The first job is to feature detect the property, which is done simply with this piece of code:

var div = document.createElement("div"); 
div.innerHTML = "<noscript><span></span></noscript>"; 
var elements = div.getElementsByTagName("noscript"); 
if (elements.length && elements[0].textContent) return; 

 
If we need to add the property, we have to resort to retreiving the markup of the page and parsing it with a regex. I know this may be frowned upon, but in this case it is quick and fairly reliable. In this case we also need to path the XmlHttpRequest object, and then retrieve the markup of the current browser location via ajax.

patchHttpRequest(); 
var xmlhttp = new XMLHttpRequest(); 
xmlhttp.onreadystatechange = function() { 
  if (xmlhttp.readyState === 4 && xmlhttp.status === 200) { 
    var regex = /<script (.|n)*?>(.|n)*?</script>/igm; 
    var tags = document.getElementsByTagName("noscript"); 
..

 
Finally, we loop through each noscript tag, and set the textContent property.

var results = [], response = xmlhttp.responseText; 
var i=0, len=tags.length;
while (i < len && results) {
  results = regex.exec(response); 
  tags[i].textContent = results[1]; 
  i++; 
} 

 
Visit the github page to view the code packed together with some dom and ajax helper code.

Read noscript tag content reliably in all browsers

Responsive Images – what’s the problem?

Something I’ve been grappling with for a while is a good solid approach to loading the correct image at the correct screen size in a responsive design. This is hard one lots of people have been working on. Mainly because using an image tag means unrequired images are loaded before you have a change to change the src attribute, and there isn’t a semantic alternative available to the img tag (yet).

So what we need is a clean easy to use approach, that is semantic and can be progressively enhanced, is responsive, and that works across all browsers on all types of devices. Here’s the approach I will be following in the next few posts:

1. Consistently detect the contents of noscript tag
2. Append an appropriate img tag to the markup for script-enabled browsers
3. Change the image based on a call to matchMedia and the resulting MediaQueryList
4. Bonus: add support for Google’s webP format

Responsive Images – what’s the problem?

Detecting webP support

If you are loading images on the fly, it may be worthwhile detecting support for Google’s webP format. It offers size reduction of 30 – 40% over png and jpeg without loss in quality. You can use lossless or lossy compression too.

To feature detect, use this code:

function testWepP(callback) {
    var webP = new Image();     
     webP.src = 'data:image/webp;base64,UklGRi4AAABXRUJQVlA4TCEAAAAvAUAAEB8wAiMw' + 
'AgSSNtse/cXjxyCCmrYNWPwmHRH9jwMA';
     webP.onload = webP.onerror = function () {
         callback(webP.height === 2);     
     }; 
};

testWebP(function(supported) {
     console.log((supported) ? "webP 0.2.0 supported!" : "webP not supported."); 
});

No image required – it uses a data uri to determine support.

Detecting webP support