ui-ssdiff.c

   1 #include "cgit.h"
   2 #include "html.h"
   3 #include "ui-shared.h"
   4 #include "ui-diff.h"
   5
   6 extern int use_ssdiff;
   7
   8 static int current_old_line, current_new_line;
   9
  10 struct deferred_lines {
  11         int line_no;
  12         char *line;
  13         struct deferred_lines *next;
  14 };
  15
  16 static struct deferred_lines *deferred_old, *deferred_old_last;
  17 static struct deferred_lines *deferred_new, *deferred_new_last;
  18
  19 static 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
  65 static 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
  86 static 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
 123 static 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
 134 static 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
 148 static 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
 162 static 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
 188 static 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
 253 static 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
 266 static 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
 279 static 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
 314 void 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  */
 331 void 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
 365 void 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
 373 void cgit_ssdiff_header_end()
 374 {
 375         html("</td><tr>");
 376 }
 377
 378 void 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 }