Merge branch 'po-id' of github.com:bagasme/git-po
[alt-git.git] / merge-ort.c
blob99dcee2db8afa4c06f88739601e98bc3cf3dd64c
1 /*
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
4 * to replace
6 * git merge [-s recursive]
8 * with
10 * git merge -s ort
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"?)
17 #include "cache.h"
18 #include "merge-ort.h"
20 #include "alloc.h"
21 #include "attr.h"
22 #include "blob.h"
23 #include "cache-tree.h"
24 #include "commit.h"
25 #include "commit-reach.h"
26 #include "diff.h"
27 #include "diffcore.h"
28 #include "dir.h"
29 #include "entry.h"
30 #include "ll-merge.h"
31 #include "object-store.h"
32 #include "promisor-remote.h"
33 #include "revision.h"
34 #include "strmap.h"
35 #include "submodule-config.h"
36 #include "submodule.h"
37 #include "tree.h"
38 #include "unpack-trees.h"
39 #include "xdiff-interface.h"
42 * We have many arrays of size 3. Whenever we have such an array, the
43 * indices refer to one of the sides of the three-way merge. This is so
44 * pervasive that the constants 0, 1, and 2 are used in many places in the
45 * code (especially in arithmetic operations to find the other side's index
46 * or to compute a relevant mask), but sometimes these enum names are used
47 * to aid code clarity.
49 * See also 'filemask' and 'dirmask' in struct conflict_info; the "ith side"
50 * referred to there is one of these three sides.
52 enum merge_side {
53 MERGE_BASE = 0,
54 MERGE_SIDE1 = 1,
55 MERGE_SIDE2 = 2
58 static unsigned RESULT_INITIALIZED = 0x1abe11ed; /* unlikely accidental value */
60 struct traversal_callback_data {
61 unsigned long mask;
62 unsigned long dirmask;
63 struct name_entry names[3];
66 struct deferred_traversal_data {
68 * possible_trivial_merges: directories to be explored only when needed
70 * possible_trivial_merges is a map of directory names to
71 * dir_rename_mask. When we detect that a directory is unchanged on
72 * one side, we can sometimes resolve the directory without recursing
73 * into it. Renames are the only things that can prevent such an
74 * optimization. However, for rename sources:
75 * - If no parent directory needed directory rename detection, then
76 * no path under such a directory can be a relevant_source.
77 * and for rename destinations:
78 * - If no cached rename has a target path under the directory AND
79 * - If there are no unpaired relevant_sources elsewhere in the
80 * repository
81 * then we don't need any path under this directory for a rename
82 * destination. The only way to know the last item above is to defer
83 * handling such directories until the end of collect_merge_info(),
84 * in handle_deferred_entries().
86 * For each we store dir_rename_mask, since that's the only bit of
87 * information we need, other than the path, to resume the recursive
88 * traversal.
90 struct strintmap possible_trivial_merges;
93 * trivial_merges_okay: if trivial directory merges are okay
95 * See possible_trivial_merges above. The "no unpaired
96 * relevant_sources elsewhere in the repository" is a single boolean
97 * per merge side, which we store here. Note that while 0 means no,
98 * 1 only means "maybe" rather than "yes"; we optimistically set it
99 * to 1 initially and only clear when we determine it is unsafe to
100 * do trivial directory merges.
102 unsigned trivial_merges_okay;
105 * target_dirs: ancestor directories of rename targets
107 * target_dirs contains all directory names that are an ancestor of
108 * any rename destination.
110 struct strset target_dirs;
113 struct rename_info {
115 * All variables that are arrays of size 3 correspond to data tracked
116 * for the sides in enum merge_side. Index 0 is almost always unused
117 * because we often only need to track information for MERGE_SIDE1 and
118 * MERGE_SIDE2 (MERGE_BASE can't have rename information since renames
119 * are determined relative to what changed since the MERGE_BASE).
123 * pairs: pairing of filenames from diffcore_rename()
125 struct diff_queue_struct pairs[3];
128 * dirs_removed: directories removed on a given side of history.
130 * The keys of dirs_removed[side] are the directories that were removed
131 * on the given side of history. The value of the strintmap for each
132 * directory is a value from enum dir_rename_relevance.
134 struct strintmap dirs_removed[3];
137 * dir_rename_count: tracking where parts of a directory were renamed to
139 * When files in a directory are renamed, they may not all go to the
140 * same location. Each strmap here tracks:
141 * old_dir => {new_dir => int}
142 * That is, dir_rename_count[side] is a strmap to a strintmap.
144 struct strmap dir_rename_count[3];
147 * dir_renames: computed directory renames
149 * This is a map of old_dir => new_dir and is derived in part from
150 * dir_rename_count.
152 struct strmap dir_renames[3];
155 * relevant_sources: deleted paths wanted in rename detection, and why
157 * relevant_sources is a set of deleted paths on each side of
158 * history for which we need rename detection. If a path is deleted
159 * on one side of history, we need to detect if it is part of a
160 * rename if either
161 * * the file is modified/deleted on the other side of history
162 * * we need to detect renames for an ancestor directory
163 * If neither of those are true, we can skip rename detection for
164 * that path. The reason is stored as a value from enum
165 * file_rename_relevance, as the reason can inform the algorithm in
166 * diffcore_rename_extended().
168 struct strintmap relevant_sources[3];
170 struct deferred_traversal_data deferred[3];
173 * dir_rename_mask:
174 * 0: optimization removing unmodified potential rename source okay
175 * 2 or 4: optimization okay, but must check for files added to dir
176 * 7: optimization forbidden; need rename source in case of dir rename
178 unsigned dir_rename_mask:3;
181 * callback_data_*: supporting data structures for alternate traversal
183 * We sometimes need to be able to traverse through all the files
184 * in a given tree before all immediate subdirectories within that
185 * tree. Since traverse_trees() doesn't do that naturally, we have
186 * a traverse_trees_wrapper() that stores any immediate
187 * subdirectories while traversing files, then traverses the
188 * immediate subdirectories later. These callback_data* variables
189 * store the information for the subdirectories so that we can do
190 * that traversal order.
192 struct traversal_callback_data *callback_data;
193 int callback_data_nr, callback_data_alloc;
194 char *callback_data_traverse_path;
197 * merge_trees: trees passed to the merge algorithm for the merge
199 * merge_trees records the trees passed to the merge algorithm. But,
200 * this data also is stored in merge_result->priv. If a sequence of
201 * merges are being done (such as when cherry-picking or rebasing),
202 * the next merge can look at this and re-use information from
203 * previous merges under certain circumstances.
205 * See also all the cached_* variables.
207 struct tree *merge_trees[3];
210 * cached_pairs_valid_side: which side's cached info can be reused
212 * See the description for merge_trees. For repeated merges, at most
213 * only one side's cached information can be used. Valid values:
214 * MERGE_SIDE2: cached data from side2 can be reused
215 * MERGE_SIDE1: cached data from side1 can be reused
216 * 0: no cached data can be reused
217 * -1: See redo_after_renames; both sides can be reused.
219 int cached_pairs_valid_side;
222 * cached_pairs: Caching of renames and deletions.
224 * These are mappings recording renames and deletions of individual
225 * files (not directories). They are thus a map from an old
226 * filename to either NULL (for deletions) or a new filename (for
227 * renames).
229 struct strmap cached_pairs[3];
232 * cached_target_names: just the destinations from cached_pairs
234 * We sometimes want a fast lookup to determine if a given filename
235 * is one of the destinations in cached_pairs. cached_target_names
236 * is thus duplicative information, but it provides a fast lookup.
238 struct strset cached_target_names[3];
241 * cached_irrelevant: Caching of rename_sources that aren't relevant.
243 * If we try to detect a rename for a source path and succeed, it's
244 * part of a rename. If we try to detect a rename for a source path
245 * and fail, then it's a delete. If we do not try to detect a rename
246 * for a path, then we don't know if it's a rename or a delete. If
247 * merge-ort doesn't think the path is relevant, then we just won't
248 * cache anything for that path. But there's a slight problem in
249 * that merge-ort can think a path is RELEVANT_LOCATION, but due to
250 * commit 9bd342137e ("diffcore-rename: determine which
251 * relevant_sources are no longer relevant", 2021-03-13),
252 * diffcore-rename can downgrade the path to RELEVANT_NO_MORE. To
253 * avoid excessive calls to diffcore_rename_extended() we still need
254 * to cache such paths, though we cannot record them as either
255 * renames or deletes. So we cache them here as a "turned out to be
256 * irrelevant *for this commit*" as they are often also irrelevant
257 * for subsequent commits, though we will have to do some extra
258 * checking to see whether such paths become relevant for rename
259 * detection when cherry-picking/rebasing subsequent commits.
261 struct strset cached_irrelevant[3];
264 * redo_after_renames: optimization flag for "restarting" the merge
266 * Sometimes it pays to detect renames, cache them, and then
267 * restart the merge operation from the beginning. The reason for
268 * this is that when we know where all the renames are, we know
269 * whether a certain directory has any paths under it affected --
270 * and if a directory is not affected then it permits us to do
271 * trivial tree merging in more cases. Doing trivial tree merging
272 * prevents the need to run process_entry() on every path
273 * underneath trees that can be trivially merged, and
274 * process_entry() is more expensive than collect_merge_info() --
275 * plus, the second collect_merge_info() will be much faster since
276 * it doesn't have to recurse into the relevant trees.
278 * Values for this flag:
279 * 0 = don't bother, not worth it (or conditions not yet checked)
280 * 1 = conditions for optimization met, optimization worthwhile
281 * 2 = we already did it (don't restart merge yet again)
283 unsigned redo_after_renames;
286 * needed_limit: value needed for inexact rename detection to run
288 * If the current rename limit wasn't high enough for inexact
289 * rename detection to run, this records the limit needed. Otherwise,
290 * this value remains 0.
292 int needed_limit;
295 struct merge_options_internal {
297 * paths: primary data structure in all of merge ort.
299 * The keys of paths:
300 * * are full relative paths from the toplevel of the repository
301 * (e.g. "drivers/firmware/raspberrypi.c").
302 * * store all relevant paths in the repo, both directories and
303 * files (e.g. drivers, drivers/firmware would also be included)
304 * * these keys serve to intern all the path strings, which allows
305 * us to do pointer comparison on directory names instead of
306 * strcmp; we just have to be careful to use the interned strings.
308 * The values of paths:
309 * * either a pointer to a merged_info, or a conflict_info struct
310 * * merged_info contains all relevant information for a
311 * non-conflicted entry.
312 * * conflict_info contains a merged_info, plus any additional
313 * information about a conflict such as the higher orders stages
314 * involved and the names of the paths those came from (handy
315 * once renames get involved).
316 * * a path may start "conflicted" (i.e. point to a conflict_info)
317 * and then a later step (e.g. three-way content merge) determines
318 * it can be cleanly merged, at which point it'll be marked clean
319 * and the algorithm will ignore any data outside the contained
320 * merged_info for that entry
321 * * If an entry remains conflicted, the merged_info portion of a
322 * conflict_info will later be filled with whatever version of
323 * the file should be placed in the working directory (e.g. an
324 * as-merged-as-possible variation that contains conflict markers).
326 struct strmap paths;
329 * conflicted: a subset of keys->values from "paths"
331 * conflicted is basically an optimization between process_entries()
332 * and record_conflicted_index_entries(); the latter could loop over
333 * ALL the entries in paths AGAIN and look for the ones that are
334 * still conflicted, but since process_entries() has to loop over
335 * all of them, it saves the ones it couldn't resolve in this strmap
336 * so that record_conflicted_index_entries() can iterate just the
337 * relevant entries.
339 struct strmap conflicted;
342 * pool: memory pool for fast allocation/deallocation
344 * We allocate room for lots of filenames and auxiliary data
345 * structures in merge_options_internal, and it tends to all be
346 * freed together too. Using a memory pool for these provides a
347 * nice speedup.
349 struct mem_pool pool;
352 * conflicts: logical conflicts and messages stored by _primary_ path
354 * This is a map of pathnames (a subset of the keys in "paths" above)
355 * to struct string_list, with each item's `util` containing a
356 * `struct logical_conflict_info`. Note, though, that for each path,
357 * it only stores the logical conflicts for which that path is the
358 * primary path; the path might be part of additional conflicts.
360 struct strmap conflicts;
363 * renames: various data relating to rename detection
365 struct rename_info renames;
368 * attr_index: hacky minimal index used for renormalization
370 * renormalization code _requires_ an index, though it only needs to
371 * find a .gitattributes file within the index. So, when
372 * renormalization is important, we create a special index with just
373 * that one file.
375 struct index_state attr_index;
378 * current_dir_name, toplevel_dir: temporary vars
380 * These are used in collect_merge_info_callback(), and will set the
381 * various merged_info.directory_name for the various paths we get;
382 * see documentation for that variable and the requirements placed on
383 * that field.
385 const char *current_dir_name;
386 const char *toplevel_dir;
388 /* call_depth: recursion level counter for merging merge bases */
389 int call_depth;
391 /* field that holds submodule conflict information */
392 struct string_list conflicted_submodules;
395 struct conflicted_submodule_item {
396 char *abbrev;
397 int flag;
400 static void conflicted_submodule_item_free(void *util, const char *str)
402 struct conflicted_submodule_item *item = util;
404 free(item->abbrev);
405 free(item);
408 struct version_info {
409 struct object_id oid;
410 unsigned short mode;
413 struct merged_info {
414 /* if is_null, ignore result. otherwise result has oid & mode */
415 struct version_info result;
416 unsigned is_null:1;
419 * clean: whether the path in question is cleanly merged.
421 * see conflict_info.merged for more details.
423 unsigned clean:1;
426 * basename_offset: offset of basename of path.
428 * perf optimization to avoid recomputing offset of final '/'
429 * character in pathname (0 if no '/' in pathname).
431 size_t basename_offset;
434 * directory_name: containing directory name.
436 * Note that we assume directory_name is constructed such that
437 * strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name,
438 * i.e. string equality is equivalent to pointer equality. For this
439 * to hold, we have to be careful setting directory_name.
441 const char *directory_name;
444 struct conflict_info {
446 * merged: the version of the path that will be written to working tree
448 * WARNING: It is critical to check merged.clean and ensure it is 0
449 * before reading any conflict_info fields outside of merged.
450 * Allocated merge_info structs will always have clean set to 1.
451 * Allocated conflict_info structs will have merged.clean set to 0
452 * initially. The merged.clean field is how we know if it is safe
453 * to access other parts of conflict_info besides merged; if a
454 * conflict_info's merged.clean is changed to 1, the rest of the
455 * algorithm is not allowed to look at anything outside of the
456 * merged member anymore.
458 struct merged_info merged;
460 /* oids & modes from each of the three trees for this path */
461 struct version_info stages[3];
463 /* pathnames for each stage; may differ due to rename detection */
464 const char *pathnames[3];
466 /* Whether this path is/was involved in a directory/file conflict */
467 unsigned df_conflict:1;
470 * Whether this path is/was involved in a non-content conflict other
471 * than a directory/file conflict (e.g. rename/rename, rename/delete,
472 * file location based on possible directory rename).
474 unsigned path_conflict:1;
477 * For filemask and dirmask, the ith bit corresponds to whether the
478 * ith entry is a file (filemask) or a directory (dirmask). Thus,
479 * filemask & dirmask is always zero, and filemask | dirmask is at
480 * most 7 but can be less when a path does not appear as either a
481 * file or a directory on at least one side of history.
483 * Note that these masks are related to enum merge_side, as the ith
484 * entry corresponds to side i.
486 * These values come from a traverse_trees() call; more info may be
487 * found looking at tree-walk.h's struct traverse_info,
488 * particularly the documentation above the "fn" member (note that
489 * filemask = mask & ~dirmask from that documentation).
491 unsigned filemask:3;
492 unsigned dirmask:3;
495 * Optimization to track which stages match, to avoid the need to
496 * recompute it in multiple steps. Either 0 or at least 2 bits are
497 * set; if at least 2 bits are set, their corresponding stages match.
499 unsigned match_mask:3;
502 enum conflict_and_info_types {
503 /* "Simple" conflicts and informational messages */
504 INFO_AUTO_MERGING = 0,
505 CONFLICT_CONTENTS, /* text file that failed to merge */
506 CONFLICT_BINARY,
507 CONFLICT_FILE_DIRECTORY,
508 CONFLICT_DISTINCT_MODES,
509 CONFLICT_MODIFY_DELETE,
511 /* Regular rename */
512 CONFLICT_RENAME_RENAME, /* same file renamed differently */
513 CONFLICT_RENAME_COLLIDES, /* rename/add or two files renamed to 1 */
514 CONFLICT_RENAME_DELETE,
516 /* Basic directory rename */
517 CONFLICT_DIR_RENAME_SUGGESTED,
518 INFO_DIR_RENAME_APPLIED,
520 /* Special directory rename cases */
521 INFO_DIR_RENAME_SKIPPED_DUE_TO_RERENAME,
522 CONFLICT_DIR_RENAME_FILE_IN_WAY,
523 CONFLICT_DIR_RENAME_COLLISION,
524 CONFLICT_DIR_RENAME_SPLIT,
526 /* Basic submodule */
527 INFO_SUBMODULE_FAST_FORWARDING,
528 CONFLICT_SUBMODULE_FAILED_TO_MERGE,
530 /* Special submodule cases broken out from FAILED_TO_MERGE */
531 CONFLICT_SUBMODULE_FAILED_TO_MERGE_BUT_POSSIBLE_RESOLUTION,
532 CONFLICT_SUBMODULE_NOT_INITIALIZED,
533 CONFLICT_SUBMODULE_HISTORY_NOT_AVAILABLE,
534 CONFLICT_SUBMODULE_MAY_HAVE_REWINDS,
535 CONFLICT_SUBMODULE_NULL_MERGE_BASE,
537 /* Keep this entry _last_ in the list */
538 NB_CONFLICT_TYPES,
542 * Short description of conflict type, relied upon by external tools.
544 * We can add more entries, but DO NOT change any of these strings. Also,
545 * Order MUST match conflict_info_and_types.
547 static const char *type_short_descriptions[] = {
548 /*** "Simple" conflicts and informational messages ***/
549 [INFO_AUTO_MERGING] = "Auto-merging",
550 [CONFLICT_CONTENTS] = "CONFLICT (contents)",
551 [CONFLICT_BINARY] = "CONFLICT (binary)",
552 [CONFLICT_FILE_DIRECTORY] = "CONFLICT (file/directory)",
553 [CONFLICT_DISTINCT_MODES] = "CONFLICT (distinct modes)",
554 [CONFLICT_MODIFY_DELETE] = "CONFLICT (modify/delete)",
556 /*** Regular rename ***/
557 [CONFLICT_RENAME_RENAME] = "CONFLICT (rename/rename)",
558 [CONFLICT_RENAME_COLLIDES] = "CONFLICT (rename involved in collision)",
559 [CONFLICT_RENAME_DELETE] = "CONFLICT (rename/delete)",
561 /*** Basic directory rename ***/
562 [CONFLICT_DIR_RENAME_SUGGESTED] =
563 "CONFLICT (directory rename suggested)",
564 [INFO_DIR_RENAME_APPLIED] = "Path updated due to directory rename",
566 /*** Special directory rename cases ***/
567 [INFO_DIR_RENAME_SKIPPED_DUE_TO_RERENAME] =
568 "Directory rename skipped since directory was renamed on both sides",
569 [CONFLICT_DIR_RENAME_FILE_IN_WAY] =
570 "CONFLICT (file in way of directory rename)",
571 [CONFLICT_DIR_RENAME_COLLISION] = "CONFLICT(directory rename collision)",
572 [CONFLICT_DIR_RENAME_SPLIT] = "CONFLICT(directory rename unclear split)",
574 /*** Basic submodule ***/
575 [INFO_SUBMODULE_FAST_FORWARDING] = "Fast forwarding submodule",
576 [CONFLICT_SUBMODULE_FAILED_TO_MERGE] = "CONFLICT (submodule)",
578 /*** Special submodule cases broken out from FAILED_TO_MERGE ***/
579 [CONFLICT_SUBMODULE_FAILED_TO_MERGE_BUT_POSSIBLE_RESOLUTION] =
580 "CONFLICT (submodule with possible resolution)",
581 [CONFLICT_SUBMODULE_NOT_INITIALIZED] =
582 "CONFLICT (submodule not initialized)",
583 [CONFLICT_SUBMODULE_HISTORY_NOT_AVAILABLE] =
584 "CONFLICT (submodule history not available)",
585 [CONFLICT_SUBMODULE_MAY_HAVE_REWINDS] =
586 "CONFLICT (submodule may have rewinds)",
587 [CONFLICT_SUBMODULE_NULL_MERGE_BASE] =
588 "CONFLICT (submodule lacks merge base)"
591 struct logical_conflict_info {
592 enum conflict_and_info_types type;
593 struct strvec paths;
596 /*** Function Grouping: various utility functions ***/
599 * For the next three macros, see warning for conflict_info.merged.
601 * In each of the below, mi is a struct merged_info*, and ci was defined
602 * as a struct conflict_info* (but we need to verify ci isn't actually
603 * pointed at a struct merged_info*).
605 * INITIALIZE_CI: Assign ci to mi but only if it's safe; set to NULL otherwise.
606 * VERIFY_CI: Ensure that something we assigned to a conflict_info* is one.
607 * ASSIGN_AND_VERIFY_CI: Similar to VERIFY_CI but do assignment first.
609 #define INITIALIZE_CI(ci, mi) do { \
610 (ci) = (!(mi) || (mi)->clean) ? NULL : (struct conflict_info *)(mi); \
611 } while (0)
612 #define VERIFY_CI(ci) assert(ci && !ci->merged.clean);
613 #define ASSIGN_AND_VERIFY_CI(ci, mi) do { \
614 (ci) = (struct conflict_info *)(mi); \
615 assert((ci) && !(mi)->clean); \
616 } while (0)
618 static void free_strmap_strings(struct strmap *map)
620 struct hashmap_iter iter;
621 struct strmap_entry *entry;
623 strmap_for_each_entry(map, &iter, entry) {
624 free((char*)entry->key);
628 static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,
629 int reinitialize)
631 struct rename_info *renames = &opti->renames;
632 int i;
633 void (*strmap_clear_func)(struct strmap *, int) =
634 reinitialize ? strmap_partial_clear : strmap_clear;
635 void (*strintmap_clear_func)(struct strintmap *) =
636 reinitialize ? strintmap_partial_clear : strintmap_clear;
637 void (*strset_clear_func)(struct strset *) =
638 reinitialize ? strset_partial_clear : strset_clear;
640 strmap_clear_func(&opti->paths, 0);
643 * All keys and values in opti->conflicted are a subset of those in
644 * opti->paths. We don't want to deallocate anything twice, so we
645 * don't free the keys and we pass 0 for free_values.
647 strmap_clear_func(&opti->conflicted, 0);
649 if (opti->attr_index.cache_nr) /* true iff opt->renormalize */
650 discard_index(&opti->attr_index);
652 /* Free memory used by various renames maps */
653 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; ++i) {
654 strintmap_clear_func(&renames->dirs_removed[i]);
655 strmap_clear_func(&renames->dir_renames[i], 0);
656 strintmap_clear_func(&renames->relevant_sources[i]);
657 if (!reinitialize)
658 assert(renames->cached_pairs_valid_side == 0);
659 if (i != renames->cached_pairs_valid_side &&
660 -1 != renames->cached_pairs_valid_side) {
661 strset_clear_func(&renames->cached_target_names[i]);
662 strmap_clear_func(&renames->cached_pairs[i], 1);
663 strset_clear_func(&renames->cached_irrelevant[i]);
664 partial_clear_dir_rename_count(&renames->dir_rename_count[i]);
665 if (!reinitialize)
666 strmap_clear(&renames->dir_rename_count[i], 1);
669 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; ++i) {
670 strintmap_clear_func(&renames->deferred[i].possible_trivial_merges);
671 strset_clear_func(&renames->deferred[i].target_dirs);
672 renames->deferred[i].trivial_merges_okay = 1; /* 1 == maybe */
674 renames->cached_pairs_valid_side = 0;
675 renames->dir_rename_mask = 0;
677 if (!reinitialize) {
678 struct hashmap_iter iter;
679 struct strmap_entry *e;
681 /* Release and free each strbuf found in output */
682 strmap_for_each_entry(&opti->conflicts, &iter, e) {
683 struct string_list *list = e->value;
684 for (int i = 0; i < list->nr; i++) {
685 struct logical_conflict_info *info =
686 list->items[i].util;
687 strvec_clear(&info->paths);
690 * While strictly speaking we don't need to
691 * free(conflicts) here because we could pass
692 * free_values=1 when calling strmap_clear() on
693 * opti->conflicts, that would require strmap_clear
694 * to do another strmap_for_each_entry() loop, so we
695 * just free it while we're iterating anyway.
697 string_list_clear(list, 1);
698 free(list);
700 strmap_clear(&opti->conflicts, 0);
703 mem_pool_discard(&opti->pool, 0);
705 string_list_clear_func(&opti->conflicted_submodules,
706 conflicted_submodule_item_free);
708 /* Clean out callback_data as well. */
709 FREE_AND_NULL(renames->callback_data);
710 renames->callback_data_nr = renames->callback_data_alloc = 0;
713 __attribute__((format (printf, 2, 3)))
714 static int err(struct merge_options *opt, const char *err, ...)
716 va_list params;
717 struct strbuf sb = STRBUF_INIT;
719 strbuf_addstr(&sb, "error: ");
720 va_start(params, err);
721 strbuf_vaddf(&sb, err, params);
722 va_end(params);
724 error("%s", sb.buf);
725 strbuf_release(&sb);
727 return -1;
730 static void format_commit(struct strbuf *sb,
731 int indent,
732 struct repository *repo,
733 struct commit *commit)
735 struct merge_remote_desc *desc;
736 struct pretty_print_context ctx = {0};
737 ctx.abbrev = DEFAULT_ABBREV;
739 strbuf_addchars(sb, ' ', indent);
740 desc = merge_remote_util(commit);
741 if (desc) {
742 strbuf_addf(sb, "virtual %s\n", desc->name);
743 return;
746 repo_format_commit_message(repo, commit, "%h %s", sb, &ctx);
747 strbuf_addch(sb, '\n');
750 __attribute__((format (printf, 8, 9)))
751 static void path_msg(struct merge_options *opt,
752 enum conflict_and_info_types type,
753 int omittable_hint, /* skippable under --remerge-diff */
754 const char *primary_path,
755 const char *other_path_1, /* may be NULL */
756 const char *other_path_2, /* may be NULL */
757 struct string_list *other_paths, /* may be NULL */
758 const char *fmt, ...)
760 va_list ap;
761 struct string_list *path_conflicts;
762 struct logical_conflict_info *info;
763 struct strbuf buf = STRBUF_INIT;
764 struct strbuf *dest;
765 struct strbuf tmp = STRBUF_INIT;
767 /* Sanity checks */
768 assert(omittable_hint ==
769 !starts_with(type_short_descriptions[type], "CONFLICT") ||
770 type == CONFLICT_DIR_RENAME_SUGGESTED);
771 if (opt->record_conflict_msgs_as_headers && omittable_hint)
772 return; /* Do not record mere hints in headers */
773 if (opt->priv->call_depth && opt->verbosity < 5)
774 return; /* Ignore messages from inner merges */
776 /* Ensure path_conflicts (ptr to array of logical_conflict) allocated */
777 path_conflicts = strmap_get(&opt->priv->conflicts, primary_path);
778 if (!path_conflicts) {
779 path_conflicts = xmalloc(sizeof(*path_conflicts));
780 string_list_init_dup(path_conflicts);
781 strmap_put(&opt->priv->conflicts, primary_path, path_conflicts);
784 /* Add a logical_conflict at the end to store info from this call */
785 info = xcalloc(1, sizeof(*info));
786 info->type = type;
787 strvec_init(&info->paths);
789 /* Handle the list of paths */
790 strvec_push(&info->paths, primary_path);
791 if (other_path_1)
792 strvec_push(&info->paths, other_path_1);
793 if (other_path_2)
794 strvec_push(&info->paths, other_path_2);
795 if (other_paths)
796 for (int i = 0; i < other_paths->nr; i++)
797 strvec_push(&info->paths, other_paths->items[i].string);
799 /* Handle message and its format, in normal case */
800 dest = (opt->record_conflict_msgs_as_headers ? &tmp : &buf);
802 va_start(ap, fmt);
803 if (opt->priv->call_depth) {
804 strbuf_addchars(dest, ' ', 2);
805 strbuf_addstr(dest, "From inner merge:");
806 strbuf_addchars(dest, ' ', opt->priv->call_depth * 2);
808 strbuf_vaddf(dest, fmt, ap);
809 va_end(ap);
811 /* Handle specialized formatting of message under --remerge-diff */
812 if (opt->record_conflict_msgs_as_headers) {
813 int i_sb = 0, i_tmp = 0;
815 /* Start with the specified prefix */
816 if (opt->msg_header_prefix)
817 strbuf_addf(&buf, "%s ", opt->msg_header_prefix);
819 /* Copy tmp to sb, adding spaces after newlines */
820 strbuf_grow(&buf, buf.len + 2*tmp.len); /* more than sufficient */
821 for (; i_tmp < tmp.len; i_tmp++, i_sb++) {
822 /* Copy next character from tmp to sb */
823 buf.buf[buf.len + i_sb] = tmp.buf[i_tmp];
825 /* If we copied a newline, add a space */
826 if (tmp.buf[i_tmp] == '\n')
827 buf.buf[++i_sb] = ' ';
829 /* Update length and ensure it's NUL-terminated */
830 buf.len += i_sb;
831 buf.buf[buf.len] = '\0';
833 strbuf_release(&tmp);
835 string_list_append_nodup(path_conflicts, strbuf_detach(&buf, NULL))
836 ->util = info;
839 static struct diff_filespec *pool_alloc_filespec(struct mem_pool *pool,
840 const char *path)
842 /* Similar to alloc_filespec(), but allocate from pool and reuse path */
843 struct diff_filespec *spec;
845 spec = mem_pool_calloc(pool, 1, sizeof(*spec));
846 spec->path = (char*)path; /* spec won't modify it */
848 spec->count = 1;
849 spec->is_binary = -1;
850 return spec;
853 static struct diff_filepair *pool_diff_queue(struct mem_pool *pool,
854 struct diff_queue_struct *queue,
855 struct diff_filespec *one,
856 struct diff_filespec *two)
858 /* Same code as diff_queue(), except allocate from pool */
859 struct diff_filepair *dp;
861 dp = mem_pool_calloc(pool, 1, sizeof(*dp));
862 dp->one = one;
863 dp->two = two;
864 if (queue)
865 diff_q(queue, dp);
866 return dp;
869 /* add a string to a strbuf, but converting "/" to "_" */
870 static void add_flattened_path(struct strbuf *out, const char *s)
872 size_t i = out->len;
873 strbuf_addstr(out, s);
874 for (; i < out->len; i++)
875 if (out->buf[i] == '/')
876 out->buf[i] = '_';
879 static char *unique_path(struct merge_options *opt,
880 const char *path,
881 const char *branch)
883 char *ret = NULL;
884 struct strbuf newpath = STRBUF_INIT;
885 int suffix = 0;
886 size_t base_len;
887 struct strmap *existing_paths = &opt->priv->paths;
889 strbuf_addf(&newpath, "%s~", path);
890 add_flattened_path(&newpath, branch);
892 base_len = newpath.len;
893 while (strmap_contains(existing_paths, newpath.buf)) {
894 strbuf_setlen(&newpath, base_len);
895 strbuf_addf(&newpath, "_%d", suffix++);
898 /* Track the new path in our memory pool */
899 ret = mem_pool_alloc(&opt->priv->pool, newpath.len + 1);
900 memcpy(ret, newpath.buf, newpath.len + 1);
901 strbuf_release(&newpath);
902 return ret;
905 /*** Function Grouping: functions related to collect_merge_info() ***/
907 static int traverse_trees_wrapper_callback(int n,
908 unsigned long mask,
909 unsigned long dirmask,
910 struct name_entry *names,
911 struct traverse_info *info)
913 struct merge_options *opt = info->data;
914 struct rename_info *renames = &opt->priv->renames;
915 unsigned filemask = mask & ~dirmask;
917 assert(n==3);
919 if (!renames->callback_data_traverse_path)
920 renames->callback_data_traverse_path = xstrdup(info->traverse_path);
922 if (filemask && filemask == renames->dir_rename_mask)
923 renames->dir_rename_mask = 0x07;
925 ALLOC_GROW(renames->callback_data, renames->callback_data_nr + 1,
926 renames->callback_data_alloc);
927 renames->callback_data[renames->callback_data_nr].mask = mask;
928 renames->callback_data[renames->callback_data_nr].dirmask = dirmask;
929 COPY_ARRAY(renames->callback_data[renames->callback_data_nr].names,
930 names, 3);
931 renames->callback_data_nr++;
933 return mask;
937 * Much like traverse_trees(), BUT:
938 * - read all the tree entries FIRST, saving them
939 * - note that the above step provides an opportunity to compute necessary
940 * additional details before the "real" traversal
941 * - loop through the saved entries and call the original callback on them
943 static int traverse_trees_wrapper(struct index_state *istate,
944 int n,
945 struct tree_desc *t,
946 struct traverse_info *info)
948 int ret, i, old_offset;
949 traverse_callback_t old_fn;
950 char *old_callback_data_traverse_path;
951 struct merge_options *opt = info->data;
952 struct rename_info *renames = &opt->priv->renames;
954 assert(renames->dir_rename_mask == 2 || renames->dir_rename_mask == 4);
956 old_callback_data_traverse_path = renames->callback_data_traverse_path;
957 old_fn = info->fn;
958 old_offset = renames->callback_data_nr;
960 renames->callback_data_traverse_path = NULL;
961 info->fn = traverse_trees_wrapper_callback;
962 ret = traverse_trees(istate, n, t, info);
963 if (ret < 0)
964 return ret;
966 info->traverse_path = renames->callback_data_traverse_path;
967 info->fn = old_fn;
968 for (i = old_offset; i < renames->callback_data_nr; ++i) {
969 info->fn(n,
970 renames->callback_data[i].mask,
971 renames->callback_data[i].dirmask,
972 renames->callback_data[i].names,
973 info);
976 renames->callback_data_nr = old_offset;
977 free(renames->callback_data_traverse_path);
978 renames->callback_data_traverse_path = old_callback_data_traverse_path;
979 info->traverse_path = NULL;
980 return 0;
983 static void setup_path_info(struct merge_options *opt,
984 struct string_list_item *result,
985 const char *current_dir_name,
986 int current_dir_name_len,
987 char *fullpath, /* we'll take over ownership */
988 struct name_entry *names,
989 struct name_entry *merged_version,
990 unsigned is_null, /* boolean */
991 unsigned df_conflict, /* boolean */
992 unsigned filemask,
993 unsigned dirmask,
994 int resolved /* boolean */)
996 /* result->util is void*, so mi is a convenience typed variable */
997 struct merged_info *mi;
999 assert(!is_null || resolved);
1000 assert(!df_conflict || !resolved); /* df_conflict implies !resolved */
1001 assert(resolved == (merged_version != NULL));
1003 mi = mem_pool_calloc(&opt->priv->pool, 1,
1004 resolved ? sizeof(struct merged_info) :
1005 sizeof(struct conflict_info));
1006 mi->directory_name = current_dir_name;
1007 mi->basename_offset = current_dir_name_len;
1008 mi->clean = !!resolved;
1009 if (resolved) {
1010 mi->result.mode = merged_version->mode;
1011 oidcpy(&mi->result.oid, &merged_version->oid);
1012 mi->is_null = !!is_null;
1013 } else {
1014 int i;
1015 struct conflict_info *ci;
1017 ASSIGN_AND_VERIFY_CI(ci, mi);
1018 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
1019 ci->pathnames[i] = fullpath;
1020 ci->stages[i].mode = names[i].mode;
1021 oidcpy(&ci->stages[i].oid, &names[i].oid);
1023 ci->filemask = filemask;
1024 ci->dirmask = dirmask;
1025 ci->df_conflict = !!df_conflict;
1026 if (dirmask)
1028 * Assume is_null for now, but if we have entries
1029 * under the directory then when it is complete in
1030 * write_completed_directory() it'll update this.
1031 * Also, for D/F conflicts, we have to handle the
1032 * directory first, then clear this bit and process
1033 * the file to see how it is handled -- that occurs
1034 * near the top of process_entry().
1036 mi->is_null = 1;
1038 strmap_put(&opt->priv->paths, fullpath, mi);
1039 result->string = fullpath;
1040 result->util = mi;
1043 static void add_pair(struct merge_options *opt,
1044 struct name_entry *names,
1045 const char *pathname,
1046 unsigned side,
1047 unsigned is_add /* if false, is_delete */,
1048 unsigned match_mask,
1049 unsigned dir_rename_mask)
1051 struct diff_filespec *one, *two;
1052 struct rename_info *renames = &opt->priv->renames;
1053 int names_idx = is_add ? side : 0;
1055 if (is_add) {
1056 assert(match_mask == 0 || match_mask == 6);
1057 if (strset_contains(&renames->cached_target_names[side],
1058 pathname))
1059 return;
1060 } else {
1061 unsigned content_relevant = (match_mask == 0);
1062 unsigned location_relevant = (dir_rename_mask == 0x07);
1064 assert(match_mask == 0 || match_mask == 3 || match_mask == 5);
1067 * If pathname is found in cached_irrelevant[side] due to
1068 * previous pick but for this commit content is relevant,
1069 * then we need to remove it from cached_irrelevant.
1071 if (content_relevant)
1072 /* strset_remove is no-op if strset doesn't have key */
1073 strset_remove(&renames->cached_irrelevant[side],
1074 pathname);
1077 * We do not need to re-detect renames for paths that we already
1078 * know the pairing, i.e. for cached_pairs (or
1079 * cached_irrelevant). However, handle_deferred_entries() needs
1080 * to loop over the union of keys from relevant_sources[side] and
1081 * cached_pairs[side], so for simplicity we set relevant_sources
1082 * for all the cached_pairs too and then strip them back out in
1083 * prune_cached_from_relevant() at the beginning of
1084 * detect_regular_renames().
1086 if (content_relevant || location_relevant) {
1087 /* content_relevant trumps location_relevant */
1088 strintmap_set(&renames->relevant_sources[side], pathname,
1089 content_relevant ? RELEVANT_CONTENT : RELEVANT_LOCATION);
1093 * Avoid creating pair if we've already cached rename results.
1094 * Note that we do this after setting relevant_sources[side]
1095 * as noted in the comment above.
1097 if (strmap_contains(&renames->cached_pairs[side], pathname) ||
1098 strset_contains(&renames->cached_irrelevant[side], pathname))
1099 return;
1102 one = pool_alloc_filespec(&opt->priv->pool, pathname);
1103 two = pool_alloc_filespec(&opt->priv->pool, pathname);
1104 fill_filespec(is_add ? two : one,
1105 &names[names_idx].oid, 1, names[names_idx].mode);
1106 pool_diff_queue(&opt->priv->pool, &renames->pairs[side], one, two);
1109 static void collect_rename_info(struct merge_options *opt,
1110 struct name_entry *names,
1111 const char *dirname,
1112 const char *fullname,
1113 unsigned filemask,
1114 unsigned dirmask,
1115 unsigned match_mask)
1117 struct rename_info *renames = &opt->priv->renames;
1118 unsigned side;
1121 * Update dir_rename_mask (determines ignore-rename-source validity)
1123 * dir_rename_mask helps us keep track of when directory rename
1124 * detection may be relevant. Basically, whenver a directory is
1125 * removed on one side of history, and a file is added to that
1126 * directory on the other side of history, directory rename
1127 * detection is relevant (meaning we have to detect renames for all
1128 * files within that directory to deduce where the directory
1129 * moved). Also, whenever a directory needs directory rename
1130 * detection, due to the "majority rules" choice for where to move
1131 * it (see t6423 testcase 1f), we also need to detect renames for
1132 * all files within subdirectories of that directory as well.
1134 * Here we haven't looked at files within the directory yet, we are
1135 * just looking at the directory itself. So, if we aren't yet in
1136 * a case where a parent directory needed directory rename detection
1137 * (i.e. dir_rename_mask != 0x07), and if the directory was removed
1138 * on one side of history, record the mask of the other side of
1139 * history in dir_rename_mask.
1141 if (renames->dir_rename_mask != 0x07 &&
1142 (dirmask == 3 || dirmask == 5)) {
1143 /* simple sanity check */
1144 assert(renames->dir_rename_mask == 0 ||
1145 renames->dir_rename_mask == (dirmask & ~1));
1146 /* update dir_rename_mask; have it record mask of new side */
1147 renames->dir_rename_mask = (dirmask & ~1);
1150 /* Update dirs_removed, as needed */
1151 if (dirmask == 1 || dirmask == 3 || dirmask == 5) {
1152 /* absent_mask = 0x07 - dirmask; sides = absent_mask/2 */
1153 unsigned sides = (0x07 - dirmask)/2;
1154 unsigned relevance = (renames->dir_rename_mask == 0x07) ?
1155 RELEVANT_FOR_ANCESTOR : NOT_RELEVANT;
1157 * Record relevance of this directory. However, note that
1158 * when collect_merge_info_callback() recurses into this
1159 * directory and calls collect_rename_info() on paths
1160 * within that directory, if we find a path that was added
1161 * to this directory on the other side of history, we will
1162 * upgrade this value to RELEVANT_FOR_SELF; see below.
1164 if (sides & 1)
1165 strintmap_set(&renames->dirs_removed[1], fullname,
1166 relevance);
1167 if (sides & 2)
1168 strintmap_set(&renames->dirs_removed[2], fullname,
1169 relevance);
1173 * Here's the block that potentially upgrades to RELEVANT_FOR_SELF.
1174 * When we run across a file added to a directory. In such a case,
1175 * find the directory of the file and upgrade its relevance.
1177 if (renames->dir_rename_mask == 0x07 &&
1178 (filemask == 2 || filemask == 4)) {
1180 * Need directory rename for parent directory on other side
1181 * of history from added file. Thus
1182 * side = (~filemask & 0x06) >> 1
1183 * or
1184 * side = 3 - (filemask/2).
1186 unsigned side = 3 - (filemask >> 1);
1187 strintmap_set(&renames->dirs_removed[side], dirname,
1188 RELEVANT_FOR_SELF);
1191 if (filemask == 0 || filemask == 7)
1192 return;
1194 for (side = MERGE_SIDE1; side <= MERGE_SIDE2; ++side) {
1195 unsigned side_mask = (1 << side);
1197 /* Check for deletion on side */
1198 if ((filemask & 1) && !(filemask & side_mask))
1199 add_pair(opt, names, fullname, side, 0 /* delete */,
1200 match_mask & filemask,
1201 renames->dir_rename_mask);
1203 /* Check for addition on side */
1204 if (!(filemask & 1) && (filemask & side_mask))
1205 add_pair(opt, names, fullname, side, 1 /* add */,
1206 match_mask & filemask,
1207 renames->dir_rename_mask);
1211 static int collect_merge_info_callback(int n,
1212 unsigned long mask,
1213 unsigned long dirmask,
1214 struct name_entry *names,
1215 struct traverse_info *info)
1218 * n is 3. Always.
1219 * common ancestor (mbase) has mask 1, and stored in index 0 of names
1220 * head of side 1 (side1) has mask 2, and stored in index 1 of names
1221 * head of side 2 (side2) has mask 4, and stored in index 2 of names
1223 struct merge_options *opt = info->data;
1224 struct merge_options_internal *opti = opt->priv;
1225 struct rename_info *renames = &opt->priv->renames;
1226 struct string_list_item pi; /* Path Info */
1227 struct conflict_info *ci; /* typed alias to pi.util (which is void*) */
1228 struct name_entry *p;
1229 size_t len;
1230 char *fullpath;
1231 const char *dirname = opti->current_dir_name;
1232 unsigned prev_dir_rename_mask = renames->dir_rename_mask;
1233 unsigned filemask = mask & ~dirmask;
1234 unsigned match_mask = 0; /* will be updated below */
1235 unsigned mbase_null = !(mask & 1);
1236 unsigned side1_null = !(mask & 2);
1237 unsigned side2_null = !(mask & 4);
1238 unsigned side1_matches_mbase = (!side1_null && !mbase_null &&
1239 names[0].mode == names[1].mode &&
1240 oideq(&names[0].oid, &names[1].oid));
1241 unsigned side2_matches_mbase = (!side2_null && !mbase_null &&
1242 names[0].mode == names[2].mode &&
1243 oideq(&names[0].oid, &names[2].oid));
1244 unsigned sides_match = (!side1_null && !side2_null &&
1245 names[1].mode == names[2].mode &&
1246 oideq(&names[1].oid, &names[2].oid));
1249 * Note: When a path is a file on one side of history and a directory
1250 * in another, we have a directory/file conflict. In such cases, if
1251 * the conflict doesn't resolve from renames and deletions, then we
1252 * always leave directories where they are and move files out of the
1253 * way. Thus, while struct conflict_info has a df_conflict field to
1254 * track such conflicts, we ignore that field for any directories at
1255 * a path and only pay attention to it for files at the given path.
1256 * The fact that we leave directories were they are also means that
1257 * we do not need to worry about getting additional df_conflict
1258 * information propagated from parent directories down to children
1259 * (unlike, say traverse_trees_recursive() in unpack-trees.c, which
1260 * sets a newinfo.df_conflicts field specifically to propagate it).
1262 unsigned df_conflict = (filemask != 0) && (dirmask != 0);
1264 /* n = 3 is a fundamental assumption. */
1265 if (n != 3)
1266 BUG("Called collect_merge_info_callback wrong");
1269 * A bunch of sanity checks verifying that traverse_trees() calls
1270 * us the way I expect. Could just remove these at some point,
1271 * though maybe they are helpful to future code readers.
1273 assert(mbase_null == is_null_oid(&names[0].oid));
1274 assert(side1_null == is_null_oid(&names[1].oid));
1275 assert(side2_null == is_null_oid(&names[2].oid));
1276 assert(!mbase_null || !side1_null || !side2_null);
1277 assert(mask > 0 && mask < 8);
1279 /* Determine match_mask */
1280 if (side1_matches_mbase)
1281 match_mask = (side2_matches_mbase ? 7 : 3);
1282 else if (side2_matches_mbase)
1283 match_mask = 5;
1284 else if (sides_match)
1285 match_mask = 6;
1288 * Get the name of the relevant filepath, which we'll pass to
1289 * setup_path_info() for tracking.
1291 p = names;
1292 while (!p->mode)
1293 p++;
1294 len = traverse_path_len(info, p->pathlen);
1296 /* +1 in both of the following lines to include the NUL byte */
1297 fullpath = mem_pool_alloc(&opt->priv->pool, len + 1);
1298 make_traverse_path(fullpath, len + 1, info, p->path, p->pathlen);
1301 * If mbase, side1, and side2 all match, we can resolve early. Even
1302 * if these are trees, there will be no renames or anything
1303 * underneath.
1305 if (side1_matches_mbase && side2_matches_mbase) {
1306 /* mbase, side1, & side2 all match; use mbase as resolution */
1307 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
1308 names, names+0, mbase_null, 0 /* df_conflict */,
1309 filemask, dirmask, 1 /* resolved */);
1310 return mask;
1314 * If the sides match, and all three paths are present and are
1315 * files, then we can take either as the resolution. We can't do
1316 * this with trees, because there may be rename sources from the
1317 * merge_base.
1319 if (sides_match && filemask == 0x07) {
1320 /* use side1 (== side2) version as resolution */
1321 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
1322 names, names+1, side1_null, 0,
1323 filemask, dirmask, 1);
1324 return mask;
1328 * If side1 matches mbase and all three paths are present and are
1329 * files, then we can use side2 as the resolution. We cannot
1330 * necessarily do so this for trees, because there may be rename
1331 * destinations within side2.
1333 if (side1_matches_mbase && filemask == 0x07) {
1334 /* use side2 version as resolution */
1335 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
1336 names, names+2, side2_null, 0,
1337 filemask, dirmask, 1);
1338 return mask;
1341 /* Similar to above but swapping sides 1 and 2 */
1342 if (side2_matches_mbase && filemask == 0x07) {
1343 /* use side1 version as resolution */
1344 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
1345 names, names+1, side1_null, 0,
1346 filemask, dirmask, 1);
1347 return mask;
1351 * Sometimes we can tell that a source path need not be included in
1352 * rename detection -- namely, whenever either
1353 * side1_matches_mbase && side2_null
1354 * or
1355 * side2_matches_mbase && side1_null
1356 * However, we call collect_rename_info() even in those cases,
1357 * because exact renames are cheap and would let us remove both a
1358 * source and destination path. We'll cull the unneeded sources
1359 * later.
1361 collect_rename_info(opt, names, dirname, fullpath,
1362 filemask, dirmask, match_mask);
1365 * None of the special cases above matched, so we have a
1366 * provisional conflict. (Rename detection might allow us to
1367 * unconflict some more cases, but that comes later so all we can
1368 * do now is record the different non-null file hashes.)
1370 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
1371 names, NULL, 0, df_conflict, filemask, dirmask, 0);
1373 ci = pi.util;
1374 VERIFY_CI(ci);
1375 ci->match_mask = match_mask;
1377 /* If dirmask, recurse into subdirectories */
1378 if (dirmask) {
1379 struct traverse_info newinfo;
1380 struct tree_desc t[3];
1381 void *buf[3] = {NULL, NULL, NULL};
1382 const char *original_dir_name;
1383 int i, ret, side;
1386 * Check for whether we can avoid recursing due to one side
1387 * matching the merge base. The side that does NOT match is
1388 * the one that might have a rename destination we need.
1390 assert(!side1_matches_mbase || !side2_matches_mbase);
1391 side = side1_matches_mbase ? MERGE_SIDE2 :
1392 side2_matches_mbase ? MERGE_SIDE1 : MERGE_BASE;
1393 if (filemask == 0 && (dirmask == 2 || dirmask == 4)) {
1395 * Also defer recursing into new directories; set up a
1396 * few variables to let us do so.
1398 ci->match_mask = (7 - dirmask);
1399 side = dirmask / 2;
1401 if (renames->dir_rename_mask != 0x07 &&
1402 side != MERGE_BASE &&
1403 renames->deferred[side].trivial_merges_okay &&
1404 !strset_contains(&renames->deferred[side].target_dirs,
1405 pi.string)) {
1406 strintmap_set(&renames->deferred[side].possible_trivial_merges,
1407 pi.string, renames->dir_rename_mask);
1408 renames->dir_rename_mask = prev_dir_rename_mask;
1409 return mask;
1412 /* We need to recurse */
1413 ci->match_mask &= filemask;
1414 newinfo = *info;
1415 newinfo.prev = info;
1416 newinfo.name = p->path;
1417 newinfo.namelen = p->pathlen;
1418 newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1);
1420 * If this directory we are about to recurse into cared about
1421 * its parent directory (the current directory) having a D/F
1422 * conflict, then we'd propagate the masks in this way:
1423 * newinfo.df_conflicts |= (mask & ~dirmask);
1424 * But we don't worry about propagating D/F conflicts. (See
1425 * comment near setting of local df_conflict variable near
1426 * the beginning of this function).
1429 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
1430 if (i == 1 && side1_matches_mbase)
1431 t[1] = t[0];
1432 else if (i == 2 && side2_matches_mbase)
1433 t[2] = t[0];
1434 else if (i == 2 && sides_match)
1435 t[2] = t[1];
1436 else {
1437 const struct object_id *oid = NULL;
1438 if (dirmask & 1)
1439 oid = &names[i].oid;
1440 buf[i] = fill_tree_descriptor(opt->repo,
1441 t + i, oid);
1443 dirmask >>= 1;
1446 original_dir_name = opti->current_dir_name;
1447 opti->current_dir_name = pi.string;
1448 if (renames->dir_rename_mask == 0 ||
1449 renames->dir_rename_mask == 0x07)
1450 ret = traverse_trees(NULL, 3, t, &newinfo);
1451 else
1452 ret = traverse_trees_wrapper(NULL, 3, t, &newinfo);
1453 opti->current_dir_name = original_dir_name;
1454 renames->dir_rename_mask = prev_dir_rename_mask;
1456 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++)
1457 free(buf[i]);
1459 if (ret < 0)
1460 return -1;
1463 return mask;
1466 static void resolve_trivial_directory_merge(struct conflict_info *ci, int side)
1468 VERIFY_CI(ci);
1469 assert((side == 1 && ci->match_mask == 5) ||
1470 (side == 2 && ci->match_mask == 3));
1471 oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
1472 ci->merged.result.mode = ci->stages[side].mode;
1473 ci->merged.is_null = is_null_oid(&ci->stages[side].oid);
1474 ci->match_mask = 0;
1475 ci->merged.clean = 1; /* (ci->filemask == 0); */
1478 static int handle_deferred_entries(struct merge_options *opt,
1479 struct traverse_info *info)
1481 struct rename_info *renames = &opt->priv->renames;
1482 struct hashmap_iter iter;
1483 struct strmap_entry *entry;
1484 int side, ret = 0;
1485 int path_count_before, path_count_after = 0;
1487 path_count_before = strmap_get_size(&opt->priv->paths);
1488 for (side = MERGE_SIDE1; side <= MERGE_SIDE2; side++) {
1489 unsigned optimization_okay = 1;
1490 struct strintmap copy;
1492 /* Loop over the set of paths we need to know rename info for */
1493 strset_for_each_entry(&renames->relevant_sources[side],
1494 &iter, entry) {
1495 char *rename_target, *dir, *dir_marker;
1496 struct strmap_entry *e;
1499 * If we don't know delete/rename info for this path,
1500 * then we need to recurse into all trees to get all
1501 * adds to make sure we have it.
1503 if (strset_contains(&renames->cached_irrelevant[side],
1504 entry->key))
1505 continue;
1506 e = strmap_get_entry(&renames->cached_pairs[side],
1507 entry->key);
1508 if (!e) {
1509 optimization_okay = 0;
1510 break;
1513 /* If this is a delete, we have enough info already */
1514 rename_target = e->value;
1515 if (!rename_target)
1516 continue;
1518 /* If we already walked the rename target, we're good */
1519 if (strmap_contains(&opt->priv->paths, rename_target))
1520 continue;
1523 * Otherwise, we need to get a list of directories that
1524 * will need to be recursed into to get this
1525 * rename_target.
1527 dir = xstrdup(rename_target);
1528 while ((dir_marker = strrchr(dir, '/'))) {
1529 *dir_marker = '\0';
1530 if (strset_contains(&renames->deferred[side].target_dirs,
1531 dir))
1532 break;
1533 strset_add(&renames->deferred[side].target_dirs,
1534 dir);
1536 free(dir);
1538 renames->deferred[side].trivial_merges_okay = optimization_okay;
1540 * We need to recurse into any directories in
1541 * possible_trivial_merges[side] found in target_dirs[side].
1542 * But when we recurse, we may need to queue up some of the
1543 * subdirectories for possible_trivial_merges[side]. Since
1544 * we can't safely iterate through a hashmap while also adding
1545 * entries, move the entries into 'copy', iterate over 'copy',
1546 * and then we'll also iterate anything added into
1547 * possible_trivial_merges[side] once this loop is done.
1549 copy = renames->deferred[side].possible_trivial_merges;
1550 strintmap_init_with_options(&renames->deferred[side].possible_trivial_merges,
1552 &opt->priv->pool,
1554 strintmap_for_each_entry(&copy, &iter, entry) {
1555 const char *path = entry->key;
1556 unsigned dir_rename_mask = (intptr_t)entry->value;
1557 struct conflict_info *ci;
1558 unsigned dirmask;
1559 struct tree_desc t[3];
1560 void *buf[3] = {NULL,};
1561 int i;
1563 ci = strmap_get(&opt->priv->paths, path);
1564 VERIFY_CI(ci);
1565 dirmask = ci->dirmask;
1567 if (optimization_okay &&
1568 !strset_contains(&renames->deferred[side].target_dirs,
1569 path)) {
1570 resolve_trivial_directory_merge(ci, side);
1571 continue;
1574 info->name = path;
1575 info->namelen = strlen(path);
1576 info->pathlen = info->namelen + 1;
1578 for (i = 0; i < 3; i++, dirmask >>= 1) {
1579 if (i == 1 && ci->match_mask == 3)
1580 t[1] = t[0];
1581 else if (i == 2 && ci->match_mask == 5)
1582 t[2] = t[0];
1583 else if (i == 2 && ci->match_mask == 6)
1584 t[2] = t[1];
1585 else {
1586 const struct object_id *oid = NULL;
1587 if (dirmask & 1)
1588 oid = &ci->stages[i].oid;
1589 buf[i] = fill_tree_descriptor(opt->repo,
1590 t+i, oid);
1594 ci->match_mask &= ci->filemask;
1595 opt->priv->current_dir_name = path;
1596 renames->dir_rename_mask = dir_rename_mask;
1597 if (renames->dir_rename_mask == 0 ||
1598 renames->dir_rename_mask == 0x07)
1599 ret = traverse_trees(NULL, 3, t, info);
1600 else
1601 ret = traverse_trees_wrapper(NULL, 3, t, info);
1603 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++)
1604 free(buf[i]);
1606 if (ret < 0)
1607 return ret;
1609 strintmap_clear(&copy);
1610 strintmap_for_each_entry(&renames->deferred[side].possible_trivial_merges,
1611 &iter, entry) {
1612 const char *path = entry->key;
1613 struct conflict_info *ci;
1615 ci = strmap_get(&opt->priv->paths, path);
1616 VERIFY_CI(ci);
1618 assert(renames->deferred[side].trivial_merges_okay &&
1619 !strset_contains(&renames->deferred[side].target_dirs,
1620 path));
1621 resolve_trivial_directory_merge(ci, side);
1623 if (!optimization_okay || path_count_after)
1624 path_count_after = strmap_get_size(&opt->priv->paths);
1626 if (path_count_after) {
1628 * The choice of wanted_factor here does not affect
1629 * correctness, only performance. When the
1630 * path_count_after / path_count_before
1631 * ratio is high, redoing after renames is a big
1632 * performance boost. I suspect that redoing is a wash
1633 * somewhere near a value of 2, and below that redoing will
1634 * slow things down. I applied a fudge factor and picked
1635 * 3; see the commit message when this was introduced for
1636 * back of the envelope calculations for this ratio.
1638 const int wanted_factor = 3;
1640 /* We should only redo collect_merge_info one time */
1641 assert(renames->redo_after_renames == 0);
1643 if (path_count_after / path_count_before >= wanted_factor) {
1644 renames->redo_after_renames = 1;
1645 renames->cached_pairs_valid_side = -1;
1647 } else if (renames->redo_after_renames == 2)
1648 renames->redo_after_renames = 0;
1649 return ret;
1652 static int collect_merge_info(struct merge_options *opt,
1653 struct tree *merge_base,
1654 struct tree *side1,
1655 struct tree *side2)
1657 int ret;
1658 struct tree_desc t[3];
1659 struct traverse_info info;
1661 opt->priv->toplevel_dir = "";
1662 opt->priv->current_dir_name = opt->priv->toplevel_dir;
1663 setup_traverse_info(&info, opt->priv->toplevel_dir);
1664 info.fn = collect_merge_info_callback;
1665 info.data = opt;
1666 info.show_all_errors = 1;
1668 parse_tree(merge_base);
1669 parse_tree(side1);
1670 parse_tree(side2);
1671 init_tree_desc(t + 0, merge_base->buffer, merge_base->size);
1672 init_tree_desc(t + 1, side1->buffer, side1->size);
1673 init_tree_desc(t + 2, side2->buffer, side2->size);
1675 trace2_region_enter("merge", "traverse_trees", opt->repo);
1676 ret = traverse_trees(NULL, 3, t, &info);
1677 if (ret == 0)
1678 ret = handle_deferred_entries(opt, &info);
1679 trace2_region_leave("merge", "traverse_trees", opt->repo);
1681 return ret;
1684 /*** Function Grouping: functions related to threeway content merges ***/
1686 static int find_first_merges(struct repository *repo,
1687 const char *path,
1688 struct commit *a,
1689 struct commit *b,
1690 struct object_array *result)
1692 int i, j;
1693 struct object_array merges = OBJECT_ARRAY_INIT;
1694 struct commit *commit;
1695 int contains_another;
1697 char merged_revision[GIT_MAX_HEXSZ + 2];
1698 const char *rev_args[] = { "rev-list", "--merges", "--ancestry-path",
1699 "--all", merged_revision, NULL };
1700 struct rev_info revs;
1701 struct setup_revision_opt rev_opts;
1703 memset(result, 0, sizeof(struct object_array));
1704 memset(&rev_opts, 0, sizeof(rev_opts));
1706 /* get all revisions that merge commit a */
1707 xsnprintf(merged_revision, sizeof(merged_revision), "^%s",
1708 oid_to_hex(&a->object.oid));
1709 repo_init_revisions(repo, &revs, NULL);
1710 /* FIXME: can't handle linked worktrees in submodules yet */
1711 revs.single_worktree = path != NULL;
1712 setup_revisions(ARRAY_SIZE(rev_args)-1, rev_args, &revs, &rev_opts);
1714 /* save all revisions from the above list that contain b */
1715 if (prepare_revision_walk(&revs))
1716 die("revision walk setup failed");
1717 while ((commit = get_revision(&revs)) != NULL) {
1718 struct object *o = &(commit->object);
1719 if (repo_in_merge_bases(repo, b, commit))
1720 add_object_array(o, NULL, &merges);
1722 reset_revision_walk();
1724 /* Now we've got all merges that contain a and b. Prune all
1725 * merges that contain another found merge and save them in
1726 * result.
1728 for (i = 0; i < merges.nr; i++) {
1729 struct commit *m1 = (struct commit *) merges.objects[i].item;
1731 contains_another = 0;
1732 for (j = 0; j < merges.nr; j++) {
1733 struct commit *m2 = (struct commit *) merges.objects[j].item;
1734 if (i != j && repo_in_merge_bases(repo, m2, m1)) {
1735 contains_another = 1;
1736 break;
1740 if (!contains_another)
1741 add_object_array(merges.objects[i].item, NULL, result);
1744 object_array_clear(&merges);
1745 release_revisions(&revs);
1746 return result->nr;
1749 static int merge_submodule(struct merge_options *opt,
1750 const char *path,
1751 const struct object_id *o,
1752 const struct object_id *a,
1753 const struct object_id *b,
1754 struct object_id *result)
1756 struct repository subrepo;
1757 struct strbuf sb = STRBUF_INIT;
1758 int ret = 0;
1759 struct commit *commit_o, *commit_a, *commit_b;
1760 int parent_count;
1761 struct object_array merges;
1763 int i;
1764 int search = !opt->priv->call_depth;
1765 int sub_not_initialized = 1;
1766 int sub_flag = CONFLICT_SUBMODULE_FAILED_TO_MERGE;
1768 /* store fallback answer in result in case we fail */
1769 oidcpy(result, opt->priv->call_depth ? o : a);
1771 /* we can not handle deletion conflicts */
1772 if (is_null_oid(a) || is_null_oid(b))
1773 BUG("submodule deleted on one side; this should be handled outside of merge_submodule()");
1775 if ((sub_not_initialized = repo_submodule_init(&subrepo,
1776 opt->repo, path, null_oid()))) {
1777 path_msg(opt, CONFLICT_SUBMODULE_NOT_INITIALIZED, 0,
1778 path, NULL, NULL, NULL,
1779 _("Failed to merge submodule %s (not checked out)"),
1780 path);
1781 sub_flag = CONFLICT_SUBMODULE_NOT_INITIALIZED;
1782 goto cleanup;
1785 if (is_null_oid(o)) {
1786 path_msg(opt, CONFLICT_SUBMODULE_NULL_MERGE_BASE, 0,
1787 path, NULL, NULL, NULL,
1788 _("Failed to merge submodule %s (no merge base)"),
1789 path);
1790 goto cleanup;
1793 if (!(commit_o = lookup_commit_reference(&subrepo, o)) ||
1794 !(commit_a = lookup_commit_reference(&subrepo, a)) ||
1795 !(commit_b = lookup_commit_reference(&subrepo, b))) {
1796 path_msg(opt, CONFLICT_SUBMODULE_HISTORY_NOT_AVAILABLE, 0,
1797 path, NULL, NULL, NULL,
1798 _("Failed to merge submodule %s (commits not present)"),
1799 path);
1800 sub_flag = CONFLICT_SUBMODULE_HISTORY_NOT_AVAILABLE;
1801 goto cleanup;
1804 /* check whether both changes are forward */
1805 if (!repo_in_merge_bases(&subrepo, commit_o, commit_a) ||
1806 !repo_in_merge_bases(&subrepo, commit_o, commit_b)) {
1807 path_msg(opt, CONFLICT_SUBMODULE_MAY_HAVE_REWINDS, 0,
1808 path, NULL, NULL, NULL,
1809 _("Failed to merge submodule %s "
1810 "(commits don't follow merge-base)"),
1811 path);
1812 goto cleanup;
1815 /* Case #1: a is contained in b or vice versa */
1816 if (repo_in_merge_bases(&subrepo, commit_a, commit_b)) {
1817 oidcpy(result, b);
1818 path_msg(opt, INFO_SUBMODULE_FAST_FORWARDING, 1,
1819 path, NULL, NULL, NULL,
1820 _("Note: Fast-forwarding submodule %s to %s"),
1821 path, oid_to_hex(b));
1822 ret = 1;
1823 goto cleanup;
1825 if (repo_in_merge_bases(&subrepo, commit_b, commit_a)) {
1826 oidcpy(result, a);
1827 path_msg(opt, INFO_SUBMODULE_FAST_FORWARDING, 1,
1828 path, NULL, NULL, NULL,
1829 _("Note: Fast-forwarding submodule %s to %s"),
1830 path, oid_to_hex(a));
1831 ret = 1;
1832 goto cleanup;
1836 * Case #2: There are one or more merges that contain a and b in
1837 * the submodule. If there is only one, then present it as a
1838 * suggestion to the user, but leave it marked unmerged so the
1839 * user needs to confirm the resolution.
1842 /* Skip the search if makes no sense to the calling context. */
1843 if (!search)
1844 goto cleanup;
1846 /* find commit which merges them */
1847 parent_count = find_first_merges(&subrepo, path, commit_a, commit_b,
1848 &merges);
1849 switch (parent_count) {
1850 case 0:
1851 path_msg(opt, CONFLICT_SUBMODULE_FAILED_TO_MERGE, 0,
1852 path, NULL, NULL, NULL,
1853 _("Failed to merge submodule %s"), path);
1854 break;
1856 case 1:
1857 format_commit(&sb, 4, &subrepo,
1858 (struct commit *)merges.objects[0].item);
1859 path_msg(opt, CONFLICT_SUBMODULE_FAILED_TO_MERGE_BUT_POSSIBLE_RESOLUTION, 0,
1860 path, NULL, NULL, NULL,
1861 _("Failed to merge submodule %s, but a possible merge "
1862 "resolution exists: %s"),
1863 path, sb.buf);
1864 strbuf_release(&sb);
1865 break;
1866 default:
1867 for (i = 0; i < merges.nr; i++)
1868 format_commit(&sb, 4, &subrepo,
1869 (struct commit *)merges.objects[i].item);
1870 path_msg(opt, CONFLICT_SUBMODULE_FAILED_TO_MERGE_BUT_POSSIBLE_RESOLUTION, 0,
1871 path, NULL, NULL, NULL,
1872 _("Failed to merge submodule %s, but multiple "
1873 "possible merges exist:\n%s"), path, sb.buf);
1874 strbuf_release(&sb);
1877 object_array_clear(&merges);
1878 cleanup:
1879 if (!opt->priv->call_depth && !ret) {
1880 struct string_list *csub = &opt->priv->conflicted_submodules;
1881 struct conflicted_submodule_item *util;
1882 const char *abbrev;
1884 util = xmalloc(sizeof(*util));
1885 util->flag = sub_flag;
1886 util->abbrev = NULL;
1887 if (!sub_not_initialized) {
1888 abbrev = repo_find_unique_abbrev(&subrepo, b, DEFAULT_ABBREV);
1889 util->abbrev = xstrdup(abbrev);
1891 string_list_append(csub, path)->util = util;
1894 if (!sub_not_initialized)
1895 repo_clear(&subrepo);
1896 return ret;
1899 static void initialize_attr_index(struct merge_options *opt)
1902 * The renormalize_buffer() functions require attributes, and
1903 * annoyingly those can only be read from the working tree or from
1904 * an index_state. merge-ort doesn't have an index_state, so we
1905 * generate a fake one containing only attribute information.
1907 struct merged_info *mi;
1908 struct index_state *attr_index = &opt->priv->attr_index;
1909 struct cache_entry *ce;
1911 attr_index->initialized = 1;
1913 if (!opt->renormalize)
1914 return;
1916 mi = strmap_get(&opt->priv->paths, GITATTRIBUTES_FILE);
1917 if (!mi)
1918 return;
1920 if (mi->clean) {
1921 int len = strlen(GITATTRIBUTES_FILE);
1922 ce = make_empty_cache_entry(attr_index, len);
1923 ce->ce_mode = create_ce_mode(mi->result.mode);
1924 ce->ce_flags = create_ce_flags(0);
1925 ce->ce_namelen = len;
1926 oidcpy(&ce->oid, &mi->result.oid);
1927 memcpy(ce->name, GITATTRIBUTES_FILE, len);
1928 add_index_entry(attr_index, ce,
1929 ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
1930 get_stream_filter(attr_index, GITATTRIBUTES_FILE, &ce->oid);
1931 } else {
1932 int stage, len;
1933 struct conflict_info *ci;
1935 ASSIGN_AND_VERIFY_CI(ci, mi);
1936 for (stage = 0; stage < 3; stage++) {
1937 unsigned stage_mask = (1 << stage);
1939 if (!(ci->filemask & stage_mask))
1940 continue;
1941 len = strlen(GITATTRIBUTES_FILE);
1942 ce = make_empty_cache_entry(attr_index, len);
1943 ce->ce_mode = create_ce_mode(ci->stages[stage].mode);
1944 ce->ce_flags = create_ce_flags(stage);
1945 ce->ce_namelen = len;
1946 oidcpy(&ce->oid, &ci->stages[stage].oid);
1947 memcpy(ce->name, GITATTRIBUTES_FILE, len);
1948 add_index_entry(attr_index, ce,
1949 ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
1950 get_stream_filter(attr_index, GITATTRIBUTES_FILE,
1951 &ce->oid);
1956 static int merge_3way(struct merge_options *opt,
1957 const char *path,
1958 const struct object_id *o,
1959 const struct object_id *a,
1960 const struct object_id *b,
1961 const char *pathnames[3],
1962 const int extra_marker_size,
1963 mmbuffer_t *result_buf)
1965 mmfile_t orig, src1, src2;
1966 struct ll_merge_options ll_opts = {0};
1967 char *base, *name1, *name2;
1968 enum ll_merge_result merge_status;
1970 if (!opt->priv->attr_index.initialized)
1971 initialize_attr_index(opt);
1973 ll_opts.renormalize = opt->renormalize;
1974 ll_opts.extra_marker_size = extra_marker_size;
1975 ll_opts.xdl_opts = opt->xdl_opts;
1977 if (opt->priv->call_depth) {
1978 ll_opts.virtual_ancestor = 1;
1979 ll_opts.variant = 0;
1980 } else {
1981 switch (opt->recursive_variant) {
1982 case MERGE_VARIANT_OURS:
1983 ll_opts.variant = XDL_MERGE_FAVOR_OURS;
1984 break;
1985 case MERGE_VARIANT_THEIRS:
1986 ll_opts.variant = XDL_MERGE_FAVOR_THEIRS;
1987 break;
1988 default:
1989 ll_opts.variant = 0;
1990 break;
1994 assert(pathnames[0] && pathnames[1] && pathnames[2] && opt->ancestor);
1995 if (pathnames[0] == pathnames[1] && pathnames[1] == pathnames[2]) {
1996 base = mkpathdup("%s", opt->ancestor);
1997 name1 = mkpathdup("%s", opt->branch1);
1998 name2 = mkpathdup("%s", opt->branch2);
1999 } else {
2000 base = mkpathdup("%s:%s", opt->ancestor, pathnames[0]);
2001 name1 = mkpathdup("%s:%s", opt->branch1, pathnames[1]);
2002 name2 = mkpathdup("%s:%s", opt->branch2, pathnames[2]);
2005 read_mmblob(&orig, o);
2006 read_mmblob(&src1, a);
2007 read_mmblob(&src2, b);
2009 merge_status = ll_merge(result_buf, path, &orig, base,
2010 &src1, name1, &src2, name2,
2011 &opt->priv->attr_index, &ll_opts);
2012 if (merge_status == LL_MERGE_BINARY_CONFLICT)
2013 path_msg(opt, CONFLICT_BINARY, 0,
2014 path, NULL, NULL, NULL,
2015 "warning: Cannot merge binary files: %s (%s vs. %s)",
2016 path, name1, name2);
2018 free(base);
2019 free(name1);
2020 free(name2);
2021 free(orig.ptr);
2022 free(src1.ptr);
2023 free(src2.ptr);
2024 return merge_status;
2027 static int handle_content_merge(struct merge_options *opt,
2028 const char *path,
2029 const struct version_info *o,
2030 const struct version_info *a,
2031 const struct version_info *b,
2032 const char *pathnames[3],
2033 const int extra_marker_size,
2034 struct version_info *result)
2037 * path is the target location where we want to put the file, and
2038 * is used to determine any normalization rules in ll_merge.
2040 * The normal case is that path and all entries in pathnames are
2041 * identical, though renames can affect which path we got one of
2042 * the three blobs to merge on various sides of history.
2044 * extra_marker_size is the amount to extend conflict markers in
2045 * ll_merge; this is neeed if we have content merges of content
2046 * merges, which happens for example with rename/rename(2to1) and
2047 * rename/add conflicts.
2049 unsigned clean = 1;
2052 * handle_content_merge() needs both files to be of the same type, i.e.
2053 * both files OR both submodules OR both symlinks. Conflicting types
2054 * needs to be handled elsewhere.
2056 assert((S_IFMT & a->mode) == (S_IFMT & b->mode));
2058 /* Merge modes */
2059 if (a->mode == b->mode || a->mode == o->mode)
2060 result->mode = b->mode;
2061 else {
2062 /* must be the 100644/100755 case */
2063 assert(S_ISREG(a->mode));
2064 result->mode = a->mode;
2065 clean = (b->mode == o->mode);
2067 * FIXME: If opt->priv->call_depth && !clean, then we really
2068 * should not make result->mode match either a->mode or
2069 * b->mode; that causes t6036 "check conflicting mode for
2070 * regular file" to fail. It would be best to use some other
2071 * mode, but we'll confuse all kinds of stuff if we use one
2072 * where S_ISREG(result->mode) isn't true, and if we use
2073 * something like 0100666, then tree-walk.c's calls to
2074 * canon_mode() will just normalize that to 100644 for us and
2075 * thus not solve anything.
2077 * Figure out if there's some kind of way we can work around
2078 * this...
2083 * Trivial oid merge.
2085 * Note: While one might assume that the next four lines would
2086 * be unnecessary due to the fact that match_mask is often
2087 * setup and already handled, renames don't always take care
2088 * of that.
2090 if (oideq(&a->oid, &b->oid) || oideq(&a->oid, &o->oid))
2091 oidcpy(&result->oid, &b->oid);
2092 else if (oideq(&b->oid, &o->oid))
2093 oidcpy(&result->oid, &a->oid);
2095 /* Remaining rules depend on file vs. submodule vs. symlink. */
2096 else if (S_ISREG(a->mode)) {
2097 mmbuffer_t result_buf;
2098 int ret = 0, merge_status;
2099 int two_way;
2102 * If 'o' is different type, treat it as null so we do a
2103 * two-way merge.
2105 two_way = ((S_IFMT & o->mode) != (S_IFMT & a->mode));
2107 merge_status = merge_3way(opt, path,
2108 two_way ? null_oid() : &o->oid,
2109 &a->oid, &b->oid,
2110 pathnames, extra_marker_size,
2111 &result_buf);
2113 if ((merge_status < 0) || !result_buf.ptr)
2114 ret = err(opt, _("Failed to execute internal merge"));
2116 if (!ret &&
2117 write_object_file(result_buf.ptr, result_buf.size,
2118 OBJ_BLOB, &result->oid))
2119 ret = err(opt, _("Unable to add %s to database"),
2120 path);
2122 free(result_buf.ptr);
2123 if (ret)
2124 return -1;
2125 clean &= (merge_status == 0);
2126 path_msg(opt, INFO_AUTO_MERGING, 1, path, NULL, NULL, NULL,
2127 _("Auto-merging %s"), path);
2128 } else if (S_ISGITLINK(a->mode)) {
2129 int two_way = ((S_IFMT & o->mode) != (S_IFMT & a->mode));
2130 clean = merge_submodule(opt, pathnames[0],
2131 two_way ? null_oid() : &o->oid,
2132 &a->oid, &b->oid, &result->oid);
2133 if (opt->priv->call_depth && two_way && !clean) {
2134 result->mode = o->mode;
2135 oidcpy(&result->oid, &o->oid);
2137 } else if (S_ISLNK(a->mode)) {
2138 if (opt->priv->call_depth) {
2139 clean = 0;
2140 result->mode = o->mode;
2141 oidcpy(&result->oid, &o->oid);
2142 } else {
2143 switch (opt->recursive_variant) {
2144 case MERGE_VARIANT_NORMAL:
2145 clean = 0;
2146 oidcpy(&result->oid, &a->oid);
2147 break;
2148 case MERGE_VARIANT_OURS:
2149 oidcpy(&result->oid, &a->oid);
2150 break;
2151 case MERGE_VARIANT_THEIRS:
2152 oidcpy(&result->oid, &b->oid);
2153 break;
2156 } else
2157 BUG("unsupported object type in the tree: %06o for %s",
2158 a->mode, path);
2160 return clean;
2163 /*** Function Grouping: functions related to detect_and_process_renames(), ***
2164 *** which are split into directory and regular rename detection sections. ***/
2166 /*** Function Grouping: functions related to directory rename detection ***/
2168 struct collision_info {
2169 struct string_list source_files;
2170 unsigned reported_already:1;
2174 * Return a new string that replaces the beginning portion (which matches
2175 * rename_info->key), with rename_info->util.new_dir. In perl-speak:
2176 * new_path_name = (old_path =~ s/rename_info->key/rename_info->value/);
2177 * NOTE:
2178 * Caller must ensure that old_path starts with rename_info->key + '/'.
2180 static char *apply_dir_rename(struct strmap_entry *rename_info,
2181 const char *old_path)
2183 struct strbuf new_path = STRBUF_INIT;
2184 const char *old_dir = rename_info->key;
2185 const char *new_dir = rename_info->value;
2186 int oldlen, newlen, new_dir_len;
2188 oldlen = strlen(old_dir);
2189 if (*new_dir == '\0')
2191 * If someone renamed/merged a subdirectory into the root
2192 * directory (e.g. 'some/subdir' -> ''), then we want to
2193 * avoid returning
2194 * '' + '/filename'
2195 * as the rename; we need to make old_path + oldlen advance
2196 * past the '/' character.
2198 oldlen++;
2199 new_dir_len = strlen(new_dir);
2200 newlen = new_dir_len + (strlen(old_path) - oldlen) + 1;
2201 strbuf_grow(&new_path, newlen);
2202 strbuf_add(&new_path, new_dir, new_dir_len);
2203 strbuf_addstr(&new_path, &old_path[oldlen]);
2205 return strbuf_detach(&new_path, NULL);
2208 static int path_in_way(struct strmap *paths, const char *path, unsigned side_mask)
2210 struct merged_info *mi = strmap_get(paths, path);
2211 struct conflict_info *ci;
2212 if (!mi)
2213 return 0;
2214 INITIALIZE_CI(ci, mi);
2215 return mi->clean || (side_mask & (ci->filemask | ci->dirmask));
2219 * See if there is a directory rename for path, and if there are any file
2220 * level conflicts on the given side for the renamed location. If there is
2221 * a rename and there are no conflicts, return the new name. Otherwise,
2222 * return NULL.
2224 static char *handle_path_level_conflicts(struct merge_options *opt,
2225 const char *path,
2226 unsigned side_index,
2227 struct strmap_entry *rename_info,
2228 struct strmap *collisions)
2230 char *new_path = NULL;
2231 struct collision_info *c_info;
2232 int clean = 1;
2233 struct strbuf collision_paths = STRBUF_INIT;
2236 * entry has the mapping of old directory name to new directory name
2237 * that we want to apply to path.
2239 new_path = apply_dir_rename(rename_info, path);
2240 if (!new_path)
2241 BUG("Failed to apply directory rename!");
2244 * The caller needs to have ensured that it has pre-populated
2245 * collisions with all paths that map to new_path. Do a quick check
2246 * to ensure that's the case.
2248 c_info = strmap_get(collisions, new_path);
2249 if (!c_info)
2250 BUG("c_info is NULL");
2253 * Check for one-sided add/add/.../add conflicts, i.e.
2254 * where implicit renames from the other side doing
2255 * directory rename(s) can affect this side of history
2256 * to put multiple paths into the same location. Warn
2257 * and bail on directory renames for such paths.
2259 if (c_info->reported_already) {
2260 clean = 0;
2261 } else if (path_in_way(&opt->priv->paths, new_path, 1 << side_index)) {
2262 c_info->reported_already = 1;
2263 strbuf_add_separated_string_list(&collision_paths, ", ",
2264 &c_info->source_files);
2265 path_msg(opt, CONFLICT_DIR_RENAME_FILE_IN_WAY, 0,
2266 new_path, NULL, NULL, &c_info->source_files,
2267 _("CONFLICT (implicit dir rename): Existing "
2268 "file/dir at %s in the way of implicit "
2269 "directory rename(s) putting the following "
2270 "path(s) there: %s."),
2271 new_path, collision_paths.buf);
2272 clean = 0;
2273 } else if (c_info->source_files.nr > 1) {
2274 c_info->reported_already = 1;
2275 strbuf_add_separated_string_list(&collision_paths, ", ",
2276 &c_info->source_files);
2277 path_msg(opt, CONFLICT_DIR_RENAME_COLLISION, 0,
2278 new_path, NULL, NULL, &c_info->source_files,
2279 _("CONFLICT (implicit dir rename): Cannot map "
2280 "more than one path to %s; implicit directory "
2281 "renames tried to put these paths there: %s"),
2282 new_path, collision_paths.buf);
2283 clean = 0;
2286 /* Free memory we no longer need */
2287 strbuf_release(&collision_paths);
2288 if (!clean && new_path) {
2289 free(new_path);
2290 return NULL;
2293 return new_path;
2296 static void get_provisional_directory_renames(struct merge_options *opt,
2297 unsigned side,
2298 int *clean)
2300 struct hashmap_iter iter;
2301 struct strmap_entry *entry;
2302 struct rename_info *renames = &opt->priv->renames;
2305 * Collapse
2306 * dir_rename_count: old_directory -> {new_directory -> count}
2307 * down to
2308 * dir_renames: old_directory -> best_new_directory
2309 * where best_new_directory is the one with the unique highest count.
2311 strmap_for_each_entry(&renames->dir_rename_count[side], &iter, entry) {
2312 const char *source_dir = entry->key;
2313 struct strintmap *counts = entry->value;
2314 struct hashmap_iter count_iter;
2315 struct strmap_entry *count_entry;
2316 int max = 0;
2317 int bad_max = 0;
2318 const char *best = NULL;
2320 strintmap_for_each_entry(counts, &count_iter, count_entry) {
2321 const char *target_dir = count_entry->key;
2322 intptr_t count = (intptr_t)count_entry->value;
2324 if (count == max)
2325 bad_max = max;
2326 else if (count > max) {
2327 max = count;
2328 best = target_dir;
2332 if (max == 0)
2333 continue;
2335 if (bad_max == max) {
2336 path_msg(opt, CONFLICT_DIR_RENAME_SPLIT, 0,
2337 source_dir, NULL, NULL, NULL,
2338 _("CONFLICT (directory rename split): "
2339 "Unclear where to rename %s to; it was "
2340 "renamed to multiple other directories, "
2341 "with no destination getting a majority of "
2342 "the files."),
2343 source_dir);
2344 *clean = 0;
2345 } else {
2346 strmap_put(&renames->dir_renames[side],
2347 source_dir, (void*)best);
2352 static void handle_directory_level_conflicts(struct merge_options *opt)
2354 struct hashmap_iter iter;
2355 struct strmap_entry *entry;
2356 struct string_list duplicated = STRING_LIST_INIT_NODUP;
2357 struct rename_info *renames = &opt->priv->renames;
2358 struct strmap *side1_dir_renames = &renames->dir_renames[MERGE_SIDE1];
2359 struct strmap *side2_dir_renames = &renames->dir_renames[MERGE_SIDE2];
2360 int i;
2362 strmap_for_each_entry(side1_dir_renames, &iter, entry) {
2363 if (strmap_contains(side2_dir_renames, entry->key))
2364 string_list_append(&duplicated, entry->key);
2367 for (i = 0; i < duplicated.nr; i++) {
2368 strmap_remove(side1_dir_renames, duplicated.items[i].string, 0);
2369 strmap_remove(side2_dir_renames, duplicated.items[i].string, 0);
2371 string_list_clear(&duplicated, 0);
2374 static struct strmap_entry *check_dir_renamed(const char *path,
2375 struct strmap *dir_renames)
2377 char *temp = xstrdup(path);
2378 char *end;
2379 struct strmap_entry *e = NULL;
2381 while ((end = strrchr(temp, '/'))) {
2382 *end = '\0';
2383 e = strmap_get_entry(dir_renames, temp);
2384 if (e)
2385 break;
2387 free(temp);
2388 return e;
2391 static void compute_collisions(struct strmap *collisions,
2392 struct strmap *dir_renames,
2393 struct diff_queue_struct *pairs)
2395 int i;
2397 strmap_init_with_options(collisions, NULL, 0);
2398 if (strmap_empty(dir_renames))
2399 return;
2402 * Multiple files can be mapped to the same path due to directory
2403 * renames done by the other side of history. Since that other
2404 * side of history could have merged multiple directories into one,
2405 * if our side of history added the same file basename to each of
2406 * those directories, then all N of them would get implicitly
2407 * renamed by the directory rename detection into the same path,
2408 * and we'd get an add/add/.../add conflict, and all those adds
2409 * from *this* side of history. This is not representable in the
2410 * index, and users aren't going to easily be able to make sense of
2411 * it. So we need to provide a good warning about what's
2412 * happening, and fall back to no-directory-rename detection
2413 * behavior for those paths.
2415 * See testcases 9e and all of section 5 from t6043 for examples.
2417 for (i = 0; i < pairs->nr; ++i) {
2418 struct strmap_entry *rename_info;
2419 struct collision_info *collision_info;
2420 char *new_path;
2421 struct diff_filepair *pair = pairs->queue[i];
2423 if (pair->status != 'A' && pair->status != 'R')
2424 continue;
2425 rename_info = check_dir_renamed(pair->two->path, dir_renames);
2426 if (!rename_info)
2427 continue;
2429 new_path = apply_dir_rename(rename_info, pair->two->path);
2430 assert(new_path);
2431 collision_info = strmap_get(collisions, new_path);
2432 if (collision_info) {
2433 free(new_path);
2434 } else {
2435 CALLOC_ARRAY(collision_info, 1);
2436 string_list_init_nodup(&collision_info->source_files);
2437 strmap_put(collisions, new_path, collision_info);
2439 string_list_insert(&collision_info->source_files,
2440 pair->two->path);
2444 static void free_collisions(struct strmap *collisions)
2446 struct hashmap_iter iter;
2447 struct strmap_entry *entry;
2449 /* Free each value in the collisions map */
2450 strmap_for_each_entry(collisions, &iter, entry) {
2451 struct collision_info *info = entry->value;
2452 string_list_clear(&info->source_files, 0);
2455 * In compute_collisions(), we set collisions.strdup_strings to 0
2456 * so that we wouldn't have to make another copy of the new_path
2457 * allocated by apply_dir_rename(). But now that we've used them
2458 * and have no other references to these strings, it is time to
2459 * deallocate them.
2461 free_strmap_strings(collisions);
2462 strmap_clear(collisions, 1);
2465 static char *check_for_directory_rename(struct merge_options *opt,
2466 const char *path,
2467 unsigned side_index,
2468 struct strmap *dir_renames,
2469 struct strmap *dir_rename_exclusions,
2470 struct strmap *collisions,
2471 int *clean_merge)
2473 char *new_path;
2474 struct strmap_entry *rename_info;
2475 struct strmap_entry *otherinfo;
2476 const char *new_dir;
2477 int other_side = 3 - side_index;
2480 * Cases where we don't have or don't want a directory rename for
2481 * this path.
2483 if (strmap_empty(dir_renames))
2484 return NULL;
2485 if (strmap_get(&collisions[other_side], path))
2486 return NULL;
2487 rename_info = check_dir_renamed(path, dir_renames);
2488 if (!rename_info)
2489 return NULL;
2492 * This next part is a little weird. We do not want to do an
2493 * implicit rename into a directory we renamed on our side, because
2494 * that will result in a spurious rename/rename(1to2) conflict. An
2495 * example:
2496 * Base commit: dumbdir/afile, otherdir/bfile
2497 * Side 1: smrtdir/afile, otherdir/bfile
2498 * Side 2: dumbdir/afile, dumbdir/bfile
2499 * Here, while working on Side 1, we could notice that otherdir was
2500 * renamed/merged to dumbdir, and change the diff_filepair for
2501 * otherdir/bfile into a rename into dumbdir/bfile. However, Side
2502 * 2 will notice the rename from dumbdir to smrtdir, and do the
2503 * transitive rename to move it from dumbdir/bfile to
2504 * smrtdir/bfile. That gives us bfile in dumbdir vs being in
2505 * smrtdir, a rename/rename(1to2) conflict. We really just want
2506 * the file to end up in smrtdir. And the way to achieve that is
2507 * to not let Side1 do the rename to dumbdir, since we know that is
2508 * the source of one of our directory renames.
2510 * That's why otherinfo and dir_rename_exclusions is here.
2512 * As it turns out, this also prevents N-way transient rename
2513 * confusion; See testcases 9c and 9d of t6043.
2515 new_dir = rename_info->value; /* old_dir = rename_info->key; */
2516 otherinfo = strmap_get_entry(dir_rename_exclusions, new_dir);
2517 if (otherinfo) {
2518 path_msg(opt, INFO_DIR_RENAME_SKIPPED_DUE_TO_RERENAME, 1,
2519 rename_info->key, path, new_dir, NULL,
2520 _("WARNING: Avoiding applying %s -> %s rename "
2521 "to %s, because %s itself was renamed."),
2522 rename_info->key, new_dir, path, new_dir);
2523 return NULL;
2526 new_path = handle_path_level_conflicts(opt, path, side_index,
2527 rename_info,
2528 &collisions[side_index]);
2529 *clean_merge &= (new_path != NULL);
2531 return new_path;
2534 static void apply_directory_rename_modifications(struct merge_options *opt,
2535 struct diff_filepair *pair,
2536 char *new_path)
2539 * The basic idea is to get the conflict_info from opt->priv->paths
2540 * at old path, and insert it into new_path; basically just this:
2541 * ci = strmap_get(&opt->priv->paths, old_path);
2542 * strmap_remove(&opt->priv->paths, old_path, 0);
2543 * strmap_put(&opt->priv->paths, new_path, ci);
2544 * However, there are some factors complicating this:
2545 * - opt->priv->paths may already have an entry at new_path
2546 * - Each ci tracks its containing directory, so we need to
2547 * update that
2548 * - If another ci has the same containing directory, then
2549 * the two char*'s MUST point to the same location. See the
2550 * comment in struct merged_info. strcmp equality is not
2551 * enough; we need pointer equality.
2552 * - opt->priv->paths must hold the parent directories of any
2553 * entries that are added. So, if this directory rename
2554 * causes entirely new directories, we must recursively add
2555 * parent directories.
2556 * - For each parent directory added to opt->priv->paths, we
2557 * also need to get its parent directory stored in its
2558 * conflict_info->merged.directory_name with all the same
2559 * requirements about pointer equality.
2561 struct string_list dirs_to_insert = STRING_LIST_INIT_NODUP;
2562 struct conflict_info *ci, *new_ci;
2563 struct strmap_entry *entry;
2564 const char *branch_with_new_path, *branch_with_dir_rename;
2565 const char *old_path = pair->two->path;
2566 const char *parent_name;
2567 const char *cur_path;
2568 int i, len;
2570 entry = strmap_get_entry(&opt->priv->paths, old_path);
2571 old_path = entry->key;
2572 ci = entry->value;
2573 VERIFY_CI(ci);
2575 /* Find parent directories missing from opt->priv->paths */
2576 cur_path = mem_pool_strdup(&opt->priv->pool, new_path);
2577 free((char*)new_path);
2578 new_path = (char *)cur_path;
2580 while (1) {
2581 /* Find the parent directory of cur_path */
2582 char *last_slash = strrchr(cur_path, '/');
2583 if (last_slash) {
2584 parent_name = mem_pool_strndup(&opt->priv->pool,
2585 cur_path,
2586 last_slash - cur_path);
2587 } else {
2588 parent_name = opt->priv->toplevel_dir;
2589 break;
2592 /* Look it up in opt->priv->paths */
2593 entry = strmap_get_entry(&opt->priv->paths, parent_name);
2594 if (entry) {
2595 parent_name = entry->key; /* reuse known pointer */
2596 break;
2599 /* Record this is one of the directories we need to insert */
2600 string_list_append(&dirs_to_insert, parent_name);
2601 cur_path = parent_name;
2604 /* Traverse dirs_to_insert and insert them into opt->priv->paths */
2605 for (i = dirs_to_insert.nr-1; i >= 0; --i) {
2606 struct conflict_info *dir_ci;
2607 char *cur_dir = dirs_to_insert.items[i].string;
2609 CALLOC_ARRAY(dir_ci, 1);
2611 dir_ci->merged.directory_name = parent_name;
2612 len = strlen(parent_name);
2613 /* len+1 because of trailing '/' character */
2614 dir_ci->merged.basename_offset = (len > 0 ? len+1 : len);
2615 dir_ci->dirmask = ci->filemask;
2616 strmap_put(&opt->priv->paths, cur_dir, dir_ci);
2618 parent_name = cur_dir;
2621 assert(ci->filemask == 2 || ci->filemask == 4);
2622 assert(ci->dirmask == 0);
2623 strmap_remove(&opt->priv->paths, old_path, 0);
2625 branch_with_new_path = (ci->filemask == 2) ? opt->branch1 : opt->branch2;
2626 branch_with_dir_rename = (ci->filemask == 2) ? opt->branch2 : opt->branch1;
2628 /* Now, finally update ci and stick it into opt->priv->paths */
2629 ci->merged.directory_name = parent_name;
2630 len = strlen(parent_name);
2631 ci->merged.basename_offset = (len > 0 ? len+1 : len);
2632 new_ci = strmap_get(&opt->priv->paths, new_path);
2633 if (!new_ci) {
2634 /* Place ci back into opt->priv->paths, but at new_path */
2635 strmap_put(&opt->priv->paths, new_path, ci);
2636 } else {
2637 int index;
2639 /* A few sanity checks */
2640 VERIFY_CI(new_ci);
2641 assert(ci->filemask == 2 || ci->filemask == 4);
2642 assert((new_ci->filemask & ci->filemask) == 0);
2643 assert(!new_ci->merged.clean);
2645 /* Copy stuff from ci into new_ci */
2646 new_ci->filemask |= ci->filemask;
2647 if (new_ci->dirmask)
2648 new_ci->df_conflict = 1;
2649 index = (ci->filemask >> 1);
2650 new_ci->pathnames[index] = ci->pathnames[index];
2651 new_ci->stages[index].mode = ci->stages[index].mode;
2652 oidcpy(&new_ci->stages[index].oid, &ci->stages[index].oid);
2654 ci = new_ci;
2657 if (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE) {
2658 /* Notify user of updated path */
2659 if (pair->status == 'A')
2660 path_msg(opt, INFO_DIR_RENAME_APPLIED, 1,
2661 new_path, old_path, NULL, NULL,
2662 _("Path updated: %s added in %s inside a "
2663 "directory that was renamed in %s; moving "
2664 "it to %s."),
2665 old_path, branch_with_new_path,
2666 branch_with_dir_rename, new_path);
2667 else
2668 path_msg(opt, INFO_DIR_RENAME_APPLIED, 1,
2669 new_path, old_path, NULL, NULL,
2670 _("Path updated: %s renamed to %s in %s, "
2671 "inside a directory that was renamed in %s; "
2672 "moving it to %s."),
2673 pair->one->path, old_path, branch_with_new_path,
2674 branch_with_dir_rename, new_path);
2675 } else {
2677 * opt->detect_directory_renames has the value
2678 * MERGE_DIRECTORY_RENAMES_CONFLICT, so mark these as conflicts.
2680 ci->path_conflict = 1;
2681 if (pair->status == 'A')
2682 path_msg(opt, CONFLICT_DIR_RENAME_SUGGESTED, 1,
2683 new_path, old_path, NULL, NULL,
2684 _("CONFLICT (file location): %s added in %s "
2685 "inside a directory that was renamed in %s, "
2686 "suggesting it should perhaps be moved to "
2687 "%s."),
2688 old_path, branch_with_new_path,
2689 branch_with_dir_rename, new_path);
2690 else
2691 path_msg(opt, CONFLICT_DIR_RENAME_SUGGESTED, 1,
2692 new_path, old_path, NULL, NULL,
2693 _("CONFLICT (file location): %s renamed to %s "
2694 "in %s, inside a directory that was renamed "
2695 "in %s, suggesting it should perhaps be "
2696 "moved to %s."),
2697 pair->one->path, old_path, branch_with_new_path,
2698 branch_with_dir_rename, new_path);
2702 * Finally, record the new location.
2704 pair->two->path = new_path;
2707 /*** Function Grouping: functions related to regular rename detection ***/
2709 static int process_renames(struct merge_options *opt,
2710 struct diff_queue_struct *renames)
2712 int clean_merge = 1, i;
2714 for (i = 0; i < renames->nr; ++i) {
2715 const char *oldpath = NULL, *newpath;
2716 struct diff_filepair *pair = renames->queue[i];
2717 struct conflict_info *oldinfo = NULL, *newinfo = NULL;
2718 struct strmap_entry *old_ent, *new_ent;
2719 unsigned int old_sidemask;
2720 int target_index, other_source_index;
2721 int source_deleted, collision, type_changed;
2722 const char *rename_branch = NULL, *delete_branch = NULL;
2724 old_ent = strmap_get_entry(&opt->priv->paths, pair->one->path);
2725 new_ent = strmap_get_entry(&opt->priv->paths, pair->two->path);
2726 if (old_ent) {
2727 oldpath = old_ent->key;
2728 oldinfo = old_ent->value;
2730 newpath = pair->two->path;
2731 if (new_ent) {
2732 newpath = new_ent->key;
2733 newinfo = new_ent->value;
2737 * If pair->one->path isn't in opt->priv->paths, that means
2738 * that either directory rename detection removed that
2739 * path, or a parent directory of oldpath was resolved and
2740 * we don't even need the rename; in either case, we can
2741 * skip it. If oldinfo->merged.clean, then the other side
2742 * of history had no changes to oldpath and we don't need
2743 * the rename and can skip it.
2745 if (!oldinfo || oldinfo->merged.clean)
2746 continue;
2749 * diff_filepairs have copies of pathnames, thus we have to
2750 * use standard 'strcmp()' (negated) instead of '=='.
2752 if (i + 1 < renames->nr &&
2753 !strcmp(oldpath, renames->queue[i+1]->one->path)) {
2754 /* Handle rename/rename(1to2) or rename/rename(1to1) */
2755 const char *pathnames[3];
2756 struct version_info merged;
2757 struct conflict_info *base, *side1, *side2;
2758 unsigned was_binary_blob = 0;
2760 pathnames[0] = oldpath;
2761 pathnames[1] = newpath;
2762 pathnames[2] = renames->queue[i+1]->two->path;
2764 base = strmap_get(&opt->priv->paths, pathnames[0]);
2765 side1 = strmap_get(&opt->priv->paths, pathnames[1]);
2766 side2 = strmap_get(&opt->priv->paths, pathnames[2]);
2768 VERIFY_CI(base);
2769 VERIFY_CI(side1);
2770 VERIFY_CI(side2);
2772 if (!strcmp(pathnames[1], pathnames[2])) {
2773 struct rename_info *ri = &opt->priv->renames;
2774 int j;
2776 /* Both sides renamed the same way */
2777 assert(side1 == side2);
2778 memcpy(&side1->stages[0], &base->stages[0],
2779 sizeof(merged));
2780 side1->filemask |= (1 << MERGE_BASE);
2781 /* Mark base as resolved by removal */
2782 base->merged.is_null = 1;
2783 base->merged.clean = 1;
2786 * Disable remembering renames optimization;
2787 * rename/rename(1to1) is incredibly rare, and
2788 * just disabling the optimization is easier
2789 * than purging cached_pairs,
2790 * cached_target_names, and dir_rename_counts.
2792 for (j = 0; j < 3; j++)
2793 ri->merge_trees[j] = NULL;
2795 /* We handled both renames, i.e. i+1 handled */
2796 i++;
2797 /* Move to next rename */
2798 continue;
2801 /* This is a rename/rename(1to2) */
2802 clean_merge = handle_content_merge(opt,
2803 pair->one->path,
2804 &base->stages[0],
2805 &side1->stages[1],
2806 &side2->stages[2],
2807 pathnames,
2808 1 + 2 * opt->priv->call_depth,
2809 &merged);
2810 if (!clean_merge &&
2811 merged.mode == side1->stages[1].mode &&
2812 oideq(&merged.oid, &side1->stages[1].oid))
2813 was_binary_blob = 1;
2814 memcpy(&side1->stages[1], &merged, sizeof(merged));
2815 if (was_binary_blob) {
2817 * Getting here means we were attempting to
2818 * merge a binary blob.
2820 * Since we can't merge binaries,
2821 * handle_content_merge() just takes one
2822 * side. But we don't want to copy the
2823 * contents of one side to both paths. We
2824 * used the contents of side1 above for
2825 * side1->stages, let's use the contents of
2826 * side2 for side2->stages below.
2828 oidcpy(&merged.oid, &side2->stages[2].oid);
2829 merged.mode = side2->stages[2].mode;
2831 memcpy(&side2->stages[2], &merged, sizeof(merged));
2833 side1->path_conflict = 1;
2834 side2->path_conflict = 1;
2836 * TODO: For renames we normally remove the path at the
2837 * old name. It would thus seem consistent to do the
2838 * same for rename/rename(1to2) cases, but we haven't
2839 * done so traditionally and a number of the regression
2840 * tests now encode an expectation that the file is
2841 * left there at stage 1. If we ever decide to change
2842 * this, add the following two lines here:
2843 * base->merged.is_null = 1;
2844 * base->merged.clean = 1;
2845 * and remove the setting of base->path_conflict to 1.
2847 base->path_conflict = 1;
2848 path_msg(opt, CONFLICT_RENAME_RENAME, 0,
2849 pathnames[0], pathnames[1], pathnames[2], NULL,
2850 _("CONFLICT (rename/rename): %s renamed to "
2851 "%s in %s and to %s in %s."),
2852 pathnames[0],
2853 pathnames[1], opt->branch1,
2854 pathnames[2], opt->branch2);
2856 i++; /* We handled both renames, i.e. i+1 handled */
2857 continue;
2860 VERIFY_CI(oldinfo);
2861 VERIFY_CI(newinfo);
2862 target_index = pair->score; /* from collect_renames() */
2863 assert(target_index == 1 || target_index == 2);
2864 other_source_index = 3 - target_index;
2865 old_sidemask = (1 << other_source_index); /* 2 or 4 */
2866 source_deleted = (oldinfo->filemask == 1);
2867 collision = ((newinfo->filemask & old_sidemask) != 0);
2868 type_changed = !source_deleted &&
2869 (S_ISREG(oldinfo->stages[other_source_index].mode) !=
2870 S_ISREG(newinfo->stages[target_index].mode));
2871 if (type_changed && collision) {
2873 * special handling so later blocks can handle this...
2875 * if type_changed && collision are both true, then this
2876 * was really a double rename, but one side wasn't
2877 * detected due to lack of break detection. I.e.
2878 * something like
2879 * orig: has normal file 'foo'
2880 * side1: renames 'foo' to 'bar', adds 'foo' symlink
2881 * side2: renames 'foo' to 'bar'
2882 * In this case, the foo->bar rename on side1 won't be
2883 * detected because the new symlink named 'foo' is
2884 * there and we don't do break detection. But we detect
2885 * this here because we don't want to merge the content
2886 * of the foo symlink with the foo->bar file, so we
2887 * have some logic to handle this special case. The
2888 * easiest way to do that is make 'bar' on side1 not
2889 * be considered a colliding file but the other part
2890 * of a normal rename. If the file is very different,
2891 * well we're going to get content merge conflicts
2892 * anyway so it doesn't hurt. And if the colliding
2893 * file also has a different type, that'll be handled
2894 * by the content merge logic in process_entry() too.
2896 * See also t6430, 'rename vs. rename/symlink'
2898 collision = 0;
2900 if (source_deleted) {
2901 if (target_index == 1) {
2902 rename_branch = opt->branch1;
2903 delete_branch = opt->branch2;
2904 } else {
2905 rename_branch = opt->branch2;
2906 delete_branch = opt->branch1;
2910 assert(source_deleted || oldinfo->filemask & old_sidemask);
2912 /* Need to check for special types of rename conflicts... */
2913 if (collision && !source_deleted) {
2914 /* collision: rename/add or rename/rename(2to1) */
2915 const char *pathnames[3];
2916 struct version_info merged;
2918 struct conflict_info *base, *side1, *side2;
2919 unsigned clean;
2921 pathnames[0] = oldpath;
2922 pathnames[other_source_index] = oldpath;
2923 pathnames[target_index] = newpath;
2925 base = strmap_get(&opt->priv->paths, pathnames[0]);
2926 side1 = strmap_get(&opt->priv->paths, pathnames[1]);
2927 side2 = strmap_get(&opt->priv->paths, pathnames[2]);
2929 VERIFY_CI(base);
2930 VERIFY_CI(side1);
2931 VERIFY_CI(side2);
2933 clean = handle_content_merge(opt, pair->one->path,
2934 &base->stages[0],
2935 &side1->stages[1],
2936 &side2->stages[2],
2937 pathnames,
2938 1 + 2 * opt->priv->call_depth,
2939 &merged);
2941 memcpy(&newinfo->stages[target_index], &merged,
2942 sizeof(merged));
2943 if (!clean) {
2944 path_msg(opt, CONFLICT_RENAME_COLLIDES, 0,
2945 newpath, oldpath, NULL, NULL,
2946 _("CONFLICT (rename involved in "
2947 "collision): rename of %s -> %s has "
2948 "content conflicts AND collides "
2949 "with another path; this may result "
2950 "in nested conflict markers."),
2951 oldpath, newpath);
2953 } else if (collision && source_deleted) {
2955 * rename/add/delete or rename/rename(2to1)/delete:
2956 * since oldpath was deleted on the side that didn't
2957 * do the rename, there's not much of a content merge
2958 * we can do for the rename. oldinfo->merged.is_null
2959 * was already set, so we just leave things as-is so
2960 * they look like an add/add conflict.
2963 newinfo->path_conflict = 1;
2964 path_msg(opt, CONFLICT_RENAME_DELETE, 0,
2965 newpath, oldpath, NULL, NULL,
2966 _("CONFLICT (rename/delete): %s renamed "
2967 "to %s in %s, but deleted in %s."),
2968 oldpath, newpath, rename_branch, delete_branch);
2969 } else {
2971 * a few different cases...start by copying the
2972 * existing stage(s) from oldinfo over the newinfo
2973 * and update the pathname(s).
2975 memcpy(&newinfo->stages[0], &oldinfo->stages[0],
2976 sizeof(newinfo->stages[0]));
2977 newinfo->filemask |= (1 << MERGE_BASE);
2978 newinfo->pathnames[0] = oldpath;
2979 if (type_changed) {
2980 /* rename vs. typechange */
2981 /* Mark the original as resolved by removal */
2982 memcpy(&oldinfo->stages[0].oid, null_oid(),
2983 sizeof(oldinfo->stages[0].oid));
2984 oldinfo->stages[0].mode = 0;
2985 oldinfo->filemask &= 0x06;
2986 } else if (source_deleted) {
2987 /* rename/delete */
2988 newinfo->path_conflict = 1;
2989 path_msg(opt, CONFLICT_RENAME_DELETE, 0,
2990 newpath, oldpath, NULL, NULL,
2991 _("CONFLICT (rename/delete): %s renamed"
2992 " to %s in %s, but deleted in %s."),
2993 oldpath, newpath,
2994 rename_branch, delete_branch);
2995 } else {
2996 /* normal rename */
2997 memcpy(&newinfo->stages[other_source_index],
2998 &oldinfo->stages[other_source_index],
2999 sizeof(newinfo->stages[0]));
3000 newinfo->filemask |= (1 << other_source_index);
3001 newinfo->pathnames[other_source_index] = oldpath;
3005 if (!type_changed) {
3006 /* Mark the original as resolved by removal */
3007 oldinfo->merged.is_null = 1;
3008 oldinfo->merged.clean = 1;
3013 return clean_merge;
3016 static inline int possible_side_renames(struct rename_info *renames,
3017 unsigned side_index)
3019 return renames->pairs[side_index].nr > 0 &&
3020 !strintmap_empty(&renames->relevant_sources[side_index]);
3023 static inline int possible_renames(struct rename_info *renames)
3025 return possible_side_renames(renames, 1) ||
3026 possible_side_renames(renames, 2) ||
3027 !strmap_empty(&renames->cached_pairs[1]) ||
3028 !strmap_empty(&renames->cached_pairs[2]);
3031 static void resolve_diffpair_statuses(struct diff_queue_struct *q)
3034 * A simplified version of diff_resolve_rename_copy(); would probably
3035 * just use that function but it's static...
3037 int i;
3038 struct diff_filepair *p;
3040 for (i = 0; i < q->nr; ++i) {
3041 p = q->queue[i];
3042 p->status = 0; /* undecided */
3043 if (!DIFF_FILE_VALID(p->one))
3044 p->status = DIFF_STATUS_ADDED;
3045 else if (!DIFF_FILE_VALID(p->two))
3046 p->status = DIFF_STATUS_DELETED;
3047 else if (DIFF_PAIR_RENAME(p))
3048 p->status = DIFF_STATUS_RENAMED;
3052 static void prune_cached_from_relevant(struct rename_info *renames,
3053 unsigned side)
3055 /* Reason for this function described in add_pair() */
3056 struct hashmap_iter iter;
3057 struct strmap_entry *entry;
3059 /* Remove from relevant_sources all entries in cached_pairs[side] */
3060 strmap_for_each_entry(&renames->cached_pairs[side], &iter, entry) {
3061 strintmap_remove(&renames->relevant_sources[side],
3062 entry->key);
3064 /* Remove from relevant_sources all entries in cached_irrelevant[side] */
3065 strset_for_each_entry(&renames->cached_irrelevant[side], &iter, entry) {
3066 strintmap_remove(&renames->relevant_sources[side],
3067 entry->key);
3071 static void use_cached_pairs(struct merge_options *opt,
3072 struct strmap *cached_pairs,
3073 struct diff_queue_struct *pairs)
3075 struct hashmap_iter iter;
3076 struct strmap_entry *entry;
3079 * Add to side_pairs all entries from renames->cached_pairs[side_index].
3080 * (Info in cached_irrelevant[side_index] is not relevant here.)
3082 strmap_for_each_entry(cached_pairs, &iter, entry) {
3083 struct diff_filespec *one, *two;
3084 const char *old_name = entry->key;
3085 const char *new_name = entry->value;
3086 if (!new_name)
3087 new_name = old_name;
3090 * cached_pairs has *copies* of old_name and new_name,
3091 * because it has to persist across merges. Since
3092 * pool_alloc_filespec() will just re-use the existing
3093 * filenames, which will also get re-used by
3094 * opt->priv->paths if they become renames, and then
3095 * get freed at the end of the merge, that would leave
3096 * the copy in cached_pairs dangling. Avoid this by
3097 * making a copy here.
3099 old_name = mem_pool_strdup(&opt->priv->pool, old_name);
3100 new_name = mem_pool_strdup(&opt->priv->pool, new_name);
3102 /* We don't care about oid/mode, only filenames and status */
3103 one = pool_alloc_filespec(&opt->priv->pool, old_name);
3104 two = pool_alloc_filespec(&opt->priv->pool, new_name);
3105 pool_diff_queue(&opt->priv->pool, pairs, one, two);
3106 pairs->queue[pairs->nr-1]->status = entry->value ? 'R' : 'D';
3110 static void cache_new_pair(struct rename_info *renames,
3111 int side,
3112 char *old_path,
3113 char *new_path,
3114 int free_old_value)
3116 char *old_value;
3117 new_path = xstrdup(new_path);
3118 old_value = strmap_put(&renames->cached_pairs[side],
3119 old_path, new_path);
3120 strset_add(&renames->cached_target_names[side], new_path);
3121 if (free_old_value)
3122 free(old_value);
3123 else
3124 assert(!old_value);
3127 static void possibly_cache_new_pair(struct rename_info *renames,
3128 struct diff_filepair *p,
3129 unsigned side,
3130 char *new_path)
3132 int dir_renamed_side = 0;
3134 if (new_path) {
3136 * Directory renames happen on the other side of history from
3137 * the side that adds new files to the old directory.
3139 dir_renamed_side = 3 - side;
3140 } else {
3141 int val = strintmap_get(&renames->relevant_sources[side],
3142 p->one->path);
3143 if (val == RELEVANT_NO_MORE) {
3144 assert(p->status == 'D');
3145 strset_add(&renames->cached_irrelevant[side],
3146 p->one->path);
3148 if (val <= 0)
3149 return;
3152 if (p->status == 'D') {
3154 * If we already had this delete, we'll just set it's value
3155 * to NULL again, so no harm.
3157 strmap_put(&renames->cached_pairs[side], p->one->path, NULL);
3158 } else if (p->status == 'R') {
3159 if (!new_path)
3160 new_path = p->two->path;
3161 else
3162 cache_new_pair(renames, dir_renamed_side,
3163 p->two->path, new_path, 0);
3164 cache_new_pair(renames, side, p->one->path, new_path, 1);
3165 } else if (p->status == 'A' && new_path) {
3166 cache_new_pair(renames, dir_renamed_side,
3167 p->two->path, new_path, 0);
3171 static int compare_pairs(const void *a_, const void *b_)
3173 const struct diff_filepair *a = *((const struct diff_filepair **)a_);
3174 const struct diff_filepair *b = *((const struct diff_filepair **)b_);
3176 return strcmp(a->one->path, b->one->path);
3179 /* Call diffcore_rename() to update deleted/added pairs into rename pairs */
3180 static int detect_regular_renames(struct merge_options *opt,
3181 unsigned side_index)
3183 struct diff_options diff_opts;
3184 struct rename_info *renames = &opt->priv->renames;
3186 prune_cached_from_relevant(renames, side_index);
3187 if (!possible_side_renames(renames, side_index)) {
3189 * No rename detection needed for this side, but we still need
3190 * to make sure 'adds' are marked correctly in case the other
3191 * side had directory renames.
3193 resolve_diffpair_statuses(&renames->pairs[side_index]);
3194 return 0;
3197 partial_clear_dir_rename_count(&renames->dir_rename_count[side_index]);
3198 repo_diff_setup(opt->repo, &diff_opts);
3199 diff_opts.flags.recursive = 1;
3200 diff_opts.flags.rename_empty = 0;
3201 diff_opts.detect_rename = DIFF_DETECT_RENAME;
3202 diff_opts.rename_limit = opt->rename_limit;
3203 if (opt->rename_limit <= 0)
3204 diff_opts.rename_limit = 7000;
3205 diff_opts.rename_score = opt->rename_score;
3206 diff_opts.show_rename_progress = opt->show_rename_progress;
3207 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
3208 diff_setup_done(&diff_opts);
3210 diff_queued_diff = renames->pairs[side_index];
3211 trace2_region_enter("diff", "diffcore_rename", opt->repo);
3212 diffcore_rename_extended(&diff_opts,
3213 &opt->priv->pool,
3214 &renames->relevant_sources[side_index],
3215 &renames->dirs_removed[side_index],
3216 &renames->dir_rename_count[side_index],
3217 &renames->cached_pairs[side_index]);
3218 trace2_region_leave("diff", "diffcore_rename", opt->repo);
3219 resolve_diffpair_statuses(&diff_queued_diff);
3221 if (diff_opts.needed_rename_limit > 0)
3222 renames->redo_after_renames = 0;
3223 if (diff_opts.needed_rename_limit > renames->needed_limit)
3224 renames->needed_limit = diff_opts.needed_rename_limit;
3226 renames->pairs[side_index] = diff_queued_diff;
3228 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
3229 diff_queued_diff.nr = 0;
3230 diff_queued_diff.queue = NULL;
3231 diff_flush(&diff_opts);
3233 return 1;
3237 * Get information of all renames which occurred in 'side_pairs', making use
3238 * of any implicit directory renames in side_dir_renames (also making use of
3239 * implicit directory renames rename_exclusions as needed by
3240 * check_for_directory_rename()). Add all (updated) renames into result.
3242 static int collect_renames(struct merge_options *opt,
3243 struct diff_queue_struct *result,
3244 unsigned side_index,
3245 struct strmap *collisions,
3246 struct strmap *dir_renames_for_side,
3247 struct strmap *rename_exclusions)
3249 int i, clean = 1;
3250 struct diff_queue_struct *side_pairs;
3251 struct rename_info *renames = &opt->priv->renames;
3253 side_pairs = &renames->pairs[side_index];
3255 for (i = 0; i < side_pairs->nr; ++i) {
3256 struct diff_filepair *p = side_pairs->queue[i];
3257 char *new_path; /* non-NULL only with directory renames */
3259 if (p->status != 'A' && p->status != 'R') {
3260 possibly_cache_new_pair(renames, p, side_index, NULL);
3261 pool_diff_free_filepair(&opt->priv->pool, p);
3262 continue;
3265 new_path = check_for_directory_rename(opt, p->two->path,
3266 side_index,
3267 dir_renames_for_side,
3268 rename_exclusions,
3269 collisions,
3270 &clean);
3272 possibly_cache_new_pair(renames, p, side_index, new_path);
3273 if (p->status != 'R' && !new_path) {
3274 pool_diff_free_filepair(&opt->priv->pool, p);
3275 continue;
3278 if (new_path)
3279 apply_directory_rename_modifications(opt, p, new_path);
3282 * p->score comes back from diffcore_rename_extended() with
3283 * the similarity of the renamed file. The similarity is
3284 * was used to determine that the two files were related
3285 * and are a rename, which we have already used, but beyond
3286 * that we have no use for the similarity. So p->score is
3287 * now irrelevant. However, process_renames() will need to
3288 * know which side of the merge this rename was associated
3289 * with, so overwrite p->score with that value.
3291 p->score = side_index;
3292 result->queue[result->nr++] = p;
3295 return clean;
3298 static int detect_and_process_renames(struct merge_options *opt,
3299 struct tree *merge_base,
3300 struct tree *side1,
3301 struct tree *side2)
3303 struct diff_queue_struct combined = { 0 };
3304 struct rename_info *renames = &opt->priv->renames;
3305 struct strmap collisions[3];
3306 int need_dir_renames, s, i, clean = 1;
3307 unsigned detection_run = 0;
3309 if (!possible_renames(renames))
3310 goto cleanup;
3312 trace2_region_enter("merge", "regular renames", opt->repo);
3313 detection_run |= detect_regular_renames(opt, MERGE_SIDE1);
3314 detection_run |= detect_regular_renames(opt, MERGE_SIDE2);
3315 if (renames->needed_limit) {
3316 renames->cached_pairs_valid_side = 0;
3317 renames->redo_after_renames = 0;
3319 if (renames->redo_after_renames && detection_run) {
3320 int i, side;
3321 struct diff_filepair *p;
3323 /* Cache the renames, we found */
3324 for (side = MERGE_SIDE1; side <= MERGE_SIDE2; side++) {
3325 for (i = 0; i < renames->pairs[side].nr; ++i) {
3326 p = renames->pairs[side].queue[i];
3327 possibly_cache_new_pair(renames, p, side, NULL);
3331 /* Restart the merge with the cached renames */
3332 renames->redo_after_renames = 2;
3333 trace2_region_leave("merge", "regular renames", opt->repo);
3334 goto cleanup;
3336 use_cached_pairs(opt, &renames->cached_pairs[1], &renames->pairs[1]);
3337 use_cached_pairs(opt, &renames->cached_pairs[2], &renames->pairs[2]);
3338 trace2_region_leave("merge", "regular renames", opt->repo);
3340 trace2_region_enter("merge", "directory renames", opt->repo);
3341 need_dir_renames =
3342 !opt->priv->call_depth &&
3343 (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE ||
3344 opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_CONFLICT);
3346 if (need_dir_renames) {
3347 get_provisional_directory_renames(opt, MERGE_SIDE1, &clean);
3348 get_provisional_directory_renames(opt, MERGE_SIDE2, &clean);
3349 handle_directory_level_conflicts(opt);
3352 ALLOC_GROW(combined.queue,
3353 renames->pairs[1].nr + renames->pairs[2].nr,
3354 combined.alloc);
3355 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {
3356 int other_side = 3 - i;
3357 compute_collisions(&collisions[i],
3358 &renames->dir_renames[other_side],
3359 &renames->pairs[i]);
3361 clean &= collect_renames(opt, &combined, MERGE_SIDE1,
3362 collisions,
3363 &renames->dir_renames[2],
3364 &renames->dir_renames[1]);
3365 clean &= collect_renames(opt, &combined, MERGE_SIDE2,
3366 collisions,
3367 &renames->dir_renames[1],
3368 &renames->dir_renames[2]);
3369 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++)
3370 free_collisions(&collisions[i]);
3371 STABLE_QSORT(combined.queue, combined.nr, compare_pairs);
3372 trace2_region_leave("merge", "directory renames", opt->repo);
3374 trace2_region_enter("merge", "process renames", opt->repo);
3375 clean &= process_renames(opt, &combined);
3376 trace2_region_leave("merge", "process renames", opt->repo);
3378 goto simple_cleanup; /* collect_renames() handles some of cleanup */
3380 cleanup:
3382 * Free now unneeded filepairs, which would have been handled
3383 * in collect_renames() normally but we skipped that code.
3385 for (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {
3386 struct diff_queue_struct *side_pairs;
3387 int i;
3389 side_pairs = &renames->pairs[s];
3390 for (i = 0; i < side_pairs->nr; ++i) {
3391 struct diff_filepair *p = side_pairs->queue[i];
3392 pool_diff_free_filepair(&opt->priv->pool, p);
3396 simple_cleanup:
3397 /* Free memory for renames->pairs[] and combined */
3398 for (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {
3399 free(renames->pairs[s].queue);
3400 DIFF_QUEUE_CLEAR(&renames->pairs[s]);
3402 for (i = 0; i < combined.nr; i++)
3403 pool_diff_free_filepair(&opt->priv->pool, combined.queue[i]);
3404 free(combined.queue);
3406 return clean;
3409 /*** Function Grouping: functions related to process_entries() ***/
3411 static int sort_dirs_next_to_their_children(const char *one, const char *two)
3413 unsigned char c1, c2;
3416 * Here we only care that entries for directories appear adjacent
3417 * to and before files underneath the directory. We can achieve
3418 * that by pretending to add a trailing slash to every file and
3419 * then sorting. In other words, we do not want the natural
3420 * sorting of
3421 * foo
3422 * foo.txt
3423 * foo/bar
3424 * Instead, we want "foo" to sort as though it were "foo/", so that
3425 * we instead get
3426 * foo.txt
3427 * foo
3428 * foo/bar
3429 * To achieve this, we basically implement our own strcmp, except that
3430 * if we get to the end of either string instead of comparing NUL to
3431 * another character, we compare '/' to it.
3433 * If this unusual "sort as though '/' were appended" perplexes
3434 * you, perhaps it will help to note that this is not the final
3435 * sort. write_tree() will sort again without the trailing slash
3436 * magic, but just on paths immediately under a given tree.
3438 * The reason to not use df_name_compare directly was that it was
3439 * just too expensive (we don't have the string lengths handy), so
3440 * it was reimplemented.
3444 * NOTE: This function will never be called with two equal strings,
3445 * because it is used to sort the keys of a strmap, and strmaps have
3446 * unique keys by construction. That simplifies our c1==c2 handling
3447 * below.
3450 while (*one && (*one == *two)) {
3451 one++;
3452 two++;
3455 c1 = *one ? *one : '/';
3456 c2 = *two ? *two : '/';
3458 if (c1 == c2) {
3459 /* Getting here means one is a leading directory of the other */
3460 return (*one) ? 1 : -1;
3461 } else
3462 return c1 - c2;
3465 static int read_oid_strbuf(struct merge_options *opt,
3466 const struct object_id *oid,
3467 struct strbuf *dst)
3469 void *buf;
3470 enum object_type type;
3471 unsigned long size;
3472 buf = read_object_file(oid, &type, &size);
3473 if (!buf)
3474 return err(opt, _("cannot read object %s"), oid_to_hex(oid));
3475 if (type != OBJ_BLOB) {
3476 free(buf);
3477 return err(opt, _("object %s is not a blob"), oid_to_hex(oid));
3479 strbuf_attach(dst, buf, size, size + 1);
3480 return 0;
3483 static int blob_unchanged(struct merge_options *opt,
3484 const struct version_info *base,
3485 const struct version_info *side,
3486 const char *path)
3488 struct strbuf basebuf = STRBUF_INIT;
3489 struct strbuf sidebuf = STRBUF_INIT;
3490 int ret = 0; /* assume changed for safety */
3491 struct index_state *idx = &opt->priv->attr_index;
3493 if (!idx->initialized)
3494 initialize_attr_index(opt);
3496 if (base->mode != side->mode)
3497 return 0;
3498 if (oideq(&base->oid, &side->oid))
3499 return 1;
3501 if (read_oid_strbuf(opt, &base->oid, &basebuf) ||
3502 read_oid_strbuf(opt, &side->oid, &sidebuf))
3503 goto error_return;
3505 * Note: binary | is used so that both renormalizations are
3506 * performed. Comparison can be skipped if both files are
3507 * unchanged since their sha1s have already been compared.
3509 if (renormalize_buffer(idx, path, basebuf.buf, basebuf.len, &basebuf) |
3510 renormalize_buffer(idx, path, sidebuf.buf, sidebuf.len, &sidebuf))
3511 ret = (basebuf.len == sidebuf.len &&
3512 !memcmp(basebuf.buf, sidebuf.buf, basebuf.len));
3514 error_return:
3515 strbuf_release(&basebuf);
3516 strbuf_release(&sidebuf);
3517 return ret;
3520 struct directory_versions {
3522 * versions: list of (basename -> version_info)
3524 * The basenames are in reverse lexicographic order of full pathnames,
3525 * as processed in process_entries(). This puts all entries within
3526 * a directory together, and covers the directory itself after
3527 * everything within it, allowing us to write subtrees before needing
3528 * to record information for the tree itself.
3530 struct string_list versions;
3533 * offsets: list of (full relative path directories -> integer offsets)
3535 * Since versions contains basenames from files in multiple different
3536 * directories, we need to know which entries in versions correspond
3537 * to which directories. Values of e.g.
3538 * "" 0
3539 * src 2
3540 * src/moduleA 5
3541 * Would mean that entries 0-1 of versions are files in the toplevel
3542 * directory, entries 2-4 are files under src/, and the remaining
3543 * entries starting at index 5 are files under src/moduleA/.
3545 struct string_list offsets;
3548 * last_directory: directory that previously processed file found in
3550 * last_directory starts NULL, but records the directory in which the
3551 * previous file was found within. As soon as
3552 * directory(current_file) != last_directory
3553 * then we need to start updating accounting in versions & offsets.
3554 * Note that last_directory is always the last path in "offsets" (or
3555 * NULL if "offsets" is empty) so this exists just for quick access.
3557 const char *last_directory;
3559 /* last_directory_len: cached computation of strlen(last_directory) */
3560 unsigned last_directory_len;
3563 static int tree_entry_order(const void *a_, const void *b_)
3565 const struct string_list_item *a = a_;
3566 const struct string_list_item *b = b_;
3568 const struct merged_info *ami = a->util;
3569 const struct merged_info *bmi = b->util;
3570 return base_name_compare(a->string, strlen(a->string), ami->result.mode,
3571 b->string, strlen(b->string), bmi->result.mode);
3574 static void write_tree(struct object_id *result_oid,
3575 struct string_list *versions,
3576 unsigned int offset,
3577 size_t hash_size)
3579 size_t maxlen = 0, extra;
3580 unsigned int nr;
3581 struct strbuf buf = STRBUF_INIT;
3582 int i;
3584 assert(offset <= versions->nr);
3585 nr = versions->nr - offset;
3586 if (versions->nr)
3587 /* No need for STABLE_QSORT -- filenames must be unique */
3588 QSORT(versions->items + offset, nr, tree_entry_order);
3590 /* Pre-allocate some space in buf */
3591 extra = hash_size + 8; /* 8: 6 for mode, 1 for space, 1 for NUL char */
3592 for (i = 0; i < nr; i++) {
3593 maxlen += strlen(versions->items[offset+i].string) + extra;
3595 strbuf_grow(&buf, maxlen);
3597 /* Write each entry out to buf */
3598 for (i = 0; i < nr; i++) {
3599 struct merged_info *mi = versions->items[offset+i].util;
3600 struct version_info *ri = &mi->result;
3601 strbuf_addf(&buf, "%o %s%c",
3602 ri->mode,
3603 versions->items[offset+i].string, '\0');
3604 strbuf_add(&buf, ri->oid.hash, hash_size);
3607 /* Write this object file out, and record in result_oid */
3608 write_object_file(buf.buf, buf.len, OBJ_TREE, result_oid);
3609 strbuf_release(&buf);
3612 static void record_entry_for_tree(struct directory_versions *dir_metadata,
3613 const char *path,
3614 struct merged_info *mi)
3616 const char *basename;
3618 if (mi->is_null)
3619 /* nothing to record */
3620 return;
3622 basename = path + mi->basename_offset;
3623 assert(strchr(basename, '/') == NULL);
3624 string_list_append(&dir_metadata->versions,
3625 basename)->util = &mi->result;
3628 static void write_completed_directory(struct merge_options *opt,
3629 const char *new_directory_name,
3630 struct directory_versions *info)
3632 const char *prev_dir;
3633 struct merged_info *dir_info = NULL;
3634 unsigned int offset;
3637 * Some explanation of info->versions and info->offsets...
3639 * process_entries() iterates over all relevant files AND
3640 * directories in reverse lexicographic order, and calls this
3641 * function. Thus, an example of the paths that process_entries()
3642 * could operate on (along with the directories for those paths
3643 * being shown) is:
3645 * xtract.c ""
3646 * tokens.txt ""
3647 * src/moduleB/umm.c src/moduleB
3648 * src/moduleB/stuff.h src/moduleB
3649 * src/moduleB/baz.c src/moduleB
3650 * src/moduleB src
3651 * src/moduleA/foo.c src/moduleA
3652 * src/moduleA/bar.c src/moduleA
3653 * src/moduleA src
3654 * src ""
3655 * Makefile ""
3657 * info->versions:
3659 * always contains the unprocessed entries and their
3660 * version_info information. For example, after the first five
3661 * entries above, info->versions would be:
3663 * xtract.c <xtract.c's version_info>
3664 * token.txt <token.txt's version_info>
3665 * umm.c <src/moduleB/umm.c's version_info>
3666 * stuff.h <src/moduleB/stuff.h's version_info>
3667 * baz.c <src/moduleB/baz.c's version_info>
3669 * Once a subdirectory is completed we remove the entries in
3670 * that subdirectory from info->versions, writing it as a tree
3671 * (write_tree()). Thus, as soon as we get to src/moduleB,
3672 * info->versions would be updated to
3674 * xtract.c <xtract.c's version_info>
3675 * token.txt <token.txt's version_info>
3676 * moduleB <src/moduleB's version_info>
3678 * info->offsets:
3680 * helps us track which entries in info->versions correspond to
3681 * which directories. When we are N directories deep (e.g. 4
3682 * for src/modA/submod/subdir/), we have up to N+1 unprocessed
3683 * directories (+1 because of toplevel dir). Corresponding to
3684 * the info->versions example above, after processing five entries
3685 * info->offsets will be:
3687 * "" 0
3688 * src/moduleB 2
3690 * which is used to know that xtract.c & token.txt are from the
3691 * toplevel dirctory, while umm.c & stuff.h & baz.c are from the
3692 * src/moduleB directory. Again, following the example above,
3693 * once we need to process src/moduleB, then info->offsets is
3694 * updated to
3696 * "" 0
3697 * src 2
3699 * which says that moduleB (and only moduleB so far) is in the
3700 * src directory.
3702 * One unique thing to note about info->offsets here is that
3703 * "src" was not added to info->offsets until there was a path
3704 * (a file OR directory) immediately below src/ that got
3705 * processed.
3707 * Since process_entry() just appends new entries to info->versions,
3708 * write_completed_directory() only needs to do work if the next path
3709 * is in a directory that is different than the last directory found
3710 * in info->offsets.
3714 * If we are working with the same directory as the last entry, there
3715 * is no work to do. (See comments above the directory_name member of
3716 * struct merged_info for why we can use pointer comparison instead of
3717 * strcmp here.)
3719 if (new_directory_name == info->last_directory)
3720 return;
3723 * If we are just starting (last_directory is NULL), or last_directory
3724 * is a prefix of the current directory, then we can just update
3725 * info->offsets to record the offset where we started this directory
3726 * and update last_directory to have quick access to it.
3728 if (info->last_directory == NULL ||
3729 !strncmp(new_directory_name, info->last_directory,
3730 info->last_directory_len)) {
3731 uintptr_t offset = info->versions.nr;
3733 info->last_directory = new_directory_name;
3734 info->last_directory_len = strlen(info->last_directory);
3736 * Record the offset into info->versions where we will
3737 * start recording basenames of paths found within
3738 * new_directory_name.
3740 string_list_append(&info->offsets,
3741 info->last_directory)->util = (void*)offset;
3742 return;
3746 * The next entry that will be processed will be within
3747 * new_directory_name. Since at this point we know that
3748 * new_directory_name is within a different directory than
3749 * info->last_directory, we have all entries for info->last_directory
3750 * in info->versions and we need to create a tree object for them.
3752 dir_info = strmap_get(&opt->priv->paths, info->last_directory);
3753 assert(dir_info);
3754 offset = (uintptr_t)info->offsets.items[info->offsets.nr-1].util;
3755 if (offset == info->versions.nr) {
3757 * Actually, we don't need to create a tree object in this
3758 * case. Whenever all files within a directory disappear
3759 * during the merge (e.g. unmodified on one side and
3760 * deleted on the other, or files were renamed elsewhere),
3761 * then we get here and the directory itself needs to be
3762 * omitted from its parent tree as well.
3764 dir_info->is_null = 1;
3765 } else {
3767 * Write out the tree to the git object directory, and also
3768 * record the mode and oid in dir_info->result.
3770 dir_info->is_null = 0;
3771 dir_info->result.mode = S_IFDIR;
3772 write_tree(&dir_info->result.oid, &info->versions, offset,
3773 opt->repo->hash_algo->rawsz);
3777 * We've now used several entries from info->versions and one entry
3778 * from info->offsets, so we get rid of those values.
3780 info->offsets.nr--;
3781 info->versions.nr = offset;
3784 * Now we've taken care of the completed directory, but we need to
3785 * prepare things since future entries will be in
3786 * new_directory_name. (In particular, process_entry() will be
3787 * appending new entries to info->versions.) So, we need to make
3788 * sure new_directory_name is the last entry in info->offsets.
3790 prev_dir = info->offsets.nr == 0 ? NULL :
3791 info->offsets.items[info->offsets.nr-1].string;
3792 if (new_directory_name != prev_dir) {
3793 uintptr_t c = info->versions.nr;
3794 string_list_append(&info->offsets,
3795 new_directory_name)->util = (void*)c;
3798 /* And, of course, we need to update last_directory to match. */
3799 info->last_directory = new_directory_name;
3800 info->last_directory_len = strlen(info->last_directory);
3803 /* Per entry merge function */
3804 static void process_entry(struct merge_options *opt,
3805 const char *path,
3806 struct conflict_info *ci,
3807 struct directory_versions *dir_metadata)
3809 int df_file_index = 0;
3811 VERIFY_CI(ci);
3812 assert(ci->filemask >= 0 && ci->filemask <= 7);
3813 /* ci->match_mask == 7 was handled in collect_merge_info_callback() */
3814 assert(ci->match_mask == 0 || ci->match_mask == 3 ||
3815 ci->match_mask == 5 || ci->match_mask == 6);
3817 if (ci->dirmask) {
3818 record_entry_for_tree(dir_metadata, path, &ci->merged);
3819 if (ci->filemask == 0)
3820 /* nothing else to handle */
3821 return;
3822 assert(ci->df_conflict);
3825 if (ci->df_conflict && ci->merged.result.mode == 0) {
3826 int i;
3829 * directory no longer in the way, but we do have a file we
3830 * need to place here so we need to clean away the "directory
3831 * merges to nothing" result.
3833 ci->df_conflict = 0;
3834 assert(ci->filemask != 0);
3835 ci->merged.clean = 0;
3836 ci->merged.is_null = 0;
3837 /* and we want to zero out any directory-related entries */
3838 ci->match_mask = (ci->match_mask & ~ci->dirmask);
3839 ci->dirmask = 0;
3840 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
3841 if (ci->filemask & (1 << i))
3842 continue;
3843 ci->stages[i].mode = 0;
3844 oidcpy(&ci->stages[i].oid, null_oid());
3846 } else if (ci->df_conflict && ci->merged.result.mode != 0) {
3848 * This started out as a D/F conflict, and the entries in
3849 * the competing directory were not removed by the merge as
3850 * evidenced by write_completed_directory() writing a value
3851 * to ci->merged.result.mode.
3853 struct conflict_info *new_ci;
3854 const char *branch;
3855 const char *old_path = path;
3856 int i;
3858 assert(ci->merged.result.mode == S_IFDIR);
3861 * If filemask is 1, we can just ignore the file as having
3862 * been deleted on both sides. We do not want to overwrite
3863 * ci->merged.result, since it stores the tree for all the
3864 * files under it.
3866 if (ci->filemask == 1) {
3867 ci->filemask = 0;
3868 return;
3872 * This file still exists on at least one side, and we want
3873 * the directory to remain here, so we need to move this
3874 * path to some new location.
3876 new_ci = mem_pool_calloc(&opt->priv->pool, 1, sizeof(*new_ci));
3878 /* We don't really want new_ci->merged.result copied, but it'll
3879 * be overwritten below so it doesn't matter. We also don't
3880 * want any directory mode/oid values copied, but we'll zero
3881 * those out immediately. We do want the rest of ci copied.
3883 memcpy(new_ci, ci, sizeof(*ci));
3884 new_ci->match_mask = (new_ci->match_mask & ~new_ci->dirmask);
3885 new_ci->dirmask = 0;
3886 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
3887 if (new_ci->filemask & (1 << i))
3888 continue;
3889 /* zero out any entries related to directories */
3890 new_ci->stages[i].mode = 0;
3891 oidcpy(&new_ci->stages[i].oid, null_oid());
3895 * Find out which side this file came from; note that we
3896 * cannot just use ci->filemask, because renames could cause
3897 * the filemask to go back to 7. So we use dirmask, then
3898 * pick the opposite side's index.
3900 df_file_index = (ci->dirmask & (1 << 1)) ? 2 : 1;
3901 branch = (df_file_index == 1) ? opt->branch1 : opt->branch2;
3902 path = unique_path(opt, path, branch);
3903 strmap_put(&opt->priv->paths, path, new_ci);
3905 path_msg(opt, CONFLICT_FILE_DIRECTORY, 0,
3906 path, old_path, NULL, NULL,
3907 _("CONFLICT (file/directory): directory in the way "
3908 "of %s from %s; moving it to %s instead."),
3909 old_path, branch, path);
3912 * Zero out the filemask for the old ci. At this point, ci
3913 * was just an entry for a directory, so we don't need to
3914 * do anything more with it.
3916 ci->filemask = 0;
3919 * Now note that we're working on the new entry (path was
3920 * updated above.
3922 ci = new_ci;
3926 * NOTE: Below there is a long switch-like if-elseif-elseif... block
3927 * which the code goes through even for the df_conflict cases
3928 * above.
3930 if (ci->match_mask) {
3931 ci->merged.clean = !ci->df_conflict && !ci->path_conflict;
3932 if (ci->match_mask == 6) {
3933 /* stages[1] == stages[2] */
3934 ci->merged.result.mode = ci->stages[1].mode;
3935 oidcpy(&ci->merged.result.oid, &ci->stages[1].oid);
3936 } else {
3937 /* determine the mask of the side that didn't match */
3938 unsigned int othermask = 7 & ~ci->match_mask;
3939 int side = (othermask == 4) ? 2 : 1;
3941 ci->merged.result.mode = ci->stages[side].mode;
3942 ci->merged.is_null = !ci->merged.result.mode;
3943 if (ci->merged.is_null)
3944 ci->merged.clean = 1;
3945 oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
3947 assert(othermask == 2 || othermask == 4);
3948 assert(ci->merged.is_null ==
3949 (ci->filemask == ci->match_mask));
3951 } else if (ci->filemask >= 6 &&
3952 (S_IFMT & ci->stages[1].mode) !=
3953 (S_IFMT & ci->stages[2].mode)) {
3954 /* Two different items from (file/submodule/symlink) */
3955 if (opt->priv->call_depth) {
3956 /* Just use the version from the merge base */
3957 ci->merged.clean = 0;
3958 oidcpy(&ci->merged.result.oid, &ci->stages[0].oid);
3959 ci->merged.result.mode = ci->stages[0].mode;
3960 ci->merged.is_null = (ci->merged.result.mode == 0);
3961 } else {
3962 /* Handle by renaming one or both to separate paths. */
3963 unsigned o_mode = ci->stages[0].mode;
3964 unsigned a_mode = ci->stages[1].mode;
3965 unsigned b_mode = ci->stages[2].mode;
3966 struct conflict_info *new_ci;
3967 const char *a_path = NULL, *b_path = NULL;
3968 int rename_a = 0, rename_b = 0;
3970 new_ci = mem_pool_alloc(&opt->priv->pool,
3971 sizeof(*new_ci));
3973 if (S_ISREG(a_mode))
3974 rename_a = 1;
3975 else if (S_ISREG(b_mode))
3976 rename_b = 1;
3977 else {
3978 rename_a = 1;
3979 rename_b = 1;
3982 if (rename_a)
3983 a_path = unique_path(opt, path, opt->branch1);
3984 if (rename_b)
3985 b_path = unique_path(opt, path, opt->branch2);
3987 if (rename_a && rename_b) {
3988 path_msg(opt, CONFLICT_DISTINCT_MODES, 0,
3989 path, a_path, b_path, NULL,
3990 _("CONFLICT (distinct types): %s had "
3991 "different types on each side; "
3992 "renamed both of them so each can "
3993 "be recorded somewhere."),
3994 path);
3995 } else {
3996 path_msg(opt, CONFLICT_DISTINCT_MODES, 0,
3997 path, rename_a ? a_path : b_path,
3998 NULL, NULL,
3999 _("CONFLICT (distinct types): %s had "
4000 "different types on each side; "
4001 "renamed one of them so each can be "
4002 "recorded somewhere."),
4003 path);
4006 ci->merged.clean = 0;
4007 memcpy(new_ci, ci, sizeof(*new_ci));
4009 /* Put b into new_ci, removing a from stages */
4010 new_ci->merged.result.mode = ci->stages[2].mode;
4011 oidcpy(&new_ci->merged.result.oid, &ci->stages[2].oid);
4012 new_ci->stages[1].mode = 0;
4013 oidcpy(&new_ci->stages[1].oid, null_oid());
4014 new_ci->filemask = 5;
4015 if ((S_IFMT & b_mode) != (S_IFMT & o_mode)) {
4016 new_ci->stages[0].mode = 0;
4017 oidcpy(&new_ci->stages[0].oid, null_oid());
4018 new_ci->filemask = 4;
4021 /* Leave only a in ci, fixing stages. */
4022 ci->merged.result.mode = ci->stages[1].mode;
4023 oidcpy(&ci->merged.result.oid, &ci->stages[1].oid);
4024 ci->stages[2].mode = 0;
4025 oidcpy(&ci->stages[2].oid, null_oid());
4026 ci->filemask = 3;
4027 if ((S_IFMT & a_mode) != (S_IFMT & o_mode)) {
4028 ci->stages[0].mode = 0;
4029 oidcpy(&ci->stages[0].oid, null_oid());
4030 ci->filemask = 2;
4033 /* Insert entries into opt->priv_paths */
4034 assert(rename_a || rename_b);
4035 if (rename_a)
4036 strmap_put(&opt->priv->paths, a_path, ci);
4038 if (!rename_b)
4039 b_path = path;
4040 strmap_put(&opt->priv->paths, b_path, new_ci);
4042 if (rename_a && rename_b)
4043 strmap_remove(&opt->priv->paths, path, 0);
4046 * Do special handling for b_path since process_entry()
4047 * won't be called on it specially.
4049 strmap_put(&opt->priv->conflicted, b_path, new_ci);
4050 record_entry_for_tree(dir_metadata, b_path,
4051 &new_ci->merged);
4054 * Remaining code for processing this entry should
4055 * think in terms of processing a_path.
4057 if (a_path)
4058 path = a_path;
4060 } else if (ci->filemask >= 6) {
4061 /* Need a two-way or three-way content merge */
4062 struct version_info merged_file;
4063 unsigned clean_merge;
4064 struct version_info *o = &ci->stages[0];
4065 struct version_info *a = &ci->stages[1];
4066 struct version_info *b = &ci->stages[2];
4068 clean_merge = handle_content_merge(opt, path, o, a, b,
4069 ci->pathnames,
4070 opt->priv->call_depth * 2,
4071 &merged_file);
4072 ci->merged.clean = clean_merge &&
4073 !ci->df_conflict && !ci->path_conflict;
4074 ci->merged.result.mode = merged_file.mode;
4075 ci->merged.is_null = (merged_file.mode == 0);
4076 oidcpy(&ci->merged.result.oid, &merged_file.oid);
4077 if (clean_merge && ci->df_conflict) {
4078 assert(df_file_index == 1 || df_file_index == 2);
4079 ci->filemask = 1 << df_file_index;
4080 ci->stages[df_file_index].mode = merged_file.mode;
4081 oidcpy(&ci->stages[df_file_index].oid, &merged_file.oid);
4083 if (!clean_merge) {
4084 const char *reason = _("content");
4085 if (ci->filemask == 6)
4086 reason = _("add/add");
4087 if (S_ISGITLINK(merged_file.mode))
4088 reason = _("submodule");
4089 path_msg(opt, CONFLICT_CONTENTS, 0,
4090 path, NULL, NULL, NULL,
4091 _("CONFLICT (%s): Merge conflict in %s"),
4092 reason, path);
4094 } else if (ci->filemask == 3 || ci->filemask == 5) {
4095 /* Modify/delete */
4096 const char *modify_branch, *delete_branch;
4097 int side = (ci->filemask == 5) ? 2 : 1;
4098 int index = opt->priv->call_depth ? 0 : side;
4100 ci->merged.result.mode = ci->stages[index].mode;
4101 oidcpy(&ci->merged.result.oid, &ci->stages[index].oid);
4102 ci->merged.clean = 0;
4104 modify_branch = (side == 1) ? opt->branch1 : opt->branch2;
4105 delete_branch = (side == 1) ? opt->branch2 : opt->branch1;
4107 if (opt->renormalize &&
4108 blob_unchanged(opt, &ci->stages[0], &ci->stages[side],
4109 path)) {
4110 if (!ci->path_conflict) {
4112 * Blob unchanged after renormalization, so
4113 * there's no modify/delete conflict after all;
4114 * we can just remove the file.
4116 ci->merged.is_null = 1;
4117 ci->merged.clean = 1;
4119 * file goes away => even if there was a
4120 * directory/file conflict there isn't one now.
4122 ci->df_conflict = 0;
4123 } else {
4124 /* rename/delete, so conflict remains */
4126 } else if (ci->path_conflict &&
4127 oideq(&ci->stages[0].oid, &ci->stages[side].oid)) {
4129 * This came from a rename/delete; no action to take,
4130 * but avoid printing "modify/delete" conflict notice
4131 * since the contents were not modified.
4133 } else {
4134 path_msg(opt, CONFLICT_MODIFY_DELETE, 0,
4135 path, NULL, NULL, NULL,
4136 _("CONFLICT (modify/delete): %s deleted in %s "
4137 "and modified in %s. Version %s of %s left "
4138 "in tree."),
4139 path, delete_branch, modify_branch,
4140 modify_branch, path);
4142 } else if (ci->filemask == 2 || ci->filemask == 4) {
4143 /* Added on one side */
4144 int side = (ci->filemask == 4) ? 2 : 1;
4145 ci->merged.result.mode = ci->stages[side].mode;
4146 oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
4147 ci->merged.clean = !ci->df_conflict && !ci->path_conflict;
4148 } else if (ci->filemask == 1) {
4149 /* Deleted on both sides */
4150 ci->merged.is_null = 1;
4151 ci->merged.result.mode = 0;
4152 oidcpy(&ci->merged.result.oid, null_oid());
4153 assert(!ci->df_conflict);
4154 ci->merged.clean = !ci->path_conflict;
4158 * If still conflicted, record it separately. This allows us to later
4159 * iterate over just conflicted entries when updating the index instead
4160 * of iterating over all entries.
4162 if (!ci->merged.clean)
4163 strmap_put(&opt->priv->conflicted, path, ci);
4165 /* Record metadata for ci->merged in dir_metadata */
4166 record_entry_for_tree(dir_metadata, path, &ci->merged);
4169 static void prefetch_for_content_merges(struct merge_options *opt,
4170 struct string_list *plist)
4172 struct string_list_item *e;
4173 struct oid_array to_fetch = OID_ARRAY_INIT;
4175 if (opt->repo != the_repository || !has_promisor_remote())
4176 return;
4178 for (e = &plist->items[plist->nr-1]; e >= plist->items; --e) {
4179 /* char *path = e->string; */
4180 struct conflict_info *ci = e->util;
4181 int i;
4183 /* Ignore clean entries */
4184 if (ci->merged.clean)
4185 continue;
4187 /* Ignore entries that don't need a content merge */
4188 if (ci->match_mask || ci->filemask < 6 ||
4189 !S_ISREG(ci->stages[1].mode) ||
4190 !S_ISREG(ci->stages[2].mode) ||
4191 oideq(&ci->stages[1].oid, &ci->stages[2].oid))
4192 continue;
4194 /* Also don't need content merge if base matches either side */
4195 if (ci->filemask == 7 &&
4196 S_ISREG(ci->stages[0].mode) &&
4197 (oideq(&ci->stages[0].oid, &ci->stages[1].oid) ||
4198 oideq(&ci->stages[0].oid, &ci->stages[2].oid)))
4199 continue;
4201 for (i = 0; i < 3; i++) {
4202 unsigned side_mask = (1 << i);
4203 struct version_info *vi = &ci->stages[i];
4205 if ((ci->filemask & side_mask) &&
4206 S_ISREG(vi->mode) &&
4207 oid_object_info_extended(opt->repo, &vi->oid, NULL,
4208 OBJECT_INFO_FOR_PREFETCH))
4209 oid_array_append(&to_fetch, &vi->oid);
4213 promisor_remote_get_direct(opt->repo, to_fetch.oid, to_fetch.nr);
4214 oid_array_clear(&to_fetch);
4217 static void process_entries(struct merge_options *opt,
4218 struct object_id *result_oid)
4220 struct hashmap_iter iter;
4221 struct strmap_entry *e;
4222 struct string_list plist = STRING_LIST_INIT_NODUP;
4223 struct string_list_item *entry;
4224 struct directory_versions dir_metadata = { STRING_LIST_INIT_NODUP,
4225 STRING_LIST_INIT_NODUP,
4226 NULL, 0 };
4228 trace2_region_enter("merge", "process_entries setup", opt->repo);
4229 if (strmap_empty(&opt->priv->paths)) {
4230 oidcpy(result_oid, opt->repo->hash_algo->empty_tree);
4231 return;
4234 /* Hack to pre-allocate plist to the desired size */
4235 trace2_region_enter("merge", "plist grow", opt->repo);
4236 ALLOC_GROW(plist.items, strmap_get_size(&opt->priv->paths), plist.alloc);
4237 trace2_region_leave("merge", "plist grow", opt->repo);
4239 /* Put every entry from paths into plist, then sort */
4240 trace2_region_enter("merge", "plist copy", opt->repo);
4241 strmap_for_each_entry(&opt->priv->paths, &iter, e) {
4242 string_list_append(&plist, e->key)->util = e->value;
4244 trace2_region_leave("merge", "plist copy", opt->repo);
4246 trace2_region_enter("merge", "plist special sort", opt->repo);
4247 plist.cmp = sort_dirs_next_to_their_children;
4248 string_list_sort(&plist);
4249 trace2_region_leave("merge", "plist special sort", opt->repo);
4251 trace2_region_leave("merge", "process_entries setup", opt->repo);
4254 * Iterate over the items in reverse order, so we can handle paths
4255 * below a directory before needing to handle the directory itself.
4257 * This allows us to write subtrees before we need to write trees,
4258 * and it also enables sane handling of directory/file conflicts
4259 * (because it allows us to know whether the directory is still in
4260 * the way when it is time to process the file at the same path).
4262 trace2_region_enter("merge", "processing", opt->repo);
4263 prefetch_for_content_merges(opt, &plist);
4264 for (entry = &plist.items[plist.nr-1]; entry >= plist.items; --entry) {
4265 char *path = entry->string;
4267 * NOTE: mi may actually be a pointer to a conflict_info, but
4268 * we have to check mi->clean first to see if it's safe to
4269 * reassign to such a pointer type.
4271 struct merged_info *mi = entry->util;
4273 write_completed_directory(opt, mi->directory_name,
4274 &dir_metadata);
4275 if (mi->clean)
4276 record_entry_for_tree(&dir_metadata, path, mi);
4277 else {
4278 struct conflict_info *ci = (struct conflict_info *)mi;
4279 process_entry(opt, path, ci, &dir_metadata);
4282 trace2_region_leave("merge", "processing", opt->repo);
4284 trace2_region_enter("merge", "process_entries cleanup", opt->repo);
4285 if (dir_metadata.offsets.nr != 1 ||
4286 (uintptr_t)dir_metadata.offsets.items[0].util != 0) {
4287 printf("dir_metadata.offsets.nr = %"PRIuMAX" (should be 1)\n",
4288 (uintmax_t)dir_metadata.offsets.nr);
4289 printf("dir_metadata.offsets.items[0].util = %u (should be 0)\n",
4290 (unsigned)(uintptr_t)dir_metadata.offsets.items[0].util);
4291 fflush(stdout);
4292 BUG("dir_metadata accounting completely off; shouldn't happen");
4294 write_tree(result_oid, &dir_metadata.versions, 0,
4295 opt->repo->hash_algo->rawsz);
4296 string_list_clear(&plist, 0);
4297 string_list_clear(&dir_metadata.versions, 0);
4298 string_list_clear(&dir_metadata.offsets, 0);
4299 trace2_region_leave("merge", "process_entries cleanup", opt->repo);
4302 /*** Function Grouping: functions related to merge_switch_to_result() ***/
4304 static int checkout(struct merge_options *opt,
4305 struct tree *prev,
4306 struct tree *next)
4308 /* Switch the index/working copy from old to new */
4309 int ret;
4310 struct tree_desc trees[2];
4311 struct unpack_trees_options unpack_opts;
4313 memset(&unpack_opts, 0, sizeof(unpack_opts));
4314 unpack_opts.head_idx = -1;
4315 unpack_opts.src_index = opt->repo->index;
4316 unpack_opts.dst_index = opt->repo->index;
4318 setup_unpack_trees_porcelain(&unpack_opts, "merge");
4321 * NOTE: if this were just "git checkout" code, we would probably
4322 * read or refresh the cache and check for a conflicted index, but
4323 * builtin/merge.c or sequencer.c really needs to read the index
4324 * and check for conflicted entries before starting merging for a
4325 * good user experience (no sense waiting for merges/rebases before
4326 * erroring out), so there's no reason to duplicate that work here.
4329 /* 2-way merge to the new branch */
4330 unpack_opts.update = 1;
4331 unpack_opts.merge = 1;
4332 unpack_opts.quiet = 0; /* FIXME: sequencer might want quiet? */
4333 unpack_opts.verbose_update = (opt->verbosity > 2);
4334 unpack_opts.fn = twoway_merge;
4335 unpack_opts.preserve_ignored = 0; /* FIXME: !opts->overwrite_ignore */
4336 parse_tree(prev);
4337 init_tree_desc(&trees[0], prev->buffer, prev->size);
4338 parse_tree(next);
4339 init_tree_desc(&trees[1], next->buffer, next->size);
4341 ret = unpack_trees(2, trees, &unpack_opts);
4342 clear_unpack_trees_porcelain(&unpack_opts);
4343 return ret;
4346 static int record_conflicted_index_entries(struct merge_options *opt)
4348 struct hashmap_iter iter;
4349 struct strmap_entry *e;
4350 struct index_state *index = opt->repo->index;
4351 struct checkout state = CHECKOUT_INIT;
4352 int errs = 0;
4353 int original_cache_nr;
4355 if (strmap_empty(&opt->priv->conflicted))
4356 return 0;
4359 * We are in a conflicted state. These conflicts might be inside
4360 * sparse-directory entries, so check if any entries are outside
4361 * of the sparse-checkout cone preemptively.
4363 * We set original_cache_nr below, but that might change if
4364 * index_name_pos() calls ask for paths within sparse directories.
4366 strmap_for_each_entry(&opt->priv->conflicted, &iter, e) {
4367 if (!path_in_sparse_checkout(e->key, index)) {
4368 ensure_full_index(index);
4369 break;
4373 /* If any entries have skip_worktree set, we'll have to check 'em out */
4374 state.force = 1;
4375 state.quiet = 1;
4376 state.refresh_cache = 1;
4377 state.istate = index;
4378 original_cache_nr = index->cache_nr;
4380 /* Append every entry from conflicted into index, then sort */
4381 strmap_for_each_entry(&opt->priv->conflicted, &iter, e) {
4382 const char *path = e->key;
4383 struct conflict_info *ci = e->value;
4384 int pos;
4385 struct cache_entry *ce;
4386 int i;
4388 VERIFY_CI(ci);
4391 * The index will already have a stage=0 entry for this path,
4392 * because we created an as-merged-as-possible version of the
4393 * file and checkout() moved the working copy and index over
4394 * to that version.
4396 * However, previous iterations through this loop will have
4397 * added unstaged entries to the end of the cache which
4398 * ignore the standard alphabetical ordering of cache
4399 * entries and break invariants needed for index_name_pos()
4400 * to work. However, we know the entry we want is before
4401 * those appended cache entries, so do a temporary swap on
4402 * cache_nr to only look through entries of interest.
4404 SWAP(index->cache_nr, original_cache_nr);
4405 pos = index_name_pos(index, path, strlen(path));
4406 SWAP(index->cache_nr, original_cache_nr);
4407 if (pos < 0) {
4408 if (ci->filemask != 1)
4409 BUG("Conflicted %s but nothing in basic working tree or index; this shouldn't happen", path);
4410 cache_tree_invalidate_path(index, path);
4411 } else {
4412 ce = index->cache[pos];
4415 * Clean paths with CE_SKIP_WORKTREE set will not be
4416 * written to the working tree by the unpack_trees()
4417 * call in checkout(). Our conflicted entries would
4418 * have appeared clean to that code since we ignored
4419 * the higher order stages. Thus, we need override
4420 * the CE_SKIP_WORKTREE bit and manually write those
4421 * files to the working disk here.
4423 if (ce_skip_worktree(ce))
4424 errs |= checkout_entry(ce, &state, NULL, NULL);
4427 * Mark this cache entry for removal and instead add
4428 * new stage>0 entries corresponding to the
4429 * conflicts. If there are many conflicted entries, we
4430 * want to avoid memmove'ing O(NM) entries by
4431 * inserting the new entries one at a time. So,
4432 * instead, we just add the new cache entries to the
4433 * end (ignoring normal index requirements on sort
4434 * order) and sort the index once we're all done.
4436 ce->ce_flags |= CE_REMOVE;
4439 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
4440 struct version_info *vi;
4441 if (!(ci->filemask & (1ul << i)))
4442 continue;
4443 vi = &ci->stages[i];
4444 ce = make_cache_entry(index, vi->mode, &vi->oid,
4445 path, i+1, 0);
4446 add_index_entry(index, ce, ADD_CACHE_JUST_APPEND);
4451 * Remove the unused cache entries (and invalidate the relevant
4452 * cache-trees), then sort the index entries to get the conflicted
4453 * entries we added to the end into their right locations.
4455 remove_marked_cache_entries(index, 1);
4457 * No need for STABLE_QSORT -- cmp_cache_name_compare sorts primarily
4458 * on filename and secondarily on stage, and (name, stage #) are a
4459 * unique tuple.
4461 QSORT(index->cache, index->cache_nr, cmp_cache_name_compare);
4463 return errs;
4466 static void print_submodule_conflict_suggestion(struct string_list *csub) {
4467 struct string_list_item *item;
4468 struct strbuf msg = STRBUF_INIT;
4469 struct strbuf tmp = STRBUF_INIT;
4470 struct strbuf subs = STRBUF_INIT;
4472 if (!csub->nr)
4473 return;
4475 strbuf_add_separated_string_list(&subs, " ", csub);
4476 for_each_string_list_item(item, csub) {
4477 struct conflicted_submodule_item *util = item->util;
4480 * NEEDSWORK: The steps to resolve these errors deserve a more
4481 * detailed explanation than what is currently printed below.
4483 if (util->flag == CONFLICT_SUBMODULE_NOT_INITIALIZED ||
4484 util->flag == CONFLICT_SUBMODULE_HISTORY_NOT_AVAILABLE)
4485 continue;
4488 * TRANSLATORS: This is a line of advice to resolve a merge
4489 * conflict in a submodule. The first argument is the submodule
4490 * name, and the second argument is the abbreviated id of the
4491 * commit that needs to be merged. For example:
4492 * - go to submodule (mysubmodule), and either merge commit abc1234"
4494 strbuf_addf(&tmp, _(" - go to submodule (%s), and either merge commit %s\n"
4495 " or update to an existing commit which has merged those changes\n"),
4496 item->string, util->abbrev);
4500 * TRANSLATORS: This is a detailed message for resolving submodule
4501 * conflicts. The first argument is string containing one step per
4502 * submodule. The second is a space-separated list of submodule names.
4504 strbuf_addf(&msg,
4505 _("Recursive merging with submodules currently only supports trivial cases.\n"
4506 "Please manually handle the merging of each conflicted submodule.\n"
4507 "This can be accomplished with the following steps:\n"
4508 "%s"
4509 " - come back to superproject and run:\n\n"
4510 " git add %s\n\n"
4511 " to record the above merge or update\n"
4512 " - resolve any other conflicts in the superproject\n"
4513 " - commit the resulting index in the superproject\n"),
4514 tmp.buf, subs.buf);
4516 printf("%s", msg.buf);
4518 strbuf_release(&subs);
4519 strbuf_release(&tmp);
4520 strbuf_release(&msg);
4523 void merge_display_update_messages(struct merge_options *opt,
4524 int detailed,
4525 struct merge_result *result)
4527 struct merge_options_internal *opti = result->priv;
4528 struct hashmap_iter iter;
4529 struct strmap_entry *e;
4530 struct string_list olist = STRING_LIST_INIT_NODUP;
4532 if (opt->record_conflict_msgs_as_headers)
4533 BUG("Either display conflict messages or record them as headers, not both");
4535 trace2_region_enter("merge", "display messages", opt->repo);
4537 /* Hack to pre-allocate olist to the desired size */
4538 ALLOC_GROW(olist.items, strmap_get_size(&opti->conflicts),
4539 olist.alloc);
4541 /* Put every entry from output into olist, then sort */
4542 strmap_for_each_entry(&opti->conflicts, &iter, e) {
4543 string_list_append(&olist, e->key)->util = e->value;
4545 string_list_sort(&olist);
4547 /* Iterate over the items, printing them */
4548 for (int path_nr = 0; path_nr < olist.nr; ++path_nr) {
4549 struct string_list *conflicts = olist.items[path_nr].util;
4550 for (int i = 0; i < conflicts->nr; i++) {
4551 struct logical_conflict_info *info =
4552 conflicts->items[i].util;
4554 if (detailed) {
4555 printf("%lu", (unsigned long)info->paths.nr);
4556 putchar('\0');
4557 for (int n = 0; n < info->paths.nr; n++) {
4558 fputs(info->paths.v[n], stdout);
4559 putchar('\0');
4561 fputs(type_short_descriptions[info->type],
4562 stdout);
4563 putchar('\0');
4565 puts(conflicts->items[i].string);
4566 if (detailed)
4567 putchar('\0');
4570 string_list_clear(&olist, 0);
4572 print_submodule_conflict_suggestion(&opti->conflicted_submodules);
4574 /* Also include needed rename limit adjustment now */
4575 diff_warn_rename_limit("merge.renamelimit",
4576 opti->renames.needed_limit, 0);
4578 trace2_region_leave("merge", "display messages", opt->repo);
4581 void merge_get_conflicted_files(struct merge_result *result,
4582 struct string_list *conflicted_files)
4584 struct hashmap_iter iter;
4585 struct strmap_entry *e;
4586 struct merge_options_internal *opti = result->priv;
4588 strmap_for_each_entry(&opti->conflicted, &iter, e) {
4589 const char *path = e->key;
4590 struct conflict_info *ci = e->value;
4591 int i;
4593 VERIFY_CI(ci);
4595 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
4596 struct stage_info *si;
4598 if (!(ci->filemask & (1ul << i)))
4599 continue;
4601 si = xmalloc(sizeof(*si));
4602 si->stage = i+1;
4603 si->mode = ci->stages[i].mode;
4604 oidcpy(&si->oid, &ci->stages[i].oid);
4605 string_list_append(conflicted_files, path)->util = si;
4608 /* string_list_sort() uses a stable sort, so we're good */
4609 string_list_sort(conflicted_files);
4612 void merge_switch_to_result(struct merge_options *opt,
4613 struct tree *head,
4614 struct merge_result *result,
4615 int update_worktree_and_index,
4616 int display_update_msgs)
4618 assert(opt->priv == NULL);
4619 if (result->clean >= 0 && update_worktree_and_index) {
4620 const char *filename;
4621 FILE *fp;
4623 trace2_region_enter("merge", "checkout", opt->repo);
4624 if (checkout(opt, head, result->tree)) {
4625 /* failure to function */
4626 result->clean = -1;
4627 merge_finalize(opt, result);
4628 trace2_region_leave("merge", "checkout", opt->repo);
4629 return;
4631 trace2_region_leave("merge", "checkout", opt->repo);
4633 trace2_region_enter("merge", "record_conflicted", opt->repo);
4634 opt->priv = result->priv;
4635 if (record_conflicted_index_entries(opt)) {
4636 /* failure to function */
4637 opt->priv = NULL;
4638 result->clean = -1;
4639 merge_finalize(opt, result);
4640 trace2_region_leave("merge", "record_conflicted",
4641 opt->repo);
4642 return;
4644 opt->priv = NULL;
4645 trace2_region_leave("merge", "record_conflicted", opt->repo);
4647 trace2_region_enter("merge", "write_auto_merge", opt->repo);
4648 filename = git_path_auto_merge(opt->repo);
4649 fp = xfopen(filename, "w");
4650 fprintf(fp, "%s\n", oid_to_hex(&result->tree->object.oid));
4651 fclose(fp);
4652 trace2_region_leave("merge", "write_auto_merge", opt->repo);
4654 if (display_update_msgs)
4655 merge_display_update_messages(opt, /* detailed */ 0, result);
4657 merge_finalize(opt, result);
4660 void merge_finalize(struct merge_options *opt,
4661 struct merge_result *result)
4663 struct merge_options_internal *opti = result->priv;
4665 if (opt->renormalize)
4666 git_attr_set_direction(GIT_ATTR_CHECKIN);
4667 assert(opt->priv == NULL);
4669 clear_or_reinit_internal_opts(opti, 0);
4670 FREE_AND_NULL(opti);
4673 /*** Function Grouping: helper functions for merge_incore_*() ***/
4675 static struct tree *shift_tree_object(struct repository *repo,
4676 struct tree *one, struct tree *two,
4677 const char *subtree_shift)
4679 struct object_id shifted;
4681 if (!*subtree_shift) {
4682 shift_tree(repo, &one->object.oid, &two->object.oid, &shifted, 0);
4683 } else {
4684 shift_tree_by(repo, &one->object.oid, &two->object.oid, &shifted,
4685 subtree_shift);
4687 if (oideq(&two->object.oid, &shifted))
4688 return two;
4689 return lookup_tree(repo, &shifted);
4692 static inline void set_commit_tree(struct commit *c, struct tree *t)
4694 c->maybe_tree = t;
4697 static struct commit *make_virtual_commit(struct repository *repo,
4698 struct tree *tree,
4699 const char *comment)
4701 struct commit *commit = alloc_commit_node(repo);
4703 set_merge_remote_desc(commit, comment, (struct object *)commit);
4704 set_commit_tree(commit, tree);
4705 commit->object.parsed = 1;
4706 return commit;
4709 static void merge_start(struct merge_options *opt, struct merge_result *result)
4711 struct rename_info *renames;
4712 int i;
4713 struct mem_pool *pool = NULL;
4715 /* Sanity checks on opt */
4716 trace2_region_enter("merge", "sanity checks", opt->repo);
4717 assert(opt->repo);
4719 assert(opt->branch1 && opt->branch2);
4721 assert(opt->detect_directory_renames >= MERGE_DIRECTORY_RENAMES_NONE &&
4722 opt->detect_directory_renames <= MERGE_DIRECTORY_RENAMES_TRUE);
4723 assert(opt->rename_limit >= -1);
4724 assert(opt->rename_score >= 0 && opt->rename_score <= MAX_SCORE);
4725 assert(opt->show_rename_progress >= 0 && opt->show_rename_progress <= 1);
4727 assert(opt->xdl_opts >= 0);
4728 assert(opt->recursive_variant >= MERGE_VARIANT_NORMAL &&
4729 opt->recursive_variant <= MERGE_VARIANT_THEIRS);
4731 if (opt->msg_header_prefix)
4732 assert(opt->record_conflict_msgs_as_headers);
4735 * detect_renames, verbosity, buffer_output, and obuf are ignored
4736 * fields that were used by "recursive" rather than "ort" -- but
4737 * sanity check them anyway.
4739 assert(opt->detect_renames >= -1 &&
4740 opt->detect_renames <= DIFF_DETECT_COPY);
4741 assert(opt->verbosity >= 0 && opt->verbosity <= 5);
4742 assert(opt->buffer_output <= 2);
4743 assert(opt->obuf.len == 0);
4745 assert(opt->priv == NULL);
4746 if (result->_properly_initialized != 0 &&
4747 result->_properly_initialized != RESULT_INITIALIZED)
4748 BUG("struct merge_result passed to merge_incore_*recursive() must be zeroed or filled with values from a previous run");
4749 assert(!!result->priv == !!result->_properly_initialized);
4750 if (result->priv) {
4751 opt->priv = result->priv;
4752 result->priv = NULL;
4754 * opt->priv non-NULL means we had results from a previous
4755 * run; do a few sanity checks that user didn't mess with
4756 * it in an obvious fashion.
4758 assert(opt->priv->call_depth == 0);
4759 assert(!opt->priv->toplevel_dir ||
4760 0 == strlen(opt->priv->toplevel_dir));
4762 trace2_region_leave("merge", "sanity checks", opt->repo);
4764 /* Default to histogram diff. Actually, just hardcode it...for now. */
4765 opt->xdl_opts = DIFF_WITH_ALG(opt, HISTOGRAM_DIFF);
4767 /* Handle attr direction stuff for renormalization */
4768 if (opt->renormalize)
4769 git_attr_set_direction(GIT_ATTR_CHECKOUT);
4771 /* Initialization of opt->priv, our internal merge data */
4772 trace2_region_enter("merge", "allocate/init", opt->repo);
4773 if (opt->priv) {
4774 clear_or_reinit_internal_opts(opt->priv, 1);
4775 string_list_init_nodup(&opt->priv->conflicted_submodules);
4776 trace2_region_leave("merge", "allocate/init", opt->repo);
4777 return;
4779 opt->priv = xcalloc(1, sizeof(*opt->priv));
4781 /* Initialization of various renames fields */
4782 renames = &opt->priv->renames;
4783 mem_pool_init(&opt->priv->pool, 0);
4784 pool = &opt->priv->pool;
4785 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {
4786 strintmap_init_with_options(&renames->dirs_removed[i],
4787 NOT_RELEVANT, pool, 0);
4788 strmap_init_with_options(&renames->dir_rename_count[i],
4789 NULL, 1);
4790 strmap_init_with_options(&renames->dir_renames[i],
4791 NULL, 0);
4793 * relevant_sources uses -1 for the default, because we need
4794 * to be able to distinguish not-in-strintmap from valid
4795 * relevant_source values from enum file_rename_relevance.
4796 * In particular, possibly_cache_new_pair() expects a negative
4797 * value for not-found entries.
4799 strintmap_init_with_options(&renames->relevant_sources[i],
4800 -1 /* explicitly invalid */,
4801 pool, 0);
4802 strmap_init_with_options(&renames->cached_pairs[i],
4803 NULL, 1);
4804 strset_init_with_options(&renames->cached_irrelevant[i],
4805 NULL, 1);
4806 strset_init_with_options(&renames->cached_target_names[i],
4807 NULL, 0);
4809 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {
4810 strintmap_init_with_options(&renames->deferred[i].possible_trivial_merges,
4811 0, pool, 0);
4812 strset_init_with_options(&renames->deferred[i].target_dirs,
4813 pool, 1);
4814 renames->deferred[i].trivial_merges_okay = 1; /* 1 == maybe */
4818 * Although we initialize opt->priv->paths with strdup_strings=0,
4819 * that's just to avoid making yet another copy of an allocated
4820 * string. Putting the entry into paths means we are taking
4821 * ownership, so we will later free it.
4823 * In contrast, conflicted just has a subset of keys from paths, so
4824 * we don't want to free those (it'd be a duplicate free).
4826 strmap_init_with_options(&opt->priv->paths, pool, 0);
4827 strmap_init_with_options(&opt->priv->conflicted, pool, 0);
4830 * keys & string_lists in conflicts will sometimes need to outlive
4831 * "paths", so it will have a copy of relevant keys. It's probably
4832 * a small subset of the overall paths that have special output.
4834 strmap_init(&opt->priv->conflicts);
4836 trace2_region_leave("merge", "allocate/init", opt->repo);
4839 static void merge_check_renames_reusable(struct merge_options *opt,
4840 struct merge_result *result,
4841 struct tree *merge_base,
4842 struct tree *side1,
4843 struct tree *side2)
4845 struct rename_info *renames;
4846 struct tree **merge_trees;
4847 struct merge_options_internal *opti = result->priv;
4849 if (!opti)
4850 return;
4852 renames = &opti->renames;
4853 merge_trees = renames->merge_trees;
4856 * Handle case where previous merge operation did not want cache to
4857 * take effect, e.g. because rename/rename(1to1) makes it invalid.
4859 if (!merge_trees[0]) {
4860 assert(!merge_trees[0] && !merge_trees[1] && !merge_trees[2]);
4861 renames->cached_pairs_valid_side = 0; /* neither side valid */
4862 return;
4866 * Handle other cases; note that merge_trees[0..2] will only
4867 * be NULL if opti is, or if all three were manually set to
4868 * NULL by e.g. rename/rename(1to1) handling.
4870 assert(merge_trees[0] && merge_trees[1] && merge_trees[2]);
4872 /* Check if we meet a condition for re-using cached_pairs */
4873 if (oideq(&merge_base->object.oid, &merge_trees[2]->object.oid) &&
4874 oideq(&side1->object.oid, &result->tree->object.oid))
4875 renames->cached_pairs_valid_side = MERGE_SIDE1;
4876 else if (oideq(&merge_base->object.oid, &merge_trees[1]->object.oid) &&
4877 oideq(&side2->object.oid, &result->tree->object.oid))
4878 renames->cached_pairs_valid_side = MERGE_SIDE2;
4879 else
4880 renames->cached_pairs_valid_side = 0; /* neither side valid */
4883 /*** Function Grouping: merge_incore_*() and their internal variants ***/
4886 * Originally from merge_trees_internal(); heavily adapted, though.
4888 static void merge_ort_nonrecursive_internal(struct merge_options *opt,
4889 struct tree *merge_base,
4890 struct tree *side1,
4891 struct tree *side2,
4892 struct merge_result *result)
4894 struct object_id working_tree_oid;
4896 if (opt->subtree_shift) {
4897 side2 = shift_tree_object(opt->repo, side1, side2,
4898 opt->subtree_shift);
4899 merge_base = shift_tree_object(opt->repo, side1, merge_base,
4900 opt->subtree_shift);
4903 redo:
4904 trace2_region_enter("merge", "collect_merge_info", opt->repo);
4905 if (collect_merge_info(opt, merge_base, side1, side2) != 0) {
4907 * TRANSLATORS: The %s arguments are: 1) tree hash of a merge
4908 * base, and 2-3) the trees for the two trees we're merging.
4910 err(opt, _("collecting merge info failed for trees %s, %s, %s"),
4911 oid_to_hex(&merge_base->object.oid),
4912 oid_to_hex(&side1->object.oid),
4913 oid_to_hex(&side2->object.oid));
4914 result->clean = -1;
4915 return;
4917 trace2_region_leave("merge", "collect_merge_info", opt->repo);
4919 trace2_region_enter("merge", "renames", opt->repo);
4920 result->clean = detect_and_process_renames(opt, merge_base,
4921 side1, side2);
4922 trace2_region_leave("merge", "renames", opt->repo);
4923 if (opt->priv->renames.redo_after_renames == 2) {
4924 trace2_region_enter("merge", "reset_maps", opt->repo);
4925 clear_or_reinit_internal_opts(opt->priv, 1);
4926 trace2_region_leave("merge", "reset_maps", opt->repo);
4927 goto redo;
4930 trace2_region_enter("merge", "process_entries", opt->repo);
4931 process_entries(opt, &working_tree_oid);
4932 trace2_region_leave("merge", "process_entries", opt->repo);
4934 /* Set return values */
4935 result->path_messages = &opt->priv->conflicts;
4937 result->tree = parse_tree_indirect(&working_tree_oid);
4938 /* existence of conflicted entries implies unclean */
4939 result->clean &= strmap_empty(&opt->priv->conflicted);
4940 if (!opt->priv->call_depth) {
4941 result->priv = opt->priv;
4942 result->_properly_initialized = RESULT_INITIALIZED;
4943 opt->priv = NULL;
4948 * Originally from merge_recursive_internal(); somewhat adapted, though.
4950 static void merge_ort_internal(struct merge_options *opt,
4951 struct commit_list *merge_bases,
4952 struct commit *h1,
4953 struct commit *h2,
4954 struct merge_result *result)
4956 struct commit *next;
4957 struct commit *merged_merge_bases;
4958 const char *ancestor_name;
4959 struct strbuf merge_base_abbrev = STRBUF_INIT;
4961 if (!merge_bases) {
4962 merge_bases = get_merge_bases(h1, h2);
4963 /* See merge-ort.h:merge_incore_recursive() declaration NOTE */
4964 merge_bases = reverse_commit_list(merge_bases);
4967 merged_merge_bases = pop_commit(&merge_bases);
4968 if (!merged_merge_bases) {
4969 /* if there is no common ancestor, use an empty tree */
4970 struct tree *tree;
4972 tree = lookup_tree(opt->repo, opt->repo->hash_algo->empty_tree);
4973 merged_merge_bases = make_virtual_commit(opt->repo, tree,
4974 "ancestor");
4975 ancestor_name = "empty tree";
4976 } else if (merge_bases) {
4977 ancestor_name = "merged common ancestors";
4978 } else {
4979 strbuf_add_unique_abbrev(&merge_base_abbrev,
4980 &merged_merge_bases->object.oid,
4981 DEFAULT_ABBREV);
4982 ancestor_name = merge_base_abbrev.buf;
4985 for (next = pop_commit(&merge_bases); next;
4986 next = pop_commit(&merge_bases)) {
4987 const char *saved_b1, *saved_b2;
4988 struct commit *prev = merged_merge_bases;
4990 opt->priv->call_depth++;
4992 * When the merge fails, the result contains files
4993 * with conflict markers. The cleanness flag is
4994 * ignored (unless indicating an error), it was never
4995 * actually used, as result of merge_trees has always
4996 * overwritten it: the committed "conflicts" were
4997 * already resolved.
4999 saved_b1 = opt->branch1;
5000 saved_b2 = opt->branch2;
5001 opt->branch1 = "Temporary merge branch 1";
5002 opt->branch2 = "Temporary merge branch 2";
5003 merge_ort_internal(opt, NULL, prev, next, result);
5004 if (result->clean < 0)
5005 return;
5006 opt->branch1 = saved_b1;
5007 opt->branch2 = saved_b2;
5008 opt->priv->call_depth--;
5010 merged_merge_bases = make_virtual_commit(opt->repo,
5011 result->tree,
5012 "merged tree");
5013 commit_list_insert(prev, &merged_merge_bases->parents);
5014 commit_list_insert(next, &merged_merge_bases->parents->next);
5016 clear_or_reinit_internal_opts(opt->priv, 1);
5019 opt->ancestor = ancestor_name;
5020 merge_ort_nonrecursive_internal(opt,
5021 repo_get_commit_tree(opt->repo,
5022 merged_merge_bases),
5023 repo_get_commit_tree(opt->repo, h1),
5024 repo_get_commit_tree(opt->repo, h2),
5025 result);
5026 strbuf_release(&merge_base_abbrev);
5027 opt->ancestor = NULL; /* avoid accidental re-use of opt->ancestor */
5030 void merge_incore_nonrecursive(struct merge_options *opt,
5031 struct tree *merge_base,
5032 struct tree *side1,
5033 struct tree *side2,
5034 struct merge_result *result)
5036 trace2_region_enter("merge", "incore_nonrecursive", opt->repo);
5038 trace2_region_enter("merge", "merge_start", opt->repo);
5039 assert(opt->ancestor != NULL);
5040 merge_check_renames_reusable(opt, result, merge_base, side1, side2);
5041 merge_start(opt, result);
5043 * Record the trees used in this merge, so if there's a next merge in
5044 * a cherry-pick or rebase sequence it might be able to take advantage
5045 * of the cached_pairs in that next merge.
5047 opt->priv->renames.merge_trees[0] = merge_base;
5048 opt->priv->renames.merge_trees[1] = side1;
5049 opt->priv->renames.merge_trees[2] = side2;
5050 trace2_region_leave("merge", "merge_start", opt->repo);
5052 merge_ort_nonrecursive_internal(opt, merge_base, side1, side2, result);
5053 trace2_region_leave("merge", "incore_nonrecursive", opt->repo);
5056 void merge_incore_recursive(struct merge_options *opt,
5057 struct commit_list *merge_bases,
5058 struct commit *side1,
5059 struct commit *side2,
5060 struct merge_result *result)
5062 trace2_region_enter("merge", "incore_recursive", opt->repo);
5064 /* We set the ancestor label based on the merge_bases */
5065 assert(opt->ancestor == NULL);
5067 trace2_region_enter("merge", "merge_start", opt->repo);
5068 merge_start(opt, result);
5069 trace2_region_leave("merge", "merge_start", opt->repo);
5071 merge_ort_internal(opt, merge_bases, side1, side2, result);
5072 trace2_region_leave("merge", "incore_recursive", opt->repo);