[PATCH] rebase: use reflog to find common base with upstream

[PATCH] rebase: use reflog to find common base with upstream

[John Keeping]

Commit 15a147e (rebase: use @{upstream} if no upstream specified,
2011-02-09) says:

	Make it default to 'git rebase @{upstream}'. That is also what
	'git pull [--rebase]' defaults to, so it only makes sense that
	'git rebase' defaults to the same thing.

but that isn't actually the case.  Since commit d44e712 (pull: support
rebased upstream + fetch + pull --rebase, 2009-07-19), pull has actually
chosen the most recent reflog entry which is an ancestor of the current
branch if it can find one.

Change rebase so that it uses the same logic.

Signed-off-by: John Keeping <john@keeping.me.uk>
---
 git-rebase.sh     | 8 ++++++++
 t/t3400-rebase.sh | 6 ++++--
 2 files changed, 12 insertions(+), 2 deletions(-)

diff --git a/git-rebase.sh b/git-rebase.sh
index 226752f..fd36cf7 100755
--- a/git-rebase.sh
+++ b/git-rebase.sh
@@ -437,6 +437,14 @@ then
 			error_on_missing_default_upstream "rebase" "rebase" \
 				"against" "git rebase <branch>"
 		fi
+		for reflog in $(git rev-list -g "$upstream_name" 2>/dev/null)
+		do
+			if test "$reflog" = "$(git merge-base "$reflog" HEAD)"
+			then
+				upstream_name=$reflog
+				break
+			fi
+		done
 		;;
 	*)	upstream_name="$1"
 		shift
diff --git a/t/t3400-rebase.sh b/t/t3400-rebase.sh
index ebf93b0..4f45f7e 100755
--- a/t/t3400-rebase.sh
+++ b/t/t3400-rebase.sh
@@ -134,12 +134,14 @@ test_expect_success 'fail when upstream arg is missing and not configured' '
 	test_must_fail git rebase
 '
 
-test_expect_success 'default to @{upstream} when upstream arg is missing' '
+test_expect_success 'default to common base in @{upstream}s reflog if no upstream arg' '
 	git checkout -b default topic &&
 	git config branch.default.remote . &&
 	git config branch.default.merge refs/heads/master &&
 	git rebase &&
-	test "$(git rev-parse default~1)" = "$(git rev-parse master)"
+	git merge-base topic master >expect &&
+	git rev-parse default~1 >actual &&
+	test_cmp expect actual
 '
 
 test_expect_success 'rebase -q is quiet' '
-- 
1.8.4.566.g73d370b

Re: [PATCH] rebase: use reflog to find common base with upstream

[Jonathan Nieder]

Hi,

John Keeping wrote:

>                                    Since commit d44e712 (pull: support
> rebased upstream + fetch + pull --rebase, 2009-07-19), pull has actually
> chosen the most recent reflog entry which is an ancestor of the current
> branch if it can find one.
>
> Change rebase so that it uses the same logic.

Nice idea.

Could pull be made to rely on rebase for this as a follow-up?

[...]
> --- a/git-rebase.sh
> +++ b/git-rebase.sh
> @@ -437,6 +437,14 @@ then
>  			error_on_missing_default_upstream "rebase" "rebase" \
>  				"against" "git rebase <branch>"
>  		fi
> +		for reflog in $(git rev-list -g "$upstream_name" 2>/dev/null)
> +		do
> +			if test "$reflog" = "$(git merge-base "$reflog" HEAD)"

"git merge-base --is-ancestor" is faster.

What should happen if HEAD is not a valid commit?  (Tested with:

	$ git checkout --orphan foo
	$ cat >>.git/config <<EOF
	[branch "foo"]
		remote = origin
		merge = refs/heads/master
	EOF
	$ bin-wrappers/git rebase 2>&1 | wc -l
	83

).

diff --git i/git-rebase.sh w/git-rebase.sh
index fd36cf7..d2e2c2e 100755
--- i/git-rebase.sh
+++ w/git-rebase.sh
@@ -439,7 +439,7 @@ then
 		fi
 		for reflog in $(git rev-list -g "$upstream_name" 2>/dev/null)
 		do
-			if test "$reflog" = "$(git merge-base "$reflog" HEAD)"
+			if git merge-base --is-ancestor "$reflog" HEAD
 			then
 				upstream_name=$reflog
 				break

Re: [PATCH] rebase: use reflog to find common base with upstream

[John Keeping]

On Wed, Oct 16, 2013 at 12:24:13PM -0700, Jonathan Nieder wrote:
> John Keeping wrote:
> 
> >                                    Since commit d44e712 (pull: support
> > rebased upstream + fetch + pull --rebase, 2009-07-19), pull has actually
> > chosen the most recent reflog entry which is an ancestor of the current
> > branch if it can find one.
> >
> > Change rebase so that it uses the same logic.
> 
> Nice idea.
> 
> Could pull be made to rely on rebase for this as a follow-up?

It's not an obvious change to do that (at least to me) - pull does the
different steps of figuring out the base and then rebasing at different
points in the script.

> [...]
> > --- a/git-rebase.sh
> > +++ b/git-rebase.sh
> > @@ -437,6 +437,14 @@ then
> >  			error_on_missing_default_upstream "rebase" "rebase" \
> >  				"against" "git rebase <branch>"
> >  		fi
> > +		for reflog in $(git rev-list -g "$upstream_name" 2>/dev/null)
> > +		do
> > +			if test "$reflog" = "$(git merge-base "$reflog" HEAD)"
> 
> "git merge-base --is-ancestor" is faster.

We should probably change git-pull to use that as well.

> What should happen if HEAD is not a valid commit?  (Tested with:
> 
> 	$ git checkout --orphan foo
> 	$ cat >>.git/config <<EOF
> 	[branch "foo"]
> 		remote = origin
> 		merge = refs/heads/master
> 	EOF
> 	$ bin-wrappers/git rebase 2>&1 | wc -l
> 	83
> 
> ).

Adding "2>/dev/null" to the merge-base line silences most of that, all
we're left with is "fatal: Needed a single revision" which is the same
as I get from master's git-rebase.  I think silencing stderr is the
right thing to do here - in the worst case we just use the merge-base of
the two branches instead of the appropriate reflog entry.

> diff --git i/git-rebase.sh w/git-rebase.sh
> index fd36cf7..d2e2c2e 100755
> --- i/git-rebase.sh
> +++ w/git-rebase.sh
> @@ -439,7 +439,7 @@ then
>  		fi
>  		for reflog in $(git rev-list -g "$upstream_name" 2>/dev/null)
>  		do
> -			if test "$reflog" = "$(git merge-base "$reflog" HEAD)"
> +			if git merge-base --is-ancestor "$reflog" HEAD
>  			then
>  				upstream_name=$reflog
>  				break

Re: [PATCH] rebase: use reflog to find common base with upstream

[Martin von Zweigbergk]

On Wed, Oct 16, 2013 at 11:53 AM, John Keeping <john@keeping.me.uk> wrote:
> Commit 15a147e (rebase: use @{upstream} if no upstream specified,
> 2011-02-09) says:
>
>         Make it default to 'git rebase @{upstream}'. That is also what
>         'git pull [--rebase]' defaults to, so it only makes sense that
>         'git rebase' defaults to the same thing.
>
> but that isn't actually the case.  Since commit d44e712 (pull: support
> rebased upstream + fetch + pull --rebase, 2009-07-19), pull has actually
> chosen the most recent reflog entry which is an ancestor of the current
> branch if it can find one.

It is exactly this inconsistency between "git rebase" and "git pull
--rebase" that confused me enough to make me send my first email to
this list almost 4 years ago [1], so thanks for working on this! I
finished that thread with:

  Would it make sense to teach "git rebase" the same tricks as "git
pull --rebase"?

Then it took me a year before I sent a patch not unlike this one [2].
To summarize, the patch did not get accepted then because it makes
rebase a little slower (or a lot slower in some cases). "git pull
--rebase" is of course at least as slow in the same cases, but because
it often involves connecting to a remote host, people would probably
blame the connection rather than git itself even in those rare (?)
cases.

I think

  git merge-base HEAD $(git rev-list -g "$upstream_name")

is roughly correct and hopefully fast enough. That can lead to too
long a command line, so I was planning on teaching merge-base a
--stdin option, but never got around to it.

Martin


[1] http://thread.gmane.org/gmane.comp.version-control.git/136339
[2] http://thread.gmane.org/gmane.comp.version-control.git/166710

Re: [PATCH] rebase: use reflog to find common base with upstream

[John Keeping]

On Sun, Oct 20, 2013 at 10:03:29PM -0700, Martin von Zweigbergk wrote:
> On Wed, Oct 16, 2013 at 11:53 AM, John Keeping <john@keeping.me.uk> wrote:
> > Commit 15a147e (rebase: use @{upstream} if no upstream specified,
> > 2011-02-09) says:
> >
> >         Make it default to 'git rebase @{upstream}'. That is also what
> >         'git pull [--rebase]' defaults to, so it only makes sense that
> >         'git rebase' defaults to the same thing.
> >
> > but that isn't actually the case.  Since commit d44e712 (pull: support
> > rebased upstream + fetch + pull --rebase, 2009-07-19), pull has actually
> > chosen the most recent reflog entry which is an ancestor of the current
> > branch if it can find one.
> 
> It is exactly this inconsistency between "git rebase" and "git pull
> --rebase" that confused me enough to make me send my first email to
> this list almost 4 years ago [1], so thanks for working on this! I
> finished that thread with:
> 
>   Would it make sense to teach "git rebase" the same tricks as "git
> pull --rebase"?
> 
> Then it took me a year before I sent a patch not unlike this one [2].
> To summarize, the patch did not get accepted then because it makes
> rebase a little slower (or a lot slower in some cases). "git pull
> --rebase" is of course at least as slow in the same cases, but because
> it often involves connecting to a remote host, people would probably
> blame the connection rather than git itself even in those rare (?)
> cases.
> 
> I think
> 
>   git merge-base HEAD $(git rev-list -g "$upstream_name")
> 
> is roughly correct and hopefully fast enough. That can lead to too
> long a command line, so I was planning on teaching merge-base a
> --stdin option, but never got around to it.

I'm not sure we should worry about the additional overhead here.  In the
common case, we should hit a common ancestor within the first couple of
reflog entries; and in the case that will be slow, it's likely that
there are a lot of differences between the branches so the cherry
comparison phase will take a while anyway.

