[darcs-users] Write-up on "tree repositories" as an alternative to conflictors

[James Cook]

On Thu, Nov 26, 2020 at 02:32:08PM +0100, Ben Franksen wrote:
> Regarding Section 4.11, let me reformulate the main definition to make
> it a bit less awkward.
> 
> A patch with name n is inactive with respect to a set of tree patches S
> if it is deactivated by any tree patch (P,D) in S (i.e. n is in D),
> subject to the side condition that there exists no patch name m (in any
> tree patch in S) that depends on n but is independent of P (that is, not
> included in P's dependencies).
> 
> In other words, m re-activates n if it depends on n and is not depended
> on by any of the tree patches that deactivate n.

That sounds right. I tried to capture something like it in the sentence
following Definition 20. Maybe I could improve Definition 20 itself,
or move that sentence inside the definition, before the math.

> Suppose m depends on n and n is deactivated by a tree patch (P,D) i.e. n
> is in D. I wonder about the side condition and what it implies.
> 
> If P depends on m, then there is a p in P that depends on m.
> 
> Doesn't that imply that such a p is also a member of D?

Maybe it ought to, but under the current definitions it doesn't.

For one thing, a tree patch that results in an "impossible" signature
is still a tree patch. Continuing your example, if suppose we had the
tree patch repository

  n   m
*-->*-->*

with the single tree patch (P = {n, m}, D = {})

Then (P = {p, n}, D = {n}) fits the definition of "tree patch", even
though adding it to the repo would result in the impossible signature
(P = {n, m, p}, A = {m, p}).

But even if we say a tree patch cannot be applied if it results in an
impossible signature, there's still a counterexample. If we start
instead with

*
| n
v
*
| m
v
*
| p
v
*

with tree patch (P = {n, m, p}, D = {n, m, p}) (i.e. everything's
already deactivated) then adding the tree patch (P = {p, n}, D = {n})
would not change the signature.

> And that m is also in P, since n is in D which is a subset of P?

Why? Note that Definition 20 doesn't put any constraints on P.

> Also, is it true that m can reactivate another patch n only if m is active?

No. For example, if we start with just

*
| n
v
*

where n is inactive, the tree patch (P = {m}, D = {m}) re-activates n
even though m is inactive. You could also use (P = {n, m}, D = {m}).

> Cheers
> Ben

-- 
James