Blame


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