Re: [PATCH] rebase: use reflog to find common base with upstream

[Martin von Zweigbergk]

On Mon, Oct 21, 2013 at 4:24 AM, John Keeping <john@keeping.me.uk> wrote:
> On Sun, Oct 20, 2013 at 10:03:29PM -0700, Martin von Zweigbergk wrote:
>> On Wed, Oct 16, 2013 at 11:53 AM, John Keeping <john@keeping.me.uk> wrote:
>> > Commit 15a147e (rebase: use @{upstream} if no upstream specified,
>> > 2011-02-09) says:
>> >
>> >         Make it default to 'git rebase @{upstream}'. That is also what
>> >         'git pull [--rebase]' defaults to, so it only makes sense that
>> >         'git rebase' defaults to the same thing.
>> >
>> > but that isn't actually the case.  Since commit d44e712 (pull: support
>> > rebased upstream + fetch + pull --rebase, 2009-07-19), pull has actually
>> > chosen the most recent reflog entry which is an ancestor of the current
>> > branch if it can find one.
>>
>> It is exactly this inconsistency between "git rebase" and "git pull
>> --rebase" that confused me enough to make me send my first email to
>> this list almost 4 years ago [1], so thanks for working on this! I
>> finished that thread with:
>>
>>   Would it make sense to teach "git rebase" the same tricks as "git
>> pull --rebase"?
>>
>> Then it took me a year before I sent a patch not unlike this one [2].
>> To summarize, the patch did not get accepted then because it makes
>> rebase a little slower (or a lot slower in some cases). "git pull
>> --rebase" is of course at least as slow in the same cases, but because
>> it often involves connecting to a remote host, people would probably
>> blame the connection rather than git itself even in those rare (?)
>> cases.
>>
>> I think
>>
>>   git merge-base HEAD $(git rev-list -g "$upstream_name")
>>
>> is roughly correct and hopefully fast enough. That can lead to too
>> long a command line, so I was planning on teaching merge-base a
>> --stdin option, but never got around to it.
>
> I'm not sure we should worry about the additional overhead here.  In the
> common case, we should hit a common ancestor within the first couple of
> reflog entries; and in the case that will be slow, it's likely that
> there are a lot of differences between the branches so the cherry
> comparison phase will take a while anyway.

Perhaps true. I created a simple commit based on my origin/master@{1}
in git.git, which happened to be 136 commits behind origin/master.
Before (a modified version of) your patch, it took 0.756s to rebase it
(best of 5) and afterwards it took 0.720s.

And in a worse case: The same test with one commit off my
origin/master@{13}, 2910 behind origin/master, shows an increase from
2.75s to 4.04s.

And a degenerate case: I created a test branch (called u) with
1000-entry reflog from the output of "git rev-list --first-parent
origin/master | head -1000 | tac" and created the same simple commit
as before off of the end of this reflog (u@{999}). This ended up 3769
commits behind u@{0} (aka origin/master). In this case it went from
3.43s to 3m32s. Obviously, this was a degenerate case designed to be
slow, but I think it's still worth noting that one can get such O(n^2)
behavior e.g. if one lets a branch get out of sync with an upstream
that's very frequently fetches (I've heard of people running
short-interval cron jobs that fetch from a remote).

I do like the feature, but I'm still concerned about this last case.

Re: [PATCH] rebase: use reflog to find common base with upstream

[Junio C Hamano]

Martin von Zweigbergk <martinvonz@gmail.com> writes:

> I think
>
>   git merge-base HEAD $(git rev-list -g "$upstream_name")
>
> is roughly correct and hopefully fast enough. That can lead to too
> long a command line, so I was planning on teaching merge-base a
> --stdin option, but never got around to it.

Sorry for coming in late.

I think the above with s/HEAD/$curr_branch/ is a good way to compute
what the whole "for reflog in $(git rev-list -g $remoteref" loop
computes when one of the historic tips recorded in the reflog was
where $curr_branch forked from, i.e. the loop actually finds at
least one ancestor in the reflog and breaks out after setting
oldremoteref.  But it would give a completely different commit if
none of the reflog entries is a fork point.

A two patch series forthcoming.

[PATCH 0/2] finding the fork point from reflog entries

[Junio C Hamano]

The first one is a clean-up of the code to parse command line
options to "git merge-base".  Options such as "--independent",
"--is-ancestor" and "--octopus" are mutually exclusive and it is
better expressed in terms of the recently introduced OPT_CMDMODE.

The second one implements the entire logic of the for loop we see in
"git pull --rebase" directly using get_merge_bases_many() and
postprocessing the result.

Junio C Hamano (2):
  merge-base: use OPT_CMDMODE and clarify the command line parsing
  merge-base: "--reflog" mode finds fork point from reflog entries

 builtin/merge-base.c  | 115 +++++++++++++++++++++++++++++++++++++++++++-------
 t/t6010-merge-base.sh |  27 ++++++++++++
 2 files changed, 126 insertions(+), 16 deletions(-)

-- 
1.8.4.1-799-g1c32b8d

[PATCH 1/2] merge-base: use OPT_CMDMODE and clarify the command line parsing

[Junio C Hamano]

The --octopus, --independent and --is-ancestor are mutually
exclusive command modes (in addition to not giving any of these
options), so represent them as such using the recent OPT_CMDMODE
facility available since 11588263 (parse-options: add OPT_CMDMODE(),
2013-07-30), which is in v1.8.4-82-g366b80b.  --all is compatible
only with plain vanilla mode and --octopus mode, and the minimum
number of arguments the command takes depends on the command modes,
so these are now separately checked in each command mode.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 builtin/merge-base.c | 38 ++++++++++++++++++++++----------------
 1 file changed, 22 insertions(+), 16 deletions(-)

diff --git a/builtin/merge-base.c b/builtin/merge-base.c
index e88eb93..d39c910 100644
--- a/builtin/merge-base.c
+++ b/builtin/merge-base.c
@@ -90,32 +90,38 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
 	struct commit **rev;
 	int rev_nr = 0;
 	int show_all = 0;
-	int octopus = 0;
-	int reduce = 0;
-	int is_ancestor = 0;
+	int cmdmode = 0;
 
 	struct option options[] = {
 		OPT_BOOL('a', "all", &show_all, N_("output all common ancestors")),
-		OPT_BOOL(0, "octopus", &octopus, N_("find ancestors for a single n-way merge")),
-		OPT_BOOL(0, "independent", &reduce, N_("list revs not reachable from others")),
-		OPT_BOOL(0, "is-ancestor", &is_ancestor,
-			 N_("is the first one ancestor of the other?")),
+		OPT_CMDMODE(0, "octopus", &cmdmode,
+			    N_("find ancestors for a single n-way merge"), 'o'),
+		OPT_CMDMODE(0, "independent", &cmdmode,
+			    N_("list revs not reachable from others"), 'r'),
+		OPT_CMDMODE(0, "is-ancestor", &cmdmode,
+			    N_("is the first one ancestor of the other?"), 'a'),
 		OPT_END()
 	};
 
 	git_config(git_default_config, NULL);
 	argc = parse_options(argc, argv, prefix, options, merge_base_usage, 0);
-	if (!octopus && !reduce && argc < 2)
-		usage_with_options(merge_base_usage, options);
-	if (is_ancestor && (show_all || octopus || reduce))
-		die("--is-ancestor cannot be used with other options");
-	if (is_ancestor)
+
+	if (cmdmode == 'a') {
+		if (argc < 2)
+			usage_with_options(merge_base_usage, options);
+		if (show_all)
+			die("--is-ancestor cannot be used with --all");
 		return handle_is_ancestor(argc, argv);
-	if (reduce && (show_all || octopus))
-		die("--independent cannot be used with other options");
+	}
 
-	if (octopus || reduce)
-		return handle_octopus(argc, argv, reduce, show_all);
+	if (cmdmode == 'r' && show_all)
+		die("--independent cannot be used with --all");
+
+	if (cmdmode == 'r' || cmdmode == 'o')
+		return handle_octopus(argc, argv, cmdmode == 'r', show_all);
+
+	if (argc < 2)
+		usage_with_options(merge_base_usage, options);
 
 	rev = xmalloc(argc * sizeof(*rev));
 	while (argc-- > 0)
-- 
1.8.4.1-799-g1c32b8d

[PATCH 2/2] merge-base: "--reflog" mode finds fork point from reflog entries

[Junio C Hamano]

The "git pull --rebase" command computes the fork point of the
branch being rebased using the reflog entries of the "base" branch
(typically a remote-tracking branch) the branch's work was based on,
in order to cope with the case in which the "base" branch has been
rewound and rebuilt.  For example, if the history looked like this:

                     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, it tries to find
B3 by going through the output of "git rev-list --reflog base" (i.e.
Base, B1, B2, B3) until it finds a commit that is an ancestor of the
current tip "Derived".

Internally, we have get_merge_bases_many() that can compute this
with one-go.  We would want a merge-base between Derived and a
fictitious merge commit that would result by merging all the
historical tips of "base".  When such a commit exist, we should get
a single result, which exactly match one of the reflog entries of
"base".

Teach "git merge-base" a new mode, "--reflog", to compute exactly
that.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 builtin/merge-base.c  | 77 +++++++++++++++++++++++++++++++++++++++++++++++++++
 t/t6010-merge-base.sh | 27 ++++++++++++++++++
 2 files changed, 104 insertions(+)

diff --git a/builtin/merge-base.c b/builtin/merge-base.c
index d39c910..7b9bc15 100644
--- a/builtin/merge-base.c
+++ b/builtin/merge-base.c
@@ -1,6 +1,7 @@
 #include "builtin.h"
 #include "cache.h"
 #include "commit.h"
+#include "refs.h"
 #include "parse-options.h"
 
 static int show_merge_base(struct commit **rev, int rev_nr, int show_all)
@@ -27,6 +28,7 @@ static const char * const merge_base_usage[] = {
 	N_("git merge-base [-a|--all] --octopus <commit>..."),
 	N_("git merge-base --independent <commit>..."),
 	N_("git merge-base --is-ancestor <commit> <commit>"),
+	N_("git merge-base --reflog <ref> [<commit>]"),
 	NULL
 };
 
