Debian Codegraph @

regress/diff/diff.html

raw
1 <!DOCTYPE html>
2 <html>
3 <head>
4 <meta charset="utf-8" />
5 <meta name="viewport" content="width=device-width,initial-scale=1" />
6 <meta name="creator" content="BSD.lv" />
7 <meta name="author" content="Kristaps Dzonsons" />
8 <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/styles/default.min.css" />
9 <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Alegreya+Sans:400,400italic,500,700" />
10 <link rel="stylesheet" href="diff.css" />
11 <script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/highlight.min.js"></script>
12 <script src="diff.js"></script>
13 <title>Lowdown Diffing Engine </title>
14 </head>
15 <body>
16 <h1 id="lowdown-diffing-engine">Lowdown Diffing Engine</h1>
17 <p>In this paper, I briefly describe the &#8220;diff&#8221; engine used in
18 <a href="https://kristaps.bsd.lv/lowdown/lowdown.1.html">lowdown-diff(1)</a> tool
19 in <a href="https://kristaps.bsd.lv/lowdown/index.html">lowdown</a>. The work is
20 motivated by the need to provide formatted output describing the
21 difference between two documents&#8212;specifically, formatted PDF via the
22 <strong>-Tms</strong> output, although <strong>-Thtml</strong> and the other output modes are of
23 course supported.</p>
24 <ins>
25 <p>This documents an early work in progress&#8212;both source code and
26 documentation. The source is documented fully in
27 <a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a>.
28 This paper itself is available as
29 <a href="https://github.com/kristapsdz/lowdown/blob/master/diff.md">diff.md</a>, or downloadable as
30 <a href="https://kristaps.bsd.lv/lowdown/diff.pdf">diff.pdf</a>.
31 Please direct comments to me by e-mail or just use the <a href="https://github.com/kristapsdz/lowdown">GitHub
32 interface</a>.</p>
33 </ins>
34 <p>For a quick example of this functionality, see
35 <a href="https://kristaps.bsd.lv/lowdown/diff.diff.html">diff.diff.html</a><ins>
36 (or </ins><ins><a href="https://kristaps.bsd.lv/lowdown/diff.diff.pdf">diff.diff.pdf</a></ins><ins>), which
37 shows the difference between this document and a [fabricated] earlier
38 version.</ins><del>.</del></p>
39 <h2 id="introduction">Introduction</h2>
40 <p>Let two source files, <del><em>foo.md</em></del><ins><em>old.md</em></ins> and <del><em>bar.md</em></del><ins><em>new.md</em></ins>, refer to the old and new versions of a file respectively.<ins>The</ins> <ins>goal</ins> <ins>is</ins> <ins>to</ins> <ins>establish</ins> <ins>the</ins> <ins>changes</ins> <ins>between</ins> <ins>these</ins> <ins>snippets</ins> <ins>in</ins> <ins>formatted</ins> <ins>output.</ins> <ins>Let</ins>&#8217;s <ins>begin</ins> <ins>with</ins> <ins>the</ins> <ins>old</ins> <ins>version,</ins> <ins><em>old.md</em></ins><ins>.</ins></p>
41 <pre><code class="language-markdown">*Lorem* ipsum dolor sit amet, consectetur adipiscing elit, sed do
42 eiusmod tempor incididunt ut [labore](index.html) et dolore magna
43 aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco
44 laboris nisi ut _aliquip_ ex ea commodo consequat. Duis aute irure dolor
45 in reprehenderit...
46 </code></pre>
47 <p>In the new version, <em>new.md</em>, I add some more links and styles.</p>
48 <pre><code class="language-markdown">*Lorem* ipsum dolor sit amet, consectetur adipiscing elit, sed do
49 eiusmod tempor incididunt ut [labore](index.html) et dolore [magna
50 aliqua](index.html). Ut enim ad minim veniam, quis nostrud exercitation
51 ullamco laboris nisi ut _aliquip_ ex ea commodo consequat. Duis *aute
52 irure* dolor in reprehenderit...
53 </code></pre>
54 <p>The most simple way of viewing changes is with the venerable
55 <a href="https://man.openbsd.org/diff.1">diff(1)</a> utility. However, this will
56 only reflect changes in the input document&#8212;not the formatted output.</p>
57 <pre><code class="language-diff">--- old.md Tue Oct 17 11:25:01 2017
58 +++ new.md Tue Oct 17 11:25:01 2017
59 @@ -1,5 +1,5 @@
60 *Lorem* ipsum dolor sit amet, consectetur adipiscing elit, sed do
61 -eiusmod tempor incididunt ut [labore](index.html) et dolore magna
62 -aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco
63 -laboris nisi ut _aliquip_ ex ea commodo consequat. Duis aute irure dolor
64 -in reprehenderit...
65 +eiusmod tempor incididunt ut [labore](index.html) et dolore [magna
66 +aliqua](index.html). Ut enim ad minim veniam, quis nostrud exercitation
67 +ullamco laboris nisi ut _aliquip_ ex ea commodo consequat. Duis *aute
68 +irure* dolor in reprehenderit...
69 </code></pre>
70 <p>Not very helpful for any but source-level change investigation. And
71 given that Markdown doesn&#8217;t encourage the usual &#8220;new sentence, new line&#8221;
72 of some languages (like <a href="https://man.openbsd.org/mdoc.7">mdoc(7)</a>), even
73 this level of change analysis is difficult: a single change might affect
74 multiple re-wrapped lines.</p>
75 <p>A similar possibility is to use
76 <a href="https://www.gnu.org/software/wdiff/">wdiff(1)</a>, which produces a set of
77 word-by-word differences.</p>
78 <pre><code class="language-markdown">*Lorem* ipsum dolor sit amet, consectetur adipiscing elit, sed do
79 eiusmod tempor incididunt ut [labore](index.html) et dolore [-magna
80 aliqua.-] {+[magna aliqua](index.html).+} Ut enim ad minim veniam, quis
81 nostrud exercitation ullamco laboris nisi ut _aliquip_ ex ea commodo
82 consequat. Duis [-aute irure-] {+*aute irure*+} dolor in
83 reprehenderit...
84 </code></pre>
85 <p>One could then extend the Markdown language to accept the insertion and
86 deletion operations and let the output flow from there.
87 (In fact, that was my first approach to solving the problem.)</p>
88 <p>Unfortunately, doing so entails extending a language already prone to extension and non-standardisation. <del>Here</del> <del>is</del> <del>some</del> <del>added</del> <del>text.</del> More unfortunately, a word-based diff will not be sensitive to the <del>shmarkdown</del> <ins>Markdown</ins> language itself, and in establishing context-free <del>foo</del> <del>bar</del> <del>baz</del> <ins>sequences</ins> of similar words, will overrun block and span element boundaries.</p>
89 <p>On the other end of the spectrum are difference tools specific to the
90 output media.</p>
91 <ins>
92 <p>One can directly analyse PDF output using (for example) the
93 <a href="https://poppler.freedesktop.org/">poppler</a> tools, which would extract
94 text, then examine the output with a linear difference engine such as
95 <a href="https://code.google.com/archive/p/google-diff-match-patch/">Diff, Match,
96 Patch</a>.
97 This is not an optimal solution because, as with the word diff above, it
98 only compares words and cannot distinguish semantic artefacts such as in
99 italics, links, code blocks, and so on.</p>
100 </ins>
101 <p>There are even more <a href="https://www.w3.org/wiki/HtmlDiff">HTML diff</a> tools
102 available, so it&#8217;s tempting to use one of these tools to produce an HTML
103 file consisting of differences, then further use a converter like
104 <a href="https://wkhtmltopdf.org/">wkhtmltopdf</a> to generate PDFs.</p>
105 <p>Since the HTML difference engines often respect the structure of HTML,
106 this is much more optimal in handling semantic difference. However,
107 re-structuring the difference does not easily produce a document of the
108 same style or readability as the PDFs themselves.</p>
109 <p>The most elegant (and reliable) solution is to attack the problem from
110 the language-level itself. Since the
111 <a href="https://kristaps.bsd.lv/lowdown/lowdown.3.html">lowdown(3)</a>
112 library is able to produce a full parse tree for analysis, it stands to
113 reason, given the wealth of literature on tree differences (instead of
114 the usual linear difference, as in the case of
115 <a href="https://man.openbsd.org/diff.1">diff(1)</a> and friends), one can work
116 within the language to produce differences.<del><sup id="fnref1"><a href="#fn1" rel="footnote">1</a></sup></del></p>
117 <h2 id="algorithm">Algorithm</h2>
118 <p>The algorithm is in effect an ordered tree diff. I began with
119 well-studied algorithms for a well-studied problem: XML tree
120 differences. (The HTML difference tools described above inherit from
121 those algorithms.) For an overview of algorithms, see Change Detection
122 in XML Trees: a Survey<sup id="fnref2"><a href="#fn2" rel="footnote">2</a></sup>. I base the
123 <a href="https://kristaps.bsd.lv/lowdown/lowdown.1.html">lowdown-diff(1)</a> algorithm off
124 of Detecting Changes in XML Documents<sup id="fnref3"><a href="#fn3" rel="footnote">3</a></sup>.</p>
125 <p>The reason for this choice instead of another is primarily the ease in
126 implementation. Moreover, since the programmatic output of the
127 algorithm is a generic AST, it&#8217;s feasible to re-implement the algorithm
128 in different ways, or augment it at a later date.</p>
129 <p>The BULD algorithm described in this paper is straightforward. It
130 begins with a short sanitisation pass.</p>
131 <ol>
132 <li><p>Annotate each node in the parse tree with a hash of the subtree
133 rooted at the node, inclusive.
134 (<a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a>,
135 <code>annotate_sigs()</code>)</p></li>
136 <li><p>Annotate each node with a weight corresponding to the subtree rooted
137 at the node.
138 (<a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a>,
139 <code>annotate_sigs()</code>)</p></li>
140 <li><p>Enqueue the new document&#8217;s root node in a priority queue ordered by
141 weight. Then, while the priority queue is non-empty:
142 (<a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a>,
143 <code>lowdown_diff()</code>)</p>
144 <ol>
145 <li>Pop the first node of the priority queue.</li>
146 <li>Look for candidates in the old document whose hash matches the
147 popped node&#8217;s hash.
148 (<a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a>,
149 <code>candidate()</code>)</li>
150 <li>Choose an optimal candidate and mark it as matched.
151 (<a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a>,
152 <code>optimality()</code>)</li>
153 <li>If the no candidates were found, enqueue the node&#8217;s children into
154 the priority queue.</li>
155 <li>A a candidate was selected, mark all of its subtree nodes as
156 matching the corresponding nodes in the old tree (&#8220;propagate
157 down&#8221;), then mark ancestor nodes similarly (&#8220;propagate up&#8221;).
158 (<a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a>,
159 <code>match_up()</code>, <code>match_down()</code>)</li>
160 </ol></li>
161 <li><p>Run an optimisation phase over the new document&#8217;s root node.
162 (<ins><a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a></ins><del><a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a></del>,
163 <del><code>node_optimise()</code></del><ins><code>node_optimise_bottomup()</code></ins><ins> and </ins><ins><code>node_optimise_topdown()</code></ins>)</p></li>
164 <li><p>Step through both trees and create a new tree with nodes cloned from
165 both and marked as inserted or deleted.
166 (<a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a>,
167 <code>node_merge()</code>)</p></li>
168 </ol>
169 <p>My implementation changes or extends the BULD algorithm in several small
170 ways, described in the per-step documentation below.</p>
171 <h3 id="sanitise">Sanitise</h3>
172 <p>Before the BULD algorithm is run, the input tree is sanitised. This
173 process merges all adjacent text nodes into a single text node. By
174 doing so, possible differences are pushed into large blocks of
175 contiguous text&#8212;which in this case are managed by the word-difference
176 algorithm described later in this paper.</p>
177 <h3 id="annotation">Annotation</h3>
178 <p>Each node in the tree is annotated with a hash and a weight. The hash,
179 MD5, is computed in all data concerning a node. For example, normal
180 text nodes (<code>LOWDOWN_NORMAL_TEXT</code>) have the hash produced from the
181 enclosed text. Autolinks (<code>LOWDOWN_LINK_AUTO</code>) use the link text, link,
182 and type.</p>
183 <p>There are some nodes whose data is not hashed. For example, list
184 numbers: since these may change when nodes are moved, the numbers are
185 not part of the hash. In general, all volatile information that may be
186 inferred from the document structure (column number, list item number,
187 footnote number, etc.) is disregarded.</p>
188 <p>Non-leaf nodes compute their hashes from the node type and the hashes of
189 all of their children. Thus, this step is a bottom-up search.</p>
190 <p>Node weight is computed exactly as noted in the paper.</p>
191 <h3 id="optimal-candidacy">Optimal candidacy</h3>
192 <p>A node&#8217;s candidate in the old tree is one whose hash matches. In most
193 documents, there are many candidates for certain types of nodes.
194 (Usually text nodes.)</p>
195 <p>Candidate optimality is computed by looking at the number of parent
196 nodes that match on both sides. The number of parents to consider is
197 noted in the next sub-section. The distance climbed is bounded by the
198 weight of the sub-tree as defined in the paper.</p>
199 <p>In the event of similar optimality, the node &#8220;closest&#8221; to the current
200 node is chosen. Proximity is defined by the node identifier, which is
201 its prefix order in the parse tree.</p>
202 <h3 id="propagate-up">&#8220;Propagate up&#8221;</h3>
203 <p>When propagating a match upward, the distance upward is bound depending
204 on the matched sub-tree as defined in the paper. This makes it so that
205 &#8220;small&#8221; similarities (such as text) don&#8217;t erroneously match two larger
206 sub-trees that are otherwise different. Upward matches occur while the
207 nodes&#8217; labels are the same, including attributes (e.g., link text).</p>
208 <p>I did modify the algorithm to propagate upward &#8220;for free&#8221; through
209 similar singleton nodes, even if it means going beyond the maximum
210 number allowed by the sub-tree weight.</p>
211 <h3 id="optimisation">Optimisation</h3>
212 <p>The <a href="https://kristaps.bsd.lv/lowdown/lowdown.1.html">lowdown-diff(1)</a>
213 algorithm has two optimisations, both lightly derived from the paper:
214 top-down and bottom-up propagation.</p>
215 <h4 id="top-down">Top-down</h4>
216 <p>The top-down optimisation, which is performed first, takes matched nodes and matches un-matched, non-terminal children by label.<ins>The</ins> <ins>children</ins> <ins>examined</ins> <ins>must</ins> <ins>be</ins> <ins>siblings</ins> <ins>of</ins> <ins>adjacent</ins> <ins>matching</ins> <ins>nodes.</ins></p>
217 <p>This is useful when, say, a document consists of several paragraphs
218 where the text has changed within paragraphs. It won&#8217;t be able to match
219 the text content, but it will match the paragraphs, which will push the
220 difference downward in the tree.</p>
221 <h4 id="bottom-up">Bottom-up</h4>
222 <p>In the bottom-up propagation, the weight of any given sub-tree is used
223 to compute how high a match will propagate. I extend the paper&#8217;s
224 version optimisation by looking at the cumulative weight of matching
225 children.</p>
226 <p>This works well for Markdown documents, which are generally quite
227 shallow and text-heavy.</p>
228 <p>For each unmatched non-terminal node with at least one
229 matched child, the weights of all matched children with the same parents
230 (where the parent node is equal in label and attributes to the examined
231 node) are computed. If any given parent of the matched children has
232 greater than 50% of the possible weight, it is matched.</p>
233 <h3 id="merging">Merging</h3>
234 <p>The merging phase, which is not described in the paper, is very
235 straightforward. It uses a recursive merge algorithm starting at the
236 root node of the new tree and the root node of the old tree.</p>
237 <ol>
238 <li>The invariant is that the current node is matched by the corresponding
239 node in the old tree.</li>
240 <li>First, step through child nodes in the old tree. Mark as deleted all
241 nodes not being matched to the new tree.</li>
242 <li>Next, step through child nodes in the new tree. Mark as inserted all
243 nodes not having a match in the old tree.</li>
244 <li>Now, starting with the first node in the new tree having a match in
245 the old tree, search for that match in the list of old tree children.</li>
246 <li>If found, mark as deleted all previous old tree nodes up until the
247 match. Then re-run the merge algorithm starting at the matching
248 child nodes.</li>
249 <li>If not found, mark the new node as inserted and return to (2).</li>
250 <li>Continue (after the recursive step) by moving after both matching
251 nodes and returning to (2).</li>
252 </ol>
253 <p>If adjacent nodes are un-matched normal text, the normal text nodes are
254 compared word-by-word to compute a shortest-edit script. This is
255 enabled by <a href="https://github.com/kristapsdz/libdiff">libdiff</a>, which
256 implements an algorithm for computing the longest common
257 subsequence<sup id="fnref4"><a href="#fn4" rel="footnote">4</a></sup>. See <sup id="fnref5"><a href="#fn5" rel="footnote">5</a></sup> for background information.</p>
258 <ins>
259 <h3 id="tables">Tables</h3>
260 </ins><ins>
261 <p>Tables are currently in the &#8220;hacks&#8221; state in that they&#8217;re considered as
262 opaque bodies. Tables that have changed in any way are simply deleted
263 and re-added: there&#8217;s no attempt to discern actual differences.</p>
264 </ins><ins>
265 <p>There are ways to reduce this opacity, such as being able to detect and
266 account for added or removed rows. However, ultimately there is some
267 opacity in that changed table headers do not have a representable form
268 in the output.</p>
269 </ins><ins>
270 <h3 id="metadata">Metadata</h3>
271 </ins><ins>
272 <p>Like tables, metadata key-value pairs are opaque bodies. Metadata has a
273 complex relationship with Markdown documents, which leaves how to handle
274 the &#8220;difference&#8221; uncertain.</p>
275 </ins><ins>
276 <p>The difference engine, after computing differences like any other opaque
277 nodes, simply passes the difference to front-ends, which determine how
278 to handle this for themselves. For front-ends that use the metadata in
279 creating document headers (e.g., HTML, LaTeX, roff), the policy is not
280 to process deleted metadata.</p>
281 </ins><ins>
282 <p>Thus, metadata won&#8217;t strictly represent the document differences.</p>
283 </ins><ins>
284 <h3 id="footnotes">Footnotes</h3>
285 </ins><ins>
286 <p>Footnotes required some consideration because the order in which the
287 definitions and references are printed must be synchronised. Now a
288 process keeps track of all references (added, deleted, unchanged) and
289 renumbers then. When references are emitted, these are emitted in the
290 correct order.</p>
291 </ins>
292 <h2 id="api">API</h2>
293 <p>The result of the algorithm is a new tree marked with insertions and
294 deletions. These are specifically noted with the <code>LOWDOWN_CHNG_INSERT</code>
295 and <code>LOWDOWN_CHNG_DELETE</code> variables.</p>
296 <p>The algorithm may be run with the <code>lowdown_diff()</code> function, which
297 produces the merged tree.</p>
298 <p>A set of convenience functions, <code>lowdown_buf_diff()</code> and
299 <code>lowdown_file_diff()</code>, also provide this functionality.</p>
300 <h2 id="future-work">Future work</h2>
301 <p>There are many possible improvements to the algorithm.</p>
302 <del>
303 <p>Foremost is the issue of normal text nodes. There should be a process
304 first that merges consecutive text nodes. This happens, for example,
305 when the <code>w</code> character is encountered at any time and might signify a
306 link. The parsing algorithm will start a new text node at each such
307 character. </p>
308 </del>
309 <p>The merging algorithm can also take advantage of
310 <a href="https://github.com/kristapsdz/libdiff">libdiff</a> when ordering the
311 output of inserted and deleted components. Right now, the algorithm is
312 simple in the sense of stopping at the earliest matched node without
313 considering subsequences.</p>
314 <del>
315 <p>Lastly, the <strong>-Tms</strong> and <strong>-Tman</strong> output needs work to make sure that
316 the insert&#47;delete macros don&#8217;t disrupt the flow of text.</p>
317 </del>
318 <p>Document last updated: $Date$</p>
319 <div class="footnotes">
320 <hr/>
321 <ol>
322
323 <li id="fn1">
324 <p>This is just to illustrate a removed footnote.&#160;<a href="#fnref1" rev="footnote">&#8617;</a></p>
325 </li>
326
327 <li id="fn2">
328 <p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.73.8912&amp;rep=rep1&amp;type=pdf">Change Detection in XML Trees: a
329 Survey</a>
330 (2005), Luuk Peters.&#160;<a href="#fnref2" rev="footnote">&#8617;</a></p>
331 </li>
332
333 <li id="fn3">
334 <p><a href="https://www.cs.rutgers.edu/~amelie/papers/2002/diff.pdf">Detecting Changes in XML
335 Documents</a>
336 (2002), Gregory Cobena, Serge Abiteboul, Amelie Marian.&#160;<a href="#fnref3" rev="footnote">&#8617;</a></p>
337 </li>
338
339 <li id="fn4">
340 <p><a href="https://publications.mpi-cbg.de/Wu_1990_6334.pdf">An O(NP) sequence comparison
341 algorithm</a> (1990),
342 Sun Wu, Udi Manber, Gene Myers.&#160;<a href="#fnref4" rev="footnote">&#8617;</a></p>
343 </li>
344
345 <li id="fn5">
346 <p><a href="https://www.cs.dartmouth.edu/~doug/diff.pdf">An Algorithm for Differential File
347 Comparison</a>(1976),
348 James W. Hunt, M. Douglas McIlroy.&#160;<a href="#fnref5" rev="footnote">&#8617;</a></p>
349 </li>
350
351 </ol>
352 </div>
353 </body>
354 </html>