#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;
} Rule;

char dict[DIC_SZ], *_dict = dict, *syms[PRM_SZ];
unsigned long prime_lut[PRM_SZ], *_prime_lut = prime_lut;
int symbols_len;
Rule rules[RUL_SZ], *_rules = rules;
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 char *
scpy(char *a, char *b)
{
	char *cap = scap(a);
	while(a < cap) *b++ = *a++;
	return b + 1;
}

static int
scmp(char *a, char *b)
{
	char *acap = scap(a), *bcap = scap(b);
	while(a < acap && b < bcap && *a == *b) a++, b++;
	return a == acap && b == bcap;
}

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 char **
find_symbol(char *s)
{
	int i;
	for(i = 0; i < symbols_len; i++)
		if(scmp(s, syms[i])) return &syms[i];
	return NULL;
}

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

static char *
print_template(FILE *f, char *s)
{
	char **symbol;
	while(*s && *s != '}') {
		while(*s && *s < 0x21) s++;
		symbol = find_symbol(s);
		if((symbol = find_symbol(s)) != NULL) {
			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 *
parse_symbol(char **dst, char *s)
{
	char **sym = find_symbol(s);
	if(sym != NULL)
		*dst = *sym;
	else
		*dst = syms[symbols_len++] = _dict, _dict = scpy(s, _dict);
	return scap(s);
}

static char *
parse_rule(char *_s)
{
	char c, *sym, *lhs;
	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) {
			_s = parse_symbol(&sym, _s);
			if(side)
				r->num *= prime_lut[find_symbol(sym) - syms];
			else
				r->den *= prime_lut[find_symbol(sym) - syms];
		}
	}
	if(side) {
		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), 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 == '(')
			while(*(_buf++) != ')');
		else if(_buf[0] == ':' && _buf[1] == ':')
			_buf = parse_rule(_buf + 2);
		else if(*_buf) {
			_buf = parse_symbol(&sym, _buf);
			additive(&accu, prime_lut[find_symbol(sym) - syms]);
		}
	}
}

static void
eval(int fuel)
{
	int pc = 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);
			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;
		}
	}
	putchar('\n'), print_frag(stdout, &accu, 0), putchar('\n');
}

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, 30 Sep 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;
}