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