darcs

Patch 1758 resolve issue2605: allow common patches to be non-consecutive

Title resolve issue2605: allow common patches to be non-consecutive
Superseder Nosy List bf
Related Issues
Status rejected Assigned To
Milestone

Created on 2018-11-03.16:39:53 by bf, last changed 2019-01-24.15:31:45 by bf.

Files
File name Status Uploaded Type Edit Remove
patch-preview.txt bf, 2018-11-16.11:28:01 text/x-darcs-patch
resolve-issue2605_-allow-common-patches-to-be-non_consecutive.dpatch bf, 2018-11-16.11:28:01 application/x-darcs-patch
unnamed bf, 2018-11-16.11:28:01 text/plain
See mailing list archives for discussion on individual patches.
Messages
msg20436 (view) Author: bf Date: 2018-11-03.16:39:51
6 patches for repository http://darcs.net/screened:

patch 01fc5a5889e7c0e5b874134257197e777b771ff6
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Oct 31 17:02:56 CET 2018
  * extended test for issue2605

patch c786b747981ba0628a55bfe399f0c34c0e21da46
Author: Ben Franksen <ben.franksen@online.de>
Date:   Thu Nov  1 17:16:24 CET 2018
  * accept issue2606: improve handling of dependency swaps

patch ea33e52a9e21100c435cae1968d7c40a4f8b8cea
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Oct 31 18:48:53 CET 2018
  * resolve issue2605: allow common patches to be non-consecutive
  
  The basic functionality is fully implementated. In particular, patch
  selection does not offer common patches to the user; they are silently
  marked as "undecided" i.e. are included in the selection if required by
  dependencies. Common patches still appear in some of the messages displayed
  to the user. This will be fixed in another patch. It is now painfully
  obvious that we need a more efficient way to represent sets of patch names,
  which is (still) done using lists and linear search.
  
  The test for issue1879 has been removed because it is no longer valid and
  its (invalid) fix has been reverted by this patch. I will re-open the issue.

patch e08759838bebe7cd0bf36440f7bdf6f3c09ff9a4
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Oct 31 20:40:00 CET 2018
  * use Data.HashSet for sets of PatchInfos
  
  This adds a dependency on unordered-containers which I think is justified.
  Note that comparing PatchInfo is expensive, which makes an array mapped trie
  a much better option than a balanced tree based container like Data.Set.

patch 46d2946cdfa1f4599b83ab56f070afa609c407a4
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Nov  2 13:57:32 CET 2018
  * fix numbering of patches in patch selection with hidden patches

patch ff4eb633aae94c20e020677d780882fcbba180fc
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Nov  2 17:49:34 CET 2018
  * remove common patches from all messages
  
  This adds another argument of type PatchPredicate to some calls which issue
  messages based on a list of selected patches. The argument is used to filter
  out the patches that should not be shown, usually patches common between
  remote and local repo.
Attachments
msg20446 (view) Author: bf Date: 2018-11-08.18:51:08
This bundle rebases the last patch to avoid a conflict with patch1742.

6 patches for repository http://darcs.net/screened:

patch 01fc5a5889e7c0e5b874134257197e777b771ff6
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Oct 31 17:02:56 CET 2018
  * extended test for issue2605

patch c786b747981ba0628a55bfe399f0c34c0e21da46
Author: Ben Franksen <ben.franksen@online.de>
Date:   Thu Nov  1 17:16:24 CET 2018
  * accept issue2606: improve handling of dependency swaps

patch ea33e52a9e21100c435cae1968d7c40a4f8b8cea
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Oct 31 18:48:53 CET 2018
  * resolve issue2605: allow common patches to be non-consecutive
  
  The basic functionality is fully implementated. In particular, patch
  selection does not offer common patches to the user; they are silently
  marked as "undecided" i.e. are included in the selection if required by
  dependencies. Common patches still appear in some of the messages displayed
  to the user. This will be fixed in another patch. It is now painfully
  obvious that we need a more efficient way to represent sets of patch names,
  which is (still) done using lists and linear search.
  
  The test for issue1879 has been removed because it is no longer valid and
  its (invalid) fix has been reverted by this patch. I will re-open the issue.

