/* * "Ostensibly Recursive's Twin" merge strategy, or "ort" for short. Meant * as a drop-in replacement for the "recursive" merge strategy, allowing one * to replace * * git merge [-s recursive] * * with * * git merge -s ort * * Note: git's parser allows the space between '-s' and its argument to be * missing. (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo", * "cale", "peedy", or "ins" instead of "ort"?) */ #include "cache.h" #include "merge-ort.h" #include "alloc.h" #include "blob.h" #include "cache-tree.h" #include "commit.h" #include "commit-reach.h" #include "diff.h" #include "diffcore.h" #include "dir.h" #include "ll-merge.h" #include "object-store.h" #include "revision.h" #include "strmap.h" #include "submodule.h" #include "tree.h" #include "unpack-trees.h" #include "xdiff-interface.h" /* * We have many arrays of size 3. Whenever we have such an array, the * indices refer to one of the sides of the three-way merge. This is so * pervasive that the constants 0, 1, and 2 are used in many places in the * code (especially in arithmetic operations to find the other side's index * or to compute a relevant mask), but sometimes these enum names are used * to aid code clarity. * * See also 'filemask' and 'dirmask' in struct conflict_info; the "ith side" * referred to there is one of these three sides. */ enum merge_side { MERGE_BASE = 0, MERGE_SIDE1 = 1, MERGE_SIDE2 = 2 }; struct rename_info { /* * All variables that are arrays of size 3 correspond to data tracked * for the sides in enum merge_side. Index 0 is almost always unused * because we often only need to track information for MERGE_SIDE1 and * MERGE_SIDE2 (MERGE_BASE can't have rename information since renames * are determined relative to what changed since the MERGE_BASE). */ /* * pairs: pairing of filenames from diffcore_rename() */ struct diff_queue_struct pairs[3]; /* * dirs_removed: directories removed on a given side of history. */ struct strset dirs_removed[3]; /* * dir_rename_count: tracking where parts of a directory were renamed to * * When files in a directory are renamed, they may not all go to the * same location. Each strmap here tracks: * old_dir => {new_dir => int} * That is, dir_rename_count[side] is a strmap to a strintmap. */ struct strmap dir_rename_count[3]; /* * dir_renames: computed directory renames * * This is a map of old_dir => new_dir and is derived in part from * dir_rename_count. */ struct strmap dir_renames[3]; /* * needed_limit: value needed for inexact rename detection to run * * If the current rename limit wasn't high enough for inexact * rename detection to run, this records the limit needed. Otherwise, * this value remains 0. */ int needed_limit; }; struct merge_options_internal { /* * paths: primary data structure in all of merge ort. * * The keys of paths: * * are full relative paths from the toplevel of the repository * (e.g. "drivers/firmware/raspberrypi.c"). * * store all relevant paths in the repo, both directories and * files (e.g. drivers, drivers/firmware would also be included) * * these keys serve to intern all the path strings, which allows * us to do pointer comparison on directory names instead of * strcmp; we just have to be careful to use the interned strings. * (Technically paths_to_free may track some strings that were * removed from froms paths.) * * The values of paths: * * either a pointer to a merged_info, or a conflict_info struct * * merged_info contains all relevant information for a * non-conflicted entry. * * conflict_info contains a merged_info, plus any additional * information about a conflict such as the higher orders stages * involved and the names of the paths those came from (handy * once renames get involved). * * a path may start "conflicted" (i.e. point to a conflict_info) * and then a later step (e.g. three-way content merge) determines * it can be cleanly merged, at which point it'll be marked clean * and the algorithm will ignore any data outside the contained * merged_info for that entry * * If an entry remains conflicted, the merged_info portion of a * conflict_info will later be filled with whatever version of * the file should be placed in the working directory (e.g. an * as-merged-as-possible variation that contains conflict markers). */ struct strmap paths; /* * conflicted: a subset of keys->values from "paths" * * conflicted is basically an optimization between process_entries() * and record_conflicted_index_entries(); the latter could loop over * ALL the entries in paths AGAIN and look for the ones that are * still conflicted, but since process_entries() has to loop over * all of them, it saves the ones it couldn't resolve in this strmap * so that record_conflicted_index_entries() can iterate just the * relevant entries. */ struct strmap conflicted; /* * paths_to_free: additional list of strings to free * * If keys are removed from "paths", they are added to paths_to_free * to ensure they are later freed. We avoid free'ing immediately since * other places (e.g. conflict_info.pathnames[]) may still be * referencing these paths. */ struct string_list paths_to_free; /* * output: special messages and conflict notices for various paths * * This is a map of pathnames (a subset of the keys in "paths" above) * to strbufs. It gathers various warning/conflict/notice messages * for later processing. */ struct strmap output; /* * renames: various data relating to rename detection */ struct rename_info renames; /* * current_dir_name, toplevel_dir: temporary vars * * These are used in collect_merge_info_callback(), and will set the * various merged_info.directory_name for the various paths we get; * see documentation for that variable and the requirements placed on * that field. */ const char *current_dir_name; const char *toplevel_dir; /* call_depth: recursion level counter for merging merge bases */ int call_depth; }; struct version_info { struct object_id oid; unsigned short mode; }; struct merged_info { /* if is_null, ignore result. otherwise result has oid & mode */ struct version_info result; unsigned is_null:1; /* * clean: whether the path in question is cleanly merged. * * see conflict_info.merged for more details. */ unsigned clean:1; /* * basename_offset: offset of basename of path. * * perf optimization to avoid recomputing offset of final '/' * character in pathname (0 if no '/' in pathname). */ size_t basename_offset; /* * directory_name: containing directory name. * * Note that we assume directory_name is constructed such that * strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name, * i.e. string equality is equivalent to pointer equality. For this * to hold, we have to be careful setting directory_name. */ const char *directory_name; }; struct conflict_info { /* * merged: the version of the path that will be written to working tree * * WARNING: It is critical to check merged.clean and ensure it is 0 * before reading any conflict_info fields outside of merged. * Allocated merge_info structs will always have clean set to 1. * Allocated conflict_info structs will have merged.clean set to 0 * initially. The merged.clean field is how we know if it is safe * to access other parts of conflict_info besides merged; if a * conflict_info's merged.clean is changed to 1, the rest of the * algorithm is not allowed to look at anything outside of the * merged member anymore. */ struct merged_info merged; /* oids & modes from each of the three trees for this path */ struct version_info stages[3]; /* pathnames for each stage; may differ due to rename detection */ const char *pathnames[3]; /* Whether this path is/was involved in a directory/file conflict */ unsigned df_conflict:1; /* * Whether this path is/was involved in a non-content conflict other * than a directory/file conflict (e.g. rename/rename, rename/delete, * file location based on possible directory rename). */ unsigned path_conflict:1; /* * For filemask and dirmask, the ith bit corresponds to whether the * ith entry is a file (filemask) or a directory (dirmask). Thus, * filemask & dirmask is always zero, and filemask | dirmask is at * most 7 but can be less when a path does not appear as either a * file or a directory on at least one side of history. * * Note that these masks are related to enum merge_side, as the ith * entry corresponds to side i. * * These values come from a traverse_trees() call; more info may be * found looking at tree-walk.h's struct traverse_info, * particularly the documentation above the "fn" member (note that * filemask = mask & ~dirmask from that documentation). */ unsigned filemask:3; unsigned dirmask:3; /* * Optimization to track which stages match, to avoid the need to * recompute it in multiple steps. Either 0 or at least 2 bits are * set; if at least 2 bits are set, their corresponding stages match. */ unsigned match_mask:3; }; /*** Function Grouping: various utility functions ***/ /* * For the next three macros, see warning for conflict_info.merged. * * In each of the below, mi is a struct merged_info*, and ci was defined * as a struct conflict_info* (but we need to verify ci isn't actually * pointed at a struct merged_info*). * * INITIALIZE_CI: Assign ci to mi but only if it's safe; set to NULL otherwise. * VERIFY_CI: Ensure that something we assigned to a conflict_info* is one. * ASSIGN_AND_VERIFY_CI: Similar to VERIFY_CI but do assignment first. */ #define INITIALIZE_CI(ci, mi) do { \ (ci) = (!(mi) || (mi)->clean) ? NULL : (struct conflict_info *)(mi); \ } while (0) #define VERIFY_CI(ci) assert(ci && !ci->merged.clean); #define ASSIGN_AND_VERIFY_CI(ci, mi) do { \ (ci) = (struct conflict_info *)(mi); \ assert((ci) && !(mi)->clean); \ } while (0) static void free_strmap_strings(struct strmap *map) { struct hashmap_iter iter; struct strmap_entry *entry; strmap_for_each_entry(map, &iter, entry) { free((char*)entry->key); } } static void clear_or_reinit_internal_opts(struct merge_options_internal *opti, int reinitialize) { struct rename_info *renames = &opti->renames; int i; void (*strmap_func)(struct strmap *, int) = reinitialize ? strmap_partial_clear : strmap_clear; void (*strset_func)(struct strset *) = reinitialize ? strset_partial_clear : strset_clear; /* * We marked opti->paths with strdup_strings = 0, so that we * wouldn't have to make another copy of the fullpath created by * make_traverse_path from setup_path_info(). But, now that we've * used it and have no other references to these strings, it is time * to deallocate them. */ free_strmap_strings(&opti->paths); strmap_func(&opti->paths, 1); /* * All keys and values in opti->conflicted are a subset of those in * opti->paths. We don't want to deallocate anything twice, so we * don't free the keys and we pass 0 for free_values. */ strmap_func(&opti->conflicted, 0); /* * opti->paths_to_free is similar to opti->paths; we created it with * strdup_strings = 0 to avoid making _another_ copy of the fullpath * but now that we've used it and have no other references to these * strings, it is time to deallocate them. We do so by temporarily * setting strdup_strings to 1. */ opti->paths_to_free.strdup_strings = 1; string_list_clear(&opti->paths_to_free, 0); opti->paths_to_free.strdup_strings = 0; /* Free memory used by various renames maps */ for (i = MERGE_SIDE1; i <= MERGE_SIDE2; ++i) { struct hashmap_iter iter; struct strmap_entry *entry; strset_func(&renames->dirs_removed[i]); strmap_for_each_entry(&renames->dir_rename_count[i], &iter, entry) { struct strintmap *counts = entry->value; strintmap_clear(counts); } strmap_func(&renames->dir_rename_count[i], 1); strmap_func(&renames->dir_renames[i], 0); } if (!reinitialize) { struct hashmap_iter iter; struct strmap_entry *e; /* Release and free each strbuf found in output */ strmap_for_each_entry(&opti->output, &iter, e) { struct strbuf *sb = e->value; strbuf_release(sb); /* * While strictly speaking we don't need to free(sb) * here because we could pass free_values=1 when * calling strmap_clear() on opti->output, that would * require strmap_clear to do another * strmap_for_each_entry() loop, so we just free it * while we're iterating anyway. */ free(sb); } strmap_clear(&opti->output, 0); } } static int err(struct merge_options *opt, const char *err, ...) { va_list params; struct strbuf sb = STRBUF_INIT; strbuf_addstr(&sb, "error: "); va_start(params, err); strbuf_vaddf(&sb, err, params); va_end(params); error("%s", sb.buf); strbuf_release(&sb); return -1; } static void format_commit(struct strbuf *sb, int indent, struct commit *commit) { struct merge_remote_desc *desc; struct pretty_print_context ctx = {0}; ctx.abbrev = DEFAULT_ABBREV; strbuf_addchars(sb, ' ', indent); desc = merge_remote_util(commit); if (desc) { strbuf_addf(sb, "virtual %s\n", desc->name); return; } format_commit_message(commit, "%h %s", sb, &ctx); strbuf_addch(sb, '\n'); } __attribute__((format (printf, 4, 5))) static void path_msg(struct merge_options *opt, const char *path, int omittable_hint, /* skippable under --remerge-diff */ const char *fmt, ...) { va_list ap; struct strbuf *sb = strmap_get(&opt->priv->output, path); if (!sb) { sb = xmalloc(sizeof(*sb)); strbuf_init(sb, 0); strmap_put(&opt->priv->output, path, sb); } va_start(ap, fmt); strbuf_vaddf(sb, fmt, ap); va_end(ap); strbuf_addch(sb, '\n'); } /* add a string to a strbuf, but converting "/" to "_" */ static void add_flattened_path(struct strbuf *out, const char *s) { size_t i = out->len; strbuf_addstr(out, s); for (; i < out->len; i++) if (out->buf[i] == '/') out->buf[i] = '_'; } static char *unique_path(struct strmap *existing_paths, const char *path, const char *branch) { struct strbuf newpath = STRBUF_INIT; int suffix = 0; size_t base_len; strbuf_addf(&newpath, "%s~", path); add_flattened_path(&newpath, branch); base_len = newpath.len; while (strmap_contains(existing_paths, newpath.buf)) { strbuf_setlen(&newpath, base_len); strbuf_addf(&newpath, "_%d", suffix++); } return strbuf_detach(&newpath, NULL); } /*** Function Grouping: functions related to collect_merge_info() ***/ static void setup_path_info(struct merge_options *opt, struct string_list_item *result, const char *current_dir_name, int current_dir_name_len, char *fullpath, /* we'll take over ownership */ struct name_entry *names, struct name_entry *merged_version, unsigned is_null, /* boolean */ unsigned df_conflict, /* boolean */ unsigned filemask, unsigned dirmask, int resolved /* boolean */) { /* result->util is void*, so mi is a convenience typed variable */ struct merged_info *mi; assert(!is_null || resolved); assert(!df_conflict || !resolved); /* df_conflict implies !resolved */ assert(resolved == (merged_version != NULL)); mi = xcalloc(1, resolved ? sizeof(struct merged_info) : sizeof(struct conflict_info)); mi->directory_name = current_dir_name; mi->basename_offset = current_dir_name_len; mi->clean = !!resolved; if (resolved) { mi->result.mode = merged_version->mode; oidcpy(&mi->result.oid, &merged_version->oid); mi->is_null = !!is_null; } else { int i; struct conflict_info *ci; ASSIGN_AND_VERIFY_CI(ci, mi); for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) { ci->pathnames[i] = fullpath; ci->stages[i].mode = names[i].mode; oidcpy(&ci->stages[i].oid, &names[i].oid); } ci->filemask = filemask; ci->dirmask = dirmask; ci->df_conflict = !!df_conflict; if (dirmask) /* * Assume is_null for now, but if we have entries * under the directory then when it is complete in * write_completed_directory() it'll update this. * Also, for D/F conflicts, we have to handle the * directory first, then clear this bit and process * the file to see how it is handled -- that occurs * near the top of process_entry(). */ mi->is_null = 1; } strmap_put(&opt->priv->paths, fullpath, mi); result->string = fullpath; result->util = mi; } static void add_pair(struct merge_options *opt, struct name_entry *names, const char *pathname, unsigned side, unsigned is_add /* if false, is_delete */) { struct diff_filespec *one, *two; struct rename_info *renames = &opt->priv->renames; int names_idx = is_add ? side : 0; one = alloc_filespec(pathname); two = alloc_filespec(pathname); fill_filespec(is_add ? two : one, &names[names_idx].oid, 1, names[names_idx].mode); diff_queue(&renames->pairs[side], one, two); } static void collect_rename_info(struct merge_options *opt, struct name_entry *names, const char *dirname, const char *fullname, unsigned filemask, unsigned dirmask, unsigned match_mask) { struct rename_info *renames = &opt->priv->renames; unsigned side; /* Update dirs_removed, as needed */ if (dirmask == 1 || dirmask == 3 || dirmask == 5) { /* absent_mask = 0x07 - dirmask; sides = absent_mask/2 */ unsigned sides = (0x07 - dirmask)/2; if (sides & 1) strset_add(&renames->dirs_removed[1], fullname); if (sides & 2) strset_add(&renames->dirs_removed[2], fullname); } if (filemask == 0 || filemask == 7) return; for (side = MERGE_SIDE1; side <= MERGE_SIDE2; ++side) { unsigned side_mask = (1 << side); /* Check for deletion on side */ if ((filemask & 1) && !(filemask & side_mask)) add_pair(opt, names, fullname, side, 0 /* delete */); /* Check for addition on side */ if (!(filemask & 1) && (filemask & side_mask)) add_pair(opt, names, fullname, side, 1 /* add */); } } static int collect_merge_info_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info) { /* * n is 3. Always. * common ancestor (mbase) has mask 1, and stored in index 0 of names * head of side 1 (side1) has mask 2, and stored in index 1 of names * head of side 2 (side2) has mask 4, and stored in index 2 of names */ struct merge_options *opt = info->data; struct merge_options_internal *opti = opt->priv; struct string_list_item pi; /* Path Info */ struct conflict_info *ci; /* typed alias to pi.util (which is void*) */ struct name_entry *p; size_t len; char *fullpath; const char *dirname = opti->current_dir_name; unsigned filemask = mask & ~dirmask; unsigned match_mask = 0; /* will be updated below */ unsigned mbase_null = !(mask & 1); unsigned side1_null = !(mask & 2); unsigned side2_null = !(mask & 4); unsigned side1_matches_mbase = (!side1_null && !mbase_null && names[0].mode == names[1].mode && oideq(&names[0].oid, &names[1].oid)); unsigned side2_matches_mbase = (!side2_null && !mbase_null && names[0].mode == names[2].mode && oideq(&names[0].oid, &names[2].oid)); unsigned sides_match = (!side1_null && !side2_null && names[1].mode == names[2].mode && oideq(&names[1].oid, &names[2].oid)); /* * Note: When a path is a file on one side of history and a directory * in another, we have a directory/file conflict. In such cases, if * the conflict doesn't resolve from renames and deletions, then we * always leave directories where they are and move files out of the * way. Thus, while struct conflict_info has a df_conflict field to * track such conflicts, we ignore that field for any directories at * a path and only pay attention to it for files at the given path. * The fact that we leave directories were they are also means that * we do not need to worry about getting additional df_conflict * information propagated from parent directories down to children * (unlike, say traverse_trees_recursive() in unpack-trees.c, which * sets a newinfo.df_conflicts field specifically to propagate it). */ unsigned df_conflict = (filemask != 0) && (dirmask != 0); /* n = 3 is a fundamental assumption. */ if (n != 3) BUG("Called collect_merge_info_callback wrong"); /* * A bunch of sanity checks verifying that traverse_trees() calls * us the way I expect. Could just remove these at some point, * though maybe they are helpful to future code readers. */ assert(mbase_null == is_null_oid(&names[0].oid)); assert(side1_null == is_null_oid(&names[1].oid)); assert(side2_null == is_null_oid(&names[2].oid)); assert(!mbase_null || !side1_null || !side2_null); assert(mask > 0 && mask < 8); /* Determine match_mask */ if (side1_matches_mbase) match_mask = (side2_matches_mbase ? 7 : 3); else if (side2_matches_mbase) match_mask = 5; else if (sides_match) match_mask = 6; /* * Get the name of the relevant filepath, which we'll pass to * setup_path_info() for tracking. */ p = names; while (!p->mode) p++; len = traverse_path_len(info, p->pathlen); /* +1 in both of the following lines to include the NUL byte */ fullpath = xmalloc(len + 1); make_traverse_path(fullpath, len + 1, info, p->path, p->pathlen); /* * If mbase, side1, and side2 all match, we can resolve early. Even * if these are trees, there will be no renames or anything * underneath. */ if (side1_matches_mbase && side2_matches_mbase) { /* mbase, side1, & side2 all match; use mbase as resolution */ setup_path_info(opt, &pi, dirname, info->pathlen, fullpath, names, names+0, mbase_null, 0, filemask, dirmask, 1); return mask; } /* * Gather additional information used in rename detection. */ collect_rename_info(opt, names, dirname, fullpath, filemask, dirmask, match_mask); /* * Record information about the path so we can resolve later in * process_entries. */ setup_path_info(opt, &pi, dirname, info->pathlen, fullpath, names, NULL, 0, df_conflict, filemask, dirmask, 0); ci = pi.util; VERIFY_CI(ci); ci->match_mask = match_mask; /* If dirmask, recurse into subdirectories */ if (dirmask) { struct traverse_info newinfo; struct tree_desc t[3]; void *buf[3] = {NULL, NULL, NULL}; const char *original_dir_name; int i, ret; ci->match_mask &= filemask; newinfo = *info; newinfo.prev = info; newinfo.name = p->path; newinfo.namelen = p->pathlen; newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1); /* * If this directory we are about to recurse into cared about * its parent directory (the current directory) having a D/F * conflict, then we'd propagate the masks in this way: * newinfo.df_conflicts |= (mask & ~dirmask); * But we don't worry about propagating D/F conflicts. (See * comment near setting of local df_conflict variable near * the beginning of this function). */ for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) { if (i == 1 && side1_matches_mbase) t[1] = t[0]; else if (i == 2 && side2_matches_mbase) t[2] = t[0]; else if (i == 2 && sides_match) t[2] = t[1]; else { const struct object_id *oid = NULL; if (dirmask & 1) oid = &names[i].oid; buf[i] = fill_tree_descriptor(opt->repo, t + i, oid); } dirmask >>= 1; } original_dir_name = opti->current_dir_name; opti->current_dir_name = pi.string; ret = traverse_trees(NULL, 3, t, &newinfo); opti->current_dir_name = original_dir_name; for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) free(buf[i]); if (ret < 0) return -1; } return mask; } static int collect_merge_info(struct merge_options *opt, struct tree *merge_base, struct tree *side1, struct tree *side2) { int ret; struct tree_desc t[3]; struct traverse_info info; opt->priv->toplevel_dir = ""; opt->priv->current_dir_name = opt->priv->toplevel_dir; setup_traverse_info(&info, opt->priv->toplevel_dir); info.fn = collect_merge_info_callback; info.data = opt; info.show_all_errors = 1; parse_tree(merge_base); parse_tree(side1); parse_tree(side2); init_tree_desc(t + 0, merge_base->buffer, merge_base->size); init_tree_desc(t + 1, side1->buffer, side1->size); init_tree_desc(t + 2, side2->buffer, side2->size); trace2_region_enter("merge", "traverse_trees", opt->repo); ret = traverse_trees(NULL, 3, t, &info); trace2_region_leave("merge", "traverse_trees", opt->repo); return ret; } /*** Function Grouping: functions related to threeway content merges ***/ static int find_first_merges(struct repository *repo, const char *path, struct commit *a, struct commit *b, struct object_array *result) { int i, j; struct object_array merges = OBJECT_ARRAY_INIT; struct commit *commit; int contains_another; char merged_revision[GIT_MAX_HEXSZ + 2]; const char *rev_args[] = { "rev-list", "--merges", "--ancestry-path", "--all", merged_revision, NULL }; struct rev_info revs; struct setup_revision_opt rev_opts; memset(result, 0, sizeof(struct object_array)); memset(&rev_opts, 0, sizeof(rev_opts)); /* get all revisions that merge commit a */ xsnprintf(merged_revision, sizeof(merged_revision), "^%s", oid_to_hex(&a->object.oid)); repo_init_revisions(repo, &revs, NULL); rev_opts.submodule = path; /* FIXME: can't handle linked worktrees in submodules yet */ revs.single_worktree = path != NULL; setup_revisions(ARRAY_SIZE(rev_args)-1, rev_args, &revs, &rev_opts); /* save all revisions from the above list that contain b */ if (prepare_revision_walk(&revs)) die("revision walk setup failed"); while ((commit = get_revision(&revs)) != NULL) { struct object *o = &(commit->object); if (in_merge_bases(b, commit)) add_object_array(o, NULL, &merges); } reset_revision_walk(); /* Now we've got all merges that contain a and b. Prune all * merges that contain another found merge and save them in * result. */ for (i = 0; i < merges.nr; i++) { struct commit *m1 = (struct commit *) merges.objects[i].item; contains_another = 0; for (j = 0; j < merges.nr; j++) { struct commit *m2 = (struct commit *) merges.objects[j].item; if (i != j && in_merge_bases(m2, m1)) { contains_another = 1; break; } } if (!contains_another) add_object_array(merges.objects[i].item, NULL, result); } object_array_clear(&merges); return result->nr; } static int merge_submodule(struct merge_options *opt, const char *path, const struct object_id *o, const struct object_id *a, const struct object_id *b, struct object_id *result) { struct commit *commit_o, *commit_a, *commit_b; int parent_count; struct object_array merges; struct strbuf sb = STRBUF_INIT; int i; int search = !opt->priv->call_depth; /* store fallback answer in result in case we fail */ oidcpy(result, opt->priv->call_depth ? o : a); /* we can not handle deletion conflicts */ if (is_null_oid(o)) return 0; if (is_null_oid(a)) return 0; if (is_null_oid(b)) return 0; if (add_submodule_odb(path)) { path_msg(opt, path, 0, _("Failed to merge submodule %s (not checked out)"), path); return 0; } if (!(commit_o = lookup_commit_reference(opt->repo, o)) || !(commit_a = lookup_commit_reference(opt->repo, a)) || !(commit_b = lookup_commit_reference(opt->repo, b))) { path_msg(opt, path, 0, _("Failed to merge submodule %s (commits not present)"), path); return 0; } /* check whether both changes are forward */ if (!in_merge_bases(commit_o, commit_a) || !in_merge_bases(commit_o, commit_b)) { path_msg(opt, path, 0, _("Failed to merge submodule %s " "(commits don't follow merge-base)"), path); return 0; } /* Case #1: a is contained in b or vice versa */ if (in_merge_bases(commit_a, commit_b)) { oidcpy(result, b); path_msg(opt, path, 1, _("Note: Fast-forwarding submodule %s to %s"), path, oid_to_hex(b)); return 1; } if (in_merge_bases(commit_b, commit_a)) { oidcpy(result, a); path_msg(opt, path, 1, _("Note: Fast-forwarding submodule %s to %s"), path, oid_to_hex(a)); return 1; } /* * Case #2: There are one or more merges that contain a and b in * the submodule. If there is only one, then present it as a * suggestion to the user, but leave it marked unmerged so the * user needs to confirm the resolution. */ /* Skip the search if makes no sense to the calling context. */ if (!search) return 0; /* find commit which merges them */ parent_count = find_first_merges(opt->repo, path, commit_a, commit_b, &merges); switch (parent_count) { case 0: path_msg(opt, path, 0, _("Failed to merge submodule %s"), path); break; case 1: format_commit(&sb, 4, (struct commit *)merges.objects[0].item); path_msg(opt, path, 0, _("Failed to merge submodule %s, but a possible merge " "resolution exists:\n%s\n"), path, sb.buf); path_msg(opt, path, 1, _("If this is correct simply add it to the index " "for example\n" "by using:\n\n" " git update-index --cacheinfo 160000 %s \"%s\"\n\n" "which will accept this suggestion.\n"), oid_to_hex(&merges.objects[0].item->oid), path); strbuf_release(&sb); break; default: for (i = 0; i < merges.nr; i++) format_commit(&sb, 4, (struct commit *)merges.objects[i].item); path_msg(opt, path, 0, _("Failed to merge submodule %s, but multiple " "possible merges exist:\n%s"), path, sb.buf); strbuf_release(&sb); } object_array_clear(&merges); return 0; } static int merge_3way(struct merge_options *opt, const char *path, const struct object_id *o, const struct object_id *a, const struct object_id *b, const char *pathnames[3], const int extra_marker_size, mmbuffer_t *result_buf) { mmfile_t orig, src1, src2; struct ll_merge_options ll_opts = {0}; char *base, *name1, *name2; int merge_status; ll_opts.renormalize = opt->renormalize; ll_opts.extra_marker_size = extra_marker_size; ll_opts.xdl_opts = opt->xdl_opts; if (opt->priv->call_depth) { ll_opts.virtual_ancestor = 1; ll_opts.variant = 0; } else { switch (opt->recursive_variant) { case MERGE_VARIANT_OURS: ll_opts.variant = XDL_MERGE_FAVOR_OURS; break; case MERGE_VARIANT_THEIRS: ll_opts.variant = XDL_MERGE_FAVOR_THEIRS; break; default: ll_opts.variant = 0; break; } } assert(pathnames[0] && pathnames[1] && pathnames[2] && opt->ancestor); if (pathnames[0] == pathnames[1] && pathnames[1] == pathnames[2]) { base = mkpathdup("%s", opt->ancestor); name1 = mkpathdup("%s", opt->branch1); name2 = mkpathdup("%s", opt->branch2); } else { base = mkpathdup("%s:%s", opt->ancestor, pathnames[0]); name1 = mkpathdup("%s:%s", opt->branch1, pathnames[1]); name2 = mkpathdup("%s:%s", opt->branch2, pathnames[2]); } read_mmblob(&orig, o); read_mmblob(&src1, a); read_mmblob(&src2, b); merge_status = ll_merge(result_buf, path, &orig, base, &src1, name1, &src2, name2, opt->repo->index, &ll_opts); free(base); free(name1); free(name2); free(orig.ptr); free(src1.ptr); free(src2.ptr); return merge_status; } static int handle_content_merge(struct merge_options *opt, const char *path, const struct version_info *o, const struct version_info *a, const struct version_info *b, const char *pathnames[3], const int extra_marker_size, struct version_info *result) { /* * path is the target location where we want to put the file, and * is used to determine any normalization rules in ll_merge. * * The normal case is that path and all entries in pathnames are * identical, though renames can affect which path we got one of * the three blobs to merge on various sides of history. * * extra_marker_size is the amount to extend conflict markers in * ll_merge; this is neeed if we have content merges of content * merges, which happens for example with rename/rename(2to1) and * rename/add conflicts. */ unsigned clean = 1; /* * handle_content_merge() needs both files to be of the same type, i.e. * both files OR both submodules OR both symlinks. Conflicting types * needs to be handled elsewhere. */ assert((S_IFMT & a->mode) == (S_IFMT & b->mode)); /* Merge modes */ if (a->mode == b->mode || a->mode == o->mode) result->mode = b->mode; else { /* must be the 100644/100755 case */ assert(S_ISREG(a->mode)); result->mode = a->mode; clean = (b->mode == o->mode); /* * FIXME: If opt->priv->call_depth && !clean, then we really * should not make result->mode match either a->mode or * b->mode; that causes t6036 "check conflicting mode for * regular file" to fail. It would be best to use some other * mode, but we'll confuse all kinds of stuff if we use one * where S_ISREG(result->mode) isn't true, and if we use * something like 0100666, then tree-walk.c's calls to * canon_mode() will just normalize that to 100644 for us and * thus not solve anything. * * Figure out if there's some kind of way we can work around * this... */ } /* * Trivial oid merge. * * Note: While one might assume that the next four lines would * be unnecessary due to the fact that match_mask is often * setup and already handled, renames don't always take care * of that. */ if (oideq(&a->oid, &b->oid) || oideq(&a->oid, &o->oid)) oidcpy(&result->oid, &b->oid); else if (oideq(&b->oid, &o->oid)) oidcpy(&result->oid, &a->oid); /* Remaining rules depend on file vs. submodule vs. symlink. */ else if (S_ISREG(a->mode)) { mmbuffer_t result_buf; int ret = 0, merge_status; int two_way; /* * If 'o' is different type, treat it as null so we do a * two-way merge. */ two_way = ((S_IFMT & o->mode) != (S_IFMT & a->mode)); merge_status = merge_3way(opt, path, two_way ? &null_oid : &o->oid, &a->oid, &b->oid, pathnames, extra_marker_size, &result_buf); if ((merge_status < 0) || !result_buf.ptr) ret = err(opt, _("Failed to execute internal merge")); if (!ret && write_object_file(result_buf.ptr, result_buf.size, blob_type, &result->oid)) ret = err(opt, _("Unable to add %s to database"), path); free(result_buf.ptr); if (ret) return -1; clean &= (merge_status == 0); path_msg(opt, path, 1, _("Auto-merging %s"), path); } else if (S_ISGITLINK(a->mode)) { int two_way = ((S_IFMT & o->mode) != (S_IFMT & a->mode)); clean = merge_submodule(opt, pathnames[0], two_way ? &null_oid : &o->oid, &a->oid, &b->oid, &result->oid); if (opt->priv->call_depth && two_way && !clean) { result->mode = o->mode; oidcpy(&result->oid, &o->oid); } } else if (S_ISLNK(a->mode)) { if (opt->priv->call_depth) { clean = 0; result->mode = o->mode; oidcpy(&result->oid, &o->oid); } else { switch (opt->recursive_variant) { case MERGE_VARIANT_NORMAL: clean = 0; oidcpy(&result->oid, &a->oid); break; case MERGE_VARIANT_OURS: oidcpy(&result->oid, &a->oid); break; case MERGE_VARIANT_THEIRS: oidcpy(&result->oid, &b->oid); break; } } } else BUG("unsupported object type in the tree: %06o for %s", a->mode, path); return clean; } /*** Function Grouping: functions related to detect_and_process_renames(), *** *** which are split into directory and regular rename detection sections. ***/ /*** Function Grouping: functions related to directory rename detection ***/ struct collision_info { struct string_list source_files; unsigned reported_already:1; }; /* * Return a new string that replaces the beginning portion (which matches * rename_info->key), with rename_info->util.new_dir. In perl-speak: * new_path_name = (old_path =~ s/rename_info->key/rename_info->value/); * NOTE: * Caller must ensure that old_path starts with rename_info->key + '/'. */ static char *apply_dir_rename(struct strmap_entry *rename_info, const char *old_path) { struct strbuf new_path = STRBUF_INIT; const char *old_dir = rename_info->key; const char *new_dir = rename_info->value; int oldlen, newlen, new_dir_len; oldlen = strlen(old_dir); if (*new_dir == '\0') /* * If someone renamed/merged a subdirectory into the root * directory (e.g. 'some/subdir' -> ''), then we want to * avoid returning * '' + '/filename' * as the rename; we need to make old_path + oldlen advance * past the '/' character. */ oldlen++; new_dir_len = strlen(new_dir); newlen = new_dir_len + (strlen(old_path) - oldlen) + 1; strbuf_grow(&new_path, newlen); strbuf_add(&new_path, new_dir, new_dir_len); strbuf_addstr(&new_path, &old_path[oldlen]); return strbuf_detach(&new_path, NULL); } static int path_in_way(struct strmap *paths, const char *path, unsigned side_mask) { struct merged_info *mi = strmap_get(paths, path); struct conflict_info *ci; if (!mi) return 0; INITIALIZE_CI(ci, mi); return mi->clean || (side_mask & (ci->filemask | ci->dirmask)); } /* * See if there is a directory rename for path, and if there are any file * level conflicts on the given side 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, unsigned side_index, struct strmap_entry *rename_info, struct strmap *collisions) { char *new_path = NULL; struct collision_info *c_info; int clean = 1; struct strbuf collision_paths = STRBUF_INIT; /* * entry has the mapping of old directory name to new directory name * that we want to apply to path. */ new_path = apply_dir_rename(rename_info, path); if (!new_path) BUG("Failed to apply directory rename!"); /* * The caller needs to have ensured that it has pre-populated * collisions with all paths that map to new_path. Do a quick check * to ensure that's the case. */ c_info = strmap_get(collisions, new_path); if (c_info == NULL) BUG("c_info is NULL"); /* * Check for one-sided add/add/.../add conflicts, i.e. * where implicit renames from the other side doing * directory rename(s) can affect this side of history * to put multiple paths into the same location. Warn * and bail on directory renames for such paths. */ if (c_info->reported_already) { clean = 0; } else if (path_in_way(&opt->priv->paths, new_path, 1 << side_index)) { c_info->reported_already = 1; strbuf_add_separated_string_list(&collision_paths, ", ", &c_info->source_files); path_msg(opt, new_path, 0, _("CONFLICT (implicit dir rename): Existing file/dir " "at %s in the way of implicit directory rename(s) " "putting the following path(s) there: %s."), new_path, collision_paths.buf); clean = 0; } else if (c_info->source_files.nr > 1) { c_info->reported_already = 1; strbuf_add_separated_string_list(&collision_paths, ", ", &c_info->source_files); path_msg(opt, new_path, 0, _("CONFLICT (implicit dir rename): Cannot map more " "than one path to %s; implicit directory renames " "tried to put these paths there: %s"), new_path, collision_paths.buf); clean = 0; } /* Free memory we no longer need */ strbuf_release(&collision_paths); if (!clean && new_path) { free(new_path); return NULL; } return new_path; } static void dirname_munge(char *filename) { char *slash = strrchr(filename, '/'); if (!slash) slash = filename; *slash = '\0'; } static void increment_count(struct strmap *dir_rename_count, char *old_dir, char *new_dir) { struct strintmap *counts; struct strmap_entry *e; /* Get the {new_dirs -> counts} mapping using old_dir */ e = strmap_get_entry(dir_rename_count, old_dir); if (e) { counts = e->value; } else { counts = xmalloc(sizeof(*counts)); strintmap_init_with_options(counts, 0, NULL, 1); strmap_put(dir_rename_count, old_dir, counts); } /* Increment the count for new_dir */ strintmap_incr(counts, new_dir, 1); } static void update_dir_rename_counts(struct strmap *dir_rename_count, struct strset *dirs_removed, const char *oldname, const char *newname) { char *old_dir = xstrdup(oldname); char *new_dir = xstrdup(newname); char new_dir_first_char = new_dir[0]; int first_time_in_loop = 1; while (1) { dirname_munge(old_dir); dirname_munge(new_dir); /* * When renaming * "a/b/c/d/e/foo.c" -> "a/b/some/thing/else/e/foo.c" * then this suggests that both * a/b/c/d/e/ => a/b/some/thing/else/e/ * a/b/c/d/ => a/b/some/thing/else/ * so we want to increment counters for both. We do NOT, * however, also want to suggest that there was the following * rename: * a/b/c/ => a/b/some/thing/ * so we need to quit at that point. * * Note the when first_time_in_loop, we only strip off the * basename, and we don't care if that's different. */ if (!first_time_in_loop) { char *old_sub_dir = strchr(old_dir, '\0')+1; char *new_sub_dir = strchr(new_dir, '\0')+1; if (!*new_dir) { /* * Special case when renaming to root directory, * i.e. when new_dir == "". In this case, we had * something like * a/b/subdir => subdir * and so dirname_munge() sets things up so that * old_dir = "a/b\0subdir\0" * new_dir = "\0ubdir\0" * We didn't have a '/' to overwrite a '\0' onto * in new_dir, so we have to compare differently. */ if (new_dir_first_char != old_sub_dir[0] || strcmp(old_sub_dir+1, new_sub_dir)) break; } else { if (strcmp(old_sub_dir, new_sub_dir)) break; } } if (strset_contains(dirs_removed, old_dir)) increment_count(dir_rename_count, old_dir, new_dir); else break; /* If we hit toplevel directory ("") for old or new dir, quit */ if (!*old_dir || !*new_dir) break; first_time_in_loop = 0; } /* Free resources we don't need anymore */ free(old_dir); free(new_dir); } static void compute_rename_counts(struct diff_queue_struct *pairs, struct strmap *dir_rename_count, struct strset *dirs_removed) { int i; for (i = 0; i < pairs->nr; ++i) { struct diff_filepair *pair = pairs->queue[i]; /* File not part of directory rename if it wasn't renamed */ if (pair->status != 'R') continue; /* * Make dir_rename_count contain a map of a map: * old_directory -> {new_directory -> count} * In other words, for every pair look at the directories for * the old filename and the new filename and count how many * times that pairing occurs. */ update_dir_rename_counts(dir_rename_count, dirs_removed, pair->one->path, pair->two->path); } } static void get_provisional_directory_renames(struct merge_options *opt, unsigned side, int *clean) { struct hashmap_iter iter; struct strmap_entry *entry; struct rename_info *renames = &opt->priv->renames; compute_rename_counts(&renames->pairs[side], &renames->dir_rename_count[side], &renames->dirs_removed[side]); /* * Collapse * dir_rename_count: old_directory -> {new_directory -> count} * down to * dir_renames: old_directory -> best_new_directory * where best_new_directory is the one with the unique highest count. */ strmap_for_each_entry(&renames->dir_rename_count[side], &iter, entry) { const char *source_dir = entry->key; struct strintmap *counts = entry->value; struct hashmap_iter count_iter; struct strmap_entry *count_entry; int max = 0; int bad_max = 0; const char *best = NULL; strintmap_for_each_entry(counts, &count_iter, count_entry) { const char *target_dir = count_entry->key; intptr_t count = (intptr_t)count_entry->value; if (count == max) bad_max = max; else if (count > max) { max = count; best = target_dir; } } if (bad_max == max) { path_msg(opt, source_dir, 0, _("CONFLICT (directory rename split): " "Unclear where to rename %s to; it was " "renamed to multiple other directories, with " "no destination getting a majority of the " "files."), source_dir); /* * We should mark this as unclean IF something attempts * to use this rename. We do not yet have the logic * in place to detect if this directory rename is being * used, and optimizations that reduce the number of * renames cause this to falsely trigger. For now, * just disable it, causing t6423 testcase 2a to break. * We'll later fix the detection, and when we do we * will re-enable setting *clean to 0 (and thereby fix * t6423 testcase 2a). */ /* *clean = 0; */ } else { strmap_put(&renames->dir_renames[side], source_dir, (void*)best); } } } static void handle_directory_level_conflicts(struct merge_options *opt) { struct hashmap_iter iter; struct strmap_entry *entry; struct string_list duplicated = STRING_LIST_INIT_NODUP; struct rename_info *renames = &opt->priv->renames; struct strmap *side1_dir_renames = &renames->dir_renames[MERGE_SIDE1]; struct strmap *side2_dir_renames = &renames->dir_renames[MERGE_SIDE2]; int i; strmap_for_each_entry(side1_dir_renames, &iter, entry) { if (strmap_contains(side2_dir_renames, entry->key)) string_list_append(&duplicated, entry->key); } for (i = 0; i < duplicated.nr; i++) { strmap_remove(side1_dir_renames, duplicated.items[i].string, 0); strmap_remove(side2_dir_renames, duplicated.items[i].string, 0); } string_list_clear(&duplicated, 0); } static struct strmap_entry *check_dir_renamed(const char *path, struct strmap *dir_renames) { char *temp = xstrdup(path); char *end; struct strmap_entry *e = NULL; while ((end = strrchr(temp, '/'))) { *end = '\0'; e = strmap_get_entry(dir_renames, temp); if (e) break; } free(temp); return e; } static void compute_collisions(struct strmap *collisions, struct strmap *dir_renames, struct diff_queue_struct *pairs) { int i; strmap_init_with_options(collisions, NULL, 0); if (strmap_empty(dir_renames)) return; /* * Multiple files can be mapped to the same path due to directory * renames done by the other side of history. Since that other * side of history could have merged multiple directories into one, * if our side of history added the same file basename to each of * those directories, then all N of them would get implicitly * renamed by the directory rename detection into the same path, * and we'd get an add/add/.../add conflict, and all those adds * from *this* side of history. This is not representable in the * index, and users aren't going to easily be able to make sense of * it. So we need to provide a good warning about what's * happening, and fall back to no-directory-rename detection * behavior for those paths. * * See testcases 9e and all of section 5 from t6043 for examples. */ for (i = 0; i < pairs->nr; ++i) { struct strmap_entry *rename_info; struct collision_info *collision_info; char *new_path; struct diff_filepair *pair = pairs->queue[i]; if (pair->status != 'A' && pair->status != 'R') continue; rename_info = check_dir_renamed(pair->two->path, dir_renames); if (!rename_info) continue; new_path = apply_dir_rename(rename_info, pair->two->path); assert(new_path); collision_info = strmap_get(collisions, new_path); if (collision_info) { free(new_path); } else { CALLOC_ARRAY(collision_info, 1); string_list_init(&collision_info->source_files, 0); strmap_put(collisions, new_path, collision_info); } string_list_insert(&collision_info->source_files, pair->two->path); } } static char *check_for_directory_rename(struct merge_options *opt, const char *path, unsigned side_index, struct strmap *dir_renames, struct strmap *dir_rename_exclusions, struct strmap *collisions, int *clean_merge) { char *new_path = NULL; struct strmap_entry *rename_info; struct strmap_entry *otherinfo = NULL; const char *new_dir; if (strmap_empty(dir_renames)) return new_path; rename_info = check_dir_renamed(path, dir_renames); if (!rename_info) return new_path; /* old_dir = rename_info->key; */ new_dir = rename_info->value; /* * This next part is a little weird. We do not want to do an * implicit rename into a directory we renamed on our side, because * that will result in a spurious rename/rename(1to2) conflict. An * example: * Base commit: dumbdir/afile, otherdir/bfile * Side 1: smrtdir/afile, otherdir/bfile * Side 2: dumbdir/afile, dumbdir/bfile * Here, while working on Side 1, we could notice that otherdir was * renamed/merged to dumbdir, and change the diff_filepair for * otherdir/bfile into a rename into dumbdir/bfile. However, Side * 2 will notice the rename from dumbdir to smrtdir, and do the * transitive rename to move it from dumbdir/bfile to * smrtdir/bfile. That gives us bfile in dumbdir vs being in * smrtdir, a rename/rename(1to2) conflict. We really just want * the file to end up in smrtdir. And the way to achieve that is * to not let Side1 do the rename to dumbdir, since we know that is * the source of one of our directory renames. * * That's why otherinfo and dir_rename_exclusions is here. * * As it turns out, this also prevents N-way transient rename * confusion; See testcases 9c and 9d of t6043. */ otherinfo = strmap_get_entry(dir_rename_exclusions, new_dir); if (otherinfo) { path_msg(opt, rename_info->key, 1, _("WARNING: Avoiding applying %s -> %s rename " "to %s, because %s itself was renamed."), rename_info->key, new_dir, path, new_dir); return NULL; } new_path = handle_path_level_conflicts(opt, path, side_index, rename_info, collisions); *clean_merge &= (new_path != NULL); return new_path; } static void apply_directory_rename_modifications(struct merge_options *opt, struct diff_filepair *pair, char *new_path) { /* * The basic idea is to get the conflict_info from opt->priv->paths * at old path, and insert it into new_path; basically just this: * ci = strmap_get(&opt->priv->paths, old_path); * strmap_remove(&opt->priv->paths, old_path, 0); * strmap_put(&opt->priv->paths, new_path, ci); * However, there are some factors complicating this: * - opt->priv->paths may already have an entry at new_path * - Each ci tracks its containing directory, so we need to * update that * - If another ci has the same containing directory, then * the two char*'s MUST point to the same location. See the * comment in struct merged_info. strcmp equality is not * enough; we need pointer equality. * - opt->priv->paths must hold the parent directories of any * entries that are added. So, if this directory rename * causes entirely new directories, we must recursively add * parent directories. * - For each parent directory added to opt->priv->paths, we * also need to get its parent directory stored in its * conflict_info->merged.directory_name with all the same * requirements about pointer equality. */ struct string_list dirs_to_insert = STRING_LIST_INIT_NODUP; struct conflict_info *ci, *new_ci; struct strmap_entry *entry; const char *branch_with_new_path, *branch_with_dir_rename; const char *old_path = pair->two->path; const char *parent_name; const char *cur_path; int i, len; entry = strmap_get_entry(&opt->priv->paths, old_path); old_path = entry->key; ci = entry->value; VERIFY_CI(ci); /* Find parent directories missing from opt->priv->paths */ cur_path = new_path; while (1) { /* Find the parent directory of cur_path */ char *last_slash = strrchr(cur_path, '/'); if (last_slash) { parent_name = xstrndup(cur_path, last_slash - cur_path); } else { parent_name = opt->priv->toplevel_dir; break; } /* Look it up in opt->priv->paths */ entry = strmap_get_entry(&opt->priv->paths, parent_name); if (entry) { free((char*)parent_name); parent_name = entry->key; /* reuse known pointer */ break; } /* Record this is one of the directories we need to insert */ string_list_append(&dirs_to_insert, parent_name); cur_path = parent_name; } /* Traverse dirs_to_insert and insert them into opt->priv->paths */ for (i = dirs_to_insert.nr-1; i >= 0; --i) { struct conflict_info *dir_ci; char *cur_dir = dirs_to_insert.items[i].string; CALLOC_ARRAY(dir_ci, 1); dir_ci->merged.directory_name = parent_name; len = strlen(parent_name); /* len+1 because of trailing '/' character */ dir_ci->merged.basename_offset = (len > 0 ? len+1 : len); dir_ci->dirmask = ci->filemask; strmap_put(&opt->priv->paths, cur_dir, dir_ci); parent_name = cur_dir; } /* * We are removing old_path from opt->priv->paths. old_path also will * eventually need to be freed, but it may still be used by e.g. * ci->pathnames. So, store it in another string-list for now. */ string_list_append(&opt->priv->paths_to_free, old_path); assert(ci->filemask == 2 || ci->filemask == 4); assert(ci->dirmask == 0); strmap_remove(&opt->priv->paths, old_path, 0); branch_with_new_path = (ci->filemask == 2) ? opt->branch1 : opt->branch2; branch_with_dir_rename = (ci->filemask == 2) ? opt->branch2 : opt->branch1; /* Now, finally update ci and stick it into opt->priv->paths */ ci->merged.directory_name = parent_name; len = strlen(parent_name); ci->merged.basename_offset = (len > 0 ? len+1 : len); new_ci = strmap_get(&opt->priv->paths, new_path); if (!new_ci) { /* Place ci back into opt->priv->paths, but at new_path */ strmap_put(&opt->priv->paths, new_path, ci); } else { int index; /* A few sanity checks */ VERIFY_CI(new_ci); assert(ci->filemask == 2 || ci->filemask == 4); assert((new_ci->filemask & ci->filemask) == 0); assert(!new_ci->merged.clean); /* Copy stuff from ci into new_ci */ new_ci->filemask |= ci->filemask; if (new_ci->dirmask) new_ci->df_conflict = 1; index = (ci->filemask >> 1); new_ci->pathnames[index] = ci->pathnames[index]; new_ci->stages[index].mode = ci->stages[index].mode; oidcpy(&new_ci->stages[index].oid, &ci->stages[index].oid); free(ci); ci = new_ci; } if (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE) { /* Notify user of updated path */ if (pair->status == 'A') path_msg(opt, new_path, 1, _("Path updated: %s added in %s inside a " "directory that was renamed in %s; moving " "it to %s."), old_path, branch_with_new_path, branch_with_dir_rename, new_path); else path_msg(opt, new_path, 1, _("Path updated: %s renamed to %s in %s, " "inside a directory that was renamed in %s; " "moving it to %s."), pair->one->path, old_path, branch_with_new_path, branch_with_dir_rename, new_path); } else { /* * opt->detect_directory_renames has the value * MERGE_DIRECTORY_RENAMES_CONFLICT, so mark these as conflicts. */ ci->path_conflict = 1; if (pair->status == 'A') path_msg(opt, new_path, 0, _("CONFLICT (file location): %s added in %s " "inside a directory that was renamed in %s, " "suggesting it should perhaps be moved to " "%s."), old_path, branch_with_new_path, branch_with_dir_rename, new_path); else path_msg(opt, new_path, 0, _("CONFLICT (file location): %s renamed to %s " "in %s, inside a directory that was renamed " "in %s, suggesting it should perhaps be " "moved to %s."), pair->one->path, old_path, branch_with_new_path, branch_with_dir_rename, new_path); } /* * Finally, record the new location. */ pair->two->path = new_path; } /*** Function Grouping: functions related to regular rename detection ***/ static int process_renames(struct merge_options *opt, struct diff_queue_struct *renames) { int clean_merge = 1, i; for (i = 0; i < renames->nr; ++i) { const char *oldpath = NULL, *newpath; struct diff_filepair *pair = renames->queue[i]; struct conflict_info *oldinfo = NULL, *newinfo = NULL; struct strmap_entry *old_ent, *new_ent; unsigned int old_sidemask; int target_index, other_source_index; int source_deleted, collision, type_changed; const char *rename_branch = NULL, *delete_branch = NULL; old_ent = strmap_get_entry(&opt->priv->paths, pair->one->path); new_ent = strmap_get_entry(&opt->priv->paths, pair->two->path); if (old_ent) { oldpath = old_ent->key; oldinfo = old_ent->value; } newpath = pair->two->path; if (new_ent) { newpath = new_ent->key; newinfo = new_ent->value; } /* * If pair->one->path isn't in opt->priv->paths, that means * that either directory rename detection removed that * path, or a parent directory of oldpath was resolved and * we don't even need the rename; in either case, we can * skip it. If oldinfo->merged.clean, then the other side * of history had no changes to oldpath and we don't need * the rename and can skip it. */ if (!oldinfo || oldinfo->merged.clean) continue; /* * diff_filepairs have copies of pathnames, thus we have to * use standard 'strcmp()' (negated) instead of '=='. */ if (i + 1 < renames->nr && !strcmp(oldpath, renames->queue[i+1]->one->path)) { /* Handle rename/rename(1to2) or rename/rename(1to1) */ const char *pathnames[3]; struct version_info merged; struct conflict_info *base, *side1, *side2; unsigned was_binary_blob = 0; pathnames[0] = oldpath; pathnames[1] = newpath; pathnames[2] = renames->queue[i+1]->two->path; base = strmap_get(&opt->priv->paths, pathnames[0]); side1 = strmap_get(&opt->priv->paths, pathnames[1]); side2 = strmap_get(&opt->priv->paths, pathnames[2]); VERIFY_CI(base); VERIFY_CI(side1); VERIFY_CI(side2); if (!strcmp(pathnames[1], pathnames[2])) { /* Both sides renamed the same way */ assert(side1 == side2); memcpy(&side1->stages[0], &base->stages[0], sizeof(merged)); side1->filemask |= (1 << MERGE_BASE); /* Mark base as resolved by removal */ base->merged.is_null = 1; base->merged.clean = 1; /* We handled both renames, i.e. i+1 handled */ i++; /* Move to next rename */ continue; } /* This is a rename/rename(1to2) */ clean_merge = handle_content_merge(opt, pair->one->path, &base->stages[0], &side1->stages[1], &side2->stages[2], pathnames, 1 + 2 * opt->priv->call_depth, &merged); if (!clean_merge && merged.mode == side1->stages[1].mode && oideq(&merged.oid, &side1->stages[1].oid)) was_binary_blob = 1; memcpy(&side1->stages[1], &merged, sizeof(merged)); if (was_binary_blob) { /* * Getting here means we were attempting to * merge a binary blob. * * Since we can't merge binaries, * handle_content_merge() just takes one * side. But we don't want to copy the * contents of one side to both paths. We * used the contents of side1 above for * side1->stages, let's use the contents of * side2 for side2->stages below. */ oidcpy(&merged.oid, &side2->stages[2].oid); merged.mode = side2->stages[2].mode; } memcpy(&side2->stages[2], &merged, sizeof(merged)); side1->path_conflict = 1; side2->path_conflict = 1; /* * TODO: For renames we normally remove the path at the * old name. It would thus seem consistent to do the * same for rename/rename(1to2) cases, but we haven't * done so traditionally and a number of the regression * tests now encode an expectation that the file is * left there at stage 1. If we ever decide to change * this, add the following two lines here: * base->merged.is_null = 1; * base->merged.clean = 1; * and remove the setting of base->path_conflict to 1. */ base->path_conflict = 1; path_msg(opt, oldpath, 0, _("CONFLICT (rename/rename): %s renamed to " "%s in %s and to %s in %s."), pathnames[0], pathnames[1], opt->branch1, pathnames[2], opt->branch2); i++; /* We handled both renames, i.e. i+1 handled */ continue; } VERIFY_CI(oldinfo); VERIFY_CI(newinfo); target_index = pair->score; /* from collect_renames() */ assert(target_index == 1 || target_index == 2); other_source_index = 3 - target_index; old_sidemask = (1 << other_source_index); /* 2 or 4 */ source_deleted = (oldinfo->filemask == 1); collision = ((newinfo->filemask & old_sidemask) != 0); type_changed = !source_deleted && (S_ISREG(oldinfo->stages[other_source_index].mode) != S_ISREG(newinfo->stages[target_index].mode)); if (type_changed && collision) { /* * special handling so later blocks can handle this... * * if type_changed && collision are both true, then this * was really a double rename, but one side wasn't * detected due to lack of break detection. I.e. * something like * orig: has normal file 'foo' * side1: renames 'foo' to 'bar', adds 'foo' symlink * side2: renames 'foo' to 'bar' * In this case, the foo->bar rename on side1 won't be * detected because the new symlink named 'foo' is * there and we don't do break detection. But we detect * this here because we don't want to merge the content * of the foo symlink with the foo->bar file, so we * have some logic to handle this special case. The * easiest way to do that is make 'bar' on side1 not * be considered a colliding file but the other part * of a normal rename. If the file is very different, * well we're going to get content merge conflicts * anyway so it doesn't hurt. And if the colliding * file also has a different type, that'll be handled * by the content merge logic in process_entry() too. * * See also t6430, 'rename vs. rename/symlink' */ collision = 0; } if (source_deleted) { if (target_index == 1) { rename_branch = opt->branch1; delete_branch = opt->branch2; } else { rename_branch = opt->branch2; delete_branch = opt->branch1; } } assert(source_deleted || oldinfo->filemask & old_sidemask); /* Need to check for special types of rename conflicts... */ if (collision && !source_deleted) { /* collision: rename/add or rename/rename(2to1) */ const char *pathnames[3]; struct version_info merged; struct conflict_info *base, *side1, *side2; unsigned clean; pathnames[0] = oldpath; pathnames[other_source_index] = oldpath; pathnames[target_index] = newpath; base = strmap_get(&opt->priv->paths, pathnames[0]); side1 = strmap_get(&opt->priv->paths, pathnames[1]); side2 = strmap_get(&opt->priv->paths, pathnames[2]); VERIFY_CI(base); VERIFY_CI(side1); VERIFY_CI(side2); clean = handle_content_merge(opt, pair->one->path, &base->stages[0], &side1->stages[1], &side2->stages[2], pathnames, 1 + 2 * opt->priv->call_depth, &merged); memcpy(&newinfo->stages[target_index], &merged, sizeof(merged)); if (!clean) { path_msg(opt, newpath, 0, _("CONFLICT (rename involved in " "collision): rename of %s -> %s has " "content conflicts AND collides " "with another path; this may result " "in nested conflict markers."), oldpath, newpath); } } else if (collision && source_deleted) { /* * rename/add/delete or rename/rename(2to1)/delete: * since oldpath was deleted on the side that didn't * do the rename, there's not much of a content merge * we can do for the rename. oldinfo->merged.is_null * was already set, so we just leave things as-is so * they look like an add/add conflict. */ newinfo->path_conflict = 1; path_msg(opt, newpath, 0, _("CONFLICT (rename/delete): %s renamed " "to %s in %s, but deleted in %s."), oldpath, newpath, rename_branch, delete_branch); } else { /* * a few different cases...start by copying the * existing stage(s) from oldinfo over the newinfo * and update the pathname(s). */ memcpy(&newinfo->stages[0], &oldinfo->stages[0], sizeof(newinfo->stages[0])); newinfo->filemask |= (1 << MERGE_BASE); newinfo->pathnames[0] = oldpath; if (type_changed) { /* rename v