Safe Haskell | Trustworthy |
---|---|

Language | Haskell2010 |

For day-to-day use, please see Data.Patch

- newtype Patch a = Patch [Edit a]
- data Edit a
- inverse :: Patch a -> Patch a
- index :: Lens' (Edit a) Int
- old :: Traversal' (Edit a) a
- new :: Traversal' (Edit a) a
- toList :: Patch a -> [Edit a]
- unsafeFromList :: [Edit a] -> Patch a
- fromList :: Eq a => [Edit a] -> Patch a
- normalise :: [Edit a] -> [Edit a]
- apply :: Patch a -> Vector a -> Vector a
- transformWith :: Eq a => (a -> a -> a) -> Patch a -> Patch a -> (Patch a, Patch a)
- ours :: a -> a -> a
- theirs :: a -> a -> a
- transform :: (Eq a, Monoid a) => Patch a -> Patch a -> (Patch a, Patch a)
- diff :: Eq a => Vector a -> Vector a -> Patch a
- data HunkStatus
- type Hunks a = [(Vector a, HunkStatus)]
- hunks :: Patch a -> Vector a -> Hunks a

# Documentation

`>>>`

`import Test.QuickCheck`

`>>>`

let nonEmpty :: Vector a -> Bool nonEmpty = (>0) . Vector.length editsTo :: Arbitrary a => Vector a -> Gen (Edit a) editsTo v = do i <- choose (0, Vector.length v -1) c <- elements [const (Insert i), \o _ -> Delete i o, Replace i] x <- arbitrary return $ c (v Vector.! i) x patchesFrom' :: (Eq a, Arbitrary a) => Vector a -> Gen (Patch a) patchesFrom' v | Vector.length v > 0 = fromList <$> listOf (editsTo v) patchesFrom' _ | otherwise = fromList <$> listOf (Insert 0 <$> arbitrary) patchesFrom :: Vector Int -> Gen (Patch Int) patchesFrom = patchesFrom' divergingPatchesFrom :: Vector Int -> Gen (Patch Int, Patch Int) divergingPatchesFrom v = (,) <$> patchesFrom v <*> patchesFrom v historyFrom d 0 = return [] historyFrom d m = do p <- patchesFrom d r <- historyFrom (apply p d) $ m - 1 return (p:r) :}`:{`

`>>>`

`:set -XScopedTypeVariables`

`>>>`

`instance Arbitrary a => Arbitrary (Vector a) where arbitrary = Vector.fromList <$> listOf arbitrary`

Blah

forAll (patchesFrom d) $ \ x -> read (show x) == x

A *patch* is a collection of edits performed to a *document*, in this case a `Vector`

. They are
implemented as a list
of `Edit`

, and can be converted to and from raw lists of edits using `toList`

and `fromList`

respectively.

Patches form a group (a `Monoid`

with inverses), where the inverse element can be computed with
`inverse`

and the group operation is *composition* of patches. Applying `p1 <> p2`

is the
same as applying `p1`

*then* `p2`

(see `apply`

). This composition operator may produce structurally
different patches depending on associativity, however the patches are guaranteed to be *equivalent*
in the sense that the resultant document will be the same when they are applied.

forAll (patchesFrom d) $ \a -> a <> mempty == a

forAll (patchesFrom d) $ \a -> mempty <> a == a

forAll (historyFrom d 3) $ \[a, b, c] -> apply (a <> (b <> c)) d == apply ((a <> b) <> c) d

The indices of the `Edit`

s are all based on the *original document*, so:

`>>>`

"a1b23"`Vector.toList $ apply (fromList [Insert 0 'a', Insert 1 'b']) (Vector.fromList "123")`

`>>>`

"ab123"`Vector.toList $ apply (fromList [Insert 0 'a', Insert 0 'b']) (Vector.fromList "123")`

Note that the first `Insert`

didn't introduce an offset for the second.

