/*
 * POSIX IEEE Std 1003.1-2017 diff implementation
 * with the following options;
 * -b, -c, -C n, -e, -f, -r, -u, -U n
 * public domain
 */

#include <sys/types.h>
#include <sys/stat.h>

#include <dirent.h>
#include <err.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

#define	EXIT_SAME	0
#define	EXIT_DIFF	1
#define	EXIT_ERR	2

enum fmt_kind {
	FMT_DEFAULT,
	FMT_CONTEXT,
	FMT_UNIFIED,
	FMT_ED,
	FMT_FORWARD
};

struct options {
	enum fmt_kind	fmt;
	int		context;
	int		ignore_space;
	int		recursive;
};

struct file_data {
	char		*bytes;
	char		**lines;
	char		*path;
	size_t		len;
	struct stat	st;
	int		has_stat;
	int		is_text;
	int		line_count;
};

struct hunk {
	int	a0;
	int	a1;
	int	b0;
	int	b1;
};

struct hunk_list {
	struct hunk	*v;
	int		cap;
	int		n;
};

struct str_list {
	char	**v;
	int	cap;
	int	n;
};

struct inode_ref {
	dev_t	dev;
	ino_t	ino;
};

struct inode_stack {
	struct inode_ref	*v;
	int			cap;
	int			n;
};

static const char	*progname = "diff";

static int	build_file_hunks(const struct file_data *, const struct file_data *,
	        const struct options *, struct hunk_list *);
static int	compare_dirs(const char *, const char *, const char *, const char *,
	        const struct options *, struct inode_stack *);
static int	compare_file_paths(const char *, const char *, const char *, const char *,
	        const struct options *, int);
static int	compare_text_files(const struct file_data *, const struct file_data *,
	        const struct options *, int);
static int	ftype_rank(mode_t);
static void	emit_context(const struct file_data *, const struct file_data *,
	        const struct hunk_list *, int);
static void	emit_default(const struct file_data *, const struct file_data *,
	        const struct hunk_list *);
static void	emit_ed(const struct file_data *, const struct file_data *,
	        const struct hunk_list *);
static void	emit_forward(const struct file_data *, const struct file_data *,
	        const struct hunk_list *);
static void	emit_unified(const struct file_data *, const struct file_data *,
	        const struct hunk_list *, int);
static void	file_to_lines(struct file_data *);
static void	fmt_context_time(const struct file_data *, char *, size_t);
static void	fmt_unified_time(const struct file_data *, char *, size_t);
static void	free_file_data(struct file_data *);
static void	free_str_list(struct str_list *);
static const char	*ftype_name(mode_t);
static void	hunk_push(struct hunk_list *, int, int, int, int);
static int	inode_stack_contains(const struct inode_stack *, dev_t, ino_t);
static void	inode_stack_pop(struct inode_stack *);
static void	inode_stack_push(struct inode_stack *, dev_t, ino_t);
static int	is_dir_path(const char *, struct stat *);
static int	is_space_no_nl(int);
static int	is_text_bytes(const char *, size_t);
static char	*join_path(const char *, const char *);
static int	line_equal(const char *, const char *, const struct options *);
static int	line_equal_ws(const char *, const char *);
static void	make_diffopt_string(const struct options *, char *, size_t);
static int	name_cmp(const void *, const void *);
static void	print_context_old_range(int, int);
static void	print_context_new_range(int, int);
static void	print_default_range(int, int);
static void	print_ed_payload(const struct file_data *, int, int);
static void	print_fwd_addr(int, int);
static void	print_line_prefixed(const char *, const char *);
static void	print_unified_range_part(int, int);
static int	parse_nonneg(const char *, int *);
static int	parse_options(int, char **, struct options *, int *);
static int	read_dir_names(const char *, struct str_list *);
static int	read_file_bytes(FILE *, char **, size_t *);
static void	read_operand(const char *, struct file_data *);
static void	usage(void) __attribute__((__noreturn__));
static void	*xmalloc(size_t);
static void	*xrealloc(void *, size_t);
static char	*xstrdup(const char *);

static void
usage(void)
{
	fprintf(stderr,
	    "usage: %s [-befr] [-c | -u | -e | -f] [-C n | -U n] file1 file2\n",
	    progname);
	exit(EXIT_ERR);
}

static void *
xmalloc(size_t n)
{
	void	*p;

	p = malloc(n);
	if (p == NULL)
	    errx(EXIT_ERR, "out of memory");
	return p;
}

static void *
xrealloc(void *p, size_t n)
{
	void	*q;

	q = realloc(p, n);
	if (q == NULL)
	    errx(EXIT_ERR, "out of memory");
	return q;
}

static char *
xstrdup(const char *s)
{
	size_t	n;
	char	*p;

	n = strlen(s);
	p = xmalloc(n + 1);
	memcpy(p, s, n + 1);
	return p;
}

static int
parse_nonneg(const char *s, int *out)
{
	char	*end;
	long	v;

	if (s == NULL || *s == '\0')
	    return 0;
	errno = 0;
	v = strtol(s, &end, 10);
	if (errno != 0 || *end != '\0' || v < 0 || v > 2147483647L)
	    return 0;
	*out = (int)v;
	return 1;
}

static int
is_space_no_nl(int c)
{
	return c == ' ' || c == '\t' || c == '\v' || c == '\f' || c == '\r';
}

