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