git-debrebase: Provide new get_tree and trees_diff_walk

These are ways to avoid calling git-diff-tree, which is very slow even
with --name-only --no-renames and without recursion.  I think it is
doing all the work to make nice actual diffs, and then throwing them
away.

Two calls to git-ls-tree is about 20x faster than git-diff-tree
on the Linux kernel, for example.

No functional change in this commit, since no callers yet.

Signed-off-by: Ian Jackson <ijackson@chiark.greenend.org.uk>

1 files changed, 56 insertions, 0 deletions

diff --git a/git-debrebase b/git-debrebase
index 5573824..d04f2a3 100755
--- a/git-debrebase
+++ b/git-debrebase
@@ -183,6 +183,62 @@ sub run_deferred_updates ($) {
     @deferred_update_messages = ();
 }
 
+sub get_tree ($) {
+    # tree object name => ([ $name, $info ], ...)
+    # where $name is the sort key, ie has / at end for subtrees
+    # $info is the LHS from git-ls-tree (<mode> <type> <hash>)
+    # will crash if $x does not exist, so don't do that
+    my ($x) = @_;
+    our (@get_tree_memo, %get_tree_memo);
+    my $memo = $get_tree_memo{$x};
+    return @$memo if $memo;
+
+    local $debugcmd_when_debuglevel = 3;
+    my @l;
+    my @cmd = (qw(git ls-tree -z --full-tree --), $x);
+    my $o = cmdoutput @cmd;
+    $o =~ s/\0$//s;
+    my $last = '';
+    foreach my $l (split /\0/, $o) {
+	my ($i, $n) = split /\t/, $l, 2;
+	$n .= '/' if $i =~ m/^\d+ tree /;
+	push @l, [ $n, $i ];
+	confess "$x need $last < $n ?" unless $last lt $n;
+    }
+    $get_tree_memo{$x} = \@l;
+    push @get_tree_memo, $x;
+    if (@get_tree_memo > 10) {
+	delete $get_tree_memo{ shift @get_tree_memo };
+    }
+    return @l;
+}
+
+sub trees_diff_walk ($$$;$) {
+    # trees_diff_walk [$all,] $x, $y, sub {... }
+    # calls sub->($name, $ix, $iy) for each difference (with $all, each name)
+    # $x and $y are as for get_tree
+    # where $name, $ix, $iy are $name and $info from get_tree
+    my $all = shift @_ if @_>=4;
+    my ($x,$y,$call) = @_;
+    return if !$all and $x eq $y;
+    my @x = get_tree $x;
+    my @y = get_tree $y;
+    while (@x || @y) {
+	my $cmp = !@x       <=> !@y          # eg @y empty? $cmp=-1, use x
+ 	     ||    $x[0][0] cmp  $y[0][0];   # eg, x lt y ? $cmp=-1, use x
+	my ($n, $ix, $iy);                   # all same? $cmp=0, use both
+	$ix=$iy='';
+	($n, $ix) = @{ shift @x } if $cmp <= 0;
+	($n, $iy) = @{ shift @y } if $cmp >= 0;
+	next if !$all and $ix eq $iy;
+	printdebug sprintf
+	    "trees_diff_walk(%d,'%s','%s') call('%s','%s','%s')\n",
+	    !!$all,$x,$y, $n,$ix,$iy
+	    if $debuglevel >= 2;
+	$call->($n, $ix, $iy);
+    }
+}
+
 sub get_differs ($$) {
     my ($x,$y) = @_;
     # This resembles quiltify_trees_differ, in dgit, a bit.