On Sun, Oct 03, 2004 at 11:16:12PM +1000, Anthony Towns wrote:
> 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.
Yes, that would be a better way of going about this.
> > > 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?
Oh, I misread, and was getting the argument order wrong! What you wrote was
right, but was wrong haskell, since you used "p" for two bindings, it
should be
commute (ChangePref p1 f1 t1, ChangePref p2 f2 t2) | p1 == p2 = Nothing
> > 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.
Right, so depending on the order something like a merger needs to be
created. i.e. we need new commutation rules of some sort, so that a
"failing" commute can instead create a merger (or whatever replaces
mergers).
> 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. :(
Argh, this sound similar to how originally I wanted mergers to work. I
couldn't get it to actually work though. Anything I could come up with
would give a different result under some obscure combination of merges
(which would be quite bad). :(
> > 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. :)
:)
This is actually somewhat similar to how mergers work, except that they
don't try to "resolve" or "mark" the conflict in any way, mostly because
that was something I wasn't able to come up with a way of doing
consistently.
> > 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.
Right, but it would be nice if we could make most common merge conflicts
*not* take exponential time. For example, if one user makes many edits to
a file which another user deletes, to a human the merge is quite simple to
understand, but darcs fails horribly on it. :( But yes, I'm all right with
risking exponential explosions... I'd just prefer that it really only
happen in corner cases.
> > > 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.
:) Great!
> 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?
Mostly, I'm not sure, but the Bool approach might not be as fast, and the
speed of commute (and commute_no_merger) is critically important.
Predicting the efficiency of a given code with ghc is almost impossible. I
don't really know, though, and after a few clumsy attempts to optimize
things (some of which actually helped), I've mostly left the code
untouched.
In particular, the commute_no_merger was added quite late in the game...
> 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)
Indeed, duplicated code is indeed bad, and that code is really ugly. It's
been a long time since I've looked at the commute code, and now that I look
at it, there's more than just this improvement to be made. But of course,
none of it should be touched until after darcs 1.0.0 is released (I know, I
keep saying that...).
--
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/20041009/b6b1c231/attachment.pgp