static const char *
ftype_name(mode_t m)
{
	if (S_ISREG(m))
	    return "regular file";
	if (S_ISDIR(m))
	    return "directory";
	if (S_ISCHR(m))
	    return "character special file";
	if (S_ISBLK(m))
	    return "block special file";
	if (S_ISFIFO(m))
	    return "fifo";
#ifdef S_ISLNK
	if (S_ISLNK(m))
	    return "symbolic link";
#endif
#ifdef S_ISSOCK
	if (S_ISSOCK(m))
	    return "socket";
#endif
	return "file";
}

static int
ftype_rank(mode_t m)
{
	if (S_ISREG(m))
	    return 0;
	if (S_ISDIR(m))
	    return 1;
	if (S_ISCHR(m))
	    return 2;
	if (S_ISBLK(m))
	    return 3;
	if (S_ISFIFO(m))
	    return 4;
#ifdef S_ISLNK
	if (S_ISLNK(m))
	    return 5;
#endif
#ifdef S_ISSOCK
	if (S_ISSOCK(m))
	    return 6;
#endif
	return 7;
}

static char *
join_path(const char *a, const char *b)
{
	size_t	na;
	size_t	nb;
	size_t	pos;
	int	need_slash;
	char	*p;

	na = strlen(a);
	nb = strlen(b);
	need_slash = (na > 0 && a[na - 1] != '/');
	p = xmalloc(na + (size_t)need_slash + nb + 1);
	memcpy(p, a, na);
	pos = na;
	if (need_slash)
	    p[pos++] = '/';
	memcpy(p + pos, b, nb + 1);
	return p;
}

static int
name_cmp(const void *a, const void *b)
{
	const char	*sa;
	const char	*sb;

	sa = *(const char * const *)a;
	sb = *(const char * const *)b;
	return strcmp(sa, sb);
}

static int
read_file_bytes(FILE *fp, char **out, size_t *out_len)
{
	size_t	cap;
	size_t	len;
	size_t	nr;
	char	*buf;

	cap = 0;
	len = 0;
	buf = NULL;
	for (;;) {
	    if (len + 4096 > cap) {
	        size_t nc;

	        nc = (cap == 0) ? 8192 : cap * 2;
	        while (nc < len + 4096)
	            nc *= 2;
	        buf = xrealloc(buf, nc);
	        cap = nc;
	    }

	    nr = fread(buf + len, 1, 4096, fp);
	    len += nr;
	    if (nr < 4096) {
	        if (ferror(fp)) {
	            free(buf);
	            return 0;
	        }
	        break;
	    }
	}

	if (buf == NULL)
	    buf = xmalloc(1);
	*out = buf;
	*out_len = len;
	return 1;
}

static int
is_text_bytes(const char *buf, size_t len)
{
	size_t	i;

	for (i = 0; i < len; i++) {
	    if (buf[i] == '\0')
	        return 0;
	}
	return 1;
}

static void
file_to_lines(struct file_data *f)
{
	struct str_list	ls;
	size_t		start;
	size_t		i;

	ls.v = NULL;
	ls.n = 0;
	ls.cap = 0;

	start = 0;
	for (i = 0; i < f->len; i++) {
	    if (f->bytes[i] == '\n') {
	        size_t	ln;
	        char	*s;

	        ln = i - start + 1;
	        s = xmalloc(ln + 1);
	        memcpy(s, f->bytes + start, ln);
	        s[ln] = '\0';
	        if (ls.n == ls.cap) {
	            int nc;

	            nc = (ls.cap == 0) ? 32 : ls.cap * 2;
	            ls.v = xrealloc(ls.v, (size_t)nc * sizeof(*ls.v));
	            ls.cap = nc;
	        }
	        ls.v[ls.n++] = s;
	        start = i + 1;
	    }
	}
	if (start < f->len) {
	    size_t	ln2;
	    char	*s2;

	    ln2 = f->len - start;
	    s2 = xmalloc(ln2 + 1);
	    memcpy(s2, f->bytes + start, ln2);
	    s2[ln2] = '\0';
	    if (ls.n == ls.cap) {
	        int nc;

	        nc = (ls.cap == 0) ? 32 : ls.cap * 2;
	        ls.v = xrealloc(ls.v, (size_t)nc * sizeof(*ls.v));
	        ls.cap = nc;
	    }
	    ls.v[ls.n++] = s2;
	}

	f->lines = ls.v;
	f->line_count = ls.n;
}

static void
read_operand(const char *path, struct file_data *out)
{
	FILE	*fp;

	memset(out, 0, sizeof(*out));
	out->path = xstrdup(path);

	if (strcmp(path, "-") == 0) {
	    fp = stdin;
	    out->has_stat = 0;
	} else {
	    if (stat(path, &out->st) != 0)
	        err(EXIT_ERR, "%s", path);
	    out->has_stat = 1;
	    fp = fopen(path, "rb");
	    if (fp == NULL)
	        err(EXIT_ERR, "%s", path);
	}

	if (!read_file_bytes(fp, &out->bytes, &out->len)) {
	    if (fp != stdin)
	        fclose(fp);
	    errx(EXIT_ERR, "%s: read error", path);
	}
	if (fp != stdin)
	    fclose(fp);

	out->is_text = is_text_bytes(out->bytes, out->len);
	if (out->is_text)
	    file_to_lines(out);
}

