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