[darcs-users] [patch106] resolve issue1208: trackdown --bisect (complete branch...

[Ganesh Sittampalam]

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 at 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