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