Gitk feature - show nearby tags

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.

Paul Mackerras <paulus@samba.org> 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.

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.

On 6/3/06, Junio C Hamano <junkio@cox.net> wrote:

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

Marco Costalba writes:

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

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.

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.

On 6/4/06, Paul Mackerras <paulus@samba.org> wrote:

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.

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

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"?

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)?

On 6/4/06, Junio C Hamano <junkio@cox.net> wrote:

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

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

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?

On 6/4/06, Junio C Hamano <junkio@cox.net> wrote:

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

"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".

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.

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

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...

On 6/4/06, Junio C Hamano <junkio@cox.net> wrote:

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?

On 6/4/06, Marco Costalba <mcostalba@gmail.com> wrote:

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;

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

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.

On 6/4/06, Junio C Hamano <junkio@cox.net> wrote:

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

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

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.

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.

On 6/5/06, Junio C Hamano <junkio@cox.net> wrote:

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

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

Junio C Hamano writes:

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?

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.

Paul Mackerras <paulus@samba.org> writes:

That would be useful I think.

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

Junio C Hamano writes:

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

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

Paul.

Junio C Hamano <junkio@cox.net> wrote Sat, Jun 03, 2006:

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 wrote:

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 <jnareb@gmail.com> wrote Sat, Jun 03, 2006:

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] ...
	| * ...
	*' ...

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 <fonseca@diku.dk> writes:

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.

Junio C Hamano <junkio@cox.net> wrote Sun, Jun 04, 2006:

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 ...

.. 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.

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 <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.

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.

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

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.

Junio C Hamano <junkio@cox.net> wrote Sun, Jun 04, 2006:

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

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.

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.

Junio C Hamano <junkio@cox.net> wrote Sun, Jun 04, 2006:

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

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