From: Petr Baudis <hidden> Date: 2016-06-15 22:42:22
Dear diary, on Sun, Mar 26, 2006 at 05:19:50AM CEST, I got a letter
where Linus Torvalds [off-list ref] said that...
On Sun, 26 Mar 2006, Petr Baudis wrote:
quoted
In [1], Linus suggests a non-core solution. Unfortunately, it doesn't
fly - it requires at least two git-ls-tree calls per revision which
would bog things down awfully (to roughly half of the original speed).
No it doesn't. It requires one git-ls-tree WHEN SOMETHING IS RENAMED.
In other words, basically never.
Huh? I don't see that now (and caps don't help me see it better). That's
certainly not what is in [1], and I don't see _how_ to detect the
renames in this case, and what would I be actually doing git-ls-tree for
when I've already detected the rename. Based on [1], I'd be doing
git-ls-tree merely to detect that a file _disappeared_ in the first
place, I have to do other stuff to detect the renames themselves.
Dear diary, on Sun, Mar 26, 2006 at 09:35:02AM CEST, I got a letter
where Ryan Anderson [off-list ref] said that...
A simple example is the first loop in git-annotate.perl. (Which was
basically written by Linus, I just translated it from a
shell/pseudo-code example into Perl)
Thanks for the hint. Unfortunately, this is precisely the thing I want
to avoid, that is essentially reimplementing part of git-rev-list - to
do something good, I would have to do my own toposort and merge by date
between parallel lines. OTOH, I might just construct a large revlist
commandline specifying all the segments I'm interested in and see what
happens when I run that.
Besides, doing it in shell would be pretty ugly job (forcing me to
finally rewrite it in perl is not a bad thing but that'd be a somewhat
larger project since I share various common routines with other cg
tools, etc).
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
Right now I am having amnesia and deja-vu at the same time. I think
I have forgotten this before.
From: Fredrik Kuivinen <hidden> Date: 2016-06-15 22:42:22
On Sun, Mar 26, 2006 at 12:07:17PM +0200, Petr Baudis wrote:
Dear diary, on Sun, Mar 26, 2006 at 05:19:50AM CEST, I got a letter
where Linus Torvalds [off-list ref] said that...
quoted
On Sun, 26 Mar 2006, Petr Baudis wrote:
quoted
In [1], Linus suggests a non-core solution. Unfortunately, it doesn't
fly - it requires at least two git-ls-tree calls per revision which
would bog things down awfully (to roughly half of the original speed).
No it doesn't. It requires one git-ls-tree WHEN SOMETHING IS RENAMED.
In other words, basically never.
Huh? I don't see that now (and caps don't help me see it better). That's
certainly not what is in [1], and I don't see _how_ to detect the
renames in this case, and what would I be actually doing git-ls-tree for
when I've already detected the rename. Based on [1], I'd be doing
git-ls-tree merely to detect that a file _disappeared_ in the first
place, I have to do other stuff to detect the renames themselves.
Dear diary, on Sun, Mar 26, 2006 at 09:35:02AM CEST, I got a letter
where Ryan Anderson [off-list ref] said that...
quoted
A simple example is the first loop in git-annotate.perl. (Which was
basically written by Linus, I just translated it from a
shell/pseudo-code example into Perl)
Thanks for the hint. Unfortunately, this is precisely the thing I want
to avoid, that is essentially reimplementing part of git-rev-list - to
do something good, I would have to do my own toposort and merge by date
between parallel lines. OTOH, I might just construct a large revlist
commandline specifying all the segments I'm interested in and see what
happens when I run that.
Besides, doing it in shell would be pretty ugly job (forcing me to
finally rewrite it in perl is not a bad thing but that'd be a somewhat
larger project since I share various common routines with other cg
tools, etc).
If you decide to modify rev-list to do rename tracking you might want
to have a look at how this is done in blame.c. git-blame only tracks
one file (since that is what it needs) but I think it should be
possible to track multiple files with a similar approach.
- Fredrik
Huh? I don't see that now (and caps don't help me see it better). That's
certainly not what is in [1], and I don't see _how_ to detect the
renames in this case, and what would I be actually doing git-ls-tree for
when I've already detected the rename. Based on [1], I'd be doing
git-ls-tree merely to detect that a file _disappeared_ in the first
place, I have to do other stuff to detect the renames themselves.
No, the point is that "git-rev-list" already does all of [1] in the core.
If you do
git-rev-list --parents --remove-empty $REV -- $filename
then you'll get the whole history for that filename. When it ends, you
know the file went away, and then you do basically _one_ "where the hell
did it go" thing.
And yes, it's not git-ls-tree (unless you only want to follow pure
renames), it's actually one "git-diff-tree -M $lastrev". Then you just
continue with the new filename (and do another "git-rev-list" until you
hit the next rename).
Linus
From: Petr Baudis <hidden> Date: 2016-06-15 22:42:22
Dear diary, on Sun, Mar 26, 2006 at 06:33:13PM CEST, I got a letter
where Linus Torvalds [off-list ref] said that...
If you do
git-rev-list --parents --remove-empty $REV -- $filename
then you'll get the whole history for that filename. When it ends, you
know the file went away, and then you do basically _one_ "where the hell
did it go" thing.
And yes, it's not git-ls-tree (unless you only want to follow pure
renames), it's actually one "git-diff-tree -M $lastrev". Then you just
continue with the new filename (and do another "git-rev-list" until you
hit the next rename).
I wrote a long rant but then it all suddenly fit together and I have now
an idea how to implement it reasonably elegantly.
So only a bugreport remains:
My current target is to support this tree (letters are filenames,
numbers are commit ids; I'll translate any git output to those digits):
2 4
b -- d
1 / \ 6
a d
\ 3 5 /
c -- d
With the commits created in the numerical order (so log shows
1,2,3,4,5,6, and my target is cg-log d showing the same output). If
anyone wants the sample history, it's at
http://pasky.or.cz/~xpasky/renametree1.git/
Curiously, git-rev-list does something totally strange when trying to
list per-file history at this point:
$ git-rev-list HEAD -- d
4
Huh? (It should list 6, 5, 4 instead.)
I worked it around by recording a change in d in the merge 6:
http://pasky.or.cz/~xpasky/renametree2.git/
$ git-rev-list --parents --remove-empty HEAD -- d
6 4 5
5
4
Which is the expected output.
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
Right now I am having amnesia and deja-vu at the same time. I think
I have forgotten this before.
From: Petr Baudis <hidden> Date: 2016-06-15 22:42:22
Dear diary, on Sun, Mar 26, 2006 at 09:14:45PM CEST, I got a letter
where Petr Baudis [off-list ref] said that...
Curiously, git-rev-list does something totally strange when trying to
list per-file history at this point:
$ git-rev-list HEAD -- d
4
Huh? (It should list 6, 5, 4 instead.)
Obviously not 6 since the file was not changed in that revision, but I'd
still expect it to list 5.
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
Right now I am having amnesia and deja-vu at the same time. I think
I have forgotten this before.
My current target is to support this tree (letters are filenames,
numbers are commit ids; I'll translate any git output to those digits):
2 4
b -- d
1 / \ 6
a d
\ 3 5 /
c -- d
Yeah, the problem with this is that you need to track separate names
across separate points. However:
Curiously, git-rev-list does something totally strange when trying to
list per-file history at this point:
$ git-rev-list HEAD -- d
4
Huh? (It should list 6, 5, 4 instead.)
What it does is list the points where file "d" _changed_.
"d" did not change in 6 - it had a parent commit (4) where "d" had the
same contents (in fact, it likely had _two_ parents where it had the same
contents, but git will pick the first one). So commit "6" is
uninteresting, and commit "5" will never even be looked at, since we
decided that the history of "d" comes from the first parent with the same
contents.
So then it lists "4", because file "d" really did change in that commit
(it went away).
Now you need to look at "4" and find the rename (which gives you 2) and
then from there you do rename detection and get (1), and as a result your
change history should end up being
(1)a -> (2)b -> (4)d (-> 6(d) which was your start point)
which is correct (now, there are other histories _too_ that get us to the
same point, but the one you found this way was _a_ history).
I worked it around by recording a change in d in the merge 6:
http://pasky.or.cz/~xpasky/renametree2.git/
$ git-rev-list --parents --remove-empty HEAD -- d
6 4 5
5
4
Which is the expected output.
No, it's the expected output just because you expected merges to always
show up. Merges get ignored if any of the parents have the same content
already.
Linus
From: Petr Baudis <hidden> Date: 2016-06-15 22:42:22
Dear diary, on Mon, Mar 27, 2006 at 12:22:04AM CEST, I got a letter
where Linus Torvalds [off-list ref] said that...
So commit "6" is uninteresting, and commit "5" will never even be
looked at, since we decided that the history of "d" comes from the
first parent with the same contents.
And this is the thing I have a problem with - this does not make much
sense to me, why can't we just follow all parents instead of arbitrarily
choosing one of them?
which is correct (now, there are other histories _too_ that get us to the
same point, but the one you found this way was _a_ history).
Ok, in that case I want the _full_ history. :-)
No, it's the expected output just because you expected merges to always
show up. Merges get ignored if any of the parents have the same content
already.
Eek. Can I avoid that? What was the reason for choosing this behavior?
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
Right now I am having amnesia and deja-vu at the same time. I think
I have forgotten this before.
Dear diary, on Mon, Mar 27, 2006 at 12:22:04AM CEST, I got a letter
where Linus Torvalds [off-list ref] said that...
quoted
So commit "6" is uninteresting, and commit "5" will never even be
looked at, since we decided that the history of "d" comes from the
first parent with the same contents.
And this is the thing I have a problem with - this does not make much
sense to me, why can't we just follow all parents instead of arbitrarily
choosing one of them?
Sure, you can. It's _usually_ a huge waste of time, though. Why would you
want to do more work than you need, since clearly the other parent was
_not_ interesting from the standpoint of the question "where did this
content come from"?
quoted
No, it's the expected output just because you expected merges to always
show up. Merges get ignored if any of the parents have the same content
already.
Eek. Can I avoid that? What was the reason for choosing this behavior?
Huge efficiency gains.
Lookie here. Do
gitk -- rev-list.c
on the git archive with the current git-rev-list, and with your hacked-up
version.
And tell me my version isn't a hell of a lot better. Because, I guarantee
you, it is. We're just not _interested_ in all those merges that didn't
actually make any difference.
Read up on what modern neuro-science thinks about the human brain, and
what a lot of it is about. It's about ignoring irrelevant information.
The ability to throw stuff out that isn't interesting is the _real_ basis
of true intelligence. I'd rather have git do the _intelligent_ history,
than show history that isn't relevant and workign harder doing so.
Linus
From: Petr Baudis <hidden> Date: 2016-06-15 22:42:22
Dear diary, on Sun, Mar 26, 2006 at 09:14:45PM CEST, I got a letter
where Petr Baudis [off-list ref] said that...
Dear diary, on Sun, Mar 26, 2006 at 06:33:13PM CEST, I got a letter
where Linus Torvalds [off-list ref] said that...
quoted
If you do
git-rev-list --parents --remove-empty $REV -- $filename
then you'll get the whole history for that filename. When it ends, you
know the file went away, and then you do basically _one_ "where the hell
did it go" thing.
And yes, it's not git-ls-tree (unless you only want to follow pure
renames), it's actually one "git-diff-tree -M $lastrev". Then you just
continue with the new filename (and do another "git-rev-list" until you
hit the next rename).
I wrote a long rant but then it all suddenly fit together and I have now
an idea how to implement it reasonably elegantly.
So, this is what I have. Testing (I've gave it very little of that) and
thoughts welcome. It is probably pretty efficient, at least in terms of
fork()s it does only 2*N of them where N is the number of commits
containing interesting renames. Actually, this should be even possible
to reduce to N+1 if you do a single git-diff-tree call and multiplex
different git-rev-lists to it, but I'm too tired to do the trickery now.
It has 'cg' in the name but depends on no Cogito stuff; it should be in
fact possible to trivially put it to git-whatchanged in place of the
final pipeline (not that I'd be suggesting this to be done universally,
but perhaps git-whatchanged -f ...?). There are three downsides in this
regard:
(i) No -c support. I need the separate deltas coming out from
git-diff-tree but I think I can join them together pretty easily on my
own, except that I have problems with -c (see
[off-list ref]) so I'm not sure how exactly is it
supposed to behave.
(ii) Only --pretty=raw output. It shouldn't be hard to add the
reformatting code, but I'm personally not going to use it and kind of
lazy, so I'll let someone else do that, I guess. :-)
(iii) Raw deltas required. -p parsing support would be certainly useful
and possible, but see (ii).
To quickly see what it does, you can try it e.g. on the git-log.sh file
in the Git repository.
Thoughts? Opinions? Bugs? Patches?
Signed-off-by: Petr Baudis <redacted>
@@ -0,0 +1,246 @@+#!/usr/bin/env perl+#+# git-rev-list | git-diff-tree --stdin following renames+# Copyright (c) Petr Baudis, 2006+# Uses bits of git-annotate.perl by Ryan Anderson.+#+# This script will efficiently show output as of the+#+# git-rev-list --remove-empty ARGS -- FILE... |+# git-diff-tree -M -r -m --stdin --pretty=raw ARGS+#+# pipeline, except that it follows renames of individual files listed+# in the FILE... set.+#+# Usage:+#+# cg-Xfollowrenames revlistargs -- difftreeargs -- revs -- files++# TODO: Does not work on multiple files properly yet - most probably+# (I didn't test it!). We want git-rev-list to stop traversing the history+# when _any_ file disappears while now it probably stops traversing when+# _all_ files disappear.++use warnings;+use strict;++$| = 1;++our (@revlist_args, @difftree_args, @revs, @files);++{ # Load arguments+ my @argp = (\@revlist_args, \@difftree_args, \@revs, \@files);+ my $argi = 0;+ for my $arg (@ARGV) {+ if ($arg eq '--' and $argi < $#argp) {+ $argi++;+ next;+ }+ push(@{$argp[$argi]}, $arg);+ }+}+++# The heads we watch (sorted by commit time)+our @heads;+# Each head is: {+# # Persistent for the whole line of development:+# pipe => $pipe,+# files => \@files, # to watch for+#+# id => $sha1, # useful actually only for debugging+# time => $timestamp,+# str => $prettyoutput,+# parents => \@sha1s,+#+# # When the commit is processed, spawn these extra heads:+# recurse => {$sha1id => \@files, ...},+# }++# To avoid printing duplicate commits+# FIXME: Currently, we will not handle merge commits properly since+# we hit them multiple times.+our %commits;+++sub open_pipe($@) {+ my ($stdin, @execlist) = @_;++ my $pid = open my $kid, "-|";+ defined $pid or die "Cannot fork: $!";++ unless ($pid) {+ if (defined $stdin) {+ open STDIN, "<&", $stdin or die "Cannot dup(): $!";+ }+ exec @execlist;+ die "Cannot exec @execlist: $!";+ }++ return $kid;+}++sub revlist($@) {+ my ($rev, @files) = @_;+ open_pipe(undef, "git-rev-list", "--remove-empty",+ @revlist_args, $rev, "--", @files)+ or die "Failed to exec git-rev-list: $!";+}++sub difftree($) {+ my ($revlist) = @_;+ open_pipe($revlist, "git-diff-tree", "-r", "-m", "--stdin", "-M",+ "--pretty=raw", @difftree_args)+ or die "Failed to exec git-diff-tree: $!";+}++sub revdiffpipe($@) {+ my ($rev, @files) = @_;+ my $pipe = difftree(revlist($rev, @files));+}+++sub read_commit($$) {+ my ($head, $tolerant) = @_;+ my $pipe = $head->{'pipe'};+ my $against;+ my @oldset = @{$head->{'files'}};+ my @newset;+ my $rename;++ # Load header+ while (my $line = <$pipe>) {+ $head->{'str'} .= $line;+ chomp $line;+ $line eq '' and goto header_loaded;++ if ($line =~ /^diff-tree (\S+) \(from (root|\S+)\)/) {+ $head->{'id'} = $1;+ if (not $tolerant and $commits{$1}++) {+ close $pipe;+ return undef;+ }+ # The 'root' case is harmless since there'll be no renames.+ $against = $2;+ } elsif ($line =~ /^parent (\S+)/) {+ push (@{$head->{'parents'}}, $1);+ } elsif ($line =~ /^committer .*?> (\d+)/) {+ $head->{'time'} = $1;+ }+ }+ return undef;+header_loaded:++ # Load message+ while (my $line = <$pipe>) {+ $head->{'str'} .= $line;+ chomp $line;+ $line eq '' and goto message_loaded;+ }+ return undef;+message_loaded:++ # Load delta+ while (my $line = <$pipe>) {+ $head->{'str'} .= $line;+ chomp $line;+ $line eq '' and goto delta_loaded;++ $line =~ /^:/ or return undef;+ my ($info, $newfile, $oldfile) = split("\t", $line);+ if ($info =~ /[RC]\d*$/) {+ # Behold, a rename!+ # (Or a copy, it's all the same for us.)+ my $i;+ for ($i = 0; $i <= $#oldset; $i++) {+ $oldfile eq $oldset[$i] or next;+ $rename = 1;+ splice(@oldset, $i, 1);+ push(@newset, $newfile);+ last;+ }+ # In case of multiple candidates, follow+ # all of them:+ # (TODO: This might be a policy decision+ # best left on the user.)+ if ($i > $#oldset and grep { $oldfile eq $_ } @newset) {+ $rename = 1;+ push(@newset, $newfile);+ }+ } elsif ($info =~ /D$/) {+ # Not weeding out deleted files might cause bizarre+ # results when following multiple files since+ # git-rev-list weeds them out too (probably?).+ @oldset = grep { $newfile ne $_ } @oldset;+ @{$head->{'files'}} = grep { $newfile ne $_ } @{$head->{'files'}};+ }+ }+ $head->{'str'} .= "\n";+delta_loaded:++ if ($rename) {+ $head->{'recurse'}->{$against} = [@newset, @oldset];+ }+ return 1;+}++sub load_commit($) {+ my ($head) = @_;+ $head->{'time'} = undef;+ $head->{'str'} = '';+ $head->{'parents'} = ();++ read_commit($head, 0) or return undef;++ # In case there was a merge, the commit will be multiple times+ # here, each time with a different delta section. Read them all.+ for (1 .. $#{$head->{'parents'}}) { # stupid vim syntax highlighting+ read_commit($head, 1) or return undef;+ }++ return 1;+}+++# Add head at the proper position+sub add_head($) {+ my ($head) = @_;+ my $i;+ for ($i = 0; $i <= $#heads; $i++) {+ last if ($head->{'time'} > $heads[$i]->{'time'})+ }+ splice(@heads, $i, 0, $head);+}++# Create new head+sub init_head($@) {+ my ($rev, @files) = @_;+ my $head = { files => \@files, 'pipe' => revdiffpipe($rev, @files) };+ load_commit($head) or return;+ add_head($head);+}++++{ # Seed the heads list+ for my $rev (@revs) {+ init_head($rev, @files);+ }+}++# Process the heads+{+ while (@heads) {+ my $head = splice(@heads, 0, 1);++ print $head->{'str'};++ foreach my $parent (keys %{$head->{'recurse'}}) {+ init_head($parent, @{$head->{'recurse'}->{$parent}});+ }+ $head->{'recurse'} = undef;++ load_commit($head) or next;+ add_head($head);+ }+}
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
Right now I am having amnesia and deja-vu at the same time. I think
I have forgotten this before.
From: Petr Baudis <hidden> Date: 2016-06-15 22:42:22
Dear diary, on Mon, Mar 27, 2006 at 01:26:49AM CEST, I got a letter
where Petr Baudis [off-list ref] said that...
To quickly see what it does, you can try it e.g. on the git-log.sh file
in the Git repository.
By the way, the cg-log in master uses it now to automagically follow
file renames (in case you call it per-file like cg-log FILENAME). If you
hate it, you can prevent it by cg-log --no-renames (cg-log -R).
Looks pretty slick.
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
Right now I am having amnesia and deja-vu at the same time. I think
I have forgotten this before.