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