patch e08759838bebe7cd0bf36440f7bdf6f3c09ff9a4
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Oct 31 20:40:00 CET 2018
  * use Data.HashSet for sets of PatchInfos
  
  This adds a dependency on unordered-containers which I think is justified.
  Note that comparing PatchInfo is expensive, which makes an array mapped trie
  a much better option than a balanced tree based container like Data.Set.

patch 46d2946cdfa1f4599b83ab56f070afa609c407a4
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Nov  2 13:57:32 CET 2018
  * fix numbering of patches in patch selection with hidden patches

patch bb0b3667a9e4f33f282d2523c62dd98ed28cea9e
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Nov  2 17:49:34 CET 2018
  * remove common patches from all messages
  
  This adds another argument of type PatchPredicate to some calls which issue
  messages based on a list of selected patches. The argument is used to filter
  out the patches that should not be shown, usually patches common between
  remote and local repo.
Attachments
msg20449 (view) Author: bf Date: 2018-11-08.19:17:46
Once again last patch rebased to fix a bug in the push command where I
forgot to add a 'not'.

6 patches for repository http://darcs.net/screened:

patch 01fc5a5889e7c0e5b874134257197e777b771ff6
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Oct 31 17:02:56 CET 2018
  * extended test for issue2605

patch c786b747981ba0628a55bfe399f0c34c0e21da46
Author: Ben Franksen <ben.franksen@online.de>
Date:   Thu Nov  1 17:16:24 CET 2018
  * accept issue2606: improve handling of dependency swaps

patch ea33e52a9e21100c435cae1968d7c40a4f8b8cea
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Oct 31 18:48:53 CET 2018
  * resolve issue2605: allow common patches to be non-consecutive
  
  The basic functionality is fully implementated. In particular, patch
  selection does not offer common patches to the user; they are silently
  marked as "undecided" i.e. are included in the selection if required by
  dependencies. Common patches still appear in some of the messages displayed
  to the user. This will be fixed in another patch. It is now painfully
  obvious that we need a more efficient way to represent sets of patch names,
  which is (still) done using lists and linear search.
  
  The test for issue1879 has been removed because it is no longer valid and
  its (invalid) fix has been reverted by this patch. I will re-open the issue.

patch e08759838bebe7cd0bf36440f7bdf6f3c09ff9a4
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Oct 31 20:40:00 CET 2018
  * use Data.HashSet for sets of PatchInfos
  
  This adds a dependency on unordered-containers which I think is justified.
  Note that comparing PatchInfo is expensive, which makes an array mapped trie
  a much better option than a balanced tree based container like Data.Set.

patch 46d2946cdfa1f4599b83ab56f070afa609c407a4
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Nov  2 13:57:32 CET 2018
  * fix numbering of patches in patch selection with hidden patches

patch 6fa5efd31460f8cf0de00f344059d43b46791ed9
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Nov  2 17:49:34 CET 2018
  * remove common patches from all messages
  
  This adds another argument of type PatchPredicate to some calls which issue
  messages based on a list of selected patches. The argument is used to filter
  out the patches that should not be shown, usually patches common between
  remote and local repo.
Attachments
msg20454 (view) Author: bf Date: 2018-11-12.19:54:33
This is an additional bundle that adds a bug fix patch.

The bug in question manifests as a failure of the "Patch not stored in patch
bundle" sort when applying a patch bundle that has common patches in the
context in a different order than in the repo where we apply the bundle. The
bug was introduced by

  * resolve issue2605: allow common patches to be non-consecutive

in which I re-implemented findCommonWithThem in terms of the more general
findCommonAndUncommon. This is okay but one has to make sure that the third
component of the Fork returned by findCommonAndUncommon is produced lazily,
so that we don't try to commute the common patches from the bundle, of which
we have only the PatchInfo and not the content.

3 patches for repository http://darcs.net/screened:

