ui-ssdiff.c

   1 #include "cgit.h"
   2 #include "ui-ssdiff.h"
   3 #include "html.h"
   4 #include "ui-shared.h"
   5 #include "ui-diff.h"
   6
   7 extern int use_ssdiff;
   8
   9 static int current_old_line, current_new_line;
  10 static int **L = NULL;
  11
  12 struct deferred_lines {
  13         int line_no;
  14         char *line;
  15         struct deferred_lines *next;
  16 };
  17
  18 static struct deferred_lines *deferred_old, *deferred_old_last;
  19 static struct deferred_lines *deferred_new, *deferred_new_last;
  20
  21 static 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
  40 static 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
  92 static 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
 112 static 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
 154 static 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
 165 static 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
 179 static 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
 193 static 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
 221 static 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
 290 static 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
 303 static 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
 316 static 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
 351 void 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  */
 368 void 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
 402 void 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
 410 void cgit_ssdiff_header_end(void)
 411 {
 412         html("</td></tr>");
 413 }
 414
 415 void 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 }