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