[PATCH/RFC] Add a --bouquet option to git rev-list

[PATCH/RFC] Add a --bouquet option to git rev-list

[Nathan W. Panike]

Add a command line option to rev-list so the command 'git rev-list --bouquet'
shows all revisions that are ancestors of refs which share history with HEAD.

Signed-off-by: Nathan W. Panike <nathan.panike@gmail.com>
---
I have a repository with the following structure:

      B
     /
A'--A--C
     \
      D

E'--E

Thus the command 'git merge base E A' returns nothing, as there is no common
history.  The E history contains stuff that is derived from the other history
(A, B, C, or D).  Often I find myself doing the following:

git checkout C
gitk $(include_forks) &
<View history, make changes, merges, et cetera>
git checkout E
<go back to gitk, only see history for B, C, etc>

Now the 'include_forks' command is a bash function in my .bashrc:

include_forks () 
{ 
    local head="$(git show -s --pretty=format:'%H' HEAD)";
    echo "HEAD $(git for-each-ref --format='%(refname)' \
	refs/heads refs/remotes | while read ref; do \
	if test "$(git merge-base HEAD ${ref}^{commit})" != ""; \
		then echo ${ref}; fi; done)"
}

The shell thus intercepts my command and I must restart gitk to see the history
of E. 

With this patch, I can issue the command 'gitk --bouquet' and when I checkout
E, I can 'reload' in gitk and see the history of E automatically.

If there is an easier way to do this in git, please let me know.  Otherwise,
please let me know how to improve this patch.

 revision.c |   38 ++++++++++++++++++++++++++++++++++++++
 1 files changed, 38 insertions(+), 0 deletions(-)

diff --git a/revision.c b/revision.c
index a8a3c3a..ba367cc 100644
--- a/revision.c
+++ b/revision.c
@@ -699,6 +699,31 @@ static int handle_one_ref(const char *path, const unsigned char *sha1, int flag,
 	return 0;
 }
 
