[darcs-devel] Bug in commute / ChangePref?

Sun Oct 3 06:16:12 PDT 2004

On Sat, Oct 02, 2004 at 07:59:32AM -0400, David Roundy wrote:
> In retrospect, I with I had made the prefs be truly versioned.  It would
> just mean that you'd have to keep two copies, one for the local prefs
> (those with apply to the current repository) and one for the recorded
> prefs.  It would have been more work, though, and when I created the
> setpref patch type, I was still pretty uncertain about how to handle
> conflicts.  I suppose I'd also have to add a flag to record, whatsnew and
> revert to make them show local changes to the prefs file, since you don't
> want such changes by default to be recorded and propogated.

Not sure I follow; wouldn't it be easier to just have _darcs/localprefs/
and look in there for preferences first, but never record them? You'd
only need to change how you get the prefs then, and wouldn't need any new
options. I don't really see the big deal with just never pushing your
pref changes if you want them to remain local, though -- if you later
want to change the "official" prefs, it's just a matter of creating a
new tree, updating the prefs in that, and pushing those changes.

> > On Thu, Sep 30, 2004 at 05:49:56AM +1000, Anthony Towns wrote:
> > Is that a bug or the way it's meant to work? If it's a bug, does adding
> > something like:
> >         commute (ChangePref p f1 t1, ChangePref p f2 t2) = Nothing
> > somewhere around line 751 of Patch.lhs fix it? (Though, presumably
> > composite patches would also have to be taken into account?)
> This would work but would be over-strict.  Better would be
>         commute (ChangePref p f1 t1, ChangePref p f2 t2) | f1 == f2 = Nothing

Shouldn't that be t1 == f2? p is the pref, f is the "from" setting,
t is the "to" setting?

> Actually, I think I think the current code would deal with setpref
> conflicts fine.  The "recorded" result of the conflict would be that
> neither setpref is performed, but the default resolution would be to just
> choose one of the two setprefs.  Recording this change would then "resolve"
> the conflict (i.e. wouldn't commute with the merger that the conflict
> generates).

Ah, magic.

> This is basically the idea behind the ideas I've got for the
> next-generation merger code.  There are a lot of trickinesses that need to
> be worked out, but the idea of making a "failing commute" generate a merger
> is a powerful one.  The trick is that it still needs to "officially" fail.
> Otherwise you introduce all sorts of nasty problems.  (And no, I'm not sure
> what "officially" means in this context... just that you can't be
> accidentally pulling a patch without patches it depends upon... that's
> crazy business.)

Yeah. I was thinking idly that some sort of "make it so I can apply this
patch" command might be interesting -- for setpref that'd mean replacing
the "from" pref with whatever the current preference is, for hunk patches
it might mean adding the file, and for other dependencies it might mean
incorporating them -- that might be a good way of knowing when thing's
can be "unofficial". Then I thought "how about you try to understand
how darcs works _now_ rather than making up new complications" :)

> The most obvious advantage of this kind of commutation behavior is in
> dealing with merges with a patch and its inverse.  In particular, it would
> be nice to have it be true for every A and B that
> 
> (A, [B,invert B]) <-> ([B',invert B'], A)  (Equation 1)
>
> Alas, this is not currently the case for mergers (although it *is* for
> ordinary patches), and as a result we get a very nasty nested merger if you
> try, for example, to merge
> 
> [A,H] (Your notation, R = rmfile f etc)
> 
> with
> 
> [A,R]
> 
> while in reality there isn't a conflict, as long as the [A,R] is done
> first.

But if it comes second, it's [[A,H], [A,R]] which doesn't work, and
mergers are meant to commute. Yick.

