1 3b0f3d61 2020-01-22 neels /* Generic infrastructure to implement various diff algorithms (implementation). */
  2 3b0f3d61 2020-01-22 neels /*
  3 3b0f3d61 2020-01-22 neels  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
  4 3b0f3d61 2020-01-22 neels  *
  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.
  8 3b0f3d61 2020-01-22 neels  *
  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.
 16 3b0f3d61 2020-01-22 neels  */
 17 3b0f3d61 2020-01-22 neels 
 18 3b0f3d61 2020-01-22 neels 
 19 3b0f3d61 2020-01-22 neels #include <sys/queue.h>
 20 732e8ee0 2020-09-20 stsp #include <ctype.h>
 21 e10a628a 2020-09-16 stsp #include <errno.h>
 22 3b0f3d61 2020-01-22 neels #include <stdint.h>
 23 3b0f3d61 2020-01-22 neels #include <stdlib.h>
 24 3b0f3d61 2020-01-22 neels #include <stdbool.h>
 25 3b0f3d61 2020-01-22 neels #include <stdio.h>
 26 3b0f3d61 2020-01-22 neels #include <string.h>
 27 3b0f3d61 2020-01-22 neels #include <limits.h>
 28 c6eecea3 2020-07-26 stsp #include <unistd.h>
 29 3b0f3d61 2020-01-22 neels 
 30 3b0f3d61 2020-01-22 neels #include <assert.h>
 31 3b0f3d61 2020-01-22 neels 
 32 1dfba055 2020-10-07 stsp #include <arraylist.h>
 33 1dfba055 2020-10-07 stsp #include <diff_main.h>
 34 3b0f3d61 2020-01-22 neels 
 35 85ab4559 2020-09-22 stsp #include "diff_internal.h"
 36 2a1b94d0 2020-09-26 stsp #include "diff_debug.h"
 37 c6eecea3 2020-07-26 stsp 
 38 b3fb4686 2020-09-20 neels static int
 39 7a54ad3a 2020-09-20 stsp read_at(FILE *f, off_t at_pos, unsigned char *buf, size_t len)
 40 c6eecea3 2020-07-26 stsp {
 41 b3fb4686 2020-09-20 neels 	int r;
 42 7a54ad3a 2020-09-20 stsp 	if (fseeko(f, at_pos, SEEK_SET) == -1)
 43 b3fb4686 2020-09-20 neels 		return errno;
 44 7a54ad3a 2020-09-20 stsp 	r = fread(buf, sizeof(char), len, f);
 45 7a54ad3a 2020-09-20 stsp 	if ((r == 0 || r < len) && ferror(f))
 46 b3fb4686 2020-09-20 neels 		return errno;
 47 b3fb4686 2020-09-20 neels 	if (r != len)
 48 b3fb4686 2020-09-20 neels 		return EIO;
 49 b3fb4686 2020-09-20 neels 	return 0;
 50 b3fb4686 2020-09-20 neels }
 51 b3fb4686 2020-09-20 neels 
 52 b3fb4686 2020-09-20 neels static int
 53 b3fb4686 2020-09-20 neels buf_cmp(const unsigned char *left, size_t left_len,
 54 732e8ee0 2020-09-20 stsp 	const unsigned char *right, size_t right_len,
 55 732e8ee0 2020-09-20 stsp 	bool ignore_whitespace)
 56 b3fb4686 2020-09-20 neels {
 57 732e8ee0 2020-09-20 stsp 	int cmp;
 58 732e8ee0 2020-09-20 stsp 
 59 732e8ee0 2020-09-20 stsp 	if (ignore_whitespace) {
 60 732e8ee0 2020-09-20 stsp 		int il = 0, ir = 0;
 61 732e8ee0 2020-09-20 stsp 		while (il < left_len && ir < right_len) {
 62 732e8ee0 2020-09-20 stsp 			unsigned char cl = left[il];
 63 732e8ee0 2020-09-20 stsp 			unsigned char cr = right[ir];
 64 732e8ee0 2020-09-20 stsp 
 65 732e8ee0 2020-09-20 stsp 			if (isspace(cl) && il < left_len) {
 66 732e8ee0 2020-09-20 stsp 				il++;
 67 732e8ee0 2020-09-20 stsp 				continue;
 68 732e8ee0 2020-09-20 stsp 			}
 69 732e8ee0 2020-09-20 stsp 			if (isspace(cr) && ir < right_len) {
 70 732e8ee0 2020-09-20 stsp 				ir++;
 71 732e8ee0 2020-09-20 stsp 				continue;
 72 732e8ee0 2020-09-20 stsp 			}
 73 732e8ee0 2020-09-20 stsp 
 74 732e8ee0 2020-09-20 stsp 			if (cl > cr)
 75 732e8ee0 2020-09-20 stsp 				return 1;
 76 732e8ee0 2020-09-20 stsp 			if (cr > cl)
 77 732e8ee0 2020-09-20 stsp 				return -1;
 78 732e8ee0 2020-09-20 stsp 			il++;
 79 732e8ee0 2020-09-20 stsp 			ir++;
 80 732e8ee0 2020-09-20 stsp 		}
 81 732e8ee0 2020-09-20 stsp 		while (il < left_len) {
 82 732e8ee0 2020-09-20 stsp 			unsigned char cl = left[il++];
 83 732e8ee0 2020-09-20 stsp 			if (!isspace(cl))
 84 732e8ee0 2020-09-20 stsp 				return 1;
 85 732e8ee0 2020-09-20 stsp 		}
 86 732e8ee0 2020-09-20 stsp 		while (ir < right_len) {
 87 732e8ee0 2020-09-20 stsp 			unsigned char cr = right[ir++];
 88 732e8ee0 2020-09-20 stsp 			if (!isspace(cr))
 89 732e8ee0 2020-09-20 stsp 				return -1;
 90 732e8ee0 2020-09-20 stsp 		}
 91 732e8ee0 2020-09-20 stsp 
 92 732e8ee0 2020-09-20 stsp 		return 0;
 93 732e8ee0 2020-09-20 stsp 	}
 94 732e8ee0 2020-09-20 stsp 
 95 732e8ee0 2020-09-20 stsp 	cmp = memcmp(left, right, MIN(left_len, right_len));
 96 b3fb4686 2020-09-20 neels 	if (cmp)
 97 b3fb4686 2020-09-20 neels 		return cmp;
 98 b3fb4686 2020-09-20 neels 	if (left_len == right_len)
 99 b3fb4686 2020-09-20 neels 		return 0;
100 b3fb4686 2020-09-20 neels 	return (left_len > right_len) ? 1 : -1;
101 b3fb4686 2020-09-20 neels }
102 b3fb4686 2020-09-20 neels 
103 b3fb4686 2020-09-20 neels int
104 b3fb4686 2020-09-20 neels diff_atom_cmp(int *cmp,
105 b3fb4686 2020-09-20 neels 	      const struct diff_atom *left,
106 b3fb4686 2020-09-20 neels 	      const struct diff_atom *right)
107 b3fb4686 2020-09-20 neels {
108 c6eecea3 2020-07-26 stsp 	off_t remain_left, remain_right;
109 00d5652b 2020-09-22 stsp 	int flags = (left->d->root->diff_flags | right->d->root->diff_flags);
110 00d5652b 2020-09-22 stsp 	bool ignore_whitespace = (flags & DIFF_FLAG_IGNORE_WHITESPACE);
111 c6eecea3 2020-07-26 stsp 
112 732e8ee0 2020-09-20 stsp 	if (!ignore_whitespace) {
113 732e8ee0 2020-09-20 stsp 		if (!left->len && !right->len) {
114 732e8ee0 2020-09-20 stsp 			*cmp = 0;
115 732e8ee0 2020-09-20 stsp 			return 0;
116 732e8ee0 2020-09-20 stsp 		}
117 732e8ee0 2020-09-20 stsp 		if (!right->len) {
118 732e8ee0 2020-09-20 stsp 			*cmp = 1;
119 732e8ee0 2020-09-20 stsp 			return 0;
120 732e8ee0 2020-09-20 stsp 		}
121 732e8ee0 2020-09-20 stsp 		if (!left->len) {
122 732e8ee0 2020-09-20 stsp 			*cmp = -1;
123 732e8ee0 2020-09-20 stsp 			return 0;
124 732e8ee0 2020-09-20 stsp 		}
125 b3fb4686 2020-09-20 neels 	}
126 c6eecea3 2020-07-26 stsp 
127 b3fb4686 2020-09-20 neels 	if (left->at != NULL && right->at != NULL) {
128 732e8ee0 2020-09-20 stsp 		*cmp = buf_cmp(left->at, left->len, right->at, right->len,
129 732e8ee0 2020-09-20 stsp 		    ignore_whitespace);
130 b3fb4686 2020-09-20 neels 		return 0;
131 b3fb4686 2020-09-20 neels 	}
132 c6eecea3 2020-07-26 stsp 
133 c6eecea3 2020-07-26 stsp 	remain_left = left->len;
134 c6eecea3 2020-07-26 stsp 	remain_right = right->len;
135 c6eecea3 2020-07-26 stsp 	while (remain_left > 0 || remain_right > 0) {
136 c6eecea3 2020-07-26 stsp 		const size_t chunksz = 8192;
137 c6eecea3 2020-07-26 stsp 		unsigned char buf_left[chunksz], buf_right[chunksz];
138 c6eecea3 2020-07-26 stsp 		const uint8_t *p_left, *p_right;
139 c6eecea3 2020-07-26 stsp 		off_t n_left, n_right;
140 c6eecea3 2020-07-26 stsp 		ssize_t r;
141 c6eecea3 2020-07-26 stsp 
142 b3fb4686 2020-09-20 neels 		if (!remain_right) {
143 b3fb4686 2020-09-20 neels 			*cmp = 1;
144 b3fb4686 2020-09-20 neels 			return 0;
145 b3fb4686 2020-09-20 neels 		}
146 b3fb4686 2020-09-20 neels 		if (!remain_left) {
147 b3fb4686 2020-09-20 neels 			*cmp = -1;
148 b3fb4686 2020-09-20 neels 			return 0;
149 b3fb4686 2020-09-20 neels 		}
150 b3fb4686 2020-09-20 neels 
151 c6eecea3 2020-07-26 stsp 		n_left = MIN(chunksz, remain_left);
152 c6eecea3 2020-07-26 stsp 		n_right = MIN(chunksz, remain_right);
153 c6eecea3 2020-07-26 stsp 
154 c6eecea3 2020-07-26 stsp 		if (left->at == NULL) {
155 7a54ad3a 2020-09-20 stsp 			r = read_at(left->d->root->f,
156 b3fb4686 2020-09-20 neels 				    left->pos + (left->len - remain_left),
157 b3fb4686 2020-09-20 neels 				    buf_left, n_left);
158 b3fb4686 2020-09-20 neels 			if (r) {
159 b3fb4686 2020-09-20 neels 				*cmp = 0;
160 b3fb4686 2020-09-20 neels 				return r;
161 b3fb4686 2020-09-20 neels 			}
162 c6eecea3 2020-07-26 stsp 			p_left = buf_left;
163 c6eecea3 2020-07-26 stsp 		} else {
164 c6eecea3 2020-07-26 stsp 			p_left = left->at + (left->len - remain_left);
165 c6eecea3 2020-07-26 stsp 		}
166 c6eecea3 2020-07-26 stsp 
167 c6eecea3 2020-07-26 stsp 		if (right->at == NULL) {
168 7a54ad3a 2020-09-20 stsp 			r = read_at(right->d->root->f,
169 b3fb4686 2020-09-20 neels 				    right->pos + (right->len - remain_right),
170 b3fb4686 2020-09-20 neels 				    buf_right, n_right);
171 b3fb4686 2020-09-20 neels 			if (r) {
172 b3fb4686 2020-09-20 neels 				*cmp = 0;
173 b3fb4686 2020-09-20 neels 				return r;
174 b3fb4686 2020-09-20 neels 			}
175 c6eecea3 2020-07-26 stsp 			p_right = buf_right;
176 c6eecea3 2020-07-26 stsp 		} else {
177 c6eecea3 2020-07-26 stsp 			p_right = right->at + (right->len - remain_right);
178 c6eecea3 2020-07-26 stsp 		}
179 b3fb4686 2020-09-20 neels 
180 732e8ee0 2020-09-20 stsp 		r = buf_cmp(p_left, n_left, p_right, n_right,
181 732e8ee0 2020-09-20 stsp 		    ignore_whitespace);
182 b3fb4686 2020-09-20 neels 		if (r) {
183 b3fb4686 2020-09-20 neels 			*cmp = r;
184 b3fb4686 2020-09-20 neels 			return 0;
185 c6eecea3 2020-07-26 stsp 		}
186 c6eecea3 2020-07-26 stsp 
187 c6eecea3 2020-07-26 stsp 		remain_left -= n_left;
188 c6eecea3 2020-07-26 stsp 		remain_right -= n_right;
189 c6eecea3 2020-07-26 stsp 	}
190 3b0f3d61 2020-01-22 neels 
191 b3fb4686 2020-09-20 neels 	*cmp = 0;
192 b3fb4686 2020-09-20 neels 	return 0;
193 b3fb4686 2020-09-20 neels }
194 b3fb4686 2020-09-20 neels 
195 b3fb4686 2020-09-20 neels int
196 b3fb4686 2020-09-20 neels diff_atom_same(bool *same,
197 b3fb4686 2020-09-20 neels 	       const struct diff_atom *left,
198 b3fb4686 2020-09-20 neels 	       const struct diff_atom *right)
199 b3fb4686 2020-09-20 neels {
200 b3fb4686 2020-09-20 neels 	int cmp;
201 b3fb4686 2020-09-20 neels 	int r = diff_atom_cmp(&cmp, left, right);
202 b3fb4686 2020-09-20 neels 	if (r) {
203 b3fb4686 2020-09-20 neels 		*same = true;
204 b3fb4686 2020-09-20 neels 		return r;
205 b3fb4686 2020-09-20 neels 	}
206 b3fb4686 2020-09-20 neels 	*same = (cmp == 0);
207 b3fb4686 2020-09-20 neels 	return 0;
208 c6eecea3 2020-07-26 stsp }
209 c6eecea3 2020-07-26 stsp 
210 93f8150a 2020-10-11 neels static struct diff_chunk *
211 93f8150a 2020-10-11 neels diff_state_add_solved_chunk(struct diff_state *state,
212 93f8150a 2020-10-11 neels 			    const struct diff_chunk *chunk)
213 3b0f3d61 2020-01-22 neels {
214 93f8150a 2020-10-11 neels 	diff_chunk_arraylist_t *result;
215 8546b045 2020-09-20 neels 	struct diff_chunk *new_chunk;
216 8546b045 2020-09-20 neels 	enum diff_chunk_type last_t;
217 8546b045 2020-09-20 neels 	enum diff_chunk_type new_t;
218 8546b045 2020-09-20 neels 
219 8546b045 2020-09-20 neels 	/* Append to solved chunks; make sure that adjacent chunks of same type are combined, and that a minus chunk
220 8546b045 2020-09-20 neels 	 * never directly follows a plus chunk. */
221 8546b045 2020-09-20 neels 	result = &state->result->chunks;
222 8546b045 2020-09-20 neels 
223 8546b045 2020-09-20 neels 	last_t = diff_chunk_type(&result->head[result->len - 1]);
224 93f8150a 2020-10-11 neels 	new_t = diff_chunk_type(chunk);
225 8546b045 2020-09-20 neels 
226 93f8150a 2020-10-11 neels 	debug("Add %s chunk:\n", chunk->solved ? "solved" : "UNSOLVED");
227 93f8150a 2020-10-11 neels 	debug("L\n");
228 93f8150a 2020-10-11 neels 	debug_dump_atoms(&state->left, chunk->left_start, chunk->left_count);
229 93f8150a 2020-10-11 neels 	debug("R\n");
230 93f8150a 2020-10-11 neels 	debug_dump_atoms(&state->right, chunk->right_start, chunk->right_count);
231 93f8150a 2020-10-11 neels 
232 8546b045 2020-09-20 neels 	if (new_t == last_t) {
233 8546b045 2020-09-20 neels 		new_chunk = &result->head[result->len - 1];
234 93f8150a 2020-10-11 neels 		new_chunk->left_count += chunk->left_count;
235 93f8150a 2020-10-11 neels 		new_chunk->right_count += chunk->right_count;
236 bb867e68 2020-10-11 neels 		debug("  - added chunk touches previous one of same type, joined:\n");
237 bb867e68 2020-10-11 neels 		debug("L\n");
238 bb867e68 2020-10-11 neels 		debug_dump_atoms(&state->left, new_chunk->left_start, new_chunk->left_count);
239 bb867e68 2020-10-11 neels 		debug("R\n");
240 bb867e68 2020-10-11 neels 		debug_dump_atoms(&state->right, new_chunk->right_start, new_chunk->right_count);
241 8546b045 2020-09-20 neels 	} else if (last_t == CHUNK_PLUS && new_t == CHUNK_MINUS) {
242 93f8150a 2020-10-11 neels 		enum diff_chunk_type prev_last_t =
243 93f8150a 2020-10-11 neels 			result->len > 1 ?
244 93f8150a 2020-10-11 neels 				diff_chunk_type(&result->head[result->len - 2])
245 93f8150a 2020-10-11 neels 				: CHUNK_EMPTY;
246 93f8150a 2020-10-11 neels 		/* If a minus-chunk follows a plus-chunk, place it above the plus-chunk->
247 8546b045 2020-09-20 neels 		 * Is the one before that also a minus? combine. */
248 8546b045 2020-09-20 neels 		if (prev_last_t == CHUNK_MINUS) {
249 8546b045 2020-09-20 neels 			new_chunk = &result->head[result->len - 2];
250 93f8150a 2020-10-11 neels 			new_chunk->left_count += chunk->left_count;
251 93f8150a 2020-10-11 neels 			new_chunk->right_count += chunk->right_count;
252 bb867e68 2020-10-11 neels 
253 bb867e68 2020-10-11 neels 			debug("  - added minus-chunk follows plus-chunk,"
254 bb867e68 2020-10-11 neels 			      " put before that plus-chunk and joined"
255 bb867e68 2020-10-11 neels 			      " with preceding minus-chunk:\n");
256 bb867e68 2020-10-11 neels 			debug("L\n");
257 bb867e68 2020-10-11 neels 			debug_dump_atoms(&state->left, new_chunk->left_start, new_chunk->left_count);
258 bb867e68 2020-10-11 neels 			debug("R\n");
259 bb867e68 2020-10-11 neels 			debug_dump_atoms(&state->right, new_chunk->right_start, new_chunk->right_count);
260 8546b045 2020-09-20 neels 		} else {
261 724967e9 2020-10-11 neels 			ARRAYLIST_INSERT(new_chunk, *result, result->len - 1);
262 8546b045 2020-09-20 neels 			if (!new_chunk)
263 8546b045 2020-09-20 neels 				return NULL;
264 93f8150a 2020-10-11 neels 			*new_chunk = *chunk;
265 bb867e68 2020-10-11 neels 
266 bb867e68 2020-10-11 neels 			debug("  - added minus-chunk follows plus-chunk,"
267 bb867e68 2020-10-11 neels 			      " put before that plus-chunk\n");
268 8546b045 2020-09-20 neels 		}
269 8546b045 2020-09-20 neels 	} else {
270 8546b045 2020-09-20 neels 		ARRAYLIST_ADD(new_chunk, *result);
271 8546b045 2020-09-20 neels 		if (!new_chunk)
272 8546b045 2020-09-20 neels 			return NULL;
273 93f8150a 2020-10-11 neels 		*new_chunk = *chunk;
274 93f8150a 2020-10-11 neels 	}
275 93f8150a 2020-10-11 neels 	return new_chunk;
276 93f8150a 2020-10-11 neels }
277 93f8150a 2020-10-11 neels 
278 93f8150a 2020-10-11 neels /* Even if a left or right side is empty, diff output may need to know the
279 93f8150a 2020-10-11 neels  * position in that file.
280 93f8150a 2020-10-11 neels  * So left_start or right_start must never be NULL -- pass left_count or
281 93f8150a 2020-10-11 neels  * right_count as zero to indicate staying at that position without consuming
282 93f8150a 2020-10-11 neels  * any lines. */
283 93f8150a 2020-10-11 neels struct diff_chunk *
284 93f8150a 2020-10-11 neels diff_state_add_chunk(struct diff_state *state, bool solved,
285 93f8150a 2020-10-11 neels 		     struct diff_atom *left_start, unsigned int left_count,
286 93f8150a 2020-10-11 neels 		     struct diff_atom *right_start, unsigned int right_count)
287 93f8150a 2020-10-11 neels {
288 93f8150a 2020-10-11 neels 	diff_chunk_arraylist_t *result = NULL;
289 93f8150a 2020-10-11 neels 	struct diff_chunk *new_chunk;
290 93f8150a 2020-10-11 neels 	struct diff_chunk chunk = {
291 93f8150a 2020-10-11 neels 		.solved = solved,
292 93f8150a 2020-10-11 neels 		.left_start = left_start,
293 93f8150a 2020-10-11 neels 		.left_count = left_count,
294 93f8150a 2020-10-11 neels 		.right_start = right_start,
295 93f8150a 2020-10-11 neels 		.right_count = right_count,
296 93f8150a 2020-10-11 neels 	};
297 93f8150a 2020-10-11 neels 
298 93f8150a 2020-10-11 neels 	if (!solved || state->temp_result.len) {
299 93f8150a 2020-10-11 neels 		/* Append to temp_result */
300 93f8150a 2020-10-11 neels 		debug("append to temp_result\n");
301 93f8150a 2020-10-11 neels 		result = &state->temp_result;
302 93f8150a 2020-10-11 neels 	} else if (!state->result->chunks.len) {
303 93f8150a 2020-10-11 neels 		/* Append to final result */
304 93f8150a 2020-10-11 neels 		debug("first chunk\n");
305 93f8150a 2020-10-11 neels 		result = &state->result->chunks;
306 93f8150a 2020-10-11 neels 	}
307 93f8150a 2020-10-11 neels 	if (result) {
308 93f8150a 2020-10-11 neels 		ARRAYLIST_ADD(new_chunk, *result);
309 93f8150a 2020-10-11 neels 		if (!new_chunk)
310 93f8150a 2020-10-11 neels 			return NULL;
311 8546b045 2020-09-20 neels 		*new_chunk = chunk;
312 93f8150a 2020-10-11 neels 		return new_chunk;
313 8546b045 2020-09-20 neels 	}
314 8546b045 2020-09-20 neels 
315 93f8150a 2020-10-11 neels 	return diff_state_add_solved_chunk(state, &chunk);
316 3b0f3d61 2020-01-22 neels }
317 3b0f3d61 2020-01-22 neels 
318 61a7b578 2020-05-06 neels void
319 7a54ad3a 2020-09-20 stsp diff_data_init_root(struct diff_data *d, FILE *f, const uint8_t *data,
320 00d5652b 2020-09-22 stsp     unsigned long long len, int diff_flags)
321 3b0f3d61 2020-01-22 neels {
322 3b0f3d61 2020-01-22 neels 	*d = (struct diff_data){
323 7a54ad3a 2020-09-20 stsp 		.f = f,
324 c6eecea3 2020-07-26 stsp 		.pos = 0,
325 3b0f3d61 2020-01-22 neels 		.data = data,
326 3b0f3d61 2020-01-22 neels 		.len = len,
327 3b0f3d61 2020-01-22 neels 		.root = d,
328 00d5652b 2020-09-22 stsp 		.diff_flags = diff_flags,
329 3b0f3d61 2020-01-22 neels 	};
330 3b0f3d61 2020-01-22 neels }
331 3b0f3d61 2020-01-22 neels 
332 61a7b578 2020-05-06 neels void
333 61a7b578 2020-05-06 neels diff_data_init_subsection(struct diff_data *d, struct diff_data *parent,
334 61a7b578 2020-05-06 neels 			  struct diff_atom *from_atom, unsigned int atoms_count)
335 3b0f3d61 2020-01-22 neels {
336 05b5f01f 2020-09-21 stsp 	struct diff_atom *last_atom;
337 05b5f01f 2020-09-21 stsp 
338 05b5f01f 2020-09-21 stsp 	if (atoms_count == 0) {
339 05b5f01f 2020-09-21 stsp 		*d = (struct diff_data){
340 05b5f01f 2020-09-21 stsp 			.f = NULL,
341 05b5f01f 2020-09-21 stsp 			.pos = 0,
342 05b5f01f 2020-09-21 stsp 			.data = "",
343 05b5f01f 2020-09-21 stsp 			.len = 0,
344 05b5f01f 2020-09-21 stsp 			.root = parent->root,
345 05b5f01f 2020-09-21 stsp 			.atoms.head = NULL,
346 05b5f01f 2020-09-21 stsp 			.atoms.len = atoms_count,
347 05b5f01f 2020-09-21 stsp 		};
348 05b5f01f 2020-09-21 stsp 
349 05b5f01f 2020-09-21 stsp 		return;
350 05b5f01f 2020-09-21 stsp 	}
351 05b5f01f 2020-09-21 stsp 
352 05b5f01f 2020-09-21 stsp 	last_atom = from_atom + atoms_count - 1;
353 3b0f3d61 2020-01-22 neels 	*d = (struct diff_data){
354 7a54ad3a 2020-09-20 stsp 		.f = NULL,
355 c6eecea3 2020-07-26 stsp 		.pos = from_atom->pos,
356 3b0f3d61 2020-01-22 neels 		.data = from_atom->at,
357 c6eecea3 2020-07-26 stsp 		.len = (last_atom->pos + last_atom->len) - from_atom->pos,
358 3b0f3d61 2020-01-22 neels 		.root = parent->root,
359 3b0f3d61 2020-01-22 neels 		.atoms.head = from_atom,
360 3b0f3d61 2020-01-22 neels 		.atoms.len = atoms_count,
361 3b0f3d61 2020-01-22 neels 	};
362 3b0f3d61 2020-01-22 neels 
363 3b0f3d61 2020-01-22 neels 	debug("subsection:\n");
364 3b0f3d61 2020-01-22 neels 	debug_dump(d);
365 3b0f3d61 2020-01-22 neels }
366 3b0f3d61 2020-01-22 neels 
367 61a7b578 2020-05-06 neels void
368 61a7b578 2020-05-06 neels diff_data_free(struct diff_data *diff_data)
369 3b0f3d61 2020-01-22 neels {
370 3b0f3d61 2020-01-22 neels 	if (!diff_data)
371 3b0f3d61 2020-01-22 neels 		return;
372 3b0f3d61 2020-01-22 neels 	if (diff_data->atoms.allocated)
373 3b0f3d61 2020-01-22 neels 		ARRAYLIST_FREE(diff_data->atoms);
374 3b0f3d61 2020-01-22 neels }
375 3b0f3d61 2020-01-22 neels 
376 3e6cba3a 2020-08-13 stsp int
377 0d27172a 2020-05-06 neels diff_algo_none(const struct diff_algo_config *algo_config,
378 0d27172a 2020-05-06 neels 	       struct diff_state *state)
379 3b0f3d61 2020-01-22 neels {
380 3b0f3d61 2020-01-22 neels 	debug("\n** %s\n", __func__);
381 3b0f3d61 2020-01-22 neels 	debug("left:\n");
382 3b0f3d61 2020-01-22 neels 	debug_dump(&state->left);
383 3b0f3d61 2020-01-22 neels 	debug("right:\n");
384 3b0f3d61 2020-01-22 neels 	debug_dump(&state->right);
385 0d27172a 2020-05-06 neels 	debug_dump_myers_graph(&state->left, &state->right, NULL, NULL, 0, NULL,
386 0d27172a 2020-05-06 neels 			       0);
387 3b0f3d61 2020-01-22 neels 
388 3b0f3d61 2020-01-22 neels 	/* Add a chunk of equal lines, if any */
389 467a993d 2020-10-11 neels 	struct diff_atom *l = state->left.atoms.head;
390 467a993d 2020-10-11 neels 	unsigned int l_len = state->left.atoms.len;
391 467a993d 2020-10-11 neels 	struct diff_atom *r = state->right.atoms.head;
392 467a993d 2020-10-11 neels 	unsigned int r_len = state->right.atoms.len;
393 41ff30f3 2020-10-11 neels 	unsigned int equal_atoms_start = 0;
394 2146cf12 2020-10-11 neels 	unsigned int equal_atoms_end = 0;
395 13497fff 2020-10-11 neels 	unsigned int l_idx = 0;
396 13497fff 2020-10-11 neels 	unsigned int r_idx = 0;
397 467a993d 2020-10-11 neels 
398 41ff30f3 2020-10-11 neels 	while (equal_atoms_start < l_len
399 41ff30f3 2020-10-11 neels 	       && equal_atoms_start < r_len) {
400 467a993d 2020-10-11 neels 		int err;
401 b3fb4686 2020-09-20 neels 		bool same;
402 41ff30f3 2020-10-11 neels 		err = diff_atom_same(&same, &l[equal_atoms_start],
403 41ff30f3 2020-10-11 neels 				   &r[equal_atoms_start]);
404 467a993d 2020-10-11 neels 		if (err)
405 467a993d 2020-10-11 neels 			return err;
406 b3fb4686 2020-09-20 neels 		if (!same)
407 b3fb4686 2020-09-20 neels 			break;
408 41ff30f3 2020-10-11 neels 		equal_atoms_start++;
409 b3fb4686 2020-09-20 neels 	}
410 2146cf12 2020-10-11 neels 	while (equal_atoms_end < (l_len - equal_atoms_start)
411 2146cf12 2020-10-11 neels 	       && equal_atoms_end < (r_len - equal_atoms_start)) {
412 2146cf12 2020-10-11 neels 		int err;
413 2146cf12 2020-10-11 neels 		bool same;
414 2146cf12 2020-10-11 neels 		err = diff_atom_same(&same, &l[l_len - 1 - equal_atoms_end],
415 2146cf12 2020-10-11 neels 				   &r[r_len - 1 - equal_atoms_end]);
416 2146cf12 2020-10-11 neels 		if (err)
417 2146cf12 2020-10-11 neels 			return err;
418 2146cf12 2020-10-11 neels 		if (!same)
419 2146cf12 2020-10-11 neels 			break;
420 2146cf12 2020-10-11 neels 		equal_atoms_end++;
421 2146cf12 2020-10-11 neels 	}
422 2146cf12 2020-10-11 neels 
423 2146cf12 2020-10-11 neels 	/* Add a chunk of equal lines at the start */
424 41ff30f3 2020-10-11 neels 	if (equal_atoms_start) {
425 3b0f3d61 2020-01-22 neels 		if (!diff_state_add_chunk(state, true,
426 467a993d 2020-10-11 neels 					  &l[0],
427 41ff30f3 2020-10-11 neels 					  equal_atoms_start,
428 467a993d 2020-10-11 neels 					  &r[0],
429 41ff30f3 2020-10-11 neels 					  equal_atoms_start))
430 3e6cba3a 2020-08-13 stsp 			return ENOMEM;
431 13497fff 2020-10-11 neels 		l_idx += equal_atoms_start;
432 13497fff 2020-10-11 neels 		r_idx += equal_atoms_start;
433 3b0f3d61 2020-01-22 neels 	}
434 3b0f3d61 2020-01-22 neels 
435 3b0f3d61 2020-01-22 neels 	/* Add a "minus" chunk with all lines from the left. */
436 2146cf12 2020-10-11 neels 	if (equal_atoms_start + equal_atoms_end < l_len) {
437 13497fff 2020-10-11 neels 		unsigned int add_len = l_len - equal_atoms_start - equal_atoms_end;
438 3b0f3d61 2020-01-22 neels 		if (!diff_state_add_chunk(state, true,
439 13497fff 2020-10-11 neels 					  &l[l_idx], add_len,
440 13497fff 2020-10-11 neels 					  &r[r_idx], 0))
441 13497fff 2020-10-11 neels 			return ENOMEM;
442 13497fff 2020-10-11 neels 		l_idx += add_len;
443 3b0f3d61 2020-01-22 neels 	}
444 3b0f3d61 2020-01-22 neels 
445 3b0f3d61 2020-01-22 neels 	/* Add a "plus" chunk with all lines from the right. */
446 2146cf12 2020-10-11 neels 	if (equal_atoms_start + equal_atoms_end < r_len) {
447 13497fff 2020-10-11 neels 		unsigned int add_len = r_len - equal_atoms_start - equal_atoms_end;
448 3b0f3d61 2020-01-22 neels 		if (!diff_state_add_chunk(state, true,
449 13497fff 2020-10-11 neels 					  &l[equal_atoms_start], 0,
450 13497fff 2020-10-11 neels 					  &r[equal_atoms_start], add_len))
451 13497fff 2020-10-11 neels 			return ENOMEM;
452 13497fff 2020-10-11 neels 		r_idx += add_len;
453 3b0f3d61 2020-01-22 neels 	}
454 2146cf12 2020-10-11 neels 
455 2146cf12 2020-10-11 neels 	/* Add a chunk of equal lines at the end */
456 2146cf12 2020-10-11 neels 	if (equal_atoms_end) {
457 2146cf12 2020-10-11 neels 		if (!diff_state_add_chunk(state, true,
458 13497fff 2020-10-11 neels 					  &l[l_idx], equal_atoms_end,
459 13497fff 2020-10-11 neels 					  &r[r_idx], equal_atoms_end))
460 2146cf12 2020-10-11 neels 			return ENOMEM;
461 2146cf12 2020-10-11 neels 	}
462 2146cf12 2020-10-11 neels 
463 3b0f3d61 2020-01-22 neels 	return DIFF_RC_OK;
464 3b0f3d61 2020-01-22 neels }
465 3b0f3d61 2020-01-22 neels 
466 3e6cba3a 2020-08-13 stsp int
467 0d27172a 2020-05-06 neels diff_run_algo(const struct diff_algo_config *algo_config,
468 0d27172a 2020-05-06 neels 	      struct diff_state *state)
469 3b0f3d61 2020-01-22 neels {
470 3e6cba3a 2020-08-13 stsp 	int rc;
471 3b0f3d61 2020-01-22 neels 	ARRAYLIST_FREE(state->temp_result);
472 3b0f3d61 2020-01-22 neels 
473 0d27172a 2020-05-06 neels 	if (!algo_config || !algo_config->impl
474 0d27172a 2020-05-06 neels 	    || !state->recursion_depth_left) {
475 3b0f3d61 2020-01-22 neels 		debug("MAX RECURSION REACHED, just dumping diff chunks\n");
476 3b0f3d61 2020-01-22 neels 		return diff_algo_none(algo_config, state);
477 3b0f3d61 2020-01-22 neels 	}
478 3b0f3d61 2020-01-22 neels 
479 3b0f3d61 2020-01-22 neels 	ARRAYLIST_INIT(state->temp_result, DIFF_RESULT_ALLOC_BLOCKSIZE);
480 3b0f3d61 2020-01-22 neels 	rc = algo_config->impl(algo_config, state);
481 3b0f3d61 2020-01-22 neels 	switch (rc) {
482 3b0f3d61 2020-01-22 neels 	case DIFF_RC_USE_DIFF_ALGO_FALLBACK:
483 0d27172a 2020-05-06 neels 		debug("Got DIFF_RC_USE_DIFF_ALGO_FALLBACK (%p)\n",
484 0d27172a 2020-05-06 neels 		      algo_config->fallback_algo);
485 3b0f3d61 2020-01-22 neels 		rc = diff_run_algo(algo_config->fallback_algo, state);
486 3b0f3d61 2020-01-22 neels 		goto return_rc;
487 3b0f3d61 2020-01-22 neels 
488 3b0f3d61 2020-01-22 neels 	case DIFF_RC_OK:
489 3b0f3d61 2020-01-22 neels 		/* continue below */
490 3b0f3d61 2020-01-22 neels 		break;
491 3b0f3d61 2020-01-22 neels 
492 3b0f3d61 2020-01-22 neels 	default:
493 3b0f3d61 2020-01-22 neels 		/* some error happened */
494 3b0f3d61 2020-01-22 neels 		goto return_rc;
495 3b0f3d61 2020-01-22 neels 	}
496 3b0f3d61 2020-01-22 neels 
497 0d27172a 2020-05-06 neels 	/* Pick up any diff chunks that are still unsolved and feed to
498 0d27172a 2020-05-06 neels 	 * inner_algo.  inner_algo will solve unsolved chunks and append to
499 0d27172a 2020-05-06 neels 	 * result, and subsequent solved chunks on this level are then appended
500 0d27172a 2020-05-06 neels 	 * to result afterwards. */
501 3b0f3d61 2020-01-22 neels 	int i;
502 3b0f3d61 2020-01-22 neels 	for (i = 0; i < state->temp_result.len; i++) {
503 3b0f3d61 2020-01-22 neels 		struct diff_chunk *c = &state->temp_result.head[i];
504 3b0f3d61 2020-01-22 neels 		if (c->solved) {
505 93f8150a 2020-10-11 neels 			diff_state_add_solved_chunk(state, c);
506 3b0f3d61 2020-01-22 neels 			continue;
507 3b0f3d61 2020-01-22 neels 		}
508 3b0f3d61 2020-01-22 neels 
509 3b0f3d61 2020-01-22 neels 		/* c is an unsolved chunk, feed to inner_algo */
510 3b0f3d61 2020-01-22 neels 		struct diff_state inner_state = {
511 3b0f3d61 2020-01-22 neels 			.result = state->result,
512 3b0f3d61 2020-01-22 neels 			.recursion_depth_left = state->recursion_depth_left - 1,
513 3b0f3d61 2020-01-22 neels 		};
514 0d27172a 2020-05-06 neels 		diff_data_init_subsection(&inner_state.left, &state->left,
515 0d27172a 2020-05-06 neels 					  c->left_start, c->left_count);
516 0d27172a 2020-05-06 neels 		diff_data_init_subsection(&inner_state.right, &state->right,
517 0d27172a 2020-05-06 neels 					  c->right_start, c->right_count);
518 3b0f3d61 2020-01-22 neels 
519 3b0f3d61 2020-01-22 neels 		rc = diff_run_algo(algo_config->inner_algo, &inner_state);
520 3b0f3d61 2020-01-22 neels 
521 3b0f3d61 2020-01-22 neels 		if (rc != DIFF_RC_OK)
522 3b0f3d61 2020-01-22 neels 			goto return_rc;
523 3b0f3d61 2020-01-22 neels 	}
524 3b0f3d61 2020-01-22 neels 
525 3b0f3d61 2020-01-22 neels 	rc = DIFF_RC_OK;
526 3b0f3d61 2020-01-22 neels return_rc:
527 3b0f3d61 2020-01-22 neels 	ARRAYLIST_FREE(state->temp_result);
528 3b0f3d61 2020-01-22 neels 	return rc;
529 3b0f3d61 2020-01-22 neels }
530 3b0f3d61 2020-01-22 neels 
531 61a7b578 2020-05-06 neels struct diff_result *
532 61a7b578 2020-05-06 neels diff_main(const struct diff_config *config,
533 7a54ad3a 2020-09-20 stsp 	  FILE *left_f, const uint8_t *left_data, off_t left_len,
534 7a54ad3a 2020-09-20 stsp 	  FILE *right_f, const uint8_t *right_data, off_t right_len,
535 00d5652b 2020-09-22 stsp 	  int diff_flags)
536 3b0f3d61 2020-01-22 neels {
537 3b0f3d61 2020-01-22 neels 	struct diff_result *result = malloc(sizeof(struct diff_result));
538 3b0f3d61 2020-01-22 neels 	if (!result)
539 3b0f3d61 2020-01-22 neels 		return NULL;
540 3b0f3d61 2020-01-22 neels 
541 3b0f3d61 2020-01-22 neels 	*result = (struct diff_result){};
542 7a54ad3a 2020-09-20 stsp 	diff_data_init_root(&result->left, left_f, left_data, left_len,
543 00d5652b 2020-09-22 stsp 	    diff_flags);
544 7a54ad3a 2020-09-20 stsp 	diff_data_init_root(&result->right, right_f, right_data, right_len,
545 00d5652b 2020-09-22 stsp 	    diff_flags);
546 3b0f3d61 2020-01-22 neels 
547 3b0f3d61 2020-01-22 neels 	if (!config->atomize_func) {
548 3e6cba3a 2020-08-13 stsp 		result->rc = EINVAL;
549 3b0f3d61 2020-01-22 neels 		return result;
550 3b0f3d61 2020-01-22 neels 	}
551 3b0f3d61 2020-01-22 neels 
552 0d27172a 2020-05-06 neels 	result->rc = config->atomize_func(config->atomize_func_data,
553 0d27172a 2020-05-06 neels 					  &result->left, &result->right);
554 3b0f3d61 2020-01-22 neels 	if (result->rc != DIFF_RC_OK)
555 3b0f3d61 2020-01-22 neels 		return result;
556 3b0f3d61 2020-01-22 neels 
557 3b0f3d61 2020-01-22 neels 	struct diff_state state = {
558 3b0f3d61 2020-01-22 neels 		.result = result,
559 00961134 2020-09-20 stsp 		.recursion_depth_left = config->max_recursion_depth ? : 32,
560 3b0f3d61 2020-01-22 neels 	};
561 0d27172a 2020-05-06 neels 	diff_data_init_subsection(&state.left, &result->left,
562 0d27172a 2020-05-06 neels 				  result->left.atoms.head,
563 0d27172a 2020-05-06 neels 				  result->left.atoms.len);
564 0d27172a 2020-05-06 neels 	diff_data_init_subsection(&state.right, &result->right,
565 0d27172a 2020-05-06 neels 				  result->right.atoms.head,
566 0d27172a 2020-05-06 neels 				  result->right.atoms.len);
567 3b0f3d61 2020-01-22 neels 
568 3b0f3d61 2020-01-22 neels 	result->rc = diff_run_algo(config->algo, &state);
569 3b0f3d61 2020-01-22 neels 
570 3b0f3d61 2020-01-22 neels 	return result;
571 3b0f3d61 2020-01-22 neels }
572 3b0f3d61 2020-01-22 neels 
573 61a7b578 2020-05-06 neels void
574 61a7b578 2020-05-06 neels diff_result_free(struct diff_result *result)
575 3b0f3d61 2020-01-22 neels {
576 3b0f3d61 2020-01-22 neels 	if (!result)
577 3b0f3d61 2020-01-22 neels 		return;
578 3b0f3d61 2020-01-22 neels 	diff_data_free(&result->left);
579 3b0f3d61 2020-01-22 neels 	diff_data_free(&result->right);
580 3b0f3d61 2020-01-22 neels 	ARRAYLIST_FREE(result->chunks);
581 3b0f3d61 2020-01-22 neels 	free(result);
582 3b0f3d61 2020-01-22 neels }