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->spec->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 static void line_log_data_insert(struct line_log_data **list,
 279                                  struct diff_filespec *spec,
 280                                  long begin, long end)
 281 {
 282         struct line_log_data *ip;
 283         struct line_log_data *p = search_line_log_data(*list, spec->path, &ip);
 284
 285         if (p) {
 286                 range_set_append_unsafe(&p->ranges, begin, end);
 287                 sort_and_merge_range_set(&p->ranges);
 288                 free_filespec(spec);
 289                 return;
 290         }
 291
 292         p = xcalloc(1, sizeof(struct line_log_data));
 293         p->spec = spec;
 294         range_set_append(&p->ranges, begin, end);
 295         if (ip) {
 296                 p->next = ip->next;
 297                 ip->next = p;
 298         } else {
 299                 p->next = *list;
 300                 *list = p;
 301         }
 302 }
 303
 304 struct collect_diff_cbdata {
 305         struct diff_ranges *diff;
 306 };
 307
 308 static int collect_diff_cb(long start_a, long count_a,
 309                            long start_b, long count_b,
 310                            void *data)
 311 {
 312         struct collect_diff_cbdata *d = data;
 313
 314         if (count_a >= 0)
 315                 range_set_append(&d->diff->parent, start_a, start_a + count_a);
 316         if (count_b >= 0)
 317                 range_set_append(&d->diff->target, start_b, start_b + count_b);
 318
 319         return 0;
 320 }
 321
 322 static void collect_diff(mmfile_t *parent, mmfile_t *target, struct diff_ranges *out)
 323 {
 324         struct collect_diff_cbdata cbdata = {NULL};
 325         xpparam_t xpp;
 326         xdemitconf_t xecfg;
 327         xdemitcb_t ecb;
 328
 329         memset(&xpp, 0, sizeof(xpp));
 330         memset(&xecfg, 0, sizeof(xecfg));
 331         xecfg.ctxlen = xecfg.interhunkctxlen = 0;
 332
 333         cbdata.diff = out;
 334         xecfg.hunk_func = collect_diff_cb;
 335         memset(&ecb, 0, sizeof(ecb));
 336         ecb.priv = &cbdata;
 337         xdi_diff(parent, target, &xpp, &xecfg, &ecb);
 338 }
 339
 340 /*
 341  * These are handy for debugging.  Removing them with #if 0 silences
 342  * the "unused function" warning.
 343  */
 344 #if 0
 345 static void dump_range_set(struct range_set *rs, const char *desc)
 346 {
 347         int i;
 348         printf("range set %s (%d items):\n", desc, rs->nr);
 349         for (i = 0; i < rs->nr; i++)
 350                 printf("\t[%ld,%ld]\n", rs->ranges[i].start, rs->ranges[i].end);
 351 }
 352
 353 static void dump_line_log_data(struct line_log_data *r)
 354 {
 355         char buf[4096];
 356         while (r) {
 357                 snprintf(buf, 4096, "file %s\n", r->spec->path);
 358                 dump_range_set(&r->ranges, buf);
 359                 r = r->next;
 360         }
 361 }
 362
 363 static void dump_diff_ranges(struct diff_ranges *diff, const char *desc)
 364 {
 365         int i;
 366         assert(diff->parent.nr == diff->target.nr);
 367         printf("diff ranges %s (%d items):\n", desc, diff->parent.nr);
 368         printf("\tparent\ttarget\n");
 369         for (i = 0; i < diff->parent.nr; i++) {
 370                 printf("\t[%ld,%ld]\t[%ld,%ld]\n",
 371                        diff->parent.ranges[i].start,
 372                        diff->parent.ranges[i].end,
 373                        diff->target.ranges[i].start,
 374                        diff->target.ranges[i].end);
 375         }
 376 }
 377 #endif
 378
 379
 380 static int ranges_overlap(struct range *a, struct range *b)
 381 {
 382         return !(a->end <= b->start || b->end <= a->start);
 383 }
 384
 385 /*
 386  * Given a diff and the set of interesting ranges, determine all hunks
 387  * of the diff which touch (overlap) at least one of the interesting
 388  * ranges in the target.
 389  */
 390 static void diff_ranges_filter_touched(struct diff_ranges *out,
 391                                        struct diff_ranges *diff,
 392                                        struct range_set *rs)
 393 {
 394         int i, j = 0;
 395
 396         assert(out->target.nr == 0);
 397
 398         for (i = 0; i < diff->target.nr; i++) {
 399                 while (diff->target.ranges[i].start > rs->ranges[j].end) {
 400                         j++;
 401                         if (j == rs->nr)
 402                                 return;
 403                 }
 404                 if (ranges_overlap(&diff->target.ranges[i], &rs->ranges[j])) {
 405                         range_set_append(&out->parent,
 406                                          diff->parent.ranges[i].start,
 407                                          diff->parent.ranges[i].end);
 408                         range_set_append(&out->target,
 409                                          diff->target.ranges[i].start,
 410                                          diff->target.ranges[i].end);
 411                 }
 412         }
 413 }
 414
 415 /*
 416  * Adjust the line counts in 'rs' to account for the lines
 417  * added/removed in the diff.
 418  */
 419 static void range_set_shift_diff(struct range_set *out,
 420                                  struct range_set *rs,
 421                                  struct diff_ranges *diff)
 422 {
 423         int i, j = 0;
 424         long offset = 0;
 425         struct range *src = rs->ranges;
 426         struct range *target = diff->target.ranges;
 427         struct range *parent = diff->parent.ranges;
 428
 429         for (i = 0; i < rs->nr; i++) {
 430                 while (j < diff->target.nr && src[i].start >= target[j].start) {
 431                         offset += (parent[j].end-parent[j].start)
 432                                 - (target[j].end-target[j].start);
 433                         j++;
 434                 }
 435                 range_set_append(out, src[i].start+offset, src[i].end+offset);
 436         }
 437 }
 438
 439 /*
 440  * Given a diff and the set of interesting ranges, map the ranges
 441  * across the diff.  That is: observe that the target commit takes
 442  * blame for all the + (target-side) ranges.  So for every pair of
 443  * ranges in the diff that was touched, we remove the latter and add
 444  * its parent side.
 445  */
 446 static void range_set_map_across_diff(struct range_set *out,
 447                                       struct range_set *rs,
 448                                       struct diff_ranges *diff,
 449                                       struct diff_ranges **touched_out)
 450 {
 451         struct diff_ranges *touched = xmalloc(sizeof(*touched));
 452         struct range_set tmp1 = RANGE_SET_INIT;
 453         struct range_set tmp2 = RANGE_SET_INIT;
 454
 455         diff_ranges_init(touched);
 456         diff_ranges_filter_touched(touched, diff, rs);
 457         range_set_difference(&tmp1, rs, &touched->target);
 458         range_set_shift_diff(&tmp2, &tmp1, diff);
 459         range_set_union(out, &tmp2, &touched->parent);
 460         range_set_release(&tmp1);
 461         range_set_release(&tmp2);
 462
 463         *touched_out = touched;
 464 }
 465
 466 static struct commit *check_single_commit(struct rev_info *revs)
 467 {
 468         struct object *commit = NULL;
 469         int found = -1;
 470         int i;
 471
 472         for (i = 0; i < revs->pending.nr; i++) {
 473                 struct object *obj = revs->pending.objects[i].item;
 474                 if (obj->flags & UNINTERESTING)
 475                         continue;
 476                 while (obj->type == OBJ_TAG)
 477                         obj = deref_tag(obj, NULL, 0);
 478                 if (obj->type != OBJ_COMMIT)
 479                         die("Non commit %s?", revs->pending.objects[i].name);
 480                 if (commit)
 481                         die("More than one commit to dig from: %s and %s?",
 482                             revs->pending.objects[i].name,
 483                             revs->pending.objects[found].name);
 484                 commit = obj;
 485                 found = i;
 486         }
 487
 488         if (!commit)
 489                 die("No commit specified?");
 490
 491         return (struct commit *) commit;
 492 }
 493
 494 static void fill_blob_sha1(struct commit *commit, struct diff_filespec *spec)
 495 {
 496         unsigned mode;
 497         unsigned char sha1[20];
 498
 499         if (get_tree_entry(commit->object.sha1, spec->path,
 500                            sha1, &mode))
 501                 die("There is no path %s in the commit", spec->path);
 502         fill_filespec(spec, sha1, 1, mode);
 503
 504         return;
 505 }
 506
 507 static void fill_line_ends(struct diff_filespec *spec, long *lines,
 508                            unsigned long **line_ends)
 509 {
 510         int num = 0, size = 50;
 511         long cur = 0;
 512         unsigned long *ends = NULL;
 513         char *data = NULL;
 514
 515         if (diff_populate_filespec(spec, 0))
 516                 die("Cannot read blob %s", sha1_to_hex(spec->sha1));
 517
 518         ends = xmalloc(size * sizeof(*ends));
 519         ends[cur++] = 0;
 520         data = spec->data;
 521         while (num < spec->size) {
 522                 if (data[num] == '\n' || num == spec->size - 1) {
 523                         ALLOC_GROW(ends, (cur + 1), size);
 524                         ends[cur++] = num;
 525                 }
 526                 num++;
 527         }
 528
 529         /* shrink the array to fit the elements */
 530         ends = xrealloc(ends, cur * sizeof(*ends));
 531         *lines = cur-1;
 532         *line_ends = ends;
 533 }
 534
 535 struct nth_line_cb {
 536         struct diff_filespec *spec;
 537         long lines;
 538         unsigned long *line_ends;
 539 };
 540
 541 static const char *nth_line(void *data, long line)
 542 {
 543         struct nth_line_cb *d = data;
 544         assert(d && line <= d->lines);
 545         assert(d->spec && d->spec->data);
 546
 547         if (line == 0)
 548                 return (char *)d->spec->data;
 549         else
 550                 return (char *)d->spec->data + d->line_ends[line] + 1;
 551 }
 552
 553 static struct line_log_data *
 554 parse_lines(struct commit *commit, const char *prefix, struct string_list *args)
 555 {
 556         long lines = 0;
 557         unsigned long *ends = NULL;
 558         struct nth_line_cb cb_data;
 559         struct string_list_item *item;
 560         struct line_log_data *ranges = NULL;
 561
 562         for_each_string_list_item(item, args) {
 563                 const char *name_part, *range_part;
 564                 const char *full_name;
 565                 struct diff_filespec *spec;
 566                 long begin = 0, end = 0;
 567
 568                 name_part = skip_range_arg(item->string);
 569                 if (!name_part || *name_part != ':' || !name_part[1])
 570                         die("-L argument '%s' not of the form start,end:file",
 571                             item->string);
 572                 range_part = xstrndup(item->string, name_part - item->string);
 573                 name_part++;
 574
 575                 full_name = prefix_path(prefix, prefix ? strlen(prefix) : 0,
 576                                         name_part);
 577
 578                 spec = alloc_filespec(full_name);
 579                 fill_blob_sha1(commit, spec);
 580                 fill_line_ends(spec, &lines, &ends);
 581                 cb_data.spec = spec;
 582                 cb_data.lines = lines;
 583                 cb_data.line_ends = ends;
 584
 585                 if (parse_range_arg(range_part, nth_line, &cb_data,
 586                                     lines, &begin, &end,
 587                                     spec->path))
 588                         die("malformed -L argument '%s'", range_part);
 589                 if (begin < 1)
 590                         begin = 1;
 591                 if (end < 1)
 592                         end = lines;
 593                 begin--;
 594                 if (lines < end || lines < begin)
 595                         die("file %s has only %ld lines", name_part, lines);
 596                 line_log_data_insert(&ranges, spec, begin, end);
 597
 598                 free(ends);
 599                 ends = NULL;
 600         }
 601
 602         return ranges;
 603 }
 604
 605 static struct line_log_data *line_log_data_copy_one(struct line_log_data *r)
 606 {
 607         struct line_log_data *ret = xmalloc(sizeof(*ret));
 608
 609         assert(r);
 610         line_log_data_init(ret);
 611         range_set_copy(&ret->ranges, &r->ranges);
 612
 613         ret->spec = r->spec;
 614         assert(ret->spec);
 615         ret->spec->count++;
 616
 617         return ret;
 618 }
 619
 620 static struct line_log_data *
 621 line_log_data_copy(struct line_log_data *r)
 622 {
 623         struct line_log_data *ret = NULL;
 624         struct line_log_data *tmp = NULL, *prev = NULL;
 625
 626         assert(r);
 627         ret = tmp = prev = line_log_data_copy_one(r);
 628         r = r->next;
 629         while (r) {
 630                 tmp = line_log_data_copy_one(r);
 631                 prev->next = tmp;
 632                 prev = tmp;
 633                 r = r->next;
 634         }
 635
 636         return ret;
 637 }
 638
 639 /* merge two range sets across files */
 640 static struct line_log_data *line_log_data_merge(struct line_log_data *a,
 641                                                  struct line_log_data *b)
 642 {
 643         struct line_log_data *head = NULL, **pp = &head;
 644
 645         while (a || b) {
 646                 struct line_log_data *src;
 647                 struct line_log_data *src2 = NULL;
 648                 struct line_log_data *d;
 649                 int cmp;
 650                 if (!a)
 651                         cmp = 1;
 652                 else if (!b)
 653                         cmp = -1;
 654                 else
 655                         cmp = strcmp(a->spec->path, b->spec->path);
 656                 if (cmp < 0) {
 657                         src = a;
 658                         a = a->next;
 659                 } else if (cmp == 0) {
 660                         src = a;
 661                         a = a->next;
 662                         src2 = b;
 663                         b = b->next;
 664                 } else {
 665                         src = b;
 666                         b = b->next;
 667                 }
 668                 d = xmalloc(sizeof(struct line_log_data));
 669                 line_log_data_init(d);
 670                 d->spec = src->spec;
 671                 d->spec->count++;
 672                 *pp = d;
 673                 pp = &d->next;
 674                 if (src2)
 675                         range_set_union(&d->ranges, &src->ranges, &src2->ranges);
 676                 else
 677                         range_set_copy(&d->ranges, &src->ranges);
 678         }
 679
 680         return head;
 681 }
 682
 683 static void add_line_range(struct rev_info *revs, struct commit *commit,
 684                            struct line_log_data *range)
 685 {
 686         struct line_log_data *old = NULL;
 687         struct line_log_data *new = NULL;
 688
 689         old = lookup_decoration(&revs->line_log_data, &commit->object);
 690         if (old && range) {
 691                 new = line_log_data_merge(old, range);
 692                 free_line_log_data(old);
 693         } else if (range)
 694                 new = line_log_data_copy(range);
 695
 696         if (new)
 697                 add_decoration(&revs->line_log_data, &commit->object, new);
 698 }
 699
 700 static void clear_commit_line_range(struct rev_info *revs, struct commit *commit)
 701 {
 702         struct line_log_data *r;
 703         r = lookup_decoration(&revs->line_log_data, &commit->object);
 704         if (!r)
 705                 return;
 706         free_line_log_data(r);
 707         add_decoration(&revs->line_log_data, &commit->object, NULL);
 708 }
 709
 710 static struct line_log_data *lookup_line_range(struct rev_info *revs,
 711                                                struct commit *commit)
 712 {
 713         struct line_log_data *ret = NULL;
 714         struct line_log_data *d;
 715
 716         ret = lookup_decoration(&revs->line_log_data, &commit->object);
 717
 718         for (d = ret; d; d = d->next)
 719                 range_set_check_invariants(&d->ranges);
 720
 721         return ret;
 722 }
 723
 724 void line_log_init(struct rev_info *rev, const char *prefix, struct string_list *args)
 725 {
 726         struct commit *commit = NULL;
 727         struct line_log_data *range;
 728
 729         commit = check_single_commit(rev);
 730         range = parse_lines(commit, prefix, args);
 731         add_line_range(rev, commit, range);
 732
 733         if (!rev->diffopt.detect_rename) {
 734                 int i, count = 0;
 735                 struct line_log_data *r = range;
 736                 const char **paths;
 737                 while (r) {
 738                         count++;
 739                         r = r->next;
 740                 }
 741                 paths = xmalloc((count+1)*sizeof(char *));
 742                 r = range;
 743                 for (i = 0; i < count; i++) {
 744                         paths[i] = xstrdup(r->spec->path);
 745                         r = r->next;
 746                 }
 747                 paths[count] = NULL;
 748                 init_pathspec(&rev->diffopt.pathspec, paths);
 749                 free(paths);
 750         }
 751 }
 752
 753 static void load_tree_desc(struct tree_desc *desc, void **tree,
 754                            const unsigned char *sha1)
 755 {
 756         unsigned long size;
 757         *tree = read_object_with_reference(sha1, tree_type, &size, NULL);
 758         if (!*tree)
 759                 die("Unable to read tree (%s)", sha1_to_hex(sha1));
 760         init_tree_desc(desc, *tree, size);
 761 }
 762
 763 static int count_parents(struct commit *commit)
 764 {
 765         struct commit_list *parents = commit->parents;
 766         int count = 0;
 767         while (parents) {
 768                 count++;
 769                 parents = parents->next;
 770         }
 771         return count;
 772 }
 773
 774 static void move_diff_queue(struct diff_queue_struct *dst,
 775                             struct diff_queue_struct *src)
 776 {
 777         assert(src != dst);
 778         memcpy(dst, src, sizeof(struct diff_queue_struct));
 779         DIFF_QUEUE_CLEAR(src);
 780 }
 781
 782 static void filter_diffs_for_paths(struct line_log_data *range, int keep_deletions)
 783 {
 784         int i;
 785         struct diff_queue_struct outq;
 786         DIFF_QUEUE_CLEAR(&outq);
 787
 788         for (i = 0; i < diff_queued_diff.nr; i++) {
 789                 struct diff_filepair *p = diff_queued_diff.queue[i];
 790                 struct line_log_data *rg = NULL;
 791
 792                 if (!DIFF_FILE_VALID(p->two)) {
 793                         if (keep_deletions)
 794                                 diff_q(&outq, p);
 795                         else
 796                                 diff_free_filepair(p);
 797                         continue;
 798                 }
 799                 for (rg = range; rg; rg = rg->next) {
 800                         if (!strcmp(rg->spec->path, p->two->path))
 801                                 break;
 802                 }
 803                 if (rg)
 804                         diff_q(&outq, p);
 805                 else
 806                         diff_free_filepair(p);
 807         }
 808         free(diff_queued_diff.queue);
 809         diff_queued_diff = outq;
 810 }
 811
 812 static inline int diff_might_be_rename(void)
 813 {
 814         int i;
 815         for (i = 0; i < diff_queued_diff.nr; i++)
 816                 if (!DIFF_FILE_VALID(diff_queued_diff.queue[i]->one)) {
 817                         /* fprintf(stderr, "diff_might_be_rename found creation of: %s\n", */
 818                         /*      diff_queued_diff.queue[i]->two->path); */
 819                         return 1;
 820                 }
 821         return 0;
 822 }
 823
 824 static void queue_diffs(struct line_log_data *range,
 825                         struct diff_options *opt,
 826                         struct diff_queue_struct *queue,
 827                         struct commit *commit, struct commit *parent)
 828 {
 829         void *tree1 = NULL, *tree2 = NULL;
 830         struct tree_desc desc1, desc2;
 831
 832         assert(commit);
 833         load_tree_desc(&desc2, &tree2, commit->tree->object.sha1);
 834         if (parent)
 835                 load_tree_desc(&desc1, &tree1, parent->tree->object.sha1);
 836         else
 837                 init_tree_desc(&desc1, "", 0);
 838
 839         DIFF_QUEUE_CLEAR(&diff_queued_diff);
 840         diff_tree(&desc1, &desc2, "", opt);
 841         if (opt->detect_rename) {
 842                 filter_diffs_for_paths(range, 1);
 843                 if (diff_might_be_rename())
 844                         diffcore_std(opt);
 845                 filter_diffs_for_paths(range, 0);
 846         }
 847         move_diff_queue(queue, &diff_queued_diff);
 848
 849         if (tree1)
 850                 free(tree1);
 851         if (tree2)
 852                 free(tree2);
 853 }
 854
 855 static char *get_nth_line(long line, unsigned long *ends, void *data)
 856 {
 857         if (line == 0)
 858                 return (char *)data;
 859         else
 860                 return (char *)data + ends[line] + 1;
 861 }
 862
 863 static void print_line(const char *prefix, char first,
 864                        long line, unsigned long *ends, void *data,
 865                        const char *color, const char *reset)
 866 {
 867         char *begin = get_nth_line(line, ends, data);
 868         char *end = get_nth_line(line+1, ends, data);
 869         int had_nl = 0;
 870
 871         if (end > begin && end[-1] == '\n') {
 872                 end--;
 873                 had_nl = 1;
 874         }
 875
 876         fputs(prefix, stdout);
 877         fputs(color, stdout);
 878         putchar(first);
 879         fwrite(begin, 1, end-begin, stdout);
 880         fputs(reset, stdout);
 881         putchar('\n');
 882         if (!had_nl)
 883                 fputs("\\ No newline at end of file\n", stdout);
 884 }
 885
 886 static char *output_prefix(struct diff_options *opt)
 887 {
 888         char *prefix = "";
 889
 890         if (opt->output_prefix) {
 891                 struct strbuf *sb = opt->output_prefix(opt, opt->output_prefix_data);
 892                 prefix = sb->buf;
 893         }
 894
 895         return prefix;
 896 }
 897
 898 static void dump_diff_hacky_one(struct rev_info *rev, struct line_log_data *range)
 899 {
 900         int i, j = 0;
 901         long p_lines, t_lines;
 902         unsigned long *p_ends = NULL, *t_ends = NULL;
 903         struct diff_filepair *pair = range->pair;
 904         struct diff_ranges *diff = &range->diff;
 905
 906         struct diff_options *opt = &rev->diffopt;
 907         char *prefix = output_prefix(opt);
 908         const char *c_reset = diff_get_color(opt->use_color, DIFF_RESET);
 909         const char *c_frag = diff_get_color(opt->use_color, DIFF_FRAGINFO);
 910         const char *c_meta = diff_get_color(opt->use_color, DIFF_METAINFO);
 911         const char *c_old = diff_get_color(opt->use_color, DIFF_FILE_OLD);
 912         const char *c_new = diff_get_color(opt->use_color, DIFF_FILE_NEW);
 913         const char *c_plain = diff_get_color(opt->use_color, DIFF_PLAIN);
 914
 915         if (!pair || !diff)
 916                 return;
 917
 918         if (pair->one->sha1_valid)
 919                 fill_line_ends(pair->one, &p_lines, &p_ends);
 920         fill_line_ends(pair->two, &t_lines, &t_ends);
 921
 922         printf("%s%sdiff --git a/%s b/%s%s\n", prefix, c_meta, pair->one->path, pair->two->path, c_reset);
 923         printf("%s%s--- %s%s%s\n", prefix, c_meta,
 924                pair->one->sha1_valid ? "a/" : "",
 925                pair->one->sha1_valid ? pair->one->path : "/dev/null",
 926                c_reset);
 927         printf("%s%s+++ b/%s%s\n", prefix, c_meta, pair->two->path, c_reset);
 928         for (i = 0; i < range->ranges.nr; i++) {
 929                 long p_start, p_end;
 930                 long t_start = range->ranges.ranges[i].start;
 931                 long t_end = range->ranges.ranges[i].end;
 932                 long t_cur = t_start;
 933                 int j_last;
 934
 935                 while (j < diff->target.nr && diff->target.ranges[j].end < t_start)
 936                         j++;
 937                 if (j == diff->target.nr || diff->target.ranges[j].start > t_end)
 938                         continue;
 939
 940                 /* Scan ahead to determine the last diff that falls in this range */
 941                 j_last = j;
 942                 while (j_last < diff->target.nr && diff->target.ranges[j_last].start < t_end)
 943                         j_last++;
 944                 if (j_last > j)
 945                         j_last--;
 946
 947                 /*
 948                  * Compute parent hunk headers: we know that the diff
 949                  * has the correct line numbers (but not all hunks).
 950                  * So it suffices to shift the start/end according to
 951                  * the line numbers of the first/last hunk(s) that
 952                  * fall in this range.
 953                  */
 954                 if (t_start < diff->target.ranges[j].start)
 955                         p_start = diff->parent.ranges[j].start - (diff->target.ranges[j].start-t_start);
 956                 else
 957                         p_start = diff->parent.ranges[j].start;
 958                 if (t_end > diff->target.ranges[j_last].end)
 959                         p_end = diff->parent.ranges[j_last].end + (t_end-diff->target.ranges[j_last].end);
 960                 else
 961                         p_end = diff->parent.ranges[j_last].end;
 962
 963                 if (!p_start && !p_end) {
 964                         p_start = -1;
 965                         p_end = -1;
 966                 }
 967
 968                 /* Now output a diff hunk for this range */
 969                 printf("%s%s@@ -%ld,%ld +%ld,%ld @@%s\n",
 970                        prefix, c_frag,
 971                        p_start+1, p_end-p_start, t_start+1, t_end-t_start,
 972                        c_reset);
 973                 while (j < diff->target.nr && diff->target.ranges[j].start < t_end) {
 974                         int k;
 975                         for (; t_cur < diff->target.ranges[j].start; t_cur++)
 976                                 print_line(prefix, ' ', t_cur, t_ends, pair->two->data,
 977                                            c_plain, c_reset);
 978                         for (k = diff->parent.ranges[j].start; k < diff->parent.ranges[j].end; k++)
 979                                 print_line(prefix, '-', k, p_ends, pair->one->data,
 980                                            c_old, c_reset);
 981                         for (; t_cur < diff->target.ranges[j].end && t_cur < t_end; t_cur++)
 982                                 print_line(prefix, '+', t_cur, t_ends, pair->two->data,
 983                                            c_new, c_reset);
 984                         j++;
 985                 }
 986                 for (; t_cur < t_end; t_cur++)
 987                         print_line(prefix, ' ', t_cur, t_ends, pair->two->data,
 988                                    c_plain, c_reset);
 989         }
 990
 991         free(p_ends);
 992         free(t_ends);
 993 }
 994
 995 /*
 996  * NEEDSWORK: manually building a diff here is not the Right
 997  * Thing(tm).  log -L should be built into the diff pipeline.
 998  */
 999 static void dump_diff_hacky(struct rev_info *rev, struct line_log_data *range)
