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#include"alloc.h" 10 11voidblame_origin_decref(struct blame_origin *o) 12{ 13if(o && --o->refcnt <=0) { 14struct blame_origin *p, *l = NULL; 15if(o->previous) 16blame_origin_decref(o->previous); 17free(o->file.ptr); 18/* Should be present exactly once in commit chain */ 19for(p = o->commit->util; p; l = p, p = p->next) { 20if(p == o) { 21if(l) 22 l->next = p->next; 23else 24 o->commit->util = p->next; 25free(o); 26return; 27} 28} 29die("internal error in blame_origin_decref"); 30} 31} 32 33/* 34 * Given a commit and a path in it, create a new origin structure. 35 * The callers that add blame to the scoreboard should use 36 * get_origin() to obtain shared, refcounted copy instead of calling 37 * this function directly. 38 */ 39static struct blame_origin *make_origin(struct commit *commit,const char*path) 40{ 41struct blame_origin *o; 42FLEX_ALLOC_STR(o, path, path); 43 o->commit = commit; 44 o->refcnt =1; 45 o->next = commit->util; 46 commit->util = o; 47return o; 48} 49 50/* 51 * Locate an existing origin or create a new one. 52 * This moves the origin to front position in the commit util list. 53 */ 54static struct blame_origin *get_origin(struct commit *commit,const char*path) 55{ 56struct blame_origin *o, *l; 57 58for(o = commit->util, l = NULL; o; l = o, o = o->next) { 59if(!strcmp(o->path, path)) { 60/* bump to front */ 61if(l) { 62 l->next = o->next; 63 o->next = commit->util; 64 commit->util = o; 65} 66returnblame_origin_incref(o); 67} 68} 69returnmake_origin(commit, path); 70} 71 72 73 74static voidverify_working_tree_path(struct commit *work_tree,const char*path) 75{ 76struct commit_list *parents; 77int pos; 78 79for(parents = work_tree->parents; parents; parents = parents->next) { 80const struct object_id *commit_oid = &parents->item->object.oid; 81struct object_id blob_oid; 82unsigned mode; 83 84if(!get_tree_entry(commit_oid, path, &blob_oid, &mode) && 85oid_object_info(the_repository, &blob_oid, NULL) == OBJ_BLOB) 86return; 87} 88 89 pos =cache_name_pos(path,strlen(path)); 90if(pos >=0) 91;/* path is in the index */ 92else if(-1- pos < active_nr && 93!strcmp(active_cache[-1- pos]->name, path)) 94;/* path is in the index, unmerged */ 95else 96die("no such path '%s' in HEAD", path); 97} 98 99static struct commit_list **append_parent(struct commit_list **tail,const struct object_id *oid) 100{ 101struct commit *parent; 102 103 parent =lookup_commit_reference(oid); 104if(!parent) 105die("no such commit%s",oid_to_hex(oid)); 106return&commit_list_insert(parent, tail)->next; 107} 108 109static voidappend_merge_parents(struct commit_list **tail) 110{ 111int merge_head; 112struct strbuf line = STRBUF_INIT; 113 114 merge_head =open(git_path_merge_head(), O_RDONLY); 115if(merge_head <0) { 116if(errno == ENOENT) 117return; 118die("cannot open '%s' for reading",git_path_merge_head()); 119} 120 121while(!strbuf_getwholeline_fd(&line, merge_head,'\n')) { 122struct object_id oid; 123if(line.len < GIT_SHA1_HEXSZ ||get_oid_hex(line.buf, &oid)) 124die("unknown line in '%s':%s",git_path_merge_head(), line.buf); 125 tail =append_parent(tail, &oid); 126} 127close(merge_head); 128strbuf_release(&line); 129} 130 131/* 132 * This isn't as simple as passing sb->buf and sb->len, because we 133 * want to transfer ownership of the buffer to the commit (so we 134 * must use detach). 135 */ 136static voidset_commit_buffer_from_strbuf(struct commit *c,struct strbuf *sb) 137{ 138size_t len; 139void*buf =strbuf_detach(sb, &len); 140set_commit_buffer(c, buf, len); 141} 142 143/* 144 * Prepare a dummy commit that represents the work tree (or staged) item. 145 * Note that annotating work tree item never works in the reverse. 146 */ 147static struct commit *fake_working_tree_commit(struct diff_options *opt, 148const char*path, 149const char*contents_from) 150{ 151struct commit *commit; 152struct blame_origin *origin; 153struct commit_list **parent_tail, *parent; 154struct object_id head_oid; 155struct strbuf buf = STRBUF_INIT; 156const char*ident; 157time_t now; 158int size, len; 159struct cache_entry *ce; 160unsigned mode; 161struct strbuf msg = STRBUF_INIT; 162 163read_cache(); 164time(&now); 165 commit =alloc_commit_node(the_repository); 166 commit->object.parsed =1; 167 commit->date = now; 168 parent_tail = &commit->parents; 169 170if(!resolve_ref_unsafe("HEAD", RESOLVE_REF_READING, &head_oid, NULL)) 171die("no such ref: HEAD"); 172 173 parent_tail =append_parent(parent_tail, &head_oid); 174append_merge_parents(parent_tail); 175verify_working_tree_path(commit, path); 176 177 origin =make_origin(commit, path); 178 179 ident =fmt_ident("Not Committed Yet","not.committed.yet", NULL,0); 180strbuf_addstr(&msg,"tree 0000000000000000000000000000000000000000\n"); 181for(parent = commit->parents; parent; parent = parent->next) 182strbuf_addf(&msg,"parent%s\n", 183oid_to_hex(&parent->item->object.oid)); 184strbuf_addf(&msg, 185"author%s\n" 186"committer%s\n\n" 187"Version of%sfrom%s\n", 188 ident, ident, path, 189(!contents_from ? path : 190(!strcmp(contents_from,"-") ?"standard input": contents_from))); 191set_commit_buffer_from_strbuf(commit, &msg); 192 193if(!contents_from ||strcmp("-", contents_from)) { 194struct stat st; 195const char*read_from; 196char*buf_ptr; 197unsigned long buf_len; 198 199if(contents_from) { 200if(stat(contents_from, &st) <0) 201die_errno("Cannot stat '%s'", contents_from); 202 read_from = contents_from; 203} 204else{ 205if(lstat(path, &st) <0) 206die_errno("Cannot lstat '%s'", path); 207 read_from = path; 208} 209 mode =canon_mode(st.st_mode); 210 211switch(st.st_mode & S_IFMT) { 212case S_IFREG: 213if(opt->flags.allow_textconv && 214textconv_object(read_from, mode, &null_oid,0, &buf_ptr, &buf_len)) 215strbuf_attach(&buf, buf_ptr, buf_len, buf_len +1); 216else if(strbuf_read_file(&buf, read_from, st.st_size) != st.st_size) 217die_errno("cannot open or read '%s'", read_from); 218break; 219case S_IFLNK: 220if(strbuf_readlink(&buf, read_from, st.st_size) <0) 221die_errno("cannot readlink '%s'", read_from); 222break; 223default: 224die("unsupported file type%s", read_from); 225} 226} 227else{ 228/* Reading from stdin */ 229 mode =0; 230if(strbuf_read(&buf,0,0) <0) 231die_errno("failed to read from stdin"); 232} 233convert_to_git(&the_index, path, buf.buf, buf.len, &buf,0); 234 origin->file.ptr = buf.buf; 235 origin->file.size = buf.len; 236pretend_object_file(buf.buf, buf.len, OBJ_BLOB, &origin->blob_oid); 237 238/* 239 * Read the current index, replace the path entry with 240 * origin->blob_sha1 without mucking with its mode or type 241 * bits; we are not going to write this index out -- we just 242 * want to run "diff-index --cached". 243 */ 244discard_cache(); 245read_cache(); 246 247 len =strlen(path); 248if(!mode) { 249int pos =cache_name_pos(path, len); 250if(0<= pos) 251 mode = active_cache[pos]->ce_mode; 252else 253/* Let's not bother reading from HEAD tree */ 254 mode = S_IFREG |0644; 255} 256 size =cache_entry_size(len); 257 ce =xcalloc(1, size); 258oidcpy(&ce->oid, &origin->blob_oid); 259memcpy(ce->name, path, len); 260 ce->ce_flags =create_ce_flags(0); 261 ce->ce_namelen = len; 262 ce->ce_mode =create_ce_mode(mode); 263add_cache_entry(ce, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE); 264 265cache_tree_invalidate_path(&the_index, path); 266 267return commit; 268} 269 270 271 272static intdiff_hunks(mmfile_t *file_a, mmfile_t *file_b, 273 xdl_emit_hunk_consume_func_t hunk_func,void*cb_data,int xdl_opts) 274{ 275 xpparam_t xpp = {0}; 276 xdemitconf_t xecfg = {0}; 277 xdemitcb_t ecb = {NULL}; 278 279 xpp.flags = xdl_opts; 280 xecfg.hunk_func = hunk_func; 281 ecb.priv = cb_data; 282returnxdi_diff(file_a, file_b, &xpp, &xecfg, &ecb); 283} 284 285/* 286 * Given an origin, prepare mmfile_t structure to be used by the 287 * diff machinery 288 */ 289static voidfill_origin_blob(struct diff_options *opt, 290struct blame_origin *o, mmfile_t *file,int*num_read_blob) 291{ 292if(!o->file.ptr) { 293enum object_type type; 294unsigned long file_size; 295 296(*num_read_blob)++; 297if(opt->flags.allow_textconv && 298textconv_object(o->path, o->mode, &o->blob_oid,1, &file->ptr, &file_size)) 299; 300else 301 file->ptr =read_object_file(&o->blob_oid, &type, 302&file_size); 303 file->size = file_size; 304 305if(!file->ptr) 306die("Cannot read blob%sfor path%s", 307oid_to_hex(&o->blob_oid), 308 o->path); 309 o->file = *file; 310} 311else 312*file = o->file; 313} 314 315static voiddrop_origin_blob(struct blame_origin *o) 316{ 317if(o->file.ptr) { 318FREE_AND_NULL(o->file.ptr); 319} 320} 321 322/* 323 * Any merge of blames happens on lists of blames that arrived via 324 * different parents in a single suspect. In this case, we want to 325 * sort according to the suspect line numbers as opposed to the final 326 * image line numbers. The function body is somewhat longish because 327 * it avoids unnecessary writes. 328 */ 329 330static struct blame_entry *blame_merge(struct blame_entry *list1, 331struct blame_entry *list2) 332{ 333struct blame_entry *p1 = list1, *p2 = list2, 334**tail = &list1; 335 336if(!p1) 337return p2; 338if(!p2) 339return p1; 340 341if(p1->s_lno <= p2->s_lno) { 342do{ 343 tail = &p1->next; 344if((p1 = *tail) == NULL) { 345*tail = p2; 346return list1; 347} 348}while(p1->s_lno <= p2->s_lno); 349} 350for(;;) { 351*tail = p2; 352do{ 353 tail = &p2->next; 354if((p2 = *tail) == NULL) { 355*tail = p1; 356return list1; 357} 358}while(p1->s_lno > p2->s_lno); 359*tail = p1; 360do{ 361 tail = &p1->next; 362if((p1 = *tail) == NULL) { 363*tail = p2; 364return list1; 365} 366}while(p1->s_lno <= p2->s_lno); 367} 368} 369 370static void*get_next_blame(const void*p) 371{ 372return((struct blame_entry *)p)->next; 373} 374 375static voidset_next_blame(void*p1,void*p2) 376{ 377((struct blame_entry *)p1)->next = p2; 378} 379 380/* 381 * Final image line numbers are all different, so we don't need a 382 * three-way comparison here. 383 */ 384 385static intcompare_blame_final(const void*p1,const void*p2) 386{ 387return((struct blame_entry *)p1)->lno > ((struct blame_entry *)p2)->lno 388?1: -1; 389} 390 391static intcompare_blame_suspect(const void*p1,const void*p2) 392{ 393const struct blame_entry *s1 = p1, *s2 = p2; 394/* 395 * to allow for collating suspects, we sort according to the 396 * respective pointer value as the primary sorting criterion. 397 * The actual relation is pretty unimportant as long as it 398 * establishes a total order. Comparing as integers gives us 399 * that. 400 */ 401if(s1->suspect != s2->suspect) 402return(intptr_t)s1->suspect > (intptr_t)s2->suspect ?1: -1; 403if(s1->s_lno == s2->s_lno) 404return0; 405return s1->s_lno > s2->s_lno ?1: -1; 406} 407 408voidblame_sort_final(struct blame_scoreboard *sb) 409{ 410 sb->ent =llist_mergesort(sb->ent, get_next_blame, set_next_blame, 411 compare_blame_final); 412} 413 414static intcompare_commits_by_reverse_commit_date(const void*a, 415const void*b, 416void*c) 417{ 418return-compare_commits_by_commit_date(a, b, c); 419} 420 421/* 422 * For debugging -- origin is refcounted, and this asserts that 423 * we do not underflow. 424 */ 425static voidsanity_check_refcnt(struct blame_scoreboard *sb) 426{ 427int baa =0; 428struct blame_entry *ent; 429 430for(ent = sb->ent; ent; ent = ent->next) { 431/* Nobody should have zero or negative refcnt */ 432if(ent->suspect->refcnt <=0) { 433fprintf(stderr,"%sin%shas negative refcnt%d\n", 434 ent->suspect->path, 435oid_to_hex(&ent->suspect->commit->object.oid), 436 ent->suspect->refcnt); 437 baa =1; 438} 439} 440if(baa) 441 sb->on_sanity_fail(sb, baa); 442} 443 444/* 445 * If two blame entries that are next to each other came from 446 * contiguous lines in the same origin (i.e. <commit, path> pair), 447 * merge them together. 448 */ 449voidblame_coalesce(struct blame_scoreboard *sb) 450{ 451struct blame_entry *ent, *next; 452 453for(ent = sb->ent; ent && (next = ent->next); ent = next) { 454if(ent->suspect == next->suspect && 455 ent->s_lno + ent->num_lines == next->s_lno) { 456 ent->num_lines += next->num_lines; 457 ent->next = next->next; 458blame_origin_decref(next->suspect); 459free(next); 460 ent->score =0; 461 next = ent;/* again */ 462} 463} 464 465if(sb->debug)/* sanity */ 466sanity_check_refcnt(sb); 467} 468 469/* 470 * Merge the given sorted list of blames into a preexisting origin. 471 * If there were no previous blames to that commit, it is entered into 472 * the commit priority queue of the score board. 473 */ 474 475static voidqueue_blames(struct blame_scoreboard *sb,struct blame_origin *porigin, 476struct blame_entry *sorted) 477{ 478if(porigin->suspects) 479 porigin->suspects =blame_merge(porigin->suspects, sorted); 480else{ 481struct blame_origin *o; 482for(o = porigin->commit->util; o; o = o->next) { 483if(o->suspects) { 484 porigin->suspects = sorted; 485return; 486} 487} 488 porigin->suspects = sorted; 489prio_queue_put(&sb->commits, porigin->commit); 490} 491} 492 493/* 494 * Fill the blob_sha1 field of an origin if it hasn't, so that later 495 * call to fill_origin_blob() can use it to locate the data. blob_sha1 496 * for an origin is also used to pass the blame for the entire file to 497 * the parent to detect the case where a child's blob is identical to 498 * that of its parent's. 499 * 500 * This also fills origin->mode for corresponding tree path. 501 */ 502static intfill_blob_sha1_and_mode(struct blame_origin *origin) 503{ 504if(!is_null_oid(&origin->blob_oid)) 505return0; 506if(get_tree_entry(&origin->commit->object.oid, origin->path, &origin->blob_oid, &origin->mode)) 507goto error_out; 508if(oid_object_info(the_repository, &origin->blob_oid, NULL) != OBJ_BLOB) 509goto error_out; 510return0; 511 error_out: 512oidclr(&origin->blob_oid); 513 origin->mode = S_IFINVALID; 514return-1; 515} 516 517/* 518 * We have an origin -- check if the same path exists in the 519 * parent and return an origin structure to represent it. 520 */ 521static struct blame_origin *find_origin(struct commit *parent, 522struct blame_origin *origin) 523{ 524struct blame_origin *porigin; 525struct diff_options diff_opts; 526const char*paths[2]; 527 528/* First check any existing origins */ 529for(porigin = parent->util; porigin; porigin = porigin->next) 530if(!strcmp(porigin->path, origin->path)) { 531/* 532 * The same path between origin and its parent 533 * without renaming -- the most common case. 534 */ 535returnblame_origin_incref(porigin); 536} 537 538/* See if the origin->path is different between parent 539 * and origin first. Most of the time they are the 540 * same and diff-tree is fairly efficient about this. 541 */ 542diff_setup(&diff_opts); 543 diff_opts.flags.recursive =1; 544 diff_opts.detect_rename =0; 545 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT; 546 paths[0] = origin->path; 547 paths[1] = NULL; 548 549parse_pathspec(&diff_opts.pathspec, 550 PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL, 551 PATHSPEC_LITERAL_PATH,"", paths); 552diff_setup_done(&diff_opts); 553 554if(is_null_oid(&origin->commit->object.oid)) 555do_diff_cache(&parent->tree->object.oid, &diff_opts); 556else 557diff_tree_oid(&parent->tree->object.oid, 558&origin->commit->tree->object.oid, 559"", &diff_opts); 560diffcore_std(&diff_opts); 561 562if(!diff_queued_diff.nr) { 563/* The path is the same as parent */ 564 porigin =get_origin(parent, origin->path); 565oidcpy(&porigin->blob_oid, &origin->blob_oid); 566 porigin->mode = origin->mode; 567}else{ 568/* 569 * Since origin->path is a pathspec, if the parent 570 * commit had it as a directory, we will see a whole 571 * bunch of deletion of files in the directory that we 572 * do not care about. 573 */ 574int i; 575struct diff_filepair *p = NULL; 576for(i =0; i < diff_queued_diff.nr; i++) { 577const char*name; 578 p = diff_queued_diff.queue[i]; 579 name = p->one->path ? p->one->path : p->two->path; 580if(!strcmp(name, origin->path)) 581break; 582} 583if(!p) 584die("internal error in blame::find_origin"); 585switch(p->status) { 586default: 587die("internal error in blame::find_origin (%c)", 588 p->status); 589case'M': 590 porigin =get_origin(parent, origin->path); 591oidcpy(&porigin->blob_oid, &p->one->oid); 592 porigin->mode = p->one->mode; 593break; 594case'A': 595case'T': 596/* Did not exist in parent, or type changed */ 597break; 598} 599} 600diff_flush(&diff_opts); 601clear_pathspec(&diff_opts.pathspec); 602return porigin; 603} 604 605/* 606 * We have an origin -- find the path that corresponds to it in its 607 * parent and return an origin structure to represent it. 608 */ 609static struct blame_origin *find_rename(struct commit *parent, 610struct blame_origin *origin) 611{ 612struct blame_origin *porigin = NULL; 613struct diff_options diff_opts; 614int i; 615 616diff_setup(&diff_opts); 617 diff_opts.flags.recursive =1; 618 diff_opts.detect_rename = DIFF_DETECT_RENAME; 619 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT; 620 diff_opts.single_follow = origin->path; 621diff_setup_done(&diff_opts); 622 623if(is_null_oid(&origin->commit->object.oid)) 624do_diff_cache(&parent->tree->object.oid, &diff_opts); 625else 626diff_tree_oid(&parent->tree->object.oid, 627&origin->commit->tree->object.oid, 628"", &diff_opts); 629diffcore_std(&diff_opts); 630 631for(i =0; i < diff_queued_diff.nr; i++) { 632struct diff_filepair *p = diff_queued_diff.queue[i]; 633if((p->status =='R'|| p->status =='C') && 634!strcmp(p->two->path, origin->path)) { 635 porigin =get_origin(parent, p->one->path); 636oidcpy(&porigin->blob_oid, &p->one->oid); 637 porigin->mode = p->one->mode; 638break; 639} 640} 641diff_flush(&diff_opts); 642clear_pathspec(&diff_opts.pathspec); 643return porigin; 644} 645 646/* 647 * Append a new blame entry to a given output queue. 648 */ 649static voidadd_blame_entry(struct blame_entry ***queue, 650const struct blame_entry *src) 651{ 652struct blame_entry *e =xmalloc(sizeof(*e)); 653memcpy(e, src,sizeof(*e)); 654blame_origin_incref(e->suspect); 655 656 e->next = **queue; 657**queue = e; 658*queue = &e->next; 659} 660 661/* 662 * src typically is on-stack; we want to copy the information in it to 663 * a malloced blame_entry that gets added to the given queue. The 664 * origin of dst loses a refcnt. 665 */ 666static voiddup_entry(struct blame_entry ***queue, 667struct blame_entry *dst,struct blame_entry *src) 668{ 669blame_origin_incref(src->suspect); 670blame_origin_decref(dst->suspect); 671memcpy(dst, src,sizeof(*src)); 672 dst->next = **queue; 673**queue = dst; 674*queue = &dst->next; 675} 676 677const char*blame_nth_line(struct blame_scoreboard *sb,long lno) 678{ 679return sb->final_buf + sb->lineno[lno]; 680} 681 682/* 683 * It is known that lines between tlno to same came from parent, and e 684 * has an overlap with that range. it also is known that parent's 685 * line plno corresponds to e's line tlno. 686 * 687 * <---- e -----> 688 * <------> 689 * <------------> 690 * <------------> 691 * <------------------> 692 * 693 * Split e into potentially three parts; before this chunk, the chunk 694 * to be blamed for the parent, and after that portion. 695 */ 696static voidsplit_overlap(struct blame_entry *split, 697struct blame_entry *e, 698int tlno,int plno,int same, 699struct blame_origin *parent) 700{ 701int chunk_end_lno; 702memset(split,0,sizeof(struct blame_entry [3])); 703 704if(e->s_lno < tlno) { 705/* there is a pre-chunk part not blamed on parent */ 706 split[0].suspect =blame_origin_incref(e->suspect); 707 split[0].lno = e->lno; 708 split[0].s_lno = e->s_lno; 709 split[0].num_lines = tlno - e->s_lno; 710 split[1].lno = e->lno + tlno - e->s_lno; 711 split[1].s_lno = plno; 712} 713else{ 714 split[1].lno = e->lno; 715 split[1].s_lno = plno + (e->s_lno - tlno); 716} 717 718if(same < e->s_lno + e->num_lines) { 719/* there is a post-chunk part not blamed on parent */ 720 split[2].suspect =blame_origin_incref(e->suspect); 721 split[2].lno = e->lno + (same - e->s_lno); 722 split[2].s_lno = e->s_lno + (same - e->s_lno); 723 split[2].num_lines = e->s_lno + e->num_lines - same; 724 chunk_end_lno = split[2].lno; 725} 726else 727 chunk_end_lno = e->lno + e->num_lines; 728 split[1].num_lines = chunk_end_lno - split[1].lno; 729 730/* 731 * if it turns out there is nothing to blame the parent for, 732 * forget about the splitting. !split[1].suspect signals this. 733 */ 734if(split[1].num_lines <1) 735return; 736 split[1].suspect =blame_origin_incref(parent); 737} 738 739/* 740 * split_overlap() divided an existing blame e into up to three parts 741 * in split. Any assigned blame is moved to queue to 742 * reflect the split. 743 */ 744static voidsplit_blame(struct blame_entry ***blamed, 745struct blame_entry ***unblamed, 746struct blame_entry *split, 747struct blame_entry *e) 748{ 749if(split[0].suspect && split[2].suspect) { 750/* The first part (reuse storage for the existing entry e) */ 751dup_entry(unblamed, e, &split[0]); 752 753/* The last part -- me */ 754add_blame_entry(unblamed, &split[2]); 755 756/* ... and the middle part -- parent */ 757add_blame_entry(blamed, &split[1]); 758} 759else if(!split[0].suspect && !split[2].suspect) 760/* 761 * The parent covers the entire area; reuse storage for 762 * e and replace it with the parent. 763 */ 764dup_entry(blamed, e, &split[1]); 765else if(split[0].suspect) { 766/* me and then parent */ 767dup_entry(unblamed, e, &split[0]); 768add_blame_entry(blamed, &split[1]); 769} 770else{ 771/* parent and then me */ 772dup_entry(blamed, e, &split[1]); 773add_blame_entry(unblamed, &split[2]); 774} 775} 776 777/* 778 * After splitting the blame, the origins used by the 779 * on-stack blame_entry should lose one refcnt each. 780 */ 781static voiddecref_split(struct blame_entry *split) 782{ 783int i; 784 785for(i =0; i <3; i++) 786blame_origin_decref(split[i].suspect); 787} 788 789/* 790 * reverse_blame reverses the list given in head, appending tail. 791 * That allows us to build lists in reverse order, then reverse them 792 * afterwards. This can be faster than building the list in proper 793 * order right away. The reason is that building in proper order 794 * requires writing a link in the _previous_ element, while building 795 * in reverse order just requires placing the list head into the 796 * _current_ element. 797 */ 798 799static struct blame_entry *reverse_blame(struct blame_entry *head, 800struct blame_entry *tail) 801{ 802while(head) { 803struct blame_entry *next = head->next; 804 head->next = tail; 805 tail = head; 806 head = next; 807} 808return tail; 809} 810 811/* 812 * Process one hunk from the patch between the current suspect for 813 * blame_entry e and its parent. This first blames any unfinished 814 * entries before the chunk (which is where target and parent start 815 * differing) on the parent, and then splits blame entries at the 816 * start and at the end of the difference region. Since use of -M and 817 * -C options may lead to overlapping/duplicate source line number 818 * ranges, all we can rely on from sorting/merging is the order of the 819 * first suspect line number. 820 */ 821static voidblame_chunk(struct blame_entry ***dstq,struct blame_entry ***srcq, 822int tlno,int offset,int same, 823struct blame_origin *parent) 824{ 825struct blame_entry *e = **srcq; 826struct blame_entry *samep = NULL, *diffp = NULL; 827 828while(e && e->s_lno < tlno) { 829struct blame_entry *next = e->next; 830/* 831 * current record starts before differing portion. If 832 * it reaches into it, we need to split it up and 833 * examine the second part separately. 834 */ 835if(e->s_lno + e->num_lines > tlno) { 836/* Move second half to a new record */ 837int len = tlno - e->s_lno; 838struct blame_entry *n =xcalloc(1,sizeof(struct blame_entry)); 839 n->suspect = e->suspect; 840 n->lno = e->lno + len; 841 n->s_lno = e->s_lno + len; 842 n->num_lines = e->num_lines - len; 843 e->num_lines = len; 844 e->score =0; 845/* Push new record to diffp */ 846 n->next = diffp; 847 diffp = n; 848}else 849blame_origin_decref(e->suspect); 850/* Pass blame for everything before the differing 851 * chunk to the parent */ 852 e->suspect =blame_origin_incref(parent); 853 e->s_lno += offset; 854 e->next = samep; 855 samep = e; 856 e = next; 857} 858/* 859 * As we don't know how much of a common stretch after this 860 * diff will occur, the currently blamed parts are all that we 861 * can assign to the parent for now. 862 */ 863 864if(samep) { 865**dstq =reverse_blame(samep, **dstq); 866*dstq = &samep->next; 867} 868/* 869 * Prepend the split off portions: everything after e starts 870 * after the blameable portion. 871 */ 872 e =reverse_blame(diffp, e); 873 874/* 875 * Now retain records on the target while parts are different 876 * from the parent. 877 */ 878 samep = NULL; 879 diffp = NULL; 880while(e && e->s_lno < same) { 881struct blame_entry *next = e->next; 882 883/* 884 * If current record extends into sameness, need to split. 885 */ 886if(e->s_lno + e->num_lines > same) { 887/* 888 * Move second half to a new record to be 889 * processed by later chunks 890 */ 891int len = same - e->s_lno; 892struct blame_entry *n =xcalloc(1,sizeof(struct blame_entry)); 893 n->suspect =blame_origin_incref(e->suspect); 894 n->lno = e->lno + len; 895 n->s_lno = e->s_lno + len; 896 n->num_lines = e->num_lines - len; 897 e->num_lines = len; 898 e->score =0; 899/* Push new record to samep */ 900 n->next = samep; 901 samep = n; 902} 903 e->next = diffp; 904 diffp = e; 905 e = next; 906} 907**srcq =reverse_blame(diffp,reverse_blame(samep, e)); 908/* Move across elements that are in the unblamable portion */ 909if(diffp) 910*srcq = &diffp->next; 911} 912 913struct blame_chunk_cb_data { 914struct blame_origin *parent; 915long offset; 916struct blame_entry **dstq; 917struct blame_entry **srcq; 918}; 919 920/* diff chunks are from parent to target */ 921static intblame_chunk_cb(long start_a,long count_a, 922long start_b,long count_b,void*data) 923{ 924struct blame_chunk_cb_data *d = data; 925if(start_a - start_b != d->offset) 926die("internal error in blame::blame_chunk_cb"); 927blame_chunk(&d->dstq, &d->srcq, start_b, start_a - start_b, 928 start_b + count_b, d->parent); 929 d->offset = start_a + count_a - (start_b + count_b); 930return0; 931} 932 933/* 934 * We are looking at the origin 'target' and aiming to pass blame 935 * for the lines it is suspected to its parent. Run diff to find 936 * which lines came from parent and pass blame for them. 937 */ 938static voidpass_blame_to_parent(struct blame_scoreboard *sb, 939struct blame_origin *target, 940struct blame_origin *parent) 941{ 942 mmfile_t file_p, file_o; 943struct blame_chunk_cb_data d; 944struct blame_entry *newdest = NULL; 945 946if(!target->suspects) 947return;/* nothing remains for this target */ 948 949 d.parent = parent; 950 d.offset =0; 951 d.dstq = &newdest; d.srcq = &target->suspects; 952 953fill_origin_blob(&sb->revs->diffopt, parent, &file_p, &sb->num_read_blob); 954fill_origin_blob(&sb->revs->diffopt, target, &file_o, &sb->num_read_blob); 955 sb->num_get_patch++; 956 957if(diff_hunks(&file_p, &file_o, blame_chunk_cb, &d, sb->xdl_opts)) 958die("unable to generate diff (%s->%s)", 959oid_to_hex(&parent->commit->object.oid), 960oid_to_hex(&target->commit->object.oid)); 961/* The rest are the same as the parent */ 962blame_chunk(&d.dstq, &d.srcq, INT_MAX, d.offset, INT_MAX, parent); 963*d.dstq = NULL; 964queue_blames(sb, parent, newdest); 965 966return; 967} 968 969/* 970 * The lines in blame_entry after splitting blames many times can become 971 * very small and trivial, and at some point it becomes pointless to 972 * blame the parents. E.g. "\t\t}\n\t}\n\n" appears everywhere in any 973 * ordinary C program, and it is not worth to say it was copied from 974 * totally unrelated file in the parent. 975 * 976 * Compute how trivial the lines in the blame_entry are. 977 */ 978unsignedblame_entry_score(struct blame_scoreboard *sb,struct blame_entry *e) 979{ 980unsigned score; 981const char*cp, *ep; 982 983if(e->score) 984return e->score; 985 986 score =1; 987 cp =blame_nth_line(sb, e->lno); 988 ep =blame_nth_line(sb, e->lno + e->num_lines); 989while(cp < ep) { 990unsigned ch = *((unsigned char*)cp); 991if(isalnum(ch)) 992 score++; 993 cp++; 994} 995 e->score = score; 996return score; 997} 998 999/*1000 * best_so_far[] and potential[] are both a split of an existing blame_entry1001 * that passes blame to the parent. Maintain best_so_far the best split so1002 * far, by comparing potential and best_so_far and copying potential into1003 * bst_so_far as needed.1004 */1005static voidcopy_split_if_better(struct blame_scoreboard *sb,1006struct blame_entry *best_so_far,1007struct blame_entry *potential)1008{1009int i;10101011if(!potential[1].suspect)1012return;1013if(best_so_far[1].suspect) {1014if(blame_entry_score(sb, &potential[1]) <1015blame_entry_score(sb, &best_so_far[1]))1016return;1017}10181019for(i =0; i <3; i++)1020blame_origin_incref(potential[i].suspect);1021decref_split(best_so_far);1022memcpy(best_so_far, potential,sizeof(struct blame_entry[3]));1023}10241025/*1026 * We are looking at a part of the final image represented by1027 * ent (tlno and same are offset by ent->s_lno).1028 * tlno is where we are looking at in the final image.1029 * up to (but not including) same match preimage.1030 * plno is where we are looking at in the preimage.1031 *1032 * <-------------- final image ---------------------->1033 * <------ent------>1034 * ^tlno ^same1035 * <---------preimage----->1036 * ^plno1037 *1038 * All line numbers are 0-based.1039 */1040static voidhandle_split(struct blame_scoreboard *sb,1041struct blame_entry *ent,1042int tlno,int plno,int same,1043struct blame_origin *parent,1044struct blame_entry *split)1045{1046if(ent->num_lines <= tlno)1047return;1048if(tlno < same) {1049struct blame_entry potential[3];1050 tlno += ent->s_lno;1051 same += ent->s_lno;1052split_overlap(potential, ent, tlno, plno, same, parent);1053copy_split_if_better(sb, split, potential);1054decref_split(potential);1055}1056}10571058struct handle_split_cb_data {1059struct blame_scoreboard *sb;1060struct blame_entry *ent;1061struct blame_origin *parent;1062struct blame_entry *split;1063long plno;1064long tlno;1065};10661067static inthandle_split_cb(long start_a,long count_a,1068long start_b,long count_b,void*data)1069{1070struct handle_split_cb_data *d = data;1071handle_split(d->sb, d->ent, d->tlno, d->plno, start_b, d->parent,1072 d->split);1073 d->plno = start_a + count_a;1074 d->tlno = start_b + count_b;1075return0;1076}10771078/*1079 * Find the lines from parent that are the same as ent so that1080 * we can pass blames to it. file_p has the blob contents for1081 * the parent.1082 */1083static voidfind_copy_in_blob(struct blame_scoreboard *sb,1084struct blame_entry *ent,1085struct blame_origin *parent,1086struct blame_entry *split,1087 mmfile_t *file_p)1088{1089const char*cp;1090 mmfile_t file_o;1091struct handle_split_cb_data d;10921093memset(&d,0,sizeof(d));1094 d.sb = sb; d.ent = ent; d.parent = parent; d.split = split;1095/*1096 * Prepare mmfile that contains only the lines in ent.1097 */1098 cp =blame_nth_line(sb, ent->lno);1099 file_o.ptr = (char*) cp;1100 file_o.size =blame_nth_line(sb, ent->lno + ent->num_lines) - cp;11011102/*1103 * file_o is a part of final image we are annotating.1104 * file_p partially may match that image.1105 */1106memset(split,0,sizeof(struct blame_entry [3]));1107if(diff_hunks(file_p, &file_o, handle_split_cb, &d, sb->xdl_opts))1108die("unable to generate diff (%s)",1109oid_to_hex(&parent->commit->object.oid));1110/* remainder, if any, all match the preimage */1111handle_split(sb, ent, d.tlno, d.plno, ent->num_lines, parent, split);1112}11131114/* Move all blame entries from list *source that have a score smaller1115 * than score_min to the front of list *small.1116 * Returns a pointer to the link pointing to the old head of the small list.1117 */11181119static struct blame_entry **filter_small(struct blame_scoreboard *sb,1120struct blame_entry **small,1121struct blame_entry **source,1122unsigned score_min)1123{1124struct blame_entry *p = *source;1125struct blame_entry *oldsmall = *small;1126while(p) {1127if(blame_entry_score(sb, p) <= score_min) {1128*small = p;1129 small = &p->next;1130 p = *small;1131}else{1132*source = p;1133 source = &p->next;1134 p = *source;1135}1136}1137*small = oldsmall;1138*source = NULL;1139return small;1140}11411142/*1143 * See if lines currently target is suspected for can be attributed to1144 * parent.1145 */1146static voidfind_move_in_parent(struct blame_scoreboard *sb,1147struct blame_entry ***blamed,1148struct blame_entry **toosmall,1149struct blame_origin *target,1150struct blame_origin *parent)1151{1152struct blame_entry *e, split[3];1153struct blame_entry *unblamed = target->suspects;1154struct blame_entry *leftover = NULL;1155 mmfile_t file_p;11561157if(!unblamed)1158return;/* nothing remains for this target */11591160fill_origin_blob(&sb->revs->diffopt, parent, &file_p, &sb->num_read_blob);1161if(!file_p.ptr)1162return;11631164/* At each iteration, unblamed has a NULL-terminated list of1165 * entries that have not yet been tested for blame. leftover1166 * contains the reversed list of entries that have been tested1167 * without being assignable to the parent.1168 */1169do{1170struct blame_entry **unblamedtail = &unblamed;1171struct blame_entry *next;1172for(e = unblamed; e; e = next) {1173 next = e->next;1174find_copy_in_blob(sb, e, parent, split, &file_p);1175if(split[1].suspect &&1176 sb->move_score <blame_entry_score(sb, &split[1])) {1177split_blame(blamed, &unblamedtail, split, e);1178}else{1179 e->next = leftover;1180 leftover = e;1181}1182decref_split(split);1183}1184*unblamedtail = NULL;1185 toosmall =filter_small(sb, toosmall, &unblamed, sb->move_score);1186}while(unblamed);1187 target->suspects =reverse_blame(leftover, NULL);1188}11891190struct blame_list {1191struct blame_entry *ent;1192struct blame_entry split[3];1193};11941195/*1196 * Count the number of entries the target is suspected for,1197 * and prepare a list of entry and the best split.1198 */1199static struct blame_list *setup_blame_list(struct blame_entry *unblamed,1200int*num_ents_p)1201{1202struct blame_entry *e;1203int num_ents, i;1204struct blame_list *blame_list = NULL;12051206for(e = unblamed, num_ents =0; e; e = e->next)1207 num_ents++;1208if(num_ents) {1209 blame_list =xcalloc(num_ents,sizeof(struct blame_list));1210for(e = unblamed, i =0; e; e = e->next)1211 blame_list[i++].ent = e;1212}1213*num_ents_p = num_ents;1214return blame_list;1215}12161217/*1218 * For lines target is suspected for, see if we can find code movement1219 * across file boundary from the parent commit. porigin is the path1220 * in the parent we already tried.1221 */1222static voidfind_copy_in_parent(struct blame_scoreboard *sb,1223struct blame_entry ***blamed,1224struct blame_entry **toosmall,1225struct blame_origin *target,1226struct commit *parent,1227struct blame_origin *porigin,1228int opt)1229{1230struct diff_options diff_opts;1231int i, j;1232struct blame_list *blame_list;1233int num_ents;1234struct blame_entry *unblamed = target->suspects;1235struct blame_entry *leftover = NULL;12361237if(!unblamed)1238return;/* nothing remains for this target */12391240diff_setup(&diff_opts);1241 diff_opts.flags.recursive =1;1242 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;12431244diff_setup_done(&diff_opts);12451246/* Try "find copies harder" on new path if requested;1247 * we do not want to use diffcore_rename() actually to1248 * match things up; find_copies_harder is set only to1249 * force diff_tree_oid() to feed all filepairs to diff_queue,1250 * and this code needs to be after diff_setup_done(), which1251 * usually makes find-copies-harder imply copy detection.1252 */1253if((opt & PICKAXE_BLAME_COPY_HARDEST)1254|| ((opt & PICKAXE_BLAME_COPY_HARDER)1255&& (!porigin ||strcmp(target->path, porigin->path))))1256 diff_opts.flags.find_copies_harder =1;12571258if(is_null_oid(&target->commit->object.oid))1259do_diff_cache(&parent->tree->object.oid, &diff_opts);1260else1261diff_tree_oid(&parent->tree->object.oid,1262&target->commit->tree->object.oid,1263"", &diff_opts);12641265if(!diff_opts.flags.find_copies_harder)1266diffcore_std(&diff_opts);12671268do{1269struct blame_entry **unblamedtail = &unblamed;1270 blame_list =setup_blame_list(unblamed, &num_ents);12711272for(i =0; i < diff_queued_diff.nr; i++) {1273struct diff_filepair *p = diff_queued_diff.queue[i];1274struct blame_origin *norigin;1275 mmfile_t file_p;1276struct blame_entry potential[3];12771278if(!DIFF_FILE_VALID(p->one))1279continue;/* does not exist in parent */1280if(S_ISGITLINK(p->one->mode))1281continue;/* ignore git links */1282if(porigin && !strcmp(p->one->path, porigin->path))1283/* find_move already dealt with this path */1284continue;12851286 norigin =get_origin(parent, p->one->path);1287oidcpy(&norigin->blob_oid, &p->one->oid);1288 norigin->mode = p->one->mode;1289fill_origin_blob(&sb->revs->diffopt, norigin, &file_p, &sb->num_read_blob);1290if(!file_p.ptr)1291continue;12921293for(j =0; j < num_ents; j++) {1294find_copy_in_blob(sb, blame_list[j].ent,1295 norigin, potential, &file_p);1296copy_split_if_better(sb, blame_list[j].split,1297 potential);1298decref_split(potential);1299}1300blame_origin_decref(norigin);1301}13021303for(j =0; j < num_ents; j++) {1304struct blame_entry *split = blame_list[j].split;1305if(split[1].suspect &&1306 sb->copy_score <blame_entry_score(sb, &split[1])) {1307split_blame(blamed, &unblamedtail, split,1308 blame_list[j].ent);1309}else{1310 blame_list[j].ent->next = leftover;1311 leftover = blame_list[j].ent;1312}1313decref_split(split);1314}1315free(blame_list);1316*unblamedtail = NULL;1317 toosmall =filter_small(sb, toosmall, &unblamed, sb->copy_score);1318}while(unblamed);1319 target->suspects =reverse_blame(leftover, NULL);1320diff_flush(&diff_opts);1321clear_pathspec(&diff_opts.pathspec);1322}13231324/*1325 * The blobs of origin and porigin exactly match, so everything1326 * origin is suspected for can be blamed on the parent.1327 */1328static voidpass_whole_blame(struct blame_scoreboard *sb,1329struct blame_origin *origin,struct blame_origin *porigin)1330{1331struct blame_entry *e, *suspects;13321333if(!porigin->file.ptr && origin->file.ptr) {1334/* Steal its file */1335 porigin->file = origin->file;1336 origin->file.ptr = NULL;1337}1338 suspects = origin->suspects;1339 origin->suspects = NULL;1340for(e = suspects; e; e = e->next) {1341blame_origin_incref(porigin);1342blame_origin_decref(e->suspect);1343 e->suspect = porigin;1344}1345queue_blames(sb, porigin, suspects);1346}13471348/*1349 * We pass blame from the current commit to its parents. We keep saying1350 * "parent" (and "porigin"), but what we mean is to find scapegoat to1351 * exonerate ourselves.1352 */1353static struct commit_list *first_scapegoat(struct rev_info *revs,struct commit *commit,1354int reverse)1355{1356if(!reverse) {1357if(revs->first_parent_only &&1358 commit->parents &&1359 commit->parents->next) {1360free_commit_list(commit->parents->next);1361 commit->parents->next = NULL;1362}1363return commit->parents;1364}1365returnlookup_decoration(&revs->children, &commit->object);1366}13671368static intnum_scapegoats(struct rev_info *revs,struct commit *commit,int reverse)1369{1370struct commit_list *l =first_scapegoat(revs, commit, reverse);1371returncommit_list_count(l);1372}13731374/* Distribute collected unsorted blames to the respected sorted lists1375 * in the various origins.1376 */1377static voiddistribute_blame(struct blame_scoreboard *sb,struct blame_entry *blamed)1378{1379 blamed =llist_mergesort(blamed, get_next_blame, set_next_blame,1380 compare_blame_suspect);1381while(blamed)1382{1383struct blame_origin *porigin = blamed->suspect;1384struct blame_entry *suspects = NULL;1385do{1386struct blame_entry *next = blamed->next;1387 blamed->next = suspects;1388 suspects = blamed;1389 blamed = next;1390}while(blamed && blamed->suspect == porigin);1391 suspects =reverse_blame(suspects, NULL);1392queue_blames(sb, porigin, suspects);1393}1394}13951396#define MAXSG 1613971398static voidpass_blame(struct blame_scoreboard *sb,struct blame_origin *origin,int opt)1399{1400struct rev_info *revs = sb->revs;1401int i, pass, num_sg;1402struct commit *commit = origin->commit;1403struct commit_list *sg;1404struct blame_origin *sg_buf[MAXSG];1405struct blame_origin *porigin, **sg_origin = sg_buf;1406struct blame_entry *toosmall = NULL;1407struct blame_entry *blames, **blametail = &blames;14081409 num_sg =num_scapegoats(revs, commit, sb->reverse);1410if(!num_sg)1411goto finish;1412else if(num_sg <ARRAY_SIZE(sg_buf))1413memset(sg_buf,0,sizeof(sg_buf));1414else1415 sg_origin =xcalloc(num_sg,sizeof(*sg_origin));14161417/*1418 * The first pass looks for unrenamed path to optimize for1419 * common cases, then we look for renames in the second pass.1420 */1421for(pass =0; pass <2- sb->no_whole_file_rename; pass++) {1422struct blame_origin *(*find)(struct commit *,struct blame_origin *);1423 find = pass ? find_rename : find_origin;14241425for(i =0, sg =first_scapegoat(revs, commit, sb->reverse);1426 i < num_sg && sg;1427 sg = sg->next, i++) {1428struct commit *p = sg->item;1429int j, same;14301431if(sg_origin[i])1432continue;1433if(parse_commit(p))1434continue;1435 porigin =find(p, origin);1436if(!porigin)1437continue;1438if(!oidcmp(&porigin->blob_oid, &origin->blob_oid)) {1439pass_whole_blame(sb, origin, porigin);1440blame_origin_decref(porigin);1441goto finish;1442}1443for(j = same =0; j < i; j++)1444if(sg_origin[j] &&1445!oidcmp(&sg_origin[j]->blob_oid, &porigin->blob_oid)) {1446 same =1;1447break;1448}1449if(!same)1450 sg_origin[i] = porigin;1451else1452blame_origin_decref(porigin);1453}1454}14551456 sb->num_commits++;1457for(i =0, sg =first_scapegoat(revs, commit, sb->reverse);1458 i < num_sg && sg;1459 sg = sg->next, i++) {1460struct blame_origin *porigin = sg_origin[i];1461if(!porigin)1462continue;1463if(!origin->previous) {1464blame_origin_incref(porigin);1465 origin->previous = porigin;1466}1467pass_blame_to_parent(sb, origin, porigin);1468if(!origin->suspects)1469goto finish;1470}14711472/*1473 * Optionally find moves in parents' files.1474 */1475if(opt & PICKAXE_BLAME_MOVE) {1476filter_small(sb, &toosmall, &origin->suspects, sb->move_score);1477if(origin->suspects) {1478for(i =0, sg =first_scapegoat(revs, commit, sb->reverse);1479 i < num_sg && sg;1480 sg = sg->next, i++) {1481struct blame_origin *porigin = sg_origin[i];1482if(!porigin)1483continue;1484find_move_in_parent(sb, &blametail, &toosmall, origin, porigin);1485if(!origin->suspects)1486break;1487}1488}1489}14901491/*1492 * Optionally find copies from parents' files.1493 */1494if(opt & PICKAXE_BLAME_COPY) {1495if(sb->copy_score > sb->move_score)1496filter_small(sb, &toosmall, &origin->suspects, sb->copy_score);1497else if(sb->copy_score < sb->move_score) {1498 origin->suspects =blame_merge(origin->suspects, toosmall);1499 toosmall = NULL;1500filter_small(sb, &toosmall, &origin->suspects, sb->copy_score);1501}1502if(!origin->suspects)1503goto finish;15041505for(i =0, sg =first_scapegoat(revs, commit, sb->reverse);1506 i < num_sg && sg;1507 sg = sg->next, i++) {1508struct blame_origin *porigin = sg_origin[i];1509find_copy_in_parent(sb, &blametail, &toosmall,1510 origin, sg->item, porigin, opt);1511if(!origin->suspects)1512goto finish;1513}1514}15151516finish:1517*blametail = NULL;1518distribute_blame(sb, blames);1519/*1520 * prepend toosmall to origin->suspects1521 *1522 * There is no point in sorting: this ends up on a big1523 * unsorted list in the caller anyway.1524 */1525if(toosmall) {1526struct blame_entry **tail = &toosmall;1527while(*tail)1528 tail = &(*tail)->next;1529*tail = origin->suspects;1530 origin->suspects = toosmall;1531}1532for(i =0; i < num_sg; i++) {1533if(sg_origin[i]) {1534drop_origin_blob(sg_origin[i]);1535blame_origin_decref(sg_origin[i]);1536}1537}1538drop_origin_blob(origin);1539if(sg_buf != sg_origin)1540free(sg_origin);1541}15421543/*1544 * The main loop -- while we have blobs with lines whose true origin1545 * is still unknown, pick one blob, and allow its lines to pass blames1546 * to its parents. */1547voidassign_blame(struct blame_scoreboard *sb,int opt)1548{1549struct rev_info *revs = sb->revs;1550struct commit *commit =prio_queue_get(&sb->commits);15511552while(commit) {1553struct blame_entry *ent;1554struct blame_origin *suspect = commit->util;15551556/* find one suspect to break down */1557while(suspect && !suspect->suspects)1558 suspect = suspect->next;15591560if(!suspect) {1561 commit =prio_queue_get(&sb->commits);1562continue;1563}15641565assert(commit == suspect->commit);15661567/*1568 * We will use this suspect later in the loop,1569 * so hold onto it in the meantime.1570 */1571blame_origin_incref(suspect);1572parse_commit(commit);1573if(sb->reverse ||1574(!(commit->object.flags & UNINTERESTING) &&1575!(revs->max_age != -1&& commit->date < revs->max_age)))1576pass_blame(sb, suspect, opt);1577else{1578 commit->object.flags |= UNINTERESTING;1579if(commit->object.parsed)1580mark_parents_uninteresting(commit);1581}1582/* treat root commit as boundary */1583if(!commit->parents && !sb->show_root)1584 commit->object.flags |= UNINTERESTING;15851586/* Take responsibility for the remaining entries */1587 ent = suspect->suspects;1588if(ent) {1589 suspect->guilty =1;1590for(;;) {1591struct blame_entry *next = ent->next;1592if(sb->found_guilty_entry)1593 sb->found_guilty_entry(ent, sb->found_guilty_entry_data);1594if(next) {1595 ent = next;1596continue;1597}1598 ent->next = sb->ent;1599 sb->ent = suspect->suspects;1600 suspect->suspects = NULL;1601break;1602}1603}1604blame_origin_decref(suspect);16051606if(sb->debug)/* sanity */1607sanity_check_refcnt(sb);1608}1609}16101611static const char*get_next_line(const char*start,const char*end)1612{1613const char*nl =memchr(start,'\n', end - start);1614return nl ? nl +1: end;1615}16161617/*1618 * To allow quick access to the contents of nth line in the1619 * final image, prepare an index in the scoreboard.1620 */1621static intprepare_lines(struct blame_scoreboard *sb)1622{1623const char*buf = sb->final_buf;1624unsigned long len = sb->final_buf_size;1625const char*end = buf + len;1626const char*p;1627int*lineno;1628int num =0;16291630for(p = buf; p < end; p =get_next_line(p, end))1631 num++;16321633ALLOC_ARRAY(sb->lineno, num +1);1634 lineno = sb->lineno;16351636for(p = buf; p < end; p =get_next_line(p, end))1637*lineno++ = p - buf;16381639*lineno = len;16401641 sb->num_lines = num;1642return sb->num_lines;1643}16441645static struct commit *find_single_final(struct rev_info *revs,1646const char**name_p)1647{1648int i;1649struct commit *found = NULL;1650const char*name = NULL;16511652for(i =0; i < revs->pending.nr; i++) {1653struct object *obj = revs->pending.objects[i].item;1654if(obj->flags & UNINTERESTING)1655continue;1656 obj =deref_tag(obj, NULL,0);1657if(obj->type != OBJ_COMMIT)1658die("Non commit%s?", revs->pending.objects[i].name);1659if(found)1660die("More than one commit to dig from%sand%s?",1661 revs->pending.objects[i].name, name);1662 found = (struct commit *)obj;1663 name = revs->pending.objects[i].name;1664}1665if(name_p)1666*name_p =xstrdup_or_null(name);1667return found;1668}16691670static struct commit *dwim_reverse_initial(struct rev_info *revs,1671const char**name_p)1672{1673/*1674 * DWIM "git blame --reverse ONE -- PATH" as1675 * "git blame --reverse ONE..HEAD -- PATH" but only do so1676 * when it makes sense.1677 */1678struct object *obj;1679struct commit *head_commit;1680struct object_id head_oid;16811682if(revs->pending.nr !=1)1683return NULL;16841685/* Is that sole rev a committish? */1686 obj = revs->pending.objects[0].item;1687 obj =deref_tag(obj, NULL,0);1688if(obj->type != OBJ_COMMIT)1689return NULL;16901691/* Do we have HEAD? */1692if(!resolve_ref_unsafe("HEAD", RESOLVE_REF_READING, &head_oid, NULL))1693return NULL;1694 head_commit =lookup_commit_reference_gently(&head_oid,1);1695if(!head_commit)1696return NULL;16971698/* Turn "ONE" into "ONE..HEAD" then */1699 obj->flags |= UNINTERESTING;1700add_pending_object(revs, &head_commit->object,"HEAD");17011702if(name_p)1703*name_p = revs->pending.objects[0].name;1704return(struct commit *)obj;1705}17061707static struct commit *find_single_initial(struct rev_info *revs,1708const char**name_p)1709{1710int i;1711struct commit *found = NULL;1712const char*name = NULL;17131714/*1715 * There must be one and only one negative commit, and it must be1716 * the boundary.1717 */1718for(i =0; i < revs->pending.nr; i++) {1719struct object *obj = revs->pending.objects[i].item;1720if(!(obj->flags & UNINTERESTING))1721continue;1722 obj =deref_tag(obj, NULL,0);1723if(obj->type != OBJ_COMMIT)1724die("Non commit%s?", revs->pending.objects[i].name);1725if(found)1726die("More than one commit to dig up from,%sand%s?",1727 revs->pending.objects[i].name, name);1728 found = (struct commit *) obj;1729 name = revs->pending.objects[i].name;1730}17311732if(!name)1733 found =dwim_reverse_initial(revs, &name);1734if(!name)1735die("No commit to dig up from?");17361737if(name_p)1738*name_p =xstrdup(name);1739return found;1740}17411742voidinit_scoreboard(struct blame_scoreboard *sb)1743{1744memset(sb,0,sizeof(struct blame_scoreboard));1745 sb->move_score = BLAME_DEFAULT_MOVE_SCORE;1746 sb->copy_score = BLAME_DEFAULT_COPY_SCORE;1747}17481749voidsetup_scoreboard(struct blame_scoreboard *sb,const char*path,struct blame_origin **orig)1750{1751const char*final_commit_name = NULL;1752struct blame_origin *o;1753struct commit *final_commit = NULL;1754enum object_type type;17551756if(sb->reverse && sb->contents_from)1757die(_("--contents and --reverse do not blend well."));17581759if(!sb->reverse) {1760 sb->final =find_single_final(sb->revs, &final_commit_name);1761 sb->commits.compare = compare_commits_by_commit_date;1762}else{1763 sb->final =find_single_initial(sb->revs, &final_commit_name);1764 sb->commits.compare = compare_commits_by_reverse_commit_date;1765}17661767if(sb->final && sb->contents_from)1768die(_("cannot use --contents with final commit object name"));17691770if(sb->reverse && sb->revs->first_parent_only)1771 sb->revs->children.name = NULL;17721773if(!sb->final) {1774/*1775 * "--not A B -- path" without anything positive;1776 * do not default to HEAD, but use the working tree1777 * or "--contents".1778 */1779setup_work_tree();1780 sb->final =fake_working_tree_commit(&sb->revs->diffopt,1781 path, sb->contents_from);1782add_pending_object(sb->revs, &(sb->final->object),":");1783}17841785if(sb->reverse && sb->revs->first_parent_only) {1786 final_commit =find_single_final(sb->revs, NULL);1787if(!final_commit)1788die(_("--reverse and --first-parent together require specified latest commit"));1789}17901791/*1792 * If we have bottom, this will mark the ancestors of the1793 * bottom commits we would reach while traversing as1794 * uninteresting.1795 */1796if(prepare_revision_walk(sb->revs))1797die(_("revision walk setup failed"));17981799if(sb->reverse && sb->revs->first_parent_only) {1800struct commit *c = final_commit;18011802 sb->revs->children.name ="children";1803while(c->parents &&1804oidcmp(&c->object.oid, &sb->final->object.oid)) {1805struct commit_list *l =xcalloc(1,sizeof(*l));18061807 l->item = c;1808if(add_decoration(&sb->revs->children,1809&c->parents->item->object, l))1810die("BUG: not unique item in first-parent chain");1811 c = c->parents->item;1812}18131814if(oidcmp(&c->object.oid, &sb->final->object.oid))1815die(_("--reverse --first-parent together require range along first-parent chain"));1816}18171818if(is_null_oid(&sb->final->object.oid)) {1819 o = sb->final->util;1820 sb->final_buf =xmemdupz(o->file.ptr, o->file.size);1821 sb->final_buf_size = o->file.size;1822}1823else{1824 o =get_origin(sb->final, path);1825if(fill_blob_sha1_and_mode(o))1826die(_("no such path%sin%s"), path, final_commit_name);18271828if(sb->revs->diffopt.flags.allow_textconv &&1829textconv_object(path, o->mode, &o->blob_oid,1, (char**) &sb->final_buf,1830&sb->final_buf_size))1831;1832else1833 sb->final_buf =read_object_file(&o->blob_oid, &type,1834&sb->final_buf_size);18351836if(!sb->final_buf)1837die(_("cannot read blob%sfor path%s"),1838oid_to_hex(&o->blob_oid),1839 path);1840}1841 sb->num_read_blob++;1842prepare_lines(sb);18431844if(orig)1845*orig = o;18461847free((char*)final_commit_name);1848}1849185018511852struct blame_entry *blame_entry_prepend(struct blame_entry *head,1853long start,long end,1854struct blame_origin *o)1855{1856struct blame_entry *new_head =xcalloc(1,sizeof(struct blame_entry));1857 new_head->lno = start;1858 new_head->num_lines = end - start;1859 new_head->suspect = o;1860 new_head->s_lno = start;1861 new_head->next = head;1862blame_origin_incref(o);1863return new_head;1864}