/*
 * difftest.c -- differential harness: kernel fnmatch (sys/libkern/fnmatch.c,
 * compiled verbatim into this binary via fnmatch_k.c + shim.h) vs the host
 * libc fnmatch(3).
 *
 * build: cc -O2 -o difftest difftest.c fnmatch_k.c
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <locale.h>
#include <fnmatch.h>

int _kfnmatch(const char *, const char *, int, int);

static int kfn(const char *p, const char *s, int f)
{
	return _kfnmatch(p, s, f, 0);
}

static long nfail = 0, ncase = 0;
static long cls_backslash = 0, cls_other = 0;

static void chk(const char *p, const char *s, int f, const char *tag)
{
	int rk = kfn(p, s, f);
	int rl = fnmatch(p, s, f);
	ncase++;
	if ((rk == 0) != (rl == 0)) {
		nfail++;
		if (p[strlen(p) - 1] == '\\' && !(f & FNM_NOESCAPE))
			cls_backslash++;
		else {
			cls_other++;
			if (cls_other <= 10)
				printf("DIVERGE-OTHER[%s] flags=%#x pattern=\"%s\" "
				       "string=\"%s\": kernel=%d libc=%d\n",
				       tag, f, p, s, rk, rl);
		}
	}
}

static double now_sec(void)
{
	struct timespec ts;
	clock_gettime(CLOCK_MONOTONIC, &ts);
	return ts.tv_sec + ts.tv_nsec / 1e9;
}

static const char *alpha = "*?[]-\\!^ab/.";	/* 12 symbols */
static const int flags_all[] = { 0, FNM_PATHNAME, FNM_PERIOD,
    FNM_PATHNAME | FNM_PERIOD, FNM_NOESCAPE, FNM_CASEFOLD,
    FNM_PATHNAME | FNM_PERIOD | FNM_NOESCAPE, FNM_LEADING_DIR,
    FNM_PATHNAME | FNM_LEADING_DIR | FNM_PERIOD };
#define NFLAGS 9

/* enumerate all strings over alpha[] of each length 1..maxlen into buf,
   calling cb for each; returns count */
static long enum_syms(int maxlen, void (*cb)(const char *, int))
{
	char buf[8];
	long total = 0;
	int na = 12, len, i;
	long count, idx;

	for (len = 1; len <= maxlen; len++) {
		count = 1;
		for (i = 0; i < len; i++)
			count *= na;		/* 12^len of this length */
		for (idx = 0; idx < count; idx++) {
			long x = idx;
			for (i = len - 1; i >= 0; i--) {
				buf[i] = alpha[x % na];
				x /= na;
			}
			buf[len] = 0;
			cb(buf, len);
			total++;
		}
	}
	return total;
}

static char cur_pat[8];

static void cb_str(const char *s, int len)
{
	int f;
	for (f = 0; f < NFLAGS; f++)
		chk(cur_pat, s, flags_all[f], "corpus");
}

static void cb_pat(const char *p, int len)
{
	snprintf(cur_pat, sizeof(cur_pat), "%s", p);
	enum_syms(3, cb_str);
}

