path: root/editors/diff.c (plain)
blob: 1961de607ebaac9efb0e73ed5dbddf86939bfedd

1	/* vi: set sw=4 ts=4: */
2	/*
3	* Mini diff implementation for busybox, adapted from OpenBSD diff.
4	*
5	* Copyright (C) 2010 by Matheus Izvekov <mizvekov@gmail.com>
6	* Copyright (C) 2006 by Robert Sullivan <cogito.ergo.cogito@hotmail.com>
7	* Copyright (c) 2003 Todd C. Miller <Todd.Miller@courtesan.com>
8	*
9	* Sponsored in part by the Defense Advanced Research Projects
10	* Agency (DARPA) and Air Force Research Laboratory, Air Force
11	* Materiel Command, USAF, under agreement number F39502-99-1-0512.
12	*
13	* Licensed under GPLv2 or later, see file LICENSE in this source tree.
14	*/
15
16	/*
17	* The following code uses an algorithm due to Harold Stone,
18	* which finds a pair of longest identical subsequences in
19	* the two files.
20	*
21	* The major goal is to generate the match vector J.
22	* J[i] is the index of the line in file1 corresponding
23	* to line i in file0. J[i] = 0 if there is no
24	* such line in file1.
25	*
26	* Lines are hashed so as to work in core. All potential
27	* matches are located by sorting the lines of each file
28	* on the hash (called "value"). In particular, this
29	* collects the equivalence classes in file1 together.
30	* Subroutine equiv replaces the value of each line in
31	* file0 by the index of the first element of its
32	* matching equivalence in (the reordered) file1.
33	* To save space equiv squeezes file1 into a single
34	* array member in which the equivalence classes
35	* are simply concatenated, except that their first
36	* members are flagged by changing sign.
37	*
38	* Next the indices that point into member are unsorted into
39	* array class according to the original order of file0.
40	*
41	* The cleverness lies in routine stone. This marches
42	* through the lines of file0, developing a vector klist
43	* of "k-candidates". At step i a k-candidate is a matched
44	* pair of lines x,y (x in file0, y in file1) such that
45	* there is a common subsequence of length k
46	* between the first i lines of file0 and the first y
47	* lines of file1, but there is no such subsequence for
48	* any smaller y. x is the earliest possible mate to y
49	* that occurs in such a subsequence.
50	*
51	* Whenever any of the members of the equivalence class of
52	* lines in file1 matable to a line in file0 has serial number
53	* less than the y of some k-candidate, that k-candidate
54	* with the smallest such y is replaced. The new
55	* k-candidate is chained (via pred) to the current
56	* k-1 candidate so that the actual subsequence can
57	* be recovered. When a member has serial number greater
58	* that the y of all k-candidates, the klist is extended.
59	* At the end, the longest subsequence is pulled out
60	* and placed in the array J by unravel
61	*
62	* With J in hand, the matches there recorded are
63	* checked against reality to assure that no spurious
64	* matches have crept in due to hashing. If they have,
65	* they are broken, and "jackpot" is recorded--a harmless
66	* matter except that a true match for a spuriously
67	* mated line may now be unnecessarily reported as a change.
68	*
69	* Much of the complexity of the program comes simply
70	* from trying to minimize core utilization and
71	* maximize the range of doable problems by dynamically
72	* allocating what is needed and reusing what is not.
73	* The core requirements for problems larger than somewhat
74	* are (in words) 2*length(file0) + length(file1) +
75	* 3*(number of k-candidates installed), typically about
76	* 6n words for files of length n.
77	*/
78
79	//config:config DIFF
80	//config: bool "diff"
81	//config: default y
82	//config: help
83	//config: diff compares two files or directories and outputs the
84	//config: differences between them in a form that can be given to
85	//config: the patch command.
86	//config:
87	//config:config FEATURE_DIFF_LONG_OPTIONS
88	//config: bool "Enable long options"
89	//config: default y
90	//config: depends on DIFF && LONG_OPTS
91	//config: help
92	//config: Enable use of long options.
93	//config:
94	//config:config FEATURE_DIFF_DIR
95	//config: bool "Enable directory support"
96	//config: default y
97	//config: depends on DIFF
98	//config: help
99	//config: This option enables support for directory and subdirectory
100	//config: comparison.
101
102	//kbuild:lib-$(CONFIG_DIFF) += diff.o
103
104	//applet:IF_DIFF(APPLET(diff, BB_DIR_USR_BIN, BB_SUID_DROP))
105
106	//usage:#define diff_trivial_usage
107	//usage: "[-abBdiNqrTstw] [-L LABEL] [-S FILE] [-U LINES] FILE1 FILE2"
108	//usage:#define diff_full_usage "\n\n"
109	//usage: "Compare files line by line and output the differences between them.\n"
110	//usage: "This implementation supports unified diffs only.\n"
111	//usage: "\n -a Treat all files as text"
112	//usage: "\n -b Ignore changes in the amount of whitespace"
113	//usage: "\n -B Ignore changes whose lines are all blank"
114	//usage: "\n -d Try hard to find a smaller set of changes"
115	//usage: "\n -i Ignore case differences"
116	//usage: "\n -L Use LABEL instead of the filename in the unified header"
117	//usage: "\n -N Treat absent files as empty"
118	//usage: "\n -q Output only whether files differ"
119	//usage: "\n -r Recurse"
120	//usage: "\n -S Start with FILE when comparing directories"
121	//usage: "\n -T Make tabs line up by prefixing a tab when necessary"
122	//usage: "\n -s Report when two files are the same"
123	//usage: "\n -t Expand tabs to spaces in output"
124	//usage: "\n -U Output LINES lines of context"
125	//usage: "\n -w Ignore all whitespace"
126
127	#include "libbb.h"
128
129	#if 0
130	# define dbg_error_msg(...) bb_error_msg(__VA_ARGS__)
131	#else
132	# define dbg_error_msg(...) ((void)0)
133	#endif
134
135	enum { /* print_status() and diffreg() return values */
136	STATUS_SAME, /* files are the same */
137	STATUS_DIFFER, /* files differ */
138	STATUS_BINARY, /* binary files differ */
139	};
140
141	enum { /* Commandline flags */
142	FLAG_a,
143	FLAG_b,
144	FLAG_d,
145	FLAG_i,
146	FLAG_L, /* never used, handled by getopt32 */
147	FLAG_N,
148	FLAG_q,
149	FLAG_r,
150	FLAG_s,
151	FLAG_S, /* never used, handled by getopt32 */
152	FLAG_t,
153	FLAG_T,
154	FLAG_U, /* never used, handled by getopt32 */
155	FLAG_w,
156	FLAG_u, /* ignored, this is the default */
157	FLAG_p, /* not implemented */
158	FLAG_B,
159	FLAG_E, /* not implemented */
160	};
161	#define FLAG(x) (1 << FLAG_##x)
162
163	/* We cache file position to avoid excessive seeking */
164	typedef struct FILE_and_pos_t {
165	FILE *ft_fp;
166	off_t ft_pos;
167	} FILE_and_pos_t;
168
169	struct globals {
170	smallint exit_status;
171	int opt_U_context;
172	const char *other_dir;
173	char *label[2];
174	struct stat stb[2];
175	};
176	#define G (*ptr_to_globals)
177	#define exit_status (G.exit_status )
178	#define opt_U_context (G.opt_U_context )
179	#define label (G.label )
180	#define stb (G.stb )
181	#define INIT_G() do { \
182	SET_PTR_TO_GLOBALS(xzalloc(sizeof(G))); \
183	opt_U_context = 3; \
184	} while (0)
185
186	typedef int token_t;
187
188	enum {
189	/* Public */
190	TOK_EMPTY = 1 << 9, /* Line fully processed, you can proceed to the next */
191	TOK_EOF = 1 << 10, /* File ended */
192	/* Private (Only to be used by read_token() */
193	TOK_EOL = 1 << 11, /* we saw EOL (sticky) */
194	TOK_SPACE = 1 << 12, /* used -b code, means we are skipping spaces */
195	SHIFT_EOF = (sizeof(token_t)*8 - 8) - 1,
196	CHAR_MASK = 0x1ff, /* 8th bit is used to distinguish EOF from 0xff */
197	};
198
199	/* Restores full EOF from one 8th bit: */
200	//#define TOK2CHAR(t) (((t) << SHIFT_EOF) >> SHIFT_EOF)
201	/* We don't really need the above, we only need to have EOF != any_real_char: */
202	#define TOK2CHAR(t) ((t) & CHAR_MASK)
203
204	static void seek_ft(FILE_and_pos_t *ft, off_t pos)
205	{
206	if (ft->ft_pos != pos) {
207	ft->ft_pos = pos;
208	fseeko(ft->ft_fp, pos, SEEK_SET);
209	}
210	}
211
212	/* Reads tokens from given fp, handling -b and -w flags
213	* The user must reset tok every line start
214	*/
215	static int read_token(FILE_and_pos_t *ft, token_t tok)
216	{
217	tok |= TOK_EMPTY;
218	while (!(tok & TOK_EOL)) {
219	bool is_space;
220	int t;
221
222	t = fgetc(ft->ft_fp);
223	if (t != EOF)
224	ft->ft_pos++;
225	is_space = (t == EOF || isspace(t));
226
227	/* If t == EOF (-1), set both TOK_EOF and TOK_EOL */
228	tok |= (t & (TOK_EOF + TOK_EOL));
229	/* Only EOL? */
230	if (t == '\n')
231	tok |= TOK_EOL;
232
233	if (option_mask32 & FLAG(i)) /* Handcoded tolower() */
234	t = (t >= 'A' && t <= 'Z') ? t - ('A' - 'a') : t;
235
236	if ((option_mask32 & FLAG(w)) && is_space)
237	continue;
238
239	/* Trim char value to low 9 bits */
240	t &= CHAR_MASK;
241
242	if (option_mask32 & FLAG(b)) {
243	/* Was prev char whitespace? */
244	if (tok & TOK_SPACE) { /* yes */
245	if (is_space) /* this one too, ignore it */
246	continue;
247	tok &= ~TOK_SPACE;
248	} else if (is_space) {
249	/* 1st whitespace char.
250	* Set TOK_SPACE and replace char by ' ' */
251	t = TOK_SPACE + ' ';
252	}
253	}
254	/* Clear EMPTY */
255	tok &= ~(TOK_EMPTY + CHAR_MASK);
256	/* Assign char value (low 9 bits) and maybe set TOK_SPACE */
257	tok |= t;
258	break;
259	}
260	#if 0
261	bb_error_msg("fp:%p tok:%x '%c'%s%s%s%s", fp, tok, tok & 0xff
262	, tok & TOK_EOF ? " EOF" : ""
263	, tok & TOK_EOL ? " EOL" : ""
264	, tok & TOK_EMPTY ? " EMPTY" : ""
265	, tok & TOK_SPACE ? " SPACE" : ""
266	);
267	#endif
268	return tok;
269	}
270
271	struct cand {
272	int x;
273	int y;
274	int pred;
275	};
276
277	static int search(const int *c, int k, int y, const struct cand *list)
278	{
279	int i, j;
280
281	if (list[c[k]].y < y) /* quick look for typical case */
282	return k + 1;
283
284	for (i = 0, j = k + 1;;) {
285	const int l = (i + j) >> 1;
286	if (l > i) {
287	const int t = list[c[l]].y;
288	if (t > y)
289	j = l;
290	else if (t < y)
291	i = l;
292	else
293	return l;
294	} else
295	return l + 1;
296	}
297	}
298
299	static unsigned isqrt(unsigned n)
300	{
301	unsigned x = 1;
302	while (1) {
303	const unsigned y = x;
304	x = ((n / x) + x) >> 1;
305	if (x <= (y + 1) && x >= (y - 1))
306	return x;
307	}
308	}
309
310	static void stone(const int *a, int n, const int *b, int *J, int pref)
311	{
312	const unsigned isq = isqrt(n);
313	const unsigned bound =
314	(option_mask32 & FLAG(d)) ? UINT_MAX : MAX(256, isq);
315	int clen = 1;
316	int clistlen = 100;
317	int k = 0;
318	struct cand *clist = xzalloc(clistlen * sizeof(clist[0]));
319	struct cand cand;
320	struct cand *q;
321	int *klist = xzalloc((n + 2) * sizeof(klist[0]));
322	/*clist[0] = (struct cand){0}; - xzalloc did it */
323	/*klist[0] = 0; */
324
325	for (cand.x = 1; cand.x <= n; cand.x++) {
326	int j = a[cand.x], oldl = 0;
327	unsigned numtries = 0;
328	if (j == 0)
329	continue;
330	cand.y = -b[j];
331	cand.pred = klist[0];
332	do {
333	int l, tc;
334	if (cand.y <= clist[cand.pred].y)
335	continue;
336	l = search(klist, k, cand.y, clist);
337	if (l != oldl + 1)
338	cand.pred = klist[l - 1];
339	if (l <= k && clist[klist[l]].y <= cand.y)
340	continue;
341	if (clen == clistlen) {
342	clistlen = clistlen * 11 / 10;
343	clist = xrealloc(clist, clistlen * sizeof(clist[0]));
344	}
345	clist[clen] = cand;
346	tc = klist[l];
347	klist[l] = clen++;
348	if (l <= k) {
349	cand.pred = tc;
350	oldl = l;
351	numtries++;
352	} else {
353	k++;
354	break;
355	}
356	} while ((cand.y = b[++j]) > 0 && numtries < bound);
357	}
358	/* Unravel */
359	for (q = clist + klist[k]; q->y; q = clist + q->pred)
360	J[q->x + pref] = q->y + pref;
361	free(klist);
362	free(clist);
363	}
364
365	struct line {
366	/* 'serial' is not used in the begining, so we reuse it
367	* to store line offsets, thus reducing memory pressure
368	*/
369	union {
370	unsigned serial;
371	off_t offset;
372	};
373	unsigned value;
374	};
375
376	static void equiv(struct line *a, int n, struct line *b, int m, int *c)
377	{
378	int i = 1, j = 1;
379
380	while (i <= n && j <= m) {
381	if (a[i].value < b[j].value)
382	a[i++].value = 0;
383	else if (a[i].value == b[j].value)
384	a[i++].value = j;
385	else
386	j++;
387	}
388	while (i <= n)
389	a[i++].value = 0;
390	b[m + 1].value = 0;
391	j = 0;
392	while (++j <= m) {
393	c[j] = -b[j].serial;
394	while (b[j + 1].value == b[j].value) {
395	j++;
396	c[j] = b[j].serial;
397	}
398	}
399	c[j] = -1;
400	}
401
402	static void unsort(const struct line *f, int l, int *b)
403	{
404	int i;
405	int *a = xmalloc((l + 1) * sizeof(a[0]));
406	for (i = 1; i <= l; i++)
407	a[f[i].serial] = f[i].value;
408	for (i = 1; i <= l; i++)
409	b[i] = a[i];
410	free(a);
411	}
412
413	static int line_compar(const void *a, const void *b)
414	{
415	#define l0 ((const struct line*)a)
416	#define l1 ((const struct line*)b)
417	int r = l0->value - l1->value;
418	if (r)
419	return r;
420	return l0->serial - l1->serial;
421	#undef l0
422	#undef l1
423	}
424
425	static void fetch(FILE_and_pos_t *ft, const off_t *ix, int a, int b, int ch)
426	{
427	int i, j, col;
428	for (i = a; i <= b; i++) {
429	seek_ft(ft, ix[i - 1]);
430	putchar(ch);
431	if (option_mask32 & FLAG(T))
432	putchar('\t');
433	for (j = 0, col = 0; j < ix[i] - ix[i - 1]; j++) {
434	int c = fgetc(ft->ft_fp);
435	if (c == EOF) {
436	printf("\n\\ No newline at end of file\n");
437	return;
438	}
439	ft->ft_pos++;
440	if (c == '\t' && (option_mask32 & FLAG(t)))
441	do putchar(' '); while (++col & 7);
442	else {
443	putchar(c);
444	col++;
445	}
446	}
447	}
448	}
449
450	/* Creates the match vector J, where J[i] is the index
451	* of the line in the new file corresponding to the line i
452	* in the old file. Lines start at 1 instead of 0, that value
453	* being used instead to denote no corresponding line.
454	* This vector is dynamically allocated and must be freed by the caller.
455	*
456	* * fp is an input parameter, where fp[0] and fp[1] are the open
457	* old file and new file respectively.
458	* * nlen is an output variable, where nlen[0] and nlen[1]
459	* gets the number of lines in the old and new file respectively.
460	* * ix is an output variable, where ix[0] and ix[1] gets
461	* assigned dynamically allocated vectors of the offsets of the lines
462	* of the old and new file respectively. These must be freed by the caller.
463	*/
464	static NOINLINE int *create_J(FILE_and_pos_t ft[2], int nlen[2], off_t *ix[2])
465	{
466	int *J, slen[2], *class, *member;
467	struct line *nfile[2], *sfile[2];
468	int pref = 0, suff = 0, i, j, delta;
469
470	/* Lines of both files are hashed, and in the process
471	* their offsets are stored in the array ix[fileno]
472	* where fileno == 0 points to the old file, and
473	* fileno == 1 points to the new one.
474	*/
475	for (i = 0; i < 2; i++) {
476	unsigned hash;
477	token_t tok;
478	int sz = 100;
479	nfile[i] = xmalloc((sz + 3) * sizeof(nfile[i][0]));
480	/* ft gets here without the correct position, cant use seek_ft */
481	ft[i].ft_pos = 0;
482	fseeko(ft[i].ft_fp, 0, SEEK_SET);
483
484	nlen[i] = 0;
485	/* We could zalloc nfile, but then zalloc starts showing in gprof at ~1% */
486	nfile[i][0].offset = 0;
487	goto start; /* saves code */
488	while (1) {
489	tok = read_token(&ft[i], tok);
490	if (!(tok & TOK_EMPTY)) {
491	/* Hash algorithm taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578. */
492	/*hash = hash * 128 - hash + TOK2CHAR(tok);
493	* gcc insists on optimizing above to "hash * 127 + ...", thus... */
494	unsigned o = hash - TOK2CHAR(tok);
495	hash = hash * 128 - o; /* we want SPEED here */
496	continue;
497	}
498	if (nlen[i]++ == sz) {
499	sz = sz * 3 / 2;
500	nfile[i] = xrealloc(nfile[i], (sz + 3) * sizeof(nfile[i][0]));
501	}
502	/* line_compar needs hashes fit into positive int */
503	nfile[i][nlen[i]].value = hash & INT_MAX;
504	/* like ftello(ft[i].ft_fp) but faster (avoids lseek syscall) */
505	nfile[i][nlen[i]].offset = ft[i].ft_pos;
506	if (tok & TOK_EOF) {
507	/* EOF counts as a token, so we have to adjust it here */
508	nfile[i][nlen[i]].offset++;
509	break;
510	}
511	start:
512	hash = tok = 0;
513	}
514	/* Exclude lone EOF line from the end of the file, to make fetch()'s job easier */
515	if (nfile[i][nlen[i]].offset - nfile[i][nlen[i] - 1].offset == 1)
516	nlen[i]--;
517	/* Now we copy the line offsets into ix */
518	ix[i] = xmalloc((nlen[i] + 2) * sizeof(ix[i][0]));
519	for (j = 0; j < nlen[i] + 1; j++)
520	ix[i][j] = nfile[i][j].offset;
521	}
522
523	/* length of prefix and suffix is calculated */
524	for (; pref < nlen[0] && pref < nlen[1] &&
525	nfile[0][pref + 1].value == nfile[1][pref + 1].value;
526	pref++);
527	for (; suff < nlen[0] - pref && suff < nlen[1] - pref &&
528	nfile[0][nlen[0] - suff].value == nfile[1][nlen[1] - suff].value;
529	suff++);
530	/* Arrays are pruned by the suffix and prefix length,
531	* the result being sorted and stored in sfile[fileno],
532	* and their sizes are stored in slen[fileno]
533	*/
534	for (j = 0; j < 2; j++) {
535	sfile[j] = nfile[j] + pref;
536	slen[j] = nlen[j] - pref - suff;
537	for (i = 0; i <= slen[j]; i++)
538	sfile[j][i].serial = i;
539	qsort(sfile[j] + 1, slen[j], sizeof(*sfile[j]), line_compar);
540	}
541	/* nfile arrays are reused to reduce memory pressure
542	* The #if zeroed out section performs the same task as the
543	* one in the #else section.
544	* Peak memory usage is higher, but one array copy is avoided
545	* by not using unsort()
546	*/
547	#if 0
548	member = xmalloc((slen[1] + 2) * sizeof(member[0]));
549	equiv(sfile[0], slen[0], sfile[1], slen[1], member);
550	free(nfile[1]);
551
552	class = xmalloc((slen[0] + 1) * sizeof(class[0]));
553	for (i = 1; i <= slen[0]; i++) /* Unsorting */
554	class[sfile[0][i].serial] = sfile[0][i].value;
555	free(nfile[0]);
556	#else
557	member = (int *)nfile[1];
558	equiv(sfile[0], slen[0], sfile[1], slen[1], member);
559	member = xrealloc(member, (slen[1] + 2) * sizeof(member[0]));
560
561	class = (int *)nfile[0];
562	unsort(sfile[0], slen[0], (int *)nfile[0]);
563	class = xrealloc(class, (slen[0] + 2) * sizeof(class[0]));
564	#endif
565	J = xmalloc((nlen[0] + 2) * sizeof(J[0]));
566	/* The elements of J which fall inside the prefix and suffix regions
567	* are marked as unchanged, while the ones which fall outside
568	* are initialized with 0 (no matches), so that function stone can
569	* then assign them their right values
570	*/
571	for (i = 0, delta = nlen[1] - nlen[0]; i <= nlen[0]; i++)
572	J[i] = i <= pref ? i :
573	i > (nlen[0] - suff) ? (i + delta) : 0;
574	/* Here the magic is performed */
575	stone(class, slen[0], member, J, pref);
576	J[nlen[0] + 1] = nlen[1] + 1;
577
578	free(class);
579	free(member);
580
581	/* Both files are rescanned, in an effort to find any lines
582	* which, due to limitations intrinsic to any hashing algorithm,
583	* are different but ended up confounded as the same
584	*/
585	for (i = 1; i <= nlen[0]; i++) {
586	if (!J[i])
587	continue;
588
589	seek_ft(&ft[0], ix[0][i - 1]);
590	seek_ft(&ft[1], ix[1][J[i] - 1]);
591
592	for (j = J[i]; i <= nlen[0] && J[i] == j; i++, j++) {
593	token_t tok0 = 0, tok1 = 0;
594	do {
595	tok0 = read_token(&ft[0], tok0);
596	tok1 = read_token(&ft[1], tok1);
597
598	if (((tok0 ^ tok1) & TOK_EMPTY) != 0 /* one is empty (not both) */
599	|| (!(tok0 & TOK_EMPTY) && TOK2CHAR(tok0) != TOK2CHAR(tok1))
600	) {
601	J[i] = 0; /* Break the correspondence */
602	}
603	} while (!(tok0 & tok1 & TOK_EMPTY));
604	}
605	}
606
607	return J;
608	}
609
610	static bool diff(FILE* fp[2], char *file[2])
611	{
612	int nlen[2];
613	off_t *ix[2];
614	FILE_and_pos_t ft[2];
615	typedef struct { int a, b; } vec_t[2];
616	vec_t *vec = NULL;
617	int i = 1, j, k, idx = -1;
618	bool anychange = false;
619	int *J;
620
621	ft[0].ft_fp = fp[0];
622	ft[1].ft_fp = fp[1];
623	/* note that ft[i].ft_pos is unintitalized, create_J()
624	* must not assume otherwise */
625	J = create_J(ft, nlen, ix);
626
627	do {
628	bool nonempty = false;
629
630	while (1) {
631	vec_t v;
632
633	for (v[0].a = i; v[0].a <= nlen[0] && J[v[0].a] == J[v[0].a - 1] + 1; v[0].a++)
634	continue;
635	v[1].a = J[v[0].a - 1] + 1;
636
637	for (v[0].b = v[0].a - 1; v[0].b < nlen[0] && !J[v[0].b + 1]; v[0].b++)
638	continue;
639	v[1].b = J[v[0].b + 1] - 1;
640	/*
641	* Indicate that there is a difference between lines a and b of the 'from' file
642	* to get to lines c to d of the 'to' file. If a is greater than b then there
643	* are no lines in the 'from' file involved and this means that there were
644	* lines appended (beginning at b). If c is greater than d then there are
645	* lines missing from the 'to' file.
646	*/
647	if (v[0].a <= v[0].b || v[1].a <= v[1].b) {
648	/*
649	* If this change is more than 'context' lines from the
650	* previous change, dump the record and reset it.
651	*/
652	int ct = (2 * opt_U_context) + 1;
653	if (idx >= 0
654	&& v[0].a > vec[idx][0].b + ct
655	&& v[1].a > vec[idx][1].b + ct
656	) {
657	break;
658	}
659
660	for (j = 0; j < 2; j++)
661	for (k = v[j].a; k < v[j].b; k++)
662	nonempty |= (ix[j][k+1] - ix[j][k] != 1);
663
664	vec = xrealloc_vector(vec, 6, ++idx);
665	memcpy(vec[idx], v, sizeof(v));
666	}
667
668	i = v[0].b + 1;
669	if (i > nlen[0])
670	break;
671	J[v[0].b] = v[1].b;
672	}
673	if (idx < 0 || ((option_mask32 & FLAG(B)) && !nonempty))
674	goto cont;
675	if (!(option_mask32 & FLAG(q))) {
676	int lowa;
677	vec_t span, *cvp = vec;
678
679	if (!anychange) {
680	/* Print the context/unidiff header first time through */
681	printf("--- %s\n", label[0] ? label[0] : file[0]);
682	printf("+++ %s\n", label[1] ? label[1] : file[1]);
683	}
684
685	printf("@@");
686	for (j = 0; j < 2; j++) {
687	int a = span[j].a = MAX(1, (*cvp)[j].a - opt_U_context);
688	int b = span[j].b = MIN(nlen[j], vec[idx][j].b + opt_U_context);
689
690	printf(" %c%d", j ? '+' : '-', MIN(a, b));
691	if (a == b)
692	continue;
693	printf(",%d", (a < b) ? b - a + 1 : 0);
694	}
695	printf(" @@\n");
696	/*
697	* Output changes in "unified" diff format--the old and new lines
698	* are printed together.
699	*/
700	for (lowa = span[0].a; ; lowa = (*cvp++)[0].b + 1) {
701	bool end = cvp > &vec[idx];
702	fetch(&ft[0], ix[0], lowa, end ? span[0].b : (*cvp)[0].a - 1, ' ');
703	if (end)
704	break;
705	for (j = 0; j < 2; j++)
706	fetch(&ft[j], ix[j], (*cvp)[j].a, (*cvp)[j].b, j ? '+' : '-');
707	}
708	}
709	anychange = true;
710	cont:
711	idx = -1;
712	} while (i <= nlen[0]);
713
714	free(vec);
715	free(ix[0]);
716	free(ix[1]);
717	free(J);
718	return anychange;
719	}
720
721	static int diffreg(char *file[2])
722	{
723	FILE *fp[2];
724	bool binary = false, differ = false;
725	int status = STATUS_SAME, i;
726
727	fp[0] = stdin;
728	fp[1] = stdin;
729	for (i = 0; i < 2; i++) {
730	int fd = open_or_warn_stdin(file[i]);
731	if (fd == -1)
732	goto out;
733	/* Our diff implementation is using seek.
734	* When we meet non-seekable file, we must make a temp copy.
735	*/
736	if (lseek(fd, 0, SEEK_SET) == -1 && errno == ESPIPE) {
737	/* really should use $TMPDIR, but not usually set on android anyway
738	here with ifdef, android will use "/data/local/tmp/difXXXXXX"
739	*/
740	char name[] =
741	#ifdef __BIONIC__
742	"/data/local"
743	#endif
744	"/tmp/difXXXXXX";
745	int fd_tmp = xmkstemp(name);
746
747	unlink(name);
748	if (bb_copyfd_eof(fd, fd_tmp) < 0)
749	xfunc_die();
750	if (fd) /* Prevents closing of stdin */
751	close(fd);
752	fd = fd_tmp;
753	}
754	fp[i] = fdopen(fd, "r");
755	}
756
757	while (1) {
758	const size_t sz = COMMON_BUFSIZE / 2;
759	char *const buf0 = bb_common_bufsiz1;
760	char *const buf1 = buf0 + sz;
761	int j, k;
762	i = fread(buf0, 1, sz, fp[0]);
763	j = fread(buf1, 1, sz, fp[1]);
764	if (i != j) {
765	differ = true;
766	i = MIN(i, j);
767	}
768	if (i == 0)
769	break;
770	for (k = 0; k < i; k++) {
771	if (!buf0[k] || !buf1[k])
772	binary = true;
773	if (buf0[k] != buf1[k])
774	differ = true;
775	}
776	}
777	if (differ) {
778	if (binary && !(option_mask32 & FLAG(a)))
779	status = STATUS_BINARY;
780	else if (diff(fp, file))
781	status = STATUS_DIFFER;
782	}
783	if (status != STATUS_SAME)
784	exit_status |= 1;
785	out:
786	fclose_if_not_stdin(fp[0]);
787	fclose_if_not_stdin(fp[1]);
788
789	return status;
790	}
791
792	static void print_status(int status, char *path[2])
793	{
794	switch (status) {
795	case STATUS_BINARY:
796	case STATUS_DIFFER:
797	if ((option_mask32 & FLAG(q)) || status == STATUS_BINARY)
798	printf("Files %s and %s differ\n", path[0], path[1]);
799	break;
800	case STATUS_SAME:
801	if (option_mask32 & FLAG(s))
802	printf("Files %s and %s are identical\n", path[0], path[1]);
803	break;
804	}
805	}
806
807	#if ENABLE_FEATURE_DIFF_DIR
808	struct dlist {
809	size_t len;
810	int s, e;
811	char **dl;
812	};
813
814	/* This function adds a filename to dl, the directory listing. */
815	static int FAST_FUNC add_to_dirlist(const char *filename,
816	struct stat *sb UNUSED_PARAM,
817	void *userdata, int depth UNUSED_PARAM)
818	{
819	struct dlist *const l = userdata;
820	const char *file = filename + l->len;
821	while (*file == '/')
822	file++;
823	l->dl = xrealloc_vector(l->dl, 6, l->e);
824	l->dl[l->e] = xstrdup(file);
825	l->e++;
826	return TRUE;
827	}
828
829	/* If recursion is not set, this function adds the directory
830	* to the list and prevents recursive_action from recursing into it.
831	*/
832	static int FAST_FUNC skip_dir(const char *filename,
833	struct stat *sb, void *userdata,
834	int depth)
835	{
836	if (!(option_mask32 & FLAG(r)) && depth) {
837	add_to_dirlist(filename, sb, userdata, depth);
838	return SKIP;
839	}
840	if (!(option_mask32 & FLAG(N))) {
841	/* -r without -N: no need to recurse into dirs
842	* which do not exist on the "other side".
843	* Testcase: diff -r /tmp /
844	* (it would recurse deep into /proc without this code) */
845	struct dlist *const l = userdata;
846	filename += l->len;
847	if (filename[0]) {
848	struct stat osb;
849	char *othername = concat_path_file(G.other_dir, filename);
850	int r = stat(othername, &osb);
851	free(othername);
852	if (r != 0 || !S_ISDIR(osb.st_mode)) {
853	/* other dir doesn't have similarly named
854	* directory, don't recurse; return 1 upon
855	* exit, just like diffutils' diff */
856	exit_status |= 1;
857	return SKIP;
858	}
859	}
860	}
861	return TRUE;
862	}
863
864	static void diffdir(char *p[2], const char *s_start)
865	{
866	struct dlist list[2];
867	int i;
868
869	memset(&list, 0, sizeof(list));
870	for (i = 0; i < 2; i++) {
871	/*list[i].s = list[i].e = 0; - memset did it */
872	/*list[i].dl = NULL; */
873
874	G.other_dir = p[1 - i];
875	/* We need to trim root directory prefix.
876	* Using list.len to specify its length,
877	* add_to_dirlist will remove it. */
878	list[i].len = strlen(p[i]);
879	recursive_action(p[i], ACTION_RECURSE | ACTION_FOLLOWLINKS,
880	add_to_dirlist, skip_dir, &list[i], 0);
881	/* Sort dl alphabetically.
882	* GNU diff does this ignoring any number of trailing dots.
883	* We don't, so for us dotted files almost always are
884	* first on the list.
885	*/
886	qsort_string_vector(list[i].dl, list[i].e);
887	/* If -S was set, find the starting point. */
888	if (!s_start)
889	continue;
890	while (list[i].s < list[i].e && strcmp(list[i].dl[list[i].s], s_start) < 0)
891	list[i].s++;
892	}
893	/* Now that both dirlist1 and dirlist2 contain sorted directory
894	* listings, we can start to go through dirlist1. If both listings
895	* contain the same file, then do a normal diff. Otherwise, behaviour
896	* is determined by whether the -N flag is set. */
897	while (1) {
898	char *dp[2];
899	int pos;
900	int k;
901
902	dp[0] = list[0].s < list[0].e ? list[0].dl[list[0].s] : NULL;
903	dp[1] = list[1].s < list[1].e ? list[1].dl[list[1].s] : NULL;
904	if (!dp[0] && !dp[1])
905	break;
906	pos = !dp[0] ? 1 : (!dp[1] ? -1 : strcmp(dp[0], dp[1]));
907	k = pos > 0;
908	if (pos && !(option_mask32 & FLAG(N))) {
909	printf("Only in %s: %s\n", p[k], dp[k]);
910	exit_status |= 1;
911	} else {
912	char *fullpath[2], *path[2]; /* if -N */
913
914	for (i = 0; i < 2; i++) {
915	if (pos == 0 || i == k) {
916	path[i] = fullpath[i] = concat_path_file(p[i], dp[i]);
917	stat(fullpath[i], &stb[i]);
918	} else {
919	fullpath[i] = concat_path_file(p[i], dp[1 - i]);
920	path[i] = (char *)bb_dev_null;
921	}
922	}
923	if (pos)
924	stat(fullpath[k], &stb[1 - k]);
925
926	if (S_ISDIR(stb[0].st_mode) && S_ISDIR(stb[1].st_mode))
927	printf("Common subdirectories: %s and %s\n", fullpath[0], fullpath[1]);
928	else if (!S_ISREG(stb[0].st_mode) && !S_ISDIR(stb[0].st_mode))
929	printf("File %s is not a regular file or directory and was skipped\n", fullpath[0]);
930	else if (!S_ISREG(stb[1].st_mode) && !S_ISDIR(stb[1].st_mode))
931	printf("File %s is not a regular file or directory and was skipped\n", fullpath[1]);
932	else if (S_ISDIR(stb[0].st_mode) != S_ISDIR(stb[1].st_mode)) {
933	if (S_ISDIR(stb[0].st_mode))
934	printf("File %s is a %s while file %s is a %s\n", fullpath[0], "directory", fullpath[1], "regular file");
935	else
936	printf("File %s is a %s while file %s is a %s\n", fullpath[0], "regular file", fullpath[1], "directory");
937	} else
938	print_status(diffreg(path), fullpath);
939
940	free(fullpath[0]);
941	free(fullpath[1]);
942	}
943	free(dp[k]);
944	list[k].s++;
945	if (pos == 0) {
946	free(dp[1 - k]);
947	list[1 - k].s++;
948	}
949	}
950	if (ENABLE_FEATURE_CLEAN_UP) {
951	free(list[0].dl);
952	free(list[1].dl);
953	}
954	}
955	#endif
956
957	#if ENABLE_FEATURE_DIFF_LONG_OPTIONS
958	static const char diff_longopts[] ALIGN1 =
959	"ignore-case\0" No_argument "i"
960	"ignore-tab-expansion\0" No_argument "E"
961	"ignore-space-change\0" No_argument "b"
962	"ignore-all-space\0" No_argument "w"
963	"ignore-blank-lines\0" No_argument "B"
964	"text\0" No_argument "a"
965	"unified\0" Required_argument "U"
966	"label\0" Required_argument "L"
967	"show-c-function\0" No_argument "p"
968	"brief\0" No_argument "q"
969	"expand-tabs\0" No_argument "t"
970	"initial-tab\0" No_argument "T"
971	"recursive\0" No_argument "r"
972	"new-file\0" No_argument "N"
973	"report-identical-files\0" No_argument "s"
974	"starting-file\0" Required_argument "S"
975	"minimal\0" No_argument "d"
976	;
977	#endif
978
979	int diff_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
980	int diff_main(int argc UNUSED_PARAM, char **argv)
981	{
982	int gotstdin = 0, i;
983	char *file[2], *s_start = NULL;
984	llist_t *L_arg = NULL;
985
986	INIT_G();
987
988	/* exactly 2 params; collect multiple -L <label>; -U N */
989	opt_complementary = "=2:L::U+";
990	#if ENABLE_FEATURE_DIFF_LONG_OPTIONS
991	applet_long_options = diff_longopts;
992	#endif
993	getopt32(argv, "abdiL:NqrsS:tTU:wupBE",
994	&L_arg, &s_start, &opt_U_context);
995	argv += optind;
996	while (L_arg)
997	label[!!label[0]] = llist_pop(&L_arg);
998	xfunc_error_retval = 2;
999	for (i = 0; i < 2; i++) {
1000	file[i] = argv[i];
1001	/* Compat: "diff file name_which_doesnt_exist" exits with 2 */
1002	if (LONE_DASH(file[i])) {
1003	fstat(STDIN_FILENO, &stb[i]);
1004	gotstdin++;
1005	} else
1006	xstat(file[i], &stb[i]);
1007	}
1008	xfunc_error_retval = 1;
1009	if (gotstdin && (S_ISDIR(stb[0].st_mode) || S_ISDIR(stb[1].st_mode)))
1010	bb_error_msg_and_die("can't compare stdin to a directory");
1011
1012	/* Compare metadata to check if the files are the same physical file.
1013	*
1014	* Comment from diffutils source says:
1015	* POSIX says that two files are identical if st_ino and st_dev are
1016	* the same, but many file systems incorrectly assign the same (device,
1017	* inode) pair to two distinct files, including:
1018	* GNU/Linux NFS servers that export all local file systems as a
1019	* single NFS file system, if a local device number (st_dev) exceeds
1020	* 255, or if a local inode number (st_ino) exceeds 16777215.
1021	*/
1022	if (ENABLE_DESKTOP
1023	&& stb[0].st_ino == stb[1].st_ino
1024	&& stb[0].st_dev == stb[1].st_dev
1025	&& stb[0].st_size == stb[1].st_size
1026	&& stb[0].st_mtime == stb[1].st_mtime
1027	&& stb[0].st_ctime == stb[1].st_ctime
1028	&& stb[0].st_mode == stb[1].st_mode
1029	&& stb[0].st_nlink == stb[1].st_nlink
1030	&& stb[0].st_uid == stb[1].st_uid
1031	&& stb[0].st_gid == stb[1].st_gid
1032	) {
1033	/* files are physically the same; no need to compare them */
1034	return STATUS_SAME;
1035	}
1036
1037	if (S_ISDIR(stb[0].st_mode) && S_ISDIR(stb[1].st_mode)) {
1038	#if ENABLE_FEATURE_DIFF_DIR
1039	diffdir(file, s_start);
1040	#else
1041	bb_error_msg_and_die("no support for directory comparison");
1042	#endif
1043	} else {
1044	bool dirfile = S_ISDIR(stb[0].st_mode) || S_ISDIR(stb[1].st_mode);
1045	bool dir = S_ISDIR(stb[1].st_mode);
1046	if (dirfile) {
1047	const char *slash = strrchr(file[!dir], '/');
1048	file[dir] = concat_path_file(file[dir], slash ? slash + 1 : file[!dir]);
1049	xstat(file[dir], &stb[dir]);
1050	}
1051	/* diffreg can get non-regular files here */
1052	print_status(gotstdin > 1 ? STATUS_SAME : diffreg(file), file);
1053
1054	if (dirfile)
1055	free(file[dir]);
1056	}
1057
1058	return exit_status;
1059	}
1060