{"thread":{"id":"6853","subject":"[PATCH] A new merge stragety 'subtree'.","startedAt":"2007-02-17T01:49:14Z","lastAt":"2007-02-17T18:04:55Z","messageCount":9,"participants":["Junio C Hamano","Shawn O. Pearce"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"34844","messageId":"7vfy95y2n9.fsf@assigned-by-dhcp.cox.net","threadId":"6853","inReplyTo":null,"subject":"[PATCH] A new merge stragety 'subtree'.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-02-17T01:49:14Z","receivedAt":"2007-02-17T01:49:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I've explained how I initially merged from Shawn's git-gui, but\nsome people might have wondered how I continue to pull from\nhim.  I published the secret on 'pu' last night, but here is an\nupdate that I currently have in my tree (still in 'pu').\n\nThe new merge strategy 'subtree' is a slightly modified\n'recursive'.  It merges current branch A with other branch\nB using common merge base O (and if there are more than one\ncommon merge bases, they are recursively merged), but it can \n\"shift\" trees while doing so.\n\nI did the initial git-gui merge in commit b4d2b0.  Later, I\nneeded to get some updates so I created commit 67c7575.\n\n\n                 b4d2b0  d63ea11\n git.git    ----o---*-------o---* 67c7575\n                   /           /\n git-gui.git   ---o------o----o fdf6cfc\n            0960f7d\n\nThe commit before the merge (d63ea11) has slightly older tree\ncontents from git-gui repository, but all renamed to be under\ngit-gui/ directory.\n\n        $ git diff --numstat d63ea11:git-gui fdf6cfc^{tree}\n        43\t12\tGIT-VERSION-GEN\n        14\t6\tMakefile\n        1\t1\tgit-gui.sh\n\nWhat merge-subtree does, when doing tree-level three-way merge\nbetween A and B based on O (that is, merge-subtree O -- A B) is\nto 'shift' B to match the tree shape of A.\n\nThe tree-shifting is a fun operation, as it sometimes needs to\nshift up and sometimes shift down.  When B looks like a subtree\nin A, we create a copy of A's tree, and replace the subtree that\ncorresponds to B with B's tree.  When A looks like a subtree in\nB, then we just pick the subtree that corresponds to A's tree\nout of B (discarding the other parts of it).\n\nThe same tree-shifting is done for the merge base to make it\nlook like A.  Then merge-recursive does its job just as usual.\nThe commit 67c7575 was made by shifting Shawn's tree down,\nreplacing the tree at git-gui in d63ea11 with fdf6cfc.\n\nIt works the other way as well.  Shawn can pull d63ea11 from me\nto his tree with subtree strategy.  In this case, he will be\nshifting my tree up, using only the tree that corresponds to\ngit-gui/ subdirectory.\n\nWhat's interesting is that this makes merge an asymmetric\noperation.  The resulting tree from such a pull will not look\nlike what I have in 67c7575; it will be only the git-gui subtree\nof it.\n\nFor normal merge strategies, if you are on branch A and merge\nbranch B into it, what you will get is exactly the same as what\nyou would get by merging branch A while being on branch A\n(modulo the direction of conflict markers).  With the subtree\nmerge, it is not the case anymore.  If I pull from git-gui.git,\nthe resulting tree look like git.git with Shawn's updates.  If\nShawn pulls from git.git, even after I did some changes on my\nown to git-gui subdirectory, bypassing his tree, he will get a\nmerged result pertaining to git-gui.git repository\n(i.e. git-gui/ subdirectory of what I have).  This way, we can\ncontinue merging from each other.\n\nAlthough I do not plan to commit anything in git-gui/ part of my\ntree myself, bypassing Shawn, it is nice to know that it will\nnot introduce problems down the road.\n\nThe subtree merge strategy is inherently incompatible with\nfast-forward, so the patch teaches git-merge about it.\n\n-- >8 --\n\nThis merge strategy largely piggy-backs on git-merge-recursive.\nWhen merging trees A and B, if B corresponds to a subtree of A,\nB is first adjusted to match the tree structure of A, instead of\nreading the trees at the same level.  This adjustment is also\ndone to the common ancestor tree.\n\nIf you are pulling updates from git-gui repository into git.git\nrepository, the root level of the former corresponds to git-gui/\nsubdirectory of the latter.  The tree object of git-gui's toplevel\nis wrapped in a fake tree object, whose sole entry has name 'git-gui'\nand records object name of the true tree, before being used by\nthe 3-way merge code.\n\nIf you are merging the other way, only the git-gui/ subtree of\ngit.git is extracted and merged into git-gui's toplevel.\n\nThe detection of corresponding subtree is done by comparing the\npathnames and types in the toplevel of the tree.\n\nHeuristics galore!  That's the git way ;-).\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n .gitignore         |    2 +\n Makefile           |   10 ++-\n cache.h            |    3 +\n git-merge.sh       |    4 +-\n match-trees.c      |  301 ++++++++++++++++++++++++++++++++++++++++++++++++++++\n merge-recursive.c  |   29 +++++\n test-match-trees.c |   24 ++++\n 7 files changed, 370 insertions(+), 3 deletions(-)\n create mode 100644 match-trees.c\n create mode 100644 test-match-trees.c\n\ndiff --git a/.gitignore b/.gitignore\nindex f15155d..8f732b4 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -74,6 +74,7 @@ git-merge-ours\n git-merge-recursive\n git-merge-resolve\n git-merge-stupid\n+git-merge-subtree\n git-mktag\n git-mktree\n git-name-rev\n@@ -142,6 +143,7 @@ gitweb/gitweb.cgi\n test-date\n test-delta\n test-dump-cache-tree\n+test-match-trees\n common-cmds.h\n *.tar.gz\n *.dsc\ndiff --git a/Makefile b/Makefile\nindex ebecbbd..e255a0d 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -221,6 +221,8 @@ BUILT_INS = \\\n # what 'all' will build and 'install' will install, in gitexecdir\n ALL_PROGRAMS = $(PROGRAMS) $(SCRIPTS)\n \n+ALL_PROGRAMS += git-merge-subtree$X\n+\n # Backward compatibility -- to be removed after 1.0\n PROGRAMS += git-ssh-pull$X git-ssh-push$X\n \n@@ -260,7 +262,7 @@ LIB_OBJS = \\\n \tserver-info.o setup.o sha1_file.o sha1_name.o strbuf.o \\\n \ttag.o tree.o usage.o config.o environment.o ctype.o copy.o \\\n \trevision.o pager.o tree-walk.o xdiff-interface.o \\\n-\twrite_or_die.o trace.o list-objects.o grep.o \\\n+\twrite_or_die.o trace.o list-objects.o grep.o match-trees.o \\\n \talloc.o merge-file.o path-list.o help.o unpack-trees.o $(DIFF_OBJS) \\\n \tcolor.o wt-status.o archive-zip.o archive-tar.o shallow.o utf8.o\n \n@@ -627,6 +629,9 @@ git$X: git.c common-cmds.h $(BUILTIN_OBJS) $(GITLIBS) GIT-CFLAGS\n \n help.o: common-cmds.h\n \n+git-merge-subtree$X: git-merge-recursive$X\n+\trm -f $@ && ln git-merge-recursive$X $@\n+\n $(BUILT_INS): git$X\n \trm -f $@ && ln git$X $@\n \n@@ -827,6 +832,9 @@ test-dump-cache-tree$X: dump-cache-tree.o $(GITLIBS)\n test-sha1$X: test-sha1.o $(GITLIBS)\n \t$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $(filter %.o,$^) $(LIBS)\n \n+test-match-trees$X: test-match-trees.o $(GITLIBS)\n+\t$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $(filter %.o,$^) $(LIBS)\n+\n check-sha1:: test-sha1$X\n \t./test-sha1.sh\n \ndiff --git a/cache.h b/cache.h\nindex c62b0b0..d1e5035 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -468,4 +468,7 @@ extern int nfvasprintf(char **str, const char *fmt, va_list va);\n extern void trace_printf(const char *format, ...);\n extern void trace_argv_printf(const char **argv, int count, const char *format, ...);\n \n+/* match-trees.c */\n+void shift_tree(const unsigned char *, const unsigned char *, unsigned char *, int);\n+\n #endif /* CACHE_H */\ndiff --git a/git-merge.sh b/git-merge.sh\nindex 498c938..f406795 100755\n--- a/git-merge.sh\n+++ b/git-merge.sh\n@@ -16,10 +16,10 @@ test -z \"$(git ls-files -u)\" ||\n LF='\n '\n \n-all_strategies='recur recursive octopus resolve stupid ours'\n+all_strategies='recur recursive octopus resolve stupid ours subtree'\n default_twohead_strategies='recursive'\n default_octopus_strategies='octopus'\n-no_trivial_merge_strategies='ours'\n+no_trivial_merge_strategies='ours subtree'\n use_strategies=\n \n index_merge=t\ndiff --git a/match-trees.c b/match-trees.c\nnew file mode 100644\nindex 0000000..fe7813c\n--- /dev/null\n+++ b/match-trees.c\n@@ -0,0 +1,301 @@\n+#include \"cache.h\"\n+#include \"tree.h\"\n+#include \"tree-walk.h\"\n+\n+static int score_missing(unsigned mode, const char *path)\n+{\n+\tint score;\n+\n+\tif (S_ISDIR(mode))\n+\t\tscore = -1000;\n+\telse if (S_ISLNK(mode))\n+\t\tscore = -500;\n+\telse\n+\t\tscore = -50;\n+\treturn score;\n+}\n+\n+static int score_differs(unsigned mode1, unsigned mode2, const char *path)\n+{\n+\tint score;\n+\n+\tif (S_ISDIR(mode1) != S_ISDIR(mode2))\n+\t\tscore = -100;\n+\telse if (S_ISLNK(mode1) != S_ISLNK(mode2))\n+\t\tscore = -50;\n+\telse\n+\t\tscore = -5;\n+\treturn score;\n+}\n+\n+static int score_matches(unsigned mode1, unsigned mode2, const char *path)\n+{\n+\tint score;\n+\n+\t/* Heh, we found SHA-1 collisions between different kind of objects */\n+\tif (S_ISDIR(mode1) != S_ISDIR(mode2))\n+\t\tscore = -100;\n+\telse if (S_ISLNK(mode1) != S_ISLNK(mode2))\n+\t\tscore = -50;\n+\n+\telse if (S_ISDIR(mode1))\n+\t\tscore = 1000;\n+\telse if (S_ISLNK(mode1))\n+\t\tscore = 500;\n+\telse\n+\t\tscore = 250;\n+\treturn score;\n+}\n+\n+/*\n+ * Inspect two trees, and give a score that tells how similar they are.\n+ */\n+static int score_trees(const unsigned char *hash1, const unsigned char *hash2)\n+{\n+\tstruct tree_desc one;\n+\tstruct tree_desc two;\n+\tvoid *one_buf, *two_buf;\n+\tint score = 0;\n+\tchar type[10];\n+\n+\tone_buf = read_sha1_file(hash1, type, &one.size);\n+\tif (!one_buf)\n+\t\tdie(\"unable to read tree (%s)\", sha1_to_hex(hash1));\n+\tif (strcmp(type, tree_type))\n+\t\tdie(\"%s is not a tree\", sha1_to_hex(hash1));\n+\ttwo_buf = read_sha1_file(hash2, type, &two.size);\n+\tif (!two_buf)\n+\t\tdie(\"unable to read tree (%s)\", sha1_to_hex(hash2));\n+\tif (strcmp(type, tree_type))\n+\t\tdie(\"%s is not a tree\", sha1_to_hex(hash2));\n+\tone.buf = one_buf;\n+\ttwo.buf = two_buf;\n+\twhile (one.size | two.size) {\n+\t\tconst unsigned char *elem1 = elem1;\n+\t\tconst unsigned char *elem2 = elem2;\n+\t\tconst char *path1, *path2;\n+\t\tunsigned mode1, mode2;\n+\t\tint cmp;\n+\n+\t\tif (one.size)\n+\t\t\telem1 = tree_entry_extract(&one, &path1, &mode1);\n+\t\tif (two.size)\n+\t\t\telem2 = tree_entry_extract(&two, &path2, &mode2);\n+\n+\t\tif (!one.size) {\n+\t\t\t/* two has more entries */\n+\t\t\tscore += score_missing(mode2, path2);\n+\t\t\tupdate_tree_entry(&two);\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!two.size) {\n+\t\t\t/* two lacks this entry */\n+\t\t\tscore += score_missing(mode1, path1);\n+\t\t\tupdate_tree_entry(&one);\n+\t\t\tcontinue;\n+\t\t}\n+\t\tcmp = base_name_compare(path1, strlen(path1), mode1,\n+\t\t\t\t\tpath2, strlen(path2), mode2);\n+\t\tif (cmp < 0) {\n+\t\t\t/* path1 does not appear in two */\n+\t\t\tscore += score_missing(mode1, path1);\n+\t\t\tupdate_tree_entry(&one);\n+\t\t\tcontinue;\n+\t\t}\n+\t\telse if (cmp > 0) {\n+\t\t\t/* path2 does not appear in one */\n+\t\t\tscore += score_missing(mode2, path2);\n+\t\t\tupdate_tree_entry(&two);\n+\t\t\tcontinue;\n+\t\t}\n+\t\telse if (hashcmp(elem1, elem2))\n+\t\t\t/* they are different */\n+\t\t\tscore += score_differs(mode1, mode2, path1);\n+\t\telse\n+\t\t\t/* same subtree or blob */\n+\t\t\tscore += score_matches(mode1, mode2, path1);\n+\t\tupdate_tree_entry(&one);\n+\t\tupdate_tree_entry(&two);\n+\t}\n+\tfree(one_buf);\n+\tfree(two_buf);\n+\treturn score;\n+}\n+\n+/*\n+ * Match one itself and its subtrees with two and pick the best match.\n+ */\n+static void match_trees(const unsigned char *hash1,\n+\t\t\tconst unsigned char *hash2,\n+\t\t\tint *best_score,\n+\t\t\tchar **best_match,\n+\t\t\tchar *base,\n+\t\t\tint recurse_limit)\n+{\n+\tstruct tree_desc one;\n+\tvoid *one_buf;\n+\tchar type[10];\n+\n+\tone_buf = read_sha1_file(hash1, type, &one.size);\n+\tif (!one_buf)\n+\t\tdie(\"unable to read tree (%s)\", sha1_to_hex(hash1));\n+\tif (strcmp(type, tree_type))\n+\t\tdie(\"%s is not a tree\", sha1_to_hex(hash1));\n+\tone.buf = one_buf;\n+\n+\twhile (one.size) {\n+\t\tconst char *path;\n+\t\tconst unsigned char *elem;\n+\t\tunsigned mode;\n+\t\tint score;\n+\n+\t\telem = tree_entry_extract(&one, &path, &mode);\n+\t\tif (!S_ISDIR(mode))\n+\t\t\tgoto next;\n+\t\tscore = score_trees(elem, hash2);\n+\t\tif (*best_score < score) {\n+\t\t\tchar *newpath;\n+\t\t\tnewpath = xmalloc(strlen(base) + strlen(path) + 1);\n+\t\t\tsprintf(newpath, \"%s%s\", base, path);\n+\t\t\tfree(*best_match);\n+\t\t\t*best_match = newpath;\n+\t\t\t*best_score = score;\n+\t\t}\n+\t\tif (recurse_limit) {\n+\t\t\tchar *newbase;\n+\t\t\tnewbase = xmalloc(strlen(base) + strlen(path) + 2);\n+\t\t\tsprintf(newbase, \"%s%s/\", base, path);\n+\t\t\tmatch_trees(elem, hash2, best_score, best_match,\n+\t\t\t\t    newbase, recurse_limit - 1);\n+\t\t\tfree(newbase);\n+\t\t}\n+\n+\tnext:\n+\t\tupdate_tree_entry(&one);\n+\t}\n+\tfree(one_buf);\n+}\n+\n+/*\n+ * A tree \"hash1\" has a subdirectory at \"prefix\".  Come up with a\n+ * tree object by replacing it with another tree \"hash2\".\n+ */\n+static int splice_tree(const unsigned char *hash1,\n+\t\t       char *prefix,\n+\t\t       const unsigned char *hash2,\n+\t\t       unsigned char *result)\n+{\n+\tchar *subpath;\n+\tint toplen;\n+\tchar *buf;\n+\tunsigned long sz;\n+\tstruct tree_desc desc;\n+\tunsigned char *rewrite_here;\n+\tconst unsigned char *rewrite_with;\n+\tunsigned char subtree[20];\n+\tchar type[20];\n+\tint status;\n+\n+\tsubpath = strchr(prefix, '/');\n+\tif (!subpath)\n+\t\ttoplen = strlen(prefix);\n+\telse {\n+\t\ttoplen = subpath - prefix;\n+\t\tsubpath++;\n+\t}\n+\n+\tbuf = read_sha1_file(hash1, type, &sz);\n+\tif (!buf)\n+\t\tdie(\"cannot read tree %s\", sha1_to_hex(hash1));\n+\tdesc.buf = buf;\n+\tdesc.size = sz;\n+\n+\trewrite_here = NULL;\n+\twhile (desc.size) {\n+\t\tconst char *name;\n+\t\tunsigned mode;\n+\t\tconst unsigned char *sha1;\n+\n+\t\tsha1 = tree_entry_extract(&desc, &name, &mode);\n+\t\tif (strlen(name) == toplen &&\n+\t\t    !memcmp(name, prefix, toplen)) {\n+\t\t\tif (!S_ISDIR(mode))\n+\t\t\t\tdie(\"entry %s in tree %s is not a tree\",\n+\t\t\t\t    name, sha1_to_hex(hash1));\n+\t\t\trewrite_here = (unsigned char *) sha1;\n+\t\t\tbreak;\n+\t\t}\n+\t\tupdate_tree_entry(&desc);\n+\t}\n+\tif (!rewrite_here)\n+\t\tdie(\"entry %.*s not found in tree %s\",\n+\t\t    toplen, prefix, sha1_to_hex(hash1));\n+\tif (subpath) {\n+\t\tstatus = splice_tree(rewrite_here, subpath, hash2, subtree);\n+\t\tif (status)\n+\t\t\treturn status;\n+\t\trewrite_with = subtree;\n+\t}\n+\telse\n+\t\trewrite_with = hash2;\n+\thashcpy(rewrite_here, rewrite_with);\n+\tstatus = write_sha1_file(buf, sz, tree_type, result);\n+\tfree(buf);\n+\treturn status;\n+}\n+\n+/*\n+ * We are trying to come up with a merge between one and two that\n+ * results in a tree shape similar to one.  The tree two might\n+ * correspond to a subtree of one, in which case it needs to be\n+ * shifted down by prefixing otherwise empty directories.  On the\n+ * other hand, it could cover tree one and we might need to pick a\n+ * subtree of it.\n+ */\n+void shift_tree(const unsigned char *hash1,\n+\t\tconst unsigned char *hash2,\n+\t\tunsigned char *shifted,\n+\t\tint depth_limit)\n+{\n+\tchar *add_prefix;\n+\tchar *del_prefix;\n+\tint add_score, del_score;\n+\n+\tadd_score = del_score = score_trees(hash1, hash2);\n+\tadd_prefix = xcalloc(1, 1);\n+\tdel_prefix = xcalloc(1, 1);\n+\n+\t/*\n+\t * See if one's subtree resembles two; if so we need to prefix\n+\t * two with a few fake trees to match the prefix.\n+\t */\n+\tmatch_trees(hash1, hash2, &add_score, &add_prefix, \"\", depth_limit);\n+\n+\t/*\n+\t * See if two's subtree resembles one; if so we need to\n+\t * pick only subtree of two.\n+\t */\n+\tmatch_trees(hash2, hash1, &del_score, &del_prefix, \"\", depth_limit);\n+\n+\t/* Assume we do not have to do any shifting */\n+\thashcpy(shifted, hash2);\n+\n+\tif (add_score < del_score) {\n+\t\t/* We need to pick a subtree of two */\n+\t\tunsigned mode;\n+\n+\t\tif (!*del_prefix)\n+\t\t\treturn;\n+\n+\t\tif (get_tree_entry(hash2, del_prefix, shifted, &mode))\n+\t\t\tdie(\"cannot find path %s in tree %s\",\n+\t\t\t    del_prefix, sha1_to_hex(hash2));\n+\t\treturn;\n+\t}\n+\n+\tif (!*add_prefix)\n+\t\treturn;\n+\n+\tsplice_tree(hash1, add_prefix, hash2, shifted);\n+}\n+\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 5898942..7b4e339 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -16,6 +16,22 @@\n #include \"path-list.h\"\n #include \"xdiff-interface.h\"\n \n+static int subtree_merge;\n+\n+static struct tree *shift_tree_object(struct tree *one, struct tree *two)\n+{\n+\tunsigned char shifted[20];\n+\n+\t/*\n+\t * NEEDSWORK: this limits the recursion depth to hardcoded\n+\t * value '2' to avoid excessive overhead.\n+\t */\n+\tshift_tree(one->object.sha1, two->object.sha1, shifted, 2);\n+\tif (!hashcmp(two->object.sha1, shifted))\n+\t\treturn two;\n+\treturn lookup_tree(shifted);\n+}\n+\n /*\n  * A virtual commit has\n  * - (const char *)commit->util set to the name, and\n@@ -1111,6 +1127,12 @@ static int merge_trees(struct tree *head,\n \t\t       struct tree **result)\n {\n \tint code, clean;\n+\n+\tif (subtree_merge) {\n+\t\tmerge = shift_tree_object(head, merge);\n+\t\tcommon = shift_tree_object(head, common);\n+\t}\n+\n \tif (sha_eq(common->object.sha1, merge->object.sha1)) {\n \t\toutput(0, \"Already uptodate!\");\n \t\t*result = head;\n@@ -1316,6 +1338,13 @@ int main(int argc, char *argv[])\n \tstruct lock_file *lock = xcalloc(1, sizeof(struct lock_file));\n \tint index_fd;\n \n+\tif (argv[0]) {\n+\t\tint namelen = strlen(argv[0]);\n+\t\tif (8 < namelen &&\n+\t\t    !strcmp(argv[0] + namelen - 8, \"-subtree\"))\n+\t\t\tsubtree_merge = 1;\n+\t}\n+\n \tgit_config(merge_config);\n \tif (getenv(\"GIT_MERGE_VERBOSITY\"))\n \t\tverbosity = strtol(getenv(\"GIT_MERGE_VERBOSITY\"), NULL, 10);\ndiff --git a/test-match-trees.c b/test-match-trees.c\nnew file mode 100644\nindex 0000000..a3c4688\n--- /dev/null\n+++ b/test-match-trees.c\n@@ -0,0 +1,24 @@\n+#include \"cache.h\"\n+#include \"tree.h\"\n+\n+int main(int ac, char **av)\n+{\n+\tunsigned char hash1[20], hash2[20], shifted[20];\n+\tstruct tree *one, *two;\n+\n+\tif (get_sha1(av[1], hash1))\n+\t\tdie(\"cannot parse %s as an object name\", av[1]);\n+\tif (get_sha1(av[2], hash2))\n+\t\tdie(\"cannot parse %s as an object name\", av[2]);\n+\tone = parse_tree_indirect(hash1);\n+\tif (!one)\n+\t\tdie(\"not a treeish %s\", av[1]);\n+\ttwo = parse_tree_indirect(hash2);\n+\tif (!two)\n+\t\tdie(\"not a treeish %s\", av[2]);\n+\n+\tshift_tree(one->object.sha1, two->object.sha1, shifted, -1);\n+\tprintf(\"shifted: %s\\n\", sha1_to_hex(shifted));\n+\n+\texit(0);\n+}\n-- \n1.5.0.552.ge1b1c\n"},{"id":"34852","messageId":"20070217071425.GD27864@spearce.org","threadId":"6853","inReplyTo":"7vfy95y2n9.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] A new merge stragety 'subtree'.","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-02-17T07:14:25Z","receivedAt":"2007-02-17T07:14:25Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano <junkio@cox.net> wrote:\n> For normal merge strategies, if you are on branch A and merge\n> branch B into it, what you will get is exactly the same as what\n> you would get by merging branch A while being on branch A\n> (modulo the direction of conflict markers).  With the subtree\n> merge, it is not the case anymore.  If I pull from git-gui.git,\n> the resulting tree look like git.git with Shawn's updates.  If\n> Shawn pulls from git.git, even after I did some changes on my\n> own to git-gui subdirectory, bypassing his tree, he will get a\n> merged result pertaining to git-gui.git repository\n> (i.e. git-gui/ subdirectory of what I have).  This way, we can\n> continue merging from each other.\n> \n> Although I do not plan to commit anything in git-gui/ part of my\n> tree myself, bypassing Shawn, it is nice to know that it will\n> not introduce problems down the road.\n\nThis does actually cause a problem if you merge a git.git commit\ninto git-gui.git (by stripping the git-gui/ part off).  The problem\nis the entire git.git history would then become the second parent\nof the git-gui.git merge commit, and suddenly the git-gui.git\nrepository increases by >11 MiB in size...  ;-)\n\nWith regards to maintaining git-gui: I'll apply all patches to my\ntree and do testing there, then ask Junio to merge a tagged release\nover to git.git for inclusion in the next git release.\n\nTo avoid pulling the entire git.git history into git-gui, I'd ask\nthat anyone bypassing me (e.g. if I'm being horribly unresponsive\none week) checkout the git-gui branch from git.git, apply the\nchange(s) there, then merge that branch into git.git using the\nsubtree strategy.  This way I can later fast-forward git-gui.git\nto the fixed commit, without sucking in more than I bargained for.\n\nFor example:\n\n\tgit log -n1 -- git-gui\n\t# copy the second parent...\n\tgit checkout -b fixgg <secondparent>\n\t# do fixes...\n\tgit checkout master\n\tgit merge -s subtree fixgg\n\nThen I can later obtain `fixgg` from the merge commit in git.git\nand update git-gui.git, without sucking in git.git's objects.\n\n-- \nShawn.\n"},{"id":"34855","messageId":"7vzm7duqzf.fsf@assigned-by-dhcp.cox.net","threadId":"6853","inReplyTo":"20070217071425.GD27864@spearce.org","subject":"Re: [PATCH] A new merge stragety 'subtree'.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-02-17T08:29:24Z","receivedAt":"2007-02-17T08:29:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" <spearce@spearce.org> writes:\n\n> Junio C Hamano <junkio@cox.net> wrote:\n>> ...\n>> Although I do not plan to commit anything in git-gui/ part of my\n>> tree myself, bypassing Shawn, it is nice to know that it will\n>> not introduce problems down the road.\n>\n> This does actually cause a problem if you merge a git.git commit\n> into git-gui.git (by stripping the git-gui/ part off).  The problem\n> is the entire git.git history would then become the second parent\n> of the git-gui.git merge commit, and suddenly the git-gui.git\n> repository increases by >11 MiB in size...  ;-)\n\nDon't worry.  I am not asking you to actually perform such a merge\nand make the relut as a part of _official_ git-gui.git history.\n\n> To avoid pulling the entire git.git history into git-gui, I'd ask\n> that anyone bypassing me (e.g. if I'm being horribly unresponsive\n> one week) checkout the git-gui branch from git.git, apply the\n> change(s) there, then merge that branch into git.git using the\n> subtree strategy.\n\nActually, I do not think you even need to ask them to do that.\nI am not planning to apply patches to git.git that touch\ngit-gui/ subdirectory myself, but if you see such a patch on the\nlist, you could first apply it to your copy of git.git\nrepository, and run your private edition of cherry-pick that\nuses merge-subtree instead of merge-recursive to pick it out\nonto your 'master' branch of git-gui.git repository.  That way,\nthe next time I'll pull from your git-gui.git repository, I will\nget the change through you.\n\nAnd the procedure would actually work _even_ _if_ (repeat, I do\nnot plan to do this) I applied such a patch to my tree before I\npull from you --- it will just result in an accidental clean\nmerge.\n"},{"id":"34856","messageId":"20070217084558.GE27864@spearce.org","threadId":"6853","inReplyTo":"7vfy95y2n9.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] A new merge stragety 'subtree'.","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-02-17T08:45:58Z","receivedAt":"2007-02-17T08:45:58Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano <junkio@cox.net> wrote:\n> The detection of corresponding subtree is done by comparing the\n> pathnames and types in the toplevel of the tree.\n> \n> Heuristics galore!  That's the git way ;-).\n\nI have some concerns about the match-tree heuristic you are using here.\n\nFor example, it is very common for Java projects to have the same\ntree \"shape\".  Just look at egit/jgit for an example, the three\ntop level directories are:\n\n\torg.spearce.egit.core/\n\t\tMETA-INF/\n\t\tbuild.properties\n\t\tplugin.xml\n\t\tsrc/\n\n\torg.spearce.egit.ui/\n\t\tMETA-INF/\n\t\tbuild.properties\n\t\tplugin.xml\n\t\tsrc/\n\n\torg.spearce.jgit\n\t\tMETA-INF/\n\t\tsrc/\n\nIf I were to treat the first two as subprojects this new subtree\nmerge strategy might fail here as it could easily match to the\nwrong directory.\n\n\nWhat about a different approach?\n\nIn a merge of commit#1 (parent project) and commit#2 (subroject)...\n\nWe have the set of merge bases readily available.  We just have\nto find out in each merge base where the files went from commit#2,\nthen modify commit#2 to conform to that same shape.\n\nReally that isn't too different from a rename detection.  In other\nwords do something like the following:\n\n  a) Scan the parents of the merge base B for a commit that is\n  in commit#2's ancestory but not commit#1's ancestory, except by\n  the merge commit B.  Such a parent must be from the project that\n  commit#2 is also from.  For sake of explaining this, lets call\n  this parent B^2.\n\n  b) Perform a partial rename-diff between B^2 and B.  The magic\n  here is we need to discard any path in B that also appears in\n  B^1 and B^2, and that has the same SHA-1 as in B^1, before we do\n  the rename-diff.\n\n  c) Find the most common prefix within the renamed files.\n\n  d) Fit commit#2 to use that prefix, and merge.\n\n\nHere's a real example.  In 67c75759 you merged git-gui.git.\n67c75759^1 is from git.git, 67c75759^2 is from git-gui.git.\n\nThe stock rename-diff:\n\n  $ git diff-tree --abbrev -r -M --diff-filter=MRD 67c75759^2 67c75759\n  :100644 100644 c714d38... d99372a... M  .gitignore\n  :100755 100755 8fac8cb... 7a10b60... M  GIT-VERSION-GEN\n  :100644 100644 fd82d9d... 5d31e6d... M  Makefile\n  :100644 100644 b95a137... b95a137... R100       TODO    git-gui/TODO\n  :100755 100755 f5010dd... f5010dd... R100       git-gui.sh      git-gui/git-gui.sh\n\nThe problem here is both ^1 and ^2 defines the first three paths,\nso we think we modified them in the merge rather than moved them.\nBut these three files match ^1, as we did not do an evil merge here.\nThat's why they are showing as modified in this diff.\n\nNow take 67c7 and whack those three files (step b above), and rediff:\n\n  $ C=$(git ls-tree 67c75759 | sed '\n          /       .gitignore$/d\n          /       GIT-VERSION-GEN$/d\n          /       Makefile$/d' | git mktree)\n  $ git diff-tree --abbrev -r -M --diff-filter=MRD 67c75759^2 $C\n  :100644 100644 c714d38... c714d38... R100       .gitignore      git-gui/.gitignore\n  :100755 100755 8fac8cb... 8fac8cb... R100       GIT-VERSION-GEN git-gui/GIT-VERSION-GEN\n  :100644 100644 fd82d9d... fd82d9d... R100       Makefile        git-gui/Makefile\n  :100644 100644 b95a137... b95a137... R100       TODO    git-gui/TODO\n  :100755 100755 f5010dd... f5010dd... R100       git-gui.sh      git-gui/git-gui.sh\n\nWow, look at that, everything starts with 'git-gui/'!  ;-)\n\nThen we just need to pick the most popular common prefix of all\nrenamed paths and fit commit#2 to conform to that structure.\nFinally we can run the merge through.\n\nThe (now functional) pretend object stuff can be useful here,\nsuch as to make $C above so we can pass it off to diffcore.\n\n\nI think popping off the 'git-gui/' prefix would be the same deal,\nonly we'd be looking at the old names to determine the prefix to pop,\nrather than the new names.\n\nWe already do rename detection in merge-recursive.  Slapping an extra\nrename pass in front of things when it is invoked as merge-subtree\ncan't performance hurt that much.\n\nThoughts?\n\n-- \nShawn.\n"},{"id":"34857","messageId":"7vps89upyl.fsf@assigned-by-dhcp.cox.net","threadId":"6853","inReplyTo":"20070217084558.GE27864@spearce.org","subject":"Re: [PATCH] A new merge stragety 'subtree'.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-02-17T08:51:30Z","receivedAt":"2007-02-17T08:51:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" <spearce@spearce.org> writes:\n\n> Really that isn't too different from a rename detection.\n\nI know, but I am just lazy.  The match scoring part is very well\nisolated so you or anybody can plug different code there.\n"},{"id":"34858","messageId":"20070217085305.GF27864@spearce.org","threadId":"6853","inReplyTo":"7vzm7duqzf.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] A new merge stragety 'subtree'.","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-02-17T08:53:05Z","receivedAt":"2007-02-17T08:53:05Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano <junkio@cox.net> wrote:\n> \"Shawn O. Pearce\" <spearce@spearce.org> writes:\n> > To avoid pulling the entire git.git history into git-gui, I'd ask\n> > that anyone bypassing me (e.g. if I'm being horribly unresponsive\n> > one week) checkout the git-gui branch from git.git, apply the\n> > change(s) there, then merge that branch into git.git using the\n> > subtree strategy.\n> \n> Actually, I do not think you even need to ask them to do that.\n> I am not planning to apply patches to git.git that touch\n> git-gui/ subdirectory myself, but if you see such a patch on the\n> list, you could first apply it to your copy of git.git\n> repository, and run your private edition of cherry-pick that\n> uses merge-subtree instead of merge-recursive to pick it out\n> onto your 'master' branch of git-gui.git repository.  That way,\n> the next time I'll pull from your git-gui.git repository, I will\n> get the change through you.\n\nOr... I/we implement -p2 in git-am.  Then I can apply it right to\nmy git-gui repository.  :-)\n\nWait, isn't there a patch floating around for that?\nWasn't it sent in by Andy Parkins just before 1.5.0?\n\nJust for the record: I am perfectly happy taking patches for git-gui\nthat were made against the git.git repository.  Obviously I can\neasily apply it onto git-gui.git by stripping the path.  I'm also\nhappy directly pulling worthwhile commits, but I won't pull something\nthat is based on a git.git commit, for the reason stated above.\n \n> And the procedure would actually work _even_ _if_ (repeat, I do\n> not plan to do this) I applied such a patch to my tree before I\n> pull from you --- it will just result in an accidental clean\n> merge.\n\nYes, of course.  One of the insanely nice things about git. :)\n\n-- \nShawn.\n"},{"id":"34859","messageId":"20070217090228.GG27864@spearce.org","threadId":"6853","inReplyTo":"7vps89upyl.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] A new merge stragety 'subtree'.","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-02-17T09:02:28Z","receivedAt":"2007-02-17T09:02:28Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano <junkio@cox.net> wrote:\n> \"Shawn O. Pearce\" <spearce@spearce.org> writes:\n> \n> > Really that isn't too different from a rename detection.\n> \n> I know, but I am just lazy.  The match scoring part is very well\n> isolated so you or anybody can plug different code there.\n\nIs that a hint that I should code something if I think its better?  ;-)\n\nI'll probably try to code up a competing version of the match code\nbased on the fun stuff you did not quote, but likely won't get\naround to it for at least week.\n\n-- \nShawn.\n"},{"id":"295927","messageId":"7v4ppkvf02.fsf@assigned-by-dhcp.cox.net","threadId":"6853","inReplyTo":"20070217085305.GF27864@spearce.org","subject":"Re: [PATCH] A new merge stragety 'subtree'.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-02-17T18:02:53Z","receivedAt":"2007-02-17T18:02:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" <spearce@spearce.org> writes:\n\n> Or... I/we implement -p2 in git-am.  Then I can apply it right to\n> my git-gui repository.  :-)\n\nWhich is 2092a1fe (v1.5.0~23), I think.\n"},{"id":"34881","messageId":"7vzm7cu0c8.fsf@assigned-by-dhcp.cox.net","threadId":"6853","inReplyTo":"20070217090228.GG27864@spearce.org","subject":"Re: [PATCH] A new merge stragety 'subtree'.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-02-17T18:04:55Z","receivedAt":"2007-02-17T18:04:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" <spearce@spearce.org> writes:\n\n> Junio C Hamano <junkio@cox.net> wrote:\n>> \"Shawn O. Pearce\" <spearce@spearce.org> writes:\n>> \n>> > Really that isn't too different from a rename detection.\n>> \n>> I know, but I am just lazy.  The match scoring part is very well\n>> isolated so you or anybody can plug different code there.\n>\n> Is that a hint that I should code something if I think its better?  ;-)\n\nIt is just a statement that scoring part is currently just a\nstub, good enough only for what I needed, and any half-seriously\ndone implementation would be better than what I currently have\nthere.\n"}]}