Gitk feature - show nearby tags

Gitk feature - show nearby tags

[Paul Mackerras]

I just pushed out an update to the "new" branch of the gitk.git
repository, which adds a feature that I have often wished for: it will
now show the nearest preceding and following tags when you select a
commit.  This is very useful if you need to identify which release was
the first to incorporate a particular patch, or if you need to know
which release a patch might have been based on.

(Specifically, it shows the tags for all tagged descendents that are
not descendents of another tagged descendent of the selected commit,
and the tags for all tagged ancestors that are not ancestors of
another tagged ancestor of the selected commit.)

Since there is a one-off computation that gitk does to work this out,
which takes an appreciable time (about 1.5 seconds on my G5 on the
kernel repository), I have made gitk do the computation in the
background, and update the diff/file display window when it's done.
There is also a checkbox in the preferences window where you can turn
it off if you don't want gitk to do this computation.

Comments/suggestions welcome.

Paul.

Re: Gitk feature - show nearby tags

[Junio C Hamano]

Paul Mackerras <paulus@samba.org> writes:

> I just pushed out an update to the "new" branch of the gitk.git
> repository, which adds a feature that I have often wished for: it will
> now show the nearest preceding and following tags when you select a
> commit.  This is very useful if you need to identify which release was
> the first to incorporate a particular patch, or if you need to know
> which release a patch might have been based on.

Another thing that would equally be useful is to show which
branch a particular commit is on, so for example I can pick one
commit while doing "gitk next" to view the next branch and see
which topic it belongs to, and "gitk this-topic" to see which
commits on that topic, if any, are not yet in the "next" branch.

For a graphical interface like gitk it may not be such a big
deal (you can always follow the line), but an interface like tig
that shows commits in a linear fashion it would make a big
difference in usability.

BTW, what's the maintenance/rewind policy on the "new" branch of
gitk.git?  If you are never going to rewind it, I could pull it
in "next" (and keep pulling your "master" in my "master") for
wider exposure if you like.

Re: Gitk feature - show nearby tags

[Marco Costalba]

On 6/3/06, Junio C Hamano <junkio@cox.net> wrote:
> Paul Mackerras <paulus@samba.org> writes:
>
> > I just pushed out an update to the "new" branch of the gitk.git
> > repository, which adds a feature that I have often wished for: it will
> > now show the nearest preceding and following tags when you select a
> > commit.  This is very useful if you need to identify which release was
> > the first to incorporate a particular patch, or if you need to know
> > which release a patch might have been based on.
>
> Another thing that would equally be useful is to show which
> branch a particular commit is on, so for example I can pick one
> commit while doing "gitk next" to view the next branch and see
> which topic it belongs to, and "gitk this-topic" to see which
> commits on that topic, if any, are not yet in the "next" branch.
>

If I have understood correctly the patch runs a 'git rev-list --all
--topo-order --parents'
and then does a tree walking.

I am wandering if there exist any native git way to found the previous tag.

As example given a selected revision with id <sha> is it possible to
do something like this to fond the ancestor?

1) get the tag list with git-peek-remote or something similar if tags
are not already loaded

2) given the tagList vector with n elements run

    git-rev-list  --topo-order <sha> ^tagList[0]  ^tagList[1]   ....
  ^tagList[n-1]

3) take the last sha spit out by git-rev-list, be it <lastSha>.

4) Previous nearest tag is the parent of lastSha

I've missed something?

      Marco

Re: Gitk feature - show nearby tags

[Paul Mackerras]

Junio C Hamano writes:

> Another thing that would equally be useful is to show which
> branch a particular commit is on, so for example I can pick one
> commit while doing "gitk next" to view the next branch and see
> which topic it belongs to, and "gitk this-topic" to see which
> commits on that topic, if any, are not yet in the "next" branch.

That wouldn't be hard to do, it's just a matter of finding which heads
are descendents of the selected commit.  I think that with heads, you
would want to see all the descendent heads, rather than just the
nearest ones (those that aren't descendents of another descendent
head) as I do with tags.  What do you think?  If one head is a
descendent of another, and both are descendents of the selected
commit, should I show both?

> BTW, what's the maintenance/rewind policy on the "new" branch of
> gitk.git?  If you are never going to rewind it, I could pull it
> in "next" (and keep pulling your "master" in my "master") for
> wider exposure if you like.

I intend to pull "new" into "master" shortly, assuming I don't get any
bug reports for the "new" branch. :)

If you pull my "new" into your "next", and you then pull your "next"
into your "master", and I pull my "new" into my "master", and you pull
my "master" into your "master", won't we end up with duplicate merges?

Paul.

Re: Gitk feature - show nearby tags

[Jonas Fonseca]

Junio C Hamano <junkio@cox.net> wrote Sat, Jun 03, 2006:
> For a graphical interface like gitk it may not be such a big
> deal (you can always follow the line), but an interface like tig
> that shows commits in a linear fashion it would make a big
> difference in usability.

I already took your hint from the other day on irc and have begun on
implementing this revision graph visualization for tig. :)

