Debian Bug report logs - #646944
tg export --linearize unnecessary conflicts due to repeated patches

Reply or subscribe to this bug.

Toggle useless messages

Message #5 received at submit@bugs.debian.org (full text, mbox, reply):

From: Ian Jackson <Ian.Jackson@eu.citrix.com>

To: submit@bugs.debian.org

Subject: tg export --linearize unnecessary conflicts due to repeated patches

Date: Fri, 28 Oct 2011 15:41:23 +0100

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="$?";

Send a report that this bug log contains spam.