Recently in my spare time, I have been working on a web site where developers can post code snippets which they would like to be reviewed by other developers on the web. Once a code snippet has been posted, other developers can add comments and make a revised version of the code snippet, which will be rendered under the original code snippet as a diff (the difference between the original snippet and the revised snippet). I have registered myself a domain, but the site is not ready to be launched yet. This post is about how I rendered a line-oriented diff in an ASP.NET MVC web page. I'll write another post to announce the site itself when I launch it.
The Algorithm
After a brief period of trying to figure out my own algorithm for rendering a diff, I decided to do some research on how others have solved the problem. It seems that it's not quite as easy of a problem to solve as it would seem on the surface, and there has actually been a fair amount of in-depth research done on how to solve it. I wound up deciding to use Bill Menee's Menees diff library, which uses the popular Myers algorithm, described in the paper An O(ND) Difference Algorithm and its Variations by Eugene W. Myers. The paper looks fascinating, and I might be interested in implementing it myself at some point, but for the moment I'm going to use the Menees library. Here is the abstract to the paper, to give you an overview of how Myers solves the problem.
The problems of finding a longest common subsequence of two sequences A and B and a shortest edit script
for transforming A into B have long been known to be dual problems. In this paper, they are shown to be
equivalent to finding a shortest/longest path in an edit graph. Using this perspective, a simple O(ND) time
and space algorithm is developed where N is the sum of the lengths of A and B and D is the size of the
minimum edit script for A and B. The algorithm performs well when differences are small (sequences are
similar) and is consequently fast in typical applications. The algorithm is shown to have O(N+D2 )
expected-time performance under a basic stochastic model. A refinement of the algorithm requires only
O(N) space, and the use of suffix trees leads to an O(NlgN +D2 ) time variation.
The Code
Here's the code that I came up with to render a diff created by the Menees library.
The model and view-data:
1: using System;
2: using System.Collections;
3: using System.Collections.Generic;
4: using System.Linq;
5: using System.Text;
6: using System.Web;
7:
8: using Menees.DiffUtils;
9:
10: namespace CodeReview.Models
11: {
12: /// <summary>
13: /// Represents a chunk of source code
14: /// </summary>
15: public class SourceCode
16: {
17: public int Id { get; set; }
18:
19: private string _title = string.Empty;
20:
21: public string Title
22: {
23: get
24: {
25: return _title;
26: }
27: set
28: {
29: _title = value;
30: }
31: }
32:
33: public string Description { get; set; }
34: public string Code { get; set; }
35: public string CreatedBy { get; set; }
36: public List<Comment> Comments { get; set; }
37:
38: private List<string> _lines = null;
39:
40: public List<string> Lines
41: {
42: get
43: {
44: if (_lines == null)
45: _lines = GetLines(Code);
46:
47: return _lines;
48: }
49: }
50:
51: public bool IsValid
52: {
53: get { return (GetRuleViolations().Count() == 0); }
54: }
55:
56: public SourceCode(string code)
57: : this()
58: {
59: Code = code;
60: }
61:
62: public SourceCode()
63: {
64: Comments = new List<Comment>();
65: }
66:
67: public List<Difference> Diff(SourceCode compareWith)
68: {
69: List<Difference> differences = new List<Difference>();
70: IList a = Lines;
71: IList b = compareWith.Lines;
72: TextDiff diff = new TextDiff((int)HashType.HashCode, false, false, 0);
73: EditScript script = diff.Execute(a, b);
74:
75: foreach (Edit edit in script)
76: {
77: differences.Add(ConvertEditToDifference(edit, compareWith));
78: }
79:
80: return differences;
81: }
82:
83: private List<string> GetLines(string code)
84: {
85: return code.Split('\n').ToList();
86: }
87:
88: private Difference ConvertEditToDifference(Edit edit, SourceCode compareWith)
89: {
90: return new Difference()
91: {
92: LineNumber = edit.StartA + 1,
93: Text = GetChangeText(edit, compareWith),
94: Type = ConvertEditTypeToDifferenceType(edit.Type),
95: NumberOfLines = edit.Length
96: };
97: }
98:
99: private string GetChangeText(Edit edit, SourceCode compareWith)
100: {
101: StringBuilder changeText = new StringBuilder();
102: SourceCode textSource;
103: int lineNumberInTextSource;
104:
105: if (edit.Type == EditType.Insert)
106: {
107: textSource = compareWith;
108: lineNumberInTextSource = edit.StartB;
109: }
110: else
111: {
112: textSource = this;
113: lineNumberInTextSource = edit.StartA;
114: }
115:
116: for (int i = 0; i < edit.Length; i++)
117: {
118: changeText.Append(textSource.Lines[lineNumberInTextSource + i]);
119: }
120:
121: return changeText.ToString();
122: }
123:
124: private DifferenceType ConvertEditTypeToDifferenceType(EditType editType)
125: {
126: switch (editType)
127: {
128: case EditType.Change:
129: return DifferenceType.Change;
130: case EditType.Delete:
131: return DifferenceType.Removal;
132: case EditType.Insert:
133: return DifferenceType.Addition;
134: default:
135: throw new ArgumentException("Unexpected edit type: " + editType, "editType");
136: }
137: }
138:
139: public IEnumerable<RuleViolation> GetRuleViolations()
140: {
141: if (String.IsNullOrEmpty(Title))
142: yield return new RuleViolation("Title is required", "Title");
143:
144: if (String.IsNullOrEmpty(Code))
145: yield return new RuleViolation("Code is required", "Code");
146:
147: yield break;
148: }
149:
150: private void Validate()
151: {
152: if (!IsValid)
153: throw new ApplicationException("Rule violations prevent saving");
154: }
155: }
156:
157: public class Difference
158: {
159: public DifferenceType Type { get; set; }
160: public string Text { get; set; }
161: public int LineNumber { get; set; }
162: public int NumberOfLines { get; set; }
163: }
164: }
165:
166: namespace CodeReview.ViewData
167: {
168: public class ShowSourceCodeViewData
169: {
170: public string RenderedOriginal { get; set; }
171: public List<CommentViewData> Comments { get; set; }
172:
173: public ShowSourceCodeViewData()
174: {
175: Comments = new List<CommentViewData>();
176: }
177: }
178:
179: public class CommentViewData
180: {
181: public string RenderedOriginal { get; set; }
182: public string RenderedRevised { get; set; }
183: public string Text { get; set; }
184: }
185: }
186:
The controller action and supporting methods:
1: public ActionResult Show(int? id)
2: {
3: SourceCode original = _repository.GetById(id.Value);
4: string[] originalLines = original.Lines.ToArray();
5: ShowSourceCodeViewData viewData = new ShowSourceCodeViewData();
6:
7: viewData.RenderedOriginal = ConvertFromPlainTextToHtml(original.Code);
8:
9: foreach (Comment comment in original.Comments)
10: {
11: StringBuilder originalBuilder = new StringBuilder(); //the buffer for displaying the original version (on the left side of the diff)
12: StringBuilder editedBuilder = new StringBuilder(); //the buffer for displaying the revised version (on the right side of the diff)
13: string[] editedLines = comment.Revision.Lines.ToArray();
14: List<Difference> differences = original.Diff(comment.Revision);
15: int originalLineNumber = 0;
16: int editedLineNumber = 0;
17: CommentViewData commentViewData = new CommentViewData();
18:
19: foreach (Difference difference in differences)
20: {
21: //put all unchanged lines leading up to this difference into both buffers
22: for (; originalLineNumber < (difference.LineNumber - 1); originalLineNumber++, editedLineNumber++)
23: {
24: originalBuilder.Append(RenderLineHtml(DifferenceType.NoChange, originalLineNumber, originalLines[originalLineNumber]));
25: editedBuilder.Append(RenderLineHtml(DifferenceType.NoChange, editedLineNumber, editedLines[editedLineNumber]));
26: }
27:
28: if (difference.Type == DifferenceType.Addition)
29: {
30: string differenceText = difference.Text;
31:
32: if (differenceText.EndsWith("\r"))
33: differenceText = differenceText.Substring(0, differenceText.Length - 1);
34:
35: string[] lines = differenceText.Split('\r');
36:
37: //put added lines only into the buffer for the revised version, and add blank space to the buffer for the original version
38: foreach (string line in lines)
39: {
40: editedBuilder.Append(RenderLineHtml(difference.Type, editedLineNumber, line));
41: originalBuilder.AppendLine();
42: editedLineNumber++;
43: }
44: }
45:
46: if (difference.Type == DifferenceType.Removal)
47: {
48: string differenceText = difference.Text;
49:
50: if (differenceText.EndsWith("\r"))
51: differenceText = differenceText.Substring(0, differenceText.Length - 1);
52:
53: string[] lines = differenceText.Split('\r');
54:
55: //put removed lines only into the buffer for the original version, and add blank space to the buffer for the revised version
56: foreach (string line in lines)
57: {
58: originalBuilder.Append(RenderLineHtml(difference.Type, originalLineNumber, line));
59: editedBuilder.AppendLine();
60: originalLineNumber++;
61: }
62: }
63:
64: if (difference.Type == DifferenceType.Change)
65: {
66: //put revised version of changed line into buffer for revised version
67: editedBuilder.Append(RenderLineHtml(difference.Type, editedLineNumber, editedLines[editedLineNumber]));
68: //put original version of changed line into buffer for original version
69: originalBuilder.Append(RenderLineHtml(difference.Type, originalLineNumber, difference.Text));
70: editedLineNumber++;
71: originalLineNumber++;
72: }
73: }
74:
75: //put all remaining unchanged lines into buffer for original version
76: for (int i = originalLineNumber; i < originalLines.Length; i++)
77: originalBuilder.Append(RenderLineHtml(DifferenceType.NoChange, i, originalLines[i]));
78:
79: //put all remaining unchanged lines into buffer for revised version
80: for (int i = editedLineNumber; i < editedLines.Length; i++)
81: editedBuilder.Append(RenderLineHtml(DifferenceType.NoChange, i, editedLines[i]));
82:
83: commentViewData.RenderedOriginal = ConvertFromPlainTextToHtml(originalBuilder.ToString());
84: commentViewData.RenderedRevised = ConvertFromPlainTextToHtml(editedBuilder.ToString());
85: commentViewData.Text = comment.Text;
86:
87: viewData.Comments.Add(commentViewData);
88: }
89:
90: return View(viewData);
91: }
92:
93: private string ConvertFromPlainTextToHtml(string plainText)
94: {
95: return plainText.Replace("\r", "<br/>").Replace("\n", "").Replace(" ", " ");
96: }
97:
98: private string RenderLineHtml(DifferenceType differenceType, int lineNumber, string lineText)
99: {
100: //the line will be styled according to the type of change that was made
101: return string.Format("<div class=\"{0}\">{1}: {2}</div>", differenceType.ToString().ToLower(), lineNumber, lineText);
102: }
The view:
1: <%
2: foreach (CommentViewData comment in Model.Comments)
3: { 4: %>
5: <p class="comment_body">
6: <%= comment.Text %>
7: </p>
8: <div class="editingArea">
9: <div class="originalCode">
10: Original:<br />
11: <%= comment.RenderedOriginal %>
12: </div>
13: <div class="editedCode">
14: Edited:<br />
15: <%= comment.RenderedRevised %>
16: </div>
17: <div style="height: 500px"></div>
18: </div>
19: <%
20: }
21: %>
The CSS:
.originalCode { float: left; border: thin solid black; padding: 10px 10px 10px 10px; width: 450px; }
.editedCode { float: right; border: thin solid black; padding: 10px 10px 10px 10px; position: absolute; left: 600px; width: 450px; }
.editingArea { }
.addition { background-color: Black; color: green }
.removal { background-color: Black; color: red }
.change { background-color: Black; color: white }
.comment_body { font-style: italic; font-weight: bold; }
.comment_header { font-weight: bold; }
#Title { width: 700px; }
#Description { width: 700px; height: 150px; }
#Code { width: 700px; height: 300px; }
This is going to need some work before it's ready for prime time (the HTML conversion and CSS need work, and the controller method should be broken out into smaller methods, perhaps using a command pattern or something, etc.), but I figured it was enough to get you going if you're thinking about implementing something like this yourself. (This approach could make for some very nice build notification emails, IMO.) Did I leave anything important out? Is there a better or easier way to do this? Is there a glaring bug? Leave a comment!