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