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"
23 #include "cache-tree.h"
25 #include "commit-reach.h"
30 #include "object-store.h"
33 #include "submodule.h"
35 #include "unpack-trees.h"
36 #include "xdiff-interface.h"
39 * We have many arrays of size 3. Whenever we have such an array, the
40 * indices refer to one of the sides of the three-way merge. This is so
41 * pervasive that the constants 0, 1, and 2 are used in many places in the
42 * code (especially in arithmetic operations to find the other side's index
43 * or to compute a relevant mask), but sometimes these enum names are used
44 * to aid code clarity.
46 * See also 'filemask' and 'dirmask' in struct conflict_info; the "ith side"
47 * referred to there is one of these three sides.
55 struct traversal_callback_data {
57 unsigned long dirmask;
58 struct name_entry names[3];
63 * All variables that are arrays of size 3 correspond to data tracked
64 * for the sides in enum merge_side. Index 0 is almost always unused
65 * because we often only need to track information for MERGE_SIDE1 and
66 * MERGE_SIDE2 (MERGE_BASE can't have rename information since renames
67 * are determined relative to what changed since the MERGE_BASE).
71 * pairs: pairing of filenames from diffcore_rename()
73 struct diff_queue_struct pairs[3];
76 * dirs_removed: directories removed on a given side of history.
78 * The keys of dirs_removed[side] are the directories that were removed
79 * on the given side of history. The value of the strintmap for each
80 * directory is a value from enum dir_rename_relevance.
82 struct strintmap dirs_removed[3];
85 * dir_rename_count: tracking where parts of a directory were renamed to
87 * When files in a directory are renamed, they may not all go to the
88 * same location. Each strmap here tracks:
89 * old_dir => {new_dir => int}
90 * That is, dir_rename_count[side] is a strmap to a strintmap.
92 struct strmap dir_rename_count[3];
95 * dir_renames: computed directory renames
97 * This is a map of old_dir => new_dir and is derived in part from
100 struct strmap dir_renames[3];
103 * relevant_sources: deleted paths wanted in rename detection, and why
105 * relevant_sources is a set of deleted paths on each side of
106 * history for which we need rename detection. If a path is deleted
107 * on one side of history, we need to detect if it is part of a
109 * * the file is modified/deleted on the other side of history
110 * * we need to detect renames for an ancestor directory
111 * If neither of those are true, we can skip rename detection for
112 * that path. The reason is stored as a value from enum
113 * file_rename_relevance, as the reason can inform the algorithm in
114 * diffcore_rename_extended().
116 struct strintmap relevant_sources[3];
120 * 0: optimization removing unmodified potential rename source okay
121 * 2 or 4: optimization okay, but must check for files added to dir
122 * 7: optimization forbidden; need rename source in case of dir rename
124 unsigned dir_rename_mask:3;
127 * callback_data_*: supporting data structures for alternate traversal
129 * We sometimes need to be able to traverse through all the files
130 * in a given tree before all immediate subdirectories within that
131 * tree. Since traverse_trees() doesn't do that naturally, we have
132 * a traverse_trees_wrapper() that stores any immediate
133 * subdirectories while traversing files, then traverses the
134 * immediate subdirectories later. These callback_data* variables
135 * store the information for the subdirectories so that we can do
136 * that traversal order.
138 struct traversal_callback_data *callback_data;
139 int callback_data_nr, callback_data_alloc;
140 char *callback_data_traverse_path;
143 * needed_limit: value needed for inexact rename detection to run
145 * If the current rename limit wasn't high enough for inexact
146 * rename detection to run, this records the limit needed. Otherwise,
147 * this value remains 0.
152 struct merge_options_internal {
154 * paths: primary data structure in all of merge ort.
157 * * are full relative paths from the toplevel of the repository
158 * (e.g. "drivers/firmware/raspberrypi.c").
159 * * store all relevant paths in the repo, both directories and
160 * files (e.g. drivers, drivers/firmware would also be included)
161 * * these keys serve to intern all the path strings, which allows
162 * us to do pointer comparison on directory names instead of
163 * strcmp; we just have to be careful to use the interned strings.
164 * (Technically paths_to_free may track some strings that were
165 * removed from froms paths.)
167 * The values of paths:
168 * * either a pointer to a merged_info, or a conflict_info struct
169 * * merged_info contains all relevant information for a
170 * non-conflicted entry.
171 * * conflict_info contains a merged_info, plus any additional
172 * information about a conflict such as the higher orders stages
173 * involved and the names of the paths those came from (handy
174 * once renames get involved).
175 * * a path may start "conflicted" (i.e. point to a conflict_info)
176 * and then a later step (e.g. three-way content merge) determines
177 * it can be cleanly merged, at which point it'll be marked clean
178 * and the algorithm will ignore any data outside the contained
179 * merged_info for that entry
180 * * If an entry remains conflicted, the merged_info portion of a
181 * conflict_info will later be filled with whatever version of
182 * the file should be placed in the working directory (e.g. an
183 * as-merged-as-possible variation that contains conflict markers).
188 * conflicted: a subset of keys->values from "paths"
190 * conflicted is basically an optimization between process_entries()
191 * and record_conflicted_index_entries(); the latter could loop over
192 * ALL the entries in paths AGAIN and look for the ones that are
193 * still conflicted, but since process_entries() has to loop over
194 * all of them, it saves the ones it couldn't resolve in this strmap
195 * so that record_conflicted_index_entries() can iterate just the
198 struct strmap conflicted;
201 * paths_to_free: additional list of strings to free
203 * If keys are removed from "paths", they are added to paths_to_free
204 * to ensure they are later freed. We avoid free'ing immediately since
205 * other places (e.g. conflict_info.pathnames[]) may still be
206 * referencing these paths.
208 struct string_list paths_to_free;
211 * output: special messages and conflict notices for various paths
213 * This is a map of pathnames (a subset of the keys in "paths" above)
214 * to strbufs. It gathers various warning/conflict/notice messages
215 * for later processing.
217 struct strmap output;
220 * renames: various data relating to rename detection
222 struct rename_info renames;
225 * attr_index: hacky minimal index used for renormalization
227 * renormalization code _requires_ an index, though it only needs to
228 * find a .gitattributes file within the index. So, when
229 * renormalization is important, we create a special index with just
232 struct index_state attr_index;
235 * current_dir_name, toplevel_dir: temporary vars
237 * These are used in collect_merge_info_callback(), and will set the
238 * various merged_info.directory_name for the various paths we get;
239 * see documentation for that variable and the requirements placed on
242 const char *current_dir_name;
243 const char *toplevel_dir;
245 /* call_depth: recursion level counter for merging merge bases */
249 struct version_info {
250 struct object_id oid;
255 /* if is_null, ignore result. otherwise result has oid & mode */
256 struct version_info result;
260 * clean: whether the path in question is cleanly merged.
262 * see conflict_info.merged for more details.
267 * basename_offset: offset of basename of path.
269 * perf optimization to avoid recomputing offset of final '/'
270 * character in pathname (0 if no '/' in pathname).
272 size_t basename_offset;
275 * directory_name: containing directory name.
277 * Note that we assume directory_name is constructed such that
278 * strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name,
279 * i.e. string equality is equivalent to pointer equality. For this
280 * to hold, we have to be careful setting directory_name.
282 const char *directory_name;
285 struct conflict_info {
287 * merged: the version of the path that will be written to working tree
289 * WARNING: It is critical to check merged.clean and ensure it is 0
290 * before reading any conflict_info fields outside of merged.
291 * Allocated merge_info structs will always have clean set to 1.
292 * Allocated conflict_info structs will have merged.clean set to 0
293 * initially. The merged.clean field is how we know if it is safe
294 * to access other parts of conflict_info besides merged; if a
295 * conflict_info's merged.clean is changed to 1, the rest of the
296 * algorithm is not allowed to look at anything outside of the
297 * merged member anymore.
299 struct merged_info merged;
301 /* oids & modes from each of the three trees for this path */
302 struct version_info stages[3];
304 /* pathnames for each stage; may differ due to rename detection */
305 const char *pathnames[3];
307 /* Whether this path is/was involved in a directory/file conflict */
308 unsigned df_conflict:1;
311 * Whether this path is/was involved in a non-content conflict other
312 * than a directory/file conflict (e.g. rename/rename, rename/delete,
313 * file location based on possible directory rename).
315 unsigned path_conflict:1;
318 * For filemask and dirmask, the ith bit corresponds to whether the
319 * ith entry is a file (filemask) or a directory (dirmask). Thus,
320 * filemask & dirmask is always zero, and filemask | dirmask is at
321 * most 7 but can be less when a path does not appear as either a
322 * file or a directory on at least one side of history.
324 * Note that these masks are related to enum merge_side, as the ith
325 * entry corresponds to side i.
327 * These values come from a traverse_trees() call; more info may be
328 * found looking at tree-walk.h's struct traverse_info,
329 * particularly the documentation above the "fn" member (note that
330 * filemask = mask & ~dirmask from that documentation).
336 * Optimization to track which stages match, to avoid the need to
337 * recompute it in multiple steps. Either 0 or at least 2 bits are
338 * set; if at least 2 bits are set, their corresponding stages match.
340 unsigned match_mask:3;
343 /*** Function Grouping: various utility functions ***/
346 * For the next three macros, see warning for conflict_info.merged.
348 * In each of the below, mi is a struct merged_info*, and ci was defined
349 * as a struct conflict_info* (but we need to verify ci isn't actually
350 * pointed at a struct merged_info*).
352 * INITIALIZE_CI: Assign ci to mi but only if it's safe; set to NULL otherwise.
353 * VERIFY_CI: Ensure that something we assigned to a conflict_info* is one.
354 * ASSIGN_AND_VERIFY_CI: Similar to VERIFY_CI but do assignment first.
356 #define INITIALIZE_CI(ci, mi) do { \
357 (ci) = (!(mi) || (mi)->clean) ? NULL : (struct conflict_info *)(mi); \
359 #define VERIFY_CI(ci) assert(ci && !ci->merged.clean);
360 #define ASSIGN_AND_VERIFY_CI(ci, mi) do { \
361 (ci) = (struct conflict_info *)(mi); \
362 assert((ci) && !(mi)->clean); \
365 static void free_strmap_strings(struct strmap *map)
367 struct hashmap_iter iter;
368 struct strmap_entry *entry;
370 strmap_for_each_entry(map, &iter, entry) {
371 free((char*)entry->key);
375 static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,
378 struct rename_info *renames = &opti->renames;
380 void (*strmap_func)(struct strmap *, int) =
381 reinitialize ? strmap_partial_clear : strmap_clear;
382 void (*strintmap_func)(struct strintmap *) =
383 reinitialize ? strintmap_partial_clear : strintmap_clear;
386 * We marked opti->paths with strdup_strings = 0, so that we
387 * wouldn't have to make another copy of the fullpath created by
388 * make_traverse_path from setup_path_info(). But, now that we've
389 * used it and have no other references to these strings, it is time
390 * to deallocate them.
392 free_strmap_strings(&opti->paths);
393 strmap_func(&opti->paths, 1);
396 * All keys and values in opti->conflicted are a subset of those in
397 * opti->paths. We don't want to deallocate anything twice, so we
398 * don't free the keys and we pass 0 for free_values.
400 strmap_func(&opti->conflicted, 0);
403 * opti->paths_to_free is similar to opti->paths; we created it with
404 * strdup_strings = 0 to avoid making _another_ copy of the fullpath
405 * but now that we've used it and have no other references to these
406 * strings, it is time to deallocate them. We do so by temporarily
407 * setting strdup_strings to 1.
409 opti->paths_to_free.strdup_strings = 1;
410 string_list_clear(&opti->paths_to_free, 0);
411 opti->paths_to_free.strdup_strings = 0;
413 if (opti->attr_index.cache_nr) /* true iff opt->renormalize */
414 discard_index(&opti->attr_index);
416 /* Free memory used by various renames maps */
417 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; ++i) {
418 strintmap_func(&renames->dirs_removed[i]);
420 partial_clear_dir_rename_count(&renames->dir_rename_count[i]);
422 strmap_clear(&renames->dir_rename_count[i], 1);
424 strmap_func(&renames->dir_renames[i], 0);
426 strintmap_func(&renames->relevant_sources[i]);
430 struct hashmap_iter iter;
431 struct strmap_entry *e;
433 /* Release and free each strbuf found in output */
434 strmap_for_each_entry(&opti->output, &iter, e) {
435 struct strbuf *sb = e->value;
438 * While strictly speaking we don't need to free(sb)
439 * here because we could pass free_values=1 when
440 * calling strmap_clear() on opti->output, that would
441 * require strmap_clear to do another
442 * strmap_for_each_entry() loop, so we just free it
443 * while we're iterating anyway.
447 strmap_clear(&opti->output, 0);
450 renames->dir_rename_mask = 0;
452 /* Clean out callback_data as well. */
453 FREE_AND_NULL(renames->callback_data);
454 renames->callback_data_nr = renames->callback_data_alloc = 0;
457 static int err(struct merge_options *opt, const char *err, ...)
460 struct strbuf sb = STRBUF_INIT;
462 strbuf_addstr(&sb, "error: ");
463 va_start(params, err);
464 strbuf_vaddf(&sb, err, params);
473 static void format_commit(struct strbuf *sb,
475 struct commit *commit)
477 struct merge_remote_desc *desc;
478 struct pretty_print_context ctx = {0};
479 ctx.abbrev = DEFAULT_ABBREV;
481 strbuf_addchars(sb, ' ', indent);
482 desc = merge_remote_util(commit);
484 strbuf_addf(sb, "virtual %s\n", desc->name);
488 format_commit_message(commit, "%h %s", sb, &ctx);
489 strbuf_addch(sb, '\n');
492 __attribute__((format (printf, 4, 5)))
493 static void path_msg(struct merge_options *opt,
495 int omittable_hint, /* skippable under --remerge-diff */
496 const char *fmt, ...)
499 struct strbuf *sb = strmap_get(&opt->priv->output, path);
501 sb = xmalloc(sizeof(*sb));
503 strmap_put(&opt->priv->output, path, sb);
507 strbuf_vaddf(sb, fmt, ap);
510 strbuf_addch(sb, '\n');
513 /* add a string to a strbuf, but converting "/" to "_" */
514 static void add_flattened_path(struct strbuf *out, const char *s)
517 strbuf_addstr(out, s);
518 for (; i < out->len; i++)
519 if (out->buf[i] == '/')
523 static char *unique_path(struct strmap *existing_paths,
527 struct strbuf newpath = STRBUF_INIT;
531 strbuf_addf(&newpath, "%s~", path);
532 add_flattened_path(&newpath, branch);
534 base_len = newpath.len;
535 while (strmap_contains(existing_paths, newpath.buf)) {
536 strbuf_setlen(&newpath, base_len);
537 strbuf_addf(&newpath, "_%d", suffix++);
540 return strbuf_detach(&newpath, NULL);
543 /*** Function Grouping: functions related to collect_merge_info() ***/
545 static int traverse_trees_wrapper_callback(int n,
547 unsigned long dirmask,
548 struct name_entry *names,
549 struct traverse_info *info)
551 struct merge_options *opt = info->data;
552 struct rename_info *renames = &opt->priv->renames;
553 unsigned filemask = mask & ~dirmask;
557 if (!renames->callback_data_traverse_path)
558 renames->callback_data_traverse_path = xstrdup(info->traverse_path);
560 if (filemask && filemask == renames->dir_rename_mask)
561 renames->dir_rename_mask = 0x07;
563 ALLOC_GROW(renames->callback_data, renames->callback_data_nr + 1,
564 renames->callback_data_alloc);
565 renames->callback_data[renames->callback_data_nr].mask = mask;
566 renames->callback_data[renames->callback_data_nr].dirmask = dirmask;
567 COPY_ARRAY(renames->callback_data[renames->callback_data_nr].names,
569 renames->callback_data_nr++;
575 * Much like traverse_trees(), BUT:
576 * - read all the tree entries FIRST, saving them
577 * - note that the above step provides an opportunity to compute necessary
578 * additional details before the "real" traversal
579 * - loop through the saved entries and call the original callback on them
581 static int traverse_trees_wrapper(struct index_state *istate,
584 struct traverse_info *info)
586 int ret, i, old_offset;
587 traverse_callback_t old_fn;
588 char *old_callback_data_traverse_path;
589 struct merge_options *opt = info->data;
590 struct rename_info *renames = &opt->priv->renames;
592 assert(renames->dir_rename_mask == 2 || renames->dir_rename_mask == 4);
594 old_callback_data_traverse_path = renames->callback_data_traverse_path;
596 old_offset = renames->callback_data_nr;
598 renames->callback_data_traverse_path = NULL;
599 info->fn = traverse_trees_wrapper_callback;
600 ret = traverse_trees(istate, n, t, info);
604 info->traverse_path = renames->callback_data_traverse_path;
606 for (i = old_offset; i < renames->callback_data_nr; ++i) {
608 renames->callback_data[i].mask,
609 renames->callback_data[i].dirmask,
610 renames->callback_data[i].names,
614 renames->callback_data_nr = old_offset;
615 free(renames->callback_data_traverse_path);
616 renames->callback_data_traverse_path = old_callback_data_traverse_path;
617 info->traverse_path = NULL;
621 static void setup_path_info(struct merge_options *opt,
622 struct string_list_item *result,
623 const char *current_dir_name,
624 int current_dir_name_len,
625 char *fullpath, /* we'll take over ownership */
626 struct name_entry *names,
627 struct name_entry *merged_version,
628 unsigned is_null, /* boolean */
629 unsigned df_conflict, /* boolean */
632 int resolved /* boolean */)
634 /* result->util is void*, so mi is a convenience typed variable */
635 struct merged_info *mi;
637 assert(!is_null || resolved);
638 assert(!df_conflict || !resolved); /* df_conflict implies !resolved */
639 assert(resolved == (merged_version != NULL));
641 mi = xcalloc(1, resolved ? sizeof(struct merged_info) :
642 sizeof(struct conflict_info));
643 mi->directory_name = current_dir_name;
644 mi->basename_offset = current_dir_name_len;
645 mi->clean = !!resolved;
647 mi->result.mode = merged_version->mode;
648 oidcpy(&mi->result.oid, &merged_version->oid);
649 mi->is_null = !!is_null;
652 struct conflict_info *ci;
654 ASSIGN_AND_VERIFY_CI(ci, mi);
655 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
656 ci->pathnames[i] = fullpath;
657 ci->stages[i].mode = names[i].mode;
658 oidcpy(&ci->stages[i].oid, &names[i].oid);
660 ci->filemask = filemask;
661 ci->dirmask = dirmask;
662 ci->df_conflict = !!df_conflict;
665 * Assume is_null for now, but if we have entries
666 * under the directory then when it is complete in
667 * write_completed_directory() it'll update this.
668 * Also, for D/F conflicts, we have to handle the
669 * directory first, then clear this bit and process
670 * the file to see how it is handled -- that occurs
671 * near the top of process_entry().
675 strmap_put(&opt->priv->paths, fullpath, mi);
676 result->string = fullpath;
680 static void add_pair(struct merge_options *opt,
681 struct name_entry *names,
682 const char *pathname,
684 unsigned is_add /* if false, is_delete */,
686 unsigned dir_rename_mask)
688 struct diff_filespec *one, *two;
689 struct rename_info *renames = &opt->priv->renames;
690 int names_idx = is_add ? side : 0;
693 unsigned content_relevant = (match_mask == 0);
694 unsigned location_relevant = (dir_rename_mask == 0x07);
696 if (content_relevant || location_relevant) {
697 /* content_relevant trumps location_relevant */
698 strintmap_set(&renames->relevant_sources[side], pathname,
699 content_relevant ? RELEVANT_CONTENT : RELEVANT_LOCATION);
703 one = alloc_filespec(pathname);
704 two = alloc_filespec(pathname);
705 fill_filespec(is_add ? two : one,
706 &names[names_idx].oid, 1, names[names_idx].mode);
707 diff_queue(&renames->pairs[side], one, two);
710 static void collect_rename_info(struct merge_options *opt,
711 struct name_entry *names,
713 const char *fullname,
718 struct rename_info *renames = &opt->priv->renames;
722 * Update dir_rename_mask (determines ignore-rename-source validity)
724 * dir_rename_mask helps us keep track of when directory rename
725 * detection may be relevant. Basically, whenver a directory is
726 * removed on one side of history, and a file is added to that
727 * directory on the other side of history, directory rename
728 * detection is relevant (meaning we have to detect renames for all
729 * files within that directory to deduce where the directory
730 * moved). Also, whenever a directory needs directory rename
731 * detection, due to the "majority rules" choice for where to move
732 * it (see t6423 testcase 1f), we also need to detect renames for
733 * all files within subdirectories of that directory as well.
735 * Here we haven't looked at files within the directory yet, we are
736 * just looking at the directory itself. So, if we aren't yet in
737 * a case where a parent directory needed directory rename detection
738 * (i.e. dir_rename_mask != 0x07), and if the directory was removed
739 * on one side of history, record the mask of the other side of
740 * history in dir_rename_mask.
742 if (renames->dir_rename_mask != 0x07 &&
743 (dirmask == 3 || dirmask == 5)) {
744 /* simple sanity check */
745 assert(renames->dir_rename_mask == 0 ||
746 renames->dir_rename_mask == (dirmask & ~1));
747 /* update dir_rename_mask; have it record mask of new side */
748 renames->dir_rename_mask = (dirmask & ~1);
751 /* Update dirs_removed, as needed */
752 if (dirmask == 1 || dirmask == 3 || dirmask == 5) {
753 /* absent_mask = 0x07 - dirmask; sides = absent_mask/2 */
754 unsigned sides = (0x07 - dirmask)/2;
755 unsigned relevance = (renames->dir_rename_mask == 0x07) ?
756 RELEVANT_FOR_ANCESTOR : NOT_RELEVANT;
758 * Record relevance of this directory. However, note that
759 * when collect_merge_info_callback() recurses into this
760 * directory and calls collect_rename_info() on paths
761 * within that directory, if we find a path that was added
762 * to this directory on the other side of history, we will
763 * upgrade this value to RELEVANT_FOR_SELF; see below.
766 strintmap_set(&renames->dirs_removed[1], fullname,
769 strintmap_set(&renames->dirs_removed[2], fullname,
774 * Here's the block that potentially upgrades to RELEVANT_FOR_SELF.
775 * When we run across a file added to a directory. In such a case,
776 * find the directory of the file and upgrade its relevance.
778 if (renames->dir_rename_mask == 0x07 &&
779 (filemask == 2 || filemask == 4)) {
781 * Need directory rename for parent directory on other side
782 * of history from added file. Thus
783 * side = (~filemask & 0x06) >> 1
785 * side = 3 - (filemask/2).
787 unsigned side = 3 - (filemask >> 1);
788 strintmap_set(&renames->dirs_removed[side], dirname,
792 if (filemask == 0 || filemask == 7)
795 for (side = MERGE_SIDE1; side <= MERGE_SIDE2; ++side) {
796 unsigned side_mask = (1 << side);
798 /* Check for deletion on side */
799 if ((filemask & 1) && !(filemask & side_mask))
800 add_pair(opt, names, fullname, side, 0 /* delete */,
801 match_mask & filemask,
802 renames->dir_rename_mask);
804 /* Check for addition on side */
805 if (!(filemask & 1) && (filemask & side_mask))
806 add_pair(opt, names, fullname, side, 1 /* add */,
807 match_mask & filemask,
808 renames->dir_rename_mask);
812 static int collect_merge_info_callback(int n,
814 unsigned long dirmask,
815 struct name_entry *names,
816 struct traverse_info *info)
820 * common ancestor (mbase) has mask 1, and stored in index 0 of names
821 * head of side 1 (side1) has mask 2, and stored in index 1 of names
822 * head of side 2 (side2) has mask 4, and stored in index 2 of names
824 struct merge_options *opt = info->data;
825 struct merge_options_internal *opti = opt->priv;
826 struct rename_info *renames = &opt->priv->renames;
827 struct string_list_item pi; /* Path Info */
828 struct conflict_info *ci; /* typed alias to pi.util (which is void*) */
829 struct name_entry *p;
832 const char *dirname = opti->current_dir_name;
833 unsigned prev_dir_rename_mask = renames->dir_rename_mask;
834 unsigned filemask = mask & ~dirmask;
835 unsigned match_mask = 0; /* will be updated below */
836 unsigned mbase_null = !(mask & 1);
837 unsigned side1_null = !(mask & 2);
838 unsigned side2_null = !(mask & 4);
839 unsigned side1_matches_mbase = (!side1_null && !mbase_null &&
840 names[0].mode == names[1].mode &&
841 oideq(&names[0].oid, &names[1].oid));
842 unsigned side2_matches_mbase = (!side2_null && !mbase_null &&
843 names[0].mode == names[2].mode &&
844 oideq(&names[0].oid, &names[2].oid));
845 unsigned sides_match = (!side1_null && !side2_null &&
846 names[1].mode == names[2].mode &&
847 oideq(&names[1].oid, &names[2].oid));
850 * Note: When a path is a file on one side of history and a directory
851 * in another, we have a directory/file conflict. In such cases, if
852 * the conflict doesn't resolve from renames and deletions, then we
853 * always leave directories where they are and move files out of the
854 * way. Thus, while struct conflict_info has a df_conflict field to
855 * track such conflicts, we ignore that field for any directories at
856 * a path and only pay attention to it for files at the given path.
857 * The fact that we leave directories were they are also means that
858 * we do not need to worry about getting additional df_conflict
859 * information propagated from parent directories down to children
860 * (unlike, say traverse_trees_recursive() in unpack-trees.c, which
861 * sets a newinfo.df_conflicts field specifically to propagate it).
863 unsigned df_conflict = (filemask != 0) && (dirmask != 0);
865 /* n = 3 is a fundamental assumption. */
867 BUG("Called collect_merge_info_callback wrong");
870 * A bunch of sanity checks verifying that traverse_trees() calls
871 * us the way I expect. Could just remove these at some point,
872 * though maybe they are helpful to future code readers.
874 assert(mbase_null == is_null_oid(&names[0].oid));
875 assert(side1_null == is_null_oid(&names[1].oid));
876 assert(side2_null == is_null_oid(&names[2].oid));
877 assert(!mbase_null || !side1_null || !side2_null);
878 assert(mask > 0 && mask < 8);
880 /* Determine match_mask */
881 if (side1_matches_mbase)
882 match_mask = (side2_matches_mbase ? 7 : 3);
883 else if (side2_matches_mbase)
885 else if (sides_match)
889 * Get the name of the relevant filepath, which we'll pass to
890 * setup_path_info() for tracking.
895 len = traverse_path_len(info, p->pathlen);
897 /* +1 in both of the following lines to include the NUL byte */
898 fullpath = xmalloc(len + 1);
899 make_traverse_path(fullpath, len + 1, info, p->path, p->pathlen);
902 * If mbase, side1, and side2 all match, we can resolve early. Even
903 * if these are trees, there will be no renames or anything
906 if (side1_matches_mbase && side2_matches_mbase) {
907 /* mbase, side1, & side2 all match; use mbase as resolution */
908 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
909 names, names+0, mbase_null, 0,
910 filemask, dirmask, 1);
915 * Gather additional information used in rename detection.
917 collect_rename_info(opt, names, dirname, fullpath,
918 filemask, dirmask, match_mask);
921 * Record information about the path so we can resolve later in
924 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
925 names, NULL, 0, df_conflict, filemask, dirmask, 0);
929 ci->match_mask = match_mask;
931 /* If dirmask, recurse into subdirectories */
933 struct traverse_info newinfo;
934 struct tree_desc t[3];
935 void *buf[3] = {NULL, NULL, NULL};
936 const char *original_dir_name;
939 ci->match_mask &= filemask;
942 newinfo.name = p->path;
943 newinfo.namelen = p->pathlen;
944 newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1);
946 * If this directory we are about to recurse into cared about
947 * its parent directory (the current directory) having a D/F
948 * conflict, then we'd propagate the masks in this way:
949 * newinfo.df_conflicts |= (mask & ~dirmask);
950 * But we don't worry about propagating D/F conflicts. (See
951 * comment near setting of local df_conflict variable near
952 * the beginning of this function).
955 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
956 if (i == 1 && side1_matches_mbase)
958 else if (i == 2 && side2_matches_mbase)
960 else if (i == 2 && sides_match)
963 const struct object_id *oid = NULL;
966 buf[i] = fill_tree_descriptor(opt->repo,
972 original_dir_name = opti->current_dir_name;
973 opti->current_dir_name = pi.string;
974 if (renames->dir_rename_mask == 0 ||
975 renames->dir_rename_mask == 0x07)
976 ret = traverse_trees(NULL, 3, t, &newinfo);
978 ret = traverse_trees_wrapper(NULL, 3, t, &newinfo);
979 opti->current_dir_name = original_dir_name;
980 renames->dir_rename_mask = prev_dir_rename_mask;
982 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++)
992 static int collect_merge_info(struct merge_options *opt,
993 struct tree *merge_base,
998 struct tree_desc t[3];
999 struct traverse_info info;
1001 opt->priv->toplevel_dir = "";
1002 opt->priv->current_dir_name = opt->priv->toplevel_dir;
1003 setup_traverse_info(&info, opt->priv->toplevel_dir);
1004 info.fn = collect_merge_info_callback;
1006 info.show_all_errors = 1;
1008 parse_tree(merge_base);
1011 init_tree_desc(t + 0, merge_base->buffer, merge_base->size);
1012 init_tree_desc(t + 1, side1->buffer, side1->size);
1013 init_tree_desc(t + 2, side2->buffer, side2->size);
1015 trace2_region_enter("merge", "traverse_trees", opt->repo);
1016 ret = traverse_trees(NULL, 3, t, &info);
1017 trace2_region_leave("merge", "traverse_trees", opt->repo);
1022 /*** Function Grouping: functions related to threeway content merges ***/
1024 static int find_first_merges(struct repository *repo,
1028 struct object_array *result)
1031 struct object_array merges = OBJECT_ARRAY_INIT;
1032 struct commit *commit;
1033 int contains_another;
1035 char merged_revision[GIT_MAX_HEXSZ + 2];
1036 const char *rev_args[] = { "rev-list", "--merges", "--ancestry-path",
1037 "--all", merged_revision, NULL };
1038 struct rev_info revs;
1039 struct setup_revision_opt rev_opts;
1041 memset(result, 0, sizeof(struct object_array));
1042 memset(&rev_opts, 0, sizeof(rev_opts));
1044 /* get all revisions that merge commit a */
1045 xsnprintf(merged_revision, sizeof(merged_revision), "^%s",
1046 oid_to_hex(&a->object.oid));
1047 repo_init_revisions(repo, &revs, NULL);
1048 rev_opts.submodule = path;
1049 /* FIXME: can't handle linked worktrees in submodules yet */
1050 revs.single_worktree = path != NULL;
1051 setup_revisions(ARRAY_SIZE(rev_args)-1, rev_args, &revs, &rev_opts);
1053 /* save all revisions from the above list that contain b */
1054 if (prepare_revision_walk(&revs))
1055 die("revision walk setup failed");
1056 while ((commit = get_revision(&revs)) != NULL) {
1057 struct object *o = &(commit->object);
1058 if (in_merge_bases(b, commit))
1059 add_object_array(o, NULL, &merges);
1061 reset_revision_walk();
1063 /* Now we've got all merges that contain a and b. Prune all
1064 * merges that contain another found merge and save them in
1067 for (i = 0; i < merges.nr; i++) {
1068 struct commit *m1 = (struct commit *) merges.objects[i].item;
1070 contains_another = 0;
1071 for (j = 0; j < merges.nr; j++) {
1072 struct commit *m2 = (struct commit *) merges.objects[j].item;
1073 if (i != j && in_merge_bases(m2, m1)) {
1074 contains_another = 1;
1079 if (!contains_another)
1080 add_object_array(merges.objects[i].item, NULL, result);
1083 object_array_clear(&merges);
1087 static int merge_submodule(struct merge_options *opt,
1089 const struct object_id *o,
1090 const struct object_id *a,
1091 const struct object_id *b,
1092 struct object_id *result)
1094 struct commit *commit_o, *commit_a, *commit_b;
1096 struct object_array merges;
1097 struct strbuf sb = STRBUF_INIT;
1100 int search = !opt->priv->call_depth;
1102 /* store fallback answer in result in case we fail */
1103 oidcpy(result, opt->priv->call_depth ? o : a);
1105 /* we can not handle deletion conflicts */
1113 if (add_submodule_odb(path)) {
1114 path_msg(opt, path, 0,
1115 _("Failed to merge submodule %s (not checked out)"),
1120 if (!(commit_o = lookup_commit_reference(opt->repo, o)) ||
1121 !(commit_a = lookup_commit_reference(opt->repo, a)) ||
1122 !(commit_b = lookup_commit_reference(opt->repo, b))) {
1123 path_msg(opt, path, 0,
1124 _("Failed to merge submodule %s (commits not present)"),
1129 /* check whether both changes are forward */
1130 if (!in_merge_bases(commit_o, commit_a) ||
1131 !in_merge_bases(commit_o, commit_b)) {
1132 path_msg(opt, path, 0,
1133 _("Failed to merge submodule %s "
1134 "(commits don't follow merge-base)"),
1139 /* Case #1: a is contained in b or vice versa */
1140 if (in_merge_bases(commit_a, commit_b)) {
1142 path_msg(opt, path, 1,
1143 _("Note: Fast-forwarding submodule %s to %s"),
1144 path, oid_to_hex(b));
1147 if (in_merge_bases(commit_b, commit_a)) {
1149 path_msg(opt, path, 1,
1150 _("Note: Fast-forwarding submodule %s to %s"),
1151 path, oid_to_hex(a));
1156 * Case #2: There are one or more merges that contain a and b in
1157 * the submodule. If there is only one, then present it as a
1158 * suggestion to the user, but leave it marked unmerged so the
1159 * user needs to confirm the resolution.
1162 /* Skip the search if makes no sense to the calling context. */
1166 /* find commit which merges them */
1167 parent_count = find_first_merges(opt->repo, path, commit_a, commit_b,
1169 switch (parent_count) {
1171 path_msg(opt, path, 0, _("Failed to merge submodule %s"), path);
1175 format_commit(&sb, 4,
1176 (struct commit *)merges.objects[0].item);
1177 path_msg(opt, path, 0,
1178 _("Failed to merge submodule %s, but a possible merge "
1179 "resolution exists:\n%s\n"),
1181 path_msg(opt, path, 1,
1182 _("If this is correct simply add it to the index "
1185 " git update-index --cacheinfo 160000 %s \"%s\"\n\n"
1186 "which will accept this suggestion.\n"),
1187 oid_to_hex(&merges.objects[0].item->oid), path);
1188 strbuf_release(&sb);
1191 for (i = 0; i < merges.nr; i++)
1192 format_commit(&sb, 4,
1193 (struct commit *)merges.objects[i].item);
1194 path_msg(opt, path, 0,
1195 _("Failed to merge submodule %s, but multiple "
1196 "possible merges exist:\n%s"), path, sb.buf);
1197 strbuf_release(&sb);
1200 object_array_clear(&merges);
1204 static void initialize_attr_index(struct merge_options *opt)
1207 * The renormalize_buffer() functions require attributes, and
1208 * annoyingly those can only be read from the working tree or from
1209 * an index_state. merge-ort doesn't have an index_state, so we
1210 * generate a fake one containing only attribute information.
1212 struct merged_info *mi;
1213 struct index_state *attr_index = &opt->priv->attr_index;
1214 struct cache_entry *ce;
1216 attr_index->initialized = 1;
1218 if (!opt->renormalize)
1221 mi = strmap_get(&opt->priv->paths, GITATTRIBUTES_FILE);
1226 int len = strlen(GITATTRIBUTES_FILE);
1227 ce = make_empty_cache_entry(attr_index, len);
1228 ce->ce_mode = create_ce_mode(mi->result.mode);
1229 ce->ce_flags = create_ce_flags(0);
1230 ce->ce_namelen = len;
1231 oidcpy(&ce->oid, &mi->result.oid);
1232 memcpy(ce->name, GITATTRIBUTES_FILE, len);
1233 add_index_entry(attr_index, ce,
1234 ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
1235 get_stream_filter(attr_index, GITATTRIBUTES_FILE, &ce->oid);
1238 struct conflict_info *ci;
1240 ASSIGN_AND_VERIFY_CI(ci, mi);
1241 for (stage = 0; stage < 3; stage++) {
1242 unsigned stage_mask = (1 << stage);
1244 if (!(ci->filemask & stage_mask))
1246 len = strlen(GITATTRIBUTES_FILE);
1247 ce = make_empty_cache_entry(attr_index, len);
1248 ce->ce_mode = create_ce_mode(ci->stages[stage].mode);
1249 ce->ce_flags = create_ce_flags(stage);
1250 ce->ce_namelen = len;
1251 oidcpy(&ce->oid, &ci->stages[stage].oid);
1252 memcpy(ce->name, GITATTRIBUTES_FILE, len);
1253 add_index_entry(attr_index, ce,
1254 ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
1255 get_stream_filter(attr_index, GITATTRIBUTES_FILE,
1261 static int merge_3way(struct merge_options *opt,
1263 const struct object_id *o,
1264 const struct object_id *a,
1265 const struct object_id *b,
1266 const char *pathnames[3],
1267 const int extra_marker_size,
1268 mmbuffer_t *result_buf)
1270 mmfile_t orig, src1, src2;
1271 struct ll_merge_options ll_opts = {0};
1272 char *base, *name1, *name2;
1275 if (!opt->priv->attr_index.initialized)
1276 initialize_attr_index(opt);
1278 ll_opts.renormalize = opt->renormalize;
1279 ll_opts.extra_marker_size = extra_marker_size;
1280 ll_opts.xdl_opts = opt->xdl_opts;
1282 if (opt->priv->call_depth) {
1283 ll_opts.virtual_ancestor = 1;
1284 ll_opts.variant = 0;
1286 switch (opt->recursive_variant) {
1287 case MERGE_VARIANT_OURS:
1288 ll_opts.variant = XDL_MERGE_FAVOR_OURS;
1290 case MERGE_VARIANT_THEIRS:
1291 ll_opts.variant = XDL_MERGE_FAVOR_THEIRS;
1294 ll_opts.variant = 0;
1299 assert(pathnames[0] && pathnames[1] && pathnames[2] && opt->ancestor);
1300 if (pathnames[0] == pathnames[1] && pathnames[1] == pathnames[2]) {
1301 base = mkpathdup("%s", opt->ancestor);
1302 name1 = mkpathdup("%s", opt->branch1);
1303 name2 = mkpathdup("%s", opt->branch2);
1305 base = mkpathdup("%s:%s", opt->ancestor, pathnames[0]);
1306 name1 = mkpathdup("%s:%s", opt->branch1, pathnames[1]);
1307 name2 = mkpathdup("%s:%s", opt->branch2, pathnames[2]);
1310 read_mmblob(&orig, o);
1311 read_mmblob(&src1, a);
1312 read_mmblob(&src2, b);
1314 merge_status = ll_merge(result_buf, path, &orig, base,
1315 &src1, name1, &src2, name2,
1316 &opt->priv->attr_index, &ll_opts);
1324 return merge_status;
1327 static int handle_content_merge(struct merge_options *opt,
1329 const struct version_info *o,
1330 const struct version_info *a,
1331 const struct version_info *b,
1332 const char *pathnames[3],
1333 const int extra_marker_size,
1334 struct version_info *result)
1337 * path is the target location where we want to put the file, and
1338 * is used to determine any normalization rules in ll_merge.
1340 * The normal case is that path and all entries in pathnames are
1341 * identical, though renames can affect which path we got one of
1342 * the three blobs to merge on various sides of history.
1344 * extra_marker_size is the amount to extend conflict markers in
1345 * ll_merge; this is neeed if we have content merges of content
1346 * merges, which happens for example with rename/rename(2to1) and
1347 * rename/add conflicts.
1352 * handle_content_merge() needs both files to be of the same type, i.e.
1353 * both files OR both submodules OR both symlinks. Conflicting types
1354 * needs to be handled elsewhere.
1356 assert((S_IFMT & a->mode) == (S_IFMT & b->mode));
1359 if (a->mode == b->mode || a->mode == o->mode)
1360 result->mode = b->mode;
1362 /* must be the 100644/100755 case */
1363 assert(S_ISREG(a->mode));
1364 result->mode = a->mode;
1365 clean = (b->mode == o->mode);
1367 * FIXME: If opt->priv->call_depth && !clean, then we really
1368 * should not make result->mode match either a->mode or
1369 * b->mode; that causes t6036 "check conflicting mode for
1370 * regular file" to fail. It would be best to use some other
1371 * mode, but we'll confuse all kinds of stuff if we use one
1372 * where S_ISREG(result->mode) isn't true, and if we use
1373 * something like 0100666, then tree-walk.c's calls to
1374 * canon_mode() will just normalize that to 100644 for us and
1375 * thus not solve anything.
1377 * Figure out if there's some kind of way we can work around
1383 * Trivial oid merge.
1385 * Note: While one might assume that the next four lines would
1386 * be unnecessary due to the fact that match_mask is often
1387 * setup and already handled, renames don't always take care
1390 if (oideq(&a->oid, &b->oid) || oideq(&a->oid, &o->oid))
1391 oidcpy(&result->oid, &b->oid);
1392 else if (oideq(&b->oid, &o->oid))
1393 oidcpy(&result->oid, &a->oid);
1395 /* Remaining rules depend on file vs. submodule vs. symlink. */
1396 else if (S_ISREG(a->mode)) {
1397 mmbuffer_t result_buf;
1398 int ret = 0, merge_status;
1402 * If 'o' is different type, treat it as null so we do a
1405 two_way = ((S_IFMT & o->mode) != (S_IFMT & a->mode));
1407 merge_status = merge_3way(opt, path,
1408 two_way ? &null_oid : &o->oid,
1410 pathnames, extra_marker_size,
1413 if ((merge_status < 0) || !result_buf.ptr)
1414 ret = err(opt, _("Failed to execute internal merge"));
1417 write_object_file(result_buf.ptr, result_buf.size,
1418 blob_type, &result->oid))
1419 ret = err(opt, _("Unable to add %s to database"),
1422 free(result_buf.ptr);
1425 clean &= (merge_status == 0);
1426 path_msg(opt, path, 1, _("Auto-merging %s"), path);
1427 } else if (S_ISGITLINK(a->mode)) {
1428 int two_way = ((S_IFMT & o->mode) != (S_IFMT & a->mode));
1429 clean = merge_submodule(opt, pathnames[0],
1430 two_way ? &null_oid : &o->oid,
1431 &a->oid, &b->oid, &result->oid);
1432 if (opt->priv->call_depth && two_way && !clean) {
1433 result->mode = o->mode;
1434 oidcpy(&result->oid, &o->oid);
1436 } else if (S_ISLNK(a->mode)) {
1437 if (opt->priv->call_depth) {
1439 result->mode = o->mode;
1440 oidcpy(&result->oid, &o->oid);
1442 switch (opt->recursive_variant) {
1443 case MERGE_VARIANT_NORMAL:
1445 oidcpy(&result->oid, &a->oid);
1447 case MERGE_VARIANT_OURS:
1448 oidcpy(&result->oid, &a->oid);
1450 case MERGE_VARIANT_THEIRS:
1451 oidcpy(&result->oid, &b->oid);
1456 BUG("unsupported object type in the tree: %06o for %s",
1462 /*** Function Grouping: functions related to detect_and_process_renames(), ***
1463 *** which are split into directory and regular rename detection sections. ***/
1465 /*** Function Grouping: functions related to directory rename detection ***/
1467 struct collision_info {
1468 struct string_list source_files;
1469 unsigned reported_already:1;
1473 * Return a new string that replaces the beginning portion (which matches
1474 * rename_info->key), with rename_info->util.new_dir. In perl-speak:
1475 * new_path_name = (old_path =~ s/rename_info->key/rename_info->value/);
1477 * Caller must ensure that old_path starts with rename_info->key + '/'.
1479 static char *apply_dir_rename(struct strmap_entry *rename_info,
1480 const char *old_path)
1482 struct strbuf new_path = STRBUF_INIT;
1483 const char *old_dir = rename_info->key;
1484 const char *new_dir = rename_info->value;
1485 int oldlen, newlen, new_dir_len;
1487 oldlen = strlen(old_dir);
1488 if (*new_dir == '\0')
1490 * If someone renamed/merged a subdirectory into the root
1491 * directory (e.g. 'some/subdir' -> ''), then we want to
1494 * as the rename; we need to make old_path + oldlen advance
1495 * past the '/' character.
1498 new_dir_len = strlen(new_dir);
1499 newlen = new_dir_len + (strlen(old_path) - oldlen) + 1;
1500 strbuf_grow(&new_path, newlen);
1501 strbuf_add(&new_path, new_dir, new_dir_len);
1502 strbuf_addstr(&new_path, &old_path[oldlen]);
1504 return strbuf_detach(&new_path, NULL);
1507 static int path_in_way(struct strmap *paths, const char *path, unsigned side_mask)
1509 struct merged_info *mi = strmap_get(paths, path);
1510 struct conflict_info *ci;
1513 INITIALIZE_CI(ci, mi);
1514 return mi->clean || (side_mask & (ci->filemask | ci->dirmask));
1518 * See if there is a directory rename for path, and if there are any file
1519 * level conflicts on the given side for the renamed location. If there is
1520 * a rename and there are no conflicts, return the new name. Otherwise,
1523 static char *handle_path_level_conflicts(struct merge_options *opt,
1525 unsigned side_index,
1526 struct strmap_entry *rename_info,
1527 struct strmap *collisions)
1529 char *new_path = NULL;
1530 struct collision_info *c_info;
1532 struct strbuf collision_paths = STRBUF_INIT;
1535 * entry has the mapping of old directory name to new directory name
1536 * that we want to apply to path.
1538 new_path = apply_dir_rename(rename_info, path);
1540 BUG("Failed to apply directory rename!");
1543 * The caller needs to have ensured that it has pre-populated
1544 * collisions with all paths that map to new_path. Do a quick check
1545 * to ensure that's the case.
1547 c_info = strmap_get(collisions, new_path);
1549 BUG("c_info is NULL");
1552 * Check for one-sided add/add/.../add conflicts, i.e.
1553 * where implicit renames from the other side doing
1554 * directory rename(s) can affect this side of history
1555 * to put multiple paths into the same location. Warn
1556 * and bail on directory renames for such paths.
1558 if (c_info->reported_already) {
1560 } else if (path_in_way(&opt->priv->paths, new_path, 1 << side_index)) {
1561 c_info->reported_already = 1;
1562 strbuf_add_separated_string_list(&collision_paths, ", ",
1563 &c_info->source_files);
1564 path_msg(opt, new_path, 0,
1565 _("CONFLICT (implicit dir rename): Existing file/dir "
1566 "at %s in the way of implicit directory rename(s) "
1567 "putting the following path(s) there: %s."),
1568 new_path, collision_paths.buf);
1570 } else if (c_info->source_files.nr > 1) {
1571 c_info->reported_already = 1;
1572 strbuf_add_separated_string_list(&collision_paths, ", ",
1573 &c_info->source_files);
1574 path_msg(opt, new_path, 0,
1575 _("CONFLICT (implicit dir rename): Cannot map more "
1576 "than one path to %s; implicit directory renames "
1577 "tried to put these paths there: %s"),
1578 new_path, collision_paths.buf);
1582 /* Free memory we no longer need */
1583 strbuf_release(&collision_paths);
1584 if (!clean && new_path) {
1592 static void get_provisional_directory_renames(struct merge_options *opt,
1596 struct hashmap_iter iter;
1597 struct strmap_entry *entry;
1598 struct rename_info *renames = &opt->priv->renames;
1602 * dir_rename_count: old_directory -> {new_directory -> count}
1604 * dir_renames: old_directory -> best_new_directory
1605 * where best_new_directory is the one with the unique highest count.
1607 strmap_for_each_entry(&renames->dir_rename_count[side], &iter, entry) {
1608 const char *source_dir = entry->key;
1609 struct strintmap *counts = entry->value;
1610 struct hashmap_iter count_iter;
1611 struct strmap_entry *count_entry;
1614 const char *best = NULL;
1616 strintmap_for_each_entry(counts, &count_iter, count_entry) {
1617 const char *target_dir = count_entry->key;
1618 intptr_t count = (intptr_t)count_entry->value;
1622 else if (count > max) {
1631 if (bad_max == max) {
1632 path_msg(opt, source_dir, 0,
1633 _("CONFLICT (directory rename split): "
1634 "Unclear where to rename %s to; it was "
1635 "renamed to multiple other directories, with "
1636 "no destination getting a majority of the "
1640 * We should mark this as unclean IF something attempts
1641 * to use this rename. We do not yet have the logic
1642 * in place to detect if this directory rename is being
1643 * used, and optimizations that reduce the number of
1644 * renames cause this to falsely trigger. For now,
1645 * just disable it, causing t6423 testcase 2a to break.
1646 * We'll later fix the detection, and when we do we
1647 * will re-enable setting *clean to 0 (and thereby fix
1648 * t6423 testcase 2a).
1652 strmap_put(&renames->dir_renames[side],
1653 source_dir, (void*)best);
1658 static void handle_directory_level_conflicts(struct merge_options *opt)
1660 struct hashmap_iter iter;
1661 struct strmap_entry *entry;
1662 struct string_list duplicated = STRING_LIST_INIT_NODUP;
1663 struct rename_info *renames = &opt->priv->renames;
1664 struct strmap *side1_dir_renames = &renames->dir_renames[MERGE_SIDE1];
1665 struct strmap *side2_dir_renames = &renames->dir_renames[MERGE_SIDE2];
1668 strmap_for_each_entry(side1_dir_renames, &iter, entry) {
1669 if (strmap_contains(side2_dir_renames, entry->key))
1670 string_list_append(&duplicated, entry->key);
1673 for (i = 0; i < duplicated.nr; i++) {
1674 strmap_remove(side1_dir_renames, duplicated.items[i].string, 0);
1675 strmap_remove(side2_dir_renames, duplicated.items[i].string, 0);
1677 string_list_clear(&duplicated, 0);
1680 static struct strmap_entry *check_dir_renamed(const char *path,
1681 struct strmap *dir_renames)
1683 char *temp = xstrdup(path);
1685 struct strmap_entry *e = NULL;
1687 while ((end = strrchr(temp, '/'))) {
1689 e = strmap_get_entry(dir_renames, temp);
1697 static void compute_collisions(struct strmap *collisions,
1698 struct strmap *dir_renames,
1699 struct diff_queue_struct *pairs)
1703 strmap_init_with_options(collisions, NULL, 0);
1704 if (strmap_empty(dir_renames))
1708 * Multiple files can be mapped to the same path due to directory
1709 * renames done by the other side of history. Since that other
1710 * side of history could have merged multiple directories into one,
1711 * if our side of history added the same file basename to each of
1712 * those directories, then all N of them would get implicitly
1713 * renamed by the directory rename detection into the same path,
1714 * and we'd get an add/add/.../add conflict, and all those adds
1715 * from *this* side of history. This is not representable in the
1716 * index, and users aren't going to easily be able to make sense of
1717 * it. So we need to provide a good warning about what's
1718 * happening, and fall back to no-directory-rename detection
1719 * behavior for those paths.
1721 * See testcases 9e and all of section 5 from t6043 for examples.
1723 for (i = 0; i < pairs->nr; ++i) {
1724 struct strmap_entry *rename_info;
1725 struct collision_info *collision_info;
1727 struct diff_filepair *pair = pairs->queue[i];
1729 if (pair->status != 'A' && pair->status != 'R')
1731 rename_info = check_dir_renamed(pair->two->path, dir_renames);
1735 new_path = apply_dir_rename(rename_info, pair->two->path);
1737 collision_info = strmap_get(collisions, new_path);
1738 if (collision_info) {
1741 collision_info = xcalloc(1,
1742 sizeof(struct collision_info));
1743 string_list_init(&collision_info->source_files, 0);
1744 strmap_put(collisions, new_path, collision_info);
1746 string_list_insert(&collision_info->source_files,
1751 static char *check_for_directory_rename(struct merge_options *opt,
1753 unsigned side_index,
1754 struct strmap *dir_renames,
1755 struct strmap *dir_rename_exclusions,
1756 struct strmap *collisions,
1759 char *new_path = NULL;
1760 struct strmap_entry *rename_info;
1761 struct strmap_entry *otherinfo = NULL;
1762 const char *new_dir;
1764 if (strmap_empty(dir_renames))
1766 rename_info = check_dir_renamed(path, dir_renames);
1769 /* old_dir = rename_info->key; */
1770 new_dir = rename_info->value;
1773 * This next part is a little weird. We do not want to do an
1774 * implicit rename into a directory we renamed on our side, because
1775 * that will result in a spurious rename/rename(1to2) conflict. An
1777 * Base commit: dumbdir/afile, otherdir/bfile
1778 * Side 1: smrtdir/afile, otherdir/bfile
1779 * Side 2: dumbdir/afile, dumbdir/bfile
1780 * Here, while working on Side 1, we could notice that otherdir was
1781 * renamed/merged to dumbdir, and change the diff_filepair for
1782 * otherdir/bfile into a rename into dumbdir/bfile. However, Side
1783 * 2 will notice the rename from dumbdir to smrtdir, and do the
1784 * transitive rename to move it from dumbdir/bfile to
1785 * smrtdir/bfile. That gives us bfile in dumbdir vs being in
1786 * smrtdir, a rename/rename(1to2) conflict. We really just want
1787 * the file to end up in smrtdir. And the way to achieve that is
1788 * to not let Side1 do the rename to dumbdir, since we know that is
1789 * the source of one of our directory renames.
1791 * That's why otherinfo and dir_rename_exclusions is here.
1793 * As it turns out, this also prevents N-way transient rename
1794 * confusion; See testcases 9c and 9d of t6043.
1796 otherinfo = strmap_get_entry(dir_rename_exclusions, new_dir);
1798 path_msg(opt, rename_info->key, 1,
1799 _("WARNING: Avoiding applying %s -> %s rename "
1800 "to %s, because %s itself was renamed."),
1801 rename_info->key, new_dir, path, new_dir);
1805 new_path = handle_path_level_conflicts(opt, path, side_index,
1806 rename_info, collisions);
1807 *clean_merge &= (new_path != NULL);
1812 static void apply_directory_rename_modifications(struct merge_options *opt,
1813 struct diff_filepair *pair,
1817 * The basic idea is to get the conflict_info from opt->priv->paths
1818 * at old path, and insert it into new_path; basically just this:
1819 * ci = strmap_get(&opt->priv->paths, old_path);
1820 * strmap_remove(&opt->priv->paths, old_path, 0);
1821 * strmap_put(&opt->priv->paths, new_path, ci);
1822 * However, there are some factors complicating this:
1823 * - opt->priv->paths may already have an entry at new_path
1824 * - Each ci tracks its containing directory, so we need to
1826 * - If another ci has the same containing directory, then
1827 * the two char*'s MUST point to the same location. See the
1828 * comment in struct merged_info. strcmp equality is not
1829 * enough; we need pointer equality.
1830 * - opt->priv->paths must hold the parent directories of any
1831 * entries that are added. So, if this directory rename
1832 * causes entirely new directories, we must recursively add
1833 * parent directories.
1834 * - For each parent directory added to opt->priv->paths, we
1835 * also need to get its parent directory stored in its
1836 * conflict_info->merged.directory_name with all the same
1837 * requirements about pointer equality.
1839 struct string_list dirs_to_insert = STRING_LIST_INIT_NODUP;
1840 struct conflict_info *ci, *new_ci;
1841 struct strmap_entry *entry;
1842 const char *branch_with_new_path, *branch_with_dir_rename;
1843 const char *old_path = pair->two->path;
1844 const char *parent_name;
1845 const char *cur_path;
1848 entry = strmap_get_entry(&opt->priv->paths, old_path);
1849 old_path = entry->key;
1853 /* Find parent directories missing from opt->priv->paths */
1854 cur_path = new_path;
1856 /* Find the parent directory of cur_path */
1857 char *last_slash = strrchr(cur_path, '/');
1859 parent_name = xstrndup(cur_path, last_slash - cur_path);
1861 parent_name = opt->priv->toplevel_dir;
1865 /* Look it up in opt->priv->paths */
1866 entry = strmap_get_entry(&opt->priv->paths, parent_name);
1868 free((char*)parent_name);
1869 parent_name = entry->key; /* reuse known pointer */
1873 /* Record this is one of the directories we need to insert */
1874 string_list_append(&dirs_to_insert, parent_name);
1875 cur_path = parent_name;
1878 /* Traverse dirs_to_insert and insert them into opt->priv->paths */
1879 for (i = dirs_to_insert.nr-1; i >= 0; --i) {
1880 struct conflict_info *dir_ci;
1881 char *cur_dir = dirs_to_insert.items[i].string;
1883 dir_ci = xcalloc(1, sizeof(*dir_ci));
1885 dir_ci->merged.directory_name = parent_name;
1886 len = strlen(parent_name);
1887 /* len+1 because of trailing '/' character */
1888 dir_ci->merged.basename_offset = (len > 0 ? len+1 : len);
1889 dir_ci->dirmask = ci->filemask;
1890 strmap_put(&opt->priv->paths, cur_dir, dir_ci);
1892 parent_name = cur_dir;
1896 * We are removing old_path from opt->priv->paths. old_path also will
1897 * eventually need to be freed, but it may still be used by e.g.
1898 * ci->pathnames. So, store it in another string-list for now.
1900 string_list_append(&opt->priv->paths_to_free, old_path);
1902 assert(ci->filemask == 2 || ci->filemask == 4);
1903 assert(ci->dirmask == 0);
1904 strmap_remove(&opt->priv->paths, old_path, 0);
1906 branch_with_new_path = (ci->filemask == 2) ? opt->branch1 : opt->branch2;
1907 branch_with_dir_rename = (ci->filemask == 2) ? opt->branch2 : opt->branch1;
1909 /* Now, finally update ci and stick it into opt->priv->paths */
1910 ci->merged.directory_name = parent_name;
1911 len = strlen(parent_name);
1912 ci->merged.basename_offset = (len > 0 ? len+1 : len);
1913 new_ci = strmap_get(&opt->priv->paths, new_path);
1915 /* Place ci back into opt->priv->paths, but at new_path */
1916 strmap_put(&opt->priv->paths, new_path, ci);
1920 /* A few sanity checks */
1922 assert(ci->filemask == 2 || ci->filemask == 4);
1923 assert((new_ci->filemask & ci->filemask) == 0);
1924 assert(!new_ci->merged.clean);
1926 /* Copy stuff from ci into new_ci */
1927 new_ci->filemask |= ci->filemask;
1928 if (new_ci->dirmask)
1929 new_ci->df_conflict = 1;
1930 index = (ci->filemask >> 1);
1931 new_ci->pathnames[index] = ci->pathnames[index];
1932 new_ci->stages[index].mode = ci->stages[index].mode;
1933 oidcpy(&new_ci->stages[index].oid, &ci->stages[index].oid);
1939 if (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE) {
1940 /* Notify user of updated path */
1941 if (pair->status == 'A')
1942 path_msg(opt, new_path, 1,
1943 _("Path updated: %s added in %s inside a "
1944 "directory that was renamed in %s; moving "
1946 old_path, branch_with_new_path,
1947 branch_with_dir_rename, new_path);
1949 path_msg(opt, new_path, 1,
1950 _("Path updated: %s renamed to %s in %s, "
1951 "inside a directory that was renamed in %s; "
1952 "moving it to %s."),
1953 pair->one->path, old_path, branch_with_new_path,
1954 branch_with_dir_rename, new_path);
1957 * opt->detect_directory_renames has the value
1958 * MERGE_DIRECTORY_RENAMES_CONFLICT, so mark these as conflicts.
1960 ci->path_conflict = 1;
1961 if (pair->status == 'A')
1962 path_msg(opt, new_path, 0,
1963 _("CONFLICT (file location): %s added in %s "
1964 "inside a directory that was renamed in %s, "
1965 "suggesting it should perhaps be moved to "
1967 old_path, branch_with_new_path,
1968 branch_with_dir_rename, new_path);
1970 path_msg(opt, new_path, 0,
1971 _("CONFLICT (file location): %s renamed to %s "
1972 "in %s, inside a directory that was renamed "
1973 "in %s, suggesting it should perhaps be "
1975 pair->one->path, old_path, branch_with_new_path,
1976 branch_with_dir_rename, new_path);
1980 * Finally, record the new location.
1982 pair->two->path = new_path;
1985 /*** Function Grouping: functions related to regular rename detection ***/
1987 static int process_renames(struct merge_options *opt,
1988 struct diff_queue_struct *renames)
1990 int clean_merge = 1, i;
1992 for (i = 0; i < renames->nr; ++i) {
1993 const char *oldpath = NULL, *newpath;
1994 struct diff_filepair *pair = renames->queue[i];
1995 struct conflict_info *oldinfo = NULL, *newinfo = NULL;
1996 struct strmap_entry *old_ent, *new_ent;
1997 unsigned int old_sidemask;
1998 int target_index, other_source_index;
1999 int source_deleted, collision, type_changed;
2000 const char *rename_branch = NULL, *delete_branch = NULL;
2002 old_ent = strmap_get_entry(&opt->priv->paths, pair->one->path);
2003 new_ent = strmap_get_entry(&opt->priv->paths, pair->two->path);
2005 oldpath = old_ent->key;
2006 oldinfo = old_ent->value;
2008 newpath = pair->two->path;
2010 newpath = new_ent->key;
2011 newinfo = new_ent->value;
2015 * If pair->one->path isn't in opt->priv->paths, that means
2016 * that either directory rename detection removed that
2017 * path, or a parent directory of oldpath was resolved and
2018 * we don't even need the rename; in either case, we can
2019 * skip it. If oldinfo->merged.clean, then the other side
2020 * of history had no changes to oldpath and we don't need
2021 * the rename and can skip it.
2023 if (!oldinfo || oldinfo->merged.clean)
2027 * diff_filepairs have copies of pathnames, thus we have to
2028 * use standard 'strcmp()' (negated) instead of '=='.
2030 if (i + 1 < renames->nr &&
2031 !strcmp(oldpath, renames->queue[i+1]->one->path)) {
2032 /* Handle rename/rename(1to2) or rename/rename(1to1) */
2033 const char *pathnames[3];
2034 struct version_info merged;
2035 struct conflict_info *base, *side1, *side2;
2036 unsigned was_binary_blob = 0;
2038 pathnames[0] = oldpath;
2039 pathnames[1] = newpath;
2040 pathnames[2] = renames->queue[i+1]->two->path;
2042 base = strmap_get(&opt->priv->paths, pathnames[0]);
2043 side1 = strmap_get(&opt->priv->paths, pathnames[1]);
2044 side2 = strmap_get(&opt->priv->paths, pathnames[2]);
2050 if (!strcmp(pathnames[1], pathnames[2])) {
2051 /* Both sides renamed the same way */
2052 assert(side1 == side2);
2053 memcpy(&side1->stages[0], &base->stages[0],
2055 side1->filemask |= (1 << MERGE_BASE);
2056 /* Mark base as resolved by removal */
2057 base->merged.is_null = 1;
2058 base->merged.clean = 1;
2060 /* We handled both renames, i.e. i+1 handled */
2062 /* Move to next rename */
2066 /* This is a rename/rename(1to2) */
2067 clean_merge = handle_content_merge(opt,
2073 1 + 2 * opt->priv->call_depth,
2076 merged.mode == side1->stages[1].mode &&
2077 oideq(&merged.oid, &side1->stages[1].oid))
2078 was_binary_blob = 1;
2079 memcpy(&side1->stages[1], &merged, sizeof(merged));
2080 if (was_binary_blob) {
2082 * Getting here means we were attempting to
2083 * merge a binary blob.
2085 * Since we can't merge binaries,
2086 * handle_content_merge() just takes one
2087 * side. But we don't want to copy the
2088 * contents of one side to both paths. We
2089 * used the contents of side1 above for
2090 * side1->stages, let's use the contents of
2091 * side2 for side2->stages below.
2093 oidcpy(&merged.oid, &side2->stages[2].oid);
2094 merged.mode = side2->stages[2].mode;
2096 memcpy(&side2->stages[2], &merged, sizeof(merged));
2098 side1->path_conflict = 1;
2099 side2->path_conflict = 1;
2101 * TODO: For renames we normally remove the path at the
2102 * old name. It would thus seem consistent to do the
2103 * same for rename/rename(1to2) cases, but we haven't
2104 * done so traditionally and a number of the regression
2105 * tests now encode an expectation that the file is
2106 * left there at stage 1. If we ever decide to change
2107 * this, add the following two lines here:
2108 * base->merged.is_null = 1;
2109 * base->merged.clean = 1;
2110 * and remove the setting of base->path_conflict to 1.
2112 base->path_conflict = 1;
2113 path_msg(opt, oldpath, 0,
2114 _("CONFLICT (rename/rename): %s renamed to "
2115 "%s in %s and to %s in %s."),
2117 pathnames[1], opt->branch1,
2118 pathnames[2], opt->branch2);
2120 i++; /* We handled both renames, i.e. i+1 handled */
2126 target_index = pair->score; /* from collect_renames() */
2127 assert(target_index == 1 || target_index == 2);
2128 other_source_index = 3 - target_index;
2129 old_sidemask = (1 << other_source_index); /* 2 or 4 */
2130 source_deleted = (oldinfo->filemask == 1);
2131 collision = ((newinfo->filemask & old_sidemask) != 0);
2132 type_changed = !source_deleted &&
2133 (S_ISREG(oldinfo->stages[other_source_index].mode) !=
2134 S_ISREG(newinfo->stages[target_index].mode));
2135 if (type_changed && collision) {
2137 * special handling so later blocks can handle this...
2139 * if type_changed && collision are both true, then this
2140 * was really a double rename, but one side wasn't
2141 * detected due to lack of break detection. I.e.
2143 * orig: has normal file 'foo'
2144 * side1: renames 'foo' to 'bar', adds 'foo' symlink
2145 * side2: renames 'foo' to 'bar'
2146 * In this case, the foo->bar rename on side1 won't be
2147 * detected because the new symlink named 'foo' is
2148 * there and we don't do break detection. But we detect
2149 * this here because we don't want to merge the content
2150 * of the foo symlink with the foo->bar file, so we
2151 * have some logic to handle this special case. The
2152 * easiest way to do that is make 'bar' on side1 not
2153 * be considered a colliding file but the other part
2154 * of a normal rename. If the file is very different,
2155 * well we're going to get content merge conflicts
2156 * anyway so it doesn't hurt. And if the colliding
2157 * file also has a different type, that'll be handled
2158 * by the content merge logic in process_entry() too.
2160 * See also t6430, 'rename vs. rename/symlink'
2164 if (source_deleted) {
2165 if (target_index == 1) {
2166 rename_branch = opt->branch1;
2167 delete_branch = opt->branch2;
2169 rename_branch = opt->branch2;
2170 delete_branch = opt->branch1;
2174 assert(source_deleted || oldinfo->filemask & old_sidemask);
2176 /* Need to check for special types of rename conflicts... */
2177 if (collision && !source_deleted) {
2178 /* collision: rename/add or rename/rename(2to1) */
2179 const char *pathnames[3];
2180 struct version_info merged;
2182 struct conflict_info *base, *side1, *side2;
2185 pathnames[0] = oldpath;
2186 pathnames[other_source_index] = oldpath;
2187 pathnames[target_index] = newpath;
2189 base = strmap_get(&opt->priv->paths, pathnames[0]);
2190 side1 = strmap_get(&opt->priv->paths, pathnames[1]);
2191 side2 = strmap_get(&opt->priv->paths, pathnames[2]);
2197 clean = handle_content_merge(opt, pair->one->path,
2202 1 + 2 * opt->priv->call_depth,
2205 memcpy(&newinfo->stages[target_index], &merged,
2208 path_msg(opt, newpath, 0,
2209 _("CONFLICT (rename involved in "
2210 "collision): rename of %s -> %s has "
2211 "content conflicts AND collides "
2212 "with another path; this may result "
2213 "in nested conflict markers."),
2216 } else if (collision && source_deleted) {
2218 * rename/add/delete or rename/rename(2to1)/delete:
2219 * since oldpath was deleted on the side that didn't
2220 * do the rename, there's not much of a content merge
2221 * we can do for the rename. oldinfo->merged.is_null
2222 * was already set, so we just leave things as-is so
2223 * they look like an add/add conflict.
2226 newinfo->path_conflict = 1;
2227 path_msg(opt, newpath, 0,
2228 _("CONFLICT (rename/delete): %s renamed "
2229 "to %s in %s, but deleted in %s."),
2230 oldpath, newpath, rename_branch, delete_branch);
2233 * a few different cases...start by copying the
2234 * existing stage(s) from oldinfo over the newinfo
2235 * and update the pathname(s).
2237 memcpy(&newinfo->stages[0], &oldinfo->stages[0],
2238 sizeof(newinfo->stages[0]));
2239 newinfo->filemask |= (1 << MERGE_BASE);
2240 newinfo->pathnames[0] = oldpath;
2242 /* rename vs. typechange */
2243 /* Mark the original as resolved by removal */
2244 memcpy(&oldinfo->stages[0].oid, &null_oid,
2245 sizeof(oldinfo->stages[0].oid));
2246 oldinfo->stages[0].mode = 0;
2247 oldinfo->filemask &= 0x06;
2248 } else if (source_deleted) {
2250 newinfo->path_conflict = 1;
2251 path_msg(opt, newpath, 0,
2252 _("CONFLICT (rename/delete): %s renamed"
2253 " to %s in %s, but deleted in %s."),
2255 rename_branch, delete_branch);
2258 memcpy(&newinfo->stages[other_source_index],
2259 &oldinfo->stages[other_source_index],
2260 sizeof(newinfo->stages[0]));
2261 newinfo->filemask |= (1 << other_source_index);
2262 newinfo->pathnames[other_source_index] = oldpath;
2266 if (!type_changed) {
2267 /* Mark the original as resolved by removal */
2268 oldinfo->merged.is_null = 1;
2269 oldinfo->merged.clean = 1;
2277 static inline int possible_side_renames(struct rename_info *renames,
2278 unsigned side_index)
2280 return renames->pairs[side_index].nr > 0 &&
2281 !strintmap_empty(&renames->relevant_sources[side_index]);
2284 static inline int possible_renames(struct rename_info *renames)
2286 return possible_side_renames(renames, 1) ||
2287 possible_side_renames(renames, 2);
2290 static void resolve_diffpair_statuses(struct diff_queue_struct *q)
2293 * A simplified version of diff_resolve_rename_copy(); would probably
2294 * just use that function but it's static...
2297 struct diff_filepair *p;
2299 for (i = 0; i < q->nr; ++i) {
2301 p->status = 0; /* undecided */
2302 if (!DIFF_FILE_VALID(p->one))
2303 p->status = DIFF_STATUS_ADDED;
2304 else if (!DIFF_FILE_VALID(p->two))
2305 p->status = DIFF_STATUS_DELETED;
2306 else if (DIFF_PAIR_RENAME(p))
2307 p->status = DIFF_STATUS_RENAMED;
2311 static int compare_pairs(const void *a_, const void *b_)
2313 const struct diff_filepair *a = *((const struct diff_filepair **)a_);
2314 const struct diff_filepair *b = *((const struct diff_filepair **)b_);
2316 return strcmp(a->one->path, b->one->path);
2319 /* Call diffcore_rename() to compute which files have changed on given side */
2320 static void detect_regular_renames(struct merge_options *opt,
2321 unsigned side_index)
2323 struct diff_options diff_opts;
2324 struct rename_info *renames = &opt->priv->renames;
2326 if (!possible_side_renames(renames, side_index)) {
2328 * No rename detection needed for this side, but we still need
2329 * to make sure 'adds' are marked correctly in case the other
2330 * side had directory renames.
2332 resolve_diffpair_statuses(&renames->pairs[side_index]);
2336 repo_diff_setup(opt->repo, &diff_opts);
2337 diff_opts.flags.recursive = 1;
2338 diff_opts.flags.rename_empty = 0;
2339 diff_opts.detect_rename = DIFF_DETECT_RENAME;
2340 diff_opts.rename_limit = opt->rename_limit;
2341 if (opt->rename_limit <= 0)
2342 diff_opts.rename_limit = 1000;
2343 diff_opts.rename_score = opt->rename_score;
2344 diff_opts.show_rename_progress = opt->show_rename_progress;
2345 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
2346 diff_setup_done(&diff_opts);
2348 diff_queued_diff = renames->pairs[side_index];
2349 trace2_region_enter("diff", "diffcore_rename", opt->repo);
2350 diffcore_rename_extended(&diff_opts,
2351 &renames->relevant_sources[side_index],
2352 &renames->dirs_removed[side_index],
2353 &renames->dir_rename_count[side_index]);
2354 trace2_region_leave("diff", "diffcore_rename", opt->repo);
2355 resolve_diffpair_statuses(&diff_queued_diff);
2357 if (diff_opts.needed_rename_limit > renames->needed_limit)
2358 renames->needed_limit = diff_opts.needed_rename_limit;
2360 renames->pairs[side_index] = diff_queued_diff;
2362 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
2363 diff_queued_diff.nr = 0;
2364 diff_queued_diff.queue = NULL;
2365 diff_flush(&diff_opts);
2369 * Get information of all renames which occurred in 'side_pairs', discarding
2372 static int collect_renames(struct merge_options *opt,
2373 struct diff_queue_struct *result,
2374 unsigned side_index,
2375 struct strmap *dir_renames_for_side,
2376 struct strmap *rename_exclusions)
2379 struct strmap collisions;
2380 struct diff_queue_struct *side_pairs;
2381 struct hashmap_iter iter;
2382 struct strmap_entry *entry;
2383 struct rename_info *renames = &opt->priv->renames;
2385 side_pairs = &renames->pairs[side_index];
2386 compute_collisions(&collisions, dir_renames_for_side, side_pairs);
2388 for (i = 0; i < side_pairs->nr; ++i) {
2389 struct diff_filepair *p = side_pairs->queue[i];
2390 char *new_path; /* non-NULL only with directory renames */
2392 if (p->status != 'A' && p->status != 'R') {
2393 diff_free_filepair(p);
2397 new_path = check_for_directory_rename(opt, p->two->path,
2399 dir_renames_for_side,
2404 if (p->status != 'R' && !new_path) {
2405 diff_free_filepair(p);
2410 apply_directory_rename_modifications(opt, p, new_path);
2413 * p->score comes back from diffcore_rename_extended() with
2414 * the similarity of the renamed file. The similarity is
2415 * was used to determine that the two files were related
2416 * and are a rename, which we have already used, but beyond
2417 * that we have no use for the similarity. So p->score is
2418 * now irrelevant. However, process_renames() will need to
2419 * know which side of the merge this rename was associated
2420 * with, so overwrite p->score with that value.
2422 p->score = side_index;
2423 result->queue[result->nr++] = p;
2426 /* Free each value in the collisions map */
2427 strmap_for_each_entry(&collisions, &iter, entry) {
2428 struct collision_info *info = entry->value;
2429 string_list_clear(&info->source_files, 0);
2432 * In compute_collisions(), we set collisions.strdup_strings to 0
2433 * so that we wouldn't have to make another copy of the new_path
2434 * allocated by apply_dir_rename(). But now that we've used them
2435 * and have no other references to these strings, it is time to
2438 free_strmap_strings(&collisions);
2439 strmap_clear(&collisions, 1);
2443 static int detect_and_process_renames(struct merge_options *opt,
2444 struct tree *merge_base,
2448 struct diff_queue_struct combined;
2449 struct rename_info *renames = &opt->priv->renames;
2450 int need_dir_renames, s, clean = 1;
2452 memset(&combined, 0, sizeof(combined));
2453 if (!possible_renames(renames))
2456 trace2_region_enter("merge", "regular renames", opt->repo);
2457 detect_regular_renames(opt, MERGE_SIDE1);
2458 detect_regular_renames(opt, MERGE_SIDE2);
2459 trace2_region_leave("merge", "regular renames", opt->repo);
2461 trace2_region_enter("merge", "directory renames", opt->repo);
2463 !opt->priv->call_depth &&
2464 (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE ||
2465 opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_CONFLICT);
2467 if (need_dir_renames) {
2468 get_provisional_directory_renames(opt, MERGE_SIDE1, &clean);
2469 get_provisional_directory_renames(opt, MERGE_SIDE2, &clean);
2470 handle_directory_level_conflicts(opt);
2473 ALLOC_GROW(combined.queue,
2474 renames->pairs[1].nr + renames->pairs[2].nr,
2476 clean &= collect_renames(opt, &combined, MERGE_SIDE1,
2477 &renames->dir_renames[2],
2478 &renames->dir_renames[1]);
2479 clean &= collect_renames(opt, &combined, MERGE_SIDE2,
2480 &renames->dir_renames[1],
2481 &renames->dir_renames[2]);
2482 STABLE_QSORT(combined.queue, combined.nr, compare_pairs);
2483 trace2_region_leave("merge", "directory renames", opt->repo);
2485 trace2_region_enter("merge", "process renames", opt->repo);
2486 clean &= process_renames(opt, &combined);
2487 trace2_region_leave("merge", "process renames", opt->repo);
2489 goto simple_cleanup; /* collect_renames() handles some of cleanup */
2493 * Free now unneeded filepairs, which would have been handled
2494 * in collect_renames() normally but we skipped that code.
2496 for (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {
2497 struct diff_queue_struct *side_pairs;
2500 side_pairs = &renames->pairs[s];
2501 for (i = 0; i < side_pairs->nr; ++i) {
2502 struct diff_filepair *p = side_pairs->queue[i];
2503 diff_free_filepair(p);
2508 /* Free memory for renames->pairs[] and combined */
2509 for (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {
2510 free(renames->pairs[s].queue);
2511 DIFF_QUEUE_CLEAR(&renames->pairs[s]);
2515 for (i = 0; i < combined.nr; i++)
2516 diff_free_filepair(combined.queue[i]);
2517 free(combined.queue);
2523 /*** Function Grouping: functions related to process_entries() ***/
2525 static int string_list_df_name_compare(const char *one, const char *two)
2527 int onelen = strlen(one);
2528 int twolen = strlen(two);
2530 * Here we only care that entries for D/F conflicts are
2531 * adjacent, in particular with the file of the D/F conflict
2532 * appearing before files below the corresponding directory.
2533 * The order of the rest of the list is irrelevant for us.
2535 * To achieve this, we sort with df_name_compare and provide
2536 * the mode S_IFDIR so that D/F conflicts will sort correctly.
2537 * We use the mode S_IFDIR for everything else for simplicity,
2538 * since in other cases any changes in their order due to
2539 * sorting cause no problems for us.
2541 int cmp = df_name_compare(one, onelen, S_IFDIR,
2542 two, twolen, S_IFDIR);
2544 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
2545 * that 'foo' comes before 'foo/bar'.
2549 return onelen - twolen;
2552 struct directory_versions {
2554 * versions: list of (basename -> version_info)
2556 * The basenames are in reverse lexicographic order of full pathnames,
2557 * as processed in process_entries(). This puts all entries within
2558 * a directory together, and covers the directory itself after
2559 * everything within it, allowing us to write subtrees before needing
2560 * to record information for the tree itself.
2562 struct string_list versions;
2565 * offsets: list of (full relative path directories -> integer offsets)
2567 * Since versions contains basenames from files in multiple different
2568 * directories, we need to know which entries in versions correspond
2569 * to which directories. Values of e.g.
2573 * Would mean that entries 0-1 of versions are files in the toplevel
2574 * directory, entries 2-4 are files under src/, and the remaining
2575 * entries starting at index 5 are files under src/moduleA/.
2577 struct string_list offsets;
2580 * last_directory: directory that previously processed file found in
2582 * last_directory starts NULL, but records the directory in which the
2583 * previous file was found within. As soon as
2584 * directory(current_file) != last_directory
2585 * then we need to start updating accounting in versions & offsets.
2586 * Note that last_directory is always the last path in "offsets" (or
2587 * NULL if "offsets" is empty) so this exists just for quick access.
2589 const char *last_directory;
2591 /* last_directory_len: cached computation of strlen(last_directory) */
2592 unsigned last_directory_len;
2595 static int tree_entry_order(const void *a_, const void *b_)
2597 const struct string_list_item *a = a_;
2598 const struct string_list_item *b = b_;
2600 const struct merged_info *ami = a->util;
2601 const struct merged_info *bmi = b->util;
2602 return base_name_compare(a->string, strlen(a->string), ami->result.mode,
2603 b->string, strlen(b->string), bmi->result.mode);
2606 static void write_tree(struct object_id *result_oid,
2607 struct string_list *versions,
2608 unsigned int offset,
2611 size_t maxlen = 0, extra;
2612 unsigned int nr = versions->nr - offset;
2613 struct strbuf buf = STRBUF_INIT;
2614 struct string_list relevant_entries = STRING_LIST_INIT_NODUP;
2618 * We want to sort the last (versions->nr-offset) entries in versions.
2619 * Do so by abusing the string_list API a bit: make another string_list
2620 * that contains just those entries and then sort them.
2622 * We won't use relevant_entries again and will let it just pop off the
2623 * stack, so there won't be allocation worries or anything.
2625 relevant_entries.items = versions->items + offset;
2626 relevant_entries.nr = versions->nr - offset;
2627 /* No need for STABLE_QSORT -- filenames must be unique */
2628 QSORT(relevant_entries.items, relevant_entries.nr, tree_entry_order);
2630 /* Pre-allocate some space in buf */
2631 extra = hash_size + 8; /* 8: 6 for mode, 1 for space, 1 for NUL char */
2632 for (i = 0; i < nr; i++) {
2633 maxlen += strlen(versions->items[offset+i].string) + extra;
2635 strbuf_grow(&buf, maxlen);
2637 /* Write each entry out to buf */
2638 for (i = 0; i < nr; i++) {
2639 struct merged_info *mi = versions->items[offset+i].util;
2640 struct version_info *ri = &mi->result;
2641 strbuf_addf(&buf, "%o %s%c",
2643 versions->items[offset+i].string, '\0');
2644 strbuf_add(&buf, ri->oid.hash, hash_size);
2647 /* Write this object file out, and record in result_oid */
2648 write_object_file(buf.buf, buf.len, tree_type, result_oid);
2649 strbuf_release(&buf);
2652 static void record_entry_for_tree(struct directory_versions *dir_metadata,
2654 struct merged_info *mi)
2656 const char *basename;
2659 /* nothing to record */
2662 basename = path + mi->basename_offset;
2663 assert(strchr(basename, '/') == NULL);
2664 string_list_append(&dir_metadata->versions,
2665 basename)->util = &mi->result;
2668 static void write_completed_directory(struct merge_options *opt,
2669 const char *new_directory_name,
2670 struct directory_versions *info)
2672 const char *prev_dir;
2673 struct merged_info *dir_info = NULL;
2674 unsigned int offset;
2677 * Some explanation of info->versions and info->offsets...
2679 * process_entries() iterates over all relevant files AND
2680 * directories in reverse lexicographic order, and calls this
2681 * function. Thus, an example of the paths that process_entries()
2682 * could operate on (along with the directories for those paths
2687 * src/moduleB/umm.c src/moduleB
2688 * src/moduleB/stuff.h src/moduleB
2689 * src/moduleB/baz.c src/moduleB
2691 * src/moduleA/foo.c src/moduleA
2692 * src/moduleA/bar.c src/moduleA
2699 * always contains the unprocessed entries and their
2700 * version_info information. For example, after the first five
2701 * entries above, info->versions would be:
2703 * xtract.c <xtract.c's version_info>
2704 * token.txt <token.txt's version_info>
2705 * umm.c <src/moduleB/umm.c's version_info>
2706 * stuff.h <src/moduleB/stuff.h's version_info>
2707 * baz.c <src/moduleB/baz.c's version_info>
2709 * Once a subdirectory is completed we remove the entries in
2710 * that subdirectory from info->versions, writing it as a tree
2711 * (write_tree()). Thus, as soon as we get to src/moduleB,
2712 * info->versions would be updated to
2714 * xtract.c <xtract.c's version_info>
2715 * token.txt <token.txt's version_info>
2716 * moduleB <src/moduleB's version_info>
2720 * helps us track which entries in info->versions correspond to
2721 * which directories. When we are N directories deep (e.g. 4
2722 * for src/modA/submod/subdir/), we have up to N+1 unprocessed
2723 * directories (+1 because of toplevel dir). Corresponding to
2724 * the info->versions example above, after processing five entries
2725 * info->offsets will be:
2730 * which is used to know that xtract.c & token.txt are from the
2731 * toplevel dirctory, while umm.c & stuff.h & baz.c are from the
2732 * src/moduleB directory. Again, following the example above,
2733 * once we need to process src/moduleB, then info->offsets is
2739 * which says that moduleB (and only moduleB so far) is in the
2742 * One unique thing to note about info->offsets here is that
2743 * "src" was not added to info->offsets until there was a path
2744 * (a file OR directory) immediately below src/ that got
2747 * Since process_entry() just appends new entries to info->versions,
2748 * write_completed_directory() only needs to do work if the next path
2749 * is in a directory that is different than the last directory found
2754 * If we are working with the same directory as the last entry, there
2755 * is no work to do. (See comments above the directory_name member of
2756 * struct merged_info for why we can use pointer comparison instead of
2759 if (new_directory_name == info->last_directory)
2763 * If we are just starting (last_directory is NULL), or last_directory
2764 * is a prefix of the current directory, then we can just update
2765 * info->offsets to record the offset where we started this directory
2766 * and update last_directory to have quick access to it.
2768 if (info->last_directory == NULL ||
2769 !strncmp(new_directory_name, info->last_directory,
2770 info->last_directory_len)) {
2771 uintptr_t offset = info->versions.nr;
2773 info->last_directory = new_directory_name;
2774 info->last_directory_len = strlen(info->last_directory);
2776 * Record the offset into info->versions where we will
2777 * start recording basenames of paths found within
2778 * new_directory_name.
2780 string_list_append(&info->offsets,
2781 info->last_directory)->util = (void*)offset;
2786 * The next entry that will be processed will be within
2787 * new_directory_name. Since at this point we know that
2788 * new_directory_name is within a different directory than
2789 * info->last_directory, we have all entries for info->last_directory
2790 * in info->versions and we need to create a tree object for them.
2792 dir_info = strmap_get(&opt->priv->paths, info->last_directory);
2794 offset = (uintptr_t)info->offsets.items[info->offsets.nr-1].util;
2795 if (offset == info->versions.nr) {
2797 * Actually, we don't need to create a tree object in this
2798 * case. Whenever all files within a directory disappear
2799 * during the merge (e.g. unmodified on one side and
2800 * deleted on the other, or files were renamed elsewhere),
2801 * then we get here and the directory itself needs to be
2802 * omitted from its parent tree as well.
2804 dir_info->is_null = 1;
2807 * Write out the tree to the git object directory, and also
2808 * record the mode and oid in dir_info->result.
2810 dir_info->is_null = 0;
2811 dir_info->result.mode = S_IFDIR;
2812 write_tree(&dir_info->result.oid, &info->versions, offset,
2813 opt->repo->hash_algo->rawsz);
2817 * We've now used several entries from info->versions and one entry
2818 * from info->offsets, so we get rid of those values.
2821 info->versions.nr = offset;
2824 * Now we've taken care of the completed directory, but we need to
2825 * prepare things since future entries will be in
2826 * new_directory_name. (In particular, process_entry() will be
2827 * appending new entries to info->versions.) So, we need to make
2828 * sure new_directory_name is the last entry in info->offsets.
2830 prev_dir = info->offsets.nr == 0 ? NULL :
2831 info->offsets.items[info->offsets.nr-1].string;
2832 if (new_directory_name != prev_dir) {
2833 uintptr_t c = info->versions.nr;
2834 string_list_append(&info->offsets,
2835 new_directory_name)->util = (void*)c;
2838 /* And, of course, we need to update last_directory to match. */
2839 info->last_directory = new_directory_name;
2840 info->last_directory_len = strlen(info->last_directory);
2843 /* Per entry merge function */
2844 static void process_entry(struct merge_options *opt,
2846 struct conflict_info *ci,
2847 struct directory_versions *dir_metadata)
2849 int df_file_index = 0;
2852 assert(ci->filemask >= 0 && ci->filemask <= 7);
2853 /* ci->match_mask == 7 was handled in collect_merge_info_callback() */
2854 assert(ci->match_mask == 0 || ci->match_mask == 3 ||
2855 ci->match_mask == 5 || ci->match_mask == 6);
2858 record_entry_for_tree(dir_metadata, path, &ci->merged);
2859 if (ci->filemask == 0)
2860 /* nothing else to handle */
2862 assert(ci->df_conflict);
2865 if (ci->df_conflict && ci->merged.result.mode == 0) {
2869 * directory no longer in the way, but we do have a file we
2870 * need to place here so we need to clean away the "directory
2871 * merges to nothing" result.
2873 ci->df_conflict = 0;
2874 assert(ci->filemask != 0);
2875 ci->merged.clean = 0;
2876 ci->merged.is_null = 0;
2877 /* and we want to zero out any directory-related entries */
2878 ci->match_mask = (ci->match_mask & ~ci->dirmask);
2880 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
2881 if (ci->filemask & (1 << i))
2883 ci->stages[i].mode = 0;
2884 oidcpy(&ci->stages[i].oid, &null_oid);
2886 } else if (ci->df_conflict && ci->merged.result.mode != 0) {
2888 * This started out as a D/F conflict, and the entries in
2889 * the competing directory were not removed by the merge as
2890 * evidenced by write_completed_directory() writing a value
2891 * to ci->merged.result.mode.
2893 struct conflict_info *new_ci;
2895 const char *old_path = path;
2898 assert(ci->merged.result.mode == S_IFDIR);
2901 * If filemask is 1, we can just ignore the file as having
2902 * been deleted on both sides. We do not want to overwrite
2903 * ci->merged.result, since it stores the tree for all the
2906 if (ci->filemask == 1) {
2912 * This file still exists on at least one side, and we want
2913 * the directory to remain here, so we need to move this
2914 * path to some new location.
2916 new_ci = xcalloc(1, sizeof(*new_ci));
2917 /* We don't really want new_ci->merged.result copied, but it'll
2918 * be overwritten below so it doesn't matter. We also don't
2919 * want any directory mode/oid values copied, but we'll zero
2920 * those out immediately. We do want the rest of ci copied.
2922 memcpy(new_ci, ci, sizeof(*ci));
2923 new_ci->match_mask = (new_ci->match_mask & ~new_ci->dirmask);
2924 new_ci->dirmask = 0;
2925 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
2926 if (new_ci->filemask & (1 << i))
2928 /* zero out any entries related to directories */
2929 new_ci->stages[i].mode = 0;
2930 oidcpy(&new_ci->stages[i].oid, &null_oid);
2934 * Find out which side this file came from; note that we
2935 * cannot just use ci->filemask, because renames could cause
2936 * the filemask to go back to 7. So we use dirmask, then
2937 * pick the opposite side's index.
2939 df_file_index = (ci->dirmask & (1 << 1)) ? 2 : 1;
2940 branch = (df_file_index == 1) ? opt->branch1 : opt->branch2;
2941 path = unique_path(&opt->priv->paths, path, branch);
2942 strmap_put(&opt->priv->paths, path, new_ci);
2944 path_msg(opt, path, 0,
2945 _("CONFLICT (file/directory): directory in the way "
2946 "of %s from %s; moving it to %s instead."),
2947 old_path, branch, path);
2950 * Zero out the filemask for the old ci. At this point, ci
2951 * was just an entry for a directory, so we don't need to
2952 * do anything more with it.
2957 * Now note that we're working on the new entry (path was
2964 * NOTE: Below there is a long switch-like if-elseif-elseif... block
2965 * which the code goes through even for the df_conflict cases
2968 if (ci->match_mask) {
2969 ci->merged.clean = 1;
2970 if (ci->match_mask == 6) {
2971 /* stages[1] == stages[2] */
2972 ci->merged.result.mode = ci->stages[1].mode;
2973 oidcpy(&ci->merged.result.oid, &ci->stages[1].oid);
2975 /* determine the mask of the side that didn't match */
2976 unsigned int othermask = 7 & ~ci->match_mask;
2977 int side = (othermask == 4) ? 2 : 1;
2979 ci->merged.result.mode = ci->stages[side].mode;
2980 ci->merged.is_null = !ci->merged.result.mode;
2981 oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
2983 assert(othermask == 2 || othermask == 4);
2984 assert(ci->merged.is_null ==
2985 (ci->filemask == ci->match_mask));
2987 } else if (ci->filemask >= 6 &&
2988 (S_IFMT & ci->stages[1].mode) !=
2989 (S_IFMT & ci->stages[2].mode)) {
2990 /* Two different items from (file/submodule/symlink) */
2991 if (opt->priv->call_depth) {
2992 /* Just use the version from the merge base */
2993 ci->merged.clean = 0;
2994 oidcpy(&ci->merged.result.oid, &ci->stages[0].oid);
2995 ci->merged.result.mode = ci->stages[0].mode;
2996 ci->merged.is_null = (ci->merged.result.mode == 0);
2998 /* Handle by renaming one or both to separate paths. */
2999 unsigned o_mode = ci->stages[0].mode;
3000 unsigned a_mode = ci->stages[1].mode;
3001 unsigned b_mode = ci->stages[2].mode;
3002 struct conflict_info *new_ci;
3003 const char *a_path = NULL, *b_path = NULL;
3004 int rename_a = 0, rename_b = 0;
3006 new_ci = xmalloc(sizeof(*new_ci));
3008 if (S_ISREG(a_mode))
3010 else if (S_ISREG(b_mode))
3017 path_msg(opt, path, 0,
3018 _("CONFLICT (distinct types): %s had different "
3019 "types on each side; renamed %s of them so "
3020 "each can be recorded somewhere."),
3022 (rename_a && rename_b) ? _("both") : _("one"));
3024 ci->merged.clean = 0;
3025 memcpy(new_ci, ci, sizeof(*new_ci));
3027 /* Put b into new_ci, removing a from stages */
3028 new_ci->merged.result.mode = ci->stages[2].mode;
3029 oidcpy(&new_ci->merged.result.oid, &ci->stages[2].oid);
3030 new_ci->stages[1].mode = 0;
3031 oidcpy(&new_ci->stages[1].oid, &null_oid);
3032 new_ci->filemask = 5;
3033 if ((S_IFMT & b_mode) != (S_IFMT & o_mode)) {
3034 new_ci->stages[0].mode = 0;
3035 oidcpy(&new_ci->stages[0].oid, &null_oid);
3036 new_ci->filemask = 4;
3039 /* Leave only a in ci, fixing stages. */
3040 ci->merged.result.mode = ci->stages[1].mode;
3041 oidcpy(&ci->merged.result.oid, &ci->stages[1].oid);
3042 ci->stages[2].mode = 0;
3043 oidcpy(&ci->stages[2].oid, &null_oid);
3045 if ((S_IFMT & a_mode) != (S_IFMT & o_mode)) {
3046 ci->stages[0].mode = 0;
3047 oidcpy(&ci->stages[0].oid, &null_oid);
3051 /* Insert entries into opt->priv_paths */
3052 assert(rename_a || rename_b);
3054 a_path = unique_path(&opt->priv->paths,
3055 path, opt->branch1);
3056 strmap_put(&opt->priv->paths, a_path, ci);
3060 b_path = unique_path(&opt->priv->paths,
3061 path, opt->branch2);
3064 strmap_put(&opt->priv->paths, b_path, new_ci);
3066 if (rename_a && rename_b) {
3067 strmap_remove(&opt->priv->paths, path, 0);
3069 * We removed path from opt->priv->paths. path
3070 * will also eventually need to be freed, but
3071 * it may still be used by e.g. ci->pathnames.
3072 * So, store it in another string-list for now.
3074 string_list_append(&opt->priv->paths_to_free,
3079 * Do special handling for b_path since process_entry()
3080 * won't be called on it specially.
3082 strmap_put(&opt->priv->conflicted, b_path, new_ci);
3083 record_entry_for_tree(dir_metadata, b_path,
3087 * Remaining code for processing this entry should
3088 * think in terms of processing a_path.
3093 } else if (ci->filemask >= 6) {
3094 /* Need a two-way or three-way content merge */
3095 struct version_info merged_file;
3096 unsigned clean_merge;
3097 struct version_info *o = &ci->stages[0];
3098 struct version_info *a = &ci->stages[1];
3099 struct version_info *b = &ci->stages[2];
3101 clean_merge = handle_content_merge(opt, path, o, a, b,
3103 opt->priv->call_depth * 2,
3105 ci->merged.clean = clean_merge &&
3106 !ci->df_conflict && !ci->path_conflict;
3107 ci->merged.result.mode = merged_file.mode;
3108 ci->merged.is_null = (merged_file.mode == 0);
3109 oidcpy(&ci->merged.result.oid, &merged_file.oid);
3110 if (clean_merge && ci->df_conflict) {
3111 assert(df_file_index == 1 || df_file_index == 2);
3112 ci->filemask = 1 << df_file_index;
3113 ci->stages[df_file_index].mode = merged_file.mode;
3114 oidcpy(&ci->stages[df_file_index].oid, &merged_file.oid);
3117 const char *reason = _("content");
3118 if (ci->filemask == 6)
3119 reason = _("add/add");
3120 if (S_ISGITLINK(merged_file.mode))
3121 reason = _("submodule");
3122 path_msg(opt, path, 0,
3123 _("CONFLICT (%s): Merge conflict in %s"),
3126 } else if (ci->filemask == 3 || ci->filemask == 5) {
3128 const char *modify_branch, *delete_branch;
3129 int side = (ci->filemask == 5) ? 2 : 1;
3130 int index = opt->priv->call_depth ? 0 : side;
3132 ci->merged.result.mode = ci->stages[index].mode;
3133 oidcpy(&ci->merged.result.oid, &ci->stages[index].oid);
3134 ci->merged.clean = 0;
3136 modify_branch = (side == 1) ? opt->branch1 : opt->branch2;
3137 delete_branch = (side == 1) ? opt->branch2 : opt->branch1;
3139 if (ci->path_conflict &&
3140 oideq(&ci->stages[0].oid, &ci->stages[side].oid)) {
3142 * This came from a rename/delete; no action to take,
3143 * but avoid printing "modify/delete" conflict notice
3144 * since the contents were not modified.
3147 path_msg(opt, path, 0,
3148 _("CONFLICT (modify/delete): %s deleted in %s "
3149 "and modified in %s. Version %s of %s left "
3151 path, delete_branch, modify_branch,
3152 modify_branch, path);
3154 } else if (ci->filemask == 2 || ci->filemask == 4) {
3155 /* Added on one side */
3156 int side = (ci->filemask == 4) ? 2 : 1;
3157 ci->merged.result.mode = ci->stages[side].mode;
3158 oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
3159 ci->merged.clean = !ci->df_conflict && !ci->path_conflict;
3160 } else if (ci->filemask == 1) {
3161 /* Deleted on both sides */
3162 ci->merged.is_null = 1;
3163 ci->merged.result.mode = 0;
3164 oidcpy(&ci->merged.result.oid, &null_oid);
3165 ci->merged.clean = !ci->path_conflict;
3169 * If still conflicted, record it separately. This allows us to later
3170 * iterate over just conflicted entries when updating the index instead
3171 * of iterating over all entries.
3173 if (!ci->merged.clean)
3174 strmap_put(&opt->priv->conflicted, path, ci);
3175 record_entry_for_tree(dir_metadata, path, &ci->merged);
3178 static void process_entries(struct merge_options *opt,
3179 struct object_id *result_oid)
3181 struct hashmap_iter iter;
3182 struct strmap_entry *e;
3183 struct string_list plist = STRING_LIST_INIT_NODUP;
3184 struct string_list_item *entry;
3185 struct directory_versions dir_metadata = { STRING_LIST_INIT_NODUP,
3186 STRING_LIST_INIT_NODUP,
3189 trace2_region_enter("merge", "process_entries setup", opt->repo);
3190 if (strmap_empty(&opt->priv->paths)) {
3191 oidcpy(result_oid, opt->repo->hash_algo->empty_tree);
3195 /* Hack to pre-allocate plist to the desired size */
3196 trace2_region_enter("merge", "plist grow", opt->repo);
3197 ALLOC_GROW(plist.items, strmap_get_size(&opt->priv->paths), plist.alloc);
3198 trace2_region_leave("merge", "plist grow", opt->repo);
3200 /* Put every entry from paths into plist, then sort */
3201 trace2_region_enter("merge", "plist copy", opt->repo);
3202 strmap_for_each_entry(&opt->priv->paths, &iter, e) {
3203 string_list_append(&plist, e->key)->util = e->value;
3205 trace2_region_leave("merge", "plist copy", opt->repo);
3207 trace2_region_enter("merge", "plist special sort", opt->repo);
3208 plist.cmp = string_list_df_name_compare;
3209 string_list_sort(&plist);
3210 trace2_region_leave("merge", "plist special sort", opt->repo);
3212 trace2_region_leave("merge", "process_entries setup", opt->repo);
3215 * Iterate over the items in reverse order, so we can handle paths
3216 * below a directory before needing to handle the directory itself.
3218 * This allows us to write subtrees before we need to write trees,
3219 * and it also enables sane handling of directory/file conflicts
3220 * (because it allows us to know whether the directory is still in
3221 * the way when it is time to process the file at the same path).
3223 trace2_region_enter("merge", "processing", opt->repo);
3224 for (entry = &plist.items[plist.nr-1]; entry >= plist.items; --entry) {
3225 char *path = entry->string;
3227 * NOTE: mi may actually be a pointer to a conflict_info, but
3228 * we have to check mi->clean first to see if it's safe to
3229 * reassign to such a pointer type.
3231 struct merged_info *mi = entry->util;
3233 write_completed_directory(opt, mi->directory_name,
3236 record_entry_for_tree(&dir_metadata, path, mi);
3238 struct conflict_info *ci = (struct conflict_info *)mi;
3239 process_entry(opt, path, ci, &dir_metadata);
3242 trace2_region_leave("merge", "processing", opt->repo);
3244 trace2_region_enter("merge", "process_entries cleanup", opt->repo);
3245 if (dir_metadata.offsets.nr != 1 ||
3246 (uintptr_t)dir_metadata.offsets.items[0].util != 0) {
3247 printf("dir_metadata.offsets.nr = %d (should be 1)\n",
3248 dir_metadata.offsets.nr);
3249 printf("dir_metadata.offsets.items[0].util = %u (should be 0)\n",
3250 (unsigned)(uintptr_t)dir_metadata.offsets.items[0].util);
3252 BUG("dir_metadata accounting completely off; shouldn't happen");
3254 write_tree(result_oid, &dir_metadata.versions, 0,
3255 opt->repo->hash_algo->rawsz);
3256 string_list_clear(&plist, 0);
3257 string_list_clear(&dir_metadata.versions, 0);
3258 string_list_clear(&dir_metadata.offsets, 0);
3259 trace2_region_leave("merge", "process_entries cleanup", opt->repo);
3262 /*** Function Grouping: functions related to merge_switch_to_result() ***/
3264 static int checkout(struct merge_options *opt,
3268 /* Switch the index/working copy from old to new */
3270 struct tree_desc trees[2];
3271 struct unpack_trees_options unpack_opts;
3273 memset(&unpack_opts, 0, sizeof(unpack_opts));
3274 unpack_opts.head_idx = -1;
3275 unpack_opts.src_index = opt->repo->index;
3276 unpack_opts.dst_index = opt->repo->index;
3278 setup_unpack_trees_porcelain(&unpack_opts, "merge");
3281 * NOTE: if this were just "git checkout" code, we would probably
3282 * read or refresh the cache and check for a conflicted index, but
3283 * builtin/merge.c or sequencer.c really needs to read the index
3284 * and check for conflicted entries before starting merging for a
3285 * good user experience (no sense waiting for merges/rebases before
3286 * erroring out), so there's no reason to duplicate that work here.
3289 /* 2-way merge to the new branch */
3290 unpack_opts.update = 1;
3291 unpack_opts.merge = 1;
3292 unpack_opts.quiet = 0; /* FIXME: sequencer might want quiet? */
3293 unpack_opts.verbose_update = (opt->verbosity > 2);
3294 unpack_opts.fn = twoway_merge;
3295 if (1/* FIXME: opts->overwrite_ignore*/) {
3296 unpack_opts.dir = xcalloc(1, sizeof(*unpack_opts.dir));
3297 unpack_opts.dir->flags |= DIR_SHOW_IGNORED;
3298 setup_standard_excludes(unpack_opts.dir);
3301 init_tree_desc(&trees[0], prev->buffer, prev->size);
3303 init_tree_desc(&trees[1], next->buffer, next->size);
3305 ret = unpack_trees(2, trees, &unpack_opts);
3306 clear_unpack_trees_porcelain(&unpack_opts);
3307 dir_clear(unpack_opts.dir);
3308 FREE_AND_NULL(unpack_opts.dir);
3312 static int record_conflicted_index_entries(struct merge_options *opt,
3313 struct index_state *index,
3314 struct strmap *paths,
3315 struct strmap *conflicted)
3317 struct hashmap_iter iter;
3318 struct strmap_entry *e;
3320 int original_cache_nr;
3322 if (strmap_empty(conflicted))
3325 original_cache_nr = index->cache_nr;
3327 /* Put every entry from paths into plist, then sort */
3328 strmap_for_each_entry(conflicted, &iter, e) {
3329 const char *path = e->key;
3330 struct conflict_info *ci = e->value;
3332 struct cache_entry *ce;
3338 * The index will already have a stage=0 entry for this path,
3339 * because we created an as-merged-as-possible version of the
3340 * file and checkout() moved the working copy and index over
3343 * However, previous iterations through this loop will have
3344 * added unstaged entries to the end of the cache which
3345 * ignore the standard alphabetical ordering of cache
3346 * entries and break invariants needed for index_name_pos()
3347 * to work. However, we know the entry we want is before
3348 * those appended cache entries, so do a temporary swap on
3349 * cache_nr to only look through entries of interest.
3351 SWAP(index->cache_nr, original_cache_nr);
3352 pos = index_name_pos(index, path, strlen(path));
3353 SWAP(index->cache_nr, original_cache_nr);
3355 if (ci->filemask != 1)
3356 BUG("Conflicted %s but nothing in basic working tree or index; this shouldn't happen", path);
3357 cache_tree_invalidate_path(index, path);
3359 ce = index->cache[pos];
3362 * Clean paths with CE_SKIP_WORKTREE set will not be
3363 * written to the working tree by the unpack_trees()
3364 * call in checkout(). Our conflicted entries would
3365 * have appeared clean to that code since we ignored
3366 * the higher order stages. Thus, we need override
3367 * the CE_SKIP_WORKTREE bit and manually write those
3368 * files to the working disk here.
3370 * TODO: Implement this CE_SKIP_WORKTREE fixup.
3374 * Mark this cache entry for removal and instead add
3375 * new stage>0 entries corresponding to the
3376 * conflicts. If there are many conflicted entries, we
3377 * want to avoid memmove'ing O(NM) entries by
3378 * inserting the new entries one at a time. So,
3379 * instead, we just add the new cache entries to the
3380 * end (ignoring normal index requirements on sort
3381 * order) and sort the index once we're all done.
3383 ce->ce_flags |= CE_REMOVE;
3386 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
3387 struct version_info *vi;
3388 if (!(ci->filemask & (1ul << i)))
3390 vi = &ci->stages[i];
3391 ce = make_cache_entry(index, vi->mode, &vi->oid,
3393 add_index_entry(index, ce, ADD_CACHE_JUST_APPEND);
3398 * Remove the unused cache entries (and invalidate the relevant
3399 * cache-trees), then sort the index entries to get the conflicted
3400 * entries we added to the end into their right locations.
3402 remove_marked_cache_entries(index, 1);
3404 * No need for STABLE_QSORT -- cmp_cache_name_compare sorts primarily
3405 * on filename and secondarily on stage, and (name, stage #) are a
3408 QSORT(index->cache, index->cache_nr, cmp_cache_name_compare);
3413 void merge_switch_to_result(struct merge_options *opt,
3415 struct merge_result *result,
3416 int update_worktree_and_index,
3417 int display_update_msgs)
3419 assert(opt->priv == NULL);
3420 if (result->clean >= 0 && update_worktree_and_index) {
3421 struct merge_options_internal *opti = result->priv;
3423 trace2_region_enter("merge", "checkout", opt->repo);
3424 if (checkout(opt, head, result->tree)) {
3425 /* failure to function */
3429 trace2_region_leave("merge", "checkout", opt->repo);
3431 trace2_region_enter("merge", "record_conflicted", opt->repo);
3432 if (record_conflicted_index_entries(opt, opt->repo->index,
3434 &opti->conflicted)) {
3435 /* failure to function */
3439 trace2_region_leave("merge", "record_conflicted", opt->repo);
3442 if (display_update_msgs) {
3443 struct merge_options_internal *opti = result->priv;
3444 struct hashmap_iter iter;
3445 struct strmap_entry *e;
3446 struct string_list olist = STRING_LIST_INIT_NODUP;
3449 trace2_region_enter("merge", "display messages", opt->repo);
3451 /* Hack to pre-allocate olist to the desired size */
3452 ALLOC_GROW(olist.items, strmap_get_size(&opti->output),
3455 /* Put every entry from output into olist, then sort */
3456 strmap_for_each_entry(&opti->output, &iter, e) {
3457 string_list_append(&olist, e->key)->util = e->value;
3459 string_list_sort(&olist);
3461 /* Iterate over the items, printing them */
3462 for (i = 0; i < olist.nr; ++i) {
3463 struct strbuf *sb = olist.items[i].util;
3465 printf("%s", sb->buf);
3467 string_list_clear(&olist, 0);
3469 /* Also include needed rename limit adjustment now */
3470 diff_warn_rename_limit("merge.renamelimit",
3471 opti->renames.needed_limit, 0);
3473 trace2_region_leave("merge", "display messages", opt->repo);
3476 merge_finalize(opt, result);
3479 void merge_finalize(struct merge_options *opt,
3480 struct merge_result *result)
3482 struct merge_options_internal *opti = result->priv;
3484 if (opt->renormalize)
3485 git_attr_set_direction(GIT_ATTR_CHECKIN);
3486 assert(opt->priv == NULL);
3488 clear_or_reinit_internal_opts(opti, 0);
3489 FREE_AND_NULL(opti);
3492 /*** Function Grouping: helper functions for merge_incore_*() ***/
3494 static inline void set_commit_tree(struct commit *c, struct tree *t)
3499 static struct commit *make_virtual_commit(struct repository *repo,
3501 const char *comment)
3503 struct commit *commit = alloc_commit_node(repo);
3505 set_merge_remote_desc(commit, comment, (struct object *)commit);
3506 set_commit_tree(commit, tree);
3507 commit->object.parsed = 1;
3511 static void merge_start(struct merge_options *opt, struct merge_result *result)
3513 struct rename_info *renames;
3516 /* Sanity checks on opt */
3517 trace2_region_enter("merge", "sanity checks", opt->repo);
3520 assert(opt->branch1 && opt->branch2);
3522 assert(opt->detect_directory_renames >= MERGE_DIRECTORY_RENAMES_NONE &&
3523 opt->detect_directory_renames <= MERGE_DIRECTORY_RENAMES_TRUE);
3524 assert(opt->rename_limit >= -1);
3525 assert(opt->rename_score >= 0 && opt->rename_score <= MAX_SCORE);
3526 assert(opt->show_rename_progress >= 0 && opt->show_rename_progress <= 1);
3528 assert(opt->xdl_opts >= 0);
3529 assert(opt->recursive_variant >= MERGE_VARIANT_NORMAL &&
3530 opt->recursive_variant <= MERGE_VARIANT_THEIRS);
3533 * detect_renames, verbosity, buffer_output, and obuf are ignored
3534 * fields that were used by "recursive" rather than "ort" -- but
3535 * sanity check them anyway.
3537 assert(opt->detect_renames >= -1 &&
3538 opt->detect_renames <= DIFF_DETECT_COPY);
3539 assert(opt->verbosity >= 0 && opt->verbosity <= 5);
3540 assert(opt->buffer_output <= 2);
3541 assert(opt->obuf.len == 0);
3543 assert(opt->priv == NULL);
3545 opt->priv = result->priv;
3546 result->priv = NULL;
3548 * opt->priv non-NULL means we had results from a previous
3549 * run; do a few sanity checks that user didn't mess with
3550 * it in an obvious fashion.
3552 assert(opt->priv->call_depth == 0);
3553 assert(!opt->priv->toplevel_dir ||
3554 0 == strlen(opt->priv->toplevel_dir));
3556 trace2_region_leave("merge", "sanity checks", opt->repo);
3558 /* Default to histogram diff. Actually, just hardcode it...for now. */
3559 opt->xdl_opts = DIFF_WITH_ALG(opt, HISTOGRAM_DIFF);
3561 /* Handle attr direction stuff for renormalization */
3562 if (opt->renormalize)
3563 git_attr_set_direction(GIT_ATTR_CHECKOUT);
3565 /* Initialization of opt->priv, our internal merge data */
3566 trace2_region_enter("merge", "allocate/init", opt->repo);
3568 clear_or_reinit_internal_opts(opt->priv, 1);
3569 trace2_region_leave("merge", "allocate/init", opt->repo);
3572 opt->priv = xcalloc(1, sizeof(*opt->priv));
3574 /* Initialization of various renames fields */
3575 renames = &opt->priv->renames;
3576 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {
3577 strintmap_init_with_options(&renames->dirs_removed[i],
3578 NOT_RELEVANT, NULL, 0);
3579 strmap_init_with_options(&renames->dir_rename_count[i],
3581 strmap_init_with_options(&renames->dir_renames[i],
3583 strintmap_init_with_options(&renames->relevant_sources[i],
3588 * Although we initialize opt->priv->paths with strdup_strings=0,
3589 * that's just to avoid making yet another copy of an allocated
3590 * string. Putting the entry into paths means we are taking
3591 * ownership, so we will later free it. paths_to_free is similar.
3593 * In contrast, conflicted just has a subset of keys from paths, so
3594 * we don't want to free those (it'd be a duplicate free).
3596 strmap_init_with_options(&opt->priv->paths, NULL, 0);
3597 strmap_init_with_options(&opt->priv->conflicted, NULL, 0);
3598 string_list_init(&opt->priv->paths_to_free, 0);
3601 * keys & strbufs in output will sometimes need to outlive "paths",
3602 * so it will have a copy of relevant keys. It's probably a small
3603 * subset of the overall paths that have special output.
3605 strmap_init(&opt->priv->output);
3607 trace2_region_leave("merge", "allocate/init", opt->repo);
3610 /*** Function Grouping: merge_incore_*() and their internal variants ***/
3613 * Originally from merge_trees_internal(); heavily adapted, though.
3615 static void merge_ort_nonrecursive_internal(struct merge_options *opt,
3616 struct tree *merge_base,
3619 struct merge_result *result)
3621 struct object_id working_tree_oid;
3623 trace2_region_enter("merge", "collect_merge_info", opt->repo);
3624 if (collect_merge_info(opt, merge_base, side1, side2) != 0) {
3626 * TRANSLATORS: The %s arguments are: 1) tree hash of a merge
3627 * base, and 2-3) the trees for the two trees we're merging.
3629 err(opt, _("collecting merge info failed for trees %s, %s, %s"),
3630 oid_to_hex(&merge_base->object.oid),
3631 oid_to_hex(&side1->object.oid),
3632 oid_to_hex(&side2->object.oid));
3636 trace2_region_leave("merge", "collect_merge_info", opt->repo);
3638 trace2_region_enter("merge", "renames", opt->repo);
3639 result->clean = detect_and_process_renames(opt, merge_base,
3641 trace2_region_leave("merge", "renames", opt->repo);
3643 trace2_region_enter("merge", "process_entries", opt->repo);
3644 process_entries(opt, &working_tree_oid);
3645 trace2_region_leave("merge", "process_entries", opt->repo);
3647 /* Set return values */
3648 result->tree = parse_tree_indirect(&working_tree_oid);
3649 /* existence of conflicted entries implies unclean */
3650 result->clean &= strmap_empty(&opt->priv->conflicted);
3651 if (!opt->priv->call_depth) {
3652 result->priv = opt->priv;
3658 * Originally from merge_recursive_internal(); somewhat adapted, though.
3660 static void merge_ort_internal(struct merge_options *opt,
3661 struct commit_list *merge_bases,
3664 struct merge_result *result)
3666 struct commit_list *iter;
3667 struct commit *merged_merge_bases;
3668 const char *ancestor_name;
3669 struct strbuf merge_base_abbrev = STRBUF_INIT;
3672 merge_bases = get_merge_bases(h1, h2);
3673 /* See merge-ort.h:merge_incore_recursive() declaration NOTE */
3674 merge_bases = reverse_commit_list(merge_bases);
3677 merged_merge_bases = pop_commit(&merge_bases);
3678 if (merged_merge_bases == NULL) {
3679 /* if there is no common ancestor, use an empty tree */
3682 tree = lookup_tree(opt->repo, opt->repo->hash_algo->empty_tree);
3683 merged_merge_bases = make_virtual_commit(opt->repo, tree,
3685 ancestor_name = "empty tree";
3686 } else if (merge_bases) {
3687 ancestor_name = "merged common ancestors";
3689 strbuf_add_unique_abbrev(&merge_base_abbrev,
3690 &merged_merge_bases->object.oid,
3692 ancestor_name = merge_base_abbrev.buf;
3695 for (iter = merge_bases; iter; iter = iter->next) {
3696 const char *saved_b1, *saved_b2;
3697 struct commit *prev = merged_merge_bases;
3699 opt->priv->call_depth++;
3701 * When the merge fails, the result contains files
3702 * with conflict markers. The cleanness flag is
3703 * ignored (unless indicating an error), it was never
3704 * actually used, as result of merge_trees has always
3705 * overwritten it: the committed "conflicts" were
3708 saved_b1 = opt->branch1;
3709 saved_b2 = opt->branch2;
3710 opt->branch1 = "Temporary merge branch 1";
3711 opt->branch2 = "Temporary merge branch 2";
3712 merge_ort_internal(opt, NULL, prev, iter->item, result);
3713 if (result->clean < 0)
3715 opt->branch1 = saved_b1;
3716 opt->branch2 = saved_b2;
3717 opt->priv->call_depth--;
3719 merged_merge_bases = make_virtual_commit(opt->repo,
3722 commit_list_insert(prev, &merged_merge_bases->parents);
3723 commit_list_insert(iter->item,
3724 &merged_merge_bases->parents->next);
3726 clear_or_reinit_internal_opts(opt->priv, 1);
3729 opt->ancestor = ancestor_name;
3730 merge_ort_nonrecursive_internal(opt,
3731 repo_get_commit_tree(opt->repo,
3732 merged_merge_bases),
3733 repo_get_commit_tree(opt->repo, h1),
3734 repo_get_commit_tree(opt->repo, h2),
3736 strbuf_release(&merge_base_abbrev);
3737 opt->ancestor = NULL; /* avoid accidental re-use of opt->ancestor */
3740 void merge_incore_nonrecursive(struct merge_options *opt,
3741 struct tree *merge_base,
3744 struct merge_result *result)
3746 trace2_region_enter("merge", "incore_nonrecursive", opt->repo);
3748 trace2_region_enter("merge", "merge_start", opt->repo);
3749 assert(opt->ancestor != NULL);
3750 merge_start(opt, result);
3751 trace2_region_leave("merge", "merge_start", opt->repo);
3753 merge_ort_nonrecursive_internal(opt, merge_base, side1, side2, result);
3754 trace2_region_leave("merge", "incore_nonrecursive", opt->repo);
3757 void merge_incore_recursive(struct merge_options *opt,
3758 struct commit_list *merge_bases,
3759 struct commit *side1,
3760 struct commit *side2,
3761 struct merge_result *result)
3763 trace2_region_enter("merge", "incore_recursive", opt->repo);
3765 /* We set the ancestor label based on the merge_bases */
3766 assert(opt->ancestor == NULL);
3768 trace2_region_enter("merge", "merge_start", opt->repo);
3769 merge_start(opt, result);
3770 trace2_region_leave("merge", "merge_start", opt->repo);
3772 merge_ort_internal(opt, merge_bases, side1, side2, result);
3773 trace2_region_leave("merge", "incore_recursive", opt->repo);