Hey, you could, umm, how can I put this? Well, when handling Merger(X,Y),
first convert all the X addfile f's, into addfile f.UNIQSTR("X"), and
similarly for the Y addfiles; then merge X', Y', and a whole bunch of
"move f.X f; move f2.Y f2". Except if f2's been removed, there's no need
for the move any more! Kinda vile though. :(

> The problem is that to make Equation 1 true for *every* patch, we'd need to
> either make all patches commute, or make them "provisionally" commute in
> some sense, 

Hrm, maybe it makes sense to think of a merge as being in three parts:
a patch to indicate there's a conflict coming up, the conflicting patches,
then a patch to finish resolving the conflict. So, if you've got:

	hunk ./foo 10
	+hello!

	hunk ./foo 10
	+goodbye!

as conflict patches, you might end up with:

	merger [          # add conflict markers
	hunk ./foo 10
	+vvvvvvvv
	+--------
	+^^^^^^^^
	] [               # add goodbye! hello!
	hunk ./foo 11
	+goodbye!
	hunk ./foo 13
	+hello!
	] [               # remove conflict markers, make it hello! goodbye!
	hunk ./foo 10
	-vvvvvvvv
	-goodbye!
	---------
	hunk ./foo 11
	-^^^^^^^^
	+goodbye!
	]

Then you've gone from A || B to [SETUP ; A' ; B' ; CLEANUP], probably
with SETUP, A' and B' commuting, but CLEANUP not commuting with anything
(ie depending on the other three patches). Then you can merge anything,
as long as you can "adjust" A and B a little bit, so for conflicting
addfiles you use the same translation you use for "movefile".

The "adjusting" bit ought to be reversible (A -> A' doesn't lose any
information), applyable (ie, A' doesn't result in anti-files or setting a
file's timestamp to two values simultaneously) and invertible (obviously)
though, which is tricky.

Err, or something. I've got no idea what I'm talking about it. If any of
that made any sense, it's not my fault. Any resemblence to the way darcs
works, should work, or possibly could work is entirely coincidental. Patch
theories may have been harmed in the making of this email. :)

>             which would mean that we'd have to have a more complicated set
> of output possibilities from commute.  There are also dangers that this
> sort of change could make commute failures exponentially expensive, which
> would be very bad (obviously), as darcs keeps hoping it'll run into an
> inverse patch which will make the previously failing commutes all right
> after all.

Hrm. OTOH, solving merges properly in all cases is probably NP-complete
(wild assed guess :), so you've probably got to expect to either risk
exponential explosions every now and then, or just adopt some sort of
"near enough's good enough" philosophy.

> > I dunno. I hope people don't mind me thinking out loud about this to
> > the list while I'm trying to figure out darcs. :)
> Not at all! Darcs started with me thinking aloud on the arch list... I just
> hope you don't end up getting frustrated and going off to qwrite your own
> revision control system... :)

Ugh, god no. Perish the thought.

Is there any reason (like efficiency?) why commute and commute_no_merger
are mostly duplicated, rather than doing something like:

	xcommute :: Bool -> (Patch,Patch) -> Maybe (Patch,Patch)

	xcommute _ (p1,p2) -- Deal with common case
		...
	xcommute True (Merger True g _ _ p1 p2, pA) ...
	xcommute True (pA, Merger True g _ _ p1 p2) ...
		...

	commute = xcommute True
	commute_no_merger = xcommute False

and passing down the Bool parameter when recursing? Admittedly, I have an
overly strong aversion to duplicated code. (Maybe there's some fancy monad
technique you can use to be even trendier, but I don't grok monads yet)

Cheers,
aj

-- 
Anthony Towns <aj at humbug.org.au> <http://azure.humbug.org.au/~aj/>
Don't assume I speak for anyone but myself. GPG signed mail preferred.

``[S]exual orgies eliminate social tensions and ought to be encouraged.''
      -- US Supreme Court Justice Antonin Scalia (http://tinyurl.com/3kwod)
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: Digital signature
Url : http://lists.osuosl.org/pipermail/darcs-devel/attachments/20041003/7f06e253/attachment.pgp