@@ -85,6 +87,73 @@ static int handle_is_ancestor(int argc, const char **argv)
 		return 1;
 }
 
+struct rev_collect {
+	struct commit **commit;
+	int nr;
+	int alloc;
+};
+
+static int collect_one_reflog_ent(unsigned char *osha1, unsigned char *nsha1,
+				  const char *ident, unsigned long timestamp,
+				  int tz, const char *message, void *cbdata_)
+{
+	struct rev_collect *revs = cbdata_;
+	struct commit *commit = lookup_commit(nsha1);
+	if (commit) {
+		ALLOC_GROW(revs->commit, revs->nr + 1, revs->alloc);
+		revs->commit[revs->nr++] = commit;
+	}
+	return 0;
+}
+
+static int handle_reflog(int argc, const char **argv)
+{
+	unsigned char sha1[20];
+	char *refname;
+	const char *commitname;
+	struct rev_collect revs;
+	struct commit *derived;
+	struct commit_list *bases;
+	int i;
+
+	switch (dwim_ref(argv[0], strlen(argv[0]), sha1, &refname)) {
+	case 0:
+		die("No such ref: '%s'", argv[0]);
+	case 1:
+		break; /* good */
+	default:
+		die("Ambiguous refname: '%s'", argv[0]);
+	}
+
+	commitname = (argc == 2) ? argv[1] : "HEAD";
+	if (get_sha1(commitname, sha1))
+		die("Not a valid object name: '%s'", commitname);
+
+	derived = lookup_commit_reference(sha1);
+	memset(&revs, 0, sizeof(revs));
+	for_each_reflog_ent(refname, collect_one_reflog_ent, &revs);
+
+	bases = get_merge_bases_many(derived, revs.nr, revs.commit, 0);
+
+	/*
+	 * There should be one and only one merge base, when we found
+	 * a common ancestor among reflog entries.
+	 */
+	if (!bases || bases->next)
+		return 1;
+
+	/* 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)
+		return 1; /* not found */
+
+	printf("%s\n", sha1_to_hex(bases->item->object.sha1));
+	free_commit_list(bases);
+	return 0;
+}
+
 int cmd_merge_base(int argc, const char **argv, const char *prefix)
 {
 	struct commit **rev;
@@ -100,6 +169,8 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
 			    N_("list revs not reachable from others"), 'r'),
 		OPT_CMDMODE(0, "is-ancestor", &cmdmode,
 			    N_("is the first one ancestor of the other?"), 'a'),
+		OPT_CMDMODE(0, "reflog", &cmdmode,
+			    N_("find where <commit> forked from reflog of <ref>"), 'g'),
 		OPT_END()
 	};
 
@@ -120,6 +191,12 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
 	if (cmdmode == 'r' || cmdmode == 'o')
 		return handle_octopus(argc, argv, cmdmode == 'r', show_all);
 
+	if (cmdmode == 'g') {
+		if (argc < 1 || 2 < argc)
+			usage_with_options(merge_base_usage, options);
+		return handle_reflog(argc, argv);
+	}
+
 	if (argc < 2)
 		usage_with_options(merge_base_usage, options);
 
diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
index f80bba8..3a1abee 100755
--- a/t/t6010-merge-base.sh
+++ b/t/t6010-merge-base.sh
@@ -230,4 +230,31 @@ test_expect_success 'criss-cross merge-base for octopus-step' '
 	test_cmp expected.sorted actual.sorted
 '
 
+test_expect_success 'using reflog to find the fork point' '
+	git reset --hard &&
+	git checkout -b base $E &&
+	(
+		for count in 1 2 3 4 5
+		do
+			git commit --allow-empty -m "Base commit #$count" &&
+			git rev-parse HEAD >expect$count &&
+			git checkout -B derived &&
+			git commit --allow-empty -m "Derived #$count" &&
+			git rev-parse HEAD >derived$count &&
+			git checkout base &&
+			count=$(( $count + 1 )) || exit 1
+		done
+
+		for count in 1 2 3 4 5
+		do
+			git merge-base --reflog base $(cat derived$count) >actual &&
+			test_cmp expect$count actual || exit 1
+		done
+
+		# check defaulting to HEAD
+		git merge-base --reflog base >actual &&
+		test_cmp expect5 actual
+	)
+'
+
 test_done
-- 
1.8.4.1-799-g1c32b8d

Re: [PATCH 2/2] merge-base: "--reflog" mode finds fork point from reflog entries

[Eric Sunshine]

On Thu, Oct 24, 2013 at 3:11 PM, Junio C Hamano <gitster@pobox.com> wrote:
> diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
> index f80bba8..3a1abee 100755
> --- a/t/t6010-merge-base.sh
> +++ b/t/t6010-merge-base.sh
> @@ -230,4 +230,31 @@ test_expect_success 'criss-cross merge-base for octopus-step' '
>         test_cmp expected.sorted actual.sorted
>  '
>
> +test_expect_success 'using reflog to find the fork point' '
> +       git reset --hard &&
> +       git checkout -b base $E &&
> +       (
> +               for count in 1 2 3 4 5
> +               do
> +                       git commit --allow-empty -m "Base commit #$count" &&
> +                       git rev-parse HEAD >expect$count &&
> +                       git checkout -B derived &&
> +                       git commit --allow-empty -m "Derived #$count" &&
> +                       git rev-parse HEAD >derived$count &&
> +                       git checkout base &&
> +                       count=$(( $count + 1 )) || exit 1
> +               done

Did you want && here?

> +
> +               for count in 1 2 3 4 5
> +               do
> +                       git merge-base --reflog base $(cat derived$count) >actual &&
> +                       test_cmp expect$count actual || exit 1
> +               done

And here?

> +
> +               # check defaulting to HEAD
> +               git merge-base --reflog base >actual &&
> +               test_cmp expect5 actual
> +       )
> +'
> +
>  test_done

Re: [PATCH 2/2] merge-base: "--reflog" mode finds fork point from reflog entries

[Junio C Hamano]

Eric Sunshine <sunshine@sunshineco.com> writes:

> On Thu, Oct 24, 2013 at 3:11 PM, Junio C Hamano <gitster@pobox.com> wrote:
>> diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
>> index f80bba8..3a1abee 100755
>> --- a/t/t6010-merge-base.sh
>> +++ b/t/t6010-merge-base.sh
>> @@ -230,4 +230,31 @@ test_expect_success 'criss-cross merge-base for octopus-step' '
>>         test_cmp expected.sorted actual.sorted
>>  '
>>
>> +test_expect_success 'using reflog to find the fork point' '
>> +       git reset --hard &&
>> +       git checkout -b base $E &&
>> +       (
>> +               for count in 1 2 3 4 5
>> +               do
>> +                       git commit --allow-empty -m "Base commit #$count" &&
>> +                       git rev-parse HEAD >expect$count &&
>> +                       git checkout -B derived &&
>> +                       git commit --allow-empty -m "Derived #$count" &&
>> +                       git rev-parse HEAD >derived$count &&
>> +                       git checkout base &&
>> +                       count=$(( $count + 1 )) || exit 1
>> +               done
>
> Did you want && here?

No, I did not.  Can't you tell from the fact that I didn't put one
there ;-)?

It does not hurt to have one there, but it is not necessary.

Because the loop itself does not &&-cascade from anything else, the
only case anything after "done &&" would be skipped and making the
whole thing fail would be when anything inside the loop fails, but
we already "exit 1" to terminate the whole subprocess in that case,
so we will not continue past the loop.

>> +
>> +               for count in 1 2 3 4 5
>> +               do
>> +                       git merge-base --reflog base $(cat derived$count) >actual &&
>> +                       test_cmp expect$count actual || exit 1
>> +               done
>
> And here?

Likewise.

Thanks.

>> +
>> +               # check defaulting to HEAD
>> +               git merge-base --reflog base >actual &&
>> +               test_cmp expect5 actual
>> +       )
>> +'
>> +
>>  test_done

Re: [PATCH 2/2] merge-base: "--reflog" mode finds fork point from reflog entries

[Eric Sunshine]

On Thu, Oct 24, 2013 at 5:26 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Eric Sunshine <sunshine@sunshineco.com> writes:
>
>> On Thu, Oct 24, 2013 at 3:11 PM, Junio C Hamano <gitster@pobox.com> wrote:
>>> diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
>>> index f80bba8..3a1abee 100755
>>> --- a/t/t6010-merge-base.sh
>>> +++ b/t/t6010-merge-base.sh
>>> @@ -230,4 +230,31 @@ test_expect_success 'criss-cross merge-base for octopus-step' '
>>>         test_cmp expected.sorted actual.sorted
>>>  '
>>>
>>> +test_expect_success 'using reflog to find the fork point' '
>>> +       git reset --hard &&
>>> +       git checkout -b base $E &&
>>> +       (
>>> +               for count in 1 2 3 4 5
>>> +               do
>>> +                       git commit --allow-empty -m "Base commit #$count" &&
>>> +                       git rev-parse HEAD >expect$count &&
>>> +                       git checkout -B derived &&
>>> +                       git commit --allow-empty -m "Derived #$count" &&
>>> +                       git rev-parse HEAD >derived$count &&
>>> +                       git checkout base &&
>>> +                       count=$(( $count + 1 )) || exit 1
>>> +               done
>>
>> Did you want && here?
>
> No, I did not.  Can't you tell from the fact that I didn't put one
> there ;-)?
>
> It does not hurt to have one there, but it is not necessary.
>
> Because the loop itself does not &&-cascade from anything else, the
> only case anything after "done &&" would be skipped and making the
> whole thing fail would be when anything inside the loop fails, but
> we already "exit 1" to terminate the whole subprocess in that case,
> so we will not continue past the loop.

I didn't read inside the loop closely enough to see that. Sorry for the noise.

>
>>> +
>>> +               for count in 1 2 3 4 5
>>> +               do
>>> +                       git merge-base --reflog base $(cat derived$count) >actual &&
>>> +                       test_cmp expect$count actual || exit 1
>>> +               done
>>
>> And here?
>
> Likewise.
>
> Thanks.
>
>>> +
>>> +               # check defaulting to HEAD
>>> +               git merge-base --reflog base >actual &&
>>> +               test_cmp expect5 actual
>>> +       )
>>> +'
>>> +
>>>  test_done

Re: [PATCH 2/2] merge-base: "--reflog" mode finds fork point from reflog entries

