2 * "Ostensibly Recursive's Twin" merge strategy, or "ort" for short. Meant
3 * as a drop-in replacement for the "recursive" merge strategy, allowing one
6 * git merge [-s recursive]
12 * Note: git's parser allows the space between '-s' and its argument to be
13 * missing. (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo",
14 * "cale", "peedy", or "ins" instead of "ort"?)
17 #include "git-compat-util.h"
18 #include "merge-ort.h"
22 #include "cache-tree.h"
24 #include "commit-reach.h"
28 #include "environment.h"
33 #include "match-trees.h"
35 #include "object-name.h"
36 #include "object-store-ll.h"
37 #include "oid-array.h"
39 #include "promisor-remote.h"
40 #include "read-cache-ll.h"
43 #include "sparse-index.h"
47 #include "unpack-trees.h"
48 #include "xdiff-interface.h"
51 * We have many arrays of size 3. Whenever we have such an array, the
52 * indices refer to one of the sides of the three-way merge. This is so
53 * pervasive that the constants 0, 1, and 2 are used in many places in the
54 * code (especially in arithmetic operations to find the other side's index
55 * or to compute a relevant mask), but sometimes these enum names are used
56 * to aid code clarity.
58 * See also 'filemask' and 'dirmask' in struct conflict_info; the "ith side"
59 * referred to there is one of these three sides.
67 static unsigned RESULT_INITIALIZED
= 0x1abe11ed; /* unlikely accidental value */
69 struct traversal_callback_data
{
71 unsigned long dirmask
;
72 struct name_entry names
[3];
75 struct deferred_traversal_data
{
77 * possible_trivial_merges: directories to be explored only when needed
79 * possible_trivial_merges is a map of directory names to
80 * dir_rename_mask. When we detect that a directory is unchanged on
81 * one side, we can sometimes resolve the directory without recursing
82 * into it. Renames are the only things that can prevent such an
83 * optimization. However, for rename sources:
84 * - If no parent directory needed directory rename detection, then
85 * no path under such a directory can be a relevant_source.
86 * and for rename destinations:
87 * - If no cached rename has a target path under the directory AND
88 * - If there are no unpaired relevant_sources elsewhere in the
90 * then we don't need any path under this directory for a rename
91 * destination. The only way to know the last item above is to defer
92 * handling such directories until the end of collect_merge_info(),
93 * in handle_deferred_entries().
95 * For each we store dir_rename_mask, since that's the only bit of
96 * information we need, other than the path, to resume the recursive
99 struct strintmap possible_trivial_merges
;
102 * trivial_merges_okay: if trivial directory merges are okay
104 * See possible_trivial_merges above. The "no unpaired
105 * relevant_sources elsewhere in the repository" is a single boolean
106 * per merge side, which we store here. Note that while 0 means no,
107 * 1 only means "maybe" rather than "yes"; we optimistically set it
108 * to 1 initially and only clear when we determine it is unsafe to
109 * do trivial directory merges.
111 unsigned trivial_merges_okay
;
114 * target_dirs: ancestor directories of rename targets
116 * target_dirs contains all directory names that are an ancestor of
117 * any rename destination.
119 struct strset target_dirs
;
124 * All variables that are arrays of size 3 correspond to data tracked
125 * for the sides in enum merge_side. Index 0 is almost always unused
126 * because we often only need to track information for MERGE_SIDE1 and
127 * MERGE_SIDE2 (MERGE_BASE can't have rename information since renames
128 * are determined relative to what changed since the MERGE_BASE).
132 * pairs: pairing of filenames from diffcore_rename()
134 struct diff_queue_struct pairs
[3];
137 * dirs_removed: directories removed on a given side of history.
139 * The keys of dirs_removed[side] are the directories that were removed
140 * on the given side of history. The value of the strintmap for each
141 * directory is a value from enum dir_rename_relevance.
143 struct strintmap dirs_removed
[3];
146 * dir_rename_count: tracking where parts of a directory were renamed to
148 * When files in a directory are renamed, they may not all go to the
149 * same location. Each strmap here tracks:
150 * old_dir => {new_dir => int}
151 * That is, dir_rename_count[side] is a strmap to a strintmap.
153 struct strmap dir_rename_count
[3];
156 * dir_renames: computed directory renames
158 * This is a map of old_dir => new_dir and is derived in part from
161 struct strmap dir_renames
[3];
164 * relevant_sources: deleted paths wanted in rename detection, and why
166 * relevant_sources is a set of deleted paths on each side of
167 * history for which we need rename detection. If a path is deleted
168 * on one side of history, we need to detect if it is part of a
170 * * the file is modified/deleted on the other side of history
171 * * we need to detect renames for an ancestor directory
172 * If neither of those are true, we can skip rename detection for
173 * that path. The reason is stored as a value from enum
174 * file_rename_relevance, as the reason can inform the algorithm in
175 * diffcore_rename_extended().
177 struct strintmap relevant_sources
[3];
179 struct deferred_traversal_data deferred
[3];
183 * 0: optimization removing unmodified potential rename source okay
184 * 2 or 4: optimization okay, but must check for files added to dir
185 * 7: optimization forbidden; need rename source in case of dir rename
187 unsigned dir_rename_mask
:3;
190 * callback_data_*: supporting data structures for alternate traversal
192 * We sometimes need to be able to traverse through all the files
193 * in a given tree before all immediate subdirectories within that
194 * tree. Since traverse_trees() doesn't do that naturally, we have
195 * a traverse_trees_wrapper() that stores any immediate
196 * subdirectories while traversing files, then traverses the
197 * immediate subdirectories later. These callback_data* variables
198 * store the information for the subdirectories so that we can do
199 * that traversal order.
201 struct traversal_callback_data
*callback_data
;
202 int callback_data_nr
, callback_data_alloc
;
203 char *callback_data_traverse_path
;
206 * merge_trees: trees passed to the merge algorithm for the merge
208 * merge_trees records the trees passed to the merge algorithm. But,
209 * this data also is stored in merge_result->priv. If a sequence of
210 * merges are being done (such as when cherry-picking or rebasing),
211 * the next merge can look at this and re-use information from
212 * previous merges under certain circumstances.
214 * See also all the cached_* variables.
216 struct tree
*merge_trees
[3];
219 * cached_pairs_valid_side: which side's cached info can be reused
221 * See the description for merge_trees. For repeated merges, at most
222 * only one side's cached information can be used. Valid values:
223 * MERGE_SIDE2: cached data from side2 can be reused
224 * MERGE_SIDE1: cached data from side1 can be reused
225 * 0: no cached data can be reused
226 * -1: See redo_after_renames; both sides can be reused.
228 int cached_pairs_valid_side
;
231 * cached_pairs: Caching of renames and deletions.
233 * These are mappings recording renames and deletions of individual
234 * files (not directories). They are thus a map from an old
235 * filename to either NULL (for deletions) or a new filename (for
238 struct strmap cached_pairs
[3];
241 * cached_target_names: just the destinations from cached_pairs
243 * We sometimes want a fast lookup to determine if a given filename
244 * is one of the destinations in cached_pairs. cached_target_names
245 * is thus duplicative information, but it provides a fast lookup.
247 struct strset cached_target_names
[3];
250 * cached_irrelevant: Caching of rename_sources that aren't relevant.
252 * If we try to detect a rename for a source path and succeed, it's
253 * part of a rename. If we try to detect a rename for a source path
254 * and fail, then it's a delete. If we do not try to detect a rename
255 * for a path, then we don't know if it's a rename or a delete. If
256 * merge-ort doesn't think the path is relevant, then we just won't
257 * cache anything for that path. But there's a slight problem in
258 * that merge-ort can think a path is RELEVANT_LOCATION, but due to
259 * commit 9bd342137e ("diffcore-rename: determine which
260 * relevant_sources are no longer relevant", 2021-03-13),
261 * diffcore-rename can downgrade the path to RELEVANT_NO_MORE. To
262 * avoid excessive calls to diffcore_rename_extended() we still need
263 * to cache such paths, though we cannot record them as either
264 * renames or deletes. So we cache them here as a "turned out to be
265 * irrelevant *for this commit*" as they are often also irrelevant
266 * for subsequent commits, though we will have to do some extra
267 * checking to see whether such paths become relevant for rename
268 * detection when cherry-picking/rebasing subsequent commits.
270 struct strset cached_irrelevant
[3];
273 * redo_after_renames: optimization flag for "restarting" the merge
275 * Sometimes it pays to detect renames, cache them, and then
276 * restart the merge operation from the beginning. The reason for
277 * this is that when we know where all the renames are, we know
278 * whether a certain directory has any paths under it affected --
279 * and if a directory is not affected then it permits us to do
280 * trivial tree merging in more cases. Doing trivial tree merging
281 * prevents the need to run process_entry() on every path
282 * underneath trees that can be trivially merged, and
283 * process_entry() is more expensive than collect_merge_info() --
284 * plus, the second collect_merge_info() will be much faster since
285 * it doesn't have to recurse into the relevant trees.
287 * Values for this flag:
288 * 0 = don't bother, not worth it (or conditions not yet checked)
289 * 1 = conditions for optimization met, optimization worthwhile
290 * 2 = we already did it (don't restart merge yet again)
292 unsigned redo_after_renames
;
295 * needed_limit: value needed for inexact rename detection to run
297 * If the current rename limit wasn't high enough for inexact
298 * rename detection to run, this records the limit needed. Otherwise,
299 * this value remains 0.
304 struct merge_options_internal
{
306 * paths: primary data structure in all of merge ort.
309 * * are full relative paths from the toplevel of the repository
310 * (e.g. "drivers/firmware/raspberrypi.c").
311 * * store all relevant paths in the repo, both directories and
312 * files (e.g. drivers, drivers/firmware would also be included)
313 * * these keys serve to intern all the path strings, which allows
314 * us to do pointer comparison on directory names instead of
315 * strcmp; we just have to be careful to use the interned strings.
317 * The values of paths:
318 * * either a pointer to a merged_info, or a conflict_info struct
319 * * merged_info contains all relevant information for a
320 * non-conflicted entry.
321 * * conflict_info contains a merged_info, plus any additional
322 * information about a conflict such as the higher orders stages
323 * involved and the names of the paths those came from (handy
324 * once renames get involved).
325 * * a path may start "conflicted" (i.e. point to a conflict_info)
326 * and then a later step (e.g. three-way content merge) determines
327 * it can be cleanly merged, at which point it'll be marked clean
328 * and the algorithm will ignore any data outside the contained
329 * merged_info for that entry
330 * * If an entry remains conflicted, the merged_info portion of a
331 * conflict_info will later be filled with whatever version of
332 * the file should be placed in the working directory (e.g. an
333 * as-merged-as-possible variation that contains conflict markers).
338 * conflicted: a subset of keys->values from "paths"
340 * conflicted is basically an optimization between process_entries()
341 * and record_conflicted_index_entries(); the latter could loop over
342 * ALL the entries in paths AGAIN and look for the ones that are
343 * still conflicted, but since process_entries() has to loop over
344 * all of them, it saves the ones it couldn't resolve in this strmap
345 * so that record_conflicted_index_entries() can iterate just the
348 struct strmap conflicted
;
351 * pool: memory pool for fast allocation/deallocation
353 * We allocate room for lots of filenames and auxiliary data
354 * structures in merge_options_internal, and it tends to all be
355 * freed together too. Using a memory pool for these provides a
358 struct mem_pool pool
;
361 * conflicts: logical conflicts and messages stored by _primary_ path
363 * This is a map of pathnames (a subset of the keys in "paths" above)
364 * to struct string_list, with each item's `util` containing a
365 * `struct logical_conflict_info`. Note, though, that for each path,
366 * it only stores the logical conflicts for which that path is the
367 * primary path; the path might be part of additional conflicts.
369 struct strmap conflicts
;
372 * renames: various data relating to rename detection
374 struct rename_info renames
;
377 * attr_index: hacky minimal index used for renormalization
379 * renormalization code _requires_ an index, though it only needs to
380 * find a .gitattributes file within the index. So, when
381 * renormalization is important, we create a special index with just
384 struct index_state attr_index
;
387 * current_dir_name, toplevel_dir: temporary vars
389 * These are used in collect_merge_info_callback(), and will set the
390 * various merged_info.directory_name for the various paths we get;
391 * see documentation for that variable and the requirements placed on
394 const char *current_dir_name
;
395 const char *toplevel_dir
;
397 /* call_depth: recursion level counter for merging merge bases */
400 /* field that holds submodule conflict information */
401 struct string_list conflicted_submodules
;
404 struct conflicted_submodule_item
{
409 static void conflicted_submodule_item_free(void *util
, const char *str UNUSED
)
411 struct conflicted_submodule_item
*item
= util
;
417 struct version_info
{
418 struct object_id oid
;
423 /* if is_null, ignore result. otherwise result has oid & mode */
424 struct version_info result
;
428 * clean: whether the path in question is cleanly merged.
430 * see conflict_info.merged for more details.
435 * basename_offset: offset of basename of path.
437 * perf optimization to avoid recomputing offset of final '/'
438 * character in pathname (0 if no '/' in pathname).
440 size_t basename_offset
;
443 * directory_name: containing directory name.
445 * Note that we assume directory_name is constructed such that
446 * strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name,
447 * i.e. string equality is equivalent to pointer equality. For this
448 * to hold, we have to be careful setting directory_name.
450 const char *directory_name
;
453 struct conflict_info
{
455 * merged: the version of the path that will be written to working tree
457 * WARNING: It is critical to check merged.clean and ensure it is 0
458 * before reading any conflict_info fields outside of merged.
459 * Allocated merge_info structs will always have clean set to 1.
460 * Allocated conflict_info structs will have merged.clean set to 0
461 * initially. The merged.clean field is how we know if it is safe
462 * to access other parts of conflict_info besides merged; if a
463 * conflict_info's merged.clean is changed to 1, the rest of the
464 * algorithm is not allowed to look at anything outside of the
465 * merged member anymore.
467 struct merged_info merged
;
469 /* oids & modes from each of the three trees for this path */
470 struct version_info stages
[3];
472 /* pathnames for each stage; may differ due to rename detection */
473 const char *pathnames
[3];
475 /* Whether this path is/was involved in a directory/file conflict */
476 unsigned df_conflict
:1;
479 * Whether this path is/was involved in a non-content conflict other
480 * than a directory/file conflict (e.g. rename/rename, rename/delete,
481 * file location based on possible directory rename).
483 unsigned path_conflict
:1;
486 * For filemask and dirmask, the ith bit corresponds to whether the
487 * ith entry is a file (filemask) or a directory (dirmask). Thus,
488 * filemask & dirmask is always zero, and filemask | dirmask is at
489 * most 7 but can be less when a path does not appear as either a
490 * file or a directory on at least one side of history.
492 * Note that these masks are related to enum merge_side, as the ith
493 * entry corresponds to side i.
495 * These values come from a traverse_trees() call; more info may be
496 * found looking at tree-walk.h's struct traverse_info,
497 * particularly the documentation above the "fn" member (note that
498 * filemask = mask & ~dirmask from that documentation).
504 * Optimization to track which stages match, to avoid the need to
505 * recompute it in multiple steps. Either 0 or at least 2 bits are
506 * set; if at least 2 bits are set, their corresponding stages match.
508 unsigned match_mask
:3;
511 enum conflict_and_info_types
{
512 /* "Simple" conflicts and informational messages */
513 INFO_AUTO_MERGING
= 0,
514 CONFLICT_CONTENTS
, /* text file that failed to merge */
516 CONFLICT_FILE_DIRECTORY
,
517 CONFLICT_DISTINCT_MODES
,
518 CONFLICT_MODIFY_DELETE
,
521 CONFLICT_RENAME_RENAME
, /* same file renamed differently */
522 CONFLICT_RENAME_COLLIDES
, /* rename/add or two files renamed to 1 */
523 CONFLICT_RENAME_DELETE
,
525 /* Basic directory rename */
526 CONFLICT_DIR_RENAME_SUGGESTED
,
527 INFO_DIR_RENAME_APPLIED
,
529 /* Special directory rename cases */
530 INFO_DIR_RENAME_SKIPPED_DUE_TO_RERENAME
,
531 CONFLICT_DIR_RENAME_FILE_IN_WAY
,
532 CONFLICT_DIR_RENAME_COLLISION
,
533 CONFLICT_DIR_RENAME_SPLIT
,
535 /* Basic submodule */
536 INFO_SUBMODULE_FAST_FORWARDING
,
537 CONFLICT_SUBMODULE_FAILED_TO_MERGE
,
539 /* Special submodule cases broken out from FAILED_TO_MERGE */
540 CONFLICT_SUBMODULE_FAILED_TO_MERGE_BUT_POSSIBLE_RESOLUTION
,
541 CONFLICT_SUBMODULE_NOT_INITIALIZED
,
542 CONFLICT_SUBMODULE_HISTORY_NOT_AVAILABLE
,
543 CONFLICT_SUBMODULE_MAY_HAVE_REWINDS
,
544 CONFLICT_SUBMODULE_NULL_MERGE_BASE
,
545 CONFLICT_SUBMODULE_CORRUPT
,
547 /* Keep this entry _last_ in the list */
552 * Short description of conflict type, relied upon by external tools.
554 * We can add more entries, but DO NOT change any of these strings. Also,
555 * Order MUST match conflict_info_and_types.
557 static const char *type_short_descriptions
[] = {
558 /*** "Simple" conflicts and informational messages ***/
559 [INFO_AUTO_MERGING
] = "Auto-merging",
560 [CONFLICT_CONTENTS
] = "CONFLICT (contents)",
561 [CONFLICT_BINARY
] = "CONFLICT (binary)",
562 [CONFLICT_FILE_DIRECTORY
] = "CONFLICT (file/directory)",
563 [CONFLICT_DISTINCT_MODES
] = "CONFLICT (distinct modes)",
564 [CONFLICT_MODIFY_DELETE
] = "CONFLICT (modify/delete)",
566 /*** Regular rename ***/
567 [CONFLICT_RENAME_RENAME
] = "CONFLICT (rename/rename)",
568 [CONFLICT_RENAME_COLLIDES
] = "CONFLICT (rename involved in collision)",
569 [CONFLICT_RENAME_DELETE
] = "CONFLICT (rename/delete)",
571 /*** Basic directory rename ***/
572 [CONFLICT_DIR_RENAME_SUGGESTED
] =
573 "CONFLICT (directory rename suggested)",
574 [INFO_DIR_RENAME_APPLIED
] = "Path updated due to directory rename",
576 /*** Special directory rename cases ***/
577 [INFO_DIR_RENAME_SKIPPED_DUE_TO_RERENAME
] =
578 "Directory rename skipped since directory was renamed on both sides",
579 [CONFLICT_DIR_RENAME_FILE_IN_WAY
] =
580 "CONFLICT (file in way of directory rename)",
581 [CONFLICT_DIR_RENAME_COLLISION
] = "CONFLICT(directory rename collision)",
582 [CONFLICT_DIR_RENAME_SPLIT
] = "CONFLICT(directory rename unclear split)",
584 /*** Basic submodule ***/
585 [INFO_SUBMODULE_FAST_FORWARDING
] = "Fast forwarding submodule",
586 [CONFLICT_SUBMODULE_FAILED_TO_MERGE
] = "CONFLICT (submodule)",
588 /*** Special submodule cases broken out from FAILED_TO_MERGE ***/
589 [CONFLICT_SUBMODULE_FAILED_TO_MERGE_BUT_POSSIBLE_RESOLUTION
] =
590 "CONFLICT (submodule with possible resolution)",
591 [CONFLICT_SUBMODULE_NOT_INITIALIZED
] =
592 "CONFLICT (submodule not initialized)",
593 [CONFLICT_SUBMODULE_HISTORY_NOT_AVAILABLE
] =
594 "CONFLICT (submodule history not available)",
595 [CONFLICT_SUBMODULE_MAY_HAVE_REWINDS
] =
596 "CONFLICT (submodule may have rewinds)",
597 [CONFLICT_SUBMODULE_NULL_MERGE_BASE
] =
598 "CONFLICT (submodule lacks merge base)",
599 [CONFLICT_SUBMODULE_CORRUPT
] =
600 "CONFLICT (submodule corrupt)"
603 struct logical_conflict_info
{
604 enum conflict_and_info_types type
;
608 /*** Function Grouping: various utility functions ***/
611 * For the next three macros, see warning for conflict_info.merged.
613 * In each of the below, mi is a struct merged_info*, and ci was defined
614 * as a struct conflict_info* (but we need to verify ci isn't actually
615 * pointed at a struct merged_info*).
617 * INITIALIZE_CI: Assign ci to mi but only if it's safe; set to NULL otherwise.
618 * VERIFY_CI: Ensure that something we assigned to a conflict_info* is one.
619 * ASSIGN_AND_VERIFY_CI: Similar to VERIFY_CI but do assignment first.
621 #define INITIALIZE_CI(ci, mi) do { \
622 (ci) = (!(mi) || (mi)->clean) ? NULL : (struct conflict_info *)(mi); \
624 #define VERIFY_CI(ci) assert(ci && !ci->merged.clean);
625 #define ASSIGN_AND_VERIFY_CI(ci, mi) do { \
626 (ci) = (struct conflict_info *)(mi); \
627 assert((ci) && !(mi)->clean); \
630 static void free_strmap_strings(struct strmap
*map
)
632 struct hashmap_iter iter
;
633 struct strmap_entry
*entry
;
635 strmap_for_each_entry(map
, &iter
, entry
) {
636 free((char*)entry
->key
);
640 static void clear_or_reinit_internal_opts(struct merge_options_internal
*opti
,
643 struct rename_info
*renames
= &opti
->renames
;
645 void (*strmap_clear_func
)(struct strmap
*, int) =
646 reinitialize
? strmap_partial_clear
: strmap_clear
;
647 void (*strintmap_clear_func
)(struct strintmap
*) =
648 reinitialize
? strintmap_partial_clear
: strintmap_clear
;
649 void (*strset_clear_func
)(struct strset
*) =
650 reinitialize
? strset_partial_clear
: strset_clear
;
652 strmap_clear_func(&opti
->paths
, 0);
655 * All keys and values in opti->conflicted are a subset of those in
656 * opti->paths. We don't want to deallocate anything twice, so we
657 * don't free the keys and we pass 0 for free_values.
659 strmap_clear_func(&opti
->conflicted
, 0);
661 if (opti
->attr_index
.cache_nr
) /* true iff opt->renormalize */
662 discard_index(&opti
->attr_index
);
664 /* Free memory used by various renames maps */
665 for (i
= MERGE_SIDE1
; i
<= MERGE_SIDE2
; ++i
) {
666 strintmap_clear_func(&renames
->dirs_removed
[i
]);
667 strmap_clear_func(&renames
->dir_renames
[i
], 0);
668 strintmap_clear_func(&renames
->relevant_sources
[i
]);
670 assert(renames
->cached_pairs_valid_side
== 0);
671 if (i
!= renames
->cached_pairs_valid_side
&&
672 -1 != renames
->cached_pairs_valid_side
) {
673 strset_clear_func(&renames
->cached_target_names
[i
]);
674 strmap_clear_func(&renames
->cached_pairs
[i
], 1);
675 strset_clear_func(&renames
->cached_irrelevant
[i
]);
676 partial_clear_dir_rename_count(&renames
->dir_rename_count
[i
]);
678 strmap_clear(&renames
->dir_rename_count
[i
], 1);
681 for (i
= MERGE_SIDE1
; i
<= MERGE_SIDE2
; ++i
) {
682 strintmap_clear_func(&renames
->deferred
[i
].possible_trivial_merges
);
683 strset_clear_func(&renames
->deferred
[i
].target_dirs
);
684 renames
->deferred
[i
].trivial_merges_okay
= 1; /* 1 == maybe */
686 renames
->cached_pairs_valid_side
= 0;
687 renames
->dir_rename_mask
= 0;
690 struct hashmap_iter iter
;
691 struct strmap_entry
*e
;
693 /* Release and free each strbuf found in output */
694 strmap_for_each_entry(&opti
->conflicts
, &iter
, e
) {
695 struct string_list
*list
= e
->value
;
696 for (int i
= 0; i
< list
->nr
; i
++) {
697 struct logical_conflict_info
*info
=
699 strvec_clear(&info
->paths
);
702 * While strictly speaking we don't need to
703 * free(conflicts) here because we could pass
704 * free_values=1 when calling strmap_clear() on
705 * opti->conflicts, that would require strmap_clear
706 * to do another strmap_for_each_entry() loop, so we
707 * just free it while we're iterating anyway.
709 string_list_clear(list
, 1);
712 strmap_clear(&opti
->conflicts
, 0);
715 mem_pool_discard(&opti
->pool
, 0);
717 string_list_clear_func(&opti
->conflicted_submodules
,
718 conflicted_submodule_item_free
);
720 /* Clean out callback_data as well. */
721 FREE_AND_NULL(renames
->callback_data
);
722 renames
->callback_data_nr
= renames
->callback_data_alloc
= 0;
725 static void format_commit(struct strbuf
*sb
,
727 struct repository
*repo
,
728 struct commit
*commit
)
730 struct merge_remote_desc
*desc
;
731 struct pretty_print_context ctx
= {0};
732 ctx
.abbrev
= DEFAULT_ABBREV
;
734 strbuf_addchars(sb
, ' ', indent
);
735 desc
= merge_remote_util(commit
);
737 strbuf_addf(sb
, "virtual %s\n", desc
->name
);
741 repo_format_commit_message(repo
, commit
, "%h %s", sb
, &ctx
);
742 strbuf_addch(sb
, '\n');
745 __attribute__((format (printf
, 8, 9)))
746 static void path_msg(struct merge_options
*opt
,
747 enum conflict_and_info_types type
,
748 int omittable_hint
, /* skippable under --remerge-diff */
749 const char *primary_path
,
750 const char *other_path_1
, /* may be NULL */
751 const char *other_path_2
, /* may be NULL */
752 struct string_list
*other_paths
, /* may be NULL */
753 const char *fmt
, ...)
756 struct string_list
*path_conflicts
;
757 struct logical_conflict_info
*info
;
758 struct strbuf buf
= STRBUF_INIT
;
760 struct strbuf tmp
= STRBUF_INIT
;
763 assert(omittable_hint
==
764 !starts_with(type_short_descriptions
[type
], "CONFLICT") ||
765 type
== CONFLICT_DIR_RENAME_SUGGESTED
);
766 if (opt
->record_conflict_msgs_as_headers
&& omittable_hint
)
767 return; /* Do not record mere hints in headers */
768 if (opt
->priv
->call_depth
&& opt
->verbosity
< 5)
769 return; /* Ignore messages from inner merges */
771 /* Ensure path_conflicts (ptr to array of logical_conflict) allocated */
772 path_conflicts
= strmap_get(&opt
->priv
->conflicts
, primary_path
);
773 if (!path_conflicts
) {
774 path_conflicts
= xmalloc(sizeof(*path_conflicts
));
775 string_list_init_dup(path_conflicts
);
776 strmap_put(&opt
->priv
->conflicts
, primary_path
, path_conflicts
);
779 /* Add a logical_conflict at the end to store info from this call */
780 info
= xcalloc(1, sizeof(*info
));
782 strvec_init(&info
->paths
);
784 /* Handle the list of paths */
785 strvec_push(&info
->paths
, primary_path
);
787 strvec_push(&info
->paths
, other_path_1
);
789 strvec_push(&info
->paths
, other_path_2
);
791 for (int i
= 0; i
< other_paths
->nr
; i
++)
792 strvec_push(&info
->paths
, other_paths
->items
[i
].string
);
794 /* Handle message and its format, in normal case */
795 dest
= (opt
->record_conflict_msgs_as_headers
? &tmp
: &buf
);
798 if (opt
->priv
->call_depth
) {
799 strbuf_addchars(dest
, ' ', 2);
800 strbuf_addstr(dest
, "From inner merge:");
801 strbuf_addchars(dest
, ' ', opt
->priv
->call_depth
* 2);
803 strbuf_vaddf(dest
, fmt
, ap
);
806 /* Handle specialized formatting of message under --remerge-diff */
807 if (opt
->record_conflict_msgs_as_headers
) {
808 int i_sb
= 0, i_tmp
= 0;
810 /* Start with the specified prefix */
811 if (opt
->msg_header_prefix
)
812 strbuf_addf(&buf
, "%s ", opt
->msg_header_prefix
);
814 /* Copy tmp to sb, adding spaces after newlines */
815 strbuf_grow(&buf
, buf
.len
+ 2*tmp
.len
); /* more than sufficient */
816 for (; i_tmp
< tmp
.len
; i_tmp
++, i_sb
++) {
817 /* Copy next character from tmp to sb */
818 buf
.buf
[buf
.len
+ i_sb
] = tmp
.buf
[i_tmp
];
820 /* If we copied a newline, add a space */
821 if (tmp
.buf
[i_tmp
] == '\n')
822 buf
.buf
[++i_sb
] = ' ';
824 /* Update length and ensure it's NUL-terminated */
826 buf
.buf
[buf
.len
] = '\0';
828 strbuf_release(&tmp
);
830 string_list_append_nodup(path_conflicts
, strbuf_detach(&buf
, NULL
))
834 static struct diff_filespec
*pool_alloc_filespec(struct mem_pool
*pool
,
837 /* Similar to alloc_filespec(), but allocate from pool and reuse path */
838 struct diff_filespec
*spec
;
840 spec
= mem_pool_calloc(pool
, 1, sizeof(*spec
));
841 spec
->path
= (char*)path
; /* spec won't modify it */
844 spec
->is_binary
= -1;
848 static struct diff_filepair
*pool_diff_queue(struct mem_pool
*pool
,
849 struct diff_queue_struct
*queue
,
850 struct diff_filespec
*one
,
851 struct diff_filespec
*two
)
853 /* Same code as diff_queue(), except allocate from pool */
854 struct diff_filepair
*dp
;
856 dp
= mem_pool_calloc(pool
, 1, sizeof(*dp
));
864 /* add a string to a strbuf, but converting "/" to "_" */
865 static void add_flattened_path(struct strbuf
*out
, const char *s
)
868 strbuf_addstr(out
, s
);
869 for (; i
< out
->len
; i
++)
870 if (out
->buf
[i
] == '/')
874 static char *unique_path(struct merge_options
*opt
,
879 struct strbuf newpath
= STRBUF_INIT
;
882 struct strmap
*existing_paths
= &opt
->priv
->paths
;
884 strbuf_addf(&newpath
, "%s~", path
);
885 add_flattened_path(&newpath
, branch
);
887 base_len
= newpath
.len
;
888 while (strmap_contains(existing_paths
, newpath
.buf
)) {
889 strbuf_setlen(&newpath
, base_len
);
890 strbuf_addf(&newpath
, "_%d", suffix
++);
893 /* Track the new path in our memory pool */
894 ret
= mem_pool_alloc(&opt
->priv
->pool
, newpath
.len
+ 1);
895 memcpy(ret
, newpath
.buf
, newpath
.len
+ 1);
896 strbuf_release(&newpath
);
900 /*** Function Grouping: functions related to collect_merge_info() ***/
902 static int traverse_trees_wrapper_callback(int n
,
904 unsigned long dirmask
,
905 struct name_entry
*names
,
906 struct traverse_info
*info
)
908 struct merge_options
*opt
= info
->data
;
909 struct rename_info
*renames
= &opt
->priv
->renames
;
910 unsigned filemask
= mask
& ~dirmask
;
914 if (!renames
->callback_data_traverse_path
)
915 renames
->callback_data_traverse_path
= xstrdup(info
->traverse_path
);
917 if (filemask
&& filemask
== renames
->dir_rename_mask
)
918 renames
->dir_rename_mask
= 0x07;
920 ALLOC_GROW(renames
->callback_data
, renames
->callback_data_nr
+ 1,
921 renames
->callback_data_alloc
);
922 renames
->callback_data
[renames
->callback_data_nr
].mask
= mask
;
923 renames
->callback_data
[renames
->callback_data_nr
].dirmask
= dirmask
;
924 COPY_ARRAY(renames
->callback_data
[renames
->callback_data_nr
].names
,
926 renames
->callback_data_nr
++;
932 * Much like traverse_trees(), BUT:
933 * - read all the tree entries FIRST, saving them
934 * - note that the above step provides an opportunity to compute necessary
935 * additional details before the "real" traversal
936 * - loop through the saved entries and call the original callback on them
938 static int traverse_trees_wrapper(struct index_state
*istate
,
941 struct traverse_info
*info
)
943 int ret
, i
, old_offset
;
944 traverse_callback_t old_fn
;
945 char *old_callback_data_traverse_path
;
946 struct merge_options
*opt
= info
->data
;
947 struct rename_info
*renames
= &opt
->priv
->renames
;
949 assert(renames
->dir_rename_mask
== 2 || renames
->dir_rename_mask
== 4);
951 old_callback_data_traverse_path
= renames
->callback_data_traverse_path
;
953 old_offset
= renames
->callback_data_nr
;
955 renames
->callback_data_traverse_path
= NULL
;
956 info
->fn
= traverse_trees_wrapper_callback
;
957 ret
= traverse_trees(istate
, n
, t
, info
);
961 info
->traverse_path
= renames
->callback_data_traverse_path
;
963 for (i
= old_offset
; i
< renames
->callback_data_nr
; ++i
) {
965 renames
->callback_data
[i
].mask
,
966 renames
->callback_data
[i
].dirmask
,
967 renames
->callback_data
[i
].names
,
971 renames
->callback_data_nr
= old_offset
;
972 free(renames
->callback_data_traverse_path
);
973 renames
->callback_data_traverse_path
= old_callback_data_traverse_path
;
974 info
->traverse_path
= NULL
;
978 static void setup_path_info(struct merge_options
*opt
,
979 struct string_list_item
*result
,
980 const char *current_dir_name
,
981 int current_dir_name_len
,
982 char *fullpath
, /* we'll take over ownership */
983 struct name_entry
*names
,
984 struct name_entry
*merged_version
,
985 unsigned is_null
, /* boolean */
986 unsigned df_conflict
, /* boolean */
989 int resolved
/* boolean */)
991 /* result->util is void*, so mi is a convenience typed variable */
992 struct merged_info
*mi
;
994 assert(!is_null
|| resolved
);
995 assert(!df_conflict
|| !resolved
); /* df_conflict implies !resolved */
996 assert(resolved
== (merged_version
!= NULL
));
998 mi
= mem_pool_calloc(&opt
->priv
->pool
, 1,
999 resolved
? sizeof(struct merged_info
) :
1000 sizeof(struct conflict_info
));
1001 mi
->directory_name
= current_dir_name
;
1002 mi
->basename_offset
= current_dir_name_len
;
1003 mi
->clean
= !!resolved
;
1005 mi
->result
.mode
= merged_version
->mode
;
1006 oidcpy(&mi
->result
.oid
, &merged_version
->oid
);
1007 mi
->is_null
= !!is_null
;
1010 struct conflict_info
*ci
;
1012 ASSIGN_AND_VERIFY_CI(ci
, mi
);
1013 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
1014 ci
->pathnames
[i
] = fullpath
;
1015 ci
->stages
[i
].mode
= names
[i
].mode
;
1016 oidcpy(&ci
->stages
[i
].oid
, &names
[i
].oid
);
1018 ci
->filemask
= filemask
;
1019 ci
->dirmask
= dirmask
;
1020 ci
->df_conflict
= !!df_conflict
;
1023 * Assume is_null for now, but if we have entries
1024 * under the directory then when it is complete in
1025 * write_completed_directory() it'll update this.
1026 * Also, for D/F conflicts, we have to handle the
1027 * directory first, then clear this bit and process
1028 * the file to see how it is handled -- that occurs
1029 * near the top of process_entry().
1033 strmap_put(&opt
->priv
->paths
, fullpath
, mi
);
1034 result
->string
= fullpath
;
1038 static void add_pair(struct merge_options
*opt
,
1039 struct name_entry
*names
,
1040 const char *pathname
,
1042 unsigned is_add
/* if false, is_delete */,
1043 unsigned match_mask
,
1044 unsigned dir_rename_mask
)
1046 struct diff_filespec
*one
, *two
;
1047 struct rename_info
*renames
= &opt
->priv
->renames
;
1048 int names_idx
= is_add
? side
: 0;
1051 assert(match_mask
== 0 || match_mask
== 6);
1052 if (strset_contains(&renames
->cached_target_names
[side
],
1056 unsigned content_relevant
= (match_mask
== 0);
1057 unsigned location_relevant
= (dir_rename_mask
== 0x07);
1059 assert(match_mask
== 0 || match_mask
== 3 || match_mask
== 5);
1062 * If pathname is found in cached_irrelevant[side] due to
1063 * previous pick but for this commit content is relevant,
1064 * then we need to remove it from cached_irrelevant.
1066 if (content_relevant
)
1067 /* strset_remove is no-op if strset doesn't have key */
1068 strset_remove(&renames
->cached_irrelevant
[side
],
1072 * We do not need to re-detect renames for paths that we already
1073 * know the pairing, i.e. for cached_pairs (or
1074 * cached_irrelevant). However, handle_deferred_entries() needs
1075 * to loop over the union of keys from relevant_sources[side] and
1076 * cached_pairs[side], so for simplicity we set relevant_sources
1077 * for all the cached_pairs too and then strip them back out in
1078 * prune_cached_from_relevant() at the beginning of
1079 * detect_regular_renames().
1081 if (content_relevant
|| location_relevant
) {
1082 /* content_relevant trumps location_relevant */
1083 strintmap_set(&renames
->relevant_sources
[side
], pathname
,
1084 content_relevant
? RELEVANT_CONTENT
: RELEVANT_LOCATION
);
1088 * Avoid creating pair if we've already cached rename results.
1089 * Note that we do this after setting relevant_sources[side]
1090 * as noted in the comment above.
1092 if (strmap_contains(&renames
->cached_pairs
[side
], pathname
) ||
1093 strset_contains(&renames
->cached_irrelevant
[side
], pathname
))
1097 one
= pool_alloc_filespec(&opt
->priv
->pool
, pathname
);
1098 two
= pool_alloc_filespec(&opt
->priv
->pool
, pathname
);
1099 fill_filespec(is_add
? two
: one
,
1100 &names
[names_idx
].oid
, 1, names
[names_idx
].mode
);
1101 pool_diff_queue(&opt
->priv
->pool
, &renames
->pairs
[side
], one
, two
);
1104 static void collect_rename_info(struct merge_options
*opt
,
1105 struct name_entry
*names
,
1106 const char *dirname
,
1107 const char *fullname
,
1110 unsigned match_mask
)
1112 struct rename_info
*renames
= &opt
->priv
->renames
;
1116 * Update dir_rename_mask (determines ignore-rename-source validity)
1118 * dir_rename_mask helps us keep track of when directory rename
1119 * detection may be relevant. Basically, whenver a directory is
1120 * removed on one side of history, and a file is added to that
1121 * directory on the other side of history, directory rename
1122 * detection is relevant (meaning we have to detect renames for all
1123 * files within that directory to deduce where the directory
1124 * moved). Also, whenever a directory needs directory rename
1125 * detection, due to the "majority rules" choice for where to move
1126 * it (see t6423 testcase 1f), we also need to detect renames for
1127 * all files within subdirectories of that directory as well.
1129 * Here we haven't looked at files within the directory yet, we are
1130 * just looking at the directory itself. So, if we aren't yet in
1131 * a case where a parent directory needed directory rename detection
1132 * (i.e. dir_rename_mask != 0x07), and if the directory was removed
1133 * on one side of history, record the mask of the other side of
1134 * history in dir_rename_mask.
1136 if (renames
->dir_rename_mask
!= 0x07 &&
1137 (dirmask
== 3 || dirmask
== 5)) {
1138 /* simple sanity check */
1139 assert(renames
->dir_rename_mask
== 0 ||
1140 renames
->dir_rename_mask
== (dirmask
& ~1));
1141 /* update dir_rename_mask; have it record mask of new side */
1142 renames
->dir_rename_mask
= (dirmask
& ~1);
1145 /* Update dirs_removed, as needed */
1146 if (dirmask
== 1 || dirmask
== 3 || dirmask
== 5) {
1147 /* absent_mask = 0x07 - dirmask; sides = absent_mask/2 */
1148 unsigned sides
= (0x07 - dirmask
)/2;
1149 unsigned relevance
= (renames
->dir_rename_mask
== 0x07) ?
1150 RELEVANT_FOR_ANCESTOR
: NOT_RELEVANT
;
1152 * Record relevance of this directory. However, note that
1153 * when collect_merge_info_callback() recurses into this
1154 * directory and calls collect_rename_info() on paths
1155 * within that directory, if we find a path that was added
1156 * to this directory on the other side of history, we will
1157 * upgrade this value to RELEVANT_FOR_SELF; see below.
1160 strintmap_set(&renames
->dirs_removed
[1], fullname
,
1163 strintmap_set(&renames
->dirs_removed
[2], fullname
,
1168 * Here's the block that potentially upgrades to RELEVANT_FOR_SELF.
1169 * When we run across a file added to a directory. In such a case,
1170 * find the directory of the file and upgrade its relevance.
1172 if (renames
->dir_rename_mask
== 0x07 &&
1173 (filemask
== 2 || filemask
== 4)) {
1175 * Need directory rename for parent directory on other side
1176 * of history from added file. Thus
1177 * side = (~filemask & 0x06) >> 1
1179 * side = 3 - (filemask/2).
1181 unsigned side
= 3 - (filemask
>> 1);
1182 strintmap_set(&renames
->dirs_removed
[side
], dirname
,
1186 if (filemask
== 0 || filemask
== 7)
1189 for (side
= MERGE_SIDE1
; side
<= MERGE_SIDE2
; ++side
) {
1190 unsigned side_mask
= (1 << side
);
1192 /* Check for deletion on side */
1193 if ((filemask
& 1) && !(filemask
& side_mask
))
1194 add_pair(opt
, names
, fullname
, side
, 0 /* delete */,
1195 match_mask
& filemask
,
1196 renames
->dir_rename_mask
);
1198 /* Check for addition on side */
1199 if (!(filemask
& 1) && (filemask
& side_mask
))
1200 add_pair(opt
, names
, fullname
, side
, 1 /* add */,
1201 match_mask
& filemask
,
1202 renames
->dir_rename_mask
);
1206 static int collect_merge_info_callback(int n
,
1208 unsigned long dirmask
,
1209 struct name_entry
*names
,
1210 struct traverse_info
*info
)
1214 * common ancestor (mbase) has mask 1, and stored in index 0 of names
1215 * head of side 1 (side1) has mask 2, and stored in index 1 of names
1216 * head of side 2 (side2) has mask 4, and stored in index 2 of names
1218 struct merge_options
*opt
= info
->data
;
1219 struct merge_options_internal
*opti
= opt
->priv
;
1220 struct rename_info
*renames
= &opt
->priv
->renames
;
1221 struct string_list_item pi
; /* Path Info */
1222 struct conflict_info
*ci
; /* typed alias to pi.util (which is void*) */
1223 struct name_entry
*p
;
1226 const char *dirname
= opti
->current_dir_name
;
1227 unsigned prev_dir_rename_mask
= renames
->dir_rename_mask
;
1228 unsigned filemask
= mask
& ~dirmask
;
1229 unsigned match_mask
= 0; /* will be updated below */
1230 unsigned mbase_null
= !(mask
& 1);
1231 unsigned side1_null
= !(mask
& 2);
1232 unsigned side2_null
= !(mask
& 4);
1233 unsigned side1_matches_mbase
= (!side1_null
&& !mbase_null
&&
1234 names
[0].mode
== names
[1].mode
&&
1235 oideq(&names
[0].oid
, &names
[1].oid
));
1236 unsigned side2_matches_mbase
= (!side2_null
&& !mbase_null
&&
1237 names
[0].mode
== names
[2].mode
&&
1238 oideq(&names
[0].oid
, &names
[2].oid
));
1239 unsigned sides_match
= (!side1_null
&& !side2_null
&&
1240 names
[1].mode
== names
[2].mode
&&
1241 oideq(&names
[1].oid
, &names
[2].oid
));
1244 * Note: When a path is a file on one side of history and a directory
1245 * in another, we have a directory/file conflict. In such cases, if
1246 * the conflict doesn't resolve from renames and deletions, then we
1247 * always leave directories where they are and move files out of the
1248 * way. Thus, while struct conflict_info has a df_conflict field to
1249 * track such conflicts, we ignore that field for any directories at
1250 * a path and only pay attention to it for files at the given path.
1251 * The fact that we leave directories were they are also means that
1252 * we do not need to worry about getting additional df_conflict
1253 * information propagated from parent directories down to children
1254 * (unlike, say traverse_trees_recursive() in unpack-trees.c, which
1255 * sets a newinfo.df_conflicts field specifically to propagate it).
1257 unsigned df_conflict
= (filemask
!= 0) && (dirmask
!= 0);
1259 /* n = 3 is a fundamental assumption. */
1261 BUG("Called collect_merge_info_callback wrong");
1264 * A bunch of sanity checks verifying that traverse_trees() calls
1265 * us the way I expect. Could just remove these at some point,
1266 * though maybe they are helpful to future code readers.
1268 assert(mbase_null
== is_null_oid(&names
[0].oid
));
1269 assert(side1_null
== is_null_oid(&names
[1].oid
));
1270 assert(side2_null
== is_null_oid(&names
[2].oid
));
1271 assert(!mbase_null
|| !side1_null
|| !side2_null
);
1272 assert(mask
> 0 && mask
< 8);
1274 /* Determine match_mask */
1275 if (side1_matches_mbase
)
1276 match_mask
= (side2_matches_mbase
? 7 : 3);
1277 else if (side2_matches_mbase
)
1279 else if (sides_match
)
1283 * Get the name of the relevant filepath, which we'll pass to
1284 * setup_path_info() for tracking.
1289 len
= traverse_path_len(info
, p
->pathlen
);
1291 /* +1 in both of the following lines to include the NUL byte */
1292 fullpath
= mem_pool_alloc(&opt
->priv
->pool
, len
+ 1);
1293 make_traverse_path(fullpath
, len
+ 1, info
, p
->path
, p
->pathlen
);
1296 * If mbase, side1, and side2 all match, we can resolve early. Even
1297 * if these are trees, there will be no renames or anything
1300 if (side1_matches_mbase
&& side2_matches_mbase
) {
1301 /* mbase, side1, & side2 all match; use mbase as resolution */
1302 setup_path_info(opt
, &pi
, dirname
, info
->pathlen
, fullpath
,
1303 names
, names
+0, mbase_null
, 0 /* df_conflict */,
1304 filemask
, dirmask
, 1 /* resolved */);
1309 * If the sides match, and all three paths are present and are
1310 * files, then we can take either as the resolution. We can't do
1311 * this with trees, because there may be rename sources from the
1314 if (sides_match
&& filemask
== 0x07) {
1315 /* use side1 (== side2) version as resolution */
1316 setup_path_info(opt
, &pi
, dirname
, info
->pathlen
, fullpath
,
1317 names
, names
+1, side1_null
, 0,
1318 filemask
, dirmask
, 1);
1323 * If side1 matches mbase and all three paths are present and are
1324 * files, then we can use side2 as the resolution. We cannot
1325 * necessarily do so this for trees, because there may be rename
1326 * destinations within side2.
1328 if (side1_matches_mbase
&& filemask
== 0x07) {
1329 /* use side2 version as resolution */
1330 setup_path_info(opt
, &pi
, dirname
, info
->pathlen
, fullpath
,
1331 names
, names
+2, side2_null
, 0,
1332 filemask
, dirmask
, 1);
1336 /* Similar to above but swapping sides 1 and 2 */
1337 if (side2_matches_mbase
&& filemask
== 0x07) {
1338 /* use side1 version as resolution */
1339 setup_path_info(opt
, &pi
, dirname
, info
->pathlen
, fullpath
,
1340 names
, names
+1, side1_null
, 0,
1341 filemask
, dirmask
, 1);
1346 * Sometimes we can tell that a source path need not be included in
1347 * rename detection -- namely, whenever either
1348 * side1_matches_mbase && side2_null
1350 * side2_matches_mbase && side1_null
1351 * However, we call collect_rename_info() even in those cases,
1352 * because exact renames are cheap and would let us remove both a
1353 * source and destination path. We'll cull the unneeded sources
1356 collect_rename_info(opt
, names
, dirname
, fullpath
,
1357 filemask
, dirmask
, match_mask
);
1360 * None of the special cases above matched, so we have a
1361 * provisional conflict. (Rename detection might allow us to
1362 * unconflict some more cases, but that comes later so all we can
1363 * do now is record the different non-null file hashes.)
1365 setup_path_info(opt
, &pi
, dirname
, info
->pathlen
, fullpath
,
1366 names
, NULL
, 0, df_conflict
, filemask
, dirmask
, 0);
1370 ci
->match_mask
= match_mask
;
1372 /* If dirmask, recurse into subdirectories */
1374 struct traverse_info newinfo
;
1375 struct tree_desc t
[3];
1376 void *buf
[3] = {NULL
, NULL
, NULL
};
1377 const char *original_dir_name
;
1381 * Check for whether we can avoid recursing due to one side
1382 * matching the merge base. The side that does NOT match is
1383 * the one that might have a rename destination we need.
1385 assert(!side1_matches_mbase
|| !side2_matches_mbase
);
1386 side
= side1_matches_mbase
? MERGE_SIDE2
:
1387 side2_matches_mbase
? MERGE_SIDE1
: MERGE_BASE
;
1388 if (filemask
== 0 && (dirmask
== 2 || dirmask
== 4)) {
1390 * Also defer recursing into new directories; set up a
1391 * few variables to let us do so.
1393 ci
->match_mask
= (7 - dirmask
);
1396 if (renames
->dir_rename_mask
!= 0x07 &&
1397 side
!= MERGE_BASE
&&
1398 renames
->deferred
[side
].trivial_merges_okay
&&
1399 !strset_contains(&renames
->deferred
[side
].target_dirs
,
1401 strintmap_set(&renames
->deferred
[side
].possible_trivial_merges
,
1402 pi
.string
, renames
->dir_rename_mask
);
1403 renames
->dir_rename_mask
= prev_dir_rename_mask
;
1407 /* We need to recurse */
1408 ci
->match_mask
&= filemask
;
1410 newinfo
.prev
= info
;
1411 newinfo
.name
= p
->path
;
1412 newinfo
.namelen
= p
->pathlen
;
1413 newinfo
.pathlen
= st_add3(newinfo
.pathlen
, p
->pathlen
, 1);
1415 * If this directory we are about to recurse into cared about
1416 * its parent directory (the current directory) having a D/F
1417 * conflict, then we'd propagate the masks in this way:
1418 * newinfo.df_conflicts |= (mask & ~dirmask);
1419 * But we don't worry about propagating D/F conflicts. (See
1420 * comment near setting of local df_conflict variable near
1421 * the beginning of this function).
1424 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
1425 if (i
== 1 && side1_matches_mbase
)
1427 else if (i
== 2 && side2_matches_mbase
)
1429 else if (i
== 2 && sides_match
)
1432 const struct object_id
*oid
= NULL
;
1434 oid
= &names
[i
].oid
;
1435 buf
[i
] = fill_tree_descriptor(opt
->repo
,
1441 original_dir_name
= opti
->current_dir_name
;
1442 opti
->current_dir_name
= pi
.string
;
1443 if (renames
->dir_rename_mask
== 0 ||
1444 renames
->dir_rename_mask
== 0x07)
1445 ret
= traverse_trees(NULL
, 3, t
, &newinfo
);
1447 ret
= traverse_trees_wrapper(NULL
, 3, t
, &newinfo
);
1448 opti
->current_dir_name
= original_dir_name
;
1449 renames
->dir_rename_mask
= prev_dir_rename_mask
;
1451 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++)
1461 static void resolve_trivial_directory_merge(struct conflict_info
*ci
, int side
)
1464 assert((side
== 1 && ci
->match_mask
== 5) ||
1465 (side
== 2 && ci
->match_mask
== 3));
1466 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[side
].oid
);
1467 ci
->merged
.result
.mode
= ci
->stages
[side
].mode
;
1468 ci
->merged
.is_null
= is_null_oid(&ci
->stages
[side
].oid
);
1470 ci
->merged
.clean
= 1; /* (ci->filemask == 0); */
1473 static int handle_deferred_entries(struct merge_options
*opt
,
1474 struct traverse_info
*info
)
1476 struct rename_info
*renames
= &opt
->priv
->renames
;
1477 struct hashmap_iter iter
;
1478 struct strmap_entry
*entry
;
1480 int path_count_before
, path_count_after
= 0;
1482 path_count_before
= strmap_get_size(&opt
->priv
->paths
);
1483 for (side
= MERGE_SIDE1
; side
<= MERGE_SIDE2
; side
++) {
1484 unsigned optimization_okay
= 1;
1485 struct strintmap copy
;
1487 /* Loop over the set of paths we need to know rename info for */
1488 strset_for_each_entry(&renames
->relevant_sources
[side
],
1490 char *rename_target
, *dir
, *dir_marker
;
1491 struct strmap_entry
*e
;
1494 * If we don't know delete/rename info for this path,
1495 * then we need to recurse into all trees to get all
1496 * adds to make sure we have it.
1498 if (strset_contains(&renames
->cached_irrelevant
[side
],
1501 e
= strmap_get_entry(&renames
->cached_pairs
[side
],
1504 optimization_okay
= 0;
1508 /* If this is a delete, we have enough info already */
1509 rename_target
= e
->value
;
1513 /* If we already walked the rename target, we're good */
1514 if (strmap_contains(&opt
->priv
->paths
, rename_target
))
1518 * Otherwise, we need to get a list of directories that
1519 * will need to be recursed into to get this
1522 dir
= xstrdup(rename_target
);
1523 while ((dir_marker
= strrchr(dir
, '/'))) {
1525 if (strset_contains(&renames
->deferred
[side
].target_dirs
,
1528 strset_add(&renames
->deferred
[side
].target_dirs
,
1533 renames
->deferred
[side
].trivial_merges_okay
= optimization_okay
;
1535 * We need to recurse into any directories in
1536 * possible_trivial_merges[side] found in target_dirs[side].
1537 * But when we recurse, we may need to queue up some of the
1538 * subdirectories for possible_trivial_merges[side]. Since
1539 * we can't safely iterate through a hashmap while also adding
1540 * entries, move the entries into 'copy', iterate over 'copy',
1541 * and then we'll also iterate anything added into
1542 * possible_trivial_merges[side] once this loop is done.
1544 copy
= renames
->deferred
[side
].possible_trivial_merges
;
1545 strintmap_init_with_options(&renames
->deferred
[side
].possible_trivial_merges
,
1549 strintmap_for_each_entry(©
, &iter
, entry
) {
1550 const char *path
= entry
->key
;
1551 unsigned dir_rename_mask
= (intptr_t)entry
->value
;
1552 struct conflict_info
*ci
;
1554 struct tree_desc t
[3];
1555 void *buf
[3] = {NULL
,};
1558 ci
= strmap_get(&opt
->priv
->paths
, path
);
1560 dirmask
= ci
->dirmask
;
1562 if (optimization_okay
&&
1563 !strset_contains(&renames
->deferred
[side
].target_dirs
,
1565 resolve_trivial_directory_merge(ci
, side
);
1570 info
->namelen
= strlen(path
);
1571 info
->pathlen
= info
->namelen
+ 1;
1573 for (i
= 0; i
< 3; i
++, dirmask
>>= 1) {
1574 if (i
== 1 && ci
->match_mask
== 3)
1576 else if (i
== 2 && ci
->match_mask
== 5)
1578 else if (i
== 2 && ci
->match_mask
== 6)
1581 const struct object_id
*oid
= NULL
;
1583 oid
= &ci
->stages
[i
].oid
;
1584 buf
[i
] = fill_tree_descriptor(opt
->repo
,
1589 ci
->match_mask
&= ci
->filemask
;
1590 opt
->priv
->current_dir_name
= path
;
1591 renames
->dir_rename_mask
= dir_rename_mask
;
1592 if (renames
->dir_rename_mask
== 0 ||
1593 renames
->dir_rename_mask
== 0x07)
1594 ret
= traverse_trees(NULL
, 3, t
, info
);
1596 ret
= traverse_trees_wrapper(NULL
, 3, t
, info
);
1598 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++)
1604 strintmap_clear(©
);
1605 strintmap_for_each_entry(&renames
->deferred
[side
].possible_trivial_merges
,
1607 const char *path
= entry
->key
;
1608 struct conflict_info
*ci
;
1610 ci
= strmap_get(&opt
->priv
->paths
, path
);
1613 assert(renames
->deferred
[side
].trivial_merges_okay
&&
1614 !strset_contains(&renames
->deferred
[side
].target_dirs
,
1616 resolve_trivial_directory_merge(ci
, side
);
1618 if (!optimization_okay
|| path_count_after
)
1619 path_count_after
= strmap_get_size(&opt
->priv
->paths
);
1621 if (path_count_after
) {
1623 * The choice of wanted_factor here does not affect
1624 * correctness, only performance. When the
1625 * path_count_after / path_count_before
1626 * ratio is high, redoing after renames is a big
1627 * performance boost. I suspect that redoing is a wash
1628 * somewhere near a value of 2, and below that redoing will
1629 * slow things down. I applied a fudge factor and picked
1630 * 3; see the commit message when this was introduced for
1631 * back of the envelope calculations for this ratio.
1633 const int wanted_factor
= 3;
1635 /* We should only redo collect_merge_info one time */
1636 assert(renames
->redo_after_renames
== 0);
1638 if (path_count_after
/ path_count_before
>= wanted_factor
) {
1639 renames
->redo_after_renames
= 1;
1640 renames
->cached_pairs_valid_side
= -1;
1642 } else if (renames
->redo_after_renames
== 2)
1643 renames
->redo_after_renames
= 0;
1647 static int collect_merge_info(struct merge_options
*opt
,
1648 struct tree
*merge_base
,
1653 struct tree_desc t
[3];
1654 struct traverse_info info
;
1656 opt
->priv
->toplevel_dir
= "";
1657 opt
->priv
->current_dir_name
= opt
->priv
->toplevel_dir
;
1658 setup_traverse_info(&info
, opt
->priv
->toplevel_dir
);
1659 info
.fn
= collect_merge_info_callback
;
1661 info
.show_all_errors
= 1;
1663 parse_tree(merge_base
);
1666 init_tree_desc(t
+ 0, merge_base
->buffer
, merge_base
->size
);
1667 init_tree_desc(t
+ 1, side1
->buffer
, side1
->size
);
1668 init_tree_desc(t
+ 2, side2
->buffer
, side2
->size
);
1670 trace2_region_enter("merge", "traverse_trees", opt
->repo
);
1671 ret
= traverse_trees(NULL
, 3, t
, &info
);
1673 ret
= handle_deferred_entries(opt
, &info
);
1674 trace2_region_leave("merge", "traverse_trees", opt
->repo
);
1679 /*** Function Grouping: functions related to threeway content merges ***/
1681 static int find_first_merges(struct repository
*repo
,
1685 struct object_array
*result
)
1688 struct object_array merges
= OBJECT_ARRAY_INIT
;
1689 struct commit
*commit
;
1690 int contains_another
;
1692 char merged_revision
[GIT_MAX_HEXSZ
+ 2];
1693 const char *rev_args
[] = { "rev-list", "--merges", "--ancestry-path",
1694 "--all", merged_revision
, NULL
};
1695 struct rev_info revs
;
1696 struct setup_revision_opt rev_opts
;
1698 memset(result
, 0, sizeof(struct object_array
));
1699 memset(&rev_opts
, 0, sizeof(rev_opts
));
1701 /* get all revisions that merge commit a */
1702 xsnprintf(merged_revision
, sizeof(merged_revision
), "^%s",
1703 oid_to_hex(&a
->object
.oid
));
1704 repo_init_revisions(repo
, &revs
, NULL
);
1705 /* FIXME: can't handle linked worktrees in submodules yet */
1706 revs
.single_worktree
= path
!= NULL
;
1707 setup_revisions(ARRAY_SIZE(rev_args
)-1, rev_args
, &revs
, &rev_opts
);
1709 /* save all revisions from the above list that contain b */
1710 if (prepare_revision_walk(&revs
))
1711 die("revision walk setup failed");
1712 while ((commit
= get_revision(&revs
)) != NULL
) {
1713 struct object
*o
= &(commit
->object
);
1714 int ret
= repo_in_merge_bases(repo
, b
, commit
);
1717 object_array_clear(&merges
);
1718 release_revisions(&revs
);
1722 add_object_array(o
, NULL
, &merges
);
1724 reset_revision_walk();
1726 /* Now we've got all merges that contain a and b. Prune all
1727 * merges that contain another found merge and save them in
1730 for (i
= 0; i
< merges
.nr
; i
++) {
1731 struct commit
*m1
= (struct commit
*) merges
.objects
[i
].item
;
1733 contains_another
= 0;
1734 for (j
= 0; j
< merges
.nr
; j
++) {
1735 struct commit
*m2
= (struct commit
*) merges
.objects
[j
].item
;
1737 int ret
= repo_in_merge_bases(repo
, m2
, m1
);
1739 object_array_clear(&merges
);
1740 release_revisions(&revs
);
1744 contains_another
= 1;
1750 if (!contains_another
)
1751 add_object_array(merges
.objects
[i
].item
, NULL
, result
);
1754 object_array_clear(&merges
);
1755 release_revisions(&revs
);
1759 static int merge_submodule(struct merge_options
*opt
,
1761 const struct object_id
*o
,
1762 const struct object_id
*a
,
1763 const struct object_id
*b
,
1764 struct object_id
*result
)
1766 struct repository subrepo
;
1767 struct strbuf sb
= STRBUF_INIT
;
1769 struct commit
*commit_o
, *commit_a
, *commit_b
;
1771 struct object_array merges
;
1774 int search
= !opt
->priv
->call_depth
;
1775 int sub_not_initialized
= 1;
1776 int sub_flag
= CONFLICT_SUBMODULE_FAILED_TO_MERGE
;
1778 /* store fallback answer in result in case we fail */
1779 oidcpy(result
, opt
->priv
->call_depth
? o
: a
);
1781 /* we can not handle deletion conflicts */
1782 if (is_null_oid(a
) || is_null_oid(b
))
1783 BUG("submodule deleted on one side; this should be handled outside of merge_submodule()");
1785 if ((sub_not_initialized
= repo_submodule_init(&subrepo
,
1786 opt
->repo
, path
, null_oid()))) {
1787 path_msg(opt
, CONFLICT_SUBMODULE_NOT_INITIALIZED
, 0,
1788 path
, NULL
, NULL
, NULL
,
1789 _("Failed to merge submodule %s (not checked out)"),
1791 sub_flag
= CONFLICT_SUBMODULE_NOT_INITIALIZED
;
1795 if (is_null_oid(o
)) {
1796 path_msg(opt
, CONFLICT_SUBMODULE_NULL_MERGE_BASE
, 0,
1797 path
, NULL
, NULL
, NULL
,
1798 _("Failed to merge submodule %s (no merge base)"),
1803 if (!(commit_o
= lookup_commit_reference(&subrepo
, o
)) ||
1804 !(commit_a
= lookup_commit_reference(&subrepo
, a
)) ||
1805 !(commit_b
= lookup_commit_reference(&subrepo
, b
))) {
1806 path_msg(opt
, CONFLICT_SUBMODULE_HISTORY_NOT_AVAILABLE
, 0,
1807 path
, NULL
, NULL
, NULL
,
1808 _("Failed to merge submodule %s (commits not present)"),
1810 sub_flag
= CONFLICT_SUBMODULE_HISTORY_NOT_AVAILABLE
;
1814 /* check whether both changes are forward */
1815 ret2
= repo_in_merge_bases(&subrepo
, commit_o
, commit_a
);
1817 path_msg(opt
, CONFLICT_SUBMODULE_CORRUPT
, 0,
1818 path
, NULL
, NULL
, NULL
,
1819 _("Failed to merge submodule %s "
1820 "(repository corrupt)"),
1826 ret2
= repo_in_merge_bases(&subrepo
, commit_o
, commit_b
);
1828 path_msg(opt
, CONFLICT_SUBMODULE_CORRUPT
, 0,
1829 path
, NULL
, NULL
, NULL
,
1830 _("Failed to merge submodule %s "
1831 "(repository corrupt)"),
1837 path_msg(opt
, CONFLICT_SUBMODULE_MAY_HAVE_REWINDS
, 0,
1838 path
, NULL
, NULL
, NULL
,
1839 _("Failed to merge submodule %s "
1840 "(commits don't follow merge-base)"),
1845 /* Case #1: a is contained in b or vice versa */
1846 ret2
= repo_in_merge_bases(&subrepo
, commit_a
, commit_b
);
1848 path_msg(opt
, CONFLICT_SUBMODULE_CORRUPT
, 0,
1849 path
, NULL
, NULL
, NULL
,
1850 _("Failed to merge submodule %s "
1851 "(repository corrupt)"),
1858 path_msg(opt
, INFO_SUBMODULE_FAST_FORWARDING
, 1,
1859 path
, NULL
, NULL
, NULL
,
1860 _("Note: Fast-forwarding submodule %s to %s"),
1861 path
, oid_to_hex(b
));
1865 ret2
= repo_in_merge_bases(&subrepo
, commit_b
, commit_a
);
1867 path_msg(opt
, CONFLICT_SUBMODULE_CORRUPT
, 0,
1868 path
, NULL
, NULL
, NULL
,
1869 _("Failed to merge submodule %s "
1870 "(repository corrupt)"),
1877 path_msg(opt
, INFO_SUBMODULE_FAST_FORWARDING
, 1,
1878 path
, NULL
, NULL
, NULL
,
1879 _("Note: Fast-forwarding submodule %s to %s"),
1880 path
, oid_to_hex(a
));
1886 * Case #2: There are one or more merges that contain a and b in
1887 * the submodule. If there is only one, then present it as a
1888 * suggestion to the user, but leave it marked unmerged so the
1889 * user needs to confirm the resolution.
1892 /* Skip the search if makes no sense to the calling context. */
1896 /* find commit which merges them */
1897 parent_count
= find_first_merges(&subrepo
, path
, commit_a
, commit_b
,
1899 switch (parent_count
) {
1901 path_msg(opt
, CONFLICT_SUBMODULE_CORRUPT
, 0,
1902 path
, NULL
, NULL
, NULL
,
1903 _("Failed to merge submodule %s "
1904 "(repository corrupt)"),
1909 path_msg(opt
, CONFLICT_SUBMODULE_FAILED_TO_MERGE
, 0,
1910 path
, NULL
, NULL
, NULL
,
1911 _("Failed to merge submodule %s"), path
);
1915 format_commit(&sb
, 4, &subrepo
,
1916 (struct commit
*)merges
.objects
[0].item
);
1917 path_msg(opt
, CONFLICT_SUBMODULE_FAILED_TO_MERGE_BUT_POSSIBLE_RESOLUTION
, 0,
1918 path
, NULL
, NULL
, NULL
,
1919 _("Failed to merge submodule %s, but a possible merge "
1920 "resolution exists: %s"),
1922 strbuf_release(&sb
);
1925 for (i
= 0; i
< merges
.nr
; i
++)
1926 format_commit(&sb
, 4, &subrepo
,
1927 (struct commit
*)merges
.objects
[i
].item
);
1928 path_msg(opt
, CONFLICT_SUBMODULE_FAILED_TO_MERGE_BUT_POSSIBLE_RESOLUTION
, 0,
1929 path
, NULL
, NULL
, NULL
,
1930 _("Failed to merge submodule %s, but multiple "
1931 "possible merges exist:\n%s"), path
, sb
.buf
);
1932 strbuf_release(&sb
);
1935 object_array_clear(&merges
);
1937 if (!opt
->priv
->call_depth
&& !ret
) {
1938 struct string_list
*csub
= &opt
->priv
->conflicted_submodules
;
1939 struct conflicted_submodule_item
*util
;
1942 util
= xmalloc(sizeof(*util
));
1943 util
->flag
= sub_flag
;
1944 util
->abbrev
= NULL
;
1945 if (!sub_not_initialized
) {
1946 abbrev
= repo_find_unique_abbrev(&subrepo
, b
, DEFAULT_ABBREV
);
1947 util
->abbrev
= xstrdup(abbrev
);
1949 string_list_append(csub
, path
)->util
= util
;
1952 if (!sub_not_initialized
)
1953 repo_clear(&subrepo
);
1957 static void initialize_attr_index(struct merge_options
*opt
)
1960 * The renormalize_buffer() functions require attributes, and
1961 * annoyingly those can only be read from the working tree or from
1962 * an index_state. merge-ort doesn't have an index_state, so we
1963 * generate a fake one containing only attribute information.
1965 struct merged_info
*mi
;
1966 struct index_state
*attr_index
= &opt
->priv
->attr_index
;
1967 struct cache_entry
*ce
;
1969 attr_index
->repo
= opt
->repo
;
1970 attr_index
->initialized
= 1;
1972 if (!opt
->renormalize
)
1975 mi
= strmap_get(&opt
->priv
->paths
, GITATTRIBUTES_FILE
);
1980 int len
= strlen(GITATTRIBUTES_FILE
);
1981 ce
= make_empty_cache_entry(attr_index
, len
);
1982 ce
->ce_mode
= create_ce_mode(mi
->result
.mode
);
1983 ce
->ce_flags
= create_ce_flags(0);
1984 ce
->ce_namelen
= len
;
1985 oidcpy(&ce
->oid
, &mi
->result
.oid
);
1986 memcpy(ce
->name
, GITATTRIBUTES_FILE
, len
);
1987 add_index_entry(attr_index
, ce
,
1988 ADD_CACHE_OK_TO_ADD
| ADD_CACHE_OK_TO_REPLACE
);
1989 get_stream_filter(attr_index
, GITATTRIBUTES_FILE
, &ce
->oid
);
1992 struct conflict_info
*ci
;
1994 ASSIGN_AND_VERIFY_CI(ci
, mi
);
1995 for (stage
= 0; stage
< 3; stage
++) {
1996 unsigned stage_mask
= (1 << stage
);
1998 if (!(ci
->filemask
& stage_mask
))
2000 len
= strlen(GITATTRIBUTES_FILE
);
2001 ce
= make_empty_cache_entry(attr_index
, len
);
2002 ce
->ce_mode
= create_ce_mode(ci
->stages
[stage
].mode
);
2003 ce
->ce_flags
= create_ce_flags(stage
);
2004 ce
->ce_namelen
= len
;
2005 oidcpy(&ce
->oid
, &ci
->stages
[stage
].oid
);
2006 memcpy(ce
->name
, GITATTRIBUTES_FILE
, len
);
2007 add_index_entry(attr_index
, ce
,
2008 ADD_CACHE_OK_TO_ADD
| ADD_CACHE_OK_TO_REPLACE
);
2009 get_stream_filter(attr_index
, GITATTRIBUTES_FILE
,
2015 static int merge_3way(struct merge_options
*opt
,
2017 const struct object_id
*o
,
2018 const struct object_id
*a
,
2019 const struct object_id
*b
,
2020 const char *pathnames
[3],
2021 const int extra_marker_size
,
2022 mmbuffer_t
*result_buf
)
2024 mmfile_t orig
, src1
, src2
;
2025 struct ll_merge_options ll_opts
= {0};
2026 char *base
, *name1
, *name2
;
2027 enum ll_merge_result merge_status
;
2029 if (!opt
->priv
->attr_index
.initialized
)
2030 initialize_attr_index(opt
);
2032 ll_opts
.renormalize
= opt
->renormalize
;
2033 ll_opts
.extra_marker_size
= extra_marker_size
;
2034 ll_opts
.xdl_opts
= opt
->xdl_opts
;
2036 if (opt
->priv
->call_depth
) {
2037 ll_opts
.virtual_ancestor
= 1;
2038 ll_opts
.variant
= 0;
2040 switch (opt
->recursive_variant
) {
2041 case MERGE_VARIANT_OURS
:
2042 ll_opts
.variant
= XDL_MERGE_FAVOR_OURS
;
2044 case MERGE_VARIANT_THEIRS
:
2045 ll_opts
.variant
= XDL_MERGE_FAVOR_THEIRS
;
2048 ll_opts
.variant
= 0;
2053 assert(pathnames
[0] && pathnames
[1] && pathnames
[2] && opt
->ancestor
);
2054 if (pathnames
[0] == pathnames
[1] && pathnames
[1] == pathnames
[2]) {
2055 base
= mkpathdup("%s", opt
->ancestor
);
2056 name1
= mkpathdup("%s", opt
->branch1
);
2057 name2
= mkpathdup("%s", opt
->branch2
);
2059 base
= mkpathdup("%s:%s", opt
->ancestor
, pathnames
[0]);
2060 name1
= mkpathdup("%s:%s", opt
->branch1
, pathnames
[1]);
2061 name2
= mkpathdup("%s:%s", opt
->branch2
, pathnames
[2]);
2064 read_mmblob(&orig
, o
);
2065 read_mmblob(&src1
, a
);
2066 read_mmblob(&src2
, b
);
2068 merge_status
= ll_merge(result_buf
, path
, &orig
, base
,
2069 &src1
, name1
, &src2
, name2
,
2070 &opt
->priv
->attr_index
, &ll_opts
);
2071 if (merge_status
== LL_MERGE_BINARY_CONFLICT
)
2072 path_msg(opt
, CONFLICT_BINARY
, 0,
2073 path
, NULL
, NULL
, NULL
,
2074 "warning: Cannot merge binary files: %s (%s vs. %s)",
2075 path
, name1
, name2
);
2083 return merge_status
;
2086 static int handle_content_merge(struct merge_options
*opt
,
2088 const struct version_info
*o
,
2089 const struct version_info
*a
,
2090 const struct version_info
*b
,
2091 const char *pathnames
[3],
2092 const int extra_marker_size
,
2093 struct version_info
*result
)
2096 * path is the target location where we want to put the file, and
2097 * is used to determine any normalization rules in ll_merge.
2099 * The normal case is that path and all entries in pathnames are
2100 * identical, though renames can affect which path we got one of
2101 * the three blobs to merge on various sides of history.
2103 * extra_marker_size is the amount to extend conflict markers in
2104 * ll_merge; this is needed if we have content merges of content
2105 * merges, which happens for example with rename/rename(2to1) and
2106 * rename/add conflicts.
2111 * handle_content_merge() needs both files to be of the same type, i.e.
2112 * both files OR both submodules OR both symlinks. Conflicting types
2113 * needs to be handled elsewhere.
2115 assert((S_IFMT
& a
->mode
) == (S_IFMT
& b
->mode
));
2118 if (a
->mode
== b
->mode
|| a
->mode
== o
->mode
)
2119 result
->mode
= b
->mode
;
2121 /* must be the 100644/100755 case */
2122 assert(S_ISREG(a
->mode
));
2123 result
->mode
= a
->mode
;
2124 clean
= (b
->mode
== o
->mode
);
2126 * FIXME: If opt->priv->call_depth && !clean, then we really
2127 * should not make result->mode match either a->mode or
2128 * b->mode; that causes t6036 "check conflicting mode for
2129 * regular file" to fail. It would be best to use some other
2130 * mode, but we'll confuse all kinds of stuff if we use one
2131 * where S_ISREG(result->mode) isn't true, and if we use
2132 * something like 0100666, then tree-walk.c's calls to
2133 * canon_mode() will just normalize that to 100644 for us and
2134 * thus not solve anything.
2136 * Figure out if there's some kind of way we can work around
2142 * Trivial oid merge.
2144 * Note: While one might assume that the next four lines would
2145 * be unnecessary due to the fact that match_mask is often
2146 * setup and already handled, renames don't always take care
2149 if (oideq(&a
->oid
, &b
->oid
) || oideq(&a
->oid
, &o
->oid
))
2150 oidcpy(&result
->oid
, &b
->oid
);
2151 else if (oideq(&b
->oid
, &o
->oid
))
2152 oidcpy(&result
->oid
, &a
->oid
);
2154 /* Remaining rules depend on file vs. submodule vs. symlink. */
2155 else if (S_ISREG(a
->mode
)) {
2156 mmbuffer_t result_buf
;
2157 int ret
= 0, merge_status
;
2161 * If 'o' is different type, treat it as null so we do a
2164 two_way
= ((S_IFMT
& o
->mode
) != (S_IFMT
& a
->mode
));
2166 merge_status
= merge_3way(opt
, path
,
2167 two_way
? null_oid() : &o
->oid
,
2169 pathnames
, extra_marker_size
,
2172 if ((merge_status
< 0) || !result_buf
.ptr
)
2173 ret
= error(_("failed to execute internal merge"));
2176 write_object_file(result_buf
.ptr
, result_buf
.size
,
2177 OBJ_BLOB
, &result
->oid
))
2178 ret
= error(_("unable to add %s to database"), path
);
2180 free(result_buf
.ptr
);
2183 clean
&= (merge_status
== 0);
2184 path_msg(opt
, INFO_AUTO_MERGING
, 1, path
, NULL
, NULL
, NULL
,
2185 _("Auto-merging %s"), path
);
2186 } else if (S_ISGITLINK(a
->mode
)) {
2187 int two_way
= ((S_IFMT
& o
->mode
) != (S_IFMT
& a
->mode
));
2188 clean
= merge_submodule(opt
, pathnames
[0],
2189 two_way
? null_oid() : &o
->oid
,
2190 &a
->oid
, &b
->oid
, &result
->oid
);
2191 if (opt
->priv
->call_depth
&& two_way
&& !clean
) {
2192 result
->mode
= o
->mode
;
2193 oidcpy(&result
->oid
, &o
->oid
);
2195 } else if (S_ISLNK(a
->mode
)) {
2196 if (opt
->priv
->call_depth
) {
2198 result
->mode
= o
->mode
;
2199 oidcpy(&result
->oid
, &o
->oid
);
2201 switch (opt
->recursive_variant
) {
2202 case MERGE_VARIANT_NORMAL
:
2204 oidcpy(&result
->oid
, &a
->oid
);
2206 case MERGE_VARIANT_OURS
:
2207 oidcpy(&result
->oid
, &a
->oid
);
2209 case MERGE_VARIANT_THEIRS
:
2210 oidcpy(&result
->oid
, &b
->oid
);
2215 BUG("unsupported object type in the tree: %06o for %s",
2221 /*** Function Grouping: functions related to detect_and_process_renames(), ***
2222 *** which are split into directory and regular rename detection sections. ***/
2224 /*** Function Grouping: functions related to directory rename detection ***/
2226 struct collision_info
{
2227 struct string_list source_files
;
2228 unsigned reported_already
:1;
2232 * Return a new string that replaces the beginning portion (which matches
2233 * rename_info->key), with rename_info->util.new_dir. In perl-speak:
2234 * new_path_name = (old_path =~ s/rename_info->key/rename_info->value/);
2236 * Caller must ensure that old_path starts with rename_info->key + '/'.
2238 static char *apply_dir_rename(struct strmap_entry
*rename_info
,
2239 const char *old_path
)
2241 struct strbuf new_path
= STRBUF_INIT
;
2242 const char *old_dir
= rename_info
->key
;
2243 const char *new_dir
= rename_info
->value
;
2244 int oldlen
, newlen
, new_dir_len
;
2246 oldlen
= strlen(old_dir
);
2247 if (*new_dir
== '\0')
2249 * If someone renamed/merged a subdirectory into the root
2250 * directory (e.g. 'some/subdir' -> ''), then we want to
2253 * as the rename; we need to make old_path + oldlen advance
2254 * past the '/' character.
2257 new_dir_len
= strlen(new_dir
);
2258 newlen
= new_dir_len
+ (strlen(old_path
) - oldlen
) + 1;
2259 strbuf_grow(&new_path
, newlen
);
2260 strbuf_add(&new_path
, new_dir
, new_dir_len
);
2261 strbuf_addstr(&new_path
, &old_path
[oldlen
]);
2263 return strbuf_detach(&new_path
, NULL
);
2266 static int path_in_way(struct strmap
*paths
, const char *path
, unsigned side_mask
)
2268 struct merged_info
*mi
= strmap_get(paths
, path
);
2269 struct conflict_info
*ci
;
2272 INITIALIZE_CI(ci
, mi
);
2273 return mi
->clean
|| (side_mask
& (ci
->filemask
| ci
->dirmask
));
2277 * See if there is a directory rename for path, and if there are any file
2278 * level conflicts on the given side for the renamed location. If there is
2279 * a rename and there are no conflicts, return the new name. Otherwise,
2282 static char *handle_path_level_conflicts(struct merge_options
*opt
,
2284 unsigned side_index
,
2285 struct strmap_entry
*rename_info
,
2286 struct strmap
*collisions
)
2288 char *new_path
= NULL
;
2289 struct collision_info
*c_info
;
2291 struct strbuf collision_paths
= STRBUF_INIT
;
2294 * entry has the mapping of old directory name to new directory name
2295 * that we want to apply to path.
2297 new_path
= apply_dir_rename(rename_info
, path
);
2299 BUG("Failed to apply directory rename!");
2302 * The caller needs to have ensured that it has pre-populated
2303 * collisions with all paths that map to new_path. Do a quick check
2304 * to ensure that's the case.
2306 c_info
= strmap_get(collisions
, new_path
);
2308 BUG("c_info is NULL");
2311 * Check for one-sided add/add/.../add conflicts, i.e.
2312 * where implicit renames from the other side doing
2313 * directory rename(s) can affect this side of history
2314 * to put multiple paths into the same location. Warn
2315 * and bail on directory renames for such paths.
2317 if (c_info
->reported_already
) {
2319 } else if (path_in_way(&opt
->priv
->paths
, new_path
, 1 << side_index
)) {
2320 c_info
->reported_already
= 1;
2321 strbuf_add_separated_string_list(&collision_paths
, ", ",
2322 &c_info
->source_files
);
2323 path_msg(opt
, CONFLICT_DIR_RENAME_FILE_IN_WAY
, 0,
2324 new_path
, NULL
, NULL
, &c_info
->source_files
,
2325 _("CONFLICT (implicit dir rename): Existing "
2326 "file/dir at %s in the way of implicit "
2327 "directory rename(s) putting the following "
2328 "path(s) there: %s."),
2329 new_path
, collision_paths
.buf
);
2331 } else if (c_info
->source_files
.nr
> 1) {
2332 c_info
->reported_already
= 1;
2333 strbuf_add_separated_string_list(&collision_paths
, ", ",
2334 &c_info
->source_files
);
2335 path_msg(opt
, CONFLICT_DIR_RENAME_COLLISION
, 0,
2336 new_path
, NULL
, NULL
, &c_info
->source_files
,
2337 _("CONFLICT (implicit dir rename): Cannot map "
2338 "more than one path to %s; implicit directory "
2339 "renames tried to put these paths there: %s"),
2340 new_path
, collision_paths
.buf
);
2344 /* Free memory we no longer need */
2345 strbuf_release(&collision_paths
);
2346 if (!clean
&& new_path
) {
2354 static void get_provisional_directory_renames(struct merge_options
*opt
,
2358 struct hashmap_iter iter
;
2359 struct strmap_entry
*entry
;
2360 struct rename_info
*renames
= &opt
->priv
->renames
;
2364 * dir_rename_count: old_directory -> {new_directory -> count}
2366 * dir_renames: old_directory -> best_new_directory
2367 * where best_new_directory is the one with the unique highest count.
2369 strmap_for_each_entry(&renames
->dir_rename_count
[side
], &iter
, entry
) {
2370 const char *source_dir
= entry
->key
;
2371 struct strintmap
*counts
= entry
->value
;
2372 struct hashmap_iter count_iter
;
2373 struct strmap_entry
*count_entry
;
2376 const char *best
= NULL
;
2378 strintmap_for_each_entry(counts
, &count_iter
, count_entry
) {
2379 const char *target_dir
= count_entry
->key
;
2380 intptr_t count
= (intptr_t)count_entry
->value
;
2384 else if (count
> max
) {
2393 if (bad_max
== max
) {
2394 path_msg(opt
, CONFLICT_DIR_RENAME_SPLIT
, 0,
2395 source_dir
, NULL
, NULL
, NULL
,
2396 _("CONFLICT (directory rename split): "
2397 "Unclear where to rename %s to; it was "
2398 "renamed to multiple other directories, "
2399 "with no destination getting a majority of "
2404 strmap_put(&renames
->dir_renames
[side
],
2405 source_dir
, (void*)best
);
2410 static void handle_directory_level_conflicts(struct merge_options
*opt
)
2412 struct hashmap_iter iter
;
2413 struct strmap_entry
*entry
;
2414 struct string_list duplicated
= STRING_LIST_INIT_NODUP
;
2415 struct rename_info
*renames
= &opt
->priv
->renames
;
2416 struct strmap
*side1_dir_renames
= &renames
->dir_renames
[MERGE_SIDE1
];
2417 struct strmap
*side2_dir_renames
= &renames
->dir_renames
[MERGE_SIDE2
];
2420 strmap_for_each_entry(side1_dir_renames
, &iter
, entry
) {
2421 if (strmap_contains(side2_dir_renames
, entry
->key
))
2422 string_list_append(&duplicated
, entry
->key
);
2425 for (i
= 0; i
< duplicated
.nr
; i
++) {
2426 strmap_remove(side1_dir_renames
, duplicated
.items
[i
].string
, 0);
2427 strmap_remove(side2_dir_renames
, duplicated
.items
[i
].string
, 0);
2429 string_list_clear(&duplicated
, 0);
2432 static struct strmap_entry
*check_dir_renamed(const char *path
,
2433 struct strmap
*dir_renames
)
2435 char *temp
= xstrdup(path
);
2437 struct strmap_entry
*e
= NULL
;
2439 while ((end
= strrchr(temp
, '/'))) {
2441 e
= strmap_get_entry(dir_renames
, temp
);
2449 static void compute_collisions(struct strmap
*collisions
,
2450 struct strmap
*dir_renames
,
2451 struct diff_queue_struct
*pairs
)
2455 strmap_init_with_options(collisions
, NULL
, 0);
2456 if (strmap_empty(dir_renames
))
2460 * Multiple files can be mapped to the same path due to directory
2461 * renames done by the other side of history. Since that other
2462 * side of history could have merged multiple directories into one,
2463 * if our side of history added the same file basename to each of
2464 * those directories, then all N of them would get implicitly
2465 * renamed by the directory rename detection into the same path,
2466 * and we'd get an add/add/.../add conflict, and all those adds
2467 * from *this* side of history. This is not representable in the
2468 * index, and users aren't going to easily be able to make sense of
2469 * it. So we need to provide a good warning about what's
2470 * happening, and fall back to no-directory-rename detection
2471 * behavior for those paths.
2473 * See testcases 9e and all of section 5 from t6043 for examples.
2475 for (i
= 0; i
< pairs
->nr
; ++i
) {
2476 struct strmap_entry
*rename_info
;
2477 struct collision_info
*collision_info
;
2479 struct diff_filepair
*pair
= pairs
->queue
[i
];
2481 if (pair
->status
!= 'A' && pair
->status
!= 'R')
2483 rename_info
= check_dir_renamed(pair
->two
->path
, dir_renames
);
2487 new_path
= apply_dir_rename(rename_info
, pair
->two
->path
);
2489 collision_info
= strmap_get(collisions
, new_path
);
2490 if (collision_info
) {
2493 CALLOC_ARRAY(collision_info
, 1);
2494 string_list_init_nodup(&collision_info
->source_files
);
2495 strmap_put(collisions
, new_path
, collision_info
);
2497 string_list_insert(&collision_info
->source_files
,
2502 static void free_collisions(struct strmap
*collisions
)
2504 struct hashmap_iter iter
;
2505 struct strmap_entry
*entry
;
2507 /* Free each value in the collisions map */
2508 strmap_for_each_entry(collisions
, &iter
, entry
) {
2509 struct collision_info
*info
= entry
->value
;
2510 string_list_clear(&info
->source_files
, 0);
2513 * In compute_collisions(), we set collisions.strdup_strings to 0
2514 * so that we wouldn't have to make another copy of the new_path
2515 * allocated by apply_dir_rename(). But now that we've used them
2516 * and have no other references to these strings, it is time to
2519 free_strmap_strings(collisions
);
2520 strmap_clear(collisions
, 1);
2523 static char *check_for_directory_rename(struct merge_options
*opt
,
2525 unsigned side_index
,
2526 struct strmap
*dir_renames
,
2527 struct strmap
*dir_rename_exclusions
,
2528 struct strmap
*collisions
,
2532 struct strmap_entry
*rename_info
;
2533 struct strmap_entry
*otherinfo
;
2534 const char *new_dir
;
2535 int other_side
= 3 - side_index
;
2538 * Cases where we don't have or don't want a directory rename for
2541 if (strmap_empty(dir_renames
))
2543 if (strmap_get(&collisions
[other_side
], path
))
2545 rename_info
= check_dir_renamed(path
, dir_renames
);
2550 * This next part is a little weird. We do not want to do an
2551 * implicit rename into a directory we renamed on our side, because
2552 * that will result in a spurious rename/rename(1to2) conflict. An
2554 * Base commit: dumbdir/afile, otherdir/bfile
2555 * Side 1: smrtdir/afile, otherdir/bfile
2556 * Side 2: dumbdir/afile, dumbdir/bfile
2557 * Here, while working on Side 1, we could notice that otherdir was
2558 * renamed/merged to dumbdir, and change the diff_filepair for
2559 * otherdir/bfile into a rename into dumbdir/bfile. However, Side
2560 * 2 will notice the rename from dumbdir to smrtdir, and do the
2561 * transitive rename to move it from dumbdir/bfile to
2562 * smrtdir/bfile. That gives us bfile in dumbdir vs being in
2563 * smrtdir, a rename/rename(1to2) conflict. We really just want
2564 * the file to end up in smrtdir. And the way to achieve that is
2565 * to not let Side1 do the rename to dumbdir, since we know that is
2566 * the source of one of our directory renames.
2568 * That's why otherinfo and dir_rename_exclusions is here.
2570 * As it turns out, this also prevents N-way transient rename
2571 * confusion; See testcases 9c and 9d of t6043.
2573 new_dir
= rename_info
->value
; /* old_dir = rename_info->key; */
2574 otherinfo
= strmap_get_entry(dir_rename_exclusions
, new_dir
);
2576 path_msg(opt
, INFO_DIR_RENAME_SKIPPED_DUE_TO_RERENAME
, 1,
2577 rename_info
->key
, path
, new_dir
, NULL
,
2578 _("WARNING: Avoiding applying %s -> %s rename "
2579 "to %s, because %s itself was renamed."),
2580 rename_info
->key
, new_dir
, path
, new_dir
);
2584 new_path
= handle_path_level_conflicts(opt
, path
, side_index
,
2586 &collisions
[side_index
]);
2587 *clean_merge
&= (new_path
!= NULL
);
2592 static void apply_directory_rename_modifications(struct merge_options
*opt
,
2593 struct diff_filepair
*pair
,
2597 * The basic idea is to get the conflict_info from opt->priv->paths
2598 * at old path, and insert it into new_path; basically just this:
2599 * ci = strmap_get(&opt->priv->paths, old_path);
2600 * strmap_remove(&opt->priv->paths, old_path, 0);
2601 * strmap_put(&opt->priv->paths, new_path, ci);
2602 * However, there are some factors complicating this:
2603 * - opt->priv->paths may already have an entry at new_path
2604 * - Each ci tracks its containing directory, so we need to
2606 * - If another ci has the same containing directory, then
2607 * the two char*'s MUST point to the same location. See the
2608 * comment in struct merged_info. strcmp equality is not
2609 * enough; we need pointer equality.
2610 * - opt->priv->paths must hold the parent directories of any
2611 * entries that are added. So, if this directory rename
2612 * causes entirely new directories, we must recursively add
2613 * parent directories.
2614 * - For each parent directory added to opt->priv->paths, we
2615 * also need to get its parent directory stored in its
2616 * conflict_info->merged.directory_name with all the same
2617 * requirements about pointer equality.
2619 struct string_list dirs_to_insert
= STRING_LIST_INIT_NODUP
;
2620 struct conflict_info
*ci
, *new_ci
;
2621 struct strmap_entry
*entry
;
2622 const char *branch_with_new_path
, *branch_with_dir_rename
;
2623 const char *old_path
= pair
->two
->path
;
2624 const char *parent_name
;
2625 const char *cur_path
;
2628 entry
= strmap_get_entry(&opt
->priv
->paths
, old_path
);
2629 old_path
= entry
->key
;
2633 /* Find parent directories missing from opt->priv->paths */
2634 cur_path
= mem_pool_strdup(&opt
->priv
->pool
, new_path
);
2635 free((char*)new_path
);
2636 new_path
= (char *)cur_path
;
2639 /* Find the parent directory of cur_path */
2640 char *last_slash
= strrchr(cur_path
, '/');
2642 parent_name
= mem_pool_strndup(&opt
->priv
->pool
,
2644 last_slash
- cur_path
);
2646 parent_name
= opt
->priv
->toplevel_dir
;
2650 /* Look it up in opt->priv->paths */
2651 entry
= strmap_get_entry(&opt
->priv
->paths
, parent_name
);
2653 parent_name
= entry
->key
; /* reuse known pointer */
2657 /* Record this is one of the directories we need to insert */
2658 string_list_append(&dirs_to_insert
, parent_name
);
2659 cur_path
= parent_name
;
2662 /* Traverse dirs_to_insert and insert them into opt->priv->paths */
2663 for (i
= dirs_to_insert
.nr
-1; i
>= 0; --i
) {
2664 struct conflict_info
*dir_ci
;
2665 char *cur_dir
= dirs_to_insert
.items
[i
].string
;
2667 CALLOC_ARRAY(dir_ci
, 1);
2669 dir_ci
->merged
.directory_name
= parent_name
;
2670 len
= strlen(parent_name
);
2671 /* len+1 because of trailing '/' character */
2672 dir_ci
->merged
.basename_offset
= (len
> 0 ? len
+1 : len
);
2673 dir_ci
->dirmask
= ci
->filemask
;
2674 strmap_put(&opt
->priv
->paths
, cur_dir
, dir_ci
);
2676 parent_name
= cur_dir
;
2679 assert(ci
->filemask
== 2 || ci
->filemask
== 4);
2680 assert(ci
->dirmask
== 0 || ci
->dirmask
== 1);
2681 if (ci
->dirmask
== 0)
2682 strmap_remove(&opt
->priv
->paths
, old_path
, 0);
2685 * This file exists on one side, but we still had a directory
2686 * at the old location that we can't remove until after
2687 * processing all paths below it. So, make a copy of ci in
2688 * new_ci and only put the file information into it.
2690 new_ci
= mem_pool_calloc(&opt
->priv
->pool
, 1, sizeof(*new_ci
));
2691 memcpy(new_ci
, ci
, sizeof(*ci
));
2692 assert(!new_ci
->match_mask
);
2693 new_ci
->dirmask
= 0;
2694 new_ci
->stages
[1].mode
= 0;
2695 oidcpy(&new_ci
->stages
[1].oid
, null_oid());
2698 * Now that we have the file information in new_ci, make sure
2699 * ci only has the directory information.
2702 ci
->merged
.clean
= 1;
2703 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
2704 if (ci
->dirmask
& (1 << i
))
2706 /* zero out any entries related to files */
2707 ci
->stages
[i
].mode
= 0;
2708 oidcpy(&ci
->stages
[i
].oid
, null_oid());
2711 /* Now we want to focus on new_ci, so reassign ci to it. */
2715 branch_with_new_path
= (ci
->filemask
== 2) ? opt
->branch1
: opt
->branch2
;
2716 branch_with_dir_rename
= (ci
->filemask
== 2) ? opt
->branch2
: opt
->branch1
;
2718 /* Now, finally update ci and stick it into opt->priv->paths */
2719 ci
->merged
.directory_name
= parent_name
;
2720 len
= strlen(parent_name
);
2721 ci
->merged
.basename_offset
= (len
> 0 ? len
+1 : len
);
2722 new_ci
= strmap_get(&opt
->priv
->paths
, new_path
);
2724 /* Place ci back into opt->priv->paths, but at new_path */
2725 strmap_put(&opt
->priv
->paths
, new_path
, ci
);
2729 /* A few sanity checks */
2731 assert(ci
->filemask
== 2 || ci
->filemask
== 4);
2732 assert((new_ci
->filemask
& ci
->filemask
) == 0);
2733 assert(!new_ci
->merged
.clean
);
2735 /* Copy stuff from ci into new_ci */
2736 new_ci
->filemask
|= ci
->filemask
;
2737 if (new_ci
->dirmask
)
2738 new_ci
->df_conflict
= 1;
2739 index
= (ci
->filemask
>> 1);
2740 new_ci
->pathnames
[index
] = ci
->pathnames
[index
];
2741 new_ci
->stages
[index
].mode
= ci
->stages
[index
].mode
;
2742 oidcpy(&new_ci
->stages
[index
].oid
, &ci
->stages
[index
].oid
);
2747 if (opt
->detect_directory_renames
== MERGE_DIRECTORY_RENAMES_TRUE
) {
2748 /* Notify user of updated path */
2749 if (pair
->status
== 'A')
2750 path_msg(opt
, INFO_DIR_RENAME_APPLIED
, 1,
2751 new_path
, old_path
, NULL
, NULL
,
2752 _("Path updated: %s added in %s inside a "
2753 "directory that was renamed in %s; moving "
2755 old_path
, branch_with_new_path
,
2756 branch_with_dir_rename
, new_path
);
2758 path_msg(opt
, INFO_DIR_RENAME_APPLIED
, 1,
2759 new_path
, old_path
, NULL
, NULL
,
2760 _("Path updated: %s renamed to %s in %s, "
2761 "inside a directory that was renamed in %s; "
2762 "moving it to %s."),
2763 pair
->one
->path
, old_path
, branch_with_new_path
,
2764 branch_with_dir_rename
, new_path
);
2767 * opt->detect_directory_renames has the value
2768 * MERGE_DIRECTORY_RENAMES_CONFLICT, so mark these as conflicts.
2770 ci
->path_conflict
= 1;
2771 if (pair
->status
== 'A')
2772 path_msg(opt
, CONFLICT_DIR_RENAME_SUGGESTED
, 1,
2773 new_path
, old_path
, NULL
, NULL
,
2774 _("CONFLICT (file location): %s added in %s "
2775 "inside a directory that was renamed in %s, "
2776 "suggesting it should perhaps be moved to "
2778 old_path
, branch_with_new_path
,
2779 branch_with_dir_rename
, new_path
);
2781 path_msg(opt
, CONFLICT_DIR_RENAME_SUGGESTED
, 1,
2782 new_path
, old_path
, NULL
, NULL
,
2783 _("CONFLICT (file location): %s renamed to %s "
2784 "in %s, inside a directory that was renamed "
2785 "in %s, suggesting it should perhaps be "
2787 pair
->one
->path
, old_path
, branch_with_new_path
,
2788 branch_with_dir_rename
, new_path
);
2792 * Finally, record the new location.
2794 pair
->two
->path
= new_path
;
2797 /*** Function Grouping: functions related to regular rename detection ***/
2799 static int process_renames(struct merge_options
*opt
,
2800 struct diff_queue_struct
*renames
)
2802 int clean_merge
= 1, i
;
2804 for (i
= 0; i
< renames
->nr
; ++i
) {
2805 const char *oldpath
= NULL
, *newpath
;
2806 struct diff_filepair
*pair
= renames
->queue
[i
];
2807 struct conflict_info
*oldinfo
= NULL
, *newinfo
= NULL
;
2808 struct strmap_entry
*old_ent
, *new_ent
;
2809 unsigned int old_sidemask
;
2810 int target_index
, other_source_index
;
2811 int source_deleted
, collision
, type_changed
;
2812 const char *rename_branch
= NULL
, *delete_branch
= NULL
;
2814 old_ent
= strmap_get_entry(&opt
->priv
->paths
, pair
->one
->path
);
2815 new_ent
= strmap_get_entry(&opt
->priv
->paths
, pair
->two
->path
);
2817 oldpath
= old_ent
->key
;
2818 oldinfo
= old_ent
->value
;
2820 newpath
= pair
->two
->path
;
2822 newpath
= new_ent
->key
;
2823 newinfo
= new_ent
->value
;
2827 * If pair->one->path isn't in opt->priv->paths, that means
2828 * that either directory rename detection removed that
2829 * path, or a parent directory of oldpath was resolved and
2830 * we don't even need the rename; in either case, we can
2831 * skip it. If oldinfo->merged.clean, then the other side
2832 * of history had no changes to oldpath and we don't need
2833 * the rename and can skip it.
2835 if (!oldinfo
|| oldinfo
->merged
.clean
)
2839 * diff_filepairs have copies of pathnames, thus we have to
2840 * use standard 'strcmp()' (negated) instead of '=='.
2842 if (i
+ 1 < renames
->nr
&&
2843 !strcmp(oldpath
, renames
->queue
[i
+1]->one
->path
)) {
2844 /* Handle rename/rename(1to2) or rename/rename(1to1) */
2845 const char *pathnames
[3];
2846 struct version_info merged
;
2847 struct conflict_info
*base
, *side1
, *side2
;
2848 unsigned was_binary_blob
= 0;
2850 pathnames
[0] = oldpath
;
2851 pathnames
[1] = newpath
;
2852 pathnames
[2] = renames
->queue
[i
+1]->two
->path
;
2854 base
= strmap_get(&opt
->priv
->paths
, pathnames
[0]);
2855 side1
= strmap_get(&opt
->priv
->paths
, pathnames
[1]);
2856 side2
= strmap_get(&opt
->priv
->paths
, pathnames
[2]);
2862 if (!strcmp(pathnames
[1], pathnames
[2])) {
2863 struct rename_info
*ri
= &opt
->priv
->renames
;
2866 /* Both sides renamed the same way */
2867 assert(side1
== side2
);
2868 memcpy(&side1
->stages
[0], &base
->stages
[0],
2870 side1
->filemask
|= (1 << MERGE_BASE
);
2871 /* Mark base as resolved by removal */
2872 base
->merged
.is_null
= 1;
2873 base
->merged
.clean
= 1;
2876 * Disable remembering renames optimization;
2877 * rename/rename(1to1) is incredibly rare, and
2878 * just disabling the optimization is easier
2879 * than purging cached_pairs,
2880 * cached_target_names, and dir_rename_counts.
2882 for (j
= 0; j
< 3; j
++)
2883 ri
->merge_trees
[j
] = NULL
;
2885 /* We handled both renames, i.e. i+1 handled */
2887 /* Move to next rename */
2891 /* This is a rename/rename(1to2) */
2892 clean_merge
= handle_content_merge(opt
,
2898 1 + 2 * opt
->priv
->call_depth
,
2900 if (clean_merge
< 0)
2903 merged
.mode
== side1
->stages
[1].mode
&&
2904 oideq(&merged
.oid
, &side1
->stages
[1].oid
))
2905 was_binary_blob
= 1;
2906 memcpy(&side1
->stages
[1], &merged
, sizeof(merged
));
2907 if (was_binary_blob
) {
2909 * Getting here means we were attempting to
2910 * merge a binary blob.
2912 * Since we can't merge binaries,
2913 * handle_content_merge() just takes one
2914 * side. But we don't want to copy the
2915 * contents of one side to both paths. We
2916 * used the contents of side1 above for
2917 * side1->stages, let's use the contents of
2918 * side2 for side2->stages below.
2920 oidcpy(&merged
.oid
, &side2
->stages
[2].oid
);
2921 merged
.mode
= side2
->stages
[2].mode
;
2923 memcpy(&side2
->stages
[2], &merged
, sizeof(merged
));
2925 side1
->path_conflict
= 1;
2926 side2
->path_conflict
= 1;
2928 * TODO: For renames we normally remove the path at the
2929 * old name. It would thus seem consistent to do the
2930 * same for rename/rename(1to2) cases, but we haven't
2931 * done so traditionally and a number of the regression
2932 * tests now encode an expectation that the file is
2933 * left there at stage 1. If we ever decide to change
2934 * this, add the following two lines here:
2935 * base->merged.is_null = 1;
2936 * base->merged.clean = 1;
2937 * and remove the setting of base->path_conflict to 1.
2939 base
->path_conflict
= 1;
2940 path_msg(opt
, CONFLICT_RENAME_RENAME
, 0,
2941 pathnames
[0], pathnames
[1], pathnames
[2], NULL
,
2942 _("CONFLICT (rename/rename): %s renamed to "
2943 "%s in %s and to %s in %s."),
2945 pathnames
[1], opt
->branch1
,
2946 pathnames
[2], opt
->branch2
);
2948 i
++; /* We handled both renames, i.e. i+1 handled */
2954 target_index
= pair
->score
; /* from collect_renames() */
2955 assert(target_index
== 1 || target_index
== 2);
2956 other_source_index
= 3 - target_index
;
2957 old_sidemask
= (1 << other_source_index
); /* 2 or 4 */
2958 source_deleted
= (oldinfo
->filemask
== 1);
2959 collision
= ((newinfo
->filemask
& old_sidemask
) != 0);
2960 type_changed
= !source_deleted
&&
2961 (S_ISREG(oldinfo
->stages
[other_source_index
].mode
) !=
2962 S_ISREG(newinfo
->stages
[target_index
].mode
));
2963 if (type_changed
&& collision
) {
2965 * special handling so later blocks can handle this...
2967 * if type_changed && collision are both true, then this
2968 * was really a double rename, but one side wasn't
2969 * detected due to lack of break detection. I.e.
2971 * orig: has normal file 'foo'
2972 * side1: renames 'foo' to 'bar', adds 'foo' symlink
2973 * side2: renames 'foo' to 'bar'
2974 * In this case, the foo->bar rename on side1 won't be
2975 * detected because the new symlink named 'foo' is
2976 * there and we don't do break detection. But we detect
2977 * this here because we don't want to merge the content
2978 * of the foo symlink with the foo->bar file, so we
2979 * have some logic to handle this special case. The
2980 * easiest way to do that is make 'bar' on side1 not
2981 * be considered a colliding file but the other part
2982 * of a normal rename. If the file is very different,
2983 * well we're going to get content merge conflicts
2984 * anyway so it doesn't hurt. And if the colliding
2985 * file also has a different type, that'll be handled
2986 * by the content merge logic in process_entry() too.
2988 * See also t6430, 'rename vs. rename/symlink'
2992 if (source_deleted
) {
2993 if (target_index
== 1) {
2994 rename_branch
= opt
->branch1
;
2995 delete_branch
= opt
->branch2
;
2997 rename_branch
= opt
->branch2
;
2998 delete_branch
= opt
->branch1
;
3002 assert(source_deleted
|| oldinfo
->filemask
& old_sidemask
);
3004 /* Need to check for special types of rename conflicts... */
3005 if (collision
&& !source_deleted
) {
3006 /* collision: rename/add or rename/rename(2to1) */
3007 const char *pathnames
[3];
3008 struct version_info merged
;
3010 struct conflict_info
*base
, *side1
, *side2
;
3013 pathnames
[0] = oldpath
;
3014 pathnames
[other_source_index
] = oldpath
;
3015 pathnames
[target_index
] = newpath
;
3017 base
= strmap_get(&opt
->priv
->paths
, pathnames
[0]);
3018 side1
= strmap_get(&opt
->priv
->paths
, pathnames
[1]);
3019 side2
= strmap_get(&opt
->priv
->paths
, pathnames
[2]);
3025 clean
= handle_content_merge(opt
, pair
->one
->path
,
3030 1 + 2 * opt
->priv
->call_depth
,
3035 memcpy(&newinfo
->stages
[target_index
], &merged
,
3038 path_msg(opt
, CONFLICT_RENAME_COLLIDES
, 0,
3039 newpath
, oldpath
, NULL
, NULL
,
3040 _("CONFLICT (rename involved in "
3041 "collision): rename of %s -> %s has "
3042 "content conflicts AND collides "
3043 "with another path; this may result "
3044 "in nested conflict markers."),
3047 } else if (collision
&& source_deleted
) {
3049 * rename/add/delete or rename/rename(2to1)/delete:
3050 * since oldpath was deleted on the side that didn't
3051 * do the rename, there's not much of a content merge
3052 * we can do for the rename. oldinfo->merged.is_null
3053 * was already set, so we just leave things as-is so
3054 * they look like an add/add conflict.
3057 newinfo
->path_conflict
= 1;
3058 path_msg(opt
, CONFLICT_RENAME_DELETE
, 0,
3059 newpath
, oldpath
, NULL
, NULL
,
3060 _("CONFLICT (rename/delete): %s renamed "
3061 "to %s in %s, but deleted in %s."),
3062 oldpath
, newpath
, rename_branch
, delete_branch
);
3065 * a few different cases...start by copying the
3066 * existing stage(s) from oldinfo over the newinfo
3067 * and update the pathname(s).
3069 memcpy(&newinfo
->stages
[0], &oldinfo
->stages
[0],
3070 sizeof(newinfo
->stages
[0]));
3071 newinfo
->filemask
|= (1 << MERGE_BASE
);
3072 newinfo
->pathnames
[0] = oldpath
;
3074 /* rename vs. typechange */
3075 /* Mark the original as resolved by removal */
3076 memcpy(&oldinfo
->stages
[0].oid
, null_oid(),
3077 sizeof(oldinfo
->stages
[0].oid
));
3078 oldinfo
->stages
[0].mode
= 0;
3079 oldinfo
->filemask
&= 0x06;
3080 } else if (source_deleted
) {
3082 newinfo
->path_conflict
= 1;
3083 path_msg(opt
, CONFLICT_RENAME_DELETE
, 0,
3084 newpath
, oldpath
, NULL
, NULL
,
3085 _("CONFLICT (rename/delete): %s renamed"
3086 " to %s in %s, but deleted in %s."),
3088 rename_branch
, delete_branch
);
3091 memcpy(&newinfo
->stages
[other_source_index
],
3092 &oldinfo
->stages
[other_source_index
],
3093 sizeof(newinfo
->stages
[0]));
3094 newinfo
->filemask
|= (1 << other_source_index
);
3095 newinfo
->pathnames
[other_source_index
] = oldpath
;
3099 if (!type_changed
) {
3100 /* Mark the original as resolved by removal */
3101 oldinfo
->merged
.is_null
= 1;
3102 oldinfo
->merged
.clean
= 1;
3110 static inline int possible_side_renames(struct rename_info
*renames
,
3111 unsigned side_index
)
3113 return renames
->pairs
[side_index
].nr
> 0 &&
3114 !strintmap_empty(&renames
->relevant_sources
[side_index
]);
3117 static inline int possible_renames(struct rename_info
*renames
)
3119 return possible_side_renames(renames
, 1) ||
3120 possible_side_renames(renames
, 2) ||
3121 !strmap_empty(&renames
->cached_pairs
[1]) ||
3122 !strmap_empty(&renames
->cached_pairs
[2]);
3125 static void resolve_diffpair_statuses(struct diff_queue_struct
*q
)
3128 * A simplified version of diff_resolve_rename_copy(); would probably
3129 * just use that function but it's static...
3132 struct diff_filepair
*p
;
3134 for (i
= 0; i
< q
->nr
; ++i
) {
3136 p
->status
= 0; /* undecided */
3137 if (!DIFF_FILE_VALID(p
->one
))
3138 p
->status
= DIFF_STATUS_ADDED
;
3139 else if (!DIFF_FILE_VALID(p
->two
))
3140 p
->status
= DIFF_STATUS_DELETED
;
3141 else if (DIFF_PAIR_RENAME(p
))
3142 p
->status
= DIFF_STATUS_RENAMED
;
3146 static void prune_cached_from_relevant(struct rename_info
*renames
,
3149 /* Reason for this function described in add_pair() */
3150 struct hashmap_iter iter
;
3151 struct strmap_entry
*entry
;
3153 /* Remove from relevant_sources all entries in cached_pairs[side] */
3154 strmap_for_each_entry(&renames
->cached_pairs
[side
], &iter
, entry
) {
3155 strintmap_remove(&renames
->relevant_sources
[side
],
3158 /* Remove from relevant_sources all entries in cached_irrelevant[side] */
3159 strset_for_each_entry(&renames
->cached_irrelevant
[side
], &iter
, entry
) {
3160 strintmap_remove(&renames
->relevant_sources
[side
],
3165 static void use_cached_pairs(struct merge_options
*opt
,
3166 struct strmap
*cached_pairs
,
3167 struct diff_queue_struct
*pairs
)
3169 struct hashmap_iter iter
;
3170 struct strmap_entry
*entry
;
3173 * Add to side_pairs all entries from renames->cached_pairs[side_index].
3174 * (Info in cached_irrelevant[side_index] is not relevant here.)
3176 strmap_for_each_entry(cached_pairs
, &iter
, entry
) {
3177 struct diff_filespec
*one
, *two
;
3178 const char *old_name
= entry
->key
;
3179 const char *new_name
= entry
->value
;
3181 new_name
= old_name
;
3184 * cached_pairs has *copies* of old_name and new_name,
3185 * because it has to persist across merges. Since
3186 * pool_alloc_filespec() will just re-use the existing
3187 * filenames, which will also get re-used by
3188 * opt->priv->paths if they become renames, and then
3189 * get freed at the end of the merge, that would leave
3190 * the copy in cached_pairs dangling. Avoid this by
3191 * making a copy here.
3193 old_name
= mem_pool_strdup(&opt
->priv
->pool
, old_name
);
3194 new_name
= mem_pool_strdup(&opt
->priv
->pool
, new_name
);
3196 /* We don't care about oid/mode, only filenames and status */
3197 one
= pool_alloc_filespec(&opt
->priv
->pool
, old_name
);
3198 two
= pool_alloc_filespec(&opt
->priv
->pool
, new_name
);
3199 pool_diff_queue(&opt
->priv
->pool
, pairs
, one
, two
);
3200 pairs
->queue
[pairs
->nr
-1]->status
= entry
->value
? 'R' : 'D';
3204 static void cache_new_pair(struct rename_info
*renames
,
3211 new_path
= xstrdup(new_path
);
3212 old_value
= strmap_put(&renames
->cached_pairs
[side
],
3213 old_path
, new_path
);
3214 strset_add(&renames
->cached_target_names
[side
], new_path
);
3221 static void possibly_cache_new_pair(struct rename_info
*renames
,
3222 struct diff_filepair
*p
,
3226 int dir_renamed_side
= 0;
3230 * Directory renames happen on the other side of history from
3231 * the side that adds new files to the old directory.
3233 dir_renamed_side
= 3 - side
;
3235 int val
= strintmap_get(&renames
->relevant_sources
[side
],
3237 if (val
== RELEVANT_NO_MORE
) {
3238 assert(p
->status
== 'D');
3239 strset_add(&renames
->cached_irrelevant
[side
],
3246 if (p
->status
== 'D') {
3248 * If we already had this delete, we'll just set it's value
3249 * to NULL again, so no harm.
3251 strmap_put(&renames
->cached_pairs
[side
], p
->one
->path
, NULL
);
3252 } else if (p
->status
== 'R') {
3254 new_path
= p
->two
->path
;
3256 cache_new_pair(renames
, dir_renamed_side
,
3257 p
->two
->path
, new_path
, 0);
3258 cache_new_pair(renames
, side
, p
->one
->path
, new_path
, 1);
3259 } else if (p
->status
== 'A' && new_path
) {
3260 cache_new_pair(renames
, dir_renamed_side
,
3261 p
->two
->path
, new_path
, 0);
3265 static int compare_pairs(const void *a_
, const void *b_
)
3267 const struct diff_filepair
*a
= *((const struct diff_filepair
**)a_
);
3268 const struct diff_filepair
*b
= *((const struct diff_filepair
**)b_
);
3270 return strcmp(a
->one
->path
, b
->one
->path
);
3273 /* Call diffcore_rename() to update deleted/added pairs into rename pairs */
3274 static int detect_regular_renames(struct merge_options
*opt
,
3275 unsigned side_index
)
3277 struct diff_options diff_opts
;
3278 struct rename_info
*renames
= &opt
->priv
->renames
;
3280 prune_cached_from_relevant(renames
, side_index
);
3281 if (!possible_side_renames(renames
, side_index
)) {
3283 * No rename detection needed for this side, but we still need
3284 * to make sure 'adds' are marked correctly in case the other
3285 * side had directory renames.
3287 resolve_diffpair_statuses(&renames
->pairs
[side_index
]);
3291 partial_clear_dir_rename_count(&renames
->dir_rename_count
[side_index
]);
3292 repo_diff_setup(opt
->repo
, &diff_opts
);
3293 diff_opts
.flags
.recursive
= 1;
3294 diff_opts
.flags
.rename_empty
= 0;
3295 diff_opts
.detect_rename
= DIFF_DETECT_RENAME
;
3296 diff_opts
.rename_limit
= opt
->rename_limit
;
3297 if (opt
->rename_limit
<= 0)
3298 diff_opts
.rename_limit
= 7000;
3299 diff_opts
.rename_score
= opt
->rename_score
;
3300 diff_opts
.show_rename_progress
= opt
->show_rename_progress
;
3301 diff_opts
.output_format
= DIFF_FORMAT_NO_OUTPUT
;
3302 diff_setup_done(&diff_opts
);
3304 diff_queued_diff
= renames
->pairs
[side_index
];
3305 trace2_region_enter("diff", "diffcore_rename", opt
->repo
);
3306 diffcore_rename_extended(&diff_opts
,
3308 &renames
->relevant_sources
[side_index
],
3309 &renames
->dirs_removed
[side_index
],
3310 &renames
->dir_rename_count
[side_index
],
3311 &renames
->cached_pairs
[side_index
]);
3312 trace2_region_leave("diff", "diffcore_rename", opt
->repo
);
3313 resolve_diffpair_statuses(&diff_queued_diff
);
3315 if (diff_opts
.needed_rename_limit
> 0)
3316 renames
->redo_after_renames
= 0;
3317 if (diff_opts
.needed_rename_limit
> renames
->needed_limit
)
3318 renames
->needed_limit
= diff_opts
.needed_rename_limit
;
3320 renames
->pairs
[side_index
] = diff_queued_diff
;
3322 diff_opts
.output_format
= DIFF_FORMAT_NO_OUTPUT
;
3323 diff_queued_diff
.nr
= 0;
3324 diff_queued_diff
.queue
= NULL
;
3325 diff_flush(&diff_opts
);
3331 * Get information of all renames which occurred in 'side_pairs', making use
3332 * of any implicit directory renames in side_dir_renames (also making use of
3333 * implicit directory renames rename_exclusions as needed by
3334 * check_for_directory_rename()). Add all (updated) renames into result.
3336 static int collect_renames(struct merge_options
*opt
,
3337 struct diff_queue_struct
*result
,
3338 unsigned side_index
,
3339 struct strmap
*collisions
,
3340 struct strmap
*dir_renames_for_side
,
3341 struct strmap
*rename_exclusions
)
3344 struct diff_queue_struct
*side_pairs
;
3345 struct rename_info
*renames
= &opt
->priv
->renames
;
3347 side_pairs
= &renames
->pairs
[side_index
];
3349 for (i
= 0; i
< side_pairs
->nr
; ++i
) {
3350 struct diff_filepair
*p
= side_pairs
->queue
[i
];
3351 char *new_path
; /* non-NULL only with directory renames */
3353 if (p
->status
!= 'A' && p
->status
!= 'R') {
3354 possibly_cache_new_pair(renames
, p
, side_index
, NULL
);
3355 pool_diff_free_filepair(&opt
->priv
->pool
, p
);
3359 new_path
= check_for_directory_rename(opt
, p
->two
->path
,
3361 dir_renames_for_side
,
3366 possibly_cache_new_pair(renames
, p
, side_index
, new_path
);
3367 if (p
->status
!= 'R' && !new_path
) {
3368 pool_diff_free_filepair(&opt
->priv
->pool
, p
);
3373 apply_directory_rename_modifications(opt
, p
, new_path
);
3376 * p->score comes back from diffcore_rename_extended() with
3377 * the similarity of the renamed file. The similarity is
3378 * was used to determine that the two files were related
3379 * and are a rename, which we have already used, but beyond
3380 * that we have no use for the similarity. So p->score is
3381 * now irrelevant. However, process_renames() will need to
3382 * know which side of the merge this rename was associated
3383 * with, so overwrite p->score with that value.
3385 p
->score
= side_index
;
3386 result
->queue
[result
->nr
++] = p
;
3392 static int detect_and_process_renames(struct merge_options
*opt
)
3394 struct diff_queue_struct combined
= { 0 };
3395 struct rename_info
*renames
= &opt
->priv
->renames
;
3396 struct strmap collisions
[3];
3397 int need_dir_renames
, s
, i
, clean
= 1;
3398 unsigned detection_run
= 0;
3400 if (!possible_renames(renames
))
3403 trace2_region_enter("merge", "regular renames", opt
->repo
);
3404 detection_run
|= detect_regular_renames(opt
, MERGE_SIDE1
);
3405 detection_run
|= detect_regular_renames(opt
, MERGE_SIDE2
);
3406 if (renames
->needed_limit
) {
3407 renames
->cached_pairs_valid_side
= 0;
3408 renames
->redo_after_renames
= 0;
3410 if (renames
->redo_after_renames
&& detection_run
) {
3412 struct diff_filepair
*p
;
3414 /* Cache the renames, we found */
3415 for (side
= MERGE_SIDE1
; side
<= MERGE_SIDE2
; side
++) {
3416 for (i
= 0; i
< renames
->pairs
[side
].nr
; ++i
) {
3417 p
= renames
->pairs
[side
].queue
[i
];
3418 possibly_cache_new_pair(renames
, p
, side
, NULL
);
3422 /* Restart the merge with the cached renames */
3423 renames
->redo_after_renames
= 2;
3424 trace2_region_leave("merge", "regular renames", opt
->repo
);
3427 use_cached_pairs(opt
, &renames
->cached_pairs
[1], &renames
->pairs
[1]);
3428 use_cached_pairs(opt
, &renames
->cached_pairs
[2], &renames
->pairs
[2]);
3429 trace2_region_leave("merge", "regular renames", opt
->repo
);
3431 trace2_region_enter("merge", "directory renames", opt
->repo
);
3433 !opt
->priv
->call_depth
&&
3434 (opt
->detect_directory_renames
== MERGE_DIRECTORY_RENAMES_TRUE
||
3435 opt
->detect_directory_renames
== MERGE_DIRECTORY_RENAMES_CONFLICT
);
3437 if (need_dir_renames
) {
3438 get_provisional_directory_renames(opt
, MERGE_SIDE1
, &clean
);
3439 get_provisional_directory_renames(opt
, MERGE_SIDE2
, &clean
);
3440 handle_directory_level_conflicts(opt
);
3443 ALLOC_GROW(combined
.queue
,
3444 renames
->pairs
[1].nr
+ renames
->pairs
[2].nr
,
3446 for (i
= MERGE_SIDE1
; i
<= MERGE_SIDE2
; i
++) {
3447 int other_side
= 3 - i
;
3448 compute_collisions(&collisions
[i
],
3449 &renames
->dir_renames
[other_side
],
3450 &renames
->pairs
[i
]);
3452 clean
&= collect_renames(opt
, &combined
, MERGE_SIDE1
,
3454 &renames
->dir_renames
[2],
3455 &renames
->dir_renames
[1]);
3456 clean
&= collect_renames(opt
, &combined
, MERGE_SIDE2
,
3458 &renames
->dir_renames
[1],
3459 &renames
->dir_renames
[2]);
3460 for (i
= MERGE_SIDE1
; i
<= MERGE_SIDE2
; i
++)
3461 free_collisions(&collisions
[i
]);
3462 STABLE_QSORT(combined
.queue
, combined
.nr
, compare_pairs
);
3463 trace2_region_leave("merge", "directory renames", opt
->repo
);
3465 trace2_region_enter("merge", "process renames", opt
->repo
);
3466 clean
&= process_renames(opt
, &combined
);
3467 trace2_region_leave("merge", "process renames", opt
->repo
);
3469 goto simple_cleanup
; /* collect_renames() handles some of cleanup */
3473 * Free now unneeded filepairs, which would have been handled
3474 * in collect_renames() normally but we skipped that code.
3476 for (s
= MERGE_SIDE1
; s
<= MERGE_SIDE2
; s
++) {
3477 struct diff_queue_struct
*side_pairs
;
3480 side_pairs
= &renames
->pairs
[s
];
3481 for (i
= 0; i
< side_pairs
->nr
; ++i
) {
3482 struct diff_filepair
*p
= side_pairs
->queue
[i
];
3483 pool_diff_free_filepair(&opt
->priv
->pool
, p
);
3488 /* Free memory for renames->pairs[] and combined */
3489 for (s
= MERGE_SIDE1
; s
<= MERGE_SIDE2
; s
++) {
3490 free(renames
->pairs
[s
].queue
);
3491 DIFF_QUEUE_CLEAR(&renames
->pairs
[s
]);
3493 for (i
= 0; i
< combined
.nr
; i
++)
3494 pool_diff_free_filepair(&opt
->priv
->pool
, combined
.queue
[i
]);
3495 free(combined
.queue
);
3500 /*** Function Grouping: functions related to process_entries() ***/
3502 static int sort_dirs_next_to_their_children(const char *one
, const char *two
)
3504 unsigned char c1
, c2
;
3507 * Here we only care that entries for directories appear adjacent
3508 * to and before files underneath the directory. We can achieve
3509 * that by pretending to add a trailing slash to every file and
3510 * then sorting. In other words, we do not want the natural
3515 * Instead, we want "foo" to sort as though it were "foo/", so that
3520 * To achieve this, we basically implement our own strcmp, except that
3521 * if we get to the end of either string instead of comparing NUL to
3522 * another character, we compare '/' to it.
3524 * If this unusual "sort as though '/' were appended" perplexes
3525 * you, perhaps it will help to note that this is not the final
3526 * sort. write_tree() will sort again without the trailing slash
3527 * magic, but just on paths immediately under a given tree.
3529 * The reason to not use df_name_compare directly was that it was
3530 * just too expensive (we don't have the string lengths handy), so
3531 * it was reimplemented.
3535 * NOTE: This function will never be called with two equal strings,
3536 * because it is used to sort the keys of a strmap, and strmaps have
3537 * unique keys by construction. That simplifies our c1==c2 handling
3541 while (*one
&& (*one
== *two
)) {
3546 c1
= *one
? *one
: '/';
3547 c2
= *two
? *two
: '/';
3550 /* Getting here means one is a leading directory of the other */
3551 return (*one
) ? 1 : -1;
3556 static int read_oid_strbuf(const struct object_id
*oid
,
3560 enum object_type type
;
3562 buf
= repo_read_object_file(the_repository
, oid
, &type
, &size
);
3564 return error(_("cannot read object %s"), oid_to_hex(oid
));
3565 if (type
!= OBJ_BLOB
) {
3567 return error(_("object %s is not a blob"), oid_to_hex(oid
));
3569 strbuf_attach(dst
, buf
, size
, size
+ 1);
3573 static int blob_unchanged(struct merge_options
*opt
,
3574 const struct version_info
*base
,
3575 const struct version_info
*side
,
3578 struct strbuf basebuf
= STRBUF_INIT
;
3579 struct strbuf sidebuf
= STRBUF_INIT
;
3580 int ret
= 0; /* assume changed for safety */
3581 struct index_state
*idx
= &opt
->priv
->attr_index
;
3583 if (!idx
->initialized
)
3584 initialize_attr_index(opt
);
3586 if (base
->mode
!= side
->mode
)
3588 if (oideq(&base
->oid
, &side
->oid
))
3591 if (read_oid_strbuf(&base
->oid
, &basebuf
) ||
3592 read_oid_strbuf(&side
->oid
, &sidebuf
))
3595 * Note: binary | is used so that both renormalizations are
3596 * performed. Comparison can be skipped if both files are
3597 * unchanged since their sha1s have already been compared.
3599 if (renormalize_buffer(idx
, path
, basebuf
.buf
, basebuf
.len
, &basebuf
) |
3600 renormalize_buffer(idx
, path
, sidebuf
.buf
, sidebuf
.len
, &sidebuf
))
3601 ret
= (basebuf
.len
== sidebuf
.len
&&
3602 !memcmp(basebuf
.buf
, sidebuf
.buf
, basebuf
.len
));
3605 strbuf_release(&basebuf
);
3606 strbuf_release(&sidebuf
);
3610 struct directory_versions
{
3612 * versions: list of (basename -> version_info)
3614 * The basenames are in reverse lexicographic order of full pathnames,
3615 * as processed in process_entries(). This puts all entries within
3616 * a directory together, and covers the directory itself after
3617 * everything within it, allowing us to write subtrees before needing
3618 * to record information for the tree itself.
3620 struct string_list versions
;
3623 * offsets: list of (full relative path directories -> integer offsets)
3625 * Since versions contains basenames from files in multiple different
3626 * directories, we need to know which entries in versions correspond
3627 * to which directories. Values of e.g.
3631 * Would mean that entries 0-1 of versions are files in the toplevel
3632 * directory, entries 2-4 are files under src/, and the remaining
3633 * entries starting at index 5 are files under src/moduleA/.
3635 struct string_list offsets
;
3638 * last_directory: directory that previously processed file found in
3640 * last_directory starts NULL, but records the directory in which the
3641 * previous file was found within. As soon as
3642 * directory(current_file) != last_directory
3643 * then we need to start updating accounting in versions & offsets.
3644 * Note that last_directory is always the last path in "offsets" (or
3645 * NULL if "offsets" is empty) so this exists just for quick access.
3647 const char *last_directory
;
3649 /* last_directory_len: cached computation of strlen(last_directory) */
3650 unsigned last_directory_len
;
3653 static int tree_entry_order(const void *a_
, const void *b_
)
3655 const struct string_list_item
*a
= a_
;
3656 const struct string_list_item
*b
= b_
;
3658 const struct merged_info
*ami
= a
->util
;
3659 const struct merged_info
*bmi
= b
->util
;
3660 return base_name_compare(a
->string
, strlen(a
->string
), ami
->result
.mode
,
3661 b
->string
, strlen(b
->string
), bmi
->result
.mode
);
3664 static int write_tree(struct object_id
*result_oid
,
3665 struct string_list
*versions
,
3666 unsigned int offset
,
3669 size_t maxlen
= 0, extra
;
3671 struct strbuf buf
= STRBUF_INIT
;
3674 assert(offset
<= versions
->nr
);
3675 nr
= versions
->nr
- offset
;
3677 /* No need for STABLE_QSORT -- filenames must be unique */
3678 QSORT(versions
->items
+ offset
, nr
, tree_entry_order
);
3680 /* Pre-allocate some space in buf */
3681 extra
= hash_size
+ 8; /* 8: 6 for mode, 1 for space, 1 for NUL char */
3682 for (i
= 0; i
< nr
; i
++) {
3683 maxlen
+= strlen(versions
->items
[offset
+i
].string
) + extra
;
3685 strbuf_grow(&buf
, maxlen
);
3687 /* Write each entry out to buf */
3688 for (i
= 0; i
< nr
; i
++) {
3689 struct merged_info
*mi
= versions
->items
[offset
+i
].util
;
3690 struct version_info
*ri
= &mi
->result
;
3691 strbuf_addf(&buf
, "%o %s%c",
3693 versions
->items
[offset
+i
].string
, '\0');
3694 strbuf_add(&buf
, ri
->oid
.hash
, hash_size
);
3697 /* Write this object file out, and record in result_oid */
3698 if (write_object_file(buf
.buf
, buf
.len
, OBJ_TREE
, result_oid
))
3700 strbuf_release(&buf
);
3704 static void record_entry_for_tree(struct directory_versions
*dir_metadata
,
3706 struct merged_info
*mi
)
3708 const char *basename
;
3711 /* nothing to record */
3714 basename
= path
+ mi
->basename_offset
;
3715 assert(strchr(basename
, '/') == NULL
);
3716 string_list_append(&dir_metadata
->versions
,
3717 basename
)->util
= &mi
->result
;
3720 static int write_completed_directory(struct merge_options
*opt
,
3721 const char *new_directory_name
,
3722 struct directory_versions
*info
)
3724 const char *prev_dir
;
3725 struct merged_info
*dir_info
= NULL
;
3726 unsigned int offset
, ret
= 0;
3729 * Some explanation of info->versions and info->offsets...
3731 * process_entries() iterates over all relevant files AND
3732 * directories in reverse lexicographic order, and calls this
3733 * function. Thus, an example of the paths that process_entries()
3734 * could operate on (along with the directories for those paths
3739 * src/moduleB/umm.c src/moduleB
3740 * src/moduleB/stuff.h src/moduleB
3741 * src/moduleB/baz.c src/moduleB
3743 * src/moduleA/foo.c src/moduleA
3744 * src/moduleA/bar.c src/moduleA
3751 * always contains the unprocessed entries and their
3752 * version_info information. For example, after the first five
3753 * entries above, info->versions would be:
3755 * xtract.c <xtract.c's version_info>
3756 * token.txt <token.txt's version_info>
3757 * umm.c <src/moduleB/umm.c's version_info>
3758 * stuff.h <src/moduleB/stuff.h's version_info>
3759 * baz.c <src/moduleB/baz.c's version_info>
3761 * Once a subdirectory is completed we remove the entries in
3762 * that subdirectory from info->versions, writing it as a tree
3763 * (write_tree()). Thus, as soon as we get to src/moduleB,
3764 * info->versions would be updated to
3766 * xtract.c <xtract.c's version_info>
3767 * token.txt <token.txt's version_info>
3768 * moduleB <src/moduleB's version_info>
3772 * helps us track which entries in info->versions correspond to
3773 * which directories. When we are N directories deep (e.g. 4
3774 * for src/modA/submod/subdir/), we have up to N+1 unprocessed
3775 * directories (+1 because of toplevel dir). Corresponding to
3776 * the info->versions example above, after processing five entries
3777 * info->offsets will be:
3782 * which is used to know that xtract.c & token.txt are from the
3783 * toplevel dirctory, while umm.c & stuff.h & baz.c are from the
3784 * src/moduleB directory. Again, following the example above,
3785 * once we need to process src/moduleB, then info->offsets is
3791 * which says that moduleB (and only moduleB so far) is in the
3794 * One unique thing to note about info->offsets here is that
3795 * "src" was not added to info->offsets until there was a path
3796 * (a file OR directory) immediately below src/ that got
3799 * Since process_entry() just appends new entries to info->versions,
3800 * write_completed_directory() only needs to do work if the next path
3801 * is in a directory that is different than the last directory found
3806 * If we are working with the same directory as the last entry, there
3807 * is no work to do. (See comments above the directory_name member of
3808 * struct merged_info for why we can use pointer comparison instead of
3811 if (new_directory_name
== info
->last_directory
)
3815 * If we are just starting (last_directory is NULL), or last_directory
3816 * is a prefix of the current directory, then we can just update
3817 * info->offsets to record the offset where we started this directory
3818 * and update last_directory to have quick access to it.
3820 if (info
->last_directory
== NULL
||
3821 !strncmp(new_directory_name
, info
->last_directory
,
3822 info
->last_directory_len
)) {
3823 uintptr_t offset
= info
->versions
.nr
;
3825 info
->last_directory
= new_directory_name
;
3826 info
->last_directory_len
= strlen(info
->last_directory
);
3828 * Record the offset into info->versions where we will
3829 * start recording basenames of paths found within
3830 * new_directory_name.
3832 string_list_append(&info
->offsets
,
3833 info
->last_directory
)->util
= (void*)offset
;
3838 * The next entry that will be processed will be within
3839 * new_directory_name. Since at this point we know that
3840 * new_directory_name is within a different directory than
3841 * info->last_directory, we have all entries for info->last_directory
3842 * in info->versions and we need to create a tree object for them.
3844 dir_info
= strmap_get(&opt
->priv
->paths
, info
->last_directory
);
3846 offset
= (uintptr_t)info
->offsets
.items
[info
->offsets
.nr
-1].util
;
3847 if (offset
== info
->versions
.nr
) {
3849 * Actually, we don't need to create a tree object in this
3850 * case. Whenever all files within a directory disappear
3851 * during the merge (e.g. unmodified on one side and
3852 * deleted on the other, or files were renamed elsewhere),
3853 * then we get here and the directory itself needs to be
3854 * omitted from its parent tree as well.
3856 dir_info
->is_null
= 1;
3859 * Write out the tree to the git object directory, and also
3860 * record the mode and oid in dir_info->result.
3862 dir_info
->is_null
= 0;
3863 dir_info
->result
.mode
= S_IFDIR
;
3864 if (write_tree(&dir_info
->result
.oid
, &info
->versions
, offset
,
3865 opt
->repo
->hash_algo
->rawsz
) < 0)
3870 * We've now used several entries from info->versions and one entry
3871 * from info->offsets, so we get rid of those values.
3874 info
->versions
.nr
= offset
;
3877 * Now we've taken care of the completed directory, but we need to
3878 * prepare things since future entries will be in
3879 * new_directory_name. (In particular, process_entry() will be
3880 * appending new entries to info->versions.) So, we need to make
3881 * sure new_directory_name is the last entry in info->offsets.
3883 prev_dir
= info
->offsets
.nr
== 0 ? NULL
:
3884 info
->offsets
.items
[info
->offsets
.nr
-1].string
;
3885 if (new_directory_name
!= prev_dir
) {
3886 uintptr_t c
= info
->versions
.nr
;
3887 string_list_append(&info
->offsets
,
3888 new_directory_name
)->util
= (void*)c
;
3891 /* And, of course, we need to update last_directory to match. */
3892 info
->last_directory
= new_directory_name
;
3893 info
->last_directory_len
= strlen(info
->last_directory
);
3898 /* Per entry merge function */
3899 static int process_entry(struct merge_options
*opt
,
3901 struct conflict_info
*ci
,
3902 struct directory_versions
*dir_metadata
)
3904 int df_file_index
= 0;
3907 assert(ci
->filemask
>= 0 && ci
->filemask
<= 7);
3908 /* ci->match_mask == 7 was handled in collect_merge_info_callback() */
3909 assert(ci
->match_mask
== 0 || ci
->match_mask
== 3 ||
3910 ci
->match_mask
== 5 || ci
->match_mask
== 6);
3913 record_entry_for_tree(dir_metadata
, path
, &ci
->merged
);
3914 if (ci
->filemask
== 0)
3915 /* nothing else to handle */
3917 assert(ci
->df_conflict
);
3920 if (ci
->df_conflict
&& ci
->merged
.result
.mode
== 0) {
3924 * directory no longer in the way, but we do have a file we
3925 * need to place here so we need to clean away the "directory
3926 * merges to nothing" result.
3928 ci
->df_conflict
= 0;
3929 assert(ci
->filemask
!= 0);
3930 ci
->merged
.clean
= 0;
3931 ci
->merged
.is_null
= 0;
3932 /* and we want to zero out any directory-related entries */
3933 ci
->match_mask
= (ci
->match_mask
& ~ci
->dirmask
);
3935 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
3936 if (ci
->filemask
& (1 << i
))
3938 ci
->stages
[i
].mode
= 0;
3939 oidcpy(&ci
->stages
[i
].oid
, null_oid());
3941 } else if (ci
->df_conflict
&& ci
->merged
.result
.mode
!= 0) {
3943 * This started out as a D/F conflict, and the entries in
3944 * the competing directory were not removed by the merge as
3945 * evidenced by write_completed_directory() writing a value
3946 * to ci->merged.result.mode.
3948 struct conflict_info
*new_ci
;
3950 const char *old_path
= path
;
3953 assert(ci
->merged
.result
.mode
== S_IFDIR
);
3956 * If filemask is 1, we can just ignore the file as having
3957 * been deleted on both sides. We do not want to overwrite
3958 * ci->merged.result, since it stores the tree for all the
3961 if (ci
->filemask
== 1) {
3967 * This file still exists on at least one side, and we want
3968 * the directory to remain here, so we need to move this
3969 * path to some new location.
3971 new_ci
= mem_pool_calloc(&opt
->priv
->pool
, 1, sizeof(*new_ci
));
3973 /* We don't really want new_ci->merged.result copied, but it'll
3974 * be overwritten below so it doesn't matter. We also don't
3975 * want any directory mode/oid values copied, but we'll zero
3976 * those out immediately. We do want the rest of ci copied.
3978 memcpy(new_ci
, ci
, sizeof(*ci
));
3979 new_ci
->match_mask
= (new_ci
->match_mask
& ~new_ci
->dirmask
);
3980 new_ci
->dirmask
= 0;
3981 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
3982 if (new_ci
->filemask
& (1 << i
))
3984 /* zero out any entries related to directories */
3985 new_ci
->stages
[i
].mode
= 0;
3986 oidcpy(&new_ci
->stages
[i
].oid
, null_oid());
3990 * Find out which side this file came from; note that we
3991 * cannot just use ci->filemask, because renames could cause
3992 * the filemask to go back to 7. So we use dirmask, then
3993 * pick the opposite side's index.
3995 df_file_index
= (ci
->dirmask
& (1 << 1)) ? 2 : 1;
3996 branch
= (df_file_index
== 1) ? opt
->branch1
: opt
->branch2
;
3997 path
= unique_path(opt
, path
, branch
);
3998 strmap_put(&opt
->priv
->paths
, path
, new_ci
);
4000 path_msg(opt
, CONFLICT_FILE_DIRECTORY
, 0,
4001 path
, old_path
, NULL
, NULL
,
4002 _("CONFLICT (file/directory): directory in the way "
4003 "of %s from %s; moving it to %s instead."),
4004 old_path
, branch
, path
);
4007 * Zero out the filemask for the old ci. At this point, ci
4008 * was just an entry for a directory, so we don't need to
4009 * do anything more with it.
4014 * Now note that we're working on the new entry (path was
4021 * NOTE: Below there is a long switch-like if-elseif-elseif... block
4022 * which the code goes through even for the df_conflict cases
4025 if (ci
->match_mask
) {
4026 ci
->merged
.clean
= !ci
->df_conflict
&& !ci
->path_conflict
;
4027 if (ci
->match_mask
== 6) {
4028 /* stages[1] == stages[2] */
4029 ci
->merged
.result
.mode
= ci
->stages
[1].mode
;
4030 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[1].oid
);
4032 /* determine the mask of the side that didn't match */
4033 unsigned int othermask
= 7 & ~ci
->match_mask
;
4034 int side
= (othermask
== 4) ? 2 : 1;
4036 ci
->merged
.result
.mode
= ci
->stages
[side
].mode
;
4037 ci
->merged
.is_null
= !ci
->merged
.result
.mode
;
4038 if (ci
->merged
.is_null
)
4039 ci
->merged
.clean
= 1;
4040 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[side
].oid
);
4042 assert(othermask
== 2 || othermask
== 4);
4043 assert(ci
->merged
.is_null
==
4044 (ci
->filemask
== ci
->match_mask
));
4046 } else if (ci
->filemask
>= 6 &&
4047 (S_IFMT
& ci
->stages
[1].mode
) !=
4048 (S_IFMT
& ci
->stages
[2].mode
)) {
4049 /* Two different items from (file/submodule/symlink) */
4050 if (opt
->priv
->call_depth
) {
4051 /* Just use the version from the merge base */
4052 ci
->merged
.clean
= 0;
4053 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[0].oid
);
4054 ci
->merged
.result
.mode
= ci
->stages
[0].mode
;
4055 ci
->merged
.is_null
= (ci
->merged
.result
.mode
== 0);
4057 /* Handle by renaming one or both to separate paths. */
4058 unsigned o_mode
= ci
->stages
[0].mode
;
4059 unsigned a_mode
= ci
->stages
[1].mode
;
4060 unsigned b_mode
= ci
->stages
[2].mode
;
4061 struct conflict_info
*new_ci
;
4062 const char *a_path
= NULL
, *b_path
= NULL
;
4063 int rename_a
= 0, rename_b
= 0;
4065 new_ci
= mem_pool_alloc(&opt
->priv
->pool
,
4068 if (S_ISREG(a_mode
))
4070 else if (S_ISREG(b_mode
))
4078 a_path
= unique_path(opt
, path
, opt
->branch1
);
4080 b_path
= unique_path(opt
, path
, opt
->branch2
);
4082 if (rename_a
&& rename_b
) {
4083 path_msg(opt
, CONFLICT_DISTINCT_MODES
, 0,
4084 path
, a_path
, b_path
, NULL
,
4085 _("CONFLICT (distinct types): %s had "
4086 "different types on each side; "
4087 "renamed both of them so each can "
4088 "be recorded somewhere."),
4091 path_msg(opt
, CONFLICT_DISTINCT_MODES
, 0,
4092 path
, rename_a
? a_path
: b_path
,
4094 _("CONFLICT (distinct types): %s had "
4095 "different types on each side; "
4096 "renamed one of them so each can be "
4097 "recorded somewhere."),
4101 ci
->merged
.clean
= 0;
4102 memcpy(new_ci
, ci
, sizeof(*new_ci
));
4104 /* Put b into new_ci, removing a from stages */
4105 new_ci
->merged
.result
.mode
= ci
->stages
[2].mode
;
4106 oidcpy(&new_ci
->merged
.result
.oid
, &ci
->stages
[2].oid
);
4107 new_ci
->stages
[1].mode
= 0;
4108 oidcpy(&new_ci
->stages
[1].oid
, null_oid());
4109 new_ci
->filemask
= 5;
4110 if ((S_IFMT
& b_mode
) != (S_IFMT
& o_mode
)) {
4111 new_ci
->stages
[0].mode
= 0;
4112 oidcpy(&new_ci
->stages
[0].oid
, null_oid());
4113 new_ci
->filemask
= 4;
4116 /* Leave only a in ci, fixing stages. */
4117 ci
->merged
.result
.mode
= ci
->stages
[1].mode
;
4118 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[1].oid
);
4119 ci
->stages
[2].mode
= 0;
4120 oidcpy(&ci
->stages
[2].oid
, null_oid());
4122 if ((S_IFMT
& a_mode
) != (S_IFMT
& o_mode
)) {
4123 ci
->stages
[0].mode
= 0;
4124 oidcpy(&ci
->stages
[0].oid
, null_oid());
4128 /* Insert entries into opt->priv_paths */
4129 assert(rename_a
|| rename_b
);
4131 strmap_put(&opt
->priv
->paths
, a_path
, ci
);
4135 strmap_put(&opt
->priv
->paths
, b_path
, new_ci
);
4137 if (rename_a
&& rename_b
)
4138 strmap_remove(&opt
->priv
->paths
, path
, 0);
4141 * Do special handling for b_path since process_entry()
4142 * won't be called on it specially.
4144 strmap_put(&opt
->priv
->conflicted
, b_path
, new_ci
);
4145 record_entry_for_tree(dir_metadata
, b_path
,
4149 * Remaining code for processing this entry should
4150 * think in terms of processing a_path.
4155 } else if (ci
->filemask
>= 6) {
4156 /* Need a two-way or three-way content merge */
4157 struct version_info merged_file
;
4159 struct version_info
*o
= &ci
->stages
[0];
4160 struct version_info
*a
= &ci
->stages
[1];
4161 struct version_info
*b
= &ci
->stages
[2];
4163 clean_merge
= handle_content_merge(opt
, path
, o
, a
, b
,
4165 opt
->priv
->call_depth
* 2,
4167 if (clean_merge
< 0)
4169 ci
->merged
.clean
= clean_merge
&&
4170 !ci
->df_conflict
&& !ci
->path_conflict
;
4171 ci
->merged
.result
.mode
= merged_file
.mode
;
4172 ci
->merged
.is_null
= (merged_file
.mode
== 0);
4173 oidcpy(&ci
->merged
.result
.oid
, &merged_file
.oid
);
4174 if (clean_merge
&& ci
->df_conflict
) {
4175 assert(df_file_index
== 1 || df_file_index
== 2);
4176 ci
->filemask
= 1 << df_file_index
;
4177 ci
->stages
[df_file_index
].mode
= merged_file
.mode
;
4178 oidcpy(&ci
->stages
[df_file_index
].oid
, &merged_file
.oid
);
4181 const char *reason
= _("content");
4182 if (ci
->filemask
== 6)
4183 reason
= _("add/add");
4184 if (S_ISGITLINK(merged_file
.mode
))
4185 reason
= _("submodule");
4186 path_msg(opt
, CONFLICT_CONTENTS
, 0,
4187 path
, NULL
, NULL
, NULL
,
4188 _("CONFLICT (%s): Merge conflict in %s"),
4191 } else if (ci
->filemask
== 3 || ci
->filemask
== 5) {
4193 const char *modify_branch
, *delete_branch
;
4194 int side
= (ci
->filemask
== 5) ? 2 : 1;
4195 int index
= opt
->priv
->call_depth
? 0 : side
;
4197 ci
->merged
.result
.mode
= ci
->stages
[index
].mode
;
4198 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[index
].oid
);
4199 ci
->merged
.clean
= 0;
4201 modify_branch
= (side
== 1) ? opt
->branch1
: opt
->branch2
;
4202 delete_branch
= (side
== 1) ? opt
->branch2
: opt
->branch1
;
4204 if (opt
->renormalize
&&
4205 blob_unchanged(opt
, &ci
->stages
[0], &ci
->stages
[side
],
4207 if (!ci
->path_conflict
) {
4209 * Blob unchanged after renormalization, so
4210 * there's no modify/delete conflict after all;
4211 * we can just remove the file.
4213 ci
->merged
.is_null
= 1;
4214 ci
->merged
.clean
= 1;
4216 * file goes away => even if there was a
4217 * directory/file conflict there isn't one now.
4219 ci
->df_conflict
= 0;
4221 /* rename/delete, so conflict remains */
4223 } else if (ci
->path_conflict
&&
4224 oideq(&ci
->stages
[0].oid
, &ci
->stages
[side
].oid
)) {
4226 * This came from a rename/delete; no action to take,
4227 * but avoid printing "modify/delete" conflict notice
4228 * since the contents were not modified.
4231 path_msg(opt
, CONFLICT_MODIFY_DELETE
, 0,
4232 path
, NULL
, NULL
, NULL
,
4233 _("CONFLICT (modify/delete): %s deleted in %s "
4234 "and modified in %s. Version %s of %s left "
4236 path
, delete_branch
, modify_branch
,
4237 modify_branch
, path
);
4239 } else if (ci
->filemask
== 2 || ci
->filemask
== 4) {
4240 /* Added on one side */
4241 int side
= (ci
->filemask
== 4) ? 2 : 1;
4242 ci
->merged
.result
.mode
= ci
->stages
[side
].mode
;
4243 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[side
].oid
);
4244 ci
->merged
.clean
= !ci
->df_conflict
&& !ci
->path_conflict
;
4245 } else if (ci
->filemask
== 1) {
4246 /* Deleted on both sides */
4247 ci
->merged
.is_null
= 1;
4248 ci
->merged
.result
.mode
= 0;
4249 oidcpy(&ci
->merged
.result
.oid
, null_oid());
4250 assert(!ci
->df_conflict
);
4251 ci
->merged
.clean
= !ci
->path_conflict
;
4255 * If still conflicted, record it separately. This allows us to later
4256 * iterate over just conflicted entries when updating the index instead
4257 * of iterating over all entries.
4259 if (!ci
->merged
.clean
)
4260 strmap_put(&opt
->priv
->conflicted
, path
, ci
);
4262 /* Record metadata for ci->merged in dir_metadata */
4263 record_entry_for_tree(dir_metadata
, path
, &ci
->merged
);
4267 static void prefetch_for_content_merges(struct merge_options
*opt
,
4268 struct string_list
*plist
)
4270 struct string_list_item
*e
;
4271 struct oid_array to_fetch
= OID_ARRAY_INIT
;
4273 if (opt
->repo
!= the_repository
|| !repo_has_promisor_remote(the_repository
))
4276 for (e
= &plist
->items
[plist
->nr
-1]; e
>= plist
->items
; --e
) {
4277 /* char *path = e->string; */
4278 struct conflict_info
*ci
= e
->util
;
4281 /* Ignore clean entries */
4282 if (ci
->merged
.clean
)
4285 /* Ignore entries that don't need a content merge */
4286 if (ci
->match_mask
|| ci
->filemask
< 6 ||
4287 !S_ISREG(ci
->stages
[1].mode
) ||
4288 !S_ISREG(ci
->stages
[2].mode
) ||
4289 oideq(&ci
->stages
[1].oid
, &ci
->stages
[2].oid
))
4292 /* Also don't need content merge if base matches either side */
4293 if (ci
->filemask
== 7 &&
4294 S_ISREG(ci
->stages
[0].mode
) &&
4295 (oideq(&ci
->stages
[0].oid
, &ci
->stages
[1].oid
) ||
4296 oideq(&ci
->stages
[0].oid
, &ci
->stages
[2].oid
)))
4299 for (i
= 0; i
< 3; i
++) {
4300 unsigned side_mask
= (1 << i
);
4301 struct version_info
*vi
= &ci
->stages
[i
];
4303 if ((ci
->filemask
& side_mask
) &&
4304 S_ISREG(vi
->mode
) &&
4305 oid_object_info_extended(opt
->repo
, &vi
->oid
, NULL
,
4306 OBJECT_INFO_FOR_PREFETCH
))
4307 oid_array_append(&to_fetch
, &vi
->oid
);
4311 promisor_remote_get_direct(opt
->repo
, to_fetch
.oid
, to_fetch
.nr
);
4312 oid_array_clear(&to_fetch
);
4315 static int process_entries(struct merge_options
*opt
,
4316 struct object_id
*result_oid
)
4318 struct hashmap_iter iter
;
4319 struct strmap_entry
*e
;
4320 struct string_list plist
= STRING_LIST_INIT_NODUP
;
4321 struct string_list_item
*entry
;
4322 struct directory_versions dir_metadata
= { STRING_LIST_INIT_NODUP
,
4323 STRING_LIST_INIT_NODUP
,
4327 trace2_region_enter("merge", "process_entries setup", opt
->repo
);
4328 if (strmap_empty(&opt
->priv
->paths
)) {
4329 oidcpy(result_oid
, opt
->repo
->hash_algo
->empty_tree
);
4333 /* Hack to pre-allocate plist to the desired size */
4334 trace2_region_enter("merge", "plist grow", opt
->repo
);
4335 ALLOC_GROW(plist
.items
, strmap_get_size(&opt
->priv
->paths
), plist
.alloc
);
4336 trace2_region_leave("merge", "plist grow", opt
->repo
);
4338 /* Put every entry from paths into plist, then sort */
4339 trace2_region_enter("merge", "plist copy", opt
->repo
);
4340 strmap_for_each_entry(&opt
->priv
->paths
, &iter
, e
) {
4341 string_list_append(&plist
, e
->key
)->util
= e
->value
;
4343 trace2_region_leave("merge", "plist copy", opt
->repo
);
4345 trace2_region_enter("merge", "plist special sort", opt
->repo
);
4346 plist
.cmp
= sort_dirs_next_to_their_children
;
4347 string_list_sort(&plist
);
4348 trace2_region_leave("merge", "plist special sort", opt
->repo
);
4350 trace2_region_leave("merge", "process_entries setup", opt
->repo
);
4353 * Iterate over the items in reverse order, so we can handle paths
4354 * below a directory before needing to handle the directory itself.
4356 * This allows us to write subtrees before we need to write trees,
4357 * and it also enables sane handling of directory/file conflicts
4358 * (because it allows us to know whether the directory is still in
4359 * the way when it is time to process the file at the same path).
4361 trace2_region_enter("merge", "processing", opt
->repo
);
4362 prefetch_for_content_merges(opt
, &plist
);
4363 for (entry
= &plist
.items
[plist
.nr
-1]; entry
>= plist
.items
; --entry
) {
4364 char *path
= entry
->string
;
4366 * NOTE: mi may actually be a pointer to a conflict_info, but
4367 * we have to check mi->clean first to see if it's safe to
4368 * reassign to such a pointer type.
4370 struct merged_info
*mi
= entry
->util
;
4372 if (write_completed_directory(opt
, mi
->directory_name
,
4373 &dir_metadata
) < 0) {
4378 record_entry_for_tree(&dir_metadata
, path
, mi
);
4380 struct conflict_info
*ci
= (struct conflict_info
*)mi
;
4381 if (process_entry(opt
, path
, ci
, &dir_metadata
) < 0) {
4387 trace2_region_leave("merge", "processing", opt
->repo
);
4389 trace2_region_enter("merge", "process_entries cleanup", opt
->repo
);
4390 if (dir_metadata
.offsets
.nr
!= 1 ||
4391 (uintptr_t)dir_metadata
.offsets
.items
[0].util
!= 0) {
4392 printf("dir_metadata.offsets.nr = %"PRIuMAX
" (should be 1)\n",
4393 (uintmax_t)dir_metadata
.offsets
.nr
);
4394 printf("dir_metadata.offsets.items[0].util = %u (should be 0)\n",
4395 (unsigned)(uintptr_t)dir_metadata
.offsets
.items
[0].util
);
4397 BUG("dir_metadata accounting completely off; shouldn't happen");
4399 if (write_tree(result_oid
, &dir_metadata
.versions
, 0,
4400 opt
->repo
->hash_algo
->rawsz
) < 0)
4403 string_list_clear(&plist
, 0);
4404 string_list_clear(&dir_metadata
.versions
, 0);
4405 string_list_clear(&dir_metadata
.offsets
, 0);
4406 trace2_region_leave("merge", "process_entries cleanup", opt
->repo
);
4411 /*** Function Grouping: functions related to merge_switch_to_result() ***/
4413 static int checkout(struct merge_options
*opt
,
4417 /* Switch the index/working copy from old to new */
4419 struct tree_desc trees
[2];
4420 struct unpack_trees_options unpack_opts
;
4422 memset(&unpack_opts
, 0, sizeof(unpack_opts
));
4423 unpack_opts
.head_idx
= -1;
4424 unpack_opts
.src_index
= opt
->repo
->index
;
4425 unpack_opts
.dst_index
= opt
->repo
->index
;
4427 setup_unpack_trees_porcelain(&unpack_opts
, "merge");
4430 * NOTE: if this were just "git checkout" code, we would probably
4431 * read or refresh the cache and check for a conflicted index, but
4432 * builtin/merge.c or sequencer.c really needs to read the index
4433 * and check for conflicted entries before starting merging for a
4434 * good user experience (no sense waiting for merges/rebases before
4435 * erroring out), so there's no reason to duplicate that work here.
4438 /* 2-way merge to the new branch */
4439 unpack_opts
.update
= 1;
4440 unpack_opts
.merge
= 1;
4441 unpack_opts
.quiet
= 0; /* FIXME: sequencer might want quiet? */
4442 unpack_opts
.verbose_update
= (opt
->verbosity
> 2);
4443 unpack_opts
.fn
= twoway_merge
;
4444 unpack_opts
.preserve_ignored
= 0; /* FIXME: !opts->overwrite_ignore */
4446 init_tree_desc(&trees
[0], prev
->buffer
, prev
->size
);
4448 init_tree_desc(&trees
[1], next
->buffer
, next
->size
);
4450 ret
= unpack_trees(2, trees
, &unpack_opts
);
4451 clear_unpack_trees_porcelain(&unpack_opts
);
4455 static int record_conflicted_index_entries(struct merge_options
*opt
)
4457 struct hashmap_iter iter
;
4458 struct strmap_entry
*e
;
4459 struct index_state
*index
= opt
->repo
->index
;
4460 struct checkout state
= CHECKOUT_INIT
;
4462 int original_cache_nr
;
4464 if (strmap_empty(&opt
->priv
->conflicted
))
4468 * We are in a conflicted state. These conflicts might be inside
4469 * sparse-directory entries, so check if any entries are outside
4470 * of the sparse-checkout cone preemptively.
4472 * We set original_cache_nr below, but that might change if
4473 * index_name_pos() calls ask for paths within sparse directories.
4475 strmap_for_each_entry(&opt
->priv
->conflicted
, &iter
, e
) {
4476 if (!path_in_sparse_checkout(e
->key
, index
)) {
4477 ensure_full_index(index
);
4482 /* If any entries have skip_worktree set, we'll have to check 'em out */
4485 state
.refresh_cache
= 1;
4486 state
.istate
= index
;
4487 original_cache_nr
= index
->cache_nr
;
4489 /* Append every entry from conflicted into index, then sort */
4490 strmap_for_each_entry(&opt
->priv
->conflicted
, &iter
, e
) {
4491 const char *path
= e
->key
;
4492 struct conflict_info
*ci
= e
->value
;
4494 struct cache_entry
*ce
;
4500 * The index will already have a stage=0 entry for this path,
4501 * because we created an as-merged-as-possible version of the
4502 * file and checkout() moved the working copy and index over
4505 * However, previous iterations through this loop will have
4506 * added unstaged entries to the end of the cache which
4507 * ignore the standard alphabetical ordering of cache
4508 * entries and break invariants needed for index_name_pos()
4509 * to work. However, we know the entry we want is before
4510 * those appended cache entries, so do a temporary swap on
4511 * cache_nr to only look through entries of interest.
4513 SWAP(index
->cache_nr
, original_cache_nr
);
4514 pos
= index_name_pos(index
, path
, strlen(path
));
4515 SWAP(index
->cache_nr
, original_cache_nr
);
4517 if (ci
->filemask
!= 1)
4518 BUG("Conflicted %s but nothing in basic working tree or index; this shouldn't happen", path
);
4519 cache_tree_invalidate_path(index
, path
);
4521 ce
= index
->cache
[pos
];
4524 * Clean paths with CE_SKIP_WORKTREE set will not be
4525 * written to the working tree by the unpack_trees()
4526 * call in checkout(). Our conflicted entries would
4527 * have appeared clean to that code since we ignored
4528 * the higher order stages. Thus, we need override
4529 * the CE_SKIP_WORKTREE bit and manually write those
4530 * files to the working disk here.
4532 if (ce_skip_worktree(ce
))
4533 errs
|= checkout_entry(ce
, &state
, NULL
, NULL
);
4536 * Mark this cache entry for removal and instead add
4537 * new stage>0 entries corresponding to the
4538 * conflicts. If there are many conflicted entries, we
4539 * want to avoid memmove'ing O(NM) entries by
4540 * inserting the new entries one at a time. So,
4541 * instead, we just add the new cache entries to the
4542 * end (ignoring normal index requirements on sort
4543 * order) and sort the index once we're all done.
4545 ce
->ce_flags
|= CE_REMOVE
;
4548 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
4549 struct version_info
*vi
;
4550 if (!(ci
->filemask
& (1ul << i
)))
4552 vi
= &ci
->stages
[i
];
4553 ce
= make_cache_entry(index
, vi
->mode
, &vi
->oid
,
4555 add_index_entry(index
, ce
, ADD_CACHE_JUST_APPEND
);
4560 * Remove the unused cache entries (and invalidate the relevant
4561 * cache-trees), then sort the index entries to get the conflicted
4562 * entries we added to the end into their right locations.
4564 remove_marked_cache_entries(index
, 1);
4566 * No need for STABLE_QSORT -- cmp_cache_name_compare sorts primarily
4567 * on filename and secondarily on stage, and (name, stage #) are a
4570 QSORT(index
->cache
, index
->cache_nr
, cmp_cache_name_compare
);
4575 static void print_submodule_conflict_suggestion(struct string_list
*csub
) {
4576 struct string_list_item
*item
;
4577 struct strbuf msg
= STRBUF_INIT
;
4578 struct strbuf tmp
= STRBUF_INIT
;
4579 struct strbuf subs
= STRBUF_INIT
;
4584 strbuf_add_separated_string_list(&subs
, " ", csub
);
4585 for_each_string_list_item(item
, csub
) {
4586 struct conflicted_submodule_item
*util
= item
->util
;
4589 * NEEDSWORK: The steps to resolve these errors deserve a more
4590 * detailed explanation than what is currently printed below.
4592 if (util
->flag
== CONFLICT_SUBMODULE_NOT_INITIALIZED
||
4593 util
->flag
== CONFLICT_SUBMODULE_HISTORY_NOT_AVAILABLE
)
4597 * TRANSLATORS: This is a line of advice to resolve a merge
4598 * conflict in a submodule. The first argument is the submodule
4599 * name, and the second argument is the abbreviated id of the
4600 * commit that needs to be merged. For example:
4601 * - go to submodule (mysubmodule), and either merge commit abc1234"
4603 strbuf_addf(&tmp
, _(" - go to submodule (%s), and either merge commit %s\n"
4604 " or update to an existing commit which has merged those changes\n"),
4605 item
->string
, util
->abbrev
);
4609 * TRANSLATORS: This is a detailed message for resolving submodule
4610 * conflicts. The first argument is string containing one step per
4611 * submodule. The second is a space-separated list of submodule names.
4614 _("Recursive merging with submodules currently only supports trivial cases.\n"
4615 "Please manually handle the merging of each conflicted submodule.\n"
4616 "This can be accomplished with the following steps:\n"
4618 " - come back to superproject and run:\n\n"
4620 " to record the above merge or update\n"
4621 " - resolve any other conflicts in the superproject\n"
4622 " - commit the resulting index in the superproject\n"),
4625 printf("%s", msg
.buf
);
4627 strbuf_release(&subs
);
4628 strbuf_release(&tmp
);
4629 strbuf_release(&msg
);
4632 void merge_display_update_messages(struct merge_options
*opt
,
4634 struct merge_result
*result
)
4636 struct merge_options_internal
*opti
= result
->priv
;
4637 struct hashmap_iter iter
;
4638 struct strmap_entry
*e
;
4639 struct string_list olist
= STRING_LIST_INIT_NODUP
;
4641 if (opt
->record_conflict_msgs_as_headers
)
4642 BUG("Either display conflict messages or record them as headers, not both");
4644 trace2_region_enter("merge", "display messages", opt
->repo
);
4646 /* Hack to pre-allocate olist to the desired size */
4647 ALLOC_GROW(olist
.items
, strmap_get_size(&opti
->conflicts
),
4650 /* Put every entry from output into olist, then sort */
4651 strmap_for_each_entry(&opti
->conflicts
, &iter
, e
) {
4652 string_list_append(&olist
, e
->key
)->util
= e
->value
;
4654 string_list_sort(&olist
);
4656 /* Iterate over the items, printing them */
4657 for (int path_nr
= 0; path_nr
< olist
.nr
; ++path_nr
) {
4658 struct string_list
*conflicts
= olist
.items
[path_nr
].util
;
4659 for (int i
= 0; i
< conflicts
->nr
; i
++) {
4660 struct logical_conflict_info
*info
=
4661 conflicts
->items
[i
].util
;
4664 printf("%lu", (unsigned long)info
->paths
.nr
);
4666 for (int n
= 0; n
< info
->paths
.nr
; n
++) {
4667 fputs(info
->paths
.v
[n
], stdout
);
4670 fputs(type_short_descriptions
[info
->type
],
4674 puts(conflicts
->items
[i
].string
);
4679 string_list_clear(&olist
, 0);
4681 print_submodule_conflict_suggestion(&opti
->conflicted_submodules
);
4683 /* Also include needed rename limit adjustment now */
4684 diff_warn_rename_limit("merge.renamelimit",
4685 opti
->renames
.needed_limit
, 0);
4687 trace2_region_leave("merge", "display messages", opt
->repo
);
4690 void merge_get_conflicted_files(struct merge_result
*result
,
4691 struct string_list
*conflicted_files
)
4693 struct hashmap_iter iter
;
4694 struct strmap_entry
*e
;
4695 struct merge_options_internal
*opti
= result
->priv
;
4697 strmap_for_each_entry(&opti
->conflicted
, &iter
, e
) {
4698 const char *path
= e
->key
;
4699 struct conflict_info
*ci
= e
->value
;
4704 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
4705 struct stage_info
*si
;
4707 if (!(ci
->filemask
& (1ul << i
)))
4710 si
= xmalloc(sizeof(*si
));
4712 si
->mode
= ci
->stages
[i
].mode
;
4713 oidcpy(&si
->oid
, &ci
->stages
[i
].oid
);
4714 string_list_append(conflicted_files
, path
)->util
= si
;
4717 /* string_list_sort() uses a stable sort, so we're good */
4718 string_list_sort(conflicted_files
);
4721 void merge_switch_to_result(struct merge_options
*opt
,
4723 struct merge_result
*result
,
4724 int update_worktree_and_index
,
4725 int display_update_msgs
)
4727 assert(opt
->priv
== NULL
);
4728 if (result
->clean
>= 0 && update_worktree_and_index
) {
4729 trace2_region_enter("merge", "checkout", opt
->repo
);
4730 if (checkout(opt
, head
, result
->tree
)) {
4731 /* failure to function */
4733 merge_finalize(opt
, result
);
4734 trace2_region_leave("merge", "checkout", opt
->repo
);
4737 trace2_region_leave("merge", "checkout", opt
->repo
);
4739 trace2_region_enter("merge", "record_conflicted", opt
->repo
);
4740 opt
->priv
= result
->priv
;
4741 if (record_conflicted_index_entries(opt
)) {
4742 /* failure to function */
4745 merge_finalize(opt
, result
);
4746 trace2_region_leave("merge", "record_conflicted",
4751 trace2_region_leave("merge", "record_conflicted", opt
->repo
);
4753 trace2_region_enter("merge", "write_auto_merge", opt
->repo
);
4754 if (refs_update_ref(get_main_ref_store(opt
->repo
), "", "AUTO_MERGE",
4755 &result
->tree
->object
.oid
, NULL
, REF_NO_DEREF
,
4756 UPDATE_REFS_MSG_ON_ERR
)) {
4757 /* failure to function */
4760 merge_finalize(opt
, result
);
4761 trace2_region_leave("merge", "write_auto_merge",
4765 trace2_region_leave("merge", "write_auto_merge", opt
->repo
);
4767 if (display_update_msgs
)
4768 merge_display_update_messages(opt
, /* detailed */ 0, result
);
4770 merge_finalize(opt
, result
);
4773 void merge_finalize(struct merge_options
*opt
,
4774 struct merge_result
*result
)
4776 if (opt
->renormalize
)
4777 git_attr_set_direction(GIT_ATTR_CHECKIN
);
4778 assert(opt
->priv
== NULL
);
4781 clear_or_reinit_internal_opts(result
->priv
, 0);
4782 FREE_AND_NULL(result
->priv
);
4786 /*** Function Grouping: helper functions for merge_incore_*() ***/
4788 static struct tree
*shift_tree_object(struct repository
*repo
,
4789 struct tree
*one
, struct tree
*two
,
4790 const char *subtree_shift
)
4792 struct object_id shifted
;
4794 if (!*subtree_shift
) {
4795 shift_tree(repo
, &one
->object
.oid
, &two
->object
.oid
, &shifted
, 0);
4797 shift_tree_by(repo
, &one
->object
.oid
, &two
->object
.oid
, &shifted
,
4800 if (oideq(&two
->object
.oid
, &shifted
))
4802 return lookup_tree(repo
, &shifted
);
4805 static inline void set_commit_tree(struct commit
*c
, struct tree
*t
)
4810 static struct commit
*make_virtual_commit(struct repository
*repo
,
4812 const char *comment
)
4814 struct commit
*commit
= alloc_commit_node(repo
);
4816 set_merge_remote_desc(commit
, comment
, (struct object
*)commit
);
4817 set_commit_tree(commit
, tree
);
4818 commit
->object
.parsed
= 1;
4822 static void merge_start(struct merge_options
*opt
, struct merge_result
*result
)
4824 struct rename_info
*renames
;
4826 struct mem_pool
*pool
= NULL
;
4828 /* Sanity checks on opt */
4829 trace2_region_enter("merge", "sanity checks", opt
->repo
);
4832 assert(opt
->branch1
&& opt
->branch2
);
4834 assert(opt
->detect_directory_renames
>= MERGE_DIRECTORY_RENAMES_NONE
&&
4835 opt
->detect_directory_renames
<= MERGE_DIRECTORY_RENAMES_TRUE
);
4836 assert(opt
->rename_limit
>= -1);
4837 assert(opt
->rename_score
>= 0 && opt
->rename_score
<= MAX_SCORE
);
4838 assert(opt
->show_rename_progress
>= 0 && opt
->show_rename_progress
<= 1);
4840 assert(opt
->xdl_opts
>= 0);
4841 assert(opt
->recursive_variant
>= MERGE_VARIANT_NORMAL
&&
4842 opt
->recursive_variant
<= MERGE_VARIANT_THEIRS
);
4844 if (opt
->msg_header_prefix
)
4845 assert(opt
->record_conflict_msgs_as_headers
);
4848 * detect_renames, verbosity, buffer_output, and obuf are ignored
4849 * fields that were used by "recursive" rather than "ort" -- but
4850 * sanity check them anyway.
4852 assert(opt
->detect_renames
>= -1 &&
4853 opt
->detect_renames
<= DIFF_DETECT_COPY
);
4854 assert(opt
->verbosity
>= 0 && opt
->verbosity
<= 5);
4855 assert(opt
->buffer_output
<= 2);
4856 assert(opt
->obuf
.len
== 0);
4858 assert(opt
->priv
== NULL
);
4859 if (result
->_properly_initialized
!= 0 &&
4860 result
->_properly_initialized
!= RESULT_INITIALIZED
)
4861 BUG("struct merge_result passed to merge_incore_*recursive() must be zeroed or filled with values from a previous run");
4862 assert(!!result
->priv
== !!result
->_properly_initialized
);
4864 opt
->priv
= result
->priv
;
4865 result
->priv
= NULL
;
4867 * opt->priv non-NULL means we had results from a previous
4868 * run; do a few sanity checks that user didn't mess with
4869 * it in an obvious fashion.
4871 assert(opt
->priv
->call_depth
== 0);
4872 assert(!opt
->priv
->toplevel_dir
||
4873 0 == strlen(opt
->priv
->toplevel_dir
));
4875 trace2_region_leave("merge", "sanity checks", opt
->repo
);
4877 /* Default to histogram diff. Actually, just hardcode it...for now. */
4878 opt
->xdl_opts
= DIFF_WITH_ALG(opt
, HISTOGRAM_DIFF
);
4880 /* Handle attr direction stuff for renormalization */
4881 if (opt
->renormalize
)
4882 git_attr_set_direction(GIT_ATTR_CHECKOUT
);
4884 /* Initialization of opt->priv, our internal merge data */
4885 trace2_region_enter("merge", "allocate/init", opt
->repo
);
4887 clear_or_reinit_internal_opts(opt
->priv
, 1);
4888 string_list_init_nodup(&opt
->priv
->conflicted_submodules
);
4889 trace2_region_leave("merge", "allocate/init", opt
->repo
);
4892 opt
->priv
= xcalloc(1, sizeof(*opt
->priv
));
4894 /* Initialization of various renames fields */
4895 renames
= &opt
->priv
->renames
;
4896 mem_pool_init(&opt
->priv
->pool
, 0);
4897 pool
= &opt
->priv
->pool
;
4898 for (i
= MERGE_SIDE1
; i
<= MERGE_SIDE2
; i
++) {
4899 strintmap_init_with_options(&renames
->dirs_removed
[i
],
4900 NOT_RELEVANT
, pool
, 0);
4901 strmap_init_with_options(&renames
->dir_rename_count
[i
],
4903 strmap_init_with_options(&renames
->dir_renames
[i
],
4906 * relevant_sources uses -1 for the default, because we need
4907 * to be able to distinguish not-in-strintmap from valid
4908 * relevant_source values from enum file_rename_relevance.
4909 * In particular, possibly_cache_new_pair() expects a negative
4910 * value for not-found entries.
4912 strintmap_init_with_options(&renames
->relevant_sources
[i
],
4913 -1 /* explicitly invalid */,
4915 strmap_init_with_options(&renames
->cached_pairs
[i
],
4917 strset_init_with_options(&renames
->cached_irrelevant
[i
],
4919 strset_init_with_options(&renames
->cached_target_names
[i
],
4922 for (i
= MERGE_SIDE1
; i
<= MERGE_SIDE2
; i
++) {
4923 strintmap_init_with_options(&renames
->deferred
[i
].possible_trivial_merges
,
4925 strset_init_with_options(&renames
->deferred
[i
].target_dirs
,
4927 renames
->deferred
[i
].trivial_merges_okay
= 1; /* 1 == maybe */
4931 * Although we initialize opt->priv->paths with strdup_strings=0,
4932 * that's just to avoid making yet another copy of an allocated
4933 * string. Putting the entry into paths means we are taking
4934 * ownership, so we will later free it.
4936 * In contrast, conflicted just has a subset of keys from paths, so
4937 * we don't want to free those (it'd be a duplicate free).
4939 strmap_init_with_options(&opt
->priv
->paths
, pool
, 0);
4940 strmap_init_with_options(&opt
->priv
->conflicted
, pool
, 0);
4943 * keys & string_lists in conflicts will sometimes need to outlive
4944 * "paths", so it will have a copy of relevant keys. It's probably
4945 * a small subset of the overall paths that have special output.
4947 strmap_init(&opt
->priv
->conflicts
);
4949 trace2_region_leave("merge", "allocate/init", opt
->repo
);
4952 static void merge_check_renames_reusable(struct merge_result
*result
,
4953 struct tree
*merge_base
,
4957 struct rename_info
*renames
;
4958 struct tree
**merge_trees
;
4959 struct merge_options_internal
*opti
= result
->priv
;
4964 renames
= &opti
->renames
;
4965 merge_trees
= renames
->merge_trees
;
4968 * Handle case where previous merge operation did not want cache to
4969 * take effect, e.g. because rename/rename(1to1) makes it invalid.
4971 if (!merge_trees
[0]) {
4972 assert(!merge_trees
[0] && !merge_trees
[1] && !merge_trees
[2]);
4973 renames
->cached_pairs_valid_side
= 0; /* neither side valid */
4978 * Handle other cases; note that merge_trees[0..2] will only
4979 * be NULL if opti is, or if all three were manually set to
4980 * NULL by e.g. rename/rename(1to1) handling.
4982 assert(merge_trees
[0] && merge_trees
[1] && merge_trees
[2]);
4984 /* Check if we meet a condition for re-using cached_pairs */
4985 if (oideq(&merge_base
->object
.oid
, &merge_trees
[2]->object
.oid
) &&
4986 oideq(&side1
->object
.oid
, &result
->tree
->object
.oid
))
4987 renames
->cached_pairs_valid_side
= MERGE_SIDE1
;
4988 else if (oideq(&merge_base
->object
.oid
, &merge_trees
[1]->object
.oid
) &&
4989 oideq(&side2
->object
.oid
, &result
->tree
->object
.oid
))
4990 renames
->cached_pairs_valid_side
= MERGE_SIDE2
;
4992 renames
->cached_pairs_valid_side
= 0; /* neither side valid */
4995 /*** Function Grouping: merge_incore_*() and their internal variants ***/
4998 * Originally from merge_trees_internal(); heavily adapted, though.
5000 static void merge_ort_nonrecursive_internal(struct merge_options
*opt
,
5001 struct tree
*merge_base
,
5004 struct merge_result
*result
)
5006 struct object_id working_tree_oid
;
5008 if (opt
->subtree_shift
) {
5009 side2
= shift_tree_object(opt
->repo
, side1
, side2
,
5010 opt
->subtree_shift
);
5011 merge_base
= shift_tree_object(opt
->repo
, side1
, merge_base
,
5012 opt
->subtree_shift
);
5016 trace2_region_enter("merge", "collect_merge_info", opt
->repo
);
5017 if (collect_merge_info(opt
, merge_base
, side1
, side2
) != 0) {
5019 * TRANSLATORS: The %s arguments are: 1) tree hash of a merge
5020 * base, and 2-3) the trees for the two trees we're merging.
5022 error(_("collecting merge info failed for trees %s, %s, %s"),
5023 oid_to_hex(&merge_base
->object
.oid
),
5024 oid_to_hex(&side1
->object
.oid
),
5025 oid_to_hex(&side2
->object
.oid
));
5029 trace2_region_leave("merge", "collect_merge_info", opt
->repo
);
5031 trace2_region_enter("merge", "renames", opt
->repo
);
5032 result
->clean
= detect_and_process_renames(opt
);
5033 trace2_region_leave("merge", "renames", opt
->repo
);
5034 if (opt
->priv
->renames
.redo_after_renames
== 2) {
5035 trace2_region_enter("merge", "reset_maps", opt
->repo
);
5036 clear_or_reinit_internal_opts(opt
->priv
, 1);
5037 trace2_region_leave("merge", "reset_maps", opt
->repo
);
5041 trace2_region_enter("merge", "process_entries", opt
->repo
);
5042 if (process_entries(opt
, &working_tree_oid
) < 0)
5044 trace2_region_leave("merge", "process_entries", opt
->repo
);
5046 /* Set return values */
5047 result
->path_messages
= &opt
->priv
->conflicts
;
5049 if (result
->clean
>= 0) {
5050 result
->tree
= parse_tree_indirect(&working_tree_oid
);
5051 /* existence of conflicted entries implies unclean */
5052 result
->clean
&= strmap_empty(&opt
->priv
->conflicted
);
5054 if (!opt
->priv
->call_depth
) {
5055 result
->priv
= opt
->priv
;
5056 result
->_properly_initialized
= RESULT_INITIALIZED
;
5062 * Originally from merge_recursive_internal(); somewhat adapted, though.
5064 static void merge_ort_internal(struct merge_options
*opt
,
5065 struct commit_list
*merge_bases
,
5068 struct merge_result
*result
)
5070 struct commit
*next
;
5071 struct commit
*merged_merge_bases
;
5072 const char *ancestor_name
;
5073 struct strbuf merge_base_abbrev
= STRBUF_INIT
;
5076 if (repo_get_merge_bases(the_repository
, h1
, h2
,
5077 &merge_bases
) < 0) {
5081 /* See merge-ort.h:merge_incore_recursive() declaration NOTE */
5082 merge_bases
= reverse_commit_list(merge_bases
);
5085 merged_merge_bases
= pop_commit(&merge_bases
);
5086 if (!merged_merge_bases
) {
5087 /* if there is no common ancestor, use an empty tree */
5090 tree
= lookup_tree(opt
->repo
, opt
->repo
->hash_algo
->empty_tree
);
5091 merged_merge_bases
= make_virtual_commit(opt
->repo
, tree
,
5093 ancestor_name
= "empty tree";
5094 } else if (merge_bases
) {
5095 ancestor_name
= "merged common ancestors";
5097 strbuf_add_unique_abbrev(&merge_base_abbrev
,
5098 &merged_merge_bases
->object
.oid
,
5100 ancestor_name
= merge_base_abbrev
.buf
;
5103 for (next
= pop_commit(&merge_bases
); next
;
5104 next
= pop_commit(&merge_bases
)) {
5105 const char *saved_b1
, *saved_b2
;
5106 struct commit
*prev
= merged_merge_bases
;
5108 opt
->priv
->call_depth
++;
5110 * When the merge fails, the result contains files
5111 * with conflict markers. The cleanness flag is
5112 * ignored (unless indicating an error), it was never
5113 * actually used, as result of merge_trees has always
5114 * overwritten it: the committed "conflicts" were
5117 saved_b1
= opt
->branch1
;
5118 saved_b2
= opt
->branch2
;
5119 opt
->branch1
= "Temporary merge branch 1";
5120 opt
->branch2
= "Temporary merge branch 2";
5121 merge_ort_internal(opt
, NULL
, prev
, next
, result
);
5122 if (result
->clean
< 0)
5124 opt
->branch1
= saved_b1
;
5125 opt
->branch2
= saved_b2
;
5126 opt
->priv
->call_depth
--;
5128 merged_merge_bases
= make_virtual_commit(opt
->repo
,
5131 commit_list_insert(prev
, &merged_merge_bases
->parents
);
5132 commit_list_insert(next
, &merged_merge_bases
->parents
->next
);
5134 clear_or_reinit_internal_opts(opt
->priv
, 1);
5137 opt
->ancestor
= ancestor_name
;
5138 merge_ort_nonrecursive_internal(opt
,
5139 repo_get_commit_tree(opt
->repo
,
5140 merged_merge_bases
),
5141 repo_get_commit_tree(opt
->repo
, h1
),
5142 repo_get_commit_tree(opt
->repo
, h2
),
5144 strbuf_release(&merge_base_abbrev
);
5145 opt
->ancestor
= NULL
; /* avoid accidental re-use of opt->ancestor */
5148 void merge_incore_nonrecursive(struct merge_options
*opt
,
5149 struct tree
*merge_base
,
5152 struct merge_result
*result
)
5154 trace2_region_enter("merge", "incore_nonrecursive", opt
->repo
);
5156 trace2_region_enter("merge", "merge_start", opt
->repo
);
5157 assert(opt
->ancestor
!= NULL
);
5158 merge_check_renames_reusable(result
, merge_base
, side1
, side2
);
5159 merge_start(opt
, result
);
5161 * Record the trees used in this merge, so if there's a next merge in
5162 * a cherry-pick or rebase sequence it might be able to take advantage
5163 * of the cached_pairs in that next merge.
5165 opt
->priv
->renames
.merge_trees
[0] = merge_base
;
5166 opt
->priv
->renames
.merge_trees
[1] = side1
;
5167 opt
->priv
->renames
.merge_trees
[2] = side2
;
5168 trace2_region_leave("merge", "merge_start", opt
->repo
);
5170 merge_ort_nonrecursive_internal(opt
, merge_base
, side1
, side2
, result
);
5171 trace2_region_leave("merge", "incore_nonrecursive", opt
->repo
);
5174 void merge_incore_recursive(struct merge_options
*opt
,
5175 struct commit_list
*merge_bases
,
5176 struct commit
*side1
,
5177 struct commit
*side2
,
5178 struct merge_result
*result
)
5180 trace2_region_enter("merge", "incore_recursive", opt
->repo
);
5182 /* We set the ancestor label based on the merge_bases */
5183 assert(opt
->ancestor
== NULL
);
5185 trace2_region_enter("merge", "merge_start", opt
->repo
);
5186 merge_start(opt
, result
);
5187 trace2_region_leave("merge", "merge_start", opt
->repo
);
5189 merge_ort_internal(opt
, merge_bases
, side1
, side2
, result
);
5190 trace2_region_leave("merge", "incore_recursive", opt
->repo
);