Safe Haskell | Safe-Inferred |
---|---|

Language | Haskell2010 |

Mapping intervals across diffs

# Types

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:

- replace "b" with "pp" at location 1,
`mkReplace 1 1 2`

; - replace "de" with "" at location 3,
`mkReplace 3 2 0`

; - 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

Internally, a diff is a sequence of *disjoint* and *nonempty* replacements,
*ordered* by their source locations.
The monoid annotation in the fingertree gives the endpoints of the replacements.

# Operations

addDiff :: forall r. Shift r => r -> ADiff r -> ADiff r Source #

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

mapDiff :: Shift r => ADiff r -> Block r -> Maybe (Block r) Source #

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.

`>>>`

Just (1 :.. offset 1)`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)`

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

`>>>`

Just (7 :.. offset 1)`mapDiff d0 (4 :.. offset 1)`

`>>>`

Just (7 :.. offset 1)`shiftBlock r0 (4 :.. offset 1)`

`>>>`

Just (4 :.. offset 1)`comapDiff d0 (7 :.. offset 1)`

`>>>`

Just (4 :.. offset 1)`coshiftBlock r0 (7 :.. offset 1)`

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

`>>>`

Nothing`mapDiff d0 (2 :.. offset 2)`

`>>>`

Nothing`shiftBlock r0 (2 :.. offset 2)`

`>>>`

Nothing`comapDiff d0 (2 :.. offset 5)`

`>>>`

Nothing`coshiftBlock r0 (2 :.. offset 5)`

### 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

comapDiff :: Shift r => ADiff r -> Block r -> Maybe (Block r) Source #

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 :: Shift r => [r] -> ADiff r Source #

`listToDiff`

= foldr`addDiff`

`emptyDiff`