Hi,
I have been, for some time, thinking of an alternative approach to solving the
"conflict problem". Even with darcs2, the conflict resolution code is
apparently exponential, despite a lot of effort going into fixing that problem.
Moreover, it seems (to me, anyway) that theory of patches may not be the best
framework for tackling this problem. But since darcs is unrivalled when
conflicts are not involved (and it is very good at avoiding conflicts)...
...my proposal would be to disallow conflicts altogether: obviously, saying
conflicts are not allowed won't magically make them go away and some mechanisms
to deal with them need to be put into place. That would be about this:
1) Turn what we currently know as darcs repo into a non-conflicting set of
patches. These patches are managed mostly like they are now. As long as no
conflicts may arise, this is all good and safe.
This means these commands are basically untouched:
add, remove, mv, replace, revert, unrevert, whatsnew
record, unrecord, amend-record
tag, setpref ?
(and semantically, although maybe not code-wise, put, get, obliterate,
rollback?)
2) Add a layer on top, working with those (non-conflicting) sets of
patches. This layer would be the one where patch-exchanging operations would be
handled: pulls and pushes, mostly.
Now the question is, how to handle these. I imagine that pulling from a remote
branch would do 2 things: get patches that are missing from ours, then if there
are conflicts, give us the choice to pick one of those (primitive) patches (and
probably show us the following dependent patches) that conflict with each other
(and "obliterate" the other (and its dependencies) -- although we may want to
retain it, as it might be the only copy -- more on that below).
I would probably store those patches, together with a minimal context file
(ie. commuted as far into history as possible -- how expensive is that to
compute?), in say _darcs/rejected or such -- both as a safety net for possibly
precious patches and also to keep track of what we have already seen and
rejected.
Now, that also basically splits "pull" into two:
a) "make my repo look more like the other repo"
b) "get new stuff from the other repo that I haven't seen yet"
When in mode a), we would want to re-ask user about the conflict decisions that
are different in remote and local repo. In mode b), we would not.
I imagine mode a) is all fine for "convergent" branch mode, while b) is better
for "divergent" mode. What a) mostly does is what is usually done now: we take
all patches from remote branch and add some of our own on top. In that world,
pull is implemented as taking everything we don't have from remote and shoving
it into local. If we have conflicts, we mark them and let the user "do
something" about them (by either amending/unpulling or recording resolution).
I imagine that the without-conflicts handling of this is similar enough to what
we have now (with conflicts) -- instead of storing the knowledge about conflict
decisions in the "conflictor" patches, we keep it outside of the patch sets, in
terms of "rejected" (primitive) patches. These decisions are propagated through
pulls of kind a) just as they are through normal pulls when conflictor patches
are involved.
Now for mode b) (ie. the divergent case), what we do, instead of trying to
"fight" the "wrong" decisions (coming from remote branch) -- with our own
("good") decisions -- we ignore them, sticking to ours. Obviously, we can't
take patches, that depend on the patches we have previously "rejected'. But
that's all fine, as there's no way we could do that, anyway.
Such resolution scheme has the "unilateral" property that David seemed to want
to achieve with conflictors -- if the user wishes to. The user can still revert
to reconfirming the resolution every time, if they wish to -- but without the
exponenital cost associated with conflictors. Or at least so I believe.
As the proposal stands, the "decisions" are not versioned in any way (the
current darcs repo is not "versioned" either, I would argue).
An alternative route (to using _darcs/rejected/ or alike) would be this: As one
might also want to attach comments to such decisions and so on, that would make
them to be "almost" patches. However, since we shove those "almost" patches
outside of the "interesting" set, we no longer need to define their commutation
properties and such. Two such "almost patches" are also mutually exclusive if
they mention same primitive patch (ie. they form a meta-conflict).
That lands us about here: We have the "real" patches (those that define the
content of pristine), then we have a set of "decision" "patches" (those define,
for each direct conflict, which primitive patch to take and which to not
take). These are under _darcs/conflicts or whatever. When we do an
(interactive) pull, we: take all "real" and "decision" patches from remote and,
if meta-conflicts occur, we ask user what to do (all-ours, all-theirs,
one-by-one). After meta-conflicts are resolved, normal conflicts need to be
resolved (possibly altering some of those previous meta-conflict decisions).
Mostly obviously, this is just a mental draft and I would appreciate some
feedback on that. Scenarios that are well served by the current approach and
impossible (or hard) with the proposed one would be good. Any other thoughts
(potenital problems in the concept) as well.
I have been haskelling somewhat recently (I have implemented a simplistic
compiler in haskell) so I might be more ready to tackle the darcs code. But it
would make sense to have the concept at least reviewed before trying to put it
into code.
Thanks for your attention. If you need something to be cleared up, do not
hesitate to ask.
Yours,
Petr.
PS: Yes, that basically means an incompatible repo format, storing the
(now-)extra information somehow. Although I imagine this is mostly equivalent
to a new patch type, with regards to backward/forward compatibility.
PPS: To describe the idea in yet different terms, I'd say that I lift the
conflict resolutions from the patch level (where the decisions need to commute
and have all sorts of properties that apparently don't fit them very well) to a
meta level. It might be tempting to ask, why not have a meta-meta level and so
on (and why not generalise this to n levels). The argument here would probably
be that the I can't think of an use-case for anything above
meta-level. Moreover, the meta-level doesn't seem to have similar-enough
semantics to the ground level, so that the meta-meta level doesn't seem to be a
natural extension. At least not when defined like above.
--
Peter Rockai | me()mornfall!net | prockai()redhat!com
http://blog.mornfall.net | http://web.mornfall.net
"In My Egotistical Opinion, most people's C programs should be
indented six feet downward and covered with dirt."
-- Blair P. Houghton on the subject of C program indentation
_______________________________________________
darcs-users mailing list
[email protected]
http://lists.osuosl.org/mailman/listinfo/darcs-users
