[darcs-devel] Conversion to darcs-3

[Benjamin Franksen]

I have taken up my initial work providing a 'darcs convert darcs-3'
command. What I have achieved so far: I can reliably convert any darcs-1
and darcs-2 repo, completely keeping all patch identities, if the repo
has the following properties:

 (1) it contains no darcs-2 duplicates

 (2) every Named patch can be made unconflicted by commuting enough
     patches past

To explain the limitations, here is a rough sketch of how it works.

Assume we are given the input repo as an FL of Named patches. We
traverse it forwards, checking each patch whether it is conflicted or
not. If it is unconflicted, we can convert it by (safely) coercing all
prims contained in it, and copying all meta-data verbatim. If it is
conflicted, then we proceed as follows: we remember all patches we have
already converted as (original,converted) pairs. When we hit a
conflicted patch we unzip the sequence of original/converted pairs and
commute the new patch backwards, pushing dependencies with it, similar
to commuteWhatWeCanRL, but we stop as soon as the patch becomes
unconflicted. We then convert it and merge it with the converted part of
the unzipped history that we passed by during the backwards commute.
When we are done with that, we have our converted patch in conflicted
form. We now check that it has the same effect as the original
conflicted patch.

There are two things that can fail here:

 (1) The backward commute hits the bottom of the repo (autsch!)

 (2) The effect of our converted patch differs from the original one.

The two properties we required above correspond to these two failure
modes. It is a sad fact that our very own darcs repo contains at least
one patch that fails property (1):

patch ae4febe5ea3946e54e0b0006c9c0525c4033aa6f
Author: Ganesh Sittampalam <ganesh at earth.li>
Date:   Fri Oct  8 23:30:21 CEST 2010
  * build test harness with witnesses and drop separate build

Here is a proof: pulling any patch into an empty repo should make it
unconflicted, but here this doesn't work (be prepared to wait a few
minutes for the pull to finish):

franksen at tiber: ~/scratch/bla > darcs init
Finished initializing repository.
franksen at tiber: ~/scratch/bla > darcs pull ~/src/darcs/reviewed -h
ae4febe5ea3946e54e0b0006c9c0525c4033aa6f --allow-conflicts -a
We have conflicts in the following files:
./darcs.cabal
./src/Darcs/Commands/Add.lhs
./src/Darcs/Commands/AmendRecord.lhs
./src/Darcs/Commands/Move.lhs
./src/Darcs/Commands/Record.lhs
./src/Darcs/Commands/Send.lhs
./src/Darcs/Hopefully.hs
./src/Darcs/Patch/Bundle.hs
./src/Darcs/Repository/Internal.hs
./src/Darcs/SelectChanges.hs
Finished pulling.
franksen at tiber: ~/scratch/bla > darcs log -s --last=1
patch ae4febe5ea3946e54e0b0006c9c0525c4033aa6f
Author: Ganesh Sittampalam <ganesh at earth.li>
Date:   Fri Oct  8 23:30:21 CEST 2010
  * build test harness with witnesses and drop separate build

    M! ./darcs.cabal -80 +2
    R ./src/witnesses.hs

I think we can't do much about that. A convenient, if dirty, way to
convert such broken patches is to replace their content with the effect.

Property (2) is what gives me the most head-aches. Almost all darcs-2
repos contain duplicates. A Named patch which contains a duplicate will
always have a different effect than the one we created by merging its
unconflicted version upward. I have considered various ways to cope with
duplicates but they are all problematic in one way or another.

So, after banging my head against this for quite some time, I am now
seriously considering to add a Duplicate constructor to RepoPatchV3. The
idea here is to implement them in a sound way that preserves
permutivity, so they won't behave exactly like V2 Duplicates. Basically,
a V3 Duplicate behaves like a specialized conflictor with a different
default resolution of the conflict. This view makes it possible to
derive the code for the new cases for commute and merge from that for
conflictors.

Similar to a Conflictor, a Duplicate needs to keep track of all patches
that we consider as its duplicates. However, I think that in this case
we can perhaps get away with keeping track only of IDs i.e. omit the
(contexted) patches themselves, since we know their prim content is
equal to our own.

I have almost completed a first prototype and will hopefully soon be
able to test it. I am currently planning to add them only for
compatibility, so the regular 'merge' function would not create them.
Instead I think I will add a special merge function to be used for
conversion only.

Whether we may want to add Duplicates as a feature is another matter.
There are some arguments for and some against. Perhaps it will be
possible to mix the two ways to merge duplicate patches, so we could
offer creation of duplicates during merge as an option. If not, we may
need to distinguish this via a format flag, which also means that a repo
that was converted from darcs-2 will have to continue to create
Duplicates when merging.

Cheers
Ben