Issue 1208 wish: darcs trackdown --bisect

Title wish: darcs trackdown --bisect
Priority feature Status resolved
Milestone Resolved in
Superseder Nosy List darcs-devel, dixiecko, dmitry.kurochkin, fis, jaredj, kowey, thorkilnaur, twb
Assigned To fis
Topics ProbablyEasy

Created on 2008-11-06.22:59:48 by kowey, last changed 2010-04-04.17:47:08 by kowey.

File name Uploaded Type Edit Remove
issue1208-bisect-patch-with-unsafeFL-removed.dpatch dixiecko, 2009-11-21.21:37:41 text/x-darcs-patch
msg6611 (view) Author: kowey Date: 2008-11-06.22:59:46
msg6612 (view) Author: droundy Date: 2008-11-07.15:35:53
I think a better option for trackdown (which never did get much attention) would
be to use the delta debugging approach, which is a generalization of the
bisection approach that works with sets of changes rather than a linear sequence
of versions.
msg6613 (view) Author: kowey Date: 2008-11-07.15:39:47
For the interested, I think it was Jason that first told me about Delta
Debugging.  I didn't fully understand it, but it sure sounded cool:
msg6683 (view) Author: twb Date: 2008-11-17.03:29:03
+1, this would be useful for me.
msg8329 (view) Author: kowey Date: 2009-08-21.23:50:02
I think we need somebody to write up a description of how delta debugging would
work in a darcs trackdown setting.
msg8911 (view) Author: kowey Date: 2009-10-06.08:03:59
I've split the Delta Debugging stuff into a new ticket, issue1638.

While I imagine that Delta Debugging would be really very cool, I don't want us
to get stuck on it when we could very easily implement bisection, which would
already be useful on its own.

I'm also bumping the priority and marking this easy because I think it's
localised to just the trackdown command.
msg9343 (view) Author: fis Date: 2009-11-15.17:58:45
Radoslav and me are working on this, patch is on the way...
msg9373 (view) Author: fis Date: 2009-11-15.20:06:14
it is done.  it's not pretty, and it's cheating with unsafeUnFL/RL, but it does
what it is supposed to do on our test cases.  if you reject it please be nice
about it.  i know unsafeUnFL/RL needs to be eliminated, but my brain is not
working any more, and i need to be told that we've done something useful today.  :-)
msg9386 (view) Author: dixiecko Date: 2009-11-16.10:02:20
As we discussed at vienna sprint, it seems it would be the best re-write it
using builtin Haskell Tree data structure, what can make it more readable/correct.
msg9387 (view) Author: fis Date: 2009-11-16.10:12:23
hi radoslav, look at the patch: i did that already.  (-:

sorry i didn't notify you explicitly any more.  after we found the
error and we fixed it, i did some clean-up and committed everything we
did as a single patch.

but it still needs to be rewritten.  see FIXME paragraph in the latex
documentation in the same file.

now i'm back at work.  i'll get back to this later this week.  feel
free to steal the work away from me!  :) or ask me if you think i can
help you.


On Mon, Nov 16, 2009 at 10:02:22AM +0000, Radoslav Dorcik wrote:
> To: darcs-devel@darcs.net, dixiecko@gmail.com, dmitry.kurochkin@gmail.com,
> 	jjenning@fastmail.fm, kowey@darcs.net,
> 	mf-hcafe-15c311f0c@etc-network.de, naur@post11.tele.dk,
> 	trentbuck@gmail.com
> From: Radoslav Dorcik <bugs@darcs.net>
> Date: Mon, 16 Nov 2009 10:02:22 +0000
> Subject: [issue1208] wish: darcs trackdown --bisect
> Radoslav Dorcik <dixiecko@gmail.com> added the comment:
> As we discussed at vienna sprint, it seems it would be the best re-write it
> using builtin Haskell Tree data structure, what can make it more readable/correct.
> __________________________________
> Darcs bug tracker <bugs@darcs.net>
> <http://bugs.darcs.net/issue1208>
> __________________________________
>  ** ACCEPT: CRM114 PASS osb unique microgroom Matcher **
> CLASSIFY succeeds; success probability: 0.9471  pR: 1.2531
> Best match to file #0 (nonspam.css) prob: 0.9471  pR: 1.2531
> Total features in input file: 2048
> #0 (nonspam.css): features: 761191, hits: 2639451, prob: 9.47e-01, pR:   1.25
> #1 (spam.css): features: 1678863, hits: 2969065, prob: 5.29e-02, pR:  -1.25
msg9438 (view) Author: dixiecko Date: 2009-11-21.21:37:41
Hi, here is updated patch without unsafeFL, now bisect functionality uses FL
instead of []. The True/False flag in generate method parameters have to remain
because FL/RL types itsef can not replace that information included in
True/False flag. 

