RE: merge-base not working as expected when base is ahead

RE: merge-base not working as expected when base is ahead

[Ekelhart Jakob]

Dear Git,

git merge-base --fork-point "master" not working if master is already newer then my current branch.
Very oddly it seems to work whenever you had the expected commit checked out previously - what made it very tricky to detect this problem.

Example:
 - Clone "https://github.com/jekelhart/GitInfoTry"
 - Switch to branch "v1.0.0"
 - git merge-base --fork-point "master"
   - or: git merge-base --fork-point "origin/master" 
 - expected result: fork point "fbb1db34c6317a6e8b319c1ec261e97ca1672c22"
 - but result is empty

In the repo where we created this example tree in the first place the command returned the expected fork point. If you clone it new and fresh it does not return any result anymore.

Works, however, on branch "v2.0.0". Assumption: because "master" is older.(?)
I think it works locally because the command uses the reflog in addition(!), however, it should work without the local reflog as well. (since the history was not modified in any way)

BR, Jakob

Re: merge-base not working as expected when base is ahead

[Michael J Gruber]

Ekelhart Jakob venit, vidit, dixit 13.09.2017 17:07:
> Dear Git,
> 
> git merge-base --fork-point "master" not working if master is already newer then my current branch.
> Very oddly it seems to work whenever you had the expected commit checked out previously - what made it very tricky to detect this problem.
> 
> Example:
>  - Clone "https://github.com/jekelhart/GitInfoTry"
>  - Switch to branch "v1.0.0"
>  - git merge-base --fork-point "master"
>    - or: git merge-base --fork-point "origin/master" 
>  - expected result: fork point "fbb1db34c6317a6e8b319c1ec261e97ca1672c22"
>  - but result is empty
> 
> In the repo where we created this example tree in the first place the command returned the expected fork point. If you clone it new and fresh it does not return any result anymore.
> 
> Works, however, on branch "v2.0.0". Assumption: because "master" is older.(?)
> I think it works locally because the command uses the reflog in addition(!), however, it should work without the local reflog as well. (since the history was not modified in any way)

The documentation lies, unfortunately. It claims that in fork-mode, "git
merge-base" "also" looks at the reflog. In fact, the code explicitely
*discards* any merge bases that it finds but which are not in the
reflog. (The merge base that you find for v2.0.0 is in the reflog
because it's the checked out HEAD.)

Removing the corresponding check gives the merge base for v1.0.0 that
you expect, and git still passes all tests. But I'll look at the history
of these lines before I submit a patch.

Michael

[PATCH 0/3] merge-base --fork-point fixes

[Michael J Gruber]

merge-base --fork-point does not quite work as advertised when the
reflog is empty or partial. This series brings it in line with the
documentation and, hopefully, with the original intent.

Michael J Gruber (3):
  t6010: test actual test output
  merge-base: return fork-point outside reflog
  merge-base: find fork-point outside partial reflog

 builtin/merge-base.c  | 20 ++++----------------
 t/t6010-merge-base.sh | 21 +++++++++++++++++++--
 2 files changed, 23 insertions(+), 18 deletions(-)

-- 
2.14.1.712.gda4591c8a2

[PATCH 1/3] t6010: test actual test output

[Michael J Gruber]

4f21454b55 ("merge-base: handle --fork-point without reflog",
2016-10-12) introduced a fix for merge-base --fork-point without reflog
and a test. While that test is fine, it did not update expected nor actual
output and tested that of the previous test instead.

Fix the test to test the merge-base output, not just its return code.

Signed-off-by: Michael J Gruber <git@grubix.eu>
---
 t/t6010-merge-base.sh | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
index 31db7b5f91..17fffd7998 100755
--- a/t/t6010-merge-base.sh
+++ b/t/t6010-merge-base.sh
@@ -262,8 +262,9 @@ test_expect_success 'using reflog to find the fork point' '
 
 test_expect_success '--fork-point works with empty reflog' '
 	git -c core.logallrefupdates=false branch no-reflog base &&
-	git merge-base --fork-point no-reflog derived &&
-	test_cmp expect3 actual
+	git rev-parse base >expect &&
+	git merge-base --fork-point no-reflog derived >actual &&
+	test_cmp expect actual
 '
 
 test_expect_success 'merge-base --octopus --all for complex tree' '
-- 
2.14.1.712.gda4591c8a2

Re: [PATCH 1/3] t6010: test actual test output

[Jeff King]

On Thu, Sep 14, 2017 at 03:15:18PM +0200, Michael J Gruber wrote:

> 4f21454b55 ("merge-base: handle --fork-point without reflog",
> 2016-10-12) introduced a fix for merge-base --fork-point without reflog
> and a test. While that test is fine, it did not update expected nor actual
> output and tested that of the previous test instead.

Oops. The use of the existing "expect3" was intentional (the idea being
that we are repeating the identical step from the previous test with the
slight tweak of not having a reflog). But obviously failing to write to
"actual" at all was a mistake.

That said, I'm OK with reiterating the expected output.

-Peff

Re: [PATCH 1/3] t6010: test actual test output

[Michael J Gruber]

Jeff King venit, vidit, dixit 14.09.2017 16:34:
> On Thu, Sep 14, 2017 at 03:15:18PM +0200, Michael J Gruber wrote:
> 
>> 4f21454b55 ("merge-base: handle --fork-point without reflog",
>> 2016-10-12) introduced a fix for merge-base --fork-point without reflog
>> and a test. While that test is fine, it did not update expected nor actual
>> output and tested that of the previous test instead.
> 
> Oops. The use of the existing "expect3" was intentional (the idea being
> that we are repeating the identical step from the previous test with the
> slight tweak of not having a reflog). But obviously failing to write to
> "actual" at all was a mistake.
> 
> That said, I'm OK with reiterating the expected output.

expect3 had a different content, too ;)

Michael

Re: [PATCH 1/3] t6010: test actual test output

[Jeff King]

On Fri, Sep 15, 2017 at 12:01:27PM +0200, Michael J Gruber wrote:

