+}
+
+sub quiltify_trees_differ ($$) {
+ my ($x,$y) = @_;
+ # returns 1 iff the two tree objects differ other than in debian/
+ local $/=undef;
+ my @cmd = (@git, qw(diff-tree --name-only -z), $x, $y);
+ my $diffs= cmdoutput @cmd;
+ foreach my $f (split /\0/, $diffs) {
+ next if $f eq 'debian';
+ return 1;
+ }
+ return 0;
+}
+
+sub quiltify_tree_sentinelfiles ($) {
+ # lists the `sentinel' files present in the tree
+ my ($x) = @_;
+ my $r = cmdoutput @git, qw(ls-tree --name-only), $x,
+ qw(-- debian/rules debian/control);
+ $r =~ s/\n/,/g;
+ return $r;
+}
+
+sub quiltify ($$) {
+ my ($clogp,$target) = @_;
+
+ # Quilt patchification algorithm
+ #
+ # We search backwards through the history of the main tree's HEAD
+ # (T) looking for a start commit S whose tree object is identical
+ # to to the patch tip tree (ie the tree corresponding to the
+ # current dpkg-committed patch series). For these purposes
+ # `identical' disregards anything in debian/ - this wrinkle is
+ # necessary because dpkg-source treates debian/ specially.
+ #
+ # We can only traverse edges where at most one of the ancestors'
+ # trees differs (in changes outside in debian/). And we cannot
+ # handle edges which change .pc/ or debian/patches. To avoid
+ # going down a rathole we avoid traversing edges which introduce
+ # debian/rules or debian/control. And we set a limit on the
+ # number of edges we are willing to look at.
+ #
+ # If we succeed, we walk forwards again. For each traversed edge
+ # PC (with P parent, C child) (starting with P=S and ending with
+ # C=T) to we do this:
+ # - git checkout C
+ # - dpkg-source --commit with a patch name and message derived from C
+ # After traversing PT, we git commit the changes which
+ # should be contained within debian/patches.
+
+ changedir '../fake';
+ mktree_in_ud_here();
+ rmtree '.pc';
+ runcmd @git, 'add', '.';
+ my $oldtiptree=git_write_tree();
+ changedir '../work';
+
+ # The search for the path S..T is breadth-first. We maintain a
+ # todo list containing search nodes. A search node identifies a
+ # commit, and looks something like this:
+ # $p = {
+ # Commit => $git_commit_id,
+ # Child => $c, # or undef if P=T
+ # Whynot => $reason_edge_PC_unsuitable, # in @nots only
+ # Nontrivial => true iff $p..$c has relevant changes
+ # };
+
+ my @todo;
+ my @nots;
+ my $sref_S;
+ my $max_work=100;
+ my %considered; # saves being exponential on some weird graphs
+
+ my $t_sentinels = quiltify_tree_sentinelfiles $target;
+
+ my $not = sub {
+ my ($search,$whynot) = @_;
+ printdebug " search NOT $search->{Commit} $whynot\n";
+ $search->{Whynot} = $whynot;
+ push @nots, $search;
+ no warnings qw(exiting);
+ next;
+ };
+
+ push @todo, {
+ Commit => $target,
+ };
+
+ while (@todo) {
+ my $c = shift @todo;
+ next if $considered{$c->{Commit}}++;
+
+ $not->($c, "maximum search space exceeded") if --$max_work <= 0;
+
+ printdebug "quiltify investigate $c->{Commit}\n";
+
+ # are we done?
+ if (!quiltify_trees_differ $c->{Commit}, $oldtiptree) {
+ printdebug " search finished hooray!\n";
+ $sref_S = $c;
+ last;
+ }
+
+ if ($quilt_mode eq 'nofix') {
+ fail "quilt fixup required but quilt mode is \`nofix'\n".
+ "HEAD commit $c->{Commit} differs from tree implied by ".
+ " debian/patches (tree object $oldtiptree)";
+ }
+ if ($quilt_mode eq 'smash') {
+ printdebug " search quitting smash\n";
+ last;
+ }
+
+ my $c_sentinels = quiltify_tree_sentinelfiles $c->{Commit};
+ $not->($c, "has $c_sentinels not $t_sentinels")
+ if $c_sentinels ne $t_sentinels;
+
+ my $commitdata = cmdoutput @git, qw(cat-file commit), $c->{Commit};
+ $commitdata =~ m/\n\n/;
+ $commitdata =~ $`;
+ my @parents = ($commitdata =~ m/^parent (\w+)$/gm);
+ @parents = map { { Commit => $_, Child => $c } } @parents;
+
+ $not->($c, "root commit") if !@parents;
+
+ foreach my $p (@parents) {
+ $p->{Nontrivial}= quiltify_trees_differ $p->{Commit},$c->{Commit};
+ }
+ my $ndiffers = grep { $_->{Nontrivial} } @parents;
+ $not->($c, "merge ($ndiffers nontrivial parents)") if $ndiffers > 1;
+
+ foreach my $p (@parents) {
+ printdebug "considering C=$c->{Commit} P=$p->{Commit}\n";
+
+ my @cmd= (@git, qw(diff-tree -r --name-only),
+ $p->{Commit},$c->{Commit}, qw(-- debian/patches .pc));
+ my $patchstackchange = cmdoutput @cmd;
+ if (length $patchstackchange) {
+ $patchstackchange =~ s/\n/,/g;
+ $not->($p, "changed $patchstackchange");
+ }
+
+ printdebug " search queue P=$p->{Commit} ",
+ ($p->{Nontrivial} ? "NT" : "triv"),"\n";
+ push @todo, $p;
+ }
+ }
+
+ if (!$sref_S) {
+ printdebug "quiltify want to smash\n";
+
+ my $abbrev = sub {
+ my $x = $_[0]{Commit};
+ $x =~ s/(.*?[0-9a-z]{8})[0-9a-z]*$/$1/;
+ return $;
+ };
+ my $reportnot = sub {
+ my ($notp) = @_;
+ my $s = $abbrev->($notp);
+ my $c = $notp->{Child};
+ $s .= "..".$abbrev->($c) if $c;
+ $s .= ": ".$notp->{Whynot};
+ return $s;
+ };
+ if ($quilt_mode eq 'linear') {
+ print STDERR "$us: quilt fixup cannot be linear. Stopped at:\n";
+ foreach my $notp (@nots) {
+ print STDERR "$us: ", $reportnot->($notp), "\n";
+ }
+ fail "quilt fixup naive history linearisation failed.\n".
+ "Use dpkg-source --commit by hand; or, --quilt=smash for one ugly patch";
+ } elsif ($quilt_mode eq 'smash') {
+ } elsif ($quilt_mode eq 'auto') {
+ progress "quilt fixup cannot be linear, smashing...";
+ } else {
+ die "$quilt_mode ?";
+ }
+
+ my $time = time;
+ my $ncommits = 3;
+ my $msg = cmdoutput @git, qw(log), "-n$ncommits";
+
+ quiltify_dpkg_commit "auto-$version-$target-$time",
+ (getfield $clogp, 'Maintainer'),
+ "Automatically generated patch ($clogp->{Version})\n".
+ "Last (up to) $ncommits git changes, FYI:\n\n". $msg;
+ return;
+ }
+
+ progress "quiltify linearisation planning successful, executing...";
+
+ for (my $p = $sref_S;
+ my $c = $p->{Child};
+ $p = $p->{Child}) {
+ printdebug "quiltify traverse $p->{Commit}..$c->{Commit}\n";
+ next unless $p->{Nontrivial};
+
+ my $cc = $c->{Commit};
+
+ my $commitdata = cmdoutput @git, qw(cat-file commit), $cc;
+ $commitdata =~ m/\n\n/ or die "$c ?";
+ $commitdata = $`;
+ my $msg = $'; #';
+ $commitdata =~ m/^author (.*) \d+ [-+0-9]+$/m or die "$cc ?";
+ my $author = $1;
+
+ $msg =~ s/^(.*)\n*/$1\n/ or die "$cc $msg ?";
+
+ my $title = $1;
+ my $patchname = $title;
+ $patchname =~ s/[.:]$//;
+ $patchname =~ y/ A-Z/-a-z/;
+ $patchname =~ y/-a-z0-9_.+=~//cd;
+ $patchname =~ s/^\W/x-$&/;
+ $patchname = substr($patchname,0,40);
+ my $index;
+ for ($index='';
+ stat "debian/patches/$patchname$index";
+ $index++) { }
+ $!==ENOENT or die "$patchname$index $!";
+
+ runcmd @git, qw(checkout -q), $cc;
+
+ # We use the tip's changelog so that dpkg-source doesn't
+ # produce complaining messages from dpkg-parsechangelog. None
+ # of the information dpkg-source gets from the changelog is
+ # actually relevant - it gets put into the original message
+ # which dpkg-source provides our stunt editor, and then
+ # overwritten.
+ runcmd @git, qw(checkout -q), $target, qw(debian/changelog);
+
+ quiltify_dpkg_commit "$patchname$index", $author, $msg,
+ "X-Dgit-Generated: $clogp->{Version} $cc\n";
+
+ runcmd @git, qw(checkout -q), $cc, qw(debian/changelog);
+ }
+
+ runcmd @git, qw(checkout -q master);
+}
+
+sub build_maybe_quilt_fixup () {
+ my $format=get_source_format;
+ return unless madformat $format;
+ # sigh
+
+ check_for_vendor_patches();
+
+ # Our objective is:
+ # - honour any existing .pc in case it has any strangeness
+ # - determine the git commit corresponding to the tip of
+ # the patch stack (if there is one)
+ # - if there is such a git commit, convert each subsequent
+ # git commit into a quilt patch with dpkg-source --commit
+ # - otherwise convert all the differences in the tree into
+ # a single git commit
+ #
+ # To do this we:
+
+ # Our git tree doesn't necessarily contain .pc. (Some versions of
+ # dgit would include the .pc in the git tree.) If there isn't
+ # one, we need to generate one by unpacking the patches that we
+ # have.
+ #
+ # We first look for a .pc in the git tree. If there is one, we
+ # will use it. (This is not the normal case.)
+ #
+ # Otherwise need to regenerate .pc so that dpkg-source --commit
+ # can work. We do this as follows:
+ # 1. Collect all relevant .orig from parent directory
+ # 2. Generate a debian.tar.gz out of
+ # debian/{patches,rules,source/format}
+ # 3. Generate a fake .dsc containing just these fields:
+ # Format Source Version Files
+ # 4. Extract the fake .dsc
+ # Now the fake .dsc has a .pc directory.
+ # (In fact we do this in every case, because in future we will
+ # want to search for a good base commit for generating patches.)
+ #
+ # Then we can actually do the dpkg-source --commit
+ # 1. Make a new working tree with the same object
+ # store as our main tree and check out the main
+ # tree's HEAD.
+ # 2. Copy .pc from the fake's extraction, if necessary
+ # 3. Run dpkg-source --commit
+ # 4. If the result has changes to debian/, then
+ # - git-add them them
+ # - git-add .pc if we had a .pc in-tree
+ # - git-commit
+ # 5. If we had a .pc in-tree, delete it, and git-commit
+ # 6. Back in the main tree, fast forward to the new HEAD
+
+ my $clogp = parsechangelog();
+ my $headref = git_rev_parse('HEAD');
+
+ prep_ud();
+ changedir $ud;
+
+ my $upstreamversion=$version;
+ $upstreamversion =~ s/-[^-]*$//;
+
+ my $fakeversion="$upstreamversion-~~DGITFAKE";
+
+ my $fakedsc=new IO::File 'fake.dsc', '>' or die $!;
+ print $fakedsc <<END or die $!;
+Format: 3.0 (quilt)
+Source: $package
+Version: $fakeversion
+Files:
+END
+
+ my $dscaddfile=sub {
+ my ($b) = @_;
+
+ my $md = new Digest::MD5;
+
+ my $fh = new IO::File $b, '<' or die "$b $!";
+ stat $fh or die $!;
+ my $size = -s _;
+
+ $md->addfile($fh);
+ print $fakedsc " ".$md->hexdigest." $size $b\n" or die $!;
+ };
+
+ foreach my $f (<../../../../*>) { #/){
+ my $b=$f; $b =~ s{.*/}{};
+ next unless is_orig_file $b, srcfn $upstreamversion,'';
+ link $f, $b or die "$b $!";
+ $dscaddfile->($b);
+ }
+
+ my @files=qw(debian/source/format debian/rules);
+ if (stat_exists '../../../debian/patches') {
+ push @files, 'debian/patches';
+ }
+
+ my $debtar= srcfn $fakeversion,'.debian.tar.gz';
+ runcmd qw(env GZIP=-1 tar -zcf), "./$debtar", qw(-C ../../..), @files;
+
+ $dscaddfile->($debtar);
+ close $fakedsc or die $!;
+
+ runcmd qw(sh -ec), 'exec dpkg-source --no-check -x fake.dsc >/dev/null';
+
+ my $fakexdir= $package.'-'.(stripepoch $upstreamversion);
+ rename $fakexdir, "fake" or die "$fakexdir $!";
+
+ mkdir "work" or die $!;
+ changedir "work";
+ mktree_in_ud_here();
+ runcmd @git, qw(reset --hard), $headref;
+
+ my $mustdeletepc=0;
+ if (stat_exists ".pc") {
+ -d _ or die;
+ progress "Tree already contains .pc - will use it then delete it.";
+ $mustdeletepc=1;
+ } else {
+ rename '../fake/.pc','.pc' or die $!;
+ }
+
+ quiltify($clogp,$headref);