{"thread":{"id":"1729","subject":"[PATCH 0/4] Support multiple ancestors in read-tree","startedAt":"2005-09-05T06:03:17Z","lastAt":"2005-09-05T06:05:17Z","messageCount":5,"participants":["Daniel Barkalow"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"8079","messageId":"Pine.LNX.4.63.0509050151240.23242@iabervon.org","threadId":"1729","inReplyTo":null,"subject":"[PATCH 0/4] Support multiple ancestors in read-tree","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-05T06:03:17Z","receivedAt":"2005-09-05T06:03:17Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"Various messages have already described this series. There's still a \nmemory leak that should get resolved, but otherwise it should work. I'm \nnot entirely sure that all directory-file conflict cases are handled \nproperly, and some undefined cases behave differently. Also, I was a bit \ncareless with preparing the patches.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"8080","messageId":"Pine.LNX.4.63.0509050203270.23242@iabervon.org","threadId":"1729","inReplyTo":"Pine.LNX.4.63.0509050151240.23242@iabervon.org","subject":"[PATCH 1/4] Add a function for getting a struct tree for an ent.","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-05T06:03:51Z","receivedAt":"2005-09-05T06:03:51Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"Signed-off-by: Daniel Barkalow <barkalow@iabervon.org>\n---\n\n tree.c |   21 +++++++++++++++++++++\n tree.h |    3 +++\n 2 files changed, 24 insertions(+), 0 deletions(-)\n\n3bfcc20b6aeff3e1fbcce97a426383c9770a2105\ndiff --git a/tree.c b/tree.c\n--- a/tree.c\n+++ b/tree.c\n@@ -1,5 +1,7 @@\n #include \"tree.h\"\n #include \"blob.h\"\n+#include \"commit.h\"\n+#include \"tag.h\"\n #include \"cache.h\"\n #include <stdlib.h>\n \n@@ -212,3 +214,22 @@ int parse_tree(struct tree *item)\n \tfree(buffer);\n \treturn ret;\n }\n+\n+struct tree *parse_tree_indirect(const unsigned char *sha1)\n+{\n+\tstruct object *obj = parse_object(sha1);\n+\tdo {\n+\t\tif (!obj)\n+\t\t\treturn NULL;\n+\t\tif (obj->type == tree_type)\n+\t\t\treturn (struct tree *) obj;\n+\t\telse if (obj->type == commit_type)\n+\t\t\tobj = &(((struct commit *) obj)->tree->object);\n+\t\telse if (obj->type == tag_type)\n+\t\t\tobj = ((struct tag *) obj)->tagged;\n+\t\telse\n+\t\t\treturn NULL;\n+\t\tif (!obj->parsed)\n+\t\t\tparse_object(obj->sha1);\n+\t} while (1);\n+}\ndiff --git a/tree.h b/tree.h\n--- a/tree.h\n+++ b/tree.h\n@@ -32,4 +32,7 @@ int parse_tree_buffer(struct tree *item,\n \n int parse_tree(struct tree *tree);\n \n+/* Parses and returns the tree in the given ent, chasing tags and commits. */\n+struct tree *parse_tree_indirect(const unsigned char *sha1);\n+\n #endif /* TREE_H */\n"},{"id":"8081","messageId":"Pine.LNX.4.63.0509050203540.23242@iabervon.org","threadId":"1729","inReplyTo":"Pine.LNX.4.63.0509050151240.23242@iabervon.org","subject":"[PATCH 2/4] Add function to append to an object_list.","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-05T06:04:18Z","receivedAt":"2005-09-05T06:04:18Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"Signed-off-by: Daniel Barkalow <barkalow@iabervon.org>\n---\n\n object.c |   11 +++++++++++\n object.h |    3 +++\n 2 files changed, 14 insertions(+), 0 deletions(-)\n\n88cf2db55848e7a2cf655171c7e9fd74c70a0281\ndiff --git a/object.c b/object.c\n--- a/object.c\n+++ b/object.c\n@@ -184,6 +184,17 @@ struct object_list *object_list_insert(s\n         return new_list;\n }\n \n+void object_list_append(struct object *item,\n+\t\t\tstruct object_list **list_p)\n+{\n+\twhile (*list_p) {\n+\t\tlist_p = &((*list_p)->next);\n+\t}\n+\t*list_p = xmalloc(sizeof(struct object_list));\n+\t(*list_p)->next = NULL;\n+\t(*list_p)->item = item;\n+}\n+\n unsigned object_list_length(struct object_list *list)\n {\n \tunsigned ret = 0;\ndiff --git a/object.h b/object.h\n--- a/object.h\n+++ b/object.h\n@@ -41,6 +41,9 @@ void mark_reachable(struct object *obj, \n struct object_list *object_list_insert(struct object *item, \n \t\t\t\t       struct object_list **list_p);\n \n+void object_list_append(struct object *item,\n+\t\t\tstruct object_list **list_p);\n+\n unsigned object_list_length(struct object_list *list);\n \n int object_list_contains(struct object_list *list, struct object *obj);\n"},{"id":"8082","messageId":"Pine.LNX.4.63.0509050204230.23242@iabervon.org","threadId":"1729","inReplyTo":"Pine.LNX.4.63.0509050151240.23242@iabervon.org","subject":"[PATCH 3/4] Rewrite read-tree","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-05T06:04:48Z","receivedAt":"2005-09-05T06:04:48Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"Adds support for multiple ancestors, removes --emu23, much simplification.\n\nSigned-off-by: Daniel Barkalow <barkalow@iabervon.org>\n---\n\n read-tree.c                       |  811 +++++++++++++++++++------------------\n t/t1005-read-tree-m-2way-emu23.sh |  422 -------------------\n 2 files changed, 425 insertions(+), 808 deletions(-)\n delete mode 100755 t/t1005-read-tree-m-2way-emu23.sh\n\nf196469bec156947038f1d3d00c899c9044334ca\ndiff --git a/read-tree.c b/read-tree.c\n--- a/read-tree.c\n+++ b/read-tree.c\n@@ -5,73 +5,291 @@\n  */\n #include \"cache.h\"\n \n-static int stage = 0;\n+#include \"object.h\"\n+#include \"tree.h\"\n+\n+static int merge = 0;\n static int update = 0;\n \n-static int unpack_tree(unsigned char *sha1)\n-{\n-\tvoid *buffer;\n-\tunsigned long size;\n-\tint ret;\n+static int head_idx = -1;\n+static int merge_size = 0;\n \n-\tbuffer = read_object_with_reference(sha1, \"tree\", &size, NULL);\n-\tif (!buffer)\n-\t\treturn -1;\n-\tret = read_tree(buffer, size, stage, NULL);\n-\tfree(buffer);\n+static struct object_list *trees = NULL;\n+\n+static struct cache_entry df_conflict_entry = { \n+};\n+\n+static struct tree_entry_list df_conflict_list = {\n+\t.name = NULL,\n+\t.next = &df_conflict_list\n+};\n+\n+typedef int (*merge_fn_t)(struct cache_entry **src);\n+\n+static int entcmp(char *name1, int dir1, char *name2, int dir2)\n+{\n+\tint len1 = strlen(name1);\n+\tint len2 = strlen(name2);\n+\tint len = len1 < len2 ? len1 : len2;\n+\tint ret = memcmp(name1, name2, len);\n+\tunsigned char c1, c2;\n+\tif (ret)\n+\t\treturn ret;\n+\tc1 = name1[len];\n+\tc2 = name2[len];\n+\tif (!c1 && dir1)\n+\t\tc1 = '/';\n+\tif (!c2 && dir2)\n+\t\tc2 = '/';\n+\tret = (c1 < c2) ? -1 : (c1 > c2) ? 1 : 0;\n+\tif (c1 && c2 && !ret)\n+\t\tret = len1 - len2;\n \treturn ret;\n }\n \n-static int path_matches(struct cache_entry *a, struct cache_entry *b)\n+static int unpack_trees_rec(struct tree_entry_list **posns, int len,\n+\t\t\t    const char *base, merge_fn_t fn, int *indpos)\n {\n-\tint len = ce_namelen(a);\n-\treturn ce_namelen(b) == len &&\n-\t\t!memcmp(a->name, b->name, len);\n+\tint baselen = strlen(base);\n+\tint src_size = len + 1;\n+\tdo {\n+\t\tint i;\n+\t\tchar *first;\n+\t\tint firstdir = 0;\n+\t\tint pathlen;\n+\t\tunsigned ce_size;\n+\t\tstruct tree_entry_list **subposns;\n+\t\tstruct cache_entry **src;\n+\t\tint any_files = 0;\n+\t\tint any_dirs = 0;\n+\t\tchar *cache_name;\n+\t\tint ce_stage;\n+\n+\t\t/* Find the first name in the input. */\n+\n+\t\tfirst = NULL;\n+\t\tcache_name = NULL;\n+\n+\t\t/* Check the cache */\n+\t\tif (merge && *indpos < active_nr) {\n+\t\t\t/* This is a bit tricky: */\n+\t\t\t/* If the index has a subdirectory (with\n+\t\t\t * contents) as the first name, it'll get a\n+\t\t\t * filename like \"foo/bar\". But that's after\n+\t\t\t * \"foo\", so the entry in trees will get\n+\t\t\t * handled first, at which point we'll go into\n+\t\t\t * \"foo\", and deal with \"bar\" from the index,\n+\t\t\t * because the base will be \"foo/\". The only\n+\t\t\t * way we can actually have \"foo/bar\" first of\n+\t\t\t * all the things is if the trees don't\n+\t\t\t * contain \"foo\" at all, in which case we'll\n+\t\t\t * handle \"foo/bar\" without going into the\n+\t\t\t * directory, but that's fine (and will return\n+\t\t\t * an error anyway, with the added unknown\n+\t\t\t * file case.\n+\t\t\t */\n+\n+\t\t\tcache_name = active_cache[*indpos]->name;\n+\t\t\tif (strlen(cache_name) > baselen &&\n+\t\t\t    !memcmp(cache_name, base, baselen)) {\n+\t\t\t\tcache_name += baselen;\n+\t\t\t\tfirst = cache_name;\n+\t\t\t} else {\n+\t\t\t\tcache_name = NULL;\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (first)\n+\t\t\tprintf(\"index %s\\n\", first);\n+\n+\t\tfor (i = 0; i < len; i++) {\n+\t\t\tif (!posns[i] || posns[i] == &df_conflict_list)\n+\t\t\t\tcontinue;\n+\t\t\tprintf(\"%d %s\\n\", i + 1, posns[i]->name);\n+\t\t\tif (!first || entcmp(first, firstdir,\n+\t\t\t\t\t     posns[i]->name, \n+\t\t\t\t\t     posns[i]->directory) > 0) {\n+\t\t\t\tfirst = posns[i]->name;\n+\t\t\t\tfirstdir = posns[i]->directory;\n+\t\t\t}\n+\t\t}\n+\t\t/* No name means we're done */\n+\t\tif (!first)\n+\t\t\treturn 0;\n+\n+\t\tpathlen = strlen(first);\n+\t\tce_size = cache_entry_size(baselen + pathlen);\n+\n+\t\tsrc = xmalloc(sizeof(struct cache_entry *) * src_size);\n+\t\tmemset(src, 0, sizeof(struct cache_entry *) * src_size);\n+\n+\t\tsubposns = xmalloc(sizeof(struct tree_list_entry *) * len);\n+\t\tmemset(subposns, 0, sizeof(struct tree_list_entry *) * len);\n+\n+\t\tif (cache_name && !strcmp(cache_name, first)) {\n+\t\t\tany_files = 1;\n+\t\t\tsrc[0] = active_cache[*indpos];\n+\t\t\tremove_cache_entry_at(*indpos);\n+\t\t}\n+\n+\t\tfor (i = 0; i < len; i++) {\n+\t\t\tstruct cache_entry *ce;\n+\n+\t\t\tif (!posns[i] ||\n+\t\t\t    (posns[i] != &df_conflict_list &&\n+\t\t\t     strcmp(first, posns[i]->name))) {\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\n+\t\t\tif (posns[i] == &df_conflict_list) {\n+\t\t\t\tsrc[i + merge] = &df_conflict_entry;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\n+\t\t\tif (posns[i]->directory) {\n+\t\t\t\tany_dirs = 1;\n+\t\t\t\tparse_tree(posns[i]->item.tree);\n+\t\t\t\tsubposns[i] = posns[i]->item.tree->entries;\n+\t\t\t\tposns[i] = posns[i]->next;\n+\t\t\t\tsrc[i + merge] = &df_conflict_entry;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\n+\t\t\tif (!merge)\n+\t\t\t\tce_stage = 0;\n+\t\t\telse if (i + 1 < head_idx)\n+\t\t\t\tce_stage = 1;\n+\t\t\telse if (i + 1 > head_idx)\n+\t\t\t\tce_stage = 3;\n+\t\t\telse\n+\t\t\t\tce_stage = 2;\n+\n+\t\t\tce = xmalloc(ce_size);\n+\t\t\tmemset(ce, 0, ce_size);\n+\t\t\tce->ce_mode = create_ce_mode(posns[i]->mode);\n+\t\t\tce->ce_flags = create_ce_flags(baselen + pathlen,\n+\t\t\t\t\t\t       ce_stage);\n+\t\t\tmemcpy(ce->name, base, baselen);\n+\t\t\tmemcpy(ce->name + baselen, first, pathlen + 1);\n+\n+\t\t\tany_files = 1;\n+\n+\t\t\tmemcpy(ce->sha1, posns[i]->item.any->sha1, 20);\n+\t\t\tsrc[i + merge] = ce;\n+\t\t\tsubposns[i] = &df_conflict_list;\n+\t\t\tposns[i] = posns[i]->next;\n+\t\t}\n+\t\tif (any_files) {\n+\t\t\tif (merge) {\n+\t\t\t\tint ret;\n+\n+\t\t\t\tprintf(\"%s:\\n\", first);\n+\t\t\t\tfor (i = 0; i < src_size; i++) {\n+\t\t\t\t\tprintf(\" %d \", i);\n+\t\t\t\t\tif (src[i])\n+\t\t\t\t\t\tprintf(\"%s\\n\", sha1_to_hex(src[i]->sha1));\n+\t\t\t\t\telse\n+\t\t\t\t\t\tprintf(\"\\n\");\n+\t\t\t\t}\n+\n+\t\t\t\tret = fn(src);\n+\t\t\t\t\n+\t\t\t\tprintf(\"Added %d entries\\n\", ret);\n+\n+\t\t\t\t*indpos += ret;\n+\t\t\t} else {\n+\t\t\t\tfor (i = 0; i < src_size; i++) {\n+\t\t\t\t\tif (src[i]) {\n+\t\t\t\t\t\tadd_cache_entry(src[i], ADD_CACHE_OK_TO_ADD|ADD_CACHE_SKIP_DFCHECK);\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\t\tif (any_dirs) {\n+\t\t\tchar *newbase = xmalloc(baselen + 2 + pathlen);\n+\t\t\tmemcpy(newbase, base, baselen);\n+\t\t\tmemcpy(newbase + baselen, first, pathlen);\n+\t\t\tnewbase[baselen + pathlen] = '/';\n+\t\t\tnewbase[baselen + pathlen + 1] = '\\0';\n+\t\t\tif (unpack_trees_rec(subposns, len, newbase, fn,\n+\t\t\t\t\t     indpos))\n+\t\t\t\treturn -1;\n+\t\t}\n+\t\tfree(subposns);\n+\t\tfree(src);\n+\t} while (1);\n }\n \n-static int same(struct cache_entry *a, struct cache_entry *b)\n+static void reject_merge(struct cache_entry *ce)\n {\n-\treturn a->ce_mode == b->ce_mode && \n-\t\t!memcmp(a->sha1, b->sha1, 20);\n+\tdie(\"Entry '%s' would be overwritten by merge. Cannot merge.\", \n+\t    ce->name);\n }\n \n+static void check_updates(struct cache_entry **src, int nr)\n+{\n+\tstatic struct checkout state = {\n+\t\t.base_dir = \"\",\n+\t\t.force = 1,\n+\t\t.quiet = 1,\n+\t\t.refresh_cache = 1,\n+\t};\n+\tunsigned short mask = htons(CE_UPDATE);\n+\twhile (nr--) {\n+\t\tstruct cache_entry *ce = *src++;\n+\t\tif (!ce->ce_mode) {\n+\t\t\tif (update)\n+\t\t\t\tunlink(ce->name);\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (ce->ce_flags & mask) {\n+\t\t\tce->ce_flags &= ~mask;\n+\t\t\tif (update)\n+\t\t\t\tcheckout_entry(ce, &state);\n+\t\t}\n+\t}\n+}\n \n-/*\n- * This removes all trivial merges that don't change the tree\n- * and collapses them to state 0.\n- */\n-static struct cache_entry *merge_entries(struct cache_entry *a,\n-\t\t\t\t\t struct cache_entry *b,\n-\t\t\t\t\t struct cache_entry *c)\n+static int unpack_trees(merge_fn_t fn)\n {\n-\t/*\n-\t * Ok, all three entries describe the same\n-\t * filename, but maybe the contents or file\n-\t * mode have changed?\n-\t *\n-\t * The trivial cases end up being the ones where two\n-\t * out of three files are the same:\n-\t *  - both destinations the same, trivially take either\n-\t *  - one of the destination versions hasn't changed,\n-\t *    take the other.\n-\t *\n-\t * The \"all entries exactly the same\" case falls out as\n-\t * a special case of any of the \"two same\" cases.\n-\t *\n-\t * Here \"a\" is \"original\", and \"b\" and \"c\" are the two\n-\t * trees we are merging.\n-\t */\n-\tif (a && b && c) {\n-\t\tif (same(b,c))\n-\t\t\treturn c;\n-\t\tif (same(a,b))\n-\t\t\treturn c;\n-\t\tif (same(a,c))\n-\t\t\treturn b;\n+\tint indpos = 0;\n+\tunsigned len = object_list_length(trees);\n+\tstruct tree_entry_list **posns = \n+\t\txmalloc(len * sizeof(struct tree_entry_list *));\n+\tint i;\n+\tstruct object_list *posn = trees;\n+\tmerge_size = len;\n+\tfor (i = 0; i < len; i++) {\n+\t\tposns[i] = ((struct tree *) posn->item)->entries;\n+\t\tposn = posn->next;\n \t}\n-\treturn NULL;\n+\tif (unpack_trees_rec(posns, len, \"\", fn, &indpos))\n+\t\treturn -1;\n+\n+\tcheck_updates(active_cache, active_nr);\n+\treturn 0;\n }\n \n+static int list_tree(unsigned char *sha1)\n+{\n+\tstruct tree *tree = parse_tree_indirect(sha1);\n+\tif (!tree)\n+\t\treturn -1;\n+\tobject_list_append(&tree->object, &trees);\n+\treturn 0;\n+}\n+\n+static int same(struct cache_entry *a, struct cache_entry *b)\n+{\n+\tif (!!a != !!b)\n+\t\treturn 0;\n+\tif (!a && !b)\n+\t\treturn 1;\n+\treturn a->ce_mode == b->ce_mode && \n+\t\t!memcmp(a->sha1, b->sha1, 20);\n+}\n+\n+\n /*\n  * When a CE gets turned into an unmerged entry, we\n  * want it to be up-to-date\n@@ -91,18 +309,7 @@ static void verify_uptodate(struct cache\n \tdie(\"Entry '%s' not uptodate. Cannot merge.\", ce->name);\n }\n \n-/*\n- * If the old tree contained a CE that isn't even in the\n- * result, that's always a problem, regardless of whether\n- * it's up-to-date or not (ie it can be a file that we\n- * have updated but not committed yet).\n- */\n-static void reject_merge(struct cache_entry *ce)\n-{\n-\tdie(\"Entry '%s' would be overwritten by merge. Cannot merge.\", ce->name);\n-}\n-\n-static int merged_entry_internal(struct cache_entry *merge, struct cache_entry *old, struct cache_entry **dst, int allow_dirty)\n+static int merged_entry(struct cache_entry *merge, struct cache_entry *old)\n {\n \tmerge->ce_flags |= htons(CE_UPDATE);\n \tif (old) {\n@@ -115,195 +322,129 @@ static int merged_entry_internal(struct \n \t\t */\n \t\tif (same(old, merge)) {\n \t\t\t*merge = *old;\n-\t\t} else if (!allow_dirty) {\n+\t\t} else {\n \t\t\tverify_uptodate(old);\n \t\t}\n \t}\n \tmerge->ce_flags &= ~htons(CE_STAGEMASK);\n-\t*dst++ = merge;\n+\tadd_cache_entry(merge, ADD_CACHE_OK_TO_ADD);\n \treturn 1;\n }\n \n-static int merged_entry_allow_dirty(struct cache_entry *merge, struct cache_entry *old, struct cache_entry **dst)\n-{\n-\treturn merged_entry_internal(merge, old, dst, 1);\n-}\n-\n-static int merged_entry(struct cache_entry *merge, struct cache_entry *old, struct cache_entry **dst)\n-{\n-\treturn merged_entry_internal(merge, old, dst, 0);\n-}\n-\n-static int deleted_entry(struct cache_entry *ce, struct cache_entry *old, struct cache_entry **dst)\n+static int deleted_entry(struct cache_entry *ce, struct cache_entry *old)\n {\n \tif (old)\n \t\tverify_uptodate(old);\n \tce->ce_mode = 0;\n-\t*dst++ = ce;\n+\tadd_cache_entry(ce, ADD_CACHE_OK_TO_ADD);\n \treturn 1;\n }\n \n-static int causes_df_conflict(struct cache_entry *ce, int stage,\n-\t\t\t      struct cache_entry **dst_,\n-\t\t\t      struct cache_entry **next_,\n-\t\t\t      int tail)\n-{\n-\t/* This is called during the merge operation and walking\n-\t * the active_cache[] array is messy, because it is in the\n-\t * middle of overlapping copy operation.  The invariants\n-\t * are:\n-\t * (1) active_cache points at the first (zeroth) entry.\n-\t * (2) up to dst pointer are resolved entries.\n-\t * (3) from the next pointer (head-inclusive) to the tail\n-\t *     of the active_cache array have the remaining paths\n-\t *     to be processed.  There can be a gap between dst\n-\t *     and next.  Note that next is called \"src\" in the\n-\t *     merge_cache() function, and tail is the original\n-\t *     end of active_cache array when merge_cache() started.\n-\t * (4) the path corresponding to *ce is not found in (2)\n-\t *     or (3).  It is in the gap.\n-\t *\n-\t *  active_cache -----......+++++++++++++.\n-\t *                    ^dst  ^next        ^tail\n-\t */\n-\tint i, next, dst;\n-\tconst char *path = ce->name;\n-\tint namelen = ce_namelen(ce);\n-\n-\tnext = next_ - active_cache;\n-\tdst = dst_ - active_cache;\n-\n-\tfor (i = 0; i < tail; i++) {\n-\t\tint entlen, len;\n-\t\tconst char *one, *two;\n-\t\tif (dst <= i && i < next)\n-\t\t\tcontinue;\n-\t\tce = active_cache[i];\n-\t\tif (ce_stage(ce) != stage)\n-\t\t\tcontinue;\n-\t\t/* If ce->name is a prefix of path, then path is a file\n-\t\t * that hangs underneath ce->name, which is bad.\n-\t\t * If path is a prefix of ce->name, then it is the\n-\t\t * other way around which also is bad.\n-\t\t */\n-\t\tentlen = ce_namelen(ce);\n-\t\tif (namelen == entlen)\n-\t\t\tcontinue;\n-\t\tif (namelen < entlen) {\n-\t\t\tlen = namelen;\n-\t\t\tone = path;\n-\t\t\ttwo = ce->name;\n-\t\t} else {\n-\t\t\tlen = entlen;\n-\t\t\tone = ce->name;\n-\t\t\ttwo = path;\n-\t\t}\n-\t\tif (memcmp(one, two, len))\n-\t\t\tcontinue;\n-\t\tif (two[len] == '/')\n-\t\t\treturn 1;\n-\t}\n-\treturn 0;\n+static int keep_entry(struct cache_entry *ce)\n+{\n+\tadd_cache_entry(ce, ADD_CACHE_OK_TO_ADD);\n+\treturn 1;\n }\n \n-static int threeway_merge(struct cache_entry *stages[4],\n-\t\t\t  struct cache_entry **dst,\n-\t\t\t  struct cache_entry **next, int tail)\n-{\n-\tstruct cache_entry *old = stages[0];\n-\tstruct cache_entry *a = stages[1], *b = stages[2], *c = stages[3];\n-\tstruct cache_entry *merge;\n+static int threeway_merge(struct cache_entry **stages)\n+{\n+\tstruct cache_entry *index;\n+\tstruct cache_entry *head; \n+\tstruct cache_entry *remote = stages[head_idx + 1];\n \tint count;\n+\tint head_match = 0;\n+\tint remote_match = 0;\n \n-\t/* #5ALT */\n-\tif (!a && b && c && same(b, c)) {\n-\t\tif (old && !same(b, old))\n-\t\t\treturn -1;\n-\t\treturn merged_entry_allow_dirty(b, old, dst);\n+\tint df_conflict_head = 0;\n+\tint df_conflict_remote = 0;\n+\n+\tint any_anc_missing = 0;\n+\tint i;\n+\n+\tfor (i = 1; i < head_idx; i++) {\n+\t\tif (!stages[i])\n+\t\t\tany_anc_missing = 1;\n \t}\n-\t/* #2ALT and #3ALT */\n-\tif (!a && (!!b != !!c)) {\n-\t\t/*\n-\t\t * The reason we need to worry about directory/file\n-\t\t * conflicts only in #2ALT and #3ALT case is this:\n-\t\t *\n-\t\t * (1) For all other cases that read-tree internally\n-\t\t *     resolves a path, we always have such a path in\n-\t\t *     *both* stage2 and stage3 when we begin.\n-\t\t *     Traditionally, the behaviour has been even\n-\t\t *     stricter and we did not resolve a path without\n-\t\t *     initially being in all of stage1, 2, and 3.\n-\t\t *\n-\t\t * (2) When read-tree finishes, all resolved paths (i.e.\n-\t\t *     the paths that are in stage0) must have come from\n-\t\t *     either stage2 or stage3.  It is not possible to\n-\t\t *     have a stage0 path as a result of a merge if\n-\t\t *     neither stage2 nor stage3 had that path.\n-\t\t *\n-\t\t * (3) It is guaranteed that just after reading the\n-\t\t *     stages, each stage cannot have directory/file\n-\t\t *     conflicts on its own, because they are populated\n-\t\t *     by reading hierarchy of a tree.  Combined with\n-\t\t *     (1) and (2) above, this means that no matter what\n-\t\t *     combination of paths we take from stage2 and\n-\t\t *     stage3 as a result of a merge, they cannot cause\n-\t\t *     a directory/file conflict situation (otherwise\n-\t\t *     the \"guilty\" path would have already had such a\n-\t\t *     conflict in the original stage, either stage2\n-\t\t *     or stage3).  Although its stage2 is synthesized\n-\t\t *     by overlaying the current index on top of \"our\n-\t\t *     head\" tree, --emu23 case also has this guarantee,\n-\t\t *     by calling add_cache_entry() to create such stage2\n-\t\t *     entries.\n-\t\t *\n-\t\t * (4) Only #2ALT and #3ALT lack the guarantee (1).\n-\t\t *     They resolve paths that exist only in stage2\n-\t\t *     or stage3.  The stage2 tree may have a file DF\n-\t\t *     while stage3 tree may have a file DF/DF.  If\n-\t\t *     #2ALT and #3ALT rules happen to apply to both\n-\t\t *     of them, we would end up having DF (coming from\n-\t\t *     stage2) and DF/DF (from stage3) in the result.\n-\t\t *     When we attempt to resolve a path that exists\n-\t\t *     only in stage2, we need to make sure there is\n-\t\t *     no path that would conflict with it in stage3\n-\t\t *     and vice versa.\n-\t\t */\n-\t\tif (c) { /* #2ALT */\n-\t\t\tif (!causes_df_conflict(c, 2, dst, next, tail) &&\n-\t\t\t    (!old || same(c, old)))\n-\t\t\t\treturn merged_entry_allow_dirty(c, old, dst);\n-\t\t}\n-\t\telse { /* #3ALT */\n-\t\t\tif (!causes_df_conflict(b, 3, dst, next, tail) &&\n-\t\t\t    (!old || same(b, old)))\n-\t\t\t\treturn merged_entry_allow_dirty(b, old, dst);\n-\t\t}\n-\t\t/* otherwise we will apply the original rule */\n-\t}\n-\t/* #14ALT */\n-\tif (a && b && c && same(a, b) && !same(a, c)) {\n-\t\tif (old && same(old, c))\n-\t\t\treturn merged_entry_allow_dirty(c, old, dst);\n-\t\t/* otherwise the regular rule applies */\n+\n+\tindex = stages[0];\n+\thead = stages[head_idx];\n+\n+\tif (head == &df_conflict_entry) {\n+\t\tdf_conflict_head = 1;\n+\t\thead = NULL;\n+\t}\n+\n+\tif (remote == &df_conflict_entry) {\n+\t\tdf_conflict_remote = 1;\n+\t\tremote = NULL;\n+\t}\n+\n+\t/* First, if there's a #16 situation, note that to prevent #13\n+\t * and #14. \n+\t */\n+\tif (!same(remote, head)) {\n+\t\tfor (i = 1; i < head_idx; i++) {\n+\t\t\tif (same(stages[i], head)) {\n+\t\t\t\thead_match = 1;\n+\t\t\t}\n+\t\t\tif (same(stages[i], remote)) {\n+\t\t\t\tremote_match = 1;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\t/* We start with cases where the index is allowed to match\n+\t * something other than the head: #14(ALT) and #2ALT, where it\n+\t * is permitted to match the result instead.\n+\t */\n+\t/* #14, #14ALT, #2ALT */\n+\tif (remote && !df_conflict_head && head_match && !remote_match) {\n+\t\tif (index && !same(index, remote) && !same(index, head))\n+\t\t\treject_merge(index);\n+\t\treturn merged_entry(remote, index);\n \t}\n \t/*\n-\t * If we have an entry in the index cache (\"old\"), then we want\n-\t * to make sure that it matches any entries in stage 2 (\"first\n-\t * branch\", aka \"b\").\n+\t * If we have an entry in the index cache, then we want to\n+\t * make sure that it matches head.\n \t */\n-\tif (old) {\n-\t\tif (!b || !same(old, b))\n-\t\t\treturn -1;\n+\tif (index && !same(index, head)) {\n+\t\treject_merge(index);\n \t}\n-\tmerge = merge_entries(a, b, c);\n-\tif (merge)\n-\t\treturn merged_entry(merge, old, dst);\n-\tif (old)\n-\t\tverify_uptodate(old);\n+\n+\tif (head) {\n+\t\t/* #5ALT, #15 */\n+\t\tif (same(head, remote))\n+\t\t\treturn merged_entry(head, index);\n+\t\t/* #13, #3ALT */\n+\t\tif (!df_conflict_remote && remote_match && !head_match)\n+\t\t\treturn merged_entry(head, index);\n+\t}\n+\n+\t/* #1 */\n+\tif (!head && !remote && any_anc_missing)\n+\t\treturn 0;\n+\n+\t/* Below are \"no merge\" cases, which require that the index be\n+\t * up-to-date to avoid the files getting overwritten with\n+\t * conflict resolution files. \n+\t */\n+\tif (index) {\n+\t\tverify_uptodate(index);\n+\t}\n+\n+\t/* #2, #3, #4, #6, #7, #9, #11. */\n \tcount = 0;\n-\tif (a) { *dst++ = a; count++; }\n-\tif (b) { *dst++ = b; count++; }\n-\tif (c) { *dst++ = c; count++; }\n+\tif (!head_match || !remote_match) {\n+\t\tfor (i = 1; i < head_idx; i++) {\n+\t\t\tif (stages[i]) {\n+\t\t\t\tkeep_entry(stages[i]);\n+\t\t\t\tcount++;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t}\n+\tif (head) { count += keep_entry(head); }\n+\tif (remote) { count += keep_entry(remote); }\n \treturn count;\n }\n \n@@ -316,14 +457,14 @@ static int threeway_merge(struct cache_e\n  * \"carry forward\" rule, please see <Documentation/git-read-tree.txt>.\n  *\n  */\n-static int twoway_merge(struct cache_entry **src, struct cache_entry **dst,\n-\t\t\tstruct cache_entry **next, int tail)\n+static int twoway_merge(struct cache_entry **src)\n {\n \tstruct cache_entry *current = src[0];\n \tstruct cache_entry *oldtree = src[1], *newtree = src[2];\n \n-\tif (src[3])\n-\t\treturn -1;\n+\tif (merge_size != 2)\n+\t\treturn error(\"Cannot do a twoway merge of %d trees\\n\",\n+\t\t\t     merge_size);\n \n \tif (current) {\n \t\tif ((!oldtree && !newtree) || /* 4 and 5 */\n@@ -334,78 +475,32 @@ static int twoway_merge(struct cache_ent\n \t\t    (oldtree && newtree &&\n \t\t     !same(oldtree, newtree) && /* 18 and 19*/\n \t\t     same(current, newtree))) {\n-\t\t\t*dst++ = current;\n-\t\t\treturn 1;\n+\t\t\treturn keep_entry(current);\n \t\t}\n \t\telse if (oldtree && !newtree && same(current, oldtree)) {\n \t\t\t/* 10 or 11 */\n-\t\t\treturn deleted_entry(oldtree, current, dst);\n+\t\t\treturn deleted_entry(oldtree, current);\n \t\t}\n \t\telse if (oldtree && newtree &&\n \t\t\t same(current, oldtree) && !same(current, newtree)) {\n \t\t\t/* 20 or 21 */\n-\t\t\treturn merged_entry(newtree, current, dst);\n+\t\t\treturn merged_entry(newtree, current);\n \t\t}\n-\t\telse\n+\t\telse {\n \t\t\t/* all other failures */\n+\t\t\tif (oldtree)\n+\t\t\t\treject_merge(oldtree);\n+\t\t\tif (current)\n+\t\t\t\treject_merge(current);\n+\t\t\tif (newtree)\n+\t\t\t\treject_merge(newtree);\n \t\t\treturn -1;\n+\t\t}\n \t}\n \telse if (newtree)\n-\t\treturn merged_entry(newtree, current, dst);\n+\t\treturn merged_entry(newtree, current);\n \telse\n-\t\treturn deleted_entry(oldtree, current, dst);\n-}\n-\n-/*\n- * Two-way merge emulated with three-way merge.\n- *\n- * This treats \"read-tree -m H M\" by transforming it internally\n- * into \"read-tree -m H I+H M\", where I+H is a tree that would\n- * contain the contents of the current index file, overlayed on\n- * top of H.  Unlike the traditional two-way merge, this leaves\n- * the stages in the resulting index file and lets the user resolve\n- * the merge conflicts using standard tools for three-way merge.\n- *\n- * This function is just to set-up such an arrangement, and the\n- * actual merge uses threeway_merge() function.\n- */\n-static void setup_emu23(void)\n-{\n-\t/* stage0 contains I, stage1 H, stage2 M.\n-\t * move stage2 to stage3, and create stage2 entries\n-\t * by scanning stage0 and stage1 entries.\n-\t */\n-\tint i, namelen, size;\n-\tstruct cache_entry *ce, *stage2;\n-\n-\tfor (i = 0; i < active_nr; i++) {\n-\t\tce = active_cache[i];\n-\t\tif (ce_stage(ce) != 2)\n-\t\t\tcontinue;\n-\t\t/* hoist them up to stage 3 */\n-\t\tnamelen = ce_namelen(ce);\n-\t\tce->ce_flags = create_ce_flags(namelen, 3);\n-\t}\n-\n-\tfor (i = 0; i < active_nr; i++) {\n-\t\tce = active_cache[i];\n-\t\tif (ce_stage(ce) > 1)\n-\t\t\tcontinue;\n-\t\tnamelen = ce_namelen(ce);\n-\t\tsize = cache_entry_size(namelen);\n-\t\tstage2 = xmalloc(size);\n-\t\tmemcpy(stage2, ce, size);\n-\t\tstage2->ce_flags = create_ce_flags(namelen, 2);\n-\t\tif (add_cache_entry(stage2, ADD_CACHE_OK_TO_ADD) < 0)\n-\t\t\tdie(\"cannot merge index and our head tree\");\n-\n-\t\t/* We are done with this name, so skip to next name */\n-\t\twhile (i < active_nr &&\n-\t\t       ce_namelen(active_cache[i]) == namelen &&\n-\t\t       !memcmp(active_cache[i]->name, ce->name, namelen))\n-\t\t\ti++;\n-\t\ti--; /* compensate for the loop control */\n-\t}\n+\t\treturn deleted_entry(oldtree, current);\n }\n \n /*\n@@ -414,78 +509,21 @@ static void setup_emu23(void)\n  * The rule is:\n  * - take the stat information from stage0, take the data from stage1\n  */\n-static int oneway_merge(struct cache_entry **src, struct cache_entry **dst,\n-\t\t\tstruct cache_entry **next, int tail)\n+static int oneway_merge(struct cache_entry **src)\n {\n \tstruct cache_entry *old = src[0];\n \tstruct cache_entry *a = src[1];\n \n-\tif (src[2] || src[3])\n-\t\treturn -1;\n+\tif (merge_size != 1)\n+\t\treturn error(\"Cannot do a oneway merge of %d trees\\n\",\n+\t\t\t     merge_size);\n \n \tif (!a)\n \t\treturn 0;\n \tif (old && same(old, a)) {\n-\t\t*dst++ = old;\n-\t\treturn 1;\n-\t}\n-\treturn merged_entry(a, NULL, dst);\n-}\n-\n-static void check_updates(struct cache_entry **src, int nr)\n-{\n-\tstatic struct checkout state = {\n-\t\t.base_dir = \"\",\n-\t\t.force = 1,\n-\t\t.quiet = 1,\n-\t\t.refresh_cache = 1,\n-\t};\n-\tunsigned short mask = htons(CE_UPDATE);\n-\twhile (nr--) {\n-\t\tstruct cache_entry *ce = *src++;\n-\t\tif (!ce->ce_mode) {\n-\t\t\tif (update)\n-\t\t\t\tunlink(ce->name);\n-\t\t\tcontinue;\n-\t\t}\n-\t\tif (ce->ce_flags & mask) {\n-\t\t\tce->ce_flags &= ~mask;\n-\t\t\tif (update)\n-\t\t\t\tcheckout_entry(ce, &state);\n-\t\t}\n-\t}\n-}\n-\n-typedef int (*merge_fn_t)(struct cache_entry **, struct cache_entry **, struct cache_entry **, int);\n-\n-static void merge_cache(struct cache_entry **src, int nr, merge_fn_t fn)\n-{\n-\tstruct cache_entry **dst = src;\n-\tint tail = nr;\n-\n-\twhile (nr) {\n-\t\tint entries;\n-\t\tstruct cache_entry *name, *ce, *stages[4] = { NULL, };\n-\n-\t\tname = ce = *src;\n-\t\tfor (;;) {\n-\t\t\tint stage = ce_stage(ce);\n-\t\t\tstages[stage] = ce;\n-\t\t\tce = *++src;\n-\t\t\tactive_nr--;\n-\t\t\tif (!--nr)\n-\t\t\t\tbreak;\n-\t\t\tif (!path_matches(ce, name))\n-\t\t\t\tbreak;\n-\t\t}\n-\n-\t\tentries = fn(stages, dst, src, tail);\n-\t\tif (entries < 0)\n-\t\t\treject_merge(name);\n-\t\tdst += entries;\n-\t\tactive_nr += entries;\n+\t\treturn keep_entry(old);\n \t}\n-\tcheck_updates(active_cache, active_nr);\n+\treturn merged_entry(a, NULL);\n }\n \n static int read_cache_unmerged(void)\n@@ -516,8 +554,9 @@ static struct cache_file cache_file;\n \n int main(int argc, char **argv)\n {\n-\tint i, newfd, merge, reset, emu23;\n+\tint i, newfd, reset, stage = 0;\n \tunsigned char sha1[20];\n+\tmerge_fn_t fn = NULL;\n \n \tnewfd = hold_index_file_for_update(&cache_file, get_index_file());\n \tif (newfd < 0)\n@@ -525,7 +564,6 @@ int main(int argc, char **argv)\n \n \tmerge = 0;\n \treset = 0;\n-\temu23 = 0;\n \tfor (i = 1; i < argc; i++) {\n \t\tconst char *arg = argv[i];\n \n@@ -537,7 +575,7 @@ int main(int argc, char **argv)\n \n \t\t/* This differs from \"-m\" in that we'll silently ignore unmerged entries */\n \t\tif (!strcmp(arg, \"--reset\")) {\n-\t\t\tif (stage || merge || emu23)\n+\t\t\tif (stage || merge)\n \t\t\t\tusage(read_tree_usage);\n \t\t\treset = 1;\n \t\t\tmerge = 1;\n@@ -546,9 +584,14 @@ int main(int argc, char **argv)\n \t\t\tcontinue;\n \t\t}\n \n+\t\tif (!strcmp(arg, \"--head\")) {\n+\t\t\thead_idx = stage - 1;\n+\t\t\tfn = threeway_merge;\n+\t\t}\n+\n \t\t/* \"-m\" stands for \"merge\", meaning we start in stage 1 */\n \t\tif (!strcmp(arg, \"-m\")) {\n-\t\t\tif (stage || merge || emu23)\n+\t\t\tif (stage || merge)\n \t\t\t\tusage(read_tree_usage);\n \t\t\tif (read_cache_unmerged())\n \t\t\t\tdie(\"you need to resolve your current index first\");\n@@ -557,45 +600,41 @@ int main(int argc, char **argv)\n \t\t\tcontinue;\n \t\t}\n \n-\t\t/* \"-emu23\" uses 3-way merge logic to perform fast-forward */\n-\t\tif (!strcmp(arg, \"--emu23\")) {\n-\t\t\tif (stage || merge || emu23)\n-\t\t\t\tusage(read_tree_usage);\n-\t\t\tif (read_cache_unmerged())\n-\t\t\t\tdie(\"you need to resolve your current index first\");\n-\t\t\tmerge = emu23 = stage = 1;\n-\t\t\tcontinue;\n-\t\t}\n-\n \t\tif (get_sha1(arg, sha1) < 0)\n \t\t\tusage(read_tree_usage);\n-\t\tif (stage > 3)\n-\t\t\tusage(read_tree_usage);\n-\t\tif (unpack_tree(sha1) < 0)\n+\t\tif (list_tree(sha1) < 0)\n \t\t\tdie(\"failed to unpack tree object %s\", arg);\n \t\tstage++;\n \t}\n \tif (update && !merge)\n \t\tusage(read_tree_usage);\n-\tif (merge) {\n-\t\tstatic const merge_fn_t merge_function[] = {\n-\t\t\t[1] = oneway_merge,\n-\t\t\t[2] = twoway_merge,\n-\t\t\t[3] = threeway_merge,\n-\t\t};\n-\t\tmerge_fn_t fn;\n-\n-\t\tif (stage < 2 || stage > 4)\n+\tif (merge && !fn) {\n+\t\tif (stage < 2)\n \t\t\tdie(\"just how do you expect me to merge %d trees?\", stage-1);\n-\t\tif (emu23 && stage != 3)\n-\t\t\tdie(\"--emu23 takes only two trees\");\n-\t\tfn = merge_function[stage-1];\n-\t\tif (stage == 3 && emu23) { \n-\t\t\tsetup_emu23();\n-\t\t\tfn = merge_function[3];\n+\t\tswitch (stage - 1) {\n+\t\tcase 1:\n+\t\t\tfn = oneway_merge;\n+\t\t\tbreak;\n+\t\tcase 2:\n+\t\t\tfn = twoway_merge;\n+\t\t\tbreak;\n+\t\tcase 3:\n+\t\t\tfn = threeway_merge;\n+\t\t\tbreak;\n+\t\tdefault:\n+\t\t\tfn = threeway_merge;\n+\t\t\tbreak;\n \t\t}\n-\t\tmerge_cache(active_cache, active_nr, fn);\n \t}\n+\n+\tif (head_idx < 0) {\n+\t\tif (stage - 1 >= 3)\n+\t\t\thead_idx = stage - 2;\n+\t\telse\n+\t\t\thead_idx = 1;\n+\t}\n+\n+\tunpack_trees(fn);\n \tif (write_cache(newfd, active_cache, active_nr) ||\n \t    commit_index_file(&cache_file))\n \t\tdie(\"unable to write new index file\");\ndiff --git a/t/t1005-read-tree-m-2way-emu23.sh b/t/t1005-read-tree-m-2way-emu23.sh\ndeleted file mode 100755\n--- a/t/t1005-read-tree-m-2way-emu23.sh\n+++ /dev/null\n@@ -1,422 +0,0 @@\n-#!/bin/sh\n-#\n-# Copyright (c) 2005 Junio C Hamano\n-#\n-\n-test_description='Two way merge with read-tree --emu23 $H $M\n-\n-This test tries two-way merge (aka fast forward with carry forward).\n-\n-There is the head (called H) and another commit (called M), which is\n-simply ahead of H.  The index and the work tree contains a state that\n-is derived from H, but may also have local changes.  This test checks\n-all the combinations described in the two-tree merge \"carry forward\"\n-rules, found in <Documentation/git-rev-tree.txt>.\n-\n-In the test, these paths are used:\n-        bozbar  - in H, stays in M, modified from bozbar to gnusto\n-        frotz   - not in H added in M\n-        nitfol  - in H, stays in M unmodified\n-        rezrov  - in H, deleted in M\n-        yomin   - not in H nor M\n-'\n-. ./test-lib.sh\n-\n-read_tree_twoway () {\n-    git-read-tree --emu23 \"$1\" \"$2\" &&\n-    git-ls-files --stage &&\n-    git-merge-cache git-merge-one-file-script -a &&\n-    git-ls-files --stage\n-}\n-\n-_x40='[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]'\n-_x40=\"$_x40$_x40$_x40$_x40$_x40$_x40$_x40$_x40\"\n-compare_change () {\n-\tsed -n >current \\\n-\t    -e '/^--- /d; /^+++ /d; /^@@ /d;' \\\n-\t    -e 's/^\\([-+][0-7][0-7][0-7][0-7][0-7][0-7]\\) '\"$_x40\"' /\\1 X /p' \\\n-\t    \"$1\"\n-\tdiff -u expected current\n-}\n-\n-check_cache_at () {\n-\tclean_if_empty=`git-diff-files \"$1\"`\n-\tcase \"$clean_if_empty\" in\n-\t'')  echo \"$1: clean\" ;;\n-\t?*)  echo \"$1: dirty\" ;;\n-\tesac\n-\tcase \"$2,$clean_if_empty\" in\n-\tclean,)\t\t:     ;;\n-\tclean,?*)\tfalse ;;\n-\tdirty,)\t\tfalse ;;\n-\tdirty,?*)\t:     ;;\n-\tesac\n-}\n-\n-check_stages () {\n-    cat >expected_stages\n-    git-ls-files --stage | sed -e \"s/ $_x40 / X /\" >current_stages\n-    diff -u expected_stages current_stages\n-}\n-\n-cat >bozbar-old <<\\EOF\n-This is a sample file used in two-way fast forward merge\n-tests.  Its second line ends with a magic word bozbar\n-which will be modified by the merged head to gnusto.\n-It has some extra lines so that external tools can\n-successfully merge independent changes made to later\n-lines (such as this one), avoiding line conflicts.\n-EOF\n-\n-sed -e 's/bozbar/gnusto (earlier bozbar)/' bozbar-old >bozbar-new\n-\n-test_expect_success \\\n-    setup \\\n-    'echo frotz >frotz &&\n-     echo nitfol >nitfol &&\n-     cat bozbar-old >bozbar &&\n-     echo rezrov >rezrov &&\n-     echo yomin >yomin &&\n-     git-update-cache --add nitfol bozbar rezrov &&\n-     treeH=`git-write-tree` &&\n-     echo treeH $treeH &&\n-     git-ls-tree $treeH &&\n-\n-     cat bozbar-new >bozbar &&\n-     git-update-cache --add frotz bozbar --force-remove rezrov &&\n-     git-ls-files --stage >M.out &&\n-     treeM=`git-write-tree` &&\n-     echo treeM $treeM &&\n-     git-ls-tree $treeM &&\n-     git-diff-tree $treeH $treeM'\n-\n-# \"read-tree -m H I+H M\" but I is empty so this is \"read-tree -m H H M\".\n-#\n-# bozbar [O && A && B && O==A && O!=B (#14) ==> B] take M by read-tree\n-# frotz  [!O && !A && B (#2) ==> B]                take M by read-tree\n-# nitfol [O && A && B && O==A && O==B (#15) ==> B] take M by read-tree\n-# rezrov [O && A && !B && O==A (#10) ==> no merge] removed by script\n-#\n-# Earlier one did not have #2ALT so taking M was done by the script,\n-# which also updated the work tree and making frotz clean.  With #2ALT,\n-# this is resolved by read-tree itself and the path is left dirty\n-# because we are not testing \"read-tree -u --emu23\".\n-test_expect_success \\\n-    '1, 2, 3 - no carry forward' \\\n-    'rm -f .git/index &&\n-     read_tree_twoway $treeH $treeM &&\n-     git-ls-files --stage >1-3.out &&\n-     diff -u M.out 1-3.out &&\n-     check_cache_at bozbar dirty &&\n-     check_cache_at frotz dirty && # same as pure 2-way again.\n-     check_cache_at nitfol dirty'\n-\n-echo '+100644 X 0\tyomin' >expected\n-\n-test_expect_success \\\n-    '4 - carry forward local addition.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     git-update-cache --add yomin &&\n-     read_tree_twoway $treeH $treeM &&\n-     git-ls-files --stage >4.out || return 1\n-     diff -u M.out 4.out >4diff.out\n-     compare_change 4diff.out expected &&\n-     check_cache_at yomin clean'\n-\n-# \"read-tree -m H I+H M\" where !H && !M; so (I+H) not being up-to-date\n-# should not matter.  Thanks to #3ALT, this is now possible.\n-test_expect_success \\\n-    '5 - carry forward local addition.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     echo yomin >yomin &&\n-     git-update-cache --add yomin &&\n-     echo yomin yomin >yomin &&\n-     read_tree_twoway $treeH $treeM &&\n-     git-ls-files --stage >5.out || return 1\n-     diff -u M.out 5.out >5diff.out\n-     compare_change 5diff.out expected &&\n-     check_cache_at yomin dirty'\n-\n-# \"read-tree -m H I+H M\" where !H && M && (I+H) == M, so this should\n-# succeed (even the entry is clean), now thanks to #5ALT.\n-test_expect_success \\\n-    '6 - local addition already has the same.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     git-update-cache --add frotz &&\n-     read_tree_twoway $treeH $treeM &&\n-     git-ls-files --stage >6.out &&\n-     diff -u M.out 6.out &&\n-     check_cache_at frotz clean'\n-\n-# Exactly the same pattern as above but with dirty cache.  This also\n-# should succeed, now thanks to #5ALT.\n-test_expect_success \\\n-    '7 - local addition already has the same.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     echo frotz >frotz &&\n-     git-update-cache --add frotz &&\n-     echo frotz frotz >frotz &&\n-     read_tree_twoway $treeH $treeM &&\n-     git-ls-files --stage >7.out &&\n-     diff -u M.out 7.out &&\n-     check_cache_at frotz dirty'\n-\n-test_expect_success \\\n-    '8 - conflicting addition.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     echo frotz frotz >frotz &&\n-     git-update-cache --add frotz &&\n-     if read_tree_twoway $treeH $treeM; then false; else :; fi'\n-\n-test_expect_success \\\n-    '9 - conflicting addition.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     echo frotz frotz >frotz &&\n-     git-update-cache --add frotz &&\n-     echo frotz >frotz &&\n-     if read_tree_twoway $treeH $treeM; then false; else :; fi'\n-\n-test_expect_success \\\n-    '10 - path removed.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     echo rezrov >rezrov &&\n-     git-update-cache --add rezrov &&\n-     read_tree_twoway $treeH $treeM &&\n-     git-ls-files --stage >10.out &&\n-     diff -u M.out 10.out'\n-\n-test_expect_success \\\n-    '11 - dirty path removed.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     echo rezrov >rezrov &&\n-     git-update-cache --add rezrov &&\n-     echo rezrov rezrov >rezrov &&\n-     if read_tree_twoway $treeH $treeM; then false; else :; fi'\n-\n-test_expect_success \\\n-    '12 - unmatching local changes being removed.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     echo rezrov rezrov >rezrov &&\n-     git-update-cache --add rezrov &&\n-     if read_tree_twoway $treeH $treeM; then false; else :; fi'\n-\n-test_expect_success \\\n-    '13 - unmatching local changes being removed.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     echo rezrov rezrov >rezrov &&\n-     git-update-cache --add rezrov &&\n-     echo rezrov >rezrov &&\n-     if read_tree_twoway $treeH $treeM; then false; else :; fi'\n-\n-cat >expected <<EOF\n--100644 X 0\tnitfol\n-+100644 X 0\tnitfol\n-EOF\n-\n-test_expect_success \\\n-    '14 - unchanged in two heads.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     echo nitfol nitfol >nitfol &&\n-     git-update-cache --add nitfol &&\n-     read_tree_twoway $treeH $treeM &&\n-     git-ls-files --stage >14.out || return 1\n-     diff -u M.out 14.out >14diff.out\n-     compare_change 14diff.out expected &&\n-     check_cache_at nitfol clean'\n-\n-test_expect_success \\\n-    '15 - unchanged in two heads.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     echo nitfol nitfol >nitfol &&\n-     git-update-cache --add nitfol &&\n-     echo nitfol nitfol nitfol >nitfol &&\n-     read_tree_twoway $treeH $treeM &&\n-     git-ls-files --stage >15.out || return 1\n-     diff -u M.out 15.out >15diff.out\n-     compare_change 15diff.out expected &&\n-     check_cache_at nitfol dirty'\n-\n-# This is different from straight 2-way merge in that it leaves\n-# three stages of bozbar in the index file without failing, so\n-# the user can run git-diff-stages to examine the situation.\n-# With #2ALT, frotz is resolved internally.\n-test_expect_success \\\n-    '16 - conflicting local change.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     echo bozbar bozbar >bozbar &&\n-     git-update-cache --add bozbar &&\n-     git-read-tree --emu23 $treeH $treeM &&\n-     check_stages' <<\\EOF\n-100644 X 1\tbozbar\n-100644 X 2\tbozbar\n-100644 X 3\tbozbar\n-100644 X 0\tfrotz\n-100644 X 0\tnitfol\n-100644 X 1\trezrov\n-100644 X 2\trezrov\n-EOF\n-\n-test_expect_success \\\n-    '17 - conflicting local change.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     echo bozbar bozbar >bozbar &&\n-     git-update-cache --add bozbar &&\n-     echo bozbar bozbar bozbar >bozbar &&\n-     if read_tree_twoway $treeH $treeM; then false; else :; fi'\n-\n-test_expect_success \\\n-    '18 - local change already having a good result.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     cat bozbar-new >bozbar &&\n-     git-update-cache --add bozbar &&\n-     read_tree_twoway $treeH $treeM &&\n-     git-ls-files --stage >18.out &&\n-     diff -u M.out 18.out &&\n-     check_cache_at bozbar clean'\n-\n-test_expect_success \\\n-    '19 - local change already having a good result, further modified.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     cat bozbar-new >bozbar &&\n-     git-update-cache --add bozbar &&\n-     echo gnusto gnusto >bozbar &&\n-     read_tree_twoway $treeH $treeM &&\n-     git-ls-files --stage >19.out &&\n-     diff -u M.out 19.out &&\n-     check_cache_at bozbar dirty'\n-\n-test_expect_success \\\n-    '20 - no local change, use new tree.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     cat bozbar-old >bozbar &&\n-     git-update-cache --add bozbar &&\n-     read_tree_twoway $treeH $treeM &&\n-     git-ls-files --stage >20.out &&\n-     diff -u M.out 20.out &&\n-     check_cache_at bozbar dirty'\n-\n-test_expect_success \\\n-    '21 - no local change, dirty cache.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     cat bozbar-old >bozbar &&\n-     git-update-cache --add bozbar &&\n-     echo gnusto gnusto >bozbar &&\n-     if read_tree_twoway $treeH $treeM; then false; else :; fi'\n-\n-echo '-100644 X 0\tbozbar\n-+100644 X 0\tbozbar' >expected\n-\n-# This fails with straight two-way fast forward, but emu23\n-# can merge them.\n-test_expect_success \\\n-    '22 - local change cache updated.' \\\n-    'rm -f .git/index &&\n-     git-read-tree $treeH &&\n-     git-checkout-cache -u -f -q -a &&\n-     sed -e \"s/such as/SUCH AS/\" bozbar-old >bozbar &&\n-     git-update-cache --add bozbar &&\n-     read_tree_twoway $treeH $treeM &&\n-     git-ls-files --stage >22.out || return 1\n-     diff -u M.out 22.out >22diff.out\n-     compare_change 22diff.out &&\n-     check_cache_at bozbar clean'\n-\n-# Also make sure we did not break DF vs DF/DF case.\n-test_expect_success \\\n-    'DF vs DF/DF case setup.' \\\n-    'rm -f .git/index &&\n-     echo DF >DF &&\n-     git-update-cache --add DF &&\n-     treeDF=`git-write-tree` &&\n-     echo treeDF $treeDF &&\n-     git-ls-tree $treeDF &&\n-     git-ls-files --stage >DF.out\n-\n-     rm -f DF &&\n-     mkdir DF &&\n-     echo DF/DF >DF/DF &&\n-     git-update-cache --add --remove DF DF/DF &&\n-     treeDFDF=`git-write-tree` &&\n-     echo treeDFDF $treeDFDF &&\n-     git-ls-tree $treeDFDF &&\n-     git-ls-files --stage >DFDF.out'\n-\n-test_expect_success \\\n-    'DF vs DF/DF case test (#1)' \\\n-    'rm -f .git/index &&\n-     rm -fr DF &&\n-     echo DF >DF &&\n-     git-update-cache --add DF &&\n-     read_tree_twoway $treeDF $treeDFDF &&\n-     git-ls-files --stage >DFDFcheck.out &&\n-     diff -u DFDF.out DFDFcheck.out &&\n-     check_cache_at DF/DF clean && # different from pure 2-way\n-     :'\n-\n-# The other way around\n-test_expect_success \\\n-    'DF vs DF/DF case test (#2)' \\\n-    'rm -f .git/index &&\n-     rm -fr DF &&\n-     mkdir DF &&\n-     echo DF/DF >DF/DF &&\n-     git-update-cache --add DF/DF &&\n-     read_tree_twoway $treeDFDF $treeDF &&\n-     git-ls-files --stage >DFDFcheck.out &&\n-     diff -u DF.out DFDFcheck.out &&\n-     check_cache_at DF clean && # different from pure 2-way\n-     :'\n-\n-# Emu23 can grok I having more than H.  Make sure we did not\n-# botch the conflict tests (fixed).\n-test_expect_success \\\n-    'DF vs DF/DF case test (#3).' \\\n-    'rm -f .git/index &&\n-     rm -fr DF &&\n-     mkdir DF &&\n-     echo DF/DF >DF/DF &&\n-     git-update-cache --add DF/DF &&\n-     # This should fail because I and H have a conflict\n-     # at DF.\n-     if git-read-tree --emu23 $treeDF $treeDFDF\n-     then false\n-     else true\n-     fi'\n-\n-test_done\n"},{"id":"8083","messageId":"Pine.LNX.4.63.0509050204500.23242@iabervon.org","threadId":"1729","inReplyTo":"Pine.LNX.4.63.0509050151240.23242@iabervon.org","subject":"[PATCH 4/4] Document the trivial merge rules for 3(+more ancestors)-way merges.","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-05T06:05:17Z","receivedAt":"2005-09-05T06:05:17Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"Signed-off-by: Daniel Barkalow\n---\n\n Documentation/technical/trivial-merge.txt |   92 +++++++++++++++++++++++++++++\n 1 files changed, 92 insertions(+), 0 deletions(-)\n create mode 100644 Documentation/technical/trivial-merge.txt\n\n7544be0a8eda7b796150729a7795c2639278da62\ndiff --git a/Documentation/technical/trivial-merge.txt b/Documentation/technical/trivial-merge.txt\nnew file mode 100644\n--- /dev/null\n+++ b/Documentation/technical/trivial-merge.txt\n@@ -0,0 +1,92 @@\n+Trivial merge rules\n+===================\n+\n+This document describes the outcomes of the trivial merge logic in read-tree.\n+\n+One-way merge\n+-------------\n+\n+This replaces the index with a different tree, keeping the stat info\n+for entries that don't change, and allowing -u to make the minimum\n+required changes to the working tree to have it match.\n+\n+   index   tree    result\n+   -----------------------\n+   *       (empty) (empty)\n+   (empty) tree    tree\n+   index+  tree    tree\n+   index+  index   index+\n+\n+Two-way merge\n+-------------\n+\n+\n+\n+Three-way merge\n+---------------\n+\n+It is permitted for the index to lack an entry; this does not prevent\n+any case from applying.\n+\n+If the index exists, it is an error for it not to match either the\n+head or (if the merge is trivial) the result.\n+\n+If multiple cases apply, the one used is listed first.\n+\n+A result of \"no merge\" means that index is left in stage 0, ancest in\n+stage 1, head in stage 2, and remote in stage 3 (if any of these are\n+empty, no entry is left for that stage). Otherwise, the given entry is\n+left in stage 0, and there are no other entries.\n+\n+A result of \"no merge\" is an error if the index is not empty and not\n+up-to-date.\n+\n+*empty* means that the tree must not have a directory-file conflict\n+ with the entry.\n+\n+For multiple ancestors or remotes, a '+' means that this case applies\n+even if only one ancestor or remote fits; normally, all of the\n+ancestors or remotes must be the same.\n+\n+case  ancest    head    remote    result\n+----------------------------------------\n+1     (empty)+  (empty) (empty)   (empty)\n+2ALT  (empty)+  *empty* remote    remote\n+2ALT  (empty)+  *empty* remote    remote\n+2     (empty)^  (empty) remote    no merge\n+3ALT  (empty)+  head    *empty*   head\n+3     (empty)^  head    (empty)   no merge\n+4     (empty)^  head    remote    no merge\n+5ALT  *         head    head      head\n+6     ancest^   (empty) (empty)   no merge\n+8ALT  ancest    (empty) ancest    (empty)\n+7     ancest+   (empty) remote    no merge\n+9     ancest+   head    (empty)   no merge\n+10ALT ancest    ancest  (empty)   (empty)\n+11    ancest+   head    remote    no merge\n+16    anc1/anc2 anc1    anc2      no merge\n+13    ancest+   head    ancest    head\n+14    ancest+   ancest  remote    remote\n+14ALT ancest+   ancest  remote    remote\n+\n+Only #2ALT and #3ALT use *empty*, because these are the only cases\n+where there can be conflicts that didn't exist before. Note that we\n+allow directory-file conflicts between things in different stages\n+after the trivial merge.\n+\n+A possible alternative for #6 is (empty), which would make it like\n+#1. This is not used, due to the likelihood that it arises due to\n+moving the file to multiple different locations or moving and deleting\n+it in different branches.\n+\n+Case #1 is included for completeness, and also in case we decide to\n+put on '+' markings; any path that is never mentioned at all isn't\n+handled.\n+\n+Note that #16 is when both #13 and #14 apply; in this case, we refuse\n+the trivial merge, because we can't tell from this data which is\n+right. This is a case of a reverted patch (in some direction, maybe\n+multiple times), and the right answer depends on looking at crossings\n+of history or common ancestors of the ancestors.\n+\n+The status as of Sep 5 is that multiple remotes are not supported\n\\ No newline at end of file\n"}]}