--- Begin Message ---
- To: submit@bugs.debian.org
- Subject: tg export --linearize unnecessary conflicts due to repeated patches
- From: Ian Jackson <Ian.Jackson@eu.citrix.com>
- Date: Fri, 28 Oct 2011 15:41:23 +0100
- Message-id: <20138.48915.424064.734388@mariner.uk.xensource.com>
Package: topgit
Version: 0.8-1.1
Tags: patch
If you say "tg export --linearize", topgit does a depth-first
traversal of your dependencies, and for each dependency it produces a
single commit on the result branch. In each case it does this by
trying to apply the diff for that patch to the current output branch
head. It hopes that if the patch has already been included, the
resulting diff will be empty, in which case it skips making a new
commit.
However, this does not work properly in many cases. For example
consider this topology:
t/A -depends-> t/B -depends-> t/C -depends-> base
t/A -depends-> t/C
If asked to export A, topgit will (ignoring the processing of the
non-topgit branch base):
+ look at the dependencies of A
+ traverse down from A to B
+ traverse down from B to C
- on the way back up from C to B, apply C
- on the way back up from B to A, apply B
+ traverse down from A to C
- on the way back up from C to A, attempt to apply C
- attempt to apply A
This is not guaranteed to work. In particular, if B and C have a
textual conflict (quite possible if B-depends->C), trying to apply C
on top of B. And in fact there is no need to try to apply C at this
stage since it has already been included.
In fact, it may well be the case that there is only one possible
topological order, in which case we are guaranteed that there is a
single obvious conflict-free linearisation - but the existing
algorithm will fail to find it.
To fix this, topgit should realise that it has already processed C and
not attempt to apply it again. This is clearly more correct.
I think that will arrange (amongst other things) that if every pair of
overlapping patches are ordered by the dependency graph (which
includes the case where there is only one possible topological order -
ie, the dependency graph forms a total rather than partial order), tg
export --linearize is guaranteed to succeed without conflicts.
The patch below does this for me. It's maybe not the prettiest but I
was (perhaps wrongly) reluctant to further abstract away the test into
the new shell function.
Thanks,
Ian.
Signed-off-by: Ian Jackson <ian.jackson@eu.citrix.com>
--- /usr/share/topgit/tg-export~ 2010-04-26 11:07:20.000000000 +0100
+++ /usr/share/topgit/tg-export 2011-10-28 15:15:58.000000000 +0100
@@ -153,6 +153,12 @@
}
+record_dep_seen () {
+ mkdir -p "$playground/$(dirname "$1")";
+ touch "$playground/$1";
+}
+
+
## Quilt driver
quilt()
@@ -178,8 +184,7 @@
return
fi
- mkdir -p "$playground/$(dirname "$_dep")";
- touch "$playground/$_dep";
+ record_dep_seen "$_dep"
if branch_empty "$_dep"; then
echo "Skip empty patch $_dep";
@@ -226,6 +231,14 @@
fi;
fi;
else
+
+ if [ -e "$playground/$_dep" ]; then
+ # We've already seen this dep
+ return
+ fi
+
+ record_dep_seen "$_dep"
+
retmerge=0;
git merge-recursive "$(pretty_tree "refs/top-bases/$_dep")" -- HEAD "$(pretty_tree "refs/heads/$_dep")" || retmerge="$?";
--- End Message ---