[Junio C Hamano]

Eric Sunshine <sunshine@sunshineco.com> writes:

> On Thu, Oct 24, 2013 at 5:26 PM, Junio C Hamano <gitster@pobox.com> wrote:
>> Eric Sunshine <sunshine@sunshineco.com> writes:
>>
>>> On Thu, Oct 24, 2013 at 3:11 PM, Junio C Hamano <gitster@pobox.com> wrote:
>>>> diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
>>>> index f80bba8..3a1abee 100755
>>>> --- a/t/t6010-merge-base.sh
>>>> +++ b/t/t6010-merge-base.sh
>>>> @@ -230,4 +230,31 @@ test_expect_success 'criss-cross merge-base for octopus-step' '
>>>>         test_cmp expected.sorted actual.sorted
>>>>  '
>>>>
>>>> +test_expect_success 'using reflog to find the fork point' '
>>>> +       git reset --hard &&
>>>> +       git checkout -b base $E &&
>>>> +       (
>>>> +               for count in 1 2 3 4 5
>>>> +               do
>>>> +                       git commit --allow-empty -m "Base commit #$count" &&
>>>> +                       git rev-parse HEAD >expect$count &&
>>>> +                       git checkout -B derived &&
>>>> +                       git commit --allow-empty -m "Derived #$count" &&
>>>> +                       git rev-parse HEAD >derived$count &&
>>>> +                       git checkout base &&
>>>> +                       count=$(( $count + 1 )) || exit 1
>>>> +               done
>>>
>>> Did you want && here?
>>
>> No, I did not.  Can't you tell from the fact that I didn't put one
>> there ;-)?
>>
>> It does not hurt to have one there, but it is not necessary.
>>
>> Because the loop itself does not &&-cascade from anything else, the
>> only case anything after "done &&" would be skipped and making the
>> whole thing fail would be when anything inside the loop fails, but
>> we already "exit 1" to terminate the whole subprocess in that case,
>> so we will not continue past the loop.
>
> I didn't read inside the loop closely enough to see that. Sorry
> for the noise.

Heh, you helped me realize that the above was suboptimal, and it
wasn't a noise ;-)

We could do it this way without the subshell and the exit, I would
think.

test_expect_success 'using reflog to find the fork point' '
	git reset --hard &&
	git checkout -b base $E &&
	for count in 1 2 3 4 5
	do
		git commit --allow-empty -m "Base commit #$count" &&
		git rev-parse HEAD >expect$count &&
		git checkout -B derived &&
		git commit --allow-empty -m "Derived #$count" &&
		git rev-parse HEAD >derived$count &&
		git checkout base &&
		count=$(( $count + 1 )) || break
	done &&

	for count in 1 2 3 4 5
	do
		git merge-base --reflog base $(cat derived$count) >actual &&
		test_cmp expect$count actual || break
	done &&

	# check defaulting to HEAD
	git merge-base --reflog base >actual &&
	test_cmp expect5 actual
'

To the earlier code, somebody could add

                (
        +               more setup code &&
        +               yet more setup code &&
                        for count in 1 2 3 4 5

inside the subshell and we would fail to notice fairlure from the
new setup code if we didn't have && after the first "done".  There
is much less risk of that kind of breakage if we did the loop
without subshell and exit and instead with the usual &&-cascade.

Thanks.

[PATCH v2 2/2] merge-base: "--reflog" mode finds fork point from reflog entries

[Junio C Hamano]

The "git pull --rebase" command computes the fork point of the
branch being rebased using the reflog entries of the "base" branch
(typically a remote-tracking branch) the branch's work was based on,
in order to cope with the case in which the "base" branch has been
rewound and rebuilt.  For example, if the history looked like this:

                     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, it tries to find
B3 by going through the output of "git rev-list --reflog base" (i.e.
Base, B1, B2, B3) until it finds a commit that is an ancestor of the
current tip "Derived".

Internally, we have get_merge_bases_many() that can compute this
with one-go.  We would want a merge-base between Derived and a
fictitious merge commit that would result by merging all the
historical tips of "base".  When such a commit exist, we should get
a single result, which exactly match one of the reflog entries of
"base".

Teach "git merge-base" a new mode, "--reflog", to compute exactly
that.

Helped-by: Eric Sunshine <sunshine@sunshineco.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---

 * With updated tests, based on conversation with Eric Sunshine

 builtin/merge-base.c  | 77 +++++++++++++++++++++++++++++++++++++++++++++++++++
 t/t6010-merge-base.sh | 25 +++++++++++++++++
 2 files changed, 102 insertions(+)

diff --git a/builtin/merge-base.c b/builtin/merge-base.c
index d39c910..7b9bc15 100644
--- a/builtin/merge-base.c
+++ b/builtin/merge-base.c
@@ -1,6 +1,7 @@
 #include "builtin.h"
 #include "cache.h"
 #include "commit.h"
+#include "refs.h"
 #include "parse-options.h"
 
 static int show_merge_base(struct commit **rev, int rev_nr, int show_all)
@@ -27,6 +28,7 @@ static const char * const merge_base_usage[] = {
 	N_("git merge-base [-a|--all] --octopus <commit>..."),
 	N_("git merge-base --independent <commit>..."),
 	N_("git merge-base --is-ancestor <commit> <commit>"),
+	N_("git merge-base --reflog <ref> [<commit>]"),
 	NULL
 };
 
@@ -85,6 +87,73 @@ static int handle_is_ancestor(int argc, const char **argv)
 		return 1;
 }
 
+struct rev_collect {
+	struct commit **commit;
+	int nr;
+	int alloc;
+};
+
+static int collect_one_reflog_ent(unsigned char *osha1, unsigned char *nsha1,
+				  const char *ident, unsigned long timestamp,
+				  int tz, const char *message, void *cbdata_)
+{
+	struct rev_collect *revs = cbdata_;
+	struct commit *commit = lookup_commit(nsha1);
+	if (commit) {
+		ALLOC_GROW(revs->commit, revs->nr + 1, revs->alloc);
+		revs->commit[revs->nr++] = commit;
+	}
+	return 0;
+}
+
+static int handle_reflog(int argc, const char **argv)
+{
+	unsigned char sha1[20];
+	char *refname;
+	const char *commitname;
+	struct rev_collect revs;
+	struct commit *derived;
+	struct commit_list *bases;
+	int i;
+
+	switch (dwim_ref(argv[0], strlen(argv[0]), sha1, &refname)) {
+	case 0:
+		die("No such ref: '%s'", argv[0]);
+	case 1:
+		break; /* good */
+	default:
+		die("Ambiguous refname: '%s'", argv[0]);
+	}
+
+	commitname = (argc == 2) ? argv[1] : "HEAD";
+	if (get_sha1(commitname, sha1))
+		die("Not a valid object name: '%s'", commitname);
+
+	derived = lookup_commit_reference(sha1);
+	memset(&revs, 0, sizeof(revs));
+	for_each_reflog_ent(refname, collect_one_reflog_ent, &revs);
+
+	bases = get_merge_bases_many(derived, revs.nr, revs.commit, 0);
+
+	/*
+	 * There should be one and only one merge base, when we found
+	 * a common ancestor among reflog entries.
+	 */
+	if (!bases || bases->next)
+		return 1;
+
+	/* 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)
+		return 1; /* not found */
+
+	printf("%s\n", sha1_to_hex(bases->item->object.sha1));
+	free_commit_list(bases);
+	return 0;
+}
+
 int cmd_merge_base(int argc, const char **argv, const char *prefix)
 {
 	struct commit **rev;
@@ -100,6 +169,8 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
 			    N_("list revs not reachable from others"), 'r'),
 		OPT_CMDMODE(0, "is-ancestor", &cmdmode,
 			    N_("is the first one ancestor of the other?"), 'a'),
+		OPT_CMDMODE(0, "reflog", &cmdmode,
+			    N_("find where <commit> forked from reflog of <ref>"), 'g'),
 		OPT_END()
 	};
 
@@ -120,6 +191,12 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
 	if (cmdmode == 'r' || cmdmode == 'o')
 		return handle_octopus(argc, argv, cmdmode == 'r', show_all);
 
+	if (cmdmode == 'g') {
+		if (argc < 1 || 2 < argc)
+			usage_with_options(merge_base_usage, options);
+		return handle_reflog(argc, argv);
+	}
+
 	if (argc < 2)
 		usage_with_options(merge_base_usage, options);
 
diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
index f80bba8..d5e76a6 100755
--- a/t/t6010-merge-base.sh
+++ b/t/t6010-merge-base.sh
@@ -230,4 +230,29 @@ test_expect_success 'criss-cross merge-base for octopus-step' '
 	test_cmp expected.sorted actual.sorted
 '
 
+test_expect_success 'using reflog to find the fork point' '
+	git reset --hard &&
+	git checkout -b base $E &&
+
+	for count in 1 2 3 4 5
+	do
+		git commit --allow-empty -m "Base commit #$count" &&
+		git rev-parse HEAD >expect$count &&
+		git checkout -B derived &&
+		git commit --allow-empty -m "Derived #$count" &&
+		git rev-parse HEAD >derived$count &&
+		git checkout base || break
+	done &&
+
+	for count in 1 2 3 4 5
+	do
+		git merge-base --reflog base $(cat derived$count) >actual &&
+		test_cmp expect$count actual || break
+	done &&
+
+	# check defaulting to HEAD
+	git merge-base --reflog base >actual &&
+	test_cmp expect5 actual
+'
+
 test_done
-- 
1.8.4.1-799-g1c32b8d

Re: [PATCH v2 2/2] merge-base: "--reflog" mode finds fork point from reflog entries

[Johannes Sixt]

Am 10/25/2013 0:21, schrieb Junio C Hamano:
> +test_expect_success 'using reflog to find the fork point' '
> +	git reset --hard &&
> +	git checkout -b base $E &&
> +
> +	for count in 1 2 3 4 5
> +	do
> +		git commit --allow-empty -m "Base commit #$count" &&
> +		git rev-parse HEAD >expect$count &&
> +		git checkout -B derived &&
> +		git commit --allow-empty -m "Derived #$count" &&
> +		git rev-parse HEAD >derived$count &&
> +		git checkout base || break
> +	done &&
> +
> +	for count in 1 2 3 4 5
> +	do
> +		git merge-base --reflog base $(cat derived$count) >actual &&
> +		test_cmp expect$count actual || break
> +	done &&

