{"thread":{"id":"907","subject":"[PATCH 4/3] Finish making --emu23 equivalent to pure 2-way merge.","startedAt":"2005-06-11T09:50:51Z","lastAt":"2005-06-11T09:50:51Z","messageCount":1,"participants":["Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"4868","messageId":"7voeadxlvo.fsf@assigned-by-dhcp.cox.net","threadId":"907","inReplyTo":null,"subject":"[PATCH 4/3] Finish making --emu23 equivalent to pure 2-way merge.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-06-11T09:50:51Z","receivedAt":"2005-06-11T09:50:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This adds #3ALT rule (and #2ALT rule for symmetry) to the\nread-tree 3-way merge logic that collapses paths that are added\nonly in one branch and not in the other internally.\n\nThis makes --emu23 to succeed in the last remaining case where\nthe pure 2-way merge succeeded and earlier one failed.  Running\ndiff between t1001 and t1005 test scripts shows that the only\ndifference between the two is that --emu23 can leave the states\ninto separate stages so that the user can use usual 3-way merge\nresolution techniques to carry forward the local changes when\npure 2-way merge would have refused to run.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\n*** This is leftover bits from the earlier 3-piece series.\n\n read-tree.c                       |  137 ++++++++++++++++++++++++++++++++++++-\n t/t1000-read-tree-m-3way.sh       |   32 +++++----\n t/t1005-read-tree-m-2way-emu23.sh |   20 ++++-\n 3 files changed, 168 insertions(+), 21 deletions(-)\n\ndiff --git a/read-tree.c b/read-tree.c\n--- a/read-tree.c\n+++ b/read-tree.c\n@@ -143,7 +143,72 @@ static int deleted_entry(struct cache_en\n \treturn 1;\n }\n \n-static int threeway_merge(struct cache_entry *stages[4], struct cache_entry **dst)\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+}\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@@ -156,6 +221,65 @@ static int threeway_merge(struct cache_e\n \t\t\treturn -1;\n \t\treturn merged_entry_allow_dirty(b, old, dst);\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/*\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@@ -186,7 +310,8 @@ 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+static int twoway_merge(struct cache_entry **src, struct cache_entry **dst,\n+\t\t\tstruct cache_entry **next, int tail)\n {\n \tstruct cache_entry *current = src[0];\n \tstruct cache_entry *oldtree = src[1], *newtree = src[2];\n@@ -283,7 +408,8 @@ 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+static int oneway_merge(struct cache_entry **src, struct cache_entry **dst,\n+\t\t\tstruct cache_entry **next, int tail)\n {\n \tstruct cache_entry *old = src[0];\n \tstruct cache_entry *a = src[1];\n@@ -324,11 +450,12 @@ static void check_updates(struct cache_e\n \t}\n }\n \n-typedef int (*merge_fn_t)(struct cache_entry **, struct cache_entry **);\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@@ -346,7 +473,7 @@ static void merge_cache(struct cache_ent\n \t\t\t\tbreak;\n \t\t}\n \n-\t\tentries = fn(stages, dst);\n+\t\tentries = fn(stages, dst, src, tail);\n \t\tif (entries < 0)\n \t\t\treject_merge(name);\n \t\tdst += entries;\ndiff --git a/t/t1000-read-tree-m-3way.sh b/t/t1000-read-tree-m-3way.sh\n--- a/t/t1000-read-tree-m-3way.sh\n+++ b/t/t1000-read-tree-m-3way.sh\n@@ -75,13 +75,13 @@ In addition:\n . ../lib-read-tree-m-3way.sh\n \n ################################################################\n-# Trivial \"majority when 3 stages exist\" merge plus #5ALT trivial\n-# merge.\n+# Trivial \"majority when 3 stages exist\" merge plus #2ALT, #3ALT\n+# and #5ALT trivial merges.\n \n cat >expected <<\\EOF\n 100644 X 2\tAA\n 100644 X 3\tAA\n-100644 X 2\tAN\n+100644 X 0\tAN\n 100644 X 1\tDD\n 100644 X 3\tDF\n 100644 X 2\tDF/DF\n@@ -96,7 +96,7 @@ cat >expected <<\\EOF\n 100644 X 2\tMM\n 100644 X 3\tMM\n 100644 X 0\tMN\n-100644 X 3\tNA\n+100644 X 0\tNA\n 100644 X 1\tND\n 100644 X 2\tND\n 100644 X 0\tNM\n@@ -107,7 +107,7 @@ cat >expected <<\\EOF\n 100644 X 3\tTT\n 100644 X 2\tZ/AA\n 100644 X 3\tZ/AA\n-100644 X 2\tZ/AN\n+100644 X 0\tZ/AN\n 100644 X 1\tZ/DD\n 100644 X 1\tZ/DM\n 100644 X 3\tZ/DM\n@@ -119,7 +119,7 @@ cat >expected <<\\EOF\n 100644 X 2\tZ/MM\n 100644 X 3\tZ/MM\n 100644 X 0\tZ/MN\n-100644 X 3\tZ/NA\n+100644 X 0\tZ/NA\n 100644 X 1\tZ/ND\n 100644 X 2\tZ/ND\n 100644 X 0\tZ/NM\n@@ -233,23 +233,31 @@ test_expect_failure \\\n      git-update-cache --add XX &&\n      git-read-tree -m $tree_O $tree_A $tree_B\"\n \n-test_expect_failure \\\n-    '2 - must not have an entry not in A.' \\\n+test_expect_success \\\n+    '2 - must match B in !O && !A && B case.' \\\n+    \"rm -f .git/index NA &&\n+     cp .orig-B/NA NA &&\n+     git-update-cache --add NA &&\n+     git-read-tree -m $tree_O $tree_A $tree_B\"\n+\n+test_expect_success \\\n+    '2 - matching B alone is OK in !O && !A && B case.' \\\n     \"rm -f .git/index NA &&\n      cp .orig-B/NA NA &&\n      git-update-cache --add NA &&\n+     echo extra >>NA &&\n      git-read-tree -m $tree_O $tree_A $tree_B\"\n \n test_expect_success \\\n-    '3 - must match and be up-to-date in !O && A && !B case.' \\\n+    '3 - must match A in !O && A && !B case.' \\\n     \"rm -f .git/index AN &&\n      cp .orig-A/AN AN &&\n      git-update-cache --add AN &&\n      git-read-tree -m $tree_O $tree_A $tree_B &&\n      check_result\"\n \n-test_expect_failure \\\n-    '3 (fail) - must match and be up-to-date in !O && A && !B case.' \\\n+test_expect_success \\\n+    '3 - matching A alone is OK in !O && A && !B case.' \\\n     \"rm -f .git/index AN &&\n      cp .orig-A/AN AN &&\n      git-update-cache --add AN &&\n@@ -257,7 +265,7 @@ test_expect_failure \\\n      git-read-tree -m $tree_O $tree_A $tree_B\"\n \n test_expect_failure \\\n-    '3 (fail) - must match and be up-to-date in !O && A && !B case.' \\\n+    '3 (fail) - must match A in !O && A && !B case.' \\\n     \"rm -f .git/index AN &&\n      cp .orig-A/AN AN &&\n      echo extra >>AN &&\ndiff --git a/t/t1005-read-tree-m-2way-emu23.sh b/t/t1005-read-tree-m-2way-emu23.sh\n--- a/t/t1005-read-tree-m-2way-emu23.sh\n+++ b/t/t1005-read-tree-m-2way-emu23.sh\n@@ -80,6 +80,17 @@ test_expect_success \\\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@@ -87,7 +98,7 @@ test_expect_success \\\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 clean && # different from pure 2-way\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@@ -103,8 +114,8 @@ test_expect_success \\\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, but without #3ALT this does not work.\n-: test_expect_success \\\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      echo yomin >yomin &&\n@@ -218,6 +229,7 @@ test_expect_success \\\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@@ -228,7 +240,7 @@ test_expect_success \\\n 100644 X 1\tbozbar\n 100644 X 2\tbozbar\n 100644 X 3\tbozbar\n-100644 X 3\tfrotz\n+100644 X 0\tfrotz\n 100644 X 0\tnitfol\n 100644 X 1\trezrov\n 100644 X 2\trezrov\n------------\n\n"}]}