> Jeff King venit, vidit, dixit 14.09.2017 16:34:
> > On Thu, Sep 14, 2017 at 03:15:18PM +0200, Michael J Gruber wrote:
> > 
> >> 4f21454b55 ("merge-base: handle --fork-point without reflog",
> >> 2016-10-12) introduced a fix for merge-base --fork-point without reflog
> >> and a test. While that test is fine, it did not update expected nor actual
> >> output and tested that of the previous test instead.
> > 
> > Oops. The use of the existing "expect3" was intentional (the idea being
> > that we are repeating the identical step from the previous test with the
> > slight tweak of not having a reflog). But obviously failing to write to
> > "actual" at all was a mistake.
> > 
> > That said, I'm OK with reiterating the expected output.
> 
> expect3 had a different content, too ;)

Oh, then it was just horribly broken, then. Oops. :)

Thanks for fixing.

-Peff

[PATCH 2/3] merge-base: return fork-point outside reflog

[Michael J Gruber]

4f21454b55 ("merge-base: handle --fork-point without reflog",
2016-10-12) fixed the case without reflog, but only partially:
The original code checks whether the merge base candidates are from the
list that we started with, which was the list of reflog entries before
4f21454b55 and the list of reflog entries - or the ref itself if empty -
after. The test from 4f21454b55 tested in a situation where the merge
base candidate equalled the commit at refname, so it was on this (1
item) list by accident.

In fact, per documentation "--fork-point" looks at the reflog in
addition to doing the usual walk from the tip. The original design
description in d96855ff51 ("merge-base: teach "--fork-point" mode",
2013-10-23) describes this as computing from a virtual merge-base of all
the historical tips of refname. They may or may not all be present in
the reflog (think pruning, non-ff fetching, fast forwarding etc.),
so filtering by the current contents of the reflog is potentially
harmful, and it does not seem to fulfill any purpose in the original
design.

Remove the filtering and add a test for an out-of-reflog merge base.

Reported-by: Ekelhart Jakob <jakob.ekelhart@fsw.at>
Signed-off-by: Michael J Gruber <git@grubix.eu>
---
 builtin/merge-base.c  | 18 +++---------------
 t/t6010-merge-base.sh |  8 ++++++++
 2 files changed, 11 insertions(+), 15 deletions(-)

diff --git a/builtin/merge-base.c b/builtin/merge-base.c
index 6dbd167d3b..926a7615ea 100644
--- a/builtin/merge-base.c
+++ b/builtin/merge-base.c
@@ -186,23 +186,11 @@ static int handle_fork_point(int argc, const char **argv)
 	 * There should be one and only one merge base, when we found
 	 * a common ancestor among reflog entries.
 	 */
-	if (!bases || bases->next) {
+	if (!bases || bases->next)
 		ret = 1;
-		goto cleanup_return;
-	}
-
-	/* And the found one must be one of the reflog entries */
-	for (i = 0; i < revs.nr; i++)
-		if (&bases->item->object == &revs.commit[i]->object)
-			break; /* found */
-	if (revs.nr <= i) {
-		ret = 1; /* not found */
-		goto cleanup_return;
-	}
-
-	printf("%s\n", oid_to_hex(&bases->item->object.oid));
+	else
+		printf("%s\n", oid_to_hex(&bases->item->object.oid));
 
-cleanup_return:
 	free_commit_list(bases);
 	return ret;
 }
diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
index 17fffd7998..850463d4f2 100755
--- a/t/t6010-merge-base.sh
+++ b/t/t6010-merge-base.sh
@@ -267,6 +267,14 @@ test_expect_success '--fork-point works with empty reflog' '
 	test_cmp expect actual
 '
 
+test_expect_success '--fork-point works with merge-base outside reflog' '
+	git -c core.logallrefupdates=false checkout no-reflog &&
+	git -c core.logallrefupdates=false commit --allow-empty -m "Commit outside reflogs" &&
+	git rev-parse base >expect &&
+	git merge-base --fork-point no-reflog derived >actual &&
+	test_cmp expect actual
+'
+
 test_expect_success 'merge-base --octopus --all for complex tree' '
 	# Best common ancestor for JE, JAA and JDD is JC
 	#             JE
-- 
2.14.1.712.gda4591c8a2

Re: [PATCH 2/3] merge-base: return fork-point outside reflog

[Junio C Hamano]

Michael J Gruber <git@grubix.eu> writes:

> In fact, per documentation "--fork-point" looks at the reflog in
> addition to doing the usual walk from the tip. The original design
> description in d96855ff51 ("merge-base: teach "--fork-point" mode",
> 2013-10-23) describes this as computing from a virtual merge-base of all
> the historical tips of refname. They may or may not all be present in
> the reflog (think pruning, non-ff fetching, fast forwarding etc.),
> so filtering by the current contents of the reflog is potentially
> harmful, and it does not seem to fulfill any purpose in the original
> design.

Let me think aloud, using the picture from the log message from that
commit.

                         o---B1
                        /
        ---o---o---B2--o---o---o---Base
                \
                 B3
                  \
                   Derived
    
    where the current tip of the "base" branch is at Base, but earlier
    fetch observed that its tip used to be B3 and then B2 and then B1
    before getting to the current commit, and the branch being rebased
    on top of the latest "base" is based on commit B3.

So the logic tries to find a merge base between "Derived" and a
virtual merge commit across Base, B1, B2 and B3.  And it finds B3.

If for some reason we didn't have B3 in the reflog, then wouldn't
the merge base computation between Derived and a virtual merge
commit across Base, B2 and B2 (but not B3 because we no longer know
about it due to its lack in the reflog) find 'o' that is the parent
of B2 and B3?  Wouldn't that lead to both B3 and Derived replayed
when the user of the fork-point potion rebases the history of
Derived?

Perhaps that is the best we could do with a pruned reflog that lacks
B3, but if that is the case, I wonder if it may be better to fail
the request saying that we cannot find the fork-point (because,
well, your reflog no longer has sufficient information), than
silently give a wrong result, and in this case, we can tell between
a correct result (i.e. the merge base is one of the commits we still
know was at the tip) and a wrong one (i.e. the merge base is not any
of the commits in the reflog).

If we declare --fork-point is the best effort option and may give an
answer that is not better than without the option, then I think this
patch is OK, but that diminishes the value of the option as a
building block, I am afraid.

