[darcs-devel] Bug in commute / ChangePref?

[David Roundy]

On Fri, Oct 01, 2004 at 05:00:02PM +1000, Anthony Towns wrote:
> On Thu, Sep 30, 2004 at 02:34:30AM -0400, Andrew Pimlott wrote:
> > On Thu, Sep 30, 2004 at 05:49:56AM +1000, Anthony Towns wrote:
> > > I'm trying to understand the way commute's meant to work. One thing that
> > > I don't understand is the behaviour for ChangePref commuting. As far as I
> > > can see, if you have:
> > > 	ChangePref boringfile foo bar ; ChangePref boringfile bar baz
> > > then you shouldn't be able to commute, but afaics darcs thinks you
> > > can.
> > David decided nobody's ever going to notice what you noticed.
> >     http://abridgegame.org/darcs/manual/node7.html#SECTION00762000000000000000
> 
> Ah, that makes sense. Seems like the main point would be to let you pull
> the "ChangePref boringfile bar baz" patch without having to bother
> getting to "foo bar" patch first, which seems useful.

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.

It may be possible to change this, so setprefs commute right, but it'd
definitely be a job for post-1.0.0 (since it'd be tricky making sure that
old repositories don't become "corrupt" just because they don't conform to
the new commutation rules).

> 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

Composite patches wouldn't be a problem, since their commutation is defined
recursively.  :)

> > I agree that it makes more sense to make setprefs versioned "correctly",
> > but you would at least have to make conflict resolution work, and there
> > might be more to it.
> 
> Hrm; you ought to be able to just say "mergers choose one of the
> ChangePrefs" rather than putting both conflicting bits of information in
> the tree itself; something like:
> 
> 	merger 0.1
> 	setpref foo left middle
> 	setpref foo left right
> 
> which behaves the same as "setpref foo left middle" except when commuting
> with "setpref foo middle right", in which case they'd need to change to:
> 
> 	setpref foo left right
> 
> 	merger 0.1
> 	setpref foo right right
> 	setpref foo right middle
> 
> (And obviously it'd need to swap back when SP(f,l,r) commutes with
> M(SP(f,r,r),SP(f,r,m)).)

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).

> You could just as easily create the "merger" when commuting, but that'd
> commute "A,B" to "B,no-op". Well, strictly it'd be "no-op(A,B)", which
> is to say "a no-op that commutes with B to become A". That seems workable,
> but I'm not sure if it'd be good or not. If you had:
> 
> 	hunk file 1..; setpref x "" a; hunk file 5...; setpref x a b
> 
> it'd commute to:
> 
> 	setpref x "" b; hunk file 1..; no_op(setpref x "" a, sepref x "" b); 
> 		hunk file 5...
>
> and let you just grab `setpref x "" b' which is kind-of what you want. But
> if you later grabbed the `Set x pref to a!' patch, it'd do nothing. I
> guess that's required by the theory, but it seems kinda counter-intuitive.
> 
> I guess the implication for other things that don't commute would be to
> handle them like:
> 
> 	commute( A, H )      (A = addfile f, H = hunk f ...)
> 
> 	= [A, H], noop(A, [A, H])
> 
> which would have the effect of collating all the patches you need if you
> want to pull "H", which isn't an outrageous thing to do. But it's pretty
> "eww" though.

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.)

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.

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, 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.

> 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... :)
-- 
David Roundy
http://www.abridgegame.org
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://lists.osuosl.org/pipermail/darcs-devel/attachments/20041002/99585b28/attachment.pgp