builtin / blame.con commit Merge branch 'tb/doc-fetch-pack-url' into maint (e8fcf70)
   1/*
   2 * Blame
   3 *
   4 * Copyright (c) 2006, Junio C Hamano
   5 */
   6
   7#include "cache.h"
   8#include "builtin.h"
   9#include "blob.h"
  10#include "commit.h"
  11#include "tag.h"
  12#include "tree-walk.h"
  13#include "diff.h"
  14#include "diffcore.h"
  15#include "revision.h"
  16#include "quote.h"
  17#include "xdiff-interface.h"
  18#include "cache-tree.h"
  19#include "string-list.h"
  20#include "mailmap.h"
  21#include "parse-options.h"
  22#include "utf8.h"
  23#include "userdiff.h"
  24#include "line-range.h"
  25#include "line-log.h"
  26
  27static char blame_usage[] = N_("git blame [options] [rev-opts] [rev] [--] file");
  28
  29static const char *blame_opt_usage[] = {
  30        blame_usage,
  31        "",
  32        N_("[rev-opts] are documented in git-rev-list(1)"),
  33        NULL
  34};
  35
  36static int longest_file;
  37static int longest_author;
  38static int max_orig_digits;
  39static int max_digits;
  40static int max_score_digits;
  41static int show_root;
  42static int reverse;
  43static int blank_boundary;
  44static int incremental;
  45static int xdl_opts;
  46static int abbrev = -1;
  47static int no_whole_file_rename;
  48
  49static enum date_mode blame_date_mode = DATE_ISO8601;
  50static size_t blame_date_width;
  51
  52static struct string_list mailmap;
  53
  54#ifndef DEBUG
  55#define DEBUG 0
  56#endif
  57
  58/* stats */
  59static int num_read_blob;
  60static int num_get_patch;
  61static int num_commits;
  62
  63#define PICKAXE_BLAME_MOVE              01
  64#define PICKAXE_BLAME_COPY              02
  65#define PICKAXE_BLAME_COPY_HARDER       04
  66#define PICKAXE_BLAME_COPY_HARDEST      010
  67
  68/*
  69 * blame for a blame_entry with score lower than these thresholds
  70 * is not passed to the parent using move/copy logic.
  71 */
  72static unsigned blame_move_score;
  73static unsigned blame_copy_score;
  74#define BLAME_DEFAULT_MOVE_SCORE        20
  75#define BLAME_DEFAULT_COPY_SCORE        40
  76
  77/* bits #0..7 in revision.h, #8..11 used for merge_bases() in commit.c */
  78#define METAINFO_SHOWN          (1u<<12)
  79#define MORE_THAN_ONE_PATH      (1u<<13)
  80
  81/*
  82 * One blob in a commit that is being suspected
  83 */
  84struct origin {
  85        int refcnt;
  86        struct origin *previous;
  87        struct commit *commit;
  88        mmfile_t file;
  89        unsigned char blob_sha1[20];
  90        unsigned mode;
  91        char path[FLEX_ARRAY];
  92};
  93
  94static int diff_hunks(mmfile_t *file_a, mmfile_t *file_b, long ctxlen,
  95                      xdl_emit_hunk_consume_func_t hunk_func, void *cb_data)
  96{
  97        xpparam_t xpp = {0};
  98        xdemitconf_t xecfg = {0};
  99        xdemitcb_t ecb = {NULL};
 100
 101        xpp.flags = xdl_opts;
 102        xecfg.ctxlen = ctxlen;
 103        xecfg.hunk_func = hunk_func;
 104        ecb.priv = cb_data;
 105        return xdi_diff(file_a, file_b, &xpp, &xecfg, &ecb);
 106}
 107
 108/*
 109 * Prepare diff_filespec and convert it using diff textconv API
 110 * if the textconv driver exists.
 111 * Return 1 if the conversion succeeds, 0 otherwise.
 112 */
 113int textconv_object(const char *path,
 114                    unsigned mode,
 115                    const unsigned char *sha1,
 116                    int sha1_valid,
 117                    char **buf,
 118                    unsigned long *buf_size)
 119{
 120        struct diff_filespec *df;
 121        struct userdiff_driver *textconv;
 122
 123        df = alloc_filespec(path);
 124        fill_filespec(df, sha1, sha1_valid, mode);
 125        textconv = get_textconv(df);
 126        if (!textconv) {
 127                free_filespec(df);
 128                return 0;
 129        }
 130
 131        *buf_size = fill_textconv(textconv, df, buf);
 132        free_filespec(df);
 133        return 1;
 134}
 135
 136/*
 137 * Given an origin, prepare mmfile_t structure to be used by the
 138 * diff machinery
 139 */
 140static void fill_origin_blob(struct diff_options *opt,
 141                             struct origin *o, mmfile_t *file)
 142{
 143        if (!o->file.ptr) {
 144                enum object_type type;
 145                unsigned long file_size;
 146
 147                num_read_blob++;
 148                if (DIFF_OPT_TST(opt, ALLOW_TEXTCONV) &&
 149                    textconv_object(o->path, o->mode, o->blob_sha1, 1, &file->ptr, &file_size))
 150                        ;
 151                else
 152                        file->ptr = read_sha1_file(o->blob_sha1, &type, &file_size);
 153                file->size = file_size;
 154
 155                if (!file->ptr)
 156                        die("Cannot read blob %s for path %s",
 157                            sha1_to_hex(o->blob_sha1),
 158                            o->path);
 159                o->file = *file;
 160        }
 161        else
 162                *file = o->file;
 163}
 164
 165/*
 166 * Origin is refcounted and usually we keep the blob contents to be
 167 * reused.
 168 */
 169static inline struct origin *origin_incref(struct origin *o)
 170{
 171        if (o)
 172                o->refcnt++;
 173        return o;
 174}
 175
 176static void origin_decref(struct origin *o)
 177{
 178        if (o && --o->refcnt <= 0) {
 179                if (o->previous)
 180                        origin_decref(o->previous);
 181                free(o->file.ptr);
 182                free(o);
 183        }
 184}
 185
 186static void drop_origin_blob(struct origin *o)
 187{
 188        if (o->file.ptr) {
 189                free(o->file.ptr);
 190                o->file.ptr = NULL;
 191        }
 192}
 193
 194/*
 195 * Each group of lines is described by a blame_entry; it can be split
 196 * as we pass blame to the parents.  They form a linked list in the
 197 * scoreboard structure, sorted by the target line number.
 198 */
 199struct blame_entry {
 200        struct blame_entry *prev;
 201        struct blame_entry *next;
 202
 203        /* the first line of this group in the final image;
 204         * internally all line numbers are 0 based.
 205         */
 206        int lno;
 207
 208        /* how many lines this group has */
 209        int num_lines;
 210
 211        /* the commit that introduced this group into the final image */
 212        struct origin *suspect;
 213
 214        /* true if the suspect is truly guilty; false while we have not
 215         * checked if the group came from one of its parents.
 216         */
 217        char guilty;
 218
 219        /* true if the entry has been scanned for copies in the current parent
 220         */
 221        char scanned;
 222
 223        /* the line number of the first line of this group in the
 224         * suspect's file; internally all line numbers are 0 based.
 225         */
 226        int s_lno;
 227
 228        /* how significant this entry is -- cached to avoid
 229         * scanning the lines over and over.
 230         */
 231        unsigned score;
 232};
 233
 234/*
 235 * The current state of the blame assignment.
 236 */
 237struct scoreboard {
 238        /* the final commit (i.e. where we started digging from) */
 239        struct commit *final;
 240        struct rev_info *revs;
 241        const char *path;
 242
 243        /*
 244         * The contents in the final image.
 245         * Used by many functions to obtain contents of the nth line,
 246         * indexed with scoreboard.lineno[blame_entry.lno].
 247         */
 248        const char *final_buf;
 249        unsigned long final_buf_size;
 250
 251        /* linked list of blames */
 252        struct blame_entry *ent;
 253
 254        /* look-up a line in the final buffer */
 255        int num_lines;
 256        int *lineno;
 257};
 258
 259static inline int same_suspect(struct origin *a, struct origin *b)
 260{
 261        if (a == b)
 262                return 1;
 263        if (a->commit != b->commit)
 264                return 0;
 265        return !strcmp(a->path, b->path);
 266}
 267
 268static void sanity_check_refcnt(struct scoreboard *);
 269
 270/*
 271 * If two blame entries that are next to each other came from
 272 * contiguous lines in the same origin (i.e. <commit, path> pair),
 273 * merge them together.
 274 */
 275static void coalesce(struct scoreboard *sb)
 276{
 277        struct blame_entry *ent, *next;
 278
 279        for (ent = sb->ent; ent && (next = ent->next); ent = next) {
 280                if (same_suspect(ent->suspect, next->suspect) &&
 281                    ent->guilty == next->guilty &&
 282                    ent->s_lno + ent->num_lines == next->s_lno) {
 283                        ent->num_lines += next->num_lines;
 284                        ent->next = next->next;
 285                        if (ent->next)
 286                                ent->next->prev = ent;
 287                        origin_decref(next->suspect);
 288                        free(next);
 289                        ent->score = 0;
 290                        next = ent; /* again */
 291                }
 292        }
 293
 294        if (DEBUG) /* sanity */
 295                sanity_check_refcnt(sb);
 296}
 297
 298/*
 299 * Given a commit and a path in it, create a new origin structure.
 300 * The callers that add blame to the scoreboard should use
 301 * get_origin() to obtain shared, refcounted copy instead of calling
 302 * this function directly.
 303 */
 304static struct origin *make_origin(struct commit *commit, const char *path)
 305{
 306        struct origin *o;
 307        o = xcalloc(1, sizeof(*o) + strlen(path) + 1);
 308        o->commit = commit;
 309        o->refcnt = 1;
 310        strcpy(o->path, path);
 311        return o;
 312}
 313
 314/*
 315 * Locate an existing origin or create a new one.
 316 */
 317static struct origin *get_origin(struct scoreboard *sb,
 318                                 struct commit *commit,
 319                                 const char *path)
 320{
 321        struct blame_entry *e;
 322
 323        for (e = sb->ent; e; e = e->next) {
 324                if (e->suspect->commit == commit &&
 325                    !strcmp(e->suspect->path, path))
 326                        return origin_incref(e->suspect);
 327        }
 328        return make_origin(commit, path);
 329}
 330
 331/*
 332 * Fill the blob_sha1 field of an origin if it hasn't, so that later
 333 * call to fill_origin_blob() can use it to locate the data.  blob_sha1
 334 * for an origin is also used to pass the blame for the entire file to
 335 * the parent to detect the case where a child's blob is identical to
 336 * that of its parent's.
 337 *
 338 * This also fills origin->mode for corresponding tree path.
 339 */
 340static int fill_blob_sha1_and_mode(struct origin *origin)
 341{
 342        if (!is_null_sha1(origin->blob_sha1))
 343                return 0;
 344        if (get_tree_entry(origin->commit->object.sha1,
 345                           origin->path,
 346                           origin->blob_sha1, &origin->mode))
 347                goto error_out;
 348        if (sha1_object_info(origin->blob_sha1, NULL) != OBJ_BLOB)
 349                goto error_out;
 350        return 0;
 351 error_out:
 352        hashclr(origin->blob_sha1);
 353        origin->mode = S_IFINVALID;
 354        return -1;
 355}
 356
 357/*
 358 * We have an origin -- check if the same path exists in the
 359 * parent and return an origin structure to represent it.
 360 */
 361static struct origin *find_origin(struct scoreboard *sb,
 362                                  struct commit *parent,
 363                                  struct origin *origin)
 364{
 365        struct origin *porigin = NULL;
 366        struct diff_options diff_opts;
 367        const char *paths[2];
 368
 369        if (parent->util) {
 370                /*
 371                 * Each commit object can cache one origin in that
 372                 * commit.  This is a freestanding copy of origin and
 373                 * not refcounted.
 374                 */
 375                struct origin *cached = parent->util;
 376                if (!strcmp(cached->path, origin->path)) {
 377                        /*
 378                         * The same path between origin and its parent
 379                         * without renaming -- the most common case.
 380                         */
 381                        porigin = get_origin(sb, parent, cached->path);
 382
 383                        /*
 384                         * If the origin was newly created (i.e. get_origin
 385                         * would call make_origin if none is found in the
 386                         * scoreboard), it does not know the blob_sha1/mode,
 387                         * so copy it.  Otherwise porigin was in the
 388                         * scoreboard and already knows blob_sha1/mode.
 389                         */
 390                        if (porigin->refcnt == 1) {
 391                                hashcpy(porigin->blob_sha1, cached->blob_sha1);
 392                                porigin->mode = cached->mode;
 393                        }
 394                        return porigin;
 395                }
 396                /* otherwise it was not very useful; free it */
 397                free(parent->util);
 398                parent->util = NULL;
 399        }
 400
 401        /* See if the origin->path is different between parent
 402         * and origin first.  Most of the time they are the
 403         * same and diff-tree is fairly efficient about this.
 404         */
 405        diff_setup(&diff_opts);
 406        DIFF_OPT_SET(&diff_opts, RECURSIVE);
 407        diff_opts.detect_rename = 0;
 408        diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 409        paths[0] = origin->path;
 410        paths[1] = NULL;
 411
 412        parse_pathspec(&diff_opts.pathspec,
 413                       PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL,
 414                       PATHSPEC_LITERAL_PATH, "", paths);
 415        diff_setup_done(&diff_opts);
 416
 417        if (is_null_sha1(origin->commit->object.sha1))
 418                do_diff_cache(parent->tree->object.sha1, &diff_opts);
 419        else
 420                diff_tree_sha1(parent->tree->object.sha1,
 421                               origin->commit->tree->object.sha1,
 422                               "", &diff_opts);
 423        diffcore_std(&diff_opts);
 424
 425        if (!diff_queued_diff.nr) {
 426                /* The path is the same as parent */
 427                porigin = get_origin(sb, parent, origin->path);
 428                hashcpy(porigin->blob_sha1, origin->blob_sha1);
 429                porigin->mode = origin->mode;
 430        } else {
 431                /*
 432                 * Since origin->path is a pathspec, if the parent
 433                 * commit had it as a directory, we will see a whole
 434                 * bunch of deletion of files in the directory that we
 435                 * do not care about.
 436                 */
 437                int i;
 438                struct diff_filepair *p = NULL;
 439                for (i = 0; i < diff_queued_diff.nr; i++) {
 440                        const char *name;
 441                        p = diff_queued_diff.queue[i];
 442                        name = p->one->path ? p->one->path : p->two->path;
 443                        if (!strcmp(name, origin->path))
 444                                break;
 445                }
 446                if (!p)
 447                        die("internal error in blame::find_origin");
 448                switch (p->status) {
 449                default:
 450                        die("internal error in blame::find_origin (%c)",
 451                            p->status);
 452                case 'M':
 453                        porigin = get_origin(sb, parent, origin->path);
 454                        hashcpy(porigin->blob_sha1, p->one->sha1);
 455                        porigin->mode = p->one->mode;
 456                        break;
 457                case 'A':
 458                case 'T':
 459                        /* Did not exist in parent, or type changed */
 460                        break;
 461                }
 462        }
 463        diff_flush(&diff_opts);
 464        free_pathspec(&diff_opts.pathspec);
 465        if (porigin) {
 466                /*
 467                 * Create a freestanding copy that is not part of
 468                 * the refcounted origin found in the scoreboard, and
 469                 * cache it in the commit.
 470                 */
 471                struct origin *cached;
 472
 473                cached = make_origin(porigin->commit, porigin->path);
 474                hashcpy(cached->blob_sha1, porigin->blob_sha1);
 475                cached->mode = porigin->mode;
 476                parent->util = cached;
 477        }
 478        return porigin;
 479}
 480
 481/*
 482 * We have an origin -- find the path that corresponds to it in its
 483 * parent and return an origin structure to represent it.
 484 */
 485static struct origin *find_rename(struct scoreboard *sb,
 486                                  struct commit *parent,
 487                                  struct origin *origin)
 488{
 489        struct origin *porigin = NULL;
 490        struct diff_options diff_opts;
 491        int i;
 492
 493        diff_setup(&diff_opts);
 494        DIFF_OPT_SET(&diff_opts, RECURSIVE);
 495        diff_opts.detect_rename = DIFF_DETECT_RENAME;
 496        diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 497        diff_opts.single_follow = origin->path;
 498        diff_setup_done(&diff_opts);
 499
 500        if (is_null_sha1(origin->commit->object.sha1))
 501                do_diff_cache(parent->tree->object.sha1, &diff_opts);
 502        else
 503                diff_tree_sha1(parent->tree->object.sha1,
 504                               origin->commit->tree->object.sha1,
 505                               "", &diff_opts);
 506        diffcore_std(&diff_opts);
 507
 508        for (i = 0; i < diff_queued_diff.nr; i++) {
 509                struct diff_filepair *p = diff_queued_diff.queue[i];
 510                if ((p->status == 'R' || p->status == 'C') &&
 511                    !strcmp(p->two->path, origin->path)) {
 512                        porigin = get_origin(sb, parent, p->one->path);
 513                        hashcpy(porigin->blob_sha1, p->one->sha1);
 514                        porigin->mode = p->one->mode;
 515                        break;
 516                }
 517        }
 518        diff_flush(&diff_opts);
 519        free_pathspec(&diff_opts.pathspec);
 520        return porigin;
 521}
 522
 523/*
 524 * Link in a new blame entry to the scoreboard.  Entries that cover the
 525 * same line range have been removed from the scoreboard previously.
 526 */
 527static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)
 528{
 529        struct blame_entry *ent, *prev = NULL;
 530
 531        origin_incref(e->suspect);
 532
 533        for (ent = sb->ent; ent && ent->lno < e->lno; ent = ent->next)
 534                prev = ent;
 535
 536        /* prev, if not NULL, is the last one that is below e */
 537        e->prev = prev;
 538        if (prev) {
 539                e->next = prev->next;
 540                prev->next = e;
 541        }
 542        else {
 543                e->next = sb->ent;
 544                sb->ent = e;
 545        }
 546        if (e->next)
 547                e->next->prev = e;
 548}
 549
 550/*
 551 * src typically is on-stack; we want to copy the information in it to
 552 * a malloced blame_entry that is already on the linked list of the
 553 * scoreboard.  The origin of dst loses a refcnt while the origin of src
 554 * gains one.
 555 */
 556static void dup_entry(struct blame_entry *dst, struct blame_entry *src)
 557{
 558        struct blame_entry *p, *n;
 559
 560        p = dst->prev;
 561        n = dst->next;
 562        origin_incref(src->suspect);
 563        origin_decref(dst->suspect);
 564        memcpy(dst, src, sizeof(*src));
 565        dst->prev = p;
 566        dst->next = n;
 567        dst->score = 0;
 568}
 569
 570static const char *nth_line(struct scoreboard *sb, long lno)
 571{
 572        return sb->final_buf + sb->lineno[lno];
 573}
 574
 575static const char *nth_line_cb(void *data, long lno)
 576{
 577        return nth_line((struct scoreboard *)data, lno);
 578}
 579
 580/*
 581 * It is known that lines between tlno to same came from parent, and e
 582 * has an overlap with that range.  it also is known that parent's
 583 * line plno corresponds to e's line tlno.
 584 *
 585 *                <---- e ----->
 586 *                   <------>
 587 *                   <------------>
 588 *             <------------>
 589 *             <------------------>
 590 *
 591 * Split e into potentially three parts; before this chunk, the chunk
 592 * to be blamed for the parent, and after that portion.
 593 */
 594static void split_overlap(struct blame_entry *split,
 595                          struct blame_entry *e,
 596                          int tlno, int plno, int same,
 597                          struct origin *parent)
 598{
 599        int chunk_end_lno;
 600        memset(split, 0, sizeof(struct blame_entry [3]));
 601
 602        if (e->s_lno < tlno) {
 603                /* there is a pre-chunk part not blamed on parent */
 604                split[0].suspect = origin_incref(e->suspect);
 605                split[0].lno = e->lno;
 606                split[0].s_lno = e->s_lno;
 607                split[0].num_lines = tlno - e->s_lno;
 608                split[1].lno = e->lno + tlno - e->s_lno;
 609                split[1].s_lno = plno;
 610        }
 611        else {
 612                split[1].lno = e->lno;
 613                split[1].s_lno = plno + (e->s_lno - tlno);
 614        }
 615
 616        if (same < e->s_lno + e->num_lines) {
 617                /* there is a post-chunk part not blamed on parent */
 618                split[2].suspect = origin_incref(e->suspect);
 619                split[2].lno = e->lno + (same - e->s_lno);
 620                split[2].s_lno = e->s_lno + (same - e->s_lno);
 621                split[2].num_lines = e->s_lno + e->num_lines - same;
 622                chunk_end_lno = split[2].lno;
 623        }
 624        else
 625                chunk_end_lno = e->lno + e->num_lines;
 626        split[1].num_lines = chunk_end_lno - split[1].lno;
 627
 628        /*
 629         * if it turns out there is nothing to blame the parent for,
 630         * forget about the splitting.  !split[1].suspect signals this.
 631         */
 632        if (split[1].num_lines < 1)
 633                return;
 634        split[1].suspect = origin_incref(parent);
 635}
 636
 637/*
 638 * split_overlap() divided an existing blame e into up to three parts
 639 * in split.  Adjust the linked list of blames in the scoreboard to
 640 * reflect the split.
 641 */
 642static void split_blame(struct scoreboard *sb,
 643                        struct blame_entry *split,
 644                        struct blame_entry *e)
 645{
 646        struct blame_entry *new_entry;
 647
 648        if (split[0].suspect && split[2].suspect) {
 649                /* The first part (reuse storage for the existing entry e) */
 650                dup_entry(e, &split[0]);
 651
 652                /* The last part -- me */
 653                new_entry = xmalloc(sizeof(*new_entry));
 654                memcpy(new_entry, &(split[2]), sizeof(struct blame_entry));
 655                add_blame_entry(sb, new_entry);
 656
 657                /* ... and the middle part -- parent */
 658                new_entry = xmalloc(sizeof(*new_entry));
 659                memcpy(new_entry, &(split[1]), sizeof(struct blame_entry));
 660                add_blame_entry(sb, new_entry);
 661        }
 662        else if (!split[0].suspect && !split[2].suspect)
 663                /*
 664                 * The parent covers the entire area; reuse storage for
 665                 * e and replace it with the parent.
 666                 */
 667                dup_entry(e, &split[1]);
 668        else if (split[0].suspect) {
 669                /* me and then parent */
 670                dup_entry(e, &split[0]);
 671
 672                new_entry = xmalloc(sizeof(*new_entry));
 673                memcpy(new_entry, &(split[1]), sizeof(struct blame_entry));
 674                add_blame_entry(sb, new_entry);
 675        }
 676        else {
 677                /* parent and then me */
 678                dup_entry(e, &split[1]);
 679
 680                new_entry = xmalloc(sizeof(*new_entry));
 681                memcpy(new_entry, &(split[2]), sizeof(struct blame_entry));
 682                add_blame_entry(sb, new_entry);
 683        }
 684
 685        if (DEBUG) { /* sanity */
 686                struct blame_entry *ent;
 687                int lno = sb->ent->lno, corrupt = 0;
 688
 689                for (ent = sb->ent; ent; ent = ent->next) {
 690                        if (lno != ent->lno)
 691                                corrupt = 1;
 692                        if (ent->s_lno < 0)
 693                                corrupt = 1;
 694                        lno += ent->num_lines;
 695                }
 696                if (corrupt) {
 697                        lno = sb->ent->lno;
 698                        for (ent = sb->ent; ent; ent = ent->next) {
 699                                printf("L %8d l %8d n %8d\n",
 700                                       lno, ent->lno, ent->num_lines);
 701                                lno = ent->lno + ent->num_lines;
 702                        }
 703                        die("oops");
 704                }
 705        }
 706}
 707
 708/*
 709 * After splitting the blame, the origins used by the
 710 * on-stack blame_entry should lose one refcnt each.
 711 */
 712static void decref_split(struct blame_entry *split)
 713{
 714        int i;
 715
 716        for (i = 0; i < 3; i++)
 717                origin_decref(split[i].suspect);
 718}
 719
 720/*
 721 * Helper for blame_chunk().  blame_entry e is known to overlap with
 722 * the patch hunk; split it and pass blame to the parent.
 723 */
 724static void blame_overlap(struct scoreboard *sb, struct blame_entry *e,
 725                          int tlno, int plno, int same,
 726                          struct origin *parent)
 727{
 728        struct blame_entry split[3];
 729
 730        split_overlap(split, e, tlno, plno, same, parent);
 731        if (split[1].suspect)
 732                split_blame(sb, split, e);
 733        decref_split(split);
 734}
 735
 736/*
 737 * Find the line number of the last line the target is suspected for.
 738 */
 739static int find_last_in_target(struct scoreboard *sb, struct origin *target)
 740{
 741        struct blame_entry *e;
 742        int last_in_target = -1;
 743
 744        for (e = sb->ent; e; e = e->next) {
 745                if (e->guilty || !same_suspect(e->suspect, target))
 746                        continue;
 747                if (last_in_target < e->s_lno + e->num_lines)
 748                        last_in_target = e->s_lno + e->num_lines;
 749        }
 750        return last_in_target;
 751}
 752
 753/*
 754 * Process one hunk from the patch between the current suspect for
 755 * blame_entry e and its parent.  Find and split the overlap, and
 756 * pass blame to the overlapping part to the parent.
 757 */
 758static void blame_chunk(struct scoreboard *sb,
 759                        int tlno, int plno, int same,
 760                        struct origin *target, struct origin *parent)
 761{
 762        struct blame_entry *e;
 763
 764        for (e = sb->ent; e; e = e->next) {
 765                if (e->guilty || !same_suspect(e->suspect, target))
 766                        continue;
 767                if (same <= e->s_lno)
 768                        continue;
 769                if (tlno < e->s_lno + e->num_lines)
 770                        blame_overlap(sb, e, tlno, plno, same, parent);
 771        }
 772}
 773
 774struct blame_chunk_cb_data {
 775        struct scoreboard *sb;
 776        struct origin *target;
 777        struct origin *parent;
 778        long plno;
 779        long tlno;
 780};
 781
 782static int blame_chunk_cb(long start_a, long count_a,
 783                          long start_b, long count_b, void *data)
 784{
 785        struct blame_chunk_cb_data *d = data;
 786        blame_chunk(d->sb, d->tlno, d->plno, start_b, d->target, d->parent);
 787        d->plno = start_a + count_a;
 788        d->tlno = start_b + count_b;
 789        return 0;
 790}
 791
 792/*
 793 * We are looking at the origin 'target' and aiming to pass blame
 794 * for the lines it is suspected to its parent.  Run diff to find
 795 * which lines came from parent and pass blame for them.
 796 */
 797static int pass_blame_to_parent(struct scoreboard *sb,
 798                                struct origin *target,
 799                                struct origin *parent)
 800{
 801        int last_in_target;
 802        mmfile_t file_p, file_o;
 803        struct blame_chunk_cb_data d;
 804
 805        memset(&d, 0, sizeof(d));
 806        d.sb = sb; d.target = target; d.parent = parent;
 807        last_in_target = find_last_in_target(sb, target);
 808        if (last_in_target < 0)
 809                return 1; /* nothing remains for this target */
 810
 811        fill_origin_blob(&sb->revs->diffopt, parent, &file_p);
 812        fill_origin_blob(&sb->revs->diffopt, target, &file_o);
 813        num_get_patch++;
 814
 815        diff_hunks(&file_p, &file_o, 0, blame_chunk_cb, &d);
 816        /* The rest (i.e. anything after tlno) are the same as the parent */
 817        blame_chunk(sb, d.tlno, d.plno, last_in_target, target, parent);
 818
 819        return 0;
 820}
 821
 822/*
 823 * The lines in blame_entry after splitting blames many times can become
 824 * very small and trivial, and at some point it becomes pointless to
 825 * blame the parents.  E.g. "\t\t}\n\t}\n\n" appears everywhere in any
 826 * ordinary C program, and it is not worth to say it was copied from
 827 * totally unrelated file in the parent.
 828 *
 829 * Compute how trivial the lines in the blame_entry are.
 830 */
 831static unsigned ent_score(struct scoreboard *sb, struct blame_entry *e)
 832{
 833        unsigned score;
 834        const char *cp, *ep;
 835
 836        if (e->score)
 837                return e->score;
 838
 839        score = 1;
 840        cp = nth_line(sb, e->lno);
 841        ep = nth_line(sb, e->lno + e->num_lines);
 842        while (cp < ep) {
 843                unsigned ch = *((unsigned char *)cp);
 844                if (isalnum(ch))
 845                        score++;
 846                cp++;
 847        }
 848        e->score = score;
 849        return score;
 850}
 851
 852/*
 853 * best_so_far[] and this[] are both a split of an existing blame_entry
 854 * that passes blame to the parent.  Maintain best_so_far the best split
 855 * so far, by comparing this and best_so_far and copying this into
 856 * bst_so_far as needed.
 857 */
 858static void copy_split_if_better(struct scoreboard *sb,
 859                                 struct blame_entry *best_so_far,
 860                                 struct blame_entry *this)
 861{
 862        int i;
 863
 864        if (!this[1].suspect)
 865                return;
 866        if (best_so_far[1].suspect) {
 867                if (ent_score(sb, &this[1]) < ent_score(sb, &best_so_far[1]))
 868                        return;
 869        }
 870
 871        for (i = 0; i < 3; i++)
 872                origin_incref(this[i].suspect);
 873        decref_split(best_so_far);
 874        memcpy(best_so_far, this, sizeof(struct blame_entry [3]));
 875}
 876
 877/*
 878 * We are looking at a part of the final image represented by
 879 * ent (tlno and same are offset by ent->s_lno).
 880 * tlno is where we are looking at in the final image.
 881 * up to (but not including) same match preimage.
 882 * plno is where we are looking at in the preimage.
 883 *
 884 * <-------------- final image ---------------------->
 885 *       <------ent------>
 886 *         ^tlno ^same
 887 *    <---------preimage----->
 888 *         ^plno
 889 *
 890 * All line numbers are 0-based.
 891 */
 892static void handle_split(struct scoreboard *sb,
 893                         struct blame_entry *ent,
 894                         int tlno, int plno, int same,
 895                         struct origin *parent,
 896                         struct blame_entry *split)
 897{
 898        if (ent->num_lines <= tlno)
 899                return;
 900        if (tlno < same) {
 901                struct blame_entry this[3];
 902                tlno += ent->s_lno;
 903                same += ent->s_lno;
 904                split_overlap(this, ent, tlno, plno, same, parent);
 905                copy_split_if_better(sb, split, this);
 906                decref_split(this);
 907        }
 908}
 909
 910struct handle_split_cb_data {
 911        struct scoreboard *sb;
 912        struct blame_entry *ent;
 913        struct origin *parent;
 914        struct blame_entry *split;
 915        long plno;
 916        long tlno;
 917};
 918
 919static int handle_split_cb(long start_a, long count_a,
 920                           long start_b, long count_b, void *data)
 921{
 922        struct handle_split_cb_data *d = data;
 923        handle_split(d->sb, d->ent, d->tlno, d->plno, start_b, d->parent,
 924                     d->split);
 925        d->plno = start_a + count_a;
 926        d->tlno = start_b + count_b;
 927        return 0;
 928}
 929
 930/*
 931 * Find the lines from parent that are the same as ent so that
 932 * we can pass blames to it.  file_p has the blob contents for
 933 * the parent.
 934 */
 935static void find_copy_in_blob(struct scoreboard *sb,
 936                              struct blame_entry *ent,
 937                              struct origin *parent,
 938                              struct blame_entry *split,
 939                              mmfile_t *file_p)
 940{
 941        const char *cp;
 942        int cnt;
 943        mmfile_t file_o;
 944        struct handle_split_cb_data d;
 945
 946        memset(&d, 0, sizeof(d));
 947        d.sb = sb; d.ent = ent; d.parent = parent; d.split = split;
 948        /*
 949         * Prepare mmfile that contains only the lines in ent.
 950         */
 951        cp = nth_line(sb, ent->lno);
 952        file_o.ptr = (char *) cp;
 953        cnt = ent->num_lines;
 954
 955        while (cnt && cp < sb->final_buf + sb->final_buf_size) {
 956                if (*cp++ == '\n')
 957                        cnt--;
 958        }
 959        file_o.size = cp - file_o.ptr;
 960
 961        /*
 962         * file_o is a part of final image we are annotating.
 963         * file_p partially may match that image.
 964         */
 965        memset(split, 0, sizeof(struct blame_entry [3]));
 966        diff_hunks(file_p, &file_o, 1, handle_split_cb, &d);
 967        /* remainder, if any, all match the preimage */
 968        handle_split(sb, ent, d.tlno, d.plno, ent->num_lines, parent, split);
 969}
 970
 971/*
 972 * See if lines currently target is suspected for can be attributed to
 973 * parent.
 974 */
 975static int find_move_in_parent(struct scoreboard *sb,
 976                               struct origin *target,
 977                               struct origin *parent)
 978{
 979        int last_in_target, made_progress;
 980        struct blame_entry *e, split[3];
 981        mmfile_t file_p;
 982
 983        last_in_target = find_last_in_target(sb, target);
 984        if (last_in_target < 0)
 985                return 1; /* nothing remains for this target */
 986
 987        fill_origin_blob(&sb->revs->diffopt, parent, &file_p);
 988        if (!file_p.ptr)
 989                return 0;
 990
 991        made_progress = 1;
 992        while (made_progress) {
 993                made_progress = 0;
 994                for (e = sb->ent; e; e = e->next) {
 995                        if (e->guilty || !same_suspect(e->suspect, target) ||
 996                            ent_score(sb, e) < blame_move_score)
 997                                continue;
 998                        find_copy_in_blob(sb, e, parent, split, &file_p);
 999                        if (split[1].suspect &&
1000                            blame_move_score < ent_score(sb, &split[1])) {
1001                                split_blame(sb, split, e);
1002                                made_progress = 1;
1003                        }
1004                        decref_split(split);
1005                }
1006        }
1007        return 0;
1008}
1009
1010struct blame_list {
1011        struct blame_entry *ent;
1012        struct blame_entry split[3];
1013};
1014
1015/*
1016 * Count the number of entries the target is suspected for,
1017 * and prepare a list of entry and the best split.
1018 */
1019static struct blame_list *setup_blame_list(struct scoreboard *sb,
1020                                           struct origin *target,
1021                                           int min_score,
1022                                           int *num_ents_p)
1023{
1024        struct blame_entry *e;
1025        int num_ents, i;
1026        struct blame_list *blame_list = NULL;
1027
1028        for (e = sb->ent, num_ents = 0; e; e = e->next)
1029                if (!e->scanned && !e->guilty &&
1030                    same_suspect(e->suspect, target) &&
1031                    min_score < ent_score(sb, e))
1032                        num_ents++;
1033        if (num_ents) {
1034                blame_list = xcalloc(num_ents, sizeof(struct blame_list));
1035                for (e = sb->ent, i = 0; e; e = e->next)
1036                        if (!e->scanned && !e->guilty &&
1037                            same_suspect(e->suspect, target) &&
1038                            min_score < ent_score(sb, e))
1039                                blame_list[i++].ent = e;
1040        }
1041        *num_ents_p = num_ents;
1042        return blame_list;
1043}
1044
1045/*
1046 * Reset the scanned status on all entries.
1047 */
1048static void reset_scanned_flag(struct scoreboard *sb)
1049{
1050        struct blame_entry *e;
1051        for (e = sb->ent; e; e = e->next)
1052                e->scanned = 0;
1053}
1054
1055/*
1056 * For lines target is suspected for, see if we can find code movement
1057 * across file boundary from the parent commit.  porigin is the path
1058 * in the parent we already tried.
1059 */
1060static int find_copy_in_parent(struct scoreboard *sb,
1061                               struct origin *target,
1062                               struct commit *parent,
1063                               struct origin *porigin,
1064                               int opt)
1065{
1066        struct diff_options diff_opts;
1067        int i, j;
1068        int retval;
1069        struct blame_list *blame_list;
1070        int num_ents;
1071
1072        blame_list = setup_blame_list(sb, target, blame_copy_score, &num_ents);
1073        if (!blame_list)
1074                return 1; /* nothing remains for this target */
1075
1076        diff_setup(&diff_opts);
1077        DIFF_OPT_SET(&diff_opts, RECURSIVE);
1078        diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
1079
1080        diff_setup_done(&diff_opts);
1081
1082        /* Try "find copies harder" on new path if requested;
1083         * we do not want to use diffcore_rename() actually to
1084         * match things up; find_copies_harder is set only to
1085         * force diff_tree_sha1() to feed all filepairs to diff_queue,
1086         * and this code needs to be after diff_setup_done(), which
1087         * usually makes find-copies-harder imply copy detection.
1088         */
1089        if ((opt & PICKAXE_BLAME_COPY_HARDEST)
1090            || ((opt & PICKAXE_BLAME_COPY_HARDER)
1091                && (!porigin || strcmp(target->path, porigin->path))))
1092                DIFF_OPT_SET(&diff_opts, FIND_COPIES_HARDER);
1093
1094        if (is_null_sha1(target->commit->object.sha1))
1095                do_diff_cache(parent->tree->object.sha1, &diff_opts);
1096        else
1097                diff_tree_sha1(parent->tree->object.sha1,
1098                               target->commit->tree->object.sha1,
1099                               "", &diff_opts);
1100
1101        if (!DIFF_OPT_TST(&diff_opts, FIND_COPIES_HARDER))
1102                diffcore_std(&diff_opts);
1103
1104        retval = 0;
1105        while (1) {
1106                int made_progress = 0;
1107
1108                for (i = 0; i < diff_queued_diff.nr; i++) {
1109                        struct diff_filepair *p = diff_queued_diff.queue[i];
1110                        struct origin *norigin;
1111                        mmfile_t file_p;
1112                        struct blame_entry this[3];
1113
1114                        if (!DIFF_FILE_VALID(p->one))
1115                                continue; /* does not exist in parent */
1116                        if (S_ISGITLINK(p->one->mode))
1117                                continue; /* ignore git links */
1118                        if (porigin && !strcmp(p->one->path, porigin->path))
1119                                /* find_move already dealt with this path */
1120                                continue;
1121
1122                        norigin = get_origin(sb, parent, p->one->path);
1123                        hashcpy(norigin->blob_sha1, p->one->sha1);
1124                        norigin->mode = p->one->mode;
1125                        fill_origin_blob(&sb->revs->diffopt, norigin, &file_p);
1126                        if (!file_p.ptr)
1127                                continue;
1128
1129                        for (j = 0; j < num_ents; j++) {
1130                                find_copy_in_blob(sb, blame_list[j].ent,
1131                                                  norigin, this, &file_p);
1132                                copy_split_if_better(sb, blame_list[j].split,
1133                                                     this);
1134                                decref_split(this);
1135                        }
1136                        origin_decref(norigin);
1137                }
1138
1139                for (j = 0; j < num_ents; j++) {
1140                        struct blame_entry *split = blame_list[j].split;
1141                        if (split[1].suspect &&
1142                            blame_copy_score < ent_score(sb, &split[1])) {
1143                                split_blame(sb, split, blame_list[j].ent);
1144                                made_progress = 1;
1145                        }
1146                        else
1147                                blame_list[j].ent->scanned = 1;
1148                        decref_split(split);
1149                }
1150                free(blame_list);
1151
1152                if (!made_progress)
1153                        break;
1154                blame_list = setup_blame_list(sb, target, blame_copy_score, &num_ents);
1155                if (!blame_list) {
1156                        retval = 1;
1157                        break;
1158                }
1159        }
1160        reset_scanned_flag(sb);
1161        diff_flush(&diff_opts);
1162        free_pathspec(&diff_opts.pathspec);
1163        return retval;
1164}
1165
1166/*
1167 * The blobs of origin and porigin exactly match, so everything
1168 * origin is suspected for can be blamed on the parent.
1169 */
1170static void pass_whole_blame(struct scoreboard *sb,
1171                             struct origin *origin, struct origin *porigin)
1172{
1173        struct blame_entry *e;
1174
1175        if (!porigin->file.ptr && origin->file.ptr) {
1176                /* Steal its file */
1177                porigin->file = origin->file;
1178                origin->file.ptr = NULL;
1179        }
1180        for (e = sb->ent; e; e = e->next) {
1181                if (!same_suspect(e->suspect, origin))
1182                        continue;
1183                origin_incref(porigin);
1184                origin_decref(e->suspect);
1185                e->suspect = porigin;
1186        }
1187}
1188
1189/*
1190 * We pass blame from the current commit to its parents.  We keep saying
1191 * "parent" (and "porigin"), but what we mean is to find scapegoat to
1192 * exonerate ourselves.
1193 */
1194static struct commit_list *first_scapegoat(struct rev_info *revs, struct commit *commit)
1195{
1196        if (!reverse)
1197                return commit->parents;
1198        return lookup_decoration(&revs->children, &commit->object);
1199}
1200
1201static int num_scapegoats(struct rev_info *revs, struct commit *commit)
1202{
1203        int cnt;
1204        struct commit_list *l = first_scapegoat(revs, commit);
1205        for (cnt = 0; l; l = l->next)
1206                cnt++;
1207        return cnt;
1208}
1209
1210#define MAXSG 16
1211
1212static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)
1213{
1214        struct rev_info *revs = sb->revs;
1215        int i, pass, num_sg;
1216        struct commit *commit = origin->commit;
1217        struct commit_list *sg;
1218        struct origin *sg_buf[MAXSG];
1219        struct origin *porigin, **sg_origin = sg_buf;
1220
1221        num_sg = num_scapegoats(revs, commit);
1222        if (!num_sg)
1223                goto finish;
1224        else if (num_sg < ARRAY_SIZE(sg_buf))
1225                memset(sg_buf, 0, sizeof(sg_buf));
1226        else
1227                sg_origin = xcalloc(num_sg, sizeof(*sg_origin));
1228
1229        /*
1230         * The first pass looks for unrenamed path to optimize for
1231         * common cases, then we look for renames in the second pass.
1232         */
1233        for (pass = 0; pass < 2 - no_whole_file_rename; pass++) {
1234                struct origin *(*find)(struct scoreboard *,
1235                                       struct commit *, struct origin *);
1236                find = pass ? find_rename : find_origin;
1237
1238                for (i = 0, sg = first_scapegoat(revs, commit);
1239                     i < num_sg && sg;
1240                     sg = sg->next, i++) {
1241                        struct commit *p = sg->item;
1242                        int j, same;
1243
1244                        if (sg_origin[i])
1245                                continue;
1246                        if (parse_commit(p))
1247                                continue;
1248                        porigin = find(sb, p, origin);
1249                        if (!porigin)
1250                                continue;
1251                        if (!hashcmp(porigin->blob_sha1, origin->blob_sha1)) {
1252                                pass_whole_blame(sb, origin, porigin);
1253                                origin_decref(porigin);
1254                                goto finish;
1255                        }
1256                        for (j = same = 0; j < i; j++)
1257                                if (sg_origin[j] &&
1258                                    !hashcmp(sg_origin[j]->blob_sha1,
1259                                             porigin->blob_sha1)) {
1260                                        same = 1;
1261                                        break;
1262                                }
1263                        if (!same)
1264                                sg_origin[i] = porigin;
1265                        else
1266                                origin_decref(porigin);
1267                }
1268        }
1269
1270        num_commits++;
1271        for (i = 0, sg = first_scapegoat(revs, commit);
1272             i < num_sg && sg;
1273             sg = sg->next, i++) {
1274                struct origin *porigin = sg_origin[i];
1275                if (!porigin)
1276                        continue;
1277                if (!origin->previous) {
1278                        origin_incref(porigin);
1279                        origin->previous = porigin;
1280                }
1281                if (pass_blame_to_parent(sb, origin, porigin))
1282                        goto finish;
1283        }
1284
1285        /*
1286         * Optionally find moves in parents' files.
1287         */
1288        if (opt & PICKAXE_BLAME_MOVE)
1289                for (i = 0, sg = first_scapegoat(revs, commit);
1290                     i < num_sg && sg;
1291                     sg = sg->next, i++) {
1292                        struct origin *porigin = sg_origin[i];
1293                        if (!porigin)
1294                                continue;
1295                        if (find_move_in_parent(sb, origin, porigin))
1296                                goto finish;
1297                }
1298
1299        /*
1300         * Optionally find copies from parents' files.
1301         */
1302        if (opt & PICKAXE_BLAME_COPY)
1303                for (i = 0, sg = first_scapegoat(revs, commit);
1304                     i < num_sg && sg;
1305                     sg = sg->next, i++) {
1306                        struct origin *porigin = sg_origin[i];
1307                        if (find_copy_in_parent(sb, origin, sg->item,
1308                                                porigin, opt))
1309                                goto finish;
1310                }
1311
1312 finish:
1313        for (i = 0; i < num_sg; i++) {
1314                if (sg_origin[i]) {
1315                        drop_origin_blob(sg_origin[i]);
1316                        origin_decref(sg_origin[i]);
1317                }
1318        }
1319        drop_origin_blob(origin);
1320        if (sg_buf != sg_origin)
1321                free(sg_origin);
1322}
1323
1324/*
1325 * Information on commits, used for output.
1326 */
1327struct commit_info {
1328        struct strbuf author;
1329        struct strbuf author_mail;
1330        unsigned long author_time;
1331        struct strbuf author_tz;
1332
1333        /* filled only when asked for details */
1334        struct strbuf committer;
1335        struct strbuf committer_mail;
1336        unsigned long committer_time;
1337        struct strbuf committer_tz;
1338
1339        struct strbuf summary;
1340};
1341
1342/*
1343 * Parse author/committer line in the commit object buffer
1344 */
1345static void get_ac_line(const char *inbuf, const char *what,
1346        struct strbuf *name, struct strbuf *mail,
1347        unsigned long *time, struct strbuf *tz)
1348{
1349        struct ident_split ident;
1350        size_t len, maillen, namelen;
1351        char *tmp, *endp;
1352        const char *namebuf, *mailbuf;
1353
1354        tmp = strstr(inbuf, what);
1355        if (!tmp)
1356                goto error_out;
1357        tmp += strlen(what);
1358        endp = strchr(tmp, '\n');
1359        if (!endp)
1360                len = strlen(tmp);
1361        else
1362                len = endp - tmp;
1363
1364        if (split_ident_line(&ident, tmp, len)) {
1365        error_out:
1366                /* Ugh */
1367                tmp = "(unknown)";
1368                strbuf_addstr(name, tmp);
1369                strbuf_addstr(mail, tmp);
1370                strbuf_addstr(tz, tmp);
1371                *time = 0;
1372                return;
1373        }
1374
1375        namelen = ident.name_end - ident.name_begin;
1376        namebuf = ident.name_begin;
1377
1378        maillen = ident.mail_end - ident.mail_begin;
1379        mailbuf = ident.mail_begin;
1380
1381        if (ident.date_begin && ident.date_end)
1382                *time = strtoul(ident.date_begin, NULL, 10);
1383        else
1384                *time = 0;
1385
1386        if (ident.tz_begin && ident.tz_end)
1387                strbuf_add(tz, ident.tz_begin, ident.tz_end - ident.tz_begin);
1388        else
1389                strbuf_addstr(tz, "(unknown)");
1390
1391        /*
1392         * Now, convert both name and e-mail using mailmap
1393         */
1394        map_user(&mailmap, &mailbuf, &maillen,
1395                 &namebuf, &namelen);
1396
1397        strbuf_addf(mail, "<%.*s>", (int)maillen, mailbuf);
1398        strbuf_add(name, namebuf, namelen);
1399}
1400
1401static void commit_info_init(struct commit_info *ci)
1402{
1403
1404        strbuf_init(&ci->author, 0);
1405        strbuf_init(&ci->author_mail, 0);
1406        strbuf_init(&ci->author_tz, 0);
1407        strbuf_init(&ci->committer, 0);
1408        strbuf_init(&ci->committer_mail, 0);
1409        strbuf_init(&ci->committer_tz, 0);
1410        strbuf_init(&ci->summary, 0);
1411}
1412
1413static void commit_info_destroy(struct commit_info *ci)
1414{
1415
1416        strbuf_release(&ci->author);
1417        strbuf_release(&ci->author_mail);
1418        strbuf_release(&ci->author_tz);
1419        strbuf_release(&ci->committer);
1420        strbuf_release(&ci->committer_mail);
1421        strbuf_release(&ci->committer_tz);
1422        strbuf_release(&ci->summary);
1423}
1424
1425static void get_commit_info(struct commit *commit,
1426                            struct commit_info *ret,
1427                            int detailed)
1428{
1429        int len;
1430        const char *subject, *encoding;
1431        char *message;
1432
1433        commit_info_init(ret);
1434
1435        encoding = get_log_output_encoding();
1436        message = logmsg_reencode(commit, NULL, encoding);
1437        get_ac_line(message, "\nauthor ",
1438                    &ret->author, &ret->author_mail,
1439                    &ret->author_time, &ret->author_tz);
1440
1441        if (!detailed) {
1442                logmsg_free(message, commit);
1443                return;
1444        }
1445
1446        get_ac_line(message, "\ncommitter ",
1447                    &ret->committer, &ret->committer_mail,
1448                    &ret->committer_time, &ret->committer_tz);
1449
1450        len = find_commit_subject(message, &subject);
1451        if (len)
1452                strbuf_add(&ret->summary, subject, len);
1453        else
1454                strbuf_addf(&ret->summary, "(%s)", sha1_to_hex(commit->object.sha1));
1455
1456        logmsg_free(message, commit);
1457}
1458
1459/*
1460 * To allow LF and other nonportable characters in pathnames,
1461 * they are c-style quoted as needed.
1462 */
1463static void write_filename_info(const char *path)
1464{
1465        printf("filename ");
1466        write_name_quoted(path, stdout, '\n');
1467}
1468
1469/*
1470 * Porcelain/Incremental format wants to show a lot of details per
1471 * commit.  Instead of repeating this every line, emit it only once,
1472 * the first time each commit appears in the output (unless the
1473 * user has specifically asked for us to repeat).
1474 */
1475static int emit_one_suspect_detail(struct origin *suspect, int repeat)
1476{
1477        struct commit_info ci;
1478
1479        if (!repeat && (suspect->commit->object.flags & METAINFO_SHOWN))
1480                return 0;
1481
1482        suspect->commit->object.flags |= METAINFO_SHOWN;
1483        get_commit_info(suspect->commit, &ci, 1);
1484        printf("author %s\n", ci.author.buf);
1485        printf("author-mail %s\n", ci.author_mail.buf);
1486        printf("author-time %lu\n", ci.author_time);
1487        printf("author-tz %s\n", ci.author_tz.buf);
1488        printf("committer %s\n", ci.committer.buf);
1489        printf("committer-mail %s\n", ci.committer_mail.buf);
1490        printf("committer-time %lu\n", ci.committer_time);
1491        printf("committer-tz %s\n", ci.committer_tz.buf);
1492        printf("summary %s\n", ci.summary.buf);
1493        if (suspect->commit->object.flags & UNINTERESTING)
1494                printf("boundary\n");
1495        if (suspect->previous) {
1496                struct origin *prev = suspect->previous;
1497                printf("previous %s ", sha1_to_hex(prev->commit->object.sha1));
1498                write_name_quoted(prev->path, stdout, '\n');
1499        }
1500
1501        commit_info_destroy(&ci);
1502
1503        return 1;
1504}
1505
1506/*
1507 * The blame_entry is found to be guilty for the range.  Mark it
1508 * as such, and show it in incremental output.
1509 */
1510static void found_guilty_entry(struct blame_entry *ent)
1511{
1512        if (ent->guilty)
1513                return;
1514        ent->guilty = 1;
1515        if (incremental) {
1516                struct origin *suspect = ent->suspect;
1517
1518                printf("%s %d %d %d\n",
1519                       sha1_to_hex(suspect->commit->object.sha1),
1520                       ent->s_lno + 1, ent->lno + 1, ent->num_lines);
1521                emit_one_suspect_detail(suspect, 0);
1522                write_filename_info(suspect->path);
1523                maybe_flush_or_die(stdout, "stdout");
1524        }
1525}
1526
1527/*
1528 * The main loop -- while the scoreboard has lines whose true origin
1529 * is still unknown, pick one blame_entry, and allow its current
1530 * suspect to pass blames to its parents.
1531 */
1532static void assign_blame(struct scoreboard *sb, int opt)
1533{
1534        struct rev_info *revs = sb->revs;
1535
1536        while (1) {
1537                struct blame_entry *ent;
1538                struct commit *commit;
1539                struct origin *suspect = NULL;
1540
1541                /* find one suspect to break down */
1542                for (ent = sb->ent; !suspect && ent; ent = ent->next)
1543                        if (!ent->guilty)
1544                                suspect = ent->suspect;
1545                if (!suspect)
1546                        return; /* all done */
1547
1548                /*
1549                 * We will use this suspect later in the loop,
1550                 * so hold onto it in the meantime.
1551                 */
1552                origin_incref(suspect);
1553                commit = suspect->commit;
1554                if (!commit->object.parsed)
1555                        parse_commit(commit);
1556                if (reverse ||
1557                    (!(commit->object.flags & UNINTERESTING) &&
1558                     !(revs->max_age != -1 && commit->date < revs->max_age)))
1559                        pass_blame(sb, suspect, opt);
1560                else {
1561                        commit->object.flags |= UNINTERESTING;
1562                        if (commit->object.parsed)
1563                                mark_parents_uninteresting(commit);
1564                }
1565                /* treat root commit as boundary */
1566                if (!commit->parents && !show_root)
1567                        commit->object.flags |= UNINTERESTING;
1568
1569                /* Take responsibility for the remaining entries */
1570                for (ent = sb->ent; ent; ent = ent->next)
1571                        if (same_suspect(ent->suspect, suspect))
1572                                found_guilty_entry(ent);
1573                origin_decref(suspect);
1574
1575                if (DEBUG) /* sanity */
1576                        sanity_check_refcnt(sb);
1577        }
1578}
1579
1580static const char *format_time(unsigned long time, const char *tz_str,
1581                               int show_raw_time)
1582{
1583        static char time_buf[128];
1584        const char *time_str;
1585        int time_len;
1586        int tz;
1587
1588        if (show_raw_time) {
1589                snprintf(time_buf, sizeof(time_buf), "%lu %s", time, tz_str);
1590        }
1591        else {
1592                tz = atoi(tz_str);
1593                time_str = show_date(time, tz, blame_date_mode);
1594                time_len = strlen(time_str);
1595                memcpy(time_buf, time_str, time_len);
1596                memset(time_buf + time_len, ' ', blame_date_width - time_len);
1597        }
1598        return time_buf;
1599}
1600
1601#define OUTPUT_ANNOTATE_COMPAT  001
1602#define OUTPUT_LONG_OBJECT_NAME 002
1603#define OUTPUT_RAW_TIMESTAMP    004
1604#define OUTPUT_PORCELAIN        010
1605#define OUTPUT_SHOW_NAME        020
1606#define OUTPUT_SHOW_NUMBER      040
1607#define OUTPUT_SHOW_SCORE      0100
1608#define OUTPUT_NO_AUTHOR       0200
1609#define OUTPUT_SHOW_EMAIL       0400
1610#define OUTPUT_LINE_PORCELAIN 01000
1611
1612static void emit_porcelain_details(struct origin *suspect, int repeat)
1613{
1614        if (emit_one_suspect_detail(suspect, repeat) ||
1615            (suspect->commit->object.flags & MORE_THAN_ONE_PATH))
1616                write_filename_info(suspect->path);
1617}
1618
1619static void emit_porcelain(struct scoreboard *sb, struct blame_entry *ent,
1620                           int opt)
1621{
1622        int repeat = opt & OUTPUT_LINE_PORCELAIN;
1623        int cnt;
1624        const char *cp;
1625        struct origin *suspect = ent->suspect;
1626        char hex[41];
1627
1628        strcpy(hex, sha1_to_hex(suspect->commit->object.sha1));
1629        printf("%s%c%d %d %d\n",
1630               hex,
1631               ent->guilty ? ' ' : '*', /* purely for debugging */
1632               ent->s_lno + 1,
1633               ent->lno + 1,
1634               ent->num_lines);
1635        emit_porcelain_details(suspect, repeat);
1636
1637        cp = nth_line(sb, ent->lno);
1638        for (cnt = 0; cnt < ent->num_lines; cnt++) {
1639                char ch;
1640                if (cnt) {
1641                        printf("%s %d %d\n", hex,
1642                               ent->s_lno + 1 + cnt,
1643                               ent->lno + 1 + cnt);
1644                        if (repeat)
1645                                emit_porcelain_details(suspect, 1);
1646                }
1647                putchar('\t');
1648                do {
1649                        ch = *cp++;
1650                        putchar(ch);
1651                } while (ch != '\n' &&
1652                         cp < sb->final_buf + sb->final_buf_size);
1653        }
1654
1655        if (sb->final_buf_size && cp[-1] != '\n')
1656                putchar('\n');
1657}
1658
1659static void emit_other(struct scoreboard *sb, struct blame_entry *ent, int opt)
1660{
1661        int cnt;
1662        const char *cp;
1663        struct origin *suspect = ent->suspect;
1664        struct commit_info ci;
1665        char hex[41];
1666        int show_raw_time = !!(opt & OUTPUT_RAW_TIMESTAMP);
1667
1668        get_commit_info(suspect->commit, &ci, 1);
1669        strcpy(hex, sha1_to_hex(suspect->commit->object.sha1));
1670
1671        cp = nth_line(sb, ent->lno);
1672        for (cnt = 0; cnt < ent->num_lines; cnt++) {
1673                char ch;
1674                int length = (opt & OUTPUT_LONG_OBJECT_NAME) ? 40 : abbrev;
1675
1676                if (suspect->commit->object.flags & UNINTERESTING) {
1677                        if (blank_boundary)
1678                                memset(hex, ' ', length);
1679                        else if (!(opt & OUTPUT_ANNOTATE_COMPAT)) {
1680                                length--;
1681                                putchar('^');
1682                        }
1683                }
1684
1685                printf("%.*s", length, hex);
1686                if (opt & OUTPUT_ANNOTATE_COMPAT) {
1687                        const char *name;
1688                        if (opt & OUTPUT_SHOW_EMAIL)
1689                                name = ci.author_mail.buf;
1690                        else
1691                                name = ci.author.buf;
1692                        printf("\t(%10s\t%10s\t%d)", name,
1693                               format_time(ci.author_time, ci.author_tz.buf,
1694                                           show_raw_time),
1695                               ent->lno + 1 + cnt);
1696                } else {
1697                        if (opt & OUTPUT_SHOW_SCORE)
1698                                printf(" %*d %02d",
1699                                       max_score_digits, ent->score,
1700                                       ent->suspect->refcnt);
1701                        if (opt & OUTPUT_SHOW_NAME)
1702                                printf(" %-*.*s", longest_file, longest_file,
1703                                       suspect->path);
1704                        if (opt & OUTPUT_SHOW_NUMBER)
1705                                printf(" %*d", max_orig_digits,
1706                                       ent->s_lno + 1 + cnt);
1707
1708                        if (!(opt & OUTPUT_NO_AUTHOR)) {
1709                                const char *name;
1710                                int pad;
1711                                if (opt & OUTPUT_SHOW_EMAIL)
1712                                        name = ci.author_mail.buf;
1713                                else
1714                                        name = ci.author.buf;
1715                                pad = longest_author - utf8_strwidth(name);
1716                                printf(" (%s%*s %10s",
1717                                       name, pad, "",
1718                                       format_time(ci.author_time,
1719                                                   ci.author_tz.buf,
1720                                                   show_raw_time));
1721                        }
1722                        printf(" %*d) ",
1723                               max_digits, ent->lno + 1 + cnt);
1724                }
1725                do {
1726                        ch = *cp++;
1727                        putchar(ch);
1728                } while (ch != '\n' &&
1729                         cp < sb->final_buf + sb->final_buf_size);
1730        }
1731
1732        if (sb->final_buf_size && cp[-1] != '\n')
1733                putchar('\n');
1734
1735        commit_info_destroy(&ci);
1736}
1737
1738static void output(struct scoreboard *sb, int option)
1739{
1740        struct blame_entry *ent;
1741
1742        if (option & OUTPUT_PORCELAIN) {
1743                for (ent = sb->ent; ent; ent = ent->next) {
1744                        struct blame_entry *oth;
1745                        struct origin *suspect = ent->suspect;
1746                        struct commit *commit = suspect->commit;
1747                        if (commit->object.flags & MORE_THAN_ONE_PATH)
1748                                continue;
1749                        for (oth = ent->next; oth; oth = oth->next) {
1750                                if ((oth->suspect->commit != commit) ||
1751                                    !strcmp(oth->suspect->path, suspect->path))
1752                                        continue;
1753                                commit->object.flags |= MORE_THAN_ONE_PATH;
1754                                break;
1755                        }
1756                }
1757        }
1758
1759        for (ent = sb->ent; ent; ent = ent->next) {
1760                if (option & OUTPUT_PORCELAIN)
1761                        emit_porcelain(sb, ent, option);
1762                else {
1763                        emit_other(sb, ent, option);
1764                }
1765        }
1766}
1767
1768/*
1769 * To allow quick access to the contents of nth line in the
1770 * final image, prepare an index in the scoreboard.
1771 */
1772static int prepare_lines(struct scoreboard *sb)
1773{
1774        const char *buf = sb->final_buf;
1775        unsigned long len = sb->final_buf_size;
1776        int num = 0, incomplete = 0, bol = 1;
1777
1778        if (len && buf[len-1] != '\n')
1779                incomplete++; /* incomplete line at the end */
1780        while (len--) {
1781                if (bol) {
1782                        sb->lineno = xrealloc(sb->lineno,
1783                                              sizeof(int *) * (num + 1));
1784                        sb->lineno[num] = buf - sb->final_buf;
1785                        bol = 0;
1786                }
1787                if (*buf++ == '\n') {
1788                        num++;
1789                        bol = 1;
1790                }
1791        }
1792        sb->lineno = xrealloc(sb->lineno,
1793                              sizeof(int *) * (num + incomplete + 1));
1794        sb->lineno[num + incomplete] = buf - sb->final_buf;
1795        sb->num_lines = num + incomplete;
1796        return sb->num_lines;
1797}
1798
1799/*
1800 * Add phony grafts for use with -S; this is primarily to
1801 * support git's cvsserver that wants to give a linear history
1802 * to its clients.
1803 */
1804static int read_ancestry(const char *graft_file)
1805{
1806        FILE *fp = fopen(graft_file, "r");
1807        char buf[1024];
1808        if (!fp)
1809                return -1;
1810        while (fgets(buf, sizeof(buf), fp)) {
1811                /* The format is just "Commit Parent1 Parent2 ...\n" */
1812                int len = strlen(buf);
1813                struct commit_graft *graft = read_graft_line(buf, len);
1814                if (graft)
1815                        register_commit_graft(graft, 0);
1816        }
1817        fclose(fp);
1818        return 0;
1819}
1820
1821static int update_auto_abbrev(int auto_abbrev, struct origin *suspect)
1822{
1823        const char *uniq = find_unique_abbrev(suspect->commit->object.sha1,
1824                                              auto_abbrev);
1825        int len = strlen(uniq);
1826        if (auto_abbrev < len)
1827                return len;
1828        return auto_abbrev;
1829}
1830
1831/*
1832 * How many columns do we need to show line numbers, authors,
1833 * and filenames?
1834 */
1835static void find_alignment(struct scoreboard *sb, int *option)
1836{
1837        int longest_src_lines = 0;
1838        int longest_dst_lines = 0;
1839        unsigned largest_score = 0;
1840        struct blame_entry *e;
1841        int compute_auto_abbrev = (abbrev < 0);
1842        int auto_abbrev = default_abbrev;
1843
1844        for (e = sb->ent; e; e = e->next) {
1845                struct origin *suspect = e->suspect;
1846                struct commit_info ci;
1847                int num;
1848
1849                if (compute_auto_abbrev)
1850                        auto_abbrev = update_auto_abbrev(auto_abbrev, suspect);
1851                if (strcmp(suspect->path, sb->path))
1852                        *option |= OUTPUT_SHOW_NAME;
1853                num = strlen(suspect->path);
1854                if (longest_file < num)
1855                        longest_file = num;
1856                if (!(suspect->commit->object.flags & METAINFO_SHOWN)) {
1857                        suspect->commit->object.flags |= METAINFO_SHOWN;
1858                        get_commit_info(suspect->commit, &ci, 1);
1859                        if (*option & OUTPUT_SHOW_EMAIL)
1860                                num = utf8_strwidth(ci.author_mail.buf);
1861                        else
1862                                num = utf8_strwidth(ci.author.buf);
1863                        if (longest_author < num)
1864                                longest_author = num;
1865                }
1866                num = e->s_lno + e->num_lines;
1867                if (longest_src_lines < num)
1868                        longest_src_lines = num;
1869                num = e->lno + e->num_lines;
1870                if (longest_dst_lines < num)
1871                        longest_dst_lines = num;
1872                if (largest_score < ent_score(sb, e))
1873                        largest_score = ent_score(sb, e);
1874
1875                commit_info_destroy(&ci);
1876        }
1877        max_orig_digits = decimal_width(longest_src_lines);
1878        max_digits = decimal_width(longest_dst_lines);
1879        max_score_digits = decimal_width(largest_score);
1880
1881        if (compute_auto_abbrev)
1882                /* one more abbrev length is needed for the boundary commit */
1883                abbrev = auto_abbrev + 1;
1884}
1885
1886/*
1887 * For debugging -- origin is refcounted, and this asserts that
1888 * we do not underflow.
1889 */
1890static void sanity_check_refcnt(struct scoreboard *sb)
1891{
1892        int baa = 0;
1893        struct blame_entry *ent;
1894
1895        for (ent = sb->ent; ent; ent = ent->next) {
1896                /* Nobody should have zero or negative refcnt */
1897                if (ent->suspect->refcnt <= 0) {
1898                        fprintf(stderr, "%s in %s has negative refcnt %d\n",
1899                                ent->suspect->path,
1900                                sha1_to_hex(ent->suspect->commit->object.sha1),
1901                                ent->suspect->refcnt);
1902                        baa = 1;
1903                }
1904        }
1905        if (baa) {
1906                int opt = 0160;
1907                find_alignment(sb, &opt);
1908                output(sb, opt);
1909                die("Baa %d!", baa);
1910        }
1911}
1912
1913/*
1914 * Used for the command line parsing; check if the path exists
1915 * in the working tree.
1916 */
1917static int has_string_in_work_tree(const char *path)
1918{
1919        struct stat st;
1920        return !lstat(path, &st);
1921}
1922
1923static unsigned parse_score(const char *arg)
1924{
1925        char *end;
1926        unsigned long score = strtoul(arg, &end, 10);
1927        if (*end)
1928                return 0;
1929        return score;
1930}
1931
1932static const char *add_prefix(const char *prefix, const char *path)
1933{
1934        return prefix_path(prefix, prefix ? strlen(prefix) : 0, path);
1935}
1936
1937static int git_blame_config(const char *var, const char *value, void *cb)
1938{
1939        if (!strcmp(var, "blame.showroot")) {
1940                show_root = git_config_bool(var, value);
1941                return 0;
1942        }
1943        if (!strcmp(var, "blame.blankboundary")) {
1944                blank_boundary = git_config_bool(var, value);
1945                return 0;
1946        }
1947        if (!strcmp(var, "blame.date")) {
1948                if (!value)
1949                        return config_error_nonbool(var);
1950                blame_date_mode = parse_date_format(value);
1951                return 0;
1952        }
1953
1954        if (userdiff_config(var, value) < 0)
1955                return -1;
1956
1957        return git_default_config(var, value, cb);
1958}
1959
1960static void verify_working_tree_path(struct commit *work_tree, const char *path)
1961{
1962        struct commit_list *parents;
1963
1964        for (parents = work_tree->parents; parents; parents = parents->next) {
1965                const unsigned char *commit_sha1 = parents->item->object.sha1;
1966                unsigned char blob_sha1[20];
1967                unsigned mode;
1968
1969                if (!get_tree_entry(commit_sha1, path, blob_sha1, &mode) &&
1970                    sha1_object_info(blob_sha1, NULL) == OBJ_BLOB)
1971                        return;
1972        }
1973        die("no such path '%s' in HEAD", path);
1974}
1975
1976static struct commit_list **append_parent(struct commit_list **tail, const unsigned char *sha1)
1977{
1978        struct commit *parent;
1979
1980        parent = lookup_commit_reference(sha1);
1981        if (!parent)
1982                die("no such commit %s", sha1_to_hex(sha1));
1983        return &commit_list_insert(parent, tail)->next;
1984}
1985
1986static void append_merge_parents(struct commit_list **tail)
1987{
1988        int merge_head;
1989        const char *merge_head_file = git_path("MERGE_HEAD");
1990        struct strbuf line = STRBUF_INIT;
1991
1992        merge_head = open(merge_head_file, O_RDONLY);
1993        if (merge_head < 0) {
1994                if (errno == ENOENT)
1995                        return;
1996                die("cannot open '%s' for reading", merge_head_file);
1997        }
1998
1999        while (!strbuf_getwholeline_fd(&line, merge_head, '\n')) {
2000                unsigned char sha1[20];
2001                if (line.len < 40 || get_sha1_hex(line.buf, sha1))
2002                        die("unknown line in '%s': %s", merge_head_file, line.buf);
2003                tail = append_parent(tail, sha1);
2004        }
2005        close(merge_head);
2006        strbuf_release(&line);
2007}
2008
2009/*
2010 * Prepare a dummy commit that represents the work tree (or staged) item.
2011 * Note that annotating work tree item never works in the reverse.
2012 */
2013static struct commit *fake_working_tree_commit(struct diff_options *opt,
2014                                               const char *path,
2015                                               const char *contents_from)
2016{
2017        struct commit *commit;
2018        struct origin *origin;
2019        struct commit_list **parent_tail, *parent;
2020        unsigned char head_sha1[20];
2021        struct strbuf buf = STRBUF_INIT;
2022        const char *ident;
2023        time_t now;
2024        int size, len;
2025        struct cache_entry *ce;
2026        unsigned mode;
2027        struct strbuf msg = STRBUF_INIT;
2028
2029        time(&now);
2030        commit = xcalloc(1, sizeof(*commit));
2031        commit->object.parsed = 1;
2032        commit->date = now;
2033        commit->object.type = OBJ_COMMIT;
2034        parent_tail = &commit->parents;
2035
2036        if (!resolve_ref_unsafe("HEAD", head_sha1, 1, NULL))
2037                die("no such ref: HEAD");
2038
2039        parent_tail = append_parent(parent_tail, head_sha1);
2040        append_merge_parents(parent_tail);
2041        verify_working_tree_path(commit, path);
2042
2043        origin = make_origin(commit, path);
2044
2045        ident = fmt_ident("Not Committed Yet", "not.committed.yet", NULL, 0);
2046        strbuf_addstr(&msg, "tree 0000000000000000000000000000000000000000\n");
2047        for (parent = commit->parents; parent; parent = parent->next)
2048                strbuf_addf(&msg, "parent %s\n",
2049                            sha1_to_hex(parent->item->object.sha1));
2050        strbuf_addf(&msg,
2051                    "author %s\n"
2052                    "committer %s\n\n"
2053                    "Version of %s from %s\n",
2054                    ident, ident, path,
2055                    (!contents_from ? path :
2056                     (!strcmp(contents_from, "-") ? "standard input" : contents_from)));
2057        commit->buffer = strbuf_detach(&msg, NULL);
2058
2059        if (!contents_from || strcmp("-", contents_from)) {
2060                struct stat st;
2061                const char *read_from;
2062                char *buf_ptr;
2063                unsigned long buf_len;
2064
2065                if (contents_from) {
2066                        if (stat(contents_from, &st) < 0)
2067                                die_errno("Cannot stat '%s'", contents_from);
2068                        read_from = contents_from;
2069                }
2070                else {
2071                        if (lstat(path, &st) < 0)
2072                                die_errno("Cannot lstat '%s'", path);
2073                        read_from = path;
2074                }
2075                mode = canon_mode(st.st_mode);
2076
2077                switch (st.st_mode & S_IFMT) {
2078                case S_IFREG:
2079                        if (DIFF_OPT_TST(opt, ALLOW_TEXTCONV) &&
2080                            textconv_object(read_from, mode, null_sha1, 0, &buf_ptr, &buf_len))
2081                                strbuf_attach(&buf, buf_ptr, buf_len, buf_len + 1);
2082                        else if (strbuf_read_file(&buf, read_from, st.st_size) != st.st_size)
2083                                die_errno("cannot open or read '%s'", read_from);
2084                        break;
2085                case S_IFLNK:
2086                        if (strbuf_readlink(&buf, read_from, st.st_size) < 0)
2087                                die_errno("cannot readlink '%s'", read_from);
2088                        break;
2089                default:
2090                        die("unsupported file type %s", read_from);
2091                }
2092        }
2093        else {
2094                /* Reading from stdin */
2095                mode = 0;
2096                if (strbuf_read(&buf, 0, 0) < 0)
2097                        die_errno("failed to read from stdin");
2098        }
2099        convert_to_git(path, buf.buf, buf.len, &buf, 0);
2100        origin->file.ptr = buf.buf;
2101        origin->file.size = buf.len;
2102        pretend_sha1_file(buf.buf, buf.len, OBJ_BLOB, origin->blob_sha1);
2103        commit->util = origin;
2104
2105        /*
2106         * Read the current index, replace the path entry with
2107         * origin->blob_sha1 without mucking with its mode or type
2108         * bits; we are not going to write this index out -- we just
2109         * want to run "diff-index --cached".
2110         */
2111        discard_cache();
2112        read_cache();
2113
2114        len = strlen(path);
2115        if (!mode) {
2116                int pos = cache_name_pos(path, len);
2117                if (0 <= pos)
2118                        mode = active_cache[pos]->ce_mode;
2119                else
2120                        /* Let's not bother reading from HEAD tree */
2121                        mode = S_IFREG | 0644;
2122        }
2123        size = cache_entry_size(len);
2124        ce = xcalloc(1, size);
2125        hashcpy(ce->sha1, origin->blob_sha1);
2126        memcpy(ce->name, path, len);
2127        ce->ce_flags = create_ce_flags(0);
2128        ce->ce_namelen = len;
2129        ce->ce_mode = create_ce_mode(mode);
2130        add_cache_entry(ce, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE);
2131
2132        /*
2133         * We are not going to write this out, so this does not matter
2134         * right now, but someday we might optimize diff-index --cached
2135         * with cache-tree information.
2136         */
2137        cache_tree_invalidate_path(active_cache_tree, path);
2138
2139        return commit;
2140}
2141
2142static const char *prepare_final(struct scoreboard *sb)
2143{
2144        int i;
2145        const char *final_commit_name = NULL;
2146        struct rev_info *revs = sb->revs;
2147
2148        /*
2149         * There must be one and only one positive commit in the
2150         * revs->pending array.
2151         */
2152        for (i = 0; i < revs->pending.nr; i++) {
2153                struct object *obj = revs->pending.objects[i].item;
2154                if (obj->flags & UNINTERESTING)
2155                        continue;
2156                while (obj->type == OBJ_TAG)
2157                        obj = deref_tag(obj, NULL, 0);
2158                if (obj->type != OBJ_COMMIT)
2159                        die("Non commit %s?", revs->pending.objects[i].name);
2160                if (sb->final)
2161                        die("More than one commit to dig from %s and %s?",
2162                            revs->pending.objects[i].name,
2163                            final_commit_name);
2164                sb->final = (struct commit *) obj;
2165                final_commit_name = revs->pending.objects[i].name;
2166        }
2167        return final_commit_name;
2168}
2169
2170static const char *prepare_initial(struct scoreboard *sb)
2171{
2172        int i;
2173        const char *final_commit_name = NULL;
2174        struct rev_info *revs = sb->revs;
2175
2176        /*
2177         * There must be one and only one negative commit, and it must be
2178         * the boundary.
2179         */
2180        for (i = 0; i < revs->pending.nr; i++) {
2181                struct object *obj = revs->pending.objects[i].item;
2182                if (!(obj->flags & UNINTERESTING))
2183                        continue;
2184                while (obj->type == OBJ_TAG)
2185                        obj = deref_tag(obj, NULL, 0);
2186                if (obj->type != OBJ_COMMIT)
2187                        die("Non commit %s?", revs->pending.objects[i].name);
2188                if (sb->final)
2189                        die("More than one commit to dig down to %s and %s?",
2190                            revs->pending.objects[i].name,
2191                            final_commit_name);
2192                sb->final = (struct commit *) obj;
2193                final_commit_name = revs->pending.objects[i].name;
2194        }
2195        if (!final_commit_name)
2196                die("No commit to dig down to?");
2197        return final_commit_name;
2198}
2199
2200static int blame_copy_callback(const struct option *option, const char *arg, int unset)
2201{
2202        int *opt = option->value;
2203
2204        /*
2205         * -C enables copy from removed files;
2206         * -C -C enables copy from existing files, but only
2207         *       when blaming a new file;
2208         * -C -C -C enables copy from existing files for
2209         *          everybody
2210         */
2211        if (*opt & PICKAXE_BLAME_COPY_HARDER)
2212                *opt |= PICKAXE_BLAME_COPY_HARDEST;
2213        if (*opt & PICKAXE_BLAME_COPY)
2214                *opt |= PICKAXE_BLAME_COPY_HARDER;
2215        *opt |= PICKAXE_BLAME_COPY | PICKAXE_BLAME_MOVE;
2216
2217        if (arg)
2218                blame_copy_score = parse_score(arg);
2219        return 0;
2220}
2221
2222static int blame_move_callback(const struct option *option, const char *arg, int unset)
2223{
2224        int *opt = option->value;
2225
2226        *opt |= PICKAXE_BLAME_MOVE;
2227
2228        if (arg)
2229                blame_move_score = parse_score(arg);
2230        return 0;
2231}
2232
2233int cmd_blame(int argc, const char **argv, const char *prefix)
2234{
2235        struct rev_info revs;
2236        const char *path;
2237        struct scoreboard sb;
2238        struct origin *o;
2239        struct blame_entry *ent = NULL;
2240        long dashdash_pos, lno;
2241        const char *final_commit_name = NULL;
2242        enum object_type type;
2243
2244        static struct string_list range_list;
2245        static int output_option = 0, opt = 0;
2246        static int show_stats = 0;
2247        static const char *revs_file = NULL;
2248        static const char *contents_from = NULL;
2249        static const struct option options[] = {
2250                OPT_BOOL(0, "incremental", &incremental, N_("Show blame entries as we find them, incrementally")),
2251                OPT_BOOL('b', NULL, &blank_boundary, N_("Show blank SHA-1 for boundary commits (Default: off)")),
2252                OPT_BOOL(0, "root", &show_root, N_("Do not treat root commits as boundaries (Default: off)")),
2253                OPT_BOOL(0, "show-stats", &show_stats, N_("Show work cost statistics")),
2254                OPT_BIT(0, "score-debug", &output_option, N_("Show output score for blame entries"), OUTPUT_SHOW_SCORE),
2255                OPT_BIT('f', "show-name", &output_option, N_("Show original filename (Default: auto)"), OUTPUT_SHOW_NAME),
2256                OPT_BIT('n', "show-number", &output_option, N_("Show original linenumber (Default: off)"), OUTPUT_SHOW_NUMBER),
2257                OPT_BIT('p', "porcelain", &output_option, N_("Show in a format designed for machine consumption"), OUTPUT_PORCELAIN),
2258                OPT_BIT(0, "line-porcelain", &output_option, N_("Show porcelain format with per-line commit information"), OUTPUT_PORCELAIN|OUTPUT_LINE_PORCELAIN),
2259                OPT_BIT('c', NULL, &output_option, N_("Use the same output mode as git-annotate (Default: off)"), OUTPUT_ANNOTATE_COMPAT),
2260                OPT_BIT('t', NULL, &output_option, N_("Show raw timestamp (Default: off)"), OUTPUT_RAW_TIMESTAMP),
2261                OPT_BIT('l', NULL, &output_option, N_("Show long commit SHA1 (Default: off)"), OUTPUT_LONG_OBJECT_NAME),
2262                OPT_BIT('s', NULL, &output_option, N_("Suppress author name and timestamp (Default: off)"), OUTPUT_NO_AUTHOR),
2263                OPT_BIT('e', "show-email", &output_option, N_("Show author email instead of name (Default: off)"), OUTPUT_SHOW_EMAIL),
2264                OPT_BIT('w', NULL, &xdl_opts, N_("Ignore whitespace differences"), XDF_IGNORE_WHITESPACE),
2265                OPT_BIT(0, "minimal", &xdl_opts, N_("Spend extra cycles to find better match"), XDF_NEED_MINIMAL),
2266                OPT_STRING('S', NULL, &revs_file, N_("file"), N_("Use revisions from <file> instead of calling git-rev-list")),
2267                OPT_STRING(0, "contents", &contents_from, N_("file"), N_("Use <file>'s contents as the final image")),
2268                { OPTION_CALLBACK, 'C', NULL, &opt, N_("score"), N_("Find line copies within and across files"), PARSE_OPT_OPTARG, blame_copy_callback },
2269                { OPTION_CALLBACK, 'M', NULL, &opt, N_("score"), N_("Find line movements within and across files"), PARSE_OPT_OPTARG, blame_move_callback },
2270                OPT_STRING_LIST('L', NULL, &range_list, N_("n,m"), N_("Process only line range n,m, counting from 1")),
2271                OPT__ABBREV(&abbrev),
2272                OPT_END()
2273        };
2274
2275        struct parse_opt_ctx_t ctx;
2276        int cmd_is_annotate = !strcmp(argv[0], "annotate");
2277        struct range_set ranges;
2278        unsigned int range_i;
2279        long anchor;
2280
2281        git_config(git_blame_config, NULL);
2282        init_revisions(&revs, NULL);
2283        revs.date_mode = blame_date_mode;
2284        DIFF_OPT_SET(&revs.diffopt, ALLOW_TEXTCONV);
2285        DIFF_OPT_SET(&revs.diffopt, FOLLOW_RENAMES);
2286
2287        save_commit_buffer = 0;
2288        dashdash_pos = 0;
2289
2290        parse_options_start(&ctx, argc, argv, prefix, options,
2291                            PARSE_OPT_KEEP_DASHDASH | PARSE_OPT_KEEP_ARGV0);
2292        for (;;) {
2293                switch (parse_options_step(&ctx, options, blame_opt_usage)) {
2294                case PARSE_OPT_HELP:
2295                        exit(129);
2296                case PARSE_OPT_DONE:
2297                        if (ctx.argv[0])
2298                                dashdash_pos = ctx.cpidx;
2299                        goto parse_done;
2300                }
2301
2302                if (!strcmp(ctx.argv[0], "--reverse")) {
2303                        ctx.argv[0] = "--children";
2304                        reverse = 1;
2305                }
2306                parse_revision_opt(&revs, &ctx, options, blame_opt_usage);
2307        }
2308parse_done:
2309        no_whole_file_rename = !DIFF_OPT_TST(&revs.diffopt, FOLLOW_RENAMES);
2310        DIFF_OPT_CLR(&revs.diffopt, FOLLOW_RENAMES);
2311        argc = parse_options_end(&ctx);
2312
2313        if (0 < abbrev)
2314                /* one more abbrev length is needed for the boundary commit */
2315                abbrev++;
2316
2317        if (revs_file && read_ancestry(revs_file))
2318                die_errno("reading graft file '%s' failed", revs_file);
2319
2320        if (cmd_is_annotate) {
2321                output_option |= OUTPUT_ANNOTATE_COMPAT;
2322                blame_date_mode = DATE_ISO8601;
2323        } else {
2324                blame_date_mode = revs.date_mode;
2325        }
2326
2327        /* The maximum width used to show the dates */
2328        switch (blame_date_mode) {
2329        case DATE_RFC2822:
2330                blame_date_width = sizeof("Thu, 19 Oct 2006 16:00:04 -0700");
2331                break;
2332        case DATE_ISO8601:
2333                blame_date_width = sizeof("2006-10-19 16:00:04 -0700");
2334                break;
2335        case DATE_RAW:
2336                blame_date_width = sizeof("1161298804 -0700");
2337                break;
2338        case DATE_SHORT:
2339                blame_date_width = sizeof("2006-10-19");
2340                break;
2341        case DATE_RELATIVE:
2342                /* "normal" is used as the fallback for "relative" */
2343        case DATE_LOCAL:
2344        case DATE_NORMAL:
2345                blame_date_width = sizeof("Thu Oct 19 16:00:04 2006 -0700");
2346                break;
2347        }
2348        blame_date_width -= 1; /* strip the null */
2349
2350        if (DIFF_OPT_TST(&revs.diffopt, FIND_COPIES_HARDER))
2351                opt |= (PICKAXE_BLAME_COPY | PICKAXE_BLAME_MOVE |
2352                        PICKAXE_BLAME_COPY_HARDER);
2353
2354        if (!blame_move_score)
2355                blame_move_score = BLAME_DEFAULT_MOVE_SCORE;
2356        if (!blame_copy_score)
2357                blame_copy_score = BLAME_DEFAULT_COPY_SCORE;
2358
2359        /*
2360         * We have collected options unknown to us in argv[1..unk]
2361         * which are to be passed to revision machinery if we are
2362         * going to do the "bottom" processing.
2363         *
2364         * The remaining are:
2365         *
2366         * (1) if dashdash_pos != 0, it is either
2367         *     "blame [revisions] -- <path>" or
2368         *     "blame -- <path> <rev>"
2369         *
2370         * (2) otherwise, it is one of the two:
2371         *     "blame [revisions] <path>"
2372         *     "blame <path> <rev>"
2373         *
2374         * Note that we must strip out <path> from the arguments: we do not
2375         * want the path pruning but we may want "bottom" processing.
2376         */
2377        if (dashdash_pos) {
2378                switch (argc - dashdash_pos - 1) {
2379                case 2: /* (1b) */
2380                        if (argc != 4)
2381                                usage_with_options(blame_opt_usage, options);
2382                        /* reorder for the new way: <rev> -- <path> */
2383                        argv[1] = argv[3];
2384                        argv[3] = argv[2];
2385                        argv[2] = "--";
2386                        /* FALLTHROUGH */
2387                case 1: /* (1a) */
2388                        path = add_prefix(prefix, argv[--argc]);
2389                        argv[argc] = NULL;
2390                        break;
2391                default:
2392                        usage_with_options(blame_opt_usage, options);
2393                }
2394        } else {
2395                if (argc < 2)
2396                        usage_with_options(blame_opt_usage, options);
2397                path = add_prefix(prefix, argv[argc - 1]);
2398                if (argc == 3 && !has_string_in_work_tree(path)) { /* (2b) */
2399                        path = add_prefix(prefix, argv[1]);
2400                        argv[1] = argv[2];
2401                }
2402                argv[argc - 1] = "--";
2403
2404                setup_work_tree();
2405                if (!has_string_in_work_tree(path))
2406                        die_errno("cannot stat path '%s'", path);
2407        }
2408
2409        revs.disable_stdin = 1;
2410        setup_revisions(argc, argv, &revs, NULL);
2411        memset(&sb, 0, sizeof(sb));
2412
2413        sb.revs = &revs;
2414        if (!reverse)
2415                final_commit_name = prepare_final(&sb);
2416        else if (contents_from)
2417                die("--contents and --children do not blend well.");
2418        else
2419                final_commit_name = prepare_initial(&sb);
2420
2421        if (!sb.final) {
2422                /*
2423                 * "--not A B -- path" without anything positive;
2424                 * do not default to HEAD, but use the working tree
2425                 * or "--contents".
2426                 */
2427                setup_work_tree();
2428                sb.final = fake_working_tree_commit(&sb.revs->diffopt,
2429                                                    path, contents_from);
2430                add_pending_object(&revs, &(sb.final->object), ":");
2431        }
2432        else if (contents_from)
2433                die("Cannot use --contents with final commit object name");
2434
2435        /*
2436         * If we have bottom, this will mark the ancestors of the
2437         * bottom commits we would reach while traversing as
2438         * uninteresting.
2439         */
2440        if (prepare_revision_walk(&revs))
2441                die("revision walk setup failed");
2442
2443        if (is_null_sha1(sb.final->object.sha1)) {
2444                char *buf;
2445                o = sb.final->util;
2446                buf = xmalloc(o->file.size + 1);
2447                memcpy(buf, o->file.ptr, o->file.size + 1);
2448                sb.final_buf = buf;
2449                sb.final_buf_size = o->file.size;
2450        }
2451        else {
2452                o = get_origin(&sb, sb.final, path);
2453                if (fill_blob_sha1_and_mode(o))
2454                        die("no such path %s in %s", path, final_commit_name);
2455
2456                if (DIFF_OPT_TST(&sb.revs->diffopt, ALLOW_TEXTCONV) &&
2457                    textconv_object(path, o->mode, o->blob_sha1, 1, (char **) &sb.final_buf,
2458                                    &sb.final_buf_size))
2459                        ;
2460                else
2461                        sb.final_buf = read_sha1_file(o->blob_sha1, &type,
2462                                                      &sb.final_buf_size);
2463
2464                if (!sb.final_buf)
2465                        die("Cannot read blob %s for path %s",
2466                            sha1_to_hex(o->blob_sha1),
2467                            path);
2468        }
2469        num_read_blob++;
2470        lno = prepare_lines(&sb);
2471
2472        if (lno && !range_list.nr)
2473                string_list_append(&range_list, xstrdup("1"));
2474
2475        anchor = 1;
2476        range_set_init(&ranges, range_list.nr);
2477        for (range_i = 0; range_i < range_list.nr; ++range_i) {
2478                long bottom, top;
2479                if (parse_range_arg(range_list.items[range_i].string,
2480                                    nth_line_cb, &sb, lno, anchor,
2481                                    &bottom, &top, sb.path))
2482                        usage(blame_usage);
2483                if (lno < top || ((lno || bottom) && lno < bottom))
2484                        die("file %s has only %lu lines", path, lno);
2485                if (bottom < 1)
2486                        bottom = 1;
2487                if (top < 1)
2488                        top = lno;
2489                bottom--;
2490                range_set_append_unsafe(&ranges, bottom, top);
2491                anchor = top + 1;
2492        }
2493        sort_and_merge_range_set(&ranges);
2494
2495        for (range_i = ranges.nr; range_i > 0; --range_i) {
2496                const struct range *r = &ranges.ranges[range_i - 1];
2497                long bottom = r->start;
2498                long top = r->end;
2499                struct blame_entry *next = ent;
2500                ent = xcalloc(1, sizeof(*ent));
2501                ent->lno = bottom;
2502                ent->num_lines = top - bottom;
2503                ent->suspect = o;
2504                ent->s_lno = bottom;
2505                ent->next = next;
2506                if (next)
2507                        next->prev = ent;
2508                origin_incref(o);
2509        }
2510        origin_decref(o);
2511
2512        range_set_release(&ranges);
2513        string_list_clear(&range_list, 0);
2514
2515        sb.ent = ent;
2516        sb.path = path;
2517
2518        read_mailmap(&mailmap, NULL);
2519
2520        if (!incremental)
2521                setup_pager();
2522
2523        assign_blame(&sb, opt);
2524
2525        if (incremental)
2526                return 0;
2527
2528        coalesce(&sb);
2529
2530        if (!(output_option & OUTPUT_PORCELAIN))
2531                find_alignment(&sb, &output_option);
2532
2533        output(&sb, output_option);
2534        free((void *)sb.final_buf);
2535        for (ent = sb.ent; ent; ) {
2536                struct blame_entry *e = ent->next;
2537                free(ent);
2538                ent = e;
2539        }
2540
2541        if (show_stats) {
2542                printf("num read blob: %d\n", num_read_blob);
2543                printf("num get patch: %d\n", num_get_patch);
2544                printf("num commits: %d\n", num_commits);
2545        }
2546        return 0;
2547}