Add "--show-all" revision walker flag for debugging

So the kernel merge window for 2.6.25 is closing today (or possibly tomorrow if I feel like it), and I've already mentally closed it, so I'm starting to free up some resources to look at the interesting problem with screwed-up commit dates confusing our commit walker into thinking that some uninteresting commit isn't actually uninteresting due to not traversing the uninteresting chain deep enough.

But one of the things I noticed is that it's really not very easy to visualize the commit walker, because - on purpose - it obvously doesn't show the uninteresting commits!

So here's a patch that adds a "--show-all" flag to the revision walker, which will make it show uninteresting commits too, and they'll have a '*' in front of them (it also fixes a logic error for !verbose_header for boundary commits - we should show the '-' even if left_right isn't shown).

It also updates 'gitk' to show those negative commits in gray. Whether that's the right color choice or not, I'll leave to bikeshedders, but it looks fairly neutral, and shows the differences pretty well.

It actually is interesting even for the cases that git doesn't have any problems with, ie for the kernel you can do

	gitk -d --show-all v2.6.24..

and you see just how far down it has to parse things to see it all. The use of "-d" is a good idea, since the date-ordered toposort is much better at showing why it goes deep down (ie the date of some of those commits after 2.6.24 is much older, because they were merged from trees that weren't rebased).

So I think this is a useful feature even for non-debugging - just to visualize what git does internally more.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

Heh. Amusingly, the changes to gitk were much bigger than the trivial changes to core git routines themselves. The log-tree.c diffstat is a bit bigger just because of the logic fix (making it more than just another added "else if ()" statement), while much of the revision.c patch is just the argument parsing ;)

 builtin-rev-list.c |    2 ++
 gitk-git/gitk      |   15 ++++++++-------
 log-tree.c         |   12 ++++++++----
 revision.c         |    9 ++++++++-
 revision.h         |    1 +
 5 files changed, 27 insertions(+), 12 deletions(-)

On Sat, 9 Feb 2008, Linus Torvalds wrote:

And here's a slight expansion patch on top of the above

It does:

 - when it actually breaks out due to the "everybody_uninteresting()" 
   case, it adds the uninteresting commits (both the one it's looking at 
   now, and the list of pending ones) to the list

   This way, we really list *all* the commits we've looked at

 - Because we now end up listing commits we may not even have been parsed 
   at all "show_log" and "show_commit" need to protect against commits 
   that don't have a commit buffer entry.

That second part is debatable just how it should work. Maybe we shouldn't show such entries at all (with this patch those entries do get shown, they just don't get any message shown with them). But I think this is a useful case.

		Linus

---
 builtin-rev-list.c |    2 +-
 log-tree.c         |    3 +++
 revision.c         |   11 ++++++++++-
 3 files changed, 14 insertions(+), 2 deletions(-)

Linus Torvalds <torvalds@linux-foundation.org> writes:

Showing them would probably be useful (definitely for debugging), but I do not think it is useful not to show the buffer contents (i.e. adding without parsing).

It _might_ mean that the excess uninteresting ones we take out from "list" can be distinguished from the ones that we did look at (and once thought they were worth keeping), but I do not think it is reliable information. The command line parser may have caused them to be parsed independent from what the revision traversal did.

So I think it would make more sense to parse them while we add them to the "newlist", and if we really want to distinguish them from others we would want to mark them separately with another flag bit.

Or unparse them when we add them to the "newlist".

Hi,

On Sat, 9 Feb 2008, Linus Torvalds wrote:

I was thinking the other night why I did not like the generation header. And I found out why: it is redundant information.

So why not have some local "cache" which maintains the generation numbers for the commits? (Much like the "notes" cache I showed last year?)

Hmm?

Ciao, Dscho

On Sun, 10 Feb 2008, Johannes Schindelin wrote:

Actually, that's not the real issue.

The real issue is that it doesn't work. I thought about it, and with multiple roots (which _can_ get merged together) it just isn't something that actually helps.

If you couldn't merge across roots, you could have a "uuid+generation header", but the moment you have multiple roots it actually gets quite complex.

So scratch the generation header.  It's not the answer.

And I do think that we can do it without it. I'm still thinking about how to do it efficiently, but I think I can get there. I just haven't had the time to sit down and really think it through and try out my ideas yet.

		Linus

Hi,

On Sat, 9 Feb 2008, Linus Torvalds wrote:

I don't see it. If G(c) >= 1 + max(G(c^) | c^ is a parent of c), then it _should_ work. And then, I think it is _much_ better to just cache it locally (if you care enough about it, i.e. if you set a certain config option that triggers possibly expensive one-shot caching) than have it in the commit object (where the information could be just plain wrong).

