[darcs-users] Fwd: Darcs Problems

[Stephen J. Turnbull]

John Lato writes:
 > We start with a single patch O establishing a shopping list:

 > Now user Arjan clones the repo and adds patch A
 > O+A (deps O):

 > Now user John clones the repo and adds a base patch bp0, then adds another
 > patch B.  His repo has
 > O + bp0 (deps B->O) + B (deps bp0):

bp0 is empty?

 > Scenario 1: Ganesh clones the repo and wants to pull from John, so he'd be
 > getting B+bp0.
 > B (deps bp0) + bp0 (deps B->O) [and this is OK]

 > Scenario 2: Arjan wants to pull from John, again he'd be getting B+bp0.
 > The transitive dependency O is present, but this time there's a problem
 > because the patches A and B don't commute.  So darcs does a forced
 > commutation of those patches,

Across the base patch?  Why does this work?  Which commuted patch ends
up on which side?

 > marks conflicts, and asks Arjan for a resolution.  Arjan commits C
 > as the resolution, giving him a repository with:
 > 
 > O+A (deps O)
 >     +bp0 (deps B1->O; C->A)
 >     + B1 (deps bp0) + C (deps B1)

I don't understand what "C (deps B1)" means.  Remember that in a
forced commute B1 has the same effect as -A.  Normally dependencies
are based on effects.  In Darcs (at least as of the last revision of
the wikibook), the dependency on B and/or B1 seems to go through the
conflictor D that represents/contains it and the information about how
it conflicts with A.

 > Scenario 3: Stephen initializes an empty repository and pulls from John.
 > Again, he'd be getting B+bp0
 > 
 > In this case there's an unfulfilled transitive dependency.  That's ok for
 > now.  But when darcs tries to apply B to an empty repository, it can't.
 > Darcs could offer to grab the missing dependency or use a null file.
 > Getting the missing dependency from the source repository is simple

No, it's not, in general.  As I wrote before, Darcs doesn't know
anything about the semantic dependencies, and can't help the user
decide.  The only thing that is close to safe in all cases is to abort
and tell the user to clone a real repo, then pull the patch.

Such options may be useful in a lot of cases, of course.  I'm just
objecting to calling it "simple"; as you have it here it's a "Here Be
Dragons" kind of thing.

 > The base patch presents an alternative model, i.e. creating a
 > special patch to take the place of dependencies, then resolving
 > conflicts after the fact.  This means the original patches can
 > retain their identity.  One downside is that this special patch
 > complicates the theory, if indeed it's workable at all.

I'm having trouble seeing how it is supposed to work, indeed.

 > Maybe it's easier if you think of it as dual to tag?  Patches
 > depend on a tag to get context, whereas base patches (cotags?) 
 > depend on patches to provide context?  Or maybe I've devolved to
 > nonsense...

General abstract, indeed!  But yes, without more information on the
relation between patch objects and context objects, calling a base
patch a "cotag" is empty formalism.

 > > I see two problems with the theory you present though.  One is that
 > > hotfix' is just going to be a new patch.  The other is that AFAIK (see
 > > caveat below) there is a theorem of patch theory that says hotfix'
 > > can't depend on both hotfix and -hotfix, since hotfix + -hotfix = 0.
 > 
 > As I understand it, this is why forced commutation flips the identities of
 > the two patch inverses.

Not identities, effects.

 > > And I still don't understand how you handle context that was
 > > established outside of the base patch and subsequent patches,
 > > unless the base patch is implemented as a tag (which guarantees
 > > that no such context exists).
 > 
 > I hope that my examples above have covered this.

No, because your examples don't touch both pre- and post-bp0 context.
What I have in mind is a sequence of a patch that adds nuts at line 3
and one that adds a nutcracker between cookies and rice (or perhaps a
two-hunk patch with the same effect).  There's a semantic dependency
here that won't be reflected in Darcs' automatic dependency list.

 > Just rambling now, but there are two parts to a patch, the context
 > and the function.  When you have the proper context, you can apply
 > the function to get a new context.  Currently, darcs requires that
 > when you pull a patch, you also pull everything necessary to
 > establish the proper context.  But what we frequently want to do is
 > pull a patch, see what's necessary to establish that context
 > manually, then do it.  So if we start with
 > 
 > oAa  (patch A is a function from context o->a)
 > 
 > and we want to pull
 > 
 > bCc  (patch C is a function from b->c)
 > 
 > darcs requires that we pull whatever's necessary to get to 'b' along with
 > C.  But what I want is to pull C, and let darcs allow me to record
 > 
 > aB'b (patch B' is a function from a->b)

Your contexts are way underspecified.  In fact, what you are thinking
about is a *partial* function {contexts}->{contexts}, and in
particular patch C is a (total) function C:{b, b', ...}->{contexts}
where {b, b', ...} are the contexts where you are allowed to apply C.
So you want to construct an appropriate B' and b', but in many cases
it's a very bad idea to throw away all the information in patch B:a->b
(the sum of "whatever's necessary to get to 'b'").

 > The problem is that after I record such a patch, most likely nobody
 > else wants it, and it also means that now my 'C' has different
 > dependencies than the original because we got to the same context
 > via a different path.

It's a different context, though.  A lot of alleged patch theory is
very sloppy about that.  The "Camp paper" (cited below) has one
formalism that works, I think, but it's clumsy.

 > > It occurs to me that Ben's ideas may imply a sort of "tag
 > > algebra" to go with "patch algebra".
 > 
 > I'm unfamiliar with this, do you have a link?  Seems very relevant.

The interesting links on patch algebras are on the Darcs wiki as far
as I know: see http://darcs.net/Theory.  The most elaborate ones are

Camp: http://projects.haskell.org/camp/files/theory.pdf
Judah Jacobson's work: http://www.math.ucla.edu/~jjacobson/patch-theory/

Unfortunately the latter 404s and I don't know where my local copy
went.  As for "tag algebra", it doesn't exist yet (at least, not to my
knowledge :-).