git/merge-recursive.c

/*
 * Recursive Merge algorithm stolen from git-merge-recursive.py by
 * Fredrik Kuivinen.
 * The thieves were Alex Riesen and Johannes Schindelin, in June/July 2006
 */

#define USE_THE_REPOSITORY_VARIABLE

#include "git-compat-util.h"
#include "merge-recursive.h"

#include "alloc.h"
#include "cache-tree.h"
#include "commit.h"
#include "commit-reach.h"
#include "config.h"
#include "diff.h"
#include "diffcore.h"
#include "dir.h"
#include "environment.h"
#include "gettext.h"
#include "hex.h"
#include "merge-ll.h"
#include "lockfile.h"
#include "match-trees.h"
#include "name-hash.h"
#include "object-file.h"
#include "object-name.h"
#include "object-store-ll.h"
#include "path.h"
#include "repository.h"
#include "revision.h"
#include "sparse-index.h"
#include "string-list.h"
#include "symlinks.h"
#include "tag.h"
#include "tree-walk.h"
#include "unpack-trees.h"
#include "xdiff-interface.h"

struct merge_options_internal { … };

struct path_hashmap_entry { … };

static int path_hashmap_cmp(const void *cmp_data UNUSED,
			    const struct hashmap_entry *eptr,
			    const struct hashmap_entry *entry_or_key,
			    const void *keydata)
{ … }

/*
 * For dir_rename_entry, directory names are stored as a full path from the
 * toplevel of the repository and do not include a trailing '/'.  Also:
 *
 *   dir:                original name of directory being renamed
 *   non_unique_new_dir: if true, could not determine new_dir
 *   new_dir:            final name of directory being renamed
 *   possible_new_dirs:  temporary used to help determine new_dir; see comments
 *                       in get_directory_renames() for details
 */
struct dir_rename_entry { … };

static struct dir_rename_entry *dir_rename_find_entry(struct hashmap *hashmap,
						      char *dir)
{ … }

static int dir_rename_cmp(const void *cmp_data UNUSED,
			  const struct hashmap_entry *eptr,
			  const struct hashmap_entry *entry_or_key,
			  const void *keydata UNUSED)
{ … }

static void dir_rename_init(struct hashmap *map)
{ … }

static void dir_rename_entry_init(struct dir_rename_entry *entry,
				  char *directory)
{ … }

struct collision_entry { … };

static struct collision_entry *collision_find_entry(struct hashmap *hashmap,
						    char *target_file)
{ … }

static int collision_cmp(const void *cmp_data UNUSED,
			 const struct hashmap_entry *eptr,
			 const struct hashmap_entry *entry_or_key,
			 const void *keydata UNUSED)
{ … }

static void collision_init(struct hashmap *map)
{ … }

static void flush_output(struct merge_options *opt)
{ … }

__attribute__((format (printf, 2, 3)))
static int err(struct merge_options *opt, const char *err, ...)
{ … }

static struct tree *shift_tree_object(struct repository *repo,
				      struct tree *one, struct tree *two,
				      const char *subtree_shift)
{ … }

static inline void set_commit_tree(struct commit *c, struct tree *t)
{ … }

static struct commit *make_virtual_commit(struct repository *repo,
					  struct tree *tree,
					  const char *comment)
{ … }

enum rename_type { … };

/*
 * Since we want to write the index eventually, we cannot reuse the index
 * for these (temporary) data.
 */
struct stage_data { … };

struct rename { … };

struct rename_conflict_info { … };

static inline void setup_rename_conflict_info(enum rename_type rename_type,
					      struct merge_options *opt,
					      struct rename *ren1,
					      struct rename *ren2)
{ … }

static int show(struct merge_options *opt, int v)
{ … }

__attribute__((format (printf, 3, 4)))
static void output(struct merge_options *opt, int v, const char *fmt, ...)
{ … }

static void repo_output_commit_title(struct merge_options *opt,
				     struct repository *repo,
				     struct commit *commit)
{ … }

static void output_commit_title(struct merge_options *opt, struct commit *commit)
{ … }

static int add_cacheinfo(struct merge_options *opt,
			 const struct diff_filespec *blob,
			 const char *path, int stage, int refresh, int options)
{ … }

static inline int merge_detect_rename(struct merge_options *opt)
{ … }

static void init_tree_desc_from_tree(struct tree_desc *desc, struct tree *tree)
{ … }

static int unpack_trees_start(struct merge_options *opt,
			      struct tree *common,
			      struct tree *head,
			      struct tree *merge)
{ … }

static void unpack_trees_finish(struct merge_options *opt)
{ … }

static int save_files_dirs(const struct object_id *oid UNUSED,
			   struct strbuf *base, const char *path,
			   unsigned int mode, void *context)
{ … }

