[darcs-devel] V3 conflictors minus prim patch identities are just optimized Mergers

Ben Franksen ben.franksen at online.de
Sun Nov 4 20:30:15 UTC 2018


I forgot to mention an important point: what we get with the derivation
I presented in my last message is not /exactly/ the same theory as in
Camp, even if we ignore differences due to merge-by-name vs.
merge-by-value. To quote Ian:

  In darcs' theory, the transitive set of conflicts is stored. I don't
  believe this is needed, and not having it makes things simpler. Not
  having it may also mean more things commute.

While this is true, this gives us a /different/ theory i.e. one that is
not compatible with V1. Furthermore, we cannot reconstruct the binary
tree of V1 Mergers from a Camp Conflictor, viewed in isolation. To do
that we need the full context of the Conflictor. For exactly the same
reason, we cannot calculate the conflict markup from a Camp conflictor
alone i.e. without its context.

In contrast, the representation I derived in my last message should be
compatible with V1. It may turn out that it doesn't work though. A
possible issue I discovered today is that it can't distinguish between
certain conflictors where the Camp theory can. It is unclear to me at
this point if this is a problem or not.

Specifically, we start with a three-way conflict between prims A, B, and
C. Merging all three with C on top gives us for the last patch

  C' = Merger (i A :> i B ::> i C)

where as a notational convention I have separated the patch we represent
with a ::> instead of :>. In Camp notation it is written as

  C' = [ , {:A, :B}, :C]

Now merge this guy with some new prim D. After a bit of calculation we get

  D' = Merger (i A :> i B :> i C ::> i D)

This is the same Merger as we would get when we merge A, B, C, and some
other D with the same domain as A, B, and C directly. In Camp this is
not so, pecisely because the conflictor that represents D does not
directly conflict with A and B, so we get

  D' = [ , {:C}, :D]

whereas the 4-way merge of A, B, C, and then D ends with

  D'' = [ , {:A, :B, :C}, :D]

Note that these are all theoretical considerations. I haven't
implemented any of that. If it turns out being able to distinguish the
conflictors in the above scenario is essential, then the Camp theory
works only /because/ it doesn't store indirect conflicts. This doesn't
mean that all is lost: we would then have to fix the optimized V1
Mergers by distinguishing between direct and indirect conflicts.

Cheers
Ben



More information about the darcs-devel mailing list