[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