Tuesday, January 12, 2010

A Silverlight Text Diff Control

Text diff tool is really useful for checking the updates of versioning files. On the web, it is widely used in wiki systems to see the changes of articles. It may also useful for tracing forum posts, page updates of CMS, etc.

This article will describes how to create a simple text diff control in Silverlight. Before going into the details, this is screen shot of our text diff control.
Text Diff Control Screen Shot

This control contains two major parts, the core algorithm to do the calculation job, and the user interface to display the result.

Diff Algoirithms

The purpose of diff algorithm is to compute the Shortest Edit Script of two list of equalable items. Hence, all of our algorithm will implement the following IDiffEngine interface.

/// <summary>
/// Supports aligning two sequences.
/// </summary>
public interface IDiffEngine
{
    IList<DiffResult> Align<T>(IList<T> from, IList<T> to, IEqualityComparer<T> comparer);
}

/// <summary>
/// Represents a particular elements alignment result.
/// </summary>
public enum DiffResult
{
    /// <summary>
    /// Two elements are considered as the same.
    /// </summary>
    Matched,

    /// <summary>
    /// The element in target sequence is inserted to the result alignment.
    /// </summary>
    Inserted,

    /// <summary>
    /// The element in original sequence is inserted to the result alignment.
    /// </summary>
    Deleted
}
    

Other than this, we need an interface accepting string list, in other word, lines of a text. It is because we may have extensions specified to text, i.e. spacing handling, case sensitivity, etc.

/// <summary>
/// Supports aligning two list of strings.
/// </summary>
public interface ITextDiffEngine
{
    IList<DiffResult> Algin(IList<string> from, IList<string> to);
}
    

Considering implementation, a widely used diff algorithm is the one described by Eugene W. Myers, in his paper, "An O(ND) Difference Algorithm and Its Variations". A simple implementation is included in the sample, which has O((N + M)D) time and space complexity. This article won't explain the details of this algorithm, but a good tutorial is available on The Code Project by Nicholas Butler.

Another algorithm in our control is Needleman-Wunsch algorithm which is commonly use for sequence alignment. This algorithm has complexity O(N + M) in both time and space. Now, we can verify both algorithms by comparing the outputs.

User Interface

As the screen shot shown previously, the control UI is similar with some text diff applications. It is using two text blocks to display the texts comparing, two scroll bars used for scrolling text blocks, and a bar on the left to summarize the diff result. Further, the text blocks is wrapping in side scroll viewer so that the scroll bar can hook on them.

Let's define a Silverlight templated control DiffViewer, with the sub controls addressed above. These controls are retrieved in OnApplyTemplate method.

/// <summary>
/// Represents the text diff control.
/// </summary>
[TemplatePart(Name = RightTextBlockElement, Type = typeof(TextBlock))]
[TemplatePart(Name = LeftTextBlockElement, Type = typeof(TextBlock))]
[TemplatePart(Name = DiffBrushElement, Type = typeof(LinearGradientBrush))]
[TemplatePart(Name = HorizontalScrollBarElement, Type = typeof(ScrollBar))]
[TemplatePart(Name = VerticalScrollBarElement, Type = typeof(ScrollBar))]
[TemplatePart(Name = RightTextScrollViewerElement, Type = typeof(ScrollViewer))]
[TemplatePart(Name = LeftTextScrollViewerElement, Type = typeof(ScrollViewer))]
public class DiffViewer : Control
{
    /// <summary> ...
    private const string RightTextBlockElement = "RightTextBlockElement";

    /// <summary> ...
    private const string LeftTextBlockElement = "LeftTextBlockElement";

    /// <summary> ...
    private const string DiffBrushElement = "DiffBrushElement";

    /// <summary> ...
    private const string HorizontalScrollBarElement = "HorizontalScrollBarElement";

    /// <summary> ...
    private const string VerticalScrollBarElement = "VerticalScrollBarElement";

    /// <summary> ...
    private const string RightTextScrollViewerElement = "RightTextScrollViewerElement";

    /// <summary> ...
    private const string LeftTextScrollViewerElement = "LeftTextScrollViewerElement";
    
    /// <summary> ...
    public override void OnApplyTemplate()
    {
        base.OnApplyTemplate();

        // Lookup template parts
        rightTextBlock = GetTemplateChild(RightTextBlockElement) as TextBlock;
        leftTextBlock = GetTemplateChild(LeftTextBlockElement) as TextBlock;
        horizontalScrollBar = GetTemplateChild(HorizontalScrollBarElement) as ScrollBar;
        verticalScrollBar = GetTemplateChild(VerticalScrollBarElement) as ScrollBar;
        leftTextScrollViewer = GetTemplateChild(LeftTextScrollViewerElement) as ScrollViewer;
        rightTextScrollViewer = GetTemplateChild(RightTextScrollViewerElement) as ScrollViewer;
        diffBrush = GetTemplateChild(DiffBrushElement) as LinearGradientBrush;
        
        leftTextBlock.SizeChanged += TextBlockSizeChanged;
        rightTextBlock.SizeChanged += TextBlockSizeChanged;

        verticalScrollBar.Scroll += VerticalScrollBarScroll;
        horizontalScrollBar.Scroll += HorizontalScrollBarScroll;

        templatedApplied = true;

        UpdateComparison();
    }
        
