[darcs-devel] [patch1758] resolve issue2605: allow common patches to be non-consecutive

Ben Franksen bugs at darcs.net
Tue Nov 20 12:27:27 UTC 2018


Ben Franksen <ben.franksen at online.de> added the comment:

> 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.)

__________________________________
Darcs bug tracker <bugs at darcs.net>
<http://bugs.darcs.net/patch1758>
__________________________________


More information about the darcs-devel mailing list