static void
free_file_data(struct file_data *f)
{
	int	i;

	if (f == NULL)
	    return;
	free(f->path);
	free(f->bytes);
	if (f->lines != NULL) {
	    for (i = 0; i < f->line_count; i++)
	        free(f->lines[i]);
	}
	free(f->lines);
	memset(f, 0, sizeof(*f));
}

static int
line_equal_ws(const char *a, const char *b)
{
	size_t	ea;
	size_t	eb;
	size_t	ia;
	size_t	ib;

	ia = 0;
	ib = 0;
	ea = strlen(a);
	eb = strlen(b);

	if (ea > 0 && a[ea - 1] == '\n')
	    ea--;
	if (eb > 0 && b[eb - 1] == '\n')
	    eb--;
	while (ea > 0 && is_space_no_nl((unsigned char)a[ea - 1]))
	    ea--;
	while (eb > 0 && is_space_no_nl((unsigned char)b[eb - 1]))
	    eb--;

	while (ia < ea && ib < eb) {
	    int wa;
	    int wb;

	    wa = is_space_no_nl((unsigned char)a[ia]);
	    wb = is_space_no_nl((unsigned char)b[ib]);
	    if (wa || wb) {
	        if (!wa || !wb)
	            return 0;
	        while (ia < ea && is_space_no_nl((unsigned char)a[ia]))
	            ia++;
	        while (ib < eb && is_space_no_nl((unsigned char)b[ib]))
	            ib++;
	        continue;
	    }
	    if (a[ia] != b[ib])
	        return 0;
	    ia++;
	    ib++;
	}
	return ia == ea && ib == eb;
}

static int
line_equal(const char *a, const char *b, const struct options *opt)
{
	if (opt->ignore_space)
	    return line_equal_ws(a, b);
	return strcmp(a, b) == 0;
}

static int
build_file_hunks(const struct file_data *a, const struct file_data *b,
    const struct options *opt, struct hunk_list *out)
{
	size_t	cols;
	size_t	rows;
	size_t	sz;
	int	*dp;
	int	i;
	int	j;
	int	m;
	int	n;

	out->v = NULL;
	out->n = 0;
	out->cap = 0;

	n = a->line_count;
	m = b->line_count;
	rows = (size_t)n + 1;
	cols = (size_t)m + 1;
	if (rows != 0 && cols > ((size_t)-1) / rows)
	    return 0;
	sz = rows * cols;
	if (sz > ((size_t)-1) / sizeof(*dp))
	    return 0;

	dp = calloc(sz, sizeof(*dp));
	if (dp == NULL)
	    return 0;

	for (i = n - 1; i >= 0; i--) {
	    for (j = m - 1; j >= 0; j--) {
	        size_t idx;

	        idx = (size_t)i * cols + (size_t)j;
	        if (line_equal(a->lines[i], b->lines[j], opt)) {
	            dp[idx] = dp[(size_t)(i + 1) * cols +
	                (size_t)(j + 1)] + 1;
	        } else {
	            int d;
	            int r;

	            d = dp[(size_t)(i + 1) * cols + (size_t)j];
	            r = dp[(size_t)i * cols + (size_t)(j + 1)];
	            dp[idx] = d >= r ? d : r;
	        }
	    }
	}

	i = 0;
	j = 0;
	while (i < n || j < m) {
	    int ei;
	    int ej;
	    int si;
	    int sj;

	    if (i < n && j < m && line_equal(a->lines[i], b->lines[j], opt)) {
	        i++;
	        j++;
	        continue;
	    }

	    si = i;
	    sj = j;
	    while (i < n || j < m) {
	        if (i < n && j < m &&
	            line_equal(a->lines[i], b->lines[j], opt))
	            break;
	        if (j >= m || (i < n &&
	            dp[(size_t)(i + 1) * cols + (size_t)j] >=
	            dp[(size_t)i * cols + (size_t)(j + 1)]))
	            i++;
	        else
	            j++;
	    }
	    ei = i;
	    ej = j;
	    hunk_push(out, si, ei, sj, ej);
	}

	free(dp);
	return 1;
}

static void
hunk_push(struct hunk_list *hs, int a0, int a1, int b0, int b1)
{
	if (hs->n == hs->cap) {
	    int nc;

	    nc = (hs->cap == 0) ? 32 : hs->cap * 2;
	    hs->v = xrealloc(hs->v, (size_t)nc * sizeof(*hs->v));
	    hs->cap = nc;
	}
	hs->v[hs->n].a0 = a0;
	hs->v[hs->n].a1 = a1;
	hs->v[hs->n].b0 = b0;
	hs->v[hs->n].b1 = b1;
	hs->n++;
}

static void
print_line_prefixed(const char *pfx, const char *line)
{
	size_t	n;

	n = strlen(line);
	fputs(pfx, stdout);
	fputs(line, stdout);
	if (n == 0 || line[n - 1] != '\n')
	    fputc('\n', stdout);
}

static void
print_default_range(int s0, int e0)
{
	int	a;
	int	b;

	a = s0 + 1;
	b = e0;
	if (a == b)
	    printf("%d", a);
	else
	    printf("%d,%d", a, b);
}

