line-log.c

   1 #include "git-compat-util.h"
   2 #include "line-range.h"
   3 #include "cache.h"
   4 #include "tag.h"
   5 #include "blob.h"
   6 #include "tree.h"
   7 #include "diff.h"
   8 #include "commit.h"
   9 #include "decorate.h"
  10 #include "revision.h"
  11 #include "xdiff-interface.h"
  12 #include "strbuf.h"
  13 #include "log-tree.h"
  14 #include "graph.h"
  15 #include "userdiff.h"
  16 #include "line-log.h"
  17
  18 static void range_set_grow(struct range_set *rs, size_t extra)
  19 {
  20         ALLOC_GROW(rs->ranges, rs->nr + extra, rs->alloc);
  21 }
  22
  23 /* Either initialization would be fine */
  24 #define RANGE_SET_INIT {0}
  25
  26 static void range_set_init(struct range_set *rs, size_t prealloc)
  27 {
  28         rs->alloc = rs->nr = 0;
  29         rs->ranges = NULL;
  30         if (prealloc)
  31                 range_set_grow(rs, prealloc);
  32 }
  33
  34 static void range_set_release(struct range_set *rs)
  35 {
  36         free(rs->ranges);
  37         rs->alloc = rs->nr = 0;
  38         rs->ranges = NULL;
  39 }
  40
  41 /* dst must be uninitialized! */
  42 static void range_set_copy(struct range_set *dst, struct range_set *src)
  43 {
  44         range_set_init(dst, src->nr);
  45         memcpy(dst->ranges, src->ranges, src->nr*sizeof(struct range_set));
  46         dst->nr = src->nr;
  47 }
  48 static void range_set_move(struct range_set *dst, struct range_set *src)
  49 {
  50         range_set_release(dst);
  51         dst->ranges = src->ranges;
  52         dst->nr = src->nr;
  53         dst->alloc = src->alloc;
  54         src->ranges = NULL;
  55         src->alloc = src->nr = 0;
  56 }
  57
  58 /* tack on a _new_ range _at the end_ */
  59 static void range_set_append_unsafe(struct range_set *rs, long a, long b)
  60 {
  61         assert(a <= b);
  62         range_set_grow(rs, 1);
  63         rs->ranges[rs->nr].start = a;
  64         rs->ranges[rs->nr].end = b;
  65         rs->nr++;
  66 }
  67
  68 static void range_set_append(struct range_set *rs, long a, long b)
  69 {
  70         assert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);
  71         range_set_append_unsafe(rs, a, b);
  72 }
  73
  74 static int range_cmp(const void *_r, const void *_s)
  75 {
  76         const struct range *r = _r;
  77         const struct range *s = _s;
  78
  79         /* this could be simply 'return r.start-s.start', but for the types */
  80         if (r->start == s->start)
  81                 return 0;
  82         if (r->start < s->start)
  83                 return -1;
  84         return 1;
  85 }
  86
  87 /*
  88  * Check that the ranges are non-empty, sorted and non-overlapping
  89  */
  90 static void range_set_check_invariants(struct range_set *rs)
  91 {
  92         int i;
  93
  94         if (!rs)
  95                 return;
  96
  97         if (rs->nr)
  98                 assert(rs->ranges[0].start < rs->ranges[0].end);
  99
 100         for (i = 1; i < rs->nr; i++) {
 101                 assert(rs->ranges[i-1].end < rs->ranges[i].start);
 102                 assert(rs->ranges[i].start < rs->ranges[i].end);
 103         }
 104 }
 105
 106 /*
 107  * In-place pass of sorting and merging the ranges in the range set,
 108  * to establish the invariants when we get the ranges from the user
 109  */
 110 static void sort_and_merge_range_set(struct range_set *rs)
 111 {
 112         int i;
 113         int o = 1; /* output cursor */
 114
 115         qsort(rs->ranges, rs->nr, sizeof(struct range), range_cmp);
 116
 117         for (i = 1; i < rs->nr; i++) {
 118                 if (rs->ranges[i].start <= rs->ranges[o-1].end) {
 119                         rs->ranges[o-1].end = rs->ranges[i].end;
 120                 } else {
 121                         rs->ranges[o].start = rs->ranges[i].start;
 122                         rs->ranges[o].end = rs->ranges[i].end;
 123                         o++;
 124                 }
 125         }
 126         assert(o <= rs->nr);
 127         rs->nr = o;
 128
 129         range_set_check_invariants(rs);
 130 }
 131
 132 /*
 133  * Union of range sets (i.e., sets of line numbers).  Used to merge
 134  * them when searches meet at a common ancestor.
 135  *
 136  * This is also where the ranges are consolidated into canonical form:
 137  * overlapping and adjacent ranges are merged, and empty ranges are
 138  * removed.
 139  */
 140 static void range_set_union(struct range_set *out,
 141                              struct range_set *a, struct range_set *b)
 142 {
 143         int i = 0, j = 0, o = 0;
 144         struct range *ra = a->ranges;
 145         struct range *rb = b->ranges;
 146         /* cannot make an alias of out->ranges: it may change during grow */
 147
 148         assert(out->nr == 0);
 149         while (i < a->nr || j < b->nr) {
 150                 struct range *new;
 151                 if (i < a->nr && j < b->nr) {
 152                         if (ra[i].start < rb[j].start)
 153                                 new = &ra[i++];
 154                         else if (ra[i].start > rb[j].start)
 155                                 new = &rb[j++];
 156                         else if (ra[i].end < rb[j].end)
 157                                 new = &ra[i++];
 158                         else
 159                                 new = &rb[j++];
 160                 } else if (i < a->nr)      /* b exhausted */
 161                         new = &ra[i++];
 162                 else                       /* a exhausted */
 163                         new = &rb[j++];
 164                 if (new->start == new->end)
 165                         ; /* empty range */
 166                 else if (!o || out->ranges[o-1].end < new->start) {
 167                         range_set_grow(out, 1);
 168                         out->ranges[o].start = new->start;
 169                         out->ranges[o].end = new->end;
 170                         o++;
 171                 } else if (out->ranges[o-1].end < new->end) {
 172                         out->ranges[o-1].end = new->end;
 173                 }
 174         }
 175         out->nr = o;
 176 }
 177
 178 /*
 179  * Difference of range sets (out = a \ b).  Pass the "interesting"
 180  * ranges as 'a' and the target side of the diff as 'b': it removes
 181  * the ranges for which the commit is responsible.
 182  */
 183 static void range_set_difference(struct range_set *out,
 184                                   struct range_set *a, struct range_set *b)
 185 {
 186         int i, j =  0;
 187         for (i = 0; i < a->nr; i++) {
 188                 long start = a->ranges[i].start;
 189                 long end = a->ranges[i].end;
 190                 while (start < end) {
 191                         while (j < b->nr && start >= b->ranges[j].end)
 192                                 /*
 193                                  * a:         |-------
 194                                  * b: ------|
 195                                  */
 196                                 j++;
 197                         if (j >= b->nr || end < b->ranges[j].start) {
 198                                 /*
 199                                  * b exhausted, or
 200                                  * a:  ----|
 201                                  * b:         |----
 202                                  */
 203                                 range_set_append(out, start, end);
 204                                 break;
 205                         }
 206                         if (start >= b->ranges[j].start) {
 207                                 /*
 208                                  * a:     |--????
 209                                  * b: |------|
 210                                  */
 211                                 start = b->ranges[j].end;
 212                         } else if (end > b->ranges[j].start) {
 213                                 /*
 214                                  * a: |-----|
 215                                  * b:    |--?????
 216                                  */
 217                                 if (start < b->ranges[j].start)
 218                                         range_set_append(out, start, b->ranges[j].start);
 219                                 start = b->ranges[j].end;
 220                         }
 221                 }
 222         }
 223 }
 224
 225 static void diff_ranges_init(struct diff_ranges *diff)
 226 {
 227         range_set_init(&diff->parent, 0);
 228         range_set_init(&diff->target, 0);
 229 }
 230
 231 static void diff_ranges_release(struct diff_ranges *diff)
 232 {
 233         range_set_release(&diff->parent);
 234         range_set_release(&diff->target);
 235 }
 236
 237 void line_log_data_init(struct line_log_data *r)
 238 {
 239         memset(r, 0, sizeof(struct line_log_data));
 240         range_set_init(&r->ranges, 0);
 241 }
 242
 243 static void line_log_data_clear(struct line_log_data *r)
 244 {
 245         range_set_release(&r->ranges);
 246         if (r->pair)
 247                 diff_free_filepair(r->pair);
 248 }
 249
 250 static void free_line_log_data(struct line_log_data *r)
 251 {
 252         while (r) {
 253                 struct line_log_data *next = r->next;
 254                 line_log_data_clear(r);
 255                 free(r);
 256                 r = next;
 257         }
 258 }
 259
 260 static struct line_log_data *
 261 search_line_log_data(struct line_log_data *list, const char *path,
 262                      struct line_log_data **insertion_point)
 263 {
 264         struct line_log_data *p = list;
 265         if (insertion_point)
 266                 *insertion_point = NULL;
 267         while (p) {
 268                 int cmp = strcmp(p->path, path);
 269                 if (!cmp)
 270                         return p;
 271                 if (insertion_point && cmp < 0)
 272                         *insertion_point = p;
 273                 p = p->next;
 274         }
 275         return NULL;
 276 }
 277
 278 /*
 279  * Note: takes ownership of 'path', which happens to be what the only
 280  * caller needs.
 281  */
 282 static void line_log_data_insert(struct line_log_data **list,
 283                                  char *path,
 284                                  long begin, long end)
 285 {
 286         struct line_log_data *ip;
 287         struct line_log_data *p = search_line_log_data(*list, path, &ip);
 288
 289         if (p) {
 290                 range_set_append_unsafe(&p->ranges, begin, end);
 291                 sort_and_merge_range_set(&p->ranges);
 292                 free(path);
 293                 return;
 294         }
 295
 296         p = xcalloc(1, sizeof(struct line_log_data));
 297         p->path = path;
 298         range_set_append(&p->ranges, begin, end);
 299         if (ip) {
 300                 p->next = ip->next;
 301                 ip->next = p;
 302         } else {
 303                 p->next = *list;
 304                 *list = p;
 305         }
 306 }
 307
 308 struct collect_diff_cbdata {
 309         struct diff_ranges *diff;
 310 };
 311
 312 static int collect_diff_cb(long start_a, long count_a,
 313                            long start_b, long count_b,
 314                            void *data)
 315 {
 316         struct collect_diff_cbdata *d = data;
 317
 318         if (count_a >= 0)
 319                 range_set_append(&d->diff->parent, start_a, start_a + count_a);
 320         if (count_b >= 0)
 321                 range_set_append(&d->diff->target, start_b, start_b + count_b);
 322
 323         return 0;
 324 }
 325
 326 static void collect_diff(mmfile_t *parent, mmfile_t *target, struct diff_ranges *out)
 327 {
 328         struct collect_diff_cbdata cbdata = {NULL};
 329         xpparam_t xpp;
 330         xdemitconf_t xecfg;
 331         xdemitcb_t ecb;
 332
 333         memset(&xpp, 0, sizeof(xpp));
 334         memset(&xecfg, 0, sizeof(xecfg));
 335         xecfg.ctxlen = xecfg.interhunkctxlen = 0;
 336
 337         cbdata.diff = out;
 338         xecfg.hunk_func = collect_diff_cb;
 339         memset(&ecb, 0, sizeof(ecb));
 340         ecb.priv = &cbdata;
 341         xdi_diff(parent, target, &xpp, &xecfg, &ecb);
 342 }
 343
 344 /*
 345  * These are handy for debugging.  Removing them with #if 0 silences
 346  * the "unused function" warning.
 347  */
 348 #if 0
 349 static void dump_range_set(struct range_set *rs, const char *desc)
 350 {
 351         int i;
 352         printf("range set %s (%d items):\n", desc, rs->nr);
 353         for (i = 0; i < rs->nr; i++)
 354                 printf("\t[%ld,%ld]\n", rs->ranges[i].start, rs->ranges[i].end);
 355 }
 356
 357 static void dump_line_log_data(struct line_log_data *r)
 358 {
 359         char buf[4096];
 360         while (r) {
 361                 snprintf(buf, 4096, "file %s\n", r->path);
 362                 dump_range_set(&r->ranges, buf);
 363                 r = r->next;
 364         }
 365 }
 366
 367 static void dump_diff_ranges(struct diff_ranges *diff, const char *desc)
 368 {
 369         int i;
 370         assert(diff->parent.nr == diff->target.nr);
 371         printf("diff ranges %s (%d items):\n", desc, diff->parent.nr);
 372         printf("\tparent\ttarget\n");
 373         for (i = 0; i < diff->parent.nr; i++) {
 374                 printf("\t[%ld,%ld]\t[%ld,%ld]\n",
 375                        diff->parent.ranges[i].start,
 376                        diff->parent.ranges[i].end,
 377                        diff->target.ranges[i].start,
 378                        diff->target.ranges[i].end);
 379         }
 380 }
 381 #endif
 382
 383
 384 static int ranges_overlap(struct range *a, struct range *b)
 385 {
 386         return !(a->end <= b->start || b->end <= a->start);
 387 }
 388
 389 /*
 390  * Given a diff and the set of interesting ranges, determine all hunks
 391  * of the diff which touch (overlap) at least one of the interesting
 392  * ranges in the target.
 393  */
 394 static void diff_ranges_filter_touched(struct diff_ranges *out,
 395                                        struct diff_ranges *diff,
 396                                        struct range_set *rs)
 397 {
 398         int i, j = 0;
 399
 400         assert(out->target.nr == 0);
 401
 402         for (i = 0; i < diff->target.nr; i++) {
 403                 while (diff->target.ranges[i].start > rs->ranges[j].end) {
 404                         j++;
 405                         if (j == rs->nr)
 406                                 return;
 407                 }
 408                 if (ranges_overlap(&diff->target.ranges[i], &rs->ranges[j])) {
 409                         range_set_append(&out->parent,
 410                                          diff->parent.ranges[i].start,
 411                                          diff->parent.ranges[i].end);
 412                         range_set_append(&out->target,
 413                                          diff->target.ranges[i].start,
 414                                          diff->target.ranges[i].end);
 415                 }
 416         }
 417 }
 418
 419 /*
 420  * Adjust the line counts in 'rs' to account for the lines
 421  * added/removed in the diff.
 422  */
 423 static void range_set_shift_diff(struct range_set *out,
 424                                  struct range_set *rs,
 425                                  struct diff_ranges *diff)
 426 {
 427         int i, j = 0;
 428         long offset = 0;
 429         struct range *src = rs->ranges;
 430         struct range *target = diff->target.ranges;
 431         struct range *parent = diff->parent.ranges;
 432
 433         for (i = 0; i < rs->nr; i++) {
 434                 while (j < diff->target.nr && src[i].start >= target[j].start) {
 435                         offset += (parent[j].end-parent[j].start)
 436                                 - (target[j].end-target[j].start);
 437                         j++;
 438                 }
 439                 range_set_append(out, src[i].start+offset, src[i].end+offset);
 440         }
 441 }
 442
 443 /*
 444  * Given a diff and the set of interesting ranges, map the ranges
 445  * across the diff.  That is: observe that the target commit takes
 446  * blame for all the + (target-side) ranges.  So for every pair of
 447  * ranges in the diff that was touched, we remove the latter and add
 448  * its parent side.
 449  */
 450 static void range_set_map_across_diff(struct range_set *out,
 451                                       struct range_set *rs,
 452                                       struct diff_ranges *diff,
 453                                       struct diff_ranges **touched_out)
 454 {
 455         struct diff_ranges *touched = xmalloc(sizeof(*touched));
 456         struct range_set tmp1 = RANGE_SET_INIT;
 457         struct range_set tmp2 = RANGE_SET_INIT;
 458
 459         diff_ranges_init(touched);
 460         diff_ranges_filter_touched(touched, diff, rs);
 461         range_set_difference(&tmp1, rs, &touched->target);
 462         range_set_shift_diff(&tmp2, &tmp1, diff);
 463         range_set_union(out, &tmp2, &touched->parent);
 464         range_set_release(&tmp1);
 465         range_set_release(&tmp2);
 466
 467         *touched_out = touched;
 468 }
 469
 470 static struct commit *check_single_commit(struct rev_info *revs)
 471 {
 472         struct object *commit = NULL;
 473         int found = -1;
 474         int i;
 475
 476         for (i = 0; i < revs->pending.nr; i++) {
 477                 struct object *obj = revs->pending.objects[i].item;
 478                 if (obj->flags & UNINTERESTING)
 479                         continue;
 480                 while (obj->type == OBJ_TAG)
 481                         obj = deref_tag(obj, NULL, 0);
 482                 if (obj->type != OBJ_COMMIT)
 483                         die("Non commit %s?", revs->pending.objects[i].name);
 484                 if (commit)
 485                         die("More than one commit to dig from: %s and %s?",
 486                             revs->pending.objects[i].name,
 487                             revs->pending.objects[found].name);
 488                 commit = obj;
 489                 found = i;
 490         }
 491
 492         if (!commit)
 493                 die("No commit specified?");
 494
 495         return (struct commit *) commit;
 496 }
 497
 498 static void fill_blob_sha1(struct commit *commit, struct diff_filespec *spec)
 499 {
 500         unsigned mode;
 501         unsigned char sha1[20];
 502
 503         if (get_tree_entry(commit->object.sha1, spec->path,
 504                            sha1, &mode))
 505                 die("There is no path %s in the commit", spec->path);
 506         fill_filespec(spec, sha1, 1, mode);
 507
 508         return;
 509 }
 510
 511 static void fill_line_ends(struct diff_filespec *spec, long *lines,
 512                            unsigned long **line_ends)
 513 {
 514         int num = 0, size = 50;
 515         long cur = 0;
 516         unsigned long *ends = NULL;
 517         char *data = NULL;
 518
 519         if (diff_populate_filespec(spec, 0))
 520                 die("Cannot read blob %s", sha1_to_hex(spec->sha1));
 521
 522         ends = xmalloc(size * sizeof(*ends));
 523         ends[cur++] = 0;
 524         data = spec->data;
 525         while (num < spec->size) {
 526                 if (data[num] == '\n' || num == spec->size - 1) {
 527                         ALLOC_GROW(ends, (cur + 1), size);
 528                         ends[cur++] = num;
 529                 }
 530                 num++;
 531         }
 532
 533         /* shrink the array to fit the elements */
 534         ends = xrealloc(ends, cur * sizeof(*ends));
 535         *lines = cur-1;
 536         *line_ends = ends;
 537 }
 538
 539 struct nth_line_cb {
 540         struct diff_filespec *spec;
 541         long lines;
 542         unsigned long *line_ends;
 543 };
 544
 545 static const char *nth_line(void *data, long line)
 546 {
 547         struct nth_line_cb *d = data;
 548         assert(d && line <= d->lines);
 549         assert(d->spec && d->spec->data);
 550
 551         if (line == 0)
 552                 return (char *)d->spec->data;
 553         else
 554                 return (char *)d->spec->data + d->line_ends[line] + 1;
 555 }
 556
 557 static struct line_log_data *
 558 parse_lines(struct commit *commit, const char *prefix, struct string_list *args)
 559 {
 560         long lines = 0;
 561         unsigned long *ends = NULL;
 562         struct nth_line_cb cb_data;
 563         struct string_list_item *item;
 564         struct line_log_data *ranges = NULL;
 565
 566         for_each_string_list_item(item, args) {
 567                 const char *name_part, *range_part;
 568                 char *full_name;
 569                 struct diff_filespec *spec;
 570                 long begin = 0, end = 0;
 571
 572                 name_part = skip_range_arg(item->string);
 573                 if (!name_part || *name_part != ':' || !name_part[1])
 574                         die("-L argument '%s' not of the form start,end:file",
 575                             item->string);
 576                 range_part = xstrndup(item->string, name_part - item->string);
 577                 name_part++;
 578
 579                 full_name = prefix_path(prefix, prefix ? strlen(prefix) : 0,
 580                                         name_part);
 581
 582                 spec = alloc_filespec(full_name);
 583                 fill_blob_sha1(commit, spec);
 584                 fill_line_ends(spec, &lines, &ends);
 585                 cb_data.spec = spec;
 586                 cb_data.lines = lines;
 587                 cb_data.line_ends = ends;
 588
 589                 if (parse_range_arg(range_part, nth_line, &cb_data,
 590                                     lines, &begin, &end,
 591                                     full_name))
 592                         die("malformed -L argument '%s'", range_part);
 593                 if (begin < 1)
 594                         begin = 1;
 595                 if (end < 1)
 596                         end = lines;
 597                 begin--;
 598                 if (lines < end || lines < begin)
 599                         die("file %s has only %ld lines", name_part, lines);
 600                 line_log_data_insert(&ranges, full_name, begin, end);
 601
 602                 free_filespec(spec);
 603                 free(ends);
 604                 ends = NULL;
 605         }
 606
 607         return ranges;
 608 }
 609
 610 static struct line_log_data *line_log_data_copy_one(struct line_log_data *r)
 611 {
 612         struct line_log_data *ret = xmalloc(sizeof(*ret));
 613
 614         assert(r);
 615         line_log_data_init(ret);
 616         range_set_copy(&ret->ranges, &r->ranges);
 617
 618         ret->path = xstrdup(r->path);
 619
 620         return ret;
 621 }
 622
 623 static struct line_log_data *
 624 line_log_data_copy(struct line_log_data *r)
 625 {
 626         struct line_log_data *ret = NULL;
 627         struct line_log_data *tmp = NULL, *prev = NULL;
 628
 629         assert(r);
 630         ret = tmp = prev = line_log_data_copy_one(r);
 631         r = r->next;
 632         while (r) {
 633                 tmp = line_log_data_copy_one(r);
 634                 prev->next = tmp;
 635                 prev = tmp;
 636                 r = r->next;
 637         }
 638
 639         return ret;
 640 }
 641
 642 /* merge two range sets across files */
 643 static struct line_log_data *line_log_data_merge(struct line_log_data *a,
 644                                                  struct line_log_data *b)
 645 {
 646         struct line_log_data *head = NULL, **pp = &head;
 647
 648         while (a || b) {
 649                 struct line_log_data *src;
 650                 struct line_log_data *src2 = NULL;
 651                 struct line_log_data *d;
 652                 int cmp;
 653                 if (!a)
 654                         cmp = 1;
 655                 else if (!b)
 656                         cmp = -1;
 657                 else
 658                         cmp = strcmp(a->path, b->path);
 659                 if (cmp < 0) {
 660                         src = a;
 661                         a = a->next;
 662                 } else if (cmp == 0) {
 663                         src = a;
 664                         a = a->next;
 665                         src2 = b;
 666                         b = b->next;
 667                 } else {
 668                         src = b;
 669                         b = b->next;
 670                 }
 671                 d = xmalloc(sizeof(struct line_log_data));
 672                 line_log_data_init(d);
 673                 d->path = xstrdup(src->path);
 674                 *pp = d;
 675                 pp = &d->next;
 676                 if (src2)
 677                         range_set_union(&d->ranges, &src->ranges, &src2->ranges);
 678                 else
 679                         range_set_copy(&d->ranges, &src->ranges);
 680         }
 681
 682         return head;
 683 }
 684
 685 static void add_line_range(struct rev_info *revs, struct commit *commit,
 686                            struct line_log_data *range)
 687 {
 688         struct line_log_data *old = NULL;
 689         struct line_log_data *new = NULL;
 690
 691         old = lookup_decoration(&revs->line_log_data, &commit->object);
 692         if (old && range) {
 693                 new = line_log_data_merge(old, range);
 694                 free_line_log_data(old);
 695         } else if (range)
 696                 new = line_log_data_copy(range);
 697
 698         if (new)
 699                 add_decoration(&revs->line_log_data, &commit->object, new);
 700 }
 701
 702 static void clear_commit_line_range(struct rev_info *revs, struct commit *commit)
 703 {
 704         struct line_log_data *r;
 705         r = lookup_decoration(&revs->line_log_data, &commit->object);
 706         if (!r)
 707                 return;
 708         free_line_log_data(r);
 709         add_decoration(&revs->line_log_data, &commit->object, NULL);
 710 }
 711
 712 static struct line_log_data *lookup_line_range(struct rev_info *revs,
 713                                                struct commit *commit)
 714 {
 715         struct line_log_data *ret = NULL;
 716         struct line_log_data *d;
 717
 718         ret = lookup_decoration(&revs->line_log_data, &commit->object);
 719
 720         for (d = ret; d; d = d->next)
 721                 range_set_check_invariants(&d->ranges);
 722
 723         return ret;
 724 }
 725
 726 void line_log_init(struct rev_info *rev, const char *prefix, struct string_list *args)
 727 {
 728         struct commit *commit = NULL;
 729         struct line_log_data *range;
 730
 731         commit = check_single_commit(rev);
 732         range = parse_lines(commit, prefix, args);
 733         add_line_range(rev, commit, range);
 734
 735         if (!rev->diffopt.detect_rename) {
 736                 int i, count = 0;
 737                 struct line_log_data *r = range;
 738                 const char **paths;
 739                 while (r) {
 740                         count++;
 741                         r = r->next;
 742                 }
 743                 paths = xmalloc((count+1)*sizeof(char *));
 744                 r = range;
 745                 for (i = 0; i < count; i++) {
 746                         paths[i] = xstrdup(r->path);
 747                         r = r->next;
 748                 }
 749                 paths[count] = NULL;
 750                 parse_pathspec(&rev->diffopt.pathspec, 0, 0, "", paths);
 751                 free(paths);
 752         }
 753 }
 754
 755 static void load_tree_desc(struct tree_desc *desc, void **tree,
 756                            const unsigned char *sha1)
 757 {
 758         unsigned long size;
 759         *tree = read_object_with_reference(sha1, tree_type, &size, NULL);
 760         if (!*tree)
 761                 die("Unable to read tree (%s)", sha1_to_hex(sha1));
 762         init_tree_desc(desc, *tree, size);
 763 }
 764
 765 static int count_parents(struct commit *commit)
 766 {
 767         struct commit_list *parents = commit->parents;
 768         int count = 0;
 769         while (parents) {
 770                 count++;
 771                 parents = parents->next;
 772         }
 773         return count;
 774 }
 775
 776 static void move_diff_queue(struct diff_queue_struct *dst,
 777                             struct diff_queue_struct *src)
 778 {
 779         assert(src != dst);
 780         memcpy(dst, src, sizeof(struct diff_queue_struct));
 781         DIFF_QUEUE_CLEAR(src);
 782 }
 783
 784 static void filter_diffs_for_paths(struct line_log_data *range, int keep_deletions)
 785 {
 786         int i;
 787         struct diff_queue_struct outq;
 788         DIFF_QUEUE_CLEAR(&outq);
 789
 790         for (i = 0; i < diff_queued_diff.nr; i++) {
 791                 struct diff_filepair *p = diff_queued_diff.queue[i];
 792                 struct line_log_data *rg = NULL;
 793
 794                 if (!DIFF_FILE_VALID(p->two)) {
 795                         if (keep_deletions)
 796                                 diff_q(&outq, p);
 797                         else
 798                                 diff_free_filepair(p);
 799                         continue;
 800                 }
 801                 for (rg = range; rg; rg = rg->next) {
 802                         if (!strcmp(rg->path, p->two->path))
 803                                 break;
 804                 }
 805                 if (rg)
 806                         diff_q(&outq, p);
 807                 else
 808                         diff_free_filepair(p);
 809         }
 810         free(diff_queued_diff.queue);
 811         diff_queued_diff = outq;
 812 }
 813
 814 static inline int diff_might_be_rename(void)
 815 {
 816         int i;
 817         for (i = 0; i < diff_queued_diff.nr; i++)
 818                 if (!DIFF_FILE_VALID(diff_queued_diff.queue[i]->one)) {
 819                         /* fprintf(stderr, "diff_might_be_rename found creation of: %s\n", */
 820                         /*      diff_queued_diff.queue[i]->two->path); */
 821                         return 1;
 822                 }
 823         return 0;
 824 }
 825
 826 static void queue_diffs(struct line_log_data *range,
 827                         struct diff_options *opt,
 828                         struct diff_queue_struct *queue,
 829                         struct commit *commit, struct commit *parent)
 830 {
 831         void *tree1 = NULL, *tree2 = NULL;
 832         struct tree_desc desc1, desc2;
 833
 834         assert(commit);
 835         load_tree_desc(&desc2, &tree2, commit->tree->object.sha1);
 836         if (parent)
 837                 load_tree_desc(&desc1, &tree1, parent->tree->object.sha1);
 838         else
 839                 init_tree_desc(&desc1, "", 0);
 840
 841         DIFF_QUEUE_CLEAR(&diff_queued_diff);
 842         diff_tree(&desc1, &desc2, "", opt);
 843         if (opt->detect_rename) {
 844                 filter_diffs_for_paths(range, 1);
 845                 if (diff_might_be_rename())
 846                         diffcore_std(opt);
 847                 filter_diffs_for_paths(range, 0);
 848         }
 849         move_diff_queue(queue, &diff_queued_diff);
 850
 851         if (tree1)
 852                 free(tree1);
 853         if (tree2)
 854                 free(tree2);
 855 }
 856
 857 static char *get_nth_line(long line, unsigned long *ends, void *data)
 858 {
 859         if (line == 0)
 860                 return (char *)data;
 861         else
 862                 return (char *)data + ends[line] + 1;
 863 }
 864
 865 static void print_line(const char *prefix, char first,
 866                        long line, unsigned long *ends, void *data,
 867                        const char *color, const char *reset)
 868 {
 869         char *begin = get_nth_line(line, ends, data);
 870         char *end = get_nth_line(line+1, ends, data);
 871         int had_nl = 0;
 872
 873         if (end > begin && end[-1] == '\n') {
 874                 end--;
 875                 had_nl = 1;
 876         }
 877
 878         fputs(prefix, stdout);
 879         fputs(color, stdout);
 880         putchar(first);
 881         fwrite(begin, 1, end-begin, stdout);
 882         fputs(reset, stdout);
 883         putchar('\n');
 884         if (!had_nl)
 885                 fputs("\\ No newline at end of file\n", stdout);
 886 }
 887
 888 static char *output_prefix(struct diff_options *opt)
 889 {
 890         char *prefix = "";
 891
 892         if (opt->output_prefix) {
 893                 struct strbuf *sb = opt->output_prefix(opt, opt->output_prefix_data);
 894                 prefix = sb->buf;
 895         }
 896
 897         return prefix;
 898 }
 899
 900 static void dump_diff_hacky_one(struct rev_info *rev, struct line_log_data *range)
 901 {
 902         int i, j = 0;
 903         long p_lines, t_lines;
 904         unsigned long *p_ends = NULL, *t_ends = NULL;
 905         struct diff_filepair *pair = range->pair;
 906         struct diff_ranges *diff = &range->diff;
 907
 908         struct diff_options *opt = &rev->diffopt;
 909         char *prefix = output_prefix(opt);
 910         const char *c_reset = diff_get_color(opt->use_color, DIFF_RESET);
 911         const char *c_frag = diff_get_color(opt->use_color, DIFF_FRAGINFO);
 912         const char *c_meta = diff_get_color(opt->use_color, DIFF_METAINFO);
 913         const char *c_old = diff_get_color(opt->use_color, DIFF_FILE_OLD);
 914         const char *c_new = diff_get_color(opt->use_color, DIFF_FILE_NEW);
 915         const char *c_plain = diff_get_color(opt->use_color, DIFF_PLAIN);
 916
 917         if (!pair || !diff)
 918                 return;
 919
 920         if (pair->one->sha1_valid)
 921                 fill_line_ends(pair->one, &p_lines, &p_ends);
 922         fill_line_ends(pair->two, &t_lines, &t_ends);
 923
 924         printf("%s%sdiff --git a/%s b/%s%s\n", prefix, c_meta, pair->one->path, pair->two->path, c_reset);
 925         printf("%s%s--- %s%s%s\n", prefix, c_meta,
 926                pair->one->sha1_valid ? "a/" : "",
 927                pair->one->sha1_valid ? pair->one->path : "/dev/null",
 928                c_reset);
 929         printf("%s%s+++ b/%s%s\n", prefix, c_meta, pair->two->path, c_reset);
 930         for (i = 0; i < range->ranges.nr; i++) {
 931                 long p_start, p_end;
 932                 long t_start = range->ranges.ranges[i].start;
 933                 long t_end = range->ranges.ranges[i].end;
 934                 long t_cur = t_start;
 935                 int j_last;
 936
 937                 while (j < diff->target.nr && diff->target.ranges[j].end < t_start)
 938                         j++;
 939                 if (j == diff->target.nr || diff->target.ranges[j].start > t_end)
 940                         continue;
 941
 942                 /* Scan ahead to determine the last diff that falls in this range */
 943                 j_last = j;
 944                 while (j_last < diff->target.nr && diff->target.ranges[j_last].start < t_end)
 945                         j_last++;
 946                 if (j_last > j)
 947                         j_last--;
 948
 949                 /*
 950                  * Compute parent hunk headers: we know that the diff
 951                  * has the correct line numbers (but not all hunks).
 952                  * So it suffices to shift the start/end according to
 953                  * the line numbers of the first/last hunk(s) that
 954                  * fall in this range.
 955                  */
 956                 if (t_start < diff->target.ranges[j].start)
 957                         p_start = diff->parent.ranges[j].start - (diff->target.ranges[j].start-t_start);
 958                 else
 959                         p_start = diff->parent.ranges[j].start;
 960                 if (t_end > diff->target.ranges[j_last].end)
 961                         p_end = diff->parent.ranges[j_last].end + (t_end-diff->target.ranges[j_last].end);
 962                 else
 963                         p_end = diff->parent.ranges[j_last].end;
 964
 965                 if (!p_start && !p_end) {
 966                         p_start = -1;
 967                         p_end = -1;
 968                 }
 969
 970                 /* Now output a diff hunk for this range */
 971                 printf("%s%s@@ -%ld,%ld +%ld,%ld @@%s\n",
 972                        prefix, c_frag,
 973                        p_start+1, p_end-p_start, t_start+1, t_end-t_start,
 974                        c_reset);
 975                 while (j < diff->target.nr && diff->target.ranges[j].start < t_end) {
 976                         int k;
 977                         for (; t_cur < diff->target.ranges[j].start; t_cur++)
 978                                 print_line(prefix, ' ', t_cur, t_ends, pair->two->data,
 979                                            c_plain, c_reset);
 980                         for (k = diff->parent.ranges[j].start; k < diff->parent.ranges[j].end; k++)
 981                                 print_line(prefix, '-', k, p_ends, pair->one->data,
 982                                            c_old, c_reset);
 983                         for (; t_cur < diff->target.ranges[j].end && t_cur < t_end; t_cur++)
 984                                 print_line(prefix, '+', t_cur, t_ends, pair->two->data,
 985                                            c_new, c_reset);
 986                         j++;
 987                 }
 988                 for (; t_cur < t_end; t_cur++)
 989                         print_line(prefix, ' ', t_cur, t_ends, pair->two->data,
 990                                    c_plain, c_reset);
 991         }
 992
 993         free(p_ends);
 994         free(t_ends);
 995 }
 996
 997 /*
 998  * NEEDSWORK: manually building a diff here is not the Right
 999  * Thing(tm).  log -L should be built into the diff pipeline.
1000  */
1001 static void dump_diff_hacky(struct rev_info *rev, struct line_log_data *range)
1002 {
1003         puts(output_prefix(&rev->diffopt));
1004         while (range) {
1005                 dump_diff_hacky_one(rev, range);
1006                 range = range->next;
1007         }
1008 }
1009
1010 /*
1011  * Unlike most other functions, this destructively operates on
1012  * 'range'.
1013  */
1014 static int process_diff_filepair(struct rev_info *rev,
1015                                  struct diff_filepair *pair,
1016                                  struct line_log_data *range,
1017                                  struct diff_ranges **diff_out)
1018 {
1019         struct line_log_data *rg = range;
1020         struct range_set tmp;
1021         struct diff_ranges diff;
1022         mmfile_t file_parent, file_target;
1023
1024         assert(pair->two->path);
1025         while (rg) {
1026                 assert(rg->path);
1027                 if (!strcmp(rg->path, pair->two->path))
1028                         break;
1029                 rg = rg->next;
1030         }
1031
1032         if (!rg)
1033                 return 0;
1034         if (rg->ranges.nr == 0)
1035                 return 0;
1036
1037         assert(pair->two->sha1_valid);
1038         diff_populate_filespec(pair->two, 0);
1039         file_target.ptr = pair->two->data;
1040         file_target.size = pair->two->size;
1041
1042         if (pair->one->sha1_valid) {
1043                 diff_populate_filespec(pair->one, 0);
1044                 file_parent.ptr = pair->one->data;
1045                 file_parent.size = pair->one->size;
1046         } else {
1047                 file_parent.ptr = "";
1048                 file_parent.size = 0;
1049         }
1050
1051         diff_ranges_init(&diff);
1052         collect_diff(&file_parent, &file_target, &diff);
1053
1054         /* NEEDSWORK should apply some heuristics to prevent mismatches */
1055         free(rg->path);
1056         rg->path = xstrdup(pair->one->path);
1057
1058         range_set_init(&tmp, 0);
1059         range_set_map_across_diff(&tmp, &rg->ranges, &diff, diff_out);
1060         range_set_release(&rg->ranges);
1061         range_set_move(&rg->ranges, &tmp);
1062
1063         diff_ranges_release(&diff);
1064
1065         return ((*diff_out)->parent.nr > 0);
1066 }
1067
1068 static struct diff_filepair *diff_filepair_dup(struct diff_filepair *pair)
1069 {
1070         struct diff_filepair *new = xmalloc(sizeof(struct diff_filepair));
1071         new->one = pair->one;
1072         new->two = pair->two;
1073         new->one->count++;
1074         new->two->count++;
1075         return new;
1076 }
1077
1078 static void free_diffqueues(int n, struct diff_queue_struct *dq)
1079 {
1080         int i, j;
1081         for (i = 0; i < n; i++)
1082                 for (j = 0; j < dq[i].nr; j++)
1083                         diff_free_filepair(dq[i].queue[j]);
1084         free(dq);
1085 }
1086
1087 static int process_all_files(struct line_log_data **range_out,
1088                              struct rev_info *rev,
1089                              struct diff_queue_struct *queue,
1090                              struct line_log_data *range)
1091 {
1092         int i, changed = 0;
1093
1094         *range_out = line_log_data_copy(range);
1095
1096         for (i = 0; i < queue->nr; i++) {
1097                 struct diff_ranges *pairdiff = NULL;
1098                 struct diff_filepair *pair = queue->queue[i];
1099                 if (process_diff_filepair(rev, pair, *range_out, &pairdiff)) {
1100                         /*
1101                          * Store away the diff for later output.  We
1102                          * tuck it in the ranges we got as _input_,
1103                          * since that's the commit that caused the
1104                          * diff.
1105                          *
1106                          * NEEDSWORK not enough when we get around to
1107                          * doing something interesting with merges;
1108                          * currently each invocation on a merge parent
1109                          * trashes the previous one's diff.
1110                          *
1111                          * NEEDSWORK tramples over data structures not owned here
1112                          */
1113                         struct line_log_data *rg = range;
1114                         changed++;
1115                         while (rg && strcmp(rg->path, pair->two->path))
1116                                 rg = rg->next;
1117                         assert(rg);
1118                         rg->pair = diff_filepair_dup(queue->queue[i]);
1119                         memcpy(&rg->diff, pairdiff, sizeof(struct diff_ranges));
1120                 }
1121         }
1122
1123         return changed;
1124 }
1125
1126 int line_log_print(struct rev_info *rev, struct commit *commit)
1127 {
1128         struct line_log_data *range = lookup_line_range(rev, commit);
1129
1130         show_log(rev);
1131         dump_diff_hacky(rev, range);
1132         return 1;
1133 }
1134
1135 static int process_ranges_ordinary_commit(struct rev_info *rev, struct commit *commit,
1136                                           struct line_log_data *range)
1137 {
1138         struct commit *parent = NULL;
1139         struct diff_queue_struct queue;
1140         struct line_log_data *parent_range;
1141         int changed;
1142
1143         if (commit->parents)
1144                 parent = commit->parents->item;
1145
1146         queue_diffs(range, &rev->diffopt, &queue, commit, parent);
1147         changed = process_all_files(&parent_range, rev, &queue, range);
1148         if (parent)
1149                 add_line_range(rev, parent, parent_range);
1150         return changed;
1151 }
1152
1153 static int process_ranges_merge_commit(struct rev_info *rev, struct commit *commit,
1154                                        struct line_log_data *range)
1155 {
1156         struct diff_queue_struct *diffqueues;
1157         struct line_log_data **cand;
1158         struct commit **parents;
1159         struct commit_list *p;
1160         int i;
1161         int nparents = count_parents(commit);
1162
1163         diffqueues = xmalloc(nparents * sizeof(*diffqueues));
1164         cand = xmalloc(nparents * sizeof(*cand));
1165         parents = xmalloc(nparents * sizeof(*parents));
1166
1167         p = commit->parents;
1168         for (i = 0; i < nparents; i++) {
1169                 parents[i] = p->item;
1170                 p = p->next;
1171                 queue_diffs(range, &rev->diffopt, &diffqueues[i], commit, parents[i]);
1172         }
1173
1174         for (i = 0; i < nparents; i++) {
1175                 int changed;
1176                 cand[i] = NULL;
1177                 changed = process_all_files(&cand[i], rev, &diffqueues[i], range);
1178                 if (!changed) {
1179                         /*
1180                          * This parent can take all the blame, so we
1181                          * don't follow any other path in history
1182                          */
1183                         add_line_range(rev, parents[i], cand[i]);
1184                         clear_commit_line_range(rev, commit);
1185                         commit->parents = xmalloc(sizeof(struct commit_list));
1186                         commit->parents->item = parents[i];
1187                         commit->parents->next = NULL;
1188                         free(parents);
1189                         free(cand);
1190                         free_diffqueues(nparents, diffqueues);
1191                         /* NEEDSWORK leaking like a sieve */
1192                         return 0;
1193                 }
1194         }
1195
1196         /*
1197          * No single parent took the blame.  We add the candidates
1198          * from the above loop to the parents.
1199          */
1200         for (i = 0; i < nparents; i++) {
1201                 add_line_range(rev, parents[i], cand[i]);
1202         }
1203
1204         clear_commit_line_range(rev, commit);
1205         free(parents);
1206         free(cand);
1207         free_diffqueues(nparents, diffqueues);
1208         return 1;
1209
1210         /* NEEDSWORK evil merge detection stuff */
1211         /* NEEDSWORK leaking like a sieve */
1212 }
1213
1214 static int process_ranges_arbitrary_commit(struct rev_info *rev, struct commit *commit)
1215 {
1216         struct line_log_data *range = lookup_line_range(rev, commit);
1217         int changed = 0;
1218
1219         if (range) {
1220                 if (!commit->parents || !commit->parents->next)
1221                         changed = process_ranges_ordinary_commit(rev, commit, range);
1222                 else
1223                         changed = process_ranges_merge_commit(rev, commit, range);
1224         }
1225
1226         if (!changed)
1227                 commit->object.flags |= TREESAME;
1228
1229         return changed;
1230 }
1231
1232 static enum rewrite_result line_log_rewrite_one(struct rev_info *rev, struct commit **pp)
1233 {
1234         for (;;) {
1235                 struct commit *p = *pp;
1236                 if (p->parents && p->parents->next)
1237                         return rewrite_one_ok;
1238                 if (p->object.flags & UNINTERESTING)
1239                         return rewrite_one_ok;
1240                 if (!(p->object.flags & TREESAME))
1241                         return rewrite_one_ok;
1242                 if (!p->parents)
1243                         return rewrite_one_noparents;
1244                 *pp = p->parents->item;
1245         }
1246 }
1247
1248 int line_log_filter(struct rev_info *rev)
1249 {
1250         struct commit *commit;
1251         struct commit_list *list = rev->commits;
1252         struct commit_list *out = NULL, **pp = &out;
1253
1254         while (list) {
1255                 struct commit_list *to_free = NULL;
1256                 commit = list->item;
1257                 if (process_ranges_arbitrary_commit(rev, commit)) {
1258                         *pp = list;
1259                         pp = &list->next;
1260                 } else
1261                         to_free = list;
1262                 list = list->next;
1263                 free(to_free);
1264         }
1265         *pp = NULL;
1266
1267         for (list = out; list; list = list->next)
1268                 rewrite_parents(rev, list->item, line_log_rewrite_one);
1269
1270         rev->commits = out;
1271
1272         return 0;
1273 }