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