oidtree: avoid unaligned access to crit-bit tree
[git/debian.git] / merge-ort.c
blob6eb910d6f0cf829f6dd028d32f89b3aa628ce12e
1 /*
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
4 * to replace
6 * git merge [-s recursive]
8 * with
10 * git merge -s ort
12 * Note: git's parser allows the space between '-s' and its argument to be
13 * missing. (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo",
14 * "cale", "peedy", or "ins" instead of "ort"?)
17 #include "cache.h"
18 #include "merge-ort.h"
20 #include "alloc.h"
21 #include "attr.h"
22 #include "blob.h"
23 #include "cache-tree.h"
24 #include "commit.h"
25 #include "commit-reach.h"
26 #include "diff.h"
27 #include "diffcore.h"
28 #include "dir.h"
29 #include "entry.h"
30 #include "ll-merge.h"
31 #include "object-store.h"
32 #include "promisor-remote.h"
33 #include "revision.h"
34 #include "strmap.h"
35 #include "submodule.h"
36 #include "tree.h"
37 #include "unpack-trees.h"
38 #include "xdiff-interface.h"
41 * We have many arrays of size 3. Whenever we have such an array, the
42 * indices refer to one of the sides of the three-way merge. This is so
43 * pervasive that the constants 0, 1, and 2 are used in many places in the
44 * code (especially in arithmetic operations to find the other side's index
45 * or to compute a relevant mask), but sometimes these enum names are used
46 * to aid code clarity.
48 * See also 'filemask' and 'dirmask' in struct conflict_info; the "ith side"
49 * referred to there is one of these three sides.
51 enum merge_side {
52 MERGE_BASE = 0,
53 MERGE_SIDE1 = 1,
54 MERGE_SIDE2 = 2
57 static unsigned RESULT_INITIALIZED = 0x1abe11ed; /* unlikely accidental value */
59 struct traversal_callback_data {
60 unsigned long mask;
61 unsigned long dirmask;
62 struct name_entry names[3];
65 struct deferred_traversal_data {
67 * possible_trivial_merges: directories to be explored only when needed
69 * possible_trivial_merges is a map of directory names to
70 * dir_rename_mask. When we detect that a directory is unchanged on
71 * one side, we can sometimes resolve the directory without recursing
72 * into it. Renames are the only things that can prevent such an
73 * optimization. However, for rename sources:
74 * - If no parent directory needed directory rename detection, then
75 * no path under such a directory can be a relevant_source.
76 * and for rename destinations:
77 * - If no cached rename has a target path under the directory AND
78 * - If there are no unpaired relevant_sources elsewhere in the
79 * repository
80 * then we don't need any path under this directory for a rename
81 * destination. The only way to know the last item above is to defer
82 * handling such directories until the end of collect_merge_info(),
83 * in handle_deferred_entries().
85 * For each we store dir_rename_mask, since that's the only bit of
86 * information we need, other than the path, to resume the recursive
87 * traversal.
89 struct strintmap possible_trivial_merges;
92 * trivial_merges_okay: if trivial directory merges are okay
94 * See possible_trivial_merges above. The "no unpaired
95 * relevant_sources elsewhere in the repository" is a single boolean
96 * per merge side, which we store here. Note that while 0 means no,
97 * 1 only means "maybe" rather than "yes"; we optimistically set it
98 * to 1 initially and only clear when we determine it is unsafe to
99 * do trivial directory merges.
101 unsigned trivial_merges_okay;
104 * target_dirs: ancestor directories of rename targets
106 * target_dirs contains all directory names that are an ancestor of
107 * any rename destination.
109 struct strset target_dirs;
112 struct rename_info {
114 * All variables that are arrays of size 3 correspond to data tracked
115 * for the sides in enum merge_side. Index 0 is almost always unused
116 * because we often only need to track information for MERGE_SIDE1 and
117 * MERGE_SIDE2 (MERGE_BASE can't have rename information since renames
118 * are determined relative to what changed since the MERGE_BASE).
122 * pairs: pairing of filenames from diffcore_rename()
124 struct diff_queue_struct pairs[3];
127 * dirs_removed: directories removed on a given side of history.
129 * The keys of dirs_removed[side] are the directories that were removed
130 * on the given side of history. The value of the strintmap for each
131 * directory is a value from enum dir_rename_relevance.
133 struct strintmap dirs_removed[3];
136 * dir_rename_count: tracking where parts of a directory were renamed to
138 * When files in a directory are renamed, they may not all go to the
139 * same location. Each strmap here tracks:
140 * old_dir => {new_dir => int}
141 * That is, dir_rename_count[side] is a strmap to a strintmap.
143 struct strmap dir_rename_count[3];
146 * dir_renames: computed directory renames
148 * This is a map of old_dir => new_dir and is derived in part from
149 * dir_rename_count.
151 struct strmap dir_renames[3];
154 * relevant_sources: deleted paths wanted in rename detection, and why
156 * relevant_sources is a set of deleted paths on each side of
157 * history for which we need rename detection. If a path is deleted
158 * on one side of history, we need to detect if it is part of a
159 * rename if either
160 * * the file is modified/deleted on the other side of history
161 * * we need to detect renames for an ancestor directory
162 * If neither of those are true, we can skip rename detection for
163 * that path. The reason is stored as a value from enum
164 * file_rename_relevance, as the reason can inform the algorithm in
165 * diffcore_rename_extended().
167 struct strintmap relevant_sources[3];
169 struct deferred_traversal_data deferred[3];
172 * dir_rename_mask:
173 * 0: optimization removing unmodified potential rename source okay
174 * 2 or 4: optimization okay, but must check for files added to dir
175 * 7: optimization forbidden; need rename source in case of dir rename
177 unsigned dir_rename_mask:3;
180 * callback_data_*: supporting data structures for alternate traversal
182 * We sometimes need to be able to traverse through all the files
183 * in a given tree before all immediate subdirectories within that
184 * tree. Since traverse_trees() doesn't do that naturally, we have
185 * a traverse_trees_wrapper() that stores any immediate
186 * subdirectories while traversing files, then traverses the
187 * immediate subdirectories later. These callback_data* variables
188 * store the information for the subdirectories so that we can do
189 * that traversal order.
191 struct traversal_callback_data *callback_data;
192 int callback_data_nr, callback_data_alloc;
193 char *callback_data_traverse_path;
196 * merge_trees: trees passed to the merge algorithm for the merge
198 * merge_trees records the trees passed to the merge algorithm. But,
199 * this data also is stored in merge_result->priv. If a sequence of
200 * merges are being done (such as when cherry-picking or rebasing),
201 * the next merge can look at this and re-use information from
202 * previous merges under certain circumstances.
204 * See also all the cached_* variables.
206 struct tree *merge_trees[3];
209 * cached_pairs_valid_side: which side's cached info can be reused
211 * See the description for merge_trees. For repeated merges, at most
212 * only one side's cached information can be used. Valid values:
213 * MERGE_SIDE2: cached data from side2 can be reused
214 * MERGE_SIDE1: cached data from side1 can be reused
215 * 0: no cached data can be reused
216 * -1: See redo_after_renames; both sides can be reused.
218 int cached_pairs_valid_side;
221 * cached_pairs: Caching of renames and deletions.
223 * These are mappings recording renames and deletions of individual
224 * files (not directories). They are thus a map from an old
225 * filename to either NULL (for deletions) or a new filename (for
226 * renames).
228 struct strmap cached_pairs[3];
231 * cached_target_names: just the destinations from cached_pairs
233 * We sometimes want a fast lookup to determine if a given filename
234 * is one of the destinations in cached_pairs. cached_target_names
235 * is thus duplicative information, but it provides a fast lookup.
237 struct strset cached_target_names[3];
240 * cached_irrelevant: Caching of rename_sources that aren't relevant.
242 * If we try to detect a rename for a source path and succeed, it's
243 * part of a rename. If we try to detect a rename for a source path
244 * and fail, then it's a delete. If we do not try to detect a rename
245 * for a path, then we don't know if it's a rename or a delete. If
246 * merge-ort doesn't think the path is relevant, then we just won't
247 * cache anything for that path. But there's a slight problem in
248 * that merge-ort can think a path is RELEVANT_LOCATION, but due to
249 * commit 9bd342137e ("diffcore-rename: determine which
250 * relevant_sources are no longer relevant", 2021-03-13),
251 * diffcore-rename can downgrade the path to RELEVANT_NO_MORE. To
252 * avoid excessive calls to diffcore_rename_extended() we still need
253 * to cache such paths, though we cannot record them as either
254 * renames or deletes. So we cache them here as a "turned out to be
255 * irrelevant *for this commit*" as they are often also irrelevant
256 * for subsequent commits, though we will have to do some extra
257 * checking to see whether such paths become relevant for rename
258 * detection when cherry-picking/rebasing subsequent commits.
260 struct strset cached_irrelevant[3];
263 * redo_after_renames: optimization flag for "restarting" the merge
265 * Sometimes it pays to detect renames, cache them, and then
266 * restart the merge operation from the beginning. The reason for
267 * this is that when we know where all the renames are, we know
268 * whether a certain directory has any paths under it affected --
269 * and if a directory is not affected then it permits us to do
270 * trivial tree merging in more cases. Doing trivial tree merging
271 * prevents the need to run process_entry() on every path
272 * underneath trees that can be trivially merged, and
273 * process_entry() is more expensive than collect_merge_info() --
274 * plus, the second collect_merge_info() will be much faster since
275 * it doesn't have to recurse into the relevant trees.
277 * Values for this flag:
278 * 0 = don't bother, not worth it (or conditions not yet checked)
279 * 1 = conditions for optimization met, optimization worthwhile
280 * 2 = we already did it (don't restart merge yet again)
282 unsigned redo_after_renames;
285 * needed_limit: value needed for inexact rename detection to run
287 * If the current rename limit wasn't high enough for inexact
288 * rename detection to run, this records the limit needed. Otherwise,
289 * this value remains 0.
291 int needed_limit;
294 struct merge_options_internal {
296 * paths: primary data structure in all of merge ort.
298 * The keys of paths:
299 * * are full relative paths from the toplevel of the repository
300 * (e.g. "drivers/firmware/raspberrypi.c").
301 * * store all relevant paths in the repo, both directories and
302 * files (e.g. drivers, drivers/firmware would also be included)
303 * * these keys serve to intern all the path strings, which allows
304 * us to do pointer comparison on directory names instead of
305 * strcmp; we just have to be careful to use the interned strings.
306 * (Technically paths_to_free may track some strings that were
307 * removed from froms paths.)
309 * The values of paths:
310 * * either a pointer to a merged_info, or a conflict_info struct
311 * * merged_info contains all relevant information for a
312 * non-conflicted entry.
313 * * conflict_info contains a merged_info, plus any additional
314 * information about a conflict such as the higher orders stages
315 * involved and the names of the paths those came from (handy
316 * once renames get involved).
317 * * a path may start "conflicted" (i.e. point to a conflict_info)
318 * and then a later step (e.g. three-way content merge) determines
319 * it can be cleanly merged, at which point it'll be marked clean
320 * and the algorithm will ignore any data outside the contained
321 * merged_info for that entry
322 * * If an entry remains conflicted, the merged_info portion of a
323 * conflict_info will later be filled with whatever version of
324 * the file should be placed in the working directory (e.g. an
325 * as-merged-as-possible variation that contains conflict markers).
327 struct strmap paths;
330 * conflicted: a subset of keys->values from "paths"
332 * conflicted is basically an optimization between process_entries()
333 * and record_conflicted_index_entries(); the latter could loop over
334 * ALL the entries in paths AGAIN and look for the ones that are
335 * still conflicted, but since process_entries() has to loop over
336 * all of them, it saves the ones it couldn't resolve in this strmap
337 * so that record_conflicted_index_entries() can iterate just the
338 * relevant entries.
340 struct strmap conflicted;
343 * paths_to_free: additional list of strings to free
345 * If keys are removed from "paths", they are added to paths_to_free
346 * to ensure they are later freed. We avoid free'ing immediately since
347 * other places (e.g. conflict_info.pathnames[]) may still be
348 * referencing these paths.
350 struct string_list paths_to_free;
353 * output: special messages and conflict notices for various paths
355 * This is a map of pathnames (a subset of the keys in "paths" above)
356 * to strbufs. It gathers various warning/conflict/notice messages
357 * for later processing.
359 struct strmap output;
362 * renames: various data relating to rename detection
364 struct rename_info renames;
367 * attr_index: hacky minimal index used for renormalization
369 * renormalization code _requires_ an index, though it only needs to
370 * find a .gitattributes file within the index. So, when
371 * renormalization is important, we create a special index with just
372 * that one file.
374 struct index_state attr_index;
377 * current_dir_name, toplevel_dir: temporary vars
379 * These are used in collect_merge_info_callback(), and will set the
380 * various merged_info.directory_name for the various paths we get;
381 * see documentation for that variable and the requirements placed on
382 * that field.
384 const char *current_dir_name;
385 const char *toplevel_dir;
387 /* call_depth: recursion level counter for merging merge bases */
388 int call_depth;
391 struct version_info {
392 struct object_id oid;
393 unsigned short mode;
396 struct merged_info {
397 /* if is_null, ignore result. otherwise result has oid & mode */
398 struct version_info result;
399 unsigned is_null:1;
402 * clean: whether the path in question is cleanly merged.
404 * see conflict_info.merged for more details.
406 unsigned clean:1;
409 * basename_offset: offset of basename of path.
411 * perf optimization to avoid recomputing offset of final '/'
412 * character in pathname (0 if no '/' in pathname).
414 size_t basename_offset;
417 * directory_name: containing directory name.
419 * Note that we assume directory_name is constructed such that
420 * strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name,
421 * i.e. string equality is equivalent to pointer equality. For this
422 * to hold, we have to be careful setting directory_name.
424 const char *directory_name;
427 struct conflict_info {
429 * merged: the version of the path that will be written to working tree
431 * WARNING: It is critical to check merged.clean and ensure it is 0
432 * before reading any conflict_info fields outside of merged.
433 * Allocated merge_info structs will always have clean set to 1.
434 * Allocated conflict_info structs will have merged.clean set to 0
435 * initially. The merged.clean field is how we know if it is safe
436 * to access other parts of conflict_info besides merged; if a
437 * conflict_info's merged.clean is changed to 1, the rest of the
438 * algorithm is not allowed to look at anything outside of the
439 * merged member anymore.
441 struct merged_info merged;
443 /* oids & modes from each of the three trees for this path */
444 struct version_info stages[3];
446 /* pathnames for each stage; may differ due to rename detection */
447 const char *pathnames[3];
449 /* Whether this path is/was involved in a directory/file conflict */
450 unsigned df_conflict:1;
453 * Whether this path is/was involved in a non-content conflict other
454 * than a directory/file conflict (e.g. rename/rename, rename/delete,
455 * file location based on possible directory rename).
457 unsigned path_conflict:1;
460 * For filemask and dirmask, the ith bit corresponds to whether the
461 * ith entry is a file (filemask) or a directory (dirmask). Thus,
462 * filemask & dirmask is always zero, and filemask | dirmask is at
463 * most 7 but can be less when a path does not appear as either a
464 * file or a directory on at least one side of history.
466 * Note that these masks are related to enum merge_side, as the ith
467 * entry corresponds to side i.
469 * These values come from a traverse_trees() call; more info may be
470 * found looking at tree-walk.h's struct traverse_info,
471 * particularly the documentation above the "fn" member (note that
472 * filemask = mask & ~dirmask from that documentation).
474 unsigned filemask:3;
475 unsigned dirmask:3;
478 * Optimization to track which stages match, to avoid the need to
479 * recompute it in multiple steps. Either 0 or at least 2 bits are
480 * set; if at least 2 bits are set, their corresponding stages match.
482 unsigned match_mask:3;
485 /*** Function Grouping: various utility functions ***/
488 * For the next three macros, see warning for conflict_info.merged.
490 * In each of the below, mi is a struct merged_info*, and ci was defined
491 * as a struct conflict_info* (but we need to verify ci isn't actually
492 * pointed at a struct merged_info*).
494 * INITIALIZE_CI: Assign ci to mi but only if it's safe; set to NULL otherwise.
495 * VERIFY_CI: Ensure that something we assigned to a conflict_info* is one.
496 * ASSIGN_AND_VERIFY_CI: Similar to VERIFY_CI but do assignment first.
498 #define INITIALIZE_CI(ci, mi) do { \
499 (ci) = (!(mi) || (mi)->clean) ? NULL : (struct conflict_info *)(mi); \
500 } while (0)
501 #define VERIFY_CI(ci) assert(ci && !ci->merged.clean);
502 #define ASSIGN_AND_VERIFY_CI(ci, mi) do { \
503 (ci) = (struct conflict_info *)(mi); \
504 assert((ci) && !(mi)->clean); \
505 } while (0)
507 static void free_strmap_strings(struct strmap *map)
509 struct hashmap_iter iter;
510 struct strmap_entry *entry;
512 strmap_for_each_entry(map, &iter, entry) {
513 free((char*)entry->key);
517 static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,
518 int reinitialize)
520 struct rename_info *renames = &opti->renames;
521 int i;
522 void (*strmap_func)(struct strmap *, int) =
523 reinitialize ? strmap_partial_clear : strmap_clear;
524 void (*strintmap_func)(struct strintmap *) =
525 reinitialize ? strintmap_partial_clear : strintmap_clear;
526 void (*strset_func)(struct strset *) =
527 reinitialize ? strset_partial_clear : strset_clear;
530 * We marked opti->paths with strdup_strings = 0, so that we
531 * wouldn't have to make another copy of the fullpath created by
532 * make_traverse_path from setup_path_info(). But, now that we've
533 * used it and have no other references to these strings, it is time
534 * to deallocate them.
536 free_strmap_strings(&opti->paths);
537 strmap_func(&opti->paths, 1);
540 * All keys and values in opti->conflicted are a subset of those in
541 * opti->paths. We don't want to deallocate anything twice, so we
542 * don't free the keys and we pass 0 for free_values.
544 strmap_func(&opti->conflicted, 0);
547 * opti->paths_to_free is similar to opti->paths; we created it with
548 * strdup_strings = 0 to avoid making _another_ copy of the fullpath
549 * but now that we've used it and have no other references to these
550 * strings, it is time to deallocate them. We do so by temporarily
551 * setting strdup_strings to 1.
553 opti->paths_to_free.strdup_strings = 1;
554 string_list_clear(&opti->paths_to_free, 0);
555 opti->paths_to_free.strdup_strings = 0;
557 if (opti->attr_index.cache_nr) /* true iff opt->renormalize */
558 discard_index(&opti->attr_index);
560 /* Free memory used by various renames maps */
561 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; ++i) {
562 strintmap_func(&renames->dirs_removed[i]);
563 strmap_func(&renames->dir_renames[i], 0);
564 strintmap_func(&renames->relevant_sources[i]);
565 if (!reinitialize)
566 assert(renames->cached_pairs_valid_side == 0);
567 if (i != renames->cached_pairs_valid_side &&
568 -1 != renames->cached_pairs_valid_side) {
569 strset_func(&renames->cached_target_names[i]);
570 strmap_func(&renames->cached_pairs[i], 1);
571 strset_func(&renames->cached_irrelevant[i]);
572 partial_clear_dir_rename_count(&renames->dir_rename_count[i]);
573 if (!reinitialize)
574 strmap_clear(&renames->dir_rename_count[i], 1);
577 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; ++i) {
578 strintmap_func(&renames->deferred[i].possible_trivial_merges);
579 strset_func(&renames->deferred[i].target_dirs);
580 renames->deferred[i].trivial_merges_okay = 1; /* 1 == maybe */
582 renames->cached_pairs_valid_side = 0;
583 renames->dir_rename_mask = 0;
585 if (!reinitialize) {
586 struct hashmap_iter iter;
587 struct strmap_entry *e;
589 /* Release and free each strbuf found in output */
590 strmap_for_each_entry(&opti->output, &iter, e) {
591 struct strbuf *sb = e->value;
592 strbuf_release(sb);
594 * While strictly speaking we don't need to free(sb)
595 * here because we could pass free_values=1 when
596 * calling strmap_clear() on opti->output, that would
597 * require strmap_clear to do another
598 * strmap_for_each_entry() loop, so we just free it
599 * while we're iterating anyway.
601 free(sb);
603 strmap_clear(&opti->output, 0);
606 /* Clean out callback_data as well. */
607 FREE_AND_NULL(renames->callback_data);
608 renames->callback_data_nr = renames->callback_data_alloc = 0;
611 __attribute__((format (printf, 2, 3)))
612 static int err(struct merge_options *opt, const char *err, ...)
614 va_list params;
615 struct strbuf sb = STRBUF_INIT;
617 strbuf_addstr(&sb, "error: ");
618 va_start(params, err);
619 strbuf_vaddf(&sb, err, params);
620 va_end(params);
622 error("%s", sb.buf);
623 strbuf_release(&sb);
625 return -1;
628 static void format_commit(struct strbuf *sb,
629 int indent,
630 struct commit *commit)
632 struct merge_remote_desc *desc;
633 struct pretty_print_context ctx = {0};
634 ctx.abbrev = DEFAULT_ABBREV;
636 strbuf_addchars(sb, ' ', indent);
637 desc = merge_remote_util(commit);
638 if (desc) {
639 strbuf_addf(sb, "virtual %s\n", desc->name);
640 return;
643 format_commit_message(commit, "%h %s", sb, &ctx);
644 strbuf_addch(sb, '\n');
647 __attribute__((format (printf, 4, 5)))
648 static void path_msg(struct merge_options *opt,
649 const char *path,
650 int omittable_hint, /* skippable under --remerge-diff */
651 const char *fmt, ...)
653 va_list ap;
654 struct strbuf *sb = strmap_get(&opt->priv->output, path);
655 if (!sb) {
656 sb = xmalloc(sizeof(*sb));
657 strbuf_init(sb, 0);
658 strmap_put(&opt->priv->output, path, sb);
661 va_start(ap, fmt);
662 strbuf_vaddf(sb, fmt, ap);
663 va_end(ap);
665 strbuf_addch(sb, '\n');
668 /* add a string to a strbuf, but converting "/" to "_" */
669 static void add_flattened_path(struct strbuf *out, const char *s)
671 size_t i = out->len;
672 strbuf_addstr(out, s);
673 for (; i < out->len; i++)
674 if (out->buf[i] == '/')
675 out->buf[i] = '_';
678 static char *unique_path(struct strmap *existing_paths,
679 const char *path,
680 const char *branch)
682 struct strbuf newpath = STRBUF_INIT;
683 int suffix = 0;
684 size_t base_len;
686 strbuf_addf(&newpath, "%s~", path);
687 add_flattened_path(&newpath, branch);
689 base_len = newpath.len;
690 while (strmap_contains(existing_paths, newpath.buf)) {
691 strbuf_setlen(&newpath, base_len);
692 strbuf_addf(&newpath, "_%d", suffix++);
695 return strbuf_detach(&newpath, NULL);
698 /*** Function Grouping: functions related to collect_merge_info() ***/
700 static int traverse_trees_wrapper_callback(int n,
701 unsigned long mask,
702 unsigned long dirmask,
703 struct name_entry *names,
704 struct traverse_info *info)
706 struct merge_options *opt = info->data;
707 struct rename_info *renames = &opt->priv->renames;
708 unsigned filemask = mask & ~dirmask;
710 assert(n==3);
712 if (!renames->callback_data_traverse_path)
713 renames->callback_data_traverse_path = xstrdup(info->traverse_path);
715 if (filemask && filemask == renames->dir_rename_mask)
716 renames->dir_rename_mask = 0x07;
718 ALLOC_GROW(renames->callback_data, renames->callback_data_nr + 1,
719 renames->callback_data_alloc);
720 renames->callback_data[renames->callback_data_nr].mask = mask;
721 renames->callback_data[renames->callback_data_nr].dirmask = dirmask;
722 COPY_ARRAY(renames->callback_data[renames->callback_data_nr].names,
723 names, 3);
724 renames->callback_data_nr++;
726 return mask;
730 * Much like traverse_trees(), BUT:
731 * - read all the tree entries FIRST, saving them
732 * - note that the above step provides an opportunity to compute necessary
733 * additional details before the "real" traversal
734 * - loop through the saved entries and call the original callback on them
736 static int traverse_trees_wrapper(struct index_state *istate,
737 int n,
738 struct tree_desc *t,
739 struct traverse_info *info)
741 int ret, i, old_offset;
742 traverse_callback_t old_fn;
743 char *old_callback_data_traverse_path;
744 struct merge_options *opt = info->data;
745 struct rename_info *renames = &opt->priv->renames;
747 assert(renames->dir_rename_mask == 2 || renames->dir_rename_mask == 4);
749 old_callback_data_traverse_path = renames->callback_data_traverse_path;
750 old_fn = info->fn;
751 old_offset = renames->callback_data_nr;
753 renames->callback_data_traverse_path = NULL;
754 info->fn = traverse_trees_wrapper_callback;
755 ret = traverse_trees(istate, n, t, info);
756 if (ret < 0)
757 return ret;
759 info->traverse_path = renames->callback_data_traverse_path;
760 info->fn = old_fn;
761 for (i = old_offset; i < renames->callback_data_nr; ++i) {
762 info->fn(n,
763 renames->callback_data[i].mask,
764 renames->callback_data[i].dirmask,
765 renames->callback_data[i].names,
766 info);
769 renames->callback_data_nr = old_offset;
770 free(renames->callback_data_traverse_path);
771 renames->callback_data_traverse_path = old_callback_data_traverse_path;
772 info->traverse_path = NULL;
773 return 0;
776 static void setup_path_info(struct merge_options *opt,
777 struct string_list_item *result,
778 const char *current_dir_name,
779 int current_dir_name_len,
780 char *fullpath, /* we'll take over ownership */
781 struct name_entry *names,
782 struct name_entry *merged_version,
783 unsigned is_null, /* boolean */
784 unsigned df_conflict, /* boolean */
785 unsigned filemask,
786 unsigned dirmask,
787 int resolved /* boolean */)
789 /* result->util is void*, so mi is a convenience typed variable */
790 struct merged_info *mi;
792 assert(!is_null || resolved);
793 assert(!df_conflict || !resolved); /* df_conflict implies !resolved */
794 assert(resolved == (merged_version != NULL));
796 mi = xcalloc(1, resolved ? sizeof(struct merged_info) :
797 sizeof(struct conflict_info));
798 mi->directory_name = current_dir_name;
799 mi->basename_offset = current_dir_name_len;
800 mi->clean = !!resolved;
801 if (resolved) {
802 mi->result.mode = merged_version->mode;
803 oidcpy(&mi->result.oid, &merged_version->oid);
804 mi->is_null = !!is_null;
805 } else {
806 int i;
807 struct conflict_info *ci;
809 ASSIGN_AND_VERIFY_CI(ci, mi);
810 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
811 ci->pathnames[i] = fullpath;
812 ci->stages[i].mode = names[i].mode;
813 oidcpy(&ci->stages[i].oid, &names[i].oid);
815 ci->filemask = filemask;
816 ci->dirmask = dirmask;
817 ci->df_conflict = !!df_conflict;
818 if (dirmask)
820 * Assume is_null for now, but if we have entries
821 * under the directory then when it is complete in
822 * write_completed_directory() it'll update this.
823 * Also, for D/F conflicts, we have to handle the
824 * directory first, then clear this bit and process
825 * the file to see how it is handled -- that occurs
826 * near the top of process_entry().
828 mi->is_null = 1;
830 strmap_put(&opt->priv->paths, fullpath, mi);
831 result->string = fullpath;
832 result->util = mi;
835 static void add_pair(struct merge_options *opt,
836 struct name_entry *names,
837 const char *pathname,
838 unsigned side,
839 unsigned is_add /* if false, is_delete */,
840 unsigned match_mask,
841 unsigned dir_rename_mask)
843 struct diff_filespec *one, *two;
844 struct rename_info *renames = &opt->priv->renames;
845 int names_idx = is_add ? side : 0;
847 if (is_add) {
848 assert(match_mask == 0 || match_mask == 6);
849 if (strset_contains(&renames->cached_target_names[side],
850 pathname))
851 return;
852 } else {
853 unsigned content_relevant = (match_mask == 0);
854 unsigned location_relevant = (dir_rename_mask == 0x07);
856 assert(match_mask == 0 || match_mask == 3 || match_mask == 5);
859 * If pathname is found in cached_irrelevant[side] due to
860 * previous pick but for this commit content is relevant,
861 * then we need to remove it from cached_irrelevant.
863 if (content_relevant)
864 /* strset_remove is no-op if strset doesn't have key */
865 strset_remove(&renames->cached_irrelevant[side],
866 pathname);
869 * We do not need to re-detect renames for paths that we already
870 * know the pairing, i.e. for cached_pairs (or
871 * cached_irrelevant). However, handle_deferred_entries() needs
872 * to loop over the union of keys from relevant_sources[side] and
873 * cached_pairs[side], so for simplicity we set relevant_sources
874 * for all the cached_pairs too and then strip them back out in
875 * prune_cached_from_relevant() at the beginning of
876 * detect_regular_renames().
878 if (content_relevant || location_relevant) {
879 /* content_relevant trumps location_relevant */
880 strintmap_set(&renames->relevant_sources[side], pathname,
881 content_relevant ? RELEVANT_CONTENT : RELEVANT_LOCATION);
885 * Avoid creating pair if we've already cached rename results.
886 * Note that we do this after setting relevant_sources[side]
887 * as noted in the comment above.
889 if (strmap_contains(&renames->cached_pairs[side], pathname) ||
890 strset_contains(&renames->cached_irrelevant[side], pathname))
891 return;
894 one = alloc_filespec(pathname);
895 two = alloc_filespec(pathname);
896 fill_filespec(is_add ? two : one,
897 &names[names_idx].oid, 1, names[names_idx].mode);
898 diff_queue(&renames->pairs[side], one, two);
901 static void collect_rename_info(struct merge_options *opt,
902 struct name_entry *names,
903 const char *dirname,
904 const char *fullname,
905 unsigned filemask,
906 unsigned dirmask,
907 unsigned match_mask)
909 struct rename_info *renames = &opt->priv->renames;
910 unsigned side;
913 * Update dir_rename_mask (determines ignore-rename-source validity)
915 * dir_rename_mask helps us keep track of when directory rename
916 * detection may be relevant. Basically, whenver a directory is
917 * removed on one side of history, and a file is added to that
918 * directory on the other side of history, directory rename
919 * detection is relevant (meaning we have to detect renames for all
920 * files within that directory to deduce where the directory
921 * moved). Also, whenever a directory needs directory rename
922 * detection, due to the "majority rules" choice for where to move
923 * it (see t6423 testcase 1f), we also need to detect renames for
924 * all files within subdirectories of that directory as well.
926 * Here we haven't looked at files within the directory yet, we are
927 * just looking at the directory itself. So, if we aren't yet in
928 * a case where a parent directory needed directory rename detection
929 * (i.e. dir_rename_mask != 0x07), and if the directory was removed
930 * on one side of history, record the mask of the other side of
931 * history in dir_rename_mask.
933 if (renames->dir_rename_mask != 0x07 &&
934 (dirmask == 3 || dirmask == 5)) {
935 /* simple sanity check */
936 assert(renames->dir_rename_mask == 0 ||
937 renames->dir_rename_mask == (dirmask & ~1));
938 /* update dir_rename_mask; have it record mask of new side */
939 renames->dir_rename_mask = (dirmask & ~1);
942 /* Update dirs_removed, as needed */
943 if (dirmask == 1 || dirmask == 3 || dirmask == 5) {
944 /* absent_mask = 0x07 - dirmask; sides = absent_mask/2 */
945 unsigned sides = (0x07 - dirmask)/2;
946 unsigned relevance = (renames->dir_rename_mask == 0x07) ?
947 RELEVANT_FOR_ANCESTOR : NOT_RELEVANT;
949 * Record relevance of this directory. However, note that
950 * when collect_merge_info_callback() recurses into this
951 * directory and calls collect_rename_info() on paths
952 * within that directory, if we find a path that was added
953 * to this directory on the other side of history, we will
954 * upgrade this value to RELEVANT_FOR_SELF; see below.
956 if (sides & 1)
957 strintmap_set(&renames->dirs_removed[1], fullname,
958 relevance);
959 if (sides & 2)
960 strintmap_set(&renames->dirs_removed[2], fullname,
961 relevance);
965 * Here's the block that potentially upgrades to RELEVANT_FOR_SELF.
966 * When we run across a file added to a directory. In such a case,
967 * find the directory of the file and upgrade its relevance.
969 if (renames->dir_rename_mask == 0x07 &&
970 (filemask == 2 || filemask == 4)) {
972 * Need directory rename for parent directory on other side
973 * of history from added file. Thus
974 * side = (~filemask & 0x06) >> 1
975 * or
976 * side = 3 - (filemask/2).
978 unsigned side = 3 - (filemask >> 1);
979 strintmap_set(&renames->dirs_removed[side], dirname,
980 RELEVANT_FOR_SELF);
983 if (filemask == 0 || filemask == 7)
984 return;
986 for (side = MERGE_SIDE1; side <= MERGE_SIDE2; ++side) {
987 unsigned side_mask = (1 << side);
989 /* Check for deletion on side */
990 if ((filemask & 1) && !(filemask & side_mask))
991 add_pair(opt, names, fullname, side, 0 /* delete */,
992 match_mask & filemask,
993 renames->dir_rename_mask);
995 /* Check for addition on side */
996 if (!(filemask & 1) && (filemask & side_mask))
997 add_pair(opt, names, fullname, side, 1 /* add */,
998 match_mask & filemask,
999 renames->dir_rename_mask);
1003 static int collect_merge_info_callback(int n,
1004 unsigned long mask,
1005 unsigned long dirmask,
1006 struct name_entry *names,
1007 struct traverse_info *info)
1010 * n is 3. Always.
1011 * common ancestor (mbase) has mask 1, and stored in index 0 of names
1012 * head of side 1 (side1) has mask 2, and stored in index 1 of names
1013 * head of side 2 (side2) has mask 4, and stored in index 2 of names
1015 struct merge_options *opt = info->data;
1016 struct merge_options_internal *opti = opt->priv;
1017 struct rename_info *renames = &opt->priv->renames;
1018 struct string_list_item pi; /* Path Info */
1019 struct conflict_info *ci; /* typed alias to pi.util (which is void*) */
1020 struct name_entry *p;
1021 size_t len;
1022 char *fullpath;
1023 const char *dirname = opti->current_dir_name;
1024 unsigned prev_dir_rename_mask = renames->dir_rename_mask;
1025 unsigned filemask = mask & ~dirmask;
1026 unsigned match_mask = 0; /* will be updated below */
1027 unsigned mbase_null = !(mask & 1);
1028 unsigned side1_null = !(mask & 2);
1029 unsigned side2_null = !(mask & 4);
1030 unsigned side1_matches_mbase = (!side1_null && !mbase_null &&
1031 names[0].mode == names[1].mode &&
1032 oideq(&names[0].oid, &names[1].oid));
1033 unsigned side2_matches_mbase = (!side2_null && !mbase_null &&
1034 names[0].mode == names[2].mode &&
1035 oideq(&names[0].oid, &names[2].oid));
1036 unsigned sides_match = (!side1_null && !side2_null &&
1037 names[1].mode == names[2].mode &&
1038 oideq(&names[1].oid, &names[2].oid));
1041 * Note: When a path is a file on one side of history and a directory
1042 * in another, we have a directory/file conflict. In such cases, if
1043 * the conflict doesn't resolve from renames and deletions, then we
1044 * always leave directories where they are and move files out of the
1045 * way. Thus, while struct conflict_info has a df_conflict field to
1046 * track such conflicts, we ignore that field for any directories at
1047 * a path and only pay attention to it for files at the given path.
1048 * The fact that we leave directories were they are also means that
1049 * we do not need to worry about getting additional df_conflict
1050 * information propagated from parent directories down to children
1051 * (unlike, say traverse_trees_recursive() in unpack-trees.c, which
1052 * sets a newinfo.df_conflicts field specifically to propagate it).
1054 unsigned df_conflict = (filemask != 0) && (dirmask != 0);
1056 /* n = 3 is a fundamental assumption. */
1057 if (n != 3)
1058 BUG("Called collect_merge_info_callback wrong");
1061 * A bunch of sanity checks verifying that traverse_trees() calls
1062 * us the way I expect. Could just remove these at some point,
1063 * though maybe they are helpful to future code readers.
1065 assert(mbase_null == is_null_oid(&names[0].oid));
1066 assert(side1_null == is_null_oid(&names[1].oid));
1067 assert(side2_null == is_null_oid(&names[2].oid));
1068 assert(!mbase_null || !side1_null || !side2_null);
1069 assert(mask > 0 && mask < 8);
1071 /* Determine match_mask */
1072 if (side1_matches_mbase)
1073 match_mask = (side2_matches_mbase ? 7 : 3);
1074 else if (side2_matches_mbase)
1075 match_mask = 5;
1076 else if (sides_match)
1077 match_mask = 6;
1080 * Get the name of the relevant filepath, which we'll pass to
1081 * setup_path_info() for tracking.
1083 p = names;
1084 while (!p->mode)
1085 p++;
1086 len = traverse_path_len(info, p->pathlen);
1088 /* +1 in both of the following lines to include the NUL byte */
1089 fullpath = xmalloc(len + 1);
1090 make_traverse_path(fullpath, len + 1, info, p->path, p->pathlen);
1093 * If mbase, side1, and side2 all match, we can resolve early. Even
1094 * if these are trees, there will be no renames or anything
1095 * underneath.
1097 if (side1_matches_mbase && side2_matches_mbase) {
1098 /* mbase, side1, & side2 all match; use mbase as resolution */
1099 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
1100 names, names+0, mbase_null, 0 /* df_conflict */,
1101 filemask, dirmask, 1 /* resolved */);
1102 return mask;
1106 * If the sides match, and all three paths are present and are
1107 * files, then we can take either as the resolution. We can't do
1108 * this with trees, because there may be rename sources from the
1109 * merge_base.
1111 if (sides_match && filemask == 0x07) {
1112 /* use side1 (== side2) version as resolution */
1113 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
1114 names, names+1, side1_null, 0,
1115 filemask, dirmask, 1);
1116 return mask;
1120 * If side1 matches mbase and all three paths are present and are
1121 * files, then we can use side2 as the resolution. We cannot
1122 * necessarily do so this for trees, because there may be rename
1123 * destinations within side2.
1125 if (side1_matches_mbase && filemask == 0x07) {
1126 /* use side2 version as resolution */
1127 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
1128 names, names+2, side2_null, 0,
1129 filemask, dirmask, 1);
1130 return mask;
1133 /* Similar to above but swapping sides 1 and 2 */
1134 if (side2_matches_mbase && filemask == 0x07) {
1135 /* use side1 version as resolution */
1136 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
1137 names, names+1, side1_null, 0,
1138 filemask, dirmask, 1);
1139 return mask;
1143 * Sometimes we can tell that a source path need not be included in
1144 * rename detection -- namely, whenever either
1145 * side1_matches_mbase && side2_null
1146 * or
1147 * side2_matches_mbase && side1_null
1148 * However, we call collect_rename_info() even in those cases,
1149 * because exact renames are cheap and would let us remove both a
1150 * source and destination path. We'll cull the unneeded sources
1151 * later.
1153 collect_rename_info(opt, names, dirname, fullpath,
1154 filemask, dirmask, match_mask);
1157 * None of the special cases above matched, so we have a
1158 * provisional conflict. (Rename detection might allow us to
1159 * unconflict some more cases, but that comes later so all we can
1160 * do now is record the different non-null file hashes.)
1162 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
1163 names, NULL, 0, df_conflict, filemask, dirmask, 0);
1165 ci = pi.util;
1166 VERIFY_CI(ci);
1167 ci->match_mask = match_mask;
1169 /* If dirmask, recurse into subdirectories */
1170 if (dirmask) {
1171 struct traverse_info newinfo;
1172 struct tree_desc t[3];
1173 void *buf[3] = {NULL, NULL, NULL};
1174 const char *original_dir_name;
1175 int i, ret, side;
1178 * Check for whether we can avoid recursing due to one side
1179 * matching the merge base. The side that does NOT match is
1180 * the one that might have a rename destination we need.
1182 assert(!side1_matches_mbase || !side2_matches_mbase);
1183 side = side1_matches_mbase ? MERGE_SIDE2 :
1184 side2_matches_mbase ? MERGE_SIDE1 : MERGE_BASE;
1185 if (filemask == 0 && (dirmask == 2 || dirmask == 4)) {
1187 * Also defer recursing into new directories; set up a
1188 * few variables to let us do so.
1190 ci->match_mask = (7 - dirmask);
1191 side = dirmask / 2;
1193 if (renames->dir_rename_mask != 0x07 &&
1194 side != MERGE_BASE &&
1195 renames->deferred[side].trivial_merges_okay &&
1196 !strset_contains(&renames->deferred[side].target_dirs,
1197 pi.string)) {
1198 strintmap_set(&renames->deferred[side].possible_trivial_merges,
1199 pi.string, renames->dir_rename_mask);
1200 renames->dir_rename_mask = prev_dir_rename_mask;
1201 return mask;
1204 /* We need to recurse */
1205 ci->match_mask &= filemask;
1206 newinfo = *info;
1207 newinfo.prev = info;
1208 newinfo.name = p->path;
1209 newinfo.namelen = p->pathlen;
1210 newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1);
1212 * If this directory we are about to recurse into cared about
1213 * its parent directory (the current directory) having a D/F
1214 * conflict, then we'd propagate the masks in this way:
1215 * newinfo.df_conflicts |= (mask & ~dirmask);
1216 * But we don't worry about propagating D/F conflicts. (See
1217 * comment near setting of local df_conflict variable near
1218 * the beginning of this function).
1221 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
1222 if (i == 1 && side1_matches_mbase)
1223 t[1] = t[0];
1224 else if (i == 2 && side2_matches_mbase)
1225 t[2] = t[0];
1226 else if (i == 2 && sides_match)
1227 t[2] = t[1];
1228 else {
1229 const struct object_id *oid = NULL;
1230 if (dirmask & 1)
1231 oid = &names[i].oid;
1232 buf[i] = fill_tree_descriptor(opt->repo,
1233 t + i, oid);
1235 dirmask >>= 1;
1238 original_dir_name = opti->current_dir_name;
1239 opti->current_dir_name = pi.string;
1240 if (renames->dir_rename_mask == 0 ||
1241 renames->dir_rename_mask == 0x07)
1242 ret = traverse_trees(NULL, 3, t, &newinfo);
1243 else
1244 ret = traverse_trees_wrapper(NULL, 3, t, &newinfo);
1245 opti->current_dir_name = original_dir_name;
1246 renames->dir_rename_mask = prev_dir_rename_mask;
1248 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++)
1249 free(buf[i]);
1251 if (ret < 0)
1252 return -1;
1255 return mask;
1258 static void resolve_trivial_directory_merge(struct conflict_info *ci, int side)
1260 VERIFY_CI(ci);
1261 assert((side == 1 && ci->match_mask == 5) ||
1262 (side == 2 && ci->match_mask == 3));
1263 oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
1264 ci->merged.result.mode = ci->stages[side].mode;
1265 ci->merged.is_null = is_null_oid(&ci->stages[side].oid);
1266 ci->match_mask = 0;
1267 ci->merged.clean = 1; /* (ci->filemask == 0); */
1270 static int handle_deferred_entries(struct merge_options *opt,
1271 struct traverse_info *info)
1273 struct rename_info *renames = &opt->priv->renames;
1274 struct hashmap_iter iter;
1275 struct strmap_entry *entry;
1276 int side, ret = 0;
1277 int path_count_before, path_count_after = 0;
1279 path_count_before = strmap_get_size(&opt->priv->paths);
1280 for (side = MERGE_SIDE1; side <= MERGE_SIDE2; side++) {
1281 unsigned optimization_okay = 1;
1282 struct strintmap copy;
1284 /* Loop over the set of paths we need to know rename info for */
1285 strset_for_each_entry(&renames->relevant_sources[side],
1286 &iter, entry) {
1287 char *rename_target, *dir, *dir_marker;
1288 struct strmap_entry *e;
1291 * If we don't know delete/rename info for this path,
1292 * then we need to recurse into all trees to get all
1293 * adds to make sure we have it.
1295 if (strset_contains(&renames->cached_irrelevant[side],
1296 entry->key))
1297 continue;
1298 e = strmap_get_entry(&renames->cached_pairs[side],
1299 entry->key);
1300 if (!e) {
1301 optimization_okay = 0;
1302 break;
1305 /* If this is a delete, we have enough info already */
1306 rename_target = e->value;
1307 if (!rename_target)
1308 continue;
1310 /* If we already walked the rename target, we're good */
1311 if (strmap_contains(&opt->priv->paths, rename_target))
1312 continue;
1315 * Otherwise, we need to get a list of directories that
1316 * will need to be recursed into to get this
1317 * rename_target.
1319 dir = xstrdup(rename_target);
1320 while ((dir_marker = strrchr(dir, '/'))) {
1321 *dir_marker = '\0';
1322 if (strset_contains(&renames->deferred[side].target_dirs,
1323 dir))
1324 break;
1325 strset_add(&renames->deferred[side].target_dirs,
1326 dir);
1328 free(dir);
1330 renames->deferred[side].trivial_merges_okay = optimization_okay;
1332 * We need to recurse into any directories in
1333 * possible_trivial_merges[side] found in target_dirs[side].
1334 * But when we recurse, we may need to queue up some of the
1335 * subdirectories for possible_trivial_merges[side]. Since
1336 * we can't safely iterate through a hashmap while also adding
1337 * entries, move the entries into 'copy', iterate over 'copy',
1338 * and then we'll also iterate anything added into
1339 * possible_trivial_merges[side] once this loop is done.
1341 copy = renames->deferred[side].possible_trivial_merges;
1342 strintmap_init_with_options(&renames->deferred[side].possible_trivial_merges,
1344 NULL,
1346 strintmap_for_each_entry(&copy, &iter, entry) {
1347 const char *path = entry->key;
1348 unsigned dir_rename_mask = (intptr_t)entry->value;
1349 struct conflict_info *ci;
1350 unsigned dirmask;
1351 struct tree_desc t[3];
1352 void *buf[3] = {NULL,};
1353 int i;
1355 ci = strmap_get(&opt->priv->paths, path);
1356 VERIFY_CI(ci);
1357 dirmask = ci->dirmask;
1359 if (optimization_okay &&
1360 !strset_contains(&renames->deferred[side].target_dirs,
1361 path)) {
1362 resolve_trivial_directory_merge(ci, side);
1363 continue;
1366 info->name = path;
1367 info->namelen = strlen(path);
1368 info->pathlen = info->namelen + 1;
1370 for (i = 0; i < 3; i++, dirmask >>= 1) {
1371 if (i == 1 && ci->match_mask == 3)
1372 t[1] = t[0];
1373 else if (i == 2 && ci->match_mask == 5)
1374 t[2] = t[0];
1375 else if (i == 2 && ci->match_mask == 6)
1376 t[2] = t[1];
1377 else {
1378 const struct object_id *oid = NULL;
1379 if (dirmask & 1)
1380 oid = &ci->stages[i].oid;
1381 buf[i] = fill_tree_descriptor(opt->repo,
1382 t+i, oid);
1386 ci->match_mask &= ci->filemask;
1387 opt->priv->current_dir_name = path;
1388 renames->dir_rename_mask = dir_rename_mask;
1389 if (renames->dir_rename_mask == 0 ||
1390 renames->dir_rename_mask == 0x07)
1391 ret = traverse_trees(NULL, 3, t, info);
1392 else
1393 ret = traverse_trees_wrapper(NULL, 3, t, info);
1395 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++)
1396 free(buf[i]);
1398 if (ret < 0)
1399 return ret;
1401 strintmap_clear(&copy);
1402 strintmap_for_each_entry(&renames->deferred[side].possible_trivial_merges,
1403 &iter, entry) {
1404 const char *path = entry->key;
1405 struct conflict_info *ci;
1407 ci = strmap_get(&opt->priv->paths, path);
1408 VERIFY_CI(ci);
1410 assert(renames->deferred[side].trivial_merges_okay &&
1411 !strset_contains(&renames->deferred[side].target_dirs,
1412 path));
1413 resolve_trivial_directory_merge(ci, side);
1415 if (!optimization_okay || path_count_after)
1416 path_count_after = strmap_get_size(&opt->priv->paths);
1418 if (path_count_after) {
1420 * The choice of wanted_factor here does not affect
1421 * correctness, only performance. When the
1422 * path_count_after / path_count_before
1423 * ratio is high, redoing after renames is a big
1424 * performance boost. I suspect that redoing is a wash
1425 * somewhere near a value of 2, and below that redoing will
1426 * slow things down. I applied a fudge factor and picked
1427 * 3; see the commit message when this was introduced for
1428 * back of the envelope calculations for this ratio.
1430 const int wanted_factor = 3;
1432 /* We should only redo collect_merge_info one time */
1433 assert(renames->redo_after_renames == 0);
1435 if (path_count_after / path_count_before >= wanted_factor) {
1436 renames->redo_after_renames = 1;
1437 renames->cached_pairs_valid_side = -1;
1439 } else if (renames->redo_after_renames == 2)
1440 renames->redo_after_renames = 0;
1441 return ret;
1444 static int collect_merge_info(struct merge_options *opt,
1445 struct tree *merge_base,
1446 struct tree *side1,
1447 struct tree *side2)
1449 int ret;
1450 struct tree_desc t[3];
1451 struct traverse_info info;
1453 opt->priv->toplevel_dir = "";
1454 opt->priv->current_dir_name = opt->priv->toplevel_dir;
1455 setup_traverse_info(&info, opt->priv->toplevel_dir);
1456 info.fn = collect_merge_info_callback;
1457 info.data = opt;
1458 info.show_all_errors = 1;
1460 parse_tree(merge_base);
1461 parse_tree(side1);
1462 parse_tree(side2);
1463 init_tree_desc(t + 0, merge_base->buffer, merge_base->size);
1464 init_tree_desc(t + 1, side1->buffer, side1->size);
1465 init_tree_desc(t + 2, side2->buffer, side2->size);
1467 trace2_region_enter("merge", "traverse_trees", opt->repo);
1468 ret = traverse_trees(NULL, 3, t, &info);
1469 if (ret == 0)
1470 ret = handle_deferred_entries(opt, &info);
1471 trace2_region_leave("merge", "traverse_trees", opt->repo);
1473 return ret;
1476 /*** Function Grouping: functions related to threeway content merges ***/
1478 static int find_first_merges(struct repository *repo,
1479 const char *path,
1480 struct commit *a,
1481 struct commit *b,
1482 struct object_array *result)
1484 int i, j;
1485 struct object_array merges = OBJECT_ARRAY_INIT;
1486 struct commit *commit;
1487 int contains_another;
1489 char merged_revision[GIT_MAX_HEXSZ + 2];
1490 const char *rev_args[] = { "rev-list", "--merges", "--ancestry-path",
1491 "--all", merged_revision, NULL };
1492 struct rev_info revs;
1493 struct setup_revision_opt rev_opts;
1495 memset(result, 0, sizeof(struct object_array));
1496 memset(&rev_opts, 0, sizeof(rev_opts));
1498 /* get all revisions that merge commit a */
1499 xsnprintf(merged_revision, sizeof(merged_revision), "^%s",
1500 oid_to_hex(&a->object.oid));
1501 repo_init_revisions(repo, &revs, NULL);
1502 rev_opts.submodule = path;
1503 /* FIXME: can't handle linked worktrees in submodules yet */
1504 revs.single_worktree = path != NULL;
1505 setup_revisions(ARRAY_SIZE(rev_args)-1, rev_args, &revs, &rev_opts);
1507 /* save all revisions from the above list that contain b */
1508 if (prepare_revision_walk(&revs))
1509 die("revision walk setup failed");
1510 while ((commit = get_revision(&revs)) != NULL) {
1511 struct object *o = &(commit->object);
1512 if (in_merge_bases(b, commit))
1513 add_object_array(o, NULL, &merges);
1515 reset_revision_walk();
1517 /* Now we've got all merges that contain a and b. Prune all
1518 * merges that contain another found merge and save them in
1519 * result.
1521 for (i = 0; i < merges.nr; i++) {
1522 struct commit *m1 = (struct commit *) merges.objects[i].item;
1524 contains_another = 0;
1525 for (j = 0; j < merges.nr; j++) {
1526 struct commit *m2 = (struct commit *) merges.objects[j].item;
1527 if (i != j && in_merge_bases(m2, m1)) {
1528 contains_another = 1;
1529 break;
1533 if (!contains_another)
1534 add_object_array(merges.objects[i].item, NULL, result);
1537 object_array_clear(&merges);
1538 return result->nr;
1541 static int merge_submodule(struct merge_options *opt,
1542 const char *path,
1543 const struct object_id *o,
1544 const struct object_id *a,
1545 const struct object_id *b,
1546 struct object_id *result)
1548 struct commit *commit_o, *commit_a, *commit_b;
1549 int parent_count;
1550 struct object_array merges;
1551 struct strbuf sb = STRBUF_INIT;
1553 int i;
1554 int search = !opt->priv->call_depth;
1556 /* store fallback answer in result in case we fail */
1557 oidcpy(result, opt->priv->call_depth ? o : a);
1559 /* we can not handle deletion conflicts */
1560 if (is_null_oid(o))
1561 return 0;
1562 if (is_null_oid(a))
1563 return 0;
1564 if (is_null_oid(b))
1565 return 0;
1567 if (add_submodule_odb(path)) {
1568 path_msg(opt, path, 0,
1569 _("Failed to merge submodule %s (not checked out)"),
1570 path);
1571 return 0;
1574 if (!(commit_o = lookup_commit_reference(opt->repo, o)) ||
1575 !(commit_a = lookup_commit_reference(opt->repo, a)) ||
1576 !(commit_b = lookup_commit_reference(opt->repo, b))) {
1577 path_msg(opt, path, 0,
1578 _("Failed to merge submodule %s (commits not present)"),
1579 path);
1580 return 0;
1583 /* check whether both changes are forward */
1584 if (!in_merge_bases(commit_o, commit_a) ||
1585 !in_merge_bases(commit_o, commit_b)) {
1586 path_msg(opt, path, 0,
1587 _("Failed to merge submodule %s "
1588 "(commits don't follow merge-base)"),
1589 path);
1590 return 0;
1593 /* Case #1: a is contained in b or vice versa */
1594 if (in_merge_bases(commit_a, commit_b)) {
1595 oidcpy(result, b);
1596 path_msg(opt, path, 1,
1597 _("Note: Fast-forwarding submodule %s to %s"),
1598 path, oid_to_hex(b));
1599 return 1;
1601 if (in_merge_bases(commit_b, commit_a)) {
1602 oidcpy(result, a);
1603 path_msg(opt, path, 1,
1604 _("Note: Fast-forwarding submodule %s to %s"),
1605 path, oid_to_hex(a));
1606 return 1;
1610 * Case #2: There are one or more merges that contain a and b in
1611 * the submodule. If there is only one, then present it as a
1612 * suggestion to the user, but leave it marked unmerged so the
1613 * user needs to confirm the resolution.
1616 /* Skip the search if makes no sense to the calling context. */
1617 if (!search)
1618 return 0;
1620 /* find commit which merges them */
1621 parent_count = find_first_merges(opt->repo, path, commit_a, commit_b,
1622 &merges);
1623 switch (parent_count) {
1624 case 0:
1625 path_msg(opt, path, 0, _("Failed to merge submodule %s"), path);
1626 break;
1628 case 1:
1629 format_commit(&sb, 4,
1630 (struct commit *)merges.objects[0].item);
1631 path_msg(opt, path, 0,
1632 _("Failed to merge submodule %s, but a possible merge "
1633 "resolution exists:\n%s\n"),
1634 path, sb.buf);
1635 path_msg(opt, path, 1,
1636 _("If this is correct simply add it to the index "
1637 "for example\n"
1638 "by using:\n\n"
1639 " git update-index --cacheinfo 160000 %s \"%s\"\n\n"
1640 "which will accept this suggestion.\n"),
1641 oid_to_hex(&merges.objects[0].item->oid), path);
1642 strbuf_release(&sb);
1643 break;
1644 default:
1645 for (i = 0; i < merges.nr; i++)
1646 format_commit(&sb, 4,
1647 (struct commit *)merges.objects[i].item);
1648 path_msg(opt, path, 0,
1649 _("Failed to merge submodule %s, but multiple "
1650 "possible merges exist:\n%s"), path, sb.buf);
1651 strbuf_release(&sb);
1654 object_array_clear(&merges);
1655 return 0;
1658 static void initialize_attr_index(struct merge_options *opt)
1661 * The renormalize_buffer() functions require attributes, and
1662 * annoyingly those can only be read from the working tree or from
1663 * an index_state. merge-ort doesn't have an index_state, so we
1664 * generate a fake one containing only attribute information.
1666 struct merged_info *mi;
1667 struct index_state *attr_index = &opt->priv->attr_index;
1668 struct cache_entry *ce;
1670 attr_index->initialized = 1;
1672 if (!opt->renormalize)
1673 return;
1675 mi = strmap_get(&opt->priv->paths, GITATTRIBUTES_FILE);
1676 if (!mi)
1677 return;
1679 if (mi->clean) {
1680 int len = strlen(GITATTRIBUTES_FILE);
1681 ce = make_empty_cache_entry(attr_index, len);
1682 ce->ce_mode = create_ce_mode(mi->result.mode);
1683 ce->ce_flags = create_ce_flags(0);
1684 ce->ce_namelen = len;
1685 oidcpy(&ce->oid, &mi->result.oid);
1686 memcpy(ce->name, GITATTRIBUTES_FILE, len);
1687 add_index_entry(attr_index, ce,
1688 ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
1689 get_stream_filter(attr_index, GITATTRIBUTES_FILE, &ce->oid);
1690 } else {
1691 int stage, len;
1692 struct conflict_info *ci;
1694 ASSIGN_AND_VERIFY_CI(ci, mi);
1695 for (stage = 0; stage < 3; stage++) {
1696 unsigned stage_mask = (1 << stage);
1698 if (!(ci->filemask & stage_mask))
1699 continue;
1700 len = strlen(GITATTRIBUTES_FILE);
1701 ce = make_empty_cache_entry(attr_index, len);
1702 ce->ce_mode = create_ce_mode(ci->stages[stage].mode);
1703 ce->ce_flags = create_ce_flags(stage);
1704 ce->ce_namelen = len;
1705 oidcpy(&ce->oid, &ci->stages[stage].oid);
1706 memcpy(ce->name, GITATTRIBUTES_FILE, len);
1707 add_index_entry(attr_index, ce,
1708 ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
1709 get_stream_filter(attr_index, GITATTRIBUTES_FILE,
1710 &ce->oid);
1715 static int merge_3way(struct merge_options *opt,
1716 const char *path,
1717 const struct object_id *o,
1718 const struct object_id *a,
1719 const struct object_id *b,
1720 const char *pathnames[3],
1721 const int extra_marker_size,
1722 mmbuffer_t *result_buf)
1724 mmfile_t orig, src1, src2;
1725 struct ll_merge_options ll_opts = {0};
1726 char *base, *name1, *name2;
1727 int merge_status;
1729 if (!opt->priv->attr_index.initialized)
1730 initialize_attr_index(opt);
1732 ll_opts.renormalize = opt->renormalize;
1733 ll_opts.extra_marker_size = extra_marker_size;
1734 ll_opts.xdl_opts = opt->xdl_opts;
1736 if (opt->priv->call_depth) {
1737 ll_opts.virtual_ancestor = 1;
1738 ll_opts.variant = 0;
1739 } else {
1740 switch (opt->recursive_variant) {
1741 case MERGE_VARIANT_OURS:
1742 ll_opts.variant = XDL_MERGE_FAVOR_OURS;
1743 break;
1744 case MERGE_VARIANT_THEIRS:
1745 ll_opts.variant = XDL_MERGE_FAVOR_THEIRS;
1746 break;
1747 default:
1748 ll_opts.variant = 0;
1749 break;
1753 assert(pathnames[0] && pathnames[1] && pathnames[2] && opt->ancestor);
1754 if (pathnames[0] == pathnames[1] && pathnames[1] == pathnames[2]) {
1755 base = mkpathdup("%s", opt->ancestor);
1756 name1 = mkpathdup("%s", opt->branch1);
1757 name2 = mkpathdup("%s", opt->branch2);
1758 } else {
1759 base = mkpathdup("%s:%s", opt->ancestor, pathnames[0]);
1760 name1 = mkpathdup("%s:%s", opt->branch1, pathnames[1]);
1761 name2 = mkpathdup("%s:%s", opt->branch2, pathnames[2]);
1764 read_mmblob(&orig, o);
1765 read_mmblob(&src1, a);
1766 read_mmblob(&src2, b);
1768 merge_status = ll_merge(result_buf, path, &orig, base,
1769 &src1, name1, &src2, name2,
1770 &opt->priv->attr_index, &ll_opts);
1772 free(base);
1773 free(name1);
1774 free(name2);
1775 free(orig.ptr);
1776 free(src1.ptr);
1777 free(src2.ptr);
1778 return merge_status;
1781 static int handle_content_merge(struct merge_options *opt,
1782 const char *path,
1783 const struct version_info *o,
1784 const struct version_info *a,
1785 const struct version_info *b,
1786 const char *pathnames[3],
1787 const int extra_marker_size,
1788 struct version_info *result)
1791 * path is the target location where we want to put the file, and
1792 * is used to determine any normalization rules in ll_merge.
1794 * The normal case is that path and all entries in pathnames are
1795 * identical, though renames can affect which path we got one of
1796 * the three blobs to merge on various sides of history.
1798 * extra_marker_size is the amount to extend conflict markers in
1799 * ll_merge; this is neeed if we have content merges of content
1800 * merges, which happens for example with rename/rename(2to1) and
1801 * rename/add conflicts.
1803 unsigned clean = 1;
1806 * handle_content_merge() needs both files to be of the same type, i.e.
1807 * both files OR both submodules OR both symlinks. Conflicting types
1808 * needs to be handled elsewhere.
1810 assert((S_IFMT & a->mode) == (S_IFMT & b->mode));
1812 /* Merge modes */
1813 if (a->mode == b->mode || a->mode == o->mode)
1814 result->mode = b->mode;
1815 else {
1816 /* must be the 100644/100755 case */
1817 assert(S_ISREG(a->mode));
1818 result->mode = a->mode;
1819 clean = (b->mode == o->mode);
1821 * FIXME: If opt->priv->call_depth && !clean, then we really
1822 * should not make result->mode match either a->mode or
1823 * b->mode; that causes t6036 "check conflicting mode for
1824 * regular file" to fail. It would be best to use some other
1825 * mode, but we'll confuse all kinds of stuff if we use one
1826 * where S_ISREG(result->mode) isn't true, and if we use
1827 * something like 0100666, then tree-walk.c's calls to
1828 * canon_mode() will just normalize that to 100644 for us and
1829 * thus not solve anything.
1831 * Figure out if there's some kind of way we can work around
1832 * this...
1837 * Trivial oid merge.
1839 * Note: While one might assume that the next four lines would
1840 * be unnecessary due to the fact that match_mask is often
1841 * setup and already handled, renames don't always take care
1842 * of that.
1844 if (oideq(&a->oid, &b->oid) || oideq(&a->oid, &o->oid))
1845 oidcpy(&result->oid, &b->oid);
1846 else if (oideq(&b->oid, &o->oid))
1847 oidcpy(&result->oid, &a->oid);
1849 /* Remaining rules depend on file vs. submodule vs. symlink. */
1850 else if (S_ISREG(a->mode)) {
1851 mmbuffer_t result_buf;
1852 int ret = 0, merge_status;
1853 int two_way;
1856 * If 'o' is different type, treat it as null so we do a
1857 * two-way merge.
1859 two_way = ((S_IFMT & o->mode) != (S_IFMT & a->mode));
1861 merge_status = merge_3way(opt, path,
1862 two_way ? null_oid() : &o->oid,
1863 &a->oid, &b->oid,
1864 pathnames, extra_marker_size,
1865 &result_buf);
1867 if ((merge_status < 0) || !result_buf.ptr)
1868 ret = err(opt, _("Failed to execute internal merge"));
1870 if (!ret &&
1871 write_object_file(result_buf.ptr, result_buf.size,
1872 blob_type, &result->oid))
1873 ret = err(opt, _("Unable to add %s to database"),
1874 path);
1876 free(result_buf.ptr);
1877 if (ret)
1878 return -1;
1879 clean &= (merge_status == 0);
1880 path_msg(opt, path, 1, _("Auto-merging %s"), path);
1881 } else if (S_ISGITLINK(a->mode)) {
1882 int two_way = ((S_IFMT & o->mode) != (S_IFMT & a->mode));
1883 clean = merge_submodule(opt, pathnames[0],
1884 two_way ? null_oid() : &o->oid,
1885 &a->oid, &b->oid, &result->oid);
1886 if (opt->priv->call_depth && two_way && !clean) {
1887 result->mode = o->mode;
1888 oidcpy(&result->oid, &o->oid);
1890 } else if (S_ISLNK(a->mode)) {
1891 if (opt->priv->call_depth) {
1892 clean = 0;
1893 result->mode = o->mode;
1894 oidcpy(&result->oid, &o->oid);
1895 } else {
1896 switch (opt->recursive_variant) {
1897 case MERGE_VARIANT_NORMAL:
1898 clean = 0;
1899 oidcpy(&result->oid, &a->oid);
1900 break;
1901 case MERGE_VARIANT_OURS:
1902 oidcpy(&result->oid, &a->oid);
1903 break;
1904 case MERGE_VARIANT_THEIRS:
1905 oidcpy(&result->oid, &b->oid);
1906 break;
1909 } else
1910 BUG("unsupported object type in the tree: %06o for %s",
1911 a->mode, path);
1913 return clean;
1916 /*** Function Grouping: functions related to detect_and_process_renames(), ***
1917 *** which are split into directory and regular rename detection sections. ***/
1919 /*** Function Grouping: functions related to directory rename detection ***/
1921 struct collision_info {
1922 struct string_list source_files;
1923 unsigned reported_already:1;
1927 * Return a new string that replaces the beginning portion (which matches
1928 * rename_info->key), with rename_info->util.new_dir. In perl-speak:
1929 * new_path_name = (old_path =~ s/rename_info->key/rename_info->value/);
1930 * NOTE:
1931 * Caller must ensure that old_path starts with rename_info->key + '/'.
1933 static char *apply_dir_rename(struct strmap_entry *rename_info,
1934 const char *old_path)
1936 struct strbuf new_path = STRBUF_INIT;
1937 const char *old_dir = rename_info->key;
1938 const char *new_dir = rename_info->value;
1939 int oldlen, newlen, new_dir_len;
1941 oldlen = strlen(old_dir);
1942 if (*new_dir == '\0')
1944 * If someone renamed/merged a subdirectory into the root
1945 * directory (e.g. 'some/subdir' -> ''), then we want to
1946 * avoid returning
1947 * '' + '/filename'
1948 * as the rename; we need to make old_path + oldlen advance
1949 * past the '/' character.
1951 oldlen++;
1952 new_dir_len = strlen(new_dir);
1953 newlen = new_dir_len + (strlen(old_path) - oldlen) + 1;
1954 strbuf_grow(&new_path, newlen);
1955 strbuf_add(&new_path, new_dir, new_dir_len);
1956 strbuf_addstr(&new_path, &old_path[oldlen]);
1958 return strbuf_detach(&new_path, NULL);
1961 static int path_in_way(struct strmap *paths, const char *path, unsigned side_mask)
1963 struct merged_info *mi = strmap_get(paths, path);
1964 struct conflict_info *ci;
1965 if (!mi)
1966 return 0;
1967 INITIALIZE_CI(ci, mi);
1968 return mi->clean || (side_mask & (ci->filemask | ci->dirmask));
1972 * See if there is a directory rename for path, and if there are any file
1973 * level conflicts on the given side for the renamed location. If there is
1974 * a rename and there are no conflicts, return the new name. Otherwise,
1975 * return NULL.
1977 static char *handle_path_level_conflicts(struct merge_options *opt,
1978 const char *path,
1979 unsigned side_index,
1980 struct strmap_entry *rename_info,
1981 struct strmap *collisions)
1983 char *new_path = NULL;
1984 struct collision_info *c_info;
1985 int clean = 1;
1986 struct strbuf collision_paths = STRBUF_INIT;
1989 * entry has the mapping of old directory name to new directory name
1990 * that we want to apply to path.
1992 new_path = apply_dir_rename(rename_info, path);
1993 if (!new_path)
1994 BUG("Failed to apply directory rename!");
1997 * The caller needs to have ensured that it has pre-populated
1998 * collisions with all paths that map to new_path. Do a quick check
1999 * to ensure that's the case.
2001 c_info = strmap_get(collisions, new_path);
2002 if (c_info == NULL)
2003 BUG("c_info is NULL");
2006 * Check for one-sided add/add/.../add conflicts, i.e.
2007 * where implicit renames from the other side doing
2008 * directory rename(s) can affect this side of history
2009 * to put multiple paths into the same location. Warn
2010 * and bail on directory renames for such paths.
2012 if (c_info->reported_already) {
2013 clean = 0;
2014 } else if (path_in_way(&opt->priv->paths, new_path, 1 << side_index)) {
2015 c_info->reported_already = 1;
2016 strbuf_add_separated_string_list(&collision_paths, ", ",
2017 &c_info->source_files);
2018 path_msg(opt, new_path, 0,
2019 _("CONFLICT (implicit dir rename): Existing file/dir "
2020 "at %s in the way of implicit directory rename(s) "
2021 "putting the following path(s) there: %s."),
2022 new_path, collision_paths.buf);
2023 clean = 0;
2024 } else if (c_info->source_files.nr > 1) {
2025 c_info->reported_already = 1;
2026 strbuf_add_separated_string_list(&collision_paths, ", ",
2027 &c_info->source_files);
2028 path_msg(opt, new_path, 0,
2029 _("CONFLICT (implicit dir rename): Cannot map more "
2030 "than one path to %s; implicit directory renames "
2031 "tried to put these paths there: %s"),
2032 new_path, collision_paths.buf);
2033 clean = 0;
2036 /* Free memory we no longer need */
2037 strbuf_release(&collision_paths);
2038 if (!clean && new_path) {
2039 free(new_path);
2040 return NULL;
2043 return new_path;
2046 static void get_provisional_directory_renames(struct merge_options *opt,
2047 unsigned side,
2048 int *clean)
2050 struct hashmap_iter iter;
2051 struct strmap_entry *entry;
2052 struct rename_info *renames = &opt->priv->renames;
2055 * Collapse
2056 * dir_rename_count: old_directory -> {new_directory -> count}
2057 * down to
2058 * dir_renames: old_directory -> best_new_directory
2059 * where best_new_directory is the one with the unique highest count.
2061 strmap_for_each_entry(&renames->dir_rename_count[side], &iter, entry) {
2062 const char *source_dir = entry->key;
2063 struct strintmap *counts = entry->value;
2064 struct hashmap_iter count_iter;
2065 struct strmap_entry *count_entry;
2066 int max = 0;
2067 int bad_max = 0;
2068 const char *best = NULL;
2070 strintmap_for_each_entry(counts, &count_iter, count_entry) {
2071 const char *target_dir = count_entry->key;
2072 intptr_t count = (intptr_t)count_entry->value;
2074 if (count == max)
2075 bad_max = max;
2076 else if (count > max) {
2077 max = count;
2078 best = target_dir;
2082 if (max == 0)
2083 continue;
2085 if (bad_max == max) {
2086 path_msg(opt, source_dir, 0,
2087 _("CONFLICT (directory rename split): "
2088 "Unclear where to rename %s to; it was "
2089 "renamed to multiple other directories, with "
2090 "no destination getting a majority of the "
2091 "files."),
2092 source_dir);
2093 *clean = 0;
2094 } else {
2095 strmap_put(&renames->dir_renames[side],
2096 source_dir, (void*)best);
2101 static void handle_directory_level_conflicts(struct merge_options *opt)
2103 struct hashmap_iter iter;
2104 struct strmap_entry *entry;
2105 struct string_list duplicated = STRING_LIST_INIT_NODUP;
2106 struct rename_info *renames = &opt->priv->renames;
2107 struct strmap *side1_dir_renames = &renames->dir_renames[MERGE_SIDE1];
2108 struct strmap *side2_dir_renames = &renames->dir_renames[MERGE_SIDE2];
2109 int i;
2111 strmap_for_each_entry(side1_dir_renames, &iter, entry) {
2112 if (strmap_contains(side2_dir_renames, entry->key))
2113 string_list_append(&duplicated, entry->key);
2116 for (i = 0; i < duplicated.nr; i++) {
2117 strmap_remove(side1_dir_renames, duplicated.items[i].string, 0);
2118 strmap_remove(side2_dir_renames, duplicated.items[i].string, 0);
2120 string_list_clear(&duplicated, 0);
2123 static struct strmap_entry *check_dir_renamed(const char *path,
2124 struct strmap *dir_renames)
2126 char *temp = xstrdup(path);
2127 char *end;
2128 struct strmap_entry *e = NULL;
2130 while ((end = strrchr(temp, '/'))) {
2131 *end = '\0';
2132 e = strmap_get_entry(dir_renames, temp);
2133 if (e)
2134 break;
2136 free(temp);
2137 return e;
2140 static void compute_collisions(struct strmap *collisions,
2141 struct strmap *dir_renames,
2142 struct diff_queue_struct *pairs)
2144 int i;
2146 strmap_init_with_options(collisions, NULL, 0);
2147 if (strmap_empty(dir_renames))
2148 return;
2151 * Multiple files can be mapped to the same path due to directory
2152 * renames done by the other side of history. Since that other
2153 * side of history could have merged multiple directories into one,
2154 * if our side of history added the same file basename to each of
2155 * those directories, then all N of them would get implicitly
2156 * renamed by the directory rename detection into the same path,
2157 * and we'd get an add/add/.../add conflict, and all those adds
2158 * from *this* side of history. This is not representable in the
2159 * index, and users aren't going to easily be able to make sense of
2160 * it. So we need to provide a good warning about what's
2161 * happening, and fall back to no-directory-rename detection
2162 * behavior for those paths.
2164 * See testcases 9e and all of section 5 from t6043 for examples.
2166 for (i = 0; i < pairs->nr; ++i) {
2167 struct strmap_entry *rename_info;
2168 struct collision_info *collision_info;
2169 char *new_path;
2170 struct diff_filepair *pair = pairs->queue[i];
2172 if (pair->status != 'A' && pair->status != 'R')
2173 continue;
2174 rename_info = check_dir_renamed(pair->two->path, dir_renames);
2175 if (!rename_info)
2176 continue;
2178 new_path = apply_dir_rename(rename_info, pair->two->path);
2179 assert(new_path);
2180 collision_info = strmap_get(collisions, new_path);
2181 if (collision_info) {
2182 free(new_path);
2183 } else {
2184 CALLOC_ARRAY(collision_info, 1);
2185 string_list_init_nodup(&collision_info->source_files);
2186 strmap_put(collisions, new_path, collision_info);
2188 string_list_insert(&collision_info->source_files,
2189 pair->two->path);
2193 static char *check_for_directory_rename(struct merge_options *opt,
2194 const char *path,
2195 unsigned side_index,
2196 struct strmap *dir_renames,
2197 struct strmap *dir_rename_exclusions,
2198 struct strmap *collisions,
2199 int *clean_merge)
2201 char *new_path = NULL;
2202 struct strmap_entry *rename_info;
2203 struct strmap_entry *otherinfo = NULL;
2204 const char *new_dir;
2206 if (strmap_empty(dir_renames))
2207 return new_path;
2208 rename_info = check_dir_renamed(path, dir_renames);
2209 if (!rename_info)
2210 return new_path;
2211 /* old_dir = rename_info->key; */
2212 new_dir = rename_info->value;
2215 * This next part is a little weird. We do not want to do an
2216 * implicit rename into a directory we renamed on our side, because
2217 * that will result in a spurious rename/rename(1to2) conflict. An
2218 * example:
2219 * Base commit: dumbdir/afile, otherdir/bfile
2220 * Side 1: smrtdir/afile, otherdir/bfile
2221 * Side 2: dumbdir/afile, dumbdir/bfile
2222 * Here, while working on Side 1, we could notice that otherdir was
2223 * renamed/merged to dumbdir, and change the diff_filepair for
2224 * otherdir/bfile into a rename into dumbdir/bfile. However, Side
2225 * 2 will notice the rename from dumbdir to smrtdir, and do the
2226 * transitive rename to move it from dumbdir/bfile to
2227 * smrtdir/bfile. That gives us bfile in dumbdir vs being in
2228 * smrtdir, a rename/rename(1to2) conflict. We really just want
2229 * the file to end up in smrtdir. And the way to achieve that is
2230 * to not let Side1 do the rename to dumbdir, since we know that is
2231 * the source of one of our directory renames.
2233 * That's why otherinfo and dir_rename_exclusions is here.
2235 * As it turns out, this also prevents N-way transient rename
2236 * confusion; See testcases 9c and 9d of t6043.
2238 otherinfo = strmap_get_entry(dir_rename_exclusions, new_dir);
2239 if (otherinfo) {
2240 path_msg(opt, rename_info->key, 1,
2241 _("WARNING: Avoiding applying %s -> %s rename "
2242 "to %s, because %s itself was renamed."),
2243 rename_info->key, new_dir, path, new_dir);
2244 return NULL;
2247 new_path = handle_path_level_conflicts(opt, path, side_index,
2248 rename_info, collisions);
2249 *clean_merge &= (new_path != NULL);
2251 return new_path;
2254 static void apply_directory_rename_modifications(struct merge_options *opt,
2255 struct diff_filepair *pair,
2256 char *new_path)
2259 * The basic idea is to get the conflict_info from opt->priv->paths
2260 * at old path, and insert it into new_path; basically just this:
2261 * ci = strmap_get(&opt->priv->paths, old_path);
2262 * strmap_remove(&opt->priv->paths, old_path, 0);
2263 * strmap_put(&opt->priv->paths, new_path, ci);
2264 * However, there are some factors complicating this:
2265 * - opt->priv->paths may already have an entry at new_path
2266 * - Each ci tracks its containing directory, so we need to
2267 * update that
2268 * - If another ci has the same containing directory, then
2269 * the two char*'s MUST point to the same location. See the
2270 * comment in struct merged_info. strcmp equality is not
2271 * enough; we need pointer equality.
2272 * - opt->priv->paths must hold the parent directories of any
2273 * entries that are added. So, if this directory rename
2274 * causes entirely new directories, we must recursively add
2275 * parent directories.
2276 * - For each parent directory added to opt->priv->paths, we
2277 * also need to get its parent directory stored in its
2278 * conflict_info->merged.directory_name with all the same
2279 * requirements about pointer equality.
2281 struct string_list dirs_to_insert = STRING_LIST_INIT_NODUP;
2282 struct conflict_info *ci, *new_ci;
2283 struct strmap_entry *entry;
2284 const char *branch_with_new_path, *branch_with_dir_rename;
2285 const char *old_path = pair->two->path;
2286 const char *parent_name;
2287 const char *cur_path;
2288 int i, len;
2290 entry = strmap_get_entry(&opt->priv->paths, old_path);
2291 old_path = entry->key;
2292 ci = entry->value;
2293 VERIFY_CI(ci);
2295 /* Find parent directories missing from opt->priv->paths */
2296 cur_path = new_path;
2297 while (1) {
2298 /* Find the parent directory of cur_path */
2299 char *last_slash = strrchr(cur_path, '/');
2300 if (last_slash) {
2301 parent_name = xstrndup(cur_path, last_slash - cur_path);
2302 } else {
2303 parent_name = opt->priv->toplevel_dir;
2304 break;
2307 /* Look it up in opt->priv->paths */
2308 entry = strmap_get_entry(&opt->priv->paths, parent_name);
2309 if (entry) {
2310 free((char*)parent_name);
2311 parent_name = entry->key; /* reuse known pointer */
2312 break;
2315 /* Record this is one of the directories we need to insert */
2316 string_list_append(&dirs_to_insert, parent_name);
2317 cur_path = parent_name;
2320 /* Traverse dirs_to_insert and insert them into opt->priv->paths */
2321 for (i = dirs_to_insert.nr-1; i >= 0; --i) {
2322 struct conflict_info *dir_ci;
2323 char *cur_dir = dirs_to_insert.items[i].string;
2325 CALLOC_ARRAY(dir_ci, 1);
2327 dir_ci->merged.directory_name = parent_name;
2328 len = strlen(parent_name);
2329 /* len+1 because of trailing '/' character */
2330 dir_ci->merged.basename_offset = (len > 0 ? len+1 : len);
2331 dir_ci->dirmask = ci->filemask;
2332 strmap_put(&opt->priv->paths, cur_dir, dir_ci);
2334 parent_name = cur_dir;
2338 * We are removing old_path from opt->priv->paths. old_path also will
2339 * eventually need to be freed, but it may still be used by e.g.
2340 * ci->pathnames. So, store it in another string-list for now.
2342 string_list_append(&opt->priv->paths_to_free, old_path);
2344 assert(ci->filemask == 2 || ci->filemask == 4);
2345 assert(ci->dirmask == 0);
2346 strmap_remove(&opt->priv->paths, old_path, 0);
2348 branch_with_new_path = (ci->filemask == 2) ? opt->branch1 : opt->branch2;
2349 branch_with_dir_rename = (ci->filemask == 2) ? opt->branch2 : opt->branch1;
2351 /* Now, finally update ci and stick it into opt->priv->paths */
2352 ci->merged.directory_name = parent_name;
2353 len = strlen(parent_name);
2354 ci->merged.basename_offset = (len > 0 ? len+1 : len);
2355 new_ci = strmap_get(&opt->priv->paths, new_path);
2356 if (!new_ci) {
2357 /* Place ci back into opt->priv->paths, but at new_path */
2358 strmap_put(&opt->priv->paths, new_path, ci);
2359 } else {
2360 int index;
2362 /* A few sanity checks */
2363 VERIFY_CI(new_ci);
2364 assert(ci->filemask == 2 || ci->filemask == 4);
2365 assert((new_ci->filemask & ci->filemask) == 0);
2366 assert(!new_ci->merged.clean);
2368 /* Copy stuff from ci into new_ci */
2369 new_ci->filemask |= ci->filemask;
2370 if (new_ci->dirmask)
2371 new_ci->df_conflict = 1;
2372 index = (ci->filemask >> 1);
2373 new_ci->pathnames[index] = ci->pathnames[index];
2374 new_ci->stages[index].mode = ci->stages[index].mode;
2375 oidcpy(&new_ci->stages[index].oid, &ci->stages[index].oid);
2377 free(ci);
2378 ci = new_ci;
2381 if (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE) {
2382 /* Notify user of updated path */
2383 if (pair->status == 'A')
2384 path_msg(opt, new_path, 1,
2385 _("Path updated: %s added in %s inside a "
2386 "directory that was renamed in %s; moving "
2387 "it to %s."),
2388 old_path, branch_with_new_path,
2389 branch_with_dir_rename, new_path);
2390 else
2391 path_msg(opt, new_path, 1,
2392 _("Path updated: %s renamed to %s in %s, "
2393 "inside a directory that was renamed in %s; "
2394 "moving it to %s."),
2395 pair->one->path, old_path, branch_with_new_path,
2396 branch_with_dir_rename, new_path);
2397 } else {
2399 * opt->detect_directory_renames has the value
2400 * MERGE_DIRECTORY_RENAMES_CONFLICT, so mark these as conflicts.
2402 ci->path_conflict = 1;
2403 if (pair->status == 'A')
2404 path_msg(opt, new_path, 0,
2405 _("CONFLICT (file location): %s added in %s "
2406 "inside a directory that was renamed in %s, "
2407 "suggesting it should perhaps be moved to "
2408 "%s."),
2409 old_path, branch_with_new_path,
2410 branch_with_dir_rename, new_path);
2411 else
2412 path_msg(opt, new_path, 0,
2413 _("CONFLICT (file location): %s renamed to %s "
2414 "in %s, inside a directory that was renamed "
2415 "in %s, suggesting it should perhaps be "
2416 "moved to %s."),
2417 pair->one->path, old_path, branch_with_new_path,
2418 branch_with_dir_rename, new_path);
2422 * Finally, record the new location.
2424 pair->two->path = new_path;
2427 /*** Function Grouping: functions related to regular rename detection ***/
2429 static int process_renames(struct merge_options *opt,
2430 struct diff_queue_struct *renames)
2432 int clean_merge = 1, i;
2434 for (i = 0; i < renames->nr; ++i) {
2435 const char *oldpath = NULL, *newpath;
2436 struct diff_filepair *pair = renames->queue[i];
2437 struct conflict_info *oldinfo = NULL, *newinfo = NULL;
2438 struct strmap_entry *old_ent, *new_ent;
2439 unsigned int old_sidemask;
2440 int target_index, other_source_index;
2441 int source_deleted, collision, type_changed;
2442 const char *rename_branch = NULL, *delete_branch = NULL;
2444 old_ent = strmap_get_entry(&opt->priv->paths, pair->one->path);
2445 new_ent = strmap_get_entry(&opt->priv->paths, pair->two->path);
2446 if (old_ent) {
2447 oldpath = old_ent->key;
2448 oldinfo = old_ent->value;
2450 newpath = pair->two->path;
2451 if (new_ent) {
2452 newpath = new_ent->key;
2453 newinfo = new_ent->value;
2457 * If pair->one->path isn't in opt->priv->paths, that means
2458 * that either directory rename detection removed that
2459 * path, or a parent directory of oldpath was resolved and
2460 * we don't even need the rename; in either case, we can
2461 * skip it. If oldinfo->merged.clean, then the other side
2462 * of history had no changes to oldpath and we don't need
2463 * the rename and can skip it.
2465 if (!oldinfo || oldinfo->merged.clean)
2466 continue;
2469 * diff_filepairs have copies of pathnames, thus we have to
2470 * use standard 'strcmp()' (negated) instead of '=='.
2472 if (i + 1 < renames->nr &&
2473 !strcmp(oldpath, renames->queue[i+1]->one->path)) {
2474 /* Handle rename/rename(1to2) or rename/rename(1to1) */
2475 const char *pathnames[3];
2476 struct version_info merged;
2477 struct conflict_info *base, *side1, *side2;
2478 unsigned was_binary_blob = 0;
2480 pathnames[0] = oldpath;
2481 pathnames[1] = newpath;
2482 pathnames[2] = renames->queue[i+1]->two->path;
2484 base = strmap_get(&opt->priv->paths, pathnames[0]);
2485 side1 = strmap_get(&opt->priv->paths, pathnames[1]);
2486 side2 = strmap_get(&opt->priv->paths, pathnames[2]);
2488 VERIFY_CI(base);
2489 VERIFY_CI(side1);
2490 VERIFY_CI(side2);
2492 if (!strcmp(pathnames[1], pathnames[2])) {
2493 struct rename_info *ri = &opt->priv->renames;
2494 int j;
2496 /* Both sides renamed the same way */
2497 assert(side1 == side2);
2498 memcpy(&side1->stages[0], &base->stages[0],
2499 sizeof(merged));
2500 side1->filemask |= (1 << MERGE_BASE);
2501 /* Mark base as resolved by removal */
2502 base->merged.is_null = 1;
2503 base->merged.clean = 1;
2506 * Disable remembering renames optimization;
2507 * rename/rename(1to1) is incredibly rare, and
2508 * just disabling the optimization is easier
2509 * than purging cached_pairs,
2510 * cached_target_names, and dir_rename_counts.
2512 for (j = 0; j < 3; j++)
2513 ri->merge_trees[j] = NULL;
2515 /* We handled both renames, i.e. i+1 handled */
2516 i++;
2517 /* Move to next rename */
2518 continue;
2521 /* This is a rename/rename(1to2) */
2522 clean_merge = handle_content_merge(opt,
2523 pair->one->path,
2524 &base->stages[0],
2525 &side1->stages[1],
2526 &side2->stages[2],
2527 pathnames,
2528 1 + 2 * opt->priv->call_depth,
2529 &merged);
2530 if (!clean_merge &&
2531 merged.mode == side1->stages[1].mode &&
2532 oideq(&merged.oid, &side1->stages[1].oid))
2533 was_binary_blob = 1;
2534 memcpy(&side1->stages[1], &merged, sizeof(merged));
2535 if (was_binary_blob) {
2537 * Getting here means we were attempting to
2538 * merge a binary blob.
2540 * Since we can't merge binaries,
2541 * handle_content_merge() just takes one
2542 * side. But we don't want to copy the
2543 * contents of one side to both paths. We
2544 * used the contents of side1 above for
2545 * side1->stages, let's use the contents of
2546 * side2 for side2->stages below.
2548 oidcpy(&merged.oid, &side2->stages[2].oid);
2549 merged.mode = side2->stages[2].mode;
2551 memcpy(&side2->stages[2], &merged, sizeof(merged));
2553 side1->path_conflict = 1;
2554 side2->path_conflict = 1;
2556 * TODO: For renames we normally remove the path at the
2557 * old name. It would thus seem consistent to do the
2558 * same for rename/rename(1to2) cases, but we haven't
2559 * done so traditionally and a number of the regression
2560 * tests now encode an expectation that the file is
2561 * left there at stage 1. If we ever decide to change
2562 * this, add the following two lines here:
2563 * base->merged.is_null = 1;
2564 * base->merged.clean = 1;
2565 * and remove the setting of base->path_conflict to 1.
2567 base->path_conflict = 1;
2568 path_msg(opt, oldpath, 0,
2569 _("CONFLICT (rename/rename): %s renamed to "
2570 "%s in %s and to %s in %s."),
2571 pathnames[0],
2572 pathnames[1], opt->branch1,
2573 pathnames[2], opt->branch2);
2575 i++; /* We handled both renames, i.e. i+1 handled */
2576 continue;
2579 VERIFY_CI(oldinfo);
2580 VERIFY_CI(newinfo);
2581 target_index = pair->score; /* from collect_renames() */
2582 assert(target_index == 1 || target_index == 2);
2583 other_source_index = 3 - target_index;
2584 old_sidemask = (1 << other_source_index); /* 2 or 4 */
2585 source_deleted = (oldinfo->filemask == 1);
2586 collision = ((newinfo->filemask & old_sidemask) != 0);
2587 type_changed = !source_deleted &&
2588 (S_ISREG(oldinfo->stages[other_source_index].mode) !=
2589 S_ISREG(newinfo->stages[target_index].mode));
2590 if (type_changed && collision) {
2592 * special handling so later blocks can handle this...
2594 * if type_changed && collision are both true, then this
2595 * was really a double rename, but one side wasn't
2596 * detected due to lack of break detection. I.e.
2597 * something like
2598 * orig: has normal file 'foo'
2599 * side1: renames 'foo' to 'bar', adds 'foo' symlink
2600 * side2: renames 'foo' to 'bar'
2601 * In this case, the foo->bar rename on side1 won't be
2602 * detected because the new symlink named 'foo' is
2603 * there and we don't do break detection. But we detect
2604 * this here because we don't want to merge the content
2605 * of the foo symlink with the foo->bar file, so we
2606 * have some logic to handle this special case. The
2607 * easiest way to do that is make 'bar' on side1 not
2608 * be considered a colliding file but the other part
2609 * of a normal rename. If the file is very different,
2610 * well we're going to get content merge conflicts
2611 * anyway so it doesn't hurt. And if the colliding
2612 * file also has a different type, that'll be handled
2613 * by the content merge logic in process_entry() too.
2615 * See also t6430, 'rename vs. rename/symlink'
2617 collision = 0;
2619 if (source_deleted) {
2620 if (target_index == 1) {
2621 rename_branch = opt->branch1;
2622 delete_branch = opt->branch2;
2623 } else {
2624 rename_branch = opt->branch2;
2625 delete_branch = opt->branch1;
2629 assert(source_deleted || oldinfo->filemask & old_sidemask);
2631 /* Need to check for special types of rename conflicts... */
2632 if (collision && !source_deleted) {
2633 /* collision: rename/add or rename/rename(2to1) */
2634 const char *pathnames[3];
2635 struct version_info merged;
2637 struct conflict_info *base, *side1, *side2;
2638 unsigned clean;
2640 pathnames[0] = oldpath;
2641 pathnames[other_source_index] = oldpath;
2642 pathnames[target_index] = newpath;
2644 base = strmap_get(&opt->priv->paths, pathnames[0]);
2645 side1 = strmap_get(&opt->priv->paths, pathnames[1]);
2646 side2 = strmap_get(&opt->priv->paths, pathnames[2]);
2648 VERIFY_CI(base);
2649 VERIFY_CI(side1);
2650 VERIFY_CI(side2);
2652 clean = handle_content_merge(opt, pair->one->path,
2653 &base->stages[0],
2654 &side1->stages[1],
2655 &side2->stages[2],
2656 pathnames,
2657 1 + 2 * opt->priv->call_depth,
2658 &merged);
2660 memcpy(&newinfo->stages[target_index], &merged,
2661 sizeof(merged));
2662 if (!clean) {
2663 path_msg(opt, newpath, 0,
2664 _("CONFLICT (rename involved in "
2665 "collision): rename of %s -> %s has "
2666 "content conflicts AND collides "
2667 "with another path; this may result "
2668 "in nested conflict markers."),
2669 oldpath, newpath);
2671 } else if (collision && source_deleted) {
2673 * rename/add/delete or rename/rename(2to1)/delete:
2674 * since oldpath was deleted on the side that didn't
2675 * do the rename, there's not much of a content merge
2676 * we can do for the rename. oldinfo->merged.is_null
2677 * was already set, so we just leave things as-is so
2678 * they look like an add/add conflict.
2681 newinfo->path_conflict = 1;
2682 path_msg(opt, newpath, 0,
2683 _("CONFLICT (rename/delete): %s renamed "
2684 "to %s in %s, but deleted in %s."),
2685 oldpath, newpath, rename_branch, delete_branch);
2686 } else {
2688 * a few different cases...start by copying the
2689 * existing stage(s) from oldinfo over the newinfo
2690 * and update the pathname(s).
2692 memcpy(&newinfo->stages[0], &oldinfo->stages[0],
2693 sizeof(newinfo->stages[0]));
2694 newinfo->filemask |= (1 << MERGE_BASE);
2695 newinfo->pathnames[0] = oldpath;
2696 if (type_changed) {
2697 /* rename vs. typechange */
2698 /* Mark the original as resolved by removal */
2699 memcpy(&oldinfo->stages[0].oid, null_oid(),
2700 sizeof(oldinfo->stages[0].oid));
2701 oldinfo->stages[0].mode = 0;
2702 oldinfo->filemask &= 0x06;
2703 } else if (source_deleted) {
2704 /* rename/delete */
2705 newinfo->path_conflict = 1;
2706 path_msg(opt, newpath, 0,
2707 _("CONFLICT (rename/delete): %s renamed"
2708 " to %s in %s, but deleted in %s."),
2709 oldpath, newpath,
2710 rename_branch, delete_branch);
2711 } else {
2712 /* normal rename */
2713 memcpy(&newinfo->stages[other_source_index],
2714 &oldinfo->stages[other_source_index],
2715 sizeof(newinfo->stages[0]));
2716 newinfo->filemask |= (1 << other_source_index);
2717 newinfo->pathnames[other_source_index] = oldpath;
2721 if (!type_changed) {
2722 /* Mark the original as resolved by removal */
2723 oldinfo->merged.is_null = 1;
2724 oldinfo->merged.clean = 1;
2729 return clean_merge;
2732 static inline int possible_side_renames(struct rename_info *renames,
2733 unsigned side_index)
2735 return renames->pairs[side_index].nr > 0 &&
2736 !strintmap_empty(&renames->relevant_sources[side_index]);
2739 static inline int possible_renames(struct rename_info *renames)
2741 return possible_side_renames(renames, 1) ||
2742 possible_side_renames(renames, 2) ||
2743 !strmap_empty(&renames->cached_pairs[1]) ||
2744 !strmap_empty(&renames->cached_pairs[2]);
2747 static void resolve_diffpair_statuses(struct diff_queue_struct *q)
2750 * A simplified version of diff_resolve_rename_copy(); would probably
2751 * just use that function but it's static...
2753 int i;
2754 struct diff_filepair *p;
2756 for (i = 0; i < q->nr; ++i) {
2757 p = q->queue[i];
2758 p->status = 0; /* undecided */
2759 if (!DIFF_FILE_VALID(p->one))
2760 p->status = DIFF_STATUS_ADDED;
2761 else if (!DIFF_FILE_VALID(p->two))
2762 p->status = DIFF_STATUS_DELETED;
2763 else if (DIFF_PAIR_RENAME(p))
2764 p->status = DIFF_STATUS_RENAMED;
2768 static void prune_cached_from_relevant(struct rename_info *renames,
2769 unsigned side)
2771 /* Reason for this function described in add_pair() */
2772 struct hashmap_iter iter;
2773 struct strmap_entry *entry;
2775 /* Remove from relevant_sources all entries in cached_pairs[side] */
2776 strmap_for_each_entry(&renames->cached_pairs[side], &iter, entry) {
2777 strintmap_remove(&renames->relevant_sources[side],
2778 entry->key);
2780 /* Remove from relevant_sources all entries in cached_irrelevant[side] */
2781 strset_for_each_entry(&renames->cached_irrelevant[side], &iter, entry) {
2782 strintmap_remove(&renames->relevant_sources[side],
2783 entry->key);
2787 static void use_cached_pairs(struct merge_options *opt,
2788 struct strmap *cached_pairs,
2789 struct diff_queue_struct *pairs)
2791 struct hashmap_iter iter;
2792 struct strmap_entry *entry;
2795 * Add to side_pairs all entries from renames->cached_pairs[side_index].
2796 * (Info in cached_irrelevant[side_index] is not relevant here.)
2798 strmap_for_each_entry(cached_pairs, &iter, entry) {
2799 struct diff_filespec *one, *two;
2800 const char *old_name = entry->key;
2801 const char *new_name = entry->value;
2802 if (!new_name)
2803 new_name = old_name;
2805 /* We don't care about oid/mode, only filenames and status */
2806 one = alloc_filespec(old_name);
2807 two = alloc_filespec(new_name);
2808 diff_queue(pairs, one, two);
2809 pairs->queue[pairs->nr-1]->status = entry->value ? 'R' : 'D';
2813 static void cache_new_pair(struct rename_info *renames,
2814 int side,
2815 char *old_path,
2816 char *new_path,
2817 int free_old_value)
2819 char *old_value;
2820 new_path = xstrdup(new_path);
2821 old_value = strmap_put(&renames->cached_pairs[side],
2822 old_path, new_path);
2823 strset_add(&renames->cached_target_names[side], new_path);
2824 if (free_old_value)
2825 free(old_value);
2826 else
2827 assert(!old_value);
2830 static void possibly_cache_new_pair(struct rename_info *renames,
2831 struct diff_filepair *p,
2832 unsigned side,
2833 char *new_path)
2835 int dir_renamed_side = 0;
2837 if (new_path) {
2839 * Directory renames happen on the other side of history from
2840 * the side that adds new files to the old directory.
2842 dir_renamed_side = 3 - side;
2843 } else {
2844 int val = strintmap_get(&renames->relevant_sources[side],
2845 p->one->path);
2846 if (val == RELEVANT_NO_MORE) {
2847 assert(p->status == 'D');
2848 strset_add(&renames->cached_irrelevant[side],
2849 p->one->path);
2851 if (val <= 0)
2852 return;
2855 if (p->status == 'D') {
2857 * If we already had this delete, we'll just set it's value
2858 * to NULL again, so no harm.
2860 strmap_put(&renames->cached_pairs[side], p->one->path, NULL);
2861 } else if (p->status == 'R') {
2862 if (!new_path)
2863 new_path = p->two->path;
2864 else
2865 cache_new_pair(renames, dir_renamed_side,
2866 p->two->path, new_path, 0);
2867 cache_new_pair(renames, side, p->one->path, new_path, 1);
2868 } else if (p->status == 'A' && new_path) {
2869 cache_new_pair(renames, dir_renamed_side,
2870 p->two->path, new_path, 0);
2874 static int compare_pairs(const void *a_, const void *b_)
2876 const struct diff_filepair *a = *((const struct diff_filepair **)a_);
2877 const struct diff_filepair *b = *((const struct diff_filepair **)b_);
2879 return strcmp(a->one->path, b->one->path);
2882 /* Call diffcore_rename() to update deleted/added pairs into rename pairs */
2883 static int detect_regular_renames(struct merge_options *opt,
2884 unsigned side_index)
2886 struct diff_options diff_opts;
2887 struct rename_info *renames = &opt->priv->renames;
2889 prune_cached_from_relevant(renames, side_index);
2890 if (!possible_side_renames(renames, side_index)) {
2892 * No rename detection needed for this side, but we still need
2893 * to make sure 'adds' are marked correctly in case the other
2894 * side had directory renames.
2896 resolve_diffpair_statuses(&renames->pairs[side_index]);
2897 return 0;
2900 partial_clear_dir_rename_count(&renames->dir_rename_count[side_index]);
2901 repo_diff_setup(opt->repo, &diff_opts);
2902 diff_opts.flags.recursive = 1;
2903 diff_opts.flags.rename_empty = 0;
2904 diff_opts.detect_rename = DIFF_DETECT_RENAME;
2905 diff_opts.rename_limit = opt->rename_limit;
2906 if (opt->rename_limit <= 0)
2907 diff_opts.rename_limit = 7000;
2908 diff_opts.rename_score = opt->rename_score;
2909 diff_opts.show_rename_progress = opt->show_rename_progress;
2910 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
2911 diff_setup_done(&diff_opts);
2913 diff_queued_diff = renames->pairs[side_index];
2914 trace2_region_enter("diff", "diffcore_rename", opt->repo);
2915 diffcore_rename_extended(&diff_opts,
2916 &renames->relevant_sources[side_index],
2917 &renames->dirs_removed[side_index],
2918 &renames->dir_rename_count[side_index],
2919 &renames->cached_pairs[side_index]);
2920 trace2_region_leave("diff", "diffcore_rename", opt->repo);
2921 resolve_diffpair_statuses(&diff_queued_diff);
2923 if (diff_opts.needed_rename_limit > 0)
2924 renames->redo_after_renames = 0;
2925 if (diff_opts.needed_rename_limit > renames->needed_limit)
2926 renames->needed_limit = diff_opts.needed_rename_limit;
2928 renames->pairs[side_index] = diff_queued_diff;
2930 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
2931 diff_queued_diff.nr = 0;
2932 diff_queued_diff.queue = NULL;
2933 diff_flush(&diff_opts);
2935 return 1;
2939 * Get information of all renames which occurred in 'side_pairs', making use
2940 * of any implicit directory renames in side_dir_renames (also making use of
2941 * implicit directory renames rename_exclusions as needed by
2942 * check_for_directory_rename()). Add all (updated) renames into result.
2944 static int collect_renames(struct merge_options *opt,
2945 struct diff_queue_struct *result,
2946 unsigned side_index,
2947 struct strmap *dir_renames_for_side,
2948 struct strmap *rename_exclusions)
2950 int i, clean = 1;
2951 struct strmap collisions;
2952 struct diff_queue_struct *side_pairs;
2953 struct hashmap_iter iter;
2954 struct strmap_entry *entry;
2955 struct rename_info *renames = &opt->priv->renames;
2957 side_pairs = &renames->pairs[side_index];
2958 compute_collisions(&collisions, dir_renames_for_side, side_pairs);
2960 for (i = 0; i < side_pairs->nr; ++i) {
2961 struct diff_filepair *p = side_pairs->queue[i];
2962 char *new_path; /* non-NULL only with directory renames */
2964 if (p->status != 'A' && p->status != 'R') {
2965 possibly_cache_new_pair(renames, p, side_index, NULL);
2966 diff_free_filepair(p);
2967 continue;
2970 new_path = check_for_directory_rename(opt, p->two->path,
2971 side_index,
2972 dir_renames_for_side,
2973 rename_exclusions,
2974 &collisions,
2975 &clean);
2977 possibly_cache_new_pair(renames, p, side_index, new_path);
2978 if (p->status != 'R' && !new_path) {
2979 diff_free_filepair(p);
2980 continue;
2983 if (new_path)
2984 apply_directory_rename_modifications(opt, p, new_path);
2987 * p->score comes back from diffcore_rename_extended() with
2988 * the similarity of the renamed file. The similarity is
2989 * was used to determine that the two files were related
2990 * and are a rename, which we have already used, but beyond
2991 * that we have no use for the similarity. So p->score is
2992 * now irrelevant. However, process_renames() will need to
2993 * know which side of the merge this rename was associated
2994 * with, so overwrite p->score with that value.
2996 p->score = side_index;
2997 result->queue[result->nr++] = p;
3000 /* Free each value in the collisions map */
3001 strmap_for_each_entry(&collisions, &iter, entry) {
3002 struct collision_info *info = entry->value;
3003 string_list_clear(&info->source_files, 0);
3006 * In compute_collisions(), we set collisions.strdup_strings to 0
3007 * so that we wouldn't have to make another copy of the new_path
3008 * allocated by apply_dir_rename(). But now that we've used them
3009 * and have no other references to these strings, it is time to
3010 * deallocate them.
3012 free_strmap_strings(&collisions);
3013 strmap_clear(&collisions, 1);
3014 return clean;
3017 static int detect_and_process_renames(struct merge_options *opt,
3018 struct tree *merge_base,
3019 struct tree *side1,
3020 struct tree *side2)
3022 struct diff_queue_struct combined;
3023 struct rename_info *renames = &opt->priv->renames;
3024 int need_dir_renames, s, clean = 1;
3025 unsigned detection_run = 0;
3027 memset(&combined, 0, sizeof(combined));
3028 if (!possible_renames(renames))
3029 goto cleanup;
3031 trace2_region_enter("merge", "regular renames", opt->repo);
3032 detection_run |= detect_regular_renames(opt, MERGE_SIDE1);
3033 detection_run |= detect_regular_renames(opt, MERGE_SIDE2);
3034 if (renames->redo_after_renames && detection_run) {
3035 int i, side;
3036 struct diff_filepair *p;
3038 /* Cache the renames, we found */
3039 for (side = MERGE_SIDE1; side <= MERGE_SIDE2; side++) {
3040 for (i = 0; i < renames->pairs[side].nr; ++i) {
3041 p = renames->pairs[side].queue[i];
3042 possibly_cache_new_pair(renames, p, side, NULL);
3046 /* Restart the merge with the cached renames */
3047 renames->redo_after_renames = 2;
3048 trace2_region_leave("merge", "regular renames", opt->repo);
3049 goto cleanup;
3051 use_cached_pairs(opt, &renames->cached_pairs[1], &renames->pairs[1]);
3052 use_cached_pairs(opt, &renames->cached_pairs[2], &renames->pairs[2]);
3053 trace2_region_leave("merge", "regular renames", opt->repo);
3055 trace2_region_enter("merge", "directory renames", opt->repo);
3056 need_dir_renames =
3057 !opt->priv->call_depth &&
3058 (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE ||
3059 opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_CONFLICT);
3061 if (need_dir_renames) {
3062 get_provisional_directory_renames(opt, MERGE_SIDE1, &clean);
3063 get_provisional_directory_renames(opt, MERGE_SIDE2, &clean);
3064 handle_directory_level_conflicts(opt);
3067 ALLOC_GROW(combined.queue,
3068 renames->pairs[1].nr + renames->pairs[2].nr,
3069 combined.alloc);
3070 clean &= collect_renames(opt, &combined, MERGE_SIDE1,
3071 &renames->dir_renames[2],
3072 &renames->dir_renames[1]);
3073 clean &= collect_renames(opt, &combined, MERGE_SIDE2,
3074 &renames->dir_renames[1],
3075 &renames->dir_renames[2]);
3076 STABLE_QSORT(combined.queue, combined.nr, compare_pairs);
3077 trace2_region_leave("merge", "directory renames", opt->repo);
3079 trace2_region_enter("merge", "process renames", opt->repo);
3080 clean &= process_renames(opt, &combined);
3081 trace2_region_leave("merge", "process renames", opt->repo);
3083 goto simple_cleanup; /* collect_renames() handles some of cleanup */
3085 cleanup:
3087 * Free now unneeded filepairs, which would have been handled
3088 * in collect_renames() normally but we skipped that code.
3090 for (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {
3091 struct diff_queue_struct *side_pairs;
3092 int i;
3094 side_pairs = &renames->pairs[s];
3095 for (i = 0; i < side_pairs->nr; ++i) {
3096 struct diff_filepair *p = side_pairs->queue[i];
3097 diff_free_filepair(p);
3101 simple_cleanup:
3102 /* Free memory for renames->pairs[] and combined */
3103 for (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {
3104 free(renames->pairs[s].queue);
3105 DIFF_QUEUE_CLEAR(&renames->pairs[s]);
3107 if (combined.nr) {
3108 int i;
3109 for (i = 0; i < combined.nr; i++)
3110 diff_free_filepair(combined.queue[i]);
3111 free(combined.queue);
3114 return clean;
3117 /*** Function Grouping: functions related to process_entries() ***/
3119 static int sort_dirs_next_to_their_children(const char *one, const char *two)
3121 unsigned char c1, c2;
3124 * Here we only care that entries for directories appear adjacent
3125 * to and before files underneath the directory. We can achieve
3126 * that by pretending to add a trailing slash to every file and
3127 * then sorting. In other words, we do not want the natural
3128 * sorting of
3129 * foo
3130 * foo.txt
3131 * foo/bar
3132 * Instead, we want "foo" to sort as though it were "foo/", so that
3133 * we instead get
3134 * foo.txt
3135 * foo
3136 * foo/bar
3137 * To achieve this, we basically implement our own strcmp, except that
3138 * if we get to the end of either string instead of comparing NUL to
3139 * another character, we compare '/' to it.
3141 * If this unusual "sort as though '/' were appended" perplexes
3142 * you, perhaps it will help to note that this is not the final
3143 * sort. write_tree() will sort again without the trailing slash
3144 * magic, but just on paths immediately under a given tree.
3146 * The reason to not use df_name_compare directly was that it was
3147 * just too expensive (we don't have the string lengths handy), so
3148 * it was reimplemented.
3152 * NOTE: This function will never be called with two equal strings,
3153 * because it is used to sort the keys of a strmap, and strmaps have
3154 * unique keys by construction. That simplifies our c1==c2 handling
3155 * below.
3158 while (*one && (*one == *two)) {
3159 one++;
3160 two++;
3163 c1 = *one ? *one : '/';
3164 c2 = *two ? *two : '/';
3166 if (c1 == c2) {
3167 /* Getting here means one is a leading directory of the other */
3168 return (*one) ? 1 : -1;
3169 } else
3170 return c1 - c2;
3173 static int read_oid_strbuf(struct merge_options *opt,
3174 const struct object_id *oid,
3175 struct strbuf *dst)
3177 void *buf;
3178 enum object_type type;
3179 unsigned long size;
3180 buf = read_object_file(oid, &type, &size);
3181 if (!buf)
3182 return err(opt, _("cannot read object %s"), oid_to_hex(oid));
3183 if (type != OBJ_BLOB) {
3184 free(buf);
3185 return err(opt, _("object %s is not a blob"), oid_to_hex(oid));
3187 strbuf_attach(dst, buf, size, size + 1);
3188 return 0;
3191 static int blob_unchanged(struct merge_options *opt,
3192 const struct version_info *base,
3193 const struct version_info *side,
3194 const char *path)
3196 struct strbuf basebuf = STRBUF_INIT;
3197 struct strbuf sidebuf = STRBUF_INIT;
3198 int ret = 0; /* assume changed for safety */
3199 struct index_state *idx = &opt->priv->attr_index;
3201 if (!idx->initialized)
3202 initialize_attr_index(opt);
3204 if (base->mode != side->mode)
3205 return 0;
3206 if (oideq(&base->oid, &side->oid))
3207 return 1;
3209 if (read_oid_strbuf(opt, &base->oid, &basebuf) ||
3210 read_oid_strbuf(opt, &side->oid, &sidebuf))
3211 goto error_return;
3213 * Note: binary | is used so that both renormalizations are
3214 * performed. Comparison can be skipped if both files are
3215 * unchanged since their sha1s have already been compared.
3217 if (renormalize_buffer(idx, path, basebuf.buf, basebuf.len, &basebuf) |
3218 renormalize_buffer(idx, path, sidebuf.buf, sidebuf.len, &sidebuf))
3219 ret = (basebuf.len == sidebuf.len &&
3220 !memcmp(basebuf.buf, sidebuf.buf, basebuf.len));
3222 error_return:
3223 strbuf_release(&basebuf);
3224 strbuf_release(&sidebuf);
3225 return ret;
3228 struct directory_versions {
3230 * versions: list of (basename -> version_info)
3232 * The basenames are in reverse lexicographic order of full pathnames,
3233 * as processed in process_entries(). This puts all entries within
3234 * a directory together, and covers the directory itself after
3235 * everything within it, allowing us to write subtrees before needing
3236 * to record information for the tree itself.
3238 struct string_list versions;
3241 * offsets: list of (full relative path directories -> integer offsets)
3243 * Since versions contains basenames from files in multiple different
3244 * directories, we need to know which entries in versions correspond
3245 * to which directories. Values of e.g.
3246 * "" 0
3247 * src 2
3248 * src/moduleA 5
3249 * Would mean that entries 0-1 of versions are files in the toplevel
3250 * directory, entries 2-4 are files under src/, and the remaining
3251 * entries starting at index 5 are files under src/moduleA/.
3253 struct string_list offsets;
3256 * last_directory: directory that previously processed file found in
3258 * last_directory starts NULL, but records the directory in which the
3259 * previous file was found within. As soon as
3260 * directory(current_file) != last_directory
3261 * then we need to start updating accounting in versions & offsets.
3262 * Note that last_directory is always the last path in "offsets" (or
3263 * NULL if "offsets" is empty) so this exists just for quick access.
3265 const char *last_directory;
3267 /* last_directory_len: cached computation of strlen(last_directory) */
3268 unsigned last_directory_len;
3271 static int tree_entry_order(const void *a_, const void *b_)
3273 const struct string_list_item *a = a_;
3274 const struct string_list_item *b = b_;
3276 const struct merged_info *ami = a->util;
3277 const struct merged_info *bmi = b->util;
3278 return base_name_compare(a->string, strlen(a->string), ami->result.mode,
3279 b->string, strlen(b->string), bmi->result.mode);
3282 static void write_tree(struct object_id *result_oid,
3283 struct string_list *versions,
3284 unsigned int offset,
3285 size_t hash_size)
3287 size_t maxlen = 0, extra;
3288 unsigned int nr;
3289 struct strbuf buf = STRBUF_INIT;
3290 int i;
3292 assert(offset <= versions->nr);
3293 nr = versions->nr - offset;
3294 if (versions->nr)
3295 /* No need for STABLE_QSORT -- filenames must be unique */
3296 QSORT(versions->items + offset, nr, tree_entry_order);
3298 /* Pre-allocate some space in buf */
3299 extra = hash_size + 8; /* 8: 6 for mode, 1 for space, 1 for NUL char */
3300 for (i = 0; i < nr; i++) {
3301 maxlen += strlen(versions->items[offset+i].string) + extra;
3303 strbuf_grow(&buf, maxlen);
3305 /* Write each entry out to buf */
3306 for (i = 0; i < nr; i++) {
3307 struct merged_info *mi = versions->items[offset+i].util;
3308 struct version_info *ri = &mi->result;
3309 strbuf_addf(&buf, "%o %s%c",
3310 ri->mode,
3311 versions->items[offset+i].string, '\0');
3312 strbuf_add(&buf, ri->oid.hash, hash_size);
3315 /* Write this object file out, and record in result_oid */
3316 write_object_file(buf.buf, buf.len, tree_type, result_oid);
3317 strbuf_release(&buf);
3320 static void record_entry_for_tree(struct directory_versions *dir_metadata,
3321 const char *path,
3322 struct merged_info *mi)
3324 const char *basename;
3326 if (mi->is_null)
3327 /* nothing to record */
3328 return;
3330 basename = path + mi->basename_offset;
3331 assert(strchr(basename, '/') == NULL);
3332 string_list_append(&dir_metadata->versions,
3333 basename)->util = &mi->result;
3336 static void write_completed_directory(struct merge_options *opt,
3337 const char *new_directory_name,
3338 struct directory_versions *info)
3340 const char *prev_dir;
3341 struct merged_info *dir_info = NULL;
3342 unsigned int offset;
3345 * Some explanation of info->versions and info->offsets...
3347 * process_entries() iterates over all relevant files AND
3348 * directories in reverse lexicographic order, and calls this
3349 * function. Thus, an example of the paths that process_entries()
3350 * could operate on (along with the directories for those paths
3351 * being shown) is:
3353 * xtract.c ""
3354 * tokens.txt ""
3355 * src/moduleB/umm.c src/moduleB
3356 * src/moduleB/stuff.h src/moduleB
3357 * src/moduleB/baz.c src/moduleB
3358 * src/moduleB src
3359 * src/moduleA/foo.c src/moduleA
3360 * src/moduleA/bar.c src/moduleA
3361 * src/moduleA src
3362 * src ""
3363 * Makefile ""
3365 * info->versions:
3367 * always contains the unprocessed entries and their
3368 * version_info information. For example, after the first five
3369 * entries above, info->versions would be:
3371 * xtract.c <xtract.c's version_info>
3372 * token.txt <token.txt's version_info>
3373 * umm.c <src/moduleB/umm.c's version_info>
3374 * stuff.h <src/moduleB/stuff.h's version_info>
3375 * baz.c <src/moduleB/baz.c's version_info>
3377 * Once a subdirectory is completed we remove the entries in
3378 * that subdirectory from info->versions, writing it as a tree
3379 * (write_tree()). Thus, as soon as we get to src/moduleB,
3380 * info->versions would be updated to
3382 * xtract.c <xtract.c's version_info>
3383 * token.txt <token.txt's version_info>
3384 * moduleB <src/moduleB's version_info>
3386 * info->offsets:
3388 * helps us track which entries in info->versions correspond to
3389 * which directories. When we are N directories deep (e.g. 4
3390 * for src/modA/submod/subdir/), we have up to N+1 unprocessed
3391 * directories (+1 because of toplevel dir). Corresponding to
3392 * the info->versions example above, after processing five entries
3393 * info->offsets will be:
3395 * "" 0
3396 * src/moduleB 2
3398 * which is used to know that xtract.c & token.txt are from the
3399 * toplevel dirctory, while umm.c & stuff.h & baz.c are from the
3400 * src/moduleB directory. Again, following the example above,
3401 * once we need to process src/moduleB, then info->offsets is
3402 * updated to
3404 * "" 0
3405 * src 2
3407 * which says that moduleB (and only moduleB so far) is in the
3408 * src directory.
3410 * One unique thing to note about info->offsets here is that
3411 * "src" was not added to info->offsets until there was a path
3412 * (a file OR directory) immediately below src/ that got
3413 * processed.
3415 * Since process_entry() just appends new entries to info->versions,
3416 * write_completed_directory() only needs to do work if the next path
3417 * is in a directory that is different than the last directory found
3418 * in info->offsets.
3422 * If we are working with the same directory as the last entry, there
3423 * is no work to do. (See comments above the directory_name member of
3424 * struct merged_info for why we can use pointer comparison instead of
3425 * strcmp here.)
3427 if (new_directory_name == info->last_directory)
3428 return;
3431 * If we are just starting (last_directory is NULL), or last_directory
3432 * is a prefix of the current directory, then we can just update
3433 * info->offsets to record the offset where we started this directory
3434 * and update last_directory to have quick access to it.
3436 if (info->last_directory == NULL ||
3437 !strncmp(new_directory_name, info->last_directory,
3438 info->last_directory_len)) {
3439 uintptr_t offset = info->versions.nr;
3441 info->last_directory = new_directory_name;
3442 info->last_directory_len = strlen(info->last_directory);
3444 * Record the offset into info->versions where we will
3445 * start recording basenames of paths found within
3446 * new_directory_name.
3448 string_list_append(&info->offsets,
3449 info->last_directory)->util = (void*)offset;
3450 return;
3454 * The next entry that will be processed will be within
3455 * new_directory_name. Since at this point we know that
3456 * new_directory_name is within a different directory than
3457 * info->last_directory, we have all entries for info->last_directory
3458 * in info->versions and we need to create a tree object for them.
3460 dir_info = strmap_get(&opt->priv->paths, info->last_directory);
3461 assert(dir_info);
3462 offset = (uintptr_t)info->offsets.items[info->offsets.nr-1].util;
3463 if (offset == info->versions.nr) {
3465 * Actually, we don't need to create a tree object in this
3466 * case. Whenever all files within a directory disappear
3467 * during the merge (e.g. unmodified on one side and
3468 * deleted on the other, or files were renamed elsewhere),
3469 * then we get here and the directory itself needs to be
3470 * omitted from its parent tree as well.
3472 dir_info->is_null = 1;
3473 } else {
3475 * Write out the tree to the git object directory, and also
3476 * record the mode and oid in dir_info->result.
3478 dir_info->is_null = 0;
3479 dir_info->result.mode = S_IFDIR;
3480 write_tree(&dir_info->result.oid, &info->versions, offset,
3481 opt->repo->hash_algo->rawsz);
3485 * We've now used several entries from info->versions and one entry
3486 * from info->offsets, so we get rid of those values.
3488 info->offsets.nr--;
3489 info->versions.nr = offset;
3492 * Now we've taken care of the completed directory, but we need to
3493 * prepare things since future entries will be in
3494 * new_directory_name. (In particular, process_entry() will be
3495 * appending new entries to info->versions.) So, we need to make
3496 * sure new_directory_name is the last entry in info->offsets.
3498 prev_dir = info->offsets.nr == 0 ? NULL :
3499 info->offsets.items[info->offsets.nr-1].string;
3500 if (new_directory_name != prev_dir) {
3501 uintptr_t c = info->versions.nr;
3502 string_list_append(&info->offsets,
3503 new_directory_name)->util = (void*)c;
3506 /* And, of course, we need to update last_directory to match. */
3507 info->last_directory = new_directory_name;
3508 info->last_directory_len = strlen(info->last_directory);
3511 /* Per entry merge function */
3512 static void process_entry(struct merge_options *opt,
3513 const char *path,
3514 struct conflict_info *ci,
3515 struct directory_versions *dir_metadata)
3517 int df_file_index = 0;
3519 VERIFY_CI(ci);
3520 assert(ci->filemask >= 0 && ci->filemask <= 7);
3521 /* ci->match_mask == 7 was handled in collect_merge_info_callback() */
3522 assert(ci->match_mask == 0 || ci->match_mask == 3 ||
3523 ci->match_mask == 5 || ci->match_mask == 6);
3525 if (ci->dirmask) {
3526 record_entry_for_tree(dir_metadata, path, &ci->merged);
3527 if (ci->filemask == 0)
3528 /* nothing else to handle */
3529 return;
3530 assert(ci->df_conflict);
3533 if (ci->df_conflict && ci->merged.result.mode == 0) {
3534 int i;
3537 * directory no longer in the way, but we do have a file we
3538 * need to place here so we need to clean away the "directory
3539 * merges to nothing" result.
3541 ci->df_conflict = 0;
3542 assert(ci->filemask != 0);
3543 ci->merged.clean = 0;
3544 ci->merged.is_null = 0;
3545 /* and we want to zero out any directory-related entries */
3546 ci->match_mask = (ci->match_mask & ~ci->dirmask);
3547 ci->dirmask = 0;
3548 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
3549 if (ci->filemask & (1 << i))
3550 continue;
3551 ci->stages[i].mode = 0;
3552 oidcpy(&ci->stages[i].oid, null_oid());
3554 } else if (ci->df_conflict && ci->merged.result.mode != 0) {
3556 * This started out as a D/F conflict, and the entries in
3557 * the competing directory were not removed by the merge as
3558 * evidenced by write_completed_directory() writing a value
3559 * to ci->merged.result.mode.
3561 struct conflict_info *new_ci;
3562 const char *branch;
3563 const char *old_path = path;
3564 int i;
3566 assert(ci->merged.result.mode == S_IFDIR);
3569 * If filemask is 1, we can just ignore the file as having
3570 * been deleted on both sides. We do not want to overwrite
3571 * ci->merged.result, since it stores the tree for all the
3572 * files under it.
3574 if (ci->filemask == 1) {
3575 ci->filemask = 0;
3576 return;
3580 * This file still exists on at least one side, and we want
3581 * the directory to remain here, so we need to move this
3582 * path to some new location.
3584 CALLOC_ARRAY(new_ci, 1);
3585 /* We don't really want new_ci->merged.result copied, but it'll
3586 * be overwritten below so it doesn't matter. We also don't
3587 * want any directory mode/oid values copied, but we'll zero
3588 * those out immediately. We do want the rest of ci copied.
3590 memcpy(new_ci, ci, sizeof(*ci));
3591 new_ci->match_mask = (new_ci->match_mask & ~new_ci->dirmask);
3592 new_ci->dirmask = 0;
3593 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
3594 if (new_ci->filemask & (1 << i))
3595 continue;
3596 /* zero out any entries related to directories */
3597 new_ci->stages[i].mode = 0;
3598 oidcpy(&new_ci->stages[i].oid, null_oid());
3602 * Find out which side this file came from; note that we
3603 * cannot just use ci->filemask, because renames could cause
3604 * the filemask to go back to 7. So we use dirmask, then
3605 * pick the opposite side's index.
3607 df_file_index = (ci->dirmask & (1 << 1)) ? 2 : 1;
3608 branch = (df_file_index == 1) ? opt->branch1 : opt->branch2;
3609 path = unique_path(&opt->priv->paths, path, branch);
3610 strmap_put(&opt->priv->paths, path, new_ci);
3612 path_msg(opt, path, 0,
3613 _("CONFLICT (file/directory): directory in the way "
3614 "of %s from %s; moving it to %s instead."),
3615 old_path, branch, path);
3618 * Zero out the filemask for the old ci. At this point, ci
3619 * was just an entry for a directory, so we don't need to
3620 * do anything more with it.
3622 ci->filemask = 0;
3625 * Now note that we're working on the new entry (path was
3626 * updated above.
3628 ci = new_ci;
3632 * NOTE: Below there is a long switch-like if-elseif-elseif... block
3633 * which the code goes through even for the df_conflict cases
3634 * above.
3636 if (ci->match_mask) {
3637 ci->merged.clean = !ci->df_conflict && !ci->path_conflict;
3638 if (ci->match_mask == 6) {
3639 /* stages[1] == stages[2] */
3640 ci->merged.result.mode = ci->stages[1].mode;
3641 oidcpy(&ci->merged.result.oid, &ci->stages[1].oid);
3642 } else {
3643 /* determine the mask of the side that didn't match */
3644 unsigned int othermask = 7 & ~ci->match_mask;
3645 int side = (othermask == 4) ? 2 : 1;
3647 ci->merged.result.mode = ci->stages[side].mode;
3648 ci->merged.is_null = !ci->merged.result.mode;
3649 if (ci->merged.is_null)
3650 ci->merged.clean = 1;
3651 oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
3653 assert(othermask == 2 || othermask == 4);
3654 assert(ci->merged.is_null ==
3655 (ci->filemask == ci->match_mask));
3657 } else if (ci->filemask >= 6 &&
3658 (S_IFMT & ci->stages[1].mode) !=
3659 (S_IFMT & ci->stages[2].mode)) {
3660 /* Two different items from (file/submodule/symlink) */
3661 if (opt->priv->call_depth) {
3662 /* Just use the version from the merge base */
3663 ci->merged.clean = 0;
3664 oidcpy(&ci->merged.result.oid, &ci->stages[0].oid);
3665 ci->merged.result.mode = ci->stages[0].mode;
3666 ci->merged.is_null = (ci->merged.result.mode == 0);
3667 } else {
3668 /* Handle by renaming one or both to separate paths. */
3669 unsigned o_mode = ci->stages[0].mode;
3670 unsigned a_mode = ci->stages[1].mode;
3671 unsigned b_mode = ci->stages[2].mode;
3672 struct conflict_info *new_ci;
3673 const char *a_path = NULL, *b_path = NULL;
3674 int rename_a = 0, rename_b = 0;
3676 new_ci = xmalloc(sizeof(*new_ci));
3678 if (S_ISREG(a_mode))
3679 rename_a = 1;
3680 else if (S_ISREG(b_mode))
3681 rename_b = 1;
3682 else {
3683 rename_a = 1;
3684 rename_b = 1;
3687 if (rename_a && rename_b) {
3688 path_msg(opt, path, 0,
3689 _("CONFLICT (distinct types): %s had "
3690 "different types on each side; "
3691 "renamed both of them so each can "
3692 "be recorded somewhere."),
3693 path);
3694 } else {
3695 path_msg(opt, path, 0,
3696 _("CONFLICT (distinct types): %s had "
3697 "different types on each side; "
3698 "renamed one of them so each can be "
3699 "recorded somewhere."),
3700 path);
3703 ci->merged.clean = 0;
3704 memcpy(new_ci, ci, sizeof(*new_ci));
3706 /* Put b into new_ci, removing a from stages */
3707 new_ci->merged.result.mode = ci->stages[2].mode;
3708 oidcpy(&new_ci->merged.result.oid, &ci->stages[2].oid);
3709 new_ci->stages[1].mode = 0;
3710 oidcpy(&new_ci->stages[1].oid, null_oid());
3711 new_ci->filemask = 5;
3712 if ((S_IFMT & b_mode) != (S_IFMT & o_mode)) {
3713 new_ci->stages[0].mode = 0;
3714 oidcpy(&new_ci->stages[0].oid, null_oid());
3715 new_ci->filemask = 4;
3718 /* Leave only a in ci, fixing stages. */
3719 ci->merged.result.mode = ci->stages[1].mode;
3720 oidcpy(&ci->merged.result.oid, &ci->stages[1].oid);
3721 ci->stages[2].mode = 0;
3722 oidcpy(&ci->stages[2].oid, null_oid());
3723 ci->filemask = 3;
3724 if ((S_IFMT & a_mode) != (S_IFMT & o_mode)) {
3725 ci->stages[0].mode = 0;
3726 oidcpy(&ci->stages[0].oid, null_oid());
3727 ci->filemask = 2;
3730 /* Insert entries into opt->priv_paths */
3731 assert(rename_a || rename_b);
3732 if (rename_a) {
3733 a_path = unique_path(&opt->priv->paths,
3734 path, opt->branch1);
3735 strmap_put(&opt->priv->paths, a_path, ci);
3738 if (rename_b)
3739 b_path = unique_path(&opt->priv->paths,
3740 path, opt->branch2);
3741 else
3742 b_path = path;
3743 strmap_put(&opt->priv->paths, b_path, new_ci);
3745 if (rename_a && rename_b) {
3746 strmap_remove(&opt->priv->paths, path, 0);
3748 * We removed path from opt->priv->paths. path
3749 * will also eventually need to be freed, but
3750 * it may still be used by e.g. ci->pathnames.
3751 * So, store it in another string-list for now.
3753 string_list_append(&opt->priv->paths_to_free,
3754 path);
3758 * Do special handling for b_path since process_entry()
3759 * won't be called on it specially.
3761 strmap_put(&opt->priv->conflicted, b_path, new_ci);
3762 record_entry_for_tree(dir_metadata, b_path,
3763 &new_ci->merged);
3766 * Remaining code for processing this entry should
3767 * think in terms of processing a_path.
3769 if (a_path)
3770 path = a_path;
3772 } else if (ci->filemask >= 6) {
3773 /* Need a two-way or three-way content merge */
3774 struct version_info merged_file;
3775 unsigned clean_merge;
3776 struct version_info *o = &ci->stages[0];
3777 struct version_info *a = &ci->stages[1];
3778 struct version_info *b = &ci->stages[2];
3780 clean_merge = handle_content_merge(opt, path, o, a, b,
3781 ci->pathnames,
3782 opt->priv->call_depth * 2,
3783 &merged_file);
3784 ci->merged.clean = clean_merge &&
3785 !ci->df_conflict && !ci->path_conflict;
3786 ci->merged.result.mode = merged_file.mode;
3787 ci->merged.is_null = (merged_file.mode == 0);
3788 oidcpy(&ci->merged.result.oid, &merged_file.oid);
3789 if (clean_merge && ci->df_conflict) {
3790 assert(df_file_index == 1 || df_file_index == 2);
3791 ci->filemask = 1 << df_file_index;
3792 ci->stages[df_file_index].mode = merged_file.mode;
3793 oidcpy(&ci->stages[df_file_index].oid, &merged_file.oid);
3795 if (!clean_merge) {
3796 const char *reason = _("content");
3797 if (ci->filemask == 6)
3798 reason = _("add/add");
3799 if (S_ISGITLINK(merged_file.mode))
3800 reason = _("submodule");
3801 path_msg(opt, path, 0,
3802 _("CONFLICT (%s): Merge conflict in %s"),
3803 reason, path);
3805 } else if (ci->filemask == 3 || ci->filemask == 5) {
3806 /* Modify/delete */
3807 const char *modify_branch, *delete_branch;
3808 int side = (ci->filemask == 5) ? 2 : 1;
3809 int index = opt->priv->call_depth ? 0 : side;
3811 ci->merged.result.mode = ci->stages[index].mode;
3812 oidcpy(&ci->merged.result.oid, &ci->stages[index].oid);
3813 ci->merged.clean = 0;
3815 modify_branch = (side == 1) ? opt->branch1 : opt->branch2;
3816 delete_branch = (side == 1) ? opt->branch2 : opt->branch1;
3818 if (opt->renormalize &&
3819 blob_unchanged(opt, &ci->stages[0], &ci->stages[side],
3820 path)) {
3821 ci->merged.is_null = 1;
3822 ci->merged.clean = 1;
3823 assert(!ci->df_conflict && !ci->path_conflict);
3824 } else if (ci->path_conflict &&
3825 oideq(&ci->stages[0].oid, &ci->stages[side].oid)) {
3827 * This came from a rename/delete; no action to take,
3828 * but avoid printing "modify/delete" conflict notice
3829 * since the contents were not modified.
3831 } else {
3832 path_msg(opt, path, 0,
3833 _("CONFLICT (modify/delete): %s deleted in %s "
3834 "and modified in %s. Version %s of %s left "
3835 "in tree."),
3836 path, delete_branch, modify_branch,
3837 modify_branch, path);
3839 } else if (ci->filemask == 2 || ci->filemask == 4) {
3840 /* Added on one side */
3841 int side = (ci->filemask == 4) ? 2 : 1;
3842 ci->merged.result.mode = ci->stages[side].mode;
3843 oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
3844 ci->merged.clean = !ci->df_conflict && !ci->path_conflict;
3845 } else if (ci->filemask == 1) {
3846 /* Deleted on both sides */
3847 ci->merged.is_null = 1;
3848 ci->merged.result.mode = 0;
3849 oidcpy(&ci->merged.result.oid, null_oid());
3850 assert(!ci->df_conflict);
3851 ci->merged.clean = !ci->path_conflict;
3855 * If still conflicted, record it separately. This allows us to later
3856 * iterate over just conflicted entries when updating the index instead
3857 * of iterating over all entries.
3859 if (!ci->merged.clean)
3860 strmap_put(&opt->priv->conflicted, path, ci);
3862 /* Record metadata for ci->merged in dir_metadata */
3863 record_entry_for_tree(dir_metadata, path, &ci->merged);
3866 static void prefetch_for_content_merges(struct merge_options *opt,
3867 struct string_list *plist)
3869 struct string_list_item *e;
3870 struct oid_array to_fetch = OID_ARRAY_INIT;
3872 if (opt->repo != the_repository || !has_promisor_remote())
3873 return;
3875 for (e = &plist->items[plist->nr-1]; e >= plist->items; --e) {
3876 /* char *path = e->string; */
3877 struct conflict_info *ci = e->util;
3878 int i;
3880 /* Ignore clean entries */
3881 if (ci->merged.clean)
3882 continue;
3884 /* Ignore entries that don't need a content merge */
3885 if (ci->match_mask || ci->filemask < 6 ||
3886 !S_ISREG(ci->stages[1].mode) ||
3887 !S_ISREG(ci->stages[2].mode) ||
3888 oideq(&ci->stages[1].oid, &ci->stages[2].oid))
3889 continue;
3891 /* Also don't need content merge if base matches either side */
3892 if (ci->filemask == 7 &&
3893 S_ISREG(ci->stages[0].mode) &&
3894 (oideq(&ci->stages[0].oid, &ci->stages[1].oid) ||
3895 oideq(&ci->stages[0].oid, &ci->stages[2].oid)))
3896 continue;
3898 for (i = 0; i < 3; i++) {
3899 unsigned side_mask = (1 << i);
3900 struct version_info *vi = &ci->stages[i];
3902 if ((ci->filemask & side_mask) &&
3903 S_ISREG(vi->mode) &&
3904 oid_object_info_extended(opt->repo, &vi->oid, NULL,
3905 OBJECT_INFO_FOR_PREFETCH))
3906 oid_array_append(&to_fetch, &vi->oid);
3910 promisor_remote_get_direct(opt->repo, to_fetch.oid, to_fetch.nr);
3911 oid_array_clear(&to_fetch);
3914 static void process_entries(struct merge_options *opt,
3915 struct object_id *result_oid)
3917 struct hashmap_iter iter;
3918 struct strmap_entry *e;
3919 struct string_list plist = STRING_LIST_INIT_NODUP;
3920 struct string_list_item *entry;
3921 struct directory_versions dir_metadata = { STRING_LIST_INIT_NODUP,
3922 STRING_LIST_INIT_NODUP,
3923 NULL, 0 };
3925 trace2_region_enter("merge", "process_entries setup", opt->repo);
3926 if (strmap_empty(&opt->priv->paths)) {
3927 oidcpy(result_oid, opt->repo->hash_algo->empty_tree);
3928 return;
3931 /* Hack to pre-allocate plist to the desired size */
3932 trace2_region_enter("merge", "plist grow", opt->repo);
3933 ALLOC_GROW(plist.items, strmap_get_size(&opt->priv->paths), plist.alloc);
3934 trace2_region_leave("merge", "plist grow", opt->repo);
3936 /* Put every entry from paths into plist, then sort */
3937 trace2_region_enter("merge", "plist copy", opt->repo);
3938 strmap_for_each_entry(&opt->priv->paths, &iter, e) {
3939 string_list_append(&plist, e->key)->util = e->value;
3941 trace2_region_leave("merge", "plist copy", opt->repo);
3943 trace2_region_enter("merge", "plist special sort", opt->repo);
3944 plist.cmp = sort_dirs_next_to_their_children;
3945 string_list_sort(&plist);
3946 trace2_region_leave("merge", "plist special sort", opt->repo);
3948 trace2_region_leave("merge", "process_entries setup", opt->repo);
3951 * Iterate over the items in reverse order, so we can handle paths
3952 * below a directory before needing to handle the directory itself.
3954 * This allows us to write subtrees before we need to write trees,
3955 * and it also enables sane handling of directory/file conflicts
3956 * (because it allows us to know whether the directory is still in
3957 * the way when it is time to process the file at the same path).
3959 trace2_region_enter("merge", "processing", opt->repo);
3960 prefetch_for_content_merges(opt, &plist);
3961 for (entry = &plist.items[plist.nr-1]; entry >= plist.items; --entry) {
3962 char *path = entry->string;
3964 * NOTE: mi may actually be a pointer to a conflict_info, but
3965 * we have to check mi->clean first to see if it's safe to
3966 * reassign to such a pointer type.
3968 struct merged_info *mi = entry->util;
3970 write_completed_directory(opt, mi->directory_name,
3971 &dir_metadata);
3972 if (mi->clean)
3973 record_entry_for_tree(&dir_metadata, path, mi);
3974 else {
3975 struct conflict_info *ci = (struct conflict_info *)mi;
3976 process_entry(opt, path, ci, &dir_metadata);
3979 trace2_region_leave("merge", "processing", opt->repo);
3981 trace2_region_enter("merge", "process_entries cleanup", opt->repo);
3982 if (dir_metadata.offsets.nr != 1 ||
3983 (uintptr_t)dir_metadata.offsets.items[0].util != 0) {
3984 printf("dir_metadata.offsets.nr = %d (should be 1)\n",
3985 dir_metadata.offsets.nr);
3986 printf("dir_metadata.offsets.items[0].util = %u (should be 0)\n",
3987 (unsigned)(uintptr_t)dir_metadata.offsets.items[0].util);
3988 fflush(stdout);
3989 BUG("dir_metadata accounting completely off; shouldn't happen");
3991 write_tree(result_oid, &dir_metadata.versions, 0,
3992 opt->repo->hash_algo->rawsz);
3993 string_list_clear(&plist, 0);
3994 string_list_clear(&dir_metadata.versions, 0);
3995 string_list_clear(&dir_metadata.offsets, 0);
3996 trace2_region_leave("merge", "process_entries cleanup", opt->repo);
3999 /*** Function Grouping: functions related to merge_switch_to_result() ***/
4001 static int checkout(struct merge_options *opt,
4002 struct tree *prev,
4003 struct tree *next)
4005 /* Switch the index/working copy from old to new */
4006 int ret;
4007 struct tree_desc trees[2];
4008 struct unpack_trees_options unpack_opts;
4010 memset(&unpack_opts, 0, sizeof(unpack_opts));
4011 unpack_opts.head_idx = -1;
4012 unpack_opts.src_index = opt->repo->index;
4013 unpack_opts.dst_index = opt->repo->index;
4015 setup_unpack_trees_porcelain(&unpack_opts, "merge");
4018 * NOTE: if this were just "git checkout" code, we would probably
4019 * read or refresh the cache and check for a conflicted index, but
4020 * builtin/merge.c or sequencer.c really needs to read the index
4021 * and check for conflicted entries before starting merging for a
4022 * good user experience (no sense waiting for merges/rebases before
4023 * erroring out), so there's no reason to duplicate that work here.
4026 /* 2-way merge to the new branch */
4027 unpack_opts.update = 1;
4028 unpack_opts.merge = 1;
4029 unpack_opts.quiet = 0; /* FIXME: sequencer might want quiet? */
4030 unpack_opts.verbose_update = (opt->verbosity > 2);
4031 unpack_opts.fn = twoway_merge;
4032 if (1/* FIXME: opts->overwrite_ignore*/) {
4033 CALLOC_ARRAY(unpack_opts.dir, 1);
4034 unpack_opts.dir->flags |= DIR_SHOW_IGNORED;
4035 setup_standard_excludes(unpack_opts.dir);
4037 parse_tree(prev);
4038 init_tree_desc(&trees[0], prev->buffer, prev->size);
4039 parse_tree(next);
4040 init_tree_desc(&trees[1], next->buffer, next->size);
4042 ret = unpack_trees(2, trees, &unpack_opts);
4043 clear_unpack_trees_porcelain(&unpack_opts);
4044 dir_clear(unpack_opts.dir);
4045 FREE_AND_NULL(unpack_opts.dir);
4046 return ret;
4049 static int record_conflicted_index_entries(struct merge_options *opt)
4051 struct hashmap_iter iter;
4052 struct strmap_entry *e;
4053 struct index_state *index = opt->repo->index;
4054 struct checkout state = CHECKOUT_INIT;
4055 int errs = 0;
4056 int original_cache_nr;
4058 if (strmap_empty(&opt->priv->conflicted))
4059 return 0;
4061 /* If any entries have skip_worktree set, we'll have to check 'em out */
4062 state.force = 1;
4063 state.quiet = 1;
4064 state.refresh_cache = 1;
4065 state.istate = index;
4066 original_cache_nr = index->cache_nr;
4068 /* Put every entry from paths into plist, then sort */
4069 strmap_for_each_entry(&opt->priv->conflicted, &iter, e) {
4070 const char *path = e->key;
4071 struct conflict_info *ci = e->value;
4072 int pos;
4073 struct cache_entry *ce;
4074 int i;
4076 VERIFY_CI(ci);
4079 * The index will already have a stage=0 entry for this path,
4080 * because we created an as-merged-as-possible version of the
4081 * file and checkout() moved the working copy and index over
4082 * to that version.
4084 * However, previous iterations through this loop will have
4085 * added unstaged entries to the end of the cache which
4086 * ignore the standard alphabetical ordering of cache
4087 * entries and break invariants needed for index_name_pos()
4088 * to work. However, we know the entry we want is before
4089 * those appended cache entries, so do a temporary swap on
4090 * cache_nr to only look through entries of interest.
4092 SWAP(index->cache_nr, original_cache_nr);
4093 pos = index_name_pos(index, path, strlen(path));
4094 SWAP(index->cache_nr, original_cache_nr);
4095 if (pos < 0) {
4096 if (ci->filemask != 1)
4097 BUG("Conflicted %s but nothing in basic working tree or index; this shouldn't happen", path);
4098 cache_tree_invalidate_path(index, path);
4099 } else {
4100 ce = index->cache[pos];
4103 * Clean paths with CE_SKIP_WORKTREE set will not be
4104 * written to the working tree by the unpack_trees()
4105 * call in checkout(). Our conflicted entries would
4106 * have appeared clean to that code since we ignored
4107 * the higher order stages. Thus, we need override
4108 * the CE_SKIP_WORKTREE bit and manually write those
4109 * files to the working disk here.
4111 if (ce_skip_worktree(ce)) {
4112 struct stat st;
4114 if (!lstat(path, &st)) {
4115 char *new_name = unique_path(&opt->priv->paths,
4116 path,
4117 "cruft");
4119 path_msg(opt, path, 1,
4120 _("Note: %s not up to date and in way of checking out conflicted version; old copy renamed to %s"),
4121 path, new_name);
4122 errs |= rename(path, new_name);
4123 free(new_name);
4125 errs |= checkout_entry(ce, &state, NULL, NULL);
4129 * Mark this cache entry for removal and instead add
4130 * new stage>0 entries corresponding to the
4131 * conflicts. If there are many conflicted entries, we
4132 * want to avoid memmove'ing O(NM) entries by
4133 * inserting the new entries one at a time. So,
4134 * instead, we just add the new cache entries to the
4135 * end (ignoring normal index requirements on sort
4136 * order) and sort the index once we're all done.
4138 ce->ce_flags |= CE_REMOVE;
4141 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
4142 struct version_info *vi;
4143 if (!(ci->filemask & (1ul << i)))
4144 continue;
4145 vi = &ci->stages[i];
4146 ce = make_cache_entry(index, vi->mode, &vi->oid,
4147 path, i+1, 0);
4148 add_index_entry(index, ce, ADD_CACHE_JUST_APPEND);
4153 * Remove the unused cache entries (and invalidate the relevant
4154 * cache-trees), then sort the index entries to get the conflicted
4155 * entries we added to the end into their right locations.
4157 remove_marked_cache_entries(index, 1);
4159 * No need for STABLE_QSORT -- cmp_cache_name_compare sorts primarily
4160 * on filename and secondarily on stage, and (name, stage #) are a
4161 * unique tuple.
4163 QSORT(index->cache, index->cache_nr, cmp_cache_name_compare);
4165 return errs;
4168 void merge_switch_to_result(struct merge_options *opt,
4169 struct tree *head,
4170 struct merge_result *result,
4171 int update_worktree_and_index,
4172 int display_update_msgs)
4174 assert(opt->priv == NULL);
4175 if (result->clean >= 0 && update_worktree_and_index) {
4176 const char *filename;
4177 FILE *fp;
4179 trace2_region_enter("merge", "checkout", opt->repo);
4180 if (checkout(opt, head, result->tree)) {
4181 /* failure to function */
4182 result->clean = -1;
4183 return;
4185 trace2_region_leave("merge", "checkout", opt->repo);
4187 trace2_region_enter("merge", "record_conflicted", opt->repo);
4188 opt->priv = result->priv;
4189 if (record_conflicted_index_entries(opt)) {
4190 /* failure to function */
4191 opt->priv = NULL;
4192 result->clean = -1;
4193 return;
4195 opt->priv = NULL;
4196 trace2_region_leave("merge", "record_conflicted", opt->repo);
4198 trace2_region_enter("merge", "write_auto_merge", opt->repo);
4199 filename = git_path_auto_merge(opt->repo);
4200 fp = xfopen(filename, "w");
4201 fprintf(fp, "%s\n", oid_to_hex(&result->tree->object.oid));
4202 fclose(fp);
4203 trace2_region_leave("merge", "write_auto_merge", opt->repo);
4206 if (display_update_msgs) {
4207 struct merge_options_internal *opti = result->priv;
4208 struct hashmap_iter iter;
4209 struct strmap_entry *e;
4210 struct string_list olist = STRING_LIST_INIT_NODUP;
4211 int i;
4213 trace2_region_enter("merge", "display messages", opt->repo);
4215 /* Hack to pre-allocate olist to the desired size */
4216 ALLOC_GROW(olist.items, strmap_get_size(&opti->output),
4217 olist.alloc);
4219 /* Put every entry from output into olist, then sort */
4220 strmap_for_each_entry(&opti->output, &iter, e) {
4221 string_list_append(&olist, e->key)->util = e->value;
4223 string_list_sort(&olist);
4225 /* Iterate over the items, printing them */
4226 for (i = 0; i < olist.nr; ++i) {
4227 struct strbuf *sb = olist.items[i].util;
4229 printf("%s", sb->buf);
4231 string_list_clear(&olist, 0);
4233 /* Also include needed rename limit adjustment now */
4234 diff_warn_rename_limit("merge.renamelimit",
4235 opti->renames.needed_limit, 0);
4237 trace2_region_leave("merge", "display messages", opt->repo);
4240 merge_finalize(opt, result);
4243 void merge_finalize(struct merge_options *opt,
4244 struct merge_result *result)
4246 struct merge_options_internal *opti = result->priv;
4248 if (opt->renormalize)
4249 git_attr_set_direction(GIT_ATTR_CHECKIN);
4250 assert(opt->priv == NULL);
4252 clear_or_reinit_internal_opts(opti, 0);
4253 FREE_AND_NULL(opti);
4256 /*** Function Grouping: helper functions for merge_incore_*() ***/
4258 static struct tree *shift_tree_object(struct repository *repo,
4259 struct tree *one, struct tree *two,
4260 const char *subtree_shift)
4262 struct object_id shifted;
4264 if (!*subtree_shift) {
4265 shift_tree(repo, &one->object.oid, &two->object.oid, &shifted, 0);
4266 } else {
4267 shift_tree_by(repo, &one->object.oid, &two->object.oid, &shifted,
4268 subtree_shift);
4270 if (oideq(&two->object.oid, &shifted))
4271 return two;
4272 return lookup_tree(repo, &shifted);
4275 static inline void set_commit_tree(struct commit *c, struct tree *t)
4277 c->maybe_tree = t;
4280 static struct commit *make_virtual_commit(struct repository *repo,
4281 struct tree *tree,
4282 const char *comment)
4284 struct commit *commit = alloc_commit_node(repo);
4286 set_merge_remote_desc(commit, comment, (struct object *)commit);
4287 set_commit_tree(commit, tree);
4288 commit->object.parsed = 1;
4289 return commit;
4292 static void merge_start(struct merge_options *opt, struct merge_result *result)
4294 struct rename_info *renames;
4295 int i;
4297 /* Sanity checks on opt */
4298 trace2_region_enter("merge", "sanity checks", opt->repo);
4299 assert(opt->repo);
4301 assert(opt->branch1 && opt->branch2);
4303 assert(opt->detect_directory_renames >= MERGE_DIRECTORY_RENAMES_NONE &&
4304 opt->detect_directory_renames <= MERGE_DIRECTORY_RENAMES_TRUE);
4305 assert(opt->rename_limit >= -1);
4306 assert(opt->rename_score >= 0 && opt->rename_score <= MAX_SCORE);
4307 assert(opt->show_rename_progress >= 0 && opt->show_rename_progress <= 1);
4309 assert(opt->xdl_opts >= 0);
4310 assert(opt->recursive_variant >= MERGE_VARIANT_NORMAL &&
4311 opt->recursive_variant <= MERGE_VARIANT_THEIRS);
4314 * detect_renames, verbosity, buffer_output, and obuf are ignored
4315 * fields that were used by "recursive" rather than "ort" -- but
4316 * sanity check them anyway.
4318 assert(opt->detect_renames >= -1 &&
4319 opt->detect_renames <= DIFF_DETECT_COPY);
4320 assert(opt->verbosity >= 0 && opt->verbosity <= 5);
4321 assert(opt->buffer_output <= 2);
4322 assert(opt->obuf.len == 0);
4324 assert(opt->priv == NULL);
4325 if (result->_properly_initialized != 0 &&
4326 result->_properly_initialized != RESULT_INITIALIZED)
4327 BUG("struct merge_result passed to merge_incore_*recursive() must be zeroed or filled with values from a previous run");
4328 assert(!!result->priv == !!result->_properly_initialized);
4329 if (result->priv) {
4330 opt->priv = result->priv;
4331 result->priv = NULL;
4333 * opt->priv non-NULL means we had results from a previous
4334 * run; do a few sanity checks that user didn't mess with
4335 * it in an obvious fashion.
4337 assert(opt->priv->call_depth == 0);
4338 assert(!opt->priv->toplevel_dir ||
4339 0 == strlen(opt->priv->toplevel_dir));
4341 trace2_region_leave("merge", "sanity checks", opt->repo);
4343 /* Default to histogram diff. Actually, just hardcode it...for now. */
4344 opt->xdl_opts = DIFF_WITH_ALG(opt, HISTOGRAM_DIFF);
4346 /* Handle attr direction stuff for renormalization */
4347 if (opt->renormalize)
4348 git_attr_set_direction(GIT_ATTR_CHECKOUT);
4350 /* Initialization of opt->priv, our internal merge data */
4351 trace2_region_enter("merge", "allocate/init", opt->repo);
4352 if (opt->priv) {
4353 clear_or_reinit_internal_opts(opt->priv, 1);
4354 trace2_region_leave("merge", "allocate/init", opt->repo);
4355 return;
4357 opt->priv = xcalloc(1, sizeof(*opt->priv));
4359 /* Initialization of various renames fields */
4360 renames = &opt->priv->renames;
4361 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {
4362 strintmap_init_with_options(&renames->dirs_removed[i],
4363 NOT_RELEVANT, NULL, 0);
4364 strmap_init_with_options(&renames->dir_rename_count[i],
4365 NULL, 1);
4366 strmap_init_with_options(&renames->dir_renames[i],
4367 NULL, 0);
4369 * relevant_sources uses -1 for the default, because we need
4370 * to be able to distinguish not-in-strintmap from valid
4371 * relevant_source values from enum file_rename_relevance.
4372 * In particular, possibly_cache_new_pair() expects a negative
4373 * value for not-found entries.
4375 strintmap_init_with_options(&renames->relevant_sources[i],
4376 -1 /* explicitly invalid */,
4377 NULL, 0);
4378 strmap_init_with_options(&renames->cached_pairs[i],
4379 NULL, 1);
4380 strset_init_with_options(&renames->cached_irrelevant[i],
4381 NULL, 1);
4382 strset_init_with_options(&renames->cached_target_names[i],
4383 NULL, 0);
4385 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {
4386 strintmap_init_with_options(&renames->deferred[i].possible_trivial_merges,
4387 0, NULL, 0);
4388 strset_init_with_options(&renames->deferred[i].target_dirs,
4389 NULL, 1);
4390 renames->deferred[i].trivial_merges_okay = 1; /* 1 == maybe */
4394 * Although we initialize opt->priv->paths with strdup_strings=0,
4395 * that's just to avoid making yet another copy of an allocated
4396 * string. Putting the entry into paths means we are taking
4397 * ownership, so we will later free it. paths_to_free is similar.
4399 * In contrast, conflicted just has a subset of keys from paths, so
4400 * we don't want to free those (it'd be a duplicate free).
4402 strmap_init_with_options(&opt->priv->paths, NULL, 0);
4403 strmap_init_with_options(&opt->priv->conflicted, NULL, 0);
4404 string_list_init_nodup(&opt->priv->paths_to_free);
4407 * keys & strbufs in output will sometimes need to outlive "paths",
4408 * so it will have a copy of relevant keys. It's probably a small
4409 * subset of the overall paths that have special output.
4411 strmap_init(&opt->priv->output);
4413 trace2_region_leave("merge", "allocate/init", opt->repo);
4416 static void merge_check_renames_reusable(struct merge_options *opt,
4417 struct merge_result *result,
4418 struct tree *merge_base,
4419 struct tree *side1,
4420 struct tree *side2)
4422 struct rename_info *renames;
4423 struct tree **merge_trees;
4424 struct merge_options_internal *opti = result->priv;
4426 if (!opti)
4427 return;
4429 renames = &opti->renames;
4430 merge_trees = renames->merge_trees;
4433 * Handle case where previous merge operation did not want cache to
4434 * take effect, e.g. because rename/rename(1to1) makes it invalid.
4436 if (!merge_trees[0]) {
4437 assert(!merge_trees[0] && !merge_trees[1] && !merge_trees[2]);
4438 renames->cached_pairs_valid_side = 0; /* neither side valid */
4439 return;
4443 * Handle other cases; note that merge_trees[0..2] will only
4444 * be NULL if opti is, or if all three were manually set to
4445 * NULL by e.g. rename/rename(1to1) handling.
4447 assert(merge_trees[0] && merge_trees[1] && merge_trees[2]);
4449 /* Check if we meet a condition for re-using cached_pairs */
4450 if (oideq(&merge_base->object.oid, &merge_trees[2]->object.oid) &&
4451 oideq(&side1->object.oid, &result->tree->object.oid))
4452 renames->cached_pairs_valid_side = MERGE_SIDE1;
4453 else if (oideq(&merge_base->object.oid, &merge_trees[1]->object.oid) &&
4454 oideq(&side2->object.oid, &result->tree->object.oid))
4455 renames->cached_pairs_valid_side = MERGE_SIDE2;
4456 else
4457 renames->cached_pairs_valid_side = 0; /* neither side valid */
4460 /*** Function Grouping: merge_incore_*() and their internal variants ***/
4463 * Originally from merge_trees_internal(); heavily adapted, though.
4465 static void merge_ort_nonrecursive_internal(struct merge_options *opt,
4466 struct tree *merge_base,
4467 struct tree *side1,
4468 struct tree *side2,
4469 struct merge_result *result)
4471 struct object_id working_tree_oid;
4473 if (opt->subtree_shift) {
4474 side2 = shift_tree_object(opt->repo, side1, side2,
4475 opt->subtree_shift);
4476 merge_base = shift_tree_object(opt->repo, side1, merge_base,
4477 opt->subtree_shift);
4480 redo:
4481 trace2_region_enter("merge", "collect_merge_info", opt->repo);
4482 if (collect_merge_info(opt, merge_base, side1, side2) != 0) {
4484 * TRANSLATORS: The %s arguments are: 1) tree hash of a merge
4485 * base, and 2-3) the trees for the two trees we're merging.
4487 err(opt, _("collecting merge info failed for trees %s, %s, %s"),
4488 oid_to_hex(&merge_base->object.oid),
4489 oid_to_hex(&side1->object.oid),
4490 oid_to_hex(&side2->object.oid));
4491 result->clean = -1;
4492 return;
4494 trace2_region_leave("merge", "collect_merge_info", opt->repo);
4496 trace2_region_enter("merge", "renames", opt->repo);
4497 result->clean = detect_and_process_renames(opt, merge_base,
4498 side1, side2);
4499 trace2_region_leave("merge", "renames", opt->repo);
4500 if (opt->priv->renames.redo_after_renames == 2) {
4501 trace2_region_enter("merge", "reset_maps", opt->repo);
4502 clear_or_reinit_internal_opts(opt->priv, 1);
4503 trace2_region_leave("merge", "reset_maps", opt->repo);
4504 goto redo;
4507 trace2_region_enter("merge", "process_entries", opt->repo);
4508 process_entries(opt, &working_tree_oid);
4509 trace2_region_leave("merge", "process_entries", opt->repo);
4511 /* Set return values */
4512 result->tree = parse_tree_indirect(&working_tree_oid);
4513 /* existence of conflicted entries implies unclean */
4514 result->clean &= strmap_empty(&opt->priv->conflicted);
4515 if (!opt->priv->call_depth) {
4516 result->priv = opt->priv;
4517 result->_properly_initialized = RESULT_INITIALIZED;
4518 opt->priv = NULL;
4523 * Originally from merge_recursive_internal(); somewhat adapted, though.
4525 static void merge_ort_internal(struct merge_options *opt,
4526 struct commit_list *merge_bases,
4527 struct commit *h1,
4528 struct commit *h2,
4529 struct merge_result *result)
4531 struct commit_list *iter;
4532 struct commit *merged_merge_bases;
4533 const char *ancestor_name;
4534 struct strbuf merge_base_abbrev = STRBUF_INIT;
4536 if (!merge_bases) {
4537 merge_bases = get_merge_bases(h1, h2);
4538 /* See merge-ort.h:merge_incore_recursive() declaration NOTE */
4539 merge_bases = reverse_commit_list(merge_bases);
4542 merged_merge_bases = pop_commit(&merge_bases);
4543 if (merged_merge_bases == NULL) {
4544 /* if there is no common ancestor, use an empty tree */
4545 struct tree *tree;
4547 tree = lookup_tree(opt->repo, opt->repo->hash_algo->empty_tree);
4548 merged_merge_bases = make_virtual_commit(opt->repo, tree,
4549 "ancestor");
4550 ancestor_name = "empty tree";
4551 } else if (merge_bases) {
4552 ancestor_name = "merged common ancestors";
4553 } else {
4554 strbuf_add_unique_abbrev(&merge_base_abbrev,
4555 &merged_merge_bases->object.oid,
4556 DEFAULT_ABBREV);
4557 ancestor_name = merge_base_abbrev.buf;
4560 for (iter = merge_bases; iter; iter = iter->next) {
4561 const char *saved_b1, *saved_b2;
4562 struct commit *prev = merged_merge_bases;
4564 opt->priv->call_depth++;
4566 * When the merge fails, the result contains files
4567 * with conflict markers. The cleanness flag is
4568 * ignored (unless indicating an error), it was never
4569 * actually used, as result of merge_trees has always
4570 * overwritten it: the committed "conflicts" were
4571 * already resolved.
4573 saved_b1 = opt->branch1;
4574 saved_b2 = opt->branch2;
4575 opt->branch1 = "Temporary merge branch 1";
4576 opt->branch2 = "Temporary merge branch 2";
4577 merge_ort_internal(opt, NULL, prev, iter->item, result);
4578 if (result->clean < 0)
4579 return;
4580 opt->branch1 = saved_b1;
4581 opt->branch2 = saved_b2;
4582 opt->priv->call_depth--;
4584 merged_merge_bases = make_virtual_commit(opt->repo,
4585 result->tree,
4586 "merged tree");
4587 commit_list_insert(prev, &merged_merge_bases->parents);
4588 commit_list_insert(iter->item,
4589 &merged_merge_bases->parents->next);
4591 clear_or_reinit_internal_opts(opt->priv, 1);
4594 opt->ancestor = ancestor_name;
4595 merge_ort_nonrecursive_internal(opt,
4596 repo_get_commit_tree(opt->repo,
4597 merged_merge_bases),
4598 repo_get_commit_tree(opt->repo, h1),
4599 repo_get_commit_tree(opt->repo, h2),
4600 result);
4601 strbuf_release(&merge_base_abbrev);
4602 opt->ancestor = NULL; /* avoid accidental re-use of opt->ancestor */
4605 void merge_incore_nonrecursive(struct merge_options *opt,
4606 struct tree *merge_base,
4607 struct tree *side1,
4608 struct tree *side2,
4609 struct merge_result *result)
4611 trace2_region_enter("merge", "incore_nonrecursive", opt->repo);
4613 trace2_region_enter("merge", "merge_start", opt->repo);
4614 assert(opt->ancestor != NULL);
4615 merge_check_renames_reusable(opt, result, merge_base, side1, side2);
4616 merge_start(opt, result);
4618 * Record the trees used in this merge, so if there's a next merge in
4619 * a cherry-pick or rebase sequence it might be able to take advantage
4620 * of the cached_pairs in that next merge.
4622 opt->priv->renames.merge_trees[0] = merge_base;
4623 opt->priv->renames.merge_trees[1] = side1;
4624 opt->priv->renames.merge_trees[2] = side2;
4625 trace2_region_leave("merge", "merge_start", opt->repo);
4627 merge_ort_nonrecursive_internal(opt, merge_base, side1, side2, result);
4628 trace2_region_leave("merge", "incore_nonrecursive", opt->repo);
4631 void merge_incore_recursive(struct merge_options *opt,
4632 struct commit_list *merge_bases,
4633 struct commit *side1,
4634 struct commit *side2,
4635 struct merge_result *result)
4637 trace2_region_enter("merge", "incore_recursive", opt->repo);
4639 /* We set the ancestor label based on the merge_bases */
4640 assert(opt->ancestor == NULL);
4642 trace2_region_enter("merge", "merge_start", opt->repo);
4643 merge_start(opt, result);
4644 trace2_region_leave("merge", "merge_start", opt->repo);
4646 merge_ort_internal(opt, merge_bases, side1, side2, result);
4647 trace2_region_leave("merge", "incore_recursive", opt->repo);