Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?
Am 29.06.20 um 19:12 schrieb James Cook: >> Another problem is that even supposing commutation does not change prim >> patches, in darcs you still have conflictors. And conflictors >> /definitely/ have to change representation when we commute them: the >> merge-commute law obviously requires that. > > Could the conflictors be re-computed? Yes, of course. This is the beauty of patch commutation. > In more detail: Suppose we've managed to make it so primitive patches > never change representation. I tell you I built my repo by pulling the > primitive patches A, B and C in some arbitrary order, changing them > into conflictors when necessary. (I might also have done some other > operations, like adding and later obliterating patches, or commuting > things.) I also tell you that the final order of patches in my repo is > AB'C', where B' is either B itself or a conflictor keeping B's > identity (and same for C'). Could there ever be more than one possible > answer for what B' and C' end up being? Not if the system maintains all global invariants. Any two sequences of patches which contain the (nominally) same patches must be representationally equal after commuting them to the same order. > If not, doesn't that mean that > the identities of A, B and C are enough to verify we've got the same > repo? Yes, but how does that help us to avoid changing the representation of conflictors? If you have conflicting patches A and B then the only way to apply them in you local repo is by choosing an order, say first A then B. Then B is conflicted and it necessarily behaves differently compared to a situation where you do not have A in the context. >>> In theory, you could >>> even allow plugins that implement new patch types, with the basic >>> principle that patches communicate with each other through >>> modifications to the repo metadata. >> >> That may be possible, especially for a completely new project that is >> designed around these notions from the start. > > Sorry to extend this tangent even further (if you keep responding to > my emails, I'll likely keep sending them :-P), That's okay. I find the discussion interesting. > but I had another > thought: you don't actually need to store the metadata with the repo > state. You could instead put some metadata into the patches, and allow > patches to modify each others' metadata when they try to commute. > Well, at least I think it would work... let me know if you want > details. I fail to see the essential difference to what Darcs does now. You just shift information from the actual patch content to what you (vaguely) call "meta-data". Then you modify that "meta-data" during commute, instead of directly modifying the patch content. Can't you make it a bit more concrete? Use a simple example of two conflicting (primitive) patches and explain what the meta data looks like and how the mechanics of commute and merge are supposed to work in that example and how these patches are applied in sequence. Cheers Ben ___ darcs-users mailing list darcs-users@osuosl.org https://lists.osuosl.org/mailman/listinfo/darcs-users
Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?
> It had never occurred to me to think of that as a possible solution. > Sometimes it helps to get input from someone who is not as deeply > involved and who can come up with fresh ideas. Many thanks for sharing them! Glad it turns out to be at least plausible. Thanks for taking the time to respond to all my questions so far. James ___ darcs-users mailing list darcs-users@osuosl.org https://lists.osuosl.org/mailman/listinfo/darcs-users
Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?
> Another problem is that even supposing commutation does not change prim > patches, in darcs you still have conflictors. And conflictors > /definitely/ have to change representation when we commute them: the > merge-commute law obviously requires that. Could the conflictors be re-computed? In more detail: Suppose we've managed to make it so primitive patches never change representation. I tell you I built my repo by pulling the primitive patches A, B and C in some arbitrary order, changing them into conflictors when necessary. (I might also have done some other operations, like adding and later obliterating patches, or commuting things.) I also tell you that the final order of patches in my repo is AB'C', where B' is either B itself or a conflictor keeping B's identity (and same for C'). Could there ever be more than one possible answer for what B' and C' end up being? If not, doesn't that mean that the identities of A, B and C are enough to verify we've got the same repo? I take your point, though, that maintaining metadata in the repository state, as required for all this, would be hard. > > In theory, you could > > even allow plugins that implement new patch types, with the basic > > principle that patches communicate with each other through > > modifications to the repo metadata. > > That may be possible, especially for a completely new project that is > designed around these notions from the start. Sorry to extend this tangent even further (if you keep responding to my emails, I'll likely keep sending them :-P), but I had another thought: you don't actually need to store the metadata with the repo state. You could instead put some metadata into the patches, and allow patches to modify each others' metadata when they try to commute. Well, at least I think it would work... let me know if you want details. This loses global uniqueness (since patch metadata changes when commuting), but might help (a) if you want to allow plugins but don't want to deal with metadata being part of the repo state, or (b) if you're trying to reason about a complicated primitive patch theory and want a way to avoid considering n^2 cases. (Based on your email, it sounds like (b) is not a practical concern, though.) James ___ darcs-users mailing list darcs-users@osuosl.org https://lists.osuosl.org/mailman/listinfo/darcs-users
Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?
Am 29.06.20 um 16:51 schrieb James Cook: >> There is also more than just hunks. What about file renames? A file >> rename commutes with a hunk that changes the file, and in darcs this >> changes the hunk patch to refer to the renamed file. You need to change >> the internal representation to refer to files using UUIDs to get around >> that. And as soon as you do that you get the same problems with global >> uniqueness invariants that you previously had for patches. There is a >> reason why git cannot track file renames: they store just trees and >> identify them by their content hash. This is secure and quite efficient, >> but properly tracking file renames is not possible in such a model. >> AFAIK Pijul suffers from a similar limitation and for the same reason >> i.e. there is no primitive "rename" patch, only file-remove and file-add. > > I think Pijul does handle renames intelligently. (I just tested: > merging a rename "f -> g" with an edit to f results in editing g.) Okay, thanks. I just remembered (vaguely) that at one point they didn't have a move command, the rest was just guessing. > A while ago I poked at Pijul's patch representation and inferred that > it indeed gives each file a unique ID, and that ID is based on the ID > of the patch that created it. I think it does something similar to > assign identities to individual lines in files. I imagine it does the > same thing for directories. Don't quote me on this, though. Hmm. If they base the UUID on the creating patch's ID, then this might be safe, assuming the latter is (based on) a content hash. So I guess I was wrong to claim that you necessarily get the same "global uniqueness" problems as Darcs has. Cheers Ben ___ darcs-users mailing list darcs-users@osuosl.org https://lists.osuosl.org/mailman/listinfo/darcs-users
Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?
> There is also more than just hunks. What about file renames? A file > rename commutes with a hunk that changes the file, and in darcs this > changes the hunk patch to refer to the renamed file. You need to change > the internal representation to refer to files using UUIDs to get around > that. And as soon as you do that you get the same problems with global > uniqueness invariants that you previously had for patches. There is a > reason why git cannot track file renames: they store just trees and > identify them by their content hash. This is secure and quite efficient, > but properly tracking file renames is not possible in such a model. > AFAIK Pijul suffers from a similar limitation and for the same reason > i.e. there is no primitive "rename" patch, only file-remove and file-add. I think Pijul does handle renames intelligently. (I just tested: merging a rename "f -> g" with an edit to f results in editing g.) A while ago I poked at Pijul's patch representation and inferred that it indeed gives each file a unique ID, and that ID is based on the ID of the patch that created it. I think it does something similar to assign identities to individual lines in files. I imagine it does the same thing for directories. Don't quote me on this, though. James ___ darcs-users mailing list darcs-users@osuosl.org https://lists.osuosl.org/mailman/listinfo/darcs-users
Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?
Am 29.06.20 um 13:46 schrieb James Cook: >> This in turn led me to the more general question of how to detect >> inconsistencies when exchanging patches between repos. The problem here >> is that darcs currently relies on global uniqueness properties that are >> quite easy to invalidate (e.g. by manually editing patches, and as >> hinted above also when we independently convert branches of a repo). >> Specifically, we rely on the following global property: if two patches >> have the same name/identity, then (a) they can always be commuted to a >> common context and (b) they are equal (content-wise) after commuting >> them to any such common context. (The context of a patch is defined as >> the set of patches preceding it.) Effectively this property means that >> patches with the same name/identity are really just commuted/merged >> versions of one and the same original patch. >> >> I have an (efficient) algorithm in mind that validates these assumptions >> whenever we exchange patches between repos. Implementing this requires a >> pretty deep refactor though. > > I was wondering if global uniqueness could be solved by borrowing from Pijul. Me too, more than once. But note that none of these considerations are practical for the kind of evolutionary change we are limited to if we want to maintain compatibility with existing repos. This is why I concluded that validation is the only practical solution for Darcs. Instead of ignoring it (as we always did, hoping it never happens), we should fully recognize the fact that different repos with the same patch format may become incompatible. (Though of course we still strive to eliminate any bugs that may cause this to happen accidentally.) > If you include some metadata as part of the repository state (e.g. the > identity of the hunk responsible for every line of every text file) > then I think you could make it so that a primitive patch's > representation doesn't change when it's commuted. I suspect pretty > much any primitive patch theory could be adapted to work this way. > (Note I'm not claiming this will make everything actually commute like > in Pijul.) If you extend the "repository state" with enough extra information, then yes, I think it is possible to do that. Indeed we have a competing prim patch theory that goes about half-way toward that goal. We never came around to integrate that properly with the high-level Repository/UI code. Because much of what goes on in those layers has to do with the repo state (for instance, think of generating difference patches between the working state and the pristine state). So we need an abstraction layer for repo states and finding out what the common API should be here is difficult. Another problem is that even supposing commutation does not change prim patches, in darcs you still have conflictors. And conflictors /definitely/ have to change representation when we commute them: the merge-commute law obviously requires that. So this would mean we end up re-implementing Pijul where conflicts are a property of the repo state, rather than of patches. > Besides giving unique names, another nice thing about this is that you > shouldn't need to implement n^2 different patch commuting functions > for n types of primitive patch. (I don't know if darcs actually needs > to do this; I'm just assuming.) The commutation rules for prim patches are the least complicated part of our core algorithms. The n^2 here is not a problem in practice. What /is/ a problem in practice is that we can never change any of the prim patch commutation rules without introducing a new incompatible patch "format", because these rules, too, must be globally invariant. If we can detect such inconsistencies reliably, we may be a bit more relaxed wrt maintaining the exact commutation behavior. > If you have access to the repo state, > you can tell if two patches commute just by trying to apply them in > the opposite order and seeing if they complain. True, but that is hardly simpler or more efficient than commuting them directly as we do in Darcs. And it means you can no longer handle patches or sequences of patches in isolation. So everything becomes stateful. Besides, determining /whether/ two patches commute could be easily cached at the named patch level, even in darcs as of today. The problem is to decide what the resulting patches look like after we commuted them. If the representation does not change, then this problem of course doesn't exist... > In theory, you could > even allow plugins that implement new patch types, with the basic > principle that patches communicate with each other through > modifications to the repo metadata. That may be possible, especially for a completely new project that is designed around these notions from the start. > A slightly less radical version of this would be to keep the current > primitive patch representation, but use this idea when generating the > patch names. E.g. a hunk's name is a hash involving
Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?
Am 29.06.20 um 12:53 schrieb James Cook: >> Converting existing repos to darcs-3 is unfortunately one of the things >> we havent't done yet. I have implemented a number of conversion schemes >> but they all fail in some situations. There are two hard problems to >> solve here: >> >> (1) What to do about so called "Duplicates" in the darcs-2 format. These >> have no equivalent in the darcs-3 format (in darcs-3 duplicate prim >> patches conflict). >> >> (2) How to ensure separately converted branches of a project remain >> interoperable. The existing 'convert darcs-2' command gives up on this >> and simply assigns new identities for all patches. This means you cän >> convert at most one branch and have to throw away all others. (Or first >> merge them all into a single repo, but that typically hits the dreaded >> eponential behavior in the darcs-1 format, so in practice normally >> doesn't work.) I always found this to be an extremely poor user >> experience! It is one of the reasons many people never converted their >> repos to the darcs-2 format. > > As an attempt to solve problem (2) ignoring problem (1), what would > happen if you used the entire darcs-2 patch theory, including > conflictors, as the primitive patch theory for darcs-3? The idea being > that you avoid creating any new darcs-2 conflictors going forward, but > if you do encounter them, they're just a legacy type of primitive > patch. Or does the existence of darcs-2 style conflictors make the > patch theory unsuitable? That's an interesting idea. Unfortunately yes, the existence of /any/ style of conflictors makes them unsuitable to serve as prim patches. At least not without making some further assumptions. The problem is that primitive patches must be invertible. But conflictors cannot properly be inverted. Darcs used to have inverse conflictors in the code until a while ago, but they were always hazardous (some operations would just call error if they get such a thing as input) and we had to make sure they never ended up being stored on disk. So eventually we removed them from the code base. The reason conflictors cannot be inverted is that they contain "references" to patches coming before them (namely the patches we are in conflict with). If you invert a sequence of patches that contains conflictors, then the inverted conflictors refer to patches coming /after/ them. That in turn invalidates the invariant that it is always safe to drop patches from the end of a sequence of patches. But now that I have written all this, perhaps it would be possible to get by with some sort of purely formal inversion. We already have a wrapper type to allow such formal inversion of patches that are not properly invertible. These patches are either "positive" (just a plain wrapper) or "negative" (formally inverted). They cannot be commuted in general (since we have no way to commute patches with different "polarities"). And in darcs-3 we already distinguish between positive and negative prim patches via their IDs. Perhaps it turns out that we can avoid doing mixed polarity commutation for prims in the darcs-3 implementation. I will investigate if that is the case. If it is, then your idea may be workable. In that case it may even make sense to track polarity in the type system (i.e. via an additional type parameter) to make sure we don't accidentally mix them inappropriately. > As an even more desparate attempt to solve (1), what if you said the > primitive patch theory is a disjoint union of (a) "old-style" darcs-2 > patches and (b) "new-style" darcs-3 primitive patches, and type (a) > and (b) patches never commute? In practice you'd get awful conflicts > if you tried to interleave darcs-2 and darcs-3 work, but in theory > could that conversion be lossless? (Maybe old-style and new-style > patches could sometimes commute. I'm trying to treat them as black > boxes, making no assumptions.) This suffers from the same problem as above (or not, depending on whether we can get by with "formal" inversion). Apart from that, yes, this may be a possible way to solve all the conversion problems with one big stroke. It had never occurred to me to think of that as a possible solution. Sometimes it helps to get input from someone who is not as deeply involved and who can come up with fresh ideas. Many thanks for sharing them! Cheers Ben ___ darcs-users mailing list darcs-users@osuosl.org https://lists.osuosl.org/mailman/listinfo/darcs-users
Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?
> This in turn led me to the more general question of how to detect > inconsistencies when exchanging patches between repos. The problem here > is that darcs currently relies on global uniqueness properties that are > quite easy to invalidate (e.g. by manually editing patches, and as > hinted above also when we independently convert branches of a repo). > Specifically, we rely on the following global property: if two patches > have the same name/identity, then (a) they can always be commuted to a > common context and (b) they are equal (content-wise) after commuting > them to any such common context. (The context of a patch is defined as > the set of patches preceding it.) Effectively this property means that > patches with the same name/identity are really just commuted/merged > versions of one and the same original patch. > > I have an (efficient) algorithm in mind that validates these assumptions > whenever we exchange patches between repos. Implementing this requires a > pretty deep refactor though. I was wondering if global uniqueness could be solved by borrowing from Pijul. If you include some metadata as part of the repository state (e.g. the identity of the hunk responsible for every line of every text file) then I think you could make it so that a primitive patch's representation doesn't change when it's commuted. I suspect pretty much any primitive patch theory could be adapted to work this way. (Note I'm not claiming this will make everything actually commute like in Pijul.) Besides giving unique names, another nice thing about this is that you shouldn't need to implement n^2 different patch commuting functions for n types of primitive patch. (I don't know if darcs actually needs to do this; I'm just assuming.) If you have access to the repo state, you can tell if two patches commute just by trying to apply them in the opposite order and seeing if they complain. In theory, you could even allow plugins that implement new patch types, with the basic principle that patches communicate with each other through modifications to the repo metadata. A slightly less radical version of this would be to keep the current primitive patch representation, but use this idea when generating the patch names. E.g. a hunk's name is a hash involving the identities of the hunks responsible for the lines it deletes. You'd still need to keep some metadata around to be able to do that, though. James ___ darcs-users mailing list darcs-users@osuosl.org https://lists.osuosl.org/mailman/listinfo/darcs-users
Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?
> Converting existing repos to darcs-3 is unfortunately one of the things > we havent't done yet. I have implemented a number of conversion schemes > but they all fail in some situations. There are two hard problems to > solve here: > > (1) What to do about so called "Duplicates" in the darcs-2 format. These > have no equivalent in the darcs-3 format (in darcs-3 duplicate prim > patches conflict). > > (2) How to ensure separately converted branches of a project remain > interoperable. The existing 'convert darcs-2' command gives up on this > and simply assigns new identities for all patches. This means you cän > convert at most one branch and have to throw away all others. (Or first > merge them all into a single repo, but that typically hits the dreaded > eponential behavior in the darcs-1 format, so in practice normally > doesn't work.) I always found this to be an extremely poor user > experience! It is one of the reasons many people never converted their > repos to the darcs-2 format. As an attempt to solve problem (2) ignoring problem (1), what would happen if you used the entire darcs-2 patch theory, including conflictors, as the primitive patch theory for darcs-3? The idea being that you avoid creating any new darcs-2 conflictors going forward, but if you do encounter them, they're just a legacy type of primitive patch. Or does the existence of darcs-2 style conflictors make the patch theory unsuitable? As an even more desparate attempt to solve (1), what if you said the primitive patch theory is a disjoint union of (a) "old-style" darcs-2 patches and (b) "new-style" darcs-3 primitive patches, and type (a) and (b) patches never commute? In practice you'd get awful conflicts if you tried to interleave darcs-2 and darcs-3 work, but in theory could that conversion be lossless? (Maybe old-style and new-style patches could sometimes commute. I'm trying to treat them as black boxes, making no assumptions.) James ___ darcs-users mailing list darcs-users@osuosl.org https://lists.osuosl.org/mailman/listinfo/darcs-users
Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?
Am 29.06.20 um 03:54 schrieb James Cook: > I'm glad to hear about darcs-3. I was worried work on implementing > Camp had stopped completely. Yes, I am quite happy about that, too. It means we finally have an implementation of a patch theory that satisfies all required patch laws. We have upgraded our QuickCheck test case generator so it now generates all possible sorts of repositories and we have verified that the darcs-3 format indeed upholds all properties, even if we seriously crank up the number of generated tests. > Is testing helpful at this point? Testing always helps. If you have a machine with lots of cores and memory, try running the test suite with "-t RepoPatchV3 -q 10 -j ". This can take a lot of time to complete, depending on the arguemnt for the -q option. > I could try cloning and converting my repos to darcs-3. Converting existing repos to darcs-3 is unfortunately one of the things we havent't done yet. I have implemented a number of conversion schemes but they all fail in some situations. There are two hard problems to solve here: (1) What to do about so called "Duplicates" in the darcs-2 format. These have no equivalent in the darcs-3 format (in darcs-3 duplicate prim patches conflict). (2) How to ensure separately converted branches of a project remain interoperable. The existing 'convert darcs-2' command gives up on this and simply assigns new identities for all patches. This means you cän convert at most one branch and have to throw away all others. (Or first merge them all into a single repo, but that typically hits the dreaded eponential behavior in the darcs-1 format, so in practice normally doesn't work.) I always found this to be an extremely poor user experience! It is one of the reasons many people never converted their repos to the darcs-2 format. My failed attempts to come up with a complete solution for both (1) and (2) convinced me that we will have to find some sort of compromise here. In particular, I think we won't be able to uphold (2) under all circumstances. This led me to investigate how we could at least make sure that we can /detect/ when separately converted repos are incompatible. The error message should be good enough that users can make an informed choice about how to work around the problem: either discard one of the branches, or discard (i.e. obliterate) only some patches, or else try to re-record/amend them (which gives them new identities). This in turn led me to the more general question of how to detect inconsistencies when exchanging patches between repos. The problem here is that darcs currently relies on global uniqueness properties that are quite easy to invalidate (e.g. by manually editing patches, and as hinted above also when we independently convert branches of a repo). Specifically, we rely on the following global property: if two patches have the same name/identity, then (a) they can always be commuted to a common context and (b) they are equal (content-wise) after commuting them to any such common context. (The context of a patch is defined as the set of patches preceding it.) Effectively this property means that patches with the same name/identity are really just commuted/merged versions of one and the same original patch. I have an (efficient) algorithm in mind that validates these assumptions whenever we exchange patches between repos. Implementing this requires a pretty deep refactor though. The upshot is that we won't get conversion to darcs-3 until we can reliably detect inconsistencies between repos. And before I can come around to fully concentrate on implementing that, we have to get out release 2.16 because our head is now many hundreds of patches beyond the last release (2.14.4) and there have been lots of bug fixes and other improvements. Cheers Ben ___ darcs-users mailing list darcs-users@osuosl.org https://lists.osuosl.org/mailman/listinfo/darcs-users
Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?
> That said, you should be advised that both patch theory implementations
> ("formats") currently in use, namely darcs-1 and darcs-2, have bugs. In
> practice that means you may not be able to do such a separation for
> complicated conflict scenarios, though I think if it succeeds then the
> resulting repos should be equivalent. We have implemented a new one,
> darcs-3, which closely follows the camp paper and does not have any of
> these bugs. But that is not yet released. You can play with it using our
> development version at http://darcs.net/screened, but please don't use
> it for serious work, because the on-disk format may still change.
I'm glad to hear about darcs-3. I was worried work on implementing
Camp had stopped completely.
Is testing helpful at this point? I could try cloning and converting
my repos to darcs-3.
> I'd be interested to hear more about your patch theory.
Unsurprisingly, I'm learning about all sorts of interesting pitfalls
while trying to make it concrete.
I still might manage to make something worth sharing, though.
James
___
darcs-users mailing list
darcs-users@osuosl.org
https://lists.osuosl.org/mailman/listinfo/darcs-users
Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?
Am 26.06.20 um 20:55 schrieb James Cook:
>>> I've been reading about patch theory [0]. I *thought* what's supposed
>>> to happen is this:
>>>
>>> * The effect of B' is the same as the effect of A. (i.e. create the file)
>>> * The effect of A' is the same as the effect of B. (i.e. add "some text")
>>> * Therefore, B'A' does the same thing as AB.
>>> * B' and A' include some information about the conflict, in addition
>>> to their effects described above. (They are "conflictor" patches.)
>>> * If I commute B' and A' again, I get back AB, since <-> is a
>>> symmetric relation.
>>
>> I understand. However, there is no patch theory I am aware of that is
>> able to make this work, except those where *any* two patches commute, so
>> there are no dependencies and patches never conflict.
>
> Thank you. I've learned a lot from your reply.
You are welcome.
> I have an idea for a patch theory that would satisfy these properties,
> and may have other advantages and might even be backward-compatible with
> darcs. I am not confident that it works, but I would love to have some
> feedback, if someone finds the time to read it. Is this list a good
> place to post something like that?
Sure, I wouldn't know of any better one.
>> As I said in the beginning, there is no force-commute command in darcs
>> because that would be unsound. By definition, if B depends on A this
>> means A;B does /not/ commute. In the theory, one starts with primitive
>> patches for which there is no total merge operation, only a partial
>> clean-merge that may fail. If you have two independently recorded
>> patches A and B in the same context (we write this as A\/B), then
>> clean-merge succeeds iff A^;B commutes (where ^ means inversion). If
>> clean-merge(A\/B) does not succeed, then A\/B are said to be in conflict.
>
> Does darcs satisfy the property that if I merge two arbitrary
> repositories R and S to produce a new repository M, then separate out
> the patches again (i.e. pull just R's patches or just S's patches from
> M to a fresh repo) then I get back R and S?
Definitely.
That said, you should be advised that both patch theory implementations
("formats") currently in use, namely darcs-1 and darcs-2, have bugs. In
practice that means you may not be able to do such a separation for
complicated conflict scenarios, though I think if it succeeds then the
resulting repos should be equivalent. We have implemented a new one,
darcs-3, which closely follows the camp paper and does not have any of
these bugs. But that is not yet released. You can play with it using our
development version at http://darcs.net/screened, but please don't use
it for serious work, because the on-disk format may still change.
> I hope the question makes sense. I can write a concrete sequence of
> commands if it doesn't.
It makes perfectly good sense.
> I had assumed this property was true because I thought force-commuting
> satisfied the magical properties in my previous email. I hope it is
> still true despite me being wrong about force-commuting.
Yes.
>> When we add conflictors, we extend the set/type of primitive patches to
>> a larger set, such that now any two patches can be merged. However, we
>> must require that this extension preserves commutation behavior. In
>> particular, if A;B does not commute, then their embeddings in the larger
>> set of patches must commute neither.
>
> Ah, I had a different picture in mind. I thought that after adding in
> conflictors, then technically you end up with a universe of patches
> where everything commutes, but the patches end up looking ugly and
> unintuitive if you commute things that aren't "supposed" to. I thought a
> "force-commute" was simply a commute that wouldn't have been possible
> before adding conflictors to your universe of patches. This is what I
> hope my patch theory accomplishes.
I'd be interested to hear more about your patch theory.
BTW, the property you asked about above is a consequence of the so
called merge-commute law. If you have a forking pair A\/B and merge it,
you end up with
o
/ \
B' A'
/ \
o o
\ /
A B
\ /
o
where by convention patches are applied bottom to top i.e. you should
imagine the patches as arrows pointing upward; arrow heads are hard to
paint in ascii ;-).
The merge-commute law says that the two "branches" of this merge, i.e.
A;B' and B;A' commute to each other. This ensures that it does not
matter whether you pull from R into S or vice versa. It also implies
that you can get back to the original state A\/B by commuting either A
or B to the end and then obliterating it.
This must remain true if the merge is conflicted and then it implies
that any individual conflicted patch (here: A' or B') can be made
unconflicted by commuting with those it conflicts with.
Cheers
Ben
___
darcs-users mailing list
darcs-users@osuosl.org
https://lists.osuosl.org/mailman/listinfo/d
Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?
> > I've been reading about patch theory [0]. I *thought* what's supposed > > to happen is this: > > > > * The effect of B' is the same as the effect of A. (i.e. create the file) > > * The effect of A' is the same as the effect of B. (i.e. add "some text") > > * Therefore, B'A' does the same thing as AB. > > * B' and A' include some information about the conflict, in addition > > to their effects described above. (They are "conflictor" patches.) > > * If I commute B' and A' again, I get back AB, since <-> is a > > symmetric relation. > > I understand. However, there is no patch theory I am aware of that is > able to make this work, except those where *any* two patches commute, so > there are no dependencies and patches never conflict. Thank you. I've learned a lot from your reply. I have an idea for a patch theory that would satisfy these properties, and may have other advantages and might even be backward-compatible with darcs. I am not confident that it works, but I would love to have some feedback, if someone finds the time to read it. Is this list a good place to post something like that? > As I said in the beginning, there is no force-commute command in darcs > because that would be unsound. By definition, if B depends on A this > means A;B does /not/ commute. In the theory, one starts with primitive > patches for which there is no total merge operation, only a partial > clean-merge that may fail. If you have two independently recorded > patches A and B in the same context (we write this as A\/B), then > clean-merge succeeds iff A^;B commutes (where ^ means inversion). If > clean-merge(A\/B) does not succeed, then A\/B are said to be in conflict. Does darcs satisfy the property that if I merge two arbitrary repositories R and S to produce a new repository M, then separate out the patches again (i.e. pull just R's patches or just S's patches from M to a fresh repo) then I get back R and S? I hope the question makes sense. I can write a concrete sequence of commands if it doesn't. I had assumed this property was true because I thought force-commuting satisfied the magical properties in my previous email. I hope it is still true despite me being wrong about force-commuting. > When we add conflictors, we extend the set/type of primitive patches to > a larger set, such that now any two patches can be merged. However, we > must require that this extension preserves commutation behavior. In > particular, if A;B does not commute, then their embeddings in the larger > set of patches must commute neither. Ah, I had a different picture in mind. I thought that after adding in conflictors, then technically you end up with a universe of patches where everything commutes, but the patches end up looking ugly and unintuitive if you commute things that aren't "supposed" to. I thought a "force-commute" was simply a commute that wouldn't have been possible before adding conflictors to your universe of patches. This is what I hope my patch theory accomplishes. James ___ darcs-users mailing list darcs-users@osuosl.org https://lists.osuosl.org/mailman/listinfo/darcs-users
Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?
Am 26.06.20 um 05:03 schrieb James Cook: >>> What I'd like to do is create a repository R1 with patches A and B, >>> and then look at the patches that result if A and B get >>> force-commuted. >>> >>> E.g. if I could pull just patch B and not A to a new repository, I >>> think that would do the trick, but of course darcs pull won't let me >>> do that because B depends on A. >> >> The main question here is: What do you expect the result of such a >> force-commute would be? > > I've been reading about patch theory [0]. I *thought* what's supposed > to happen is this: > > * The effect of B' is the same as the effect of A. (i.e. create the file) > * The effect of A' is the same as the effect of B. (i.e. add "some text") > * Therefore, B'A' does the same thing as AB. > * B' and A' include some information about the conflict, in addition > to their effects described above. (They are "conflictor" patches.) > * If I commute B' and A' again, I get back AB, since <-> is a > symmetric relation. I understand. However, there is no patch theory I am aware of that is able to make this work, except those where *any* two patches commute, so there are no dependencies and patches never conflict. > However, that doesn't seem to be what happened (see below). No, indeed. The procedure I described /edits/ the patch history, assigning new identities to both patches. > Even if that were correct, it still doesn't leave me with a complete > picture of what darcs actually does, so I wanted to experiment. > > >>> Question 1: Is there a simple way to make darcs do this? >> >> Not exactly simple, but it is possible: >> >> darcs clone . ../saved >> darcs rebase suspend # select B and A >> darcs rebase obliterate # select A >> darcs rebase unsuspend # select B >> darcs pull ../saved # select A >> >> You should expect to get conflicts first when you unsuspend B (after >> obliterating A) and then also when you re-pull A from the clone. You >> will probably want to amend the conflict resolution into the conflicted >> patch. > > Thanks, that seems to have worked. (I only got the first conflict, not > the second.) But now I'm confused. > > Based on, for example, the "Forced commutation" section of > https://en.wikibooks.org/wiki/Understanding_Darcs/Patch_theory_and_conflicts > , I expected B' to add the file "foo", and A' to add "some text" (so, > B' has the effect of A and A' has the effect of B). > > Instead of that, I get this: > > (a) If I follow your advice and amend the conflict resolution into B' > before pulling, then (the amended) B' has the effect of AB, and A' has > no effect. > > (b) If I run "darcs revert" instead of amending the conflict > resolution into B', then B' has the effect of A and A' still has no > effect. > > Confusingly, darcs offers to pull B from ../saved --- I thought darcs > should consider it to already be present (as B'). > > I also noticed that if I run the swap a second time, I don't exactly > get A and B back. (In the (a) case, I get patches with the same > effects, but the new B starts with "duplicate"). I thought commutation > was always supposed to be symmetric. Does that not apply when > conflictors are involved? You can rest assured that proper commutation is symmetric. The procedure I described is *not* a commutation! The 'rebase' and 'amend' commands create completely new patches that are unrelated to the original ones. It's more like 'darcs unrecord', fiddle around with the changes, then again 'darcs record' in a different order. As I said in the beginning, there is no force-commute command in darcs because that would be unsound. By definition, if B depends on A this means A;B does /not/ commute. In the theory, one starts with primitive patches for which there is no total merge operation, only a partial clean-merge that may fail. If you have two independently recorded patches A and B in the same context (we write this as A\/B), then clean-merge succeeds iff A^;B commutes (where ^ means inversion). If clean-merge(A\/B) does not succeed, then A\/B are said to be in conflict. When we add conflictors, we extend the set/type of primitive patches to a larger set, such that now any two patches can be merged. However, we must require that this extension preserves commutation behavior. In particular, if A;B does not commute, then their embeddings in the larger set of patches must commute neither. I know that Judah Jacobsen in his inverse semigroup paper writes that adding conflictors makes any two patches commutable. This is wrong. He derived this from the square commute law. But when you add conflictors, this law is no longer valid. Indeed, the existence of the square-commute law is precisely what distinguishes primitive patches from (potentially) conflicted ones. Another way to see the contradiction here is that if you can commute any two patches, then there is no longer any way to define (or calculate) which patches are in conflict: if A^;B always commutes, then A\/B always merges cleanly
Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?
Thanks, Ben! Responses inline. If you have the time, I'd be curious to hear about why my expectations didn't match what darcs actually did. > > What I'd like to do is create a repository R1 with patches A and B, > > and then look at the patches that result if A and B get > > force-commuted. > > > > E.g. if I could pull just patch B and not A to a new repository, I > > think that would do the trick, but of course darcs pull won't let me > > do that because B depends on A. > > The main question here is: What do you expect the result of such a > force-commute would be? > > Let us take a very simple example: > > A = addfile ./foo > B = hunk ./foo 1 [] ["some text"] > > where the hunk notation is simplified but hopefully understandable (the > hunk here removes no lines and adds the line "some text"). > > Suppose you had a 'darcs force-commute' command, and you force-commuted > A;B to B';A'. What would you expect the B' then A' to be? I've been reading about patch theory [0]. I *thought* what's supposed to happen is this: * The effect of B' is the same as the effect of A. (i.e. create the file) * The effect of A' is the same as the effect of B. (i.e. add "some text") * Therefore, B'A' does the same thing as AB. * B' and A' include some information about the conflict, in addition to their effects described above. (They are "conflictor" patches.) * If I commute B' and A' again, I get back AB, since <-> is a symmetric relation. However, that doesn't seem to be what happened (see below). Even if that were correct, it still doesn't leave me with a complete picture of what darcs actually does, so I wanted to experiment. > > Question 1: Is there a simple way to make darcs do this? > > Not exactly simple, but it is possible: > > darcs clone . ../saved > darcs rebase suspend # select B and A > darcs rebase obliterate # select A > darcs rebase unsuspend # select B > darcs pull ../saved # select A > > You should expect to get conflicts first when you unsuspend B (after > obliterating A) and then also when you re-pull A from the clone. You > will probably want to amend the conflict resolution into the conflicted > patch. Thanks, that seems to have worked. (I only got the first conflict, not the second.) But now I'm confused. Based on, for example, the "Forced commutation" section of https://en.wikibooks.org/wiki/Understanding_Darcs/Patch_theory_and_conflicts , I expected B' to add the file "foo", and A' to add "some text" (so, B' has the effect of A and A' has the effect of B). Instead of that, I get this: (a) If I follow your advice and amend the conflict resolution into B' before pulling, then (the amended) B' has the effect of AB, and A' has no effect. (b) If I run "darcs revert" instead of amending the conflict resolution into B', then B' has the effect of A and A' still has no effect. Confusingly, darcs offers to pull B from ../saved --- I thought darcs should consider it to already be present (as B'). I also noticed that if I run the swap a second time, I don't exactly get A and B back. (In the (a) case, I get patches with the same effects, but the new B starts with "duplicate"). I thought commutation was always supposed to be symmetric. Does that not apply when conflictors are involved? > Cheers > Ben Thanks, James [0] "Understanding darcs" on Wikibooks, "A formalization of Darcs patch theory using inverse semigroups", and some of Camp's "theory.pdf" ___ darcs-users mailing list darcs-users@osuosl.org https://lists.osuosl.org/mailman/listinfo/darcs-users
Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?
Am 25.06.20 um 18:52 schrieb James Cook: > I'm trying to learn more about how darcs force commutes work. There is a reason we do not have such a command ;-) > What I'd like to do is create a repository R1 with patches A and B, > and then look at the patches that result if A and B get > force-commuted. > > E.g. if I could pull just patch B and not A to a new repository, I > think that would do the trick, but of course darcs pull won't let me > do that because B depends on A. The main question here is: What do you expect the result of such a force-commute would be? Let us take a very simple example: A = addfile ./foo B = hunk ./foo 1 [] ["some text"] where the hunk notation is simplified but hopefully understandable (the hunk here removes no lines and adds the line "some text"). Suppose you had a 'darcs force-commute' command, and you force-commuted A;B to B';A'. What would you expect the B' then A' to be? > Question 1: Is there a simple way to make darcs do this? Not exactly simple, but it is possible: darcs clone . ../saved darcs rebase suspend # select B and A darcs rebase obliterate # select A darcs rebase unsuspend # select B darcs pull ../saved # select A You should expect to get conflicts first when you unsuspend B (after obliterating A) and then also when you re-pull A from the clone. You will probably want to amend the conflict resolution into the conflicted patch. > Question 2: Is there a way to make "darcs changes" show the patch > contents? -v or --verbose is your friend here. Cheers Ben ___ darcs-users mailing list darcs-users@osuosl.org https://lists.osuosl.org/mailman/listinfo/darcs-users
Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?
(re-sending 3 days later; sorry if this arrives twice) Hi darcs-users, I'm trying to learn more about how darcs force commutes work. What I'd like to do is create a repository R1 with patches A and B, and then look at the patches that result if A and B get force-commuted. E.g. if I could pull just patch B and not A to a new repository, I think that would do the trick, but of course darcs pull won't let me do that because B depends on A. Question 1: Is there a simple way to make darcs do this? I can think of two complicated ways, which I might resort to: (a) Play with the darcs source code. (b) Set up contrived situations involving merges to force darcs to do the force-commutes I'm looking for. Question 2: Is there a way to make "darcs changes" show the patch contents? For now, I've been manually examining files in _darcs/patches. I vaguely remember there's an option to darcs changes or a related command to show the patch contents, but I can't seem to find it now. Thanks, James ___ darcs-users mailing list darcs-users@osuosl.org https://lists.osuosl.org/mailman/listinfo/darcs-users
