[Quilt-dev] Patch reordering: simple but powerful idea for resolving simple dependencies

[Norbert Nemec]

Hi there,

I'm using quilt very successfully for handling the various fixes and 
enhancements that I make to a large number of programs that I'm using.

The ever recurring problem that probably everyone else has had as well 
is the reordering of patches. Editing the series file by hand is tedious 
and dangerous. If the patches interdependent, it is even impossible.

However, I just figured out a simple solution for interdependent 
patches!!! (At least as long as the interdependencies are in 
non-overlapping regions of a file and can be resolved by diff3.)

First, the user-interface, as it was proposed by John Vandenberg before:
   (http://lists.gnu.org/archive/html/quilt-dev/2005-09/msg00016.html)

Basically the command
   quilt raise <patchname>
reorders the stack of applied patches such that <patchname> which was 
buried under other patches is raised to the top. The source tree is 
unaffected by this.

In John's proposal, this was limited to independent patches, so it would 
have been a handy simplification for what can be done by hand as well. 
Here is the simple idea that would turns it into a really cool feature:

-----------------------------
Assume A and B to be patches x, y and z to be versions of the same file. 
In mathematical notation, patches act as operators:

   y = A x
   z = B y
   z = B A x

Generally, patches do not commute. However, we assume that the changes 
in both patches do not overlap (i.e. they do not affect the same regions 
of the file). Commuting the patches therefore is just a matter of 
adjusting line numbers and contexts. That means, there exist modified 
versions of patches, namely A' and B' such that:

   y' = B' x
   z = A' y'
   z = A' B' x

These to patches A' and B' contain in principle the same information as 
A' and B' but work in reverse order.

Each patch A has a reverse ~A, such that x = ~A y. (This can be computed 
by diff -R) We can write:

   y' = B' ~A y = ~A' B y

Finally we have the "merge" operation, provided by the standard tool 
diff3. The mathematical operator * designates merging. Typically, diff3 
would be used to produce z from x, y and y' (x would be ORIG, y would be 
MINE and y' would be YOURS in the notation of the diff3 manpage) In our 
notation this process looks like:

   z = (B'*A) x

The whole thing can be visualized as an arrow diagram as follows.

            x 

        /   |   \
       /    |    \
      A     |     B'
   | /      |      \ |
   |/_      |      _\|
            |
  y       (A*B')       y'
            |
    \       |       /
     \      |      /
      B     |     A'
       \ |  |  | /
       _\| \|/ |/_

            z


Now, the whole idea is, that this diagram can simply be rotated by 90 
degrees as:

            y 

        /   |   \
       /    |    \
      B     |    ~A
   | /      |      \ |
   |/_      |      _\|
            |
  z       (B*~A)       x
            |
    \       |       /
     \      |      /
     ~A'    |     B'
       \ |  |  | /
       _\| \|/ |/_

            y'


So, we can express y' as:

   y' = (B*~A) y

With this idea, the algorithm is fairly simply:

Having the three versions of the file x,y and z and the patches in 
original order A and B, do a 3-way merge using diff3, using y as ORIG 
(!!!) to obtain y'. Now do the two diffs between x, y' and z to obtain 
the patches in reversed order A' and B'.
(Of course, it will only work where the changes happen only in 
non-overlapping regions, so the merge can be done without a conflict. 
Trying a manual resolution will be pointless in most cases, so quilt 
should just abort the operation in that case.)
-----------------------------

Unfortunately, I do not know when I might find the time to put this into 
a quilt-script. All the steps are fairly straightforward, so if anybody 
else wants to try an implementation, feel free to do so. having this 
feature would certainly boost the usefulness of quilt tremendously. The 
only other tool that I know to handle patch commutation is darcs and 
that requires a lot of overhead.

Greetings,
Norbert

--
-----------------------------------------------------> Norbert Nemec
  Molecular Computing Group ... Institute for Theoretical Physics
         University of Regensburg ... D-93040 Regensburg
     phone: +49-(0)941-943-2026 ... mobile: +49-(0)179-7475199
eMail: <address@hidden> ... room: Phy 4.1.30