patch ea33e52a9e21100c435cae1968d7c40a4f8b8cea
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Oct 31 18:48:53 CET 2018
  * resolve issue2605: allow common patches to be non-consecutive
  
  The basic functionality is fully implementated. In particular, patch
  selection does not offer common patches to the user; they are silently
  marked as "undecided" i.e. are included in the selection if required by
  dependencies. Common patches still appear in some of the messages displayed
  to the user. This will be fixed in another patch. It is now painfully
  obvious that we need a more efficient way to represent sets of patch names,
  which is (still) done using lists and linear search.
  
  The test for issue1879 has been removed because it is no longer valid and
  its (invalid) fix has been reverted by this patch. I will re-open the issue.

patch e08759838bebe7cd0bf36440f7bdf6f3c09ff9a4
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Oct 31 20:40:00 CET 2018
  * use Data.HashSet for sets of PatchInfos
  
  This adds a dependency on unordered-containers which I think is justified.
  Note that comparing PatchInfo is expensive, which makes an array mapped trie
  a much better option than a balanced tree based container like Data.Set.

patch 9107fcbc0aff1f20c7314c9f8d641995eca72a23
Author: Ben Franksen <ben.franksen@online.de>
Date:   Mon Nov 12 20:30:44 CET 2018
  * fix a subtle bug in findCommonAndUncommon
  
  This became an issue only because findCommonWithThem is now implemented in
  terms of findCommonAndUncommon. This was a rather subtle laziness bug, so I
  added a detailed explanation in a comment.
Attachments
msg20468 (view) Author: bf Date: 2018-11-16.11:28:01
This is a full replacement bundle that contains yet another bug fix patch as
well as a patch that cleans up and extends the test script.

I have not rebased the original patch because I think it is pretty
instructive to study the two failures and how to fix them.

After using this version for some time I am now quite confident that
embracing and fixing merge by value is the right thing to do. While it adds
a bit of complexity in the UI to filter out common patches that cannot be
commuted to a common shared history, this is by far less than I originally
thought would be needed.

9 patches for repository http://darcs.net/screened:

patch ea33e52a9e21100c435cae1968d7c40a4f8b8cea
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Oct 31 18:48:53 CET 2018
  * resolve issue2605: allow common patches to be non-consecutive
  
  The basic functionality is fully implementated. In particular, patch
  selection does not offer common patches to the user; they are silently
  marked as "undecided" i.e. are included in the selection if required by
  dependencies. Common patches still appear in some of the messages displayed
  to the user. This will be fixed in another patch. It is now painfully
  obvious that we need a more efficient way to represent sets of patch names,
  which is (still) done using lists and linear search.
  
  The test for issue1879 has been removed because it is no longer valid and
  its (invalid) fix has been reverted by this patch. I will re-open the issue.

patch 46d2946cdfa1f4599b83ab56f070afa609c407a4
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Nov  2 13:57:32 CET 2018
  * fix numbering of patches in patch selection with hidden patches

patch e08759838bebe7cd0bf36440f7bdf6f3c09ff9a4
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Oct 31 20:40:00 CET 2018
  * use Data.HashSet for sets of PatchInfos
  
  This adds a dependency on unordered-containers which I think is justified.
  Note that comparing PatchInfo is expensive, which makes an array mapped trie
  a much better option than a balanced tree based container like Data.Set.

patch 9107fcbc0aff1f20c7314c9f8d641995eca72a23
Author: Ben Franksen <ben.franksen@online.de>
Date:   Mon Nov 12 20:30:44 CET 2018
  * fix a subtle bug in findCommonAndUncommon
  
  This became an issue only because findCommonWithThem is now implemented in
  terms of findCommonAndUncommon. This was a rather subtle laziness bug, so I
  added a detailed explanation in a comment.

patch 01fc5a5889e7c0e5b874134257197e777b771ff6
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Oct 31 17:02:56 CET 2018
  * extended test for issue2605

patch 6fa5efd31460f8cf0de00f344059d43b46791ed9
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Nov  2 17:49:34 CET 2018
  * remove common patches from all messages
  
  This adds another argument of type PatchPredicate to some calls which issue
  messages based on a list of selected patches. The argument is used to filter
  out the patches that should not be shown, usually patches common between
  remote and local repo.

