line.c

   1 #include "cache.h"
   2 #include "tag.h"
   3 #include "blob.h"
   4 #include "tree.h"
   5 #include "diff.h"
   6 #include "commit.h"
   7 #include "decorate.h"
   8 #include "revision.h"
   9 #include "xdiff-interface.h"
  10 #include "strbuf.h"
  11 #include "log-tree.h"
  12 #include "graph.h"
  13 #include "line.h"
  14
  15 static int limited;
  16
  17 static void cleanup(struct diff_line_range *r)
  18 {
  19         while (r) {
  20                 struct diff_line_range *next = r->next;
  21                 DIFF_LINE_RANGE_CLEAR(r);
  22                 free(r);
  23                 r = next;
  24         }
  25 }
  26
  27 static struct object *verify_commit(struct rev_info *revs)
  28 {
  29         struct object *commit = NULL;
  30         int found = -1;
  31         int i;
  32
  33         for (i = 0; i < revs->pending.nr; i++) {
  34                 struct object *obj = revs->pending.objects[i].item;
  35                 if (obj->flags & UNINTERESTING)
  36                         continue;
  37                 while (obj->type == OBJ_TAG)
  38                         obj = deref_tag(obj, NULL, 0);
  39                 if (obj->type != OBJ_COMMIT)
  40                         die("Non commit %s?", revs->pending.objects[i].name);
  41                 if (commit)
  42                         die("More than one commit to dig from: %s and %s?",
  43                             revs->pending.objects[i].name,
  44                                 revs->pending.objects[found].name);
  45                 commit = obj;
  46                 found = i;
  47         }
  48
  49         if (commit == NULL)
  50                 die("No commit specified?");
  51
  52         return commit;
  53 }
  54
  55 static void fill_blob_sha1(struct commit *commit, struct diff_line_range *r)
  56 {
  57         unsigned mode;
  58         unsigned char sha1[20];
  59
  60         while (r) {
  61                 if (get_tree_entry(commit->object.sha1, r->spec->path,
  62                         sha1, &mode))
  63                         goto error;
  64                 fill_filespec(r->spec, sha1, mode);
  65                 r = r->next;
  66         }
  67
  68         return;
  69 error:
  70         die("There is no path %s in the commit", r->spec->path);
  71 }
  72
  73 static void fill_line_ends(struct diff_filespec *spec, long *lines,
  74         unsigned long **line_ends)
  75 {
  76         int num = 0, size = 50;
  77         long cur = 0;
  78         unsigned long *ends = NULL;
  79         char *data = NULL;
  80
  81         if (diff_populate_filespec(spec, 0))
  82                 die("Cannot read blob %s", sha1_to_hex(spec->sha1));
  83
  84         ends = xmalloc(size * sizeof(*ends));
  85         ends[cur++] = 0;
  86         data = spec->data;
  87         while (num < spec->size) {
  88                 if (data[num] == '\n' || num == spec->size - 1) {
  89                         ALLOC_GROW(ends, (cur + 1), size);
  90                         ends[cur++] = num;
  91                 }
  92                 num++;
  93         }
  94
  95         /* shrink the array to fit the elements */
  96         ends = xrealloc(ends, cur * sizeof(*ends));
  97         *lines = cur;
  98         *line_ends = ends;
  99 }
 100
 101 struct nth_line_cb {
 102         struct diff_filespec *spec;
 103         long lines;
 104         unsigned long *line_ends;
 105 };
 106
 107 static const char *nth_line(void *data, long line)
 108 {
 109         struct nth_line_cb *d = data;
 110         assert(d && line < d->lines);
 111         assert(d->spec && d->spec->data);
 112
 113         if (line == 0)
 114                 return (char *)d->spec->data;
 115         else
 116                 return (char *)d->spec->data + d->line_ends[line] + 1;
 117 }
 118
 119 /*
 120  * Parsing of (comma separated) one item in the -L option
 121  */
 122 const char *parse_loc(const char *spec, nth_line_fn_t nth_line,
 123                 void *data, long lines, long begin, long *ret)
 124 {
 125         char *term;
 126         const char *line;
 127         long num;
 128         int reg_error;
 129         regex_t regexp;
 130         regmatch_t match[1];
 131
 132         /* Catch the '$' matcher, now it is used to match the last
 133          * line of the file. */
 134         if (spec[0] == '$') {
 135                 *ret = lines;
 136                 return spec + 1;
 137         }
 138
 139         /* Allow "-L <something>,+20" to mean starting at <something>
 140          * for 20 lines, or "-L <something>,-5" for 5 lines ending at
 141          * <something>.
 142          */
 143         if (1 < begin && (spec[0] == '+' || spec[0] == '-')) {
 144                 num = strtol(spec + 1, &term, 10);
 145                 if (term != spec + 1) {
 146                         if (spec[0] == '-')
 147                                 num = 0 - num;
 148                         if (0 < num)
 149                                 *ret = begin + num - 2;
 150                         else if (!num)
 151                                 *ret = begin;
 152                         else
 153                                 *ret = begin + num;
 154                         return term;
 155                 }
 156                 return spec;
 157         }
 158         num = strtol(spec, &term, 10);
 159         if (term != spec) {
 160                 *ret = num;
 161                 return term;
 162         }
 163         if (spec[0] != '/')
 164                 return spec;
 165
 166         /* it could be a regexp of form /.../ */
 167         for (term = (char *) spec + 1; *term && *term != '/'; term++) {
 168                 if (*term == '\\')
 169                         term++;
 170         }
 171         if (*term != '/')
 172                 return spec;
 173
 174         /* try [spec+1 .. term-1] as regexp */
 175         *term = 0;
 176         begin--; /* input is in human terms */
 177         line = nth_line(data, begin);
 178
 179         if (!(reg_error = regcomp(&regexp, spec + 1, REG_NEWLINE)) &&
 180             !(reg_error = regexec(&regexp, line, 1, match, 0))) {
 181                 const char *cp = line + match[0].rm_so;
 182                 const char *nline;
 183
 184                 while (begin++ < lines) {
 185                         nline = nth_line(data, begin);
 186                         if (line <= cp && cp < nline)
 187                                 break;
 188                         line = nline;
 189                 }
 190                 *ret = begin;
 191                 regfree(&regexp);
 192                 *term++ = '/';
 193                 return term;
 194         } else {
 195                 char errbuf[1024];
 196                 regerror(reg_error, &regexp, errbuf, 1024);
 197                 die("-L parameter '%s': %s", spec + 1, errbuf);
 198         }
 199 }
 200
 201 static void parse_range(long lines, unsigned long *line_ends,
 202                 struct line_range *r, struct diff_filespec *spec)
 203 {
 204         const char *term;
 205         struct nth_line_cb data = {spec, lines, line_ends};
 206
 207         term = parse_loc(r->arg, nth_line, &data, lines - 1, 1, &r->start);
 208         if (*term == ',') {
 209                 term = parse_loc(term + 1, nth_line, &data, lines - 1,
 210                         r->start + 1, &r->end);
 211                 if (*term)
 212                         die("-L parameter's argument should be <start>,<end>");
 213         }
 214
 215         if (*term)
 216                 die("-L parameter's argument should be <start>,<end>");
 217
 218         if (r->start < 1)
 219                 r->start = 1;
 220         if (r->end >= lines)
 221                 r->end = lines - 1;
 222
 223         if (r->start > r->end) {
 224                 long tmp = r->start;
 225                 r->start = r->end;
 226                 r->end = tmp;
 227         }
 228 }
 229
 230 static void parse_lines(struct commit *commit, struct diff_line_range *r)
 231 {
 232         int i;
 233         struct line_range *old_range = NULL;
 234         long lines = 0;
 235         unsigned long *ends = NULL;
 236
 237         while (r) {
 238                 struct diff_filespec *spec = r->spec;
 239                 int num = r->nr;
 240                 assert(spec);
 241                 fill_blob_sha1(commit, r);
 242                 old_range = r->ranges;
 243                 r->ranges = NULL;
 244                 r->nr = r->alloc = 0;
 245                 fill_line_ends(spec, &lines, &ends);
 246                 for (i = 0; i < num; i++) {
 247                         parse_range(lines, ends, old_range + i, spec);
 248                         diff_line_range_insert(r, old_range[i].arg,
 249                                 old_range[i].start, old_range[i].end);
 250                 }
 251
 252                 free(ends);
 253                 ends = NULL;
 254
 255                 r = r->next;
 256                 free(old_range);
 257         }
 258 }
 259
 260 /*
 261  * Insert a new line range into a diff_line_range struct, and keep the
 262  * r->ranges sorted by their starting line number.
 263  */
 264 struct line_range *diff_line_range_insert(struct diff_line_range *r,
 265                 const char *arg, int start, int end)
 266 {
 267         int i = 0;
 268         struct line_range *rs = r->ranges;
 269         int left_merge = 0, right_merge = 0;
 270
 271         assert(r != NULL);
 272         assert(start <= end);
 273
 274         if (r->nr == 0 || rs[r->nr - 1].end < start - 1) {
 275                 int num = 0;
 276                 DIFF_LINE_RANGE_GROW(r);
 277                 rs = r->ranges;
 278                 num = r->nr - 1;
 279                 rs[num].arg = arg;
 280                 rs[num].start = start;
 281                 rs[num].end = end;
 282                 return rs + num;
 283         }
 284
 285         for (; i < r->nr; i++) {
 286                 if (rs[i].end < start - 1)
 287                         continue;
 288                 if (rs[i].end == start - 1) {
 289                         rs[i].end = end;
 290                         right_merge = 1;
 291                         goto out;
 292                 }
 293
 294                 assert(rs[i].end > start - 1);
 295                 if (rs[i].start <= start) {
 296                         if (rs[i].end < end) {
 297                                 rs[i].end = end;
 298                                 right_merge = 1;
 299                         }
 300                         goto out;
 301                 } else if (rs[i].start <= end + 1) {
 302                         rs[i].start = start;
 303                         left_merge = 1;
 304                         if (rs[i].end < end) {
 305                                 rs[i].end = end;
 306                                 right_merge = 1;
 307                         }
 308                         goto out;
 309                 } else {
 310                         int num = r->nr - i;
 311                         DIFF_LINE_RANGE_GROW(r);
 312                         rs = r->ranges;
 313                         memmove(rs + i + 1, rs + i, num * sizeof(struct line_range));
 314                         rs[i].arg = arg;
 315                         rs[i].start = start;
 316                         rs[i].end = end;
 317                         goto out;
 318                 }
 319         }
 320
 321 out:
 322         assert(r->nr != i);
 323         if (left_merge) {
 324                 int j = i;
 325                 for (; j > -1; j--) {
 326                         if (rs[j].end >= rs[i].start - 1)
 327                                 if (rs[j].start < rs[i].start)
 328                                         rs[i].start = rs[j].start;
 329                 }
 330                 memmove(rs + j + 1, rs + i, (r->nr - i) * sizeof(struct line_range));
 331                 r->nr -= i - j - 1;
 332         }
 333         if (right_merge) {
 334                 int j = i;
 335                 for (; j < r->nr; j++) {
 336                         if (rs[j].start <= rs[i].end + 1)
 337                                 if (rs[j].end > rs[i].end)
 338                                         rs[i].end = rs[j].end;
 339                 }
 340                 if (j < r->nr)
 341                         memmove(rs + i + 1, rs + j, (r->nr - j) * sizeof(struct line_range));
 342                 r->nr -= j - i - 1;
 343         }
 344         assert(r->nr);
 345
 346         return rs + i;
 347 }
 348
 349 void diff_line_range_clear(struct diff_line_range *r)
 350 {
 351         int i = 0, zero = 0;
 352
 353         for (; i < r->nr; i++) {
 354                 struct line_range *rg = r->ranges + i;
 355                 RANGE_CLEAR(rg);
 356         }
 357
 358         if (r->prev) {
 359                 zero = 0;
 360                 if (r->prev->count == 1)
 361                         zero = 1;
 362                 free_filespec(r->prev);
 363                 if (zero)
 364                         r->prev = NULL;
 365         }
 366         if (r->spec) {
 367                 zero = 0;
 368                 if (r->spec->count == 1)
 369                         zero = 1;
 370                 free_filespec(r->spec);
 371                 if (zero)
 372                         r->spec = NULL;
 373         }
 374
 375         r->status = '\0';
 376         r->alloc = r->nr = 0;
 377
 378         if (r->ranges)
 379                 free(r->ranges);
 380         r->ranges = NULL;
 381         r->next = NULL;
 382 }
 383
 384 void diff_line_range_append(struct diff_line_range *r, const char *arg)
 385 {
 386         DIFF_LINE_RANGE_GROW(r);
 387         r->ranges[r->nr - 1].arg = arg;
 388 }
 389
 390 struct diff_line_range *diff_line_range_clone(struct diff_line_range *r)
 391 {
 392         struct diff_line_range *ret = xmalloc(sizeof(*ret));
 393         int i = 0;
 394
 395         assert(r);
 396         DIFF_LINE_RANGE_INIT(ret);
 397         ret->ranges = xcalloc(r->nr, sizeof(struct line_range));
 398         memcpy(ret->ranges, r->ranges, sizeof(struct line_range) * r->nr);
 399
 400         ret->alloc = ret->nr = r->nr;
 401
 402         for (; i < ret->nr; i++)
 403                 PRINT_PAIR_INIT(&ret->ranges[i].pair);
 404
 405         ret->spec = r->spec;
 406         assert(ret->spec);
 407         ret->spec->count++;
 408
 409         return ret;
 410 }
 411
 412 struct diff_line_range *diff_line_range_clone_deeply(struct diff_line_range *r)
 413 {
 414         struct diff_line_range *ret = NULL;
 415         struct diff_line_range *tmp = NULL, *prev = NULL;
 416
 417         assert(r);
 418         ret = tmp = prev = diff_line_range_clone(r);
 419         r = r->next;
 420         while (r) {
 421                 tmp = diff_line_range_clone(r);
 422                 prev->next = tmp;
 423                 prev = tmp;
 424                 r = r->next;
 425         }
 426
 427         return ret;
 428 }
 429
 430 struct diff_line_range *diff_line_range_merge(struct diff_line_range *out,
 431                 struct diff_line_range *other)
 432 {
 433         struct diff_line_range *one = out, *two = other;
 434         struct diff_line_range *pone = NULL;
 435
 436         while (one) {
 437                 struct diff_line_range *ptwo;
 438                 two = other;
 439                 ptwo = other;
 440                 while (two) {
 441                         if (!strcmp(one->spec->path, two->spec->path)) {
 442                                 int i = 0;
 443                                 for (; i < two->nr; i++) {
 444                                         diff_line_range_insert(one, NULL,
 445                                                 two->ranges[i].start,
 446                                                 two->ranges[i].end);
 447                                 }
 448                                 if (two == other)
 449                                         other = other->next;
 450                                 else
 451                                         ptwo->next = two->next;
 452                                 DIFF_LINE_RANGE_CLEAR(two);
 453                                 free(two);
 454                                 two = NULL;
 455
 456                                 break;
 457                         }
 458
 459                         ptwo = two;
 460                         two = two->next;
 461                 }
 462
 463                 pone = one;
 464                 one = one->next;
 465         }
 466         pone->next = other;
 467
 468         return out;
 469 }
 470
 471 void add_line_range(struct rev_info *revs, struct commit *commit,
 472                 struct diff_line_range *r)
 473 {
 474         struct diff_line_range *ret = NULL;
 475
 476         ret = lookup_decoration(&revs->line_range, &commit->object);
 477         if (ret != NULL && r != NULL)
 478                 diff_line_range_merge(ret, r);
 479         else
 480                 add_decoration(&revs->line_range, &commit->object, r);
 481
 482         if (r != NULL)
 483                 commit->object.flags |= RANGE_UPDATE;
 484 }
 485
 486 struct diff_line_range *lookup_line_range(struct rev_info *revs,
 487                 struct commit *commit)
 488 {
 489         struct diff_line_range *ret = NULL;
 490
 491         ret = lookup_decoration(&revs->line_range, &commit->object);
 492         return ret;
 493 }
 494
 495 void setup_line(struct rev_info *rev, struct diff_line_range *r)
 496 {
 497         struct commit *commit = NULL;
 498         struct diff_options *opt = &rev->diffopt;
 499
 500         commit = (struct commit *)verify_commit(rev);
 501         parse_lines(commit, r);
 502
 503         add_line_range(rev, commit, r);
 504         /*
 505          * Note we support -M/-C to detect file rename
 506          */
 507         opt->nr_paths = 0;
 508         diff_tree_release_paths(opt);
 509 }
 510
 511 struct take_range_cb_data {
 512         struct diff_line_range *interesting;    /* currently interesting ranges */
 513         struct diff_line_range *range;
 514                 /* the ranges corresponds to the interesting ranges of parent commit */
 515         long plno, tlno;
 516                 /* the last line number of diff hunk */
 517         int diff;
 518                 /* whether there is some line changes between the current
 519                  * commit and its parent */
 520 };
 521
 522 #define SCALE_FACTOR 4
 523 /*
 524  * [p_start, p_end] represents the pre-image of current diff hunk,
 525  * [t_start, t_end] represents the post-image of the current diff hunk,
 526  * [start, end] represents the currently interesting line range in
 527  * post-image,
 528  * [o_start, o_end] represents the original line range that coresponds
 529  * to current line range.
 530  */
 531 void map_lines(long p_start, long p_end, long t_start, long t_end,
 532                 long start, long end, long *o_start, long *o_end)
 533 {
 534         /*
 535          * Normally, p_start should be less than p_end, so does the
 536          * t_start and t_end. But when the line range is added from
 537          * scratch, p_start will be greater than p_end. When the line
 538          * range is deleted, t_start will be greater than t_end.
 539          */
 540         if (p_start > p_end) {
 541                 *o_start = *o_end = 0;
 542                 return;
 543         }
 544         /* A deletion */
 545         if (t_start > t_end) {
 546                 *o_start = p_start;
 547                 *o_end = p_end;
 548                 return;
 549         }
 550
 551         if (start == t_start && end == t_end) {
 552                 *o_start = p_start;
 553                 *o_end = p_end;
 554                 return;
 555         }
 556
 557         if (start == t_start) {
 558                 *o_start = p_start;
 559                 *o_end = p_start + (end - start);
 560                 if (*o_end > p_end)
 561                         *o_end = p_end;
 562                 return;
 563         }
 564
 565         if (end == t_end) {
 566                 *o_start = p_end - (end - start);
 567                 if (*o_start < p_start)
 568                         *o_start = p_start;
 569                 *o_end = p_end;
 570                 return;
 571         }
 572
 573         /*
 574          * A heuristic for lines mapping:
 575          *
 576          * When the pre-image is no more than 1/SCALE_FACTOR of the post-image,
 577          * there is no effective way to find out which part of pre-image
 578          * corresponds to the currently interesting range of post-image.
 579          * And we are in the danger of tracking totally useless lines.
 580          * So, we just treat all the post-image lines as added from scratch.
 581          */
 582         if (SCALE_FACTOR * (p_end - p_start + 1) < (t_end - t_start + 1)) {
 583                 *o_start = *o_end = 0;
 584                 return;
 585         }
 586
 587         *o_start = p_start + start - t_start;
 588         *o_end = p_end - (t_end - end);
 589
 590         if (*o_start > *o_end) {
 591                 int temp = *o_start;
 592                 *o_start = *o_end;
 593                 *o_end = temp;
 594         }
 595
 596         if (*o_start < p_start)
 597                 *o_start = p_start;
 598         if (*o_end > p_end)
 599                 *o_end = p_end;
 600 }
 601
 602 /*
 603  * When same == 1:
 604  * [p_start, p_end] represents the diff hunk line range of pre-image,
 605  * [t_start, t_end] represents the diff hunk line range of post-image.
 606  * When same == 0, they represent a range of identical lines between
 607  * two images.
 608  *
 609  * This function find out the corresponding line ranges of currently
 610  * interesting ranges which this diff hunk touches.
 611  */
 612 static void map_range(struct take_range_cb_data *data, int same,
 613                 long p_start, long p_end, long t_start, long t_end)
 614 {
 615         struct line_range *ranges = data->interesting->ranges;
 616         long takens, takene, start, end;
 617         int i = 0, out = 0, added = 0;
 618         long op_start = p_start, op_end = p_end, ot_start = t_start, ot_end = t_end;
 619
 620         for (; i < data->interesting->nr; i++) {
 621                 added = 0;
 622                 if (t_start > ranges[i].end)
 623                         continue;
 624                 if (t_end < ranges[i].start)
 625                         break;
 626
 627                 if (t_start > ranges[i].start) {
 628                         start = t_start;
 629                         takens = p_start;
 630                         if (t_end >= ranges[i].end) {
 631                                 end = ranges[i].end;
 632                                 takene = p_start + end - t_start;
 633                         } else {
 634                                 end = t_end;
 635                                 takene = p_end;
 636                                 out = 1;
 637                         }
 638                 } else {
 639                         start = ranges[i].start;
 640                         takens = p_start + start - t_start;
 641                         if (t_end >= ranges[i].end) {
 642                                 end = ranges[i].end;
 643                                 takene = p_start + end - t_start;
 644                         } else {
 645                                 end = t_end;
 646                                 takene = p_end;
 647                                 out = 1;
 648                         }
 649                 }
 650
 651                 if (!same) {
 652                         struct print_pair *pair = &ranges[i].pair;
 653                         struct print_range *rr = NULL;
 654                         PRINT_PAIR_GROW(pair);
 655                         rr = pair->ranges + pair->nr - 1;
 656                         PRINT_RANGE_INIT(rr);
 657                         rr->start = start;
 658                         rr->end = end;
 659                         map_lines(op_start, op_end, ot_start, ot_end, start, end,
 660                                         &takens, &takene);
 661                         if (takens == 0 && takene == 0) {
 662                                 added = 1;
 663                                 rr->line_added = 1;
 664                         }
 665                         rr->pstart = takens;
 666                         rr->pend = takene;
 667                         data->diff = 1;
 668                         data->interesting->diff = 1;
 669                         ranges[i].diff = 1;
 670                 }
 671                 if (added) {
 672                         /* Code movement/copy detect here, now place two dummy statements here */
 673                         int dummy = 0;
 674                         dummy = 1;
 675                 } else {
 676                         struct line_range *added_range = diff_line_range_insert(data->range,
 677                                         NULL, takens, takene);
 678                         assert(added_range);
 679                         ranges[i].pstart = added_range->start;
 680                         ranges[i].pend = added_range->end;
 681                 }
 682
 683                 t_start = end + 1;
 684                 p_start = takene + 1;
 685
 686                 if (out)
 687                         break;
 688         }
 689 }
 690
 691 /*
 692  * [p_start, p_end] represents the line range of pre-image,
 693  * [t_start, t_end] represents the line range of post-image,
 694  * and they are identical lines.
 695  *
 696  * This function substracts out the identical lines between current
 697  * commit and its parent, from currently interesting ranges.
 698  */
 699 static void take_range(struct take_range_cb_data *data,
 700                 long p_start, long p_end, long t_start, long t_end)
 701 {
 702         struct line_range *ranges = data->interesting->ranges;
 703         long takens, takene, start, end;
 704         int i = 0, out = 0, added = 0;
 705
 706         for (; i < data->interesting->nr; i++) {
 707                 added = 0;
 708                 if (t_start > ranges[i].end)
 709                         continue;
 710                 if (t_end < ranges[i].start)
 711                         break;
 712
 713                 if (t_start > ranges[i].start) {
 714                         long tmp = ranges[i].end;
 715                         ranges[i].end = t_start - 1;
 716                         start = t_start;
 717                         takens = p_start;
 718                         if (t_end >= tmp) {
 719                                 end = tmp;
 720                                 takene = p_start + end - t_start;
 721                                 p_start = takene + 1;
 722                                 t_start = end + 1;
 723                         } else {
 724                                 end = t_end;
 725                                 takene = p_end;
 726                                 diff_line_range_insert(data->interesting, NULL,
 727                                         t_end + 1, tmp);
 728                                 out = 1;
 729                         }
 730                 } else {
 731                         start = ranges[i].start;
 732                         takens = p_start + start - t_start;
 733                         if (t_end >= ranges[i].end) {
 734                                 int num = data->interesting->nr - 1;
 735                                 end = ranges[i].end;
 736                                 takene = p_start + end - t_start;
 737                                 t_start = end + 1;
 738                                 p_start = takene + 1;
 739                                 memmove(ranges + i, ranges + i + 1, (num - i) * sizeof(*ranges));
 740                                 data->interesting->nr = num;
 741                                 i--;
 742                         } else {
 743                                 end = t_end;
 744                                 takene = p_end;
 745                                 ranges[i].start = t_end + 1;
 746                                 out = 1;
 747                         }
 748                 }
 749
 750                 diff_line_range_insert(data->range, NULL, takens, takene);
 751
 752                 if (out)
 753                         break;
 754         }
 755 }
 756
 757 static void take_range_cb(void *data, long same, long p_next, long t_next)
 758 {
 759         struct take_range_cb_data *d = data;
 760         long p_start = d->plno + 1, t_start = d->tlno + 1;
 761         long p_end = p_start + same - t_start, t_end = same;
 762
 763         /* If one file is added from scratch, we should not bother to call
 764          * take_range, since there is nothing to take
 765          */
 766         if (t_end >= t_start)
 767                 take_range(d, p_start, p_end, t_start, t_end);
 768         d->plno = p_next;
 769         d->tlno = t_next;
 770 }
 771
 772 static void map_range_cb(void *data, long same, long p_next, long t_next)
 773 {
 774         struct take_range_cb_data *d = data;
 775
 776         long p_start = d->plno + 1;
 777         long t_start = d->tlno + 1;
 778         long p_end = same - t_start + p_start;
 779         long t_end = same;
 780
 781         /* Firstly, take the unchanged lines from child */
 782         if (t_end >= t_start)
 783                 map_range(d, 1, p_start, p_end, t_start, t_end);
 784
 785         /* find out which lines to print */
 786         t_start = same + 1;
 787         p_start = d->plno + t_start - d->tlno;
 788         map_range(d, 0, p_start, p_next, t_start, t_next);
 789
 790         d->plno = p_next;
 791         d->tlno = t_next;
 792 }
 793
 794 /*
 795  * We support two kinds of operation in this function:
 796  * 1. map == 0, take the same lines from the current commit and assign it
 797  *              to parent;
 798  * 2. map == 1, in addition to the same lines, we also map the changed lines
 799  *              from the current commit to the parent according to the
 800  *              diff output.
 801  * take_range_cb and take_range are used to take same lines from current commit
 802  * to parents.
 803  * map_range_cb and map_range are used to map line ranges to the parent.
 804  */
 805 static int assign_range_to_parent(struct rev_info *rev, struct commit *c,
 806                 struct commit *p, struct diff_line_range *r,
 807                 struct diff_options *opt, int map)
 808 {
 809         struct diff_line_range *rr = xmalloc(sizeof(*rr));
 810         struct diff_line_range *cr = rr, *prev_r = rr;
 811         struct diff_line_range *rg = NULL;
 812         struct tree_desc desc1, desc2;
 813         void *tree1 = NULL, *tree2 = NULL;
 814         unsigned long size1, size2;
 815         struct diff_queue_struct *queue;
 816         struct take_range_cb_data cb = {NULL, cr, 0, 0};
 817         xpparam_t xpp;
 818         xdemitconf_t xecfg;
 819         int i, diff = 0;
 820         xdiff_emit_hunk_consume_fn fn = map ? map_range_cb : take_range_cb;
 821
 822         DIFF_LINE_RANGE_INIT(cr);
 823         memset(&xpp, 0, sizeof(xpp));
 824         memset(&xecfg, 0, sizeof(xecfg));
 825         xecfg.ctxlen = xecfg.interhunkctxlen = 0;
 826
 827         /*
 828          * Compose up two trees, for root commit, we make up a empty tree.
 829          */
 830         assert(c);
 831         tree2 = read_object_with_reference(c->tree->object.sha1, "tree",
 832                         &size2, NULL);
 833         if (tree2 == NULL)
 834                 die("Unable to read tree (%s)", sha1_to_hex(c->tree->object.sha1));
 835         init_tree_desc(&desc2, tree2, size2);
 836         if (p) {
 837                 tree1 = read_object_with_reference(p->tree->object.sha1,
 838                                 "tree", &size1, NULL);
 839                 if (tree1 == NULL)
 840                         die("Unable to read tree (%s)",
 841                                         sha1_to_hex(p->tree->object.sha1));
 842                 init_tree_desc(&desc1, tree1, size1);
 843         } else {
 844                 init_tree_desc(&desc1, "", 0);
 845         }
 846
 847         DIFF_QUEUE_CLEAR(&diff_queued_diff);
 848         diff_tree(&desc1, &desc2, "", opt);
 849         diffcore_std(opt);
 850
 851         queue = &diff_queued_diff;
 852         for (i = 0; i < queue->nr; i++) {
 853                 struct diff_filepair *pair = queue->queue[i];
 854                 struct diff_line_range *rg = r;
 855                 mmfile_t file_p, file_t;
 856                 assert(pair->two->path);
 857                 while (rg) {
 858                         assert(rg->spec->path);
 859                         if (!strcmp(rg->spec->path, pair->two->path))
 860                                 break;
 861                         rg = rg->next;
 862                 }
 863
 864                 if (rg == NULL)
 865                         continue;
 866                 rg->touch = 1;
 867                 if (rg->nr == 0)
 868                         continue;
 869
 870                 rg->status = pair->status;
 871                 assert(pair->two->sha1_valid);
 872                 diff_populate_filespec(pair->two, 0);
 873                 file_t.ptr = pair->two->data;
 874                 file_t.size = pair->two->size;
 875
 876                 if (rg->prev)
 877                         free_filespec(rg->prev);
 878                 rg->prev = pair->one;
 879                 rg->prev->count++;
 880                 if (pair->one->sha1_valid) {
 881                         diff_populate_filespec(pair->one, 0);
 882                         file_p.ptr = pair->one->data;
 883                         file_p.size = pair->one->size;
 884                 } else {
 885                         file_p.ptr = "";
 886                         file_p.size = 0;
 887                 }
 888
 889                 if (cr->nr != 0) {
 890                         struct diff_line_range *tmp = xmalloc(sizeof(*tmp));
 891                         cr->next = tmp;
 892                         prev_r = cr;
 893                         cr = tmp;
 894                 } else if (cr->spec)
 895                         DIFF_LINE_RANGE_CLEAR(cr);
 896
 897                 DIFF_LINE_RANGE_INIT(cr);
 898                 if (pair->one->sha1_valid) {
 899                         cr->spec = pair->one;
 900                         cr->spec->count++;
 901                 }
 902
 903                 cb.interesting = rg;
 904                 cb.range = cr;
 905                 cb.diff = 0;
 906                 cb.plno = cb.tlno = 0;
 907                 xdi_diff_hunks(&file_p, &file_t, fn, &cb, &xpp, &xecfg);
 908                 if (cb.diff)
 909                         diff = 1;
 910                 /*
 911                  * The remain part is the same part.
 912                  * Instead of calculating the true line number of the two files,
 913                  * use the biggest integer.
 914                  */
 915                 if (map)
 916                         map_range(&cb, 1, cb.plno + 1, INT_MAX, cb.tlno + 1, INT_MAX);
 917                 else
 918                         take_range(&cb, cb.plno + 1, INT_MAX, cb.tlno + 1, INT_MAX);
 919         }
 920         opt->output_format = DIFF_FORMAT_NO_OUTPUT;
 921         diff_flush(opt);
 922
 923         /*
 924          * Collect the untouch ranges, this comes from the files not changed
 925          * between two commit.
 926          */
 927         rg = r;
 928         while (rg) {
 929                 /* clear the touch one to make it usable in next round */
 930                 if (rg->touch) {
 931                         rg->touch = 0;
 932                 } else {
 933                         struct diff_line_range *untouch = diff_line_range_clone(rg);
 934                         if (prev_r == rr && rr->nr == 0) {
 935                                 rr = prev_r = untouch;
 936                         } else {
 937                                 prev_r->next = untouch;
 938                                 prev_r = untouch;
 939                         }
 940                 }
 941                 rg = rg->next;
 942         }
 943
 944         if (cr->nr == 0) {
 945                 DIFF_LINE_RANGE_CLEAR(cr);
 946                 free(cr);
 947                 if (prev_r == cr)
 948                         rr = NULL;
 949                 else
 950                         prev_r->next = NULL;
 951         }
 952
 953         if (!map)
 954                 goto out;
 955
 956         if (rr) {
 957                 assert(p);
 958                 add_line_range(rev, p, rr);
 959         } else {
 960                 /*
 961                  * If there is no new ranges assigned to the parent,
 962                  * we should mark it as a 'root' commit.
 963                  */
 964                 free(c->parents);
 965                 c->parents = NULL;
 966         }
 967
 968         /* and the ranges of current commit c is updated */
 969         c->object.flags &= ~RANGE_UPDATE;
 970         if (diff)
 971                 c->object.flags |= NEED_PRINT;
 972
 973 out:
 974         if (tree1)
 975                 free(tree1);
 976         if (tree2)
 977                 free(tree2);
 978
 979         return diff;
 980 }
 981
 982 static void diff_update_parent_range(struct rev_info *rev,
 983                 struct commit *commit)
 984 {
 985         struct diff_line_range *r = lookup_line_range(rev, commit);
 986         struct commit_list *parents = commit->parents;
 987         struct commit *c = NULL;
 988         if (parents) {
 989                 assert(parents->next == NULL);
 990                 c = parents->item;
 991         }
 992
 993         assign_range_to_parent(rev, commit, c, r, &rev->diffopt, 1);
 994 }
 995
 996 struct commit_state {
 997         struct diff_line_range *range;
 998         struct object obj;
 999 };
