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"
21 #include "cache-tree.h"
22 #include "commit-reach.h"
27 #include "object-store.h"
30 #include "unpack-trees.h"
31 #include "xdiff-interface.h"
34 * We have many arrays of size 3. Whenever we have such an array, the
35 * indices refer to one of the sides of the three-way merge. This is so
36 * pervasive that the constants 0, 1, and 2 are used in many places in the
37 * code (especially in arithmetic operations to find the other side's index
38 * or to compute a relevant mask), but sometimes these enum names are used
39 * to aid code clarity.
41 * See also 'filemask' and 'dirmask' in struct conflict_info; the "ith side"
42 * referred to there is one of these three sides.
50 struct merge_options_internal
{
52 * paths: primary data structure in all of merge ort.
55 * * are full relative paths from the toplevel of the repository
56 * (e.g. "drivers/firmware/raspberrypi.c").
57 * * store all relevant paths in the repo, both directories and
58 * files (e.g. drivers, drivers/firmware would also be included)
59 * * these keys serve to intern all the path strings, which allows
60 * us to do pointer comparison on directory names instead of
61 * strcmp; we just have to be careful to use the interned strings.
62 * (Technically paths_to_free may track some strings that were
63 * removed from froms paths.)
65 * The values of paths:
66 * * either a pointer to a merged_info, or a conflict_info struct
67 * * merged_info contains all relevant information for a
68 * non-conflicted entry.
69 * * conflict_info contains a merged_info, plus any additional
70 * information about a conflict such as the higher orders stages
71 * involved and the names of the paths those came from (handy
72 * once renames get involved).
73 * * a path may start "conflicted" (i.e. point to a conflict_info)
74 * and then a later step (e.g. three-way content merge) determines
75 * it can be cleanly merged, at which point it'll be marked clean
76 * and the algorithm will ignore any data outside the contained
77 * merged_info for that entry
78 * * If an entry remains conflicted, the merged_info portion of a
79 * conflict_info will later be filled with whatever version of
80 * the file should be placed in the working directory (e.g. an
81 * as-merged-as-possible variation that contains conflict markers).
86 * conflicted: a subset of keys->values from "paths"
88 * conflicted is basically an optimization between process_entries()
89 * and record_conflicted_index_entries(); the latter could loop over
90 * ALL the entries in paths AGAIN and look for the ones that are
91 * still conflicted, but since process_entries() has to loop over
92 * all of them, it saves the ones it couldn't resolve in this strmap
93 * so that record_conflicted_index_entries() can iterate just the
96 struct strmap conflicted
;
99 * paths_to_free: additional list of strings to free
101 * If keys are removed from "paths", they are added to paths_to_free
102 * to ensure they are later freed. We avoid free'ing immediately since
103 * other places (e.g. conflict_info.pathnames[]) may still be
104 * referencing these paths.
106 struct string_list paths_to_free
;
109 * output: special messages and conflict notices for various paths
111 * This is a map of pathnames (a subset of the keys in "paths" above)
112 * to strbufs. It gathers various warning/conflict/notice messages
113 * for later processing.
115 struct strmap output
;
118 * current_dir_name: temporary var used in collect_merge_info_callback()
120 * Used to set merged_info.directory_name; see documentation for that
121 * variable and the requirements placed on that field.
123 const char *current_dir_name
;
125 /* call_depth: recursion level counter for merging merge bases */
129 struct version_info
{
130 struct object_id oid
;
135 /* if is_null, ignore result. otherwise result has oid & mode */
136 struct version_info result
;
140 * clean: whether the path in question is cleanly merged.
142 * see conflict_info.merged for more details.
147 * basename_offset: offset of basename of path.
149 * perf optimization to avoid recomputing offset of final '/'
150 * character in pathname (0 if no '/' in pathname).
152 size_t basename_offset
;
155 * directory_name: containing directory name.
157 * Note that we assume directory_name is constructed such that
158 * strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name,
159 * i.e. string equality is equivalent to pointer equality. For this
160 * to hold, we have to be careful setting directory_name.
162 const char *directory_name
;
165 struct conflict_info
{
167 * merged: the version of the path that will be written to working tree
169 * WARNING: It is critical to check merged.clean and ensure it is 0
170 * before reading any conflict_info fields outside of merged.
171 * Allocated merge_info structs will always have clean set to 1.
172 * Allocated conflict_info structs will have merged.clean set to 0
173 * initially. The merged.clean field is how we know if it is safe
174 * to access other parts of conflict_info besides merged; if a
175 * conflict_info's merged.clean is changed to 1, the rest of the
176 * algorithm is not allowed to look at anything outside of the
177 * merged member anymore.
179 struct merged_info merged
;
181 /* oids & modes from each of the three trees for this path */
182 struct version_info stages
[3];
184 /* pathnames for each stage; may differ due to rename detection */
185 const char *pathnames
[3];
187 /* Whether this path is/was involved in a directory/file conflict */
188 unsigned df_conflict
:1;
191 * Whether this path is/was involved in a non-content conflict other
192 * than a directory/file conflict (e.g. rename/rename, rename/delete,
193 * file location based on possible directory rename).
195 unsigned path_conflict
:1;
198 * For filemask and dirmask, the ith bit corresponds to whether the
199 * ith entry is a file (filemask) or a directory (dirmask). Thus,
200 * filemask & dirmask is always zero, and filemask | dirmask is at
201 * most 7 but can be less when a path does not appear as either a
202 * file or a directory on at least one side of history.
204 * Note that these masks are related to enum merge_side, as the ith
205 * entry corresponds to side i.
207 * These values come from a traverse_trees() call; more info may be
208 * found looking at tree-walk.h's struct traverse_info,
209 * particularly the documentation above the "fn" member (note that
210 * filemask = mask & ~dirmask from that documentation).
216 * Optimization to track which stages match, to avoid the need to
217 * recompute it in multiple steps. Either 0 or at least 2 bits are
218 * set; if at least 2 bits are set, their corresponding stages match.
220 unsigned match_mask
:3;
223 /*** Function Grouping: various utility functions ***/
226 * For the next three macros, see warning for conflict_info.merged.
228 * In each of the below, mi is a struct merged_info*, and ci was defined
229 * as a struct conflict_info* (but we need to verify ci isn't actually
230 * pointed at a struct merged_info*).
232 * INITIALIZE_CI: Assign ci to mi but only if it's safe; set to NULL otherwise.
233 * VERIFY_CI: Ensure that something we assigned to a conflict_info* is one.
234 * ASSIGN_AND_VERIFY_CI: Similar to VERIFY_CI but do assignment first.
236 #define INITIALIZE_CI(ci, mi) do { \
237 (ci) = (!(mi) || (mi)->clean) ? NULL : (struct conflict_info *)(mi); \
239 #define VERIFY_CI(ci) assert(ci && !ci->merged.clean);
240 #define ASSIGN_AND_VERIFY_CI(ci, mi) do { \
241 (ci) = (struct conflict_info *)(mi); \
242 assert((ci) && !(mi)->clean); \
245 static void free_strmap_strings(struct strmap
*map
)
247 struct hashmap_iter iter
;
248 struct strmap_entry
*entry
;
250 strmap_for_each_entry(map
, &iter
, entry
) {
251 free((char*)entry
->key
);
255 static void clear_internal_opts(struct merge_options_internal
*opti
,
258 assert(!reinitialize
);
261 * We marked opti->paths with strdup_strings = 0, so that we
262 * wouldn't have to make another copy of the fullpath created by
263 * make_traverse_path from setup_path_info(). But, now that we've
264 * used it and have no other references to these strings, it is time
265 * to deallocate them.
267 free_strmap_strings(&opti
->paths
);
268 strmap_clear(&opti
->paths
, 1);
271 * All keys and values in opti->conflicted are a subset of those in
272 * opti->paths. We don't want to deallocate anything twice, so we
273 * don't free the keys and we pass 0 for free_values.
275 strmap_clear(&opti
->conflicted
, 0);
278 * opti->paths_to_free is similar to opti->paths; we created it with
279 * strdup_strings = 0 to avoid making _another_ copy of the fullpath
280 * but now that we've used it and have no other references to these
281 * strings, it is time to deallocate them. We do so by temporarily
282 * setting strdup_strings to 1.
284 opti
->paths_to_free
.strdup_strings
= 1;
285 string_list_clear(&opti
->paths_to_free
, 0);
286 opti
->paths_to_free
.strdup_strings
= 0;
289 struct hashmap_iter iter
;
290 struct strmap_entry
*e
;
292 /* Release and free each strbuf found in output */
293 strmap_for_each_entry(&opti
->output
, &iter
, e
) {
294 struct strbuf
*sb
= e
->value
;
297 * While strictly speaking we don't need to free(sb)
298 * here because we could pass free_values=1 when
299 * calling strmap_clear() on opti->output, that would
300 * require strmap_clear to do another
301 * strmap_for_each_entry() loop, so we just free it
302 * while we're iterating anyway.
306 strmap_clear(&opti
->output
, 0);
310 static int err(struct merge_options
*opt
, const char *err
, ...)
313 struct strbuf sb
= STRBUF_INIT
;
315 strbuf_addstr(&sb
, "error: ");
316 va_start(params
, err
);
317 strbuf_vaddf(&sb
, err
, params
);
326 __attribute__((format (printf
, 4, 5)))
327 static void path_msg(struct merge_options
*opt
,
329 int omittable_hint
, /* skippable under --remerge-diff */
330 const char *fmt
, ...)
333 struct strbuf
*sb
= strmap_get(&opt
->priv
->output
, path
);
335 sb
= xmalloc(sizeof(*sb
));
337 strmap_put(&opt
->priv
->output
, path
, sb
);
341 strbuf_vaddf(sb
, fmt
, ap
);
344 strbuf_addch(sb
, '\n');
347 /* add a string to a strbuf, but converting "/" to "_" */
348 static void add_flattened_path(struct strbuf
*out
, const char *s
)
351 strbuf_addstr(out
, s
);
352 for (; i
< out
->len
; i
++)
353 if (out
->buf
[i
] == '/')
357 static char *unique_path(struct strmap
*existing_paths
,
361 struct strbuf newpath
= STRBUF_INIT
;
365 strbuf_addf(&newpath
, "%s~", path
);
366 add_flattened_path(&newpath
, branch
);
368 base_len
= newpath
.len
;
369 while (strmap_contains(existing_paths
, newpath
.buf
)) {
370 strbuf_setlen(&newpath
, base_len
);
371 strbuf_addf(&newpath
, "_%d", suffix
++);
374 return strbuf_detach(&newpath
, NULL
);
377 /*** Function Grouping: functions related to collect_merge_info() ***/
379 static void setup_path_info(struct merge_options
*opt
,
380 struct string_list_item
*result
,
381 const char *current_dir_name
,
382 int current_dir_name_len
,
383 char *fullpath
, /* we'll take over ownership */
384 struct name_entry
*names
,
385 struct name_entry
*merged_version
,
386 unsigned is_null
, /* boolean */
387 unsigned df_conflict
, /* boolean */
390 int resolved
/* boolean */)
392 /* result->util is void*, so mi is a convenience typed variable */
393 struct merged_info
*mi
;
395 assert(!is_null
|| resolved
);
396 assert(!df_conflict
|| !resolved
); /* df_conflict implies !resolved */
397 assert(resolved
== (merged_version
!= NULL
));
399 mi
= xcalloc(1, resolved
? sizeof(struct merged_info
) :
400 sizeof(struct conflict_info
));
401 mi
->directory_name
= current_dir_name
;
402 mi
->basename_offset
= current_dir_name_len
;
403 mi
->clean
= !!resolved
;
405 mi
->result
.mode
= merged_version
->mode
;
406 oidcpy(&mi
->result
.oid
, &merged_version
->oid
);
407 mi
->is_null
= !!is_null
;
410 struct conflict_info
*ci
;
412 ASSIGN_AND_VERIFY_CI(ci
, mi
);
413 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
414 ci
->pathnames
[i
] = fullpath
;
415 ci
->stages
[i
].mode
= names
[i
].mode
;
416 oidcpy(&ci
->stages
[i
].oid
, &names
[i
].oid
);
418 ci
->filemask
= filemask
;
419 ci
->dirmask
= dirmask
;
420 ci
->df_conflict
= !!df_conflict
;
423 * Assume is_null for now, but if we have entries
424 * under the directory then when it is complete in
425 * write_completed_directory() it'll update this.
426 * Also, for D/F conflicts, we have to handle the
427 * directory first, then clear this bit and process
428 * the file to see how it is handled -- that occurs
429 * near the top of process_entry().
433 strmap_put(&opt
->priv
->paths
, fullpath
, mi
);
434 result
->string
= fullpath
;
438 static int collect_merge_info_callback(int n
,
440 unsigned long dirmask
,
441 struct name_entry
*names
,
442 struct traverse_info
*info
)
446 * common ancestor (mbase) has mask 1, and stored in index 0 of names
447 * head of side 1 (side1) has mask 2, and stored in index 1 of names
448 * head of side 2 (side2) has mask 4, and stored in index 2 of names
450 struct merge_options
*opt
= info
->data
;
451 struct merge_options_internal
*opti
= opt
->priv
;
452 struct string_list_item pi
; /* Path Info */
453 struct conflict_info
*ci
; /* typed alias to pi.util (which is void*) */
454 struct name_entry
*p
;
457 const char *dirname
= opti
->current_dir_name
;
458 unsigned filemask
= mask
& ~dirmask
;
459 unsigned match_mask
= 0; /* will be updated below */
460 unsigned mbase_null
= !(mask
& 1);
461 unsigned side1_null
= !(mask
& 2);
462 unsigned side2_null
= !(mask
& 4);
463 unsigned side1_matches_mbase
= (!side1_null
&& !mbase_null
&&
464 names
[0].mode
== names
[1].mode
&&
465 oideq(&names
[0].oid
, &names
[1].oid
));
466 unsigned side2_matches_mbase
= (!side2_null
&& !mbase_null
&&
467 names
[0].mode
== names
[2].mode
&&
468 oideq(&names
[0].oid
, &names
[2].oid
));
469 unsigned sides_match
= (!side1_null
&& !side2_null
&&
470 names
[1].mode
== names
[2].mode
&&
471 oideq(&names
[1].oid
, &names
[2].oid
));
474 * Note: When a path is a file on one side of history and a directory
475 * in another, we have a directory/file conflict. In such cases, if
476 * the conflict doesn't resolve from renames and deletions, then we
477 * always leave directories where they are and move files out of the
478 * way. Thus, while struct conflict_info has a df_conflict field to
479 * track such conflicts, we ignore that field for any directories at
480 * a path and only pay attention to it for files at the given path.
481 * The fact that we leave directories were they are also means that
482 * we do not need to worry about getting additional df_conflict
483 * information propagated from parent directories down to children
484 * (unlike, say traverse_trees_recursive() in unpack-trees.c, which
485 * sets a newinfo.df_conflicts field specifically to propagate it).
487 unsigned df_conflict
= (filemask
!= 0) && (dirmask
!= 0);
489 /* n = 3 is a fundamental assumption. */
491 BUG("Called collect_merge_info_callback wrong");
494 * A bunch of sanity checks verifying that traverse_trees() calls
495 * us the way I expect. Could just remove these at some point,
496 * though maybe they are helpful to future code readers.
498 assert(mbase_null
== is_null_oid(&names
[0].oid
));
499 assert(side1_null
== is_null_oid(&names
[1].oid
));
500 assert(side2_null
== is_null_oid(&names
[2].oid
));
501 assert(!mbase_null
|| !side1_null
|| !side2_null
);
502 assert(mask
> 0 && mask
< 8);
504 /* Determine match_mask */
505 if (side1_matches_mbase
)
506 match_mask
= (side2_matches_mbase
? 7 : 3);
507 else if (side2_matches_mbase
)
509 else if (sides_match
)
513 * Get the name of the relevant filepath, which we'll pass to
514 * setup_path_info() for tracking.
519 len
= traverse_path_len(info
, p
->pathlen
);
521 /* +1 in both of the following lines to include the NUL byte */
522 fullpath
= xmalloc(len
+ 1);
523 make_traverse_path(fullpath
, len
+ 1, info
, p
->path
, p
->pathlen
);
526 * If mbase, side1, and side2 all match, we can resolve early. Even
527 * if these are trees, there will be no renames or anything
530 if (side1_matches_mbase
&& side2_matches_mbase
) {
531 /* mbase, side1, & side2 all match; use mbase as resolution */
532 setup_path_info(opt
, &pi
, dirname
, info
->pathlen
, fullpath
,
533 names
, names
+0, mbase_null
, 0,
534 filemask
, dirmask
, 1);
539 * Record information about the path so we can resolve later in
542 setup_path_info(opt
, &pi
, dirname
, info
->pathlen
, fullpath
,
543 names
, NULL
, 0, df_conflict
, filemask
, dirmask
, 0);
547 ci
->match_mask
= match_mask
;
549 /* If dirmask, recurse into subdirectories */
551 struct traverse_info newinfo
;
552 struct tree_desc t
[3];
553 void *buf
[3] = {NULL
, NULL
, NULL
};
554 const char *original_dir_name
;
557 ci
->match_mask
&= filemask
;
560 newinfo
.name
= p
->path
;
561 newinfo
.namelen
= p
->pathlen
;
562 newinfo
.pathlen
= st_add3(newinfo
.pathlen
, p
->pathlen
, 1);
564 * If this directory we are about to recurse into cared about
565 * its parent directory (the current directory) having a D/F
566 * conflict, then we'd propagate the masks in this way:
567 * newinfo.df_conflicts |= (mask & ~dirmask);
568 * But we don't worry about propagating D/F conflicts. (See
569 * comment near setting of local df_conflict variable near
570 * the beginning of this function).
573 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
574 if (i
== 1 && side1_matches_mbase
)
576 else if (i
== 2 && side2_matches_mbase
)
578 else if (i
== 2 && sides_match
)
581 const struct object_id
*oid
= NULL
;
584 buf
[i
] = fill_tree_descriptor(opt
->repo
,
590 original_dir_name
= opti
->current_dir_name
;
591 opti
->current_dir_name
= pi
.string
;
592 ret
= traverse_trees(NULL
, 3, t
, &newinfo
);
593 opti
->current_dir_name
= original_dir_name
;
595 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++)
605 static int collect_merge_info(struct merge_options
*opt
,
606 struct tree
*merge_base
,
611 struct tree_desc t
[3];
612 struct traverse_info info
;
613 const char *toplevel_dir_placeholder
= "";
615 opt
->priv
->current_dir_name
= toplevel_dir_placeholder
;
616 setup_traverse_info(&info
, toplevel_dir_placeholder
);
617 info
.fn
= collect_merge_info_callback
;
619 info
.show_all_errors
= 1;
621 parse_tree(merge_base
);
624 init_tree_desc(t
+ 0, merge_base
->buffer
, merge_base
->size
);
625 init_tree_desc(t
+ 1, side1
->buffer
, side1
->size
);
626 init_tree_desc(t
+ 2, side2
->buffer
, side2
->size
);
628 ret
= traverse_trees(NULL
, 3, t
, &info
);
633 /*** Function Grouping: functions related to threeway content merges ***/
635 static int merge_submodule(struct merge_options
*opt
,
637 const struct object_id
*o
,
638 const struct object_id
*a
,
639 const struct object_id
*b
,
640 struct object_id
*result
)
642 die("Not yet implemented.");
645 static int merge_3way(struct merge_options
*opt
,
647 const struct object_id
*o
,
648 const struct object_id
*a
,
649 const struct object_id
*b
,
650 const char *pathnames
[3],
651 const int extra_marker_size
,
652 mmbuffer_t
*result_buf
)
654 mmfile_t orig
, src1
, src2
;
655 struct ll_merge_options ll_opts
= {0};
656 char *base
, *name1
, *name2
;
659 ll_opts
.renormalize
= opt
->renormalize
;
660 ll_opts
.extra_marker_size
= extra_marker_size
;
661 ll_opts
.xdl_opts
= opt
->xdl_opts
;
663 if (opt
->priv
->call_depth
) {
664 ll_opts
.virtual_ancestor
= 1;
667 switch (opt
->recursive_variant
) {
668 case MERGE_VARIANT_OURS
:
669 ll_opts
.variant
= XDL_MERGE_FAVOR_OURS
;
671 case MERGE_VARIANT_THEIRS
:
672 ll_opts
.variant
= XDL_MERGE_FAVOR_THEIRS
;
680 assert(pathnames
[0] && pathnames
[1] && pathnames
[2] && opt
->ancestor
);
681 if (pathnames
[0] == pathnames
[1] && pathnames
[1] == pathnames
[2]) {
682 base
= mkpathdup("%s", opt
->ancestor
);
683 name1
= mkpathdup("%s", opt
->branch1
);
684 name2
= mkpathdup("%s", opt
->branch2
);
686 base
= mkpathdup("%s:%s", opt
->ancestor
, pathnames
[0]);
687 name1
= mkpathdup("%s:%s", opt
->branch1
, pathnames
[1]);
688 name2
= mkpathdup("%s:%s", opt
->branch2
, pathnames
[2]);
691 read_mmblob(&orig
, o
);
692 read_mmblob(&src1
, a
);
693 read_mmblob(&src2
, b
);
695 merge_status
= ll_merge(result_buf
, path
, &orig
, base
,
696 &src1
, name1
, &src2
, name2
,
697 opt
->repo
->index
, &ll_opts
);
708 static int handle_content_merge(struct merge_options
*opt
,
710 const struct version_info
*o
,
711 const struct version_info
*a
,
712 const struct version_info
*b
,
713 const char *pathnames
[3],
714 const int extra_marker_size
,
715 struct version_info
*result
)
718 * path is the target location where we want to put the file, and
719 * is used to determine any normalization rules in ll_merge.
721 * The normal case is that path and all entries in pathnames are
722 * identical, though renames can affect which path we got one of
723 * the three blobs to merge on various sides of history.
725 * extra_marker_size is the amount to extend conflict markers in
726 * ll_merge; this is neeed if we have content merges of content
727 * merges, which happens for example with rename/rename(2to1) and
728 * rename/add conflicts.
733 * handle_content_merge() needs both files to be of the same type, i.e.
734 * both files OR both submodules OR both symlinks. Conflicting types
735 * needs to be handled elsewhere.
737 assert((S_IFMT
& a
->mode
) == (S_IFMT
& b
->mode
));
740 if (a
->mode
== b
->mode
|| a
->mode
== o
->mode
)
741 result
->mode
= b
->mode
;
743 /* must be the 100644/100755 case */
744 assert(S_ISREG(a
->mode
));
745 result
->mode
= a
->mode
;
746 clean
= (b
->mode
== o
->mode
);
748 * FIXME: If opt->priv->call_depth && !clean, then we really
749 * should not make result->mode match either a->mode or
750 * b->mode; that causes t6036 "check conflicting mode for
751 * regular file" to fail. It would be best to use some other
752 * mode, but we'll confuse all kinds of stuff if we use one
753 * where S_ISREG(result->mode) isn't true, and if we use
754 * something like 0100666, then tree-walk.c's calls to
755 * canon_mode() will just normalize that to 100644 for us and
756 * thus not solve anything.
758 * Figure out if there's some kind of way we can work around
766 * Note: While one might assume that the next four lines would
767 * be unnecessary due to the fact that match_mask is often
768 * setup and already handled, renames don't always take care
771 if (oideq(&a
->oid
, &b
->oid
) || oideq(&a
->oid
, &o
->oid
))
772 oidcpy(&result
->oid
, &b
->oid
);
773 else if (oideq(&b
->oid
, &o
->oid
))
774 oidcpy(&result
->oid
, &a
->oid
);
776 /* Remaining rules depend on file vs. submodule vs. symlink. */
777 else if (S_ISREG(a
->mode
)) {
778 mmbuffer_t result_buf
;
779 int ret
= 0, merge_status
;
783 * If 'o' is different type, treat it as null so we do a
786 two_way
= ((S_IFMT
& o
->mode
) != (S_IFMT
& a
->mode
));
788 merge_status
= merge_3way(opt
, path
,
789 two_way
? &null_oid
: &o
->oid
,
791 pathnames
, extra_marker_size
,
794 if ((merge_status
< 0) || !result_buf
.ptr
)
795 ret
= err(opt
, _("Failed to execute internal merge"));
798 write_object_file(result_buf
.ptr
, result_buf
.size
,
799 blob_type
, &result
->oid
))
800 ret
= err(opt
, _("Unable to add %s to database"),
803 free(result_buf
.ptr
);
806 clean
&= (merge_status
== 0);
807 path_msg(opt
, path
, 1, _("Auto-merging %s"), path
);
808 } else if (S_ISGITLINK(a
->mode
)) {
809 int two_way
= ((S_IFMT
& o
->mode
) != (S_IFMT
& a
->mode
));
810 clean
= merge_submodule(opt
, pathnames
[0],
811 two_way
? &null_oid
: &o
->oid
,
812 &a
->oid
, &b
->oid
, &result
->oid
);
813 if (opt
->priv
->call_depth
&& two_way
&& !clean
) {
814 result
->mode
= o
->mode
;
815 oidcpy(&result
->oid
, &o
->oid
);
817 } else if (S_ISLNK(a
->mode
)) {
818 if (opt
->priv
->call_depth
) {
820 result
->mode
= o
->mode
;
821 oidcpy(&result
->oid
, &o
->oid
);
823 switch (opt
->recursive_variant
) {
824 case MERGE_VARIANT_NORMAL
:
826 oidcpy(&result
->oid
, &a
->oid
);
828 case MERGE_VARIANT_OURS
:
829 oidcpy(&result
->oid
, &a
->oid
);
831 case MERGE_VARIANT_THEIRS
:
832 oidcpy(&result
->oid
, &b
->oid
);
837 BUG("unsupported object type in the tree: %06o for %s",
843 /*** Function Grouping: functions related to detect_and_process_renames(), ***
844 *** which are split into directory and regular rename detection sections. ***/
846 /*** Function Grouping: functions related to directory rename detection ***/
848 /*** Function Grouping: functions related to regular rename detection ***/
850 static int detect_and_process_renames(struct merge_options
*opt
,
851 struct tree
*merge_base
,
858 * Rename detection works by detecting file similarity. Here we use
859 * a really easy-to-implement scheme: files are similar IFF they have
860 * the same filename. Therefore, by this scheme, there are no renames.
862 * TODO: Actually implement a real rename detection scheme.
867 /*** Function Grouping: functions related to process_entries() ***/
869 static int string_list_df_name_compare(const char *one
, const char *two
)
871 int onelen
= strlen(one
);
872 int twolen
= strlen(two
);
874 * Here we only care that entries for D/F conflicts are
875 * adjacent, in particular with the file of the D/F conflict
876 * appearing before files below the corresponding directory.
877 * The order of the rest of the list is irrelevant for us.
879 * To achieve this, we sort with df_name_compare and provide
880 * the mode S_IFDIR so that D/F conflicts will sort correctly.
881 * We use the mode S_IFDIR for everything else for simplicity,
882 * since in other cases any changes in their order due to
883 * sorting cause no problems for us.
885 int cmp
= df_name_compare(one
, onelen
, S_IFDIR
,
886 two
, twolen
, S_IFDIR
);
888 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
889 * that 'foo' comes before 'foo/bar'.
893 return onelen
- twolen
;
896 struct directory_versions
{
898 * versions: list of (basename -> version_info)
900 * The basenames are in reverse lexicographic order of full pathnames,
901 * as processed in process_entries(). This puts all entries within
902 * a directory together, and covers the directory itself after
903 * everything within it, allowing us to write subtrees before needing
904 * to record information for the tree itself.
906 struct string_list versions
;
909 * offsets: list of (full relative path directories -> integer offsets)
911 * Since versions contains basenames from files in multiple different
912 * directories, we need to know which entries in versions correspond
913 * to which directories. Values of e.g.
917 * Would mean that entries 0-1 of versions are files in the toplevel
918 * directory, entries 2-4 are files under src/, and the remaining
919 * entries starting at index 5 are files under src/moduleA/.
921 struct string_list offsets
;
924 * last_directory: directory that previously processed file found in
926 * last_directory starts NULL, but records the directory in which the
927 * previous file was found within. As soon as
928 * directory(current_file) != last_directory
929 * then we need to start updating accounting in versions & offsets.
930 * Note that last_directory is always the last path in "offsets" (or
931 * NULL if "offsets" is empty) so this exists just for quick access.
933 const char *last_directory
;
935 /* last_directory_len: cached computation of strlen(last_directory) */
936 unsigned last_directory_len
;
939 static int tree_entry_order(const void *a_
, const void *b_
)
941 const struct string_list_item
*a
= a_
;
942 const struct string_list_item
*b
= b_
;
944 const struct merged_info
*ami
= a
->util
;
945 const struct merged_info
*bmi
= b
->util
;
946 return base_name_compare(a
->string
, strlen(a
->string
), ami
->result
.mode
,
947 b
->string
, strlen(b
->string
), bmi
->result
.mode
);
950 static void write_tree(struct object_id
*result_oid
,
951 struct string_list
*versions
,
955 size_t maxlen
= 0, extra
;
956 unsigned int nr
= versions
->nr
- offset
;
957 struct strbuf buf
= STRBUF_INIT
;
958 struct string_list relevant_entries
= STRING_LIST_INIT_NODUP
;
962 * We want to sort the last (versions->nr-offset) entries in versions.
963 * Do so by abusing the string_list API a bit: make another string_list
964 * that contains just those entries and then sort them.
966 * We won't use relevant_entries again and will let it just pop off the
967 * stack, so there won't be allocation worries or anything.
969 relevant_entries
.items
= versions
->items
+ offset
;
970 relevant_entries
.nr
= versions
->nr
- offset
;
971 QSORT(relevant_entries
.items
, relevant_entries
.nr
, tree_entry_order
);
973 /* Pre-allocate some space in buf */
974 extra
= hash_size
+ 8; /* 8: 6 for mode, 1 for space, 1 for NUL char */
975 for (i
= 0; i
< nr
; i
++) {
976 maxlen
+= strlen(versions
->items
[offset
+i
].string
) + extra
;
978 strbuf_grow(&buf
, maxlen
);
980 /* Write each entry out to buf */
981 for (i
= 0; i
< nr
; i
++) {
982 struct merged_info
*mi
= versions
->items
[offset
+i
].util
;
983 struct version_info
*ri
= &mi
->result
;
984 strbuf_addf(&buf
, "%o %s%c",
986 versions
->items
[offset
+i
].string
, '\0');
987 strbuf_add(&buf
, ri
->oid
.hash
, hash_size
);
990 /* Write this object file out, and record in result_oid */
991 write_object_file(buf
.buf
, buf
.len
, tree_type
, result_oid
);
992 strbuf_release(&buf
);
995 static void record_entry_for_tree(struct directory_versions
*dir_metadata
,
997 struct merged_info
*mi
)
999 const char *basename
;
1002 /* nothing to record */
1005 basename
= path
+ mi
->basename_offset
;
1006 assert(strchr(basename
, '/') == NULL
);
1007 string_list_append(&dir_metadata
->versions
,
1008 basename
)->util
= &mi
->result
;
1011 static void write_completed_directory(struct merge_options
*opt
,
1012 const char *new_directory_name
,
1013 struct directory_versions
*info
)
1015 const char *prev_dir
;
1016 struct merged_info
*dir_info
= NULL
;
1017 unsigned int offset
;
1020 * Some explanation of info->versions and info->offsets...
1022 * process_entries() iterates over all relevant files AND
1023 * directories in reverse lexicographic order, and calls this
1024 * function. Thus, an example of the paths that process_entries()
1025 * could operate on (along with the directories for those paths
1030 * src/moduleB/umm.c src/moduleB
1031 * src/moduleB/stuff.h src/moduleB
1032 * src/moduleB/baz.c src/moduleB
1034 * src/moduleA/foo.c src/moduleA
1035 * src/moduleA/bar.c src/moduleA
1042 * always contains the unprocessed entries and their
1043 * version_info information. For example, after the first five
1044 * entries above, info->versions would be:
1046 * xtract.c <xtract.c's version_info>
1047 * token.txt <token.txt's version_info>
1048 * umm.c <src/moduleB/umm.c's version_info>
1049 * stuff.h <src/moduleB/stuff.h's version_info>
1050 * baz.c <src/moduleB/baz.c's version_info>
1052 * Once a subdirectory is completed we remove the entries in
1053 * that subdirectory from info->versions, writing it as a tree
1054 * (write_tree()). Thus, as soon as we get to src/moduleB,
1055 * info->versions would be updated to
1057 * xtract.c <xtract.c's version_info>
1058 * token.txt <token.txt's version_info>
1059 * moduleB <src/moduleB's version_info>
1063 * helps us track which entries in info->versions correspond to
1064 * which directories. When we are N directories deep (e.g. 4
1065 * for src/modA/submod/subdir/), we have up to N+1 unprocessed
1066 * directories (+1 because of toplevel dir). Corresponding to
1067 * the info->versions example above, after processing five entries
1068 * info->offsets will be:
1073 * which is used to know that xtract.c & token.txt are from the
1074 * toplevel dirctory, while umm.c & stuff.h & baz.c are from the
1075 * src/moduleB directory. Again, following the example above,
1076 * once we need to process src/moduleB, then info->offsets is
1082 * which says that moduleB (and only moduleB so far) is in the
1085 * One unique thing to note about info->offsets here is that
1086 * "src" was not added to info->offsets until there was a path
1087 * (a file OR directory) immediately below src/ that got
1090 * Since process_entry() just appends new entries to info->versions,
1091 * write_completed_directory() only needs to do work if the next path
1092 * is in a directory that is different than the last directory found
1097 * If we are working with the same directory as the last entry, there
1098 * is no work to do. (See comments above the directory_name member of
1099 * struct merged_info for why we can use pointer comparison instead of
1102 if (new_directory_name
== info
->last_directory
)
1106 * If we are just starting (last_directory is NULL), or last_directory
1107 * is a prefix of the current directory, then we can just update
1108 * info->offsets to record the offset where we started this directory
1109 * and update last_directory to have quick access to it.
1111 if (info
->last_directory
== NULL
||
1112 !strncmp(new_directory_name
, info
->last_directory
,
1113 info
->last_directory_len
)) {
1114 uintptr_t offset
= info
->versions
.nr
;
1116 info
->last_directory
= new_directory_name
;
1117 info
->last_directory_len
= strlen(info
->last_directory
);
1119 * Record the offset into info->versions where we will
1120 * start recording basenames of paths found within
1121 * new_directory_name.
1123 string_list_append(&info
->offsets
,
1124 info
->last_directory
)->util
= (void*)offset
;
1129 * The next entry that will be processed will be within
1130 * new_directory_name. Since at this point we know that
1131 * new_directory_name is within a different directory than
1132 * info->last_directory, we have all entries for info->last_directory
1133 * in info->versions and we need to create a tree object for them.
1135 dir_info
= strmap_get(&opt
->priv
->paths
, info
->last_directory
);
1137 offset
= (uintptr_t)info
->offsets
.items
[info
->offsets
.nr
-1].util
;
1138 if (offset
== info
->versions
.nr
) {
1140 * Actually, we don't need to create a tree object in this
1141 * case. Whenever all files within a directory disappear
1142 * during the merge (e.g. unmodified on one side and
1143 * deleted on the other, or files were renamed elsewhere),
1144 * then we get here and the directory itself needs to be
1145 * omitted from its parent tree as well.
1147 dir_info
->is_null
= 1;
1150 * Write out the tree to the git object directory, and also
1151 * record the mode and oid in dir_info->result.
1153 dir_info
->is_null
= 0;
1154 dir_info
->result
.mode
= S_IFDIR
;
1155 write_tree(&dir_info
->result
.oid
, &info
->versions
, offset
,
1156 opt
->repo
->hash_algo
->rawsz
);
1160 * We've now used several entries from info->versions and one entry
1161 * from info->offsets, so we get rid of those values.
1164 info
->versions
.nr
= offset
;
1167 * Now we've taken care of the completed directory, but we need to
1168 * prepare things since future entries will be in
1169 * new_directory_name. (In particular, process_entry() will be
1170 * appending new entries to info->versions.) So, we need to make
1171 * sure new_directory_name is the last entry in info->offsets.
1173 prev_dir
= info
->offsets
.nr
== 0 ? NULL
:
1174 info
->offsets
.items
[info
->offsets
.nr
-1].string
;
1175 if (new_directory_name
!= prev_dir
) {
1176 uintptr_t c
= info
->versions
.nr
;
1177 string_list_append(&info
->offsets
,
1178 new_directory_name
)->util
= (void*)c
;
1181 /* And, of course, we need to update last_directory to match. */
1182 info
->last_directory
= new_directory_name
;
1183 info
->last_directory_len
= strlen(info
->last_directory
);
1186 /* Per entry merge function */
1187 static void process_entry(struct merge_options
*opt
,
1189 struct conflict_info
*ci
,
1190 struct directory_versions
*dir_metadata
)
1192 int df_file_index
= 0;
1195 assert(ci
->filemask
>= 0 && ci
->filemask
<= 7);
1196 /* ci->match_mask == 7 was handled in collect_merge_info_callback() */
1197 assert(ci
->match_mask
== 0 || ci
->match_mask
== 3 ||
1198 ci
->match_mask
== 5 || ci
->match_mask
== 6);
1201 record_entry_for_tree(dir_metadata
, path
, &ci
->merged
);
1202 if (ci
->filemask
== 0)
1203 /* nothing else to handle */
1205 assert(ci
->df_conflict
);
1208 if (ci
->df_conflict
&& ci
->merged
.result
.mode
== 0) {
1212 * directory no longer in the way, but we do have a file we
1213 * need to place here so we need to clean away the "directory
1214 * merges to nothing" result.
1216 ci
->df_conflict
= 0;
1217 assert(ci
->filemask
!= 0);
1218 ci
->merged
.clean
= 0;
1219 ci
->merged
.is_null
= 0;
1220 /* and we want to zero out any directory-related entries */
1221 ci
->match_mask
= (ci
->match_mask
& ~ci
->dirmask
);
1223 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
1224 if (ci
->filemask
& (1 << i
))
1226 ci
->stages
[i
].mode
= 0;
1227 oidcpy(&ci
->stages
[i
].oid
, &null_oid
);
1229 } else if (ci
->df_conflict
&& ci
->merged
.result
.mode
!= 0) {
1231 * This started out as a D/F conflict, and the entries in
1232 * the competing directory were not removed by the merge as
1233 * evidenced by write_completed_directory() writing a value
1234 * to ci->merged.result.mode.
1236 struct conflict_info
*new_ci
;
1238 const char *old_path
= path
;
1241 assert(ci
->merged
.result
.mode
== S_IFDIR
);
1244 * If filemask is 1, we can just ignore the file as having
1245 * been deleted on both sides. We do not want to overwrite
1246 * ci->merged.result, since it stores the tree for all the
1249 if (ci
->filemask
== 1) {
1255 * This file still exists on at least one side, and we want
1256 * the directory to remain here, so we need to move this
1257 * path to some new location.
1259 new_ci
= xcalloc(1, sizeof(*new_ci
));
1260 /* We don't really want new_ci->merged.result copied, but it'll
1261 * be overwritten below so it doesn't matter. We also don't
1262 * want any directory mode/oid values copied, but we'll zero
1263 * those out immediately. We do want the rest of ci copied.
1265 memcpy(new_ci
, ci
, sizeof(*ci
));
1266 new_ci
->match_mask
= (new_ci
->match_mask
& ~new_ci
->dirmask
);
1267 new_ci
->dirmask
= 0;
1268 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
1269 if (new_ci
->filemask
& (1 << i
))
1271 /* zero out any entries related to directories */
1272 new_ci
->stages
[i
].mode
= 0;
1273 oidcpy(&new_ci
->stages
[i
].oid
, &null_oid
);
1277 * Find out which side this file came from; note that we
1278 * cannot just use ci->filemask, because renames could cause
1279 * the filemask to go back to 7. So we use dirmask, then
1280 * pick the opposite side's index.
1282 df_file_index
= (ci
->dirmask
& (1 << 1)) ? 2 : 1;
1283 branch
= (df_file_index
== 1) ? opt
->branch1
: opt
->branch2
;
1284 path
= unique_path(&opt
->priv
->paths
, path
, branch
);
1285 strmap_put(&opt
->priv
->paths
, path
, new_ci
);
1287 path_msg(opt
, path
, 0,
1288 _("CONFLICT (file/directory): directory in the way "
1289 "of %s from %s; moving it to %s instead."),
1290 old_path
, branch
, path
);
1293 * Zero out the filemask for the old ci. At this point, ci
1294 * was just an entry for a directory, so we don't need to
1295 * do anything more with it.
1300 * Now note that we're working on the new entry (path was
1307 * NOTE: Below there is a long switch-like if-elseif-elseif... block
1308 * which the code goes through even for the df_conflict cases
1311 if (ci
->match_mask
) {
1312 ci
->merged
.clean
= 1;
1313 if (ci
->match_mask
== 6) {
1314 /* stages[1] == stages[2] */
1315 ci
->merged
.result
.mode
= ci
->stages
[1].mode
;
1316 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[1].oid
);
1318 /* determine the mask of the side that didn't match */
1319 unsigned int othermask
= 7 & ~ci
->match_mask
;
1320 int side
= (othermask
== 4) ? 2 : 1;
1322 ci
->merged
.result
.mode
= ci
->stages
[side
].mode
;
1323 ci
->merged
.is_null
= !ci
->merged
.result
.mode
;
1324 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[side
].oid
);
1326 assert(othermask
== 2 || othermask
== 4);
1327 assert(ci
->merged
.is_null
==
1328 (ci
->filemask
== ci
->match_mask
));
1330 } else if (ci
->filemask
>= 6 &&
1331 (S_IFMT
& ci
->stages
[1].mode
) !=
1332 (S_IFMT
& ci
->stages
[2].mode
)) {
1334 * Two different items from (file/submodule/symlink)
1336 die("Not yet implemented.");
1337 } else if (ci
->filemask
>= 6) {
1338 /* Need a two-way or three-way content merge */
1339 struct version_info merged_file
;
1340 unsigned clean_merge
;
1341 struct version_info
*o
= &ci
->stages
[0];
1342 struct version_info
*a
= &ci
->stages
[1];
1343 struct version_info
*b
= &ci
->stages
[2];
1345 clean_merge
= handle_content_merge(opt
, path
, o
, a
, b
,
1347 opt
->priv
->call_depth
* 2,
1349 ci
->merged
.clean
= clean_merge
&&
1350 !ci
->df_conflict
&& !ci
->path_conflict
;
1351 ci
->merged
.result
.mode
= merged_file
.mode
;
1352 ci
->merged
.is_null
= (merged_file
.mode
== 0);
1353 oidcpy(&ci
->merged
.result
.oid
, &merged_file
.oid
);
1354 if (clean_merge
&& ci
->df_conflict
) {
1355 assert(df_file_index
== 1 || df_file_index
== 2);
1356 ci
->filemask
= 1 << df_file_index
;
1357 ci
->stages
[df_file_index
].mode
= merged_file
.mode
;
1358 oidcpy(&ci
->stages
[df_file_index
].oid
, &merged_file
.oid
);
1361 const char *reason
= _("content");
1362 if (ci
->filemask
== 6)
1363 reason
= _("add/add");
1364 if (S_ISGITLINK(merged_file
.mode
))
1365 reason
= _("submodule");
1366 path_msg(opt
, path
, 0,
1367 _("CONFLICT (%s): Merge conflict in %s"),
1370 } else if (ci
->filemask
== 3 || ci
->filemask
== 5) {
1372 const char *modify_branch
, *delete_branch
;
1373 int side
= (ci
->filemask
== 5) ? 2 : 1;
1374 int index
= opt
->priv
->call_depth
? 0 : side
;
1376 ci
->merged
.result
.mode
= ci
->stages
[index
].mode
;
1377 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[index
].oid
);
1378 ci
->merged
.clean
= 0;
1380 modify_branch
= (side
== 1) ? opt
->branch1
: opt
->branch2
;
1381 delete_branch
= (side
== 1) ? opt
->branch2
: opt
->branch1
;
1383 path_msg(opt
, path
, 0,
1384 _("CONFLICT (modify/delete): %s deleted in %s "
1385 "and modified in %s. Version %s of %s left "
1387 path
, delete_branch
, modify_branch
,
1388 modify_branch
, path
);
1389 } else if (ci
->filemask
== 2 || ci
->filemask
== 4) {
1390 /* Added on one side */
1391 int side
= (ci
->filemask
== 4) ? 2 : 1;
1392 ci
->merged
.result
.mode
= ci
->stages
[side
].mode
;
1393 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[side
].oid
);
1394 ci
->merged
.clean
= !ci
->df_conflict
;
1395 } else if (ci
->filemask
== 1) {
1396 /* Deleted on both sides */
1397 ci
->merged
.is_null
= 1;
1398 ci
->merged
.result
.mode
= 0;
1399 oidcpy(&ci
->merged
.result
.oid
, &null_oid
);
1400 ci
->merged
.clean
= 1;
1404 * If still conflicted, record it separately. This allows us to later
1405 * iterate over just conflicted entries when updating the index instead
1406 * of iterating over all entries.
1408 if (!ci
->merged
.clean
)
1409 strmap_put(&opt
->priv
->conflicted
, path
, ci
);
1410 record_entry_for_tree(dir_metadata
, path
, &ci
->merged
);
1413 static void process_entries(struct merge_options
*opt
,
1414 struct object_id
*result_oid
)
1416 struct hashmap_iter iter
;
1417 struct strmap_entry
*e
;
1418 struct string_list plist
= STRING_LIST_INIT_NODUP
;
1419 struct string_list_item
*entry
;
1420 struct directory_versions dir_metadata
= { STRING_LIST_INIT_NODUP
,
1421 STRING_LIST_INIT_NODUP
,
1424 if (strmap_empty(&opt
->priv
->paths
)) {
1425 oidcpy(result_oid
, opt
->repo
->hash_algo
->empty_tree
);
1429 /* Hack to pre-allocate plist to the desired size */
1430 ALLOC_GROW(plist
.items
, strmap_get_size(&opt
->priv
->paths
), plist
.alloc
);
1432 /* Put every entry from paths into plist, then sort */
1433 strmap_for_each_entry(&opt
->priv
->paths
, &iter
, e
) {
1434 string_list_append(&plist
, e
->key
)->util
= e
->value
;
1436 plist
.cmp
= string_list_df_name_compare
;
1437 string_list_sort(&plist
);
1440 * Iterate over the items in reverse order, so we can handle paths
1441 * below a directory before needing to handle the directory itself.
1443 * This allows us to write subtrees before we need to write trees,
1444 * and it also enables sane handling of directory/file conflicts
1445 * (because it allows us to know whether the directory is still in
1446 * the way when it is time to process the file at the same path).
1448 for (entry
= &plist
.items
[plist
.nr
-1]; entry
>= plist
.items
; --entry
) {
1449 char *path
= entry
->string
;
1451 * NOTE: mi may actually be a pointer to a conflict_info, but
1452 * we have to check mi->clean first to see if it's safe to
1453 * reassign to such a pointer type.
1455 struct merged_info
*mi
= entry
->util
;
1457 write_completed_directory(opt
, mi
->directory_name
,
1460 record_entry_for_tree(&dir_metadata
, path
, mi
);
1462 struct conflict_info
*ci
= (struct conflict_info
*)mi
;
1463 process_entry(opt
, path
, ci
, &dir_metadata
);
1467 if (dir_metadata
.offsets
.nr
!= 1 ||
1468 (uintptr_t)dir_metadata
.offsets
.items
[0].util
!= 0) {
1469 printf("dir_metadata.offsets.nr = %d (should be 1)\n",
1470 dir_metadata
.offsets
.nr
);
1471 printf("dir_metadata.offsets.items[0].util = %u (should be 0)\n",
1472 (unsigned)(uintptr_t)dir_metadata
.offsets
.items
[0].util
);
1474 BUG("dir_metadata accounting completely off; shouldn't happen");
1476 write_tree(result_oid
, &dir_metadata
.versions
, 0,
1477 opt
->repo
->hash_algo
->rawsz
);
1478 string_list_clear(&plist
, 0);
1479 string_list_clear(&dir_metadata
.versions
, 0);
1480 string_list_clear(&dir_metadata
.offsets
, 0);
1483 /*** Function Grouping: functions related to merge_switch_to_result() ***/
1485 static int checkout(struct merge_options
*opt
,
1489 /* Switch the index/working copy from old to new */
1491 struct tree_desc trees
[2];
1492 struct unpack_trees_options unpack_opts
;
1494 memset(&unpack_opts
, 0, sizeof(unpack_opts
));
1495 unpack_opts
.head_idx
= -1;
1496 unpack_opts
.src_index
= opt
->repo
->index
;
1497 unpack_opts
.dst_index
= opt
->repo
->index
;
1499 setup_unpack_trees_porcelain(&unpack_opts
, "merge");
1502 * NOTE: if this were just "git checkout" code, we would probably
1503 * read or refresh the cache and check for a conflicted index, but
1504 * builtin/merge.c or sequencer.c really needs to read the index
1505 * and check for conflicted entries before starting merging for a
1506 * good user experience (no sense waiting for merges/rebases before
1507 * erroring out), so there's no reason to duplicate that work here.
1510 /* 2-way merge to the new branch */
1511 unpack_opts
.update
= 1;
1512 unpack_opts
.merge
= 1;
1513 unpack_opts
.quiet
= 0; /* FIXME: sequencer might want quiet? */
1514 unpack_opts
.verbose_update
= (opt
->verbosity
> 2);
1515 unpack_opts
.fn
= twoway_merge
;
1516 if (1/* FIXME: opts->overwrite_ignore*/) {
1517 unpack_opts
.dir
= xcalloc(1, sizeof(*unpack_opts
.dir
));
1518 unpack_opts
.dir
->flags
|= DIR_SHOW_IGNORED
;
1519 setup_standard_excludes(unpack_opts
.dir
);
1522 init_tree_desc(&trees
[0], prev
->buffer
, prev
->size
);
1524 init_tree_desc(&trees
[1], next
->buffer
, next
->size
);
1526 ret
= unpack_trees(2, trees
, &unpack_opts
);
1527 clear_unpack_trees_porcelain(&unpack_opts
);
1528 dir_clear(unpack_opts
.dir
);
1529 FREE_AND_NULL(unpack_opts
.dir
);
1533 static int record_conflicted_index_entries(struct merge_options
*opt
,
1534 struct index_state
*index
,
1535 struct strmap
*paths
,
1536 struct strmap
*conflicted
)
1538 struct hashmap_iter iter
;
1539 struct strmap_entry
*e
;
1541 int original_cache_nr
;
1543 if (strmap_empty(conflicted
))
1546 original_cache_nr
= index
->cache_nr
;
1548 /* Put every entry from paths into plist, then sort */
1549 strmap_for_each_entry(conflicted
, &iter
, e
) {
1550 const char *path
= e
->key
;
1551 struct conflict_info
*ci
= e
->value
;
1553 struct cache_entry
*ce
;
1559 * The index will already have a stage=0 entry for this path,
1560 * because we created an as-merged-as-possible version of the
1561 * file and checkout() moved the working copy and index over
1564 * However, previous iterations through this loop will have
1565 * added unstaged entries to the end of the cache which
1566 * ignore the standard alphabetical ordering of cache
1567 * entries and break invariants needed for index_name_pos()
1568 * to work. However, we know the entry we want is before
1569 * those appended cache entries, so do a temporary swap on
1570 * cache_nr to only look through entries of interest.
1572 SWAP(index
->cache_nr
, original_cache_nr
);
1573 pos
= index_name_pos(index
, path
, strlen(path
));
1574 SWAP(index
->cache_nr
, original_cache_nr
);
1576 if (ci
->filemask
!= 1)
1577 BUG("Conflicted %s but nothing in basic working tree or index; this shouldn't happen", path
);
1578 cache_tree_invalidate_path(index
, path
);
1580 ce
= index
->cache
[pos
];
1583 * Clean paths with CE_SKIP_WORKTREE set will not be
1584 * written to the working tree by the unpack_trees()
1585 * call in checkout(). Our conflicted entries would
1586 * have appeared clean to that code since we ignored
1587 * the higher order stages. Thus, we need override
1588 * the CE_SKIP_WORKTREE bit and manually write those
1589 * files to the working disk here.
1591 * TODO: Implement this CE_SKIP_WORKTREE fixup.
1595 * Mark this cache entry for removal and instead add
1596 * new stage>0 entries corresponding to the
1597 * conflicts. If there are many conflicted entries, we
1598 * want to avoid memmove'ing O(NM) entries by
1599 * inserting the new entries one at a time. So,
1600 * instead, we just add the new cache entries to the
1601 * end (ignoring normal index requirements on sort
1602 * order) and sort the index once we're all done.
1604 ce
->ce_flags
|= CE_REMOVE
;
1607 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
1608 struct version_info
*vi
;
1609 if (!(ci
->filemask
& (1ul << i
)))
1611 vi
= &ci
->stages
[i
];
1612 ce
= make_cache_entry(index
, vi
->mode
, &vi
->oid
,
1614 add_index_entry(index
, ce
, ADD_CACHE_JUST_APPEND
);
1619 * Remove the unused cache entries (and invalidate the relevant
1620 * cache-trees), then sort the index entries to get the conflicted
1621 * entries we added to the end into their right locations.
1623 remove_marked_cache_entries(index
, 1);
1624 QSORT(index
->cache
, index
->cache_nr
, cmp_cache_name_compare
);
1629 void merge_switch_to_result(struct merge_options
*opt
,
1631 struct merge_result
*result
,
1632 int update_worktree_and_index
,
1633 int display_update_msgs
)
1635 assert(opt
->priv
== NULL
);
1636 if (result
->clean
>= 0 && update_worktree_and_index
) {
1637 struct merge_options_internal
*opti
= result
->priv
;
1639 if (checkout(opt
, head
, result
->tree
)) {
1640 /* failure to function */
1645 if (record_conflicted_index_entries(opt
, opt
->repo
->index
,
1647 &opti
->conflicted
)) {
1648 /* failure to function */
1654 if (display_update_msgs
) {
1655 struct merge_options_internal
*opti
= result
->priv
;
1656 struct hashmap_iter iter
;
1657 struct strmap_entry
*e
;
1658 struct string_list olist
= STRING_LIST_INIT_NODUP
;
1661 /* Hack to pre-allocate olist to the desired size */
1662 ALLOC_GROW(olist
.items
, strmap_get_size(&opti
->output
),
1665 /* Put every entry from output into olist, then sort */
1666 strmap_for_each_entry(&opti
->output
, &iter
, e
) {
1667 string_list_append(&olist
, e
->key
)->util
= e
->value
;
1669 string_list_sort(&olist
);
1671 /* Iterate over the items, printing them */
1672 for (i
= 0; i
< olist
.nr
; ++i
) {
1673 struct strbuf
*sb
= olist
.items
[i
].util
;
1675 printf("%s", sb
->buf
);
1677 string_list_clear(&olist
, 0);
1680 merge_finalize(opt
, result
);
1683 void merge_finalize(struct merge_options
*opt
,
1684 struct merge_result
*result
)
1686 struct merge_options_internal
*opti
= result
->priv
;
1688 assert(opt
->priv
== NULL
);
1690 clear_internal_opts(opti
, 0);
1691 FREE_AND_NULL(opti
);
1694 /*** Function Grouping: helper functions for merge_incore_*() ***/
1696 static void merge_start(struct merge_options
*opt
, struct merge_result
*result
)
1698 /* Sanity checks on opt */
1701 assert(opt
->branch1
&& opt
->branch2
);
1703 assert(opt
->detect_directory_renames
>= MERGE_DIRECTORY_RENAMES_NONE
&&
1704 opt
->detect_directory_renames
<= MERGE_DIRECTORY_RENAMES_TRUE
);
1705 assert(opt
->rename_limit
>= -1);
1706 assert(opt
->rename_score
>= 0 && opt
->rename_score
<= MAX_SCORE
);
1707 assert(opt
->show_rename_progress
>= 0 && opt
->show_rename_progress
<= 1);
1709 assert(opt
->xdl_opts
>= 0);
1710 assert(opt
->recursive_variant
>= MERGE_VARIANT_NORMAL
&&
1711 opt
->recursive_variant
<= MERGE_VARIANT_THEIRS
);
1714 * detect_renames, verbosity, buffer_output, and obuf are ignored
1715 * fields that were used by "recursive" rather than "ort" -- but
1716 * sanity check them anyway.
1718 assert(opt
->detect_renames
>= -1 &&
1719 opt
->detect_renames
<= DIFF_DETECT_COPY
);
1720 assert(opt
->verbosity
>= 0 && opt
->verbosity
<= 5);
1721 assert(opt
->buffer_output
<= 2);
1722 assert(opt
->obuf
.len
== 0);
1724 assert(opt
->priv
== NULL
);
1726 /* Default to histogram diff. Actually, just hardcode it...for now. */
1727 opt
->xdl_opts
= DIFF_WITH_ALG(opt
, HISTOGRAM_DIFF
);
1729 /* Initialization of opt->priv, our internal merge data */
1730 opt
->priv
= xcalloc(1, sizeof(*opt
->priv
));
1733 * Although we initialize opt->priv->paths with strdup_strings=0,
1734 * that's just to avoid making yet another copy of an allocated
1735 * string. Putting the entry into paths means we are taking
1736 * ownership, so we will later free it. paths_to_free is similar.
1738 * In contrast, conflicted just has a subset of keys from paths, so
1739 * we don't want to free those (it'd be a duplicate free).
1741 strmap_init_with_options(&opt
->priv
->paths
, NULL
, 0);
1742 strmap_init_with_options(&opt
->priv
->conflicted
, NULL
, 0);
1743 string_list_init(&opt
->priv
->paths_to_free
, 0);
1746 * keys & strbufs in output will sometimes need to outlive "paths",
1747 * so it will have a copy of relevant keys. It's probably a small
1748 * subset of the overall paths that have special output.
1750 strmap_init(&opt
->priv
->output
);
1753 /*** Function Grouping: merge_incore_*() and their internal variants ***/
1756 * Originally from merge_trees_internal(); heavily adapted, though.
1758 static void merge_ort_nonrecursive_internal(struct merge_options
*opt
,
1759 struct tree
*merge_base
,
1762 struct merge_result
*result
)
1764 struct object_id working_tree_oid
;
1766 if (collect_merge_info(opt
, merge_base
, side1
, side2
) != 0) {
1768 * TRANSLATORS: The %s arguments are: 1) tree hash of a merge
1769 * base, and 2-3) the trees for the two trees we're merging.
1771 err(opt
, _("collecting merge info failed for trees %s, %s, %s"),
1772 oid_to_hex(&merge_base
->object
.oid
),
1773 oid_to_hex(&side1
->object
.oid
),
1774 oid_to_hex(&side2
->object
.oid
));
1779 result
->clean
= detect_and_process_renames(opt
, merge_base
,
1781 process_entries(opt
, &working_tree_oid
);
1783 /* Set return values */
1784 result
->tree
= parse_tree_indirect(&working_tree_oid
);
1785 /* existence of conflicted entries implies unclean */
1786 result
->clean
&= strmap_empty(&opt
->priv
->conflicted
);
1787 if (!opt
->priv
->call_depth
) {
1788 result
->priv
= opt
->priv
;
1793 void merge_incore_nonrecursive(struct merge_options
*opt
,
1794 struct tree
*merge_base
,
1797 struct merge_result
*result
)
1799 assert(opt
->ancestor
!= NULL
);
1800 merge_start(opt
, result
);
1801 merge_ort_nonrecursive_internal(opt
, merge_base
, side1
, side2
, result
);
1804 void merge_incore_recursive(struct merge_options
*opt
,
1805 struct commit_list
*merge_bases
,
1806 struct commit
*side1
,
1807 struct commit
*side2
,
1808 struct merge_result
*result
)
1810 die("Not yet implemented");