2 * "Ostensibly Recursive's Twin" merge strategy, or "ort" for short. Meant
3 * as a drop-in replacement for the "recursive" merge strategy, allowing one
6 * git merge [-s recursive]
12 * Note: git's parser allows the space between '-s' and its argument to be
13 * missing. (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo",
14 * "cale", "peedy", or "ins" instead of "ort"?)
18 #include "merge-ort.h"
22 #include "cache-tree.h"
24 #include "commit-reach.h"
29 #include "object-store.h"
32 #include "submodule.h"
34 #include "unpack-trees.h"
35 #include "xdiff-interface.h"
38 * We have many arrays of size 3. Whenever we have such an array, the
39 * indices refer to one of the sides of the three-way merge. This is so
40 * pervasive that the constants 0, 1, and 2 are used in many places in the
41 * code (especially in arithmetic operations to find the other side's index
42 * or to compute a relevant mask), but sometimes these enum names are used
43 * to aid code clarity.
45 * See also 'filemask' and 'dirmask' in struct conflict_info; the "ith side"
46 * referred to there is one of these three sides.
56 * All variables that are arrays of size 3 correspond to data tracked
57 * for the sides in enum merge_side. Index 0 is almost always unused
58 * because we often only need to track information for MERGE_SIDE1 and
59 * MERGE_SIDE2 (MERGE_BASE can't have rename information since renames
60 * are determined relative to what changed since the MERGE_BASE).
64 * pairs: pairing of filenames from diffcore_rename()
66 struct diff_queue_struct pairs
[3];
69 * dirs_removed: directories removed on a given side of history.
71 struct strset dirs_removed
[3];
74 * dir_rename_count: tracking where parts of a directory were renamed to
76 * When files in a directory are renamed, they may not all go to the
77 * same location. Each strmap here tracks:
78 * old_dir => {new_dir => int}
79 * That is, dir_rename_count[side] is a strmap to a strintmap.
81 struct strmap dir_rename_count
[3];
84 * dir_renames: computed directory renames
86 * This is a map of old_dir => new_dir and is derived in part from
89 struct strmap dir_renames
[3];
92 * needed_limit: value needed for inexact rename detection to run
94 * If the current rename limit wasn't high enough for inexact
95 * rename detection to run, this records the limit needed. Otherwise,
96 * this value remains 0.
101 struct merge_options_internal
{
103 * paths: primary data structure in all of merge ort.
106 * * are full relative paths from the toplevel of the repository
107 * (e.g. "drivers/firmware/raspberrypi.c").
108 * * store all relevant paths in the repo, both directories and
109 * files (e.g. drivers, drivers/firmware would also be included)
110 * * these keys serve to intern all the path strings, which allows
111 * us to do pointer comparison on directory names instead of
112 * strcmp; we just have to be careful to use the interned strings.
113 * (Technically paths_to_free may track some strings that were
114 * removed from froms paths.)
116 * The values of paths:
117 * * either a pointer to a merged_info, or a conflict_info struct
118 * * merged_info contains all relevant information for a
119 * non-conflicted entry.
120 * * conflict_info contains a merged_info, plus any additional
121 * information about a conflict such as the higher orders stages
122 * involved and the names of the paths those came from (handy
123 * once renames get involved).
124 * * a path may start "conflicted" (i.e. point to a conflict_info)
125 * and then a later step (e.g. three-way content merge) determines
126 * it can be cleanly merged, at which point it'll be marked clean
127 * and the algorithm will ignore any data outside the contained
128 * merged_info for that entry
129 * * If an entry remains conflicted, the merged_info portion of a
130 * conflict_info will later be filled with whatever version of
131 * the file should be placed in the working directory (e.g. an
132 * as-merged-as-possible variation that contains conflict markers).
137 * conflicted: a subset of keys->values from "paths"
139 * conflicted is basically an optimization between process_entries()
140 * and record_conflicted_index_entries(); the latter could loop over
141 * ALL the entries in paths AGAIN and look for the ones that are
142 * still conflicted, but since process_entries() has to loop over
143 * all of them, it saves the ones it couldn't resolve in this strmap
144 * so that record_conflicted_index_entries() can iterate just the
147 struct strmap conflicted
;
150 * paths_to_free: additional list of strings to free
152 * If keys are removed from "paths", they are added to paths_to_free
153 * to ensure they are later freed. We avoid free'ing immediately since
154 * other places (e.g. conflict_info.pathnames[]) may still be
155 * referencing these paths.
157 struct string_list paths_to_free
;
160 * output: special messages and conflict notices for various paths
162 * This is a map of pathnames (a subset of the keys in "paths" above)
163 * to strbufs. It gathers various warning/conflict/notice messages
164 * for later processing.
166 struct strmap output
;
169 * renames: various data relating to rename detection
171 struct rename_info renames
;
174 * current_dir_name, toplevel_dir: temporary vars
176 * These are used in collect_merge_info_callback(), and will set the
177 * various merged_info.directory_name for the various paths we get;
178 * see documentation for that variable and the requirements placed on
181 const char *current_dir_name
;
182 const char *toplevel_dir
;
184 /* call_depth: recursion level counter for merging merge bases */
188 struct version_info
{
189 struct object_id oid
;
194 /* if is_null, ignore result. otherwise result has oid & mode */
195 struct version_info result
;
199 * clean: whether the path in question is cleanly merged.
201 * see conflict_info.merged for more details.
206 * basename_offset: offset of basename of path.
208 * perf optimization to avoid recomputing offset of final '/'
209 * character in pathname (0 if no '/' in pathname).
211 size_t basename_offset
;
214 * directory_name: containing directory name.
216 * Note that we assume directory_name is constructed such that
217 * strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name,
218 * i.e. string equality is equivalent to pointer equality. For this
219 * to hold, we have to be careful setting directory_name.
221 const char *directory_name
;
224 struct conflict_info
{
226 * merged: the version of the path that will be written to working tree
228 * WARNING: It is critical to check merged.clean and ensure it is 0
229 * before reading any conflict_info fields outside of merged.
230 * Allocated merge_info structs will always have clean set to 1.
231 * Allocated conflict_info structs will have merged.clean set to 0
232 * initially. The merged.clean field is how we know if it is safe
233 * to access other parts of conflict_info besides merged; if a
234 * conflict_info's merged.clean is changed to 1, the rest of the
235 * algorithm is not allowed to look at anything outside of the
236 * merged member anymore.
238 struct merged_info merged
;
240 /* oids & modes from each of the three trees for this path */
241 struct version_info stages
[3];
243 /* pathnames for each stage; may differ due to rename detection */
244 const char *pathnames
[3];
246 /* Whether this path is/was involved in a directory/file conflict */
247 unsigned df_conflict
:1;
250 * Whether this path is/was involved in a non-content conflict other
251 * than a directory/file conflict (e.g. rename/rename, rename/delete,
252 * file location based on possible directory rename).
254 unsigned path_conflict
:1;
257 * For filemask and dirmask, the ith bit corresponds to whether the
258 * ith entry is a file (filemask) or a directory (dirmask). Thus,
259 * filemask & dirmask is always zero, and filemask | dirmask is at
260 * most 7 but can be less when a path does not appear as either a
261 * file or a directory on at least one side of history.
263 * Note that these masks are related to enum merge_side, as the ith
264 * entry corresponds to side i.
266 * These values come from a traverse_trees() call; more info may be
267 * found looking at tree-walk.h's struct traverse_info,
268 * particularly the documentation above the "fn" member (note that
269 * filemask = mask & ~dirmask from that documentation).
275 * Optimization to track which stages match, to avoid the need to
276 * recompute it in multiple steps. Either 0 or at least 2 bits are
277 * set; if at least 2 bits are set, their corresponding stages match.
279 unsigned match_mask
:3;
282 /*** Function Grouping: various utility functions ***/
285 * For the next three macros, see warning for conflict_info.merged.
287 * In each of the below, mi is a struct merged_info*, and ci was defined
288 * as a struct conflict_info* (but we need to verify ci isn't actually
289 * pointed at a struct merged_info*).
291 * INITIALIZE_CI: Assign ci to mi but only if it's safe; set to NULL otherwise.
292 * VERIFY_CI: Ensure that something we assigned to a conflict_info* is one.
293 * ASSIGN_AND_VERIFY_CI: Similar to VERIFY_CI but do assignment first.
295 #define INITIALIZE_CI(ci, mi) do { \
296 (ci) = (!(mi) || (mi)->clean) ? NULL : (struct conflict_info *)(mi); \
298 #define VERIFY_CI(ci) assert(ci && !ci->merged.clean);
299 #define ASSIGN_AND_VERIFY_CI(ci, mi) do { \
300 (ci) = (struct conflict_info *)(mi); \
301 assert((ci) && !(mi)->clean); \
304 static void free_strmap_strings(struct strmap
*map
)
306 struct hashmap_iter iter
;
307 struct strmap_entry
*entry
;
309 strmap_for_each_entry(map
, &iter
, entry
) {
310 free((char*)entry
->key
);
314 static void clear_or_reinit_internal_opts(struct merge_options_internal
*opti
,
317 struct rename_info
*renames
= &opti
->renames
;
319 void (*strmap_func
)(struct strmap
*, int) =
320 reinitialize
? strmap_partial_clear
: strmap_clear
;
321 void (*strset_func
)(struct strset
*) =
322 reinitialize
? strset_partial_clear
: strset_clear
;
325 * We marked opti->paths with strdup_strings = 0, so that we
326 * wouldn't have to make another copy of the fullpath created by
327 * make_traverse_path from setup_path_info(). But, now that we've
328 * used it and have no other references to these strings, it is time
329 * to deallocate them.
331 free_strmap_strings(&opti
->paths
);
332 strmap_func(&opti
->paths
, 1);
335 * All keys and values in opti->conflicted are a subset of those in
336 * opti->paths. We don't want to deallocate anything twice, so we
337 * don't free the keys and we pass 0 for free_values.
339 strmap_func(&opti
->conflicted
, 0);
342 * opti->paths_to_free is similar to opti->paths; we created it with
343 * strdup_strings = 0 to avoid making _another_ copy of the fullpath
344 * but now that we've used it and have no other references to these
345 * strings, it is time to deallocate them. We do so by temporarily
346 * setting strdup_strings to 1.
348 opti
->paths_to_free
.strdup_strings
= 1;
349 string_list_clear(&opti
->paths_to_free
, 0);
350 opti
->paths_to_free
.strdup_strings
= 0;
352 /* Free memory used by various renames maps */
353 for (i
= MERGE_SIDE1
; i
<= MERGE_SIDE2
; ++i
) {
354 strset_func(&renames
->dirs_removed
[i
]);
356 partial_clear_dir_rename_count(&renames
->dir_rename_count
[i
]);
358 strmap_clear(&renames
->dir_rename_count
[i
], 1);
360 strmap_func(&renames
->dir_renames
[i
], 0);
364 struct hashmap_iter iter
;
365 struct strmap_entry
*e
;
367 /* Release and free each strbuf found in output */
368 strmap_for_each_entry(&opti
->output
, &iter
, e
) {
369 struct strbuf
*sb
= e
->value
;
372 * While strictly speaking we don't need to free(sb)
373 * here because we could pass free_values=1 when
374 * calling strmap_clear() on opti->output, that would
375 * require strmap_clear to do another
376 * strmap_for_each_entry() loop, so we just free it
377 * while we're iterating anyway.
381 strmap_clear(&opti
->output
, 0);
385 static int err(struct merge_options
*opt
, const char *err
, ...)
388 struct strbuf sb
= STRBUF_INIT
;
390 strbuf_addstr(&sb
, "error: ");
391 va_start(params
, err
);
392 strbuf_vaddf(&sb
, err
, params
);
401 static void format_commit(struct strbuf
*sb
,
403 struct commit
*commit
)
405 struct merge_remote_desc
*desc
;
406 struct pretty_print_context ctx
= {0};
407 ctx
.abbrev
= DEFAULT_ABBREV
;
409 strbuf_addchars(sb
, ' ', indent
);
410 desc
= merge_remote_util(commit
);
412 strbuf_addf(sb
, "virtual %s\n", desc
->name
);
416 format_commit_message(commit
, "%h %s", sb
, &ctx
);
417 strbuf_addch(sb
, '\n');
420 __attribute__((format (printf
, 4, 5)))
421 static void path_msg(struct merge_options
*opt
,
423 int omittable_hint
, /* skippable under --remerge-diff */
424 const char *fmt
, ...)
427 struct strbuf
*sb
= strmap_get(&opt
->priv
->output
, path
);
429 sb
= xmalloc(sizeof(*sb
));
431 strmap_put(&opt
->priv
->output
, path
, sb
);
435 strbuf_vaddf(sb
, fmt
, ap
);
438 strbuf_addch(sb
, '\n');
441 /* add a string to a strbuf, but converting "/" to "_" */
442 static void add_flattened_path(struct strbuf
*out
, const char *s
)
445 strbuf_addstr(out
, s
);
446 for (; i
< out
->len
; i
++)
447 if (out
->buf
[i
] == '/')
451 static char *unique_path(struct strmap
*existing_paths
,
455 struct strbuf newpath
= STRBUF_INIT
;
459 strbuf_addf(&newpath
, "%s~", path
);
460 add_flattened_path(&newpath
, branch
);
462 base_len
= newpath
.len
;
463 while (strmap_contains(existing_paths
, newpath
.buf
)) {
464 strbuf_setlen(&newpath
, base_len
);
465 strbuf_addf(&newpath
, "_%d", suffix
++);
468 return strbuf_detach(&newpath
, NULL
);
471 /*** Function Grouping: functions related to collect_merge_info() ***/
473 static void setup_path_info(struct merge_options
*opt
,
474 struct string_list_item
*result
,
475 const char *current_dir_name
,
476 int current_dir_name_len
,
477 char *fullpath
, /* we'll take over ownership */
478 struct name_entry
*names
,
479 struct name_entry
*merged_version
,
480 unsigned is_null
, /* boolean */
481 unsigned df_conflict
, /* boolean */
484 int resolved
/* boolean */)
486 /* result->util is void*, so mi is a convenience typed variable */
487 struct merged_info
*mi
;
489 assert(!is_null
|| resolved
);
490 assert(!df_conflict
|| !resolved
); /* df_conflict implies !resolved */
491 assert(resolved
== (merged_version
!= NULL
));
493 mi
= xcalloc(1, resolved
? sizeof(struct merged_info
) :
494 sizeof(struct conflict_info
));
495 mi
->directory_name
= current_dir_name
;
496 mi
->basename_offset
= current_dir_name_len
;
497 mi
->clean
= !!resolved
;
499 mi
->result
.mode
= merged_version
->mode
;
500 oidcpy(&mi
->result
.oid
, &merged_version
->oid
);
501 mi
->is_null
= !!is_null
;
504 struct conflict_info
*ci
;
506 ASSIGN_AND_VERIFY_CI(ci
, mi
);
507 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
508 ci
->pathnames
[i
] = fullpath
;
509 ci
->stages
[i
].mode
= names
[i
].mode
;
510 oidcpy(&ci
->stages
[i
].oid
, &names
[i
].oid
);
512 ci
->filemask
= filemask
;
513 ci
->dirmask
= dirmask
;
514 ci
->df_conflict
= !!df_conflict
;
517 * Assume is_null for now, but if we have entries
518 * under the directory then when it is complete in
519 * write_completed_directory() it'll update this.
520 * Also, for D/F conflicts, we have to handle the
521 * directory first, then clear this bit and process
522 * the file to see how it is handled -- that occurs
523 * near the top of process_entry().
527 strmap_put(&opt
->priv
->paths
, fullpath
, mi
);
528 result
->string
= fullpath
;
532 static void add_pair(struct merge_options
*opt
,
533 struct name_entry
*names
,
534 const char *pathname
,
536 unsigned is_add
/* if false, is_delete */)
538 struct diff_filespec
*one
, *two
;
539 struct rename_info
*renames
= &opt
->priv
->renames
;
540 int names_idx
= is_add
? side
: 0;
542 one
= alloc_filespec(pathname
);
543 two
= alloc_filespec(pathname
);
544 fill_filespec(is_add
? two
: one
,
545 &names
[names_idx
].oid
, 1, names
[names_idx
].mode
);
546 diff_queue(&renames
->pairs
[side
], one
, two
);
549 static void collect_rename_info(struct merge_options
*opt
,
550 struct name_entry
*names
,
552 const char *fullname
,
557 struct rename_info
*renames
= &opt
->priv
->renames
;
560 /* Update dirs_removed, as needed */
561 if (dirmask
== 1 || dirmask
== 3 || dirmask
== 5) {
562 /* absent_mask = 0x07 - dirmask; sides = absent_mask/2 */
563 unsigned sides
= (0x07 - dirmask
)/2;
565 strset_add(&renames
->dirs_removed
[1], fullname
);
567 strset_add(&renames
->dirs_removed
[2], fullname
);
570 if (filemask
== 0 || filemask
== 7)
573 for (side
= MERGE_SIDE1
; side
<= MERGE_SIDE2
; ++side
) {
574 unsigned side_mask
= (1 << side
);
576 /* Check for deletion on side */
577 if ((filemask
& 1) && !(filemask
& side_mask
))
578 add_pair(opt
, names
, fullname
, side
, 0 /* delete */);
580 /* Check for addition on side */
581 if (!(filemask
& 1) && (filemask
& side_mask
))
582 add_pair(opt
, names
, fullname
, side
, 1 /* add */);
586 static int collect_merge_info_callback(int n
,
588 unsigned long dirmask
,
589 struct name_entry
*names
,
590 struct traverse_info
*info
)
594 * common ancestor (mbase) has mask 1, and stored in index 0 of names
595 * head of side 1 (side1) has mask 2, and stored in index 1 of names
596 * head of side 2 (side2) has mask 4, and stored in index 2 of names
598 struct merge_options
*opt
= info
->data
;
599 struct merge_options_internal
*opti
= opt
->priv
;
600 struct string_list_item pi
; /* Path Info */
601 struct conflict_info
*ci
; /* typed alias to pi.util (which is void*) */
602 struct name_entry
*p
;
605 const char *dirname
= opti
->current_dir_name
;
606 unsigned filemask
= mask
& ~dirmask
;
607 unsigned match_mask
= 0; /* will be updated below */
608 unsigned mbase_null
= !(mask
& 1);
609 unsigned side1_null
= !(mask
& 2);
610 unsigned side2_null
= !(mask
& 4);
611 unsigned side1_matches_mbase
= (!side1_null
&& !mbase_null
&&
612 names
[0].mode
== names
[1].mode
&&
613 oideq(&names
[0].oid
, &names
[1].oid
));
614 unsigned side2_matches_mbase
= (!side2_null
&& !mbase_null
&&
615 names
[0].mode
== names
[2].mode
&&
616 oideq(&names
[0].oid
, &names
[2].oid
));
617 unsigned sides_match
= (!side1_null
&& !side2_null
&&
618 names
[1].mode
== names
[2].mode
&&
619 oideq(&names
[1].oid
, &names
[2].oid
));
622 * Note: When a path is a file on one side of history and a directory
623 * in another, we have a directory/file conflict. In such cases, if
624 * the conflict doesn't resolve from renames and deletions, then we
625 * always leave directories where they are and move files out of the
626 * way. Thus, while struct conflict_info has a df_conflict field to
627 * track such conflicts, we ignore that field for any directories at
628 * a path and only pay attention to it for files at the given path.
629 * The fact that we leave directories were they are also means that
630 * we do not need to worry about getting additional df_conflict
631 * information propagated from parent directories down to children
632 * (unlike, say traverse_trees_recursive() in unpack-trees.c, which
633 * sets a newinfo.df_conflicts field specifically to propagate it).
635 unsigned df_conflict
= (filemask
!= 0) && (dirmask
!= 0);
637 /* n = 3 is a fundamental assumption. */
639 BUG("Called collect_merge_info_callback wrong");
642 * A bunch of sanity checks verifying that traverse_trees() calls
643 * us the way I expect. Could just remove these at some point,
644 * though maybe they are helpful to future code readers.
646 assert(mbase_null
== is_null_oid(&names
[0].oid
));
647 assert(side1_null
== is_null_oid(&names
[1].oid
));
648 assert(side2_null
== is_null_oid(&names
[2].oid
));
649 assert(!mbase_null
|| !side1_null
|| !side2_null
);
650 assert(mask
> 0 && mask
< 8);
652 /* Determine match_mask */
653 if (side1_matches_mbase
)
654 match_mask
= (side2_matches_mbase
? 7 : 3);
655 else if (side2_matches_mbase
)
657 else if (sides_match
)
661 * Get the name of the relevant filepath, which we'll pass to
662 * setup_path_info() for tracking.
667 len
= traverse_path_len(info
, p
->pathlen
);
669 /* +1 in both of the following lines to include the NUL byte */
670 fullpath
= xmalloc(len
+ 1);
671 make_traverse_path(fullpath
, len
+ 1, info
, p
->path
, p
->pathlen
);
674 * If mbase, side1, and side2 all match, we can resolve early. Even
675 * if these are trees, there will be no renames or anything
678 if (side1_matches_mbase
&& side2_matches_mbase
) {
679 /* mbase, side1, & side2 all match; use mbase as resolution */
680 setup_path_info(opt
, &pi
, dirname
, info
->pathlen
, fullpath
,
681 names
, names
+0, mbase_null
, 0,
682 filemask
, dirmask
, 1);
687 * Gather additional information used in rename detection.
689 collect_rename_info(opt
, names
, dirname
, fullpath
,
690 filemask
, dirmask
, match_mask
);
693 * Record information about the path so we can resolve later in
696 setup_path_info(opt
, &pi
, dirname
, info
->pathlen
, fullpath
,
697 names
, NULL
, 0, df_conflict
, filemask
, dirmask
, 0);
701 ci
->match_mask
= match_mask
;
703 /* If dirmask, recurse into subdirectories */
705 struct traverse_info newinfo
;
706 struct tree_desc t
[3];
707 void *buf
[3] = {NULL
, NULL
, NULL
};
708 const char *original_dir_name
;
711 ci
->match_mask
&= filemask
;
714 newinfo
.name
= p
->path
;
715 newinfo
.namelen
= p
->pathlen
;
716 newinfo
.pathlen
= st_add3(newinfo
.pathlen
, p
->pathlen
, 1);
718 * If this directory we are about to recurse into cared about
719 * its parent directory (the current directory) having a D/F
720 * conflict, then we'd propagate the masks in this way:
721 * newinfo.df_conflicts |= (mask & ~dirmask);
722 * But we don't worry about propagating D/F conflicts. (See
723 * comment near setting of local df_conflict variable near
724 * the beginning of this function).
727 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
728 if (i
== 1 && side1_matches_mbase
)
730 else if (i
== 2 && side2_matches_mbase
)
732 else if (i
== 2 && sides_match
)
735 const struct object_id
*oid
= NULL
;
738 buf
[i
] = fill_tree_descriptor(opt
->repo
,
744 original_dir_name
= opti
->current_dir_name
;
745 opti
->current_dir_name
= pi
.string
;
746 ret
= traverse_trees(NULL
, 3, t
, &newinfo
);
747 opti
->current_dir_name
= original_dir_name
;
749 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++)
759 static int collect_merge_info(struct merge_options
*opt
,
760 struct tree
*merge_base
,
765 struct tree_desc t
[3];
766 struct traverse_info info
;
768 opt
->priv
->toplevel_dir
= "";
769 opt
->priv
->current_dir_name
= opt
->priv
->toplevel_dir
;
770 setup_traverse_info(&info
, opt
->priv
->toplevel_dir
);
771 info
.fn
= collect_merge_info_callback
;
773 info
.show_all_errors
= 1;
775 parse_tree(merge_base
);
778 init_tree_desc(t
+ 0, merge_base
->buffer
, merge_base
->size
);
779 init_tree_desc(t
+ 1, side1
->buffer
, side1
->size
);
780 init_tree_desc(t
+ 2, side2
->buffer
, side2
->size
);
782 trace2_region_enter("merge", "traverse_trees", opt
->repo
);
783 ret
= traverse_trees(NULL
, 3, t
, &info
);
784 trace2_region_leave("merge", "traverse_trees", opt
->repo
);
789 /*** Function Grouping: functions related to threeway content merges ***/
791 static int find_first_merges(struct repository
*repo
,
795 struct object_array
*result
)
798 struct object_array merges
= OBJECT_ARRAY_INIT
;
799 struct commit
*commit
;
800 int contains_another
;
802 char merged_revision
[GIT_MAX_HEXSZ
+ 2];
803 const char *rev_args
[] = { "rev-list", "--merges", "--ancestry-path",
804 "--all", merged_revision
, NULL
};
805 struct rev_info revs
;
806 struct setup_revision_opt rev_opts
;
808 memset(result
, 0, sizeof(struct object_array
));
809 memset(&rev_opts
, 0, sizeof(rev_opts
));
811 /* get all revisions that merge commit a */
812 xsnprintf(merged_revision
, sizeof(merged_revision
), "^%s",
813 oid_to_hex(&a
->object
.oid
));
814 repo_init_revisions(repo
, &revs
, NULL
);
815 rev_opts
.submodule
= path
;
816 /* FIXME: can't handle linked worktrees in submodules yet */
817 revs
.single_worktree
= path
!= NULL
;
818 setup_revisions(ARRAY_SIZE(rev_args
)-1, rev_args
, &revs
, &rev_opts
);
820 /* save all revisions from the above list that contain b */
821 if (prepare_revision_walk(&revs
))
822 die("revision walk setup failed");
823 while ((commit
= get_revision(&revs
)) != NULL
) {
824 struct object
*o
= &(commit
->object
);
825 if (in_merge_bases(b
, commit
))
826 add_object_array(o
, NULL
, &merges
);
828 reset_revision_walk();
830 /* Now we've got all merges that contain a and b. Prune all
831 * merges that contain another found merge and save them in
834 for (i
= 0; i
< merges
.nr
; i
++) {
835 struct commit
*m1
= (struct commit
*) merges
.objects
[i
].item
;
837 contains_another
= 0;
838 for (j
= 0; j
< merges
.nr
; j
++) {
839 struct commit
*m2
= (struct commit
*) merges
.objects
[j
].item
;
840 if (i
!= j
&& in_merge_bases(m2
, m1
)) {
841 contains_another
= 1;
846 if (!contains_another
)
847 add_object_array(merges
.objects
[i
].item
, NULL
, result
);
850 object_array_clear(&merges
);
854 static int merge_submodule(struct merge_options
*opt
,
856 const struct object_id
*o
,
857 const struct object_id
*a
,
858 const struct object_id
*b
,
859 struct object_id
*result
)
861 struct commit
*commit_o
, *commit_a
, *commit_b
;
863 struct object_array merges
;
864 struct strbuf sb
= STRBUF_INIT
;
867 int search
= !opt
->priv
->call_depth
;
869 /* store fallback answer in result in case we fail */
870 oidcpy(result
, opt
->priv
->call_depth
? o
: a
);
872 /* we can not handle deletion conflicts */
880 if (add_submodule_odb(path
)) {
881 path_msg(opt
, path
, 0,
882 _("Failed to merge submodule %s (not checked out)"),
887 if (!(commit_o
= lookup_commit_reference(opt
->repo
, o
)) ||
888 !(commit_a
= lookup_commit_reference(opt
->repo
, a
)) ||
889 !(commit_b
= lookup_commit_reference(opt
->repo
, b
))) {
890 path_msg(opt
, path
, 0,
891 _("Failed to merge submodule %s (commits not present)"),
896 /* check whether both changes are forward */
897 if (!in_merge_bases(commit_o
, commit_a
) ||
898 !in_merge_bases(commit_o
, commit_b
)) {
899 path_msg(opt
, path
, 0,
900 _("Failed to merge submodule %s "
901 "(commits don't follow merge-base)"),
906 /* Case #1: a is contained in b or vice versa */
907 if (in_merge_bases(commit_a
, commit_b
)) {
909 path_msg(opt
, path
, 1,
910 _("Note: Fast-forwarding submodule %s to %s"),
911 path
, oid_to_hex(b
));
914 if (in_merge_bases(commit_b
, commit_a
)) {
916 path_msg(opt
, path
, 1,
917 _("Note: Fast-forwarding submodule %s to %s"),
918 path
, oid_to_hex(a
));
923 * Case #2: There are one or more merges that contain a and b in
924 * the submodule. If there is only one, then present it as a
925 * suggestion to the user, but leave it marked unmerged so the
926 * user needs to confirm the resolution.
929 /* Skip the search if makes no sense to the calling context. */
933 /* find commit which merges them */
934 parent_count
= find_first_merges(opt
->repo
, path
, commit_a
, commit_b
,
936 switch (parent_count
) {
938 path_msg(opt
, path
, 0, _("Failed to merge submodule %s"), path
);
942 format_commit(&sb
, 4,
943 (struct commit
*)merges
.objects
[0].item
);
944 path_msg(opt
, path
, 0,
945 _("Failed to merge submodule %s, but a possible merge "
946 "resolution exists:\n%s\n"),
948 path_msg(opt
, path
, 1,
949 _("If this is correct simply add it to the index "
952 " git update-index --cacheinfo 160000 %s \"%s\"\n\n"
953 "which will accept this suggestion.\n"),
954 oid_to_hex(&merges
.objects
[0].item
->oid
), path
);
958 for (i
= 0; i
< merges
.nr
; i
++)
959 format_commit(&sb
, 4,
960 (struct commit
*)merges
.objects
[i
].item
);
961 path_msg(opt
, path
, 0,
962 _("Failed to merge submodule %s, but multiple "
963 "possible merges exist:\n%s"), path
, sb
.buf
);
967 object_array_clear(&merges
);
971 static int merge_3way(struct merge_options
*opt
,
973 const struct object_id
*o
,
974 const struct object_id
*a
,
975 const struct object_id
*b
,
976 const char *pathnames
[3],
977 const int extra_marker_size
,
978 mmbuffer_t
*result_buf
)
980 mmfile_t orig
, src1
, src2
;
981 struct ll_merge_options ll_opts
= {0};
982 char *base
, *name1
, *name2
;
985 ll_opts
.renormalize
= opt
->renormalize
;
986 ll_opts
.extra_marker_size
= extra_marker_size
;
987 ll_opts
.xdl_opts
= opt
->xdl_opts
;
989 if (opt
->priv
->call_depth
) {
990 ll_opts
.virtual_ancestor
= 1;
993 switch (opt
->recursive_variant
) {
994 case MERGE_VARIANT_OURS
:
995 ll_opts
.variant
= XDL_MERGE_FAVOR_OURS
;
997 case MERGE_VARIANT_THEIRS
:
998 ll_opts
.variant
= XDL_MERGE_FAVOR_THEIRS
;
1001 ll_opts
.variant
= 0;
1006 assert(pathnames
[0] && pathnames
[1] && pathnames
[2] && opt
->ancestor
);
1007 if (pathnames
[0] == pathnames
[1] && pathnames
[1] == pathnames
[2]) {
1008 base
= mkpathdup("%s", opt
->ancestor
);
1009 name1
= mkpathdup("%s", opt
->branch1
);
1010 name2
= mkpathdup("%s", opt
->branch2
);
1012 base
= mkpathdup("%s:%s", opt
->ancestor
, pathnames
[0]);
1013 name1
= mkpathdup("%s:%s", opt
->branch1
, pathnames
[1]);
1014 name2
= mkpathdup("%s:%s", opt
->branch2
, pathnames
[2]);
1017 read_mmblob(&orig
, o
);
1018 read_mmblob(&src1
, a
);
1019 read_mmblob(&src2
, b
);
1021 merge_status
= ll_merge(result_buf
, path
, &orig
, base
,
1022 &src1
, name1
, &src2
, name2
,
1023 opt
->repo
->index
, &ll_opts
);
1031 return merge_status
;
1034 static int handle_content_merge(struct merge_options
*opt
,
1036 const struct version_info
*o
,
1037 const struct version_info
*a
,
1038 const struct version_info
*b
,
1039 const char *pathnames
[3],
1040 const int extra_marker_size
,
1041 struct version_info
*result
)
1044 * path is the target location where we want to put the file, and
1045 * is used to determine any normalization rules in ll_merge.
1047 * The normal case is that path and all entries in pathnames are
1048 * identical, though renames can affect which path we got one of
1049 * the three blobs to merge on various sides of history.
1051 * extra_marker_size is the amount to extend conflict markers in
1052 * ll_merge; this is neeed if we have content merges of content
1053 * merges, which happens for example with rename/rename(2to1) and
1054 * rename/add conflicts.
1059 * handle_content_merge() needs both files to be of the same type, i.e.
1060 * both files OR both submodules OR both symlinks. Conflicting types
1061 * needs to be handled elsewhere.
1063 assert((S_IFMT
& a
->mode
) == (S_IFMT
& b
->mode
));
1066 if (a
->mode
== b
->mode
|| a
->mode
== o
->mode
)
1067 result
->mode
= b
->mode
;
1069 /* must be the 100644/100755 case */
1070 assert(S_ISREG(a
->mode
));
1071 result
->mode
= a
->mode
;
1072 clean
= (b
->mode
== o
->mode
);
1074 * FIXME: If opt->priv->call_depth && !clean, then we really
1075 * should not make result->mode match either a->mode or
1076 * b->mode; that causes t6036 "check conflicting mode for
1077 * regular file" to fail. It would be best to use some other
1078 * mode, but we'll confuse all kinds of stuff if we use one
1079 * where S_ISREG(result->mode) isn't true, and if we use
1080 * something like 0100666, then tree-walk.c's calls to
1081 * canon_mode() will just normalize that to 100644 for us and
1082 * thus not solve anything.
1084 * Figure out if there's some kind of way we can work around
1090 * Trivial oid merge.
1092 * Note: While one might assume that the next four lines would
1093 * be unnecessary due to the fact that match_mask is often
1094 * setup and already handled, renames don't always take care
1097 if (oideq(&a
->oid
, &b
->oid
) || oideq(&a
->oid
, &o
->oid
))
1098 oidcpy(&result
->oid
, &b
->oid
);
1099 else if (oideq(&b
->oid
, &o
->oid
))
1100 oidcpy(&result
->oid
, &a
->oid
);
1102 /* Remaining rules depend on file vs. submodule vs. symlink. */
1103 else if (S_ISREG(a
->mode
)) {
1104 mmbuffer_t result_buf
;
1105 int ret
= 0, merge_status
;
1109 * If 'o' is different type, treat it as null so we do a
1112 two_way
= ((S_IFMT
& o
->mode
) != (S_IFMT
& a
->mode
));
1114 merge_status
= merge_3way(opt
, path
,
1115 two_way
? &null_oid
: &o
->oid
,
1117 pathnames
, extra_marker_size
,
1120 if ((merge_status
< 0) || !result_buf
.ptr
)
1121 ret
= err(opt
, _("Failed to execute internal merge"));
1124 write_object_file(result_buf
.ptr
, result_buf
.size
,
1125 blob_type
, &result
->oid
))
1126 ret
= err(opt
, _("Unable to add %s to database"),
1129 free(result_buf
.ptr
);
1132 clean
&= (merge_status
== 0);
1133 path_msg(opt
, path
, 1, _("Auto-merging %s"), path
);
1134 } else if (S_ISGITLINK(a
->mode
)) {
1135 int two_way
= ((S_IFMT
& o
->mode
) != (S_IFMT
& a
->mode
));
1136 clean
= merge_submodule(opt
, pathnames
[0],
1137 two_way
? &null_oid
: &o
->oid
,
1138 &a
->oid
, &b
->oid
, &result
->oid
);
1139 if (opt
->priv
->call_depth
&& two_way
&& !clean
) {
1140 result
->mode
= o
->mode
;
1141 oidcpy(&result
->oid
, &o
->oid
);
1143 } else if (S_ISLNK(a
->mode
)) {
1144 if (opt
->priv
->call_depth
) {
1146 result
->mode
= o
->mode
;
1147 oidcpy(&result
->oid
, &o
->oid
);
1149 switch (opt
->recursive_variant
) {
1150 case MERGE_VARIANT_NORMAL
:
1152 oidcpy(&result
->oid
, &a
->oid
);
1154 case MERGE_VARIANT_OURS
:
1155 oidcpy(&result
->oid
, &a
->oid
);
1157 case MERGE_VARIANT_THEIRS
:
1158 oidcpy(&result
->oid
, &b
->oid
);
1163 BUG("unsupported object type in the tree: %06o for %s",
1169 /*** Function Grouping: functions related to detect_and_process_renames(), ***
1170 *** which are split into directory and regular rename detection sections. ***/
1172 /*** Function Grouping: functions related to directory rename detection ***/
1174 struct collision_info
{
1175 struct string_list source_files
;
1176 unsigned reported_already
:1;
1180 * Return a new string that replaces the beginning portion (which matches
1181 * rename_info->key), with rename_info->util.new_dir. In perl-speak:
1182 * new_path_name = (old_path =~ s/rename_info->key/rename_info->value/);
1184 * Caller must ensure that old_path starts with rename_info->key + '/'.
1186 static char *apply_dir_rename(struct strmap_entry
*rename_info
,
1187 const char *old_path
)
1189 struct strbuf new_path
= STRBUF_INIT
;
1190 const char *old_dir
= rename_info
->key
;
1191 const char *new_dir
= rename_info
->value
;
1192 int oldlen
, newlen
, new_dir_len
;
1194 oldlen
= strlen(old_dir
);
1195 if (*new_dir
== '\0')
1197 * If someone renamed/merged a subdirectory into the root
1198 * directory (e.g. 'some/subdir' -> ''), then we want to
1201 * as the rename; we need to make old_path + oldlen advance
1202 * past the '/' character.
1205 new_dir_len
= strlen(new_dir
);
1206 newlen
= new_dir_len
+ (strlen(old_path
) - oldlen
) + 1;
1207 strbuf_grow(&new_path
, newlen
);
1208 strbuf_add(&new_path
, new_dir
, new_dir_len
);
1209 strbuf_addstr(&new_path
, &old_path
[oldlen
]);
1211 return strbuf_detach(&new_path
, NULL
);
1214 static int path_in_way(struct strmap
*paths
, const char *path
, unsigned side_mask
)
1216 struct merged_info
*mi
= strmap_get(paths
, path
);
1217 struct conflict_info
*ci
;
1220 INITIALIZE_CI(ci
, mi
);
1221 return mi
->clean
|| (side_mask
& (ci
->filemask
| ci
->dirmask
));
1225 * See if there is a directory rename for path, and if there are any file
1226 * level conflicts on the given side for the renamed location. If there is
1227 * a rename and there are no conflicts, return the new name. Otherwise,
1230 static char *handle_path_level_conflicts(struct merge_options
*opt
,
1232 unsigned side_index
,
1233 struct strmap_entry
*rename_info
,
1234 struct strmap
*collisions
)
1236 char *new_path
= NULL
;
1237 struct collision_info
*c_info
;
1239 struct strbuf collision_paths
= STRBUF_INIT
;
1242 * entry has the mapping of old directory name to new directory name
1243 * that we want to apply to path.
1245 new_path
= apply_dir_rename(rename_info
, path
);
1247 BUG("Failed to apply directory rename!");
1250 * The caller needs to have ensured that it has pre-populated
1251 * collisions with all paths that map to new_path. Do a quick check
1252 * to ensure that's the case.
1254 c_info
= strmap_get(collisions
, new_path
);
1256 BUG("c_info is NULL");
1259 * Check for one-sided add/add/.../add conflicts, i.e.
1260 * where implicit renames from the other side doing
1261 * directory rename(s) can affect this side of history
1262 * to put multiple paths into the same location. Warn
1263 * and bail on directory renames for such paths.
1265 if (c_info
->reported_already
) {
1267 } else if (path_in_way(&opt
->priv
->paths
, new_path
, 1 << side_index
)) {
1268 c_info
->reported_already
= 1;
1269 strbuf_add_separated_string_list(&collision_paths
, ", ",
1270 &c_info
->source_files
);
1271 path_msg(opt
, new_path
, 0,
1272 _("CONFLICT (implicit dir rename): Existing file/dir "
1273 "at %s in the way of implicit directory rename(s) "
1274 "putting the following path(s) there: %s."),
1275 new_path
, collision_paths
.buf
);
1277 } else if (c_info
->source_files
.nr
> 1) {
1278 c_info
->reported_already
= 1;
1279 strbuf_add_separated_string_list(&collision_paths
, ", ",
1280 &c_info
->source_files
);
1281 path_msg(opt
, new_path
, 0,
1282 _("CONFLICT (implicit dir rename): Cannot map more "
1283 "than one path to %s; implicit directory renames "
1284 "tried to put these paths there: %s"),
1285 new_path
, collision_paths
.buf
);
1289 /* Free memory we no longer need */
1290 strbuf_release(&collision_paths
);
1291 if (!clean
&& new_path
) {
1299 static void get_provisional_directory_renames(struct merge_options
*opt
,
1303 struct hashmap_iter iter
;
1304 struct strmap_entry
*entry
;
1305 struct rename_info
*renames
= &opt
->priv
->renames
;
1309 * dir_rename_count: old_directory -> {new_directory -> count}
1311 * dir_renames: old_directory -> best_new_directory
1312 * where best_new_directory is the one with the unique highest count.
1314 strmap_for_each_entry(&renames
->dir_rename_count
[side
], &iter
, entry
) {
1315 const char *source_dir
= entry
->key
;
1316 struct strintmap
*counts
= entry
->value
;
1317 struct hashmap_iter count_iter
;
1318 struct strmap_entry
*count_entry
;
1321 const char *best
= NULL
;
1323 strintmap_for_each_entry(counts
, &count_iter
, count_entry
) {
1324 const char *target_dir
= count_entry
->key
;
1325 intptr_t count
= (intptr_t)count_entry
->value
;
1329 else if (count
> max
) {
1335 if (bad_max
== max
) {
1336 path_msg(opt
, source_dir
, 0,
1337 _("CONFLICT (directory rename split): "
1338 "Unclear where to rename %s to; it was "
1339 "renamed to multiple other directories, with "
1340 "no destination getting a majority of the "
1344 * We should mark this as unclean IF something attempts
1345 * to use this rename. We do not yet have the logic
1346 * in place to detect if this directory rename is being
1347 * used, and optimizations that reduce the number of
1348 * renames cause this to falsely trigger. For now,
1349 * just disable it, causing t6423 testcase 2a to break.
1350 * We'll later fix the detection, and when we do we
1351 * will re-enable setting *clean to 0 (and thereby fix
1352 * t6423 testcase 2a).
1356 strmap_put(&renames
->dir_renames
[side
],
1357 source_dir
, (void*)best
);
1362 static void handle_directory_level_conflicts(struct merge_options
*opt
)
1364 struct hashmap_iter iter
;
1365 struct strmap_entry
*entry
;
1366 struct string_list duplicated
= STRING_LIST_INIT_NODUP
;
1367 struct rename_info
*renames
= &opt
->priv
->renames
;
1368 struct strmap
*side1_dir_renames
= &renames
->dir_renames
[MERGE_SIDE1
];
1369 struct strmap
*side2_dir_renames
= &renames
->dir_renames
[MERGE_SIDE2
];
1372 strmap_for_each_entry(side1_dir_renames
, &iter
, entry
) {
1373 if (strmap_contains(side2_dir_renames
, entry
->key
))
1374 string_list_append(&duplicated
, entry
->key
);
1377 for (i
= 0; i
< duplicated
.nr
; i
++) {
1378 strmap_remove(side1_dir_renames
, duplicated
.items
[i
].string
, 0);
1379 strmap_remove(side2_dir_renames
, duplicated
.items
[i
].string
, 0);
1381 string_list_clear(&duplicated
, 0);
1384 static struct strmap_entry
*check_dir_renamed(const char *path
,
1385 struct strmap
*dir_renames
)
1387 char *temp
= xstrdup(path
);
1389 struct strmap_entry
*e
= NULL
;
1391 while ((end
= strrchr(temp
, '/'))) {
1393 e
= strmap_get_entry(dir_renames
, temp
);
1401 static void compute_collisions(struct strmap
*collisions
,
1402 struct strmap
*dir_renames
,
1403 struct diff_queue_struct
*pairs
)
1407 strmap_init_with_options(collisions
, NULL
, 0);
1408 if (strmap_empty(dir_renames
))
1412 * Multiple files can be mapped to the same path due to directory
1413 * renames done by the other side of history. Since that other
1414 * side of history could have merged multiple directories into one,
1415 * if our side of history added the same file basename to each of
1416 * those directories, then all N of them would get implicitly
1417 * renamed by the directory rename detection into the same path,
1418 * and we'd get an add/add/.../add conflict, and all those adds
1419 * from *this* side of history. This is not representable in the
1420 * index, and users aren't going to easily be able to make sense of
1421 * it. So we need to provide a good warning about what's
1422 * happening, and fall back to no-directory-rename detection
1423 * behavior for those paths.
1425 * See testcases 9e and all of section 5 from t6043 for examples.
1427 for (i
= 0; i
< pairs
->nr
; ++i
) {
1428 struct strmap_entry
*rename_info
;
1429 struct collision_info
*collision_info
;
1431 struct diff_filepair
*pair
= pairs
->queue
[i
];
1433 if (pair
->status
!= 'A' && pair
->status
!= 'R')
1435 rename_info
= check_dir_renamed(pair
->two
->path
, dir_renames
);
1439 new_path
= apply_dir_rename(rename_info
, pair
->two
->path
);
1441 collision_info
= strmap_get(collisions
, new_path
);
1442 if (collision_info
) {
1445 CALLOC_ARRAY(collision_info
, 1);
1446 string_list_init(&collision_info
->source_files
, 0);
1447 strmap_put(collisions
, new_path
, collision_info
);
1449 string_list_insert(&collision_info
->source_files
,
1454 static char *check_for_directory_rename(struct merge_options
*opt
,
1456 unsigned side_index
,
1457 struct strmap
*dir_renames
,
1458 struct strmap
*dir_rename_exclusions
,
1459 struct strmap
*collisions
,
1462 char *new_path
= NULL
;
1463 struct strmap_entry
*rename_info
;
1464 struct strmap_entry
*otherinfo
= NULL
;
1465 const char *new_dir
;
1467 if (strmap_empty(dir_renames
))
1469 rename_info
= check_dir_renamed(path
, dir_renames
);
1472 /* old_dir = rename_info->key; */
1473 new_dir
= rename_info
->value
;
1476 * This next part is a little weird. We do not want to do an
1477 * implicit rename into a directory we renamed on our side, because
1478 * that will result in a spurious rename/rename(1to2) conflict. An
1480 * Base commit: dumbdir/afile, otherdir/bfile
1481 * Side 1: smrtdir/afile, otherdir/bfile
1482 * Side 2: dumbdir/afile, dumbdir/bfile
1483 * Here, while working on Side 1, we could notice that otherdir was
1484 * renamed/merged to dumbdir, and change the diff_filepair for
1485 * otherdir/bfile into a rename into dumbdir/bfile. However, Side
1486 * 2 will notice the rename from dumbdir to smrtdir, and do the
1487 * transitive rename to move it from dumbdir/bfile to
1488 * smrtdir/bfile. That gives us bfile in dumbdir vs being in
1489 * smrtdir, a rename/rename(1to2) conflict. We really just want
1490 * the file to end up in smrtdir. And the way to achieve that is
1491 * to not let Side1 do the rename to dumbdir, since we know that is
1492 * the source of one of our directory renames.
1494 * That's why otherinfo and dir_rename_exclusions is here.
1496 * As it turns out, this also prevents N-way transient rename
1497 * confusion; See testcases 9c and 9d of t6043.
1499 otherinfo
= strmap_get_entry(dir_rename_exclusions
, new_dir
);
1501 path_msg(opt
, rename_info
->key
, 1,
1502 _("WARNING: Avoiding applying %s -> %s rename "
1503 "to %s, because %s itself was renamed."),
1504 rename_info
->key
, new_dir
, path
, new_dir
);
1508 new_path
= handle_path_level_conflicts(opt
, path
, side_index
,
1509 rename_info
, collisions
);
1510 *clean_merge
&= (new_path
!= NULL
);
1515 static void apply_directory_rename_modifications(struct merge_options
*opt
,
1516 struct diff_filepair
*pair
,
1520 * The basic idea is to get the conflict_info from opt->priv->paths
1521 * at old path, and insert it into new_path; basically just this:
1522 * ci = strmap_get(&opt->priv->paths, old_path);
1523 * strmap_remove(&opt->priv->paths, old_path, 0);
1524 * strmap_put(&opt->priv->paths, new_path, ci);
1525 * However, there are some factors complicating this:
1526 * - opt->priv->paths may already have an entry at new_path
1527 * - Each ci tracks its containing directory, so we need to
1529 * - If another ci has the same containing directory, then
1530 * the two char*'s MUST point to the same location. See the
1531 * comment in struct merged_info. strcmp equality is not
1532 * enough; we need pointer equality.
1533 * - opt->priv->paths must hold the parent directories of any
1534 * entries that are added. So, if this directory rename
1535 * causes entirely new directories, we must recursively add
1536 * parent directories.
1537 * - For each parent directory added to opt->priv->paths, we
1538 * also need to get its parent directory stored in its
1539 * conflict_info->merged.directory_name with all the same
1540 * requirements about pointer equality.
1542 struct string_list dirs_to_insert
= STRING_LIST_INIT_NODUP
;
1543 struct conflict_info
*ci
, *new_ci
;
1544 struct strmap_entry
*entry
;
1545 const char *branch_with_new_path
, *branch_with_dir_rename
;
1546 const char *old_path
= pair
->two
->path
;
1547 const char *parent_name
;
1548 const char *cur_path
;
1551 entry
= strmap_get_entry(&opt
->priv
->paths
, old_path
);
1552 old_path
= entry
->key
;
1556 /* Find parent directories missing from opt->priv->paths */
1557 cur_path
= new_path
;
1559 /* Find the parent directory of cur_path */
1560 char *last_slash
= strrchr(cur_path
, '/');
1562 parent_name
= xstrndup(cur_path
, last_slash
- cur_path
);
1564 parent_name
= opt
->priv
->toplevel_dir
;
1568 /* Look it up in opt->priv->paths */
1569 entry
= strmap_get_entry(&opt
->priv
->paths
, parent_name
);
1571 free((char*)parent_name
);
1572 parent_name
= entry
->key
; /* reuse known pointer */
1576 /* Record this is one of the directories we need to insert */
1577 string_list_append(&dirs_to_insert
, parent_name
);
1578 cur_path
= parent_name
;
1581 /* Traverse dirs_to_insert and insert them into opt->priv->paths */
1582 for (i
= dirs_to_insert
.nr
-1; i
>= 0; --i
) {
1583 struct conflict_info
*dir_ci
;
1584 char *cur_dir
= dirs_to_insert
.items
[i
].string
;
1586 CALLOC_ARRAY(dir_ci
, 1);
1588 dir_ci
->merged
.directory_name
= parent_name
;
1589 len
= strlen(parent_name
);
1590 /* len+1 because of trailing '/' character */
1591 dir_ci
->merged
.basename_offset
= (len
> 0 ? len
+1 : len
);
1592 dir_ci
->dirmask
= ci
->filemask
;
1593 strmap_put(&opt
->priv
->paths
, cur_dir
, dir_ci
);
1595 parent_name
= cur_dir
;
1599 * We are removing old_path from opt->priv->paths. old_path also will
1600 * eventually need to be freed, but it may still be used by e.g.
1601 * ci->pathnames. So, store it in another string-list for now.
1603 string_list_append(&opt
->priv
->paths_to_free
, old_path
);
1605 assert(ci
->filemask
== 2 || ci
->filemask
== 4);
1606 assert(ci
->dirmask
== 0);
1607 strmap_remove(&opt
->priv
->paths
, old_path
, 0);
1609 branch_with_new_path
= (ci
->filemask
== 2) ? opt
->branch1
: opt
->branch2
;
1610 branch_with_dir_rename
= (ci
->filemask
== 2) ? opt
->branch2
: opt
->branch1
;
1612 /* Now, finally update ci and stick it into opt->priv->paths */
1613 ci
->merged
.directory_name
= parent_name
;
1614 len
= strlen(parent_name
);
1615 ci
->merged
.basename_offset
= (len
> 0 ? len
+1 : len
);
1616 new_ci
= strmap_get(&opt
->priv
->paths
, new_path
);
1618 /* Place ci back into opt->priv->paths, but at new_path */
1619 strmap_put(&opt
->priv
->paths
, new_path
, ci
);
1623 /* A few sanity checks */
1625 assert(ci
->filemask
== 2 || ci
->filemask
== 4);
1626 assert((new_ci
->filemask
& ci
->filemask
) == 0);
1627 assert(!new_ci
->merged
.clean
);
1629 /* Copy stuff from ci into new_ci */
1630 new_ci
->filemask
|= ci
->filemask
;
1631 if (new_ci
->dirmask
)
1632 new_ci
->df_conflict
= 1;
1633 index
= (ci
->filemask
>> 1);
1634 new_ci
->pathnames
[index
] = ci
->pathnames
[index
];
1635 new_ci
->stages
[index
].mode
= ci
->stages
[index
].mode
;
1636 oidcpy(&new_ci
->stages
[index
].oid
, &ci
->stages
[index
].oid
);
1642 if (opt
->detect_directory_renames
== MERGE_DIRECTORY_RENAMES_TRUE
) {
1643 /* Notify user of updated path */
1644 if (pair
->status
== 'A')
1645 path_msg(opt
, new_path
, 1,
1646 _("Path updated: %s added in %s inside a "
1647 "directory that was renamed in %s; moving "
1649 old_path
, branch_with_new_path
,
1650 branch_with_dir_rename
, new_path
);
1652 path_msg(opt
, new_path
, 1,
1653 _("Path updated: %s renamed to %s in %s, "
1654 "inside a directory that was renamed in %s; "
1655 "moving it to %s."),
1656 pair
->one
->path
, old_path
, branch_with_new_path
,
1657 branch_with_dir_rename
, new_path
);
1660 * opt->detect_directory_renames has the value
1661 * MERGE_DIRECTORY_RENAMES_CONFLICT, so mark these as conflicts.
1663 ci
->path_conflict
= 1;
1664 if (pair
->status
== 'A')
1665 path_msg(opt
, new_path
, 0,
1666 _("CONFLICT (file location): %s added in %s "
1667 "inside a directory that was renamed in %s, "
1668 "suggesting it should perhaps be moved to "
1670 old_path
, branch_with_new_path
,
1671 branch_with_dir_rename
, new_path
);
1673 path_msg(opt
, new_path
, 0,
1674 _("CONFLICT (file location): %s renamed to %s "
1675 "in %s, inside a directory that was renamed "
1676 "in %s, suggesting it should perhaps be "
1678 pair
->one
->path
, old_path
, branch_with_new_path
,
1679 branch_with_dir_rename
, new_path
);
1683 * Finally, record the new location.
1685 pair
->two
->path
= new_path
;
1688 /*** Function Grouping: functions related to regular rename detection ***/
1690 static int process_renames(struct merge_options
*opt
,
1691 struct diff_queue_struct
*renames
)
1693 int clean_merge
= 1, i
;
1695 for (i
= 0; i
< renames
->nr
; ++i
) {
1696 const char *oldpath
= NULL
, *newpath
;
1697 struct diff_filepair
*pair
= renames
->queue
[i
];
1698 struct conflict_info
*oldinfo
= NULL
, *newinfo
= NULL
;
1699 struct strmap_entry
*old_ent
, *new_ent
;
1700 unsigned int old_sidemask
;
1701 int target_index
, other_source_index
;
1702 int source_deleted
, collision
, type_changed
;
1703 const char *rename_branch
= NULL
, *delete_branch
= NULL
;
1705 old_ent
= strmap_get_entry(&opt
->priv
->paths
, pair
->one
->path
);
1706 new_ent
= strmap_get_entry(&opt
->priv
->paths
, pair
->two
->path
);
1708 oldpath
= old_ent
->key
;
1709 oldinfo
= old_ent
->value
;
1711 newpath
= pair
->two
->path
;
1713 newpath
= new_ent
->key
;
1714 newinfo
= new_ent
->value
;
1718 * If pair->one->path isn't in opt->priv->paths, that means
1719 * that either directory rename detection removed that
1720 * path, or a parent directory of oldpath was resolved and
1721 * we don't even need the rename; in either case, we can
1722 * skip it. If oldinfo->merged.clean, then the other side
1723 * of history had no changes to oldpath and we don't need
1724 * the rename and can skip it.
1726 if (!oldinfo
|| oldinfo
->merged
.clean
)
1730 * diff_filepairs have copies of pathnames, thus we have to
1731 * use standard 'strcmp()' (negated) instead of '=='.
1733 if (i
+ 1 < renames
->nr
&&
1734 !strcmp(oldpath
, renames
->queue
[i
+1]->one
->path
)) {
1735 /* Handle rename/rename(1to2) or rename/rename(1to1) */
1736 const char *pathnames
[3];
1737 struct version_info merged
;
1738 struct conflict_info
*base
, *side1
, *side2
;
1739 unsigned was_binary_blob
= 0;
1741 pathnames
[0] = oldpath
;
1742 pathnames
[1] = newpath
;
1743 pathnames
[2] = renames
->queue
[i
+1]->two
->path
;
1745 base
= strmap_get(&opt
->priv
->paths
, pathnames
[0]);
1746 side1
= strmap_get(&opt
->priv
->paths
, pathnames
[1]);
1747 side2
= strmap_get(&opt
->priv
->paths
, pathnames
[2]);
1753 if (!strcmp(pathnames
[1], pathnames
[2])) {
1754 /* Both sides renamed the same way */
1755 assert(side1
== side2
);
1756 memcpy(&side1
->stages
[0], &base
->stages
[0],
1758 side1
->filemask
|= (1 << MERGE_BASE
);
1759 /* Mark base as resolved by removal */
1760 base
->merged
.is_null
= 1;
1761 base
->merged
.clean
= 1;
1763 /* We handled both renames, i.e. i+1 handled */
1765 /* Move to next rename */
1769 /* This is a rename/rename(1to2) */
1770 clean_merge
= handle_content_merge(opt
,
1776 1 + 2 * opt
->priv
->call_depth
,
1779 merged
.mode
== side1
->stages
[1].mode
&&
1780 oideq(&merged
.oid
, &side1
->stages
[1].oid
))
1781 was_binary_blob
= 1;
1782 memcpy(&side1
->stages
[1], &merged
, sizeof(merged
));
1783 if (was_binary_blob
) {
1785 * Getting here means we were attempting to
1786 * merge a binary blob.
1788 * Since we can't merge binaries,
1789 * handle_content_merge() just takes one
1790 * side. But we don't want to copy the
1791 * contents of one side to both paths. We
1792 * used the contents of side1 above for
1793 * side1->stages, let's use the contents of
1794 * side2 for side2->stages below.
1796 oidcpy(&merged
.oid
, &side2
->stages
[2].oid
);
1797 merged
.mode
= side2
->stages
[2].mode
;
1799 memcpy(&side2
->stages
[2], &merged
, sizeof(merged
));
1801 side1
->path_conflict
= 1;
1802 side2
->path_conflict
= 1;
1804 * TODO: For renames we normally remove the path at the
1805 * old name. It would thus seem consistent to do the
1806 * same for rename/rename(1to2) cases, but we haven't
1807 * done so traditionally and a number of the regression
1808 * tests now encode an expectation that the file is
1809 * left there at stage 1. If we ever decide to change
1810 * this, add the following two lines here:
1811 * base->merged.is_null = 1;
1812 * base->merged.clean = 1;
1813 * and remove the setting of base->path_conflict to 1.
1815 base
->path_conflict
= 1;
1816 path_msg(opt
, oldpath
, 0,
1817 _("CONFLICT (rename/rename): %s renamed to "
1818 "%s in %s and to %s in %s."),
1820 pathnames
[1], opt
->branch1
,
1821 pathnames
[2], opt
->branch2
);
1823 i
++; /* We handled both renames, i.e. i+1 handled */
1829 target_index
= pair
->score
; /* from collect_renames() */
1830 assert(target_index
== 1 || target_index
== 2);
1831 other_source_index
= 3 - target_index
;
1832 old_sidemask
= (1 << other_source_index
); /* 2 or 4 */
1833 source_deleted
= (oldinfo
->filemask
== 1);
1834 collision
= ((newinfo
->filemask
& old_sidemask
) != 0);
1835 type_changed
= !source_deleted
&&
1836 (S_ISREG(oldinfo
->stages
[other_source_index
].mode
) !=
1837 S_ISREG(newinfo
->stages
[target_index
].mode
));
1838 if (type_changed
&& collision
) {
1840 * special handling so later blocks can handle this...
1842 * if type_changed && collision are both true, then this
1843 * was really a double rename, but one side wasn't
1844 * detected due to lack of break detection. I.e.
1846 * orig: has normal file 'foo'
1847 * side1: renames 'foo' to 'bar', adds 'foo' symlink
1848 * side2: renames 'foo' to 'bar'
1849 * In this case, the foo->bar rename on side1 won't be
1850 * detected because the new symlink named 'foo' is
1851 * there and we don't do break detection. But we detect
1852 * this here because we don't want to merge the content
1853 * of the foo symlink with the foo->bar file, so we
1854 * have some logic to handle this special case. The
1855 * easiest way to do that is make 'bar' on side1 not
1856 * be considered a colliding file but the other part
1857 * of a normal rename. If the file is very different,
1858 * well we're going to get content merge conflicts
1859 * anyway so it doesn't hurt. And if the colliding
1860 * file also has a different type, that'll be handled
1861 * by the content merge logic in process_entry() too.
1863 * See also t6430, 'rename vs. rename/symlink'
1867 if (source_deleted
) {
1868 if (target_index
== 1) {
1869 rename_branch
= opt
->branch1
;
1870 delete_branch
= opt
->branch2
;
1872 rename_branch
= opt
->branch2
;
1873 delete_branch
= opt
->branch1
;
1877 assert(source_deleted
|| oldinfo
->filemask
& old_sidemask
);
1879 /* Need to check for special types of rename conflicts... */
1880 if (collision
&& !source_deleted
) {
1881 /* collision: rename/add or rename/rename(2to1) */
1882 const char *pathnames
[3];
1883 struct version_info merged
;
1885 struct conflict_info
*base
, *side1
, *side2
;
1888 pathnames
[0] = oldpath
;
1889 pathnames
[other_source_index
] = oldpath
;
1890 pathnames
[target_index
] = newpath
;
1892 base
= strmap_get(&opt
->priv
->paths
, pathnames
[0]);
1893 side1
= strmap_get(&opt
->priv
->paths
, pathnames
[1]);
1894 side2
= strmap_get(&opt
->priv
->paths
, pathnames
[2]);
1900 clean
= handle_content_merge(opt
, pair
->one
->path
,
1905 1 + 2 * opt
->priv
->call_depth
,
1908 memcpy(&newinfo
->stages
[target_index
], &merged
,
1911 path_msg(opt
, newpath
, 0,
1912 _("CONFLICT (rename involved in "
1913 "collision): rename of %s -> %s has "
1914 "content conflicts AND collides "
1915 "with another path; this may result "
1916 "in nested conflict markers."),
1919 } else if (collision
&& source_deleted
) {
1921 * rename/add/delete or rename/rename(2to1)/delete:
1922 * since oldpath was deleted on the side that didn't
1923 * do the rename, there's not much of a content merge
1924 * we can do for the rename. oldinfo->merged.is_null
1925 * was already set, so we just leave things as-is so
1926 * they look like an add/add conflict.
1929 newinfo
->path_conflict
= 1;
1930 path_msg(opt
, newpath
, 0,
1931 _("CONFLICT (rename/delete): %s renamed "
1932 "to %s in %s, but deleted in %s."),
1933 oldpath
, newpath
, rename_branch
, delete_branch
);
1936 * a few different cases...start by copying the
1937 * existing stage(s) from oldinfo over the newinfo
1938 * and update the pathname(s).
1940 memcpy(&newinfo
->stages
[0], &oldinfo
->stages
[0],
1941 sizeof(newinfo
->stages
[0]));
1942 newinfo
->filemask
|= (1 << MERGE_BASE
);
1943 newinfo
->pathnames
[0] = oldpath
;
1945 /* rename vs. typechange */
1946 /* Mark the original as resolved by removal */
1947 memcpy(&oldinfo
->stages
[0].oid
, &null_oid
,
1948 sizeof(oldinfo
->stages
[0].oid
));
1949 oldinfo
->stages
[0].mode
= 0;
1950 oldinfo
->filemask
&= 0x06;
1951 } else if (source_deleted
) {
1953 newinfo
->path_conflict
= 1;
1954 path_msg(opt
, newpath
, 0,
1955 _("CONFLICT (rename/delete): %s renamed"
1956 " to %s in %s, but deleted in %s."),
1958 rename_branch
, delete_branch
);
1961 memcpy(&newinfo
->stages
[other_source_index
],
1962 &oldinfo
->stages
[other_source_index
],
1963 sizeof(newinfo
->stages
[0]));
1964 newinfo
->filemask
|= (1 << other_source_index
);
1965 newinfo
->pathnames
[other_source_index
] = oldpath
;
1969 if (!type_changed
) {
1970 /* Mark the original as resolved by removal */
1971 oldinfo
->merged
.is_null
= 1;
1972 oldinfo
->merged
.clean
= 1;
1980 static void resolve_diffpair_statuses(struct diff_queue_struct
*q
)
1983 * A simplified version of diff_resolve_rename_copy(); would probably
1984 * just use that function but it's static...
1987 struct diff_filepair
*p
;
1989 for (i
= 0; i
< q
->nr
; ++i
) {
1991 p
->status
= 0; /* undecided */
1992 if (!DIFF_FILE_VALID(p
->one
))
1993 p
->status
= DIFF_STATUS_ADDED
;
1994 else if (!DIFF_FILE_VALID(p
->two
))
1995 p
->status
= DIFF_STATUS_DELETED
;
1996 else if (DIFF_PAIR_RENAME(p
))
1997 p
->status
= DIFF_STATUS_RENAMED
;
2001 static int compare_pairs(const void *a_
, const void *b_
)
2003 const struct diff_filepair
*a
= *((const struct diff_filepair
**)a_
);
2004 const struct diff_filepair
*b
= *((const struct diff_filepair
**)b_
);
2006 return strcmp(a
->one
->path
, b
->one
->path
);
2009 /* Call diffcore_rename() to compute which files have changed on given side */
2010 static void detect_regular_renames(struct merge_options
*opt
,
2011 unsigned side_index
)
2013 struct diff_options diff_opts
;
2014 struct rename_info
*renames
= &opt
->priv
->renames
;
2016 repo_diff_setup(opt
->repo
, &diff_opts
);
2017 diff_opts
.flags
.recursive
= 1;
2018 diff_opts
.flags
.rename_empty
= 0;
2019 diff_opts
.detect_rename
= DIFF_DETECT_RENAME
;
2020 diff_opts
.rename_limit
= opt
->rename_limit
;
2021 if (opt
->rename_limit
<= 0)
2022 diff_opts
.rename_limit
= 1000;
2023 diff_opts
.rename_score
= opt
->rename_score
;
2024 diff_opts
.show_rename_progress
= opt
->show_rename_progress
;
2025 diff_opts
.output_format
= DIFF_FORMAT_NO_OUTPUT
;
2026 diff_setup_done(&diff_opts
);
2028 diff_queued_diff
= renames
->pairs
[side_index
];
2029 trace2_region_enter("diff", "diffcore_rename", opt
->repo
);
2030 diffcore_rename_extended(&diff_opts
,
2031 &renames
->dirs_removed
[side_index
],
2032 &renames
->dir_rename_count
[side_index
]);
2033 trace2_region_leave("diff", "diffcore_rename", opt
->repo
);
2034 resolve_diffpair_statuses(&diff_queued_diff
);
2036 if (diff_opts
.needed_rename_limit
> renames
->needed_limit
)
2037 renames
->needed_limit
= diff_opts
.needed_rename_limit
;
2039 renames
->pairs
[side_index
] = diff_queued_diff
;
2041 diff_opts
.output_format
= DIFF_FORMAT_NO_OUTPUT
;
2042 diff_queued_diff
.nr
= 0;
2043 diff_queued_diff
.queue
= NULL
;
2044 diff_flush(&diff_opts
);
2048 * Get information of all renames which occurred in 'side_pairs', discarding
2051 static int collect_renames(struct merge_options
*opt
,
2052 struct diff_queue_struct
*result
,
2053 unsigned side_index
,
2054 struct strmap
*dir_renames_for_side
,
2055 struct strmap
*rename_exclusions
)
2058 struct strmap collisions
;
2059 struct diff_queue_struct
*side_pairs
;
2060 struct hashmap_iter iter
;
2061 struct strmap_entry
*entry
;
2062 struct rename_info
*renames
= &opt
->priv
->renames
;
2064 side_pairs
= &renames
->pairs
[side_index
];
2065 compute_collisions(&collisions
, dir_renames_for_side
, side_pairs
);
2067 for (i
= 0; i
< side_pairs
->nr
; ++i
) {
2068 struct diff_filepair
*p
= side_pairs
->queue
[i
];
2069 char *new_path
; /* non-NULL only with directory renames */
2071 if (p
->status
!= 'A' && p
->status
!= 'R') {
2072 diff_free_filepair(p
);
2076 new_path
= check_for_directory_rename(opt
, p
->two
->path
,
2078 dir_renames_for_side
,
2083 if (p
->status
!= 'R' && !new_path
) {
2084 diff_free_filepair(p
);
2089 apply_directory_rename_modifications(opt
, p
, new_path
);
2092 * p->score comes back from diffcore_rename_extended() with
2093 * the similarity of the renamed file. The similarity is
2094 * was used to determine that the two files were related
2095 * and are a rename, which we have already used, but beyond
2096 * that we have no use for the similarity. So p->score is
2097 * now irrelevant. However, process_renames() will need to
2098 * know which side of the merge this rename was associated
2099 * with, so overwrite p->score with that value.
2101 p
->score
= side_index
;
2102 result
->queue
[result
->nr
++] = p
;
2105 /* Free each value in the collisions map */
2106 strmap_for_each_entry(&collisions
, &iter
, entry
) {
2107 struct collision_info
*info
= entry
->value
;
2108 string_list_clear(&info
->source_files
, 0);
2111 * In compute_collisions(), we set collisions.strdup_strings to 0
2112 * so that we wouldn't have to make another copy of the new_path
2113 * allocated by apply_dir_rename(). But now that we've used them
2114 * and have no other references to these strings, it is time to
2117 free_strmap_strings(&collisions
);
2118 strmap_clear(&collisions
, 1);
2122 static int detect_and_process_renames(struct merge_options
*opt
,
2123 struct tree
*merge_base
,
2127 struct diff_queue_struct combined
;
2128 struct rename_info
*renames
= &opt
->priv
->renames
;
2129 int need_dir_renames
, s
, clean
= 1;
2131 memset(&combined
, 0, sizeof(combined
));
2133 trace2_region_enter("merge", "regular renames", opt
->repo
);
2134 detect_regular_renames(opt
, MERGE_SIDE1
);
2135 detect_regular_renames(opt
, MERGE_SIDE2
);
2136 trace2_region_leave("merge", "regular renames", opt
->repo
);
2138 trace2_region_enter("merge", "directory renames", opt
->repo
);
2140 !opt
->priv
->call_depth
&&
2141 (opt
->detect_directory_renames
== MERGE_DIRECTORY_RENAMES_TRUE
||
2142 opt
->detect_directory_renames
== MERGE_DIRECTORY_RENAMES_CONFLICT
);
2144 if (need_dir_renames
) {
2145 get_provisional_directory_renames(opt
, MERGE_SIDE1
, &clean
);
2146 get_provisional_directory_renames(opt
, MERGE_SIDE2
, &clean
);
2147 handle_directory_level_conflicts(opt
);
2150 ALLOC_GROW(combined
.queue
,
2151 renames
->pairs
[1].nr
+ renames
->pairs
[2].nr
,
2153 clean
&= collect_renames(opt
, &combined
, MERGE_SIDE1
,
2154 &renames
->dir_renames
[2],
2155 &renames
->dir_renames
[1]);
2156 clean
&= collect_renames(opt
, &combined
, MERGE_SIDE2
,
2157 &renames
->dir_renames
[1],
2158 &renames
->dir_renames
[2]);
2159 QSORT(combined
.queue
, combined
.nr
, compare_pairs
);
2160 trace2_region_leave("merge", "directory renames", opt
->repo
);
2162 trace2_region_enter("merge", "process renames", opt
->repo
);
2163 clean
&= process_renames(opt
, &combined
);
2164 trace2_region_leave("merge", "process renames", opt
->repo
);
2166 /* Free memory for renames->pairs[] and combined */
2167 for (s
= MERGE_SIDE1
; s
<= MERGE_SIDE2
; s
++) {
2168 free(renames
->pairs
[s
].queue
);
2169 DIFF_QUEUE_CLEAR(&renames
->pairs
[s
]);
2173 for (i
= 0; i
< combined
.nr
; i
++)
2174 diff_free_filepair(combined
.queue
[i
]);
2175 free(combined
.queue
);
2181 /*** Function Grouping: functions related to process_entries() ***/
2183 static int string_list_df_name_compare(const char *one
, const char *two
)
2185 int onelen
= strlen(one
);
2186 int twolen
= strlen(two
);
2188 * Here we only care that entries for D/F conflicts are
2189 * adjacent, in particular with the file of the D/F conflict
2190 * appearing before files below the corresponding directory.
2191 * The order of the rest of the list is irrelevant for us.
2193 * To achieve this, we sort with df_name_compare and provide
2194 * the mode S_IFDIR so that D/F conflicts will sort correctly.
2195 * We use the mode S_IFDIR for everything else for simplicity,
2196 * since in other cases any changes in their order due to
2197 * sorting cause no problems for us.
2199 int cmp
= df_name_compare(one
, onelen
, S_IFDIR
,
2200 two
, twolen
, S_IFDIR
);
2202 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
2203 * that 'foo' comes before 'foo/bar'.
2207 return onelen
- twolen
;
2210 struct directory_versions
{
2212 * versions: list of (basename -> version_info)
2214 * The basenames are in reverse lexicographic order of full pathnames,
2215 * as processed in process_entries(). This puts all entries within
2216 * a directory together, and covers the directory itself after
2217 * everything within it, allowing us to write subtrees before needing
2218 * to record information for the tree itself.
2220 struct string_list versions
;
2223 * offsets: list of (full relative path directories -> integer offsets)
2225 * Since versions contains basenames from files in multiple different
2226 * directories, we need to know which entries in versions correspond
2227 * to which directories. Values of e.g.
2231 * Would mean that entries 0-1 of versions are files in the toplevel
2232 * directory, entries 2-4 are files under src/, and the remaining
2233 * entries starting at index 5 are files under src/moduleA/.
2235 struct string_list offsets
;
2238 * last_directory: directory that previously processed file found in
2240 * last_directory starts NULL, but records the directory in which the
2241 * previous file was found within. As soon as
2242 * directory(current_file) != last_directory
2243 * then we need to start updating accounting in versions & offsets.
2244 * Note that last_directory is always the last path in "offsets" (or
2245 * NULL if "offsets" is empty) so this exists just for quick access.
2247 const char *last_directory
;
2249 /* last_directory_len: cached computation of strlen(last_directory) */
2250 unsigned last_directory_len
;
2253 static int tree_entry_order(const void *a_
, const void *b_
)
2255 const struct string_list_item
*a
= a_
;
2256 const struct string_list_item
*b
= b_
;
2258 const struct merged_info
*ami
= a
->util
;
2259 const struct merged_info
*bmi
= b
->util
;
2260 return base_name_compare(a
->string
, strlen(a
->string
), ami
->result
.mode
,
2261 b
->string
, strlen(b
->string
), bmi
->result
.mode
);
2264 static void write_tree(struct object_id
*result_oid
,
2265 struct string_list
*versions
,
2266 unsigned int offset
,
2269 size_t maxlen
= 0, extra
;
2270 unsigned int nr
= versions
->nr
- offset
;
2271 struct strbuf buf
= STRBUF_INIT
;
2272 struct string_list relevant_entries
= STRING_LIST_INIT_NODUP
;
2276 * We want to sort the last (versions->nr-offset) entries in versions.
2277 * Do so by abusing the string_list API a bit: make another string_list
2278 * that contains just those entries and then sort them.
2280 * We won't use relevant_entries again and will let it just pop off the
2281 * stack, so there won't be allocation worries or anything.
2283 relevant_entries
.items
= versions
->items
+ offset
;
2284 relevant_entries
.nr
= versions
->nr
- offset
;
2285 QSORT(relevant_entries
.items
, relevant_entries
.nr
, tree_entry_order
);
2287 /* Pre-allocate some space in buf */
2288 extra
= hash_size
+ 8; /* 8: 6 for mode, 1 for space, 1 for NUL char */
2289 for (i
= 0; i
< nr
; i
++) {
2290 maxlen
+= strlen(versions
->items
[offset
+i
].string
) + extra
;
2292 strbuf_grow(&buf
, maxlen
);
2294 /* Write each entry out to buf */
2295 for (i
= 0; i
< nr
; i
++) {
2296 struct merged_info
*mi
= versions
->items
[offset
+i
].util
;
2297 struct version_info
*ri
= &mi
->result
;
2298 strbuf_addf(&buf
, "%o %s%c",
2300 versions
->items
[offset
+i
].string
, '\0');
2301 strbuf_add(&buf
, ri
->oid
.hash
, hash_size
);
2304 /* Write this object file out, and record in result_oid */
2305 write_object_file(buf
.buf
, buf
.len
, tree_type
, result_oid
);
2306 strbuf_release(&buf
);
2309 static void record_entry_for_tree(struct directory_versions
*dir_metadata
,
2311 struct merged_info
*mi
)
2313 const char *basename
;
2316 /* nothing to record */
2319 basename
= path
+ mi
->basename_offset
;
2320 assert(strchr(basename
, '/') == NULL
);
2321 string_list_append(&dir_metadata
->versions
,
2322 basename
)->util
= &mi
->result
;
2325 static void write_completed_directory(struct merge_options
*opt
,
2326 const char *new_directory_name
,
2327 struct directory_versions
*info
)
2329 const char *prev_dir
;
2330 struct merged_info
*dir_info
= NULL
;
2331 unsigned int offset
;
2334 * Some explanation of info->versions and info->offsets...
2336 * process_entries() iterates over all relevant files AND
2337 * directories in reverse lexicographic order, and calls this
2338 * function. Thus, an example of the paths that process_entries()
2339 * could operate on (along with the directories for those paths
2344 * src/moduleB/umm.c src/moduleB
2345 * src/moduleB/stuff.h src/moduleB
2346 * src/moduleB/baz.c src/moduleB
2348 * src/moduleA/foo.c src/moduleA
2349 * src/moduleA/bar.c src/moduleA
2356 * always contains the unprocessed entries and their
2357 * version_info information. For example, after the first five
2358 * entries above, info->versions would be:
2360 * xtract.c <xtract.c's version_info>
2361 * token.txt <token.txt's version_info>
2362 * umm.c <src/moduleB/umm.c's version_info>
2363 * stuff.h <src/moduleB/stuff.h's version_info>
2364 * baz.c <src/moduleB/baz.c's version_info>
2366 * Once a subdirectory is completed we remove the entries in
2367 * that subdirectory from info->versions, writing it as a tree
2368 * (write_tree()). Thus, as soon as we get to src/moduleB,
2369 * info->versions would be updated to
2371 * xtract.c <xtract.c's version_info>
2372 * token.txt <token.txt's version_info>
2373 * moduleB <src/moduleB's version_info>
2377 * helps us track which entries in info->versions correspond to
2378 * which directories. When we are N directories deep (e.g. 4
2379 * for src/modA/submod/subdir/), we have up to N+1 unprocessed
2380 * directories (+1 because of toplevel dir). Corresponding to
2381 * the info->versions example above, after processing five entries
2382 * info->offsets will be:
2387 * which is used to know that xtract.c & token.txt are from the
2388 * toplevel dirctory, while umm.c & stuff.h & baz.c are from the
2389 * src/moduleB directory. Again, following the example above,
2390 * once we need to process src/moduleB, then info->offsets is
2396 * which says that moduleB (and only moduleB so far) is in the
2399 * One unique thing to note about info->offsets here is that
2400 * "src" was not added to info->offsets until there was a path
2401 * (a file OR directory) immediately below src/ that got
2404 * Since process_entry() just appends new entries to info->versions,
2405 * write_completed_directory() only needs to do work if the next path
2406 * is in a directory that is different than the last directory found
2411 * If we are working with the same directory as the last entry, there
2412 * is no work to do. (See comments above the directory_name member of
2413 * struct merged_info for why we can use pointer comparison instead of
2416 if (new_directory_name
== info
->last_directory
)
2420 * If we are just starting (last_directory is NULL), or last_directory
2421 * is a prefix of the current directory, then we can just update
2422 * info->offsets to record the offset where we started this directory
2423 * and update last_directory to have quick access to it.
2425 if (info
->last_directory
== NULL
||
2426 !strncmp(new_directory_name
, info
->last_directory
,
2427 info
->last_directory_len
)) {
2428 uintptr_t offset
= info
->versions
.nr
;
2430 info
->last_directory
= new_directory_name
;
2431 info
->last_directory_len
= strlen(info
->last_directory
);
2433 * Record the offset into info->versions where we will
2434 * start recording basenames of paths found within
2435 * new_directory_name.
2437 string_list_append(&info
->offsets
,
2438 info
->last_directory
)->util
= (void*)offset
;
2443 * The next entry that will be processed will be within
2444 * new_directory_name. Since at this point we know that
2445 * new_directory_name is within a different directory than
2446 * info->last_directory, we have all entries for info->last_directory
2447 * in info->versions and we need to create a tree object for them.
2449 dir_info
= strmap_get(&opt
->priv
->paths
, info
->last_directory
);
2451 offset
= (uintptr_t)info
->offsets
.items
[info
->offsets
.nr
-1].util
;
2452 if (offset
== info
->versions
.nr
) {
2454 * Actually, we don't need to create a tree object in this
2455 * case. Whenever all files within a directory disappear
2456 * during the merge (e.g. unmodified on one side and
2457 * deleted on the other, or files were renamed elsewhere),
2458 * then we get here and the directory itself needs to be
2459 * omitted from its parent tree as well.
2461 dir_info
->is_null
= 1;
2464 * Write out the tree to the git object directory, and also
2465 * record the mode and oid in dir_info->result.
2467 dir_info
->is_null
= 0;
2468 dir_info
->result
.mode
= S_IFDIR
;
2469 write_tree(&dir_info
->result
.oid
, &info
->versions
, offset
,
2470 opt
->repo
->hash_algo
->rawsz
);
2474 * We've now used several entries from info->versions and one entry
2475 * from info->offsets, so we get rid of those values.
2478 info
->versions
.nr
= offset
;
2481 * Now we've taken care of the completed directory, but we need to
2482 * prepare things since future entries will be in
2483 * new_directory_name. (In particular, process_entry() will be
2484 * appending new entries to info->versions.) So, we need to make
2485 * sure new_directory_name is the last entry in info->offsets.
2487 prev_dir
= info
->offsets
.nr
== 0 ? NULL
:
2488 info
->offsets
.items
[info
->offsets
.nr
-1].string
;
2489 if (new_directory_name
!= prev_dir
) {
2490 uintptr_t c
= info
->versions
.nr
;
2491 string_list_append(&info
->offsets
,
2492 new_directory_name
)->util
= (void*)c
;
2495 /* And, of course, we need to update last_directory to match. */
2496 info
->last_directory
= new_directory_name
;
2497 info
->last_directory_len
= strlen(info
->last_directory
);
2500 /* Per entry merge function */
2501 static void process_entry(struct merge_options
*opt
,
2503 struct conflict_info
*ci
,
2504 struct directory_versions
*dir_metadata
)
2506 int df_file_index
= 0;
2509 assert(ci
->filemask
>= 0 && ci
->filemask
<= 7);
2510 /* ci->match_mask == 7 was handled in collect_merge_info_callback() */
2511 assert(ci
->match_mask
== 0 || ci
->match_mask
== 3 ||
2512 ci
->match_mask
== 5 || ci
->match_mask
== 6);
2515 record_entry_for_tree(dir_metadata
, path
, &ci
->merged
);
2516 if (ci
->filemask
== 0)
2517 /* nothing else to handle */
2519 assert(ci
->df_conflict
);
2522 if (ci
->df_conflict
&& ci
->merged
.result
.mode
== 0) {
2526 * directory no longer in the way, but we do have a file we
2527 * need to place here so we need to clean away the "directory
2528 * merges to nothing" result.
2530 ci
->df_conflict
= 0;
2531 assert(ci
->filemask
!= 0);
2532 ci
->merged
.clean
= 0;
2533 ci
->merged
.is_null
= 0;
2534 /* and we want to zero out any directory-related entries */
2535 ci
->match_mask
= (ci
->match_mask
& ~ci
->dirmask
);
2537 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
2538 if (ci
->filemask
& (1 << i
))
2540 ci
->stages
[i
].mode
= 0;
2541 oidcpy(&ci
->stages
[i
].oid
, &null_oid
);
2543 } else if (ci
->df_conflict
&& ci
->merged
.result
.mode
!= 0) {
2545 * This started out as a D/F conflict, and the entries in
2546 * the competing directory were not removed by the merge as
2547 * evidenced by write_completed_directory() writing a value
2548 * to ci->merged.result.mode.
2550 struct conflict_info
*new_ci
;
2552 const char *old_path
= path
;
2555 assert(ci
->merged
.result
.mode
== S_IFDIR
);
2558 * If filemask is 1, we can just ignore the file as having
2559 * been deleted on both sides. We do not want to overwrite
2560 * ci->merged.result, since it stores the tree for all the
2563 if (ci
->filemask
== 1) {
2569 * This file still exists on at least one side, and we want
2570 * the directory to remain here, so we need to move this
2571 * path to some new location.
2573 CALLOC_ARRAY(new_ci
, 1);
2574 /* We don't really want new_ci->merged.result copied, but it'll
2575 * be overwritten below so it doesn't matter. We also don't
2576 * want any directory mode/oid values copied, but we'll zero
2577 * those out immediately. We do want the rest of ci copied.
2579 memcpy(new_ci
, ci
, sizeof(*ci
));
2580 new_ci
->match_mask
= (new_ci
->match_mask
& ~new_ci
->dirmask
);
2581 new_ci
->dirmask
= 0;
2582 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
2583 if (new_ci
->filemask
& (1 << i
))
2585 /* zero out any entries related to directories */
2586 new_ci
->stages
[i
].mode
= 0;
2587 oidcpy(&new_ci
->stages
[i
].oid
, &null_oid
);
2591 * Find out which side this file came from; note that we
2592 * cannot just use ci->filemask, because renames could cause
2593 * the filemask to go back to 7. So we use dirmask, then
2594 * pick the opposite side's index.
2596 df_file_index
= (ci
->dirmask
& (1 << 1)) ? 2 : 1;
2597 branch
= (df_file_index
== 1) ? opt
->branch1
: opt
->branch2
;
2598 path
= unique_path(&opt
->priv
->paths
, path
, branch
);
2599 strmap_put(&opt
->priv
->paths
, path
, new_ci
);
2601 path_msg(opt
, path
, 0,
2602 _("CONFLICT (file/directory): directory in the way "
2603 "of %s from %s; moving it to %s instead."),
2604 old_path
, branch
, path
);
2607 * Zero out the filemask for the old ci. At this point, ci
2608 * was just an entry for a directory, so we don't need to
2609 * do anything more with it.
2614 * Now note that we're working on the new entry (path was
2621 * NOTE: Below there is a long switch-like if-elseif-elseif... block
2622 * which the code goes through even for the df_conflict cases
2625 if (ci
->match_mask
) {
2626 ci
->merged
.clean
= 1;
2627 if (ci
->match_mask
== 6) {
2628 /* stages[1] == stages[2] */
2629 ci
->merged
.result
.mode
= ci
->stages
[1].mode
;
2630 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[1].oid
);
2632 /* determine the mask of the side that didn't match */
2633 unsigned int othermask
= 7 & ~ci
->match_mask
;
2634 int side
= (othermask
== 4) ? 2 : 1;
2636 ci
->merged
.result
.mode
= ci
->stages
[side
].mode
;
2637 ci
->merged
.is_null
= !ci
->merged
.result
.mode
;
2638 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[side
].oid
);
2640 assert(othermask
== 2 || othermask
== 4);
2641 assert(ci
->merged
.is_null
==
2642 (ci
->filemask
== ci
->match_mask
));
2644 } else if (ci
->filemask
>= 6 &&
2645 (S_IFMT
& ci
->stages
[1].mode
) !=
2646 (S_IFMT
& ci
->stages
[2].mode
)) {
2647 /* Two different items from (file/submodule/symlink) */
2648 if (opt
->priv
->call_depth
) {
2649 /* Just use the version from the merge base */
2650 ci
->merged
.clean
= 0;
2651 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[0].oid
);
2652 ci
->merged
.result
.mode
= ci
->stages
[0].mode
;
2653 ci
->merged
.is_null
= (ci
->merged
.result
.mode
== 0);
2655 /* Handle by renaming one or both to separate paths. */
2656 unsigned o_mode
= ci
->stages
[0].mode
;
2657 unsigned a_mode
= ci
->stages
[1].mode
;
2658 unsigned b_mode
= ci
->stages
[2].mode
;
2659 struct conflict_info
*new_ci
;
2660 const char *a_path
= NULL
, *b_path
= NULL
;
2661 int rename_a
= 0, rename_b
= 0;
2663 new_ci
= xmalloc(sizeof(*new_ci
));
2665 if (S_ISREG(a_mode
))
2667 else if (S_ISREG(b_mode
))
2674 path_msg(opt
, path
, 0,
2675 _("CONFLICT (distinct types): %s had different "
2676 "types on each side; renamed %s of them so "
2677 "each can be recorded somewhere."),
2679 (rename_a
&& rename_b
) ? _("both") : _("one"));
2681 ci
->merged
.clean
= 0;
2682 memcpy(new_ci
, ci
, sizeof(*new_ci
));
2684 /* Put b into new_ci, removing a from stages */
2685 new_ci
->merged
.result
.mode
= ci
->stages
[2].mode
;
2686 oidcpy(&new_ci
->merged
.result
.oid
, &ci
->stages
[2].oid
);
2687 new_ci
->stages
[1].mode
= 0;
2688 oidcpy(&new_ci
->stages
[1].oid
, &null_oid
);
2689 new_ci
->filemask
= 5;
2690 if ((S_IFMT
& b_mode
) != (S_IFMT
& o_mode
)) {
2691 new_ci
->stages
[0].mode
= 0;
2692 oidcpy(&new_ci
->stages
[0].oid
, &null_oid
);
2693 new_ci
->filemask
= 4;
2696 /* Leave only a in ci, fixing stages. */
2697 ci
->merged
.result
.mode
= ci
->stages
[1].mode
;
2698 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[1].oid
);
2699 ci
->stages
[2].mode
= 0;
2700 oidcpy(&ci
->stages
[2].oid
, &null_oid
);
2702 if ((S_IFMT
& a_mode
) != (S_IFMT
& o_mode
)) {
2703 ci
->stages
[0].mode
= 0;
2704 oidcpy(&ci
->stages
[0].oid
, &null_oid
);
2708 /* Insert entries into opt->priv_paths */
2709 assert(rename_a
|| rename_b
);
2711 a_path
= unique_path(&opt
->priv
->paths
,
2712 path
, opt
->branch1
);
2713 strmap_put(&opt
->priv
->paths
, a_path
, ci
);
2717 b_path
= unique_path(&opt
->priv
->paths
,
2718 path
, opt
->branch2
);
2721 strmap_put(&opt
->priv
->paths
, b_path
, new_ci
);
2723 if (rename_a
&& rename_b
) {
2724 strmap_remove(&opt
->priv
->paths
, path
, 0);
2726 * We removed path from opt->priv->paths. path
2727 * will also eventually need to be freed, but
2728 * it may still be used by e.g. ci->pathnames.
2729 * So, store it in another string-list for now.
2731 string_list_append(&opt
->priv
->paths_to_free
,
2736 * Do special handling for b_path since process_entry()
2737 * won't be called on it specially.
2739 strmap_put(&opt
->priv
->conflicted
, b_path
, new_ci
);
2740 record_entry_for_tree(dir_metadata
, b_path
,
2744 * Remaining code for processing this entry should
2745 * think in terms of processing a_path.
2750 } else if (ci
->filemask
>= 6) {
2751 /* Need a two-way or three-way content merge */
2752 struct version_info merged_file
;
2753 unsigned clean_merge
;
2754 struct version_info
*o
= &ci
->stages
[0];
2755 struct version_info
*a
= &ci
->stages
[1];
2756 struct version_info
*b
= &ci
->stages
[2];
2758 clean_merge
= handle_content_merge(opt
, path
, o
, a
, b
,
2760 opt
->priv
->call_depth
* 2,
2762 ci
->merged
.clean
= clean_merge
&&
2763 !ci
->df_conflict
&& !ci
->path_conflict
;
2764 ci
->merged
.result
.mode
= merged_file
.mode
;
2765 ci
->merged
.is_null
= (merged_file
.mode
== 0);
2766 oidcpy(&ci
->merged
.result
.oid
, &merged_file
.oid
);
2767 if (clean_merge
&& ci
->df_conflict
) {
2768 assert(df_file_index
== 1 || df_file_index
== 2);
2769 ci
->filemask
= 1 << df_file_index
;
2770 ci
->stages
[df_file_index
].mode
= merged_file
.mode
;
2771 oidcpy(&ci
->stages
[df_file_index
].oid
, &merged_file
.oid
);
2774 const char *reason
= _("content");
2775 if (ci
->filemask
== 6)
2776 reason
= _("add/add");
2777 if (S_ISGITLINK(merged_file
.mode
))
2778 reason
= _("submodule");
2779 path_msg(opt
, path
, 0,
2780 _("CONFLICT (%s): Merge conflict in %s"),
2783 } else if (ci
->filemask
== 3 || ci
->filemask
== 5) {
2785 const char *modify_branch
, *delete_branch
;
2786 int side
= (ci
->filemask
== 5) ? 2 : 1;
2787 int index
= opt
->priv
->call_depth
? 0 : side
;
2789 ci
->merged
.result
.mode
= ci
->stages
[index
].mode
;
2790 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[index
].oid
);
2791 ci
->merged
.clean
= 0;
2793 modify_branch
= (side
== 1) ? opt
->branch1
: opt
->branch2
;
2794 delete_branch
= (side
== 1) ? opt
->branch2
: opt
->branch1
;
2796 if (ci
->path_conflict
&&
2797 oideq(&ci
->stages
[0].oid
, &ci
->stages
[side
].oid
)) {
2799 * This came from a rename/delete; no action to take,
2800 * but avoid printing "modify/delete" conflict notice
2801 * since the contents were not modified.
2804 path_msg(opt
, path
, 0,
2805 _("CONFLICT (modify/delete): %s deleted in %s "
2806 "and modified in %s. Version %s of %s left "
2808 path
, delete_branch
, modify_branch
,
2809 modify_branch
, path
);
2811 } else if (ci
->filemask
== 2 || ci
->filemask
== 4) {
2812 /* Added on one side */
2813 int side
= (ci
->filemask
== 4) ? 2 : 1;
2814 ci
->merged
.result
.mode
= ci
->stages
[side
].mode
;
2815 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[side
].oid
);
2816 ci
->merged
.clean
= !ci
->df_conflict
&& !ci
->path_conflict
;
2817 } else if (ci
->filemask
== 1) {
2818 /* Deleted on both sides */
2819 ci
->merged
.is_null
= 1;
2820 ci
->merged
.result
.mode
= 0;
2821 oidcpy(&ci
->merged
.result
.oid
, &null_oid
);
2822 ci
->merged
.clean
= !ci
->path_conflict
;
2826 * If still conflicted, record it separately. This allows us to later
2827 * iterate over just conflicted entries when updating the index instead
2828 * of iterating over all entries.
2830 if (!ci
->merged
.clean
)
2831 strmap_put(&opt
->priv
->conflicted
, path
, ci
);
2832 record_entry_for_tree(dir_metadata
, path
, &ci
->merged
);
2835 static void process_entries(struct merge_options
*opt
,
2836 struct object_id
*result_oid
)
2838 struct hashmap_iter iter
;
2839 struct strmap_entry
*e
;
2840 struct string_list plist
= STRING_LIST_INIT_NODUP
;
2841 struct string_list_item
*entry
;
2842 struct directory_versions dir_metadata
= { STRING_LIST_INIT_NODUP
,
2843 STRING_LIST_INIT_NODUP
,
2846 trace2_region_enter("merge", "process_entries setup", opt
->repo
);
2847 if (strmap_empty(&opt
->priv
->paths
)) {
2848 oidcpy(result_oid
, opt
->repo
->hash_algo
->empty_tree
);
2852 /* Hack to pre-allocate plist to the desired size */
2853 trace2_region_enter("merge", "plist grow", opt
->repo
);
2854 ALLOC_GROW(plist
.items
, strmap_get_size(&opt
->priv
->paths
), plist
.alloc
);
2855 trace2_region_leave("merge", "plist grow", opt
->repo
);
2857 /* Put every entry from paths into plist, then sort */
2858 trace2_region_enter("merge", "plist copy", opt
->repo
);
2859 strmap_for_each_entry(&opt
->priv
->paths
, &iter
, e
) {
2860 string_list_append(&plist
, e
->key
)->util
= e
->value
;
2862 trace2_region_leave("merge", "plist copy", opt
->repo
);
2864 trace2_region_enter("merge", "plist special sort", opt
->repo
);
2865 plist
.cmp
= string_list_df_name_compare
;
2866 string_list_sort(&plist
);
2867 trace2_region_leave("merge", "plist special sort", opt
->repo
);
2869 trace2_region_leave("merge", "process_entries setup", opt
->repo
);
2872 * Iterate over the items in reverse order, so we can handle paths
2873 * below a directory before needing to handle the directory itself.
2875 * This allows us to write subtrees before we need to write trees,
2876 * and it also enables sane handling of directory/file conflicts
2877 * (because it allows us to know whether the directory is still in
2878 * the way when it is time to process the file at the same path).
2880 trace2_region_enter("merge", "processing", opt
->repo
);
2881 for (entry
= &plist
.items
[plist
.nr
-1]; entry
>= plist
.items
; --entry
) {
2882 char *path
= entry
->string
;
2884 * NOTE: mi may actually be a pointer to a conflict_info, but
2885 * we have to check mi->clean first to see if it's safe to
2886 * reassign to such a pointer type.
2888 struct merged_info
*mi
= entry
->util
;
2890 write_completed_directory(opt
, mi
->directory_name
,
2893 record_entry_for_tree(&dir_metadata
, path
, mi
);
2895 struct conflict_info
*ci
= (struct conflict_info
*)mi
;
2896 process_entry(opt
, path
, ci
, &dir_metadata
);
2899 trace2_region_leave("merge", "processing", opt
->repo
);
2901 trace2_region_enter("merge", "process_entries cleanup", opt
->repo
);
2902 if (dir_metadata
.offsets
.nr
!= 1 ||
2903 (uintptr_t)dir_metadata
.offsets
.items
[0].util
!= 0) {
2904 printf("dir_metadata.offsets.nr = %d (should be 1)\n",
2905 dir_metadata
.offsets
.nr
);
2906 printf("dir_metadata.offsets.items[0].util = %u (should be 0)\n",
2907 (unsigned)(uintptr_t)dir_metadata
.offsets
.items
[0].util
);
2909 BUG("dir_metadata accounting completely off; shouldn't happen");
2911 write_tree(result_oid
, &dir_metadata
.versions
, 0,
2912 opt
->repo
->hash_algo
->rawsz
);
2913 string_list_clear(&plist
, 0);
2914 string_list_clear(&dir_metadata
.versions
, 0);
2915 string_list_clear(&dir_metadata
.offsets
, 0);
2916 trace2_region_leave("merge", "process_entries cleanup", opt
->repo
);
2919 /*** Function Grouping: functions related to merge_switch_to_result() ***/
2921 static int checkout(struct merge_options
*opt
,
2925 /* Switch the index/working copy from old to new */
2927 struct tree_desc trees
[2];
2928 struct unpack_trees_options unpack_opts
;
2930 memset(&unpack_opts
, 0, sizeof(unpack_opts
));
2931 unpack_opts
.head_idx
= -1;
2932 unpack_opts
.src_index
= opt
->repo
->index
;
2933 unpack_opts
.dst_index
= opt
->repo
->index
;
2935 setup_unpack_trees_porcelain(&unpack_opts
, "merge");
2938 * NOTE: if this were just "git checkout" code, we would probably
2939 * read or refresh the cache and check for a conflicted index, but
2940 * builtin/merge.c or sequencer.c really needs to read the index
2941 * and check for conflicted entries before starting merging for a
2942 * good user experience (no sense waiting for merges/rebases before
2943 * erroring out), so there's no reason to duplicate that work here.
2946 /* 2-way merge to the new branch */
2947 unpack_opts
.update
= 1;
2948 unpack_opts
.merge
= 1;
2949 unpack_opts
.quiet
= 0; /* FIXME: sequencer might want quiet? */
2950 unpack_opts
.verbose_update
= (opt
->verbosity
> 2);
2951 unpack_opts
.fn
= twoway_merge
;
2952 if (1/* FIXME: opts->overwrite_ignore*/) {
2953 CALLOC_ARRAY(unpack_opts
.dir
, 1);
2954 unpack_opts
.dir
->flags
|= DIR_SHOW_IGNORED
;
2955 setup_standard_excludes(unpack_opts
.dir
);
2958 init_tree_desc(&trees
[0], prev
->buffer
, prev
->size
);
2960 init_tree_desc(&trees
[1], next
->buffer
, next
->size
);
2962 ret
= unpack_trees(2, trees
, &unpack_opts
);
2963 clear_unpack_trees_porcelain(&unpack_opts
);
2964 dir_clear(unpack_opts
.dir
);
2965 FREE_AND_NULL(unpack_opts
.dir
);
2969 static int record_conflicted_index_entries(struct merge_options
*opt
,
2970 struct index_state
*index
,
2971 struct strmap
*paths
,
2972 struct strmap
*conflicted
)
2974 struct hashmap_iter iter
;
2975 struct strmap_entry
*e
;
2977 int original_cache_nr
;
2979 if (strmap_empty(conflicted
))
2982 original_cache_nr
= index
->cache_nr
;
2984 /* Put every entry from paths into plist, then sort */
2985 strmap_for_each_entry(conflicted
, &iter
, e
) {
2986 const char *path
= e
->key
;
2987 struct conflict_info
*ci
= e
->value
;
2989 struct cache_entry
*ce
;
2995 * The index will already have a stage=0 entry for this path,
2996 * because we created an as-merged-as-possible version of the
2997 * file and checkout() moved the working copy and index over
3000 * However, previous iterations through this loop will have
3001 * added unstaged entries to the end of the cache which
3002 * ignore the standard alphabetical ordering of cache
3003 * entries and break invariants needed for index_name_pos()
3004 * to work. However, we know the entry we want is before
3005 * those appended cache entries, so do a temporary swap on
3006 * cache_nr to only look through entries of interest.
3008 SWAP(index
->cache_nr
, original_cache_nr
);
3009 pos
= index_name_pos(index
, path
, strlen(path
));
3010 SWAP(index
->cache_nr
, original_cache_nr
);
3012 if (ci
->filemask
!= 1)
3013 BUG("Conflicted %s but nothing in basic working tree or index; this shouldn't happen", path
);
3014 cache_tree_invalidate_path(index
, path
);
3016 ce
= index
->cache
[pos
];
3019 * Clean paths with CE_SKIP_WORKTREE set will not be
3020 * written to the working tree by the unpack_trees()
3021 * call in checkout(). Our conflicted entries would
3022 * have appeared clean to that code since we ignored
3023 * the higher order stages. Thus, we need override
3024 * the CE_SKIP_WORKTREE bit and manually write those
3025 * files to the working disk here.
3027 * TODO: Implement this CE_SKIP_WORKTREE fixup.
3031 * Mark this cache entry for removal and instead add
3032 * new stage>0 entries corresponding to the
3033 * conflicts. If there are many conflicted entries, we
3034 * want to avoid memmove'ing O(NM) entries by
3035 * inserting the new entries one at a time. So,
3036 * instead, we just add the new cache entries to the
3037 * end (ignoring normal index requirements on sort
3038 * order) and sort the index once we're all done.
3040 ce
->ce_flags
|= CE_REMOVE
;
3043 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
3044 struct version_info
*vi
;
3045 if (!(ci
->filemask
& (1ul << i
)))
3047 vi
= &ci
->stages
[i
];
3048 ce
= make_cache_entry(index
, vi
->mode
, &vi
->oid
,
3050 add_index_entry(index
, ce
, ADD_CACHE_JUST_APPEND
);
3055 * Remove the unused cache entries (and invalidate the relevant
3056 * cache-trees), then sort the index entries to get the conflicted
3057 * entries we added to the end into their right locations.
3059 remove_marked_cache_entries(index
, 1);
3060 QSORT(index
->cache
, index
->cache_nr
, cmp_cache_name_compare
);
3065 void merge_switch_to_result(struct merge_options
*opt
,
3067 struct merge_result
*result
,
3068 int update_worktree_and_index
,
3069 int display_update_msgs
)
3071 assert(opt
->priv
== NULL
);
3072 if (result
->clean
>= 0 && update_worktree_and_index
) {
3073 struct merge_options_internal
*opti
= result
->priv
;
3075 trace2_region_enter("merge", "checkout", opt
->repo
);
3076 if (checkout(opt
, head
, result
->tree
)) {
3077 /* failure to function */
3081 trace2_region_leave("merge", "checkout", opt
->repo
);
3083 trace2_region_enter("merge", "record_conflicted", opt
->repo
);
3084 if (record_conflicted_index_entries(opt
, opt
->repo
->index
,
3086 &opti
->conflicted
)) {
3087 /* failure to function */
3091 trace2_region_leave("merge", "record_conflicted", opt
->repo
);
3094 if (display_update_msgs
) {
3095 struct merge_options_internal
*opti
= result
->priv
;
3096 struct hashmap_iter iter
;
3097 struct strmap_entry
*e
;
3098 struct string_list olist
= STRING_LIST_INIT_NODUP
;
3101 trace2_region_enter("merge", "display messages", opt
->repo
);
3103 /* Hack to pre-allocate olist to the desired size */
3104 ALLOC_GROW(olist
.items
, strmap_get_size(&opti
->output
),
3107 /* Put every entry from output into olist, then sort */
3108 strmap_for_each_entry(&opti
->output
, &iter
, e
) {
3109 string_list_append(&olist
, e
->key
)->util
= e
->value
;
3111 string_list_sort(&olist
);
3113 /* Iterate over the items, printing them */
3114 for (i
= 0; i
< olist
.nr
; ++i
) {
3115 struct strbuf
*sb
= olist
.items
[i
].util
;
3117 printf("%s", sb
->buf
);
3119 string_list_clear(&olist
, 0);
3121 /* Also include needed rename limit adjustment now */
3122 diff_warn_rename_limit("merge.renamelimit",
3123 opti
->renames
.needed_limit
, 0);
3125 trace2_region_leave("merge", "display messages", opt
->repo
);
3128 merge_finalize(opt
, result
);
3131 void merge_finalize(struct merge_options
*opt
,
3132 struct merge_result
*result
)
3134 struct merge_options_internal
*opti
= result
->priv
;
3136 assert(opt
->priv
== NULL
);
3138 clear_or_reinit_internal_opts(opti
, 0);
3139 FREE_AND_NULL(opti
);
3142 /*** Function Grouping: helper functions for merge_incore_*() ***/
3144 static inline void set_commit_tree(struct commit
*c
, struct tree
*t
)
3149 static struct commit
*make_virtual_commit(struct repository
*repo
,
3151 const char *comment
)
3153 struct commit
*commit
= alloc_commit_node(repo
);
3155 set_merge_remote_desc(commit
, comment
, (struct object
*)commit
);
3156 set_commit_tree(commit
, tree
);
3157 commit
->object
.parsed
= 1;
3161 static void merge_start(struct merge_options
*opt
, struct merge_result
*result
)
3163 struct rename_info
*renames
;
3166 /* Sanity checks on opt */
3167 trace2_region_enter("merge", "sanity checks", opt
->repo
);
3170 assert(opt
->branch1
&& opt
->branch2
);
3172 assert(opt
->detect_directory_renames
>= MERGE_DIRECTORY_RENAMES_NONE
&&
3173 opt
->detect_directory_renames
<= MERGE_DIRECTORY_RENAMES_TRUE
);
3174 assert(opt
->rename_limit
>= -1);
3175 assert(opt
->rename_score
>= 0 && opt
->rename_score
<= MAX_SCORE
);
3176 assert(opt
->show_rename_progress
>= 0 && opt
->show_rename_progress
<= 1);
3178 assert(opt
->xdl_opts
>= 0);
3179 assert(opt
->recursive_variant
>= MERGE_VARIANT_NORMAL
&&
3180 opt
->recursive_variant
<= MERGE_VARIANT_THEIRS
);
3183 * detect_renames, verbosity, buffer_output, and obuf are ignored
3184 * fields that were used by "recursive" rather than "ort" -- but
3185 * sanity check them anyway.
3187 assert(opt
->detect_renames
>= -1 &&
3188 opt
->detect_renames
<= DIFF_DETECT_COPY
);
3189 assert(opt
->verbosity
>= 0 && opt
->verbosity
<= 5);
3190 assert(opt
->buffer_output
<= 2);
3191 assert(opt
->obuf
.len
== 0);
3193 assert(opt
->priv
== NULL
);
3195 opt
->priv
= result
->priv
;
3196 result
->priv
= NULL
;
3198 * opt->priv non-NULL means we had results from a previous
3199 * run; do a few sanity checks that user didn't mess with
3200 * it in an obvious fashion.
3202 assert(opt
->priv
->call_depth
== 0);
3203 assert(!opt
->priv
->toplevel_dir
||
3204 0 == strlen(opt
->priv
->toplevel_dir
));
3206 trace2_region_leave("merge", "sanity checks", opt
->repo
);
3208 /* Default to histogram diff. Actually, just hardcode it...for now. */
3209 opt
->xdl_opts
= DIFF_WITH_ALG(opt
, HISTOGRAM_DIFF
);
3211 /* Initialization of opt->priv, our internal merge data */
3212 trace2_region_enter("merge", "allocate/init", opt
->repo
);
3214 clear_or_reinit_internal_opts(opt
->priv
, 1);
3215 trace2_region_leave("merge", "allocate/init", opt
->repo
);
3218 opt
->priv
= xcalloc(1, sizeof(*opt
->priv
));
3220 /* Initialization of various renames fields */
3221 renames
= &opt
->priv
->renames
;
3222 for (i
= MERGE_SIDE1
; i
<= MERGE_SIDE2
; i
++) {
3223 strset_init_with_options(&renames
->dirs_removed
[i
],
3225 strmap_init_with_options(&renames
->dir_rename_count
[i
],
3227 strmap_init_with_options(&renames
->dir_renames
[i
],
3232 * Although we initialize opt->priv->paths with strdup_strings=0,
3233 * that's just to avoid making yet another copy of an allocated
3234 * string. Putting the entry into paths means we are taking
3235 * ownership, so we will later free it. paths_to_free is similar.
3237 * In contrast, conflicted just has a subset of keys from paths, so
3238 * we don't want to free those (it'd be a duplicate free).
3240 strmap_init_with_options(&opt
->priv
->paths
, NULL
, 0);
3241 strmap_init_with_options(&opt
->priv
->conflicted
, NULL
, 0);
3242 string_list_init(&opt
->priv
->paths_to_free
, 0);
3245 * keys & strbufs in output will sometimes need to outlive "paths",
3246 * so it will have a copy of relevant keys. It's probably a small
3247 * subset of the overall paths that have special output.
3249 strmap_init(&opt
->priv
->output
);
3251 trace2_region_leave("merge", "allocate/init", opt
->repo
);
3254 /*** Function Grouping: merge_incore_*() and their internal variants ***/
3257 * Originally from merge_trees_internal(); heavily adapted, though.
3259 static void merge_ort_nonrecursive_internal(struct merge_options
*opt
,
3260 struct tree
*merge_base
,
3263 struct merge_result
*result
)
3265 struct object_id working_tree_oid
;
3267 trace2_region_enter("merge", "collect_merge_info", opt
->repo
);
3268 if (collect_merge_info(opt
, merge_base
, side1
, side2
) != 0) {
3270 * TRANSLATORS: The %s arguments are: 1) tree hash of a merge
3271 * base, and 2-3) the trees for the two trees we're merging.
3273 err(opt
, _("collecting merge info failed for trees %s, %s, %s"),
3274 oid_to_hex(&merge_base
->object
.oid
),
3275 oid_to_hex(&side1
->object
.oid
),
3276 oid_to_hex(&side2
->object
.oid
));
3280 trace2_region_leave("merge", "collect_merge_info", opt
->repo
);
3282 trace2_region_enter("merge", "renames", opt
->repo
);
3283 result
->clean
= detect_and_process_renames(opt
, merge_base
,
3285 trace2_region_leave("merge", "renames", opt
->repo
);
3287 trace2_region_enter("merge", "process_entries", opt
->repo
);
3288 process_entries(opt
, &working_tree_oid
);
3289 trace2_region_leave("merge", "process_entries", opt
->repo
);
3291 /* Set return values */
3292 result
->tree
= parse_tree_indirect(&working_tree_oid
);
3293 /* existence of conflicted entries implies unclean */
3294 result
->clean
&= strmap_empty(&opt
->priv
->conflicted
);
3295 if (!opt
->priv
->call_depth
) {
3296 result
->priv
= opt
->priv
;
3302 * Originally from merge_recursive_internal(); somewhat adapted, though.
3304 static void merge_ort_internal(struct merge_options
*opt
,
3305 struct commit_list
*merge_bases
,
3308 struct merge_result
*result
)
3310 struct commit_list
*iter
;
3311 struct commit
*merged_merge_bases
;
3312 const char *ancestor_name
;
3313 struct strbuf merge_base_abbrev
= STRBUF_INIT
;
3316 merge_bases
= get_merge_bases(h1
, h2
);
3317 /* See merge-ort.h:merge_incore_recursive() declaration NOTE */
3318 merge_bases
= reverse_commit_list(merge_bases
);
3321 merged_merge_bases
= pop_commit(&merge_bases
);
3322 if (merged_merge_bases
== NULL
) {
3323 /* if there is no common ancestor, use an empty tree */
3326 tree
= lookup_tree(opt
->repo
, opt
->repo
->hash_algo
->empty_tree
);
3327 merged_merge_bases
= make_virtual_commit(opt
->repo
, tree
,
3329 ancestor_name
= "empty tree";
3330 } else if (merge_bases
) {
3331 ancestor_name
= "merged common ancestors";
3333 strbuf_add_unique_abbrev(&merge_base_abbrev
,
3334 &merged_merge_bases
->object
.oid
,
3336 ancestor_name
= merge_base_abbrev
.buf
;
3339 for (iter
= merge_bases
; iter
; iter
= iter
->next
) {
3340 const char *saved_b1
, *saved_b2
;
3341 struct commit
*prev
= merged_merge_bases
;
3343 opt
->priv
->call_depth
++;
3345 * When the merge fails, the result contains files
3346 * with conflict markers. The cleanness flag is
3347 * ignored (unless indicating an error), it was never
3348 * actually used, as result of merge_trees has always
3349 * overwritten it: the committed "conflicts" were
3352 saved_b1
= opt
->branch1
;
3353 saved_b2
= opt
->branch2
;
3354 opt
->branch1
= "Temporary merge branch 1";
3355 opt
->branch2
= "Temporary merge branch 2";
3356 merge_ort_internal(opt
, NULL
, prev
, iter
->item
, result
);
3357 if (result
->clean
< 0)
3359 opt
->branch1
= saved_b1
;
3360 opt
->branch2
= saved_b2
;
3361 opt
->priv
->call_depth
--;
3363 merged_merge_bases
= make_virtual_commit(opt
->repo
,
3366 commit_list_insert(prev
, &merged_merge_bases
->parents
);
3367 commit_list_insert(iter
->item
,
3368 &merged_merge_bases
->parents
->next
);
3370 clear_or_reinit_internal_opts(opt
->priv
, 1);
3373 opt
->ancestor
= ancestor_name
;
3374 merge_ort_nonrecursive_internal(opt
,
3375 repo_get_commit_tree(opt
->repo
,
3376 merged_merge_bases
),
3377 repo_get_commit_tree(opt
->repo
, h1
),
3378 repo_get_commit_tree(opt
->repo
, h2
),
3380 strbuf_release(&merge_base_abbrev
);
3381 opt
->ancestor
= NULL
; /* avoid accidental re-use of opt->ancestor */
3384 void merge_incore_nonrecursive(struct merge_options
*opt
,
3385 struct tree
*merge_base
,
3388 struct merge_result
*result
)
3390 trace2_region_enter("merge", "incore_nonrecursive", opt
->repo
);
3392 trace2_region_enter("merge", "merge_start", opt
->repo
);
3393 assert(opt
->ancestor
!= NULL
);
3394 merge_start(opt
, result
);
3395 trace2_region_leave("merge", "merge_start", opt
->repo
);
3397 merge_ort_nonrecursive_internal(opt
, merge_base
, side1
, side2
, result
);
3398 trace2_region_leave("merge", "incore_nonrecursive", opt
->repo
);
3401 void merge_incore_recursive(struct merge_options
*opt
,
3402 struct commit_list
*merge_bases
,
3403 struct commit
*side1
,
3404 struct commit
*side2
,
3405 struct merge_result
*result
)
3407 trace2_region_enter("merge", "incore_recursive", opt
->repo
);
3409 /* We set the ancestor label based on the merge_bases */
3410 assert(opt
->ancestor
== NULL
);
3412 trace2_region_enter("merge", "merge_start", opt
->repo
);
3413 merge_start(opt
, result
);
3414 trace2_region_leave("merge", "merge_start", opt
->repo
);
3416 merge_ort_internal(opt
, merge_bases
, side1
, side2
, result
);
3417 trace2_region_leave("merge", "incore_recursive", opt
->repo
);