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 * All variables that are arrays of size 3 correspond to data tracked
54 * for the sides in enum merge_side. Index 0 is almost always unused
55 * because we often only need to track information for MERGE_SIDE1 and
56 * MERGE_SIDE2 (MERGE_BASE can't have rename information since renames
57 * are determined relative to what changed since the MERGE_BASE).
61 * pairs: pairing of filenames from diffcore_rename()
63 struct diff_queue_struct pairs
[3];
66 * dirs_removed: directories removed on a given side of history.
68 struct strset dirs_removed
[3];
71 * dir_rename_count: tracking where parts of a directory were renamed to
73 * When files in a directory are renamed, they may not all go to the
74 * same location. Each strmap here tracks:
75 * old_dir => {new_dir => int}
76 * That is, dir_rename_count[side] is a strmap to a strintmap.
78 struct strmap dir_rename_count
[3];
81 * dir_renames: computed directory renames
83 * This is a map of old_dir => new_dir and is derived in part from
86 struct strmap dir_renames
[3];
89 * needed_limit: value needed for inexact rename detection to run
91 * If the current rename limit wasn't high enough for inexact
92 * rename detection to run, this records the limit needed. Otherwise,
93 * this value remains 0.
98 struct merge_options_internal
{
100 * paths: primary data structure in all of merge ort.
103 * * are full relative paths from the toplevel of the repository
104 * (e.g. "drivers/firmware/raspberrypi.c").
105 * * store all relevant paths in the repo, both directories and
106 * files (e.g. drivers, drivers/firmware would also be included)
107 * * these keys serve to intern all the path strings, which allows
108 * us to do pointer comparison on directory names instead of
109 * strcmp; we just have to be careful to use the interned strings.
110 * (Technically paths_to_free may track some strings that were
111 * removed from froms paths.)
113 * The values of paths:
114 * * either a pointer to a merged_info, or a conflict_info struct
115 * * merged_info contains all relevant information for a
116 * non-conflicted entry.
117 * * conflict_info contains a merged_info, plus any additional
118 * information about a conflict such as the higher orders stages
119 * involved and the names of the paths those came from (handy
120 * once renames get involved).
121 * * a path may start "conflicted" (i.e. point to a conflict_info)
122 * and then a later step (e.g. three-way content merge) determines
123 * it can be cleanly merged, at which point it'll be marked clean
124 * and the algorithm will ignore any data outside the contained
125 * merged_info for that entry
126 * * If an entry remains conflicted, the merged_info portion of a
127 * conflict_info will later be filled with whatever version of
128 * the file should be placed in the working directory (e.g. an
129 * as-merged-as-possible variation that contains conflict markers).
134 * conflicted: a subset of keys->values from "paths"
136 * conflicted is basically an optimization between process_entries()
137 * and record_conflicted_index_entries(); the latter could loop over
138 * ALL the entries in paths AGAIN and look for the ones that are
139 * still conflicted, but since process_entries() has to loop over
140 * all of them, it saves the ones it couldn't resolve in this strmap
141 * so that record_conflicted_index_entries() can iterate just the
144 struct strmap conflicted
;
147 * paths_to_free: additional list of strings to free
149 * If keys are removed from "paths", they are added to paths_to_free
150 * to ensure they are later freed. We avoid free'ing immediately since
151 * other places (e.g. conflict_info.pathnames[]) may still be
152 * referencing these paths.
154 struct string_list paths_to_free
;
157 * output: special messages and conflict notices for various paths
159 * This is a map of pathnames (a subset of the keys in "paths" above)
160 * to strbufs. It gathers various warning/conflict/notice messages
161 * for later processing.
163 struct strmap output
;
166 * renames: various data relating to rename detection
168 struct rename_info renames
;
171 * current_dir_name: temporary var used in collect_merge_info_callback()
173 * Used to set merged_info.directory_name; see documentation for that
174 * variable and the requirements placed on that field.
176 const char *current_dir_name
;
178 /* call_depth: recursion level counter for merging merge bases */
182 struct version_info
{
183 struct object_id oid
;
188 /* if is_null, ignore result. otherwise result has oid & mode */
189 struct version_info result
;
193 * clean: whether the path in question is cleanly merged.
195 * see conflict_info.merged for more details.
200 * basename_offset: offset of basename of path.
202 * perf optimization to avoid recomputing offset of final '/'
203 * character in pathname (0 if no '/' in pathname).
205 size_t basename_offset
;
208 * directory_name: containing directory name.
210 * Note that we assume directory_name is constructed such that
211 * strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name,
212 * i.e. string equality is equivalent to pointer equality. For this
213 * to hold, we have to be careful setting directory_name.
215 const char *directory_name
;
218 struct conflict_info
{
220 * merged: the version of the path that will be written to working tree
222 * WARNING: It is critical to check merged.clean and ensure it is 0
223 * before reading any conflict_info fields outside of merged.
224 * Allocated merge_info structs will always have clean set to 1.
225 * Allocated conflict_info structs will have merged.clean set to 0
226 * initially. The merged.clean field is how we know if it is safe
227 * to access other parts of conflict_info besides merged; if a
228 * conflict_info's merged.clean is changed to 1, the rest of the
229 * algorithm is not allowed to look at anything outside of the
230 * merged member anymore.
232 struct merged_info merged
;
234 /* oids & modes from each of the three trees for this path */
235 struct version_info stages
[3];
237 /* pathnames for each stage; may differ due to rename detection */
238 const char *pathnames
[3];
240 /* Whether this path is/was involved in a directory/file conflict */
241 unsigned df_conflict
:1;
244 * Whether this path is/was involved in a non-content conflict other
245 * than a directory/file conflict (e.g. rename/rename, rename/delete,
246 * file location based on possible directory rename).
248 unsigned path_conflict
:1;
251 * For filemask and dirmask, the ith bit corresponds to whether the
252 * ith entry is a file (filemask) or a directory (dirmask). Thus,
253 * filemask & dirmask is always zero, and filemask | dirmask is at
254 * most 7 but can be less when a path does not appear as either a
255 * file or a directory on at least one side of history.
257 * Note that these masks are related to enum merge_side, as the ith
258 * entry corresponds to side i.
260 * These values come from a traverse_trees() call; more info may be
261 * found looking at tree-walk.h's struct traverse_info,
262 * particularly the documentation above the "fn" member (note that
263 * filemask = mask & ~dirmask from that documentation).
269 * Optimization to track which stages match, to avoid the need to
270 * recompute it in multiple steps. Either 0 or at least 2 bits are
271 * set; if at least 2 bits are set, their corresponding stages match.
273 unsigned match_mask
:3;
276 /*** Function Grouping: various utility functions ***/
279 * For the next three macros, see warning for conflict_info.merged.
281 * In each of the below, mi is a struct merged_info*, and ci was defined
282 * as a struct conflict_info* (but we need to verify ci isn't actually
283 * pointed at a struct merged_info*).
285 * INITIALIZE_CI: Assign ci to mi but only if it's safe; set to NULL otherwise.
286 * VERIFY_CI: Ensure that something we assigned to a conflict_info* is one.
287 * ASSIGN_AND_VERIFY_CI: Similar to VERIFY_CI but do assignment first.
289 #define INITIALIZE_CI(ci, mi) do { \
290 (ci) = (!(mi) || (mi)->clean) ? NULL : (struct conflict_info *)(mi); \
292 #define VERIFY_CI(ci) assert(ci && !ci->merged.clean);
293 #define ASSIGN_AND_VERIFY_CI(ci, mi) do { \
294 (ci) = (struct conflict_info *)(mi); \
295 assert((ci) && !(mi)->clean); \
298 static void free_strmap_strings(struct strmap
*map
)
300 struct hashmap_iter iter
;
301 struct strmap_entry
*entry
;
303 strmap_for_each_entry(map
, &iter
, entry
) {
304 free((char*)entry
->key
);
308 static void clear_or_reinit_internal_opts(struct merge_options_internal
*opti
,
311 struct rename_info
*renames
= &opti
->renames
;
313 void (*strmap_func
)(struct strmap
*, int) =
314 reinitialize
? strmap_partial_clear
: strmap_clear
;
315 void (*strset_func
)(struct strset
*) =
316 reinitialize
? strset_partial_clear
: strset_clear
;
319 * We marked opti->paths with strdup_strings = 0, so that we
320 * wouldn't have to make another copy of the fullpath created by
321 * make_traverse_path from setup_path_info(). But, now that we've
322 * used it and have no other references to these strings, it is time
323 * to deallocate them.
325 free_strmap_strings(&opti
->paths
);
326 strmap_func(&opti
->paths
, 1);
329 * All keys and values in opti->conflicted are a subset of those in
330 * opti->paths. We don't want to deallocate anything twice, so we
331 * don't free the keys and we pass 0 for free_values.
333 strmap_func(&opti
->conflicted
, 0);
336 * opti->paths_to_free is similar to opti->paths; we created it with
337 * strdup_strings = 0 to avoid making _another_ copy of the fullpath
338 * but now that we've used it and have no other references to these
339 * strings, it is time to deallocate them. We do so by temporarily
340 * setting strdup_strings to 1.
342 opti
->paths_to_free
.strdup_strings
= 1;
343 string_list_clear(&opti
->paths_to_free
, 0);
344 opti
->paths_to_free
.strdup_strings
= 0;
346 /* Free memory used by various renames maps */
347 for (i
= MERGE_SIDE1
; i
<= MERGE_SIDE2
; ++i
) {
348 struct hashmap_iter iter
;
349 struct strmap_entry
*entry
;
351 strset_func(&renames
->dirs_removed
[i
]);
353 strmap_for_each_entry(&renames
->dir_rename_count
[i
],
355 struct strintmap
*counts
= entry
->value
;
356 strintmap_clear(counts
);
358 strmap_func(&renames
->dir_rename_count
[i
], 1);
360 strmap_func(&renames
->dir_renames
[i
], 0);
364 struct hashmap_iter iter
;
365 struct strmap_entry
*e
;
367 /* Release and free each strbuf found in output */
368 strmap_for_each_entry(&opti
->output
, &iter
, e
) {
369 struct strbuf
*sb
= e
->value
;
372 * While strictly speaking we don't need to free(sb)
373 * here because we could pass free_values=1 when
374 * calling strmap_clear() on opti->output, that would
375 * require strmap_clear to do another
376 * strmap_for_each_entry() loop, so we just free it
377 * while we're iterating anyway.
381 strmap_clear(&opti
->output
, 0);
385 static int err(struct merge_options
*opt
, const char *err
, ...)
388 struct strbuf sb
= STRBUF_INIT
;
390 strbuf_addstr(&sb
, "error: ");
391 va_start(params
, err
);
392 strbuf_vaddf(&sb
, err
, params
);
401 __attribute__((format (printf
, 4, 5)))
402 static void path_msg(struct merge_options
*opt
,
404 int omittable_hint
, /* skippable under --remerge-diff */
405 const char *fmt
, ...)
408 struct strbuf
*sb
= strmap_get(&opt
->priv
->output
, path
);
410 sb
= xmalloc(sizeof(*sb
));
412 strmap_put(&opt
->priv
->output
, path
, sb
);
416 strbuf_vaddf(sb
, fmt
, ap
);
419 strbuf_addch(sb
, '\n');
422 /*** Function Grouping: functions related to collect_merge_info() ***/
424 static void setup_path_info(struct merge_options
*opt
,
425 struct string_list_item
*result
,
426 const char *current_dir_name
,
427 int current_dir_name_len
,
428 char *fullpath
, /* we'll take over ownership */
429 struct name_entry
*names
,
430 struct name_entry
*merged_version
,
431 unsigned is_null
, /* boolean */
432 unsigned df_conflict
, /* boolean */
435 int resolved
/* boolean */)
437 /* result->util is void*, so mi is a convenience typed variable */
438 struct merged_info
*mi
;
440 assert(!is_null
|| resolved
);
441 assert(!df_conflict
|| !resolved
); /* df_conflict implies !resolved */
442 assert(resolved
== (merged_version
!= NULL
));
444 mi
= xcalloc(1, resolved
? sizeof(struct merged_info
) :
445 sizeof(struct conflict_info
));
446 mi
->directory_name
= current_dir_name
;
447 mi
->basename_offset
= current_dir_name_len
;
448 mi
->clean
= !!resolved
;
450 mi
->result
.mode
= merged_version
->mode
;
451 oidcpy(&mi
->result
.oid
, &merged_version
->oid
);
452 mi
->is_null
= !!is_null
;
455 struct conflict_info
*ci
;
457 ASSIGN_AND_VERIFY_CI(ci
, mi
);
458 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
459 ci
->pathnames
[i
] = fullpath
;
460 ci
->stages
[i
].mode
= names
[i
].mode
;
461 oidcpy(&ci
->stages
[i
].oid
, &names
[i
].oid
);
463 ci
->filemask
= filemask
;
464 ci
->dirmask
= dirmask
;
465 ci
->df_conflict
= !!df_conflict
;
468 * Assume is_null for now, but if we have entries
469 * under the directory then when it is complete in
470 * write_completed_directory() it'll update this.
471 * Also, for D/F conflicts, we have to handle the
472 * directory first, then clear this bit and process
473 * the file to see how it is handled -- that occurs
474 * near the top of process_entry().
478 strmap_put(&opt
->priv
->paths
, fullpath
, mi
);
479 result
->string
= fullpath
;
483 static int collect_merge_info_callback(int n
,
485 unsigned long dirmask
,
486 struct name_entry
*names
,
487 struct traverse_info
*info
)
491 * common ancestor (mbase) has mask 1, and stored in index 0 of names
492 * head of side 1 (side1) has mask 2, and stored in index 1 of names
493 * head of side 2 (side2) has mask 4, and stored in index 2 of names
495 struct merge_options
*opt
= info
->data
;
496 struct merge_options_internal
*opti
= opt
->priv
;
497 struct string_list_item pi
; /* Path Info */
498 struct conflict_info
*ci
; /* typed alias to pi.util (which is void*) */
499 struct name_entry
*p
;
502 const char *dirname
= opti
->current_dir_name
;
503 unsigned filemask
= mask
& ~dirmask
;
504 unsigned match_mask
= 0; /* will be updated below */
505 unsigned mbase_null
= !(mask
& 1);
506 unsigned side1_null
= !(mask
& 2);
507 unsigned side2_null
= !(mask
& 4);
508 unsigned side1_matches_mbase
= (!side1_null
&& !mbase_null
&&
509 names
[0].mode
== names
[1].mode
&&
510 oideq(&names
[0].oid
, &names
[1].oid
));
511 unsigned side2_matches_mbase
= (!side2_null
&& !mbase_null
&&
512 names
[0].mode
== names
[2].mode
&&
513 oideq(&names
[0].oid
, &names
[2].oid
));
514 unsigned sides_match
= (!side1_null
&& !side2_null
&&
515 names
[1].mode
== names
[2].mode
&&
516 oideq(&names
[1].oid
, &names
[2].oid
));
519 * Note: When a path is a file on one side of history and a directory
520 * in another, we have a directory/file conflict. In such cases, if
521 * the conflict doesn't resolve from renames and deletions, then we
522 * always leave directories where they are and move files out of the
523 * way. Thus, while struct conflict_info has a df_conflict field to
524 * track such conflicts, we ignore that field for any directories at
525 * a path and only pay attention to it for files at the given path.
526 * The fact that we leave directories were they are also means that
527 * we do not need to worry about getting additional df_conflict
528 * information propagated from parent directories down to children
529 * (unlike, say traverse_trees_recursive() in unpack-trees.c, which
530 * sets a newinfo.df_conflicts field specifically to propagate it).
532 unsigned df_conflict
= (filemask
!= 0) && (dirmask
!= 0);
534 /* n = 3 is a fundamental assumption. */
536 BUG("Called collect_merge_info_callback wrong");
539 * A bunch of sanity checks verifying that traverse_trees() calls
540 * us the way I expect. Could just remove these at some point,
541 * though maybe they are helpful to future code readers.
543 assert(mbase_null
== is_null_oid(&names
[0].oid
));
544 assert(side1_null
== is_null_oid(&names
[1].oid
));
545 assert(side2_null
== is_null_oid(&names
[2].oid
));
546 assert(!mbase_null
|| !side1_null
|| !side2_null
);
547 assert(mask
> 0 && mask
< 8);
549 /* Determine match_mask */
550 if (side1_matches_mbase
)
551 match_mask
= (side2_matches_mbase
? 7 : 3);
552 else if (side2_matches_mbase
)
554 else if (sides_match
)
558 * Get the name of the relevant filepath, which we'll pass to
559 * setup_path_info() for tracking.
564 len
= traverse_path_len(info
, p
->pathlen
);
566 /* +1 in both of the following lines to include the NUL byte */
567 fullpath
= xmalloc(len
+ 1);
568 make_traverse_path(fullpath
, len
+ 1, info
, p
->path
, p
->pathlen
);
571 * If mbase, side1, and side2 all match, we can resolve early. Even
572 * if these are trees, there will be no renames or anything
575 if (side1_matches_mbase
&& side2_matches_mbase
) {
576 /* mbase, side1, & side2 all match; use mbase as resolution */
577 setup_path_info(opt
, &pi
, dirname
, info
->pathlen
, fullpath
,
578 names
, names
+0, mbase_null
, 0,
579 filemask
, dirmask
, 1);
584 * Record information about the path so we can resolve later in
587 setup_path_info(opt
, &pi
, dirname
, info
->pathlen
, fullpath
,
588 names
, NULL
, 0, df_conflict
, filemask
, dirmask
, 0);
592 ci
->match_mask
= match_mask
;
594 /* If dirmask, recurse into subdirectories */
596 struct traverse_info newinfo
;
597 struct tree_desc t
[3];
598 void *buf
[3] = {NULL
, NULL
, NULL
};
599 const char *original_dir_name
;
602 ci
->match_mask
&= filemask
;
605 newinfo
.name
= p
->path
;
606 newinfo
.namelen
= p
->pathlen
;
607 newinfo
.pathlen
= st_add3(newinfo
.pathlen
, p
->pathlen
, 1);
609 * If this directory we are about to recurse into cared about
610 * its parent directory (the current directory) having a D/F
611 * conflict, then we'd propagate the masks in this way:
612 * newinfo.df_conflicts |= (mask & ~dirmask);
613 * But we don't worry about propagating D/F conflicts. (See
614 * comment near setting of local df_conflict variable near
615 * the beginning of this function).
618 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
619 if (i
== 1 && side1_matches_mbase
)
621 else if (i
== 2 && side2_matches_mbase
)
623 else if (i
== 2 && sides_match
)
626 const struct object_id
*oid
= NULL
;
629 buf
[i
] = fill_tree_descriptor(opt
->repo
,
635 original_dir_name
= opti
->current_dir_name
;
636 opti
->current_dir_name
= pi
.string
;
637 ret
= traverse_trees(NULL
, 3, t
, &newinfo
);
638 opti
->current_dir_name
= original_dir_name
;
640 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++)
650 static int collect_merge_info(struct merge_options
*opt
,
651 struct tree
*merge_base
,
656 struct tree_desc t
[3];
657 struct traverse_info info
;
658 const char *toplevel_dir_placeholder
= "";
660 opt
->priv
->current_dir_name
= toplevel_dir_placeholder
;
661 setup_traverse_info(&info
, toplevel_dir_placeholder
);
662 info
.fn
= collect_merge_info_callback
;
664 info
.show_all_errors
= 1;
666 parse_tree(merge_base
);
669 init_tree_desc(t
+ 0, merge_base
->buffer
, merge_base
->size
);
670 init_tree_desc(t
+ 1, side1
->buffer
, side1
->size
);
671 init_tree_desc(t
+ 2, side2
->buffer
, side2
->size
);
673 ret
= traverse_trees(NULL
, 3, t
, &info
);
678 /*** Function Grouping: functions related to threeway content merges ***/
680 static int handle_content_merge(struct merge_options
*opt
,
682 const struct version_info
*o
,
683 const struct version_info
*a
,
684 const struct version_info
*b
,
685 const char *pathnames
[3],
686 const int extra_marker_size
,
687 struct version_info
*result
)
689 die("Not yet implemented");
692 /*** Function Grouping: functions related to detect_and_process_renames(), ***
693 *** which are split into directory and regular rename detection sections. ***/
695 /*** Function Grouping: functions related to directory rename detection ***/
697 /*** Function Grouping: functions related to regular rename detection ***/
699 static int process_renames(struct merge_options
*opt
,
700 struct diff_queue_struct
*renames
)
702 int clean_merge
= 1, i
;
704 for (i
= 0; i
< renames
->nr
; ++i
) {
705 const char *oldpath
= NULL
, *newpath
;
706 struct diff_filepair
*pair
= renames
->queue
[i
];
707 struct conflict_info
*oldinfo
= NULL
, *newinfo
= NULL
;
708 struct strmap_entry
*old_ent
, *new_ent
;
709 unsigned int old_sidemask
;
710 int target_index
, other_source_index
;
711 int source_deleted
, collision
, type_changed
;
712 const char *rename_branch
= NULL
, *delete_branch
= NULL
;
714 old_ent
= strmap_get_entry(&opt
->priv
->paths
, pair
->one
->path
);
715 oldpath
= old_ent
->key
;
716 oldinfo
= old_ent
->value
;
718 new_ent
= strmap_get_entry(&opt
->priv
->paths
, pair
->two
->path
);
719 newpath
= new_ent
->key
;
720 newinfo
= new_ent
->value
;
723 * diff_filepairs have copies of pathnames, thus we have to
724 * use standard 'strcmp()' (negated) instead of '=='.
726 if (i
+ 1 < renames
->nr
&&
727 !strcmp(oldpath
, renames
->queue
[i
+1]->one
->path
)) {
728 /* Handle rename/rename(1to2) or rename/rename(1to1) */
729 const char *pathnames
[3];
730 struct version_info merged
;
731 struct conflict_info
*base
, *side1
, *side2
;
732 unsigned was_binary_blob
= 0;
734 pathnames
[0] = oldpath
;
735 pathnames
[1] = newpath
;
736 pathnames
[2] = renames
->queue
[i
+1]->two
->path
;
738 base
= strmap_get(&opt
->priv
->paths
, pathnames
[0]);
739 side1
= strmap_get(&opt
->priv
->paths
, pathnames
[1]);
740 side2
= strmap_get(&opt
->priv
->paths
, pathnames
[2]);
746 if (!strcmp(pathnames
[1], pathnames
[2])) {
747 /* Both sides renamed the same way */
748 assert(side1
== side2
);
749 memcpy(&side1
->stages
[0], &base
->stages
[0],
751 side1
->filemask
|= (1 << MERGE_BASE
);
752 /* Mark base as resolved by removal */
753 base
->merged
.is_null
= 1;
754 base
->merged
.clean
= 1;
756 /* We handled both renames, i.e. i+1 handled */
758 /* Move to next rename */
762 /* This is a rename/rename(1to2) */
763 clean_merge
= handle_content_merge(opt
,
769 1 + 2 * opt
->priv
->call_depth
,
772 merged
.mode
== side1
->stages
[1].mode
&&
773 oideq(&merged
.oid
, &side1
->stages
[1].oid
))
775 memcpy(&side1
->stages
[1], &merged
, sizeof(merged
));
776 if (was_binary_blob
) {
778 * Getting here means we were attempting to
779 * merge a binary blob.
781 * Since we can't merge binaries,
782 * handle_content_merge() just takes one
783 * side. But we don't want to copy the
784 * contents of one side to both paths. We
785 * used the contents of side1 above for
786 * side1->stages, let's use the contents of
787 * side2 for side2->stages below.
789 oidcpy(&merged
.oid
, &side2
->stages
[2].oid
);
790 merged
.mode
= side2
->stages
[2].mode
;
792 memcpy(&side2
->stages
[2], &merged
, sizeof(merged
));
794 side1
->path_conflict
= 1;
795 side2
->path_conflict
= 1;
797 * TODO: For renames we normally remove the path at the
798 * old name. It would thus seem consistent to do the
799 * same for rename/rename(1to2) cases, but we haven't
800 * done so traditionally and a number of the regression
801 * tests now encode an expectation that the file is
802 * left there at stage 1. If we ever decide to change
803 * this, add the following two lines here:
804 * base->merged.is_null = 1;
805 * base->merged.clean = 1;
806 * and remove the setting of base->path_conflict to 1.
808 base
->path_conflict
= 1;
809 path_msg(opt
, oldpath
, 0,
810 _("CONFLICT (rename/rename): %s renamed to "
811 "%s in %s and to %s in %s."),
813 pathnames
[1], opt
->branch1
,
814 pathnames
[2], opt
->branch2
);
816 i
++; /* We handled both renames, i.e. i+1 handled */
822 target_index
= pair
->score
; /* from collect_renames() */
823 assert(target_index
== 1 || target_index
== 2);
824 other_source_index
= 3 - target_index
;
825 old_sidemask
= (1 << other_source_index
); /* 2 or 4 */
826 source_deleted
= (oldinfo
->filemask
== 1);
827 collision
= ((newinfo
->filemask
& old_sidemask
) != 0);
828 type_changed
= !source_deleted
&&
829 (S_ISREG(oldinfo
->stages
[other_source_index
].mode
) !=
830 S_ISREG(newinfo
->stages
[target_index
].mode
));
831 if (type_changed
&& collision
) {
833 * special handling so later blocks can handle this...
835 * if type_changed && collision are both true, then this
836 * was really a double rename, but one side wasn't
837 * detected due to lack of break detection. I.e.
839 * orig: has normal file 'foo'
840 * side1: renames 'foo' to 'bar', adds 'foo' symlink
841 * side2: renames 'foo' to 'bar'
842 * In this case, the foo->bar rename on side1 won't be
843 * detected because the new symlink named 'foo' is
844 * there and we don't do break detection. But we detect
845 * this here because we don't want to merge the content
846 * of the foo symlink with the foo->bar file, so we
847 * have some logic to handle this special case. The
848 * easiest way to do that is make 'bar' on side1 not
849 * be considered a colliding file but the other part
850 * of a normal rename. If the file is very different,
851 * well we're going to get content merge conflicts
852 * anyway so it doesn't hurt. And if the colliding
853 * file also has a different type, that'll be handled
854 * by the content merge logic in process_entry() too.
856 * See also t6430, 'rename vs. rename/symlink'
860 if (source_deleted
) {
861 if (target_index
== 1) {
862 rename_branch
= opt
->branch1
;
863 delete_branch
= opt
->branch2
;
865 rename_branch
= opt
->branch2
;
866 delete_branch
= opt
->branch1
;
870 assert(source_deleted
|| oldinfo
->filemask
& old_sidemask
);
872 /* Need to check for special types of rename conflicts... */
873 if (collision
&& !source_deleted
) {
874 /* collision: rename/add or rename/rename(2to1) */
875 const char *pathnames
[3];
876 struct version_info merged
;
878 struct conflict_info
*base
, *side1
, *side2
;
881 pathnames
[0] = oldpath
;
882 pathnames
[other_source_index
] = oldpath
;
883 pathnames
[target_index
] = newpath
;
885 base
= strmap_get(&opt
->priv
->paths
, pathnames
[0]);
886 side1
= strmap_get(&opt
->priv
->paths
, pathnames
[1]);
887 side2
= strmap_get(&opt
->priv
->paths
, pathnames
[2]);
893 clean
= handle_content_merge(opt
, pair
->one
->path
,
898 1 + 2 * opt
->priv
->call_depth
,
901 memcpy(&newinfo
->stages
[target_index
], &merged
,
904 path_msg(opt
, newpath
, 0,
905 _("CONFLICT (rename involved in "
906 "collision): rename of %s -> %s has "
907 "content conflicts AND collides "
908 "with another path; this may result "
909 "in nested conflict markers."),
912 } else if (collision
&& source_deleted
) {
914 * rename/add/delete or rename/rename(2to1)/delete:
915 * since oldpath was deleted on the side that didn't
916 * do the rename, there's not much of a content merge
917 * we can do for the rename. oldinfo->merged.is_null
918 * was already set, so we just leave things as-is so
919 * they look like an add/add conflict.
922 newinfo
->path_conflict
= 1;
923 path_msg(opt
, newpath
, 0,
924 _("CONFLICT (rename/delete): %s renamed "
925 "to %s in %s, but deleted in %s."),
926 oldpath
, newpath
, rename_branch
, delete_branch
);
929 * a few different cases...start by copying the
930 * existing stage(s) from oldinfo over the newinfo
931 * and update the pathname(s).
933 memcpy(&newinfo
->stages
[0], &oldinfo
->stages
[0],
934 sizeof(newinfo
->stages
[0]));
935 newinfo
->filemask
|= (1 << MERGE_BASE
);
936 newinfo
->pathnames
[0] = oldpath
;
938 /* rename vs. typechange */
939 /* Mark the original as resolved by removal */
940 memcpy(&oldinfo
->stages
[0].oid
, &null_oid
,
941 sizeof(oldinfo
->stages
[0].oid
));
942 oldinfo
->stages
[0].mode
= 0;
943 oldinfo
->filemask
&= 0x06;
944 } else if (source_deleted
) {
946 newinfo
->path_conflict
= 1;
947 path_msg(opt
, newpath
, 0,
948 _("CONFLICT (rename/delete): %s renamed"
949 " to %s in %s, but deleted in %s."),
951 rename_branch
, delete_branch
);
954 memcpy(&newinfo
->stages
[other_source_index
],
955 &oldinfo
->stages
[other_source_index
],
956 sizeof(newinfo
->stages
[0]));
957 newinfo
->filemask
|= (1 << other_source_index
);
958 newinfo
->pathnames
[other_source_index
] = oldpath
;
963 /* Mark the original as resolved by removal */
964 oldinfo
->merged
.is_null
= 1;
965 oldinfo
->merged
.clean
= 1;
973 static int compare_pairs(const void *a_
, const void *b_
)
975 const struct diff_filepair
*a
= *((const struct diff_filepair
**)a_
);
976 const struct diff_filepair
*b
= *((const struct diff_filepair
**)b_
);
978 return strcmp(a
->one
->path
, b
->one
->path
);
981 /* Call diffcore_rename() to compute which files have changed on given side */
982 static void detect_regular_renames(struct merge_options
*opt
,
983 struct tree
*merge_base
,
987 struct diff_options diff_opts
;
988 struct rename_info
*renames
= &opt
->priv
->renames
;
990 repo_diff_setup(opt
->repo
, &diff_opts
);
991 diff_opts
.flags
.recursive
= 1;
992 diff_opts
.flags
.rename_empty
= 0;
993 diff_opts
.detect_rename
= DIFF_DETECT_RENAME
;
994 diff_opts
.rename_limit
= opt
->rename_limit
;
995 if (opt
->rename_limit
<= 0)
996 diff_opts
.rename_limit
= 1000;
997 diff_opts
.rename_score
= opt
->rename_score
;
998 diff_opts
.show_rename_progress
= opt
->show_rename_progress
;
999 diff_opts
.output_format
= DIFF_FORMAT_NO_OUTPUT
;
1000 diff_setup_done(&diff_opts
);
1001 diff_tree_oid(&merge_base
->object
.oid
, &side
->object
.oid
, "",
1003 diffcore_std(&diff_opts
);
1005 if (diff_opts
.needed_rename_limit
> renames
->needed_limit
)
1006 renames
->needed_limit
= diff_opts
.needed_rename_limit
;
1008 renames
->pairs
[side_index
] = diff_queued_diff
;
1010 diff_opts
.output_format
= DIFF_FORMAT_NO_OUTPUT
;
1011 diff_queued_diff
.nr
= 0;
1012 diff_queued_diff
.queue
= NULL
;
1013 diff_flush(&diff_opts
);
1017 * Get information of all renames which occurred in 'side_pairs', discarding
1020 static int collect_renames(struct merge_options
*opt
,
1021 struct diff_queue_struct
*result
,
1022 unsigned side_index
)
1025 struct diff_queue_struct
*side_pairs
;
1026 struct rename_info
*renames
= &opt
->priv
->renames
;
1028 side_pairs
= &renames
->pairs
[side_index
];
1030 for (i
= 0; i
< side_pairs
->nr
; ++i
) {
1031 struct diff_filepair
*p
= side_pairs
->queue
[i
];
1033 if (p
->status
!= 'R') {
1034 diff_free_filepair(p
);
1039 * p->score comes back from diffcore_rename_extended() with
1040 * the similarity of the renamed file. The similarity is
1041 * was used to determine that the two files were related
1042 * and are a rename, which we have already used, but beyond
1043 * that we have no use for the similarity. So p->score is
1044 * now irrelevant. However, process_renames() will need to
1045 * know which side of the merge this rename was associated
1046 * with, so overwrite p->score with that value.
1048 p
->score
= side_index
;
1049 result
->queue
[result
->nr
++] = p
;
1055 static int detect_and_process_renames(struct merge_options
*opt
,
1056 struct tree
*merge_base
,
1060 struct diff_queue_struct combined
;
1061 struct rename_info
*renames
= &opt
->priv
->renames
;
1064 memset(&combined
, 0, sizeof(combined
));
1066 detect_regular_renames(opt
, merge_base
, side1
, MERGE_SIDE1
);
1067 detect_regular_renames(opt
, merge_base
, side2
, MERGE_SIDE2
);
1069 ALLOC_GROW(combined
.queue
,
1070 renames
->pairs
[1].nr
+ renames
->pairs
[2].nr
,
1072 clean
&= collect_renames(opt
, &combined
, MERGE_SIDE1
);
1073 clean
&= collect_renames(opt
, &combined
, MERGE_SIDE2
);
1074 QSORT(combined
.queue
, combined
.nr
, compare_pairs
);
1076 clean
&= process_renames(opt
, &combined
);
1078 /* Free memory for renames->pairs[] and combined */
1079 for (s
= MERGE_SIDE1
; s
<= MERGE_SIDE2
; s
++) {
1080 free(renames
->pairs
[s
].queue
);
1081 DIFF_QUEUE_CLEAR(&renames
->pairs
[s
]);
1085 for (i
= 0; i
< combined
.nr
; i
++)
1086 diff_free_filepair(combined
.queue
[i
]);
1087 free(combined
.queue
);
1093 /*** Function Grouping: functions related to process_entries() ***/
1095 static int string_list_df_name_compare(const char *one
, const char *two
)
1097 int onelen
= strlen(one
);
1098 int twolen
= strlen(two
);
1100 * Here we only care that entries for D/F conflicts are
1101 * adjacent, in particular with the file of the D/F conflict
1102 * appearing before files below the corresponding directory.
1103 * The order of the rest of the list is irrelevant for us.
1105 * To achieve this, we sort with df_name_compare and provide
1106 * the mode S_IFDIR so that D/F conflicts will sort correctly.
1107 * We use the mode S_IFDIR for everything else for simplicity,
1108 * since in other cases any changes in their order due to
1109 * sorting cause no problems for us.
1111 int cmp
= df_name_compare(one
, onelen
, S_IFDIR
,
1112 two
, twolen
, S_IFDIR
);
1114 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
1115 * that 'foo' comes before 'foo/bar'.
1119 return onelen
- twolen
;
1122 struct directory_versions
{
1124 * versions: list of (basename -> version_info)
1126 * The basenames are in reverse lexicographic order of full pathnames,
1127 * as processed in process_entries(). This puts all entries within
1128 * a directory together, and covers the directory itself after
1129 * everything within it, allowing us to write subtrees before needing
1130 * to record information for the tree itself.
1132 struct string_list versions
;
1135 * offsets: list of (full relative path directories -> integer offsets)
1137 * Since versions contains basenames from files in multiple different
1138 * directories, we need to know which entries in versions correspond
1139 * to which directories. Values of e.g.
1143 * Would mean that entries 0-1 of versions are files in the toplevel
1144 * directory, entries 2-4 are files under src/, and the remaining
1145 * entries starting at index 5 are files under src/moduleA/.
1147 struct string_list offsets
;
1150 * last_directory: directory that previously processed file found in
1152 * last_directory starts NULL, but records the directory in which the
1153 * previous file was found within. As soon as
1154 * directory(current_file) != last_directory
1155 * then we need to start updating accounting in versions & offsets.
1156 * Note that last_directory is always the last path in "offsets" (or
1157 * NULL if "offsets" is empty) so this exists just for quick access.
1159 const char *last_directory
;
1161 /* last_directory_len: cached computation of strlen(last_directory) */
1162 unsigned last_directory_len
;
1165 static int tree_entry_order(const void *a_
, const void *b_
)
1167 const struct string_list_item
*a
= a_
;
1168 const struct string_list_item
*b
= b_
;
1170 const struct merged_info
*ami
= a
->util
;
1171 const struct merged_info
*bmi
= b
->util
;
1172 return base_name_compare(a
->string
, strlen(a
->string
), ami
->result
.mode
,
1173 b
->string
, strlen(b
->string
), bmi
->result
.mode
);
1176 static void write_tree(struct object_id
*result_oid
,
1177 struct string_list
*versions
,
1178 unsigned int offset
,
1181 size_t maxlen
= 0, extra
;
1182 unsigned int nr
= versions
->nr
- offset
;
1183 struct strbuf buf
= STRBUF_INIT
;
1184 struct string_list relevant_entries
= STRING_LIST_INIT_NODUP
;
1188 * We want to sort the last (versions->nr-offset) entries in versions.
1189 * Do so by abusing the string_list API a bit: make another string_list
1190 * that contains just those entries and then sort them.
1192 * We won't use relevant_entries again and will let it just pop off the
1193 * stack, so there won't be allocation worries or anything.
1195 relevant_entries
.items
= versions
->items
+ offset
;
1196 relevant_entries
.nr
= versions
->nr
- offset
;
1197 QSORT(relevant_entries
.items
, relevant_entries
.nr
, tree_entry_order
);
1199 /* Pre-allocate some space in buf */
1200 extra
= hash_size
+ 8; /* 8: 6 for mode, 1 for space, 1 for NUL char */
1201 for (i
= 0; i
< nr
; i
++) {
1202 maxlen
+= strlen(versions
->items
[offset
+i
].string
) + extra
;
1204 strbuf_grow(&buf
, maxlen
);
1206 /* Write each entry out to buf */
1207 for (i
= 0; i
< nr
; i
++) {
1208 struct merged_info
*mi
= versions
->items
[offset
+i
].util
;
1209 struct version_info
*ri
= &mi
->result
;
1210 strbuf_addf(&buf
, "%o %s%c",
1212 versions
->items
[offset
+i
].string
, '\0');
1213 strbuf_add(&buf
, ri
->oid
.hash
, hash_size
);
1216 /* Write this object file out, and record in result_oid */
1217 write_object_file(buf
.buf
, buf
.len
, tree_type
, result_oid
);
1218 strbuf_release(&buf
);
1221 static void record_entry_for_tree(struct directory_versions
*dir_metadata
,
1223 struct merged_info
*mi
)
1225 const char *basename
;
1228 /* nothing to record */
1231 basename
= path
+ mi
->basename_offset
;
1232 assert(strchr(basename
, '/') == NULL
);
1233 string_list_append(&dir_metadata
->versions
,
1234 basename
)->util
= &mi
->result
;
1237 static void write_completed_directory(struct merge_options
*opt
,
1238 const char *new_directory_name
,
1239 struct directory_versions
*info
)
1241 const char *prev_dir
;
1242 struct merged_info
*dir_info
= NULL
;
1243 unsigned int offset
;
1246 * Some explanation of info->versions and info->offsets...
1248 * process_entries() iterates over all relevant files AND
1249 * directories in reverse lexicographic order, and calls this
1250 * function. Thus, an example of the paths that process_entries()
1251 * could operate on (along with the directories for those paths
1256 * src/moduleB/umm.c src/moduleB
1257 * src/moduleB/stuff.h src/moduleB
1258 * src/moduleB/baz.c src/moduleB
1260 * src/moduleA/foo.c src/moduleA
1261 * src/moduleA/bar.c src/moduleA
1268 * always contains the unprocessed entries and their
1269 * version_info information. For example, after the first five
1270 * entries above, info->versions would be:
1272 * xtract.c <xtract.c's version_info>
1273 * token.txt <token.txt's version_info>
1274 * umm.c <src/moduleB/umm.c's version_info>
1275 * stuff.h <src/moduleB/stuff.h's version_info>
1276 * baz.c <src/moduleB/baz.c's version_info>
1278 * Once a subdirectory is completed we remove the entries in
1279 * that subdirectory from info->versions, writing it as a tree
1280 * (write_tree()). Thus, as soon as we get to src/moduleB,
1281 * info->versions would be updated to
1283 * xtract.c <xtract.c's version_info>
1284 * token.txt <token.txt's version_info>
1285 * moduleB <src/moduleB's version_info>
1289 * helps us track which entries in info->versions correspond to
1290 * which directories. When we are N directories deep (e.g. 4
1291 * for src/modA/submod/subdir/), we have up to N+1 unprocessed
1292 * directories (+1 because of toplevel dir). Corresponding to
1293 * the info->versions example above, after processing five entries
1294 * info->offsets will be:
1299 * which is used to know that xtract.c & token.txt are from the
1300 * toplevel dirctory, while umm.c & stuff.h & baz.c are from the
1301 * src/moduleB directory. Again, following the example above,
1302 * once we need to process src/moduleB, then info->offsets is
1308 * which says that moduleB (and only moduleB so far) is in the
1311 * One unique thing to note about info->offsets here is that
1312 * "src" was not added to info->offsets until there was a path
1313 * (a file OR directory) immediately below src/ that got
1316 * Since process_entry() just appends new entries to info->versions,
1317 * write_completed_directory() only needs to do work if the next path
1318 * is in a directory that is different than the last directory found
1323 * If we are working with the same directory as the last entry, there
1324 * is no work to do. (See comments above the directory_name member of
1325 * struct merged_info for why we can use pointer comparison instead of
1328 if (new_directory_name
== info
->last_directory
)
1332 * If we are just starting (last_directory is NULL), or last_directory
1333 * is a prefix of the current directory, then we can just update
1334 * info->offsets to record the offset where we started this directory
1335 * and update last_directory to have quick access to it.
1337 if (info
->last_directory
== NULL
||
1338 !strncmp(new_directory_name
, info
->last_directory
,
1339 info
->last_directory_len
)) {
1340 uintptr_t offset
= info
->versions
.nr
;
1342 info
->last_directory
= new_directory_name
;
1343 info
->last_directory_len
= strlen(info
->last_directory
);
1345 * Record the offset into info->versions where we will
1346 * start recording basenames of paths found within
1347 * new_directory_name.
1349 string_list_append(&info
->offsets
,
1350 info
->last_directory
)->util
= (void*)offset
;
1355 * The next entry that will be processed will be within
1356 * new_directory_name. Since at this point we know that
1357 * new_directory_name is within a different directory than
1358 * info->last_directory, we have all entries for info->last_directory
1359 * in info->versions and we need to create a tree object for them.
1361 dir_info
= strmap_get(&opt
->priv
->paths
, info
->last_directory
);
1363 offset
= (uintptr_t)info
->offsets
.items
[info
->offsets
.nr
-1].util
;
1364 if (offset
== info
->versions
.nr
) {
1366 * Actually, we don't need to create a tree object in this
1367 * case. Whenever all files within a directory disappear
1368 * during the merge (e.g. unmodified on one side and
1369 * deleted on the other, or files were renamed elsewhere),
1370 * then we get here and the directory itself needs to be
1371 * omitted from its parent tree as well.
1373 dir_info
->is_null
= 1;
1376 * Write out the tree to the git object directory, and also
1377 * record the mode and oid in dir_info->result.
1379 dir_info
->is_null
= 0;
1380 dir_info
->result
.mode
= S_IFDIR
;
1381 write_tree(&dir_info
->result
.oid
, &info
->versions
, offset
,
1382 opt
->repo
->hash_algo
->rawsz
);
1386 * We've now used several entries from info->versions and one entry
1387 * from info->offsets, so we get rid of those values.
1390 info
->versions
.nr
= offset
;
1393 * Now we've taken care of the completed directory, but we need to
1394 * prepare things since future entries will be in
1395 * new_directory_name. (In particular, process_entry() will be
1396 * appending new entries to info->versions.) So, we need to make
1397 * sure new_directory_name is the last entry in info->offsets.
1399 prev_dir
= info
->offsets
.nr
== 0 ? NULL
:
1400 info
->offsets
.items
[info
->offsets
.nr
-1].string
;
1401 if (new_directory_name
!= prev_dir
) {
1402 uintptr_t c
= info
->versions
.nr
;
1403 string_list_append(&info
->offsets
,
1404 new_directory_name
)->util
= (void*)c
;
1407 /* And, of course, we need to update last_directory to match. */
1408 info
->last_directory
= new_directory_name
;
1409 info
->last_directory_len
= strlen(info
->last_directory
);
1412 /* Per entry merge function */
1413 static void process_entry(struct merge_options
*opt
,
1415 struct conflict_info
*ci
,
1416 struct directory_versions
*dir_metadata
)
1419 assert(ci
->filemask
>= 0 && ci
->filemask
<= 7);
1420 /* ci->match_mask == 7 was handled in collect_merge_info_callback() */
1421 assert(ci
->match_mask
== 0 || ci
->match_mask
== 3 ||
1422 ci
->match_mask
== 5 || ci
->match_mask
== 6);
1425 record_entry_for_tree(dir_metadata
, path
, &ci
->merged
);
1426 if (ci
->filemask
== 0)
1427 /* nothing else to handle */
1429 assert(ci
->df_conflict
);
1432 if (ci
->df_conflict
) {
1433 die("Not yet implemented.");
1437 * NOTE: Below there is a long switch-like if-elseif-elseif... block
1438 * which the code goes through even for the df_conflict cases
1439 * above. Well, it will once we don't die-not-implemented above.
1441 if (ci
->match_mask
) {
1442 ci
->merged
.clean
= 1;
1443 if (ci
->match_mask
== 6) {
1444 /* stages[1] == stages[2] */
1445 ci
->merged
.result
.mode
= ci
->stages
[1].mode
;
1446 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[1].oid
);
1448 /* determine the mask of the side that didn't match */
1449 unsigned int othermask
= 7 & ~ci
->match_mask
;
1450 int side
= (othermask
== 4) ? 2 : 1;
1452 ci
->merged
.result
.mode
= ci
->stages
[side
].mode
;
1453 ci
->merged
.is_null
= !ci
->merged
.result
.mode
;
1454 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[side
].oid
);
1456 assert(othermask
== 2 || othermask
== 4);
1457 assert(ci
->merged
.is_null
==
1458 (ci
->filemask
== ci
->match_mask
));
1460 } else if (ci
->filemask
>= 6 &&
1461 (S_IFMT
& ci
->stages
[1].mode
) !=
1462 (S_IFMT
& ci
->stages
[2].mode
)) {
1464 * Two different items from (file/submodule/symlink)
1466 die("Not yet implemented.");
1467 } else if (ci
->filemask
>= 6) {
1469 * TODO: Needs a two-way or three-way content merge, but we're
1470 * just being lazy and copying the version from HEAD and
1471 * leaving it as conflicted.
1473 ci
->merged
.clean
= 0;
1474 ci
->merged
.result
.mode
= ci
->stages
[1].mode
;
1475 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[1].oid
);
1476 /* When we fix above, we'll call handle_content_merge() */
1477 (void)handle_content_merge
;
1478 } else if (ci
->filemask
== 3 || ci
->filemask
== 5) {
1480 const char *modify_branch
, *delete_branch
;
1481 int side
= (ci
->filemask
== 5) ? 2 : 1;
1482 int index
= opt
->priv
->call_depth
? 0 : side
;
1484 ci
->merged
.result
.mode
= ci
->stages
[index
].mode
;
1485 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[index
].oid
);
1486 ci
->merged
.clean
= 0;
1488 modify_branch
= (side
== 1) ? opt
->branch1
: opt
->branch2
;
1489 delete_branch
= (side
== 1) ? opt
->branch2
: opt
->branch1
;
1491 if (ci
->path_conflict
&&
1492 oideq(&ci
->stages
[0].oid
, &ci
->stages
[side
].oid
)) {
1494 * This came from a rename/delete; no action to take,
1495 * but avoid printing "modify/delete" conflict notice
1496 * since the contents were not modified.
1499 path_msg(opt
, path
, 0,
1500 _("CONFLICT (modify/delete): %s deleted in %s "
1501 "and modified in %s. Version %s of %s left "
1503 path
, delete_branch
, modify_branch
,
1504 modify_branch
, path
);
1506 } else if (ci
->filemask
== 2 || ci
->filemask
== 4) {
1507 /* Added on one side */
1508 int side
= (ci
->filemask
== 4) ? 2 : 1;
1509 ci
->merged
.result
.mode
= ci
->stages
[side
].mode
;
1510 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[side
].oid
);
1511 ci
->merged
.clean
= !ci
->df_conflict
&& !ci
->path_conflict
;
1512 } else if (ci
->filemask
== 1) {
1513 /* Deleted on both sides */
1514 ci
->merged
.is_null
= 1;
1515 ci
->merged
.result
.mode
= 0;
1516 oidcpy(&ci
->merged
.result
.oid
, &null_oid
);
1517 ci
->merged
.clean
= !ci
->path_conflict
;
1521 * If still conflicted, record it separately. This allows us to later
1522 * iterate over just conflicted entries when updating the index instead
1523 * of iterating over all entries.
1525 if (!ci
->merged
.clean
)
1526 strmap_put(&opt
->priv
->conflicted
, path
, ci
);
1527 record_entry_for_tree(dir_metadata
, path
, &ci
->merged
);
1530 static void process_entries(struct merge_options
*opt
,
1531 struct object_id
*result_oid
)
1533 struct hashmap_iter iter
;
1534 struct strmap_entry
*e
;
1535 struct string_list plist
= STRING_LIST_INIT_NODUP
;
1536 struct string_list_item
*entry
;
1537 struct directory_versions dir_metadata
= { STRING_LIST_INIT_NODUP
,
1538 STRING_LIST_INIT_NODUP
,
1541 if (strmap_empty(&opt
->priv
->paths
)) {
1542 oidcpy(result_oid
, opt
->repo
->hash_algo
->empty_tree
);
1546 /* Hack to pre-allocate plist to the desired size */
1547 ALLOC_GROW(plist
.items
, strmap_get_size(&opt
->priv
->paths
), plist
.alloc
);
1549 /* Put every entry from paths into plist, then sort */
1550 strmap_for_each_entry(&opt
->priv
->paths
, &iter
, e
) {
1551 string_list_append(&plist
, e
->key
)->util
= e
->value
;
1553 plist
.cmp
= string_list_df_name_compare
;
1554 string_list_sort(&plist
);
1557 * Iterate over the items in reverse order, so we can handle paths
1558 * below a directory before needing to handle the directory itself.
1560 * This allows us to write subtrees before we need to write trees,
1561 * and it also enables sane handling of directory/file conflicts
1562 * (because it allows us to know whether the directory is still in
1563 * the way when it is time to process the file at the same path).
1565 for (entry
= &plist
.items
[plist
.nr
-1]; entry
>= plist
.items
; --entry
) {
1566 char *path
= entry
->string
;
1568 * NOTE: mi may actually be a pointer to a conflict_info, but
1569 * we have to check mi->clean first to see if it's safe to
1570 * reassign to such a pointer type.
1572 struct merged_info
*mi
= entry
->util
;
1574 write_completed_directory(opt
, mi
->directory_name
,
1577 record_entry_for_tree(&dir_metadata
, path
, mi
);
1579 struct conflict_info
*ci
= (struct conflict_info
*)mi
;
1580 process_entry(opt
, path
, ci
, &dir_metadata
);
1584 if (dir_metadata
.offsets
.nr
!= 1 ||
1585 (uintptr_t)dir_metadata
.offsets
.items
[0].util
!= 0) {
1586 printf("dir_metadata.offsets.nr = %d (should be 1)\n",
1587 dir_metadata
.offsets
.nr
);
1588 printf("dir_metadata.offsets.items[0].util = %u (should be 0)\n",
1589 (unsigned)(uintptr_t)dir_metadata
.offsets
.items
[0].util
);
1591 BUG("dir_metadata accounting completely off; shouldn't happen");
1593 write_tree(result_oid
, &dir_metadata
.versions
, 0,
1594 opt
->repo
->hash_algo
->rawsz
);
1595 string_list_clear(&plist
, 0);
1596 string_list_clear(&dir_metadata
.versions
, 0);
1597 string_list_clear(&dir_metadata
.offsets
, 0);
1600 /*** Function Grouping: functions related to merge_switch_to_result() ***/
1602 static int checkout(struct merge_options
*opt
,
1606 /* Switch the index/working copy from old to new */
1608 struct tree_desc trees
[2];
1609 struct unpack_trees_options unpack_opts
;
1611 memset(&unpack_opts
, 0, sizeof(unpack_opts
));
1612 unpack_opts
.head_idx
= -1;
1613 unpack_opts
.src_index
= opt
->repo
->index
;
1614 unpack_opts
.dst_index
= opt
->repo
->index
;
1616 setup_unpack_trees_porcelain(&unpack_opts
, "merge");
1619 * NOTE: if this were just "git checkout" code, we would probably
1620 * read or refresh the cache and check for a conflicted index, but
1621 * builtin/merge.c or sequencer.c really needs to read the index
1622 * and check for conflicted entries before starting merging for a
1623 * good user experience (no sense waiting for merges/rebases before
1624 * erroring out), so there's no reason to duplicate that work here.
1627 /* 2-way merge to the new branch */
1628 unpack_opts
.update
= 1;
1629 unpack_opts
.merge
= 1;
1630 unpack_opts
.quiet
= 0; /* FIXME: sequencer might want quiet? */
1631 unpack_opts
.verbose_update
= (opt
->verbosity
> 2);
1632 unpack_opts
.fn
= twoway_merge
;
1633 if (1/* FIXME: opts->overwrite_ignore*/) {
1634 unpack_opts
.dir
= xcalloc(1, sizeof(*unpack_opts
.dir
));
1635 unpack_opts
.dir
->flags
|= DIR_SHOW_IGNORED
;
1636 setup_standard_excludes(unpack_opts
.dir
);
1639 init_tree_desc(&trees
[0], prev
->buffer
, prev
->size
);
1641 init_tree_desc(&trees
[1], next
->buffer
, next
->size
);
1643 ret
= unpack_trees(2, trees
, &unpack_opts
);
1644 clear_unpack_trees_porcelain(&unpack_opts
);
1645 dir_clear(unpack_opts
.dir
);
1646 FREE_AND_NULL(unpack_opts
.dir
);
1650 static int record_conflicted_index_entries(struct merge_options
*opt
,
1651 struct index_state
*index
,
1652 struct strmap
*paths
,
1653 struct strmap
*conflicted
)
1655 struct hashmap_iter iter
;
1656 struct strmap_entry
*e
;
1658 int original_cache_nr
;
1660 if (strmap_empty(conflicted
))
1663 original_cache_nr
= index
->cache_nr
;
1665 /* Put every entry from paths into plist, then sort */
1666 strmap_for_each_entry(conflicted
, &iter
, e
) {
1667 const char *path
= e
->key
;
1668 struct conflict_info
*ci
= e
->value
;
1670 struct cache_entry
*ce
;
1676 * The index will already have a stage=0 entry for this path,
1677 * because we created an as-merged-as-possible version of the
1678 * file and checkout() moved the working copy and index over
1681 * However, previous iterations through this loop will have
1682 * added unstaged entries to the end of the cache which
1683 * ignore the standard alphabetical ordering of cache
1684 * entries and break invariants needed for index_name_pos()
1685 * to work. However, we know the entry we want is before
1686 * those appended cache entries, so do a temporary swap on
1687 * cache_nr to only look through entries of interest.
1689 SWAP(index
->cache_nr
, original_cache_nr
);
1690 pos
= index_name_pos(index
, path
, strlen(path
));
1691 SWAP(index
->cache_nr
, original_cache_nr
);
1693 if (ci
->filemask
!= 1)
1694 BUG("Conflicted %s but nothing in basic working tree or index; this shouldn't happen", path
);
1695 cache_tree_invalidate_path(index
, path
);
1697 ce
= index
->cache
[pos
];
1700 * Clean paths with CE_SKIP_WORKTREE set will not be
1701 * written to the working tree by the unpack_trees()
1702 * call in checkout(). Our conflicted entries would
1703 * have appeared clean to that code since we ignored
1704 * the higher order stages. Thus, we need override
1705 * the CE_SKIP_WORKTREE bit and manually write those
1706 * files to the working disk here.
1708 * TODO: Implement this CE_SKIP_WORKTREE fixup.
1712 * Mark this cache entry for removal and instead add
1713 * new stage>0 entries corresponding to the
1714 * conflicts. If there are many conflicted entries, we
1715 * want to avoid memmove'ing O(NM) entries by
1716 * inserting the new entries one at a time. So,
1717 * instead, we just add the new cache entries to the
1718 * end (ignoring normal index requirements on sort
1719 * order) and sort the index once we're all done.
1721 ce
->ce_flags
|= CE_REMOVE
;
1724 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
1725 struct version_info
*vi
;
1726 if (!(ci
->filemask
& (1ul << i
)))
1728 vi
= &ci
->stages
[i
];
1729 ce
= make_cache_entry(index
, vi
->mode
, &vi
->oid
,
1731 add_index_entry(index
, ce
, ADD_CACHE_JUST_APPEND
);
1736 * Remove the unused cache entries (and invalidate the relevant
1737 * cache-trees), then sort the index entries to get the conflicted
1738 * entries we added to the end into their right locations.
1740 remove_marked_cache_entries(index
, 1);
1741 QSORT(index
->cache
, index
->cache_nr
, cmp_cache_name_compare
);
1746 void merge_switch_to_result(struct merge_options
*opt
,
1748 struct merge_result
*result
,
1749 int update_worktree_and_index
,
1750 int display_update_msgs
)
1752 assert(opt
->priv
== NULL
);
1753 if (result
->clean
>= 0 && update_worktree_and_index
) {
1754 struct merge_options_internal
*opti
= result
->priv
;
1756 if (checkout(opt
, head
, result
->tree
)) {
1757 /* failure to function */
1762 if (record_conflicted_index_entries(opt
, opt
->repo
->index
,
1764 &opti
->conflicted
)) {
1765 /* failure to function */
1771 if (display_update_msgs
) {
1772 struct merge_options_internal
*opti
= result
->priv
;
1773 struct hashmap_iter iter
;
1774 struct strmap_entry
*e
;
1775 struct string_list olist
= STRING_LIST_INIT_NODUP
;
1778 /* Hack to pre-allocate olist to the desired size */
1779 ALLOC_GROW(olist
.items
, strmap_get_size(&opti
->output
),
1782 /* Put every entry from output into olist, then sort */
1783 strmap_for_each_entry(&opti
->output
, &iter
, e
) {
1784 string_list_append(&olist
, e
->key
)->util
= e
->value
;
1786 string_list_sort(&olist
);
1788 /* Iterate over the items, printing them */
1789 for (i
= 0; i
< olist
.nr
; ++i
) {
1790 struct strbuf
*sb
= olist
.items
[i
].util
;
1792 printf("%s", sb
->buf
);
1794 string_list_clear(&olist
, 0);
1796 /* Also include needed rename limit adjustment now */
1797 diff_warn_rename_limit("merge.renamelimit",
1798 opti
->renames
.needed_limit
, 0);
1801 merge_finalize(opt
, result
);
1804 void merge_finalize(struct merge_options
*opt
,
1805 struct merge_result
*result
)
1807 struct merge_options_internal
*opti
= result
->priv
;
1809 assert(opt
->priv
== NULL
);
1811 clear_or_reinit_internal_opts(opti
, 0);
1812 FREE_AND_NULL(opti
);
1815 /*** Function Grouping: helper functions for merge_incore_*() ***/
1817 static inline void set_commit_tree(struct commit
*c
, struct tree
*t
)
1822 static struct commit
*make_virtual_commit(struct repository
*repo
,
1824 const char *comment
)
1826 struct commit
*commit
= alloc_commit_node(repo
);
1828 set_merge_remote_desc(commit
, comment
, (struct object
*)commit
);
1829 set_commit_tree(commit
, tree
);
1830 commit
->object
.parsed
= 1;
1834 static void merge_start(struct merge_options
*opt
, struct merge_result
*result
)
1836 struct rename_info
*renames
;
1839 /* Sanity checks on opt */
1842 assert(opt
->branch1
&& opt
->branch2
);
1844 assert(opt
->detect_directory_renames
>= MERGE_DIRECTORY_RENAMES_NONE
&&
1845 opt
->detect_directory_renames
<= MERGE_DIRECTORY_RENAMES_TRUE
);
1846 assert(opt
->rename_limit
>= -1);
1847 assert(opt
->rename_score
>= 0 && opt
->rename_score
<= MAX_SCORE
);
1848 assert(opt
->show_rename_progress
>= 0 && opt
->show_rename_progress
<= 1);
1850 assert(opt
->xdl_opts
>= 0);
1851 assert(opt
->recursive_variant
>= MERGE_VARIANT_NORMAL
&&
1852 opt
->recursive_variant
<= MERGE_VARIANT_THEIRS
);
1855 * detect_renames, verbosity, buffer_output, and obuf are ignored
1856 * fields that were used by "recursive" rather than "ort" -- but
1857 * sanity check them anyway.
1859 assert(opt
->detect_renames
>= -1 &&
1860 opt
->detect_renames
<= DIFF_DETECT_COPY
);
1861 assert(opt
->verbosity
>= 0 && opt
->verbosity
<= 5);
1862 assert(opt
->buffer_output
<= 2);
1863 assert(opt
->obuf
.len
== 0);
1865 assert(opt
->priv
== NULL
);
1867 /* Default to histogram diff. Actually, just hardcode it...for now. */
1868 opt
->xdl_opts
= DIFF_WITH_ALG(opt
, HISTOGRAM_DIFF
);
1870 /* Initialization of opt->priv, our internal merge data */
1871 opt
->priv
= xcalloc(1, sizeof(*opt
->priv
));
1873 /* Initialization of various renames fields */
1874 renames
= &opt
->priv
->renames
;
1875 for (i
= MERGE_SIDE1
; i
<= MERGE_SIDE2
; i
++) {
1876 strset_init_with_options(&renames
->dirs_removed
[i
],
1878 strmap_init_with_options(&renames
->dir_rename_count
[i
],
1880 strmap_init_with_options(&renames
->dir_renames
[i
],
1885 * Although we initialize opt->priv->paths with strdup_strings=0,
1886 * that's just to avoid making yet another copy of an allocated
1887 * string. Putting the entry into paths means we are taking
1888 * ownership, so we will later free it. paths_to_free is similar.
1890 * In contrast, conflicted just has a subset of keys from paths, so
1891 * we don't want to free those (it'd be a duplicate free).
1893 strmap_init_with_options(&opt
->priv
->paths
, NULL
, 0);
1894 strmap_init_with_options(&opt
->priv
->conflicted
, NULL
, 0);
1895 string_list_init(&opt
->priv
->paths_to_free
, 0);
1898 * keys & strbufs in output will sometimes need to outlive "paths",
1899 * so it will have a copy of relevant keys. It's probably a small
1900 * subset of the overall paths that have special output.
1902 strmap_init(&opt
->priv
->output
);
1905 /*** Function Grouping: merge_incore_*() and their internal variants ***/
1908 * Originally from merge_trees_internal(); heavily adapted, though.
1910 static void merge_ort_nonrecursive_internal(struct merge_options
*opt
,
1911 struct tree
*merge_base
,
1914 struct merge_result
*result
)
1916 struct object_id working_tree_oid
;
1918 if (collect_merge_info(opt
, merge_base
, side1
, side2
) != 0) {
1920 * TRANSLATORS: The %s arguments are: 1) tree hash of a merge
1921 * base, and 2-3) the trees for the two trees we're merging.
1923 err(opt
, _("collecting merge info failed for trees %s, %s, %s"),
1924 oid_to_hex(&merge_base
->object
.oid
),
1925 oid_to_hex(&side1
->object
.oid
),
1926 oid_to_hex(&side2
->object
.oid
));
1931 result
->clean
= detect_and_process_renames(opt
, merge_base
,
1933 process_entries(opt
, &working_tree_oid
);
1935 /* Set return values */
1936 result
->tree
= parse_tree_indirect(&working_tree_oid
);
1937 /* existence of conflicted entries implies unclean */
1938 result
->clean
&= strmap_empty(&opt
->priv
->conflicted
);
1939 if (!opt
->priv
->call_depth
) {
1940 result
->priv
= opt
->priv
;
1946 * Originally from merge_recursive_internal(); somewhat adapted, though.
1948 static void merge_ort_internal(struct merge_options
*opt
,
1949 struct commit_list
*merge_bases
,
1952 struct merge_result
*result
)
1954 struct commit_list
*iter
;
1955 struct commit
*merged_merge_bases
;
1956 const char *ancestor_name
;
1957 struct strbuf merge_base_abbrev
= STRBUF_INIT
;
1960 merge_bases
= get_merge_bases(h1
, h2
);
1961 /* See merge-ort.h:merge_incore_recursive() declaration NOTE */
1962 merge_bases
= reverse_commit_list(merge_bases
);
1965 merged_merge_bases
= pop_commit(&merge_bases
);
1966 if (merged_merge_bases
== NULL
) {
1967 /* if there is no common ancestor, use an empty tree */
1970 tree
= lookup_tree(opt
->repo
, opt
->repo
->hash_algo
->empty_tree
);
1971 merged_merge_bases
= make_virtual_commit(opt
->repo
, tree
,
1973 ancestor_name
= "empty tree";
1974 } else if (merge_bases
) {
1975 ancestor_name
= "merged common ancestors";
1977 strbuf_add_unique_abbrev(&merge_base_abbrev
,
1978 &merged_merge_bases
->object
.oid
,
1980 ancestor_name
= merge_base_abbrev
.buf
;
1983 for (iter
= merge_bases
; iter
; iter
= iter
->next
) {
1984 const char *saved_b1
, *saved_b2
;
1985 struct commit
*prev
= merged_merge_bases
;
1987 opt
->priv
->call_depth
++;
1989 * When the merge fails, the result contains files
1990 * with conflict markers. The cleanness flag is
1991 * ignored (unless indicating an error), it was never
1992 * actually used, as result of merge_trees has always
1993 * overwritten it: the committed "conflicts" were
1996 saved_b1
= opt
->branch1
;
1997 saved_b2
= opt
->branch2
;
1998 opt
->branch1
= "Temporary merge branch 1";
1999 opt
->branch2
= "Temporary merge branch 2";
2000 merge_ort_internal(opt
, NULL
, prev
, iter
->item
, result
);
2001 if (result
->clean
< 0)
2003 opt
->branch1
= saved_b1
;
2004 opt
->branch2
= saved_b2
;
2005 opt
->priv
->call_depth
--;
2007 merged_merge_bases
= make_virtual_commit(opt
->repo
,
2010 commit_list_insert(prev
, &merged_merge_bases
->parents
);
2011 commit_list_insert(iter
->item
,
2012 &merged_merge_bases
->parents
->next
);
2014 clear_or_reinit_internal_opts(opt
->priv
, 1);
2017 opt
->ancestor
= ancestor_name
;
2018 merge_ort_nonrecursive_internal(opt
,
2019 repo_get_commit_tree(opt
->repo
,
2020 merged_merge_bases
),
2021 repo_get_commit_tree(opt
->repo
, h1
),
2022 repo_get_commit_tree(opt
->repo
, h2
),
2024 strbuf_release(&merge_base_abbrev
);
2025 opt
->ancestor
= NULL
; /* avoid accidental re-use of opt->ancestor */
2028 void merge_incore_nonrecursive(struct merge_options
*opt
,
2029 struct tree
*merge_base
,
2032 struct merge_result
*result
)
2034 assert(opt
->ancestor
!= NULL
);
2035 merge_start(opt
, result
);
2036 merge_ort_nonrecursive_internal(opt
, merge_base
, side1
, side2
, result
);
2039 void merge_incore_recursive(struct merge_options
*opt
,
2040 struct commit_list
*merge_bases
,
2041 struct commit
*side1
,
2042 struct commit
*side2
,
2043 struct merge_result
*result
)
2045 /* We set the ancestor label based on the merge_bases */
2046 assert(opt
->ancestor
== NULL
);
2048 merge_start(opt
, result
);
2049 merge_ort_internal(opt
, merge_bases
, side1
, side2
, result
);