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_compat.h"
29 #include "got_object.h"
30 #include "got_opentemp.h"
31 #include "got_error.h"
34 #include "got_lib_diff.h"
36 const struct diff_algo_config myers_then_patience;
37 const struct diff_algo_config myers_then_myers_divide;
38 const struct diff_algo_config patience;
39 const struct diff_algo_config myers_divide;
41 const struct diff_algo_config myers_then_patience = (struct diff_algo_config){
42 .impl = diff_algo_myers,
43 .permitted_state_size = 1024 * 1024 * sizeof(int),
44 .fallback_algo = &patience,
47 const struct diff_algo_config myers_then_myers_divide =
48 (struct diff_algo_config){
49 .impl = diff_algo_myers,
50 .permitted_state_size = 1024 * 1024 * sizeof(int),
51 .fallback_algo = &myers_divide,
54 const struct diff_algo_config patience = (struct diff_algo_config){
55 .impl = diff_algo_patience,
56 /* After subdivision, do Patience again: */
57 .inner_algo = &patience,
58 /* If subdivision failed, do Myers Divide et Impera: */
59 .fallback_algo = &myers_then_myers_divide,
62 const struct diff_algo_config myers_divide = (struct diff_algo_config){
63 .impl = diff_algo_myers_divide,
64 /* When division succeeded, start from the top: */
65 .inner_algo = &myers_then_myers_divide,
66 /* (fallback_algo = NULL implies diff_algo_none). */
69 /* If the state for a forward-Myers is small enough, use Myers, otherwise first
70 * do a Myers-divide. */
71 const struct diff_config diff_config_myers_then_myers_divide = {
72 .atomize_func = diff_atomize_text_by_line,
73 .algo = &myers_then_myers_divide,
76 /* If the state for a forward-Myers is small enough, use Myers, otherwise first
78 const struct diff_config diff_config_myers_then_patience = {
79 .atomize_func = diff_atomize_text_by_line,
80 .algo = &myers_then_patience,
83 /* Directly force Patience as a first divider of the source file. */
84 const struct diff_config diff_config_patience = {
85 .atomize_func = diff_atomize_text_by_line,
89 /* Directly force Patience as a first divider of the source file. */
90 const struct diff_config diff_config_no_algo = {
91 .atomize_func = diff_atomize_text_by_line,
94 const struct got_error *
95 got_diffreg_close(char *p1, size_t size1, char *p2, size_t size2)
97 const struct got_error *err = NULL;
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");
106 const struct got_error *
107 got_diff_get_config(struct diff_config **cfg,
108 enum got_diff_algorithm algorithm,
109 diff_atomize_func_t atomize_func, void *atomize_func_data)
111 *cfg = calloc(1, sizeof(**cfg));
113 return got_error_from_errno("calloc");
116 case GOT_DIFF_ALGORITHM_PATIENCE:
117 (*cfg)->algo = &patience;
119 case GOT_DIFF_ALGORITHM_MYERS:
120 (*cfg)->algo = &myers_then_myers_divide;
123 return got_error_msg(GOT_ERR_NOT_IMPL, "bad diff algorithm");
127 (*cfg)->atomize_func = atomize_func;
128 (*cfg)->atomize_func_data = atomize_func_data;
130 (*cfg)->atomize_func = diff_atomize_text_by_line;
132 (*cfg)->max_recursion_depth = 0; /* use default recursion depth */
137 const struct got_error *
138 got_diff_prepare_file(FILE *f, char **p, size_t *size,
139 struct diff_data *diff_data, const struct diff_config *cfg,
140 int ignore_whitespace, int force_text_diff)
142 const struct got_error *err = NULL;
144 int diff_flags = 0, rc;
148 diff_flags |= DIFF_FLAG_SHOW_PROTOTYPES;
149 if (ignore_whitespace)
150 diff_flags |= DIFF_FLAG_IGNORE_WHITESPACE;
152 diff_flags |= DIFF_FLAG_FORCE_TEXT_DATA;
154 if (fstat(fileno(f), &st) == -1) {
155 err = got_error_from_errno("fstat");
158 #ifndef GOT_DIFF_NO_MMAP
159 *p = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE,
161 if (*p == MAP_FAILED)
163 *p = NULL; /* fall back on file I/O */
165 rc = diff_atomize_file(diff_data, cfg, f, *p, st.st_size, diff_flags);
167 err = got_error_set_errno(rc, "diff_atomize_file");
172 diff_data_free(diff_data);
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,
183 const struct got_error *err = NULL;
184 struct diff_config *cfg = NULL;
185 char *p1 = NULL, *p2 = NULL;
187 struct diff_data d_left, d_right;
188 struct diff_data *left, *right;
189 struct diff_result *diff_result;
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;
198 memset(&d_left, 0, sizeof(d_left));
199 memset(&d_right, 0, sizeof(d_right));
204 err = got_diff_get_config(&cfg, algorithm, NULL, NULL);
208 err = got_diff_prepare_file(f1, &p1, &size1, left, cfg,
209 ignore_whitespace, force_text_diff);
213 err = got_diff_prepare_file(f2, &p2, &size2, right, cfg,
214 ignore_whitespace, force_text_diff);
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;
230 (*diffreg_result)->map1 = p1;
231 (*diffreg_result)->size1 = size1;
232 (*diffreg_result)->map2 = p2;
233 (*diffreg_result)->size2 = size2;
237 if (diffreg_result == NULL) {
238 diff_data_free(left);
239 diff_data_free(right);
242 got_diffreg_close(p1, size1, p2, size2);
243 if (diffreg_result) {
244 diff_data_free(left);
245 diff_data_free(right);
246 free(*diffreg_result);
247 *diffreg_result = NULL;
254 const struct got_error *
255 got_diffreg_output(struct got_diff_line **lines, size_t *nlines,
256 struct got_diffreg_result *diff_result, int f1_exists, int f2_exists,
257 const char *path1, const char *path2,
258 enum got_diff_output_format output_format, int context_lines, FILE *outfile)
260 struct diff_input_info info = {
266 struct diff_output_info *output_info;
269 info.flags |= DIFF_INPUT_LEFT_NONEXISTENT;
271 info.flags |= DIFF_INPUT_RIGHT_NONEXISTENT;
273 switch (output_format) {
274 case GOT_DIFF_OUTPUT_UNIDIFF:
275 rc = diff_output_unidiff(
276 lines ? &output_info : NULL, outfile, &info,
277 diff_result->result, context_lines);
278 if (rc != DIFF_RC_OK)
279 return got_error_set_errno(rc, "diff_output_unidiff");
281 case GOT_DIFF_OUTPUT_PLAIN:
282 rc = diff_output_plain(lines ? &output_info : NULL,
283 outfile, &info, diff_result->result, 1);
284 if (rc != DIFF_RC_OK)
285 return got_error_set_errno(rc, "diff_output_edscript");
290 if (lines && *lines) {
291 if (output_info->line_offsets.len > 0) {
292 struct got_diff_line *p;
293 off_t prev_offset = 0, *o;
297 prev_offset = (*lines)[*nlines - 1].offset;
299 * First line offset is always zero. Skip it
300 * when appending to a pre-populated array.
302 o = &output_info->line_offsets.head[1];
303 o2 = &output_info->line_types.head[1];
304 len = output_info->line_offsets.len - 1;
306 o = &output_info->line_offsets.head[0];
307 o2 = &output_info->line_types.head[0];
308 len = output_info->line_offsets.len;
310 p = reallocarray(*lines, *nlines + len, sizeof(**lines));
312 return got_error_from_errno("calloc");
313 for (i = 0; i < len; i++) {
314 p[*nlines + i].offset = o[i] + prev_offset;
315 p[*nlines + i].type = o2[i];
320 diff_output_info_free(output_info);
326 const struct got_error *
327 got_diffreg_result_free(struct got_diffreg_result *diffreg_result)
329 const struct got_error *err;
331 diff_result_free(diffreg_result->result);
332 diff_data_free(&diffreg_result->left);
333 diff_data_free(&diffreg_result->right);
334 err = got_diffreg_close(diffreg_result->map1, diffreg_result->size1,
335 diffreg_result->map2, diffreg_result->size2);
336 free(diffreg_result);
340 const struct got_error *
341 got_diffreg_result_free_left(struct got_diffreg_result *diffreg_result)
343 diff_data_free(&diffreg_result->left);
344 memset(&diffreg_result->left, 0, sizeof(diffreg_result->left));
345 return got_diffreg_close(diffreg_result->map1, diffreg_result->size1,
349 const struct got_error *
350 got_diffreg_result_free_right(struct got_diffreg_result *diffreg_result)
352 diff_data_free(&diffreg_result->right);
353 memset(&diffreg_result->right, 0, sizeof(diffreg_result->right));
354 return got_diffreg_close(NULL, 0, diffreg_result->map2,
355 diffreg_result->size2);