static void
emit_default(const struct file_data *a, const struct file_data *b,
    const struct hunk_list *hs)
{
	const struct hunk	*x;
	int			h;
	int			k;

	for (h = 0; h < hs->n; h++) {
	    x = &hs->v[h];
	    if (x->a0 == x->a1) {
	        printf("%da", x->a0);
	        print_default_range(x->b0, x->b1);
	        printf("\n");
	        for (k = x->b0; k < x->b1; k++)
	            print_line_prefixed("> ", b->lines[k]);
	    } else if (x->b0 == x->b1) {
	        print_default_range(x->a0, x->a1);
	        printf("d%d\n", x->b0);
	        for (k = x->a0; k < x->a1; k++)
	            print_line_prefixed("< ", a->lines[k]);
	    } else {
	        print_default_range(x->a0, x->a1);
	        printf("c");
	        print_default_range(x->b0, x->b1);
	        printf("\n");
	        for (k = x->a0; k < x->a1; k++)
	            print_line_prefixed("< ", a->lines[k]);
	        printf("---\n");
	        for (k = x->b0; k < x->b1; k++)
	            print_line_prefixed("> ", b->lines[k]);
	    }
	}
}

static void
print_ed_payload(const struct file_data *b, int s, int e)
{
	int		k;
	const char	*ln;
	size_t		n;

	for (k = s; k < e; k++) {
	    ln = b->lines[k];
	    if (strcmp(ln, ".") == 0 || strcmp(ln, ".\n") == 0)
	        printf("..\n");
	    else {
	        fputs(ln, stdout);
	        n = strlen(ln);
	        if (n == 0 || ln[n - 1] != '\n')
	            fputc('\n', stdout);
	    }
	}
	printf(".\n");
}

static void
emit_ed(const struct file_data *a, const struct file_data *b,
    const struct hunk_list *hs)
{
	const struct hunk	*x;
	int			alen;
	int			blen;
	int			h;

	(void)a;
	for (h = hs->n - 1; h >= 0; h--) {
	    x = &hs->v[h];
	    alen = x->a1 - x->a0;
	    blen = x->b1 - x->b0;
	    if (alen == 0) {
	        printf("%da\n", x->a0);
	        print_ed_payload(b, x->b0, x->b1);
	    } else if (blen == 0) {
	        if (alen == 1)
	            printf("%dd\n", x->a0 + 1);
	        else
	            printf("%d,%dd\n", x->a0 + 1, x->a1);
	    } else {
	        if (alen == 1)
	            printf("%dc\n", x->a0 + 1);
	        else
	            printf("%d,%dc\n", x->a0 + 1, x->a1);
	        print_ed_payload(b, x->b0, x->b1);
	    }
	}
}

static void
print_fwd_addr(int s, int e)
{
	if (e - s <= 1)
	    printf("%d", s + 1);
	else
	    printf("%d %d", s + 1, e);
}

static void
emit_forward(const struct file_data *a, const struct file_data *b,
    const struct hunk_list *hs)
{
	const struct hunk	*x;
	int			alen;
	int			blen;
	int			h;

	(void)a;
	for (h = 0; h < hs->n; h++) {
	    x = &hs->v[h];
	    alen = x->a1 - x->a0;
	    blen = x->b1 - x->b0;
	    if (alen == 0) {
	        printf("a %d\n", x->a0);
	        print_ed_payload(b, x->b0, x->b1);
	    } else if (blen == 0) {
	        printf("d ");
	        print_fwd_addr(x->a0, x->a1);
	        printf("\n");
	    } else {
	        printf("c ");
	        print_fwd_addr(x->a0, x->a1);
	        printf("\n");
	        print_ed_payload(b, x->b0, x->b1);
	    }
	}
}

static void
fmt_context_time(const struct file_data *f, char *buf, size_t buflen)
{
	char		day[16];
	char		hmy[32];
	char		mon[16];
	time_t		t;
	struct tm	*tmv;

	t = f->has_stat ? f->st.st_mtime : time(NULL);
	tmv = localtime(&t);
	if (tmv == NULL) {
	    strncpy(buf, "??? ??? ?? ??:??:?? ????", buflen);
	    buf[buflen - 1] = '\0';
	    return;
	}
	if (strftime(day, sizeof(day), "%a", tmv) == 0 ||
	    strftime(mon, sizeof(mon), "%b", tmv) == 0 ||
	    strftime(hmy, sizeof(hmy), "%H:%M:%S %Y", tmv) == 0) {
	    strncpy(buf, "??? ??? ?? ??:??:?? ????", buflen);
	    buf[buflen - 1] = '\0';
	    return;
	}
	snprintf(buf, buflen, "%s %s %2d %s", day, mon, tmv->tm_mday, hmy);
}

static void
fmt_unified_time(const struct file_data *f, char *buf, size_t buflen)
{
	char		base[64];
	char		sign;
	long		off;
	long		off_abs;
	long		off_hh;
	long		off_mm;
	time_t		g_as_local;
	time_t		t;
	struct tm	gtm;
	struct tm	*gtmp;
	struct tm	*tmv;

	t = f->has_stat ? f->st.st_mtime : time(NULL);
	tmv = localtime(&t);
	if (tmv == NULL) {
	    strncpy(buf, "1970-01-01 00:00:00.000000000 +0000", buflen);
	    buf[buflen - 1] = '\0';
	    return;
	}
	if (strftime(base, sizeof(base), "%Y-%m-%d %H:%M:%S", tmv) == 0)
	    strcpy(base, "1970-01-01 00:00:00");
	gtmp = gmtime(&t);
	if (gtmp == NULL) {
	    snprintf(buf, buflen, "%s.000000000 +0000", base);
	    return;
	}
	gtm = *gtmp;
	g_as_local = mktime(&gtm);
	if (g_as_local == (time_t)-1) {
	    snprintf(buf, buflen, "%s.000000000 +0000", base);
	    return;
	}
	off = (long)difftime(t, g_as_local);
	sign = off < 0 ? '-' : '+';
	off_abs = off < 0 ? -off : off;
	off_hh = off_abs / 3600;
	off_mm = (off_abs % 3600) / 60;
	snprintf(buf, buflen, "%s.000000000 %c%02ld%02ld", base, sign, off_hh,
	    off_mm);
}

