Wed Dec  2 21:56:29 CET 2009  mf-hcafe-15c311f0c@etc-network.de
  * resolve issue1208: trackdown --bisect (complete branches only).

Attachments

• resolve-issue1208_-trackdown-__bisect-_complete-branches-only__.dpatch
• unnamed

The implementation of this looks pretty good to me - easy to read and minimally
invasive.

Unfortunately, it breaks the type witnesses build, because it completely ignores
them, specifically in this type and all the code surrounding it:

> type PatchTree p = Tree (Either (FL p) (RL p))

I think the right solution is simply to use our own tree type that does respect
witnesses - in particular the Forest constructor would use an FL rather than a
[], and PatchTree itself would be something like this:

type PatchTree p C(x y) = OurTree (OurEither (FL p) (RL p)) C(x y)

Annoyingly we'd need our own Either type too because the kinds would be wrong
otherwise.

I just spent a little while looking at adding witnesses to this, and I think
it's actually a bit tricky because of the way the tree structure is defined.
Also, I realised I'm not very keen on the way that a tree is only ever used with
either 0 or 2 children, where the 2 children are always [FL, RL] - I think
defining a special datatype for this would be best, even aside from the
witnesses issue.

I think the feature also requires a test. For one thing this would make it
easier to refactor to improve the data structure.

re the test, I notice that in the issue1208 comments you (fis) mention adding a
unit test - did you forget to add it?

Hello, I updated the original patch from fis:

- added tests (trackdown-bisect.sh)
- added script from fis (used by above test) which generates test repo
- updated message "Oldest patch" -> "Last recent patch"

I'll release in near future next patch which obsoletes this patch and
will replace all data used types with custom types (preparation for GATDs).

please comment, if the tests are right written and not something else
expected.

Attachments

• resolve_issue1208_trackdown_bisect_with_tests_included.dpatch

Hello, I replaced both generic structures:
- Data.Tree
- Either

Attached patch depends on my previous patch with tests:
- resolve_issue1208_trackdown_bisect_with_tests_included.dpatch

New "PatchTree" encanpsulate Either logic using two node constructores
(FLNode and RLNode). Not all things are nice, like that function
"keepSearching" which has been optimalized by fis for algorithm with
generic Data.Tree. I have re-used it with not very nice approach -
passing lambda functions with messy meaning (it is not very readable). 

Anyway I would like to start with GADTs on PatchTree. 
Any suggestions/review comments?

Rado

Attachments

• resolve_issue1208_replace_data_tree.dpatch

On Sun, 7 Mar 2010, Radoslav Dorcik wrote:

> Anyway I would like to start with GADTs on PatchTree.
> Any suggestions/review comments?

GADTs aren't well documented, unfortunately. There's some old stuff here: 
http://wiki.darcs.net/Ideas/GADTPlan

and other than that look in the source of Darcs.Witnesses.Ordered to get 
an idea of how the contexts are threaded around.

I'll try to review what you've done so far within the next few days.

Cheers,

Ganesh

I'm still not very happy with the PatchTree type. Why does it actually
need to have both FL and RL pieces? Also there's an invariant on the
representation which could be expressed in the constructor - either the
list of patches is of length 1 and the list of child trees is of length
0, or the list is of length >1 and the list of child trees is of length 2.

Also, why store a copy of the list of patches as well as the tree? You
can traverse either in the same amount of time, modulo a small and
almost certainly irrelevant constant factor.

Why not something like

data PatchTree p = Leaf p | Fork (PatchTree p) (PatchTree p)

Also, from reading the code it looks like it would report an internal
error if given an empty list of patches to bisect over.

At Thu, 11 Mar 2010 08:06:52 +0000,

Hi Ganesh,

Thanks for review comments. I'll try to re-think existing bi-sect
algorithm. Unforunatelly it will take time :) 

Appart the realization of the patch tree, the algorithm defined is
based on lazy binary tree. Each node represents state within history
of repository. The state here is the "list of applied patches".

