* Agency (DARPA) and Air Force Research Laboratory, Air Force
* Materiel Command, USAF, under agreement number F39502-99-1-0512.
*
- * Licensed under GPLv2 or later, see file LICENSE in this tarball for details.
+ * Licensed under GPLv2 or later, see file LICENSE in this source tree.
*/
/*
* 6n words for files of length n.
*/
+//config:config DIFF
+//config: bool "diff"
+//config: default y
+//config: help
+//config: diff compares two files or directories and outputs the
+//config: differences between them in a form that can be given to
+//config: the patch command.
+//config:
+//config:config FEATURE_DIFF_LONG_OPTIONS
+//config: bool "Enable long options"
+//config: default y
+//config: depends on DIFF && LONG_OPTS
+//config: help
+//config: Enable use of long options.
+//config:
+//config:config FEATURE_DIFF_DIR
+//config: bool "Enable directory support"
+//config: default y
+//config: depends on DIFF
+//config: help
+//config: This option enables support for directory and subdirectory
+//config: comparison.
+
+//kbuild:lib-$(CONFIG_DIFF) += diff.o
+
+//applet:IF_DIFF(APPLET(diff, BB_DIR_USR_BIN, BB_SUID_DROP))
+
+//usage:#define diff_trivial_usage
+//usage: "[-abBdiNqrTstw] [-L LABEL] [-S FILE] [-U LINES] FILE1 FILE2"
+//usage:#define diff_full_usage "\n\n"
+//usage: "Compare files line by line and output the differences between them.\n"
+//usage: "This implementation supports unified diffs only.\n"
+//usage: "\n -a Treat all files as text"
+//usage: "\n -b Ignore changes in the amount of whitespace"
+//usage: "\n -B Ignore changes whose lines are all blank"
+//usage: "\n -d Try hard to find a smaller set of changes"
+//usage: "\n -i Ignore case differences"
+//usage: "\n -L Use LABEL instead of the filename in the unified header"
+//usage: "\n -N Treat absent files as empty"
+//usage: "\n -q Output only whether files differ"
+//usage: "\n -r Recurse"
+//usage: "\n -S Start with FILE when comparing directories"
+//usage: "\n -T Make tabs line up by prefixing a tab when necessary"
+//usage: "\n -s Report when two files are the same"
+//usage: "\n -t Expand tabs to spaces in output"
+//usage: "\n -U Output LINES lines of context"
+//usage: "\n -w Ignore all whitespace"
+
#include "libbb.h"
#if 0
-//#define dbg_error_msg(...) bb_error_msg(__VA_ARGS__)
+# define dbg_error_msg(...) bb_error_msg(__VA_ARGS__)
#else
-#define dbg_error_msg(...) ((void)0)
+# define dbg_error_msg(...) ((void)0)
#endif
enum { /* print_status() and diffreg() return values */
struct globals {
smallint exit_status;
int opt_U_context;
+ const char *other_dir;
char *label[2];
struct stat stb[2];
};
static int search(const int *c, int k, int y, const struct cand *list)
{
- if (list[c[k]].y < y) /* quick look for typical case */
+ int i, j;
+
+ if (list[c[k]].y < y) /* quick look for typical case */
return k + 1;
- for (int i = 0, j = k + 1;;) {
+ for (i = 0, j = k + 1;;) {
const int l = (i + j) >> 1;
if (l > i) {
const int t = list[c[l]].y;
int clistlen = 100;
int k = 0;
struct cand *clist = xzalloc(clistlen * sizeof(clist[0]));
+ struct cand cand;
+ struct cand *q;
int *klist = xzalloc((n + 2) * sizeof(klist[0]));
/*clist[0] = (struct cand){0}; - xzalloc did it */
/*klist[0] = 0; */
- for (struct cand cand = {1}; cand.x <= n; cand.x++) {
+ for (cand.x = 1; cand.x <= n; cand.x++) {
int j = a[cand.x], oldl = 0;
unsigned numtries = 0;
if (j == 0)
} while ((cand.y = b[++j]) > 0 && numtries < bound);
}
/* Unravel */
- for (struct cand *q = clist + klist[k]; q->y; q = clist + q->pred)
+ for (q = clist + klist[k]; q->y; q = clist + q->pred)
J[q->x + pref] = q->y + pref;
free(klist);
free(clist);
static void unsort(const struct line *f, int l, int *b)
{
+ int i;
int *a = xmalloc((l + 1) * sizeof(a[0]));
- for (int i = 1; i <= l; i++)
+ for (i = 1; i <= l; i++)
a[f[i].serial] = f[i].value;
- for (int i = 1; i <= l; i++)
+ for (i = 1; i <= l; i++)
b[i] = a[i];
free(a);
}
#undef l1
}
-static void uni_range(int a, int b)
-{
- if (a < b)
- printf("%d,%d", a, b - a + 1);
- else if (a == b)
- printf("%d", b);
- else
- printf("%d,0", b);
-}
-
static void fetch(FILE_and_pos_t *ft, const off_t *ix, int a, int b, int ch)
{
- for (int i = a; i <= b; i++) {
+ int i, j, col;
+ for (i = a; i <= b; i++) {
seek_ft(ft, ix[i - 1]);
putchar(ch);
if (option_mask32 & FLAG(T))
putchar('\t');
- for (int j = 0, col = 0; j < ix[i] - ix[i - 1]; j++) {
+ for (j = 0, col = 0; j < ix[i] - ix[i - 1]; j++) {
int c = fgetc(ft->ft_fp);
if (c == EOF) {
printf("\n\\ No newline at end of file\n");
{
int *J, slen[2], *class, *member;
struct line *nfile[2], *sfile[2];
- int pref = 0, suff = 0;
+ int pref = 0, suff = 0, i, j, delta;
/* Lines of both files are hashed, and in the process
* their offsets are stored in the array ix[fileno]
* where fileno == 0 points to the old file, and
* fileno == 1 points to the new one.
*/
- for (int i = 0; i < 2; i++) {
+ for (i = 0; i < 2; i++) {
unsigned hash;
token_t tok;
size_t sz = 100;
nfile[i] = xmalloc((sz + 3) * sizeof(nfile[i][0]));
- seek_ft(&ft[i], 0);
+ /* ft gets here without the correct position, cant use seek_ft */
+ ft[i].ft_pos = 0;
+ fseeko(ft[i].ft_fp, 0, SEEK_SET);
nlen[i] = 0;
/* We could zalloc nfile, but then zalloc starts showing in gprof at ~1% */
nlen[i]--;
/* Now we copy the line offsets into ix */
ix[i] = xmalloc((nlen[i] + 2) * sizeof(ix[i][0]));
- for (int j = 0; j < nlen[i] + 1; j++)
+ for (j = 0; j < nlen[i] + 1; j++)
ix[i][j] = nfile[i][j].offset;
}
- /* lenght of prefix and suffix is calculated */
+ /* length of prefix and suffix is calculated */
for (; pref < nlen[0] && pref < nlen[1] &&
nfile[0][pref + 1].value == nfile[1][pref + 1].value;
pref++);
for (; suff < nlen[0] - pref && suff < nlen[1] - pref &&
nfile[0][nlen[0] - suff].value == nfile[1][nlen[1] - suff].value;
suff++);
- /* Arrays are pruned by the suffix and prefix lenght,
+ /* Arrays are pruned by the suffix and prefix length,
* the result being sorted and stored in sfile[fileno],
* and their sizes are stored in slen[fileno]
*/
- for (int j = 0; j < 2; j++) {
+ for (j = 0; j < 2; j++) {
sfile[j] = nfile[j] + pref;
slen[j] = nlen[j] - pref - suff;
- for (int i = 0; i <= slen[j]; i++)
+ for (i = 0; i <= slen[j]; i++)
sfile[j][i].serial = i;
qsort(sfile[j] + 1, slen[j], sizeof(*sfile[j]), line_compar);
}
free(nfile[1]);
class = xmalloc((slen[0] + 1) * sizeof(class[0]));
- for (int i = 1; i <= slen[0]; i++) /* Unsorting */
+ for (i = 1; i <= slen[0]; i++) /* Unsorting */
class[sfile[0][i].serial] = sfile[0][i].value;
free(nfile[0]);
#else
* are initialized with 0 (no matches), so that function stone can
* then assign them their right values
*/
- for (int i = 0, delta = nlen[1] - nlen[0]; i <= nlen[0]; i++)
+ for (i = 0, delta = nlen[1] - nlen[0]; i <= nlen[0]; i++)
J[i] = i <= pref ? i :
i > (nlen[0] - suff) ? (i + delta) : 0;
/* Here the magic is performed */
* which, due to limitations intrinsic to any hashing algorithm,
* are different but ended up confounded as the same
*/
- for (int i = 1; i <= nlen[0]; i++) {
+ for (i = 1; i <= nlen[0]; i++) {
if (!J[i])
continue;
seek_ft(&ft[0], ix[0][i - 1]);
seek_ft(&ft[1], ix[1][J[i] - 1]);
- for (int j = J[i]; i <= nlen[0] && J[i] == j; i++, j++) {
+ for (j = J[i]; i <= nlen[0] && J[i] == j; i++, j++) {
token_t tok0 = 0, tok1 = 0;
do {
tok0 = read_token(&ft[0], tok0);
return J;
}
-/*
- * The following struct is used to record change information
- * doing a "context" or "unified" diff.
- */
-struct context_vec {
- int a; /* start line in old file */
- int b; /* end line in old file */
- int c; /* start line in new file */
- int d; /* end line in new file */
-};
-
-static bool diff(FILE_and_pos_t ft[2], char *file[2])
+static bool diff(FILE* fp[2], char *file[2])
{
int nlen[2];
off_t *ix[2];
- int *J = create_J(ft, nlen, ix);
-
+ FILE_and_pos_t ft[2];
+ typedef struct { int a, b; } vec_t[2];
+ vec_t *vec = NULL;
+ int i = 1, j, k, idx = -1;
bool anychange = false;
- struct context_vec *vec = NULL;
- int idx = -1, i = 1;
+ int *J;
+
+ ft[0].ft_fp = fp[0];
+ ft[1].ft_fp = fp[1];
+ /* note that ft[i].ft_pos is unintitalized, create_J()
+ * must not assume otherwise */
+ J = create_J(ft, nlen, ix);
do {
bool nonempty = false;
while (1) {
- struct context_vec v;
+ vec_t v;
- for (v.a = i; v.a <= nlen[0] && J[v.a] == J[v.a - 1] + 1; v.a++)
+ for (v[0].a = i; v[0].a <= nlen[0] && J[v[0].a] == J[v[0].a - 1] + 1; v[0].a++)
continue;
- v.c = J[v.a - 1] + 1;
+ v[1].a = J[v[0].a - 1] + 1;
- for (v.b = v.a - 1; v.b < nlen[0] && !J[v.b + 1]; v.b++)
+ for (v[0].b = v[0].a - 1; v[0].b < nlen[0] && !J[v[0].b + 1]; v[0].b++)
continue;
- v.d = J[v.b + 1] - 1;
+ v[1].b = J[v[0].b + 1] - 1;
/*
* Indicate that there is a difference between lines a and b of the 'from' file
* to get to lines c to d of the 'to' file. If a is greater than b then there
* lines appended (beginning at b). If c is greater than d then there are
* lines missing from the 'to' file.
*/
- if (v.a <= v.b || v.c <= v.d) {
+ if (v[0].a <= v[0].b || v[1].a <= v[1].b) {
/*
* If this change is more than 'context' lines from the
* previous change, dump the record and reset it.
*/
+ int ct = (2 * opt_U_context) + 1;
if (idx >= 0
- && v.a > vec[idx].b + (2 * opt_U_context) + 1
- && v.c > vec[idx].d + (2 * opt_U_context) + 1
+ && v[0].a > vec[idx][0].b + ct
+ && v[1].a > vec[idx][1].b + ct
) {
break;
}
- nonempty |= (v.a >= v.b) && (v.c >= v.d);
+
+ for (j = 0; j < 2; j++)
+ for (k = v[j].a; k < v[j].b; k++)
+ nonempty |= (ix[j][k+1] - ix[j][k] != 1);
+
vec = xrealloc_vector(vec, 6, ++idx);
- vec[idx] = v;
+ memcpy(vec[idx], v, sizeof(v));
}
- i = v.b + 1;
+ i = v[0].b + 1;
if (i > nlen[0])
break;
- J[v.b] = v.d;
+ J[v[0].b] = v[1].b;
}
- if (idx < 0)
- continue;
- if (!(option_mask32 & FLAG(q)) && !((option_mask32 & FLAG(B)) && !nonempty)) {
- struct context_vec *cvp = vec;
- int lowa = MAX(1, cvp->a - opt_U_context);
- int upb = MIN(nlen[0], vec[idx].b + opt_U_context);
- int lowc = MAX(1, cvp->c - opt_U_context);
- int upd = MIN(nlen[1], vec[idx].d + opt_U_context);
+ if (idx < 0 || ((option_mask32 & FLAG(B)) && !nonempty))
+ goto cont;
+ if (!(option_mask32 & FLAG(q))) {
+ int lowa;
+ vec_t span, *cvp = vec;
if (!anychange) {
/* Print the context/unidiff header first time through */
- printf("--- %s\n", label[0] ?: file[0]);
- printf("+++ %s\n", label[1] ?: file[1]);
+ printf("--- %s\n", label[0] ? label[0] : file[0]);
+ printf("+++ %s\n", label[1] ? label[1] : file[1]);
}
- printf("@@ -");
- uni_range(lowa, upb);
- printf(" +");
- uni_range(lowc, upd);
- printf(" @@\n");
+ printf("@@");
+ for (j = 0; j < 2; j++) {
+ int a = span[j].a = MAX(1, (*cvp)[j].a - opt_U_context);
+ int b = span[j].b = MIN(nlen[j], vec[idx][j].b + opt_U_context);
+ printf(" %c%d", j ? '+' : '-', MIN(a, b));
+ if (a == b)
+ continue;
+ printf(",%d", (a < b) ? b - a + 1 : 0);
+ }
+ printf(" @@\n");
/*
* Output changes in "unified" diff format--the old and new lines
* are printed together.
*/
- while (1) {
+ for (lowa = span[0].a; ; lowa = (*cvp++)[0].b + 1) {
bool end = cvp > &vec[idx];
- fetch(&ft[0], ix[0], lowa, end ? upb : cvp->a - 1, ' ');
+ fetch(&ft[0], ix[0], lowa, end ? span[0].b : (*cvp)[0].a - 1, ' ');
if (end)
break;
- fetch(&ft[0], ix[0], cvp->a, cvp->b, '-');
- fetch(&ft[1], ix[1], cvp->c, cvp->d, '+');
- lowa = cvp++->b + 1;
+ for (j = 0; j < 2; j++)
+ fetch(&ft[j], ix[j], (*cvp)[j].a, (*cvp)[j].b, j ? '+' : '-');
}
}
- idx = -1;
anychange = true;
+ cont:
+ idx = -1;
} while (i <= nlen[0]);
free(vec);
static int diffreg(char *file[2])
{
- FILE_and_pos_t ft[2];
+ FILE *fp[2];
bool binary = false, differ = false;
- int status = STATUS_SAME;
+ int status = STATUS_SAME, i;
- for (int i = 0; i < 2; i++) {
+ fp[0] = stdin;
+ fp[1] = stdin;
+ for (i = 0; i < 2; i++) {
int fd = open_or_warn_stdin(file[i]);
if (fd == -1)
- xfunc_die();
+ goto out;
/* Our diff implementation is using seek.
* When we meet non-seekable file, we must make a temp copy.
*/
- ft[i].ft_pos = 0;
if (lseek(fd, 0, SEEK_SET) == -1 && errno == ESPIPE) {
char name[] = "/tmp/difXXXXXX";
- int fd_tmp = mkstemp(name);
- if (fd_tmp < 0)
- bb_perror_msg_and_die("mkstemp");
+ int fd_tmp = xmkstemp(name);
+
unlink(name);
- ft[i].ft_pos = bb_copyfd_eof(fd, fd_tmp);
- /* error message is printed by bb_copyfd_eof */
- if (ft[i].ft_pos < 0)
+ if (bb_copyfd_eof(fd, fd_tmp) < 0)
xfunc_die();
- fstat(fd, &stb[i]);
if (fd) /* Prevents closing of stdin */
close(fd);
fd = fd_tmp;
}
- ft[i].ft_fp = fdopen(fd, "r");
+ fp[i] = fdopen(fd, "r");
}
while (1) {
const size_t sz = COMMON_BUFSIZE / 2;
char *const buf0 = bb_common_bufsiz1;
char *const buf1 = buf0 + sz;
- int i, j;
- i = fread(buf0, 1, sz, ft[0].ft_fp);
- ft[0].ft_pos += i;
- j = fread(buf1, 1, sz, ft[1].ft_fp);
- ft[1].ft_pos += j;
+ int j, k;
+ i = fread(buf0, 1, sz, fp[0]);
+ j = fread(buf1, 1, sz, fp[1]);
if (i != j) {
differ = true;
i = MIN(i, j);
}
if (i == 0)
break;
- for (int k = 0; k < i; k++) {
+ for (k = 0; k < i; k++) {
if (!buf0[k] || !buf1[k])
binary = true;
if (buf0[k] != buf1[k])
if (differ) {
if (binary && !(option_mask32 & FLAG(a)))
status = STATUS_BINARY;
- else if (diff(ft, file))
+ else if (diff(fp, file))
status = STATUS_DIFFER;
}
if (status != STATUS_SAME)
exit_status |= 1;
-
- fclose_if_not_stdin(ft[0].ft_fp);
- fclose_if_not_stdin(ft[1].ft_fp);
+out:
+ fclose_if_not_stdin(fp[0]);
+ fclose_if_not_stdin(fp[1]);
return status;
}
void *userdata, int depth UNUSED_PARAM)
{
struct dlist *const l = userdata;
+ const char *file = filename + l->len;
+ while (*file == '/')
+ file++;
l->dl = xrealloc_vector(l->dl, 6, l->e);
- /* + 1 skips "/" after dirname */
- l->dl[l->e] = xstrdup(filename + l->len + 1);
+ l->dl[l->e] = xstrdup(file);
l->e++;
return TRUE;
}
add_to_dirlist(filename, sb, userdata, depth);
return SKIP;
}
+ if (!(option_mask32 & FLAG(N))) {
+ /* -r without -N: no need to recurse into dirs
+ * which do not exist on the "other side".
+ * Testcase: diff -r /tmp /
+ * (it would recurse deep into /proc without this code) */
+ struct dlist *const l = userdata;
+ filename += l->len;
+ if (filename[0]) {
+ struct stat osb;
+ char *othername = concat_path_file(G.other_dir, filename);
+ int r = stat(othername, &osb);
+ free(othername);
+ if (r != 0 || !S_ISDIR(osb.st_mode)) {
+ /* other dir doesn't have similarly named
+ * directory, don't recurse; return 1 upon
+ * exit, just like diffutils' diff */
+ exit_status |= 1;
+ return SKIP;
+ }
+ }
+ }
return TRUE;
}
static void diffdir(char *p[2], const char *s_start)
{
struct dlist list[2];
+ int i;
memset(&list, 0, sizeof(list));
- for (int i = 0; i < 2; i++) {
+ for (i = 0; i < 2; i++) {
/*list[i].s = list[i].e = 0; - memset did it */
/*list[i].dl = NULL; */
+ G.other_dir = p[1 - i];
/* We need to trim root directory prefix.
* Using list.len to specify its length,
* add_to_dirlist will remove it. */
list[i].len = strlen(p[i]);
recursive_action(p[i], ACTION_RECURSE | ACTION_FOLLOWLINKS,
- add_to_dirlist, skip_dir, &list[i], 0);
+ add_to_dirlist, skip_dir, &list[i], 0);
/* Sort dl alphabetically.
* GNU diff does this ignoring any number of trailing dots.
* We don't, so for us dotted files almost always are
break;
pos = !dp[0] ? 1 : (!dp[1] ? -1 : strcmp(dp[0], dp[1]));
k = pos > 0;
- if (pos && !(option_mask32 & FLAG(N)))
+ if (pos && !(option_mask32 & FLAG(N))) {
printf("Only in %s: %s\n", p[k], dp[k]);
- else {
+ exit_status |= 1;
+ } else {
char *fullpath[2], *path[2]; /* if -N */
- for (int i = 0; i < 2; i++) {
+ for (i = 0; i < 2; i++) {
if (pos == 0 || i == k) {
path[i] = fullpath[i] = concat_path_file(p[i], dp[i]);
stat(fullpath[i], &stb[i]);
int diff_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
int diff_main(int argc UNUSED_PARAM, char **argv)
{
- int gotstdin = 0;
+ int gotstdin = 0, i;
char *file[2], *s_start = NULL;
llist_t *L_arg = NULL;
getopt32(argv, "abdiL:NqrsS:tTU:wupBE",
&L_arg, &s_start, &opt_U_context);
argv += optind;
- while (L_arg) {
- if (label[0] && label[1])
- bb_show_usage();
- if (label[0]) /* then label[1] is NULL */
- label[1] = label[0];
- label[0] = llist_pop(&L_arg);
- }
+ while (L_arg)
+ label[!!label[0]] = llist_pop(&L_arg);
xfunc_error_retval = 2;
- for (int i = 0; i < 2; i++) {
+ for (i = 0; i < 2; i++) {
file[i] = argv[i];
/* Compat: "diff file name_which_doesnt_exist" exits with 2 */
if (LONE_DASH(file[i])) {
if (gotstdin && (S_ISDIR(stb[0].st_mode) || S_ISDIR(stb[1].st_mode)))
bb_error_msg_and_die("can't compare stdin to a directory");
+ /* Compare metadata to check if the files are the same physical file.
+ *
+ * Comment from diffutils source says:
+ * POSIX says that two files are identical if st_ino and st_dev are
+ * the same, but many file systems incorrectly assign the same (device,
+ * inode) pair to two distinct files, including:
+ * GNU/Linux NFS servers that export all local file systems as a
+ * single NFS file system, if a local device number (st_dev) exceeds
+ * 255, or if a local inode number (st_ino) exceeds 16777215.
+ */
+ if (ENABLE_DESKTOP
+ && stb[0].st_ino == stb[1].st_ino
+ && stb[0].st_dev == stb[1].st_dev
+ && stb[0].st_size == stb[1].st_size
+ && stb[0].st_mtime == stb[1].st_mtime
+ && stb[0].st_ctime == stb[1].st_ctime
+ && stb[0].st_mode == stb[1].st_mode
+ && stb[0].st_nlink == stb[1].st_nlink
+ && stb[0].st_uid == stb[1].st_uid
+ && stb[0].st_gid == stb[1].st_gid
+ ) {
+ /* files are physically the same; no need to compare them */
+ return STATUS_SAME;
+ }
+
if (S_ISDIR(stb[0].st_mode) && S_ISDIR(stb[1].st_mode)) {
#if ENABLE_FEATURE_DIFF_DIR
diffdir(file, s_start);
projects / platform / upstream / busybox.git / blobdiff