summaryrefslogtreecommitdiffabout
authorRagnar Ouchterlony <ragnar@lysator.liu.se>2009-10-25 17:13:22 (UTC)
committer Lars Hjemli <hjemli@gmail.com>2009-11-07 14:37:11 (UTC)
commit735e15e38a484bf0daa98776fa7cde270a271cda (patch) (unidiff)
tree588545cead471e8997adc1ae5abca164a4873481
parent4a198e4b8ee62a9a8b5156a46bfce46dc7223fe9 (diff)
downloadcgit-735e15e38a484bf0daa98776fa7cde270a271cda.zip
cgit-735e15e38a484bf0daa98776fa7cde270a271cda.tar.gz
cgit-735e15e38a484bf0daa98776fa7cde270a271cda.tar.bz2
In side-by-side diff, add support for marking individual characters.
Refuses to do so if the left hand side of the diff has different amount of differing lines to the right hand side to avoid confusion. Note that I use the naive dynamic programming approach for calculating the longest common subsequence. We could probably be more efficient by using a better algorithm. The LCS calculating function is O(n*m) and uses up n*m amount of memory too (so if we we compare two strings of length 100, I use an array of 10000 for calculating the LCS). Might want to not calculate LCS if the length of the line is too large. Signed-off-by: Ragnar Ouchterlony <ragnar@lysator.liu.se>
Diffstat (more/less context) (ignore whitespace changes)
-rw-r--r--cgit.css10
-rw-r--r--ui-ssdiff.c145
2 files changed, 130 insertions, 25 deletions
diff --git a/cgit.css b/cgit.css
index 3f37165..9e6d2a4 100644
--- a/cgit.css
+++ b/cgit.css
@@ -629,2 +629,7 @@ table.ssdiff td.add_dark {
629 629
630table.ssdiff span.add {
631 background: #cfc;
632 font-weight: bold;
633}
634
630table.ssdiff td.del { 635table.ssdiff td.del {
@@ -641,2 +646,7 @@ table.ssdiff td.del_dark {
641 646
647table.ssdiff span.del {
648 background: #fcc;
649 font-weight: bold;
650}
651
642table.ssdiff td.changed { 652table.ssdiff td.changed {
diff --git a/ui-ssdiff.c b/ui-ssdiff.c
index 5673642..408e620 100644
--- a/ui-ssdiff.c
+++ b/ui-ssdiff.c
@@ -17,2 +17,48 @@ static struct deferred_lines *deferred_new, *deferred_new_last;
17 17
18static char *longest_common_subsequence(char *A, char *B)
19{
20 int i, j, ri;
21 int m = strlen(A);
22 int n = strlen(B);
23 int L[m + 1][n + 1];
24 int tmp1, tmp2;
25 int lcs_length;
26 char *result;
27
28 for (i = m; i >= 0; i--) {
29 for (j = n; j >= 0; j--) {
30 if (A[i] == '\0' || B[j] == '\0') {
31 L[i][j] = 0;
32 } else if (A[i] == B[j]) {
33 L[i][j] = 1 + L[i + 1][j + 1];
34 } else {
35 tmp1 = L[i + 1][j];
36 tmp2 = L[i][j + 1];
37 L[i][j] = (tmp1 > tmp2 ? tmp1 : tmp2);
38 }
39 }
40 }
41
42 lcs_length = L[0][0];
43 result = xmalloc(lcs_length + 2);
44 memset(result, 0, sizeof(*result) * (lcs_length + 2));
45
46 ri = 0;
47 i = 0;
48 j = 0;
49 while (i < m && j < n) {
50 if (A[i] == B[j]) {
51 result[ri] = A[i];
52 ri += 1;
53 i += 1;
54 j += 1;
55 } else if (L[i + 1][j] >= L[i][j + 1]) {
56 i += 1;
57 } else {
58 j += 1;
59 }
60 }
61 return result;
62}
63
18static int line_from_hunk(char *line, char type) 64static int line_from_hunk(char *line, char type)
@@ -75,2 +121,13 @@ static char *replace_tabs(char *line)
75 121
122static int calc_deferred_lines(struct deferred_lines *start)
123{
124 struct deferred_lines *item = start;
125 int result = 0;
126 while (item) {
127 result += 1;
128 item = item->next;
129 }
130 return result;
131}
132
76static void deferred_old_add(char *line, int line_no) 133static void deferred_old_add(char *line, int line_no)
@@ -103,5 +160,41 @@ static void deferred_new_add(char *line, int line_no)
103 160
104static void print_ssdiff_line(char *class, int old_line_no, char *old_line, 161static void print_part_with_lcs(char *class, char *line, char *lcs)
105 int new_line_no, char *new_line) 162{
163 int line_len = strlen(line);
164 int i, j;
165 char c[2] = " ";
166 int same = 1;
167
168 j = 0;
169 for (i = 0; i < line_len; i++) {
170 c[0] = line[i];
171 if (same) {
172 if (line[i] == lcs[j])
173 j += 1;
174 else {
175 same = 0;
176 htmlf("<span class='%s'>", class);
177 }
178 } else if (line[i] == lcs[j]) {
179 same = 1;
180 htmlf("</span>");
181 j += 1;
182 }
183 html_txt(c);
184 }
185}
186
187static void print_ssdiff_line(char *class,
188 int old_line_no,
189 char *old_line,
190 int new_line_no,
191 char *new_line, int individual_chars)
106{ 192{
193 char *lcs = NULL;
194 if (old_line)
195 old_line = replace_tabs(old_line + 1);
196 if (new_line)
197 new_line = replace_tabs(new_line + 1);
198 if (individual_chars && old_line && new_line)
199 lcs = longest_common_subsequence(old_line, new_line);
107 html("<tr>"); 200 html("<tr>");
@@ -114,7 +207,7 @@ static void print_ssdiff_line(char *class, int old_line_no, char *old_line,
114 htmlf("<td class='lineno'></td><td class='%s_dark'>", class); 207 htmlf("<td class='lineno'></td><td class='%s_dark'>", class);
115
116 if (old_line) { 208 if (old_line) {
117 old_line = replace_tabs(old_line + 1); 209 if (lcs)
118 html_txt(old_line); 210 print_part_with_lcs("del", old_line, lcs);
119 free(old_line); 211 else
212 html_txt(old_line);
120 } 213 }
@@ -122,3 +215,2 @@ static void print_ssdiff_line(char *class, int old_line_no, char *old_line,
122 html("</td>"); 215 html("</td>");
123
124 if (new_line_no > 0) 216 if (new_line_no > 0)
@@ -130,7 +222,7 @@ static void print_ssdiff_line(char *class, int old_line_no, char *old_line,
130 htmlf("<td class='lineno'></td><td class='%s_dark'>", class); 222 htmlf("<td class='lineno'></td><td class='%s_dark'>", class);
131
132 if (new_line) { 223 if (new_line) {
133 new_line = replace_tabs(new_line + 1); 224 if (lcs)
134 html_txt(new_line); 225 print_part_with_lcs("add", new_line, lcs);
135 free(new_line); 226 else
227 html_txt(new_line);
136 } 228 }
@@ -138,2 +230,8 @@ static void print_ssdiff_line(char *class, int old_line_no, char *old_line,
138 html("</td></tr>"); 230 html("</td></tr>");
231 if (lcs)
232 free(lcs);
233 if (new_line)
234 free(new_line);
235 if (old_line)
236 free(old_line);
139} 237}
@@ -143,3 +241,2 @@ static void print_deferred_old_lines()
143 struct deferred_lines *iter_old, *tmp; 241 struct deferred_lines *iter_old, *tmp;
144
145 iter_old = deferred_old; 242 iter_old = deferred_old;
@@ -147,3 +244,3 @@ static void print_deferred_old_lines()
147 print_ssdiff_line("del", iter_old->line_no, 244 print_ssdiff_line("del", iter_old->line_no,
148 iter_old->line, -1, NULL); 245 iter_old->line, -1, NULL, 0);
149 tmp = iter_old->next; 246 tmp = iter_old->next;
@@ -157,7 +254,6 @@ static void print_deferred_new_lines()
157 struct deferred_lines *iter_new, *tmp; 254 struct deferred_lines *iter_new, *tmp;
158
159 iter_new = deferred_new; 255 iter_new = deferred_new;
160 while (iter_new) { 256 while (iter_new) {
161 print_ssdiff_line("add", -1, NULL, iter_new->line_no, 257 print_ssdiff_line("add", -1, NULL,
162 iter_new->line); 258 iter_new->line_no, iter_new->line, 0);
163 tmp = iter_new->next; 259 tmp = iter_new->next;
@@ -171,2 +267,5 @@ static void print_deferred_changed_lines()
171 struct deferred_lines *iter_old, *iter_new, *tmp; 267 struct deferred_lines *iter_old, *iter_new, *tmp;
268 int n_old_lines = calc_deferred_lines(deferred_old);
269 int n_new_lines = calc_deferred_lines(deferred_new);
270 int individual_chars = (n_old_lines == n_new_lines ? 1 : 0);
172 271
@@ -178,10 +277,10 @@ static void print_deferred_changed_lines()
178 iter_old->line, 277 iter_old->line,
179 iter_new->line_no, iter_new->line); 278 iter_new->line_no, iter_new->line,
279 individual_chars);
180 else if (iter_old) 280 else if (iter_old)
181 print_ssdiff_line("changed", iter_old->line_no, 281 print_ssdiff_line("changed", iter_old->line_no,
182 iter_old->line, -1, NULL); 282 iter_old->line, -1, NULL, 0);
183 else if (iter_new) 283 else if (iter_new)
184 print_ssdiff_line("changed", -1, NULL, 284 print_ssdiff_line("changed", -1, NULL,
185 iter_new->line_no, iter_new->line); 285 iter_new->line_no, iter_new->line, 0);
186
187 if (iter_old) { 286 if (iter_old) {
@@ -204,3 +303,2 @@ void cgit_ssdiff_print_deferred_lines()
204 return; 303 return;
205
206 if (deferred_old && !deferred_new) 304 if (deferred_old && !deferred_new)
@@ -211,3 +309,2 @@ void cgit_ssdiff_print_deferred_lines()
211 print_deferred_changed_lines(); 309 print_deferred_changed_lines();
212
213 deferred_old = deferred_old_last = NULL; 310 deferred_old = deferred_old_last = NULL;
@@ -222,5 +319,3 @@ void cgit_ssdiff_line_cb(char *line, int len)
222 char c = line[len - 1]; 319 char c = line[len - 1];
223
224 line[len - 1] = '\0'; 320 line[len - 1] = '\0';
225
226 if (line[0] == '@') { 321 if (line[0] == '@') {
@@ -234,3 +329,3 @@ void cgit_ssdiff_line_cb(char *line, int len)
234 print_ssdiff_line("ctx", current_old_line, line, 329 print_ssdiff_line("ctx", current_old_line, line,
235 current_new_line, line); 330 current_new_line, line, 0);
236 current_old_line += 1; 331 current_old_line += 1;