/*
 * DF-0411 ALGORITHM TEST: faithful userland copy of the three kernel
 * functions from sys/netgraph7/netgraph/ng_parse.c:
 *   - ng_parse_skip_value  (lines 1651-1683)
 *   - ng_parse_get_token   (lines 1690-1735)
 *   - ng_get_string_token  (lines 1737-1818)
 *
 * These are PURE functions over a C string; the only edit is kmalloc->malloc,
 * kfree->free, M_NETGRAPH_PARSE dropped, KKASSERT dropped. The control flow
 * (which is what the finding is about) is byte-identical.
 *
 * We instrument ng_parse_skip_value with an iteration cap and per-iteration
 * logging to OBSERVE whether it terminates or infinite-loops, and to see the
 * exact value of `len` used in `off += len` when an unclosed quote is hit.
 *
 * If the finding is correct, `len` is 0 on the unclosed-quote iteration and
 * `off` never advances -> infinite loop (we cap at 100000 iters and report).
 * If `len` is always >=1 in continuing iterations, the loop terminates.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>

enum ng_parse_token {
	T_EOF, T_ERROR, T_WORD, T_STRING, T_LBRACE, T_RBRACE,
	T_LBRACKET, T_RBRACKET, T_EQUALS
};

/* ---- faithful copy of ng_get_string_token (1737-1818) ---- */
static char *
ng_get_string_token(const char *s, int *startp, int *lenp, int *slenp)
{
	char *cbuf, *p;
	int start, off;
	int slen;

	while (isspace(s[*startp]))
		(*startp)++;
	start = *startp;
	if (s[*startp] != '"')
		return (NULL);
	cbuf = malloc(strlen(s + start));		/* was kmalloc */
	if (cbuf == NULL)
		return (NULL);
	strcpy(cbuf, s + start + 1);
	for (slen = 0, off = 1, p = cbuf; *p != '\0'; slen++, off++, p++) {
		if (*p == '"') {
			*p = '\0';
			*lenp = off + 1;
			if (slenp != NULL)
				*slenp = slen;
			return (cbuf);
		} else if (p[0] == '\\' && p[1] != '\0') {
			int x, k;
			char *v;

			strcpy(p, p + 1);
			v = p;
			switch (*p) {
			case 't': *v = '\t'; off++; continue;
			case 'n': *v = '\n'; off++; continue;
			case 'r': *v = '\r'; off++; continue;
			case 'v': *v =  '\v'; off++; continue;
			case 'f': *v =  '\f'; off++; continue;
			case '"': *v =  '"'; off++; continue;
			case '0': case '1': case '2': case '3':
			case '4': case '5': case '6': case '7':
				for (x = k = 0; k < 3 && *v >= '0' && *v <= '7'; v++) {
					x = (x << 3) + (*v - '0'); off++;
				}
				*--v = (char)x; break;
			case 'x':
				for (v++, x = k = 0; k < 2 && isxdigit(*v); v++) {
					x = (x << 4) + (isdigit(*v) ?
					      (*v - '0') : (tolower(*v) - 'a' + 10));
					off++;
				}
				*--v = (char)x; break;
			default: continue;
			}
			strcpy(p, v);
		}
	}
	free(cbuf);					/* was kfree */
	return (NULL);					/* no closing quote */
}

/* ---- faithful copy of ng_parse_get_token (1690-1735) ---- */
static enum ng_parse_token
ng_parse_get_token(const char *s, int *startp, int *lenp)
{
	char *t;
	int i;

	while (isspace(s[*startp]))
		(*startp)++;
	switch (s[*startp]) {
	case '\0': *lenp = 0; return T_EOF;
	case '{': *lenp = 1; return T_LBRACE;
	case '}': *lenp = 1; return T_RBRACE;
	case '[': *lenp = 1; return T_LBRACKET;
	case ']': *lenp = 1; return T_RBRACKET;
	case '=': *lenp = 1; return T_EQUALS;
	case '"':
		if ((t = ng_get_string_token(s, startp, lenp, NULL)) == NULL)
			return T_ERROR;
		free(t);
		return T_STRING;
	default:
		for (i = *startp + 1; s[i] != '\0' && !isspace(s[i])
		    && s[i] != '{' && s[i] != '}' && s[i] != '['
		    && s[i] != ']' && s[i] != '=' && s[i] != '"'; i++)
			;
		*lenp = i - *startp;
		return T_WORD;
	}
}

/* ---- faithful copy of ng_parse_skip_value (1651-1683) + instrumentation ---- */
static int iters;
static int
ng_parse_skip_value(const char *s, int off0, int *lenp)
{
	int len, nbracket, nbrace;
	int off = off0;

	len = nbracket = nbrace = 0;
	do {
		enum ng_parse_token tok = ng_parse_get_token(s, &off, &len);
		if (iters < 40)
			fprintf(stderr, "    iter=%d off=%d len=%d tok=%d "
			    "nbracket=%d nbrace=%d char='", iters, off, len,
			    tok, nbracket, nbrace);
		switch (tok) {
		case T_LBRACKET: nbracket++; break;
		case T_LBRACE: nbrace++; break;
		case T_RBRACKET:
			if (nbracket-- == 0) return (EINVAL);
			break;
		case T_RBRACE:
			if (nbrace-- == 0) return (EINVAL);
			break;
		case T_EOF:
			return (EINVAL);
		default:
			break;
		}
		int prev_off = off;
		off += len;
		if (iters < 40)
			fprintf(stderr, "%c' off_after=%d (delta=%d)\n",
			    s[prev_off] ? s[prev_off] : '?', off, len);
		if (++iters > 100000) {
			fprintf(stderr, "    *** LOOP CAP HIT (100000 iters) -- "
			    "INFINITE LOOP CONFIRMED ***\n");
			return (-1);
		}
	} while (nbracket > 0 || nbrace > 0);
	*lenp = off - off0;
	return (0);
}

int main(void)
{
	const char *tests[] = {
		"[1 \"abc",		/* finding's claimed trigger shape */
		"[\"abc",
		"{\"abc",
		"[[\"abc",
		"[abcdef\"abc",
		"[ ]",			/* benign: unclosed bracket */
		"[1 2 3]",		/* benign: normal array */
		"\"abc",		/* unclosed quote, no bracket */
		NULL
	};
	for (int i = 0; tests[i]; i++) {
		int len = -999, rc;
		iters = 0;
		fprintf(stderr, "\n=== test %d: input=\"%s\" ===\n", i, tests[i]);
		rc = ng_parse_skip_value(tests[i], 0, &len);
		fprintf(stderr, "-> rc=%d len=%d iters=%d\n", rc, len, iters);
	}
	return 0;
}