ui-ssdiff.c

   1 #include "cgit.h"
   2 #include "html.h"
   3 #include "ui-shared.h"
   4
   5 extern int use_ssdiff;
   6
   7 static int current_old_line, current_new_line;
   8
   9 struct deferred_lines {
  10         int line_no;
  11         char *line;
  12         struct deferred_lines *next;
  13 };
  14
  15 static struct deferred_lines *deferred_old, *deferred_old_last;
  16 static struct deferred_lines *deferred_new, *deferred_new_last;
  17
  18 static 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
  64 static 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
  85 static 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
 122 static 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
 133 static 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
 147 static 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
 161 static 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
 187 static 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
 239 static 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
 252 static 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
 265 static 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
 300 void 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  */
 317 void 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
 351 void 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
 359 void cgit_ssdiff_header_end()
 360 {
 361         html("</td><tr>");
 362 }
 363
 364 void 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 }