Re: [PATCH 0/3] Teach Git about the patience diff algorithm

[Pierre Habouzit <madcoder@debian.org>]

[-- Attachment #1.1: Type: text/plain, Size: 2784 bytes --]

On Tue, Jan 06, 2009 at 11:17:12AM +0000, Pierre Habouzit wrote:
> On jeu, jan 01, 2009 at 04:38:09 +0000, Johannes Schindelin wrote:
> > 
> > Nothing fancy, really, just a straight-forward implementation of the
> > heavily under-documented and under-analyzed paience diff algorithm.
> 
> Btw, what is the status of this series ? I see it neither in pu nor in
> next. And I would gladly see it included in git.

Johannes: I've not had time to investigate, but when finding what I
present in the end of this mail, I ran:

    git log -p > log-normal
    git log -p --patience > log-patience

in git.git.

I saw that patience diff is slower than normal diff, which is expected,
but I had to kill the latter command because it leaks like hell. I've
not investigated yet (And yes I'm running your latest posted series).

> On jeu, jan 01, 2009 at 07:45:21 +0000, Linus Torvalds wrote:
> > On Thu, 1 Jan 2009, Johannes Schindelin wrote:
> > > 
> > > Nothing fancy, really, just a straight-forward implementation of the
> > > heavily under-documented and under-analyzed paience diff algorithm.
> > 
> > Exactly because the patience diff is so under-documented, could you 
> > perhaps give a few examples of how it differs in the result, and why it's 
> > so wonderful? Yes, yes, I can google, and no, no, nothing useful shows up 
> > except for *totally* content-free fanboisms. 
> > 
> > So could we have some actual real data on it?

> I've checked in many projects I have under git, the differences between
> git log -p and git log -p --patience. The patience algorithm is really
> really more readable with it involves code moves with changes in the
> moved sections. If the section you move across is smaller than the moved
> ones, the patience algorithm will show the moved code as removed where
> it was and added where it now is, changes included. The current diff
> will rather move the smaller invariend section you move across and
> present mangled diffs involving the function prototypes making it less
> than readable.

Actually git.git has a canonical example of this in 214a34d22.

For those not having the --patience diff applied locally, attached are
the two patches git show / git show --patience give. It's of course a
matter of taste, but I like the patience version a lot more.

I'm also curious to see what a merge conflict with such a move would
look like (e.g. inverting some of the added arguments to the factorized
function of 214a34d22 or something similar). I'm somehow convinced that
it would generate a nicer conflict somehow.

-- 
·O·  Pierre Habouzit
··O                                                madcoder@debian.org
OOO                                                http://www.madism.org

[-- Attachment #1.2: 214a34d22.normal --]
[-- Type: text/plain, Size: 2323 bytes --]

commit 214a34d22ec59ec7e1166772f06ecf8799f96c96
Author: Florian Weimer <fw@deneb.enyo.de>
Date:   Sun Aug 31 17:45:04 2008 +0200

    git-svn: Introduce SVN::Git::Editor::_chg_file_get_blob
    
    Signed-off-by: Florian Weimer <fw@deneb.enyo.de>
    Acked-by: Eric Wong <normalperson@yhbt.net>

diff --git a/git-svn.perl b/git-svn.perl
index 0479f41..2c3e13f 100755
--- a/git-svn.perl
+++ b/git-svn.perl
@@ -3663,28 +3663,35 @@ sub change_file_prop {
 	$self->SUPER::change_file_prop($fbat, $pname, $pval, $self->{pool});
 }
 
-sub chg_file {
-	my ($self, $fbat, $m) = @_;
-	if ($m->{mode_b} =~ /755$/ && $m->{mode_a} !~ /755$/) {
-		$self->change_file_prop($fbat,'svn:executable','*');
-	} elsif ($m->{mode_b} !~ /755$/ && $m->{mode_a} =~ /755$/) {
-		$self->change_file_prop($fbat,'svn:executable',undef);
-	}
-	my $fh = Git::temp_acquire('git_blob');
-	if ($m->{mode_b} =~ /^120/) {
+sub _chg_file_get_blob ($$$$) {
+	my ($self, $fbat, $m, $which) = @_;
+	my $fh = Git::temp_acquire("git_blob_$which");
+	if ($m->{"mode_$which"} =~ /^120/) {
 		print $fh 'link ' or croak $!;
 		$self->change_file_prop($fbat,'svn:special','*');
-	} elsif ($m->{mode_a} =~ /^120/ && $m->{mode_b} !~ /^120/) {
+	} elsif ($m->{mode_a} =~ /^120/ && $m->{"mode_$which"} !~ /^120/) {
 		$self->change_file_prop($fbat,'svn:special',undef);
 	}
-	my $size = $::_repository->cat_blob($m->{sha1_b}, $fh);
-	croak "Failed to read object $m->{sha1_b}" if ($size < 0);
+	my $blob = $m->{"sha1_$which"};
+	return ($fh,) if ($blob =~ /^0{40}$/);
+	my $size = $::_repository->cat_blob($blob, $fh);
+	croak "Failed to read object $blob" if ($size < 0);
 	$fh->flush == 0 or croak $!;
 	seek $fh, 0, 0 or croak $!;
 
 	my $exp = ::md5sum($fh);
 	seek $fh, 0, 0 or croak $!;
+	return ($fh, $exp);
+}
 
+sub chg_file {
+	my ($self, $fbat, $m) = @_;
+	if ($m->{mode_b} =~ /755$/ && $m->{mode_a} !~ /755$/) {
+		$self->change_file_prop($fbat,'svn:executable','*');
+	} elsif ($m->{mode_b} !~ /755$/ && $m->{mode_a} =~ /755$/) {
+		$self->change_file_prop($fbat,'svn:executable',undef);
+	}
+	my ($fh, $exp) = _chg_file_get_blob $self, $fbat, $m, 'b';
 	my $pool = SVN::Pool->new;
 	my $atd = $self->apply_textdelta($fbat, undef, $pool);
 	my $got = SVN::TxDelta::send_stream($fh, @$atd, $pool);

[-- Attachment #1.3: 214a34d22.patience --]
[-- Type: text/plain, Size: 2290 bytes --]

commit 214a34d22ec59ec7e1166772f06ecf8799f96c96
Author: Florian Weimer <fw@deneb.enyo.de>
Date:   Sun Aug 31 17:45:04 2008 +0200

    git-svn: Introduce SVN::Git::Editor::_chg_file_get_blob
    
    Signed-off-by: Florian Weimer <fw@deneb.enyo.de>
    Acked-by: Eric Wong <normalperson@yhbt.net>

diff --git a/git-svn.perl b/git-svn.perl
index 0479f41..2c3e13f 100755
--- a/git-svn.perl
+++ b/git-svn.perl
@@ -3663,6 +3663,27 @@ sub change_file_prop {
 	$self->SUPER::change_file_prop($fbat, $pname, $pval, $self->{pool});
 }
 
+sub _chg_file_get_blob ($$$$) {
+	my ($self, $fbat, $m, $which) = @_;
+	my $fh = Git::temp_acquire("git_blob_$which");
+	if ($m->{"mode_$which"} =~ /^120/) {
+		print $fh 'link ' or croak $!;
+		$self->change_file_prop($fbat,'svn:special','*');
+	} elsif ($m->{mode_a} =~ /^120/ && $m->{"mode_$which"} !~ /^120/) {
+		$self->change_file_prop($fbat,'svn:special',undef);
+	}
+	my $blob = $m->{"sha1_$which"};
+	return ($fh,) if ($blob =~ /^0{40}$/);
+	my $size = $::_repository->cat_blob($blob, $fh);
+	croak "Failed to read object $blob" if ($size < 0);
+	$fh->flush == 0 or croak $!;
+	seek $fh, 0, 0 or croak $!;
+
+	my $exp = ::md5sum($fh);
+	seek $fh, 0, 0 or croak $!;
+	return ($fh, $exp);
+}
+
 sub chg_file {
 	my ($self, $fbat, $m) = @_;
 	if ($m->{mode_b} =~ /755$/ && $m->{mode_a} !~ /755$/) {
@@ -3670,21 +3691,7 @@ sub chg_file {
 	} elsif ($m->{mode_b} !~ /755$/ && $m->{mode_a} =~ /755$/) {
 		$self->change_file_prop($fbat,'svn:executable',undef);
 	}
-	my $fh = Git::temp_acquire('git_blob');
-	if ($m->{mode_b} =~ /^120/) {
-		print $fh 'link ' or croak $!;
-		$self->change_file_prop($fbat,'svn:special','*');
-	} elsif ($m->{mode_a} =~ /^120/ && $m->{mode_b} !~ /^120/) {
-		$self->change_file_prop($fbat,'svn:special',undef);
-	}
-	my $size = $::_repository->cat_blob($m->{sha1_b}, $fh);
-	croak "Failed to read object $m->{sha1_b}" if ($size < 0);
-	$fh->flush == 0 or croak $!;
-	seek $fh, 0, 0 or croak $!;
-
-	my $exp = ::md5sum($fh);
-	seek $fh, 0, 0 or croak $!;
-
+	my ($fh, $exp) = _chg_file_get_blob $self, $fbat, $m, 'b';
 	my $pool = SVN::Pool->new;
 	my $atd = $self->apply_textdelta($fbat, undef, $pool);
 	my $got = SVN::TxDelta::send_stream($fh, @$atd, $pool);

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]