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.
26 #include "got_compat.h"
28 #include "got_object.h"
29 #include "got_opentemp.h"
30 #include "got_error.h"
32 #include "got_lib_diff.h"
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
;
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
,
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
,
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
,
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). */
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
,
74 /* If the state for a forward-Myers is small enough, use Myers, otherwise first
76 const struct diff_config diff_config_myers_then_patience
= {
77 .atomize_func
= diff_atomize_text_by_line
,
78 .algo
= &myers_then_patience
,
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
,
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
,
92 const struct got_error
*
93 got_diffreg_close(FILE *f1
, char *p1
, size_t size1
,
94 FILE *f2
, char *p2
, size_t size2
)
96 const struct got_error
*err
= NULL
;
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");
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
)
114 *cfg
= calloc(1, sizeof(**cfg
));
116 return got_error_from_errno("calloc");
119 case GOT_DIFF_ALGORITHM_PATIENCE
:
120 (*cfg
)->algo
= &patience
;
122 case GOT_DIFF_ALGORITHM_MYERS
:
123 (*cfg
)->algo
= &myers_then_myers_divide
;
126 return got_error_msg(GOT_ERR_NOT_IMPL
, "bad diff algorithm");
130 (*cfg
)->atomize_func
= atomize_func
;
131 (*cfg
)->atomize_func_data
= atomize_func_data
;
133 (*cfg
)->atomize_func
= diff_atomize_text_by_line
;
135 (*cfg
)->max_recursion_depth
= 0; /* use default recursion depth */
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
)
145 const struct got_error
*err
= NULL
;
147 int diff_flags
= 0, rc
;
151 diff_flags
|= DIFF_FLAG_SHOW_PROTOTYPES
;
152 if (ignore_whitespace
)
153 diff_flags
|= DIFF_FLAG_IGNORE_WHITESPACE
;
155 diff_flags
|= DIFF_FLAG_FORCE_TEXT_DATA
;
157 if (fstat(fileno(f
), &st
) == -1) {
158 err
= got_error_from_errno("fstat");
161 #ifndef GOT_DIFF_NO_MMAP
162 *p
= mmap(NULL
, st
.st_size
, PROT_READ
, MAP_PRIVATE
,
164 if (*p
== MAP_FAILED
)
166 *p
= NULL
; /* fall back on file I/O */
168 rc
= diff_atomize_file(diff_data
, cfg
, f
, *p
, st
.st_size
, diff_flags
);
170 err
= got_error_set_errno(rc
, "diff_atomize_file");
175 diff_data_free(diff_data
);
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
,
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;
191 struct diff_data d_left
, d_right
;
192 struct diff_data
*left
, *right
;
193 struct diff_result
*diff_result
;
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
;
202 memset(&d_left
, 0, sizeof(d_left
));
203 memset(&d_right
, 0, sizeof(d_right
));
208 err
= got_diff_get_config(&cfg
, algorithm
, NULL
, NULL
);
216 err
= got_error_from_errno("got_opentemp");
224 err
= got_error_from_errno("got_opentemp");
229 err
= got_diff_prepare_file(f1
, &p1
, &size1
, left
, cfg
,
230 ignore_whitespace
, force_text_diff
);
234 err
= got_diff_prepare_file(f2
, &p2
, &size2
, right
, cfg
,
235 ignore_whitespace
, force_text_diff
);
239 diff_result
= diff_main(cfg
, left
, right
);
240 if (diff_result
== NULL
) {
241 err
= got_error_set_errno(ENOMEM
, "malloc");
244 if (diff_result
->rc
!= DIFF_RC_OK
) {
245 err
= got_error_set_errno(diff_result
->rc
, "diff");
249 if (diffreg_result
) {
250 (*diffreg_result
)->result
= diff_result
;
252 (*diffreg_result
)->f1
= f1
;
253 (*diffreg_result
)->map1
= p1
;
254 (*diffreg_result
)->size1
= size1
;
256 (*diffreg_result
)->f2
= f2
;
257 (*diffreg_result
)->map2
= p2
;
258 (*diffreg_result
)->size2
= size2
;
262 if (diffreg_result
== NULL
) {
263 diff_data_free(left
);
264 diff_data_free(right
);
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
;
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
)
286 struct diff_input_info info
= {
292 struct diff_output_info
*output_info
;
295 info
.flags
|= DIFF_INPUT_LEFT_NONEXISTENT
;
297 info
.flags
|= DIFF_INPUT_RIGHT_NONEXISTENT
;
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");
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");
316 if (line_offsets
&& *line_offsets
) {
317 if (output_info
->line_offsets
.len
> 0) {
318 off_t prev_offset
= 0, *p
, *o
;
321 prev_offset
= (*line_offsets
)[*nlines
- 1];
323 * First line offset is always zero. Skip it
324 * when appending to a pre-populated array.
326 o
= &output_info
->line_offsets
.head
[1];
327 len
= output_info
->line_offsets
.len
- 1;
329 o
= &output_info
->line_offsets
.head
[0];
330 len
= output_info
->line_offsets
.len
;
332 p
= reallocarray(*line_offsets
, *nlines
+ len
,
335 return got_error_from_errno("calloc");
336 for (i
= 0; i
< len
; i
++)
337 p
[*nlines
+ i
] = o
[i
] + prev_offset
;
341 diff_output_info_free(output_info
);
347 const struct got_error
*
348 got_diffreg_result_free(struct got_diffreg_result
*diffreg_result
)
350 const struct got_error
*err
;
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
);
362 const struct got_error
*
363 got_diffreg_result_free_left(struct got_diffreg_result
*diffreg_result
)
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);
371 const struct got_error
*
372 got_diffreg_result_free_right(struct got_diffreg_result
*diffreg_result
)
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
);