Hi,
These are all going in under the usual plan of "it doesn't seem to
change current behaviour, but I can't wrap my head around all the new
stuff".
> Thu Aug 23 12:06:57 PDT 2007 David Roundy
> * add eq_patches support for Conflicted, etc.
>
> Thu Aug 23 12:35:26 PDT 2007 David Roundy
> * introduce ordersafe compare
>
> Thu Aug 23 13:12:28 PDT 2007 David Roundy
> * clean up unconflict_some_to_end
New functions

My notes...
remerge  didn't really look
conflict  mark a patch as a Conflicted type, unless it is already
Conflicted, or it was Cancelled (which we're not worried about
anyway). If I correctly recall what the Conflict type is about,
the patch isn't marked as conflicting with anything (NilFS) in
particular.
conflictFL  mark a sequence of patches as conflicted. I'm not
entirely sure why we're trying to force them all to end though
force_to_end  given
p1 :>: p2 :>: ps
try to commute p1 all the way down to the end, resulting in
p2' :>: ps' +>+ (p1' :>: NilFL)
[:>: is to cons as +>+ is to ++]. If we succeed, great! If
not, force it! Mark any patches it fails to commute past
as conflicted. Here we are interested not interested in
what happens to p1, just to the patch sequences. So given
p1 / b c d e
If p1 commutes fine, we get
b' c d e
If it gets stuck trying to commute past c, we will get
b' [c] [d] [e]
Where brackets denote conflicted patches.
safeEqFL  used for checking if two Conflicted patches are
equal. We don't know what order the two sequences are going to be in,
so we can't just zip compare down the lists. Instead, given (x:xs)
and (yys), we use the handy dandy head_permutationsFL to see if we can
find an analogue to x in the list.
head_permutationsFL

The head_permutations(FL) function was interesting to study. No major
changes here, just a minor rewrite to use the new GADT types. For
some reason, I decided to figure out what this function was about. Here
are my notes.
The function reminds me a bit of Haskell list functions 'inits' and
'tails' in the sense that we probably don't actually want to use all of
the results, but we rely on laziness to only compute the ones we want.
But this is just a guess.
After playing with it on paper, the basic idea seems to be that given a
patch 'p' and a patch sequence 'ps'; you want to find the possible ways
to commute *one* patch in ps with p. So given a sequence like
X h a y stc k
You want to retrieve one of the patches in 'h a y s t c k' that can
commute with X. The approach has two basic steps: commute the patch
down to the head of the list (recursive call), and try commuting them
with p (swap_first).
Let's say that the patch t depends on s, and c depends on t (this is
denoted above with hyphens). Calling head_permutations on this function
will give us
X h a y s t c k
h X a y s t c k
a X h y s t c k
y X h a s t c k
s X h a y t c k
k X h a y s t c
There are two things to notice here. First, in all the patch sequences,
the order of the patches is mostly undisturbed except that one patch has
been moved on to head of the list. Second, something is missing!
None of the patch sequences seem to begin with 't' or 'c'. This is
because of the dependencies; c depends on t and t depends on s, so when
we try to commute them past s, we fail and do not explore that branch of
the tree.

Eric Kow http://www.loria.fr/~kow
PGP Key ID: 08AC04F9 Merci de corriger mon français.
