1/* 2 * Blame 3 * 4 * Copyright (c) 2006, 2014 by its authors 5 * See COPYING for licensing conditions 6 */ 7 8#include"cache.h" 9#include"refs.h" 10#include"builtin.h" 11#include"blob.h" 12#include"commit.h" 13#include"tag.h" 14#include"tree-walk.h" 15#include"diff.h" 16#include"diffcore.h" 17#include"revision.h" 18#include"quote.h" 19#include"xdiff-interface.h" 20#include"cache-tree.h" 21#include"string-list.h" 22#include"mailmap.h" 23#include"mergesort.h" 24#include"parse-options.h" 25#include"prio-queue.h" 26#include"utf8.h" 27#include"userdiff.h" 28#include"line-range.h" 29#include"line-log.h" 30#include"dir.h" 31#include"progress.h" 32 33static char blame_usage[] =N_("git blame [<options>] [<rev-opts>] [<rev>] [--] <file>"); 34 35static const char*blame_opt_usage[] = { 36 blame_usage, 37"", 38N_("<rev-opts> are documented in git-rev-list(1)"), 39 NULL 40}; 41 42static int longest_file; 43static int longest_author; 44static int max_orig_digits; 45static int max_digits; 46static int max_score_digits; 47static int show_root; 48static int reverse; 49static int blank_boundary; 50static int incremental; 51static int xdl_opts; 52static int abbrev = -1; 53static int no_whole_file_rename; 54static int show_progress; 55 56static struct date_mode blame_date_mode = { DATE_ISO8601 }; 57static size_t blame_date_width; 58 59static struct string_list mailmap = STRING_LIST_INIT_NODUP; 60 61#ifndef DEBUG 62#define DEBUG 0 63#endif 64 65/* stats */ 66static int num_read_blob; 67static int num_get_patch; 68static int num_commits; 69 70#define PICKAXE_BLAME_MOVE 01 71#define PICKAXE_BLAME_COPY 02 72#define PICKAXE_BLAME_COPY_HARDER 04 73#define PICKAXE_BLAME_COPY_HARDEST 010 74 75/* 76 * blame for a blame_entry with score lower than these thresholds 77 * is not passed to the parent using move/copy logic. 78 */ 79static unsigned blame_move_score; 80static unsigned blame_copy_score; 81#define BLAME_DEFAULT_MOVE_SCORE 20 82#define BLAME_DEFAULT_COPY_SCORE 40 83 84/* Remember to update object flag allocation in object.h */ 85#define METAINFO_SHOWN (1u<<12) 86#define MORE_THAN_ONE_PATH (1u<<13) 87 88/* 89 * One blob in a commit that is being suspected 90 */ 91struct origin { 92int refcnt; 93/* Record preceding blame record for this blob */ 94struct origin *previous; 95/* origins are put in a list linked via `next' hanging off the 96 * corresponding commit's util field in order to make finding 97 * them fast. The presence in this chain does not count 98 * towards the origin's reference count. It is tempting to 99 * let it count as long as the commit is pending examination, 100 * but even under circumstances where the commit will be 101 * present multiple times in the priority queue of unexamined 102 * commits, processing the first instance will not leave any 103 * work requiring the origin data for the second instance. An 104 * interspersed commit changing that would have to be 105 * preexisting with a different ancestry and with the same 106 * commit date in order to wedge itself between two instances 107 * of the same commit in the priority queue _and_ produce 108 * blame entries relevant for it. While we don't want to let 109 * us get tripped up by this case, it certainly does not seem 110 * worth optimizing for. 111 */ 112struct origin *next; 113struct commit *commit; 114/* `suspects' contains blame entries that may be attributed to 115 * this origin's commit or to parent commits. When a commit 116 * is being processed, all suspects will be moved, either by 117 * assigning them to an origin in a different commit, or by 118 * shipping them to the scoreboard's ent list because they 119 * cannot be attributed to a different commit. 120 */ 121struct blame_entry *suspects; 122 mmfile_t file; 123struct object_id blob_oid; 124unsigned mode; 125/* guilty gets set when shipping any suspects to the final 126 * blame list instead of other commits 127 */ 128char guilty; 129char path[FLEX_ARRAY]; 130}; 131 132struct progress_info { 133struct progress *progress; 134int blamed_lines; 135}; 136 137static intdiff_hunks(mmfile_t *file_a, mmfile_t *file_b, 138 xdl_emit_hunk_consume_func_t hunk_func,void*cb_data) 139{ 140 xpparam_t xpp = {0}; 141 xdemitconf_t xecfg = {0}; 142 xdemitcb_t ecb = {NULL}; 143 144 xpp.flags = xdl_opts; 145 xecfg.hunk_func = hunk_func; 146 ecb.priv = cb_data; 147returnxdi_diff(file_a, file_b, &xpp, &xecfg, &ecb); 148} 149 150/* 151 * Prepare diff_filespec and convert it using diff textconv API 152 * if the textconv driver exists. 153 * Return 1 if the conversion succeeds, 0 otherwise. 154 */ 155inttextconv_object(const char*path, 156unsigned mode, 157const struct object_id *oid, 158int oid_valid, 159char**buf, 160unsigned long*buf_size) 161{ 162struct diff_filespec *df; 163struct userdiff_driver *textconv; 164 165 df =alloc_filespec(path); 166fill_filespec(df, oid->hash, oid_valid, mode); 167 textconv =get_textconv(df); 168if(!textconv) { 169free_filespec(df); 170return0; 171} 172 173*buf_size =fill_textconv(textconv, df, buf); 174free_filespec(df); 175return1; 176} 177 178/* 179 * Given an origin, prepare mmfile_t structure to be used by the 180 * diff machinery 181 */ 182static voidfill_origin_blob(struct diff_options *opt, 183struct origin *o, mmfile_t *file) 184{ 185if(!o->file.ptr) { 186enum object_type type; 187unsigned long file_size; 188 189 num_read_blob++; 190if(DIFF_OPT_TST(opt, ALLOW_TEXTCONV) && 191textconv_object(o->path, o->mode, &o->blob_oid,1, &file->ptr, &file_size)) 192; 193else 194 file->ptr =read_sha1_file(o->blob_oid.hash, &type, 195&file_size); 196 file->size = file_size; 197 198if(!file->ptr) 199die("Cannot read blob%sfor path%s", 200oid_to_hex(&o->blob_oid), 201 o->path); 202 o->file = *file; 203} 204else 205*file = o->file; 206} 207 208/* 209 * Origin is refcounted and usually we keep the blob contents to be 210 * reused. 211 */ 212staticinlinestruct origin *origin_incref(struct origin *o) 213{ 214if(o) 215 o->refcnt++; 216return o; 217} 218 219static voidorigin_decref(struct origin *o) 220{ 221if(o && --o->refcnt <=0) { 222struct origin *p, *l = NULL; 223if(o->previous) 224origin_decref(o->previous); 225free(o->file.ptr); 226/* Should be present exactly once in commit chain */ 227for(p = o->commit->util; p; l = p, p = p->next) { 228if(p == o) { 229if(l) 230 l->next = p->next; 231else 232 o->commit->util = p->next; 233free(o); 234return; 235} 236} 237die("internal error in blame::origin_decref"); 238} 239} 240 241static voiddrop_origin_blob(struct origin *o) 242{ 243if(o->file.ptr) { 244free(o->file.ptr); 245 o->file.ptr = NULL; 246} 247} 248 249/* 250 * Each group of lines is described by a blame_entry; it can be split 251 * as we pass blame to the parents. They are arranged in linked lists 252 * kept as `suspects' of some unprocessed origin, or entered (when the 253 * blame origin has been finalized) into the scoreboard structure. 254 * While the scoreboard structure is only sorted at the end of 255 * processing (according to final image line number), the lists 256 * attached to an origin are sorted by the target line number. 257 */ 258struct blame_entry { 259struct blame_entry *next; 260 261/* the first line of this group in the final image; 262 * internally all line numbers are 0 based. 263 */ 264int lno; 265 266/* how many lines this group has */ 267int num_lines; 268 269/* the commit that introduced this group into the final image */ 270struct origin *suspect; 271 272/* the line number of the first line of this group in the 273 * suspect's file; internally all line numbers are 0 based. 274 */ 275int s_lno; 276 277/* how significant this entry is -- cached to avoid 278 * scanning the lines over and over. 279 */ 280unsigned score; 281}; 282 283/* 284 * Any merge of blames happens on lists of blames that arrived via 285 * different parents in a single suspect. In this case, we want to 286 * sort according to the suspect line numbers as opposed to the final 287 * image line numbers. The function body is somewhat longish because 288 * it avoids unnecessary writes. 289 */ 290 291static struct blame_entry *blame_merge(struct blame_entry *list1, 292struct blame_entry *list2) 293{ 294struct blame_entry *p1 = list1, *p2 = list2, 295**tail = &list1; 296 297if(!p1) 298return p2; 299if(!p2) 300return p1; 301 302if(p1->s_lno <= p2->s_lno) { 303do{ 304 tail = &p1->next; 305if((p1 = *tail) == NULL) { 306*tail = p2; 307return list1; 308} 309}while(p1->s_lno <= p2->s_lno); 310} 311for(;;) { 312*tail = p2; 313do{ 314 tail = &p2->next; 315if((p2 = *tail) == NULL) { 316*tail = p1; 317return list1; 318} 319}while(p1->s_lno > p2->s_lno); 320*tail = p1; 321do{ 322 tail = &p1->next; 323if((p1 = *tail) == NULL) { 324*tail = p2; 325return list1; 326} 327}while(p1->s_lno <= p2->s_lno); 328} 329} 330 331static void*get_next_blame(const void*p) 332{ 333return((struct blame_entry *)p)->next; 334} 335 336static voidset_next_blame(void*p1,void*p2) 337{ 338((struct blame_entry *)p1)->next = p2; 339} 340 341/* 342 * Final image line numbers are all different, so we don't need a 343 * three-way comparison here. 344 */ 345 346static intcompare_blame_final(const void*p1,const void*p2) 347{ 348return((struct blame_entry *)p1)->lno > ((struct blame_entry *)p2)->lno 349?1: -1; 350} 351 352static intcompare_blame_suspect(const void*p1,const void*p2) 353{ 354const struct blame_entry *s1 = p1, *s2 = p2; 355/* 356 * to allow for collating suspects, we sort according to the 357 * respective pointer value as the primary sorting criterion. 358 * The actual relation is pretty unimportant as long as it 359 * establishes a total order. Comparing as integers gives us 360 * that. 361 */ 362if(s1->suspect != s2->suspect) 363return(intptr_t)s1->suspect > (intptr_t)s2->suspect ?1: -1; 364if(s1->s_lno == s2->s_lno) 365return0; 366return s1->s_lno > s2->s_lno ?1: -1; 367} 368 369static struct blame_entry *blame_sort(struct blame_entry *head, 370int(*compare_fn)(const void*,const void*)) 371{ 372returnllist_mergesort(head, get_next_blame, set_next_blame, compare_fn); 373} 374 375static intcompare_commits_by_reverse_commit_date(const void*a, 376const void*b, 377void*c) 378{ 379return-compare_commits_by_commit_date(a, b, c); 380} 381 382/* 383 * The current state of the blame assignment. 384 */ 385struct scoreboard { 386/* the final commit (i.e. where we started digging from) */ 387struct commit *final; 388/* Priority queue for commits with unassigned blame records */ 389struct prio_queue commits; 390struct rev_info *revs; 391const char*path; 392 393/* 394 * The contents in the final image. 395 * Used by many functions to obtain contents of the nth line, 396 * indexed with scoreboard.lineno[blame_entry.lno]. 397 */ 398const char*final_buf; 399unsigned long final_buf_size; 400 401/* linked list of blames */ 402struct blame_entry *ent; 403 404/* look-up a line in the final buffer */ 405int num_lines; 406int*lineno; 407}; 408 409static voidsanity_check_refcnt(struct scoreboard *); 410 411/* 412 * If two blame entries that are next to each other came from 413 * contiguous lines in the same origin (i.e. <commit, path> pair), 414 * merge them together. 415 */ 416static voidcoalesce(struct scoreboard *sb) 417{ 418struct blame_entry *ent, *next; 419 420for(ent = sb->ent; ent && (next = ent->next); ent = next) { 421if(ent->suspect == next->suspect && 422 ent->s_lno + ent->num_lines == next->s_lno) { 423 ent->num_lines += next->num_lines; 424 ent->next = next->next; 425origin_decref(next->suspect); 426free(next); 427 ent->score =0; 428 next = ent;/* again */ 429} 430} 431 432if(DEBUG)/* sanity */ 433sanity_check_refcnt(sb); 434} 435 436/* 437 * Merge the given sorted list of blames into a preexisting origin. 438 * If there were no previous blames to that commit, it is entered into 439 * the commit priority queue of the score board. 440 */ 441 442static voidqueue_blames(struct scoreboard *sb,struct origin *porigin, 443struct blame_entry *sorted) 444{ 445if(porigin->suspects) 446 porigin->suspects =blame_merge(porigin->suspects, sorted); 447else{ 448struct origin *o; 449for(o = porigin->commit->util; o; o = o->next) { 450if(o->suspects) { 451 porigin->suspects = sorted; 452return; 453} 454} 455 porigin->suspects = sorted; 456prio_queue_put(&sb->commits, porigin->commit); 457} 458} 459 460/* 461 * Given a commit and a path in it, create a new origin structure. 462 * The callers that add blame to the scoreboard should use 463 * get_origin() to obtain shared, refcounted copy instead of calling 464 * this function directly. 465 */ 466static struct origin *make_origin(struct commit *commit,const char*path) 467{ 468struct origin *o; 469FLEX_ALLOC_STR(o, path, path); 470 o->commit = commit; 471 o->refcnt =1; 472 o->next = commit->util; 473 commit->util = o; 474return o; 475} 476 477/* 478 * Locate an existing origin or create a new one. 479 * This moves the origin to front position in the commit util list. 480 */ 481static struct origin *get_origin(struct scoreboard *sb, 482struct commit *commit, 483const char*path) 484{ 485struct origin *o, *l; 486 487for(o = commit->util, l = NULL; o; l = o, o = o->next) { 488if(!strcmp(o->path, path)) { 489/* bump to front */ 490if(l) { 491 l->next = o->next; 492 o->next = commit->util; 493 commit->util = o; 494} 495returnorigin_incref(o); 496} 497} 498returnmake_origin(commit, path); 499} 500 501/* 502 * Fill the blob_sha1 field of an origin if it hasn't, so that later 503 * call to fill_origin_blob() can use it to locate the data. blob_sha1 504 * for an origin is also used to pass the blame for the entire file to 505 * the parent to detect the case where a child's blob is identical to 506 * that of its parent's. 507 * 508 * This also fills origin->mode for corresponding tree path. 509 */ 510static intfill_blob_sha1_and_mode(struct origin *origin) 511{ 512if(!is_null_oid(&origin->blob_oid)) 513return0; 514if(get_tree_entry(origin->commit->object.oid.hash, 515 origin->path, 516 origin->blob_oid.hash, &origin->mode)) 517goto error_out; 518if(sha1_object_info(origin->blob_oid.hash, NULL) != OBJ_BLOB) 519goto error_out; 520return0; 521 error_out: 522oidclr(&origin->blob_oid); 523 origin->mode = S_IFINVALID; 524return-1; 525} 526 527/* 528 * We have an origin -- check if the same path exists in the 529 * parent and return an origin structure to represent it. 530 */ 531static struct origin *find_origin(struct scoreboard *sb, 532struct commit *parent, 533struct origin *origin) 534{ 535struct origin *porigin; 536struct diff_options diff_opts; 537const char*paths[2]; 538 539/* First check any existing origins */ 540for(porigin = parent->util; porigin; porigin = porigin->next) 541if(!strcmp(porigin->path, origin->path)) { 542/* 543 * The same path between origin and its parent 544 * without renaming -- the most common case. 545 */ 546returnorigin_incref(porigin); 547} 548 549/* See if the origin->path is different between parent 550 * and origin first. Most of the time they are the 551 * same and diff-tree is fairly efficient about this. 552 */ 553diff_setup(&diff_opts); 554DIFF_OPT_SET(&diff_opts, RECURSIVE); 555 diff_opts.detect_rename =0; 556 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT; 557 paths[0] = origin->path; 558 paths[1] = NULL; 559 560parse_pathspec(&diff_opts.pathspec, 561 PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL, 562 PATHSPEC_LITERAL_PATH,"", paths); 563diff_setup_done(&diff_opts); 564 565if(is_null_oid(&origin->commit->object.oid)) 566do_diff_cache(parent->tree->object.oid.hash, &diff_opts); 567else 568diff_tree_sha1(parent->tree->object.oid.hash, 569 origin->commit->tree->object.oid.hash, 570"", &diff_opts); 571diffcore_std(&diff_opts); 572 573if(!diff_queued_diff.nr) { 574/* The path is the same as parent */ 575 porigin =get_origin(sb, parent, origin->path); 576oidcpy(&porigin->blob_oid, &origin->blob_oid); 577 porigin->mode = origin->mode; 578}else{ 579/* 580 * Since origin->path is a pathspec, if the parent 581 * commit had it as a directory, we will see a whole 582 * bunch of deletion of files in the directory that we 583 * do not care about. 584 */ 585int i; 586struct diff_filepair *p = NULL; 587for(i =0; i < diff_queued_diff.nr; i++) { 588const char*name; 589 p = diff_queued_diff.queue[i]; 590 name = p->one->path ? p->one->path : p->two->path; 591if(!strcmp(name, origin->path)) 592break; 593} 594if(!p) 595die("internal error in blame::find_origin"); 596switch(p->status) { 597default: 598die("internal error in blame::find_origin (%c)", 599 p->status); 600case'M': 601 porigin =get_origin(sb, parent, origin->path); 602oidcpy(&porigin->blob_oid, &p->one->oid); 603 porigin->mode = p->one->mode; 604break; 605case'A': 606case'T': 607/* Did not exist in parent, or type changed */ 608break; 609} 610} 611diff_flush(&diff_opts); 612clear_pathspec(&diff_opts.pathspec); 613return porigin; 614} 615 616/* 617 * We have an origin -- find the path that corresponds to it in its 618 * parent and return an origin structure to represent it. 619 */ 620static struct origin *find_rename(struct scoreboard *sb, 621struct commit *parent, 622struct origin *origin) 623{ 624struct origin *porigin = NULL; 625struct diff_options diff_opts; 626int i; 627 628diff_setup(&diff_opts); 629DIFF_OPT_SET(&diff_opts, RECURSIVE); 630 diff_opts.detect_rename = DIFF_DETECT_RENAME; 631 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT; 632 diff_opts.single_follow = origin->path; 633diff_setup_done(&diff_opts); 634 635if(is_null_oid(&origin->commit->object.oid)) 636do_diff_cache(parent->tree->object.oid.hash, &diff_opts); 637else 638diff_tree_sha1(parent->tree->object.oid.hash, 639 origin->commit->tree->object.oid.hash, 640"", &diff_opts); 641diffcore_std(&diff_opts); 642 643for(i =0; i < diff_queued_diff.nr; i++) { 644struct diff_filepair *p = diff_queued_diff.queue[i]; 645if((p->status =='R'|| p->status =='C') && 646!strcmp(p->two->path, origin->path)) { 647 porigin =get_origin(sb, parent, p->one->path); 648oidcpy(&porigin->blob_oid, &p->one->oid); 649 porigin->mode = p->one->mode; 650break; 651} 652} 653diff_flush(&diff_opts); 654clear_pathspec(&diff_opts.pathspec); 655return porigin; 656} 657 658/* 659 * Append a new blame entry to a given output queue. 660 */ 661static voidadd_blame_entry(struct blame_entry ***queue, 662const struct blame_entry *src) 663{ 664struct blame_entry *e =xmalloc(sizeof(*e)); 665memcpy(e, src,sizeof(*e)); 666origin_incref(e->suspect); 667 668 e->next = **queue; 669**queue = e; 670*queue = &e->next; 671} 672 673/* 674 * src typically is on-stack; we want to copy the information in it to 675 * a malloced blame_entry that gets added to the given queue. The 676 * origin of dst loses a refcnt. 677 */ 678static voiddup_entry(struct blame_entry ***queue, 679struct blame_entry *dst,struct blame_entry *src) 680{ 681origin_incref(src->suspect); 682origin_decref(dst->suspect); 683memcpy(dst, src,sizeof(*src)); 684 dst->next = **queue; 685**queue = dst; 686*queue = &dst->next; 687} 688 689static const char*nth_line(struct scoreboard *sb,long lno) 690{ 691return sb->final_buf + sb->lineno[lno]; 692} 693 694static const char*nth_line_cb(void*data,long lno) 695{ 696returnnth_line((struct scoreboard *)data, lno); 697} 698 699/* 700 * It is known that lines between tlno to same came from parent, and e 701 * has an overlap with that range. it also is known that parent's 702 * line plno corresponds to e's line tlno. 703 * 704 * <---- e -----> 705 * <------> 706 * <------------> 707 * <------------> 708 * <------------------> 709 * 710 * Split e into potentially three parts; before this chunk, the chunk 711 * to be blamed for the parent, and after that portion. 712 */ 713static voidsplit_overlap(struct blame_entry *split, 714struct blame_entry *e, 715int tlno,int plno,int same, 716struct origin *parent) 717{ 718int chunk_end_lno; 719memset(split,0,sizeof(struct blame_entry [3])); 720 721if(e->s_lno < tlno) { 722/* there is a pre-chunk part not blamed on parent */ 723 split[0].suspect =origin_incref(e->suspect); 724 split[0].lno = e->lno; 725 split[0].s_lno = e->s_lno; 726 split[0].num_lines = tlno - e->s_lno; 727 split[1].lno = e->lno + tlno - e->s_lno; 728 split[1].s_lno = plno; 729} 730else{ 731 split[1].lno = e->lno; 732 split[1].s_lno = plno + (e->s_lno - tlno); 733} 734 735if(same < e->s_lno + e->num_lines) { 736/* there is a post-chunk part not blamed on parent */ 737 split[2].suspect =origin_incref(e->suspect); 738 split[2].lno = e->lno + (same - e->s_lno); 739 split[2].s_lno = e->s_lno + (same - e->s_lno); 740 split[2].num_lines = e->s_lno + e->num_lines - same; 741 chunk_end_lno = split[2].lno; 742} 743else 744 chunk_end_lno = e->lno + e->num_lines; 745 split[1].num_lines = chunk_end_lno - split[1].lno; 746 747/* 748 * if it turns out there is nothing to blame the parent for, 749 * forget about the splitting. !split[1].suspect signals this. 750 */ 751if(split[1].num_lines <1) 752return; 753 split[1].suspect =origin_incref(parent); 754} 755 756/* 757 * split_overlap() divided an existing blame e into up to three parts 758 * in split. Any assigned blame is moved to queue to 759 * reflect the split. 760 */ 761static voidsplit_blame(struct blame_entry ***blamed, 762struct blame_entry ***unblamed, 763struct blame_entry *split, 764struct blame_entry *e) 765{ 766if(split[0].suspect && split[2].suspect) { 767/* The first part (reuse storage for the existing entry e) */ 768dup_entry(unblamed, e, &split[0]); 769 770/* The last part -- me */ 771add_blame_entry(unblamed, &split[2]); 772 773/* ... and the middle part -- parent */ 774add_blame_entry(blamed, &split[1]); 775} 776else if(!split[0].suspect && !split[2].suspect) 777/* 778 * The parent covers the entire area; reuse storage for 779 * e and replace it with the parent. 780 */ 781dup_entry(blamed, e, &split[1]); 782else if(split[0].suspect) { 783/* me and then parent */ 784dup_entry(unblamed, e, &split[0]); 785add_blame_entry(blamed, &split[1]); 786} 787else{ 788/* parent and then me */ 789dup_entry(blamed, e, &split[1]); 790add_blame_entry(unblamed, &split[2]); 791} 792} 793 794/* 795 * After splitting the blame, the origins used by the 796 * on-stack blame_entry should lose one refcnt each. 797 */ 798static voiddecref_split(struct blame_entry *split) 799{ 800int i; 801 802for(i =0; i <3; i++) 803origin_decref(split[i].suspect); 804} 805 806/* 807 * reverse_blame reverses the list given in head, appending tail. 808 * That allows us to build lists in reverse order, then reverse them 809 * afterwards. This can be faster than building the list in proper 810 * order right away. The reason is that building in proper order 811 * requires writing a link in the _previous_ element, while building 812 * in reverse order just requires placing the list head into the 813 * _current_ element. 814 */ 815 816static struct blame_entry *reverse_blame(struct blame_entry *head, 817struct blame_entry *tail) 818{ 819while(head) { 820struct blame_entry *next = head->next; 821 head->next = tail; 822 tail = head; 823 head = next; 824} 825return tail; 826} 827 828/* 829 * Process one hunk from the patch between the current suspect for 830 * blame_entry e and its parent. This first blames any unfinished 831 * entries before the chunk (which is where target and parent start 832 * differing) on the parent, and then splits blame entries at the 833 * start and at the end of the difference region. Since use of -M and 834 * -C options may lead to overlapping/duplicate source line number 835 * ranges, all we can rely on from sorting/merging is the order of the 836 * first suspect line number. 837 */ 838static voidblame_chunk(struct blame_entry ***dstq,struct blame_entry ***srcq, 839int tlno,int offset,int same, 840struct origin *parent) 841{ 842struct blame_entry *e = **srcq; 843struct blame_entry *samep = NULL, *diffp = NULL; 844 845while(e && e->s_lno < tlno) { 846struct blame_entry *next = e->next; 847/* 848 * current record starts before differing portion. If 849 * it reaches into it, we need to split it up and 850 * examine the second part separately. 851 */ 852if(e->s_lno + e->num_lines > tlno) { 853/* Move second half to a new record */ 854int len = tlno - e->s_lno; 855struct blame_entry *n =xcalloc(1,sizeof(struct blame_entry)); 856 n->suspect = e->suspect; 857 n->lno = e->lno + len; 858 n->s_lno = e->s_lno + len; 859 n->num_lines = e->num_lines - len; 860 e->num_lines = len; 861 e->score =0; 862/* Push new record to diffp */ 863 n->next = diffp; 864 diffp = n; 865}else 866origin_decref(e->suspect); 867/* Pass blame for everything before the differing 868 * chunk to the parent */ 869 e->suspect =origin_incref(parent); 870 e->s_lno += offset; 871 e->next = samep; 872 samep = e; 873 e = next; 874} 875/* 876 * As we don't know how much of a common stretch after this 877 * diff will occur, the currently blamed parts are all that we 878 * can assign to the parent for now. 879 */ 880 881if(samep) { 882**dstq =reverse_blame(samep, **dstq); 883*dstq = &samep->next; 884} 885/* 886 * Prepend the split off portions: everything after e starts 887 * after the blameable portion. 888 */ 889 e =reverse_blame(diffp, e); 890 891/* 892 * Now retain records on the target while parts are different 893 * from the parent. 894 */ 895 samep = NULL; 896 diffp = NULL; 897while(e && e->s_lno < same) { 898struct blame_entry *next = e->next; 899 900/* 901 * If current record extends into sameness, need to split. 902 */ 903if(e->s_lno + e->num_lines > same) { 904/* 905 * Move second half to a new record to be 906 * processed by later chunks 907 */ 908int len = same - e->s_lno; 909struct blame_entry *n =xcalloc(1,sizeof(struct blame_entry)); 910 n->suspect =origin_incref(e->suspect); 911 n->lno = e->lno + len; 912 n->s_lno = e->s_lno + len; 913 n->num_lines = e->num_lines - len; 914 e->num_lines = len; 915 e->score =0; 916/* Push new record to samep */ 917 n->next = samep; 918 samep = n; 919} 920 e->next = diffp; 921 diffp = e; 922 e = next; 923} 924**srcq =reverse_blame(diffp,reverse_blame(samep, e)); 925/* Move across elements that are in the unblamable portion */ 926if(diffp) 927*srcq = &diffp->next; 928} 929 930struct blame_chunk_cb_data { 931struct origin *parent; 932long offset; 933struct blame_entry **dstq; 934struct blame_entry **srcq; 935}; 936 937/* diff chunks are from parent to target */ 938static intblame_chunk_cb(long start_a,long count_a, 939long start_b,long count_b,void*data) 940{ 941struct blame_chunk_cb_data *d = data; 942if(start_a - start_b != d->offset) 943die("internal error in blame::blame_chunk_cb"); 944blame_chunk(&d->dstq, &d->srcq, start_b, start_a - start_b, 945 start_b + count_b, d->parent); 946 d->offset = start_a + count_a - (start_b + count_b); 947return0; 948} 949 950/* 951 * We are looking at the origin 'target' and aiming to pass blame 952 * for the lines it is suspected to its parent. Run diff to find 953 * which lines came from parent and pass blame for them. 954 */ 955static voidpass_blame_to_parent(struct scoreboard *sb, 956struct origin *target, 957struct origin *parent) 958{ 959 mmfile_t file_p, file_o; 960struct blame_chunk_cb_data d; 961struct blame_entry *newdest = NULL; 962 963if(!target->suspects) 964return;/* nothing remains for this target */ 965 966 d.parent = parent; 967 d.offset =0; 968 d.dstq = &newdest; d.srcq = &target->suspects; 969 970fill_origin_blob(&sb->revs->diffopt, parent, &file_p); 971fill_origin_blob(&sb->revs->diffopt, target, &file_o); 972 num_get_patch++; 973 974if(diff_hunks(&file_p, &file_o, blame_chunk_cb, &d)) 975die("unable to generate diff (%s->%s)", 976oid_to_hex(&parent->commit->object.oid), 977oid_to_hex(&target->commit->object.oid)); 978/* The rest are the same as the parent */ 979blame_chunk(&d.dstq, &d.srcq, INT_MAX, d.offset, INT_MAX, parent); 980*d.dstq = NULL; 981queue_blames(sb, parent, newdest); 982 983return; 984} 985 986/* 987 * The lines in blame_entry after splitting blames many times can become 988 * very small and trivial, and at some point it becomes pointless to 989 * blame the parents. E.g. "\t\t}\n\t}\n\n" appears everywhere in any 990 * ordinary C program, and it is not worth to say it was copied from 991 * totally unrelated file in the parent. 992 * 993 * Compute how trivial the lines in the blame_entry are. 994 */ 995static unsignedent_score(struct scoreboard *sb,struct blame_entry *e) 996{ 997unsigned score; 998const char*cp, *ep; 9991000if(e->score)1001return e->score;10021003 score =1;1004 cp =nth_line(sb, e->lno);1005 ep =nth_line(sb, e->lno + e->num_lines);1006while(cp < ep) {1007unsigned ch = *((unsigned char*)cp);1008if(isalnum(ch))1009 score++;1010 cp++;1011}1012 e->score = score;1013return score;1014}10151016/*1017 * best_so_far[] and this[] are both a split of an existing blame_entry1018 * that passes blame to the parent. Maintain best_so_far the best split1019 * so far, by comparing this and best_so_far and copying this into1020 * bst_so_far as needed.1021 */1022static voidcopy_split_if_better(struct scoreboard *sb,1023struct blame_entry *best_so_far,1024struct blame_entry *this)1025{1026int i;10271028if(!this[1].suspect)1029return;1030if(best_so_far[1].suspect) {1031if(ent_score(sb, &this[1]) <ent_score(sb, &best_so_far[1]))1032return;1033}10341035for(i =0; i <3; i++)1036origin_incref(this[i].suspect);1037decref_split(best_so_far);1038memcpy(best_so_far,this,sizeof(struct blame_entry [3]));1039}10401041/*1042 * We are looking at a part of the final image represented by1043 * ent (tlno and same are offset by ent->s_lno).1044 * tlno is where we are looking at in the final image.1045 * up to (but not including) same match preimage.1046 * plno is where we are looking at in the preimage.1047 *1048 * <-------------- final image ---------------------->1049 * <------ent------>1050 * ^tlno ^same1051 * <---------preimage----->1052 * ^plno1053 *1054 * All line numbers are 0-based.1055 */1056static voidhandle_split(struct scoreboard *sb,1057struct blame_entry *ent,1058int tlno,int plno,int same,1059struct origin *parent,1060struct blame_entry *split)1061{1062if(ent->num_lines <= tlno)1063return;1064if(tlno < same) {1065struct blame_entry this[3];1066 tlno += ent->s_lno;1067 same += ent->s_lno;1068split_overlap(this, ent, tlno, plno, same, parent);1069copy_split_if_better(sb, split,this);1070decref_split(this);1071}1072}10731074struct handle_split_cb_data {1075struct scoreboard *sb;1076struct blame_entry *ent;1077struct origin *parent;1078struct blame_entry *split;1079long plno;1080long tlno;1081};10821083static inthandle_split_cb(long start_a,long count_a,1084long start_b,long count_b,void*data)1085{1086struct handle_split_cb_data *d = data;1087handle_split(d->sb, d->ent, d->tlno, d->plno, start_b, d->parent,1088 d->split);1089 d->plno = start_a + count_a;1090 d->tlno = start_b + count_b;1091return0;1092}10931094/*1095 * Find the lines from parent that are the same as ent so that1096 * we can pass blames to it. file_p has the blob contents for1097 * the parent.1098 */1099static voidfind_copy_in_blob(struct scoreboard *sb,1100struct blame_entry *ent,1101struct origin *parent,1102struct blame_entry *split,1103 mmfile_t *file_p)1104{1105const char*cp;1106 mmfile_t file_o;1107struct handle_split_cb_data d;11081109memset(&d,0,sizeof(d));1110 d.sb = sb; d.ent = ent; d.parent = parent; d.split = split;1111/*1112 * Prepare mmfile that contains only the lines in ent.1113 */1114 cp =nth_line(sb, ent->lno);1115 file_o.ptr = (char*) cp;1116 file_o.size =nth_line(sb, ent->lno + ent->num_lines) - cp;11171118/*1119 * file_o is a part of final image we are annotating.1120 * file_p partially may match that image.1121 */1122memset(split,0,sizeof(struct blame_entry [3]));1123if(diff_hunks(file_p, &file_o, handle_split_cb, &d))1124die("unable to generate diff (%s)",1125oid_to_hex(&parent->commit->object.oid));1126/* remainder, if any, all match the preimage */1127handle_split(sb, ent, d.tlno, d.plno, ent->num_lines, parent, split);1128}11291130/* Move all blame entries from list *source that have a score smaller1131 * than score_min to the front of list *small.1132 * Returns a pointer to the link pointing to the old head of the small list.1133 */11341135static struct blame_entry **filter_small(struct scoreboard *sb,1136struct blame_entry **small,1137struct blame_entry **source,1138unsigned score_min)1139{1140struct blame_entry *p = *source;1141struct blame_entry *oldsmall = *small;1142while(p) {1143if(ent_score(sb, p) <= score_min) {1144*small = p;1145 small = &p->next;1146 p = *small;1147}else{1148*source = p;1149 source = &p->next;1150 p = *source;1151}1152}1153*small = oldsmall;1154*source = NULL;1155return small;1156}11571158/*1159 * See if lines currently target is suspected for can be attributed to1160 * parent.1161 */1162static voidfind_move_in_parent(struct scoreboard *sb,1163struct blame_entry ***blamed,1164struct blame_entry **toosmall,1165struct origin *target,1166struct origin *parent)1167{1168struct blame_entry *e, split[3];1169struct blame_entry *unblamed = target->suspects;1170struct blame_entry *leftover = NULL;1171 mmfile_t file_p;11721173if(!unblamed)1174return;/* nothing remains for this target */11751176fill_origin_blob(&sb->revs->diffopt, parent, &file_p);1177if(!file_p.ptr)1178return;11791180/* At each iteration, unblamed has a NULL-terminated list of1181 * entries that have not yet been tested for blame. leftover1182 * contains the reversed list of entries that have been tested1183 * without being assignable to the parent.1184 */1185do{1186struct blame_entry **unblamedtail = &unblamed;1187struct blame_entry *next;1188for(e = unblamed; e; e = next) {1189 next = e->next;1190find_copy_in_blob(sb, e, parent, split, &file_p);1191if(split[1].suspect &&1192 blame_move_score <ent_score(sb, &split[1])) {1193split_blame(blamed, &unblamedtail, split, e);1194}else{1195 e->next = leftover;1196 leftover = e;1197}1198decref_split(split);1199}1200*unblamedtail = NULL;1201 toosmall =filter_small(sb, toosmall, &unblamed, blame_move_score);1202}while(unblamed);1203 target->suspects =reverse_blame(leftover, NULL);1204}12051206struct blame_list {1207struct blame_entry *ent;1208struct blame_entry split[3];1209};12101211/*1212 * Count the number of entries the target is suspected for,1213 * and prepare a list of entry and the best split.1214 */1215static struct blame_list *setup_blame_list(struct blame_entry *unblamed,1216int*num_ents_p)1217{1218struct blame_entry *e;1219int num_ents, i;1220struct blame_list *blame_list = NULL;12211222for(e = unblamed, num_ents =0; e; e = e->next)1223 num_ents++;1224if(num_ents) {1225 blame_list =xcalloc(num_ents,sizeof(struct blame_list));1226for(e = unblamed, i =0; e; e = e->next)1227 blame_list[i++].ent = e;1228}1229*num_ents_p = num_ents;1230return blame_list;1231}12321233/*1234 * For lines target is suspected for, see if we can find code movement1235 * across file boundary from the parent commit. porigin is the path1236 * in the parent we already tried.1237 */1238static voidfind_copy_in_parent(struct scoreboard *sb,1239struct blame_entry ***blamed,1240struct blame_entry **toosmall,1241struct origin *target,1242struct commit *parent,1243struct origin *porigin,1244int opt)1245{1246struct diff_options diff_opts;1247int i, j;1248struct blame_list *blame_list;1249int num_ents;1250struct blame_entry *unblamed = target->suspects;1251struct blame_entry *leftover = NULL;12521253if(!unblamed)1254return;/* nothing remains for this target */12551256diff_setup(&diff_opts);1257DIFF_OPT_SET(&diff_opts, RECURSIVE);1258 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;12591260diff_setup_done(&diff_opts);12611262/* Try "find copies harder" on new path if requested;1263 * we do not want to use diffcore_rename() actually to1264 * match things up; find_copies_harder is set only to1265 * force diff_tree_sha1() to feed all filepairs to diff_queue,1266 * and this code needs to be after diff_setup_done(), which1267 * usually makes find-copies-harder imply copy detection.1268 */1269if((opt & PICKAXE_BLAME_COPY_HARDEST)1270|| ((opt & PICKAXE_BLAME_COPY_HARDER)1271&& (!porigin ||strcmp(target->path, porigin->path))))1272DIFF_OPT_SET(&diff_opts, FIND_COPIES_HARDER);12731274if(is_null_oid(&target->commit->object.oid))1275do_diff_cache(parent->tree->object.oid.hash, &diff_opts);1276else1277diff_tree_sha1(parent->tree->object.oid.hash,1278 target->commit->tree->object.oid.hash,1279"", &diff_opts);12801281if(!DIFF_OPT_TST(&diff_opts, FIND_COPIES_HARDER))1282diffcore_std(&diff_opts);12831284do{1285struct blame_entry **unblamedtail = &unblamed;1286 blame_list =setup_blame_list(unblamed, &num_ents);12871288for(i =0; i < diff_queued_diff.nr; i++) {1289struct diff_filepair *p = diff_queued_diff.queue[i];1290struct origin *norigin;1291 mmfile_t file_p;1292struct blame_entry this[3];12931294if(!DIFF_FILE_VALID(p->one))1295continue;/* does not exist in parent */1296if(S_ISGITLINK(p->one->mode))1297continue;/* ignore git links */1298if(porigin && !strcmp(p->one->path, porigin->path))1299/* find_move already dealt with this path */1300continue;13011302 norigin =get_origin(sb, parent, p->one->path);1303oidcpy(&norigin->blob_oid, &p->one->oid);1304 norigin->mode = p->one->mode;1305fill_origin_blob(&sb->revs->diffopt, norigin, &file_p);1306if(!file_p.ptr)1307continue;13081309for(j =0; j < num_ents; j++) {1310find_copy_in_blob(sb, blame_list[j].ent,1311 norigin,this, &file_p);1312copy_split_if_better(sb, blame_list[j].split,1313this);1314decref_split(this);1315}1316origin_decref(norigin);1317}13181319for(j =0; j < num_ents; j++) {1320struct blame_entry *split = blame_list[j].split;1321if(split[1].suspect &&1322 blame_copy_score <ent_score(sb, &split[1])) {1323split_blame(blamed, &unblamedtail, split,1324 blame_list[j].ent);1325}else{1326 blame_list[j].ent->next = leftover;1327 leftover = blame_list[j].ent;1328}1329decref_split(split);1330}1331free(blame_list);1332*unblamedtail = NULL;1333 toosmall =filter_small(sb, toosmall, &unblamed, blame_copy_score);1334}while(unblamed);1335 target->suspects =reverse_blame(leftover, NULL);1336diff_flush(&diff_opts);1337clear_pathspec(&diff_opts.pathspec);1338}13391340/*1341 * The blobs of origin and porigin exactly match, so everything1342 * origin is suspected for can be blamed on the parent.1343 */1344static voidpass_whole_blame(struct scoreboard *sb,1345struct origin *origin,struct origin *porigin)1346{1347struct blame_entry *e, *suspects;13481349if(!porigin->file.ptr && origin->file.ptr) {1350/* Steal its file */1351 porigin->file = origin->file;1352 origin->file.ptr = NULL;1353}1354 suspects = origin->suspects;1355 origin->suspects = NULL;1356for(e = suspects; e; e = e->next) {1357origin_incref(porigin);1358origin_decref(e->suspect);1359 e->suspect = porigin;1360}1361queue_blames(sb, porigin, suspects);1362}13631364/*1365 * We pass blame from the current commit to its parents. We keep saying1366 * "parent" (and "porigin"), but what we mean is to find scapegoat to1367 * exonerate ourselves.1368 */1369static struct commit_list *first_scapegoat(struct rev_info *revs,struct commit *commit)1370{1371if(!reverse) {1372if(revs->first_parent_only &&1373 commit->parents &&1374 commit->parents->next) {1375free_commit_list(commit->parents->next);1376 commit->parents->next = NULL;1377}1378return commit->parents;1379}1380returnlookup_decoration(&revs->children, &commit->object);1381}13821383static intnum_scapegoats(struct rev_info *revs,struct commit *commit)1384{1385struct commit_list *l =first_scapegoat(revs, commit);1386returncommit_list_count(l);1387}13881389/* Distribute collected unsorted blames to the respected sorted lists1390 * in the various origins.1391 */1392static voiddistribute_blame(struct scoreboard *sb,struct blame_entry *blamed)1393{1394 blamed =blame_sort(blamed, compare_blame_suspect);1395while(blamed)1396{1397struct origin *porigin = blamed->suspect;1398struct blame_entry *suspects = NULL;1399do{1400struct blame_entry *next = blamed->next;1401 blamed->next = suspects;1402 suspects = blamed;1403 blamed = next;1404}while(blamed && blamed->suspect == porigin);1405 suspects =reverse_blame(suspects, NULL);1406queue_blames(sb, porigin, suspects);1407}1408}14091410#define MAXSG 1614111412static voidpass_blame(struct scoreboard *sb,struct origin *origin,int opt)1413{1414struct rev_info *revs = sb->revs;1415int i, pass, num_sg;1416struct commit *commit = origin->commit;1417struct commit_list *sg;1418struct origin *sg_buf[MAXSG];1419struct origin *porigin, **sg_origin = sg_buf;1420struct blame_entry *toosmall = NULL;1421struct blame_entry *blames, **blametail = &blames;14221423 num_sg =num_scapegoats(revs, commit);1424if(!num_sg)1425goto finish;1426else if(num_sg <ARRAY_SIZE(sg_buf))1427memset(sg_buf,0,sizeof(sg_buf));1428else1429 sg_origin =xcalloc(num_sg,sizeof(*sg_origin));14301431/*1432 * The first pass looks for unrenamed path to optimize for1433 * common cases, then we look for renames in the second pass.1434 */1435for(pass =0; pass <2- no_whole_file_rename; pass++) {1436struct origin *(*find)(struct scoreboard *,1437struct commit *,struct origin *);1438 find = pass ? find_rename : find_origin;14391440for(i =0, sg =first_scapegoat(revs, commit);1441 i < num_sg && sg;1442 sg = sg->next, i++) {1443struct commit *p = sg->item;1444int j, same;14451446if(sg_origin[i])1447continue;1448if(parse_commit(p))1449continue;1450 porigin =find(sb, p, origin);1451if(!porigin)1452continue;1453if(!oidcmp(&porigin->blob_oid, &origin->blob_oid)) {1454pass_whole_blame(sb, origin, porigin);1455origin_decref(porigin);1456goto finish;1457}1458for(j = same =0; j < i; j++)1459if(sg_origin[j] &&1460!oidcmp(&sg_origin[j]->blob_oid, &porigin->blob_oid)) {1461 same =1;1462break;1463}1464if(!same)1465 sg_origin[i] = porigin;1466else1467origin_decref(porigin);1468}1469}14701471 num_commits++;1472for(i =0, sg =first_scapegoat(revs, commit);1473 i < num_sg && sg;1474 sg = sg->next, i++) {1475struct origin *porigin = sg_origin[i];1476if(!porigin)1477continue;1478if(!origin->previous) {1479origin_incref(porigin);1480 origin->previous = porigin;1481}1482pass_blame_to_parent(sb, origin, porigin);1483if(!origin->suspects)1484goto finish;1485}14861487/*1488 * Optionally find moves in parents' files.1489 */1490if(opt & PICKAXE_BLAME_MOVE) {1491filter_small(sb, &toosmall, &origin->suspects, blame_move_score);1492if(origin->suspects) {1493for(i =0, sg =first_scapegoat(revs, commit);1494 i < num_sg && sg;1495 sg = sg->next, i++) {1496struct origin *porigin = sg_origin[i];1497if(!porigin)1498continue;1499find_move_in_parent(sb, &blametail, &toosmall, origin, porigin);1500if(!origin->suspects)1501break;1502}1503}1504}15051506/*1507 * Optionally find copies from parents' files.1508 */1509if(opt & PICKAXE_BLAME_COPY) {1510if(blame_copy_score > blame_move_score)1511filter_small(sb, &toosmall, &origin->suspects, blame_copy_score);1512else if(blame_copy_score < blame_move_score) {1513 origin->suspects =blame_merge(origin->suspects, toosmall);1514 toosmall = NULL;1515filter_small(sb, &toosmall, &origin->suspects, blame_copy_score);1516}1517if(!origin->suspects)1518goto finish;15191520for(i =0, sg =first_scapegoat(revs, commit);1521 i < num_sg && sg;1522 sg = sg->next, i++) {1523struct origin *porigin = sg_origin[i];1524find_copy_in_parent(sb, &blametail, &toosmall,1525 origin, sg->item, porigin, opt);1526if(!origin->suspects)1527goto finish;1528}1529}15301531finish:1532*blametail = NULL;1533distribute_blame(sb, blames);1534/*1535 * prepend toosmall to origin->suspects1536 *1537 * There is no point in sorting: this ends up on a big1538 * unsorted list in the caller anyway.1539 */1540if(toosmall) {1541struct blame_entry **tail = &toosmall;1542while(*tail)1543 tail = &(*tail)->next;1544*tail = origin->suspects;1545 origin->suspects = toosmall;1546}1547for(i =0; i < num_sg; i++) {1548if(sg_origin[i]) {1549drop_origin_blob(sg_origin[i]);1550origin_decref(sg_origin[i]);1551}1552}1553drop_origin_blob(origin);1554if(sg_buf != sg_origin)1555free(sg_origin);1556}15571558/*1559 * Information on commits, used for output.1560 */1561struct commit_info {1562struct strbuf author;1563struct strbuf author_mail;1564unsigned long author_time;1565struct strbuf author_tz;15661567/* filled only when asked for details */1568struct strbuf committer;1569struct strbuf committer_mail;1570unsigned long committer_time;1571struct strbuf committer_tz;15721573struct strbuf summary;1574};15751576/*1577 * Parse author/committer line in the commit object buffer1578 */1579static voidget_ac_line(const char*inbuf,const char*what,1580struct strbuf *name,struct strbuf *mail,1581unsigned long*time,struct strbuf *tz)1582{1583struct ident_split ident;1584size_t len, maillen, namelen;1585char*tmp, *endp;1586const char*namebuf, *mailbuf;15871588 tmp =strstr(inbuf, what);1589if(!tmp)1590goto error_out;1591 tmp +=strlen(what);1592 endp =strchr(tmp,'\n');1593if(!endp)1594 len =strlen(tmp);1595else1596 len = endp - tmp;15971598if(split_ident_line(&ident, tmp, len)) {1599 error_out:1600/* Ugh */1601 tmp ="(unknown)";1602strbuf_addstr(name, tmp);1603strbuf_addstr(mail, tmp);1604strbuf_addstr(tz, tmp);1605*time =0;1606return;1607}16081609 namelen = ident.name_end - ident.name_begin;1610 namebuf = ident.name_begin;16111612 maillen = ident.mail_end - ident.mail_begin;1613 mailbuf = ident.mail_begin;16141615if(ident.date_begin && ident.date_end)1616*time =strtoul(ident.date_begin, NULL,10);1617else1618*time =0;16191620if(ident.tz_begin && ident.tz_end)1621strbuf_add(tz, ident.tz_begin, ident.tz_end - ident.tz_begin);1622else1623strbuf_addstr(tz,"(unknown)");16241625/*1626 * Now, convert both name and e-mail using mailmap1627 */1628map_user(&mailmap, &mailbuf, &maillen,1629&namebuf, &namelen);16301631strbuf_addf(mail,"<%.*s>", (int)maillen, mailbuf);1632strbuf_add(name, namebuf, namelen);1633}16341635static voidcommit_info_init(struct commit_info *ci)1636{16371638strbuf_init(&ci->author,0);1639strbuf_init(&ci->author_mail,0);1640strbuf_init(&ci->author_tz,0);1641strbuf_init(&ci->committer,0);1642strbuf_init(&ci->committer_mail,0);1643strbuf_init(&ci->committer_tz,0);1644strbuf_init(&ci->summary,0);1645}16461647static voidcommit_info_destroy(struct commit_info *ci)1648{16491650strbuf_release(&ci->author);1651strbuf_release(&ci->author_mail);1652strbuf_release(&ci->author_tz);1653strbuf_release(&ci->committer);1654strbuf_release(&ci->committer_mail);1655strbuf_release(&ci->committer_tz);1656strbuf_release(&ci->summary);1657}16581659static voidget_commit_info(struct commit *commit,1660struct commit_info *ret,1661int detailed)1662{1663int len;1664const char*subject, *encoding;1665const char*message;16661667commit_info_init(ret);16681669 encoding =get_log_output_encoding();1670 message =logmsg_reencode(commit, NULL, encoding);1671get_ac_line(message,"\nauthor ",1672&ret->author, &ret->author_mail,1673&ret->author_time, &ret->author_tz);16741675if(!detailed) {1676unuse_commit_buffer(commit, message);1677return;1678}16791680get_ac_line(message,"\ncommitter ",1681&ret->committer, &ret->committer_mail,1682&ret->committer_time, &ret->committer_tz);16831684 len =find_commit_subject(message, &subject);1685if(len)1686strbuf_add(&ret->summary, subject, len);1687else1688strbuf_addf(&ret->summary,"(%s)",oid_to_hex(&commit->object.oid));16891690unuse_commit_buffer(commit, message);1691}16921693/*1694 * Write out any suspect information which depends on the path. This must be1695 * handled separately from emit_one_suspect_detail(), because a given commit1696 * may have changes in multiple paths. So this needs to appear each time1697 * we mention a new group.1698 *1699 * To allow LF and other nonportable characters in pathnames,1700 * they are c-style quoted as needed.1701 */1702static voidwrite_filename_info(struct origin *suspect)1703{1704if(suspect->previous) {1705struct origin *prev = suspect->previous;1706printf("previous%s",oid_to_hex(&prev->commit->object.oid));1707write_name_quoted(prev->path, stdout,'\n');1708}1709printf("filename ");1710write_name_quoted(suspect->path, stdout,'\n');1711}17121713/*1714 * Porcelain/Incremental format wants to show a lot of details per1715 * commit. Instead of repeating this every line, emit it only once,1716 * the first time each commit appears in the output (unless the1717 * user has specifically asked for us to repeat).1718 */1719static intemit_one_suspect_detail(struct origin *suspect,int repeat)1720{1721struct commit_info ci;17221723if(!repeat && (suspect->commit->object.flags & METAINFO_SHOWN))1724return0;17251726 suspect->commit->object.flags |= METAINFO_SHOWN;1727get_commit_info(suspect->commit, &ci,1);1728printf("author%s\n", ci.author.buf);1729printf("author-mail%s\n", ci.author_mail.buf);1730printf("author-time%lu\n", ci.author_time);1731printf("author-tz%s\n", ci.author_tz.buf);1732printf("committer%s\n", ci.committer.buf);1733printf("committer-mail%s\n", ci.committer_mail.buf);1734printf("committer-time%lu\n", ci.committer_time);1735printf("committer-tz%s\n", ci.committer_tz.buf);1736printf("summary%s\n", ci.summary.buf);1737if(suspect->commit->object.flags & UNINTERESTING)1738printf("boundary\n");17391740commit_info_destroy(&ci);17411742return1;1743}17441745/*1746 * The blame_entry is found to be guilty for the range.1747 * Show it in incremental output.1748 */1749static voidfound_guilty_entry(struct blame_entry *ent,1750struct progress_info *pi)1751{1752if(incremental) {1753struct origin *suspect = ent->suspect;17541755printf("%s %d %d %d\n",1756oid_to_hex(&suspect->commit->object.oid),1757 ent->s_lno +1, ent->lno +1, ent->num_lines);1758emit_one_suspect_detail(suspect,0);1759write_filename_info(suspect);1760maybe_flush_or_die(stdout,"stdout");1761}1762 pi->blamed_lines += ent->num_lines;1763display_progress(pi->progress, pi->blamed_lines);1764}17651766/*1767 * The main loop -- while we have blobs with lines whose true origin1768 * is still unknown, pick one blob, and allow its lines to pass blames1769 * to its parents. */1770static voidassign_blame(struct scoreboard *sb,int opt)1771{1772struct rev_info *revs = sb->revs;1773struct commit *commit =prio_queue_get(&sb->commits);1774struct progress_info pi = { NULL,0};17751776if(show_progress)1777 pi.progress =start_progress_delay(_("Blaming lines"),1778 sb->num_lines,50,1);17791780while(commit) {1781struct blame_entry *ent;1782struct origin *suspect = commit->util;17831784/* find one suspect to break down */1785while(suspect && !suspect->suspects)1786 suspect = suspect->next;17871788if(!suspect) {1789 commit =prio_queue_get(&sb->commits);1790continue;1791}17921793assert(commit == suspect->commit);17941795/*1796 * We will use this suspect later in the loop,1797 * so hold onto it in the meantime.1798 */1799origin_incref(suspect);1800parse_commit(commit);1801if(reverse ||1802(!(commit->object.flags & UNINTERESTING) &&1803!(revs->max_age != -1&& commit->date < revs->max_age)))1804pass_blame(sb, suspect, opt);1805else{1806 commit->object.flags |= UNINTERESTING;1807if(commit->object.parsed)1808mark_parents_uninteresting(commit);1809}1810/* treat root commit as boundary */1811if(!commit->parents && !show_root)1812 commit->object.flags |= UNINTERESTING;18131814/* Take responsibility for the remaining entries */1815 ent = suspect->suspects;1816if(ent) {1817 suspect->guilty =1;1818for(;;) {1819struct blame_entry *next = ent->next;1820found_guilty_entry(ent, &pi);1821if(next) {1822 ent = next;1823continue;1824}1825 ent->next = sb->ent;1826 sb->ent = suspect->suspects;1827 suspect->suspects = NULL;1828break;1829}1830}1831origin_decref(suspect);18321833if(DEBUG)/* sanity */1834sanity_check_refcnt(sb);1835}18361837stop_progress(&pi.progress);1838}18391840static const char*format_time(unsigned long time,const char*tz_str,1841int show_raw_time)1842{1843static struct strbuf time_buf = STRBUF_INIT;18441845strbuf_reset(&time_buf);1846if(show_raw_time) {1847strbuf_addf(&time_buf,"%lu%s", time, tz_str);1848}1849else{1850const char*time_str;1851size_t time_width;1852int tz;1853 tz =atoi(tz_str);1854 time_str =show_date(time, tz, &blame_date_mode);1855strbuf_addstr(&time_buf, time_str);1856/*1857 * Add space paddings to time_buf to display a fixed width1858 * string, and use time_width for display width calibration.1859 */1860for(time_width =utf8_strwidth(time_str);1861 time_width < blame_date_width;1862 time_width++)1863strbuf_addch(&time_buf,' ');1864}1865return time_buf.buf;1866}18671868#define OUTPUT_ANNOTATE_COMPAT 0011869#define OUTPUT_LONG_OBJECT_NAME 0021870#define OUTPUT_RAW_TIMESTAMP 0041871#define OUTPUT_PORCELAIN 0101872#define OUTPUT_SHOW_NAME 0201873#define OUTPUT_SHOW_NUMBER 0401874#define OUTPUT_SHOW_SCORE 01001875#define OUTPUT_NO_AUTHOR 02001876#define OUTPUT_SHOW_EMAIL 04001877#define OUTPUT_LINE_PORCELAIN 0100018781879static voidemit_porcelain_details(struct origin *suspect,int repeat)1880{1881if(emit_one_suspect_detail(suspect, repeat) ||1882(suspect->commit->object.flags & MORE_THAN_ONE_PATH))1883write_filename_info(suspect);1884}18851886static voidemit_porcelain(struct scoreboard *sb,struct blame_entry *ent,1887int opt)1888{1889int repeat = opt & OUTPUT_LINE_PORCELAIN;1890int cnt;1891const char*cp;1892struct origin *suspect = ent->suspect;1893char hex[GIT_MAX_HEXSZ +1];18941895oid_to_hex_r(hex, &suspect->commit->object.oid);1896printf("%s %d %d %d\n",1897 hex,1898 ent->s_lno +1,1899 ent->lno +1,1900 ent->num_lines);1901emit_porcelain_details(suspect, repeat);19021903 cp =nth_line(sb, ent->lno);1904for(cnt =0; cnt < ent->num_lines; cnt++) {1905char ch;1906if(cnt) {1907printf("%s %d %d\n", hex,1908 ent->s_lno +1+ cnt,1909 ent->lno +1+ cnt);1910if(repeat)1911emit_porcelain_details(suspect,1);1912}1913putchar('\t');1914do{1915 ch = *cp++;1916putchar(ch);1917}while(ch !='\n'&&1918 cp < sb->final_buf + sb->final_buf_size);1919}19201921if(sb->final_buf_size && cp[-1] !='\n')1922putchar('\n');1923}19241925static voidemit_other(struct scoreboard *sb,struct blame_entry *ent,int opt)1926{1927int cnt;1928const char*cp;1929struct origin *suspect = ent->suspect;1930struct commit_info ci;1931char hex[GIT_MAX_HEXSZ +1];1932int show_raw_time = !!(opt & OUTPUT_RAW_TIMESTAMP);19331934get_commit_info(suspect->commit, &ci,1);1935oid_to_hex_r(hex, &suspect->commit->object.oid);19361937 cp =nth_line(sb, ent->lno);1938for(cnt =0; cnt < ent->num_lines; cnt++) {1939char ch;1940int length = (opt & OUTPUT_LONG_OBJECT_NAME) ? GIT_SHA1_HEXSZ : abbrev;19411942if(suspect->commit->object.flags & UNINTERESTING) {1943if(blank_boundary)1944memset(hex,' ', length);1945else if(!(opt & OUTPUT_ANNOTATE_COMPAT)) {1946 length--;1947putchar('^');1948}1949}19501951printf("%.*s", length, hex);1952if(opt & OUTPUT_ANNOTATE_COMPAT) {1953const char*name;1954if(opt & OUTPUT_SHOW_EMAIL)1955 name = ci.author_mail.buf;1956else1957 name = ci.author.buf;1958printf("\t(%10s\t%10s\t%d)", name,1959format_time(ci.author_time, ci.author_tz.buf,1960 show_raw_time),1961 ent->lno +1+ cnt);1962}else{1963if(opt & OUTPUT_SHOW_SCORE)1964printf(" %*d%02d",1965 max_score_digits, ent->score,1966 ent->suspect->refcnt);1967if(opt & OUTPUT_SHOW_NAME)1968printf(" %-*.*s", longest_file, longest_file,1969 suspect->path);1970if(opt & OUTPUT_SHOW_NUMBER)1971printf(" %*d", max_orig_digits,1972 ent->s_lno +1+ cnt);19731974if(!(opt & OUTPUT_NO_AUTHOR)) {1975const char*name;1976int pad;1977if(opt & OUTPUT_SHOW_EMAIL)1978 name = ci.author_mail.buf;1979else1980 name = ci.author.buf;1981 pad = longest_author -utf8_strwidth(name);1982printf(" (%s%*s%10s",1983 name, pad,"",1984format_time(ci.author_time,1985 ci.author_tz.buf,1986 show_raw_time));1987}1988printf(" %*d) ",1989 max_digits, ent->lno +1+ cnt);1990}1991do{1992 ch = *cp++;1993putchar(ch);1994}while(ch !='\n'&&1995 cp < sb->final_buf + sb->final_buf_size);1996}19971998if(sb->final_buf_size && cp[-1] !='\n')1999putchar('\n');20002001commit_info_destroy(&ci);2002}20032004static voidoutput(struct scoreboard *sb,int option)2005{2006struct blame_entry *ent;20072008if(option & OUTPUT_PORCELAIN) {2009for(ent = sb->ent; ent; ent = ent->next) {2010int count =0;2011struct origin *suspect;2012struct commit *commit = ent->suspect->commit;2013if(commit->object.flags & MORE_THAN_ONE_PATH)2014continue;2015for(suspect = commit->util; suspect; suspect = suspect->next) {2016if(suspect->guilty && count++) {2017 commit->object.flags |= MORE_THAN_ONE_PATH;2018break;2019}2020}2021}2022}20232024for(ent = sb->ent; ent; ent = ent->next) {2025if(option & OUTPUT_PORCELAIN)2026emit_porcelain(sb, ent, option);2027else{2028emit_other(sb, ent, option);2029}2030}2031}20322033static const char*get_next_line(const char*start,const char*end)2034{2035const char*nl =memchr(start,'\n', end - start);2036return nl ? nl +1: end;2037}20382039/*2040 * To allow quick access to the contents of nth line in the2041 * final image, prepare an index in the scoreboard.2042 */2043static intprepare_lines(struct scoreboard *sb)2044{2045const char*buf = sb->final_buf;2046unsigned long len = sb->final_buf_size;2047const char*end = buf + len;2048const char*p;2049int*lineno;2050int num =0;20512052for(p = buf; p < end; p =get_next_line(p, end))2053 num++;20542055ALLOC_ARRAY(sb->lineno, num +1);2056 lineno = sb->lineno;20572058for(p = buf; p < end; p =get_next_line(p, end))2059*lineno++ = p - buf;20602061*lineno = len;20622063 sb->num_lines = num;2064return sb->num_lines;2065}20662067/*2068 * Add phony grafts for use with -S; this is primarily to2069 * support git's cvsserver that wants to give a linear history2070 * to its clients.2071 */2072static intread_ancestry(const char*graft_file)2073{2074FILE*fp =fopen(graft_file,"r");2075struct strbuf buf = STRBUF_INIT;2076if(!fp)2077return-1;2078while(!strbuf_getwholeline(&buf, fp,'\n')) {2079/* The format is just "Commit Parent1 Parent2 ...\n" */2080struct commit_graft *graft =read_graft_line(buf.buf, buf.len);2081if(graft)2082register_commit_graft(graft,0);2083}2084fclose(fp);2085strbuf_release(&buf);2086return0;2087}20882089static intupdate_auto_abbrev(int auto_abbrev,struct origin *suspect)2090{2091const char*uniq =find_unique_abbrev(suspect->commit->object.oid.hash,2092 auto_abbrev);2093int len =strlen(uniq);2094if(auto_abbrev < len)2095return len;2096return auto_abbrev;2097}20982099/*2100 * How many columns do we need to show line numbers, authors,2101 * and filenames?2102 */2103static voidfind_alignment(struct scoreboard *sb,int*option)2104{2105int longest_src_lines =0;2106int longest_dst_lines =0;2107unsigned largest_score =0;2108struct blame_entry *e;2109int compute_auto_abbrev = (abbrev <0);2110int auto_abbrev = DEFAULT_ABBREV;21112112for(e = sb->ent; e; e = e->next) {2113struct origin *suspect = e->suspect;2114int num;21152116if(compute_auto_abbrev)2117 auto_abbrev =update_auto_abbrev(auto_abbrev, suspect);2118if(strcmp(suspect->path, sb->path))2119*option |= OUTPUT_SHOW_NAME;2120 num =strlen(suspect->path);2121if(longest_file < num)2122 longest_file = num;2123if(!(suspect->commit->object.flags & METAINFO_SHOWN)) {2124struct commit_info ci;2125 suspect->commit->object.flags |= METAINFO_SHOWN;2126get_commit_info(suspect->commit, &ci,1);2127if(*option & OUTPUT_SHOW_EMAIL)2128 num =utf8_strwidth(ci.author_mail.buf);2129else2130 num =utf8_strwidth(ci.author.buf);2131if(longest_author < num)2132 longest_author = num;2133commit_info_destroy(&ci);2134}2135 num = e->s_lno + e->num_lines;2136if(longest_src_lines < num)2137 longest_src_lines = num;2138 num = e->lno + e->num_lines;2139if(longest_dst_lines < num)2140 longest_dst_lines = num;2141if(largest_score <ent_score(sb, e))2142 largest_score =ent_score(sb, e);2143}2144 max_orig_digits =decimal_width(longest_src_lines);2145 max_digits =decimal_width(longest_dst_lines);2146 max_score_digits =decimal_width(largest_score);21472148if(compute_auto_abbrev)2149/* one more abbrev length is needed for the boundary commit */2150 abbrev = auto_abbrev +1;2151}21522153/*2154 * For debugging -- origin is refcounted, and this asserts that2155 * we do not underflow.2156 */2157static voidsanity_check_refcnt(struct scoreboard *sb)2158{2159int baa =0;2160struct blame_entry *ent;21612162for(ent = sb->ent; ent; ent = ent->next) {2163/* Nobody should have zero or negative refcnt */2164if(ent->suspect->refcnt <=0) {2165fprintf(stderr,"%sin%shas negative refcnt%d\n",2166 ent->suspect->path,2167oid_to_hex(&ent->suspect->commit->object.oid),2168 ent->suspect->refcnt);2169 baa =1;2170}2171}2172if(baa) {2173int opt =0160;2174find_alignment(sb, &opt);2175output(sb, opt);2176die("Baa%d!", baa);2177}2178}21792180static unsignedparse_score(const char*arg)2181{2182char*end;2183unsigned long score =strtoul(arg, &end,10);2184if(*end)2185return0;2186return score;2187}21882189static const char*add_prefix(const char*prefix,const char*path)2190{2191returnprefix_path(prefix, prefix ?strlen(prefix) :0, path);2192}21932194static intgit_blame_config(const char*var,const char*value,void*cb)2195{2196if(!strcmp(var,"blame.showroot")) {2197 show_root =git_config_bool(var, value);2198return0;2199}2200if(!strcmp(var,"blame.blankboundary")) {2201 blank_boundary =git_config_bool(var, value);2202return0;2203}2204if(!strcmp(var,"blame.showemail")) {2205int*output_option = cb;2206if(git_config_bool(var, value))2207*output_option |= OUTPUT_SHOW_EMAIL;2208else2209*output_option &= ~OUTPUT_SHOW_EMAIL;2210return0;2211}2212if(!strcmp(var,"blame.date")) {2213if(!value)2214returnconfig_error_nonbool(var);2215parse_date_format(value, &blame_date_mode);2216return0;2217}22182219if(git_diff_heuristic_config(var, value, cb) <0)2220return-1;2221if(userdiff_config(var, value) <0)2222return-1;22232224returngit_default_config(var, value, cb);2225}22262227static voidverify_working_tree_path(struct commit *work_tree,const char*path)2228{2229struct commit_list *parents;2230int pos;22312232for(parents = work_tree->parents; parents; parents = parents->next) {2233const struct object_id *commit_oid = &parents->item->object.oid;2234struct object_id blob_oid;2235unsigned mode;22362237if(!get_tree_entry(commit_oid->hash, path, blob_oid.hash, &mode) &&2238sha1_object_info(blob_oid.hash, NULL) == OBJ_BLOB)2239return;2240}22412242 pos =cache_name_pos(path,strlen(path));2243if(pos >=0)2244;/* path is in the index */2245else if(-1- pos < active_nr &&2246!strcmp(active_cache[-1- pos]->name, path))2247;/* path is in the index, unmerged */2248else2249die("no such path '%s' in HEAD", path);2250}22512252static struct commit_list **append_parent(struct commit_list **tail,const struct object_id *oid)2253{2254struct commit *parent;22552256 parent =lookup_commit_reference(oid->hash);2257if(!parent)2258die("no such commit%s",oid_to_hex(oid));2259return&commit_list_insert(parent, tail)->next;2260}22612262static voidappend_merge_parents(struct commit_list **tail)2263{2264int merge_head;2265struct strbuf line = STRBUF_INIT;22662267 merge_head =open(git_path_merge_head(), O_RDONLY);2268if(merge_head <0) {2269if(errno == ENOENT)2270return;2271die("cannot open '%s' for reading",git_path_merge_head());2272}22732274while(!strbuf_getwholeline_fd(&line, merge_head,'\n')) {2275struct object_id oid;2276if(line.len < GIT_SHA1_HEXSZ ||get_oid_hex(line.buf, &oid))2277die("unknown line in '%s':%s",git_path_merge_head(), line.buf);2278 tail =append_parent(tail, &oid);2279}2280close(merge_head);2281strbuf_release(&line);2282}22832284/*2285 * This isn't as simple as passing sb->buf and sb->len, because we2286 * want to transfer ownership of the buffer to the commit (so we2287 * must use detach).2288 */2289static voidset_commit_buffer_from_strbuf(struct commit *c,struct strbuf *sb)2290{2291size_t len;2292void*buf =strbuf_detach(sb, &len);2293set_commit_buffer(c, buf, len);2294}22952296/*2297 * Prepare a dummy commit that represents the work tree (or staged) item.2298 * Note that annotating work tree item never works in the reverse.2299 */2300static struct commit *fake_working_tree_commit(struct diff_options *opt,2301const char*path,2302const char*contents_from)2303{2304struct commit *commit;2305struct origin *origin;2306struct commit_list **parent_tail, *parent;2307struct object_id head_oid;2308struct strbuf buf = STRBUF_INIT;2309const char*ident;2310time_t now;2311int size, len;2312struct cache_entry *ce;2313unsigned mode;2314struct strbuf msg = STRBUF_INIT;23152316read_cache();2317time(&now);2318 commit =alloc_commit_node();2319 commit->object.parsed =1;2320 commit->date = now;2321 parent_tail = &commit->parents;23222323if(!resolve_ref_unsafe("HEAD", RESOLVE_REF_READING, head_oid.hash, NULL))2324die("no such ref: HEAD");23252326 parent_tail =append_parent(parent_tail, &head_oid);2327append_merge_parents(parent_tail);2328verify_working_tree_path(commit, path);23292330 origin =make_origin(commit, path);23312332 ident =fmt_ident("Not Committed Yet","not.committed.yet", NULL,0);2333strbuf_addstr(&msg,"tree 0000000000000000000000000000000000000000\n");2334for(parent = commit->parents; parent; parent = parent->next)2335strbuf_addf(&msg,"parent%s\n",2336oid_to_hex(&parent->item->object.oid));2337strbuf_addf(&msg,2338"author%s\n"2339"committer%s\n\n"2340"Version of%sfrom%s\n",2341 ident, ident, path,2342(!contents_from ? path :2343(!strcmp(contents_from,"-") ?"standard input": contents_from)));2344set_commit_buffer_from_strbuf(commit, &msg);23452346if(!contents_from ||strcmp("-", contents_from)) {2347struct stat st;2348const char*read_from;2349char*buf_ptr;2350unsigned long buf_len;23512352if(contents_from) {2353if(stat(contents_from, &st) <0)2354die_errno("Cannot stat '%s'", contents_from);2355 read_from = contents_from;2356}2357else{2358if(lstat(path, &st) <0)2359die_errno("Cannot lstat '%s'", path);2360 read_from = path;2361}2362 mode =canon_mode(st.st_mode);23632364switch(st.st_mode & S_IFMT) {2365case S_IFREG:2366if(DIFF_OPT_TST(opt, ALLOW_TEXTCONV) &&2367textconv_object(read_from, mode, &null_oid,0, &buf_ptr, &buf_len))2368strbuf_attach(&buf, buf_ptr, buf_len, buf_len +1);2369else if(strbuf_read_file(&buf, read_from, st.st_size) != st.st_size)2370die_errno("cannot open or read '%s'", read_from);2371break;2372case S_IFLNK:2373if(strbuf_readlink(&buf, read_from, st.st_size) <0)2374die_errno("cannot readlink '%s'", read_from);2375break;2376default:2377die("unsupported file type%s", read_from);2378}2379}2380else{2381/* Reading from stdin */2382 mode =0;2383if(strbuf_read(&buf,0,0) <0)2384die_errno("failed to read from stdin");2385}2386convert_to_git(path, buf.buf, buf.len, &buf,0);2387 origin->file.ptr = buf.buf;2388 origin->file.size = buf.len;2389pretend_sha1_file(buf.buf, buf.len, OBJ_BLOB, origin->blob_oid.hash);23902391/*2392 * Read the current index, replace the path entry with2393 * origin->blob_sha1 without mucking with its mode or type2394 * bits; we are not going to write this index out -- we just2395 * want to run "diff-index --cached".2396 */2397discard_cache();2398read_cache();23992400 len =strlen(path);2401if(!mode) {2402int pos =cache_name_pos(path, len);2403if(0<= pos)2404 mode = active_cache[pos]->ce_mode;2405else2406/* Let's not bother reading from HEAD tree */2407 mode = S_IFREG |0644;2408}2409 size =cache_entry_size(len);2410 ce =xcalloc(1, size);2411oidcpy(&ce->oid, &origin->blob_oid);2412memcpy(ce->name, path, len);2413 ce->ce_flags =create_ce_flags(0);2414 ce->ce_namelen = len;2415 ce->ce_mode =create_ce_mode(mode);2416add_cache_entry(ce, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE);24172418cache_tree_invalidate_path(&the_index, path);24192420return commit;2421}24222423static struct commit *find_single_final(struct rev_info *revs,2424const char**name_p)2425{2426int i;2427struct commit *found = NULL;2428const char*name = NULL;24292430for(i =0; i < revs->pending.nr; i++) {2431struct object *obj = revs->pending.objects[i].item;2432if(obj->flags & UNINTERESTING)2433continue;2434 obj =deref_tag(obj, NULL,0);2435if(obj->type != OBJ_COMMIT)2436die("Non commit%s?", revs->pending.objects[i].name);2437if(found)2438die("More than one commit to dig from%sand%s?",2439 revs->pending.objects[i].name, name);2440 found = (struct commit *)obj;2441 name = revs->pending.objects[i].name;2442}2443if(name_p)2444*name_p = name;2445return found;2446}24472448static char*prepare_final(struct scoreboard *sb)2449{2450const char*name;2451 sb->final =find_single_final(sb->revs, &name);2452returnxstrdup_or_null(name);2453}24542455static const char*dwim_reverse_initial(struct scoreboard *sb)2456{2457/*2458 * DWIM "git blame --reverse ONE -- PATH" as2459 * "git blame --reverse ONE..HEAD -- PATH" but only do so2460 * when it makes sense.2461 */2462struct object *obj;2463struct commit *head_commit;2464unsigned char head_sha1[20];24652466if(sb->revs->pending.nr !=1)2467return NULL;24682469/* Is that sole rev a committish? */2470 obj = sb->revs->pending.objects[0].item;2471 obj =deref_tag(obj, NULL,0);2472if(obj->type != OBJ_COMMIT)2473return NULL;24742475/* Do we have HEAD? */2476if(!resolve_ref_unsafe("HEAD", RESOLVE_REF_READING, head_sha1, NULL))2477return NULL;2478 head_commit =lookup_commit_reference_gently(head_sha1,1);2479if(!head_commit)2480return NULL;24812482/* Turn "ONE" into "ONE..HEAD" then */2483 obj->flags |= UNINTERESTING;2484add_pending_object(sb->revs, &head_commit->object,"HEAD");24852486 sb->final = (struct commit *)obj;2487return sb->revs->pending.objects[0].name;2488}24892490static char*prepare_initial(struct scoreboard *sb)2491{2492int i;2493const char*final_commit_name = NULL;2494struct rev_info *revs = sb->revs;24952496/*2497 * There must be one and only one negative commit, and it must be2498 * the boundary.2499 */2500for(i =0; i < revs->pending.nr; i++) {2501struct object *obj = revs->pending.objects[i].item;2502if(!(obj->flags & UNINTERESTING))2503continue;2504 obj =deref_tag(obj, NULL,0);2505if(obj->type != OBJ_COMMIT)2506die("Non commit%s?", revs->pending.objects[i].name);2507if(sb->final)2508die("More than one commit to dig up from,%sand%s?",2509 revs->pending.objects[i].name,2510 final_commit_name);2511 sb->final = (struct commit *) obj;2512 final_commit_name = revs->pending.objects[i].name;2513}25142515if(!final_commit_name)2516 final_commit_name =dwim_reverse_initial(sb);2517if(!final_commit_name)2518die("No commit to dig up from?");2519returnxstrdup(final_commit_name);2520}25212522static intblame_copy_callback(const struct option *option,const char*arg,int unset)2523{2524int*opt = option->value;25252526/*2527 * -C enables copy from removed files;2528 * -C -C enables copy from existing files, but only2529 * when blaming a new file;2530 * -C -C -C enables copy from existing files for2531 * everybody2532 */2533if(*opt & PICKAXE_BLAME_COPY_HARDER)2534*opt |= PICKAXE_BLAME_COPY_HARDEST;2535if(*opt & PICKAXE_BLAME_COPY)2536*opt |= PICKAXE_BLAME_COPY_HARDER;2537*opt |= PICKAXE_BLAME_COPY | PICKAXE_BLAME_MOVE;25382539if(arg)2540 blame_copy_score =parse_score(arg);2541return0;2542}25432544static intblame_move_callback(const struct option *option,const char*arg,int unset)2545{2546int*opt = option->value;25472548*opt |= PICKAXE_BLAME_MOVE;25492550if(arg)2551 blame_move_score =parse_score(arg);2552return0;2553}25542555intcmd_blame(int argc,const char**argv,const char*prefix)2556{2557struct rev_info revs;2558const char*path;2559struct scoreboard sb;2560struct origin *o;2561struct blame_entry *ent = NULL;2562long dashdash_pos, lno;2563char*final_commit_name = NULL;2564enum object_type type;2565struct commit *final_commit = NULL;25662567struct string_list range_list = STRING_LIST_INIT_NODUP;2568int output_option =0, opt =0;2569int show_stats =0;2570const char*revs_file = NULL;2571const char*contents_from = NULL;2572const struct option options[] = {2573OPT_BOOL(0,"incremental", &incremental,N_("Show blame entries as we find them, incrementally")),2574OPT_BOOL('b', NULL, &blank_boundary,N_("Show blank SHA-1 for boundary commits (Default: off)")),2575OPT_BOOL(0,"root", &show_root,N_("Do not treat root commits as boundaries (Default: off)")),2576OPT_BOOL(0,"show-stats", &show_stats,N_("Show work cost statistics")),2577OPT_BOOL(0,"progress", &show_progress,N_("Force progress reporting")),2578OPT_BIT(0,"score-debug", &output_option,N_("Show output score for blame entries"), OUTPUT_SHOW_SCORE),2579OPT_BIT('f',"show-name", &output_option,N_("Show original filename (Default: auto)"), OUTPUT_SHOW_NAME),2580OPT_BIT('n',"show-number", &output_option,N_("Show original linenumber (Default: off)"), OUTPUT_SHOW_NUMBER),2581OPT_BIT('p',"porcelain", &output_option,N_("Show in a format designed for machine consumption"), OUTPUT_PORCELAIN),2582OPT_BIT(0,"line-porcelain", &output_option,N_("Show porcelain format with per-line commit information"), OUTPUT_PORCELAIN|OUTPUT_LINE_PORCELAIN),2583OPT_BIT('c', NULL, &output_option,N_("Use the same output mode as git-annotate (Default: off)"), OUTPUT_ANNOTATE_COMPAT),2584OPT_BIT('t', NULL, &output_option,N_("Show raw timestamp (Default: off)"), OUTPUT_RAW_TIMESTAMP),2585OPT_BIT('l', NULL, &output_option,N_("Show long commit SHA1 (Default: off)"), OUTPUT_LONG_OBJECT_NAME),2586OPT_BIT('s', NULL, &output_option,N_("Suppress author name and timestamp (Default: off)"), OUTPUT_NO_AUTHOR),2587OPT_BIT('e',"show-email", &output_option,N_("Show author email instead of name (Default: off)"), OUTPUT_SHOW_EMAIL),2588OPT_BIT('w', NULL, &xdl_opts,N_("Ignore whitespace differences"), XDF_IGNORE_WHITESPACE),25892590/*2591 * The following two options are parsed by parse_revision_opt()2592 * and are only included here to get included in the "-h"2593 * output:2594 */2595{ OPTION_LOWLEVEL_CALLBACK,0,"indent-heuristic", NULL, NULL,N_("Use an experimental heuristic to improve diffs"), PARSE_OPT_NOARG, parse_opt_unknown_cb },25962597OPT_BIT(0,"minimal", &xdl_opts,N_("Spend extra cycles to find better match"), XDF_NEED_MINIMAL),2598OPT_STRING('S', NULL, &revs_file,N_("file"),N_("Use revisions from <file> instead of calling git-rev-list")),2599OPT_STRING(0,"contents", &contents_from,N_("file"),N_("Use <file>'s contents as the final image")),2600{ OPTION_CALLBACK,'C', NULL, &opt,N_("score"),N_("Find line copies within and across files"), PARSE_OPT_OPTARG, blame_copy_callback },2601{ OPTION_CALLBACK,'M', NULL, &opt,N_("score"),N_("Find line movements within and across files"), PARSE_OPT_OPTARG, blame_move_callback },2602OPT_STRING_LIST('L', NULL, &range_list,N_("n,m"),N_("Process only line range n,m, counting from 1")),2603OPT__ABBREV(&abbrev),2604OPT_END()2605};26062607struct parse_opt_ctx_t ctx;2608int cmd_is_annotate = !strcmp(argv[0],"annotate");2609struct range_set ranges;2610unsigned int range_i;2611long anchor;26122613git_config(git_blame_config, &output_option);2614init_revisions(&revs, NULL);2615 revs.date_mode = blame_date_mode;2616DIFF_OPT_SET(&revs.diffopt, ALLOW_TEXTCONV);2617DIFF_OPT_SET(&revs.diffopt, FOLLOW_RENAMES);26182619 save_commit_buffer =0;2620 dashdash_pos =0;2621 show_progress = -1;26222623parse_options_start(&ctx, argc, argv, prefix, options,2624 PARSE_OPT_KEEP_DASHDASH | PARSE_OPT_KEEP_ARGV0);2625for(;;) {2626switch(parse_options_step(&ctx, options, blame_opt_usage)) {2627case PARSE_OPT_HELP:2628exit(129);2629case PARSE_OPT_DONE:2630if(ctx.argv[0])2631 dashdash_pos = ctx.cpidx;2632goto parse_done;2633}26342635if(!strcmp(ctx.argv[0],"--reverse")) {2636 ctx.argv[0] ="--children";2637 reverse =1;2638}2639parse_revision_opt(&revs, &ctx, options, blame_opt_usage);2640}2641parse_done:2642 no_whole_file_rename = !DIFF_OPT_TST(&revs.diffopt, FOLLOW_RENAMES);2643 xdl_opts |= revs.diffopt.xdl_opts & XDF_INDENT_HEURISTIC;2644DIFF_OPT_CLR(&revs.diffopt, FOLLOW_RENAMES);2645 argc =parse_options_end(&ctx);26462647if(incremental || (output_option & OUTPUT_PORCELAIN)) {2648if(show_progress >0)2649die(_("--progress can't be used with --incremental or porcelain formats"));2650 show_progress =0;2651}else if(show_progress <0)2652 show_progress =isatty(2);26532654if(0< abbrev && abbrev < GIT_SHA1_HEXSZ)2655/* one more abbrev length is needed for the boundary commit */2656 abbrev++;2657else if(!abbrev)2658 abbrev = GIT_SHA1_HEXSZ;26592660if(revs_file &&read_ancestry(revs_file))2661die_errno("reading graft file '%s' failed", revs_file);26622663if(cmd_is_annotate) {2664 output_option |= OUTPUT_ANNOTATE_COMPAT;2665 blame_date_mode.type = DATE_ISO8601;2666}else{2667 blame_date_mode = revs.date_mode;2668}26692670/* The maximum width used to show the dates */2671switch(blame_date_mode.type) {2672case DATE_RFC2822:2673 blame_date_width =sizeof("Thu, 19 Oct 2006 16:00:04 -0700");2674break;2675case DATE_ISO8601_STRICT:2676 blame_date_width =sizeof("2006-10-19T16:00:04-07:00");2677break;2678case DATE_ISO8601:2679 blame_date_width =sizeof("2006-10-19 16:00:04 -0700");2680break;2681case DATE_RAW:2682 blame_date_width =sizeof("1161298804 -0700");2683break;2684case DATE_UNIX:2685 blame_date_width =sizeof("1161298804");2686break;2687case DATE_SHORT:2688 blame_date_width =sizeof("2006-10-19");2689break;2690case DATE_RELATIVE:2691/* TRANSLATORS: This string is used to tell us the maximum2692 display width for a relative timestamp in "git blame"2693 output. For C locale, "4 years, 11 months ago", which2694 takes 22 places, is the longest among various forms of2695 relative timestamps, but your language may need more or2696 fewer display columns. */2697 blame_date_width =utf8_strwidth(_("4 years, 11 months ago")) +1;/* add the null */2698break;2699case DATE_NORMAL:2700 blame_date_width =sizeof("Thu Oct 19 16:00:04 2006 -0700");2701break;2702case DATE_STRFTIME:2703 blame_date_width =strlen(show_date(0,0, &blame_date_mode)) +1;/* add the null */2704break;2705}2706 blame_date_width -=1;/* strip the null */27072708if(DIFF_OPT_TST(&revs.diffopt, FIND_COPIES_HARDER))2709 opt |= (PICKAXE_BLAME_COPY | PICKAXE_BLAME_MOVE |2710 PICKAXE_BLAME_COPY_HARDER);27112712if(!blame_move_score)2713 blame_move_score = BLAME_DEFAULT_MOVE_SCORE;2714if(!blame_copy_score)2715 blame_copy_score = BLAME_DEFAULT_COPY_SCORE;27162717/*2718 * We have collected options unknown to us in argv[1..unk]2719 * which are to be passed to revision machinery if we are2720 * going to do the "bottom" processing.2721 *2722 * The remaining are:2723 *2724 * (1) if dashdash_pos != 0, it is either2725 * "blame [revisions] -- <path>" or2726 * "blame -- <path> <rev>"2727 *2728 * (2) otherwise, it is one of the two:2729 * "blame [revisions] <path>"2730 * "blame <path> <rev>"2731 *2732 * Note that we must strip out <path> from the arguments: we do not2733 * want the path pruning but we may want "bottom" processing.2734 */2735if(dashdash_pos) {2736switch(argc - dashdash_pos -1) {2737case2:/* (1b) */2738if(argc !=4)2739usage_with_options(blame_opt_usage, options);2740/* reorder for the new way: <rev> -- <path> */2741 argv[1] = argv[3];2742 argv[3] = argv[2];2743 argv[2] ="--";2744/* FALLTHROUGH */2745case1:/* (1a) */2746 path =add_prefix(prefix, argv[--argc]);2747 argv[argc] = NULL;2748break;2749default:2750usage_with_options(blame_opt_usage, options);2751}2752}else{2753if(argc <2)2754usage_with_options(blame_opt_usage, options);2755 path =add_prefix(prefix, argv[argc -1]);2756if(argc ==3&& !file_exists(path)) {/* (2b) */2757 path =add_prefix(prefix, argv[1]);2758 argv[1] = argv[2];2759}2760 argv[argc -1] ="--";27612762setup_work_tree();2763if(!file_exists(path))2764die_errno("cannot stat path '%s'", path);2765}27662767 revs.disable_stdin =1;2768setup_revisions(argc, argv, &revs, NULL);2769memset(&sb,0,sizeof(sb));27702771 sb.revs = &revs;2772if(!reverse) {2773 final_commit_name =prepare_final(&sb);2774 sb.commits.compare = compare_commits_by_commit_date;2775}2776else if(contents_from)2777die(_("--contents and --reverse do not blend well."));2778else{2779 final_commit_name =prepare_initial(&sb);2780 sb.commits.compare = compare_commits_by_reverse_commit_date;2781if(revs.first_parent_only)2782 revs.children.name = NULL;2783}27842785if(!sb.final) {2786/*2787 * "--not A B -- path" without anything positive;2788 * do not default to HEAD, but use the working tree2789 * or "--contents".2790 */2791setup_work_tree();2792 sb.final =fake_working_tree_commit(&sb.revs->diffopt,2793 path, contents_from);2794add_pending_object(&revs, &(sb.final->object),":");2795}2796else if(contents_from)2797die(_("cannot use --contents with final commit object name"));27982799if(reverse && revs.first_parent_only) {2800 final_commit =find_single_final(sb.revs, NULL);2801if(!final_commit)2802die(_("--reverse and --first-parent together require specified latest commit"));2803}28042805/*2806 * If we have bottom, this will mark the ancestors of the2807 * bottom commits we would reach while traversing as2808 * uninteresting.2809 */2810if(prepare_revision_walk(&revs))2811die(_("revision walk setup failed"));28122813if(reverse && revs.first_parent_only) {2814struct commit *c = final_commit;28152816 sb.revs->children.name ="children";2817while(c->parents &&2818oidcmp(&c->object.oid, &sb.final->object.oid)) {2819struct commit_list *l =xcalloc(1,sizeof(*l));28202821 l->item = c;2822if(add_decoration(&sb.revs->children,2823&c->parents->item->object, l))2824die("BUG: not unique item in first-parent chain");2825 c = c->parents->item;2826}28272828if(oidcmp(&c->object.oid, &sb.final->object.oid))2829die(_("--reverse --first-parent together require range along first-parent chain"));2830}28312832if(is_null_oid(&sb.final->object.oid)) {2833 o = sb.final->util;2834 sb.final_buf =xmemdupz(o->file.ptr, o->file.size);2835 sb.final_buf_size = o->file.size;2836}2837else{2838 o =get_origin(&sb, sb.final, path);2839if(fill_blob_sha1_and_mode(o))2840die(_("no such path%sin%s"), path, final_commit_name);28412842if(DIFF_OPT_TST(&sb.revs->diffopt, ALLOW_TEXTCONV) &&2843textconv_object(path, o->mode, &o->blob_oid,1, (char**) &sb.final_buf,2844&sb.final_buf_size))2845;2846else2847 sb.final_buf =read_sha1_file(o->blob_oid.hash, &type,2848&sb.final_buf_size);28492850if(!sb.final_buf)2851die(_("cannot read blob%sfor path%s"),2852oid_to_hex(&o->blob_oid),2853 path);2854}2855 num_read_blob++;2856 lno =prepare_lines(&sb);28572858if(lno && !range_list.nr)2859string_list_append(&range_list,"1");28602861 anchor =1;2862range_set_init(&ranges, range_list.nr);2863for(range_i =0; range_i < range_list.nr; ++range_i) {2864long bottom, top;2865if(parse_range_arg(range_list.items[range_i].string,2866 nth_line_cb, &sb, lno, anchor,2867&bottom, &top, sb.path))2868usage(blame_usage);2869if(lno < top || ((lno || bottom) && lno < bottom))2870die(Q_("file%shas only%lu line",2871"file%shas only%lu lines",2872 lno), path, lno);2873if(bottom <1)2874 bottom =1;2875if(top <1)2876 top = lno;2877 bottom--;2878range_set_append_unsafe(&ranges, bottom, top);2879 anchor = top +1;2880}2881sort_and_merge_range_set(&ranges);28822883for(range_i = ranges.nr; range_i >0; --range_i) {2884const struct range *r = &ranges.ranges[range_i -1];2885long bottom = r->start;2886long top = r->end;2887struct blame_entry *next = ent;2888 ent =xcalloc(1,sizeof(*ent));2889 ent->lno = bottom;2890 ent->num_lines = top - bottom;2891 ent->suspect = o;2892 ent->s_lno = bottom;2893 ent->next = next;2894origin_incref(o);2895}28962897 o->suspects = ent;2898prio_queue_put(&sb.commits, o->commit);28992900origin_decref(o);29012902range_set_release(&ranges);2903string_list_clear(&range_list,0);29042905 sb.ent = NULL;2906 sb.path = path;29072908read_mailmap(&mailmap, NULL);29092910assign_blame(&sb, opt);29112912if(!incremental)2913setup_pager();29142915free(final_commit_name);29162917if(incremental)2918return0;29192920 sb.ent =blame_sort(sb.ent, compare_blame_final);29212922coalesce(&sb);29232924if(!(output_option & OUTPUT_PORCELAIN))2925find_alignment(&sb, &output_option);29262927output(&sb, output_option);2928free((void*)sb.final_buf);2929for(ent = sb.ent; ent; ) {2930struct blame_entry *e = ent->next;2931free(ent);2932 ent = e;2933}29342935if(show_stats) {2936printf("num read blob:%d\n", num_read_blob);2937printf("num get patch:%d\n", num_get_patch);2938printf("num commits:%d\n", num_commits);2939}2940return0;2941}