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

Ben Franksen ben.franksen at online.de
Thu Nov 8 20:02:26 UTC 2018


It turned out that restoring the old V1 Mergers is not possible with the
representation I had in mind. The problem is that it throws away a bit
too much information when merging conflicting Mergers. I am currently
searching for a way to add this information without compromising efficiency.

Stay tuned...

Cheers
Ben

Am 04.11.18 um 21:30 schrieb Ben Franksen:
> 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