2 * "Ostensibly Recursive's Twin" merge strategy, or "ort" for short. Meant
3 * as a drop-in replacement for the "recursive" merge strategy, allowing one
6 * git merge [-s recursive]
12 * Note: git's parser allows the space between '-s' and its argument to be
13 * missing. (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo",
14 * "cale", "peedy", or "ins" instead of "ort"?)
18 #include "merge-ort.h"
22 #include "cache-tree.h"
24 #include "commit-reach.h"
29 #include "object-store.h"
32 #include "submodule.h"
34 #include "unpack-trees.h"
35 #include "xdiff-interface.h"
38 * We have many arrays of size 3. Whenever we have such an array, the
39 * indices refer to one of the sides of the three-way merge. This is so
40 * pervasive that the constants 0, 1, and 2 are used in many places in the
41 * code (especially in arithmetic operations to find the other side's index
42 * or to compute a relevant mask), but sometimes these enum names are used
43 * to aid code clarity.
45 * See also 'filemask' and 'dirmask' in struct conflict_info; the "ith side"
46 * referred to there is one of these three sides.
54 struct traversal_callback_data {
56 unsigned long dirmask;
57 struct name_entry names[3];
62 * All variables that are arrays of size 3 correspond to data tracked
63 * for the sides in enum merge_side. Index 0 is almost always unused
64 * because we often only need to track information for MERGE_SIDE1 and
65 * MERGE_SIDE2 (MERGE_BASE can't have rename information since renames
66 * are determined relative to what changed since the MERGE_BASE).
70 * pairs: pairing of filenames from diffcore_rename()
72 struct diff_queue_struct pairs[3];
75 * dirs_removed: directories removed on a given side of history.
77 struct strset dirs_removed[3];
80 * dir_rename_count: tracking where parts of a directory were renamed to
82 * When files in a directory are renamed, they may not all go to the
83 * same location. Each strmap here tracks:
84 * old_dir => {new_dir => int}
85 * That is, dir_rename_count[side] is a strmap to a strintmap.
87 struct strmap dir_rename_count[3];
90 * dir_renames: computed directory renames
92 * This is a map of old_dir => new_dir and is derived in part from
95 struct strmap dir_renames[3];
98 * relevant_sources: deleted paths for which we need rename detection
100 * relevant_sources is a set of deleted paths on each side of
101 * history for which we need rename detection. If a path is deleted
102 * on one side of history, we need to detect if it is part of a
104 * * we need to detect renames for an ancestor directory
105 * * the file is modified/deleted on the other side of history
106 * If neither of those are true, we can skip rename detection for
109 struct strset relevant_sources[3];
112 * callback_data_*: supporting data structures for alternate traversal
114 * We sometimes need to be able to traverse through all the files
115 * in a given tree before all immediate subdirectories within that
116 * tree. Since traverse_trees() doesn't do that naturally, we have
117 * a traverse_trees_wrapper() that stores any immediate
118 * subdirectories while traversing files, then traverses the
119 * immediate subdirectories later. These callback_data* variables
120 * store the information for the subdirectories so that we can do
121 * that traversal order.
123 struct traversal_callback_data *callback_data;
124 int callback_data_nr, callback_data_alloc;
125 char *callback_data_traverse_path;
128 * needed_limit: value needed for inexact rename detection to run
130 * If the current rename limit wasn't high enough for inexact
131 * rename detection to run, this records the limit needed. Otherwise,
132 * this value remains 0.
137 struct merge_options_internal {
139 * paths: primary data structure in all of merge ort.
142 * * are full relative paths from the toplevel of the repository
143 * (e.g. "drivers/firmware/raspberrypi.c").
144 * * store all relevant paths in the repo, both directories and
145 * files (e.g. drivers, drivers/firmware would also be included)
146 * * these keys serve to intern all the path strings, which allows
147 * us to do pointer comparison on directory names instead of
148 * strcmp; we just have to be careful to use the interned strings.
149 * (Technically paths_to_free may track some strings that were
150 * removed from froms paths.)
152 * The values of paths:
153 * * either a pointer to a merged_info, or a conflict_info struct
154 * * merged_info contains all relevant information for a
155 * non-conflicted entry.
156 * * conflict_info contains a merged_info, plus any additional
157 * information about a conflict such as the higher orders stages
158 * involved and the names of the paths those came from (handy
159 * once renames get involved).
160 * * a path may start "conflicted" (i.e. point to a conflict_info)
161 * and then a later step (e.g. three-way content merge) determines
162 * it can be cleanly merged, at which point it'll be marked clean
163 * and the algorithm will ignore any data outside the contained
164 * merged_info for that entry
165 * * If an entry remains conflicted, the merged_info portion of a
166 * conflict_info will later be filled with whatever version of
167 * the file should be placed in the working directory (e.g. an
168 * as-merged-as-possible variation that contains conflict markers).
173 * conflicted: a subset of keys->values from "paths"
175 * conflicted is basically an optimization between process_entries()
176 * and record_conflicted_index_entries(); the latter could loop over
177 * ALL the entries in paths AGAIN and look for the ones that are
178 * still conflicted, but since process_entries() has to loop over
179 * all of them, it saves the ones it couldn't resolve in this strmap
180 * so that record_conflicted_index_entries() can iterate just the
183 struct strmap conflicted;
186 * paths_to_free: additional list of strings to free
188 * If keys are removed from "paths", they are added to paths_to_free
189 * to ensure they are later freed. We avoid free'ing immediately since
190 * other places (e.g. conflict_info.pathnames[]) may still be
191 * referencing these paths.
193 struct string_list paths_to_free;
196 * output: special messages and conflict notices for various paths
198 * This is a map of pathnames (a subset of the keys in "paths" above)
199 * to strbufs. It gathers various warning/conflict/notice messages
200 * for later processing.
202 struct strmap output;
205 * renames: various data relating to rename detection
207 struct rename_info renames;
210 * current_dir_name, toplevel_dir: temporary vars
212 * These are used in collect_merge_info_callback(), and will set the
213 * various merged_info.directory_name for the various paths we get;
214 * see documentation for that variable and the requirements placed on
217 const char *current_dir_name;
218 const char *toplevel_dir;
220 /* call_depth: recursion level counter for merging merge bases */
224 struct version_info {
225 struct object_id oid;
230 /* if is_null, ignore result. otherwise result has oid & mode */
231 struct version_info result;
235 * clean: whether the path in question is cleanly merged.
237 * see conflict_info.merged for more details.
242 * basename_offset: offset of basename of path.
244 * perf optimization to avoid recomputing offset of final '/'
245 * character in pathname (0 if no '/' in pathname).
247 size_t basename_offset;
250 * directory_name: containing directory name.
252 * Note that we assume directory_name is constructed such that
253 * strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name,
254 * i.e. string equality is equivalent to pointer equality. For this
255 * to hold, we have to be careful setting directory_name.
257 const char *directory_name;
260 struct conflict_info {
262 * merged: the version of the path that will be written to working tree
264 * WARNING: It is critical to check merged.clean and ensure it is 0
265 * before reading any conflict_info fields outside of merged.
266 * Allocated merge_info structs will always have clean set to 1.
267 * Allocated conflict_info structs will have merged.clean set to 0
268 * initially. The merged.clean field is how we know if it is safe
269 * to access other parts of conflict_info besides merged; if a
270 * conflict_info's merged.clean is changed to 1, the rest of the
271 * algorithm is not allowed to look at anything outside of the
272 * merged member anymore.
274 struct merged_info merged;
276 /* oids & modes from each of the three trees for this path */
277 struct version_info stages[3];
279 /* pathnames for each stage; may differ due to rename detection */
280 const char *pathnames[3];
282 /* Whether this path is/was involved in a directory/file conflict */
283 unsigned df_conflict:1;
286 * Whether this path is/was involved in a non-content conflict other
287 * than a directory/file conflict (e.g. rename/rename, rename/delete,
288 * file location based on possible directory rename).
290 unsigned path_conflict:1;
293 * For filemask and dirmask, the ith bit corresponds to whether the
294 * ith entry is a file (filemask) or a directory (dirmask). Thus,
295 * filemask & dirmask is always zero, and filemask | dirmask is at
296 * most 7 but can be less when a path does not appear as either a
297 * file or a directory on at least one side of history.
299 * Note that these masks are related to enum merge_side, as the ith
300 * entry corresponds to side i.
302 * These values come from a traverse_trees() call; more info may be
303 * found looking at tree-walk.h's struct traverse_info,
304 * particularly the documentation above the "fn" member (note that
305 * filemask = mask & ~dirmask from that documentation).
311 * Optimization to track which stages match, to avoid the need to
312 * recompute it in multiple steps. Either 0 or at least 2 bits are
313 * set; if at least 2 bits are set, their corresponding stages match.
315 unsigned match_mask:3;
318 /*** Function Grouping: various utility functions ***/
321 * For the next three macros, see warning for conflict_info.merged.
323 * In each of the below, mi is a struct merged_info*, and ci was defined
324 * as a struct conflict_info* (but we need to verify ci isn't actually
325 * pointed at a struct merged_info*).
327 * INITIALIZE_CI: Assign ci to mi but only if it's safe; set to NULL otherwise.
328 * VERIFY_CI: Ensure that something we assigned to a conflict_info* is one.
329 * ASSIGN_AND_VERIFY_CI: Similar to VERIFY_CI but do assignment first.
331 #define INITIALIZE_CI(ci, mi) do { \
332 (ci) = (!(mi) || (mi)->clean) ? NULL : (struct conflict_info *)(mi); \
334 #define VERIFY_CI(ci) assert(ci && !ci->merged.clean);
335 #define ASSIGN_AND_VERIFY_CI(ci, mi) do { \
336 (ci) = (struct conflict_info *)(mi); \
337 assert((ci) && !(mi)->clean); \
340 static void free_strmap_strings(struct strmap *map)
342 struct hashmap_iter iter;
343 struct strmap_entry *entry;
345 strmap_for_each_entry(map, &iter, entry) {
346 free((char*)entry->key);
350 static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,
353 struct rename_info *renames = &opti->renames;
355 void (*strmap_func)(struct strmap *, int) =
356 reinitialize ? strmap_partial_clear : strmap_clear;
357 void (*strset_func)(struct strset *) =
358 reinitialize ? strset_partial_clear : strset_clear;
361 * We marked opti->paths with strdup_strings = 0, so that we
362 * wouldn't have to make another copy of the fullpath created by
363 * make_traverse_path from setup_path_info(). But, now that we've
364 * used it and have no other references to these strings, it is time
365 * to deallocate them.
367 free_strmap_strings(&opti->paths);
368 strmap_func(&opti->paths, 1);
371 * All keys and values in opti->conflicted are a subset of those in
372 * opti->paths. We don't want to deallocate anything twice, so we
373 * don't free the keys and we pass 0 for free_values.
375 strmap_func(&opti->conflicted, 0);
378 * opti->paths_to_free is similar to opti->paths; we created it with
379 * strdup_strings = 0 to avoid making _another_ copy of the fullpath
380 * but now that we've used it and have no other references to these
381 * strings, it is time to deallocate them. We do so by temporarily
382 * setting strdup_strings to 1.
384 opti->paths_to_free.strdup_strings = 1;
385 string_list_clear(&opti->paths_to_free, 0);
386 opti->paths_to_free.strdup_strings = 0;
388 /* Free memory used by various renames maps */
389 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; ++i) {
390 strset_func(&renames->dirs_removed[i]);
392 partial_clear_dir_rename_count(&renames->dir_rename_count[i]);
394 strmap_clear(&renames->dir_rename_count[i], 1);
396 strmap_func(&renames->dir_renames[i], 0);
398 strset_func(&renames->relevant_sources[i]);
402 struct hashmap_iter iter;
403 struct strmap_entry *e;
405 /* Release and free each strbuf found in output */
406 strmap_for_each_entry(&opti->output, &iter, e) {
407 struct strbuf *sb = e->value;
410 * While strictly speaking we don't need to free(sb)
411 * here because we could pass free_values=1 when
412 * calling strmap_clear() on opti->output, that would
413 * require strmap_clear to do another
414 * strmap_for_each_entry() loop, so we just free it
415 * while we're iterating anyway.
419 strmap_clear(&opti->output, 0);
422 /* Clean out callback_data as well. */
423 FREE_AND_NULL(renames->callback_data);
424 renames->callback_data_nr = renames->callback_data_alloc = 0;
427 static int err(struct merge_options *opt, const char *err, ...)
430 struct strbuf sb = STRBUF_INIT;
432 strbuf_addstr(&sb, "error: ");
433 va_start(params, err);
434 strbuf_vaddf(&sb, err, params);
443 static void format_commit(struct strbuf *sb,
445 struct commit *commit)
447 struct merge_remote_desc *desc;
448 struct pretty_print_context ctx = {0};
449 ctx.abbrev = DEFAULT_ABBREV;
451 strbuf_addchars(sb, ' ', indent);
452 desc = merge_remote_util(commit);
454 strbuf_addf(sb, "virtual %s\n", desc->name);
458 format_commit_message(commit, "%h %s", sb, &ctx);
459 strbuf_addch(sb, '\n');
462 __attribute__((format (printf, 4, 5)))
463 static void path_msg(struct merge_options *opt,
465 int omittable_hint, /* skippable under --remerge-diff */
466 const char *fmt, ...)
469 struct strbuf *sb = strmap_get(&opt->priv->output, path);
471 sb = xmalloc(sizeof(*sb));
473 strmap_put(&opt->priv->output, path, sb);
477 strbuf_vaddf(sb, fmt, ap);
480 strbuf_addch(sb, '\n');
483 /* add a string to a strbuf, but converting "/" to "_" */
484 static void add_flattened_path(struct strbuf *out, const char *s)
487 strbuf_addstr(out, s);
488 for (; i < out->len; i++)
489 if (out->buf[i] == '/')
493 static char *unique_path(struct strmap *existing_paths,
497 struct strbuf newpath = STRBUF_INIT;
501 strbuf_addf(&newpath, "%s~", path);
502 add_flattened_path(&newpath, branch);
504 base_len = newpath.len;
505 while (strmap_contains(existing_paths, newpath.buf)) {
506 strbuf_setlen(&newpath, base_len);
507 strbuf_addf(&newpath, "_%d", suffix++);
510 return strbuf_detach(&newpath, NULL);
513 /*** Function Grouping: functions related to collect_merge_info() ***/
515 static int traverse_trees_wrapper_callback(int n,
517 unsigned long dirmask,
518 struct name_entry *names,
519 struct traverse_info *info)
521 struct merge_options *opt = info->data;
522 struct rename_info *renames = &opt->priv->renames;
526 if (!renames->callback_data_traverse_path)
527 renames->callback_data_traverse_path = xstrdup(info->traverse_path);
529 ALLOC_GROW(renames->callback_data, renames->callback_data_nr + 1,
530 renames->callback_data_alloc);
531 renames->callback_data[renames->callback_data_nr].mask = mask;
532 renames->callback_data[renames->callback_data_nr].dirmask = dirmask;
533 COPY_ARRAY(renames->callback_data[renames->callback_data_nr].names,
535 renames->callback_data_nr++;
541 * Much like traverse_trees(), BUT:
542 * - read all the tree entries FIRST, saving them
543 * - note that the above step provides an opportunity to compute necessary
544 * additional details before the "real" traversal
545 * - loop through the saved entries and call the original callback on them
548 static int traverse_trees_wrapper(struct index_state *istate,
551 struct traverse_info *info)
553 int ret, i, old_offset;
554 traverse_callback_t old_fn;
555 char *old_callback_data_traverse_path;
556 struct merge_options *opt = info->data;
557 struct rename_info *renames = &opt->priv->renames;
559 old_callback_data_traverse_path = renames->callback_data_traverse_path;
561 old_offset = renames->callback_data_nr;
563 renames->callback_data_traverse_path = NULL;
564 info->fn = traverse_trees_wrapper_callback;
565 ret = traverse_trees(istate, n, t, info);
569 info->traverse_path = renames->callback_data_traverse_path;
571 for (i = old_offset; i < renames->callback_data_nr; ++i) {
573 renames->callback_data[i].mask,
574 renames->callback_data[i].dirmask,
575 renames->callback_data[i].names,
579 renames->callback_data_nr = old_offset;
580 free(renames->callback_data_traverse_path);
581 renames->callback_data_traverse_path = old_callback_data_traverse_path;
582 info->traverse_path = NULL;
586 static void setup_path_info(struct merge_options *opt,
587 struct string_list_item *result,
588 const char *current_dir_name,
589 int current_dir_name_len,
590 char *fullpath, /* we'll take over ownership */
591 struct name_entry *names,
592 struct name_entry *merged_version,
593 unsigned is_null, /* boolean */
594 unsigned df_conflict, /* boolean */
597 int resolved /* boolean */)
599 /* result->util is void*, so mi is a convenience typed variable */
600 struct merged_info *mi;
602 assert(!is_null || resolved);
603 assert(!df_conflict || !resolved); /* df_conflict implies !resolved */
604 assert(resolved == (merged_version != NULL));
606 mi = xcalloc(1, resolved ? sizeof(struct merged_info) :
607 sizeof(struct conflict_info));
608 mi->directory_name = current_dir_name;
609 mi->basename_offset = current_dir_name_len;
610 mi->clean = !!resolved;
612 mi->result.mode = merged_version->mode;
613 oidcpy(&mi->result.oid, &merged_version->oid);
614 mi->is_null = !!is_null;
617 struct conflict_info *ci;
619 ASSIGN_AND_VERIFY_CI(ci, mi);
620 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
621 ci->pathnames[i] = fullpath;
622 ci->stages[i].mode = names[i].mode;
623 oidcpy(&ci->stages[i].oid, &names[i].oid);
625 ci->filemask = filemask;
626 ci->dirmask = dirmask;
627 ci->df_conflict = !!df_conflict;
630 * Assume is_null for now, but if we have entries
631 * under the directory then when it is complete in
632 * write_completed_directory() it'll update this.
633 * Also, for D/F conflicts, we have to handle the
634 * directory first, then clear this bit and process
635 * the file to see how it is handled -- that occurs
636 * near the top of process_entry().
640 strmap_put(&opt->priv->paths, fullpath, mi);
641 result->string = fullpath;
645 static void add_pair(struct merge_options *opt,
646 struct name_entry *names,
647 const char *pathname,
649 unsigned is_add /* if false, is_delete */,
652 struct diff_filespec *one, *two;
653 struct rename_info *renames = &opt->priv->renames;
654 int names_idx = is_add ? side : 0;
657 unsigned content_relevant = (match_mask == 0);
658 unsigned location_relevant = 1; /* FIXME: compute this */
660 if (content_relevant || location_relevant)
661 strset_add(&renames->relevant_sources[side], pathname);
664 one = alloc_filespec(pathname);
665 two = alloc_filespec(pathname);
666 fill_filespec(is_add ? two : one,
667 &names[names_idx].oid, 1, names[names_idx].mode);
668 diff_queue(&renames->pairs[side], one, two);
671 static void collect_rename_info(struct merge_options *opt,
672 struct name_entry *names,
674 const char *fullname,
679 struct rename_info *renames = &opt->priv->renames;
682 /* Update dirs_removed, as needed */
683 if (dirmask == 1 || dirmask == 3 || dirmask == 5) {
684 /* absent_mask = 0x07 - dirmask; sides = absent_mask/2 */
685 unsigned sides = (0x07 - dirmask)/2;
687 strset_add(&renames->dirs_removed[1], fullname);
689 strset_add(&renames->dirs_removed[2], fullname);
692 if (filemask == 0 || filemask == 7)
695 for (side = MERGE_SIDE1; side <= MERGE_SIDE2; ++side) {
696 unsigned side_mask = (1 << side);
698 /* Check for deletion on side */
699 if ((filemask & 1) && !(filemask & side_mask))
700 add_pair(opt, names, fullname, side, 0 /* delete */,
701 match_mask & filemask);
703 /* Check for addition on side */
704 if (!(filemask & 1) && (filemask & side_mask))
705 add_pair(opt, names, fullname, side, 1 /* add */,
706 match_mask & filemask);
710 static int collect_merge_info_callback(int n,
712 unsigned long dirmask,
713 struct name_entry *names,
714 struct traverse_info *info)
718 * common ancestor (mbase) has mask 1, and stored in index 0 of names
719 * head of side 1 (side1) has mask 2, and stored in index 1 of names
720 * head of side 2 (side2) has mask 4, and stored in index 2 of names
722 struct merge_options *opt = info->data;
723 struct merge_options_internal *opti = opt->priv;
724 struct string_list_item pi; /* Path Info */
725 struct conflict_info *ci; /* typed alias to pi.util (which is void*) */
726 struct name_entry *p;
729 const char *dirname = opti->current_dir_name;
730 unsigned filemask = mask & ~dirmask;
731 unsigned match_mask = 0; /* will be updated below */
732 unsigned mbase_null = !(mask & 1);
733 unsigned side1_null = !(mask & 2);
734 unsigned side2_null = !(mask & 4);
735 unsigned side1_matches_mbase = (!side1_null && !mbase_null &&
736 names[0].mode == names[1].mode &&
737 oideq(&names[0].oid, &names[1].oid));
738 unsigned side2_matches_mbase = (!side2_null && !mbase_null &&
739 names[0].mode == names[2].mode &&
740 oideq(&names[0].oid, &names[2].oid));
741 unsigned sides_match = (!side1_null && !side2_null &&
742 names[1].mode == names[2].mode &&
743 oideq(&names[1].oid, &names[2].oid));
746 * Note: When a path is a file on one side of history and a directory
747 * in another, we have a directory/file conflict. In such cases, if
748 * the conflict doesn't resolve from renames and deletions, then we
749 * always leave directories where they are and move files out of the
750 * way. Thus, while struct conflict_info has a df_conflict field to
751 * track such conflicts, we ignore that field for any directories at
752 * a path and only pay attention to it for files at the given path.
753 * The fact that we leave directories were they are also means that
754 * we do not need to worry about getting additional df_conflict
755 * information propagated from parent directories down to children
756 * (unlike, say traverse_trees_recursive() in unpack-trees.c, which
757 * sets a newinfo.df_conflicts field specifically to propagate it).
759 unsigned df_conflict = (filemask != 0) && (dirmask != 0);
761 /* n = 3 is a fundamental assumption. */
763 BUG("Called collect_merge_info_callback wrong");
766 * A bunch of sanity checks verifying that traverse_trees() calls
767 * us the way I expect. Could just remove these at some point,
768 * though maybe they are helpful to future code readers.
770 assert(mbase_null == is_null_oid(&names[0].oid));
771 assert(side1_null == is_null_oid(&names[1].oid));
772 assert(side2_null == is_null_oid(&names[2].oid));
773 assert(!mbase_null || !side1_null || !side2_null);
774 assert(mask > 0 && mask < 8);
776 /* Determine match_mask */
777 if (side1_matches_mbase)
778 match_mask = (side2_matches_mbase ? 7 : 3);
779 else if (side2_matches_mbase)
781 else if (sides_match)
785 * Get the name of the relevant filepath, which we'll pass to
786 * setup_path_info() for tracking.
791 len = traverse_path_len(info, p->pathlen);
793 /* +1 in both of the following lines to include the NUL byte */
794 fullpath = xmalloc(len + 1);
795 make_traverse_path(fullpath, len + 1, info, p->path, p->pathlen);
798 * If mbase, side1, and side2 all match, we can resolve early. Even
799 * if these are trees, there will be no renames or anything
802 if (side1_matches_mbase && side2_matches_mbase) {
803 /* mbase, side1, & side2 all match; use mbase as resolution */
804 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
805 names, names+0, mbase_null, 0,
806 filemask, dirmask, 1);
811 * Gather additional information used in rename detection.
813 collect_rename_info(opt, names, dirname, fullpath,
814 filemask, dirmask, match_mask);
817 * Record information about the path so we can resolve later in
820 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
821 names, NULL, 0, df_conflict, filemask, dirmask, 0);
825 ci->match_mask = match_mask;
827 /* If dirmask, recurse into subdirectories */
829 struct traverse_info newinfo;
830 struct tree_desc t[3];
831 void *buf[3] = {NULL, NULL, NULL};
832 const char *original_dir_name;
835 ci->match_mask &= filemask;
838 newinfo.name = p->path;
839 newinfo.namelen = p->pathlen;
840 newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1);
842 * If this directory we are about to recurse into cared about
843 * its parent directory (the current directory) having a D/F
844 * conflict, then we'd propagate the masks in this way:
845 * newinfo.df_conflicts |= (mask & ~dirmask);
846 * But we don't worry about propagating D/F conflicts. (See
847 * comment near setting of local df_conflict variable near
848 * the beginning of this function).
851 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
852 if (i == 1 && side1_matches_mbase)
854 else if (i == 2 && side2_matches_mbase)
856 else if (i == 2 && sides_match)
859 const struct object_id *oid = NULL;
862 buf[i] = fill_tree_descriptor(opt->repo,
868 original_dir_name = opti->current_dir_name;
869 opti->current_dir_name = pi.string;
870 ret = traverse_trees(NULL, 3, t, &newinfo);
871 opti->current_dir_name = original_dir_name;
873 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++)
883 static int collect_merge_info(struct merge_options *opt,
884 struct tree *merge_base,
889 struct tree_desc t[3];
890 struct traverse_info info;
892 opt->priv->toplevel_dir = "";
893 opt->priv->current_dir_name = opt->priv->toplevel_dir;
894 setup_traverse_info(&info, opt->priv->toplevel_dir);
895 info.fn = collect_merge_info_callback;
897 info.show_all_errors = 1;
899 parse_tree(merge_base);
902 init_tree_desc(t + 0, merge_base->buffer, merge_base->size);
903 init_tree_desc(t + 1, side1->buffer, side1->size);
904 init_tree_desc(t + 2, side2->buffer, side2->size);
906 trace2_region_enter("merge", "traverse_trees", opt->repo);
907 ret = traverse_trees(NULL, 3, t, &info);
908 trace2_region_leave("merge", "traverse_trees", opt->repo);
913 /*** Function Grouping: functions related to threeway content merges ***/
915 static int find_first_merges(struct repository *repo,
919 struct object_array *result)
922 struct object_array merges = OBJECT_ARRAY_INIT;
923 struct commit *commit;
924 int contains_another;
926 char merged_revision[GIT_MAX_HEXSZ + 2];
927 const char *rev_args[] = { "rev-list", "--merges", "--ancestry-path",
928 "--all", merged_revision, NULL };
929 struct rev_info revs;
930 struct setup_revision_opt rev_opts;
932 memset(result, 0, sizeof(struct object_array));
933 memset(&rev_opts, 0, sizeof(rev_opts));
935 /* get all revisions that merge commit a */
936 xsnprintf(merged_revision, sizeof(merged_revision), "^%s",
937 oid_to_hex(&a->object.oid));
938 repo_init_revisions(repo, &revs, NULL);
939 rev_opts.submodule = path;
940 /* FIXME: can't handle linked worktrees in submodules yet */
941 revs.single_worktree = path != NULL;
942 setup_revisions(ARRAY_SIZE(rev_args)-1, rev_args, &revs, &rev_opts);
944 /* save all revisions from the above list that contain b */
945 if (prepare_revision_walk(&revs))
946 die("revision walk setup failed");
947 while ((commit = get_revision(&revs)) != NULL) {
948 struct object *o = &(commit->object);
949 if (in_merge_bases(b, commit))
950 add_object_array(o, NULL, &merges);
952 reset_revision_walk();
954 /* Now we've got all merges that contain a and b. Prune all
955 * merges that contain another found merge and save them in
958 for (i = 0; i < merges.nr; i++) {
959 struct commit *m1 = (struct commit *) merges.objects[i].item;
961 contains_another = 0;
962 for (j = 0; j < merges.nr; j++) {
963 struct commit *m2 = (struct commit *) merges.objects[j].item;
964 if (i != j && in_merge_bases(m2, m1)) {
965 contains_another = 1;
970 if (!contains_another)
971 add_object_array(merges.objects[i].item, NULL, result);
974 object_array_clear(&merges);
978 static int merge_submodule(struct merge_options *opt,
980 const struct object_id *o,
981 const struct object_id *a,
982 const struct object_id *b,
983 struct object_id *result)
985 struct commit *commit_o, *commit_a, *commit_b;
987 struct object_array merges;
988 struct strbuf sb = STRBUF_INIT;
991 int search = !opt->priv->call_depth;
993 /* store fallback answer in result in case we fail */
994 oidcpy(result, opt->priv->call_depth ? o : a);
996 /* we can not handle deletion conflicts */
1004 if (add_submodule_odb(path)) {
1005 path_msg(opt, path, 0,
1006 _("Failed to merge submodule %s (not checked out)"),
1011 if (!(commit_o = lookup_commit_reference(opt->repo, o)) ||
1012 !(commit_a = lookup_commit_reference(opt->repo, a)) ||
1013 !(commit_b = lookup_commit_reference(opt->repo, b))) {
1014 path_msg(opt, path, 0,
1015 _("Failed to merge submodule %s (commits not present)"),
1020 /* check whether both changes are forward */
1021 if (!in_merge_bases(commit_o, commit_a) ||
1022 !in_merge_bases(commit_o, commit_b)) {
1023 path_msg(opt, path, 0,
1024 _("Failed to merge submodule %s "
1025 "(commits don't follow merge-base)"),
1030 /* Case #1: a is contained in b or vice versa */
1031 if (in_merge_bases(commit_a, commit_b)) {
1033 path_msg(opt, path, 1,
1034 _("Note: Fast-forwarding submodule %s to %s"),
1035 path, oid_to_hex(b));
1038 if (in_merge_bases(commit_b, commit_a)) {
1040 path_msg(opt, path, 1,
1041 _("Note: Fast-forwarding submodule %s to %s"),
1042 path, oid_to_hex(a));
1047 * Case #2: There are one or more merges that contain a and b in
1048 * the submodule. If there is only one, then present it as a
1049 * suggestion to the user, but leave it marked unmerged so the
1050 * user needs to confirm the resolution.
1053 /* Skip the search if makes no sense to the calling context. */
1057 /* find commit which merges them */
1058 parent_count = find_first_merges(opt->repo, path, commit_a, commit_b,
1060 switch (parent_count) {
1062 path_msg(opt, path, 0, _("Failed to merge submodule %s"), path);
1066 format_commit(&sb, 4,
1067 (struct commit *)merges.objects[0].item);
1068 path_msg(opt, path, 0,
1069 _("Failed to merge submodule %s, but a possible merge "
1070 "resolution exists:\n%s\n"),
1072 path_msg(opt, path, 1,
1073 _("If this is correct simply add it to the index "
1076 " git update-index --cacheinfo 160000 %s \"%s\"\n\n"
1077 "which will accept this suggestion.\n"),
1078 oid_to_hex(&merges.objects[0].item->oid), path);
1079 strbuf_release(&sb);
1082 for (i = 0; i < merges.nr; i++)
1083 format_commit(&sb, 4,
1084 (struct commit *)merges.objects[i].item);
1085 path_msg(opt, path, 0,
1086 _("Failed to merge submodule %s, but multiple "
1087 "possible merges exist:\n%s"), path, sb.buf);
1088 strbuf_release(&sb);
1091 object_array_clear(&merges);
1095 static int merge_3way(struct merge_options *opt,
1097 const struct object_id *o,
1098 const struct object_id *a,
1099 const struct object_id *b,
1100 const char *pathnames[3],
1101 const int extra_marker_size,
1102 mmbuffer_t *result_buf)
1104 mmfile_t orig, src1, src2;
1105 struct ll_merge_options ll_opts = {0};
1106 char *base, *name1, *name2;
1109 ll_opts.renormalize = opt->renormalize;
1110 ll_opts.extra_marker_size = extra_marker_size;
1111 ll_opts.xdl_opts = opt->xdl_opts;
1113 if (opt->priv->call_depth) {
1114 ll_opts.virtual_ancestor = 1;
1115 ll_opts.variant = 0;
1117 switch (opt->recursive_variant) {
1118 case MERGE_VARIANT_OURS:
1119 ll_opts.variant = XDL_MERGE_FAVOR_OURS;
1121 case MERGE_VARIANT_THEIRS:
1122 ll_opts.variant = XDL_MERGE_FAVOR_THEIRS;
1125 ll_opts.variant = 0;
1130 assert(pathnames[0] && pathnames[1] && pathnames[2] && opt->ancestor);
1131 if (pathnames[0] == pathnames[1] && pathnames[1] == pathnames[2]) {
1132 base = mkpathdup("%s", opt->ancestor);
1133 name1 = mkpathdup("%s", opt->branch1);
1134 name2 = mkpathdup("%s", opt->branch2);
1136 base = mkpathdup("%s:%s", opt->ancestor, pathnames[0]);
1137 name1 = mkpathdup("%s:%s", opt->branch1, pathnames[1]);
1138 name2 = mkpathdup("%s:%s", opt->branch2, pathnames[2]);
1141 read_mmblob(&orig, o);
1142 read_mmblob(&src1, a);
1143 read_mmblob(&src2, b);
1145 merge_status = ll_merge(result_buf, path, &orig, base,
1146 &src1, name1, &src2, name2,
1147 opt->repo->index, &ll_opts);
1155 return merge_status;
1158 static int handle_content_merge(struct merge_options *opt,
1160 const struct version_info *o,
1161 const struct version_info *a,
1162 const struct version_info *b,
1163 const char *pathnames[3],
1164 const int extra_marker_size,
1165 struct version_info *result)
1168 * path is the target location where we want to put the file, and
1169 * is used to determine any normalization rules in ll_merge.
1171 * The normal case is that path and all entries in pathnames are
1172 * identical, though renames can affect which path we got one of
1173 * the three blobs to merge on various sides of history.
1175 * extra_marker_size is the amount to extend conflict markers in
1176 * ll_merge; this is neeed if we have content merges of content
1177 * merges, which happens for example with rename/rename(2to1) and
1178 * rename/add conflicts.
1183 * handle_content_merge() needs both files to be of the same type, i.e.
1184 * both files OR both submodules OR both symlinks. Conflicting types
1185 * needs to be handled elsewhere.
1187 assert((S_IFMT & a->mode) == (S_IFMT & b->mode));
1190 if (a->mode == b->mode || a->mode == o->mode)
1191 result->mode = b->mode;
1193 /* must be the 100644/100755 case */
1194 assert(S_ISREG(a->mode));
1195 result->mode = a->mode;
1196 clean = (b->mode == o->mode);
1198 * FIXME: If opt->priv->call_depth && !clean, then we really
1199 * should not make result->mode match either a->mode or
1200 * b->mode; that causes t6036 "check conflicting mode for
1201 * regular file" to fail. It would be best to use some other
1202 * mode, but we'll confuse all kinds of stuff if we use one
1203 * where S_ISREG(result->mode) isn't true, and if we use
1204 * something like 0100666, then tree-walk.c's calls to
1205 * canon_mode() will just normalize that to 100644 for us and
1206 * thus not solve anything.
1208 * Figure out if there's some kind of way we can work around
1214 * Trivial oid merge.
1216 * Note: While one might assume that the next four lines would
1217 * be unnecessary due to the fact that match_mask is often
1218 * setup and already handled, renames don't always take care
1221 if (oideq(&a->oid, &b->oid) || oideq(&a->oid, &o->oid))
1222 oidcpy(&result->oid, &b->oid);
1223 else if (oideq(&b->oid, &o->oid))
1224 oidcpy(&result->oid, &a->oid);
1226 /* Remaining rules depend on file vs. submodule vs. symlink. */
1227 else if (S_ISREG(a->mode)) {
1228 mmbuffer_t result_buf;
1229 int ret = 0, merge_status;
1233 * If 'o' is different type, treat it as null so we do a
1236 two_way = ((S_IFMT & o->mode) != (S_IFMT & a->mode));
1238 merge_status = merge_3way(opt, path,
1239 two_way ? &null_oid : &o->oid,
1241 pathnames, extra_marker_size,
1244 if ((merge_status < 0) || !result_buf.ptr)
1245 ret = err(opt, _("Failed to execute internal merge"));
1248 write_object_file(result_buf.ptr, result_buf.size,
1249 blob_type, &result->oid))
1250 ret = err(opt, _("Unable to add %s to database"),
1253 free(result_buf.ptr);
1256 clean &= (merge_status == 0);
1257 path_msg(opt, path, 1, _("Auto-merging %s"), path);
1258 } else if (S_ISGITLINK(a->mode)) {
1259 int two_way = ((S_IFMT & o->mode) != (S_IFMT & a->mode));
1260 clean = merge_submodule(opt, pathnames[0],
1261 two_way ? &null_oid : &o->oid,
1262 &a->oid, &b->oid, &result->oid);
1263 if (opt->priv->call_depth && two_way && !clean) {
1264 result->mode = o->mode;
1265 oidcpy(&result->oid, &o->oid);
1267 } else if (S_ISLNK(a->mode)) {
1268 if (opt->priv->call_depth) {
1270 result->mode = o->mode;
1271 oidcpy(&result->oid, &o->oid);
1273 switch (opt->recursive_variant) {
1274 case MERGE_VARIANT_NORMAL:
1276 oidcpy(&result->oid, &a->oid);
1278 case MERGE_VARIANT_OURS:
1279 oidcpy(&result->oid, &a->oid);
1281 case MERGE_VARIANT_THEIRS:
1282 oidcpy(&result->oid, &b->oid);
1287 BUG("unsupported object type in the tree: %06o for %s",
1293 /*** Function Grouping: functions related to detect_and_process_renames(), ***
1294 *** which are split into directory and regular rename detection sections. ***/
1296 /*** Function Grouping: functions related to directory rename detection ***/
1298 struct collision_info {
1299 struct string_list source_files;
1300 unsigned reported_already:1;
1304 * Return a new string that replaces the beginning portion (which matches
1305 * rename_info->key), with rename_info->util.new_dir. In perl-speak:
1306 * new_path_name = (old_path =~ s/rename_info->key/rename_info->value/);
1308 * Caller must ensure that old_path starts with rename_info->key + '/'.
1310 static char *apply_dir_rename(struct strmap_entry *rename_info,
1311 const char *old_path)
1313 struct strbuf new_path = STRBUF_INIT;
1314 const char *old_dir = rename_info->key;
1315 const char *new_dir = rename_info->value;
1316 int oldlen, newlen, new_dir_len;
1318 oldlen = strlen(old_dir);
1319 if (*new_dir == '\0')
1321 * If someone renamed/merged a subdirectory into the root
1322 * directory (e.g. 'some/subdir' -> ''), then we want to
1325 * as the rename; we need to make old_path + oldlen advance
1326 * past the '/' character.
1329 new_dir_len = strlen(new_dir);
1330 newlen = new_dir_len + (strlen(old_path) - oldlen) + 1;
1331 strbuf_grow(&new_path, newlen);
1332 strbuf_add(&new_path, new_dir, new_dir_len);
1333 strbuf_addstr(&new_path, &old_path[oldlen]);
1335 return strbuf_detach(&new_path, NULL);
1338 static int path_in_way(struct strmap *paths, const char *path, unsigned side_mask)
1340 struct merged_info *mi = strmap_get(paths, path);
1341 struct conflict_info *ci;
1344 INITIALIZE_CI(ci, mi);
1345 return mi->clean || (side_mask & (ci->filemask | ci->dirmask));
1349 * See if there is a directory rename for path, and if there are any file
1350 * level conflicts on the given side for the renamed location. If there is
1351 * a rename and there are no conflicts, return the new name. Otherwise,
1354 static char *handle_path_level_conflicts(struct merge_options *opt,
1356 unsigned side_index,
1357 struct strmap_entry *rename_info,
1358 struct strmap *collisions)
1360 char *new_path = NULL;
1361 struct collision_info *c_info;
1363 struct strbuf collision_paths = STRBUF_INIT;
1366 * entry has the mapping of old directory name to new directory name
1367 * that we want to apply to path.
1369 new_path = apply_dir_rename(rename_info, path);
1371 BUG("Failed to apply directory rename!");
1374 * The caller needs to have ensured that it has pre-populated
1375 * collisions with all paths that map to new_path. Do a quick check
1376 * to ensure that's the case.
1378 c_info = strmap_get(collisions, new_path);
1380 BUG("c_info is NULL");
1383 * Check for one-sided add/add/.../add conflicts, i.e.
1384 * where implicit renames from the other side doing
1385 * directory rename(s) can affect this side of history
1386 * to put multiple paths into the same location. Warn
1387 * and bail on directory renames for such paths.
1389 if (c_info->reported_already) {
1391 } else if (path_in_way(&opt->priv->paths, new_path, 1 << side_index)) {
1392 c_info->reported_already = 1;
1393 strbuf_add_separated_string_list(&collision_paths, ", ",
1394 &c_info->source_files);
1395 path_msg(opt, new_path, 0,
1396 _("CONFLICT (implicit dir rename): Existing file/dir "
1397 "at %s in the way of implicit directory rename(s) "
1398 "putting the following path(s) there: %s."),
1399 new_path, collision_paths.buf);
1401 } else if (c_info->source_files.nr > 1) {
1402 c_info->reported_already = 1;
1403 strbuf_add_separated_string_list(&collision_paths, ", ",
1404 &c_info->source_files);
1405 path_msg(opt, new_path, 0,
1406 _("CONFLICT (implicit dir rename): Cannot map more "
1407 "than one path to %s; implicit directory renames "
1408 "tried to put these paths there: %s"),
1409 new_path, collision_paths.buf);
1413 /* Free memory we no longer need */
1414 strbuf_release(&collision_paths);
1415 if (!clean && new_path) {
1423 static void get_provisional_directory_renames(struct merge_options *opt,
1427 struct hashmap_iter iter;
1428 struct strmap_entry *entry;
1429 struct rename_info *renames = &opt->priv->renames;
1433 * dir_rename_count: old_directory -> {new_directory -> count}
1435 * dir_renames: old_directory -> best_new_directory
1436 * where best_new_directory is the one with the unique highest count.
1438 strmap_for_each_entry(&renames->dir_rename_count[side], &iter, entry) {
1439 const char *source_dir = entry->key;
1440 struct strintmap *counts = entry->value;
1441 struct hashmap_iter count_iter;
1442 struct strmap_entry *count_entry;
1445 const char *best = NULL;
1447 strintmap_for_each_entry(counts, &count_iter, count_entry) {
1448 const char *target_dir = count_entry->key;
1449 intptr_t count = (intptr_t)count_entry->value;
1453 else if (count > max) {
1459 if (bad_max == max) {
1460 path_msg(opt, source_dir, 0,
1461 _("CONFLICT (directory rename split): "
1462 "Unclear where to rename %s to; it was "
1463 "renamed to multiple other directories, with "
1464 "no destination getting a majority of the "
1468 * We should mark this as unclean IF something attempts
1469 * to use this rename. We do not yet have the logic
1470 * in place to detect if this directory rename is being
1471 * used, and optimizations that reduce the number of
1472 * renames cause this to falsely trigger. For now,
1473 * just disable it, causing t6423 testcase 2a to break.
1474 * We'll later fix the detection, and when we do we
1475 * will re-enable setting *clean to 0 (and thereby fix
1476 * t6423 testcase 2a).
1480 strmap_put(&renames->dir_renames[side],
1481 source_dir, (void*)best);
1486 static void handle_directory_level_conflicts(struct merge_options *opt)
1488 struct hashmap_iter iter;
1489 struct strmap_entry *entry;
1490 struct string_list duplicated = STRING_LIST_INIT_NODUP;
1491 struct rename_info *renames = &opt->priv->renames;
1492 struct strmap *side1_dir_renames = &renames->dir_renames[MERGE_SIDE1];
1493 struct strmap *side2_dir_renames = &renames->dir_renames[MERGE_SIDE2];
1496 strmap_for_each_entry(side1_dir_renames, &iter, entry) {
1497 if (strmap_contains(side2_dir_renames, entry->key))
1498 string_list_append(&duplicated, entry->key);
1501 for (i = 0; i < duplicated.nr; i++) {
1502 strmap_remove(side1_dir_renames, duplicated.items[i].string, 0);
1503 strmap_remove(side2_dir_renames, duplicated.items[i].string, 0);
1505 string_list_clear(&duplicated, 0);
1508 static struct strmap_entry *check_dir_renamed(const char *path,
1509 struct strmap *dir_renames)
1511 char *temp = xstrdup(path);
1513 struct strmap_entry *e = NULL;
1515 while ((end = strrchr(temp, '/'))) {
1517 e = strmap_get_entry(dir_renames, temp);
1525 static void compute_collisions(struct strmap *collisions,
1526 struct strmap *dir_renames,
1527 struct diff_queue_struct *pairs)
1531 strmap_init_with_options(collisions, NULL, 0);
1532 if (strmap_empty(dir_renames))
1536 * Multiple files can be mapped to the same path due to directory
1537 * renames done by the other side of history. Since that other
1538 * side of history could have merged multiple directories into one,
1539 * if our side of history added the same file basename to each of
1540 * those directories, then all N of them would get implicitly
1541 * renamed by the directory rename detection into the same path,
1542 * and we'd get an add/add/.../add conflict, and all those adds
1543 * from *this* side of history. This is not representable in the
1544 * index, and users aren't going to easily be able to make sense of
1545 * it. So we need to provide a good warning about what's
1546 * happening, and fall back to no-directory-rename detection
1547 * behavior for those paths.
1549 * See testcases 9e and all of section 5 from t6043 for examples.
1551 for (i = 0; i < pairs->nr; ++i) {
1552 struct strmap_entry *rename_info;
1553 struct collision_info *collision_info;
1555 struct diff_filepair *pair = pairs->queue[i];
1557 if (pair->status != 'A' && pair->status != 'R')
1559 rename_info = check_dir_renamed(pair->two->path, dir_renames);
1563 new_path = apply_dir_rename(rename_info, pair->two->path);
1565 collision_info = strmap_get(collisions, new_path);
1566 if (collision_info) {
1569 collision_info = xcalloc(1,
1570 sizeof(struct collision_info));
1571 string_list_init(&collision_info->source_files, 0);
1572 strmap_put(collisions, new_path, collision_info);
1574 string_list_insert(&collision_info->source_files,
1579 static char *check_for_directory_rename(struct merge_options *opt,
1581 unsigned side_index,
1582 struct strmap *dir_renames,
1583 struct strmap *dir_rename_exclusions,
1584 struct strmap *collisions,
1587 char *new_path = NULL;
1588 struct strmap_entry *rename_info;
1589 struct strmap_entry *otherinfo = NULL;
1590 const char *new_dir;
1592 if (strmap_empty(dir_renames))
1594 rename_info = check_dir_renamed(path, dir_renames);
1597 /* old_dir = rename_info->key; */
1598 new_dir = rename_info->value;
1601 * This next part is a little weird. We do not want to do an
1602 * implicit rename into a directory we renamed on our side, because
1603 * that will result in a spurious rename/rename(1to2) conflict. An
1605 * Base commit: dumbdir/afile, otherdir/bfile
1606 * Side 1: smrtdir/afile, otherdir/bfile
1607 * Side 2: dumbdir/afile, dumbdir/bfile
1608 * Here, while working on Side 1, we could notice that otherdir was
1609 * renamed/merged to dumbdir, and change the diff_filepair for
1610 * otherdir/bfile into a rename into dumbdir/bfile. However, Side
1611 * 2 will notice the rename from dumbdir to smrtdir, and do the
1612 * transitive rename to move it from dumbdir/bfile to
1613 * smrtdir/bfile. That gives us bfile in dumbdir vs being in
1614 * smrtdir, a rename/rename(1to2) conflict. We really just want
1615 * the file to end up in smrtdir. And the way to achieve that is
1616 * to not let Side1 do the rename to dumbdir, since we know that is
1617 * the source of one of our directory renames.
1619 * That's why otherinfo and dir_rename_exclusions is here.
1621 * As it turns out, this also prevents N-way transient rename
1622 * confusion; See testcases 9c and 9d of t6043.
1624 otherinfo = strmap_get_entry(dir_rename_exclusions, new_dir);
1626 path_msg(opt, rename_info->key, 1,
1627 _("WARNING: Avoiding applying %s -> %s rename "
1628 "to %s, because %s itself was renamed."),
1629 rename_info->key, new_dir, path, new_dir);
1633 new_path = handle_path_level_conflicts(opt, path, side_index,
1634 rename_info, collisions);
1635 *clean_merge &= (new_path != NULL);
1640 static void apply_directory_rename_modifications(struct merge_options *opt,
1641 struct diff_filepair *pair,
1645 * The basic idea is to get the conflict_info from opt->priv->paths
1646 * at old path, and insert it into new_path; basically just this:
1647 * ci = strmap_get(&opt->priv->paths, old_path);
1648 * strmap_remove(&opt->priv->paths, old_path, 0);
1649 * strmap_put(&opt->priv->paths, new_path, ci);
1650 * However, there are some factors complicating this:
1651 * - opt->priv->paths may already have an entry at new_path
1652 * - Each ci tracks its containing directory, so we need to
1654 * - If another ci has the same containing directory, then
1655 * the two char*'s MUST point to the same location. See the
1656 * comment in struct merged_info. strcmp equality is not
1657 * enough; we need pointer equality.
1658 * - opt->priv->paths must hold the parent directories of any
1659 * entries that are added. So, if this directory rename
1660 * causes entirely new directories, we must recursively add
1661 * parent directories.
1662 * - For each parent directory added to opt->priv->paths, we
1663 * also need to get its parent directory stored in its
1664 * conflict_info->merged.directory_name with all the same
1665 * requirements about pointer equality.
1667 struct string_list dirs_to_insert = STRING_LIST_INIT_NODUP;
1668 struct conflict_info *ci, *new_ci;
1669 struct strmap_entry *entry;
1670 const char *branch_with_new_path, *branch_with_dir_rename;
1671 const char *old_path = pair->two->path;
1672 const char *parent_name;
1673 const char *cur_path;
1676 entry = strmap_get_entry(&opt->priv->paths, old_path);
1677 old_path = entry->key;
1681 /* Find parent directories missing from opt->priv->paths */
1682 cur_path = new_path;
1684 /* Find the parent directory of cur_path */
1685 char *last_slash = strrchr(cur_path, '/');
1687 parent_name = xstrndup(cur_path, last_slash - cur_path);
1689 parent_name = opt->priv->toplevel_dir;
1693 /* Look it up in opt->priv->paths */
1694 entry = strmap_get_entry(&opt->priv->paths, parent_name);
1696 free((char*)parent_name);
1697 parent_name = entry->key; /* reuse known pointer */
1701 /* Record this is one of the directories we need to insert */
1702 string_list_append(&dirs_to_insert, parent_name);
1703 cur_path = parent_name;
1706 /* Traverse dirs_to_insert and insert them into opt->priv->paths */
1707 for (i = dirs_to_insert.nr-1; i >= 0; --i) {
1708 struct conflict_info *dir_ci;
1709 char *cur_dir = dirs_to_insert.items[i].string;
1711 dir_ci = xcalloc(1, sizeof(*dir_ci));
1713 dir_ci->merged.directory_name = parent_name;
1714 len = strlen(parent_name);
1715 /* len+1 because of trailing '/' character */
1716 dir_ci->merged.basename_offset = (len > 0 ? len+1 : len);
1717 dir_ci->dirmask = ci->filemask;
1718 strmap_put(&opt->priv->paths, cur_dir, dir_ci);
1720 parent_name = cur_dir;
1724 * We are removing old_path from opt->priv->paths. old_path also will
1725 * eventually need to be freed, but it may still be used by e.g.
1726 * ci->pathnames. So, store it in another string-list for now.
1728 string_list_append(&opt->priv->paths_to_free, old_path);
1730 assert(ci->filemask == 2 || ci->filemask == 4);
1731 assert(ci->dirmask == 0);
1732 strmap_remove(&opt->priv->paths, old_path, 0);
1734 branch_with_new_path = (ci->filemask == 2) ? opt->branch1 : opt->branch2;
1735 branch_with_dir_rename = (ci->filemask == 2) ? opt->branch2 : opt->branch1;
1737 /* Now, finally update ci and stick it into opt->priv->paths */
1738 ci->merged.directory_name = parent_name;
1739 len = strlen(parent_name);
1740 ci->merged.basename_offset = (len > 0 ? len+1 : len);
1741 new_ci = strmap_get(&opt->priv->paths, new_path);
1743 /* Place ci back into opt->priv->paths, but at new_path */
1744 strmap_put(&opt->priv->paths, new_path, ci);
1748 /* A few sanity checks */
1750 assert(ci->filemask == 2 || ci->filemask == 4);
1751 assert((new_ci->filemask & ci->filemask) == 0);
1752 assert(!new_ci->merged.clean);
1754 /* Copy stuff from ci into new_ci */
1755 new_ci->filemask |= ci->filemask;
1756 if (new_ci->dirmask)
1757 new_ci->df_conflict = 1;
1758 index = (ci->filemask >> 1);
1759 new_ci->pathnames[index] = ci->pathnames[index];
1760 new_ci->stages[index].mode = ci->stages[index].mode;
1761 oidcpy(&new_ci->stages[index].oid, &ci->stages[index].oid);
1767 if (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE) {
1768 /* Notify user of updated path */
1769 if (pair->status == 'A')
1770 path_msg(opt, new_path, 1,
1771 _("Path updated: %s added in %s inside a "
1772 "directory that was renamed in %s; moving "
1774 old_path, branch_with_new_path,
1775 branch_with_dir_rename, new_path);
1777 path_msg(opt, new_path, 1,
1778 _("Path updated: %s renamed to %s in %s, "
1779 "inside a directory that was renamed in %s; "
1780 "moving it to %s."),
1781 pair->one->path, old_path, branch_with_new_path,
1782 branch_with_dir_rename, new_path);
1785 * opt->detect_directory_renames has the value
1786 * MERGE_DIRECTORY_RENAMES_CONFLICT, so mark these as conflicts.
1788 ci->path_conflict = 1;
1789 if (pair->status == 'A')
1790 path_msg(opt, new_path, 0,
1791 _("CONFLICT (file location): %s added in %s "
1792 "inside a directory that was renamed in %s, "
1793 "suggesting it should perhaps be moved to "
1795 old_path, branch_with_new_path,
1796 branch_with_dir_rename, new_path);
1798 path_msg(opt, new_path, 0,
1799 _("CONFLICT (file location): %s renamed to %s "
1800 "in %s, inside a directory that was renamed "
1801 "in %s, suggesting it should perhaps be "
1803 pair->one->path, old_path, branch_with_new_path,
1804 branch_with_dir_rename, new_path);
1808 * Finally, record the new location.
1810 pair->two->path = new_path;
1813 /*** Function Grouping: functions related to regular rename detection ***/
1815 static int process_renames(struct merge_options *opt,
1816 struct diff_queue_struct *renames)
1818 int clean_merge = 1, i;
1820 for (i = 0; i < renames->nr; ++i) {
1821 const char *oldpath = NULL, *newpath;
1822 struct diff_filepair *pair = renames->queue[i];
1823 struct conflict_info *oldinfo = NULL, *newinfo = NULL;
1824 struct strmap_entry *old_ent, *new_ent;
1825 unsigned int old_sidemask;
1826 int target_index, other_source_index;
1827 int source_deleted, collision, type_changed;
1828 const char *rename_branch = NULL, *delete_branch = NULL;
1830 old_ent = strmap_get_entry(&opt->priv->paths, pair->one->path);
1831 new_ent = strmap_get_entry(&opt->priv->paths, pair->two->path);
1833 oldpath = old_ent->key;
1834 oldinfo = old_ent->value;
1836 newpath = pair->two->path;
1838 newpath = new_ent->key;
1839 newinfo = new_ent->value;
1843 * If pair->one->path isn't in opt->priv->paths, that means
1844 * that either directory rename detection removed that
1845 * path, or a parent directory of oldpath was resolved and
1846 * we don't even need the rename; in either case, we can
1847 * skip it. If oldinfo->merged.clean, then the other side
1848 * of history had no changes to oldpath and we don't need
1849 * the rename and can skip it.
1851 if (!oldinfo || oldinfo->merged.clean)
1855 * diff_filepairs have copies of pathnames, thus we have to
1856 * use standard 'strcmp()' (negated) instead of '=='.
1858 if (i + 1 < renames->nr &&
1859 !strcmp(oldpath, renames->queue[i+1]->one->path)) {
1860 /* Handle rename/rename(1to2) or rename/rename(1to1) */
1861 const char *pathnames[3];
1862 struct version_info merged;
1863 struct conflict_info *base, *side1, *side2;
1864 unsigned was_binary_blob = 0;
1866 pathnames[0] = oldpath;
1867 pathnames[1] = newpath;
1868 pathnames[2] = renames->queue[i+1]->two->path;
1870 base = strmap_get(&opt->priv->paths, pathnames[0]);
1871 side1 = strmap_get(&opt->priv->paths, pathnames[1]);
1872 side2 = strmap_get(&opt->priv->paths, pathnames[2]);
1878 if (!strcmp(pathnames[1], pathnames[2])) {
1879 /* Both sides renamed the same way */
1880 assert(side1 == side2);
1881 memcpy(&side1->stages[0], &base->stages[0],
1883 side1->filemask |= (1 << MERGE_BASE);
1884 /* Mark base as resolved by removal */
1885 base->merged.is_null = 1;
1886 base->merged.clean = 1;
1888 /* We handled both renames, i.e. i+1 handled */
1890 /* Move to next rename */
1894 /* This is a rename/rename(1to2) */
1895 clean_merge = handle_content_merge(opt,
1901 1 + 2 * opt->priv->call_depth,
1904 merged.mode == side1->stages[1].mode &&
1905 oideq(&merged.oid, &side1->stages[1].oid))
1906 was_binary_blob = 1;
1907 memcpy(&side1->stages[1], &merged, sizeof(merged));
1908 if (was_binary_blob) {
1910 * Getting here means we were attempting to
1911 * merge a binary blob.
1913 * Since we can't merge binaries,
1914 * handle_content_merge() just takes one
1915 * side. But we don't want to copy the
1916 * contents of one side to both paths. We
1917 * used the contents of side1 above for
1918 * side1->stages, let's use the contents of
1919 * side2 for side2->stages below.
1921 oidcpy(&merged.oid, &side2->stages[2].oid);
1922 merged.mode = side2->stages[2].mode;
1924 memcpy(&side2->stages[2], &merged, sizeof(merged));
1926 side1->path_conflict = 1;
1927 side2->path_conflict = 1;
1929 * TODO: For renames we normally remove the path at the
1930 * old name. It would thus seem consistent to do the
1931 * same for rename/rename(1to2) cases, but we haven't
1932 * done so traditionally and a number of the regression
1933 * tests now encode an expectation that the file is
1934 * left there at stage 1. If we ever decide to change
1935 * this, add the following two lines here:
1936 * base->merged.is_null = 1;
1937 * base->merged.clean = 1;
1938 * and remove the setting of base->path_conflict to 1.
1940 base->path_conflict = 1;
1941 path_msg(opt, oldpath, 0,
1942 _("CONFLICT (rename/rename): %s renamed to "
1943 "%s in %s and to %s in %s."),
1945 pathnames[1], opt->branch1,
1946 pathnames[2], opt->branch2);
1948 i++; /* We handled both renames, i.e. i+1 handled */
1954 target_index = pair->score; /* from collect_renames() */
1955 assert(target_index == 1 || target_index == 2);
1956 other_source_index = 3 - target_index;
1957 old_sidemask = (1 << other_source_index); /* 2 or 4 */
1958 source_deleted = (oldinfo->filemask == 1);
1959 collision = ((newinfo->filemask & old_sidemask) != 0);
1960 type_changed = !source_deleted &&
1961 (S_ISREG(oldinfo->stages[other_source_index].mode) !=
1962 S_ISREG(newinfo->stages[target_index].mode));
1963 if (type_changed && collision) {
1965 * special handling so later blocks can handle this...
1967 * if type_changed && collision are both true, then this
1968 * was really a double rename, but one side wasn't
1969 * detected due to lack of break detection. I.e.
1971 * orig: has normal file 'foo'
1972 * side1: renames 'foo' to 'bar', adds 'foo' symlink
1973 * side2: renames 'foo' to 'bar'
1974 * In this case, the foo->bar rename on side1 won't be
1975 * detected because the new symlink named 'foo' is
1976 * there and we don't do break detection. But we detect
1977 * this here because we don't want to merge the content
1978 * of the foo symlink with the foo->bar file, so we
1979 * have some logic to handle this special case. The
1980 * easiest way to do that is make 'bar' on side1 not
1981 * be considered a colliding file but the other part
1982 * of a normal rename. If the file is very different,
1983 * well we're going to get content merge conflicts
1984 * anyway so it doesn't hurt. And if the colliding
1985 * file also has a different type, that'll be handled
1986 * by the content merge logic in process_entry() too.
1988 * See also t6430, 'rename vs. rename/symlink'
1992 if (source_deleted) {
1993 if (target_index == 1) {
1994 rename_branch = opt->branch1;
1995 delete_branch = opt->branch2;
1997 rename_branch = opt->branch2;
1998 delete_branch = opt->branch1;
2002 assert(source_deleted || oldinfo->filemask & old_sidemask);
2004 /* Need to check for special types of rename conflicts... */
2005 if (collision && !source_deleted) {
2006 /* collision: rename/add or rename/rename(2to1) */
2007 const char *pathnames[3];
2008 struct version_info merged;
2010 struct conflict_info *base, *side1, *side2;
2013 pathnames[0] = oldpath;
2014 pathnames[other_source_index] = oldpath;
2015 pathnames[target_index] = newpath;
2017 base = strmap_get(&opt->priv->paths, pathnames[0]);
2018 side1 = strmap_get(&opt->priv->paths, pathnames[1]);
2019 side2 = strmap_get(&opt->priv->paths, pathnames[2]);
2025 clean = handle_content_merge(opt, pair->one->path,
2030 1 + 2 * opt->priv->call_depth,
2033 memcpy(&newinfo->stages[target_index], &merged,
2036 path_msg(opt, newpath, 0,
2037 _("CONFLICT (rename involved in "
2038 "collision): rename of %s -> %s has "
2039 "content conflicts AND collides "
2040 "with another path; this may result "
2041 "in nested conflict markers."),
2044 } else if (collision && source_deleted) {
2046 * rename/add/delete or rename/rename(2to1)/delete:
2047 * since oldpath was deleted on the side that didn't
2048 * do the rename, there's not much of a content merge
2049 * we can do for the rename. oldinfo->merged.is_null
2050 * was already set, so we just leave things as-is so
2051 * they look like an add/add conflict.
2054 newinfo->path_conflict = 1;
2055 path_msg(opt, newpath, 0,
2056 _("CONFLICT (rename/delete): %s renamed "
2057 "to %s in %s, but deleted in %s."),
2058 oldpath, newpath, rename_branch, delete_branch);
2061 * a few different cases...start by copying the
2062 * existing stage(s) from oldinfo over the newinfo
2063 * and update the pathname(s).
2065 memcpy(&newinfo->stages[0], &oldinfo->stages[0],
2066 sizeof(newinfo->stages[0]));
2067 newinfo->filemask |= (1 << MERGE_BASE);
2068 newinfo->pathnames[0] = oldpath;
2070 /* rename vs. typechange */
2071 /* Mark the original as resolved by removal */
2072 memcpy(&oldinfo->stages[0].oid, &null_oid,
2073 sizeof(oldinfo->stages[0].oid));
2074 oldinfo->stages[0].mode = 0;
2075 oldinfo->filemask &= 0x06;
2076 } else if (source_deleted) {
2078 newinfo->path_conflict = 1;
2079 path_msg(opt, newpath, 0,
2080 _("CONFLICT (rename/delete): %s renamed"
2081 " to %s in %s, but deleted in %s."),
2083 rename_branch, delete_branch);
2086 memcpy(&newinfo->stages[other_source_index],
2087 &oldinfo->stages[other_source_index],
2088 sizeof(newinfo->stages[0]));
2089 newinfo->filemask |= (1 << other_source_index);
2090 newinfo->pathnames[other_source_index] = oldpath;
2094 if (!type_changed) {
2095 /* Mark the original as resolved by removal */
2096 oldinfo->merged.is_null = 1;
2097 oldinfo->merged.clean = 1;
2105 static void resolve_diffpair_statuses(struct diff_queue_struct *q)
2108 * A simplified version of diff_resolve_rename_copy(); would probably
2109 * just use that function but it's static...
2112 struct diff_filepair *p;
2114 for (i = 0; i < q->nr; ++i) {
2116 p->status = 0; /* undecided */
2117 if (!DIFF_FILE_VALID(p->one))
2118 p->status = DIFF_STATUS_ADDED;
2119 else if (!DIFF_FILE_VALID(p->two))
2120 p->status = DIFF_STATUS_DELETED;
2121 else if (DIFF_PAIR_RENAME(p))
2122 p->status = DIFF_STATUS_RENAMED;
2126 static int compare_pairs(const void *a_, const void *b_)
2128 const struct diff_filepair *a = *((const struct diff_filepair **)a_);
2129 const struct diff_filepair *b = *((const struct diff_filepair **)b_);
2131 return strcmp(a->one->path, b->one->path);
2134 /* Call diffcore_rename() to compute which files have changed on given side */
2135 static void detect_regular_renames(struct merge_options *opt,
2136 unsigned side_index)
2138 struct diff_options diff_opts;
2139 struct rename_info *renames = &opt->priv->renames;
2141 repo_diff_setup(opt->repo, &diff_opts);
2142 diff_opts.flags.recursive = 1;
2143 diff_opts.flags.rename_empty = 0;
2144 diff_opts.detect_rename = DIFF_DETECT_RENAME;
2145 diff_opts.rename_limit = opt->rename_limit;
2146 if (opt->rename_limit <= 0)
2147 diff_opts.rename_limit = 1000;
2148 diff_opts.rename_score = opt->rename_score;
2149 diff_opts.show_rename_progress = opt->show_rename_progress;
2150 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
2151 diff_setup_done(&diff_opts);
2153 diff_queued_diff = renames->pairs[side_index];
2154 trace2_region_enter("diff", "diffcore_rename", opt->repo);
2155 diffcore_rename_extended(&diff_opts,
2157 &renames->dirs_removed[side_index],
2158 &renames->dir_rename_count[side_index]);
2159 trace2_region_leave("diff", "diffcore_rename", opt->repo);
2160 resolve_diffpair_statuses(&diff_queued_diff);
2162 if (diff_opts.needed_rename_limit > renames->needed_limit)
2163 renames->needed_limit = diff_opts.needed_rename_limit;
2165 renames->pairs[side_index] = diff_queued_diff;
2167 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
2168 diff_queued_diff.nr = 0;
2169 diff_queued_diff.queue = NULL;
2170 diff_flush(&diff_opts);
2174 * Get information of all renames which occurred in 'side_pairs', discarding
2177 static int collect_renames(struct merge_options *opt,
2178 struct diff_queue_struct *result,
2179 unsigned side_index,
2180 struct strmap *dir_renames_for_side,
2181 struct strmap *rename_exclusions)
2184 struct strmap collisions;
2185 struct diff_queue_struct *side_pairs;
2186 struct hashmap_iter iter;
2187 struct strmap_entry *entry;
2188 struct rename_info *renames = &opt->priv->renames;
2190 side_pairs = &renames->pairs[side_index];
2191 compute_collisions(&collisions, dir_renames_for_side, side_pairs);
2193 for (i = 0; i < side_pairs->nr; ++i) {
2194 struct diff_filepair *p = side_pairs->queue[i];
2195 char *new_path; /* non-NULL only with directory renames */
2197 if (p->status != 'A' && p->status != 'R') {
2198 diff_free_filepair(p);
2202 new_path = check_for_directory_rename(opt, p->two->path,
2204 dir_renames_for_side,
2209 if (p->status != 'R' && !new_path) {
2210 diff_free_filepair(p);
2215 apply_directory_rename_modifications(opt, p, new_path);
2218 * p->score comes back from diffcore_rename_extended() with
2219 * the similarity of the renamed file. The similarity is
2220 * was used to determine that the two files were related
2221 * and are a rename, which we have already used, but beyond
2222 * that we have no use for the similarity. So p->score is
2223 * now irrelevant. However, process_renames() will need to
2224 * know which side of the merge this rename was associated
2225 * with, so overwrite p->score with that value.
2227 p->score = side_index;
2228 result->queue[result->nr++] = p;
2231 /* Free each value in the collisions map */
2232 strmap_for_each_entry(&collisions, &iter, entry) {
2233 struct collision_info *info = entry->value;
2234 string_list_clear(&info->source_files, 0);
2237 * In compute_collisions(), we set collisions.strdup_strings to 0
2238 * so that we wouldn't have to make another copy of the new_path
2239 * allocated by apply_dir_rename(). But now that we've used them
2240 * and have no other references to these strings, it is time to
2243 free_strmap_strings(&collisions);
2244 strmap_clear(&collisions, 1);
2248 static int detect_and_process_renames(struct merge_options *opt,
2249 struct tree *merge_base,
2253 struct diff_queue_struct combined;
2254 struct rename_info *renames = &opt->priv->renames;
2255 int need_dir_renames, s, clean = 1;
2257 memset(&combined, 0, sizeof(combined));
2259 trace2_region_enter("merge", "regular renames", opt->repo);
2260 detect_regular_renames(opt, MERGE_SIDE1);
2261 detect_regular_renames(opt, MERGE_SIDE2);
2262 trace2_region_leave("merge", "regular renames", opt->repo);
2264 trace2_region_enter("merge", "directory renames", opt->repo);
2266 !opt->priv->call_depth &&
2267 (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE ||
2268 opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_CONFLICT);
2270 if (need_dir_renames) {
2271 get_provisional_directory_renames(opt, MERGE_SIDE1, &clean);
2272 get_provisional_directory_renames(opt, MERGE_SIDE2, &clean);
2273 handle_directory_level_conflicts(opt);
2276 ALLOC_GROW(combined.queue,
2277 renames->pairs[1].nr + renames->pairs[2].nr,
2279 clean &= collect_renames(opt, &combined, MERGE_SIDE1,
2280 &renames->dir_renames[2],
2281 &renames->dir_renames[1]);
2282 clean &= collect_renames(opt, &combined, MERGE_SIDE2,
2283 &renames->dir_renames[1],
2284 &renames->dir_renames[2]);
2285 QSORT(combined.queue, combined.nr, compare_pairs);
2286 trace2_region_leave("merge", "directory renames", opt->repo);
2288 trace2_region_enter("merge", "process renames", opt->repo);
2289 clean &= process_renames(opt, &combined);
2290 trace2_region_leave("merge", "process renames", opt->repo);
2292 /* Free memory for renames->pairs[] and combined */
2293 for (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {
2294 free(renames->pairs[s].queue);
2295 DIFF_QUEUE_CLEAR(&renames->pairs[s]);
2299 for (i = 0; i < combined.nr; i++)
2300 diff_free_filepair(combined.queue[i]);
2301 free(combined.queue);
2307 /*** Function Grouping: functions related to process_entries() ***/
2309 static int string_list_df_name_compare(const char *one, const char *two)
2311 int onelen = strlen(one);
2312 int twolen = strlen(two);
2314 * Here we only care that entries for D/F conflicts are
2315 * adjacent, in particular with the file of the D/F conflict
2316 * appearing before files below the corresponding directory.
2317 * The order of the rest of the list is irrelevant for us.
2319 * To achieve this, we sort with df_name_compare and provide
2320 * the mode S_IFDIR so that D/F conflicts will sort correctly.
2321 * We use the mode S_IFDIR for everything else for simplicity,
2322 * since in other cases any changes in their order due to
2323 * sorting cause no problems for us.
2325 int cmp = df_name_compare(one, onelen, S_IFDIR,
2326 two, twolen, S_IFDIR);
2328 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
2329 * that 'foo' comes before 'foo/bar'.
2333 return onelen - twolen;
2336 struct directory_versions {
2338 * versions: list of (basename -> version_info)
2340 * The basenames are in reverse lexicographic order of full pathnames,
2341 * as processed in process_entries(). This puts all entries within
2342 * a directory together, and covers the directory itself after
2343 * everything within it, allowing us to write subtrees before needing
2344 * to record information for the tree itself.
2346 struct string_list versions;
2349 * offsets: list of (full relative path directories -> integer offsets)
2351 * Since versions contains basenames from files in multiple different
2352 * directories, we need to know which entries in versions correspond
2353 * to which directories. Values of e.g.
2357 * Would mean that entries 0-1 of versions are files in the toplevel
2358 * directory, entries 2-4 are files under src/, and the remaining
2359 * entries starting at index 5 are files under src/moduleA/.
2361 struct string_list offsets;
2364 * last_directory: directory that previously processed file found in
2366 * last_directory starts NULL, but records the directory in which the
2367 * previous file was found within. As soon as
2368 * directory(current_file) != last_directory
2369 * then we need to start updating accounting in versions & offsets.
2370 * Note that last_directory is always the last path in "offsets" (or
2371 * NULL if "offsets" is empty) so this exists just for quick access.
2373 const char *last_directory;
2375 /* last_directory_len: cached computation of strlen(last_directory) */
2376 unsigned last_directory_len;
2379 static int tree_entry_order(const void *a_, const void *b_)
2381 const struct string_list_item *a = a_;
2382 const struct string_list_item *b = b_;
2384 const struct merged_info *ami = a->util;
2385 const struct merged_info *bmi = b->util;
2386 return base_name_compare(a->string, strlen(a->string), ami->result.mode,
2387 b->string, strlen(b->string), bmi->result.mode);
2390 static void write_tree(struct object_id *result_oid,
2391 struct string_list *versions,
2392 unsigned int offset,
2395 size_t maxlen = 0, extra;
2396 unsigned int nr = versions->nr - offset;
2397 struct strbuf buf = STRBUF_INIT;
2398 struct string_list relevant_entries = STRING_LIST_INIT_NODUP;
2402 * We want to sort the last (versions->nr-offset) entries in versions.
2403 * Do so by abusing the string_list API a bit: make another string_list
2404 * that contains just those entries and then sort them.
2406 * We won't use relevant_entries again and will let it just pop off the
2407 * stack, so there won't be allocation worries or anything.
2409 relevant_entries.items = versions->items + offset;
2410 relevant_entries.nr = versions->nr - offset;
2411 QSORT(relevant_entries.items, relevant_entries.nr, tree_entry_order);
2413 /* Pre-allocate some space in buf */
2414 extra = hash_size + 8; /* 8: 6 for mode, 1 for space, 1 for NUL char */
2415 for (i = 0; i < nr; i++) {
2416 maxlen += strlen(versions->items[offset+i].string) + extra;
2418 strbuf_grow(&buf, maxlen);
2420 /* Write each entry out to buf */
2421 for (i = 0; i < nr; i++) {
2422 struct merged_info *mi = versions->items[offset+i].util;
2423 struct version_info *ri = &mi->result;
2424 strbuf_addf(&buf, "%o %s%c",
2426 versions->items[offset+i].string, '\0');
2427 strbuf_add(&buf, ri->oid.hash, hash_size);
2430 /* Write this object file out, and record in result_oid */
2431 write_object_file(buf.buf, buf.len, tree_type, result_oid);
2432 strbuf_release(&buf);
2435 static void record_entry_for_tree(struct directory_versions *dir_metadata,
2437 struct merged_info *mi)
2439 const char *basename;
2442 /* nothing to record */
2445 basename = path + mi->basename_offset;
2446 assert(strchr(basename, '/') == NULL);
2447 string_list_append(&dir_metadata->versions,
2448 basename)->util = &mi->result;
2451 static void write_completed_directory(struct merge_options *opt,
2452 const char *new_directory_name,
2453 struct directory_versions *info)
2455 const char *prev_dir;
2456 struct merged_info *dir_info = NULL;
2457 unsigned int offset;
2460 * Some explanation of info->versions and info->offsets...
2462 * process_entries() iterates over all relevant files AND
2463 * directories in reverse lexicographic order, and calls this
2464 * function. Thus, an example of the paths that process_entries()
2465 * could operate on (along with the directories for those paths
2470 * src/moduleB/umm.c src/moduleB
2471 * src/moduleB/stuff.h src/moduleB
2472 * src/moduleB/baz.c src/moduleB
2474 * src/moduleA/foo.c src/moduleA
2475 * src/moduleA/bar.c src/moduleA
2482 * always contains the unprocessed entries and their
2483 * version_info information. For example, after the first five
2484 * entries above, info->versions would be:
2486 * xtract.c <xtract.c's version_info>
2487 * token.txt <token.txt's version_info>
2488 * umm.c <src/moduleB/umm.c's version_info>
2489 * stuff.h <src/moduleB/stuff.h's version_info>
2490 * baz.c <src/moduleB/baz.c's version_info>
2492 * Once a subdirectory is completed we remove the entries in
2493 * that subdirectory from info->versions, writing it as a tree
2494 * (write_tree()). Thus, as soon as we get to src/moduleB,
2495 * info->versions would be updated to
2497 * xtract.c <xtract.c's version_info>
2498 * token.txt <token.txt's version_info>
2499 * moduleB <src/moduleB's version_info>
2503 * helps us track which entries in info->versions correspond to
2504 * which directories. When we are N directories deep (e.g. 4
2505 * for src/modA/submod/subdir/), we have up to N+1 unprocessed
2506 * directories (+1 because of toplevel dir). Corresponding to
2507 * the info->versions example above, after processing five entries
2508 * info->offsets will be:
2513 * which is used to know that xtract.c & token.txt are from the
2514 * toplevel dirctory, while umm.c & stuff.h & baz.c are from the
2515 * src/moduleB directory. Again, following the example above,
2516 * once we need to process src/moduleB, then info->offsets is
2522 * which says that moduleB (and only moduleB so far) is in the
2525 * One unique thing to note about info->offsets here is that
2526 * "src" was not added to info->offsets until there was a path
2527 * (a file OR directory) immediately below src/ that got
2530 * Since process_entry() just appends new entries to info->versions,
2531 * write_completed_directory() only needs to do work if the next path
2532 * is in a directory that is different than the last directory found
2537 * If we are working with the same directory as the last entry, there
2538 * is no work to do. (See comments above the directory_name member of
2539 * struct merged_info for why we can use pointer comparison instead of
2542 if (new_directory_name == info->last_directory)
2546 * If we are just starting (last_directory is NULL), or last_directory
2547 * is a prefix of the current directory, then we can just update
2548 * info->offsets to record the offset where we started this directory
2549 * and update last_directory to have quick access to it.
2551 if (info->last_directory == NULL ||
2552 !strncmp(new_directory_name, info->last_directory,
2553 info->last_directory_len)) {
2554 uintptr_t offset = info->versions.nr;
2556 info->last_directory = new_directory_name;
2557 info->last_directory_len = strlen(info->last_directory);
2559 * Record the offset into info->versions where we will
2560 * start recording basenames of paths found within
2561 * new_directory_name.
2563 string_list_append(&info->offsets,
2564 info->last_directory)->util = (void*)offset;
2569 * The next entry that will be processed will be within
2570 * new_directory_name. Since at this point we know that
2571 * new_directory_name is within a different directory than
2572 * info->last_directory, we have all entries for info->last_directory
2573 * in info->versions and we need to create a tree object for them.
2575 dir_info = strmap_get(&opt->priv->paths, info->last_directory);
2577 offset = (uintptr_t)info->offsets.items[info->offsets.nr-1].util;
2578 if (offset == info->versions.nr) {
2580 * Actually, we don't need to create a tree object in this
2581 * case. Whenever all files within a directory disappear
2582 * during the merge (e.g. unmodified on one side and
2583 * deleted on the other, or files were renamed elsewhere),
2584 * then we get here and the directory itself needs to be
2585 * omitted from its parent tree as well.
2587 dir_info->is_null = 1;
2590 * Write out the tree to the git object directory, and also
2591 * record the mode and oid in dir_info->result.
2593 dir_info->is_null = 0;
2594 dir_info->result.mode = S_IFDIR;
2595 write_tree(&dir_info->result.oid, &info->versions, offset,
2596 opt->repo->hash_algo->rawsz);
2600 * We've now used several entries from info->versions and one entry
2601 * from info->offsets, so we get rid of those values.
2604 info->versions.nr = offset;
2607 * Now we've taken care of the completed directory, but we need to
2608 * prepare things since future entries will be in
2609 * new_directory_name. (In particular, process_entry() will be
2610 * appending new entries to info->versions.) So, we need to make
2611 * sure new_directory_name is the last entry in info->offsets.
2613 prev_dir = info->offsets.nr == 0 ? NULL :
2614 info->offsets.items[info->offsets.nr-1].string;
2615 if (new_directory_name != prev_dir) {
2616 uintptr_t c = info->versions.nr;
2617 string_list_append(&info->offsets,
2618 new_directory_name)->util = (void*)c;
2621 /* And, of course, we need to update last_directory to match. */
2622 info->last_directory = new_directory_name;
2623 info->last_directory_len = strlen(info->last_directory);
2626 /* Per entry merge function */
2627 static void process_entry(struct merge_options *opt,
2629 struct conflict_info *ci,
2630 struct directory_versions *dir_metadata)
2632 int df_file_index = 0;
2635 assert(ci->filemask >= 0 && ci->filemask <= 7);
2636 /* ci->match_mask == 7 was handled in collect_merge_info_callback() */
2637 assert(ci->match_mask == 0 || ci->match_mask == 3 ||
2638 ci->match_mask == 5 || ci->match_mask == 6);
2641 record_entry_for_tree(dir_metadata, path, &ci->merged);
2642 if (ci->filemask == 0)
2643 /* nothing else to handle */
2645 assert(ci->df_conflict);
2648 if (ci->df_conflict && ci->merged.result.mode == 0) {
2652 * directory no longer in the way, but we do have a file we
2653 * need to place here so we need to clean away the "directory
2654 * merges to nothing" result.
2656 ci->df_conflict = 0;
2657 assert(ci->filemask != 0);
2658 ci->merged.clean = 0;
2659 ci->merged.is_null = 0;
2660 /* and we want to zero out any directory-related entries */
2661 ci->match_mask = (ci->match_mask & ~ci->dirmask);
2663 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
2664 if (ci->filemask & (1 << i))
2666 ci->stages[i].mode = 0;
2667 oidcpy(&ci->stages[i].oid, &null_oid);
2669 } else if (ci->df_conflict && ci->merged.result.mode != 0) {
2671 * This started out as a D/F conflict, and the entries in
2672 * the competing directory were not removed by the merge as
2673 * evidenced by write_completed_directory() writing a value
2674 * to ci->merged.result.mode.
2676 struct conflict_info *new_ci;
2678 const char *old_path = path;
2681 assert(ci->merged.result.mode == S_IFDIR);
2684 * If filemask is 1, we can just ignore the file as having
2685 * been deleted on both sides. We do not want to overwrite
2686 * ci->merged.result, since it stores the tree for all the
2689 if (ci->filemask == 1) {
2695 * This file still exists on at least one side, and we want
2696 * the directory to remain here, so we need to move this
2697 * path to some new location.
2699 new_ci = xcalloc(1, sizeof(*new_ci));
2700 /* We don't really want new_ci->merged.result copied, but it'll
2701 * be overwritten below so it doesn't matter. We also don't
2702 * want any directory mode/oid values copied, but we'll zero
2703 * those out immediately. We do want the rest of ci copied.
2705 memcpy(new_ci, ci, sizeof(*ci));
2706 new_ci->match_mask = (new_ci->match_mask & ~new_ci->dirmask);
2707 new_ci->dirmask = 0;
2708 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
2709 if (new_ci->filemask & (1 << i))
2711 /* zero out any entries related to directories */
2712 new_ci->stages[i].mode = 0;
2713 oidcpy(&new_ci->stages[i].oid, &null_oid);
2717 * Find out which side this file came from; note that we
2718 * cannot just use ci->filemask, because renames could cause
2719 * the filemask to go back to 7. So we use dirmask, then
2720 * pick the opposite side's index.
2722 df_file_index = (ci->dirmask & (1 << 1)) ? 2 : 1;
2723 branch = (df_file_index == 1) ? opt->branch1 : opt->branch2;
2724 path = unique_path(&opt->priv->paths, path, branch);
2725 strmap_put(&opt->priv->paths, path, new_ci);
2727 path_msg(opt, path, 0,
2728 _("CONFLICT (file/directory): directory in the way "
2729 "of %s from %s; moving it to %s instead."),
2730 old_path, branch, path);
2733 * Zero out the filemask for the old ci. At this point, ci
2734 * was just an entry for a directory, so we don't need to
2735 * do anything more with it.
2740 * Now note that we're working on the new entry (path was
2747 * NOTE: Below there is a long switch-like if-elseif-elseif... block
2748 * which the code goes through even for the df_conflict cases
2751 if (ci->match_mask) {
2752 ci->merged.clean = 1;
2753 if (ci->match_mask == 6) {
2754 /* stages[1] == stages[2] */
2755 ci->merged.result.mode = ci->stages[1].mode;
2756 oidcpy(&ci->merged.result.oid, &ci->stages[1].oid);
2758 /* determine the mask of the side that didn't match */
2759 unsigned int othermask = 7 & ~ci->match_mask;
2760 int side = (othermask == 4) ? 2 : 1;
2762 ci->merged.result.mode = ci->stages[side].mode;
2763 ci->merged.is_null = !ci->merged.result.mode;
2764 oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
2766 assert(othermask == 2 || othermask == 4);
2767 assert(ci->merged.is_null ==
2768 (ci->filemask == ci->match_mask));
2770 } else if (ci->filemask >= 6 &&
2771 (S_IFMT & ci->stages[1].mode) !=
2772 (S_IFMT & ci->stages[2].mode)) {
2773 /* Two different items from (file/submodule/symlink) */
2774 if (opt->priv->call_depth) {
2775 /* Just use the version from the merge base */
2776 ci->merged.clean = 0;
2777 oidcpy(&ci->merged.result.oid, &ci->stages[0].oid);
2778 ci->merged.result.mode = ci->stages[0].mode;
2779 ci->merged.is_null = (ci->merged.result.mode == 0);
2781 /* Handle by renaming one or both to separate paths. */
2782 unsigned o_mode = ci->stages[0].mode;
2783 unsigned a_mode = ci->stages[1].mode;
2784 unsigned b_mode = ci->stages[2].mode;
2785 struct conflict_info *new_ci;
2786 const char *a_path = NULL, *b_path = NULL;
2787 int rename_a = 0, rename_b = 0;
2789 new_ci = xmalloc(sizeof(*new_ci));
2791 if (S_ISREG(a_mode))
2793 else if (S_ISREG(b_mode))
2800 path_msg(opt, path, 0,
2801 _("CONFLICT (distinct types): %s had different "
2802 "types on each side; renamed %s of them so "
2803 "each can be recorded somewhere."),
2805 (rename_a && rename_b) ? _("both") : _("one"));
2807 ci->merged.clean = 0;
2808 memcpy(new_ci, ci, sizeof(*new_ci));
2810 /* Put b into new_ci, removing a from stages */
2811 new_ci->merged.result.mode = ci->stages[2].mode;
2812 oidcpy(&new_ci->merged.result.oid, &ci->stages[2].oid);
2813 new_ci->stages[1].mode = 0;
2814 oidcpy(&new_ci->stages[1].oid, &null_oid);
2815 new_ci->filemask = 5;
2816 if ((S_IFMT & b_mode) != (S_IFMT & o_mode)) {
2817 new_ci->stages[0].mode = 0;
2818 oidcpy(&new_ci->stages[0].oid, &null_oid);
2819 new_ci->filemask = 4;
2822 /* Leave only a in ci, fixing stages. */
2823 ci->merged.result.mode = ci->stages[1].mode;
2824 oidcpy(&ci->merged.result.oid, &ci->stages[1].oid);
2825 ci->stages[2].mode = 0;
2826 oidcpy(&ci->stages[2].oid, &null_oid);
2828 if ((S_IFMT & a_mode) != (S_IFMT & o_mode)) {
2829 ci->stages[0].mode = 0;
2830 oidcpy(&ci->stages[0].oid, &null_oid);
2834 /* Insert entries into opt->priv_paths */
2835 assert(rename_a || rename_b);
2837 a_path = unique_path(&opt->priv->paths,
2838 path, opt->branch1);
2839 strmap_put(&opt->priv->paths, a_path, ci);
2843 b_path = unique_path(&opt->priv->paths,
2844 path, opt->branch2);
2847 strmap_put(&opt->priv->paths, b_path, new_ci);
2849 if (rename_a && rename_b) {
2850 strmap_remove(&opt->priv->paths, path, 0);
2852 * We removed path from opt->priv->paths. path
2853 * will also eventually need to be freed, but
2854 * it may still be used by e.g. ci->pathnames.
2855 * So, store it in another string-list for now.
2857 string_list_append(&opt->priv->paths_to_free,
2862 * Do special handling for b_path since process_entry()
2863 * won't be called on it specially.
2865 strmap_put(&opt->priv->conflicted, b_path, new_ci);
2866 record_entry_for_tree(dir_metadata, b_path,
2870 * Remaining code for processing this entry should
2871 * think in terms of processing a_path.
2876 } else if (ci->filemask >= 6) {
2877 /* Need a two-way or three-way content merge */
2878 struct version_info merged_file;
2879 unsigned clean_merge;
2880 struct version_info *o = &ci->stages[0];
2881 struct version_info *a = &ci->stages[1];
2882 struct version_info *b = &ci->stages[2];
2884 clean_merge = handle_content_merge(opt, path, o, a, b,
2886 opt->priv->call_depth * 2,
2888 ci->merged.clean = clean_merge &&
2889 !ci->df_conflict && !ci->path_conflict;
2890 ci->merged.result.mode = merged_file.mode;
2891 ci->merged.is_null = (merged_file.mode == 0);
2892 oidcpy(&ci->merged.result.oid, &merged_file.oid);
2893 if (clean_merge && ci->df_conflict) {
2894 assert(df_file_index == 1 || df_file_index == 2);
2895 ci->filemask = 1 << df_file_index;
2896 ci->stages[df_file_index].mode = merged_file.mode;
2897 oidcpy(&ci->stages[df_file_index].oid, &merged_file.oid);
2900 const char *reason = _("content");
2901 if (ci->filemask == 6)
2902 reason = _("add/add");
2903 if (S_ISGITLINK(merged_file.mode))
2904 reason = _("submodule");
2905 path_msg(opt, path, 0,
2906 _("CONFLICT (%s): Merge conflict in %s"),
2909 } else if (ci->filemask == 3 || ci->filemask == 5) {
2911 const char *modify_branch, *delete_branch;
2912 int side = (ci->filemask == 5) ? 2 : 1;
2913 int index = opt->priv->call_depth ? 0 : side;
2915 ci->merged.result.mode = ci->stages[index].mode;
2916 oidcpy(&ci->merged.result.oid, &ci->stages[index].oid);
2917 ci->merged.clean = 0;
2919 modify_branch = (side == 1) ? opt->branch1 : opt->branch2;
2920 delete_branch = (side == 1) ? opt->branch2 : opt->branch1;
2922 if (ci->path_conflict &&
2923 oideq(&ci->stages[0].oid, &ci->stages[side].oid)) {
2925 * This came from a rename/delete; no action to take,
2926 * but avoid printing "modify/delete" conflict notice
2927 * since the contents were not modified.
2930 path_msg(opt, path, 0,
2931 _("CONFLICT (modify/delete): %s deleted in %s "
2932 "and modified in %s. Version %s of %s left "
2934 path, delete_branch, modify_branch,
2935 modify_branch, path);
2937 } else if (ci->filemask == 2 || ci->filemask == 4) {
2938 /* Added on one side */
2939 int side = (ci->filemask == 4) ? 2 : 1;
2940 ci->merged.result.mode = ci->stages[side].mode;
2941 oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
2942 ci->merged.clean = !ci->df_conflict && !ci->path_conflict;
2943 } else if (ci->filemask == 1) {
2944 /* Deleted on both sides */
2945 ci->merged.is_null = 1;
2946 ci->merged.result.mode = 0;
2947 oidcpy(&ci->merged.result.oid, &null_oid);
2948 ci->merged.clean = !ci->path_conflict;
2952 * If still conflicted, record it separately. This allows us to later
2953 * iterate over just conflicted entries when updating the index instead
2954 * of iterating over all entries.
2956 if (!ci->merged.clean)
2957 strmap_put(&opt->priv->conflicted, path, ci);
2958 record_entry_for_tree(dir_metadata, path, &ci->merged);
2961 static void process_entries(struct merge_options *opt,
2962 struct object_id *result_oid)
2964 struct hashmap_iter iter;
2965 struct strmap_entry *e;
2966 struct string_list plist = STRING_LIST_INIT_NODUP;
2967 struct string_list_item *entry;
2968 struct directory_versions dir_metadata = { STRING_LIST_INIT_NODUP,
2969 STRING_LIST_INIT_NODUP,
2972 trace2_region_enter("merge", "process_entries setup", opt->repo);
2973 if (strmap_empty(&opt->priv->paths)) {
2974 oidcpy(result_oid, opt->repo->hash_algo->empty_tree);
2978 /* Hack to pre-allocate plist to the desired size */
2979 trace2_region_enter("merge", "plist grow", opt->repo);
2980 ALLOC_GROW(plist.items, strmap_get_size(&opt->priv->paths), plist.alloc);
2981 trace2_region_leave("merge", "plist grow", opt->repo);
2983 /* Put every entry from paths into plist, then sort */
2984 trace2_region_enter("merge", "plist copy", opt->repo);
2985 strmap_for_each_entry(&opt->priv->paths, &iter, e) {
2986 string_list_append(&plist, e->key)->util = e->value;
2988 trace2_region_leave("merge", "plist copy", opt->repo);
2990 trace2_region_enter("merge", "plist special sort", opt->repo);
2991 plist.cmp = string_list_df_name_compare;
2992 string_list_sort(&plist);
2993 trace2_region_leave("merge", "plist special sort", opt->repo);
2995 trace2_region_leave("merge", "process_entries setup", opt->repo);
2998 * Iterate over the items in reverse order, so we can handle paths
2999 * below a directory before needing to handle the directory itself.
3001 * This allows us to write subtrees before we need to write trees,
3002 * and it also enables sane handling of directory/file conflicts
3003 * (because it allows us to know whether the directory is still in
3004 * the way when it is time to process the file at the same path).
3006 trace2_region_enter("merge", "processing", opt->repo);
3007 for (entry = &plist.items[plist.nr-1]; entry >= plist.items; --entry) {
3008 char *path = entry->string;
3010 * NOTE: mi may actually be a pointer to a conflict_info, but
3011 * we have to check mi->clean first to see if it's safe to
3012 * reassign to such a pointer type.
3014 struct merged_info *mi = entry->util;
3016 write_completed_directory(opt, mi->directory_name,
3019 record_entry_for_tree(&dir_metadata, path, mi);
3021 struct conflict_info *ci = (struct conflict_info *)mi;
3022 process_entry(opt, path, ci, &dir_metadata);
3025 trace2_region_leave("merge", "processing", opt->repo);
3027 trace2_region_enter("merge", "process_entries cleanup", opt->repo);
3028 if (dir_metadata.offsets.nr != 1 ||
3029 (uintptr_t)dir_metadata.offsets.items[0].util != 0) {
3030 printf("dir_metadata.offsets.nr = %d (should be 1)\n",
3031 dir_metadata.offsets.nr);
3032 printf("dir_metadata.offsets.items[0].util = %u (should be 0)\n",
3033 (unsigned)(uintptr_t)dir_metadata.offsets.items[0].util);
3035 BUG("dir_metadata accounting completely off; shouldn't happen");
3037 write_tree(result_oid, &dir_metadata.versions, 0,
3038 opt->repo->hash_algo->rawsz);
3039 string_list_clear(&plist, 0);
3040 string_list_clear(&dir_metadata.versions, 0);
3041 string_list_clear(&dir_metadata.offsets, 0);
3042 trace2_region_leave("merge", "process_entries cleanup", opt->repo);
3045 /*** Function Grouping: functions related to merge_switch_to_result() ***/
3047 static int checkout(struct merge_options *opt,
3051 /* Switch the index/working copy from old to new */
3053 struct tree_desc trees[2];
3054 struct unpack_trees_options unpack_opts;
3056 memset(&unpack_opts, 0, sizeof(unpack_opts));
3057 unpack_opts.head_idx = -1;
3058 unpack_opts.src_index = opt->repo->index;
3059 unpack_opts.dst_index = opt->repo->index;
3061 setup_unpack_trees_porcelain(&unpack_opts, "merge");
3064 * NOTE: if this were just "git checkout" code, we would probably
3065 * read or refresh the cache and check for a conflicted index, but
3066 * builtin/merge.c or sequencer.c really needs to read the index
3067 * and check for conflicted entries before starting merging for a
3068 * good user experience (no sense waiting for merges/rebases before
3069 * erroring out), so there's no reason to duplicate that work here.
3072 /* 2-way merge to the new branch */
3073 unpack_opts.update = 1;
3074 unpack_opts.merge = 1;
3075 unpack_opts.quiet = 0; /* FIXME: sequencer might want quiet? */
3076 unpack_opts.verbose_update = (opt->verbosity > 2);
3077 unpack_opts.fn = twoway_merge;
3078 if (1/* FIXME: opts->overwrite_ignore*/) {
3079 unpack_opts.dir = xcalloc(1, sizeof(*unpack_opts.dir));
3080 unpack_opts.dir->flags |= DIR_SHOW_IGNORED;
3081 setup_standard_excludes(unpack_opts.dir);
3084 init_tree_desc(&trees[0], prev->buffer, prev->size);
3086 init_tree_desc(&trees[1], next->buffer, next->size);
3088 ret = unpack_trees(2, trees, &unpack_opts);
3089 clear_unpack_trees_porcelain(&unpack_opts);
3090 dir_clear(unpack_opts.dir);
3091 FREE_AND_NULL(unpack_opts.dir);
3095 static int record_conflicted_index_entries(struct merge_options *opt,
3096 struct index_state *index,
3097 struct strmap *paths,
3098 struct strmap *conflicted)
3100 struct hashmap_iter iter;
3101 struct strmap_entry *e;
3103 int original_cache_nr;
3105 if (strmap_empty(conflicted))
3108 original_cache_nr = index->cache_nr;
3110 /* Put every entry from paths into plist, then sort */
3111 strmap_for_each_entry(conflicted, &iter, e) {
3112 const char *path = e->key;
3113 struct conflict_info *ci = e->value;
3115 struct cache_entry *ce;
3121 * The index will already have a stage=0 entry for this path,
3122 * because we created an as-merged-as-possible version of the
3123 * file and checkout() moved the working copy and index over
3126 * However, previous iterations through this loop will have
3127 * added unstaged entries to the end of the cache which
3128 * ignore the standard alphabetical ordering of cache
3129 * entries and break invariants needed for index_name_pos()
3130 * to work. However, we know the entry we want is before
3131 * those appended cache entries, so do a temporary swap on
3132 * cache_nr to only look through entries of interest.
3134 SWAP(index->cache_nr, original_cache_nr);
3135 pos = index_name_pos(index, path, strlen(path));
3136 SWAP(index->cache_nr, original_cache_nr);
3138 if (ci->filemask != 1)
3139 BUG("Conflicted %s but nothing in basic working tree or index; this shouldn't happen", path);
3140 cache_tree_invalidate_path(index, path);
3142 ce = index->cache[pos];
3145 * Clean paths with CE_SKIP_WORKTREE set will not be
3146 * written to the working tree by the unpack_trees()
3147 * call in checkout(). Our conflicted entries would
3148 * have appeared clean to that code since we ignored
3149 * the higher order stages. Thus, we need override
3150 * the CE_SKIP_WORKTREE bit and manually write those
3151 * files to the working disk here.
3153 * TODO: Implement this CE_SKIP_WORKTREE fixup.
3157 * Mark this cache entry for removal and instead add
3158 * new stage>0 entries corresponding to the
3159 * conflicts. If there are many conflicted entries, we
3160 * want to avoid memmove'ing O(NM) entries by
3161 * inserting the new entries one at a time. So,
3162 * instead, we just add the new cache entries to the
3163 * end (ignoring normal index requirements on sort
3164 * order) and sort the index once we're all done.
3166 ce->ce_flags |= CE_REMOVE;
3169 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
3170 struct version_info *vi;
3171 if (!(ci->filemask & (1ul << i)))
3173 vi = &ci->stages[i];
3174 ce = make_cache_entry(index, vi->mode, &vi->oid,
3176 add_index_entry(index, ce, ADD_CACHE_JUST_APPEND);
3181 * Remove the unused cache entries (and invalidate the relevant
3182 * cache-trees), then sort the index entries to get the conflicted
3183 * entries we added to the end into their right locations.
3185 remove_marked_cache_entries(index, 1);
3186 QSORT(index->cache, index->cache_nr, cmp_cache_name_compare);
3191 void merge_switch_to_result(struct merge_options *opt,
3193 struct merge_result *result,
3194 int update_worktree_and_index,
3195 int display_update_msgs)
3197 assert(opt->priv == NULL);
3198 if (result->clean >= 0 && update_worktree_and_index) {
3199 struct merge_options_internal *opti = result->priv;
3201 trace2_region_enter("merge", "checkout", opt->repo);
3202 if (checkout(opt, head, result->tree)) {
3203 /* failure to function */
3207 trace2_region_leave("merge", "checkout", opt->repo);
3209 trace2_region_enter("merge", "record_conflicted", opt->repo);
3210 if (record_conflicted_index_entries(opt, opt->repo->index,
3212 &opti->conflicted)) {
3213 /* failure to function */
3217 trace2_region_leave("merge", "record_conflicted", opt->repo);
3220 if (display_update_msgs) {
3221 struct merge_options_internal *opti = result->priv;
3222 struct hashmap_iter iter;
3223 struct strmap_entry *e;
3224 struct string_list olist = STRING_LIST_INIT_NODUP;
3227 trace2_region_enter("merge", "display messages", opt->repo);
3229 /* Hack to pre-allocate olist to the desired size */
3230 ALLOC_GROW(olist.items, strmap_get_size(&opti->output),
3233 /* Put every entry from output into olist, then sort */
3234 strmap_for_each_entry(&opti->output, &iter, e) {
3235 string_list_append(&olist, e->key)->util = e->value;
3237 string_list_sort(&olist);
3239 /* Iterate over the items, printing them */
3240 for (i = 0; i < olist.nr; ++i) {
3241 struct strbuf *sb = olist.items[i].util;
3243 printf("%s", sb->buf);
3245 string_list_clear(&olist, 0);
3247 /* Also include needed rename limit adjustment now */
3248 diff_warn_rename_limit("merge.renamelimit",
3249 opti->renames.needed_limit, 0);
3251 trace2_region_leave("merge", "display messages", opt->repo);
3254 merge_finalize(opt, result);
3257 void merge_finalize(struct merge_options *opt,
3258 struct merge_result *result)
3260 struct merge_options_internal *opti = result->priv;
3262 assert(opt->priv == NULL);
3264 clear_or_reinit_internal_opts(opti, 0);
3265 FREE_AND_NULL(opti);
3268 /*** Function Grouping: helper functions for merge_incore_*() ***/
3270 static inline void set_commit_tree(struct commit *c, struct tree *t)
3275 static struct commit *make_virtual_commit(struct repository *repo,
3277 const char *comment)
3279 struct commit *commit = alloc_commit_node(repo);
3281 set_merge_remote_desc(commit, comment, (struct object *)commit);
3282 set_commit_tree(commit, tree);
3283 commit->object.parsed = 1;
3287 static void merge_start(struct merge_options *opt, struct merge_result *result)
3289 struct rename_info *renames;
3292 /* Sanity checks on opt */
3293 trace2_region_enter("merge", "sanity checks", opt->repo);
3296 assert(opt->branch1 && opt->branch2);
3298 assert(opt->detect_directory_renames >= MERGE_DIRECTORY_RENAMES_NONE &&
3299 opt->detect_directory_renames <= MERGE_DIRECTORY_RENAMES_TRUE);
3300 assert(opt->rename_limit >= -1);
3301 assert(opt->rename_score >= 0 && opt->rename_score <= MAX_SCORE);
3302 assert(opt->show_rename_progress >= 0 && opt->show_rename_progress <= 1);
3304 assert(opt->xdl_opts >= 0);
3305 assert(opt->recursive_variant >= MERGE_VARIANT_NORMAL &&
3306 opt->recursive_variant <= MERGE_VARIANT_THEIRS);
3309 * detect_renames, verbosity, buffer_output, and obuf are ignored
3310 * fields that were used by "recursive" rather than "ort" -- but
3311 * sanity check them anyway.
3313 assert(opt->detect_renames >= -1 &&
3314 opt->detect_renames <= DIFF_DETECT_COPY);
3315 assert(opt->verbosity >= 0 && opt->verbosity <= 5);
3316 assert(opt->buffer_output <= 2);
3317 assert(opt->obuf.len == 0);
3319 assert(opt->priv == NULL);
3321 opt->priv = result->priv;
3322 result->priv = NULL;
3324 * opt->priv non-NULL means we had results from a previous
3325 * run; do a few sanity checks that user didn't mess with
3326 * it in an obvious fashion.
3328 assert(opt->priv->call_depth == 0);
3329 assert(!opt->priv->toplevel_dir ||
3330 0 == strlen(opt->priv->toplevel_dir));
3332 trace2_region_leave("merge", "sanity checks", opt->repo);
3334 /* Default to histogram diff. Actually, just hardcode it...for now. */
3335 opt->xdl_opts = DIFF_WITH_ALG(opt, HISTOGRAM_DIFF);
3337 /* Initialization of opt->priv, our internal merge data */
3338 trace2_region_enter("merge", "allocate/init", opt->repo);
3340 clear_or_reinit_internal_opts(opt->priv, 1);
3341 trace2_region_leave("merge", "allocate/init", opt->repo);
3344 opt->priv = xcalloc(1, sizeof(*opt->priv));
3346 /* Initialization of various renames fields */
3347 renames = &opt->priv->renames;
3348 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {
3349 strset_init_with_options(&renames->dirs_removed[i],
3351 strmap_init_with_options(&renames->dir_rename_count[i],
3353 strmap_init_with_options(&renames->dir_renames[i],
3355 strset_init_with_options(&renames->relevant_sources[i],
3360 * Although we initialize opt->priv->paths with strdup_strings=0,
3361 * that's just to avoid making yet another copy of an allocated
3362 * string. Putting the entry into paths means we are taking
3363 * ownership, so we will later free it. paths_to_free is similar.
3365 * In contrast, conflicted just has a subset of keys from paths, so
3366 * we don't want to free those (it'd be a duplicate free).
3368 strmap_init_with_options(&opt->priv->paths, NULL, 0);
3369 strmap_init_with_options(&opt->priv->conflicted, NULL, 0);
3370 string_list_init(&opt->priv->paths_to_free, 0);
3373 * keys & strbufs in output will sometimes need to outlive "paths",
3374 * so it will have a copy of relevant keys. It's probably a small
3375 * subset of the overall paths that have special output.
3377 strmap_init(&opt->priv->output);
3379 trace2_region_leave("merge", "allocate/init", opt->repo);
3382 /*** Function Grouping: merge_incore_*() and their internal variants ***/
3385 * Originally from merge_trees_internal(); heavily adapted, though.
3387 static void merge_ort_nonrecursive_internal(struct merge_options *opt,
3388 struct tree *merge_base,
3391 struct merge_result *result)
3393 struct object_id working_tree_oid;
3395 trace2_region_enter("merge", "collect_merge_info", opt->repo);
3396 if (collect_merge_info(opt, merge_base, side1, side2) != 0) {
3398 * TRANSLATORS: The %s arguments are: 1) tree hash of a merge
3399 * base, and 2-3) the trees for the two trees we're merging.
3401 err(opt, _("collecting merge info failed for trees %s, %s, %s"),
3402 oid_to_hex(&merge_base->object.oid),
3403 oid_to_hex(&side1->object.oid),
3404 oid_to_hex(&side2->object.oid));
3408 trace2_region_leave("merge", "collect_merge_info", opt->repo);
3410 trace2_region_enter("merge", "renames", opt->repo);
3411 result->clean = detect_and_process_renames(opt, merge_base,
3413 trace2_region_leave("merge", "renames", opt->repo);
3415 trace2_region_enter("merge", "process_entries", opt->repo);
3416 process_entries(opt, &working_tree_oid);
3417 trace2_region_leave("merge", "process_entries", opt->repo);
3419 /* Set return values */
3420 result->tree = parse_tree_indirect(&working_tree_oid);
3421 /* existence of conflicted entries implies unclean */
3422 result->clean &= strmap_empty(&opt->priv->conflicted);
3423 if (!opt->priv->call_depth) {
3424 result->priv = opt->priv;
3430 * Originally from merge_recursive_internal(); somewhat adapted, though.
3432 static void merge_ort_internal(struct merge_options *opt,
3433 struct commit_list *merge_bases,
3436 struct merge_result *result)
3438 struct commit_list *iter;
3439 struct commit *merged_merge_bases;
3440 const char *ancestor_name;
3441 struct strbuf merge_base_abbrev = STRBUF_INIT;
3444 merge_bases = get_merge_bases(h1, h2);
3445 /* See merge-ort.h:merge_incore_recursive() declaration NOTE */
3446 merge_bases = reverse_commit_list(merge_bases);
3449 merged_merge_bases = pop_commit(&merge_bases);
3450 if (merged_merge_bases == NULL) {
3451 /* if there is no common ancestor, use an empty tree */
3454 tree = lookup_tree(opt->repo, opt->repo->hash_algo->empty_tree);
3455 merged_merge_bases = make_virtual_commit(opt->repo, tree,
3457 ancestor_name = "empty tree";
3458 } else if (merge_bases) {
3459 ancestor_name = "merged common ancestors";
3461 strbuf_add_unique_abbrev(&merge_base_abbrev,
3462 &merged_merge_bases->object.oid,
3464 ancestor_name = merge_base_abbrev.buf;
3467 for (iter = merge_bases; iter; iter = iter->next) {
3468 const char *saved_b1, *saved_b2;
3469 struct commit *prev = merged_merge_bases;
3471 opt->priv->call_depth++;
3473 * When the merge fails, the result contains files
3474 * with conflict markers. The cleanness flag is
3475 * ignored (unless indicating an error), it was never
3476 * actually used, as result of merge_trees has always
3477 * overwritten it: the committed "conflicts" were
3480 saved_b1 = opt->branch1;
3481 saved_b2 = opt->branch2;
3482 opt->branch1 = "Temporary merge branch 1";
3483 opt->branch2 = "Temporary merge branch 2";
3484 merge_ort_internal(opt, NULL, prev, iter->item, result);
3485 if (result->clean < 0)
3487 opt->branch1 = saved_b1;
3488 opt->branch2 = saved_b2;
3489 opt->priv->call_depth--;
3491 merged_merge_bases = make_virtual_commit(opt->repo,
3494 commit_list_insert(prev, &merged_merge_bases->parents);
3495 commit_list_insert(iter->item,
3496 &merged_merge_bases->parents->next);
3498 clear_or_reinit_internal_opts(opt->priv, 1);
3501 opt->ancestor = ancestor_name;
3502 merge_ort_nonrecursive_internal(opt,
3503 repo_get_commit_tree(opt->repo,
3504 merged_merge_bases),
3505 repo_get_commit_tree(opt->repo, h1),
3506 repo_get_commit_tree(opt->repo, h2),
3508 strbuf_release(&merge_base_abbrev);
3509 opt->ancestor = NULL; /* avoid accidental re-use of opt->ancestor */
3512 void merge_incore_nonrecursive(struct merge_options *opt,
3513 struct tree *merge_base,
3516 struct merge_result *result)
3518 trace2_region_enter("merge", "incore_nonrecursive", opt->repo);
3520 trace2_region_enter("merge", "merge_start", opt->repo);
3521 assert(opt->ancestor != NULL);
3522 merge_start(opt, result);
3523 trace2_region_leave("merge", "merge_start", opt->repo);
3525 merge_ort_nonrecursive_internal(opt, merge_base, side1, side2, result);
3526 trace2_region_leave("merge", "incore_nonrecursive", opt->repo);
3529 void merge_incore_recursive(struct merge_options *opt,
3530 struct commit_list *merge_bases,
3531 struct commit *side1,
3532 struct commit *side2,
3533 struct merge_result *result)
3535 trace2_region_enter("merge", "incore_recursive", opt->repo);
3537 /* We set the ancestor label based on the merge_bases */
3538 assert(opt->ancestor == NULL);
3540 trace2_region_enter("merge", "merge_start", opt->repo);
3541 merge_start(opt, result);
3542 trace2_region_leave("merge", "merge_start", opt->repo);
3544 merge_ort_internal(opt, merge_bases, side1, side2, result);
3545 trace2_region_leave("merge", "incore_recursive", opt->repo);