1#include"cache.h" 2#include"refs.h" 3#include"cache-tree.h" 4#include"mergesort.h" 5#include"diff.h" 6#include"diffcore.h" 7#include"tag.h" 8#include"blame.h" 9 10voidblame_origin_decref(struct blame_origin *o) 11{ 12if(o && --o->refcnt <=0) { 13struct blame_origin *p, *l = NULL; 14if(o->previous) 15blame_origin_decref(o->previous); 16free(o->file.ptr); 17/* Should be present exactly once in commit chain */ 18for(p = o->commit->util; p; l = p, p = p->next) { 19if(p == o) { 20if(l) 21 l->next = p->next; 22else 23 o->commit->util = p->next; 24free(o); 25return; 26} 27} 28die("internal error in blame_origin_decref"); 29} 30} 31 32/* 33 * Given a commit and a path in it, create a new origin structure. 34 * The callers that add blame to the scoreboard should use 35 * get_origin() to obtain shared, refcounted copy instead of calling 36 * this function directly. 37 */ 38static struct blame_origin *make_origin(struct commit *commit,const char*path) 39{ 40struct blame_origin *o; 41FLEX_ALLOC_STR(o, path, path); 42 o->commit = commit; 43 o->refcnt =1; 44 o->next = commit->util; 45 commit->util = o; 46return o; 47} 48 49/* 50 * Locate an existing origin or create a new one. 51 * This moves the origin to front position in the commit util list. 52 */ 53static struct blame_origin *get_origin(struct commit *commit,const char*path) 54{ 55struct blame_origin *o, *l; 56 57for(o = commit->util, l = NULL; o; l = o, o = o->next) { 58if(!strcmp(o->path, path)) { 59/* bump to front */ 60if(l) { 61 l->next = o->next; 62 o->next = commit->util; 63 commit->util = o; 64} 65returnblame_origin_incref(o); 66} 67} 68returnmake_origin(commit, path); 69} 70 71 72 73static voidverify_working_tree_path(struct commit *work_tree,const char*path) 74{ 75struct commit_list *parents; 76int pos; 77 78for(parents = work_tree->parents; parents; parents = parents->next) { 79const struct object_id *commit_oid = &parents->item->object.oid; 80struct object_id blob_oid; 81unsigned mode; 82 83if(!get_tree_entry(commit_oid, path, &blob_oid, &mode) && 84oid_object_info(the_repository, &blob_oid, NULL) == OBJ_BLOB) 85return; 86} 87 88 pos =cache_name_pos(path,strlen(path)); 89if(pos >=0) 90;/* path is in the index */ 91else if(-1- pos < active_nr && 92!strcmp(active_cache[-1- pos]->name, path)) 93;/* path is in the index, unmerged */ 94else 95die("no such path '%s' in HEAD", path); 96} 97 98static struct commit_list **append_parent(struct commit_list **tail,const struct object_id *oid) 99{ 100struct commit *parent; 101 102 parent =lookup_commit_reference(oid); 103if(!parent) 104die("no such commit%s",oid_to_hex(oid)); 105return&commit_list_insert(parent, tail)->next; 106} 107 108static voidappend_merge_parents(struct commit_list **tail) 109{ 110int merge_head; 111struct strbuf line = STRBUF_INIT; 112 113 merge_head =open(git_path_merge_head(), O_RDONLY); 114if(merge_head <0) { 115if(errno == ENOENT) 116return; 117die("cannot open '%s' for reading",git_path_merge_head()); 118} 119 120while(!strbuf_getwholeline_fd(&line, merge_head,'\n')) { 121struct object_id oid; 122if(line.len < GIT_SHA1_HEXSZ ||get_oid_hex(line.buf, &oid)) 123die("unknown line in '%s':%s",git_path_merge_head(), line.buf); 124 tail =append_parent(tail, &oid); 125} 126close(merge_head); 127strbuf_release(&line); 128} 129 130/* 131 * This isn't as simple as passing sb->buf and sb->len, because we 132 * want to transfer ownership of the buffer to the commit (so we 133 * must use detach). 134 */ 135static voidset_commit_buffer_from_strbuf(struct commit *c,struct strbuf *sb) 136{ 137size_t len; 138void*buf =strbuf_detach(sb, &len); 139set_commit_buffer(c, buf, len); 140} 141 142/* 143 * Prepare a dummy commit that represents the work tree (or staged) item. 144 * Note that annotating work tree item never works in the reverse. 145 */ 146static struct commit *fake_working_tree_commit(struct diff_options *opt, 147const char*path, 148const char*contents_from) 149{ 150struct commit *commit; 151struct blame_origin *origin; 152struct commit_list **parent_tail, *parent; 153struct object_id head_oid; 154struct strbuf buf = STRBUF_INIT; 155const char*ident; 156time_t now; 157int len; 158struct cache_entry *ce; 159unsigned mode; 160struct strbuf msg = STRBUF_INIT; 161 162read_cache(); 163time(&now); 164 commit =alloc_commit_node(); 165 commit->object.parsed =1; 166 commit->date = now; 167 parent_tail = &commit->parents; 168 169if(!resolve_ref_unsafe("HEAD", RESOLVE_REF_READING, &head_oid, NULL)) 170die("no such ref: HEAD"); 171 172 parent_tail =append_parent(parent_tail, &head_oid); 173append_merge_parents(parent_tail); 174verify_working_tree_path(commit, path); 175 176 origin =make_origin(commit, path); 177 178 ident =fmt_ident("Not Committed Yet","not.committed.yet", NULL,0); 179strbuf_addstr(&msg,"tree 0000000000000000000000000000000000000000\n"); 180for(parent = commit->parents; parent; parent = parent->next) 181strbuf_addf(&msg,"parent%s\n", 182oid_to_hex(&parent->item->object.oid)); 183strbuf_addf(&msg, 184"author%s\n" 185"committer%s\n\n" 186"Version of%sfrom%s\n", 187 ident, ident, path, 188(!contents_from ? path : 189(!strcmp(contents_from,"-") ?"standard input": contents_from))); 190set_commit_buffer_from_strbuf(commit, &msg); 191 192if(!contents_from ||strcmp("-", contents_from)) { 193struct stat st; 194const char*read_from; 195char*buf_ptr; 196unsigned long buf_len; 197 198if(contents_from) { 199if(stat(contents_from, &st) <0) 200die_errno("Cannot stat '%s'", contents_from); 201 read_from = contents_from; 202} 203else{ 204if(lstat(path, &st) <0) 205die_errno("Cannot lstat '%s'", path); 206 read_from = path; 207} 208 mode =canon_mode(st.st_mode); 209 210switch(st.st_mode & S_IFMT) { 211case S_IFREG: 212if(opt->flags.allow_textconv && 213textconv_object(read_from, mode, &null_oid,0, &buf_ptr, &buf_len)) 214strbuf_attach(&buf, buf_ptr, buf_len, buf_len +1); 215else if(strbuf_read_file(&buf, read_from, st.st_size) != st.st_size) 216die_errno("cannot open or read '%s'", read_from); 217break; 218case S_IFLNK: 219if(strbuf_readlink(&buf, read_from, st.st_size) <0) 220die_errno("cannot readlink '%s'", read_from); 221break; 222default: 223die("unsupported file type%s", read_from); 224} 225} 226else{ 227/* Reading from stdin */ 228 mode =0; 229if(strbuf_read(&buf,0,0) <0) 230die_errno("failed to read from stdin"); 231} 232convert_to_git(&the_index, path, buf.buf, buf.len, &buf,0); 233 origin->file.ptr = buf.buf; 234 origin->file.size = buf.len; 235pretend_object_file(buf.buf, buf.len, OBJ_BLOB, &origin->blob_oid); 236 237/* 238 * Read the current index, replace the path entry with 239 * origin->blob_sha1 without mucking with its mode or type 240 * bits; we are not going to write this index out -- we just 241 * want to run "diff-index --cached". 242 */ 243discard_cache(); 244read_cache(); 245 246 len =strlen(path); 247if(!mode) { 248int pos =cache_name_pos(path, len); 249if(0<= pos) 250 mode = active_cache[pos]->ce_mode; 251else 252/* Let's not bother reading from HEAD tree */ 253 mode = S_IFREG |0644; 254} 255 ce =make_empty_cache_entry(&the_index, len); 256oidcpy(&ce->oid, &origin->blob_oid); 257memcpy(ce->name, path, len); 258 ce->ce_flags =create_ce_flags(0); 259 ce->ce_namelen = len; 260 ce->ce_mode =create_ce_mode(mode); 261add_cache_entry(ce, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE); 262 263cache_tree_invalidate_path(&the_index, path); 264 265return commit; 266} 267 268 269 270static intdiff_hunks(mmfile_t *file_a, mmfile_t *file_b, 271 xdl_emit_hunk_consume_func_t hunk_func,void*cb_data,int xdl_opts) 272{ 273 xpparam_t xpp = {0}; 274 xdemitconf_t xecfg = {0}; 275 xdemitcb_t ecb = {NULL}; 276 277 xpp.flags = xdl_opts; 278 xecfg.hunk_func = hunk_func; 279 ecb.priv = cb_data; 280returnxdi_diff(file_a, file_b, &xpp, &xecfg, &ecb); 281} 282 283/* 284 * Given an origin, prepare mmfile_t structure to be used by the 285 * diff machinery 286 */ 287static voidfill_origin_blob(struct diff_options *opt, 288struct blame_origin *o, mmfile_t *file,int*num_read_blob) 289{ 290if(!o->file.ptr) { 291enum object_type type; 292unsigned long file_size; 293 294(*num_read_blob)++; 295if(opt->flags.allow_textconv && 296textconv_object(o->path, o->mode, &o->blob_oid,1, &file->ptr, &file_size)) 297; 298else 299 file->ptr =read_object_file(&o->blob_oid, &type, 300&file_size); 301 file->size = file_size; 302 303if(!file->ptr) 304die("Cannot read blob%sfor path%s", 305oid_to_hex(&o->blob_oid), 306 o->path); 307 o->file = *file; 308} 309else 310*file = o->file; 311} 312 313static voiddrop_origin_blob(struct blame_origin *o) 314{ 315if(o->file.ptr) { 316FREE_AND_NULL(o->file.ptr); 317} 318} 319 320/* 321 * Any merge of blames happens on lists of blames that arrived via 322 * different parents in a single suspect. In this case, we want to 323 * sort according to the suspect line numbers as opposed to the final 324 * image line numbers. The function body is somewhat longish because 325 * it avoids unnecessary writes. 326 */ 327 328static struct blame_entry *blame_merge(struct blame_entry *list1, 329struct blame_entry *list2) 330{ 331struct blame_entry *p1 = list1, *p2 = list2, 332**tail = &list1; 333 334if(!p1) 335return p2; 336if(!p2) 337return p1; 338 339if(p1->s_lno <= p2->s_lno) { 340do{ 341 tail = &p1->next; 342if((p1 = *tail) == NULL) { 343*tail = p2; 344return list1; 345} 346}while(p1->s_lno <= p2->s_lno); 347} 348for(;;) { 349*tail = p2; 350do{ 351 tail = &p2->next; 352if((p2 = *tail) == NULL) { 353*tail = p1; 354return list1; 355} 356}while(p1->s_lno > p2->s_lno); 357*tail = p1; 358do{ 359 tail = &p1->next; 360if((p1 = *tail) == NULL) { 361*tail = p2; 362return list1; 363} 364}while(p1->s_lno <= p2->s_lno); 365} 366} 367 368static void*get_next_blame(const void*p) 369{ 370return((struct blame_entry *)p)->next; 371} 372 373static voidset_next_blame(void*p1,void*p2) 374{ 375((struct blame_entry *)p1)->next = p2; 376} 377 378/* 379 * Final image line numbers are all different, so we don't need a 380 * three-way comparison here. 381 */ 382 383static intcompare_blame_final(const void*p1,const void*p2) 384{ 385return((struct blame_entry *)p1)->lno > ((struct blame_entry *)p2)->lno 386?1: -1; 387} 388 389static intcompare_blame_suspect(const void*p1,const void*p2) 390{ 391const struct blame_entry *s1 = p1, *s2 = p2; 392/* 393 * to allow for collating suspects, we sort according to the 394 * respective pointer value as the primary sorting criterion. 395 * The actual relation is pretty unimportant as long as it 396 * establishes a total order. Comparing as integers gives us 397 * that. 398 */ 399if(s1->suspect != s2->suspect) 400return(intptr_t)s1->suspect > (intptr_t)s2->suspect ?1: -1; 401if(s1->s_lno == s2->s_lno) 402return0; 403return s1->s_lno > s2->s_lno ?1: -1; 404} 405 406voidblame_sort_final(struct blame_scoreboard *sb) 407{ 408 sb->ent =llist_mergesort(sb->ent, get_next_blame, set_next_blame, 409 compare_blame_final); 410} 411 412static intcompare_commits_by_reverse_commit_date(const void*a, 413const void*b, 414void*c) 415{ 416return-compare_commits_by_commit_date(a, b, c); 417} 418 419/* 420 * For debugging -- origin is refcounted, and this asserts that 421 * we do not underflow. 422 */ 423static voidsanity_check_refcnt(struct blame_scoreboard *sb) 424{ 425int baa =0; 426struct blame_entry *ent; 427 428for(ent = sb->ent; ent; ent = ent->next) { 429/* Nobody should have zero or negative refcnt */ 430if(ent->suspect->refcnt <=0) { 431fprintf(stderr,"%sin%shas negative refcnt%d\n", 432 ent->suspect->path, 433oid_to_hex(&ent->suspect->commit->object.oid), 434 ent->suspect->refcnt); 435 baa =1; 436} 437} 438if(baa) 439 sb->on_sanity_fail(sb, baa); 440} 441 442/* 443 * If two blame entries that are next to each other came from 444 * contiguous lines in the same origin (i.e. <commit, path> pair), 445 * merge them together. 446 */ 447voidblame_coalesce(struct blame_scoreboard *sb) 448{ 449struct blame_entry *ent, *next; 450 451for(ent = sb->ent; ent && (next = ent->next); ent = next) { 452if(ent->suspect == next->suspect && 453 ent->s_lno + ent->num_lines == next->s_lno) { 454 ent->num_lines += next->num_lines; 455 ent->next = next->next; 456blame_origin_decref(next->suspect); 457free(next); 458 ent->score =0; 459 next = ent;/* again */ 460} 461} 462 463if(sb->debug)/* sanity */ 464sanity_check_refcnt(sb); 465} 466 467/* 468 * Merge the given sorted list of blames into a preexisting origin. 469 * If there were no previous blames to that commit, it is entered into 470 * the commit priority queue of the score board. 471 */ 472 473static voidqueue_blames(struct blame_scoreboard *sb,struct blame_origin *porigin, 474struct blame_entry *sorted) 475{ 476if(porigin->suspects) 477 porigin->suspects =blame_merge(porigin->suspects, sorted); 478else{ 479struct blame_origin *o; 480for(o = porigin->commit->util; o; o = o->next) { 481if(o->suspects) { 482 porigin->suspects = sorted; 483return; 484} 485} 486 porigin->suspects = sorted; 487prio_queue_put(&sb->commits, porigin->commit); 488} 489} 490 491/* 492 * Fill the blob_sha1 field of an origin if it hasn't, so that later 493 * call to fill_origin_blob() can use it to locate the data. blob_sha1 494 * for an origin is also used to pass the blame for the entire file to 495 * the parent to detect the case where a child's blob is identical to 496 * that of its parent's. 497 * 498 * This also fills origin->mode for corresponding tree path. 499 */ 500static intfill_blob_sha1_and_mode(struct blame_origin *origin) 501{ 502if(!is_null_oid(&origin->blob_oid)) 503return0; 504if(get_tree_entry(&origin->commit->object.oid, origin->path, &origin->blob_oid, &origin->mode)) 505goto error_out; 506if(oid_object_info(the_repository, &origin->blob_oid, NULL) != OBJ_BLOB) 507goto error_out; 508return0; 509 error_out: 510oidclr(&origin->blob_oid); 511 origin->mode = S_IFINVALID; 512return-1; 513} 514 515/* 516 * We have an origin -- check if the same path exists in the 517 * parent and return an origin structure to represent it. 518 */ 519static struct blame_origin *find_origin(struct commit *parent, 520struct blame_origin *origin) 521{ 522struct blame_origin *porigin; 523struct diff_options diff_opts; 524const char*paths[2]; 525 526/* First check any existing origins */ 527for(porigin = parent->util; porigin; porigin = porigin->next) 528if(!strcmp(porigin->path, origin->path)) { 529/* 530 * The same path between origin and its parent 531 * without renaming -- the most common case. 532 */ 533returnblame_origin_incref(porigin); 534} 535 536/* See if the origin->path is different between parent 537 * and origin first. Most of the time they are the 538 * same and diff-tree is fairly efficient about this. 539 */ 540diff_setup(&diff_opts); 541 diff_opts.flags.recursive =1; 542 diff_opts.detect_rename =0; 543 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT; 544 paths[0] = origin->path; 545 paths[1] = NULL; 546 547parse_pathspec(&diff_opts.pathspec, 548 PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL, 549 PATHSPEC_LITERAL_PATH,"", paths); 550diff_setup_done(&diff_opts); 551 552if(is_null_oid(&origin->commit->object.oid)) 553do_diff_cache(get_commit_tree_oid(parent), &diff_opts); 554else 555diff_tree_oid(get_commit_tree_oid(parent), 556get_commit_tree_oid(origin->commit), 557"", &diff_opts); 558diffcore_std(&diff_opts); 559 560if(!diff_queued_diff.nr) { 561/* The path is the same as parent */ 562 porigin =get_origin(parent, origin->path); 563oidcpy(&porigin->blob_oid, &origin->blob_oid); 564 porigin->mode = origin->mode; 565}else{ 566/* 567 * Since origin->path is a pathspec, if the parent 568 * commit had it as a directory, we will see a whole 569 * bunch of deletion of files in the directory that we 570 * do not care about. 571 */ 572int i; 573struct diff_filepair *p = NULL; 574for(i =0; i < diff_queued_diff.nr; i++) { 575const char*name; 576 p = diff_queued_diff.queue[i]; 577 name = p->one->path ? p->one->path : p->two->path; 578if(!strcmp(name, origin->path)) 579break; 580} 581if(!p) 582die("internal error in blame::find_origin"); 583switch(p->status) { 584default: 585die("internal error in blame::find_origin (%c)", 586 p->status); 587case'M': 588 porigin =get_origin(parent, origin->path); 589oidcpy(&porigin->blob_oid, &p->one->oid); 590 porigin->mode = p->one->mode; 591break; 592case'A': 593case'T': 594/* Did not exist in parent, or type changed */ 595break; 596} 597} 598diff_flush(&diff_opts); 599clear_pathspec(&diff_opts.pathspec); 600return porigin; 601} 602 603/* 604 * We have an origin -- find the path that corresponds to it in its 605 * parent and return an origin structure to represent it. 606 */ 607static struct blame_origin *find_rename(struct commit *parent, 608struct blame_origin *origin) 609{ 610struct blame_origin *porigin = NULL; 611struct diff_options diff_opts; 612int i; 613 614diff_setup(&diff_opts); 615 diff_opts.flags.recursive =1; 616 diff_opts.detect_rename = DIFF_DETECT_RENAME; 617 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT; 618 diff_opts.single_follow = origin->path; 619diff_setup_done(&diff_opts); 620 621if(is_null_oid(&origin->commit->object.oid)) 622do_diff_cache(get_commit_tree_oid(parent), &diff_opts); 623else 624diff_tree_oid(get_commit_tree_oid(parent), 625get_commit_tree_oid(origin->commit), 626"", &diff_opts); 627diffcore_std(&diff_opts); 628 629for(i =0; i < diff_queued_diff.nr; i++) { 630struct diff_filepair *p = diff_queued_diff.queue[i]; 631if((p->status =='R'|| p->status =='C') && 632!strcmp(p->two->path, origin->path)) { 633 porigin =get_origin(parent, p->one->path); 634oidcpy(&porigin->blob_oid, &p->one->oid); 635 porigin->mode = p->one->mode; 636break; 637} 638} 639diff_flush(&diff_opts); 640clear_pathspec(&diff_opts.pathspec); 641return porigin; 642} 643 644/* 645 * Append a new blame entry to a given output queue. 646 */ 647static voidadd_blame_entry(struct blame_entry ***queue, 648const struct blame_entry *src) 649{ 650struct blame_entry *e =xmalloc(sizeof(*e)); 651memcpy(e, src,sizeof(*e)); 652blame_origin_incref(e->suspect); 653 654 e->next = **queue; 655**queue = e; 656*queue = &e->next; 657} 658 659/* 660 * src typically is on-stack; we want to copy the information in it to 661 * a malloced blame_entry that gets added to the given queue. The 662 * origin of dst loses a refcnt. 663 */ 664static voiddup_entry(struct blame_entry ***queue, 665struct blame_entry *dst,struct blame_entry *src) 666{ 667blame_origin_incref(src->suspect); 668blame_origin_decref(dst->suspect); 669memcpy(dst, src,sizeof(*src)); 670 dst->next = **queue; 671**queue = dst; 672*queue = &dst->next; 673} 674 675const char*blame_nth_line(struct blame_scoreboard *sb,long lno) 676{ 677return sb->final_buf + sb->lineno[lno]; 678} 679 680/* 681 * It is known that lines between tlno to same came from parent, and e 682 * has an overlap with that range. it also is known that parent's 683 * line plno corresponds to e's line tlno. 684 * 685 * <---- e -----> 686 * <------> 687 * <------------> 688 * <------------> 689 * <------------------> 690 * 691 * Split e into potentially three parts; before this chunk, the chunk 692 * to be blamed for the parent, and after that portion. 693 */ 694static voidsplit_overlap(struct blame_entry *split, 695struct blame_entry *e, 696int tlno,int plno,int same, 697struct blame_origin *parent) 698{ 699int chunk_end_lno; 700memset(split,0,sizeof(struct blame_entry [3])); 701 702if(e->s_lno < tlno) { 703/* there is a pre-chunk part not blamed on parent */ 704 split[0].suspect =blame_origin_incref(e->suspect); 705 split[0].lno = e->lno; 706 split[0].s_lno = e->s_lno; 707 split[0].num_lines = tlno - e->s_lno; 708 split[1].lno = e->lno + tlno - e->s_lno; 709 split[1].s_lno = plno; 710} 711else{ 712 split[1].lno = e->lno; 713 split[1].s_lno = plno + (e->s_lno - tlno); 714} 715 716if(same < e->s_lno + e->num_lines) { 717/* there is a post-chunk part not blamed on parent */ 718 split[2].suspect =blame_origin_incref(e->suspect); 719 split[2].lno = e->lno + (same - e->s_lno); 720 split[2].s_lno = e->s_lno + (same - e->s_lno); 721 split[2].num_lines = e->s_lno + e->num_lines - same; 722 chunk_end_lno = split[2].lno; 723} 724else 725 chunk_end_lno = e->lno + e->num_lines; 726 split[1].num_lines = chunk_end_lno - split[1].lno; 727 728/* 729 * if it turns out there is nothing to blame the parent for, 730 * forget about the splitting. !split[1].suspect signals this. 731 */ 732if(split[1].num_lines <1) 733return; 734 split[1].suspect =blame_origin_incref(parent); 735} 736 737/* 738 * split_overlap() divided an existing blame e into up to three parts 739 * in split. Any assigned blame is moved to queue to 740 * reflect the split. 741 */ 742static voidsplit_blame(struct blame_entry ***blamed, 743struct blame_entry ***unblamed, 744struct blame_entry *split, 745struct blame_entry *e) 746{ 747if(split[0].suspect && split[2].suspect) { 748/* The first part (reuse storage for the existing entry e) */ 749dup_entry(unblamed, e, &split[0]); 750 751/* The last part -- me */ 752add_blame_entry(unblamed, &split[2]); 753 754/* ... and the middle part -- parent */ 755add_blame_entry(blamed, &split[1]); 756} 757else if(!split[0].suspect && !split[2].suspect) 758/* 759 * The parent covers the entire area; reuse storage for 760 * e and replace it with the parent. 761 */ 762dup_entry(blamed, e, &split[1]); 763else if(split[0].suspect) { 764/* me and then parent */ 765dup_entry(unblamed, e, &split[0]); 766add_blame_entry(blamed, &split[1]); 767} 768else{ 769/* parent and then me */ 770dup_entry(blamed, e, &split[1]); 771add_blame_entry(unblamed, &split[2]); 772} 773} 774 775/* 776 * After splitting the blame, the origins used by the 777 * on-stack blame_entry should lose one refcnt each. 778 */ 779static voiddecref_split(struct blame_entry *split) 780{ 781int i; 782 783for(i =0; i <3; i++) 784blame_origin_decref(split[i].suspect); 785} 786 787/* 788 * reverse_blame reverses the list given in head, appending tail. 789 * That allows us to build lists in reverse order, then reverse them 790 * afterwards. This can be faster than building the list in proper 791 * order right away. The reason is that building in proper order 792 * requires writing a link in the _previous_ element, while building 793 * in reverse order just requires placing the list head into the 794 * _current_ element. 795 */ 796 797static struct blame_entry *reverse_blame(struct blame_entry *head, 798struct blame_entry *tail) 799{ 800while(head) { 801struct blame_entry *next = head->next; 802 head->next = tail; 803 tail = head; 804 head = next; 805} 806return tail; 807} 808 809/* 810 * Process one hunk from the patch between the current suspect for 811 * blame_entry e and its parent. This first blames any unfinished 812 * entries before the chunk (which is where target and parent start 813 * differing) on the parent, and then splits blame entries at the 814 * start and at the end of the difference region. Since use of -M and 815 * -C options may lead to overlapping/duplicate source line number 816 * ranges, all we can rely on from sorting/merging is the order of the 817 * first suspect line number. 818 */ 819static voidblame_chunk(struct blame_entry ***dstq,struct blame_entry ***srcq, 820int tlno,int offset,int same, 821struct blame_origin *parent) 822{ 823struct blame_entry *e = **srcq; 824struct blame_entry *samep = NULL, *diffp = NULL; 825 826while(e && e->s_lno < tlno) { 827struct blame_entry *next = e->next; 828/* 829 * current record starts before differing portion. If 830 * it reaches into it, we need to split it up and 831 * examine the second part separately. 832 */ 833if(e->s_lno + e->num_lines > tlno) { 834/* Move second half to a new record */ 835int len = tlno - e->s_lno; 836struct blame_entry *n =xcalloc(1,sizeof(struct blame_entry)); 837 n->suspect = e->suspect; 838 n->lno = e->lno + len; 839 n->s_lno = e->s_lno + len; 840 n->num_lines = e->num_lines - len; 841 e->num_lines = len; 842 e->score =0; 843/* Push new record to diffp */ 844 n->next = diffp; 845 diffp = n; 846}else 847blame_origin_decref(e->suspect); 848/* Pass blame for everything before the differing 849 * chunk to the parent */ 850 e->suspect =blame_origin_incref(parent); 851 e->s_lno += offset; 852 e->next = samep; 853 samep = e; 854 e = next; 855} 856/* 857 * As we don't know how much of a common stretch after this 858 * diff will occur, the currently blamed parts are all that we 859 * can assign to the parent for now. 860 */ 861 862if(samep) { 863**dstq =reverse_blame(samep, **dstq); 864*dstq = &samep->next; 865} 866/* 867 * Prepend the split off portions: everything after e starts 868 * after the blameable portion. 869 */ 870 e =reverse_blame(diffp, e); 871 872/* 873 * Now retain records on the target while parts are different 874 * from the parent. 875 */ 876 samep = NULL; 877 diffp = NULL; 878while(e && e->s_lno < same) { 879struct blame_entry *next = e->next; 880 881/* 882 * If current record extends into sameness, need to split. 883 */ 884if(e->s_lno + e->num_lines > same) { 885/* 886 * Move second half to a new record to be 887 * processed by later chunks 888 */ 889int len = same - e->s_lno; 890struct blame_entry *n =xcalloc(1,sizeof(struct blame_entry)); 891 n->suspect =blame_origin_incref(e->suspect); 892 n->lno = e->lno + len; 893 n->s_lno = e->s_lno + len; 894 n->num_lines = e->num_lines - len; 895 e->num_lines = len; 896 e->score =0; 897/* Push new record to samep */ 898 n->next = samep; 899 samep = n; 900} 901 e->next = diffp; 902 diffp = e; 903 e = next; 904} 905**srcq =reverse_blame(diffp,reverse_blame(samep, e)); 906/* Move across elements that are in the unblamable portion */ 907if(diffp) 908*srcq = &diffp->next; 909} 910 911struct blame_chunk_cb_data { 912struct blame_origin *parent; 913long offset; 914struct blame_entry **dstq; 915struct blame_entry **srcq; 916}; 917 918/* diff chunks are from parent to target */ 919static intblame_chunk_cb(long start_a,long count_a, 920long start_b,long count_b,void*data) 921{ 922struct blame_chunk_cb_data *d = data; 923if(start_a - start_b != d->offset) 924die("internal error in blame::blame_chunk_cb"); 925blame_chunk(&d->dstq, &d->srcq, start_b, start_a - start_b, 926 start_b + count_b, d->parent); 927 d->offset = start_a + count_a - (start_b + count_b); 928return0; 929} 930 931/* 932 * We are looking at the origin 'target' and aiming to pass blame 933 * for the lines it is suspected to its parent. Run diff to find 934 * which lines came from parent and pass blame for them. 935 */ 936static voidpass_blame_to_parent(struct blame_scoreboard *sb, 937struct blame_origin *target, 938struct blame_origin *parent) 939{ 940 mmfile_t file_p, file_o; 941struct blame_chunk_cb_data d; 942struct blame_entry *newdest = NULL; 943 944if(!target->suspects) 945return;/* nothing remains for this target */ 946 947 d.parent = parent; 948 d.offset =0; 949 d.dstq = &newdest; d.srcq = &target->suspects; 950 951fill_origin_blob(&sb->revs->diffopt, parent, &file_p, &sb->num_read_blob); 952fill_origin_blob(&sb->revs->diffopt, target, &file_o, &sb->num_read_blob); 953 sb->num_get_patch++; 954 955if(diff_hunks(&file_p, &file_o, blame_chunk_cb, &d, sb->xdl_opts)) 956die("unable to generate diff (%s->%s)", 957oid_to_hex(&parent->commit->object.oid), 958oid_to_hex(&target->commit->object.oid)); 959/* The rest are the same as the parent */ 960blame_chunk(&d.dstq, &d.srcq, INT_MAX, d.offset, INT_MAX, parent); 961*d.dstq = NULL; 962queue_blames(sb, parent, newdest); 963 964return; 965} 966 967/* 968 * The lines in blame_entry after splitting blames many times can become 969 * very small and trivial, and at some point it becomes pointless to 970 * blame the parents. E.g. "\t\t}\n\t}\n\n" appears everywhere in any 971 * ordinary C program, and it is not worth to say it was copied from 972 * totally unrelated file in the parent. 973 * 974 * Compute how trivial the lines in the blame_entry are. 975 */ 976unsignedblame_entry_score(struct blame_scoreboard *sb,struct blame_entry *e) 977{ 978unsigned score; 979const char*cp, *ep; 980 981if(e->score) 982return e->score; 983 984 score =1; 985 cp =blame_nth_line(sb, e->lno); 986 ep =blame_nth_line(sb, e->lno + e->num_lines); 987while(cp < ep) { 988unsigned ch = *((unsigned char*)cp); 989if(isalnum(ch)) 990 score++; 991 cp++; 992} 993 e->score = score; 994return score; 995} 996 997/* 998 * best_so_far[] and potential[] are both a split of an existing blame_entry 999 * that passes blame to the parent. Maintain best_so_far the best split so1000 * far, by comparing potential and best_so_far and copying potential into1001 * bst_so_far as needed.1002 */1003static voidcopy_split_if_better(struct blame_scoreboard *sb,1004struct blame_entry *best_so_far,1005struct blame_entry *potential)1006{1007int i;10081009if(!potential[1].suspect)1010return;1011if(best_so_far[1].suspect) {1012if(blame_entry_score(sb, &potential[1]) <1013blame_entry_score(sb, &best_so_far[1]))1014return;1015}10161017for(i =0; i <3; i++)1018blame_origin_incref(potential[i].suspect);1019decref_split(best_so_far);1020memcpy(best_so_far, potential,sizeof(struct blame_entry[3]));1021}10221023/*1024 * We are looking at a part of the final image represented by1025 * ent (tlno and same are offset by ent->s_lno).1026 * tlno is where we are looking at in the final image.1027 * up to (but not including) same match preimage.1028 * plno is where we are looking at in the preimage.1029 *1030 * <-------------- final image ---------------------->1031 * <------ent------>1032 * ^tlno ^same1033 * <---------preimage----->1034 * ^plno1035 *1036 * All line numbers are 0-based.1037 */1038static voidhandle_split(struct blame_scoreboard *sb,1039struct blame_entry *ent,1040int tlno,int plno,int same,1041struct blame_origin *parent,1042struct blame_entry *split)1043{1044if(ent->num_lines <= tlno)1045return;1046if(tlno < same) {1047struct blame_entry potential[3];1048 tlno += ent->s_lno;1049 same += ent->s_lno;1050split_overlap(potential, ent, tlno, plno, same, parent);1051copy_split_if_better(sb, split, potential);1052decref_split(potential);1053}1054}10551056struct handle_split_cb_data {1057struct blame_scoreboard *sb;1058struct blame_entry *ent;1059struct blame_origin *parent;1060struct blame_entry *split;1061long plno;1062long tlno;1063};10641065static inthandle_split_cb(long start_a,long count_a,1066long start_b,long count_b,void*data)1067{1068struct handle_split_cb_data *d = data;1069handle_split(d->sb, d->ent, d->tlno, d->plno, start_b, d->parent,1070 d->split);1071 d->plno = start_a + count_a;1072 d->tlno = start_b + count_b;1073return0;1074}10751076/*1077 * Find the lines from parent that are the same as ent so that1078 * we can pass blames to it. file_p has the blob contents for1079 * the parent.1080 */1081static voidfind_copy_in_blob(struct blame_scoreboard *sb,1082struct blame_entry *ent,1083struct blame_origin *parent,1084struct blame_entry *split,1085 mmfile_t *file_p)1086{1087const char*cp;1088 mmfile_t file_o;1089struct handle_split_cb_data d;10901091memset(&d,0,sizeof(d));1092 d.sb = sb; d.ent = ent; d.parent = parent; d.split = split;1093/*1094 * Prepare mmfile that contains only the lines in ent.1095 */1096 cp =blame_nth_line(sb, ent->lno);1097 file_o.ptr = (char*) cp;1098 file_o.size =blame_nth_line(sb, ent->lno + ent->num_lines) - cp;10991100/*1101 * file_o is a part of final image we are annotating.1102 * file_p partially may match that image.1103 */1104memset(split,0,sizeof(struct blame_entry [3]));1105if(diff_hunks(file_p, &file_o, handle_split_cb, &d, sb->xdl_opts))1106die("unable to generate diff (%s)",1107oid_to_hex(&parent->commit->object.oid));1108/* remainder, if any, all match the preimage */1109handle_split(sb, ent, d.tlno, d.plno, ent->num_lines, parent, split);1110}11111112/* Move all blame entries from list *source that have a score smaller1113 * than score_min to the front of list *small.1114 * Returns a pointer to the link pointing to the old head of the small list.1115 */11161117static struct blame_entry **filter_small(struct blame_scoreboard *sb,1118struct blame_entry **small,1119struct blame_entry **source,1120unsigned score_min)1121{1122struct blame_entry *p = *source;1123struct blame_entry *oldsmall = *small;1124while(p) {1125if(blame_entry_score(sb, p) <= score_min) {1126*small = p;1127 small = &p->next;1128 p = *small;1129}else{1130*source = p;1131 source = &p->next;1132 p = *source;1133}1134}1135*small = oldsmall;1136*source = NULL;1137return small;1138}11391140/*1141 * See if lines currently target is suspected for can be attributed to1142 * parent.1143 */1144static voidfind_move_in_parent(struct blame_scoreboard *sb,1145struct blame_entry ***blamed,1146struct blame_entry **toosmall,1147struct blame_origin *target,1148struct blame_origin *parent)1149{1150struct blame_entry *e, split[3];1151struct blame_entry *unblamed = target->suspects;1152struct blame_entry *leftover = NULL;1153 mmfile_t file_p;11541155if(!unblamed)1156return;/* nothing remains for this target */11571158fill_origin_blob(&sb->revs->diffopt, parent, &file_p, &sb->num_read_blob);1159if(!file_p.ptr)1160return;11611162/* At each iteration, unblamed has a NULL-terminated list of1163 * entries that have not yet been tested for blame. leftover1164 * contains the reversed list of entries that have been tested1165 * without being assignable to the parent.1166 */1167do{1168struct blame_entry **unblamedtail = &unblamed;1169struct blame_entry *next;1170for(e = unblamed; e; e = next) {1171 next = e->next;1172find_copy_in_blob(sb, e, parent, split, &file_p);1173if(split[1].suspect &&1174 sb->move_score <blame_entry_score(sb, &split[1])) {1175split_blame(blamed, &unblamedtail, split, e);1176}else{1177 e->next = leftover;1178 leftover = e;1179}1180decref_split(split);1181}1182*unblamedtail = NULL;1183 toosmall =filter_small(sb, toosmall, &unblamed, sb->move_score);1184}while(unblamed);1185 target->suspects =reverse_blame(leftover, NULL);1186}11871188struct blame_list {1189struct blame_entry *ent;1190struct blame_entry split[3];1191};11921193/*1194 * Count the number of entries the target is suspected for,1195 * and prepare a list of entry and the best split.1196 */1197static struct blame_list *setup_blame_list(struct blame_entry *unblamed,1198int*num_ents_p)1199{1200struct blame_entry *e;1201int num_ents, i;1202struct blame_list *blame_list = NULL;12031204for(e = unblamed, num_ents =0; e; e = e->next)1205 num_ents++;1206if(num_ents) {1207 blame_list =xcalloc(num_ents,sizeof(struct blame_list));1208for(e = unblamed, i =0; e; e = e->next)1209 blame_list[i++].ent = e;1210}1211*num_ents_p = num_ents;1212return blame_list;1213}12141215/*1216 * For lines target is suspected for, see if we can find code movement1217 * across file boundary from the parent commit. porigin is the path1218 * in the parent we already tried.1219 */1220static voidfind_copy_in_parent(struct blame_scoreboard *sb,1221struct blame_entry ***blamed,1222struct blame_entry **toosmall,1223struct blame_origin *target,1224struct commit *parent,1225struct blame_origin *porigin,1226int opt)1227{1228struct diff_options diff_opts;1229int i, j;1230struct blame_list *blame_list;1231int num_ents;1232struct blame_entry *unblamed = target->suspects;1233struct blame_entry *leftover = NULL;12341235if(!unblamed)1236return;/* nothing remains for this target */12371238diff_setup(&diff_opts);1239 diff_opts.flags.recursive =1;1240 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;12411242diff_setup_done(&diff_opts);12431244/* Try "find copies harder" on new path if requested;1245 * we do not want to use diffcore_rename() actually to1246 * match things up; find_copies_harder is set only to1247 * force diff_tree_oid() to feed all filepairs to diff_queue,1248 * and this code needs to be after diff_setup_done(), which1249 * usually makes find-copies-harder imply copy detection.1250 */1251if((opt & PICKAXE_BLAME_COPY_HARDEST)1252|| ((opt & PICKAXE_BLAME_COPY_HARDER)1253&& (!porigin ||strcmp(target->path, porigin->path))))1254 diff_opts.flags.find_copies_harder =1;12551256if(is_null_oid(&target->commit->object.oid))1257do_diff_cache(get_commit_tree_oid(parent), &diff_opts);1258else1259diff_tree_oid(get_commit_tree_oid(parent),1260get_commit_tree_oid(target->commit),1261"", &diff_opts);12621263if(!diff_opts.flags.find_copies_harder)1264diffcore_std(&diff_opts);12651266do{1267struct blame_entry **unblamedtail = &unblamed;1268 blame_list =setup_blame_list(unblamed, &num_ents);12691270for(i =0; i < diff_queued_diff.nr; i++) {1271struct diff_filepair *p = diff_queued_diff.queue[i];1272struct blame_origin *norigin;1273 mmfile_t file_p;1274struct blame_entry potential[3];12751276if(!DIFF_FILE_VALID(p->one))1277continue;/* does not exist in parent */1278if(S_ISGITLINK(p->one->mode))1279continue;/* ignore git links */1280if(porigin && !strcmp(p->one->path, porigin->path))1281/* find_move already dealt with this path */1282continue;12831284 norigin =get_origin(parent, p->one->path);1285oidcpy(&norigin->blob_oid, &p->one->oid);1286 norigin->mode = p->one->mode;1287fill_origin_blob(&sb->revs->diffopt, norigin, &file_p, &sb->num_read_blob);1288if(!file_p.ptr)1289continue;12901291for(j =0; j < num_ents; j++) {1292find_copy_in_blob(sb, blame_list[j].ent,1293 norigin, potential, &file_p);1294copy_split_if_better(sb, blame_list[j].split,1295 potential);1296decref_split(potential);1297}1298blame_origin_decref(norigin);1299}13001301for(j =0; j < num_ents; j++) {1302struct blame_entry *split = blame_list[j].split;1303if(split[1].suspect &&1304 sb->copy_score <blame_entry_score(sb, &split[1])) {1305split_blame(blamed, &unblamedtail, split,1306 blame_list[j].ent);1307}else{1308 blame_list[j].ent->next = leftover;1309 leftover = blame_list[j].ent;1310}1311decref_split(split);1312}1313free(blame_list);1314*unblamedtail = NULL;1315 toosmall =filter_small(sb, toosmall, &unblamed, sb->copy_score);1316}while(unblamed);1317 target->suspects =reverse_blame(leftover, NULL);1318diff_flush(&diff_opts);1319clear_pathspec(&diff_opts.pathspec);1320}13211322/*1323 * The blobs of origin and porigin exactly match, so everything1324 * origin is suspected for can be blamed on the parent.1325 */1326static voidpass_whole_blame(struct blame_scoreboard *sb,1327struct blame_origin *origin,struct blame_origin *porigin)1328{1329struct blame_entry *e, *suspects;13301331if(!porigin->file.ptr && origin->file.ptr) {1332/* Steal its file */1333 porigin->file = origin->file;1334 origin->file.ptr = NULL;1335}1336 suspects = origin->suspects;1337 origin->suspects = NULL;1338for(e = suspects; e; e = e->next) {1339blame_origin_incref(porigin);1340blame_origin_decref(e->suspect);1341 e->suspect = porigin;1342}1343queue_blames(sb, porigin, suspects);1344}13451346/*1347 * We pass blame from the current commit to its parents. We keep saying1348 * "parent" (and "porigin"), but what we mean is to find scapegoat to1349 * exonerate ourselves.1350 */1351static struct commit_list *first_scapegoat(struct rev_info *revs,struct commit *commit,1352int reverse)1353{1354if(!reverse) {1355if(revs->first_parent_only &&1356 commit->parents &&1357 commit->parents->next) {1358free_commit_list(commit->parents->next);1359 commit->parents->next = NULL;1360}1361return commit->parents;1362}1363returnlookup_decoration(&revs->children, &commit->object);1364}13651366static intnum_scapegoats(struct rev_info *revs,struct commit *commit,int reverse)1367{1368struct commit_list *l =first_scapegoat(revs, commit, reverse);1369returncommit_list_count(l);1370}13711372/* Distribute collected unsorted blames to the respected sorted lists1373 * in the various origins.1374 */1375static voiddistribute_blame(struct blame_scoreboard *sb,struct blame_entry *blamed)1376{1377 blamed =llist_mergesort(blamed, get_next_blame, set_next_blame,1378 compare_blame_suspect);1379while(blamed)1380{1381struct blame_origin *porigin = blamed->suspect;1382struct blame_entry *suspects = NULL;1383do{1384struct blame_entry *next = blamed->next;1385 blamed->next = suspects;1386 suspects = blamed;1387 blamed = next;1388}while(blamed && blamed->suspect == porigin);1389 suspects =reverse_blame(suspects, NULL);1390queue_blames(sb, porigin, suspects);1391}1392}13931394#define MAXSG 1613951396static voidpass_blame(struct blame_scoreboard *sb,struct blame_origin *origin,int opt)1397{1398struct rev_info *revs = sb->revs;1399int i, pass, num_sg;1400struct commit *commit = origin->commit;1401struct commit_list *sg;1402struct blame_origin *sg_buf[MAXSG];1403struct blame_origin *porigin, **sg_origin = sg_buf;1404struct blame_entry *toosmall = NULL;1405struct blame_entry *blames, **blametail = &blames;14061407 num_sg =num_scapegoats(revs, commit, sb->reverse);1408if(!num_sg)1409goto finish;1410else if(num_sg <ARRAY_SIZE(sg_buf))1411memset(sg_buf,0,sizeof(sg_buf));1412else1413 sg_origin =xcalloc(num_sg,sizeof(*sg_origin));14141415/*1416 * The first pass looks for unrenamed path to optimize for1417 * common cases, then we look for renames in the second pass.1418 */1419for(pass =0; pass <2- sb->no_whole_file_rename; pass++) {1420struct blame_origin *(*find)(struct commit *,struct blame_origin *);1421 find = pass ? find_rename : find_origin;14221423for(i =0, sg =first_scapegoat(revs, commit, sb->reverse);1424 i < num_sg && sg;1425 sg = sg->next, i++) {1426struct commit *p = sg->item;1427int j, same;14281429if(sg_origin[i])1430continue;1431if(parse_commit(p))1432continue;1433 porigin =find(p, origin);1434if(!porigin)1435continue;1436if(!oidcmp(&porigin->blob_oid, &origin->blob_oid)) {1437pass_whole_blame(sb, origin, porigin);1438blame_origin_decref(porigin);1439goto finish;1440}1441for(j = same =0; j < i; j++)1442if(sg_origin[j] &&1443!oidcmp(&sg_origin[j]->blob_oid, &porigin->blob_oid)) {1444 same =1;1445break;1446}1447if(!same)1448 sg_origin[i] = porigin;1449else1450blame_origin_decref(porigin);1451}1452}14531454 sb->num_commits++;1455for(i =0, sg =first_scapegoat(revs, commit, sb->reverse);1456 i < num_sg && sg;1457 sg = sg->next, i++) {1458struct blame_origin *porigin = sg_origin[i];1459if(!porigin)1460continue;1461if(!origin->previous) {1462blame_origin_incref(porigin);1463 origin->previous = porigin;1464}1465pass_blame_to_parent(sb, origin, porigin);1466if(!origin->suspects)1467goto finish;1468}14691470/*1471 * Optionally find moves in parents' files.1472 */1473if(opt & PICKAXE_BLAME_MOVE) {1474filter_small(sb, &toosmall, &origin->suspects, sb->move_score);1475if(origin->suspects) {1476for(i =0, sg =first_scapegoat(revs, commit, sb->reverse);1477 i < num_sg && sg;1478 sg = sg->next, i++) {1479struct blame_origin *porigin = sg_origin[i];1480if(!porigin)1481continue;1482find_move_in_parent(sb, &blametail, &toosmall, origin, porigin);1483if(!origin->suspects)1484break;1485}1486}1487}14881489/*1490 * Optionally find copies from parents' files.1491 */1492if(opt & PICKAXE_BLAME_COPY) {1493if(sb->copy_score > sb->move_score)1494filter_small(sb, &toosmall, &origin->suspects, sb->copy_score);1495else if(sb->copy_score < sb->move_score) {1496 origin->suspects =blame_merge(origin->suspects, toosmall);1497 toosmall = NULL;1498filter_small(sb, &toosmall, &origin->suspects, sb->copy_score);1499}1500if(!origin->suspects)1501goto finish;15021503for(i =0, sg =first_scapegoat(revs, commit, sb->reverse);1504 i < num_sg && sg;1505 sg = sg->next, i++) {1506struct blame_origin *porigin = sg_origin[i];1507find_copy_in_parent(sb, &blametail, &toosmall,1508 origin, sg->item, porigin, opt);1509if(!origin->suspects)1510goto finish;1511}1512}15131514finish:1515*blametail = NULL;1516distribute_blame(sb, blames);1517/*1518 * prepend toosmall to origin->suspects1519 *1520 * There is no point in sorting: this ends up on a big1521 * unsorted list in the caller anyway.1522 */1523if(toosmall) {1524struct blame_entry **tail = &toosmall;1525while(*tail)1526 tail = &(*tail)->next;1527*tail = origin->suspects;1528 origin->suspects = toosmall;1529}1530for(i =0; i < num_sg; i++) {1531if(sg_origin[i]) {1532drop_origin_blob(sg_origin[i]);1533blame_origin_decref(sg_origin[i]);1534}1535}1536drop_origin_blob(origin);1537if(sg_buf != sg_origin)1538free(sg_origin);1539}15401541/*1542 * The main loop -- while we have blobs with lines whose true origin1543 * is still unknown, pick one blob, and allow its lines to pass blames1544 * to its parents. */1545voidassign_blame(struct blame_scoreboard *sb,int opt)1546{1547struct rev_info *revs = sb->revs;1548struct commit *commit =prio_queue_get(&sb->commits);15491550while(commit) {1551struct blame_entry *ent;1552struct blame_origin *suspect = commit->util;15531554/* find one suspect to break down */1555while(suspect && !suspect->suspects)1556 suspect = suspect->next;15571558if(!suspect) {1559 commit =prio_queue_get(&sb->commits);1560continue;1561}15621563assert(commit == suspect->commit);15641565/*1566 * We will use this suspect later in the loop,1567 * so hold onto it in the meantime.1568 */1569blame_origin_incref(suspect);1570parse_commit(commit);1571if(sb->reverse ||1572(!(commit->object.flags & UNINTERESTING) &&1573!(revs->max_age != -1&& commit->date < revs->max_age)))1574pass_blame(sb, suspect, opt);1575else{1576 commit->object.flags |= UNINTERESTING;1577if(commit->object.parsed)1578mark_parents_uninteresting(commit);1579}1580/* treat root commit as boundary */1581if(!commit->parents && !sb->show_root)1582 commit->object.flags |= UNINTERESTING;15831584/* Take responsibility for the remaining entries */1585 ent = suspect->suspects;1586if(ent) {1587 suspect->guilty =1;1588for(;;) {1589struct blame_entry *next = ent->next;1590if(sb->found_guilty_entry)1591 sb->found_guilty_entry(ent, sb->found_guilty_entry_data);1592if(next) {1593 ent = next;1594continue;1595}1596 ent->next = sb->ent;1597 sb->ent = suspect->suspects;1598 suspect->suspects = NULL;1599break;1600}1601}1602blame_origin_decref(suspect);16031604if(sb->debug)/* sanity */1605sanity_check_refcnt(sb);1606}1607}16081609static const char*get_next_line(const char*start,const char*end)1610{1611const char*nl =memchr(start,'\n', end - start);1612return nl ? nl +1: end;1613}16141615/*1616 * To allow quick access to the contents of nth line in the1617 * final image, prepare an index in the scoreboard.1618 */1619static intprepare_lines(struct blame_scoreboard *sb)1620{1621const char*buf = sb->final_buf;1622unsigned long len = sb->final_buf_size;1623const char*end = buf + len;1624const char*p;1625int*lineno;1626int num =0;16271628for(p = buf; p < end; p =get_next_line(p, end))1629 num++;16301631ALLOC_ARRAY(sb->lineno, num +1);1632 lineno = sb->lineno;16331634for(p = buf; p < end; p =get_next_line(p, end))1635*lineno++ = p - buf;16361637*lineno = len;16381639 sb->num_lines = num;1640return sb->num_lines;1641}16421643static struct commit *find_single_final(struct rev_info *revs,1644const char**name_p)1645{1646int i;1647struct commit *found = NULL;1648const char*name = NULL;16491650for(i =0; i < revs->pending.nr; i++) {1651struct object *obj = revs->pending.objects[i].item;1652if(obj->flags & UNINTERESTING)1653continue;1654 obj =deref_tag(obj, NULL,0);1655if(obj->type != OBJ_COMMIT)1656die("Non commit%s?", revs->pending.objects[i].name);1657if(found)1658die("More than one commit to dig from%sand%s?",1659 revs->pending.objects[i].name, name);1660 found = (struct commit *)obj;1661 name = revs->pending.objects[i].name;1662}1663if(name_p)1664*name_p =xstrdup_or_null(name);1665return found;1666}16671668static struct commit *dwim_reverse_initial(struct rev_info *revs,1669const char**name_p)1670{1671/*1672 * DWIM "git blame --reverse ONE -- PATH" as1673 * "git blame --reverse ONE..HEAD -- PATH" but only do so1674 * when it makes sense.1675 */1676struct object *obj;1677struct commit *head_commit;1678struct object_id head_oid;16791680if(revs->pending.nr !=1)1681return NULL;16821683/* Is that sole rev a committish? */1684 obj = revs->pending.objects[0].item;1685 obj =deref_tag(obj, NULL,0);1686if(obj->type != OBJ_COMMIT)1687return NULL;16881689/* Do we have HEAD? */1690if(!resolve_ref_unsafe("HEAD", RESOLVE_REF_READING, &head_oid, NULL))1691return NULL;1692 head_commit =lookup_commit_reference_gently(&head_oid,1);1693if(!head_commit)1694return NULL;16951696/* Turn "ONE" into "ONE..HEAD" then */1697 obj->flags |= UNINTERESTING;1698add_pending_object(revs, &head_commit->object,"HEAD");16991700if(name_p)1701*name_p = revs->pending.objects[0].name;1702return(struct commit *)obj;1703}17041705static struct commit *find_single_initial(struct rev_info *revs,1706const char**name_p)1707{1708int i;1709struct commit *found = NULL;1710const char*name = NULL;17111712/*1713 * There must be one and only one negative commit, and it must be1714 * the boundary.1715 */1716for(i =0; i < revs->pending.nr; i++) {1717struct object *obj = revs->pending.objects[i].item;1718if(!(obj->flags & UNINTERESTING))1719continue;1720 obj =deref_tag(obj, NULL,0);1721if(obj->type != OBJ_COMMIT)1722die("Non commit%s?", revs->pending.objects[i].name);1723if(found)1724die("More than one commit to dig up from,%sand%s?",1725 revs->pending.objects[i].name, name);1726 found = (struct commit *) obj;1727 name = revs->pending.objects[i].name;1728}17291730if(!name)1731 found =dwim_reverse_initial(revs, &name);1732if(!name)1733die("No commit to dig up from?");17341735if(name_p)1736*name_p =xstrdup(name);1737return found;1738}17391740voidinit_scoreboard(struct blame_scoreboard *sb)1741{1742memset(sb,0,sizeof(struct blame_scoreboard));1743 sb->move_score = BLAME_DEFAULT_MOVE_SCORE;1744 sb->copy_score = BLAME_DEFAULT_COPY_SCORE;1745}17461747voidsetup_scoreboard(struct blame_scoreboard *sb,const char*path,struct blame_origin **orig)1748{1749const char*final_commit_name = NULL;1750struct blame_origin *o;1751struct commit *final_commit = NULL;1752enum object_type type;17531754if(sb->reverse && sb->contents_from)1755die(_("--contents and --reverse do not blend well."));17561757if(!sb->reverse) {1758 sb->final =find_single_final(sb->revs, &final_commit_name);1759 sb->commits.compare = compare_commits_by_commit_date;1760}else{1761 sb->final =find_single_initial(sb->revs, &final_commit_name);1762 sb->commits.compare = compare_commits_by_reverse_commit_date;1763}17641765if(sb->final && sb->contents_from)1766die(_("cannot use --contents with final commit object name"));17671768if(sb->reverse && sb->revs->first_parent_only)1769 sb->revs->children.name = NULL;17701771if(!sb->final) {1772/*1773 * "--not A B -- path" without anything positive;1774 * do not default to HEAD, but use the working tree1775 * or "--contents".1776 */1777setup_work_tree();1778 sb->final =fake_working_tree_commit(&sb->revs->diffopt,1779 path, sb->contents_from);1780add_pending_object(sb->revs, &(sb->final->object),":");1781}17821783if(sb->reverse && sb->revs->first_parent_only) {1784 final_commit =find_single_final(sb->revs, NULL);1785if(!final_commit)1786die(_("--reverse and --first-parent together require specified latest commit"));1787}17881789/*1790 * If we have bottom, this will mark the ancestors of the1791 * bottom commits we would reach while traversing as1792 * uninteresting.1793 */1794if(prepare_revision_walk(sb->revs))1795die(_("revision walk setup failed"));17961797if(sb->reverse && sb->revs->first_parent_only) {1798struct commit *c = final_commit;17991800 sb->revs->children.name ="children";1801while(c->parents &&1802oidcmp(&c->object.oid, &sb->final->object.oid)) {1803struct commit_list *l =xcalloc(1,sizeof(*l));18041805 l->item = c;1806if(add_decoration(&sb->revs->children,1807&c->parents->item->object, l))1808BUG("not unique item in first-parent chain");1809 c = c->parents->item;1810}18111812if(oidcmp(&c->object.oid, &sb->final->object.oid))1813die(_("--reverse --first-parent together require range along first-parent chain"));1814}18151816if(is_null_oid(&sb->final->object.oid)) {1817 o = sb->final->util;1818 sb->final_buf =xmemdupz(o->file.ptr, o->file.size);1819 sb->final_buf_size = o->file.size;1820}1821else{1822 o =get_origin(sb->final, path);1823if(fill_blob_sha1_and_mode(o))1824die(_("no such path%sin%s"), path, final_commit_name);18251826if(sb->revs->diffopt.flags.allow_textconv &&1827textconv_object(path, o->mode, &o->blob_oid,1, (char**) &sb->final_buf,1828&sb->final_buf_size))1829;1830else1831 sb->final_buf =read_object_file(&o->blob_oid, &type,1832&sb->final_buf_size);18331834if(!sb->final_buf)1835die(_("cannot read blob%sfor path%s"),1836oid_to_hex(&o->blob_oid),1837 path);1838}1839 sb->num_read_blob++;1840prepare_lines(sb);18411842if(orig)1843*orig = o;18441845free((char*)final_commit_name);1846}1847184818491850struct blame_entry *blame_entry_prepend(struct blame_entry *head,1851long start,long end,1852struct blame_origin *o)1853{1854struct blame_entry *new_head =xcalloc(1,sizeof(struct blame_entry));1855 new_head->lno = start;1856 new_head->num_lines = end - start;1857 new_head->suspect = o;1858 new_head->s_lno = start;1859 new_head->next = head;1860blame_origin_incref(o);1861return new_head;1862}