patch 2ec71857d9cefc819af4b8b804b60251d9ae5a5c
Author: Ben Franksen <ben.franksen@online.de>
Date:   Thu Nov 15 10:59:54 CET 2018
  * fix in test for issue2605

patch 273c53ee327748d7549403c3c55296d67f95b9db
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Nov 16 11:52:56 CET 2018
  * clean up, extend, and comment test for issue2605

patch d5a1b68dc420455eed6c4f6d6ae3e22107691669
Author: Ben Franksen <ben.franksen@online.de>
Date:   Thu Nov 15 10:53:10 CET 2018
  * fix in mergeThem after resolving issue2605
  
  This procedure is used to update the unrevert bundle. It calls merge2FL
  which is now more sensitive to "unavailable" patches (i.e. those in the
  context of a bundle, for which we only have the meta data but not the
  content). This can lead to errors of the "Patch not stored in patch bundle"
  sort. The solution is to remove all context patches before we call merge2FL
  by using findUncommon instead of just taggedIntersection. Note that common
  patches that cannot be commuted to the common trunk are always included
  (with content) in a bundle; they are filtered out only when we apply it.
Attachments
msg20538 (view) Author: ganesh Date: 2018-11-20.08:24:04
As expected, I am nervous about this change :-)

It's clear that the current situation isn't good. Darcs is trying to
implement "merge by name" but has some bugs that means you can sort
of get "merge by value" if you try hard enough. So if we tried to
rely on any strong global properties from merge by name, we'd have
bugs. So we should certainly do something, and I haven't (yet :-))
found a killer argument against merge by name. Some random thoughts
below.

It's worth reminding ourselves that we can never rely on merge
by name for any kind of security/integrity properties anyway,
as someone can always edit a  repository by hand.

Can we rely on the contents of tags to be immutable given this
change? It seems that they always list every named patch not
covered by another tag, but I'm never quite sure about that
implementation. We should probably strengthen our guarantees about
this.

"X depends on Y" is now "X depends on [Y1 or Y2]". What does this
mean when we start thinking about X's transitive dependencies?
Personally I feel I'm losing a lot of intuition about how darcs
should behave, but perhaps I just need time to embrace it.

Does merge by value support replacing with "near duplicates" as well
as exact duplicates, i.e. in the sequence X;Z where Z depends on X,
can we also replace X with any other patch that sets up the
right context for Z?

If the intention of merge by value is to support replacing
dependencies, should we offer some UI for doing this directly?
Doing it via having a temporary duplicate is quite awkward,
especially in darcs-1 where it's a conflict (and will be again
in darcs-3, I guess).

It's also confusing, and arguably a bug, that if I have P_1;Q in
one repository and P_2 in another where P_2 is equal by value to 
P_1, I can't just pull Q on its own into the other repo - but I can 
pull P_1;Q then unpull P_1. This suggests that cross-repo patch 
selection needs to be rethought to be consistent with the new 
merging behaviour.

This change might also make your desired behaviour for rebase 
feasible, where patches only change identity lazily, but we'd have 
to think it through and I'm again nervous :-)
msg20541 (view) Author: bf Date: 2018-11-20.12:27:26
> As expected, I am nervous about this change :-)

I am glad we can discuss this now.

> It's clear that the current situation isn't good. Darcs is trying to
> implement "merge by name" but has some bugs that means you can sort
> of get "merge by value" if you try hard enough. 

Umm. Yes one could see it that way.

> So if we tried to
> rely on any strong global properties from merge by name, we'd have
> bugs. So we should certainly do something, and I haven't (yet :-))
> found a killer argument against merge by name. Some random thoughts
> below.
> 
> It's worth reminding ourselves that we can never rely on merge
> by name for any kind of security/integrity properties anyway,
> as someone can always edit a  repository by hand.

