diff options
| -rw-r--r-- | diffcore-rename.c | 209 | ||||
| -rw-r--r-- | merge-ort.c | 671 | ||||
| -rwxr-xr-x | t/t4058-diff-duplicates.sh | 114 |
3 files changed, 845 insertions, 149 deletions
diff --git a/diffcore-rename.c b/diffcore-rename.c index d367a6d244..90db9ebd6d 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -9,63 +9,36 @@ #include "hashmap.h" #include "progress.h" #include "promisor-remote.h" +#include "strmap.h" /* Table of rename/copy destinations */ static struct diff_rename_dst { - struct diff_filespec *two; - struct diff_filepair *pair; + struct diff_filepair *p; + struct diff_filespec *filespec_to_free; + int is_rename; /* false -> just a create; true -> rename or copy */ } *rename_dst; static int rename_dst_nr, rename_dst_alloc; +/* Mapping from break source pathname to break destination index */ +static struct strintmap *break_idx = NULL; -static int find_rename_dst(struct diff_filespec *two) -{ - int first, last; - - first = 0; - last = rename_dst_nr; - while (last > first) { - int next = first + ((last - first) >> 1); - struct diff_rename_dst *dst = &(rename_dst[next]); - int cmp = strcmp(two->path, dst->two->path); - if (!cmp) - return next; - if (cmp < 0) { - last = next; - continue; - } - first = next+1; - } - return -first - 1; -} - -static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two) +static struct diff_rename_dst *locate_rename_dst(struct diff_filepair *p) { - int ofs = find_rename_dst(two); - return ofs < 0 ? NULL : &rename_dst[ofs]; + /* Lookup by p->ONE->path */ + int idx = break_idx ? strintmap_get(break_idx, p->one->path) : -1; + return (idx == -1) ? NULL : &rename_dst[idx]; } /* * Returns 0 on success, -1 if we found a duplicate. */ -static int add_rename_dst(struct diff_filespec *two) +static int add_rename_dst(struct diff_filepair *p) { - int first = find_rename_dst(two); - - if (first >= 0) - return -1; - first = -first - 1; - - /* insert to make it at "first" */ ALLOC_GROW(rename_dst, rename_dst_nr + 1, rename_dst_alloc); + rename_dst[rename_dst_nr].p = p; + rename_dst[rename_dst_nr].filespec_to_free = NULL; + rename_dst[rename_dst_nr].is_rename = 0; rename_dst_nr++; - if (first < rename_dst_nr) - MOVE_ARRAY(rename_dst + first + 1, rename_dst + first, - rename_dst_nr - first - 1); - rename_dst[first].two = alloc_filespec(two->path); - fill_filespec(rename_dst[first].two, &two->oid, two->oid_valid, - two->mode); - rename_dst[first].pair = NULL; return 0; } @@ -76,36 +49,20 @@ static struct diff_rename_src { } *rename_src; static int rename_src_nr, rename_src_alloc; -static struct diff_rename_src *register_rename_src(struct diff_filepair *p) +static void register_rename_src(struct diff_filepair *p) { - int first, last; - struct diff_filespec *one = p->one; - unsigned short score = p->score; - - first = 0; - last = rename_src_nr; - while (last > first) { - int next = first + ((last - first) >> 1); - struct diff_rename_src *src = &(rename_src[next]); - int cmp = strcmp(one->path, src->p->one->path); - if (!cmp) - return src; - if (cmp < 0) { - last = next; - continue; + if (p->broken_pair) { + if (!break_idx) { + break_idx = xmalloc(sizeof(*break_idx)); + strintmap_init(break_idx, -1); } - first = next+1; + strintmap_set(break_idx, p->one->path, rename_dst_nr); } - /* insert to make it at "first" */ ALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc); + rename_src[rename_src_nr].p = p; + rename_src[rename_src_nr].score = p->score; rename_src_nr++; - if (first < rename_src_nr) - MOVE_ARRAY(rename_src + first + 1, rename_src + first, - rename_src_nr - first - 1); - rename_src[first].p = p; - rename_src[first].score = score; - return &(rename_src[first]); } static int basename_same(struct diff_filespec *src, struct diff_filespec *dst) @@ -141,14 +98,14 @@ static void prefetch(void *prefetch_options) struct oid_array to_fetch = OID_ARRAY_INIT; for (i = 0; i < rename_dst_nr; i++) { - if (rename_dst[i].pair) + if (rename_dst[i].p->renamed_pair) /* * The loop in diffcore_rename() will not need these * blobs, so skip prefetching. */ continue; /* already found exact match */ diff_add_if_missing(options->repo, &to_fetch, - rename_dst[i].two); + rename_dst[i].p->two); } for (i = 0; i < rename_src_nr; i++) { if (options->skip_unmodified && @@ -258,26 +215,24 @@ static int estimate_similarity(struct repository *r, static void record_rename_pair(int dst_index, int src_index, int score) { - struct diff_filespec *src, *dst; - struct diff_filepair *dp; + struct diff_filepair *src = rename_src[src_index].p; + struct diff_filepair *dst = rename_dst[dst_index].p; - if (rename_dst[dst_index].pair) + if (dst->renamed_pair) die("internal error: dst already matched."); - src = rename_src[src_index].p->one; - src->rename_used++; - src->count++; + src->one->rename_used++; + src->one->count++; - dst = rename_dst[dst_index].two; - dst->count++; + rename_dst[dst_index].filespec_to_free = dst->one; + rename_dst[dst_index].is_rename = 1; - dp = diff_queue(NULL, src, dst); - dp->renamed_pair = 1; - if (!strcmp(src->path, dst->path)) - dp->score = rename_src[src_index].score; + dst->one = src->one; + dst->renamed_pair = 1; + if (!strcmp(dst->one->path, dst->two->path)) + dst->score = rename_src[src_index].score; else - dp->score = score; - rename_dst[dst_index].pair = dp; + dst->score = score; } /* @@ -323,7 +278,7 @@ static int find_identical_files(struct hashmap *srcs, struct diff_options *options) { int renames = 0; - struct diff_filespec *target = rename_dst[dst_index].two; + struct diff_filespec *target = rename_dst[dst_index].p->two; struct file_similarity *p, *best = NULL; int i = 100, best_score = -1; unsigned int hash = hash_filespec(options->repo, target); @@ -434,12 +389,11 @@ static void record_if_better(struct diff_score m[], struct diff_score *o) * 1 if we need to disable inexact rename detection; * 2 if we would be under the limit if we were given -C instead of -C -C. */ -static int too_many_rename_candidates(int num_create, +static int too_many_rename_candidates(int num_destinations, int num_sources, struct diff_options *options) { int rename_limit = options->rename_limit; - int num_src = rename_src_nr; - int i; + int i, limited_sources; options->needed_rename_limit = 0; @@ -447,31 +401,34 @@ static int too_many_rename_candidates(int num_create, * This basically does a test for the rename matrix not * growing larger than a "rename_limit" square matrix, ie: * - * num_create * num_src > rename_limit * rename_limit + * num_destinations * num_sources > rename_limit * rename_limit + * + * We use st_mult() to check overflow conditions; in the + * exceptional circumstance that size_t isn't large enough to hold + * the multiplication, the system won't be able to allocate enough + * memory for the matrix anyway. */ if (rename_limit <= 0) rename_limit = 32767; - if ((num_create <= rename_limit || num_src <= rename_limit) && - ((uint64_t)num_create * (uint64_t)num_src - <= (uint64_t)rename_limit * (uint64_t)rename_limit)) + if (st_mult(num_destinations, num_sources) + <= st_mult(rename_limit, rename_limit)) return 0; options->needed_rename_limit = - num_src > num_create ? num_src : num_create; + num_sources > num_destinations ? num_sources : num_destinations; /* Are we running under -C -C? */ if (!options->flags.find_copies_harder) return 1; /* Would we bust the limit if we were running under -C? */ - for (num_src = i = 0; i < rename_src_nr; i++) { + for (limited_sources = i = 0; i < num_sources; i++) { if (diff_unmodified_pair(rename_src[i].p)) continue; - num_src++; + limited_sources++; } - if ((num_create <= rename_limit || num_src <= rename_limit) && - ((uint64_t)num_create * (uint64_t)num_src - <= (uint64_t)rename_limit * (uint64_t)rename_limit)) + if (st_mult(num_destinations, limited_sources) + <= st_mult(rename_limit, rename_limit)) return 2; return 1; } @@ -487,7 +444,7 @@ static int find_renames(struct diff_score *mx, int dst_cnt, int minimum_score, i (mx[i].score < minimum_score)) break; /* there is no more usable pair. */ dst = &rename_dst[mx[i].dst]; - if (dst->pair) + if (dst->is_rename) continue; /* already done, either exact or fuzzy. */ if (!copies && rename_src[mx[i].src].p->one->rename_used) continue; @@ -505,7 +462,7 @@ void diffcore_rename(struct diff_options *options) struct diff_queue_struct outq; struct diff_score *mx; int i, j, rename_count, skip_unmodified = 0; - int num_create, dst_cnt; + int num_destinations, dst_cnt; struct progress *progress = NULL; if (!minimum_score) @@ -522,7 +479,7 @@ void diffcore_rename(struct diff_options *options) else if (!options->flags.rename_empty && is_empty_blob_oid(&p->two->oid)) continue; - else if (add_rename_dst(p->two) < 0) { + else if (add_rename_dst(p) < 0) { warning("skipping rename detection, detected" " duplicate destination '%s'", p->two->path); @@ -570,13 +527,14 @@ void diffcore_rename(struct diff_options *options) * Calculate how many renames are left (but all the source * files still remain as options for rename/copies!) */ - num_create = (rename_dst_nr - rename_count); + num_destinations = (rename_dst_nr - rename_count); /* All done? */ - if (!num_create) + if (!num_destinations) goto cleanup; - switch (too_many_rename_candidates(num_create, options)) { + switch (too_many_rename_candidates(num_destinations, rename_src_nr, + options)) { case 1: goto cleanup; case 2: @@ -590,15 +548,16 @@ void diffcore_rename(struct diff_options *options) if (options->show_rename_progress) { progress = start_delayed_progress( _("Performing inexact rename detection"), - (uint64_t)rename_dst_nr * (uint64_t)rename_src_nr); + (uint64_t)num_destinations * (uint64_t)rename_src_nr); } - mx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_create), sizeof(*mx)); + mx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_destinations), + sizeof(*mx)); for (dst_cnt = i = 0; i < rename_dst_nr; i++) { - struct diff_filespec *two = rename_dst[i].two; + struct diff_filespec *two = rename_dst[i].p->two; struct diff_score *m; - if (rename_dst[i].pair) + if (rename_dst[i].is_rename) continue; /* dealt with exact match already. */ m = &mx[dst_cnt * NUM_CANDIDATE_PER_DST]; @@ -629,7 +588,8 @@ void diffcore_rename(struct diff_options *options) diff_free_filespec_blob(two); } dst_cnt++; - display_progress(progress, (uint64_t)(i+1)*(uint64_t)rename_src_nr); + display_progress(progress, + (uint64_t)dst_cnt * (uint64_t)rename_src_nr); } stop_progress(&progress); @@ -654,22 +614,8 @@ void diffcore_rename(struct diff_options *options) diff_q(&outq, p); } else if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) { - /* - * Creation - * - * We would output this create record if it has - * not been turned into a rename/copy already. - */ - struct diff_rename_dst *dst = locate_rename_dst(p->two); - if (dst && dst->pair) { - diff_q(&outq, dst->pair); - pair_to_free = p; - } - else - /* no matching rename/copy source, so - * record this as a creation. - */ - diff_q(&outq, p); + /* Creation */ + diff_q(&outq, p); } else if (DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) { /* @@ -690,8 +636,10 @@ void diffcore_rename(struct diff_options *options) */ if (DIFF_PAIR_BROKEN(p)) { /* broken delete */ - struct diff_rename_dst *dst = locate_rename_dst(p->one); - if (dst && dst->pair) + struct diff_rename_dst *dst = locate_rename_dst(p); + if (!dst) + BUG("tracking failed somehow; failed to find associated dst for broken pair"); + if (dst->is_rename) /* counterpart is now rename/copy */ pair_to_free = p; } @@ -701,16 +649,14 @@ void diffcore_rename(struct diff_options *options) pair_to_free = p; } - if (pair_to_free) - ; - else + if (!pair_to_free) diff_q(&outq, p); } else if (!diff_unmodified_pair(p)) /* all the usual ones need to be kept */ diff_q(&outq, p); else - /* no need to keep unmodified pairs */ + /* no need to keep unmodified pairs; FIXME: remove earlier? */ pair_to_free = p; if (pair_to_free) @@ -723,11 +669,16 @@ void diffcore_rename(struct diff_options *options) diff_debug_queue("done collapsing", q); for (i = 0; i < rename_dst_nr; i++) - free_filespec(rename_dst[i].two); + if (rename_dst[i].filespec_to_free) + free_filespec(rename_dst[i].filespec_to_free); FREE_AND_NULL(rename_dst); rename_dst_nr = rename_dst_alloc = 0; FREE_AND_NULL(rename_src); rename_src_nr = rename_src_alloc = 0; + if (break_idx) { + strintmap_clear(break_idx); + FREE_AND_NULL(break_idx); + } return; } diff --git a/merge-ort.c b/merge-ort.c index 3192b27625..05c6b2e0dc 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -25,8 +25,11 @@ #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" @@ -401,6 +404,25 @@ static int err(struct merge_options *opt, const char *err, ...) 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, @@ -422,6 +444,36 @@ static void path_msg(struct merge_options *opt, 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, @@ -707,6 +759,249 @@ static int collect_merge_info(struct merge_options *opt, /*** 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, @@ -716,7 +1011,130 @@ static int handle_content_merge(struct merge_options *opt, const int extra_marker_size, struct version_info *result) { - die("Not yet implemented"); + /* + * 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(), *** @@ -2144,6 +2562,8 @@ static void process_entry(struct merge_options *opt, struct conflict_info *ci, struct directory_versions *dir_metadata) { + int df_file_index = 0; + VERIFY_CI(ci); assert(ci->filemask >= 0 && ci->filemask <= 7); /* ci->match_mask == 7 was handled in collect_merge_info_callback() */ @@ -2158,14 +2578,108 @@ static void process_entry(struct merge_options *opt, assert(ci->df_conflict); } - if (ci->df_conflict) { - die("Not yet implemented."); + if (ci->df_conflict && ci->merged.result.mode == 0) { + int i; + + /* + * directory no longer in the way, but we do have a file we + * need to place here so we need to clean away the "directory + * merges to nothing" result. + */ + ci->df_conflict = 0; + assert(ci->filemask != 0); + ci->merged.clean = 0; + ci->merged.is_null = 0; + /* and we want to zero out any directory-related entries */ + ci->match_mask = (ci->match_mask & ~ci->dirmask); + ci->dirmask = 0; + for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) { + if (ci->filemask & (1 << i)) + continue; + ci->stages[i].mode = 0; + oidcpy(&ci->stages[i].oid, &null_oid); + } + } else if (ci->df_conflict && ci->merged.result.mode != 0) { + /* + * This started out as a D/F conflict, and the entries in + * the competing directory were not removed by the merge as + * evidenced by write_completed_directory() writing a value + * to ci->merged.result.mode. + */ + struct conflict_info *new_ci; + const char *branch; + const char *old_path = path; + int i; + + assert(ci->merged.result.mode == S_IFDIR); + + /* + * If filemask is 1, we can just ignore the file as having + * been deleted on both sides. We do not want to overwrite + * ci->merged.result, since it stores the tree for all the + * files under it. + */ + if (ci->filemask == 1) { + ci->filemask = 0; + return; + } + + /* + * This file still exists on at least one side, and we want + * the directory to remain here, so we need to move this + * path to some new location. + */ + new_ci = xcalloc(1, sizeof(*new_ci)); + /* We don't really want new_ci->merged.result copied, but it'll + * be overwritten below so it doesn't matter. We also don't + * want any directory mode/oid values copied, but we'll zero + * those out immediately. We do want the rest of ci copied. + */ + memcpy(new_ci, ci, sizeof(*ci)); + new_ci->match_mask = (new_ci->match_mask & ~new_ci->dirmask); + new_ci->dirmask = 0; + for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) { + if (new_ci->filemask & (1 << i)) + continue; + /* zero out any entries related to directories */ + new_ci->stages[i].mode = 0; + oidcpy(&new_ci->stages[i].oid, &null_oid); + } + + /* + * Find out which side this file came from; note that we + * cannot just use ci->filemask, because renames could cause + * the filemask to go back to 7. So we use dirmask, then + * pick the opposite side's index. + */ + df_file_index = (ci->dirmask & (1 << 1)) ? 2 : 1; + branch = (df_file_index == 1) ? opt->branch1 : opt->branch2; + path = unique_path(&opt->priv->paths, path, branch); + strmap_put(&opt->priv->paths, path, new_ci); + + path_msg(opt, path, 0, + _("CONFLICT (file/directory): directory in the way " + "of %s from %s; moving it to %s instead."), + old_path, branch, path); + + /* + * Zero out the filemask for the old ci. At this point, ci + * was just an entry for a directory, so we don't need to + * do anything more with it. + */ + ci->filemask = 0; + + /* + * Now note that we're working on the new entry (path was + * updated above. + */ + ci = new_ci; } /* * NOTE: Below there is a long switch-like if-elseif-elseif... block * which the code goes through even for the df_conflict cases - * above. Well, it will once we don't die-not-implemented above. + * above. */ if (ci->match_mask) { ci->merged.clean = 1; @@ -2189,21 +2703,142 @@ static void process_entry(struct merge_options *opt, } else if (ci->filemask >= 6 && (S_IFMT & ci->stages[1].mode) != (S_IFMT & ci->stages[2].mode)) { - /* - * Two different items from (file/submodule/symlink) - */ - die("Not yet implemented."); + /* Two different items from (file/submodule/symlink) */ + if (opt->priv->call_depth) { + /* Just use the version from the merge base */ + ci->merged.clean = 0; + oidcpy(&ci->merged.result.oid, &ci->stages[0].oid); + ci->merged.result.mode = ci->stages[0].mode; + ci->merged.is_null = (ci->merged.result.mode == 0); + } else { + /* Handle by renaming one or both to separate paths. */ + unsigned o_mode = ci->stages[0].mode; + unsigned a_mode = ci->stages[1].mode; + unsigned b_mode = ci->stages[2].mode; + struct conflict_info *new_ci; + const char *a_path = NULL, *b_path = NULL; + int rename_a = 0, rename_b = 0; + + new_ci = xmalloc(sizeof(*new_ci)); + + if (S_ISREG(a_mode)) + rename_a = 1; + else if (S_ISREG(b_mode)) + rename_b = 1; + else { + rename_a = 1; + rename_b = 1; + } + + path_msg(opt, path, 0, + _("CONFLICT (distinct types): %s had different " + "types on each side; renamed %s of them so " + "each can be recorded somewhere."), + path, + (rename_a && rename_b) ? _("both") : _("one")); + + ci->merged.clean = 0; + memcpy(new_ci, ci, sizeof(*new_ci)); + + /* Put b into new_ci, removing a from stages */ + new_ci->merged.result.mode = ci->stages[2].mode; + oidcpy(&new_ci->merged.result.oid, &ci->stages[2].oid); + new_ci->stages[1].mode = 0; + oidcpy(&new_ci->stages[1].oid, &null_oid); + new_ci->filemask = 5; + if ((S_IFMT & b_mode) != (S_IFMT & o_mode)) { + new_ci->stages[0].mode = 0; + oidcpy(&new_ci->stages[0].oid, &null_oid); + new_ci->filemask = 4; + } + + /* Leave only a in ci, fixing stages. */ + ci->merged.result.mode = ci->stages[1].mode; + oidcpy(&ci->merged.result.oid, &ci->stages[1].oid); + ci->stages[2].mode = 0; + oidcpy(&ci->stages[2].oid, &null_oid); + ci->filemask = 3; + if ((S_IFMT & a_mode) != (S_IFMT & o_mode)) { + ci->stages[0].mode = 0; + oidcpy(&ci->stages[0].oid, &null_oid); + ci->filemask = 2; + } + + /* Insert entries into opt->priv_paths */ + assert(rename_a || rename_b); + if (rename_a) { + a_path = unique_path(&opt->priv->paths, + path, opt->branch1); + strmap_put(&opt->priv->paths, a_path, ci); + } + + if (rename_b) + b_path = unique_path(&opt->priv->paths, + path, opt->branch2); + else + b_path = path; + strmap_put(&opt->priv->paths, b_path, new_ci); + + if (rename_a && rename_b) { + strmap_remove(&opt->priv->paths, path, 0); + /* + * We removed path from opt->priv->paths. path + * will also 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, + path); + } + + /* + * Do special handling for b_path since process_entry() + * won't be called on it specially. + */ + strmap_put(&opt->priv->conflicted, b_path, new_ci); + record_entry_for_tree(dir_metadata, b_path, + &new_ci->merged); + + /* + * Remaining code for processing this entry should + * think in terms of processing a_path. + */ + if (a_path) + path = a_path; + } } else if (ci->filemask >= 6) { - /* - * TODO: Needs a two-way or three-way content merge, but we're - * just being lazy and copying the version from HEAD and - * leaving it as conflicted. - */ - ci->merged.clean = 0; - ci->merged.result.mode = ci->stages[1].mode; - oidcpy(&ci->merged.result.oid, &ci->stages[1].oid); - /* When we fix above, we'll call handle_content_merge() */ - (void)handle_content_merge; + /* Need a two-way or three-way content merge */ + struct version_info merged_file; + unsigned clean_merge; + struct version_info *o = &ci->stages[0]; + struct version_info *a = &ci->stages[1]; + struct version_info *b = &ci->stages[2]; + + clean_merge = handle_content_merge(opt, path, o, a, b, + ci->pathnames, + opt->priv->call_depth * 2, + &merged_file); + ci->merged.clean = clean_merge && + !ci->df_conflict && !ci->path_conflict; + ci->merged.result.mode = merged_file.mode; + ci->merged.is_null = (merged_file.mode == 0); + oidcpy(&ci->merged.result.oid, &merged_file.oid); + if (clean_merge && ci->df_conflict) { + assert(df_file_index == 1 || df_file_index == 2); + ci->filemask = 1 << df_file_index; + ci->stages[df_file_index].mode = merged_file.mode; + oidcpy(&ci->stages[df_file_index].oid, &merged_file.oid); + } + if (!clean_merge) { + const char *reason = _("content"); + if (ci->filemask == 6) + reason = _("add/add"); + if (S_ISGITLINK(merged_file.mode)) + reason = _("submodule"); + path_msg(opt, path, 0, + _("CONFLICT (%s): Merge conflict in %s"), + reason, path); + } } else if (ci->filemask == 3 || ci->filemask == 5) { /* Modify/delete */ const char *modify_branch, *delete_branch; diff --git a/t/t4058-diff-duplicates.sh b/t/t4058-diff-duplicates.sh index c24ee175ef..54614b814d 100755 --- a/t/t4058-diff-duplicates.sh +++ b/t/t4058-diff-duplicates.sh @@ -1,5 +1,14 @@ #!/bin/sh +# NOTICE: +# This testsuite does a number of diffs and checks that the output match. +# However, it is a "garbage in, garbage out" situation; the trees have +# duplicate entries for individual paths, and it results in diffs that do +# not make much sense. As such, it is not clear that the diffs are +# "correct". The primary purpose of these tests was to verify that +# diff-tree does not segfault, but there is perhaps some value in ensuring +# that the diff output isn't wildly unreasonable. + test_description='test tree diff when trees have duplicate entries' . ./test-lib.sh @@ -57,7 +66,16 @@ test_expect_success 'create trees with duplicate entries' ' git tag two $outer_two ' -test_expect_success 'diff-tree between trees' ' +test_expect_success 'create tree without duplicate entries' ' + blob_one=$(echo one | git hash-object -w --stdin) && + outer_three=$(make_tree \ + 100644 renamed $blob_one + ) && + git tag three $outer_three +' + +test_expect_success 'diff-tree between duplicate trees' ' + # See NOTICE at top of file { printf ":000000 100644 $ZERO_OID $blob_two A\touter/inner\n" && printf ":000000 100644 $ZERO_OID $blob_two A\touter/inner\n" && @@ -71,9 +89,101 @@ test_expect_success 'diff-tree between trees' ' ' test_expect_success 'diff-tree with renames' ' - # same expectation as above, since we disable rename detection + # See NOTICE at top of file. git diff-tree -M -r --no-abbrev one two >actual && + test_must_be_empty actual +' + +test_expect_success 'diff-tree FROM duplicate tree' ' + # See NOTICE at top of file. + { + printf ":100644 000000 $blob_one $ZERO_OID D\touter/inner\n" && + printf ":100644 000000 $blob_two $ZERO_OID D\touter/inner\n" && + printf ":100644 000000 $blob_two $ZERO_OID D\touter/inner\n" && + printf ":100644 000000 $blob_two $ZERO_OID D\touter/inner\n" && + printf ":000000 100644 $ZERO_OID $blob_one A\trenamed\n" + } >expect && + git diff-tree -r --no-abbrev one three >actual && test_cmp expect actual ' +test_expect_success 'diff-tree FROM duplicate tree, with renames' ' + # See NOTICE at top of file. + { + printf ":100644 000000 $blob_two $ZERO_OID D\touter/inner\n" && + printf ":100644 000000 $blob_two $ZERO_OID D\touter/inner\n" && + printf ":100644 000000 $blob_two $ZERO_OID D\touter/inner\n" && + printf ":100644 100644 $blob_one $blob_one R100\touter/inner\trenamed\n" + } >expect && + git diff-tree -M -r --no-abbrev one three >actual && + test_cmp expect actual +' + +test_expect_success 'create a few commits' ' + git commit-tree -m "Duplicate Entries" two^{tree} >commit_id && + git branch base $(cat commit_id) && + + git commit-tree -p $(cat commit_id) -m "Just one" three^{tree} >up && + git branch update $(cat up) && + + git commit-tree -p $(cat up) -m "Back to weird" two^{tree} >final && + git branch final $(cat final) && + + rm commit_id up final +' + +test_expect_failure 'git read-tree does not segfault' ' + test_when_finished rm .git/index.lock && + test_might_fail git read-tree --reset base +' + +test_expect_failure 'reset --hard does not segfault' ' + test_when_finished rm .git/index.lock && + git checkout base && + test_might_fail git reset --hard +' + +test_expect_failure 'git diff HEAD does not segfault' ' + git checkout base && + GIT_TEST_CHECK_CACHE_TREE=false && + git reset --hard && + test_might_fail git diff HEAD +' + +test_expect_failure 'can switch to another branch when status is empty' ' + git clean -ffdqx && + git status --porcelain -uno >actual && + test_must_be_empty actual && + git checkout update +' + +test_expect_success 'forcibly switch to another branch, verify status empty' ' + git checkout -f update && + git status --porcelain -uno >actual && + test_must_be_empty actual +' + +test_expect_success 'fast-forward from non-duplicate entries to duplicate' ' + git merge final +' + +test_expect_failure 'clean status, switch branches, status still clean' ' + git status --porcelain -uno >actual && + test_must_be_empty actual && + git checkout base && + git status --porcelain -uno >actual && + test_must_be_empty actual +' + +test_expect_success 'switch to base branch and force status to be clean' ' + git checkout base && + GIT_TEST_CHECK_CACHE_TREE=false git reset --hard && + git status --porcelain -uno >actual && + test_must_be_empty actual +' + +test_expect_failure 'fast-forward from duplicate entries to non-duplicate' ' + git merge update +' + test_done |