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 <inttypes.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, int, bool);
45 FILE *		 openfile(const char *, char **, struct stat *);
46 
47 __dead void
48 usage(void)
49 {
50 	fprintf(stderr,
51 		"usage: %s [-PQTwe] [-U n] file1 file2\n"
52 		"\n"
53 		"  -P   Use Patience Diff (slower but often nicer)\n"
54 		"  -Q   Use forward-Myers for small files, otherwise Patience\n"
55 		"  -T   Trivial algo: detect similar start and end only\n"
56 		"  -w   Ignore Whitespace\n"
57 		"  -U n Number of Context Lines\n"
58 		"  -e   Produce ed script output\n"
59 		, getprogname());
60 	exit(1);
61 }
62 
63 int
64 main(int argc, char *argv[])
65 {
66 	int ch, rc;
67 	bool ignore_whitespace = false;
68 	bool edscript = false;
69 	int context_lines = 3;
70 	enum diffreg_algo algo = DIFFREG_ALGO_MYERS_THEN_MYERS_DIVIDE;
71 
72 	while ((ch = getopt(argc, argv, "PQTwU:e")) != -1) {
73 		switch (ch) {
74 		case 'P':
75 			algo = DIFFREG_ALGO_PATIENCE;
76 			break;
77 		case 'Q':
78 			algo = DIFFREG_ALGO_MYERS_THEN_PATIENCE;
79 			break;
80 		case 'T':
81 			algo = DIFFREG_ALGO_NONE;
82 			break;
83 		case 'w':
84 			ignore_whitespace = true;
85 			break;
86 		case 'U':
87 			context_lines = atoi(optarg);
88 			break;
89 		case 'e':
90 			edscript = true;
91 			break;
92 		default:
93 			usage();
94 		}
95 	}
96 
97 	argc -= optind;
98 	argv += optind;
99 
100 	if (argc != 2)
101 		usage();
102 
103 	rc = diffreg(argv[0], argv[1], algo, ignore_whitespace,
104 	    context_lines, edscript);
105 	if (rc != DIFF_RC_OK) {
106 		fprintf(stderr, "diff: %s\n", strerror(rc));
107 		return 1;
108 	}
109 	return 0;
110 }
111 
112 const struct diff_algo_config myers_then_patience;
113 const struct diff_algo_config myers_then_myers_divide;
114 const struct diff_algo_config patience;
115 const struct diff_algo_config myers_divide;
116 
117 const struct diff_algo_config myers_then_patience = (struct diff_algo_config){
118 	.impl = diff_algo_myers,
119 	.permitted_state_size = 1024 * 1024 * sizeof(int),
120 	.fallback_algo = &patience,
121 };
122 
123 const struct diff_algo_config myers_then_myers_divide =
124 	(struct diff_algo_config){
125 	.impl = diff_algo_myers,
126 	.permitted_state_size = 1024 * 1024 * sizeof(int),
127 	.fallback_algo = &myers_divide,
128 };
129 
130 const struct diff_algo_config patience = (struct diff_algo_config){
131 	.impl = diff_algo_patience,
132 	/* After subdivision, do Patience again: */
133 	.inner_algo = &patience,
134 	/* If subdivision failed, do Myers Divide et Impera: */
135 	.fallback_algo = &myers_then_myers_divide,
136 };
137 
138 const struct diff_algo_config myers_divide = (struct diff_algo_config){
139 	.impl = diff_algo_myers_divide,
140 	/* When division succeeded, start from the top: */
141 	.inner_algo = &myers_then_myers_divide,
142 	/* (fallback_algo = NULL implies diff_algo_none). */
143 };
144 
145 const struct diff_algo_config no_algo = (struct diff_algo_config){
146 	.impl = diff_algo_none,
147 };
148 
149 /* If the state for a forward-Myers is small enough, use Myers, otherwise first
150  * do a Myers-divide. */
151 const struct diff_config diff_config_myers_then_myers_divide = {
152 	.atomize_func = diff_atomize_text_by_line,
153 	.algo = &myers_then_myers_divide,
154 };
155 
156 /* If the state for a forward-Myers is small enough, use Myers, otherwise first
157  * do a Patience. */
158 const struct diff_config diff_config_myers_then_patience = {
159 	.atomize_func = diff_atomize_text_by_line,
160 	.algo = &myers_then_patience,
161 };
162 
163 /* Directly force Patience as a first divider of the source file. */
164 const struct diff_config diff_config_patience = {
165 	.atomize_func = diff_atomize_text_by_line,
166 	.algo = &patience,
167 };
168 
169 /* Directly force Patience as a first divider of the source file. */
170 const struct diff_config diff_config_no_algo = {
171 	.atomize_func = diff_atomize_text_by_line,
172 };
173 
174 int
175 diffreg(char *file1, char *file2, enum diffreg_algo algo, bool ignore_whitespace,
176     int context_lines, bool edscript)
177 {
178 	char *str1, *str2;
179 	FILE *f1, *f2;
180 	struct stat st1, st2;
181 	struct diff_input_info info = {
182 		.left_path = file1,
183 		.right_path = file2,
184 	};
185 	struct diff_result *result;
186 	int rc;
187 	const struct diff_config *cfg;
188 	int diff_flags = 0;
189 	
190 	switch (algo) {
191 	default:
192 	case DIFFREG_ALGO_MYERS_THEN_MYERS_DIVIDE:
193 		cfg = &diff_config_myers_then_myers_divide;
194 		break;
195 	case DIFFREG_ALGO_MYERS_THEN_PATIENCE:
196 		cfg = &diff_config_myers_then_patience;
197 		break;
198 	case DIFFREG_ALGO_PATIENCE:
199 		cfg = &diff_config_patience;
200 		break;
201 	case DIFFREG_ALGO_NONE:
202 		cfg = &diff_config_no_algo;
203 		break;
204 	}
205 
206 	f1 = openfile(file1, &str1, &st1);
207 	f2 = openfile(file2, &str2, &st2);
208 
209 	if (ignore_whitespace)
210 		diff_flags |= DIFF_FLAG_IGNORE_WHITESPACE;
211 
212 	result = diff_main(cfg, f1, str1, st1.st_size, f2, str2, st2.st_size,
213 	    diff_flags);
214 #if 0
215 	rc = diff_output_plain(stdout, &info, result);
216 #else
217 	if (edscript)
218 		rc = diff_output_edscript(NULL, stdout, &info, result);
219 	else {
220 		rc = diff_output_unidiff(NULL, stdout, &info, result,
221 		    context_lines);
222 	}
223 #endif
224 	diff_result_free(result);
225 
226 	if (str1)
227 		munmap(str1, st1.st_size);
228 	if (str2)
229 		munmap(str2, st2.st_size);
230 	fclose(f1);
231 	fclose(f2);
232 
233 	return rc;
234 }
235 
236 FILE *
237 openfile(const char *path, char **p, struct stat *st)
238 {
239 	FILE *f = NULL;
240 
241 	f = fopen(path, "r");
242 	if (f == NULL)
243 		err(2, "%s", path);
244 
245 	if (fstat(fileno(f), st) == -1)
246 		err(2, "%s", path);
247 
248 #ifndef DIFF_NO_MMAP
249 	*p = mmap(NULL, st->st_size, PROT_READ, MAP_PRIVATE, fileno(f), 0);
250 	if (*p == MAP_FAILED)
251 #endif
252 		*p = NULL; /* fall back on file I/O */
253 
254 	return f;
255 }