1 fe621944 2020-11-10 stsp /* Generic infrastructure to implement various diff algorithms (implementation). */
  2 fe621944 2020-11-10 stsp /*
  3 fe621944 2020-11-10 stsp  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
  4 fe621944 2020-11-10 stsp  *
  5 fe621944 2020-11-10 stsp  * Permission to use, copy, modify, and distribute this software for any
  6 fe621944 2020-11-10 stsp  * purpose with or without fee is hereby granted, provided that the above
  7 fe621944 2020-11-10 stsp  * copyright notice and this permission notice appear in all copies.
  8 fe621944 2020-11-10 stsp  *
  9 fe621944 2020-11-10 stsp  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 10 fe621944 2020-11-10 stsp  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 11 fe621944 2020-11-10 stsp  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 12 fe621944 2020-11-10 stsp  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 13 fe621944 2020-11-10 stsp  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 14 fe621944 2020-11-10 stsp  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 15 fe621944 2020-11-10 stsp  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 16 fe621944 2020-11-10 stsp  */
 17 fe621944 2020-11-10 stsp 
 18 fe621944 2020-11-10 stsp 
 19 8b925c6c 2022-07-16 thomas #include <sys/queue.h>
 20 fe621944 2020-11-10 stsp #include <ctype.h>
 21 fe621944 2020-11-10 stsp #include <errno.h>
 22 fe621944 2020-11-10 stsp #include <stdint.h>
 23 fe621944 2020-11-10 stsp #include <stdlib.h>
 24 fe621944 2020-11-10 stsp #include <stdbool.h>
 25 fe621944 2020-11-10 stsp #include <stdio.h>
 26 fe621944 2020-11-10 stsp #include <string.h>
 27 fe621944 2020-11-10 stsp #include <limits.h>
 28 fe621944 2020-11-10 stsp #include <unistd.h>
 29 fe621944 2020-11-10 stsp 
 30 fe621944 2020-11-10 stsp #include <assert.h>
 31 fe621944 2020-11-10 stsp 
 32 fe621944 2020-11-10 stsp #include <arraylist.h>
 33 fe621944 2020-11-10 stsp #include <diff_main.h>
 34 fe621944 2020-11-10 stsp 
 35 dd038bc6 2021-09-21 thomas.ad #include "got_compat.h"
 36 dd038bc6 2021-09-21 thomas.ad 
 37 fe621944 2020-11-10 stsp #include "diff_internal.h"
 38 fe621944 2020-11-10 stsp #include "diff_debug.h"
 39 fe621944 2020-11-10 stsp 
 40 fe621944 2020-11-10 stsp static int
 41 fe621944 2020-11-10 stsp read_at(FILE *f, off_t at_pos, unsigned char *buf, size_t len)
 42 fe621944 2020-11-10 stsp {
 43 fe621944 2020-11-10 stsp 	int r;
 44 fe621944 2020-11-10 stsp 	if (fseeko(f, at_pos, SEEK_SET) == -1)
 45 fe621944 2020-11-10 stsp 		return errno;
 46 fe621944 2020-11-10 stsp 	r = fread(buf, sizeof(char), len, f);
 47 fe621944 2020-11-10 stsp 	if ((r == 0 || r < len) && ferror(f))
 48 fe621944 2020-11-10 stsp 		return errno;
 49 fe621944 2020-11-10 stsp 	if (r != len)
 50 fe621944 2020-11-10 stsp 		return EIO;
 51 fe621944 2020-11-10 stsp 	return 0;
 52 fe621944 2020-11-10 stsp }
 53 fe621944 2020-11-10 stsp 
 54 fe621944 2020-11-10 stsp static int
 55 fe621944 2020-11-10 stsp buf_cmp(const unsigned char *left, size_t left_len,
 56 fe621944 2020-11-10 stsp 	const unsigned char *right, size_t right_len,
 57 fe621944 2020-11-10 stsp 	bool ignore_whitespace)
 58 fe621944 2020-11-10 stsp {
 59 fe621944 2020-11-10 stsp 	int cmp;
 60 fe621944 2020-11-10 stsp 
 61 fe621944 2020-11-10 stsp 	if (ignore_whitespace) {
 62 fe621944 2020-11-10 stsp 		int il = 0, ir = 0;
 63 fe621944 2020-11-10 stsp 		while (il < left_len && ir < right_len) {
 64 fe621944 2020-11-10 stsp 			unsigned char cl = left[il];
 65 fe621944 2020-11-10 stsp 			unsigned char cr = right[ir];
 66 fe621944 2020-11-10 stsp 
 67 fe621944 2020-11-10 stsp 			if (isspace(cl) && il < left_len) {
 68 fe621944 2020-11-10 stsp 				il++;
 69 fe621944 2020-11-10 stsp 				continue;
 70 fe621944 2020-11-10 stsp 			}
 71 fe621944 2020-11-10 stsp 			if (isspace(cr) && ir < right_len) {
 72 fe621944 2020-11-10 stsp 				ir++;
 73 fe621944 2020-11-10 stsp 				continue;
 74 fe621944 2020-11-10 stsp 			}
 75 fe621944 2020-11-10 stsp 
 76 fe621944 2020-11-10 stsp 			if (cl > cr)
 77 fe621944 2020-11-10 stsp 				return 1;
 78 fe621944 2020-11-10 stsp 			if (cr > cl)
 79 fe621944 2020-11-10 stsp 				return -1;
 80 fe621944 2020-11-10 stsp 			il++;
 81 fe621944 2020-11-10 stsp 			ir++;
 82 fe621944 2020-11-10 stsp 		}
 83 fe621944 2020-11-10 stsp 		while (il < left_len) {
 84 fe621944 2020-11-10 stsp 			unsigned char cl = left[il++];
 85 fe621944 2020-11-10 stsp 			if (!isspace(cl))
 86 fe621944 2020-11-10 stsp 				return 1;
 87 fe621944 2020-11-10 stsp 		}
 88 fe621944 2020-11-10 stsp 		while (ir < right_len) {
 89 fe621944 2020-11-10 stsp 			unsigned char cr = right[ir++];
 90 fe621944 2020-11-10 stsp 			if (!isspace(cr))
 91 fe621944 2020-11-10 stsp 				return -1;
 92 fe621944 2020-11-10 stsp 		}
 93 fe621944 2020-11-10 stsp 
 94 fe621944 2020-11-10 stsp 		return 0;
 95 fe621944 2020-11-10 stsp 	}
 96 fe621944 2020-11-10 stsp 
 97 fe621944 2020-11-10 stsp 	cmp = memcmp(left, right, MIN(left_len, right_len));
 98 fe621944 2020-11-10 stsp 	if (cmp)
 99 fe621944 2020-11-10 stsp 		return cmp;
100 fe621944 2020-11-10 stsp 	if (left_len == right_len)
101 fe621944 2020-11-10 stsp 		return 0;
102 fe621944 2020-11-10 stsp 	return (left_len > right_len) ? 1 : -1;
103 fe621944 2020-11-10 stsp }
104 fe621944 2020-11-10 stsp 
105 fe621944 2020-11-10 stsp int
106 fe621944 2020-11-10 stsp diff_atom_cmp(int *cmp,
107 fe621944 2020-11-10 stsp 	      const struct diff_atom *left,
108 fe621944 2020-11-10 stsp 	      const struct diff_atom *right)
109 fe621944 2020-11-10 stsp {
110 fe621944 2020-11-10 stsp 	off_t remain_left, remain_right;
111 fe621944 2020-11-10 stsp 	int flags = (left->root->diff_flags | right->root->diff_flags);
112 fe621944 2020-11-10 stsp 	bool ignore_whitespace = (flags & DIFF_FLAG_IGNORE_WHITESPACE);
113 fe621944 2020-11-10 stsp 
114 fe621944 2020-11-10 stsp 	if (!left->len && !right->len) {
115 fe621944 2020-11-10 stsp 		*cmp = 0;
116 fe621944 2020-11-10 stsp 		return 0;
117 fe621944 2020-11-10 stsp 	}
118 fe621944 2020-11-10 stsp 	if (!ignore_whitespace) {
119 fe621944 2020-11-10 stsp 		if (!right->len) {
120 fe621944 2020-11-10 stsp 			*cmp = 1;
121 fe621944 2020-11-10 stsp 			return 0;
122 fe621944 2020-11-10 stsp 		}
123 fe621944 2020-11-10 stsp 		if (!left->len) {
124 fe621944 2020-11-10 stsp 			*cmp = -1;
125 fe621944 2020-11-10 stsp 			return 0;
126 fe621944 2020-11-10 stsp 		}
127 fe621944 2020-11-10 stsp 	}
128 fe621944 2020-11-10 stsp 
129 fe621944 2020-11-10 stsp 	if (left->at != NULL && right->at != NULL) {
130 fe621944 2020-11-10 stsp 		*cmp = buf_cmp(left->at, left->len, right->at, right->len,
131 fe621944 2020-11-10 stsp 		    ignore_whitespace);
132 fe621944 2020-11-10 stsp 		return 0;
133 fe621944 2020-11-10 stsp 	}
134 fe621944 2020-11-10 stsp 
135 fe621944 2020-11-10 stsp 	remain_left = left->len;
136 fe621944 2020-11-10 stsp 	remain_right = right->len;
137 fe621944 2020-11-10 stsp 	while (remain_left > 0 || remain_right > 0) {
138 fe621944 2020-11-10 stsp 		const size_t chunksz = 8192;
139 fe621944 2020-11-10 stsp 		unsigned char buf_left[chunksz], buf_right[chunksz];
140 fe621944 2020-11-10 stsp 		const uint8_t *p_left, *p_right;
141 fe621944 2020-11-10 stsp 		off_t n_left, n_right;
142 fe621944 2020-11-10 stsp 		ssize_t r;
143 fe621944 2020-11-10 stsp 
144 fe621944 2020-11-10 stsp 		if (!remain_right) {
145 fe621944 2020-11-10 stsp 			*cmp = 1;
146 fe621944 2020-11-10 stsp 			return 0;
147 fe621944 2020-11-10 stsp 		}
148 fe621944 2020-11-10 stsp 		if (!remain_left) {
149 fe621944 2020-11-10 stsp 			*cmp = -1;
150 fe621944 2020-11-10 stsp 			return 0;
151 fe621944 2020-11-10 stsp 		}
152 fe621944 2020-11-10 stsp 
153 fe621944 2020-11-10 stsp 		n_left = MIN(chunksz, remain_left);
154 fe621944 2020-11-10 stsp 		n_right = MIN(chunksz, remain_right);
155 fe621944 2020-11-10 stsp 
156 fe621944 2020-11-10 stsp 		if (left->at == NULL) {
157 fe621944 2020-11-10 stsp 			r = read_at(left->root->f,
158 fe621944 2020-11-10 stsp 				    left->pos + (left->len - remain_left),
159 fe621944 2020-11-10 stsp 				    buf_left, n_left);
160 fe621944 2020-11-10 stsp 			if (r) {
161 fe621944 2020-11-10 stsp 				*cmp = 0;
162 fe621944 2020-11-10 stsp 				return r;
163 fe621944 2020-11-10 stsp 			}
164 fe621944 2020-11-10 stsp 			p_left = buf_left;
165 fe621944 2020-11-10 stsp 		} else {
166 fe621944 2020-11-10 stsp 			p_left = left->at + (left->len - remain_left);
167 fe621944 2020-11-10 stsp 		}
168 fe621944 2020-11-10 stsp 
169 fe621944 2020-11-10 stsp 		if (right->at == NULL) {
170 fe621944 2020-11-10 stsp 			r = read_at(right->root->f,
171 fe621944 2020-11-10 stsp 				    right->pos + (right->len - remain_right),
172 fe621944 2020-11-10 stsp 				    buf_right, n_right);
173 fe621944 2020-11-10 stsp 			if (r) {
174 fe621944 2020-11-10 stsp 				*cmp = 0;
175 fe621944 2020-11-10 stsp 				return r;
176 fe621944 2020-11-10 stsp 			}
177 fe621944 2020-11-10 stsp 			p_right = buf_right;
178 fe621944 2020-11-10 stsp 		} else {
179 fe621944 2020-11-10 stsp 			p_right = right->at + (right->len - remain_right);
180 fe621944 2020-11-10 stsp 		}
181 fe621944 2020-11-10 stsp 
182 fe621944 2020-11-10 stsp 		r = buf_cmp(p_left, n_left, p_right, n_right,
183 fe621944 2020-11-10 stsp 		    ignore_whitespace);
184 fe621944 2020-11-10 stsp 		if (r) {
185 fe621944 2020-11-10 stsp 			*cmp = r;
186 fe621944 2020-11-10 stsp 			return 0;
187 fe621944 2020-11-10 stsp 		}
188 fe621944 2020-11-10 stsp 
189 fe621944 2020-11-10 stsp 		remain_left -= n_left;
190 fe621944 2020-11-10 stsp 		remain_right -= n_right;
191 fe621944 2020-11-10 stsp 	}
192 fe621944 2020-11-10 stsp 
193 fe621944 2020-11-10 stsp 	*cmp = 0;
194 fe621944 2020-11-10 stsp 	return 0;
195 fe621944 2020-11-10 stsp }
196 fe621944 2020-11-10 stsp 
197 fe621944 2020-11-10 stsp int
198 fe621944 2020-11-10 stsp diff_atom_same(bool *same,
199 fe621944 2020-11-10 stsp 	       const struct diff_atom *left,
200 fe621944 2020-11-10 stsp 	       const struct diff_atom *right)
201 fe621944 2020-11-10 stsp {
202 fe621944 2020-11-10 stsp 	int cmp;
203 fe621944 2020-11-10 stsp 	int r;
204 fe621944 2020-11-10 stsp 	if (left->hash != right->hash) {
205 fe621944 2020-11-10 stsp 		*same = false;
206 fe621944 2020-11-10 stsp 		return 0;
207 fe621944 2020-11-10 stsp 	}
208 fe621944 2020-11-10 stsp 	r = diff_atom_cmp(&cmp, left, right);
209 fe621944 2020-11-10 stsp 	if (r) {
210 fe621944 2020-11-10 stsp 		*same = true;
211 fe621944 2020-11-10 stsp 		return r;
212 fe621944 2020-11-10 stsp 	}
213 fe621944 2020-11-10 stsp 	*same = (cmp == 0);
214 fe621944 2020-11-10 stsp 	return 0;
215 fe621944 2020-11-10 stsp }
216 fe621944 2020-11-10 stsp 
217 fe621944 2020-11-10 stsp static struct diff_chunk *
218 fe621944 2020-11-10 stsp diff_state_add_solved_chunk(struct diff_state *state,
219 fe621944 2020-11-10 stsp 			    const struct diff_chunk *chunk)
220 fe621944 2020-11-10 stsp {
221 fe621944 2020-11-10 stsp 	diff_chunk_arraylist_t *result;
222 fe621944 2020-11-10 stsp 	struct diff_chunk *new_chunk;
223 fe621944 2020-11-10 stsp 	enum diff_chunk_type last_t;
224 fe621944 2020-11-10 stsp 	enum diff_chunk_type new_t;
225 fe621944 2020-11-10 stsp 	struct diff_chunk *last;
226 fe621944 2020-11-10 stsp 
227 fe621944 2020-11-10 stsp 	/* Append to solved chunks; make sure that adjacent chunks of same type are combined, and that a minus chunk
228 fe621944 2020-11-10 stsp 	 * never directly follows a plus chunk. */
229 fe621944 2020-11-10 stsp 	result = &state->result->chunks;
230 fe621944 2020-11-10 stsp 
231 fe621944 2020-11-10 stsp 	last_t = result->len ? diff_chunk_type(&result->head[result->len - 1])
232 fe621944 2020-11-10 stsp 		: CHUNK_EMPTY;
233 fe621944 2020-11-10 stsp 	new_t = diff_chunk_type(chunk);
234 fe621944 2020-11-10 stsp 
235 fe621944 2020-11-10 stsp 	debug("ADD %s chunk #%u:\n", chunk->solved ? "solved" : "UNSOLVED",
236 fe621944 2020-11-10 stsp 	      result->len);
237 fe621944 2020-11-10 stsp 	debug("L\n");
238 fe621944 2020-11-10 stsp 	debug_dump_atoms(&state->left, chunk->left_start, chunk->left_count);
239 fe621944 2020-11-10 stsp 	debug("R\n");
240 fe621944 2020-11-10 stsp 	debug_dump_atoms(&state->right, chunk->right_start, chunk->right_count);
241 fe621944 2020-11-10 stsp 
242 fe621944 2020-11-10 stsp 	if (result->len) {
243 fe621944 2020-11-10 stsp 		last = &result->head[result->len - 1];
244 fe621944 2020-11-10 stsp 		assert(chunk->left_start
245 fe621944 2020-11-10 stsp 		       == last->left_start + last->left_count);
246 fe621944 2020-11-10 stsp 		assert(chunk->right_start
247 fe621944 2020-11-10 stsp 		       == last->right_start + last->right_count);
248 fe621944 2020-11-10 stsp 	}
249 fe621944 2020-11-10 stsp 
250 fe621944 2020-11-10 stsp 	if (new_t == last_t) {
251 fe621944 2020-11-10 stsp 		new_chunk = &result->head[result->len - 1];
252 fe621944 2020-11-10 stsp 		new_chunk->left_count += chunk->left_count;
253 fe621944 2020-11-10 stsp 		new_chunk->right_count += chunk->right_count;
254 fe621944 2020-11-10 stsp 		debug("  - added chunk touches previous one of same type, joined:\n");
255 fe621944 2020-11-10 stsp 		debug("L\n");
256 fe621944 2020-11-10 stsp 		debug_dump_atoms(&state->left, new_chunk->left_start, new_chunk->left_count);
257 fe621944 2020-11-10 stsp 		debug("R\n");
258 fe621944 2020-11-10 stsp 		debug_dump_atoms(&state->right, new_chunk->right_start, new_chunk->right_count);
259 fe621944 2020-11-10 stsp 	} else if (last_t == CHUNK_PLUS && new_t == CHUNK_MINUS) {
260 fe621944 2020-11-10 stsp 		enum diff_chunk_type prev_last_t =
261 fe621944 2020-11-10 stsp 			result->len > 1 ?
262 fe621944 2020-11-10 stsp 				diff_chunk_type(&result->head[result->len - 2])
263 fe621944 2020-11-10 stsp 				: CHUNK_EMPTY;
264 fe621944 2020-11-10 stsp 		/* If a minus-chunk follows a plus-chunk, place it above the plus-chunk->
265 fe621944 2020-11-10 stsp 		 * Is the one before that also a minus? combine. */
266 fe621944 2020-11-10 stsp 		if (prev_last_t == CHUNK_MINUS) {
267 fe621944 2020-11-10 stsp 			new_chunk = &result->head[result->len - 2];
268 fe621944 2020-11-10 stsp 			new_chunk->left_count += chunk->left_count;
269 fe621944 2020-11-10 stsp 			new_chunk->right_count += chunk->right_count;
270 fe621944 2020-11-10 stsp 
271 fe621944 2020-11-10 stsp 			debug("  - added minus-chunk follows plus-chunk,"
272 fe621944 2020-11-10 stsp 			      " put before that plus-chunk and joined"
273 fe621944 2020-11-10 stsp 			      " with preceding minus-chunk:\n");
274 fe621944 2020-11-10 stsp 			debug("L\n");
275 fe621944 2020-11-10 stsp 			debug_dump_atoms(&state->left, new_chunk->left_start, new_chunk->left_count);
276 fe621944 2020-11-10 stsp 			debug("R\n");
277 fe621944 2020-11-10 stsp 			debug_dump_atoms(&state->right, new_chunk->right_start, new_chunk->right_count);
278 fe621944 2020-11-10 stsp 		} else {
279 fe621944 2020-11-10 stsp 			ARRAYLIST_INSERT(new_chunk, *result, result->len - 1);
280 fe621944 2020-11-10 stsp 			if (!new_chunk)
281 fe621944 2020-11-10 stsp 				return NULL;
282 fe621944 2020-11-10 stsp 			*new_chunk = *chunk;
283 fe621944 2020-11-10 stsp 
284 fe621944 2020-11-10 stsp 			/* The new minus chunk indicates to which position on
285 fe621944 2020-11-10 stsp 			 * the right it corresponds, even though it doesn't add
286 fe621944 2020-11-10 stsp 			 * any lines on the right. By moving above a plus chunk,
287 fe621944 2020-11-10 stsp 			 * that position on the right has shifted. */
288 fe621944 2020-11-10 stsp 			last = &result->head[result->len - 1];
289 fe621944 2020-11-10 stsp 			new_chunk->right_start = last->right_start;
290 fe621944 2020-11-10 stsp 
291 fe621944 2020-11-10 stsp 			debug("  - added minus-chunk follows plus-chunk,"
292 fe621944 2020-11-10 stsp 			      " put before that plus-chunk\n");
293 fe621944 2020-11-10 stsp 		}
294 fe621944 2020-11-10 stsp 
295 fe621944 2020-11-10 stsp 		/* That last_t == CHUNK_PLUS indicates to which position on the
296 fe621944 2020-11-10 stsp 		 * left it corresponds, even though it doesn't add any lines on
297 fe621944 2020-11-10 stsp 		 * the left. By inserting/extending the prev_last_t ==
298 fe621944 2020-11-10 stsp 		 * CHUNK_MINUS, that position on the left has shifted. */
299 fe621944 2020-11-10 stsp 		last = &result->head[result->len - 1];
300 fe621944 2020-11-10 stsp 		last->left_start = new_chunk->left_start
301 fe621944 2020-11-10 stsp 			+ new_chunk->left_count;
302 fe621944 2020-11-10 stsp 
303 fe621944 2020-11-10 stsp 	} else {
304 fe621944 2020-11-10 stsp 		ARRAYLIST_ADD(new_chunk, *result);
305 fe621944 2020-11-10 stsp 		if (!new_chunk)
306 fe621944 2020-11-10 stsp 			return NULL;
307 fe621944 2020-11-10 stsp 		*new_chunk = *chunk;
308 fe621944 2020-11-10 stsp 	}
309 fe621944 2020-11-10 stsp 	return new_chunk;
310 fe621944 2020-11-10 stsp }
311 fe621944 2020-11-10 stsp 
312 fe621944 2020-11-10 stsp /* Even if a left or right side is empty, diff output may need to know the
313 fe621944 2020-11-10 stsp  * position in that file.
314 fe621944 2020-11-10 stsp  * So left_start or right_start must never be NULL -- pass left_count or
315 fe621944 2020-11-10 stsp  * right_count as zero to indicate staying at that position without consuming
316 fe621944 2020-11-10 stsp  * any lines. */
317 fe621944 2020-11-10 stsp struct diff_chunk *
318 fe621944 2020-11-10 stsp diff_state_add_chunk(struct diff_state *state, bool solved,
319 fe621944 2020-11-10 stsp 		     struct diff_atom *left_start, unsigned int left_count,
320 fe621944 2020-11-10 stsp 		     struct diff_atom *right_start, unsigned int right_count)
321 fe621944 2020-11-10 stsp {
322 fe621944 2020-11-10 stsp 	struct diff_chunk *new_chunk;
323 fe621944 2020-11-10 stsp 	struct diff_chunk chunk = {
324 fe621944 2020-11-10 stsp 		.solved = solved,
325 fe621944 2020-11-10 stsp 		.left_start = left_start,
326 fe621944 2020-11-10 stsp 		.left_count = left_count,
327 fe621944 2020-11-10 stsp 		.right_start = right_start,
328 fe621944 2020-11-10 stsp 		.right_count = right_count,
329 fe621944 2020-11-10 stsp 	};
330 fe621944 2020-11-10 stsp 
331 fe621944 2020-11-10 stsp 	/* An unsolved chunk means store as intermediate result for later
332 fe621944 2020-11-10 stsp 	 * re-iteration.
333 fe621944 2020-11-10 stsp 	 * If there already are intermediate results, that means even a
334 fe621944 2020-11-10 stsp 	 * following solved chunk needs to go to intermediate results, so that
335 fe621944 2020-11-10 stsp 	 * it is later put in the final correct position in solved chunks.
336 fe621944 2020-11-10 stsp 	 */
337 fe621944 2020-11-10 stsp 	if (!solved || state->temp_result.len) {
338 fe621944 2020-11-10 stsp 		/* Append to temp_result */
339 fe621944 2020-11-10 stsp 		debug("ADD %s chunk to temp result:\n",
340 fe621944 2020-11-10 stsp 		      chunk.solved ? "solved" : "UNSOLVED");
341 fe621944 2020-11-10 stsp 		debug("L\n");
342 fe621944 2020-11-10 stsp 		debug_dump_atoms(&state->left, left_start, left_count);
343 fe621944 2020-11-10 stsp 		debug("R\n");
344 fe621944 2020-11-10 stsp 		debug_dump_atoms(&state->right, right_start, right_count);
345 fe621944 2020-11-10 stsp 		ARRAYLIST_ADD(new_chunk, state->temp_result);
346 fe621944 2020-11-10 stsp 		if (!new_chunk)
347 fe621944 2020-11-10 stsp 			return NULL;
348 fe621944 2020-11-10 stsp 		*new_chunk = chunk;
349 fe621944 2020-11-10 stsp 		return new_chunk;
350 fe621944 2020-11-10 stsp 	}
351 fe621944 2020-11-10 stsp 
352 fe621944 2020-11-10 stsp 	return diff_state_add_solved_chunk(state, &chunk);
353 fe621944 2020-11-10 stsp }
354 fe621944 2020-11-10 stsp 
355 ef20f542 2022-06-26 thomas static void
356 fe621944 2020-11-10 stsp diff_data_init_root(struct diff_data *d, FILE *f, const uint8_t *data,
357 fe621944 2020-11-10 stsp     unsigned long long len, int diff_flags)
358 fe621944 2020-11-10 stsp {
359 fe621944 2020-11-10 stsp 	*d = (struct diff_data){
360 fe621944 2020-11-10 stsp 		.f = f,
361 fe621944 2020-11-10 stsp 		.pos = 0,
362 fe621944 2020-11-10 stsp 		.data = data,
363 fe621944 2020-11-10 stsp 		.len = len,
364 fe621944 2020-11-10 stsp 		.root = d,
365 fe621944 2020-11-10 stsp 		.diff_flags = diff_flags,
366 fe621944 2020-11-10 stsp 	};
367 fe621944 2020-11-10 stsp }
368 fe621944 2020-11-10 stsp 
369 fe621944 2020-11-10 stsp void
370 fe621944 2020-11-10 stsp diff_data_init_subsection(struct diff_data *d, struct diff_data *parent,
371 fe621944 2020-11-10 stsp 			  struct diff_atom *from_atom, unsigned int atoms_count)
372 fe621944 2020-11-10 stsp {
373 fe621944 2020-11-10 stsp 	struct diff_atom *last_atom;
374 fe621944 2020-11-10 stsp 
375 fe621944 2020-11-10 stsp 	debug("diff_data %p  parent %p  from_atom %p  atoms_count %u\n",
376 fe621944 2020-11-10 stsp 	      d, parent, from_atom, atoms_count);
377 fe621944 2020-11-10 stsp 	debug("  from_atom ");
378 fe621944 2020-11-10 stsp 	debug_dump_atom(parent, NULL, from_atom);
379 fe621944 2020-11-10 stsp 
380 fe621944 2020-11-10 stsp 	if (atoms_count == 0) {
381 fe621944 2020-11-10 stsp 		*d = (struct diff_data){
382 fe621944 2020-11-10 stsp 			.f = NULL,
383 fe621944 2020-11-10 stsp 			.pos = 0,
384 fe621944 2020-11-10 stsp 			.data = NULL,
385 fe621944 2020-11-10 stsp 			.len = 0,
386 fe621944 2020-11-10 stsp 			.root = parent->root,
387 fe621944 2020-11-10 stsp 			.atoms.head = NULL,
388 fe621944 2020-11-10 stsp 			.atoms.len = atoms_count,
389 fe621944 2020-11-10 stsp 		};
390 fe621944 2020-11-10 stsp 
391 fe621944 2020-11-10 stsp 		return;
392 fe621944 2020-11-10 stsp 	}
393 fe621944 2020-11-10 stsp 
394 fe621944 2020-11-10 stsp 	last_atom = from_atom + atoms_count - 1;
395 fe621944 2020-11-10 stsp 	*d = (struct diff_data){
396 fe621944 2020-11-10 stsp 		.f = NULL,
397 fe621944 2020-11-10 stsp 		.pos = from_atom->pos,
398 fe621944 2020-11-10 stsp 		.data = from_atom->at,
399 fe621944 2020-11-10 stsp 		.len = (last_atom->pos + last_atom->len) - from_atom->pos,
400 fe621944 2020-11-10 stsp 		.root = parent->root,
401 fe621944 2020-11-10 stsp 		.atoms.head = from_atom,
402 fe621944 2020-11-10 stsp 		.atoms.len = atoms_count,
403 fe621944 2020-11-10 stsp 	};
404 fe621944 2020-11-10 stsp 
405 fe621944 2020-11-10 stsp 	debug("subsection:\n");
406 fe621944 2020-11-10 stsp 	debug_dump(d);
407 fe621944 2020-11-10 stsp }
408 fe621944 2020-11-10 stsp 
409 fe621944 2020-11-10 stsp void
410 fe621944 2020-11-10 stsp diff_data_free(struct diff_data *diff_data)
411 fe621944 2020-11-10 stsp {
412 fe621944 2020-11-10 stsp 	if (!diff_data)
413 fe621944 2020-11-10 stsp 		return;
414 fe621944 2020-11-10 stsp 	if (diff_data->atoms.allocated)
415 fe621944 2020-11-10 stsp 		ARRAYLIST_FREE(diff_data->atoms);
416 fe621944 2020-11-10 stsp }
417 fe621944 2020-11-10 stsp 
418 fe621944 2020-11-10 stsp int
419 fe621944 2020-11-10 stsp diff_algo_none(const struct diff_algo_config *algo_config,
420 fe621944 2020-11-10 stsp 	       struct diff_state *state)
421 fe621944 2020-11-10 stsp {
422 fe621944 2020-11-10 stsp 	debug("\n** %s\n", __func__);
423 fe621944 2020-11-10 stsp 	debug("left:\n");
424 fe621944 2020-11-10 stsp 	debug_dump(&state->left);
425 fe621944 2020-11-10 stsp 	debug("right:\n");
426 fe621944 2020-11-10 stsp 	debug_dump(&state->right);
427 fe621944 2020-11-10 stsp 	debug_dump_myers_graph(&state->left, &state->right, NULL, NULL, 0, NULL,
428 fe621944 2020-11-10 stsp 			       0);
429 fe621944 2020-11-10 stsp 
430 fe621944 2020-11-10 stsp 	/* Add a chunk of equal lines, if any */
431 fe621944 2020-11-10 stsp 	struct diff_atom *l = state->left.atoms.head;
432 fe621944 2020-11-10 stsp 	unsigned int l_len = state->left.atoms.len;
433 fe621944 2020-11-10 stsp 	struct diff_atom *r = state->right.atoms.head;
434 fe621944 2020-11-10 stsp 	unsigned int r_len = state->right.atoms.len;
435 fe621944 2020-11-10 stsp 	unsigned int equal_atoms_start = 0;
436 fe621944 2020-11-10 stsp 	unsigned int equal_atoms_end = 0;
437 fe621944 2020-11-10 stsp 	unsigned int l_idx = 0;
438 fe621944 2020-11-10 stsp 	unsigned int r_idx = 0;
439 fe621944 2020-11-10 stsp 
440 fe621944 2020-11-10 stsp 	while (equal_atoms_start < l_len
441 fe621944 2020-11-10 stsp 	       && equal_atoms_start < r_len) {
442 fe621944 2020-11-10 stsp 		int err;
443 fe621944 2020-11-10 stsp 		bool same;
444 fe621944 2020-11-10 stsp 		err = diff_atom_same(&same, &l[equal_atoms_start],
445 fe621944 2020-11-10 stsp 				     &r[equal_atoms_start]);
446 fe621944 2020-11-10 stsp 		if (err)
447 fe621944 2020-11-10 stsp 			return err;
448 fe621944 2020-11-10 stsp 		if (!same)
449 fe621944 2020-11-10 stsp 			break;
450 fe621944 2020-11-10 stsp 		equal_atoms_start++;
451 fe621944 2020-11-10 stsp 	}
452 fe621944 2020-11-10 stsp 	while (equal_atoms_end < (l_len - equal_atoms_start)
453 fe621944 2020-11-10 stsp 	       && equal_atoms_end < (r_len - equal_atoms_start)) {
454 fe621944 2020-11-10 stsp 		int err;
455 fe621944 2020-11-10 stsp 		bool same;
456 fe621944 2020-11-10 stsp 		err = diff_atom_same(&same, &l[l_len - 1 - equal_atoms_end],
457 fe621944 2020-11-10 stsp 				   &r[r_len - 1 - equal_atoms_end]);
458 fe621944 2020-11-10 stsp 		if (err)
459 fe621944 2020-11-10 stsp 			return err;
460 fe621944 2020-11-10 stsp 		if (!same)
461 fe621944 2020-11-10 stsp 			break;
462 fe621944 2020-11-10 stsp 		equal_atoms_end++;
463 fe621944 2020-11-10 stsp 	}
464 fe621944 2020-11-10 stsp 
465 fe621944 2020-11-10 stsp 	/* Add a chunk of equal lines at the start */
466 fe621944 2020-11-10 stsp 	if (equal_atoms_start) {
467 fe621944 2020-11-10 stsp 		if (!diff_state_add_chunk(state, true,
468 fe621944 2020-11-10 stsp 					  l, equal_atoms_start,
469 fe621944 2020-11-10 stsp 					  r, equal_atoms_start))
470 fe621944 2020-11-10 stsp 			return ENOMEM;
471 fe621944 2020-11-10 stsp 		l_idx += equal_atoms_start;
472 fe621944 2020-11-10 stsp 		r_idx += equal_atoms_start;
473 fe621944 2020-11-10 stsp 	}
474 fe621944 2020-11-10 stsp 
475 fe621944 2020-11-10 stsp 	/* Add a "minus" chunk with all lines from the left. */
476 fe621944 2020-11-10 stsp 	if (equal_atoms_start + equal_atoms_end < l_len) {
477 fe621944 2020-11-10 stsp 		unsigned int add_len = l_len - equal_atoms_start - equal_atoms_end;
478 fe621944 2020-11-10 stsp 		if (!diff_state_add_chunk(state, true,
479 fe621944 2020-11-10 stsp 					  &l[l_idx], add_len,
480 fe621944 2020-11-10 stsp 					  &r[r_idx], 0))
481 fe621944 2020-11-10 stsp 			return ENOMEM;
482 fe621944 2020-11-10 stsp 		l_idx += add_len;
483 fe621944 2020-11-10 stsp 	}
484 fe621944 2020-11-10 stsp 
485 fe621944 2020-11-10 stsp 	/* Add a "plus" chunk with all lines from the right. */
486 fe621944 2020-11-10 stsp 	if (equal_atoms_start + equal_atoms_end < r_len) {
487 fe621944 2020-11-10 stsp 		unsigned int add_len = r_len - equal_atoms_start - equal_atoms_end;
488 fe621944 2020-11-10 stsp 		if (!diff_state_add_chunk(state, true,
489 fe621944 2020-11-10 stsp 					  &l[l_idx], 0,
490 fe621944 2020-11-10 stsp 					  &r[r_idx], add_len))
491 fe621944 2020-11-10 stsp 			return ENOMEM;
492 fe621944 2020-11-10 stsp 		r_idx += add_len;
493 fe621944 2020-11-10 stsp 	}
494 fe621944 2020-11-10 stsp 
495 fe621944 2020-11-10 stsp 	/* Add a chunk of equal lines at the end */
496 fe621944 2020-11-10 stsp 	if (equal_atoms_end) {
497 fe621944 2020-11-10 stsp 		if (!diff_state_add_chunk(state, true,
498 fe621944 2020-11-10 stsp 					  &l[l_idx], equal_atoms_end,
499 fe621944 2020-11-10 stsp 					  &r[r_idx], equal_atoms_end))
500 fe621944 2020-11-10 stsp 			return ENOMEM;
501 fe621944 2020-11-10 stsp 	}
502 fe621944 2020-11-10 stsp 
503 fe621944 2020-11-10 stsp 	return DIFF_RC_OK;
504 fe621944 2020-11-10 stsp }
505 fe621944 2020-11-10 stsp 
506 ef20f542 2022-06-26 thomas static int
507 fe621944 2020-11-10 stsp diff_run_algo(const struct diff_algo_config *algo_config,
508 fe621944 2020-11-10 stsp 	      struct diff_state *state)
509 fe621944 2020-11-10 stsp {
510 fe621944 2020-11-10 stsp 	int rc;
511 fe621944 2020-11-10 stsp 
512 fe621944 2020-11-10 stsp 	if (!algo_config || !algo_config->impl
513 fe621944 2020-11-10 stsp 	    || !state->recursion_depth_left
514 fe621944 2020-11-10 stsp 	    || !state->left.atoms.len || !state->right.atoms.len) {
515 fe621944 2020-11-10 stsp 		debug("Fall back to diff_algo_none():%s%s%s\n",
516 fe621944 2020-11-10 stsp 		      (!algo_config || !algo_config->impl) ? " no-cfg" : "",
517 fe621944 2020-11-10 stsp 		      (!state->recursion_depth_left) ? " max-depth" : "",
518 fe621944 2020-11-10 stsp 		      (!state->left.atoms.len || !state->right.atoms.len)?
519 fe621944 2020-11-10 stsp 			      " trivial" : "");
520 fe621944 2020-11-10 stsp 		return diff_algo_none(algo_config, state);
521 fe621944 2020-11-10 stsp 	}
522 fe621944 2020-11-10 stsp 
523 fe621944 2020-11-10 stsp 	ARRAYLIST_FREE(state->temp_result);
524 fe621944 2020-11-10 stsp 	ARRAYLIST_INIT(state->temp_result, DIFF_RESULT_ALLOC_BLOCKSIZE);
525 fe621944 2020-11-10 stsp 	rc = algo_config->impl(algo_config, state);
526 fe621944 2020-11-10 stsp 	switch (rc) {
527 fe621944 2020-11-10 stsp 	case DIFF_RC_USE_DIFF_ALGO_FALLBACK:
528 fe621944 2020-11-10 stsp 		debug("Got DIFF_RC_USE_DIFF_ALGO_FALLBACK (%p)\n",
529 fe621944 2020-11-10 stsp 		      algo_config->fallback_algo);
530 fe621944 2020-11-10 stsp 		rc = diff_run_algo(algo_config->fallback_algo, state);
531 fe621944 2020-11-10 stsp 		goto return_rc;
532 fe621944 2020-11-10 stsp 
533 fe621944 2020-11-10 stsp 	case DIFF_RC_OK:
534 fe621944 2020-11-10 stsp 		/* continue below */
535 fe621944 2020-11-10 stsp 		break;
536 fe621944 2020-11-10 stsp 
537 fe621944 2020-11-10 stsp 	default:
538 fe621944 2020-11-10 stsp 		/* some error happened */
539 fe621944 2020-11-10 stsp 		goto return_rc;
540 fe621944 2020-11-10 stsp 	}
541 fe621944 2020-11-10 stsp 
542 fe621944 2020-11-10 stsp 	/* Pick up any diff chunks that are still unsolved and feed to
543 fe621944 2020-11-10 stsp 	 * inner_algo.  inner_algo will solve unsolved chunks and append to
544 fe621944 2020-11-10 stsp 	 * result, and subsequent solved chunks on this level are then appended
545 fe621944 2020-11-10 stsp 	 * to result afterwards. */
546 fe621944 2020-11-10 stsp 	int i;
547 fe621944 2020-11-10 stsp 	for (i = 0; i < state->temp_result.len; i++) {
548 fe621944 2020-11-10 stsp 		struct diff_chunk *c = &state->temp_result.head[i];
549 fe621944 2020-11-10 stsp 		if (c->solved) {
550 fe621944 2020-11-10 stsp 			diff_state_add_solved_chunk(state, c);
551 fe621944 2020-11-10 stsp 			continue;
552 fe621944 2020-11-10 stsp 		}
553 fe621944 2020-11-10 stsp 
554 fe621944 2020-11-10 stsp 		/* c is an unsolved chunk, feed to inner_algo */
555 fe621944 2020-11-10 stsp 		struct diff_state inner_state = {
556 fe621944 2020-11-10 stsp 			.result = state->result,
557 fe621944 2020-11-10 stsp 			.recursion_depth_left = state->recursion_depth_left - 1,
558 fe621944 2020-11-10 stsp 			.kd_buf = state->kd_buf,
559 fe621944 2020-11-10 stsp 			.kd_buf_size = state->kd_buf_size,
560 fe621944 2020-11-10 stsp 		};
561 fe621944 2020-11-10 stsp 		diff_data_init_subsection(&inner_state.left, &state->left,
562 fe621944 2020-11-10 stsp 					  c->left_start, c->left_count);
563 fe621944 2020-11-10 stsp 		diff_data_init_subsection(&inner_state.right, &state->right,
564 fe621944 2020-11-10 stsp 					  c->right_start, c->right_count);
565 fe621944 2020-11-10 stsp 
566 fe621944 2020-11-10 stsp 		rc = diff_run_algo(algo_config->inner_algo, &inner_state);
567 fe621944 2020-11-10 stsp 		state->kd_buf = inner_state.kd_buf;
568 fe621944 2020-11-10 stsp 		state->kd_buf_size = inner_state.kd_buf_size;
569 fe621944 2020-11-10 stsp 		if (rc != DIFF_RC_OK)
570 fe621944 2020-11-10 stsp 			goto return_rc;
571 fe621944 2020-11-10 stsp 	}
572 fe621944 2020-11-10 stsp 
573 fe621944 2020-11-10 stsp 	rc = DIFF_RC_OK;
574 fe621944 2020-11-10 stsp return_rc:
575 fe621944 2020-11-10 stsp 	ARRAYLIST_FREE(state->temp_result);
576 fe621944 2020-11-10 stsp 	return rc;
577 fe621944 2020-11-10 stsp }
578 fe621944 2020-11-10 stsp 
579 fe621944 2020-11-10 stsp int
580 fe621944 2020-11-10 stsp diff_atomize_file(struct diff_data *d,
581 fe621944 2020-11-10 stsp 		  const struct diff_config *config,
582 fe621944 2020-11-10 stsp 		  FILE *f, const uint8_t *data, off_t len, int diff_flags)
583 fe621944 2020-11-10 stsp {
584 fe621944 2020-11-10 stsp 	if (!config->atomize_func)
585 fe621944 2020-11-10 stsp 		return EINVAL;
586 fe621944 2020-11-10 stsp 
587 fe621944 2020-11-10 stsp 	diff_data_init_root(d, f, data, len, diff_flags);
588 fe621944 2020-11-10 stsp 
589 fe621944 2020-11-10 stsp 	return config->atomize_func(config->atomize_func_data, d);
590 fe621944 2020-11-10 stsp 
591 fe621944 2020-11-10 stsp }
592 fe621944 2020-11-10 stsp 
593 fe621944 2020-11-10 stsp struct diff_result *
594 fe621944 2020-11-10 stsp diff_main(const struct diff_config *config, struct diff_data *left,
595 fe621944 2020-11-10 stsp 	  struct diff_data *right)
596 fe621944 2020-11-10 stsp {
597 fe621944 2020-11-10 stsp 	struct diff_result *result = malloc(sizeof(struct diff_result));
598 fe621944 2020-11-10 stsp 	if (!result)
599 fe621944 2020-11-10 stsp 		return NULL;
600 fe621944 2020-11-10 stsp 
601 fe621944 2020-11-10 stsp 	*result = (struct diff_result){};
602 fe621944 2020-11-10 stsp 	result->left = left;
603 fe621944 2020-11-10 stsp 	result->right = right;
604 fe621944 2020-11-10 stsp 
605 fe621944 2020-11-10 stsp 	struct diff_state state = {
606 fe621944 2020-11-10 stsp 		.result = result,
607 b15f45f4 2022-09-02 thomas 		.recursion_depth_left = config->max_recursion_depth ?
608 b15f45f4 2022-09-02 thomas 		    config->max_recursion_depth : UINT_MAX,
609 fe621944 2020-11-10 stsp 		.kd_buf = NULL,
610 fe621944 2020-11-10 stsp 		.kd_buf_size = 0,
611 fe621944 2020-11-10 stsp 	};
612 fe621944 2020-11-10 stsp 	diff_data_init_subsection(&state.left, left,
613 fe621944 2020-11-10 stsp 				  left->atoms.head,
614 fe621944 2020-11-10 stsp 				  left->atoms.len);
615 fe621944 2020-11-10 stsp 	diff_data_init_subsection(&state.right, right,
616 fe621944 2020-11-10 stsp 				  right->atoms.head,
617 fe621944 2020-11-10 stsp 				  right->atoms.len);
618 fe621944 2020-11-10 stsp 
619 fe621944 2020-11-10 stsp 	result->rc = diff_run_algo(config->algo, &state);
620 fe621944 2020-11-10 stsp 	free(state.kd_buf);
621 fe621944 2020-11-10 stsp 
622 fe621944 2020-11-10 stsp 	return result;
623 fe621944 2020-11-10 stsp }
624 fe621944 2020-11-10 stsp 
625 fe621944 2020-11-10 stsp void
626 fe621944 2020-11-10 stsp diff_result_free(struct diff_result *result)
627 fe621944 2020-11-10 stsp {
628 fe621944 2020-11-10 stsp 	if (!result)
629 fe621944 2020-11-10 stsp 		return;
630 fe621944 2020-11-10 stsp 	ARRAYLIST_FREE(result->chunks);
631 fe621944 2020-11-10 stsp 	free(result);
632 fe621944 2020-11-10 stsp }