[darcs-users] Request for more details

[Dalon Work]

Darcs team,

I recently discovered Darcs, and probably like lots of people, I'm very
intrigued by the "Patch Theory" behind it. I've read everything I could
find, and to be fair, much of it was over my head. I think I understand the
basic ideas, but I still have a lot of questions. I would appreciate it if
anyone could point me at some materials I missed or misunderstood, or could
explain in greater detail how it all works.

So, starting with a set of patches with a linear history: AB, and if you
want to "undo" A, you have to reorder A & B so you can undo A. Take AB,
commute them to get B'A', and then post-multiply by the inverse of A':

B'A'.inv(A) = B'.

I understand the basic diagram that gives the equation 0 -> AB = B'A' -> 1,
where we start with context 0, and want to get to context 1. But I don't
understand how we actually solve for B' and A'? It seems we have 2
unknowns, but only 1 equation. This is the part I can't seem to find. Is
this a manual step? I can see how if the two patches have nothing to do
with each other, then B' = B, and A' = A. But what if they do influence
each other, but don't actually conflict?

Then, in the case of a merge of two parallel patches, how do we know what
the "unique" merge result is? (Assuming no conflicts). The equation is now
0 -> AU = BV -> 1, but now we don't even know what the ending context 1
looks like! This to me looks like we have 3 unknowns, and only 1 equation.
What am I missing here?

My next question is about scalability. In a system with hundreds of
thousands of patches, it seems like a scalability nightmare, as the naive
description of how the system works makes it seems that to reconstruct the
state of the repository would require building the working tree from the
empty context every time. There has to be a way to "snapshot" a set of
patches so you have a new ground-zero to start from. And then, importing
patches from an outside repository, is it possible to "batch" them, and
work on a sets of patches inside of comparing patches 1 at a time? (ignore
conflicts for now). It seems to me
that you would have to take all the incoming patches, and 1 at a time,
modify the context for each one of them to apply them on top of the
importing repository. It sounds painfully slow.

How do you determine which patches are dependent on which patches? I know
the user can manually specify dependencies, but there has to be some
automated way to figure out the important ones, the ones that would break
things if not maintained correctly. Naively thinking, would you have to try
and commute the incoming patch with every other stored patch? Or can you do
that until you find a match, and attach it to the "dependency tree", or are
there encoded manual rules?

What is the internal patch format for darcs? Like, could I implement a
crude patch-based system using unix diff/patch utils? Or do you have to
store extra metadata to get the mechanics to work correctly? So far, all
I've found is the high-level "a patch is a transformation function". Great.
What does that function actually look like in real-life?

Anyway, thank you so much! I think this work is really interesting, and I'd
appreciate any help with satisfying my curiosity.

Dalon
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osuosl.org/pipermail/darcs-users/attachments/20201110/fafa4ea9/attachment.html>