static void
print_context_old_range(int s, int e)
{
	int len;

	len = e - s;
	if (len <= 0)
	    printf("*** %d ****\n", s);
	else if (len == 1)
	    printf("*** %d ****\n", s + 1);
	else
	    printf("*** %d,%d ****\n", s + 1, e);
}

static void
print_context_new_range(int s, int e)
{
	int len;

	len = e - s;
	if (len <= 0)
	    printf("--- %d ----\n", s);
	else if (len == 1)
	    printf("--- %d ----\n", s + 1);
	else
	    printf("--- %d,%d ----\n", s + 1, e);
}

static void
emit_context(const struct file_data *a, const struct file_data *b,
    const struct hunk_list *hs, int ctx)
{
	char			*mark_a;
	char			*mark_b;
	char			ta[64];
	char			tb[64];
	const struct hunk	*x;
	int			ge;
	int			gi;
	int			gs;
	int			h;
	int			i;
	int			new_e;
	int			new_s;
	int			old_e;
	int			old_s;
	int			size_a;
	int			size_b;

	if (hs->n == 0)
	    return;

	fmt_context_time(a, ta, sizeof(ta));
	fmt_context_time(b, tb, sizeof(tb));
	printf("*** %s %s\n", a->path, ta);
	printf("--- %s %s\n", b->path, tb);

	size_a = a->line_count > 0 ? a->line_count : 1;
	size_b = b->line_count > 0 ? b->line_count : 1;
	gs = 0;
	while (gs < hs->n) {
	    ge = gs;
	    while (ge + 1 < hs->n) {
	        const struct hunk *cur;
	        const struct hunk *nxt;

	        cur = &hs->v[ge];
	        nxt = &hs->v[ge + 1];
	        if ((nxt->a0 - cur->a1) <= 2 * ctx ||
	            (nxt->b0 - cur->b1) <= 2 * ctx)
	            ge++;
	        else
	            break;
	    }

	    old_s = hs->v[gs].a0 - ctx;
	    if (old_s < 0)
	        old_s = 0;
	    old_e = hs->v[ge].a1 + ctx;
	    if (old_e > a->line_count)
	        old_e = a->line_count;
	    new_s = hs->v[gs].b0 - ctx;
	    if (new_s < 0)
	        new_s = 0;
	    new_e = hs->v[ge].b1 + ctx;
	    if (new_e > b->line_count)
	        new_e = b->line_count;

	    mark_a = xmalloc((size_t)size_a);
	    mark_b = xmalloc((size_t)size_b);
	    memset(mark_a, ' ', (size_t)size_a);
	    memset(mark_b, ' ', (size_t)size_b);

	    for (h = gs; h <= ge; h++) {
	        x = &hs->v[h];
	        if (x->a1 > x->a0 && x->b1 > x->b0) {
	            for (i = x->a0; i < x->a1; i++)
	                mark_a[i] = '!';
	            for (i = x->b0; i < x->b1; i++)
	                mark_b[i] = '!';
	        } else if (x->a1 > x->a0) {
	            for (i = x->a0; i < x->a1; i++)
	                mark_a[i] = '-';
	        } else {
	            for (i = x->b0; i < x->b1; i++)
	                mark_b[i] = '+';
	        }
	    }

	    printf("***************\n");
	    print_context_old_range(old_s, old_e);
	    for (gi = old_s; gi < old_e; gi++) {
	        char pfx[3];

	        pfx[0] = mark_a[gi] == '-' ? '-' :
	            (mark_a[gi] == '!' ? '!' : ' ');
	        pfx[1] = ' ';
	        pfx[2] = '\0';
	        print_line_prefixed(pfx, a->lines[gi]);
	    }
	    print_context_new_range(new_s, new_e);
	    for (gi = new_s; gi < new_e; gi++) {
	        char pfx[3];

	        pfx[0] = mark_b[gi] == '+' ? '+' :
	            (mark_b[gi] == '!' ? '!' : ' ');
	        pfx[1] = ' ';
	        pfx[2] = '\0';
	        print_line_prefixed(pfx, b->lines[gi]);
	    }

	    free(mark_a);
	    free(mark_b);
	    gs = ge + 1;
	}
}

static void
print_unified_range_part(int s, int e)
{
	int	len;
	int	pos;

	len = e - s;
	pos = len == 0 ? s : s + 1;
	if (len == 1)
	    printf("%d", pos);
	else
	    printf("%d,%d", pos, len);
}