static void get_files_dirs(struct merge_options *opt, struct tree *tree)
{ … }

static int get_tree_entry_if_blob(struct repository *r,
				  const struct object_id *tree,
				  const char *path,
				  struct diff_filespec *dfs)
{ … }

/*
 * Returns an index_entry instance which doesn't have to correspond to
 * a real cache entry in Git's index.
 */
static struct stage_data *insert_stage_data(struct repository *r,
		const char *path,
		struct tree *o, struct tree *a, struct tree *b,
		struct string_list *entries)
{ … }

/*
 * Create a dictionary mapping file names to stage_data objects. The
 * dictionary contains one entry for every path with a non-zero stage entry.
 */
static struct string_list *get_unmerged(struct index_state *istate)
{ … }

static int string_list_df_name_compare(const char *one, const char *two)
{ … }

static void record_df_conflict_files(struct merge_options *opt,
				     struct string_list *entries)
{ … }

static int update_stages(struct merge_options *opt, const char *path,
			 const struct diff_filespec *o,
			 const struct diff_filespec *a,
			 const struct diff_filespec *b)
{ … }

static void update_entry(struct stage_data *entry,
			 struct diff_filespec *o,
			 struct diff_filespec *a,
			 struct diff_filespec *b)
{ … }

static int remove_file(struct merge_options *opt, int clean,
		       const char *path, int no_wd)
{ … }

/* add a string to a strbuf, but converting "/" to "_" */
static void add_flattened_path(struct strbuf *out, const char *s)
{ … }

static char *unique_path(struct merge_options *opt,
			 const char *path,
			 const char *branch)
{ … }

/**
 * Check whether a directory in the index is in the way of an incoming
 * file.  Return 1 if so.  If check_working_copy is non-zero, also
 * check the working directory.  If empty_ok is non-zero, also return
 * 0 in the case where the working-tree dir exists but is empty.
 */
static int dir_in_way(struct index_state *istate, const char *path,
		      int check_working_copy, int empty_ok)
{ … }

/*
 * Returns whether path was tracked in the index before the merge started,
 * and its oid and mode match the specified values
 */
static int was_tracked_and_matches(struct merge_options *opt, const char *path,
				   const struct diff_filespec *blob)
{ … }

/*
 * Returns whether path was tracked in the index before the merge started
 */
static int was_tracked(struct merge_options *opt, const char *path)
{ … }

static int would_lose_untracked(struct merge_options *opt, const char *path)
{ … }

static int was_dirty(struct merge_options *opt, const char *path)
{ … }

static int make_room_for_path(struct merge_options *opt, const char *path)
{ … }

static int update_file_flags(struct merge_options *opt,
			     const struct diff_filespec *contents,
			     const char *path,
			     int update_cache,
			     int update_wd)
{ … }

static int update_file(struct merge_options *opt,
		       int clean,
		       const struct diff_filespec *contents,
		       const char *path)
{ … }

/* Low level file merging, update and removal */

struct merge_file_info { … };

static int merge_3way(struct merge_options *opt,
		      mmbuffer_t *result_buf,
		      const struct diff_filespec *o,
		      const struct diff_filespec *a,
		      const struct diff_filespec *b,
		      const char *branch1,
		      const char *branch2,
		      const int extra_marker_size)
{ … }

static int find_first_merges(struct repository *repo,
			     struct object_array *result, const char *path,
			     struct commit *a, struct commit *b)
{ … }

static void print_commit(struct repository *repo, struct commit *commit)
{ … }

static int is_valid(const struct diff_filespec *dfs)
{ … }

static int merge_submodule(struct merge_options *opt,
			   struct object_id *result, const char *path,
			   const struct object_id *base, const struct object_id *a,
			   const struct object_id *b)
{ … }

static int merge_mode_and_contents(struct merge_options *opt,
				   const struct diff_filespec *o,
				   const struct diff_filespec *a,
				   const struct diff_filespec *b,
				   const char *filename,
				   const char *branch1,
				   const char *branch2,
				   const int extra_marker_size,
				   struct merge_file_info *result)
{ … }

static int handle_rename_via_dir(struct merge_options *opt,
				 struct rename_conflict_info *ci)
{ … }

static int handle_change_delete(struct merge_options *opt,
				const char *path, const char *old_path,
				const struct diff_filespec *o,
				const struct diff_filespec *changed,
				const char *change_branch,
				const char *delete_branch,
				const char *change, const char *change_past)
{ … }

static int handle_rename_delete(struct merge_options *opt,
				struct rename_conflict_info *ci)
{ … }

