[darcs-devel] again: calculating minimal contexts

Benjamin Franksen benjamin.franksen at helmholtz-berlin.de
Tue Feb 11 14:46:10 UTC 2020


A while ago I wondered how Pijul is able to determine minimal contexts
efficiently. I think I understand that part now.

The main problem with efficiently determining minimal contexts in Darcs
is that in order to know whether B depends on A we have to get them into
proximity. For a sequence of patches A;A1;...An;B that means we have to
commute A past all the Ai; only then can we try to commute it with B. We
have to do this even if we already know that A commutes past all the Ai
(for instance because we have cached that information somewhere),
because during that commutation the A may be modified.

In Pijul patches are never modified! Any two patches A;B either commute
trivially or not at all. This is so because (1) there are no conflictors
(instead conflicts are represented as de-normalized state) and (2) all
the atomic pieces of the state are addressed using UUIDs, including file
content. In particular, (2) means that there are no hunks as in Darcs
i.e. no line numbers, instead the order of the pieces that make up a
file content is determined using before/after relations between these
pieces.

If patches are never modified, determining a minimal context is worst
case linear in the number of patches, even if we naively try to commute
with every existing patch. With clever caching it can probably be
brought down to something sub-linear, at least on average.

Cheers
Ben



More information about the darcs-devel mailing list