{"thread":{"id":"44318","subject":"[RFD] should all merge bases be equal?","startedAt":"2016-10-17T22:28:56Z","lastAt":"2017-02-09T16:58:56Z","messageCount":13,"participants":["Junio C Hamano","Michael Haggerty"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"304315","messageId":"xmqqmvi2sj8f.fsf@gitster.mtv.corp.google.com","threadId":"44318","inReplyTo":null,"subject":"[RFD] should all merge bases be equal?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-17T22:28:48Z","receivedAt":"2016-10-17T22:28:56Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"People can see how fast the usual merges I see everyday are by\nlooking at output from\n\n $ git log --first-parent --format='%ct %s' master..pu\n\nand noticing the seconds since epoch. Most of the days, these are\nrecreated directly on top of 'master' from scratch, and they get\ntimestamps that are very close to each other (or the same), meaning\nthat I am getting multiple merges per second.\n\nBeing accustomed how fast my merges go, there is one merge that\nhiccups for me every once in a few days: merging back from 'master'\nto 'next'. This happens after having multiple topics (that by\ndefinition have to be the ones that were already merged to 'next'\nsome time ago) to 'master', and 'master' may also have its own\ncommit (e.g. update to \"RelNotes\") and merges of side branches that\nwere not in 'next' (e.g. merge from submaintainers like i18n, etc.)\n\nThe reason why this merge is slow is because it typically have many\nmerge bases. For example, today's tip of 'next' is:\n\n commit 6021889cc14df07d4366829367d2c4a11d1eaa56\n Merge: 4868def05e 659889482a\n Author: Junio C Hamano \n Date: Mon Oct 17 14:02:05 2016 -0700\n\n Sync with master\n\n * master:\n Tenth batch for 2.11\n l10n: de.po: translate 260 new messages\n l10n: de.po: fix translation of autostash\n l10n: ru.po: update Russian translation\n\nwhich is a merge that has 12 merge bases:\n\n $ git merge-base --all 4868def05e 659889482a | git name-rev --stdin\n 3cdd5d19178a54d2e51b5098d43b57571241d0ab (ko/master)\n 641c900b2c3a8c3d385eb353b3801a5f49ddbb47 (js/reset-usage)\n 30cfe72d37ed8c174cae43923769730a94549dae (rs/pretty-format-color-doc-fix)\n 654311bf6ee0fbf530c088271c2c76d46f31f82d (da/mergetool-diff-order)\n 72710165c932edb2b8552aef7aef2f357dde4746 (sb/submodule-config-doc-drop-path)\n 842a516cb02a53cf0291ff67ed6f8517966345c0 (js/regexec-buf)\n 62fe0eb4804c297486a1d421a4f893865fcbc911 (jk/quarantine-received-objects)\n a94bb683970a111b467a36590ca36e52754ad504 (rs/cocci)\n e8c42cb9ce6a566aad797cc6c5bc1279d608d819 (jk/ref-symlink-loop)\n 22d3b8de1b625813faec6f3d6ffe66124837b78b (jk/clone-copy-alternates-fix)\n 7431596ab1f05a13adb93b44108f27cfd6578a31 (nd/commit-p-doc)\n 5275c3081c2b2c6166a2fc6b253a3acb20f8ae89 (dt/http-empty-auth)\n\nThe tip of each topic that was merged recently to 'master' since\n'master' was last merged to 'next' becomes a valid merge-base by\ndesign of the workflow. We merge a topic to 'master' whose tip\nhas been already in 'next' for a while, so the tip of 'next' before\nmerging 'master' back is a descendant of the tips of these topics,\nand the tip of 'master' before I make this merge has just become a\ndescendant of the tips of these topics. That makes them common\nancestors between 'master' and 'next'.\n\nBut for the purpose of figuring out the 3-way merge result, I\nsuspect that they are pretty much useless common ancestor to use as\nthe merge base. The first one in the list, the old 'master' that\nwas merged the last time to 'next', would be a lot more useful one.\n\nAnd of course, if I do this:\n\n $ git checkout next\n $ git merge master ;# this is slow due to the 12-base above\n $ git checkout HEAD^ ;# detach at the previous state\n $ git merge-recursive ko/master -- HEAD master\n\nthe merge is instantaneous. I'd get only what truly happened\nuniquely on 'master', e.g. RelNotes update and i18n merge.\n\nI am wondering if it is worth trying to optimize it by taking\nadvantage of the specific workflow (i.e. give me an option to use\nwhen merging 'master' back to 'next') and allows me to exclude the\ntips of these topic branches. Would I be making the result open to\nthe criss-cross merge gotchas the \"recursive merge\" machinery was\ndesigned to prevent in the first place by doing so? Offhand, I do\nnot think that would be the case.\n\nAssuming that it is a good idea, there is another question of how to\ntell the more meaningful merge bases (ko/master in this case) out of\nthe less useful ones (all the others). I think it would be\nsufficient to reject commits that are not on the first-parent chain\nof neither branch being merged. Among the 12 merge bases, ko/master\nis the only one that appears on the first-parent chain from 'master'\nbeing merged (it does not appear on the first-parent chain from\n'next'). All others were topic tips that by definition were merged\nas second parent to integration branches ('next' and later 'master').\nThe place to do this would be a new option to 'merge-base'; instead\nof \"--all\", perhaps \"--major\" option gives only the major merge bases\n(with the definition of 'major' being the above heuristics), and then\n\"git merge-recursive\" would learn \"-Xmajor-base-only\" strategy option,\nor something along that line.\n\nThoughts?\n"},{"id":"304375","messageId":"20161019042345.29766-1-gitster@pobox.com","threadId":"44318","inReplyTo":"xmqqmvi2sj8f.fsf@gitster.mtv.corp.google.com","subject":"[PATCH 0/7] Rejecting useless merge bases","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-19T04:23:38Z","receivedAt":"2016-10-19T04:23:56Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This is a continuation of\n\n http://public-inbox.org/git/xmqqmvi2sj8f.fsf@gitster.mtv.corp.google.com\n\nIn a workflow where topic branches are first merged to the 'next'\nintegration branch to be tested before getting merged down to the\n'master' integration branch to be consumed by the end users, merging\nthe 'master' branch back to the 'next' happens after topics graduate\nto 'master' and release notes entries are written for them.\n\nGit finds many merge bases between 'master' and 'next' while\ncreating this merge. In addition to the tip of 'master' back when\nwe made such a merge back from 'master' to 'next' was made the last\ntime, which is the most reasonable merge base to explain the\nhistories of both branches, all the tips of topic branches that\ngraduated recently are merge bases. Because these tips of topic\nbranches were already in 'next', the tip of 'next' reaches them, and\nbecause they just graduated to 'master', the tip of 'master' reaches\nthem, too. And these topics are independent most of the time (that\nis the point of employing the topic-branch workflow), so they cannot\nbe reduced.\n\nThe merge-recursive machinery is very inefficient to compute this\nmerge, because it needs to create pointless virtual merge-base\ncommits across these many merge bases. Conceptually, the point\nwhere the histories of 'master' and 'next' diverged was the tip of\n'master' back when we created such a merge back from 'master' to\n'next' the last time, and in practice that is the only merge base\nthat matters.\n\nThe series allows us to ignore these tips of topics, which are\nuninteresting merge bases, when running \"git merge\". The example\nmerge with 12 merge bases:\n\n git checkout 4868def05e && git merge 659889482a\n\nin our history takes about 1.22-1.33 seconds without the series,\nwhile running the latter \"git merge\" with the \"--fp-base-only\"\noption takes about 0.54-0.59 seconds.\n\nJunio C Hamano (7):\n commit: simplify fastpath of merge-base\n sha1_name: remove ONELINE_SEEN bit\n merge-base: stop moving commits around in remove_redundant()\n merge-base: expose get_merge_bases_many_0() a bit more\n merge-base: mark bases that are on first-parent chain\n merge-base: limit the output to bases that are on first-parent chain\n merge: allow to use only the fp-only merge bases\n\n Documentation/git-merge-base.txt | 8 +++-\n Documentation/merge-options.txt | 9 +++++\n builtin/merge-base.c | 10 +++--\n builtin/merge.c | 15 ++++++--\n commit.c | 81 ++++++++++++++++++++++++----------------\n commit.h | 7 +++-\n object.h | 3 +-\n sha1_name.c | 10 ++---\n 8 files changed, 94 insertions(+), 49 deletions(-)\n\n-- \n2.10.1-631-gb2c64dcf30\n\n"},{"id":"304376","messageId":"20161019042345.29766-2-gitster@pobox.com","threadId":"44318","inReplyTo":"20161019042345.29766-1-gitster@pobox.com","subject":"[PATCH 1/7] commit: simplify fastpath of merge-base computation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-19T04:23:39Z","receivedAt":"2016-10-19T04:24:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The get_merge_bases_many*() family of functions first call\nmerge_bases_many() to find all possible merge bases between a single\ncommit \"one\" and a set of other commits \"twos[]\". Because this\ntypically involves traversing the commit graph, which uses the\nobject flags on the commits involved, the function needs to clear\nthe flags before it returns.\n\nExcept for one special case. If \"one\" is exactly one of the \"twos\",\n\"one\" is the merge base and merge_bases_many() returns a list of\nmerge bases with a single element, \"one\", on it, without smudging\nthe object flags of the commits at all.\n\nWe used to use a loop over \"twos[]\" array to see if this fast-path\nwould have kicked in in merge_bases_many(), in which case we can\nreturn without cleaning the bits at all. We can do the same by\ninspecting the result in a more direct way, which is conceptually\ncleaner.\n\nSigned-off-by: Junio C Hamano \n---\n commit.c | 15 +++++++++++----\n 1 file changed, 11 insertions(+), 4 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex aada266f9a..6266c0380c 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -955,10 +955,17 @@ static struct commit_list *get_merge_bases_many_0(struct commit *one,\n \tint cnt, i;\n \n \tresult = merge_bases_many(one, n, twos);\n-\tfor (i = 0; i < n; i++) {\n-\t\tif (one == twos[i])\n-\t\t\treturn result;\n-\t}\n+\n+\t/*\n+\t * The fast-path of 'one' being the merge-base; there is no\n+\t * need to clean the object flags in this case.\n+\t */\n+\tif (result && !result->next &&\n+\t result->item == one &&\n+\t !(one->object.flags & RESULT))\n+\t\treturn result;\n+\n+\t/* If we didn't get any, or there is only one, we are done */\n \tif (!result || !result->next) {\n \t\tif (cleanup) {\n \t\t\tclear_commit_marks(one, all_flags);\n-- \n2.10.1-631-gb2c64dcf30\n\n"},{"id":"304377","messageId":"20161019042345.29766-4-gitster@pobox.com","threadId":"44318","inReplyTo":"20161019042345.29766-1-gitster@pobox.com","subject":"[PATCH 3/7] merge-base: stop moving commits around in remove_redundant()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-19T04:23:41Z","receivedAt":"2016-10-19T04:24:03Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The merge-base computation is performed in two steps. First,\npaint_down_to_common() traverses the history to find all possible\nmerge bases (and more), and then remove_redundant() checks the\nresult and culls the ones that can be reached from another commit\nin the result.\n\nThe latter received an array of commits, and then returned the same\narray after reordering the elements in it, moving the surviving ones\nto the front and returning the number of surviving ones.\n\nThis arrangement works, but it makes it cumbersome for the callers\nwhen they want to see the array's contents intact (e.g. the caller\nmay want to keep an additional per-commit data in an independent\narray that parallels the array of commits).\n\nStop moving commits around in the array, and instead mark the ones\nthat are not merge bases with the STALE bit in their object->flags\nbitword.\n\nSigned-off-by: Junio C Hamano \n---\n commit.c | 32 ++++++++++++++++++--------------\n 1 file changed, 18 insertions(+), 14 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 6266c0380c..59bd18e67c 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -888,11 +888,11 @@ struct commit_list *get_octopus_merge_bases(struct commit_list *in)\n \treturn ret;\n }\n \n-static int remove_redundant(struct commit **array, int cnt)\n+static void mark_redundant(struct commit **array, int cnt)\n {\n \t/*\n \t * Some commit in the array may be an ancestor of\n-\t * another commit. Move such commit to the end of\n+\t * another commit. Mark such commit as STALE in\n \t * the array, and return the number of commits that\n \t * are independent from each other.\n \t */\n@@ -930,18 +930,16 @@ static int remove_redundant(struct commit **array, int cnt)\n \t\tfree_commit_list(common);\n \t}\n \n-\t/* Now collect the result */\n-\tCOPY_ARRAY(work, array, cnt);\n-\tfor (i = filled = 0; i < cnt; i++)\n-\t\tif (!redundant[i])\n-\t\t\tarray[filled++] = work[i];\n-\tfor (j = filled, i = 0; i < cnt; i++)\n+\t/* Mark the result */\n+\tfor (i = 0; i < cnt; i++)\n \t\tif (redundant[i])\n-\t\t\tarray[j++] = work[i];\n+\t\t\tarray[i]->object.flags |= STALE;\n+\t\telse\n+\t\t\tarray[i]->object.flags &= ~STALE;\n+\n \tfree(work);\n \tfree(redundant);\n \tfree(filled_index);\n-\treturn filled;\n }\n \n static struct commit_list *get_merge_bases_many_0(struct commit *one,\n@@ -984,10 +982,13 @@ static struct commit_list *get_merge_bases_many_0(struct commit *one,\n \tclear_commit_marks(one, all_flags);\n \tclear_commit_marks_many(n, twos, all_flags);\n \n-\tcnt = remove_redundant(rslt, cnt);\n+\tmark_redundant(rslt, cnt);\n \tresult = NULL;\n \tfor (i = 0; i < cnt; i++)\n-\t\tcommit_list_insert_by_date(rslt[i], &result);\n+\t\tif (!(rslt[i]->object.flags & STALE))\n+\t\t\tcommit_list_insert_by_date(rslt[i], &result);\n+\t\telse\n+\t\t\trslt[i]->object.flags &= ~STALE;\n \tfree(rslt);\n \treturn result;\n }\n@@ -1086,9 +1087,12 @@ struct commit_list *reduce_heads(struct commit_list *heads)\n \t\t\tp->item->object.flags &= ~STALE;\n \t\t}\n \t}\n-\tnum_head = remove_redundant(array, num_head);\n+\tmark_redundant(array, num_head);\n \tfor (i = 0; i < num_head; i++)\n-\t\ttail = &commit_list_insert(array[i], tail)->next;\n+\t\tif (!(array[i]->object.flags & STALE))\n+\t\t\ttail = &commit_list_insert(array[i], tail)->next;\n+\t\telse\n+\t\t\tarray[i]->object.flags &= ~STALE;\n \treturn result;\n }\n \n-- \n2.10.1-631-gb2c64dcf30\n\n"},{"id":"304378","messageId":"20161019042345.29766-3-gitster@pobox.com","threadId":"44318","inReplyTo":"20161019042345.29766-1-gitster@pobox.com","subject":"[PATCH 2/7] sha1_name: remove ONELINE_SEEN bit","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-19T04:23:40Z","receivedAt":"2016-10-19T04:24:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"28a4d94044 (\"object name: introduce ':/' notation\",\n2007-02-24) started using its own bit from object->flags to mark\ncommits used while parsing the \":/token\" extended SHA-1 syntax to\nname a commit temporarily, and this was kept even when f7bff00314\n(\"sha1_name.c: fix parsing of \":/token\" syntax\", 2010-08-02) found\nand fixed a bug in its implementation.\n\nThe use of that flag bit, however, is limited to a single function,\nget_sha1_oneline(), which first sets it for the commits sitting at\nthe tips of refs, uses the bit to avoid duplicate traversal while\nwalking the history, and then cleans the bit from all commits it\nwalked.\n\nWhich is exactly what the general-purpose TMP_MARK bit meant to be\nused for isolated case was invented for. Replace ONELINE_SEEN with\nTMP_MARK and retire the former.\n\nSigned-off-by: Junio C Hamano \n---\n object.h | 1 -\n sha1_name.c | 10 ++++------\n 2 files changed, 4 insertions(+), 7 deletions(-)\n\ndiff --git a/object.h b/object.h\nindex f8b644263f..f8e218eccd 100644\n--- a/object.h\n+++ b/object.h\n@@ -37,7 +37,6 @@ struct object_array {\n * bundle.c: 16\n * http-push.c: 16-----19\n * commit.c: 16-----19\n- * sha1_name.c: 20\n */\n #define FLAG_BITS 27\n \ndiff --git a/sha1_name.c b/sha1_name.c\nindex ca7ddd6f2c..fa0e6701a3 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -7,6 +7,7 @@\n #include \"refs.h\"\n #include \"remote.h\"\n #include \"dir.h\"\n+#include \"revision.h\"\n \n static int get_sha1_oneline(const char *, unsigned char *, struct commit_list *);\n \n@@ -855,9 +856,6 @@ static int get_sha1_1(const char *name, int len, unsigned char *sha1, unsigned l\n * For future extension, all other sequences beginning with ':/!' are reserved.\n */\n \n-/* Remember to update object flag allocation in object.h */\n-#define ONELINE_SEEN (1u<<20)\n-\n static int handle_one_ref(const char *path, const struct object_id *oid,\n \t\t\t int flag, void *cb_data)\n {\n@@ -899,7 +897,7 @@ static int get_sha1_oneline(const char *prefix, unsigned char *sha1,\n \t\treturn -1;\n \n \tfor (l = list; l; l = l->next) {\n-\t\tl->item->object.flags |= ONELINE_SEEN;\n+\t\tl->item->object.flags |= TMP_MARK;\n \t\tcommit_list_insert(l->item, &backup);\n \t}\n \twhile (list) {\n@@ -907,7 +905,7 @@ static int get_sha1_oneline(const char *prefix, unsigned char *sha1,\n \t\tstruct commit *commit;\n \t\tint matches;\n \n-\t\tcommit = pop_most_recent_commit(&list, ONELINE_SEEN);\n+\t\tcommit = pop_most_recent_commit(&list, TMP_MARK);\n \t\tif (!parse_object(commit->object.oid.hash))\n \t\t\tcontinue;\n \t\tbuf = get_commit_buffer(commit, NULL);\n@@ -924,7 +922,7 @@ static int get_sha1_oneline(const char *prefix, unsigned char *sha1,\n \tregfree(®ex);\n \tfree_commit_list(list);\n \tfor (l = backup; l; l = l->next)\n-\t\tclear_commit_marks(l->item, ONELINE_SEEN);\n+\t\tclear_commit_marks(l->item, TMP_MARK);\n \tfree_commit_list(backup);\n \treturn found ? 0 : -1;\n }\n-- \n2.10.1-631-gb2c64dcf30\n\n"},{"id":"304379","messageId":"20161019042345.29766-5-gitster@pobox.com","threadId":"44318","inReplyTo":"20161019042345.29766-1-gitster@pobox.com","subject":"[PATCH 4/7] merge-base: expose get_merge_bases_many_0() a bit more","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-19T04:23:42Z","receivedAt":"2016-10-19T04:24:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"git merge-base\" names its internal workhorse helper function\n\"get_merge_bases_many_0()\", which takes one \"can we get away without\nclearing the object->flags bits because we know we are the last\ncaller?\" parameter. Make the parameter into a flags word to make it\nextensible and rename it to get_merge_bases_opt(). Use it to turn\nget_merge_bases_many_dirty() wrapper into a C-preprocessor macro.\n\nSigned-off-by: Junio C Hamano \n---\n commit.c | 19 ++++++-------------\n commit.h | 6 ++++--\n 2 files changed, 10 insertions(+), 15 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 59bd18e67c..92d23b1082 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -942,15 +942,15 @@ static void mark_redundant(struct commit **array, int cnt)\n \tfree(filled_index);\n }\n \n-static struct commit_list *get_merge_bases_many_0(struct commit *one,\n-\t\t\t\t\t\t int n,\n-\t\t\t\t\t\t struct commit **twos,\n-\t\t\t\t\t\t int cleanup)\n+struct commit_list *get_merge_bases_opt(struct commit *one,\n+\t\t\t\t\tint n, struct commit **twos,\n+\t\t\t\t\tunsigned flags)\n {\n \tstruct commit_list *list;\n \tstruct commit **rslt;\n \tstruct commit_list *result;\n \tint cnt, i;\n+\tint cleanup = !!(flags & MB_POSTCLEAN);\n \n \tresult = merge_bases_many(one, n, twos);\n \n@@ -997,19 +997,12 @@ struct commit_list *get_merge_bases_many(struct commit *one,\n \t\t\t\t\t int n,\n \t\t\t\t\t struct commit **twos)\n {\n-\treturn get_merge_bases_many_0(one, n, twos, 1);\n-}\n-\n-struct commit_list *get_merge_bases_many_dirty(struct commit *one,\n-\t\t\t\t\t int n,\n-\t\t\t\t\t struct commit **twos)\n-{\n-\treturn get_merge_bases_many_0(one, n, twos, 0);\n+\treturn get_merge_bases_opt(one, n, twos, 0);\n }\n \n struct commit_list *get_merge_bases(struct commit *one, struct commit *two)\n {\n-\treturn get_merge_bases_many_0(one, 1, &two, 1);\n+\treturn get_merge_bases_opt(one, 1, &two, MB_POSTCLEAN);\n }\n \n /*\ndiff --git a/commit.h b/commit.h\nindex 32e1a113e5..557f2814b7 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -253,8 +253,10 @@ extern struct commit_list *get_merge_bases(struct commit *rev1, struct commit *r\n extern struct commit_list *get_merge_bases_many(struct commit *one, int n, struct commit **twos);\n extern struct commit_list *get_octopus_merge_bases(struct commit_list *in);\n \n-/* To be used only when object flags after this call no longer matter */\n-extern struct commit_list *get_merge_bases_many_dirty(struct commit *one, int n, struct commit **twos);\n+#define MB_POSTCLEAN 01\n+extern struct commit_list *get_merge_bases_opt(struct commit *one, int n, struct commit **twos, unsigned flags);\n+\n+#define get_merge_bases_many_dirty(one, n, twos) get_merge_bases_opt((one),(n),(twos),MB_POSTCLEAN)\n \n /* largest positive number a signed 32-bit integer can contain */\n #define INFINITE_DEPTH 0x7fffffff\n-- \n2.10.1-631-gb2c64dcf30\n\n"},{"id":"304380","messageId":"20161019042345.29766-6-gitster@pobox.com","threadId":"44318","inReplyTo":"20161019042345.29766-1-gitster@pobox.com","subject":"[PATCH 5/7] merge-base: mark bases that are on first-parent chain","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-19T04:23:43Z","receivedAt":"2016-10-19T04:24:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"In a workflow where topic branches are first merged to the 'next'\nintegration branch to be tested before getting merged down to the\n'master' integration branch to be consumed by the end users, merging\nthe 'master' branch back to the 'next' happens after topics graduate\nto 'master' and release notes entries are written for them.\n\nGit finds many merge bases between 'master' and 'next' while\ncreating this merge. In addition to the tip of 'master' back when\nwe made such a merge back from 'master' to 'next' was made the last\ntime, which is the most reasonable merge base to explain the\nhistories of both branches, all the tips of topic branches that\ngraduated recently are merge bases. Because these tips of topic\nbranches were already in 'next', the tip of 'next' reaches them, and\nbecause they just graduated to 'master', the tip of 'master' reaches\nthem, too. And these topics are independent most of the time (that\nis the point of employing the topic-branch workflow), so they cannot\nbe reduced.\n\nThe merge-recursive machinery is very inefficient to compute this\nmerge, because it needs to create pointless virtual merge-base\ncommits across these many merge bases. Conceptually, the point\nwhere the histories of 'master' and 'next' diverged was the tip of\n'master' back when we created such a merge back from 'master' to\n'next' the last time, and in practice that is the only merge base\nthat matters.\n\nUpdate the logic in paint_down_to_common() so that it can mark if a\nmerge-base commit was reached by following the first-parent chain of\neither side of the merge to find such commit, and give an option to\nget_merge_bases_opt() to return only merge-base commits that are on\nthe first-parent chain, so that a later step of this series can\nintroduce a command line option to enable it and avoid feeding\nuseless merge bases to the merge machinery.\n\nSigned-off-by: Junio C Hamano \n---\n commit.c | 17 +++++++++++++++--\n commit.h | 1 +\n object.h | 2 +-\n 3 files changed, 17 insertions(+), 3 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 92d23b1082..8e90531b05 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -765,8 +765,9 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n #define PARENT2\t\t(1u<<17)\n #define STALE\t\t(1u<<18)\n #define RESULT\t\t(1u<<19)\n+#define FPCHAIN\t\t(1u<<20)\n \n-static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);\n+static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT | FPCHAIN);\n \n static int queue_has_nonstale(struct prio_queue *queue)\n {\n@@ -802,6 +803,7 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n, struc\n \t\tstruct commit *commit = prio_queue_get(&queue);\n \t\tstruct commit_list *parents;\n \t\tint flags;\n+\t\tint nth_parent = 0;\n \n \t\tflags = commit->object.flags & (PARENT1 | PARENT2 | STALE);\n \t\tif (flags == (PARENT1 | PARENT2)) {\n@@ -816,11 +818,14 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n, struc\n \t\twhile (parents) {\n \t\t\tstruct commit *p = parents->item;\n \t\t\tparents = parents->next;\n+\t\t\tnth_parent++;\n \t\t\tif ((p->object.flags & flags) == flags)\n \t\t\t\tcontinue;\n \t\t\tif (parse_commit(p))\n \t\t\t\treturn NULL;\n \t\t\tp->object.flags |= flags;\n+\t\t\tif (nth_parent == 1)\n+\t\t\t\tp->object.flags |= FPCHAIN;\n \t\t\tprio_queue_put(&queue, p);\n \t\t}\n \t}\n@@ -951,6 +956,8 @@ struct commit_list *get_merge_bases_opt(struct commit *one,\n \tstruct commit_list *result;\n \tint cnt, i;\n \tint cleanup = !!(flags & MB_POSTCLEAN);\n+\tint fpchain = !!(flags & MB_FPCHAIN);\n+\tchar *on_fpchain;\n \n \tresult = merge_bases_many(one, n, twos);\n \n@@ -975,21 +982,27 @@ struct commit_list *get_merge_bases_opt(struct commit *one,\n \t/* There are more than one */\n \tcnt = commit_list_count(result);\n \trslt = xcalloc(cnt, sizeof(*rslt));\n+\ton_fpchain = xcalloc(cnt, sizeof(*on_fpchain));\n \tfor (list = result, i = 0; list; list = list->next)\n \t\trslt[i++] = list->item;\n \tfree_commit_list(result);\n \n+\tfor (i = 0; i < cnt; i++)\n+\t\ton_fpchain[i] = !!(rslt[i]->object.flags & FPCHAIN);\n+\n \tclear_commit_marks(one, all_flags);\n \tclear_commit_marks_many(n, twos, all_flags);\n \n \tmark_redundant(rslt, cnt);\n \tresult = NULL;\n \tfor (i = 0; i < cnt; i++)\n-\t\tif (!(rslt[i]->object.flags & STALE))\n+\t\tif (!(rslt[i]->object.flags & STALE) &&\n+\t\t (!fpchain || on_fpchain[i]))\n \t\t\tcommit_list_insert_by_date(rslt[i], &result);\n \t\telse\n \t\t\trslt[i]->object.flags &= ~STALE;\n \tfree(rslt);\n+\tfree(on_fpchain);\n \treturn result;\n }\n \ndiff --git a/commit.h b/commit.h\nindex 557f2814b7..ec6e09a985 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -254,6 +254,7 @@ extern struct commit_list *get_merge_bases_many(struct commit *one, int n, struc\n extern struct commit_list *get_octopus_merge_bases(struct commit_list *in);\n \n #define MB_POSTCLEAN 01\n+#define MB_FPCHAIN 02\n extern struct commit_list *get_merge_bases_opt(struct commit *one, int n, struct commit **twos, unsigned flags);\n \n #define get_merge_bases_many_dirty(one, n, twos) get_merge_bases_opt((one),(n),(twos),MB_POSTCLEAN)\ndiff --git a/object.h b/object.h\nindex f8e218eccd..7e6729158a 100644\n--- a/object.h\n+++ b/object.h\n@@ -36,7 +36,7 @@ struct object_array {\n * bisect.c: 16\n * bundle.c: 16\n * http-push.c: 16-----19\n- * commit.c: 16-----19\n+ * commit.c: 16-------20\n */\n #define FLAG_BITS 27\n \n-- \n2.10.1-631-gb2c64dcf30\n\n"},{"id":"304381","messageId":"20161019042345.29766-7-gitster@pobox.com","threadId":"44318","inReplyTo":"20161019042345.29766-1-gitster@pobox.com","subject":"[PATCH 6/7] merge-base: limit the output to bases that are on first-parent chain","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-19T04:23:44Z","receivedAt":"2016-10-19T04:24:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"A new option \"--fp-only\" limits the output to the merge bases that\nare on the first-parent chain from the branches being merged.\n\nSigned-off-by: Junio C Hamano \n---\n Documentation/git-merge-base.txt | 8 +++++++-\n builtin/merge-base.c | 10 +++++++---\n 2 files changed, 14 insertions(+), 4 deletions(-)\n\ndiff --git a/Documentation/git-merge-base.txt b/Documentation/git-merge-base.txt\nindex 808426faac..f99653f138 100644\n--- a/Documentation/git-merge-base.txt\n+++ b/Documentation/git-merge-base.txt\n@@ -9,7 +9,7 @@ git-merge-base - Find as good common ancestors as possible for a merge\n SYNOPSIS\n --------\n [verse]\n-'git merge-base' [-a|--all] ...\n+'git merge-base' [-a|--all] [--fp-only] ...\n 'git merge-base' [-a|--all] --octopus ...\n 'git merge-base' --is-ancestor \n 'git merge-base' --independent ...\n@@ -72,6 +72,12 @@ OPTIONS\n --all::\n \tOutput all merge bases for the commits, instead of just one.\n \n+--fp-only::\n+\tLimit the output to merge bases that are on the first-parent\n+\tchain from none of the commits given on the command line.\n+\n+\n+\n DISCUSSION\n ----------\n \ndiff --git a/builtin/merge-base.c b/builtin/merge-base.c\nindex c0d1822eb3..42febb20ff 100644\n--- a/builtin/merge-base.c\n+++ b/builtin/merge-base.c\n@@ -6,11 +6,12 @@\n #include \"revision.h\"\n #include \"parse-options.h\"\n \n-static int show_merge_base(struct commit **rev, int rev_nr, int show_all)\n+static int show_merge_base(struct commit **rev, int rev_nr, int show_all, int fp_only)\n {\n \tstruct commit_list *result;\n+\tunsigned flags = fp_only ? MB_FPCHAIN : 0;\n \n-\tresult = get_merge_bases_many_dirty(rev[0], rev_nr - 1, rev + 1);\n+\tresult = get_merge_bases_opt(rev[0], rev_nr - 1, rev + 1, flags);\n \n \tif (!result)\n \t\treturn 1;\n@@ -208,10 +209,13 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)\n \tstruct commit **rev;\n \tint rev_nr = 0;\n \tint show_all = 0;\n+\tint fp_only = 0;\n \tint cmdmode = 0;\n \n \tstruct option options[] = {\n \t\tOPT_BOOL('a', \"all\", &show_all, N_(\"output all common ancestors\")),\n+\t\tOPT_BOOL(0, \"fp-only\", &fp_only,\n+\t\t\t N_(\"limit to bases that are on first-parent chain\")),\n \t\tOPT_CMDMODE(0, \"octopus\", &cmdmode,\n \t\t\t N_(\"find ancestors for a single n-way merge\"), 'o'),\n \t\tOPT_CMDMODE(0, \"independent\", &cmdmode,\n@@ -255,5 +259,5 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)\n \tALLOC_ARRAY(rev, argc);\n \twhile (argc-- > 0)\n \t\trev[rev_nr++] = get_commit_reference(*argv++);\n-\treturn show_merge_base(rev, rev_nr, show_all);\n+\treturn show_merge_base(rev, rev_nr, show_all, fp_only);\n }\n-- \n2.10.1-631-gb2c64dcf30\n\n"},{"id":"304382","messageId":"20161019042345.29766-8-gitster@pobox.com","threadId":"44318","inReplyTo":"20161019042345.29766-1-gitster@pobox.com","subject":"[PATCH 7/7] merge: allow to use only the fp-only merge bases","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-19T04:23:45Z","receivedAt":"2016-10-19T04:24:19Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Teach \"git merge\" a new option \"--fp-base-only\" that tells it to\nconsider only merge bases that are on the first-parent chain.\n\nThis speeds up back-merges needed in the topic branch workflow. The\nmerge of 'master' back into 'next' used as an example in the RFD\narticle , i.e.\n\n git checkout 4868def05e && git merge 659889482a\n\nin our history takes about 1.22-1.33 seconds without the series,\nwhile running the latter \"git merge\" with the \"--fp-base-only\"\noption takes about 0.54-0.59 seconds.\n\nSigned-off-by: Junio C Hamano \n---\n Documentation/merge-options.txt | 9 +++++++++\n builtin/merge.c | 15 ++++++++++++---\n 2 files changed, 21 insertions(+), 3 deletions(-)\n\ndiff --git a/Documentation/merge-options.txt b/Documentation/merge-options.txt\nindex 5b4a62e936..7927f069e4 100644\n--- a/Documentation/merge-options.txt\n+++ b/Documentation/merge-options.txt\n@@ -116,6 +116,15 @@ ifndef::git-pull[]\n \tNote that not all merge strategies may support progress\n \treporting.\n \n+--fp-base-only::\n+\tInstead of using all merge bases when computing the\n+\tthree-way merge result, use only the merge bases on the\n+\tfirst-parent chain of the commits being merged. This\n+\texperimental feature is meant to be used when merging an\n+\tolder integration branch back to a newer integration branch\n+\tin the topic-branch workflow.\n+\n+\n endif::git-pull[]\n \n --allow-unrelated-histories::\ndiff --git a/builtin/merge.c b/builtin/merge.c\nindex 0ae099f746..a38b878e61 100644\n--- a/builtin/merge.c\n+++ b/builtin/merge.c\n@@ -88,6 +88,8 @@ enum ff_type {\n \n static enum ff_type fast_forward = FF_ALLOW;\n \n+static int fp_base_only;\n+\n static int option_parse_message(const struct option *opt,\n \t\t\t\tconst char *arg, int unset)\n {\n@@ -210,6 +212,8 @@ static struct option builtin_merge_options[] = {\n \t{ OPTION_SET_INT, 0, \"ff-only\", &fast_forward, NULL,\n \t\tN_(\"abort if fast-forward is not possible\"),\n \t\tPARSE_OPT_NOARG | PARSE_OPT_NONEG, NULL, FF_ONLY },\n+\tOPT_BOOL(0, \"fp-base-only\", &fp_base_only,\n+\t\t N_(\"use only merge bases on first-parent chain\")),\n \tOPT_RERERE_AUTOUPDATE(&allow_rerere_auto),\n \tOPT_BOOL(0, \"verify-signatures\", &verify_signatures,\n \t\tN_(\"verify that the named commit has a valid GPG signature\")),\n@@ -1340,9 +1344,14 @@ int cmd_merge(int argc, const char **argv, const char *prefix)\n \n \tif (!remoteheads)\n \t\t; /* already up-to-date */\n-\telse if (!remoteheads->next)\n-\t\tcommon = get_merge_bases(head_commit, remoteheads->item);\n-\telse {\n+\telse if (!remoteheads->next) {\n+\t\tunsigned flags = MB_POSTCLEAN;\n+\t\tif (fp_base_only)\n+\t\t\tflags |= MB_FPCHAIN;\n+\t\tcommon = get_merge_bases_opt(head_commit,\n+\t\t\t\t\t 1, &remoteheads->item,\n+\t\t\t\t\t flags);\n+\t} else {\n \t\tstruct commit_list *list = remoteheads;\n \t\tcommit_list_insert(head_commit, &list);\n \t\tcommon = get_octopus_merge_bases(list);\n-- \n2.10.1-631-gb2c64dcf30\n\n"},{"id":"304404","messageId":"xmqq4m48me0l.fsf@gitster.mtv.corp.google.com","threadId":"44318","inReplyTo":"20161019042345.29766-6-gitster@pobox.com","subject":"Re: [PATCH 5/7] merge-base: mark bases that are on first-parent chain","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-19T17:42:34Z","receivedAt":"2016-10-19T17:42:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> In a workflow where topic branches are first merged to the 'next'\n> integration branch to be tested before getting merged down to the\n> 'master' integration branch to be consumed by the end users, merging\n> the 'master' branch back to the 'next' happens after topics graduate\n> to 'master' and release notes entries are written for them.\n>\n> Git finds many merge bases between 'master' and 'next' while\n> creating this merge. In addition to the tip of 'master' back when\n> we made such a merge back from 'master' to 'next' was made the last\n> time, which is the most reasonable merge base to explain the\n> histories of both branches, all the tips of topic branches that\n> graduated recently are merge bases. Because these tips of topic\n> branches were already in 'next', the tip of 'next' reaches them, and\n> because they just graduated to 'master', the tip of 'master' reaches\n> them, too. And these topics are independent most of the time (that\n> is the point of employing the topic-branch workflow), so they cannot\n> be reduced.\n\nThe idea here is to exclude tips of topic branches as \"obviously\nless useful as merge bases than the mainline commit\". Aside from\nthe fact that the approach is purely a heuristic that heavily relies\non convention aka \"topic branch workflow\", there is a caveat (or\nmore that I haven't thought of yet). \n\nOne is that there may be no merge base found that is on the first\nparent chain with this particular patch. When any of the topics\nthat just graduated to 'master' was forked off of 'master' after the\nlatest merge from 'master' to 'next' was made, then the merge base\non the first parent chain, i.e. the commit on 'master' that was\nmerged to 'next' the last time, will be an ancestor of the tip of\nthat recently forked topic, which is another common ancestor between\n'master' and 'next' being merged (hence removed as redundant). We\nwill be left with only the merge bases that are off first-parent\nchain, and I think \"git merge\" will say \"no related histories; I\nwon't merge them\".\n\nI do not know if that is a problem in practice, but if it turns out\nto be, it probably can be corrected by updating the way how the\npaint_down_to_common() function works. It still stops traversal,\neven with this patch, when a commit is found to be common and place\nit to the \"potential merge bases\" list, but instead we could keep\ndigging until we hit a commit that is common between PARENT1 and\nPARENT2 and also is on the first-parent chain, without declaring\nthat we found one result.\n\nBut that probably ends up being the same as ignoring all side\nbranches from merges and finding merge bases only paying attention\nto the first-parent chain.\n"},{"id":"304427","messageId":"xmqqr37cja56.fsf@gitster.mtv.corp.google.com","threadId":"44318","inReplyTo":"20161019042345.29766-1-gitster@pobox.com","subject":"Re: [PATCH 0/7] Rejecting useless merge bases","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-19T21:34:29Z","receivedAt":"2016-10-19T21:34:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> This is a continuation of\n>\n> http://public-inbox.org/git/xmqqmvi2sj8f.fsf@gitster.mtv.corp.google.com\n\nI scanned all two-parent merges in git.git leading to 'next' and\n'pu' and reproduced them with or without the new --fp-base-only\noption. I also did the same experiment in linux.git, but only for\nthe latest 10,000 merges.\n\nThis exercise yielded some interesting numbers.\n\nAmong the total 10,995 merges, 10,487 merges had only one merge base\nand that merge base was on the first-parent chain, i.e. the result\nof reproduction is the same with or without \"--fp-base-only\".\n\nThere were 65 merges with multiple merge-bases but all of these\nmerge bases were on the first-parent chain, i.e. again the result is\nthe same with or without \"--fp-base-only\".\n\nThe remaining 443 merges had merge bases that are not on the\nfirst-parent chain. These merges, when recreated with\n\"--fp-base-only\", would use different/reduced set of merge bases to\ndrive merge-recursive machinery and could produce different results.\n\nAmong these 443, \"git merge\" with or without the \"--fp-base-only\"\noption successfully auto-resolved and produced the same result as\nrecorded in the real history for 214 of them. They stopped in\nconflicts but \"git ls-files -s\" output in their conflicted states\nwere the same, i.e. they left the identical conflicts, for 221 of\nthem.\n\nThe remaining 8 merges were auto-resolved the same way with or\nwithout the \"--fp-base-only\" option, but they were different from\nthe merge in the real history (i.e. the real history had an evil\nmerge there to adjust for non-textual conflicts).\n\nThe most important numbers was 0. There was no merges whose\nreproduction with and without \"--fp-base-only\" produced different\nresults.\n\n\nFor linux.git the numbers are:\n\n - total merges looked at: 10,000\n - single merge base: 9,705\n - multi merge base all on the first parent chain: 123\n - fp-base-only eligible: 172\n - cleanly resolved the same way w/ or w/o fp-only: 118\n - conflicted the same way w/ or w/o fp-only: 54\n - evil merges among fp-base-only eligible merges: 0\n - fp-base-only mismerges: 0\n"},{"id":"311181","messageId":"8a9b3f20-eed2-c59b-f7ea-3c68b3c30bf5@alum.mit.edu","threadId":"44318","inReplyTo":"xmqqmvi2sj8f.fsf@gitster.mtv.corp.google.com","subject":"Re: [RFD] should all merge bases be equal?","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-02-09T14:44:09Z","receivedAt":"2017-02-09T14:44:20Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 10/18/2016 12:28 AM, Junio C Hamano wrote:\n> [...]\n> Being accustomed how fast my merges go, there is one merge that\n> hiccups for me every once in a few days: merging back from 'master'\n> to 'next'. [...]\n> \n> The reason why this merge is slow is because it typically have many\n> merge bases. [...]\n\nI overlooked this topic until just now :-(\n\nI spent a lot of time looking at merge bases a couple of years ago [1],\noriginally motivated by the crappy diffs you get from\n\n git diff master...branch\n\nwhen the merge base is chosen poorly. In that email I include a lot of\ndata and suggest a different heuristic, namely to define the \"best\"\nmerge base $M to be the one that minimizes the number of non-merge\ncommits between $M and either of the branch tips (it doesn't matter\nwhich one you choose); i.e., the one that minimizes\n\n git rev-list --count --no-merges $M..$TIP\n\n. The idea is that a merge base that is \"closer\" content-wise to the\ntips will probably yield smaller diffs. I would expect that merge base\nalso to yield simpler merges, though I didn't test that. Relying on the\nnumber of commits (rather than some other measure of how much the\ncontent has been changed) is only a heuristic, but it seems to work well\nand it can be implemented pretty cheaply.\n\nWe actually use an algorithm like the one I described at GitHub, though\nit is implemented as a script rather than ever having been integrated\ninto git. And (for no particular reason) we include merge commits in the\ncommit count (it doesn't make much difference whether merges are\nincluded or excluded).\n\nYour idea to look at the first-parent histories of the two branch tips\nis an interesting one and has the nice theoretical property that it is\nbased on the DAG topology rather than a count of commits. I'd be very\ncurious to see how the sizes of asymmetric diffs differ between your\nmethod and mine, because for me smaller and more readable diffs are one\nof the main benefits of better merge bases.\n\nI would worry a bit that your proposed algorithm won't perform as well\nfor people who use less disciplined workflows than git.git or the Linux\nkernel. For example, many people merge a lot more frequently and\nchaotically, maybe even with the parents reversed from the canonical order.\n\nAnyway, I mostly wanted to remind you of the earlier discussion of this\ntopic. There's a lot more information there.\n\nMichael\n\n[1] http://public-inbox.org/git/539A25BF.4060501@alum.mit.edu/\n\n"},{"id":"311186","messageId":"xmqqlgtfs3np.fsf@gitster.mtv.corp.google.com","threadId":"44318","inReplyTo":"8a9b3f20-eed2-c59b-f7ea-3c68b3c30bf5@alum.mit.edu","subject":"Re: [RFD] should all merge bases be equal?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-02-09T16:57:30Z","receivedAt":"2017-02-09T16:58:56Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty writes:\n\n> Anyway, I mostly wanted to remind you of the earlier discussion of this\n> topic. There's a lot more information there.\n>\n> Michael\n>\n> [1] http://public-inbox.org/git/539A25BF.4060501@alum.mit.edu/\n\nYour http://public-inbox.org/git/53A3F67A.80501@alum.mit.edu/ in the\nthread appears to me the best place to continue exploring.\n\nThanks for the link. \n"}]}