This has always been a weakness of Darcs. To correctly apply a patch we
need a suitable context and the patch itself cannot give it to us. This
is why we need inventories and though these are hashed, too, I think it
is possible to fake a repo which applies patches in an incorrect order,
possibly leading to corruption when we merge it. And explicit
dependencies (including tags) only refer to the meta data so that isn't
secure either.

> Can we rely on the contents of tags to be immutable given this
> change? It seems that they always list every named patch not
> covered by another tag, but I'm never quite sure about that
> implementation. We should probably strengthen our guarantees about
> this.

I am pretty confident that tags and explicit dependencies are not
weakened in any way by this change. Explicit dependencies /are/ by name
and this is enforced on top of all the RepoPatch commute/merge logic.

"strengthen our guarantees about this" sounds good, but I am not sure
what exactly you mean. Are you thinking of adding a property we should
check?

> "X depends on Y" is now "X depends on [Y1 or Y2]". What does this
> mean when we start thinking about X's transitive dependencies?

I guess "the set of (transitive) dependencies of a patch" is no longer a
well-defined notion.

> Personally I feel I'm losing a lot of intuition about how darcs
> should behave, but perhaps I just need time to embrace it.

I think your feeling is correct. Reasoning about a merge-by-name based
system /is/ simpler. It allows to abstract over the fact that a named
patch consists of a sequence of smaller changes. Reasoning at a higher
level of abstraction usually simplifies things, the mental model is less
complex, and I think that gives us "more intuitive" behavior.

Merge by value means we have to be aware that named patches are really
just change-sets: a certain set/sequence of more elementary changes that
we happen to have lumped together in a single named patch. It also makes
the notion of dependency rather more slippery when considering not only
a single repo but the universe of all repositories. An infinite graph of
"possible dependencies" so to speak.

I don't think merge-by-value is "better" than merge-by-name in any
absolute sense. It /is/ more powerful but it is also more low-level and
thus more difficult to reason about.

The problem is that you cannot build merge-by-name in a sound way on top
of a pure merge-by-value RepoPatch type with "generic" conflictors. In
that Ian was absolutely right and his argument in Appendix B of his
paper is irrefutable.

This means we have no other choice than to embrace merge-by-value unless
we go the whole way and add identifiers to prim patches as Ian did with
Camp. Doing nothing means we accept that Darcs is fundamentally unsound
at its core and that is the worst of our options. Being logically
consistent is the raison d'├Ętre for Darcs!

> Does merge by value support replacing with "near duplicates" as well
> as exact duplicates, i.e. in the sequence X;Z where Z depends on X,
> can we also replace X with any other patch that sets up the
> right context for Z?

Yes, absolutely. I should add a test to confirm that this is true. This
is a simple consequence of commute/merge for named patches being
implemented in terms of commute/merge for the underlying RepoPatch type.
Implicit dependencies are really only between RepoPatches.

> If the intention of merge by value is to support replacing
> dependencies, should we offer some UI for doing this directly?
> Doing it via having a temporary duplicate is quite awkward,
> especially in darcs-1 where it's a conflict (and will be again
> in darcs-3, I guess).

Yes, this is awkward, see issue2606.

> It's also confusing, and arguably a bug, that if I have P_1;Q in
> one repository and P_2 in another where P_2 is equal by value to 
> P_1, I can't just pull Q on its own into the other repo - but I can 
> pull P_1;Q then unpull P_1. This suggests that cross-repo patch 
> selection needs to be rethought to be consistent with the new 
> merging behaviour.

I agree that this is strange. To fix this I think we need to /first/
merge the two sequences, then select patches from the result,
suppressing display of common (by name) patches (the latter is already
implemented in this bundle). The problem here is a practical one: such a
merge may involve more patches than the user is interested in and thus
may not be quite as efficient when we give e.g. matching options.

> This change might also make your desired behaviour for rebase 
> feasible, where patches only change identity lazily, but we'd have 
> to think it through and I'm again nervous :-)

