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

[James Cook]

> Interesting! So corners (potential contexts) have an inherent partial
> order, indeed they form a join-semilattice. You postulate that if two
> contexts have an uppper bound that is also a context, then the minimal
> upper bound must also be a context. I think the math term would be that
> contexts form a sub-semilattice of the corners.

I should credit my friend Sridhar Ramesh here. I was asking them
whether there's a name for some property involving pushouts, and
casually mentioned we might not need to distinguish morphisms with the
same domain and codomain, and Sridhar pointed out that's just a
pre-order.

> It's funny how this brings us all the way back to the ideas in your
> first paper: instead of focusing on patches or paths, we now focus
> almost completely on contexts.

That's a good point.

I think there's a straightforward connection to the "pseudo-contexts" I
had before. A pseudo-context was a path together with a partition of
the names in the path into a "before" part and and "after" part. You
can translate that to a corner of the hypercube by taking the names in
the start node of the path, and adding in the names in the "before"
set. This at least captures the idea I had in mind that the
pseudocontext comes "after" that set of names.

On Mon, Dec 14, 2020 at 03:30:50PM +0100, Ben Franksen wrote:
> Am 13.12.20 um 11:16 schrieb Ben Franksen:
> > However, remember your counter example of a patch universe with only two
> > paths with names abc and cba. From the presence of both {a} and {c} we
> > can deduce that of {a,c}, but it seems impossible to prove that {b} is
> > present. For that we need a fifth axiom (e) analogous to (d) but with
> > intersections instead of unions:
> > 
> > e) If nodes c1 and c2 are present, then c1 ∩ c2 is also present.
> 
> This is still not quite insufficient. With the natural numbers as the
> set of names, b={}, and t={1,2}, the set C={b,t} would be a valid set of
> contexts. But then there is no path from b to t (in fact we have no
> patches at all). In general I think we want the patch graph to be
> connected. A possible characterization in terms of contexts could be:
> 
> (f) For every non-empty context c there is at least one element n of c,
>     such that c\\{n} is also a context.
> 
> It is then easy to show that a path p:s->t exists if and only if s is a
> subset of t.

Good points. So now with some rephrasing, the rules on the set of
contexts are:

(a) The empty set is a context.

(b) If c1 and c2 are contexts, then c1 ∩ c2 is a context.

(c) If c1, c2, c3 are contexts and c1 ⊆ c3 and c2 ⊆ c3, then c1 ∪ c2 is
    a context.

(d) For every non-empty context c there is at least one element n of c
    such that c\{n} is also a context.

I haven't found a definition for "sub-semilattice" but maybe that word
could encompass some of the above.


> Another interesting observation is that we can regard a name as a
> partial bijection between contexts. The action of the function is to add
> the name to the context and its inverse is to remove it. Its domain and
> range are given by
> 
>   domain(n)={c∈C|n∉c and c∪{n}∈C}, range(n)={c∈C|n∈c and c\{n}∈C}
> 
> The reason I find this interesting is that it hints at a possibility to
> re-introduce /concrete/ patches (that is, /patch content/) into the
> picture. Concrete (primitive) patches can be seen as partial bijections
> on a set S of states, represented as data.

I'm not sure I understand. I guess a state is the content of the files
in the repository. Any concrete patch has exactly one start state and
one end state. Do you mean that it's a partial bijection where the
domain and range are both sets of size 1?

E.g. suppose the concrete patch P is:

hunk ./file.txt 2
+world

and in the context of p, file.txt has just one line "Hello".

I guess it's tempting to think of p as the following partial bijection
f: f always inserts the line "world" after the first line of file.txt.
But that's not really a useful representation of p; e.g. it doesn't
work if p gets commuted to a different context. So to me it makes more
sense to just say that concretely, p is the pair ("Hello\n",
"Hello\nworld\n").

I guess this is a long-winded way to just say I'm not sure what you
mean by concrete patches being bijections.

I guess you'd want to be able to commute concrete patches without
access to any information other than those two patches'
representations. Does your definition capture that?

> Here, too, we can generalize
> to finite sequences of patches, which then naturally form a category,
> and there is a (non-injective) functor (the "apply" functor) from that
> category to the groupoid of partial bijections on states that maps
> concatenation to function composition.
> 
> We may want to study functors from an abstract patch theory to a
> concrete one.

That's neat.

> A functor maps both objects and arrows. For objects,
> F:C->S associates a concrete state to each context (this mapping is also
> not necessarily injective). For arrows it associates to each path p:s->t
> a concrete patch F(p):F(s)->F(t). The functor laws say that
> F(id_c)=id_F(c) and that F(p;q)=F(p);F(q).

So the patch is an arrow joining two states? This is more in line with
my view above that a patch is a pair of states.

> This does not a priori mean that each abstract /patch/ (singleton path)
> maps to a concrete patch,

Doesn't it, if a concrete patch is just a pair of states? But I guess I
don't really know what you mean by concrete patch.

> so I guess we have to require that, in
> addition to the usual functor laws. There may be a few more extra
> requirements that we want to impose. For instance, I guess we need some
> sort of consistency requirement that relates commutation in the abstract
> setting to that in the concrete setting. Needless to say, I haven't
> thought these things through to the end, so I can't tell yet if it has
> any practical relevance.

> This variant of abstract patch theory has clean merge and unmerge (of
> contexts) already built-in, so to speak, since merging is just taking
> the union and unmerging is taking the intersection. I find it
> interesting to note that adding conflictors a la Darcs means that we
> enlarge the set of contexts by adding /conflicted states/, which are
> those corners that we get (in addition to the normal unconflicted
> contexts) if we allow arbitrary unions of contexts. Seen in this way,
> conflictors appear quite natural and simple, conceptually at least.

(Replying to this last since it depends on more context.)

To make this point of view work, I guess you would want to extend the
functor so that the conflicted contexts also map to concrete states ---
this determines what state Darcs leaves the repo in when there are
conflicting patches (if you leave out the conflict markers). And
similarly you'd want to extend concrete representations of patches.

I'm not sure what rules constrain us here. E.g. I could just declare
that any "conflicted" context maps to the empty fileset, but would that
work out? I guess the hard part is figuring out what how the concrete
patches work (for example, how you can commute them without access to
anything but the two patch representations).

This reminds me of the function I built that mapped every
pseudo-context to a primitive context, when I was working on making an
arbitrary primitive patch theory commute. If the above could be
extended to the entire hypercube (rather than just arbitrary unions of
contexts) then I guess we would have arrived at my original goal of
making a patch theory where patches always commute. (At this point I'm
not sure how useful that is.)

> Cheers
> Ben

-- 
James