1 /*
2  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
3  * Copyright (c) 2020 Stefan Sperling <stsp@openbsd.org>
4  *
5  * Permission to use, copy, modify, and distribute this software for any
6  * purpose with or without fee is hereby granted, provided that the above
7  * copyright notice and this permission notice appear in all copies.
8  *
9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16  */
17 
18 #include <sys/mman.h>
19 #include <sys/stat.h>
20 #include <sys/queue.h>
21 
22 #include <errno.h>
23 #include <sha1.h>
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <string.h>
27 
28 #include "got_object.h"
29 #include "got_opentemp.h"
30 #include "got_error.h"
31 #include "got_diff.h"
32 
33 #include "got_lib_diff.h"
34 
35 const struct diff_algo_config myers_then_patience;
36 const struct diff_algo_config myers_then_myers_divide;
37 const struct diff_algo_config patience;
38 const struct diff_algo_config myers_divide;
39 
40 const struct diff_algo_config myers_then_patience = {
41 	.impl = diff_algo_myers,
42 	.permitted_state_size = 1024 * 1024 * sizeof(int),
43 	.fallback_algo = &patience,
44 };
45 
46 const struct diff_algo_config myers_then_myers_divide = {
47 	.impl = diff_algo_myers,
48 	.permitted_state_size = 1024 * 1024 * sizeof(int),
49 	.fallback_algo = &myers_divide,
50 };
51 
52 const struct diff_algo_config patience = {
53 	.impl = diff_algo_patience,
54 	/* After subdivision, do Patience again: */
55 	.inner_algo = &patience,
56 	/* If subdivision failed, do Myers Divide et Impera: */
57 	.fallback_algo = &myers_then_myers_divide,
58 };
59 
60 const struct diff_algo_config myers_divide = {
61 	.impl = diff_algo_myers_divide,
62 	/* When division succeeded, start from the top: */
63 	.inner_algo = &myers_then_myers_divide,
64 	/* (fallback_algo = NULL implies diff_algo_none). */
65 };
66 
67 /* If the state for a forward-Myers is small enough, use Myers, otherwise first
68  * do a Myers-divide. */
69 const struct diff_config diff_config_myers_then_myers_divide = {
70 	.atomize_func = diff_atomize_text_by_line,
71 	.algo = &myers_then_myers_divide,
72 };
73 
74 /* If the state for a forward-Myers is small enough, use Myers, otherwise first
75  * do a Patience. */
76 const struct diff_config diff_config_myers_then_patience = {
77 	.atomize_func = diff_atomize_text_by_line,
78 	.algo = &myers_then_patience,
79 };
80 
81 /* Directly force Patience as a first divider of the source file. */
82 const struct diff_config diff_config_patience = {
83 	.atomize_func = diff_atomize_text_by_line,
84 	.algo = &patience,
85 };
86 
87 /* Directly force Patience as a first divider of the source file. */
88 const struct diff_config diff_config_no_algo = {
89 	.atomize_func = diff_atomize_text_by_line,
90 };
91 
92 const struct got_error *
93 got_diffreg_close(char *p1, size_t size1, char *p2, size_t size2)
94 {
95 	const struct got_error *err = NULL;
96 
97 	if (p1 && munmap(p1, size1) == -1 && err == NULL)
98 		err = got_error_from_errno("munmap");
99 	if (p2 && munmap(p2, size2) == -1 && err == NULL)
100 		err = got_error_from_errno("munmap");
101 	return err;
102 }
103 
104 const struct got_error *
105 got_diff_get_config(struct diff_config **cfg,
106     enum got_diff_algorithm algorithm,
107     diff_atomize_func_t atomize_func, void *atomize_func_data)
108 {
109 	*cfg = calloc(1, sizeof(**cfg));
110 	if (*cfg == NULL)
111 		return got_error_from_errno("calloc");
112 
113 	switch (algorithm) {
114 	case GOT_DIFF_ALGORITHM_PATIENCE:
115 		(*cfg)->algo = &patience;
116 		break;
117 	case GOT_DIFF_ALGORITHM_MYERS:
118 		(*cfg)->algo = &myers_then_myers_divide;
119 		break;
120 	default:
121 		return got_error_msg(GOT_ERR_NOT_IMPL, "bad diff algorithm");
122 	}
123 
124 	if (atomize_func) {
125 		(*cfg)->atomize_func = atomize_func;
126 		(*cfg)->atomize_func_data = atomize_func_data;
127 	} else
128 		(*cfg)->atomize_func = diff_atomize_text_by_line;
129 
130 	(*cfg)->max_recursion_depth = 0; /* use default recursion depth */
131 
132 	return NULL;
133 }
134 
135 const struct got_error *
136 got_diff_prepare_file(FILE *f, char **p, size_t *size,
137     struct diff_data *diff_data, const struct diff_config *cfg,
138     int ignore_whitespace, int force_text_diff)
139 {
140 	const struct got_error *err = NULL;
141 	struct stat st;
142 	int diff_flags = 0, rc;
143 
144 	*size = 0;
145 
146 	diff_flags |= DIFF_FLAG_SHOW_PROTOTYPES;
147 	if (ignore_whitespace)
148 		diff_flags |= DIFF_FLAG_IGNORE_WHITESPACE;
149 	if (force_text_diff)
150 		diff_flags |= DIFF_FLAG_FORCE_TEXT_DATA;
151 
152 	if (fstat(fileno(f), &st) == -1) {
153 		err = got_error_from_errno("fstat");
154 		goto done;
155 	}
156 #ifndef GOT_DIFF_NO_MMAP
157 	*p = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE,
158 	    fileno(f), 0);
159 	if (*p == MAP_FAILED)
160 #endif
161 		*p = NULL; /* fall back on file I/O */
162 
163 	rc = diff_atomize_file(diff_data, cfg, f, *p, st.st_size, diff_flags);
164 	if (rc) {
165 		err = got_error_set_errno(rc, "diff_atomize_file");
166 		goto done;
167 	}
168 done:
169 	if (err)
170 		diff_data_free(diff_data);
171 	else
172 		*size = st.st_size;
173 	return err;
174 }
175 
176 const struct got_error *
177 got_diffreg(struct got_diffreg_result **diffreg_result, FILE *f1, FILE *f2,
178     enum got_diff_algorithm algorithm, int ignore_whitespace,
179     int force_text_diff)
180 {
181 	const struct got_error *err = NULL;
182 	struct diff_config *cfg = NULL;
183 	char *p1 = NULL, *p2 = NULL;
184 	size_t size1, size2;
185 	struct diff_data d_left, d_right;
186 	struct diff_data *left, *right;
187 	struct diff_result *diff_result;
188 
189 	if (diffreg_result) {
190 		*diffreg_result = calloc(1, sizeof(**diffreg_result));
191 		if (*diffreg_result == NULL)
192 			return got_error_from_errno("calloc");
193 		left = &(*diffreg_result)->left;
194 		right = &(*diffreg_result)->right;
195 	} else {
196 		memset(&d_left, 0, sizeof(d_left));
197 		memset(&d_right, 0, sizeof(d_right));
198 		left = &d_left;
199 		right = &d_right;
200 	}
201 
202 	err = got_diff_get_config(&cfg, algorithm, NULL, NULL);
203 	if (err)
204 		goto done;
205 
206 	err = got_diff_prepare_file(f1, &p1, &size1, left, cfg,
207 	    ignore_whitespace, force_text_diff);
208 	if (err)
209 		goto done;
210 
211 	err = got_diff_prepare_file(f2, &p2, &size2, right, cfg,
212 	    ignore_whitespace, force_text_diff);
213 	if (err)
214 		goto done;
215 
216 	diff_result = diff_main(cfg, left, right);
217 	if (diff_result == NULL) {
218 		err = got_error_set_errno(ENOMEM, "malloc");
219 		goto done;
220 	}
221 	if (diff_result->rc != DIFF_RC_OK) {
222 		err = got_error_set_errno(diff_result->rc, "diff");
223 		goto done;
224 	}
225 
226 	if (diffreg_result) {
227 		(*diffreg_result)->result = diff_result;
228 		(*diffreg_result)->map1 = p1;
229 		(*diffreg_result)->size1 = size1;
230 		(*diffreg_result)->map2 = p2;
231 		(*diffreg_result)->size2 = size2;
232 	}
233 done:
234 	free(cfg);
235 	if (diffreg_result == NULL) {
236 		diff_data_free(left);
237 		diff_data_free(right);
238 	}
239 	if (err) {
240 		got_diffreg_close(p1, size1, p2, size2);
241 		if (diffreg_result) {
242 			diff_data_free(left);
243 			diff_data_free(right);
244 			free(*diffreg_result);
245 			*diffreg_result = NULL;
246 		}
247 	}
248 
249 	return err;
250 }
251 
252 const struct got_error *
253 got_diffreg_output(struct got_diff_line **lines, size_t *nlines,
254     struct got_diffreg_result *diff_result, int f1_exists, int f2_exists,
255     const char *path1, const char *path2,
256     enum got_diff_output_format output_format, int context_lines, FILE *outfile)
257 {
258 	struct diff_input_info info = {
259 		.left_path = path1,
260 		.right_path = path2,
261 		.flags = 0,
262 	};
263 	int rc;
264 	struct diff_output_info *output_info;
265 
266 	if (!f1_exists)
267 		info.flags |= DIFF_INPUT_LEFT_NONEXISTENT;
268 	if (!f2_exists)
269 		info.flags |= DIFF_INPUT_RIGHT_NONEXISTENT;
270 
271 	switch (output_format) {
272 	case GOT_DIFF_OUTPUT_UNIDIFF:
273 		rc = diff_output_unidiff(
274 		    lines ? &output_info : NULL, outfile, &info,
275 		    diff_result->result, context_lines);
276 		if (rc != DIFF_RC_OK)
277 			return got_error_set_errno(rc, "diff_output_unidiff");
278 		break;
279 	case GOT_DIFF_OUTPUT_PLAIN:
280 		rc = diff_output_plain(lines ? &output_info : NULL,
281 		    outfile, &info, diff_result->result, 1);
282 		if (rc != DIFF_RC_OK)
283 			return got_error_set_errno(rc, "diff_output_edscript");
284 		break;
285 
286 	}
287 
288 	if (lines && *lines) {
289 		if (output_info->line_offsets.len > 0) {
290 			struct got_diff_line *p;
291 			off_t prev_offset = 0, *o;
292 			uint8_t *o2;
293 			int i, len;
294 			if (*nlines > 0) {
295 				prev_offset = (*lines)[*nlines - 1].offset;
296 				/*
297 				 * First line offset is always zero. Skip it
298 				 * when appending to a pre-populated array.
299 				 */
300 				o = &output_info->line_offsets.head[1];
301 				o2 = &output_info->line_types.head[1];
302 				len = output_info->line_offsets.len - 1;
303 			} else {
304 				o = &output_info->line_offsets.head[0];
305 				o2 = &output_info->line_types.head[0];
306 				len = output_info->line_offsets.len;
307 			}
308 			p = reallocarray(*lines, *nlines + len, sizeof(**lines));
309 			if (p == NULL)
310 				return got_error_from_errno("calloc");
311 			for (i = 0; i < len; i++) {
312 				p[*nlines + i].offset = o[i] + prev_offset;
313 				p[*nlines + i].type = o2[i];
314 			}
315 			*lines = p;
316 			*nlines += len;
317 		}
318 		diff_output_info_free(output_info);
319 	}
320 
321 	return NULL;
322 }
323 
324 const struct got_error *
325 got_diffreg_result_free(struct got_diffreg_result *diffreg_result)
326 {
327 	const struct got_error *err;
328 
329 	diff_result_free(diffreg_result->result);
330 	diff_data_free(&diffreg_result->left);
331 	diff_data_free(&diffreg_result->right);
332 	err = got_diffreg_close(diffreg_result->map1, diffreg_result->size1,
333 	    diffreg_result->map2, diffreg_result->size2);
334 	free(diffreg_result);
335 	return err;
336 }
337 
338 const struct got_error *
339 got_diffreg_result_free_left(struct got_diffreg_result *diffreg_result)
340 {
341 	diff_data_free(&diffreg_result->left);
342 	memset(&diffreg_result->left, 0, sizeof(diffreg_result->left));
343 	return got_diffreg_close(diffreg_result->map1, diffreg_result->size1,
344 	    NULL, 0);
345 }
346 
347 const struct got_error *
348 got_diffreg_result_free_right(struct got_diffreg_result *diffreg_result)
349 {
350 	diff_data_free(&diffreg_result->right);
351 	memset(&diffreg_result->right, 0, sizeof(diffreg_result->right));
352 	return got_diffreg_close(NULL, 0, diffreg_result->map2,
353 	    diffreg_result->size2);
354 }