Ben Franksen | 3 Mar 03:30 2012
Picon

darcs cannot apply some patch bundles

Hi Experts

I recently had a situation where I could not apply a patch bundle created 
using darcs send because darcs apply complained about a missing patch in the 
repo. So I pulled the missing patch, could apply the bundle, and then 
obliterated the patch I just pulled. So, obviously the bundle did not depend 
on teh missing patch, so why did darcs not allow me to apply it?

Is this behaviour intended and if yes why and if not is it a bug or a 
technical limitation?

Thanks
Ben
Eric Kow | 3 Mar 08:08 2012
Picon

Re: darcs cannot apply some patch bundles

Hi Ben,

On 3 Mar 2012, at 02:30, Ben Franksen wrote:
> I recently had a situation where I could not apply a patch bundle created 
> using darcs send because darcs apply complained about a missing patch in the 
> repo. So I pulled the missing patch, could apply the bundle, and then 
> obliterated the patch I just pulled. So, obviously the bundle did not depend 
> on teh missing patch, so why did darcs not allow me to apply it?

This question would make a nice FAQ.  I couldn't find any written-up discussions specifically on it
(ideally, on http://wiki.darcs.net/FAQ), but I did manage to dig up this old discussion on IRC:

http://irclog.perlgeek.de/darcs/2011-05-12#i_3723753

(Assuming I didn't get it wrong myself)
It's a subtle limitation in Darcs, and a UI hole that people fall through :-(

Basically the issue is that for Darcs to know whether or not it needs a patch, it needs a representation of the
patch.  Compare darcs pull and darcs apply.  They both do  the same thing patch-theory wise, except that in
the case of darcs pull, missing patches can be retrieved from the remote repo (if only to be commuted out and
discarded).  Darcs apply can't do this retrieving, hence the long approach you use.

For me, what's a bit upsetting about this limitation is that it undermines people's confidence in
cherry-picking, even though cherry-picking is actually innocent here.

Is this explanation clear?  I'll hold off on exploring 3 rough ideas on how darcs could make this better until
I or somebody else has taken the time to try and write this up for future use.

Thanks,

(Continue reading)

Eric Kow | 3 Mar 20:54 2012
Picon

Re: darcs cannot apply some patch bundles

Hi again,

On 3 Mar 2012, at 07:08, Eric Kow wrote:
> 
> On 3 Mar 2012, at 02:30, Ben Franksen wrote:
>> I recently had a situation where I could not apply a patch bundle created 
>> using darcs send because darcs apply complained about a missing patch in the 
>> repo. So I pulled the missing patch, could apply the bundle, and then 
>> obliterated the patch I just pulled. So, obviously the bundle did not depend 
>> on teh missing patch, so why did darcs not allow me to apply it?
> 
> This question would make a nice FAQ.  I couldn't find any written-up discussions specifically on it
(ideally, on http://wiki.darcs.net/FAQ), but I did manage to dig up this old discussion on IRC:

OK, I wrote this up in
  http://wiki.darcs.net/FAQ#why-does-darcs-apply-force-me-to-get-unrelated-dependencies

Hope it helps.

See also http://bugs.darcs.net/issue2150 for a placeholder ticket about improving this.

Thanks and sorry,

Eric

PS: any corrections, darcs devs?

--

-- 
Eric Kow <http://erickow.com>

(Continue reading)

Ben Franksen | 4 Mar 13:28 2012
Picon

Re: darcs cannot apply some patch bundles

Hi Eric

thanks for explaining and adding the FAQ entry.

Eric Kow wrote:
> On 3 Mar 2012, at 07:08, Eric Kow wrote:
>> On 3 Mar 2012, at 02:30, Ben Franksen wrote:
>>> I recently had a situation where I could not apply a patch bundle
>>> created using darcs send because darcs apply complained about a missing
>>> patch in the repo. So I pulled the missing patch, could apply the
>>> bundle, and then obliterated the patch I just pulled. So, obviously the
>>> bundle did not depend on teh missing patch, so why did darcs not allow
>>> me to apply it?
>> 
>> This question would make a nice FAQ.  I couldn't find any written-up
>> discussions specifically on it (ideally, on http://wiki.darcs.net/FAQ),
>> but I did manage to dig up this old discussion on IRC:
> 
> OK, I wrote this up in
>   http://wiki.darcs.net/FAQ#why-does-darcs-apply-force-me-to-get-
unrelated-dependencies
> 
> Hope it helps.

Yes, thanks you.

> See also http://bugs.darcs.net/issue2150 for a placeholder ticket about
> improving this.

As far as I am concerned, the 'darcs send computes minimal context' solution 
(Continue reading)

Eric Kow | 5 Mar 09:09 2012
Picon

Re: darcs cannot apply some patch bundles


On 4 Mar 2012, at 12:28, Ben Franksen wrote:
> As far as I am concerned, the 'darcs send computes minimal context' solution 
> would be perfect. But I have no idea how difficult that is (both for the 
> darcs developers and then for darcs). For a compromise, maybe some 
> approximation of 'minimal' would be good enough in practice.

Ah yes, I think I remember that one issue is that computing the minimal context is actually expensive.

I wonder what Darcs could compute that would a useful “smaller context”.  Maybe since Darcs already
bases the bundle off the latest shared tag between sender and trunk (don't quote me on this, just a guess),
it could just be minimal-assuming-that-latest-tag?

--

-- 
Eric Kow <http://erickow.com>

_______________________________________________
darcs-users mailing list
darcs-users <at> darcs.net
http://lists.osuosl.org/mailman/listinfo/darcs-users
Florent Becker | 5 Mar 11:08 2012

Re: darcs cannot apply some patch bundles

Le 05/03/2012 09:09, Eric Kow a écrit :
> 
> On 4 Mar 2012, at 12:28, Ben Franksen wrote:
>> As far as I am concerned, the 'darcs send computes minimal context' solution 
>> would be perfect. But I have no idea how difficult that is (both for the 
>> darcs developers and then for darcs). For a compromise, maybe some 
>> approximation of 'minimal' would be good enough in practice.
> 
> Ah yes, I think I remember that one issue is that computing the minimal context is actually expensive.
> 
> I wonder what Darcs could compute that would a useful “smaller context”.  Maybe since Darcs already
bases the bundle off the latest shared tag between sender and trunk (don't quote me on this, just a guess),
it could just be minimal-assuming-that-latest-tag?
> 
> 
We can also start computing the minimal context and let the user use
Ctrl-C (or another key combination) to send the patch now in a
not-quite-minimal context if computing the minimal context takes too long.

Florent
Michael Hendricks | 5 Mar 17:18 2012

Re: darcs cannot apply some patch bundles

On Mon, Mar 5, 2012 at 1:09 AM, Eric Kow <eric.kow <at> gmail.com> wrote:
>
> On 4 Mar 2012, at 12:28, Ben Franksen wrote:
>> As far as I am concerned, the 'darcs send computes minimal context' solution
>> would be perfect. But I have no idea how difficult that is (both for the
>> darcs developers and then for darcs). For a compromise, maybe some
>> approximation of 'minimal' would be good enough in practice.
>
> Ah yes, I think I remember that one issue is that computing the minimal context is actually expensive.

Since I'm not yet familiar with Darcs' internal workings, can someone
help me understand why calculating a minimal context is so expensive?
Is it because Darcs doesn't have quick access to patch summaries and
must load every patch, in its entirety, from disk to perform a
commutation?

If that's the reason, is it possible to store patch summaries (like
"hunk ./src/Darcs/Repository/Merge.hs 83 -1 +1") in the inventory
files?  To my naive understanding, it seems that many commutations
could be calculated with just those summaries.

Thanks for any insight.

--
Michael
Owen Stephens | 5 Mar 18:05 2012
Picon

Re: darcs cannot apply some patch bundles

On 5 March 2012 16:18, Michael Hendricks <michael <at> ndrix.org> wrote:
>Since I'm not yet familiar with Darcs' internal workings, can someone
>help me understand why calculating a minimal context is so expensive?

Because you need to do a whole bunch of commutes - working out which of *all*
the patches in the repository cleanly commute past a given patch.

>Is it because Darcs doesn't have quick access to patch summaries and
>must load every patch, in its entirety, from disk to perform a
>commutation?

Yeah, I think that's pretty much it.

>If that's the reason, is it possible to store patch summaries (like
>"hunk ./src/Darcs/Repository/Merge.hs 83 -1 +1") in the inventory
>files?  To my naive understanding, it seems that many commutations
>could be calculated with just those summaries.

Many, yes, but not all - you'd still sometimes need both, for example commuting a
replace patch and a hunk (you'd need to know if the replace affected the hunk).

e.g. consider commuting p1 and p2, where file1 initially consists of just
"A" and p2 duplicates file1's line:
p1 = replace file1 A B
p2 = hunk file1 2 +B

These commute to
p2' = hunk file1 2 +A
p1' = replace A B

But you wouldn't be able to calculate that, just knowing the summary of p2. I've
attached a shell script that demonstrates that it works (unpulling the replace
causes the commute).

In fact, storing a "summary" is what mornfall's GSoC project did for v3
primitive patches, exactly so that in non-conflicting cases, we can commute
hunk-patches *without* loading the entire patch, but that work isn't merged
into Darcs yet...

Cheers,
Owen.

Attachment (unpull_replace.sh): application/x-sh, 356 bytes
_______________________________________________
darcs-users mailing list
darcs-users <at> darcs.net
http://lists.osuosl.org/mailman/listinfo/darcs-users
Ganesh Sittampalam | 6 Mar 07:15 2012
Picon

Re: darcs cannot apply some patch bundles

On 05/03/2012 17:05, Owen Stephens wrote:
> On 5 March 2012 16:18, Michael Hendricks <michael <at> ndrix.org
> <mailto:michael <at> ndrix.org>> wrote:
>>Since I'm not yet familiar with Darcs' internal workings, can someone
>>help me understand why calculating a minimal context is so expensive?
> 
> Because you need to do a whole bunch of commutes - working out which of
> *all*
> the patches in the repository cleanly commute past a given patch.
> 
>>Is it because Darcs doesn't have quick access to patch summaries and
>>must load every patch, in its entirety, from disk to perform a
>>commutation?
> 
> Yeah, I think that's pretty much it.

It's also that, whether or not you have the patch data, the naive
algorithm is O(n^2) to commute the minimal context of a single patch,
and I don't know a more sophisticated one (though I have some vague ideas).

Consider a repo ABCDEF, and you want to calculate the minimal context of
F. First you commute F past E, and that succeeds so you can drop E. I'm
ignoring the fact that the representation changes as you do it:

ABCDF

Now you try D. That fails. Now you need to try C. But to try C, you
first have to commute it past D. So now what we really have is a list of
patches we need to try to commute everything else past:

ABC|DF

In general the lists on the left-hand side and right-hand side of the |
may be O(n), so each operation to reduce the list on the left by 1 is
O(n) and the whole job is O(n^2).

In practice it may be that the list on the right doesn't grow too much,
but I actually tried this on the darcs repo itself a while back and it
did seem to be quite slow in practice.

Ganesh
Michael Hendricks | 6 Mar 16:12 2012

Re: darcs cannot apply some patch bundles

On Mon, Mar 5, 2012 at 11:15 PM, Ganesh Sittampalam <ganesh <at> earth.li> wrote:
> It's also that, whether or not you have the patch data, the naive
> algorithm is O(n^2) to commute the minimal context of a single patch,
> and I don't know a more sophisticated one (though I have some vague ideas).

That makes sense.  I wonder if Eric's suggestion to only consider
patches not in a tag makes O(n^2) feasible.  Roughly how many commutes
per second can Darcs handle?  100, thousand, ten thousand?  If n were
too large, Darcs could always fall back to the current behavior.

> Consider a repo ABCDEF, and you want to calculate the minimal context of
> F. First you commute F past E, and that succeeds so you can drop E. I'm
> ignoring the fact that the representation changes as you do it:
>
> ABCDF
>
> Now you try D. That fails. Now you need to try C. But to try C, you
> first have to commute it past D. So now what we really have is a list of
> patches we need to try to commute everything else past:

When generating a patch bundle, it seems that minimal context is more
aggressive than we need.  A "reduced context" might be sufficient.  I
imagine just commuting F backwards until it fails to commute or it
reaches a tag.  That would be O(n) and probably removes most patches
that are obviously not relevant to the context.

In my typical workflow (with Darcs or other VCS), my local repository
is only a couple dozen patches ahead of the upstream repository.  Most
of those patches are entirely independent of each other.  In that
scenario, the "reduced context" sounds quite effective.

--
Michael
Ganesh Sittampalam | 6 Mar 19:24 2012
Picon

Re: darcs cannot apply some patch bundles

On 06/03/2012 15:12, Michael Hendricks wrote:
> On Mon, Mar 5, 2012 at 11:15 PM, Ganesh Sittampalam <ganesh <at> earth.li> wrote:
>> It's also that, whether or not you have the patch data, the naive
>> algorithm is O(n^2) to commute the minimal context of a single patch,
>> and I don't know a more sophisticated one (though I have some vague ideas).
> 
> That makes sense.  I wonder if Eric's suggestion to only consider
> patches not in a tag makes O(n^2) feasible.  Roughly how many commutes
> per second can Darcs handle?  100, thousand, ten thousand?  If n were
> too large, Darcs could always fall back to the current behavior.

> When generating a patch bundle, it seems that minimal context is more
> aggressive than we need.  A "reduced context" might be sufficient.  I
> imagine just commuting F backwards until it fails to commute or it
> reaches a tag.  That would be O(n) and probably removes most patches
> that are obviously not relevant to the context.

Yes, I agree it would be fine just to consider some subset of patches
for this use case using whatever heuristic, and I think that e.g. 100
patches would be absolutely fine. The only difficulty is picking a
heuristic that won't cause fresh confusion when it doesn't work out.

Ganesh
Owen Stephens | 6 Mar 21:53 2012
Picon

Re: darcs cannot apply some patch bundles

On 06/03/12 at 06:24pm, Ganesh Sittampalam wrote:
> On 06/03/2012 15:12, Michael Hendricks wrote:
> > When generating a patch bundle, it seems that minimal context is more
> > aggressive than we need.  A "reduced context" might be sufficient.  I
> > imagine just commuting F backwards until it fails to commute or it
> > reaches a tag.  That would be O(n) and probably removes most patches
> > that are obviously not relevant to the context.
>
> Yes, I agree it would be fine just to consider some subset of patches
> for this use case using whatever heuristic, and I think that e.g. 100
> patches would be absolutely fine. The only difficulty is picking a
> heuristic that won't cause fresh confusion when it doesn't work out.
Warning: Thinking out loud!

I wonder if a useful user-provided flag would be:

  darcs send --reduce-context-to 'date: -5 days'

or

  darcs send --reduce-context-to 'patch: my-patch-I-think-you-have'

which would attempt to remove the patches since a given date or patch (or other
matcher), failing if it wasn't possible (perhaps just a warning?), or if a tag
was encountered first.

I guess the obvious flaw is that it'd be quite easy to forget the flag when
sending, rendering the whole thing pointless. Maybe an interactive prompt would
be better?

Having proposed it, I'm not sure I like the idea much though - it feels like
the sort of thing that a user might question with "Why do I have to pick an
arbitrary point in history? Why isn't Darcs doing this for me?".

--
Owen.

_______________________________________________
darcs-users mailing list
darcs-users <at> darcs.net
http://lists.osuosl.org/mailman/listinfo/darcs-users
Ben Franksen | 8 Mar 00:59 2012
Picon

Re: darcs cannot apply some patch bundles

Ganesh Sittampalam wrote:
> On 05/03/2012 17:05, Owen Stephens wrote:
>> On 5 March 2012 16:18, Michael Hendricks <michael <at> ndrix.org
>> <mailto:michael <at> ndrix.org>> wrote:
>>>Since I'm not yet familiar with Darcs' internal workings, can someone
>>>help me understand why calculating a minimal context is so expensive?
>> 
>> Because you need to do a whole bunch of commutes - working out which of
>> *all*
>> the patches in the repository cleanly commute past a given patch.
>> 
>>>Is it because Darcs doesn't have quick access to patch summaries and
>>>must load every patch, in its entirety, from disk to perform a
>>>commutation?
>> 
>> Yeah, I think that's pretty much it.
> 
> It's also that, whether or not you have the patch data, the naive
> algorithm is O(n^2) to commute the minimal context of a single patch,
> and I don't know a more sophisticated one (though I have some vague
> ideas).
> 
> Consider a repo ABCDEF, and you want to calculate the minimal context of
> F. First you commute F past E, and that succeeds so you can drop E. I'm
> ignoring the fact that the representation changes as you do it:
> 
> ABCDF
> 
> Now you try D. That fails. Now you need to try C. But to try C, you
> first have to commute it past D. So now what we really have is a list of
> patches we need to try to commute everything else past:
> 
> ABC|DF
> 
> In general the lists on the left-hand side and right-hand side of the |
> may be O(n), so each operation to reduce the list on the left by 1 is
> O(n) and the whole job is O(n^2).
> 
> In practice it may be that the list on the right doesn't grow too much,
> but I actually tried this on the darcs repo itself a while back and it
> did seem to be quite slow in practice.

Hey Ganesh

thank you very much for the explanation. The problem is a lot clearer to me 
now.

I wonder if this process could be optimized somehow.

What darcs could at least do, I think, is to cache whether two patches 
commute or not. Darcs already has a global cache for patches, why not add a 
global cache for commutability/dependency information?

For instance, every time I try to amend-record a patch from somewhere in the 
past, darcs seems to calculate some patch dependencies, so it can tell me 
whether the amend is possible.

I have often wished for a graphical tool for viewing the dependencies (or 
maybe the opposite i.e. commutability) between patches. Such a tool could 
also contribute to the global cache, speeding up future requests.

Just raw ideas, of course.

Cheers
Ben
Ben Franksen | 6 Mar 01:29 2012
Picon

Re: darcs cannot apply some patch bundles

Eric Kow wrote:
> On 4 Mar 2012, at 12:28, Ben Franksen wrote:
>> As far as I am concerned, the 'darcs send computes minimal context'
>> solution would be perfect. But I have no idea how difficult that is (both
>> for the darcs developers and then for darcs). For a compromise, maybe
>> some approximation of 'minimal' would be good enough in practice.
> 
> Ah yes, I think I remember that one issue is that computing the minimal
> context is actually expensive.
> 
> I wonder what Darcs could compute that would a useful “smaller context”. 
> Maybe since Darcs already bases the bundle off the latest shared tag
> between sender and trunk (don't quote me on this, just a guess), it could
> just be minimal-assuming-that-latest-tag?

Yup, that is exactly what I was thinking of. So darcs would only need to 
calculate dependencies for the patches that are not in the latest tag, which 
is usually orders of magnitude less than the whole repo. It is not perfect, 
of course, but it would still be a noticeable improvement for usability.

Cheers
Ben

_______________________________________________
darcs-users mailing list
darcs-users <at> darcs.net
http://lists.osuosl.org/mailman/listinfo/darcs-users

Gmane