Interesting. I don't see the connection yet. Could you explain in more
detail? (I guess this doesn't strictly belong here and should be
discussed separately.)
msg20545 (view) Author: bf Date: 2018-11-20.16:27:57
> The problem is that you cannot build merge-by-name in a sound way on top
> of a pure merge-by-value RepoPatch type with "generic" conflictors. In
> that Ian was absolutely right and his argument in Appendix B of his
> paper is irrefutable.
> 
> This means we have no other choice than to embrace merge-by-value unless
> we go the whole way and add identifiers to prim patches as Ian did with
> Camp.

Let me qualify this. It may not be necessary to attach identities to all
prim patches as in Camp. In principle it should suffice to tag prim
patches /inside a conflictor/ with the (meta-data) hash of the named
patch they belong to. This relies on the reasonable assumption/invariant
that a single named patch cannot contain duplicate prims.

However, this would still be incompatible with both our existing patch
formats.

>> Does merge by value support replacing with "near duplicates" as well
>> as exact duplicates, i.e. in the sequence X;Z where Z depends on X,
>> can we also replace X with any other patch that sets up the
>> right context for Z?
> 
> Yes, absolutely. I should add a test to confirm that this is true. This
> is a simple consequence of commute/merge for named patches being
> implemented in terms of commute/merge for the underlying RepoPatch type.
> Implicit dependencies are really only between RepoPatches.

In fact I regard this as the killer-feature of merge-by-value. Suppose
patch B depends on a small change contained in patch A. We want to pull
B, but not A because A contains other changes that are incompatible or
unwanted, perhaps causing lots of hard to resolve conflicts with our
repo. We can then create A' that contains /only/ a duplicate of the
small change that B depends upon, and then pull B without A. With
merge-by-name this is impossible.

I have added a comment to issue2606 that explores a possible UI.
msg20548 (view) Author: ganesh Date: 2018-11-22.07:43:40
On 20/11/2018 16:27, Ben Franksen wrote:
> 
> Ben Franksen <ben.franksen@online.de> added the comment:

>> The problem is that you cannot build merge-by-name in a sound way on top
>> of a pure merge-by-value RepoPatch type with "generic" conflictors. In
>> that Ian was absolutely right and his argument in Appendix B of his
>> paper is irrefutable.
>>
>> This means we have no other choice than to embrace merge-by-value unless
>> we go the whole way and add identifiers to prim patches as Ian did with
>> Camp.
> 
> Let me qualify this. It may not be necessary to attach identities to all
> prim patches as in Camp. In principle it should suffice to tag prim
> patches /inside a conflictor/ with the (meta-data) hash of the named
> patch they belong to. This relies on the reasonable assumption/invariant
> that a single named patch cannot contain duplicate prims.
> 
> However, this would still be incompatible with both our existing patch
> formats.

Clearly this would make on-disk repositories incompatible, but I think
it would still be safe to exchange patches with non-upgraded
repositories. If someone had swapped out a dependency then there'd be a
problem, of course, perhaps at an unpredictable moment.

I played with this idea quite a while ago when I was trying to improve
conflict marking by annotating conflicting section with the named patch
they came from. To get the names if they're not available, you have to
commute conflicts far enough back to find the patches they conflict
with, then commute again forward with the new patch representation
annotated with the names.

My old code is here https://hub.darcs.net/ganesh/darcs-conflict-marking
for what it's worth (not very much).

>> Can we rely on the contents of tags to be immutable given this
>> change? It seems that they always list every named patch not
>> covered by another tag, but I'm never quite sure about that
>> implementation. We should probably strengthen our guarantees about
>> this.
> 
> I am pretty confident that tags and explicit dependencies are not
> weakened in any way by this change. Explicit dependencies /are/ by name
> and this is enforced on top of all the RepoPatch commute/merge logic.
> 
> "strengthen our guarantees about this" sounds good, but I am not sure
> what exactly you mean. Are you thinking of adding a property we should
> check?

I'm not sure exactly what I mean either :-) But overall it'd be about
trying to make it very clear to future developers and users that tags
must always *explicitly* depend on every single named patch in the repo,
either directly or indirectly.

The ways we could do this would include tests, comments in the code and
perhaps the documentation of the tag command.