static void
emit_unified(const struct file_data *a, const struct file_data *b,
    const struct hunk_list *hs, int ctx)
{
	char			ta[96];
	char			tb[96];
	const struct hunk	*x;
	int			cur_a;
	int			cur_b;
	int			ge;
	int			gs;
	int			h;
	int			i;
	int			new_e;
	int			new_s;
	int			old_e;
	int			old_s;

	if (hs->n == 0)
	    return;

	fmt_unified_time(a, ta, sizeof(ta));
	fmt_unified_time(b, tb, sizeof(tb));
	printf("--- %s\t%s\n", a->path, ta);
	printf("+++ %s\t%s\n", b->path, tb);

	gs = 0;
	while (gs < hs->n) {
	    ge = gs;
	    while (ge + 1 < hs->n) {
	        const struct hunk *cur;
	        const struct hunk *nxt;

	        cur = &hs->v[ge];
	        nxt = &hs->v[ge + 1];
	        if ((nxt->a0 - cur->a1) <= 2 * ctx ||
	            (nxt->b0 - cur->b1) <= 2 * ctx)
	            ge++;
	        else
	            break;
	    }

	    old_s = hs->v[gs].a0 - ctx;
	    if (old_s < 0)
	        old_s = 0;
	    old_e = hs->v[ge].a1 + ctx;
	    if (old_e > a->line_count)
	        old_e = a->line_count;
	    new_s = hs->v[gs].b0 - ctx;
	    if (new_s < 0)
	        new_s = 0;
	    new_e = hs->v[ge].b1 + ctx;
	    if (new_e > b->line_count)
	        new_e = b->line_count;

	    printf("@@ -");
	    print_unified_range_part(old_s, old_e);
	    printf(" +");
	    print_unified_range_part(new_s, new_e);
	    printf(" @@\n");

	    cur_a = old_s;
	    cur_b = new_s;
	    for (h = gs; h <= ge; h++) {
	        x = &hs->v[h];
	        while (cur_a < x->a0 && cur_b < x->b0) {
	            print_line_prefixed(" ", a->lines[cur_a]);
	            cur_a++;
	            cur_b++;
	        }
	        for (i = cur_a; i < x->a1; i++)
	            print_line_prefixed("-", a->lines[i]);
	        for (i = cur_b; i < x->b1; i++)
	            print_line_prefixed("+", b->lines[i]);
	        cur_a = x->a1;
	        cur_b = x->b1;
	    }
	    while (cur_a < old_e && cur_b < new_e) {
	        print_line_prefixed(" ", a->lines[cur_a]);
	        cur_a++;
	        cur_b++;
	    }

	    gs = ge + 1;
	}
}

static void
make_diffopt_string(const struct options *opt, char *buf, size_t buflen)
{
	char	fmtbuf[32];
	char	flags[16];

	fmtbuf[0] = '\0';
	flags[0] = '\0';
	if (opt->fmt == FMT_CONTEXT) {
	    if (opt->context == 3)
	        strcpy(fmtbuf, "-c");
	    else
	        snprintf(fmtbuf, sizeof(fmtbuf), "-C %d", opt->context);
	} else if (opt->fmt == FMT_UNIFIED) {
	    if (opt->context == 3)
	        strcpy(fmtbuf, "-u");
	    else
	        snprintf(fmtbuf, sizeof(fmtbuf), "-U %d", opt->context);
	} else if (opt->fmt == FMT_ED)
	    strcpy(fmtbuf, "-e");
	else if (opt->fmt == FMT_FORWARD)
	    strcpy(fmtbuf, "-f");

	if (opt->ignore_space)
	    strcat(flags, " -b");
	if (opt->recursive)
	    strcat(flags, " -r");

	if (fmtbuf[0] != '\0')
	    snprintf(buf, buflen, "%s%s", fmtbuf, flags);
	else if (flags[0] != '\0')
	    snprintf(buf, buflen, "%s", flags + 1);
	else
	    buf[0] = '\0';
}

static int
compare_text_files(const struct file_data *a, const struct file_data *b,
    const struct options *opt, int emit)
{
	struct hunk_list	hs;

	if (!build_file_hunks(a, b, opt, &hs))
	    errx(EXIT_ERR, "out of memory");
	if (hs.n == 0) {
	    free(hs.v);
	    return EXIT_SAME;
	}

	if (emit) {
	    switch (opt->fmt) {
	    case FMT_DEFAULT:
	        emit_default(a, b, &hs);
	        break;
	    case FMT_CONTEXT:
	        emit_context(a, b, &hs, opt->context);
	        break;
	    case FMT_UNIFIED:
	        emit_unified(a, b, &hs, opt->context);
	        break;
	    case FMT_ED:
	        emit_ed(a, b, &hs);
	        break;
	    case FMT_FORWARD:
	        emit_forward(a, b, &hs);
	        break;
	    }
	}

	free(hs.v);
	return EXIT_DIFF;
}

static int
compare_file_paths(const char *path1, const char *path2, const char *label1,
    const char *label2, const struct options *opt, int emit)
{
	struct file_data	a;
	struct file_data	b;
	int			rc;

	if (strcmp(path1, "-") == 0 && strcmp(path2, "-") == 0)
	    errx(EXIT_ERR, "both operands cannot be '-'");

	read_operand(path1, &a);
	read_operand(path2, &b);
	free(a.path);
	free(b.path);
	a.path = xstrdup(label1);
	b.path = xstrdup(label2);

	if (!a.is_text || !b.is_text) {
	    if (a.len != b.len || memcmp(a.bytes, b.bytes, a.len) != 0) {
	        if (emit)
	            printf("Binary files %s and %s differ\n", label1, label2);
	        rc = EXIT_DIFF;
	    } else
	        rc = EXIT_SAME;
	} else
	    rc = compare_text_files(&a, &b, opt, emit);

	free_file_data(&a);
	free_file_data(&b);
	return rc;
}

