darcs

Issue 1514 minimal context function

Title minimal context function
Priority feature Status has-patch
Milestone 2.8.0 Resolved in
Superseder Nosy List alex.aegf, alrunner4, darcs-devel, dmitry.kurochkin, ganesh, kowey, mndrix, thorkilnaur, tux_rocker
Assigned To alex.aegf
Topics

Created on 2009-08-07.15:51:58 by kowey, last changed 2014-07-23.14:50:16 by gh.

Messages
msg8046 (view) Author: kowey Date: 2009-08-07.15:51:56
Note that we may also have to have some conventions for canonical order for
cases where patches just commute.
msg8811 (view) Author: kowey Date: 2009-09-14.13:25:19
If I follow Ganesh correctly, he was working on this last and that the sticking
point is Darcs 2 allowing stupid unpull tricks whereby a patch can have
different dependencies due to duplicates.
msg8818 (view) Author: ganesh Date: 2009-09-14.20:48:12
There are two problems, in fact.

The first is that calculating the minimal context for a single patch added to
the end of a repo (which already has the hashes of minimal contexts stored for
existing patches) is O(n^2) and this hurts in practice. I have some ideas for
speeding this up but I think it's a hard problem.

The second is the unpull tricks you can play using duplicate patches in darcs-2
semantics, as you mention. That problem can be solved in a reasonable manner,
but at the expense of only including primitive patch dependencies in the hash of
a patch.
msg11493 (view) Author: tux_rocker Date: 2010-06-20.13:43:06
I bump the release to 2.6 because I presume this is not going to happen
before darcs 2.5. Please adjust the milestone if you have a good reason
to do so.
msg15209 (view) Author: kowey Date: 2012-03-06.07:27:44
More elaboration from Ganesh for what makes minimal context expensive: 
http://lists.osuosl.org/pipermail/darcs-users/2012-March/026406.html
msg15211 (view) Author: kowey Date: 2012-03-06.07:41:26
Another issue perhaps: for current darcs send, you need not just a 
minimal context for a single patch, but for a single minimal context for 
a set of potentially unrelated patches.

Wouldn't that be a bit tricky? Naive algorithm might be: commute patches 
backwards to compute minimal context separately for each one of the 
patches, take union of the contexts, then commute each patch forwards 
until it fits into the union-context again.  :-/

(Minimal context still has lots of uses outside of send, if I remember 
correctly, just thinking about this over breakfast)
msg15212 (view) Author: kowey Date: 2012-03-06.07:46:20
Ignore me, I was talking nonsense. I forgot that once you have the minimal 
context for the bottom-most patch, you're sorted.
History
Date User Action Args
2009-08-07 15:51:58koweycreate
2009-08-07 15:52:31koweylinkissue1261 superseder
2009-08-18 14:59:16koweysetstatus: unread -> needs-implementation
nosy: kowey, simon, thorkilnaur, dmitry.kurochkin
topic: + Target-2.4
2009-08-22 12:53:48koweylinkissue927 superseder
2009-08-22 12:54:39koweyunlinkissue1261 superseder
2009-08-23 01:00:25koweylinkissue831 superseder
2009-08-25 18:14:19adminsetnosy: + darcs-devel, - simon
2009-08-27 14:29:55adminsetnosy: kowey, darcs-devel, thorkilnaur, dmitry.kurochkin
2009-09-14 10:50:04koweysettopic: + Target-2.5, - Target-2.4
nosy: kowey, darcs-devel, thorkilnaur, dmitry.kurochkin
2009-09-14 13:23:56koweylinkissue1608 superseder
2009-09-14 13:25:22koweysetstatus: needs-implementation -> has-patch
nosy: + ganesh
messages: + msg8811
assignedto: ganesh
2009-09-14 20:48:14ganeshsetnosy: kowey, darcs-devel, ganesh, thorkilnaur, dmitry.kurochkin
messages: + msg8818
2009-09-30 21:32:39koweylinkissue1630 superseder
2010-06-15 20:51:51adminsetmilestone: 2.5.0
2010-06-15 20:59:09adminsettopic: - Target-2.5
2010-06-20 13:43:07tux_rockersetnosy: + tux_rocker
messages: + msg11493
milestone: 2.5.0 -> 2.8.0
2012-03-06 07:27:45koweysetmessages: + msg15209
2012-03-06 07:41:28koweysetmessages: + msg15211
2012-03-06 07:46:20koweysetmessages: + msg15212
2012-03-06 14:44:26mndrixsetnosy: + mndrix
2013-01-16 03:19:44alrunner4setnosy: + alrunner4
2014-07-23 14:50:16ghsetassignedto: ganesh -> alex.aegf
nosy: + alex.aegf