1 3b0f3d61 2020-01-22 neels /* Generic infrastructure to implement various diff algorithms. */
3 3b0f3d61 2020-01-22 neels * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
5 3b0f3d61 2020-01-22 neels * Permission to use, copy, modify, and distribute this software for any
6 3b0f3d61 2020-01-22 neels * purpose with or without fee is hereby granted, provided that the above
7 3b0f3d61 2020-01-22 neels * copyright notice and this permission notice appear in all copies.
9 3b0f3d61 2020-01-22 neels * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 3b0f3d61 2020-01-22 neels * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 3b0f3d61 2020-01-22 neels * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 3b0f3d61 2020-01-22 neels * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 3b0f3d61 2020-01-22 neels * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 3b0f3d61 2020-01-22 neels * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 3b0f3d61 2020-01-22 neels * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 3b0f3d61 2020-01-22 neels #pragma once
20 3b0f3d61 2020-01-22 neels #include <stdint.h>
21 3b0f3d61 2020-01-22 neels #include <stdlib.h>
22 3b0f3d61 2020-01-22 neels #include <stdbool.h>
23 3b0f3d61 2020-01-22 neels #include <string.h>
24 3b0f3d61 2020-01-22 neels #include <errno.h>
26 3b0f3d61 2020-01-22 neels #include <diff/arraylist.h>
28 54fa8228 2020-01-27 neels #ifndef MAX
29 54fa8228 2020-01-27 neels #define MAX(A,B) ((A)>(B)?(A):(B))
31 54fa8228 2020-01-27 neels #ifndef MIN
32 54fa8228 2020-01-27 neels #define MIN(A,B) ((A)<(B)?(A):(B))
35 54fa8228 2020-01-27 neels struct range {
40 61a7b578 2020-05-06 neels static inline bool
41 61a7b578 2020-05-06 neels range_empty(const struct range *r)
43 54fa8228 2020-01-27 neels return r->start == r->end;
46 61a7b578 2020-05-06 neels static inline bool
47 61a7b578 2020-05-06 neels ranges_touch(const struct range *a, const struct range *b)
49 54fa8228 2020-01-27 neels return (a->end >= b->start) && (a->start <= b->end);
52 61a7b578 2020-05-06 neels static inline void
53 61a7b578 2020-05-06 neels ranges_merge(struct range *a, const struct range *b)
55 54fa8228 2020-01-27 neels *a = (struct range){
56 54fa8228 2020-01-27 neels .start = MIN(a->start, b->start),
57 54fa8228 2020-01-27 neels .end = MAX(a->end, b->end),
61 61a7b578 2020-05-06 neels static inline int
62 61a7b578 2020-05-06 neels range_len(const struct range *r)
66 54fa8228 2020-01-27 neels return r->end - r->start;
69 3b0f3d61 2020-01-22 neels /* List of all possible return codes of a diff invocation. */
70 3b0f3d61 2020-01-22 neels enum diff_rc {
71 3b0f3d61 2020-01-22 neels DIFF_RC_USE_DIFF_ALGO_FALLBACK = -1,
72 3b0f3d61 2020-01-22 neels DIFF_RC_OK = 0,
73 3b0f3d61 2020-01-22 neels DIFF_RC_ENOTSUP = ENOTSUP,
74 3b0f3d61 2020-01-22 neels DIFF_RC_ENOMEM = ENOMEM,
75 3b0f3d61 2020-01-22 neels DIFF_RC_EINVAL = EINVAL,
78 3b0f3d61 2020-01-22 neels struct diff_atom {
79 3b0f3d61 2020-01-22 neels const uint8_t *at;
80 3b0f3d61 2020-01-22 neels size_t len;
82 3b0f3d61 2020-01-22 neels /* This hash is just a very cheap speed up for finding *mismatching* atoms. When hashes match, we still need to
83 3b0f3d61 2020-01-22 neels * compare entire atoms to find out whether they are indeed identical or not. */
84 3b0f3d61 2020-01-22 neels unsigned int hash;
86 3b0f3d61 2020-01-22 neels /* State for the Patience Diff algorithm */
87 3b0f3d61 2020-01-22 neels /* TODO: keep a separate array for the patience state */
89 3b0f3d61 2020-01-22 neels bool unique_here;
90 3b0f3d61 2020-01-22 neels bool unique_in_both;
91 3b0f3d61 2020-01-22 neels struct diff_atom *pos_in_other;
92 3b0f3d61 2020-01-22 neels struct diff_atom *prev_stack;
93 bb7fb738 2020-01-27 neels struct range identical_lines;
94 3b0f3d61 2020-01-22 neels } patience;
97 61a7b578 2020-05-06 neels static inline bool
98 61a7b578 2020-05-06 neels diff_atom_same(const struct diff_atom *left, const struct diff_atom *right)
100 3b0f3d61 2020-01-22 neels return left->hash == right->hash
101 3b0f3d61 2020-01-22 neels && left->len == right->len
102 3b0f3d61 2020-01-22 neels && memcmp(left->at, right->at, left->len) == 0;
105 3b0f3d61 2020-01-22 neels /* For each file, there is a "root" struct diff_data referencing the entire file, which the atoms are parsed from. In
106 3b0f3d61 2020-01-22 neels * recursion of diff algorithm, there may be "child" struct diff_data only referencing a subsection of the file,
107 3b0f3d61 2020-01-22 neels * re-using the atoms parsing. For "root" structs, atoms_allocated will be nonzero, indicating that the array of atoms
108 3b0f3d61 2020-01-22 neels * is owned by that struct. For "child" structs, atoms_allocated == 0, to indicate that the struct is referencing a
109 3b0f3d61 2020-01-22 neels * subset of atoms. */
110 3b0f3d61 2020-01-22 neels struct diff_data {
111 3b0f3d61 2020-01-22 neels const uint8_t *data;
112 3b0f3d61 2020-01-22 neels size_t len;
113 3b0f3d61 2020-01-22 neels ARRAYLIST(struct diff_atom) atoms;
114 3b0f3d61 2020-01-22 neels struct diff_data *root;
117 3b0f3d61 2020-01-22 neels void diff_data_free(struct diff_data *diff_data);
119 3b0f3d61 2020-01-22 neels /* The atom's index in the entire file. For atoms divided by lines of text, this yields the line number (starting with
120 3b0f3d61 2020-01-22 neels * 0). Also works for diff_data that reference only a subsection of a file, always reflecting the global position in
121 3b0f3d61 2020-01-22 neels * the file (and not the relative position within the subsection). */
122 3b0f3d61 2020-01-22 neels #define diff_atom_root_idx(DIFF_DATA, ATOM) \
123 15ac50e2 2020-05-05 neels ((ATOM) && ((ATOM) >= (DIFF_DATA)->root->atoms.head) \
124 15ac50e2 2020-05-05 neels ? (unsigned int)((ATOM) - ((DIFF_DATA)->root->atoms.head)) \
125 15ac50e2 2020-05-05 neels : (DIFF_DATA)->root->atoms.len)
127 3b0f3d61 2020-01-22 neels /* The atom's index within DIFF_DATA. For atoms divided by lines of text, this yields the line number (starting with
129 3b0f3d61 2020-01-22 neels #define diff_atom_idx(DIFF_DATA, ATOM) \
130 15ac50e2 2020-05-05 neels ((ATOM) && ((ATOM) >= (DIFF_DATA)->atoms.head) \
131 15ac50e2 2020-05-05 neels ? (unsigned int)((ATOM) - ((DIFF_DATA)->atoms.head)) \
132 15ac50e2 2020-05-05 neels : (DIFF_DATA)->atoms.len)
134 3b0f3d61 2020-01-22 neels #define foreach_diff_atom(ATOM, FIRST_ATOM, COUNT) \
135 3b0f3d61 2020-01-22 neels for ((ATOM) = (FIRST_ATOM); \
136 3b0f3d61 2020-01-22 neels (ATOM) && ((ATOM) >= (FIRST_ATOM)) && ((ATOM) - (FIRST_ATOM) < (COUNT)); \
139 3b0f3d61 2020-01-22 neels #define diff_data_foreach_atom(ATOM, DIFF_DATA) \
140 3b0f3d61 2020-01-22 neels foreach_diff_atom(ATOM, (DIFF_DATA)->atoms.head, (DIFF_DATA)->atoms.len)
142 3b0f3d61 2020-01-22 neels #define diff_data_foreach_atom_from(FROM, ATOM, DIFF_DATA) \
143 3b0f3d61 2020-01-22 neels for ((ATOM) = (FROM); \
144 3b0f3d61 2020-01-22 neels (ATOM) && ((ATOM) >= (DIFF_DATA)->atoms.head) && ((ATOM) - (DIFF_DATA)->atoms.head < (DIFF_DATA)->atoms.len); \
147 3b0f3d61 2020-01-22 neels /* A diff chunk represents a set of atoms on the left and/or a set of atoms on the right.
149 3b0f3d61 2020-01-22 neels * If solved == false:
150 3b0f3d61 2020-01-22 neels * The diff algorithm has divided the source file, and this is a chunk that the inner_algo should run on next.
151 3b0f3d61 2020-01-22 neels * The lines on the left should be diffed against the lines on the right.
152 3b0f3d61 2020-01-22 neels * (If there are no left lines or no right lines, it implies solved == true, because there is nothing to diff.)
154 3b0f3d61 2020-01-22 neels * If solved == true:
155 3b0f3d61 2020-01-22 neels * If there are only left atoms, it is a chunk removing atoms from the left ("a minus chunk").
156 3b0f3d61 2020-01-22 neels * If there are only right atoms, it is a chunk adding atoms from the right ("a plus chunk").
157 3b0f3d61 2020-01-22 neels * If there are both left and right lines, it is a chunk of equal content on both sides,
158 3b0f3d61 2020-01-22 neels * and left_count == right_count:
161 3b0f3d61 2020-01-22 neels * - bar }-- diff_chunk{ left_start = &left.atoms.head[0], left_count = 3,
162 3b0f3d61 2020-01-22 neels * - baz } right_start = NULL, right_count = 0 }
164 3b0f3d61 2020-01-22 neels * goo }-- diff_chunk{ left_start = &left.atoms.head[3], left_count = 3,
165 3b0f3d61 2020-01-22 neels * zoo } right_start = &right.atoms.head[0], right_count = 3 }
167 3b0f3d61 2020-01-22 neels * +roo }-- diff_chunk{ left_start = NULL, left_count = 0,
168 3b0f3d61 2020-01-22 neels * +too } right_start = &right.atoms.head[3], right_count = 3 }
171 3b0f3d61 2020-01-22 neels struct diff_chunk {
172 3b0f3d61 2020-01-22 neels bool solved;
173 3b0f3d61 2020-01-22 neels struct diff_atom *left_start;
174 3b0f3d61 2020-01-22 neels unsigned int left_count;
175 3b0f3d61 2020-01-22 neels struct diff_atom *right_start;
176 3b0f3d61 2020-01-22 neels unsigned int right_count;
179 3b0f3d61 2020-01-22 neels typedef ARRAYLIST(struct diff_chunk) diff_chunk_arraylist_t;
180 3b0f3d61 2020-01-22 neels #define DIFF_RESULT_ALLOC_BLOCKSIZE 128
182 3b0f3d61 2020-01-22 neels struct diff_result {
183 3b0f3d61 2020-01-22 neels enum diff_rc rc;
184 3b0f3d61 2020-01-22 neels struct diff_data left;
185 3b0f3d61 2020-01-22 neels struct diff_data right;
186 3b0f3d61 2020-01-22 neels diff_chunk_arraylist_t chunks;
189 3b0f3d61 2020-01-22 neels struct diff_state {
190 3b0f3d61 2020-01-22 neels /* The final result passed to the original diff caller. */
191 3b0f3d61 2020-01-22 neels struct diff_result *result;
193 3b0f3d61 2020-01-22 neels /* The root diff_data is in result->left,right, these are (possibly) subsections of the root data. */
194 3b0f3d61 2020-01-22 neels struct diff_data left;
195 3b0f3d61 2020-01-22 neels struct diff_data right;
197 3b0f3d61 2020-01-22 neels unsigned int recursion_depth_left;
199 3b0f3d61 2020-01-22 neels /* Remaining chunks from one diff algorithm pass, if any solved == false chunks came up. */
200 3b0f3d61 2020-01-22 neels diff_chunk_arraylist_t temp_result;
203 3b0f3d61 2020-01-22 neels struct diff_chunk *diff_state_add_chunk(struct diff_state *state, bool solved,
204 3b0f3d61 2020-01-22 neels struct diff_atom *left_start, unsigned int left_count,
205 3b0f3d61 2020-01-22 neels struct diff_atom *right_start, unsigned int right_count);
207 3b0f3d61 2020-01-22 neels /* Signature of a utility function to divide both source files into diff atoms.
208 3b0f3d61 2020-01-22 neels * It is possible that a (future) algorithm requires both source files to decide on atom split points, hence this gets
209 3b0f3d61 2020-01-22 neels * both left and right to atomize at the same time.
210 3b0f3d61 2020-01-22 neels * An example is diff_atomize_text_by_line() in diff_atomize_text.c.
212 3b0f3d61 2020-01-22 neels * func_data: context pointer (free to be used by implementation).
213 3b0f3d61 2020-01-22 neels * left: struct diff_data with left->data and left->len already set up, and left->atoms to be created.
214 3b0f3d61 2020-01-22 neels * right: struct diff_data with right->data and right->len already set up, and right->atoms to be created.
216 3b0f3d61 2020-01-22 neels typedef enum diff_rc (*diff_atomize_func_t)(void *func_data, struct diff_data *left, struct diff_data *right);
218 3b0f3d61 2020-01-22 neels extern enum diff_rc diff_atomize_text_by_line(void *func_data, struct diff_data *left, struct diff_data *right);
220 3b0f3d61 2020-01-22 neels struct diff_algo_config;
221 3b0f3d61 2020-01-22 neels typedef enum diff_rc (*diff_algo_impl_t)(const struct diff_algo_config *algo_config, struct diff_state *state);
223 3b0f3d61 2020-01-22 neels /* Form a result with all left-side removed and all right-side added, i.e. no actual diff algorithm involved. */
224 3b0f3d61 2020-01-22 neels enum diff_rc diff_algo_none(const struct diff_algo_config *algo_config, struct diff_state *state);
226 3b0f3d61 2020-01-22 neels /* Myers Diff tracing from the start all the way through to the end, requiring quadratic amounts of memory. This can
227 3b0f3d61 2020-01-22 neels * fail if the required space surpasses algo_config->permitted_state_size. */
228 3b0f3d61 2020-01-22 neels extern enum diff_rc diff_algo_myers(const struct diff_algo_config *algo_config, struct diff_state *state);
230 3b0f3d61 2020-01-22 neels /* Myers "Divide et Impera": tracing forwards from the start and backwards from the end to find a midpoint that divides
231 3b0f3d61 2020-01-22 neels * the problem into smaller chunks. Requires only linear amounts of memory. */
232 3b0f3d61 2020-01-22 neels extern enum diff_rc diff_algo_myers_divide(const struct diff_algo_config *algo_config, struct diff_state *state);
234 3b0f3d61 2020-01-22 neels /* Patience Diff algorithm, which divides a larger diff into smaller chunks. For very specific scenarios, it may lead to
235 3b0f3d61 2020-01-22 neels * a complete diff result by itself, but needs a fallback algo to solve chunks that don't have common-unique atoms. */
236 3b0f3d61 2020-01-22 neels extern enum diff_rc diff_algo_patience(const struct diff_algo_config *algo_config, struct diff_state *state);
238 3b0f3d61 2020-01-22 neels /* Diff algorithms to use, possibly nested. For example:
240 3b0f3d61 2020-01-22 neels * struct diff_algo_config myers, patience, myers_divide;
242 3b0f3d61 2020-01-22 neels * myers = (struct diff_algo_config){
243 3b0f3d61 2020-01-22 neels * .impl = diff_algo_myers,
244 3b0f3d61 2020-01-22 neels * .permitted_state_size = 32 * 1024 * 1024,
245 3b0f3d61 2020-01-22 neels * .fallback_algo = &patience, // when too large, do diff_algo_patience
248 3b0f3d61 2020-01-22 neels * patience = (struct diff_algo_config){
249 3b0f3d61 2020-01-22 neels * .impl = diff_algo_patience,
250 3b0f3d61 2020-01-22 neels * .inner_algo = &patience, // After subdivision, do Patience again.
251 3b0f3d61 2020-01-22 neels * .fallback_algo = &myers_divide, // If subdivision failed, do Myers Divide et Impera.
254 3b0f3d61 2020-01-22 neels * myers_divide = (struct diff_algo_config){
255 3b0f3d61 2020-01-22 neels * .impl = diff_algo_myers_divide,
256 3b0f3d61 2020-01-22 neels * .inner_algo = &myers, // When division succeeded, start from the top.
257 3b0f3d61 2020-01-22 neels * // (fallback_algo = NULL implies diff_algo_none).
260 3b0f3d61 2020-01-22 neels * struct diff_config config = {
261 3b0f3d61 2020-01-22 neels * .algo = &myers,
264 3b0f3d61 2020-01-22 neels * diff_main(&config, ...);
266 3b0f3d61 2020-01-22 neels struct diff_algo_config {
267 3b0f3d61 2020-01-22 neels diff_algo_impl_t impl;
269 3b0f3d61 2020-01-22 neels /* Fail this algo if it would use more than this amount of memory, and instead use fallback_algo
270 3b0f3d61 2020-01-22 neels * (diff_algo_myers). permitted_state_size == 0 means no limitation. */
271 3b0f3d61 2020-01-22 neels size_t permitted_state_size;
273 3b0f3d61 2020-01-22 neels /* For algorithms that divide into smaller chunks, use this algorithm to solve the divided chunks. */
274 3b0f3d61 2020-01-22 neels const struct diff_algo_config *inner_algo;
276 3b0f3d61 2020-01-22 neels /* If the algorithm fails (e.g. diff_algo_myers_if_small needs too large state, or diff_algo_patience can't find
277 3b0f3d61 2020-01-22 neels * any common-unique atoms), then use this algorithm instead. */
278 3b0f3d61 2020-01-22 neels const struct diff_algo_config *fallback_algo;
281 3b0f3d61 2020-01-22 neels struct diff_config {
282 3b0f3d61 2020-01-22 neels diff_atomize_func_t atomize_func;
283 3b0f3d61 2020-01-22 neels void *atomize_func_data;
285 3b0f3d61 2020-01-22 neels const struct diff_algo_config *algo;
287 3b0f3d61 2020-01-22 neels /* How deep to step into subdivisions of a source file, a paranoia / safety measure to guard against infinite
288 3b0f3d61 2020-01-22 neels * loops through diff algorithms. When the maximum recursion is reached, employ diff_algo_none (i.e. remove all
289 3b0f3d61 2020-01-22 neels * left atoms and add all right atoms). */
290 3b0f3d61 2020-01-22 neels unsigned int max_recursion_depth;
293 3b0f3d61 2020-01-22 neels struct diff_result *diff_main(const struct diff_config *config,
294 3b0f3d61 2020-01-22 neels const uint8_t *left_data, size_t left_len,
295 3b0f3d61 2020-01-22 neels const uint8_t *right_data, size_t right_len);
296 3b0f3d61 2020-01-22 neels void diff_result_free(struct diff_result *result);
