[darcs-users] Colin Walters blogs on Arch changesets vs Darcs

Zooko O'Whielacronx zooko at zooko.com
Thu Nov 25 13:40:27 UTC 2004


On 2004, Nov 25, at 08:42, David Roundy wrote:

>> then you will eventually get two copies or two variants of a patch
>> imported from outside-darcs-world to inside-darcs-world.  Inside
>> darcsworld, those two patches are like matter and antimatter (hello,
>> physics analogies!) -- as soon as they both meet in the same repo then
>> that repo will become locked in its O(N^2) merging algorithm until
>> someone manually picks it apart and deletes one of the two patches.
>
> This is what Anthony was saying, when he said that darcs "doesn't 
> scale",
> but not necesarily "cannot scale".  The merge algorithms definitely 
> need
> improvement when there are conflicts.  It's possible that there is no
> efficient solution, which would be very sad, but I'm still optimistic 
> that
> I'll be able to figure out a more efficient way to do things.

Waitaminute, what is the algorithm intended to do?

I mean, suppose I have two identical patches, and...  Heck, I'll just 
try it and see.  It's only O(N^2)...

<time passes>

Okay, appended is a cutnpaste of me creating an identical file in two 
different darcs repos then pulling the "add" patch from one to the 
other.  The result is a merge conflict, which I assert makes darcs 
non-scalable in terms of a large number of decentralized hackers 
sharing source code.  (Unless all of them were to use darcs exclusively 
and all of them were to get their history from a single initial darcs 
repo, which means darcs is not scalable.)

Now you seem to be saying that you might be able to write a new 
algorithm which generates this merge conflict faster.  I agree that 
generating the merge conflict is better than hanging indefinitely 
trying to generate the merge conflict, but until darcs has a new model 
in which this experiment does not generate a merge conflict then I do 
not believe that darcs is scalable in terms of number of decentralized 
hackers.  Also, of course, it remains vulnerable to the insertion of 
backdoors into the darcs-controlled source code.

The "matter/antimatter" problem is because darcs can have two different 
names for the same patch and doesn't realize that it is the same patch. 
  The security hole is because darcs can have two different patches 
under the same name and not realize that they are different patches.  A 
change to darcs in which there is a one-to-one mapping between names 
and patches would solve both problems.

Now, this isn't a condemnation of darcs.  Not every tool has to scale 
in every way.  Darcs is an excellent tool, I'm quite happy with it 
despite the problems, and I intend to keep using darcs for the small, 
centralized projects that I'm currently using it for.  However if one 
of these grows to be a large, decentralized project, or if I want to 
contribute to a large, decentralized project, then I will not try to 
use darcs v1 for that.

Okay here is the cutnpaste.  What I wanted was for darcs to say "No 
changes!" after I pulled the identical duplicate patch from one repo to 
the other.  Instead it gave a merge conflict.  By the way, when I 
reverted the change, it got into a state that looks wrong to me -- both 
patches are present, and there are no merge conflicts or unrecorded 
changes, but the file doesn't exist.  Bug?

Regards,

Zooko

DARC draco:~/tmp$ mkdir r1 r2
DARC draco:~/tmp$ cd r1
DARC draco:~/tmp/r1$ darcs init
DARC draco:~/tmp/r1$ touch worm
DARC draco:~/tmp/r1$ darcs add worm
DARC draco:~/tmp/r1$ darcs record --author="r1author" -m'worm! whee!' 
--all
Finished recording patch 'worm! whee!'
DARC draco:~/tmp/r1$ cd ../r2
DARC draco:~/tmp/r2$ darcs init
DARC draco:~/tmp/r2$ touch worm
DARC draco:~/tmp/r2$ darcs add worm
DARC draco:~/tmp/r2$ darcs record --author="r2author" -m'worm! whoo!' 
--all
Finished recording patch 'worm! whoo!'
DARC draco:~/tmp/r2$ darcs pull -v -a ../r1
We have the following new (to them) patches:
Thu Nov 25 09:34:48 AST 2004  r2author
   * worm! whoo!

They have the following patches to pull:
Thu Nov 25 09:34:36 AST 2004  r1author
   * worm! whee!

Getting and merging the following patches:
[worm! whee!
r1author**20041125133436]
diffing dir...
We have conflicts in the following files:
./worm
Applying patches to the local directories...
Finished pulling.
DARC draco:~/tmp/r2$ darcs whatsnew -l
{
addfile ./worm
}
DARC draco:~/tmp/r2$ darcs revert --all
Do you really want to do this? yes
Finished reverting.
DARC draco:~/tmp/r2$ darcs whatsnew -l
No changes!
DARC draco:~/tmp/r2$ cat worm
cat: worm: No such file or directory
DARC draco:~/tmp/r2$ darcs changes
Thu Nov 25 09:34:36 AST 2004  r1author
   * worm! whee!

Thu Nov 25 09:34:48 AST 2004  r2author
   * worm! whoo!

DARC draco:~/tmp/r2$ darcs check
The repo is consistent!
DARC draco:~/tmp/r2$ ls -al
total 0
drwxrwxr-x  3 zooko  staff  102 25 Nov 09:35 .
drwxrwxr-x  4 zooko  staff  136 25 Nov 09:34 ..
drwxrwxr-x  7 zooko  staff  238 25 Nov 09:35 _darcs





More information about the darcs-users mailing list