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 filter_diffs_for_paths(struct line_log_data *range, int keep_deletions)
 754 {
 755         int i;
 756         struct diff_queue_struct outq;
 757         DIFF_QUEUE_CLEAR(&outq);
 758
 759         for (i = 0; i < diff_queued_diff.nr; i++) {
 760                 struct diff_filepair *p = diff_queued_diff.queue[i];
 761                 struct line_log_data *rg = NULL;
 762
 763                 if (!DIFF_FILE_VALID(p->two)) {
 764                         if (keep_deletions)
 765                                 diff_q(&outq, p);
 766                         else
 767                                 diff_free_filepair(p);
 768                         continue;
 769                 }
 770                 for (rg = range; rg; rg = rg->next) {
 771                         if (!strcmp(rg->spec->path, p->two->path))
 772                                 break;
 773                 }
 774                 if (rg)
 775                         diff_q(&outq, p);
 776                 else
 777                         diff_free_filepair(p);
 778         }
 779         free(diff_queued_diff.queue);
 780         diff_queued_diff = outq;
 781 }
 782
 783 static inline int diff_might_be_rename(void)
 784 {
 785         int i;
 786         for (i = 0; i < diff_queued_diff.nr; i++)
 787                 if (!DIFF_FILE_VALID(diff_queued_diff.queue[i]->one)) {
 788                         /* fprintf(stderr, "diff_might_be_rename found creation of: %s\n", */
 789                         /*      diff_queued_diff.queue[i]->two->path); */
 790                         return 1;
 791                 }
 792         return 0;
 793 }
 794
 795 static void queue_diffs(struct line_log_data *range,
 796                         struct diff_options *opt,
 797                         struct diff_queue_struct *queue,
 798                         struct commit *commit, struct commit *parent)
 799 {
 800         void *tree1 = NULL, *tree2 = NULL;
 801         struct tree_desc desc1, desc2;
 802
 803         assert(commit);
 804         load_tree_desc(&desc2, &tree2, commit->tree->object.sha1);
 805         if (parent)
 806                 load_tree_desc(&desc1, &tree1, parent->tree->object.sha1);
 807         else
 808                 init_tree_desc(&desc1, "", 0);
 809
 810         DIFF_QUEUE_CLEAR(&diff_queued_diff);
 811         diff_tree(&desc1, &desc2, "", opt);
 812         if (opt->detect_rename) {
 813                 filter_diffs_for_paths(range, 1);
 814                 if (diff_might_be_rename())
 815                         diffcore_std(opt);
 816                 filter_diffs_for_paths(range, 0);
 817         }
 818         move_diff_queue(queue, &diff_queued_diff);
 819
 820         if (tree1)
 821                 free(tree1);
 822         if (tree2)
 823                 free(tree2);
 824 }
 825
 826 static char *get_nth_line(long line, unsigned long *ends, void *data)
 827 {
 828         if (line == 0)
 829                 return (char *)data;
 830         else
 831                 return (char *)data + ends[line] + 1;
 832 }
 833
 834 static void print_line(const char *prefix, char first,
 835                        long line, unsigned long *ends, void *data,
 836                        const char *color, const char *reset)
 837 {
 838         char *begin = get_nth_line(line, ends, data);
 839         char *end = get_nth_line(line+1, ends, data);
 840         int had_nl = 0;
 841
 842         if (end > begin && end[-1] == '\n') {
 843                 end--;
 844                 had_nl = 1;
 845         }
 846
 847         fputs(prefix, stdout);
 848         fputs(color, stdout);
 849         putchar(first);
 850         fwrite(begin, 1, end-begin, stdout);
 851         fputs(reset, stdout);
 852         putchar('\n');
 853         if (!had_nl)
 854                 fputs("\\ No newline at end of file\n", stdout);
 855 }
 856
 857 static char *output_prefix(struct diff_options *opt)
 858 {
 859         char *prefix = "";
 860
 861         if (opt->output_prefix) {
 862                 struct strbuf *sb = opt->output_prefix(opt, opt->output_prefix_data);
 863                 prefix = sb->buf;
 864         }
 865
 866         return prefix;
 867 }
 868
 869 static void dump_diff_hacky_one(struct rev_info *rev, struct line_log_data *range)
 870 {
 871         int i, j = 0;
 872         long p_lines, t_lines;
 873         unsigned long *p_ends = NULL, *t_ends = NULL;
 874         struct diff_filepair *pair = range->pair;
 875         struct diff_ranges *diff = &range->diff;
 876
 877         struct diff_options *opt = &rev->diffopt;
 878         char *prefix = output_prefix(opt);
 879         const char *c_reset = diff_get_color(opt->use_color, DIFF_RESET);
 880         const char *c_frag = diff_get_color(opt->use_color, DIFF_FRAGINFO);
 881         const char *c_meta = diff_get_color(opt->use_color, DIFF_METAINFO);
 882         const char *c_old = diff_get_color(opt->use_color, DIFF_FILE_OLD);
 883         const char *c_new = diff_get_color(opt->use_color, DIFF_FILE_NEW);
 884         const char *c_plain = diff_get_color(opt->use_color, DIFF_PLAIN);
 885
 886         if (!pair || !diff)
 887                 return;
 888
 889         if (pair->one->sha1_valid)
 890                 fill_line_ends(pair->one, &p_lines, &p_ends);
 891         fill_line_ends(pair->two, &t_lines, &t_ends);
 892
 893         printf("%s%sdiff --git a/%s b/%s%s\n", prefix, c_meta, pair->one->path, pair->two->path, c_reset);
 894         printf("%s%s--- %s%s%s\n", prefix, c_meta,
 895                pair->one->sha1_valid ? "a/" : "",
 896                pair->one->sha1_valid ? pair->one->path : "/dev/null",
 897                c_reset);
 898         printf("%s%s+++ b/%s%s\n", prefix, c_meta, pair->two->path, c_reset);
 899         for (i = 0; i < range->ranges.nr; i++) {
 900                 long p_start, p_end;
 901                 long t_start = range->ranges.ranges[i].start;
 902                 long t_end = range->ranges.ranges[i].end;
 903                 long t_cur = t_start;
 904                 int j_last;
 905
 906                 while (j < diff->target.nr && diff->target.ranges[j].end < t_start)
 907                         j++;
 908                 if (j == diff->target.nr || diff->target.ranges[j].start > t_end)
 909                         continue;
 910
 911                 /* Scan ahead to determine the last diff that falls in this range */
 912                 j_last = j;
 913                 while (j_last < diff->target.nr && diff->target.ranges[j_last].start < t_end)
 914                         j_last++;
 915                 if (j_last > j)
 916                         j_last--;
 917
 918                 /*
 919                  * Compute parent hunk headers: we know that the diff
 920                  * has the correct line numbers (but not all hunks).
 921                  * So it suffices to shift the start/end according to
 922                  * the line numbers of the first/last hunk(s) that
 923                  * fall in this range.
 924                  */
 925                 if (t_start < diff->target.ranges[j].start)
 926                         p_start = diff->parent.ranges[j].start - (diff->target.ranges[j].start-t_start);
 927                 else
 928                         p_start = diff->parent.ranges[j].start;
 929                 if (t_end > diff->target.ranges[j_last].end)
 930                         p_end = diff->parent.ranges[j_last].end + (t_end-diff->target.ranges[j_last].end);
 931                 else
 932                         p_end = diff->parent.ranges[j_last].end;
 933
 934                 if (!p_start && !p_end) {
 935                         p_start = -1;
 936                         p_end = -1;
 937                 }
 938
 939                 /* Now output a diff hunk for this range */
 940                 printf("%s%s@@ -%ld,%ld +%ld,%ld @@%s\n",
 941                        prefix, c_frag,
 942                        p_start+1, p_end-p_start, t_start+1, t_end-t_start,
 943                        c_reset);
 944                 while (j < diff->target.nr && diff->target.ranges[j].start < t_end) {
 945                         int k;
 946                         for (; t_cur < diff->target.ranges[j].start; t_cur++)
 947                                 print_line(prefix, ' ', t_cur, t_ends, pair->two->data,
 948                                            c_plain, c_reset);
 949                         for (k = diff->parent.ranges[j].start; k < diff->parent.ranges[j].end; k++)
 950                                 print_line(prefix, '-', k, p_ends, pair->one->data,
 951                                            c_old, c_reset);
 952                         for (; t_cur < diff->target.ranges[j].end && t_cur < t_end; t_cur++)
 953                                 print_line(prefix, '+', t_cur, t_ends, pair->two->data,
 954                                            c_new, c_reset);
 955                         j++;
 956                 }
 957                 for (; t_cur < t_end; t_cur++)
 958                         print_line(prefix, ' ', t_cur, t_ends, pair->two->data,
 959                                    c_plain, c_reset);
 960         }
 961
 962         free(p_ends);
 963         free(t_ends);
 964 }
 965
 966 /*
 967  * NEEDSWORK: manually building a diff here is not the Right
 968  * Thing(tm).  log -L should be built into the diff pipeline.
 969  */
 970 static void dump_diff_hacky(struct rev_info *rev, struct line_log_data *range)
 971 {
 972         puts(output_prefix(&rev->diffopt));
 973         while (range) {
 974                 dump_diff_hacky_one(rev, range);
 975                 range = range->next;
 976         }
 977 }
 978
 979 /*
 980  * Unlike most other functions, this destructively operates on
 981  * 'range'.
 982  */
 983 static int process_diff_filepair(struct rev_info *rev,
 984                                  struct diff_filepair *pair,
 985                                  struct line_log_data *range,
 986                                  struct diff_ranges **diff_out)
 987 {
 988         struct line_log_data *rg = range;
 989         struct range_set tmp;
 990         struct diff_ranges diff;
 991         mmfile_t file_parent, file_target;
 992
 993         assert(pair->two->path);
 994         while (rg) {
 995                 assert(rg->spec->path);
 996                 if (!strcmp(rg->spec->path, pair->two->path))
 997                         break;
 998                 rg = rg->next;
 999         }
1000
1001         if (!rg)
1002                 return 0;
1003         if (rg->ranges.nr == 0)
1004                 return 0;
1005
1006         assert(pair->two->sha1_valid);
1007         diff_populate_filespec(pair->two, 0);
1008         file_target.ptr = pair->two->data;
1009         file_target.size = pair->two->size;
1010
1011         if (pair->one->sha1_valid) {
1012                 diff_populate_filespec(pair->one, 0);
1013                 file_parent.ptr = pair->one->data;
1014                 file_parent.size = pair->one->size;
1015         } else {
1016                 file_parent.ptr = "";
1017                 file_parent.size = 0;
1018         }
1019
1020         diff_ranges_init(&diff);
1021         collect_diff(&file_parent, &file_target, &diff);
1022
1023         /* NEEDSWORK should apply some heuristics to prevent mismatches */
1024         rg->spec->path = xstrdup(pair->one->path);
1025
1026         range_set_init(&tmp, 0);
1027         range_set_map_across_diff(&tmp, &rg->ranges, &diff, diff_out);
1028         range_set_release(&rg->ranges);
1029         range_set_move(&rg->ranges, &tmp);
1030
1031         diff_ranges_release(&diff);
1032
1033         return ((*diff_out)->parent.nr > 0);
1034 }
1035
1036 static struct diff_filepair *diff_filepair_dup(struct diff_filepair *pair)
1037 {
1038         struct diff_filepair *new = xmalloc(sizeof(struct diff_filepair));
1039         new->one = pair->one;
1040         new->two = pair->two;
1041         new->one->count++;
1042         new->two->count++;
1043         return new;
1044 }
1045
1046 static void free_diffqueues(int n, struct diff_queue_struct *dq)
1047 {
1048         int i, j;
1049         for (i = 0; i < n; i++)
1050                 for (j = 0; j < dq[i].nr; j++)
1051                         diff_free_filepair(dq[i].queue[j]);
1052         free(dq);
1053 }
1054
1055 static int process_all_files(struct line_log_data **range_out,
1056                              struct rev_info *rev,
1057                              struct diff_queue_struct *queue,
1058                              struct line_log_data *range)
1059 {
1060         int i, changed = 0;
1061
1062         *range_out = line_log_data_copy(range);
1063
1064         for (i = 0; i < queue->nr; i++) {
1065                 struct diff_ranges *pairdiff = NULL;
1066                 if (process_diff_filepair(rev, queue->queue[i], *range_out, &pairdiff)) {
1067                         struct line_log_data *rg = range;
1068                         changed++;
1069                         /* NEEDSWORK tramples over data structures not owned here */
1070                         while (rg && strcmp(rg->spec->path, queue->queue[i]->two->path))
1071                                 rg = rg->next;
1072                         assert(rg);
1073                         rg->pair = diff_filepair_dup(queue->queue[i]);
1074                         memcpy(&rg->diff, pairdiff, sizeof(struct diff_ranges));
1075                 }
1076         }
1077
1078         return changed;
1079 }
1080
1081 int line_log_print(struct rev_info *rev, struct commit *commit)
1082 {
1083         struct line_log_data *range = lookup_line_range(rev, commit);
1084
1085         show_log(rev);
1086         dump_diff_hacky(rev, range);
1087         return 1;
1088 }
1089
1090 static int process_ranges_ordinary_commit(struct rev_info *rev, struct commit *commit,
1091                                           struct line_log_data *range)
1092 {
1093         struct commit *parent = NULL;
1094         struct diff_queue_struct queue;
1095         struct line_log_data *parent_range;
1096         int changed;
1097
1098         if (commit->parents)
1099                 parent = commit->parents->item;
1100
1101         queue_diffs(range, &rev->diffopt, &queue, commit, parent);
1102         changed = process_all_files(&parent_range, rev, &queue, range);
1103         if (parent)
1104                 add_line_range(rev, parent, parent_range);
1105         return changed;
1106 }
1107
1108 static int process_ranges_merge_commit(struct rev_info *rev, struct commit *commit,
1109                                        struct line_log_data *range)
1110 {
1111         struct diff_queue_struct *diffqueues;
1112         struct line_log_data **cand;
1113         struct commit **parents;
1114         struct commit_list *p;
1115         int i;
1116         int nparents = count_parents(commit);
1117
1118         diffqueues = xmalloc(nparents * sizeof(*diffqueues));
1119         cand = xmalloc(nparents * sizeof(*cand));
1120         parents = xmalloc(nparents * sizeof(*parents));
1121
1122         p = commit->parents;
1123         for (i = 0; i < nparents; i++) {
1124                 parents[i] = p->item;
1125                 p = p->next;
1126                 queue_diffs(range, &rev->diffopt, &diffqueues[i], commit, parents[i]);
1127         }
1128
1129         for (i = 0; i < nparents; i++) {
1130                 int changed;
1131                 cand[i] = NULL;
1132                 changed = process_all_files(&cand[i], rev, &diffqueues[i], range);
1133                 if (!changed) {
1134                         /*
1135                          * This parent can take all the blame, so we
1136                          * don't follow any other path in history
1137                          */
1138                         add_line_range(rev, parents[i], cand[i]);
1139                         clear_commit_line_range(rev, commit);
1140                         commit->parents = xmalloc(sizeof(struct commit_list));
1141                         commit->parents->item = parents[i];
1142                         commit->parents->next = NULL;
1143                         free(parents);
1144                         free(cand);
1145                         free_diffqueues(nparents, diffqueues);
1146                         /* NEEDSWORK leaking like a sieve */
1147                         return 0;
1148                 }
1149         }
1150
1151         /*
1152          * No single parent took the blame.  We add the candidates
1153          * from the above loop to the parents.
1154          */
1155         for (i = 0; i < nparents; i++) {
1156                 add_line_range(rev, parents[i], cand[i]);
1157         }
1158
1159         clear_commit_line_range(rev, commit);
1160         free(parents);
1161         free(cand);
1162         free_diffqueues(nparents, diffqueues);
1163         return 1;
1164
1165         /* NEEDSWORK evil merge detection stuff */
1166         /* NEEDSWORK leaking like a sieve */
1167 }
1168
1169 static int process_ranges_arbitrary_commit(struct rev_info *rev, struct commit *commit)
1170 {
1171         struct line_log_data *range = lookup_line_range(rev, commit);
1172         int changed = 0;
1173
1174         if (range) {
1175                 if (!commit->parents || !commit->parents->next)
1176                         changed = process_ranges_ordinary_commit(rev, commit, range);
1177                 else
1178                         changed = process_ranges_merge_commit(rev, commit, range);
1179         }
1180
1181         if (!changed)
1182                 commit->object.flags |= TREESAME;
1183
1184         return changed;
1185 }
1186
1187 static enum rewrite_result line_log_rewrite_one(struct rev_info *rev, struct commit **pp)
1188 {
1189         for (;;) {
1190                 struct commit *p = *pp;
1191                 if (p->parents && p->parents->next)
1192                         return rewrite_one_ok;
1193                 if (p->object.flags & UNINTERESTING)
1194                         return rewrite_one_ok;
1195                 if (!(p->object.flags & TREESAME))
1196                         return rewrite_one_ok;
1197                 if (!p->parents)
1198                         return rewrite_one_noparents;
1199                 *pp = p->parents->item;
1200         }
1201 }
1202
1203 int line_log_filter(struct rev_info *rev)
1204 {
1205         struct commit *commit;
1206         struct commit_list *list = rev->commits;
1207         struct commit_list *out = NULL, **pp = &out;
1208
1209         while (list) {
1210                 struct commit_list *to_free = NULL;
1211                 commit = list->item;
1212                 if (process_ranges_arbitrary_commit(rev, commit)) {
1213                         *pp = list;
1214                         pp = &list->next;
1215                 } else
1216                         to_free = list;
1217                 list = list->next;
1218                 free(to_free);
1219         }
1220         *pp = NULL;
1221
1222         for (list = out; list; list = list->next)
1223                 rewrite_parents(rev, list->item, line_log_rewrite_one);
1224
1225         rev->commits = out;
1226
1227         return 0;
1228 }