+static int handle_one_connected_ref(const char *path, const unsigned char *sha1, int flag, void *cb_data)
+{
+	struct all_refs_cb *cb = cb_data;
+	struct object *object = get_reference(cb->all_revs, path, sha1,
+					      cb->all_flags);
+	struct commit *r;
+	static int got_head = 1;
+	static struct commit *head_commit;
+	static int head_nr = 0;
+	if(got_head) {
+		got_head=head_ref(handle_one_ref,cb);
+		if(got_head)
+			return 1;
+		if(cb && cb->all_revs && cb->all_revs->pending.nr > 0) {
+			head_nr = cb->all_revs->pending.nr - 1;
+			head_commit = (struct commit*)&cb->all_revs->pending.objects->item[head_nr];
+		}
+	}
+	r = lookup_commit_reference_gently(sha1,1);
+	if(r != NULL && head_commit)
+		if(get_merge_bases_many(head_commit,1,&r,1)) 
+			add_pending_object(cb->all_revs, object, path);
+	return 0;
+}
+
 static void handle_refs(struct rev_info *revs, unsigned flags,
 		int (*for_each)(each_ref_fn, void *))
 {
@@ -708,6 +733,15 @@ static void handle_refs(struct rev_info *revs, unsigned flags,
 	for_each(handle_one_ref, &cb);
 }
 
+static void handle_connected_refs(struct rev_info *revs, unsigned flags,
+		int (*for_each)(each_ref_fn, void *))
+{
+	struct all_refs_cb cb;
+	cb.all_revs = revs;
+	cb.all_flags = flags;
+	for_each(handle_one_connected_ref, &cb);
+}
+
 static void handle_one_reflog_commit(unsigned char *sha1, void *cb_data)
 {
 	struct all_refs_cb *cb = cb_data;
@@ -1352,6 +1386,10 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch
 				handle_refs(revs, flags, for_each_remote_ref);
 				continue;
 			}
+			if (!strcmp(arg, "--bouquet")) {
+				handle_connected_refs(revs, flags, for_each_ref);
+				continue;
+			}
 			if (!strcmp(arg, "--reflog")) {
 				handle_reflog(revs, flags);
 				continue;
-- 
1.6.5.3

Re: [PATCH/RFC] Add a --bouquet option to git rev-list

[Michael J Gruber]

Nathan W. Panike venit, vidit, dixit 30.11.2009 21:55:
> Add a command line option to rev-list so the command 'git rev-list --bouquet'
> shows all revisions that are ancestors of refs which share history with HEAD.
> 
> Signed-off-by: Nathan W. Panike <nathan.panike@gmail.com>
> ---
> I have a repository with the following structure:
> 
>       B
>      /
> A'--A--C
>      \
>       D
> 
> E'--E
> 
> Thus the command 'git merge base E A' returns nothing, as there is no common
> history.  The E history contains stuff that is derived from the other history
> (A, B, C, or D).  Often I find myself doing the following:

Either I don't understand the diagram or your term "derived". If
"derived" means "on some branch of a merge" and E is derived from A, B,
C, or D, then (since B, C, D is derived from A, and from A') E is
derived from A', and they will have a merge base.

Are these diagrams really disconnected from each other?

> git checkout C
> gitk $(include_forks) &
> <View history, make changes, merges, et cetera>
> git checkout E
> <go back to gitk, only see history for B, C, etc>
> 
> Now the 'include_forks' command is a bash function in my .bashrc:
> 
> include_forks () 
> { 
>     local head="$(git show -s --pretty=format:'%H' HEAD)";
>     echo "HEAD $(git for-each-ref --format='%(refname)' \
> 	refs/heads refs/remotes | while read ref; do \
> 	if test "$(git merge-base HEAD ${ref}^{commit})" != ""; \
> 		then echo ${ref}; fi; done)"
> }
> 
> The shell thus intercepts my command and I must restart gitk to see the history
> of E. 
> 
> With this patch, I can issue the command 'gitk --bouquet' and when I checkout
> E, I can 'reload' in gitk and see the history of E automatically.

What would your patch do in the example you gave above? Which refs would
it cause gitk (rev-list) to show?

Michael

Re: [PATCH/RFC] Add a --bouquet option to git rev-list

[Nathan W. Panike]

Hello,

On Tue, Dec 1, 2009 at 2:09 AM, Michael J Gruber
<git@drmicha.warpmail.net> wrote:
> Nathan W. Panike venit, vidit, dixit 30.11.2009 21:55:
>> Add a command line option to rev-list so the command 'git rev-list --bouquet'
>> shows all revisions that are ancestors of refs which share history with HEAD.
>>
>> Signed-off-by: Nathan W. Panike <nathan.panike@gmail.com>
>> ---
>> I have a repository with the following structure:
>>
>>       B
>>      /
>> A'--A--C
>>      \
>>       D
>>
>> E'--E
>>
>> Thus the command 'git merge base E A' returns nothing, as there is no common
>> history.  The E history contains stuff that is derived from the other history
>> (A, B, C, or D).  Often I find myself doing the following:
>
> Either I don't understand the diagram or your term "derived". If
> "derived" means "on some branch of a merge" and E is derived from A, B,
> C, or D, then (since B, C, D is derived from A, and from A') E is
> derived from A', and they will have a merge base.
>

"Derived" in my case means that E is processed from a snapshot of the
tree at, say, A.

> Are these diagrams really disconnected from each other?

Yes.  I started the history of E with plumbing using git commit-tree,
without a -p flag specifying a parent

>
>> git checkout C
>> gitk $(include_forks) &
>> <View history, make changes, merges, et cetera>
>> git checkout E
>> <go back to gitk, only see history for B, C, etc>
>>
>> Now the 'include_forks' command is a bash function in my .bashrc:
>>
>> include_forks ()
>> {
>>     local head="$(git show -s --pretty=format:'%H' HEAD)";
>>     echo "HEAD $(git for-each-ref --format='%(refname)' \
>>       refs/heads refs/remotes | while read ref; do \
>>       if test "$(git merge-base HEAD ${ref}^{commit})" != ""; \
>>               then echo ${ref}; fi; done)"
>> }
>>
>> The shell thus intercepts my command and I must restart gitk to see the history
>> of E.
>>
>> With this patch, I can issue the command 'gitk --bouquet' and when I checkout
>> E, I can 'reload' in gitk and see the history of E automatically.
>
> What would your patch do in the example you gave above? Which refs would
> it cause gitk (rev-list) to show?
>

I wish to be concrete, so let us suppose you use a default clone of
git.git.  Further, suppose you are on origin/master.
Then, with my patch,

git rev-list --bouquet

should be an---admittedly less efficient---equivalent to

git rev-list --all --not refs/remotes/origin/html
refs/remotes/origin/man refs/remotes/origin/todo

> Michael
>

Thanks,

Nathan Panike

Re: [PATCH/RFC] Add a --bouquet option to git rev-list

[Junio C Hamano]

"Nathan W. Panike" <nathan.panike@gmail.com> writes:

>>> include_forks ()
>>> {
>>>     local head="$(git show -s --pretty=format:'%H' HEAD)";
>>>     echo "HEAD $(git for-each-ref --format='%(refname)' \
>>>       refs/heads refs/remotes | while read ref; do \
>>>       if test "$(git merge-base HEAD ${ref}^{commit})" != ""; \
>>>               then echo ${ref}; fi; done)"
>>> }

Because you have to traverse the entire history from tips of refs to know
if the histories to reach them are disjoint, this is fundamentally a very
expensive operation and will not scale to projects with deep histories.

If a low-level support for this kind of thing is necessary, then I do not
think it should just be "give me set of refs that is related to HEAD".  I
suspect that is too inflexible to be useful in other situations.

A command to list refs (i.e. not as rev-list argument that shows list of
commits, but as a new feature of for-each-ref) with new criteria might
have wider use (I am just thinking aloud).  Something like

 - among these refs (you would specify this with --all, --heads, or prefix
   'refs/heads refs/remotes'), list only the ones related to this and that
   ref (here you would give HEAD or whatever you want to check with as
   argument)"; and 

 - its counterpart "list the ones that are _not_ related" with the same
   input.

As to the implementation, instead of running get_merge_bases() number of
times (a naive implementation would be O(n*m), I guess), I think it may
make sense to run the traversal in parallel, similar to the way done in
show-branches (but the termination condition would be different).