>>> Does merge by value support replacing with "near duplicates" as well
>>> as exact duplicates, i.e. in the sequence X;Z where Z depends on X,
>>> can we also replace X with any other patch that sets up the
>>> right context for Z?
>>
>> Yes, absolutely. I should add a test to confirm that this is true. This
>> is a simple consequence of commute/merge for named patches being
>> implemented in terms of commute/merge for the underlying RepoPatch type.
>> Implicit dependencies are really only between RepoPatches.
> 
> In fact I regard this as the killer-feature of merge-by-value. Suppose
> patch B depends on a small change contained in patch A. We want to pull
> B, but not A because A contains other changes that are incompatible or
> unwanted, perhaps causing lots of hard to resolve conflicts with our
> repo. We can then create A' that contains /only/ a duplicate of the
> small change that B depends upon, and then pull B without A. With
> merge-by-name this is impossible.
> 
> I have added a comment to issue2606 that explores a possible UI.

I should clarify what I meant by "near duplicate"; I understand that we
only need a duplicate of the specific Prim in A that B depends on. But
can we also use a slightly different Prim that happens to setup exactly
the same context as the original? For example:

A:
hunk ./file1.txt 1
-line1
-line2
-line3
+line1A
+line2A
+line3A

B:
hunk ./file1.txt 3
-line3A
-line4
+line3B
+line4B

A':
hunk ./file1.txt 1
-line1
-line2
-line3
+line1A'
+line2A
+line3A

Given that in darcs-1, we can swap A for a duplicate of A even though
they actively conflict, I was wondering if we can also swap A for A'.

After a bit of experimenting and thinking about it, I don't think we
can, because we can never get B into a suitable context.

Cheers,

Ganesh
msg20552 (view) Author: bf Date: 2018-11-24.18:21:21
[about re-constructing patch identities with existing formats]
> [...] To get the names if they're not available, you have to
> commute conflicts far enough back to find the patches they conflict
> with, then commute again forward with the new patch representation
> annotated with the names.

It sounds plausible to me that this should be possible, but only under
the assumption that there are no duplicates present in the repo. More
precisely, no duplicates that can be commuted into proximity. Otherwise
which of the two candidates would be chosen?

> trying to make it very clear to future developers and users that tags
> must always *explicitly* depend on every single named patch in the repo,
> either directly or indirectly.
> 
> The ways we could do this would include tests, comments in the code and
> perhaps the documentation of the tag command.

Agreed.

> I should clarify what I meant by "near duplicate"; I understand that we
> only need a duplicate of the specific Prim in A that B depends on. But
> can we also use a slightly different Prim that happens to setup exactly
> the same context as the original?

Ah, okay.