Than there is traversing action which moves to given state and execute
test. The outcome of the test defines the next move within binary
tree:
1. If the test == OK    than apply patches (move towards head)
2. If the test == ERROR than unpull patches (move towards first patch ever)

Nothing new here, but what is interesting:
1. The state is temporary repository on file system with some set
of patches applied. Here is unpure nature hidden. 
2. Move operation may be either applying or unpulling the patches.
3. Node within tree have information about the move (list of patches),
   not about the state on filesystem. 

Do you like above approach in general or there is new clever idea ?

See my (probably stupid :)) questions inline related to your comments:

Ganesh Sittampalam wrote:
> Ganesh Sittampalam <ganesh@earth.li> added the comment:
> 
> I'm still not very happy with the PatchTree type. Why does it actually
> need to have both FL and RL pieces? 

I would say that the type of the patch lists defines what to do with
them - if they are for moving forward within history (apply) or back
to big bang (unpull them). This type we needed because the moving
operation is done within child of the parent. If we do the
apply/unpull on the parent, we can use single type (eg. FL). I'll
check it. 

> Also there's an invariant on the
> representation which could be expressed in the constructor - either the
> list of patches is of length 1 and the list of child trees is of length
> 0, or the list is of length >1 and the list of child trees is of length 2.
> 
> Also, why store a copy of the list of patches as well as the tree? You
> can traverse either in the same amount of time, modulo a small and
> almost certainly irrelevant constant factor.
> 
> Why not something like
> 
> data PatchTree p = Leaf p | Fork (PatchTree p) (PatchTree p)

Do you mean here with the "p" the "patch" or the "FL/RL" ?

If the "Fork" is the place where the decision need to be done, question
here is what is the "move" operation afer the test upon current
"state" ? In original implementation the "move" is defined by the list
(RL or LF) of the patches within the node of the child. 

Whan is than meaning of the "Leaf p" ? 
Is it "first patch which breaks the test" ?

Thanks!
Rado

Hi Radoslav,

On Fri, 12 Mar 2010, Radoslav Dorcik wrote:

> At Thu, 11 Mar 2010 08:06:52 +0000,
>
> Hi Ganesh,
>
> Thanks for review comments. I'll try to re-think existing bi-sect
> algorithm. Unforunatelly it will take time :)

I think the algorithm is fine, actually :-) It's just the data structure I 
think is a bit over-complicated.

> Appart the realization of the patch tree, the algorithm defined is
> based on lazy binary tree. Each node represents state within history
> of repository. The state here is the "list of applied patches".
>
> Than there is traversing action which moves to given state and execute
> test. The outcome of the test defines the next move within binary
> tree:
> 1. If the test == OK    than apply patches (move towards head)
> 2. If the test == ERROR than unpull patches (move towards first patch ever)
>
> Nothing new here, but what is interesting:
> 1. The state is temporary repository on file system with some set
> of patches applied. Here is unpure nature hidden.
> 2. Move operation may be either applying or unpulling the patches.
> 3. Node within tree have information about the move (list of patches),
>   not about the state on filesystem.
>
> Do you like above approach in general or there is new clever idea ?

I think that's fine.

> See my (probably stupid :)) questions inline related to your comments:
>
> Ganesh Sittampalam wrote:
>> Ganesh Sittampalam <ganesh@earth.li> added the comment:
>>
>> I'm still not very happy with the PatchTree type. Why does it actually
>> need to have both FL and RL pieces?
>
> I would say that the type of the patch lists defines what to do with
> them - if they are for moving forward within history (apply) or back
> to big bang (unpull them). This type we needed because the moving
> operation is done within child of the parent. If we do the
> apply/unpull on the parent, we can use single type (eg. FL). I'll
> check it.

I'm not quite sure I follow what you mean here, but my argument is that 
you should be able to tell what to do just by which way you move in the 
tree. Also, adding witnesses should help here as it should be impossible 
to apply when you should have unapplied or vice versa.

