[darcs-devel] Generic instances for FLs

Ben Franksen ben.franksen at online.de
Thu Jun 27 09:17:54 UTC 2019


For many patch classes X, we provide generic instances

  X p => X (FL p)

In some cases this works well, Commute is a good example.

However, for some classes this is problematic. My chief examples here
are Eq2 and Merge. In both cases we want to do something different if
the patch type p also has an (instance Ident).

For Eq2 the problem is efficiency. The generic instance needs to perform
commutation to see if two FLs are equal, since by definition we identify
two sequences that differ only in the order of patches. But if we have
identities, we can do this a lot more efficiently by just comparing two
sets of PatchIds.

For Merge the problem is to avoid accidentally using the wrong function.
I just discovered a bug in the V3 implementation for resolveConflicts
that was caused by the use of 'merge' for FLs when recombining
non-conflicting FLs of NamedPrims. Using the generic merge for FLs here
is wrong, because both FLs may have NamedPrims in common, i.e. a common
dependency. The generic merge doesn't know about identities, so it
treats the common dependency as a conflict! I should have used merge2FL
instead, which first pulls all common patches from both FLs to the left.
But due to a not yet published refactor the use of merge for FLs here
was hidden in another function that I imported, so this wasn't easy to
detect.

Ideally we would be able to say: Use the generic definition by default,
but if (Ident p) holds, then use another function. Is there a clean way
to do that in Haskell?

Note that having a generic instance Merge (FL p) is quite useful. For
instance, we can define a property once for Merge p => ... and then feed
it with single patches or FLs of patches. But this is not so useful if
this uses the wrong definition!

I think the best we can do here is to adopt the hack that the standard
libraries use for Show a => Show [a]. That is, we add a method
'mergeFLFL' to class Merge and then use that as the definition of merge
in the instance Merge p => Merge (FL p). Then we can define 'mergeFLFL =
merge2FL' if we have an instance Ident, and use the previous generic
definition otherwise. (BTW: the generic mergeFL function that merges a
single patch with an FL is also dangerous as it is now; it should be
redefined to use mergeFLFL.)

And similarly with Eq2 which would get another method unsafeCompareFL
(and probably unsafeCompareRL, too).

Any better ideas?

Cheers
Ben



More information about the darcs-devel mailing list