The problem is of course to come up with some ascii-art which is both
readable and dense. Below is my mockup of something not using line
graphics, however using line graphics it might be possible to get
something more unambiguos but also more "edgy".

	* [release] Sync docs
	M Merge ...
	|`* [master] Fix spelling
	| * Implement ...
	M | Merge ...
	|`M Merge ...
	| |`* Topic B ...
	| | * Topic B ...
	| * | Topic A
	| * | Topic A
	| *' Update docs
	: :
	M | Merge ...
	|`M Merge ...
	| *`. Topic B ...
	| * | Topic B ...
	| | * Topic A
	| | * Topic A
	| *' Update docs
	: :
	M | Merge ...
	|`M Merge ...
	| *`. Topic B ...
	| * | Topic B ...
	| | * Topic A
	M  `.`. Merge
	|`* | | Update docs

-- 
Jonas Fonseca

Re: Gitk feature - show nearby tags

[Jakub Narebski]

Jonas Fonseca wrote:

> I already took your hint from the other day on irc and have begun on
> implementing this revision graph visualization for tig. :)
> 
> The problem is of course to come up with some ascii-art which is both
> readable and dense. Below is my mockup of something not using line
> graphics,[...]

As I can see you use 'vertical' layout. Do I understand correctly that '*'
refers to commit on marked (by column) branch, and '|' means pass-thru?

BTW. you might want to take a look at http://revctrl.org/ diagrams;
AFAICT all the git documentation uses 'horizontal' layout, which is good
for example but perhaps not for long-lived development...

-- 
Jakub Narebski
Warsaw, Poland

Re: Gitk feature - show nearby tags

[Jonas Fonseca]

Jakub Narebski <jnareb@gmail.com> wrote Sat, Jun 03, 2006:
> Jonas Fonseca wrote:
> 
> > I already took your hint from the other day on irc and have begun on
> > implementing this revision graph visualization for tig. :)
> > 
> > The problem is of course to come up with some ascii-art which is both
> > readable and dense. Below is my mockup of something not using line
> > graphics,[...]
> 
> As I can see you use 'vertical' layout. Do I understand correctly that '*'
> refers to commit on marked (by column) branch, and '|' means pass-thru?

Yes, and 'M' marks merges. Putting information in the "commit node"
should make certain things more obvious. You could encode information
such as whether a commit is a "unique head" (nothing other revisions
references this commit). For example the first commit will always be
unique, but when using --all other heads might show up "unique".

	+ [master] ...
	* ...
	| + [unmerged/topic] ...
	| * ...
	*' ...

> BTW. you might want to take a look at http://revctrl.org/ diagrams;
> AFAICT all the git documentation uses 'horizontal' layout, which is good
> for example but perhaps not for long-lived development...

Looking at the examples on http://revctrl.org/StaircaseMerge: it might
be more readable but not as dense as I would like, namely one commit pr
line.

-- 
Jonas Fonseca

Re: Gitk feature - show nearby tags

[Junio C Hamano]

Paul Mackerras <paulus@samba.org> writes:

> ...  I think that with heads, you
> would want to see all the descendent heads, rather than just the
> nearest ones (those that aren't descendents of another descendent
> head) as I do with tags.  What do you think?  If one head is a
> descendent of another, and both are descendents of the selected
> commit, should I show both?

That would be useful I think.

>> BTW, what's the maintenance/rewind policy on the "new" branch of
>> gitk.git?  If you are never going to rewind it, I could pull it
>> in "next" (and keep pulling your "master" in my "master") for
>> wider exposure if you like.
>
> I intend to pull "new" into "master" shortly, assuming I don't get any
> bug reports for the "new" branch. :)
>
> If you pull my "new" into your "next", and you then pull your "next"
> into your "master", and I pull my "new" into my "master", and you pull
> my "master" into your "master", won't we end up with duplicate merges?

Yes, but I rarely if ever pull "next" as a whole into "master".

Re: Gitk feature - show nearby tags

[Paul Mackerras]

Junio C Hamano writes:

> That would be useful I think.

Done.  It was pretty easy with the infrastructure for doing the tags
in place.

> Yes, but I rarely if ever pull "next" as a whole into "master".

I see.  In that case it probably would be good if you pulled the gitk
"new" branch into "next".

Paul.

Re: Gitk feature - show nearby tags

[Paul Mackerras]

Marco Costalba writes:

> If I have understood correctly the patch runs a 'git rev-list --all
> --topo-order --parents'
> and then does a tree walking.

Yes, that's right.  It means that gitk can show the nearest tags even
if they aren't included in the current view.

> I am wandering if there exist any native git way to found the previous tag.

I don't know of any.  Doing the tree walking in Tcl turned out to be
not too much of an overhead, though; it does the whole kernel
repository in 1.5 seconds on my G5.

> As example given a selected revision with id <sha> is it possible to
> do something like this to fond the ancestor?
> 
> 1) get the tag list with git-peek-remote or something similar if tags
> are not already loaded
> 
> 2) given the tagList vector with n elements run
> 
>     git-rev-list  --topo-order <sha> ^tagList[0]  ^tagList[1]   ....
>   ^tagList[n-1]
> 
> 3) take the last sha spit out by git-rev-list, be it <lastSha>.
> 
> 4) Previous nearest tag is the parent of lastSha
> 
> I've missed something?

I'm not sure exactly what that would do, but gitk can show more than
one tag (the term "nearest tag" is only a shorthand approximation for
what it does).  For example, if you have two tagged commits where
neither is an ancestor of the other, and do a merge of the two, gitk
will show both tags when you select the merge.  It doesn't actually
happen in the kernel repository, though, because the tags there form a
linear list (at least the tags in the upstream repository do).

Paul.

Re: Gitk feature - show nearby tags

[Marco Costalba]