This does not work as intended because the exit code of 'break' is always
zero. Unlike 'exit' and 'return', it does *not* pick up the exit code of
the last command that was executed.

That's annoying, but makes some sense because 'break 2' does not mean to
apply exit code 2 to the command, either, but to break out of 2 levels of
loops.

You could put the loops into a function from which you 'return', but that
is obscure in this case. The first iteration was better, IMO.

> +
> +	# check defaulting to HEAD
> +	git merge-base --reflog base >actual &&
> +	test_cmp expect5 actual
> +'
> +
>  test_done

-- Hannes

Re: [PATCH v2 2/2] merge-base: "--reflog" mode finds fork point from reflog entries

[John Keeping]

On Fri, Oct 25, 2013 at 09:12:10AM +0200, Johannes Sixt wrote:
> Am 10/25/2013 0:21, schrieb Junio C Hamano:
> > +test_expect_success 'using reflog to find the fork point' '
> > +	git reset --hard &&
> > +	git checkout -b base $E &&
> > +
> > +	for count in 1 2 3 4 5
> > +	do
> > +		git commit --allow-empty -m "Base commit #$count" &&
> > +		git rev-parse HEAD >expect$count &&
> > +		git checkout -B derived &&
> > +		git commit --allow-empty -m "Derived #$count" &&
> > +		git rev-parse HEAD >derived$count &&
> > +		git checkout base || break
> > +	done &&
> > +
> > +	for count in 1 2 3 4 5
> > +	do
> > +		git merge-base --reflog base $(cat derived$count) >actual &&
> > +		test_cmp expect$count actual || break
> > +	done &&
> 
> This does not work as intended because the exit code of 'break' is always
> zero. Unlike 'exit' and 'return', it does *not* pick up the exit code of
> the last command that was executed.
> 
> That's annoying, but makes some sense because 'break 2' does not mean to
> apply exit code 2 to the command, either, but to break out of 2 levels of
> loops.
> 
> You could put the loops into a function from which you 'return', but that
> is obscure in this case. The first iteration was better, IMO.

Wouldn't it be simpler to just return from the test?  That is, replace
the "break" in the above patch with "return 1".

There's code in several other test cases (e.g. t3311) which handles the
same problem like that.

Re: [PATCH v2 2/2] merge-base: "--reflog" mode finds fork point from reflog entries

[Johannes Sixt]

Am 10/25/2013 10:09, schrieb John Keeping:
> On Fri, Oct 25, 2013 at 09:12:10AM +0200, Johannes Sixt wrote:
>> You could put the loops into a function from which you 'return', but that
>> is obscure in this case. The first iteration was better, IMO.
> 
> Wouldn't it be simpler to just return from the test?  That is, replace
> the "break" in the above patch with "return 1".

Good catch! We explicitly have

test_eval_ () {
	# This is a separate function because some tests use
	# "return" to end a test_expect_success block early.
	eval </dev/null >&3 2>&4 "$*"
}

to protect this use of return.

-- Hannes

Re: [PATCH v2 2/2] merge-base: "--reflog" mode finds fork point from reflog entries

[Junio C Hamano]

Johannes Sixt <j.sixt@viscovery.net> writes:

>> +	for count in 1 2 3 4 5
>> +	do
>> +		git merge-base --reflog base $(cat derived$count) >actual &&
>> +		test_cmp expect$count actual || break
>> +	done &&
>
> This does not work as intended because the exit code of 'break' is always
> zero. Unlike 'exit' and 'return', it does *not* pick up the exit code of
> the last command that was executed.

You are right. I obviously was not thinking straight.

> You could put the loops into a function from which you 'return',
> but that is obscure in this case. The first iteration was better,
> IMO.

I do not think using "return 1" is a good thing to do, either.

We saw breakages with different shells around the use of "return"
and we know the original "exit 1 inside subshell" works reliably
everywher.

I'll send out a revamped version later today, updating not just the
test but the implementation.

Thank for a dose of sanity.

[PATCH v3 2/2] merge-base: teach "--fork-point" mode

[Junio C Hamano]

The "git pull --rebase" command computes the fork point of the
branch being rebased using the reflog entries of the "base" branch
(typically a remote-tracking branch) the branch's work was based on,
in order to cope with the case in which the "base" branch has been
rewound and rebuilt.  For example, if the history looked like this:

                     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, it tries to find
B3 by going through the output of "git rev-list --reflog base" (i.e.
Base, B1, B2, B3) until it finds a commit that is an ancestor of the
current tip "Derived".

Internally, we have get_merge_bases_many() that can compute this
with one-go.  We would want a merge-base between Derived and a
fictitious merge commit that would result by merging all the
historical tips of "base".  When such a commit exist, we should get
a single result, which exactly match one of the reflog entries of
"base".

Teach "git merge-base" a new mode, "--fork-point", to compute
exactly that.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---

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

 > I'll send out a revamped version later today, updating not just the
 > test but the implementation.

 And here is the reroll. The test is back to use "exit 1 from a subshell"
 pattern to notice a breakage in the loop. I also rolled the "we can
 pick one more old commit from the reflog after it got expired"
 change John noticed into the logic.

 It also comes with a documentation update. The option is not called
 --reflog but --fork-point; naming a feature after what it does
 (i.e. it finds the fork point) is a lot more sensible than naming
 it after how it happens to do what it does (i.e. it does so by
 peeking into the reflog).

 Documentation/git-merge-base.txt |  35 ++++++++++++-
 builtin/merge-base.c             | 103 +++++++++++++++++++++++++++++++++++++++
 t/t6010-merge-base.sh            |  27 ++++++++++
 3 files changed, 163 insertions(+), 2 deletions(-)

diff --git a/Documentation/git-merge-base.txt b/Documentation/git-merge-base.txt
index 87842e3..b383766 100644
--- a/Documentation/git-merge-base.txt
+++ b/Documentation/git-merge-base.txt
@@ -13,6 +13,7 @@ SYNOPSIS
 'git merge-base' [-a|--all] --octopus <commit>...
 'git merge-base' --is-ancestor <commit> <commit>
 'git merge-base' --independent <commit>...
+'git merge-base' --fork-point <ref> [<commit>]
 
 DESCRIPTION
 -----------
@@ -24,8 +25,8 @@ that does not have any better common ancestor is a 'best common
 ancestor', i.e. a 'merge base'.  Note that there can be more than one
 merge base for a pair of commits.
 
-OPERATION MODE
---------------
+OPERATION MODES
+---------------
 
 As the most common special case, specifying only two commits on the
 command line means computing the merge base between the given two commits.
@@ -56,6 +57,11 @@ from linkgit:git-show-branch[1] when used with the `--merge-base` option.
 	and exit with status 0 if true, or with status 1 if not.
 	Errors are signaled by a non-zero status that is not 1.
 
+--fork-point::
+	Given a commit that is derived from possibly an earlier
+	incarnation of a ref, find an appropriate fork-point of the
+	derived history to rebase it on top of an updated base
+	history (see discussion on this mode below).
 
 OPTIONS
 -------
@@ -137,6 +143,31 @@ In modern git, you can say this in a more direct way:
 
 instead.
 
