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