On 6/4/06, Paul Mackerras <paulus@samba.org> wrote:
> Marco Costalba writes:
>
> > If I have understood correctly the patch runs a 'git rev-list --all
> > --topo-order --parents'
> > and then does a tree walking.
>
> Yes, that's right.  It means that gitk can show the nearest tags even
> if they aren't included in the current view.
>
> > I am wandering if there exist any native git way to found the previous tag.
>
> I don't know of any.  Doing the tree walking in Tcl turned out to be
> not too much of an overhead, though; it does the whole kernel
> repository in 1.5 seconds on my G5.
>
> > As example given a selected revision with id <sha> is it possible to
> > do something like this to fond the ancestor?
> >
> > 1) get the tag list with git-peek-remote or something similar if tags
> > are not already loaded
> >
> > 2) given the tagList vector with n elements run
> >
> >     git-rev-list  --topo-order <sha> ^tagList[0]  ^tagList[1]   ....
> >   ^tagList[n-1]
> >
> > 3) take the last sha spit out by git-rev-list, be it <lastSha>.
> >
> > 4) Previous nearest tag is the parent of lastSha
> >
> > I've missed something?
>
> I'm not sure exactly what that would do, but gitk can show more than
> one tag (the term "nearest tag" is only a shorthand approximation for
> what it does).  For example, if you have two tagged commits where
> neither is an ancestor of the other, and do a merge of the two, gitk
> will show both tags when you select the merge.

What you suggest we need it's a kind of history of tags.

Currently we can run

git-rev-list --top-order --parents HEAD -- foo.c

and we get an history of file foo.c *with modified parents*

Junio, could be possible have something like

git-rev-list --top-order --parents --tags

with the history of tags ?

And, according to Paul suggestions, not only tags, but merge revisions
between tags.

A more general and IMHO very powerful tool could be something like

git-rev-list --top-order --parents --selected-only HEAD -- <sha 1>
<sha 2> .....  <sha n>

Where git rev list gives the history, with modified parents, of the
given revisions _only_ plus the merging revisions among them.

This could be used for tags (got from git-peek-remote), for branches
and in general for a given set of interesting revisions.

Once we have the history of tags, perhaps requested once at startup,
we can get the previous tags of a given revision, our original
problem, with

git-rev-list  --topo-order <sha> ^tagList[0]  ^tagList[1]   ....
^tagList[n-1] ^merge[0] ... ^merge[k]

And have one or more tags according if results is a rev in tagList or
mergeList. Having the tag history it's easy to look up _all_ the tag
ancestors.

       Marco

P.S: another use of

git-rev-list --top-order --parents --selected-only HEAD -- <sha 1>
<sha 2> .....  <sha n>

could be this:

Currently both qgit and gitk can filter revisions with a given set of
filter rules, but the results are shown together with the other
revisions or as a list of matching revisions with no useful graph
information.
We could feed git-rev-list --top-order --parents --selected-only with
the list of matching revisions and have a pretty and sensible graph
too.

Re: Gitk feature - show nearby tags

[Junio C Hamano]

"Marco Costalba" <mcostalba@gmail.com> writes:

> As example given a selected revision with id <sha> is it possible to
> do something like this to fond the ancestor?
>
> 1) get the tag list with git-peek-remote or something similar if tags
> are not already loaded
>
> 2) given the tagList vector with n elements run
>
>    git-rev-list  --topo-order <sha> ^tagList[0]  ^tagList[1]   ....
>  ^tagList[n-1]
>
> 3) take the last sha spit out by git-rev-list, be it <lastSha>.
>
> 4) Previous nearest tag is the parent of lastSha

Sorry, I do not understand what you are doing here at all.
Suppose you have this simple history.

  (root)

         a---b---d---e---f---g
         t1   \ /        t3        
            ---c
               t2

and <sha1> in (2) is "e".  When tagList = (t1, t2, t3), the
above rev-list would return empty.  For tagList = (t1, t2), the
rev-list would return "e", and then "d".  Parent of "d" are "b"
and "c", and c is tagged but b is not.  So if you are willing to
try 2^N permutations of what tagList to use, then the above
sequence, with a bit of tweak to step (4) to see which parents
are tagged, would yield the closest tag in the past of "e", but
is that what you are suggesting?

Re: Gitk feature - show nearby tags

[Junio C Hamano]

"Marco Costalba" <mcostalba@gmail.com> writes:

> What you suggest we need it's a kind of history of tags.

I do not understand what you mean by "history of tags".  Are you
talking about "tag v1.0.0 was pointing at X commit yesterday but
now today it points at Y commit"?

> And, according to Paul suggestions, not only tags, but merge revisions
> between tags.
>
> A more general and IMHO very powerful tool could be something like
>
> git-rev-list --top-order --parents --selected-only HEAD -- <sha 1>
> <sha 2> .....  <sha n>
>
> Where git rev list gives the history, with modified parents, of the
> given revisions _only_ plus the merging revisions among them.

You completely lost me here.  The '--' markers are to mean "from
here on the parameters are not revisions but are path limiters",
so you are doing something else.  What are these <sha1#1>, <sha1#2>,...
in this?  Are they revisions (i.e. commit object names)?

Re: Gitk feature - show nearby tags

[Marco Costalba]

