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 <[email protected]> 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 _______________________________________________ darcs-users mailing list [email protected] http://lists.osuosl.org/mailman/listinfo/darcs-users
