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