1000 {
1001         puts(output_prefix(&rev->diffopt));
1002         while (range) {
1003                 dump_diff_hacky_one(rev, range);
1004                 range = range->next;
1005         }
1006 }
1007
1008 /*
1009  * Unlike most other functions, this destructively operates on
1010  * 'range'.
1011  */
1012 static int process_diff_filepair(struct rev_info *rev,
1013                                  struct diff_filepair *pair,
1014                                  struct line_log_data *range,
1015                                  struct diff_ranges **diff_out)
1016 {
1017         struct line_log_data *rg = range;
1018         struct range_set tmp;
1019         struct diff_ranges diff;
1020         mmfile_t file_parent, file_target;
1021
1022         assert(pair->two->path);
1023         while (rg) {
1024                 assert(rg->spec->path);
1025                 if (!strcmp(rg->spec->path, pair->two->path))
1026                         break;
1027                 rg = rg->next;
1028         }
1029
1030         if (!rg)
1031                 return 0;
1032         if (rg->ranges.nr == 0)
1033                 return 0;
1034
1035         assert(pair->two->sha1_valid);
1036         diff_populate_filespec(pair->two, 0);
1037         file_target.ptr = pair->two->data;
1038         file_target.size = pair->two->size;
1039
1040         if (pair->one->sha1_valid) {
1041                 diff_populate_filespec(pair->one, 0);
1042                 file_parent.ptr = pair->one->data;
1043                 file_parent.size = pair->one->size;
1044         } else {
1045                 file_parent.ptr = "";
1046                 file_parent.size = 0;
1047         }
1048
1049         diff_ranges_init(&diff);
1050         collect_diff(&file_parent, &file_target, &diff);
1051
1052         /* NEEDSWORK should apply some heuristics to prevent mismatches */
1053         rg->spec->path = xstrdup(pair->one->path);
1054
1055         range_set_init(&tmp, 0);
1056         range_set_map_across_diff(&tmp, &rg->ranges, &diff, diff_out);
1057         range_set_release(&rg->ranges);
1058         range_set_move(&rg->ranges, &tmp);
1059
1060         diff_ranges_release(&diff);
1061
1062         return ((*diff_out)->parent.nr > 0);
1063 }
1064
1065 static struct diff_filepair *diff_filepair_dup(struct diff_filepair *pair)
1066 {
1067         struct diff_filepair *new = xmalloc(sizeof(struct diff_filepair));
1068         new->one = pair->one;
1069         new->two = pair->two;
1070         new->one->count++;
1071         new->two->count++;
1072         return new;
1073 }
1074
1075 static void free_diffqueues(int n, struct diff_queue_struct *dq)
1076 {
1077         int i, j;
1078         for (i = 0; i < n; i++)
1079                 for (j = 0; j < dq[i].nr; j++)
1080                         diff_free_filepair(dq[i].queue[j]);
1081         free(dq);
1082 }
1083
1084 static int process_all_files(struct line_log_data **range_out,
1085                              struct rev_info *rev,
1086                              struct diff_queue_struct *queue,
1087                              struct line_log_data *range)
1088 {
1089         int i, changed = 0;
1090
1091         *range_out = line_log_data_copy(range);
1092
1093         for (i = 0; i < queue->nr; i++) {
1094                 struct diff_ranges *pairdiff = NULL;
1095                 if (process_diff_filepair(rev, queue->queue[i], *range_out, &pairdiff)) {
1096                         struct line_log_data *rg = range;
1097                         changed++;
1098                         /* NEEDSWORK tramples over data structures not owned here */
1099                         while (rg && strcmp(rg->spec->path, queue->queue[i]->two->path))
1100                                 rg = rg->next;
1101                         assert(rg);
1102                         rg->pair = diff_filepair_dup(queue->queue[i]);
1103                         memcpy(&rg->diff, pairdiff, sizeof(struct diff_ranges));
1104                 }
1105         }
1106
1107         return changed;
1108 }
1109
1110 int line_log_print(struct rev_info *rev, struct commit *commit)
1111 {
1112         struct line_log_data *range = lookup_line_range(rev, commit);
1113
1114         show_log(rev);
1115         dump_diff_hacky(rev, range);
1116         return 1;
1117 }
1118
1119 static int process_ranges_ordinary_commit(struct rev_info *rev, struct commit *commit,
1120                                           struct line_log_data *range)
1121 {
1122         struct commit *parent = NULL;
1123         struct diff_queue_struct queue;
1124         struct line_log_data *parent_range;
1125         int changed;
1126
1127         if (commit->parents)
1128                 parent = commit->parents->item;
1129
1130         queue_diffs(range, &rev->diffopt, &queue, commit, parent);
1131         changed = process_all_files(&parent_range, rev, &queue, range);
1132         if (parent)
1133                 add_line_range(rev, parent, parent_range);
1134         return changed;
1135 }
1136
1137 static int process_ranges_merge_commit(struct rev_info *rev, struct commit *commit,
1138                                        struct line_log_data *range)
1139 {
1140         struct diff_queue_struct *diffqueues;
1141         struct line_log_data **cand;
1142         struct commit **parents;
1143         struct commit_list *p;
1144         int i;
1145         int nparents = count_parents(commit);
1146
1147         diffqueues = xmalloc(nparents * sizeof(*diffqueues));
1148         cand = xmalloc(nparents * sizeof(*cand));
1149         parents = xmalloc(nparents * sizeof(*parents));
1150
1151         p = commit->parents;
1152         for (i = 0; i < nparents; i++) {
1153                 parents[i] = p->item;
1154                 p = p->next;
1155                 queue_diffs(range, &rev->diffopt, &diffqueues[i], commit, parents[i]);
1156         }
1157
1158         for (i = 0; i < nparents; i++) {
1159                 int changed;
1160                 cand[i] = NULL;
1161                 changed = process_all_files(&cand[i], rev, &diffqueues[i], range);
1162                 if (!changed) {
1163                         /*
1164                          * This parent can take all the blame, so we
1165                          * don't follow any other path in history
1166                          */
1167                         add_line_range(rev, parents[i], cand[i]);
1168                         clear_commit_line_range(rev, commit);
1169                         commit->parents = xmalloc(sizeof(struct commit_list));
1170                         commit->parents->item = parents[i];
1171                         commit->parents->next = NULL;
1172                         free(parents);
1173                         free(cand);
1174                         free_diffqueues(nparents, diffqueues);
1175                         /* NEEDSWORK leaking like a sieve */
1176                         return 0;
1177                 }
1178         }
1179
1180         /*
1181          * No single parent took the blame.  We add the candidates
1182          * from the above loop to the parents.
1183          */
1184         for (i = 0; i < nparents; i++) {
1185                 add_line_range(rev, parents[i], cand[i]);
1186         }
1187
1188         clear_commit_line_range(rev, commit);
1189         free(parents);
1190         free(cand);
1191         free_diffqueues(nparents, diffqueues);
1192         return 1;
1193
1194         /* NEEDSWORK evil merge detection stuff */
1195         /* NEEDSWORK leaking like a sieve */
1196 }
1197
1198 static int process_ranges_arbitrary_commit(struct rev_info *rev, struct commit *commit)
1199 {
1200         struct line_log_data *range = lookup_line_range(rev, commit);
1201         int changed = 0;
1202
1203         if (range) {
1204                 if (!commit->parents || !commit->parents->next)
1205                         changed = process_ranges_ordinary_commit(rev, commit, range);
1206                 else
1207                         changed = process_ranges_merge_commit(rev, commit, range);
1208         }
1209
1210         if (!changed)
1211                 commit->object.flags |= TREESAME;
1212
1213         return changed;
1214 }
1215
1216 static enum rewrite_result line_log_rewrite_one(struct rev_info *rev, struct commit **pp)
1217 {
1218         for (;;) {
1219                 struct commit *p = *pp;
1220                 if (p->parents && p->parents->next)
1221                         return rewrite_one_ok;
1222                 if (p->object.flags & UNINTERESTING)
1223                         return rewrite_one_ok;
1224                 if (!(p->object.flags & TREESAME))
1225                         return rewrite_one_ok;
1226                 if (!p->parents)
1227                         return rewrite_one_noparents;
1228                 *pp = p->parents->item;
1229         }
1230 }
1231
1232 int line_log_filter(struct rev_info *rev)
1233 {
1234         struct commit *commit;
1235         struct commit_list *list = rev->commits;
1236         struct commit_list *out = NULL, **pp = &out;
1237
1238         while (list) {
1239                 struct commit_list *to_free = NULL;
1240                 commit = list->item;
1241                 if (process_ranges_arbitrary_commit(rev, commit)) {
1242                         *pp = list;
1243                         pp = &list->next;
1244                 } else
1245                         to_free = list;
1246                 list = list->next;
1247                 free(to_free);
1248         }
1249         *pp = NULL;
1250
1251         for (list = out; list; list = list->next)
1252                 rewrite_parents(rev, list->item, line_log_rewrite_one);
1253
1254         rev->commits = out;
1255
1256         return 0;
1257 }