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