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