A Side-By-Side Diff Viewer Built With Ext JS

July 13, 2010 by James Brantly

One of the great things about Ext JS is how easy it is to create web applications with desktop functionality. In this article I’ll show you how to create a familiar application: a visual side-by-side diff tool. The tool provides a diff algorithm implementation in Javascript and a custom code viewing component that can interpret the results of the diff to show insertions, deletions and modifications.

The Diff Algorithm

The most important part of a diff tool is the diff implementation itself. While there are a few Javascript implementations floating around the web these days, for this project I decided to start from scratch using the algorithm described in Eugene Myer’s paper. The details of the algorithm itself is beyond the scope of this article. However, the input and output is important to understand.

The input is simply two arrays which I’ll call A and B. The diff algorithm can take arrays of characters, numbers, strings or other comparable data as input. What the arrays hold is irrelevant as long as their contents can be compared for equality. The output is called an edit script. An edit script is a list of instructions for how to convert array A into array B through the deletion of items from A and the insertion of items into B. As a demonstration, I’ll use the example from the paper: “ABCABBA” and “CBABAC”. First, I turn these strings into arrays of characters. Then I run the arrays through the diff algorithm to obtain the edit script.

var A = ['A', 'B', 'C', 'A', 'B', 'B', 'A'],
    B = ['C', 'B', 'A', 'B', 'A', 'C'];

var editScript = diff(A, B);
// editScript = {
//     deletions: [0, 1, 5],
//     insertions: [1, 5],
// }

Note that the edit script indicates deletions from A at indexes 0, 1 and 5 and insertions into B at index 1 and 5. To see how this works, I’ll walk through the application of the edit script by using two cursors, one for A and one for B, and reconstruct B from A.

Note that in the above reconstruction, I use data from B itself for insertions because the edit script does not contain that information. In other words, the edit script indicates an insertion at index 1 but it does not specify what character should go there. This is fine for the visual diff since all we’re interested in is the indexes. For patching, the edit script would also need to include the inserted data.

Making it Visual

Using the above process, it’s possible to mark lines as inserted, deleted or modified as they are created in the DOM. Instead of comparing characters in a string, I split the code into arrays of lines. The lines are the input to the diff algorithm. The following code shows how the viewer component renders text using the edit script that is passed in after the diff. Notice that two cursors are maintained to keep track of placement in A and B, and those cursors are used in conjunction with the edit script to set CSS classes or insert empty lines.

setCode: function(code, diff) {
    // Clear
    this.el.update("");

        // Create copies of the edit script
    var insertions = diff.insertions.slice(0),
        deletions = diff.deletions.slice(0),

        // Obtain reference to HTML templates
        lineTpl = Ext.ux.CodeViewer.lineTpl,
        emptyLineTpl = Ext.ux.CodeViewer.emptyLineTpl,

        // Create a "pre" tag to hold the code
        pre = this.el.createChild({tag: 'pre'}),

        // Normalize line-breaks in the code
        code = code.replace(/\r\n?/g, '\n'),

        // Split code into discrete lines
        lines = code.split('\n'),

        // Cursors/flags for walking the edit script
        sideAIndex = 0,
        sideBIndex = 0,
        sideAChangeIndex = deletions.shift(),
        sideBChangeIndex = insertions.shift(),
        prevWasModified = false;

    // Loop over each line
    for (var i = 0, n = lines.length; i<n; i++) {
        // Create the HTML for the line, including highlighting
        var el = lineTpl.append(pre, [i+1, this.highlightLine(lines[i])]);

        // By default we want to move both cursors forward
        var advanceA = true,
            advanceB = true;

        // If both cursors indicate a change, consider it to be a modification
        if (sideAIndex === sideAChangeIndex && sideBIndex === sideBChangeIndex) {
            Ext.fly(el).addClass('ux-codeViewer-modified');

            // Get next changes
            sideAChangeIndex = deletions.shift();
            sideBChangeIndex = insertions.shift();

            // Set modified flag so that following lines
            // are marked accordingly
            prevWasModified = true;
        }
        else {
            // Different logic for side A vs side B
            // For instance, an insert means an empty line on side A
            // and highlighting on side B
            if (this.sideA) {
                // If there was a deletion
                if (sideAIndex === sideAChangeIndex) {
                    // Either highlight as deleted or modified depending
                    // on the previous line
                    Ext.fly(el).addClass(prevWasModified ? 'ux-codeViewer-modified' : 'ux-codeViewer-deleted');

                    // Get next change
                    sideAChangeIndex = deletions.shift();

                    // Don't advance B cursor
                    advanceB = false;
                }
                else {
                    // If there were insertions, generate empty lines
                    while (sideBIndex === sideBChangeIndex) {
                        // Insert empty line
                        emptyLineTpl.insertBefore(el);

                        // Get next change
                        sideBChangeIndex = insertions.shift();

                        // Keep advancing as long as there was an insertion
                        sideBIndex++;
                    }
                }
            }
            // Side B
            else {
                //  If there was an insertation
                if (sideBIndex == sideBChangeIndex) {
                    // Either highlight as inserted or modified depending
                    // on the previous line
                    Ext.fly(el).addClass(prevWasModified ? 'ux-codeViewer-modified' : 'ux-codeViewer-inserted');

                    // Get next change
                    sideBChangeIndex = insertions.shift();

                    // Don't advance A cursor
                    advanceA = false;
                }
                else {
                    // If there were deletions, generate empty lines
                    while (sideAIndex === sideAChangeIndex) {
                        // Insert empty line
                        emptyLineTpl.insertBefore(el);

                        // Get next change
                        sideAChangeIndex = deletions.shift();

                        // Keep advancing as long as there was a deletion
                        sideAIndex++;
                    }
                }
            }

            // Reset modified flag
            prevWasModified = false;
        }

        // Advance cursors
        if (advanceA) { sideAIndex++; }
        if (advanceB) { sideBIndex++; }
    }
}

Demo

You can find a working demo here. In order to change the code, click “Edit Mode”. Once you’re done editing, click “Edit Mode” again to see the changes and the diff. The un-minified source is also available for viewing.

Possible Improvements

Distinguishing modifications from insertions and deletions can be tricky. The code above starts a modification when there is an insertion and deletion at the same spot and continues the modification status through any following changes. This can pose problems if a modification is next to a true insertion or deletion because lines may not display side-by-side next to each other as you expect. You could solve this by providing more advanced logic for determining modifications. The interpretation of the results of the diff is almost as important as the diff itself.

Another improvement could be the addition of options such as ignoring whitespace. This could be accomplished in a number of ways. One would be to preprocess the code prior to running the diff algorithm. An alternative would be to create a custom comparison function for use within the diff implementation itself that ignores leading and trailing whitespace.

The tool also includes simple syntax highlighting for Javascript. This could be extended to include other languages/syntaxes and multi-line support.

A Simple Diff Viewer

And that’s how easy it is. Using standard Ext components and a couple of custom ones, you can create a great looking diff viewer for the web that requires no backend.

This entry was posted on Tuesday, July 13th, 2010 at 1:18 pm and is filed under Applications, Ext JS, Open Source, Tutorials. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.