Callers that are more careful could ask merge-base with --fork-point
(and happily use it knowing that the result is indeed a commit that
used to be at the tip), or fall back to the result merge-base
without --fork-point gives (because you could do no better) and deal
with duplicates that may happen due to the imprecise determination.
With this change, these callers will get result from a call to
"merge-base --fork-point" that may or may not be definite, and they
cannot tell.  For lazy users, making the option itself to fall back
may be simpler to use, and certainly is a valid stance to take when
implementing a convenience option to a Porcelain command, but I do
not know if it is a good idea to throw "merge-base --fork-point"
into that category.



>
> Remove the filtering and add a test for an out-of-reflog merge base.
>
> Reported-by: Ekelhart Jakob <jakob.ekelhart@fsw.at>
> Signed-off-by: Michael J Gruber <git@grubix.eu>
> ---
>  builtin/merge-base.c  | 18 +++---------------
>  t/t6010-merge-base.sh |  8 ++++++++
>  2 files changed, 11 insertions(+), 15 deletions(-)
>
> diff --git a/builtin/merge-base.c b/builtin/merge-base.c
> index 6dbd167d3b..926a7615ea 100644
> --- a/builtin/merge-base.c
> +++ b/builtin/merge-base.c
> @@ -186,23 +186,11 @@ static int handle_fork_point(int argc, const char **argv)
>  	 * There should be one and only one merge base, when we found
>  	 * a common ancestor among reflog entries.
>  	 */
> -	if (!bases || bases->next) {
> +	if (!bases || bases->next)
>  		ret = 1;
> -		goto cleanup_return;
> -	}
> -
> -	/* And the found one must be one of the reflog entries */
> -	for (i = 0; i < revs.nr; i++)
> -		if (&bases->item->object == &revs.commit[i]->object)
> -			break; /* found */
> -	if (revs.nr <= i) {
> -		ret = 1; /* not found */
> -		goto cleanup_return;
> -	}
> -
> -	printf("%s\n", oid_to_hex(&bases->item->object.oid));
> +	else
> +		printf("%s\n", oid_to_hex(&bases->item->object.oid));
>  
> -cleanup_return:
>  	free_commit_list(bases);
>  	return ret;
>  }
> diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
> index 17fffd7998..850463d4f2 100755
> --- a/t/t6010-merge-base.sh
> +++ b/t/t6010-merge-base.sh
> @@ -267,6 +267,14 @@ test_expect_success '--fork-point works with empty reflog' '
>  	test_cmp expect actual
>  '
>  
> +test_expect_success '--fork-point works with merge-base outside reflog' '
> +	git -c core.logallrefupdates=false checkout no-reflog &&
> +	git -c core.logallrefupdates=false commit --allow-empty -m "Commit outside reflogs" &&
> +	git rev-parse base >expect &&
> +	git merge-base --fork-point no-reflog derived >actual &&
> +	test_cmp expect actual
> +'
> +
>  test_expect_success 'merge-base --octopus --all for complex tree' '
>  	# Best common ancestor for JE, JAA and JDD is JC
>  	#             JE

Re: [PATCH 2/3] merge-base: return fork-point outside reflog

[Phillip Wood]

On 15/09/17 03:48, Junio C Hamano wrote:
> 
> Michael J Gruber <git@grubix.eu> writes:
> 
>> In fact, per documentation "--fork-point" looks at the reflog in
>> addition to doing the usual walk from the tip. The original design
>> description in d96855ff51 ("merge-base: teach "--fork-point" mode",
>> 2013-10-23) describes this as computing from a virtual merge-base of all
>> the historical tips of refname. They may or may not all be present in
>> the reflog (think pruning, non-ff fetching, fast forwarding etc.),
>> so filtering by the current contents of the reflog is potentially
>> harmful, and it does not seem to fulfill any purpose in the original
>> design.
> 
> Let me think aloud, using the picture from the log message from that
> commit.
> 
>                          o---B1
>                         /
>         ---o---o---B2--o---o---o---Base
>                 \
>                  B3
>                   \
>                    Derived
>     
>     where the current tip of the "base" branch is at Base, but earlier
>     fetch observed that its tip used to be B3 and then B2 and then B1
>     before getting to the current commit, and the branch being rebased
>     on top of the latest "base" is based on commit B3.
> 
> So the logic tries to find a merge base between "Derived" and a
> virtual merge commit across Base, B1, B2 and B3.  And it finds B3.


Thanks for this explanation, I've never been sure exactly what
--fork-point did, after reading this I think I understand it.

> If for some reason we didn't have B3 in the reflog, then wouldn't
> the merge base computation between Derived and a virtual merge
> commit across Base, B2 and B2 (but not B3 because we no longer know
> about it due to its lack in the reflog) find 'o' that is the parent
> of B2 and B3?  Wouldn't that lead to both B3 and Derived replayed
> when the user of the fork-point potion rebases the history of
> Derived?
> 
> Perhaps that is the best we could do with a pruned reflog that lacks
> B3, but if that is the case, I wonder if it may be better to fail
> the request saying that we cannot find the fork-point (because,
> well, your reflog no longer has sufficient information), than
> silently give a wrong result, and in this case, we can tell between
> a correct result (i.e. the merge base is one of the commits we still
> know was at the tip) and a wrong one (i.e. the merge base is not any
> of the commits in the reflog).
> 
> If we declare --fork-point is the best effort option and may give an
> answer that is not better than without the option, then I think this
> patch is OK, but that diminishes the value of the option as a
> building block, I am afraid.

I'd tend to agree with you that it would be better to fail rather than
give a best effort. I've got a script that I use to sync the branch I'm
working on between my desktop and laptop. When it pulls it checks the
local head and the compares it to the remote head before pulling. If
they match then it does 'git reset --hard $new_remote', if the local
head is descended from the old remote head then it does 'git rebase
--onto $new_remote $old_remote', otherwise it refuses to update the
local head. If I've understood --fork-point correctly then I could use
'git rebase --fork-point $remote_branch' if it failed when it couldn't
find a merge base in the reflog of the remote branch.

> 
> Callers that are more careful could ask merge-base with --fork-point
> (and happily use it knowing that the result is indeed a commit that
> used to be at the tip), or fall back to the result merge-base
> without --fork-point gives (because you could do no better) and deal
> with duplicates that may happen due to the imprecise determination.
> With this change, these callers will get result from a call to
> "merge-base --fork-point" that may or may not be definite, and they
> cannot tell.  For lazy users, making the option itself to fall back
> may be simpler to use, and certainly is a valid stance to take when
> implementing a convenience option to a Porcelain command, but I do
> not know if it is a good idea to throw "merge-base --fork-point"
> into that category.
> 