static int
inode_stack_contains(const struct inode_stack *st, dev_t dev, ino_t ino)
{
	int	i;

	for (i = 0; i < st->n; i++) {
	    if (st->v[i].dev == dev && st->v[i].ino == ino)
	        return 1;
	}
	return 0;
}

static void
inode_stack_push(struct inode_stack *st, dev_t dev, ino_t ino)
{
	if (st->n == st->cap) {
	    int nc;

	    nc = (st->cap == 0) ? 32 : st->cap * 2;
	    st->v = xrealloc(st->v, (size_t)nc * sizeof(*st->v));
	    st->cap = nc;
	}
	st->v[st->n].dev = dev;
	st->v[st->n].ino = ino;
	st->n++;
}

static void
inode_stack_pop(struct inode_stack *st)
{
	if (st->n > 0)
	    st->n--;
}

static int
read_dir_names(const char *path, struct str_list *out)
{
	DIR		*d;
	struct dirent	*de;

	out->v = NULL;
	out->n = 0;
	out->cap = 0;

	d = opendir(path);
	if (d == NULL) {
	    warn("%s", path);
	    return EXIT_ERR;
	}
	for (;;) {
	    de = readdir(d);
	    if (de == NULL)
	        break;
	    if (strcmp(de->d_name, ".") == 0 || strcmp(de->d_name, "..") == 0)
	        continue;
	    if (out->n == out->cap) {
	        int nc;

	        nc = (out->cap == 0) ? 32 : out->cap * 2;
	        out->v = xrealloc(out->v, (size_t)nc * sizeof(*out->v));
	        out->cap = nc;
	    }
	    out->v[out->n++] = xstrdup(de->d_name);
	}
	if (closedir(d) != 0) {
	    warn("%s", path);
	    return EXIT_ERR;
	}
	qsort(out->v, (size_t)out->n, sizeof(*out->v), name_cmp);
	return EXIT_SAME;
}

static void
free_str_list(struct str_list *ls)
{
	int i;

	for (i = 0; i < ls->n; i++)
	    free(ls->v[i]);
	free(ls->v);
	ls->v = NULL;
	ls->n = 0;
	ls->cap = 0;
}

static int
compare_dirs(const char *dir1, const char *dir2, const char *disp1,
    const char *disp2, const struct options *opt, struct inode_stack *stack)
{
	struct str_list	a;
	struct str_list	b;
	char		optbuf[128];
	int		i;
	int		j;
	int		rc;
	int		saw_diff;

	rc = read_dir_names(dir1, &a);
	if (rc == EXIT_ERR)
	    return EXIT_ERR;
	rc = read_dir_names(dir2, &b);
	if (rc == EXIT_ERR) {
	    free_str_list(&a);
	    return EXIT_ERR;
	}

	saw_diff = 0;
	make_diffopt_string(opt, optbuf, sizeof(optbuf));

	i = 0;
	j = 0;
	while (i < a.n || j < b.n) {
	    int c;

	    if (i < a.n && j < b.n)
	        c = strcmp(a.v[i], b.v[j]);
	    else
	        c = (i < a.n) ? -1 : 1;

	    if (c < 0) {
	        printf("Only in %s: %s\n", disp1, a.v[i]);
	        saw_diff = 1;
	        i++;
	        continue;
	    }
	    if (c > 0) {
	        printf("Only in %s: %s\n", disp2, b.v[j]);
	        saw_diff = 1;
	        j++;
	        continue;
	    }

	    {
	        char		*p1;
	        char		*p2;
	        char		*d1;
	        char		*d2;
	        int		rr;
	        struct stat	s1;
	        struct stat	s2;

	        p1 = join_path(dir1, a.v[i]);
	        p2 = join_path(dir2, b.v[j]);
	        d1 = join_path(disp1, a.v[i]);
	        d2 = join_path(disp2, b.v[j]);
	        if (lstat(p1, &s1) != 0 || lstat(p2, &s2) != 0) {
	            warn("%s or %s", p1, p2);
	            free(p1);
	            free(p2);
	            free(d1);
	            free(d2);
	            free_str_list(&a);
	            free_str_list(&b);
	            return EXIT_ERR;
	        }

	        if (S_ISDIR(s1.st_mode) && S_ISDIR(s2.st_mode)) {
	            if (!opt->recursive)
	                printf("Common subdirectories: %s and %s\n",
	                    d1, d2);
	            else if (inode_stack_contains(stack, s1.st_dev,
	                s1.st_ino) || inode_stack_contains(stack,
	                s2.st_dev, s2.st_ino)) {
	                warnx("infinite directory loop detected at %s and "
	                    "%s", d1, d2);
	            } else {
	                inode_stack_push(stack, s1.st_dev, s1.st_ino);
	                inode_stack_push(stack, s2.st_dev, s2.st_ino);
	                rr = compare_dirs(p1, p2, d1, d2, opt, stack);
	                inode_stack_pop(stack);
	                inode_stack_pop(stack);
	                if (rr == EXIT_ERR) {
	                    free(p1);
	                    free(p2);
	                    free(d1);
	                    free(d2);
	                    free_str_list(&a);
	                    free_str_list(&b);
	                    return EXIT_ERR;
	                }
	                if (rr == EXIT_DIFF)
	                    saw_diff = 1;
	            }
	        } else if (S_ISREG(s1.st_mode) && S_ISREG(s2.st_mode)) {
	            rr = compare_file_paths(p1, p2, d1, d2, opt, 0);
	            if (rr == EXIT_ERR) {
	                free(p1);
	                free(p2);
	                free(d1);
	                free(d2);
	                free_str_list(&a);
	                free_str_list(&b);
	                return EXIT_ERR;
	            }
	            if (rr == EXIT_DIFF) {
	                if (optbuf[0] != '\0')
	                    printf("diff %s %s %s\n", optbuf, d1,
	                        d2);
	                else
	                    printf("diff %s %s\n", d1, d2);
	                rr = compare_file_paths(p1, p2, d1, d2, opt, 1);
	                if (rr == EXIT_ERR) {
	                    free(p1);
	                    free(p2);
	                    free(d1);
	                    free(d2);
	                    free_str_list(&a);
	                    free_str_list(&b);
	                    return EXIT_ERR;
	                }
	                saw_diff = 1;
	            }
	        } else {
	            int t1;
	            int t2;

	            t1 = ftype_rank(s1.st_mode);
	            t2 = ftype_rank(s2.st_mode);
	            if (t1 <= t2)
	                printf("File %s is a %s while file %s is a %s\n",
	                    d1, ftype_name(s1.st_mode), d2,
	                    ftype_name(s2.st_mode));
	            else
	                printf("File %s is a %s while file %s is a %s\n",
	                    d2, ftype_name(s2.st_mode), d1,
	                    ftype_name(s1.st_mode));
	            saw_diff = 1;
	        }

	        free(p1);
	        free(p2);
	        free(d1);
	        free(d2);
	    }

	    i++;
	    j++;
	}

	free_str_list(&a);
	free_str_list(&b);
	return saw_diff ? EXIT_DIFF : EXIT_SAME;
}

