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