1000
1001 static void assign_parents_range(struct rev_info *rev, struct commit *commit)
1002 {
1003         struct commit_list *parents = commit->parents;
1004         struct diff_line_range *r = lookup_line_range(rev, commit);
1005         struct diff_line_range *evil = NULL, *range = NULL;
1006         struct decoration parents_state;
1007         struct commit_state *state = NULL;
1008         int nontrivial = 0;
1009
1010         memset(&parents_state, 0, sizeof(parents_state));
1011         /*
1012          * If we are in linear history, update range and flush the patch if
1013          * necessary
1014          */
1015         if (parents == NULL || parents->next == NULL)
1016                 return diff_update_parent_range(rev, commit);
1017
1018         /*
1019          * Loop on the parents and assign the ranges to different
1020          * parents, if there is any range left, this commit must
1021          * be an evil merge.
1022          */
1023         evil = diff_line_range_clone_deeply(r);
1024         parents = commit->parents;
1025         while (parents) {
1026                 struct commit *p = parents->item;
1027                 int diff = 0;
1028                 struct diff_line_range *origin_range = lookup_line_range(rev, p);
1029                 if (origin_range)
1030                         origin_range = diff_line_range_clone_deeply(origin_range);
1031
1032                 state = xmalloc(sizeof(*state));
1033                 state->range = origin_range;
1034                 state->obj = p->object;
1035                 add_decoration(&parents_state, &p->object, state);
1036                 diff = assign_range_to_parent(rev, commit, p, r, &rev->diffopt, 1);
1037                 /* Since all the ranges comes from this parent, we can ignore others */
1038                 if (diff == 0) {
1039                         /* restore the state of parents before this one */
1040                         parents = commit->parents;
1041                         while (parents->item != p) {
1042                                 struct commit_list *list = parents;
1043                                 struct diff_line_range *line_range = NULL;
1044                                 parents = parents->next;
1045                                 line_range = lookup_line_range(rev, list->item);
1046                                 cleanup(line_range);
1047                                 state = lookup_decoration(&parents_state, &list->item->object);
1048                                 add_decoration(&parents_state, &list->item->object, NULL);
1049                                 add_line_range(rev, list->item, state->range);
1050                                 list->item->object = state->obj;
1051                                 free(state);
1052                                 free(list);
1053                         }
1054
1055                         commit->parents = parents;
1056                         parents = parents->next;
1057                         commit->parents->next = NULL;
1058
1059                         /* free the non-use commit_list */
1060                         while (parents) {
1061                                 struct commit_list *list = parents;
1062                                 parents = parents->next;
1063                                 free(list);
1064                         }
1065                         goto out;
1066                 }
1067                 /* take the ranges from 'commit', try to detect nontrivial merge */
1068                 assign_range_to_parent(rev, commit, p, evil, &rev->diffopt, 0);
1069                 parents = parents->next;
1070         }
1071
1072         commit->object.flags |= NONTRIVIAL_MERGE;
1073         /*
1074          * yes, this must be an evil merge.
1075          */
1076         range = evil;
1077         while (range) {
1078                 if (range->nr) {
1079                         commit->object.flags |= EVIL_MERGE;
1080                         nontrivial = 1;
1081                 }
1082                 range = range->next;
1083         }
1084
1085 out:
1086         /* Never print out any diff for a merge commit */
1087         commit->object.flags &= ~NEED_PRINT;
1088
1089         parents = commit->parents;
1090         while (parents) {
1091                 state = lookup_decoration(&parents_state, &parents->item->object);
1092                 if (state) {
1093                         cleanup(state->range);
1094                         free(state);
1095                 }
1096                 parents = parents->next;
1097         }
1098
1099         if (nontrivial)
1100                 add_decoration(&rev->nontrivial_merge, &commit->object, evil);
1101         else
1102                 cleanup(evil);
1103 }
1104
1105 struct line_chunk {
1106         int lone, ltwo;
1107         const char *one, *two;
1108         const char *one_end, *two_end;
1109         struct diff_line_range *range;
1110 };
1111
1112 static void flush_lines(struct diff_options *opt, const char **ptr, const char *end,
1113                 int slno, int elno, int *lno, const char *color, const char heading)
1114 {
1115         const char *p = *ptr;
1116         struct strbuf buf = STRBUF_INIT;
1117         const char *reset;
1118         char *line_prefix = "";
1119         struct strbuf *msgbuf;
1120
1121         if (opt && opt->output_prefix) {
1122                 msgbuf = opt->output_prefix(opt, opt->output_prefix_data);
1123                 line_prefix = msgbuf->buf;
1124         }
1125
1126         if (*color)
1127                 reset = diff_get_color_opt(opt, DIFF_RESET);
1128         else
1129                 reset = "";
1130
1131         strbuf_addf(&buf, "%s%c", color, heading);
1132         while (*ptr < end && *lno < slno) {
1133                 if (**ptr == '\n') {
1134                         (*lno)++;
1135                         if (*lno == slno) {
1136                                 (*ptr)++;
1137                                 break;
1138                         }
1139                 }
1140                 (*ptr)++;
1141         }
1142         assert(*ptr <= end);
1143         p = *ptr;
1144
1145         while (*ptr < end && *lno <= elno) {
1146                 if (**ptr == '\n') {
1147                         fprintf(opt->file, "%s%s", line_prefix, buf.buf);
1148                         if (*ptr - p)
1149                                 fwrite(p, *ptr - p, 1, opt->file);
1150                         fprintf(opt->file, "%s\n", reset);
1151                         p = *ptr + 1;
1152                         (*lno)++;
1153                 }
1154                 (*ptr)++;
1155         }
1156         if (*lno <= elno) {
1157                 fprintf(opt->file, "%s%s", line_prefix, buf.buf);
1158                 if (*ptr - p)
1159                         fwrite(p, *ptr - p, 1, opt->file);
1160                 fprintf(opt->file, "%s\n", reset);
1161         }
1162         strbuf_release(&buf);
1163 }
1164
1165 static void diff_flush_range(struct diff_options *opt, struct line_chunk *chunk,
1166                 struct line_range *range)
1167 {
1168         struct print_pair *pair = &range->pair;
1169         const char *old = diff_get_color_opt(opt, DIFF_FILE_OLD);
1170         const char *new = diff_get_color_opt(opt, DIFF_FILE_NEW);
1171         int i, cur = range->start;
1172
1173         for (i = 0; i < pair->nr; i++) {
1174                 struct print_range *pr = pair->ranges + i;
1175                 if (cur < pr->start)
1176                         flush_lines(opt, &chunk->two, chunk->two_end,
1177                                 cur, pr->start - 1, &chunk->ltwo, "", ' ');
1178
1179                 if (!pr->line_added)
1180                         flush_lines(opt, &chunk->one, chunk->one_end,
1181                                 pr->pstart, pr->pend, &chunk->lone, old, '-');
1182                 flush_lines(opt, &chunk->two, chunk->two_end,
1183                         pr->start, pr->end, &chunk->ltwo, new, '+');
1184
1185                 cur = pr->end + 1;
1186         }
1187
1188         if (cur <= range->end) {
1189                 flush_lines(opt, &chunk->two, chunk->two_end,
1190                         cur, range->end, &chunk->ltwo, "", ' ');
1191         }
1192 }
1193
1194 static void diff_flush_chunks(struct diff_options *opt, struct line_chunk *chunk)
1195 {
1196         struct diff_line_range *range = chunk->range;
1197         const char *set = diff_get_color_opt(opt, DIFF_FRAGINFO);
1198         const char *reset = diff_get_color_opt(opt, DIFF_RESET);
1199         char *line_prefix = "";
1200         struct strbuf *msgbuf;
1201         int i;
1202
1203         if (opt && opt->output_prefix) {
1204                 msgbuf = opt->output_prefix(opt, opt->output_prefix_data);
1205                 line_prefix = msgbuf->buf;
1206         }
1207
1208         for (i = 0; i < range->nr; i++) {
1209                 struct line_range *r = range->ranges + i;
1210                 long lenp = r->pend - r->pstart + 1, pstart = r->pstart;
1211                 long len = r->end - r->start + 1;
1212                 if (pstart == 0)
1213                         lenp = 0;
1214
1215                 fprintf(opt->file, "%s%s@@ -%ld,%ld +%ld,%ld @@%s\n",
1216                         line_prefix, set, pstart, lenp, r->start, len, reset);
1217
1218                 diff_flush_range(opt, chunk, r);
1219         }
1220 }
1221
1222 static void diff_flush_filepair(struct rev_info *rev, struct diff_line_range *range)
1223 {
1224         struct diff_options *opt = &rev->diffopt;
1225         struct diff_filespec *one = range->prev, *two = range->spec;
1226         struct diff_filepair p = {one, two, range->status, 0};
1227         struct strbuf header = STRBUF_INIT, meta = STRBUF_INIT;
1228         const char *a_prefix, *b_prefix;
1229         const char *name_a, *name_b, *a_one, *b_two;
1230         const char *lbl[2];
1231         const char *set = diff_get_color_opt(opt, DIFF_METAINFO);
1232         const char *reset = diff_get_color_opt(opt, DIFF_RESET);
1233         struct line_chunk chunk;
1234         int must_show_header;
1235         char *line_prefix = "";
1236         struct strbuf *msgbuf;
1237
1238         if (opt && opt->output_prefix) {
1239                 msgbuf = opt->output_prefix(opt, opt->output_prefix_data);
1240                 line_prefix = msgbuf->buf;
1241         }
1242
1243         /*
1244          * the ranges that touch no different file, in this case
1245          * the line number will not change, and of course we have
1246          * no sensible range->pair since there is no diff run.
1247          */
1248         if (one == NULL) {
1249                 if (rev->full_line_diff) {
1250                         chunk.two = two->data;
1251                         chunk.two_end = (const char *)two->data + two->size;
1252                         chunk.ltwo = 1;
1253                         chunk.range = range;
1254                         diff_flush_chunks(&rev->diffopt, &chunk);
1255                 }
1256                 return;
1257         }
1258
1259         if (range->status == DIFF_STATUS_DELETED)
1260                 die("We are following an nonexistent file, interesting!");
1261
1262         name_a  = one->path;
1263         name_b = two->path;
1264         fill_metainfo(&meta, name_a, name_b, one, two, opt, &p, &must_show_header,
1265                         DIFF_OPT_TST(opt, COLOR_DIFF));
1266
1267         diff_set_mnemonic_prefix(opt, "a/", "b/");
1268         if (DIFF_OPT_TST(opt, REVERSE_DIFF)) {
1269                 a_prefix = opt->b_prefix;
1270                 b_prefix = opt->a_prefix;
1271         } else {
1272                 a_prefix = opt->a_prefix;
1273                 b_prefix = opt->b_prefix;
1274         }
1275
1276         name_a = DIFF_FILE_VALID(one) ? name_a : name_b;
1277         name_b = DIFF_FILE_VALID(two) ? name_b : name_a;
1278
1279         a_one = quote_two(a_prefix, name_a + (*name_a == '/'));
1280         b_two = quote_two(b_prefix, name_b + (*name_b == '/'));
1281         lbl[0] = DIFF_FILE_VALID(one) ? a_one : "/dev/null";
1282         lbl[1] = DIFF_FILE_VALID(two) ? b_two : "/dev/null";
1283         strbuf_addf(&header, "%s%sdiff --git %s %s%s\n", line_prefix,
1284                         set, a_one, b_two, reset);
1285         if (lbl[0][0] == '/') {
1286                 strbuf_addf(&header, "%s%snew file mode %06o%s\n",
1287                         line_prefix, set, two->mode, reset);
1288         } else if (lbl[1][0] == '/') {
1289                 strbuf_addf(&header, "%s%sdeleted file mode %06o%s\n",
1290                         line_prefix, set, one->mode, reset);
1291         } else if (one->mode != two->mode) {
1292                         strbuf_addf(&header, "%s%sold mode %06o%s\n",
1293                                 line_prefix, set, one->mode, reset);
1294                         strbuf_addf(&header, "%s%snew mode %06o%s\n",
1295                                 line_prefix, set, two->mode, reset);
1296         }
1297
1298         fprintf(opt->file, "%s%s", header.buf, meta.buf);
1299         strbuf_release(&meta);
1300         strbuf_release(&header);
1301         fprintf(opt->file, "%s%s--- %s%s\n", line_prefix, set, lbl[0], reset);
1302         fprintf(opt->file, "%s%s+++ %s%s\n", line_prefix, set, lbl[1], reset);
1303         free((void *)a_one);
1304         free((void *)b_two);
1305
1306         chunk.one = one->data;
1307         chunk.one_end = (const char *)one->data + one->size;
1308         chunk.lone = 1;
1309         chunk.two = two->data;
1310         chunk.two_end = (const char *)two->data + two->size;
1311         chunk.ltwo = 1;
1312         chunk.range = range;
1313         diff_flush_chunks(&rev->diffopt, &chunk);
1314 }
1315
1316 #define EVIL_MERGE_STR "nontrivial merge found"
1317 static void flush_nontrivial_merge(struct rev_info *rev,
1318                 struct diff_line_range *range)
1319 {
1320         struct diff_options *opt = &rev->diffopt;
1321         const char *reset = diff_get_color_opt(opt, DIFF_RESET);
1322         const char *frag = diff_get_color_opt(opt, DIFF_FRAGINFO);
1323         const char *meta = diff_get_color_opt(opt, DIFF_METAINFO);
1324         const char *new = diff_get_color_opt(opt, DIFF_FILE_NEW);
1325         char *line_prefix = "";
1326         struct strbuf *msgbuf;
1327         int evil = 0;
1328         struct diff_line_range *r = range;
1329
1330         if (opt && opt->output_prefix) {
1331                 msgbuf = opt->output_prefix(opt, opt->output_prefix_data);
1332                 line_prefix = msgbuf->buf;
1333         }
1334
1335         while (r) {
1336                 if (r->nr)
1337                         evil = 1;
1338                 r = r->next;
1339         }
1340
1341         if (!evil)
1342                 return;
1343
1344         fprintf(opt->file, "%s%s%s%s\n", line_prefix, meta, EVIL_MERGE_STR, reset);
1345
1346         while (range) {
1347                 if (range->nr) {
1348                         int lno = 1;
1349                         const char *ptr = range->spec->data;
1350                         const char *end = (const char *)range->spec->data + range->spec->size;
1351                         int i = 0;
1352                         fprintf(opt->file, "%s%s%s%s\n", line_prefix,
1353                                 meta, range->spec->path, reset);
1354                         for (; i < range->nr; i++) {
1355                                 struct line_range *r = range->ranges + i;
1356                                 fprintf(opt->file, "%s%s@@ %ld,%ld @@%s\n",
1357                                         line_prefix, frag, r->start,
1358                                         r->end - r->start + 1, reset);
1359                                 flush_lines(opt, &ptr, end, r->start, r->end,
1360                                         &lno, new, ' ');
1361                         }
1362                         fprintf(opt->file, "%s\n", line_prefix);
1363                 }
1364                 range = range->next;
1365         }
1366 }
1367
1368 static void line_log_flush(struct rev_info *rev, struct commit *c)
1369 {
1370         struct diff_line_range *range = lookup_line_range(rev, c);
1371         struct diff_line_range *nontrivial = lookup_decoration(&rev->nontrivial_merge,
1372                                                         &c->object);
1373         struct log_info log;
1374         struct diff_options *opt = &rev->diffopt;
1375         char *line_prefix = "";
1376         struct strbuf *msgbuf;
1377
1378         if (range == NULL || !(c->object.flags & NONTRIVIAL_MERGE ||
1379                         c->object.flags & NEED_PRINT ||
1380                         rev->full_line_diff))
1381                 return;
1382
1383         if (rev->graph)
1384                 graph_update(rev->graph, c);
1385         log.commit = c;
1386         log.parent = NULL;
1387         rev->loginfo = &log;
1388         show_log(rev);
1389         rev->loginfo = NULL;
1390
1391         if (opt && opt->output_prefix) {
1392                 msgbuf = opt->output_prefix(opt, opt->output_prefix_data);
1393                 line_prefix = msgbuf->buf;
1394         }
1395         fprintf(rev->diffopt.file, "%s\n", line_prefix);
1396
1397         if (c->object.flags & NONTRIVIAL_MERGE)
1398                 flush_nontrivial_merge(rev, nontrivial);
1399         else {
1400                 while (range) {
1401                         if (range->diff || (range->nr && rev->full_line_diff))
1402                                 diff_flush_filepair(rev, range);
1403                         range = range->next;
1404                 }
1405         }
1406
1407         while (rev->graph && !graph_is_commit_finished(rev->graph)) {
1408                 struct strbuf sb;
1409                 strbuf_init(&sb, 0);
1410                 graph_next_line(rev->graph, &sb);
1411                 fputs(sb.buf, opt->file);
1412         }
1413 }
1414
1415 int cmd_line_log_walk(struct rev_info *rev)
1416 {
1417         struct commit *commit;
1418         struct commit_list *list = NULL;
1419         struct diff_line_range *r = NULL;
1420
1421         if (prepare_revision_walk(rev))
1422                 die("revision walk prepare failed");
1423
1424         list = rev->commits;
1425         if (list && !limited) {
1426                 list->item->object.flags |= RANGE_UPDATE;
1427                 list = list->next;
1428         }
1429         /* Clear the flags */
1430         while (list && !limited) {
1431                 list->item->object.flags &= ~(RANGE_UPDATE | NONTRIVIAL_MERGE |
1432                                 NEED_PRINT | EVIL_MERGE);
1433                 list = list->next;
1434         }
1435
1436         list = rev->commits;
1437         while (list) {
1438                 struct commit_list *need_free = list;
1439                 commit = list->item;
1440
1441                 if (commit->object.flags & RANGE_UPDATE)
1442                         assign_parents_range(rev, commit);
1443
1444                 if (commit->object.flags & NEED_PRINT ||
1445                         commit->object.flags & NONTRIVIAL_MERGE ||
1446                         rev->full_line_diff)
1447                         line_log_flush(rev, commit);
1448
1449                 r = lookup_line_range(rev, commit);
1450                 if (r) {
1451                         cleanup(r);
1452                         r = NULL;
1453                         add_line_range(rev, commit, r);
1454                 }
1455
1456                 r = lookup_decoration(&rev->nontrivial_merge, &commit->object);
1457                 if (r) {
1458                         cleanup(r);
1459                         r = NULL;
1460                         add_decoration(&rev->nontrivial_merge, &commit->object, r);
1461                 }
1462
1463                 list = list->next;
1464                 free(need_free);
1465         }
1466
1467         return 0;
1468 }
1469
1470 static enum rewrite_result rewrite_one(struct rev_info *rev, struct commit **pp)
1471 {
1472         struct diff_line_range *r = NULL;
1473         struct commit *p;
1474         while (1) {
1475                 p = *pp;
1476                 if (p->object.flags & RANGE_UPDATE)
1477                         assign_parents_range(rev, p);
1478                 if (p->object.flags & NEED_PRINT || p->object.flags & NONTRIVIAL_MERGE)
1479                         return rewrite_one_ok;
1480                 if (!p->parents)
1481                         return rewrite_one_noparents;
1482
1483                 r = lookup_line_range(rev, p);
1484                 if (!r)
1485                         return rewrite_one_noparents;
1486                 *pp = p->parents->item;
1487         }
1488 }
1489
1490 /* The rev->commits must be sorted in topologically order */
1491 void limit_list_line(struct rev_info *rev)
1492 {
1493         struct commit_list *list = rev->commits;
1494         struct commit_list *commits = xmalloc(sizeof(struct commit_list));
1495         struct commit_list *out = commits, *prev = commits;
1496         struct commit *c;
1497         struct diff_line_range *r;
1498
1499         if (list) {
1500                 list->item->object.flags |= RANGE_UPDATE;
1501                 list = list->next;
1502         }
1503         /* Clear the flags */
1504         while (list) {
1505                 list->item->object.flags &= ~(RANGE_UPDATE | NONTRIVIAL_MERGE |
1506                                                 NEED_PRINT | EVIL_MERGE);
1507                 list = list->next;
1508         }
1509
1510         list = rev->commits;
1511         while (list) {
1512                 c = list->item;
1513
1514                 if (c->object.flags & RANGE_UPDATE)
1515                         assign_parents_range(rev, c);
1516
1517                 if (c->object.flags & NEED_PRINT || c->object.flags & NONTRIVIAL_MERGE) {
1518                         if (rewrite_parents(rev, c, rewrite_one))
1519                                 die("Can't rewrite parent for commit %s",
1520                                         sha1_to_hex(c->object.sha1));
1521                         commits->item = c;
1522                         commits->next = xmalloc(sizeof(struct commit_list));
1523                         prev = commits;
1524                         commits = commits->next;
1525                 } else {
1526                         r = lookup_line_range(rev, c);
1527                         if (r) {
1528                                 cleanup(r);
1529                                 r = NULL;
1530                                 add_line_range(rev, c, r);
1531                         }
1532                 }
1533
1534                 list = list->next;
1535         }
1536
1537         prev->next = NULL;
1538         free(commits);
1539
1540         list = rev->commits;
1541         while (list) {
1542                 struct commit_list *l = list;
1543                 list = list->next;
1544                 free(l);
1545         }
1546
1547         rev->commits = out;
1548         limited = 1;
1549 }