+Discussion on fork-point mode
+-----------------------------
+
+After working on the `topic` branch created with `git checkout -b
+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---o---B2--o---o---o---B (origin/master)
+		\
+		 B3
+		  \
+		   Derived (topic)
+
+where `origin/master` used to point at commits B3, B2, B1 and now it
+points at B, and your `topic` branch was stated on top of it back
+when `origin/master` was at B3. This mode uses the reflog of
+`origin/master` to finds B3 as the fork point, so that the `topic`
+can be rebased on top of the updated `origin/master` by:
+
+    $ fork_point=$(git merge-base --fork-point origin/master topic)
+    $ git rebase --onto origin/master $fork_point topic
+
 
 See also
 --------
diff --git a/builtin/merge-base.c b/builtin/merge-base.c
index d39c910..6a674e7 100644
--- a/builtin/merge-base.c
+++ b/builtin/merge-base.c
@@ -1,6 +1,9 @@
 #include "builtin.h"
 #include "cache.h"
 #include "commit.h"
+#include "refs.h"
+#include "diff.h"
+#include "revision.h"
 #include "parse-options.h"
 
 static int show_merge_base(struct commit **rev, int rev_nr, int show_all)
@@ -27,6 +30,7 @@ static const char * const merge_base_usage[] = {
 	N_("git merge-base [-a|--all] --octopus <commit>..."),
 	N_("git merge-base --independent <commit>..."),
 	N_("git merge-base --is-ancestor <commit> <commit>"),
+	N_("git merge-base --fork-point <ref> [<commit>]"),
 	NULL
 };
 
@@ -85,6 +89,97 @@ static int handle_is_ancestor(int argc, const char **argv)
 		return 1;
 }
 
+struct rev_collect {
+	struct commit **commit;
+	int nr;
+	int alloc;
+	unsigned int initial : 1;
+};
+
+static void add_one_commit(unsigned char *sha1, struct rev_collect *revs)
+{
+	struct commit *commit;
+
+	if (is_null_sha1(sha1))
+		return;
+
+	commit = lookup_commit(sha1);
+	if (!commit ||
+	    (commit->object.flags & TMP_MARK) ||
+	    parse_commit(commit))
+		return;
+
+	ALLOC_GROW(revs->commit, revs->nr + 1, revs->alloc);
+	revs->commit[revs->nr++] = commit;
+	commit->object.flags |= TMP_MARK;
+}
+
+static int collect_one_reflog_ent(unsigned char *osha1, unsigned char *nsha1,
+				  const char *ident, unsigned long timestamp,
+				  int tz, const char *message, void *cbdata)
+{
+	struct rev_collect *revs = cbdata;
+
+	if (revs->initial) {
+		revs->initial = 0;
+		add_one_commit(osha1, revs);
+	}
+	add_one_commit(nsha1, revs);
+	return 0;
+}
+
+static int handle_fork_point(int argc, const char **argv)
+{
+	unsigned char sha1[20];
+	char *refname;
+	const char *commitname;
+	struct rev_collect revs;
+	struct commit *derived;
+	struct commit_list *bases;
+	int i;
+
+	switch (dwim_ref(argv[0], strlen(argv[0]), sha1, &refname)) {
+	case 0:
+		die("No such ref: '%s'", argv[0]);
+	case 1:
+		break; /* good */
+	default:
+		die("Ambiguous refname: '%s'", argv[0]);
+	}
+
+	commitname = (argc == 2) ? argv[1] : "HEAD";
+	if (get_sha1(commitname, sha1))
+		die("Not a valid object name: '%s'", commitname);
+
+	derived = lookup_commit_reference(sha1);
+	memset(&revs, 0, sizeof(revs));
+	revs.initial = 1;
+	for_each_reflog_ent(refname, collect_one_reflog_ent, &revs);
+
+	for (i = 0; i < revs.nr; i++)
+		revs.commit[i]->object.flags &= ~TMP_MARK;
+
+	bases = get_merge_bases_many(derived, revs.nr, revs.commit, 0);
+
+	/*
+	 * There should be one and only one merge base, when we found
+	 * a common ancestor among reflog entries.
+	 */
+	if (!bases || bases->next)
+		return 1;
+
+	/* 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)
+		return 1; /* not found */
+
+	printf("%s\n", sha1_to_hex(bases->item->object.sha1));
+	free_commit_list(bases);
+	return 0;
+}
+
 int cmd_merge_base(int argc, const char **argv, const char *prefix)
 {
 	struct commit **rev;
@@ -100,6 +195,8 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
 			    N_("list revs not reachable from others"), 'r'),
 		OPT_CMDMODE(0, "is-ancestor", &cmdmode,
 			    N_("is the first one ancestor of the other?"), 'a'),
+		OPT_CMDMODE(0, "fork-point", &cmdmode,
+			    N_("find where <commit> forked from reflog of <ref>"), 'f'),
 		OPT_END()
 	};
 
@@ -120,6 +217,12 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
 	if (cmdmode == 'r' || cmdmode == 'o')
 		return handle_octopus(argc, argv, cmdmode == 'r', show_all);
 
+	if (cmdmode == 'f') {
+		if (argc < 1 || 2 < argc)
+			usage_with_options(merge_base_usage, options);
+		return handle_fork_point(argc, argv);
+	}
+
 	if (argc < 2)
 		usage_with_options(merge_base_usage, options);
 
diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
index f80bba8..4f09db0 100755
--- a/t/t6010-merge-base.sh
+++ b/t/t6010-merge-base.sh
@@ -230,4 +230,31 @@ test_expect_success 'criss-cross merge-base for octopus-step' '
 	test_cmp expected.sorted actual.sorted
 '
 
+test_expect_success 'using reflog to find the fork point' '
+	git reset --hard &&
+	git checkout -b base $E &&
+
+	(
+		for count in 1 2 3 4 5
+		do
+			git commit --allow-empty -m "Base commit #$count" &&
+			git rev-parse HEAD >expect$count &&
+			git checkout -B derived &&
+			git commit --allow-empty -m "Derived #$count" &&
+			git rev-parse HEAD >derived$count &&
+			git checkout base || exit 1
+		done
+
+		for count in 1 2 3 4 5
+		do
+			git merge-base --fork-point base $(cat derived$count) >actual &&
+			test_cmp expect$count actual || exit 1
+		done
+
+	) &&
+	# check that we correctly default to HEAD
+	git merge-base --fork-point base >actual &&
+	test_cmp expect5 actual
+'
+
 test_done
-- 
1.8.4.1-797-gda615de

Re: [PATCH v3 2/2] merge-base: teach "--fork-point" mode

[Eric Sunshine]

On Fri, Oct 25, 2013 at 5:38 PM, Junio C Hamano <gitster@pobox.com> wrote:
> diff --git a/Documentation/git-merge-base.txt b/Documentation/git-merge-base.txt
> index 87842e3..b383766 100644
> --- a/Documentation/git-merge-base.txt
> +++ b/Documentation/git-merge-base.txt
> @@ -137,6 +143,31 @@ In modern git, you can say this in a more direct way:
>
>  instead.
>
> +Discussion on fork-point mode
> +-----------------------------
> +
> +After working on the `topic` branch created with `git checkout -b
> +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---o---B2--o---o---o---B (origin/master)
> +               \
> +                B3
> +                 \
> +                  Derived (topic)
> +
> +where `origin/master` used to point at commits B3, B2, B1 and now it
> +points at B, and your `topic` branch was stated on top of it back
> +when `origin/master` was at B3. This mode uses the reflog of
> +`origin/master` to finds B3 as the fork point, so that the `topic`

s/finds/find/

> +can be rebased on top of the updated `origin/master` by:
> +
> +    $ fork_point=$(git merge-base --fork-point origin/master topic)
> +    $ git rebase --onto origin/master $fork_point topic
> +
>
>  See also
>  --------

Re: [PATCH v3 2/2] merge-base: teach "--fork-point" mode

[Martin von Zweigbergk]

Thanks for taking care of this! Maybe John or I can finally get the
changes to rebase done after this.

A few comments below. Sorry I didn't find time to review the earlier revisions.

On Fri, Oct 25, 2013 at 2:38 PM, Junio C Hamano <gitster@pobox.com> wrote:
> +
> +where `origin/master` used to point at commits B3, B2, B1 and now it
> +points at B, and your `topic` branch was stated on top of it back

s/stated/started/

> +       bases = get_merge_bases_many(derived, revs.nr, revs.commit, 0);
> +
> +       /*
> +        * There should be one and only one merge base, when we found
> +        * a common ancestor among reflog entries.
> +        */
> +       if (!bases || bases->next)
> +               return 1;
> +
> +       /* 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)
> +               return 1; /* not found */
> +
> +       printf("%s\n", sha1_to_hex(bases->item->object.sha1));
> +       free_commit_list(bases);
> +       return 0;

Should free_commit_list also be called in the two "return 1" cases
above? I suppose the process will exit soon after this, but that seems
to be true for all three cases.

> diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
> index f80bba8..4f09db0 100755
> --- a/t/t6010-merge-base.sh
> +++ b/t/t6010-merge-base.sh
> @@ -230,4 +230,31 @@ test_expect_success 'criss-cross merge-base for octopus-step' '
>         test_cmp expected.sorted actual.sorted
>  '
>
> +test_expect_success 'using reflog to find the fork point' '
> +       git reset --hard &&
> +       git checkout -b base $E &&
> +
> +       (
> +               for count in 1 2 3 4 5
> +               do
> +                       git commit --allow-empty -m "Base commit #$count" &&
> +                       git rev-parse HEAD >expect$count &&
> +                       git checkout -B derived &&
> +                       git commit --allow-empty -m "Derived #$count" &&
> +                       git rev-parse HEAD >derived$count &&
> +                       git checkout base || exit 1

I think this creates a history like

---E---B1--B2--B3--B4--B5 (base)
        \   \   \   \   \
         D1  D2  D3  D4  D5 (derived)

So I think the following test would pass even if you drop the
--fork-point. Did you mean to create a fan-shaped history by resetting
base to $E on every iteration above?

> +                       git merge-base --fork-point base $(cat derived$count) >actual &&
> +                       test_cmp expect$count actual || exit 1

Re: [PATCH v3 2/2] merge-base: teach "--fork-point" mode

[Junio C Hamano]

Martin von Zweigbergk <martinvonz@gmail.com> writes:

>> +       bases = get_merge_bases_many(derived, revs.nr, revs.commit, 0);
>> + ...
>> +       if (revs.nr <= i)
>> +               return 1; /* not found */
>> +
>> +       printf("%s\n", sha1_to_hex(bases->item->object.sha1));
>> +       free_commit_list(bases);
>> +       return 0;
>
> Should free_commit_list also be called in the two "return 1" cases
> above? I suppose the process will exit soon after this, but that seems
> to be true for all three cases.

You are right that the above is inconsistent. Because the code
intends to be called only once in the lifetime of the program,
it calls get_merge_bases_many() with cleanup set to 0, so in that
sense, not freeing them anywhere may make it even more clear that
this function expects to be shortly followed by a process exit.

>> diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
>> index f80bba8..4f09db0 100755
>> --- a/t/t6010-merge-base.sh
>> +++ b/t/t6010-merge-base.sh
>> @@ -230,4 +230,31 @@ test_expect_success 'criss-cross merge-base for octopus-step' '
>>         test_cmp expected.sorted actual.sorted
>>  '
>>
>> +test_expect_success 'using reflog to find the fork point' '
>> +       git reset --hard &&
>> +       git checkout -b base $E &&
>> +
>> +       (
>> +               for count in 1 2 3 4 5
>> +               do
>> +                       git commit --allow-empty -m "Base commit #$count" &&
>> +                       git rev-parse HEAD >expect$count &&
>> +                       git checkout -B derived &&
>> +                       git commit --allow-empty -m "Derived #$count" &&
>> +                       git rev-parse HEAD >derived$count &&
>> +                       git checkout base || exit 1
>
> I think this creates a history like
>
> ---E---B1--B2--B3--B4--B5 (base)
>         \   \   \   \   \
>          D1  D2  D3  D4  D5 (derived)
>
> So I think the following test would pass even if you drop the
> --fork-point. Did you mean to create a fan-shaped history by resetting
> base to $E on every iteration above?

Just showing that I didn't think things deeply ;-)  I do agree that a
fan-shaped history would show what we want to do a lot better.

Thanks.

>> +                       git merge-base --fork-point base $(cat derived$count) >actual &&
>> +                       test_cmp expect$count actual || exit 1

Re: [PATCH v3 2/2] merge-base: teach "--fork-point" mode

[John Keeping]

On Fri, Oct 25, 2013 at 02:38:08PM -0700, Junio C Hamano wrote:
>  It also comes with a documentation update. The option is not called
>  --reflog but --fork-point; naming a feature after what it does
>  (i.e. it finds the fork point) is a lot more sensible than naming
>  it after how it happens to do what it does (i.e. it does so by
>  peeking into the reflog).

I think the new name is likely to confuse normal users - when talking
about a branch, you can talk about where it forked from and in that case
it normally means the merge-base of that branch and master.

The --reflog name has the advantage that it makes clear that this is
looking at something more than the commit graph and I don't think
--fork-point does imply that.

Re: [PATCH v3 2/2] merge-base: teach "--fork-point" mode

[Junio C Hamano]

John Keeping <john@keeping.me.uk> writes:

> The --reflog name has the advantage that it makes clear that this is
> looking at something more than the commit graph and I don't think
> --fork-point does imply that.

I think I understand what you are saying, but that "more than the
commit graph" part in your reasoning is exactly one of the two
reasons why I do not think that it is a good idea to call it with
"reflog" in its name.  The next round of update to the feature may
find a better way to find the fork point than looking at the reflog.
What the feature is meant to do, i.e. "find the fork point" can stay
the same (i.e. people can use it in their script), while the way how
the implementation achieves it (i.e. by looking at reflog) can
evolve over time, and by not hardcoding "how" in the name, the users
will benefit from the updated behaviour, without having to ask for a
better heuristics by using a different option by updating all of
their scripts.

The other reason (of my two reasons) is because I do not think
"finding the fork-point" will stay to be the _only_ feature that
uses reflog in merge-base. When a next cool feature to compute
something completely different from fork-point happens to be
implemented by taking advantage of reflog data, what would we call
it?

Re: [PATCH v3 2/2] merge-base: teach "--fork-point" mode

[John Keeping]

On Mon, Oct 28, 2013 at 12:13:22PM -0700, Junio C Hamano wrote:
> John Keeping <john@keeping.me.uk> writes:
> 
> > The --reflog name has the advantage that it makes clear that this is
> > looking at something more than the commit graph and I don't think
> > --fork-point does imply that.
> 
> I think I understand what you are saying, but that "more than the
> commit graph" part in your reasoning is exactly one of the two
> reasons why I do not think that it is a good idea to call it with
> "reflog" in its name.  The next round of update to the feature may
> find a better way to find the fork point than looking at the reflog.
> What the feature is meant to do, i.e. "find the fork point" can stay
> the same (i.e. people can use it in their script), while the way how
> the implementation achieves it (i.e. by looking at reflog) can
> evolve over time, and by not hardcoding "how" in the name, the users
> will benefit from the updated behaviour, without having to ask for a
> better heuristics by using a different option by updating all of
> their scripts.

OK - given this reasoning I agree that --fork-point makes sense.

I think this would have been clearer if the short description said
something like:

    Find the point at which a branch forked from another branch; this
    does not just look for the common ancestor of the two commits but
    also takes into account the reflog of <ref> to see if the branch
    forked from an earlier incarnation.

Re: [PATCH v3 2/2] merge-base: teach "--fork-point" mode

[Junio C Hamano]

John Keeping <john@keeping.me.uk> writes:

> OK - given this reasoning I agree that --fork-point makes sense.
>
> I think this would have been clearer if the short description said
> something like:
>
>     Find the point at which a branch forked from another branch; this
>     does not just look for the common ancestor of the two commits but
>     also takes into account the reflog of <ref> to see if the branch
>     forked from an earlier incarnation.

That's much easier to read. Will squash the following in (I do want
to make sure that it is clear that <commit> does not have to be at
the tip, and also <ref> does not have to be a branch---it could be
any ref).

Thanks.

 --fork-point::
-	Given a commit that is derived from possibly an earlier
-	incarnation of a ref, find an appropriate fork-point of the
-	derived history to rebase it on top of an updated base
-	history (see discussion on this mode below).
+	Find the point at which a branch (or any history that leads
+	to <commit>) forked from another branch (or any reference)
+	<ref>. This does not just look for the common ancestor of
+	the two commits, but also takes into account the reflog of
+	<ref> to see if the history leading to <commit> forked from
+	an earlier incarnation of the branch <ref> (see discussion
+	on this mode below).
 
 OPTIONS
 -------

Re: [PATCH 0/2] finding the fork point from reflog entries

[John Keeping]

On Thu, Oct 24, 2013 at 12:11:22PM -0700, Junio C Hamano wrote:
> The first one is a clean-up of the code to parse command line
> options to "git merge-base".  Options such as "--independent",
> "--is-ancestor" and "--octopus" are mutually exclusive and it is
> better expressed in terms of the recently introduced OPT_CMDMODE.
> 
> The second one implements the entire logic of the for loop we see in
> "git pull --rebase" directly using get_merge_bases_many() and
> postprocessing the result.

Nice!  I tried this in the case where the target commit happens to be
the 63rd reflog entry:

$ time sh -c 'for rev in $(git rev-list -g origin/master 2>/dev/null)
do
    git merge-base --is-ancestor $rev b2edae0 && break
done
'

real    0m3.772s
user    0m3.338s
sys     0m0.440s

$ time git merge-base --reflog origin/master b2edae0

real    0m0.156s
user    0m0.138s
sys     0m0.018s


> Junio C Hamano (2):
>   merge-base: use OPT_CMDMODE and clarify the command line parsing
>   merge-base: "--reflog" mode finds fork point from reflog entries
> 
>  builtin/merge-base.c  | 115 +++++++++++++++++++++++++++++++++++++++++++-------
>  t/t6010-merge-base.sh |  27 ++++++++++++
>  2 files changed, 126 insertions(+), 16 deletions(-)

Should there be a change to Documentation/git-merge-base.txt in here?

Re: [PATCH 0/2] finding the fork point from reflog entries

[Junio C Hamano]

John Keeping <john@keeping.me.uk> writes:

> On Thu, Oct 24, 2013 at 12:11:22PM -0700, Junio C Hamano wrote:
>> The first one is a clean-up of the code to parse command line
>> options to "git merge-base".  Options such as "--independent",
>> "--is-ancestor" and "--octopus" are mutually exclusive and it is
>> better expressed in terms of the recently introduced OPT_CMDMODE.
>> 
>> The second one implements the entire logic of the for loop we see in
>> "git pull --rebase" directly using get_merge_bases_many() and
>> postprocessing the result.
>
> Nice!  I tried this in the case where the target commit happens to be
> the 63rd reflog entry:
>
> $ time sh -c 'for rev in $(git rev-list -g origin/master 2>/dev/null)
> do
>     git merge-base --is-ancestor $rev b2edae0 && break
> done
> '
>
> real    0m3.772s
> user    0m3.338s
> sys     0m0.440s
>
> $ time git merge-base --reflog origin/master b2edae0
>
> real    0m0.156s
> user    0m0.138s
> sys     0m0.018s

The real question is if the C code computes the same as the shell
loop.

Re: [PATCH 0/2] finding the fork point from reflog entries

[John Keeping]

On Thu, Oct 24, 2013 at 02:20:29PM -0700, Junio C Hamano wrote:
> John Keeping <john@keeping.me.uk> writes:
> 
> > On Thu, Oct 24, 2013 at 12:11:22PM -0700, Junio C Hamano wrote:
> >> The first one is a clean-up of the code to parse command line
> >> options to "git merge-base".  Options such as "--independent",
> >> "--is-ancestor" and "--octopus" are mutually exclusive and it is
> >> better expressed in terms of the recently introduced OPT_CMDMODE.
> >> 
> >> The second one implements the entire logic of the for loop we see in
> >> "git pull --rebase" directly using get_merge_bases_many() and
> >> postprocessing the result.
> >
> > Nice!  I tried this in the case where the target commit happens to be
> > the 63rd reflog entry:
> >
> > $ time sh -c 'for rev in $(git rev-list -g origin/master 2>/dev/null)
> > do
> >     git merge-base --is-ancestor $rev b2edae0 && break
> > done
> > '
> >
> > real    0m3.772s
> > user    0m3.338s
> > sys     0m0.440s
> >
> > $ time git merge-base --reflog origin/master b2edae0
> >
> > real    0m0.156s
> > user    0m0.138s
> > sys     0m0.018s
> 
> The real question is if the C code computes the same as the shell
> loop.

And in fact it doesn't - if you replace the "break" with "echo $rev" the
shell version prints b2edae0... but the C version prints nothing (and
exists with status 1).

Re: [PATCH 0/2] finding the fork point from reflog entries

[John Keeping]

On Thu, Oct 24, 2013 at 10:31:35PM +0100, John Keeping wrote:
> On Thu, Oct 24, 2013 at 02:20:29PM -0700, Junio C Hamano wrote:
> > John Keeping <john@keeping.me.uk> writes:
> > 
> > > On Thu, Oct 24, 2013 at 12:11:22PM -0700, Junio C Hamano wrote:
> > >> The first one is a clean-up of the code to parse command line
> > >> options to "git merge-base".  Options such as "--independent",
> > >> "--is-ancestor" and "--octopus" are mutually exclusive and it is
> > >> better expressed in terms of the recently introduced OPT_CMDMODE.
> > >> 
> > >> The second one implements the entire logic of the for loop we see in
> > >> "git pull --rebase" directly using get_merge_bases_many() and
> > >> postprocessing the result.
> > >
> > > Nice!  I tried this in the case where the target commit happens to be
> > > the 63rd reflog entry:
> > >
> > > $ time sh -c 'for rev in $(git rev-list -g origin/master 2>/dev/null)
> > > do
> > >     git merge-base --is-ancestor $rev b2edae0 && break
> > > done
> > > '
> > >
> > > real    0m3.772s
> > > user    0m3.338s
> > > sys     0m0.440s
> > >
> > > $ time git merge-base --reflog origin/master b2edae0
> > >
> > > real    0m0.156s
> > > user    0m0.138s
> > > sys     0m0.018s
> > 
> > The real question is if the C code computes the same as the shell
> > loop.
> 
> And in fact it doesn't - if you replace the "break" with "echo $rev" the
> shell version prints b2edae0... but the C version prints nothing (and
> exists with status 1).

To clarify: the particular commit in the calls above happens to be the
oldest entry in the reflog, if I pick a newer entry then it works.

It seems that for_each_reflog_ent isn't returning the oldest entry;
revs.nr is 62 whereas "git rev-list -g origin/master | wc -l" gives 63.

Re: [PATCH 0/2] finding the fork point from reflog entries

[John Keeping]

On Thu, Oct 24, 2013 at 10:40:07PM +0100, John Keeping wrote:
> On Thu, Oct 24, 2013 at 10:31:35PM +0100, John Keeping wrote:
> > On Thu, Oct 24, 2013 at 02:20:29PM -0700, Junio C Hamano wrote:
> > > John Keeping <john@keeping.me.uk> writes:
> > > 
> > > > On Thu, Oct 24, 2013 at 12:11:22PM -0700, Junio C Hamano wrote:
> > > >> The first one is a clean-up of the code to parse command line
> > > >> options to "git merge-base".  Options such as "--independent",
> > > >> "--is-ancestor" and "--octopus" are mutually exclusive and it is
> > > >> better expressed in terms of the recently introduced OPT_CMDMODE.
> > > >> 
> > > >> The second one implements the entire logic of the for loop we see in
> > > >> "git pull --rebase" directly using get_merge_bases_many() and
> > > >> postprocessing the result.
> > > >
> > > > Nice!  I tried this in the case where the target commit happens to be
> > > > the 63rd reflog entry:
> > > >
> > > > $ time sh -c 'for rev in $(git rev-list -g origin/master 2>/dev/null)
> > > > do
> > > >     git merge-base --is-ancestor $rev b2edae0 && break
> > > > done
> > > > '
> > > >
> > > > real    0m3.772s
> > > > user    0m3.338s
> > > > sys     0m0.440s
> > > >
> > > > $ time git merge-base --reflog origin/master b2edae0
> > > >
> > > > real    0m0.156s
> > > > user    0m0.138s
> > > > sys     0m0.018s
> > > 
> > > The real question is if the C code computes the same as the shell
> > > loop.
> > 
> > And in fact it doesn't - if you replace the "break" with "echo $rev" the
> > shell version prints b2edae0... but the C version prints nothing (and
> > exists with status 1).
> 
> To clarify: the particular commit in the calls above happens to be the
> oldest entry in the reflog, if I pick a newer entry then it works.
> 
> It seems that for_each_reflog_ent isn't returning the oldest entry;
> revs.nr is 62 whereas "git rev-list -g origin/master | wc -l" gives 63.

The following patch on top fixes it, but I'm sure it can be done in a
neater way.

-- >8 --
diff --git a/builtin/merge-base.c b/builtin/merge-base.c
index 7b9bc15..f6f1f14 100644
--- a/builtin/merge-base.c
+++ b/builtin/merge-base.c
@@ -98,7 +98,17 @@ static int collect_one_reflog_ent(unsigned char *osha1, unsigned char *nsha1,
 				  int tz, const char *message, void *cbdata_)
 {
 	struct rev_collect *revs = cbdata_;
-	struct commit *commit = lookup_commit(nsha1);
+	struct commit *commit;
+
+	if (!revs->nr) {
+		commit = lookup_commit(osha1);
+		if (commit) {
+			ALLOC_GROW(revs->commit, revs->nr + 1, revs->alloc);
+			revs->commit[revs->nr++] = commit;
+		}
+	}
+
+	commit = lookup_commit(nsha1);
 	if (commit) {
 		ALLOC_GROW(revs->commit, revs->nr + 1, revs->alloc);
 		revs->commit[revs->nr++] = commit;

Re: [PATCH 0/2] finding the fork point from reflog entries

[Junio C Hamano]

John Keeping <john@keeping.me.uk> writes:

> To clarify: the particular commit in the calls above happens to be the
> oldest entry in the reflog, if I pick a newer entry then it works.
>
> It seems that for_each_reflog_ent isn't returning the oldest entry;
> revs.nr is 62 whereas "git rev-list -g origin/master | wc -l" gives 63.

Perhaps this on top.

One thing I somehow feel dirty about this change is that we have to
include diff.h only to include revision.h only to get the definition
of TMP_MARK. Perhaps object.h should be the header that defines the
bit assignment for objects.flags bit-field.

 builtin/merge-base.c | 28 ++++++++++++++++++++++++----
 1 file changed, 24 insertions(+), 4 deletions(-)

diff --git a/builtin/merge-base.c b/builtin/merge-base.c
index 7b9bc15..7fdc3de 100644
--- a/builtin/merge-base.c
+++ b/builtin/merge-base.c
@@ -2,6 +2,8 @@
 #include "cache.h"
 #include "commit.h"
 #include "refs.h"
+#include "diff.h"
+#include "revision.h"
 #include "parse-options.h"
 
 static int show_merge_base(struct commit **rev, int rev_nr, int show_all)
@@ -91,18 +93,32 @@ struct rev_collect {
 	struct commit **commit;
 	int nr;
 	int alloc;
+	unsigned int initial : 1;
 };
 
+static void add_one_commit(unsigned char *sha1, struct rev_collect *revs)
+{
+	struct commit *commit = lookup_commit(sha1);
+
+	if (!commit || (commit->object.flags & TMP_MARK))
+		return;
+
+	ALLOC_GROW(revs->commit, revs->nr + 1, revs->alloc);
+	revs->commit[revs->nr++] = commit;
+	commit->object.flags |= TMP_MARK;
+}
+
 static int collect_one_reflog_ent(unsigned char *osha1, unsigned char *nsha1,
 				  const char *ident, unsigned long timestamp,
 				  int tz, const char *message, void *cbdata_)
 {
 	struct rev_collect *revs = cbdata_;
-	struct commit *commit = lookup_commit(nsha1);
-	if (commit) {
-		ALLOC_GROW(revs->commit, revs->nr + 1, revs->alloc);
-		revs->commit[revs->nr++] = commit;
+
+	if (revs->initial) {
+		add_one_commit(osha1, revs);
+		revs->initial = 0;
 	}
+	add_one_commit(nsha1, revs);
 	return 0;
 }
 
@@ -131,8 +147,12 @@ static int handle_reflog(int argc, const char **argv)
 
 	derived = lookup_commit_reference(sha1);
 	memset(&revs, 0, sizeof(revs));
+	revs.initial = 1;
 	for_each_reflog_ent(refname, collect_one_reflog_ent, &revs);
 
+	for (i = 0; i < revs.nr; i++)
+		revs.commit[i]->object.flags &= ~TMP_MARK;
+
 	bases = get_merge_bases_many(derived, revs.nr, revs.commit, 0);
 
 	/*

Re: [PATCH] rebase: use reflog to find common base with upstream

[Martin von Zweigbergk]

On Wed, Oct 16, 2013 at 11:53 AM, John Keeping <john@keeping.me.uk> wrote:
> Commit 15a147e (rebase: use @{upstream} if no upstream specified,
> 2011-02-09) says:
>
>         Make it default to 'git rebase @{upstream}'. That is also what
>         'git pull [--rebase]' defaults to, so it only makes sense that
>         'git rebase' defaults to the same thing.
>
> but that isn't actually the case.  Since commit d44e712 (pull: support
> rebased upstream + fetch + pull --rebase, 2009-07-19), pull has actually
> chosen the most recent reflog entry which is an ancestor of the current
> branch if it can find one.
>
> Change rebase so that it uses the same logic.
>
> Signed-off-by: John Keeping <john@keeping.me.uk>
> ---
>  git-rebase.sh     | 8 ++++++++
>  t/t3400-rebase.sh | 6 ++++--
>  2 files changed, 12 insertions(+), 2 deletions(-)
>
> diff --git a/git-rebase.sh b/git-rebase.sh
> index 226752f..fd36cf7 100755
> --- a/git-rebase.sh
> +++ b/git-rebase.sh
> @@ -437,6 +437,14 @@ then
>                         error_on_missing_default_upstream "rebase" "rebase" \
>                                 "against" "git rebase <branch>"
>                 fi
> +               for reflog in $(git rev-list -g "$upstream_name" 2>/dev/null)
> +               do
> +                       if test "$reflog" = "$(git merge-base "$reflog" HEAD)"
> +                       then
> +                               upstream_name=$reflog
> +                               break
> +                       fi
> +               done
>                 ;;
>         *)      upstream_name="$1"
>                 shift

A little later, "onto_name" gets assigned like so:

  onto_name=${onto-"$upstream_name"}

So if upstream_name was set above, then onto would get the same value,
which is not what we want, right? It seems like this block of code
should come a bit later.

I also think it not be run only when rebase was run without a given
upstream. If the configured upstream is "origin/master", it seems like
it would be surprising to get different behavior from "git rebase" and
"git rebase origin/master".

Re: [PATCH] rebase: use reflog to find common base with upstream

[John Keeping]

On Mon, Oct 21, 2013 at 10:40:22PM -0700, Martin von Zweigbergk wrote:
> On Wed, Oct 16, 2013 at 11:53 AM, John Keeping <john@keeping.me.uk> wrote:
> > Commit 15a147e (rebase: use @{upstream} if no upstream specified,
> > 2011-02-09) says:
> >
> >         Make it default to 'git rebase @{upstream}'. That is also what
> >         'git pull [--rebase]' defaults to, so it only makes sense that
> >         'git rebase' defaults to the same thing.
> >
> > but that isn't actually the case.  Since commit d44e712 (pull: support
> > rebased upstream + fetch + pull --rebase, 2009-07-19), pull has actually
> > chosen the most recent reflog entry which is an ancestor of the current
> > branch if it can find one.
> >
> > Change rebase so that it uses the same logic.
> >
> > Signed-off-by: John Keeping <john@keeping.me.uk>
> > ---
> >  git-rebase.sh     | 8 ++++++++
> >  t/t3400-rebase.sh | 6 ++++--
> >  2 files changed, 12 insertions(+), 2 deletions(-)
> >
> > diff --git a/git-rebase.sh b/git-rebase.sh
> > index 226752f..fd36cf7 100755
> > --- a/git-rebase.sh
> > +++ b/git-rebase.sh
> > @@ -437,6 +437,14 @@ then
> >                         error_on_missing_default_upstream "rebase" "rebase" \
> >                                 "against" "git rebase <branch>"
> >                 fi
> > +               for reflog in $(git rev-list -g "$upstream_name" 2>/dev/null)
> > +               do
> > +                       if test "$reflog" = "$(git merge-base "$reflog" HEAD)"
> > +                       then
> > +                               upstream_name=$reflog
> > +                               break
> > +                       fi
> > +               done
> >                 ;;
> >         *)      upstream_name="$1"
> >                 shift
> 
> A little later, "onto_name" gets assigned like so:
> 
>   onto_name=${onto-"$upstream_name"}
> 
> So if upstream_name was set above, then onto would get the same value,
> which is not what we want, right? It seems like this block of code
> should come a bit later.
> 
> I also think it not be run only when rebase was run without a given
> upstream. If the configured upstream is "origin/master", it seems like
> it would be surprising to get different behavior from "git rebase" and
> "git rebase origin/master".

Hmm... I think you're right.  I originally didn't want to change the
behaviour when the user specifies a branch, but in this case we want to
look for a common ancestor in the reflog of the upstream regardless of
where the ref came from.