On 6/4/06, Junio C Hamano <junkio@cox.net> wrote:
> "Marco Costalba" <mcostalba@gmail.com> writes:
>
> > What you suggest we need it's a kind of history of tags.
>
> I do not understand what you mean by "history of tags".  Are you
> talking about "tag v1.0.0 was pointing at X commit yesterday but
> now today it points at Y commit"?
>
> > And, according to Paul suggestions, not only tags, but merge revisions
> > between tags.
> >
> > A more general and IMHO very powerful tool could be something like
> >
> > git-rev-list --top-order --parents --selected-only HEAD -- <sha 1>
> > <sha 2> .....  <sha n>
> >
> > Where git rev list gives the history, with modified parents, of the
> > given revisions _only_ plus the merging revisions among them.
>
> You completely lost me here.  The '--' markers are to mean "from
> here on the parameters are not revisions but are path limiters",
> so you are doing something else.  What are these <sha1#1>, <sha1#2>,...
> in this?  Are they revisions (i.e. commit object names)?

Yes they are.

Insted of path limiters I meant revisions limiters.

Given a revision history like

a
b--|
|   f
|   g
c
d
e

git-rev-list --top-order --parents --selected-only HEAD -- <a>  <g>  <d>

Should output something like

a
b--|
|   g
d

Of course with modified parent information as does git-rev-list
--parents -- foo.c

Re: Gitk feature - show nearby tags

[Marco Costalba]

On 6/4/06, Junio C Hamano <junkio@cox.net> wrote:
> "Marco Costalba" <mcostalba@gmail.com> writes:
>
> > As example given a selected revision with id <sha> is it possible to
> > do something like this to fond the ancestor?
> >
> > 1) get the tag list with git-peek-remote or something similar if tags
> > are not already loaded
> >
> > 2) given the tagList vector with n elements run
> >
> >    git-rev-list  --topo-order <sha> ^tagList[0]  ^tagList[1]   ....
> >  ^tagList[n-1]
> >
> > 3) take the last sha spit out by git-rev-list, be it <lastSha>.
> >
> > 4) Previous nearest tag is the parent of lastSha
>
> Sorry, I do not understand what you are doing here at all.
> Suppose you have this simple history.
>
>   (root)
>
>          a---b---d---e---f---g
>          t1   \ /        t3
>             ---c
>                t2
>
> and <sha1> in (2) is "e".  When tagList = (t1, t2, t3), the
> above rev-list would return empty.

This is enough!

Empty list is an useful and enough information.

It means:

1) Parent of current revision ("e" in our case) is a tag, indeed our seeked tag.
2) If previous point is not true then there are no previous tags.

In a less corner case, just to better explaing my idea, consider this:

          a---b---d---e---f---g---h
          t1   \ /              t3
             ---c
                t2

Where our sha1 is still "e", in this case

git-rev-list  --topo-order <e>  ^a  ^c   ^g

gives, as last revision in output list, "f"
Then parentOf(<f>) is <g> and our looked for tag is t3

   Marco

Re: Gitk feature - show nearby tags

[Junio C Hamano]

"Marco Costalba" <mcostalba@gmail.com> writes:

> In a less corner case, just to better explaing my idea, consider this:
>
>          a---b---d---e---f---g---h
>          t1   \ /              t3
>             ---c
>                t2
>
> Where our sha1 is still "e", in this case
>
> git-rev-list  --topo-order <e>  ^a  ^c   ^g
>
> gives, as last revision in output list, "f"
> Then parentOf(<f>) is <g> and our looked for tag is t3

Sorry, in the example time flows from left to right.  If you
exclude g then you are excluding everything that is reachable
from g so you would not see "f".

Even if your example is different from what I gave (which had
"a" as the root commit) and h is the root commit, your ^a and ^c
would exclude everything that is reachable from either a or c,
so you would get an empty set.  So your "last revision in
output" would not be "f" either.

Re: Gitk feature - show nearby tags

[Junio C Hamano]

Junio C Hamano <junkio@cox.net> writes:

> "Marco Costalba" <mcostalba@gmail.com> writes:
>
>> In a less corner case, just to better explaing my idea, consider this:
>>
>>          a---b---d---e---f---g---h
>>          t1   \ /              t3
>>             ---c
>>                t2
>>
>> Where our sha1 is still "e", in this case
>>
>> git-rev-list  --topo-order <e>  ^a  ^c   ^g
>>
>> gives, as last revision in output list, "f"
>> Then parentOf(<f>) is <g> and our looked for tag is t3
>
> Sorry, in the example time flows from left to right.  If you
> exclude g then you are excluding everything that is reachable
> from g so you would not see "f".
>
> Even if your example is different from what I gave (which had
> "a" as the root commit) and h is the root commit, your ^a and ^c
> would exclude everything that is reachable from either a or c,
> so you would get an empty set.  So your "last revision in
> output" would not be "f" either.

BTW, that was exactly what I meant by "2^N permutations of
tags".  If you exclude all tags that are older than "e" then
your algorithm would work beautifully, but the algorithm is
about finding out which tags are older than "e" to begin with,
so...

Re: Gitk feature - show nearby tags

[Marco Costalba]

On 6/4/06, Junio C Hamano <junkio@cox.net> wrote:
> "Marco Costalba" <mcostalba@gmail.com> writes:
>
> > In a less corner case, just to better explaing my idea, consider this:
> >
> >          a---b---d---e---f---g---h
> >          t1   \ /              t3
> >             ---c
> >                t2
> >
> > Where our sha1 is still "e", in this case
> >
> > git-rev-list  --topo-order <e>  ^a  ^c   ^g
> >
> > gives, as last revision in output list, "f"
> > Then parentOf(<f>) is <g> and our looked for tag is t3
>
> Sorry, in the example time flows from left to right.  If you
> exclude g then you are excluding everything that is reachable
> from g so you would not see "f".
>
From today git:

tag list is:

v1.3.3 1b9bc5a7b7434d771726011613a00cb202bd9f44
v1.3.2 7abd7117ec57b8c3c2a469db62c7811fdac5c655
v1.3.1 7d09fbe4ab7f080a8f8f5dcef7e0f3edf5e26019
v1.3.0 4baff50551545e2b6825973ec37bcaf03edb95fe

selected sha is ccb365047a1081455b767867f0887e7b4334f9d8
(Allow "git repack" users to specify repacking window/depth)

$ git-rev-list --topo-order ccb365047a1081455b767867f0887e7b4334f9d8
^1b9bc5a7b7434d771726011613a00cb202bd9f44
^7abd7117ec57b8c3c2a469db62c7811fdac5c655
^7d09fbe4ab7f080a8f8f5dcef7e0f3edf5e26019
^4baff50551545e2b6825973ec37bcaf03edb95fe

ccb365047a1081455b767867f0887e7b4334f9d8
85e6326cc3e7c272566c60a39741f84391830d49
4262c1b0c38613a8c5ae729bd4d3f18f0df3ec44
24735cfc500feb2a8dba9f140080ab3476363d28
caef71a5354ca162cc5a6914a7a643efbc9ae28a
34e98ea56414adc5a582e6368e8ec9c109dbee48
3a624b346db02a07b0317743b362d1a15c6c3c18
965f803c323bb72a9dedbbc8f7ba00bbadb6cf58
b073f26b256cded6252bafd34982eb6f69d2a4b6
a4d34e2db5565e6b75f79f9d3938aa9151e72e44
eab144ac49c18d981261c2d0ba964d6380d9f1da
9153983310a169a340bd1023dccafd80b70b05bc
db89665fbf86d4e0166b2f252a939ed8bf6782fe
78fff6ebbafe2d23464a2b059104954bfe8732c7
cb8f64b4e3f263c113b7a2f156af74b810e969ff
d4ed9793fd981ea5a35ebaa8e337446bb29f6d55
b2934926dd7455de61577c1dfdf4c12d224e7ae0
ba1d45051e050cbcf68ccccacea86a4b6ecde731
5b84f4d87a1bd58c7540e9ea82ee3673ecddbad5
7594c4b2d7cc81f806453402aefe1bf71ae6dd53
6b9c58f4669b3832ed2830f0cb1a307ea6bc6063
8c1f0b44c59530dea8007a9f5b69d0fac6aea3b1
8e8f998739db6526fe890fabc88c866759bc2ac3
cd2bdc5309461034e5cc58e1d3e87535ed9e093b

Parent of cd2bdc5309461034e5cc58e1d3e87535ed9e093b is

4baff50551545e2b6825973ec37bcaf03edb95fe

aka tag v1.3.0

Am I missing something?

Re: Gitk feature - show nearby tags

[Marco Costalba]

On 6/4/06, Marco Costalba <mcostalba@gmail.com> wrote:
> On 6/4/06, Junio C Hamano <junkio@cox.net> wrote:
> > "Marco Costalba" <mcostalba@gmail.com> writes:
> >
> > > In a less corner case, just to better explaing my idea, consider this:
> > >
> > >          a---b---d---e---f---g---h
> > >          t1   \ /              t3
> > >             ---c
> > >                t2
> > >
> > > Where our sha1 is still "e", in this case
> > >
> > > git-rev-list  --topo-order <e>  ^a  ^c   ^g
> > >
> > > gives, as last revision in output list, "f"
> > > Then parentOf(<f>) is <g> and our looked for tag is t3
> >
> > Sorry, in the example time flows from left to right.  If you
> > exclude g then you are excluding everything that is reachable
> > from g so you would not see "f".

To better explain what I mean, that's the algorithm :

cmd = "git-rev-list --topo-order --parents " + sha;
for (uint i = 0; i < tagList.count(); i++)
	cmd.append(" ^" + tagList[i]);

output = run(cmd);

if (output.isEmpty()) {
	parent = parentOf(sha);
	return (parent && parent->isTag()) ? parent->tag() : NO_TAG;
}

lastSha = getLastLine(output);
parent = parentOf(lastSha);
return (parent && parent->isTag()) ? parent->tag() : NO_TAG;

Re: Gitk feature - show nearby tags

[Junio C Hamano]

"Marco Costalba" <mcostalba@gmail.com> writes:

>> Sorry, in the example time flows from left to right.  If you
>> exclude g then you are excluding everything that is reachable
>> from g so you would not see "f".
>>
> From today git:
>
> tag list is:
>
> v1.3.3 1b9bc5a7b7434d771726011613a00cb202bd9f44
> v1.3.2 7abd7117ec57b8c3c2a469db62c7811fdac5c655
> v1.3.1 7d09fbe4ab7f080a8f8f5dcef7e0f3edf5e26019
> v1.3.0 4baff50551545e2b6825973ec37bcaf03edb95fe
>
> selected sha is ccb365047a1081455b767867f0887e7b4334f9d8
> (Allow "git repack" users to specify repacking window/depth)
>
> $ git-rev-list --topo-order ccb365047a1081455b767867f0887e7b4334f9d8
> ^1b9bc5a7b7434d771726011613a00cb202bd9f44
> ^7abd7117ec57b8c3c2a469db62c7811fdac5c655
> ^7d09fbe4ab7f080a8f8f5dcef7e0f3edf5e26019
> ^4baff50551545e2b6825973ec37bcaf03edb95fe
>
> ccb365047a1081455b767867f0887e7b4334f9d8
> ...
> cd2bdc5309461034e5cc58e1d3e87535ed9e093b
>
> Parent of cd2bdc5309461034e5cc58e1d3e87535ed9e093b is
>
> 4baff50551545e2b6825973ec37bcaf03edb95fe
>
> aka tag v1.3.0
>
> Am I missing something?

