merge-ort.c · leroysheep/rag-system

seen

bisect jch maint master next seen test todo

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

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