Best Wishes

Phillip

Re: [PATCH 2/3] merge-base: return fork-point outside reflog

[Michael J Gruber]

Junio C Hamano venit, vidit, dixit 15.09.2017 04:48:
> Michael J Gruber <git@grubix.eu> writes:
> 
>> In fact, per documentation "--fork-point" looks at the reflog in
>> addition to doing the usual walk from the tip. The original design
>> description in d96855ff51 ("merge-base: teach "--fork-point" mode",
>> 2013-10-23) describes this as computing from a virtual merge-base of all
>> the historical tips of refname. They may or may not all be present in
>> the reflog (think pruning, non-ff fetching, fast forwarding etc.),
>> so filtering by the current contents of the reflog is potentially
>> harmful, and it does not seem to fulfill any purpose in the original
>> design.
> 
> Let me think aloud, using the picture from the log message from that
> commit.
> 
>                          o---B1
>                         /
>         ---o---o---B2--o---o---o---Base
>                 \
>                  B3
>                   \
>                    Derived
>     
>     where the current tip of the "base" branch is at Base, but earlier
>     fetch observed that its tip used to be B3 and then B2 and then B1
>     before getting to the current commit, and the branch being rebased
>     on top of the latest "base" is based on commit B3.
> 
> So the logic tries to find a merge base between "Derived" and a
> virtual merge commit across Base, B1, B2 and B3.  And it finds B3.
> 
> If for some reason we didn't have B3 in the reflog, then wouldn't
> the merge base computation between Derived and a virtual merge
> commit across Base, B2 and B2 (but not B3 because we no longer know
> about it due to its lack in the reflog) find 'o' that is the parent
> of B2 and B3? 

Yes.

> Wouldn't that lead to both B3 and Derived replayed
> when the user of the fork-point potion rebases the history of
> Derived?

Replayed, yes. What that means would depend on how B3 ended up being
"off base" (reset or rebase, e.g.): the replay could lead to a reapply
without conflict, or with conflict, or an empty (discarded) commit,
depending on "how much of B3" is still "on base".

> Perhaps that is the best we could do with a pruned reflog that lacks
> B3, but if that is the case, I wonder if it may be better to fail
> the request saying that we cannot find the fork-point (because,
> well, your reflog no longer has sufficient information), than
> silently give a wrong result, and in this case, we can tell between
> a correct result (i.e. the merge base is one of the commits we still
> know was at the tip) and a wrong one (i.e. the merge base is not any
> of the commits in the reflog).
> 
> If we declare --fork-point is the best effort option and may give an
> answer that is not better than without the option, then I think this
> patch is OK, but that diminishes the value of the option as a
> building block, I am afraid.
> 
> Callers that are more careful could ask merge-base with --fork-point
> (and happily use it knowing that the result is indeed a commit that
> used to be at the tip), or fall back to the result merge-base
> without --fork-point gives (because you could do no better) and deal
> with duplicates that may happen due to the imprecise determination.
> With this change, these callers will get result from a call to
> "merge-base --fork-point" that may or may not be definite, and they
> cannot tell.  For lazy users, making the option itself to fall back
> may be simpler to use, and certainly is a valid stance to take when
> implementing a convenience option to a Porcelain command, but I do
> not know if it is a good idea to throw "merge-base --fork-point"
> into that category.

Simply put, "git merge-base ref commit" looks at the (graph) history of
ref and considers merge-base candidates that are also in the graph
history of commit. This is the "graph notion" of merge-base, and the
result is immanently determined by the DAG.

There is also the "reflog notion" where you look at the "reflog history"
of ref. The result depends on the reflog, which itself is "volatile"
(think prune), and such is the result.

Now, the original documentation of merge-base says that "merge-base
--fork-point" looks at the reflog of ref "also" (*in addition to*) the
DAG. That is, the merge-base candidates for "merge-base --fork-point"
are a super-set of those for the plain mode, enhanced by the reflog.
(graph notion plus reflog notion)

The original implementation makes sure that "merge-base --fork-point"
looks *only* at candidates from the reflog. (strict reflog notion)

That is a discrepancy that we should resolve in any case.

Note that with a "complete reflog", the set of reflog merge-base
candidates is a superset of the one from the DAG.

