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->hash, path, blob_oid.hash, &mode) && 84sha1_object_info(blob_oid.hash, 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 size, 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.hash, 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(DIFF_OPT_TST(opt, 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_sha1_file(buf.buf, buf.len, OBJ_BLOB, origin->blob_oid.hash); 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 size =cache_entry_size(len); 256 ce =xcalloc(1, size); 257oidcpy(&ce->oid, &origin->blob_oid); 258memcpy(ce->name, path, len); 259 ce->ce_flags =create_ce_flags(0); 260 ce->ce_namelen = len; 261 ce->ce_mode =create_ce_mode(mode); 262add_cache_entry(ce, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE); 263 264cache_tree_invalidate_path(&the_index, path); 265 266return commit; 267} 268 269 270 271static intdiff_hunks(mmfile_t *file_a, mmfile_t *file_b, 272 xdl_emit_hunk_consume_func_t hunk_func,void*cb_data,int xdl_opts) 273{ 274 xpparam_t xpp = {0}; 275 xdemitconf_t xecfg = {0}; 276 xdemitcb_t ecb = {NULL}; 277 278 xpp.flags = xdl_opts; 279 xecfg.hunk_func = hunk_func; 280 ecb.priv = cb_data; 281returnxdi_diff(file_a, file_b, &xpp, &xecfg, &ecb); 282} 283 284/* 285 * Given an origin, prepare mmfile_t structure to be used by the 286 * diff machinery 287 */ 288static voidfill_origin_blob(struct diff_options *opt, 289struct blame_origin *o, mmfile_t *file,int*num_read_blob) 290{ 291if(!o->file.ptr) { 292enum object_type type; 293unsigned long file_size; 294 295(*num_read_blob)++; 296if(DIFF_OPT_TST(opt, ALLOW_TEXTCONV) && 297textconv_object(o->path, o->mode, &o->blob_oid,1, &file->ptr, &file_size)) 298; 299else 300 file->ptr =read_sha1_file(o->blob_oid.hash, &type, 301&file_size); 302 file->size = file_size; 303 304if(!file->ptr) 305die("Cannot read blob%sfor path%s", 306oid_to_hex(&o->blob_oid), 307 o->path); 308 o->file = *file; 309} 310else 311*file = o->file; 312} 313 314static voiddrop_origin_blob(struct blame_origin *o) 315{ 316if(o->file.ptr) { 317free(o->file.ptr); 318 o->file.ptr = NULL; 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.hash, 507 origin->path, 508 origin->blob_oid.hash, &origin->mode)) 509goto error_out; 510if(sha1_object_info(origin->blob_oid.hash, NULL) != OBJ_BLOB) 511goto error_out; 512return0; 513 error_out: 514oidclr(&origin->blob_oid); 515 origin->mode = S_IFINVALID; 516return-1; 517} 518 519/* 520 * We have an origin -- check if the same path exists in the 521 * parent and return an origin structure to represent it. 522 */ 523static struct blame_origin *find_origin(struct commit *parent, 524struct blame_origin *origin) 525{ 526struct blame_origin *porigin; 527struct diff_options diff_opts; 528const char*paths[2]; 529 530/* First check any existing origins */ 531for(porigin = parent->util; porigin; porigin = porigin->next) 532if(!strcmp(porigin->path, origin->path)) { 533/* 534 * The same path between origin and its parent 535 * without renaming -- the most common case. 536 */ 537returnblame_origin_incref(porigin); 538} 539 540/* See if the origin->path is different between parent 541 * and origin first. Most of the time they are the 542 * same and diff-tree is fairly efficient about this. 543 */ 544diff_setup(&diff_opts); 545DIFF_OPT_SET(&diff_opts, RECURSIVE); 546 diff_opts.detect_rename =0; 547 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT; 548 paths[0] = origin->path; 549 paths[1] = NULL; 550 551parse_pathspec(&diff_opts.pathspec, 552 PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL, 553 PATHSPEC_LITERAL_PATH,"", paths); 554diff_setup_done(&diff_opts); 555 556if(is_null_oid(&origin->commit->object.oid)) 557do_diff_cache(&parent->tree->object.oid, &diff_opts); 558else 559diff_tree_sha1(parent->tree->object.oid.hash, 560 origin->commit->tree->object.oid.hash, 561"", &diff_opts); 562diffcore_std(&diff_opts); 563 564if(!diff_queued_diff.nr) { 565/* The path is the same as parent */ 566 porigin =get_origin(parent, origin->path); 567oidcpy(&porigin->blob_oid, &origin->blob_oid); 568 porigin->mode = origin->mode; 569}else{ 570/* 571 * Since origin->path is a pathspec, if the parent 572 * commit had it as a directory, we will see a whole 573 * bunch of deletion of files in the directory that we 574 * do not care about. 575 */ 576int i; 577struct diff_filepair *p = NULL; 578for(i =0; i < diff_queued_diff.nr; i++) { 579const char*name; 580 p = diff_queued_diff.queue[i]; 581 name = p->one->path ? p->one->path : p->two->path; 582if(!strcmp(name, origin->path)) 583break; 584} 585if(!p) 586die("internal error in blame::find_origin"); 587switch(p->status) { 588default: 589die("internal error in blame::find_origin (%c)", 590 p->status); 591case'M': 592 porigin =get_origin(parent, origin->path); 593oidcpy(&porigin->blob_oid, &p->one->oid); 594 porigin->mode = p->one->mode; 595break; 596case'A': 597case'T': 598/* Did not exist in parent, or type changed */ 599break; 600} 601} 602diff_flush(&diff_opts); 603clear_pathspec(&diff_opts.pathspec); 604return porigin; 605} 606 607/* 608 * We have an origin -- find the path that corresponds to it in its 609 * parent and return an origin structure to represent it. 610 */ 611static struct blame_origin *find_rename(struct commit *parent, 612struct blame_origin *origin) 613{ 614struct blame_origin *porigin = NULL; 615struct diff_options diff_opts; 616int i; 617 618diff_setup(&diff_opts); 619DIFF_OPT_SET(&diff_opts, RECURSIVE); 620 diff_opts.detect_rename = DIFF_DETECT_RENAME; 621 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT; 622 diff_opts.single_follow = origin->path; 623diff_setup_done(&diff_opts); 624 625if(is_null_oid(&origin->commit->object.oid)) 626do_diff_cache(&parent->tree->object.oid, &diff_opts); 627else 628diff_tree_sha1(parent->tree->object.oid.hash, 629 origin->commit->tree->object.oid.hash, 630"", &diff_opts); 631diffcore_std(&diff_opts); 632 633for(i =0; i < diff_queued_diff.nr; i++) { 634struct diff_filepair *p = diff_queued_diff.queue[i]; 635if((p->status =='R'|| p->status =='C') && 636!strcmp(p->two->path, origin->path)) { 637 porigin =get_origin(parent, p->one->path); 638oidcpy(&porigin->blob_oid, &p->one->oid); 639 porigin->mode = p->one->mode; 640break; 641} 642} 643diff_flush(&diff_opts); 644clear_pathspec(&diff_opts.pathspec); 645return porigin; 646} 647 648/* 649 * Append a new blame entry to a given output queue. 650 */ 651static voidadd_blame_entry(struct blame_entry ***queue, 652const struct blame_entry *src) 653{ 654struct blame_entry *e =xmalloc(sizeof(*e)); 655memcpy(e, src,sizeof(*e)); 656blame_origin_incref(e->suspect); 657 658 e->next = **queue; 659**queue = e; 660*queue = &e->next; 661} 662 663/* 664 * src typically is on-stack; we want to copy the information in it to 665 * a malloced blame_entry that gets added to the given queue. The 666 * origin of dst loses a refcnt. 667 */ 668static voiddup_entry(struct blame_entry ***queue, 669struct blame_entry *dst,struct blame_entry *src) 670{ 671blame_origin_incref(src->suspect); 672blame_origin_decref(dst->suspect); 673memcpy(dst, src,sizeof(*src)); 674 dst->next = **queue; 675**queue = dst; 676*queue = &dst->next; 677} 678 679const char*blame_nth_line(struct blame_scoreboard *sb,long lno) 680{ 681return sb->final_buf + sb->lineno[lno]; 682} 683 684/* 685 * It is known that lines between tlno to same came from parent, and e 686 * has an overlap with that range. it also is known that parent's 687 * line plno corresponds to e's line tlno. 688 * 689 * <---- e -----> 690 * <------> 691 * <------------> 692 * <------------> 693 * <------------------> 694 * 695 * Split e into potentially three parts; before this chunk, the chunk 696 * to be blamed for the parent, and after that portion. 697 */ 698static voidsplit_overlap(struct blame_entry *split, 699struct blame_entry *e, 700int tlno,int plno,int same, 701struct blame_origin *parent) 702{ 703int chunk_end_lno; 704memset(split,0,sizeof(struct blame_entry [3])); 705 706if(e->s_lno < tlno) { 707/* there is a pre-chunk part not blamed on parent */ 708 split[0].suspect =blame_origin_incref(e->suspect); 709 split[0].lno = e->lno; 710 split[0].s_lno = e->s_lno; 711 split[0].num_lines = tlno - e->s_lno; 712 split[1].lno = e->lno + tlno - e->s_lno; 713 split[1].s_lno = plno; 714} 715else{ 716 split[1].lno = e->lno; 717 split[1].s_lno = plno + (e->s_lno - tlno); 718} 719 720if(same < e->s_lno + e->num_lines) { 721/* there is a post-chunk part not blamed on parent */ 722 split[2].suspect =blame_origin_incref(e->suspect); 723 split[2].lno = e->lno + (same - e->s_lno); 724 split[2].s_lno = e->s_lno + (same - e->s_lno); 725 split[2].num_lines = e->s_lno + e->num_lines - same; 726 chunk_end_lno = split[2].lno; 727} 728else 729 chunk_end_lno = e->lno + e->num_lines; 730 split[1].num_lines = chunk_end_lno - split[1].lno; 731 732/* 733 * if it turns out there is nothing to blame the parent for, 734 * forget about the splitting. !split[1].suspect signals this. 735 */ 736if(split[1].num_lines <1) 737return; 738 split[1].suspect =blame_origin_incref(parent); 739} 740 741/* 742 * split_overlap() divided an existing blame e into up to three parts 743 * in split. Any assigned blame is moved to queue to 744 * reflect the split. 745 */ 746static voidsplit_blame(struct blame_entry ***blamed, 747struct blame_entry ***unblamed, 748struct blame_entry *split, 749struct blame_entry *e) 750{ 751if(split[0].suspect && split[2].suspect) { 752/* The first part (reuse storage for the existing entry e) */ 753dup_entry(unblamed, e, &split[0]); 754 755/* The last part -- me */ 756add_blame_entry(unblamed, &split[2]); 757 758/* ... and the middle part -- parent */ 759add_blame_entry(blamed, &split[1]); 760} 761else if(!split[0].suspect && !split[2].suspect) 762/* 763 * The parent covers the entire area; reuse storage for 764 * e and replace it with the parent. 765 */ 766dup_entry(blamed, e, &split[1]); 767else if(split[0].suspect) { 768/* me and then parent */ 769dup_entry(unblamed, e, &split[0]); 770add_blame_entry(blamed, &split[1]); 771} 772else{ 773/* parent and then me */ 774dup_entry(blamed, e, &split[1]); 775add_blame_entry(unblamed, &split[2]); 776} 777} 778 779/* 780 * After splitting the blame, the origins used by the 781 * on-stack blame_entry should lose one refcnt each. 782 */ 783static voiddecref_split(struct blame_entry *split) 784{ 785int i; 786 787for(i =0; i <3; i++) 788blame_origin_decref(split[i].suspect); 789} 790 791/* 792 * reverse_blame reverses the list given in head, appending tail. 793 * That allows us to build lists in reverse order, then reverse them 794 * afterwards. This can be faster than building the list in proper 795 * order right away. The reason is that building in proper order 796 * requires writing a link in the _previous_ element, while building 797 * in reverse order just requires placing the list head into the 798 * _current_ element. 799 */ 800 801static struct blame_entry *reverse_blame(struct blame_entry *head, 802struct blame_entry *tail) 803{ 804while(head) { 805struct blame_entry *next = head->next; 806 head->next = tail; 807 tail = head; 808 head = next; 809} 810return tail; 811} 812 813/* 814 * Process one hunk from the patch between the current suspect for 815 * blame_entry e and its parent. This first blames any unfinished 816 * entries before the chunk (which is where target and parent start 817 * differing) on the parent, and then splits blame entries at the 818 * start and at the end of the difference region. Since use of -M and 819 * -C options may lead to overlapping/duplicate source line number 820 * ranges, all we can rely on from sorting/merging is the order of the 821 * first suspect line number. 822 */ 823static voidblame_chunk(struct blame_entry ***dstq,struct blame_entry ***srcq, 824int tlno,int offset,int same, 825struct blame_origin *parent) 826{ 827struct blame_entry *e = **srcq; 828struct blame_entry *samep = NULL, *diffp = NULL; 829 830while(e && e->s_lno < tlno) { 831struct blame_entry *next = e->next; 832/* 833 * current record starts before differing portion. If 834 * it reaches into it, we need to split it up and 835 * examine the second part separately. 836 */ 837if(e->s_lno + e->num_lines > tlno) { 838/* Move second half to a new record */ 839int len = tlno - e->s_lno; 840struct blame_entry *n =xcalloc(1,sizeof(struct blame_entry)); 841 n->suspect = e->suspect; 842 n->lno = e->lno + len; 843 n->s_lno = e->s_lno + len; 844 n->num_lines = e->num_lines - len; 845 e->num_lines = len; 846 e->score =0; 847/* Push new record to diffp */ 848 n->next = diffp; 849 diffp = n; 850}else 851blame_origin_decref(e->suspect); 852/* Pass blame for everything before the differing 853 * chunk to the parent */ 854 e->suspect =blame_origin_incref(parent); 855 e->s_lno += offset; 856 e->next = samep; 857 samep = e; 858 e = next; 859} 860/* 861 * As we don't know how much of a common stretch after this 862 * diff will occur, the currently blamed parts are all that we 863 * can assign to the parent for now. 864 */ 865 866if(samep) { 867**dstq =reverse_blame(samep, **dstq); 868*dstq = &samep->next; 869} 870/* 871 * Prepend the split off portions: everything after e starts 872 * after the blameable portion. 873 */ 874 e =reverse_blame(diffp, e); 875 876/* 877 * Now retain records on the target while parts are different 878 * from the parent. 879 */ 880 samep = NULL; 881 diffp = NULL; 882while(e && e->s_lno < same) { 883struct blame_entry *next = e->next; 884 885/* 886 * If current record extends into sameness, need to split. 887 */ 888if(e->s_lno + e->num_lines > same) { 889/* 890 * Move second half to a new record to be 891 * processed by later chunks 892 */ 893int len = same - e->s_lno; 894struct blame_entry *n =xcalloc(1,sizeof(struct blame_entry)); 895 n->suspect =blame_origin_incref(e->suspect); 896 n->lno = e->lno + len; 897 n->s_lno = e->s_lno + len; 898 n->num_lines = e->num_lines - len; 899 e->num_lines = len; 900 e->score =0; 901/* Push new record to samep */ 902 n->next = samep; 903 samep = n; 904} 905 e->next = diffp; 906 diffp = e; 907 e = next; 908} 909**srcq =reverse_blame(diffp,reverse_blame(samep, e)); 910/* Move across elements that are in the unblamable portion */ 911if(diffp) 912*srcq = &diffp->next; 913} 914 915struct blame_chunk_cb_data { 916struct blame_origin *parent; 917long offset; 918struct blame_entry **dstq; 919struct blame_entry **srcq; 920}; 921 922/* diff chunks are from parent to target */ 923static intblame_chunk_cb(long start_a,long count_a, 924long start_b,long count_b,void*data) 925{ 926struct blame_chunk_cb_data *d = data; 927if(start_a - start_b != d->offset) 928die("internal error in blame::blame_chunk_cb"); 929blame_chunk(&d->dstq, &d->srcq, start_b, start_a - start_b, 930 start_b + count_b, d->parent); 931 d->offset = start_a + count_a - (start_b + count_b); 932return0; 933} 934 935/* 936 * We are looking at the origin 'target' and aiming to pass blame 937 * for the lines it is suspected to its parent. Run diff to find 938 * which lines came from parent and pass blame for them. 939 */ 940static voidpass_blame_to_parent(struct blame_scoreboard *sb, 941struct blame_origin *target, 942struct blame_origin *parent) 943{ 944 mmfile_t file_p, file_o; 945struct blame_chunk_cb_data d; 946struct blame_entry *newdest = NULL; 947 948if(!target->suspects) 949return;/* nothing remains for this target */ 950 951 d.parent = parent; 952 d.offset =0; 953 d.dstq = &newdest; d.srcq = &target->suspects; 954 955fill_origin_blob(&sb->revs->diffopt, parent, &file_p, &sb->num_read_blob); 956fill_origin_blob(&sb->revs->diffopt, target, &file_o, &sb->num_read_blob); 957 sb->num_get_patch++; 958 959if(diff_hunks(&file_p, &file_o, blame_chunk_cb, &d, sb->xdl_opts)) 960die("unable to generate diff (%s->%s)", 961oid_to_hex(&parent->commit->object.oid), 962oid_to_hex(&target->commit->object.oid)); 963/* The rest are the same as the parent */ 964blame_chunk(&d.dstq, &d.srcq, INT_MAX, d.offset, INT_MAX, parent); 965*d.dstq = NULL; 966queue_blames(sb, parent, newdest); 967 968return; 969} 970 971/* 972 * The lines in blame_entry after splitting blames many times can become 973 * very small and trivial, and at some point it becomes pointless to 974 * blame the parents. E.g. "\t\t}\n\t}\n\n" appears everywhere in any 975 * ordinary C program, and it is not worth to say it was copied from 976 * totally unrelated file in the parent. 977 * 978 * Compute how trivial the lines in the blame_entry are. 979 */ 980unsignedblame_entry_score(struct blame_scoreboard *sb,struct blame_entry *e) 981{ 982unsigned score; 983const char*cp, *ep; 984 985if(e->score) 986return e->score; 987 988 score =1; 989 cp =blame_nth_line(sb, e->lno); 990 ep =blame_nth_line(sb, e->lno + e->num_lines); 991while(cp < ep) { 992unsigned ch = *((unsigned char*)cp); 993if(isalnum(ch)) 994 score++; 995 cp++; 996} 997 e->score = score; 998return score; 999}10001001/*1002 * best_so_far[] and this[] are both a split of an existing blame_entry1003 * that passes blame to the parent. Maintain best_so_far the best split1004 * so far, by comparing this and best_so_far and copying this into1005 * bst_so_far as needed.1006 */1007static voidcopy_split_if_better(struct blame_scoreboard *sb,1008struct blame_entry *best_so_far,1009struct blame_entry *this)1010{1011int i;10121013if(!this[1].suspect)1014return;1015if(best_so_far[1].suspect) {1016if(blame_entry_score(sb, &this[1]) <blame_entry_score(sb, &best_so_far[1]))1017return;1018}10191020for(i =0; i <3; i++)1021blame_origin_incref(this[i].suspect);1022decref_split(best_so_far);1023memcpy(best_so_far,this,sizeof(struct blame_entry [3]));1024}10251026/*1027 * We are looking at a part of the final image represented by1028 * ent (tlno and same are offset by ent->s_lno).1029 * tlno is where we are looking at in the final image.1030 * up to (but not including) same match preimage.1031 * plno is where we are looking at in the preimage.1032 *1033 * <-------------- final image ---------------------->1034 * <------ent------>1035 * ^tlno ^same1036 * <---------preimage----->1037 * ^plno1038 *1039 * All line numbers are 0-based.1040 */1041static voidhandle_split(struct blame_scoreboard *sb,1042struct blame_entry *ent,1043int tlno,int plno,int same,1044struct blame_origin *parent,1045struct blame_entry *split)1046{1047if(ent->num_lines <= tlno)1048return;1049if(tlno < same) {1050struct blame_entry this[3];1051 tlno += ent->s_lno;1052 same += ent->s_lno;1053split_overlap(this, ent, tlno, plno, same, parent);1054copy_split_if_better(sb, split,this);1055decref_split(this);1056}1057}10581059struct handle_split_cb_data {1060struct blame_scoreboard *sb;1061struct blame_entry *ent;1062struct blame_origin *parent;1063struct blame_entry *split;1064long plno;1065long tlno;1066};10671068static inthandle_split_cb(long start_a,long count_a,1069long start_b,long count_b,void*data)1070{1071struct handle_split_cb_data *d = data;1072handle_split(d->sb, d->ent, d->tlno, d->plno, start_b, d->parent,1073 d->split);1074 d->plno = start_a + count_a;1075 d->tlno = start_b + count_b;1076return0;1077}10781079/*1080 * Find the lines from parent that are the same as ent so that1081 * we can pass blames to it. file_p has the blob contents for1082 * the parent.1083 */1084static voidfind_copy_in_blob(struct blame_scoreboard *sb,1085struct blame_entry *ent,1086struct blame_origin *parent,1087struct blame_entry *split,1088 mmfile_t *file_p)1089{1090const char*cp;1091 mmfile_t file_o;1092struct handle_split_cb_data d;10931094memset(&d,0,sizeof(d));1095 d.sb = sb; d.ent = ent; d.parent = parent; d.split = split;1096/*1097 * Prepare mmfile that contains only the lines in ent.1098 */1099 cp =blame_nth_line(sb, ent->lno);1100 file_o.ptr = (char*) cp;1101 file_o.size =blame_nth_line(sb, ent->lno + ent->num_lines) - cp;11021103/*1104 * file_o is a part of final image we are annotating.1105 * file_p partially may match that image.1106 */1107memset(split,0,sizeof(struct blame_entry [3]));1108if(diff_hunks(file_p, &file_o, handle_split_cb, &d, sb->xdl_opts))1109die("unable to generate diff (%s)",1110oid_to_hex(&parent->commit->object.oid));1111/* remainder, if any, all match the preimage */1112handle_split(sb, ent, d.tlno, d.plno, ent->num_lines, parent, split);1113}11141115/* Move all blame entries from list *source that have a score smaller1116 * than score_min to the front of list *small.1117 * Returns a pointer to the link pointing to the old head of the small list.1118 */11191120static struct blame_entry **filter_small(struct blame_scoreboard *sb,1121struct blame_entry **small,1122struct blame_entry **source,1123unsigned score_min)1124{1125struct blame_entry *p = *source;1126struct blame_entry *oldsmall = *small;1127while(p) {1128if(blame_entry_score(sb, p) <= score_min) {1129*small = p;1130 small = &p->next;1131 p = *small;1132}else{1133*source = p;1134 source = &p->next;1135 p = *source;1136}1137}1138*small = oldsmall;1139*source = NULL;1140return small;1141}11421143/*1144 * See if lines currently target is suspected for can be attributed to1145 * parent.1146 */1147static voidfind_move_in_parent(struct blame_scoreboard *sb,1148struct blame_entry ***blamed,1149struct blame_entry **toosmall,1150struct blame_origin *target,1151struct blame_origin *parent)1152{1153struct blame_entry *e, split[3];1154struct blame_entry *unblamed = target->suspects;1155struct blame_entry *leftover = NULL;1156 mmfile_t file_p;11571158if(!unblamed)1159return;/* nothing remains for this target */11601161fill_origin_blob(&sb->revs->diffopt, parent, &file_p, &sb->num_read_blob);1162if(!file_p.ptr)1163return;11641165/* At each iteration, unblamed has a NULL-terminated list of1166 * entries that have not yet been tested for blame. leftover1167 * contains the reversed list of entries that have been tested1168 * without being assignable to the parent.1169 */1170do{1171struct blame_entry **unblamedtail = &unblamed;1172struct blame_entry *next;1173for(e = unblamed; e; e = next) {1174 next = e->next;1175find_copy_in_blob(sb, e, parent, split, &file_p);1176if(split[1].suspect &&1177 sb->move_score <blame_entry_score(sb, &split[1])) {1178split_blame(blamed, &unblamedtail, split, e);1179}else{1180 e->next = leftover;1181 leftover = e;1182}1183decref_split(split);1184}1185*unblamedtail = NULL;1186 toosmall =filter_small(sb, toosmall, &unblamed, sb->move_score);1187}while(unblamed);1188 target->suspects =reverse_blame(leftover, NULL);1189}11901191struct blame_list {1192struct blame_entry *ent;1193struct blame_entry split[3];1194};11951196/*1197 * Count the number of entries the target is suspected for,1198 * and prepare a list of entry and the best split.1199 */1200static struct blame_list *setup_blame_list(struct blame_entry *unblamed,1201int*num_ents_p)1202{1203struct blame_entry *e;1204int num_ents, i;1205struct blame_list *blame_list = NULL;12061207for(e = unblamed, num_ents =0; e; e = e->next)1208 num_ents++;1209if(num_ents) {1210 blame_list =xcalloc(num_ents,sizeof(struct blame_list));1211for(e = unblamed, i =0; e; e = e->next)1212 blame_list[i++].ent = e;1213}1214*num_ents_p = num_ents;1215return blame_list;1216}12171218/*1219 * For lines target is suspected for, see if we can find code movement1220 * across file boundary from the parent commit. porigin is the path1221 * in the parent we already tried.1222 */1223static voidfind_copy_in_parent(struct blame_scoreboard *sb,1224struct blame_entry ***blamed,1225struct blame_entry **toosmall,1226struct blame_origin *target,1227struct commit *parent,1228struct blame_origin *porigin,1229int opt)1230{1231struct diff_options diff_opts;1232int i, j;1233struct blame_list *blame_list;1234int num_ents;1235struct blame_entry *unblamed = target->suspects;1236struct blame_entry *leftover = NULL;12371238if(!unblamed)1239return;/* nothing remains for this target */12401241diff_setup(&diff_opts);1242DIFF_OPT_SET(&diff_opts, RECURSIVE);1243 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;12441245diff_setup_done(&diff_opts);12461247/* Try "find copies harder" on new path if requested;1248 * we do not want to use diffcore_rename() actually to1249 * match things up; find_copies_harder is set only to1250 * force diff_tree_sha1() to feed all filepairs to diff_queue,1251 * and this code needs to be after diff_setup_done(), which1252 * usually makes find-copies-harder imply copy detection.1253 */1254if((opt & PICKAXE_BLAME_COPY_HARDEST)1255|| ((opt & PICKAXE_BLAME_COPY_HARDER)1256&& (!porigin ||strcmp(target->path, porigin->path))))1257DIFF_OPT_SET(&diff_opts, FIND_COPIES_HARDER);12581259if(is_null_oid(&target->commit->object.oid))1260do_diff_cache(&parent->tree->object.oid, &diff_opts);1261else1262diff_tree_sha1(parent->tree->object.oid.hash,1263 target->commit->tree->object.oid.hash,1264"", &diff_opts);12651266if(!DIFF_OPT_TST(&diff_opts, FIND_COPIES_HARDER))1267diffcore_std(&diff_opts);12681269do{1270struct blame_entry **unblamedtail = &unblamed;1271 blame_list =setup_blame_list(unblamed, &num_ents);12721273for(i =0; i < diff_queued_diff.nr; i++) {1274struct diff_filepair *p = diff_queued_diff.queue[i];1275struct blame_origin *norigin;1276 mmfile_t file_p;1277struct blame_entry this[3];12781279if(!DIFF_FILE_VALID(p->one))1280continue;/* does not exist in parent */1281if(S_ISGITLINK(p->one->mode))1282continue;/* ignore git links */1283if(porigin && !strcmp(p->one->path, porigin->path))1284/* find_move already dealt with this path */1285continue;12861287 norigin =get_origin(parent, p->one->path);1288oidcpy(&norigin->blob_oid, &p->one->oid);1289 norigin->mode = p->one->mode;1290fill_origin_blob(&sb->revs->diffopt, norigin, &file_p, &sb->num_read_blob);1291if(!file_p.ptr)1292continue;12931294for(j =0; j < num_ents; j++) {1295find_copy_in_blob(sb, blame_list[j].ent,1296 norigin,this, &file_p);1297copy_split_if_better(sb, blame_list[j].split,1298this);1299decref_split(this);1300}1301blame_origin_decref(norigin);1302}13031304for(j =0; j < num_ents; j++) {1305struct blame_entry *split = blame_list[j].split;1306if(split[1].suspect &&1307 sb->copy_score <blame_entry_score(sb, &split[1])) {1308split_blame(blamed, &unblamedtail, split,1309 blame_list[j].ent);1310}else{1311 blame_list[j].ent->next = leftover;1312 leftover = blame_list[j].ent;1313}1314decref_split(split);1315}1316free(blame_list);1317*unblamedtail = NULL;1318 toosmall =filter_small(sb, toosmall, &unblamed, sb->copy_score);1319}while(unblamed);1320 target->suspects =reverse_blame(leftover, NULL);1321diff_flush(&diff_opts);1322clear_pathspec(&diff_opts.pathspec);1323}13241325/*1326 * The blobs of origin and porigin exactly match, so everything1327 * origin is suspected for can be blamed on the parent.1328 */1329static voidpass_whole_blame(struct blame_scoreboard *sb,1330struct blame_origin *origin,struct blame_origin *porigin)1331{1332struct blame_entry *e, *suspects;13331334if(!porigin->file.ptr && origin->file.ptr) {1335/* Steal its file */1336 porigin->file = origin->file;1337 origin->file.ptr = NULL;1338}1339 suspects = origin->suspects;1340 origin->suspects = NULL;1341for(e = suspects; e; e = e->next) {1342blame_origin_incref(porigin);1343blame_origin_decref(e->suspect);1344 e->suspect = porigin;1345}1346queue_blames(sb, porigin, suspects);1347}13481349/*1350 * We pass blame from the current commit to its parents. We keep saying1351 * "parent" (and "porigin"), but what we mean is to find scapegoat to1352 * exonerate ourselves.1353 */1354static struct commit_list *first_scapegoat(struct rev_info *revs,struct commit *commit,1355int reverse)1356{1357if(!reverse) {1358if(revs->first_parent_only &&1359 commit->parents &&1360 commit->parents->next) {1361free_commit_list(commit->parents->next);1362 commit->parents->next = NULL;1363}1364return commit->parents;1365}1366returnlookup_decoration(&revs->children, &commit->object);1367}13681369static intnum_scapegoats(struct rev_info *revs,struct commit *commit,int reverse)1370{1371struct commit_list *l =first_scapegoat(revs, commit, reverse);1372returncommit_list_count(l);1373}13741375/* Distribute collected unsorted blames to the respected sorted lists1376 * in the various origins.1377 */1378static voiddistribute_blame(struct blame_scoreboard *sb,struct blame_entry *blamed)1379{1380 blamed =llist_mergesort(blamed, get_next_blame, set_next_blame,1381 compare_blame_suspect);1382while(blamed)1383{1384struct blame_origin *porigin = blamed->suspect;1385struct blame_entry *suspects = NULL;1386do{1387struct blame_entry *next = blamed->next;1388 blamed->next = suspects;1389 suspects = blamed;1390 blamed = next;1391}while(blamed && blamed->suspect == porigin);1392 suspects =reverse_blame(suspects, NULL);1393queue_blames(sb, porigin, suspects);1394}1395}13961397#define MAXSG 1613981399static voidpass_blame(struct blame_scoreboard *sb,struct blame_origin *origin,int opt)1400{1401struct rev_info *revs = sb->revs;1402int i, pass, num_sg;1403struct commit *commit = origin->commit;1404struct commit_list *sg;1405struct blame_origin *sg_buf[MAXSG];1406struct blame_origin *porigin, **sg_origin = sg_buf;1407struct blame_entry *toosmall = NULL;1408struct blame_entry *blames, **blametail = &blames;14091410 num_sg =num_scapegoats(revs, commit, sb->reverse);1411if(!num_sg)1412goto finish;1413else if(num_sg <ARRAY_SIZE(sg_buf))1414memset(sg_buf,0,sizeof(sg_buf));1415else1416 sg_origin =xcalloc(num_sg,sizeof(*sg_origin));14171418/*1419 * The first pass looks for unrenamed path to optimize for1420 * common cases, then we look for renames in the second pass.1421 */1422for(pass =0; pass <2- sb->no_whole_file_rename; pass++) {1423struct blame_origin *(*find)(struct commit *,struct blame_origin *);1424 find = pass ? find_rename : find_origin;14251426for(i =0, sg =first_scapegoat(revs, commit, sb->reverse);1427 i < num_sg && sg;1428 sg = sg->next, i++) {1429struct commit *p = sg->item;1430int j, same;14311432if(sg_origin[i])1433continue;1434if(parse_commit(p))1435continue;1436 porigin =find(p, origin);1437if(!porigin)1438continue;1439if(!oidcmp(&porigin->blob_oid, &origin->blob_oid)) {1440pass_whole_blame(sb, origin, porigin);1441blame_origin_decref(porigin);1442goto finish;1443}1444for(j = same =0; j < i; j++)1445if(sg_origin[j] &&1446!oidcmp(&sg_origin[j]->blob_oid, &porigin->blob_oid)) {1447 same =1;1448break;1449}1450if(!same)1451 sg_origin[i] = porigin;1452else1453blame_origin_decref(porigin);1454}1455}14561457 sb->num_commits++;1458for(i =0, sg =first_scapegoat(revs, commit, sb->reverse);1459 i < num_sg && sg;1460 sg = sg->next, i++) {1461struct blame_origin *porigin = sg_origin[i];1462if(!porigin)1463continue;1464if(!origin->previous) {1465blame_origin_incref(porigin);1466 origin->previous = porigin;1467}1468pass_blame_to_parent(sb, origin, porigin);1469if(!origin->suspects)1470goto finish;1471}14721473/*1474 * Optionally find moves in parents' files.1475 */1476if(opt & PICKAXE_BLAME_MOVE) {1477filter_small(sb, &toosmall, &origin->suspects, sb->move_score);1478if(origin->suspects) {1479for(i =0, sg =first_scapegoat(revs, commit, sb->reverse);1480 i < num_sg && sg;1481 sg = sg->next, i++) {1482struct blame_origin *porigin = sg_origin[i];1483if(!porigin)1484continue;1485find_move_in_parent(sb, &blametail, &toosmall, origin, porigin);1486if(!origin->suspects)1487break;1488}1489}1490}14911492/*1493 * Optionally find copies from parents' files.1494 */1495if(opt & PICKAXE_BLAME_COPY) {1496if(sb->copy_score > sb->move_score)1497filter_small(sb, &toosmall, &origin->suspects, sb->copy_score);1498else if(sb->copy_score < sb->move_score) {1499 origin->suspects =blame_merge(origin->suspects, toosmall);1500 toosmall = NULL;1501filter_small(sb, &toosmall, &origin->suspects, sb->copy_score);1502}1503if(!origin->suspects)1504goto finish;15051506for(i =0, sg =first_scapegoat(revs, commit, sb->reverse);1507 i < num_sg && sg;1508 sg = sg->next, i++) {1509struct blame_origin *porigin = sg_origin[i];1510find_copy_in_parent(sb, &blametail, &toosmall,1511 origin, sg->item, porigin, opt);1512if(!origin->suspects)1513goto finish;1514}1515}15161517finish:1518*blametail = NULL;1519distribute_blame(sb, blames);1520/*1521 * prepend toosmall to origin->suspects1522 *1523 * There is no point in sorting: this ends up on a big1524 * unsorted list in the caller anyway.1525 */1526if(toosmall) {1527struct blame_entry **tail = &toosmall;1528while(*tail)1529 tail = &(*tail)->next;1530*tail = origin->suspects;1531 origin->suspects = toosmall;1532}1533for(i =0; i < num_sg; i++) {1534if(sg_origin[i]) {1535drop_origin_blob(sg_origin[i]);1536blame_origin_decref(sg_origin[i]);1537}1538}1539drop_origin_blob(origin);1540if(sg_buf != sg_origin)1541free(sg_origin);1542}15431544/*1545 * The main loop -- while we have blobs with lines whose true origin1546 * is still unknown, pick one blob, and allow its lines to pass blames1547 * to its parents. */1548voidassign_blame(struct blame_scoreboard *sb,int opt)1549{1550struct rev_info *revs = sb->revs;1551struct commit *commit =prio_queue_get(&sb->commits);15521553while(commit) {1554struct blame_entry *ent;1555struct blame_origin *suspect = commit->util;15561557/* find one suspect to break down */1558while(suspect && !suspect->suspects)1559 suspect = suspect->next;15601561if(!suspect) {1562 commit =prio_queue_get(&sb->commits);1563continue;1564}15651566assert(commit == suspect->commit);15671568/*1569 * We will use this suspect later in the loop,1570 * so hold onto it in the meantime.1571 */1572blame_origin_incref(suspect);1573parse_commit(commit);1574if(sb->reverse ||1575(!(commit->object.flags & UNINTERESTING) &&1576!(revs->max_age != -1&& commit->date < revs->max_age)))1577pass_blame(sb, suspect, opt);1578else{1579 commit->object.flags |= UNINTERESTING;1580if(commit->object.parsed)1581mark_parents_uninteresting(commit);1582}1583/* treat root commit as boundary */1584if(!commit->parents && !sb->show_root)1585 commit->object.flags |= UNINTERESTING;15861587/* Take responsibility for the remaining entries */1588 ent = suspect->suspects;1589if(ent) {1590 suspect->guilty =1;1591for(;;) {1592struct blame_entry *next = ent->next;1593if(sb->found_guilty_entry)1594 sb->found_guilty_entry(ent, sb->found_guilty_entry_data);1595if(next) {1596 ent = next;1597continue;1598}1599 ent->next = sb->ent;1600 sb->ent = suspect->suspects;1601 suspect->suspects = NULL;1602break;1603}1604}1605blame_origin_decref(suspect);16061607if(sb->debug)/* sanity */1608sanity_check_refcnt(sb);1609}1610}16111612static const char*get_next_line(const char*start,const char*end)1613{1614const char*nl =memchr(start,'\n', end - start);1615return nl ? nl +1: end;1616}16171618/*1619 * To allow quick access to the contents of nth line in the1620 * final image, prepare an index in the scoreboard.1621 */1622static intprepare_lines(struct blame_scoreboard *sb)1623{1624const char*buf = sb->final_buf;1625unsigned long len = sb->final_buf_size;1626const char*end = buf + len;1627const char*p;1628int*lineno;1629int num =0;16301631for(p = buf; p < end; p =get_next_line(p, end))1632 num++;16331634ALLOC_ARRAY(sb->lineno, num +1);1635 lineno = sb->lineno;16361637for(p = buf; p < end; p =get_next_line(p, end))1638*lineno++ = p - buf;16391640*lineno = len;16411642 sb->num_lines = num;1643return sb->num_lines;1644}16451646static struct commit *find_single_final(struct rev_info *revs,1647const char**name_p)1648{1649int i;1650struct commit *found = NULL;1651const char*name = NULL;16521653for(i =0; i < revs->pending.nr; i++) {1654struct object *obj = revs->pending.objects[i].item;1655if(obj->flags & UNINTERESTING)1656continue;1657 obj =deref_tag(obj, NULL,0);1658if(obj->type != OBJ_COMMIT)1659die("Non commit%s?", revs->pending.objects[i].name);1660if(found)1661die("More than one commit to dig from%sand%s?",1662 revs->pending.objects[i].name, name);1663 found = (struct commit *)obj;1664 name = revs->pending.objects[i].name;1665}1666if(name_p)1667*name_p = name;1668return found;1669}16701671static struct commit *dwim_reverse_initial(struct rev_info *revs,1672const char**name_p)1673{1674/*1675 * DWIM "git blame --reverse ONE -- PATH" as1676 * "git blame --reverse ONE..HEAD -- PATH" but only do so1677 * when it makes sense.1678 */1679struct object *obj;1680struct commit *head_commit;1681struct object_id head_oid;16821683if(revs->pending.nr !=1)1684return NULL;16851686/* Is that sole rev a committish? */1687 obj = revs->pending.objects[0].item;1688 obj =deref_tag(obj, NULL,0);1689if(obj->type != OBJ_COMMIT)1690return NULL;16911692/* Do we have HEAD? */1693if(!resolve_ref_unsafe("HEAD", RESOLVE_REF_READING, head_oid.hash, NULL))1694return NULL;1695 head_commit =lookup_commit_reference_gently(&head_oid,1);1696if(!head_commit)1697return NULL;16981699/* Turn "ONE" into "ONE..HEAD" then */1700 obj->flags |= UNINTERESTING;1701add_pending_object(revs, &head_commit->object,"HEAD");17021703if(name_p)1704*name_p = revs->pending.objects[0].name;1705return(struct commit *)obj;1706}17071708static struct commit *find_single_initial(struct rev_info *revs,1709const char**name_p)1710{1711int i;1712struct commit *found = NULL;1713const char*name = NULL;17141715/*1716 * There must be one and only one negative commit, and it must be1717 * the boundary.1718 */1719for(i =0; i < revs->pending.nr; i++) {1720struct object *obj = revs->pending.objects[i].item;1721if(!(obj->flags & UNINTERESTING))1722continue;1723 obj =deref_tag(obj, NULL,0);1724if(obj->type != OBJ_COMMIT)1725die("Non commit%s?", revs->pending.objects[i].name);1726if(found)1727die("More than one commit to dig up from,%sand%s?",1728 revs->pending.objects[i].name, name);1729 found = (struct commit *) obj;1730 name = revs->pending.objects[i].name;1731}17321733if(!name)1734 found =dwim_reverse_initial(revs, &name);1735if(!name)1736die("No commit to dig up from?");17371738if(name_p)1739*name_p = name;1740return found;1741}17421743voidinit_scoreboard(struct blame_scoreboard *sb)1744{1745memset(sb,0,sizeof(struct blame_scoreboard));1746 sb->move_score = BLAME_DEFAULT_MOVE_SCORE;1747 sb->copy_score = BLAME_DEFAULT_COPY_SCORE;1748}17491750voidsetup_scoreboard(struct blame_scoreboard *sb,const char*path,struct blame_origin **orig)1751{1752const char*final_commit_name = NULL;1753struct blame_origin *o;1754struct commit *final_commit = NULL;1755enum object_type type;17561757if(sb->reverse && sb->contents_from)1758die(_("--contents and --reverse do not blend well."));17591760if(!sb->reverse) {1761 sb->final =find_single_final(sb->revs, &final_commit_name);1762 sb->commits.compare = compare_commits_by_commit_date;1763}else{1764 sb->final =find_single_initial(sb->revs, &final_commit_name);1765 sb->commits.compare = compare_commits_by_reverse_commit_date;1766}17671768if(sb->final && sb->contents_from)1769die(_("cannot use --contents with final commit object name"));17701771if(sb->reverse && sb->revs->first_parent_only)1772 sb->revs->children.name = NULL;17731774if(!sb->final) {1775/*1776 * "--not A B -- path" without anything positive;1777 * do not default to HEAD, but use the working tree1778 * or "--contents".1779 */1780setup_work_tree();1781 sb->final =fake_working_tree_commit(&sb->revs->diffopt,1782 path, sb->contents_from);1783add_pending_object(sb->revs, &(sb->final->object),":");1784}17851786if(sb->reverse && sb->revs->first_parent_only) {1787 final_commit =find_single_final(sb->revs, NULL);1788if(!final_commit)1789die(_("--reverse and --first-parent together require specified latest commit"));1790}17911792/*1793 * If we have bottom, this will mark the ancestors of the1794 * bottom commits we would reach while traversing as1795 * uninteresting.1796 */1797if(prepare_revision_walk(sb->revs))1798die(_("revision walk setup failed"));17991800if(sb->reverse && sb->revs->first_parent_only) {1801struct commit *c = final_commit;18021803 sb->revs->children.name ="children";1804while(c->parents &&1805oidcmp(&c->object.oid, &sb->final->object.oid)) {1806struct commit_list *l =xcalloc(1,sizeof(*l));18071808 l->item = c;1809if(add_decoration(&sb->revs->children,1810&c->parents->item->object, l))1811die("BUG: not unique item in first-parent chain");1812 c = c->parents->item;1813}18141815if(oidcmp(&c->object.oid, &sb->final->object.oid))1816die(_("--reverse --first-parent together require range along first-parent chain"));1817}18181819if(is_null_oid(&sb->final->object.oid)) {1820 o = sb->final->util;1821 sb->final_buf =xmemdupz(o->file.ptr, o->file.size);1822 sb->final_buf_size = o->file.size;1823}1824else{1825 o =get_origin(sb->final, path);1826if(fill_blob_sha1_and_mode(o))1827die(_("no such path%sin%s"), path, final_commit_name);18281829if(DIFF_OPT_TST(&sb->revs->diffopt, ALLOW_TEXTCONV) &&1830textconv_object(path, o->mode, &o->blob_oid,1, (char**) &sb->final_buf,1831&sb->final_buf_size))1832;1833else1834 sb->final_buf =read_sha1_file(o->blob_oid.hash, &type,1835&sb->final_buf_size);18361837if(!sb->final_buf)1838die(_("cannot read blob%sfor path%s"),1839oid_to_hex(&o->blob_oid),1840 path);1841}1842 sb->num_read_blob++;1843prepare_lines(sb);18441845if(orig)1846*orig = o;1847}1848184918501851struct blame_entry *blame_entry_prepend(struct blame_entry *head,1852long start,long end,1853struct blame_origin *o)1854{1855struct blame_entry *new_head =xcalloc(1,sizeof(struct blame_entry));1856 new_head->lno = start;1857 new_head->num_lines = end - start;1858 new_head->suspect = o;1859 new_head->s_lno = start;1860 new_head->next = head;1861blame_origin_incref(o);1862return new_head;1863}