#include <stdio.h>

/*
Copyright (c) 2024 Devine Lu Linvega

Permission to use, copy, modify, and distribute this software for any
purpose with or without fee is hereby granted, provided that the above
copyright notice and this permission notice appear in all copies.

THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
WITH REGARD TO THIS SOFTWARE.
*/

#define PRM_SZ 0x200
#define RUL_SZ 0x200
#define DIC_SZ 0x400
#define SRC_SZ 0x8000
#define HLT_SZ 0x100000

typedef struct Frag {
	unsigned char regs[PRM_SZ];
} Frag;

typedef struct Rule {
	unsigned long num, den;
	Frag fnum, fden;
	int exhaustive;
} Rule;

char dict[DIC_SZ], *_dict = dict, *syms[PRM_SZ];
unsigned long prime_lut[PRM_SZ], *_prime_lut = prime_lut;
Rule rules[RUL_SZ], *_rules = rules;
int symbols_len;
Frag accu;

static char *
scap(char *s)
{
	if(*s == '"') {
		s++;
		while(*s && *s != '"') s++;
		return s + 1;
	}
	while(*s > 0x20 && *s != '}') s++;
	return s;
}

static unsigned long
gcd(unsigned long a, unsigned long b)
{
	if(b == 0) return a;
	return gcd(b, a % b);
}

static unsigned int
is_prime(unsigned int num)
{
	unsigned int i = 1;
	while(++i < num)
		if(gcd(i, num) > 1) return 0;
	return 1;
}

static unsigned long
frag_int(Frag *frag)
{
	unsigned long res = 1;
	unsigned int i, j;
	for(i = 0; i < PRM_SZ; i++)
		for(j = 0; j < frag->regs[i]; j++) res *= i;
	return res;
}

static int
mask(Frag *frag, unsigned long num)
{
	unsigned long fac = 2, pow;
	while(num > 1) {
		if(num % fac == 0) {
			pow = 1, num /= fac;
			while(!(num % fac)) num /= fac, pow++;
			if(frag->regs[fac] < pow) return 0;
		} else
			fac++;
	}
	return 1;
}

static void
create(Frag *frag, unsigned long num)
{
	unsigned long fac = 2, pow;
	while(num > 1) {
		if(num % fac == 0) {
			pow = 1, num /= fac;
			while(!(num % fac)) num /= fac, pow++;
			frag->regs[fac] = (char)pow;
		} else
			fac++;
	}
}

static void
additive(Frag *frag, unsigned long num)
{
	unsigned long fac = 2, pow;
	while(num > 1) {
		if(num % fac == 0) {
			pow = 1, num /= fac;
			while(!(num % fac)) num /= fac, pow++;
			frag->regs[fac] += (char)pow;
		} else
			fac++;
	}
}

static void
subtractive(Frag *frag, unsigned long num)
{
	unsigned long fac = 2, pow;
	while(num > 1) {
		if(num % fac == 0) {
			pow = 1, num /= fac;
			while(!(num % fac)) num /= fac, pow++;
			frag->regs[fac] -= (char)pow;
		} else
			fac++;
	}
}

static int
find_symbol(char *s)
{
	int i;
	for(i = 0; i < symbols_len; i++) {
		char *a = s, *b = syms[i];
		char *acap = scap(a), *bcap = scap(b);
		while(a < acap && b < bcap && *a == *b) a++, b++;
		if(a == acap && b == bcap)
			return i;
	}
	return -1;
}

static void print_s(FILE *f, char *symbol);

static char *
print_template(FILE *f, char *s)
{
	char **symbol;
	while(*s && *s != '}') {
		int sid;
		while(*s && *s < 0x21) s++;
		if((sid = find_symbol(s)) >= 0) {
			symbol = &syms[sid];
			if(mask(&accu, prime_lut[symbol - syms])) {
				print_s(f, *symbol);
				while(*s && *s != '}') s++;
				return s + 1;
			}
			s = scap(s);
		} else
			while(*s && *s != '}' && *s > 0x20) fprintf(f, "%c", *s++);
	}
	return s + 1;
}

static void
print_s(FILE *f, char *symbol)
{
	int is_str = *symbol == '"';
	char *_symbol = symbol;
	while(*_symbol && !(*_symbol == '#' && !is_str)) {
		if(*_symbol == '{') {
			_symbol = print_template(f, _symbol + 1);
			continue;
		}
		if(*_symbol != '"')
			fprintf(f, "%c", *_symbol);
		_symbol++;
	}
}

static void
print_frag(FILE *f, Frag *frag, int debug)
{
	unsigned int i, j;
	for(i = 0; i < PRM_SZ; i++) {
		int count = frag->regs[i];
		if(count) {
			for(j = 0; j < PRM_SZ; j++)
				if(prime_lut[j] == i) break;
			print_s(f, syms[j]);
			if(debug) fprintf(f, ".%d", i);
			if(count > 1) fprintf(f, "^%d", count);
			fprintf(f, " ");
		}
	}
}

static char *
walk_number(char *s, int *count)
{
	int value = 0;
	while(*s && *s >= '0' && *s <= '9')
		value *= 10, value += *s - '0', s++;
	*count = value;
	return s;
}

