[darcs-devel] darcs patch: Partial remerge (and 8 more)

[Eric Y. Kow]

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 <droundy at darcs.net>
>   * add eq_patches support for Conflicted, etc.
> 
> Thu Aug 23 12:35:26 PDT 2007  David Roundy <droundy at darcs.net>
>   * introduce order-safe compare
> 
> Thu Aug 23 13:12:28 PDT 2007  David Roundy <droundy at darcs.net>
>   * 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 s-t-c 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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 186 bytes
Desc: not available
Url : http://lists.osuosl.org/pipermail/darcs-devel/attachments/20070826/4ae53b2d/attachment.pgp