static int
is_dir_path(const char *p, struct stat *st)
{
	if (strcmp(p, "-") == 0)
	    return 0;
	if (stat(p, st) != 0)
	    return 0;
	return S_ISDIR(st->st_mode);
}

static int
parse_options(int argc, char **argv, struct options *opt, int *argi)
{
	int	ch;
	int	v;

	opt->fmt = FMT_DEFAULT;
	opt->context = 3;
	opt->ignore_space = 0;
	opt->recursive = 0;

	optind = 1;
	opterr = 0;
	while ((ch = getopt(argc, argv, "bC:cefU:ur")) != -1) {
	    switch (ch) {
	    case 'C':
	        if (!parse_nonneg(optarg, &v) || v <= 0)
	            errx(EXIT_ERR, "-C requires positive decimal integer");
	        opt->fmt = FMT_CONTEXT;
	        opt->context = v;
	        break;
	    case 'U':
	        if (!parse_nonneg(optarg, &v))
	            errx(EXIT_ERR, "-U requires decimal integer");
	        opt->fmt = FMT_UNIFIED;
	        opt->context = v;
	        break;
	    case 'b':
	        opt->ignore_space = 1;
	        break;
	    case 'c':
	        opt->fmt = FMT_CONTEXT;
	        opt->context = 3;
	        break;
	    case 'e':
	        opt->fmt = FMT_ED;
	        break;
	    case 'f':
	        opt->fmt = FMT_FORWARD;
	        break;
	    case 'r':
	        opt->recursive = 1;
	        break;
	    case 'u':
	        opt->fmt = FMT_UNIFIED;
	        opt->context = 3;
	        break;
	    default:
	        usage();
	    }
	}

	*argi = optind;
	if (argc - optind != 2)
	    usage();
	return EXIT_SAME;
}

int
main(int argc, char **argv)
{
	const char		*base;
	char			*in_dir;
	char			*op1;
	char			*op2;
	struct inode_stack	stack;
	struct options		opt;
	struct stat		st1;
	struct stat		st2;
	int			argi;
	int			d1;
	int			d2;
	int			rc;

	if (argc > 0 && argv[0] != NULL) {
	    base = strrchr(argv[0], '/');
	    if (base != NULL)
	        progname = base + 1;
	    else
	        progname = argv[0];
	}

	parse_options(argc, argv, &opt, &argi);
	op1 = argv[argi];
	op2 = argv[argi + 1];

	d1 = is_dir_path(op1, &st1);
	d2 = is_dir_path(op2, &st2);

	if (d1 && d2) {
	    stack.v = NULL;
	    stack.n = 0;
	    stack.cap = 0;
	    inode_stack_push(&stack, st1.st_dev, st1.st_ino);
	    inode_stack_push(&stack, st2.st_dev, st2.st_ino);
	    rc = compare_dirs(op1, op2, op1, op2, &opt, &stack);
	    free(stack.v);
	    return rc;
	}

	if (d1 != d2) {
	    char *dir;
	    char *file;

	    if (d1) {
	        dir = op1;
	        file = op2;
	    } else {
	        dir = op2;
	        file = op1;
	    }
	    base = strrchr(file, '/');
	    if (base == NULL)
	        base = file;
	    else
	        base++;

	    in_dir = join_path(dir, base);
	    if (d1)
	        rc = compare_file_paths(in_dir, file, in_dir, file, &opt, 1);
	    else
	        rc = compare_file_paths(file, in_dir, file, in_dir, &opt, 1);
	    free(in_dir);
	    return rc;
	}

	return compare_file_paths(op1, op2, op1, op2, &opt, 1);
}