Ciao, Dscho

Linus Torvalds <torvalds@linux-foundation.org> writes:

I do not think multiple roots can be helped without going all the way down to the roots, and I think it can be proven.

Generation number would on the other hand eliminate the issue of clock skew if heads are connected, and I think it also can be proven.

Both proofs need the axiom "there is no loop in the commit ancestry graph", but that is something we already rely on in the merge-base computation.

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

Ah, please scratch that comment. I was puzzled but did not understand what you meant by uuid+generation.

You are right. If we cannot tell if we are dealing with disconnected history, we would always need to play safe and do the clean-up like what I suggested earlier using merge-base traversal, which could be costly, and we do not want to pay that penalty in a connected history, which should be the normal case.

Generation header does not help us detect that case, so it is not useful.

On Sun, 10 Feb 2008, Johannes Schindelin wrote:

Absolutely.

I, too, have some reservations about adding any kind of generation header to commit objects. First because it can be generated and maintained locally, just like the pack index. But also because its usefulness has not been proven in all possible graph topologies, and adding it to the commit header pretty much deny any further modifications/improvements on it, if for example some other kind of generation notation becomes advantageous to use.

So please don't put it into the commit object format. The object database should ultimately contain only data that cannot be regenerated.

Nicolas

Hi,

On Sat, 9 Feb 2008, Nicolas Pitre wrote:

I fully agree.

Ciao, Dscho

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

I think I'd agree, also because without 'generation' (and 'roots') commit object header being there from beginning it is not clear when to calculate it: the first few commits with it would be costly. Besides graft and shallow information is local, and it affect commit traversal.

I was thinking about pack-index like file, either directly mapping "sha1 -> generation + roots", or indirectly "sha1 -> offset", "offset -> generation + roots".

