[darcs-users] Code internals: reordering patches?

Marnix Klooster mklooster at baan.nl
Mon Nov 24 08:57:03 UTC 2003

Kevin Smith wrote (in part):
> 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?

The Patch datatype declaration has "deriving Ord", and therefore the
Haskell implementation is required to generate code that looks
something like this:

  instance Ord Patch where
      p < q = ...

So the code you're looking for is generated automagically.

And for the meaning of that generated (<): you can find that in the
Haskell language specification.  In this case, I assume that David
just wants to have some arbitrary order on patches, for canonization.

> 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.

The 'commute' function either commutes two patches p2 and p1 (and
returns Just (p1',p2')), or it fails to commute them (and returns

> 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.

To me, this code looks like a list of patches is ordered in some
'canonical order': if commutation is possible, then use the arbitrary-
but-deterministic <-order, otherwise there is a dependency, and use
the dependency-order.

Marnix Klooster
mklooster at baan.nl

More information about the darcs-users mailing list