1 /* Commandline diff utility to test diff implementations. */
2 /*
3  * Copyright (c) 2018 Martin Pieuchot
4  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
5  *
6  * Permission to use, copy, modify, and distribute this software for any
7  * purpose with or without fee is hereby granted, provided that the above
8  * copyright notice and this permission notice appear in all copies.
9  *
10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17  */
18 
19 #include <sys/mman.h>
20 #include <sys/stat.h>
21 #include <sys/types.h>
22 
23 #include <err.h>
24 #include <fcntl.h>
25 #include <stdint.h>
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <stdbool.h>
29 #include <string.h>
30 #include <unistd.h>
31 
32 #include <arraylist.h>
33 #include <diff_main.h>
34 #include <diff_output.h>
35 
36 enum diffreg_algo {
37 	DIFFREG_ALGO_MYERS_THEN_MYERS_DIVIDE = 0,
38 	DIFFREG_ALGO_MYERS_THEN_PATIENCE = 1,
39 	DIFFREG_ALGO_PATIENCE = 2,
40 	DIFFREG_ALGO_NONE = 3,
41 };
42 
43 __dead void	 usage(void);
44 int		 diffreg(char *, char *, enum diffreg_algo, bool, bool, bool,
45 			 int, bool);
46 FILE *		 openfile(const char *, char **, struct stat *);
47 
48 __dead void
49 usage(void)
50 {
51 	fprintf(stderr,
52 		"usage: %s [-apPQTwe] [-U n] file1 file2\n"
53 		"\n"
54 		"  -a   Treat input as ASCII even if binary data is detected\n"
55 		"  -p   Show function prototypes in hunk headers\n"
56 		"  -P   Use Patience Diff (slower but often nicer)\n"
57 		"  -Q   Use forward-Myers for small files, otherwise Patience\n"
58 		"  -T   Trivial algo: detect similar start and end only\n"
59 		"  -w   Ignore Whitespace\n"
60 		"  -U n Number of Context Lines\n"
61 		"  -e   Produce ed script output\n"
62 		, getprogname());
63 	exit(1);
64 }
65 
66 int
67 main(int argc, char *argv[])
68 {
69 	int ch, rc;
70 	bool force_text = false;
71 	bool ignore_whitespace = false;
72 	bool show_function_prototypes = false;
73 	bool edscript = false;
74 	int context_lines = 3;
75 	enum diffreg_algo algo = DIFFREG_ALGO_MYERS_THEN_MYERS_DIVIDE;
76 
77 	while ((ch = getopt(argc, argv, "apPQTwU:e")) != -1) {
78 		switch (ch) {
79 		case 'a':
80 			force_text = true;
81 			break;
82 		case 'p':
83 			show_function_prototypes = true;
84 			break;
85 		case 'P':
86 			algo = DIFFREG_ALGO_PATIENCE;
87 			break;
88 		case 'Q':
89 			algo = DIFFREG_ALGO_MYERS_THEN_PATIENCE;
90 			break;
91 		case 'T':
92 			algo = DIFFREG_ALGO_NONE;
93 			break;
94 		case 'w':
95 			ignore_whitespace = true;
96 			break;
97 		case 'U':
98 			context_lines = atoi(optarg);
99 			break;
100 		case 'e':
101 			edscript = true;
102 			break;
103 		default:
104 			usage();
105 		}
106 	}
107 
108 	argc -= optind;
109 	argv += optind;
110 
111 	if (argc != 2)
112 		usage();
113 
114 	rc = diffreg(argv[0], argv[1], algo, force_text, ignore_whitespace,
115 	    show_function_prototypes, context_lines, edscript);
116 	if (rc != DIFF_RC_OK) {
117 		fprintf(stderr, "diff: %s\n", strerror(rc));
118 		return 1;
119 	}
120 	return 0;
121 }
122 
123 const struct diff_algo_config myers_then_patience;
124 const struct diff_algo_config myers_then_myers_divide;
125 const struct diff_algo_config patience;
126 const struct diff_algo_config myers_divide;
127 
128 const struct diff_algo_config myers_then_patience = (struct diff_algo_config){
129 	.impl = diff_algo_myers,
130 	.permitted_state_size = 1024 * 1024 * sizeof(int),
131 	.fallback_algo = &patience,
132 };
133 
134 const struct diff_algo_config myers_then_myers_divide =
135 	(struct diff_algo_config){
136 	.impl = diff_algo_myers,
137 	.permitted_state_size = 1024 * 1024 * sizeof(int),
138 	.fallback_algo = &myers_divide,
139 };
140 
141 const struct diff_algo_config patience = (struct diff_algo_config){
142 	.impl = diff_algo_patience,
143 	/* After subdivision, do Patience again: */
144 	.inner_algo = &patience,
145 	/* If subdivision failed, do Myers Divide et Impera: */
146 	.fallback_algo = &myers_then_myers_divide,
147 };
148 
149 const struct diff_algo_config myers_divide = (struct diff_algo_config){
150 	.impl = diff_algo_myers_divide,
151 	/* When division succeeded, start from the top: */
152 	.inner_algo = &myers_then_myers_divide,
153 	/* (fallback_algo = NULL implies diff_algo_none). */
154 };
155 
156 const struct diff_algo_config no_algo = (struct diff_algo_config){
157 	.impl = diff_algo_none,
158 };
159 
160 /* If the state for a forward-Myers is small enough, use Myers, otherwise first
161  * do a Myers-divide. */
162 const struct diff_config diff_config_myers_then_myers_divide = {
163 	.atomize_func = diff_atomize_text_by_line,
164 	.algo = &myers_then_myers_divide,
165 };
166 
167 /* If the state for a forward-Myers is small enough, use Myers, otherwise first
168  * do a Patience. */
169 const struct diff_config diff_config_myers_then_patience = {
170 	.atomize_func = diff_atomize_text_by_line,
171 	.algo = &myers_then_patience,
172 };
173 
174 /* Directly force Patience as a first divider of the source file. */
175 const struct diff_config diff_config_patience = {
176 	.atomize_func = diff_atomize_text_by_line,
177 	.algo = &patience,
178 };
179 
180 /* Directly force Patience as a first divider of the source file. */
181 const struct diff_config diff_config_no_algo = {
182 	.atomize_func = diff_atomize_text_by_line,
183 };
184 
185 int
186 diffreg(char *file1, char *file2, enum diffreg_algo algo, bool force_text,
187     bool ignore_whitespace, bool show_function_prototypes, int context_lines,
188     bool edscript)
189 {
190 	char *str1, *str2;
191 	FILE *f1, *f2;
192 	struct stat st1, st2;
193 	struct diff_input_info info = {
194 		.left_path = file1,
195 		.right_path = file2,
196 	};
197 	struct diff_data left = {}, right = {};
198 	struct diff_result *result = NULL;
199 	int rc;
200 	const struct diff_config *cfg;
201 	int diff_flags = 0;
202 	
203 	switch (algo) {
204 	default:
205 	case DIFFREG_ALGO_MYERS_THEN_MYERS_DIVIDE:
206 		cfg = &diff_config_myers_then_myers_divide;
207 		break;
208 	case DIFFREG_ALGO_MYERS_THEN_PATIENCE:
209 		cfg = &diff_config_myers_then_patience;
210 		break;
211 	case DIFFREG_ALGO_PATIENCE:
212 		cfg = &diff_config_patience;
213 		break;
214 	case DIFFREG_ALGO_NONE:
215 		cfg = &diff_config_no_algo;
216 		break;
217 	}
218 
219 	f1 = openfile(file1, &str1, &st1);
220 	f2 = openfile(file2, &str2, &st2);
221 
222 	if (force_text)
223 		diff_flags |= DIFF_FLAG_FORCE_TEXT_DATA;
224 	if (ignore_whitespace)
225 		diff_flags |= DIFF_FLAG_IGNORE_WHITESPACE;
226 	if (show_function_prototypes)
227 		diff_flags |= DIFF_FLAG_SHOW_PROTOTYPES;
228 
229 	rc = diff_atomize_file(&left, cfg, f1, str1, st1.st_size, diff_flags);
230 	if (rc)
231 		goto done;
232 	rc = diff_atomize_file(&right, cfg, f2, str2, st2.st_size, diff_flags);
233 	if (rc)
234 		goto done;
235 
236 	result = diff_main(cfg, &left, &right);
237 #if 0
238 	rc = diff_output_plain(stdout, &info, result);
239 #else
240 	if (edscript)
241 		rc = diff_output_edscript(NULL, stdout, &info, result);
242 	else {
243 		rc = diff_output_unidiff(NULL, stdout, &info, result,
244 		    context_lines);
245 	}
246 #endif
247 done:
248 	diff_result_free(result);
249 	diff_data_free(&left);
250 	diff_data_free(&right);
251 	if (str1)
252 		munmap(str1, st1.st_size);
253 	if (str2)
254 		munmap(str2, st2.st_size);
255 	fclose(f1);
256 	fclose(f2);
257 
258 	return rc;
259 }
260 
261 FILE *
262 openfile(const char *path, char **p, struct stat *st)
263 {
264 	FILE *f = NULL;
265 
266 	f = fopen(path, "r");
267 	if (f == NULL)
268 		err(2, "%s", path);
269 
270 	if (fstat(fileno(f), st) == -1)
271 		err(2, "%s", path);
272 
273 #ifndef DIFF_NO_MMAP
274 	*p = mmap(NULL, st->st_size, PROT_READ, MAP_PRIVATE, fileno(f), 0);
275 	if (*p == MAP_FAILED)
276 #endif
277 		*p = NULL; /* fall back on file I/O */
278 
279 	return f;
280 }