git-rev-list feature request

git-rev-list feature request

[Paul Mackerras]

Hi,

I'd like to implement a new features in gitk to enable it to show the
relationship of a given commit to the tags and other references.  What
I would like is for git-rev-list to be able to output a dense graph
containing only one or more specified commits plus all the commits
that have a reference (i.e. a file under $GIT_DIR/refs that contains
their SHA1 ID), plus the merges that are needed to complete the
graph.

It would be nice also to be able to combine that with the existing
ability to output a dense graph containing the commits that modify a
specified set of files or directories.

In other words, I would like to be able to select any combination of
(a) some explicitly specified commits
(b) commits that have a reference
(c) commits that affect specified files or directories

and have git-rev-list output a graph that shows the relationship of
those commits.

Possible?

Thanks,
Paul.

Re: git-rev-list feature request

[Linus Torvalds]

On Fri, 10 Mar 2006, Paul Mackerras wrote:
> 
> It would be nice also to be able to combine that with the existing
> ability to output a dense graph containing the commits that modify a
> specified set of files or directories.
> 
> In other words, I would like to be able to select any combination of
> (a) some explicitly specified commits
> (b) commits that have a reference
> (c) commits that affect specified files or directories
> 
> and have git-rev-list output a graph that shows the relationship of
> those commits.
> 
> Possible?

Yeah. I _think_ what you want is

 - phase 1: generate the current graph that we already do for

	git-rev-list --all ^cmit

 - phase 2: start at "cmit", and mark everything that refers to it as 
   "show me" (including "cmit" itself, which was originally marked 
   uninteresting)

So phase 1 already exists and was the hard part. phase 2 is just walking 
the graph (that is now all in memory) from "cmit" using the "object->refs" 
reverse references that got built up during phase 1.

The only question is how to show the ref-names, or, more properly, what to 
do when we have a ref-name, but the commit it points to wasn't interesting 
because it didn't change the set of files we used to determine interest...

And where to find the sucker^H^H^H^H^H^Hhelpful soul to actually do the 
work.

		Linus

Re: git-rev-list feature request

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> So phase 1 already exists and was the hard part. phase 2 is just walking 
> the graph (that is now all in memory) from "cmit" using the "object->refs" 
> reverse references that got built up during phase 1.

Eh,... what reverse references???

Re: git-rev-list feature request

[Linus Torvalds]

On Thu, 9 Mar 2006, Junio C Hamano wrote:

> Linus Torvalds <torvalds@osdl.org> writes:
> 
> > So phase 1 already exists and was the hard part. phase 2 is just walking 
> > the graph (that is now all in memory) from "cmit" using the "object->refs" 
> > reverse references that got built up during phase 1.
> 
> Eh,... what reverse references???

Heh. Exercise left to the reader. Right now we do only forward references 
(and rev-list.c actually turns that off, since it has no use for them). 

But doing reverse refs should be easy - in the same place we do the 
forward ones. I'd suggest making "track_object_refs == -1" mean "reverse 
refs".

(I think the only thing that uses forwards refs is fsck. Nobody else wants 
them, or would prefer the reverse kind - since forwards refs you can 
just look up yourself anyway).

		Linus

Re: git-rev-list feature request

[Paul Mackerras]

Linus Torvalds writes:

> Yeah. I _think_ what you want is
> 
>  - phase 1: generate the current graph that we already do for
> 
> 	git-rev-list --all ^cmit
> 
>  - phase 2: start at "cmit", and mark everything that refers to it as 
>    "show me" (including "cmit" itself, which was originally marked 
>    uninteresting)

I'm not sure if that's what I want.  Is that how "git-rev-list -- foo" 
works?

What I want is basically just what "git-rev-list -- foo" does, but
with some extra flexibility in choosing what commits are interesting -
that is, to be able to say that a commit is interesting if it affects
some file, has a reference under .git/refs, or if it is one of a set
of specified commits.

Paul.

Re: git-rev-list feature request

[Linus Torvalds]

On Fri, 10 Mar 2006, Paul Mackerras wrote:

