On Sat, Feb 14, 2009 at 3:38 PM, Eric Kow <ko...@darcs.net> wrote: > (I'm removing the camp list from my CC list because of errors) > > On Mon, Feb 02, 2009 at 19:47:22 +0100, Jean-Philippe Bernardy wrote: >> Let's take a simple example. Imagine we index lines by rationals for >> the moment. The indices are picked randomly by the system as long as >> they preserve the order of the user file. The fact that they are >> rationals ensure that one can always insert something between two >> other things. We'll see how we can refine this later. > > Thanks for your example. > > Now I understand that > (a) the weights (Int) are used to detect conflicts > (b) rationals as line indices are used to allow different patches to the > same place to be applied concurrently (e.g. 2.1 and 2.2 are > modifications to line 2 made in two different repositories) > (c) a tree-structured file allows for blocks to be inserted between > lines (and not just lines). > Is that right?
Yes. > In this particular example, a negative weight tells us we are removing > the same line twice (or N times), which can be marked up as a conflict. > Are there other ways that the weights are used? > >> Initial state, each line is a triple (weight, index, contents) >> >> 1 1 a >> 1 2 b >> 1 3 c > > I'm just going put these side by side for the interested > (sorry, fixed-width fonts, only) > >> User A changes to: | User B changes the initial state in his own repo to >> | >> 1 1 a | 1 1 a >> 1 2.1 x | 1 2.2 y >> 1 3 b | 1 3 c >> | >> The patch is | The patch is >> | >> -1 2 b | -1 2 b >> 1 2.1 x | 1 2.2 y > >> Composing the initial state with both patches yields: >> >> 1 1 a >> -1 2 b >> 1 2.1 x >> 1 2.2 y >> 1 3 c >> >> The external representation for this merge can be: >> >> a >> <<< >> b >> >>> >> x >> y >> c > > (Just checking: did you mean to include some kind of marker between y > and c?) No. This is mainly what I mean by "non standard marking of conflicts" >> Here the "conflict" can be detected because a line has a negative weight. >> >> There are a few catches with proceeding as such. >> >> 1. Line indices may clash > > By this you mean that the indices (say 2.1 vs 2.2) are handed out > randomly, but it may so happen anyway that the two users get the same > index? If so, is your solution just to reduce the probability of a > clash to something really small? Yes and yes. In fact in my latest version I do a hashing instead of random picking. > I wonder if it would be useful to > have some scheme where one does not rely on randomly assigned indices, > but some kind of automatic index renaming instead. Yes, I believe there is lots of room for improving the internal representation. >> 2. The notation for representing conflicts is non-standard > > I'm not sure I understand what you mean exactly See above. >> 3. Merging concurrent insertions at the same point may yield >> arbitrary interleavings. > > And from your explanation below, this is why files are represented as > trees? Yep. > Just to make sure I have the 'shape' of the idea right, this > means that files will only be as wide as their initial version > (everything else is an insertion)? Right; unless you insert at the end or beginning. Cheers, JP. _______________________________________________ darcs-users mailing list darcs-users@darcs.net http://lists.osuosl.org/mailman/listinfo/darcs-users
