git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Pierre Habouzit <madcoder@debian.org>
Date
Jan 6, 2009, 11:39 UTC
Message-ID
<20090106113943.GA28659@artemis.corp>
In-Reply-To
<20090106111712.GB30766@artemis.corp>
On Tue, Jan 06, 2009 at 11:17:12AM +0000, Pierre Habouzit wrote:
Show 7 quoted lines
> 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).

Show 12 quoted lines
> 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?
Show 9 quoted lines
> 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


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


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);
Previous: Pierre HabouzitNext: Johannes Schindelin
Message 39 of 67 in “libxdiff and patience diff”
  1. Pierre HabouzitNov 4, 2008
  2. Davide LibenziNov 4, 2008
  3. Pierre HabouzitNov 4, 2008
  4. Johannes SchindelinNov 4, 2008
  5. Pierre HabouzitNov 4, 2008
  6. Johannes SchindelinNov 4, 2008
  7. Pierre HabouzitNov 4, 2008
  8. Johannes SchindelinNov 4, 2008
  9. Pierre HabouzitNov 4, 2008
  10. 0/3 Teach Git about the patience diff algorithmJohannes Schindelin, Jan 1, 2009
  11. 1/3 Implement the patience diff algorithmJohannes Schindelin, Jan 1, 2009
  12. 2/3 Introduce the diff option '--patience'Johannes Schindelin, Jan 1, 2009
  13. 3/3 bash completions: Add the --patience optionJohannes Schindelin, Jan 1, 2009
  14. Linus TorvaldsJan 1, 2009
  15. Linus TorvaldsJan 1, 2009
  16. Johannes SchindelinJan 2, 2009
  17. Linus TorvaldsJan 2, 2009
  18. Johannes SchindelinJan 2, 2009
  19. Jeff KingJan 2, 2009
  20. 1/3 Implement the patience diff algorithmJohannes Schindelin, Jan 2, 2009
  21. Johannes SchindelinJan 2, 2009
  22. Adeodato SimóJan 1, 2009
  23. Linus TorvaldsJan 2, 2009
  24. Clemens BuchacherJan 2, 2009
  25. Clemens BuchacherJan 2, 2009
  26. Linus TorvaldsJan 2, 2009
  27. Johannes SchindelinJan 2, 2009
  28. Linus TorvaldsJan 2, 2009
  29. Johannes SchindelinJan 2, 2009
  30. Jeff KingJan 2, 2009
  31. Jeff KingJan 2, 2009
  32. Jeff KingJan 2, 2009
  33. Linus TorvaldsJan 2, 2009
  34. Bazaar's patience diff as GIT_EXTERNAL_DIFFAdeodato Simó, Jan 3, 2009
  35. Johannes SchindelinJan 2, 2009
  36. Junio C HamanoJan 2, 2009
  37. Adeodato SimóJan 2, 2009
  38. Pierre HabouzitJan 6, 2009
  39. Pierre HabouzitJan 6, 2009
  40. Johannes SchindelinJan 6, 2009
  41. Pierre HabouzitJan 7, 2009
  42. Johannes SchindelinJan 7, 2009
  43. 1/3 Implement the patience diff algorithmJohannes Schindelin, Jan 7, 2009
  44. Davide LibenziJan 7, 2009
  45. Johannes SchindelinJan 7, 2009
  46. Davide LibenziJan 7, 2009
  47. Johannes SchindelinJan 7, 2009
  48. Linus TorvaldsJan 7, 2009
  49. Johannes SchindelinJan 7, 2009
  50. Davide LibenziJan 7, 2009
  51. Sam VilainJan 7, 2009
  52. Linus TorvaldsJan 7, 2009
  53. Sam VilainJan 8, 2009
  54. Johannes SchindelinJan 7, 2009
  55. Junio C HamanoJan 7, 2009
  56. Johannes SchindelinJan 7, 2009
  57. Pierre HabouzitJan 7, 2009
  58. Johannes SchindelinJan 7, 2009
  59. Adeodato SimóJan 8, 2009
  60. Adeodato SimóJan 8, 2009
  61. Junio C HamanoJan 9, 2009
  62. Johannes SchindelinJan 9, 2009
  63. Adeodato SimóJan 9, 2009
  64. Linus TorvaldsJan 9, 2009
  65. Linus TorvaldsJan 9, 2009
  66. Junio C HamanoJan 9, 2009
  67. Johannes SchindelinJan 10, 2009

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.