P.S. Would having generation + roots be enough?

  gen(rev) = max_i { gen(i) + 1 : i in parents(rev) } || 1

  roots(rev) = { rev  if rev is a root (parentless) commit 
               { union of roots of parents of a commit otherwise

Union in the sense of set sum.

Note that if roots was to be saved in commit header, then it couldn't be as simple as commit-id for root commits: no self links. It would have to be empty for root commits, and the "union of roots" would have to be modified to "union of roots or commit ids for root commits, of each of parents of a commit".

On Sun, 10 Feb 2008, Jakub Narebski wrote:

I'm wavering here. Maybe just "generation" works (the longest path from any root), because what we are looking for is essentially "guarantee that this commit cannot possibly be reached from that other commit", and I guess a simple generation count actually does work for that (if the generation of "x" is smaller than the generation of "y", we definitely cannot reach y from x).

At the same time, I'm still not really convinced we need to add the redundant info. I do think I *should* have designed it that way to start with (and I thought so two years ago - blaah), so the strongest reason for "we should add generation numbers" at least for me is that I actually think it's a GoodThing(tm) to have.

But adding it is a pretty invasive thing, and would force people to upgrade (it really isn't backwards compatible - old versions of git would immediately refuse to touch archives with even just a single top commit that has a generation number in it, unless we'd hide it at the end of the buffer and just uglify things in general).

So even if it does work, the advantage isn't big enough for me to think it's really worth it. I'd *really* prefer to not have a flag day here, and the fact is, it's redundant information _and_ it fundamentally doesn't work with grafting anyway, so even if we were able to start from scratch, we'd then have to seriously consider dropping grafts.

So let's work at not needing it, rather than argue whether we could use it or not ;)

		Linus

On Sun, 10 Feb 2008, Linus Torvalds wrote:

Repeating myself: for one, I'm rather against any such generation headers in the commit object, and so is Dscho.

Why?  Because it doesn't have to live in the commit object at all.

Just like we have a locally managed pack index file, we can have a locally managed "index of generations" file just fine.

Nicolas

On Sat, 10 Feb 2008, Linus Torvalds wrote:

Well, "generation" number alone would work quote well as an exclusion mechanism; generation + roots would work better, I think.

Lets take for an example the following revision graph:

roots: a a a aA aA gen: 1 2 3 4 5

       a----b----c----d----e
                     /
            A----B--/

gen: 1 2 roots: A A

For example lone generation number is enough to decide that 'c' (generation 3) cannot be reached from 'a' (generation 1 < 3), and that 'c' (generation 3) cannot be reached from 'B' (generation 2 < 3). Roots allow for easy check that 'B' (gen: 2, roots: A) cannot be reached from 'c' (roots: a, and A \not\in a), but can be reached from 'e' (gen: 5 > 2, roots: aA \ni a).

What I don't know if generation number would be enough to avoid "going to root" or "going to common ancestor" costly case when calculating excluded commits.

While this information can be calculated from revision graph it is I think costly enough that it truly would be better to have it in commit object.

Well, we could always start using core.repositoryFormatVersion ;-)

Well, we could always add it as a local (per repository) "cache". With only generation numbers we could use pack-index-like format to store a mapping "commit sha-1 => generation number", just like now pack index stores mapping "object sha-1 => offset in pack".

If we want to store also roots, we could either map "commit sha-1 => generation number, roots set offset / id" (constant length value)[*1*], or have gen-*.gen file with generation numbers and roots, and gen-*.idx as index to that file.

[*1*] If I understand math correctly it would limit us in theory to up to 64 roots (git.git has 8 roots IIRC).

On Sun, 10 Feb 2008, Jakub Narebski wrote:

Yes, and even embedding this in the pack-file (or perhaps, the index, as a new index extension) is probably a good idea.

The thing is, the roots are almost never actually interesting. Very seldom do you have any issue with different commits having different roots. So I really don't think it's worth it, considering that it's also much more complicated than just adding a sequence number to each commit.

		Linus

Linus Torvalds wrote:

Errr... index is per workarea (per checkout), and this information is per repository, so IMHO storing this info in an index (dircache) is a layering violation. Unless you were talking about pack-file-index.

I think that separate file is better idea, this way we can update generation info lazily: when we went to the root or project whose all parents have generatrion number, then we save gen numbers to such "cache" file. If we had to calculate it (even accidentally), save it.

Weren't the cases of multiple roots that were difficult? Storing roots would help with 'hard' (if seldom happening) cases then.

On Mon, 11 Feb 2008, Jakub Narebski wrote:

The pack index isn't a good idea since one pack doesn't necessarily cover the whole of the repository. A separate new file is the only sensible thing to do, if done at all.

Nicolas

On Mon, 11 Feb 2008, Jakub Narebski wrote:

I did mean the pack-file index, not the "cache" index.

It's not that they aren't difficult, it's that they are so rare (ie having ranges that really *are* separate never happens in practice). So it's not worth worrying about from a performance angle.

The thing that worried me about multiple roots was that they make the generation numbers essentially "meaningless" when compared across totally unrelated commits, and might give incorrect results for generation number comparisons as a result.

However, I decided that if two commits really *are* totally unrelated and don't share a commit, then:

 - yes, the generation number comparison is "meaningless"

 - BUT: we don't actually care if it's correct or not, because it will 
   never matter: whatever we choose to do, it's correct. Because there are 
   just two choices:

    (a) stop early because everything we have left is uninteresting

        This is correct, because if they have two separate roots, they'll 
        never meet anyway, so from a correctness standpoint they will 
        never change a interesting commit into an uninteresting one.

    (b) continue to the root because we think we might turn something 
        interesting into an uninteresting commit. This may be wasteful 
        (because the generation numbers happened to fool us into thinking 
        we migth care and one is older than the other), but it's still 
        technically _correct_.

        And we really don't need to care about the performance issues 
        since continuing down to the root is what we'd have had to do even 
        without the generation numbers anyway, but more importantly 
        because we simply don't care - if people start doing comparisons 
        across truly independent commits, they are doing something wrong.

So that's why a generation number is sufficient.

And yes, just generating the generation number when repacking is fine. It would mean that unpacked objects don't have generation numbers, but of you have tons and tons of unpacked objects, you have more serious problems anyway!

			Linus

On Mon, 11 Feb 2008, Linus Torvalds wrote:

With generation number info in pack index, we could generate them on repack (adding some time to repack).

With generation number info in separate pack-index like file, we could add generation info whenever during browsing history we get to root or to commit with generation number, saving generation numbers in the by-the-way way, generating them lazily.

By the way, with generation number we can always limit walk length to difference between generation numbers, or distance to root if it is smaller.

On Mon, 11 Feb 2008, Linus Torvalds wrote:

I think this has nothing to do with pack index either. Your repo may have one pack, or multiple packs, or even no pack at all. They may or may not contain commit objects, etc.

The generation indexing is OTOH a repo wide issue, completely orthogonal to object packing. It has to be centralized in a single global file, or possibly one file per branch, and updated whenever new commits are added to the repository. I think the best format is to have a list of (generation_nr, commit_sha1) tuples in assending order, so whenever a fetch or a commit is performed then updating this file is only a matter of appending to it.

And optimizing it even further, only merge commits (or rather merge direct parents as well as branch heads) should have their generation number cached in a file since the linear commits are trivially deduced from there.

And regenerating this generation cache should not take longer than a full history walk.

Nicolas