I did not look up the discussion preceeding 4f21454b55 ("merge-base:
handle --fork-point without reflog", 2016-10-12), but if "merge-base
--fork-point" were about a "strict reflog" notion then there was nothing
to fix back then - no reflog, no merge-base candidates. Period.

I don't mind having two modes, say "--reflog" (strict reflog notion) and
"--fork-point" (reflog plus DAG), but the current implementation is
neither, and the current documentation clearly is the latter, which is
what I'm trying to bring the implementaion in line with. Strict mode
would need a revert of 4f21454b55 (which adds the tip of ref if the
reflog is empty) for that mode.

Michael

Re: [PATCH 2/3] merge-base: return fork-point outside reflog

[Junio C Hamano]

Michael J Gruber <git@grubix.eu> writes:

> I did not look up the discussion preceeding 4f21454b55 ("merge-base:
> handle --fork-point without reflog", 2016-10-12), but if "merge-base
> --fork-point" were about a "strict reflog" notion then there was nothing
> to fix back then - no reflog, no merge-base candidates. Period.
>
> I don't mind having two modes, say "--reflog" (strict reflog notion) and
> "--fork-point" (reflog plus DAG), but the current implementation is
> neither, and the current documentation clearly is the latter, which is
> what I'm trying to bring the implementaion in line with. Strict mode
> would need a revert of 4f21454b55 (which adds the tip of ref if the
> reflog is empty) for that mode.

Thanks for pointing out a flaw in the logic in my response.

When the user runs "merge-base --fork-point Branch Derived", the
question she is asking is: "what is the merge-base between the
Derived and a virtual commit across all the commits that we know
were at the tip of the Branch at some point and is the merge-base
commit among one of these historical tips of Branch?"

You are correct to point out that loosening the definition of the
"--fork-point" to lose the "and is the merge-base among the one of
these historical tips?" half of the question may be useful, and we
need to introduce "strict" vs "non-strict" modes in order to allow
such a distinction.  I somehow thought that giving and not giving
the "--fork-point" option would be a sufficient clue to express that
distinction, but that is not the same thing and my reasoning was
flawed.  Even when the exact answer of the more strict version of
the "--fork-point" (i.e. what the current implementation computes)
is not available because of missing reflog entries, the merge-base
computation that takes available reflog entries into account but
that does not insist that the resulting base must be among the known
historical tips (i.e. what your patch 2/3 wants to compute) could be
closer to the fork-point than "merge-base Branch Derived" without
"--fork-point" option would compute, and could be more useful as a
"best --onto commit that is guessed automatically" for the purpose
of "rebase".  I agree that there is a value in what your patch 2/3
wants to do when the current one that is more strict would say
"there is no known fork-point"---we would gain a way to say "... but
this is the best guess based on available data that may be better
than getting no answer." which we lack.

Having said all that, I do not agree with your last sentence in the
paragraph I quoted above.  It is a mere implementation detail to
consult the reflog to find out the set of "historical tips of the
Branch"; the current tip by definition is among the commits in that
set, even when the reflog of Branch is missing.  What 4f21454b55 did
was a reasonable "fix" that is still in line with the definition of
"--fork-point" from that point of view.

Whether we add a "looser" version of "--fork-point" to the system or
not, the more strict version should still use the current tip as one
of the historical tips (i.e. those that we would take from the
reflog if the reflog were not empty) in the more "strict" mode.  The
looser version may also want to do so as well.

Thanks.

Re: [PATCH 2/3] merge-base: return fork-point outside reflog

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> ...  I agree that there is a value in what your patch 2/3
> wants to do when the current one that is more strict would say
> "there is no known fork-point"---we would gain a way to say "... but
> this is the best guess based on available data that may be better
> than getting no answer." which we lack.
>
> Having said all that, I do not agree with your last sentence in the
> paragraph I quoted above.  It is a mere implementation detail to
> consult the reflog to find out the set of "historical tips of the
> Branch"; the current tip by definition is among the commits in that
> set, even when the reflog of Branch is missing.  What 4f21454b55 did
> was a reasonable "fix" that is still in line with the definition of
> "--fork-point" from that point of view.
>
> Whether we add a "looser" version of "--fork-point" to the system or
> not, the more strict version should still use the current tip as one
> of the historical tips (i.e. those that we would take from the
> reflog if the reflog were not empty) in the more "strict" mode.  The
> looser version may also want to do so as well.

So, should I mark this in What's cooking report as "expecting a
reroll", anticipating that a new option would be added to trigger
the new & looser behaviour?

Re: [PATCH 2/3] merge-base: return fork-point outside reflog

[Michael J Gruber]

Junio C Hamano venit, vidit, dixit 21.09.2017 08:27:
> Junio C Hamano <gitster@pobox.com> writes:
> 
>> ...  I agree that there is a value in what your patch 2/3
>> wants to do when the current one that is more strict would say
>> "there is no known fork-point"---we would gain a way to say "... but
>> this is the best guess based on available data that may be better
>> than getting no answer." which we lack.
>>
>> Having said all that, I do not agree with your last sentence in the
>> paragraph I quoted above.  It is a mere implementation detail to
>> consult the reflog to find out the set of "historical tips of the
>> Branch"; the current tip by definition is among the commits in that
>> set, even when the reflog of Branch is missing.  What 4f21454b55 did
>> was a reasonable "fix" that is still in line with the definition of
>> "--fork-point" from that point of view.
>>
>> Whether we add a "looser" version of "--fork-point" to the system or
>> not, the more strict version should still use the current tip as one
>> of the historical tips (i.e. those that we would take from the
>> reflog if the reflog were not empty) in the more "strict" mode.  The
>> looser version may also want to do so as well.
> 
> So, should I mark this in What's cooking report as "expecting a
> reroll", anticipating that a new option would be added to trigger
> the new & looser behaviour?
> 

I dunno. Some participants in this thread considered my patch to be a
fix rather than alternative behaviour. So I hoped for more responses to
your response. (Re-adding dscho on cc - our thread graph forked...)

Also, I'm undecided about about your reflog argument above - if we leave
"--fork-point" to be the current behaviour including Jeff's fix then the
documentation would need an even bigger overhaul, because it's neither
"reflog also" (as claimed in the doc) nor "reflog only" (as in the
original implementation) but "historical tips as inferred from the
current value and the reflog".

In any case, for two modes we need two names for the options. Maybe
--fork-point and --fork-base because in the loose mode, you may get a
"base of a strict fork point"?

Michael

Re: [PATCH 2/3] merge-base: return fork-point outside reflog

[Junio C Hamano]

Michael J Gruber <git@grubix.eu> writes:

> Also, I'm undecided about about your reflog argument above - if we leave
> "--fork-point" to be the current behaviour including Jeff's fix then the
> documentation would need an even bigger overhaul, because it's neither
> "reflog also" (as claimed in the doc) nor "reflog only" (as in the
> original implementation) but "historical tips as inferred from the
> current value and the reflog".

Even though things like "reflog only", "reflog also", may be
something implementors may care about, they are irrelevant
implementation details to the intended audience.  "The bases that
are not in reflogs are ignored" _does_ matter, as it affects the
outcome, and that may be a bit too strict a filter (which this
series takes us in a good direction to fix) but what the readers
need to know is the real-world implications of the choices made at
the implementation detail level, and more importantly, what the
implementation is trying to compute.

It is a documentation bug (with or without these patches) if the
current text gives an impression that the code is trying to do
anything but "guessing the fork point using historical tips".

> In any case, for two modes we need two names for the options. Maybe
> --fork-point and --fork-base because in the loose mode, you may get a
> "base of a strict fork point"?

Perhaps.

Re: [PATCH 2/3] merge-base: return fork-point outside reflog

[Michael J Gruber]

Junio C Hamano venit, vidit, dixit 22.09.2017 03:49:
> Michael J Gruber <git@grubix.eu> writes:
> 
>> Also, I'm undecided about about your reflog argument above - if we leave
>> "--fork-point" to be the current behaviour including Jeff's fix then the
>> documentation would need an even bigger overhaul, because it's neither
>> "reflog also" (as claimed in the doc) nor "reflog only" (as in the
>> original implementation) but "historical tips as inferred from the
>> current value and the reflog".
> 
> Even though things like "reflog only", "reflog also", may be
> something implementors may care about, they are irrelevant
> implementation details to the intended audience.  "The bases that
> are not in reflogs are ignored" _does_ matter, as it affects the
> outcome, and that may be a bit too strict a filter (which this
> series takes us in a good direction to fix) but what the readers
> need to know is the real-world implications of the choices made at
> the implementation detail level, and more importantly, what the
> implementation is trying to compute.
> 
> It is a documentation bug (with or without these patches) if the
> current text gives an impression that the code is trying to do
> anything but "guessing the fork point using historical tips".

I'm still trying to understand what the original intent was: If we
abstract from the implementation (as we should, as you rightly
emphasize) and talk about historical tips then we have to ask ourselves:
- What is "historical"?
- What is tip?
- Tip of what, i.e. what is a "branch"?

If by "branch" we mean the moving branch ref that it is in git then by
all means, historical tips are the values that that ref ever had, and
all that we can say is that this includes the current value and the
current contents of the branch refs's reflog (which may or may not be
"complete").

Note that this notion of "branch" is completely independent of the DAG,
whereas by definition a "merge-base" is a concept that relies on an
ancestry graph.

If by "branch" we mean everything that is "on" (or in, think
"--contains") that branch - and I assume that is how most users think
about a branch - then it is not clear at all why we should focus on
"historical values that that refname had", which is an implemenation
detail in itself (branch refs is how we implement the branch concept).

Especially, it's not clear why we should exclude for example a commit
that is in between two commits that are in the reflog ("historical
tips") of a branch that has been fast forwarded or reset (-A, then fast
forward to -A-B-C; this excludes B from the list of merge-base candidates).

>> In any case, for two modes we need two names for the options. Maybe
>> --fork-point and --fork-base because in the loose mode, you may get a
>> "base of a strict fork point"?
> 
> Perhaps.
> 

Re: [PATCH 2/3] merge-base: return fork-point outside reflog

[Junio C Hamano]

Michael J Gruber <git@grubix.eu> writes:

> I'm still trying to understand what the original intent was: If we
> abstract from the implementation (as we should, as you rightly
> emphasize) and talk about historical tips then we have to ask ourselves:
> - What is "historical"?
> - What is tip?
> - Tip of what, i.e. what is a "branch"?

The feature was meant to be a solution for "upstream rebased the
branch I based my work on."

Suppose you did

	git clone $URL
	git checkout -b mytopic origin/topic
	work work work and commit commit commit

and then the next "git fetch" found that remote/origin/topic did not
fast-forward, i.e. your upstream rewound and rebuilt the topic.

Now, running

	git rebase origin/topic mytopic

would be a disaster, as it would try to replay all the commits
reachable from mytopic on top of the updated origin/topic, but the
set of commits reachable from mytopic includes those the upstream
used to have, on top of which you based your work, and you are not
interested in replaying them at all.

If you remember where you forked your topic from (you should be able
to tell from "git log mytopic"), then

	git rebase --onto origin/topic $fork_point mytopic

would be the way to replay "your" work on mytopic on top of the
updated upstream.

The reason why "--fork-point" exists is because people wanted to
automate the "remember where you forked your topic from" part.

Your upstream might have rewound the tip of topic many times while
your repository did not fetch from it (iow, the reflog for
origin/topic may not have _all_ the tips of other people observed to
be historicallly at the tip of the remote), but that is immaterial
for our purpose.  As long as you built on top of origin/topic, the
fork point must be one of the commits _you_ saw at the tip and it
does not matter that you did not constantly fetch to observe all the
changes at the remote.

So the answers of these three questions are:

 - "historical": _you_ saw in your repository;

 - "tip": _you_ saw it pointed by the branch you forked your work
   from; and

 - "branch": whatever you consider you based your work on top of,
   typically a remote tracking branch.

Of course, if you are employing a more advanced workflow, you might
not have started your mytopic branch at any of the tip.  E.g.  if
you wanted to extend Ben's fsmonitor topic, you would have forked
your own topic like

	git checkout -b my-fsmonitor origin/pu^2

after fetching from me, and --fork-point would not be of much help
obviously for such a workflow.  But such users will use --onto and
explicitly specify the fork point so it is outside the scope of the
feature.

Re: [PATCH 2/3] merge-base: return fork-point outside reflog

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Michael J Gruber <git@grubix.eu> writes:
>
>> I'm still trying to understand what the original intent was: If we
>> abstract from the implementation (as we should, as you rightly
>> emphasize) and talk about historical tips then we have to ask ourselves:
>> - What is "historical"?
>> - What is tip?
>> - Tip of what, i.e. what is a "branch"?
>
> The feature was meant to be a solution for "upstream rebased the
> branch I based my work on."
> ...

So, what is the status of this thing?

While I think 1/3 and 3/3 of these three definitely make sense, I do
not think "fork-point outside reflog" does as-is If it is not even
part of the commits that were known to be at the tip some time in
the past (including "right now"---which is the fix you made with 3/3
is about), then the patch may make the command return something in
more situations, and these extra things that it returns might even
be improvements, but they are definitely not "fork-points".

To be quite honest, I am not convinced that the extra output you
would get out of the command by removing the latter half of "which
are the ancestors that were known to be at the tip?" would always
give better commit to use as the beginning of the topic to be
rebased, as I do not see any reasoning behind why, unlike the
filtered case where there _is_ a strong reasoning (with explained
limitation) behind it.

As long as the code misidentifies and picks a commits deeper than
necessary, which will force the user to say "rebase --skip", I think
we are OK.  What we want to absolutely avoid is the opposite;
somehow the code misidentifies a commit that is part of the work you
want to rebase as a recommended fork-point, which would cause the
rebase to silently lose changes.  I do not think I saw why it won't
happen explained in the log message of 2/3 at all.

RE: [PATCH 2/3] merge-base: return fork-point outside reflog

[Ekelhart Jakob]

Thank you for all the effort to fix this issue. Unfortunately, we are still suffering from this and our workaround just stopped being sufficient.

We were wondering if there is any way to tell when this fix will be released?

BR Jakob

-----Original Message-----
From: Junio C Hamano *EXTERN* [mailto:gitster@pobox.com] 
Sent: Dienstag, 3. Oktober 2017 08:06
To: Michael J Gruber <git@grubix.eu>
Cc: git@vger.kernel.org; Ekelhart Jakob <jakob.ekelhart@fsw.at>; Jeff King <peff@peff.net>; Johannes Schindelin <johannes.schindelin@gmx.de>
Subject: Re: [PATCH 2/3] merge-base: return fork-point outside reflog

Junio C Hamano <gitster@pobox.com> writes:

> Michael J Gruber <git@grubix.eu> writes:
>
>> I'm still trying to understand what the original intent was: If we 
>> abstract from the implementation (as we should, as you rightly
>> emphasize) and talk about historical tips then we have to ask ourselves:
>> - What is "historical"?
>> - What is tip?
>> - Tip of what, i.e. what is a "branch"?
>
> The feature was meant to be a solution for "upstream rebased the 
> branch I based my work on."
> ...

So, what is the status of this thing?

While I think 1/3 and 3/3 of these three definitely make sense, I do not think "fork-point outside reflog" does as-is If it is not even part of the commits that were known to be at the tip some time in the past (including "right now"---which is the fix you made with 3/3 is about), then the patch may make the command return something in more situations, and these extra things that it returns might even be improvements, but they are definitely not "fork-points".

To be quite honest, I am not convinced that the extra output you would get out of the command by removing the latter half of "which are the ancestors that were known to be at the tip?" would always give better commit to use as the beginning of the topic to be rebased, as I do not see any reasoning behind why, unlike the filtered case where there _is_ a strong reasoning (with explained
limitation) behind it.

As long as the code misidentifies and picks a commits deeper than necessary, which will force the user to say "rebase --skip", I think we are OK.  What we want to absolutely avoid is the opposite; somehow the code misidentifies a commit that is part of the work you want to rebase as a recommended fork-point, which would cause the rebase to silently lose changes.  I do not think I saw why it won't happen explained in the log message of 2/3 at all.

Re: [PATCH 2/3] merge-base: return fork-point outside reflog

[Michael J Gruber]

Ekelhart Jakob venit, vidit, dixit 08.11.2017 09:52:
> Thank you for all the effort to fix this issue. Unfortunately, we are still suffering from this and our workaround just stopped being sufficient.
> 
> We were wondering if there is any way to tell when this fix will be released?
> 
> BR Jakob

Soon (TM) :)

