[darcs-users] Code internals: reordering patches?

Kevin Smith yarcs at qualitycode.com
Sun Nov 23 05:24:27 UTC 2003


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?

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.

Simple examples of needing to be rearranged would be creating a 
directory before adding a file within it, or moving a file before the 
new copy gets a hunk change.

For each pair of patches, I think we have four possibilities:
1. They must stay in this order
2. They need to be reversed
3. They have no relationship to each other
4. They conflict

But looking at the logic, I don't see case 4 handled, so we don't call 
this function with conflicting patches?

Based on that, it seems that the < would handle case 1, and commute 
would return Nothing for case 3. Or maybe it's that commute returns 
Nothing for cases 1 and 3, and the < is there to check for explicit 
dependencies?

But looking at the commute code, it looks like it returns Nothing for 
conflict, and otherwise returns the successful commutation. Which makes 
it seem that we are commuting every patch that we can, rather than only 
commuting the patches that we must.

Kevin





More information about the darcs-users mailing list