]> git.ipfire.org Git - thirdparty/git.git/blob - merge-ort.c
reftable: read reftable files
[thirdparty/git.git] / merge-ort.c
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
5 *
6 * git merge [-s recursive]
7 *
8 * with
9 *
10 * git merge -s ort
11 *
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"?)
15 */
16
17 #include "cache.h"
18 #include "merge-ort.h"
19
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"
39
40 /*
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.
47 *
48 * See also 'filemask' and 'dirmask' in struct conflict_info; the "ith side"
49 * referred to there is one of these three sides.
50 */
51 enum merge_side {
52 MERGE_BASE = 0,
53 MERGE_SIDE1 = 1,
54 MERGE_SIDE2 = 2
55 };
56
57 static unsigned RESULT_INITIALIZED = 0x1abe11ed; /* unlikely accidental value */
58
59 struct traversal_callback_data {
60 unsigned long mask;
61 unsigned long dirmask;
62 struct name_entry names[3];
63 };
64
65 struct deferred_traversal_data {
66 /*
67 * possible_trivial_merges: directories to be explored only when needed
68 *
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().
84 *
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.
88 */
89 struct strintmap possible_trivial_merges;
90
91 /*
92 * trivial_merges_okay: if trivial directory merges are okay
93 *
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.
100 */
101 unsigned trivial_merges_okay;
102
103 /*
104 * target_dirs: ancestor directories of rename targets
105 *
106 * target_dirs contains all directory names that are an ancestor of
107 * any rename destination.
108 */
109 struct strset target_dirs;
110 };
111
112 struct rename_info {
113 /*
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).
119 */
120
121 /*
122 * pairs: pairing of filenames from diffcore_rename()
123 */
124 struct diff_queue_struct pairs[3];
125
126 /*
127 * dirs_removed: directories removed on a given side of history.
128 *
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.
132 */
133 struct strintmap dirs_removed[3];
134
135 /*
136 * dir_rename_count: tracking where parts of a directory were renamed to
137 *
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.
142 */
143 struct strmap dir_rename_count[3];
144
145 /*
146 * dir_renames: computed directory renames
147 *
148 * This is a map of old_dir => new_dir and is derived in part from
149 * dir_rename_count.
150 */
151 struct strmap dir_renames[3];
152
153 /*
154 * relevant_sources: deleted paths wanted in rename detection, and why
155 *
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().
166 */
167 struct strintmap relevant_sources[3];
168
169 struct deferred_traversal_data deferred[3];
170
171 /*
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
176 */
177 unsigned dir_rename_mask:3;
178
179 /*
180 * callback_data_*: supporting data structures for alternate traversal
181 *
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.
190 */
191 struct traversal_callback_data *callback_data;
192 int callback_data_nr, callback_data_alloc;
193 char *callback_data_traverse_path;
194
195 /*
196 * merge_trees: trees passed to the merge algorithm for the merge
197 *
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.
203 *
204 * See also all the cached_* variables.
205 */
206 struct tree *merge_trees[3];
207
208 /*
209 * cached_pairs_valid_side: which side's cached info can be reused
210 *
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.
217 */
218 int cached_pairs_valid_side;
219
220 /*
221 * cached_pairs: Caching of renames and deletions.
222 *
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).
227 */
228 struct strmap cached_pairs[3];
229
230 /*
231 * cached_target_names: just the destinations from cached_pairs
232 *
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.
236 */
237 struct strset cached_target_names[3];
238
239 /*
240 * cached_irrelevant: Caching of rename_sources that aren't relevant.
241 *
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.
259 */
260 struct strset cached_irrelevant[3];
261
262 /*
263 * redo_after_renames: optimization flag for "restarting" the merge
264 *
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.
276 *
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)
281 */
282 unsigned redo_after_renames;
283
284 /*
285 * needed_limit: value needed for inexact rename detection to run
286 *
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.
290 */
291 int needed_limit;
292 };
293
294 struct merge_options_internal {
295 /*
296 * paths: primary data structure in all of merge ort.
297 *
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 *
307 * The values of paths:
308 * * either a pointer to a merged_info, or a conflict_info struct
309 * * merged_info contains all relevant information for a
310 * non-conflicted entry.
311 * * conflict_info contains a merged_info, plus any additional
312 * information about a conflict such as the higher orders stages
313 * involved and the names of the paths those came from (handy
314 * once renames get involved).
315 * * a path may start "conflicted" (i.e. point to a conflict_info)
316 * and then a later step (e.g. three-way content merge) determines
317 * it can be cleanly merged, at which point it'll be marked clean
318 * and the algorithm will ignore any data outside the contained
319 * merged_info for that entry
320 * * If an entry remains conflicted, the merged_info portion of a
321 * conflict_info will later be filled with whatever version of
322 * the file should be placed in the working directory (e.g. an
323 * as-merged-as-possible variation that contains conflict markers).
324 */
325 struct strmap paths;
326
327 /*
328 * conflicted: a subset of keys->values from "paths"
329 *
330 * conflicted is basically an optimization between process_entries()
331 * and record_conflicted_index_entries(); the latter could loop over
332 * ALL the entries in paths AGAIN and look for the ones that are
333 * still conflicted, but since process_entries() has to loop over
334 * all of them, it saves the ones it couldn't resolve in this strmap
335 * so that record_conflicted_index_entries() can iterate just the
336 * relevant entries.
337 */
338 struct strmap conflicted;
339
340 /*
341 * pool: memory pool for fast allocation/deallocation
342 *
343 * We allocate room for lots of filenames and auxiliary data
344 * structures in merge_options_internal, and it tends to all be
345 * freed together too. Using a memory pool for these provides a
346 * nice speedup.
347 */
348 struct mem_pool pool;
349
350 /*
351 * output: special messages and conflict notices for various paths
352 *
353 * This is a map of pathnames (a subset of the keys in "paths" above)
354 * to strbufs. It gathers various warning/conflict/notice messages
355 * for later processing.
356 */
357 struct strmap output;
358
359 /*
360 * renames: various data relating to rename detection
361 */
362 struct rename_info renames;
363
364 /*
365 * attr_index: hacky minimal index used for renormalization
366 *
367 * renormalization code _requires_ an index, though it only needs to
368 * find a .gitattributes file within the index. So, when
369 * renormalization is important, we create a special index with just
370 * that one file.
371 */
372 struct index_state attr_index;
373
374 /*
375 * current_dir_name, toplevel_dir: temporary vars
376 *
377 * These are used in collect_merge_info_callback(), and will set the
378 * various merged_info.directory_name for the various paths we get;
379 * see documentation for that variable and the requirements placed on
380 * that field.
381 */
382 const char *current_dir_name;
383 const char *toplevel_dir;
384
385 /* call_depth: recursion level counter for merging merge bases */
386 int call_depth;
387 };
388
389 struct version_info {
390 struct object_id oid;
391 unsigned short mode;
392 };
393
394 struct merged_info {
395 /* if is_null, ignore result. otherwise result has oid & mode */
396 struct version_info result;
397 unsigned is_null:1;
398
399 /*
400 * clean: whether the path in question is cleanly merged.
401 *
402 * see conflict_info.merged for more details.
403 */
404 unsigned clean:1;
405
406 /*
407 * basename_offset: offset of basename of path.
408 *
409 * perf optimization to avoid recomputing offset of final '/'
410 * character in pathname (0 if no '/' in pathname).
411 */
412 size_t basename_offset;
413
414 /*
415 * directory_name: containing directory name.
416 *
417 * Note that we assume directory_name is constructed such that
418 * strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name,
419 * i.e. string equality is equivalent to pointer equality. For this
420 * to hold, we have to be careful setting directory_name.
421 */
422 const char *directory_name;
423 };
424
425 struct conflict_info {
426 /*
427 * merged: the version of the path that will be written to working tree
428 *
429 * WARNING: It is critical to check merged.clean and ensure it is 0
430 * before reading any conflict_info fields outside of merged.
431 * Allocated merge_info structs will always have clean set to 1.
432 * Allocated conflict_info structs will have merged.clean set to 0
433 * initially. The merged.clean field is how we know if it is safe
434 * to access other parts of conflict_info besides merged; if a
435 * conflict_info's merged.clean is changed to 1, the rest of the
436 * algorithm is not allowed to look at anything outside of the
437 * merged member anymore.
438 */
439 struct merged_info merged;
440
441 /* oids & modes from each of the three trees for this path */
442 struct version_info stages[3];
443
444 /* pathnames for each stage; may differ due to rename detection */
445 const char *pathnames[3];
446
447 /* Whether this path is/was involved in a directory/file conflict */
448 unsigned df_conflict:1;
449
450 /*
451 * Whether this path is/was involved in a non-content conflict other
452 * than a directory/file conflict (e.g. rename/rename, rename/delete,
453 * file location based on possible directory rename).
454 */
455 unsigned path_conflict:1;
456
457 /*
458 * For filemask and dirmask, the ith bit corresponds to whether the
459 * ith entry is a file (filemask) or a directory (dirmask). Thus,
460 * filemask & dirmask is always zero, and filemask | dirmask is at
461 * most 7 but can be less when a path does not appear as either a
462 * file or a directory on at least one side of history.
463 *
464 * Note that these masks are related to enum merge_side, as the ith
465 * entry corresponds to side i.
466 *
467 * These values come from a traverse_trees() call; more info may be
468 * found looking at tree-walk.h's struct traverse_info,
469 * particularly the documentation above the "fn" member (note that
470 * filemask = mask & ~dirmask from that documentation).
471 */
472 unsigned filemask:3;
473 unsigned dirmask:3;
474
475 /*
476 * Optimization to track which stages match, to avoid the need to
477 * recompute it in multiple steps. Either 0 or at least 2 bits are
478 * set; if at least 2 bits are set, their corresponding stages match.
479 */
480 unsigned match_mask:3;
481 };
482
483 /*** Function Grouping: various utility functions ***/
484
485 /*
486 * For the next three macros, see warning for conflict_info.merged.
487 *
488 * In each of the below, mi is a struct merged_info*, and ci was defined
489 * as a struct conflict_info* (but we need to verify ci isn't actually
490 * pointed at a struct merged_info*).
491 *
492 * INITIALIZE_CI: Assign ci to mi but only if it's safe; set to NULL otherwise.
493 * VERIFY_CI: Ensure that something we assigned to a conflict_info* is one.
494 * ASSIGN_AND_VERIFY_CI: Similar to VERIFY_CI but do assignment first.
495 */
496 #define INITIALIZE_CI(ci, mi) do { \
497 (ci) = (!(mi) || (mi)->clean) ? NULL : (struct conflict_info *)(mi); \
498 } while (0)
499 #define VERIFY_CI(ci) assert(ci && !ci->merged.clean);
500 #define ASSIGN_AND_VERIFY_CI(ci, mi) do { \
501 (ci) = (struct conflict_info *)(mi); \
502 assert((ci) && !(mi)->clean); \
503 } while (0)
504
505 static void free_strmap_strings(struct strmap *map)
506 {
507 struct hashmap_iter iter;
508 struct strmap_entry *entry;
509
510 strmap_for_each_entry(map, &iter, entry) {
511 free((char*)entry->key);
512 }
513 }
514
515 static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,
516 int reinitialize)
517 {
518 struct rename_info *renames = &opti->renames;
519 int i;
520 void (*strmap_clear_func)(struct strmap *, int) =
521 reinitialize ? strmap_partial_clear : strmap_clear;
522 void (*strintmap_clear_func)(struct strintmap *) =
523 reinitialize ? strintmap_partial_clear : strintmap_clear;
524 void (*strset_clear_func)(struct strset *) =
525 reinitialize ? strset_partial_clear : strset_clear;
526
527 strmap_clear_func(&opti->paths, 0);
528
529 /*
530 * All keys and values in opti->conflicted are a subset of those in
531 * opti->paths. We don't want to deallocate anything twice, so we
532 * don't free the keys and we pass 0 for free_values.
533 */
534 strmap_clear_func(&opti->conflicted, 0);
535
536 if (opti->attr_index.cache_nr) /* true iff opt->renormalize */
537 discard_index(&opti->attr_index);
538
539 /* Free memory used by various renames maps */
540 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; ++i) {
541 strintmap_clear_func(&renames->dirs_removed[i]);
542 strmap_clear_func(&renames->dir_renames[i], 0);
543 strintmap_clear_func(&renames->relevant_sources[i]);
544 if (!reinitialize)
545 assert(renames->cached_pairs_valid_side == 0);
546 if (i != renames->cached_pairs_valid_side &&
547 -1 != renames->cached_pairs_valid_side) {
548 strset_clear_func(&renames->cached_target_names[i]);
549 strmap_clear_func(&renames->cached_pairs[i], 1);
550 strset_clear_func(&renames->cached_irrelevant[i]);
551 partial_clear_dir_rename_count(&renames->dir_rename_count[i]);
552 if (!reinitialize)
553 strmap_clear(&renames->dir_rename_count[i], 1);
554 }
555 }
556 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; ++i) {
557 strintmap_clear_func(&renames->deferred[i].possible_trivial_merges);
558 strset_clear_func(&renames->deferred[i].target_dirs);
559 renames->deferred[i].trivial_merges_okay = 1; /* 1 == maybe */
560 }
561 renames->cached_pairs_valid_side = 0;
562 renames->dir_rename_mask = 0;
563
564 if (!reinitialize) {
565 struct hashmap_iter iter;
566 struct strmap_entry *e;
567
568 /* Release and free each strbuf found in output */
569 strmap_for_each_entry(&opti->output, &iter, e) {
570 struct strbuf *sb = e->value;
571 strbuf_release(sb);
572 /*
573 * While strictly speaking we don't need to free(sb)
574 * here because we could pass free_values=1 when
575 * calling strmap_clear() on opti->output, that would
576 * require strmap_clear to do another
577 * strmap_for_each_entry() loop, so we just free it
578 * while we're iterating anyway.
579 */
580 free(sb);
581 }
582 strmap_clear(&opti->output, 0);
583 }
584
585 mem_pool_discard(&opti->pool, 0);
586
587 /* Clean out callback_data as well. */
588 FREE_AND_NULL(renames->callback_data);
589 renames->callback_data_nr = renames->callback_data_alloc = 0;
590 }
591
592 __attribute__((format (printf, 2, 3)))
593 static int err(struct merge_options *opt, const char *err, ...)
594 {
595 va_list params;
596 struct strbuf sb = STRBUF_INIT;
597
598 strbuf_addstr(&sb, "error: ");
599 va_start(params, err);
600 strbuf_vaddf(&sb, err, params);
601 va_end(params);
602
603 error("%s", sb.buf);
604 strbuf_release(&sb);
605
606 return -1;
607 }
608
609 static void format_commit(struct strbuf *sb,
610 int indent,
611 struct commit *commit)
612 {
613 struct merge_remote_desc *desc;
614 struct pretty_print_context ctx = {0};
615 ctx.abbrev = DEFAULT_ABBREV;
616
617 strbuf_addchars(sb, ' ', indent);
618 desc = merge_remote_util(commit);
619 if (desc) {
620 strbuf_addf(sb, "virtual %s\n", desc->name);
621 return;
622 }
623
624 format_commit_message(commit, "%h %s", sb, &ctx);
625 strbuf_addch(sb, '\n');
626 }
627
628 __attribute__((format (printf, 4, 5)))
629 static void path_msg(struct merge_options *opt,
630 const char *path,
631 int omittable_hint, /* skippable under --remerge-diff */
632 const char *fmt, ...)
633 {
634 va_list ap;
635 struct strbuf *sb = strmap_get(&opt->priv->output, path);
636 if (!sb) {
637 sb = xmalloc(sizeof(*sb));
638 strbuf_init(sb, 0);
639 strmap_put(&opt->priv->output, path, sb);
640 }
641
642 va_start(ap, fmt);
643 strbuf_vaddf(sb, fmt, ap);
644 va_end(ap);
645
646 strbuf_addch(sb, '\n');
647 }
648
649 static struct diff_filespec *pool_alloc_filespec(struct mem_pool *pool,
650 const char *path)
651 {
652 /* Similar to alloc_filespec(), but allocate from pool and reuse path */
653 struct diff_filespec *spec;
654
655 spec = mem_pool_calloc(pool, 1, sizeof(*spec));
656 spec->path = (char*)path; /* spec won't modify it */
657
658 spec->count = 1;
659 spec->is_binary = -1;
660 return spec;
661 }
662
663 static struct diff_filepair *pool_diff_queue(struct mem_pool *pool,
664 struct diff_queue_struct *queue,
665 struct diff_filespec *one,
666 struct diff_filespec *two)
667 {
668 /* Same code as diff_queue(), except allocate from pool */
669 struct diff_filepair *dp;
670
671 dp = mem_pool_calloc(pool, 1, sizeof(*dp));
672 dp->one = one;
673 dp->two = two;
674 if (queue)
675 diff_q(queue, dp);
676 return dp;
677 }
678
679 /* add a string to a strbuf, but converting "/" to "_" */
680 static void add_flattened_path(struct strbuf *out, const char *s)
681 {
682 size_t i = out->len;
683 strbuf_addstr(out, s);
684 for (; i < out->len; i++)
685 if (out->buf[i] == '/')
686 out->buf[i] = '_';
687 }
688
689 static char *unique_path(struct strmap *existing_paths,
690 const char *path,
691 const char *branch)
692 {
693 struct strbuf newpath = STRBUF_INIT;
694 int suffix = 0;
695 size_t base_len;
696
697 strbuf_addf(&newpath, "%s~", path);
698 add_flattened_path(&newpath, branch);
699
700 base_len = newpath.len;
701 while (strmap_contains(existing_paths, newpath.buf)) {
702 strbuf_setlen(&newpath, base_len);
703 strbuf_addf(&newpath, "_%d", suffix++);
704 }
705
706 return strbuf_detach(&newpath, NULL);
707 }
708
709 /*** Function Grouping: functions related to collect_merge_info() ***/
710
711 static int traverse_trees_wrapper_callback(int n,
712 unsigned long mask,
713 unsigned long dirmask,
714 struct name_entry *names,
715 struct traverse_info *info)
716 {
717 struct merge_options *opt = info->data;
718 struct rename_info *renames = &opt->priv->renames;
719 unsigned filemask = mask & ~dirmask;
720
721 assert(n==3);
722
723 if (!renames->callback_data_traverse_path)
724 renames->callback_data_traverse_path = xstrdup(info->traverse_path);
725
726 if (filemask && filemask == renames->dir_rename_mask)
727 renames->dir_rename_mask = 0x07;
728
729 ALLOC_GROW(renames->callback_data, renames->callback_data_nr + 1,
730 renames->callback_data_alloc);
731 renames->callback_data[renames->callback_data_nr].mask = mask;
732 renames->callback_data[renames->callback_data_nr].dirmask = dirmask;
733 COPY_ARRAY(renames->callback_data[renames->callback_data_nr].names,
734 names, 3);
735 renames->callback_data_nr++;
736
737 return mask;
738 }
739
740 /*
741 * Much like traverse_trees(), BUT:
742 * - read all the tree entries FIRST, saving them
743 * - note that the above step provides an opportunity to compute necessary
744 * additional details before the "real" traversal
745 * - loop through the saved entries and call the original callback on them
746 */
747 static int traverse_trees_wrapper(struct index_state *istate,
748 int n,
749 struct tree_desc *t,
750 struct traverse_info *info)
751 {
752 int ret, i, old_offset;
753 traverse_callback_t old_fn;
754 char *old_callback_data_traverse_path;
755 struct merge_options *opt = info->data;
756 struct rename_info *renames = &opt->priv->renames;
757
758 assert(renames->dir_rename_mask == 2 || renames->dir_rename_mask == 4);
759
760 old_callback_data_traverse_path = renames->callback_data_traverse_path;
761 old_fn = info->fn;
762 old_offset = renames->callback_data_nr;
763
764 renames->callback_data_traverse_path = NULL;
765 info->fn = traverse_trees_wrapper_callback;
766 ret = traverse_trees(istate, n, t, info);
767 if (ret < 0)
768 return ret;
769
770 info->traverse_path = renames->callback_data_traverse_path;
771 info->fn = old_fn;
772 for (i = old_offset; i < renames->callback_data_nr; ++i) {
773 info->fn(n,
774 renames->callback_data[i].mask,
775 renames->callback_data[i].dirmask,
776 renames->callback_data[i].names,
777 info);
778 }
779
780 renames->callback_data_nr = old_offset;
781 free(renames->callback_data_traverse_path);
782 renames->callback_data_traverse_path = old_callback_data_traverse_path;
783 info->traverse_path = NULL;
784 return 0;
785 }
786
787 static void setup_path_info(struct merge_options *opt,
788 struct string_list_item *result,
789 const char *current_dir_name,
790 int current_dir_name_len,
791 char *fullpath, /* we'll take over ownership */
792 struct name_entry *names,
793 struct name_entry *merged_version,
794 unsigned is_null, /* boolean */
795 unsigned df_conflict, /* boolean */
796 unsigned filemask,
797 unsigned dirmask,
798 int resolved /* boolean */)
799 {
800 /* result->util is void*, so mi is a convenience typed variable */
801 struct merged_info *mi;
802
803 assert(!is_null || resolved);
804 assert(!df_conflict || !resolved); /* df_conflict implies !resolved */
805 assert(resolved == (merged_version != NULL));
806
807 mi = mem_pool_calloc(&opt->priv->pool, 1,
808 resolved ? sizeof(struct merged_info) :
809 sizeof(struct conflict_info));
810 mi->directory_name = current_dir_name;
811 mi->basename_offset = current_dir_name_len;
812 mi->clean = !!resolved;
813 if (resolved) {
814 mi->result.mode = merged_version->mode;
815 oidcpy(&mi->result.oid, &merged_version->oid);
816 mi->is_null = !!is_null;
817 } else {
818 int i;
819 struct conflict_info *ci;
820
821 ASSIGN_AND_VERIFY_CI(ci, mi);
822 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
823 ci->pathnames[i] = fullpath;
824 ci->stages[i].mode = names[i].mode;
825 oidcpy(&ci->stages[i].oid, &names[i].oid);
826 }
827 ci->filemask = filemask;
828 ci->dirmask = dirmask;
829 ci->df_conflict = !!df_conflict;
830 if (dirmask)
831 /*
832 * Assume is_null for now, but if we have entries
833 * under the directory then when it is complete in
834 * write_completed_directory() it'll update this.
835 * Also, for D/F conflicts, we have to handle the
836 * directory first, then clear this bit and process
837 * the file to see how it is handled -- that occurs
838 * near the top of process_entry().
839 */
840 mi->is_null = 1;
841 }
842 strmap_put(&opt->priv->paths, fullpath, mi);
843 result->string = fullpath;
844 result->util = mi;
845 }
846
847 static void add_pair(struct merge_options *opt,
848 struct name_entry *names,
849 const char *pathname,
850 unsigned side,
851 unsigned is_add /* if false, is_delete */,
852 unsigned match_mask,
853 unsigned dir_rename_mask)
854 {
855 struct diff_filespec *one, *two;
856 struct rename_info *renames = &opt->priv->renames;
857 int names_idx = is_add ? side : 0;
858
859 if (is_add) {
860 assert(match_mask == 0 || match_mask == 6);
861 if (strset_contains(&renames->cached_target_names[side],
862 pathname))
863 return;
864 } else {
865 unsigned content_relevant = (match_mask == 0);
866 unsigned location_relevant = (dir_rename_mask == 0x07);
867
868 assert(match_mask == 0 || match_mask == 3 || match_mask == 5);
869
870 /*
871 * If pathname is found in cached_irrelevant[side] due to
872 * previous pick but for this commit content is relevant,
873 * then we need to remove it from cached_irrelevant.
874 */
875 if (content_relevant)
876 /* strset_remove is no-op if strset doesn't have key */
877 strset_remove(&renames->cached_irrelevant[side],
878 pathname);
879
880 /*
881 * We do not need to re-detect renames for paths that we already
882 * know the pairing, i.e. for cached_pairs (or
883 * cached_irrelevant). However, handle_deferred_entries() needs
884 * to loop over the union of keys from relevant_sources[side] and
885 * cached_pairs[side], so for simplicity we set relevant_sources
886 * for all the cached_pairs too and then strip them back out in
887 * prune_cached_from_relevant() at the beginning of
888 * detect_regular_renames().
889 */
890 if (content_relevant || location_relevant) {
891 /* content_relevant trumps location_relevant */
892 strintmap_set(&renames->relevant_sources[side], pathname,
893 content_relevant ? RELEVANT_CONTENT : RELEVANT_LOCATION);
894 }
895
896 /*
897 * Avoid creating pair if we've already cached rename results.
898 * Note that we do this after setting relevant_sources[side]
899 * as noted in the comment above.
900 */
901 if (strmap_contains(&renames->cached_pairs[side], pathname) ||
902 strset_contains(&renames->cached_irrelevant[side], pathname))
903 return;
904 }
905
906 one = pool_alloc_filespec(&opt->priv->pool, pathname);
907 two = pool_alloc_filespec(&opt->priv->pool, pathname);
908 fill_filespec(is_add ? two : one,
909 &names[names_idx].oid, 1, names[names_idx].mode);
910 pool_diff_queue(&opt->priv->pool, &renames->pairs[side], one, two);
911 }
912
913 static void collect_rename_info(struct merge_options *opt,
914 struct name_entry *names,
915 const char *dirname,
916 const char *fullname,
917 unsigned filemask,
918 unsigned dirmask,
919 unsigned match_mask)
920 {
921 struct rename_info *renames = &opt->priv->renames;
922 unsigned side;
923
924 /*
925 * Update dir_rename_mask (determines ignore-rename-source validity)
926 *
927 * dir_rename_mask helps us keep track of when directory rename
928 * detection may be relevant. Basically, whenver a directory is
929 * removed on one side of history, and a file is added to that
930 * directory on the other side of history, directory rename
931 * detection is relevant (meaning we have to detect renames for all
932 * files within that directory to deduce where the directory
933 * moved). Also, whenever a directory needs directory rename
934 * detection, due to the "majority rules" choice for where to move
935 * it (see t6423 testcase 1f), we also need to detect renames for
936 * all files within subdirectories of that directory as well.
937 *
938 * Here we haven't looked at files within the directory yet, we are
939 * just looking at the directory itself. So, if we aren't yet in
940 * a case where a parent directory needed directory rename detection
941 * (i.e. dir_rename_mask != 0x07), and if the directory was removed
942 * on one side of history, record the mask of the other side of
943 * history in dir_rename_mask.
944 */
945 if (renames->dir_rename_mask != 0x07 &&
946 (dirmask == 3 || dirmask == 5)) {
947 /* simple sanity check */
948 assert(renames->dir_rename_mask == 0 ||
949 renames->dir_rename_mask == (dirmask & ~1));
950 /* update dir_rename_mask; have it record mask of new side */
951 renames->dir_rename_mask = (dirmask & ~1);
952 }
953
954 /* Update dirs_removed, as needed */
955 if (dirmask == 1 || dirmask == 3 || dirmask == 5) {
956 /* absent_mask = 0x07 - dirmask; sides = absent_mask/2 */
957 unsigned sides = (0x07 - dirmask)/2;
958 unsigned relevance = (renames->dir_rename_mask == 0x07) ?
959 RELEVANT_FOR_ANCESTOR : NOT_RELEVANT;
960 /*
961 * Record relevance of this directory. However, note that
962 * when collect_merge_info_callback() recurses into this
963 * directory and calls collect_rename_info() on paths
964 * within that directory, if we find a path that was added
965 * to this directory on the other side of history, we will
966 * upgrade this value to RELEVANT_FOR_SELF; see below.
967 */
968 if (sides & 1)
969 strintmap_set(&renames->dirs_removed[1], fullname,
970 relevance);
971 if (sides & 2)
972 strintmap_set(&renames->dirs_removed[2], fullname,
973 relevance);
974 }
975
976 /*
977 * Here's the block that potentially upgrades to RELEVANT_FOR_SELF.
978 * When we run across a file added to a directory. In such a case,
979 * find the directory of the file and upgrade its relevance.
980 */
981 if (renames->dir_rename_mask == 0x07 &&
982 (filemask == 2 || filemask == 4)) {
983 /*
984 * Need directory rename for parent directory on other side
985 * of history from added file. Thus
986 * side = (~filemask & 0x06) >> 1
987 * or
988 * side = 3 - (filemask/2).
989 */
990 unsigned side = 3 - (filemask >> 1);
991 strintmap_set(&renames->dirs_removed[side], dirname,
992 RELEVANT_FOR_SELF);
993 }
994
995 if (filemask == 0 || filemask == 7)
996 return;
997
998 for (side = MERGE_SIDE1; side <= MERGE_SIDE2; ++side) {
999 unsigned side_mask = (1 << side);
1000
1001 /* Check for deletion on side */
1002 if ((filemask & 1) && !(filemask & side_mask))
1003 add_pair(opt, names, fullname, side, 0 /* delete */,
1004 match_mask & filemask,
1005 renames->dir_rename_mask);
1006
1007 /* Check for addition on side */
1008 if (!(filemask & 1) && (filemask & side_mask))
1009 add_pair(opt, names, fullname, side, 1 /* add */,
1010 match_mask & filemask,
1011 renames->dir_rename_mask);
1012 }
1013 }
1014
1015 static int collect_merge_info_callback(int n,
1016 unsigned long mask,
1017 unsigned long dirmask,
1018 struct name_entry *names,
1019 struct traverse_info *info)
1020 {
1021 /*
1022 * n is 3. Always.
1023 * common ancestor (mbase) has mask 1, and stored in index 0 of names
1024 * head of side 1 (side1) has mask 2, and stored in index 1 of names
1025 * head of side 2 (side2) has mask 4, and stored in index 2 of names
1026 */
1027 struct merge_options *opt = info->data;
1028 struct merge_options_internal *opti = opt->priv;
1029 struct rename_info *renames = &opt->priv->renames;
1030 struct string_list_item pi; /* Path Info */
1031 struct conflict_info *ci; /* typed alias to pi.util (which is void*) */
1032 struct name_entry *p;
1033 size_t len;
1034 char *fullpath;
1035 const char *dirname = opti->current_dir_name;
1036 unsigned prev_dir_rename_mask = renames->dir_rename_mask;
1037 unsigned filemask = mask & ~dirmask;
1038 unsigned match_mask = 0; /* will be updated below */
1039 unsigned mbase_null = !(mask & 1);
1040 unsigned side1_null = !(mask & 2);
1041 unsigned side2_null = !(mask & 4);
1042 unsigned side1_matches_mbase = (!side1_null && !mbase_null &&
1043 names[0].mode == names[1].mode &&
1044 oideq(&names[0].oid, &names[1].oid));
1045 unsigned side2_matches_mbase = (!side2_null && !mbase_null &&
1046 names[0].mode == names[2].mode &&
1047 oideq(&names[0].oid, &names[2].oid));
1048 unsigned sides_match = (!side1_null && !side2_null &&
1049 names[1].mode == names[2].mode &&
1050 oideq(&names[1].oid, &names[2].oid));
1051
1052 /*
1053 * Note: When a path is a file on one side of history and a directory
1054 * in another, we have a directory/file conflict. In such cases, if
1055 * the conflict doesn't resolve from renames and deletions, then we
1056 * always leave directories where they are and move files out of the
1057 * way. Thus, while struct conflict_info has a df_conflict field to
1058 * track such conflicts, we ignore that field for any directories at
1059 * a path and only pay attention to it for files at the given path.
1060 * The fact that we leave directories were they are also means that
1061 * we do not need to worry about getting additional df_conflict
1062 * information propagated from parent directories down to children
1063 * (unlike, say traverse_trees_recursive() in unpack-trees.c, which
1064 * sets a newinfo.df_conflicts field specifically to propagate it).
1065 */
1066 unsigned df_conflict = (filemask != 0) && (dirmask != 0);
1067
1068 /* n = 3 is a fundamental assumption. */
1069 if (n != 3)
1070 BUG("Called collect_merge_info_callback wrong");
1071
1072 /*
1073 * A bunch of sanity checks verifying that traverse_trees() calls
1074 * us the way I expect. Could just remove these at some point,
1075 * though maybe they are helpful to future code readers.
1076 */
1077 assert(mbase_null == is_null_oid(&names[0].oid));
1078 assert(side1_null == is_null_oid(&names[1].oid));
1079 assert(side2_null == is_null_oid(&names[2].oid));
1080 assert(!mbase_null || !side1_null || !side2_null);
1081 assert(mask > 0 && mask < 8);
1082
1083 /* Determine match_mask */
1084 if (side1_matches_mbase)
1085 match_mask = (side2_matches_mbase ? 7 : 3);
1086 else if (side2_matches_mbase)
1087 match_mask = 5;
1088 else if (sides_match)
1089 match_mask = 6;
1090
1091 /*
1092 * Get the name of the relevant filepath, which we'll pass to
1093 * setup_path_info() for tracking.
1094 */
1095 p = names;
1096 while (!p->mode)
1097 p++;
1098 len = traverse_path_len(info, p->pathlen);
1099
1100 /* +1 in both of the following lines to include the NUL byte */
1101 fullpath = mem_pool_alloc(&opt->priv->pool, len + 1);
1102 make_traverse_path(fullpath, len + 1, info, p->path, p->pathlen);
1103
1104 /*
1105 * If mbase, side1, and side2 all match, we can resolve early. Even
1106 * if these are trees, there will be no renames or anything
1107 * underneath.
1108 */
1109 if (side1_matches_mbase && side2_matches_mbase) {
1110 /* mbase, side1, & side2 all match; use mbase as resolution */
1111 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
1112 names, names+0, mbase_null, 0 /* df_conflict */,
1113 filemask, dirmask, 1 /* resolved */);
1114 return mask;
1115 }
1116
1117 /*
1118 * If the sides match, and all three paths are present and are
1119 * files, then we can take either as the resolution. We can't do
1120 * this with trees, because there may be rename sources from the
1121 * merge_base.
1122 */
1123 if (sides_match && filemask == 0x07) {
1124 /* use side1 (== side2) version as resolution */
1125 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
1126 names, names+1, side1_null, 0,
1127 filemask, dirmask, 1);
1128 return mask;
1129 }
1130
1131 /*
1132 * If side1 matches mbase and all three paths are present and are
1133 * files, then we can use side2 as the resolution. We cannot
1134 * necessarily do so this for trees, because there may be rename
1135 * destinations within side2.
1136 */
1137 if (side1_matches_mbase && filemask == 0x07) {
1138 /* use side2 version as resolution */
1139 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
1140 names, names+2, side2_null, 0,
1141 filemask, dirmask, 1);
1142 return mask;
1143 }
1144
1145 /* Similar to above but swapping sides 1 and 2 */
1146 if (side2_matches_mbase && filemask == 0x07) {
1147 /* use side1 version as resolution */
1148 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
1149 names, names+1, side1_null, 0,
1150 filemask, dirmask, 1);
1151 return mask;
1152 }
1153
1154 /*
1155 * Sometimes we can tell that a source path need not be included in
1156 * rename detection -- namely, whenever either
1157 * side1_matches_mbase && side2_null
1158 * or
1159 * side2_matches_mbase && side1_null
1160 * However, we call collect_rename_info() even in those cases,
1161 * because exact renames are cheap and would let us remove both a
1162 * source and destination path. We'll cull the unneeded sources
1163 * later.
1164 */
1165 collect_rename_info(opt, names, dirname, fullpath,
1166 filemask, dirmask, match_mask);
1167
1168 /*
1169 * None of the special cases above matched, so we have a
1170 * provisional conflict. (Rename detection might allow us to
1171 * unconflict some more cases, but that comes later so all we can
1172 * do now is record the different non-null file hashes.)
1173 */
1174 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
1175 names, NULL, 0, df_conflict, filemask, dirmask, 0);
1176
1177 ci = pi.util;
1178 VERIFY_CI(ci);
1179 ci->match_mask = match_mask;
1180
1181 /* If dirmask, recurse into subdirectories */
1182 if (dirmask) {
1183 struct traverse_info newinfo;
1184 struct tree_desc t[3];
1185 void *buf[3] = {NULL, NULL, NULL};
1186 const char *original_dir_name;
1187 int i, ret, side;
1188
1189 /*
1190 * Check for whether we can avoid recursing due to one side
1191 * matching the merge base. The side that does NOT match is
1192 * the one that might have a rename destination we need.
1193 */
1194 assert(!side1_matches_mbase || !side2_matches_mbase);
1195 side = side1_matches_mbase ? MERGE_SIDE2 :
1196 side2_matches_mbase ? MERGE_SIDE1 : MERGE_BASE;
1197 if (filemask == 0 && (dirmask == 2 || dirmask == 4)) {
1198 /*
1199 * Also defer recursing into new directories; set up a
1200 * few variables to let us do so.
1201 */
1202 ci->match_mask = (7 - dirmask);
1203 side = dirmask / 2;
1204 }
1205 if (renames->dir_rename_mask != 0x07 &&
1206 side != MERGE_BASE &&
1207 renames->deferred[side].trivial_merges_okay &&
1208 !strset_contains(&renames->deferred[side].target_dirs,
1209 pi.string)) {
1210 strintmap_set(&renames->deferred[side].possible_trivial_merges,
1211 pi.string, renames->dir_rename_mask);
1212 renames->dir_rename_mask = prev_dir_rename_mask;
1213 return mask;
1214 }
1215
1216 /* We need to recurse */
1217 ci->match_mask &= filemask;
1218 newinfo = *info;
1219 newinfo.prev = info;
1220 newinfo.name = p->path;
1221 newinfo.namelen = p->pathlen;
1222 newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1);
1223 /*
1224 * If this directory we are about to recurse into cared about
1225 * its parent directory (the current directory) having a D/F
1226 * conflict, then we'd propagate the masks in this way:
1227 * newinfo.df_conflicts |= (mask & ~dirmask);
1228 * But we don't worry about propagating D/F conflicts. (See
1229 * comment near setting of local df_conflict variable near
1230 * the beginning of this function).
1231 */
1232
1233 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
1234 if (i == 1 && side1_matches_mbase)
1235 t[1] = t[0];
1236 else if (i == 2 && side2_matches_mbase)
1237 t[2] = t[0];
1238 else if (i == 2 && sides_match)
1239 t[2] = t[1];
1240 else {
1241 const struct object_id *oid = NULL;
1242 if (dirmask & 1)
1243 oid = &names[i].oid;
1244 buf[i] = fill_tree_descriptor(opt->repo,
1245 t + i, oid);
1246 }
1247 dirmask >>= 1;
1248 }
1249
1250 original_dir_name = opti->current_dir_name;
1251 opti->current_dir_name = pi.string;
1252 if (renames->dir_rename_mask == 0 ||
1253 renames->dir_rename_mask == 0x07)
1254 ret = traverse_trees(NULL, 3, t, &newinfo);
1255 else
1256 ret = traverse_trees_wrapper(NULL, 3, t, &newinfo);
1257 opti->current_dir_name = original_dir_name;
1258 renames->dir_rename_mask = prev_dir_rename_mask;
1259
1260 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++)
1261 free(buf[i]);
1262
1263 if (ret < 0)
1264 return -1;
1265 }
1266
1267 return mask;
1268 }
1269
1270 static void resolve_trivial_directory_merge(struct conflict_info *ci, int side)
1271 {
1272 VERIFY_CI(ci);
1273 assert((side == 1 && ci->match_mask == 5) ||
1274 (side == 2 && ci->match_mask == 3));
1275 oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
1276 ci->merged.result.mode = ci->stages[side].mode;
1277 ci->merged.is_null = is_null_oid(&ci->stages[side].oid);
1278 ci->match_mask = 0;
1279 ci->merged.clean = 1; /* (ci->filemask == 0); */
1280 }
1281
1282 static int handle_deferred_entries(struct merge_options *opt,
1283 struct traverse_info *info)
1284 {
1285 struct rename_info *renames = &opt->priv->renames;
1286 struct hashmap_iter iter;
1287 struct strmap_entry *entry;
1288 int side, ret = 0;
1289 int path_count_before, path_count_after = 0;
1290
1291 path_count_before = strmap_get_size(&opt->priv->paths);
1292 for (side = MERGE_SIDE1; side <= MERGE_SIDE2; side++) {
1293 unsigned optimization_okay = 1;
1294 struct strintmap copy;
1295
1296 /* Loop over the set of paths we need to know rename info for */
1297 strset_for_each_entry(&renames->relevant_sources[side],
1298 &iter, entry) {
1299 char *rename_target, *dir, *dir_marker;
1300 struct strmap_entry *e;
1301
1302 /*
1303 * If we don't know delete/rename info for this path,
1304 * then we need to recurse into all trees to get all
1305 * adds to make sure we have it.
1306 */
1307 if (strset_contains(&renames->cached_irrelevant[side],
1308 entry->key))
1309 continue;
1310 e = strmap_get_entry(&renames->cached_pairs[side],
1311 entry->key);
1312 if (!e) {
1313 optimization_okay = 0;
1314 break;
1315 }
1316
1317 /* If this is a delete, we have enough info already */
1318 rename_target = e->value;
1319 if (!rename_target)
1320 continue;
1321
1322 /* If we already walked the rename target, we're good */
1323 if (strmap_contains(&opt->priv->paths, rename_target))
1324 continue;
1325
1326 /*
1327 * Otherwise, we need to get a list of directories that
1328 * will need to be recursed into to get this
1329 * rename_target.
1330 */
1331 dir = xstrdup(rename_target);
1332 while ((dir_marker = strrchr(dir, '/'))) {
1333 *dir_marker = '\0';
1334 if (strset_contains(&renames->deferred[side].target_dirs,
1335 dir))
1336 break;
1337 strset_add(&renames->deferred[side].target_dirs,
1338 dir);
1339 }
1340 free(dir);
1341 }
1342 renames->deferred[side].trivial_merges_okay = optimization_okay;
1343 /*
1344 * We need to recurse into any directories in
1345 * possible_trivial_merges[side] found in target_dirs[side].
1346 * But when we recurse, we may need to queue up some of the
1347 * subdirectories for possible_trivial_merges[side]. Since
1348 * we can't safely iterate through a hashmap while also adding
1349 * entries, move the entries into 'copy', iterate over 'copy',
1350 * and then we'll also iterate anything added into
1351 * possible_trivial_merges[side] once this loop is done.
1352 */
1353 copy = renames->deferred[side].possible_trivial_merges;
1354 strintmap_init_with_options(&renames->deferred[side].possible_trivial_merges,
1355 0,
1356 &opt->priv->pool,
1357 0);
1358 strintmap_for_each_entry(&copy, &iter, entry) {
1359 const char *path = entry->key;
1360 unsigned dir_rename_mask = (intptr_t)entry->value;
1361 struct conflict_info *ci;
1362 unsigned dirmask;
1363 struct tree_desc t[3];
1364 void *buf[3] = {NULL,};
1365 int i;
1366
1367 ci = strmap_get(&opt->priv->paths, path);
1368 VERIFY_CI(ci);
1369 dirmask = ci->dirmask;
1370
1371 if (optimization_okay &&
1372 !strset_contains(&renames->deferred[side].target_dirs,
1373 path)) {
1374 resolve_trivial_directory_merge(ci, side);
1375 continue;
1376 }
1377
1378 info->name = path;
1379 info->namelen = strlen(path);
1380 info->pathlen = info->namelen + 1;
1381
1382 for (i = 0; i < 3; i++, dirmask >>= 1) {
1383 if (i == 1 && ci->match_mask == 3)
1384 t[1] = t[0];
1385 else if (i == 2 && ci->match_mask == 5)
1386 t[2] = t[0];
1387 else if (i == 2 && ci->match_mask == 6)
1388 t[2] = t[1];
1389 else {
1390 const struct object_id *oid = NULL;
1391 if (dirmask & 1)
1392 oid = &ci->stages[i].oid;
1393 buf[i] = fill_tree_descriptor(opt->repo,
1394 t+i, oid);
1395 }
1396 }
1397
1398 ci->match_mask &= ci->filemask;
1399 opt->priv->current_dir_name = path;
1400 renames->dir_rename_mask = dir_rename_mask;
1401 if (renames->dir_rename_mask == 0 ||
1402 renames->dir_rename_mask == 0x07)
1403 ret = traverse_trees(NULL, 3, t, info);
1404 else
1405 ret = traverse_trees_wrapper(NULL, 3, t, info);
1406
1407 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++)
1408 free(buf[i]);
1409
1410 if (ret < 0)
1411 return ret;
1412 }
1413 strintmap_clear(&copy);
1414 strintmap_for_each_entry(&renames->deferred[side].possible_trivial_merges,
1415 &iter, entry) {
1416 const char *path = entry->key;
1417 struct conflict_info *ci;
1418
1419 ci = strmap_get(&opt->priv->paths, path);
1420 VERIFY_CI(ci);
1421
1422 assert(renames->deferred[side].trivial_merges_okay &&
1423 !strset_contains(&renames->deferred[side].target_dirs,
1424 path));
1425 resolve_trivial_directory_merge(ci, side);
1426 }
1427 if (!optimization_okay || path_count_after)
1428 path_count_after = strmap_get_size(&opt->priv->paths);
1429 }
1430 if (path_count_after) {
1431 /*
1432 * The choice of wanted_factor here does not affect
1433 * correctness, only performance. When the
1434 * path_count_after / path_count_before
1435 * ratio is high, redoing after renames is a big
1436 * performance boost. I suspect that redoing is a wash
1437 * somewhere near a value of 2, and below that redoing will
1438 * slow things down. I applied a fudge factor and picked
1439 * 3; see the commit message when this was introduced for
1440 * back of the envelope calculations for this ratio.
1441 */
1442 const int wanted_factor = 3;
1443
1444 /* We should only redo collect_merge_info one time */
1445 assert(renames->redo_after_renames == 0);
1446
1447 if (path_count_after / path_count_before >= wanted_factor) {
1448 renames->redo_after_renames = 1;
1449 renames->cached_pairs_valid_side = -1;
1450 }
1451 } else if (renames->redo_after_renames == 2)
1452 renames->redo_after_renames = 0;
1453 return ret;
1454 }
1455
1456 static int collect_merge_info(struct merge_options *opt,
1457 struct tree *merge_base,
1458 struct tree *side1,
1459 struct tree *side2)
1460 {
1461 int ret;
1462 struct tree_desc t[3];
1463 struct traverse_info info;
1464
1465 opt->priv->toplevel_dir = "";
1466 opt->priv->current_dir_name = opt->priv->toplevel_dir;
1467 setup_traverse_info(&info, opt->priv->toplevel_dir);
1468 info.fn = collect_merge_info_callback;
1469 info.data = opt;
1470 info.show_all_errors = 1;
1471
1472 parse_tree(merge_base);
1473 parse_tree(side1);
1474 parse_tree(side2);
1475 init_tree_desc(t + 0, merge_base->buffer, merge_base->size);
1476 init_tree_desc(t + 1, side1->buffer, side1->size);
1477 init_tree_desc(t + 2, side2->buffer, side2->size);
1478
1479 trace2_region_enter("merge", "traverse_trees", opt->repo);
1480 ret = traverse_trees(NULL, 3, t, &info);
1481 if (ret == 0)
1482 ret = handle_deferred_entries(opt, &info);
1483 trace2_region_leave("merge", "traverse_trees", opt->repo);
1484
1485 return ret;
1486 }
1487
1488 /*** Function Grouping: functions related to threeway content merges ***/
1489
1490 static int find_first_merges(struct repository *repo,
1491 const char *path,
1492 struct commit *a,
1493 struct commit *b,
1494 struct object_array *result)
1495 {
1496 int i, j;
1497 struct object_array merges = OBJECT_ARRAY_INIT;
1498 struct commit *commit;
1499 int contains_another;
1500
1501 char merged_revision[GIT_MAX_HEXSZ + 2];
1502 const char *rev_args[] = { "rev-list", "--merges", "--ancestry-path",
1503 "--all", merged_revision, NULL };
1504 struct rev_info revs;
1505 struct setup_revision_opt rev_opts;
1506
1507 memset(result, 0, sizeof(struct object_array));
1508 memset(&rev_opts, 0, sizeof(rev_opts));
1509
1510 /* get all revisions that merge commit a */
1511 xsnprintf(merged_revision, sizeof(merged_revision), "^%s",
1512 oid_to_hex(&a->object.oid));
1513 repo_init_revisions(repo, &revs, NULL);
1514 rev_opts.submodule = path;
1515 /* FIXME: can't handle linked worktrees in submodules yet */
1516 revs.single_worktree = path != NULL;
1517 setup_revisions(ARRAY_SIZE(rev_args)-1, rev_args, &revs, &rev_opts);
1518
1519 /* save all revisions from the above list that contain b */
1520 if (prepare_revision_walk(&revs))
1521 die("revision walk setup failed");
1522 while ((commit = get_revision(&revs)) != NULL) {
1523 struct object *o = &(commit->object);
1524 if (in_merge_bases(b, commit))
1525 add_object_array(o, NULL, &merges);
1526 }
1527 reset_revision_walk();
1528
1529 /* Now we've got all merges that contain a and b. Prune all
1530 * merges that contain another found merge and save them in
1531 * result.
1532 */
1533 for (i = 0; i < merges.nr; i++) {
1534 struct commit *m1 = (struct commit *) merges.objects[i].item;
1535
1536 contains_another = 0;
1537 for (j = 0; j < merges.nr; j++) {
1538 struct commit *m2 = (struct commit *) merges.objects[j].item;
1539 if (i != j && in_merge_bases(m2, m1)) {
1540 contains_another = 1;
1541 break;
1542 }
1543 }
1544
1545 if (!contains_another)
1546 add_object_array(merges.objects[i].item, NULL, result);
1547 }
1548
1549 object_array_clear(&merges);
1550 return result->nr;
1551 }
1552
1553 static int merge_submodule(struct merge_options *opt,
1554 const char *path,
1555 const struct object_id *o,
1556 const struct object_id *a,
1557 const struct object_id *b,
1558 struct object_id *result)
1559 {
1560 struct commit *commit_o, *commit_a, *commit_b;
1561 int parent_count;
1562 struct object_array merges;
1563 struct strbuf sb = STRBUF_INIT;
1564
1565 int i;
1566 int search = !opt->priv->call_depth;
1567
1568 /* store fallback answer in result in case we fail */
1569 oidcpy(result, opt->priv->call_depth ? o : a);
1570
1571 /* we can not handle deletion conflicts */
1572 if (is_null_oid(o))
1573 return 0;
1574 if (is_null_oid(a))
1575 return 0;
1576 if (is_null_oid(b))
1577 return 0;
1578
1579 if (add_submodule_odb(path)) {
1580 path_msg(opt, path, 0,
1581 _("Failed to merge submodule %s (not checked out)"),
1582 path);
1583 return 0;
1584 }
1585
1586 if (!(commit_o = lookup_commit_reference(opt->repo, o)) ||
1587 !(commit_a = lookup_commit_reference(opt->repo, a)) ||
1588 !(commit_b = lookup_commit_reference(opt->repo, b))) {
1589 path_msg(opt, path, 0,
1590 _("Failed to merge submodule %s (commits not present)"),
1591 path);
1592 return 0;
1593 }
1594
1595 /* check whether both changes are forward */
1596 if (!in_merge_bases(commit_o, commit_a) ||
1597 !in_merge_bases(commit_o, commit_b)) {
1598 path_msg(opt, path, 0,
1599 _("Failed to merge submodule %s "
1600 "(commits don't follow merge-base)"),
1601 path);
1602 return 0;
1603 }
1604
1605 /* Case #1: a is contained in b or vice versa */
1606 if (in_merge_bases(commit_a, commit_b)) {
1607 oidcpy(result, b);
1608 path_msg(opt, path, 1,
1609 _("Note: Fast-forwarding submodule %s to %s"),
1610 path, oid_to_hex(b));
1611 return 1;
1612 }
1613 if (in_merge_bases(commit_b, commit_a)) {
1614 oidcpy(result, a);
1615 path_msg(opt, path, 1,
1616 _("Note: Fast-forwarding submodule %s to %s"),
1617 path, oid_to_hex(a));
1618 return 1;
1619 }
1620
1621 /*
1622 * Case #2: There are one or more merges that contain a and b in
1623 * the submodule. If there is only one, then present it as a
1624 * suggestion to the user, but leave it marked unmerged so the
1625 * user needs to confirm the resolution.
1626 */
1627
1628 /* Skip the search if makes no sense to the calling context. */
1629 if (!search)
1630 return 0;
1631
1632 /* find commit which merges them */
1633 parent_count = find_first_merges(opt->repo, path, commit_a, commit_b,
1634 &merges);
1635 switch (parent_count) {
1636 case 0:
1637 path_msg(opt, path, 0, _("Failed to merge submodule %s"), path);
1638 break;
1639
1640 case 1:
1641 format_commit(&sb, 4,
1642 (struct commit *)merges.objects[0].item);
1643 path_msg(opt, path, 0,
1644 _("Failed to merge submodule %s, but a possible merge "
1645 "resolution exists:\n%s\n"),
1646 path, sb.buf);
1647 path_msg(opt, path, 1,
1648 _("If this is correct simply add it to the index "
1649 "for example\n"
1650 "by using:\n\n"
1651 " git update-index --cacheinfo 160000 %s \"%s\"\n\n"
1652 "which will accept this suggestion.\n"),
1653 oid_to_hex(&merges.objects[0].item->oid), path);
1654 strbuf_release(&sb);
1655 break;
1656 default:
1657 for (i = 0; i < merges.nr; i++)
1658 format_commit(&sb, 4,
1659 (struct commit *)merges.objects[i].item);
1660 path_msg(opt, path, 0,
1661 _("Failed to merge submodule %s, but multiple "
1662 "possible merges exist:\n%s"), path, sb.buf);
1663 strbuf_release(&sb);
1664 }
1665
1666 object_array_clear(&merges);
1667 return 0;
1668 }
1669
1670 static void initialize_attr_index(struct merge_options *opt)
1671 {
1672 /*
1673 * The renormalize_buffer() functions require attributes, and
1674 * annoyingly those can only be read from the working tree or from
1675 * an index_state. merge-ort doesn't have an index_state, so we
1676 * generate a fake one containing only attribute information.
1677 */
1678 struct merged_info *mi;
1679 struct index_state *attr_index = &opt->priv->attr_index;
1680 struct cache_entry *ce;
1681
1682 attr_index->initialized = 1;
1683
1684 if (!opt->renormalize)
1685 return;
1686
1687 mi = strmap_get(&opt->priv->paths, GITATTRIBUTES_FILE);
1688 if (!mi)
1689 return;
1690
1691 if (mi->clean) {
1692 int len = strlen(GITATTRIBUTES_FILE);
1693 ce = make_empty_cache_entry(attr_index, len);
1694 ce->ce_mode = create_ce_mode(mi->result.mode);
1695 ce->ce_flags = create_ce_flags(0);
1696 ce->ce_namelen = len;
1697 oidcpy(&ce->oid, &mi->result.oid);
1698 memcpy(ce->name, GITATTRIBUTES_FILE, len);
1699 add_index_entry(attr_index, ce,
1700 ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
1701 get_stream_filter(attr_index, GITATTRIBUTES_FILE, &ce->oid);
1702 } else {
1703 int stage, len;
1704 struct conflict_info *ci;
1705
1706 ASSIGN_AND_VERIFY_CI(ci, mi);
1707 for (stage = 0; stage < 3; stage++) {
1708 unsigned stage_mask = (1 << stage);
1709
1710 if (!(ci->filemask & stage_mask))
1711 continue;
1712 len = strlen(GITATTRIBUTES_FILE);
1713 ce = make_empty_cache_entry(attr_index, len);
1714 ce->ce_mode = create_ce_mode(ci->stages[stage].mode);
1715 ce->ce_flags = create_ce_flags(stage);
1716 ce->ce_namelen = len;
1717 oidcpy(&ce->oid, &ci->stages[stage].oid);
1718 memcpy(ce->name, GITATTRIBUTES_FILE, len);
1719 add_index_entry(attr_index, ce,
1720 ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
1721 get_stream_filter(attr_index, GITATTRIBUTES_FILE,
1722 &ce->oid);
1723 }
1724 }
1725 }
1726
1727 static int merge_3way(struct merge_options *opt,
1728 const char *path,
1729 const struct object_id *o,
1730 const struct object_id *a,
1731 const struct object_id *b,
1732 const char *pathnames[3],
1733 const int extra_marker_size,
1734 mmbuffer_t *result_buf)
1735 {
1736 mmfile_t orig, src1, src2;
1737 struct ll_merge_options ll_opts = {0};
1738 char *base, *name1, *name2;
1739 int merge_status;
1740
1741 if (!opt->priv->attr_index.initialized)
1742 initialize_attr_index(opt);
1743
1744 ll_opts.renormalize = opt->renormalize;
1745 ll_opts.extra_marker_size = extra_marker_size;
1746 ll_opts.xdl_opts = opt->xdl_opts;
1747
1748 if (opt->priv->call_depth) {
1749 ll_opts.virtual_ancestor = 1;
1750 ll_opts.variant = 0;
1751 } else {
1752 switch (opt->recursive_variant) {
1753 case MERGE_VARIANT_OURS:
1754 ll_opts.variant = XDL_MERGE_FAVOR_OURS;
1755 break;
1756 case MERGE_VARIANT_THEIRS:
1757 ll_opts.variant = XDL_MERGE_FAVOR_THEIRS;
1758 break;
1759 default:
1760 ll_opts.variant = 0;
1761 break;
1762 }
1763 }
1764
1765 assert(pathnames[0] && pathnames[1] && pathnames[2] && opt->ancestor);
1766 if (pathnames[0] == pathnames[1] && pathnames[1] == pathnames[2]) {
1767 base = mkpathdup("%s", opt->ancestor);
1768 name1 = mkpathdup("%s", opt->branch1);
1769 name2 = mkpathdup("%s", opt->branch2);
1770 } else {
1771 base = mkpathdup("%s:%s", opt->ancestor, pathnames[0]);
1772 name1 = mkpathdup("%s:%s", opt->branch1, pathnames[1]);
1773 name2 = mkpathdup("%s:%s", opt->branch2, pathnames[2]);
1774 }
1775
1776 read_mmblob(&orig, o);
1777 read_mmblob(&src1, a);
1778 read_mmblob(&src2, b);
1779
1780 merge_status = ll_merge(result_buf, path, &orig, base,
1781 &src1, name1, &src2, name2,
1782 &opt->priv->attr_index, &ll_opts);
1783
1784 free(base);
1785 free(name1);
1786 free(name2);
1787 free(orig.ptr);
1788 free(src1.ptr);
1789 free(src2.ptr);
1790 return merge_status;
1791 }
1792
1793 static int handle_content_merge(struct merge_options *opt,
1794 const char *path,
1795 const struct version_info *o,
1796 const struct version_info *a,
1797 const struct version_info *b,
1798 const char *pathnames[3],
1799 const int extra_marker_size,
1800 struct version_info *result)
1801 {
1802 /*
1803 * path is the target location where we want to put the file, and
1804 * is used to determine any normalization rules in ll_merge.
1805 *
1806 * The normal case is that path and all entries in pathnames are
1807 * identical, though renames can affect which path we got one of
1808 * the three blobs to merge on various sides of history.
1809 *
1810 * extra_marker_size is the amount to extend conflict markers in
1811 * ll_merge; this is neeed if we have content merges of content
1812 * merges, which happens for example with rename/rename(2to1) and
1813 * rename/add conflicts.
1814 */
1815 unsigned clean = 1;
1816
1817 /*
1818 * handle_content_merge() needs both files to be of the same type, i.e.
1819 * both files OR both submodules OR both symlinks. Conflicting types
1820 * needs to be handled elsewhere.
1821 */
1822 assert((S_IFMT & a->mode) == (S_IFMT & b->mode));
1823
1824 /* Merge modes */
1825 if (a->mode == b->mode || a->mode == o->mode)
1826 result->mode = b->mode;
1827 else {
1828 /* must be the 100644/100755 case */
1829 assert(S_ISREG(a->mode));
1830 result->mode = a->mode;
1831 clean = (b->mode == o->mode);
1832 /*
1833 * FIXME: If opt->priv->call_depth && !clean, then we really
1834 * should not make result->mode match either a->mode or
1835 * b->mode; that causes t6036 "check conflicting mode for
1836 * regular file" to fail. It would be best to use some other
1837 * mode, but we'll confuse all kinds of stuff if we use one
1838 * where S_ISREG(result->mode) isn't true, and if we use
1839 * something like 0100666, then tree-walk.c's calls to
1840 * canon_mode() will just normalize that to 100644 for us and
1841 * thus not solve anything.
1842 *
1843 * Figure out if there's some kind of way we can work around
1844 * this...
1845 */
1846 }
1847
1848 /*
1849 * Trivial oid merge.
1850 *
1851 * Note: While one might assume that the next four lines would
1852 * be unnecessary due to the fact that match_mask is often
1853 * setup and already handled, renames don't always take care
1854 * of that.
1855 */
1856 if (oideq(&a->oid, &b->oid) || oideq(&a->oid, &o->oid))
1857 oidcpy(&result->oid, &b->oid);
1858 else if (oideq(&b->oid, &o->oid))
1859 oidcpy(&result->oid, &a->oid);
1860
1861 /* Remaining rules depend on file vs. submodule vs. symlink. */
1862 else if (S_ISREG(a->mode)) {
1863 mmbuffer_t result_buf;
1864 int ret = 0, merge_status;
1865 int two_way;
1866
1867 /*
1868 * If 'o' is different type, treat it as null so we do a
1869 * two-way merge.
1870 */
1871 two_way = ((S_IFMT & o->mode) != (S_IFMT & a->mode));
1872
1873 merge_status = merge_3way(opt, path,
1874 two_way ? null_oid() : &o->oid,
1875 &a->oid, &b->oid,
1876 pathnames, extra_marker_size,
1877 &result_buf);
1878
1879 if ((merge_status < 0) || !result_buf.ptr)
1880 ret = err(opt, _("Failed to execute internal merge"));
1881
1882 if (!ret &&
1883 write_object_file(result_buf.ptr, result_buf.size,
1884 blob_type, &result->oid))
1885 ret = err(opt, _("Unable to add %s to database"),
1886 path);
1887
1888 free(result_buf.ptr);
1889 if (ret)
1890 return -1;
1891 clean &= (merge_status == 0);
1892 path_msg(opt, path, 1, _("Auto-merging %s"), path);
1893 } else if (S_ISGITLINK(a->mode)) {
1894 int two_way = ((S_IFMT & o->mode) != (S_IFMT & a->mode));
1895 clean = merge_submodule(opt, pathnames[0],
1896 two_way ? null_oid() : &o->oid,
1897 &a->oid, &b->oid, &result->oid);
1898 if (opt->priv->call_depth && two_way && !clean) {
1899 result->mode = o->mode;
1900 oidcpy(&result->oid, &o->oid);
1901 }
1902 } else if (S_ISLNK(a->mode)) {
1903 if (opt->priv->call_depth) {
1904 clean = 0;
1905 result->mode = o->mode;
1906 oidcpy(&result->oid, &o->oid);
1907 } else {
1908 switch (opt->recursive_variant) {
1909 case MERGE_VARIANT_NORMAL:
1910 clean = 0;
1911 oidcpy(&result->oid, &a->oid);
1912 break;
1913 case MERGE_VARIANT_OURS:
1914 oidcpy(&result->oid, &a->oid);
1915 break;
1916 case MERGE_VARIANT_THEIRS:
1917 oidcpy(&result->oid, &b->oid);
1918 break;
1919 }
1920 }
1921 } else
1922 BUG("unsupported object type in the tree: %06o for %s",
1923 a->mode, path);
1924
1925 return clean;
1926 }
1927
1928 /*** Function Grouping: functions related to detect_and_process_renames(), ***
1929 *** which are split into directory and regular rename detection sections. ***/
1930
1931 /*** Function Grouping: functions related to directory rename detection ***/
1932
1933 struct collision_info {
1934 struct string_list source_files;
1935 unsigned reported_already:1;
1936 };
1937
1938 /*
1939 * Return a new string that replaces the beginning portion (which matches
1940 * rename_info->key), with rename_info->util.new_dir. In perl-speak:
1941 * new_path_name = (old_path =~ s/rename_info->key/rename_info->value/);
1942 * NOTE:
1943 * Caller must ensure that old_path starts with rename_info->key + '/'.
1944 */
1945 static char *apply_dir_rename(struct strmap_entry *rename_info,
1946 const char *old_path)
1947 {
1948 struct strbuf new_path = STRBUF_INIT;
1949 const char *old_dir = rename_info->key;
1950 const char *new_dir = rename_info->value;
1951 int oldlen, newlen, new_dir_len;
1952
1953 oldlen = strlen(old_dir);
1954 if (*new_dir == '\0')
1955 /*
1956 * If someone renamed/merged a subdirectory into the root
1957 * directory (e.g. 'some/subdir' -> ''), then we want to
1958 * avoid returning
1959 * '' + '/filename'
1960 * as the rename; we need to make old_path + oldlen advance
1961 * past the '/' character.
1962 */
1963 oldlen++;
1964 new_dir_len = strlen(new_dir);
1965 newlen = new_dir_len + (strlen(old_path) - oldlen) + 1;
1966 strbuf_grow(&new_path, newlen);
1967 strbuf_add(&new_path, new_dir, new_dir_len);
1968 strbuf_addstr(&new_path, &old_path[oldlen]);
1969
1970 return strbuf_detach(&new_path, NULL);
1971 }
1972
1973 static int path_in_way(struct strmap *paths, const char *path, unsigned side_mask)
1974 {
1975 struct merged_info *mi = strmap_get(paths, path);
1976 struct conflict_info *ci;
1977 if (!mi)
1978 return 0;
1979 INITIALIZE_CI(ci, mi);
1980 return mi->clean || (side_mask & (ci->filemask | ci->dirmask));
1981 }
1982
1983 /*
1984 * See if there is a directory rename for path, and if there are any file
1985 * level conflicts on the given side for the renamed location. If there is
1986 * a rename and there are no conflicts, return the new name. Otherwise,
1987 * return NULL.
1988 */
1989 static char *handle_path_level_conflicts(struct merge_options *opt,
1990 const char *path,
1991 unsigned side_index,
1992 struct strmap_entry *rename_info,
1993 struct strmap *collisions)
1994 {
1995 char *new_path = NULL;
1996 struct collision_info *c_info;
1997 int clean = 1;
1998 struct strbuf collision_paths = STRBUF_INIT;
1999
2000 /*
2001 * entry has the mapping of old directory name to new directory name
2002 * that we want to apply to path.
2003 */
2004 new_path = apply_dir_rename(rename_info, path);
2005 if (!new_path)
2006 BUG("Failed to apply directory rename!");
2007
2008 /*
2009 * The caller needs to have ensured that it has pre-populated
2010 * collisions with all paths that map to new_path. Do a quick check
2011 * to ensure that's the case.
2012 */
2013 c_info = strmap_get(collisions, new_path);
2014 if (c_info == NULL)
2015 BUG("c_info is NULL");
2016
2017 /*
2018 * Check for one-sided add/add/.../add conflicts, i.e.
2019 * where implicit renames from the other side doing
2020 * directory rename(s) can affect this side of history
2021 * to put multiple paths into the same location. Warn
2022 * and bail on directory renames for such paths.
2023 */
2024 if (c_info->reported_already) {
2025 clean = 0;
2026 } else if (path_in_way(&opt->priv->paths, new_path, 1 << side_index)) {
2027 c_info->reported_already = 1;
2028 strbuf_add_separated_string_list(&collision_paths, ", ",
2029 &c_info->source_files);
2030 path_msg(opt, new_path, 0,
2031 _("CONFLICT (implicit dir rename): Existing file/dir "
2032 "at %s in the way of implicit directory rename(s) "
2033 "putting the following path(s) there: %s."),
2034 new_path, collision_paths.buf);
2035 clean = 0;
2036 } else if (c_info->source_files.nr > 1) {
2037 c_info->reported_already = 1;
2038 strbuf_add_separated_string_list(&collision_paths, ", ",
2039 &c_info->source_files);
2040 path_msg(opt, new_path, 0,
2041 _("CONFLICT (implicit dir rename): Cannot map more "
2042 "than one path to %s; implicit directory renames "
2043 "tried to put these paths there: %s"),
2044 new_path, collision_paths.buf);
2045 clean = 0;
2046 }
2047
2048 /* Free memory we no longer need */
2049 strbuf_release(&collision_paths);
2050 if (!clean && new_path) {
2051 free(new_path);
2052 return NULL;
2053 }
2054
2055 return new_path;
2056 }
2057
2058 static void get_provisional_directory_renames(struct merge_options *opt,
2059 unsigned side,
2060 int *clean)
2061 {
2062 struct hashmap_iter iter;
2063 struct strmap_entry *entry;
2064 struct rename_info *renames = &opt->priv->renames;
2065
2066 /*
2067 * Collapse
2068 * dir_rename_count: old_directory -> {new_directory -> count}
2069 * down to
2070 * dir_renames: old_directory -> best_new_directory
2071 * where best_new_directory is the one with the unique highest count.
2072 */
2073 strmap_for_each_entry(&renames->dir_rename_count[side], &iter, entry) {
2074 const char *source_dir = entry->key;
2075 struct strintmap *counts = entry->value;
2076 struct hashmap_iter count_iter;
2077 struct strmap_entry *count_entry;
2078 int max = 0;
2079 int bad_max = 0;
2080 const char *best = NULL;
2081
2082 strintmap_for_each_entry(counts, &count_iter, count_entry) {
2083 const char *target_dir = count_entry->key;
2084 intptr_t count = (intptr_t)count_entry->value;
2085
2086 if (count == max)
2087 bad_max = max;
2088 else if (count > max) {
2089 max = count;
2090 best = target_dir;
2091 }
2092 }
2093
2094 if (max == 0)
2095 continue;
2096
2097 if (bad_max == max) {
2098 path_msg(opt, source_dir, 0,
2099 _("CONFLICT (directory rename split): "
2100 "Unclear where to rename %s to; it was "
2101 "renamed to multiple other directories, with "
2102 "no destination getting a majority of the "
2103 "files."),
2104 source_dir);
2105 *clean = 0;
2106 } else {
2107 strmap_put(&renames->dir_renames[side],
2108 source_dir, (void*)best);
2109 }
2110 }
2111 }
2112
2113 static void handle_directory_level_conflicts(struct merge_options *opt)
2114 {
2115 struct hashmap_iter iter;
2116 struct strmap_entry *entry;
2117 struct string_list duplicated = STRING_LIST_INIT_NODUP;
2118 struct rename_info *renames = &opt->priv->renames;
2119 struct strmap *side1_dir_renames = &renames->dir_renames[MERGE_SIDE1];
2120 struct strmap *side2_dir_renames = &renames->dir_renames[MERGE_SIDE2];
2121 int i;
2122
2123 strmap_for_each_entry(side1_dir_renames, &iter, entry) {
2124 if (strmap_contains(side2_dir_renames, entry->key))
2125 string_list_append(&duplicated, entry->key);
2126 }
2127
2128 for (i = 0; i < duplicated.nr; i++) {
2129 strmap_remove(side1_dir_renames, duplicated.items[i].string, 0);
2130 strmap_remove(side2_dir_renames, duplicated.items[i].string, 0);
2131 }
2132 string_list_clear(&duplicated, 0);
2133 }
2134
2135 static struct strmap_entry *check_dir_renamed(const char *path,
2136 struct strmap *dir_renames)
2137 {
2138 char *temp = xstrdup(path);
2139 char *end;
2140 struct strmap_entry *e = NULL;
2141
2142 while ((end = strrchr(temp, '/'))) {
2143 *end = '\0';
2144 e = strmap_get_entry(dir_renames, temp);
2145 if (e)
2146 break;
2147 }
2148 free(temp);
2149 return e;
2150 }
2151
2152 static void compute_collisions(struct strmap *collisions,
2153 struct strmap *dir_renames,
2154 struct diff_queue_struct *pairs)
2155 {
2156 int i;
2157
2158 strmap_init_with_options(collisions, NULL, 0);
2159 if (strmap_empty(dir_renames))
2160 return;
2161
2162 /*
2163 * Multiple files can be mapped to the same path due to directory
2164 * renames done by the other side of history. Since that other
2165 * side of history could have merged multiple directories into one,
2166 * if our side of history added the same file basename to each of
2167 * those directories, then all N of them would get implicitly
2168 * renamed by the directory rename detection into the same path,
2169 * and we'd get an add/add/.../add conflict, and all those adds
2170 * from *this* side of history. This is not representable in the
2171 * index, and users aren't going to easily be able to make sense of
2172 * it. So we need to provide a good warning about what's
2173 * happening, and fall back to no-directory-rename detection
2174 * behavior for those paths.
2175 *
2176 * See testcases 9e and all of section 5 from t6043 for examples.
2177 */
2178 for (i = 0; i < pairs->nr; ++i) {
2179 struct strmap_entry *rename_info;
2180 struct collision_info *collision_info;
2181 char *new_path;
2182 struct diff_filepair *pair = pairs->queue[i];
2183
2184 if (pair->status != 'A' && pair->status != 'R')
2185 continue;
2186 rename_info = check_dir_renamed(pair->two->path, dir_renames);
2187 if (!rename_info)
2188 continue;
2189
2190 new_path = apply_dir_rename(rename_info, pair->two->path);
2191 assert(new_path);
2192 collision_info = strmap_get(collisions, new_path);
2193 if (collision_info) {
2194 free(new_path);
2195 } else {
2196 CALLOC_ARRAY(collision_info, 1);
2197 string_list_init_nodup(&collision_info->source_files);
2198 strmap_put(collisions, new_path, collision_info);
2199 }
2200 string_list_insert(&collision_info->source_files,
2201 pair->two->path);
2202 }
2203 }
2204
2205 static char *check_for_directory_rename(struct merge_options *opt,
2206 const char *path,
2207 unsigned side_index,
2208 struct strmap *dir_renames,
2209 struct strmap *dir_rename_exclusions,
2210 struct strmap *collisions,
2211 int *clean_merge)
2212 {
2213 char *new_path = NULL;
2214 struct strmap_entry *rename_info;
2215 struct strmap_entry *otherinfo = NULL;
2216 const char *new_dir;
2217
2218 if (strmap_empty(dir_renames))
2219 return new_path;
2220 rename_info = check_dir_renamed(path, dir_renames);
2221 if (!rename_info)
2222 return new_path;
2223 /* old_dir = rename_info->key; */
2224 new_dir = rename_info->value;
2225
2226 /*
2227 * This next part is a little weird. We do not want to do an
2228 * implicit rename into a directory we renamed on our side, because
2229 * that will result in a spurious rename/rename(1to2) conflict. An
2230 * example:
2231 * Base commit: dumbdir/afile, otherdir/bfile
2232 * Side 1: smrtdir/afile, otherdir/bfile
2233 * Side 2: dumbdir/afile, dumbdir/bfile
2234 * Here, while working on Side 1, we could notice that otherdir was
2235 * renamed/merged to dumbdir, and change the diff_filepair for
2236 * otherdir/bfile into a rename into dumbdir/bfile. However, Side
2237 * 2 will notice the rename from dumbdir to smrtdir, and do the
2238 * transitive rename to move it from dumbdir/bfile to
2239 * smrtdir/bfile. That gives us bfile in dumbdir vs being in
2240 * smrtdir, a rename/rename(1to2) conflict. We really just want
2241 * the file to end up in smrtdir. And the way to achieve that is
2242 * to not let Side1 do the rename to dumbdir, since we know that is
2243 * the source of one of our directory renames.
2244 *
2245 * That's why otherinfo and dir_rename_exclusions is here.
2246 *
2247 * As it turns out, this also prevents N-way transient rename
2248 * confusion; See testcases 9c and 9d of t6043.
2249 */
2250 otherinfo = strmap_get_entry(dir_rename_exclusions, new_dir);
2251 if (otherinfo) {
2252 path_msg(opt, rename_info->key, 1,
2253 _("WARNING: Avoiding applying %s -> %s rename "
2254 "to %s, because %s itself was renamed."),
2255 rename_info->key, new_dir, path, new_dir);
2256 return NULL;
2257 }
2258
2259 new_path = handle_path_level_conflicts(opt, path, side_index,
2260 rename_info, collisions);
2261 *clean_merge &= (new_path != NULL);
2262
2263 return new_path;
2264 }
2265
2266 static void apply_directory_rename_modifications(struct merge_options *opt,
2267 struct diff_filepair *pair,
2268 char *new_path)
2269 {
2270 /*
2271 * The basic idea is to get the conflict_info from opt->priv->paths
2272 * at old path, and insert it into new_path; basically just this:
2273 * ci = strmap_get(&opt->priv->paths, old_path);
2274 * strmap_remove(&opt->priv->paths, old_path, 0);
2275 * strmap_put(&opt->priv->paths, new_path, ci);
2276 * However, there are some factors complicating this:
2277 * - opt->priv->paths may already have an entry at new_path
2278 * - Each ci tracks its containing directory, so we need to
2279 * update that
2280 * - If another ci has the same containing directory, then
2281 * the two char*'s MUST point to the same location. See the
2282 * comment in struct merged_info. strcmp equality is not
2283 * enough; we need pointer equality.
2284 * - opt->priv->paths must hold the parent directories of any
2285 * entries that are added. So, if this directory rename
2286 * causes entirely new directories, we must recursively add
2287 * parent directories.
2288 * - For each parent directory added to opt->priv->paths, we
2289 * also need to get its parent directory stored in its
2290 * conflict_info->merged.directory_name with all the same
2291 * requirements about pointer equality.
2292 */
2293 struct string_list dirs_to_insert = STRING_LIST_INIT_NODUP;
2294 struct conflict_info *ci, *new_ci;
2295 struct strmap_entry *entry;
2296 const char *branch_with_new_path, *branch_with_dir_rename;
2297 const char *old_path = pair->two->path;
2298 const char *parent_name;
2299 const char *cur_path;
2300 int i, len;
2301
2302 entry = strmap_get_entry(&opt->priv->paths, old_path);
2303 old_path = entry->key;
2304 ci = entry->value;
2305 VERIFY_CI(ci);
2306
2307 /* Find parent directories missing from opt->priv->paths */
2308 cur_path = mem_pool_strdup(&opt->priv->pool, new_path);
2309 free((char*)new_path);
2310 new_path = (char *)cur_path;
2311
2312 while (1) {
2313 /* Find the parent directory of cur_path */
2314 char *last_slash = strrchr(cur_path, '/');
2315 if (last_slash) {
2316 parent_name = mem_pool_strndup(&opt->priv->pool,
2317 cur_path,
2318 last_slash - cur_path);
2319 } else {
2320 parent_name = opt->priv->toplevel_dir;
2321 break;
2322 }
2323
2324 /* Look it up in opt->priv->paths */
2325 entry = strmap_get_entry(&opt->priv->paths, parent_name);
2326 if (entry) {
2327 parent_name = entry->key; /* reuse known pointer */
2328 break;
2329 }
2330
2331 /* Record this is one of the directories we need to insert */
2332 string_list_append(&dirs_to_insert, parent_name);
2333 cur_path = parent_name;
2334 }
2335
2336 /* Traverse dirs_to_insert and insert them into opt->priv->paths */
2337 for (i = dirs_to_insert.nr-1; i >= 0; --i) {
2338 struct conflict_info *dir_ci;
2339 char *cur_dir = dirs_to_insert.items[i].string;
2340
2341 CALLOC_ARRAY(dir_ci, 1);
2342
2343 dir_ci->merged.directory_name = parent_name;
2344 len = strlen(parent_name);
2345 /* len+1 because of trailing '/' character */
2346 dir_ci->merged.basename_offset = (len > 0 ? len+1 : len);
2347 dir_ci->dirmask = ci->filemask;
2348 strmap_put(&opt->priv->paths, cur_dir, dir_ci);
2349
2350 parent_name = cur_dir;
2351 }
2352
2353 assert(ci->filemask == 2 || ci->filemask == 4);
2354 assert(ci->dirmask == 0);
2355 strmap_remove(&opt->priv->paths, old_path, 0);
2356
2357 branch_with_new_path = (ci->filemask == 2) ? opt->branch1 : opt->branch2;
2358 branch_with_dir_rename = (ci->filemask == 2) ? opt->branch2 : opt->branch1;
2359
2360 /* Now, finally update ci and stick it into opt->priv->paths */
2361 ci->merged.directory_name = parent_name;
2362 len = strlen(parent_name);
2363 ci->merged.basename_offset = (len > 0 ? len+1 : len);
2364 new_ci = strmap_get(&opt->priv->paths, new_path);
2365 if (!new_ci) {
2366 /* Place ci back into opt->priv->paths, but at new_path */
2367 strmap_put(&opt->priv->paths, new_path, ci);
2368 } else {
2369 int index;
2370
2371 /* A few sanity checks */
2372 VERIFY_CI(new_ci);
2373 assert(ci->filemask == 2 || ci->filemask == 4);
2374 assert((new_ci->filemask & ci->filemask) == 0);
2375 assert(!new_ci->merged.clean);
2376
2377 /* Copy stuff from ci into new_ci */
2378 new_ci->filemask |= ci->filemask;
2379 if (new_ci->dirmask)
2380 new_ci->df_conflict = 1;
2381 index = (ci->filemask >> 1);
2382 new_ci->pathnames[index] = ci->pathnames[index];
2383 new_ci->stages[index].mode = ci->stages[index].mode;
2384 oidcpy(&new_ci->stages[index].oid, &ci->stages[index].oid);
2385
2386 ci = new_ci;
2387 }
2388
2389 if (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE) {
2390 /* Notify user of updated path */
2391 if (pair->status == 'A')
2392 path_msg(opt, new_path, 1,
2393 _("Path updated: %s added in %s inside a "
2394 "directory that was renamed in %s; moving "
2395 "it to %s."),
2396 old_path, branch_with_new_path,
2397 branch_with_dir_rename, new_path);
2398 else
2399 path_msg(opt, new_path, 1,
2400 _("Path updated: %s renamed to %s in %s, "
2401 "inside a directory that was renamed in %s; "
2402 "moving it to %s."),
2403 pair->one->path, old_path, branch_with_new_path,
2404 branch_with_dir_rename, new_path);
2405 } else {
2406 /*
2407 * opt->detect_directory_renames has the value
2408 * MERGE_DIRECTORY_RENAMES_CONFLICT, so mark these as conflicts.
2409 */
2410 ci->path_conflict = 1;
2411 if (pair->status == 'A')
2412 path_msg(opt, new_path, 0,
2413 _("CONFLICT (file location): %s added in %s "
2414 "inside a directory that was renamed in %s, "
2415 "suggesting it should perhaps be moved to "
2416 "%s."),
2417 old_path, branch_with_new_path,
2418 branch_with_dir_rename, new_path);
2419 else
2420 path_msg(opt, new_path, 0,
2421 _("CONFLICT (file location): %s renamed to %s "
2422 "in %s, inside a directory that was renamed "
2423 "in %s, suggesting it should perhaps be "
2424 "moved to %s."),
2425 pair->one->path, old_path, branch_with_new_path,
2426 branch_with_dir_rename, new_path);
2427 }
2428
2429 /*
2430 * Finally, record the new location.
2431 */
2432 pair->two->path = new_path;
2433 }
2434
2435 /*** Function Grouping: functions related to regular rename detection ***/
2436
2437 static int process_renames(struct merge_options *opt,
2438 struct diff_queue_struct *renames)
2439 {
2440 int clean_merge = 1, i;
2441
2442 for (i = 0; i < renames->nr; ++i) {
2443 const char *oldpath = NULL, *newpath;
2444 struct diff_filepair *pair = renames->queue[i];
2445 struct conflict_info *oldinfo = NULL, *newinfo = NULL;
2446 struct strmap_entry *old_ent, *new_ent;
2447 unsigned int old_sidemask;
2448 int target_index, other_source_index;
2449 int source_deleted, collision, type_changed;
2450 const char *rename_branch = NULL, *delete_branch = NULL;
2451
2452 old_ent = strmap_get_entry(&opt->priv->paths, pair->one->path);
2453 new_ent = strmap_get_entry(&opt->priv->paths, pair->two->path);
2454 if (old_ent) {
2455 oldpath = old_ent->key;
2456 oldinfo = old_ent->value;
2457 }
2458 newpath = pair->two->path;
2459 if (new_ent) {
2460 newpath = new_ent->key;
2461 newinfo = new_ent->value;
2462 }
2463
2464 /*
2465 * If pair->one->path isn't in opt->priv->paths, that means
2466 * that either directory rename detection removed that
2467 * path, or a parent directory of oldpath was resolved and
2468 * we don't even need the rename; in either case, we can
2469 * skip it. If oldinfo->merged.clean, then the other side
2470 * of history had no changes to oldpath and we don't need
2471 * the rename and can skip it.
2472 */
2473 if (!oldinfo || oldinfo->merged.clean)
2474 continue;
2475
2476 /*
2477 * diff_filepairs have copies of pathnames, thus we have to
2478 * use standard 'strcmp()' (negated) instead of '=='.
2479 */
2480 if (i + 1 < renames->nr &&
2481 !strcmp(oldpath, renames->queue[i+1]->one->path)) {
2482 /* Handle rename/rename(1to2) or rename/rename(1to1) */
2483 const char *pathnames[3];
2484 struct version_info merged;
2485 struct conflict_info *base, *side1, *side2;
2486 unsigned was_binary_blob = 0;
2487
2488 pathnames[0] = oldpath;
2489 pathnames[1] = newpath;
2490 pathnames[2] = renames->queue[i+1]->two->path;
2491
2492 base = strmap_get(&opt->priv->paths, pathnames[0]);
2493 side1 = strmap_get(&opt->priv->paths, pathnames[1]);
2494 side2 = strmap_get(&opt->priv->paths, pathnames[2]);
2495
2496 VERIFY_CI(base);
2497 VERIFY_CI(side1);
2498 VERIFY_CI(side2);
2499
2500 if (!strcmp(pathnames[1], pathnames[2])) {
2501 struct rename_info *ri = &opt->priv->renames;
2502 int j;
2503
2504 /* Both sides renamed the same way */
2505 assert(side1 == side2);
2506 memcpy(&side1->stages[0], &base->stages[0],
2507 sizeof(merged));
2508 side1->filemask |= (1 << MERGE_BASE);
2509 /* Mark base as resolved by removal */
2510 base->merged.is_null = 1;
2511 base->merged.clean = 1;
2512
2513 /*
2514 * Disable remembering renames optimization;
2515 * rename/rename(1to1) is incredibly rare, and
2516 * just disabling the optimization is easier
2517 * than purging cached_pairs,
2518 * cached_target_names, and dir_rename_counts.
2519 */
2520 for (j = 0; j < 3; j++)
2521 ri->merge_trees[j] = NULL;
2522
2523 /* We handled both renames, i.e. i+1 handled */
2524 i++;
2525 /* Move to next rename */
2526 continue;
2527 }
2528
2529 /* This is a rename/rename(1to2) */
2530 clean_merge = handle_content_merge(opt,
2531 pair->one->path,
2532 &base->stages[0],
2533 &side1->stages[1],
2534 &side2->stages[2],
2535 pathnames,
2536 1 + 2 * opt->priv->call_depth,
2537 &merged);
2538 if (!clean_merge &&
2539 merged.mode == side1->stages[1].mode &&
2540 oideq(&merged.oid, &side1->stages[1].oid))
2541 was_binary_blob = 1;
2542 memcpy(&side1->stages[1], &merged, sizeof(merged));
2543 if (was_binary_blob) {
2544 /*
2545 * Getting here means we were attempting to
2546 * merge a binary blob.
2547 *
2548 * Since we can't merge binaries,
2549 * handle_content_merge() just takes one
2550 * side. But we don't want to copy the
2551 * contents of one side to both paths. We
2552 * used the contents of side1 above for
2553 * side1->stages, let's use the contents of
2554 * side2 for side2->stages below.
2555 */
2556 oidcpy(&merged.oid, &side2->stages[2].oid);
2557 merged.mode = side2->stages[2].mode;
2558 }
2559 memcpy(&side2->stages[2], &merged, sizeof(merged));
2560
2561 side1->path_conflict = 1;
2562 side2->path_conflict = 1;
2563 /*
2564 * TODO: For renames we normally remove the path at the
2565 * old name. It would thus seem consistent to do the
2566 * same for rename/rename(1to2) cases, but we haven't
2567 * done so traditionally and a number of the regression
2568 * tests now encode an expectation that the file is
2569 * left there at stage 1. If we ever decide to change
2570 * this, add the following two lines here:
2571 * base->merged.is_null = 1;
2572 * base->merged.clean = 1;
2573 * and remove the setting of base->path_conflict to 1.
2574 */
2575 base->path_conflict = 1;
2576 path_msg(opt, oldpath, 0,
2577 _("CONFLICT (rename/rename): %s renamed to "
2578 "%s in %s and to %s in %s."),
2579 pathnames[0],
2580 pathnames[1], opt->branch1,
2581 pathnames[2], opt->branch2);
2582
2583 i++; /* We handled both renames, i.e. i+1 handled */
2584 continue;
2585 }
2586
2587 VERIFY_CI(oldinfo);
2588 VERIFY_CI(newinfo);
2589 target_index = pair->score; /* from collect_renames() */
2590 assert(target_index == 1 || target_index == 2);
2591 other_source_index = 3 - target_index;
2592 old_sidemask = (1 << other_source_index); /* 2 or 4 */
2593 source_deleted = (oldinfo->filemask == 1);
2594 collision = ((newinfo->filemask & old_sidemask) != 0);
2595 type_changed = !source_deleted &&
2596 (S_ISREG(oldinfo->stages[other_source_index].mode) !=
2597 S_ISREG(newinfo->stages[target_index].mode));
2598 if (type_changed && collision) {
2599 /*
2600 * special handling so later blocks can handle this...
2601 *
2602 * if type_changed && collision are both true, then this
2603 * was really a double rename, but one side wasn't
2604 * detected due to lack of break detection. I.e.
2605 * something like
2606 * orig: has normal file 'foo'
2607 * side1: renames 'foo' to 'bar', adds 'foo' symlink
2608 * side2: renames 'foo' to 'bar'
2609 * In this case, the foo->bar rename on side1 won't be
2610 * detected because the new symlink named 'foo' is
2611 * there and we don't do break detection. But we detect
2612 * this here because we don't want to merge the content
2613 * of the foo symlink with the foo->bar file, so we
2614 * have some logic to handle this special case. The
2615 * easiest way to do that is make 'bar' on side1 not
2616 * be considered a colliding file but the other part
2617 * of a normal rename. If the file is very different,
2618 * well we're going to get content merge conflicts
2619 * anyway so it doesn't hurt. And if the colliding
2620 * file also has a different type, that'll be handled
2621 * by the content merge logic in process_entry() too.
2622 *
2623 * See also t6430, 'rename vs. rename/symlink'
2624 */
2625 collision = 0;
2626 }
2627 if (source_deleted) {
2628 if (target_index == 1) {
2629 rename_branch = opt->branch1;
2630 delete_branch = opt->branch2;
2631 } else {
2632 rename_branch = opt->branch2;
2633 delete_branch = opt->branch1;
2634 }
2635 }
2636
2637 assert(source_deleted || oldinfo->filemask & old_sidemask);
2638
2639 /* Need to check for special types of rename conflicts... */
2640 if (collision && !source_deleted) {
2641 /* collision: rename/add or rename/rename(2to1) */
2642 const char *pathnames[3];
2643 struct version_info merged;
2644
2645 struct conflict_info *base, *side1, *side2;
2646 unsigned clean;
2647
2648 pathnames[0] = oldpath;
2649 pathnames[other_source_index] = oldpath;
2650 pathnames[target_index] = newpath;
2651
2652 base = strmap_get(&opt->priv->paths, pathnames[0]);
2653 side1 = strmap_get(&opt->priv->paths, pathnames[1]);
2654 side2 = strmap_get(&opt->priv->paths, pathnames[2]);
2655
2656 VERIFY_CI(base);
2657 VERIFY_CI(side1);
2658 VERIFY_CI(side2);
2659
2660 clean = handle_content_merge(opt, pair->one->path,
2661 &base->stages[0],
2662 &side1->stages[1],
2663 &side2->stages[2],
2664 pathnames,
2665 1 + 2 * opt->priv->call_depth,
2666 &merged);
2667
2668 memcpy(&newinfo->stages[target_index], &merged,
2669 sizeof(merged));
2670 if (!clean) {
2671 path_msg(opt, newpath, 0,
2672 _("CONFLICT (rename involved in "
2673 "collision): rename of %s -> %s has "
2674 "content conflicts AND collides "
2675 "with another path; this may result "
2676 "in nested conflict markers."),
2677 oldpath, newpath);
2678 }
2679 } else if (collision && source_deleted) {
2680 /*
2681 * rename/add/delete or rename/rename(2to1)/delete:
2682 * since oldpath was deleted on the side that didn't
2683 * do the rename, there's not much of a content merge
2684 * we can do for the rename. oldinfo->merged.is_null
2685 * was already set, so we just leave things as-is so
2686 * they look like an add/add conflict.
2687 */
2688
2689 newinfo->path_conflict = 1;
2690 path_msg(opt, newpath, 0,
2691 _("CONFLICT (rename/delete): %s renamed "
2692 "to %s in %s, but deleted in %s."),
2693 oldpath, newpath, rename_branch, delete_branch);
2694 } else {
2695 /*
2696 * a few different cases...start by copying the
2697 * existing stage(s) from oldinfo over the newinfo
2698 * and update the pathname(s).
2699 */
2700 memcpy(&newinfo->stages[0], &oldinfo->stages[0],
2701 sizeof(newinfo->stages[0]));
2702 newinfo->filemask |= (1 << MERGE_BASE);
2703 newinfo->pathnames[0] = oldpath;
2704 if (type_changed) {
2705 /* rename vs. typechange */
2706 /* Mark the original as resolved by removal */
2707 memcpy(&oldinfo->stages[0].oid, null_oid(),
2708 sizeof(oldinfo->stages[0].oid));
2709 oldinfo->stages[0].mode = 0;
2710 oldinfo->filemask &= 0x06;
2711 } else if (source_deleted) {
2712 /* rename/delete */
2713 newinfo->path_conflict = 1;
2714 path_msg(opt, newpath, 0,
2715 _("CONFLICT (rename/delete): %s renamed"
2716 " to %s in %s, but deleted in %s."),
2717 oldpath, newpath,
2718 rename_branch, delete_branch);
2719 } else {
2720 /* normal rename */
2721 memcpy(&newinfo->stages[other_source_index],
2722 &oldinfo->stages[other_source_index],
2723 sizeof(newinfo->stages[0]));
2724 newinfo->filemask |= (1 << other_source_index);
2725 newinfo->pathnames[other_source_index] = oldpath;
2726 }
2727 }
2728
2729 if (!type_changed) {
2730 /* Mark the original as resolved by removal */
2731 oldinfo->merged.is_null = 1;
2732 oldinfo->merged.clean = 1;
2733 }
2734
2735 }
2736
2737 return clean_merge;
2738 }
2739
2740 static inline int possible_side_renames(struct rename_info *renames,
2741 unsigned side_index)
2742 {
2743 return renames->pairs[side_index].nr > 0 &&
2744 !strintmap_empty(&renames->relevant_sources[side_index]);
2745 }
2746
2747 static inline int possible_renames(struct rename_info *renames)
2748 {
2749 return possible_side_renames(renames, 1) ||
2750 possible_side_renames(renames, 2) ||
2751 !strmap_empty(&renames->cached_pairs[1]) ||
2752 !strmap_empty(&renames->cached_pairs[2]);
2753 }
2754
2755 static void resolve_diffpair_statuses(struct diff_queue_struct *q)
2756 {
2757 /*
2758 * A simplified version of diff_resolve_rename_copy(); would probably
2759 * just use that function but it's static...
2760 */
2761 int i;
2762 struct diff_filepair *p;
2763
2764 for (i = 0; i < q->nr; ++i) {
2765 p = q->queue[i];
2766 p->status = 0; /* undecided */
2767 if (!DIFF_FILE_VALID(p->one))
2768 p->status = DIFF_STATUS_ADDED;
2769 else if (!DIFF_FILE_VALID(p->two))
2770 p->status = DIFF_STATUS_DELETED;
2771 else if (DIFF_PAIR_RENAME(p))
2772 p->status = DIFF_STATUS_RENAMED;
2773 }
2774 }
2775
2776 static void prune_cached_from_relevant(struct rename_info *renames,
2777 unsigned side)
2778 {
2779 /* Reason for this function described in add_pair() */
2780 struct hashmap_iter iter;
2781 struct strmap_entry *entry;
2782
2783 /* Remove from relevant_sources all entries in cached_pairs[side] */
2784 strmap_for_each_entry(&renames->cached_pairs[side], &iter, entry) {
2785 strintmap_remove(&renames->relevant_sources[side],
2786 entry->key);
2787 }
2788 /* Remove from relevant_sources all entries in cached_irrelevant[side] */
2789 strset_for_each_entry(&renames->cached_irrelevant[side], &iter, entry) {
2790 strintmap_remove(&renames->relevant_sources[side],
2791 entry->key);
2792 }
2793 }
2794
2795 static void use_cached_pairs(struct merge_options *opt,
2796 struct strmap *cached_pairs,
2797 struct diff_queue_struct *pairs)
2798 {
2799 struct hashmap_iter iter;
2800 struct strmap_entry *entry;
2801
2802 /*
2803 * Add to side_pairs all entries from renames->cached_pairs[side_index].
2804 * (Info in cached_irrelevant[side_index] is not relevant here.)
2805 */
2806 strmap_for_each_entry(cached_pairs, &iter, entry) {
2807 struct diff_filespec *one, *two;
2808 const char *old_name = entry->key;
2809 const char *new_name = entry->value;
2810 if (!new_name)
2811 new_name = old_name;
2812
2813 /*
2814 * cached_pairs has *copies* of old_name and new_name,
2815 * because it has to persist across merges. Since
2816 * pool_alloc_filespec() will just re-use the existing
2817 * filenames, which will also get re-used by
2818 * opt->priv->paths if they become renames, and then
2819 * get freed at the end of the merge, that would leave
2820 * the copy in cached_pairs dangling. Avoid this by
2821 * making a copy here.
2822 */
2823 old_name = mem_pool_strdup(&opt->priv->pool, old_name);
2824 new_name = mem_pool_strdup(&opt->priv->pool, new_name);
2825
2826 /* We don't care about oid/mode, only filenames and status */
2827 one = pool_alloc_filespec(&opt->priv->pool, old_name);
2828 two = pool_alloc_filespec(&opt->priv->pool, new_name);
2829 pool_diff_queue(&opt->priv->pool, pairs, one, two);
2830 pairs->queue[pairs->nr-1]->status = entry->value ? 'R' : 'D';
2831 }
2832 }
2833
2834 static void cache_new_pair(struct rename_info *renames,
2835 int side,
2836 char *old_path,
2837 char *new_path,
2838 int free_old_value)
2839 {
2840 char *old_value;
2841 new_path = xstrdup(new_path);
2842 old_value = strmap_put(&renames->cached_pairs[side],
2843 old_path, new_path);
2844 strset_add(&renames->cached_target_names[side], new_path);
2845 if (free_old_value)
2846 free(old_value);
2847 else
2848 assert(!old_value);
2849 }
2850
2851 static void possibly_cache_new_pair(struct rename_info *renames,
2852 struct diff_filepair *p,
2853 unsigned side,
2854 char *new_path)
2855 {
2856 int dir_renamed_side = 0;
2857
2858 if (new_path) {
2859 /*
2860 * Directory renames happen on the other side of history from
2861 * the side that adds new files to the old directory.
2862 */
2863 dir_renamed_side = 3 - side;
2864 } else {
2865 int val = strintmap_get(&renames->relevant_sources[side],
2866 p->one->path);
2867 if (val == RELEVANT_NO_MORE) {
2868 assert(p->status == 'D');
2869 strset_add(&renames->cached_irrelevant[side],
2870 p->one->path);
2871 }
2872 if (val <= 0)
2873 return;
2874 }
2875
2876 if (p->status == 'D') {
2877 /*
2878 * If we already had this delete, we'll just set it's value
2879 * to NULL again, so no harm.
2880 */
2881 strmap_put(&renames->cached_pairs[side], p->one->path, NULL);
2882 } else if (p->status == 'R') {
2883 if (!new_path)
2884 new_path = p->two->path;
2885 else
2886 cache_new_pair(renames, dir_renamed_side,
2887 p->two->path, new_path, 0);
2888 cache_new_pair(renames, side, p->one->path, new_path, 1);
2889 } else if (p->status == 'A' && new_path) {
2890 cache_new_pair(renames, dir_renamed_side,
2891 p->two->path, new_path, 0);
2892 }
2893 }
2894
2895 static int compare_pairs(const void *a_, const void *b_)
2896 {
2897 const struct diff_filepair *a = *((const struct diff_filepair **)a_);
2898 const struct diff_filepair *b = *((const struct diff_filepair **)b_);
2899
2900 return strcmp(a->one->path, b->one->path);
2901 }
2902
2903 /* Call diffcore_rename() to update deleted/added pairs into rename pairs */
2904 static int detect_regular_renames(struct merge_options *opt,
2905 unsigned side_index)
2906 {
2907 struct diff_options diff_opts;
2908 struct rename_info *renames = &opt->priv->renames;
2909
2910 prune_cached_from_relevant(renames, side_index);
2911 if (!possible_side_renames(renames, side_index)) {
2912 /*
2913 * No rename detection needed for this side, but we still need
2914 * to make sure 'adds' are marked correctly in case the other
2915 * side had directory renames.
2916 */
2917 resolve_diffpair_statuses(&renames->pairs[side_index]);
2918 return 0;
2919 }
2920
2921 partial_clear_dir_rename_count(&renames->dir_rename_count[side_index]);
2922 repo_diff_setup(opt->repo, &diff_opts);
2923 diff_opts.flags.recursive = 1;
2924 diff_opts.flags.rename_empty = 0;
2925 diff_opts.detect_rename = DIFF_DETECT_RENAME;
2926 diff_opts.rename_limit = opt->rename_limit;
2927 if (opt->rename_limit <= 0)
2928 diff_opts.rename_limit = 7000;
2929 diff_opts.rename_score = opt->rename_score;
2930 diff_opts.show_rename_progress = opt->show_rename_progress;
2931 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
2932 diff_setup_done(&diff_opts);
2933
2934 diff_queued_diff = renames->pairs[side_index];
2935 trace2_region_enter("diff", "diffcore_rename", opt->repo);
2936 diffcore_rename_extended(&diff_opts,
2937 &opt->priv->pool,
2938 &renames->relevant_sources[side_index],
2939 &renames->dirs_removed[side_index],
2940 &renames->dir_rename_count[side_index],
2941 &renames->cached_pairs[side_index]);
2942 trace2_region_leave("diff", "diffcore_rename", opt->repo);
2943 resolve_diffpair_statuses(&diff_queued_diff);
2944
2945 if (diff_opts.needed_rename_limit > 0)
2946 renames->redo_after_renames = 0;
2947 if (diff_opts.needed_rename_limit > renames->needed_limit)
2948 renames->needed_limit = diff_opts.needed_rename_limit;
2949
2950 renames->pairs[side_index] = diff_queued_diff;
2951
2952 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
2953 diff_queued_diff.nr = 0;
2954 diff_queued_diff.queue = NULL;
2955 diff_flush(&diff_opts);
2956
2957 return 1;
2958 }
2959
2960 /*
2961 * Get information of all renames which occurred in 'side_pairs', making use
2962 * of any implicit directory renames in side_dir_renames (also making use of
2963 * implicit directory renames rename_exclusions as needed by
2964 * check_for_directory_rename()). Add all (updated) renames into result.
2965 */
2966 static int collect_renames(struct merge_options *opt,
2967 struct diff_queue_struct *result,
2968 unsigned side_index,
2969 struct strmap *dir_renames_for_side,
2970 struct strmap *rename_exclusions)
2971 {
2972 int i, clean = 1;
2973 struct strmap collisions;
2974 struct diff_queue_struct *side_pairs;
2975 struct hashmap_iter iter;
2976 struct strmap_entry *entry;
2977 struct rename_info *renames = &opt->priv->renames;
2978
2979 side_pairs = &renames->pairs[side_index];
2980 compute_collisions(&collisions, dir_renames_for_side, side_pairs);
2981
2982 for (i = 0; i < side_pairs->nr; ++i) {
2983 struct diff_filepair *p = side_pairs->queue[i];
2984 char *new_path; /* non-NULL only with directory renames */
2985
2986 if (p->status != 'A' && p->status != 'R') {
2987 possibly_cache_new_pair(renames, p, side_index, NULL);
2988 pool_diff_free_filepair(&opt->priv->pool, p);
2989 continue;
2990 }
2991
2992 new_path = check_for_directory_rename(opt, p->two->path,
2993 side_index,
2994 dir_renames_for_side,
2995 rename_exclusions,
2996 &collisions,
2997 &clean);
2998
2999 possibly_cache_new_pair(renames, p, side_index, new_path);
3000 if (p->status != 'R' && !new_path) {
3001 pool_diff_free_filepair(&opt->priv->pool, p);
3002 continue;
3003 }
3004
3005 if (new_path)
3006 apply_directory_rename_modifications(opt, p, new_path);
3007
3008 /*
3009 * p->score comes back from diffcore_rename_extended() with
3010 * the similarity of the renamed file. The similarity is
3011 * was used to determine that the two files were related
3012 * and are a rename, which we have already used, but beyond
3013 * that we have no use for the similarity. So p->score is
3014 * now irrelevant. However, process_renames() will need to
3015 * know which side of the merge this rename was associated
3016 * with, so overwrite p->score with that value.
3017 */
3018 p->score = side_index;
3019 result->queue[result->nr++] = p;
3020 }
3021
3022 /* Free each value in the collisions map */
3023 strmap_for_each_entry(&collisions, &iter, entry) {
3024 struct collision_info *info = entry->value;
3025 string_list_clear(&info->source_files, 0);
3026 }
3027 /*
3028 * In compute_collisions(), we set collisions.strdup_strings to 0
3029 * so that we wouldn't have to make another copy of the new_path
3030 * allocated by apply_dir_rename(). But now that we've used them
3031 * and have no other references to these strings, it is time to
3032 * deallocate them.
3033 */
3034 free_strmap_strings(&collisions);
3035 strmap_clear(&collisions, 1);
3036 return clean;
3037 }
3038
3039 static int detect_and_process_renames(struct merge_options *opt,
3040 struct tree *merge_base,
3041 struct tree *side1,
3042 struct tree *side2)
3043 {
3044 struct diff_queue_struct combined;
3045 struct rename_info *renames = &opt->priv->renames;
3046 int need_dir_renames, s, clean = 1;
3047 unsigned detection_run = 0;
3048
3049 memset(&combined, 0, sizeof(combined));
3050 if (!possible_renames(renames))
3051 goto cleanup;
3052
3053 trace2_region_enter("merge", "regular renames", opt->repo);
3054 detection_run |= detect_regular_renames(opt, MERGE_SIDE1);
3055 detection_run |= detect_regular_renames(opt, MERGE_SIDE2);
3056 if (renames->redo_after_renames && detection_run) {
3057 int i, side;
3058 struct diff_filepair *p;
3059
3060 /* Cache the renames, we found */
3061 for (side = MERGE_SIDE1; side <= MERGE_SIDE2; side++) {
3062 for (i = 0; i < renames->pairs[side].nr; ++i) {
3063 p = renames->pairs[side].queue[i];
3064 possibly_cache_new_pair(renames, p, side, NULL);
3065 }
3066 }
3067
3068 /* Restart the merge with the cached renames */
3069 renames->redo_after_renames = 2;
3070 trace2_region_leave("merge", "regular renames", opt->repo);
3071 goto cleanup;
3072 }
3073 use_cached_pairs(opt, &renames->cached_pairs[1], &renames->pairs[1]);
3074 use_cached_pairs(opt, &renames->cached_pairs[2], &renames->pairs[2]);
3075 trace2_region_leave("merge", "regular renames", opt->repo);
3076
3077 trace2_region_enter("merge", "directory renames", opt->repo);
3078 need_dir_renames =
3079 !opt->priv->call_depth &&
3080 (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE ||
3081 opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_CONFLICT);
3082
3083 if (need_dir_renames) {
3084 get_provisional_directory_renames(opt, MERGE_SIDE1, &clean);
3085 get_provisional_directory_renames(opt, MERGE_SIDE2, &clean);
3086 handle_directory_level_conflicts(opt);
3087 }
3088
3089 ALLOC_GROW(combined.queue,
3090 renames->pairs[1].nr + renames->pairs[2].nr,
3091 combined.alloc);
3092 clean &= collect_renames(opt, &combined, MERGE_SIDE1,
3093 &renames->dir_renames[2],
3094 &renames->dir_renames[1]);
3095 clean &= collect_renames(opt, &combined, MERGE_SIDE2,
3096 &renames->dir_renames[1],
3097 &renames->dir_renames[2]);
3098 STABLE_QSORT(combined.queue, combined.nr, compare_pairs);
3099 trace2_region_leave("merge", "directory renames", opt->repo);
3100
3101 trace2_region_enter("merge", "process renames", opt->repo);
3102 clean &= process_renames(opt, &combined);
3103 trace2_region_leave("merge", "process renames", opt->repo);
3104
3105 goto simple_cleanup; /* collect_renames() handles some of cleanup */
3106
3107 cleanup:
3108 /*
3109 * Free now unneeded filepairs, which would have been handled
3110 * in collect_renames() normally but we skipped that code.
3111 */
3112 for (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {
3113 struct diff_queue_struct *side_pairs;
3114 int i;
3115
3116 side_pairs = &renames->pairs[s];
3117 for (i = 0; i < side_pairs->nr; ++i) {
3118 struct diff_filepair *p = side_pairs->queue[i];
3119 pool_diff_free_filepair(&opt->priv->pool, p);
3120 }
3121 }
3122
3123 simple_cleanup:
3124 /* Free memory for renames->pairs[] and combined */
3125 for (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {
3126 free(renames->pairs[s].queue);
3127 DIFF_QUEUE_CLEAR(&renames->pairs[s]);
3128 }
3129 if (combined.nr) {
3130 int i;
3131 for (i = 0; i < combined.nr; i++)
3132 pool_diff_free_filepair(&opt->priv->pool,
3133 combined.queue[i]);
3134 free(combined.queue);
3135 }
3136
3137 return clean;
3138 }
3139
3140 /*** Function Grouping: functions related to process_entries() ***/
3141
3142 static int sort_dirs_next_to_their_children(const char *one, const char *two)
3143 {
3144 unsigned char c1, c2;
3145
3146 /*
3147 * Here we only care that entries for directories appear adjacent
3148 * to and before files underneath the directory. We can achieve
3149 * that by pretending to add a trailing slash to every file and
3150 * then sorting. In other words, we do not want the natural
3151 * sorting of
3152 * foo
3153 * foo.txt
3154 * foo/bar
3155 * Instead, we want "foo" to sort as though it were "foo/", so that
3156 * we instead get
3157 * foo.txt
3158 * foo
3159 * foo/bar
3160 * To achieve this, we basically implement our own strcmp, except that
3161 * if we get to the end of either string instead of comparing NUL to
3162 * another character, we compare '/' to it.
3163 *
3164 * If this unusual "sort as though '/' were appended" perplexes
3165 * you, perhaps it will help to note that this is not the final
3166 * sort. write_tree() will sort again without the trailing slash
3167 * magic, but just on paths immediately under a given tree.
3168 *
3169 * The reason to not use df_name_compare directly was that it was
3170 * just too expensive (we don't have the string lengths handy), so
3171 * it was reimplemented.
3172 */
3173
3174 /*
3175 * NOTE: This function will never be called with two equal strings,
3176 * because it is used to sort the keys of a strmap, and strmaps have
3177 * unique keys by construction. That simplifies our c1==c2 handling
3178 * below.
3179 */
3180
3181 while (*one && (*one == *two)) {
3182 one++;
3183 two++;
3184 }
3185
3186 c1 = *one ? *one : '/';
3187 c2 = *two ? *two : '/';
3188
3189 if (c1 == c2) {
3190 /* Getting here means one is a leading directory of the other */
3191 return (*one) ? 1 : -1;
3192 } else
3193 return c1 - c2;
3194 }
3195
3196 static int read_oid_strbuf(struct merge_options *opt,
3197 const struct object_id *oid,
3198 struct strbuf *dst)
3199 {
3200 void *buf;
3201 enum object_type type;
3202 unsigned long size;
3203 buf = read_object_file(oid, &type, &size);
3204 if (!buf)
3205 return err(opt, _("cannot read object %s"), oid_to_hex(oid));
3206 if (type != OBJ_BLOB) {
3207 free(buf);
3208 return err(opt, _("object %s is not a blob"), oid_to_hex(oid));
3209 }
3210 strbuf_attach(dst, buf, size, size + 1);
3211 return 0;
3212 }
3213
3214 static int blob_unchanged(struct merge_options *opt,
3215 const struct version_info *base,
3216 const struct version_info *side,
3217 const char *path)
3218 {
3219 struct strbuf basebuf = STRBUF_INIT;
3220 struct strbuf sidebuf = STRBUF_INIT;
3221 int ret = 0; /* assume changed for safety */
3222 struct index_state *idx = &opt->priv->attr_index;
3223
3224 if (!idx->initialized)
3225 initialize_attr_index(opt);
3226
3227 if (base->mode != side->mode)
3228 return 0;
3229 if (oideq(&base->oid, &side->oid))
3230 return 1;
3231
3232 if (read_oid_strbuf(opt, &base->oid, &basebuf) ||
3233 read_oid_strbuf(opt, &side->oid, &sidebuf))
3234 goto error_return;
3235 /*
3236 * Note: binary | is used so that both renormalizations are
3237 * performed. Comparison can be skipped if both files are
3238 * unchanged since their sha1s have already been compared.
3239 */
3240 if (renormalize_buffer(idx, path, basebuf.buf, basebuf.len, &basebuf) |
3241 renormalize_buffer(idx, path, sidebuf.buf, sidebuf.len, &sidebuf))
3242 ret = (basebuf.len == sidebuf.len &&
3243 !memcmp(basebuf.buf, sidebuf.buf, basebuf.len));
3244
3245 error_return:
3246 strbuf_release(&basebuf);
3247 strbuf_release(&sidebuf);
3248 return ret;
3249 }
3250
3251 struct directory_versions {
3252 /*
3253 * versions: list of (basename -> version_info)
3254 *
3255 * The basenames are in reverse lexicographic order of full pathnames,
3256 * as processed in process_entries(). This puts all entries within
3257 * a directory together, and covers the directory itself after
3258 * everything within it, allowing us to write subtrees before needing
3259 * to record information for the tree itself.
3260 */
3261 struct string_list versions;
3262
3263 /*
3264 * offsets: list of (full relative path directories -> integer offsets)
3265 *
3266 * Since versions contains basenames from files in multiple different
3267 * directories, we need to know which entries in versions correspond
3268 * to which directories. Values of e.g.
3269 * "" 0
3270 * src 2
3271 * src/moduleA 5
3272 * Would mean that entries 0-1 of versions are files in the toplevel
3273 * directory, entries 2-4 are files under src/, and the remaining
3274 * entries starting at index 5 are files under src/moduleA/.
3275 */
3276 struct string_list offsets;
3277
3278 /*
3279 * last_directory: directory that previously processed file found in
3280 *
3281 * last_directory starts NULL, but records the directory in which the
3282 * previous file was found within. As soon as
3283 * directory(current_file) != last_directory
3284 * then we need to start updating accounting in versions & offsets.
3285 * Note that last_directory is always the last path in "offsets" (or
3286 * NULL if "offsets" is empty) so this exists just for quick access.
3287 */
3288 const char *last_directory;
3289
3290 /* last_directory_len: cached computation of strlen(last_directory) */
3291 unsigned last_directory_len;
3292 };
3293
3294 static int tree_entry_order(const void *a_, const void *b_)
3295 {
3296 const struct string_list_item *a = a_;
3297 const struct string_list_item *b = b_;
3298
3299 const struct merged_info *ami = a->util;
3300 const struct merged_info *bmi = b->util;
3301 return base_name_compare(a->string, strlen(a->string), ami->result.mode,
3302 b->string, strlen(b->string), bmi->result.mode);
3303 }
3304
3305 static void write_tree(struct object_id *result_oid,
3306 struct string_list *versions,
3307 unsigned int offset,
3308 size_t hash_size)
3309 {
3310 size_t maxlen = 0, extra;
3311 unsigned int nr;
3312 struct strbuf buf = STRBUF_INIT;
3313 int i;
3314
3315 assert(offset <= versions->nr);
3316 nr = versions->nr - offset;
3317 if (versions->nr)
3318 /* No need for STABLE_QSORT -- filenames must be unique */
3319 QSORT(versions->items + offset, nr, tree_entry_order);
3320
3321 /* Pre-allocate some space in buf */
3322 extra = hash_size + 8; /* 8: 6 for mode, 1 for space, 1 for NUL char */
3323 for (i = 0; i < nr; i++) {
3324 maxlen += strlen(versions->items[offset+i].string) + extra;
3325 }
3326 strbuf_grow(&buf, maxlen);
3327
3328 /* Write each entry out to buf */
3329 for (i = 0; i < nr; i++) {
3330 struct merged_info *mi = versions->items[offset+i].util;
3331 struct version_info *ri = &mi->result;
3332 strbuf_addf(&buf, "%o %s%c",
3333 ri->mode,
3334 versions->items[offset+i].string, '\0');
3335 strbuf_add(&buf, ri->oid.hash, hash_size);
3336 }
3337
3338 /* Write this object file out, and record in result_oid */
3339 write_object_file(buf.buf, buf.len, tree_type, result_oid);
3340 strbuf_release(&buf);
3341 }
3342
3343 static void record_entry_for_tree(struct directory_versions *dir_metadata,
3344 const char *path,
3345 struct merged_info *mi)
3346 {
3347 const char *basename;
3348
3349 if (mi->is_null)
3350 /* nothing to record */
3351 return;
3352
3353 basename = path + mi->basename_offset;
3354 assert(strchr(basename, '/') == NULL);
3355 string_list_append(&dir_metadata->versions,
3356 basename)->util = &mi->result;
3357 }
3358
3359 static void write_completed_directory(struct merge_options *opt,
3360 const char *new_directory_name,
3361 struct directory_versions *info)
3362 {
3363 const char *prev_dir;
3364 struct merged_info *dir_info = NULL;
3365 unsigned int offset;
3366
3367 /*
3368 * Some explanation of info->versions and info->offsets...
3369 *
3370 * process_entries() iterates over all relevant files AND
3371 * directories in reverse lexicographic order, and calls this
3372 * function. Thus, an example of the paths that process_entries()
3373 * could operate on (along with the directories for those paths
3374 * being shown) is:
3375 *
3376 * xtract.c ""
3377 * tokens.txt ""
3378 * src/moduleB/umm.c src/moduleB
3379 * src/moduleB/stuff.h src/moduleB
3380 * src/moduleB/baz.c src/moduleB
3381 * src/moduleB src
3382 * src/moduleA/foo.c src/moduleA
3383 * src/moduleA/bar.c src/moduleA
3384 * src/moduleA src
3385 * src ""
3386 * Makefile ""
3387 *
3388 * info->versions:
3389 *
3390 * always contains the unprocessed entries and their
3391 * version_info information. For example, after the first five
3392 * entries above, info->versions would be:
3393 *
3394 * xtract.c <xtract.c's version_info>
3395 * token.txt <token.txt's version_info>
3396 * umm.c <src/moduleB/umm.c's version_info>
3397 * stuff.h <src/moduleB/stuff.h's version_info>
3398 * baz.c <src/moduleB/baz.c's version_info>
3399 *
3400 * Once a subdirectory is completed we remove the entries in
3401 * that subdirectory from info->versions, writing it as a tree
3402 * (write_tree()). Thus, as soon as we get to src/moduleB,
3403 * info->versions would be updated to
3404 *
3405 * xtract.c <xtract.c's version_info>
3406 * token.txt <token.txt's version_info>
3407 * moduleB <src/moduleB's version_info>
3408 *
3409 * info->offsets:
3410 *
3411 * helps us track which entries in info->versions correspond to
3412 * which directories. When we are N directories deep (e.g. 4
3413 * for src/modA/submod/subdir/), we have up to N+1 unprocessed
3414 * directories (+1 because of toplevel dir). Corresponding to
3415 * the info->versions example above, after processing five entries
3416 * info->offsets will be:
3417 *
3418 * "" 0
3419 * src/moduleB 2
3420 *
3421 * which is used to know that xtract.c & token.txt are from the
3422 * toplevel dirctory, while umm.c & stuff.h & baz.c are from the
3423 * src/moduleB directory. Again, following the example above,
3424 * once we need to process src/moduleB, then info->offsets is
3425 * updated to
3426 *
3427 * "" 0
3428 * src 2
3429 *
3430 * which says that moduleB (and only moduleB so far) is in the
3431 * src directory.
3432 *
3433 * One unique thing to note about info->offsets here is that
3434 * "src" was not added to info->offsets until there was a path
3435 * (a file OR directory) immediately below src/ that got
3436 * processed.
3437 *
3438 * Since process_entry() just appends new entries to info->versions,
3439 * write_completed_directory() only needs to do work if the next path
3440 * is in a directory that is different than the last directory found
3441 * in info->offsets.
3442 */
3443
3444 /*
3445 * If we are working with the same directory as the last entry, there
3446 * is no work to do. (See comments above the directory_name member of
3447 * struct merged_info for why we can use pointer comparison instead of
3448 * strcmp here.)
3449 */
3450 if (new_directory_name == info->last_directory)
3451 return;
3452
3453 /*
3454 * If we are just starting (last_directory is NULL), or last_directory
3455 * is a prefix of the current directory, then we can just update
3456 * info->offsets to record the offset where we started this directory
3457 * and update last_directory to have quick access to it.
3458 */
3459 if (info->last_directory == NULL ||
3460 !strncmp(new_directory_name, info->last_directory,
3461 info->last_directory_len)) {
3462 uintptr_t offset = info->versions.nr;
3463
3464 info->last_directory = new_directory_name;
3465 info->last_directory_len = strlen(info->last_directory);
3466 /*
3467 * Record the offset into info->versions where we will
3468 * start recording basenames of paths found within
3469 * new_directory_name.
3470 */
3471 string_list_append(&info->offsets,
3472 info->last_directory)->util = (void*)offset;
3473 return;
3474 }
3475
3476 /*
3477 * The next entry that will be processed will be within
3478 * new_directory_name. Since at this point we know that
3479 * new_directory_name is within a different directory than
3480 * info->last_directory, we have all entries for info->last_directory
3481 * in info->versions and we need to create a tree object for them.
3482 */
3483 dir_info = strmap_get(&opt->priv->paths, info->last_directory);
3484 assert(dir_info);
3485 offset = (uintptr_t)info->offsets.items[info->offsets.nr-1].util;
3486 if (offset == info->versions.nr) {
3487 /*
3488 * Actually, we don't need to create a tree object in this
3489 * case. Whenever all files within a directory disappear
3490 * during the merge (e.g. unmodified on one side and
3491 * deleted on the other, or files were renamed elsewhere),
3492 * then we get here and the directory itself needs to be
3493 * omitted from its parent tree as well.
3494 */
3495 dir_info->is_null = 1;
3496 } else {
3497 /*
3498 * Write out the tree to the git object directory, and also
3499 * record the mode and oid in dir_info->result.
3500 */
3501 dir_info->is_null = 0;
3502 dir_info->result.mode = S_IFDIR;
3503 write_tree(&dir_info->result.oid, &info->versions, offset,
3504 opt->repo->hash_algo->rawsz);
3505 }
3506
3507 /*
3508 * We've now used several entries from info->versions and one entry
3509 * from info->offsets, so we get rid of those values.
3510 */
3511 info->offsets.nr--;
3512 info->versions.nr = offset;
3513
3514 /*
3515 * Now we've taken care of the completed directory, but we need to
3516 * prepare things since future entries will be in
3517 * new_directory_name. (In particular, process_entry() will be
3518 * appending new entries to info->versions.) So, we need to make
3519 * sure new_directory_name is the last entry in info->offsets.
3520 */
3521 prev_dir = info->offsets.nr == 0 ? NULL :
3522 info->offsets.items[info->offsets.nr-1].string;
3523 if (new_directory_name != prev_dir) {
3524 uintptr_t c = info->versions.nr;
3525 string_list_append(&info->offsets,
3526 new_directory_name)->util = (void*)c;
3527 }
3528
3529 /* And, of course, we need to update last_directory to match. */
3530 info->last_directory = new_directory_name;
3531 info->last_directory_len = strlen(info->last_directory);
3532 }
3533
3534 /* Per entry merge function */
3535 static void process_entry(struct merge_options *opt,
3536 const char *path,
3537 struct conflict_info *ci,
3538 struct directory_versions *dir_metadata)
3539 {
3540 int df_file_index = 0;
3541
3542 VERIFY_CI(ci);
3543 assert(ci->filemask >= 0 && ci->filemask <= 7);
3544 /* ci->match_mask == 7 was handled in collect_merge_info_callback() */
3545 assert(ci->match_mask == 0 || ci->match_mask == 3 ||
3546 ci->match_mask == 5 || ci->match_mask == 6);
3547
3548 if (ci->dirmask) {
3549 record_entry_for_tree(dir_metadata, path, &ci->merged);
3550 if (ci->filemask == 0)
3551 /* nothing else to handle */
3552 return;
3553 assert(ci->df_conflict);
3554 }
3555
3556 if (ci->df_conflict && ci->merged.result.mode == 0) {
3557 int i;
3558
3559 /*
3560 * directory no longer in the way, but we do have a file we
3561 * need to place here so we need to clean away the "directory
3562 * merges to nothing" result.
3563 */
3564 ci->df_conflict = 0;
3565 assert(ci->filemask != 0);
3566 ci->merged.clean = 0;
3567 ci->merged.is_null = 0;
3568 /* and we want to zero out any directory-related entries */
3569 ci->match_mask = (ci->match_mask & ~ci->dirmask);
3570 ci->dirmask = 0;
3571 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
3572 if (ci->filemask & (1 << i))
3573 continue;
3574 ci->stages[i].mode = 0;
3575 oidcpy(&ci->stages[i].oid, null_oid());
3576 }
3577 } else if (ci->df_conflict && ci->merged.result.mode != 0) {
3578 /*
3579 * This started out as a D/F conflict, and the entries in
3580 * the competing directory were not removed by the merge as
3581 * evidenced by write_completed_directory() writing a value
3582 * to ci->merged.result.mode.
3583 */
3584 struct conflict_info *new_ci;
3585 const char *branch;
3586 const char *old_path = path;
3587 int i;
3588
3589 assert(ci->merged.result.mode == S_IFDIR);
3590
3591 /*
3592 * If filemask is 1, we can just ignore the file as having
3593 * been deleted on both sides. We do not want to overwrite
3594 * ci->merged.result, since it stores the tree for all the
3595 * files under it.
3596 */
3597 if (ci->filemask == 1) {
3598 ci->filemask = 0;
3599 return;
3600 }
3601
3602 /*
3603 * This file still exists on at least one side, and we want
3604 * the directory to remain here, so we need to move this
3605 * path to some new location.
3606 */
3607 new_ci = mem_pool_calloc(&opt->priv->pool, 1, sizeof(*new_ci));
3608
3609 /* We don't really want new_ci->merged.result copied, but it'll
3610 * be overwritten below so it doesn't matter. We also don't
3611 * want any directory mode/oid values copied, but we'll zero
3612 * those out immediately. We do want the rest of ci copied.
3613 */
3614 memcpy(new_ci, ci, sizeof(*ci));
3615 new_ci->match_mask = (new_ci->match_mask & ~new_ci->dirmask);
3616 new_ci->dirmask = 0;
3617 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
3618 if (new_ci->filemask & (1 << i))
3619 continue;
3620 /* zero out any entries related to directories */
3621 new_ci->stages[i].mode = 0;
3622 oidcpy(&new_ci->stages[i].oid, null_oid());
3623 }
3624
3625 /*
3626 * Find out which side this file came from; note that we
3627 * cannot just use ci->filemask, because renames could cause
3628 * the filemask to go back to 7. So we use dirmask, then
3629 * pick the opposite side's index.
3630 */
3631 df_file_index = (ci->dirmask & (1 << 1)) ? 2 : 1;
3632 branch = (df_file_index == 1) ? opt->branch1 : opt->branch2;
3633 path = unique_path(&opt->priv->paths, path, branch);
3634 strmap_put(&opt->priv->paths, path, new_ci);
3635
3636 path_msg(opt, path, 0,
3637 _("CONFLICT (file/directory): directory in the way "
3638 "of %s from %s; moving it to %s instead."),
3639 old_path, branch, path);
3640
3641 /*
3642 * Zero out the filemask for the old ci. At this point, ci
3643 * was just an entry for a directory, so we don't need to
3644 * do anything more with it.
3645 */
3646 ci->filemask = 0;
3647
3648 /*
3649 * Now note that we're working on the new entry (path was
3650 * updated above.
3651 */
3652 ci = new_ci;
3653 }
3654
3655 /*
3656 * NOTE: Below there is a long switch-like if-elseif-elseif... block
3657 * which the code goes through even for the df_conflict cases
3658 * above.
3659 */
3660 if (ci->match_mask) {
3661 ci->merged.clean = !ci->df_conflict && !ci->path_conflict;
3662 if (ci->match_mask == 6) {
3663 /* stages[1] == stages[2] */
3664 ci->merged.result.mode = ci->stages[1].mode;
3665 oidcpy(&ci->merged.result.oid, &ci->stages[1].oid);
3666 } else {
3667 /* determine the mask of the side that didn't match */
3668 unsigned int othermask = 7 & ~ci->match_mask;
3669 int side = (othermask == 4) ? 2 : 1;
3670
3671 ci->merged.result.mode = ci->stages[side].mode;
3672 ci->merged.is_null = !ci->merged.result.mode;
3673 if (ci->merged.is_null)
3674 ci->merged.clean = 1;
3675 oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
3676
3677 assert(othermask == 2 || othermask == 4);
3678 assert(ci->merged.is_null ==
3679 (ci->filemask == ci->match_mask));
3680 }
3681 } else if (ci->filemask >= 6 &&
3682 (S_IFMT & ci->stages[1].mode) !=
3683 (S_IFMT & ci->stages[2].mode)) {
3684 /* Two different items from (file/submodule/symlink) */
3685 if (opt->priv->call_depth) {
3686 /* Just use the version from the merge base */
3687 ci->merged.clean = 0;
3688 oidcpy(&ci->merged.result.oid, &ci->stages[0].oid);
3689 ci->merged.result.mode = ci->stages[0].mode;
3690 ci->merged.is_null = (ci->merged.result.mode == 0);
3691 } else {
3692 /* Handle by renaming one or both to separate paths. */
3693 unsigned o_mode = ci->stages[0].mode;
3694 unsigned a_mode = ci->stages[1].mode;
3695 unsigned b_mode = ci->stages[2].mode;
3696 struct conflict_info *new_ci;
3697 const char *a_path = NULL, *b_path = NULL;
3698 int rename_a = 0, rename_b = 0;
3699
3700 new_ci = mem_pool_alloc(&opt->priv->pool,
3701 sizeof(*new_ci));
3702
3703 if (S_ISREG(a_mode))
3704 rename_a = 1;
3705 else if (S_ISREG(b_mode))
3706 rename_b = 1;
3707 else {
3708 rename_a = 1;
3709 rename_b = 1;
3710 }
3711
3712 if (rename_a && rename_b) {
3713 path_msg(opt, path, 0,
3714 _("CONFLICT (distinct types): %s had "
3715 "different types on each side; "
3716 "renamed both of them so each can "
3717 "be recorded somewhere."),
3718 path);
3719 } else {
3720 path_msg(opt, path, 0,
3721 _("CONFLICT (distinct types): %s had "
3722 "different types on each side; "
3723 "renamed one of them so each can be "
3724 "recorded somewhere."),
3725 path);
3726 }
3727
3728 ci->merged.clean = 0;
3729 memcpy(new_ci, ci, sizeof(*new_ci));
3730
3731 /* Put b into new_ci, removing a from stages */
3732 new_ci->merged.result.mode = ci->stages[2].mode;
3733 oidcpy(&new_ci->merged.result.oid, &ci->stages[2].oid);
3734 new_ci->stages[1].mode = 0;
3735 oidcpy(&new_ci->stages[1].oid, null_oid());
3736 new_ci->filemask = 5;
3737 if ((S_IFMT & b_mode) != (S_IFMT & o_mode)) {
3738 new_ci->stages[0].mode = 0;
3739 oidcpy(&new_ci->stages[0].oid, null_oid());
3740 new_ci->filemask = 4;
3741 }
3742
3743 /* Leave only a in ci, fixing stages. */
3744 ci->merged.result.mode = ci->stages[1].mode;
3745 oidcpy(&ci->merged.result.oid, &ci->stages[1].oid);
3746 ci->stages[2].mode = 0;
3747 oidcpy(&ci->stages[2].oid, null_oid());
3748 ci->filemask = 3;
3749 if ((S_IFMT & a_mode) != (S_IFMT & o_mode)) {
3750 ci->stages[0].mode = 0;
3751 oidcpy(&ci->stages[0].oid, null_oid());
3752 ci->filemask = 2;
3753 }
3754
3755 /* Insert entries into opt->priv_paths */
3756 assert(rename_a || rename_b);
3757 if (rename_a) {
3758 a_path = unique_path(&opt->priv->paths,
3759 path, opt->branch1);
3760 strmap_put(&opt->priv->paths, a_path, ci);
3761 }
3762
3763 if (rename_b)
3764 b_path = unique_path(&opt->priv->paths,
3765 path, opt->branch2);
3766 else
3767 b_path = path;
3768 strmap_put(&opt->priv->paths, b_path, new_ci);
3769
3770 if (rename_a && rename_b)
3771 strmap_remove(&opt->priv->paths, path, 0);
3772
3773 /*
3774 * Do special handling for b_path since process_entry()
3775 * won't be called on it specially.
3776 */
3777 strmap_put(&opt->priv->conflicted, b_path, new_ci);
3778 record_entry_for_tree(dir_metadata, b_path,
3779 &new_ci->merged);
3780
3781 /*
3782 * Remaining code for processing this entry should
3783 * think in terms of processing a_path.
3784 */
3785 if (a_path)
3786 path = a_path;
3787 }
3788 } else if (ci->filemask >= 6) {
3789 /* Need a two-way or three-way content merge */
3790 struct version_info merged_file;
3791 unsigned clean_merge;
3792 struct version_info *o = &ci->stages[0];
3793 struct version_info *a = &ci->stages[1];
3794 struct version_info *b = &ci->stages[2];
3795
3796 clean_merge = handle_content_merge(opt, path, o, a, b,
3797 ci->pathnames,
3798 opt->priv->call_depth * 2,
3799 &merged_file);
3800 ci->merged.clean = clean_merge &&
3801 !ci->df_conflict && !ci->path_conflict;
3802 ci->merged.result.mode = merged_file.mode;
3803 ci->merged.is_null = (merged_file.mode == 0);
3804 oidcpy(&ci->merged.result.oid, &merged_file.oid);
3805 if (clean_merge && ci->df_conflict) {
3806 assert(df_file_index == 1 || df_file_index == 2);
3807 ci->filemask = 1 << df_file_index;
3808 ci->stages[df_file_index].mode = merged_file.mode;
3809 oidcpy(&ci->stages[df_file_index].oid, &merged_file.oid);
3810 }
3811 if (!clean_merge) {
3812 const char *reason = _("content");
3813 if (ci->filemask == 6)
3814 reason = _("add/add");
3815 if (S_ISGITLINK(merged_file.mode))
3816 reason = _("submodule");
3817 path_msg(opt, path, 0,
3818 _("CONFLICT (%s): Merge conflict in %s"),
3819 reason, path);
3820 }
3821 } else if (ci->filemask == 3 || ci->filemask == 5) {
3822 /* Modify/delete */
3823 const char *modify_branch, *delete_branch;
3824 int side = (ci->filemask == 5) ? 2 : 1;
3825 int index = opt->priv->call_depth ? 0 : side;
3826
3827 ci->merged.result.mode = ci->stages[index].mode;
3828 oidcpy(&ci->merged.result.oid, &ci->stages[index].oid);
3829 ci->merged.clean = 0;
3830
3831 modify_branch = (side == 1) ? opt->branch1 : opt->branch2;
3832 delete_branch = (side == 1) ? opt->branch2 : opt->branch1;
3833
3834 if (opt->renormalize &&
3835 blob_unchanged(opt, &ci->stages[0], &ci->stages[side],
3836 path)) {
3837 ci->merged.is_null = 1;
3838 ci->merged.clean = 1;
3839 assert(!ci->df_conflict && !ci->path_conflict);
3840 } else if (ci->path_conflict &&
3841 oideq(&ci->stages[0].oid, &ci->stages[side].oid)) {
3842 /*
3843 * This came from a rename/delete; no action to take,
3844 * but avoid printing "modify/delete" conflict notice
3845 * since the contents were not modified.
3846 */
3847 } else {
3848 path_msg(opt, path, 0,
3849 _("CONFLICT (modify/delete): %s deleted in %s "
3850 "and modified in %s. Version %s of %s left "
3851 "in tree."),
3852 path, delete_branch, modify_branch,
3853 modify_branch, path);
3854 }
3855 } else if (ci->filemask == 2 || ci->filemask == 4) {
3856 /* Added on one side */
3857 int side = (ci->filemask == 4) ? 2 : 1;
3858 ci->merged.result.mode = ci->stages[side].mode;
3859 oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
3860 ci->merged.clean = !ci->df_conflict && !ci->path_conflict;
3861 } else if (ci->filemask == 1) {
3862 /* Deleted on both sides */
3863 ci->merged.is_null = 1;
3864 ci->merged.result.mode = 0;
3865 oidcpy(&ci->merged.result.oid, null_oid());
3866 assert(!ci->df_conflict);
3867 ci->merged.clean = !ci->path_conflict;
3868 }
3869
3870 /*
3871 * If still conflicted, record it separately. This allows us to later
3872 * iterate over just conflicted entries when updating the index instead
3873 * of iterating over all entries.
3874 */
3875 if (!ci->merged.clean)
3876 strmap_put(&opt->priv->conflicted, path, ci);
3877
3878 /* Record metadata for ci->merged in dir_metadata */
3879 record_entry_for_tree(dir_metadata, path, &ci->merged);
3880 }
3881
3882 static void prefetch_for_content_merges(struct merge_options *opt,
3883 struct string_list *plist)
3884 {
3885 struct string_list_item *e;
3886 struct oid_array to_fetch = OID_ARRAY_INIT;
3887
3888 if (opt->repo != the_repository || !has_promisor_remote())
3889 return;
3890
3891 for (e = &plist->items[plist->nr-1]; e >= plist->items; --e) {
3892 /* char *path = e->string; */
3893 struct conflict_info *ci = e->util;
3894 int i;
3895
3896 /* Ignore clean entries */
3897 if (ci->merged.clean)
3898 continue;
3899
3900 /* Ignore entries that don't need a content merge */
3901 if (ci->match_mask || ci->filemask < 6 ||
3902 !S_ISREG(ci->stages[1].mode) ||
3903 !S_ISREG(ci->stages[2].mode) ||
3904 oideq(&ci->stages[1].oid, &ci->stages[2].oid))
3905 continue;
3906
3907 /* Also don't need content merge if base matches either side */
3908 if (ci->filemask == 7 &&
3909 S_ISREG(ci->stages[0].mode) &&
3910 (oideq(&ci->stages[0].oid, &ci->stages[1].oid) ||
3911 oideq(&ci->stages[0].oid, &ci->stages[2].oid)))
3912 continue;
3913
3914 for (i = 0; i < 3; i++) {
3915 unsigned side_mask = (1 << i);
3916 struct version_info *vi = &ci->stages[i];
3917
3918 if ((ci->filemask & side_mask) &&
3919 S_ISREG(vi->mode) &&
3920 oid_object_info_extended(opt->repo, &vi->oid, NULL,
3921 OBJECT_INFO_FOR_PREFETCH))
3922 oid_array_append(&to_fetch, &vi->oid);
3923 }
3924 }
3925
3926 promisor_remote_get_direct(opt->repo, to_fetch.oid, to_fetch.nr);
3927 oid_array_clear(&to_fetch);
3928 }
3929
3930 static void process_entries(struct merge_options *opt,
3931 struct object_id *result_oid)
3932 {
3933 struct hashmap_iter iter;
3934 struct strmap_entry *e;
3935 struct string_list plist = STRING_LIST_INIT_NODUP;
3936 struct string_list_item *entry;
3937 struct directory_versions dir_metadata = { STRING_LIST_INIT_NODUP,
3938 STRING_LIST_INIT_NODUP,
3939 NULL, 0 };
3940
3941 trace2_region_enter("merge", "process_entries setup", opt->repo);
3942 if (strmap_empty(&opt->priv->paths)) {
3943 oidcpy(result_oid, opt->repo->hash_algo->empty_tree);
3944 return;
3945 }
3946
3947 /* Hack to pre-allocate plist to the desired size */
3948 trace2_region_enter("merge", "plist grow", opt->repo);
3949 ALLOC_GROW(plist.items, strmap_get_size(&opt->priv->paths), plist.alloc);
3950 trace2_region_leave("merge", "plist grow", opt->repo);
3951
3952 /* Put every entry from paths into plist, then sort */
3953 trace2_region_enter("merge", "plist copy", opt->repo);
3954 strmap_for_each_entry(&opt->priv->paths, &iter, e) {
3955 string_list_append(&plist, e->key)->util = e->value;
3956 }
3957 trace2_region_leave("merge", "plist copy", opt->repo);
3958
3959 trace2_region_enter("merge", "plist special sort", opt->repo);
3960 plist.cmp = sort_dirs_next_to_their_children;
3961 string_list_sort(&plist);
3962 trace2_region_leave("merge", "plist special sort", opt->repo);
3963
3964 trace2_region_leave("merge", "process_entries setup", opt->repo);
3965
3966 /*
3967 * Iterate over the items in reverse order, so we can handle paths
3968 * below a directory before needing to handle the directory itself.
3969 *
3970 * This allows us to write subtrees before we need to write trees,
3971 * and it also enables sane handling of directory/file conflicts
3972 * (because it allows us to know whether the directory is still in
3973 * the way when it is time to process the file at the same path).
3974 */
3975 trace2_region_enter("merge", "processing", opt->repo);
3976 prefetch_for_content_merges(opt, &plist);
3977 for (entry = &plist.items[plist.nr-1]; entry >= plist.items; --entry) {
3978 char *path = entry->string;
3979 /*
3980 * NOTE: mi may actually be a pointer to a conflict_info, but
3981 * we have to check mi->clean first to see if it's safe to
3982 * reassign to such a pointer type.
3983 */
3984 struct merged_info *mi = entry->util;
3985
3986 write_completed_directory(opt, mi->directory_name,
3987 &dir_metadata);
3988 if (mi->clean)
3989 record_entry_for_tree(&dir_metadata, path, mi);
3990 else {
3991 struct conflict_info *ci = (struct conflict_info *)mi;
3992 process_entry(opt, path, ci, &dir_metadata);
3993 }
3994 }
3995 trace2_region_leave("merge", "processing", opt->repo);
3996
3997 trace2_region_enter("merge", "process_entries cleanup", opt->repo);
3998 if (dir_metadata.offsets.nr != 1 ||
3999 (uintptr_t)dir_metadata.offsets.items[0].util != 0) {
4000 printf("dir_metadata.offsets.nr = %d (should be 1)\n",
4001 dir_metadata.offsets.nr);
4002 printf("dir_metadata.offsets.items[0].util = %u (should be 0)\n",
4003 (unsigned)(uintptr_t)dir_metadata.offsets.items[0].util);
4004 fflush(stdout);
4005 BUG("dir_metadata accounting completely off; shouldn't happen");
4006 }
4007 write_tree(result_oid, &dir_metadata.versions, 0,
4008 opt->repo->hash_algo->rawsz);
4009 string_list_clear(&plist, 0);
4010 string_list_clear(&dir_metadata.versions, 0);
4011 string_list_clear(&dir_metadata.offsets, 0);
4012 trace2_region_leave("merge", "process_entries cleanup", opt->repo);
4013 }
4014
4015 /*** Function Grouping: functions related to merge_switch_to_result() ***/
4016
4017 static int checkout(struct merge_options *opt,
4018 struct tree *prev,
4019 struct tree *next)
4020 {
4021 /* Switch the index/working copy from old to new */
4022 int ret;
4023 struct tree_desc trees[2];
4024 struct unpack_trees_options unpack_opts;
4025
4026 memset(&unpack_opts, 0, sizeof(unpack_opts));
4027 unpack_opts.head_idx = -1;
4028 unpack_opts.src_index = opt->repo->index;
4029 unpack_opts.dst_index = opt->repo->index;
4030
4031 setup_unpack_trees_porcelain(&unpack_opts, "merge");
4032
4033 /*
4034 * NOTE: if this were just "git checkout" code, we would probably
4035 * read or refresh the cache and check for a conflicted index, but
4036 * builtin/merge.c or sequencer.c really needs to read the index
4037 * and check for conflicted entries before starting merging for a
4038 * good user experience (no sense waiting for merges/rebases before
4039 * erroring out), so there's no reason to duplicate that work here.
4040 */
4041
4042 /* 2-way merge to the new branch */
4043 unpack_opts.update = 1;
4044 unpack_opts.merge = 1;
4045 unpack_opts.quiet = 0; /* FIXME: sequencer might want quiet? */
4046 unpack_opts.verbose_update = (opt->verbosity > 2);
4047 unpack_opts.fn = twoway_merge;
4048 if (1/* FIXME: opts->overwrite_ignore*/) {
4049 CALLOC_ARRAY(unpack_opts.dir, 1);
4050 unpack_opts.dir->flags |= DIR_SHOW_IGNORED;
4051 setup_standard_excludes(unpack_opts.dir);
4052 }
4053 parse_tree(prev);
4054 init_tree_desc(&trees[0], prev->buffer, prev->size);
4055 parse_tree(next);
4056 init_tree_desc(&trees[1], next->buffer, next->size);
4057
4058 ret = unpack_trees(2, trees, &unpack_opts);
4059 clear_unpack_trees_porcelain(&unpack_opts);
4060 dir_clear(unpack_opts.dir);
4061 FREE_AND_NULL(unpack_opts.dir);
4062 return ret;
4063 }
4064
4065 static int record_conflicted_index_entries(struct merge_options *opt)
4066 {
4067 struct hashmap_iter iter;
4068 struct strmap_entry *e;
4069 struct index_state *index = opt->repo->index;
4070 struct checkout state = CHECKOUT_INIT;
4071 int errs = 0;
4072 int original_cache_nr;
4073
4074 if (strmap_empty(&opt->priv->conflicted))
4075 return 0;
4076
4077 /* If any entries have skip_worktree set, we'll have to check 'em out */
4078 state.force = 1;
4079 state.quiet = 1;
4080 state.refresh_cache = 1;
4081 state.istate = index;
4082 original_cache_nr = index->cache_nr;
4083
4084 /* Put every entry from paths into plist, then sort */
4085 strmap_for_each_entry(&opt->priv->conflicted, &iter, e) {
4086 const char *path = e->key;
4087 struct conflict_info *ci = e->value;
4088 int pos;
4089 struct cache_entry *ce;
4090 int i;
4091
4092 VERIFY_CI(ci);
4093
4094 /*
4095 * The index will already have a stage=0 entry for this path,
4096 * because we created an as-merged-as-possible version of the
4097 * file and checkout() moved the working copy and index over
4098 * to that version.
4099 *
4100 * However, previous iterations through this loop will have
4101 * added unstaged entries to the end of the cache which
4102 * ignore the standard alphabetical ordering of cache
4103 * entries and break invariants needed for index_name_pos()
4104 * to work. However, we know the entry we want is before
4105 * those appended cache entries, so do a temporary swap on
4106 * cache_nr to only look through entries of interest.
4107 */
4108 SWAP(index->cache_nr, original_cache_nr);
4109 pos = index_name_pos(index, path, strlen(path));
4110 SWAP(index->cache_nr, original_cache_nr);
4111 if (pos < 0) {
4112 if (ci->filemask != 1)
4113 BUG("Conflicted %s but nothing in basic working tree or index; this shouldn't happen", path);
4114 cache_tree_invalidate_path(index, path);
4115 } else {
4116 ce = index->cache[pos];
4117
4118 /*
4119 * Clean paths with CE_SKIP_WORKTREE set will not be
4120 * written to the working tree by the unpack_trees()
4121 * call in checkout(). Our conflicted entries would
4122 * have appeared clean to that code since we ignored
4123 * the higher order stages. Thus, we need override
4124 * the CE_SKIP_WORKTREE bit and manually write those
4125 * files to the working disk here.
4126 */
4127 if (ce_skip_worktree(ce)) {
4128 struct stat st;
4129
4130 if (!lstat(path, &st)) {
4131 char *new_name = unique_path(&opt->priv->paths,
4132 path,
4133 "cruft");
4134
4135 path_msg(opt, path, 1,
4136 _("Note: %s not up to date and in way of checking out conflicted version; old copy renamed to %s"),
4137 path, new_name);
4138 errs |= rename(path, new_name);
4139 free(new_name);
4140 }
4141 errs |= checkout_entry(ce, &state, NULL, NULL);
4142 }
4143
4144 /*
4145 * Mark this cache entry for removal and instead add
4146 * new stage>0 entries corresponding to the
4147 * conflicts. If there are many conflicted entries, we
4148 * want to avoid memmove'ing O(NM) entries by
4149 * inserting the new entries one at a time. So,
4150 * instead, we just add the new cache entries to the
4151 * end (ignoring normal index requirements on sort
4152 * order) and sort the index once we're all done.
4153 */
4154 ce->ce_flags |= CE_REMOVE;
4155 }
4156
4157 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
4158 struct version_info *vi;
4159 if (!(ci->filemask & (1ul << i)))
4160 continue;
4161 vi = &ci->stages[i];
4162 ce = make_cache_entry(index, vi->mode, &vi->oid,
4163 path, i+1, 0);
4164 add_index_entry(index, ce, ADD_CACHE_JUST_APPEND);
4165 }
4166 }
4167
4168 /*
4169 * Remove the unused cache entries (and invalidate the relevant
4170 * cache-trees), then sort the index entries to get the conflicted
4171 * entries we added to the end into their right locations.
4172 */
4173 remove_marked_cache_entries(index, 1);
4174 /*
4175 * No need for STABLE_QSORT -- cmp_cache_name_compare sorts primarily
4176 * on filename and secondarily on stage, and (name, stage #) are a
4177 * unique tuple.
4178 */
4179 QSORT(index->cache, index->cache_nr, cmp_cache_name_compare);
4180
4181 return errs;
4182 }
4183
4184 void merge_switch_to_result(struct merge_options *opt,
4185 struct tree *head,
4186 struct merge_result *result,
4187 int update_worktree_and_index,
4188 int display_update_msgs)
4189 {
4190 assert(opt->priv == NULL);
4191 if (result->clean >= 0 && update_worktree_and_index) {
4192 const char *filename;
4193 FILE *fp;
4194
4195 trace2_region_enter("merge", "checkout", opt->repo);
4196 if (checkout(opt, head, result->tree)) {
4197 /* failure to function */
4198 result->clean = -1;
4199 return;
4200 }
4201 trace2_region_leave("merge", "checkout", opt->repo);
4202
4203 trace2_region_enter("merge", "record_conflicted", opt->repo);
4204 opt->priv = result->priv;
4205 if (record_conflicted_index_entries(opt)) {
4206 /* failure to function */
4207 opt->priv = NULL;
4208 result->clean = -1;
4209 return;
4210 }
4211 opt->priv = NULL;
4212 trace2_region_leave("merge", "record_conflicted", opt->repo);
4213
4214 trace2_region_enter("merge", "write_auto_merge", opt->repo);
4215 filename = git_path_auto_merge(opt->repo);
4216 fp = xfopen(filename, "w");
4217 fprintf(fp, "%s\n", oid_to_hex(&result->tree->object.oid));
4218 fclose(fp);
4219 trace2_region_leave("merge", "write_auto_merge", opt->repo);
4220 }
4221
4222 if (display_update_msgs) {
4223 struct merge_options_internal *opti = result->priv;
4224 struct hashmap_iter iter;
4225 struct strmap_entry *e;
4226 struct string_list olist = STRING_LIST_INIT_NODUP;
4227 int i;
4228
4229 trace2_region_enter("merge", "display messages", opt->repo);
4230
4231 /* Hack to pre-allocate olist to the desired size */
4232 ALLOC_GROW(olist.items, strmap_get_size(&opti->output),
4233 olist.alloc);
4234
4235 /* Put every entry from output into olist, then sort */
4236 strmap_for_each_entry(&opti->output, &iter, e) {
4237 string_list_append(&olist, e->key)->util = e->value;
4238 }
4239 string_list_sort(&olist);
4240
4241 /* Iterate over the items, printing them */
4242 for (i = 0; i < olist.nr; ++i) {
4243 struct strbuf *sb = olist.items[i].util;
4244
4245 printf("%s", sb->buf);
4246 }
4247 string_list_clear(&olist, 0);
4248
4249 /* Also include needed rename limit adjustment now */
4250 diff_warn_rename_limit("merge.renamelimit",
4251 opti->renames.needed_limit, 0);
4252
4253 trace2_region_leave("merge", "display messages", opt->repo);
4254 }
4255
4256 merge_finalize(opt, result);
4257 }
4258
4259 void merge_finalize(struct merge_options *opt,
4260 struct merge_result *result)
4261 {
4262 struct merge_options_internal *opti = result->priv;
4263
4264 if (opt->renormalize)
4265 git_attr_set_direction(GIT_ATTR_CHECKIN);
4266 assert(opt->priv == NULL);
4267
4268 clear_or_reinit_internal_opts(opti, 0);
4269 FREE_AND_NULL(opti);
4270 }
4271
4272 /*** Function Grouping: helper functions for merge_incore_*() ***/
4273
4274 static struct tree *shift_tree_object(struct repository *repo,
4275 struct tree *one, struct tree *two,
4276 const char *subtree_shift)
4277 {
4278 struct object_id shifted;
4279
4280 if (!*subtree_shift) {
4281 shift_tree(repo, &one->object.oid, &two->object.oid, &shifted, 0);
4282 } else {
4283 shift_tree_by(repo, &one->object.oid, &two->object.oid, &shifted,
4284 subtree_shift);
4285 }
4286 if (oideq(&two->object.oid, &shifted))
4287 return two;
4288 return lookup_tree(repo, &shifted);
4289 }
4290
4291 static inline void set_commit_tree(struct commit *c, struct tree *t)
4292 {
4293 c->maybe_tree = t;
4294 }
4295
4296 static struct commit *make_virtual_commit(struct repository *repo,
4297 struct tree *tree,
4298 const char *comment)
4299 {
4300 struct commit *commit = alloc_commit_node(repo);
4301
4302 set_merge_remote_desc(commit, comment, (struct object *)commit);
4303 set_commit_tree(commit, tree);
4304 commit->object.parsed = 1;
4305 return commit;
4306 }
4307
4308 static void merge_start(struct merge_options *opt, struct merge_result *result)
4309 {
4310 struct rename_info *renames;
4311 int i;
4312 struct mem_pool *pool = NULL;
4313
4314 /* Sanity checks on opt */
4315 trace2_region_enter("merge", "sanity checks", opt->repo);
4316 assert(opt->repo);
4317
4318 assert(opt->branch1 && opt->branch2);
4319
4320 assert(opt->detect_directory_renames >= MERGE_DIRECTORY_RENAMES_NONE &&
4321 opt->detect_directory_renames <= MERGE_DIRECTORY_RENAMES_TRUE);
4322 assert(opt->rename_limit >= -1);
4323 assert(opt->rename_score >= 0 && opt->rename_score <= MAX_SCORE);
4324 assert(opt->show_rename_progress >= 0 && opt->show_rename_progress <= 1);
4325
4326 assert(opt->xdl_opts >= 0);
4327 assert(opt->recursive_variant >= MERGE_VARIANT_NORMAL &&
4328 opt->recursive_variant <= MERGE_VARIANT_THEIRS);
4329
4330 /*
4331 * detect_renames, verbosity, buffer_output, and obuf are ignored
4332 * fields that were used by "recursive" rather than "ort" -- but
4333 * sanity check them anyway.
4334 */
4335 assert(opt->detect_renames >= -1 &&
4336 opt->detect_renames <= DIFF_DETECT_COPY);
4337 assert(opt->verbosity >= 0 && opt->verbosity <= 5);
4338 assert(opt->buffer_output <= 2);
4339 assert(opt->obuf.len == 0);
4340
4341 assert(opt->priv == NULL);
4342 if (result->_properly_initialized != 0 &&
4343 result->_properly_initialized != RESULT_INITIALIZED)
4344 BUG("struct merge_result passed to merge_incore_*recursive() must be zeroed or filled with values from a previous run");
4345 assert(!!result->priv == !!result->_properly_initialized);
4346 if (result->priv) {
4347 opt->priv = result->priv;
4348 result->priv = NULL;
4349 /*
4350 * opt->priv non-NULL means we had results from a previous
4351 * run; do a few sanity checks that user didn't mess with
4352 * it in an obvious fashion.
4353 */
4354 assert(opt->priv->call_depth == 0);
4355 assert(!opt->priv->toplevel_dir ||
4356 0 == strlen(opt->priv->toplevel_dir));
4357 }
4358 trace2_region_leave("merge", "sanity checks", opt->repo);
4359
4360 /* Default to histogram diff. Actually, just hardcode it...for now. */
4361 opt->xdl_opts = DIFF_WITH_ALG(opt, HISTOGRAM_DIFF);
4362
4363 /* Handle attr direction stuff for renormalization */
4364 if (opt->renormalize)
4365 git_attr_set_direction(GIT_ATTR_CHECKOUT);
4366
4367 /* Initialization of opt->priv, our internal merge data */
4368 trace2_region_enter("merge", "allocate/init", opt->repo);
4369 if (opt->priv) {
4370 clear_or_reinit_internal_opts(opt->priv, 1);
4371 trace2_region_leave("merge", "allocate/init", opt->repo);
4372 return;
4373 }
4374 opt->priv = xcalloc(1, sizeof(*opt->priv));
4375
4376 /* Initialization of various renames fields */
4377 renames = &opt->priv->renames;
4378 mem_pool_init(&opt->priv->pool, 0);
4379 pool = &opt->priv->pool;
4380 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {
4381 strintmap_init_with_options(&renames->dirs_removed[i],
4382 NOT_RELEVANT, pool, 0);
4383 strmap_init_with_options(&renames->dir_rename_count[i],
4384 NULL, 1);
4385 strmap_init_with_options(&renames->dir_renames[i],
4386 NULL, 0);
4387 /*
4388 * relevant_sources uses -1 for the default, because we need
4389 * to be able to distinguish not-in-strintmap from valid
4390 * relevant_source values from enum file_rename_relevance.
4391 * In particular, possibly_cache_new_pair() expects a negative
4392 * value for not-found entries.
4393 */
4394 strintmap_init_with_options(&renames->relevant_sources[i],
4395 -1 /* explicitly invalid */,
4396 pool, 0);
4397 strmap_init_with_options(&renames->cached_pairs[i],
4398 NULL, 1);
4399 strset_init_with_options(&renames->cached_irrelevant[i],
4400 NULL, 1);
4401 strset_init_with_options(&renames->cached_target_names[i],
4402 NULL, 0);
4403 }
4404 for (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {
4405 strintmap_init_with_options(&renames->deferred[i].possible_trivial_merges,
4406 0, pool, 0);
4407 strset_init_with_options(&renames->deferred[i].target_dirs,
4408 pool, 1);
4409 renames->deferred[i].trivial_merges_okay = 1; /* 1 == maybe */
4410 }
4411
4412 /*
4413 * Although we initialize opt->priv->paths with strdup_strings=0,
4414 * that's just to avoid making yet another copy of an allocated
4415 * string. Putting the entry into paths means we are taking
4416 * ownership, so we will later free it.
4417 *
4418 * In contrast, conflicted just has a subset of keys from paths, so
4419 * we don't want to free those (it'd be a duplicate free).
4420 */
4421 strmap_init_with_options(&opt->priv->paths, pool, 0);
4422 strmap_init_with_options(&opt->priv->conflicted, pool, 0);
4423
4424 /*
4425 * keys & strbufs in output will sometimes need to outlive "paths",
4426 * so it will have a copy of relevant keys. It's probably a small
4427 * subset of the overall paths that have special output.
4428 */
4429 strmap_init(&opt->priv->output);
4430
4431 trace2_region_leave("merge", "allocate/init", opt->repo);
4432 }
4433
4434 static void merge_check_renames_reusable(struct merge_options *opt,
4435 struct merge_result *result,
4436 struct tree *merge_base,
4437 struct tree *side1,
4438 struct tree *side2)
4439 {
4440 struct rename_info *renames;
4441 struct tree **merge_trees;
4442 struct merge_options_internal *opti = result->priv;
4443
4444 if (!opti)
4445 return;
4446
4447 renames = &opti->renames;
4448 merge_trees = renames->merge_trees;
4449
4450 /*
4451 * Handle case where previous merge operation did not want cache to
4452 * take effect, e.g. because rename/rename(1to1) makes it invalid.
4453 */
4454 if (!merge_trees[0]) {
4455 assert(!merge_trees[0] && !merge_trees[1] && !merge_trees[2]);
4456 renames->cached_pairs_valid_side = 0; /* neither side valid */
4457 return;
4458 }
4459
4460 /*
4461 * Handle other cases; note that merge_trees[0..2] will only
4462 * be NULL if opti is, or if all three were manually set to
4463 * NULL by e.g. rename/rename(1to1) handling.
4464 */
4465 assert(merge_trees[0] && merge_trees[1] && merge_trees[2]);
4466
4467 /* Check if we meet a condition for re-using cached_pairs */
4468 if (oideq(&merge_base->object.oid, &merge_trees[2]->object.oid) &&
4469 oideq(&side1->object.oid, &result->tree->object.oid))
4470 renames->cached_pairs_valid_side = MERGE_SIDE1;
4471 else if (oideq(&merge_base->object.oid, &merge_trees[1]->object.oid) &&
4472 oideq(&side2->object.oid, &result->tree->object.oid))
4473 renames->cached_pairs_valid_side = MERGE_SIDE2;
4474 else
4475 renames->cached_pairs_valid_side = 0; /* neither side valid */
4476 }
4477
4478 /*** Function Grouping: merge_incore_*() and their internal variants ***/
4479
4480 /*
4481 * Originally from merge_trees_internal(); heavily adapted, though.
4482 */
4483 static void merge_ort_nonrecursive_internal(struct merge_options *opt,
4484 struct tree *merge_base,
4485 struct tree *side1,
4486 struct tree *side2,
4487 struct merge_result *result)
4488 {
4489 struct object_id working_tree_oid;
4490
4491 if (opt->subtree_shift) {
4492 side2 = shift_tree_object(opt->repo, side1, side2,
4493 opt->subtree_shift);
4494 merge_base = shift_tree_object(opt->repo, side1, merge_base,
4495 opt->subtree_shift);
4496 }
4497
4498 redo:
4499 trace2_region_enter("merge", "collect_merge_info", opt->repo);
4500 if (collect_merge_info(opt, merge_base, side1, side2) != 0) {
4501 /*
4502 * TRANSLATORS: The %s arguments are: 1) tree hash of a merge
4503 * base, and 2-3) the trees for the two trees we're merging.
4504 */
4505 err(opt, _("collecting merge info failed for trees %s, %s, %s"),
4506 oid_to_hex(&merge_base->object.oid),
4507 oid_to_hex(&side1->object.oid),
4508 oid_to_hex(&side2->object.oid));
4509 result->clean = -1;
4510 return;
4511 }
4512 trace2_region_leave("merge", "collect_merge_info", opt->repo);
4513
4514 trace2_region_enter("merge", "renames", opt->repo);
4515 result->clean = detect_and_process_renames(opt, merge_base,
4516 side1, side2);
4517 trace2_region_leave("merge", "renames", opt->repo);
4518 if (opt->priv->renames.redo_after_renames == 2) {
4519 trace2_region_enter("merge", "reset_maps", opt->repo);
4520 clear_or_reinit_internal_opts(opt->priv, 1);
4521 trace2_region_leave("merge", "reset_maps", opt->repo);
4522 goto redo;
4523 }
4524
4525 trace2_region_enter("merge", "process_entries", opt->repo);
4526 process_entries(opt, &working_tree_oid);
4527 trace2_region_leave("merge", "process_entries", opt->repo);
4528
4529 /* Set return values */
4530 result->tree = parse_tree_indirect(&working_tree_oid);
4531 /* existence of conflicted entries implies unclean */
4532 result->clean &= strmap_empty(&opt->priv->conflicted);
4533 if (!opt->priv->call_depth) {
4534 result->priv = opt->priv;
4535 result->_properly_initialized = RESULT_INITIALIZED;
4536 opt->priv = NULL;
4537 }
4538 }
4539
4540 /*
4541 * Originally from merge_recursive_internal(); somewhat adapted, though.
4542 */
4543 static void merge_ort_internal(struct merge_options *opt,
4544 struct commit_list *merge_bases,
4545 struct commit *h1,
4546 struct commit *h2,
4547 struct merge_result *result)
4548 {
4549 struct commit_list *iter;
4550 struct commit *merged_merge_bases;
4551 const char *ancestor_name;
4552 struct strbuf merge_base_abbrev = STRBUF_INIT;
4553
4554 if (!merge_bases) {
4555 merge_bases = get_merge_bases(h1, h2);
4556 /* See merge-ort.h:merge_incore_recursive() declaration NOTE */
4557 merge_bases = reverse_commit_list(merge_bases);
4558 }
4559
4560 merged_merge_bases = pop_commit(&merge_bases);
4561 if (merged_merge_bases == NULL) {
4562 /* if there is no common ancestor, use an empty tree */
4563 struct tree *tree;
4564
4565 tree = lookup_tree(opt->repo, opt->repo->hash_algo->empty_tree);
4566 merged_merge_bases = make_virtual_commit(opt->repo, tree,
4567 "ancestor");
4568 ancestor_name = "empty tree";
4569 } else if (merge_bases) {
4570 ancestor_name = "merged common ancestors";
4571 } else {
4572 strbuf_add_unique_abbrev(&merge_base_abbrev,
4573 &merged_merge_bases->object.oid,
4574 DEFAULT_ABBREV);
4575 ancestor_name = merge_base_abbrev.buf;
4576 }
4577
4578 for (iter = merge_bases; iter; iter = iter->next) {
4579 const char *saved_b1, *saved_b2;
4580 struct commit *prev = merged_merge_bases;
4581
4582 opt->priv->call_depth++;
4583 /*
4584 * When the merge fails, the result contains files
4585 * with conflict markers. The cleanness flag is
4586 * ignored (unless indicating an error), it was never
4587 * actually used, as result of merge_trees has always
4588 * overwritten it: the committed "conflicts" were
4589 * already resolved.
4590 */
4591 saved_b1 = opt->branch1;
4592 saved_b2 = opt->branch2;
4593 opt->branch1 = "Temporary merge branch 1";
4594 opt->branch2 = "Temporary merge branch 2";
4595 merge_ort_internal(opt, NULL, prev, iter->item, result);
4596 if (result->clean < 0)
4597 return;
4598 opt->branch1 = saved_b1;
4599 opt->branch2 = saved_b2;
4600 opt->priv->call_depth--;
4601
4602 merged_merge_bases = make_virtual_commit(opt->repo,
4603 result->tree,
4604 "merged tree");
4605 commit_list_insert(prev, &merged_merge_bases->parents);
4606 commit_list_insert(iter->item,
4607 &merged_merge_bases->parents->next);
4608
4609 clear_or_reinit_internal_opts(opt->priv, 1);
4610 }
4611
4612 opt->ancestor = ancestor_name;
4613 merge_ort_nonrecursive_internal(opt,
4614 repo_get_commit_tree(opt->repo,
4615 merged_merge_bases),
4616 repo_get_commit_tree(opt->repo, h1),
4617 repo_get_commit_tree(opt->repo, h2),
4618 result);
4619 strbuf_release(&merge_base_abbrev);
4620 opt->ancestor = NULL; /* avoid accidental re-use of opt->ancestor */
4621 }
4622
4623 void merge_incore_nonrecursive(struct merge_options *opt,
4624 struct tree *merge_base,
4625 struct tree *side1,
4626 struct tree *side2,
4627 struct merge_result *result)
4628 {
4629 trace2_region_enter("merge", "incore_nonrecursive", opt->repo);
4630
4631 trace2_region_enter("merge", "merge_start", opt->repo);
4632 assert(opt->ancestor != NULL);
4633 merge_check_renames_reusable(opt, result, merge_base, side1, side2);
4634 merge_start(opt, result);
4635 /*
4636 * Record the trees used in this merge, so if there's a next merge in
4637 * a cherry-pick or rebase sequence it might be able to take advantage
4638 * of the cached_pairs in that next merge.
4639 */
4640 opt->priv->renames.merge_trees[0] = merge_base;
4641 opt->priv->renames.merge_trees[1] = side1;
4642 opt->priv->renames.merge_trees[2] = side2;
4643 trace2_region_leave("merge", "merge_start", opt->repo);
4644
4645 merge_ort_nonrecursive_internal(opt, merge_base, side1, side2, result);
4646 trace2_region_leave("merge", "incore_nonrecursive", opt->repo);
4647 }
4648
4649 void merge_incore_recursive(struct merge_options *opt,
4650 struct commit_list *merge_bases,
4651 struct commit *side1,
4652 struct commit *side2,
4653 struct merge_result *result)
4654 {
4655 trace2_region_enter("merge", "incore_recursive", opt->repo);
4656
4657 /* We set the ancestor label based on the merge_bases */
4658 assert(opt->ancestor == NULL);
4659
4660 trace2_region_enter("merge", "merge_start", opt->repo);
4661 merge_start(opt, result);
4662 trace2_region_leave("merge", "merge_start", opt->repo);
4663
4664 merge_ort_internal(opt, merge_bases, side1, side2, result);
4665 trace2_region_leave("merge", "incore_recursive", opt->repo);
4666 }