    /// ...
}
    

In OnApplyTemplate method, I also added event handlers to SizeChanged and Scroll event of text blocks and scroll bars. Essentially, the scroll bars will be adjusted according to the size of text blocks, and the viewport of text blocks will be moved according to the position of scroll bars.

public class DiffViewer : Control
{
    /// <summary> ...
    private void HorizontalScrollBarScroll(object sender, ScrollEventArgs e)
    {
        // Scroll text blocks horiontally
        leftTextScrollViewer.ScrollToHorizontalOffset(horizontalScrollBar.Value);
        rightTextScrollViewer.ScrollToHorizontalOffset(horizontalScrollBar.Value);
    }

    /// <summary> ...
    private void VerticalScrollBarScroll(object sender, ScrollEventArgs e)
    {
        // Scroll text blocks vertically
        leftTextScrollViewer.ScrollToVerticalOffset(verticalScrollBar.Value);
        rightTextScrollViewer.ScrollToVerticalOffset(verticalScrollBar.Value);
    }

    /// <summary> ...
    private void TextBlockSizeChanged(object sender, SizeChangedEventArgs e)
    {
        UpdateScrollBars();
    }

    /// <summary> ...
    private void UpdateScrollBars()
    {
        // Horizontal scroll bar
        var viewportWidth = Math.Max(leftTextScrollViewer.ViewportWidth, rightTextScrollViewer.ViewportWidth);
        var extentWidth = Math.Max(leftTextScrollViewer.ExtentWidth, rightTextScrollViewer.ExtentWidth);
        horizontalScrollBar.ViewportSize = viewportWidth;
        horizontalScrollBar.Maximum = extentWidth - viewportWidth;

        // Vertical scroll bar
        var viewportHeight = Math.Max(leftTextScrollViewer.ViewportHeight, rightTextScrollViewer.ViewportHeight);
        var extentHeight = Math.Max(leftTextScrollViewer.ExtentHeight, rightTextScrollViewer.ExtentHeight);
        verticalScrollBar.ViewportSize = viewportHeight;
        verticalScrollBar.Maximum = extentHeight - viewportHeight;
    }
        
    /// ...
}

Then, we need the dependency properties for two text inputs and the ITextDiffEngine instance to be used. A static method UpdateComparison is tracing these properties and delegates to namesake method of the DiffView instance.

public class DiffViewer : Control
{
    /// <summary> ...
    public static readonly DependencyProperty LeftTextProperty =
        DependencyProperty.Register("LeftText", typeof(string), typeof(DiffViewer), new PropertyMetadata(UpdateComparison));

    /// <summary> ...
    public static readonly DependencyProperty RightTextProperty =
        DependencyProperty.Register("RightText", typeof(string), typeof(DiffViewer), new PropertyMetadata(UpdateComparison));

    /// <summary> ...
    public static readonly DependencyProperty DiffEngineProperty =
        DependencyProperty.Register("DiffEngine", typeof(ITextDiffEngine), typeof(DiffViewer), new PropertyMetadata(UpdateComparison));

    /// <summary> ...
    public string LeftText
    {
        get { return (string)GetValue(LeftTextProperty); }
        set { SetValue(LeftTextProperty, value); }
    }

    /// <summary> ...
    public string RightText
    {
        get { return (string)GetValue(RightTextProperty); }
        set { SetValue(RightTextProperty, value); }
    }

    /// <summary> ...
    public ITextDiffEngine DiffEngine
    {
        get { return (ITextDiffEngine)GetValue(DiffEngineProperty); }
        set { SetValue(DiffEngineProperty, value); }
    }
    
    private static void UpdateComparison(DependencyObject dependencyObject, DependencyPropertyChangedEventArgs eventArgs)
    {
        var diffView = dependencyObject as DiffViewer;
        if (diffView != null)
        {
            if (diffView.templatedApplied && diffView.AutoUpdate)
            {
                diffView.UpdateComparison();
            }
        }
    }
        
    /// ...
}
    

Finally, UpdateComparison method will invokes the diff engine and displaying result. Inside the method, each line in both texts will be aligned and added to text blocks as Inline objects. The color brush will be draw in the same time as well.

public class DiffViewer : Control
{
    /// <summary> ...
    public void UpdateComparison()
    {
        // ...

        // Compute alignment
        var diffSolution = engine.Algin(leftTextLines, rightTextLines);

        // ...

        for (int i = 0; i < solutionLength; ++i)
        {
            var lineResult = diffSolution[i];

            // Append inlines according to result
            switch (lineResult)
            {
                case DiffResult.Matched:
                    // ...
                    break;
                case DiffResult.Deleted:
                    // ...
                    break;
                case DiffResult.Inserted:
                    // ...
                    break;
            }


            // ...

            if (lastResult != lineResult)
            {
                // End previous color
                gradientStops.Add(CreateGradientStop(lastResult, i, solutionLength));

                // Start new color
                gradientStops.Add(CreateGradientStop(lineResult, i, solutionLength));

                lastResult = lineResult;
            }
        }
        
        // ...
    }
        
    /// ...
}
    

If you have Silverlight 3 installed, you should be able to see the sample application running underneath. Feel free to have a try!

Get Microsoft Silverlight