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