Class of patches that have an identity.

It generalizes named prim patches a la camp (see Darcs.Patch.Prim.Named) and Named patches i.e. those with a PatchInfo.

Patch identity should be invariant under commutation: if there is also an instance Commute p, then

commute (p :> q) == Just (q' :> p') => ident p == ident p' && ident q == ident q'

The converse should also be true: patches with the same identity can be commuted (back) to the same context and then compare equal. Assuming

  p :: p wX wY, (ps :> q) :: (RL p :> p) wX wZ

then

ident p == ident q => commuteRL (ps :> q) == Just (p :> _)

As a special case we get that parallel patches with the same identity are equal: if p :: p wX wY, q :: p wX wZ, then

ident p == ident q => p =\/= q == IsEq

In general, comparing patches via their identity is coarser than (structural) equality, so we only have

unsafeCompare p q => (ident p == ident q)

Constraint for patches that have an identity that is signed, i.e. can be positive (uninverted) or negative (inverted).

Provided that an instance Invert exists, inverting a patch inverts its identity:

ident (invert p) = invertId (ident p)

Signed identities.

Like for class Invert, we require that invertId is self-inverse:

invertId . invertId = id

We also require that inverting changes the sign:

positiveId . invertId = not . positiveId

Side remark: in mathematical terms, these properties can be expressed by stating that invertId is an involution and that positiveId is a "homomorphism of sets with an involution" (there is no official term for this) from a to the simplest non-trivial set with involution, namely Bool with the involution not.

Storable identities.

The methods here can be used to help implement ReadPatch and ShowPatch for a patch type containing the identity.

As with all Read/Show pairs, We expect that the output of showId ForStorage a can be parsed by readId to produce a.

Faster equality tests for patches with an identity.

This function is similar to merge, but with one important difference: merge works on patches for which there is not necessarily a concept of identity (e.g. primitive patches, conflictors, etc). Thus it does not even try to recognize patches that are common to both sequences. Instead these are passed on to the Merge instance for single patches. This instance may handle duplicate patches by creating special patches (Duplicate, Conflictor).

We do not want this to happen for named patches, or in general for patches with an identity. Instead, we want to discard one of the two duplicates, retaining only one copy. This is done by the fastRemoveFL calls below. We call mergeFL only after we have ensured that the head of the left hand side does not occur in the right hand side.

Remove a patch from an FL of patches with an identity. The result is Just whenever the patch has been found and removed and Nothing otherwise. If the patch is not found at the head of the sequence we must first commute it to the head before we can remove it.

We assume that this commute always succeeds. This is justified because patches are created with a (universally) unique identity, implying that if two patches have the same identity, then they have originally been the same patch; thus being at a different position must be due to commutation, meaning we can commute it back.

Same as fastRemoveFL only for RL.

Find the common and uncommon parts of two lists that start in a common context, using patch identity for comparison. Of the common patches, only one is retained, the other is discarded, similar to merge2FL.

Try to commute patches matching any of the PatchIds in the set to the head of an FL, i.e. backwards in history. It is not required that all the PatchIds are found in the sequence, but if they do then the traversal terminates as soon as the set is exhausted.

Try to commute patches matching any of the PatchIds in the set to the head of an RL, i.e. forwards in history. It is not required that all the PatchIds are found in the sequence, but if they do then the traversal terminates as soon as the set is exhausted.

Like commuteToPostfix but drag dependencies with us.