> Linus Torvalds writes:
> 
> > Yeah. I _think_ what you want is
> > 
> >  - phase 1: generate the current graph that we already do for
> > 
> > 	git-rev-list --all ^cmit
> > 
> >  - phase 2: start at "cmit", and mark everything that refers to it as 
> >    "show me" (including "cmit" itself, which was originally marked 
> >    uninteresting)
> 
> I'm not sure if that's what I want.  Is that how "git-rev-list -- foo" 
> works?

Nope. "git-rev-list -- foo" will just start from the heads given, and walk 
down. 

> What I want is basically just what "git-rev-list -- foo" does, but
> with some extra flexibility in choosing what commits are interesting -
> that is, to be able to say that a commit is interesting if it affects
> some file, has a reference under .git/refs, or if it is one of a set
> of specified commits.

Ahh, ok, you actually wanted something simpler than I thought you might.

What you want is (in its most trivial form) really trivial: mark the 
special commits you want to save with TREECHANGE, so that they aren't 
pruned by the logic that prunes off the "this commit doesn't change the 
file, so ignore it" commits.

HOWEVER. That trivial thing has problems. What if the history got 
simplified at a merge because one side of the merge changed it, and the 
other one did not - in that case we'll follow the history down the leg 
that didn't change (since that's the history that ended up being the final 
one). Now, that means that we will totally prune out the other parent 
info, and the commits you want to remain simply won't be "connected" any 
more.

To explain that better, let's say that history looks like this:

	     a
	    / \
	   b   c
	   |   |
	   d   e
	    \ /
	     f

and you're following file "foo", which is the same in "a" and "c". The 
fact that they are the same there means that the name pruning will decide 
that the history that led to "a" through "b" wasn't interesting, so it 
will prune that out, and make the whole history be

	   a
	   |
	   c
	   |
	   e
	   |
	   f

and then after that, it will remove all commits that didn't actually 
change foo at all (we know "a" was such a commit since we already 
simplified the merge, but let's say that "e" was one too), so you get

	   c
	   |
	   f

as the final simplified history right now.

Now, the problem is that what should you do if you want to tag "d" and "e" 
as inherently interesting (perhaps because they are tagged releases)?

Now, the "e" case is the above trivial case: just mark any "inherently 
interesting" commit with the TREECHANGE flag, and the history won't be 
pruned away. So it now looks like

	   c
	   |
	   e    <- faked "interesting"
	   |
	   f

however, the fact that you did the same to "d" means that we will have 
that too on our list of "interesting" commits, even though we've pruned 
away all of the history leading _from_ it, so the trivial algorithm would 
actually result in

	     c
	     |
	 d   e
	  \ /
	   f

in that case. We'd see "d" because it's somehow intrisically interesting, 
but it ends up being shown as that "dead tip", because the merge that 
would reach it was simplified away.

Is that what you'd want?

If so, then the appended trivial path should effectively do what you ask 
for. It keeps all the revs you passed in as "interesting" whether they are 
or not, so now you can effectively just pass in all the refs you want, and 
it will never remove any of the positive refs you passed it.

If you want a commit that has a ref pointing to it be marked as 
interesting only if we see it while parsing the tree, then you need to do 
slightly more (in "rewrite_one()", you should look up whether that commit 
has a ref pointing to it).

		Linus

----
diff --git a/revision.c b/revision.c
index 713f27e..90d3764 100644
--- a/revision.c
+++ b/revision.c
@@ -149,7 +149,8 @@ static struct commit *get_commit_referen
 		if (flags & UNINTERESTING) {
 			mark_parents_uninteresting(commit);
 			revs->limited = 1;
-		}
+		} else
+			object->flags |= TREECHANGE;
 		return commit;
 	}
 

Re: git-rev-list feature request

[Linus Torvalds]

On Thu, 9 Mar 2006, Linus Torvalds wrote:
> 
> Ahh, ok, you actually wanted something simpler than I thought you might.

Btw, what I _thought_ you migth want is to do the current "strong 
pruning", and then look up - from the stuff left behind - which ones reach 
to a ref or a tag. That's where the reverse refs would come in, and it 
requires some fundamental surgery (but it shouldn't be hard at all).

		Linus