ui-ssdiff.c

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