Actually this thing was one in your TODO. I hope I'll find the time to create
also module tests (or automatic tests) for bisect.
msg9521 (view) Author: fis Date: 2009-12-02.21:12:52
hi, http://bugs.darcs.net/patch106 obsoletes all other patches posted here
earlier, and is in my opinion ready for review:

 - i took radoslav's improved generate function, massaged it a bit more, 
   and now it's quite easy to read and compliant with the GADT

 - i added a unit test script and repositories.

--match, --last, etc. are still missing, but i think that should be a new
patch that can be reviewed independently.  (i'm currently looking at
how diff does it, and i think i can just copy a few lines from there.
any opinions on that approach?)

thanks / cheers,
msg9522 (view) Author: fis Date: 2009-12-02.21:14:54
(i changed the status to "waiting-for".  not sure if this means "needs review"?)
msg10664 (view) Author: kowey Date: 2010-04-04.17:47:07
Resolved with this patch (but our auto-resolver got confused by the dash).

Congrats to Rado and Matthias.  I think darcs trackdown just became more
useful :-)

Mon Mar 29 23:10:33 BST 2010  dixiecko@gmail.com
  * resolve-issue1208: trackdown --bisect (PatchTree).
Date User Action Args
2008-11-06 22:59:48koweycreate
2008-11-07 15:35:56droundysetstatus: unread -> unknown
nosy: + droundy
messages: + msg6612
2008-11-07 15:39:49koweysetnosy: droundy, kowey, dagit, simon, thorkilnaur, dmitry.kurochkin
messages: + msg6613
2008-11-17 03:29:05twbsetnosy: + twb
messages: + msg6683
2009-08-06 18:01:46adminsetnosy: + markstos, jast, Serware, darcs-devel, zooko, mornfall, tommy, beschmi, - droundy, twb
2009-08-06 21:14:01adminsetnosy: - beschmi
2009-08-10 21:50:42adminsetnosy: + twb, - tommy, markstos, darcs-devel, zooko, jast, Serware, mornfall
2009-08-10 23:50:50adminsetnosy: - dagit
2009-08-21 23:50:04koweysetstatus: unknown -> needs-reproduction
nosy: kowey, simon, twb, thorkilnaur, dmitry.kurochkin
messages: + msg8329
2009-08-25 17:33:50adminsetnosy: + darcs-devel, - simon
2009-08-27 14:29:02adminsetnosy: kowey, darcs-devel, twb, thorkilnaur, dmitry.kurochkin
2009-10-06 08:04:05koweysetpriority: wishlist -> feature
status: needs-reproduction -> needs-implementation
topic: + ProbablyEasy
messages: + msg8911
nosy: + jaredj
2009-11-15 17:58:48fissetnosy: + fis
messages: + msg9343
assignedto: fis
2009-11-15 18:00:08fissetnosy: + dixiecko
2009-11-15 20:05:00fislinkpatch86 issues
2009-11-15 20:06:16fissetmessages: + msg9373
2009-11-16 10:02:22dixieckosetmessages: + msg9386
2009-11-16 10:12:25fissetmessages: + msg9387
2009-11-21 21:37:43dixieckosetfiles: + issue1208-bisect-patch-with-unsafeFL-removed.dpatch
messages: + msg9438
2009-12-02 21:09:29fislinkpatch106 issues
2009-12-02 21:12:54fissetmessages: + msg9521
2009-12-02 21:14:56fissetstatus: needs-implementation -> waiting-for
messages: + msg9522
2010-03-23 19:45:11koweysetstatus: waiting-for -> has-patch
2010-04-04 17:47:08koweysetstatus: has-patch -> resolved
messages: + msg10664