>> Also there's an invariant on the
>> representation which could be expressed in the constructor - either the
>> list of patches is of length 1 and the list of child trees is of length
>> 0, or the list is of length >1 and the list of child trees is of length 2.
>>
>> Also, why store a copy of the list of patches as well as the tree? You
>> can traverse either in the same amount of time, modulo a small and
>> almost certainly irrelevant constant factor.
>>
>> Why not something like
>>
>> data PatchTree p = Leaf p | Fork (PatchTree p) (PatchTree p)
>
> Do you mean here with the "p" the "patch" or the "FL/RL" ?

p is the patch type.

> If the "Fork" is the place where the decision need to be done, question
> here is what is the "move" operation afer the test upon current
> "state" ? In original implementation the "move" is defined by the list
> (RL or LF) of the patches within the node of the child.

Here, the move would be defined by traversing the entirety of 
either the left branch or the right branch in the right order, and 
applying or unapplying the patches as appropriate.

> Whan is than meaning of the "Leaf p" ?
> Is it "first patch which breaks the test" ?

Leaf p replaces FLNode (p :>: NilFL) [] and RLNode (p :<: NilFL) [] in 
your code. So yes, if you reach it during the search, it is the patch that 
is found to break the test.

Hope this helps. Will you be at the hackathon? If so perhaps we should 
discuss further then if necessary, and I can also try to explain witnesses 
then.

Cheers,

Ganesh

Hi,

I hope that this new PatchTree data structure matches the expectations.
I welcome all review comments. Please take a look on the code (it is
smaller).

Attached patch obsoletes all previous patches. The GADTs are not
included yet. 

Thanks,
Rado

Attachments

• resolve-issue1208_-trackdown-__bisect-_patchtree__.dpatch

That's a lot clearer, thanks!

There's a spurious whitespace hunk in line 20 which it would be better 
to leave out (they're ugly and can contribute to unnecessary conflicts 
later).

The patch count display (2^dnow/2^dtotal) looks a bit dubious to me. 
Won't it always display a power of two, which generally won't correspond 
to the actual number of patches? I'd be inclined to just leave it out as 
the dnow/dtotal indicator is fine.

It also looks like it'll fail with an internal error if given zero 
patches to test, which doesn't happen with linear trackdown. I think it 
should make sure that there really is a failure at one end and a pass at 
the other end of the patch series, and complain if not. Zero patches to 
test is then just a degenerate case of that.

I'm actually a bit confused about whether linear trackdown really tests 
the last patch, so perhaps there's scope to clean that up at the same 
time.

I'd be happy to do the GADT part of things if you're stuck with that. 
I'm conscious there's still very little documentation of how to work 
with them.

Hi!

here is update of the patch (unrecord/record) with:
- remove whitespace
- simplify progress message
- in the case of empty patch list verify the test and
  write error/success according the result of the test.
- above test execution for empty patchlist included in linear trackdown

It would be great if you can put the GADTs into PatchTree. I already
read some articles. But I want focus now on using darcs and learning its
workflow. 

Thanks,
Rado

Attachments

• resolve_issue1208_-trackdown-__bisect-_patchtree__.dpatch

OK, this looks good. Thanks!

I'm not sure if this feature technically ought to have "grumpy old 
man" review, but it's been visible (and an open bug request) for a 
while, and in my humble opinion would easily pass the review anyway 
because it's a simple and obvious enhancement to an existing 
command that fits in with it nicely.

I've added type witnesses, and a few extra fixups (below). I think 
these all come under the trivial category.

One thing to note is that even after the patch below to speed 
things up, the addition of Haskell utility code to the test harness 
adds about 10% to a typical 'cabal test' run (on my machine, 26 
extra seconds on a 4 minute run). I think this is just about ok and 
wouldn't want to discourage people from using Haskell :-) Also, if 
more such utility code gets added, we could probably merge it all 
into a single helper program and amortise the compilation 
overheads.

I'll hold off actually pushing for a couple of days just in case 
anyone would like to object to any of the above.