No, just that I am not getting what you are trying to prove
here.  The tags are all older than your chosen commit.

$ git-rev-list --topo-order ^v1.3.0 ^v1.3.1 ^v1.3.2 ^v1.3.3 e923eff

would show nothing -- and you propose to find out that commit is
between v1.3.1 and v1.3.2 by using the information that the
command gives an empty result but I do not know how?

$ git show-branch v1.3.1 e923eff v1.3.2

does show it is between these two, but that is because it avoids
the 2^N permutations by using 1-bit per revision that it wants to
check the reachability across.

Re: Gitk feature - show nearby tags

[Marco Costalba]

On 6/4/06, Junio C Hamano <junkio@cox.net> wrote:
> "Marco Costalba" <mcostalba@gmail.com> writes:
>
> >> Sorry, in the example time flows from left to right.  If you
> >> exclude g then you are excluding everything that is reachable
> >> from g so you would not see "f".
> >>
> > From today git:
> >
> > tag list is:
> >
> > v1.3.3 1b9bc5a7b7434d771726011613a00cb202bd9f44
> > v1.3.2 7abd7117ec57b8c3c2a469db62c7811fdac5c655
> > v1.3.1 7d09fbe4ab7f080a8f8f5dcef7e0f3edf5e26019
> > v1.3.0 4baff50551545e2b6825973ec37bcaf03edb95fe
> >
> > selected sha is ccb365047a1081455b767867f0887e7b4334f9d8
> > (Allow "git repack" users to specify repacking window/depth)
> >
> > $ git-rev-list --topo-order ccb365047a1081455b767867f0887e7b4334f9d8
> > ^1b9bc5a7b7434d771726011613a00cb202bd9f44
> > ^7abd7117ec57b8c3c2a469db62c7811fdac5c655
> > ^7d09fbe4ab7f080a8f8f5dcef7e0f3edf5e26019
> > ^4baff50551545e2b6825973ec37bcaf03edb95fe
> >
> > ccb365047a1081455b767867f0887e7b4334f9d8
> > ...
> > cd2bdc5309461034e5cc58e1d3e87535ed9e093b
> >
> > Parent of cd2bdc5309461034e5cc58e1d3e87535ed9e093b is
> >
> > 4baff50551545e2b6825973ec37bcaf03edb95fe
> >
> > aka tag v1.3.0
> >
> > Am I missing something?
>
> No, just that I am not getting what you are trying to prove
> here.  The tags are all older than your chosen commit.
>
> $ git-rev-list --topo-order ^v1.3.0 ^v1.3.1 ^v1.3.2 ^v1.3.3 e923eff
>
> would show nothing -- and you propose to find out that commit is
> between v1.3.1 and v1.3.2 by using the information that the
> command gives an empty result but I do not know how?
>

OK. Now I understand.

I was erroneously thinking that in

$ git-rev-list --topo-order e923eff ^v1.3.0 ^v1.3.1 ^v1.3.2 ^v1.3.3

the listing (and searching) was _starting_ from e923eff, i.e. all the
previous stuff, in our case v1.3.2 and v1.3.3 was never seen neither
filtered out.

Following an extract from git-rev-list documentation.

DESCRIPTION
-----------
Lists commit objects in reverse chronological order *starting at the
given commit(s)*, taking ancestry relationship into account.  This is
useful to produce human-readable log output.

Commits which are stated with a preceding '{caret}' *cause listing to stop at
that point*. Their parents are implied. "git-rev-list foo bar {caret}baz" thus
means "list all the commits which are included in 'foo' and 'bar', but
not in 'baz'".



Perhaps it's me, but I really don't found clear from documentation
that git-rev-list anySha ^HEAD gives _always_ an empty result.

What I understand is that git-rev-list lists _first_ the given commit,
then his parents, then his grandparents and so on _until_ a commit
which is stated with a preceding '{caret}'  is found.
So everything that is between the given commit and HEAD is never found
and ignored.

Is it a problem to change the git-rev-list behaviour to reflect (my
understanding of) documentation or it breaks something?

If I have understood correctly with this change the above proposed
algorithm should work.

    Marco

Re: Gitk feature - show nearby tags

[Junio C Hamano]

Jonas Fonseca <fonseca@diku.dk> writes:

> The problem is of course to come up with some ascii-art which is both
> readable and dense. Below is my mockup of something not using line
> graphics, however using line graphics it might be possible to get
> something more unambiguos but also more "edgy".

I do not necessarily think an ascii-art is needed, nor an
appropriate way to present it to the curses user.  When the user
wants to "view" a commit, you could show from which branch heads
and from which tags the commit is reachable, and perhaps which
tag is the latest among the ones reachable from that commit, as
part of the commit detail information you display on the lower
pane (log/diff view).