Term start kept me busy, but I'll try and resume dangling topics this
week or next.

It seems the consensus was that current functionality is as designed but
not necessarily as expected, and another mode "--fork-base" (that does
what I suggested as "fix") would meet these expectations. I would reuse
the documentation of the current mode as a description of the new mode
and add documentation for the existing mode ;)

Michael

Re: [PATCH 2/3] merge-base: return fork-point outside reflog

[Junio C Hamano]

Michael J Gruber <git@grubix.eu> writes:

> It seems the consensus was that current functionality is as designed but
> not necessarily as expected, and another mode "--fork-base" (that does
> what I suggested as "fix") would meet these expectations. I would reuse
> the documentation of the current mode as a description of the new mode
> and add documentation for the existing mode ;)

If we are going to have two modes, it would be absolutely necessary
to explain in the documentation what they compute exactly in terms
that the end users understand, so that the users can choose which
one to use.

The current documentation is not that great because it can get away
with "we automatically by magic find the commit on top of which you
forked your branch", but when we have two different kinds of magic,
that would no longer be a useful description to help users to
choose.  We probably need to enhance the description in "Discussion
on fork-point mode" as a preliminary clean-up.  The attached is my
attempt.

I'd expect `--fork-base` to be explained in a similar way and to the
level of detail to help users pick which one of the three options
(i.e. without any option, with fork-point and with the new one) is
appropriate for their situation.  I've been thinking about what your
patch does, and I cannot come up with a reasonable way to explain
what it computes in the terms the users can get their heads around,
with history illustrations.