5 patches for repository http://darcs.net:

Mon Mar 29 23:10:33 BST 2010  dixiecko@gmail.com
  * resolve-issue1208: trackdown --bisect (PatchTree).

Tue Mar 30 06:54:12 BST 2010  Ganesh Sittampalam <ganesh@earth.li>
  * fix warning

Tue Mar 30 06:54:45 BST 2010  Ganesh Sittampalam <ganesh@earth.li>
  * add type witnesses to trackdown --bisect

Tue Mar 30 07:03:35 BST 2010  Ganesh Sittampalam <ganesh@earth.li>
  * speed up test by compiling helper once

Tue Mar 30 07:06:45 BST 2010  Ganesh Sittampalam <ganesh@earth.li>
  * drop unnecessary GHC extensions from test helper

Attachments

• resolve_issue1208_-trackdown-__bisect-_patchtree__.dpatch
• unnamed

On Tue, Mar 30, 2010 at 21:07:07 +0000, Ganesh Sittampalam wrote:
> I'm not sure if this feature technically ought to have "grumpy old 
> man" review, but it's been visible (and an open bug request) for a 
> while, and in my humble opinion would easily pass the review anyway 
> because it's a simple and obvious enhancement to an existing 
> command that fits in with it nicely.

Let's go!  http://wiki.darcs.net/Ideas

WARNING: I haven't been following the review well enough to know if I
understand what bisect does exactly, in UI terms.  So I'm guessing below
that it behaves like darcs trackdown would only faster.

1. What problem does the proposed feature solve?

   EYK: Efficiently identifying a set of patches in the repository which
   cause a test to pass (or was it fail?).  We currently have plain old
   darcs trackdown, but it only works one patch a time, which makes it
   rather painful.  Trackdown --bisect would presumably be a lot faster.

2. What are the user stories?

   EYK: A typical scenario may be that a user submits a bug report for
   frobnicator which *appears* to be a regression, but where?  Somebody
   in the frobnicator team could write a formal test case for this bug
   and run darcs trackdown --bisect "./run-test-case
   frimp-switching-xy".

   In doing so, they would find out that the latest version of the
   repository in which the frimp-switching-xy test case passes
   contains the patches up to 2010-03-11 "Tweak identation in woffle
   module".  Therefore, the next patch up, "Refactor frimp processing"
   is the culprit.

3. Does this change any pre-existing workflows? Does this introduce any
   incompatibilities?

   EYK: My current best guess is that it works exactly as darcs
   trackdown would without any switches.  Is that correct?


4. How do we preserve the conceptual integrity of Darcs? Is the UI for
   this feature really Darcs-ish?

   EYK: This switch does not require you to learn any new concepts; it's
   just a variant of trackdown as far as I can tell.

   On the other hand, one thing I would be worried about is the little
   edge details like what exactly trackdown --bisect tells you.  Is it
   the same exact thing as trackdown [the longest sequence of passing
   patches in the order of your repository? next after the sequence being
   the bad guy].  Should it be?

   Also, could we even take a step further and pro-actively enhance the
   user interface by renaming darcs trackdown to darcs test.  The idea
   then is that darcs test by itself just runs the test, and
   darcs test --trackdown and darcs test --bisect do trackdown-ish tasks?

5. What are the possible unintended interactions with other pre-existing
   features?

   EYK: Like Darcs trackdown, this assumes a patch ordering (which goes
   a little bit against the grain of Darcs), but this is not a new
   problem and it seems hard to avoid anyway (consider darcs changes -v)

6. What are the alternative approaches to solving the same problem? Why
   do we prefer this one?

   EYK: We could farm this out to third party tools, eg. using the Darcs
   library.  I suppose we prefer doing this within Darcs because it's
   something that users would run frequently enough.  Also, we already
   have a testing command anyway, so it would seem silly not to pass up
   the opportunity to make it more powerful.

7.  Who are the stakeholders? Who is going to benefit/be affected by
    this feature: end-users, repo farms like patch-tag, darcs
    developers?

    I think this is specific to stakeholders.

