2 * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
3 * Copyright (c) 2020 Stefan Sperling <stsp@openbsd.org>
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.
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.
20 #include <sys/queue.h>
27 #include "got_object.h"
28 #include "got_opentemp.h"
29 #include "got_error.h"
31 #include "got_lib_diff.h"
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;
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,
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,
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,
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). */
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,
73 /* If the state for a forward-Myers is small enough, use Myers, otherwise first
75 const struct diff_config diff_config_myers_then_patience = {
76 .atomize_func = diff_atomize_text_by_line,
77 .algo = &myers_then_patience,
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,
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,
91 const struct got_error *
92 got_diffreg_close(FILE *f1, char *p1, size_t size1,
93 FILE *f2, char *p2, size_t size2)
95 const struct got_error *err = NULL;
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");
108 const struct diff_config *
109 got_diff_get_config(enum got_diff_algorithm algorithm)
112 case GOT_DIFF_ALGORITHM_PATIENCE:
113 return &diff_config_patience;
114 case GOT_DIFF_ALGORITHM_MYERS:
115 return &diff_config_myers_then_myers_divide;
117 return NULL; /* should not happen */
120 const struct got_error *
121 got_diff_prepare_file(FILE *f, char **p, size_t *size,
122 struct diff_data *diff_data, const struct diff_config *cfg,
123 int ignore_whitespace)
125 const struct got_error *err = NULL;
127 int diff_flags = 0, rc;
131 diff_flags |= DIFF_FLAG_SHOW_PROTOTYPES;
132 if (ignore_whitespace)
133 diff_flags |= DIFF_FLAG_IGNORE_WHITESPACE;
135 if (fstat(fileno(f), &st) == -1) {
136 err = got_error_from_errno("fstat");
139 #ifndef GOT_DIFF_NO_MMAP
140 *p = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE,
142 if (*p == MAP_FAILED)
144 *p = NULL; /* fall back on file I/O */
146 rc = diff_atomize_file(diff_data, cfg, f, *p, st.st_size, diff_flags);
148 err = got_error_set_errno(rc, "diff_atomize_file");
153 diff_data_free(diff_data);
159 const struct got_error *
160 got_diffreg(struct got_diffreg_result **diffreg_result, FILE *f1, FILE *f2,
161 enum got_diff_algorithm algorithm, int ignore_whitespace)
163 const struct got_error *err = NULL;
164 const struct diff_config *cfg;
165 char *p1 = NULL, *p2 = NULL;
166 int f1_created = 0, f2_created = 0;
168 struct diff_data d_left, d_right;
169 struct diff_data *left, *right;
170 struct diff_result *diff_result;
172 if (diffreg_result) {
173 *diffreg_result = calloc(1, sizeof(**diffreg_result));
174 if (*diffreg_result == NULL)
175 return got_error_from_errno("calloc");
176 left = &(*diffreg_result)->left;
177 right = &(*diffreg_result)->right;
179 memset(&d_left, 0, sizeof(d_left));
180 memset(&d_right, 0, sizeof(d_right));
185 cfg = got_diff_get_config(algorithm);
187 err = got_error(GOT_ERR_NOT_IMPL);
195 err = got_error_from_errno("got_opentemp");
203 err = got_error_from_errno("got_opentemp");
208 err = got_diff_prepare_file(f1, &p1, &size1, left, cfg,
213 err = got_diff_prepare_file(f2, &p2, &size2, right, cfg,
218 diff_result = diff_main(cfg, left, right);
219 if (diff_result == NULL) {
220 err = got_error_set_errno(ENOMEM, "malloc");
223 if (diff_result->rc != DIFF_RC_OK) {
224 err = got_error_set_errno(diff_result->rc, "diff");
228 if (diffreg_result) {
229 (*diffreg_result)->result = diff_result;
231 (*diffreg_result)->f1 = f1;
232 (*diffreg_result)->map1 = p1;
233 (*diffreg_result)->size1 = size1;
235 (*diffreg_result)->f2 = f2;
236 (*diffreg_result)->map2 = p2;
237 (*diffreg_result)->size2 = size2;
240 if (diffreg_result == NULL) {
241 diff_data_free(left);
242 diff_data_free(right);
245 got_diffreg_close(f1_created ? f1 : NULL, p1, size1,
246 f2_created ? f2 : NULL, p2, size2);
247 if (diffreg_result) {
248 diff_data_free(left);
249 diff_data_free(right);
250 free(*diffreg_result);
251 *diffreg_result = NULL;
258 const struct got_error *
259 got_diffreg_output(off_t **line_offsets, size_t *nlines,
260 struct got_diffreg_result *diff_result, FILE *f1, FILE *f2,
261 const char *path1, const char *path2,
262 enum got_diff_output_format output_format, int context_lines, FILE *outfile)
264 struct diff_input_info info = {
269 struct diff_output_info *output_info;
271 switch (output_format) {
272 case GOT_DIFF_OUTPUT_UNIDIFF:
273 rc = diff_output_unidiff(
274 line_offsets ? &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");
279 case GOT_DIFF_OUTPUT_EDSCRIPT:
280 rc = diff_output_edscript(line_offsets ? &output_info : NULL,
281 outfile, &info, diff_result->result);
282 if (rc != DIFF_RC_OK)
283 return got_error_set_errno(rc, "diff_output_edscript");
288 if (line_offsets && *line_offsets) {
289 if (output_info->line_offsets.len > 0) {
290 off_t prev_offset = 0, *p, *o;
293 prev_offset = (*line_offsets)[*nlines - 1];
295 * First line offset is always zero. Skip it
296 * when appending to a pre-populated array.
298 o = &output_info->line_offsets.head[1];
299 len = output_info->line_offsets.len - 1;
301 o = &output_info->line_offsets.head[0];
302 len = output_info->line_offsets.len;
304 p = reallocarray(*line_offsets, *nlines + len,
307 return got_error_from_errno("calloc");
308 for (i = 0; i < len; i++)
309 p[*nlines + i] = o[i] + prev_offset;
313 diff_output_info_free(output_info);
319 const struct got_error *
320 got_diffreg_result_free(struct got_diffreg_result *diffreg_result)
322 const struct got_error *err;
324 diff_result_free(diffreg_result->result);
325 diff_data_free(&diffreg_result->left);
326 diff_data_free(&diffreg_result->right);
327 err = got_diffreg_close(diffreg_result->f1, diffreg_result->map1,
328 diffreg_result->size1, diffreg_result->f2,
329 diffreg_result->map2, diffreg_result->size2);
330 free(diffreg_result);
334 const struct got_error *
335 got_diffreg_result_free_left(struct got_diffreg_result *diffreg_result)
337 diff_data_free(&diffreg_result->left);
338 memset(&diffreg_result->left, 0, sizeof(diffreg_result->left));
339 return got_diffreg_close(diffreg_result->f1, diffreg_result->map1,
340 diffreg_result->size1, NULL, NULL, 0);
343 const struct got_error *
344 got_diffreg_result_free_right(struct got_diffreg_result *diffreg_result)
346 diff_data_free(&diffreg_result->right);
347 memset(&diffreg_result->right, 0, sizeof(diffreg_result->right));
348 return got_diffreg_close(NULL, NULL, 0, diffreg_result->f2,
349 diffreg_result->map2, diffreg_result->size2);