Hi Ian, I have a potentially silly question: is it fair to characterise darcs-style merging in the absence of conflicts as being O(n * m) time, with n and m being the number of uncommon patches on each side? My informal way of arriving at this characterisation of things is that we can say the cost of commutation is constant (wrt # of patches, provided no conflicts), and that the only work you have to do is to commute each one of m patches past one of the m patches. Is that the correct way of looking at things?
Deep down, this is a marketing question. I want people to have a clearer picture of when the exponential merge problem will and will not strike. And part of this picture is knowing where it is NOT a problem, and what exactly will happen in those cases. To be clear, I do not intend this to be flippant about this and say something like, 'oh, it "only" happens when there are conflicts' as if it was just a corner case. Of course, conflicts are a problem and of course we need to keep working on them, but I just wanted to remove the feeling of uncertainty from darcs by pinning things down a bit better. http://www.ericsink.com/entries/merge_history.html Ideally, we would also have a more precise characterisation of what kinds of conflicts we think darcs-2 handles better than darcs-1, and where things can blow up. Thanks! Eric Background for not-Ian ====================== For the interested darcs merging works like this: you have two repositories that have some patches in common, and some patches that are in one repository and not the other. Repo 1 : c c c c c m1 m2 m3 m4 Repo 2 : c c c c c n1 n2 n3 If repo 2 pulls from repo 1 (i.e. if we have to merge the repositories), we simply have to invertthe patches on one side... Repo 2: c c c c c c n1 n2 n3 n3^ n2^ n1^ Slap on the patches from the other patches (which you can now do because inverting the patches gets you back to zero)... Repo 2: c c c c c c n1 n2 n3 n3^ n2^ n1^ m1 m2 m3 m4 Commute the patches past each other Repo 2: c c c c c c n1 n2 n3 m1' m2' m3' m4' n3^' n2^' n1^' Then remove the commuted inverses Repo 2: c c c c c c n1 n2 n3 m1' m2' m3' m4' -- Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow> PGP Key ID: 08AC04F9
signature.asc
Description: Digital signature
_______________________________________________ darcs-users mailing list [email protected] http://lists.osuosl.org/mailman/listinfo/darcs-users
