.TH "Diffing" 3o 2023-02-12 OCamldoc "OCaml library"
.SH NAME
Diffing \-  Parametric diffing 
.SH Module
Module   Diffing
.SH Documentation
.sp
Module
.BI "Diffing"
 : 
.B sig end

.sp
.SS Parametric diffing
.sp
This module implements diffing over lists of arbitrary content\&.
It is parameterized by
.sp
\-The content of the two lists
.sp
\-The equality witness when an element is kept
.sp
\-The diffing witness when an element is changed

Diffing is extended to maintain state depending on the
computed changes while walking through the two lists\&.
.sp
The underlying algorithm is a modified Wagner\-Fischer algorithm
(see <https://en\&.wikipedia\&.org/wiki/Wagner%E2%80%93Fischer_algorithm>)\&.
.sp
We provide the following guarantee:
Given two lists 
.ft B
l
.ft R
and 
.ft B
r
.ft R
, if different patches result in different
states, we say that the state diverges\&.
.sp
\-We always return the optimal patch on prefixes of 
.ft B
l
.ft R
and 
.ft B
r
.ft R
on which state does not diverge\&.
.sp
\-Otherwise, we return a correct but non\-optimal patch where subpatches
with no divergent states are optimal for the given initial state\&.

More precisely, the optimality of Wagner\-Fischer depends on the property
that the edit\-distance between a k\-prefix of the left input and a l\-prefix
of the right input d(k,l) satisfies
.sp
d(k,l) = min (
del_cost + d(k\-1,l),
insert_cost + d(k,l\-1),
change_cost + d(k\-1,l\-1)
)
.sp
Under this hypothesis, it is optimal to choose greedily the state of the
minimal patch transforming the left k\-prefix into the right l\-prefix as a
representative of the states of all possible patches transforming the left
k\-prefix into the right l\-prefix\&.
.sp
If this property is not satisfied, we can still choose greedily a
representative state\&. However, the computed patch is no more guaranteed to
be globally optimal\&.
Nevertheless, it is still a correct patch, which is even optimal among all
explored patches\&.

.sp

.sp
.sp
.I type 
.B ('left, 'right, 'eq, 'diff)
.I change 
=
 | Delete
.B of 
.B 'left
 | Insert
.B of 
.B 'right
 | Keep
.B of 
.B 'left * 'right * 'eq
 | Change
.B of 
.B 'left * 'right * 'diff
 
.sp
The type of potential changes on a list\&.

.sp

.I val map 
: 
.B ('l1 -> 'l2) ->
.B   ('r1 -> 'r2) ->
.B   ('l1, 'r1, 'eq, 'diff) change ->
.B   ('l2, 'r2, 'eq, 'diff) change
.sp

.sp
.I type 
.B ('l, 'r, 'eq, 'diff)
.I patch 
= 
.B ('l, 'r, 'eq, 'diff) change list

.sp
A patch is an ordered list of changes\&.

.sp

.I val diff 
: 
.B weight:(('l, 'r, 'eq, 'diff) change -> int) ->
.B   test:('state -> 'l -> 'r -> ('eq, 'diff) result) ->
.B   update:(('l, 'r, 'eq, 'diff) change -> 'state -> 'state) ->
.B   'state -> 'l array -> 'r array -> ('l, 'r, 'eq, 'diff) patch
.sp

.ft B
diff ~weight ~test ~update state l r
.ft R
computes
the diff between 
.ft B
l
.ft R
and 
.ft B
r
.ft R
, using the initial state 
.ft B
state
.ft R
\&.
.sp
\-
.ft B
test st xl xr
.ft R
tests if the elements 
.ft B
xl
.ft R
and 
.ft B
xr
.ft R
are
compatible (
.ft B
Ok
.ft R
) or not (
.ft B
Error
.ft R
)\&.
.sp
\-
.ft B
weight ch
.ft R
returns the weight of the change 
.ft B
ch
.ft R
\&.
Used to find the smallest patch\&.
.sp
\-
.ft B
update ch st
.ft R
returns the new state after applying a change\&.


.sp

.PP
.SS Variadic diffing
.sp
Variadic diffing allows to expand the lists being diffed during diffing\&.
.PP
.I type 
.B ('l, 'r, 'e, 'd, 'state)
.I update 
=
 | Without_extensions
.B of 
.B (('l, 'r, 'e, 'd) change -> 'state -> 'state)
 | With_left_extensions
.B of 
.B (('l, 'r, 'e, 'd) change -> 'state -> 'state * 'l array)
 | With_right_extensions
.B of 
.B (('l, 'r, 'e, 'd) change -> 'state -> 'state * 'r array)
 
.sp

.sp

.I val variadic_diff 
: 
.B weight:(('l, 'r, 'eq, 'diff) change -> int) ->
.B   test:('state -> 'l -> 'r -> ('eq, 'diff) result) ->
.B   update:('l, 'r, 'eq, 'diff, 'state) update ->
.B   'state -> 'l array -> 'r array -> ('l, 'r, 'eq, 'diff) patch
.sp

.ft B
variadic_diff ~weight ~test ~update state l r
.ft R
behaves as 
.ft B
diff
.ft R
with the following difference:
.sp
\-
.ft B
update
.ft R
must now be an 
.ft B
Diffing\&.update
.ft R
which indicates in which direction
the expansion takes place\&.


.sp