2 * Recursive Merge algorithm stolen from git-merge-recursive.py by
4 * The thieves were Alex Riesen and Johannes Schindelin, in June/July 2006
9 #include "cache-tree.h"
13 #include "tree-walk.h"
17 #include "unpack-trees.h"
18 #include "string-list.h"
19 #include "xdiff-interface.h"
22 #include "merge-recursive.h"
24 #include "submodule.h"
26 static void flush_output(struct merge_options
*o
)
28 if (o
->buffer_output
< 2 && o
->obuf
.len
) {
29 fputs(o
->obuf
.buf
, stdout
);
30 strbuf_reset(&o
->obuf
);
34 static int err(struct merge_options
*o
, const char *err
, ...)
38 if (o
->buffer_output
< 2)
41 strbuf_complete(&o
->obuf
, '\n');
42 strbuf_addstr(&o
->obuf
, "error: ");
44 va_start(params
, err
);
45 strbuf_vaddf(&o
->obuf
, err
, params
);
47 if (o
->buffer_output
> 1)
48 strbuf_addch(&o
->obuf
, '\n');
50 error("%s", o
->obuf
.buf
);
51 strbuf_reset(&o
->obuf
);
57 static struct tree
*shift_tree_object(struct tree
*one
, struct tree
*two
,
58 const char *subtree_shift
)
60 struct object_id shifted
;
62 if (!*subtree_shift
) {
63 shift_tree(&one
->object
.oid
, &two
->object
.oid
, &shifted
, 0);
65 shift_tree_by(&one
->object
.oid
, &two
->object
.oid
, &shifted
,
68 if (!oidcmp(&two
->object
.oid
, &shifted
))
70 return lookup_tree(shifted
.hash
);
73 static struct commit
*make_virtual_commit(struct tree
*tree
, const char *comment
)
75 struct commit
*commit
= alloc_commit_node();
77 set_merge_remote_desc(commit
, comment
, (struct object
*)commit
);
79 commit
->object
.parsed
= 1;
84 * Since we use get_tree_entry(), which does not put the read object into
85 * the object pool, we cannot rely on a == b.
87 static int oid_eq(const struct object_id
*a
, const struct object_id
*b
)
91 return a
&& b
&& oidcmp(a
, b
) == 0;
97 RENAME_ONE_FILE_TO_ONE
,
98 RENAME_ONE_FILE_TO_TWO
,
99 RENAME_TWO_FILES_TO_ONE
102 struct rename_conflict_info
{
103 enum rename_type rename_type
;
104 struct diff_filepair
*pair1
;
105 struct diff_filepair
*pair2
;
108 struct stage_data
*dst_entry1
;
109 struct stage_data
*dst_entry2
;
110 struct diff_filespec ren1_other
;
111 struct diff_filespec ren2_other
;
115 * Since we want to write the index eventually, we cannot reuse the index
116 * for these (temporary) data.
121 struct object_id oid
;
123 struct rename_conflict_info
*rename_conflict_info
;
124 unsigned processed
:1;
127 static inline void setup_rename_conflict_info(enum rename_type rename_type
,
128 struct diff_filepair
*pair1
,
129 struct diff_filepair
*pair2
,
132 struct stage_data
*dst_entry1
,
133 struct stage_data
*dst_entry2
,
134 struct merge_options
*o
,
135 struct stage_data
*src_entry1
,
136 struct stage_data
*src_entry2
)
138 struct rename_conflict_info
*ci
= xcalloc(1, sizeof(struct rename_conflict_info
));
139 ci
->rename_type
= rename_type
;
141 ci
->branch1
= branch1
;
142 ci
->branch2
= branch2
;
144 ci
->dst_entry1
= dst_entry1
;
145 dst_entry1
->rename_conflict_info
= ci
;
146 dst_entry1
->processed
= 0;
148 assert(!pair2
== !dst_entry2
);
150 ci
->dst_entry2
= dst_entry2
;
152 dst_entry2
->rename_conflict_info
= ci
;
155 if (rename_type
== RENAME_TWO_FILES_TO_ONE
) {
157 * For each rename, there could have been
158 * modifications on the side of history where that
159 * file was not renamed.
161 int ostage1
= o
->branch1
== branch1
? 3 : 2;
162 int ostage2
= ostage1
^ 1;
164 ci
->ren1_other
.path
= pair1
->one
->path
;
165 oidcpy(&ci
->ren1_other
.oid
, &src_entry1
->stages
[ostage1
].oid
);
166 ci
->ren1_other
.mode
= src_entry1
->stages
[ostage1
].mode
;
168 ci
->ren2_other
.path
= pair2
->one
->path
;
169 oidcpy(&ci
->ren2_other
.oid
, &src_entry2
->stages
[ostage2
].oid
);
170 ci
->ren2_other
.mode
= src_entry2
->stages
[ostage2
].mode
;
174 static int show(struct merge_options
*o
, int v
)
176 return (!o
->call_depth
&& o
->verbosity
>= v
) || o
->verbosity
>= 5;
179 __attribute__((format (printf
, 3, 4)))
180 static void output(struct merge_options
*o
, int v
, const char *fmt
, ...)
187 strbuf_addchars(&o
->obuf
, ' ', o
->call_depth
* 2);
190 strbuf_vaddf(&o
->obuf
, fmt
, ap
);
193 strbuf_addch(&o
->obuf
, '\n');
194 if (!o
->buffer_output
)
198 static void output_commit_title(struct merge_options
*o
, struct commit
*commit
)
200 strbuf_addchars(&o
->obuf
, ' ', o
->call_depth
* 2);
202 strbuf_addf(&o
->obuf
, "virtual %s\n",
203 merge_remote_util(commit
)->name
);
205 strbuf_add_unique_abbrev(&o
->obuf
, commit
->object
.oid
.hash
,
207 strbuf_addch(&o
->obuf
, ' ');
208 if (parse_commit(commit
) != 0)
209 strbuf_addstr(&o
->obuf
, _("(bad commit)\n"));
212 const char *msg
= get_commit_buffer(commit
, NULL
);
213 int len
= find_commit_subject(msg
, &title
);
215 strbuf_addf(&o
->obuf
, "%.*s\n", len
, title
);
216 unuse_commit_buffer(commit
, msg
);
222 static int add_cacheinfo(struct merge_options
*o
,
223 unsigned int mode
, const struct object_id
*oid
,
224 const char *path
, int stage
, int refresh
, int options
)
226 struct cache_entry
*ce
;
229 ce
= make_cache_entry(mode
, oid
? oid
->hash
: null_sha1
, path
, stage
, 0);
231 return err(o
, _("addinfo_cache failed for path '%s'"), path
);
233 ret
= add_cache_entry(ce
, options
);
235 struct cache_entry
*nce
;
237 nce
= refresh_cache_entry(ce
, CE_MATCH_REFRESH
| CE_MATCH_IGNORE_MISSING
);
239 return err(o
, _("addinfo_cache failed for path '%s'"), path
);
241 ret
= add_cache_entry(nce
, options
);
246 static void init_tree_desc_from_tree(struct tree_desc
*desc
, struct tree
*tree
)
249 init_tree_desc(desc
, tree
->buffer
, tree
->size
);
252 static int git_merge_trees(int index_only
,
258 struct tree_desc t
[3];
259 struct unpack_trees_options opts
;
261 memset(&opts
, 0, sizeof(opts
));
268 opts
.fn
= threeway_merge
;
269 opts
.src_index
= &the_index
;
270 opts
.dst_index
= &the_index
;
271 setup_unpack_trees_porcelain(&opts
, "merge");
273 init_tree_desc_from_tree(t
+0, common
);
274 init_tree_desc_from_tree(t
+1, head
);
275 init_tree_desc_from_tree(t
+2, merge
);
277 rc
= unpack_trees(3, t
, &opts
);
278 cache_tree_free(&active_cache_tree
);
282 struct tree
*write_tree_from_memory(struct merge_options
*o
)
284 struct tree
*result
= NULL
;
286 if (unmerged_cache()) {
288 fprintf(stderr
, "BUG: There are unmerged index entries:\n");
289 for (i
= 0; i
< active_nr
; i
++) {
290 const struct cache_entry
*ce
= active_cache
[i
];
292 fprintf(stderr
, "BUG: %d %.*s\n", ce_stage(ce
),
293 (int)ce_namelen(ce
), ce
->name
);
295 die("BUG: unmerged index entries in merge-recursive.c");
298 if (!active_cache_tree
)
299 active_cache_tree
= cache_tree();
301 if (!cache_tree_fully_valid(active_cache_tree
) &&
302 cache_tree_update(&the_index
, 0) < 0) {
303 err(o
, _("error building trees"));
307 result
= lookup_tree(active_cache_tree
->sha1
);
312 static int save_files_dirs(const unsigned char *sha1
,
313 struct strbuf
*base
, const char *path
,
314 unsigned int mode
, int stage
, void *context
)
316 int baselen
= base
->len
;
317 struct merge_options
*o
= context
;
319 strbuf_addstr(base
, path
);
322 string_list_insert(&o
->current_directory_set
, base
->buf
);
324 string_list_insert(&o
->current_file_set
, base
->buf
);
326 strbuf_setlen(base
, baselen
);
327 return (S_ISDIR(mode
) ? READ_TREE_RECURSIVE
: 0);
330 static int get_files_dirs(struct merge_options
*o
, struct tree
*tree
)
333 struct pathspec match_all
;
334 memset(&match_all
, 0, sizeof(match_all
));
335 if (read_tree_recursive(tree
, "", 0, 0, &match_all
, save_files_dirs
, o
))
337 n
= o
->current_file_set
.nr
+ o
->current_directory_set
.nr
;
342 * Returns an index_entry instance which doesn't have to correspond to
343 * a real cache entry in Git's index.
345 static struct stage_data
*insert_stage_data(const char *path
,
346 struct tree
*o
, struct tree
*a
, struct tree
*b
,
347 struct string_list
*entries
)
349 struct string_list_item
*item
;
350 struct stage_data
*e
= xcalloc(1, sizeof(struct stage_data
));
351 get_tree_entry(o
->object
.oid
.hash
, path
,
352 e
->stages
[1].oid
.hash
, &e
->stages
[1].mode
);
353 get_tree_entry(a
->object
.oid
.hash
, path
,
354 e
->stages
[2].oid
.hash
, &e
->stages
[2].mode
);
355 get_tree_entry(b
->object
.oid
.hash
, path
,
356 e
->stages
[3].oid
.hash
, &e
->stages
[3].mode
);
357 item
= string_list_insert(entries
, path
);
363 * Create a dictionary mapping file names to stage_data objects. The
364 * dictionary contains one entry for every path with a non-zero stage entry.
366 static struct string_list
*get_unmerged(void)
368 struct string_list
*unmerged
= xcalloc(1, sizeof(struct string_list
));
371 unmerged
->strdup_strings
= 1;
373 for (i
= 0; i
< active_nr
; i
++) {
374 struct string_list_item
*item
;
375 struct stage_data
*e
;
376 const struct cache_entry
*ce
= active_cache
[i
];
380 item
= string_list_lookup(unmerged
, ce
->name
);
382 item
= string_list_insert(unmerged
, ce
->name
);
383 item
->util
= xcalloc(1, sizeof(struct stage_data
));
386 e
->stages
[ce_stage(ce
)].mode
= ce
->ce_mode
;
387 oidcpy(&e
->stages
[ce_stage(ce
)].oid
, &ce
->oid
);
393 static int string_list_df_name_compare(const void *a
, const void *b
)
395 const struct string_list_item
*one
= a
;
396 const struct string_list_item
*two
= b
;
397 int onelen
= strlen(one
->string
);
398 int twolen
= strlen(two
->string
);
400 * Here we only care that entries for D/F conflicts are
401 * adjacent, in particular with the file of the D/F conflict
402 * appearing before files below the corresponding directory.
403 * The order of the rest of the list is irrelevant for us.
405 * To achieve this, we sort with df_name_compare and provide
406 * the mode S_IFDIR so that D/F conflicts will sort correctly.
407 * We use the mode S_IFDIR for everything else for simplicity,
408 * since in other cases any changes in their order due to
409 * sorting cause no problems for us.
411 int cmp
= df_name_compare(one
->string
, onelen
, S_IFDIR
,
412 two
->string
, twolen
, S_IFDIR
);
414 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
415 * that 'foo' comes before 'foo/bar'.
419 return onelen
- twolen
;
422 static void record_df_conflict_files(struct merge_options
*o
,
423 struct string_list
*entries
)
425 /* If there is a D/F conflict and the file for such a conflict
426 * currently exist in the working tree, we want to allow it to be
427 * removed to make room for the corresponding directory if needed.
428 * The files underneath the directories of such D/F conflicts will
429 * be processed before the corresponding file involved in the D/F
430 * conflict. If the D/F directory ends up being removed by the
431 * merge, then we won't have to touch the D/F file. If the D/F
432 * directory needs to be written to the working copy, then the D/F
433 * file will simply be removed (in make_room_for_path()) to make
434 * room for the necessary paths. Note that if both the directory
435 * and the file need to be present, then the D/F file will be
436 * reinstated with a new unique name at the time it is processed.
438 struct string_list df_sorted_entries
= STRING_LIST_INIT_NODUP
;
439 const char *last_file
= NULL
;
444 * If we're merging merge-bases, we don't want to bother with
445 * any working directory changes.
450 /* Ensure D/F conflicts are adjacent in the entries list. */
451 for (i
= 0; i
< entries
->nr
; i
++) {
452 struct string_list_item
*next
= &entries
->items
[i
];
453 string_list_append(&df_sorted_entries
, next
->string
)->util
=
456 qsort(df_sorted_entries
.items
, entries
->nr
, sizeof(*entries
->items
),
457 string_list_df_name_compare
);
459 string_list_clear(&o
->df_conflict_file_set
, 1);
460 for (i
= 0; i
< df_sorted_entries
.nr
; i
++) {
461 const char *path
= df_sorted_entries
.items
[i
].string
;
462 int len
= strlen(path
);
463 struct stage_data
*e
= df_sorted_entries
.items
[i
].util
;
466 * Check if last_file & path correspond to a D/F conflict;
467 * i.e. whether path is last_file+'/'+<something>.
468 * If so, record that it's okay to remove last_file to make
469 * room for path and friends if needed.
473 memcmp(path
, last_file
, last_len
) == 0 &&
474 path
[last_len
] == '/') {
475 string_list_insert(&o
->df_conflict_file_set
, last_file
);
479 * Determine whether path could exist as a file in the
480 * working directory as a possible D/F conflict. This
481 * will only occur when it exists in stage 2 as a
484 if (S_ISREG(e
->stages
[2].mode
) || S_ISLNK(e
->stages
[2].mode
)) {
491 string_list_clear(&df_sorted_entries
, 0);
495 struct diff_filepair
*pair
;
496 struct stage_data
*src_entry
;
497 struct stage_data
*dst_entry
;
498 unsigned processed
:1;
502 * Get information of all renames which occurred between 'o_tree' and
503 * 'tree'. We need the three trees in the merge ('o_tree', 'a_tree' and
504 * 'b_tree') to be able to associate the correct cache entries with
505 * the rename information. 'tree' is always equal to either a_tree or b_tree.
507 static struct string_list
*get_renames(struct merge_options
*o
,
512 struct string_list
*entries
)
515 struct string_list
*renames
;
516 struct diff_options opts
;
518 renames
= xcalloc(1, sizeof(struct string_list
));
519 if (!o
->detect_rename
)
523 DIFF_OPT_SET(&opts
, RECURSIVE
);
524 DIFF_OPT_CLR(&opts
, RENAME_EMPTY
);
525 opts
.detect_rename
= DIFF_DETECT_RENAME
;
526 opts
.rename_limit
= o
->merge_rename_limit
>= 0 ? o
->merge_rename_limit
:
527 o
->diff_rename_limit
>= 0 ? o
->diff_rename_limit
:
529 opts
.rename_score
= o
->rename_score
;
530 opts
.show_rename_progress
= o
->show_rename_progress
;
531 opts
.output_format
= DIFF_FORMAT_NO_OUTPUT
;
532 diff_setup_done(&opts
);
533 diff_tree_sha1(o_tree
->object
.oid
.hash
, tree
->object
.oid
.hash
, "", &opts
);
535 if (opts
.needed_rename_limit
> o
->needed_rename_limit
)
536 o
->needed_rename_limit
= opts
.needed_rename_limit
;
537 for (i
= 0; i
< diff_queued_diff
.nr
; ++i
) {
538 struct string_list_item
*item
;
540 struct diff_filepair
*pair
= diff_queued_diff
.queue
[i
];
541 if (pair
->status
!= 'R') {
542 diff_free_filepair(pair
);
545 re
= xmalloc(sizeof(*re
));
548 item
= string_list_lookup(entries
, re
->pair
->one
->path
);
550 re
->src_entry
= insert_stage_data(re
->pair
->one
->path
,
551 o_tree
, a_tree
, b_tree
, entries
);
553 re
->src_entry
= item
->util
;
555 item
= string_list_lookup(entries
, re
->pair
->two
->path
);
557 re
->dst_entry
= insert_stage_data(re
->pair
->two
->path
,
558 o_tree
, a_tree
, b_tree
, entries
);
560 re
->dst_entry
= item
->util
;
561 item
= string_list_insert(renames
, pair
->one
->path
);
564 opts
.output_format
= DIFF_FORMAT_NO_OUTPUT
;
565 diff_queued_diff
.nr
= 0;
570 static int update_stages(struct merge_options
*opt
, const char *path
,
571 const struct diff_filespec
*o
,
572 const struct diff_filespec
*a
,
573 const struct diff_filespec
*b
)
577 * NOTE: It is usually a bad idea to call update_stages on a path
578 * before calling update_file on that same path, since it can
579 * sometimes lead to spurious "refusing to lose untracked file..."
580 * messages from update_file (via make_room_for path via
581 * would_lose_untracked). Instead, reverse the order of the calls
582 * (executing update_file first and then update_stages).
585 int options
= ADD_CACHE_OK_TO_ADD
| ADD_CACHE_SKIP_DFCHECK
;
587 if (remove_file_from_cache(path
))
590 if (add_cacheinfo(opt
, o
->mode
, &o
->oid
, path
, 1, 0, options
))
593 if (add_cacheinfo(opt
, a
->mode
, &a
->oid
, path
, 2, 0, options
))
596 if (add_cacheinfo(opt
, b
->mode
, &b
->oid
, path
, 3, 0, options
))
601 static void update_entry(struct stage_data
*entry
,
602 struct diff_filespec
*o
,
603 struct diff_filespec
*a
,
604 struct diff_filespec
*b
)
606 entry
->processed
= 0;
607 entry
->stages
[1].mode
= o
->mode
;
608 entry
->stages
[2].mode
= a
->mode
;
609 entry
->stages
[3].mode
= b
->mode
;
610 oidcpy(&entry
->stages
[1].oid
, &o
->oid
);
611 oidcpy(&entry
->stages
[2].oid
, &a
->oid
);
612 oidcpy(&entry
->stages
[3].oid
, &b
->oid
);
615 static int remove_file(struct merge_options
*o
, int clean
,
616 const char *path
, int no_wd
)
618 int update_cache
= o
->call_depth
|| clean
;
619 int update_working_directory
= !o
->call_depth
&& !no_wd
;
622 if (remove_file_from_cache(path
))
625 if (update_working_directory
) {
627 struct cache_entry
*ce
;
628 ce
= cache_file_exists(path
, strlen(path
), ignore_case
);
629 if (ce
&& ce_stage(ce
) == 0)
632 if (remove_path(path
))
638 /* add a string to a strbuf, but converting "/" to "_" */
639 static void add_flattened_path(struct strbuf
*out
, const char *s
)
642 strbuf_addstr(out
, s
);
643 for (; i
< out
->len
; i
++)
644 if (out
->buf
[i
] == '/')
648 static char *unique_path(struct merge_options
*o
, const char *path
, const char *branch
)
650 struct strbuf newpath
= STRBUF_INIT
;
654 strbuf_addf(&newpath
, "%s~", path
);
655 add_flattened_path(&newpath
, branch
);
657 base_len
= newpath
.len
;
658 while (string_list_has_string(&o
->current_file_set
, newpath
.buf
) ||
659 string_list_has_string(&o
->current_directory_set
, newpath
.buf
) ||
660 (!o
->call_depth
&& file_exists(newpath
.buf
))) {
661 strbuf_setlen(&newpath
, base_len
);
662 strbuf_addf(&newpath
, "_%d", suffix
++);
665 string_list_insert(&o
->current_file_set
, newpath
.buf
);
666 return strbuf_detach(&newpath
, NULL
);
670 * Check whether a directory in the index is in the way of an incoming
671 * file. Return 1 if so. If check_working_copy is non-zero, also
672 * check the working directory. If empty_ok is non-zero, also return
673 * 0 in the case where the working-tree dir exists but is empty.
675 static int dir_in_way(const char *path
, int check_working_copy
, int empty_ok
)
678 struct strbuf dirpath
= STRBUF_INIT
;
681 strbuf_addstr(&dirpath
, path
);
682 strbuf_addch(&dirpath
, '/');
684 pos
= cache_name_pos(dirpath
.buf
, dirpath
.len
);
688 if (pos
< active_nr
&&
689 !strncmp(dirpath
.buf
, active_cache
[pos
]->name
, dirpath
.len
)) {
690 strbuf_release(&dirpath
);
694 strbuf_release(&dirpath
);
695 return check_working_copy
&& !lstat(path
, &st
) && S_ISDIR(st
.st_mode
) &&
696 !(empty_ok
&& is_empty_dir(path
));
699 static int was_tracked(const char *path
)
701 int pos
= cache_name_pos(path
, strlen(path
));
704 /* we have been tracking this path */
708 * Look for an unmerged entry for the path,
709 * specifically stage #2, which would indicate
710 * that "our" side before the merge started
711 * had the path tracked (and resulted in a conflict).
714 pos
< active_nr
&& !strcmp(path
, active_cache
[pos
]->name
);
716 if (ce_stage(active_cache
[pos
]) == 2)
721 static int would_lose_untracked(const char *path
)
723 return !was_tracked(path
) && file_exists(path
);
726 static int make_room_for_path(struct merge_options
*o
, const char *path
)
729 const char *msg
= _("failed to create path '%s'%s");
731 /* Unlink any D/F conflict files that are in the way */
732 for (i
= 0; i
< o
->df_conflict_file_set
.nr
; i
++) {
733 const char *df_path
= o
->df_conflict_file_set
.items
[i
].string
;
734 size_t pathlen
= strlen(path
);
735 size_t df_pathlen
= strlen(df_path
);
736 if (df_pathlen
< pathlen
&&
737 path
[df_pathlen
] == '/' &&
738 strncmp(path
, df_path
, df_pathlen
) == 0) {
740 _("Removing %s to make room for subdirectory\n"),
743 unsorted_string_list_delete_item(&o
->df_conflict_file_set
,
749 /* Make sure leading directories are created */
750 status
= safe_create_leading_directories_const(path
);
752 if (status
== SCLD_EXISTS
)
753 /* something else exists */
754 return err(o
, msg
, path
, _(": perhaps a D/F conflict?"));
755 return err(o
, msg
, path
, "");
759 * Do not unlink a file in the work tree if we are not
762 if (would_lose_untracked(path
))
763 return err(o
, _("refusing to lose untracked file at '%s'"),
766 /* Successful unlink is good.. */
769 /* .. and so is no existing file */
772 /* .. but not some other error (who really cares what?) */
773 return err(o
, msg
, path
, _(": perhaps a D/F conflict?"));
776 static int update_file_flags(struct merge_options
*o
,
777 const struct object_id
*oid
,
789 enum object_type type
;
793 if (S_ISGITLINK(mode
)) {
795 * We may later decide to recursively descend into
796 * the submodule directory and update its index
797 * and/or work tree, but we do not do that now.
803 buf
= read_sha1_file(oid
->hash
, &type
, &size
);
805 return err(o
, _("cannot read object %s '%s'"), oid_to_hex(oid
), path
);
806 if (type
!= OBJ_BLOB
) {
807 ret
= err(o
, _("blob expected for %s '%s'"), oid_to_hex(oid
), path
);
811 struct strbuf strbuf
= STRBUF_INIT
;
812 if (convert_to_working_tree(path
, buf
, size
, &strbuf
)) {
815 buf
= strbuf_detach(&strbuf
, NULL
);
819 if (make_room_for_path(o
, path
) < 0) {
823 if (S_ISREG(mode
) || (!has_symlinks
&& S_ISLNK(mode
))) {
829 fd
= open(path
, O_WRONLY
| O_TRUNC
| O_CREAT
, mode
);
831 ret
= err(o
, _("failed to open '%s': %s"),
832 path
, strerror(errno
));
835 write_in_full(fd
, buf
, size
);
837 } else if (S_ISLNK(mode
)) {
838 char *lnk
= xmemdupz(buf
, size
);
839 safe_create_leading_directories_const(path
);
841 if (symlink(lnk
, path
))
842 ret
= err(o
, _("failed to symlink '%s': %s"),
843 path
, strerror(errno
));
847 _("do not know what to do with %06o %s '%s'"),
848 mode
, oid_to_hex(oid
), path
);
853 if (!ret
&& update_cache
)
854 add_cacheinfo(o
, mode
, oid
, path
, 0, update_wd
, ADD_CACHE_OK_TO_ADD
);
858 static int update_file(struct merge_options
*o
,
860 const struct object_id
*oid
,
864 return update_file_flags(o
, oid
, mode
, path
, o
->call_depth
|| clean
, !o
->call_depth
);
867 /* Low level file merging, update and removal */
869 struct merge_file_info
{
870 struct object_id oid
;
876 static int merge_3way(struct merge_options
*o
,
877 mmbuffer_t
*result_buf
,
878 const struct diff_filespec
*one
,
879 const struct diff_filespec
*a
,
880 const struct diff_filespec
*b
,
884 mmfile_t orig
, src1
, src2
;
885 struct ll_merge_options ll_opts
= {0};
886 char *base_name
, *name1
, *name2
;
889 ll_opts
.renormalize
= o
->renormalize
;
890 ll_opts
.xdl_opts
= o
->xdl_opts
;
893 ll_opts
.virtual_ancestor
= 1;
896 switch (o
->recursive_variant
) {
897 case MERGE_RECURSIVE_OURS
:
898 ll_opts
.variant
= XDL_MERGE_FAVOR_OURS
;
900 case MERGE_RECURSIVE_THEIRS
:
901 ll_opts
.variant
= XDL_MERGE_FAVOR_THEIRS
;
909 if (strcmp(a
->path
, b
->path
) ||
910 (o
->ancestor
!= NULL
&& strcmp(a
->path
, one
->path
) != 0)) {
911 base_name
= o
->ancestor
== NULL
? NULL
:
912 mkpathdup("%s:%s", o
->ancestor
, one
->path
);
913 name1
= mkpathdup("%s:%s", branch1
, a
->path
);
914 name2
= mkpathdup("%s:%s", branch2
, b
->path
);
916 base_name
= o
->ancestor
== NULL
? NULL
:
917 mkpathdup("%s", o
->ancestor
);
918 name1
= mkpathdup("%s", branch1
);
919 name2
= mkpathdup("%s", branch2
);
922 read_mmblob(&orig
, &one
->oid
);
923 read_mmblob(&src1
, &a
->oid
);
924 read_mmblob(&src2
, &b
->oid
);
926 merge_status
= ll_merge(result_buf
, a
->path
, &orig
, base_name
,
927 &src1
, name1
, &src2
, name2
, &ll_opts
);
938 static int merge_file_1(struct merge_options
*o
,
939 const struct diff_filespec
*one
,
940 const struct diff_filespec
*a
,
941 const struct diff_filespec
*b
,
944 struct merge_file_info
*result
)
949 if ((S_IFMT
& a
->mode
) != (S_IFMT
& b
->mode
)) {
951 if (S_ISREG(a
->mode
)) {
952 result
->mode
= a
->mode
;
953 oidcpy(&result
->oid
, &a
->oid
);
955 result
->mode
= b
->mode
;
956 oidcpy(&result
->oid
, &b
->oid
);
959 if (!oid_eq(&a
->oid
, &one
->oid
) && !oid_eq(&b
->oid
, &one
->oid
))
965 if (a
->mode
== b
->mode
|| a
->mode
== one
->mode
)
966 result
->mode
= b
->mode
;
968 result
->mode
= a
->mode
;
969 if (b
->mode
!= one
->mode
) {
975 if (oid_eq(&a
->oid
, &b
->oid
) || oid_eq(&a
->oid
, &one
->oid
))
976 oidcpy(&result
->oid
, &b
->oid
);
977 else if (oid_eq(&b
->oid
, &one
->oid
))
978 oidcpy(&result
->oid
, &a
->oid
);
979 else if (S_ISREG(a
->mode
)) {
980 mmbuffer_t result_buf
;
981 int ret
= 0, merge_status
;
983 merge_status
= merge_3way(o
, &result_buf
, one
, a
, b
,
986 if ((merge_status
< 0) || !result_buf
.ptr
)
987 ret
= err(o
, _("Failed to execute internal merge"));
989 if (!ret
&& write_sha1_file(result_buf
.ptr
, result_buf
.size
,
990 blob_type
, result
->oid
.hash
))
991 ret
= err(o
, _("Unable to add %s to database"),
994 free(result_buf
.ptr
);
997 result
->clean
= (merge_status
== 0);
998 } else if (S_ISGITLINK(a
->mode
)) {
999 result
->clean
= merge_submodule(result
->oid
.hash
,
1005 } else if (S_ISLNK(a
->mode
)) {
1006 oidcpy(&result
->oid
, &a
->oid
);
1008 if (!oid_eq(&a
->oid
, &b
->oid
))
1011 die("BUG: unsupported object type in the tree");
1017 static int merge_file_special_markers(struct merge_options
*o
,
1018 const struct diff_filespec
*one
,
1019 const struct diff_filespec
*a
,
1020 const struct diff_filespec
*b
,
1021 const char *branch1
,
1022 const char *filename1
,
1023 const char *branch2
,
1024 const char *filename2
,
1025 struct merge_file_info
*mfi
)
1032 side1
= xstrfmt("%s:%s", branch1
, filename1
);
1034 side2
= xstrfmt("%s:%s", branch2
, filename2
);
1036 ret
= merge_file_1(o
, one
, a
, b
,
1037 side1
? side1
: branch1
,
1038 side2
? side2
: branch2
, mfi
);
1044 static int merge_file_one(struct merge_options
*o
,
1046 const struct object_id
*o_oid
, int o_mode
,
1047 const struct object_id
*a_oid
, int a_mode
,
1048 const struct object_id
*b_oid
, int b_mode
,
1049 const char *branch1
,
1050 const char *branch2
,
1051 struct merge_file_info
*mfi
)
1053 struct diff_filespec one
, a
, b
;
1055 one
.path
= a
.path
= b
.path
= (char *)path
;
1056 oidcpy(&one
.oid
, o_oid
);
1058 oidcpy(&a
.oid
, a_oid
);
1060 oidcpy(&b
.oid
, b_oid
);
1062 return merge_file_1(o
, &one
, &a
, &b
, branch1
, branch2
, mfi
);
1065 static int handle_change_delete(struct merge_options
*o
,
1067 const struct object_id
*o_oid
, int o_mode
,
1068 const struct object_id
*a_oid
, int a_mode
,
1069 const struct object_id
*b_oid
, int b_mode
,
1070 const char *change
, const char *change_past
)
1072 char *renamed
= NULL
;
1074 if (dir_in_way(path
, !o
->call_depth
, 0)) {
1075 renamed
= unique_path(o
, path
, a_oid
? o
->branch1
: o
->branch2
);
1078 if (o
->call_depth
) {
1080 * We cannot arbitrarily accept either a_sha or b_sha as
1081 * correct; since there is no true "middle point" between
1082 * them, simply reuse the base version for virtual merge base.
1084 ret
= remove_file_from_cache(path
);
1086 ret
= update_file(o
, 0, o_oid
, o_mode
,
1087 renamed
? renamed
: path
);
1088 } else if (!a_oid
) {
1090 output(o
, 1, _("CONFLICT (%s/delete): %s deleted in %s "
1091 "and %s in %s. Version %s of %s left in tree."),
1092 change
, path
, o
->branch1
, change_past
,
1093 o
->branch2
, o
->branch2
, path
);
1094 ret
= update_file(o
, 0, b_oid
, b_mode
, path
);
1096 output(o
, 1, _("CONFLICT (%s/delete): %s deleted in %s "
1097 "and %s in %s. Version %s of %s left in tree at %s."),
1098 change
, path
, o
->branch1
, change_past
,
1099 o
->branch2
, o
->branch2
, path
, renamed
);
1100 ret
= update_file(o
, 0, b_oid
, b_mode
, renamed
);
1104 output(o
, 1, _("CONFLICT (%s/delete): %s deleted in %s "
1105 "and %s in %s. Version %s of %s left in tree."),
1106 change
, path
, o
->branch2
, change_past
,
1107 o
->branch1
, o
->branch1
, path
);
1109 output(o
, 1, _("CONFLICT (%s/delete): %s deleted in %s "
1110 "and %s in %s. Version %s of %s left in tree at %s."),
1111 change
, path
, o
->branch2
, change_past
,
1112 o
->branch1
, o
->branch1
, path
, renamed
);
1113 ret
= update_file(o
, 0, a_oid
, a_mode
, renamed
);
1116 * No need to call update_file() on path when !renamed, since
1117 * that would needlessly touch path. We could call
1118 * update_file_flags() with update_cache=0 and update_wd=0,
1119 * but that's a no-op.
1127 static int conflict_rename_delete(struct merge_options
*o
,
1128 struct diff_filepair
*pair
,
1129 const char *rename_branch
,
1130 const char *other_branch
)
1132 const struct diff_filespec
*orig
= pair
->one
;
1133 const struct diff_filespec
*dest
= pair
->two
;
1134 const struct object_id
*a_oid
= NULL
;
1135 const struct object_id
*b_oid
= NULL
;
1139 if (rename_branch
== o
->branch1
) {
1141 a_mode
= dest
->mode
;
1144 b_mode
= dest
->mode
;
1147 if (handle_change_delete(o
,
1148 o
->call_depth
? orig
->path
: dest
->path
,
1149 &orig
->oid
, orig
->mode
,
1152 _("rename"), _("renamed")))
1156 return remove_file_from_cache(dest
->path
);
1158 return update_stages(o
, dest
->path
, NULL
,
1159 rename_branch
== o
->branch1
? dest
: NULL
,
1160 rename_branch
== o
->branch1
? NULL
: dest
);
1163 static struct diff_filespec
*filespec_from_entry(struct diff_filespec
*target
,
1164 struct stage_data
*entry
,
1167 struct object_id
*oid
= &entry
->stages
[stage
].oid
;
1168 unsigned mode
= entry
->stages
[stage
].mode
;
1169 if (mode
== 0 || is_null_oid(oid
))
1171 oidcpy(&target
->oid
, oid
);
1172 target
->mode
= mode
;
1176 static int handle_file(struct merge_options
*o
,
1177 struct diff_filespec
*rename
,
1179 struct rename_conflict_info
*ci
)
1181 char *dst_name
= rename
->path
;
1182 struct stage_data
*dst_entry
;
1183 const char *cur_branch
, *other_branch
;
1184 struct diff_filespec other
;
1185 struct diff_filespec
*add
;
1189 dst_entry
= ci
->dst_entry1
;
1190 cur_branch
= ci
->branch1
;
1191 other_branch
= ci
->branch2
;
1193 dst_entry
= ci
->dst_entry2
;
1194 cur_branch
= ci
->branch2
;
1195 other_branch
= ci
->branch1
;
1198 add
= filespec_from_entry(&other
, dst_entry
, stage
^ 1);
1200 char *add_name
= unique_path(o
, rename
->path
, other_branch
);
1201 if (update_file(o
, 0, &add
->oid
, add
->mode
, add_name
))
1204 remove_file(o
, 0, rename
->path
, 0);
1205 dst_name
= unique_path(o
, rename
->path
, cur_branch
);
1207 if (dir_in_way(rename
->path
, !o
->call_depth
, 0)) {
1208 dst_name
= unique_path(o
, rename
->path
, cur_branch
);
1209 output(o
, 1, _("%s is a directory in %s adding as %s instead"),
1210 rename
->path
, other_branch
, dst_name
);
1213 if ((ret
= update_file(o
, 0, &rename
->oid
, rename
->mode
, dst_name
)))
1214 ; /* fall through, do allow dst_name to be released */
1215 else if (stage
== 2)
1216 ret
= update_stages(o
, rename
->path
, NULL
, rename
, add
);
1218 ret
= update_stages(o
, rename
->path
, NULL
, add
, rename
);
1220 if (dst_name
!= rename
->path
)
1226 static int conflict_rename_rename_1to2(struct merge_options
*o
,
1227 struct rename_conflict_info
*ci
)
1229 /* One file was renamed in both branches, but to different names. */
1230 struct diff_filespec
*one
= ci
->pair1
->one
;
1231 struct diff_filespec
*a
= ci
->pair1
->two
;
1232 struct diff_filespec
*b
= ci
->pair2
->two
;
1234 output(o
, 1, _("CONFLICT (rename/rename): "
1235 "Rename \"%s\"->\"%s\" in branch \"%s\" "
1236 "rename \"%s\"->\"%s\" in \"%s\"%s"),
1237 one
->path
, a
->path
, ci
->branch1
,
1238 one
->path
, b
->path
, ci
->branch2
,
1239 o
->call_depth
? _(" (left unresolved)") : "");
1240 if (o
->call_depth
) {
1241 struct merge_file_info mfi
;
1242 struct diff_filespec other
;
1243 struct diff_filespec
*add
;
1244 if (merge_file_one(o
, one
->path
,
1245 &one
->oid
, one
->mode
,
1248 ci
->branch1
, ci
->branch2
, &mfi
))
1252 * FIXME: For rename/add-source conflicts (if we could detect
1253 * such), this is wrong. We should instead find a unique
1254 * pathname and then either rename the add-source file to that
1255 * unique path, or use that unique path instead of src here.
1257 if (update_file(o
, 0, &mfi
.oid
, mfi
.mode
, one
->path
))
1261 * Above, we put the merged content at the merge-base's
1262 * path. Now we usually need to delete both a->path and
1263 * b->path. However, the rename on each side of the merge
1264 * could also be involved in a rename/add conflict. In
1265 * such cases, we should keep the added file around,
1266 * resolving the conflict at that path in its favor.
1268 add
= filespec_from_entry(&other
, ci
->dst_entry1
, 2 ^ 1);
1270 if (update_file(o
, 0, &add
->oid
, add
->mode
, a
->path
))
1274 remove_file_from_cache(a
->path
);
1275 add
= filespec_from_entry(&other
, ci
->dst_entry2
, 3 ^ 1);
1277 if (update_file(o
, 0, &add
->oid
, add
->mode
, b
->path
))
1281 remove_file_from_cache(b
->path
);
1282 } else if (handle_file(o
, a
, 2, ci
) || handle_file(o
, b
, 3, ci
))
1288 static int conflict_rename_rename_2to1(struct merge_options
*o
,
1289 struct rename_conflict_info
*ci
)
1291 /* Two files, a & b, were renamed to the same thing, c. */
1292 struct diff_filespec
*a
= ci
->pair1
->one
;
1293 struct diff_filespec
*b
= ci
->pair2
->one
;
1294 struct diff_filespec
*c1
= ci
->pair1
->two
;
1295 struct diff_filespec
*c2
= ci
->pair2
->two
;
1296 char *path
= c1
->path
; /* == c2->path */
1297 struct merge_file_info mfi_c1
;
1298 struct merge_file_info mfi_c2
;
1301 output(o
, 1, _("CONFLICT (rename/rename): "
1302 "Rename %s->%s in %s. "
1303 "Rename %s->%s in %s"),
1304 a
->path
, c1
->path
, ci
->branch1
,
1305 b
->path
, c2
->path
, ci
->branch2
);
1307 remove_file(o
, 1, a
->path
, o
->call_depth
|| would_lose_untracked(a
->path
));
1308 remove_file(o
, 1, b
->path
, o
->call_depth
|| would_lose_untracked(b
->path
));
1310 if (merge_file_special_markers(o
, a
, c1
, &ci
->ren1_other
,
1311 o
->branch1
, c1
->path
,
1312 o
->branch2
, ci
->ren1_other
.path
, &mfi_c1
) ||
1313 merge_file_special_markers(o
, b
, &ci
->ren2_other
, c2
,
1314 o
->branch1
, ci
->ren2_other
.path
,
1315 o
->branch2
, c2
->path
, &mfi_c2
))
1318 if (o
->call_depth
) {
1320 * If mfi_c1.clean && mfi_c2.clean, then it might make
1321 * sense to do a two-way merge of those results. But, I
1322 * think in all cases, it makes sense to have the virtual
1323 * merge base just undo the renames; they can be detected
1324 * again later for the non-recursive merge.
1326 remove_file(o
, 0, path
, 0);
1327 ret
= update_file(o
, 0, &mfi_c1
.oid
, mfi_c1
.mode
, a
->path
);
1329 ret
= update_file(o
, 0, &mfi_c2
.oid
, mfi_c2
.mode
,
1332 char *new_path1
= unique_path(o
, path
, ci
->branch1
);
1333 char *new_path2
= unique_path(o
, path
, ci
->branch2
);
1334 output(o
, 1, _("Renaming %s to %s and %s to %s instead"),
1335 a
->path
, new_path1
, b
->path
, new_path2
);
1336 remove_file(o
, 0, path
, 0);
1337 ret
= update_file(o
, 0, &mfi_c1
.oid
, mfi_c1
.mode
, new_path1
);
1339 ret
= update_file(o
, 0, &mfi_c2
.oid
, mfi_c2
.mode
,
1348 static int process_renames(struct merge_options
*o
,
1349 struct string_list
*a_renames
,
1350 struct string_list
*b_renames
)
1352 int clean_merge
= 1, i
, j
;
1353 struct string_list a_by_dst
= STRING_LIST_INIT_NODUP
;
1354 struct string_list b_by_dst
= STRING_LIST_INIT_NODUP
;
1355 const struct rename
*sre
;
1357 for (i
= 0; i
< a_renames
->nr
; i
++) {
1358 sre
= a_renames
->items
[i
].util
;
1359 string_list_insert(&a_by_dst
, sre
->pair
->two
->path
)->util
1362 for (i
= 0; i
< b_renames
->nr
; i
++) {
1363 sre
= b_renames
->items
[i
].util
;
1364 string_list_insert(&b_by_dst
, sre
->pair
->two
->path
)->util
1368 for (i
= 0, j
= 0; i
< a_renames
->nr
|| j
< b_renames
->nr
;) {
1369 struct string_list
*renames1
, *renames2Dst
;
1370 struct rename
*ren1
= NULL
, *ren2
= NULL
;
1371 const char *branch1
, *branch2
;
1372 const char *ren1_src
, *ren1_dst
;
1373 struct string_list_item
*lookup
;
1375 if (i
>= a_renames
->nr
) {
1376 ren2
= b_renames
->items
[j
++].util
;
1377 } else if (j
>= b_renames
->nr
) {
1378 ren1
= a_renames
->items
[i
++].util
;
1380 int compare
= strcmp(a_renames
->items
[i
].string
,
1381 b_renames
->items
[j
].string
);
1383 ren1
= a_renames
->items
[i
++].util
;
1385 ren2
= b_renames
->items
[j
++].util
;
1388 /* TODO: refactor, so that 1/2 are not needed */
1390 renames1
= a_renames
;
1391 renames2Dst
= &b_by_dst
;
1392 branch1
= o
->branch1
;
1393 branch2
= o
->branch2
;
1396 renames1
= b_renames
;
1397 renames2Dst
= &a_by_dst
;
1398 branch1
= o
->branch2
;
1399 branch2
= o
->branch1
;
1405 if (ren1
->processed
)
1407 ren1
->processed
= 1;
1408 ren1
->dst_entry
->processed
= 1;
1409 /* BUG: We should only mark src_entry as processed if we
1410 * are not dealing with a rename + add-source case.
1412 ren1
->src_entry
->processed
= 1;
1414 ren1_src
= ren1
->pair
->one
->path
;
1415 ren1_dst
= ren1
->pair
->two
->path
;
1418 /* One file renamed on both sides */
1419 const char *ren2_src
= ren2
->pair
->one
->path
;
1420 const char *ren2_dst
= ren2
->pair
->two
->path
;
1421 enum rename_type rename_type
;
1422 if (strcmp(ren1_src
, ren2_src
) != 0)
1423 die("BUG: ren1_src != ren2_src");
1424 ren2
->dst_entry
->processed
= 1;
1425 ren2
->processed
= 1;
1426 if (strcmp(ren1_dst
, ren2_dst
) != 0) {
1427 rename_type
= RENAME_ONE_FILE_TO_TWO
;
1430 rename_type
= RENAME_ONE_FILE_TO_ONE
;
1431 /* BUG: We should only remove ren1_src in
1432 * the base stage (think of rename +
1433 * add-source cases).
1435 remove_file(o
, 1, ren1_src
, 1);
1436 update_entry(ren1
->dst_entry
,
1441 setup_rename_conflict_info(rename_type
,
1451 } else if ((lookup
= string_list_lookup(renames2Dst
, ren1_dst
))) {
1452 /* Two different files renamed to the same thing */
1454 ren2
= lookup
->util
;
1455 ren2_dst
= ren2
->pair
->two
->path
;
1456 if (strcmp(ren1_dst
, ren2_dst
) != 0)
1457 die("BUG: ren1_dst != ren2_dst");
1460 ren2
->processed
= 1;
1462 * BUG: We should only mark src_entry as processed
1463 * if we are not dealing with a rename + add-source
1466 ren2
->src_entry
->processed
= 1;
1468 setup_rename_conflict_info(RENAME_TWO_FILES_TO_ONE
,
1480 /* Renamed in 1, maybe changed in 2 */
1481 /* we only use sha1 and mode of these */
1482 struct diff_filespec src_other
, dst_other
;
1486 * unpack_trees loads entries from common-commit
1487 * into stage 1, from head-commit into stage 2, and
1488 * from merge-commit into stage 3. We keep track
1489 * of which side corresponds to the rename.
1491 int renamed_stage
= a_renames
== renames1
? 2 : 3;
1492 int other_stage
= a_renames
== renames1
? 3 : 2;
1494 /* BUG: We should only remove ren1_src in the base
1495 * stage and in other_stage (think of rename +
1498 remove_file(o
, 1, ren1_src
,
1499 renamed_stage
== 2 || !was_tracked(ren1_src
));
1501 oidcpy(&src_other
.oid
,
1502 &ren1
->src_entry
->stages
[other_stage
].oid
);
1503 src_other
.mode
= ren1
->src_entry
->stages
[other_stage
].mode
;
1504 oidcpy(&dst_other
.oid
,
1505 &ren1
->dst_entry
->stages
[other_stage
].oid
);
1506 dst_other
.mode
= ren1
->dst_entry
->stages
[other_stage
].mode
;
1509 if (oid_eq(&src_other
.oid
, &null_oid
)) {
1510 setup_rename_conflict_info(RENAME_DELETE
,
1520 } else if ((dst_other
.mode
== ren1
->pair
->two
->mode
) &&
1521 oid_eq(&dst_other
.oid
, &ren1
->pair
->two
->oid
)) {
1523 * Added file on the other side identical to
1524 * the file being renamed: clean merge.
1525 * Also, there is no need to overwrite the
1526 * file already in the working copy, so call
1527 * update_file_flags() instead of
1530 if (update_file_flags(o
,
1531 &ren1
->pair
->two
->oid
,
1532 ren1
->pair
->two
->mode
,
1534 1, /* update_cache */
1537 } else if (!oid_eq(&dst_other
.oid
, &null_oid
)) {
1540 output(o
, 1, _("CONFLICT (rename/add): Rename %s->%s in %s. "
1542 ren1_src
, ren1_dst
, branch1
,
1544 if (o
->call_depth
) {
1545 struct merge_file_info mfi
;
1546 if (merge_file_one(o
, ren1_dst
, &null_oid
, 0,
1547 &ren1
->pair
->two
->oid
,
1548 ren1
->pair
->two
->mode
,
1551 branch1
, branch2
, &mfi
)) {
1553 goto cleanup_and_return
;
1555 output(o
, 1, _("Adding merged %s"), ren1_dst
);
1556 if (update_file(o
, 0, &mfi
.oid
,
1557 mfi
.mode
, ren1_dst
))
1561 char *new_path
= unique_path(o
, ren1_dst
, branch2
);
1562 output(o
, 1, _("Adding as %s instead"), new_path
);
1563 if (update_file(o
, 0, &dst_other
.oid
,
1564 dst_other
.mode
, new_path
))
1571 if (clean_merge
< 0)
1572 goto cleanup_and_return
;
1574 struct diff_filespec
*one
, *a
, *b
;
1575 src_other
.path
= (char *)ren1_src
;
1577 one
= ren1
->pair
->one
;
1578 if (a_renames
== renames1
) {
1579 a
= ren1
->pair
->two
;
1582 b
= ren1
->pair
->two
;
1585 update_entry(ren1
->dst_entry
, one
, a
, b
);
1586 setup_rename_conflict_info(RENAME_NORMAL
,
1600 string_list_clear(&a_by_dst
, 0);
1601 string_list_clear(&b_by_dst
, 0);
1606 static struct object_id
*stage_oid(const struct object_id
*oid
, unsigned mode
)
1608 return (is_null_oid(oid
) || mode
== 0) ? NULL
: (struct object_id
*)oid
;
1611 static int read_oid_strbuf(struct merge_options
*o
,
1612 const struct object_id
*oid
, struct strbuf
*dst
)
1615 enum object_type type
;
1617 buf
= read_sha1_file(oid
->hash
, &type
, &size
);
1619 return err(o
, _("cannot read object %s"), oid_to_hex(oid
));
1620 if (type
!= OBJ_BLOB
) {
1622 return err(o
, _("object %s is not a blob"), oid_to_hex(oid
));
1624 strbuf_attach(dst
, buf
, size
, size
+ 1);
1628 static int blob_unchanged(struct merge_options
*opt
,
1629 const struct object_id
*o_oid
,
1631 const struct object_id
*a_oid
,
1633 int renormalize
, const char *path
)
1635 struct strbuf o
= STRBUF_INIT
;
1636 struct strbuf a
= STRBUF_INIT
;
1637 int ret
= 0; /* assume changed for safety */
1639 if (a_mode
!= o_mode
)
1641 if (oid_eq(o_oid
, a_oid
))
1646 assert(o_oid
&& a_oid
);
1647 if (read_oid_strbuf(opt
, o_oid
, &o
) || read_oid_strbuf(opt
, a_oid
, &a
))
1650 * Note: binary | is used so that both renormalizations are
1651 * performed. Comparison can be skipped if both files are
1652 * unchanged since their sha1s have already been compared.
1654 if (renormalize_buffer(path
, o
.buf
, o
.len
, &o
) |
1655 renormalize_buffer(path
, a
.buf
, a
.len
, &a
))
1656 ret
= (o
.len
== a
.len
&& !memcmp(o
.buf
, a
.buf
, o
.len
));
1664 static int handle_modify_delete(struct merge_options
*o
,
1666 struct object_id
*o_oid
, int o_mode
,
1667 struct object_id
*a_oid
, int a_mode
,
1668 struct object_id
*b_oid
, int b_mode
)
1670 return handle_change_delete(o
,
1675 _("modify"), _("modified"));
1678 static int merge_content(struct merge_options
*o
,
1680 struct object_id
*o_oid
, int o_mode
,
1681 struct object_id
*a_oid
, int a_mode
,
1682 struct object_id
*b_oid
, int b_mode
,
1683 struct rename_conflict_info
*rename_conflict_info
)
1685 const char *reason
= _("content");
1686 const char *path1
= NULL
, *path2
= NULL
;
1687 struct merge_file_info mfi
;
1688 struct diff_filespec one
, a
, b
;
1689 unsigned df_conflict_remains
= 0;
1692 reason
= _("add/add");
1693 o_oid
= (struct object_id
*)&null_oid
;
1695 one
.path
= a
.path
= b
.path
= (char *)path
;
1696 oidcpy(&one
.oid
, o_oid
);
1698 oidcpy(&a
.oid
, a_oid
);
1700 oidcpy(&b
.oid
, b_oid
);
1703 if (rename_conflict_info
) {
1704 struct diff_filepair
*pair1
= rename_conflict_info
->pair1
;
1706 path1
= (o
->branch1
== rename_conflict_info
->branch1
) ?
1707 pair1
->two
->path
: pair1
->one
->path
;
1708 /* If rename_conflict_info->pair2 != NULL, we are in
1709 * RENAME_ONE_FILE_TO_ONE case. Otherwise, we have a
1712 path2
= (rename_conflict_info
->pair2
||
1713 o
->branch2
== rename_conflict_info
->branch1
) ?
1714 pair1
->two
->path
: pair1
->one
->path
;
1716 if (dir_in_way(path
, !o
->call_depth
,
1717 S_ISGITLINK(pair1
->two
->mode
)))
1718 df_conflict_remains
= 1;
1720 if (merge_file_special_markers(o
, &one
, &a
, &b
,
1722 o
->branch2
, path2
, &mfi
))
1725 if (mfi
.clean
&& !df_conflict_remains
&&
1726 oid_eq(&mfi
.oid
, a_oid
) && mfi
.mode
== a_mode
) {
1727 int path_renamed_outside_HEAD
;
1728 output(o
, 3, _("Skipped %s (merged same as existing)"), path
);
1730 * The content merge resulted in the same file contents we
1731 * already had. We can return early if those file contents
1732 * are recorded at the correct path (which may not be true
1733 * if the merge involves a rename).
1735 path_renamed_outside_HEAD
= !path2
|| !strcmp(path
, path2
);
1736 if (!path_renamed_outside_HEAD
) {
1737 add_cacheinfo(o
, mfi
.mode
, &mfi
.oid
, path
,
1738 0, (!o
->call_depth
), 0);
1742 output(o
, 2, _("Auto-merging %s"), path
);
1745 if (S_ISGITLINK(mfi
.mode
))
1746 reason
= _("submodule");
1747 output(o
, 1, _("CONFLICT (%s): Merge conflict in %s"),
1749 if (rename_conflict_info
&& !df_conflict_remains
)
1750 if (update_stages(o
, path
, &one
, &a
, &b
))
1754 if (df_conflict_remains
) {
1756 if (o
->call_depth
) {
1757 remove_file_from_cache(path
);
1760 if (update_stages(o
, path
, &one
, &a
, &b
))
1763 int file_from_stage2
= was_tracked(path
);
1764 struct diff_filespec merged
;
1765 oidcpy(&merged
.oid
, &mfi
.oid
);
1766 merged
.mode
= mfi
.mode
;
1768 if (update_stages(o
, path
, NULL
,
1769 file_from_stage2
? &merged
: NULL
,
1770 file_from_stage2
? NULL
: &merged
))
1775 new_path
= unique_path(o
, path
, rename_conflict_info
->branch1
);
1776 output(o
, 1, _("Adding as %s instead"), new_path
);
1777 if (update_file(o
, 0, &mfi
.oid
, mfi
.mode
, new_path
)) {
1783 } else if (update_file(o
, mfi
.clean
, &mfi
.oid
, mfi
.mode
, path
))
1788 /* Per entry merge function */
1789 static int process_entry(struct merge_options
*o
,
1790 const char *path
, struct stage_data
*entry
)
1792 int clean_merge
= 1;
1793 int normalize
= o
->renormalize
;
1794 unsigned o_mode
= entry
->stages
[1].mode
;
1795 unsigned a_mode
= entry
->stages
[2].mode
;
1796 unsigned b_mode
= entry
->stages
[3].mode
;
1797 struct object_id
*o_oid
= stage_oid(&entry
->stages
[1].oid
, o_mode
);
1798 struct object_id
*a_oid
= stage_oid(&entry
->stages
[2].oid
, a_mode
);
1799 struct object_id
*b_oid
= stage_oid(&entry
->stages
[3].oid
, b_mode
);
1801 entry
->processed
= 1;
1802 if (entry
->rename_conflict_info
) {
1803 struct rename_conflict_info
*conflict_info
= entry
->rename_conflict_info
;
1804 switch (conflict_info
->rename_type
) {
1806 case RENAME_ONE_FILE_TO_ONE
:
1807 clean_merge
= merge_content(o
, path
,
1808 o_oid
, o_mode
, a_oid
, a_mode
, b_oid
, b_mode
,
1813 if (conflict_rename_delete(o
,
1814 conflict_info
->pair1
,
1815 conflict_info
->branch1
,
1816 conflict_info
->branch2
))
1819 case RENAME_ONE_FILE_TO_TWO
:
1821 if (conflict_rename_rename_1to2(o
, conflict_info
))
1824 case RENAME_TWO_FILES_TO_ONE
:
1826 if (conflict_rename_rename_2to1(o
, conflict_info
))
1830 entry
->processed
= 0;
1833 } else if (o_oid
&& (!a_oid
|| !b_oid
)) {
1834 /* Case A: Deleted in one */
1835 if ((!a_oid
&& !b_oid
) ||
1836 (!b_oid
&& blob_unchanged(o
, o_oid
, o_mode
, a_oid
, a_mode
, normalize
, path
)) ||
1837 (!a_oid
&& blob_unchanged(o
, o_oid
, o_mode
, b_oid
, b_mode
, normalize
, path
))) {
1838 /* Deleted in both or deleted in one and
1839 * unchanged in the other */
1841 output(o
, 2, _("Removing %s"), path
);
1842 /* do not touch working file if it did not exist */
1843 remove_file(o
, 1, path
, !a_oid
);
1845 /* Modify/delete; deleted side may have put a directory in the way */
1847 if (handle_modify_delete(o
, path
, o_oid
, o_mode
,
1848 a_oid
, a_mode
, b_oid
, b_mode
))
1851 } else if ((!o_oid
&& a_oid
&& !b_oid
) ||
1852 (!o_oid
&& !a_oid
&& b_oid
)) {
1853 /* Case B: Added in one. */
1854 /* [nothing|directory] -> ([nothing|directory], file) */
1856 const char *add_branch
;
1857 const char *other_branch
;
1859 const struct object_id
*oid
;
1863 add_branch
= o
->branch1
;
1864 other_branch
= o
->branch2
;
1867 conf
= _("file/directory");
1869 add_branch
= o
->branch2
;
1870 other_branch
= o
->branch1
;
1873 conf
= _("directory/file");
1875 if (dir_in_way(path
, !o
->call_depth
,
1876 S_ISGITLINK(a_mode
))) {
1877 char *new_path
= unique_path(o
, path
, add_branch
);
1879 output(o
, 1, _("CONFLICT (%s): There is a directory with name %s in %s. "
1881 conf
, path
, other_branch
, path
, new_path
);
1882 if (update_file(o
, 0, oid
, mode
, new_path
))
1884 else if (o
->call_depth
)
1885 remove_file_from_cache(path
);
1888 output(o
, 2, _("Adding %s"), path
);
1889 /* do not overwrite file if already present */
1890 if (update_file_flags(o
, oid
, mode
, path
, 1, !a_oid
))
1893 } else if (a_oid
&& b_oid
) {
1894 /* Case C: Added in both (check for same permissions) and */
1895 /* case D: Modified in both, but differently. */
1896 clean_merge
= merge_content(o
, path
,
1897 o_oid
, o_mode
, a_oid
, a_mode
, b_oid
, b_mode
,
1899 } else if (!o_oid
&& !a_oid
&& !b_oid
) {
1901 * this entry was deleted altogether. a_mode == 0 means
1902 * we had that path and want to actively remove it.
1904 remove_file(o
, 1, path
, !a_mode
);
1906 die("BUG: fatal merge failure, shouldn't happen.");
1911 int merge_trees(struct merge_options
*o
,
1914 struct tree
*common
,
1915 struct tree
**result
)
1919 if (o
->subtree_shift
) {
1920 merge
= shift_tree_object(head
, merge
, o
->subtree_shift
);
1921 common
= shift_tree_object(head
, common
, o
->subtree_shift
);
1924 if (oid_eq(&common
->object
.oid
, &merge
->object
.oid
)) {
1925 output(o
, 0, _("Already up-to-date!"));
1930 code
= git_merge_trees(o
->call_depth
, common
, head
, merge
);
1933 if (show(o
, 4) || o
->call_depth
)
1934 err(o
, _("merging of trees %s and %s failed"),
1935 oid_to_hex(&head
->object
.oid
),
1936 oid_to_hex(&merge
->object
.oid
));
1940 if (unmerged_cache()) {
1941 struct string_list
*entries
, *re_head
, *re_merge
;
1943 string_list_clear(&o
->current_file_set
, 1);
1944 string_list_clear(&o
->current_directory_set
, 1);
1945 get_files_dirs(o
, head
);
1946 get_files_dirs(o
, merge
);
1948 entries
= get_unmerged();
1949 record_df_conflict_files(o
, entries
);
1950 re_head
= get_renames(o
, head
, common
, head
, merge
, entries
);
1951 re_merge
= get_renames(o
, merge
, common
, head
, merge
, entries
);
1952 clean
= process_renames(o
, re_head
, re_merge
);
1955 for (i
= entries
->nr
-1; 0 <= i
; i
--) {
1956 const char *path
= entries
->items
[i
].string
;
1957 struct stage_data
*e
= entries
->items
[i
].util
;
1958 if (!e
->processed
) {
1959 int ret
= process_entry(o
, path
, e
);
1966 for (i
= 0; i
< entries
->nr
; i
++) {
1967 struct stage_data
*e
= entries
->items
[i
].util
;
1969 die("BUG: unprocessed path??? %s",
1970 entries
->items
[i
].string
);
1973 string_list_clear(re_merge
, 0);
1974 string_list_clear(re_head
, 0);
1975 string_list_clear(entries
, 1);
1984 if (o
->call_depth
&& !(*result
= write_tree_from_memory(o
)))
1990 static struct commit_list
*reverse_commit_list(struct commit_list
*list
)
1992 struct commit_list
*next
= NULL
, *current
, *backup
;
1993 for (current
= list
; current
; current
= backup
) {
1994 backup
= current
->next
;
1995 current
->next
= next
;
2002 * Merge the commits h1 and h2, return the resulting virtual
2003 * commit object and a flag indicating the cleanness of the merge.
2005 int merge_recursive(struct merge_options
*o
,
2008 struct commit_list
*ca
,
2009 struct commit
**result
)
2011 struct commit_list
*iter
;
2012 struct commit
*merged_common_ancestors
;
2013 struct tree
*mrtree
= mrtree
;
2017 output(o
, 4, _("Merging:"));
2018 output_commit_title(o
, h1
);
2019 output_commit_title(o
, h2
);
2023 ca
= get_merge_bases(h1
, h2
);
2024 ca
= reverse_commit_list(ca
);
2028 unsigned cnt
= commit_list_count(ca
);
2030 output(o
, 5, Q_("found %u common ancestor:",
2031 "found %u common ancestors:", cnt
), cnt
);
2032 for (iter
= ca
; iter
; iter
= iter
->next
)
2033 output_commit_title(o
, iter
->item
);
2036 merged_common_ancestors
= pop_commit(&ca
);
2037 if (merged_common_ancestors
== NULL
) {
2038 /* if there is no common ancestor, use an empty tree */
2041 tree
= lookup_tree(EMPTY_TREE_SHA1_BIN
);
2042 merged_common_ancestors
= make_virtual_commit(tree
, "ancestor");
2045 for (iter
= ca
; iter
; iter
= iter
->next
) {
2046 const char *saved_b1
, *saved_b2
;
2049 * When the merge fails, the result contains files
2050 * with conflict markers. The cleanness flag is
2051 * ignored (unless indicating an error), it was never
2052 * actually used, as result of merge_trees has always
2053 * overwritten it: the committed "conflicts" were
2057 saved_b1
= o
->branch1
;
2058 saved_b2
= o
->branch2
;
2059 o
->branch1
= "Temporary merge branch 1";
2060 o
->branch2
= "Temporary merge branch 2";
2061 if (merge_recursive(o
, merged_common_ancestors
, iter
->item
,
2062 NULL
, &merged_common_ancestors
) < 0)
2064 o
->branch1
= saved_b1
;
2065 o
->branch2
= saved_b2
;
2068 if (!merged_common_ancestors
)
2069 return err(o
, _("merge returned no commit"));
2076 o
->ancestor
= "merged common ancestors";
2077 clean
= merge_trees(o
, h1
->tree
, h2
->tree
, merged_common_ancestors
->tree
,
2084 if (o
->call_depth
) {
2085 *result
= make_virtual_commit(mrtree
, "merged tree");
2086 commit_list_insert(h1
, &(*result
)->parents
);
2087 commit_list_insert(h2
, &(*result
)->parents
->next
);
2090 if (!o
->call_depth
&& o
->buffer_output
< 2)
2091 strbuf_release(&o
->obuf
);
2093 diff_warn_rename_limit("merge.renamelimit",
2094 o
->needed_rename_limit
, 0);
2098 static struct commit
*get_ref(const struct object_id
*oid
, const char *name
)
2100 struct object
*object
;
2102 object
= deref_tag(parse_object(oid
->hash
), name
, strlen(name
));
2105 if (object
->type
== OBJ_TREE
)
2106 return make_virtual_commit((struct tree
*)object
, name
);
2107 if (object
->type
!= OBJ_COMMIT
)
2109 if (parse_commit((struct commit
*)object
))
2111 return (struct commit
*)object
;
2114 int merge_recursive_generic(struct merge_options
*o
,
2115 const struct object_id
*head
,
2116 const struct object_id
*merge
,
2118 const struct object_id
**base_list
,
2119 struct commit
**result
)
2122 struct lock_file
*lock
= xcalloc(1, sizeof(struct lock_file
));
2123 struct commit
*head_commit
= get_ref(head
, o
->branch1
);
2124 struct commit
*next_commit
= get_ref(merge
, o
->branch2
);
2125 struct commit_list
*ca
= NULL
;
2129 for (i
= 0; i
< num_base_list
; ++i
) {
2130 struct commit
*base
;
2131 if (!(base
= get_ref(base_list
[i
], oid_to_hex(base_list
[i
]))))
2132 return err(o
, _("Could not parse object '%s'"),
2133 oid_to_hex(base_list
[i
]));
2134 commit_list_insert(base
, &ca
);
2138 hold_locked_index(lock
, 1);
2139 clean
= merge_recursive(o
, head_commit
, next_commit
, ca
,
2144 if (active_cache_changed
&&
2145 write_locked_index(&the_index
, lock
, COMMIT_LOCK
))
2146 return err(o
, _("Unable to write index."));
2148 return clean
? 0 : 1;
2151 static void merge_recursive_config(struct merge_options
*o
)
2153 git_config_get_int("merge.verbosity", &o
->verbosity
);
2154 git_config_get_int("diff.renamelimit", &o
->diff_rename_limit
);
2155 git_config_get_int("merge.renamelimit", &o
->merge_rename_limit
);
2156 git_config(git_xmerge_config
, NULL
);
2159 void init_merge_options(struct merge_options
*o
)
2161 memset(o
, 0, sizeof(struct merge_options
));
2163 o
->buffer_output
= 1;
2164 o
->diff_rename_limit
= -1;
2165 o
->merge_rename_limit
= -1;
2167 o
->detect_rename
= 1;
2168 merge_recursive_config(o
);
2169 if (getenv("GIT_MERGE_VERBOSITY"))
2171 strtol(getenv("GIT_MERGE_VERBOSITY"), NULL
, 10);
2172 if (o
->verbosity
>= 5)
2173 o
->buffer_output
= 0;
2174 strbuf_init(&o
->obuf
, 0);
2175 string_list_init(&o
->current_file_set
, 1);
2176 string_list_init(&o
->current_directory_set
, 1);
2177 string_list_init(&o
->df_conflict_file_set
, 1);
2180 int parse_merge_opt(struct merge_options
*o
, const char *s
)
2186 if (!strcmp(s
, "ours"))
2187 o
->recursive_variant
= MERGE_RECURSIVE_OURS
;
2188 else if (!strcmp(s
, "theirs"))
2189 o
->recursive_variant
= MERGE_RECURSIVE_THEIRS
;
2190 else if (!strcmp(s
, "subtree"))
2191 o
->subtree_shift
= "";
2192 else if (skip_prefix(s
, "subtree=", &arg
))
2193 o
->subtree_shift
= arg
;
2194 else if (!strcmp(s
, "patience"))
2195 o
->xdl_opts
= DIFF_WITH_ALG(o
, PATIENCE_DIFF
);
2196 else if (!strcmp(s
, "histogram"))
2197 o
->xdl_opts
= DIFF_WITH_ALG(o
, HISTOGRAM_DIFF
);
2198 else if (skip_prefix(s
, "diff-algorithm=", &arg
)) {
2199 long value
= parse_algorithm_value(arg
);
2202 /* clear out previous settings */
2203 DIFF_XDL_CLR(o
, NEED_MINIMAL
);
2204 o
->xdl_opts
&= ~XDF_DIFF_ALGORITHM_MASK
;
2205 o
->xdl_opts
|= value
;
2207 else if (!strcmp(s
, "ignore-space-change"))
2208 o
->xdl_opts
|= XDF_IGNORE_WHITESPACE_CHANGE
;
2209 else if (!strcmp(s
, "ignore-all-space"))
2210 o
->xdl_opts
|= XDF_IGNORE_WHITESPACE
;
2211 else if (!strcmp(s
, "ignore-space-at-eol"))
2212 o
->xdl_opts
|= XDF_IGNORE_WHITESPACE_AT_EOL
;
2213 else if (!strcmp(s
, "renormalize"))
2215 else if (!strcmp(s
, "no-renormalize"))
2217 else if (!strcmp(s
, "no-renames"))
2218 o
->detect_rename
= 0;
2219 else if (!strcmp(s
, "find-renames")) {
2220 o
->detect_rename
= 1;
2221 o
->rename_score
= 0;
2223 else if (skip_prefix(s
, "find-renames=", &arg
) ||
2224 skip_prefix(s
, "rename-threshold=", &arg
)) {
2225 if ((o
->rename_score
= parse_rename_score(&arg
)) == -1 || *arg
!= 0)
2227 o
->detect_rename
= 1;