Phew, I hope I got this right.  This is something we'll learn to do
right over the long term, I hope.

Eric

PS. For other Grumpy Old Men out there, I think it's important that we

(i) Treat these questions as a guide to ensure that we are being
    sufficiently attentive about conceptual integrity (and not
    as a formality or a bureaucratic burden)

(ii) Avoid mindless conservatism.  The point is to make sure that
     Darcs UI is great (partly because being the easiest DVCS to
     use is one of the precious/unique aspects of Darcs).  While we want
     to avoid flip-flopping, it may sometimes be necessary to introduce
     change to have a more stable and coherent UI in the long term.

-- 
Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow>
PGP Key ID: 08AC04F9

On Wed, Mar 31, 2010 at 10:34:59 +0100, Eric Kow wrote:
> 7.  Who are the stakeholders? Who is going to benefit/be affected by
>     this feature: end-users, repo farms like patch-tag, darcs
>     developers?
> 
>     I think this is specific to stakeholders.

I meant "this is specific to end-users" (but maybe fancy hosting
services could hook this into something like buildbot)

Heh, and after all this talk about being attentive...

-- 
Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow>
PGP Key ID: 08AC04F9

Eric Kow wrote:
> 1. What problem does the proposed feature solve?
> 
>    EYK: Efficiently identifying a set of patches in the repository which
>    cause a test to pass (or was it fail?).  We currently have plain old
>    darcs trackdown, but it only works one patch a time, which makes it
>    rather painful.  Trackdown --bisect would presumably be a lot faster.
[snip]
>    Also, could we even take a step further and pro-actively enhance the
>    user interface by renaming darcs trackdown to darcs test.  The idea
>    then is that darcs test by itself just runs the test, and
>    darcs test --trackdown and darcs test --bisect do trackdown-ish tasks?

The obvious question here, particularly in the pro-active case: if 
--bisect is preferable in most/all cases (it should be faster in most 
cases, right?), perhaps --bisect should be the default "trackdown" and 
the current one renamed/deprecated?

That is, what are the use cases where one would prefer existing 
trackdown over trackdown --bisect?

--
--Max Battcher--
http://worldmaker.net

