merge-ort.c · leroysheep/Socializer

maint

bisect jch maint master next seen test todo

c 5,598 lines 179 KB

Raw

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

Showing first 5,000 of 5,598 lines. View raw