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