ui-ssdiff.c (view raw)
1#include "cgit.h"
2#include "html.h"
3#include "ui-shared.h"
4
5extern int use_ssdiff;
6
7static int current_old_line, current_new_line;
8
9struct deferred_lines {
10 int line_no;
11 char *line;
12 struct deferred_lines *next;
13};
14
15static struct deferred_lines *deferred_old, *deferred_old_last;
16static struct deferred_lines *deferred_new, *deferred_new_last;
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
64static int line_from_hunk(char *line, char type)
65{
66 char *buf1, *buf2;
67 int len;
68
69 buf1 = strchr(line, type);
70 if (buf1 == NULL)
71 return 0;
72 buf1 += 1;
73 buf2 = strchr(buf1, ',');
74 if (buf2 == NULL)
75 return 0;
76 len = buf2 - buf1;
77 buf2 = xmalloc(len + 1);
78 strncpy(buf2, buf1, len);
79 buf2[len] = '\0';
80 int res = atoi(buf2);
81 free(buf2);
82 return res;
83}
84
85static char *replace_tabs(char *line)
86{
87 char *prev_buf = line;
88 char *cur_buf;
89 int linelen = strlen(line);
90 int n_tabs = 0;
91 int i;
92 char *result;
93 char *spaces = " ";
94
95 if (linelen == 0) {
96 result = xmalloc(1);
97 result[0] = '\0';
98 return result;
99 }
100
101 for (i = 0; i < linelen; i++)
102 if (line[i] == '\t')
103 n_tabs += 1;
104 result = xmalloc(linelen + n_tabs * 8 + 1);
105 result[0] = '\0';
106
107 while (1) {
108 cur_buf = strchr(prev_buf, '\t');
109 if (!cur_buf) {
110 strcat(result, prev_buf);
111 break;
112 } else {
113 strcat(result, " ");
114 strncat(result, spaces, 8 - (strlen(result) % 8));
115 strncat(result, prev_buf, cur_buf - prev_buf);
116 }
117 prev_buf = cur_buf + 1;
118 }
119 return result;
120}
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
133static void deferred_old_add(char *line, int line_no)
134{
135 struct deferred_lines *item = xmalloc(sizeof(struct deferred_lines));
136 item->line = xstrdup(line);
137 item->line_no = line_no;
138 item->next = NULL;
139 if (deferred_old) {
140 deferred_old_last->next = item;
141 deferred_old_last = item;
142 } else {
143 deferred_old = deferred_old_last = item;
144 }
145}
146
147static void deferred_new_add(char *line, int line_no)
148{
149 struct deferred_lines *item = xmalloc(sizeof(struct deferred_lines));
150 item->line = xstrdup(line);
151 item->line_no = line_no;
152 item->next = NULL;
153 if (deferred_new) {
154 deferred_new_last->next = item;
155 deferred_new_last = item;
156 } else {
157 deferred_new = deferred_new_last = item;
158 }
159}
160
161static void print_part_with_lcs(char *class, char *line, char *lcs)
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)
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);
200 html("<tr>");
201 if (old_line_no > 0)
202 htmlf("<td class='lineno'>%d</td><td class='%s'>",
203 old_line_no, class);
204 else if (old_line)
205 htmlf("<td class='lineno'></td><td class='%s'>", class);
206 else
207 htmlf("<td class='lineno'></td><td class='%s_dark'>", class);
208 if (old_line) {
209 if (lcs)
210 print_part_with_lcs("del", old_line, lcs);
211 else
212 html_txt(old_line);
213 }
214
215 html("</td>");
216 if (new_line_no > 0)
217 htmlf("<td class='lineno'>%d</td><td class='%s'>",
218 new_line_no, class);
219 else if (new_line)
220 htmlf("<td class='lineno'></td><td class='%s'>", class);
221 else
222 htmlf("<td class='lineno'></td><td class='%s_dark'>", class);
223 if (new_line) {
224 if (lcs)
225 print_part_with_lcs("add", new_line, lcs);
226 else
227 html_txt(new_line);
228 }
229
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);
237}
238
239static void print_deferred_old_lines()
240{
241 struct deferred_lines *iter_old, *tmp;
242 iter_old = deferred_old;
243 while (iter_old) {
244 print_ssdiff_line("del", iter_old->line_no,
245 iter_old->line, -1, NULL, 0);
246 tmp = iter_old->next;
247 free(iter_old);
248 iter_old = tmp;
249 }
250}
251
252static void print_deferred_new_lines()
253{
254 struct deferred_lines *iter_new, *tmp;
255 iter_new = deferred_new;
256 while (iter_new) {
257 print_ssdiff_line("add", -1, NULL,
258 iter_new->line_no, iter_new->line, 0);
259 tmp = iter_new->next;
260 free(iter_new);
261 iter_new = tmp;
262 }
263}
264
265static void print_deferred_changed_lines()
266{
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);
271
272 iter_old = deferred_old;
273 iter_new = deferred_new;
274 while (iter_old || iter_new) {
275 if (iter_old && iter_new)
276 print_ssdiff_line("changed", iter_old->line_no,
277 iter_old->line,
278 iter_new->line_no, iter_new->line,
279 individual_chars);
280 else if (iter_old)
281 print_ssdiff_line("changed", iter_old->line_no,
282 iter_old->line, -1, NULL, 0);
283 else if (iter_new)
284 print_ssdiff_line("changed", -1, NULL,
285 iter_new->line_no, iter_new->line, 0);
286 if (iter_old) {
287 tmp = iter_old->next;
288 free(iter_old);
289 iter_old = tmp;
290 }
291
292 if (iter_new) {
293 tmp = iter_new->next;
294 free(iter_new);
295 iter_new = tmp;
296 }
297 }
298}
299
300void cgit_ssdiff_print_deferred_lines()
301{
302 if (!deferred_old && !deferred_new)
303 return;
304 if (deferred_old && !deferred_new)
305 print_deferred_old_lines();
306 else if (!deferred_old && deferred_new)
307 print_deferred_new_lines();
308 else
309 print_deferred_changed_lines();
310 deferred_old = deferred_old_last = NULL;
311 deferred_new = deferred_new_last = NULL;
312}
313
314/*
315 * print a single line returned from xdiff
316 */
317void cgit_ssdiff_line_cb(char *line, int len)
318{
319 char c = line[len - 1];
320 line[len - 1] = '\0';
321 if (line[0] == '@') {
322 current_old_line = line_from_hunk(line, '-');
323 current_new_line = line_from_hunk(line, '+');
324 }
325
326 if (line[0] == ' ') {
327 if (deferred_old || deferred_new)
328 cgit_ssdiff_print_deferred_lines();
329 print_ssdiff_line("ctx", current_old_line, line,
330 current_new_line, line, 0);
331 current_old_line += 1;
332 current_new_line += 1;
333 } else if (line[0] == '+') {
334 deferred_new_add(line, current_new_line);
335 current_new_line += 1;
336 } else if (line[0] == '-') {
337 deferred_old_add(line, current_old_line);
338 current_old_line += 1;
339 } else if (line[0] == '@') {
340 html("<tr><td colspan='4' class='hunk'>");
341 html_txt(line);
342 html("</td></tr>");
343 } else {
344 html("<tr><td colspan='4' class='ctx'>");
345 html_txt(line);
346 html("</td></tr>");
347 }
348 line[len - 1] = c;
349}
350
351void cgit_ssdiff_header_begin()
352{
353 current_old_line = -1;
354 current_new_line = -1;
355 html("<tr><td class='space' colspan='4'><div></div></td></tr>");
356 html("<tr><td class='head' colspan='4'>");
357}
358
359void cgit_ssdiff_header_end()
360{
361 html("</td><tr>");
362}
363
364void cgit_ssdiff_footer()
365{
366 if (deferred_old || deferred_new)
367 cgit_ssdiff_print_deferred_lines();
368 html("<tr><td class='foot' colspan='4'></td></tr>");
369}