Hi, I've had a chance to sit down and read this. Here are some superficial comments, followed by some questions.
I do like the idea of separating an 'internal' representation of state from the 'external' one. It seems like the darcs pristine cache, especially in its hashed form, is an approximation of the internal state. For what it's worth, I also get the impression also that this distinction is something that the darcs user manual (and the Understanding Darcs wikibook) attempt to make, at least informally. Unless I am mistaken, the unrecord command in the appear appears to be akin to the darcs obliterate/unpull command than to darcs unrecord. Is that intentional? (Unrecord only changes the internal state, leaving the external state untouched; see also revert which does the opposite). I'm afraid I didn't understand the idea of "weights", nor did I fully understand the use of a tree structure to represent the lines in a file. I am dimly aware that representing the file as a list of lines will not suffice if we want to have an internal representation that allows us to simultaneously represent conflicting states. But in what is the representation tree shaped? For example, are conflicting modifications to a line just different sublines? Perhaps an example? On Wed, Jan 07, 2009 at 15:17:06 +0100, Jean-Philippe Bernardy wrote: > > First (of two) questions: what, in a nutshell, does it mean not to have any > > conflicts? Clearly, there can be conflicting situations (i.e. two people > > edit > > different parts of a file). How roughly does your idea cope with them? As > > you > > can see, I haven't yet had the chance to read the paper, but was hoping for > > a > > little bit more of a taster (now that I've had the teaser) > In our representation of files, each line is given a unique identity. > Let's imagine for a moment that two people replace the same part of a > file with another. It means that some portion of the file was removed > twice. Therefore, there will be a "minus one" zone in that portion of > the file that indicate the problem. (This is very similar to two > people withdrawing the same money concurrently on the bank account.) How would a user perceive this? > > Second question. The paper says: > > | Darcs will flag this scenario as a conflict, i.e. it cannot represent > > such a > > | merge. The result of a merge in Darcs is dependent on the order that the > > | changes are applied, Darcs will try all possible "non conflicting" > > permutations > > | of the changes which will result, in the worst case, in exponential > > complexity. > > > > What does this mean, please? I thought the whole point of the darcs > > approach > > to conflicts is that it be completely independent of order (i.e. we cancel > > out > > both patches). > Surely you know more about darcs than us, so we can clear it up > together. Note that we refer to darcs 1.0. Isn't it true that the > patch representation (potentially) changes after a reordering? Well, I must warn you that I'm really a patch theory novice and very easily in over my head. I had the understanding that the exponential nature of darcs 1.0 was due to a use of nested structures. That is, if there is a conflict, the representation of one of the combatants must be modified to include a copy of the patch it is conflicting with. That means that each conflict doubles the size of a patch. If there are conflicts of conflicts, we get yet more doubling and the rest is history. Darcs 2, if I understand correctly, still uses some amount of nesting, but it helps by including enough information to avoid the nesting in the most common cases, i.e. with spurious conflicts of conflicts (I don't have a precise definition of this, but rather a vague understanding that a lot of things that darcs 1.0 would consider a nested conflict are actually just by-products of its conflicts resolution, and can be avoided). As a result, the conflict explosion is avoided, except in cases of conflict fights, where we have case of a genuinely nested conflict. This is all very vague because my understanding is very limited. Perhaps others can step in to clarify. The point is that I remain a bit suspicious of this particular version of the story from the paper: | Darcs will try all possible "non conflicting" permutations of the | changes which will result, in the worst case, in exponential | complexity. Is that right? What does it mean? Thanks very much! (Now, I hope to have a chance to sit down and play with focal a bit) -- Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow> PGP Key ID: 08AC04F9
pgppk5WtpoqGw.pgp
Description: PGP signature
_______________________________________________ darcs-users mailing list darcs-users@darcs.net http://lists.osuosl.org/mailman/listinfo/darcs-users
