ui-ssdiff.c (view raw)
1#include "cgit.h"
2#include "ui-ssdiff.h"
3#include "html.h"
4#include "ui-shared.h"
5#include "ui-diff.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(void)
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, res;
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 strlcpy(buf2, buf1, len + 1);
107 res = atoi(buf2);
108 free(buf2);
109 return res;
110}
111
112static char *replace_tabs(char *line)
113{
114 char *prev_buf = line;
115 char *cur_buf;
116 size_t linelen = strlen(line);
117 int n_tabs = 0;
118 int i;
119 char *result;
120 size_t result_len;
121
122 if (linelen == 0) {
123 result = xmalloc(1);
124 result[0] = '\0';
125 return result;
126 }
127
128 for (i = 0; i < linelen; i++) {
129 if (line[i] == '\t')
130 n_tabs += 1;
131 }
132 result_len = linelen + n_tabs * 8;
133 result = xmalloc(result_len + 1);
134 result[0] = '\0';
135
136 for (;;) {
137 cur_buf = strchr(prev_buf, '\t');
138 if (!cur_buf) {
139 linelen = strlen(result);
140 strlcpy(&result[linelen], prev_buf, result_len - linelen + 1);
141 break;
142 } else {
143 linelen = strlen(result);
144 strlcpy(&result[linelen], prev_buf, cur_buf - prev_buf + 1);
145 linelen = strlen(result);
146 memset(&result[linelen], ' ', 8 - (linelen % 8));
147 result[linelen + 8 - (linelen % 8)] = '\0';
148 }
149 prev_buf = cur_buf + 1;
150 }
151 return result;
152}
153
154static int calc_deferred_lines(struct deferred_lines *start)
155{
156 struct deferred_lines *item = start;
157 int result = 0;
158 while (item) {
159 result += 1;
160 item = item->next;
161 }
162 return result;
163}
164
165static void deferred_old_add(char *line, int line_no)
166{
167 struct deferred_lines *item = xmalloc(sizeof(struct deferred_lines));
168 item->line = xstrdup(line);
169 item->line_no = line_no;
170 item->next = NULL;
171 if (deferred_old) {
172 deferred_old_last->next = item;
173 deferred_old_last = item;
174 } else {
175 deferred_old = deferred_old_last = item;
176 }
177}
178
179static void deferred_new_add(char *line, int line_no)
180{
181 struct deferred_lines *item = xmalloc(sizeof(struct deferred_lines));
182 item->line = xstrdup(line);
183 item->line_no = line_no;
184 item->next = NULL;
185 if (deferred_new) {
186 deferred_new_last->next = item;
187 deferred_new_last = item;
188 } else {
189 deferred_new = deferred_new_last = item;
190 }
191}
192
193static void print_part_with_lcs(char *class, char *line, char *lcs)
194{
195 int line_len = strlen(line);
196 int i, j;
197 char c[2] = " ";
198 int same = 1;
199
200 j = 0;
201 for (i = 0; i < line_len; i++) {
202 c[0] = line[i];
203 if (same) {
204 if (line[i] == lcs[j])
205 j += 1;
206 else {
207 same = 0;
208 htmlf("<span class='%s'>", class);
209 }
210 } else if (line[i] == lcs[j]) {
211 same = 1;
212 html("</span>");
213 j += 1;
214 }
215 html_txt(c);
216 }
217 if (!same)
218 html("</span>");
219}
220
221static void print_ssdiff_line(char *class,
222 int old_line_no,
223 char *old_line,
224 int new_line_no,
225 char *new_line, int individual_chars)
226{
227 char *lcs = NULL;
228
229 if (old_line)
230 old_line = replace_tabs(old_line + 1);
231 if (new_line)
232 new_line = replace_tabs(new_line + 1);
233 if (individual_chars && old_line && new_line)
234 lcs = longest_common_subsequence(old_line, new_line);
235 html("<tr>\n");
236 if (old_line_no > 0) {
237 struct diff_filespec *old_file = cgit_get_current_old_file();
238 char *lineno_str = fmt("n%d", old_line_no);
239 char *id_str = fmt("id=%s#%s", is_null_oid(&old_file->oid)?"HEAD":oid_to_hex(old_rev_oid), lineno_str);
240 char *fileurl = cgit_fileurl(ctx.repo->url, "tree", old_file->path, id_str);
241 html("<td class='lineno'><a href='");
242 html(fileurl);
243 htmlf("'>%s</a>", lineno_str + 1);
244 html("</td>");
245 htmlf("<td class='%s'>", class);
246 free(fileurl);
247 } else if (old_line)
248 htmlf("<td class='lineno'></td><td class='%s'>", class);
249 else
250 htmlf("<td class='lineno'></td><td class='%s_dark'>", class);
251 if (old_line) {
252 if (lcs)
253 print_part_with_lcs("del", old_line, lcs);
254 else
255 html_txt(old_line);
256 }
257
258 html("</td>\n");
259 if (new_line_no > 0) {
260 struct diff_filespec *new_file = cgit_get_current_new_file();
261 char *lineno_str = fmt("n%d", new_line_no);
262 char *id_str = fmt("id=%s#%s", is_null_oid(&new_file->oid)?"HEAD":oid_to_hex(new_rev_oid), lineno_str);
263 char *fileurl = cgit_fileurl(ctx.repo->url, "tree", new_file->path, id_str);
264 html("<td class='lineno'><a href='");
265 html(fileurl);
266 htmlf("'>%s</a>", lineno_str + 1);
267 html("</td>");
268 htmlf("<td class='%s'>", class);
269 free(fileurl);
270 } else if (new_line)
271 htmlf("<td class='lineno'></td><td class='%s'>", class);
272 else
273 htmlf("<td class='lineno'></td><td class='%s_dark'>", class);
274 if (new_line) {
275 if (lcs)
276 print_part_with_lcs("add", new_line, lcs);
277 else
278 html_txt(new_line);
279 }
280
281 html("</td></tr>");
282 if (lcs)
283 free(lcs);
284 if (new_line)
285 free(new_line);
286 if (old_line)
287 free(old_line);
288}
289
290static void print_deferred_old_lines(void)
291{
292 struct deferred_lines *iter_old, *tmp;
293 iter_old = deferred_old;
294 while (iter_old) {
295 print_ssdiff_line("del", iter_old->line_no,
296 iter_old->line, -1, NULL, 0);
297 tmp = iter_old->next;
298 free(iter_old);
299 iter_old = tmp;
300 }
301}
302
303static void print_deferred_new_lines(void)
304{
305 struct deferred_lines *iter_new, *tmp;
306 iter_new = deferred_new;
307 while (iter_new) {
308 print_ssdiff_line("add", -1, NULL,
309 iter_new->line_no, iter_new->line, 0);
310 tmp = iter_new->next;
311 free(iter_new);
312 iter_new = tmp;
313 }
314}
315
316static void print_deferred_changed_lines(void)
317{
318 struct deferred_lines *iter_old, *iter_new, *tmp;
319 int n_old_lines = calc_deferred_lines(deferred_old);
320 int n_new_lines = calc_deferred_lines(deferred_new);
321 int individual_chars = (n_old_lines == n_new_lines ? 1 : 0);
322
323 iter_old = deferred_old;
324 iter_new = deferred_new;
325 while (iter_old || iter_new) {
326 if (iter_old && iter_new)
327 print_ssdiff_line("changed", iter_old->line_no,
328 iter_old->line,
329 iter_new->line_no, iter_new->line,
330 individual_chars);
331 else if (iter_old)
332 print_ssdiff_line("changed", iter_old->line_no,
333 iter_old->line, -1, NULL, 0);
334 else if (iter_new)
335 print_ssdiff_line("changed", -1, NULL,
336 iter_new->line_no, iter_new->line, 0);
337 if (iter_old) {
338 tmp = iter_old->next;
339 free(iter_old);
340 iter_old = tmp;
341 }
342
343 if (iter_new) {
344 tmp = iter_new->next;
345 free(iter_new);
346 iter_new = tmp;
347 }
348 }
349}
350
351void cgit_ssdiff_print_deferred_lines(void)
352{
353 if (!deferred_old && !deferred_new)
354 return;
355 if (deferred_old && !deferred_new)
356 print_deferred_old_lines();
357 else if (!deferred_old && deferred_new)
358 print_deferred_new_lines();
359 else
360 print_deferred_changed_lines();
361 deferred_old = deferred_old_last = NULL;
362 deferred_new = deferred_new_last = NULL;
363}
364
365/*
366 * print a single line returned from xdiff
367 */
368void cgit_ssdiff_line_cb(char *line, int len)
369{
370 char c = line[len - 1];
371 line[len - 1] = '\0';
372 if (line[0] == '@') {
373 current_old_line = line_from_hunk(line, '-');
374 current_new_line = line_from_hunk(line, '+');
375 }
376
377 if (line[0] == ' ') {
378 if (deferred_old || deferred_new)
379 cgit_ssdiff_print_deferred_lines();
380 print_ssdiff_line("ctx", current_old_line, line,
381 current_new_line, line, 0);
382 current_old_line += 1;
383 current_new_line += 1;
384 } else if (line[0] == '+') {
385 deferred_new_add(line, current_new_line);
386 current_new_line += 1;
387 } else if (line[0] == '-') {
388 deferred_old_add(line, current_old_line);
389 current_old_line += 1;
390 } else if (line[0] == '@') {
391 html("<tr><td colspan='4' class='hunk'>");
392 html_txt(line);
393 html("</td></tr>");
394 } else {
395 html("<tr><td colspan='4' class='ctx'>");
396 html_txt(line);
397 html("</td></tr>");
398 }
399 line[len - 1] = c;
400}
401
402void cgit_ssdiff_header_begin(void)
403{
404 current_old_line = -1;
405 current_new_line = -1;
406 html("<tr><td class='space' colspan='4'><div></div></td></tr>");
407 html("<tr><td class='head' colspan='4'>");
408}
409
410void cgit_ssdiff_header_end(void)
411{
412 html("</td></tr>");
413}
414
415void cgit_ssdiff_footer(void)
416{
417 if (deferred_old || deferred_new)
418 cgit_ssdiff_print_deferred_lines();
419 html("<tr><td class='foot' colspan='4'></td></tr>");
420}