Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?

2020-06-30 Thread Ben Franksen
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?

2020-06-29 Thread James Cook
> 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?

2020-06-29 Thread 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?

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?

2020-06-29 Thread Ben Franksen
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?

2020-06-29 Thread 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.)

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?

2020-06-29 Thread Ben Franksen
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?

2020-06-29 Thread Ben Franksen
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?

2020-06-29 Thread 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.

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?

2020-06-29 Thread 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?

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?

2020-06-29 Thread Ben Franksen
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?

2020-06-28 Thread James Cook
> 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?

2020-06-27 Thread Ben Franksen
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

Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?

2020-06-26 Thread 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.

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?

2020-06-26 Thread Ben Franksen
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 

Re: [darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?

2020-06-25 Thread James Cook
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?

2020-06-25 Thread Ben Franksen
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?

2020-06-25 Thread James Cook
(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