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
@@ -627,6 +627,11 @@ table.ssdiff td.add_dark {
627 min-width: 50%; 627 min-width: 50%;
628} 628}
629 629
630table.ssdiff span.add {
631 background: #cfc;
632 font-weight: bold;
633}
634
630table.ssdiff td.del { 635table.ssdiff td.del {
631 color: black; 636 color: black;
632 background: #fcc; 637 background: #fcc;
@@ -639,6 +644,11 @@ table.ssdiff td.del_dark {
639 min-width: 50%; 644 min-width: 50%;
640} 645}
641 646
647table.ssdiff span.del {
648 background: #fcc;
649 font-weight: bold;
650}
651
642table.ssdiff td.changed { 652table.ssdiff td.changed {
643 color: black; 653 color: black;
644 background: #ffc; 654 background: #ffc;
diff --git a/ui-ssdiff.c b/ui-ssdiff.c
index 5673642..408e620 100644
--- a/ui-ssdiff.c
+++ b/ui-ssdiff.c
@@ -15,6 +15,52 @@ struct deferred_lines {
15static struct deferred_lines *deferred_old, *deferred_old_last; 15static struct deferred_lines *deferred_old, *deferred_old_last;
16static struct deferred_lines *deferred_new, *deferred_new_last; 16static 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)
19{ 65{
20 char *buf1, *buf2; 66 char *buf1, *buf2;
@@ -73,6 +119,17 @@ static char *replace_tabs(char *line)
73 return result; 119 return result;
74} 120}
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)
77{ 134{
78 struct deferred_lines *item = xmalloc(sizeof(struct deferred_lines)); 135 struct deferred_lines *item = xmalloc(sizeof(struct deferred_lines));
@@ -101,9 +158,45 @@ static void deferred_new_add(char *line, int line_no)
101 } 158 }
102} 159}
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>");
108 if (old_line_no > 0) 201 if (old_line_no > 0)
109 htmlf("<td class='lineno'>%d</td><td class='%s'>", 202 htmlf("<td class='lineno'>%d</td><td class='%s'>",
@@ -112,15 +205,14 @@ static void print_ssdiff_line(char *class, int old_line_no, char *old_line,
112 htmlf("<td class='lineno'></td><td class='%s'>", class); 205 htmlf("<td class='lineno'></td><td class='%s'>", class);
113 else 206 else
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 }
121 214
122 html("</td>"); 215 html("</td>");
123
124 if (new_line_no > 0) 216 if (new_line_no > 0)
125 htmlf("<td class='lineno'>%d</td><td class='%s'>", 217 htmlf("<td class='lineno'>%d</td><td class='%s'>",
126 new_line_no, class); 218 new_line_no, class);
@@ -128,24 +220,29 @@ static void print_ssdiff_line(char *class, int old_line_no, char *old_line,
128 htmlf("<td class='lineno'></td><td class='%s'>", class); 220 htmlf("<td class='lineno'></td><td class='%s'>", class);
129 else 221 else
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 }
137 229
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}
140 238
141static void print_deferred_old_lines() 239static void print_deferred_old_lines()
142{ 240{
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;
146 while (iter_old) { 243 while (iter_old) {
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;
150 free(iter_old); 247 free(iter_old);
151 iter_old = tmp; 248 iter_old = tmp;
@@ -155,11 +252,10 @@ static void print_deferred_old_lines()
155static void print_deferred_new_lines() 252static void print_deferred_new_lines()
156{ 253{
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;
164 free(iter_new); 260 free(iter_new);
165 iter_new = tmp; 261 iter_new = tmp;
@@ -169,6 +265,9 @@ static void print_deferred_new_lines()
169static void print_deferred_changed_lines() 265static void print_deferred_changed_lines()
170{ 266{
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
173 iter_old = deferred_old; 272 iter_old = deferred_old;
174 iter_new = deferred_new; 273 iter_new = deferred_new;
@@ -176,14 +275,14 @@ static void print_deferred_changed_lines()
176 if (iter_old && iter_new) 275 if (iter_old && iter_new)
177 print_ssdiff_line("changed", iter_old->line_no, 276 print_ssdiff_line("changed", iter_old->line_no,
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) {
188 tmp = iter_old->next; 287 tmp = iter_old->next;
189 free(iter_old); 288 free(iter_old);
@@ -202,14 +301,12 @@ void cgit_ssdiff_print_deferred_lines()
202{ 301{
203 if (!deferred_old && !deferred_new) 302 if (!deferred_old && !deferred_new)
204 return; 303 return;
205
206 if (deferred_old && !deferred_new) 304 if (deferred_old && !deferred_new)
207 print_deferred_old_lines(); 305 print_deferred_old_lines();
208 else if (!deferred_old && deferred_new) 306 else if (!deferred_old && deferred_new)
209 print_deferred_new_lines(); 307 print_deferred_new_lines();
210 else 308 else
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;
214 deferred_new = deferred_new_last = NULL; 311 deferred_new = deferred_new_last = NULL;
215} 312}
@@ -220,9 +317,7 @@ void cgit_ssdiff_print_deferred_lines()
220void cgit_ssdiff_line_cb(char *line, int len) 317void cgit_ssdiff_line_cb(char *line, int len)
221{ 318{
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] == '@') {
227 current_old_line = line_from_hunk(line, '-'); 322 current_old_line = line_from_hunk(line, '-');
228 current_new_line = line_from_hunk(line, '+'); 323 current_new_line = line_from_hunk(line, '+');
@@ -232,7 +327,7 @@ void cgit_ssdiff_line_cb(char *line, int len)
232 if (deferred_old || deferred_new) 327 if (deferred_old || deferred_new)
233 cgit_ssdiff_print_deferred_lines(); 328 cgit_ssdiff_print_deferred_lines();
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;
237 current_new_line += 1; 332 current_new_line += 1;
238 } else if (line[0] == '+') { 333 } else if (line[0] == '+') {