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