No subject


Fri Aug 24 18:29:08 UTC 2007


    * The existence of a precedence operator.  For any two patches, P1
      and P2, exactly one of the following three statements is true:

        P1 <p P2  (P1 precedes P2)
        P2 <p P1  (P2 precedes P1)
        P1 ~p P2  (P1 and P2 have no precedence relationship)

      Additionally,
        P1 >p P2 iff P2 <p P1
        P2 ~p P1 iff P1 ~p P2
        P1 =p P2 iff P1 and P2 are the same patch
        P1 !p p2 iff P1 <p P2 or P1 >p P2
        if P1 <p P2 and P2 <p P3 then P1 <p P3
        if P1 >p P2 and P2 >p P3 then P1 >p P3

    * There is a set P of all patches which is partially ordered
      on precedence.

I started thinking about the above because I was looking for a way to
define the empty tree such that it is clear what effect any given
patch would have on it, especially since there are obviously some
patches which can operate on an empty tree and some which cannot.

    * From the implementation, it looks as though there are only two
      kind of patches which can operate on an empty tree: "file add"
      and "directory add".

    * If we posit that an empty tree contains no directories at all
      (not even the "top level" directory), then the *only* patch
      which can operate on the empty tree is a "directory add" patch
      for that top level directory.  (This is only for theoretical
      purposes of course; it doesn't need to be explicit in the
      implementation).

This way we have an implied precedence for lots of different kinds of
patches; a file or directory add depends on the "directory add" patch
of its parent, except for the top-level directory which has no parent.
A file modification patch depends on the that file's "file add" patch.
A file or directory move or delete patch also depends the "add" patch
for that file or directory, and so on.

Establishing this partial ordering goes a long way towards being able
to prove the theorem that merges always succeed.

So... does any of this make sense?  Feedback is very much welcome.

cheers,
--Mirian




More information about the darcs-users mailing list