I may not be using tig in the way it was intended to, but I
often find it frustrating having to do the following:

    - start tig, which shows list of one-line logs.  Wonderful.

    - browsing around by UP or DOWN and stop at one particular commit
      I want to view closely.  Press Enter and the screen split
      into two and I see what I want to see.  Again, wonderful.

    - I want to see the neighbouring commits, but UP or DOWN
      does not do what I naïvely expect.  It scrolls the lower
      pane.  I say TAB to go up.

    - Press UP or DOWN and I can move the highlight to
      neighbouring commits.  This is wonderful, but the lower
      pane does not follow this -- it keeps showing the original
      commit, and I have to say ENTER again.

It might make sense to make the log/diff view follow what
happens on the main view when both are on-screen.

Re: Gitk feature - show nearby tags

[Jonas Fonseca]

Junio C Hamano <junkio@cox.net> wrote Sun, Jun 04, 2006:
> 
> I may not be using tig in the way it was intended to, but I
> often find it frustrating having to do the following:
> 
>     - start tig, which shows list of one-line logs.  Wonderful.
> 
>     - browsing around by UP or DOWN and stop at one particular commit
>       I want to view closely.  Press Enter and the screen split
>       into two and I see what I want to see.  Again, wonderful.
> 
>     - I want to see the neighbouring commits, but UP or DOWN
>       does not do what I naïvely expect.  It scrolls the lower
>       pane.  I say TAB to go up.

I wonder what tig version you are using. If you are using the tig
version from my git repo this should also be working to your
expectation, making ...

>     - Press UP or DOWN and I can move the highlight to
>       neighbouring commits.  This is wonderful, but the lower
>       pane does not follow this -- it keeps showing the original
>       commit, and I have to say ENTER again.

.. this unnecessary. At least, I'd like to keep the one-line log view
from forcing updates of the diff view so it is more responsive over slow
links.

> It might make sense to make the log/diff view follow what
> happens on the main view when both are on-screen.

With my current version, the two views are much more integrated, e.g.
you can press 'd' to show full-screen diff view and use Up and Down to
navigate the log view.

-- 
Jonas Fonseca

Re: Gitk feature - show nearby tags

[Junio C Hamano]

Jonas Fonseca <fonseca@diku.dk> writes:

>>     - I want to see the neighbouring commits, but UP or DOWN
>>       does not do what I naïvely expect.  It scrolls the lower
>>       pane.  I say TAB to go up.
>
> I wonder what tig version you are using. If you are using the tig
> version from my git repo this should also be working to your
> expectation, making ...

Whichever was the latest when I wrote the message.  I see you
have added a handful commits on it since then.

>>     - Press UP or DOWN and I can move the highlight to
>>       neighbouring commits.  This is wonderful, but the lower
>>       pane does not follow this -- it keeps showing the original
>>       commit, and I have to say ENTER again.
>
> .. this unnecessary.

Maybe I am misusing it then.

"full-screen" diff view and being able to do [UP] and [DOWN] to
move around there do not feel useful to me that much.  It is
something "git log -p" does already, thanks to its output paged
via "less" by default.

I like viewing the list in the upper and diff/log in the lower
at the same time, and that is the primary reason I liked tig, so
moving around in the commit list view and not seeing the
diff/log updated in sync was major dissapointment at least for
me.

Re: Gitk feature - show nearby tags

[Junio C Hamano]

"Marco Costalba" <mcostalba@gmail.com> writes:

> What I understand is that git-rev-list lists _first_ the given commit,
> then his parents, then his grandparents and so on _until_ a commit
> which is stated with a preceding '{caret}'  is found.
> So everything that is between the given commit and HEAD is never found
> and ignored.

As you now know, the way it works is that it takes an unordered
set of committishes, and performs a set operation that says
"include everybody reachable from positive ones while excluding
everybody reachable from negative ones".  --topo-order tells it
to topologically (instead of doing the commit date-order which
it does by default) sort the resulting list.  The resulting list
is then written out.

> Is it a problem to change the git-rev-list behaviour to reflect (my
> understanding of) documentation or it breaks something?

I suspect it would break quite many things.  Existing users use
the command knowing it is a set operation on an unordered set of
committishes, and expect the command to behave that way.  Also
the most typical use A..B translates to ^B A (either internally
or by rev-parse) so "the first" would typically be a negative
one.

I think your "start from positive ones, traverse one by one and
stop traversal that hits the negative one" logic requires the
negative one to be directly on the traversal paths starting from
positive ones to have _any_ effect.  We often ask "what's the
ones that are still not merged to the master from the side
branch" while dealing with topic branches:

         c-------d---e master         time flows from
        /       /                     left to right
 --a---b---x---y---z side

and the way to ask that question is "rev-list master..side"
(which is "rev-list side ^master").  It should list z and not
show y nor x nor b nor a.

In order for it to be able to notice that y should not be
listed, it needs to perform traversals from negative ones as
well in order to learn that y is reachable from master.  

How would you ask the same question to the modified rev-list
that does "start from positive ones, traverse one by one and
stop traversal that hits the negative one" logic?

I think one useful thing we can do is to generalize what
"describe", "nave-rev", and "merge-base" do to have a command
that takes a committish X and a set of other committish T1..Tn,
and examines if Ti (1<=i<=n) is reachable from X and if X is
reachable from Ti (1<=i<=n), and give a short-hand to specify
the set of T for common patterns like --heads --tags and --all.

