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       Parametric diffing
17
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       module type Defs = sig end
65
66
67       The core types of a diffing implementation
68
69
70       type change_kind =
71        | Deletion
72        | Insertion
73        | Modification
74        | Preservation
75
76
77       The  kind of changes which is used to share printing and styling across
78       implementation
79
80
81
82       val prefix : Format.formatter -> int * change_kind -> unit
83
84
85
86
87       val style : change_kind -> Misc.Color.style list
88
89
90
91       type ('left, 'right, 'eq, 'diff) change =
92        | Delete of 'left
93        | Insert of 'right
94        | Keep of 'left * 'right * 'eq
95        | Change of 'left * 'right * 'diff
96
97
98
99
100
101       val classify : ('a, 'b, 'c, 'd) change -> change_kind
102
103
104
105       module Define : functor (D : Defs) -> sig end
106
107
108
109       Define(Defs) creates the diffing types from the types defined  in  Defs
110       and  the  functors  that need to be instantatied with the diffing algo‐
111       rithm parameters
112
113
114
115
116
117OCamldoc                          2022-07-22                        Diffing(3)