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