static int handle_file_collision(struct merge_options *opt,
				 const char *collide_path,
				 const char *prev_path1,
				 const char *prev_path2,
				 const char *branch1, const char *branch2,
				 struct diff_filespec *a,
				 struct diff_filespec *b)
{ … }

static int handle_rename_add(struct merge_options *opt,
			     struct rename_conflict_info *ci)
{ … }

static char *find_path_for_conflict(struct merge_options *opt,
				    const char *path,
				    const char *branch1,
				    const char *branch2)
{ … }

/*
 * Toggle the stage number between "ours" and "theirs" (2 and 3).
 */
static inline int flip_stage(int stage)
{ … }

static int handle_rename_rename_1to2(struct merge_options *opt,
				     struct rename_conflict_info *ci)
{ … }

static int handle_rename_rename_2to1(struct merge_options *opt,
				     struct rename_conflict_info *ci)
{ … }

/*
 * Get the diff_filepairs changed between o_tree and tree.
 */
static struct diff_queue_struct *get_diffpairs(struct merge_options *opt,
					       struct tree *o_tree,
					       struct tree *tree)
{ … }

static int tree_has_path(struct repository *r, struct tree *tree,
			 const char *path)
{ … }

/*
 * Return a new string that replaces the beginning portion (which matches
 * entry->dir), with entry->new_dir.  In perl-speak:
 *   new_path_name = (old_path =~ s/entry->dir/entry->new_dir/);
 * NOTE:
 *   Caller must ensure that old_path starts with entry->dir + '/'.
 */
static char *apply_dir_rename(struct dir_rename_entry *entry,
			      const char *old_path)
{ … }

static void get_renamed_dir_portion(const char *old_path, const char *new_path,
				    char **old_dir, char **new_dir)
{ … }

static void remove_hashmap_entries(struct hashmap *dir_renames,
				   struct string_list *items_to_remove)
{ … }

/*
 * See if there is a directory rename for path, and if there are any file
 * level conflicts for the renamed location.  If there is a rename and
 * there are no conflicts, return the new name.  Otherwise, return NULL.
 */
static char *handle_path_level_conflicts(struct merge_options *opt,
					 const char *path,
					 struct dir_rename_entry *entry,
					 struct hashmap *collisions,
					 struct tree *tree)
{ … }

/*
 * There are a couple things we want to do at the directory level:
 *   1. Check for both sides renaming to the same thing, in order to avoid
 *      implicit renaming of files that should be left in place.  (See
 *      testcase 6b in t6043 for details.)
 *   2. Prune directory renames if there are still files left in the
 *      original directory.  These represent a partial directory rename,
 *      i.e. a rename where only some of the files within the directory
 *      were renamed elsewhere.  (Technically, this could be done earlier
 *      in get_directory_renames(), except that would prevent us from
 *      doing the previous check and thus failing testcase 6b.)
 *   3. Check for rename/rename(1to2) conflicts (at the directory level).
 *      In the future, we could potentially record this info as well and
 *      omit reporting rename/rename(1to2) conflicts for each path within
 *      the affected directories, thus cleaning up the merge output.
 *   NOTE: We do NOT check for rename/rename(2to1) conflicts at the
 *         directory level, because merging directories is fine.  If it
 *         causes conflicts for files within those merged directories, then
 *         that should be detected at the individual path level.
 */
static void handle_directory_level_conflicts(struct merge_options *opt,
					     struct hashmap *dir_re_head,
					     struct tree *head,
					     struct hashmap *dir_re_merge,
					     struct tree *merge)
{ … }

static struct hashmap *get_directory_renames(struct diff_queue_struct *pairs)
{ … }

static struct dir_rename_entry *check_dir_renamed(const char *path,
						  struct hashmap *dir_renames)
{ … }

static void compute_collisions(struct hashmap *collisions,
			       struct hashmap *dir_renames,
			       struct diff_queue_struct *pairs)
{ … }

static char *check_for_directory_rename(struct merge_options *opt,
					const char *path,
					struct tree *tree,
					struct hashmap *dir_renames,
					struct hashmap *dir_rename_exclusions,
					struct hashmap *collisions,
					int *clean_merge)
{ … }

static void apply_directory_rename_modifications(struct merge_options *opt,
						 struct diff_filepair *pair,
						 char *new_path,
						 struct rename *re,
						 struct tree *tree,
						 struct tree *o_tree,
						 struct tree *a_tree,
						 struct tree *b_tree,
						 struct string_list *entries)
{ … }

/*
 * Get information of all renames which occurred in 'pairs', making use of
 * any implicit directory renames inferred from the other side of history.
 * We need the three trees in the merge ('o_tree', 'a_tree' and 'b_tree')
 * to be able to associate the correct cache entries with the rename
 * information; tree is always equal to either a_tree or b_tree.
 */
