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                 if (c->parents && !c->parents->next) {
 965                         free(c->parents);
 966                         c->parents = NULL;
 967                 }
 968         }
 969
 970         /* and the ranges of current commit c is updated */
 971         c->object.flags &= ~RANGE_UPDATE;
 972         if (diff)
 973                 c->object.flags |= NEED_PRINT;
 974
 975 out:
 976         if (tree1)
 977                 free(tree1);
 978         if (tree2)
 979                 free(tree2);
 980
 981         return diff;
 982 }
 983
 984 static void diff_update_parent_range(struct rev_info *rev,
 985                 struct commit *commit)
 986 {
 987         struct diff_line_range *r = lookup_line_range(rev, commit);
 988         struct commit_list *parents = commit->parents;
 989         struct commit *c = NULL;
 990         if (parents) {
 991                 assert(parents->next == NULL);
 992                 c = parents->item;
 993         }
 994
 995         assign_range_to_parent(rev, commit, c, r, &rev->diffopt, 1);
 996 }
 997
 998 struct commit_state {
 999         struct diff_line_range *range;
1000         struct object obj;
1001 };
1002
1003 static void assign_parents_range(struct rev_info *rev, struct commit *commit)
1004 {
1005         struct commit_list *parents = commit->parents;
1006         struct diff_line_range *r = lookup_line_range(rev, commit);
1007         struct diff_line_range *evil = NULL, *range = NULL;
1008         struct decoration parents_state;
1009         struct commit_state *state = NULL;
1010         int nontrivial = 0;
1011
1012         memset(&parents_state, 0, sizeof(parents_state));
1013         /*
1014          * If we are in linear history, update range and flush the patch if
1015          * necessary
1016          */
1017         if (parents == NULL || parents->next == NULL)
1018                 return diff_update_parent_range(rev, commit);
1019
1020         /*
1021          * Loop on the parents and assign the ranges to different
1022          * parents, if there is any range left, this commit must
1023          * be an evil merge.
1024          */
1025         evil = diff_line_range_clone_deeply(r);
1026         parents = commit->parents;
1027         while (parents) {
1028                 struct commit *p = parents->item;
1029                 int diff = 0;
1030                 struct diff_line_range *origin_range = lookup_line_range(rev, p);
1031                 if (origin_range)
1032                         origin_range = diff_line_range_clone_deeply(origin_range);
1033
1034                 state = xmalloc(sizeof(*state));
1035                 state->range = origin_range;
1036                 state->obj = p->object;
1037                 add_decoration(&parents_state, &p->object, state);
1038                 diff = assign_range_to_parent(rev, commit, p, r, &rev->diffopt, 1);
1039                 /* Since all the ranges comes from this parent, we can ignore others */
1040                 if (diff == 0) {
1041                         /* restore the state of parents before this one */
1042                         parents = commit->parents;
1043                         while (parents->item != p) {
1044                                 struct commit_list *list = parents;
1045                                 struct diff_line_range *line_range = NULL;
1046                                 parents = parents->next;
1047                                 line_range = lookup_line_range(rev, list->item);
1048                                 cleanup(line_range);
1049                                 state = lookup_decoration(&parents_state, &list->item->object);
1050                                 add_decoration(&parents_state, &list->item->object, NULL);
1051                                 add_line_range(rev, list->item, state->range);
1052                                 list->item->object = state->obj;
1053                                 free(state);
1054                                 free(list);
1055                         }
1056
1057                         commit->parents = parents;
1058                         parents = parents->next;
1059                         commit->parents->next = NULL;
1060
1061                         /* free the non-use commit_list */
1062                         while (parents) {
1063                                 struct commit_list *list = parents;
1064                                 parents = parents->next;
1065                                 free(list);
1066                         }
1067                         goto out;
1068                 }
1069                 /* take the ranges from 'commit', try to detect nontrivial merge */
1070                 assign_range_to_parent(rev, commit, p, evil, &rev->diffopt, 0);
1071                 parents = parents->next;
1072         }
1073
1074         commit->object.flags |= NONTRIVIAL_MERGE;
1075         /*
1076          * yes, this must be an evil merge.
1077          */
1078         range = evil;
1079         while (range) {
1080                 if (range->nr) {
1081                         commit->object.flags |= EVIL_MERGE;
1082                         nontrivial = 1;
1083                 }
1084                 range = range->next;
1085         }
1086
1087 out:
1088         /* Never print out any diff for a merge commit */
1089         commit->object.flags &= ~NEED_PRINT;
1090
1091         parents = commit->parents;
1092         while (parents) {
1093                 state = lookup_decoration(&parents_state, &parents->item->object);
1094                 if (state) {
1095                         cleanup(state->range);
1096                         free(state);
1097                 }
1098                 parents = parents->next;
1099         }
1100
1101         if (nontrivial)
1102                 add_decoration(&rev->nontrivial_merge, &commit->object, evil);
1103         else
1104                 cleanup(evil);
1105 }
1106
1107 struct line_chunk {
1108         int lone, ltwo;
1109         const char *one, *two;
1110         const char *one_end, *two_end;
1111         struct diff_line_range *range;
1112 };
1113
1114 static void flush_lines(struct diff_options *opt, const char **ptr, const char *end,
1115                 int slno, int elno, int *lno, const char *color, const char heading)
1116 {
1117         const char *p = *ptr;
1118         struct strbuf buf = STRBUF_INIT;
1119         const char *reset;
1120         char *line_prefix = "";
1121         struct strbuf *msgbuf;
1122
1123         if (opt && opt->output_prefix) {
1124                 msgbuf = opt->output_prefix(opt, opt->output_prefix_data);
1125                 line_prefix = msgbuf->buf;
1126         }
1127
1128         if (*color)
1129                 reset = diff_get_color_opt(opt, DIFF_RESET);
1130         else
1131                 reset = "";
1132
1133         strbuf_addf(&buf, "%s%c", color, heading);
1134         while (*ptr < end && *lno < slno) {
1135                 if (**ptr == '\n') {
1136                         (*lno)++;
1137                         if (*lno == slno) {
1138                                 (*ptr)++;
1139                                 break;
1140                         }
1141                 }
1142                 (*ptr)++;
1143         }
1144         assert(*ptr <= end);
1145         p = *ptr;
1146
1147         while (*ptr < end && *lno <= elno) {
1148                 if (**ptr == '\n') {
1149                         fprintf(opt->file, "%s%s", line_prefix, buf.buf);
1150                         if (*ptr - p)
1151                                 fwrite(p, *ptr - p, 1, opt->file);
1152                         fprintf(opt->file, "%s\n", reset);
1153                         p = *ptr + 1;
1154                         (*lno)++;
1155                 }
1156                 (*ptr)++;
1157         }
1158         if (*lno <= elno) {
1159                 fprintf(opt->file, "%s%s", line_prefix, buf.buf);
1160                 if (*ptr - p)
1161                         fwrite(p, *ptr - p, 1, opt->file);
1162                 fprintf(opt->file, "%s\n", reset);
1163         }
1164         strbuf_release(&buf);
1165 }
1166
1167 static void diff_flush_range(struct diff_options *opt, struct line_chunk *chunk,
1168                 struct line_range *range)
1169 {
1170         struct print_pair *pair = &range->pair;
1171         const char *old = diff_get_color_opt(opt, DIFF_FILE_OLD);
1172         const char *new = diff_get_color_opt(opt, DIFF_FILE_NEW);
1173         int i, cur = range->start;
1174
1175         for (i = 0; i < pair->nr; i++) {
1176                 struct print_range *pr = pair->ranges + i;
1177                 if (cur < pr->start)
1178                         flush_lines(opt, &chunk->two, chunk->two_end,
1179                                 cur, pr->start - 1, &chunk->ltwo, "", ' ');
1180
1181                 if (!pr->line_added)
1182                         flush_lines(opt, &chunk->one, chunk->one_end,
1183                                 pr->pstart, pr->pend, &chunk->lone, old, '-');
1184                 flush_lines(opt, &chunk->two, chunk->two_end,
1185                         pr->start, pr->end, &chunk->ltwo, new, '+');
1186
1187                 cur = pr->end + 1;
1188         }
1189
1190         if (cur <= range->end) {
1191                 flush_lines(opt, &chunk->two, chunk->two_end,
1192                         cur, range->end, &chunk->ltwo, "", ' ');
1193         }
1194 }
1195
1196 static void diff_flush_chunks(struct diff_options *opt, struct line_chunk *chunk)
1197 {
1198         struct diff_line_range *range = chunk->range;
1199         const char *set = diff_get_color_opt(opt, DIFF_FRAGINFO);
1200         const char *reset = diff_get_color_opt(opt, DIFF_RESET);
1201         char *line_prefix = "";
1202         struct strbuf *msgbuf;
1203         int i;
1204
1205         if (opt && opt->output_prefix) {
1206                 msgbuf = opt->output_prefix(opt, opt->output_prefix_data);
1207                 line_prefix = msgbuf->buf;
1208         }
1209
1210         for (i = 0; i < range->nr; i++) {
1211                 struct line_range *r = range->ranges + i;
1212                 long lenp = r->pend - r->pstart + 1, pstart = r->pstart;
1213                 long len = r->end - r->start + 1;
1214                 if (pstart == 0)
1215                         lenp = 0;
1216
1217                 fprintf(opt->file, "%s%s@@ -%ld,%ld +%ld,%ld @@%s\n",
1218                         line_prefix, set, pstart, lenp, r->start, len, reset);
1219
1220                 diff_flush_range(opt, chunk, r);
1221         }
1222 }
1223
1224 static void diff_flush_filepair(struct rev_info *rev, struct diff_line_range *range)
1225 {
1226         struct diff_options *opt = &rev->diffopt;
1227         struct diff_filespec *one = range->prev, *two = range->spec;
1228         struct diff_filepair p = {one, two, range->status, 0};
1229         struct strbuf header = STRBUF_INIT, meta = STRBUF_INIT;
1230         const char *a_prefix, *b_prefix;
1231         const char *name_a, *name_b, *a_one, *b_two;
1232         const char *lbl[2];
1233         const char *set = diff_get_color_opt(opt, DIFF_METAINFO);
1234         const char *reset = diff_get_color_opt(opt, DIFF_RESET);
1235         struct line_chunk chunk;
1236         int must_show_header;
1237         char *line_prefix = "";
1238         struct strbuf *msgbuf;
1239
1240         if (opt && opt->output_prefix) {
1241                 msgbuf = opt->output_prefix(opt, opt->output_prefix_data);
1242                 line_prefix = msgbuf->buf;
1243         }
1244
1245         /*
1246          * the ranges that touch no different file, in this case
1247          * the line number will not change, and of course we have
1248          * no sensible range->pair since there is no diff run.
1249          */
1250         if (one == NULL) {
1251                 if (rev->full_line_diff) {
1252                         chunk.two = two->data;
1253                         chunk.two_end = (const char *)two->data + two->size;
1254                         chunk.ltwo = 1;
1255                         chunk.range = range;
1256                         diff_flush_chunks(&rev->diffopt, &chunk);
1257                 }
1258                 return;
1259         }
1260
1261         if (range->status == DIFF_STATUS_DELETED)
1262                 die("We are following an nonexistent file, interesting!");
1263
1264         name_a  = one->path;
1265         name_b = two->path;
1266         fill_metainfo(&meta, name_a, name_b, one, two, opt, &p, &must_show_header,
1267                         DIFF_OPT_TST(opt, COLOR_DIFF));
1268
1269         diff_set_mnemonic_prefix(opt, "a/", "b/");
1270         if (DIFF_OPT_TST(opt, REVERSE_DIFF)) {
1271                 a_prefix = opt->b_prefix;
1272                 b_prefix = opt->a_prefix;
1273         } else {
1274                 a_prefix = opt->a_prefix;
1275                 b_prefix = opt->b_prefix;
1276         }
1277
1278         name_a = DIFF_FILE_VALID(one) ? name_a : name_b;
1279         name_b = DIFF_FILE_VALID(two) ? name_b : name_a;
1280
1281         a_one = quote_two(a_prefix, name_a + (*name_a == '/'));
1282         b_two = quote_two(b_prefix, name_b + (*name_b == '/'));
1283         lbl[0] = DIFF_FILE_VALID(one) ? a_one : "/dev/null";
1284         lbl[1] = DIFF_FILE_VALID(two) ? b_two : "/dev/null";
1285         strbuf_addf(&header, "%s%sdiff --git %s %s%s\n", line_prefix,
1286                         set, a_one, b_two, reset);
1287         if (lbl[0][0] == '/') {
1288                 strbuf_addf(&header, "%s%snew file mode %06o%s\n",
1289                         line_prefix, set, two->mode, reset);
1290         } else if (lbl[1][0] == '/') {
1291                 strbuf_addf(&header, "%s%sdeleted file mode %06o%s\n",
1292                         line_prefix, set, one->mode, reset);
1293         } else if (one->mode != two->mode) {
1294                         strbuf_addf(&header, "%s%sold mode %06o%s\n",
1295                                 line_prefix, set, one->mode, reset);
1296                         strbuf_addf(&header, "%s%snew mode %06o%s\n",
1297                                 line_prefix, set, two->mode, reset);
1298         }
1299
1300         fprintf(opt->file, "%s%s", header.buf, meta.buf);
1301         strbuf_release(&meta);
1302         strbuf_release(&header);
1303         fprintf(opt->file, "%s%s--- %s%s\n", line_prefix, set, lbl[0], reset);
1304         fprintf(opt->file, "%s%s+++ %s%s\n", line_prefix, set, lbl[1], reset);
1305         free((void *)a_one);
1306         free((void *)b_two);
1307
1308         chunk.one = one->data;
1309         chunk.one_end = (const char *)one->data + one->size;
1310         chunk.lone = 1;
1311         chunk.two = two->data;
1312         chunk.two_end = (const char *)two->data + two->size;
1313         chunk.ltwo = 1;
1314         chunk.range = range;
1315         diff_flush_chunks(&rev->diffopt, &chunk);
1316 }
1317
1318 #define EVIL_MERGE_STR "nontrivial merge found"
1319 static void flush_nontrivial_merge(struct rev_info *rev,
1320                 struct diff_line_range *range)
1321 {
1322         struct diff_options *opt = &rev->diffopt;
1323         const char *reset = diff_get_color_opt(opt, DIFF_RESET);
1324         const char *frag = diff_get_color_opt(opt, DIFF_FRAGINFO);
1325         const char *meta = diff_get_color_opt(opt, DIFF_METAINFO);
1326         const char *new = diff_get_color_opt(opt, DIFF_FILE_NEW);
1327         char *line_prefix = "";
1328         struct strbuf *msgbuf;
1329         int evil = 0;
1330         struct diff_line_range *r = range;
1331
1332         if (opt && opt->output_prefix) {
1333                 msgbuf = opt->output_prefix(opt, opt->output_prefix_data);
1334                 line_prefix = msgbuf->buf;
1335         }
1336
1337         while (r) {
1338                 if (r->nr)
1339                         evil = 1;
1340                 r = r->next;
1341         }
1342
1343         if (!evil)
1344                 return;
1345
1346         fprintf(opt->file, "%s%s%s%s\n", line_prefix, meta, EVIL_MERGE_STR, reset);
1347
1348         while (range) {
1349                 if (range->nr) {
1350                         int lno = 1;
1351                         const char *ptr = range->spec->data;
1352                         const char *end = (const char *)range->spec->data + range->spec->size;
1353                         int i = 0;
1354                         fprintf(opt->file, "%s%s%s%s\n", line_prefix,
1355                                 meta, range->spec->path, reset);
1356                         for (; i < range->nr; i++) {
1357                                 struct line_range *r = range->ranges + i;
1358                                 fprintf(opt->file, "%s%s@@ %ld,%ld @@%s\n",
1359                                         line_prefix, frag, r->start,
1360                                         r->end - r->start + 1, reset);
1361                                 flush_lines(opt, &ptr, end, r->start, r->end,
1362                                         &lno, new, ' ');
1363                         }
1364                         fprintf(opt->file, "%s\n", line_prefix);
1365                 }
1366                 range = range->next;
1367         }
1368 }
1369
1370 static void line_log_flush(struct rev_info *rev, struct commit *c)
1371 {
1372         struct diff_line_range *range = lookup_line_range(rev, c);
1373         struct diff_line_range *nontrivial = lookup_decoration(&rev->nontrivial_merge,
1374                                                         &c->object);
1375         struct log_info log;
1376         struct diff_options *opt = &rev->diffopt;
1377         char *line_prefix = "";
1378         struct strbuf *msgbuf;
1379
1380         if (range == NULL || !(c->object.flags & NONTRIVIAL_MERGE ||
1381                         c->object.flags & NEED_PRINT ||
1382                         rev->full_line_diff))
1383                 return;
1384
1385         if (rev->graph)
1386                 graph_update(rev->graph, c);
1387         log.commit = c;
1388         log.parent = NULL;
1389         rev->loginfo = &log;
1390         show_log(rev);
1391         rev->loginfo = NULL;
1392
1393         if (opt && opt->output_prefix) {
1394                 msgbuf = opt->output_prefix(opt, opt->output_prefix_data);
1395                 line_prefix = msgbuf->buf;
1396         }
1397         fprintf(rev->diffopt.file, "%s\n", line_prefix);
1398
1399         if (c->object.flags & NONTRIVIAL_MERGE)
1400                 flush_nontrivial_merge(rev, nontrivial);
1401         else {
1402                 while (range) {
1403                         if (range->diff || (range->nr && rev->full_line_diff))
1404                                 diff_flush_filepair(rev, range);
1405                         range = range->next;
1406                 }
1407         }
1408
1409         while (rev->graph && !graph_is_commit_finished(rev->graph)) {
1410                 struct strbuf sb;
1411                 strbuf_init(&sb, 0);
1412                 graph_next_line(rev->graph, &sb);
1413                 fputs(sb.buf, opt->file);
1414         }
1415 }
1416
1417 int cmd_line_log_walk(struct rev_info *rev)
1418 {
1419         struct commit *commit;
1420         struct commit_list *list = NULL;
1421         struct diff_line_range *r = NULL;
1422
1423         if (prepare_revision_walk(rev))
1424                 die("revision walk prepare failed");
1425
1426         list = rev->commits;
1427         if (list && !limited) {
1428                 list->item->object.flags |= RANGE_UPDATE;
1429                 list = list->next;
1430         }
1431         /* Clear the flags */
1432         while (list && !limited) {
1433                 list->item->object.flags &= ~(RANGE_UPDATE | NONTRIVIAL_MERGE |
1434                                 NEED_PRINT | EVIL_MERGE);
1435                 list = list->next;
1436         }
1437
1438         list = rev->commits;
1439         while (list) {
1440                 struct commit_list *need_free = list;
1441                 commit = list->item;
1442
1443                 if (commit->object.flags & RANGE_UPDATE)
1444                         assign_parents_range(rev, commit);
1445
1446                 if (commit->object.flags & NEED_PRINT ||
1447                         commit->object.flags & NONTRIVIAL_MERGE ||
1448                         rev->full_line_diff)
1449                         line_log_flush(rev, commit);
1450
1451                 r = lookup_line_range(rev, commit);
1452                 if (r) {
1453                         cleanup(r);
1454                         r = NULL;
1455                         add_line_range(rev, commit, r);
1456                 }
1457
1458                 r = lookup_decoration(&rev->nontrivial_merge, &commit->object);
1459                 if (r) {
1460                         cleanup(r);
1461                         r = NULL;
1462                         add_decoration(&rev->nontrivial_merge, &commit->object, r);
1463                 }
1464
1465                 list = list->next;
1466                 free(need_free);
1467         }
1468
1469         return 0;
1470 }
1471
1472 static enum rewrite_result rewrite_one(struct rev_info *rev, struct commit **pp)
1473 {
1474         struct diff_line_range *r = NULL;
1475         struct commit *p;
1476         while (1) {
1477                 p = *pp;
1478                 if (p->object.flags & RANGE_UPDATE)
1479                         assign_parents_range(rev, p);
1480                 if (p->object.flags & NEED_PRINT || p->object.flags & NONTRIVIAL_MERGE)
1481                         return rewrite_one_ok;
1482                 if (!p->parents)
1483                         return rewrite_one_noparents;
1484
1485                 r = lookup_line_range(rev, p);
1486                 if (!r)
1487                         return rewrite_one_noparents;
1488                 *pp = p->parents->item;
1489         }
1490 }
1491
1492 /* The rev->commits must be sorted in topologically order */
1493 void limit_list_line(struct rev_info *rev)
1494 {
1495         struct commit_list *list = rev->commits;
1496         struct commit_list *commits = xmalloc(sizeof(struct commit_list));
1497         struct commit_list *out = commits, *prev = commits;
1498         struct commit *c;
1499         struct diff_line_range *r;
1500
1501         if (list) {
1502                 list->item->object.flags |= RANGE_UPDATE;
1503                 list = list->next;
1504         }
1505         /* Clear the flags */
1506         while (list) {
1507                 list->item->object.flags &= ~(RANGE_UPDATE | NONTRIVIAL_MERGE |
1508                                                 NEED_PRINT | EVIL_MERGE);
1509                 list = list->next;
1510         }
1511
1512         list = rev->commits;
1513         while (list) {
1514                 c = list->item;
1515
1516                 if (c->object.flags & RANGE_UPDATE)
1517                         assign_parents_range(rev, c);
1518
1519                 if (c->object.flags & NEED_PRINT || c->object.flags & NONTRIVIAL_MERGE) {
1520                         if (rewrite_parents(rev, c, rewrite_one))
1521                                 die("Can't rewrite parent for commit %s",
1522                                         sha1_to_hex(c->object.sha1));
1523                         commits->item = c;
1524                         commits->next = xmalloc(sizeof(struct commit_list));
1525                         prev = commits;
1526                         commits = commits->next;
1527                 } else {
1528                         r = lookup_line_range(rev, c);
1529                         if (r) {
1530                                 cleanup(r);
1531                                 r = NULL;
1532                                 add_line_range(rev, c, r);
1533                         }
1534                 }
1535
1536                 list = list->next;
1537         }
1538
1539         prev->next = NULL;
1540         free(commits);
1541
1542         list = rev->commits;
1543         while (list) {
1544                 struct commit_list *l = list;
1545                 list = list->next;
1546                 free(l);
1547         }
1548
1549         rev->commits = out;
1550         limited = 1;
1551 }