ui-ssdiff.c (view raw)
1#include "cgit.h"
2#include "html.h"
3#include "ui-shared.h"
4#include "ui-diff.h"
5#include "ui-ssdiff.h"
6
7extern int use_ssdiff;
8
9static int current_old_line, current_new_line;
10static int **L = NULL;
11
12struct deferred_lines {
13 int line_no;
14 char *line;
15 struct deferred_lines *next;
16};
17
18static struct deferred_lines *deferred_old, *deferred_old_last;
19static struct deferred_lines *deferred_new, *deferred_new_last;
20
21static void create_or_reset_lcs_table()
22{
23 int i;
24
25 if (L != NULL) {
26 memset(*L, 0, sizeof(int) * MAX_SSDIFF_SIZE);
27 return;
28 }
29
30 // xcalloc will die if we ran out of memory;
31 // not very helpful for debugging
32 L = (int**)xcalloc(MAX_SSDIFF_M, sizeof(int *));
33 *L = (int*)xcalloc(MAX_SSDIFF_SIZE, sizeof(int));
34
35 for (i = 1; i < MAX_SSDIFF_M; i++) {
36 L[i] = *L + i * MAX_SSDIFF_N;
37 }
38}
39
40static char *longest_common_subsequence(char *A, char *B)
41{
42 int i, j, ri;
43 int m = strlen(A);
44 int n = strlen(B);
45 int tmp1, tmp2;
46 int lcs_length;
47 char *result;
48
49 // We bail if the lines are too long
50 if (m >= MAX_SSDIFF_M || n >= MAX_SSDIFF_N)
51 return NULL;
52
53 create_or_reset_lcs_table();
54
55 for (i = m; i >= 0; i--) {
56 for (j = n; j >= 0; j--) {
57 if (A[i] == '\0' || B[j] == '\0') {
58 L[i][j] = 0;
59 } else if (A[i] == B[j]) {
60 L[i][j] = 1 + L[i + 1][j + 1];
61 } else {
62 tmp1 = L[i + 1][j];
63 tmp2 = L[i][j + 1];
64 L[i][j] = (tmp1 > tmp2 ? tmp1 : tmp2);
65 }
66 }
67 }
68
69 lcs_length = L[0][0];
70 result = xmalloc(lcs_length + 2);
71 memset(result, 0, sizeof(*result) * (lcs_length + 2));
72
73 ri = 0;
74 i = 0;
75 j = 0;
76 while (i < m && j < n) {
77 if (A[i] == B[j]) {
78 result[ri] = A[i];
79 ri += 1;
80 i += 1;
81 j += 1;
82 } else if (L[i + 1][j] >= L[i][j + 1]) {
83 i += 1;
84 } else {
85 j += 1;
86 }
87 }
88
89 return result;
90}
91
92static int line_from_hunk(char *line, char type)
93{
94 char *buf1, *buf2;
95 int len;
96
97 buf1 = strchr(line, type);
98 if (buf1 == NULL)
99 return 0;
100 buf1 += 1;
101 buf2 = strchr(buf1, ',');
102 if (buf2 == NULL)
103 return 0;
104 len = buf2 - buf1;
105 buf2 = xmalloc(len + 1);
106 strncpy(buf2, buf1, len);
107 buf2[len] = '\0';
108 int res = atoi(buf2);
109 free(buf2);
110 return res;
111}
112
113static char *replace_tabs(char *line)
114{
115 char *prev_buf = line;
116 char *cur_buf;
117 int linelen = strlen(line);
118 int n_tabs = 0;
119 int i;
120 char *result;
121 char *spaces = " ";
122
123 if (linelen == 0) {
124 result = xmalloc(1);
125 result[0] = '\0';
126 return result;
127 }
128
129 for (i = 0; i < linelen; i++)
130 if (line[i] == '\t')
131 n_tabs += 1;
132 result = xmalloc(linelen + n_tabs * 8 + 1);
133 result[0] = '\0';
134
135 while (1) {
136 cur_buf = strchr(prev_buf, '\t');
137 if (!cur_buf) {
138 strcat(result, prev_buf);
139 break;
140 } else {
141 strcat(result, " ");
142 strncat(result, spaces, 8 - (strlen(result) % 8));
143 strncat(result, prev_buf, cur_buf - prev_buf);
144 }
145 prev_buf = cur_buf + 1;
146 }
147 return result;
148}
149
150static int calc_deferred_lines(struct deferred_lines *start)
151{
152 struct deferred_lines *item = start;
153 int result = 0;
154 while (item) {
155 result += 1;
156 item = item->next;
157 }
158 return result;
159}
160
161static void deferred_old_add(char *line, int line_no)
162{
163 struct deferred_lines *item = xmalloc(sizeof(struct deferred_lines));
164 item->line = xstrdup(line);
165 item->line_no = line_no;
166 item->next = NULL;
167 if (deferred_old) {
168 deferred_old_last->next = item;
169 deferred_old_last = item;
170 } else {
171 deferred_old = deferred_old_last = item;
172 }
173}
174
175static void deferred_new_add(char *line, int line_no)
176{
177 struct deferred_lines *item = xmalloc(sizeof(struct deferred_lines));
178 item->line = xstrdup(line);
179 item->line_no = line_no;
180 item->next = NULL;
181 if (deferred_new) {
182 deferred_new_last->next = item;
183 deferred_new_last = item;
184 } else {
185 deferred_new = deferred_new_last = item;
186 }
187}
188
189static void print_part_with_lcs(char *class, char *line, char *lcs)
190{
191 int line_len = strlen(line);
192 int i, j;
193 char c[2] = " ";
194 int same = 1;
195
196 j = 0;
197 for (i = 0; i < line_len; i++) {
198 c[0] = line[i];
199 if (same) {
200 if (line[i] == lcs[j])
201 j += 1;
202 else {
203 same = 0;
204 htmlf("<span class='%s'>", class);
205 }
206 } else if (line[i] == lcs[j]) {
207 same = 1;
208 htmlf("</span>");
209 j += 1;
210 }
211 html_txt(c);
212 }
213}
214
215static void print_ssdiff_line(char *class,
216 int old_line_no,
217 char *old_line,
218 int new_line_no,
219 char *new_line, int individual_chars)
220{
221 char *lcs = NULL;
222
223 if (old_line)
224 old_line = replace_tabs(old_line + 1);
225 if (new_line)
226 new_line = replace_tabs(new_line + 1);
227 if (individual_chars && old_line && new_line)
228 lcs = longest_common_subsequence(old_line, new_line);
229 html("<tr>\n");
230 if (old_line_no > 0) {
231 struct diff_filespec *old_file = cgit_get_current_old_file();
232 char *lineno_str = fmt("n%d", old_line_no);
233 char *id_str = fmt("%s#%s", is_null_sha1(old_file->sha1)?"HEAD":sha1_to_hex(old_rev_sha1), lineno_str);
234 html("<td class='lineno'><a class='no' href='");
235 html(cgit_fileurl(ctx.repo->url, "tree", old_file->path, id_str));
236 htmlf("' id='%s' name='%s'>%s</a>", lineno_str, lineno_str, lineno_str + 1);
237 html("</td>");
238 htmlf("<td class='%s'>", class);
239 } else if (old_line)
240 htmlf("<td class='lineno'></td><td class='%s'>", class);
241 else
242 htmlf("<td class='lineno'></td><td class='%s_dark'>", class);
243 if (old_line) {
244 if (lcs)
245 print_part_with_lcs("del", old_line, lcs);
246 else
247 html_txt(old_line);
248 }
249
250 html("</td>\n");
251 if (new_line_no > 0) {
252 struct diff_filespec *new_file = cgit_get_current_new_file();
253 char *lineno_str = fmt("n%d", new_line_no);
254 char *id_str = fmt("%s#%s", is_null_sha1(new_file->sha1)?"HEAD":sha1_to_hex(new_rev_sha1), lineno_str);
255 html("<td class='lineno'><a class='no' href='");
256 html(cgit_fileurl(ctx.repo->url, "tree", new_file->path, id_str));
257 htmlf("' id='%s' name='%s'>%s</a>", lineno_str, lineno_str, lineno_str + 1);
258 html("</td>");
259 htmlf("<td class='%s'>", class);
260 } else if (new_line)
261 htmlf("<td class='lineno'></td><td class='%s'>", class);
262 else
263 htmlf("<td class='lineno'></td><td class='%s_dark'>", class);
264 if (new_line) {
265 if (lcs)
266 print_part_with_lcs("add", new_line, lcs);
267 else
268 html_txt(new_line);
269 }
270
271 html("</td></tr>");
272 if (lcs)
273 free(lcs);
274 if (new_line)
275 free(new_line);
276 if (old_line)
277 free(old_line);
278}
279
280static void print_deferred_old_lines()
281{
282 struct deferred_lines *iter_old, *tmp;
283 iter_old = deferred_old;
284 while (iter_old) {
285 print_ssdiff_line("del", iter_old->line_no,
286 iter_old->line, -1, NULL, 0);
287 tmp = iter_old->next;
288 free(iter_old);
289 iter_old = tmp;
290 }
291}
292
293static void print_deferred_new_lines()
294{
295 struct deferred_lines *iter_new, *tmp;
296 iter_new = deferred_new;
297 while (iter_new) {
298 print_ssdiff_line("add", -1, NULL,
299 iter_new->line_no, iter_new->line, 0);
300 tmp = iter_new->next;
301 free(iter_new);
302 iter_new = tmp;
303 }
304}
305
306static void print_deferred_changed_lines()
307{
308 struct deferred_lines *iter_old, *iter_new, *tmp;
309 int n_old_lines = calc_deferred_lines(deferred_old);
310 int n_new_lines = calc_deferred_lines(deferred_new);
311 int individual_chars = (n_old_lines == n_new_lines ? 1 : 0);
312
313 iter_old = deferred_old;
314 iter_new = deferred_new;
315 while (iter_old || iter_new) {
316 if (iter_old && iter_new)
317 print_ssdiff_line("changed", iter_old->line_no,
318 iter_old->line,
319 iter_new->line_no, iter_new->line,
320 individual_chars);
321 else if (iter_old)
322 print_ssdiff_line("changed", iter_old->line_no,
323 iter_old->line, -1, NULL, 0);
324 else if (iter_new)
325 print_ssdiff_line("changed", -1, NULL,
326 iter_new->line_no, iter_new->line, 0);
327 if (iter_old) {
328 tmp = iter_old->next;
329 free(iter_old);
330 iter_old = tmp;
331 }
332
333 if (iter_new) {
334 tmp = iter_new->next;
335 free(iter_new);
336 iter_new = tmp;
337 }
338 }
339}
340
341void cgit_ssdiff_print_deferred_lines()
342{
343 if (!deferred_old && !deferred_new)
344 return;
345 if (deferred_old && !deferred_new)
346 print_deferred_old_lines();
347 else if (!deferred_old && deferred_new)
348 print_deferred_new_lines();
349 else
350 print_deferred_changed_lines();
351 deferred_old = deferred_old_last = NULL;
352 deferred_new = deferred_new_last = NULL;
353}
354
355/*
356 * print a single line returned from xdiff
357 */
358void cgit_ssdiff_line_cb(char *line, int len)
359{
360 char c = line[len - 1];
361 line[len - 1] = '\0';
362 if (line[0] == '@') {
363 current_old_line = line_from_hunk(line, '-');
364 current_new_line = line_from_hunk(line, '+');
365 }
366
367 if (line[0] == ' ') {
368 if (deferred_old || deferred_new)
369 cgit_ssdiff_print_deferred_lines();
370 print_ssdiff_line("ctx", current_old_line, line,
371 current_new_line, line, 0);
372 current_old_line += 1;
373 current_new_line += 1;
374 } else if (line[0] == '+') {
375 deferred_new_add(line, current_new_line);
376 current_new_line += 1;
377 } else if (line[0] == '-') {
378 deferred_old_add(line, current_old_line);
379 current_old_line += 1;
380 } else if (line[0] == '@') {
381 html("<tr><td colspan='4' class='hunk'>");
382 html_txt(line);
383 html("</td></tr>");
384 } else {
385 html("<tr><td colspan='4' class='ctx'>");
386 html_txt(line);
387 html("</td></tr>");
388 }
389 line[len - 1] = c;
390}
391
392void cgit_ssdiff_header_begin()
393{
394 current_old_line = -1;
395 current_new_line = -1;
396 html("<tr><td class='space' colspan='4'><div></div></td></tr>");
397 html("<tr><td class='head' colspan='4'>");
398}
399
400void cgit_ssdiff_header_end()
401{
402 html("</td><tr>");
403}
404
405void cgit_ssdiff_footer()
406{
407 if (deferred_old || deferred_new)
408 cgit_ssdiff_print_deferred_lines();
409 html("<tr><td class='foot' colspan='4'></td></tr>");
410}