+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>)
+ # without $precheck, will crash if $x does not exist, so don't do that;
+ # instead pass '' to get ().
+ my ($x, $precheck, $recurse) = @_;
+
+ return () if !length $x;
+
+ if ($precheck) {
+ my ($type, $dummy) = git_cat_file $x, [qw(tree missing)];
+ return () if $type eq 'missing';
+ }
+
+ confess "get_tree needs object not $x ?" unless $x =~ m{^[0-9a-f]+\:};
+
+ our (@get_tree_memo, %get_tree_memo);
+ my $memo = $get_tree_memo{$x};
+ return @$memo if $memo;
+
+ local $Debian::Dgit::debugcmd_when_debuglevel = 3;
+ my @l;
+ my @cmd = (qw(git ls-tree -z --full-tree));
+ push @cmd, qw(-r) if $recurse;
+ push @cmd, qw(--), $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;
+ printdebug "trees_diff_walk(..$x,$y..) ".Dumper(\@x,\@y)
+ if $debuglevel >= 3;
+ 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='';
+ printdebug "trees_diff_walk $cmp : @{ $x[0]//[] } | @{ $y[0]//[] }\n"
+ if $debuglevel >= 3;
+ ($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);
+ }
+}
+