Andrew's git - gitweb.git/blob

b0846bc09bd2dc2c63f7ec702ac021e192606d93
   1#include "cache.h"
   2#include "commit.h"
   3#include "diff.h"
   4#include "diffcore.h"
   5#include "quote.h"
   6
   7struct path_list {
   8        struct path_list *next;
   9        int len;
  10        char *path;
  11        unsigned char sha1[20];
  12        unsigned char parent_sha1[FLEX_ARRAY][20];
  13};
  14
  15static int uninteresting(struct diff_filepair *p)
  16{
  17        if (diff_unmodified_pair(p))
  18                return 1;
  19        if (!S_ISREG(p->one->mode) || !S_ISREG(p->two->mode))
  20                return 1;
  21        return 0;
  22}
  23
  24static struct path_list *intersect_paths(struct path_list *curr,
  25                                         int n, int num_parent)
  26{
  27        struct diff_queue_struct *q = &diff_queued_diff;
  28        struct path_list *p;
  29        int i;
  30
  31        if (!n) {
  32                struct path_list *list = NULL, **tail = &list;
  33                for (i = 0; i < q->nr; i++) {
  34                        int len;
  35                        const char *path;
  36                        if (uninteresting(q->queue[i]))
  37                                continue;
  38                        path = q->queue[i]->two->path;
  39                        len = strlen(path);
  40
  41                        p = xmalloc(sizeof(*p) + len + 1 + num_parent * 20);
  42                        p->path = (char*) &(p->parent_sha1[num_parent][0]);
  43                        memcpy(p->path, path, len);
  44                        p->path[len] = 0;
  45                        p->len = len;
  46                        p->next = NULL;
  47                        memcpy(p->sha1, q->queue[i]->two->sha1, 20);
  48                        memcpy(p->parent_sha1[n], q->queue[i]->one->sha1, 20);
  49                        *tail = p;
  50                        tail = &p->next;
  51                }
  52                return list;
  53        }
  54
  55        for (p = curr; p; p = p->next) {
  56                int found = 0;
  57                if (!p->len)
  58                        continue;
  59                for (i = 0; i < q->nr; i++) {
  60                        const char *path;
  61                        int len;
  62
  63                        if (uninteresting(q->queue[i]))
  64                                continue;
  65                        path = q->queue[i]->two->path;
  66                        len = strlen(path);
  67                        if (len == p->len && !memcmp(path, p->path, len)) {
  68                                found = 1;
  69                                memcpy(p->parent_sha1[n],
  70                                       q->queue[i]->one->sha1, 20);
  71                                break;
  72                        }
  73                }
  74                if (!found)
  75                        p->len = 0;
  76        }
  77        return curr;
  78}
  79
  80struct lline {
  81        struct lline *next;
  82        int len;
  83        unsigned long parent_map;
  84        char line[FLEX_ARRAY];
  85};
  86
  87struct sline {
  88        struct lline *lost_head, **lost_tail;
  89        char *bol;
  90        int len;
  91        unsigned long flag;
  92};
  93
  94static char *grab_blob(const unsigned char *sha1, unsigned long *size)
  95{
  96        char *blob;
  97        char type[20];
  98        if (!memcmp(sha1, null_sha1, 20)) {
  99                /* deleted blob */
 100                *size = 0;
 101                return xcalloc(1, 1);
 102        }
 103        blob = read_sha1_file(sha1, type, size);
 104        if (strcmp(type, "blob"))
 105                die("object '%s' is not a blob!", sha1_to_hex(sha1));
 106        return blob;
 107}
 108
 109#define TMPPATHLEN 50
 110#define MAXLINELEN 10240
 111
 112static void write_to_temp_file(char *tmpfile, void *blob, unsigned long size)
 113{
 114        int fd = git_mkstemp(tmpfile, TMPPATHLEN, ".diff_XXXXXX");
 115        if (fd < 0)
 116                die("unable to create temp-file");
 117        if (write(fd, blob, size) != size)
 118                die("unable to write temp-file");
 119        close(fd);
 120}
 121
 122static void write_temp_blob(char *tmpfile, const unsigned char *sha1)
 123{
 124        unsigned long size;
 125        void *blob;
 126        blob = grab_blob(sha1, &size);
 127        write_to_temp_file(tmpfile, blob, size);
 128        free(blob);
 129}
 130
 131static int parse_num(char **cp_p, unsigned int *num_p)
 132{
 133        char *cp = *cp_p;
 134        unsigned int num = 0;
 135        int read_some;
 136
 137        while ('0' <= *cp && *cp <= '9')
 138                num = num * 10 + *cp++ - '0';
 139        if (!(read_some = cp - *cp_p))
 140                return -1;
 141        *cp_p = cp;
 142        *num_p = num;
 143        return 0;
 144}
 145
 146static int parse_hunk_header(char *line, int len,
 147                             unsigned int *ob, unsigned int *on,
 148                             unsigned int *nb, unsigned int *nn)
 149{
 150        char *cp;
 151        cp = line + 4;
 152        if (parse_num(&cp, ob)) {
 153        bad_line:
 154                return error("malformed diff output: %s", line);
 155        }
 156        if (*cp == ',') {
 157                cp++;
 158                if (parse_num(&cp, on))
 159                        goto bad_line;
 160        }
 161        else
 162                *on = 1;
 163        if (*cp++ != ' ' || *cp++ != '+')
 164                goto bad_line;
 165        if (parse_num(&cp, nb))
 166                goto bad_line;
 167        if (*cp == ',') {
 168                cp++;
 169                if (parse_num(&cp, nn))
 170                        goto bad_line;
 171        }
 172        else
 173                *nn = 1;
 174        return -!!memcmp(cp, " @@", 3);
 175}
 176
 177static void append_lost(struct sline *sline, int n, const char *line)
 178{
 179        struct lline *lline;
 180        int len = strlen(line);
 181        unsigned long this_mask = (1UL<<n);
 182        if (line[len-1] == '\n')
 183                len--;
 184
 185        /* Check to see if we can squash things */
 186        if (sline->lost_head) {
 187                struct lline *last_one = NULL;
 188                /* We cannot squash it with earlier one */
 189                for (lline = sline->lost_head;
 190                     lline;
 191                     lline = lline->next)
 192                        if (lline->parent_map & this_mask)
 193                                last_one = lline;
 194                lline = last_one ? last_one->next : sline->lost_head;
 195                while (lline) {
 196                        if (lline->len == len &&
 197                            !memcmp(lline->line, line, len)) {
 198                                lline->parent_map |= this_mask;
 199                                return;
 200                        }
 201                        lline = lline->next;
 202                }
 203        }
 204
 205        lline = xmalloc(sizeof(*lline) + len + 1);
 206        lline->len = len;
 207        lline->next = NULL;
 208        lline->parent_map = this_mask;
 209        memcpy(lline->line, line, len);
 210        lline->line[len] = 0;
 211        *sline->lost_tail = lline;
 212        sline->lost_tail = &lline->next;
 213}
 214
 215static void combine_diff(const unsigned char *parent, const char *ourtmp,
 216                         struct sline *sline, int cnt, int n)
 217{
 218        FILE *in;
 219        char parent_tmp[TMPPATHLEN];
 220        char cmd[TMPPATHLEN * 2 + 1024];
 221        char line[MAXLINELEN];
 222        unsigned int lno, ob, on, nb, nn;
 223        unsigned long pmask = ~(1UL << n);
 224        struct sline *lost_bucket = NULL;
 225
 226        write_temp_blob(parent_tmp, parent);
 227        sprintf(cmd, "diff --unified=0 -La/x -Lb/x '%s' '%s'",
 228                parent_tmp, ourtmp);
 229        in = popen(cmd, "r");
 230        if (!in)
 231                return;
 232
 233        lno = 1;
 234        while (fgets(line, sizeof(line), in) != NULL) {
 235                int len = strlen(line);
 236                if (5 < len && !memcmp("@@ -", line, 4)) {
 237                        if (parse_hunk_header(line, len,
 238                                              &ob, &on, &nb, &nn))
 239                                break;
 240                        lno = nb;
 241                        if (!nb) {
 242                                /* @@ -1,2 +0,0 @@ to remove the
 243                                 * first two lines...
 244                                 */
 245                                nb = 1;
 246                        }
 247                        lost_bucket = &sline[nb-1]; /* sline is 0 based */
 248                        continue;
 249                }
 250                if (!lost_bucket)
 251                        continue;
 252                switch (line[0]) {
 253                case '-':
 254                        append_lost(lost_bucket, n, line+1);
 255                        break;
 256                case '+':
 257                        sline[lno-1].flag &= pmask;
 258                        lno++;
 259                        break;
 260                }
 261        }
 262        fclose(in);
 263        unlink(parent_tmp);
 264}
 265
 266static unsigned long context = 3;
 267static char combine_marker = '@';
 268
 269static int interesting(struct sline *sline, unsigned long all_mask)
 270{
 271        return ((sline->flag & all_mask) != all_mask || sline->lost_head);
 272}
 273
 274static unsigned long line_diff_parents(struct sline *sline, unsigned long all_mask)
 275{
 276        /*
 277         * Look at the line and see from which parents we have difference.
 278         * Lower bits of sline->flag records if the parent had this line,
 279         * so XOR with all_mask gives us on-bits for parents we have
 280         * differences with.
 281         */
 282        unsigned long parents = (sline->flag ^ all_mask);
 283        if (sline->lost_head) {
 284                struct lline *ll;
 285                for (ll = sline->lost_head; ll; ll = ll->next)
 286                        parents |= ll->parent_map;
 287        }
 288        return parents & all_mask;
 289}
 290
 291static void make_hunks(struct sline *sline, unsigned long cnt,
 292                       int num_parent, int dense)
 293{
 294        unsigned long all_mask = (1UL<<num_parent) - 1;
 295        unsigned long mark = (1UL<<num_parent);
 296        unsigned long i;
 297
 298        i = 0;
 299        while (i < cnt) {
 300                if (interesting(&sline[i], all_mask)) {
 301                        unsigned long j = (context < i) ? i - context : 0;
 302                        while (j <= i)
 303                                sline[j++].flag |= mark;
 304                        while (++i < cnt) {
 305                                if (!interesting(&sline[i], all_mask))
 306                                        break;
 307                                sline[i].flag |= mark;
 308                        }
 309                        j = (i + context < cnt) ? i + context : cnt;
 310                        while (i < j)
 311                                sline[i++].flag |= mark;
 312                        continue;
 313                }
 314                i++;
 315        }
 316        if (!dense)
 317                return;
 318
 319        /* Look at each hunk, and if it contains changes from only
 320         * one parent, mark that uninteresting.
 321         */
 322        i = 0;
 323        while (i < cnt) {
 324                int j, hunk_end, diffs;
 325                unsigned long parents;
 326                while (i < cnt && !(sline[i].flag & mark))
 327                        i++;
 328                if (cnt <= i)
 329                        break; /* No more interesting hunks */
 330                for (hunk_end = i + 1; hunk_end < cnt; hunk_end++)
 331                        if (!(sline[hunk_end].flag & mark))
 332                                break;
 333                /* [i..hunk_end) are interesting.  Now is it from
 334                 * only one parent?
 335                 * If lost lines are only from one parent and
 336                 * remaining lines existed in parents other than
 337                 * that parent, then the hunk is not that interesting.
 338                 */
 339                parents = 0;
 340                diffs = 0;
 341                for (j = i; j < hunk_end; j++)
 342                        parents |= line_diff_parents(sline + j, all_mask);
 343                /* Now, how many bits from [0..num_parent) are on? */
 344                for (j = 0; j < num_parent; j++) {
 345                        if (parents & (1UL<<j))
 346                                diffs++;
 347                }
 348                if (diffs < 2) {
 349                        /* This hunk is not that interesting after all */
 350                        for (j = i; j < hunk_end; j++)
 351                                sline[j].flag &= ~mark;
 352                }
 353                i = hunk_end;
 354        }
 355}
 356
 357static void dump_sline(struct sline *sline, int cnt, int num_parent)
 358{
 359        unsigned long mark = (1UL<<num_parent);
 360        int i;
 361        int lno = 0;
 362
 363        while (1) {
 364                struct sline *sl = &sline[lno];
 365                int hunk_end;
 366                while (lno < cnt && !(sline[lno].flag & mark))
 367                        lno++;
 368                if (cnt <= lno)
 369                        break;
 370                for (hunk_end = lno + 1; hunk_end < cnt; hunk_end++)
 371                        if (!(sline[hunk_end].flag & mark))
 372                                break;
 373                for (i = 0; i <= num_parent; i++) putchar(combine_marker);
 374                printf(" +%d,%d ", lno+1, hunk_end-lno);
 375                for (i = 0; i <= num_parent; i++) putchar(combine_marker);
 376                putchar('\n');
 377                while (lno < hunk_end) {
 378                        struct lline *ll;
 379                        int j;
 380                        sl = &sline[lno++];
 381                        ll = sl->lost_head;
 382                        while (ll) {
 383                                for (j = 0; j < num_parent; j++) {
 384                                        if (ll->parent_map & (1UL<<j))
 385                                                putchar('-');
 386                                        else
 387                                                putchar(' ');
 388                                }
 389                                puts(ll->line);
 390                                ll = ll->next;
 391                        }
 392                        for (j = 0; j < num_parent; j++) {
 393                                if ((1UL<<j) & sl->flag)
 394                                        putchar(' ');
 395                                else
 396                                        putchar('+');
 397                        }
 398                        printf("%.*s\n", sl->len, sl->bol);
 399                }
 400        }
 401}
 402
 403static void show_combined_diff(struct path_list *elem, int num_parent,
 404                               int dense)
 405{
 406        unsigned long size, cnt, lno;
 407        char *result, *cp, *ep;
 408        struct sline *sline; /* survived lines */
 409        int i;
 410        char ourtmp[TMPPATHLEN];
 411
 412        /* Read the result of merge first */
 413        result = grab_blob(elem->sha1, &size);
 414        write_to_temp_file(ourtmp, result, size);
 415
 416        for (cnt = 0, cp = result; cp - result < size; cp++) {
 417                if (*cp == '\n')
 418                        cnt++;
 419        }
 420        if (result[size-1] != '\n')
 421                cnt++; /* incomplete line */
 422
 423        sline = xcalloc(cnt, sizeof(*sline));
 424        ep = result;
 425        sline[0].bol = result;
 426        for (lno = 0, cp = result; cp - result < size; cp++) {
 427                if (*cp == '\n') {
 428                        sline[lno].lost_tail = &sline[lno].lost_head;
 429                        sline[lno].len = cp - sline[lno].bol;
 430                        sline[lno].flag = (1UL<<num_parent) - 1;
 431                        lno++;
 432                        if (lno < cnt)
 433                                sline[lno].bol = cp + 1;
 434                }
 435        }
 436        if (result[size-1] != '\n') {
 437                sline[cnt-1].lost_tail = &sline[cnt-1].lost_head;
 438                sline[cnt-1].len = size - (sline[cnt-1].bol - result);
 439                sline[cnt-1].flag = (1UL<<num_parent) - 1;
 440        }
 441
 442        for (i = 0; i < num_parent; i++)
 443                combine_diff(elem->parent_sha1[i], ourtmp, sline, cnt, i);
 444
 445        make_hunks(sline, cnt, num_parent, dense);
 446
 447        dump_sline(sline, cnt, num_parent);
 448        unlink(ourtmp);
 449        free(result);
 450
 451        for (i = 0; i < cnt; i++) {
 452                if (sline[i].lost_head) {
 453                        struct lline *ll = sline[i].lost_head;
 454                        while (ll) {
 455                                struct lline *tmp = ll;
 456                                ll = ll->next;
 457                                free(tmp);
 458                        }
 459                }
 460        }
 461        free(sline);
 462}
 463
 464int diff_tree_combined_merge(const unsigned char *sha1,
 465                             const char *header,
 466                             int show_empty_merge, int dense)
 467{
 468        struct commit *commit = lookup_commit(sha1);
 469        struct diff_options diffopts;
 470        struct commit_list *parents;
 471        struct path_list *p, *paths = NULL;
 472        int num_parent, i, num_paths;
 473
 474        diff_setup(&diffopts);
 475        diffopts.output_format = DIFF_FORMAT_NO_OUTPUT;
 476        diffopts.recursive = 1;
 477
 478        /* count parents */
 479        for (parents = commit->parents, num_parent = 0;
 480             parents;
 481             parents = parents->next, num_parent++)
 482                ; /* nothing */
 483
 484        /* find set of paths that everybody touches */
 485        for (parents = commit->parents, i = 0;
 486             parents;
 487             parents = parents->next, i++) {
 488                struct commit *parent = parents->item;
 489                diff_tree_sha1(parent->object.sha1, commit->object.sha1, "",
 490                               &diffopts);
 491                paths = intersect_paths(paths, i, num_parent);
 492                diff_flush(&diffopts);
 493        }
 494
 495        /* find out surviving paths */
 496        for (num_paths = 0, p = paths; p; p = p->next) {
 497                if (p->len)
 498                        num_paths++;
 499        }
 500        if (num_paths || show_empty_merge) {
 501                puts(header);
 502                for (p = paths; p; p = p->next) {
 503                        if (!p->len)
 504                                continue;
 505                        printf("diff --%s ", dense ? "cc" : "combined");
 506                        if (quote_c_style(p->path, NULL, NULL, 0))
 507                                quote_c_style(p->path, NULL, stdout, 0);
 508                        else
 509                                printf("%s", p->path);
 510                        putchar('\n');
 511                        show_combined_diff(p, num_parent, dense);
 512                }
 513        }
 514
 515        /* Clean things up */
 516        while (paths) {
 517                struct path_list *tmp = paths;
 518                paths = paths->next;
 519                free(tmp);
 520        }
 521        return 0;
 522}