9 static int current_old_line
, current_new_line
;
10 static int **L
= NULL
;
12 struct deferred_lines
{
15 struct deferred_lines
*next
;
18 static struct deferred_lines
*deferred_old
, *deferred_old_last
;
19 static struct deferred_lines
*deferred_new
, *deferred_new_last
;
21 static void create_or_reset_lcs_table()
26 memset(*L
, 0, sizeof(int) * MAX_SSDIFF_SIZE
);
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));
35 for (i
= 1; i
< MAX_SSDIFF_M
; i
++) {
36 L
[i
] = *L
+ i
* MAX_SSDIFF_N
;
40 static char *longest_common_subsequence(char *A
, char *B
)
49 // We bail if the lines are too long
50 if (m
>= MAX_SSDIFF_M
|| n
>= MAX_SSDIFF_N
)
53 create_or_reset_lcs_table();
55 for (i
= m
; i
>= 0; i
--) {
56 for (j
= n
; j
>= 0; j
--) {
57 if (A
[i
] == '\0' || B
[j
] == '\0') {
59 } else if (A
[i
] == B
[j
]) {
60 L
[i
][j
] = 1 + L
[i
+ 1][j
+ 1];
64 L
[i
][j
] = (tmp1
> tmp2
? tmp1
: tmp2
);
70 result
= xmalloc(lcs_length
+ 2);
71 memset(result
, 0, sizeof(*result
) * (lcs_length
+ 2));
76 while (i
< m
&& j
< n
) {
82 } else if (L
[i
+ 1][j
] >= L
[i
][j
+ 1]) {
92 static int line_from_hunk(char *line
, char type
)
97 buf1
= strchr(line
, type
);
101 buf2
= strchr(buf1
, ',');
105 buf2
= xmalloc(len
+ 1);
106 strncpy(buf2
, buf1
, len
);
108 int res
= atoi(buf2
);
113 static char *replace_tabs(char *line
)
115 char *prev_buf
= line
;
117 int linelen
= strlen(line
);
129 for (i
= 0; i
< linelen
; i
++)
132 result
= xmalloc(linelen
+ n_tabs
* 8 + 1);
136 cur_buf
= strchr(prev_buf
, '\t');
138 strcat(result
, prev_buf
);
141 strncat(result
, prev_buf
, cur_buf
- prev_buf
);
142 strncat(result
, spaces
, 8 - (strlen(result
) % 8));
144 prev_buf
= cur_buf
+ 1;
149 static int calc_deferred_lines(struct deferred_lines
*start
)
151 struct deferred_lines
*item
= start
;
160 static void deferred_old_add(char *line
, int line_no
)
162 struct deferred_lines
*item
= xmalloc(sizeof(struct deferred_lines
));
163 item
->line
= xstrdup(line
);
164 item
->line_no
= line_no
;
167 deferred_old_last
->next
= item
;
168 deferred_old_last
= item
;
170 deferred_old
= deferred_old_last
= item
;
174 static void deferred_new_add(char *line
, int line_no
)
176 struct deferred_lines
*item
= xmalloc(sizeof(struct deferred_lines
));
177 item
->line
= xstrdup(line
);
178 item
->line_no
= line_no
;
181 deferred_new_last
->next
= item
;
182 deferred_new_last
= item
;
184 deferred_new
= deferred_new_last
= item
;
188 static void print_part_with_lcs(char *class, char *line
, char *lcs
)
190 int line_len
= strlen(line
);
196 for (i
= 0; i
< line_len
; i
++) {
199 if (line
[i
] == lcs
[j
])
203 htmlf("<span class='%s'>", class);
205 } else if (line
[i
] == lcs
[j
]) {
214 static void print_ssdiff_line(char *class,
218 char *new_line
, int individual_chars
)
223 old_line
= replace_tabs(old_line
+ 1);
225 new_line
= replace_tabs(new_line
+ 1);
226 if (individual_chars
&& old_line
&& new_line
)
227 lcs
= longest_common_subsequence(old_line
, new_line
);
229 if (old_line_no
> 0) {
230 struct diff_filespec
*old_file
= cgit_get_current_old_file();
231 char *lineno_str
= fmt("n%d", old_line_no
);
232 char *id_str
= fmt("id=%s#%s", is_null_sha1(old_file
->sha1
)?"HEAD":sha1_to_hex(old_rev_sha1
), lineno_str
);
233 html("<td class='lineno'><a href='");
234 html(cgit_fileurl(ctx
.repo
->url
, "tree", old_file
->path
, id_str
));
235 htmlf("' id='%s'>%s</a>", lineno_str
, lineno_str
+ 1);
237 htmlf("<td class='%s'>", class);
239 htmlf("<td class='lineno'></td><td class='%s'>", class);
241 htmlf("<td class='lineno'></td><td class='%s_dark'>", class);
244 print_part_with_lcs("del", old_line
, lcs
);
250 if (new_line_no
> 0) {
251 struct diff_filespec
*new_file
= cgit_get_current_new_file();
252 char *lineno_str
= fmt("n%d", new_line_no
);
253 char *id_str
= fmt("id=%s#%s", is_null_sha1(new_file
->sha1
)?"HEAD":sha1_to_hex(new_rev_sha1
), lineno_str
);
254 html("<td class='lineno'><a href='");
255 html(cgit_fileurl(ctx
.repo
->url
, "tree", new_file
->path
, id_str
));
256 htmlf("' id='%s'>%s</a>", lineno_str
, lineno_str
+ 1);
258 htmlf("<td class='%s'>", class);
260 htmlf("<td class='lineno'></td><td class='%s'>", class);
262 htmlf("<td class='lineno'></td><td class='%s_dark'>", class);
265 print_part_with_lcs("add", new_line
, lcs
);
279 static void print_deferred_old_lines()
281 struct deferred_lines
*iter_old
, *tmp
;
282 iter_old
= deferred_old
;
284 print_ssdiff_line("del", iter_old
->line_no
,
285 iter_old
->line
, -1, NULL
, 0);
286 tmp
= iter_old
->next
;
292 static void print_deferred_new_lines()
294 struct deferred_lines
*iter_new
, *tmp
;
295 iter_new
= deferred_new
;
297 print_ssdiff_line("add", -1, NULL
,
298 iter_new
->line_no
, iter_new
->line
, 0);
299 tmp
= iter_new
->next
;
305 static void print_deferred_changed_lines()
307 struct deferred_lines
*iter_old
, *iter_new
, *tmp
;
308 int n_old_lines
= calc_deferred_lines(deferred_old
);
309 int n_new_lines
= calc_deferred_lines(deferred_new
);
310 int individual_chars
= (n_old_lines
== n_new_lines
? 1 : 0);
312 iter_old
= deferred_old
;
313 iter_new
= deferred_new
;
314 while (iter_old
|| iter_new
) {
315 if (iter_old
&& iter_new
)
316 print_ssdiff_line("changed", iter_old
->line_no
,
318 iter_new
->line_no
, iter_new
->line
,
321 print_ssdiff_line("changed", iter_old
->line_no
,
322 iter_old
->line
, -1, NULL
, 0);
324 print_ssdiff_line("changed", -1, NULL
,
325 iter_new
->line_no
, iter_new
->line
, 0);
327 tmp
= iter_old
->next
;
333 tmp
= iter_new
->next
;
340 void cgit_ssdiff_print_deferred_lines()
342 if (!deferred_old
&& !deferred_new
)
344 if (deferred_old
&& !deferred_new
)
345 print_deferred_old_lines();
346 else if (!deferred_old
&& deferred_new
)
347 print_deferred_new_lines();
349 print_deferred_changed_lines();
350 deferred_old
= deferred_old_last
= NULL
;
351 deferred_new
= deferred_new_last
= NULL
;
355 * print a single line returned from xdiff
357 void cgit_ssdiff_line_cb(char *line
, int len
)
359 char c
= line
[len
- 1];
360 line
[len
- 1] = '\0';
361 if (line
[0] == '@') {
362 current_old_line
= line_from_hunk(line
, '-');
363 current_new_line
= line_from_hunk(line
, '+');
366 if (line
[0] == ' ') {
367 if (deferred_old
|| deferred_new
)
368 cgit_ssdiff_print_deferred_lines();
369 print_ssdiff_line("ctx", current_old_line
, line
,
370 current_new_line
, line
, 0);
371 current_old_line
+= 1;
372 current_new_line
+= 1;
373 } else if (line
[0] == '+') {
374 deferred_new_add(line
, current_new_line
);
375 current_new_line
+= 1;
376 } else if (line
[0] == '-') {
377 deferred_old_add(line
, current_old_line
);
378 current_old_line
+= 1;
379 } else if (line
[0] == '@') {
380 html("<tr><td colspan='4' class='hunk'>");
384 html("<tr><td colspan='4' class='ctx'>");
391 void cgit_ssdiff_header_begin()
393 current_old_line
= -1;
394 current_new_line
= -1;
395 html("<tr><td class='space' colspan='4'><div></div></td></tr>");
396 html("<tr><td class='head' colspan='4'>");
399 void cgit_ssdiff_header_end()
404 void cgit_ssdiff_footer()
406 if (deferred_old
|| deferred_new
)
407 cgit_ssdiff_print_deferred_lines();
408 html("<tr><td class='foot' colspan='4'></td></tr>");