A diff represents a transformation from one file to another.

Example diff between "abcdefgh" and "appcfgzzh":

source ab cdefg  h
     -  b  de
     +  pp     zz
target appc  fgzzh

It consists of three replacements:

1. replace "b" with "pp" at location 1, mkReplace 1 1 2;
2. replace "de" with "" at location 3, mkReplace 3 2 0;
3. replace "" with "zz" at location 7, mkReplace 7 0 2.

>>> :{
  let d :: Diff N
      d = addDiff (Replace 1 (offset 1) (offset 2))  -- at location 1, replace "b" (length 1) with "pp" (length 2)
        $ addDiff (Replace 3 (offset 2) (offset 0))  -- at location 3, replace "de" with ""
        $ addDiff (Replace 7 (offset 0) (offset 2))  -- at location 7, replace "" with "zz"
        $ emptyDiff
  -- N.B.: replacements should be inserted right to left.
:}

ADiff is an abstract representation to be instantiated with a concrete representation of atomic replacements.

Internal details

The empty diff.

Add a replacement to a diff. The replacement is performed after the diff.

Properties

not (isZeroLength x) ==> mapDiff (addDiff r d) x == (shiftBlock r <=< mapDiff (d :: Diff N)) x

not (isZeroLength x) ==> comapDiff (addDiff r d) x == (comapDiff d <=< coshiftBlock (r :: Replace N)) x

Translate a span in the source of a diff to a span in its target. Nothing if the span overlaps with a replacement.

For exaple, given the following ADiff (or Replace) from "aAacCc" to "aAabbbcCc":

source aAa   cCc
     - 
     +    bbb
target aAabbbcCc

>>> r0 = Replace 3 (offset 0) (offset 3) :: Replace N
>>> d0 = addDiff r0 emptyDiff

The span of "A" remains unchanged.

>>> mapDiff d0 (1 :.. offset 1)
Just (1 :.. offset 1)
>>> shiftBlock r0 (1 :.. offset 1)
Just (1 :.. offset 1)
>>> comapDiff d0 (1 :.. offset 1)
Just (1 :.. offset 1)
>>> coshiftBlock r0 (1 :.. offset 1)
Just (1 :.. offset 1)

The span of "C" is shifted by 3 characters.

>>> mapDiff d0 (4 :.. offset 1)
Just (7 :.. offset 1)
>>> shiftBlock r0 (4 :.. offset 1)
Just (7 :.. offset 1)
>>> comapDiff d0 (7 :.. offset 1)
Just (4 :.. offset 1)
>>> coshiftBlock r0 (7 :.. offset 1)
Just (4 :.. offset 1)

The span of "ac" overlaps with the replacement, so the mapping is undefined.

>>> mapDiff d0 (2 :.. offset 2)
Nothing
>>> shiftBlock r0 (2 :.. offset 2)
Nothing
>>> comapDiff d0 (2 :.. offset 5)
Nothing
>>> coshiftBlock r0 (2 :.. offset 5)
Nothing

Properties

\(FSN d s) -> not (isZeroLength s) ==> partialSemiInverse (mapDiff d) (comapDiff d) s

\(FSN d s) -> not (isZeroLength s) ==> partialSemiInverse (comapDiff d) (mapDiff d) s

where partialSemiInverse f g x is the property

if   f x == Just y   -- for some y
then g y == Just x

Translate a span in the target of a diff to a span in its source. Nothing if the span overlaps with a replacement.

See also mapDiff.

listToDiff = foldr addDiff emptyDiff