On Wed, Mar 31, 2010 at 02:49:30PM -0400, Max Battcher wrote:
> To: Ganesh Sittampalam <bugs@darcs.net>, darcs-users@darcs.net,
> 	dixiecko@gmail.com, ganesh@earth.li,
> 	mf-hcafe-15c311f0c@etc-network.de
> From: Max Battcher <me@worldmaker.net>
> Date: Wed, 31 Mar 2010 14:49:30 -0400
> Subject: Re: [darcs-users] [patch106] resolve issue1208: trackdown --bisect
> 	(complete branch...
> 
> Eric Kow wrote:
>> 1. What problem does the proposed feature solve?
>>
>>    EYK: Efficiently identifying a set of patches in the repository which
>>    cause a test to pass (or was it fail?).  We currently have plain old
>>    darcs trackdown, but it only works one patch a time, which makes it
>>    rather painful.  Trackdown --bisect would presumably be a lot faster.
> [snip]
>>    Also, could we even take a step further and pro-actively enhance the
>>    user interface by renaming darcs trackdown to darcs test.  The idea
>>    then is that darcs test by itself just runs the test, and
>>    darcs test --trackdown and darcs test --bisect do trackdown-ish tasks?
>
> The obvious question here, particularly in the pro-active case: if  
> --bisect is preferable in most/all cases (it should be faster in most  
> cases, right?), perhaps --bisect should be the default "trackdown" and  
> the current one renamed/deprecated?
> 
> That is, what are the use cases where one would prefer existing  
> trackdown over trackdown --bisect?

when i was still up to date what's going on with this patch, it wasn't
possible to restrict the range of patches to search.  this can be a
problem if the test script acts non-continously over the complete
repository (i.e. used to work some time, then not work, then work
again...).  in that case you'd want to either work the patch set
linearly backwards to find the most recent point of change, or
restrict the search space to a fraction of the repository on which the
script acts coninously, or both.

i'm not sure if the current --bisect command allows that?

also the linear search is easier to understand.

thanks rado for not letting this feature die!  (-:


cheers,
matthias

Hello!

On Wed, Mar 31, 2010 at 9:48 PM, <mf-hcafe-15c311f0c@etc-network.de> wrote:

>
> On Wed, Mar 31, 2010 at 02:49:30PM -0400, Max Battcher wrote:> Eric Kow
> wrote:
> >> 1. What problem does the proposed feature solve?
> >>
> > The obvious question here, particularly in the pro-active case: if
> > --bisect is preferable in most/all cases (it should be faster in most
> > cases, right?), perhaps --bisect should be the default "trackdown" and
> > the current one renamed/deprecated?
> >
> > That is, what are the use cases where one would prefer existing
> > trackdown over trackdown --bisect?
>
> when i was still up to date what's going on with this patch, it wasn't
> possible to restrict the range of patches to search.  this can be a
> problem if the test script acts non-continously over the complete
> repository (i.e. used to work some time, then not work, then work
> again...).  in that case you'd want to either work the patch set
> linearly backwards to find the most recent point of change, or
> restrict the search space to a fraction of the repository on which the
> script acts coninously, or both.
>
>
Linear trackdown is nice default because for me it seems that people usually
want to "trackdown latest" working/compiling version of repository.
In the case that condition can fail/success on more than one place the
linear trackdown find the latest such place but bisect may find older one.
Other thing is that bisect needs jump into half of the internal. This "jump"
operation involved apply (or revert) given set of patches. If the test
command itself is fast than this setting state (jump) of temporary repo may
make the --bisect slower than linear trackdown.

Regarding the range of the patches to search or some pattern matching; Do
you mean that it is not possible at all with bisect trackdown ? I'm not
sure, maybe there may be a bisect patch tree which will use "halfs" of given
set of patches according the range/condtion. But that the "jump" (or move)
operation to given state has to apply / revert also patches in between (and
not matched by condition/range). It has than impact on patchtree data
structure again :)


> i'm not sure if the current --bisect command allows that?
> also the linear search is easier to understand.
> thanks rado for not letting this feature die!  (-:
>

I didn't do too much except change of the data structure. The algorithm is
the same as you wrote it, so thanks for that :)
Regarding that tests - that is right, it increases the time of the 'cabal
test'. I'll take a look how to speed up it because it can be annoying.

cheers,
Rado

Attachments

• unnamed

I'm not entirely sure from the discussion whether there are outstanding 
objections to applying this or not. Please shout if there are, otherwise 
it's going in.

No objections from the Grumpy Old Man perspective.  

I had some questions about what bisect really gives you wrt trackdown,
but the online help that Rado/Matthias kindly wrote clarifies that.

Bisect gives you the first patch it finds that fails, "randomly" from
the user perspective; whereas linear trackdown gives you the first patch
working backwards from HEAD.  If your repository is uniformly "fail"
followed by "pass", the two are equivalent.

This patch bundle (with 1 patches) was just applied to the repository http://darcs.net/.
This message was brought to you by DarcsWatch
http://darcswatch.nomeata.de/repo_http:__darcs.net_.html#bundle-355018af3576e961735d62e2dee963560e02c1dc

This patch bundle (with 5 patches) was just applied to the repository http://darcs.net/reviewed.
This message was brought to you by DarcsWatch
http://darcswatch.nomeata.de/repo_http:__darcs.net_reviewed.html#bundle-c87454bf446fba46af646ce4541228750cb6cb35

This patch bundle (with 1 patches) was just applied to the repository http://darcs.net/reviewed.
This message was brought to you by DarcsWatch
http://darcswatch.nomeata.de/repo_http:__darcs.net_reviewed.html#bundle-355018af3576e961735d62e2dee963560e02c1dc