git.oblomov.eu Git - git/blob - diff.c

   1 /*
   2  * Copyright (C) 2005 Junio C Hamano
   3  */
   4 #include <sys/types.h>
   5 #include <sys/wait.h>
   6 #include <signal.h>
   7 #include "cache.h"
   8 #include "quote.h"
   9 #include "diff.h"
  10 #include "diffcore.h"
  11 #include "delta.h"
  12 #include "xdiff-interface.h"
  13
  14 static int use_size_cache;
  15
  16 static int diff_detect_rename_default = 0;
  17 static int diff_rename_limit_default = -1;
  18 static int diff_use_color_default = 0;
  19
  20 enum color_diff {
  21         DIFF_RESET = 0,
  22         DIFF_PLAIN = 1,
  23         DIFF_METAINFO = 2,
  24         DIFF_FRAGINFO = 3,
  25         DIFF_FILE_OLD = 4,
  26         DIFF_FILE_NEW = 5,
  27 };
  28
  29 /* "\033[1;38;5;2xx;48;5;2xxm\0" is 23 bytes */
  30 static char diff_colors[][24] = {
  31         "\033[m",       /* reset */
  32         "",             /* normal */
  33         "\033[1m",      /* bold */
  34         "\033[36m",     /* cyan */
  35         "\033[31m",     /* red */
  36         "\033[32m"      /* green */
  37 };
  38
  39 static int parse_diff_color_slot(const char *var, int ofs)
  40 {
  41         if (!strcasecmp(var+ofs, "plain"))
  42                 return DIFF_PLAIN;
  43         if (!strcasecmp(var+ofs, "meta"))
  44                 return DIFF_METAINFO;
  45         if (!strcasecmp(var+ofs, "frag"))
  46                 return DIFF_FRAGINFO;
  47         if (!strcasecmp(var+ofs, "old"))
  48                 return DIFF_FILE_OLD;
  49         if (!strcasecmp(var+ofs, "new"))
  50                 return DIFF_FILE_NEW;
  51         die("bad config variable '%s'", var);
  52 }
  53
  54 static int parse_color(const char *name, int len)
  55 {
  56         static const char * const color_names[] = {
  57                 "normal", "black", "red", "green", "yellow",
  58                 "blue", "magenta", "cyan", "white"
  59         };
  60         char *end;
  61         int i;
  62         for (i = 0; i < ARRAY_SIZE(color_names); i++) {
  63                 const char *str = color_names[i];
  64                 if (!strncasecmp(name, str, len) && !str[len])
  65                         return i - 1;
  66         }
  67         i = strtol(name, &end, 10);
  68         if (*name && !*end && i >= -1 && i <= 255)
  69                 return i;
  70         return -2;
  71 }
  72
  73 static int parse_attr(const char *name, int len)
  74 {
  75         static const int attr_values[] = { 1, 2, 4, 5, 7 };
  76         static const char * const attr_names[] = {
  77                 "bold", "dim", "ul", "blink", "reverse"
  78         };
  79         int i;
  80         for (i = 0; i < ARRAY_SIZE(attr_names); i++) {
  81                 const char *str = attr_names[i];
  82                 if (!strncasecmp(name, str, len) && !str[len])
  83                         return attr_values[i];
  84         }
  85         return -1;
  86 }
  87
  88 static void parse_diff_color_value(const char *value, const char *var, char *dst)
  89 {
  90         const char *ptr = value;
  91         int attr = -1;
  92         int fg = -2;
  93         int bg = -2;
  94
  95         if (!strcasecmp(value, "reset")) {
  96                 strcpy(dst, "\033[m");
  97                 return;
  98         }
  99
 100         /* [fg [bg]] [attr] */
 101         while (*ptr) {
 102                 const char *word = ptr;
 103                 int val, len = 0;
 104
 105                 while (word[len] && !isspace(word[len]))
 106                         len++;
 107
 108                 ptr = word + len;
 109                 while (*ptr && isspace(*ptr))
 110                         ptr++;
 111
 112                 val = parse_color(word, len);
 113                 if (val >= -1) {
 114                         if (fg == -2) {
 115                                 fg = val;
 116                                 continue;
 117                         }
 118                         if (bg == -2) {
 119                                 bg = val;
 120                                 continue;
 121                         }
 122                         goto bad;
 123                 }
 124                 val = parse_attr(word, len);
 125                 if (val < 0 || attr != -1)
 126                         goto bad;
 127                 attr = val;
 128         }
 129
 130         if (attr >= 0 || fg >= 0 || bg >= 0) {
 131                 int sep = 0;
 132
 133                 *dst++ = '\033';
 134                 *dst++ = '[';
 135                 if (attr >= 0) {
 136                         *dst++ = '0' + attr;
 137                         sep++;
 138                 }
 139                 if (fg >= 0) {
 140                         if (sep++)
 141                                 *dst++ = ';';
 142                         if (fg < 8) {
 143                                 *dst++ = '3';
 144                                 *dst++ = '0' + fg;
 145                         } else {
 146                                 dst += sprintf(dst, "38;5;%d", fg);
 147                         }
 148                 }
 149                 if (bg >= 0) {
 150                         if (sep++)
 151                                 *dst++ = ';';
 152                         if (bg < 8) {
 153                                 *dst++ = '4';
 154                                 *dst++ = '0' + bg;
 155                         } else {
 156                                 dst += sprintf(dst, "48;5;%d", bg);
 157                         }
 158                 }
 159                 *dst++ = 'm';
 160         }
 161         *dst = 0;
 162         return;
 163 bad:
 164         die("bad config value '%s' for variable '%s'", value, var);
 165 }
 166
 167 /*
 168  * These are to give UI layer defaults.
 169  * The core-level commands such as git-diff-files should
 170  * never be affected by the setting of diff.renames
 171  * the user happens to have in the configuration file.
 172  */
 173 int git_diff_ui_config(const char *var, const char *value)
 174 {
 175         if (!strcmp(var, "diff.renamelimit")) {
 176                 diff_rename_limit_default = git_config_int(var, value);
 177                 return 0;
 178         }
 179         if (!strcmp(var, "diff.color")) {
 180                 if (!value)
 181                         diff_use_color_default = 1; /* bool */
 182                 else if (!strcasecmp(value, "auto")) {
 183                         diff_use_color_default = 0;
 184                         if (isatty(1) || pager_in_use) {
 185                                 char *term = getenv("TERM");
 186                                 if (term && strcmp(term, "dumb"))
 187                                         diff_use_color_default = 1;
 188                         }
 189                 }
 190                 else if (!strcasecmp(value, "never"))
 191                         diff_use_color_default = 0;
 192                 else if (!strcasecmp(value, "always"))
 193                         diff_use_color_default = 1;
 194                 else
 195                         diff_use_color_default = git_config_bool(var, value);
 196                 return 0;
 197         }
 198         if (!strcmp(var, "diff.renames")) {
 199                 if (!value)
 200                         diff_detect_rename_default = DIFF_DETECT_RENAME;
 201                 else if (!strcasecmp(value, "copies") ||
 202                          !strcasecmp(value, "copy"))
 203                         diff_detect_rename_default = DIFF_DETECT_COPY;
 204                 else if (git_config_bool(var,value))
 205                         diff_detect_rename_default = DIFF_DETECT_RENAME;
 206                 return 0;
 207         }
 208         if (!strncmp(var, "diff.color.", 11)) {
 209                 int slot = parse_diff_color_slot(var, 11);
 210                 parse_diff_color_value(value, var, diff_colors[slot]);
 211                 return 0;
 212         }
 213         return git_default_config(var, value);
 214 }
 215
 216 static char *quote_one(const char *str)
 217 {
 218         int needlen;
 219         char *xp;
 220
 221         if (!str)
 222                 return NULL;
 223         needlen = quote_c_style(str, NULL, NULL, 0);
 224         if (!needlen)
 225                 return strdup(str);
 226         xp = xmalloc(needlen + 1);
 227         quote_c_style(str, xp, NULL, 0);
 228         return xp;
 229 }
 230
 231 static char *quote_two(const char *one, const char *two)
 232 {
 233         int need_one = quote_c_style(one, NULL, NULL, 1);
 234         int need_two = quote_c_style(two, NULL, NULL, 1);
 235         char *xp;
 236
 237         if (need_one + need_two) {
 238                 if (!need_one) need_one = strlen(one);
 239                 if (!need_two) need_one = strlen(two);
 240
 241                 xp = xmalloc(need_one + need_two + 3);
 242                 xp[0] = '"';
 243                 quote_c_style(one, xp + 1, NULL, 1);
 244                 quote_c_style(two, xp + need_one + 1, NULL, 1);
 245                 strcpy(xp + need_one + need_two + 1, "\"");
 246                 return xp;
 247         }
 248         need_one = strlen(one);
 249         need_two = strlen(two);
 250         xp = xmalloc(need_one + need_two + 1);
 251         strcpy(xp, one);
 252         strcpy(xp + need_one, two);
 253         return xp;
 254 }
 255
 256 static const char *external_diff(void)
 257 {
 258         static const char *external_diff_cmd = NULL;
 259         static int done_preparing = 0;
 260
 261         if (done_preparing)
 262                 return external_diff_cmd;
 263         external_diff_cmd = getenv("GIT_EXTERNAL_DIFF");
 264         done_preparing = 1;
 265         return external_diff_cmd;
 266 }
 267
 268 #define TEMPFILE_PATH_LEN               50
 269
 270 static struct diff_tempfile {
 271         const char *name; /* filename external diff should read from */
 272         char hex[41];
 273         char mode[10];
 274         char tmp_path[TEMPFILE_PATH_LEN];
 275 } diff_temp[2];
 276
 277 static int count_lines(const char *data, int size)
 278 {
 279         int count, ch, completely_empty = 1, nl_just_seen = 0;
 280         count = 0;
 281         while (0 < size--) {
 282                 ch = *data++;
 283                 if (ch == '\n') {
 284                         count++;
 285                         nl_just_seen = 1;
 286                         completely_empty = 0;
 287                 }
 288                 else {
 289                         nl_just_seen = 0;
 290                         completely_empty = 0;
 291                 }
 292         }
 293         if (completely_empty)
 294                 return 0;
 295         if (!nl_just_seen)
 296                 count++; /* no trailing newline */
 297         return count;
 298 }
 299
 300 static void print_line_count(int count)
 301 {
 302         switch (count) {
 303         case 0:
 304                 printf("0,0");
 305                 break;
 306         case 1:
 307                 printf("1");
 308                 break;
 309         default:
 310                 printf("1,%d", count);
 311                 break;
 312         }
 313 }
 314
 315 static void copy_file(int prefix, const char *data, int size)
 316 {
 317         int ch, nl_just_seen = 1;
 318         while (0 < size--) {
 319                 ch = *data++;
 320                 if (nl_just_seen)
 321                         putchar(prefix);
 322                 putchar(ch);
 323                 if (ch == '\n')
 324                         nl_just_seen = 1;
 325                 else
 326                         nl_just_seen = 0;
 327         }
 328         if (!nl_just_seen)
 329                 printf("\n\\ No newline at end of file\n");
 330 }
 331
 332 static void emit_rewrite_diff(const char *name_a,
 333                               const char *name_b,
 334                               struct diff_filespec *one,
 335                               struct diff_filespec *two)
 336 {
 337         int lc_a, lc_b;
 338         diff_populate_filespec(one, 0);
 339         diff_populate_filespec(two, 0);
 340         lc_a = count_lines(one->data, one->size);
 341         lc_b = count_lines(two->data, two->size);
 342         printf("--- %s\n+++ %s\n@@ -", name_a, name_b);
 343         print_line_count(lc_a);
 344         printf(" +");
 345         print_line_count(lc_b);
 346         printf(" @@\n");
 347         if (lc_a)
 348                 copy_file('-', one->data, one->size);
 349         if (lc_b)
 350                 copy_file('+', two->data, two->size);
 351 }
 352
 353 static int fill_mmfile(mmfile_t *mf, struct diff_filespec *one)
 354 {
 355         if (!DIFF_FILE_VALID(one)) {
 356                 mf->ptr = (char *)""; /* does not matter */
 357                 mf->size = 0;
 358                 return 0;
 359         }
 360         else if (diff_populate_filespec(one, 0))
 361                 return -1;
 362         mf->ptr = one->data;
 363         mf->size = one->size;
 364         return 0;
 365 }
 366
 367 struct emit_callback {
 368         struct xdiff_emit_state xm;
 369         int nparents, color_diff;
 370         const char **label_path;
 371 };
 372
 373 static inline const char *get_color(int diff_use_color, enum color_diff ix)
 374 {
 375         if (diff_use_color)
 376                 return diff_colors[ix];
 377         return "";
 378 }
 379
 380 static void fn_out_consume(void *priv, char *line, unsigned long len)
 381 {
 382         int i;
 383         struct emit_callback *ecbdata = priv;
 384         const char *set = get_color(ecbdata->color_diff, DIFF_METAINFO);
 385         const char *reset = get_color(ecbdata->color_diff, DIFF_RESET);
 386
 387         if (ecbdata->label_path[0]) {
 388                 printf("%s--- %s%s\n", set, ecbdata->label_path[0], reset);
 389                 printf("%s+++ %s%s\n", set, ecbdata->label_path[1], reset);
 390                 ecbdata->label_path[0] = ecbdata->label_path[1] = NULL;
 391         }
 392
 393         /* This is not really necessary for now because
 394          * this codepath only deals with two-way diffs.
 395          */
 396         for (i = 0; i < len && line[i] == '@'; i++)
 397                 ;
 398         if (2 <= i && i < len && line[i] == ' ') {
 399                 ecbdata->nparents = i - 1;
 400                 set = get_color(ecbdata->color_diff, DIFF_FRAGINFO);
 401         }
 402         else if (len < ecbdata->nparents)
 403                 set = reset;
 404         else {
 405                 int nparents = ecbdata->nparents;
 406                 int color = DIFF_PLAIN;
 407                 for (i = 0; i < nparents && len; i++) {
 408                         if (line[i] == '-')
 409                                 color = DIFF_FILE_OLD;
 410                         else if (line[i] == '+')
 411                                 color = DIFF_FILE_NEW;
 412                 }
 413                 set = get_color(ecbdata->color_diff, color);
 414         }
 415         if (len > 0 && line[len-1] == '\n')
 416                 len--;
 417         fputs (set, stdout);
 418         fwrite (line, len, 1, stdout);
 419         puts (reset);
 420 }
 421
 422 static char *pprint_rename(const char *a, const char *b)
 423 {
 424         const char *old = a;
 425         const char *new = b;
 426         char *name = NULL;
 427         int pfx_length, sfx_length;
 428         int len_a = strlen(a);
 429         int len_b = strlen(b);
 430
 431         /* Find common prefix */
 432         pfx_length = 0;
 433         while (*old && *new && *old == *new) {
 434                 if (*old == '/')
 435                         pfx_length = old - a + 1;
 436                 old++;
 437                 new++;
 438         }
 439
 440         /* Find common suffix */
 441         old = a + len_a;
 442         new = b + len_b;
 443         sfx_length = 0;
 444         while (a <= old && b <= new && *old == *new) {
 445                 if (*old == '/')
 446                         sfx_length = len_a - (old - a);
 447                 old--;
 448                 new--;
 449         }
 450
 451         /*
 452          * pfx{mid-a => mid-b}sfx
 453          * {pfx-a => pfx-b}sfx
 454          * pfx{sfx-a => sfx-b}
 455          * name-a => name-b
 456          */
 457         if (pfx_length + sfx_length) {
 458                 int a_midlen = len_a - pfx_length - sfx_length;
 459                 int b_midlen = len_b - pfx_length - sfx_length;
 460                 if (a_midlen < 0) a_midlen = 0;
 461                 if (b_midlen < 0) b_midlen = 0;
 462
 463                 name = xmalloc(pfx_length + a_midlen + b_midlen + sfx_length + 7);
 464                 sprintf(name, "%.*s{%.*s => %.*s}%s",
 465                         pfx_length, a,
 466                         a_midlen, a + pfx_length,
 467                         b_midlen, b + pfx_length,
 468                         a + len_a - sfx_length);
 469         }
 470         else {
 471                 name = xmalloc(len_a + len_b + 5);
 472                 sprintf(name, "%s => %s", a, b);
 473         }
 474         return name;
 475 }
 476
 477 struct diffstat_t {
 478         struct xdiff_emit_state xm;
 479
 480         int nr;
 481         int alloc;
 482         struct diffstat_file {
 483                 char *name;
 484                 unsigned is_unmerged:1;
 485                 unsigned is_binary:1;
 486                 unsigned is_renamed:1;
 487                 unsigned int added, deleted;
 488         } **files;
 489 };
 490
 491 static struct diffstat_file *diffstat_add(struct diffstat_t *diffstat,
 492                                           const char *name_a,
 493                                           const char *name_b)
 494 {
 495         struct diffstat_file *x;
 496         x = xcalloc(sizeof (*x), 1);
 497         if (diffstat->nr == diffstat->alloc) {
 498                 diffstat->alloc = alloc_nr(diffstat->alloc);
 499                 diffstat->files = xrealloc(diffstat->files,
 500                                 diffstat->alloc * sizeof(x));
 501         }
 502         diffstat->files[diffstat->nr++] = x;
 503         if (name_b) {
 504                 x->name = pprint_rename(name_a, name_b);
 505                 x->is_renamed = 1;
 506         }
 507         else
 508                 x->name = strdup(name_a);
 509         return x;
 510 }
 511
 512 static void diffstat_consume(void *priv, char *line, unsigned long len)
 513 {
 514         struct diffstat_t *diffstat = priv;
 515         struct diffstat_file *x = diffstat->files[diffstat->nr - 1];
 516
 517         if (line[0] == '+')
 518                 x->added++;
 519         else if (line[0] == '-')
 520                 x->deleted++;
 521 }
 522
 523 static const char pluses[] = "++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++";
 524 static const char minuses[]= "----------------------------------------------------------------------";
 525 const char mime_boundary_leader[] = "------------";
 526
 527 static void show_stats(struct diffstat_t* data)
 528 {
 529         int i, len, add, del, total, adds = 0, dels = 0;
 530         int max, max_change = 0, max_len = 0;
 531         int total_files = data->nr;
 532
 533         if (data->nr == 0)
 534                 return;
 535
 536         for (i = 0; i < data->nr; i++) {
 537                 struct diffstat_file *file = data->files[i];
 538
 539                 len = strlen(file->name);
 540                 if (max_len < len)
 541                         max_len = len;
 542
 543                 if (file->is_binary || file->is_unmerged)
 544                         continue;
 545                 if (max_change < file->added + file->deleted)
 546                         max_change = file->added + file->deleted;
 547         }
 548
 549         for (i = 0; i < data->nr; i++) {
 550                 const char *prefix = "";
 551                 char *name = data->files[i]->name;
 552                 int added = data->files[i]->added;
 553                 int deleted = data->files[i]->deleted;
 554
 555                 if (0 < (len = quote_c_style(name, NULL, NULL, 0))) {
 556                         char *qname = xmalloc(len + 1);
 557                         quote_c_style(name, qname, NULL, 0);
 558                         free(name);
 559                         data->files[i]->name = name = qname;
 560                 }
 561
 562                 /*
 563                  * "scale" the filename
 564                  */
 565                 len = strlen(name);
 566                 max = max_len;
 567                 if (max > 50)
 568                         max = 50;
 569                 if (len > max) {
 570                         char *slash;
 571                         prefix = "...";
 572                         max -= 3;
 573                         name += len - max;
 574                         slash = strchr(name, '/');
 575                         if (slash)
 576                                 name = slash;
 577                 }
 578                 len = max;
 579
 580                 /*
 581                  * scale the add/delete
 582                  */
 583                 max = max_change;
 584                 if (max + len > 70)
 585                         max = 70 - len;
 586
 587                 if (data->files[i]->is_binary) {
 588                         printf(" %s%-*s |  Bin\n", prefix, len, name);
 589                         goto free_diffstat_file;
 590                 }
 591                 else if (data->files[i]->is_unmerged) {
 592                         printf(" %s%-*s |  Unmerged\n", prefix, len, name);
 593                         goto free_diffstat_file;
 594                 }
 595                 else if (!data->files[i]->is_renamed &&
 596                          (added + deleted == 0)) {
 597                         total_files--;
 598                         goto free_diffstat_file;
 599                 }
 600
 601                 add = added;
 602                 del = deleted;
 603                 total = add + del;
 604                 adds += add;
 605                 dels += del;
 606
 607                 if (max_change > 0) {
 608                         total = (total * max + max_change / 2) / max_change;
 609                         add = (add * max + max_change / 2) / max_change;
 610                         del = total - add;
 611                 }
 612                 printf(" %s%-*s |%5d %.*s%.*s\n", prefix,
 613                                 len, name, added + deleted,
 614                                 add, pluses, del, minuses);
 615         free_diffstat_file:
 616                 free(data->files[i]->name);
 617                 free(data->files[i]);
 618         }
 619         free(data->files);
 620         printf(" %d files changed, %d insertions(+), %d deletions(-)\n",
 621                         total_files, adds, dels);
 622 }
 623
 624 struct checkdiff_t {
 625         struct xdiff_emit_state xm;
 626         const char *filename;
 627         int lineno;
 628 };
 629
 630 static void checkdiff_consume(void *priv, char *line, unsigned long len)
 631 {
 632         struct checkdiff_t *data = priv;
 633
 634         if (line[0] == '+') {
 635                 int i, spaces = 0;
 636
 637                 data->lineno++;
 638
 639                 /* check space before tab */
 640                 for (i = 1; i < len && (line[i] == ' ' || line[i] == '\t'); i++)
 641                         if (line[i] == ' ')
 642                                 spaces++;
 643                 if (line[i - 1] == '\t' && spaces)
 644                         printf("%s:%d: space before tab:%.*s\n",
 645                                 data->filename, data->lineno, (int)len, line);
 646
 647                 /* check white space at line end */
 648                 if (line[len - 1] == '\n')
 649                         len--;
 650                 if (isspace(line[len - 1]))
 651                         printf("%s:%d: white space at end: %.*s\n",
 652                                 data->filename, data->lineno, (int)len, line);
 653         } else if (line[0] == ' ')
 654                 data->lineno++;
 655         else if (line[0] == '@') {
 656                 char *plus = strchr(line, '+');
 657                 if (plus)
 658                         data->lineno = strtol(plus, NULL, 10);
 659                 else
 660                         die("invalid diff");
 661         }
 662 }
 663
 664 static unsigned char *deflate_it(char *data,
 665                                  unsigned long size,
 666                                  unsigned long *result_size)
 667 {
 668         int bound;
 669         unsigned char *deflated;
 670         z_stream stream;
 671
 672         memset(&stream, 0, sizeof(stream));
 673         deflateInit(&stream, zlib_compression_level);
 674         bound = deflateBound(&stream, size);
 675         deflated = xmalloc(bound);
 676         stream.next_out = deflated;
 677         stream.avail_out = bound;
 678
 679         stream.next_in = (unsigned char *)data;
 680         stream.avail_in = size;
 681         while (deflate(&stream, Z_FINISH) == Z_OK)
 682                 ; /* nothing */
 683         deflateEnd(&stream);
 684         *result_size = stream.total_out;
 685         return deflated;
 686 }
 687
 688 static void emit_binary_diff(mmfile_t *one, mmfile_t *two)
 689 {
 690         void *cp;
 691         void *delta;
 692         void *deflated;
 693         void *data;
 694         unsigned long orig_size;
 695         unsigned long delta_size;
 696         unsigned long deflate_size;
 697         unsigned long data_size;
 698
 699         printf("GIT binary patch\n");
 700         /* We could do deflated delta, or we could do just deflated two,
 701          * whichever is smaller.
 702          */
 703         delta = NULL;
 704         deflated = deflate_it(two->ptr, two->size, &deflate_size);
 705         if (one->size && two->size) {
 706                 delta = diff_delta(one->ptr, one->size,
 707                                    two->ptr, two->size,
 708                                    &delta_size, deflate_size);
 709                 if (delta) {
 710                         void *to_free = delta;
 711                         orig_size = delta_size;
 712                         delta = deflate_it(delta, delta_size, &delta_size);
 713                         free(to_free);
 714                 }
 715         }
 716
 717         if (delta && delta_size < deflate_size) {
 718                 printf("delta %lu\n", orig_size);
 719                 free(deflated);
 720                 data = delta;
 721                 data_size = delta_size;
 722         }
 723         else {
 724                 printf("literal %lu\n", two->size);
 725                 free(delta);
 726                 data = deflated;
 727                 data_size = deflate_size;
 728         }
 729
 730         /* emit data encoded in base85 */
 731         cp = data;
 732         while (data_size) {
 733                 int bytes = (52 < data_size) ? 52 : data_size;
 734                 char line[70];
 735                 data_size -= bytes;
 736                 if (bytes <= 26)
 737                         line[0] = bytes + 'A' - 1;
 738                 else
 739                         line[0] = bytes - 26 + 'a' - 1;
 740                 encode_85(line + 1, cp, bytes);
 741                 cp = (char *) cp + bytes;
 742                 puts(line);
 743         }
 744         printf("\n");
 745         free(data);
 746 }
 747
 748 #define FIRST_FEW_BYTES 8000
 749 static int mmfile_is_binary(mmfile_t *mf)
 750 {
 751         long sz = mf->size;
 752         if (FIRST_FEW_BYTES < sz)
 753                 sz = FIRST_FEW_BYTES;
 754         if (memchr(mf->ptr, 0, sz))
 755                 return 1;
 756         return 0;
 757 }
 758
 759 static void builtin_diff(const char *name_a,
 760                          const char *name_b,
 761                          struct diff_filespec *one,
 762                          struct diff_filespec *two,
 763                          const char *xfrm_msg,
 764                          struct diff_options *o,
 765                          int complete_rewrite)
 766 {
 767         mmfile_t mf1, mf2;
 768         const char *lbl[2];
 769         char *a_one, *b_two;
 770         const char *set = get_color(o->color_diff, DIFF_METAINFO);
 771         const char *reset = get_color(o->color_diff, DIFF_RESET);
 772
 773         a_one = quote_two("a/", name_a);
 774         b_two = quote_two("b/", name_b);
 775         lbl[0] = DIFF_FILE_VALID(one) ? a_one : "/dev/null";
 776         lbl[1] = DIFF_FILE_VALID(two) ? b_two : "/dev/null";
 777         printf("%sdiff --git %s %s%s\n", set, a_one, b_two, reset);
 778         if (lbl[0][0] == '/') {
 779                 /* /dev/null */
 780                 printf("%snew file mode %06o%s\n", set, two->mode, reset);
 781                 if (xfrm_msg && xfrm_msg[0])
 782                         printf("%s%s%s\n", set, xfrm_msg, reset);
 783         }
 784         else if (lbl[1][0] == '/') {
 785                 printf("%sdeleted file mode %06o%s\n", set, one->mode, reset);
 786                 if (xfrm_msg && xfrm_msg[0])
 787                         printf("%s%s%s\n", set, xfrm_msg, reset);
 788         }
 789         else {
 790                 if (one->mode != two->mode) {
 791                         printf("%sold mode %06o%s\n", set, one->mode, reset);
 792                         printf("%snew mode %06o%s\n", set, two->mode, reset);
 793                 }
 794                 if (xfrm_msg && xfrm_msg[0])
 795                         printf("%s%s%s\n", set, xfrm_msg, reset);
 796                 /*
 797                  * we do not run diff between different kind
 798                  * of objects.
 799                  */
 800                 if ((one->mode ^ two->mode) & S_IFMT)
 801                         goto free_ab_and_return;
 802                 if (complete_rewrite) {
 803                         emit_rewrite_diff(name_a, name_b, one, two);
 804                         goto free_ab_and_return;
 805                 }
 806         }
 807
 808         if (fill_mmfile(&mf1, one) < 0 || fill_mmfile(&mf2, two) < 0)
 809                 die("unable to read files to diff");
 810
 811         if (!o->text && (mmfile_is_binary(&mf1) || mmfile_is_binary(&mf2))) {
 812                 /* Quite common confusing case */
 813                 if (mf1.size == mf2.size &&
 814                     !memcmp(mf1.ptr, mf2.ptr, mf1.size))
 815                         goto free_ab_and_return;
 816                 if (o->binary)
 817                         emit_binary_diff(&mf1, &mf2);
 818                 else
 819                         printf("Binary files %s and %s differ\n",
 820                                lbl[0], lbl[1]);
 821         }
 822         else {
 823                 /* Crazy xdl interfaces.. */
 824                 const char *diffopts = getenv("GIT_DIFF_OPTS");
 825                 xpparam_t xpp;
 826                 xdemitconf_t xecfg;
 827                 xdemitcb_t ecb;
 828                 struct emit_callback ecbdata;
 829
 830                 memset(&ecbdata, 0, sizeof(ecbdata));
 831                 ecbdata.label_path = lbl;
 832                 ecbdata.color_diff = o->color_diff;
 833                 xpp.flags = XDF_NEED_MINIMAL | o->xdl_opts;
 834                 xecfg.ctxlen = o->context;
 835                 xecfg.flags = XDL_EMIT_FUNCNAMES;
 836                 if (!diffopts)
 837                         ;
 838                 else if (!strncmp(diffopts, "--unified=", 10))
 839                         xecfg.ctxlen = strtoul(diffopts + 10, NULL, 10);
 840                 else if (!strncmp(diffopts, "-u", 2))
 841                         xecfg.ctxlen = strtoul(diffopts + 2, NULL, 10);
 842                 ecb.outf = xdiff_outf;
 843                 ecb.priv = &ecbdata;
 844                 ecbdata.xm.consume = fn_out_consume;
 845                 xdl_diff(&mf1, &mf2, &xpp, &xecfg, &ecb);
 846         }
 847
 848  free_ab_and_return:
 849         free(a_one);
 850         free(b_two);
 851         return;
 852 }
 853
 854 static void builtin_diffstat(const char *name_a, const char *name_b,
 855                              struct diff_filespec *one,
 856                              struct diff_filespec *two,
 857                              struct diffstat_t *diffstat,
 858                              struct diff_options *o,
 859                              int complete_rewrite)
 860 {
 861         mmfile_t mf1, mf2;
 862         struct diffstat_file *data;
 863
 864         data = diffstat_add(diffstat, name_a, name_b);
 865
 866         if (!one || !two) {
 867                 data->is_unmerged = 1;
 868                 return;
 869         }
 870         if (complete_rewrite) {
 871                 diff_populate_filespec(one, 0);
 872                 diff_populate_filespec(two, 0);
 873                 data->deleted = count_lines(one->data, one->size);
 874                 data->added = count_lines(two->data, two->size);
 875                 return;
 876         }
 877         if (fill_mmfile(&mf1, one) < 0 || fill_mmfile(&mf2, two) < 0)
 878                 die("unable to read files to diff");
 879
 880         if (mmfile_is_binary(&mf1) || mmfile_is_binary(&mf2))
 881                 data->is_binary = 1;
 882         else {
 883                 /* Crazy xdl interfaces.. */
 884                 xpparam_t xpp;
 885                 xdemitconf_t xecfg;
 886                 xdemitcb_t ecb;
 887
 888                 xpp.flags = XDF_NEED_MINIMAL | o->xdl_opts;
 889                 xecfg.ctxlen = 0;
 890                 xecfg.flags = 0;
 891                 ecb.outf = xdiff_outf;
 892                 ecb.priv = diffstat;
 893                 xdl_diff(&mf1, &mf2, &xpp, &xecfg, &ecb);
 894         }
 895 }
 896
 897 static void builtin_checkdiff(const char *name_a, const char *name_b,
 898                              struct diff_filespec *one,
 899                              struct diff_filespec *two)
 900 {
 901         mmfile_t mf1, mf2;
 902         struct checkdiff_t data;
 903
 904         if (!two)
 905                 return;
 906
 907         memset(&data, 0, sizeof(data));
 908         data.xm.consume = checkdiff_consume;
 909         data.filename = name_b ? name_b : name_a;
 910         data.lineno = 0;
 911
 912         if (fill_mmfile(&mf1, one) < 0 || fill_mmfile(&mf2, two) < 0)
 913                 die("unable to read files to diff");
 914
 915         if (mmfile_is_binary(&mf2))
 916                 return;
 917         else {
 918                 /* Crazy xdl interfaces.. */
 919                 xpparam_t xpp;
 920                 xdemitconf_t xecfg;
 921                 xdemitcb_t ecb;
 922
 923                 xpp.flags = XDF_NEED_MINIMAL;
 924                 xecfg.ctxlen = 0;
 925                 xecfg.flags = 0;
 926                 ecb.outf = xdiff_outf;
 927                 ecb.priv = &data;
 928                 xdl_diff(&mf1, &mf2, &xpp, &xecfg, &ecb);
 929         }
 930 }
 931
 932 struct diff_filespec *alloc_filespec(const char *path)
 933 {
 934         int namelen = strlen(path);
 935         struct diff_filespec *spec = xmalloc(sizeof(*spec) + namelen + 1);
 936
 937         memset(spec, 0, sizeof(*spec));
 938         spec->path = (char *)(spec + 1);
 939         memcpy(spec->path, path, namelen+1);
 940         return spec;
 941 }
 942
 943 void fill_filespec(struct diff_filespec *spec, const unsigned char *sha1,
 944                    unsigned short mode)
 945 {
 946         if (mode) {
 947                 spec->mode = canon_mode(mode);
 948                 memcpy(spec->sha1, sha1, 20);
 949                 spec->sha1_valid = !!memcmp(sha1, null_sha1, 20);
 950         }
 951 }
 952
 953 /*
 954  * Given a name and sha1 pair, if the dircache tells us the file in
 955  * the work tree has that object contents, return true, so that
 956  * prepare_temp_file() does not have to inflate and extract.
 957  */
 958 static int work_tree_matches(const char *name, const unsigned char *sha1)
 959 {
 960         struct cache_entry *ce;
 961         struct stat st;
 962         int pos, len;
 963
 964         /* We do not read the cache ourselves here, because the
 965          * benchmark with my previous version that always reads cache
 966          * shows that it makes things worse for diff-tree comparing
 967          * two linux-2.6 kernel trees in an already checked out work
 968          * tree.  This is because most diff-tree comparisons deal with
 969          * only a small number of files, while reading the cache is
 970          * expensive for a large project, and its cost outweighs the
 971          * savings we get by not inflating the object to a temporary
 972          * file.  Practically, this code only helps when we are used
 973          * by diff-cache --cached, which does read the cache before
 974          * calling us.
 975          */
 976         if (!active_cache)
 977                 return 0;
 978
 979         len = strlen(name);
 980         pos = cache_name_pos(name, len);
 981         if (pos < 0)
 982                 return 0;
 983         ce = active_cache[pos];
 984         if ((lstat(name, &st) < 0) ||
 985             !S_ISREG(st.st_mode) || /* careful! */
 986             ce_match_stat(ce, &st, 0) ||
 987             memcmp(sha1, ce->sha1, 20))
 988                 return 0;
 989         /* we return 1 only when we can stat, it is a regular file,
 990          * stat information matches, and sha1 recorded in the cache
 991          * matches.  I.e. we know the file in the work tree really is
 992          * the same as the <name, sha1> pair.
 993          */
 994         return 1;
 995 }
 996
 997 static struct sha1_size_cache {
 998         unsigned char sha1[20];
 999         unsigned long size;
1000 } **sha1_size_cache;
1001 static int sha1_size_cache_nr, sha1_size_cache_alloc;
1002
1003 static struct sha1_size_cache *locate_size_cache(unsigned char *sha1,
1004                                                  int find_only,
1005                                                  unsigned long size)
1006 {
1007         int first, last;
1008         struct sha1_size_cache *e;
1009
1010         first = 0;
1011         last = sha1_size_cache_nr;
1012         while (last > first) {
1013                 int cmp, next = (last + first) >> 1;
1014                 e = sha1_size_cache[next];
1015                 cmp = memcmp(e->sha1, sha1, 20);
1016                 if (!cmp)
1017                         return e;
1018                 if (cmp < 0) {
1019                         last = next;
1020                         continue;
1021                 }
1022                 first = next+1;
1023         }
1024         /* not found */
1025         if (find_only)
1026                 return NULL;
1027         /* insert to make it at "first" */
1028         if (sha1_size_cache_alloc <= sha1_size_cache_nr) {
1029                 sha1_size_cache_alloc = alloc_nr(sha1_size_cache_alloc);
1030                 sha1_size_cache = xrealloc(sha1_size_cache,
1031                                            sha1_size_cache_alloc *
1032                                            sizeof(*sha1_size_cache));
1033         }
1034         sha1_size_cache_nr++;
1035         if (first < sha1_size_cache_nr)
1036                 memmove(sha1_size_cache + first + 1, sha1_size_cache + first,
1037                         (sha1_size_cache_nr - first - 1) *
1038                         sizeof(*sha1_size_cache));
1039         e = xmalloc(sizeof(struct sha1_size_cache));
1040         sha1_size_cache[first] = e;
1041         memcpy(e->sha1, sha1, 20);
1042         e->size = size;
1043         return e;
1044 }
1045
1046 /*
1047  * While doing rename detection and pickaxe operation, we may need to
1048  * grab the data for the blob (or file) for our own in-core comparison.
1049  * diff_filespec has data and size fields for this purpose.
1050  */
1051 int diff_populate_filespec(struct diff_filespec *s, int size_only)
1052 {
1053         int err = 0;
1054         if (!DIFF_FILE_VALID(s))
1055                 die("internal error: asking to populate invalid file.");
1056         if (S_ISDIR(s->mode))
1057                 return -1;
1058
1059         if (!use_size_cache)
1060                 size_only = 0;
1061
1062         if (s->data)
1063                 return err;
1064         if (!s->sha1_valid ||
1065             work_tree_matches(s->path, s->sha1)) {
1066                 struct stat st;
1067                 int fd;
1068                 if (lstat(s->path, &st) < 0) {
1069                         if (errno == ENOENT) {
1070                         err_empty:
1071                                 err = -1;
1072                         empty:
1073                                 s->data = (char *)"";
1074                                 s->size = 0;
1075                                 return err;
1076                         }
1077                 }
1078                 s->size = st.st_size;
1079                 if (!s->size)
1080                         goto empty;
1081                 if (size_only)
1082                         return 0;
1083                 if (S_ISLNK(st.st_mode)) {
1084                         int ret;
1085                         s->data = xmalloc(s->size);
1086                         s->should_free = 1;
1087                         ret = readlink(s->path, s->data, s->size);
1088                         if (ret < 0) {
1089                                 free(s->data);
1090                                 goto err_empty;
1091                         }
1092                         return 0;
1093                 }
1094                 fd = open(s->path, O_RDONLY);
1095                 if (fd < 0)
1096                         goto err_empty;
1097                 s->data = mmap(NULL, s->size, PROT_READ, MAP_PRIVATE, fd, 0);
1098                 close(fd);
1099                 if (s->data == MAP_FAILED)
1100                         goto err_empty;
1101                 s->should_munmap = 1;
1102         }
1103         else {
1104                 char type[20];
1105                 struct sha1_size_cache *e;
1106
1107                 if (size_only) {
1108                         e = locate_size_cache(s->sha1, 1, 0);
1109                         if (e) {
1110                                 s->size = e->size;
1111                                 return 0;
1112                         }
1113                         if (!sha1_object_info(s->sha1, type, &s->size))
1114                                 locate_size_cache(s->sha1, 0, s->size);
1115                 }
1116                 else {
1117                         s->data = read_sha1_file(s->sha1, type, &s->size);
1118                         s->should_free = 1;
1119                 }
1120         }
1121         return 0;
1122 }
1123
1124 void diff_free_filespec_data(struct diff_filespec *s)
1125 {
1126         if (s->should_free)
1127                 free(s->data);
1128         else if (s->should_munmap)
1129                 munmap(s->data, s->size);
1130         s->should_free = s->should_munmap = 0;
1131         s->data = NULL;
1132         free(s->cnt_data);
1133         s->cnt_data = NULL;
1134 }
1135
1136 static void prep_temp_blob(struct diff_tempfile *temp,
1137                            void *blob,
1138                            unsigned long size,
1139                            const unsigned char *sha1,
1140                            int mode)
1141 {
1142         int fd;
1143
1144         fd = git_mkstemp(temp->tmp_path, TEMPFILE_PATH_LEN, ".diff_XXXXXX");
1145         if (fd < 0)
1146                 die("unable to create temp-file");
1147         if (write(fd, blob, size) != size)
1148                 die("unable to write temp-file");
1149         close(fd);
1150         temp->name = temp->tmp_path;
1151         strcpy(temp->hex, sha1_to_hex(sha1));
1152         temp->hex[40] = 0;
1153         sprintf(temp->mode, "%06o", mode);
1154 }
1155
1156 static void prepare_temp_file(const char *name,
1157                               struct diff_tempfile *temp,
1158                               struct diff_filespec *one)
1159 {
1160         if (!DIFF_FILE_VALID(one)) {
1161         not_a_valid_file:
1162                 /* A '-' entry produces this for file-2, and
1163                  * a '+' entry produces this for file-1.
1164                  */
1165                 temp->name = "/dev/null";
1166                 strcpy(temp->hex, ".");
1167                 strcpy(temp->mode, ".");
1168                 return;
1169         }
1170
1171         if (!one->sha1_valid ||
1172             work_tree_matches(name, one->sha1)) {
1173                 struct stat st;
1174                 if (lstat(name, &st) < 0) {
1175                         if (errno == ENOENT)
1176                                 goto not_a_valid_file;
1177                         die("stat(%s): %s", name, strerror(errno));
1178                 }
1179                 if (S_ISLNK(st.st_mode)) {
1180                         int ret;
1181                         char buf[PATH_MAX + 1]; /* ought to be SYMLINK_MAX */
1182                         if (sizeof(buf) <= st.st_size)
1183                                 die("symlink too long: %s", name);
1184                         ret = readlink(name, buf, st.st_size);
1185                         if (ret < 0)
1186                                 die("readlink(%s)", name);
1187                         prep_temp_blob(temp, buf, st.st_size,
1188                                        (one->sha1_valid ?
1189                                         one->sha1 : null_sha1),
1190                                        (one->sha1_valid ?
1191                                         one->mode : S_IFLNK));
1192                 }
1193                 else {
1194                         /* we can borrow from the file in the work tree */
1195                         temp->name = name;
1196                         if (!one->sha1_valid)
1197                                 strcpy(temp->hex, sha1_to_hex(null_sha1));
1198                         else
1199                                 strcpy(temp->hex, sha1_to_hex(one->sha1));
1200                         /* Even though we may sometimes borrow the
1201                          * contents from the work tree, we always want
1202                          * one->mode.  mode is trustworthy even when
1203                          * !(one->sha1_valid), as long as
1204                          * DIFF_FILE_VALID(one).
1205                          */
1206                         sprintf(temp->mode, "%06o", one->mode);
1207                 }
1208                 return;
1209         }
1210         else {
1211                 if (diff_populate_filespec(one, 0))
1212                         die("cannot read data blob for %s", one->path);
1213                 prep_temp_blob(temp, one->data, one->size,
1214                                one->sha1, one->mode);
1215         }
1216 }
1217
1218 static void remove_tempfile(void)
1219 {
1220         int i;
1221
1222         for (i = 0; i < 2; i++)
1223                 if (diff_temp[i].name == diff_temp[i].tmp_path) {
1224                         unlink(diff_temp[i].name);
1225                         diff_temp[i].name = NULL;
1226                 }
1227 }
1228
1229 static void remove_tempfile_on_signal(int signo)
1230 {
1231         remove_tempfile();
1232         signal(SIGINT, SIG_DFL);
1233         raise(signo);
1234 }
1235
1236 static int spawn_prog(const char *pgm, const char **arg)
1237 {
1238         pid_t pid;
1239         int status;
1240
1241         fflush(NULL);
1242         pid = fork();
1243         if (pid < 0)
1244                 die("unable to fork");
1245         if (!pid) {
1246                 execvp(pgm, (char *const*) arg);
1247                 exit(255);
1248         }
1249
1250         while (waitpid(pid, &status, 0) < 0) {
1251                 if (errno == EINTR)
1252                         continue;
1253                 return -1;
1254         }
1255
1256         /* Earlier we did not check the exit status because
1257          * diff exits non-zero if files are different, and
1258          * we are not interested in knowing that.  It was a
1259          * mistake which made it harder to quit a diff-*
1260          * session that uses the git-apply-patch-script as
1261          * the GIT_EXTERNAL_DIFF.  A custom GIT_EXTERNAL_DIFF
1262          * should also exit non-zero only when it wants to
1263          * abort the entire diff-* session.
1264          */
1265         if (WIFEXITED(status) && !WEXITSTATUS(status))
1266                 return 0;
1267         return -1;
1268 }
1269
1270 /* An external diff command takes:
1271  *
1272  * diff-cmd name infile1 infile1-sha1 infile1-mode \
1273  *               infile2 infile2-sha1 infile2-mode [ rename-to ]
1274  *
1275  */
1276 static void run_external_diff(const char *pgm,
1277                               const char *name,
1278                               const char *other,
1279                               struct diff_filespec *one,
1280                               struct diff_filespec *two,
1281                               const char *xfrm_msg,
1282                               int complete_rewrite)
1283 {
1284         const char *spawn_arg[10];
1285         struct diff_tempfile *temp = diff_temp;
1286         int retval;
1287         static int atexit_asked = 0;
1288         const char *othername;
1289         const char **arg = &spawn_arg[0];
1290
1291         othername = (other? other : name);
1292         if (one && two) {
1293                 prepare_temp_file(name, &temp[0], one);
1294                 prepare_temp_file(othername, &temp[1], two);
1295                 if (! atexit_asked &&
1296                     (temp[0].name == temp[0].tmp_path ||
1297                      temp[1].name == temp[1].tmp_path)) {
1298                         atexit_asked = 1;
1299                         atexit(remove_tempfile);
1300                 }
1301                 signal(SIGINT, remove_tempfile_on_signal);
1302         }
1303
1304         if (one && two) {
1305                 *arg++ = pgm;
1306                 *arg++ = name;
1307                 *arg++ = temp[0].name;
1308                 *arg++ = temp[0].hex;
1309                 *arg++ = temp[0].mode;
1310                 *arg++ = temp[1].name;
1311                 *arg++ = temp[1].hex;
1312                 *arg++ = temp[1].mode;
1313                 if (other) {
1314                         *arg++ = other;
1315                         *arg++ = xfrm_msg;
1316                 }
1317         } else {
1318                 *arg++ = pgm;
1319                 *arg++ = name;
1320         }
1321         *arg = NULL;
1322         retval = spawn_prog(pgm, spawn_arg);
1323         remove_tempfile();
1324         if (retval) {
1325                 fprintf(stderr, "external diff died, stopping at %s.\n", name);
1326                 exit(1);
1327         }
1328 }
1329
1330 static void run_diff_cmd(const char *pgm,
1331                          const char *name,
1332                          const char *other,
1333                          struct diff_filespec *one,
1334                          struct diff_filespec *two,
1335                          const char *xfrm_msg,
1336                          struct diff_options *o,
1337                          int complete_rewrite)
1338 {
1339         if (pgm) {
1340                 run_external_diff(pgm, name, other, one, two, xfrm_msg,
1341                                   complete_rewrite);
1342                 return;
1343         }
1344         if (one && two)
1345                 builtin_diff(name, other ? other : name,
1346                              one, two, xfrm_msg, o, complete_rewrite);
1347         else
1348                 printf("* Unmerged path %s\n", name);
1349 }
1350
1351 static void diff_fill_sha1_info(struct diff_filespec *one)
1352 {
1353         if (DIFF_FILE_VALID(one)) {
1354                 if (!one->sha1_valid) {
1355                         struct stat st;
1356                         if (lstat(one->path, &st) < 0)
1357                                 die("stat %s", one->path);
1358                         if (index_path(one->sha1, one->path, &st, 0))
1359                                 die("cannot hash %s\n", one->path);
1360                 }
1361         }
1362         else
1363                 memset(one->sha1, 0, 20);
1364 }
1365
1366 static void run_diff(struct diff_filepair *p, struct diff_options *o)
1367 {
1368         const char *pgm = external_diff();
1369         char msg[PATH_MAX*2+300], *xfrm_msg;
1370         struct diff_filespec *one;
1371         struct diff_filespec *two;
1372         const char *name;
1373         const char *other;
1374         char *name_munged, *other_munged;
1375         int complete_rewrite = 0;
1376         int len;
1377
1378         if (DIFF_PAIR_UNMERGED(p)) {
1379                 /* unmerged */
1380                 run_diff_cmd(pgm, p->one->path, NULL, NULL, NULL, NULL, o, 0);
1381                 return;
1382         }
1383
1384         name = p->one->path;
1385         other = (strcmp(name, p->two->path) ? p->two->path : NULL);
1386         name_munged = quote_one(name);
1387         other_munged = quote_one(other);
1388         one = p->one; two = p->two;
1389
1390         diff_fill_sha1_info(one);
1391         diff_fill_sha1_info(two);
1392
1393         len = 0;
1394         switch (p->status) {
1395         case DIFF_STATUS_COPIED:
1396                 len += snprintf(msg + len, sizeof(msg) - len,
1397                                 "similarity index %d%%\n"
1398                                 "copy from %s\n"
1399                                 "copy to %s\n",
1400                                 (int)(0.5 + p->score * 100.0/MAX_SCORE),
1401                                 name_munged, other_munged);
1402                 break;
1403         case DIFF_STATUS_RENAMED:
1404                 len += snprintf(msg + len, sizeof(msg) - len,
1405                                 "similarity index %d%%\n"
1406                                 "rename from %s\n"
1407                                 "rename to %s\n",
1408                                 (int)(0.5 + p->score * 100.0/MAX_SCORE),
1409                                 name_munged, other_munged);
1410                 break;
1411         case DIFF_STATUS_MODIFIED:
1412                 if (p->score) {
1413                         len += snprintf(msg + len, sizeof(msg) - len,
1414                                         "dissimilarity index %d%%\n",
1415                                         (int)(0.5 + p->score *
1416                                               100.0/MAX_SCORE));
1417                         complete_rewrite = 1;
1418                         break;
1419                 }
1420                 /* fallthru */
1421         default:
1422                 /* nothing */
1423                 ;
1424         }
1425
1426         if (memcmp(one->sha1, two->sha1, 20)) {
1427                 int abbrev = o->full_index ? 40 : DEFAULT_ABBREV;
1428
1429                 len += snprintf(msg + len, sizeof(msg) - len,
1430                                 "index %.*s..%.*s",
1431                                 abbrev, sha1_to_hex(one->sha1),
1432                                 abbrev, sha1_to_hex(two->sha1));
1433                 if (one->mode == two->mode)
1434                         len += snprintf(msg + len, sizeof(msg) - len,
1435                                         " %06o", one->mode);
1436                 len += snprintf(msg + len, sizeof(msg) - len, "\n");
1437         }
1438
1439         if (len)
1440                 msg[--len] = 0;
1441         xfrm_msg = len ? msg : NULL;
1442
1443         if (!pgm &&
1444             DIFF_FILE_VALID(one) && DIFF_FILE_VALID(two) &&
1445             (S_IFMT & one->mode) != (S_IFMT & two->mode)) {
1446                 /* a filepair that changes between file and symlink
1447                  * needs to be split into deletion and creation.
1448                  */
1449                 struct diff_filespec *null = alloc_filespec(two->path);
1450                 run_diff_cmd(NULL, name, other, one, null, xfrm_msg, o, 0);
1451                 free(null);
1452                 null = alloc_filespec(one->path);
1453                 run_diff_cmd(NULL, name, other, null, two, xfrm_msg, o, 0);
1454                 free(null);
1455         }
1456         else
1457                 run_diff_cmd(pgm, name, other, one, two, xfrm_msg, o,
1458                              complete_rewrite);
1459
1460         free(name_munged);
1461         free(other_munged);
1462 }
1463
1464 static void run_diffstat(struct diff_filepair *p, struct diff_options *o,
1465                          struct diffstat_t *diffstat)
1466 {
1467         const char *name;
1468         const char *other;
1469         int complete_rewrite = 0;
1470
1471         if (DIFF_PAIR_UNMERGED(p)) {
1472                 /* unmerged */
1473                 builtin_diffstat(p->one->path, NULL, NULL, NULL, diffstat, o, 0);
1474                 return;
1475         }
1476
1477         name = p->one->path;
1478         other = (strcmp(name, p->two->path) ? p->two->path : NULL);
1479
1480         diff_fill_sha1_info(p->one);
1481         diff_fill_sha1_info(p->two);
1482
1483         if (p->status == DIFF_STATUS_MODIFIED && p->score)
1484                 complete_rewrite = 1;
1485         builtin_diffstat(name, other, p->one, p->two, diffstat, o, complete_rewrite);
1486 }
1487
1488 static void run_checkdiff(struct diff_filepair *p, struct diff_options *o)
1489 {
1490         const char *name;
1491         const char *other;
1492
1493         if (DIFF_PAIR_UNMERGED(p)) {
1494                 /* unmerged */
1495                 return;
1496         }
1497
1498         name = p->one->path;
1499         other = (strcmp(name, p->two->path) ? p->two->path : NULL);
1500
1501         diff_fill_sha1_info(p->one);
1502         diff_fill_sha1_info(p->two);
1503
1504         builtin_checkdiff(name, other, p->one, p->two);
1505 }
1506
1507 void diff_setup(struct diff_options *options)
1508 {
1509         memset(options, 0, sizeof(*options));
1510         options->line_termination = '\n';
1511         options->break_opt = -1;
1512         options->rename_limit = -1;
1513         options->context = 3;
1514         options->msg_sep = "";
1515
1516         options->change = diff_change;
1517         options->add_remove = diff_addremove;
1518         options->color_diff = diff_use_color_default;
1519         options->detect_rename = diff_detect_rename_default;
1520 }
1521
1522 int diff_setup_done(struct diff_options *options)
1523 {
1524         if ((options->find_copies_harder &&
1525              options->detect_rename != DIFF_DETECT_COPY) ||
1526             (0 <= options->rename_limit && !options->detect_rename))
1527                 return -1;
1528
1529         if (options->output_format & (DIFF_FORMAT_NAME |
1530                                       DIFF_FORMAT_NAME_STATUS |
1531                                       DIFF_FORMAT_CHECKDIFF |
1532                                       DIFF_FORMAT_NO_OUTPUT))
1533                 options->output_format &= ~(DIFF_FORMAT_RAW |
1534                                             DIFF_FORMAT_DIFFSTAT |
1535                                             DIFF_FORMAT_SUMMARY |
1536                                             DIFF_FORMAT_PATCH);
1537
1538         /*
1539          * These cases always need recursive; we do not drop caller-supplied
1540          * recursive bits for other formats here.
1541          */
1542         if (options->output_format & (DIFF_FORMAT_PATCH |
1543                                       DIFF_FORMAT_DIFFSTAT |
1544                                       DIFF_FORMAT_CHECKDIFF))
1545                 options->recursive = 1;
1546         /*
1547          * Also pickaxe would not work very well if you do not say recursive
1548          */
1549         if (options->pickaxe)
1550                 options->recursive = 1;
1551
1552         if (options->detect_rename && options->rename_limit < 0)
1553                 options->rename_limit = diff_rename_limit_default;
1554         if (options->setup & DIFF_SETUP_USE_CACHE) {
1555                 if (!active_cache)
1556                         /* read-cache does not die even when it fails
1557                          * so it is safe for us to do this here.  Also
1558                          * it does not smudge active_cache or active_nr
1559                          * when it fails, so we do not have to worry about
1560                          * cleaning it up ourselves either.
1561                          */
1562                         read_cache();
1563         }
1564         if (options->setup & DIFF_SETUP_USE_SIZE_CACHE)
1565                 use_size_cache = 1;
1566         if (options->abbrev <= 0 || 40 < options->abbrev)
1567                 options->abbrev = 40; /* full */
1568
1569         return 0;
1570 }
1571
1572 static int opt_arg(const char *arg, int arg_short, const char *arg_long, int *val)
1573 {
1574         char c, *eq;
1575         int len;
1576
1577         if (*arg != '-')
1578                 return 0;
1579         c = *++arg;
1580         if (!c)
1581                 return 0;
1582         if (c == arg_short) {
1583                 c = *++arg;
1584                 if (!c)
1585                         return 1;
1586                 if (val && isdigit(c)) {
1587                         char *end;
1588                         int n = strtoul(arg, &end, 10);
1589                         if (*end)
1590                                 return 0;
1591                         *val = n;
1592                         return 1;
1593                 }
1594                 return 0;
1595         }
1596         if (c != '-')
1597                 return 0;
1598         arg++;
1599         eq = strchr(arg, '=');
1600         if (eq)
1601                 len = eq - arg;
1602         else
1603                 len = strlen(arg);
1604         if (!len || strncmp(arg, arg_long, len))
1605                 return 0;
1606         if (eq) {
1607                 int n;
1608                 char *end;
1609                 if (!isdigit(*++eq))
1610                         return 0;
1611                 n = strtoul(eq, &end, 10);
1612                 if (*end)
1613                         return 0;
1614                 *val = n;
1615         }
1616         return 1;
1617 }
1618
1619 int diff_opt_parse(struct diff_options *options, const char **av, int ac)
1620 {
1621         const char *arg = av[0];
1622         if (!strcmp(arg, "-p") || !strcmp(arg, "-u"))
1623                 options->output_format |= DIFF_FORMAT_PATCH;
1624         else if (opt_arg(arg, 'U', "unified", &options->context))
1625                 options->output_format |= DIFF_FORMAT_PATCH;
1626         else if (!strcmp(arg, "--raw"))
1627                 options->output_format |= DIFF_FORMAT_RAW;
1628         else if (!strcmp(arg, "--patch-with-raw")) {
1629                 options->output_format |= DIFF_FORMAT_PATCH | DIFF_FORMAT_RAW;
1630         }
1631         else if (!strcmp(arg, "--stat"))
1632                 options->output_format |= DIFF_FORMAT_DIFFSTAT;
1633         else if (!strcmp(arg, "--check"))
1634                 options->output_format |= DIFF_FORMAT_CHECKDIFF;
1635         else if (!strcmp(arg, "--summary"))
1636                 options->output_format |= DIFF_FORMAT_SUMMARY;
1637         else if (!strcmp(arg, "--patch-with-stat")) {
1638                 options->output_format |= DIFF_FORMAT_PATCH | DIFF_FORMAT_DIFFSTAT;
1639         }
1640         else if (!strcmp(arg, "-z"))
1641                 options->line_termination = 0;
1642         else if (!strncmp(arg, "-l", 2))
1643                 options->rename_limit = strtoul(arg+2, NULL, 10);
1644         else if (!strcmp(arg, "--full-index"))
1645                 options->full_index = 1;
1646         else if (!strcmp(arg, "--binary")) {
1647                 options->output_format |= DIFF_FORMAT_PATCH;
1648                 options->full_index = options->binary = 1;
1649         }
1650         else if (!strcmp(arg, "-a") || !strcmp(arg, "--text")) {
1651                 options->text = 1;
1652         }
1653         else if (!strcmp(arg, "--name-only"))
1654                 options->output_format |= DIFF_FORMAT_NAME;
1655         else if (!strcmp(arg, "--name-status"))
1656                 options->output_format |= DIFF_FORMAT_NAME_STATUS;
1657         else if (!strcmp(arg, "-R"))
1658                 options->reverse_diff = 1;
1659         else if (!strncmp(arg, "-S", 2))
1660                 options->pickaxe = arg + 2;
1661         else if (!strcmp(arg, "-s")) {
1662                 options->output_format |= DIFF_FORMAT_NO_OUTPUT;
1663         }
1664         else if (!strncmp(arg, "-O", 2))
1665                 options->orderfile = arg + 2;
1666         else if (!strncmp(arg, "--diff-filter=", 14))
1667                 options->filter = arg + 14;
1668         else if (!strcmp(arg, "--pickaxe-all"))
1669                 options->pickaxe_opts = DIFF_PICKAXE_ALL;
1670         else if (!strcmp(arg, "--pickaxe-regex"))
1671                 options->pickaxe_opts = DIFF_PICKAXE_REGEX;
1672         else if (!strncmp(arg, "-B", 2)) {
1673                 if ((options->break_opt =
1674                      diff_scoreopt_parse(arg)) == -1)
1675                         return -1;
1676         }
1677         else if (!strncmp(arg, "-M", 2)) {
1678                 if ((options->rename_score =
1679                      diff_scoreopt_parse(arg)) == -1)
1680                         return -1;
1681                 options->detect_rename = DIFF_DETECT_RENAME;
1682         }
1683         else if (!strncmp(arg, "-C", 2)) {
1684                 if ((options->rename_score =
1685                      diff_scoreopt_parse(arg)) == -1)
1686                         return -1;
1687                 options->detect_rename = DIFF_DETECT_COPY;
1688         }
1689         else if (!strcmp(arg, "--find-copies-harder"))
1690                 options->find_copies_harder = 1;
1691         else if (!strcmp(arg, "--abbrev"))
1692                 options->abbrev = DEFAULT_ABBREV;
1693         else if (!strncmp(arg, "--abbrev=", 9)) {
1694                 options->abbrev = strtoul(arg + 9, NULL, 10);
1695                 if (options->abbrev < MINIMUM_ABBREV)
1696                         options->abbrev = MINIMUM_ABBREV;
1697                 else if (40 < options->abbrev)
1698                         options->abbrev = 40;
1699         }
1700         else if (!strcmp(arg, "--color"))
1701                 options->color_diff = 1;
1702         else if (!strcmp(arg, "--no-color"))
1703                 options->color_diff = 0;
1704         else if (!strcmp(arg, "-w") || !strcmp(arg, "--ignore-all-space"))
1705                 options->xdl_opts |= XDF_IGNORE_WHITESPACE;
1706         else if (!strcmp(arg, "-b") || !strcmp(arg, "--ignore-space-change"))
1707                 options->xdl_opts |= XDF_IGNORE_WHITESPACE_CHANGE;
1708         else if (!strcmp(arg, "--no-renames"))
1709                 options->detect_rename = 0;
1710         else
1711                 return 0;
1712         return 1;
1713 }
1714
1715 static int parse_num(const char **cp_p)
1716 {
1717         unsigned long num, scale;
1718         int ch, dot;
1719         const char *cp = *cp_p;
1720
1721         num = 0;
1722         scale = 1;
1723         dot = 0;
1724         for(;;) {
1725                 ch = *cp;
1726                 if ( !dot && ch == '.' ) {
1727                         scale = 1;
1728                         dot = 1;
1729                 } else if ( ch == '%' ) {
1730                         scale = dot ? scale*100 : 100;
1731                         cp++;   /* % is always at the end */
1732                         break;
1733                 } else if ( ch >= '0' && ch <= '9' ) {
1734                         if ( scale < 100000 ) {
1735                                 scale *= 10;
1736                                 num = (num*10) + (ch-'0');
1737                         }
1738                 } else {
1739                         break;
1740                 }
1741                 cp++;
1742         }
1743         *cp_p = cp;
1744
1745         /* user says num divided by scale and we say internally that
1746          * is MAX_SCORE * num / scale.
1747          */
1748         return (num >= scale) ? MAX_SCORE : (MAX_SCORE * num / scale);
1749 }
1750
1751 int diff_scoreopt_parse(const char *opt)
1752 {
1753         int opt1, opt2, cmd;
1754
1755         if (*opt++ != '-')
1756                 return -1;
1757         cmd = *opt++;
1758         if (cmd != 'M' && cmd != 'C' && cmd != 'B')
1759                 return -1; /* that is not a -M, -C nor -B option */
1760
1761         opt1 = parse_num(&opt);
1762         if (cmd != 'B')
1763                 opt2 = 0;
1764         else {
1765                 if (*opt == 0)
1766                         opt2 = 0;
1767                 else if (*opt != '/')
1768                         return -1; /* we expect -B80/99 or -B80 */
1769                 else {
1770                         opt++;
1771                         opt2 = parse_num(&opt);
1772                 }
1773         }
1774         if (*opt != 0)
1775                 return -1;
1776         return opt1 | (opt2 << 16);
1777 }
1778
1779 struct diff_queue_struct diff_queued_diff;
1780
1781 void diff_q(struct diff_queue_struct *queue, struct diff_filepair *dp)
1782 {
1783         if (queue->alloc <= queue->nr) {
1784                 queue->alloc = alloc_nr(queue->alloc);
1785                 queue->queue = xrealloc(queue->queue,
1786                                         sizeof(dp) * queue->alloc);
1787         }
1788         queue->queue[queue->nr++] = dp;
1789 }
1790
1791 struct diff_filepair *diff_queue(struct diff_queue_struct *queue,
1792                                  struct diff_filespec *one,
1793                                  struct diff_filespec *two)
1794 {
1795         struct diff_filepair *dp = xmalloc(sizeof(*dp));
1796         dp->one = one;
1797         dp->two = two;
1798         dp->score = 0;
1799         dp->status = 0;
1800         dp->source_stays = 0;
1801         dp->broken_pair = 0;
1802         if (queue)
1803                 diff_q(queue, dp);
1804         return dp;
1805 }
1806
1807 void diff_free_filepair(struct diff_filepair *p)
1808 {
1809         diff_free_filespec_data(p->one);
1810         diff_free_filespec_data(p->two);
1811         free(p->one);
1812         free(p->two);
1813         free(p);
1814 }
1815
1816 /* This is different from find_unique_abbrev() in that
1817  * it stuffs the result with dots for alignment.
1818  */
1819 const char *diff_unique_abbrev(const unsigned char *sha1, int len)
1820 {
1821         int abblen;
1822         const char *abbrev;
1823         if (len == 40)
1824                 return sha1_to_hex(sha1);
1825
1826         abbrev = find_unique_abbrev(sha1, len);
1827         if (!abbrev)
1828                 return sha1_to_hex(sha1);
1829         abblen = strlen(abbrev);
1830         if (abblen < 37) {
1831                 static char hex[41];
1832                 if (len < abblen && abblen <= len + 2)
1833                         sprintf(hex, "%s%.*s", abbrev, len+3-abblen, "..");
1834                 else
1835                         sprintf(hex, "%s...", abbrev);
1836                 return hex;
1837         }
1838         return sha1_to_hex(sha1);
1839 }
1840
1841 static void diff_flush_raw(struct diff_filepair *p,
1842                            struct diff_options *options)
1843 {
1844         int two_paths;
1845         char status[10];
1846         int abbrev = options->abbrev;
1847         const char *path_one, *path_two;
1848         int inter_name_termination = '\t';
1849         int line_termination = options->line_termination;
1850
1851         if (!line_termination)
1852                 inter_name_termination = 0;
1853
1854         path_one = p->one->path;
1855         path_two = p->two->path;
1856         if (line_termination) {
1857                 path_one = quote_one(path_one);
1858                 path_two = quote_one(path_two);
1859         }
1860
1861         if (p->score)
1862                 sprintf(status, "%c%03d", p->status,
1863                         (int)(0.5 + p->score * 100.0/MAX_SCORE));
1864         else {
1865                 status[0] = p->status;
1866                 status[1] = 0;
1867         }
1868         switch (p->status) {
1869         case DIFF_STATUS_COPIED:
1870         case DIFF_STATUS_RENAMED:
1871                 two_paths = 1;
1872                 break;
1873         case DIFF_STATUS_ADDED:
1874         case DIFF_STATUS_DELETED:
1875                 two_paths = 0;
1876                 break;
1877         default:
1878                 two_paths = 0;
1879                 break;
1880         }
1881         if (!(options->output_format & DIFF_FORMAT_NAME_STATUS)) {
1882                 printf(":%06o %06o %s ",
1883                        p->one->mode, p->two->mode,
1884                        diff_unique_abbrev(p->one->sha1, abbrev));
1885                 printf("%s ",
1886                        diff_unique_abbrev(p->two->sha1, abbrev));
1887         }
1888         printf("%s%c%s", status, inter_name_termination, path_one);
1889         if (two_paths)
1890                 printf("%c%s", inter_name_termination, path_two);
1891         putchar(line_termination);
1892         if (path_one != p->one->path)
1893                 free((void*)path_one);
1894         if (path_two != p->two->path)
1895                 free((void*)path_two);
1896 }
1897
1898 static void diff_flush_name(struct diff_filepair *p, int line_termination)
1899 {
1900         char *path = p->two->path;
1901
1902         if (line_termination)
1903                 path = quote_one(p->two->path);
1904         printf("%s%c", path, line_termination);
1905         if (p->two->path != path)
1906                 free(path);
1907 }
1908
1909 int diff_unmodified_pair(struct diff_filepair *p)
1910 {
1911         /* This function is written stricter than necessary to support
1912          * the currently implemented transformers, but the idea is to
1913          * let transformers to produce diff_filepairs any way they want,
1914          * and filter and clean them up here before producing the output.
1915          */
1916         struct diff_filespec *one, *two;
1917
1918         if (DIFF_PAIR_UNMERGED(p))
1919                 return 0; /* unmerged is interesting */
1920
1921         one = p->one;
1922         two = p->two;
1923
1924         /* deletion, addition, mode or type change
1925          * and rename are all interesting.
1926          */
1927         if (DIFF_FILE_VALID(one) != DIFF_FILE_VALID(two) ||
1928             DIFF_PAIR_MODE_CHANGED(p) ||
1929             strcmp(one->path, two->path))
1930                 return 0;
1931
1932         /* both are valid and point at the same path.  that is, we are
1933          * dealing with a change.
1934          */
1935         if (one->sha1_valid && two->sha1_valid &&
1936             !memcmp(one->sha1, two->sha1, sizeof(one->sha1)))
1937                 return 1; /* no change */
1938         if (!one->sha1_valid && !two->sha1_valid)
1939                 return 1; /* both look at the same file on the filesystem. */
1940         return 0;
1941 }
1942
1943 static void diff_flush_patch(struct diff_filepair *p, struct diff_options *o)
1944 {
1945         if (diff_unmodified_pair(p))
1946                 return;
1947
1948         if ((DIFF_FILE_VALID(p->one) && S_ISDIR(p->one->mode)) ||
1949             (DIFF_FILE_VALID(p->two) && S_ISDIR(p->two->mode)))
1950                 return; /* no tree diffs in patch format */
1951
1952         run_diff(p, o);
1953 }
1954
1955 static void diff_flush_stat(struct diff_filepair *p, struct diff_options *o,
1956                             struct diffstat_t *diffstat)
1957 {
1958         if (diff_unmodified_pair(p))
1959                 return;
1960
1961         if ((DIFF_FILE_VALID(p->one) && S_ISDIR(p->one->mode)) ||
1962             (DIFF_FILE_VALID(p->two) && S_ISDIR(p->two->mode)))
1963                 return; /* no tree diffs in patch format */
1964
1965         run_diffstat(p, o, diffstat);
1966 }
1967
1968 static void diff_flush_checkdiff(struct diff_filepair *p,
1969                 struct diff_options *o)
1970 {
1971         if (diff_unmodified_pair(p))
1972                 return;
1973
1974         if ((DIFF_FILE_VALID(p->one) && S_ISDIR(p->one->mode)) ||
1975             (DIFF_FILE_VALID(p->two) && S_ISDIR(p->two->mode)))
1976                 return; /* no tree diffs in patch format */
1977
1978         run_checkdiff(p, o);
1979 }
1980
1981 int diff_queue_is_empty(void)
1982 {
1983         struct diff_queue_struct *q = &diff_queued_diff;
1984         int i;
1985         for (i = 0; i < q->nr; i++)
1986                 if (!diff_unmodified_pair(q->queue[i]))
1987                         return 0;
1988         return 1;
1989 }
1990
1991 #if DIFF_DEBUG
1992 void diff_debug_filespec(struct diff_filespec *s, int x, const char *one)
1993 {
1994         fprintf(stderr, "queue[%d] %s (%s) %s %06o %s\n",
1995                 x, one ? one : "",
1996                 s->path,
1997                 DIFF_FILE_VALID(s) ? "valid" : "invalid",
1998                 s->mode,
1999                 s->sha1_valid ? sha1_to_hex(s->sha1) : "");
2000         fprintf(stderr, "queue[%d] %s size %lu flags %d\n",
2001                 x, one ? one : "",
2002                 s->size, s->xfrm_flags);
2003 }
2004
2005 void diff_debug_filepair(const struct diff_filepair *p, int i)
2006 {
2007         diff_debug_filespec(p->one, i, "one");
2008         diff_debug_filespec(p->two, i, "two");
2009         fprintf(stderr, "score %d, status %c stays %d broken %d\n",
2010                 p->score, p->status ? p->status : '?',
2011                 p->source_stays, p->broken_pair);
2012 }
2013
2014 void diff_debug_queue(const char *msg, struct diff_queue_struct *q)
2015 {
2016         int i;
2017         if (msg)
2018                 fprintf(stderr, "%s\n", msg);
2019         fprintf(stderr, "q->nr = %d\n", q->nr);
2020         for (i = 0; i < q->nr; i++) {
2021                 struct diff_filepair *p = q->queue[i];
2022                 diff_debug_filepair(p, i);
2023         }
2024 }
2025 #endif
2026
2027 static void diff_resolve_rename_copy(void)
2028 {
2029         int i, j;
2030         struct diff_filepair *p, *pp;
2031         struct diff_queue_struct *q = &diff_queued_diff;
2032
2033         diff_debug_queue("resolve-rename-copy", q);
2034
2035         for (i = 0; i < q->nr; i++) {
2036                 p = q->queue[i];
2037                 p->status = 0; /* undecided */
2038                 if (DIFF_PAIR_UNMERGED(p))
2039                         p->status = DIFF_STATUS_UNMERGED;
2040                 else if (!DIFF_FILE_VALID(p->one))
2041                         p->status = DIFF_STATUS_ADDED;
2042                 else if (!DIFF_FILE_VALID(p->two))
2043                         p->status = DIFF_STATUS_DELETED;
2044                 else if (DIFF_PAIR_TYPE_CHANGED(p))
2045                         p->status = DIFF_STATUS_TYPE_CHANGED;
2046
2047                 /* from this point on, we are dealing with a pair
2048                  * whose both sides are valid and of the same type, i.e.
2049                  * either in-place edit or rename/copy edit.
2050                  */
2051                 else if (DIFF_PAIR_RENAME(p)) {
2052                         if (p->source_stays) {
2053                                 p->status = DIFF_STATUS_COPIED;
2054                                 continue;
2055                         }
2056                         /* See if there is some other filepair that
2057                          * copies from the same source as us.  If so
2058                          * we are a copy.  Otherwise we are either a
2059                          * copy if the path stays, or a rename if it
2060                          * does not, but we already handled "stays" case.
2061                          */
2062                         for (j = i + 1; j < q->nr; j++) {
2063                                 pp = q->queue[j];
2064                                 if (strcmp(pp->one->path, p->one->path))
2065                                         continue; /* not us */
2066                                 if (!DIFF_PAIR_RENAME(pp))
2067                                         continue; /* not a rename/copy */
2068                                 /* pp is a rename/copy from the same source */
2069                                 p->status = DIFF_STATUS_COPIED;
2070                                 break;
2071                         }
2072                         if (!p->status)
2073                                 p->status = DIFF_STATUS_RENAMED;
2074                 }
2075                 else if (memcmp(p->one->sha1, p->two->sha1, 20) ||
2076                          p->one->mode != p->two->mode)
2077                         p->status = DIFF_STATUS_MODIFIED;
2078                 else {
2079                         /* This is a "no-change" entry and should not
2080                          * happen anymore, but prepare for broken callers.
2081                          */
2082                         error("feeding unmodified %s to diffcore",
2083                               p->one->path);
2084                         p->status = DIFF_STATUS_UNKNOWN;
2085                 }
2086         }
2087         diff_debug_queue("resolve-rename-copy done", q);
2088 }
2089
2090 static int check_pair_status(struct diff_filepair *p)
2091 {
2092         switch (p->status) {
2093         case DIFF_STATUS_UNKNOWN:
2094                 return 0;
2095         case 0:
2096                 die("internal error in diff-resolve-rename-copy");
2097         default:
2098                 return 1;
2099         }
2100 }
2101
2102 static void flush_one_pair(struct diff_filepair *p, struct diff_options *opt)
2103 {
2104         int fmt = opt->output_format;
2105
2106         if (fmt & DIFF_FORMAT_CHECKDIFF)
2107                 diff_flush_checkdiff(p, opt);
2108         else if (fmt & (DIFF_FORMAT_RAW | DIFF_FORMAT_NAME_STATUS))
2109                 diff_flush_raw(p, opt);
2110         else if (fmt & DIFF_FORMAT_NAME)
2111                 diff_flush_name(p, opt->line_termination);
2112 }
2113
2114 static void show_file_mode_name(const char *newdelete, struct diff_filespec *fs)
2115 {
2116         if (fs->mode)
2117                 printf(" %s mode %06o %s\n", newdelete, fs->mode, fs->path);
2118         else
2119                 printf(" %s %s\n", newdelete, fs->path);
2120 }
2121
2122
2123 static void show_mode_change(struct diff_filepair *p, int show_name)
2124 {
2125         if (p->one->mode && p->two->mode && p->one->mode != p->two->mode) {
2126                 if (show_name)
2127                         printf(" mode change %06o => %06o %s\n",
2128                                p->one->mode, p->two->mode, p->two->path);
2129                 else
2130                         printf(" mode change %06o => %06o\n",
2131                                p->one->mode, p->two->mode);
2132         }
2133 }
2134
2135 static void show_rename_copy(const char *renamecopy, struct diff_filepair *p)
2136 {
2137         const char *old, *new;
2138
2139         /* Find common prefix */
2140         old = p->one->path;
2141         new = p->two->path;
2142         while (1) {
2143                 const char *slash_old, *slash_new;
2144                 slash_old = strchr(old, '/');
2145                 slash_new = strchr(new, '/');
2146                 if (!slash_old ||
2147                     !slash_new ||
2148                     slash_old - old != slash_new - new ||
2149                     memcmp(old, new, slash_new - new))
2150                         break;
2151                 old = slash_old + 1;
2152                 new = slash_new + 1;
2153         }
2154         /* p->one->path thru old is the common prefix, and old and new
2155          * through the end of names are renames
2156          */
2157         if (old != p->one->path)
2158                 printf(" %s %.*s{%s => %s} (%d%%)\n", renamecopy,
2159                        (int)(old - p->one->path), p->one->path,
2160                        old, new, (int)(0.5 + p->score * 100.0/MAX_SCORE));
2161         else
2162                 printf(" %s %s => %s (%d%%)\n", renamecopy,
2163                        p->one->path, p->two->path,
2164                        (int)(0.5 + p->score * 100.0/MAX_SCORE));
2165         show_mode_change(p, 0);
2166 }
2167
2168 static void diff_summary(struct diff_filepair *p)
2169 {
2170         switch(p->status) {
2171         case DIFF_STATUS_DELETED:
2172                 show_file_mode_name("delete", p->one);
2173                 break;
2174         case DIFF_STATUS_ADDED:
2175                 show_file_mode_name("create", p->two);
2176                 break;
2177         case DIFF_STATUS_COPIED:
2178                 show_rename_copy("copy", p);
2179                 break;
2180         case DIFF_STATUS_RENAMED:
2181                 show_rename_copy("rename", p);
2182                 break;
2183         default:
2184                 if (p->score) {
2185                         printf(" rewrite %s (%d%%)\n", p->two->path,
2186                                 (int)(0.5 + p->score * 100.0/MAX_SCORE));
2187                         show_mode_change(p, 0);
2188                 } else  show_mode_change(p, 1);
2189                 break;
2190         }
2191 }
2192
2193 struct patch_id_t {
2194         struct xdiff_emit_state xm;
2195         SHA_CTX *ctx;
2196         int patchlen;
2197 };
2198
2199 static int remove_space(char *line, int len)
2200 {
2201         int i;
2202         char *dst = line;
2203         unsigned char c;
2204
2205         for (i = 0; i < len; i++)
2206                 if (!isspace((c = line[i])))
2207                         *dst++ = c;
2208
2209         return dst - line;
2210 }
2211
2212 static void patch_id_consume(void *priv, char *line, unsigned long len)
2213 {
2214         struct patch_id_t *data = priv;
2215         int new_len;
2216
2217         /* Ignore line numbers when computing the SHA1 of the patch */
2218         if (!strncmp(line, "@@ -", 4))
2219                 return;
2220
2221         new_len = remove_space(line, len);
2222
2223         SHA1_Update(data->ctx, line, new_len);
2224         data->patchlen += new_len;
2225 }
2226
2227 /* returns 0 upon success, and writes result into sha1 */
2228 static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1)
2229 {
2230         struct diff_queue_struct *q = &diff_queued_diff;
2231         int i;
2232         SHA_CTX ctx;
2233         struct patch_id_t data;
2234         char buffer[PATH_MAX * 4 + 20];
2235
2236         SHA1_Init(&ctx);
2237         memset(&data, 0, sizeof(struct patch_id_t));
2238         data.ctx = &ctx;
2239         data.xm.consume = patch_id_consume;
2240
2241         for (i = 0; i < q->nr; i++) {
2242                 xpparam_t xpp;
2243                 xdemitconf_t xecfg;
2244                 xdemitcb_t ecb;
2245                 mmfile_t mf1, mf2;
2246                 struct diff_filepair *p = q->queue[i];
2247                 int len1, len2;
2248
2249                 if (p->status == 0)
2250                         return error("internal diff status error");
2251                 if (p->status == DIFF_STATUS_UNKNOWN)
2252                         continue;
2253                 if (diff_unmodified_pair(p))
2254                         continue;
2255                 if ((DIFF_FILE_VALID(p->one) && S_ISDIR(p->one->mode)) ||
2256                     (DIFF_FILE_VALID(p->two) && S_ISDIR(p->two->mode)))
2257                         continue;
2258                 if (DIFF_PAIR_UNMERGED(p))
2259                         continue;
2260
2261                 diff_fill_sha1_info(p->one);
2262                 diff_fill_sha1_info(p->two);
2263                 if (fill_mmfile(&mf1, p->one) < 0 ||
2264                                 fill_mmfile(&mf2, p->two) < 0)
2265                         return error("unable to read files to diff");
2266
2267                 /* Maybe hash p->two? into the patch id? */
2268                 if (mmfile_is_binary(&mf2))
2269                         continue;
2270
2271                 len1 = remove_space(p->one->path, strlen(p->one->path));
2272                 len2 = remove_space(p->two->path, strlen(p->two->path));
2273                 if (p->one->mode == 0)
2274                         len1 = snprintf(buffer, sizeof(buffer),
2275                                         "diff--gita/%.*sb/%.*s"
2276                                         "newfilemode%06o"
2277                                         "---/dev/null"
2278                                         "+++b/%.*s",
2279                                         len1, p->one->path,
2280                                         len2, p->two->path,
2281                                         p->two->mode,
2282                                         len2, p->two->path);
2283                 else if (p->two->mode == 0)
2284                         len1 = snprintf(buffer, sizeof(buffer),
2285                                         "diff--gita/%.*sb/%.*s"
2286                                         "deletedfilemode%06o"
2287                                         "---a/%.*s"
2288                                         "+++/dev/null",
2289                                         len1, p->one->path,
2290                                         len2, p->two->path,
2291                                         p->one->mode,
2292                                         len1, p->one->path);
2293                 else
2294                         len1 = snprintf(buffer, sizeof(buffer),
2295                                         "diff--gita/%.*sb/%.*s"
2296                                         "---a/%.*s"
2297                                         "+++b/%.*s",
2298                                         len1, p->one->path,
2299                                         len2, p->two->path,
2300                                         len1, p->one->path,
2301                                         len2, p->two->path);
2302                 SHA1_Update(&ctx, buffer, len1);
2303
2304                 xpp.flags = XDF_NEED_MINIMAL;
2305                 xecfg.ctxlen = 3;
2306                 xecfg.flags = XDL_EMIT_FUNCNAMES;
2307                 ecb.outf = xdiff_outf;
2308                 ecb.priv = &data;
2309                 xdl_diff(&mf1, &mf2, &xpp, &xecfg, &ecb);
2310         }
2311
2312         SHA1_Final(sha1, &ctx);
2313         return 0;
2314 }
2315
2316 int diff_flush_patch_id(struct diff_options *options, unsigned char *sha1)
2317 {
2318         struct diff_queue_struct *q = &diff_queued_diff;
2319         int i;
2320         int result = diff_get_patch_id(options, sha1);
2321
2322         for (i = 0; i < q->nr; i++)
2323                 diff_free_filepair(q->queue[i]);
2324
2325         free(q->queue);
2326         q->queue = NULL;
2327         q->nr = q->alloc = 0;
2328
2329         return result;
2330 }
2331
2332 static int is_summary_empty(const struct diff_queue_struct *q)
2333 {
2334         int i;
2335
2336         for (i = 0; i < q->nr; i++) {
2337                 const struct diff_filepair *p = q->queue[i];
2338
2339                 switch (p->status) {
2340                 case DIFF_STATUS_DELETED:
2341                 case DIFF_STATUS_ADDED:
2342                 case DIFF_STATUS_COPIED:
2343                 case DIFF_STATUS_RENAMED:
2344                         return 0;
2345                 default:
2346                         if (p->score)
2347                                 return 0;
2348                         if (p->one->mode && p->two->mode &&
2349                             p->one->mode != p->two->mode)
2350                                 return 0;
2351                         break;
2352                 }
2353         }
2354         return 1;
2355 }
2356
2357 void diff_flush(struct diff_options *options)
2358 {
2359         struct diff_queue_struct *q = &diff_queued_diff;
2360         int i, output_format = options->output_format;
2361         int separator = 0;
2362
2363         /*
2364          * Order: raw, stat, summary, patch
2365          * or:    name/name-status/checkdiff (other bits clear)
2366          */
2367         if (!q->nr)
2368                 goto free_queue;
2369
2370         if (output_format & (DIFF_FORMAT_RAW |
2371                              DIFF_FORMAT_NAME |
2372                              DIFF_FORMAT_NAME_STATUS |
2373                              DIFF_FORMAT_CHECKDIFF)) {
2374                 for (i = 0; i < q->nr; i++) {
2375                         struct diff_filepair *p = q->queue[i];
2376                         if (check_pair_status(p))
2377                                 flush_one_pair(p, options);
2378                 }
2379                 separator++;
2380         }
2381
2382         if (output_format & DIFF_FORMAT_DIFFSTAT) {
2383                 struct diffstat_t diffstat;
2384
2385                 memset(&diffstat, 0, sizeof(struct diffstat_t));
2386                 diffstat.xm.consume = diffstat_consume;
2387                 for (i = 0; i < q->nr; i++) {
2388                         struct diff_filepair *p = q->queue[i];
2389                         if (check_pair_status(p))
2390                                 diff_flush_stat(p, options, &diffstat);
2391                 }
2392                 show_stats(&diffstat);
2393                 separator++;
2394         }
2395
2396         if (output_format & DIFF_FORMAT_SUMMARY && !is_summary_empty(q)) {
2397                 for (i = 0; i < q->nr; i++)
2398                         diff_summary(q->queue[i]);
2399                 separator++;
2400         }
2401
2402         if (output_format & DIFF_FORMAT_PATCH) {
2403                 if (separator) {
2404                         if (options->stat_sep) {
2405                                 /* attach patch instead of inline */
2406                                 fputs(options->stat_sep, stdout);
2407                         } else {
2408                                 putchar(options->line_termination);
2409                         }
2410                 }
2411
2412                 for (i = 0; i < q->nr; i++) {
2413                         struct diff_filepair *p = q->queue[i];
2414                         if (check_pair_status(p))
2415                                 diff_flush_patch(p, options);
2416                 }
2417         }
2418
2419         for (i = 0; i < q->nr; i++)
2420                 diff_free_filepair(q->queue[i]);
2421 free_queue:
2422         free(q->queue);
2423         q->queue = NULL;
2424         q->nr = q->alloc = 0;
2425 }
2426
2427 static void diffcore_apply_filter(const char *filter)
2428 {
2429         int i;
2430         struct diff_queue_struct *q = &diff_queued_diff;
2431         struct diff_queue_struct outq;
2432         outq.queue = NULL;
2433         outq.nr = outq.alloc = 0;
2434
2435         if (!filter)
2436                 return;
2437
2438         if (strchr(filter, DIFF_STATUS_FILTER_AON)) {
2439                 int found;
2440                 for (i = found = 0; !found && i < q->nr; i++) {
2441                         struct diff_filepair *p = q->queue[i];
2442                         if (((p->status == DIFF_STATUS_MODIFIED) &&
2443                              ((p->score &&
2444                                strchr(filter, DIFF_STATUS_FILTER_BROKEN)) ||
2445                               (!p->score &&
2446                                strchr(filter, DIFF_STATUS_MODIFIED)))) ||
2447                             ((p->status != DIFF_STATUS_MODIFIED) &&
2448                              strchr(filter, p->status)))
2449                                 found++;
2450                 }
2451                 if (found)
2452                         return;
2453
2454                 /* otherwise we will clear the whole queue
2455                  * by copying the empty outq at the end of this
2456                  * function, but first clear the current entries
2457                  * in the queue.
2458                  */
2459                 for (i = 0; i < q->nr; i++)
2460                         diff_free_filepair(q->queue[i]);
2461         }
2462         else {
2463                 /* Only the matching ones */
2464                 for (i = 0; i < q->nr; i++) {
2465                         struct diff_filepair *p = q->queue[i];
2466
2467                         if (((p->status == DIFF_STATUS_MODIFIED) &&
2468                              ((p->score &&
2469                                strchr(filter, DIFF_STATUS_FILTER_BROKEN)) ||
2470                               (!p->score &&
2471                                strchr(filter, DIFF_STATUS_MODIFIED)))) ||
2472                             ((p->status != DIFF_STATUS_MODIFIED) &&
2473                              strchr(filter, p->status)))
2474                                 diff_q(&outq, p);
2475                         else
2476                                 diff_free_filepair(p);
2477                 }
2478         }
2479         free(q->queue);
2480         *q = outq;
2481 }
2482
2483 void diffcore_std(struct diff_options *options)
2484 {
2485         if (options->break_opt != -1)
2486                 diffcore_break(options->break_opt);
2487         if (options->detect_rename)
2488                 diffcore_rename(options);
2489         if (options->break_opt != -1)
2490                 diffcore_merge_broken();
2491         if (options->pickaxe)
2492                 diffcore_pickaxe(options->pickaxe, options->pickaxe_opts);
2493         if (options->orderfile)
2494                 diffcore_order(options->orderfile);
2495         diff_resolve_rename_copy();
2496         diffcore_apply_filter(options->filter);
2497 }
2498
2499
2500 void diffcore_std_no_resolve(struct diff_options *options)
2501 {
2502         if (options->pickaxe)
2503                 diffcore_pickaxe(options->pickaxe, options->pickaxe_opts);
2504         if (options->orderfile)
2505                 diffcore_order(options->orderfile);
2506         diffcore_apply_filter(options->filter);
2507 }
2508
2509 void diff_addremove(struct diff_options *options,
2510                     int addremove, unsigned mode,
2511                     const unsigned char *sha1,
2512                     const char *base, const char *path)
2513 {
2514         char concatpath[PATH_MAX];
2515         struct diff_filespec *one, *two;
2516
2517         /* This may look odd, but it is a preparation for
2518          * feeding "there are unchanged files which should
2519          * not produce diffs, but when you are doing copy
2520          * detection you would need them, so here they are"
2521          * entries to the diff-core.  They will be prefixed
2522          * with something like '=' or '*' (I haven't decided
2523          * which but should not make any difference).
2524          * Feeding the same new and old to diff_change()
2525          * also has the same effect.
2526          * Before the final output happens, they are pruned after
2527          * merged into rename/copy pairs as appropriate.
2528          */
2529         if (options->reverse_diff)
2530                 addremove = (addremove == '+' ? '-' :
2531                              addremove == '-' ? '+' : addremove);
2532
2533         if (!path) path = "";
2534         sprintf(concatpath, "%s%s", base, path);
2535         one = alloc_filespec(concatpath);
2536         two = alloc_filespec(concatpath);
2537
2538         if (addremove != '+')
2539                 fill_filespec(one, sha1, mode);
2540         if (addremove != '-')
2541                 fill_filespec(two, sha1, mode);
2542
2543         diff_queue(&diff_queued_diff, one, two);
2544 }
2545
2546 void diff_change(struct diff_options *options,
2547                  unsigned old_mode, unsigned new_mode,
2548                  const unsigned char *old_sha1,
2549                  const unsigned char *new_sha1,
2550                  const char *base, const char *path)
2551 {
2552         char concatpath[PATH_MAX];
2553         struct diff_filespec *one, *two;
2554
2555         if (options->reverse_diff) {
2556                 unsigned tmp;
2557                 const unsigned char *tmp_c;
2558                 tmp = old_mode; old_mode = new_mode; new_mode = tmp;
2559                 tmp_c = old_sha1; old_sha1 = new_sha1; new_sha1 = tmp_c;
2560         }
2561         if (!path) path = "";
2562         sprintf(concatpath, "%s%s", base, path);
2563         one = alloc_filespec(concatpath);
2564         two = alloc_filespec(concatpath);
2565         fill_filespec(one, old_sha1, old_mode);
2566         fill_filespec(two, new_sha1, new_mode);
2567
2568         diff_queue(&diff_queued_diff, one, two);
2569 }
2570
2571 void diff_unmerge(struct diff_options *options,
2572                   const char *path)
2573 {
2574         struct diff_filespec *one, *two;
2575         one = alloc_filespec(path);
2576         two = alloc_filespec(path);
2577         diff_queue(&diff_queued_diff, one, two);
2578 }