1Diffing(3)                       OCaml library                      Diffing(3)
2
3
4

NAME

6       Diffing -  Parametric diffing
7

Module

9       Module   Diffing
10

Documentation

12       Module Diffing
13        : sig end
14
15
16
17   Parametric diffing
18       This  module implements diffing over lists of arbitrary content.  It is
19       parameterized by
20
21       -The content of the two lists
22
23       -The equality witness when an element is kept
24
25       -The diffing witness when an element is changed
26
27       Diffing is extended to maintain state depending on the computed changes
28       while walking through the two lists.
29
30       The  underlying  algorithm  is a modified Wagner-Fischer algorithm (see
31       <https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm>).
32
33       We provide the following guarantee: Given two lists l and r ,  if  dif‐
34       ferent  patches  result  in different states, we say that the state di‐
35       verges.
36
37       -We always return the optimal patch on prefixes of l  and  r  on  which
38       state does not diverge.
39
40       -Otherwise,  we return a correct but non-optimal patch where subpatches
41       with no divergent states are optimal for the given initial state.
42
43       More precisely, the optimality of Wagner-Fischer depends on  the  prop‐
44       erty  that the edit-distance between a k-prefix of the left input and a
45       l-prefix of the right input d(k,l) satisfies
46
47       d(k,l) = min ( del_cost + d(k-1,l), insert_cost + d(k,l-1), change_cost
48       + d(k-1,l-1) )
49
50       Under  this  hypothesis,  it is optimal to choose greedily the state of
51       the minimal patch transforming the left k-prefix into the right  l-pre‐
52       fix  as  a  representative of the states of all possible patches trans‐
53       forming the left k-prefix into the right l-prefix.
54
55       If this property is not satisfied, we can still choose greedily a  rep‐
56       resentative state. However, the computed patch is no more guaranteed to
57       be globally optimal.  Nevertheless, it is still a correct patch,  which
58       is even optimal among all explored patches.
59
60
61
62
63
64       type ('left, 'right, 'eq, 'diff) change =
65        | Delete of 'left
66        | Insert of 'right
67        | Keep of 'left * 'right * 'eq
68        | Change of 'left * 'right * 'diff
69
70
71       The type of potential changes on a list.
72
73
74
75       val map : ('l1 -> 'l2) -> ('r1 -> 'r2) -> ('l1, 'r1, 'eq, 'diff) change
76       -> ('l2, 'r2, 'eq, 'diff) change
77
78
79
80       type ('l, 'r, 'eq, 'diff) patch = ('l, 'r, 'eq, 'diff) change list
81
82
83       A patch is an ordered list of changes.
84
85
86
87       val diff : weight:(('l, 'r, 'eq, 'diff) change -> int) ->  test:('state
88       ->  'l  ->  'r  -> ('eq, 'diff) result) -> update:(('l, 'r, 'eq, 'diff)
89       change -> 'state -> 'state) -> 'state -> 'l array -> 'r array  ->  ('l,
90       'r, 'eq, 'diff) patch
91
92
93       diff  ~weight ~test ~update state l r computes the diff between l and r
94       , using the initial state state .
95
96       - test st xl xr tests if the elements xl and xr are compatible (  Ok  )
97       or not ( Error ).
98
99       -  weight  ch  returns  the weight of the change ch .  Used to find the
100       smallest patch.
101
102       - update ch st returns the new state after applying a change.
103
104
105
106
107
108   Variadic diffing
109       Variadic diffing allows to expand the lists being diffed  during  diff‐
110       ing.
111
112       type ('l, 'r, 'e, 'd, 'state) update =
113        | Without_extensions of (('l, 'r, 'e, 'd) change -> 'state -> 'state)
114        | With_left_extensions of (('l, 'r, 'e, 'd) change -> 'state -> 'state
115       * 'l array)
116        | With_right_extensions of (('l, 'r,  'e,  'd)  change  ->  'state  ->
117       'state * 'r array)
118
119
120
121
122
123       val  variadic_diff  :  weight:(('l,  'r,  'eq, 'diff) change -> int) ->
124       test:('state -> 'l -> 'r -> ('eq, 'diff)  result)  ->  update:('l,  'r,
125       'eq,  'diff,  'state)  update -> 'state -> 'l array -> 'r array -> ('l,
126       'r, 'eq, 'diff) patch
127
128
129       variadic_diff ~weight ~test ~update state l r behaves as diff with  the
130       following difference:
131
132       -  update must now be an Diffing.update which indicates in which direc‐
133       tion the expansion takes place.
134
135
136
137
138
139
140OCamldoc                          2022-02-04                        Diffing(3)