1/* 2 * Recursive Merge algorithm stolen from git-merge-recursive.py by 3 * Fredrik Kuivinen. 4 * The thieves were Alex Riesen and Johannes Schindelin, in June/July 2006 5 */ 6#include "cache.h" 7#include "config.h" 8#include "advice.h" 9#include "lockfile.h" 10#include "cache-tree.h" 11#include "commit.h" 12#include "blob.h" 13#include "builtin.h" 14#include "tree-walk.h" 15#include "diff.h" 16#include "diffcore.h" 17#include "tag.h" 18#include "unpack-trees.h" 19#include "string-list.h" 20#include "xdiff-interface.h" 21#include "ll-merge.h" 22#include "attr.h" 23#include "merge-recursive.h" 24#include "dir.h" 25#include "submodule.h" 26 27struct path_hashmap_entry { 28 struct hashmap_entry e; 29 char path[FLEX_ARRAY]; 30}; 31 32static int path_hashmap_cmp(const void *cmp_data, 33 const void *entry, 34 const void *entry_or_key, 35 const void *keydata) 36{ 37 const struct path_hashmap_entry *a = entry; 38 const struct path_hashmap_entry *b = entry_or_key; 39 const char *key = keydata; 40 41 if (ignore_case) 42 return strcasecmp(a->path, key ? key : b->path); 43 else 44 return strcmp(a->path, key ? key : b->path); 45} 46 47static unsigned int path_hash(const char *path) 48{ 49 return ignore_case ? strihash(path) : strhash(path); 50} 51 52static struct dir_rename_entry *dir_rename_find_entry(struct hashmap *hashmap, 53 char *dir) 54{ 55 struct dir_rename_entry key; 56 57 if (dir == NULL) 58 return NULL; 59 hashmap_entry_init(&key, strhash(dir)); 60 key.dir = dir; 61 return hashmap_get(hashmap, &key, NULL); 62} 63 64static int dir_rename_cmp(const void *unused_cmp_data, 65 const void *entry, 66 const void *entry_or_key, 67 const void *unused_keydata) 68{ 69 const struct dir_rename_entry *e1 = entry; 70 const struct dir_rename_entry *e2 = entry_or_key; 71 72 return strcmp(e1->dir, e2->dir); 73} 74 75static void dir_rename_init(struct hashmap *map) 76{ 77 hashmap_init(map, dir_rename_cmp, NULL, 0); 78} 79 80static void dir_rename_entry_init(struct dir_rename_entry *entry, 81 char *directory) 82{ 83 hashmap_entry_init(entry, strhash(directory)); 84 entry->dir = directory; 85 entry->non_unique_new_dir = 0; 86 strbuf_init(&entry->new_dir, 0); 87 string_list_init(&entry->possible_new_dirs, 0); 88} 89 90static struct collision_entry *collision_find_entry(struct hashmap *hashmap, 91 char *target_file) 92{ 93 struct collision_entry key; 94 95 hashmap_entry_init(&key, strhash(target_file)); 96 key.target_file = target_file; 97 return hashmap_get(hashmap, &key, NULL); 98} 99 100static int collision_cmp(void *unused_cmp_data, 101 const struct collision_entry *e1, 102 const struct collision_entry *e2, 103 const void *unused_keydata) 104{ 105 return strcmp(e1->target_file, e2->target_file); 106} 107 108static void collision_init(struct hashmap *map) 109{ 110 hashmap_init(map, (hashmap_cmp_fn) collision_cmp, NULL, 0); 111} 112 113static void flush_output(struct merge_options *o) 114{ 115 if (o->buffer_output < 2 && o->obuf.len) { 116 fputs(o->obuf.buf, stdout); 117 strbuf_reset(&o->obuf); 118 } 119} 120 121static int err(struct merge_options *o, const char *err, ...) 122{ 123 va_list params; 124 125 if (o->buffer_output < 2) 126 flush_output(o); 127 else { 128 strbuf_complete(&o->obuf, '\n'); 129 strbuf_addstr(&o->obuf, "error: "); 130 } 131 va_start(params, err); 132 strbuf_vaddf(&o->obuf, err, params); 133 va_end(params); 134 if (o->buffer_output > 1) 135 strbuf_addch(&o->obuf, '\n'); 136 else { 137 error("%s", o->obuf.buf); 138 strbuf_reset(&o->obuf); 139 } 140 141 return -1; 142} 143 144static struct tree *shift_tree_object(struct tree *one, struct tree *two, 145 const char *subtree_shift) 146{ 147 struct object_id shifted; 148 149 if (!*subtree_shift) { 150 shift_tree(&one->object.oid, &two->object.oid, &shifted, 0); 151 } else { 152 shift_tree_by(&one->object.oid, &two->object.oid, &shifted, 153 subtree_shift); 154 } 155 if (!oidcmp(&two->object.oid, &shifted)) 156 return two; 157 return lookup_tree(&shifted); 158} 159 160static struct commit *make_virtual_commit(struct tree *tree, const char *comment) 161{ 162 struct commit *commit = alloc_commit_node(); 163 164 set_merge_remote_desc(commit, comment, (struct object *)commit); 165 commit->tree = tree; 166 commit->object.parsed = 1; 167 return commit; 168} 169 170/* 171 * Since we use get_tree_entry(), which does not put the read object into 172 * the object pool, we cannot rely on a == b. 173 */ 174static int oid_eq(const struct object_id *a, const struct object_id *b) 175{ 176 if (!a && !b) 177 return 2; 178 return a && b && oidcmp(a, b) == 0; 179} 180 181enum rename_type { 182 RENAME_NORMAL = 0, 183 RENAME_DIR, 184 RENAME_DELETE, 185 RENAME_ONE_FILE_TO_ONE, 186 RENAME_ONE_FILE_TO_TWO, 187 RENAME_TWO_FILES_TO_ONE 188}; 189 190struct rename_conflict_info { 191 enum rename_type rename_type; 192 struct diff_filepair *pair1; 193 struct diff_filepair *pair2; 194 const char *branch1; 195 const char *branch2; 196 struct stage_data *dst_entry1; 197 struct stage_data *dst_entry2; 198 struct diff_filespec ren1_other; 199 struct diff_filespec ren2_other; 200}; 201 202/* 203 * Since we want to write the index eventually, we cannot reuse the index 204 * for these (temporary) data. 205 */ 206struct stage_data { 207 struct { 208 unsigned mode; 209 struct object_id oid; 210 } stages[4]; 211 struct rename_conflict_info *rename_conflict_info; 212 unsigned processed:1; 213}; 214 215static inline void setup_rename_conflict_info(enum rename_type rename_type, 216 struct diff_filepair *pair1, 217 struct diff_filepair *pair2, 218 const char *branch1, 219 const char *branch2, 220 struct stage_data *dst_entry1, 221 struct stage_data *dst_entry2, 222 struct merge_options *o, 223 struct stage_data *src_entry1, 224 struct stage_data *src_entry2) 225{ 226 struct rename_conflict_info *ci = xcalloc(1, sizeof(struct rename_conflict_info)); 227 ci->rename_type = rename_type; 228 ci->pair1 = pair1; 229 ci->branch1 = branch1; 230 ci->branch2 = branch2; 231 232 ci->dst_entry1 = dst_entry1; 233 dst_entry1->rename_conflict_info = ci; 234 dst_entry1->processed = 0; 235 236 assert(!pair2 == !dst_entry2); 237 if (dst_entry2) { 238 ci->dst_entry2 = dst_entry2; 239 ci->pair2 = pair2; 240 dst_entry2->rename_conflict_info = ci; 241 } 242 243 if (rename_type == RENAME_TWO_FILES_TO_ONE) { 244 /* 245 * For each rename, there could have been 246 * modifications on the side of history where that 247 * file was not renamed. 248 */ 249 int ostage1 = o->branch1 == branch1 ? 3 : 2; 250 int ostage2 = ostage1 ^ 1; 251 252 ci->ren1_other.path = pair1->one->path; 253 oidcpy(&ci->ren1_other.oid, &src_entry1->stages[ostage1].oid); 254 ci->ren1_other.mode = src_entry1->stages[ostage1].mode; 255 256 ci->ren2_other.path = pair2->one->path; 257 oidcpy(&ci->ren2_other.oid, &src_entry2->stages[ostage2].oid); 258 ci->ren2_other.mode = src_entry2->stages[ostage2].mode; 259 } 260} 261 262static int show(struct merge_options *o, int v) 263{ 264 return (!o->call_depth && o->verbosity >= v) || o->verbosity >= 5; 265} 266 267__attribute__((format (printf, 3, 4))) 268static void output(struct merge_options *o, int v, const char *fmt, ...) 269{ 270 va_list ap; 271 272 if (!show(o, v)) 273 return; 274 275 strbuf_addchars(&o->obuf, ' ', o->call_depth * 2); 276 277 va_start(ap, fmt); 278 strbuf_vaddf(&o->obuf, fmt, ap); 279 va_end(ap); 280 281 strbuf_addch(&o->obuf, '\n'); 282 if (!o->buffer_output) 283 flush_output(o); 284} 285 286static void output_commit_title(struct merge_options *o, struct commit *commit) 287{ 288 strbuf_addchars(&o->obuf, ' ', o->call_depth * 2); 289 if (commit->util) 290 strbuf_addf(&o->obuf, "virtual %s\n", 291 merge_remote_util(commit)->name); 292 else { 293 strbuf_add_unique_abbrev(&o->obuf, commit->object.oid.hash, 294 DEFAULT_ABBREV); 295 strbuf_addch(&o->obuf, ' '); 296 if (parse_commit(commit) != 0) 297 strbuf_addstr(&o->obuf, _("(bad commit)\n")); 298 else { 299 const char *title; 300 const char *msg = get_commit_buffer(commit, NULL); 301 int len = find_commit_subject(msg, &title); 302 if (len) 303 strbuf_addf(&o->obuf, "%.*s\n", len, title); 304 unuse_commit_buffer(commit, msg); 305 } 306 } 307 flush_output(o); 308} 309 310static int add_cacheinfo(struct merge_options *o, 311 unsigned int mode, const struct object_id *oid, 312 const char *path, int stage, int refresh, int options) 313{ 314 struct cache_entry *ce; 315 int ret; 316 317 ce = make_cache_entry(mode, oid ? oid->hash : null_sha1, path, stage, 0); 318 if (!ce) 319 return err(o, _("addinfo_cache failed for path '%s'"), path); 320 321 ret = add_cache_entry(ce, options); 322 if (refresh) { 323 struct cache_entry *nce; 324 325 nce = refresh_cache_entry(ce, CE_MATCH_REFRESH | CE_MATCH_IGNORE_MISSING); 326 if (!nce) 327 return err(o, _("addinfo_cache failed for path '%s'"), path); 328 if (nce != ce) 329 ret = add_cache_entry(nce, options); 330 } 331 return ret; 332} 333 334static void init_tree_desc_from_tree(struct tree_desc *desc, struct tree *tree) 335{ 336 parse_tree(tree); 337 init_tree_desc(desc, tree->buffer, tree->size); 338} 339 340static int git_merge_trees(struct merge_options *o, 341 struct tree *common, 342 struct tree *head, 343 struct tree *merge) 344{ 345 int rc; 346 struct tree_desc t[3]; 347 348 memset(&o->unpack_opts, 0, sizeof(o->unpack_opts)); 349 if (o->call_depth) 350 o->unpack_opts.index_only = 1; 351 else 352 o->unpack_opts.update = 1; 353 o->unpack_opts.merge = 1; 354 o->unpack_opts.head_idx = 2; 355 o->unpack_opts.fn = threeway_merge; 356 o->unpack_opts.src_index = &the_index; 357 o->unpack_opts.dst_index = &the_index; 358 setup_unpack_trees_porcelain(&o->unpack_opts, "merge"); 359 360 init_tree_desc_from_tree(t+0, common); 361 init_tree_desc_from_tree(t+1, head); 362 init_tree_desc_from_tree(t+2, merge); 363 364 rc = unpack_trees(3, t, &o->unpack_opts); 365 /* 366 * unpack_trees NULLifies src_index, but it's used in verify_uptodate, 367 * so set to the new index which will usually have modification 368 * timestamp info copied over. 369 */ 370 o->unpack_opts.src_index = &the_index; 371 cache_tree_free(&active_cache_tree); 372 return rc; 373} 374 375struct tree *write_tree_from_memory(struct merge_options *o) 376{ 377 struct tree *result = NULL; 378 379 if (unmerged_cache()) { 380 int i; 381 fprintf(stderr, "BUG: There are unmerged index entries:\n"); 382 for (i = 0; i < active_nr; i++) { 383 const struct cache_entry *ce = active_cache[i]; 384 if (ce_stage(ce)) 385 fprintf(stderr, "BUG: %d %.*s\n", ce_stage(ce), 386 (int)ce_namelen(ce), ce->name); 387 } 388 die("BUG: unmerged index entries in merge-recursive.c"); 389 } 390 391 if (!active_cache_tree) 392 active_cache_tree = cache_tree(); 393 394 if (!cache_tree_fully_valid(active_cache_tree) && 395 cache_tree_update(&the_index, 0) < 0) { 396 err(o, _("error building trees")); 397 return NULL; 398 } 399 400 result = lookup_tree(&active_cache_tree->oid); 401 402 return result; 403} 404 405static int save_files_dirs(const unsigned char *sha1, 406 struct strbuf *base, const char *path, 407 unsigned int mode, int stage, void *context) 408{ 409 struct path_hashmap_entry *entry; 410 int baselen = base->len; 411 struct merge_options *o = context; 412 413 strbuf_addstr(base, path); 414 415 FLEX_ALLOC_MEM(entry, path, base->buf, base->len); 416 hashmap_entry_init(entry, path_hash(entry->path)); 417 hashmap_add(&o->current_file_dir_set, entry); 418 419 strbuf_setlen(base, baselen); 420 return (S_ISDIR(mode) ? READ_TREE_RECURSIVE : 0); 421} 422 423static void get_files_dirs(struct merge_options *o, struct tree *tree) 424{ 425 struct pathspec match_all; 426 memset(&match_all, 0, sizeof(match_all)); 427 read_tree_recursive(tree, "", 0, 0, &match_all, save_files_dirs, o); 428} 429 430static int get_tree_entry_if_blob(const unsigned char *tree, 431 const char *path, 432 unsigned char *hashy, 433 unsigned int *mode_o) 434{ 435 int ret; 436 437 ret = get_tree_entry(tree, path, hashy, mode_o); 438 if (S_ISDIR(*mode_o)) { 439 hashcpy(hashy, null_sha1); 440 *mode_o = 0; 441 } 442 return ret; 443} 444 445/* 446 * Returns an index_entry instance which doesn't have to correspond to 447 * a real cache entry in Git's index. 448 */ 449static struct stage_data *insert_stage_data(const char *path, 450 struct tree *o, struct tree *a, struct tree *b, 451 struct string_list *entries) 452{ 453 struct string_list_item *item; 454 struct stage_data *e = xcalloc(1, sizeof(struct stage_data)); 455 get_tree_entry_if_blob(o->object.oid.hash, path, 456 e->stages[1].oid.hash, &e->stages[1].mode); 457 get_tree_entry_if_blob(a->object.oid.hash, path, 458 e->stages[2].oid.hash, &e->stages[2].mode); 459 get_tree_entry_if_blob(b->object.oid.hash, path, 460 e->stages[3].oid.hash, &e->stages[3].mode); 461 item = string_list_insert(entries, path); 462 item->util = e; 463 return e; 464} 465 466/* 467 * Create a dictionary mapping file names to stage_data objects. The 468 * dictionary contains one entry for every path with a non-zero stage entry. 469 */ 470static struct string_list *get_unmerged(void) 471{ 472 struct string_list *unmerged = xcalloc(1, sizeof(struct string_list)); 473 int i; 474 475 unmerged->strdup_strings = 1; 476 477 for (i = 0; i < active_nr; i++) { 478 struct string_list_item *item; 479 struct stage_data *e; 480 const struct cache_entry *ce = active_cache[i]; 481 if (!ce_stage(ce)) 482 continue; 483 484 item = string_list_lookup(unmerged, ce->name); 485 if (!item) { 486 item = string_list_insert(unmerged, ce->name); 487 item->util = xcalloc(1, sizeof(struct stage_data)); 488 } 489 e = item->util; 490 e->stages[ce_stage(ce)].mode = ce->ce_mode; 491 oidcpy(&e->stages[ce_stage(ce)].oid, &ce->oid); 492 } 493 494 return unmerged; 495} 496 497static int string_list_df_name_compare(const char *one, const char *two) 498{ 499 int onelen = strlen(one); 500 int twolen = strlen(two); 501 /* 502 * Here we only care that entries for D/F conflicts are 503 * adjacent, in particular with the file of the D/F conflict 504 * appearing before files below the corresponding directory. 505 * The order of the rest of the list is irrelevant for us. 506 * 507 * To achieve this, we sort with df_name_compare and provide 508 * the mode S_IFDIR so that D/F conflicts will sort correctly. 509 * We use the mode S_IFDIR for everything else for simplicity, 510 * since in other cases any changes in their order due to 511 * sorting cause no problems for us. 512 */ 513 int cmp = df_name_compare(one, onelen, S_IFDIR, 514 two, twolen, S_IFDIR); 515 /* 516 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure 517 * that 'foo' comes before 'foo/bar'. 518 */ 519 if (cmp) 520 return cmp; 521 return onelen - twolen; 522} 523 524static void record_df_conflict_files(struct merge_options *o, 525 struct string_list *entries) 526{ 527 /* If there is a D/F conflict and the file for such a conflict 528 * currently exist in the working tree, we want to allow it to be 529 * removed to make room for the corresponding directory if needed. 530 * The files underneath the directories of such D/F conflicts will 531 * be processed before the corresponding file involved in the D/F 532 * conflict. If the D/F directory ends up being removed by the 533 * merge, then we won't have to touch the D/F file. If the D/F 534 * directory needs to be written to the working copy, then the D/F 535 * file will simply be removed (in make_room_for_path()) to make 536 * room for the necessary paths. Note that if both the directory 537 * and the file need to be present, then the D/F file will be 538 * reinstated with a new unique name at the time it is processed. 539 */ 540 struct string_list df_sorted_entries = STRING_LIST_INIT_NODUP; 541 const char *last_file = NULL; 542 int last_len = 0; 543 int i; 544 545 /* 546 * If we're merging merge-bases, we don't want to bother with 547 * any working directory changes. 548 */ 549 if (o->call_depth) 550 return; 551 552 /* Ensure D/F conflicts are adjacent in the entries list. */ 553 for (i = 0; i < entries->nr; i++) { 554 struct string_list_item *next = &entries->items[i]; 555 string_list_append(&df_sorted_entries, next->string)->util = 556 next->util; 557 } 558 df_sorted_entries.cmp = string_list_df_name_compare; 559 string_list_sort(&df_sorted_entries); 560 561 string_list_clear(&o->df_conflict_file_set, 1); 562 for (i = 0; i < df_sorted_entries.nr; i++) { 563 const char *path = df_sorted_entries.items[i].string; 564 int len = strlen(path); 565 struct stage_data *e = df_sorted_entries.items[i].util; 566 567 /* 568 * Check if last_file & path correspond to a D/F conflict; 569 * i.e. whether path is last_file+'/'+<something>. 570 * If so, record that it's okay to remove last_file to make 571 * room for path and friends if needed. 572 */ 573 if (last_file && 574 len > last_len && 575 memcmp(path, last_file, last_len) == 0 && 576 path[last_len] == '/') { 577 string_list_insert(&o->df_conflict_file_set, last_file); 578 } 579 580 /* 581 * Determine whether path could exist as a file in the 582 * working directory as a possible D/F conflict. This 583 * will only occur when it exists in stage 2 as a 584 * file. 585 */ 586 if (S_ISREG(e->stages[2].mode) || S_ISLNK(e->stages[2].mode)) { 587 last_file = path; 588 last_len = len; 589 } else { 590 last_file = NULL; 591 } 592 } 593 string_list_clear(&df_sorted_entries, 0); 594} 595 596struct rename { 597 struct diff_filepair *pair; 598 /* 599 * Purpose of src_entry and dst_entry: 600 * 601 * If 'before' is renamed to 'after' then src_entry will contain 602 * the versions of 'before' from the merge_base, HEAD, and MERGE in 603 * stages 1, 2, and 3; dst_entry will contain the respective 604 * versions of 'after' in corresponding locations. Thus, we have a 605 * total of six modes and oids, though some will be null. (Stage 0 606 * is ignored; we're interested in handling conflicts.) 607 * 608 * Since we don't turn on break-rewrites by default, neither 609 * src_entry nor dst_entry can have all three of their stages have 610 * non-null oids, meaning at most four of the six will be non-null. 611 * Also, since this is a rename, both src_entry and dst_entry will 612 * have at least one non-null oid, meaning at least two will be 613 * non-null. Of the six oids, a typical rename will have three be 614 * non-null. Only two implies a rename/delete, and four implies a 615 * rename/add. 616 */ 617 struct stage_data *src_entry; 618 struct stage_data *dst_entry; 619 unsigned add_turned_into_rename:1; 620 unsigned processed:1; 621}; 622 623static int update_stages(struct merge_options *opt, const char *path, 624 const struct diff_filespec *o, 625 const struct diff_filespec *a, 626 const struct diff_filespec *b) 627{ 628 629 /* 630 * NOTE: It is usually a bad idea to call update_stages on a path 631 * before calling update_file on that same path, since it can 632 * sometimes lead to spurious "refusing to lose untracked file..." 633 * messages from update_file (via make_room_for path via 634 * would_lose_untracked). Instead, reverse the order of the calls 635 * (executing update_file first and then update_stages). 636 */ 637 int clear = 1; 638 int options = ADD_CACHE_OK_TO_ADD | ADD_CACHE_SKIP_DFCHECK; 639 if (clear) 640 if (remove_file_from_cache(path)) 641 return -1; 642 if (o) 643 if (add_cacheinfo(opt, o->mode, &o->oid, path, 1, 0, options)) 644 return -1; 645 if (a) 646 if (add_cacheinfo(opt, a->mode, &a->oid, path, 2, 0, options)) 647 return -1; 648 if (b) 649 if (add_cacheinfo(opt, b->mode, &b->oid, path, 3, 0, options)) 650 return -1; 651 return 0; 652} 653 654static int update_stages_for_stage_data(struct merge_options *opt, 655 const char *path, 656 const struct stage_data *stage_data) 657{ 658 struct diff_filespec o, a, b; 659 660 o.mode = stage_data->stages[1].mode; 661 oidcpy(&o.oid, &stage_data->stages[1].oid); 662 663 a.mode = stage_data->stages[2].mode; 664 oidcpy(&a.oid, &stage_data->stages[2].oid); 665 666 b.mode = stage_data->stages[3].mode; 667 oidcpy(&b.oid, &stage_data->stages[3].oid); 668 669 return update_stages(opt, path, 670 is_null_oid(&o.oid) ? NULL : &o, 671 is_null_oid(&a.oid) ? NULL : &a, 672 is_null_oid(&b.oid) ? NULL : &b); 673} 674 675static void update_entry(struct stage_data *entry, 676 struct diff_filespec *o, 677 struct diff_filespec *a, 678 struct diff_filespec *b) 679{ 680 entry->processed = 0; 681 entry->stages[1].mode = o->mode; 682 entry->stages[2].mode = a->mode; 683 entry->stages[3].mode = b->mode; 684 oidcpy(&entry->stages[1].oid, &o->oid); 685 oidcpy(&entry->stages[2].oid, &a->oid); 686 oidcpy(&entry->stages[3].oid, &b->oid); 687} 688 689static int remove_file(struct merge_options *o, int clean, 690 const char *path, int no_wd) 691{ 692 int update_cache = o->call_depth || clean; 693 int update_working_directory = !o->call_depth && !no_wd; 694 695 if (update_cache) { 696 if (remove_file_from_cache(path)) 697 return -1; 698 } 699 if (update_working_directory) { 700 if (ignore_case) { 701 struct cache_entry *ce; 702 ce = cache_file_exists(path, strlen(path), ignore_case); 703 if (ce && ce_stage(ce) == 0 && strcmp(path, ce->name)) 704 return 0; 705 } 706 if (remove_path(path)) 707 return -1; 708 } 709 return 0; 710} 711 712/* add a string to a strbuf, but converting "/" to "_" */ 713static void add_flattened_path(struct strbuf *out, const char *s) 714{ 715 size_t i = out->len; 716 strbuf_addstr(out, s); 717 for (; i < out->len; i++) 718 if (out->buf[i] == '/') 719 out->buf[i] = '_'; 720} 721 722static char *unique_path(struct merge_options *o, const char *path, const char *branch) 723{ 724 struct path_hashmap_entry *entry; 725 struct strbuf newpath = STRBUF_INIT; 726 int suffix = 0; 727 size_t base_len; 728 729 strbuf_addf(&newpath, "%s~", path); 730 add_flattened_path(&newpath, branch); 731 732 base_len = newpath.len; 733 while (hashmap_get_from_hash(&o->current_file_dir_set, 734 path_hash(newpath.buf), newpath.buf) || 735 (!o->call_depth && file_exists(newpath.buf))) { 736 strbuf_setlen(&newpath, base_len); 737 strbuf_addf(&newpath, "_%d", suffix++); 738 } 739 740 FLEX_ALLOC_MEM(entry, path, newpath.buf, newpath.len); 741 hashmap_entry_init(entry, path_hash(entry->path)); 742 hashmap_add(&o->current_file_dir_set, entry); 743 return strbuf_detach(&newpath, NULL); 744} 745 746/** 747 * Check whether a directory in the index is in the way of an incoming 748 * file. Return 1 if so. If check_working_copy is non-zero, also 749 * check the working directory. If empty_ok is non-zero, also return 750 * 0 in the case where the working-tree dir exists but is empty. 751 */ 752static int dir_in_way(const char *path, int check_working_copy, int empty_ok) 753{ 754 int pos; 755 struct strbuf dirpath = STRBUF_INIT; 756 struct stat st; 757 758 strbuf_addstr(&dirpath, path); 759 strbuf_addch(&dirpath, '/'); 760 761 pos = cache_name_pos(dirpath.buf, dirpath.len); 762 763 if (pos < 0) 764 pos = -1 - pos; 765 if (pos < active_nr && 766 !strncmp(dirpath.buf, active_cache[pos]->name, dirpath.len)) { 767 strbuf_release(&dirpath); 768 return 1; 769 } 770 771 strbuf_release(&dirpath); 772 return check_working_copy && !lstat(path, &st) && S_ISDIR(st.st_mode) && 773 !(empty_ok && is_empty_dir(path)); 774} 775 776static int was_tracked(const char *path) 777{ 778 int pos = cache_name_pos(path, strlen(path)); 779 780 if (0 <= pos) 781 /* we have been tracking this path */ 782 return 1; 783 784 /* 785 * Look for an unmerged entry for the path, 786 * specifically stage #2, which would indicate 787 * that "our" side before the merge started 788 * had the path tracked (and resulted in a conflict). 789 */ 790 for (pos = -1 - pos; 791 pos < active_nr && !strcmp(path, active_cache[pos]->name); 792 pos++) 793 if (ce_stage(active_cache[pos]) == 2) 794 return 1; 795 return 0; 796} 797 798static int would_lose_untracked(const char *path) 799{ 800 return !was_tracked(path) && file_exists(path); 801} 802 803static int was_dirty(struct merge_options *o, const char *path) 804{ 805 struct cache_entry *ce; 806 int dirty = 1; 807 808 if (o->call_depth || !was_tracked(path)) 809 return !dirty; 810 811 ce = cache_file_exists(path, strlen(path), ignore_case); 812 dirty = (ce->ce_stat_data.sd_mtime.sec > 0 && 813 verify_uptodate(ce, &o->unpack_opts) != 0); 814 return dirty; 815} 816 817static int make_room_for_path(struct merge_options *o, const char *path) 818{ 819 int status, i; 820 const char *msg = _("failed to create path '%s'%s"); 821 822 /* Unlink any D/F conflict files that are in the way */ 823 for (i = 0; i < o->df_conflict_file_set.nr; i++) { 824 const char *df_path = o->df_conflict_file_set.items[i].string; 825 size_t pathlen = strlen(path); 826 size_t df_pathlen = strlen(df_path); 827 if (df_pathlen < pathlen && 828 path[df_pathlen] == '/' && 829 strncmp(path, df_path, df_pathlen) == 0) { 830 output(o, 3, 831 _("Removing %s to make room for subdirectory\n"), 832 df_path); 833 unlink(df_path); 834 unsorted_string_list_delete_item(&o->df_conflict_file_set, 835 i, 0); 836 break; 837 } 838 } 839 840 /* Make sure leading directories are created */ 841 status = safe_create_leading_directories_const(path); 842 if (status) { 843 if (status == SCLD_EXISTS) 844 /* something else exists */ 845 return err(o, msg, path, _(": perhaps a D/F conflict?")); 846 return err(o, msg, path, ""); 847 } 848 849 /* 850 * Do not unlink a file in the work tree if we are not 851 * tracking it. 852 */ 853 if (would_lose_untracked(path)) 854 return err(o, _("refusing to lose untracked file at '%s'"), 855 path); 856 857 /* Successful unlink is good.. */ 858 if (!unlink(path)) 859 return 0; 860 /* .. and so is no existing file */ 861 if (errno == ENOENT) 862 return 0; 863 /* .. but not some other error (who really cares what?) */ 864 return err(o, msg, path, _(": perhaps a D/F conflict?")); 865} 866 867static int update_file_flags(struct merge_options *o, 868 const struct object_id *oid, 869 unsigned mode, 870 const char *path, 871 int update_cache, 872 int update_wd) 873{ 874 int ret = 0; 875 876 if (o->call_depth) 877 update_wd = 0; 878 879 if (update_wd) { 880 enum object_type type; 881 void *buf; 882 unsigned long size; 883 884 if (S_ISGITLINK(mode)) { 885 /* 886 * We may later decide to recursively descend into 887 * the submodule directory and update its index 888 * and/or work tree, but we do not do that now. 889 */ 890 update_wd = 0; 891 goto update_index; 892 } 893 894 buf = read_sha1_file(oid->hash, &type, &size); 895 if (!buf) 896 return err(o, _("cannot read object %s '%s'"), oid_to_hex(oid), path); 897 if (type != OBJ_BLOB) { 898 ret = err(o, _("blob expected for %s '%s'"), oid_to_hex(oid), path); 899 goto free_buf; 900 } 901 if (S_ISREG(mode)) { 902 struct strbuf strbuf = STRBUF_INIT; 903 if (convert_to_working_tree(path, buf, size, &strbuf)) { 904 free(buf); 905 size = strbuf.len; 906 buf = strbuf_detach(&strbuf, NULL); 907 } 908 } 909 910 if (make_room_for_path(o, path) < 0) { 911 update_wd = 0; 912 goto free_buf; 913 } 914 if (S_ISREG(mode) || (!has_symlinks && S_ISLNK(mode))) { 915 int fd; 916 if (mode & 0100) 917 mode = 0777; 918 else 919 mode = 0666; 920 fd = open(path, O_WRONLY | O_TRUNC | O_CREAT, mode); 921 if (fd < 0) { 922 ret = err(o, _("failed to open '%s': %s"), 923 path, strerror(errno)); 924 goto free_buf; 925 } 926 write_in_full(fd, buf, size); 927 close(fd); 928 } else if (S_ISLNK(mode)) { 929 char *lnk = xmemdupz(buf, size); 930 safe_create_leading_directories_const(path); 931 unlink(path); 932 if (symlink(lnk, path)) 933 ret = err(o, _("failed to symlink '%s': %s"), 934 path, strerror(errno)); 935 free(lnk); 936 } else 937 ret = err(o, 938 _("do not know what to do with %06o %s '%s'"), 939 mode, oid_to_hex(oid), path); 940 free_buf: 941 free(buf); 942 } 943 update_index: 944 if (!ret && update_cache) 945 add_cacheinfo(o, mode, oid, path, 0, update_wd, ADD_CACHE_OK_TO_ADD); 946 return ret; 947} 948 949static int update_file(struct merge_options *o, 950 int clean, 951 const struct object_id *oid, 952 unsigned mode, 953 const char *path) 954{ 955 return update_file_flags(o, oid, mode, path, o->call_depth || clean, !o->call_depth); 956} 957 958/* Low level file merging, update and removal */ 959 960struct merge_file_info { 961 struct object_id oid; 962 unsigned mode; 963 unsigned clean:1, 964 merge:1; 965}; 966 967static int merge_3way(struct merge_options *o, 968 mmbuffer_t *result_buf, 969 const struct diff_filespec *one, 970 const struct diff_filespec *a, 971 const struct diff_filespec *b, 972 const char *branch1, 973 const char *branch2) 974{ 975 mmfile_t orig, src1, src2; 976 struct ll_merge_options ll_opts = {0}; 977 char *base_name, *name1, *name2; 978 int merge_status; 979 980 ll_opts.renormalize = o->renormalize; 981 ll_opts.xdl_opts = o->xdl_opts; 982 983 if (o->call_depth) { 984 ll_opts.virtual_ancestor = 1; 985 ll_opts.variant = 0; 986 } else { 987 switch (o->recursive_variant) { 988 case MERGE_RECURSIVE_OURS: 989 ll_opts.variant = XDL_MERGE_FAVOR_OURS; 990 break; 991 case MERGE_RECURSIVE_THEIRS: 992 ll_opts.variant = XDL_MERGE_FAVOR_THEIRS; 993 break; 994 default: 995 ll_opts.variant = 0; 996 break; 997 } 998 } 9991000 if (strcmp(a->path, b->path) ||1001 (o->ancestor != NULL && strcmp(a->path, one->path) != 0)) {1002 base_name = o->ancestor == NULL ? NULL :1003 mkpathdup("%s:%s", o->ancestor, one->path);1004 name1 = mkpathdup("%s:%s", branch1, a->path);1005 name2 = mkpathdup("%s:%s", branch2, b->path);1006 } else {1007 base_name = o->ancestor == NULL ? NULL :1008 mkpathdup("%s", o->ancestor);1009 name1 = mkpathdup("%s", branch1);1010 name2 = mkpathdup("%s", branch2);1011 }10121013 read_mmblob(&orig, &one->oid);1014 read_mmblob(&src1, &a->oid);1015 read_mmblob(&src2, &b->oid);10161017 merge_status = ll_merge(result_buf, a->path, &orig, base_name,1018 &src1, name1, &src2, name2, &ll_opts);10191020 free(base_name);1021 free(name1);1022 free(name2);1023 free(orig.ptr);1024 free(src1.ptr);1025 free(src2.ptr);1026 return merge_status;1027}10281029static int merge_file_1(struct merge_options *o,1030 const struct diff_filespec *one,1031 const struct diff_filespec *a,1032 const struct diff_filespec *b,1033 const char *branch1,1034 const char *branch2,1035 struct merge_file_info *result)1036{1037 result->merge = 0;1038 result->clean = 1;10391040 if ((S_IFMT & a->mode) != (S_IFMT & b->mode)) {1041 result->clean = 0;1042 if (S_ISREG(a->mode)) {1043 result->mode = a->mode;1044 oidcpy(&result->oid, &a->oid);1045 } else {1046 result->mode = b->mode;1047 oidcpy(&result->oid, &b->oid);1048 }1049 } else {1050 if (!oid_eq(&a->oid, &one->oid) && !oid_eq(&b->oid, &one->oid))1051 result->merge = 1;10521053 /*1054 * Merge modes1055 */1056 if (a->mode == b->mode || a->mode == one->mode)1057 result->mode = b->mode;1058 else {1059 result->mode = a->mode;1060 if (b->mode != one->mode) {1061 result->clean = 0;1062 result->merge = 1;1063 }1064 }10651066 if (oid_eq(&a->oid, &b->oid) || oid_eq(&a->oid, &one->oid))1067 oidcpy(&result->oid, &b->oid);1068 else if (oid_eq(&b->oid, &one->oid))1069 oidcpy(&result->oid, &a->oid);1070 else if (S_ISREG(a->mode)) {1071 mmbuffer_t result_buf;1072 int ret = 0, merge_status;10731074 merge_status = merge_3way(o, &result_buf, one, a, b,1075 branch1, branch2);10761077 if ((merge_status < 0) || !result_buf.ptr)1078 ret = err(o, _("Failed to execute internal merge"));10791080 if (!ret && write_sha1_file(result_buf.ptr, result_buf.size,1081 blob_type, result->oid.hash))1082 ret = err(o, _("Unable to add %s to database"),1083 a->path);10841085 free(result_buf.ptr);1086 if (ret)1087 return ret;1088 result->clean = (merge_status == 0);1089 } else if (S_ISGITLINK(a->mode)) {1090 result->clean = merge_submodule(&result->oid,1091 one->path,1092 &one->oid,1093 &a->oid,1094 &b->oid,1095 !o->call_depth);1096 } else if (S_ISLNK(a->mode)) {1097 oidcpy(&result->oid, &a->oid);10981099 if (!oid_eq(&a->oid, &b->oid))1100 result->clean = 0;1101 } else1102 die("BUG: unsupported object type in the tree");1103 }11041105 return 0;1106}11071108static int merge_file_special_markers(struct merge_options *o,1109 const struct diff_filespec *one,1110 const struct diff_filespec *a,1111 const struct diff_filespec *b,1112 const char *branch1,1113 const char *filename1,1114 const char *branch2,1115 const char *filename2,1116 struct merge_file_info *mfi)1117{1118 char *side1 = NULL;1119 char *side2 = NULL;1120 int ret;11211122 if (filename1)1123 side1 = xstrfmt("%s:%s", branch1, filename1);1124 if (filename2)1125 side2 = xstrfmt("%s:%s", branch2, filename2);11261127 ret = merge_file_1(o, one, a, b,1128 side1 ? side1 : branch1,1129 side2 ? side2 : branch2, mfi);1130 free(side1);1131 free(side2);1132 return ret;1133}11341135static int merge_file_one(struct merge_options *o,1136 const char *path,1137 const struct object_id *o_oid, int o_mode,1138 const struct object_id *a_oid, int a_mode,1139 const struct object_id *b_oid, int b_mode,1140 const char *branch1,1141 const char *branch2,1142 struct merge_file_info *mfi)1143{1144 struct diff_filespec one, a, b;11451146 one.path = a.path = b.path = (char *)path;1147 oidcpy(&one.oid, o_oid);1148 one.mode = o_mode;1149 oidcpy(&a.oid, a_oid);1150 a.mode = a_mode;1151 oidcpy(&b.oid, b_oid);1152 b.mode = b_mode;1153 return merge_file_1(o, &one, &a, &b, branch1, branch2, mfi);1154}11551156static int conflict_rename_dir(struct merge_options *o,1157 struct diff_filepair *pair,1158 const char *rename_branch,1159 const char *other_branch)1160{1161 const struct diff_filespec *dest = pair->two;11621163 if (!o->call_depth && would_lose_untracked(dest->path)) {1164 char *alt_path = unique_path(o, dest->path, rename_branch);11651166 output(o, 1, _("Error: Refusing to lose untracked file at %s; "1167 "writing to %s instead."),1168 dest->path, alt_path);1169 /*1170 * Write the file in worktree at alt_path, but not in the1171 * index. Instead, write to dest->path for the index but1172 * only at the higher appropriate stage.1173 */1174 if (update_file(o, 0, &dest->oid, dest->mode, alt_path))1175 return -1;1176 free(alt_path);1177 return update_stages(o, dest->path, NULL,1178 rename_branch == o->branch1 ? dest : NULL,1179 rename_branch == o->branch1 ? NULL : dest);1180 }11811182 /* Update dest->path both in index and in worktree */1183 if (update_file(o, 1, &dest->oid, dest->mode, dest->path))1184 return -1;1185 return 0;1186}11871188static int handle_change_delete(struct merge_options *o,1189 const char *path, const char *old_path,1190 const struct object_id *o_oid, int o_mode,1191 const struct object_id *changed_oid,1192 int changed_mode,1193 const char *change_branch,1194 const char *delete_branch,1195 const char *change, const char *change_past)1196{1197 char *alt_path = NULL;1198 const char *update_path = path;1199 int ret = 0;12001201 if (dir_in_way(path, !o->call_depth, 0) ||1202 (!o->call_depth && would_lose_untracked(path))) {1203 update_path = alt_path = unique_path(o, path, change_branch);1204 }12051206 if (o->call_depth) {1207 /*1208 * We cannot arbitrarily accept either a_sha or b_sha as1209 * correct; since there is no true "middle point" between1210 * them, simply reuse the base version for virtual merge base.1211 */1212 ret = remove_file_from_cache(path);1213 if (!ret)1214 ret = update_file(o, 0, o_oid, o_mode, update_path);1215 } else {1216 if (!alt_path) {1217 if (!old_path) {1218 output(o, 1, _("CONFLICT (%s/delete): %s deleted in %s "1219 "and %s in %s. Version %s of %s left in tree."),1220 change, path, delete_branch, change_past,1221 change_branch, change_branch, path);1222 } else {1223 output(o, 1, _("CONFLICT (%s/delete): %s deleted in %s "1224 "and %s to %s in %s. Version %s of %s left in tree."),1225 change, old_path, delete_branch, change_past, path,1226 change_branch, change_branch, path);1227 }1228 } else {1229 if (!old_path) {1230 output(o, 1, _("CONFLICT (%s/delete): %s deleted in %s "1231 "and %s in %s. Version %s of %s left in tree at %s."),1232 change, path, delete_branch, change_past,1233 change_branch, change_branch, path, alt_path);1234 } else {1235 output(o, 1, _("CONFLICT (%s/delete): %s deleted in %s "1236 "and %s to %s in %s. Version %s of %s left in tree at %s."),1237 change, old_path, delete_branch, change_past, path,1238 change_branch, change_branch, path, alt_path);1239 }1240 }1241 /*1242 * No need to call update_file() on path when change_branch ==1243 * o->branch1 && !alt_path, since that would needlessly touch1244 * path. We could call update_file_flags() with update_cache=01245 * and update_wd=0, but that's a no-op.1246 */1247 if (change_branch != o->branch1 || alt_path)1248 ret = update_file(o, 0, changed_oid, changed_mode, update_path);1249 }1250 free(alt_path);12511252 return ret;1253}12541255static int conflict_rename_delete(struct merge_options *o,1256 struct diff_filepair *pair,1257 const char *rename_branch,1258 const char *delete_branch)1259{1260 const struct diff_filespec *orig = pair->one;1261 const struct diff_filespec *dest = pair->two;12621263 if (handle_change_delete(o,1264 o->call_depth ? orig->path : dest->path,1265 o->call_depth ? NULL : orig->path,1266 &orig->oid, orig->mode,1267 &dest->oid, dest->mode,1268 rename_branch, delete_branch,1269 _("rename"), _("renamed")))1270 return -1;12711272 if (o->call_depth)1273 return remove_file_from_cache(dest->path);1274 else1275 return update_stages(o, dest->path, NULL,1276 rename_branch == o->branch1 ? dest : NULL,1277 rename_branch == o->branch1 ? NULL : dest);1278}12791280static struct diff_filespec *filespec_from_entry(struct diff_filespec *target,1281 struct stage_data *entry,1282 int stage)1283{1284 struct object_id *oid = &entry->stages[stage].oid;1285 unsigned mode = entry->stages[stage].mode;1286 if (mode == 0 || is_null_oid(oid))1287 return NULL;1288 oidcpy(&target->oid, oid);1289 target->mode = mode;1290 return target;1291}12921293static int handle_file(struct merge_options *o,1294 struct diff_filespec *rename,1295 int stage,1296 struct rename_conflict_info *ci)1297{1298 char *dst_name = rename->path;1299 struct stage_data *dst_entry;1300 const char *cur_branch, *other_branch;1301 struct diff_filespec other;1302 struct diff_filespec *add;1303 int ret;13041305 if (stage == 2) {1306 dst_entry = ci->dst_entry1;1307 cur_branch = ci->branch1;1308 other_branch = ci->branch2;1309 } else {1310 dst_entry = ci->dst_entry2;1311 cur_branch = ci->branch2;1312 other_branch = ci->branch1;1313 }13141315 add = filespec_from_entry(&other, dst_entry, stage ^ 1);1316 if (add) {1317 char *add_name = unique_path(o, rename->path, other_branch);1318 if (update_file(o, 0, &add->oid, add->mode, add_name))1319 return -1;13201321 remove_file(o, 0, rename->path, 0);1322 dst_name = unique_path(o, rename->path, cur_branch);1323 } else {1324 if (dir_in_way(rename->path, !o->call_depth, 0)) {1325 dst_name = unique_path(o, rename->path, cur_branch);1326 output(o, 1, _("%s is a directory in %s adding as %s instead"),1327 rename->path, other_branch, dst_name);1328 } else if (!o->call_depth &&1329 would_lose_untracked(rename->path)) {1330 dst_name = unique_path(o, rename->path, cur_branch);1331 output(o, 1, _("Refusing to lose untracked file at %s; "1332 "adding as %s instead"),1333 rename->path, dst_name);1334 }1335 }1336 if ((ret = update_file(o, 0, &rename->oid, rename->mode, dst_name)))1337 ; /* fall through, do allow dst_name to be released */1338 else if (stage == 2)1339 ret = update_stages(o, rename->path, NULL, rename, add);1340 else1341 ret = update_stages(o, rename->path, NULL, add, rename);13421343 if (dst_name != rename->path)1344 free(dst_name);13451346 return ret;1347}13481349static int conflict_rename_rename_1to2(struct merge_options *o,1350 struct rename_conflict_info *ci)1351{1352 /* One file was renamed in both branches, but to different names. */1353 struct diff_filespec *one = ci->pair1->one;1354 struct diff_filespec *a = ci->pair1->two;1355 struct diff_filespec *b = ci->pair2->two;13561357 output(o, 1, _("CONFLICT (rename/rename): "1358 "Rename \"%s\"->\"%s\" in branch \"%s\" "1359 "rename \"%s\"->\"%s\" in \"%s\"%s"),1360 one->path, a->path, ci->branch1,1361 one->path, b->path, ci->branch2,1362 o->call_depth ? _(" (left unresolved)") : "");1363 if (o->call_depth) {1364 struct merge_file_info mfi;1365 struct diff_filespec other;1366 struct diff_filespec *add;1367 if (merge_file_one(o, one->path,1368 &one->oid, one->mode,1369 &a->oid, a->mode,1370 &b->oid, b->mode,1371 ci->branch1, ci->branch2, &mfi))1372 return -1;13731374 /*1375 * FIXME: For rename/add-source conflicts (if we could detect1376 * such), this is wrong. We should instead find a unique1377 * pathname and then either rename the add-source file to that1378 * unique path, or use that unique path instead of src here.1379 */1380 if (update_file(o, 0, &mfi.oid, mfi.mode, one->path))1381 return -1;13821383 /*1384 * Above, we put the merged content at the merge-base's1385 * path. Now we usually need to delete both a->path and1386 * b->path. However, the rename on each side of the merge1387 * could also be involved in a rename/add conflict. In1388 * such cases, we should keep the added file around,1389 * resolving the conflict at that path in its favor.1390 */1391 add = filespec_from_entry(&other, ci->dst_entry1, 2 ^ 1);1392 if (add) {1393 if (update_file(o, 0, &add->oid, add->mode, a->path))1394 return -1;1395 }1396 else1397 remove_file_from_cache(a->path);1398 add = filespec_from_entry(&other, ci->dst_entry2, 3 ^ 1);1399 if (add) {1400 if (update_file(o, 0, &add->oid, add->mode, b->path))1401 return -1;1402 }1403 else1404 remove_file_from_cache(b->path);1405 } else if (handle_file(o, a, 2, ci) || handle_file(o, b, 3, ci))1406 return -1;14071408 return 0;1409}14101411static int conflict_rename_rename_2to1(struct merge_options *o,1412 struct rename_conflict_info *ci)1413{1414 /* Two files, a & b, were renamed to the same thing, c. */1415 struct diff_filespec *a = ci->pair1->one;1416 struct diff_filespec *b = ci->pair2->one;1417 struct diff_filespec *c1 = ci->pair1->two;1418 struct diff_filespec *c2 = ci->pair2->two;1419 char *path = c1->path; /* == c2->path */1420 struct merge_file_info mfi_c1;1421 struct merge_file_info mfi_c2;1422 int ret;14231424 output(o, 1, _("CONFLICT (rename/rename): "1425 "Rename %s->%s in %s. "1426 "Rename %s->%s in %s"),1427 a->path, c1->path, ci->branch1,1428 b->path, c2->path, ci->branch2);14291430 remove_file(o, 1, a->path, o->call_depth || would_lose_untracked(a->path));1431 remove_file(o, 1, b->path, o->call_depth || would_lose_untracked(b->path));14321433 if (merge_file_special_markers(o, a, c1, &ci->ren1_other,1434 o->branch1, c1->path,1435 o->branch2, ci->ren1_other.path, &mfi_c1) ||1436 merge_file_special_markers(o, b, &ci->ren2_other, c2,1437 o->branch1, ci->ren2_other.path,1438 o->branch2, c2->path, &mfi_c2))1439 return -1;14401441 if (o->call_depth) {1442 /*1443 * If mfi_c1.clean && mfi_c2.clean, then it might make1444 * sense to do a two-way merge of those results. But, I1445 * think in all cases, it makes sense to have the virtual1446 * merge base just undo the renames; they can be detected1447 * again later for the non-recursive merge.1448 */1449 remove_file(o, 0, path, 0);1450 ret = update_file(o, 0, &mfi_c1.oid, mfi_c1.mode, a->path);1451 if (!ret)1452 ret = update_file(o, 0, &mfi_c2.oid, mfi_c2.mode,1453 b->path);1454 } else {1455 char *new_path1 = unique_path(o, path, ci->branch1);1456 char *new_path2 = unique_path(o, path, ci->branch2);1457 output(o, 1, _("Renaming %s to %s and %s to %s instead"),1458 a->path, new_path1, b->path, new_path2);1459 if (would_lose_untracked(path))1460 /*1461 * Only way we get here is if both renames were from1462 * a directory rename AND user had an untracked file1463 * at the location where both files end up after the1464 * two directory renames. See testcase 10d of t6043.1465 */1466 output(o, 1, _("Refusing to lose untracked file at "1467 "%s, even though it's in the way."),1468 path);1469 else1470 remove_file(o, 0, path, 0);1471 ret = update_file(o, 0, &mfi_c1.oid, mfi_c1.mode, new_path1);1472 if (!ret)1473 ret = update_file(o, 0, &mfi_c2.oid, mfi_c2.mode,1474 new_path2);1475 /*1476 * unpack_trees() actually populates the index for us for1477 * "normal" rename/rename(2to1) situtations so that the1478 * correct entries are at the higher stages, which would1479 * make the call below to update_stages_for_stage_data1480 * unnecessary. However, if either of the renames came1481 * from a directory rename, then unpack_trees() will not1482 * have gotten the right data loaded into the index, so we1483 * need to do so now. (While it'd be tempting to move this1484 * call to update_stages_for_stage_data() to1485 * apply_directory_rename_modifications(), that would break1486 * our intermediate calls to would_lose_untracked() since1487 * those rely on the current in-memory index. See also the1488 * big "NOTE" in update_stages()).1489 */1490 if (update_stages_for_stage_data(o, path, ci->dst_entry1))1491 ret = -1;14921493 free(new_path2);1494 free(new_path1);1495 }14961497 return ret;1498}14991500/*1501 * Get the diff_filepairs changed between o_tree and tree.1502 */1503static struct diff_queue_struct *get_diffpairs(struct merge_options *o,1504 struct tree *o_tree,1505 struct tree *tree)1506{1507 struct diff_queue_struct *ret;1508 struct diff_options opts;15091510 diff_setup(&opts);1511 opts.flags.recursive = 1;1512 opts.flags.rename_empty = 0;1513 opts.detect_rename = DIFF_DETECT_RENAME;1514 opts.rename_limit = o->merge_rename_limit >= 0 ? o->merge_rename_limit :1515 o->diff_rename_limit >= 0 ? o->diff_rename_limit :1516 1000;1517 opts.rename_score = o->rename_score;1518 opts.show_rename_progress = o->show_rename_progress;1519 opts.output_format = DIFF_FORMAT_NO_OUTPUT;1520 diff_setup_done(&opts);1521 diff_tree_oid(&o_tree->object.oid, &tree->object.oid, "", &opts);1522 diffcore_std(&opts);1523 if (opts.needed_rename_limit > o->needed_rename_limit)1524 o->needed_rename_limit = opts.needed_rename_limit;15251526 ret = xmalloc(sizeof(*ret));1527 *ret = diff_queued_diff;15281529 opts.output_format = DIFF_FORMAT_NO_OUTPUT;1530 diff_queued_diff.nr = 0;1531 diff_queued_diff.queue = NULL;1532 diff_flush(&opts);1533 return ret;1534}15351536static int tree_has_path(struct tree *tree, const char *path)1537{1538 unsigned char hashy[GIT_MAX_RAWSZ];1539 unsigned int mode_o;15401541 return !get_tree_entry(tree->object.oid.hash, path,1542 hashy, &mode_o);1543}15441545/*1546 * Return a new string that replaces the beginning portion (which matches1547 * entry->dir), with entry->new_dir. In perl-speak:1548 * new_path_name = (old_path =~ s/entry->dir/entry->new_dir/);1549 * NOTE:1550 * Caller must ensure that old_path starts with entry->dir + '/'.1551 */1552static char *apply_dir_rename(struct dir_rename_entry *entry,1553 const char *old_path)1554{1555 struct strbuf new_path = STRBUF_INIT;1556 int oldlen, newlen;15571558 if (entry->non_unique_new_dir)1559 return NULL;15601561 oldlen = strlen(entry->dir);1562 newlen = entry->new_dir.len + (strlen(old_path) - oldlen) + 1;1563 strbuf_grow(&new_path, newlen);1564 strbuf_addbuf(&new_path, &entry->new_dir);1565 strbuf_addstr(&new_path, &old_path[oldlen]);15661567 return strbuf_detach(&new_path, NULL);1568}15691570static void get_renamed_dir_portion(const char *old_path, const char *new_path,1571 char **old_dir, char **new_dir)1572{1573 char *end_of_old, *end_of_new;1574 int old_len, new_len;15751576 *old_dir = NULL;1577 *new_dir = NULL;15781579 /*1580 * For1581 * "a/b/c/d/e/foo.c" -> "a/b/some/thing/else/e/foo.c"1582 * the "e/foo.c" part is the same, we just want to know that1583 * "a/b/c/d" was renamed to "a/b/some/thing/else"1584 * so, for this example, this function returns "a/b/c/d" in1585 * *old_dir and "a/b/some/thing/else" in *new_dir.1586 *1587 * Also, if the basename of the file changed, we don't care. We1588 * want to know which portion of the directory, if any, changed.1589 */1590 end_of_old = strrchr(old_path, '/');1591 end_of_new = strrchr(new_path, '/');15921593 if (end_of_old == NULL || end_of_new == NULL)1594 return;1595 while (*--end_of_new == *--end_of_old &&1596 end_of_old != old_path &&1597 end_of_new != new_path)1598 ; /* Do nothing; all in the while loop */1599 /*1600 * We've found the first non-matching character in the directory1601 * paths. That means the current directory we were comparing1602 * represents the rename. Move end_of_old and end_of_new back1603 * to the full directory name.1604 */1605 if (*end_of_old == '/')1606 end_of_old++;1607 if (*end_of_old != '/')1608 end_of_new++;1609 end_of_old = strchr(end_of_old, '/');1610 end_of_new = strchr(end_of_new, '/');16111612 /*1613 * It may have been the case that old_path and new_path were the same1614 * directory all along. Don't claim a rename if they're the same.1615 */1616 old_len = end_of_old - old_path;1617 new_len = end_of_new - new_path;16181619 if (old_len != new_len || strncmp(old_path, new_path, old_len)) {1620 *old_dir = xstrndup(old_path, old_len);1621 *new_dir = xstrndup(new_path, new_len);1622 }1623}16241625static void remove_hashmap_entries(struct hashmap *dir_renames,1626 struct string_list *items_to_remove)1627{1628 int i;1629 struct dir_rename_entry *entry;16301631 for (i = 0; i < items_to_remove->nr; i++) {1632 entry = items_to_remove->items[i].util;1633 hashmap_remove(dir_renames, entry, NULL);1634 }1635 string_list_clear(items_to_remove, 0);1636}16371638/*1639 * See if there is a directory rename for path, and if there are any file1640 * level conflicts for the renamed location. If there is a rename and1641 * there are no conflicts, return the new name. Otherwise, return NULL.1642 */1643static char *handle_path_level_conflicts(struct merge_options *o,1644 const char *path,1645 struct dir_rename_entry *entry,1646 struct hashmap *collisions,1647 struct tree *tree)1648{1649 char *new_path = NULL;1650 struct collision_entry *collision_ent;1651 int clean = 1;1652 struct strbuf collision_paths = STRBUF_INIT;16531654 /*1655 * entry has the mapping of old directory name to new directory name1656 * that we want to apply to path.1657 */1658 new_path = apply_dir_rename(entry, path);16591660 if (!new_path) {1661 /* This should only happen when entry->non_unique_new_dir set */1662 if (!entry->non_unique_new_dir)1663 BUG("entry->non_unqiue_dir not set and !new_path");1664 output(o, 1, _("CONFLICT (directory rename split): "1665 "Unclear where to place %s because directory "1666 "%s was renamed to multiple other directories, "1667 "with no destination getting a majority of the "1668 "files."),1669 path, entry->dir);1670 clean = 0;1671 return NULL;1672 }16731674 /*1675 * The caller needs to have ensured that it has pre-populated1676 * collisions with all paths that map to new_path. Do a quick check1677 * to ensure that's the case.1678 */1679 collision_ent = collision_find_entry(collisions, new_path);1680 if (collision_ent == NULL)1681 BUG("collision_ent is NULL");16821683 /*1684 * Check for one-sided add/add/.../add conflicts, i.e.1685 * where implicit renames from the other side doing1686 * directory rename(s) can affect this side of history1687 * to put multiple paths into the same location. Warn1688 * and bail on directory renames for such paths.1689 */1690 if (collision_ent->reported_already) {1691 clean = 0;1692 } else if (tree_has_path(tree, new_path)) {1693 collision_ent->reported_already = 1;1694 strbuf_add_separated_string_list(&collision_paths, ", ",1695 &collision_ent->source_files);1696 output(o, 1, _("CONFLICT (implicit dir rename): Existing "1697 "file/dir at %s in the way of implicit "1698 "directory rename(s) putting the following "1699 "path(s) there: %s."),1700 new_path, collision_paths.buf);1701 clean = 0;1702 } else if (collision_ent->source_files.nr > 1) {1703 collision_ent->reported_already = 1;1704 strbuf_add_separated_string_list(&collision_paths, ", ",1705 &collision_ent->source_files);1706 output(o, 1, _("CONFLICT (implicit dir rename): Cannot map "1707 "more than one path to %s; implicit directory "1708 "renames tried to put these paths there: %s"),1709 new_path, collision_paths.buf);1710 clean = 0;1711 }17121713 /* Free memory we no longer need */1714 strbuf_release(&collision_paths);1715 if (!clean && new_path) {1716 free(new_path);1717 return NULL;1718 }17191720 return new_path;1721}17221723/*1724 * There are a couple things we want to do at the directory level:1725 * 1. Check for both sides renaming to the same thing, in order to avoid1726 * implicit renaming of files that should be left in place. (See1727 * testcase 6b in t6043 for details.)1728 * 2. Prune directory renames if there are still files left in the1729 * the original directory. These represent a partial directory rename,1730 * i.e. a rename where only some of the files within the directory1731 * were renamed elsewhere. (Technically, this could be done earlier1732 * in get_directory_renames(), except that would prevent us from1733 * doing the previous check and thus failing testcase 6b.)1734 * 3. Check for rename/rename(1to2) conflicts (at the directory level).1735 * In the future, we could potentially record this info as well and1736 * omit reporting rename/rename(1to2) conflicts for each path within1737 * the affected directories, thus cleaning up the merge output.1738 * NOTE: We do NOT check for rename/rename(2to1) conflicts at the1739 * directory level, because merging directories is fine. If it1740 * causes conflicts for files within those merged directories, then1741 * that should be detected at the individual path level.1742 */1743static void handle_directory_level_conflicts(struct merge_options *o,1744 struct hashmap *dir_re_head,1745 struct tree *head,1746 struct hashmap *dir_re_merge,1747 struct tree *merge)1748{1749 struct hashmap_iter iter;1750 struct dir_rename_entry *head_ent;1751 struct dir_rename_entry *merge_ent;17521753 struct string_list remove_from_head = STRING_LIST_INIT_NODUP;1754 struct string_list remove_from_merge = STRING_LIST_INIT_NODUP;17551756 hashmap_iter_init(dir_re_head, &iter);1757 while ((head_ent = hashmap_iter_next(&iter))) {1758 merge_ent = dir_rename_find_entry(dir_re_merge, head_ent->dir);1759 if (merge_ent &&1760 !head_ent->non_unique_new_dir &&1761 !merge_ent->non_unique_new_dir &&1762 !strbuf_cmp(&head_ent->new_dir, &merge_ent->new_dir)) {1763 /* 1. Renamed identically; remove it from both sides */1764 string_list_append(&remove_from_head,1765 head_ent->dir)->util = head_ent;1766 strbuf_release(&head_ent->new_dir);1767 string_list_append(&remove_from_merge,1768 merge_ent->dir)->util = merge_ent;1769 strbuf_release(&merge_ent->new_dir);1770 } else if (tree_has_path(head, head_ent->dir)) {1771 /* 2. This wasn't a directory rename after all */1772 string_list_append(&remove_from_head,1773 head_ent->dir)->util = head_ent;1774 strbuf_release(&head_ent->new_dir);1775 }1776 }17771778 remove_hashmap_entries(dir_re_head, &remove_from_head);1779 remove_hashmap_entries(dir_re_merge, &remove_from_merge);17801781 hashmap_iter_init(dir_re_merge, &iter);1782 while ((merge_ent = hashmap_iter_next(&iter))) {1783 head_ent = dir_rename_find_entry(dir_re_head, merge_ent->dir);1784 if (tree_has_path(merge, merge_ent->dir)) {1785 /* 2. This wasn't a directory rename after all */1786 string_list_append(&remove_from_merge,1787 merge_ent->dir)->util = merge_ent;1788 } else if (head_ent &&1789 !head_ent->non_unique_new_dir &&1790 !merge_ent->non_unique_new_dir) {1791 /* 3. rename/rename(1to2) */1792 /*1793 * We can assume it's not rename/rename(1to1) because1794 * that was case (1), already checked above. So we1795 * know that head_ent->new_dir and merge_ent->new_dir1796 * are different strings.1797 */1798 output(o, 1, _("CONFLICT (rename/rename): "1799 "Rename directory %s->%s in %s. "1800 "Rename directory %s->%s in %s"),1801 head_ent->dir, head_ent->new_dir.buf, o->branch1,1802 head_ent->dir, merge_ent->new_dir.buf, o->branch2);1803 string_list_append(&remove_from_head,1804 head_ent->dir)->util = head_ent;1805 strbuf_release(&head_ent->new_dir);1806 string_list_append(&remove_from_merge,1807 merge_ent->dir)->util = merge_ent;1808 strbuf_release(&merge_ent->new_dir);1809 }1810 }18111812 remove_hashmap_entries(dir_re_head, &remove_from_head);1813 remove_hashmap_entries(dir_re_merge, &remove_from_merge);1814}18151816static struct hashmap *get_directory_renames(struct diff_queue_struct *pairs,1817 struct tree *tree)1818{1819 struct hashmap *dir_renames;1820 struct hashmap_iter iter;1821 struct dir_rename_entry *entry;1822 int i;18231824 /*1825 * Typically, we think of a directory rename as all files from a1826 * certain directory being moved to a target directory. However,1827 * what if someone first moved two files from the original1828 * directory in one commit, and then renamed the directory1829 * somewhere else in a later commit? At merge time, we just know1830 * that files from the original directory went to two different1831 * places, and that the bulk of them ended up in the same place.1832 * We want each directory rename to represent where the bulk of the1833 * files from that directory end up; this function exists to find1834 * where the bulk of the files went.1835 *1836 * The first loop below simply iterates through the list of file1837 * renames, finding out how often each directory rename pair1838 * possibility occurs.1839 */1840 dir_renames = xmalloc(sizeof(struct hashmap));1841 dir_rename_init(dir_renames);1842 for (i = 0; i < pairs->nr; ++i) {1843 struct string_list_item *item;1844 int *count;1845 struct diff_filepair *pair = pairs->queue[i];1846 char *old_dir, *new_dir;18471848 /* File not part of directory rename if it wasn't renamed */1849 if (pair->status != 'R')1850 continue;18511852 get_renamed_dir_portion(pair->one->path, pair->two->path,1853 &old_dir, &new_dir);1854 if (!old_dir)1855 /* Directory didn't change at all; ignore this one. */1856 continue;18571858 entry = dir_rename_find_entry(dir_renames, old_dir);1859 if (!entry) {1860 entry = xmalloc(sizeof(struct dir_rename_entry));1861 dir_rename_entry_init(entry, old_dir);1862 hashmap_put(dir_renames, entry);1863 } else {1864 free(old_dir);1865 }1866 item = string_list_lookup(&entry->possible_new_dirs, new_dir);1867 if (!item) {1868 item = string_list_insert(&entry->possible_new_dirs,1869 new_dir);1870 item->util = xcalloc(1, sizeof(int));1871 } else {1872 free(new_dir);1873 }1874 count = item->util;1875 *count += 1;1876 }18771878 /*1879 * For each directory with files moved out of it, we find out which1880 * target directory received the most files so we can declare it to1881 * be the "winning" target location for the directory rename. This1882 * winner gets recorded in new_dir. If there is no winner1883 * (multiple target directories received the same number of files),1884 * we set non_unique_new_dir. Once we've determined the winner (or1885 * that there is no winner), we no longer need possible_new_dirs.1886 */1887 hashmap_iter_init(dir_renames, &iter);1888 while ((entry = hashmap_iter_next(&iter))) {1889 int max = 0;1890 int bad_max = 0;1891 char *best = NULL;18921893 for (i = 0; i < entry->possible_new_dirs.nr; i++) {1894 int *count = entry->possible_new_dirs.items[i].util;18951896 if (*count == max)1897 bad_max = max;1898 else if (*count > max) {1899 max = *count;1900 best = entry->possible_new_dirs.items[i].string;1901 }1902 }1903 if (bad_max == max)1904 entry->non_unique_new_dir = 1;1905 else {1906 assert(entry->new_dir.len == 0);1907 strbuf_addstr(&entry->new_dir, best);1908 }1909 /*1910 * The relevant directory sub-portion of the original full1911 * filepaths were xstrndup'ed before inserting into1912 * possible_new_dirs, and instead of manually iterating the1913 * list and free'ing each, just lie and tell1914 * possible_new_dirs that it did the strdup'ing so that it1915 * will free them for us.1916 */1917 entry->possible_new_dirs.strdup_strings = 1;1918 string_list_clear(&entry->possible_new_dirs, 1);1919 }19201921 return dir_renames;1922}19231924static struct dir_rename_entry *check_dir_renamed(const char *path,1925 struct hashmap *dir_renames)1926{1927 char temp[PATH_MAX];1928 char *end;1929 struct dir_rename_entry *entry;19301931 strcpy(temp, path);1932 while ((end = strrchr(temp, '/'))) {1933 *end = '\0';1934 entry = dir_rename_find_entry(dir_renames, temp);1935 if (entry)1936 return entry;1937 }1938 return NULL;1939}19401941static void compute_collisions(struct hashmap *collisions,1942 struct hashmap *dir_renames,1943 struct diff_queue_struct *pairs)1944{1945 int i;19461947 /*1948 * Multiple files can be mapped to the same path due to directory1949 * renames done by the other side of history. Since that other1950 * side of history could have merged multiple directories into one,1951 * if our side of history added the same file basename to each of1952 * those directories, then all N of them would get implicitly1953 * renamed by the directory rename detection into the same path,1954 * and we'd get an add/add/.../add conflict, and all those adds1955 * from *this* side of history. This is not representable in the1956 * index, and users aren't going to easily be able to make sense of1957 * it. So we need to provide a good warning about what's1958 * happening, and fall back to no-directory-rename detection1959 * behavior for those paths.1960 *1961 * See testcases 9e and all of section 5 from t6043 for examples.1962 */1963 collision_init(collisions);19641965 for (i = 0; i < pairs->nr; ++i) {1966 struct dir_rename_entry *dir_rename_ent;1967 struct collision_entry *collision_ent;1968 char *new_path;1969 struct diff_filepair *pair = pairs->queue[i];19701971 if (pair->status == 'D')1972 continue;1973 dir_rename_ent = check_dir_renamed(pair->two->path,1974 dir_renames);1975 if (!dir_rename_ent)1976 continue;19771978 new_path = apply_dir_rename(dir_rename_ent, pair->two->path);1979 if (!new_path)1980 /*1981 * dir_rename_ent->non_unique_new_path is true, which1982 * means there is no directory rename for us to use,1983 * which means it won't cause us any additional1984 * collisions.1985 */1986 continue;1987 collision_ent = collision_find_entry(collisions, new_path);1988 if (!collision_ent) {1989 collision_ent = xcalloc(1,1990 sizeof(struct collision_entry));1991 hashmap_entry_init(collision_ent, strhash(new_path));1992 hashmap_put(collisions, collision_ent);1993 collision_ent->target_file = new_path;1994 } else {1995 free(new_path);1996 }1997 string_list_insert(&collision_ent->source_files,1998 pair->two->path);1999 }2000}20012002static char *check_for_directory_rename(struct merge_options *o,2003 const char *path,2004 struct tree *tree,2005 struct hashmap *dir_renames,2006 struct hashmap *dir_rename_exclusions,2007 struct hashmap *collisions,2008 int *clean_merge)2009{2010 char *new_path = NULL;2011 struct dir_rename_entry *entry = check_dir_renamed(path, dir_renames);2012 struct dir_rename_entry *oentry = NULL;20132014 if (!entry)2015 return new_path;20162017 /*2018 * This next part is a little weird. We do not want to do an2019 * implicit rename into a directory we renamed on our side, because2020 * that will result in a spurious rename/rename(1to2) conflict. An2021 * example:2022 * Base commit: dumbdir/afile, otherdir/bfile2023 * Side 1: smrtdir/afile, otherdir/bfile2024 * Side 2: dumbdir/afile, dumbdir/bfile2025 * Here, while working on Side 1, we could notice that otherdir was2026 * renamed/merged to dumbdir, and change the diff_filepair for2027 * otherdir/bfile into a rename into dumbdir/bfile. However, Side2028 * 2 will notice the rename from dumbdir to smrtdir, and do the2029 * transitive rename to move it from dumbdir/bfile to2030 * smrtdir/bfile. That gives us bfile in dumbdir vs being in2031 * smrtdir, a rename/rename(1to2) conflict. We really just want2032 * the file to end up in smrtdir. And the way to achieve that is2033 * to not let Side1 do the rename to dumbdir, since we know that is2034 * the source of one of our directory renames.2035 *2036 * That's why oentry and dir_rename_exclusions is here.2037 *2038 * As it turns out, this also prevents N-way transient rename2039 * confusion; See testcases 9c and 9d of t6043.2040 */2041 oentry = dir_rename_find_entry(dir_rename_exclusions, entry->new_dir.buf);2042 if (oentry) {2043 output(o, 1, _("WARNING: Avoiding applying %s -> %s rename "2044 "to %s, because %s itself was renamed."),2045 entry->dir, entry->new_dir.buf, path, entry->new_dir.buf);2046 } else {2047 new_path = handle_path_level_conflicts(o, path, entry,2048 collisions, tree);2049 *clean_merge &= (new_path != NULL);2050 }20512052 return new_path;2053}20542055static void apply_directory_rename_modifications(struct merge_options *o,2056 struct diff_filepair *pair,2057 char *new_path,2058 struct rename *re,2059 struct tree *tree,2060 struct tree *o_tree,2061 struct tree *a_tree,2062 struct tree *b_tree,2063 struct string_list *entries,2064 int *clean)2065{2066 struct string_list_item *item;2067 int stage = (tree == a_tree ? 2 : 3);20682069 /*2070 * In all cases where we can do directory rename detection,2071 * unpack_trees() will have read pair->two->path into the2072 * index and the working copy. We need to remove it so that2073 * we can instead place it at new_path. It is guaranteed to2074 * not be untracked (unpack_trees() would have errored out2075 * saying the file would have been overwritten), but it might2076 * be dirty, though.2077 */2078 remove_file(o, 1, pair->two->path, 0 /* no_wd */);20792080 /* Find or create a new re->dst_entry */2081 item = string_list_lookup(entries, new_path);2082 if (item) {2083 /*2084 * Since we're renaming on this side of history, and it's2085 * due to a directory rename on the other side of history2086 * (which we only allow when the directory in question no2087 * longer exists on the other side of history), the2088 * original entry for re->dst_entry is no longer2089 * necessary...2090 */2091 re->dst_entry->processed = 1;20922093 /*2094 * ...because we'll be using this new one.2095 */2096 re->dst_entry = item->util;2097 } else {2098 /*2099 * re->dst_entry is for the before-dir-rename path, and we2100 * need it to hold information for the after-dir-rename2101 * path. Before creating a new entry, we need to mark the2102 * old one as unnecessary (...unless it is shared by2103 * src_entry, i.e. this didn't use to be a rename, in which2104 * case we can just allow the normal processing to happen2105 * for it).2106 */2107 if (pair->status == 'R')2108 re->dst_entry->processed = 1;21092110 re->dst_entry = insert_stage_data(new_path,2111 o_tree, a_tree, b_tree,2112 entries);2113 item = string_list_insert(entries, new_path);2114 item->util = re->dst_entry;2115 }21162117 /*2118 * Update the stage_data with the information about the path we are2119 * moving into place. That slot will be empty and available for us2120 * to write to because of the collision checks in2121 * handle_path_level_conflicts(). In other words,2122 * re->dst_entry->stages[stage].oid will be the null_oid, so it's2123 * open for us to write to.2124 *2125 * It may be tempting to actually update the index at this point as2126 * well, using update_stages_for_stage_data(), but as per the big2127 * "NOTE" in update_stages(), doing so will modify the current2128 * in-memory index which will break calls to would_lose_untracked()2129 * that we need to make. Instead, we need to just make sure that2130 * the various conflict_rename_*() functions update the index2131 * explicitly rather than relying on unpack_trees() to have done it.2132 */2133 get_tree_entry(tree->object.oid.hash,2134 pair->two->path,2135 re->dst_entry->stages[stage].oid.hash,2136 &re->dst_entry->stages[stage].mode);21372138 /* Update pair status */2139 if (pair->status == 'A') {2140 /*2141 * Recording rename information for this add makes it look2142 * like a rename/delete conflict. Make sure we can2143 * correctly handle this as an add that was moved to a new2144 * directory instead of reporting a rename/delete conflict.2145 */2146 re->add_turned_into_rename = 1;2147 }2148 /*2149 * We don't actually look at pair->status again, but it seems2150 * pedagogically correct to adjust it.2151 */2152 pair->status = 'R';21532154 /*2155 * Finally, record the new location.2156 */2157 pair->two->path = new_path;2158}21592160/*2161 * Get information of all renames which occurred in 'pairs', making use of2162 * any implicit directory renames inferred from the other side of history.2163 * We need the three trees in the merge ('o_tree', 'a_tree' and 'b_tree')2164 * to be able to associate the correct cache entries with the rename2165 * information; tree is always equal to either a_tree or b_tree.2166 */2167static struct string_list *get_renames(struct merge_options *o,2168 struct diff_queue_struct *pairs,2169 struct hashmap *dir_renames,2170 struct hashmap *dir_rename_exclusions,2171 struct tree *tree,2172 struct tree *o_tree,2173 struct tree *a_tree,2174 struct tree *b_tree,2175 struct string_list *entries,2176 int *clean_merge)2177{2178 int i;2179 struct hashmap collisions;2180 struct hashmap_iter iter;2181 struct collision_entry *e;2182 struct string_list *renames;21832184 compute_collisions(&collisions, dir_renames, pairs);2185 renames = xcalloc(1, sizeof(struct string_list));21862187 for (i = 0; i < pairs->nr; ++i) {2188 struct string_list_item *item;2189 struct rename *re;2190 struct diff_filepair *pair = pairs->queue[i];2191 char *new_path; /* non-NULL only with directory renames */21922193 if (pair->status == 'D') {2194 diff_free_filepair(pair);2195 continue;2196 }2197 new_path = check_for_directory_rename(o, pair->two->path, tree,2198 dir_renames,2199 dir_rename_exclusions,2200 &collisions,2201 clean_merge);2202 if (pair->status != 'R' && !new_path) {2203 diff_free_filepair(pair);2204 continue;2205 }22062207 re = xmalloc(sizeof(*re));2208 re->processed = 0;2209 re->add_turned_into_rename = 0;2210 re->pair = pair;2211 item = string_list_lookup(entries, re->pair->one->path);2212 if (!item)2213 re->src_entry = insert_stage_data(re->pair->one->path,2214 o_tree, a_tree, b_tree, entries);2215 else2216 re->src_entry = item->util;22172218 item = string_list_lookup(entries, re->pair->two->path);2219 if (!item)2220 re->dst_entry = insert_stage_data(re->pair->two->path,2221 o_tree, a_tree, b_tree, entries);2222 else2223 re->dst_entry = item->util;2224 item = string_list_insert(renames, pair->one->path);2225 item->util = re;2226 if (new_path)2227 apply_directory_rename_modifications(o, pair, new_path,2228 re, tree, o_tree,2229 a_tree, b_tree,2230 entries,2231 clean_merge);2232 }22332234 hashmap_iter_init(&collisions, &iter);2235 while ((e = hashmap_iter_next(&iter))) {2236 free(e->target_file);2237 string_list_clear(&e->source_files, 0);2238 }2239 hashmap_free(&collisions, 1);2240 return renames;2241}22422243static int process_renames(struct merge_options *o,2244 struct string_list *a_renames,2245 struct string_list *b_renames)2246{2247 int clean_merge = 1, i, j;2248 struct string_list a_by_dst = STRING_LIST_INIT_NODUP;2249 struct string_list b_by_dst = STRING_LIST_INIT_NODUP;2250 const struct rename *sre;22512252 for (i = 0; i < a_renames->nr; i++) {2253 sre = a_renames->items[i].util;2254 string_list_insert(&a_by_dst, sre->pair->two->path)->util2255 = (void *)sre;2256 }2257 for (i = 0; i < b_renames->nr; i++) {2258 sre = b_renames->items[i].util;2259 string_list_insert(&b_by_dst, sre->pair->two->path)->util2260 = (void *)sre;2261 }22622263 for (i = 0, j = 0; i < a_renames->nr || j < b_renames->nr;) {2264 struct string_list *renames1, *renames2Dst;2265 struct rename *ren1 = NULL, *ren2 = NULL;2266 const char *branch1, *branch2;2267 const char *ren1_src, *ren1_dst;2268 struct string_list_item *lookup;22692270 if (i >= a_renames->nr) {2271 ren2 = b_renames->items[j++].util;2272 } else if (j >= b_renames->nr) {2273 ren1 = a_renames->items[i++].util;2274 } else {2275 int compare = strcmp(a_renames->items[i].string,2276 b_renames->items[j].string);2277 if (compare <= 0)2278 ren1 = a_renames->items[i++].util;2279 if (compare >= 0)2280 ren2 = b_renames->items[j++].util;2281 }22822283 /* TODO: refactor, so that 1/2 are not needed */2284 if (ren1) {2285 renames1 = a_renames;2286 renames2Dst = &b_by_dst;2287 branch1 = o->branch1;2288 branch2 = o->branch2;2289 } else {2290 renames1 = b_renames;2291 renames2Dst = &a_by_dst;2292 branch1 = o->branch2;2293 branch2 = o->branch1;2294 SWAP(ren2, ren1);2295 }22962297 if (ren1->processed)2298 continue;2299 ren1->processed = 1;2300 ren1->dst_entry->processed = 1;2301 /* BUG: We should only mark src_entry as processed if we2302 * are not dealing with a rename + add-source case.2303 */2304 ren1->src_entry->processed = 1;23052306 ren1_src = ren1->pair->one->path;2307 ren1_dst = ren1->pair->two->path;23082309 if (ren2) {2310 /* One file renamed on both sides */2311 const char *ren2_src = ren2->pair->one->path;2312 const char *ren2_dst = ren2->pair->two->path;2313 enum rename_type rename_type;2314 if (strcmp(ren1_src, ren2_src) != 0)2315 die("BUG: ren1_src != ren2_src");2316 ren2->dst_entry->processed = 1;2317 ren2->processed = 1;2318 if (strcmp(ren1_dst, ren2_dst) != 0) {2319 rename_type = RENAME_ONE_FILE_TO_TWO;2320 clean_merge = 0;2321 } else {2322 rename_type = RENAME_ONE_FILE_TO_ONE;2323 /* BUG: We should only remove ren1_src in2324 * the base stage (think of rename +2325 * add-source cases).2326 */2327 remove_file(o, 1, ren1_src, 1);2328 update_entry(ren1->dst_entry,2329 ren1->pair->one,2330 ren1->pair->two,2331 ren2->pair->two);2332 }2333 setup_rename_conflict_info(rename_type,2334 ren1->pair,2335 ren2->pair,2336 branch1,2337 branch2,2338 ren1->dst_entry,2339 ren2->dst_entry,2340 o,2341 NULL,2342 NULL);2343 } else if ((lookup = string_list_lookup(renames2Dst, ren1_dst))) {2344 /* Two different files renamed to the same thing */2345 char *ren2_dst;2346 ren2 = lookup->util;2347 ren2_dst = ren2->pair->two->path;2348 if (strcmp(ren1_dst, ren2_dst) != 0)2349 die("BUG: ren1_dst != ren2_dst");23502351 clean_merge = 0;2352 ren2->processed = 1;2353 /*2354 * BUG: We should only mark src_entry as processed2355 * if we are not dealing with a rename + add-source2356 * case.2357 */2358 ren2->src_entry->processed = 1;23592360 setup_rename_conflict_info(RENAME_TWO_FILES_TO_ONE,2361 ren1->pair,2362 ren2->pair,2363 branch1,2364 branch2,2365 ren1->dst_entry,2366 ren2->dst_entry,2367 o,2368 ren1->src_entry,2369 ren2->src_entry);23702371 } else {2372 /* Renamed in 1, maybe changed in 2 */2373 /* we only use sha1 and mode of these */2374 struct diff_filespec src_other, dst_other;2375 int try_merge;23762377 /*2378 * unpack_trees loads entries from common-commit2379 * into stage 1, from head-commit into stage 2, and2380 * from merge-commit into stage 3. We keep track2381 * of which side corresponds to the rename.2382 */2383 int renamed_stage = a_renames == renames1 ? 2 : 3;2384 int other_stage = a_renames == renames1 ? 3 : 2;23852386 /* BUG: We should only remove ren1_src in the base2387 * stage and in other_stage (think of rename +2388 * add-source case).2389 */2390 remove_file(o, 1, ren1_src,2391 renamed_stage == 2 || !was_tracked(ren1_src));23922393 oidcpy(&src_other.oid,2394 &ren1->src_entry->stages[other_stage].oid);2395 src_other.mode = ren1->src_entry->stages[other_stage].mode;2396 oidcpy(&dst_other.oid,2397 &ren1->dst_entry->stages[other_stage].oid);2398 dst_other.mode = ren1->dst_entry->stages[other_stage].mode;2399 try_merge = 0;24002401 if (oid_eq(&src_other.oid, &null_oid) &&2402 ren1->add_turned_into_rename) {2403 setup_rename_conflict_info(RENAME_DIR,2404 ren1->pair,2405 NULL,2406 branch1,2407 branch2,2408 ren1->dst_entry,2409 NULL,2410 o,2411 NULL,2412 NULL);2413 } else if (oid_eq(&src_other.oid, &null_oid)) {2414 setup_rename_conflict_info(RENAME_DELETE,2415 ren1->pair,2416 NULL,2417 branch1,2418 branch2,2419 ren1->dst_entry,2420 NULL,2421 o,2422 NULL,2423 NULL);2424 } else if ((dst_other.mode == ren1->pair->two->mode) &&2425 oid_eq(&dst_other.oid, &ren1->pair->two->oid)) {2426 /*2427 * Added file on the other side identical to2428 * the file being renamed: clean merge.2429 * Also, there is no need to overwrite the2430 * file already in the working copy, so call2431 * update_file_flags() instead of2432 * update_file().2433 */2434 if (update_file_flags(o,2435 &ren1->pair->two->oid,2436 ren1->pair->two->mode,2437 ren1_dst,2438 1, /* update_cache */2439 0 /* update_wd */))2440 clean_merge = -1;2441 } else if (!oid_eq(&dst_other.oid, &null_oid)) {2442 clean_merge = 0;2443 try_merge = 1;2444 output(o, 1, _("CONFLICT (rename/add): Rename %s->%s in %s. "2445 "%s added in %s"),2446 ren1_src, ren1_dst, branch1,2447 ren1_dst, branch2);2448 if (o->call_depth) {2449 struct merge_file_info mfi;2450 if (merge_file_one(o, ren1_dst, &null_oid, 0,2451 &ren1->pair->two->oid,2452 ren1->pair->two->mode,2453 &dst_other.oid,2454 dst_other.mode,2455 branch1, branch2, &mfi)) {2456 clean_merge = -1;2457 goto cleanup_and_return;2458 }2459 output(o, 1, _("Adding merged %s"), ren1_dst);2460 if (update_file(o, 0, &mfi.oid,2461 mfi.mode, ren1_dst))2462 clean_merge = -1;2463 try_merge = 0;2464 } else {2465 char *new_path = unique_path(o, ren1_dst, branch2);2466 output(o, 1, _("Adding as %s instead"), new_path);2467 if (update_file(o, 0, &dst_other.oid,2468 dst_other.mode, new_path))2469 clean_merge = -1;2470 free(new_path);2471 }2472 } else2473 try_merge = 1;24742475 if (clean_merge < 0)2476 goto cleanup_and_return;2477 if (try_merge) {2478 struct diff_filespec *one, *a, *b;2479 src_other.path = (char *)ren1_src;24802481 one = ren1->pair->one;2482 if (a_renames == renames1) {2483 a = ren1->pair->two;2484 b = &src_other;2485 } else {2486 b = ren1->pair->two;2487 a = &src_other;2488 }2489 update_entry(ren1->dst_entry, one, a, b);2490 setup_rename_conflict_info(RENAME_NORMAL,2491 ren1->pair,2492 NULL,2493 branch1,2494 NULL,2495 ren1->dst_entry,2496 NULL,2497 o,2498 NULL,2499 NULL);2500 }2501 }2502 }2503cleanup_and_return:2504 string_list_clear(&a_by_dst, 0);2505 string_list_clear(&b_by_dst, 0);25062507 return clean_merge;2508}25092510struct rename_info {2511 struct string_list *head_renames;2512 struct string_list *merge_renames;2513};25142515static void initial_cleanup_rename(struct diff_queue_struct *pairs,2516 struct hashmap *dir_renames)2517{2518 struct hashmap_iter iter;2519 struct dir_rename_entry *e;25202521 hashmap_iter_init(dir_renames, &iter);2522 while ((e = hashmap_iter_next(&iter))) {2523 free(e->dir);2524 strbuf_release(&e->new_dir);2525 /* possible_new_dirs already cleared in get_directory_renames */2526 }2527 hashmap_free(dir_renames, 1);2528 free(dir_renames);25292530 free(pairs->queue);2531 free(pairs);2532}25332534static int handle_renames(struct merge_options *o,2535 struct tree *common,2536 struct tree *head,2537 struct tree *merge,2538 struct string_list *entries,2539 struct rename_info *ri)2540{2541 struct diff_queue_struct *head_pairs, *merge_pairs;2542 struct hashmap *dir_re_head, *dir_re_merge;2543 int clean = 1;25442545 ri->head_renames = NULL;2546 ri->merge_renames = NULL;25472548 if (!o->detect_rename)2549 return 1;25502551 head_pairs = get_diffpairs(o, common, head);2552 merge_pairs = get_diffpairs(o, common, merge);25532554 dir_re_head = get_directory_renames(head_pairs, head);2555 dir_re_merge = get_directory_renames(merge_pairs, merge);25562557 handle_directory_level_conflicts(o,2558 dir_re_head, head,2559 dir_re_merge, merge);25602561 ri->head_renames = get_renames(o, head_pairs,2562 dir_re_merge, dir_re_head, head,2563 common, head, merge, entries,2564 &clean);2565 if (clean < 0)2566 goto cleanup;2567 ri->merge_renames = get_renames(o, merge_pairs,2568 dir_re_head, dir_re_merge, merge,2569 common, head, merge, entries,2570 &clean);2571 if (clean < 0)2572 goto cleanup;2573 clean &= process_renames(o, ri->head_renames, ri->merge_renames);25742575cleanup:2576 /*2577 * Some cleanup is deferred until cleanup_renames() because the2578 * data structures are still needed and referenced in2579 * process_entry(). But there are a few things we can free now.2580 */2581 initial_cleanup_rename(head_pairs, dir_re_head);2582 initial_cleanup_rename(merge_pairs, dir_re_merge);25832584 return clean;2585}25862587static void final_cleanup_rename(struct string_list *rename)2588{2589 const struct rename *re;2590 int i;25912592 if (rename == NULL)2593 return;25942595 for (i = 0; i < rename->nr; i++) {2596 re = rename->items[i].util;2597 diff_free_filepair(re->pair);2598 }2599 string_list_clear(rename, 1);2600 free(rename);2601}26022603static void final_cleanup_renames(struct rename_info *re_info)2604{2605 final_cleanup_rename(re_info->head_renames);2606 final_cleanup_rename(re_info->merge_renames);2607}26082609static struct object_id *stage_oid(const struct object_id *oid, unsigned mode)2610{2611 return (is_null_oid(oid) || mode == 0) ? NULL: (struct object_id *)oid;2612}26132614static int read_oid_strbuf(struct merge_options *o,2615 const struct object_id *oid, struct strbuf *dst)2616{2617 void *buf;2618 enum object_type type;2619 unsigned long size;2620 buf = read_sha1_file(oid->hash, &type, &size);2621 if (!buf)2622 return err(o, _("cannot read object %s"), oid_to_hex(oid));2623 if (type != OBJ_BLOB) {2624 free(buf);2625 return err(o, _("object %s is not a blob"), oid_to_hex(oid));2626 }2627 strbuf_attach(dst, buf, size, size + 1);2628 return 0;2629}26302631static int blob_unchanged(struct merge_options *opt,2632 const struct object_id *o_oid,2633 unsigned o_mode,2634 const struct object_id *a_oid,2635 unsigned a_mode,2636 int renormalize, const char *path)2637{2638 struct strbuf o = STRBUF_INIT;2639 struct strbuf a = STRBUF_INIT;2640 int ret = 0; /* assume changed for safety */26412642 if (a_mode != o_mode)2643 return 0;2644 if (oid_eq(o_oid, a_oid))2645 return 1;2646 if (!renormalize)2647 return 0;26482649 assert(o_oid && a_oid);2650 if (read_oid_strbuf(opt, o_oid, &o) || read_oid_strbuf(opt, a_oid, &a))2651 goto error_return;2652 /*2653 * Note: binary | is used so that both renormalizations are2654 * performed. Comparison can be skipped if both files are2655 * unchanged since their sha1s have already been compared.2656 */2657 if (renormalize_buffer(&the_index, path, o.buf, o.len, &o) |2658 renormalize_buffer(&the_index, path, a.buf, a.len, &a))2659 ret = (o.len == a.len && !memcmp(o.buf, a.buf, o.len));26602661error_return:2662 strbuf_release(&o);2663 strbuf_release(&a);2664 return ret;2665}26662667static int handle_modify_delete(struct merge_options *o,2668 const char *path,2669 struct object_id *o_oid, int o_mode,2670 struct object_id *a_oid, int a_mode,2671 struct object_id *b_oid, int b_mode)2672{2673 const char *modify_branch, *delete_branch;2674 struct object_id *changed_oid;2675 int changed_mode;26762677 if (a_oid) {2678 modify_branch = o->branch1;2679 delete_branch = o->branch2;2680 changed_oid = a_oid;2681 changed_mode = a_mode;2682 } else {2683 modify_branch = o->branch2;2684 delete_branch = o->branch1;2685 changed_oid = b_oid;2686 changed_mode = b_mode;2687 }26882689 return handle_change_delete(o,2690 path, NULL,2691 o_oid, o_mode,2692 changed_oid, changed_mode,2693 modify_branch, delete_branch,2694 _("modify"), _("modified"));2695}26962697static int merge_content(struct merge_options *o,2698 const char *path,2699 int file_in_way,2700 struct object_id *o_oid, int o_mode,2701 struct object_id *a_oid, int a_mode,2702 struct object_id *b_oid, int b_mode,2703 struct rename_conflict_info *rename_conflict_info)2704{2705 const char *reason = _("content");2706 const char *path1 = NULL, *path2 = NULL;2707 struct merge_file_info mfi;2708 struct diff_filespec one, a, b;2709 unsigned df_conflict_remains = 0;27102711 if (!o_oid) {2712 reason = _("add/add");2713 o_oid = (struct object_id *)&null_oid;2714 }2715 one.path = a.path = b.path = (char *)path;2716 oidcpy(&one.oid, o_oid);2717 one.mode = o_mode;2718 oidcpy(&a.oid, a_oid);2719 a.mode = a_mode;2720 oidcpy(&b.oid, b_oid);2721 b.mode = b_mode;27222723 if (rename_conflict_info) {2724 struct diff_filepair *pair1 = rename_conflict_info->pair1;27252726 path1 = (o->branch1 == rename_conflict_info->branch1) ?2727 pair1->two->path : pair1->one->path;2728 /* If rename_conflict_info->pair2 != NULL, we are in2729 * RENAME_ONE_FILE_TO_ONE case. Otherwise, we have a2730 * normal rename.2731 */2732 path2 = (rename_conflict_info->pair2 ||2733 o->branch2 == rename_conflict_info->branch1) ?2734 pair1->two->path : pair1->one->path;27352736 if (dir_in_way(path, !o->call_depth,2737 S_ISGITLINK(pair1->two->mode)))2738 df_conflict_remains = 1;2739 }2740 if (merge_file_special_markers(o, &one, &a, &b,2741 o->branch1, path1,2742 o->branch2, path2, &mfi))2743 return -1;27442745 if (mfi.clean && !df_conflict_remains &&2746 oid_eq(&mfi.oid, a_oid) && mfi.mode == a_mode) {2747 int path_renamed_outside_HEAD;2748 output(o, 3, _("Skipped %s (merged same as existing)"), path);2749 /*2750 * The content merge resulted in the same file contents we2751 * already had. We can return early if those file contents2752 * are recorded at the correct path (which may not be true2753 * if the merge involves a rename).2754 */2755 path_renamed_outside_HEAD = !path2 || !strcmp(path, path2);2756 if (!path_renamed_outside_HEAD) {2757 add_cacheinfo(o, mfi.mode, &mfi.oid, path,2758 0, (!o->call_depth), 0);2759 return mfi.clean;2760 }2761 } else2762 output(o, 2, _("Auto-merging %s"), path);27632764 if (!mfi.clean) {2765 if (S_ISGITLINK(mfi.mode))2766 reason = _("submodule");2767 output(o, 1, _("CONFLICT (%s): Merge conflict in %s"),2768 reason, path);2769 if (rename_conflict_info && !df_conflict_remains)2770 if (update_stages(o, path, &one, &a, &b))2771 return -1;2772 }27732774 if (df_conflict_remains || file_in_way) {2775 char *new_path;2776 if (o->call_depth) {2777 remove_file_from_cache(path);2778 } else {2779 if (!mfi.clean) {2780 if (update_stages(o, path, &one, &a, &b))2781 return -1;2782 } else {2783 int file_from_stage2 = was_tracked(path);2784 struct diff_filespec merged;2785 oidcpy(&merged.oid, &mfi.oid);2786 merged.mode = mfi.mode;27872788 if (update_stages(o, path, NULL,2789 file_from_stage2 ? &merged : NULL,2790 file_from_stage2 ? NULL : &merged))2791 return -1;2792 }27932794 }2795 new_path = unique_path(o, path, rename_conflict_info->branch1);2796 output(o, 1, _("Adding as %s instead"), new_path);2797 if (update_file(o, 0, &mfi.oid, mfi.mode, new_path)) {2798 free(new_path);2799 return -1;2800 }2801 free(new_path);2802 mfi.clean = 0;2803 } else if (update_file(o, mfi.clean, &mfi.oid, mfi.mode, path))2804 return -1;2805 return mfi.clean;2806}28072808static int conflict_rename_normal(struct merge_options *o,2809 const char *path,2810 struct object_id *o_oid, unsigned int o_mode,2811 struct object_id *a_oid, unsigned int a_mode,2812 struct object_id *b_oid, unsigned int b_mode,2813 struct rename_conflict_info *ci)2814{2815 int clean_merge;2816 int file_in_the_way = 0;28172818 if (was_dirty(o, path)) {2819 file_in_the_way = 1;2820 output(o, 1, _("Refusing to lose dirty file at %s"), path);2821 }28222823 /* Merge the content and write it out */2824 clean_merge = merge_content(o, path, file_in_the_way,2825 o_oid, o_mode, a_oid, a_mode, b_oid, b_mode,2826 ci);2827 if (clean_merge > 0 && file_in_the_way)2828 clean_merge = 0;2829 return clean_merge;2830}28312832/* Per entry merge function */2833static int process_entry(struct merge_options *o,2834 const char *path, struct stage_data *entry)2835{2836 int clean_merge = 1;2837 int normalize = o->renormalize;2838 unsigned o_mode = entry->stages[1].mode;2839 unsigned a_mode = entry->stages[2].mode;2840 unsigned b_mode = entry->stages[3].mode;2841 struct object_id *o_oid = stage_oid(&entry->stages[1].oid, o_mode);2842 struct object_id *a_oid = stage_oid(&entry->stages[2].oid, a_mode);2843 struct object_id *b_oid = stage_oid(&entry->stages[3].oid, b_mode);28442845 entry->processed = 1;2846 if (entry->rename_conflict_info) {2847 struct rename_conflict_info *conflict_info = entry->rename_conflict_info;2848 switch (conflict_info->rename_type) {2849 case RENAME_NORMAL:2850 case RENAME_ONE_FILE_TO_ONE:2851 clean_merge = conflict_rename_normal(o,2852 path,2853 o_oid, o_mode,2854 a_oid, a_mode,2855 b_oid, b_mode,2856 conflict_info);2857 break;2858 case RENAME_DIR:2859 clean_merge = 1;2860 if (conflict_rename_dir(o,2861 conflict_info->pair1,2862 conflict_info->branch1,2863 conflict_info->branch2))2864 clean_merge = -1;2865 break;2866 case RENAME_DELETE:2867 clean_merge = 0;2868 if (conflict_rename_delete(o,2869 conflict_info->pair1,2870 conflict_info->branch1,2871 conflict_info->branch2))2872 clean_merge = -1;2873 break;2874 case RENAME_ONE_FILE_TO_TWO:2875 clean_merge = 0;2876 if (conflict_rename_rename_1to2(o, conflict_info))2877 clean_merge = -1;2878 break;2879 case RENAME_TWO_FILES_TO_ONE:2880 clean_merge = 0;2881 if (conflict_rename_rename_2to1(o, conflict_info))2882 clean_merge = -1;2883 break;2884 default:2885 entry->processed = 0;2886 break;2887 }2888 } else if (o_oid && (!a_oid || !b_oid)) {2889 /* Case A: Deleted in one */2890 if ((!a_oid && !b_oid) ||2891 (!b_oid && blob_unchanged(o, o_oid, o_mode, a_oid, a_mode, normalize, path)) ||2892 (!a_oid && blob_unchanged(o, o_oid, o_mode, b_oid, b_mode, normalize, path))) {2893 /* Deleted in both or deleted in one and2894 * unchanged in the other */2895 if (a_oid)2896 output(o, 2, _("Removing %s"), path);2897 /* do not touch working file if it did not exist */2898 remove_file(o, 1, path, !a_oid);2899 } else {2900 /* Modify/delete; deleted side may have put a directory in the way */2901 clean_merge = 0;2902 if (handle_modify_delete(o, path, o_oid, o_mode,2903 a_oid, a_mode, b_oid, b_mode))2904 clean_merge = -1;2905 }2906 } else if ((!o_oid && a_oid && !b_oid) ||2907 (!o_oid && !a_oid && b_oid)) {2908 /* Case B: Added in one. */2909 /* [nothing|directory] -> ([nothing|directory], file) */29102911 const char *add_branch;2912 const char *other_branch;2913 unsigned mode;2914 const struct object_id *oid;2915 const char *conf;29162917 if (a_oid) {2918 add_branch = o->branch1;2919 other_branch = o->branch2;2920 mode = a_mode;2921 oid = a_oid;2922 conf = _("file/directory");2923 } else {2924 add_branch = o->branch2;2925 other_branch = o->branch1;2926 mode = b_mode;2927 oid = b_oid;2928 conf = _("directory/file");2929 }2930 if (dir_in_way(path,2931 !o->call_depth && !S_ISGITLINK(a_mode),2932 0)) {2933 char *new_path = unique_path(o, path, add_branch);2934 clean_merge = 0;2935 output(o, 1, _("CONFLICT (%s): There is a directory with name %s in %s. "2936 "Adding %s as %s"),2937 conf, path, other_branch, path, new_path);2938 if (update_file(o, 0, oid, mode, new_path))2939 clean_merge = -1;2940 else if (o->call_depth)2941 remove_file_from_cache(path);2942 free(new_path);2943 } else {2944 output(o, 2, _("Adding %s"), path);2945 /* do not overwrite file if already present */2946 if (update_file_flags(o, oid, mode, path, 1, !a_oid))2947 clean_merge = -1;2948 }2949 } else if (a_oid && b_oid) {2950 /* Case C: Added in both (check for same permissions) and */2951 /* case D: Modified in both, but differently. */2952 clean_merge = merge_content(o, path, 0 /* file_in_way */,2953 o_oid, o_mode, a_oid, a_mode, b_oid, b_mode,2954 NULL);2955 } else if (!o_oid && !a_oid && !b_oid) {2956 /*2957 * this entry was deleted altogether. a_mode == 0 means2958 * we had that path and want to actively remove it.2959 */2960 remove_file(o, 1, path, !a_mode);2961 } else2962 die("BUG: fatal merge failure, shouldn't happen.");29632964 return clean_merge;2965}29662967int merge_trees(struct merge_options *o,2968 struct tree *head,2969 struct tree *merge,2970 struct tree *common,2971 struct tree **result)2972{2973 int code, clean;29742975 if (o->subtree_shift) {2976 merge = shift_tree_object(head, merge, o->subtree_shift);2977 common = shift_tree_object(head, common, o->subtree_shift);2978 }29792980 if (oid_eq(&common->object.oid, &merge->object.oid)) {2981 struct strbuf sb = STRBUF_INIT;29822983 if (!o->call_depth && index_has_changes(&sb)) {2984 err(o, _("Dirty index: cannot merge (dirty: %s)"),2985 sb.buf);2986 return 0;2987 }2988 output(o, 0, _("Already up to date!"));2989 *result = head;2990 return 1;2991 }29922993 code = git_merge_trees(o, common, head, merge);29942995 if (code != 0) {2996 if (show(o, 4) || o->call_depth)2997 err(o, _("merging of trees %s and %s failed"),2998 oid_to_hex(&head->object.oid),2999 oid_to_hex(&merge->object.oid));3000 return -1;3001 }30023003 if (unmerged_cache()) {3004 struct string_list *entries;3005 struct rename_info re_info;3006 int i;3007 /*3008 * Only need the hashmap while processing entries, so3009 * initialize it here and free it when we are done running3010 * through the entries. Keeping it in the merge_options as3011 * opposed to decaring a local hashmap is for convenience3012 * so that we don't have to pass it to around.3013 */3014 hashmap_init(&o->current_file_dir_set, path_hashmap_cmp, NULL, 512);3015 get_files_dirs(o, head);3016 get_files_dirs(o, merge);30173018 entries = get_unmerged();3019 clean = handle_renames(o, common, head, merge, entries,3020 &re_info);3021 record_df_conflict_files(o, entries);3022 if (clean < 0)3023 goto cleanup;3024 for (i = entries->nr-1; 0 <= i; i--) {3025 const char *path = entries->items[i].string;3026 struct stage_data *e = entries->items[i].util;3027 if (!e->processed) {3028 int ret = process_entry(o, path, e);3029 if (!ret)3030 clean = 0;3031 else if (ret < 0) {3032 clean = ret;3033 goto cleanup;3034 }3035 }3036 }3037 for (i = 0; i < entries->nr; i++) {3038 struct stage_data *e = entries->items[i].util;3039 if (!e->processed)3040 die("BUG: unprocessed path??? %s",3041 entries->items[i].string);3042 }30433044cleanup:3045 final_cleanup_renames(&re_info);30463047 string_list_clear(entries, 1);3048 free(entries);30493050 hashmap_free(&o->current_file_dir_set, 1);30513052 if (clean < 0)3053 return clean;3054 }3055 else3056 clean = 1;30573058 if (o->call_depth && !(*result = write_tree_from_memory(o)))3059 return -1;30603061 return clean;3062}30633064static struct commit_list *reverse_commit_list(struct commit_list *list)3065{3066 struct commit_list *next = NULL, *current, *backup;3067 for (current = list; current; current = backup) {3068 backup = current->next;3069 current->next = next;3070 next = current;3071 }3072 return next;3073}30743075/*3076 * Merge the commits h1 and h2, return the resulting virtual3077 * commit object and a flag indicating the cleanness of the merge.3078 */3079int merge_recursive(struct merge_options *o,3080 struct commit *h1,3081 struct commit *h2,3082 struct commit_list *ca,3083 struct commit **result)3084{3085 struct commit_list *iter;3086 struct commit *merged_common_ancestors;3087 struct tree *mrtree = mrtree;3088 int clean;30893090 if (show(o, 4)) {3091 output(o, 4, _("Merging:"));3092 output_commit_title(o, h1);3093 output_commit_title(o, h2);3094 }30953096 if (!ca) {3097 ca = get_merge_bases(h1, h2);3098 ca = reverse_commit_list(ca);3099 }31003101 if (show(o, 5)) {3102 unsigned cnt = commit_list_count(ca);31033104 output(o, 5, Q_("found %u common ancestor:",3105 "found %u common ancestors:", cnt), cnt);3106 for (iter = ca; iter; iter = iter->next)3107 output_commit_title(o, iter->item);3108 }31093110 merged_common_ancestors = pop_commit(&ca);3111 if (merged_common_ancestors == NULL) {3112 /* if there is no common ancestor, use an empty tree */3113 struct tree *tree;31143115 tree = lookup_tree(the_hash_algo->empty_tree);3116 merged_common_ancestors = make_virtual_commit(tree, "ancestor");3117 }31183119 for (iter = ca; iter; iter = iter->next) {3120 const char *saved_b1, *saved_b2;3121 o->call_depth++;3122 /*3123 * When the merge fails, the result contains files3124 * with conflict markers. The cleanness flag is3125 * ignored (unless indicating an error), it was never3126 * actually used, as result of merge_trees has always3127 * overwritten it: the committed "conflicts" were3128 * already resolved.3129 */3130 discard_cache();3131 saved_b1 = o->branch1;3132 saved_b2 = o->branch2;3133 o->branch1 = "Temporary merge branch 1";3134 o->branch2 = "Temporary merge branch 2";3135 if (merge_recursive(o, merged_common_ancestors, iter->item,3136 NULL, &merged_common_ancestors) < 0)3137 return -1;3138 o->branch1 = saved_b1;3139 o->branch2 = saved_b2;3140 o->call_depth--;31413142 if (!merged_common_ancestors)3143 return err(o, _("merge returned no commit"));3144 }31453146 discard_cache();3147 if (!o->call_depth)3148 read_cache();31493150 o->ancestor = "merged common ancestors";3151 clean = merge_trees(o, h1->tree, h2->tree, merged_common_ancestors->tree,3152 &mrtree);3153 if (clean < 0) {3154 flush_output(o);3155 return clean;3156 }31573158 if (o->call_depth) {3159 *result = make_virtual_commit(mrtree, "merged tree");3160 commit_list_insert(h1, &(*result)->parents);3161 commit_list_insert(h2, &(*result)->parents->next);3162 }3163 flush_output(o);3164 if (!o->call_depth && o->buffer_output < 2)3165 strbuf_release(&o->obuf);3166 if (show(o, 2))3167 diff_warn_rename_limit("merge.renamelimit",3168 o->needed_rename_limit, 0);3169 return clean;3170}31713172static struct commit *get_ref(const struct object_id *oid, const char *name)3173{3174 struct object *object;31753176 object = deref_tag(parse_object(oid), name, strlen(name));3177 if (!object)3178 return NULL;3179 if (object->type == OBJ_TREE)3180 return make_virtual_commit((struct tree*)object, name);3181 if (object->type != OBJ_COMMIT)3182 return NULL;3183 if (parse_commit((struct commit *)object))3184 return NULL;3185 return (struct commit *)object;3186}31873188int merge_recursive_generic(struct merge_options *o,3189 const struct object_id *head,3190 const struct object_id *merge,3191 int num_base_list,3192 const struct object_id **base_list,3193 struct commit **result)3194{3195 int clean;3196 struct lock_file lock = LOCK_INIT;3197 struct commit *head_commit = get_ref(head, o->branch1);3198 struct commit *next_commit = get_ref(merge, o->branch2);3199 struct commit_list *ca = NULL;32003201 if (base_list) {3202 int i;3203 for (i = 0; i < num_base_list; ++i) {3204 struct commit *base;3205 if (!(base = get_ref(base_list[i], oid_to_hex(base_list[i]))))3206 return err(o, _("Could not parse object '%s'"),3207 oid_to_hex(base_list[i]));3208 commit_list_insert(base, &ca);3209 }3210 }32113212 hold_locked_index(&lock, LOCK_DIE_ON_ERROR);3213 clean = merge_recursive(o, head_commit, next_commit, ca,3214 result);3215 if (clean < 0)3216 return clean;32173218 if (active_cache_changed &&3219 write_locked_index(&the_index, &lock, COMMIT_LOCK))3220 return err(o, _("Unable to write index."));32213222 return clean ? 0 : 1;3223}32243225static void merge_recursive_config(struct merge_options *o)3226{3227 git_config_get_int("merge.verbosity", &o->verbosity);3228 git_config_get_int("diff.renamelimit", &o->diff_rename_limit);3229 git_config_get_int("merge.renamelimit", &o->merge_rename_limit);3230 git_config(git_xmerge_config, NULL);3231}32323233void init_merge_options(struct merge_options *o)3234{3235 const char *merge_verbosity;3236 memset(o, 0, sizeof(struct merge_options));3237 o->verbosity = 2;3238 o->buffer_output = 1;3239 o->diff_rename_limit = -1;3240 o->merge_rename_limit = -1;3241 o->renormalize = 0;3242 o->detect_rename = 1;3243 merge_recursive_config(o);3244 merge_verbosity = getenv("GIT_MERGE_VERBOSITY");3245 if (merge_verbosity)3246 o->verbosity = strtol(merge_verbosity, NULL, 10);3247 if (o->verbosity >= 5)3248 o->buffer_output = 0;3249 strbuf_init(&o->obuf, 0);3250 string_list_init(&o->df_conflict_file_set, 1);3251}32523253int parse_merge_opt(struct merge_options *o, const char *s)3254{3255 const char *arg;32563257 if (!s || !*s)3258 return -1;3259 if (!strcmp(s, "ours"))3260 o->recursive_variant = MERGE_RECURSIVE_OURS;3261 else if (!strcmp(s, "theirs"))3262 o->recursive_variant = MERGE_RECURSIVE_THEIRS;3263 else if (!strcmp(s, "subtree"))3264 o->subtree_shift = "";3265 else if (skip_prefix(s, "subtree=", &arg))3266 o->subtree_shift = arg;3267 else if (!strcmp(s, "patience"))3268 o->xdl_opts = DIFF_WITH_ALG(o, PATIENCE_DIFF);3269 else if (!strcmp(s, "histogram"))3270 o->xdl_opts = DIFF_WITH_ALG(o, HISTOGRAM_DIFF);3271 else if (skip_prefix(s, "diff-algorithm=", &arg)) {3272 long value = parse_algorithm_value(arg);3273 if (value < 0)3274 return -1;3275 /* clear out previous settings */3276 DIFF_XDL_CLR(o, NEED_MINIMAL);3277 o->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;3278 o->xdl_opts |= value;3279 }3280 else if (!strcmp(s, "ignore-space-change"))3281 DIFF_XDL_SET(o, IGNORE_WHITESPACE_CHANGE);3282 else if (!strcmp(s, "ignore-all-space"))3283 DIFF_XDL_SET(o, IGNORE_WHITESPACE);3284 else if (!strcmp(s, "ignore-space-at-eol"))3285 DIFF_XDL_SET(o, IGNORE_WHITESPACE_AT_EOL);3286 else if (!strcmp(s, "ignore-cr-at-eol"))3287 DIFF_XDL_SET(o, IGNORE_CR_AT_EOL);3288 else if (!strcmp(s, "renormalize"))3289 o->renormalize = 1;3290 else if (!strcmp(s, "no-renormalize"))3291 o->renormalize = 0;3292 else if (!strcmp(s, "no-renames"))3293 o->detect_rename = 0;3294 else if (!strcmp(s, "find-renames")) {3295 o->detect_rename = 1;3296 o->rename_score = 0;3297 }3298 else if (skip_prefix(s, "find-renames=", &arg) ||3299 skip_prefix(s, "rename-threshold=", &arg)) {3300 if ((o->rename_score = parse_rename_score(&arg)) == -1 || *arg != 0)3301 return -1;3302 o->detect_rename = 1;3303 }3304 else3305 return -1;3306 return 0;3307}