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