static struct string_list *get_renames(struct merge_options *opt,
				       const char *branch,
				       struct diff_queue_struct *pairs,
				       struct hashmap *dir_renames,
				       struct hashmap *dir_rename_exclusions,
				       struct tree *tree,
				       struct tree *o_tree,
				       struct tree *a_tree,
				       struct tree *b_tree,
				       struct string_list *entries,
				       int *clean_merge)
{ … }

static int process_renames(struct merge_options *opt,
			   struct string_list *a_renames,
			   struct string_list *b_renames)
{ … }

struct rename_info { … };

static void initial_cleanup_rename(struct diff_queue_struct *pairs,
				   struct hashmap *dir_renames)
{ … }

static int detect_and_process_renames(struct merge_options *opt,
				      struct tree *common,
				      struct tree *head,
				      struct tree *merge,
				      struct string_list *entries,
				      struct rename_info *ri)
{ … }

static void final_cleanup_rename(struct string_list *rename)
{ … }

static void final_cleanup_renames(struct rename_info *re_info)
{ … }

static int read_oid_strbuf(struct merge_options *opt,
			   const struct object_id *oid,
			   struct strbuf *dst)
{ … }

static int blob_unchanged(struct merge_options *opt,
			  const struct diff_filespec *o,
			  const struct diff_filespec *a,
			  int renormalize, const char *path)
{ … }

static int handle_modify_delete(struct merge_options *opt,
				const char *path,
				const struct diff_filespec *o,
				const struct diff_filespec *a,
				const struct diff_filespec *b)
{ … }

static int handle_content_merge(struct merge_file_info *mfi,
				struct merge_options *opt,
				const char *path,
				int is_dirty,
				const struct diff_filespec *o,
				const struct diff_filespec *a,
				const struct diff_filespec *b,
				struct rename_conflict_info *ci)
{ … }

static int handle_rename_normal(struct merge_options *opt,
				const char *path,
				const struct diff_filespec *o,
				const struct diff_filespec *a,
				const struct diff_filespec *b,
				struct rename_conflict_info *ci)
{ … }

static void dir_rename_warning(const char *msg,
			       int is_add,
			       int clean,
			       struct merge_options *opt,
			       struct rename *ren)
{ … }
static int warn_about_dir_renamed_entries(struct merge_options *opt,
					  struct rename *ren)
{ … }

/* Per entry merge function */
static int process_entry(struct merge_options *opt,
			 const char *path, struct stage_data *entry)
{ … }

static int merge_trees_internal(struct merge_options *opt,
				struct tree *head,
				struct tree *merge,
				struct tree *merge_base,
				struct tree **result)
{ … }

/*
 * Merge the commits h1 and h2, returning a flag (int) indicating the
 * cleanness of the merge.  Also, if opt->priv->call_depth, create a
 * virtual commit and write its location to *result.
 */
static int merge_recursive_internal(struct merge_options *opt,
				    struct commit *h1,
				    struct commit *h2,
				    const struct commit_list *_merge_bases,
				    struct commit **result)
{ … }

static int merge_start(struct merge_options *opt, struct tree *head)
{ … }

static void merge_finalize(struct merge_options *opt)
{ … }

int merge_trees(struct merge_options *opt,
		struct tree *head,
		struct tree *merge,
		struct tree *merge_base)
{ … }

int merge_recursive(struct merge_options *opt,
		    struct commit *h1,
		    struct commit *h2,
		    const struct commit_list *merge_bases,
		    struct commit **result)
{ … }

static struct commit *get_ref(struct repository *repo,
			      const struct object_id *oid,
			      const char *name)
{ … }

int merge_recursive_generic(struct merge_options *opt,
			    const struct object_id *head,
			    const struct object_id *merge,
			    int num_merge_bases,
			    const struct object_id *merge_bases,
			    struct commit **result)
{ … }

static void merge_recursive_config(struct merge_options *opt, int ui)
{ … }

static void init_merge_options(struct merge_options *opt,
			struct repository *repo, int ui)
{ … }

void init_ui_merge_options(struct merge_options *opt,
			struct repository *repo)
{ … }

void init_basic_merge_options(struct merge_options *opt,
			struct repository *repo)
{ … }

/*
 * For now, members of merge_options do not need deep copying, but
 * it may change in the future, in which case we would need to update
 * this, and also make a matching change to clear_merge_options() to
 * release the resources held by a copied instance.
 */
void copy_merge_options(struct merge_options *dst, struct merge_options *src)
{ … }

void clear_merge_options(struct merge_options *opt UNUSED)
{ … }

int parse_merge_opt(struct merge_options *opt, const char *s)
{ … }