[prev in list] [next in list] [prev in thread] [next in thread] 

List:       darcs-devel
Subject:    [darcs-devel] alternate (simplified) conflicts proposal.
From:       David Roundy <droundy () darcs ! net>
Date:       2006-07-13 12:49:22
Message-ID: 20060713124917.GE29591 () abridgegame ! org
[Download RAW message or body]

Hello interested persons (and uninterested persons, please ignore me),

I'm attaching here a description of the proposed new semantics of
conflict resolution, etc.  I don't describe how resolutions will be
created (that's a UI issue, as far as I can see), but instead how they
will behave.  As far as I know, this is complete, but it's very brief
and assumes a knowledge of how primitive patches (changes) currently
behave.

I would very much appreciate it if you'd take a look, and point out
areas that are unclear or incomplete (of which I suspect there are
several).  Note that if you don't understand something, it's almost by
definition unclear (the exception being if it's covered in the "theory
of patches", and you aren't familiar with where--but even then I'll
appreciate being asked and see if I can provide a reference).

I also would like to field any questions about how these semantics
would work out in hypothetical examples.  Even if the following is
entirely clear and complete, if it doesn't behave in an acceptable
manner, then we'll have to rethink it.

NOTE: For now, I will try to use *change* to refer to ``primitive
patches''.

Definitions
===========

A *live change* is a change that is either depended upon by a live
change, or has not been specified in a resolution.

A *resolution* is a change that has no effect, but which specifies a
single sequence of changes that are to be killed.  *Note: this
definition doesn't define all behavior of a resolution, nor is it
intended to.*

A *live conflict* is a sequence of changes that conflict with other
changes in the repository--with those changes also being part of
another live conflict.

The *conflict branch point* occurs at the end of the sequence of
patches corresponding to the pristine state, although it may be said
not to exist if there are no *live conflicts*.

State of pristine
=================

The pristine state of the repository is defined to include the set of
all live changes that do not conflict with any other live change.

Handling of live conflicts
==========================

Live conflicts are equivalent to a set of sequences of changes all
leading out from a single *conflict branch point*.  How to deal with
them is an interesting question, but not a fundamental question (or
rather, not one I'm addressing at the moment).  They must exist, and
must be equivalent to the above, but most of the important semantics
involves merely the distinction between live conflicts and the
pristine state.

In other words, we can for the moment ask the question of how your
repository will behave if you never resolve a conflict yourself, but
only pull resolutions from other repos.  That should define the
semantics adequately, I think.

Behavior of resolution patches
==============================

A resolution of the sequence of changes $ABC...$ generally commutes
like the sequence ABC...C^B^A^, with the exception that two successive
resolution patches always commute.

Meaning of merging
==================

A ``nonconflicted'' merge of two changes is always achieved by
commutation with an inverse (which I won't explain here... it's
explained elsewhere).  In any other case, the two changes involved
conflict with one another, and cannot live together in the pristine
state.  i.e. one of them must be killed.  It's a brutal dog eat dog
world we live in...

Conclusions
===========

As far as I can see, this is essentially a complete spec, albeit
highly informal.  I'm sure there are unmentioned assumptions I've
made, or cases I haven't thought of, which I certainly hope to hear
about.
-- 
David Roundy

_______________________________________________
darcs-devel mailing list
darcs-devel@darcs.net
http://www.abridgegame.org/cgi-bin/mailman/listinfo/darcs-devel
[prev in list] [next in list] [prev in thread] [next in thread]