1/* 2 * Recursive Merge algorithm stolen from git-merge-recursive.py by 3 * Fredrik Kuivinen. 4 * The thieves were Alex Riesen and Johannes Schindelin, in June/July 2006 5 */ 6#include"cache.h" 7#include"config.h" 8#include"advice.h" 9#include"lockfile.h" 10#include"cache-tree.h" 11#include"commit.h" 12#include"blob.h" 13#include"builtin.h" 14#include"tree-walk.h" 15#include"diff.h" 16#include"diffcore.h" 17#include"tag.h" 18#include"alloc.h" 19#include"unpack-trees.h" 20#include"string-list.h" 21#include"xdiff-interface.h" 22#include"ll-merge.h" 23#include"attr.h" 24#include"merge-recursive.h" 25#include"dir.h" 26#include"submodule.h" 27#include"revision.h" 28 29struct path_hashmap_entry { 30struct hashmap_entry e; 31char path[FLEX_ARRAY]; 32}; 33 34static intpath_hashmap_cmp(const void*cmp_data, 35const void*entry, 36const void*entry_or_key, 37const void*keydata) 38{ 39const struct path_hashmap_entry *a = entry; 40const struct path_hashmap_entry *b = entry_or_key; 41const char*key = keydata; 42 43if(ignore_case) 44returnstrcasecmp(a->path, key ? key : b->path); 45else 46returnstrcmp(a->path, key ? key : b->path); 47} 48 49static unsigned intpath_hash(const char*path) 50{ 51return ignore_case ?strihash(path) :strhash(path); 52} 53 54static struct dir_rename_entry *dir_rename_find_entry(struct hashmap *hashmap, 55char*dir) 56{ 57struct dir_rename_entry key; 58 59if(dir == NULL) 60return NULL; 61hashmap_entry_init(&key,strhash(dir)); 62 key.dir = dir; 63returnhashmap_get(hashmap, &key, NULL); 64} 65 66static intdir_rename_cmp(const void*unused_cmp_data, 67const void*entry, 68const void*entry_or_key, 69const void*unused_keydata) 70{ 71const struct dir_rename_entry *e1 = entry; 72const struct dir_rename_entry *e2 = entry_or_key; 73 74returnstrcmp(e1->dir, e2->dir); 75} 76 77static voiddir_rename_init(struct hashmap *map) 78{ 79hashmap_init(map, dir_rename_cmp, NULL,0); 80} 81 82static voiddir_rename_entry_init(struct dir_rename_entry *entry, 83char*directory) 84{ 85hashmap_entry_init(entry,strhash(directory)); 86 entry->dir = directory; 87 entry->non_unique_new_dir =0; 88strbuf_init(&entry->new_dir,0); 89string_list_init(&entry->possible_new_dirs,0); 90} 91 92static struct collision_entry *collision_find_entry(struct hashmap *hashmap, 93char*target_file) 94{ 95struct collision_entry key; 96 97hashmap_entry_init(&key,strhash(target_file)); 98 key.target_file = target_file; 99returnhashmap_get(hashmap, &key, NULL); 100} 101 102static intcollision_cmp(void*unused_cmp_data, 103const struct collision_entry *e1, 104const struct collision_entry *e2, 105const void*unused_keydata) 106{ 107returnstrcmp(e1->target_file, e2->target_file); 108} 109 110static voidcollision_init(struct hashmap *map) 111{ 112hashmap_init(map, (hashmap_cmp_fn) collision_cmp, NULL,0); 113} 114 115static voidflush_output(struct merge_options *o) 116{ 117if(o->buffer_output <2&& o->obuf.len) { 118fputs(o->obuf.buf, stdout); 119strbuf_reset(&o->obuf); 120} 121} 122 123static interr(struct merge_options *o,const char*err, ...) 124{ 125va_list params; 126 127if(o->buffer_output <2) 128flush_output(o); 129else{ 130strbuf_complete(&o->obuf,'\n'); 131strbuf_addstr(&o->obuf,"error: "); 132} 133va_start(params, err); 134strbuf_vaddf(&o->obuf, err, params); 135va_end(params); 136if(o->buffer_output >1) 137strbuf_addch(&o->obuf,'\n'); 138else{ 139error("%s", o->obuf.buf); 140strbuf_reset(&o->obuf); 141} 142 143return-1; 144} 145 146static struct tree *shift_tree_object(struct tree *one,struct tree *two, 147const char*subtree_shift) 148{ 149struct object_id shifted; 150 151if(!*subtree_shift) { 152shift_tree(&one->object.oid, &two->object.oid, &shifted,0); 153}else{ 154shift_tree_by(&one->object.oid, &two->object.oid, &shifted, 155 subtree_shift); 156} 157if(!oidcmp(&two->object.oid, &shifted)) 158return two; 159returnlookup_tree(&shifted); 160} 161 162static struct commit *make_virtual_commit(struct tree *tree,const char*comment) 163{ 164struct commit *commit =alloc_commit_node(the_repository); 165 166set_merge_remote_desc(commit, comment, (struct object *)commit); 167 commit->maybe_tree = tree; 168 commit->object.parsed =1; 169return commit; 170} 171 172/* 173 * Since we use get_tree_entry(), which does not put the read object into 174 * the object pool, we cannot rely on a == b. 175 */ 176static intoid_eq(const struct object_id *a,const struct object_id *b) 177{ 178if(!a && !b) 179return2; 180return a && b &&oidcmp(a, b) ==0; 181} 182 183enum rename_type { 184 RENAME_NORMAL =0, 185 RENAME_VIA_DIR, 186 RENAME_DELETE, 187 RENAME_ONE_FILE_TO_ONE, 188 RENAME_ONE_FILE_TO_TWO, 189 RENAME_TWO_FILES_TO_ONE 190}; 191 192struct rename_conflict_info { 193enum rename_type rename_type; 194struct diff_filepair *pair1; 195struct diff_filepair *pair2; 196const char*branch1; 197const char*branch2; 198struct stage_data *dst_entry1; 199struct stage_data *dst_entry2; 200struct diff_filespec ren1_other; 201struct diff_filespec ren2_other; 202}; 203 204/* 205 * Since we want to write the index eventually, we cannot reuse the index 206 * for these (temporary) data. 207 */ 208struct stage_data { 209struct{ 210unsigned mode; 211struct object_id oid; 212} stages[4]; 213struct rename_conflict_info *rename_conflict_info; 214unsigned processed:1; 215}; 216 217staticinlinevoidsetup_rename_conflict_info(enum rename_type rename_type, 218struct diff_filepair *pair1, 219struct diff_filepair *pair2, 220const char*branch1, 221const char*branch2, 222struct stage_data *dst_entry1, 223struct stage_data *dst_entry2, 224struct merge_options *o, 225struct stage_data *src_entry1, 226struct stage_data *src_entry2) 227{ 228struct rename_conflict_info *ci =xcalloc(1,sizeof(struct rename_conflict_info)); 229 ci->rename_type = rename_type; 230 ci->pair1 = pair1; 231 ci->branch1 = branch1; 232 ci->branch2 = branch2; 233 234 ci->dst_entry1 = dst_entry1; 235 dst_entry1->rename_conflict_info = ci; 236 dst_entry1->processed =0; 237 238assert(!pair2 == !dst_entry2); 239if(dst_entry2) { 240 ci->dst_entry2 = dst_entry2; 241 ci->pair2 = pair2; 242 dst_entry2->rename_conflict_info = ci; 243} 244 245if(rename_type == RENAME_TWO_FILES_TO_ONE) { 246/* 247 * For each rename, there could have been 248 * modifications on the side of history where that 249 * file was not renamed. 250 */ 251int ostage1 = o->branch1 == branch1 ?3:2; 252int ostage2 = ostage1 ^1; 253 254 ci->ren1_other.path = pair1->one->path; 255oidcpy(&ci->ren1_other.oid, &src_entry1->stages[ostage1].oid); 256 ci->ren1_other.mode = src_entry1->stages[ostage1].mode; 257 258 ci->ren2_other.path = pair2->one->path; 259oidcpy(&ci->ren2_other.oid, &src_entry2->stages[ostage2].oid); 260 ci->ren2_other.mode = src_entry2->stages[ostage2].mode; 261} 262} 263 264static intshow(struct merge_options *o,int v) 265{ 266return(!o->call_depth && o->verbosity >= v) || o->verbosity >=5; 267} 268 269__attribute__((format(printf,3,4))) 270static voidoutput(struct merge_options *o,int v,const char*fmt, ...) 271{ 272va_list ap; 273 274if(!show(o, v)) 275return; 276 277strbuf_addchars(&o->obuf,' ', o->call_depth *2); 278 279va_start(ap, fmt); 280strbuf_vaddf(&o->obuf, fmt, ap); 281va_end(ap); 282 283strbuf_addch(&o->obuf,'\n'); 284if(!o->buffer_output) 285flush_output(o); 286} 287 288static voidoutput_commit_title(struct merge_options *o,struct commit *commit) 289{ 290struct merge_remote_desc *desc; 291 292strbuf_addchars(&o->obuf,' ', o->call_depth *2); 293 desc =merge_remote_util(commit); 294if(desc) 295strbuf_addf(&o->obuf,"virtual%s\n", desc->name); 296else{ 297strbuf_add_unique_abbrev(&o->obuf, &commit->object.oid, 298 DEFAULT_ABBREV); 299strbuf_addch(&o->obuf,' '); 300if(parse_commit(commit) !=0) 301strbuf_addstr(&o->obuf,_("(bad commit)\n")); 302else{ 303const char*title; 304const char*msg =get_commit_buffer(commit, NULL); 305int len =find_commit_subject(msg, &title); 306if(len) 307strbuf_addf(&o->obuf,"%.*s\n", len, title); 308unuse_commit_buffer(commit, msg); 309} 310} 311flush_output(o); 312} 313 314static intadd_cacheinfo(struct merge_options *o, 315unsigned int mode,const struct object_id *oid, 316const char*path,int stage,int refresh,int options) 317{ 318struct cache_entry *ce; 319int ret; 320 321 ce =make_cache_entry(mode, oid ? oid->hash : null_sha1, path, stage,0); 322if(!ce) 323returnerr(o,_("add_cacheinfo failed for path '%s'; merge aborting."), path); 324 325 ret =add_cache_entry(ce, options); 326if(refresh) { 327struct cache_entry *nce; 328 329 nce =refresh_cache_entry(ce, CE_MATCH_REFRESH | CE_MATCH_IGNORE_MISSING); 330if(!nce) 331returnerr(o,_("add_cacheinfo failed to refresh for path '%s'; merge aborting."), path); 332if(nce != ce) 333 ret =add_cache_entry(nce, options); 334} 335return ret; 336} 337 338static voidinit_tree_desc_from_tree(struct tree_desc *desc,struct tree *tree) 339{ 340parse_tree(tree); 341init_tree_desc(desc, tree->buffer, tree->size); 342} 343 344static intunpack_trees_start(struct merge_options *o, 345struct tree *common, 346struct tree *head, 347struct tree *merge) 348{ 349int rc; 350struct tree_desc t[3]; 351struct index_state tmp_index = { NULL }; 352 353memset(&o->unpack_opts,0,sizeof(o->unpack_opts)); 354if(o->call_depth) 355 o->unpack_opts.index_only =1; 356else 357 o->unpack_opts.update =1; 358 o->unpack_opts.merge =1; 359 o->unpack_opts.head_idx =2; 360 o->unpack_opts.fn = threeway_merge; 361 o->unpack_opts.src_index = &the_index; 362 o->unpack_opts.dst_index = &tmp_index; 363 o->unpack_opts.aggressive = !merge_detect_rename(o); 364setup_unpack_trees_porcelain(&o->unpack_opts,"merge"); 365 366init_tree_desc_from_tree(t+0, common); 367init_tree_desc_from_tree(t+1, head); 368init_tree_desc_from_tree(t+2, merge); 369 370 rc =unpack_trees(3, t, &o->unpack_opts); 371cache_tree_free(&active_cache_tree); 372 373/* 374 * Update the_index to match the new results, AFTER saving a copy 375 * in o->orig_index. Update src_index to point to the saved copy. 376 * (verify_uptodate() checks src_index, and the original index is 377 * the one that had the necessary modification timestamps.) 378 */ 379 o->orig_index = the_index; 380 the_index = tmp_index; 381 o->unpack_opts.src_index = &o->orig_index; 382 383return rc; 384} 385 386static voidunpack_trees_finish(struct merge_options *o) 387{ 388discard_index(&o->orig_index); 389clear_unpack_trees_porcelain(&o->unpack_opts); 390} 391 392struct tree *write_tree_from_memory(struct merge_options *o) 393{ 394struct tree *result = NULL; 395 396if(unmerged_cache()) { 397int i; 398fprintf(stderr,"BUG: There are unmerged index entries:\n"); 399for(i =0; i < active_nr; i++) { 400const struct cache_entry *ce = active_cache[i]; 401if(ce_stage(ce)) 402fprintf(stderr,"BUG:%d%.*s\n",ce_stage(ce), 403(int)ce_namelen(ce), ce->name); 404} 405BUG("unmerged index entries in merge-recursive.c"); 406} 407 408if(!active_cache_tree) 409 active_cache_tree =cache_tree(); 410 411if(!cache_tree_fully_valid(active_cache_tree) && 412cache_tree_update(&the_index,0) <0) { 413err(o,_("error building trees")); 414return NULL; 415} 416 417 result =lookup_tree(&active_cache_tree->oid); 418 419return result; 420} 421 422static intsave_files_dirs(const struct object_id *oid, 423struct strbuf *base,const char*path, 424unsigned int mode,int stage,void*context) 425{ 426struct path_hashmap_entry *entry; 427int baselen = base->len; 428struct merge_options *o = context; 429 430strbuf_addstr(base, path); 431 432FLEX_ALLOC_MEM(entry, path, base->buf, base->len); 433hashmap_entry_init(entry,path_hash(entry->path)); 434hashmap_add(&o->current_file_dir_set, entry); 435 436strbuf_setlen(base, baselen); 437return(S_ISDIR(mode) ? READ_TREE_RECURSIVE :0); 438} 439 440static voidget_files_dirs(struct merge_options *o,struct tree *tree) 441{ 442struct pathspec match_all; 443memset(&match_all,0,sizeof(match_all)); 444read_tree_recursive(tree,"",0,0, &match_all, save_files_dirs, o); 445} 446 447static intget_tree_entry_if_blob(const struct object_id *tree, 448const char*path, 449struct object_id *hashy, 450unsigned int*mode_o) 451{ 452int ret; 453 454 ret =get_tree_entry(tree, path, hashy, mode_o); 455if(S_ISDIR(*mode_o)) { 456oidcpy(hashy, &null_oid); 457*mode_o =0; 458} 459return ret; 460} 461 462/* 463 * Returns an index_entry instance which doesn't have to correspond to 464 * a real cache entry in Git's index. 465 */ 466static struct stage_data *insert_stage_data(const char*path, 467struct tree *o,struct tree *a,struct tree *b, 468struct string_list *entries) 469{ 470struct string_list_item *item; 471struct stage_data *e =xcalloc(1,sizeof(struct stage_data)); 472get_tree_entry_if_blob(&o->object.oid, path, 473&e->stages[1].oid, &e->stages[1].mode); 474get_tree_entry_if_blob(&a->object.oid, path, 475&e->stages[2].oid, &e->stages[2].mode); 476get_tree_entry_if_blob(&b->object.oid, path, 477&e->stages[3].oid, &e->stages[3].mode); 478 item =string_list_insert(entries, path); 479 item->util = e; 480return e; 481} 482 483/* 484 * Create a dictionary mapping file names to stage_data objects. The 485 * dictionary contains one entry for every path with a non-zero stage entry. 486 */ 487static struct string_list *get_unmerged(void) 488{ 489struct string_list *unmerged =xcalloc(1,sizeof(struct string_list)); 490int i; 491 492 unmerged->strdup_strings =1; 493 494for(i =0; i < active_nr; i++) { 495struct string_list_item *item; 496struct stage_data *e; 497const struct cache_entry *ce = active_cache[i]; 498if(!ce_stage(ce)) 499continue; 500 501 item =string_list_lookup(unmerged, ce->name); 502if(!item) { 503 item =string_list_insert(unmerged, ce->name); 504 item->util =xcalloc(1,sizeof(struct stage_data)); 505} 506 e = item->util; 507 e->stages[ce_stage(ce)].mode = ce->ce_mode; 508oidcpy(&e->stages[ce_stage(ce)].oid, &ce->oid); 509} 510 511return unmerged; 512} 513 514static intstring_list_df_name_compare(const char*one,const char*two) 515{ 516int onelen =strlen(one); 517int twolen =strlen(two); 518/* 519 * Here we only care that entries for D/F conflicts are 520 * adjacent, in particular with the file of the D/F conflict 521 * appearing before files below the corresponding directory. 522 * The order of the rest of the list is irrelevant for us. 523 * 524 * To achieve this, we sort with df_name_compare and provide 525 * the mode S_IFDIR so that D/F conflicts will sort correctly. 526 * We use the mode S_IFDIR for everything else for simplicity, 527 * since in other cases any changes in their order due to 528 * sorting cause no problems for us. 529 */ 530int cmp =df_name_compare(one, onelen, S_IFDIR, 531 two, twolen, S_IFDIR); 532/* 533 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure 534 * that 'foo' comes before 'foo/bar'. 535 */ 536if(cmp) 537return cmp; 538return onelen - twolen; 539} 540 541static voidrecord_df_conflict_files(struct merge_options *o, 542struct string_list *entries) 543{ 544/* If there is a D/F conflict and the file for such a conflict 545 * currently exists in the working tree, we want to allow it to be 546 * removed to make room for the corresponding directory if needed. 547 * The files underneath the directories of such D/F conflicts will 548 * be processed before the corresponding file involved in the D/F 549 * conflict. If the D/F directory ends up being removed by the 550 * merge, then we won't have to touch the D/F file. If the D/F 551 * directory needs to be written to the working copy, then the D/F 552 * file will simply be removed (in make_room_for_path()) to make 553 * room for the necessary paths. Note that if both the directory 554 * and the file need to be present, then the D/F file will be 555 * reinstated with a new unique name at the time it is processed. 556 */ 557struct string_list df_sorted_entries = STRING_LIST_INIT_NODUP; 558const char*last_file = NULL; 559int last_len =0; 560int i; 561 562/* 563 * If we're merging merge-bases, we don't want to bother with 564 * any working directory changes. 565 */ 566if(o->call_depth) 567return; 568 569/* Ensure D/F conflicts are adjacent in the entries list. */ 570for(i =0; i < entries->nr; i++) { 571struct string_list_item *next = &entries->items[i]; 572string_list_append(&df_sorted_entries, next->string)->util = 573 next->util; 574} 575 df_sorted_entries.cmp = string_list_df_name_compare; 576string_list_sort(&df_sorted_entries); 577 578string_list_clear(&o->df_conflict_file_set,1); 579for(i =0; i < df_sorted_entries.nr; i++) { 580const char*path = df_sorted_entries.items[i].string; 581int len =strlen(path); 582struct stage_data *e = df_sorted_entries.items[i].util; 583 584/* 585 * Check if last_file & path correspond to a D/F conflict; 586 * i.e. whether path is last_file+'/'+<something>. 587 * If so, record that it's okay to remove last_file to make 588 * room for path and friends if needed. 589 */ 590if(last_file && 591 len > last_len && 592memcmp(path, last_file, last_len) ==0&& 593 path[last_len] =='/') { 594string_list_insert(&o->df_conflict_file_set, last_file); 595} 596 597/* 598 * Determine whether path could exist as a file in the 599 * working directory as a possible D/F conflict. This 600 * will only occur when it exists in stage 2 as a 601 * file. 602 */ 603if(S_ISREG(e->stages[2].mode) ||S_ISLNK(e->stages[2].mode)) { 604 last_file = path; 605 last_len = len; 606}else{ 607 last_file = NULL; 608} 609} 610string_list_clear(&df_sorted_entries,0); 611} 612 613struct rename { 614struct diff_filepair *pair; 615/* 616 * Purpose of src_entry and dst_entry: 617 * 618 * If 'before' is renamed to 'after' then src_entry will contain 619 * the versions of 'before' from the merge_base, HEAD, and MERGE in 620 * stages 1, 2, and 3; dst_entry will contain the respective 621 * versions of 'after' in corresponding locations. Thus, we have a 622 * total of six modes and oids, though some will be null. (Stage 0 623 * is ignored; we're interested in handling conflicts.) 624 * 625 * Since we don't turn on break-rewrites by default, neither 626 * src_entry nor dst_entry can have all three of their stages have 627 * non-null oids, meaning at most four of the six will be non-null. 628 * Also, since this is a rename, both src_entry and dst_entry will 629 * have at least one non-null oid, meaning at least two will be 630 * non-null. Of the six oids, a typical rename will have three be 631 * non-null. Only two implies a rename/delete, and four implies a 632 * rename/add. 633 */ 634struct stage_data *src_entry; 635struct stage_data *dst_entry; 636unsigned add_turned_into_rename:1; 637unsigned processed:1; 638}; 639 640static intupdate_stages(struct merge_options *opt,const char*path, 641const struct diff_filespec *o, 642const struct diff_filespec *a, 643const struct diff_filespec *b) 644{ 645 646/* 647 * NOTE: It is usually a bad idea to call update_stages on a path 648 * before calling update_file on that same path, since it can 649 * sometimes lead to spurious "refusing to lose untracked file..." 650 * messages from update_file (via make_room_for path via 651 * would_lose_untracked). Instead, reverse the order of the calls 652 * (executing update_file first and then update_stages). 653 */ 654int clear =1; 655int options = ADD_CACHE_OK_TO_ADD | ADD_CACHE_SKIP_DFCHECK; 656if(clear) 657if(remove_file_from_cache(path)) 658return-1; 659if(o) 660if(add_cacheinfo(opt, o->mode, &o->oid, path,1,0, options)) 661return-1; 662if(a) 663if(add_cacheinfo(opt, a->mode, &a->oid, path,2,0, options)) 664return-1; 665if(b) 666if(add_cacheinfo(opt, b->mode, &b->oid, path,3,0, options)) 667return-1; 668return0; 669} 670 671static intupdate_stages_for_stage_data(struct merge_options *opt, 672const char*path, 673const struct stage_data *stage_data) 674{ 675struct diff_filespec o, a, b; 676 677 o.mode = stage_data->stages[1].mode; 678oidcpy(&o.oid, &stage_data->stages[1].oid); 679 680 a.mode = stage_data->stages[2].mode; 681oidcpy(&a.oid, &stage_data->stages[2].oid); 682 683 b.mode = stage_data->stages[3].mode; 684oidcpy(&b.oid, &stage_data->stages[3].oid); 685 686returnupdate_stages(opt, path, 687is_null_oid(&o.oid) ? NULL : &o, 688is_null_oid(&a.oid) ? NULL : &a, 689is_null_oid(&b.oid) ? NULL : &b); 690} 691 692static voidupdate_entry(struct stage_data *entry, 693struct diff_filespec *o, 694struct diff_filespec *a, 695struct diff_filespec *b) 696{ 697 entry->processed =0; 698 entry->stages[1].mode = o->mode; 699 entry->stages[2].mode = a->mode; 700 entry->stages[3].mode = b->mode; 701oidcpy(&entry->stages[1].oid, &o->oid); 702oidcpy(&entry->stages[2].oid, &a->oid); 703oidcpy(&entry->stages[3].oid, &b->oid); 704} 705 706static intremove_file(struct merge_options *o,int clean, 707const char*path,int no_wd) 708{ 709int update_cache = o->call_depth || clean; 710int update_working_directory = !o->call_depth && !no_wd; 711 712if(update_cache) { 713if(remove_file_from_cache(path)) 714return-1; 715} 716if(update_working_directory) { 717if(ignore_case) { 718struct cache_entry *ce; 719 ce =cache_file_exists(path,strlen(path), ignore_case); 720if(ce &&ce_stage(ce) ==0&&strcmp(path, ce->name)) 721return0; 722} 723if(remove_path(path)) 724return-1; 725} 726return0; 727} 728 729/* add a string to a strbuf, but converting "/" to "_" */ 730static voidadd_flattened_path(struct strbuf *out,const char*s) 731{ 732size_t i = out->len; 733strbuf_addstr(out, s); 734for(; i < out->len; i++) 735if(out->buf[i] =='/') 736 out->buf[i] ='_'; 737} 738 739static char*unique_path(struct merge_options *o,const char*path,const char*branch) 740{ 741struct path_hashmap_entry *entry; 742struct strbuf newpath = STRBUF_INIT; 743int suffix =0; 744size_t base_len; 745 746strbuf_addf(&newpath,"%s~", path); 747add_flattened_path(&newpath, branch); 748 749 base_len = newpath.len; 750while(hashmap_get_from_hash(&o->current_file_dir_set, 751path_hash(newpath.buf), newpath.buf) || 752(!o->call_depth &&file_exists(newpath.buf))) { 753strbuf_setlen(&newpath, base_len); 754strbuf_addf(&newpath,"_%d", suffix++); 755} 756 757FLEX_ALLOC_MEM(entry, path, newpath.buf, newpath.len); 758hashmap_entry_init(entry,path_hash(entry->path)); 759hashmap_add(&o->current_file_dir_set, entry); 760returnstrbuf_detach(&newpath, NULL); 761} 762 763/** 764 * Check whether a directory in the index is in the way of an incoming 765 * file. Return 1 if so. If check_working_copy is non-zero, also 766 * check the working directory. If empty_ok is non-zero, also return 767 * 0 in the case where the working-tree dir exists but is empty. 768 */ 769static intdir_in_way(const char*path,int check_working_copy,int empty_ok) 770{ 771int pos; 772struct strbuf dirpath = STRBUF_INIT; 773struct stat st; 774 775strbuf_addstr(&dirpath, path); 776strbuf_addch(&dirpath,'/'); 777 778 pos =cache_name_pos(dirpath.buf, dirpath.len); 779 780if(pos <0) 781 pos = -1- pos; 782if(pos < active_nr && 783!strncmp(dirpath.buf, active_cache[pos]->name, dirpath.len)) { 784strbuf_release(&dirpath); 785return1; 786} 787 788strbuf_release(&dirpath); 789return check_working_copy && !lstat(path, &st) &&S_ISDIR(st.st_mode) && 790!(empty_ok &&is_empty_dir(path)); 791} 792 793/* 794 * Returns whether path was tracked in the index before the merge started, 795 * and its oid and mode match the specified values 796 */ 797static intwas_tracked_and_matches(struct merge_options *o,const char*path, 798const struct object_id *oid,unsigned mode) 799{ 800int pos =index_name_pos(&o->orig_index, path,strlen(path)); 801struct cache_entry *ce; 802 803if(0> pos) 804/* we were not tracking this path before the merge */ 805return0; 806 807/* See if the file we were tracking before matches */ 808 ce = o->orig_index.cache[pos]; 809return(oid_eq(&ce->oid, oid) && ce->ce_mode == mode); 810} 811 812/* 813 * Returns whether path was tracked in the index before the merge started 814 */ 815static intwas_tracked(struct merge_options *o,const char*path) 816{ 817int pos =index_name_pos(&o->orig_index, path,strlen(path)); 818 819if(0<= pos) 820/* we were tracking this path before the merge */ 821return1; 822 823return0; 824} 825 826static intwould_lose_untracked(const char*path) 827{ 828/* 829 * This may look like it can be simplified to: 830 * return !was_tracked(o, path) && file_exists(path) 831 * but it can't. This function needs to know whether path was in 832 * the working tree due to EITHER having been tracked in the index 833 * before the merge OR having been put into the working copy and 834 * index by unpack_trees(). Due to that either-or requirement, we 835 * check the current index instead of the original one. 836 * 837 * Note that we do not need to worry about merge-recursive itself 838 * updating the index after unpack_trees() and before calling this 839 * function, because we strictly require all code paths in 840 * merge-recursive to update the working tree first and the index 841 * second. Doing otherwise would break 842 * update_file()/would_lose_untracked(); see every comment in this 843 * file which mentions "update_stages". 844 */ 845int pos =cache_name_pos(path,strlen(path)); 846 847if(pos <0) 848 pos = -1- pos; 849while(pos < active_nr && 850!strcmp(path, active_cache[pos]->name)) { 851/* 852 * If stage #0, it is definitely tracked. 853 * If it has stage #2 then it was tracked 854 * before this merge started. All other 855 * cases the path was not tracked. 856 */ 857switch(ce_stage(active_cache[pos])) { 858case0: 859case2: 860return0; 861} 862 pos++; 863} 864returnfile_exists(path); 865} 866 867static intwas_dirty(struct merge_options *o,const char*path) 868{ 869struct cache_entry *ce; 870int dirty =1; 871 872if(o->call_depth || !was_tracked(o, path)) 873return!dirty; 874 875 ce =index_file_exists(o->unpack_opts.src_index, 876 path,strlen(path), ignore_case); 877 dirty =verify_uptodate(ce, &o->unpack_opts) !=0; 878return dirty; 879} 880 881static intmake_room_for_path(struct merge_options *o,const char*path) 882{ 883int status, i; 884const char*msg =_("failed to create path '%s'%s"); 885 886/* Unlink any D/F conflict files that are in the way */ 887for(i =0; i < o->df_conflict_file_set.nr; i++) { 888const char*df_path = o->df_conflict_file_set.items[i].string; 889size_t pathlen =strlen(path); 890size_t df_pathlen =strlen(df_path); 891if(df_pathlen < pathlen && 892 path[df_pathlen] =='/'&& 893strncmp(path, df_path, df_pathlen) ==0) { 894output(o,3, 895_("Removing%sto make room for subdirectory\n"), 896 df_path); 897unlink(df_path); 898unsorted_string_list_delete_item(&o->df_conflict_file_set, 899 i,0); 900break; 901} 902} 903 904/* Make sure leading directories are created */ 905 status =safe_create_leading_directories_const(path); 906if(status) { 907if(status == SCLD_EXISTS) 908/* something else exists */ 909returnerr(o, msg, path,_(": perhaps a D/F conflict?")); 910returnerr(o, msg, path,""); 911} 912 913/* 914 * Do not unlink a file in the work tree if we are not 915 * tracking it. 916 */ 917if(would_lose_untracked(path)) 918returnerr(o,_("refusing to lose untracked file at '%s'"), 919 path); 920 921/* Successful unlink is good.. */ 922if(!unlink(path)) 923return0; 924/* .. and so is no existing file */ 925if(errno == ENOENT) 926return0; 927/* .. but not some other error (who really cares what?) */ 928returnerr(o, msg, path,_(": perhaps a D/F conflict?")); 929} 930 931static intupdate_file_flags(struct merge_options *o, 932const struct object_id *oid, 933unsigned mode, 934const char*path, 935int update_cache, 936int update_wd) 937{ 938int ret =0; 939 940if(o->call_depth) 941 update_wd =0; 942 943if(update_wd) { 944enum object_type type; 945void*buf; 946unsigned long size; 947 948if(S_ISGITLINK(mode)) { 949/* 950 * We may later decide to recursively descend into 951 * the submodule directory and update its index 952 * and/or work tree, but we do not do that now. 953 */ 954 update_wd =0; 955goto update_index; 956} 957 958 buf =read_object_file(oid, &type, &size); 959if(!buf) 960returnerr(o,_("cannot read object%s'%s'"),oid_to_hex(oid), path); 961if(type != OBJ_BLOB) { 962 ret =err(o,_("blob expected for%s'%s'"),oid_to_hex(oid), path); 963goto free_buf; 964} 965if(S_ISREG(mode)) { 966struct strbuf strbuf = STRBUF_INIT; 967if(convert_to_working_tree(path, buf, size, &strbuf)) { 968free(buf); 969 size = strbuf.len; 970 buf =strbuf_detach(&strbuf, NULL); 971} 972} 973 974if(make_room_for_path(o, path) <0) { 975 update_wd =0; 976goto free_buf; 977} 978if(S_ISREG(mode) || (!has_symlinks &&S_ISLNK(mode))) { 979int fd; 980if(mode &0100) 981 mode =0777; 982else 983 mode =0666; 984 fd =open(path, O_WRONLY | O_TRUNC | O_CREAT, mode); 985if(fd <0) { 986 ret =err(o,_("failed to open '%s':%s"), 987 path,strerror(errno)); 988goto free_buf; 989} 990write_in_full(fd, buf, size); 991close(fd); 992}else if(S_ISLNK(mode)) { 993char*lnk =xmemdupz(buf, size); 994safe_create_leading_directories_const(path); 995unlink(path); 996if(symlink(lnk, path)) 997 ret =err(o,_("failed to symlink '%s':%s"), 998 path,strerror(errno)); 999free(lnk);1000}else1001 ret =err(o,1002_("do not know what to do with%06o%s'%s'"),1003 mode,oid_to_hex(oid), path);1004 free_buf:1005free(buf);1006}1007update_index:1008if(!ret && update_cache)1009if(add_cacheinfo(o, mode, oid, path,0, update_wd,1010 ADD_CACHE_OK_TO_ADD))1011return-1;1012return ret;1013}10141015static intupdate_file(struct merge_options *o,1016int clean,1017const struct object_id *oid,1018unsigned mode,1019const char*path)1020{1021returnupdate_file_flags(o, oid, mode, path, o->call_depth || clean, !o->call_depth);1022}10231024/* Low level file merging, update and removal */10251026struct merge_file_info {1027struct object_id oid;1028unsigned mode;1029unsigned clean:1,1030 merge:1;1031};10321033static intmerge_3way(struct merge_options *o,1034 mmbuffer_t *result_buf,1035const struct diff_filespec *one,1036const struct diff_filespec *a,1037const struct diff_filespec *b,1038const char*branch1,1039const char*branch2)1040{1041 mmfile_t orig, src1, src2;1042struct ll_merge_options ll_opts = {0};1043char*base_name, *name1, *name2;1044int merge_status;10451046 ll_opts.renormalize = o->renormalize;1047 ll_opts.xdl_opts = o->xdl_opts;10481049if(o->call_depth) {1050 ll_opts.virtual_ancestor =1;1051 ll_opts.variant =0;1052}else{1053switch(o->recursive_variant) {1054case MERGE_RECURSIVE_OURS:1055 ll_opts.variant = XDL_MERGE_FAVOR_OURS;1056break;1057case MERGE_RECURSIVE_THEIRS:1058 ll_opts.variant = XDL_MERGE_FAVOR_THEIRS;1059break;1060default:1061 ll_opts.variant =0;1062break;1063}1064}10651066if(strcmp(a->path, b->path) ||1067(o->ancestor != NULL &&strcmp(a->path, one->path) !=0)) {1068 base_name = o->ancestor == NULL ? NULL :1069mkpathdup("%s:%s", o->ancestor, one->path);1070 name1 =mkpathdup("%s:%s", branch1, a->path);1071 name2 =mkpathdup("%s:%s", branch2, b->path);1072}else{1073 base_name = o->ancestor == NULL ? NULL :1074mkpathdup("%s", o->ancestor);1075 name1 =mkpathdup("%s", branch1);1076 name2 =mkpathdup("%s", branch2);1077}10781079read_mmblob(&orig, &one->oid);1080read_mmblob(&src1, &a->oid);1081read_mmblob(&src2, &b->oid);10821083 merge_status =ll_merge(result_buf, a->path, &orig, base_name,1084&src1, name1, &src2, name2, &ll_opts);10851086free(base_name);1087free(name1);1088free(name2);1089free(orig.ptr);1090free(src1.ptr);1091free(src2.ptr);1092return merge_status;1093}10941095static intfind_first_merges(struct object_array *result,const char*path,1096struct commit *a,struct commit *b)1097{1098int i, j;1099struct object_array merges = OBJECT_ARRAY_INIT;1100struct commit *commit;1101int contains_another;11021103char merged_revision[42];1104const char*rev_args[] = {"rev-list","--merges","--ancestry-path",1105"--all", merged_revision, NULL };1106struct rev_info revs;1107struct setup_revision_opt rev_opts;11081109memset(result,0,sizeof(struct object_array));1110memset(&rev_opts,0,sizeof(rev_opts));11111112/* get all revisions that merge commit a */1113xsnprintf(merged_revision,sizeof(merged_revision),"^%s",1114oid_to_hex(&a->object.oid));1115init_revisions(&revs, NULL);1116 rev_opts.submodule = path;1117/* FIXME: can't handle linked worktrees in submodules yet */1118 revs.single_worktree = path != NULL;1119setup_revisions(ARRAY_SIZE(rev_args)-1, rev_args, &revs, &rev_opts);11201121/* save all revisions from the above list that contain b */1122if(prepare_revision_walk(&revs))1123die("revision walk setup failed");1124while((commit =get_revision(&revs)) != NULL) {1125struct object *o = &(commit->object);1126if(in_merge_bases(b, commit))1127add_object_array(o, NULL, &merges);1128}1129reset_revision_walk();11301131/* Now we've got all merges that contain a and b. Prune all1132 * merges that contain another found merge and save them in1133 * result.1134 */1135for(i =0; i < merges.nr; i++) {1136struct commit *m1 = (struct commit *) merges.objects[i].item;11371138 contains_another =0;1139for(j =0; j < merges.nr; j++) {1140struct commit *m2 = (struct commit *) merges.objects[j].item;1141if(i != j &&in_merge_bases(m2, m1)) {1142 contains_another =1;1143break;1144}1145}11461147if(!contains_another)1148add_object_array(merges.objects[i].item, NULL, result);1149}11501151object_array_clear(&merges);1152return result->nr;1153}11541155static voidprint_commit(struct commit *commit)1156{1157struct strbuf sb = STRBUF_INIT;1158struct pretty_print_context ctx = {0};1159 ctx.date_mode.type = DATE_NORMAL;1160format_commit_message(commit,"%h:%m %s", &sb, &ctx);1161fprintf(stderr,"%s\n", sb.buf);1162strbuf_release(&sb);1163}11641165static intmerge_submodule(struct merge_options *o,1166struct object_id *result,const char*path,1167const struct object_id *base,const struct object_id *a,1168const struct object_id *b)1169{1170struct commit *commit_base, *commit_a, *commit_b;1171int parent_count;1172struct object_array merges;11731174int i;1175int search = !o->call_depth;11761177/* store a in result in case we fail */1178oidcpy(result, a);11791180/* we can not handle deletion conflicts */1181if(is_null_oid(base))1182return0;1183if(is_null_oid(a))1184return0;1185if(is_null_oid(b))1186return0;11871188if(add_submodule_odb(path)) {1189output(o,1,_("Failed to merge submodule%s(not checked out)"), path);1190return0;1191}11921193if(!(commit_base =lookup_commit_reference(base)) ||1194!(commit_a =lookup_commit_reference(a)) ||1195!(commit_b =lookup_commit_reference(b))) {1196output(o,1,_("Failed to merge submodule%s(commits not present)"), path);1197return0;1198}11991200/* check whether both changes are forward */1201if(!in_merge_bases(commit_base, commit_a) ||1202!in_merge_bases(commit_base, commit_b)) {1203output(o,1,_("Failed to merge submodule%s(commits don't follow merge-base)"), path);1204return0;1205}12061207/* Case #1: a is contained in b or vice versa */1208if(in_merge_bases(commit_a, commit_b)) {1209oidcpy(result, b);1210if(show(o,3)) {1211output(o,3,_("Fast-forwarding submodule%sto the following commit:"), path);1212output_commit_title(o, commit_b);1213}else if(show(o,2))1214output(o,2,_("Fast-forwarding submodule%s"), path);1215else1216;/* no output */12171218return1;1219}1220if(in_merge_bases(commit_b, commit_a)) {1221oidcpy(result, a);1222if(show(o,3)) {1223output(o,3,_("Fast-forwarding submodule%sto the following commit:"), path);1224output_commit_title(o, commit_a);1225}else if(show(o,2))1226output(o,2,_("Fast-forwarding submodule%s"), path);1227else1228;/* no output */12291230return1;1231}12321233/*1234 * Case #2: There are one or more merges that contain a and b in1235 * the submodule. If there is only one, then present it as a1236 * suggestion to the user, but leave it marked unmerged so the1237 * user needs to confirm the resolution.1238 */12391240/* Skip the search if makes no sense to the calling context. */1241if(!search)1242return0;12431244/* find commit which merges them */1245 parent_count =find_first_merges(&merges, path, commit_a, commit_b);1246switch(parent_count) {1247case0:1248output(o,1,_("Failed to merge submodule%s(merge following commits not found)"), path);1249break;12501251case1:1252output(o,1,_("Failed to merge submodule%s(not fast-forward)"), path);1253output(o,2,_("Found a possible merge resolution for the submodule:\n"));1254print_commit((struct commit *) merges.objects[0].item);1255output(o,2,_(1256"If this is correct simply add it to the index "1257"for example\n"1258"by using:\n\n"1259" git update-index --cacheinfo 160000%s\"%s\"\n\n"1260"which will accept this suggestion.\n"),1261oid_to_hex(&merges.objects[0].item->oid), path);1262break;12631264default:1265output(o,1,_("Failed to merge submodule%s(multiple merges found)"), path);1266for(i =0; i < merges.nr; i++)1267print_commit((struct commit *) merges.objects[i].item);1268}12691270object_array_clear(&merges);1271return0;1272}12731274static intmerge_file_1(struct merge_options *o,1275const struct diff_filespec *one,1276const struct diff_filespec *a,1277const struct diff_filespec *b,1278const char*filename,1279const char*branch1,1280const char*branch2,1281struct merge_file_info *result)1282{1283 result->merge =0;1284 result->clean =1;12851286if((S_IFMT & a->mode) != (S_IFMT & b->mode)) {1287 result->clean =0;1288if(S_ISREG(a->mode)) {1289 result->mode = a->mode;1290oidcpy(&result->oid, &a->oid);1291}else{1292 result->mode = b->mode;1293oidcpy(&result->oid, &b->oid);1294}1295}else{1296if(!oid_eq(&a->oid, &one->oid) && !oid_eq(&b->oid, &one->oid))1297 result->merge =1;12981299/*1300 * Merge modes1301 */1302if(a->mode == b->mode || a->mode == one->mode)1303 result->mode = b->mode;1304else{1305 result->mode = a->mode;1306if(b->mode != one->mode) {1307 result->clean =0;1308 result->merge =1;1309}1310}13111312if(oid_eq(&a->oid, &b->oid) ||oid_eq(&a->oid, &one->oid))1313oidcpy(&result->oid, &b->oid);1314else if(oid_eq(&b->oid, &one->oid))1315oidcpy(&result->oid, &a->oid);1316else if(S_ISREG(a->mode)) {1317 mmbuffer_t result_buf;1318int ret =0, merge_status;13191320 merge_status =merge_3way(o, &result_buf, one, a, b,1321 branch1, branch2);13221323if((merge_status <0) || !result_buf.ptr)1324 ret =err(o,_("Failed to execute internal merge"));13251326if(!ret &&1327write_object_file(result_buf.ptr, result_buf.size,1328 blob_type, &result->oid))1329 ret =err(o,_("Unable to add%sto database"),1330 a->path);13311332free(result_buf.ptr);1333if(ret)1334return ret;1335 result->clean = (merge_status ==0);1336}else if(S_ISGITLINK(a->mode)) {1337 result->clean =merge_submodule(o, &result->oid,1338 one->path,1339&one->oid,1340&a->oid,1341&b->oid);1342}else if(S_ISLNK(a->mode)) {1343switch(o->recursive_variant) {1344case MERGE_RECURSIVE_NORMAL:1345oidcpy(&result->oid, &a->oid);1346if(!oid_eq(&a->oid, &b->oid))1347 result->clean =0;1348break;1349case MERGE_RECURSIVE_OURS:1350oidcpy(&result->oid, &a->oid);1351break;1352case MERGE_RECURSIVE_THEIRS:1353oidcpy(&result->oid, &b->oid);1354break;1355}1356}else1357BUG("unsupported object type in the tree");1358}13591360if(result->merge)1361output(o,2,_("Auto-merging%s"), filename);13621363return0;1364}13651366static intmerge_file_special_markers(struct merge_options *o,1367const struct diff_filespec *one,1368const struct diff_filespec *a,1369const struct diff_filespec *b,1370const char*target_filename,1371const char*branch1,1372const char*filename1,1373const char*branch2,1374const char*filename2,1375struct merge_file_info *mfi)1376{1377char*side1 = NULL;1378char*side2 = NULL;1379int ret;13801381if(filename1)1382 side1 =xstrfmt("%s:%s", branch1, filename1);1383if(filename2)1384 side2 =xstrfmt("%s:%s", branch2, filename2);13851386 ret =merge_file_1(o, one, a, b, target_filename,1387 side1 ? side1 : branch1,1388 side2 ? side2 : branch2, mfi);13891390free(side1);1391free(side2);1392return ret;1393}13941395static intmerge_file_one(struct merge_options *o,1396const char*path,1397const struct object_id *o_oid,int o_mode,1398const struct object_id *a_oid,int a_mode,1399const struct object_id *b_oid,int b_mode,1400const char*branch1,1401const char*branch2,1402struct merge_file_info *mfi)1403{1404struct diff_filespec one, a, b;14051406 one.path = a.path = b.path = (char*)path;1407oidcpy(&one.oid, o_oid);1408 one.mode = o_mode;1409oidcpy(&a.oid, a_oid);1410 a.mode = a_mode;1411oidcpy(&b.oid, b_oid);1412 b.mode = b_mode;1413returnmerge_file_1(o, &one, &a, &b, path, branch1, branch2, mfi);1414}14151416static inthandle_rename_via_dir(struct merge_options *o,1417struct diff_filepair *pair,1418const char*rename_branch,1419const char*other_branch)1420{1421/*1422 * Handle file adds that need to be renamed due to directory rename1423 * detection. This differs from handle_rename_normal, because1424 * there is no content merge to do; just move the file into the1425 * desired final location.1426 */1427const struct diff_filespec *dest = pair->two;14281429if(!o->call_depth &&would_lose_untracked(dest->path)) {1430char*alt_path =unique_path(o, dest->path, rename_branch);14311432output(o,1,_("Error: Refusing to lose untracked file at%s; "1433"writing to%sinstead."),1434 dest->path, alt_path);1435/*1436 * Write the file in worktree at alt_path, but not in the1437 * index. Instead, write to dest->path for the index but1438 * only at the higher appropriate stage.1439 */1440if(update_file(o,0, &dest->oid, dest->mode, alt_path))1441return-1;1442free(alt_path);1443returnupdate_stages(o, dest->path, NULL,1444 rename_branch == o->branch1 ? dest : NULL,1445 rename_branch == o->branch1 ? NULL : dest);1446}14471448/* Update dest->path both in index and in worktree */1449if(update_file(o,1, &dest->oid, dest->mode, dest->path))1450return-1;1451return0;1452}14531454static inthandle_change_delete(struct merge_options *o,1455const char*path,const char*old_path,1456const struct object_id *o_oid,int o_mode,1457const struct object_id *changed_oid,1458int changed_mode,1459const char*change_branch,1460const char*delete_branch,1461const char*change,const char*change_past)1462{1463char*alt_path = NULL;1464const char*update_path = path;1465int ret =0;14661467if(dir_in_way(path, !o->call_depth,0) ||1468(!o->call_depth &&would_lose_untracked(path))) {1469 update_path = alt_path =unique_path(o, path, change_branch);1470}14711472if(o->call_depth) {1473/*1474 * We cannot arbitrarily accept either a_sha or b_sha as1475 * correct; since there is no true "middle point" between1476 * them, simply reuse the base version for virtual merge base.1477 */1478 ret =remove_file_from_cache(path);1479if(!ret)1480 ret =update_file(o,0, o_oid, o_mode, update_path);1481}else{1482/*1483 * Despite the four nearly duplicate messages and argument1484 * lists below and the ugliness of the nested if-statements,1485 * having complete messages makes the job easier for1486 * translators.1487 *1488 * The slight variance among the cases is due to the fact1489 * that:1490 * 1) directory/file conflicts (in effect if1491 * !alt_path) could cause us to need to write the1492 * file to a different path.1493 * 2) renames (in effect if !old_path) could mean that1494 * there are two names for the path that the user1495 * may know the file by.1496 */1497if(!alt_path) {1498if(!old_path) {1499output(o,1,_("CONFLICT (%s/delete):%sdeleted in%s"1500"and%sin%s. Version%sof%sleft in tree."),1501 change, path, delete_branch, change_past,1502 change_branch, change_branch, path);1503}else{1504output(o,1,_("CONFLICT (%s/delete):%sdeleted in%s"1505"and%sto%sin%s. Version%sof%sleft in tree."),1506 change, old_path, delete_branch, change_past, path,1507 change_branch, change_branch, path);1508}1509}else{1510if(!old_path) {1511output(o,1,_("CONFLICT (%s/delete):%sdeleted in%s"1512"and%sin%s. Version%sof%sleft in tree at%s."),1513 change, path, delete_branch, change_past,1514 change_branch, change_branch, path, alt_path);1515}else{1516output(o,1,_("CONFLICT (%s/delete):%sdeleted in%s"1517"and%sto%sin%s. Version%sof%sleft in tree at%s."),1518 change, old_path, delete_branch, change_past, path,1519 change_branch, change_branch, path, alt_path);1520}1521}1522/*1523 * No need to call update_file() on path when change_branch ==1524 * o->branch1 && !alt_path, since that would needlessly touch1525 * path. We could call update_file_flags() with update_cache=01526 * and update_wd=0, but that's a no-op.1527 */1528if(change_branch != o->branch1 || alt_path)1529 ret =update_file(o,0, changed_oid, changed_mode, update_path);1530}1531free(alt_path);15321533return ret;1534}15351536static inthandle_rename_delete(struct merge_options *o,1537struct diff_filepair *pair,1538const char*rename_branch,1539const char*delete_branch)1540{1541const struct diff_filespec *orig = pair->one;1542const struct diff_filespec *dest = pair->two;15431544if(handle_change_delete(o,1545 o->call_depth ? orig->path : dest->path,1546 o->call_depth ? NULL : orig->path,1547&orig->oid, orig->mode,1548&dest->oid, dest->mode,1549 rename_branch, delete_branch,1550_("rename"),_("renamed")))1551return-1;15521553if(o->call_depth)1554returnremove_file_from_cache(dest->path);1555else1556returnupdate_stages(o, dest->path, NULL,1557 rename_branch == o->branch1 ? dest : NULL,1558 rename_branch == o->branch1 ? NULL : dest);1559}15601561static struct diff_filespec *filespec_from_entry(struct diff_filespec *target,1562struct stage_data *entry,1563int stage)1564{1565struct object_id *oid = &entry->stages[stage].oid;1566unsigned mode = entry->stages[stage].mode;1567if(mode ==0||is_null_oid(oid))1568return NULL;1569oidcpy(&target->oid, oid);1570 target->mode = mode;1571return target;1572}15731574static inthandle_file(struct merge_options *o,1575struct diff_filespec *rename,1576int stage,1577struct rename_conflict_info *ci)1578{1579char*dst_name = rename->path;1580struct stage_data *dst_entry;1581const char*cur_branch, *other_branch;1582struct diff_filespec other;1583struct diff_filespec *add;1584int ret;15851586if(stage ==2) {1587 dst_entry = ci->dst_entry1;1588 cur_branch = ci->branch1;1589 other_branch = ci->branch2;1590}else{1591 dst_entry = ci->dst_entry2;1592 cur_branch = ci->branch2;1593 other_branch = ci->branch1;1594}15951596 add =filespec_from_entry(&other, dst_entry, stage ^1);1597if(add) {1598int ren_src_was_dirty =was_dirty(o, rename->path);1599char*add_name =unique_path(o, rename->path, other_branch);1600if(update_file(o,0, &add->oid, add->mode, add_name))1601return-1;16021603if(ren_src_was_dirty) {1604output(o,1,_("Refusing to lose dirty file at%s"),1605 rename->path);1606}1607/*1608 * Because the double negatives somehow keep confusing me...1609 * 1) update_wd iff !ren_src_was_dirty.1610 * 2) no_wd iff !update_wd1611 * 3) so, no_wd == !!ren_src_was_dirty == ren_src_was_dirty1612 */1613remove_file(o,0, rename->path, ren_src_was_dirty);1614 dst_name =unique_path(o, rename->path, cur_branch);1615}else{1616if(dir_in_way(rename->path, !o->call_depth,0)) {1617 dst_name =unique_path(o, rename->path, cur_branch);1618output(o,1,_("%sis a directory in%sadding as%sinstead"),1619 rename->path, other_branch, dst_name);1620}else if(!o->call_depth &&1621would_lose_untracked(rename->path)) {1622 dst_name =unique_path(o, rename->path, cur_branch);1623output(o,1,_("Refusing to lose untracked file at%s; "1624"adding as%sinstead"),1625 rename->path, dst_name);1626}1627}1628if((ret =update_file(o,0, &rename->oid, rename->mode, dst_name)))1629;/* fall through, do allow dst_name to be released */1630else if(stage ==2)1631 ret =update_stages(o, rename->path, NULL, rename, add);1632else1633 ret =update_stages(o, rename->path, NULL, add, rename);16341635if(dst_name != rename->path)1636free(dst_name);16371638return ret;1639}16401641static inthandle_rename_rename_1to2(struct merge_options *o,1642struct rename_conflict_info *ci)1643{1644/* One file was renamed in both branches, but to different names. */1645struct diff_filespec *one = ci->pair1->one;1646struct diff_filespec *a = ci->pair1->two;1647struct diff_filespec *b = ci->pair2->two;16481649output(o,1,_("CONFLICT (rename/rename): "1650"Rename\"%s\"->\"%s\"in branch\"%s\""1651"rename\"%s\"->\"%s\"in\"%s\"%s"),1652 one->path, a->path, ci->branch1,1653 one->path, b->path, ci->branch2,1654 o->call_depth ?_(" (left unresolved)") :"");1655if(o->call_depth) {1656struct merge_file_info mfi;1657struct diff_filespec other;1658struct diff_filespec *add;1659if(merge_file_one(o, one->path,1660&one->oid, one->mode,1661&a->oid, a->mode,1662&b->oid, b->mode,1663 ci->branch1, ci->branch2, &mfi))1664return-1;16651666/*1667 * FIXME: For rename/add-source conflicts (if we could detect1668 * such), this is wrong. We should instead find a unique1669 * pathname and then either rename the add-source file to that1670 * unique path, or use that unique path instead of src here.1671 */1672if(update_file(o,0, &mfi.oid, mfi.mode, one->path))1673return-1;16741675/*1676 * Above, we put the merged content at the merge-base's1677 * path. Now we usually need to delete both a->path and1678 * b->path. However, the rename on each side of the merge1679 * could also be involved in a rename/add conflict. In1680 * such cases, we should keep the added file around,1681 * resolving the conflict at that path in its favor.1682 */1683 add =filespec_from_entry(&other, ci->dst_entry1,2^1);1684if(add) {1685if(update_file(o,0, &add->oid, add->mode, a->path))1686return-1;1687}1688else1689remove_file_from_cache(a->path);1690 add =filespec_from_entry(&other, ci->dst_entry2,3^1);1691if(add) {1692if(update_file(o,0, &add->oid, add->mode, b->path))1693return-1;1694}1695else1696remove_file_from_cache(b->path);1697}else if(handle_file(o, a,2, ci) ||handle_file(o, b,3, ci))1698return-1;16991700return0;1701}17021703static inthandle_rename_rename_2to1(struct merge_options *o,1704struct rename_conflict_info *ci)1705{1706/* Two files, a & b, were renamed to the same thing, c. */1707struct diff_filespec *a = ci->pair1->one;1708struct diff_filespec *b = ci->pair2->one;1709struct diff_filespec *c1 = ci->pair1->two;1710struct diff_filespec *c2 = ci->pair2->two;1711char*path = c1->path;/* == c2->path */1712char*path_side_1_desc;1713char*path_side_2_desc;1714struct merge_file_info mfi_c1;1715struct merge_file_info mfi_c2;1716int ret;17171718output(o,1,_("CONFLICT (rename/rename): "1719"Rename%s->%sin%s. "1720"Rename%s->%sin%s"),1721 a->path, c1->path, ci->branch1,1722 b->path, c2->path, ci->branch2);17231724remove_file(o,1, a->path, o->call_depth ||would_lose_untracked(a->path));1725remove_file(o,1, b->path, o->call_depth ||would_lose_untracked(b->path));17261727 path_side_1_desc =xstrfmt("%s(was%s)", path, a->path);1728 path_side_2_desc =xstrfmt("%s(was%s)", path, b->path);1729if(merge_file_special_markers(o, a, c1, &ci->ren1_other,1730 path_side_1_desc,1731 o->branch1, c1->path,1732 o->branch2, ci->ren1_other.path, &mfi_c1) ||1733merge_file_special_markers(o, b, &ci->ren2_other, c2,1734 path_side_2_desc,1735 o->branch1, ci->ren2_other.path,1736 o->branch2, c2->path, &mfi_c2))1737return-1;1738free(path_side_1_desc);1739free(path_side_2_desc);17401741if(o->call_depth) {1742/*1743 * If mfi_c1.clean && mfi_c2.clean, then it might make1744 * sense to do a two-way merge of those results. But, I1745 * think in all cases, it makes sense to have the virtual1746 * merge base just undo the renames; they can be detected1747 * again later for the non-recursive merge.1748 */1749remove_file(o,0, path,0);1750 ret =update_file(o,0, &mfi_c1.oid, mfi_c1.mode, a->path);1751if(!ret)1752 ret =update_file(o,0, &mfi_c2.oid, mfi_c2.mode,1753 b->path);1754}else{1755char*new_path1 =unique_path(o, path, ci->branch1);1756char*new_path2 =unique_path(o, path, ci->branch2);1757output(o,1,_("Renaming%sto%sand%sto%sinstead"),1758 a->path, new_path1, b->path, new_path2);1759if(was_dirty(o, path))1760output(o,1,_("Refusing to lose dirty file at%s"),1761 path);1762else if(would_lose_untracked(path))1763/*1764 * Only way we get here is if both renames were from1765 * a directory rename AND user had an untracked file1766 * at the location where both files end up after the1767 * two directory renames. See testcase 10d of t6043.1768 */1769output(o,1,_("Refusing to lose untracked file at "1770"%s, even though it's in the way."),1771 path);1772else1773remove_file(o,0, path,0);1774 ret =update_file(o,0, &mfi_c1.oid, mfi_c1.mode, new_path1);1775if(!ret)1776 ret =update_file(o,0, &mfi_c2.oid, mfi_c2.mode,1777 new_path2);1778/*1779 * unpack_trees() actually populates the index for us for1780 * "normal" rename/rename(2to1) situtations so that the1781 * correct entries are at the higher stages, which would1782 * make the call below to update_stages_for_stage_data1783 * unnecessary. However, if either of the renames came1784 * from a directory rename, then unpack_trees() will not1785 * have gotten the right data loaded into the index, so we1786 * need to do so now. (While it'd be tempting to move this1787 * call to update_stages_for_stage_data() to1788 * apply_directory_rename_modifications(), that would break1789 * our intermediate calls to would_lose_untracked() since1790 * those rely on the current in-memory index. See also the1791 * big "NOTE" in update_stages()).1792 */1793if(update_stages_for_stage_data(o, path, ci->dst_entry1))1794 ret = -1;17951796free(new_path2);1797free(new_path1);1798}17991800return ret;1801}18021803/*1804 * Get the diff_filepairs changed between o_tree and tree.1805 */1806static struct diff_queue_struct *get_diffpairs(struct merge_options *o,1807struct tree *o_tree,1808struct tree *tree)1809{1810struct diff_queue_struct *ret;1811struct diff_options opts;18121813diff_setup(&opts);1814 opts.flags.recursive =1;1815 opts.flags.rename_empty =0;1816 opts.detect_rename =merge_detect_rename(o);1817/*1818 * We do not have logic to handle the detection of copies. In1819 * fact, it may not even make sense to add such logic: would we1820 * really want a change to a base file to be propagated through1821 * multiple other files by a merge?1822 */1823if(opts.detect_rename > DIFF_DETECT_RENAME)1824 opts.detect_rename = DIFF_DETECT_RENAME;1825 opts.rename_limit = o->merge_rename_limit >=0? o->merge_rename_limit :1826 o->diff_rename_limit >=0? o->diff_rename_limit :18271000;1828 opts.rename_score = o->rename_score;1829 opts.show_rename_progress = o->show_rename_progress;1830 opts.output_format = DIFF_FORMAT_NO_OUTPUT;1831diff_setup_done(&opts);1832diff_tree_oid(&o_tree->object.oid, &tree->object.oid,"", &opts);1833diffcore_std(&opts);1834if(opts.needed_rename_limit > o->needed_rename_limit)1835 o->needed_rename_limit = opts.needed_rename_limit;18361837 ret =xmalloc(sizeof(*ret));1838*ret = diff_queued_diff;18391840 opts.output_format = DIFF_FORMAT_NO_OUTPUT;1841 diff_queued_diff.nr =0;1842 diff_queued_diff.queue = NULL;1843diff_flush(&opts);1844return ret;1845}18461847static inttree_has_path(struct tree *tree,const char*path)1848{1849struct object_id hashy;1850unsigned int mode_o;18511852return!get_tree_entry(&tree->object.oid, path,1853&hashy, &mode_o);1854}18551856/*1857 * Return a new string that replaces the beginning portion (which matches1858 * entry->dir), with entry->new_dir. In perl-speak:1859 * new_path_name = (old_path =~ s/entry->dir/entry->new_dir/);1860 * NOTE:1861 * Caller must ensure that old_path starts with entry->dir + '/'.1862 */1863static char*apply_dir_rename(struct dir_rename_entry *entry,1864const char*old_path)1865{1866struct strbuf new_path = STRBUF_INIT;1867int oldlen, newlen;18681869if(entry->non_unique_new_dir)1870return NULL;18711872 oldlen =strlen(entry->dir);1873 newlen = entry->new_dir.len + (strlen(old_path) - oldlen) +1;1874strbuf_grow(&new_path, newlen);1875strbuf_addbuf(&new_path, &entry->new_dir);1876strbuf_addstr(&new_path, &old_path[oldlen]);18771878returnstrbuf_detach(&new_path, NULL);1879}18801881static voidget_renamed_dir_portion(const char*old_path,const char*new_path,1882char**old_dir,char**new_dir)1883{1884char*end_of_old, *end_of_new;1885int old_len, new_len;18861887*old_dir = NULL;1888*new_dir = NULL;18891890/*1891 * For1892 * "a/b/c/d/e/foo.c" -> "a/b/some/thing/else/e/foo.c"1893 * the "e/foo.c" part is the same, we just want to know that1894 * "a/b/c/d" was renamed to "a/b/some/thing/else"1895 * so, for this example, this function returns "a/b/c/d" in1896 * *old_dir and "a/b/some/thing/else" in *new_dir.1897 *1898 * Also, if the basename of the file changed, we don't care. We1899 * want to know which portion of the directory, if any, changed.1900 */1901 end_of_old =strrchr(old_path,'/');1902 end_of_new =strrchr(new_path,'/');19031904if(end_of_old == NULL || end_of_new == NULL)1905return;1906while(*--end_of_new == *--end_of_old &&1907 end_of_old != old_path &&1908 end_of_new != new_path)1909;/* Do nothing; all in the while loop */1910/*1911 * We've found the first non-matching character in the directory1912 * paths. That means the current directory we were comparing1913 * represents the rename. Move end_of_old and end_of_new back1914 * to the full directory name.1915 */1916if(*end_of_old =='/')1917 end_of_old++;1918if(*end_of_old !='/')1919 end_of_new++;1920 end_of_old =strchr(end_of_old,'/');1921 end_of_new =strchr(end_of_new,'/');19221923/*1924 * It may have been the case that old_path and new_path were the same1925 * directory all along. Don't claim a rename if they're the same.1926 */1927 old_len = end_of_old - old_path;1928 new_len = end_of_new - new_path;19291930if(old_len != new_len ||strncmp(old_path, new_path, old_len)) {1931*old_dir =xstrndup(old_path, old_len);1932*new_dir =xstrndup(new_path, new_len);1933}1934}19351936static voidremove_hashmap_entries(struct hashmap *dir_renames,1937struct string_list *items_to_remove)1938{1939int i;1940struct dir_rename_entry *entry;19411942for(i =0; i < items_to_remove->nr; i++) {1943 entry = items_to_remove->items[i].util;1944hashmap_remove(dir_renames, entry, NULL);1945}1946string_list_clear(items_to_remove,0);1947}19481949/*1950 * See if there is a directory rename for path, and if there are any file1951 * level conflicts for the renamed location. If there is a rename and1952 * there are no conflicts, return the new name. Otherwise, return NULL.1953 */1954static char*handle_path_level_conflicts(struct merge_options *o,1955const char*path,1956struct dir_rename_entry *entry,1957struct hashmap *collisions,1958struct tree *tree)1959{1960char*new_path = NULL;1961struct collision_entry *collision_ent;1962int clean =1;1963struct strbuf collision_paths = STRBUF_INIT;19641965/*1966 * entry has the mapping of old directory name to new directory name1967 * that we want to apply to path.1968 */1969 new_path =apply_dir_rename(entry, path);19701971if(!new_path) {1972/* This should only happen when entry->non_unique_new_dir set */1973if(!entry->non_unique_new_dir)1974BUG("entry->non_unqiue_dir not set and !new_path");1975output(o,1,_("CONFLICT (directory rename split): "1976"Unclear where to place%sbecause directory "1977"%swas renamed to multiple other directories, "1978"with no destination getting a majority of the "1979"files."),1980 path, entry->dir);1981 clean =0;1982return NULL;1983}19841985/*1986 * The caller needs to have ensured that it has pre-populated1987 * collisions with all paths that map to new_path. Do a quick check1988 * to ensure that's the case.1989 */1990 collision_ent =collision_find_entry(collisions, new_path);1991if(collision_ent == NULL)1992BUG("collision_ent is NULL");19931994/*1995 * Check for one-sided add/add/.../add conflicts, i.e.1996 * where implicit renames from the other side doing1997 * directory rename(s) can affect this side of history1998 * to put multiple paths into the same location. Warn1999 * and bail on directory renames for such paths.2000 */2001if(collision_ent->reported_already) {2002 clean =0;2003}else if(tree_has_path(tree, new_path)) {2004 collision_ent->reported_already =1;2005strbuf_add_separated_string_list(&collision_paths,", ",2006&collision_ent->source_files);2007output(o,1,_("CONFLICT (implicit dir rename): Existing "2008"file/dir at%sin the way of implicit "2009"directory rename(s) putting the following "2010"path(s) there:%s."),2011 new_path, collision_paths.buf);2012 clean =0;2013}else if(collision_ent->source_files.nr >1) {2014 collision_ent->reported_already =1;2015strbuf_add_separated_string_list(&collision_paths,", ",2016&collision_ent->source_files);2017output(o,1,_("CONFLICT (implicit dir rename): Cannot map "2018"more than one path to%s; implicit directory "2019"renames tried to put these paths there:%s"),2020 new_path, collision_paths.buf);2021 clean =0;2022}20232024/* Free memory we no longer need */2025strbuf_release(&collision_paths);2026if(!clean && new_path) {2027free(new_path);2028return NULL;2029}20302031return new_path;2032}20332034/*2035 * There are a couple things we want to do at the directory level:2036 * 1. Check for both sides renaming to the same thing, in order to avoid2037 * implicit renaming of files that should be left in place. (See2038 * testcase 6b in t6043 for details.)2039 * 2. Prune directory renames if there are still files left in the2040 * the original directory. These represent a partial directory rename,2041 * i.e. a rename where only some of the files within the directory2042 * were renamed elsewhere. (Technically, this could be done earlier2043 * in get_directory_renames(), except that would prevent us from2044 * doing the previous check and thus failing testcase 6b.)2045 * 3. Check for rename/rename(1to2) conflicts (at the directory level).2046 * In the future, we could potentially record this info as well and2047 * omit reporting rename/rename(1to2) conflicts for each path within2048 * the affected directories, thus cleaning up the merge output.2049 * NOTE: We do NOT check for rename/rename(2to1) conflicts at the2050 * directory level, because merging directories is fine. If it2051 * causes conflicts for files within those merged directories, then2052 * that should be detected at the individual path level.2053 */2054static voidhandle_directory_level_conflicts(struct merge_options *o,2055struct hashmap *dir_re_head,2056struct tree *head,2057struct hashmap *dir_re_merge,2058struct tree *merge)2059{2060struct hashmap_iter iter;2061struct dir_rename_entry *head_ent;2062struct dir_rename_entry *merge_ent;20632064struct string_list remove_from_head = STRING_LIST_INIT_NODUP;2065struct string_list remove_from_merge = STRING_LIST_INIT_NODUP;20662067hashmap_iter_init(dir_re_head, &iter);2068while((head_ent =hashmap_iter_next(&iter))) {2069 merge_ent =dir_rename_find_entry(dir_re_merge, head_ent->dir);2070if(merge_ent &&2071!head_ent->non_unique_new_dir &&2072!merge_ent->non_unique_new_dir &&2073!strbuf_cmp(&head_ent->new_dir, &merge_ent->new_dir)) {2074/* 1. Renamed identically; remove it from both sides */2075string_list_append(&remove_from_head,2076 head_ent->dir)->util = head_ent;2077strbuf_release(&head_ent->new_dir);2078string_list_append(&remove_from_merge,2079 merge_ent->dir)->util = merge_ent;2080strbuf_release(&merge_ent->new_dir);2081}else if(tree_has_path(head, head_ent->dir)) {2082/* 2. This wasn't a directory rename after all */2083string_list_append(&remove_from_head,2084 head_ent->dir)->util = head_ent;2085strbuf_release(&head_ent->new_dir);2086}2087}20882089remove_hashmap_entries(dir_re_head, &remove_from_head);2090remove_hashmap_entries(dir_re_merge, &remove_from_merge);20912092hashmap_iter_init(dir_re_merge, &iter);2093while((merge_ent =hashmap_iter_next(&iter))) {2094 head_ent =dir_rename_find_entry(dir_re_head, merge_ent->dir);2095if(tree_has_path(merge, merge_ent->dir)) {2096/* 2. This wasn't a directory rename after all */2097string_list_append(&remove_from_merge,2098 merge_ent->dir)->util = merge_ent;2099}else if(head_ent &&2100!head_ent->non_unique_new_dir &&2101!merge_ent->non_unique_new_dir) {2102/* 3. rename/rename(1to2) */2103/*2104 * We can assume it's not rename/rename(1to1) because2105 * that was case (1), already checked above. So we2106 * know that head_ent->new_dir and merge_ent->new_dir2107 * are different strings.2108 */2109output(o,1,_("CONFLICT (rename/rename): "2110"Rename directory%s->%sin%s. "2111"Rename directory%s->%sin%s"),2112 head_ent->dir, head_ent->new_dir.buf, o->branch1,2113 head_ent->dir, merge_ent->new_dir.buf, o->branch2);2114string_list_append(&remove_from_head,2115 head_ent->dir)->util = head_ent;2116strbuf_release(&head_ent->new_dir);2117string_list_append(&remove_from_merge,2118 merge_ent->dir)->util = merge_ent;2119strbuf_release(&merge_ent->new_dir);2120}2121}21222123remove_hashmap_entries(dir_re_head, &remove_from_head);2124remove_hashmap_entries(dir_re_merge, &remove_from_merge);2125}21262127static struct hashmap *get_directory_renames(struct diff_queue_struct *pairs,2128struct tree *tree)2129{2130struct hashmap *dir_renames;2131struct hashmap_iter iter;2132struct dir_rename_entry *entry;2133int i;21342135/*2136 * Typically, we think of a directory rename as all files from a2137 * certain directory being moved to a target directory. However,2138 * what if someone first moved two files from the original2139 * directory in one commit, and then renamed the directory2140 * somewhere else in a later commit? At merge time, we just know2141 * that files from the original directory went to two different2142 * places, and that the bulk of them ended up in the same place.2143 * We want each directory rename to represent where the bulk of the2144 * files from that directory end up; this function exists to find2145 * where the bulk of the files went.2146 *2147 * The first loop below simply iterates through the list of file2148 * renames, finding out how often each directory rename pair2149 * possibility occurs.2150 */2151 dir_renames =xmalloc(sizeof(*dir_renames));2152dir_rename_init(dir_renames);2153for(i =0; i < pairs->nr; ++i) {2154struct string_list_item *item;2155int*count;2156struct diff_filepair *pair = pairs->queue[i];2157char*old_dir, *new_dir;21582159/* File not part of directory rename if it wasn't renamed */2160if(pair->status !='R')2161continue;21622163get_renamed_dir_portion(pair->one->path, pair->two->path,2164&old_dir, &new_dir);2165if(!old_dir)2166/* Directory didn't change at all; ignore this one. */2167continue;21682169 entry =dir_rename_find_entry(dir_renames, old_dir);2170if(!entry) {2171 entry =xmalloc(sizeof(*entry));2172dir_rename_entry_init(entry, old_dir);2173hashmap_put(dir_renames, entry);2174}else{2175free(old_dir);2176}2177 item =string_list_lookup(&entry->possible_new_dirs, new_dir);2178if(!item) {2179 item =string_list_insert(&entry->possible_new_dirs,2180 new_dir);2181 item->util =xcalloc(1,sizeof(int));2182}else{2183free(new_dir);2184}2185 count = item->util;2186*count +=1;2187}21882189/*2190 * For each directory with files moved out of it, we find out which2191 * target directory received the most files so we can declare it to2192 * be the "winning" target location for the directory rename. This2193 * winner gets recorded in new_dir. If there is no winner2194 * (multiple target directories received the same number of files),2195 * we set non_unique_new_dir. Once we've determined the winner (or2196 * that there is no winner), we no longer need possible_new_dirs.2197 */2198hashmap_iter_init(dir_renames, &iter);2199while((entry =hashmap_iter_next(&iter))) {2200int max =0;2201int bad_max =0;2202char*best = NULL;22032204for(i =0; i < entry->possible_new_dirs.nr; i++) {2205int*count = entry->possible_new_dirs.items[i].util;22062207if(*count == max)2208 bad_max = max;2209else if(*count > max) {2210 max = *count;2211 best = entry->possible_new_dirs.items[i].string;2212}2213}2214if(bad_max == max)2215 entry->non_unique_new_dir =1;2216else{2217assert(entry->new_dir.len ==0);2218strbuf_addstr(&entry->new_dir, best);2219}2220/*2221 * The relevant directory sub-portion of the original full2222 * filepaths were xstrndup'ed before inserting into2223 * possible_new_dirs, and instead of manually iterating the2224 * list and free'ing each, just lie and tell2225 * possible_new_dirs that it did the strdup'ing so that it2226 * will free them for us.2227 */2228 entry->possible_new_dirs.strdup_strings =1;2229string_list_clear(&entry->possible_new_dirs,1);2230}22312232return dir_renames;2233}22342235static struct dir_rename_entry *check_dir_renamed(const char*path,2236struct hashmap *dir_renames)2237{2238char*temp =xstrdup(path);2239char*end;2240struct dir_rename_entry *entry = NULL;;22412242while((end =strrchr(temp,'/'))) {2243*end ='\0';2244 entry =dir_rename_find_entry(dir_renames, temp);2245if(entry)2246break;2247}2248free(temp);2249return entry;2250}22512252static voidcompute_collisions(struct hashmap *collisions,2253struct hashmap *dir_renames,2254struct diff_queue_struct *pairs)2255{2256int i;22572258/*2259 * Multiple files can be mapped to the same path due to directory2260 * renames done by the other side of history. Since that other2261 * side of history could have merged multiple directories into one,2262 * if our side of history added the same file basename to each of2263 * those directories, then all N of them would get implicitly2264 * renamed by the directory rename detection into the same path,2265 * and we'd get an add/add/.../add conflict, and all those adds2266 * from *this* side of history. This is not representable in the2267 * index, and users aren't going to easily be able to make sense of2268 * it. So we need to provide a good warning about what's2269 * happening, and fall back to no-directory-rename detection2270 * behavior for those paths.2271 *2272 * See testcases 9e and all of section 5 from t6043 for examples.2273 */2274collision_init(collisions);22752276for(i =0; i < pairs->nr; ++i) {2277struct dir_rename_entry *dir_rename_ent;2278struct collision_entry *collision_ent;2279char*new_path;2280struct diff_filepair *pair = pairs->queue[i];22812282if(pair->status !='A'&& pair->status !='R')2283continue;2284 dir_rename_ent =check_dir_renamed(pair->two->path,2285 dir_renames);2286if(!dir_rename_ent)2287continue;22882289 new_path =apply_dir_rename(dir_rename_ent, pair->two->path);2290if(!new_path)2291/*2292 * dir_rename_ent->non_unique_new_path is true, which2293 * means there is no directory rename for us to use,2294 * which means it won't cause us any additional2295 * collisions.2296 */2297continue;2298 collision_ent =collision_find_entry(collisions, new_path);2299if(!collision_ent) {2300 collision_ent =xcalloc(1,2301sizeof(struct collision_entry));2302hashmap_entry_init(collision_ent,strhash(new_path));2303hashmap_put(collisions, collision_ent);2304 collision_ent->target_file = new_path;2305}else{2306free(new_path);2307}2308string_list_insert(&collision_ent->source_files,2309 pair->two->path);2310}2311}23122313static char*check_for_directory_rename(struct merge_options *o,2314const char*path,2315struct tree *tree,2316struct hashmap *dir_renames,2317struct hashmap *dir_rename_exclusions,2318struct hashmap *collisions,2319int*clean_merge)2320{2321char*new_path = NULL;2322struct dir_rename_entry *entry =check_dir_renamed(path, dir_renames);2323struct dir_rename_entry *oentry = NULL;23242325if(!entry)2326return new_path;23272328/*2329 * This next part is a little weird. We do not want to do an2330 * implicit rename into a directory we renamed on our side, because2331 * that will result in a spurious rename/rename(1to2) conflict. An2332 * example:2333 * Base commit: dumbdir/afile, otherdir/bfile2334 * Side 1: smrtdir/afile, otherdir/bfile2335 * Side 2: dumbdir/afile, dumbdir/bfile2336 * Here, while working on Side 1, we could notice that otherdir was2337 * renamed/merged to dumbdir, and change the diff_filepair for2338 * otherdir/bfile into a rename into dumbdir/bfile. However, Side2339 * 2 will notice the rename from dumbdir to smrtdir, and do the2340 * transitive rename to move it from dumbdir/bfile to2341 * smrtdir/bfile. That gives us bfile in dumbdir vs being in2342 * smrtdir, a rename/rename(1to2) conflict. We really just want2343 * the file to end up in smrtdir. And the way to achieve that is2344 * to not let Side1 do the rename to dumbdir, since we know that is2345 * the source of one of our directory renames.2346 *2347 * That's why oentry and dir_rename_exclusions is here.2348 *2349 * As it turns out, this also prevents N-way transient rename2350 * confusion; See testcases 9c and 9d of t6043.2351 */2352 oentry =dir_rename_find_entry(dir_rename_exclusions, entry->new_dir.buf);2353if(oentry) {2354output(o,1,_("WARNING: Avoiding applying%s->%srename "2355"to%s, because%sitself was renamed."),2356 entry->dir, entry->new_dir.buf, path, entry->new_dir.buf);2357}else{2358 new_path =handle_path_level_conflicts(o, path, entry,2359 collisions, tree);2360*clean_merge &= (new_path != NULL);2361}23622363return new_path;2364}23652366static voidapply_directory_rename_modifications(struct merge_options *o,2367struct diff_filepair *pair,2368char*new_path,2369struct rename *re,2370struct tree *tree,2371struct tree *o_tree,2372struct tree *a_tree,2373struct tree *b_tree,2374struct string_list *entries,2375int*clean)2376{2377struct string_list_item *item;2378int stage = (tree == a_tree ?2:3);2379int update_wd;23802381/*2382 * In all cases where we can do directory rename detection,2383 * unpack_trees() will have read pair->two->path into the2384 * index and the working copy. We need to remove it so that2385 * we can instead place it at new_path. It is guaranteed to2386 * not be untracked (unpack_trees() would have errored out2387 * saying the file would have been overwritten), but it might2388 * be dirty, though.2389 */2390 update_wd = !was_dirty(o, pair->two->path);2391if(!update_wd)2392output(o,1,_("Refusing to lose dirty file at%s"),2393 pair->two->path);2394remove_file(o,1, pair->two->path, !update_wd);23952396/* Find or create a new re->dst_entry */2397 item =string_list_lookup(entries, new_path);2398if(item) {2399/*2400 * Since we're renaming on this side of history, and it's2401 * due to a directory rename on the other side of history2402 * (which we only allow when the directory in question no2403 * longer exists on the other side of history), the2404 * original entry for re->dst_entry is no longer2405 * necessary...2406 */2407 re->dst_entry->processed =1;24082409/*2410 * ...because we'll be using this new one.2411 */2412 re->dst_entry = item->util;2413}else{2414/*2415 * re->dst_entry is for the before-dir-rename path, and we2416 * need it to hold information for the after-dir-rename2417 * path. Before creating a new entry, we need to mark the2418 * old one as unnecessary (...unless it is shared by2419 * src_entry, i.e. this didn't use to be a rename, in which2420 * case we can just allow the normal processing to happen2421 * for it).2422 */2423if(pair->status =='R')2424 re->dst_entry->processed =1;24252426 re->dst_entry =insert_stage_data(new_path,2427 o_tree, a_tree, b_tree,2428 entries);2429 item =string_list_insert(entries, new_path);2430 item->util = re->dst_entry;2431}24322433/*2434 * Update the stage_data with the information about the path we are2435 * moving into place. That slot will be empty and available for us2436 * to write to because of the collision checks in2437 * handle_path_level_conflicts(). In other words,2438 * re->dst_entry->stages[stage].oid will be the null_oid, so it's2439 * open for us to write to.2440 *2441 * It may be tempting to actually update the index at this point as2442 * well, using update_stages_for_stage_data(), but as per the big2443 * "NOTE" in update_stages(), doing so will modify the current2444 * in-memory index which will break calls to would_lose_untracked()2445 * that we need to make. Instead, we need to just make sure that2446 * the various handle_rename_*() functions update the index2447 * explicitly rather than relying on unpack_trees() to have done it.2448 */2449get_tree_entry(&tree->object.oid,2450 pair->two->path,2451&re->dst_entry->stages[stage].oid,2452&re->dst_entry->stages[stage].mode);24532454/* Update pair status */2455if(pair->status =='A') {2456/*2457 * Recording rename information for this add makes it look2458 * like a rename/delete conflict. Make sure we can2459 * correctly handle this as an add that was moved to a new2460 * directory instead of reporting a rename/delete conflict.2461 */2462 re->add_turned_into_rename =1;2463}2464/*2465 * We don't actually look at pair->status again, but it seems2466 * pedagogically correct to adjust it.2467 */2468 pair->status ='R';24692470/*2471 * Finally, record the new location.2472 */2473 pair->two->path = new_path;2474}24752476/*2477 * Get information of all renames which occurred in 'pairs', making use of2478 * any implicit directory renames inferred from the other side of history.2479 * We need the three trees in the merge ('o_tree', 'a_tree' and 'b_tree')2480 * to be able to associate the correct cache entries with the rename2481 * information; tree is always equal to either a_tree or b_tree.2482 */2483static struct string_list *get_renames(struct merge_options *o,2484struct diff_queue_struct *pairs,2485struct hashmap *dir_renames,2486struct hashmap *dir_rename_exclusions,2487struct tree *tree,2488struct tree *o_tree,2489struct tree *a_tree,2490struct tree *b_tree,2491struct string_list *entries,2492int*clean_merge)2493{2494int i;2495struct hashmap collisions;2496struct hashmap_iter iter;2497struct collision_entry *e;2498struct string_list *renames;24992500compute_collisions(&collisions, dir_renames, pairs);2501 renames =xcalloc(1,sizeof(struct string_list));25022503for(i =0; i < pairs->nr; ++i) {2504struct string_list_item *item;2505struct rename *re;2506struct diff_filepair *pair = pairs->queue[i];2507char*new_path;/* non-NULL only with directory renames */25082509if(pair->status !='A'&& pair->status !='R') {2510diff_free_filepair(pair);2511continue;2512}2513 new_path =check_for_directory_rename(o, pair->two->path, tree,2514 dir_renames,2515 dir_rename_exclusions,2516&collisions,2517 clean_merge);2518if(pair->status !='R'&& !new_path) {2519diff_free_filepair(pair);2520continue;2521}25222523 re =xmalloc(sizeof(*re));2524 re->processed =0;2525 re->add_turned_into_rename =0;2526 re->pair = pair;2527 item =string_list_lookup(entries, re->pair->one->path);2528if(!item)2529 re->src_entry =insert_stage_data(re->pair->one->path,2530 o_tree, a_tree, b_tree, entries);2531else2532 re->src_entry = item->util;25332534 item =string_list_lookup(entries, re->pair->two->path);2535if(!item)2536 re->dst_entry =insert_stage_data(re->pair->two->path,2537 o_tree, a_tree, b_tree, entries);2538else2539 re->dst_entry = item->util;2540 item =string_list_insert(renames, pair->one->path);2541 item->util = re;2542if(new_path)2543apply_directory_rename_modifications(o, pair, new_path,2544 re, tree, o_tree,2545 a_tree, b_tree,2546 entries,2547 clean_merge);2548}25492550hashmap_iter_init(&collisions, &iter);2551while((e =hashmap_iter_next(&iter))) {2552free(e->target_file);2553string_list_clear(&e->source_files,0);2554}2555hashmap_free(&collisions,1);2556return renames;2557}25582559static intprocess_renames(struct merge_options *o,2560struct string_list *a_renames,2561struct string_list *b_renames)2562{2563int clean_merge =1, i, j;2564struct string_list a_by_dst = STRING_LIST_INIT_NODUP;2565struct string_list b_by_dst = STRING_LIST_INIT_NODUP;2566const struct rename *sre;25672568for(i =0; i < a_renames->nr; i++) {2569 sre = a_renames->items[i].util;2570string_list_insert(&a_by_dst, sre->pair->two->path)->util2571= (void*)sre;2572}2573for(i =0; i < b_renames->nr; i++) {2574 sre = b_renames->items[i].util;2575string_list_insert(&b_by_dst, sre->pair->two->path)->util2576= (void*)sre;2577}25782579for(i =0, j =0; i < a_renames->nr || j < b_renames->nr;) {2580struct string_list *renames1, *renames2Dst;2581struct rename *ren1 = NULL, *ren2 = NULL;2582const char*branch1, *branch2;2583const char*ren1_src, *ren1_dst;2584struct string_list_item *lookup;25852586if(i >= a_renames->nr) {2587 ren2 = b_renames->items[j++].util;2588}else if(j >= b_renames->nr) {2589 ren1 = a_renames->items[i++].util;2590}else{2591int compare =strcmp(a_renames->items[i].string,2592 b_renames->items[j].string);2593if(compare <=0)2594 ren1 = a_renames->items[i++].util;2595if(compare >=0)2596 ren2 = b_renames->items[j++].util;2597}25982599/* TODO: refactor, so that 1/2 are not needed */2600if(ren1) {2601 renames1 = a_renames;2602 renames2Dst = &b_by_dst;2603 branch1 = o->branch1;2604 branch2 = o->branch2;2605}else{2606 renames1 = b_renames;2607 renames2Dst = &a_by_dst;2608 branch1 = o->branch2;2609 branch2 = o->branch1;2610SWAP(ren2, ren1);2611}26122613if(ren1->processed)2614continue;2615 ren1->processed =1;2616 ren1->dst_entry->processed =1;2617/* BUG: We should only mark src_entry as processed if we2618 * are not dealing with a rename + add-source case.2619 */2620 ren1->src_entry->processed =1;26212622 ren1_src = ren1->pair->one->path;2623 ren1_dst = ren1->pair->two->path;26242625if(ren2) {2626/* One file renamed on both sides */2627const char*ren2_src = ren2->pair->one->path;2628const char*ren2_dst = ren2->pair->two->path;2629enum rename_type rename_type;2630if(strcmp(ren1_src, ren2_src) !=0)2631BUG("ren1_src != ren2_src");2632 ren2->dst_entry->processed =1;2633 ren2->processed =1;2634if(strcmp(ren1_dst, ren2_dst) !=0) {2635 rename_type = RENAME_ONE_FILE_TO_TWO;2636 clean_merge =0;2637}else{2638 rename_type = RENAME_ONE_FILE_TO_ONE;2639/* BUG: We should only remove ren1_src in2640 * the base stage (think of rename +2641 * add-source cases).2642 */2643remove_file(o,1, ren1_src,1);2644update_entry(ren1->dst_entry,2645 ren1->pair->one,2646 ren1->pair->two,2647 ren2->pair->two);2648}2649setup_rename_conflict_info(rename_type,2650 ren1->pair,2651 ren2->pair,2652 branch1,2653 branch2,2654 ren1->dst_entry,2655 ren2->dst_entry,2656 o,2657 NULL,2658 NULL);2659}else if((lookup =string_list_lookup(renames2Dst, ren1_dst))) {2660/* Two different files renamed to the same thing */2661char*ren2_dst;2662 ren2 = lookup->util;2663 ren2_dst = ren2->pair->two->path;2664if(strcmp(ren1_dst, ren2_dst) !=0)2665BUG("ren1_dst != ren2_dst");26662667 clean_merge =0;2668 ren2->processed =1;2669/*2670 * BUG: We should only mark src_entry as processed2671 * if we are not dealing with a rename + add-source2672 * case.2673 */2674 ren2->src_entry->processed =1;26752676setup_rename_conflict_info(RENAME_TWO_FILES_TO_ONE,2677 ren1->pair,2678 ren2->pair,2679 branch1,2680 branch2,2681 ren1->dst_entry,2682 ren2->dst_entry,2683 o,2684 ren1->src_entry,2685 ren2->src_entry);26862687}else{2688/* Renamed in 1, maybe changed in 2 */2689/* we only use sha1 and mode of these */2690struct diff_filespec src_other, dst_other;2691int try_merge;26922693/*2694 * unpack_trees loads entries from common-commit2695 * into stage 1, from head-commit into stage 2, and2696 * from merge-commit into stage 3. We keep track2697 * of which side corresponds to the rename.2698 */2699int renamed_stage = a_renames == renames1 ?2:3;2700int other_stage = a_renames == renames1 ?3:2;27012702/* BUG: We should only remove ren1_src in the base2703 * stage and in other_stage (think of rename +2704 * add-source case).2705 */2706remove_file(o,1, ren1_src,2707 renamed_stage ==2|| !was_tracked(o, ren1_src));27082709oidcpy(&src_other.oid,2710&ren1->src_entry->stages[other_stage].oid);2711 src_other.mode = ren1->src_entry->stages[other_stage].mode;2712oidcpy(&dst_other.oid,2713&ren1->dst_entry->stages[other_stage].oid);2714 dst_other.mode = ren1->dst_entry->stages[other_stage].mode;2715 try_merge =0;27162717if(oid_eq(&src_other.oid, &null_oid) &&2718 ren1->add_turned_into_rename) {2719setup_rename_conflict_info(RENAME_VIA_DIR,2720 ren1->pair,2721 NULL,2722 branch1,2723 branch2,2724 ren1->dst_entry,2725 NULL,2726 o,2727 NULL,2728 NULL);2729}else if(oid_eq(&src_other.oid, &null_oid)) {2730setup_rename_conflict_info(RENAME_DELETE,2731 ren1->pair,2732 NULL,2733 branch1,2734 branch2,2735 ren1->dst_entry,2736 NULL,2737 o,2738 NULL,2739 NULL);2740}else if((dst_other.mode == ren1->pair->two->mode) &&2741oid_eq(&dst_other.oid, &ren1->pair->two->oid)) {2742/*2743 * Added file on the other side identical to2744 * the file being renamed: clean merge.2745 * Also, there is no need to overwrite the2746 * file already in the working copy, so call2747 * update_file_flags() instead of2748 * update_file().2749 */2750if(update_file_flags(o,2751&ren1->pair->two->oid,2752 ren1->pair->two->mode,2753 ren1_dst,27541,/* update_cache */27550/* update_wd */))2756 clean_merge = -1;2757}else if(!oid_eq(&dst_other.oid, &null_oid)) {2758 clean_merge =0;2759 try_merge =1;2760output(o,1,_("CONFLICT (rename/add): Rename%s->%sin%s. "2761"%sadded in%s"),2762 ren1_src, ren1_dst, branch1,2763 ren1_dst, branch2);2764if(o->call_depth) {2765struct merge_file_info mfi;2766if(merge_file_one(o, ren1_dst, &null_oid,0,2767&ren1->pair->two->oid,2768 ren1->pair->two->mode,2769&dst_other.oid,2770 dst_other.mode,2771 branch1, branch2, &mfi)) {2772 clean_merge = -1;2773goto cleanup_and_return;2774}2775output(o,1,_("Adding merged%s"), ren1_dst);2776if(update_file(o,0, &mfi.oid,2777 mfi.mode, ren1_dst))2778 clean_merge = -1;2779 try_merge =0;2780}else{2781char*new_path =unique_path(o, ren1_dst, branch2);2782output(o,1,_("Adding as%sinstead"), new_path);2783if(update_file(o,0, &dst_other.oid,2784 dst_other.mode, new_path))2785 clean_merge = -1;2786free(new_path);2787}2788}else2789 try_merge =1;27902791if(clean_merge <0)2792goto cleanup_and_return;2793if(try_merge) {2794struct diff_filespec *one, *a, *b;2795 src_other.path = (char*)ren1_src;27962797 one = ren1->pair->one;2798if(a_renames == renames1) {2799 a = ren1->pair->two;2800 b = &src_other;2801}else{2802 b = ren1->pair->two;2803 a = &src_other;2804}2805update_entry(ren1->dst_entry, one, a, b);2806setup_rename_conflict_info(RENAME_NORMAL,2807 ren1->pair,2808 NULL,2809 branch1,2810 NULL,2811 ren1->dst_entry,2812 NULL,2813 o,2814 NULL,2815 NULL);2816}2817}2818}2819cleanup_and_return:2820string_list_clear(&a_by_dst,0);2821string_list_clear(&b_by_dst,0);28222823return clean_merge;2824}28252826struct rename_info {2827struct string_list *head_renames;2828struct string_list *merge_renames;2829};28302831static voidinitial_cleanup_rename(struct diff_queue_struct *pairs,2832struct hashmap *dir_renames)2833{2834struct hashmap_iter iter;2835struct dir_rename_entry *e;28362837hashmap_iter_init(dir_renames, &iter);2838while((e =hashmap_iter_next(&iter))) {2839free(e->dir);2840strbuf_release(&e->new_dir);2841/* possible_new_dirs already cleared in get_directory_renames */2842}2843hashmap_free(dir_renames,1);2844free(dir_renames);28452846free(pairs->queue);2847free(pairs);2848}28492850static intdetect_and_process_renames(struct merge_options *o,2851struct tree *common,2852struct tree *head,2853struct tree *merge,2854struct string_list *entries,2855struct rename_info *ri)2856{2857struct diff_queue_struct *head_pairs, *merge_pairs;2858struct hashmap *dir_re_head, *dir_re_merge;2859int clean =1;28602861 ri->head_renames = NULL;2862 ri->merge_renames = NULL;28632864if(!merge_detect_rename(o))2865return1;28662867 head_pairs =get_diffpairs(o, common, head);2868 merge_pairs =get_diffpairs(o, common, merge);28692870 dir_re_head =get_directory_renames(head_pairs, head);2871 dir_re_merge =get_directory_renames(merge_pairs, merge);28722873handle_directory_level_conflicts(o,2874 dir_re_head, head,2875 dir_re_merge, merge);28762877 ri->head_renames =get_renames(o, head_pairs,2878 dir_re_merge, dir_re_head, head,2879 common, head, merge, entries,2880&clean);2881if(clean <0)2882goto cleanup;2883 ri->merge_renames =get_renames(o, merge_pairs,2884 dir_re_head, dir_re_merge, merge,2885 common, head, merge, entries,2886&clean);2887if(clean <0)2888goto cleanup;2889 clean &=process_renames(o, ri->head_renames, ri->merge_renames);28902891cleanup:2892/*2893 * Some cleanup is deferred until cleanup_renames() because the2894 * data structures are still needed and referenced in2895 * process_entry(). But there are a few things we can free now.2896 */2897initial_cleanup_rename(head_pairs, dir_re_head);2898initial_cleanup_rename(merge_pairs, dir_re_merge);28992900return clean;2901}29022903static voidfinal_cleanup_rename(struct string_list *rename)2904{2905const struct rename *re;2906int i;29072908if(rename == NULL)2909return;29102911for(i =0; i < rename->nr; i++) {2912 re = rename->items[i].util;2913diff_free_filepair(re->pair);2914}2915string_list_clear(rename,1);2916free(rename);2917}29182919static voidfinal_cleanup_renames(struct rename_info *re_info)2920{2921final_cleanup_rename(re_info->head_renames);2922final_cleanup_rename(re_info->merge_renames);2923}29242925static struct object_id *stage_oid(const struct object_id *oid,unsigned mode)2926{2927return(is_null_oid(oid) || mode ==0) ? NULL: (struct object_id *)oid;2928}29292930static intread_oid_strbuf(struct merge_options *o,2931const struct object_id *oid,2932struct strbuf *dst)2933{2934void*buf;2935enum object_type type;2936unsigned long size;2937 buf =read_object_file(oid, &type, &size);2938if(!buf)2939returnerr(o,_("cannot read object%s"),oid_to_hex(oid));2940if(type != OBJ_BLOB) {2941free(buf);2942returnerr(o,_("object%sis not a blob"),oid_to_hex(oid));2943}2944strbuf_attach(dst, buf, size, size +1);2945return0;2946}29472948static intblob_unchanged(struct merge_options *opt,2949const struct object_id *o_oid,2950unsigned o_mode,2951const struct object_id *a_oid,2952unsigned a_mode,2953int renormalize,const char*path)2954{2955struct strbuf o = STRBUF_INIT;2956struct strbuf a = STRBUF_INIT;2957int ret =0;/* assume changed for safety */29582959if(a_mode != o_mode)2960return0;2961if(oid_eq(o_oid, a_oid))2962return1;2963if(!renormalize)2964return0;29652966assert(o_oid && a_oid);2967if(read_oid_strbuf(opt, o_oid, &o) ||read_oid_strbuf(opt, a_oid, &a))2968goto error_return;2969/*2970 * Note: binary | is used so that both renormalizations are2971 * performed. Comparison can be skipped if both files are2972 * unchanged since their sha1s have already been compared.2973 */2974if(renormalize_buffer(&the_index, path, o.buf, o.len, &o) |2975renormalize_buffer(&the_index, path, a.buf, a.len, &a))2976 ret = (o.len == a.len && !memcmp(o.buf, a.buf, o.len));29772978error_return:2979strbuf_release(&o);2980strbuf_release(&a);2981return ret;2982}29832984static inthandle_modify_delete(struct merge_options *o,2985const char*path,2986struct object_id *o_oid,int o_mode,2987struct object_id *a_oid,int a_mode,2988struct object_id *b_oid,int b_mode)2989{2990const char*modify_branch, *delete_branch;2991struct object_id *changed_oid;2992int changed_mode;29932994if(a_oid) {2995 modify_branch = o->branch1;2996 delete_branch = o->branch2;2997 changed_oid = a_oid;2998 changed_mode = a_mode;2999}else{3000 modify_branch = o->branch2;3001 delete_branch = o->branch1;3002 changed_oid = b_oid;3003 changed_mode = b_mode;3004}30053006returnhandle_change_delete(o,3007 path, NULL,3008 o_oid, o_mode,3009 changed_oid, changed_mode,3010 modify_branch, delete_branch,3011_("modify"),_("modified"));3012}30133014static intmerge_content(struct merge_options *o,3015const char*path,3016int is_dirty,3017struct object_id *o_oid,int o_mode,3018struct object_id *a_oid,int a_mode,3019struct object_id *b_oid,int b_mode,3020struct rename_conflict_info *rename_conflict_info)3021{3022const char*reason =_("content");3023const char*path1 = NULL, *path2 = NULL;3024struct merge_file_info mfi;3025struct diff_filespec one, a, b;3026unsigned df_conflict_remains =0;30273028if(!o_oid) {3029 reason =_("add/add");3030 o_oid = (struct object_id *)&null_oid;3031}3032 one.path = a.path = b.path = (char*)path;3033oidcpy(&one.oid, o_oid);3034 one.mode = o_mode;3035oidcpy(&a.oid, a_oid);3036 a.mode = a_mode;3037oidcpy(&b.oid, b_oid);3038 b.mode = b_mode;30393040if(rename_conflict_info) {3041struct diff_filepair *pair1 = rename_conflict_info->pair1;30423043 path1 = (o->branch1 == rename_conflict_info->branch1) ?3044 pair1->two->path : pair1->one->path;3045/* If rename_conflict_info->pair2 != NULL, we are in3046 * RENAME_ONE_FILE_TO_ONE case. Otherwise, we have a3047 * normal rename.3048 */3049 path2 = (rename_conflict_info->pair2 ||3050 o->branch2 == rename_conflict_info->branch1) ?3051 pair1->two->path : pair1->one->path;30523053if(dir_in_way(path, !o->call_depth,3054S_ISGITLINK(pair1->two->mode)))3055 df_conflict_remains =1;3056}3057if(merge_file_special_markers(o, &one, &a, &b, path,3058 o->branch1, path1,3059 o->branch2, path2, &mfi))3060return-1;30613062/*3063 * We can skip updating the working tree file iff:3064 * a) The merge is clean3065 * b) The merge matches what was in HEAD (content, mode, pathname)3066 * c) The target path is usable (i.e. not involved in D/F conflict)3067 */3068if(mfi.clean &&3069was_tracked_and_matches(o, path, &mfi.oid, mfi.mode) &&3070!df_conflict_remains) {3071output(o,3,_("Skipped%s(merged same as existing)"), path);3072if(add_cacheinfo(o, mfi.mode, &mfi.oid, path,30730, (!o->call_depth && !is_dirty),0))3074return-1;3075return mfi.clean;3076}30773078if(!mfi.clean) {3079if(S_ISGITLINK(mfi.mode))3080 reason =_("submodule");3081output(o,1,_("CONFLICT (%s): Merge conflict in%s"),3082 reason, path);3083if(rename_conflict_info && !df_conflict_remains)3084if(update_stages(o, path, &one, &a, &b))3085return-1;3086}30873088if(df_conflict_remains || is_dirty) {3089char*new_path;3090if(o->call_depth) {3091remove_file_from_cache(path);3092}else{3093if(!mfi.clean) {3094if(update_stages(o, path, &one, &a, &b))3095return-1;3096}else{3097int file_from_stage2 =was_tracked(o, path);3098struct diff_filespec merged;3099oidcpy(&merged.oid, &mfi.oid);3100 merged.mode = mfi.mode;31013102if(update_stages(o, path, NULL,3103 file_from_stage2 ? &merged : NULL,3104 file_from_stage2 ? NULL : &merged))3105return-1;3106}31073108}3109 new_path =unique_path(o, path, rename_conflict_info->branch1);3110if(is_dirty) {3111output(o,1,_("Refusing to lose dirty file at%s"),3112 path);3113}3114output(o,1,_("Adding as%sinstead"), new_path);3115if(update_file(o,0, &mfi.oid, mfi.mode, new_path)) {3116free(new_path);3117return-1;3118}3119free(new_path);3120 mfi.clean =0;3121}else if(update_file(o, mfi.clean, &mfi.oid, mfi.mode, path))3122return-1;3123return!is_dirty && mfi.clean;3124}31253126static inthandle_rename_normal(struct merge_options *o,3127const char*path,3128struct object_id *o_oid,unsigned int o_mode,3129struct object_id *a_oid,unsigned int a_mode,3130struct object_id *b_oid,unsigned int b_mode,3131struct rename_conflict_info *ci)3132{3133/* Merge the content and write it out */3134returnmerge_content(o, path,was_dirty(o, path),3135 o_oid, o_mode, a_oid, a_mode, b_oid, b_mode,3136 ci);3137}31383139/* Per entry merge function */3140static intprocess_entry(struct merge_options *o,3141const char*path,struct stage_data *entry)3142{3143int clean_merge =1;3144int normalize = o->renormalize;3145unsigned o_mode = entry->stages[1].mode;3146unsigned a_mode = entry->stages[2].mode;3147unsigned b_mode = entry->stages[3].mode;3148struct object_id *o_oid =stage_oid(&entry->stages[1].oid, o_mode);3149struct object_id *a_oid =stage_oid(&entry->stages[2].oid, a_mode);3150struct object_id *b_oid =stage_oid(&entry->stages[3].oid, b_mode);31513152 entry->processed =1;3153if(entry->rename_conflict_info) {3154struct rename_conflict_info *conflict_info = entry->rename_conflict_info;3155switch(conflict_info->rename_type) {3156case RENAME_NORMAL:3157case RENAME_ONE_FILE_TO_ONE:3158 clean_merge =handle_rename_normal(o,3159 path,3160 o_oid, o_mode,3161 a_oid, a_mode,3162 b_oid, b_mode,3163 conflict_info);3164break;3165case RENAME_VIA_DIR:3166 clean_merge =1;3167if(handle_rename_via_dir(o,3168 conflict_info->pair1,3169 conflict_info->branch1,3170 conflict_info->branch2))3171 clean_merge = -1;3172break;3173case RENAME_DELETE:3174 clean_merge =0;3175if(handle_rename_delete(o,3176 conflict_info->pair1,3177 conflict_info->branch1,3178 conflict_info->branch2))3179 clean_merge = -1;3180break;3181case RENAME_ONE_FILE_TO_TWO:3182 clean_merge =0;3183if(handle_rename_rename_1to2(o, conflict_info))3184 clean_merge = -1;3185break;3186case RENAME_TWO_FILES_TO_ONE:3187 clean_merge =0;3188if(handle_rename_rename_2to1(o, conflict_info))3189 clean_merge = -1;3190break;3191default:3192 entry->processed =0;3193break;3194}3195}else if(o_oid && (!a_oid || !b_oid)) {3196/* Case A: Deleted in one */3197if((!a_oid && !b_oid) ||3198(!b_oid &&blob_unchanged(o, o_oid, o_mode, a_oid, a_mode, normalize, path)) ||3199(!a_oid &&blob_unchanged(o, o_oid, o_mode, b_oid, b_mode, normalize, path))) {3200/* Deleted in both or deleted in one and3201 * unchanged in the other */3202if(a_oid)3203output(o,2,_("Removing%s"), path);3204/* do not touch working file if it did not exist */3205remove_file(o,1, path, !a_oid);3206}else{3207/* Modify/delete; deleted side may have put a directory in the way */3208 clean_merge =0;3209if(handle_modify_delete(o, path, o_oid, o_mode,3210 a_oid, a_mode, b_oid, b_mode))3211 clean_merge = -1;3212}3213}else if((!o_oid && a_oid && !b_oid) ||3214(!o_oid && !a_oid && b_oid)) {3215/* Case B: Added in one. */3216/* [nothing|directory] -> ([nothing|directory], file) */32173218const char*add_branch;3219const char*other_branch;3220unsigned mode;3221const struct object_id *oid;3222const char*conf;32233224if(a_oid) {3225 add_branch = o->branch1;3226 other_branch = o->branch2;3227 mode = a_mode;3228 oid = a_oid;3229 conf =_("file/directory");3230}else{3231 add_branch = o->branch2;3232 other_branch = o->branch1;3233 mode = b_mode;3234 oid = b_oid;3235 conf =_("directory/file");3236}3237if(dir_in_way(path,3238!o->call_depth && !S_ISGITLINK(a_mode),32390)) {3240char*new_path =unique_path(o, path, add_branch);3241 clean_merge =0;3242output(o,1,_("CONFLICT (%s): There is a directory with name%sin%s. "3243"Adding%sas%s"),3244 conf, path, other_branch, path, new_path);3245if(update_file(o,0, oid, mode, new_path))3246 clean_merge = -1;3247else if(o->call_depth)3248remove_file_from_cache(path);3249free(new_path);3250}else{3251output(o,2,_("Adding%s"), path);3252/* do not overwrite file if already present */3253if(update_file_flags(o, oid, mode, path,1, !a_oid))3254 clean_merge = -1;3255}3256}else if(a_oid && b_oid) {3257/* Case C: Added in both (check for same permissions) and */3258/* case D: Modified in both, but differently. */3259int is_dirty =0;/* unpack_trees would have bailed if dirty */3260 clean_merge =merge_content(o, path, is_dirty,3261 o_oid, o_mode, a_oid, a_mode, b_oid, b_mode,3262 NULL);3263}else if(!o_oid && !a_oid && !b_oid) {3264/*3265 * this entry was deleted altogether. a_mode == 0 means3266 * we had that path and want to actively remove it.3267 */3268remove_file(o,1, path, !a_mode);3269}else3270BUG("fatal merge failure, shouldn't happen.");32713272return clean_merge;3273}32743275intmerge_trees(struct merge_options *o,3276struct tree *head,3277struct tree *merge,3278struct tree *common,3279struct tree **result)3280{3281int code, clean;32823283if(o->subtree_shift) {3284 merge =shift_tree_object(head, merge, o->subtree_shift);3285 common =shift_tree_object(head, common, o->subtree_shift);3286}32873288if(oid_eq(&common->object.oid, &merge->object.oid)) {3289struct strbuf sb = STRBUF_INIT;32903291if(!o->call_depth &&index_has_changes(&sb)) {3292err(o,_("Dirty index: cannot merge (dirty:%s)"),3293 sb.buf);3294return0;3295}3296output(o,0,_("Already up to date!"));3297*result = head;3298return1;3299}33003301 code =unpack_trees_start(o, common, head, merge);33023303if(code !=0) {3304if(show(o,4) || o->call_depth)3305err(o,_("merging of trees%sand%sfailed"),3306oid_to_hex(&head->object.oid),3307oid_to_hex(&merge->object.oid));3308unpack_trees_finish(o);3309return-1;3310}33113312if(unmerged_cache()) {3313struct string_list *entries;3314struct rename_info re_info;3315int i;3316/*3317 * Only need the hashmap while processing entries, so3318 * initialize it here and free it when we are done running3319 * through the entries. Keeping it in the merge_options as3320 * opposed to decaring a local hashmap is for convenience3321 * so that we don't have to pass it to around.3322 */3323hashmap_init(&o->current_file_dir_set, path_hashmap_cmp, NULL,512);3324get_files_dirs(o, head);3325get_files_dirs(o, merge);33263327 entries =get_unmerged();3328 clean =detect_and_process_renames(o, common, head, merge,3329 entries, &re_info);3330record_df_conflict_files(o, entries);3331if(clean <0)3332goto cleanup;3333for(i = entries->nr-1;0<= i; i--) {3334const char*path = entries->items[i].string;3335struct stage_data *e = entries->items[i].util;3336if(!e->processed) {3337int ret =process_entry(o, path, e);3338if(!ret)3339 clean =0;3340else if(ret <0) {3341 clean = ret;3342goto cleanup;3343}3344}3345}3346for(i =0; i < entries->nr; i++) {3347struct stage_data *e = entries->items[i].util;3348if(!e->processed)3349BUG("unprocessed path???%s",3350 entries->items[i].string);3351}33523353 cleanup:3354final_cleanup_renames(&re_info);33553356string_list_clear(entries,1);3357free(entries);33583359hashmap_free(&o->current_file_dir_set,1);33603361if(clean <0) {3362unpack_trees_finish(o);3363return clean;3364}3365}3366else3367 clean =1;33683369unpack_trees_finish(o);33703371if(o->call_depth && !(*result =write_tree_from_memory(o)))3372return-1;33733374return clean;3375}33763377static struct commit_list *reverse_commit_list(struct commit_list *list)3378{3379struct commit_list *next = NULL, *current, *backup;3380for(current = list; current; current = backup) {3381 backup = current->next;3382 current->next = next;3383 next = current;3384}3385return next;3386}33873388/*3389 * Merge the commits h1 and h2, return the resulting virtual3390 * commit object and a flag indicating the cleanness of the merge.3391 */3392intmerge_recursive(struct merge_options *o,3393struct commit *h1,3394struct commit *h2,3395struct commit_list *ca,3396struct commit **result)3397{3398struct commit_list *iter;3399struct commit *merged_common_ancestors;3400struct tree *mrtree;3401int clean;34023403if(show(o,4)) {3404output(o,4,_("Merging:"));3405output_commit_title(o, h1);3406output_commit_title(o, h2);3407}34083409if(!ca) {3410 ca =get_merge_bases(h1, h2);3411 ca =reverse_commit_list(ca);3412}34133414if(show(o,5)) {3415unsigned cnt =commit_list_count(ca);34163417output(o,5,Q_("found%ucommon ancestor:",3418"found%ucommon ancestors:", cnt), cnt);3419for(iter = ca; iter; iter = iter->next)3420output_commit_title(o, iter->item);3421}34223423 merged_common_ancestors =pop_commit(&ca);3424if(merged_common_ancestors == NULL) {3425/* if there is no common ancestor, use an empty tree */3426struct tree *tree;34273428 tree =lookup_tree(the_hash_algo->empty_tree);3429 merged_common_ancestors =make_virtual_commit(tree,"ancestor");3430}34313432for(iter = ca; iter; iter = iter->next) {3433const char*saved_b1, *saved_b2;3434 o->call_depth++;3435/*3436 * When the merge fails, the result contains files3437 * with conflict markers. The cleanness flag is3438 * ignored (unless indicating an error), it was never3439 * actually used, as result of merge_trees has always3440 * overwritten it: the committed "conflicts" were3441 * already resolved.3442 */3443discard_cache();3444 saved_b1 = o->branch1;3445 saved_b2 = o->branch2;3446 o->branch1 ="Temporary merge branch 1";3447 o->branch2 ="Temporary merge branch 2";3448if(merge_recursive(o, merged_common_ancestors, iter->item,3449 NULL, &merged_common_ancestors) <0)3450return-1;3451 o->branch1 = saved_b1;3452 o->branch2 = saved_b2;3453 o->call_depth--;34543455if(!merged_common_ancestors)3456returnerr(o,_("merge returned no commit"));3457}34583459discard_cache();3460if(!o->call_depth)3461read_cache();34623463 o->ancestor ="merged common ancestors";3464 clean =merge_trees(o,get_commit_tree(h1),get_commit_tree(h2),3465get_commit_tree(merged_common_ancestors),3466&mrtree);3467if(clean <0) {3468flush_output(o);3469return clean;3470}34713472if(o->call_depth) {3473*result =make_virtual_commit(mrtree,"merged tree");3474commit_list_insert(h1, &(*result)->parents);3475commit_list_insert(h2, &(*result)->parents->next);3476}3477flush_output(o);3478if(!o->call_depth && o->buffer_output <2)3479strbuf_release(&o->obuf);3480if(show(o,2))3481diff_warn_rename_limit("merge.renamelimit",3482 o->needed_rename_limit,0);3483return clean;3484}34853486static struct commit *get_ref(const struct object_id *oid,const char*name)3487{3488struct object *object;34893490 object =deref_tag(parse_object(oid), name,strlen(name));3491if(!object)3492return NULL;3493if(object->type == OBJ_TREE)3494returnmake_virtual_commit((struct tree*)object, name);3495if(object->type != OBJ_COMMIT)3496return NULL;3497if(parse_commit((struct commit *)object))3498return NULL;3499return(struct commit *)object;3500}35013502intmerge_recursive_generic(struct merge_options *o,3503const struct object_id *head,3504const struct object_id *merge,3505int num_base_list,3506const struct object_id **base_list,3507struct commit **result)3508{3509int clean;3510struct lock_file lock = LOCK_INIT;3511struct commit *head_commit =get_ref(head, o->branch1);3512struct commit *next_commit =get_ref(merge, o->branch2);3513struct commit_list *ca = NULL;35143515if(base_list) {3516int i;3517for(i =0; i < num_base_list; ++i) {3518struct commit *base;3519if(!(base =get_ref(base_list[i],oid_to_hex(base_list[i]))))3520returnerr(o,_("Could not parse object '%s'"),3521oid_to_hex(base_list[i]));3522commit_list_insert(base, &ca);3523}3524}35253526hold_locked_index(&lock, LOCK_DIE_ON_ERROR);3527 clean =merge_recursive(o, head_commit, next_commit, ca,3528 result);3529if(clean <0) {3530rollback_lock_file(&lock);3531return clean;3532}35333534if(write_locked_index(&the_index, &lock,3535 COMMIT_LOCK | SKIP_IF_UNCHANGED))3536returnerr(o,_("Unable to write index."));35373538return clean ?0:1;3539}35403541static voidmerge_recursive_config(struct merge_options *o)3542{3543char*value = NULL;3544git_config_get_int("merge.verbosity", &o->verbosity);3545git_config_get_int("diff.renamelimit", &o->diff_rename_limit);3546git_config_get_int("merge.renamelimit", &o->merge_rename_limit);3547if(!git_config_get_string("diff.renames", &value)) {3548 o->diff_detect_rename =git_config_rename("diff.renames", value);3549free(value);3550}3551if(!git_config_get_string("merge.renames", &value)) {3552 o->merge_detect_rename =git_config_rename("merge.renames", value);3553free(value);3554}3555git_config(git_xmerge_config, NULL);3556}35573558voidinit_merge_options(struct merge_options *o)3559{3560const char*merge_verbosity;3561memset(o,0,sizeof(struct merge_options));3562 o->verbosity =2;3563 o->buffer_output =1;3564 o->diff_rename_limit = -1;3565 o->merge_rename_limit = -1;3566 o->renormalize =0;3567 o->diff_detect_rename = -1;3568 o->merge_detect_rename = -1;3569merge_recursive_config(o);3570 merge_verbosity =getenv("GIT_MERGE_VERBOSITY");3571if(merge_verbosity)3572 o->verbosity =strtol(merge_verbosity, NULL,10);3573if(o->verbosity >=5)3574 o->buffer_output =0;3575strbuf_init(&o->obuf,0);3576string_list_init(&o->df_conflict_file_set,1);3577}35783579intparse_merge_opt(struct merge_options *o,const char*s)3580{3581const char*arg;35823583if(!s || !*s)3584return-1;3585if(!strcmp(s,"ours"))3586 o->recursive_variant = MERGE_RECURSIVE_OURS;3587else if(!strcmp(s,"theirs"))3588 o->recursive_variant = MERGE_RECURSIVE_THEIRS;3589else if(!strcmp(s,"subtree"))3590 o->subtree_shift ="";3591else if(skip_prefix(s,"subtree=", &arg))3592 o->subtree_shift = arg;3593else if(!strcmp(s,"patience"))3594 o->xdl_opts =DIFF_WITH_ALG(o, PATIENCE_DIFF);3595else if(!strcmp(s,"histogram"))3596 o->xdl_opts =DIFF_WITH_ALG(o, HISTOGRAM_DIFF);3597else if(skip_prefix(s,"diff-algorithm=", &arg)) {3598long value =parse_algorithm_value(arg);3599if(value <0)3600return-1;3601/* clear out previous settings */3602DIFF_XDL_CLR(o, NEED_MINIMAL);3603 o->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;3604 o->xdl_opts |= value;3605}3606else if(!strcmp(s,"ignore-space-change"))3607DIFF_XDL_SET(o, IGNORE_WHITESPACE_CHANGE);3608else if(!strcmp(s,"ignore-all-space"))3609DIFF_XDL_SET(o, IGNORE_WHITESPACE);3610else if(!strcmp(s,"ignore-space-at-eol"))3611DIFF_XDL_SET(o, IGNORE_WHITESPACE_AT_EOL);3612else if(!strcmp(s,"ignore-cr-at-eol"))3613DIFF_XDL_SET(o, IGNORE_CR_AT_EOL);3614else if(!strcmp(s,"renormalize"))3615 o->renormalize =1;3616else if(!strcmp(s,"no-renormalize"))3617 o->renormalize =0;3618else if(!strcmp(s,"no-renames"))3619 o->merge_detect_rename =0;3620else if(!strcmp(s,"find-renames")) {3621 o->merge_detect_rename =1;3622 o->rename_score =0;3623}3624else if(skip_prefix(s,"find-renames=", &arg) ||3625skip_prefix(s,"rename-threshold=", &arg)) {3626if((o->rename_score =parse_rename_score(&arg)) == -1|| *arg !=0)3627return-1;3628 o->merge_detect_rename =1;3629}3630else3631return-1;3632return0;3633}