But that would not be rev-list; I suspect you would end up doing
something quite similar to what show-branch does.

Re: Gitk feature - show nearby tags

[Marco Costalba]

On 6/5/06, Junio C Hamano <junkio@cox.net> wrote:
> "Marco Costalba" <mcostalba@gmail.com> writes:
>
> I think your "start from positive ones, traverse one by one and
> stop traversal that hits the negative one" logic requires the
> negative one to be directly on the traversal paths starting from
> positive ones to have _any_ effect.  We often ask "what's the
> ones that are still not merged to the master from the side
> branch" while dealing with topic branches:
>
>          c-------d---e master         time flows from
>         /       /                     left to right
>  --a---b---x---y---z side
>
> and the way to ask that question is "rev-list master..side"
> (which is "rev-list side ^master").  It should list z and not
> show y nor x nor b nor a.
>
> In order for it to be able to notice that y should not be
> listed, it needs to perform traversals from negative ones as
> well in order to learn that y is reachable from master.
>

Thanks for your clear explanation. Now I see much better what's the deal.

>
> I think one useful thing we can do is to generalize what
> "describe", "nave-rev", and "merge-base" do to have a command
> that takes a committish X and a set of other committish T1..Tn,
> and examines if Ti (1<=i<=n) is reachable from X and if X is
> reachable from Ti (1<=i<=n), and give a short-hand to specify
> the set of T for common patterns like --heads --tags and --all.
>

I don't know if this is enough for our original problem to find previous tag.

Our problem is indeed not only to find previous tags, but _nearest_
previous, so I think we have to think to a generalization that takes
in account also a kind of 'metric' among tags because the only
reachability seems to fall short in finding the nearset one.

But definitely I need to think more about this ;-)

   Marco

Re: Gitk feature - show nearby tags

[Junio C Hamano]

Junio C Hamano <junkio@cox.net> writes:

> Jonas Fonseca <fonseca@diku.dk> writes:
>
> Whichever was the latest when I wrote the message.  I see you
> have added a handful commits on it since then.
>
>>>     - Press UP or DOWN and I can move the highlight to
>>>       neighbouring commits.  This is wonderful, but the lower
>>>       pane does not follow this -- it keeps showing the original
>>>       commit, and I have to say ENTER again.
>>
>> .. this unnecessary.
>
> Maybe I am misusing it then.

Sorry, I *was* misusing it.  I was doing PageUp/PageDown.  Duh.

I typed uparrow and downarrow while in the split view and it was
doing what I wanted to do.

Re: Gitk feature - show nearby tags

[Jonas Fonseca]

Junio C Hamano <junkio@cox.net> wrote Sun, Jun 04, 2006:
> Jonas Fonseca <fonseca@diku.dk> writes:
> 
> >>     - I want to see the neighbouring commits, but UP or DOWN
> >>       does not do what I naïvely expect.  It scrolls the lower
> >>       pane.  I say TAB to go up.
> >
> > I wonder what tig version you are using. If you are using the tig
> > version from my git repo this should also be working to your
> > expectation, making ...
> 
> Whichever was the latest when I wrote the message.  I see you
> have added a handful commits on it since then.

Yes, I added your Makefile patch. Thanks for that one.

> >>     - Press UP or DOWN and I can move the highlight to
> >>       neighbouring commits.  This is wonderful, but the lower
> >>       pane does not follow this -- it keeps showing the original
> >>       commit, and I have to say ENTER again.
> >
> > .. this unnecessary.
> 
> Maybe I am misusing it then.

I admit the basic user controls might still have some rough spots.
Here is my take on what you are trying to do:

 - When you open tig, UP/DOWN will move the cursor line.

 - When you press ENTER on the commit you would like to see, it will
   open the split view and move focus to the diff view.  So if you press
   Enter again it will start scrolling the diff view. This is much like
   the way Mutt works.

 - If you press UP/DOWN (while the diff view is focused) you will move
   to previous or next commit in the main view (the one-line log view)
   and load it in the diff view. That is, there is no reason to switch
   to the main view unless you want to navigate to a commit without
   repeatedly reloading the diff view which is clearly not what you are
   requesting.

Is this not what you requested? That you can "see neighbouring commit"
by pressing UP and DOWN? But without having to press ENTER again.

Now, I've experienced some problems with ncurses and key detection but
only for Insert/Delete and Home/End. If UP/DOWN scrolls the diff view
something is terrible wrong.

> I like viewing the list in the upper and diff/log in the lower
> at the same time, and that is the primary reason I liked tig, so
> moving around in the commit list view and not seeing the
> diff/log updated in sync was major dissapointment at least for
> me.

Ok, well I can just make it optional, if you want the split view always
to be in sync, even while moving when the main view is in focus.

-- 
Jonas Fonseca

Re: Gitk feature - show nearby tags

[Jonas Fonseca]

Junio C Hamano <junkio@cox.net> wrote Sun, Jun 04, 2006:
> I do not necessarily think an ascii-art is needed, nor an
> appropriate way to present it to the curses user.

With certain limitations, I think it could be useful for some
epositories. Optionally, of course.

> When the user wants to "view" a commit, you could show from which
> branch heads and from which tags the commit is reachable, and perhaps
> which tag is the latest among the ones reachable from that commit, as
> part of the commit detail information you display on the lower pane
> (log/diff view).

Thanks for recapping, I've added this to the TODO file.

-- 
Jonas Fonseca