Blame


1 1dfba055 2020-10-07 stsp /* Generic infrastructure to implement various diff algorithms. */
2 1dfba055 2020-10-07 stsp /*
3 1dfba055 2020-10-07 stsp * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
4 1dfba055 2020-10-07 stsp *
5 1dfba055 2020-10-07 stsp * Permission to use, copy, modify, and distribute this software for any
6 1dfba055 2020-10-07 stsp * purpose with or without fee is hereby granted, provided that the above
7 1dfba055 2020-10-07 stsp * copyright notice and this permission notice appear in all copies.
8 1dfba055 2020-10-07 stsp *
9 1dfba055 2020-10-07 stsp * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 1dfba055 2020-10-07 stsp * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 1dfba055 2020-10-07 stsp * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 1dfba055 2020-10-07 stsp * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 1dfba055 2020-10-07 stsp * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 1dfba055 2020-10-07 stsp * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 1dfba055 2020-10-07 stsp * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 1dfba055 2020-10-07 stsp */
17 1dfba055 2020-10-07 stsp
18 1dfba055 2020-10-07 stsp struct diff_range {
19 1dfba055 2020-10-07 stsp int start;
20 1dfba055 2020-10-07 stsp int end;
21 1dfba055 2020-10-07 stsp };
22 1dfba055 2020-10-07 stsp
23 1dfba055 2020-10-07 stsp /* List of all possible return codes of a diff invocation. */
24 1dfba055 2020-10-07 stsp #define DIFF_RC_USE_DIFF_ALGO_FALLBACK -1
25 1dfba055 2020-10-07 stsp #define DIFF_RC_OK 0
26 1dfba055 2020-10-07 stsp /* Any positive return values are errno values from sys/errno.h */
27 1dfba055 2020-10-07 stsp
28 29916bb6 2020-11-18 stsp struct diff_atom {
29 29916bb6 2020-11-18 stsp struct diff_data *root; /* back pointer to root diff data */
30 1dfba055 2020-10-07 stsp
31 29916bb6 2020-11-18 stsp off_t pos; /* if not memory-mapped */
32 29916bb6 2020-11-18 stsp const uint8_t *at; /* if memory-mapped */
33 29916bb6 2020-11-18 stsp off_t len;
34 29916bb6 2020-11-18 stsp
35 29916bb6 2020-11-18 stsp /* This hash is just a very cheap speed up for finding *mismatching*
36 29916bb6 2020-11-18 stsp * atoms. When hashes match, we still need to compare entire atoms to
37 29916bb6 2020-11-18 stsp * find out whether they are indeed identical or not.
38 29916bb6 2020-11-18 stsp * Calculated over all atom bytes with diff_atom_hash_update(). */
39 29916bb6 2020-11-18 stsp unsigned int hash;
40 29916bb6 2020-11-18 stsp };
41 29916bb6 2020-11-18 stsp
42 29916bb6 2020-11-18 stsp /* Mix another atom_byte into the provided hash value and return the result.
43 29916bb6 2020-11-18 stsp * The hash value passed in for the first byte of the atom must be zero. */
44 29916bb6 2020-11-18 stsp unsigned int
45 29916bb6 2020-11-18 stsp diff_atom_hash_update(unsigned int hash, unsigned char atom_byte);
46 29916bb6 2020-11-18 stsp
47 29916bb6 2020-11-18 stsp /* Compare two atoms for equality. Return 0 on success, or errno on failure.
48 29916bb6 2020-11-18 stsp * Set cmp to -1, 0, or 1, just like strcmp(). */
49 29916bb6 2020-11-18 stsp int
50 29916bb6 2020-11-18 stsp diff_atom_cmp(int *cmp,
51 29916bb6 2020-11-18 stsp const struct diff_atom *left,
52 29916bb6 2020-11-18 stsp const struct diff_atom *right);
53 29916bb6 2020-11-18 stsp
54 29916bb6 2020-11-18 stsp
55 29916bb6 2020-11-18 stsp /* The atom's index in the entire file. For atoms divided by lines of text, this
56 29916bb6 2020-11-18 stsp * yields the line number (starting with 0). Also works for diff_data that
57 29916bb6 2020-11-18 stsp * reference only a subsection of a file, always reflecting the global position
58 29916bb6 2020-11-18 stsp * in the file (and not the relative position within the subsection). */
59 29916bb6 2020-11-18 stsp #define diff_atom_root_idx(DIFF_DATA, ATOM) \
60 29916bb6 2020-11-18 stsp ((ATOM) && ((ATOM) >= (DIFF_DATA)->root->atoms.head) \
61 29916bb6 2020-11-18 stsp ? (unsigned int)((ATOM) - ((DIFF_DATA)->root->atoms.head)) \
62 29916bb6 2020-11-18 stsp : (DIFF_DATA)->root->atoms.len)
63 29916bb6 2020-11-18 stsp
64 29916bb6 2020-11-18 stsp /* The atom's index within DIFF_DATA. For atoms divided by lines of text, this
65 29916bb6 2020-11-18 stsp * yields the line number (starting with 0). */
66 29916bb6 2020-11-18 stsp #define diff_atom_idx(DIFF_DATA, ATOM) \
67 29916bb6 2020-11-18 stsp ((ATOM) && ((ATOM) >= (DIFF_DATA)->atoms.head) \
68 29916bb6 2020-11-18 stsp ? (unsigned int)((ATOM) - ((DIFF_DATA)->atoms.head)) \
69 29916bb6 2020-11-18 stsp : (DIFF_DATA)->atoms.len)
70 29916bb6 2020-11-18 stsp
71 29916bb6 2020-11-18 stsp #define foreach_diff_atom(ATOM, FIRST_ATOM, COUNT) \
72 29916bb6 2020-11-18 stsp for ((ATOM) = (FIRST_ATOM); \
73 29916bb6 2020-11-18 stsp (ATOM) \
74 29916bb6 2020-11-18 stsp && ((ATOM) >= (FIRST_ATOM)) \
75 29916bb6 2020-11-18 stsp && ((ATOM) - (FIRST_ATOM) < (COUNT)); \
76 29916bb6 2020-11-18 stsp (ATOM)++)
77 29916bb6 2020-11-18 stsp
78 29916bb6 2020-11-18 stsp #define diff_data_foreach_atom(ATOM, DIFF_DATA) \
79 29916bb6 2020-11-18 stsp foreach_diff_atom(ATOM, (DIFF_DATA)->atoms.head, (DIFF_DATA)->atoms.len)
80 29916bb6 2020-11-18 stsp
81 29916bb6 2020-11-18 stsp #define diff_data_foreach_atom_from(FROM, ATOM, DIFF_DATA) \
82 29916bb6 2020-11-18 stsp for ((ATOM) = (FROM); \
83 29916bb6 2020-11-18 stsp (ATOM) \
84 29916bb6 2020-11-18 stsp && ((ATOM) >= (DIFF_DATA)->atoms.head) \
85 29916bb6 2020-11-18 stsp && ((ATOM) - (DIFF_DATA)->atoms.head < (DIFF_DATA)->atoms.len); \
86 29916bb6 2020-11-18 stsp (ATOM)++)
87 29916bb6 2020-11-18 stsp
88 29916bb6 2020-11-18 stsp #define diff_data_foreach_atom_backwards_from(FROM, ATOM, DIFF_DATA) \
89 29916bb6 2020-11-18 stsp for ((ATOM) = (FROM); \
90 29916bb6 2020-11-18 stsp (ATOM) \
91 29916bb6 2020-11-18 stsp && ((ATOM) >= (DIFF_DATA)->atoms.head) \
92 29916bb6 2020-11-18 stsp && ((ATOM) - (DIFF_DATA)->atoms.head >= 0); \
93 29916bb6 2020-11-18 stsp (ATOM)--)
94 29916bb6 2020-11-18 stsp
95 1dfba055 2020-10-07 stsp /* For each file, there is a "root" struct diff_data referencing the entire
96 1dfba055 2020-10-07 stsp * file, which the atoms are parsed from. In recursion of diff algorithm, there
97 1dfba055 2020-10-07 stsp * may be "child" struct diff_data only referencing a subsection of the file,
98 1dfba055 2020-10-07 stsp * re-using the atoms parsing. For "root" structs, atoms_allocated will be
99 1dfba055 2020-10-07 stsp * nonzero, indicating that the array of atoms is owned by that struct. For
100 1dfba055 2020-10-07 stsp * "child" structs, atoms_allocated == 0, to indicate that the struct is
101 1dfba055 2020-10-07 stsp * referencing a subset of atoms. */
102 1dfba055 2020-10-07 stsp struct diff_data {
103 1dfba055 2020-10-07 stsp FILE *f; /* if root diff_data and not memory-mapped */
104 1dfba055 2020-10-07 stsp off_t pos; /* if not memory-mapped */
105 1dfba055 2020-10-07 stsp const uint8_t *data; /* if memory-mapped */
106 1dfba055 2020-10-07 stsp off_t len;
107 1dfba055 2020-10-07 stsp
108 e51ebd83 2020-11-21 stsp int atomizer_flags;
109 1dfba055 2020-10-07 stsp ARRAYLIST(struct diff_atom) atoms;
110 1dfba055 2020-10-07 stsp struct diff_data *root;
111 6c8c5d3f 2020-10-12 neels struct diff_data *current;
112 6c8c5d3f 2020-10-12 neels void *algo_data;
113 1dfba055 2020-10-07 stsp
114 1dfba055 2020-10-07 stsp int diff_flags;
115 60b6e08b 2020-10-12 neels
116 60b6e08b 2020-10-12 neels int err;
117 1dfba055 2020-10-07 stsp };
118 1dfba055 2020-10-07 stsp
119 e51ebd83 2020-11-21 stsp /* Flags set by file atomizer. */
120 e51ebd83 2020-11-21 stsp #define DIFF_ATOMIZER_FOUND_BINARY_DATA 0x00000001
121 e51ebd83 2020-11-21 stsp
122 e51ebd83 2020-11-21 stsp /* Flags set by caller of diff_main(). */
123 1dfba055 2020-10-07 stsp #define DIFF_FLAG_IGNORE_WHITESPACE 0x00000001
124 13e2caa3 2020-10-17 stsp #define DIFF_FLAG_SHOW_PROTOTYPES 0x00000002
125 e51ebd83 2020-11-21 stsp #define DIFF_FLAG_FORCE_TEXT_DATA 0x00000004
126 1dfba055 2020-10-07 stsp
127 1dfba055 2020-10-07 stsp void diff_data_free(struct diff_data *diff_data);
128 1dfba055 2020-10-07 stsp
129 1dfba055 2020-10-07 stsp struct diff_chunk;
130 1dfba055 2020-10-07 stsp typedef ARRAYLIST(struct diff_chunk) diff_chunk_arraylist_t;
131 1dfba055 2020-10-07 stsp
132 1dfba055 2020-10-07 stsp struct diff_result {
133 1dfba055 2020-10-07 stsp int rc;
134 c16dde50 2020-10-22 stsp
135 c16dde50 2020-10-22 stsp /*
136 c16dde50 2020-10-22 stsp * Pointers to diff data passed in via diff_main.
137 c16dde50 2020-10-22 stsp * Do not free these diff_data before freeing the diff_result struct.
138 c16dde50 2020-10-22 stsp */
139 c16dde50 2020-10-22 stsp struct diff_data *left;
140 c16dde50 2020-10-22 stsp struct diff_data *right;
141 c16dde50 2020-10-22 stsp
142 1dfba055 2020-10-07 stsp diff_chunk_arraylist_t chunks;
143 1dfba055 2020-10-07 stsp };
144 1dfba055 2020-10-07 stsp
145 1dfba055 2020-10-07 stsp struct diff_state;
146 1dfba055 2020-10-07 stsp
147 c16dde50 2020-10-22 stsp /* Signature of a utility function to divide a file into diff atoms.
148 1dfba055 2020-10-07 stsp * An example is diff_atomize_text_by_line() in diff_atomize_text.c.
149 1dfba055 2020-10-07 stsp *
150 1dfba055 2020-10-07 stsp * func_data: context pointer (free to be used by implementation).
151 c16dde50 2020-10-22 stsp * d: struct diff_data with d->data and d->len already set up, and
152 e51ebd83 2020-11-21 stsp * d->atoms to be created and d->atomizer_flags to be set up.
153 1dfba055 2020-10-07 stsp */
154 c16dde50 2020-10-22 stsp typedef int (*diff_atomize_func_t)(void *func_data, struct diff_data *d);
155 1dfba055 2020-10-07 stsp
156 c16dde50 2020-10-22 stsp extern int diff_atomize_text_by_line(void *func_data, struct diff_data *d);
157 1dfba055 2020-10-07 stsp
158 1dfba055 2020-10-07 stsp struct diff_algo_config;
159 1dfba055 2020-10-07 stsp typedef int (*diff_algo_impl_t)(
160 1dfba055 2020-10-07 stsp const struct diff_algo_config *algo_config, struct diff_state *state);
161 1dfba055 2020-10-07 stsp
162 1dfba055 2020-10-07 stsp /* Form a result with all left-side removed and all right-side added, i.e. no
163 1dfba055 2020-10-07 stsp * actual diff algorithm involved. */
164 1dfba055 2020-10-07 stsp int diff_algo_none(const struct diff_algo_config *algo_config,
165 0c70b22b 2020-10-11 neels struct diff_state *state);
166 1dfba055 2020-10-07 stsp
167 1dfba055 2020-10-07 stsp /* Myers Diff tracing from the start all the way through to the end, requiring
168 1dfba055 2020-10-07 stsp * quadratic amounts of memory. This can fail if the required space surpasses
169 1dfba055 2020-10-07 stsp * algo_config->permitted_state_size. */
170 1dfba055 2020-10-07 stsp extern int diff_algo_myers(const struct diff_algo_config *algo_config,
171 0c70b22b 2020-10-11 neels struct diff_state *state);
172 1dfba055 2020-10-07 stsp
173 1dfba055 2020-10-07 stsp /* Myers "Divide et Impera": tracing forwards from the start and backwards from
174 1dfba055 2020-10-07 stsp * the end to find a midpoint that divides the problem into smaller chunks.
175 1dfba055 2020-10-07 stsp * Requires only linear amounts of memory. */
176 1dfba055 2020-10-07 stsp extern int diff_algo_myers_divide(
177 1dfba055 2020-10-07 stsp const struct diff_algo_config *algo_config, struct diff_state *state);
178 1dfba055 2020-10-07 stsp
179 1dfba055 2020-10-07 stsp /* Patience Diff algorithm, which divides a larger diff into smaller chunks. For
180 1dfba055 2020-10-07 stsp * very specific scenarios, it may lead to a complete diff result by itself, but
181 1dfba055 2020-10-07 stsp * needs a fallback algo to solve chunks that don't have common-unique atoms. */
182 1dfba055 2020-10-07 stsp extern int diff_algo_patience(
183 1dfba055 2020-10-07 stsp const struct diff_algo_config *algo_config, struct diff_state *state);
184 1dfba055 2020-10-07 stsp
185 1dfba055 2020-10-07 stsp /* Diff algorithms to use, possibly nested. For example:
186 1dfba055 2020-10-07 stsp *
187 1dfba055 2020-10-07 stsp * struct diff_algo_config myers, patience, myers_divide;
188 1dfba055 2020-10-07 stsp *
189 1dfba055 2020-10-07 stsp * myers = (struct diff_algo_config){
190 1dfba055 2020-10-07 stsp * .impl = diff_algo_myers,
191 1dfba055 2020-10-07 stsp * .permitted_state_size = 32 * 1024 * 1024,
192 1dfba055 2020-10-07 stsp * // When too large, do diff_algo_patience:
193 1dfba055 2020-10-07 stsp * .fallback_algo = &patience,
194 1dfba055 2020-10-07 stsp * };
195 1dfba055 2020-10-07 stsp *
196 1dfba055 2020-10-07 stsp * const struct diff_algo_config patience = (struct diff_algo_config){
197 1dfba055 2020-10-07 stsp * .impl = diff_algo_patience,
198 1dfba055 2020-10-07 stsp * // After subdivision, do Patience again:
199 1dfba055 2020-10-07 stsp * .inner_algo = &patience,
200 1dfba055 2020-10-07 stsp * // If subdivision failed, do Myers Divide et Impera:
201 1dfba055 2020-10-07 stsp * .fallback_algo = &myers_then_myers_divide,
202 1dfba055 2020-10-07 stsp * };
203 1dfba055 2020-10-07 stsp *
204 1dfba055 2020-10-07 stsp * const struct diff_algo_config myers_divide = (struct diff_algo_config){
205 1dfba055 2020-10-07 stsp * .impl = diff_algo_myers_divide,
206 1dfba055 2020-10-07 stsp * // When division succeeded, start from the top:
207 1dfba055 2020-10-07 stsp * .inner_algo = &myers_then_myers_divide,
208 1dfba055 2020-10-07 stsp * // (fallback_algo = NULL implies diff_algo_none).
209 1dfba055 2020-10-07 stsp * };
210 1dfba055 2020-10-07 stsp * struct diff_config config = {
211 1dfba055 2020-10-07 stsp * .algo = &myers,
212 1dfba055 2020-10-07 stsp * ...
213 1dfba055 2020-10-07 stsp * };
214 1dfba055 2020-10-07 stsp * diff_main(&config, ...);
215 1dfba055 2020-10-07 stsp */
216 1dfba055 2020-10-07 stsp struct diff_algo_config {
217 1dfba055 2020-10-07 stsp diff_algo_impl_t impl;
218 1dfba055 2020-10-07 stsp
219 1dfba055 2020-10-07 stsp /* Fail this algo if it would use more than this amount of memory, and
220 1dfba055 2020-10-07 stsp * instead use fallback_algo (diff_algo_myers). permitted_state_size ==
221 1dfba055 2020-10-07 stsp * 0 means no limitation. */
222 1dfba055 2020-10-07 stsp size_t permitted_state_size;
223 1dfba055 2020-10-07 stsp
224 1dfba055 2020-10-07 stsp /* For algorithms that divide into smaller chunks, use this algorithm to
225 1dfba055 2020-10-07 stsp * solve the divided chunks. */
226 1dfba055 2020-10-07 stsp const struct diff_algo_config *inner_algo;
227 1dfba055 2020-10-07 stsp
228 1dfba055 2020-10-07 stsp /* If the algorithm fails (e.g. diff_algo_myers_if_small needs too large
229 1dfba055 2020-10-07 stsp * state, or diff_algo_patience can't find any common-unique atoms),
230 1dfba055 2020-10-07 stsp * then use this algorithm instead. */
231 1dfba055 2020-10-07 stsp const struct diff_algo_config *fallback_algo;
232 1dfba055 2020-10-07 stsp };
233 1dfba055 2020-10-07 stsp
234 1dfba055 2020-10-07 stsp struct diff_config {
235 1dfba055 2020-10-07 stsp diff_atomize_func_t atomize_func;
236 1dfba055 2020-10-07 stsp void *atomize_func_data;
237 1dfba055 2020-10-07 stsp
238 1dfba055 2020-10-07 stsp const struct diff_algo_config *algo;
239 1dfba055 2020-10-07 stsp
240 1dfba055 2020-10-07 stsp /* How deep to step into subdivisions of a source file, a paranoia /
241 1dfba055 2020-10-07 stsp * safety measure to guard against infinite loops through diff
242 1dfba055 2020-10-07 stsp * algorithms. When the maximum recursion is reached, employ
243 1dfba055 2020-10-07 stsp * diff_algo_none (i.e. remove all left atoms and add all right atoms).
244 1dfba055 2020-10-07 stsp */
245 1dfba055 2020-10-07 stsp unsigned int max_recursion_depth;
246 1dfba055 2020-10-07 stsp };
247 1dfba055 2020-10-07 stsp
248 c16dde50 2020-10-22 stsp int diff_atomize_file(struct diff_data *d, const struct diff_config *config,
249 c16dde50 2020-10-22 stsp FILE *f, const uint8_t *data, off_t len, int diff_flags);
250 1dfba055 2020-10-07 stsp struct diff_result *diff_main(const struct diff_config *config,
251 c16dde50 2020-10-22 stsp struct diff_data *left,
252 c16dde50 2020-10-22 stsp struct diff_data *right);
253 1dfba055 2020-10-07 stsp void diff_result_free(struct diff_result *result);