An `Edit`

is a single alteration of the vector, either inserting, removing, or replacing an element.

Useful optics are provided below, for the `index`

, the `old`

element, and the `new`

element.

inverse :: Patch a -> Patch a Source

Compute the inverse of a patch, such that:

forAll (patchesFrom d) $ \p -> p <> inverse p == mempty

forAll (patchesFrom d) $ \p -> inverse p <> p == mempty

forAll (patchesFrom d) $ \p -> inverse (inverse p) == p

forAll (historyFrom d 2) $ \[p, q] -> inverse (p <> q) == inverse q <> inverse p

forAll (patchesFrom d) $ \p -> inverse mempty == mempty

index :: Lens' (Edit a) Int Source

A lens for the index where an edit is to be performed.

nonEmpty d ==> forAll (editsTo d) $ \e -> set index v e ^. index == v

nonEmpty d ==> forAll (editsTo d) $ \e -> set index (e ^. index) e == e

nonEmpty d ==> forAll (editsTo d) $ \e -> set index v' (set index v e) == set index v' e

old :: Traversal' (Edit a) a Source

A traversal for the old element to be replaced/deleted. Empty in the case of an `Insert`

.

new :: Traversal' (Edit a) a Source

A traversal for the new value to be inserted or replacing the old value. Empty in the case of a `Delete`

.

unsafeFromList :: [Edit a] -> Patch a Source

Directly convert a list of edits to a patch, without sorting edits by index, and resolving contradictory edits. Use this function if you know that the input list is already a wellformed patch.

fromList :: Eq a => [Edit a] -> Patch a Source

Convert a list of edits to a patch, making sure to eliminate conflicting edits and sorting by index.

apply :: Patch a -> Vector a -> Vector a Source

Apply a patch to a document.

Technically, `apply`

is a *monoid morphism* to the monoid of endomorphisms `Vector a -> Vector a`

,
and that's how we can derive the following two laws:

forAll (historyFrom d 2) $ \[a, b] -> apply b (apply a d) == apply (a <> b) d

apply mempty d == d

transformWith :: Eq a => (a -> a -> a) -> Patch a -> Patch a -> (Patch a, Patch a) Source

Given two diverging patches `p`

and `q`

, `transform m p q`

returns
a pair of updated patches `(p',q')`

such that `q <> p'`

and
`p <> q'`

are equivalent patches that incorporate the changes
of *both* `p`

and `q`

, up to merge conflicts, which are handled by
the provided function `m`

.

This is the standard `transform`

function of Operational Transformation
patch resolution techniques.

forAll (divergingPatchesFrom d) $ \(p,q) -> let (p', q') = transformWith ours p q in apply (p <> q') d == apply (q <> p') d

This function is commutative iff `m`

is commutative.

forAll (divergingPatchesFrom d) $ \(p,q) -> let (p', q') = transformWith (*) p q; (q'', p'') = transformWith (*) q p in p' == p'' && q' == q''

forAll (patchesFrom d) $ \ p -> transformWith (*) mempty p == (mempty, p)

forAll (patchesFrom d) $ \ p -> transformWith (*) p mempty == (p, mempty)

Some example conflict strategies are provided below.

transform :: (Eq a, Monoid a) => Patch a -> Patch a -> (Patch a, Patch a) Source

A convenience version of `transformWith`

which resolves conflicts using `mappend`

.

diff :: Eq a => Vector a -> Vector a -> Patch a Source

Compute the difference between two documents, using the Wagner-Fischer algorithm. O(mn) time and space.

apply (diff d e) d == e

apply (diff d e) d == apply (inverse (diff e d)) d

apply (diff a b <> diff b c) a == apply (diff a c) a

data HunkStatus Source

The four different ways a hunk may have been manipulated.

type Hunks a = [(Vector a, HunkStatus)] Source

The type for a series of hunks; a patch as it may be displayed to a user.