int main(void)
{
	int i, j;
	char pat[128], str[128];

	setlocale(LC_ALL, "C");

	/* ---- 1. exhaustive small corpus: patterns len 1..3 x strings len 1..3 ---- */
	{
		long total = enum_syms(3, cb_pat);	/* 1884 patterns */
		(void)total;
		/* random longer cases, mixed lengths up to 16 */
		srand(12345);
		for (i = 0; i < 300000; i++) {
			int plen = 1 + rand() % 16;
			int slen = 1 + rand() % 16;
			for (j = 0; j < plen; j++)
				pat[j] = alpha[rand() % 12];
			pat[plen] = 0;
			for (j = 0; j < slen; j++)
				str[j] = alpha[rand() % 12];
			str[slen] = 0;
			chk(pat, str, flags_all[rand() % NFLAGS], "random");
		}
		printf("[corpus] %ld cases, %ld divergences\n", ncase, nfail);
	}

	/* ---- 1b. dedicated bracket-expression sweep: "[" + 1..3 syms + "]"
	 *          (drives every pointer move in rangematch) ---- */
	{
		char bp[8], bs[2];
		const char *bal = "]-\\!^ab/.\x80\xff";
		int nb = (int)strlen(bal);
		int cnt = 0;
		for (int a = 0; a < nb; a++)
		for (int b = 0; b < nb; b++)
		for (int c = 0; c < nb; c++) {
			snprintf(bp, sizeof(bp), "[%c%c%c]", bal[a], bal[b], bal[c]);
			for (int d = 0; d < nb; d++) {
				bs[0] = bal[d]; bs[1] = 0;
				chk(bp, bs, 0, "bracket");
				chk(bp, bs, FNM_NOESCAPE, "bracket");
				chk(bp, bs, FNM_PATHNAME, "bracket");
				chk(bp, bs, FNM_CASEFOLD, "bracket");
				cnt += 4;
			}
		}
		printf("[bracket] %d cases (running divergences: %ld)\n", cnt, nfail);
	}

	/* ---- 2. targeted: MAXNEST depth cap (string scaled to keep C(n,k) small) ---- */
	{
		int diverge_at = -1;
		for (int nstars = 1; nstars <= 24; nstars++) {
			int o = 0;
			for (j = 0; j < nstars; j++) {
				pat[o++] = '*'; pat[o++] = 'a';
			}
			pat[o] = 0;
			for (j = 0; j < nstars + 2; j++) str[j] = 'a';
			str[nstars + 2] = 0;
			int rk = kfn(pat, str, 0);
			int rl = fnmatch(pat, str, 0);
			printf("[maxnest] stars=%2d kernel=%d libc=%d%s\n",
			       nstars, rk, rl,
			       ((rk == 0) != (rl == 0)) ? "  <== DIVERGE" : "");
			if (diverge_at < 0 && (rk == 0) != (rl == 0))
				diverge_at = nstars;
		}
		printf("[maxnest] first divergence at %d stars\n", diverge_at);
	}

	/* ---- 3. targeted: signed-char bracket range endpoints ---- */
	{
		struct { const char *p; const char *s; const char *why; } t[] = {
			{ "[a-\xff]",	"\x80", "0x80 within [0x61,0xff]" },
			{ "[a-\xff]",	"\xfe", "0xfe within [0x61,0xff]" },
			{ "[\x80-\xff]", "\x90", "high-high range" },
			{ "[\x01-\x7f]", "\x80", "0x80 outside [1,0x7f]" },
		};
		for (i = 0; i < 4; i++) {
			int rk = kfn(t[i].p, t[i].s, 0);
			int rl = fnmatch(t[i].p, t[i].s, 0);
			printf("[signed] pattern-raw=\"%s\" string-raw=\"%s\" "
			       "kernel=%d libc=%d  (%s)\n",
			       t[i].p, t[i].s, rk, rl, t[i].why);
		}
	}

	/* ---- 4. backtracking cost characterization (worst case = FAILING match) ----
	 * worst-case work for "*a"*k+"b" vs n a's ~ C(n,k) chains:
	 *  - in-kernel bound: if_xname <= 16 bytes  => C(16,8)=12870 chains max
	 *  - long-string danger (no kernel consumer today): shown with n=20..28
	 */
	{
		for (int nstars = 4; nstars <= 10; nstars += 2) {
			int o = 0;
			for (j = 0; j < nstars; j++) { pat[o++] = '*'; pat[o++] = 'a'; }
			pat[o++] = 'b';			/* never occurs: worst case */
			pat[o] = 0;
			for (j = 0; j < 16; j++) str[j] = 'a';
			str[16] = 0;
			double t0 = now_sec();
			int r = kfn(pat, str, 0);
			double dt = now_sec() - t0;
			printf("[time-ifname-worst] stars=%2d n=16 kernel: %.6f s (ret %d)\n",
			       nstars, dt, r);
		}
		for (int n = 20; n <= 28; n += 4) {
			int o = 0;
			for (j = 0; j < 10; j++) { pat[o++] = '*'; pat[o++] = 'a'; }
			pat[o++] = 'b';
			pat[o] = 0;
			for (j = 0; j < n; j++) str[j] = 'a';
			str[n] = 0;
			double t0 = now_sec();
			int r = kfn(pat, str, 0);
			double dt = now_sec() - t0;
			t0 = now_sec();
			int rl = fnmatch(pat, str, 0);
			double dtl = now_sec() - t0;
			printf("[time-long-worst] stars=10 n=%2d kernel: %.6f s (ret %d)  "
			       "libc: %.6f s (ret %d)\n", n, dt, r, dtl, rl);
		}
	}

	printf("TOTAL divergences: %ld / %ld cases "
	       "(trailing-backslash class: %ld, other: %ld)\n",
	       nfail, ncase, cls_backslash, cls_other);

	printf("TOTAL divergences: %ld / %ld cases\n", nfail, ncase);
	return 0;
}