[darcs-users] Code internals: reordering patches?

David Roundy droundy at abridgegame.org
Sun Nov 23 17:38:53 UTC 2003

On Sat, Nov 22, 2003 at 09:24:27PM -0800, Kevin Smith wrote:
> I'm looking at the code for whatsnew, and I can see that it has the 
> option to list the patches in any order, or in the real order they would 
> actually be applied. I got as far as the sortps function:
> sortps (p1:ps) =
>     case sortps ps of
>     [] -> [p1]
>     (p2:ps') -> if p1 < p2 then p1 : p2 : ps'
>                 else case commute (p2,p1) of
>                      Nothing -> p1 : p2 : ps'
>                      Just (p1',p2') -> p2': sortps (p1':ps')
> I know that the Patch types "have" Ord, which allows them to be 
> compared. But I can't find where (<) :: Patch -> Patch -> ?? is defined. 
> What does it mean for one patch to be "less than" another?

This is defined by the "deriving (Eq, Ord)" line (or something like that).
Because it's derived, it sorts patch types according to the order in which
they are listed in the constructor declarations, and within types,
according to each parameter in order (for filepatch case this means first
the file name).

> Aside from that, it's still hard to grasp the details of this function, 
> because it quickly gets into commute, where the calls are nested fairly 
> deeply, and it's not immediately obvious what a 'Nothing' return value 
> indicates.
> So I'm hoping to understand the intent, rather than every specific line 
> of code. It seems like we have a list of patches, which may or may not 
> have existing dependencies defined, and which may already be in a 
> perfect sequence, or might need to be rearranged.

The list of patches is already ordered in the order in which they are
defined.  Every patch has a context, which is a set of patches.  In this
case the context of each patch in the list includes all the patches coming
before it in the list.  sortps creates a new list of patches which also has
this sequential property, that is, in which the context of each patch
contains all the patches preceding it (and none of the patches following

The commute function accepts two patches, which differ in context only in
that the second patch contains the first in its context (i.e. a sequential
pair) and reorders them.  This may or may not be possible.  If it isn't
possible (e.g. the pair "create file foo" and "delete file foo"), then
Nothing is returned--this means the two patches don't commute.

The sort is an O(n^2) sort, which isn't good, but doing better requires
that we be able to break the patches into sets that trivially commute.
I'll get around to this some day...

> sortps (p1:ps) =
Firts, we sort the rest of the list:
>     case sortps ps of
If it was empty, we are done:
>     [] -> [p1]
Otherwise, we need to check if we are greater or less than the first in the
sorted rest of the list.  If we're less, then we're done:
>     (p2:ps') -> if p1 < p2 then p1 : p2 : ps'
If we're greater (or equal), we need to reorder ourselves.  We do this by
commuting with the first element in the sorted list:
>                 else case commute (p2,p1) of
If we can't commute, then we're done:
>                      Nothing -> p1 : p2 : ps'
Otherwise we've found the first element of the sorted list, and now we need
to call sort again to sort the rest of the list:
>                      Just (p1',p2') -> p2': sortps (p1':ps')

Note that none of these cases are what I call a conflict.  Conflicts can
only happen during a merge.  This is a sequential set of patches, so
(unless it's been corrupted somehow) it must be valid.  Failure to commute
indicates a dependency, not a conflict.
David Roundy

More information about the darcs-users mailing list