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"object-store.h" 12#include"repository.h" 13#include"commit.h" 14#include"blob.h" 15#include"builtin.h" 16#include"tree-walk.h" 17#include"diff.h" 18#include"diffcore.h" 19#include"tag.h" 20#include"alloc.h" 21#include"unpack-trees.h" 22#include"string-list.h" 23#include"xdiff-interface.h" 24#include"ll-merge.h" 25#include"attr.h" 26#include"merge-recursive.h" 27#include"dir.h" 28#include"submodule.h" 29#include"revision.h" 30#include"commit-reach.h" 31 32struct path_hashmap_entry { 33struct hashmap_entry e; 34char path[FLEX_ARRAY]; 35}; 36 37static intpath_hashmap_cmp(const void*cmp_data, 38const void*entry, 39const void*entry_or_key, 40const void*keydata) 41{ 42const struct path_hashmap_entry *a = entry; 43const struct path_hashmap_entry *b = entry_or_key; 44const char*key = keydata; 45 46if(ignore_case) 47returnstrcasecmp(a->path, key ? key : b->path); 48else 49returnstrcmp(a->path, key ? key : b->path); 50} 51 52static unsigned intpath_hash(const char*path) 53{ 54return ignore_case ?strihash(path) :strhash(path); 55} 56 57static struct dir_rename_entry *dir_rename_find_entry(struct hashmap *hashmap, 58char*dir) 59{ 60struct dir_rename_entry key; 61 62if(dir == NULL) 63return NULL; 64hashmap_entry_init(&key,strhash(dir)); 65 key.dir = dir; 66returnhashmap_get(hashmap, &key, NULL); 67} 68 69static intdir_rename_cmp(const void*unused_cmp_data, 70const void*entry, 71const void*entry_or_key, 72const void*unused_keydata) 73{ 74const struct dir_rename_entry *e1 = entry; 75const struct dir_rename_entry *e2 = entry_or_key; 76 77returnstrcmp(e1->dir, e2->dir); 78} 79 80static voiddir_rename_init(struct hashmap *map) 81{ 82hashmap_init(map, dir_rename_cmp, NULL,0); 83} 84 85static voiddir_rename_entry_init(struct dir_rename_entry *entry, 86char*directory) 87{ 88hashmap_entry_init(entry,strhash(directory)); 89 entry->dir = directory; 90 entry->non_unique_new_dir =0; 91strbuf_init(&entry->new_dir,0); 92string_list_init(&entry->possible_new_dirs,0); 93} 94 95static struct collision_entry *collision_find_entry(struct hashmap *hashmap, 96char*target_file) 97{ 98struct collision_entry key; 99 100hashmap_entry_init(&key,strhash(target_file)); 101 key.target_file = target_file; 102returnhashmap_get(hashmap, &key, NULL); 103} 104 105static intcollision_cmp(void*unused_cmp_data, 106const struct collision_entry *e1, 107const struct collision_entry *e2, 108const void*unused_keydata) 109{ 110returnstrcmp(e1->target_file, e2->target_file); 111} 112 113static voidcollision_init(struct hashmap *map) 114{ 115hashmap_init(map, (hashmap_cmp_fn) collision_cmp, NULL,0); 116} 117 118static voidflush_output(struct merge_options *opt) 119{ 120if(opt->buffer_output <2&& opt->obuf.len) { 121fputs(opt->obuf.buf, stdout); 122strbuf_reset(&opt->obuf); 123} 124} 125 126static interr(struct merge_options *opt,const char*err, ...) 127{ 128va_list params; 129 130if(opt->buffer_output <2) 131flush_output(opt); 132else{ 133strbuf_complete(&opt->obuf,'\n'); 134strbuf_addstr(&opt->obuf,"error: "); 135} 136va_start(params, err); 137strbuf_vaddf(&opt->obuf, err, params); 138va_end(params); 139if(opt->buffer_output >1) 140strbuf_addch(&opt->obuf,'\n'); 141else{ 142error("%s", opt->obuf.buf); 143strbuf_reset(&opt->obuf); 144} 145 146return-1; 147} 148 149static struct tree *shift_tree_object(struct repository *repo, 150struct tree *one,struct tree *two, 151const char*subtree_shift) 152{ 153struct object_id shifted; 154 155if(!*subtree_shift) { 156shift_tree(&one->object.oid, &two->object.oid, &shifted,0); 157}else{ 158shift_tree_by(&one->object.oid, &two->object.oid, &shifted, 159 subtree_shift); 160} 161if(oideq(&two->object.oid, &shifted)) 162return two; 163returnlookup_tree(repo, &shifted); 164} 165 166static struct commit *make_virtual_commit(struct repository *repo, 167struct tree *tree, 168const char*comment) 169{ 170struct commit *commit =alloc_commit_node(repo); 171 172set_merge_remote_desc(commit, comment, (struct object *)commit); 173 commit->maybe_tree = tree; 174 commit->object.parsed =1; 175return commit; 176} 177 178/* 179 * Since we use get_tree_entry(), which does not put the read object into 180 * the object pool, we cannot rely on a == b. 181 */ 182static intoid_eq(const struct object_id *a,const struct object_id *b) 183{ 184if(!a && !b) 185return2; 186return a && b &&oideq(a, b); 187} 188 189enum rename_type { 190 RENAME_NORMAL =0, 191 RENAME_VIA_DIR, 192 RENAME_ADD, 193 RENAME_DELETE, 194 RENAME_ONE_FILE_TO_ONE, 195 RENAME_ONE_FILE_TO_TWO, 196 RENAME_TWO_FILES_TO_ONE 197}; 198 199/* 200 * Since we want to write the index eventually, we cannot reuse the index 201 * for these (temporary) data. 202 */ 203struct stage_data { 204struct diff_filespec stages[4];/* mostly for oid & mode; maybe path */ 205struct rename_conflict_info *rename_conflict_info; 206unsigned processed:1; 207}; 208 209struct rename { 210unsigned processed:1; 211struct diff_filepair *pair; 212const char*branch;/* branch that the rename occurred on */ 213/* 214 * If directory rename detection affected this rename, what was its 215 * original type ('A' or 'R') and it's original destination before 216 * the directory rename (otherwise, '\0' and NULL for these two vars). 217 */ 218char dir_rename_original_type; 219char*dir_rename_original_dest; 220/* 221 * Purpose of src_entry and dst_entry: 222 * 223 * If 'before' is renamed to 'after' then src_entry will contain 224 * the versions of 'before' from the merge_base, HEAD, and MERGE in 225 * stages 1, 2, and 3; dst_entry will contain the respective 226 * versions of 'after' in corresponding locations. Thus, we have a 227 * total of six modes and oids, though some will be null. (Stage 0 228 * is ignored; we're interested in handling conflicts.) 229 * 230 * Since we don't turn on break-rewrites by default, neither 231 * src_entry nor dst_entry can have all three of their stages have 232 * non-null oids, meaning at most four of the six will be non-null. 233 * Also, since this is a rename, both src_entry and dst_entry will 234 * have at least one non-null oid, meaning at least two will be 235 * non-null. Of the six oids, a typical rename will have three be 236 * non-null. Only two implies a rename/delete, and four implies a 237 * rename/add. 238 */ 239struct stage_data *src_entry; 240struct stage_data *dst_entry; 241}; 242 243struct rename_conflict_info { 244enum rename_type rename_type; 245struct rename *ren1; 246struct rename *ren2; 247}; 248 249staticinlinevoidsetup_rename_conflict_info(enum rename_type rename_type, 250struct merge_options *opt, 251struct rename *ren1, 252struct rename *ren2) 253{ 254struct rename_conflict_info *ci; 255 256/* 257 * When we have two renames involved, it's easiest to get the 258 * correct things into stage 2 and 3, and to make sure that the 259 * content merge puts HEAD before the other branch if we just 260 * ensure that branch1 == opt->branch1. So, simply flip arguments 261 * around if we don't have that. 262 */ 263if(ren2 && ren1->branch != opt->branch1) { 264setup_rename_conflict_info(rename_type, opt, ren2, ren1); 265return; 266} 267 268 ci =xcalloc(1,sizeof(struct rename_conflict_info)); 269 ci->rename_type = rename_type; 270 ci->ren1 = ren1; 271 ci->ren2 = ren2; 272 273 ci->ren1->dst_entry->processed =0; 274 ci->ren1->dst_entry->rename_conflict_info = ci; 275if(ren2) { 276 ci->ren2->dst_entry->rename_conflict_info = ci; 277} 278} 279 280static intshow(struct merge_options *opt,int v) 281{ 282return(!opt->call_depth && opt->verbosity >= v) || opt->verbosity >=5; 283} 284 285__attribute__((format(printf,3,4))) 286static voidoutput(struct merge_options *opt,int v,const char*fmt, ...) 287{ 288va_list ap; 289 290if(!show(opt, v)) 291return; 292 293strbuf_addchars(&opt->obuf,' ', opt->call_depth *2); 294 295va_start(ap, fmt); 296strbuf_vaddf(&opt->obuf, fmt, ap); 297va_end(ap); 298 299strbuf_addch(&opt->obuf,'\n'); 300if(!opt->buffer_output) 301flush_output(opt); 302} 303 304static voidoutput_commit_title(struct merge_options *opt,struct commit *commit) 305{ 306struct merge_remote_desc *desc; 307 308strbuf_addchars(&opt->obuf,' ', opt->call_depth *2); 309 desc =merge_remote_util(commit); 310if(desc) 311strbuf_addf(&opt->obuf,"virtual%s\n", desc->name); 312else{ 313strbuf_add_unique_abbrev(&opt->obuf, &commit->object.oid, 314 DEFAULT_ABBREV); 315strbuf_addch(&opt->obuf,' '); 316if(parse_commit(commit) !=0) 317strbuf_addstr(&opt->obuf,_("(bad commit)\n")); 318else{ 319const char*title; 320const char*msg =get_commit_buffer(commit, NULL); 321int len =find_commit_subject(msg, &title); 322if(len) 323strbuf_addf(&opt->obuf,"%.*s\n", len, title); 324unuse_commit_buffer(commit, msg); 325} 326} 327flush_output(opt); 328} 329 330static intadd_cacheinfo(struct merge_options *opt, 331const struct diff_filespec *blob, 332const char*path,int stage,int refresh,int options) 333{ 334struct index_state *istate = opt->repo->index; 335struct cache_entry *ce; 336int ret; 337 338 ce =make_cache_entry(istate, blob->mode, &blob->oid, path, stage,0); 339if(!ce) 340returnerr(opt,_("add_cacheinfo failed for path '%s'; merge aborting."), path); 341 342 ret =add_index_entry(istate, ce, options); 343if(refresh) { 344struct cache_entry *nce; 345 346 nce =refresh_cache_entry(istate, ce, 347 CE_MATCH_REFRESH | CE_MATCH_IGNORE_MISSING); 348if(!nce) 349returnerr(opt,_("add_cacheinfo failed to refresh for path '%s'; merge aborting."), path); 350if(nce != ce) 351 ret =add_index_entry(istate, nce, options); 352} 353return ret; 354} 355 356static voidinit_tree_desc_from_tree(struct tree_desc *desc,struct tree *tree) 357{ 358parse_tree(tree); 359init_tree_desc(desc, tree->buffer, tree->size); 360} 361 362static intunpack_trees_start(struct merge_options *opt, 363struct tree *common, 364struct tree *head, 365struct tree *merge) 366{ 367int rc; 368struct tree_desc t[3]; 369struct index_state tmp_index = { NULL }; 370 371memset(&opt->unpack_opts,0,sizeof(opt->unpack_opts)); 372if(opt->call_depth) 373 opt->unpack_opts.index_only =1; 374else 375 opt->unpack_opts.update =1; 376 opt->unpack_opts.merge =1; 377 opt->unpack_opts.head_idx =2; 378 opt->unpack_opts.fn = threeway_merge; 379 opt->unpack_opts.src_index = opt->repo->index; 380 opt->unpack_opts.dst_index = &tmp_index; 381 opt->unpack_opts.aggressive = !merge_detect_rename(opt); 382setup_unpack_trees_porcelain(&opt->unpack_opts,"merge"); 383 384init_tree_desc_from_tree(t+0, common); 385init_tree_desc_from_tree(t+1, head); 386init_tree_desc_from_tree(t+2, merge); 387 388 rc =unpack_trees(3, t, &opt->unpack_opts); 389cache_tree_free(&opt->repo->index->cache_tree); 390 391/* 392 * Update opt->repo->index to match the new results, AFTER saving a copy 393 * in opt->orig_index. Update src_index to point to the saved copy. 394 * (verify_uptodate() checks src_index, and the original index is 395 * the one that had the necessary modification timestamps.) 396 */ 397 opt->orig_index = *opt->repo->index; 398*opt->repo->index = tmp_index; 399 opt->unpack_opts.src_index = &opt->orig_index; 400 401return rc; 402} 403 404static voidunpack_trees_finish(struct merge_options *opt) 405{ 406discard_index(&opt->orig_index); 407clear_unpack_trees_porcelain(&opt->unpack_opts); 408} 409 410struct tree *write_tree_from_memory(struct merge_options *opt) 411{ 412struct tree *result = NULL; 413struct index_state *istate = opt->repo->index; 414 415if(unmerged_index(istate)) { 416int i; 417fprintf(stderr,"BUG: There are unmerged index entries:\n"); 418for(i =0; i < istate->cache_nr; i++) { 419const struct cache_entry *ce = istate->cache[i]; 420if(ce_stage(ce)) 421fprintf(stderr,"BUG:%d%.*s\n",ce_stage(ce), 422(int)ce_namelen(ce), ce->name); 423} 424BUG("unmerged index entries in merge-recursive.c"); 425} 426 427if(!istate->cache_tree) 428 istate->cache_tree =cache_tree(); 429 430if(!cache_tree_fully_valid(istate->cache_tree) && 431cache_tree_update(istate,0) <0) { 432err(opt,_("error building trees")); 433return NULL; 434} 435 436 result =lookup_tree(opt->repo, &istate->cache_tree->oid); 437 438return result; 439} 440 441static intsave_files_dirs(const struct object_id *oid, 442struct strbuf *base,const char*path, 443unsigned int mode,int stage,void*context) 444{ 445struct path_hashmap_entry *entry; 446int baselen = base->len; 447struct merge_options *opt = context; 448 449strbuf_addstr(base, path); 450 451FLEX_ALLOC_MEM(entry, path, base->buf, base->len); 452hashmap_entry_init(entry,path_hash(entry->path)); 453hashmap_add(&opt->current_file_dir_set, entry); 454 455strbuf_setlen(base, baselen); 456return(S_ISDIR(mode) ? READ_TREE_RECURSIVE :0); 457} 458 459static voidget_files_dirs(struct merge_options *opt,struct tree *tree) 460{ 461struct pathspec match_all; 462memset(&match_all,0,sizeof(match_all)); 463read_tree_recursive(the_repository, tree,"",0,0, 464&match_all, save_files_dirs, opt); 465} 466 467static intget_tree_entry_if_blob(const struct object_id *tree, 468const char*path, 469struct diff_filespec *dfs) 470{ 471int ret; 472 473 ret =get_tree_entry(tree, path, &dfs->oid, &dfs->mode); 474if(S_ISDIR(dfs->mode)) { 475oidcpy(&dfs->oid, &null_oid); 476 dfs->mode =0; 477} 478return ret; 479} 480 481/* 482 * Returns an index_entry instance which doesn't have to correspond to 483 * a real cache entry in Git's index. 484 */ 485static struct stage_data *insert_stage_data(const char*path, 486struct tree *o,struct tree *a,struct tree *b, 487struct string_list *entries) 488{ 489struct string_list_item *item; 490struct stage_data *e =xcalloc(1,sizeof(struct stage_data)); 491get_tree_entry_if_blob(&o->object.oid, path, &e->stages[1]); 492get_tree_entry_if_blob(&a->object.oid, path, &e->stages[2]); 493get_tree_entry_if_blob(&b->object.oid, path, &e->stages[3]); 494 item =string_list_insert(entries, path); 495 item->util = e; 496return e; 497} 498 499/* 500 * Create a dictionary mapping file names to stage_data objects. The 501 * dictionary contains one entry for every path with a non-zero stage entry. 502 */ 503static struct string_list *get_unmerged(struct index_state *istate) 504{ 505struct string_list *unmerged =xcalloc(1,sizeof(struct string_list)); 506int i; 507 508 unmerged->strdup_strings =1; 509 510for(i =0; i < istate->cache_nr; i++) { 511struct string_list_item *item; 512struct stage_data *e; 513const struct cache_entry *ce = istate->cache[i]; 514if(!ce_stage(ce)) 515continue; 516 517 item =string_list_lookup(unmerged, ce->name); 518if(!item) { 519 item =string_list_insert(unmerged, ce->name); 520 item->util =xcalloc(1,sizeof(struct stage_data)); 521} 522 e = item->util; 523 e->stages[ce_stage(ce)].mode = ce->ce_mode; 524oidcpy(&e->stages[ce_stage(ce)].oid, &ce->oid); 525} 526 527return unmerged; 528} 529 530static intstring_list_df_name_compare(const char*one,const char*two) 531{ 532int onelen =strlen(one); 533int twolen =strlen(two); 534/* 535 * Here we only care that entries for D/F conflicts are 536 * adjacent, in particular with the file of the D/F conflict 537 * appearing before files below the corresponding directory. 538 * The order of the rest of the list is irrelevant for us. 539 * 540 * To achieve this, we sort with df_name_compare and provide 541 * the mode S_IFDIR so that D/F conflicts will sort correctly. 542 * We use the mode S_IFDIR for everything else for simplicity, 543 * since in other cases any changes in their order due to 544 * sorting cause no problems for us. 545 */ 546int cmp =df_name_compare(one, onelen, S_IFDIR, 547 two, twolen, S_IFDIR); 548/* 549 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure 550 * that 'foo' comes before 'foo/bar'. 551 */ 552if(cmp) 553return cmp; 554return onelen - twolen; 555} 556 557static voidrecord_df_conflict_files(struct merge_options *opt, 558struct string_list *entries) 559{ 560/* If there is a D/F conflict and the file for such a conflict 561 * currently exists in the working tree, we want to allow it to be 562 * removed to make room for the corresponding directory if needed. 563 * The files underneath the directories of such D/F conflicts will 564 * be processed before the corresponding file involved in the D/F 565 * conflict. If the D/F directory ends up being removed by the 566 * merge, then we won't have to touch the D/F file. If the D/F 567 * directory needs to be written to the working copy, then the D/F 568 * file will simply be removed (in make_room_for_path()) to make 569 * room for the necessary paths. Note that if both the directory 570 * and the file need to be present, then the D/F file will be 571 * reinstated with a new unique name at the time it is processed. 572 */ 573struct string_list df_sorted_entries = STRING_LIST_INIT_NODUP; 574const char*last_file = NULL; 575int last_len =0; 576int i; 577 578/* 579 * If we're merging merge-bases, we don't want to bother with 580 * any working directory changes. 581 */ 582if(opt->call_depth) 583return; 584 585/* Ensure D/F conflicts are adjacent in the entries list. */ 586for(i =0; i < entries->nr; i++) { 587struct string_list_item *next = &entries->items[i]; 588string_list_append(&df_sorted_entries, next->string)->util = 589 next->util; 590} 591 df_sorted_entries.cmp = string_list_df_name_compare; 592string_list_sort(&df_sorted_entries); 593 594string_list_clear(&opt->df_conflict_file_set,1); 595for(i =0; i < df_sorted_entries.nr; i++) { 596const char*path = df_sorted_entries.items[i].string; 597int len =strlen(path); 598struct stage_data *e = df_sorted_entries.items[i].util; 599 600/* 601 * Check if last_file & path correspond to a D/F conflict; 602 * i.e. whether path is last_file+'/'+<something>. 603 * If so, record that it's okay to remove last_file to make 604 * room for path and friends if needed. 605 */ 606if(last_file && 607 len > last_len && 608memcmp(path, last_file, last_len) ==0&& 609 path[last_len] =='/') { 610string_list_insert(&opt->df_conflict_file_set, last_file); 611} 612 613/* 614 * Determine whether path could exist as a file in the 615 * working directory as a possible D/F conflict. This 616 * will only occur when it exists in stage 2 as a 617 * file. 618 */ 619if(S_ISREG(e->stages[2].mode) ||S_ISLNK(e->stages[2].mode)) { 620 last_file = path; 621 last_len = len; 622}else{ 623 last_file = NULL; 624} 625} 626string_list_clear(&df_sorted_entries,0); 627} 628 629static intupdate_stages(struct merge_options *opt,const char*path, 630const struct diff_filespec *o, 631const struct diff_filespec *a, 632const struct diff_filespec *b) 633{ 634 635/* 636 * NOTE: It is usually a bad idea to call update_stages on a path 637 * before calling update_file on that same path, since it can 638 * sometimes lead to spurious "refusing to lose untracked file..." 639 * messages from update_file (via make_room_for path via 640 * would_lose_untracked). Instead, reverse the order of the calls 641 * (executing update_file first and then update_stages). 642 */ 643int clear =1; 644int options = ADD_CACHE_OK_TO_ADD | ADD_CACHE_SKIP_DFCHECK; 645if(clear) 646if(remove_file_from_index(opt->repo->index, path)) 647return-1; 648if(o) 649if(add_cacheinfo(opt, o, path,1,0, options)) 650return-1; 651if(a) 652if(add_cacheinfo(opt, a, path,2,0, options)) 653return-1; 654if(b) 655if(add_cacheinfo(opt, b, path,3,0, options)) 656return-1; 657return0; 658} 659 660static voidupdate_entry(struct stage_data *entry, 661struct diff_filespec *o, 662struct diff_filespec *a, 663struct diff_filespec *b) 664{ 665 entry->processed =0; 666 entry->stages[1].mode = o->mode; 667 entry->stages[2].mode = a->mode; 668 entry->stages[3].mode = b->mode; 669oidcpy(&entry->stages[1].oid, &o->oid); 670oidcpy(&entry->stages[2].oid, &a->oid); 671oidcpy(&entry->stages[3].oid, &b->oid); 672} 673 674static intremove_file(struct merge_options *opt,int clean, 675const char*path,int no_wd) 676{ 677int update_cache = opt->call_depth || clean; 678int update_working_directory = !opt->call_depth && !no_wd; 679 680if(update_cache) { 681if(remove_file_from_index(opt->repo->index, path)) 682return-1; 683} 684if(update_working_directory) { 685if(ignore_case) { 686struct cache_entry *ce; 687 ce =index_file_exists(opt->repo->index, path,strlen(path), 688 ignore_case); 689if(ce &&ce_stage(ce) ==0&&strcmp(path, ce->name)) 690return0; 691} 692if(remove_path(path)) 693return-1; 694} 695return0; 696} 697 698/* add a string to a strbuf, but converting "/" to "_" */ 699static voidadd_flattened_path(struct strbuf *out,const char*s) 700{ 701size_t i = out->len; 702strbuf_addstr(out, s); 703for(; i < out->len; i++) 704if(out->buf[i] =='/') 705 out->buf[i] ='_'; 706} 707 708static char*unique_path(struct merge_options *opt,const char*path,const char*branch) 709{ 710struct path_hashmap_entry *entry; 711struct strbuf newpath = STRBUF_INIT; 712int suffix =0; 713size_t base_len; 714 715strbuf_addf(&newpath,"%s~", path); 716add_flattened_path(&newpath, branch); 717 718 base_len = newpath.len; 719while(hashmap_get_from_hash(&opt->current_file_dir_set, 720path_hash(newpath.buf), newpath.buf) || 721(!opt->call_depth &&file_exists(newpath.buf))) { 722strbuf_setlen(&newpath, base_len); 723strbuf_addf(&newpath,"_%d", suffix++); 724} 725 726FLEX_ALLOC_MEM(entry, path, newpath.buf, newpath.len); 727hashmap_entry_init(entry,path_hash(entry->path)); 728hashmap_add(&opt->current_file_dir_set, entry); 729returnstrbuf_detach(&newpath, NULL); 730} 731 732/** 733 * Check whether a directory in the index is in the way of an incoming 734 * file. Return 1 if so. If check_working_copy is non-zero, also 735 * check the working directory. If empty_ok is non-zero, also return 736 * 0 in the case where the working-tree dir exists but is empty. 737 */ 738static intdir_in_way(struct index_state *istate,const char*path, 739int check_working_copy,int empty_ok) 740{ 741int pos; 742struct strbuf dirpath = STRBUF_INIT; 743struct stat st; 744 745strbuf_addstr(&dirpath, path); 746strbuf_addch(&dirpath,'/'); 747 748 pos =index_name_pos(istate, dirpath.buf, dirpath.len); 749 750if(pos <0) 751 pos = -1- pos; 752if(pos < istate->cache_nr && 753!strncmp(dirpath.buf, istate->cache[pos]->name, dirpath.len)) { 754strbuf_release(&dirpath); 755return1; 756} 757 758strbuf_release(&dirpath); 759return check_working_copy && !lstat(path, &st) &&S_ISDIR(st.st_mode) && 760!(empty_ok &&is_empty_dir(path)); 761} 762 763/* 764 * Returns whether path was tracked in the index before the merge started, 765 * and its oid and mode match the specified values 766 */ 767static intwas_tracked_and_matches(struct merge_options *opt,const char*path, 768const struct diff_filespec *blob) 769{ 770int pos =index_name_pos(&opt->orig_index, path,strlen(path)); 771struct cache_entry *ce; 772 773if(0> pos) 774/* we were not tracking this path before the merge */ 775return0; 776 777/* See if the file we were tracking before matches */ 778 ce = opt->orig_index.cache[pos]; 779return(oid_eq(&ce->oid, &blob->oid) && ce->ce_mode == blob->mode); 780} 781 782/* 783 * Returns whether path was tracked in the index before the merge started 784 */ 785static intwas_tracked(struct merge_options *opt,const char*path) 786{ 787int pos =index_name_pos(&opt->orig_index, path,strlen(path)); 788 789if(0<= pos) 790/* we were tracking this path before the merge */ 791return1; 792 793return0; 794} 795 796static intwould_lose_untracked(struct merge_options *opt,const char*path) 797{ 798struct index_state *istate = opt->repo->index; 799 800/* 801 * This may look like it can be simplified to: 802 * return !was_tracked(opt, path) && file_exists(path) 803 * but it can't. This function needs to know whether path was in 804 * the working tree due to EITHER having been tracked in the index 805 * before the merge OR having been put into the working copy and 806 * index by unpack_trees(). Due to that either-or requirement, we 807 * check the current index instead of the original one. 808 * 809 * Note that we do not need to worry about merge-recursive itself 810 * updating the index after unpack_trees() and before calling this 811 * function, because we strictly require all code paths in 812 * merge-recursive to update the working tree first and the index 813 * second. Doing otherwise would break 814 * update_file()/would_lose_untracked(); see every comment in this 815 * file which mentions "update_stages". 816 */ 817int pos =index_name_pos(istate, path,strlen(path)); 818 819if(pos <0) 820 pos = -1- pos; 821while(pos < istate->cache_nr && 822!strcmp(path, istate->cache[pos]->name)) { 823/* 824 * If stage #0, it is definitely tracked. 825 * If it has stage #2 then it was tracked 826 * before this merge started. All other 827 * cases the path was not tracked. 828 */ 829switch(ce_stage(istate->cache[pos])) { 830case0: 831case2: 832return0; 833} 834 pos++; 835} 836returnfile_exists(path); 837} 838 839static intwas_dirty(struct merge_options *opt,const char*path) 840{ 841struct cache_entry *ce; 842int dirty =1; 843 844if(opt->call_depth || !was_tracked(opt, path)) 845return!dirty; 846 847 ce =index_file_exists(opt->unpack_opts.src_index, 848 path,strlen(path), ignore_case); 849 dirty =verify_uptodate(ce, &opt->unpack_opts) !=0; 850return dirty; 851} 852 853static intmake_room_for_path(struct merge_options *opt,const char*path) 854{ 855int status, i; 856const char*msg =_("failed to create path '%s'%s"); 857 858/* Unlink any D/F conflict files that are in the way */ 859for(i =0; i < opt->df_conflict_file_set.nr; i++) { 860const char*df_path = opt->df_conflict_file_set.items[i].string; 861size_t pathlen =strlen(path); 862size_t df_pathlen =strlen(df_path); 863if(df_pathlen < pathlen && 864 path[df_pathlen] =='/'&& 865strncmp(path, df_path, df_pathlen) ==0) { 866output(opt,3, 867_("Removing%sto make room for subdirectory\n"), 868 df_path); 869unlink(df_path); 870unsorted_string_list_delete_item(&opt->df_conflict_file_set, 871 i,0); 872break; 873} 874} 875 876/* Make sure leading directories are created */ 877 status =safe_create_leading_directories_const(path); 878if(status) { 879if(status == SCLD_EXISTS) 880/* something else exists */ 881returnerr(opt, msg, path,_(": perhaps a D/F conflict?")); 882returnerr(opt, msg, path,""); 883} 884 885/* 886 * Do not unlink a file in the work tree if we are not 887 * tracking it. 888 */ 889if(would_lose_untracked(opt, path)) 890returnerr(opt,_("refusing to lose untracked file at '%s'"), 891 path); 892 893/* Successful unlink is good.. */ 894if(!unlink(path)) 895return0; 896/* .. and so is no existing file */ 897if(errno == ENOENT) 898return0; 899/* .. but not some other error (who really cares what?) */ 900returnerr(opt, msg, path,_(": perhaps a D/F conflict?")); 901} 902 903static intupdate_file_flags(struct merge_options *opt, 904const struct diff_filespec *contents, 905const char*path, 906int update_cache, 907int update_wd) 908{ 909int ret =0; 910 911if(opt->call_depth) 912 update_wd =0; 913 914if(update_wd) { 915enum object_type type; 916void*buf; 917unsigned long size; 918 919if(S_ISGITLINK(contents->mode)) { 920/* 921 * We may later decide to recursively descend into 922 * the submodule directory and update its index 923 * and/or work tree, but we do not do that now. 924 */ 925 update_wd =0; 926goto update_index; 927} 928 929 buf =read_object_file(&contents->oid, &type, &size); 930if(!buf) 931returnerr(opt,_("cannot read object%s'%s'"), 932oid_to_hex(&contents->oid), path); 933if(type != OBJ_BLOB) { 934 ret =err(opt,_("blob expected for%s'%s'"), 935oid_to_hex(&contents->oid), path); 936goto free_buf; 937} 938if(S_ISREG(contents->mode)) { 939struct strbuf strbuf = STRBUF_INIT; 940if(convert_to_working_tree(opt->repo->index, path, buf, size, &strbuf)) { 941free(buf); 942 size = strbuf.len; 943 buf =strbuf_detach(&strbuf, NULL); 944} 945} 946 947if(make_room_for_path(opt, path) <0) { 948 update_wd =0; 949goto free_buf; 950} 951if(S_ISREG(contents->mode) || 952(!has_symlinks &&S_ISLNK(contents->mode))) { 953int fd; 954int mode = (contents->mode &0100?0777:0666); 955 956 fd =open(path, O_WRONLY | O_TRUNC | O_CREAT, mode); 957if(fd <0) { 958 ret =err(opt,_("failed to open '%s':%s"), 959 path,strerror(errno)); 960goto free_buf; 961} 962write_in_full(fd, buf, size); 963close(fd); 964}else if(S_ISLNK(contents->mode)) { 965char*lnk =xmemdupz(buf, size); 966safe_create_leading_directories_const(path); 967unlink(path); 968if(symlink(lnk, path)) 969 ret =err(opt,_("failed to symlink '%s':%s"), 970 path,strerror(errno)); 971free(lnk); 972}else 973 ret =err(opt, 974_("do not know what to do with%06o%s'%s'"), 975 contents->mode,oid_to_hex(&contents->oid), path); 976 free_buf: 977free(buf); 978} 979update_index: 980if(!ret && update_cache) 981if(add_cacheinfo(opt, contents, path,0, update_wd, 982 ADD_CACHE_OK_TO_ADD)) 983return-1; 984return ret; 985} 986 987static intupdate_file(struct merge_options *opt, 988int clean, 989const struct diff_filespec *contents, 990const char*path) 991{ 992returnupdate_file_flags(opt, contents, path, 993 opt->call_depth || clean, !opt->call_depth); 994} 995 996/* Low level file merging, update and removal */ 997 998struct merge_file_info { 999struct diff_filespec blob;/* mostly use oid & mode; sometimes path */1000unsigned clean:1,1001 merge:1;1002};10031004static intmerge_3way(struct merge_options *opt,1005 mmbuffer_t *result_buf,1006const struct diff_filespec *o,1007const struct diff_filespec *a,1008const struct diff_filespec *b,1009const char*branch1,1010const char*branch2,1011const int extra_marker_size)1012{1013 mmfile_t orig, src1, src2;1014struct ll_merge_options ll_opts = {0};1015char*base_name, *name1, *name2;1016int merge_status;10171018 ll_opts.renormalize = opt->renormalize;1019 ll_opts.extra_marker_size = extra_marker_size;1020 ll_opts.xdl_opts = opt->xdl_opts;10211022if(opt->call_depth) {1023 ll_opts.virtual_ancestor =1;1024 ll_opts.variant =0;1025}else{1026switch(opt->recursive_variant) {1027case MERGE_RECURSIVE_OURS:1028 ll_opts.variant = XDL_MERGE_FAVOR_OURS;1029break;1030case MERGE_RECURSIVE_THEIRS:1031 ll_opts.variant = XDL_MERGE_FAVOR_THEIRS;1032break;1033default:1034 ll_opts.variant =0;1035break;1036}1037}10381039assert(a->path && b->path);1040if(strcmp(a->path, b->path) ||1041(opt->ancestor != NULL &&strcmp(a->path, o->path) !=0)) {1042 base_name = opt->ancestor == NULL ? NULL :1043mkpathdup("%s:%s", opt->ancestor, o->path);1044 name1 =mkpathdup("%s:%s", branch1, a->path);1045 name2 =mkpathdup("%s:%s", branch2, b->path);1046}else{1047 base_name = opt->ancestor == NULL ? NULL :1048mkpathdup("%s", opt->ancestor);1049 name1 =mkpathdup("%s", branch1);1050 name2 =mkpathdup("%s", branch2);1051}10521053read_mmblob(&orig, &o->oid);1054read_mmblob(&src1, &a->oid);1055read_mmblob(&src2, &b->oid);10561057 merge_status =ll_merge(result_buf, a->path, &orig, base_name,1058&src1, name1, &src2, name2,1059 opt->repo->index, &ll_opts);10601061free(base_name);1062free(name1);1063free(name2);1064free(orig.ptr);1065free(src1.ptr);1066free(src2.ptr);1067return merge_status;1068}10691070static intfind_first_merges(struct repository *repo,1071struct object_array *result,const char*path,1072struct commit *a,struct commit *b)1073{1074int i, j;1075struct object_array merges = OBJECT_ARRAY_INIT;1076struct commit *commit;1077int contains_another;10781079char merged_revision[42];1080const char*rev_args[] = {"rev-list","--merges","--ancestry-path",1081"--all", merged_revision, NULL };1082struct rev_info revs;1083struct setup_revision_opt rev_opts;10841085memset(result,0,sizeof(struct object_array));1086memset(&rev_opts,0,sizeof(rev_opts));10871088/* get all revisions that merge commit a */1089xsnprintf(merged_revision,sizeof(merged_revision),"^%s",1090oid_to_hex(&a->object.oid));1091repo_init_revisions(repo, &revs, NULL);1092 rev_opts.submodule = path;1093/* FIXME: can't handle linked worktrees in submodules yet */1094 revs.single_worktree = path != NULL;1095setup_revisions(ARRAY_SIZE(rev_args)-1, rev_args, &revs, &rev_opts);10961097/* save all revisions from the above list that contain b */1098if(prepare_revision_walk(&revs))1099die("revision walk setup failed");1100while((commit =get_revision(&revs)) != NULL) {1101struct object *o = &(commit->object);1102if(in_merge_bases(b, commit))1103add_object_array(o, NULL, &merges);1104}1105reset_revision_walk();11061107/* Now we've got all merges that contain a and b. Prune all1108 * merges that contain another found merge and save them in1109 * result.1110 */1111for(i =0; i < merges.nr; i++) {1112struct commit *m1 = (struct commit *) merges.objects[i].item;11131114 contains_another =0;1115for(j =0; j < merges.nr; j++) {1116struct commit *m2 = (struct commit *) merges.objects[j].item;1117if(i != j &&in_merge_bases(m2, m1)) {1118 contains_another =1;1119break;1120}1121}11221123if(!contains_another)1124add_object_array(merges.objects[i].item, NULL, result);1125}11261127object_array_clear(&merges);1128return result->nr;1129}11301131static voidprint_commit(struct commit *commit)1132{1133struct strbuf sb = STRBUF_INIT;1134struct pretty_print_context ctx = {0};1135 ctx.date_mode.type = DATE_NORMAL;1136format_commit_message(commit,"%h:%m %s", &sb, &ctx);1137fprintf(stderr,"%s\n", sb.buf);1138strbuf_release(&sb);1139}11401141static intis_valid(const struct diff_filespec *dfs)1142{1143return dfs->mode !=0&& !is_null_oid(&dfs->oid);1144}11451146static intmerge_submodule(struct merge_options *opt,1147struct object_id *result,const char*path,1148const struct object_id *base,const struct object_id *a,1149const struct object_id *b)1150{1151struct commit *commit_base, *commit_a, *commit_b;1152int parent_count;1153struct object_array merges;11541155int i;1156int search = !opt->call_depth;11571158/* store a in result in case we fail */1159oidcpy(result, a);11601161/* we can not handle deletion conflicts */1162if(is_null_oid(base))1163return0;1164if(is_null_oid(a))1165return0;1166if(is_null_oid(b))1167return0;11681169if(add_submodule_odb(path)) {1170output(opt,1,_("Failed to merge submodule%s(not checked out)"), path);1171return0;1172}11731174if(!(commit_base =lookup_commit_reference(opt->repo, base)) ||1175!(commit_a =lookup_commit_reference(opt->repo, a)) ||1176!(commit_b =lookup_commit_reference(opt->repo, b))) {1177output(opt,1,_("Failed to merge submodule%s(commits not present)"), path);1178return0;1179}11801181/* check whether both changes are forward */1182if(!in_merge_bases(commit_base, commit_a) ||1183!in_merge_bases(commit_base, commit_b)) {1184output(opt,1,_("Failed to merge submodule%s(commits don't follow merge-base)"), path);1185return0;1186}11871188/* Case #1: a is contained in b or vice versa */1189if(in_merge_bases(commit_a, commit_b)) {1190oidcpy(result, b);1191if(show(opt,3)) {1192output(opt,3,_("Fast-forwarding submodule%sto the following commit:"), path);1193output_commit_title(opt, commit_b);1194}else if(show(opt,2))1195output(opt,2,_("Fast-forwarding submodule%s"), path);1196else1197;/* no output */11981199return1;1200}1201if(in_merge_bases(commit_b, commit_a)) {1202oidcpy(result, a);1203if(show(opt,3)) {1204output(opt,3,_("Fast-forwarding submodule%sto the following commit:"), path);1205output_commit_title(opt, commit_a);1206}else if(show(opt,2))1207output(opt,2,_("Fast-forwarding submodule%s"), path);1208else1209;/* no output */12101211return1;1212}12131214/*1215 * Case #2: There are one or more merges that contain a and b in1216 * the submodule. If there is only one, then present it as a1217 * suggestion to the user, but leave it marked unmerged so the1218 * user needs to confirm the resolution.1219 */12201221/* Skip the search if makes no sense to the calling context. */1222if(!search)1223return0;12241225/* find commit which merges them */1226 parent_count =find_first_merges(opt->repo, &merges, path,1227 commit_a, commit_b);1228switch(parent_count) {1229case0:1230output(opt,1,_("Failed to merge submodule%s(merge following commits not found)"), path);1231break;12321233case1:1234output(opt,1,_("Failed to merge submodule%s(not fast-forward)"), path);1235output(opt,2,_("Found a possible merge resolution for the submodule:\n"));1236print_commit((struct commit *) merges.objects[0].item);1237output(opt,2,_(1238"If this is correct simply add it to the index "1239"for example\n"1240"by using:\n\n"1241" git update-index --cacheinfo 160000%s\"%s\"\n\n"1242"which will accept this suggestion.\n"),1243oid_to_hex(&merges.objects[0].item->oid), path);1244break;12451246default:1247output(opt,1,_("Failed to merge submodule%s(multiple merges found)"), path);1248for(i =0; i < merges.nr; i++)1249print_commit((struct commit *) merges.objects[i].item);1250}12511252object_array_clear(&merges);1253return0;1254}12551256static intmerge_mode_and_contents(struct merge_options *opt,1257const struct diff_filespec *o,1258const struct diff_filespec *a,1259const struct diff_filespec *b,1260const char*filename,1261const char*branch1,1262const char*branch2,1263const int extra_marker_size,1264struct merge_file_info *result)1265{1266if(opt->branch1 != branch1) {1267/*1268 * It's weird getting a reverse merge with HEAD on the bottom1269 * side of the conflict markers and the other branch on the1270 * top. Fix that.1271 */1272returnmerge_mode_and_contents(opt, o, b, a,1273 filename,1274 branch2, branch1,1275 extra_marker_size, result);1276}12771278 result->merge =0;1279 result->clean =1;12801281if((S_IFMT & a->mode) != (S_IFMT & b->mode)) {1282 result->clean =0;1283if(S_ISREG(a->mode)) {1284 result->blob.mode = a->mode;1285oidcpy(&result->blob.oid, &a->oid);1286}else{1287 result->blob.mode = b->mode;1288oidcpy(&result->blob.oid, &b->oid);1289}1290}else{1291if(!oid_eq(&a->oid, &o->oid) && !oid_eq(&b->oid, &o->oid))1292 result->merge =1;12931294/*1295 * Merge modes1296 */1297if(a->mode == b->mode || a->mode == o->mode)1298 result->blob.mode = b->mode;1299else{1300 result->blob.mode = a->mode;1301if(b->mode != o->mode) {1302 result->clean =0;1303 result->merge =1;1304}1305}13061307if(oid_eq(&a->oid, &b->oid) ||oid_eq(&a->oid, &o->oid))1308oidcpy(&result->blob.oid, &b->oid);1309else if(oid_eq(&b->oid, &o->oid))1310oidcpy(&result->blob.oid, &a->oid);1311else if(S_ISREG(a->mode)) {1312 mmbuffer_t result_buf;1313int ret =0, merge_status;13141315 merge_status =merge_3way(opt, &result_buf, o, a, b,1316 branch1, branch2,1317 extra_marker_size);13181319if((merge_status <0) || !result_buf.ptr)1320 ret =err(opt,_("Failed to execute internal merge"));13211322if(!ret &&1323write_object_file(result_buf.ptr, result_buf.size,1324 blob_type, &result->blob.oid))1325 ret =err(opt,_("Unable to add%sto database"),1326 a->path);13271328free(result_buf.ptr);1329if(ret)1330return ret;1331 result->clean = (merge_status ==0);1332}else if(S_ISGITLINK(a->mode)) {1333 result->clean =merge_submodule(opt, &result->blob.oid,1334 o->path,1335&o->oid,1336&a->oid,1337&b->oid);1338}else if(S_ISLNK(a->mode)) {1339switch(opt->recursive_variant) {1340case MERGE_RECURSIVE_NORMAL:1341oidcpy(&result->blob.oid, &a->oid);1342if(!oid_eq(&a->oid, &b->oid))1343 result->clean =0;1344break;1345case MERGE_RECURSIVE_OURS:1346oidcpy(&result->blob.oid, &a->oid);1347break;1348case MERGE_RECURSIVE_THEIRS:1349oidcpy(&result->blob.oid, &b->oid);1350break;1351}1352}else1353BUG("unsupported object type in the tree");1354}13551356if(result->merge)1357output(opt,2,_("Auto-merging%s"), filename);13581359return0;1360}13611362static inthandle_rename_via_dir(struct merge_options *opt,1363struct rename_conflict_info *ci)1364{1365/*1366 * Handle file adds that need to be renamed due to directory rename1367 * detection. This differs from handle_rename_normal, because1368 * there is no content merge to do; just move the file into the1369 * desired final location.1370 */1371const struct rename *ren = ci->ren1;1372const struct diff_filespec *dest = ren->pair->two;13731374if(!opt->call_depth &&would_lose_untracked(opt, dest->path)) {1375char*alt_path =unique_path(opt, dest->path, ren->branch);13761377output(opt,1,_("Error: Refusing to lose untracked file at%s; "1378"writing to%sinstead."),1379 dest->path, alt_path);1380/*1381 * Write the file in worktree at alt_path, but not in the1382 * index. Instead, write to dest->path for the index but1383 * only at the higher appropriate stage.1384 */1385if(update_file(opt,0, dest, alt_path))1386return-1;1387free(alt_path);1388returnupdate_stages(opt, dest->path, NULL,1389 ren->branch == opt->branch1 ? dest : NULL,1390 ren->branch == opt->branch1 ? NULL : dest);1391}13921393/* Update dest->path both in index and in worktree */1394if(update_file(opt,1, dest, dest->path))1395return-1;1396return0;1397}13981399static inthandle_change_delete(struct merge_options *opt,1400const char*path,const char*old_path,1401const struct diff_filespec *o,1402const struct diff_filespec *changed,1403const char*change_branch,1404const char*delete_branch,1405const char*change,const char*change_past)1406{1407char*alt_path = NULL;1408const char*update_path = path;1409int ret =0;14101411if(dir_in_way(opt->repo->index, path, !opt->call_depth,0) ||1412(!opt->call_depth &&would_lose_untracked(opt, path))) {1413 update_path = alt_path =unique_path(opt, path, change_branch);1414}14151416if(opt->call_depth) {1417/*1418 * We cannot arbitrarily accept either a_sha or b_sha as1419 * correct; since there is no true "middle point" between1420 * them, simply reuse the base version for virtual merge base.1421 */1422 ret =remove_file_from_index(opt->repo->index, path);1423if(!ret)1424 ret =update_file(opt,0, o, update_path);1425}else{1426/*1427 * Despite the four nearly duplicate messages and argument1428 * lists below and the ugliness of the nested if-statements,1429 * having complete messages makes the job easier for1430 * translators.1431 *1432 * The slight variance among the cases is due to the fact1433 * that:1434 * 1) directory/file conflicts (in effect if1435 * !alt_path) could cause us to need to write the1436 * file to a different path.1437 * 2) renames (in effect if !old_path) could mean that1438 * there are two names for the path that the user1439 * may know the file by.1440 */1441if(!alt_path) {1442if(!old_path) {1443output(opt,1,_("CONFLICT (%s/delete):%sdeleted in%s"1444"and%sin%s. Version%sof%sleft in tree."),1445 change, path, delete_branch, change_past,1446 change_branch, change_branch, path);1447}else{1448output(opt,1,_("CONFLICT (%s/delete):%sdeleted in%s"1449"and%sto%sin%s. Version%sof%sleft in tree."),1450 change, old_path, delete_branch, change_past, path,1451 change_branch, change_branch, path);1452}1453}else{1454if(!old_path) {1455output(opt,1,_("CONFLICT (%s/delete):%sdeleted in%s"1456"and%sin%s. Version%sof%sleft in tree at%s."),1457 change, path, delete_branch, change_past,1458 change_branch, change_branch, path, alt_path);1459}else{1460output(opt,1,_("CONFLICT (%s/delete):%sdeleted in%s"1461"and%sto%sin%s. Version%sof%sleft in tree at%s."),1462 change, old_path, delete_branch, change_past, path,1463 change_branch, change_branch, path, alt_path);1464}1465}1466/*1467 * No need to call update_file() on path when change_branch ==1468 * opt->branch1 && !alt_path, since that would needlessly touch1469 * path. We could call update_file_flags() with update_cache=01470 * and update_wd=0, but that's a no-op.1471 */1472if(change_branch != opt->branch1 || alt_path)1473 ret =update_file(opt,0, changed, update_path);1474}1475free(alt_path);14761477return ret;1478}14791480static inthandle_rename_delete(struct merge_options *opt,1481struct rename_conflict_info *ci)1482{1483const struct rename *ren = ci->ren1;1484const struct diff_filespec *orig = ren->pair->one;1485const struct diff_filespec *dest = ren->pair->two;1486const char*rename_branch = ren->branch;1487const char*delete_branch = (opt->branch1 == ren->branch ?1488 opt->branch2 : opt->branch1);14891490if(handle_change_delete(opt,1491 opt->call_depth ? orig->path : dest->path,1492 opt->call_depth ? NULL : orig->path,1493 orig, dest,1494 rename_branch, delete_branch,1495_("rename"),_("renamed")))1496return-1;14971498if(opt->call_depth)1499returnremove_file_from_index(opt->repo->index, dest->path);1500else1501returnupdate_stages(opt, dest->path, NULL,1502 rename_branch == opt->branch1 ? dest : NULL,1503 rename_branch == opt->branch1 ? NULL : dest);1504}15051506static inthandle_file_collision(struct merge_options *opt,1507const char*collide_path,1508const char*prev_path1,1509const char*prev_path2,1510const char*branch1,const char*branch2,1511struct diff_filespec *a,1512struct diff_filespec *b)1513{1514struct merge_file_info mfi;1515struct diff_filespec null;1516char*alt_path = NULL;1517const char*update_path = collide_path;15181519/*1520 * It's easiest to get the correct things into stage 2 and 3, and1521 * to make sure that the content merge puts HEAD before the other1522 * branch if we just ensure that branch1 == opt->branch1. So, simply1523 * flip arguments around if we don't have that.1524 */1525if(branch1 != opt->branch1) {1526returnhandle_file_collision(opt, collide_path,1527 prev_path2, prev_path1,1528 branch2, branch1,1529 b, a);1530}15311532/*1533 * In the recursive case, we just opt to undo renames1534 */1535if(opt->call_depth && (prev_path1 || prev_path2)) {1536/* Put first file (a->oid, a->mode) in its original spot */1537if(prev_path1) {1538if(update_file(opt,1, a, prev_path1))1539return-1;1540}else{1541if(update_file(opt,1, a, collide_path))1542return-1;1543}15441545/* Put second file (b->oid, b->mode) in its original spot */1546if(prev_path2) {1547if(update_file(opt,1, b, prev_path2))1548return-1;1549}else{1550if(update_file(opt,1, b, collide_path))1551return-1;1552}15531554/* Don't leave something at collision path if unrenaming both */1555if(prev_path1 && prev_path2)1556remove_file(opt,1, collide_path,0);15571558return0;1559}15601561/* Remove rename sources if rename/add or rename/rename(2to1) */1562if(prev_path1)1563remove_file(opt,1, prev_path1,1564 opt->call_depth ||would_lose_untracked(opt, prev_path1));1565if(prev_path2)1566remove_file(opt,1, prev_path2,1567 opt->call_depth ||would_lose_untracked(opt, prev_path2));15681569/*1570 * Remove the collision path, if it wouldn't cause dirty contents1571 * or an untracked file to get lost. We'll either overwrite with1572 * merged contents, or just write out to differently named files.1573 */1574if(was_dirty(opt, collide_path)) {1575output(opt,1,_("Refusing to lose dirty file at%s"),1576 collide_path);1577 update_path = alt_path =unique_path(opt, collide_path,"merged");1578}else if(would_lose_untracked(opt, collide_path)) {1579/*1580 * Only way we get here is if both renames were from1581 * a directory rename AND user had an untracked file1582 * at the location where both files end up after the1583 * two directory renames. See testcase 10d of t6043.1584 */1585output(opt,1,_("Refusing to lose untracked file at "1586"%s, even though it's in the way."),1587 collide_path);1588 update_path = alt_path =unique_path(opt, collide_path,"merged");1589}else{1590/*1591 * FIXME: It's possible that the two files are identical1592 * and that the current working copy happens to match, in1593 * which case we are unnecessarily touching the working1594 * tree file. It's not a likely enough scenario that I1595 * want to code up the checks for it and a better fix is1596 * available if we restructure how unpack_trees() and1597 * merge-recursive interoperate anyway, so punting for1598 * now...1599 */1600remove_file(opt,0, collide_path,0);1601}16021603/* Store things in diff_filespecs for functions that need it */1604 null.path = (char*)collide_path;1605oidcpy(&null.oid, &null_oid);1606 null.mode =0;16071608if(merge_mode_and_contents(opt, &null, a, b, collide_path,1609 branch1, branch2, opt->call_depth *2, &mfi))1610return-1;1611 mfi.clean &= !alt_path;1612if(update_file(opt, mfi.clean, &mfi.blob, update_path))1613return-1;1614if(!mfi.clean && !opt->call_depth &&1615update_stages(opt, collide_path, NULL, a, b))1616return-1;1617free(alt_path);1618/*1619 * FIXME: If both a & b both started with conflicts (only possible1620 * if they came from a rename/rename(2to1)), but had IDENTICAL1621 * contents including those conflicts, then in the next line we claim1622 * it was clean. If someone cares about this case, we should have the1623 * caller notify us if we started with conflicts.1624 */1625return mfi.clean;1626}16271628static inthandle_rename_add(struct merge_options *opt,1629struct rename_conflict_info *ci)1630{1631/* a was renamed to c, and a separate c was added. */1632struct diff_filespec *a = ci->ren1->pair->one;1633struct diff_filespec *c = ci->ren1->pair->two;1634char*path = c->path;1635char*prev_path_desc;1636struct merge_file_info mfi;16371638const char*rename_branch = ci->ren1->branch;1639const char*add_branch = (opt->branch1 == rename_branch ?1640 opt->branch2 : opt->branch1);1641int other_stage = (ci->ren1->branch == opt->branch1 ?3:2);16421643output(opt,1,_("CONFLICT (rename/add): "1644"Rename%s->%sin%s. Added%sin%s"),1645 a->path, c->path, rename_branch,1646 c->path, add_branch);16471648 prev_path_desc =xstrfmt("version of%sfrom%s", path, a->path);1649if(merge_mode_and_contents(opt, a, c,1650&ci->ren1->src_entry->stages[other_stage],1651 prev_path_desc,1652 opt->branch1, opt->branch2,16531+ opt->call_depth *2, &mfi))1654return-1;1655free(prev_path_desc);16561657 ci->ren1->dst_entry->stages[other_stage].path = mfi.blob.path = c->path;1658returnhandle_file_collision(opt,1659 c->path, a->path, NULL,1660 rename_branch, add_branch,1661&mfi.blob,1662&ci->ren1->dst_entry->stages[other_stage]);1663}16641665static char*find_path_for_conflict(struct merge_options *opt,1666const char*path,1667const char*branch1,1668const char*branch2)1669{1670char*new_path = NULL;1671if(dir_in_way(opt->repo->index, path, !opt->call_depth,0)) {1672 new_path =unique_path(opt, path, branch1);1673output(opt,1,_("%sis a directory in%sadding "1674"as%sinstead"),1675 path, branch2, new_path);1676}else if(would_lose_untracked(opt, path)) {1677 new_path =unique_path(opt, path, branch1);1678output(opt,1,_("Refusing to lose untracked file"1679" at%s; adding as%sinstead"),1680 path, new_path);1681}16821683return new_path;1684}16851686static inthandle_rename_rename_1to2(struct merge_options *opt,1687struct rename_conflict_info *ci)1688{1689/* One file was renamed in both branches, but to different names. */1690struct merge_file_info mfi;1691struct diff_filespec *add;1692struct diff_filespec *o = ci->ren1->pair->one;1693struct diff_filespec *a = ci->ren1->pair->two;1694struct diff_filespec *b = ci->ren2->pair->two;1695char*path_desc;16961697output(opt,1,_("CONFLICT (rename/rename): "1698"Rename\"%s\"->\"%s\"in branch\"%s\""1699"rename\"%s\"->\"%s\"in\"%s\"%s"),1700 o->path, a->path, ci->ren1->branch,1701 o->path, b->path, ci->ren2->branch,1702 opt->call_depth ?_(" (left unresolved)") :"");17031704 path_desc =xstrfmt("%sand%s, both renamed from%s",1705 a->path, b->path, o->path);1706if(merge_mode_and_contents(opt, o, a, b, path_desc,1707 ci->ren1->branch, ci->ren2->branch,1708 opt->call_depth *2, &mfi))1709return-1;1710free(path_desc);17111712if(opt->call_depth) {1713/*1714 * FIXME: For rename/add-source conflicts (if we could detect1715 * such), this is wrong. We should instead find a unique1716 * pathname and then either rename the add-source file to that1717 * unique path, or use that unique path instead of src here.1718 */1719if(update_file(opt,0, &mfi.blob, o->path))1720return-1;17211722/*1723 * Above, we put the merged content at the merge-base's1724 * path. Now we usually need to delete both a->path and1725 * b->path. However, the rename on each side of the merge1726 * could also be involved in a rename/add conflict. In1727 * such cases, we should keep the added file around,1728 * resolving the conflict at that path in its favor.1729 */1730 add = &ci->ren1->dst_entry->stages[2^1];1731if(is_valid(add)) {1732if(update_file(opt,0, add, a->path))1733return-1;1734}1735else1736remove_file_from_index(opt->repo->index, a->path);1737 add = &ci->ren2->dst_entry->stages[3^1];1738if(is_valid(add)) {1739if(update_file(opt,0, add, b->path))1740return-1;1741}1742else1743remove_file_from_index(opt->repo->index, b->path);1744}else{1745/*1746 * For each destination path, we need to see if there is a1747 * rename/add collision. If not, we can write the file out1748 * to the specified location.1749 */1750 add = &ci->ren1->dst_entry->stages[2^1];1751if(is_valid(add)) {1752 add->path = mfi.blob.path = a->path;1753if(handle_file_collision(opt, a->path,1754 NULL, NULL,1755 ci->ren1->branch,1756 ci->ren2->branch,1757&mfi.blob, add) <0)1758return-1;1759}else{1760char*new_path =find_path_for_conflict(opt, a->path,1761 ci->ren1->branch,1762 ci->ren2->branch);1763if(update_file(opt,0, &mfi.blob,1764 new_path ? new_path : a->path))1765return-1;1766free(new_path);1767if(update_stages(opt, a->path, NULL, a, NULL))1768return-1;1769}17701771 add = &ci->ren2->dst_entry->stages[3^1];1772if(is_valid(add)) {1773 add->path = mfi.blob.path = b->path;1774if(handle_file_collision(opt, b->path,1775 NULL, NULL,1776 ci->ren1->branch,1777 ci->ren2->branch,1778 add, &mfi.blob) <0)1779return-1;1780}else{1781char*new_path =find_path_for_conflict(opt, b->path,1782 ci->ren2->branch,1783 ci->ren1->branch);1784if(update_file(opt,0, &mfi.blob,1785 new_path ? new_path : b->path))1786return-1;1787free(new_path);1788if(update_stages(opt, b->path, NULL, NULL, b))1789return-1;1790}1791}17921793return0;1794}17951796static inthandle_rename_rename_2to1(struct merge_options *opt,1797struct rename_conflict_info *ci)1798{1799/* Two files, a & b, were renamed to the same thing, c. */1800struct diff_filespec *a = ci->ren1->pair->one;1801struct diff_filespec *b = ci->ren2->pair->one;1802struct diff_filespec *c1 = ci->ren1->pair->two;1803struct diff_filespec *c2 = ci->ren2->pair->two;1804char*path = c1->path;/* == c2->path */1805char*path_side_1_desc;1806char*path_side_2_desc;1807struct merge_file_info mfi_c1;1808struct merge_file_info mfi_c2;1809int ostage1, ostage2;18101811output(opt,1,_("CONFLICT (rename/rename): "1812"Rename%s->%sin%s. "1813"Rename%s->%sin%s"),1814 a->path, c1->path, ci->ren1->branch,1815 b->path, c2->path, ci->ren2->branch);18161817 path_side_1_desc =xstrfmt("version of%sfrom%s", path, a->path);1818 path_side_2_desc =xstrfmt("version of%sfrom%s", path, b->path);1819 ostage1 = ci->ren1->branch == opt->branch1 ?3:2;1820 ostage2 = ostage1 ^1;1821 ci->ren1->src_entry->stages[ostage1].path = a->path;1822 ci->ren2->src_entry->stages[ostage2].path = b->path;1823if(merge_mode_and_contents(opt, a, c1,1824&ci->ren1->src_entry->stages[ostage1],1825 path_side_1_desc,1826 opt->branch1, opt->branch2,18271+ opt->call_depth *2, &mfi_c1) ||1828merge_mode_and_contents(opt, b,1829&ci->ren2->src_entry->stages[ostage2],1830 c2, path_side_2_desc,1831 opt->branch1, opt->branch2,18321+ opt->call_depth *2, &mfi_c2))1833return-1;1834free(path_side_1_desc);1835free(path_side_2_desc);1836 mfi_c1.blob.path = path;1837 mfi_c2.blob.path = path;18381839returnhandle_file_collision(opt, path, a->path, b->path,1840 ci->ren1->branch, ci->ren2->branch,1841&mfi_c1.blob, &mfi_c2.blob);1842}18431844/*1845 * Get the diff_filepairs changed between o_tree and tree.1846 */1847static struct diff_queue_struct *get_diffpairs(struct merge_options *opt,1848struct tree *o_tree,1849struct tree *tree)1850{1851struct diff_queue_struct *ret;1852struct diff_options opts;18531854repo_diff_setup(opt->repo, &opts);1855 opts.flags.recursive =1;1856 opts.flags.rename_empty =0;1857 opts.detect_rename =merge_detect_rename(opt);1858/*1859 * We do not have logic to handle the detection of copies. In1860 * fact, it may not even make sense to add such logic: would we1861 * really want a change to a base file to be propagated through1862 * multiple other files by a merge?1863 */1864if(opts.detect_rename > DIFF_DETECT_RENAME)1865 opts.detect_rename = DIFF_DETECT_RENAME;1866 opts.rename_limit = opt->merge_rename_limit >=0? opt->merge_rename_limit :1867 opt->diff_rename_limit >=0? opt->diff_rename_limit :18681000;1869 opts.rename_score = opt->rename_score;1870 opts.show_rename_progress = opt->show_rename_progress;1871 opts.output_format = DIFF_FORMAT_NO_OUTPUT;1872diff_setup_done(&opts);1873diff_tree_oid(&o_tree->object.oid, &tree->object.oid,"", &opts);1874diffcore_std(&opts);1875if(opts.needed_rename_limit > opt->needed_rename_limit)1876 opt->needed_rename_limit = opts.needed_rename_limit;18771878 ret =xmalloc(sizeof(*ret));1879*ret = diff_queued_diff;18801881 opts.output_format = DIFF_FORMAT_NO_OUTPUT;1882 diff_queued_diff.nr =0;1883 diff_queued_diff.queue = NULL;1884diff_flush(&opts);1885return ret;1886}18871888static inttree_has_path(struct tree *tree,const char*path)1889{1890struct object_id hashy;1891unsigned short mode_o;18921893return!get_tree_entry(&tree->object.oid, path,1894&hashy, &mode_o);1895}18961897/*1898 * Return a new string that replaces the beginning portion (which matches1899 * entry->dir), with entry->new_dir. In perl-speak:1900 * new_path_name = (old_path =~ s/entry->dir/entry->new_dir/);1901 * NOTE:1902 * Caller must ensure that old_path starts with entry->dir + '/'.1903 */1904static char*apply_dir_rename(struct dir_rename_entry *entry,1905const char*old_path)1906{1907struct strbuf new_path = STRBUF_INIT;1908int oldlen, newlen;19091910if(entry->non_unique_new_dir)1911return NULL;19121913 oldlen =strlen(entry->dir);1914 newlen = entry->new_dir.len + (strlen(old_path) - oldlen) +1;1915strbuf_grow(&new_path, newlen);1916strbuf_addbuf(&new_path, &entry->new_dir);1917strbuf_addstr(&new_path, &old_path[oldlen]);19181919returnstrbuf_detach(&new_path, NULL);1920}19211922static voidget_renamed_dir_portion(const char*old_path,const char*new_path,1923char**old_dir,char**new_dir)1924{1925char*end_of_old, *end_of_new;1926int old_len, new_len;19271928*old_dir = NULL;1929*new_dir = NULL;19301931/*1932 * For1933 * "a/b/c/d/e/foo.c" -> "a/b/some/thing/else/e/foo.c"1934 * the "e/foo.c" part is the same, we just want to know that1935 * "a/b/c/d" was renamed to "a/b/some/thing/else"1936 * so, for this example, this function returns "a/b/c/d" in1937 * *old_dir and "a/b/some/thing/else" in *new_dir.1938 *1939 * Also, if the basename of the file changed, we don't care. We1940 * want to know which portion of the directory, if any, changed.1941 */1942 end_of_old =strrchr(old_path,'/');1943 end_of_new =strrchr(new_path,'/');19441945if(end_of_old == NULL || end_of_new == NULL)1946return;1947while(*--end_of_new == *--end_of_old &&1948 end_of_old != old_path &&1949 end_of_new != new_path)1950;/* Do nothing; all in the while loop */1951/*1952 * We've found the first non-matching character in the directory1953 * paths. That means the current directory we were comparing1954 * represents the rename. Move end_of_old and end_of_new back1955 * to the full directory name.1956 */1957if(*end_of_old =='/')1958 end_of_old++;1959if(*end_of_old !='/')1960 end_of_new++;1961 end_of_old =strchr(end_of_old,'/');1962 end_of_new =strchr(end_of_new,'/');19631964/*1965 * It may have been the case that old_path and new_path were the same1966 * directory all along. Don't claim a rename if they're the same.1967 */1968 old_len = end_of_old - old_path;1969 new_len = end_of_new - new_path;19701971if(old_len != new_len ||strncmp(old_path, new_path, old_len)) {1972*old_dir =xstrndup(old_path, old_len);1973*new_dir =xstrndup(new_path, new_len);1974}1975}19761977static voidremove_hashmap_entries(struct hashmap *dir_renames,1978struct string_list *items_to_remove)1979{1980int i;1981struct dir_rename_entry *entry;19821983for(i =0; i < items_to_remove->nr; i++) {1984 entry = items_to_remove->items[i].util;1985hashmap_remove(dir_renames, entry, NULL);1986}1987string_list_clear(items_to_remove,0);1988}19891990/*1991 * See if there is a directory rename for path, and if there are any file1992 * level conflicts for the renamed location. If there is a rename and1993 * there are no conflicts, return the new name. Otherwise, return NULL.1994 */1995static char*handle_path_level_conflicts(struct merge_options *opt,1996const char*path,1997struct dir_rename_entry *entry,1998struct hashmap *collisions,1999struct tree *tree)2000{2001char*new_path = NULL;2002struct collision_entry *collision_ent;2003int clean =1;2004struct strbuf collision_paths = STRBUF_INIT;20052006/*2007 * entry has the mapping of old directory name to new directory name2008 * that we want to apply to path.2009 */2010 new_path =apply_dir_rename(entry, path);20112012if(!new_path) {2013/* This should only happen when entry->non_unique_new_dir set */2014if(!entry->non_unique_new_dir)2015BUG("entry->non_unqiue_dir not set and !new_path");2016output(opt,1,_("CONFLICT (directory rename split): "2017"Unclear where to place%sbecause directory "2018"%swas renamed to multiple other directories, "2019"with no destination getting a majority of the "2020"files."),2021 path, entry->dir);2022 clean =0;2023return NULL;2024}20252026/*2027 * The caller needs to have ensured that it has pre-populated2028 * collisions with all paths that map to new_path. Do a quick check2029 * to ensure that's the case.2030 */2031 collision_ent =collision_find_entry(collisions, new_path);2032if(collision_ent == NULL)2033BUG("collision_ent is NULL");20342035/*2036 * Check for one-sided add/add/.../add conflicts, i.e.2037 * where implicit renames from the other side doing2038 * directory rename(s) can affect this side of history2039 * to put multiple paths into the same location. Warn2040 * and bail on directory renames for such paths.2041 */2042if(collision_ent->reported_already) {2043 clean =0;2044}else if(tree_has_path(tree, new_path)) {2045 collision_ent->reported_already =1;2046strbuf_add_separated_string_list(&collision_paths,", ",2047&collision_ent->source_files);2048output(opt,1,_("CONFLICT (implicit dir rename): Existing "2049"file/dir at%sin the way of implicit "2050"directory rename(s) putting the following "2051"path(s) there:%s."),2052 new_path, collision_paths.buf);2053 clean =0;2054}else if(collision_ent->source_files.nr >1) {2055 collision_ent->reported_already =1;2056strbuf_add_separated_string_list(&collision_paths,", ",2057&collision_ent->source_files);2058output(opt,1,_("CONFLICT (implicit dir rename): Cannot map "2059"more than one path to%s; implicit directory "2060"renames tried to put these paths there:%s"),2061 new_path, collision_paths.buf);2062 clean =0;2063}20642065/* Free memory we no longer need */2066strbuf_release(&collision_paths);2067if(!clean && new_path) {2068free(new_path);2069return NULL;2070}20712072return new_path;2073}20742075/*2076 * There are a couple things we want to do at the directory level:2077 * 1. Check for both sides renaming to the same thing, in order to avoid2078 * implicit renaming of files that should be left in place. (See2079 * testcase 6b in t6043 for details.)2080 * 2. Prune directory renames if there are still files left in the2081 * the original directory. These represent a partial directory rename,2082 * i.e. a rename where only some of the files within the directory2083 * were renamed elsewhere. (Technically, this could be done earlier2084 * in get_directory_renames(), except that would prevent us from2085 * doing the previous check and thus failing testcase 6b.)2086 * 3. Check for rename/rename(1to2) conflicts (at the directory level).2087 * In the future, we could potentially record this info as well and2088 * omit reporting rename/rename(1to2) conflicts for each path within2089 * the affected directories, thus cleaning up the merge output.2090 * NOTE: We do NOT check for rename/rename(2to1) conflicts at the2091 * directory level, because merging directories is fine. If it2092 * causes conflicts for files within those merged directories, then2093 * that should be detected at the individual path level.2094 */2095static voidhandle_directory_level_conflicts(struct merge_options *opt,2096struct hashmap *dir_re_head,2097struct tree *head,2098struct hashmap *dir_re_merge,2099struct tree *merge)2100{2101struct hashmap_iter iter;2102struct dir_rename_entry *head_ent;2103struct dir_rename_entry *merge_ent;21042105struct string_list remove_from_head = STRING_LIST_INIT_NODUP;2106struct string_list remove_from_merge = STRING_LIST_INIT_NODUP;21072108hashmap_iter_init(dir_re_head, &iter);2109while((head_ent =hashmap_iter_next(&iter))) {2110 merge_ent =dir_rename_find_entry(dir_re_merge, head_ent->dir);2111if(merge_ent &&2112!head_ent->non_unique_new_dir &&2113!merge_ent->non_unique_new_dir &&2114!strbuf_cmp(&head_ent->new_dir, &merge_ent->new_dir)) {2115/* 1. Renamed identically; remove it from both sides */2116string_list_append(&remove_from_head,2117 head_ent->dir)->util = head_ent;2118strbuf_release(&head_ent->new_dir);2119string_list_append(&remove_from_merge,2120 merge_ent->dir)->util = merge_ent;2121strbuf_release(&merge_ent->new_dir);2122}else if(tree_has_path(head, head_ent->dir)) {2123/* 2. This wasn't a directory rename after all */2124string_list_append(&remove_from_head,2125 head_ent->dir)->util = head_ent;2126strbuf_release(&head_ent->new_dir);2127}2128}21292130remove_hashmap_entries(dir_re_head, &remove_from_head);2131remove_hashmap_entries(dir_re_merge, &remove_from_merge);21322133hashmap_iter_init(dir_re_merge, &iter);2134while((merge_ent =hashmap_iter_next(&iter))) {2135 head_ent =dir_rename_find_entry(dir_re_head, merge_ent->dir);2136if(tree_has_path(merge, merge_ent->dir)) {2137/* 2. This wasn't a directory rename after all */2138string_list_append(&remove_from_merge,2139 merge_ent->dir)->util = merge_ent;2140}else if(head_ent &&2141!head_ent->non_unique_new_dir &&2142!merge_ent->non_unique_new_dir) {2143/* 3. rename/rename(1to2) */2144/*2145 * We can assume it's not rename/rename(1to1) because2146 * that was case (1), already checked above. So we2147 * know that head_ent->new_dir and merge_ent->new_dir2148 * are different strings.2149 */2150output(opt,1,_("CONFLICT (rename/rename): "2151"Rename directory%s->%sin%s. "2152"Rename directory%s->%sin%s"),2153 head_ent->dir, head_ent->new_dir.buf, opt->branch1,2154 head_ent->dir, merge_ent->new_dir.buf, opt->branch2);2155string_list_append(&remove_from_head,2156 head_ent->dir)->util = head_ent;2157strbuf_release(&head_ent->new_dir);2158string_list_append(&remove_from_merge,2159 merge_ent->dir)->util = merge_ent;2160strbuf_release(&merge_ent->new_dir);2161}2162}21632164remove_hashmap_entries(dir_re_head, &remove_from_head);2165remove_hashmap_entries(dir_re_merge, &remove_from_merge);2166}21672168static struct hashmap *get_directory_renames(struct diff_queue_struct *pairs)2169{2170struct hashmap *dir_renames;2171struct hashmap_iter iter;2172struct dir_rename_entry *entry;2173int i;21742175/*2176 * Typically, we think of a directory rename as all files from a2177 * certain directory being moved to a target directory. However,2178 * what if someone first moved two files from the original2179 * directory in one commit, and then renamed the directory2180 * somewhere else in a later commit? At merge time, we just know2181 * that files from the original directory went to two different2182 * places, and that the bulk of them ended up in the same place.2183 * We want each directory rename to represent where the bulk of the2184 * files from that directory end up; this function exists to find2185 * where the bulk of the files went.2186 *2187 * The first loop below simply iterates through the list of file2188 * renames, finding out how often each directory rename pair2189 * possibility occurs.2190 */2191 dir_renames =xmalloc(sizeof(*dir_renames));2192dir_rename_init(dir_renames);2193for(i =0; i < pairs->nr; ++i) {2194struct string_list_item *item;2195int*count;2196struct diff_filepair *pair = pairs->queue[i];2197char*old_dir, *new_dir;21982199/* File not part of directory rename if it wasn't renamed */2200if(pair->status !='R')2201continue;22022203get_renamed_dir_portion(pair->one->path, pair->two->path,2204&old_dir, &new_dir);2205if(!old_dir)2206/* Directory didn't change at all; ignore this one. */2207continue;22082209 entry =dir_rename_find_entry(dir_renames, old_dir);2210if(!entry) {2211 entry =xmalloc(sizeof(*entry));2212dir_rename_entry_init(entry, old_dir);2213hashmap_put(dir_renames, entry);2214}else{2215free(old_dir);2216}2217 item =string_list_lookup(&entry->possible_new_dirs, new_dir);2218if(!item) {2219 item =string_list_insert(&entry->possible_new_dirs,2220 new_dir);2221 item->util =xcalloc(1,sizeof(int));2222}else{2223free(new_dir);2224}2225 count = item->util;2226*count +=1;2227}22282229/*2230 * For each directory with files moved out of it, we find out which2231 * target directory received the most files so we can declare it to2232 * be the "winning" target location for the directory rename. This2233 * winner gets recorded in new_dir. If there is no winner2234 * (multiple target directories received the same number of files),2235 * we set non_unique_new_dir. Once we've determined the winner (or2236 * that there is no winner), we no longer need possible_new_dirs.2237 */2238hashmap_iter_init(dir_renames, &iter);2239while((entry =hashmap_iter_next(&iter))) {2240int max =0;2241int bad_max =0;2242char*best = NULL;22432244for(i =0; i < entry->possible_new_dirs.nr; i++) {2245int*count = entry->possible_new_dirs.items[i].util;22462247if(*count == max)2248 bad_max = max;2249else if(*count > max) {2250 max = *count;2251 best = entry->possible_new_dirs.items[i].string;2252}2253}2254if(bad_max == max)2255 entry->non_unique_new_dir =1;2256else{2257assert(entry->new_dir.len ==0);2258strbuf_addstr(&entry->new_dir, best);2259}2260/*2261 * The relevant directory sub-portion of the original full2262 * filepaths were xstrndup'ed before inserting into2263 * possible_new_dirs, and instead of manually iterating the2264 * list and free'ing each, just lie and tell2265 * possible_new_dirs that it did the strdup'ing so that it2266 * will free them for us.2267 */2268 entry->possible_new_dirs.strdup_strings =1;2269string_list_clear(&entry->possible_new_dirs,1);2270}22712272return dir_renames;2273}22742275static struct dir_rename_entry *check_dir_renamed(const char*path,2276struct hashmap *dir_renames)2277{2278char*temp =xstrdup(path);2279char*end;2280struct dir_rename_entry *entry = NULL;22812282while((end =strrchr(temp,'/'))) {2283*end ='\0';2284 entry =dir_rename_find_entry(dir_renames, temp);2285if(entry)2286break;2287}2288free(temp);2289return entry;2290}22912292static voidcompute_collisions(struct hashmap *collisions,2293struct hashmap *dir_renames,2294struct diff_queue_struct *pairs)2295{2296int i;22972298/*2299 * Multiple files can be mapped to the same path due to directory2300 * renames done by the other side of history. Since that other2301 * side of history could have merged multiple directories into one,2302 * if our side of history added the same file basename to each of2303 * those directories, then all N of them would get implicitly2304 * renamed by the directory rename detection into the same path,2305 * and we'd get an add/add/.../add conflict, and all those adds2306 * from *this* side of history. This is not representable in the2307 * index, and users aren't going to easily be able to make sense of2308 * it. So we need to provide a good warning about what's2309 * happening, and fall back to no-directory-rename detection2310 * behavior for those paths.2311 *2312 * See testcases 9e and all of section 5 from t6043 for examples.2313 */2314collision_init(collisions);23152316for(i =0; i < pairs->nr; ++i) {2317struct dir_rename_entry *dir_rename_ent;2318struct collision_entry *collision_ent;2319char*new_path;2320struct diff_filepair *pair = pairs->queue[i];23212322if(pair->status !='A'&& pair->status !='R')2323continue;2324 dir_rename_ent =check_dir_renamed(pair->two->path,2325 dir_renames);2326if(!dir_rename_ent)2327continue;23282329 new_path =apply_dir_rename(dir_rename_ent, pair->two->path);2330if(!new_path)2331/*2332 * dir_rename_ent->non_unique_new_path is true, which2333 * means there is no directory rename for us to use,2334 * which means it won't cause us any additional2335 * collisions.2336 */2337continue;2338 collision_ent =collision_find_entry(collisions, new_path);2339if(!collision_ent) {2340 collision_ent =xcalloc(1,2341sizeof(struct collision_entry));2342hashmap_entry_init(collision_ent,strhash(new_path));2343hashmap_put(collisions, collision_ent);2344 collision_ent->target_file = new_path;2345}else{2346free(new_path);2347}2348string_list_insert(&collision_ent->source_files,2349 pair->two->path);2350}2351}23522353static char*check_for_directory_rename(struct merge_options *opt,2354const char*path,2355struct tree *tree,2356struct hashmap *dir_renames,2357struct hashmap *dir_rename_exclusions,2358struct hashmap *collisions,2359int*clean_merge)2360{2361char*new_path = NULL;2362struct dir_rename_entry *entry =check_dir_renamed(path, dir_renames);2363struct dir_rename_entry *oentry = NULL;23642365if(!entry)2366return new_path;23672368/*2369 * This next part is a little weird. We do not want to do an2370 * implicit rename into a directory we renamed on our side, because2371 * that will result in a spurious rename/rename(1to2) conflict. An2372 * example:2373 * Base commit: dumbdir/afile, otherdir/bfile2374 * Side 1: smrtdir/afile, otherdir/bfile2375 * Side 2: dumbdir/afile, dumbdir/bfile2376 * Here, while working on Side 1, we could notice that otherdir was2377 * renamed/merged to dumbdir, and change the diff_filepair for2378 * otherdir/bfile into a rename into dumbdir/bfile. However, Side2379 * 2 will notice the rename from dumbdir to smrtdir, and do the2380 * transitive rename to move it from dumbdir/bfile to2381 * smrtdir/bfile. That gives us bfile in dumbdir vs being in2382 * smrtdir, a rename/rename(1to2) conflict. We really just want2383 * the file to end up in smrtdir. And the way to achieve that is2384 * to not let Side1 do the rename to dumbdir, since we know that is2385 * the source of one of our directory renames.2386 *2387 * That's why oentry and dir_rename_exclusions is here.2388 *2389 * As it turns out, this also prevents N-way transient rename2390 * confusion; See testcases 9c and 9d of t6043.2391 */2392 oentry =dir_rename_find_entry(dir_rename_exclusions, entry->new_dir.buf);2393if(oentry) {2394output(opt,1,_("WARNING: Avoiding applying%s->%srename "2395"to%s, because%sitself was renamed."),2396 entry->dir, entry->new_dir.buf, path, entry->new_dir.buf);2397}else{2398 new_path =handle_path_level_conflicts(opt, path, entry,2399 collisions, tree);2400*clean_merge &= (new_path != NULL);2401}24022403return new_path;2404}24052406static voidapply_directory_rename_modifications(struct merge_options *opt,2407struct diff_filepair *pair,2408char*new_path,2409struct rename *re,2410struct tree *tree,2411struct tree *o_tree,2412struct tree *a_tree,2413struct tree *b_tree,2414struct string_list *entries)2415{2416struct string_list_item *item;2417int stage = (tree == a_tree ?2:3);2418int update_wd;24192420/*2421 * In all cases where we can do directory rename detection,2422 * unpack_trees() will have read pair->two->path into the2423 * index and the working copy. We need to remove it so that2424 * we can instead place it at new_path. It is guaranteed to2425 * not be untracked (unpack_trees() would have errored out2426 * saying the file would have been overwritten), but it might2427 * be dirty, though.2428 */2429 update_wd = !was_dirty(opt, pair->two->path);2430if(!update_wd)2431output(opt,1,_("Refusing to lose dirty file at%s"),2432 pair->two->path);2433remove_file(opt,1, pair->two->path, !update_wd);24342435/* Find or create a new re->dst_entry */2436 item =string_list_lookup(entries, new_path);2437if(item) {2438/*2439 * Since we're renaming on this side of history, and it's2440 * due to a directory rename on the other side of history2441 * (which we only allow when the directory in question no2442 * longer exists on the other side of history), the2443 * original entry for re->dst_entry is no longer2444 * necessary...2445 */2446 re->dst_entry->processed =1;24472448/*2449 * ...because we'll be using this new one.2450 */2451 re->dst_entry = item->util;2452}else{2453/*2454 * re->dst_entry is for the before-dir-rename path, and we2455 * need it to hold information for the after-dir-rename2456 * path. Before creating a new entry, we need to mark the2457 * old one as unnecessary (...unless it is shared by2458 * src_entry, i.e. this didn't use to be a rename, in which2459 * case we can just allow the normal processing to happen2460 * for it).2461 */2462if(pair->status =='R')2463 re->dst_entry->processed =1;24642465 re->dst_entry =insert_stage_data(new_path,2466 o_tree, a_tree, b_tree,2467 entries);2468 item =string_list_insert(entries, new_path);2469 item->util = re->dst_entry;2470}24712472/*2473 * Update the stage_data with the information about the path we are2474 * moving into place. That slot will be empty and available for us2475 * to write to because of the collision checks in2476 * handle_path_level_conflicts(). In other words,2477 * re->dst_entry->stages[stage].oid will be the null_oid, so it's2478 * open for us to write to.2479 *2480 * It may be tempting to actually update the index at this point as2481 * well, using update_stages_for_stage_data(), but as per the big2482 * "NOTE" in update_stages(), doing so will modify the current2483 * in-memory index which will break calls to would_lose_untracked()2484 * that we need to make. Instead, we need to just make sure that2485 * the various handle_rename_*() functions update the index2486 * explicitly rather than relying on unpack_trees() to have done it.2487 */2488get_tree_entry(&tree->object.oid,2489 pair->two->path,2490&re->dst_entry->stages[stage].oid,2491&re->dst_entry->stages[stage].mode);24922493/*2494 * Record the original change status (or 'type' of change). If it2495 * was originally an add ('A'), this lets us differentiate later2496 * between a RENAME_DELETE conflict and RENAME_VIA_DIR (they2497 * otherwise look the same). If it was originally a rename ('R'),2498 * this lets us remember and report accurately about the transitive2499 * renaming that occurred via the directory rename detection. Also,2500 * record the original destination name.2501 */2502 re->dir_rename_original_type = pair->status;2503 re->dir_rename_original_dest = pair->two->path;25042505/*2506 * We don't actually look at pair->status again, but it seems2507 * pedagogically correct to adjust it.2508 */2509 pair->status ='R';25102511/*2512 * Finally, record the new location.2513 */2514 pair->two->path = new_path;2515}25162517/*2518 * Get information of all renames which occurred in 'pairs', making use of2519 * any implicit directory renames inferred from the other side of history.2520 * We need the three trees in the merge ('o_tree', 'a_tree' and 'b_tree')2521 * to be able to associate the correct cache entries with the rename2522 * information; tree is always equal to either a_tree or b_tree.2523 */2524static struct string_list *get_renames(struct merge_options *opt,2525const char*branch,2526struct diff_queue_struct *pairs,2527struct hashmap *dir_renames,2528struct hashmap *dir_rename_exclusions,2529struct tree *tree,2530struct tree *o_tree,2531struct tree *a_tree,2532struct tree *b_tree,2533struct string_list *entries,2534int*clean_merge)2535{2536int i;2537struct hashmap collisions;2538struct hashmap_iter iter;2539struct collision_entry *e;2540struct string_list *renames;25412542compute_collisions(&collisions, dir_renames, pairs);2543 renames =xcalloc(1,sizeof(struct string_list));25442545for(i =0; i < pairs->nr; ++i) {2546struct string_list_item *item;2547struct rename *re;2548struct diff_filepair *pair = pairs->queue[i];2549char*new_path;/* non-NULL only with directory renames */25502551if(pair->status !='A'&& pair->status !='R') {2552diff_free_filepair(pair);2553continue;2554}2555 new_path =check_for_directory_rename(opt, pair->two->path, tree,2556 dir_renames,2557 dir_rename_exclusions,2558&collisions,2559 clean_merge);2560if(pair->status !='R'&& !new_path) {2561diff_free_filepair(pair);2562continue;2563}25642565 re =xmalloc(sizeof(*re));2566 re->processed =0;2567 re->pair = pair;2568 re->branch = branch;2569 re->dir_rename_original_type ='\0';2570 re->dir_rename_original_dest = NULL;2571 item =string_list_lookup(entries, re->pair->one->path);2572if(!item)2573 re->src_entry =insert_stage_data(re->pair->one->path,2574 o_tree, a_tree, b_tree, entries);2575else2576 re->src_entry = item->util;25772578 item =string_list_lookup(entries, re->pair->two->path);2579if(!item)2580 re->dst_entry =insert_stage_data(re->pair->two->path,2581 o_tree, a_tree, b_tree, entries);2582else2583 re->dst_entry = item->util;2584 item =string_list_insert(renames, pair->one->path);2585 item->util = re;2586if(new_path)2587apply_directory_rename_modifications(opt, pair, new_path,2588 re, tree, o_tree,2589 a_tree, b_tree,2590 entries);2591}25922593hashmap_iter_init(&collisions, &iter);2594while((e =hashmap_iter_next(&iter))) {2595free(e->target_file);2596string_list_clear(&e->source_files,0);2597}2598hashmap_free(&collisions,1);2599return renames;2600}26012602static intprocess_renames(struct merge_options *opt,2603struct string_list *a_renames,2604struct string_list *b_renames)2605{2606int clean_merge =1, i, j;2607struct string_list a_by_dst = STRING_LIST_INIT_NODUP;2608struct string_list b_by_dst = STRING_LIST_INIT_NODUP;2609const struct rename *sre;26102611for(i =0; i < a_renames->nr; i++) {2612 sre = a_renames->items[i].util;2613string_list_insert(&a_by_dst, sre->pair->two->path)->util2614= (void*)sre;2615}2616for(i =0; i < b_renames->nr; i++) {2617 sre = b_renames->items[i].util;2618string_list_insert(&b_by_dst, sre->pair->two->path)->util2619= (void*)sre;2620}26212622for(i =0, j =0; i < a_renames->nr || j < b_renames->nr;) {2623struct string_list *renames1, *renames2Dst;2624struct rename *ren1 = NULL, *ren2 = NULL;2625const char*ren1_src, *ren1_dst;2626struct string_list_item *lookup;26272628if(i >= a_renames->nr) {2629 ren2 = b_renames->items[j++].util;2630}else if(j >= b_renames->nr) {2631 ren1 = a_renames->items[i++].util;2632}else{2633int compare =strcmp(a_renames->items[i].string,2634 b_renames->items[j].string);2635if(compare <=0)2636 ren1 = a_renames->items[i++].util;2637if(compare >=0)2638 ren2 = b_renames->items[j++].util;2639}26402641/* TODO: refactor, so that 1/2 are not needed */2642if(ren1) {2643 renames1 = a_renames;2644 renames2Dst = &b_by_dst;2645}else{2646 renames1 = b_renames;2647 renames2Dst = &a_by_dst;2648SWAP(ren2, ren1);2649}26502651if(ren1->processed)2652continue;2653 ren1->processed =1;2654 ren1->dst_entry->processed =1;2655/* BUG: We should only mark src_entry as processed if we2656 * are not dealing with a rename + add-source case.2657 */2658 ren1->src_entry->processed =1;26592660 ren1_src = ren1->pair->one->path;2661 ren1_dst = ren1->pair->two->path;26622663if(ren2) {2664/* One file renamed on both sides */2665const char*ren2_src = ren2->pair->one->path;2666const char*ren2_dst = ren2->pair->two->path;2667enum rename_type rename_type;2668if(strcmp(ren1_src, ren2_src) !=0)2669BUG("ren1_src != ren2_src");2670 ren2->dst_entry->processed =1;2671 ren2->processed =1;2672if(strcmp(ren1_dst, ren2_dst) !=0) {2673 rename_type = RENAME_ONE_FILE_TO_TWO;2674 clean_merge =0;2675}else{2676 rename_type = RENAME_ONE_FILE_TO_ONE;2677/* BUG: We should only remove ren1_src in2678 * the base stage (think of rename +2679 * add-source cases).2680 */2681remove_file(opt,1, ren1_src,1);2682update_entry(ren1->dst_entry,2683 ren1->pair->one,2684 ren1->pair->two,2685 ren2->pair->two);2686}2687setup_rename_conflict_info(rename_type, opt, ren1, ren2);2688}else if((lookup =string_list_lookup(renames2Dst, ren1_dst))) {2689/* Two different files renamed to the same thing */2690char*ren2_dst;2691 ren2 = lookup->util;2692 ren2_dst = ren2->pair->two->path;2693if(strcmp(ren1_dst, ren2_dst) !=0)2694BUG("ren1_dst != ren2_dst");26952696 clean_merge =0;2697 ren2->processed =1;2698/*2699 * BUG: We should only mark src_entry as processed2700 * if we are not dealing with a rename + add-source2701 * case.2702 */2703 ren2->src_entry->processed =1;27042705setup_rename_conflict_info(RENAME_TWO_FILES_TO_ONE,2706 opt, ren1, ren2);2707}else{2708/* Renamed in 1, maybe changed in 2 */2709/* we only use sha1 and mode of these */2710struct diff_filespec src_other, dst_other;2711int try_merge;27122713/*2714 * unpack_trees loads entries from common-commit2715 * into stage 1, from head-commit into stage 2, and2716 * from merge-commit into stage 3. We keep track2717 * of which side corresponds to the rename.2718 */2719int renamed_stage = a_renames == renames1 ?2:3;2720int other_stage = a_renames == renames1 ?3:2;27212722/* BUG: We should only remove ren1_src in the base2723 * stage and in other_stage (think of rename +2724 * add-source case).2725 */2726remove_file(opt,1, ren1_src,2727 renamed_stage ==2|| !was_tracked(opt, ren1_src));27282729oidcpy(&src_other.oid,2730&ren1->src_entry->stages[other_stage].oid);2731 src_other.mode = ren1->src_entry->stages[other_stage].mode;2732oidcpy(&dst_other.oid,2733&ren1->dst_entry->stages[other_stage].oid);2734 dst_other.mode = ren1->dst_entry->stages[other_stage].mode;2735 try_merge =0;27362737if(oid_eq(&src_other.oid, &null_oid) &&2738 ren1->dir_rename_original_type =='A') {2739setup_rename_conflict_info(RENAME_VIA_DIR,2740 opt, ren1, NULL);2741}else if(oid_eq(&src_other.oid, &null_oid)) {2742setup_rename_conflict_info(RENAME_DELETE,2743 opt, ren1, NULL);2744}else if((dst_other.mode == ren1->pair->two->mode) &&2745oid_eq(&dst_other.oid, &ren1->pair->two->oid)) {2746/*2747 * Added file on the other side identical to2748 * the file being renamed: clean merge.2749 * Also, there is no need to overwrite the2750 * file already in the working copy, so call2751 * update_file_flags() instead of2752 * update_file().2753 */2754if(update_file_flags(opt,2755 ren1->pair->two,2756 ren1_dst,27571,/* update_cache */27580/* update_wd */))2759 clean_merge = -1;2760}else if(!oid_eq(&dst_other.oid, &null_oid)) {2761/*2762 * Probably not a clean merge, but it's2763 * premature to set clean_merge to 0 here,2764 * because if the rename merges cleanly and2765 * the merge exactly matches the newly added2766 * file, then the merge will be clean.2767 */2768setup_rename_conflict_info(RENAME_ADD,2769 opt, ren1, NULL);2770}else2771 try_merge =1;27722773if(clean_merge <0)2774goto cleanup_and_return;2775if(try_merge) {2776struct diff_filespec *o, *a, *b;2777 src_other.path = (char*)ren1_src;27782779 o = ren1->pair->one;2780if(a_renames == renames1) {2781 a = ren1->pair->two;2782 b = &src_other;2783}else{2784 b = ren1->pair->two;2785 a = &src_other;2786}2787update_entry(ren1->dst_entry, o, a, b);2788setup_rename_conflict_info(RENAME_NORMAL,2789 opt, ren1, NULL);2790}2791}2792}2793cleanup_and_return:2794string_list_clear(&a_by_dst,0);2795string_list_clear(&b_by_dst,0);27962797return clean_merge;2798}27992800struct rename_info {2801struct string_list *head_renames;2802struct string_list *merge_renames;2803};28042805static voidinitial_cleanup_rename(struct diff_queue_struct *pairs,2806struct hashmap *dir_renames)2807{2808struct hashmap_iter iter;2809struct dir_rename_entry *e;28102811hashmap_iter_init(dir_renames, &iter);2812while((e =hashmap_iter_next(&iter))) {2813free(e->dir);2814strbuf_release(&e->new_dir);2815/* possible_new_dirs already cleared in get_directory_renames */2816}2817hashmap_free(dir_renames,1);2818free(dir_renames);28192820free(pairs->queue);2821free(pairs);2822}28232824static intdetect_and_process_renames(struct merge_options *opt,2825struct tree *common,2826struct tree *head,2827struct tree *merge,2828struct string_list *entries,2829struct rename_info *ri)2830{2831struct diff_queue_struct *head_pairs, *merge_pairs;2832struct hashmap *dir_re_head, *dir_re_merge;2833int clean =1;28342835 ri->head_renames = NULL;2836 ri->merge_renames = NULL;28372838if(!merge_detect_rename(opt))2839return1;28402841 head_pairs =get_diffpairs(opt, common, head);2842 merge_pairs =get_diffpairs(opt, common, merge);28432844if(opt->detect_directory_renames) {2845 dir_re_head =get_directory_renames(head_pairs);2846 dir_re_merge =get_directory_renames(merge_pairs);28472848handle_directory_level_conflicts(opt,2849 dir_re_head, head,2850 dir_re_merge, merge);2851}else{2852 dir_re_head =xmalloc(sizeof(*dir_re_head));2853 dir_re_merge =xmalloc(sizeof(*dir_re_merge));2854dir_rename_init(dir_re_head);2855dir_rename_init(dir_re_merge);2856}28572858 ri->head_renames =get_renames(opt, opt->branch1, head_pairs,2859 dir_re_merge, dir_re_head, head,2860 common, head, merge, entries,2861&clean);2862if(clean <0)2863goto cleanup;2864 ri->merge_renames =get_renames(opt, opt->branch2, merge_pairs,2865 dir_re_head, dir_re_merge, merge,2866 common, head, merge, entries,2867&clean);2868if(clean <0)2869goto cleanup;2870 clean &=process_renames(opt, ri->head_renames, ri->merge_renames);28712872cleanup:2873/*2874 * Some cleanup is deferred until cleanup_renames() because the2875 * data structures are still needed and referenced in2876 * process_entry(). But there are a few things we can free now.2877 */2878initial_cleanup_rename(head_pairs, dir_re_head);2879initial_cleanup_rename(merge_pairs, dir_re_merge);28802881return clean;2882}28832884static voidfinal_cleanup_rename(struct string_list *rename)2885{2886const struct rename *re;2887int i;28882889if(rename == NULL)2890return;28912892for(i =0; i < rename->nr; i++) {2893 re = rename->items[i].util;2894diff_free_filepair(re->pair);2895}2896string_list_clear(rename,1);2897free(rename);2898}28992900static voidfinal_cleanup_renames(struct rename_info *re_info)2901{2902final_cleanup_rename(re_info->head_renames);2903final_cleanup_rename(re_info->merge_renames);2904}29052906static intread_oid_strbuf(struct merge_options *opt,2907const struct object_id *oid,2908struct strbuf *dst)2909{2910void*buf;2911enum object_type type;2912unsigned long size;2913 buf =read_object_file(oid, &type, &size);2914if(!buf)2915returnerr(opt,_("cannot read object%s"),oid_to_hex(oid));2916if(type != OBJ_BLOB) {2917free(buf);2918returnerr(opt,_("object%sis not a blob"),oid_to_hex(oid));2919}2920strbuf_attach(dst, buf, size, size +1);2921return0;2922}29232924static intblob_unchanged(struct merge_options *opt,2925const struct diff_filespec *o,2926const struct diff_filespec *a,2927int renormalize,const char*path)2928{2929struct strbuf obuf = STRBUF_INIT;2930struct strbuf abuf = STRBUF_INIT;2931int ret =0;/* assume changed for safety */2932const struct index_state *idx = opt->repo->index;29332934if(a->mode != o->mode)2935return0;2936if(oid_eq(&o->oid, &a->oid))2937return1;2938if(!renormalize)2939return0;29402941if(read_oid_strbuf(opt, &o->oid, &obuf) ||2942read_oid_strbuf(opt, &a->oid, &abuf))2943goto error_return;2944/*2945 * Note: binary | is used so that both renormalizations are2946 * performed. Comparison can be skipped if both files are2947 * unchanged since their sha1s have already been compared.2948 */2949if(renormalize_buffer(idx, path, obuf.buf, obuf.len, &obuf) |2950renormalize_buffer(idx, path, abuf.buf, abuf.len, &abuf))2951 ret = (obuf.len == abuf.len && !memcmp(obuf.buf, abuf.buf, obuf.len));29522953error_return:2954strbuf_release(&obuf);2955strbuf_release(&abuf);2956return ret;2957}29582959static inthandle_modify_delete(struct merge_options *opt,2960const char*path,2961const struct diff_filespec *o,2962const struct diff_filespec *a,2963const struct diff_filespec *b)2964{2965const char*modify_branch, *delete_branch;2966const struct diff_filespec *changed;29672968if(is_valid(a)) {2969 modify_branch = opt->branch1;2970 delete_branch = opt->branch2;2971 changed = a;2972}else{2973 modify_branch = opt->branch2;2974 delete_branch = opt->branch1;2975 changed = b;2976}29772978returnhandle_change_delete(opt,2979 path, NULL,2980 o, changed,2981 modify_branch, delete_branch,2982_("modify"),_("modified"));2983}29842985static inthandle_content_merge(struct merge_file_info *mfi,2986struct merge_options *opt,2987const char*path,2988int is_dirty,2989const struct diff_filespec *o,2990const struct diff_filespec *a,2991const struct diff_filespec *b,2992struct rename_conflict_info *ci)2993{2994const char*reason =_("content");2995unsigned df_conflict_remains =0;29962997if(!is_valid(o))2998 reason =_("add/add");29993000assert(o->path && a->path && b->path);3001if(ci &&dir_in_way(opt->repo->index, path, !opt->call_depth,3002S_ISGITLINK(ci->ren1->pair->two->mode)))3003 df_conflict_remains =1;30043005if(merge_mode_and_contents(opt, o, a, b, path,3006 opt->branch1, opt->branch2,3007 opt->call_depth *2, mfi))3008return-1;30093010/*3011 * We can skip updating the working tree file iff:3012 * a) The merge is clean3013 * b) The merge matches what was in HEAD (content, mode, pathname)3014 * c) The target path is usable (i.e. not involved in D/F conflict)3015 */3016if(mfi->clean &&was_tracked_and_matches(opt, path, &mfi->blob) &&3017!df_conflict_remains) {3018int pos;3019struct cache_entry *ce;30203021output(opt,3,_("Skipped%s(merged same as existing)"), path);3022if(add_cacheinfo(opt, &mfi->blob, path,30230, (!opt->call_depth && !is_dirty),0))3024return-1;3025/*3026 * However, add_cacheinfo() will delete the old cache entry3027 * and add a new one. We need to copy over any skip_worktree3028 * flag to avoid making the file appear as if it were3029 * deleted by the user.3030 */3031 pos =index_name_pos(&opt->orig_index, path,strlen(path));3032 ce = opt->orig_index.cache[pos];3033if(ce_skip_worktree(ce)) {3034 pos =index_name_pos(opt->repo->index, path,strlen(path));3035 ce = opt->repo->index->cache[pos];3036 ce->ce_flags |= CE_SKIP_WORKTREE;3037}3038return mfi->clean;3039}30403041if(!mfi->clean) {3042if(S_ISGITLINK(mfi->blob.mode))3043 reason =_("submodule");3044output(opt,1,_("CONFLICT (%s): Merge conflict in%s"),3045 reason, path);3046if(ci && !df_conflict_remains)3047if(update_stages(opt, path, o, a, b))3048return-1;3049}30503051if(df_conflict_remains || is_dirty) {3052char*new_path;3053if(opt->call_depth) {3054remove_file_from_index(opt->repo->index, path);3055}else{3056if(!mfi->clean) {3057if(update_stages(opt, path, o, a, b))3058return-1;3059}else{3060int file_from_stage2 =was_tracked(opt, path);30613062if(update_stages(opt, path, NULL,3063 file_from_stage2 ? &mfi->blob : NULL,3064 file_from_stage2 ? NULL : &mfi->blob))3065return-1;3066}30673068}3069 new_path =unique_path(opt, path, ci->ren1->branch);3070if(is_dirty) {3071output(opt,1,_("Refusing to lose dirty file at%s"),3072 path);3073}3074output(opt,1,_("Adding as%sinstead"), new_path);3075if(update_file(opt,0, &mfi->blob, new_path)) {3076free(new_path);3077return-1;3078}3079free(new_path);3080 mfi->clean =0;3081}else if(update_file(opt, mfi->clean, &mfi->blob, path))3082return-1;3083return!is_dirty && mfi->clean;3084}30853086static inthandle_rename_normal(struct merge_options *opt,3087const char*path,3088const struct diff_filespec *o,3089const struct diff_filespec *a,3090const struct diff_filespec *b,3091struct rename_conflict_info *ci)3092{3093/* Merge the content and write it out */3094struct merge_file_info mfi;3095returnhandle_content_merge(&mfi, opt, path,was_dirty(opt, path),3096 o, a, b, ci);3097}30983099/* Per entry merge function */3100static intprocess_entry(struct merge_options *opt,3101const char*path,struct stage_data *entry)3102{3103int clean_merge =1;3104int normalize = opt->renormalize;31053106struct diff_filespec *o = &entry->stages[1];3107struct diff_filespec *a = &entry->stages[2];3108struct diff_filespec *b = &entry->stages[3];3109int o_valid =is_valid(o);3110int a_valid =is_valid(a);3111int b_valid =is_valid(b);3112 o->path = a->path = b->path = (char*)path;31133114 entry->processed =1;3115if(entry->rename_conflict_info) {3116struct rename_conflict_info *ci = entry->rename_conflict_info;3117struct diff_filespec *temp;31183119/*3120 * For cases with a single rename, {o,a,b}->path have all been3121 * set to the rename target path; we need to set two of these3122 * back to the rename source.3123 * For rename/rename conflicts, we'll manually fix paths below.3124 */3125 temp = (opt->branch1 == ci->ren1->branch) ? b : a;3126 o->path = temp->path = ci->ren1->pair->one->path;3127if(ci->ren2) {3128assert(opt->branch1 == ci->ren1->branch);3129}31303131switch(ci->rename_type) {3132case RENAME_NORMAL:3133case RENAME_ONE_FILE_TO_ONE:3134 clean_merge =handle_rename_normal(opt, path, o, a, b,3135 ci);3136break;3137case RENAME_VIA_DIR:3138 clean_merge =1;3139if(handle_rename_via_dir(opt, ci))3140 clean_merge = -1;3141break;3142case RENAME_ADD:3143/*3144 * Probably unclean merge, but if the renamed file3145 * merges cleanly and the result can then be3146 * two-way merged cleanly with the added file, I3147 * guess it's a clean merge?3148 */3149 clean_merge =handle_rename_add(opt, ci);3150break;3151case RENAME_DELETE:3152 clean_merge =0;3153if(handle_rename_delete(opt, ci))3154 clean_merge = -1;3155break;3156case RENAME_ONE_FILE_TO_TWO:3157/*3158 * Manually fix up paths; note:3159 * ren[12]->pair->one->path are equal.3160 */3161 o->path = ci->ren1->pair->one->path;3162 a->path = ci->ren1->pair->two->path;3163 b->path = ci->ren2->pair->two->path;31643165 clean_merge =0;3166if(handle_rename_rename_1to2(opt, ci))3167 clean_merge = -1;3168break;3169case RENAME_TWO_FILES_TO_ONE:3170/*3171 * Manually fix up paths; note,3172 * ren[12]->pair->two->path are actually equal.3173 */3174 o->path = NULL;3175 a->path = ci->ren1->pair->two->path;3176 b->path = ci->ren2->pair->two->path;31773178/*3179 * Probably unclean merge, but if the two renamed3180 * files merge cleanly and the two resulting files3181 * can then be two-way merged cleanly, I guess it's3182 * a clean merge?3183 */3184 clean_merge =handle_rename_rename_2to1(opt, ci);3185break;3186default:3187 entry->processed =0;3188break;3189}3190}else if(o_valid && (!a_valid || !b_valid)) {3191/* Case A: Deleted in one */3192if((!a_valid && !b_valid) ||3193(!b_valid &&blob_unchanged(opt, o, a, normalize, path)) ||3194(!a_valid &&blob_unchanged(opt, o, b, normalize, path))) {3195/* Deleted in both or deleted in one and3196 * unchanged in the other */3197if(a_valid)3198output(opt,2,_("Removing%s"), path);3199/* do not touch working file if it did not exist */3200remove_file(opt,1, path, !a_valid);3201}else{3202/* Modify/delete; deleted side may have put a directory in the way */3203 clean_merge =0;3204if(handle_modify_delete(opt, path, o, a, b))3205 clean_merge = -1;3206}3207}else if((!o_valid && a_valid && !b_valid) ||3208(!o_valid && !a_valid && b_valid)) {3209/* Case B: Added in one. */3210/* [nothing|directory] -> ([nothing|directory], file) */32113212const char*add_branch;3213const char*other_branch;3214const char*conf;3215const struct diff_filespec *contents;32163217if(a_valid) {3218 add_branch = opt->branch1;3219 other_branch = opt->branch2;3220 contents = a;3221 conf =_("file/directory");3222}else{3223 add_branch = opt->branch2;3224 other_branch = opt->branch1;3225 contents = b;3226 conf =_("directory/file");3227}3228if(dir_in_way(opt->repo->index, path,3229!opt->call_depth && !S_ISGITLINK(a->mode),32300)) {3231char*new_path =unique_path(opt, path, add_branch);3232 clean_merge =0;3233output(opt,1,_("CONFLICT (%s): There is a directory with name%sin%s. "3234"Adding%sas%s"),3235 conf, path, other_branch, path, new_path);3236if(update_file(opt,0, contents, new_path))3237 clean_merge = -1;3238else if(opt->call_depth)3239remove_file_from_index(opt->repo->index, path);3240free(new_path);3241}else{3242output(opt,2,_("Adding%s"), path);3243/* do not overwrite file if already present */3244if(update_file_flags(opt, contents, path,1, !a_valid))3245 clean_merge = -1;3246}3247}else if(a_valid && b_valid) {3248if(!o_valid) {3249/* Case C: Added in both (check for same permissions) */3250output(opt,1,3251_("CONFLICT (add/add): Merge conflict in%s"),3252 path);3253 clean_merge =handle_file_collision(opt,3254 path, NULL, NULL,3255 opt->branch1,3256 opt->branch2,3257 a, b);3258}else{3259/* case D: Modified in both, but differently. */3260struct merge_file_info mfi;3261int is_dirty =0;/* unpack_trees would have bailed if dirty */3262 clean_merge =handle_content_merge(&mfi, opt, path,3263 is_dirty,3264 o, a, b, NULL);3265}3266}else if(!o_valid && !a_valid && !b_valid) {3267/*3268 * this entry was deleted altogether. a_mode == 0 means3269 * we had that path and want to actively remove it.3270 */3271remove_file(opt,1, path, !a->mode);3272}else3273BUG("fatal merge failure, shouldn't happen.");32743275return clean_merge;3276}32773278intmerge_trees(struct merge_options *opt,3279struct tree *head,3280struct tree *merge,3281struct tree *common,3282struct tree **result)3283{3284struct index_state *istate = opt->repo->index;3285int code, clean;3286struct strbuf sb = STRBUF_INIT;32873288if(!opt->call_depth &&repo_index_has_changes(opt->repo, head, &sb)) {3289err(opt,_("Your local changes to the following files would be overwritten by merge:\n%s"),3290 sb.buf);3291return-1;3292}32933294if(opt->subtree_shift) {3295 merge =shift_tree_object(opt->repo, head, merge, opt->subtree_shift);3296 common =shift_tree_object(opt->repo, head, common, opt->subtree_shift);3297}32983299if(oid_eq(&common->object.oid, &merge->object.oid)) {3300output(opt,0,_("Already up to date!"));3301*result = head;3302return1;3303}33043305 code =unpack_trees_start(opt, common, head, merge);33063307if(code !=0) {3308if(show(opt,4) || opt->call_depth)3309err(opt,_("merging of trees%sand%sfailed"),3310oid_to_hex(&head->object.oid),3311oid_to_hex(&merge->object.oid));3312unpack_trees_finish(opt);3313return-1;3314}33153316if(unmerged_index(istate)) {3317struct string_list *entries;3318struct rename_info re_info;3319int i;3320/*3321 * Only need the hashmap while processing entries, so3322 * initialize it here and free it when we are done running3323 * through the entries. Keeping it in the merge_options as3324 * opposed to decaring a local hashmap is for convenience3325 * so that we don't have to pass it to around.3326 */3327hashmap_init(&opt->current_file_dir_set, path_hashmap_cmp, NULL,512);3328get_files_dirs(opt, head);3329get_files_dirs(opt, merge);33303331 entries =get_unmerged(opt->repo->index);3332 clean =detect_and_process_renames(opt, common, head, merge,3333 entries, &re_info);3334record_df_conflict_files(opt, entries);3335if(clean <0)3336goto cleanup;3337for(i = entries->nr-1;0<= i; i--) {3338const char*path = entries->items[i].string;3339struct stage_data *e = entries->items[i].util;3340if(!e->processed) {3341int ret =process_entry(opt, path, e);3342if(!ret)3343 clean =0;3344else if(ret <0) {3345 clean = ret;3346goto cleanup;3347}3348}3349}3350for(i =0; i < entries->nr; i++) {3351struct stage_data *e = entries->items[i].util;3352if(!e->processed)3353BUG("unprocessed path???%s",3354 entries->items[i].string);3355}33563357 cleanup:3358final_cleanup_renames(&re_info);33593360string_list_clear(entries,1);3361free(entries);33623363hashmap_free(&opt->current_file_dir_set,1);33643365if(clean <0) {3366unpack_trees_finish(opt);3367return clean;3368}3369}3370else3371 clean =1;33723373unpack_trees_finish(opt);33743375if(opt->call_depth && !(*result =write_tree_from_memory(opt)))3376return-1;33773378return clean;3379}33803381static struct commit_list *reverse_commit_list(struct commit_list *list)3382{3383struct commit_list *next = NULL, *current, *backup;3384for(current = list; current; current = backup) {3385 backup = current->next;3386 current->next = next;3387 next = current;3388}3389return next;3390}33913392/*3393 * Merge the commits h1 and h2, return the resulting virtual3394 * commit object and a flag indicating the cleanness of the merge.3395 */3396intmerge_recursive(struct merge_options *opt,3397struct commit *h1,3398struct commit *h2,3399struct commit_list *ca,3400struct commit **result)3401{3402struct commit_list *iter;3403struct commit *merged_common_ancestors;3404struct tree *mrtree;3405int clean;34063407if(show(opt,4)) {3408output(opt,4,_("Merging:"));3409output_commit_title(opt, h1);3410output_commit_title(opt, h2);3411}34123413if(!ca) {3414 ca =get_merge_bases(h1, h2);3415 ca =reverse_commit_list(ca);3416}34173418if(show(opt,5)) {3419unsigned cnt =commit_list_count(ca);34203421output(opt,5,Q_("found%ucommon ancestor:",3422"found%ucommon ancestors:", cnt), cnt);3423for(iter = ca; iter; iter = iter->next)3424output_commit_title(opt, iter->item);3425}34263427 merged_common_ancestors =pop_commit(&ca);3428if(merged_common_ancestors == NULL) {3429/* if there is no common ancestor, use an empty tree */3430struct tree *tree;34313432 tree =lookup_tree(opt->repo, opt->repo->hash_algo->empty_tree);3433 merged_common_ancestors =make_virtual_commit(opt->repo, tree,"ancestor");3434}34353436for(iter = ca; iter; iter = iter->next) {3437const char*saved_b1, *saved_b2;3438 opt->call_depth++;3439/*3440 * When the merge fails, the result contains files3441 * with conflict markers. The cleanness flag is3442 * ignored (unless indicating an error), it was never3443 * actually used, as result of merge_trees has always3444 * overwritten it: the committed "conflicts" were3445 * already resolved.3446 */3447discard_index(opt->repo->index);3448 saved_b1 = opt->branch1;3449 saved_b2 = opt->branch2;3450 opt->branch1 ="Temporary merge branch 1";3451 opt->branch2 ="Temporary merge branch 2";3452if(merge_recursive(opt, merged_common_ancestors, iter->item,3453 NULL, &merged_common_ancestors) <0)3454return-1;3455 opt->branch1 = saved_b1;3456 opt->branch2 = saved_b2;3457 opt->call_depth--;34583459if(!merged_common_ancestors)3460returnerr(opt,_("merge returned no commit"));3461}34623463discard_index(opt->repo->index);3464if(!opt->call_depth)3465repo_read_index(opt->repo);34663467 opt->ancestor ="merged common ancestors";3468 clean =merge_trees(opt,get_commit_tree(h1),get_commit_tree(h2),3469get_commit_tree(merged_common_ancestors),3470&mrtree);3471if(clean <0) {3472flush_output(opt);3473return clean;3474}34753476if(opt->call_depth) {3477*result =make_virtual_commit(opt->repo, mrtree,"merged tree");3478commit_list_insert(h1, &(*result)->parents);3479commit_list_insert(h2, &(*result)->parents->next);3480}3481flush_output(opt);3482if(!opt->call_depth && opt->buffer_output <2)3483strbuf_release(&opt->obuf);3484if(show(opt,2))3485diff_warn_rename_limit("merge.renamelimit",3486 opt->needed_rename_limit,0);3487return clean;3488}34893490static struct commit *get_ref(struct repository *repo,const struct object_id *oid,3491const char*name)3492{3493struct object *object;34943495 object =deref_tag(repo,parse_object(repo, oid),3496 name,strlen(name));3497if(!object)3498return NULL;3499if(object->type == OBJ_TREE)3500returnmake_virtual_commit(repo, (struct tree*)object, name);3501if(object->type != OBJ_COMMIT)3502return NULL;3503if(parse_commit((struct commit *)object))3504return NULL;3505return(struct commit *)object;3506}35073508intmerge_recursive_generic(struct merge_options *opt,3509const struct object_id *head,3510const struct object_id *merge,3511int num_base_list,3512const struct object_id **base_list,3513struct commit **result)3514{3515int clean;3516struct lock_file lock = LOCK_INIT;3517struct commit *head_commit =get_ref(opt->repo, head, opt->branch1);3518struct commit *next_commit =get_ref(opt->repo, merge, opt->branch2);3519struct commit_list *ca = NULL;35203521if(base_list) {3522int i;3523for(i =0; i < num_base_list; ++i) {3524struct commit *base;3525if(!(base =get_ref(opt->repo, base_list[i],oid_to_hex(base_list[i]))))3526returnerr(opt,_("Could not parse object '%s'"),3527oid_to_hex(base_list[i]));3528commit_list_insert(base, &ca);3529}3530}35313532repo_hold_locked_index(opt->repo, &lock, LOCK_DIE_ON_ERROR);3533 clean =merge_recursive(opt, head_commit, next_commit, ca,3534 result);3535if(clean <0) {3536rollback_lock_file(&lock);3537return clean;3538}35393540if(write_locked_index(opt->repo->index, &lock,3541 COMMIT_LOCK | SKIP_IF_UNCHANGED))3542returnerr(opt,_("Unable to write index."));35433544return clean ?0:1;3545}35463547static voidmerge_recursive_config(struct merge_options *opt)3548{3549char*value = NULL;3550git_config_get_int("merge.verbosity", &opt->verbosity);3551git_config_get_int("diff.renamelimit", &opt->diff_rename_limit);3552git_config_get_int("merge.renamelimit", &opt->merge_rename_limit);3553if(!git_config_get_string("diff.renames", &value)) {3554 opt->diff_detect_rename =git_config_rename("diff.renames", value);3555free(value);3556}3557if(!git_config_get_string("merge.renames", &value)) {3558 opt->merge_detect_rename =git_config_rename("merge.renames", value);3559free(value);3560}3561git_config(git_xmerge_config, NULL);3562}35633564voidinit_merge_options(struct merge_options *opt,3565struct repository *repo)3566{3567const char*merge_verbosity;3568memset(opt,0,sizeof(struct merge_options));3569 opt->repo = repo;3570 opt->verbosity =2;3571 opt->buffer_output =1;3572 opt->diff_rename_limit = -1;3573 opt->merge_rename_limit = -1;3574 opt->renormalize =0;3575 opt->diff_detect_rename = -1;3576 opt->merge_detect_rename = -1;3577 opt->detect_directory_renames =1;3578merge_recursive_config(opt);3579 merge_verbosity =getenv("GIT_MERGE_VERBOSITY");3580if(merge_verbosity)3581 opt->verbosity =strtol(merge_verbosity, NULL,10);3582if(opt->verbosity >=5)3583 opt->buffer_output =0;3584strbuf_init(&opt->obuf,0);3585string_list_init(&opt->df_conflict_file_set,1);3586}35873588intparse_merge_opt(struct merge_options *opt,const char*s)3589{3590const char*arg;35913592if(!s || !*s)3593return-1;3594if(!strcmp(s,"ours"))3595 opt->recursive_variant = MERGE_RECURSIVE_OURS;3596else if(!strcmp(s,"theirs"))3597 opt->recursive_variant = MERGE_RECURSIVE_THEIRS;3598else if(!strcmp(s,"subtree"))3599 opt->subtree_shift ="";3600else if(skip_prefix(s,"subtree=", &arg))3601 opt->subtree_shift = arg;3602else if(!strcmp(s,"patience"))3603 opt->xdl_opts =DIFF_WITH_ALG(opt, PATIENCE_DIFF);3604else if(!strcmp(s,"histogram"))3605 opt->xdl_opts =DIFF_WITH_ALG(opt, HISTOGRAM_DIFF);3606else if(skip_prefix(s,"diff-algorithm=", &arg)) {3607long value =parse_algorithm_value(arg);3608if(value <0)3609return-1;3610/* clear out previous settings */3611DIFF_XDL_CLR(opt, NEED_MINIMAL);3612 opt->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;3613 opt->xdl_opts |= value;3614}3615else if(!strcmp(s,"ignore-space-change"))3616DIFF_XDL_SET(opt, IGNORE_WHITESPACE_CHANGE);3617else if(!strcmp(s,"ignore-all-space"))3618DIFF_XDL_SET(opt, IGNORE_WHITESPACE);3619else if(!strcmp(s,"ignore-space-at-eol"))3620DIFF_XDL_SET(opt, IGNORE_WHITESPACE_AT_EOL);3621else if(!strcmp(s,"ignore-cr-at-eol"))3622DIFF_XDL_SET(opt, IGNORE_CR_AT_EOL);3623else if(!strcmp(s,"renormalize"))3624 opt->renormalize =1;3625else if(!strcmp(s,"no-renormalize"))3626 opt->renormalize =0;3627else if(!strcmp(s,"no-renames"))3628 opt->merge_detect_rename =0;3629else if(!strcmp(s,"find-renames")) {3630 opt->merge_detect_rename =1;3631 opt->rename_score =0;3632}3633else if(skip_prefix(s,"find-renames=", &arg) ||3634skip_prefix(s,"rename-threshold=", &arg)) {3635if((opt->rename_score =parse_rename_score(&arg)) == -1|| *arg !=0)3636return-1;3637 opt->merge_detect_rename =1;3638}3639/*3640 * Please update $__git_merge_strategy_options in3641 * git-completion.bash when you add new options3642 */3643else3644return-1;3645return0;3646}