1/* 2 * Pickaxe 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 20static char blame_usage[] = 21"git-blame [-c] [-l] [-t] [-f] [-n] [-p] [-L n,m] [-S <revs-file>] [-M] [-C] [-C] [--contents <filename>] [--incremental] [commit] [--] file\n" 22" -c Use the same output mode as git-annotate (Default: off)\n" 23" -b Show blank SHA-1 for boundary commits (Default: off)\n" 24" -l Show long commit SHA1 (Default: off)\n" 25" --root Do not treat root commits as boundaries (Default: off)\n" 26" -t Show raw timestamp (Default: off)\n" 27" -f, --show-name Show original filename (Default: auto)\n" 28" -n, --show-number Show original linenumber (Default: off)\n" 29" -p, --porcelain Show in a format designed for machine consumption\n" 30" -L n,m Process only line range n,m, counting from 1\n" 31" -M, -C Find line movements within and across files\n" 32" --incremental Show blame entries as we find them, incrementally\n" 33" --contents file Use <file>'s contents as the final image\n" 34" -S revs-file Use revisions from revs-file instead of calling git-rev-list\n"; 35 36static int longest_file; 37static int longest_author; 38static int max_orig_digits; 39static int max_digits; 40static int max_score_digits; 41static int show_root; 42static int blank_boundary; 43static int incremental; 44static int cmd_is_annotate; 45 46#ifndef DEBUG 47#define DEBUG 0 48#endif 49 50/* stats */ 51static int num_read_blob; 52static int num_get_patch; 53static int num_commits; 54 55#define PICKAXE_BLAME_MOVE 01 56#define PICKAXE_BLAME_COPY 02 57#define PICKAXE_BLAME_COPY_HARDER 04 58 59/* 60 * blame for a blame_entry with score lower than these thresholds 61 * is not passed to the parent using move/copy logic. 62 */ 63static unsigned blame_move_score; 64static unsigned blame_copy_score; 65#define BLAME_DEFAULT_MOVE_SCORE 20 66#define BLAME_DEFAULT_COPY_SCORE 40 67 68/* bits #0..7 in revision.h, #8..11 used for merge_bases() in commit.c */ 69#define METAINFO_SHOWN (1u<<12) 70#define MORE_THAN_ONE_PATH (1u<<13) 71 72/* 73 * One blob in a commit that is being suspected 74 */ 75struct origin { 76int refcnt; 77struct commit *commit; 78 mmfile_t file; 79unsigned char blob_sha1[20]; 80char path[FLEX_ARRAY]; 81}; 82 83/* 84 * Given an origin, prepare mmfile_t structure to be used by the 85 * diff machinery 86 */ 87static char*fill_origin_blob(struct origin *o, mmfile_t *file) 88{ 89if(!o->file.ptr) { 90enum object_type type; 91 num_read_blob++; 92 file->ptr =read_sha1_file(o->blob_sha1, &type, 93(unsigned long*)(&(file->size))); 94 o->file = *file; 95} 96else 97*file = o->file; 98return file->ptr; 99} 100 101/* 102 * Origin is refcounted and usually we keep the blob contents to be 103 * reused. 104 */ 105staticinlinestruct origin *origin_incref(struct origin *o) 106{ 107if(o) 108 o->refcnt++; 109return o; 110} 111 112static voidorigin_decref(struct origin *o) 113{ 114if(o && --o->refcnt <=0) { 115if(o->file.ptr) 116free(o->file.ptr); 117memset(o,0,sizeof(*o)); 118free(o); 119} 120} 121 122/* 123 * Each group of lines is described by a blame_entry; it can be split 124 * as we pass blame to the parents. They form a linked list in the 125 * scoreboard structure, sorted by the target line number. 126 */ 127struct blame_entry { 128struct blame_entry *prev; 129struct blame_entry *next; 130 131/* the first line of this group in the final image; 132 * internally all line numbers are 0 based. 133 */ 134int lno; 135 136/* how many lines this group has */ 137int num_lines; 138 139/* the commit that introduced this group into the final image */ 140struct origin *suspect; 141 142/* true if the suspect is truly guilty; false while we have not 143 * checked if the group came from one of its parents. 144 */ 145char guilty; 146 147/* the line number of the first line of this group in the 148 * suspect's file; internally all line numbers are 0 based. 149 */ 150int s_lno; 151 152/* how significant this entry is -- cached to avoid 153 * scanning the lines over and over. 154 */ 155unsigned score; 156}; 157 158/* 159 * The current state of the blame assignment. 160 */ 161struct scoreboard { 162/* the final commit (i.e. where we started digging from) */ 163struct commit *final; 164 165const char*path; 166 167/* 168 * The contents in the final image. 169 * Used by many functions to obtain contents of the nth line, 170 * indexed with scoreboard.lineno[blame_entry.lno]. 171 */ 172const char*final_buf; 173unsigned long final_buf_size; 174 175/* linked list of blames */ 176struct blame_entry *ent; 177 178/* look-up a line in the final buffer */ 179int num_lines; 180int*lineno; 181}; 182 183staticinlineintsame_suspect(struct origin *a,struct origin *b) 184{ 185if(a == b) 186return1; 187if(a->commit != b->commit) 188return0; 189return!strcmp(a->path, b->path); 190} 191 192static voidsanity_check_refcnt(struct scoreboard *); 193 194/* 195 * If two blame entries that are next to each other came from 196 * contiguous lines in the same origin (i.e. <commit, path> pair), 197 * merge them together. 198 */ 199static voidcoalesce(struct scoreboard *sb) 200{ 201struct blame_entry *ent, *next; 202 203for(ent = sb->ent; ent && (next = ent->next); ent = next) { 204if(same_suspect(ent->suspect, next->suspect) && 205 ent->guilty == next->guilty && 206 ent->s_lno + ent->num_lines == next->s_lno) { 207 ent->num_lines += next->num_lines; 208 ent->next = next->next; 209if(ent->next) 210 ent->next->prev = ent; 211origin_decref(next->suspect); 212free(next); 213 ent->score =0; 214 next = ent;/* again */ 215} 216} 217 218if(DEBUG)/* sanity */ 219sanity_check_refcnt(sb); 220} 221 222/* 223 * Given a commit and a path in it, create a new origin structure. 224 * The callers that add blame to the scoreboard should use 225 * get_origin() to obtain shared, refcounted copy instead of calling 226 * this function directly. 227 */ 228static struct origin *make_origin(struct commit *commit,const char*path) 229{ 230struct origin *o; 231 o =xcalloc(1,sizeof(*o) +strlen(path) +1); 232 o->commit = commit; 233 o->refcnt =1; 234strcpy(o->path, path); 235return o; 236} 237 238/* 239 * Locate an existing origin or create a new one. 240 */ 241static struct origin *get_origin(struct scoreboard *sb, 242struct commit *commit, 243const char*path) 244{ 245struct blame_entry *e; 246 247for(e = sb->ent; e; e = e->next) { 248if(e->suspect->commit == commit && 249!strcmp(e->suspect->path, path)) 250returnorigin_incref(e->suspect); 251} 252returnmake_origin(commit, path); 253} 254 255/* 256 * Fill the blob_sha1 field of an origin if it hasn't, so that later 257 * call to fill_origin_blob() can use it to locate the data. blob_sha1 258 * for an origin is also used to pass the blame for the entire file to 259 * the parent to detect the case where a child's blob is identical to 260 * that of its parent's. 261 */ 262static intfill_blob_sha1(struct origin *origin) 263{ 264unsigned mode; 265 266if(!is_null_sha1(origin->blob_sha1)) 267return0; 268if(get_tree_entry(origin->commit->object.sha1, 269 origin->path, 270 origin->blob_sha1, &mode)) 271goto error_out; 272if(sha1_object_info(origin->blob_sha1, NULL) != OBJ_BLOB) 273goto error_out; 274return0; 275 error_out: 276hashclr(origin->blob_sha1); 277return-1; 278} 279 280/* 281 * We have an origin -- check if the same path exists in the 282 * parent and return an origin structure to represent it. 283 */ 284static struct origin *find_origin(struct scoreboard *sb, 285struct commit *parent, 286struct origin *origin) 287{ 288struct origin *porigin = NULL; 289struct diff_options diff_opts; 290const char*paths[2]; 291 292if(parent->util) { 293/* 294 * Each commit object can cache one origin in that 295 * commit. This is a freestanding copy of origin and 296 * not refcounted. 297 */ 298struct origin *cached = parent->util; 299if(!strcmp(cached->path, origin->path)) { 300/* 301 * The same path between origin and its parent 302 * without renaming -- the most common case. 303 */ 304 porigin =get_origin(sb, parent, cached->path); 305 306/* 307 * If the origin was newly created (i.e. get_origin 308 * would call make_origin if none is found in the 309 * scoreboard), it does not know the blob_sha1, 310 * so copy it. Otherwise porigin was in the 311 * scoreboard and already knows blob_sha1. 312 */ 313if(porigin->refcnt ==1) 314hashcpy(porigin->blob_sha1, cached->blob_sha1); 315return porigin; 316} 317/* otherwise it was not very useful; free it */ 318free(parent->util); 319 parent->util = NULL; 320} 321 322/* See if the origin->path is different between parent 323 * and origin first. Most of the time they are the 324 * same and diff-tree is fairly efficient about this. 325 */ 326diff_setup(&diff_opts); 327 diff_opts.recursive =1; 328 diff_opts.detect_rename =0; 329 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT; 330 paths[0] = origin->path; 331 paths[1] = NULL; 332 333diff_tree_setup_paths(paths, &diff_opts); 334if(diff_setup_done(&diff_opts) <0) 335die("diff-setup"); 336 337if(is_null_sha1(origin->commit->object.sha1)) 338do_diff_cache(parent->tree->object.sha1, &diff_opts); 339else 340diff_tree_sha1(parent->tree->object.sha1, 341 origin->commit->tree->object.sha1, 342"", &diff_opts); 343diffcore_std(&diff_opts); 344 345/* It is either one entry that says "modified", or "created", 346 * or nothing. 347 */ 348if(!diff_queued_diff.nr) { 349/* The path is the same as parent */ 350 porigin =get_origin(sb, parent, origin->path); 351hashcpy(porigin->blob_sha1, origin->blob_sha1); 352} 353else if(diff_queued_diff.nr !=1) 354die("internal error in blame::find_origin"); 355else{ 356struct diff_filepair *p = diff_queued_diff.queue[0]; 357switch(p->status) { 358default: 359die("internal error in blame::find_origin (%c)", 360 p->status); 361case'M': 362 porigin =get_origin(sb, parent, origin->path); 363hashcpy(porigin->blob_sha1, p->one->sha1); 364break; 365case'A': 366case'T': 367/* Did not exist in parent, or type changed */ 368break; 369} 370} 371diff_flush(&diff_opts); 372if(porigin) { 373/* 374 * Create a freestanding copy that is not part of 375 * the refcounted origin found in the scoreboard, and 376 * cache it in the commit. 377 */ 378struct origin *cached; 379 380 cached =make_origin(porigin->commit, porigin->path); 381hashcpy(cached->blob_sha1, porigin->blob_sha1); 382 parent->util = cached; 383} 384return porigin; 385} 386 387/* 388 * We have an origin -- find the path that corresponds to it in its 389 * parent and return an origin structure to represent it. 390 */ 391static struct origin *find_rename(struct scoreboard *sb, 392struct commit *parent, 393struct origin *origin) 394{ 395struct origin *porigin = NULL; 396struct diff_options diff_opts; 397int i; 398const char*paths[2]; 399 400diff_setup(&diff_opts); 401 diff_opts.recursive =1; 402 diff_opts.detect_rename = DIFF_DETECT_RENAME; 403 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT; 404 diff_opts.single_follow = origin->path; 405 paths[0] = NULL; 406diff_tree_setup_paths(paths, &diff_opts); 407if(diff_setup_done(&diff_opts) <0) 408die("diff-setup"); 409 410if(is_null_sha1(origin->commit->object.sha1)) 411do_diff_cache(parent->tree->object.sha1, &diff_opts); 412else 413diff_tree_sha1(parent->tree->object.sha1, 414 origin->commit->tree->object.sha1, 415"", &diff_opts); 416diffcore_std(&diff_opts); 417 418for(i =0; i < diff_queued_diff.nr; i++) { 419struct diff_filepair *p = diff_queued_diff.queue[i]; 420if((p->status =='R'|| p->status =='C') && 421!strcmp(p->two->path, origin->path)) { 422 porigin =get_origin(sb, parent, p->one->path); 423hashcpy(porigin->blob_sha1, p->one->sha1); 424break; 425} 426} 427diff_flush(&diff_opts); 428return porigin; 429} 430 431/* 432 * Parsing of patch chunks... 433 */ 434struct chunk { 435/* line number in postimage; up to but not including this 436 * line is the same as preimage 437 */ 438int same; 439 440/* preimage line number after this chunk */ 441int p_next; 442 443/* postimage line number after this chunk */ 444int t_next; 445}; 446 447struct patch { 448struct chunk *chunks; 449int num; 450}; 451 452struct blame_diff_state { 453struct xdiff_emit_state xm; 454struct patch *ret; 455unsigned hunk_post_context; 456unsigned hunk_in_pre_context :1; 457}; 458 459static voidprocess_u_diff(void*state_,char*line,unsigned long len) 460{ 461struct blame_diff_state *state = state_; 462struct chunk *chunk; 463int off1, off2, len1, len2, num; 464 465 num = state->ret->num; 466if(len <4|| line[0] !='@'|| line[1] !='@') { 467if(state->hunk_in_pre_context && line[0] ==' ') 468 state->ret->chunks[num -1].same++; 469else{ 470 state->hunk_in_pre_context =0; 471if(line[0] ==' ') 472 state->hunk_post_context++; 473else 474 state->hunk_post_context =0; 475} 476return; 477} 478 479if(num && state->hunk_post_context) { 480 chunk = &state->ret->chunks[num -1]; 481 chunk->p_next -= state->hunk_post_context; 482 chunk->t_next -= state->hunk_post_context; 483} 484 state->ret->num = ++num; 485 state->ret->chunks =xrealloc(state->ret->chunks, 486sizeof(struct chunk) * num); 487 chunk = &state->ret->chunks[num -1]; 488if(parse_hunk_header(line, len, &off1, &len1, &off2, &len2)) { 489 state->ret->num--; 490return; 491} 492 493/* Line numbers in patch output are one based. */ 494 off1--; 495 off2--; 496 497 chunk->same = len2 ? off2 : (off2 +1); 498 499 chunk->p_next = off1 + (len1 ? len1 :1); 500 chunk->t_next = chunk->same + len2; 501 state->hunk_in_pre_context =1; 502 state->hunk_post_context =0; 503} 504 505static struct patch *compare_buffer(mmfile_t *file_p, mmfile_t *file_o, 506int context) 507{ 508struct blame_diff_state state; 509 xpparam_t xpp; 510 xdemitconf_t xecfg; 511 xdemitcb_t ecb; 512 513 xpp.flags = XDF_NEED_MINIMAL; 514 xecfg.ctxlen = context; 515 xecfg.flags =0; 516 ecb.outf = xdiff_outf; 517 ecb.priv = &state; 518memset(&state,0,sizeof(state)); 519 state.xm.consume = process_u_diff; 520 state.ret =xmalloc(sizeof(struct patch)); 521 state.ret->chunks = NULL; 522 state.ret->num =0; 523 524xdl_diff(file_p, file_o, &xpp, &xecfg, &ecb); 525 526if(state.ret->num) { 527struct chunk *chunk; 528 chunk = &state.ret->chunks[state.ret->num -1]; 529 chunk->p_next -= state.hunk_post_context; 530 chunk->t_next -= state.hunk_post_context; 531} 532return state.ret; 533} 534 535/* 536 * Run diff between two origins and grab the patch output, so that 537 * we can pass blame for lines origin is currently suspected for 538 * to its parent. 539 */ 540static struct patch *get_patch(struct origin *parent,struct origin *origin) 541{ 542 mmfile_t file_p, file_o; 543struct patch *patch; 544 545fill_origin_blob(parent, &file_p); 546fill_origin_blob(origin, &file_o); 547if(!file_p.ptr || !file_o.ptr) 548return NULL; 549 patch =compare_buffer(&file_p, &file_o,0); 550 num_get_patch++; 551return patch; 552} 553 554static voidfree_patch(struct patch *p) 555{ 556free(p->chunks); 557free(p); 558} 559 560/* 561 * Link in a new blame entry to the scoreboard. Entries that cover the 562 * same line range have been removed from the scoreboard previously. 563 */ 564static voidadd_blame_entry(struct scoreboard *sb,struct blame_entry *e) 565{ 566struct blame_entry *ent, *prev = NULL; 567 568origin_incref(e->suspect); 569 570for(ent = sb->ent; ent && ent->lno < e->lno; ent = ent->next) 571 prev = ent; 572 573/* prev, if not NULL, is the last one that is below e */ 574 e->prev = prev; 575if(prev) { 576 e->next = prev->next; 577 prev->next = e; 578} 579else{ 580 e->next = sb->ent; 581 sb->ent = e; 582} 583if(e->next) 584 e->next->prev = e; 585} 586 587/* 588 * src typically is on-stack; we want to copy the information in it to 589 * an malloced blame_entry that is already on the linked list of the 590 * scoreboard. The origin of dst loses a refcnt while the origin of src 591 * gains one. 592 */ 593static voiddup_entry(struct blame_entry *dst,struct blame_entry *src) 594{ 595struct blame_entry *p, *n; 596 597 p = dst->prev; 598 n = dst->next; 599origin_incref(src->suspect); 600origin_decref(dst->suspect); 601memcpy(dst, src,sizeof(*src)); 602 dst->prev = p; 603 dst->next = n; 604 dst->score =0; 605} 606 607static const char*nth_line(struct scoreboard *sb,int lno) 608{ 609return sb->final_buf + sb->lineno[lno]; 610} 611 612/* 613 * It is known that lines between tlno to same came from parent, and e 614 * has an overlap with that range. it also is known that parent's 615 * line plno corresponds to e's line tlno. 616 * 617 * <---- e -----> 618 * <------> 619 * <------------> 620 * <------------> 621 * <------------------> 622 * 623 * Split e into potentially three parts; before this chunk, the chunk 624 * to be blamed for the parent, and after that portion. 625 */ 626static voidsplit_overlap(struct blame_entry *split, 627struct blame_entry *e, 628int tlno,int plno,int same, 629struct origin *parent) 630{ 631int chunk_end_lno; 632memset(split,0,sizeof(struct blame_entry [3])); 633 634if(e->s_lno < tlno) { 635/* there is a pre-chunk part not blamed on parent */ 636 split[0].suspect =origin_incref(e->suspect); 637 split[0].lno = e->lno; 638 split[0].s_lno = e->s_lno; 639 split[0].num_lines = tlno - e->s_lno; 640 split[1].lno = e->lno + tlno - e->s_lno; 641 split[1].s_lno = plno; 642} 643else{ 644 split[1].lno = e->lno; 645 split[1].s_lno = plno + (e->s_lno - tlno); 646} 647 648if(same < e->s_lno + e->num_lines) { 649/* there is a post-chunk part not blamed on parent */ 650 split[2].suspect =origin_incref(e->suspect); 651 split[2].lno = e->lno + (same - e->s_lno); 652 split[2].s_lno = e->s_lno + (same - e->s_lno); 653 split[2].num_lines = e->s_lno + e->num_lines - same; 654 chunk_end_lno = split[2].lno; 655} 656else 657 chunk_end_lno = e->lno + e->num_lines; 658 split[1].num_lines = chunk_end_lno - split[1].lno; 659 660/* 661 * if it turns out there is nothing to blame the parent for, 662 * forget about the splitting. !split[1].suspect signals this. 663 */ 664if(split[1].num_lines <1) 665return; 666 split[1].suspect =origin_incref(parent); 667} 668 669/* 670 * split_overlap() divided an existing blame e into up to three parts 671 * in split. Adjust the linked list of blames in the scoreboard to 672 * reflect the split. 673 */ 674static voidsplit_blame(struct scoreboard *sb, 675struct blame_entry *split, 676struct blame_entry *e) 677{ 678struct blame_entry *new_entry; 679 680if(split[0].suspect && split[2].suspect) { 681/* The first part (reuse storage for the existing entry e) */ 682dup_entry(e, &split[0]); 683 684/* The last part -- me */ 685 new_entry =xmalloc(sizeof(*new_entry)); 686memcpy(new_entry, &(split[2]),sizeof(struct blame_entry)); 687add_blame_entry(sb, new_entry); 688 689/* ... and the middle part -- parent */ 690 new_entry =xmalloc(sizeof(*new_entry)); 691memcpy(new_entry, &(split[1]),sizeof(struct blame_entry)); 692add_blame_entry(sb, new_entry); 693} 694else if(!split[0].suspect && !split[2].suspect) 695/* 696 * The parent covers the entire area; reuse storage for 697 * e and replace it with the parent. 698 */ 699dup_entry(e, &split[1]); 700else if(split[0].suspect) { 701/* me and then parent */ 702dup_entry(e, &split[0]); 703 704 new_entry =xmalloc(sizeof(*new_entry)); 705memcpy(new_entry, &(split[1]),sizeof(struct blame_entry)); 706add_blame_entry(sb, new_entry); 707} 708else{ 709/* parent and then me */ 710dup_entry(e, &split[1]); 711 712 new_entry =xmalloc(sizeof(*new_entry)); 713memcpy(new_entry, &(split[2]),sizeof(struct blame_entry)); 714add_blame_entry(sb, new_entry); 715} 716 717if(DEBUG) {/* sanity */ 718struct blame_entry *ent; 719int lno = sb->ent->lno, corrupt =0; 720 721for(ent = sb->ent; ent; ent = ent->next) { 722if(lno != ent->lno) 723 corrupt =1; 724if(ent->s_lno <0) 725 corrupt =1; 726 lno += ent->num_lines; 727} 728if(corrupt) { 729 lno = sb->ent->lno; 730for(ent = sb->ent; ent; ent = ent->next) { 731printf("L%8d l%8d n%8d\n", 732 lno, ent->lno, ent->num_lines); 733 lno = ent->lno + ent->num_lines; 734} 735die("oops"); 736} 737} 738} 739 740/* 741 * After splitting the blame, the origins used by the 742 * on-stack blame_entry should lose one refcnt each. 743 */ 744static voiddecref_split(struct blame_entry *split) 745{ 746int i; 747 748for(i =0; i <3; i++) 749origin_decref(split[i].suspect); 750} 751 752/* 753 * Helper for blame_chunk(). blame_entry e is known to overlap with 754 * the patch hunk; split it and pass blame to the parent. 755 */ 756static voidblame_overlap(struct scoreboard *sb,struct blame_entry *e, 757int tlno,int plno,int same, 758struct origin *parent) 759{ 760struct blame_entry split[3]; 761 762split_overlap(split, e, tlno, plno, same, parent); 763if(split[1].suspect) 764split_blame(sb, split, e); 765decref_split(split); 766} 767 768/* 769 * Find the line number of the last line the target is suspected for. 770 */ 771static intfind_last_in_target(struct scoreboard *sb,struct origin *target) 772{ 773struct blame_entry *e; 774int last_in_target = -1; 775 776for(e = sb->ent; e; e = e->next) { 777if(e->guilty || !same_suspect(e->suspect, target)) 778continue; 779if(last_in_target < e->s_lno + e->num_lines) 780 last_in_target = e->s_lno + e->num_lines; 781} 782return last_in_target; 783} 784 785/* 786 * Process one hunk from the patch between the current suspect for 787 * blame_entry e and its parent. Find and split the overlap, and 788 * pass blame to the overlapping part to the parent. 789 */ 790static voidblame_chunk(struct scoreboard *sb, 791int tlno,int plno,int same, 792struct origin *target,struct origin *parent) 793{ 794struct blame_entry *e; 795 796for(e = sb->ent; e; e = e->next) { 797if(e->guilty || !same_suspect(e->suspect, target)) 798continue; 799if(same <= e->s_lno) 800continue; 801if(tlno < e->s_lno + e->num_lines) 802blame_overlap(sb, e, tlno, plno, same, parent); 803} 804} 805 806/* 807 * We are looking at the origin 'target' and aiming to pass blame 808 * for the lines it is suspected to its parent. Run diff to find 809 * which lines came from parent and pass blame for them. 810 */ 811static intpass_blame_to_parent(struct scoreboard *sb, 812struct origin *target, 813struct origin *parent) 814{ 815int i, last_in_target, plno, tlno; 816struct patch *patch; 817 818 last_in_target =find_last_in_target(sb, target); 819if(last_in_target <0) 820return1;/* nothing remains for this target */ 821 822 patch =get_patch(parent, target); 823 plno = tlno =0; 824for(i =0; i < patch->num; i++) { 825struct chunk *chunk = &patch->chunks[i]; 826 827blame_chunk(sb, tlno, plno, chunk->same, target, parent); 828 plno = chunk->p_next; 829 tlno = chunk->t_next; 830} 831/* The rest (i.e. anything after tlno) are the same as the parent */ 832blame_chunk(sb, tlno, plno, last_in_target, target, parent); 833 834free_patch(patch); 835return0; 836} 837 838/* 839 * The lines in blame_entry after splitting blames many times can become 840 * very small and trivial, and at some point it becomes pointless to 841 * blame the parents. E.g. "\t\t}\n\t}\n\n" appears everywhere in any 842 * ordinary C program, and it is not worth to say it was copied from 843 * totally unrelated file in the parent. 844 * 845 * Compute how trivial the lines in the blame_entry are. 846 */ 847static unsignedent_score(struct scoreboard *sb,struct blame_entry *e) 848{ 849unsigned score; 850const char*cp, *ep; 851 852if(e->score) 853return e->score; 854 855 score =1; 856 cp =nth_line(sb, e->lno); 857 ep =nth_line(sb, e->lno + e->num_lines); 858while(cp < ep) { 859unsigned ch = *((unsigned char*)cp); 860if(isalnum(ch)) 861 score++; 862 cp++; 863} 864 e->score = score; 865return score; 866} 867 868/* 869 * best_so_far[] and this[] are both a split of an existing blame_entry 870 * that passes blame to the parent. Maintain best_so_far the best split 871 * so far, by comparing this and best_so_far and copying this into 872 * bst_so_far as needed. 873 */ 874static voidcopy_split_if_better(struct scoreboard *sb, 875struct blame_entry *best_so_far, 876struct blame_entry *this) 877{ 878int i; 879 880if(!this[1].suspect) 881return; 882if(best_so_far[1].suspect) { 883if(ent_score(sb, &this[1]) <ent_score(sb, &best_so_far[1])) 884return; 885} 886 887for(i =0; i <3; i++) 888origin_incref(this[i].suspect); 889decref_split(best_so_far); 890memcpy(best_so_far,this,sizeof(struct blame_entry [3])); 891} 892 893/* 894 * We are looking at a part of the final image represented by 895 * ent (tlno and same are offset by ent->s_lno). 896 * tlno is where we are looking at in the final image. 897 * up to (but not including) same match preimage. 898 * plno is where we are looking at in the preimage. 899 * 900 * <-------------- final image ----------------------> 901 * <------ent------> 902 * ^tlno ^same 903 * <---------preimage-----> 904 * ^plno 905 * 906 * All line numbers are 0-based. 907 */ 908static voidhandle_split(struct scoreboard *sb, 909struct blame_entry *ent, 910int tlno,int plno,int same, 911struct origin *parent, 912struct blame_entry *split) 913{ 914if(ent->num_lines <= tlno) 915return; 916if(tlno < same) { 917struct blame_entry this[3]; 918 tlno += ent->s_lno; 919 same += ent->s_lno; 920split_overlap(this, ent, tlno, plno, same, parent); 921copy_split_if_better(sb, split,this); 922decref_split(this); 923} 924} 925 926/* 927 * Find the lines from parent that are the same as ent so that 928 * we can pass blames to it. file_p has the blob contents for 929 * the parent. 930 */ 931static voidfind_copy_in_blob(struct scoreboard *sb, 932struct blame_entry *ent, 933struct origin *parent, 934struct blame_entry *split, 935 mmfile_t *file_p) 936{ 937const char*cp; 938int cnt; 939 mmfile_t file_o; 940struct patch *patch; 941int i, plno, tlno; 942 943/* 944 * Prepare mmfile that contains only the lines in ent. 945 */ 946 cp =nth_line(sb, ent->lno); 947 file_o.ptr = (char*) cp; 948 cnt = ent->num_lines; 949 950while(cnt && cp < sb->final_buf + sb->final_buf_size) { 951if(*cp++ =='\n') 952 cnt--; 953} 954 file_o.size = cp - file_o.ptr; 955 956 patch =compare_buffer(file_p, &file_o,1); 957 958/* 959 * file_o is a part of final image we are annotating. 960 * file_p partially may match that image. 961 */ 962memset(split,0,sizeof(struct blame_entry [3])); 963 plno = tlno =0; 964for(i =0; i < patch->num; i++) { 965struct chunk *chunk = &patch->chunks[i]; 966 967handle_split(sb, ent, tlno, plno, chunk->same, parent, split); 968 plno = chunk->p_next; 969 tlno = chunk->t_next; 970} 971/* remainder, if any, all match the preimage */ 972handle_split(sb, ent, tlno, plno, ent->num_lines, parent, split); 973free_patch(patch); 974} 975 976/* 977 * See if lines currently target is suspected for can be attributed to 978 * parent. 979 */ 980static intfind_move_in_parent(struct scoreboard *sb, 981struct origin *target, 982struct origin *parent) 983{ 984int last_in_target, made_progress; 985struct blame_entry *e, split[3]; 986 mmfile_t file_p; 987 988 last_in_target =find_last_in_target(sb, target); 989if(last_in_target <0) 990return1;/* nothing remains for this target */ 991 992fill_origin_blob(parent, &file_p); 993if(!file_p.ptr) 994return0; 995 996 made_progress =1; 997while(made_progress) { 998 made_progress =0; 999for(e = sb->ent; e; e = e->next) {1000if(e->guilty || !same_suspect(e->suspect, target))1001continue;1002find_copy_in_blob(sb, e, parent, split, &file_p);1003if(split[1].suspect &&1004 blame_move_score <ent_score(sb, &split[1])) {1005split_blame(sb, split, e);1006 made_progress =1;1007}1008decref_split(split);1009}1010}1011return0;1012}10131014struct blame_list {1015struct blame_entry *ent;1016struct blame_entry split[3];1017};10181019/*1020 * Count the number of entries the target is suspected for,1021 * and prepare a list of entry and the best split.1022 */1023static struct blame_list *setup_blame_list(struct scoreboard *sb,1024struct origin *target,1025int*num_ents_p)1026{1027struct blame_entry *e;1028int num_ents, i;1029struct blame_list *blame_list = NULL;10301031for(e = sb->ent, num_ents =0; e; e = e->next)1032if(!e->guilty &&same_suspect(e->suspect, target))1033 num_ents++;1034if(num_ents) {1035 blame_list =xcalloc(num_ents,sizeof(struct blame_list));1036for(e = sb->ent, i =0; e; e = e->next)1037if(!e->guilty &&same_suspect(e->suspect, target))1038 blame_list[i++].ent = e;1039}1040*num_ents_p = num_ents;1041return blame_list;1042}10431044/*1045 * For lines target is suspected for, see if we can find code movement1046 * across file boundary from the parent commit. porigin is the path1047 * in the parent we already tried.1048 */1049static intfind_copy_in_parent(struct scoreboard *sb,1050struct origin *target,1051struct commit *parent,1052struct origin *porigin,1053int opt)1054{1055struct diff_options diff_opts;1056const char*paths[1];1057int i, j;1058int retval;1059struct blame_list *blame_list;1060int num_ents;10611062 blame_list =setup_blame_list(sb, target, &num_ents);1063if(!blame_list)1064return1;/* nothing remains for this target */10651066diff_setup(&diff_opts);1067 diff_opts.recursive =1;1068 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;10691070 paths[0] = NULL;1071diff_tree_setup_paths(paths, &diff_opts);1072if(diff_setup_done(&diff_opts) <0)1073die("diff-setup");10741075/* Try "find copies harder" on new path if requested;1076 * we do not want to use diffcore_rename() actually to1077 * match things up; find_copies_harder is set only to1078 * force diff_tree_sha1() to feed all filepairs to diff_queue,1079 * and this code needs to be after diff_setup_done(), which1080 * usually makes find-copies-harder imply copy detection.1081 */1082if((opt & PICKAXE_BLAME_COPY_HARDER) &&1083(!porigin ||strcmp(target->path, porigin->path)))1084 diff_opts.find_copies_harder =1;10851086if(is_null_sha1(target->commit->object.sha1))1087do_diff_cache(parent->tree->object.sha1, &diff_opts);1088else1089diff_tree_sha1(parent->tree->object.sha1,1090 target->commit->tree->object.sha1,1091"", &diff_opts);10921093if(!diff_opts.find_copies_harder)1094diffcore_std(&diff_opts);10951096 retval =0;1097while(1) {1098int made_progress =0;10991100for(i =0; i < diff_queued_diff.nr; i++) {1101struct diff_filepair *p = diff_queued_diff.queue[i];1102struct origin *norigin;1103 mmfile_t file_p;1104struct blame_entry this[3];11051106if(!DIFF_FILE_VALID(p->one))1107continue;/* does not exist in parent */1108if(porigin && !strcmp(p->one->path, porigin->path))1109/* find_move already dealt with this path */1110continue;11111112 norigin =get_origin(sb, parent, p->one->path);1113hashcpy(norigin->blob_sha1, p->one->sha1);1114fill_origin_blob(norigin, &file_p);1115if(!file_p.ptr)1116continue;11171118for(j =0; j < num_ents; j++) {1119find_copy_in_blob(sb, blame_list[j].ent,1120 norigin,this, &file_p);1121copy_split_if_better(sb, blame_list[j].split,1122this);1123decref_split(this);1124}1125origin_decref(norigin);1126}11271128for(j =0; j < num_ents; j++) {1129struct blame_entry *split = blame_list[j].split;1130if(split[1].suspect &&1131 blame_copy_score <ent_score(sb, &split[1])) {1132split_blame(sb, split, blame_list[j].ent);1133 made_progress =1;1134}1135decref_split(split);1136}1137free(blame_list);11381139if(!made_progress)1140break;1141 blame_list =setup_blame_list(sb, target, &num_ents);1142if(!blame_list) {1143 retval =1;1144break;1145}1146}1147diff_flush(&diff_opts);11481149return retval;1150}11511152/*1153 * The blobs of origin and porigin exactly match, so everything1154 * origin is suspected for can be blamed on the parent.1155 */1156static voidpass_whole_blame(struct scoreboard *sb,1157struct origin *origin,struct origin *porigin)1158{1159struct blame_entry *e;11601161if(!porigin->file.ptr && origin->file.ptr) {1162/* Steal its file */1163 porigin->file = origin->file;1164 origin->file.ptr = NULL;1165}1166for(e = sb->ent; e; e = e->next) {1167if(!same_suspect(e->suspect, origin))1168continue;1169origin_incref(porigin);1170origin_decref(e->suspect);1171 e->suspect = porigin;1172}1173}11741175#define MAXPARENT 1611761177static voidpass_blame(struct scoreboard *sb,struct origin *origin,int opt)1178{1179int i, pass;1180struct commit *commit = origin->commit;1181struct commit_list *parent;1182struct origin *parent_origin[MAXPARENT], *porigin;11831184memset(parent_origin,0,sizeof(parent_origin));11851186/* The first pass looks for unrenamed path to optimize for1187 * common cases, then we look for renames in the second pass.1188 */1189for(pass =0; pass <2; pass++) {1190struct origin *(*find)(struct scoreboard *,1191struct commit *,struct origin *);1192 find = pass ? find_rename : find_origin;11931194for(i =0, parent = commit->parents;1195 i < MAXPARENT && parent;1196 parent = parent->next, i++) {1197struct commit *p = parent->item;1198int j, same;11991200if(parent_origin[i])1201continue;1202if(parse_commit(p))1203continue;1204 porigin =find(sb, p, origin);1205if(!porigin)1206continue;1207if(!hashcmp(porigin->blob_sha1, origin->blob_sha1)) {1208pass_whole_blame(sb, origin, porigin);1209origin_decref(porigin);1210goto finish;1211}1212for(j = same =0; j < i; j++)1213if(parent_origin[j] &&1214!hashcmp(parent_origin[j]->blob_sha1,1215 porigin->blob_sha1)) {1216 same =1;1217break;1218}1219if(!same)1220 parent_origin[i] = porigin;1221else1222origin_decref(porigin);1223}1224}12251226 num_commits++;1227for(i =0, parent = commit->parents;1228 i < MAXPARENT && parent;1229 parent = parent->next, i++) {1230struct origin *porigin = parent_origin[i];1231if(!porigin)1232continue;1233if(pass_blame_to_parent(sb, origin, porigin))1234goto finish;1235}12361237/*1238 * Optionally find moves in parents' files.1239 */1240if(opt & PICKAXE_BLAME_MOVE)1241for(i =0, parent = commit->parents;1242 i < MAXPARENT && parent;1243 parent = parent->next, i++) {1244struct origin *porigin = parent_origin[i];1245if(!porigin)1246continue;1247if(find_move_in_parent(sb, origin, porigin))1248goto finish;1249}12501251/*1252 * Optionally find copies from parents' files.1253 */1254if(opt & PICKAXE_BLAME_COPY)1255for(i =0, parent = commit->parents;1256 i < MAXPARENT && parent;1257 parent = parent->next, i++) {1258struct origin *porigin = parent_origin[i];1259if(find_copy_in_parent(sb, origin, parent->item,1260 porigin, opt))1261goto finish;1262}12631264 finish:1265for(i =0; i < MAXPARENT; i++)1266origin_decref(parent_origin[i]);1267}12681269/*1270 * Information on commits, used for output.1271 */1272struct commit_info1273{1274const char*author;1275const char*author_mail;1276unsigned long author_time;1277const char*author_tz;12781279/* filled only when asked for details */1280const char*committer;1281const char*committer_mail;1282unsigned long committer_time;1283const char*committer_tz;12841285const char*summary;1286};12871288/*1289 * Parse author/committer line in the commit object buffer1290 */1291static voidget_ac_line(const char*inbuf,const char*what,1292int bufsz,char*person,const char**mail,1293unsigned long*time,const char**tz)1294{1295int len;1296char*tmp, *endp;12971298 tmp =strstr(inbuf, what);1299if(!tmp)1300goto error_out;1301 tmp +=strlen(what);1302 endp =strchr(tmp,'\n');1303if(!endp)1304 len =strlen(tmp);1305else1306 len = endp - tmp;1307if(bufsz <= len) {1308 error_out:1309/* Ugh */1310*mail = *tz ="(unknown)";1311*time =0;1312return;1313}1314memcpy(person, tmp, len);13151316 tmp = person;1317 tmp += len;1318*tmp =0;1319while(*tmp !=' ')1320 tmp--;1321*tz = tmp+1;13221323*tmp =0;1324while(*tmp !=' ')1325 tmp--;1326*time =strtoul(tmp, NULL,10);13271328*tmp =0;1329while(*tmp !=' ')1330 tmp--;1331*mail = tmp +1;1332*tmp =0;1333}13341335static voidget_commit_info(struct commit *commit,1336struct commit_info *ret,1337int detailed)1338{1339int len;1340char*tmp, *endp;1341static char author_buf[1024];1342static char committer_buf[1024];1343static char summary_buf[1024];13441345/*1346 * We've operated without save_commit_buffer, so1347 * we now need to populate them for output.1348 */1349if(!commit->buffer) {1350enum object_type type;1351unsigned long size;1352 commit->buffer =1353read_sha1_file(commit->object.sha1, &type, &size);1354}1355 ret->author = author_buf;1356get_ac_line(commit->buffer,"\nauthor ",1357sizeof(author_buf), author_buf, &ret->author_mail,1358&ret->author_time, &ret->author_tz);13591360if(!detailed)1361return;13621363 ret->committer = committer_buf;1364get_ac_line(commit->buffer,"\ncommitter ",1365sizeof(committer_buf), committer_buf, &ret->committer_mail,1366&ret->committer_time, &ret->committer_tz);13671368 ret->summary = summary_buf;1369 tmp =strstr(commit->buffer,"\n\n");1370if(!tmp) {1371 error_out:1372sprintf(summary_buf,"(%s)",sha1_to_hex(commit->object.sha1));1373return;1374}1375 tmp +=2;1376 endp =strchr(tmp,'\n');1377if(!endp)1378 endp = tmp +strlen(tmp);1379 len = endp - tmp;1380if(len >=sizeof(summary_buf) || len ==0)1381goto error_out;1382memcpy(summary_buf, tmp, len);1383 summary_buf[len] =0;1384}13851386/*1387 * To allow LF and other nonportable characters in pathnames,1388 * they are c-style quoted as needed.1389 */1390static voidwrite_filename_info(const char*path)1391{1392printf("filename ");1393write_name_quoted(NULL,0, path,1, stdout);1394putchar('\n');1395}13961397/*1398 * The blame_entry is found to be guilty for the range. Mark it1399 * as such, and show it in incremental output.1400 */1401static voidfound_guilty_entry(struct blame_entry *ent)1402{1403if(ent->guilty)1404return;1405 ent->guilty =1;1406if(incremental) {1407struct origin *suspect = ent->suspect;14081409printf("%s %d %d %d\n",1410sha1_to_hex(suspect->commit->object.sha1),1411 ent->s_lno +1, ent->lno +1, ent->num_lines);1412if(!(suspect->commit->object.flags & METAINFO_SHOWN)) {1413struct commit_info ci;1414 suspect->commit->object.flags |= METAINFO_SHOWN;1415get_commit_info(suspect->commit, &ci,1);1416printf("author%s\n", ci.author);1417printf("author-mail%s\n", ci.author_mail);1418printf("author-time%lu\n", ci.author_time);1419printf("author-tz%s\n", ci.author_tz);1420printf("committer%s\n", ci.committer);1421printf("committer-mail%s\n", ci.committer_mail);1422printf("committer-time%lu\n", ci.committer_time);1423printf("committer-tz%s\n", ci.committer_tz);1424printf("summary%s\n", ci.summary);1425if(suspect->commit->object.flags & UNINTERESTING)1426printf("boundary\n");1427}1428write_filename_info(suspect->path);1429}1430}14311432/*1433 * The main loop -- while the scoreboard has lines whose true origin1434 * is still unknown, pick one blame_entry, and allow its current1435 * suspect to pass blames to its parents.1436 */1437static voidassign_blame(struct scoreboard *sb,struct rev_info *revs,int opt)1438{1439while(1) {1440struct blame_entry *ent;1441struct commit *commit;1442struct origin *suspect = NULL;14431444/* find one suspect to break down */1445for(ent = sb->ent; !suspect && ent; ent = ent->next)1446if(!ent->guilty)1447 suspect = ent->suspect;1448if(!suspect)1449return;/* all done */14501451/*1452 * We will use this suspect later in the loop,1453 * so hold onto it in the meantime.1454 */1455origin_incref(suspect);1456 commit = suspect->commit;1457if(!commit->object.parsed)1458parse_commit(commit);1459if(!(commit->object.flags & UNINTERESTING) &&1460!(revs->max_age != -1&& commit->date < revs->max_age))1461pass_blame(sb, suspect, opt);1462else{1463 commit->object.flags |= UNINTERESTING;1464if(commit->object.parsed)1465mark_parents_uninteresting(commit);1466}1467/* treat root commit as boundary */1468if(!commit->parents && !show_root)1469 commit->object.flags |= UNINTERESTING;14701471/* Take responsibility for the remaining entries */1472for(ent = sb->ent; ent; ent = ent->next)1473if(same_suspect(ent->suspect, suspect))1474found_guilty_entry(ent);1475origin_decref(suspect);14761477if(DEBUG)/* sanity */1478sanity_check_refcnt(sb);1479}1480}14811482static const char*format_time(unsigned long time,const char*tz_str,1483int show_raw_time)1484{1485static char time_buf[128];1486time_t t = time;1487int minutes, tz;1488struct tm *tm;14891490if(show_raw_time) {1491sprintf(time_buf,"%lu%s", time, tz_str);1492return time_buf;1493}14941495 tz =atoi(tz_str);1496 minutes = tz <0? -tz : tz;1497 minutes = (minutes /100)*60+ (minutes %100);1498 minutes = tz <0? -minutes : minutes;1499 t = time + minutes *60;1500 tm =gmtime(&t);15011502strftime(time_buf,sizeof(time_buf),"%Y-%m-%d %H:%M:%S", tm);1503strcat(time_buf, tz_str);1504return time_buf;1505}15061507#define OUTPUT_ANNOTATE_COMPAT 0011508#define OUTPUT_LONG_OBJECT_NAME 0021509#define OUTPUT_RAW_TIMESTAMP 0041510#define OUTPUT_PORCELAIN 0101511#define OUTPUT_SHOW_NAME 0201512#define OUTPUT_SHOW_NUMBER 0401513#define OUTPUT_SHOW_SCORE 010015141515static voidemit_porcelain(struct scoreboard *sb,struct blame_entry *ent)1516{1517int cnt;1518const char*cp;1519struct origin *suspect = ent->suspect;1520char hex[41];15211522strcpy(hex,sha1_to_hex(suspect->commit->object.sha1));1523printf("%s%c%d %d %d\n",1524 hex,1525 ent->guilty ?' ':'*',// purely for debugging1526 ent->s_lno +1,1527 ent->lno +1,1528 ent->num_lines);1529if(!(suspect->commit->object.flags & METAINFO_SHOWN)) {1530struct commit_info ci;1531 suspect->commit->object.flags |= METAINFO_SHOWN;1532get_commit_info(suspect->commit, &ci,1);1533printf("author%s\n", ci.author);1534printf("author-mail%s\n", ci.author_mail);1535printf("author-time%lu\n", ci.author_time);1536printf("author-tz%s\n", ci.author_tz);1537printf("committer%s\n", ci.committer);1538printf("committer-mail%s\n", ci.committer_mail);1539printf("committer-time%lu\n", ci.committer_time);1540printf("committer-tz%s\n", ci.committer_tz);1541write_filename_info(suspect->path);1542printf("summary%s\n", ci.summary);1543if(suspect->commit->object.flags & UNINTERESTING)1544printf("boundary\n");1545}1546else if(suspect->commit->object.flags & MORE_THAN_ONE_PATH)1547write_filename_info(suspect->path);15481549 cp =nth_line(sb, ent->lno);1550for(cnt =0; cnt < ent->num_lines; cnt++) {1551char ch;1552if(cnt)1553printf("%s %d %d\n", hex,1554 ent->s_lno +1+ cnt,1555 ent->lno +1+ cnt);1556putchar('\t');1557do{1558 ch = *cp++;1559putchar(ch);1560}while(ch !='\n'&&1561 cp < sb->final_buf + sb->final_buf_size);1562}1563}15641565static voidemit_other(struct scoreboard *sb,struct blame_entry *ent,int opt)1566{1567int cnt;1568const char*cp;1569struct origin *suspect = ent->suspect;1570struct commit_info ci;1571char hex[41];1572int show_raw_time = !!(opt & OUTPUT_RAW_TIMESTAMP);15731574get_commit_info(suspect->commit, &ci,1);1575strcpy(hex,sha1_to_hex(suspect->commit->object.sha1));15761577 cp =nth_line(sb, ent->lno);1578for(cnt =0; cnt < ent->num_lines; cnt++) {1579char ch;1580int length = (opt & OUTPUT_LONG_OBJECT_NAME) ?40:8;15811582if(suspect->commit->object.flags & UNINTERESTING) {1583if(blank_boundary)1584memset(hex,' ', length);1585else if(!cmd_is_annotate) {1586 length--;1587putchar('^');1588}1589}15901591printf("%.*s", length, hex);1592if(opt & OUTPUT_ANNOTATE_COMPAT)1593printf("\t(%10s\t%10s\t%d)", ci.author,1594format_time(ci.author_time, ci.author_tz,1595 show_raw_time),1596 ent->lno +1+ cnt);1597else{1598if(opt & OUTPUT_SHOW_SCORE)1599printf(" %*d%02d",1600 max_score_digits, ent->score,1601 ent->suspect->refcnt);1602if(opt & OUTPUT_SHOW_NAME)1603printf(" %-*.*s", longest_file, longest_file,1604 suspect->path);1605if(opt & OUTPUT_SHOW_NUMBER)1606printf(" %*d", max_orig_digits,1607 ent->s_lno +1+ cnt);1608printf(" (%-*.*s%10s %*d) ",1609 longest_author, longest_author, ci.author,1610format_time(ci.author_time, ci.author_tz,1611 show_raw_time),1612 max_digits, ent->lno +1+ cnt);1613}1614do{1615 ch = *cp++;1616putchar(ch);1617}while(ch !='\n'&&1618 cp < sb->final_buf + sb->final_buf_size);1619}1620}16211622static voidoutput(struct scoreboard *sb,int option)1623{1624struct blame_entry *ent;16251626if(option & OUTPUT_PORCELAIN) {1627for(ent = sb->ent; ent; ent = ent->next) {1628struct blame_entry *oth;1629struct origin *suspect = ent->suspect;1630struct commit *commit = suspect->commit;1631if(commit->object.flags & MORE_THAN_ONE_PATH)1632continue;1633for(oth = ent->next; oth; oth = oth->next) {1634if((oth->suspect->commit != commit) ||1635!strcmp(oth->suspect->path, suspect->path))1636continue;1637 commit->object.flags |= MORE_THAN_ONE_PATH;1638break;1639}1640}1641}16421643for(ent = sb->ent; ent; ent = ent->next) {1644if(option & OUTPUT_PORCELAIN)1645emit_porcelain(sb, ent);1646else{1647emit_other(sb, ent, option);1648}1649}1650}16511652/*1653 * To allow quick access to the contents of nth line in the1654 * final image, prepare an index in the scoreboard.1655 */1656static intprepare_lines(struct scoreboard *sb)1657{1658const char*buf = sb->final_buf;1659unsigned long len = sb->final_buf_size;1660int num =0, incomplete =0, bol =1;16611662if(len && buf[len-1] !='\n')1663 incomplete++;/* incomplete line at the end */1664while(len--) {1665if(bol) {1666 sb->lineno =xrealloc(sb->lineno,1667sizeof(int* ) * (num +1));1668 sb->lineno[num] = buf - sb->final_buf;1669 bol =0;1670}1671if(*buf++ =='\n') {1672 num++;1673 bol =1;1674}1675}1676 sb->lineno =xrealloc(sb->lineno,1677sizeof(int* ) * (num + incomplete +1));1678 sb->lineno[num + incomplete] = buf - sb->final_buf;1679 sb->num_lines = num + incomplete;1680return sb->num_lines;1681}16821683/*1684 * Add phony grafts for use with -S; this is primarily to1685 * support git-cvsserver that wants to give a linear history1686 * to its clients.1687 */1688static intread_ancestry(const char*graft_file)1689{1690FILE*fp =fopen(graft_file,"r");1691char buf[1024];1692if(!fp)1693return-1;1694while(fgets(buf,sizeof(buf), fp)) {1695/* The format is just "Commit Parent1 Parent2 ...\n" */1696int len =strlen(buf);1697struct commit_graft *graft =read_graft_line(buf, len);1698if(graft)1699register_commit_graft(graft,0);1700}1701fclose(fp);1702return0;1703}17041705/*1706 * How many columns do we need to show line numbers in decimal?1707 */1708static intlineno_width(int lines)1709{1710int i, width;17111712for(width =1, i =10; i <= lines +1; width++)1713 i *=10;1714return width;1715}17161717/*1718 * How many columns do we need to show line numbers, authors,1719 * and filenames?1720 */1721static voidfind_alignment(struct scoreboard *sb,int*option)1722{1723int longest_src_lines =0;1724int longest_dst_lines =0;1725unsigned largest_score =0;1726struct blame_entry *e;17271728for(e = sb->ent; e; e = e->next) {1729struct origin *suspect = e->suspect;1730struct commit_info ci;1731int num;17321733if(strcmp(suspect->path, sb->path))1734*option |= OUTPUT_SHOW_NAME;1735 num =strlen(suspect->path);1736if(longest_file < num)1737 longest_file = num;1738if(!(suspect->commit->object.flags & METAINFO_SHOWN)) {1739 suspect->commit->object.flags |= METAINFO_SHOWN;1740get_commit_info(suspect->commit, &ci,1);1741 num =strlen(ci.author);1742if(longest_author < num)1743 longest_author = num;1744}1745 num = e->s_lno + e->num_lines;1746if(longest_src_lines < num)1747 longest_src_lines = num;1748 num = e->lno + e->num_lines;1749if(longest_dst_lines < num)1750 longest_dst_lines = num;1751if(largest_score <ent_score(sb, e))1752 largest_score =ent_score(sb, e);1753}1754 max_orig_digits =lineno_width(longest_src_lines);1755 max_digits =lineno_width(longest_dst_lines);1756 max_score_digits =lineno_width(largest_score);1757}17581759/*1760 * For debugging -- origin is refcounted, and this asserts that1761 * we do not underflow.1762 */1763static voidsanity_check_refcnt(struct scoreboard *sb)1764{1765int baa =0;1766struct blame_entry *ent;17671768for(ent = sb->ent; ent; ent = ent->next) {1769/* Nobody should have zero or negative refcnt */1770if(ent->suspect->refcnt <=0) {1771fprintf(stderr,"%sin%shas negative refcnt%d\n",1772 ent->suspect->path,1773sha1_to_hex(ent->suspect->commit->object.sha1),1774 ent->suspect->refcnt);1775 baa =1;1776}1777}1778for(ent = sb->ent; ent; ent = ent->next) {1779/* Mark the ones that haven't been checked */1780if(0< ent->suspect->refcnt)1781 ent->suspect->refcnt = -ent->suspect->refcnt;1782}1783for(ent = sb->ent; ent; ent = ent->next) {1784/*1785 * ... then pick each and see if they have the the1786 * correct refcnt.1787 */1788int found;1789struct blame_entry *e;1790struct origin *suspect = ent->suspect;17911792if(0< suspect->refcnt)1793continue;1794 suspect->refcnt = -suspect->refcnt;/* Unmark */1795for(found =0, e = sb->ent; e; e = e->next) {1796if(e->suspect != suspect)1797continue;1798 found++;1799}1800if(suspect->refcnt != found) {1801fprintf(stderr,"%sin%shas refcnt%d, not%d\n",1802 ent->suspect->path,1803sha1_to_hex(ent->suspect->commit->object.sha1),1804 ent->suspect->refcnt, found);1805 baa =2;1806}1807}1808if(baa) {1809int opt =0160;1810find_alignment(sb, &opt);1811output(sb, opt);1812die("Baa%d!", baa);1813}1814}18151816/*1817 * Used for the command line parsing; check if the path exists1818 * in the working tree.1819 */1820static inthas_path_in_work_tree(const char*path)1821{1822struct stat st;1823return!lstat(path, &st);1824}18251826static unsignedparse_score(const char*arg)1827{1828char*end;1829unsigned long score =strtoul(arg, &end,10);1830if(*end)1831return0;1832return score;1833}18341835static const char*add_prefix(const char*prefix,const char*path)1836{1837if(!prefix || !prefix[0])1838return path;1839returnprefix_path(prefix,strlen(prefix), path);1840}18411842/*1843 * Parsing of (comma separated) one item in the -L option1844 */1845static const char*parse_loc(const char*spec,1846struct scoreboard *sb,long lno,1847long begin,long*ret)1848{1849char*term;1850const char*line;1851long num;1852int reg_error;1853 regex_t regexp;1854 regmatch_t match[1];18551856/* Allow "-L <something>,+20" to mean starting at <something>1857 * for 20 lines, or "-L <something>,-5" for 5 lines ending at1858 * <something>.1859 */1860if(1< begin && (spec[0] =='+'|| spec[0] =='-')) {1861 num =strtol(spec +1, &term,10);1862if(term != spec +1) {1863if(spec[0] =='-')1864 num =0- num;1865if(0< num)1866*ret = begin + num -2;1867else if(!num)1868*ret = begin;1869else1870*ret = begin + num;1871return term;1872}1873return spec;1874}1875 num =strtol(spec, &term,10);1876if(term != spec) {1877*ret = num;1878return term;1879}1880if(spec[0] !='/')1881return spec;18821883/* it could be a regexp of form /.../ */1884for(term = (char*) spec +1; *term && *term !='/'; term++) {1885if(*term =='\\')1886 term++;1887}1888if(*term !='/')1889return spec;18901891/* try [spec+1 .. term-1] as regexp */1892*term =0;1893 begin--;/* input is in human terms */1894 line =nth_line(sb, begin);18951896if(!(reg_error =regcomp(®exp, spec +1, REG_NEWLINE)) &&1897!(reg_error =regexec(®exp, line,1, match,0))) {1898const char*cp = line + match[0].rm_so;1899const char*nline;19001901while(begin++ < lno) {1902 nline =nth_line(sb, begin);1903if(line <= cp && cp < nline)1904break;1905 line = nline;1906}1907*ret = begin;1908regfree(®exp);1909*term++ ='/';1910return term;1911}1912else{1913char errbuf[1024];1914regerror(reg_error, ®exp, errbuf,1024);1915die("-L parameter '%s':%s", spec +1, errbuf);1916}1917}19181919/*1920 * Parsing of -L option1921 */1922static voidprepare_blame_range(struct scoreboard *sb,1923const char*bottomtop,1924long lno,1925long*bottom,long*top)1926{1927const char*term;19281929 term =parse_loc(bottomtop, sb, lno,1, bottom);1930if(*term ==',') {1931 term =parse_loc(term +1, sb, lno, *bottom +1, top);1932if(*term)1933usage(blame_usage);1934}1935if(*term)1936usage(blame_usage);1937}19381939static intgit_blame_config(const char*var,const char*value)1940{1941if(!strcmp(var,"blame.showroot")) {1942 show_root =git_config_bool(var, value);1943return0;1944}1945if(!strcmp(var,"blame.blankboundary")) {1946 blank_boundary =git_config_bool(var, value);1947return0;1948}1949returngit_default_config(var, value);1950}19511952static struct commit *fake_working_tree_commit(const char*path,const char*contents_from)1953{1954struct commit *commit;1955struct origin *origin;1956unsigned char head_sha1[20];1957char*buf;1958const char*ident;1959int fd;1960time_t now;1961unsigned long fin_size;1962int size, len;1963struct cache_entry *ce;1964unsigned mode;19651966if(get_sha1("HEAD", head_sha1))1967die("No such ref: HEAD");19681969time(&now);1970 commit =xcalloc(1,sizeof(*commit));1971 commit->parents =xcalloc(1,sizeof(*commit->parents));1972 commit->parents->item =lookup_commit_reference(head_sha1);1973 commit->object.parsed =1;1974 commit->date = now;1975 commit->object.type = OBJ_COMMIT;19761977 origin =make_origin(commit, path);19781979if(!contents_from ||strcmp("-", contents_from)) {1980struct stat st;1981const char*read_from;19821983if(contents_from) {1984if(stat(contents_from, &st) <0)1985die("Cannot stat%s", contents_from);1986 read_from = contents_from;1987}1988else{1989if(lstat(path, &st) <0)1990die("Cannot lstat%s", path);1991 read_from = path;1992}1993 fin_size =xsize_t(st.st_size);1994 buf =xmalloc(fin_size+1);1995 mode =canon_mode(st.st_mode);1996switch(st.st_mode & S_IFMT) {1997case S_IFREG:1998 fd =open(read_from, O_RDONLY);1999if(fd <0)2000die("cannot open%s", read_from);2001if(read_in_full(fd, buf, fin_size) != fin_size)2002die("cannot read%s", read_from);2003break;2004case S_IFLNK:2005if(readlink(read_from, buf, fin_size+1) != fin_size)2006die("cannot readlink%s", read_from);2007break;2008default:2009die("unsupported file type%s", read_from);2010}2011}2012else{2013/* Reading from stdin */2014 contents_from ="standard input";2015 buf = NULL;2016 fin_size =0;2017 mode =0;2018while(1) {2019 ssize_t cnt =8192;2020 buf =xrealloc(buf, fin_size + cnt);2021 cnt =xread(0, buf + fin_size, cnt);2022if(cnt <0)2023die("read error%sfrom stdin",2024strerror(errno));2025if(!cnt)2026break;2027 fin_size += cnt;2028}2029 buf =xrealloc(buf, fin_size +1);2030}2031 buf[fin_size] =0;2032 origin->file.ptr = buf;2033 origin->file.size = fin_size;2034pretend_sha1_file(buf, fin_size, OBJ_BLOB, origin->blob_sha1);2035 commit->util = origin;20362037/*2038 * Read the current index, replace the path entry with2039 * origin->blob_sha1 without mucking with its mode or type2040 * bits; we are not going to write this index out -- we just2041 * want to run "diff-index --cached".2042 */2043discard_cache();2044read_cache();20452046 len =strlen(path);2047if(!mode) {2048int pos =cache_name_pos(path, len);2049if(0<= pos)2050 mode =ntohl(active_cache[pos]->ce_mode);2051else2052/* Let's not bother reading from HEAD tree */2053 mode = S_IFREG |0644;2054}2055 size =cache_entry_size(len);2056 ce =xcalloc(1, size);2057hashcpy(ce->sha1, origin->blob_sha1);2058memcpy(ce->name, path, len);2059 ce->ce_flags =create_ce_flags(len,0);2060 ce->ce_mode =create_ce_mode(mode);2061add_cache_entry(ce, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE);20622063/*2064 * We are not going to write this out, so this does not matter2065 * right now, but someday we might optimize diff-index --cached2066 * with cache-tree information.2067 */2068cache_tree_invalidate_path(active_cache_tree, path);20692070 commit->buffer =xmalloc(400);2071 ident =fmt_ident("Not Committed Yet","not.committed.yet", NULL,0);2072snprintf(commit->buffer,400,2073"tree 0000000000000000000000000000000000000000\n"2074"parent%s\n"2075"author%s\n"2076"committer%s\n\n"2077"Version of%sfrom%s\n",2078sha1_to_hex(head_sha1),2079 ident, ident, path, contents_from ? contents_from : path);2080return commit;2081}20822083intcmd_blame(int argc,const char**argv,const char*prefix)2084{2085struct rev_info revs;2086const char*path;2087struct scoreboard sb;2088struct origin *o;2089struct blame_entry *ent;2090int i, seen_dashdash, unk, opt;2091long bottom, top, lno;2092int output_option =0;2093int show_stats =0;2094const char*revs_file = NULL;2095const char*final_commit_name = NULL;2096enum object_type type;2097const char*bottomtop = NULL;2098const char*contents_from = NULL;20992100 cmd_is_annotate = !strcmp(argv[0],"annotate");21012102git_config(git_blame_config);2103 save_commit_buffer =0;21042105 opt =0;2106 seen_dashdash =0;2107for(unk = i =1; i < argc; i++) {2108const char*arg = argv[i];2109if(*arg !='-')2110break;2111else if(!strcmp("-b", arg))2112 blank_boundary =1;2113else if(!strcmp("--root", arg))2114 show_root =1;2115else if(!strcmp(arg,"--show-stats"))2116 show_stats =1;2117else if(!strcmp("-c", arg))2118 output_option |= OUTPUT_ANNOTATE_COMPAT;2119else if(!strcmp("-t", arg))2120 output_option |= OUTPUT_RAW_TIMESTAMP;2121else if(!strcmp("-l", arg))2122 output_option |= OUTPUT_LONG_OBJECT_NAME;2123else if(!strcmp("-S", arg) && ++i < argc)2124 revs_file = argv[i];2125else if(!prefixcmp(arg,"-M")) {2126 opt |= PICKAXE_BLAME_MOVE;2127 blame_move_score =parse_score(arg+2);2128}2129else if(!prefixcmp(arg,"-C")) {2130if(opt & PICKAXE_BLAME_COPY)2131 opt |= PICKAXE_BLAME_COPY_HARDER;2132 opt |= PICKAXE_BLAME_COPY | PICKAXE_BLAME_MOVE;2133 blame_copy_score =parse_score(arg+2);2134}2135else if(!prefixcmp(arg,"-L")) {2136if(!arg[2]) {2137if(++i >= argc)2138usage(blame_usage);2139 arg = argv[i];2140}2141else2142 arg +=2;2143if(bottomtop)2144die("More than one '-L n,m' option given");2145 bottomtop = arg;2146}2147else if(!strcmp("--contents", arg)) {2148if(++i >= argc)2149usage(blame_usage);2150 contents_from = argv[i];2151}2152else if(!strcmp("--incremental", arg))2153 incremental =1;2154else if(!strcmp("--score-debug", arg))2155 output_option |= OUTPUT_SHOW_SCORE;2156else if(!strcmp("-f", arg) ||2157!strcmp("--show-name", arg))2158 output_option |= OUTPUT_SHOW_NAME;2159else if(!strcmp("-n", arg) ||2160!strcmp("--show-number", arg))2161 output_option |= OUTPUT_SHOW_NUMBER;2162else if(!strcmp("-p", arg) ||2163!strcmp("--porcelain", arg))2164 output_option |= OUTPUT_PORCELAIN;2165else if(!strcmp("--", arg)) {2166 seen_dashdash =1;2167 i++;2168break;2169}2170else2171 argv[unk++] = arg;2172}21732174if(!incremental)2175setup_pager();21762177if(!blame_move_score)2178 blame_move_score = BLAME_DEFAULT_MOVE_SCORE;2179if(!blame_copy_score)2180 blame_copy_score = BLAME_DEFAULT_COPY_SCORE;21812182/*2183 * We have collected options unknown to us in argv[1..unk]2184 * which are to be passed to revision machinery if we are2185 * going to do the "bottom" processing.2186 *2187 * The remaining are:2188 *2189 * (1) if seen_dashdash, its either2190 * "-options -- <path>" or2191 * "-options -- <path> <rev>".2192 * but the latter is allowed only if there is no2193 * options that we passed to revision machinery.2194 *2195 * (2) otherwise, we may have "--" somewhere later and2196 * might be looking at the first one of multiple 'rev'2197 * parameters (e.g. " master ^next ^maint -- path").2198 * See if there is a dashdash first, and give the2199 * arguments before that to revision machinery.2200 * After that there must be one 'path'.2201 *2202 * (3) otherwise, its one of the three:2203 * "-options <path> <rev>"2204 * "-options <rev> <path>"2205 * "-options <path>"2206 * but again the first one is allowed only if2207 * there is no options that we passed to revision2208 * machinery.2209 */22102211if(seen_dashdash) {2212/* (1) */2213if(argc <= i)2214usage(blame_usage);2215 path =add_prefix(prefix, argv[i]);2216if(i +1== argc -1) {2217if(unk !=1)2218usage(blame_usage);2219 argv[unk++] = argv[i +1];2220}2221else if(i +1!= argc)2222/* garbage at end */2223usage(blame_usage);2224}2225else{2226int j;2227for(j = i; !seen_dashdash && j < argc; j++)2228if(!strcmp(argv[j],"--"))2229 seen_dashdash = j;2230if(seen_dashdash) {2231/* (2) */2232if(seen_dashdash +1!= argc -1)2233usage(blame_usage);2234 path =add_prefix(prefix, argv[seen_dashdash +1]);2235for(j = i; j < seen_dashdash; j++)2236 argv[unk++] = argv[j];2237}2238else{2239/* (3) */2240if(argc <= i)2241usage(blame_usage);2242 path =add_prefix(prefix, argv[i]);2243if(i +1== argc -1) {2244 final_commit_name = argv[i +1];22452246/* if (unk == 1) we could be getting2247 * old-style2248 */2249if(unk ==1&& !has_path_in_work_tree(path)) {2250 path =add_prefix(prefix, argv[i +1]);2251 final_commit_name = argv[i];2252}2253}2254else if(i != argc -1)2255usage(blame_usage);/* garbage at end */22562257if(!has_path_in_work_tree(path))2258die("cannot stat path%s:%s",2259 path,strerror(errno));2260}2261}22622263if(final_commit_name)2264 argv[unk++] = final_commit_name;22652266/*2267 * Now we got rev and path. We do not want the path pruning2268 * but we may want "bottom" processing.2269 */2270 argv[unk++] ="--";/* terminate the rev name */2271 argv[unk] = NULL;22722273init_revisions(&revs, NULL);2274setup_revisions(unk, argv, &revs, NULL);2275memset(&sb,0,sizeof(sb));22762277/*2278 * There must be one and only one positive commit in the2279 * revs->pending array.2280 */2281for(i =0; i < revs.pending.nr; i++) {2282struct object *obj = revs.pending.objects[i].item;2283if(obj->flags & UNINTERESTING)2284continue;2285while(obj->type == OBJ_TAG)2286 obj =deref_tag(obj, NULL,0);2287if(obj->type != OBJ_COMMIT)2288die("Non commit%s?",2289 revs.pending.objects[i].name);2290if(sb.final)2291die("More than one commit to dig from%sand%s?",2292 revs.pending.objects[i].name,2293 final_commit_name);2294 sb.final = (struct commit *) obj;2295 final_commit_name = revs.pending.objects[i].name;2296}22972298if(!sb.final) {2299/*2300 * "--not A B -- path" without anything positive;2301 * do not default to HEAD, but use the working tree2302 * or "--contents".2303 */2304 sb.final =fake_working_tree_commit(path, contents_from);2305add_pending_object(&revs, &(sb.final->object),":");2306}2307else if(contents_from)2308die("Cannot use --contents with final commit object name");23092310/*2311 * If we have bottom, this will mark the ancestors of the2312 * bottom commits we would reach while traversing as2313 * uninteresting.2314 */2315prepare_revision_walk(&revs);23162317if(is_null_sha1(sb.final->object.sha1)) {2318char*buf;2319 o = sb.final->util;2320 buf =xmalloc(o->file.size +1);2321memcpy(buf, o->file.ptr, o->file.size +1);2322 sb.final_buf = buf;2323 sb.final_buf_size = o->file.size;2324}2325else{2326 o =get_origin(&sb, sb.final, path);2327if(fill_blob_sha1(o))2328die("no such path%sin%s", path, final_commit_name);23292330 sb.final_buf =read_sha1_file(o->blob_sha1, &type,2331&sb.final_buf_size);2332}2333 num_read_blob++;2334 lno =prepare_lines(&sb);23352336 bottom = top =0;2337if(bottomtop)2338prepare_blame_range(&sb, bottomtop, lno, &bottom, &top);2339if(bottom && top && top < bottom) {2340long tmp;2341 tmp = top; top = bottom; bottom = tmp;2342}2343if(bottom <1)2344 bottom =1;2345if(top <1)2346 top = lno;2347 bottom--;2348if(lno < top)2349die("file%shas only%lu lines", path, lno);23502351 ent =xcalloc(1,sizeof(*ent));2352 ent->lno = bottom;2353 ent->num_lines = top - bottom;2354 ent->suspect = o;2355 ent->s_lno = bottom;23562357 sb.ent = ent;2358 sb.path = path;23592360if(revs_file &&read_ancestry(revs_file))2361die("reading graft file%sfailed:%s",2362 revs_file,strerror(errno));23632364assign_blame(&sb, &revs, opt);23652366if(incremental)2367return0;23682369coalesce(&sb);23702371if(!(output_option & OUTPUT_PORCELAIN))2372find_alignment(&sb, &output_option);23732374output(&sb, output_option);2375free((void*)sb.final_buf);2376for(ent = sb.ent; ent; ) {2377struct blame_entry *e = ent->next;2378free(ent);2379 ent = e;2380}23812382if(show_stats) {2383printf("num read blob:%d\n", num_read_blob);2384printf("num get patch:%d\n", num_get_patch);2385printf("num commits:%d\n", num_commits);2386}2387return0;2388}