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"
28 #include "object-store.h"
31 #include "unpack-trees.h"
32 #include "xdiff-interface.h"
35 * We have many arrays of size 3. Whenever we have such an array, the
36 * indices refer to one of the sides of the three-way merge. This is so
37 * pervasive that the constants 0, 1, and 2 are used in many places in the
38 * code (especially in arithmetic operations to find the other side's index
39 * or to compute a relevant mask), but sometimes these enum names are used
40 * to aid code clarity.
42 * See also 'filemask' and 'dirmask' in struct conflict_info; the "ith side"
43 * referred to there is one of these three sides.
53 * pairs: pairing of filenames from diffcore_rename()
55 * Index 1 and 2 correspond to sides 1 & 2 as used in
56 * conflict_info.stages. Index 0 unused.
58 struct diff_queue_struct pairs
[3];
61 * needed_limit: value needed for inexact rename detection to run
63 * If the current rename limit wasn't high enough for inexact
64 * rename detection to run, this records the limit needed. Otherwise,
65 * this value remains 0.
70 struct merge_options_internal
{
72 * paths: primary data structure in all of merge ort.
75 * * are full relative paths from the toplevel of the repository
76 * (e.g. "drivers/firmware/raspberrypi.c").
77 * * store all relevant paths in the repo, both directories and
78 * files (e.g. drivers, drivers/firmware would also be included)
79 * * these keys serve to intern all the path strings, which allows
80 * us to do pointer comparison on directory names instead of
81 * strcmp; we just have to be careful to use the interned strings.
82 * (Technically paths_to_free may track some strings that were
83 * removed from froms paths.)
85 * The values of paths:
86 * * either a pointer to a merged_info, or a conflict_info struct
87 * * merged_info contains all relevant information for a
88 * non-conflicted entry.
89 * * conflict_info contains a merged_info, plus any additional
90 * information about a conflict such as the higher orders stages
91 * involved and the names of the paths those came from (handy
92 * once renames get involved).
93 * * a path may start "conflicted" (i.e. point to a conflict_info)
94 * and then a later step (e.g. three-way content merge) determines
95 * it can be cleanly merged, at which point it'll be marked clean
96 * and the algorithm will ignore any data outside the contained
97 * merged_info for that entry
98 * * If an entry remains conflicted, the merged_info portion of a
99 * conflict_info will later be filled with whatever version of
100 * the file should be placed in the working directory (e.g. an
101 * as-merged-as-possible variation that contains conflict markers).
106 * conflicted: a subset of keys->values from "paths"
108 * conflicted is basically an optimization between process_entries()
109 * and record_conflicted_index_entries(); the latter could loop over
110 * ALL the entries in paths AGAIN and look for the ones that are
111 * still conflicted, but since process_entries() has to loop over
112 * all of them, it saves the ones it couldn't resolve in this strmap
113 * so that record_conflicted_index_entries() can iterate just the
116 struct strmap conflicted
;
119 * paths_to_free: additional list of strings to free
121 * If keys are removed from "paths", they are added to paths_to_free
122 * to ensure they are later freed. We avoid free'ing immediately since
123 * other places (e.g. conflict_info.pathnames[]) may still be
124 * referencing these paths.
126 struct string_list paths_to_free
;
129 * output: special messages and conflict notices for various paths
131 * This is a map of pathnames (a subset of the keys in "paths" above)
132 * to strbufs. It gathers various warning/conflict/notice messages
133 * for later processing.
135 struct strmap output
;
138 * renames: various data relating to rename detection
140 struct rename_info renames
;
143 * current_dir_name: temporary var used in collect_merge_info_callback()
145 * Used to set merged_info.directory_name; see documentation for that
146 * variable and the requirements placed on that field.
148 const char *current_dir_name
;
150 /* call_depth: recursion level counter for merging merge bases */
154 struct version_info
{
155 struct object_id oid
;
160 /* if is_null, ignore result. otherwise result has oid & mode */
161 struct version_info result
;
165 * clean: whether the path in question is cleanly merged.
167 * see conflict_info.merged for more details.
172 * basename_offset: offset of basename of path.
174 * perf optimization to avoid recomputing offset of final '/'
175 * character in pathname (0 if no '/' in pathname).
177 size_t basename_offset
;
180 * directory_name: containing directory name.
182 * Note that we assume directory_name is constructed such that
183 * strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name,
184 * i.e. string equality is equivalent to pointer equality. For this
185 * to hold, we have to be careful setting directory_name.
187 const char *directory_name
;
190 struct conflict_info
{
192 * merged: the version of the path that will be written to working tree
194 * WARNING: It is critical to check merged.clean and ensure it is 0
195 * before reading any conflict_info fields outside of merged.
196 * Allocated merge_info structs will always have clean set to 1.
197 * Allocated conflict_info structs will have merged.clean set to 0
198 * initially. The merged.clean field is how we know if it is safe
199 * to access other parts of conflict_info besides merged; if a
200 * conflict_info's merged.clean is changed to 1, the rest of the
201 * algorithm is not allowed to look at anything outside of the
202 * merged member anymore.
204 struct merged_info merged
;
206 /* oids & modes from each of the three trees for this path */
207 struct version_info stages
[3];
209 /* pathnames for each stage; may differ due to rename detection */
210 const char *pathnames
[3];
212 /* Whether this path is/was involved in a directory/file conflict */
213 unsigned df_conflict
:1;
216 * Whether this path is/was involved in a non-content conflict other
217 * than a directory/file conflict (e.g. rename/rename, rename/delete,
218 * file location based on possible directory rename).
220 unsigned path_conflict
:1;
223 * For filemask and dirmask, the ith bit corresponds to whether the
224 * ith entry is a file (filemask) or a directory (dirmask). Thus,
225 * filemask & dirmask is always zero, and filemask | dirmask is at
226 * most 7 but can be less when a path does not appear as either a
227 * file or a directory on at least one side of history.
229 * Note that these masks are related to enum merge_side, as the ith
230 * entry corresponds to side i.
232 * These values come from a traverse_trees() call; more info may be
233 * found looking at tree-walk.h's struct traverse_info,
234 * particularly the documentation above the "fn" member (note that
235 * filemask = mask & ~dirmask from that documentation).
241 * Optimization to track which stages match, to avoid the need to
242 * recompute it in multiple steps. Either 0 or at least 2 bits are
243 * set; if at least 2 bits are set, their corresponding stages match.
245 unsigned match_mask
:3;
248 /*** Function Grouping: various utility functions ***/
251 * For the next three macros, see warning for conflict_info.merged.
253 * In each of the below, mi is a struct merged_info*, and ci was defined
254 * as a struct conflict_info* (but we need to verify ci isn't actually
255 * pointed at a struct merged_info*).
257 * INITIALIZE_CI: Assign ci to mi but only if it's safe; set to NULL otherwise.
258 * VERIFY_CI: Ensure that something we assigned to a conflict_info* is one.
259 * ASSIGN_AND_VERIFY_CI: Similar to VERIFY_CI but do assignment first.
261 #define INITIALIZE_CI(ci, mi) do { \
262 (ci) = (!(mi) || (mi)->clean) ? NULL : (struct conflict_info *)(mi); \
264 #define VERIFY_CI(ci) assert(ci && !ci->merged.clean);
265 #define ASSIGN_AND_VERIFY_CI(ci, mi) do { \
266 (ci) = (struct conflict_info *)(mi); \
267 assert((ci) && !(mi)->clean); \
270 static void free_strmap_strings(struct strmap
*map
)
272 struct hashmap_iter iter
;
273 struct strmap_entry
*entry
;
275 strmap_for_each_entry(map
, &iter
, entry
) {
276 free((char*)entry
->key
);
280 static void clear_or_reinit_internal_opts(struct merge_options_internal
*opti
,
283 void (*strmap_func
)(struct strmap
*, int) =
284 reinitialize
? strmap_partial_clear
: strmap_clear
;
287 * We marked opti->paths with strdup_strings = 0, so that we
288 * wouldn't have to make another copy of the fullpath created by
289 * make_traverse_path from setup_path_info(). But, now that we've
290 * used it and have no other references to these strings, it is time
291 * to deallocate them.
293 free_strmap_strings(&opti
->paths
);
294 strmap_func(&opti
->paths
, 1);
297 * All keys and values in opti->conflicted are a subset of those in
298 * opti->paths. We don't want to deallocate anything twice, so we
299 * don't free the keys and we pass 0 for free_values.
301 strmap_func(&opti
->conflicted
, 0);
304 * opti->paths_to_free is similar to opti->paths; we created it with
305 * strdup_strings = 0 to avoid making _another_ copy of the fullpath
306 * but now that we've used it and have no other references to these
307 * strings, it is time to deallocate them. We do so by temporarily
308 * setting strdup_strings to 1.
310 opti
->paths_to_free
.strdup_strings
= 1;
311 string_list_clear(&opti
->paths_to_free
, 0);
312 opti
->paths_to_free
.strdup_strings
= 0;
315 struct hashmap_iter iter
;
316 struct strmap_entry
*e
;
318 /* Release and free each strbuf found in output */
319 strmap_for_each_entry(&opti
->output
, &iter
, e
) {
320 struct strbuf
*sb
= e
->value
;
323 * While strictly speaking we don't need to free(sb)
324 * here because we could pass free_values=1 when
325 * calling strmap_clear() on opti->output, that would
326 * require strmap_clear to do another
327 * strmap_for_each_entry() loop, so we just free it
328 * while we're iterating anyway.
332 strmap_clear(&opti
->output
, 0);
336 static int err(struct merge_options
*opt
, const char *err
, ...)
339 struct strbuf sb
= STRBUF_INIT
;
341 strbuf_addstr(&sb
, "error: ");
342 va_start(params
, err
);
343 strbuf_vaddf(&sb
, err
, params
);
352 __attribute__((format (printf
, 4, 5)))
353 static void path_msg(struct merge_options
*opt
,
355 int omittable_hint
, /* skippable under --remerge-diff */
356 const char *fmt
, ...)
359 struct strbuf
*sb
= strmap_get(&opt
->priv
->output
, path
);
361 sb
= xmalloc(sizeof(*sb
));
363 strmap_put(&opt
->priv
->output
, path
, sb
);
367 strbuf_vaddf(sb
, fmt
, ap
);
370 strbuf_addch(sb
, '\n');
373 /*** Function Grouping: functions related to collect_merge_info() ***/
375 static void setup_path_info(struct merge_options
*opt
,
376 struct string_list_item
*result
,
377 const char *current_dir_name
,
378 int current_dir_name_len
,
379 char *fullpath
, /* we'll take over ownership */
380 struct name_entry
*names
,
381 struct name_entry
*merged_version
,
382 unsigned is_null
, /* boolean */
383 unsigned df_conflict
, /* boolean */
386 int resolved
/* boolean */)
388 /* result->util is void*, so mi is a convenience typed variable */
389 struct merged_info
*mi
;
391 assert(!is_null
|| resolved
);
392 assert(!df_conflict
|| !resolved
); /* df_conflict implies !resolved */
393 assert(resolved
== (merged_version
!= NULL
));
395 mi
= xcalloc(1, resolved
? sizeof(struct merged_info
) :
396 sizeof(struct conflict_info
));
397 mi
->directory_name
= current_dir_name
;
398 mi
->basename_offset
= current_dir_name_len
;
399 mi
->clean
= !!resolved
;
401 mi
->result
.mode
= merged_version
->mode
;
402 oidcpy(&mi
->result
.oid
, &merged_version
->oid
);
403 mi
->is_null
= !!is_null
;
406 struct conflict_info
*ci
;
408 ASSIGN_AND_VERIFY_CI(ci
, mi
);
409 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
410 ci
->pathnames
[i
] = fullpath
;
411 ci
->stages
[i
].mode
= names
[i
].mode
;
412 oidcpy(&ci
->stages
[i
].oid
, &names
[i
].oid
);
414 ci
->filemask
= filemask
;
415 ci
->dirmask
= dirmask
;
416 ci
->df_conflict
= !!df_conflict
;
419 * Assume is_null for now, but if we have entries
420 * under the directory then when it is complete in
421 * write_completed_directory() it'll update this.
422 * Also, for D/F conflicts, we have to handle the
423 * directory first, then clear this bit and process
424 * the file to see how it is handled -- that occurs
425 * near the top of process_entry().
429 strmap_put(&opt
->priv
->paths
, fullpath
, mi
);
430 result
->string
= fullpath
;
434 static int collect_merge_info_callback(int n
,
436 unsigned long dirmask
,
437 struct name_entry
*names
,
438 struct traverse_info
*info
)
442 * common ancestor (mbase) has mask 1, and stored in index 0 of names
443 * head of side 1 (side1) has mask 2, and stored in index 1 of names
444 * head of side 2 (side2) has mask 4, and stored in index 2 of names
446 struct merge_options
*opt
= info
->data
;
447 struct merge_options_internal
*opti
= opt
->priv
;
448 struct string_list_item pi
; /* Path Info */
449 struct conflict_info
*ci
; /* typed alias to pi.util (which is void*) */
450 struct name_entry
*p
;
453 const char *dirname
= opti
->current_dir_name
;
454 unsigned filemask
= mask
& ~dirmask
;
455 unsigned match_mask
= 0; /* will be updated below */
456 unsigned mbase_null
= !(mask
& 1);
457 unsigned side1_null
= !(mask
& 2);
458 unsigned side2_null
= !(mask
& 4);
459 unsigned side1_matches_mbase
= (!side1_null
&& !mbase_null
&&
460 names
[0].mode
== names
[1].mode
&&
461 oideq(&names
[0].oid
, &names
[1].oid
));
462 unsigned side2_matches_mbase
= (!side2_null
&& !mbase_null
&&
463 names
[0].mode
== names
[2].mode
&&
464 oideq(&names
[0].oid
, &names
[2].oid
));
465 unsigned sides_match
= (!side1_null
&& !side2_null
&&
466 names
[1].mode
== names
[2].mode
&&
467 oideq(&names
[1].oid
, &names
[2].oid
));
470 * Note: When a path is a file on one side of history and a directory
471 * in another, we have a directory/file conflict. In such cases, if
472 * the conflict doesn't resolve from renames and deletions, then we
473 * always leave directories where they are and move files out of the
474 * way. Thus, while struct conflict_info has a df_conflict field to
475 * track such conflicts, we ignore that field for any directories at
476 * a path and only pay attention to it for files at the given path.
477 * The fact that we leave directories were they are also means that
478 * we do not need to worry about getting additional df_conflict
479 * information propagated from parent directories down to children
480 * (unlike, say traverse_trees_recursive() in unpack-trees.c, which
481 * sets a newinfo.df_conflicts field specifically to propagate it).
483 unsigned df_conflict
= (filemask
!= 0) && (dirmask
!= 0);
485 /* n = 3 is a fundamental assumption. */
487 BUG("Called collect_merge_info_callback wrong");
490 * A bunch of sanity checks verifying that traverse_trees() calls
491 * us the way I expect. Could just remove these at some point,
492 * though maybe they are helpful to future code readers.
494 assert(mbase_null
== is_null_oid(&names
[0].oid
));
495 assert(side1_null
== is_null_oid(&names
[1].oid
));
496 assert(side2_null
== is_null_oid(&names
[2].oid
));
497 assert(!mbase_null
|| !side1_null
|| !side2_null
);
498 assert(mask
> 0 && mask
< 8);
500 /* Determine match_mask */
501 if (side1_matches_mbase
)
502 match_mask
= (side2_matches_mbase
? 7 : 3);
503 else if (side2_matches_mbase
)
505 else if (sides_match
)
509 * Get the name of the relevant filepath, which we'll pass to
510 * setup_path_info() for tracking.
515 len
= traverse_path_len(info
, p
->pathlen
);
517 /* +1 in both of the following lines to include the NUL byte */
518 fullpath
= xmalloc(len
+ 1);
519 make_traverse_path(fullpath
, len
+ 1, info
, p
->path
, p
->pathlen
);
522 * If mbase, side1, and side2 all match, we can resolve early. Even
523 * if these are trees, there will be no renames or anything
526 if (side1_matches_mbase
&& side2_matches_mbase
) {
527 /* mbase, side1, & side2 all match; use mbase as resolution */
528 setup_path_info(opt
, &pi
, dirname
, info
->pathlen
, fullpath
,
529 names
, names
+0, mbase_null
, 0,
530 filemask
, dirmask
, 1);
535 * Record information about the path so we can resolve later in
538 setup_path_info(opt
, &pi
, dirname
, info
->pathlen
, fullpath
,
539 names
, NULL
, 0, df_conflict
, filemask
, dirmask
, 0);
543 ci
->match_mask
= match_mask
;
545 /* If dirmask, recurse into subdirectories */
547 struct traverse_info newinfo
;
548 struct tree_desc t
[3];
549 void *buf
[3] = {NULL
, NULL
, NULL
};
550 const char *original_dir_name
;
553 ci
->match_mask
&= filemask
;
556 newinfo
.name
= p
->path
;
557 newinfo
.namelen
= p
->pathlen
;
558 newinfo
.pathlen
= st_add3(newinfo
.pathlen
, p
->pathlen
, 1);
560 * If this directory we are about to recurse into cared about
561 * its parent directory (the current directory) having a D/F
562 * conflict, then we'd propagate the masks in this way:
563 * newinfo.df_conflicts |= (mask & ~dirmask);
564 * But we don't worry about propagating D/F conflicts. (See
565 * comment near setting of local df_conflict variable near
566 * the beginning of this function).
569 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
570 if (i
== 1 && side1_matches_mbase
)
572 else if (i
== 2 && side2_matches_mbase
)
574 else if (i
== 2 && sides_match
)
577 const struct object_id
*oid
= NULL
;
580 buf
[i
] = fill_tree_descriptor(opt
->repo
,
586 original_dir_name
= opti
->current_dir_name
;
587 opti
->current_dir_name
= pi
.string
;
588 ret
= traverse_trees(NULL
, 3, t
, &newinfo
);
589 opti
->current_dir_name
= original_dir_name
;
591 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++)
601 static int collect_merge_info(struct merge_options
*opt
,
602 struct tree
*merge_base
,
607 struct tree_desc t
[3];
608 struct traverse_info info
;
609 const char *toplevel_dir_placeholder
= "";
611 opt
->priv
->current_dir_name
= toplevel_dir_placeholder
;
612 setup_traverse_info(&info
, toplevel_dir_placeholder
);
613 info
.fn
= collect_merge_info_callback
;
615 info
.show_all_errors
= 1;
617 parse_tree(merge_base
);
620 init_tree_desc(t
+ 0, merge_base
->buffer
, merge_base
->size
);
621 init_tree_desc(t
+ 1, side1
->buffer
, side1
->size
);
622 init_tree_desc(t
+ 2, side2
->buffer
, side2
->size
);
624 ret
= traverse_trees(NULL
, 3, t
, &info
);
629 /*** Function Grouping: functions related to threeway content merges ***/
631 static int handle_content_merge(struct merge_options
*opt
,
633 const struct version_info
*o
,
634 const struct version_info
*a
,
635 const struct version_info
*b
,
636 const char *pathnames
[3],
637 const int extra_marker_size
,
638 struct version_info
*result
)
640 die("Not yet implemented");
643 /*** Function Grouping: functions related to detect_and_process_renames(), ***
644 *** which are split into directory and regular rename detection sections. ***/
646 /*** Function Grouping: functions related to directory rename detection ***/
648 /*** Function Grouping: functions related to regular rename detection ***/
650 static int process_renames(struct merge_options
*opt
,
651 struct diff_queue_struct
*renames
)
653 int clean_merge
= 1, i
;
655 for (i
= 0; i
< renames
->nr
; ++i
) {
656 const char *oldpath
= NULL
, *newpath
;
657 struct diff_filepair
*pair
= renames
->queue
[i
];
658 struct conflict_info
*oldinfo
= NULL
, *newinfo
= NULL
;
659 struct strmap_entry
*old_ent
, *new_ent
;
660 unsigned int old_sidemask
;
661 int target_index
, other_source_index
;
662 int source_deleted
, collision
, type_changed
;
663 const char *rename_branch
= NULL
, *delete_branch
= NULL
;
665 old_ent
= strmap_get_entry(&opt
->priv
->paths
, pair
->one
->path
);
666 oldpath
= old_ent
->key
;
667 oldinfo
= old_ent
->value
;
669 new_ent
= strmap_get_entry(&opt
->priv
->paths
, pair
->two
->path
);
670 newpath
= new_ent
->key
;
671 newinfo
= new_ent
->value
;
674 * diff_filepairs have copies of pathnames, thus we have to
675 * use standard 'strcmp()' (negated) instead of '=='.
677 if (i
+ 1 < renames
->nr
&&
678 !strcmp(oldpath
, renames
->queue
[i
+1]->one
->path
)) {
679 /* Handle rename/rename(1to2) or rename/rename(1to1) */
680 const char *pathnames
[3];
681 struct version_info merged
;
682 struct conflict_info
*base
, *side1
, *side2
;
683 unsigned was_binary_blob
= 0;
685 pathnames
[0] = oldpath
;
686 pathnames
[1] = newpath
;
687 pathnames
[2] = renames
->queue
[i
+1]->two
->path
;
689 base
= strmap_get(&opt
->priv
->paths
, pathnames
[0]);
690 side1
= strmap_get(&opt
->priv
->paths
, pathnames
[1]);
691 side2
= strmap_get(&opt
->priv
->paths
, pathnames
[2]);
697 if (!strcmp(pathnames
[1], pathnames
[2])) {
698 /* Both sides renamed the same way */
699 assert(side1
== side2
);
700 memcpy(&side1
->stages
[0], &base
->stages
[0],
702 side1
->filemask
|= (1 << MERGE_BASE
);
703 /* Mark base as resolved by removal */
704 base
->merged
.is_null
= 1;
705 base
->merged
.clean
= 1;
707 /* We handled both renames, i.e. i+1 handled */
709 /* Move to next rename */
713 /* This is a rename/rename(1to2) */
714 clean_merge
= handle_content_merge(opt
,
720 1 + 2 * opt
->priv
->call_depth
,
723 merged
.mode
== side1
->stages
[1].mode
&&
724 oideq(&merged
.oid
, &side1
->stages
[1].oid
))
726 memcpy(&side1
->stages
[1], &merged
, sizeof(merged
));
727 if (was_binary_blob
) {
729 * Getting here means we were attempting to
730 * merge a binary blob.
732 * Since we can't merge binaries,
733 * handle_content_merge() just takes one
734 * side. But we don't want to copy the
735 * contents of one side to both paths. We
736 * used the contents of side1 above for
737 * side1->stages, let's use the contents of
738 * side2 for side2->stages below.
740 oidcpy(&merged
.oid
, &side2
->stages
[2].oid
);
741 merged
.mode
= side2
->stages
[2].mode
;
743 memcpy(&side2
->stages
[2], &merged
, sizeof(merged
));
745 side1
->path_conflict
= 1;
746 side2
->path_conflict
= 1;
748 * TODO: For renames we normally remove the path at the
749 * old name. It would thus seem consistent to do the
750 * same for rename/rename(1to2) cases, but we haven't
751 * done so traditionally and a number of the regression
752 * tests now encode an expectation that the file is
753 * left there at stage 1. If we ever decide to change
754 * this, add the following two lines here:
755 * base->merged.is_null = 1;
756 * base->merged.clean = 1;
757 * and remove the setting of base->path_conflict to 1.
759 base
->path_conflict
= 1;
760 path_msg(opt
, oldpath
, 0,
761 _("CONFLICT (rename/rename): %s renamed to "
762 "%s in %s and to %s in %s."),
764 pathnames
[1], opt
->branch1
,
765 pathnames
[2], opt
->branch2
);
767 i
++; /* We handled both renames, i.e. i+1 handled */
773 target_index
= pair
->score
; /* from collect_renames() */
774 assert(target_index
== 1 || target_index
== 2);
775 other_source_index
= 3 - target_index
;
776 old_sidemask
= (1 << other_source_index
); /* 2 or 4 */
777 source_deleted
= (oldinfo
->filemask
== 1);
778 collision
= ((newinfo
->filemask
& old_sidemask
) != 0);
779 type_changed
= !source_deleted
&&
780 (S_ISREG(oldinfo
->stages
[other_source_index
].mode
) !=
781 S_ISREG(newinfo
->stages
[target_index
].mode
));
782 if (type_changed
&& collision
) {
784 * special handling so later blocks can handle this...
786 * if type_changed && collision are both true, then this
787 * was really a double rename, but one side wasn't
788 * detected due to lack of break detection. I.e.
790 * orig: has normal file 'foo'
791 * side1: renames 'foo' to 'bar', adds 'foo' symlink
792 * side2: renames 'foo' to 'bar'
793 * In this case, the foo->bar rename on side1 won't be
794 * detected because the new symlink named 'foo' is
795 * there and we don't do break detection. But we detect
796 * this here because we don't want to merge the content
797 * of the foo symlink with the foo->bar file, so we
798 * have some logic to handle this special case. The
799 * easiest way to do that is make 'bar' on side1 not
800 * be considered a colliding file but the other part
801 * of a normal rename. If the file is very different,
802 * well we're going to get content merge conflicts
803 * anyway so it doesn't hurt. And if the colliding
804 * file also has a different type, that'll be handled
805 * by the content merge logic in process_entry() too.
807 * See also t6430, 'rename vs. rename/symlink'
811 if (source_deleted
) {
812 if (target_index
== 1) {
813 rename_branch
= opt
->branch1
;
814 delete_branch
= opt
->branch2
;
816 rename_branch
= opt
->branch2
;
817 delete_branch
= opt
->branch1
;
821 assert(source_deleted
|| oldinfo
->filemask
& old_sidemask
);
823 /* Need to check for special types of rename conflicts... */
824 if (collision
&& !source_deleted
) {
825 /* collision: rename/add or rename/rename(2to1) */
826 const char *pathnames
[3];
827 struct version_info merged
;
829 struct conflict_info
*base
, *side1
, *side2
;
832 pathnames
[0] = oldpath
;
833 pathnames
[other_source_index
] = oldpath
;
834 pathnames
[target_index
] = newpath
;
836 base
= strmap_get(&opt
->priv
->paths
, pathnames
[0]);
837 side1
= strmap_get(&opt
->priv
->paths
, pathnames
[1]);
838 side2
= strmap_get(&opt
->priv
->paths
, pathnames
[2]);
844 clean
= handle_content_merge(opt
, pair
->one
->path
,
849 1 + 2 * opt
->priv
->call_depth
,
852 memcpy(&newinfo
->stages
[target_index
], &merged
,
855 path_msg(opt
, newpath
, 0,
856 _("CONFLICT (rename involved in "
857 "collision): rename of %s -> %s has "
858 "content conflicts AND collides "
859 "with another path; this may result "
860 "in nested conflict markers."),
863 } else if (collision
&& source_deleted
) {
865 * rename/add/delete or rename/rename(2to1)/delete:
866 * since oldpath was deleted on the side that didn't
867 * do the rename, there's not much of a content merge
868 * we can do for the rename. oldinfo->merged.is_null
869 * was already set, so we just leave things as-is so
870 * they look like an add/add conflict.
873 newinfo
->path_conflict
= 1;
874 path_msg(opt
, newpath
, 0,
875 _("CONFLICT (rename/delete): %s renamed "
876 "to %s in %s, but deleted in %s."),
877 oldpath
, newpath
, rename_branch
, delete_branch
);
880 * a few different cases...start by copying the
881 * existing stage(s) from oldinfo over the newinfo
882 * and update the pathname(s).
884 memcpy(&newinfo
->stages
[0], &oldinfo
->stages
[0],
885 sizeof(newinfo
->stages
[0]));
886 newinfo
->filemask
|= (1 << MERGE_BASE
);
887 newinfo
->pathnames
[0] = oldpath
;
889 /* rename vs. typechange */
890 /* Mark the original as resolved by removal */
891 memcpy(&oldinfo
->stages
[0].oid
, &null_oid
,
892 sizeof(oldinfo
->stages
[0].oid
));
893 oldinfo
->stages
[0].mode
= 0;
894 oldinfo
->filemask
&= 0x06;
895 } else if (source_deleted
) {
897 newinfo
->path_conflict
= 1;
898 path_msg(opt
, newpath
, 0,
899 _("CONFLICT (rename/delete): %s renamed"
900 " to %s in %s, but deleted in %s."),
902 rename_branch
, delete_branch
);
905 memcpy(&newinfo
->stages
[other_source_index
],
906 &oldinfo
->stages
[other_source_index
],
907 sizeof(newinfo
->stages
[0]));
908 newinfo
->filemask
|= (1 << other_source_index
);
909 newinfo
->pathnames
[other_source_index
] = oldpath
;
914 /* Mark the original as resolved by removal */
915 oldinfo
->merged
.is_null
= 1;
916 oldinfo
->merged
.clean
= 1;
924 static int compare_pairs(const void *a_
, const void *b_
)
926 const struct diff_filepair
*a
= *((const struct diff_filepair
**)a_
);
927 const struct diff_filepair
*b
= *((const struct diff_filepair
**)b_
);
929 return strcmp(a
->one
->path
, b
->one
->path
);
932 /* Call diffcore_rename() to compute which files have changed on given side */
933 static void detect_regular_renames(struct merge_options
*opt
,
934 struct tree
*merge_base
,
938 struct diff_options diff_opts
;
939 struct rename_info
*renames
= &opt
->priv
->renames
;
941 repo_diff_setup(opt
->repo
, &diff_opts
);
942 diff_opts
.flags
.recursive
= 1;
943 diff_opts
.flags
.rename_empty
= 0;
944 diff_opts
.detect_rename
= DIFF_DETECT_RENAME
;
945 diff_opts
.rename_limit
= opt
->rename_limit
;
946 if (opt
->rename_limit
<= 0)
947 diff_opts
.rename_limit
= 1000;
948 diff_opts
.rename_score
= opt
->rename_score
;
949 diff_opts
.show_rename_progress
= opt
->show_rename_progress
;
950 diff_opts
.output_format
= DIFF_FORMAT_NO_OUTPUT
;
951 diff_setup_done(&diff_opts
);
952 diff_tree_oid(&merge_base
->object
.oid
, &side
->object
.oid
, "",
954 diffcore_std(&diff_opts
);
956 if (diff_opts
.needed_rename_limit
> renames
->needed_limit
)
957 renames
->needed_limit
= diff_opts
.needed_rename_limit
;
959 renames
->pairs
[side_index
] = diff_queued_diff
;
961 diff_opts
.output_format
= DIFF_FORMAT_NO_OUTPUT
;
962 diff_queued_diff
.nr
= 0;
963 diff_queued_diff
.queue
= NULL
;
964 diff_flush(&diff_opts
);
968 * Get information of all renames which occurred in 'side_pairs', discarding
971 static int collect_renames(struct merge_options
*opt
,
972 struct diff_queue_struct
*result
,
976 struct diff_queue_struct
*side_pairs
;
977 struct rename_info
*renames
= &opt
->priv
->renames
;
979 side_pairs
= &renames
->pairs
[side_index
];
981 for (i
= 0; i
< side_pairs
->nr
; ++i
) {
982 struct diff_filepair
*p
= side_pairs
->queue
[i
];
984 if (p
->status
!= 'R') {
985 diff_free_filepair(p
);
990 * p->score comes back from diffcore_rename_extended() with
991 * the similarity of the renamed file. The similarity is
992 * was used to determine that the two files were related
993 * and are a rename, which we have already used, but beyond
994 * that we have no use for the similarity. So p->score is
995 * now irrelevant. However, process_renames() will need to
996 * know which side of the merge this rename was associated
997 * with, so overwrite p->score with that value.
999 p
->score
= side_index
;
1000 result
->queue
[result
->nr
++] = p
;
1006 static int detect_and_process_renames(struct merge_options
*opt
,
1007 struct tree
*merge_base
,
1011 struct diff_queue_struct combined
;
1012 struct rename_info
*renames
= &opt
->priv
->renames
;
1015 memset(&combined
, 0, sizeof(combined
));
1017 detect_regular_renames(opt
, merge_base
, side1
, MERGE_SIDE1
);
1018 detect_regular_renames(opt
, merge_base
, side2
, MERGE_SIDE2
);
1020 ALLOC_GROW(combined
.queue
,
1021 renames
->pairs
[1].nr
+ renames
->pairs
[2].nr
,
1023 clean
&= collect_renames(opt
, &combined
, MERGE_SIDE1
);
1024 clean
&= collect_renames(opt
, &combined
, MERGE_SIDE2
);
1025 QSORT(combined
.queue
, combined
.nr
, compare_pairs
);
1027 clean
&= process_renames(opt
, &combined
);
1029 /* Free memory for renames->pairs[] and combined */
1030 for (s
= MERGE_SIDE1
; s
<= MERGE_SIDE2
; s
++) {
1031 free(renames
->pairs
[s
].queue
);
1032 DIFF_QUEUE_CLEAR(&renames
->pairs
[s
]);
1036 for (i
= 0; i
< combined
.nr
; i
++)
1037 diff_free_filepair(combined
.queue
[i
]);
1038 free(combined
.queue
);
1044 /*** Function Grouping: functions related to process_entries() ***/
1046 static int string_list_df_name_compare(const char *one
, const char *two
)
1048 int onelen
= strlen(one
);
1049 int twolen
= strlen(two
);
1051 * Here we only care that entries for D/F conflicts are
1052 * adjacent, in particular with the file of the D/F conflict
1053 * appearing before files below the corresponding directory.
1054 * The order of the rest of the list is irrelevant for us.
1056 * To achieve this, we sort with df_name_compare and provide
1057 * the mode S_IFDIR so that D/F conflicts will sort correctly.
1058 * We use the mode S_IFDIR for everything else for simplicity,
1059 * since in other cases any changes in their order due to
1060 * sorting cause no problems for us.
1062 int cmp
= df_name_compare(one
, onelen
, S_IFDIR
,
1063 two
, twolen
, S_IFDIR
);
1065 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
1066 * that 'foo' comes before 'foo/bar'.
1070 return onelen
- twolen
;
1073 struct directory_versions
{
1075 * versions: list of (basename -> version_info)
1077 * The basenames are in reverse lexicographic order of full pathnames,
1078 * as processed in process_entries(). This puts all entries within
1079 * a directory together, and covers the directory itself after
1080 * everything within it, allowing us to write subtrees before needing
1081 * to record information for the tree itself.
1083 struct string_list versions
;
1086 * offsets: list of (full relative path directories -> integer offsets)
1088 * Since versions contains basenames from files in multiple different
1089 * directories, we need to know which entries in versions correspond
1090 * to which directories. Values of e.g.
1094 * Would mean that entries 0-1 of versions are files in the toplevel
1095 * directory, entries 2-4 are files under src/, and the remaining
1096 * entries starting at index 5 are files under src/moduleA/.
1098 struct string_list offsets
;
1101 * last_directory: directory that previously processed file found in
1103 * last_directory starts NULL, but records the directory in which the
1104 * previous file was found within. As soon as
1105 * directory(current_file) != last_directory
1106 * then we need to start updating accounting in versions & offsets.
1107 * Note that last_directory is always the last path in "offsets" (or
1108 * NULL if "offsets" is empty) so this exists just for quick access.
1110 const char *last_directory
;
1112 /* last_directory_len: cached computation of strlen(last_directory) */
1113 unsigned last_directory_len
;
1116 static int tree_entry_order(const void *a_
, const void *b_
)
1118 const struct string_list_item
*a
= a_
;
1119 const struct string_list_item
*b
= b_
;
1121 const struct merged_info
*ami
= a
->util
;
1122 const struct merged_info
*bmi
= b
->util
;
1123 return base_name_compare(a
->string
, strlen(a
->string
), ami
->result
.mode
,
1124 b
->string
, strlen(b
->string
), bmi
->result
.mode
);
1127 static void write_tree(struct object_id
*result_oid
,
1128 struct string_list
*versions
,
1129 unsigned int offset
,
1132 size_t maxlen
= 0, extra
;
1133 unsigned int nr
= versions
->nr
- offset
;
1134 struct strbuf buf
= STRBUF_INIT
;
1135 struct string_list relevant_entries
= STRING_LIST_INIT_NODUP
;
1139 * We want to sort the last (versions->nr-offset) entries in versions.
1140 * Do so by abusing the string_list API a bit: make another string_list
1141 * that contains just those entries and then sort them.
1143 * We won't use relevant_entries again and will let it just pop off the
1144 * stack, so there won't be allocation worries or anything.
1146 relevant_entries
.items
= versions
->items
+ offset
;
1147 relevant_entries
.nr
= versions
->nr
- offset
;
1148 QSORT(relevant_entries
.items
, relevant_entries
.nr
, tree_entry_order
);
1150 /* Pre-allocate some space in buf */
1151 extra
= hash_size
+ 8; /* 8: 6 for mode, 1 for space, 1 for NUL char */
1152 for (i
= 0; i
< nr
; i
++) {
1153 maxlen
+= strlen(versions
->items
[offset
+i
].string
) + extra
;
1155 strbuf_grow(&buf
, maxlen
);
1157 /* Write each entry out to buf */
1158 for (i
= 0; i
< nr
; i
++) {
1159 struct merged_info
*mi
= versions
->items
[offset
+i
].util
;
1160 struct version_info
*ri
= &mi
->result
;
1161 strbuf_addf(&buf
, "%o %s%c",
1163 versions
->items
[offset
+i
].string
, '\0');
1164 strbuf_add(&buf
, ri
->oid
.hash
, hash_size
);
1167 /* Write this object file out, and record in result_oid */
1168 write_object_file(buf
.buf
, buf
.len
, tree_type
, result_oid
);
1169 strbuf_release(&buf
);
1172 static void record_entry_for_tree(struct directory_versions
*dir_metadata
,
1174 struct merged_info
*mi
)
1176 const char *basename
;
1179 /* nothing to record */
1182 basename
= path
+ mi
->basename_offset
;
1183 assert(strchr(basename
, '/') == NULL
);
1184 string_list_append(&dir_metadata
->versions
,
1185 basename
)->util
= &mi
->result
;
1188 static void write_completed_directory(struct merge_options
*opt
,
1189 const char *new_directory_name
,
1190 struct directory_versions
*info
)
1192 const char *prev_dir
;
1193 struct merged_info
*dir_info
= NULL
;
1194 unsigned int offset
;
1197 * Some explanation of info->versions and info->offsets...
1199 * process_entries() iterates over all relevant files AND
1200 * directories in reverse lexicographic order, and calls this
1201 * function. Thus, an example of the paths that process_entries()
1202 * could operate on (along with the directories for those paths
1207 * src/moduleB/umm.c src/moduleB
1208 * src/moduleB/stuff.h src/moduleB
1209 * src/moduleB/baz.c src/moduleB
1211 * src/moduleA/foo.c src/moduleA
1212 * src/moduleA/bar.c src/moduleA
1219 * always contains the unprocessed entries and their
1220 * version_info information. For example, after the first five
1221 * entries above, info->versions would be:
1223 * xtract.c <xtract.c's version_info>
1224 * token.txt <token.txt's version_info>
1225 * umm.c <src/moduleB/umm.c's version_info>
1226 * stuff.h <src/moduleB/stuff.h's version_info>
1227 * baz.c <src/moduleB/baz.c's version_info>
1229 * Once a subdirectory is completed we remove the entries in
1230 * that subdirectory from info->versions, writing it as a tree
1231 * (write_tree()). Thus, as soon as we get to src/moduleB,
1232 * info->versions would be updated to
1234 * xtract.c <xtract.c's version_info>
1235 * token.txt <token.txt's version_info>
1236 * moduleB <src/moduleB's version_info>
1240 * helps us track which entries in info->versions correspond to
1241 * which directories. When we are N directories deep (e.g. 4
1242 * for src/modA/submod/subdir/), we have up to N+1 unprocessed
1243 * directories (+1 because of toplevel dir). Corresponding to
1244 * the info->versions example above, after processing five entries
1245 * info->offsets will be:
1250 * which is used to know that xtract.c & token.txt are from the
1251 * toplevel dirctory, while umm.c & stuff.h & baz.c are from the
1252 * src/moduleB directory. Again, following the example above,
1253 * once we need to process src/moduleB, then info->offsets is
1259 * which says that moduleB (and only moduleB so far) is in the
1262 * One unique thing to note about info->offsets here is that
1263 * "src" was not added to info->offsets until there was a path
1264 * (a file OR directory) immediately below src/ that got
1267 * Since process_entry() just appends new entries to info->versions,
1268 * write_completed_directory() only needs to do work if the next path
1269 * is in a directory that is different than the last directory found
1274 * If we are working with the same directory as the last entry, there
1275 * is no work to do. (See comments above the directory_name member of
1276 * struct merged_info for why we can use pointer comparison instead of
1279 if (new_directory_name
== info
->last_directory
)
1283 * If we are just starting (last_directory is NULL), or last_directory
1284 * is a prefix of the current directory, then we can just update
1285 * info->offsets to record the offset where we started this directory
1286 * and update last_directory to have quick access to it.
1288 if (info
->last_directory
== NULL
||
1289 !strncmp(new_directory_name
, info
->last_directory
,
1290 info
->last_directory_len
)) {
1291 uintptr_t offset
= info
->versions
.nr
;
1293 info
->last_directory
= new_directory_name
;
1294 info
->last_directory_len
= strlen(info
->last_directory
);
1296 * Record the offset into info->versions where we will
1297 * start recording basenames of paths found within
1298 * new_directory_name.
1300 string_list_append(&info
->offsets
,
1301 info
->last_directory
)->util
= (void*)offset
;
1306 * The next entry that will be processed will be within
1307 * new_directory_name. Since at this point we know that
1308 * new_directory_name is within a different directory than
1309 * info->last_directory, we have all entries for info->last_directory
1310 * in info->versions and we need to create a tree object for them.
1312 dir_info
= strmap_get(&opt
->priv
->paths
, info
->last_directory
);
1314 offset
= (uintptr_t)info
->offsets
.items
[info
->offsets
.nr
-1].util
;
1315 if (offset
== info
->versions
.nr
) {
1317 * Actually, we don't need to create a tree object in this
1318 * case. Whenever all files within a directory disappear
1319 * during the merge (e.g. unmodified on one side and
1320 * deleted on the other, or files were renamed elsewhere),
1321 * then we get here and the directory itself needs to be
1322 * omitted from its parent tree as well.
1324 dir_info
->is_null
= 1;
1327 * Write out the tree to the git object directory, and also
1328 * record the mode and oid in dir_info->result.
1330 dir_info
->is_null
= 0;
1331 dir_info
->result
.mode
= S_IFDIR
;
1332 write_tree(&dir_info
->result
.oid
, &info
->versions
, offset
,
1333 opt
->repo
->hash_algo
->rawsz
);
1337 * We've now used several entries from info->versions and one entry
1338 * from info->offsets, so we get rid of those values.
1341 info
->versions
.nr
= offset
;
1344 * Now we've taken care of the completed directory, but we need to
1345 * prepare things since future entries will be in
1346 * new_directory_name. (In particular, process_entry() will be
1347 * appending new entries to info->versions.) So, we need to make
1348 * sure new_directory_name is the last entry in info->offsets.
1350 prev_dir
= info
->offsets
.nr
== 0 ? NULL
:
1351 info
->offsets
.items
[info
->offsets
.nr
-1].string
;
1352 if (new_directory_name
!= prev_dir
) {
1353 uintptr_t c
= info
->versions
.nr
;
1354 string_list_append(&info
->offsets
,
1355 new_directory_name
)->util
= (void*)c
;
1358 /* And, of course, we need to update last_directory to match. */
1359 info
->last_directory
= new_directory_name
;
1360 info
->last_directory_len
= strlen(info
->last_directory
);
1363 /* Per entry merge function */
1364 static void process_entry(struct merge_options
*opt
,
1366 struct conflict_info
*ci
,
1367 struct directory_versions
*dir_metadata
)
1370 assert(ci
->filemask
>= 0 && ci
->filemask
<= 7);
1371 /* ci->match_mask == 7 was handled in collect_merge_info_callback() */
1372 assert(ci
->match_mask
== 0 || ci
->match_mask
== 3 ||
1373 ci
->match_mask
== 5 || ci
->match_mask
== 6);
1376 record_entry_for_tree(dir_metadata
, path
, &ci
->merged
);
1377 if (ci
->filemask
== 0)
1378 /* nothing else to handle */
1380 assert(ci
->df_conflict
);
1383 if (ci
->df_conflict
) {
1384 die("Not yet implemented.");
1388 * NOTE: Below there is a long switch-like if-elseif-elseif... block
1389 * which the code goes through even for the df_conflict cases
1390 * above. Well, it will once we don't die-not-implemented above.
1392 if (ci
->match_mask
) {
1393 ci
->merged
.clean
= 1;
1394 if (ci
->match_mask
== 6) {
1395 /* stages[1] == stages[2] */
1396 ci
->merged
.result
.mode
= ci
->stages
[1].mode
;
1397 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[1].oid
);
1399 /* determine the mask of the side that didn't match */
1400 unsigned int othermask
= 7 & ~ci
->match_mask
;
1401 int side
= (othermask
== 4) ? 2 : 1;
1403 ci
->merged
.result
.mode
= ci
->stages
[side
].mode
;
1404 ci
->merged
.is_null
= !ci
->merged
.result
.mode
;
1405 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[side
].oid
);
1407 assert(othermask
== 2 || othermask
== 4);
1408 assert(ci
->merged
.is_null
==
1409 (ci
->filemask
== ci
->match_mask
));
1411 } else if (ci
->filemask
>= 6 &&
1412 (S_IFMT
& ci
->stages
[1].mode
) !=
1413 (S_IFMT
& ci
->stages
[2].mode
)) {
1415 * Two different items from (file/submodule/symlink)
1417 die("Not yet implemented.");
1418 } else if (ci
->filemask
>= 6) {
1420 * TODO: Needs a two-way or three-way content merge, but we're
1421 * just being lazy and copying the version from HEAD and
1422 * leaving it as conflicted.
1424 ci
->merged
.clean
= 0;
1425 ci
->merged
.result
.mode
= ci
->stages
[1].mode
;
1426 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[1].oid
);
1427 /* When we fix above, we'll call handle_content_merge() */
1428 (void)handle_content_merge
;
1429 } else if (ci
->filemask
== 3 || ci
->filemask
== 5) {
1431 const char *modify_branch
, *delete_branch
;
1432 int side
= (ci
->filemask
== 5) ? 2 : 1;
1433 int index
= opt
->priv
->call_depth
? 0 : side
;
1435 ci
->merged
.result
.mode
= ci
->stages
[index
].mode
;
1436 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[index
].oid
);
1437 ci
->merged
.clean
= 0;
1439 modify_branch
= (side
== 1) ? opt
->branch1
: opt
->branch2
;
1440 delete_branch
= (side
== 1) ? opt
->branch2
: opt
->branch1
;
1442 if (ci
->path_conflict
&&
1443 oideq(&ci
->stages
[0].oid
, &ci
->stages
[side
].oid
)) {
1445 * This came from a rename/delete; no action to take,
1446 * but avoid printing "modify/delete" conflict notice
1447 * since the contents were not modified.
1450 path_msg(opt
, path
, 0,
1451 _("CONFLICT (modify/delete): %s deleted in %s "
1452 "and modified in %s. Version %s of %s left "
1454 path
, delete_branch
, modify_branch
,
1455 modify_branch
, path
);
1457 } else if (ci
->filemask
== 2 || ci
->filemask
== 4) {
1458 /* Added on one side */
1459 int side
= (ci
->filemask
== 4) ? 2 : 1;
1460 ci
->merged
.result
.mode
= ci
->stages
[side
].mode
;
1461 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[side
].oid
);
1462 ci
->merged
.clean
= !ci
->df_conflict
&& !ci
->path_conflict
;
1463 } else if (ci
->filemask
== 1) {
1464 /* Deleted on both sides */
1465 ci
->merged
.is_null
= 1;
1466 ci
->merged
.result
.mode
= 0;
1467 oidcpy(&ci
->merged
.result
.oid
, &null_oid
);
1468 ci
->merged
.clean
= !ci
->path_conflict
;
1472 * If still conflicted, record it separately. This allows us to later
1473 * iterate over just conflicted entries when updating the index instead
1474 * of iterating over all entries.
1476 if (!ci
->merged
.clean
)
1477 strmap_put(&opt
->priv
->conflicted
, path
, ci
);
1478 record_entry_for_tree(dir_metadata
, path
, &ci
->merged
);
1481 static void process_entries(struct merge_options
*opt
,
1482 struct object_id
*result_oid
)
1484 struct hashmap_iter iter
;
1485 struct strmap_entry
*e
;
1486 struct string_list plist
= STRING_LIST_INIT_NODUP
;
1487 struct string_list_item
*entry
;
1488 struct directory_versions dir_metadata
= { STRING_LIST_INIT_NODUP
,
1489 STRING_LIST_INIT_NODUP
,
1492 if (strmap_empty(&opt
->priv
->paths
)) {
1493 oidcpy(result_oid
, opt
->repo
->hash_algo
->empty_tree
);
1497 /* Hack to pre-allocate plist to the desired size */
1498 ALLOC_GROW(plist
.items
, strmap_get_size(&opt
->priv
->paths
), plist
.alloc
);
1500 /* Put every entry from paths into plist, then sort */
1501 strmap_for_each_entry(&opt
->priv
->paths
, &iter
, e
) {
1502 string_list_append(&plist
, e
->key
)->util
= e
->value
;
1504 plist
.cmp
= string_list_df_name_compare
;
1505 string_list_sort(&plist
);
1508 * Iterate over the items in reverse order, so we can handle paths
1509 * below a directory before needing to handle the directory itself.
1511 * This allows us to write subtrees before we need to write trees,
1512 * and it also enables sane handling of directory/file conflicts
1513 * (because it allows us to know whether the directory is still in
1514 * the way when it is time to process the file at the same path).
1516 for (entry
= &plist
.items
[plist
.nr
-1]; entry
>= plist
.items
; --entry
) {
1517 char *path
= entry
->string
;
1519 * NOTE: mi may actually be a pointer to a conflict_info, but
1520 * we have to check mi->clean first to see if it's safe to
1521 * reassign to such a pointer type.
1523 struct merged_info
*mi
= entry
->util
;
1525 write_completed_directory(opt
, mi
->directory_name
,
1528 record_entry_for_tree(&dir_metadata
, path
, mi
);
1530 struct conflict_info
*ci
= (struct conflict_info
*)mi
;
1531 process_entry(opt
, path
, ci
, &dir_metadata
);
1535 if (dir_metadata
.offsets
.nr
!= 1 ||
1536 (uintptr_t)dir_metadata
.offsets
.items
[0].util
!= 0) {
1537 printf("dir_metadata.offsets.nr = %d (should be 1)\n",
1538 dir_metadata
.offsets
.nr
);
1539 printf("dir_metadata.offsets.items[0].util = %u (should be 0)\n",
1540 (unsigned)(uintptr_t)dir_metadata
.offsets
.items
[0].util
);
1542 BUG("dir_metadata accounting completely off; shouldn't happen");
1544 write_tree(result_oid
, &dir_metadata
.versions
, 0,
1545 opt
->repo
->hash_algo
->rawsz
);
1546 string_list_clear(&plist
, 0);
1547 string_list_clear(&dir_metadata
.versions
, 0);
1548 string_list_clear(&dir_metadata
.offsets
, 0);
1551 /*** Function Grouping: functions related to merge_switch_to_result() ***/
1553 static int checkout(struct merge_options
*opt
,
1557 /* Switch the index/working copy from old to new */
1559 struct tree_desc trees
[2];
1560 struct unpack_trees_options unpack_opts
;
1562 memset(&unpack_opts
, 0, sizeof(unpack_opts
));
1563 unpack_opts
.head_idx
= -1;
1564 unpack_opts
.src_index
= opt
->repo
->index
;
1565 unpack_opts
.dst_index
= opt
->repo
->index
;
1567 setup_unpack_trees_porcelain(&unpack_opts
, "merge");
1570 * NOTE: if this were just "git checkout" code, we would probably
1571 * read or refresh the cache and check for a conflicted index, but
1572 * builtin/merge.c or sequencer.c really needs to read the index
1573 * and check for conflicted entries before starting merging for a
1574 * good user experience (no sense waiting for merges/rebases before
1575 * erroring out), so there's no reason to duplicate that work here.
1578 /* 2-way merge to the new branch */
1579 unpack_opts
.update
= 1;
1580 unpack_opts
.merge
= 1;
1581 unpack_opts
.quiet
= 0; /* FIXME: sequencer might want quiet? */
1582 unpack_opts
.verbose_update
= (opt
->verbosity
> 2);
1583 unpack_opts
.fn
= twoway_merge
;
1584 if (1/* FIXME: opts->overwrite_ignore*/) {
1585 unpack_opts
.dir
= xcalloc(1, sizeof(*unpack_opts
.dir
));
1586 unpack_opts
.dir
->flags
|= DIR_SHOW_IGNORED
;
1587 setup_standard_excludes(unpack_opts
.dir
);
1590 init_tree_desc(&trees
[0], prev
->buffer
, prev
->size
);
1592 init_tree_desc(&trees
[1], next
->buffer
, next
->size
);
1594 ret
= unpack_trees(2, trees
, &unpack_opts
);
1595 clear_unpack_trees_porcelain(&unpack_opts
);
1596 dir_clear(unpack_opts
.dir
);
1597 FREE_AND_NULL(unpack_opts
.dir
);
1601 static int record_conflicted_index_entries(struct merge_options
*opt
,
1602 struct index_state
*index
,
1603 struct strmap
*paths
,
1604 struct strmap
*conflicted
)
1606 struct hashmap_iter iter
;
1607 struct strmap_entry
*e
;
1609 int original_cache_nr
;
1611 if (strmap_empty(conflicted
))
1614 original_cache_nr
= index
->cache_nr
;
1616 /* Put every entry from paths into plist, then sort */
1617 strmap_for_each_entry(conflicted
, &iter
, e
) {
1618 const char *path
= e
->key
;
1619 struct conflict_info
*ci
= e
->value
;
1621 struct cache_entry
*ce
;
1627 * The index will already have a stage=0 entry for this path,
1628 * because we created an as-merged-as-possible version of the
1629 * file and checkout() moved the working copy and index over
1632 * However, previous iterations through this loop will have
1633 * added unstaged entries to the end of the cache which
1634 * ignore the standard alphabetical ordering of cache
1635 * entries and break invariants needed for index_name_pos()
1636 * to work. However, we know the entry we want is before
1637 * those appended cache entries, so do a temporary swap on
1638 * cache_nr to only look through entries of interest.
1640 SWAP(index
->cache_nr
, original_cache_nr
);
1641 pos
= index_name_pos(index
, path
, strlen(path
));
1642 SWAP(index
->cache_nr
, original_cache_nr
);
1644 if (ci
->filemask
!= 1)
1645 BUG("Conflicted %s but nothing in basic working tree or index; this shouldn't happen", path
);
1646 cache_tree_invalidate_path(index
, path
);
1648 ce
= index
->cache
[pos
];
1651 * Clean paths with CE_SKIP_WORKTREE set will not be
1652 * written to the working tree by the unpack_trees()
1653 * call in checkout(). Our conflicted entries would
1654 * have appeared clean to that code since we ignored
1655 * the higher order stages. Thus, we need override
1656 * the CE_SKIP_WORKTREE bit and manually write those
1657 * files to the working disk here.
1659 * TODO: Implement this CE_SKIP_WORKTREE fixup.
1663 * Mark this cache entry for removal and instead add
1664 * new stage>0 entries corresponding to the
1665 * conflicts. If there are many conflicted entries, we
1666 * want to avoid memmove'ing O(NM) entries by
1667 * inserting the new entries one at a time. So,
1668 * instead, we just add the new cache entries to the
1669 * end (ignoring normal index requirements on sort
1670 * order) and sort the index once we're all done.
1672 ce
->ce_flags
|= CE_REMOVE
;
1675 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
1676 struct version_info
*vi
;
1677 if (!(ci
->filemask
& (1ul << i
)))
1679 vi
= &ci
->stages
[i
];
1680 ce
= make_cache_entry(index
, vi
->mode
, &vi
->oid
,
1682 add_index_entry(index
, ce
, ADD_CACHE_JUST_APPEND
);
1687 * Remove the unused cache entries (and invalidate the relevant
1688 * cache-trees), then sort the index entries to get the conflicted
1689 * entries we added to the end into their right locations.
1691 remove_marked_cache_entries(index
, 1);
1692 QSORT(index
->cache
, index
->cache_nr
, cmp_cache_name_compare
);
1697 void merge_switch_to_result(struct merge_options
*opt
,
1699 struct merge_result
*result
,
1700 int update_worktree_and_index
,
1701 int display_update_msgs
)
1703 assert(opt
->priv
== NULL
);
1704 if (result
->clean
>= 0 && update_worktree_and_index
) {
1705 struct merge_options_internal
*opti
= result
->priv
;
1707 if (checkout(opt
, head
, result
->tree
)) {
1708 /* failure to function */
1713 if (record_conflicted_index_entries(opt
, opt
->repo
->index
,
1715 &opti
->conflicted
)) {
1716 /* failure to function */
1722 if (display_update_msgs
) {
1723 struct merge_options_internal
*opti
= result
->priv
;
1724 struct hashmap_iter iter
;
1725 struct strmap_entry
*e
;
1726 struct string_list olist
= STRING_LIST_INIT_NODUP
;
1729 /* Hack to pre-allocate olist to the desired size */
1730 ALLOC_GROW(olist
.items
, strmap_get_size(&opti
->output
),
1733 /* Put every entry from output into olist, then sort */
1734 strmap_for_each_entry(&opti
->output
, &iter
, e
) {
1735 string_list_append(&olist
, e
->key
)->util
= e
->value
;
1737 string_list_sort(&olist
);
1739 /* Iterate over the items, printing them */
1740 for (i
= 0; i
< olist
.nr
; ++i
) {
1741 struct strbuf
*sb
= olist
.items
[i
].util
;
1743 printf("%s", sb
->buf
);
1745 string_list_clear(&olist
, 0);
1747 /* Also include needed rename limit adjustment now */
1748 diff_warn_rename_limit("merge.renamelimit",
1749 opti
->renames
.needed_limit
, 0);
1752 merge_finalize(opt
, result
);
1755 void merge_finalize(struct merge_options
*opt
,
1756 struct merge_result
*result
)
1758 struct merge_options_internal
*opti
= result
->priv
;
1760 assert(opt
->priv
== NULL
);
1762 clear_or_reinit_internal_opts(opti
, 0);
1763 FREE_AND_NULL(opti
);
1766 /*** Function Grouping: helper functions for merge_incore_*() ***/
1768 static inline void set_commit_tree(struct commit
*c
, struct tree
*t
)
1773 static struct commit
*make_virtual_commit(struct repository
*repo
,
1775 const char *comment
)
1777 struct commit
*commit
= alloc_commit_node(repo
);
1779 set_merge_remote_desc(commit
, comment
, (struct object
*)commit
);
1780 set_commit_tree(commit
, tree
);
1781 commit
->object
.parsed
= 1;
1785 static void merge_start(struct merge_options
*opt
, struct merge_result
*result
)
1787 /* Sanity checks on opt */
1790 assert(opt
->branch1
&& opt
->branch2
);
1792 assert(opt
->detect_directory_renames
>= MERGE_DIRECTORY_RENAMES_NONE
&&
1793 opt
->detect_directory_renames
<= MERGE_DIRECTORY_RENAMES_TRUE
);
1794 assert(opt
->rename_limit
>= -1);
1795 assert(opt
->rename_score
>= 0 && opt
->rename_score
<= MAX_SCORE
);
1796 assert(opt
->show_rename_progress
>= 0 && opt
->show_rename_progress
<= 1);
1798 assert(opt
->xdl_opts
>= 0);
1799 assert(opt
->recursive_variant
>= MERGE_VARIANT_NORMAL
&&
1800 opt
->recursive_variant
<= MERGE_VARIANT_THEIRS
);
1803 * detect_renames, verbosity, buffer_output, and obuf are ignored
1804 * fields that were used by "recursive" rather than "ort" -- but
1805 * sanity check them anyway.
1807 assert(opt
->detect_renames
>= -1 &&
1808 opt
->detect_renames
<= DIFF_DETECT_COPY
);
1809 assert(opt
->verbosity
>= 0 && opt
->verbosity
<= 5);
1810 assert(opt
->buffer_output
<= 2);
1811 assert(opt
->obuf
.len
== 0);
1813 assert(opt
->priv
== NULL
);
1815 /* Default to histogram diff. Actually, just hardcode it...for now. */
1816 opt
->xdl_opts
= DIFF_WITH_ALG(opt
, HISTOGRAM_DIFF
);
1818 /* Initialization of opt->priv, our internal merge data */
1819 opt
->priv
= xcalloc(1, sizeof(*opt
->priv
));
1822 * Although we initialize opt->priv->paths with strdup_strings=0,
1823 * that's just to avoid making yet another copy of an allocated
1824 * string. Putting the entry into paths means we are taking
1825 * ownership, so we will later free it. paths_to_free is similar.
1827 * In contrast, conflicted just has a subset of keys from paths, so
1828 * we don't want to free those (it'd be a duplicate free).
1830 strmap_init_with_options(&opt
->priv
->paths
, NULL
, 0);
1831 strmap_init_with_options(&opt
->priv
->conflicted
, NULL
, 0);
1832 string_list_init(&opt
->priv
->paths_to_free
, 0);
1835 * keys & strbufs in output will sometimes need to outlive "paths",
1836 * so it will have a copy of relevant keys. It's probably a small
1837 * subset of the overall paths that have special output.
1839 strmap_init(&opt
->priv
->output
);
1842 /*** Function Grouping: merge_incore_*() and their internal variants ***/
1845 * Originally from merge_trees_internal(); heavily adapted, though.
1847 static void merge_ort_nonrecursive_internal(struct merge_options
*opt
,
1848 struct tree
*merge_base
,
1851 struct merge_result
*result
)
1853 struct object_id working_tree_oid
;
1855 if (collect_merge_info(opt
, merge_base
, side1
, side2
) != 0) {
1857 * TRANSLATORS: The %s arguments are: 1) tree hash of a merge
1858 * base, and 2-3) the trees for the two trees we're merging.
1860 err(opt
, _("collecting merge info failed for trees %s, %s, %s"),
1861 oid_to_hex(&merge_base
->object
.oid
),
1862 oid_to_hex(&side1
->object
.oid
),
1863 oid_to_hex(&side2
->object
.oid
));
1868 result
->clean
= detect_and_process_renames(opt
, merge_base
,
1870 process_entries(opt
, &working_tree_oid
);
1872 /* Set return values */
1873 result
->tree
= parse_tree_indirect(&working_tree_oid
);
1874 /* existence of conflicted entries implies unclean */
1875 result
->clean
&= strmap_empty(&opt
->priv
->conflicted
);
1876 if (!opt
->priv
->call_depth
) {
1877 result
->priv
= opt
->priv
;
1883 * Originally from merge_recursive_internal(); somewhat adapted, though.
1885 static void merge_ort_internal(struct merge_options
*opt
,
1886 struct commit_list
*merge_bases
,
1889 struct merge_result
*result
)
1891 struct commit_list
*iter
;
1892 struct commit
*merged_merge_bases
;
1893 const char *ancestor_name
;
1894 struct strbuf merge_base_abbrev
= STRBUF_INIT
;
1897 merge_bases
= get_merge_bases(h1
, h2
);
1898 /* See merge-ort.h:merge_incore_recursive() declaration NOTE */
1899 merge_bases
= reverse_commit_list(merge_bases
);
1902 merged_merge_bases
= pop_commit(&merge_bases
);
1903 if (merged_merge_bases
== NULL
) {
1904 /* if there is no common ancestor, use an empty tree */
1907 tree
= lookup_tree(opt
->repo
, opt
->repo
->hash_algo
->empty_tree
);
1908 merged_merge_bases
= make_virtual_commit(opt
->repo
, tree
,
1910 ancestor_name
= "empty tree";
1911 } else if (merge_bases
) {
1912 ancestor_name
= "merged common ancestors";
1914 strbuf_add_unique_abbrev(&merge_base_abbrev
,
1915 &merged_merge_bases
->object
.oid
,
1917 ancestor_name
= merge_base_abbrev
.buf
;
1920 for (iter
= merge_bases
; iter
; iter
= iter
->next
) {
1921 const char *saved_b1
, *saved_b2
;
1922 struct commit
*prev
= merged_merge_bases
;
1924 opt
->priv
->call_depth
++;
1926 * When the merge fails, the result contains files
1927 * with conflict markers. The cleanness flag is
1928 * ignored (unless indicating an error), it was never
1929 * actually used, as result of merge_trees has always
1930 * overwritten it: the committed "conflicts" were
1933 saved_b1
= opt
->branch1
;
1934 saved_b2
= opt
->branch2
;
1935 opt
->branch1
= "Temporary merge branch 1";
1936 opt
->branch2
= "Temporary merge branch 2";
1937 merge_ort_internal(opt
, NULL
, prev
, iter
->item
, result
);
1938 if (result
->clean
< 0)
1940 opt
->branch1
= saved_b1
;
1941 opt
->branch2
= saved_b2
;
1942 opt
->priv
->call_depth
--;
1944 merged_merge_bases
= make_virtual_commit(opt
->repo
,
1947 commit_list_insert(prev
, &merged_merge_bases
->parents
);
1948 commit_list_insert(iter
->item
,
1949 &merged_merge_bases
->parents
->next
);
1951 clear_or_reinit_internal_opts(opt
->priv
, 1);
1954 opt
->ancestor
= ancestor_name
;
1955 merge_ort_nonrecursive_internal(opt
,
1956 repo_get_commit_tree(opt
->repo
,
1957 merged_merge_bases
),
1958 repo_get_commit_tree(opt
->repo
, h1
),
1959 repo_get_commit_tree(opt
->repo
, h2
),
1961 strbuf_release(&merge_base_abbrev
);
1962 opt
->ancestor
= NULL
; /* avoid accidental re-use of opt->ancestor */
1965 void merge_incore_nonrecursive(struct merge_options
*opt
,
1966 struct tree
*merge_base
,
1969 struct merge_result
*result
)
1971 assert(opt
->ancestor
!= NULL
);
1972 merge_start(opt
, result
);
1973 merge_ort_nonrecursive_internal(opt
, merge_base
, side1
, side2
, result
);
1976 void merge_incore_recursive(struct merge_options
*opt
,
1977 struct commit_list
*merge_bases
,
1978 struct commit
*side1
,
1979 struct commit
*side2
,
1980 struct merge_result
*result
)
1982 /* We set the ancestor label based on the merge_bases */
1983 assert(opt
->ancestor
== NULL
);
1985 merge_start(opt
, result
);
1986 merge_ort_internal(opt
, merge_bases
, side1
, side2
, result
);