[snip example with B depending on A or A', where both A' and A establish
a suitable context for B but aren't equal]

> Given that in darcs-1, we can swap A for a duplicate of A even though
> they actively conflict, I was wondering if we can also swap A for A'.
> 
> After a bit of experimenting and thinking about it, I don't think we
> can, because we can never get B into a suitable context.

Yes, since this is all about equality of patches and we have no notion
of "partial equality".

What do we need to make the dependency swap succeed? Suppose we have
R1=A1 and R2=A2:>B and pull A1 into R2, getting R2'=A2:>B:>A1'. We need
to have

(1)  B:>A1' <--> A1'':>B'

then

(2)  A2:>A1'' <--> A1''':>A2'

and finally

(3)  A2':>B' <--> B'':> A2''

We can get (1) and (2) to succeed easily because these are obviously
conflicting commutes. But (3) is not, unless A1 and A2 happen to be
(exactly) equal.

The crucial point are the rules for commuting conflicting patches. To
see whether A2':>B' should commute, we check whether B' matches the
result of a conflicted merge with A2', and in that case return the other
branch of the conflict. That requires us to compare A2' with (some
version of) A1 that we stored inside the B' conflictor. If they are
equal the commute succeeds, otherwise it doesn't. Merge-by-value just
means that the comparison is done by value, whereas merge-by-name means
that we also take the origin of the patches into account. In either
case, if the patches don't even have exactly the same context, our rules
won't match and the commute fails.

I think this failure to recognize a situation where, in principle, we
could swap a dependency with another one, is a symptom of hunks being
"too large". A more fine-grained split into single-line hunks would make
your example succeed as some of the "more primitive" patches would then
become equal. Prim V1 hunks are geared toward practical usability
concerns, rather than allowing more fine-grained equality tests.
msg20558 (view) Author: ganesh Date: 2018-11-26.06:34:41
On 24/11/2018 18:21, Ben Franksen wrote:
> 
> Ben Franksen <ben.franksen@online.de> added the comment:
> 
> [about re-constructing patch identities with existing formats]
>> [...] To get the names if they're not available, you have to
>> commute conflicts far enough back to find the patches they conflict
>> with, then commute again forward with the new patch representation
>> annotated with the names.
> 
> It sounds plausible to me that this should be possible, but only under
> the assumption that there are no duplicates present in the repo. More
> precisely, no duplicates that can be commuted into proximity. Otherwise
> which of the two candidates would be chosen?

Yes, good point. I didn't know that was a problem in my old prototype,
and I think the earlier one would have just won by default.

If it did arise I'm not sure how to get out of it. Ultimately we want
the user to pick one of the two for us, but would that lead to a valid
repo? i.e. in the A1 :> A2 :> B case where A1 and A2 are duplicates and
B depends on them, if B now only depends on A1 where would that leave A2
- would the result still be a valid repo?

Ganesh
msg20634 (view) Author: bf Date: 2019-01-24.15:31:45
I am marking this bundle as rejected. The proposed solution is unsound:
it breaks permutivity, as explained in detail in issue2614.
History
Date User Action Args
2018-11-03 16:39:53bfcreate
2018-11-08 18:51:09bfsetfiles: + patch-preview.txt, extended-test-for-issue2605.dpatch, unnamed
messages: + msg20446
2018-11-08 19:17:46bfsetfiles: + patch-preview.txt, extended-test-for-issue2605.dpatch, unnamed
messages: + msg20449
2018-11-12 19:54:34bfsetfiles: + patch-preview.txt, resolve-issue2605_-allow-common-patches-to-be-non_consecutive.dpatch, unnamed
messages: + msg20454
2018-11-16 11:28:03bfsetfiles: + patch-preview.txt, resolve-issue2605_-allow-common-patches-to-be-non_consecutive.dpatch, unnamed
messages: + msg20468
2018-11-16 12:59:13bfsetfiles: - extended-test-for-issue2605.dpatch
2018-11-16 12:59:25bfsetfiles: - extended-test-for-issue2605.dpatch
2018-11-16 12:59:31bfsetfiles: - extended-test-for-issue2605.dpatch
2018-11-16 12:59:36bfsetfiles: - patch-preview.txt
2018-11-16 12:59:41bfsetfiles: - patch-preview.txt
2018-11-16 12:59:47bfsetfiles: - patch-preview.txt
2018-11-16 12:59:49bfsetfiles: - patch-preview.txt
2018-11-16 12:59:56bfsetfiles: - resolve-issue2605_-allow-common-patches-to-be-non_consecutive.dpatch
2018-11-16 13:00:01bfsetfiles: - unnamed
2018-11-16 13:00:08bfsetfiles: - unnamed
2018-11-16 13:00:10bfsetfiles: - unnamed
2018-11-16 13:00:12bfsetfiles: - unnamed
2018-11-20 08:24:05ganeshsetmessages: + msg20538
2018-11-20 12:27:27bfsetmessages: + msg20541
2018-11-20 16:27:57bfsetmessages: + msg20545
2018-11-22 07:43:42ganeshsetmessages: + msg20548
2018-11-24 18:21:22bfsetmessages: + msg20552
2018-11-26 06:34:42ganeshsetmessages: + msg20558
2018-11-26 22:43:02ganeshsetstatus: needs-screening -> in-discussion
2019-01-24 15:31:45bfsetstatus: in-discussion -> rejected
messages: + msg20634