static char *
parse_symbol(char **dst, char *s, int *count)
{
	int sid = find_symbol(s);
	if(sid >= 0) {
		*dst = syms[sid];
		return scap(s);
	} else {
		char *cap = scap(s);
		*dst = syms[symbols_len++] = _dict;
		while(s < cap) {
			if(*s == '^') {
				s = walk_number(s + 1, count);
				break;
			}
			*_dict++ = *s++;
		}
		_dict++;
	}
	return s;
}

static void
validate(Rule *r)
{
	int i, j, reafail = 0;
	for(i = r - rules - 1, r->exhaustive = 1; i >= 0; i--) {
		if(mask(&r->fden, rules[i].den))
			reafail = 1;
		for(j = 0; j < PRM_SZ; j++)
			if(r->fnum.regs[j] && rules[i].fden.regs[j]) r->exhaustive = 0;
	}
	if(reafail)
		fprintf(stderr, "(unreachable)");
	else if(r->exhaustive)
		fprintf(stderr, "(exhaustive)");
	r++;
}

static char *
parse_rule(char *_s)
{
	char c, *sym, *lhs = NULL;
	int side = 0;
	Rule *r = _rules++;
	r->num = r->den = 1;
	while(*_s) {
		while((c = *_s) && (c == 0x09 || c == 0x20)) _s++;
		if(*_s == 0xa || (_s[0] == ':' && _s[1] == ':')) break;
		if(*_s == '>') {
			if(side) {
				_s = parse_rule(lhs);
				break;
			} else
				lhs = _s + 2;
			side = 1, _s++;
		} else if(*_s > 0x20) {
			int count = 1;
			_s = parse_symbol(&sym, _s, &count);
			while(count--)
				if(side)
					r->num *= prime_lut[find_symbol(sym)];
				else
					r->den *= prime_lut[find_symbol(sym)];
		}
	}
	if(side && r->den > 1) {
		create(&r->fnum, r->num), create(&r->fden, r->den);
		fprintf(stderr, ":: %lu/%lu ", r->num, r->den), print_frag(stderr, &r->fden, 1);
		fprintf(stderr, "> "), print_frag(stderr, &r->fnum, 1), validate(r), fprintf(stderr, "\n");
	} else /* forward declarations */
		_rules--;
	return _s;
}

static void
tokenize(char *buf)
{
	char *_buf = buf, *sym;
	while(*_buf) {
		while(*_buf && *_buf < 0x21) _buf++;
		if(_buf[0] == ':' && _buf[1] == ':')
			_buf = parse_rule(_buf + 2);
		else if(*_buf) {
			int count = 1;
			_buf = parse_symbol(&sym, _buf, &count);
			while(count--)
				additive(&accu, prime_lut[find_symbol(sym)]);
		}
	}
}

static void
eval(int fuel)
{
	int pc = 0, steps = 0;
	Rule *r = &rules[pc];
	while(fuel-- && r->den) {
		r = &rules[pc];
		if(!mask(&accu, r->den))
			pc++;
		else {
			unsigned long a = frag_int(&accu);
			if(r->exhaustive) {
				while(mask(&accu, r->den))
					subtractive(&accu, r->den), additive(&accu, r->num);
			} else
				subtractive(&accu, r->den), additive(&accu, r->num);
			if(r->den) {
				fprintf(stderr, "%02d %lu × %lu/%lu = %lu, ", pc, a, r->num, r->den, frag_int(&accu));
				print_frag(stderr, &accu, 0), fprintf(stderr, "\n");
			}
			pc = 0, steps++;
		}
	}
	putchar('\n'), print_frag(stdout, &accu, 0), putchar('\n'), fprintf(stderr, "Completed in %d steps.\n", steps - 1);
}

int
main(int argc, char *argv[])
{
	FILE *f;
	int i, a = 1, repl = 0;
	char c, src[SRC_SZ], *_src = src;
	if(argc < 2) return !printf("Fractran Rewriting, 14 Dec 2024.\nusage: fractran [-i] input.fra [arguments..]\n");
	if(argv[a][0] == '-' && argv[a][1] == 'i') repl = 1, a++;
	if(!(f = fopen(argv[a], "r"))) return !printf("Source missing: %s\n", argv[a]);
	if(!fread(&src, 1, SRC_SZ, f)) return !printf("Source empty: %s\n", argv[a]);
	create(&accu, 1), fclose(f);
	/* memorize */
	for(i = 2; _prime_lut - prime_lut < PRM_SZ; i++)
		if(is_prime(i)) *_prime_lut++ = i;
	/* tokenize */
	tokenize(src), src[0] = 0;
	for(i = a + 1; i < argc; i++)
		tokenize(argv[i]);
	fprintf(stderr, "\nAC %lu, ", frag_int(&accu)), print_frag(stderr, &accu, 0), fprintf(stderr, "\n");
	/* repl */
	eval(HLT_SZ);
	while(repl && fread(&c, 1, 1, stdin))
		if(c == 0xa) {
			tokenize(src), eval(HLT_SZ);
			_src = src, *_src = 0;
		} else
			*_src++ = c, *_src = 0;
	return 0;
}