--- >8 ---
Subject: merge-base --fork-point doc: clarify the example and failure modes

The illustrated history used to explain the `--fork-point` mode
named three keypoint commits B3, B2 and B1 from the oldest to the
newest, which was hard to read.  Relabel them to B0, B1, B2.  Also
illustrate the history after the rebase using the `--fork-point`
facility was made.

The text already mentions use of reflog, but the description is not
clear what benefit we are trying to gain by using reflog.  Clarify
that it is to find the commits that were known to be at the tip of
the remote-tracking branch.  This in turn necessitates users to know
the ramifications of the underlying assumptions, namely, expiry of
reflog entries will make it impossible to determine which commits
were at the tip of the remote-tracking branches and we fail when in
doubt (instead of giving a random and incorrect result without even
warning).  Another limitation is that it won't be useful if you did
not fork from the tip of a remote-tracking branch but from in the
middle.

Describe them.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 Documentation/git-merge-base.txt | 64 +++++++++++++++++++++++++++++++++++-----
 1 file changed, 56 insertions(+), 8 deletions(-)

diff --git a/Documentation/git-merge-base.txt b/Documentation/git-merge-base.txt
index b968b64c38..a4859c8597 100644
--- a/Documentation/git-merge-base.txt
+++ b/Documentation/git-merge-base.txt
@@ -154,23 +154,71 @@ topic origin/master`, the history of remote-tracking branch
 `origin/master` may have been rewound and rebuilt, leading to a
 history of this shape:
 
-	                 o---B1
+	                 o---B2
 	                /
-	---o---o---B2--o---o---o---B (origin/master)
+	---o---o---B1--o---o---o---B (origin/master)
 	        \
-	         B3
+	         B0
 	          \
-	           Derived (topic)
+	           D0---D1---D (topic)
 
-where `origin/master` used to point at commits B3, B2, B1 and now it
+where `origin/master` used to point at commits B0, B1, B2 and now it
 points at B, and your `topic` branch was started on top of it back
-when `origin/master` was at B3. This mode uses the reflog of
-`origin/master` to find B3 as the fork point, so that the `topic`
-can be rebased on top of the updated `origin/master` by:
+when `origin/master` was at B0, and you built three commits, D0, D1,
+and D, on top of it.  Imagine that you now want to rebase the work
+you did on the topic on top of the updated origin/master.
+
+In such a case, `git merge-base origin/master topic` would return the
+parent of B0 in the above picture, but B0^..D is *not* the range of
+commits you would want to replay on top of B (it includes B0, which
+is not what you wrote; it is a commit the other side discarded when
+it moved its tip from B0 to B1).  
+
+`git merge-base --fork-point origin/master topic` is designed to
+help in such a case.  It takes not only B but also B0, B1, and B2
+(i.e. old tips of the remote-tracking branches your repository's
+reflog knows about) into account to see on which commit your topic
+branch was built and finds B0, allowing you to replay only the
+commits on your topic, excluding the commits the other side later
+discarded.
+
+Hence
 
     $ fork_point=$(git merge-base --fork-point origin/master topic)
+
+will find B0, and
+
     $ git rebase --onto origin/master $fork_point topic
 
+will replay D0, D1 and D on top of B to create a new history of this
+shape:
+
+                         o---B2
+                        /
+        ---o---o---B1--o---o---o---B (origin/master)
+                \                   \
+                 B0                  D0'--D1'--D' (topic - updated)
+                  \
+                   D0---D1---D (topic - old)
+
+A caveat is that older reflog entries in your repository may be
+expired by `git gc`.  If B0 no longer appears in the reflog of the
+remote-tracking branch `origin/master`, the `--fork-point` mode
+obviously cannot find it and fails, avoiding to give a random and
+useless result (such as the parent of B0, like the same command
+without the `--fork-point` option gives).  
+
+Also, the remote-tracking branch you use the `--fork-point` mode
+with must be the one your topic forked from its tip.  If you forked
+from an older commit than the tip, this mode would not find the fork
+point (imagine in the above sample history B0 did not exist,
+origin/master started at B1, moved to B2 and then B, and you forked
+your topic at origin/master^ when origin/master was B1; the shape of
+the history would be the same as above, without B0, and the parent
+of B1 is what `git merge-base origin/master topic` correctly finds,
+but the `--fork-point` mode will not, because it is not one of the
+commits that used to be at the tip of origin/master).
+
 
 See also
 --------

[PATCH 3/3] merge-base: find fork-point outside partial reflog

[Michael J Gruber]

In fork-point mode, merge-base adds the commit at refname to a list of
candidates to walk from only when the reflog is empty. Therefore, it
fails to find merge bases that are descendants of the most recent reflog
entry.

Add the commit at the tip unconditionally so that a merge base on the
history of refname is found in any case, independent of the state of the
reflog.

Signed-off-by: Michael J Gruber <git@grubix.eu>
---
 builtin/merge-base.c  | 2 +-
 t/t6010-merge-base.sh | 8 ++++++++
 2 files changed, 9 insertions(+), 1 deletion(-)

diff --git a/builtin/merge-base.c b/builtin/merge-base.c
index 926a7615ea..b5b4cf7eac 100644
--- a/builtin/merge-base.c
+++ b/builtin/merge-base.c
@@ -174,7 +174,7 @@ static int handle_fork_point(int argc, const char **argv)
 	revs.initial = 1;
 	for_each_reflog_ent(refname, collect_one_reflog_ent, &revs);
 
-	if (!revs.nr && !get_oid(refname, &oid))
+	if (!get_oid(refname, &oid))
 		add_one_commit(&oid, &revs);
 
 	for (i = 0; i < revs.nr; i++)
diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
index 850463d4f2..78342896c7 100755
--- a/t/t6010-merge-base.sh
+++ b/t/t6010-merge-base.sh
@@ -275,6 +275,14 @@ test_expect_success '--fork-point works with merge-base outside reflog' '
 	test_cmp expect actual
 '
 
+test_expect_success '--fork-point works with merge-base outside partial reflog' '
+	git -c core.logallrefupdates=true branch partial-reflog base &&
+	git rev-parse no-reflog >.git/refs/heads/partial-reflog &&
+	git rev-parse no-reflog >expect &&
+	git merge-base --fork-point partial-reflog no-reflog >actual &&
+	test_cmp expect actual
+'
+
 test_expect_success 'merge-base --octopus --all for complex tree' '
 	# Best common ancestor for JE, JAA and JDD is JC
 	#             JE
-- 
2.14.1.712.gda4591c8a2

Re: [PATCH 3/3] merge-base: find fork-point outside partial reflog

[Jeff King]

On Thu, Sep 14, 2017 at 03:15:20PM +0200, Michael J Gruber wrote:

> In fork-point mode, merge-base adds the commit at refname to a list of
> candidates to walk from only when the reflog is empty. Therefore, it
> fails to find merge bases that are descendants of the most recent reflog
> entry.
> 
> Add the commit at the tip unconditionally so that a merge base on the
> history of refname is found in any case, independent of the state of the
> reflog.

OK, so the reflog we are interested in here is one where the tip commit
is not mentioned. I'm not sure how one gets into that state, but I agree
it makes sense to act as if it's there.

-Peff

Re: [PATCH 0/3] merge-base --fork-point fixes

[Johannes Schindelin]

Hi Michael,

On Thu, 14 Sep 2017, Michael J Gruber wrote:

> merge-base --fork-point does not quite work as advertised when the
> reflog is empty or partial. This series brings it in line with the
> documentation and, hopefully, with the original intent.

Thank you so much for working on this. I recently tried to use
--fork-point in a script of mine and it failed in this surprising way,
too. So here's hoping for this patch series being accepted quickly (and
sorry in advance for not having time to review...).

Ciao,
Dscho

Re: [PATCH 0/3] merge-base --fork-point fixes

[Jeff King]

On Thu, Sep 14, 2017 at 03:15:17PM +0200, Michael J Gruber wrote:

> merge-base --fork-point does not quite work as advertised when the
> reflog is empty or partial. This series brings it in line with the
> documentation and, hopefully, with the original intent.
> 
> Michael J Gruber (3):
>   t6010: test actual test output
>   merge-base: return fork-point outside reflog
>   merge-base: find fork-point outside partial reflog

Patches 1 and 3 look sane to me. Your argument in patch 2 looks
plausible to me, but I'm not familiar enough with the mechanics of
fork-point to have a solid opinion.

-Peff