boolean CAS in C

boolcas.c

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <inttypes.h>
#include <stdbool.h>
#include <string.h>
#include <stdarg.h>


#define FOR(counter, limit)     for( size_t counter = 0; counter < (limit); counter++ )

#define GEN_FOR(counter, cmp, limit)          for( size_t counter=0; counter cmp (limit); counter++ )
#define GEN_FOR_IDX(arr, counter, cmp, limit) for( size_t counter=0; (arr)[counter] cmp (limit); counter++ )

#define MAX(a,b)        (((a) > (b))? (a) : (b))
#define MIN(a,b)        (((a) < (b))? (a) : (b))
#define CLAMP(v,l,h)    MIN(MAX(l, v), h)

enum {
	INVALID,
	
	// 0 1
	ZERO, ONE,
	
	// &*, |+, !~
	AND, OR, NOT,
	
	// () []
	LPAREN1, RPAREN1,
	LPAREN2, RPAREN2,
	
	VAR,
};

struct BoolCASLexer {
	char const *input;
	size_t      idx;
	int         tok;
};

int get_token(struct BoolCASLexer *const l) {
	while( l->input[l->idx] != 0 ) {
		int const chr = l->input[l->idx];
		switch( tolower(chr) ) {
			case ' ': case '\n': case '\t': case '\r': case '\v':
				l->idx++;
				goto loop_continue;
			case '0':
				l->tok = ZERO; l->idx++;
				return 1;
			case '1':
				l->tok = ONE; l->idx++;
				return 1;
			case '&': case '*':
				l->tok = AND; l->idx++;
				return 1;
			case '|': case '+':
				l->tok = OR; l->idx++;
				return 1;
			case '!': case '~':
				l->tok = NOT; l->idx++;
				return 1;
			case '(':
				l->tok = LPAREN1; l->idx++;
				return 1;
			case '[':
				l->tok = LPAREN2; l->idx++;
				return 1;
			case ')':
				l->tok = RPAREN1; l->idx++;
				return 1;
			case ']':
				l->tok = RPAREN2; l->idx++;
				return 1;
			case 'a': case 'b': case 'c': case 'd':
			case 'e': case 'f': case 'g': case 'h':
			case 'i': case 'j': case 'k': case 'l':
			case 'm': case 'n': case 'o': case 'p':
			case 'q': case 'r': case 's': case 't':
			case 'u': case 'v': case 'w': case 'x':
			case 'y': case 'z':
				l->tok = tolower(chr); l->idx++;
				return 1;
		}
loop_continue:;
	}
	l->tok = INVALID;
	return 0;
}


enum ASTType {
	InvalidNode,
	OrNode, AndNode, NotNode,
	VarNode, NotVarNode, LitNode,
	MAX_EXPR_NODES = 2,
};

char const *ast_type_to_cstr(enum ASTType const t) {
	switch( t ) {
		case InvalidNode: return "Invalid Node";
		case OrNode:      return "OR Node";
		case AndNode:     return "AND Node";
		case NotNode:     return "NOT Node";
		case VarNode:     return "Var Node";
		case NotVarNode:  return "NOT Var Node";
		case LitNode:     return "Literal Node";
		default:          return "Unknown";
	}
}


struct BoolCASAST {
	union {
		struct BoolCASAST *expr[MAX_EXPR_NODES];
		int                lit;
	} data;
	enum ASTType tag;
};

struct FlatBoolCASAST {
	union {
		uint16_t  bin_expr[2];
		int32_t   literal;
	}            *data;
	enum ASTType *tags;
	size_t        cap, len;
};


struct BoolCASAST *make_ast(enum ASTType const tag) {
	struct BoolCASAST *ast = calloc(1, sizeof *ast);
	ast->tag = tag;
	return ast;
}

struct BoolCASAST *make_ast_binary(enum ASTType const tag, struct BoolCASAST *const l, struct BoolCASAST *const r) {
	struct BoolCASAST *ast = make_ast(tag);
	ast->data.expr[0] = l;
	ast->data.expr[1] = r;
	return ast;
}

struct BoolCASAST *make_ast_var(int const chr, bool const is_not) {
	struct BoolCASAST *ast = make_ast(is_not? NotVarNode : VarNode);
	ast->data.lit = chr;
	return ast;
}
struct BoolCASAST *make_ast_lit(int const num) {
	struct BoolCASAST *ast = make_ast(LitNode);
	ast->data.lit = !!num;
	return ast;
}

struct BoolCASAST *make_ast_copy(struct BoolCASAST *const n) {
	struct BoolCASAST *ast = make_ast(n->tag);
	switch( n->tag ) {
		case OrNode: case AndNode: case NotNode: {
			FOR(i, MAX_EXPR_NODES) {
				if( n->data.expr[i]==NULL ) {
					continue;
				}
				ast->data.expr[i] = make_ast_copy(n->data.expr[i]);
			}
			break;
		}
		case LitNode: case NotVarNode: case VarNode: {
			ast->data = n->data;
			break;
		}
		default: {
			break;
		}
	}
	return ast;
}

void free_ast(struct BoolCASAST **ast_ref) {
	if( ast_ref==NULL || *ast_ref==NULL ) {
		return;
	}
	//printf("free_ast :: AST ('%p') Tag -> '%s'\n", (*ast_ref), ast_type_to_cstr((*ast_ref)->tag));
	switch( (*ast_ref)->tag ) {
		case OrNode: case AndNode: case NotNode: {
			FOR(i, MAX_EXPR_NODES) {
				//printf("\t\tfree_ast :: from OR/AND/NOT ('%p') going to -> '%p'\n", *ast_ref, (*ast_ref)->data.expr[i]);
				free_ast(&(*ast_ref)->data.expr[i]);
			}
			break;
		}
		default: {
			//printf("free_ast :: AST Lit -> '%c'\n", (*ast_ref)->data.lit);
			break;
		}
	}
	//printf("free_ast :: freeing AST '%p'\n", *ast_ref);
	free(*ast_ref);
	//printf("free_ast :: Nullifying AST\n");
	*ast_ref = NULL;
}

struct BoolCASAST *detach_ast_expr(struct BoolCASAST **node_ref, size_t const i) {
	if( i >= MAX_EXPR_NODES ) {
		return NULL;
	}
	struct BoolCASAST *detached_node = (*node_ref)->data.expr[i];
	(*node_ref)->data.expr[i] = NULL;
	free_ast(node_ref);
	return detached_node;
}

void detach_ast_exprs(struct BoolCASAST **node_ref, struct BoolCASAST *(*exprs)[MAX_EXPR_NODES]) {
	FOR(i, MAX_EXPR_NODES) {
		(*exprs)[i] = (*node_ref)->data.expr[i];
	}
	FOR(i, MAX_EXPR_NODES) {
		(*node_ref)->data.expr[i] = NULL;
	}
	free_ast(node_ref);
}

int is_ast_0(struct BoolCASAST const *ast) {
	return ast->tag==LitNode && ast->data.lit==0;
}
int is_ast_1(struct BoolCASAST const *ast) {
	return ast->tag==LitNode && ast->data.lit==1;
}
int is_ast_var(struct BoolCASAST const *ast, int const check_negate) {
	return ast->tag==VarNode || (check_negate && ast->tag==NotVarNode);
}
int is_ast_var_kind(struct BoolCASAST const *ast, int const chr, int const check_negate) {
	return is_ast_var(ast, check_negate) && ast->data.lit==chr;
}
int ast_get_lit(struct BoolCASAST const *ast, int const check_negate) {
	return ast->tag==LitNode || is_ast_var(ast, check_negate)? ast->data.lit : -1;
}
int asts_are_vars(struct BoolCASAST *(*exprs)[MAX_EXPR_NODES], int const check_negate) {
	int res = 0;
	FOR(i, MAX_EXPR_NODES) {
		res |= is_ast_var((*exprs)[i], check_negate);
	}
	return res;
}
int asts_have_same_lit(struct BoolCASAST *(*exprs)[MAX_EXPR_NODES], int const check_negate) {
	int res = 1;
	int lits[MAX_EXPR_NODES] = {0};
	FOR(i, MAX_EXPR_NODES) {
		lits[i] = ast_get_lit((*exprs)[i], check_negate);
		if( lits[i] < 0 ) {
			return 0;
		}
	}
	for( size_t i=1; i < MAX_EXPR_NODES; i++ ) {
		res = res & (lits[i]==lits[0]);
	}
	return res;
}
int asts_are_same_var(struct BoolCASAST *(*exprs)[MAX_EXPR_NODES], int const check_negate) {
	if( asts_are_vars(exprs, check_negate) ) {
		return asts_have_same_lit(exprs, check_negate);
	}
	return 0;
}

int asts_have_one_expr(struct BoolCASAST *(*exprs)[MAX_EXPR_NODES], ...) {
	va_list args;
	va_start(args, exprs);
	int idx = 0, res = 0;
	for( int i=0; i < MAX_EXPR_NODES; i++ ) {
		enum ASTType ast_tag;
		while( (ast_tag = va_arg(args, enum ASTType)) > 0 ) {
			int const match = (*exprs)[i]->tag==ast_tag;
			res += match;
			if( match > 0 ) {
				idx = i;
			}
		}
		va_start(args, exprs);
	}
	va_end(args);
	if( res <= 0 ) {
		return -1;
	} else if( res > 1 ) {
		return -2;
	} else {
		return idx;
	}
}

/// make sure there's no nested expressions, everything is spaced out between OR expressions.
/// a + ba + ca -> a(1+b+c) = a, factorability of 3
size_t ast_count_factorability(struct BoolCASAST const *ast, int const chr) {
	if( ast==NULL ) {
		return 0;
	}
	
	size_t factors = 0;
	switch( ast->tag ) {
		case AndNode: case OrNode: case NotNode: {
			FOR(i, MAX_EXPR_NODES) {
				factors += ast_count_factorability(ast->data.expr[i], chr);
			}
			break;
		}
		case VarNode: case NotVarNode: {
			if( ast->data.lit==chr ) {
				factors++;
			}
		}
		default:
			break;
	}
	return factors;
}


/**
 * BooleanExpr = OrExpr .
 * OrExpr      = AndExpr *( '|' AndExpr ) .
 * AndExpr     = NotExpr *( '&' NotExpr ) .
 * NotExpr     = *( '!' ) TermExpr .
 * TermExpr    = [a-zA-Z] | '1' | '0' | '(' BooleanExpr ')' | '[' BooleanExpr ']' .
 */
struct BoolCASAST *parse_bool_expr(struct BoolCASLexer *l);
struct BoolCASAST *parse_or_expr(struct BoolCASLexer *l);
struct BoolCASAST *parse_and_expr(struct BoolCASLexer *l);
struct BoolCASAST *parse_not_expr(struct BoolCASLexer *l);
struct BoolCASAST *parse_term_expr(struct BoolCASLexer *l);

struct BoolCASAST *parse_bool_expr(struct BoolCASLexer *const l) {
	get_token(l);
	return parse_or_expr(l);
}

/// OrExpr = AndExpr *( '|' AndExpr ) .
struct BoolCASAST *parse_or_expr(struct BoolCASLexer *const l) {
	struct BoolCASAST *ast = parse_and_expr(l);
	while( l->tok==OR ) {
		get_token(l);
		ast = make_ast_binary(OrNode, ast, parse_and_expr(l));
	}
	return ast;
}

/// AndExpr = NotExpr *( '&' NotExpr ) .
struct BoolCASAST *parse_and_expr(struct BoolCASLexer *const l) {
	struct BoolCASAST *ast = parse_not_expr(l);
	while( l->tok==AND ) {
		get_token(l);
		ast = make_ast_binary(AndNode, ast, parse_not_expr(l));
	}
	return ast;
}

/// NotExpr = *( '!' ) TermExpr .
struct BoolCASAST *parse_not_expr(struct BoolCASLexer *const l) {
	if( l->tok==NOT ) {
		get_token(l);
		struct BoolCASAST *prev_ast = parse_not_expr(l);
		switch( prev_ast->tag ) {
			case VarNode:
				prev_ast->tag = NotVarNode;
				return prev_ast;
			case LitNode:
				prev_ast->data.lit ^= 1;
				return prev_ast;
			default:
				break;
		}
		return make_ast_binary(NotNode, prev_ast, NULL);
	}
	return parse_term_expr(l);
}

/// TermExpr = [a-zA-Z] | '1' | '0' | '(' BooleanExpr ')' | '[' BooleanExpr ']' .
struct BoolCASAST *parse_term_expr(struct BoolCASLexer *const l) {
	struct BoolCASAST *t = NULL;
	switch( l->tok ) {
		case ZERO:
			t = make_ast(LitNode);
			t->data.lit = 0;
			break;
		case ONE:
			t = make_ast(LitNode);
			t->data.lit = 1;
			break;
		case LPAREN1: case LPAREN2: {
			int const END = l->tok==LPAREN1? RPAREN1 : RPAREN2;
			t = parse_bool_expr(l);
			if( l->tok != END ) {
				fprintf(stderr, "missing %s, got '%c'\n", END==RPAREN1? ")" : "]", l->input[l->idx-1]);
				abort();
			}
			break;
		}
		case 'a': case 'b': case 'c': case 'd':
		case 'e': case 'f': case 'g': case 'h':
		case 'i': case 'j': case 'k': case 'l':
		case 'm': case 'n': case 'o': case 'p':
		case 'q': case 'r': case 's': case 't':
		case 'u': case 'v': case 'w': case 'x':
		case 'y': case 'z':
			t = make_ast(VarNode);
			t->data.lit = l->tok;
			break;
		default:
			/// error
			break;
	}
	get_token(l);
	return t;
}


void print_tabs(FILE *const stream, size_t const tabs, int const chr) {
	FOR(i, tabs) {
		fprintf(stream, "%c", chr);
	}
}

void print_ast(struct BoolCASAST *ast, FILE *const stream, size_t const tabs) {
	if( ast==NULL ) {
		return;
	}
	
	print_tabs(stream, tabs, '-');
	switch( ast->tag ) {
		case OrNode:
			fprintf(stream, "OR expression\n");
			print_ast(ast->data.expr[0], stream, tabs+1);
			print_ast(ast->data.expr[1], stream, tabs+1);
			break;
		case AndNode:
			fprintf(stream, "AND expression\n");
			print_ast(ast->data.expr[0], stream, tabs+1);
			print_ast(ast->data.expr[1], stream, tabs+1);
			break;
		case NotNode:
			fprintf(stream, "NOT expression\n");
			print_ast(ast->data.expr[0], stream, tabs+1);
			break;
		case VarNode: case NotVarNode:
			fprintf(stream, "Var expression: '%s%c' | '%p'\n", ast->tag==NotVarNode? "!":"", ast->data.lit, ast);
			if( ast->data.expr[1] != NULL ) {
				print_ast(ast->data.expr[1], stream, tabs+10);
			}
			break;
		case LitNode:
			fprintf(stream, "Num expression: '%i'\n", ast->data.lit);
			break;
		default:
			break;
	}
}

void print_ast_as_expr(struct BoolCASAST *ast, FILE *const stream, int const alt_paren) {
	if( ast==NULL ) {
		return;
	}
	char const *const ops = "+&";
	char const *const parens[][2] = {
		{"(",")"},
		{"[","]"},
		{"{","}"},
	};
	char const *const spacing[] = {
		" %c ", "%c"
	};
	switch( ast->tag ) {
		case OrNode: case AndNode: {
			fprintf(stream, parens[alt_paren % 3][0]);
			print_ast_as_expr(ast->data.expr[0], stream, alt_paren+1);
			fprintf(stream, spacing[ast->tag - OrNode], ops[ast->tag - OrNode]);
			print_ast_as_expr(ast->data.expr[1], stream, alt_paren+1);
			fprintf(stream, parens[alt_paren % 3][1]);
			break;
		}
		case NotNode: {
			fprintf(stream, "!%s", parens[alt_paren % 3][0]);
			print_ast_as_expr(ast->data.expr[0], stream, !alt_paren);
			fprintf(stream, parens[alt_paren % 3][1]);
			break;
		}
		case VarNode: case LitNode: case NotVarNode: {
			fprintf(stream, "%s", ast->tag==NotVarNode? "!" : "");
			fprintf(stream, ast->tag==VarNode||ast->tag==NotVarNode? "%c" : "%i", ast->data.lit);
			break;
		}
		default:
			break;
	}
}


void ast_optimize(struct BoolCASAST **ast_ref);

/// A & 1 = A
/// A | 0 = A
struct BoolCASAST *optimize_identity(struct BoolCASAST **node_ref, int *optimized) {
	if( *node_ref==NULL ) {
		return NULL;
	}
	
	struct BoolCASAST *node = *node_ref;
	if( node->tag==OrNode || node->tag==AndNode ) {
		FOR(i, MAX_EXPR_NODES) {
			node->data.expr[i] = optimize_identity(&node->data.expr[i], optimized);
		}
		
		int (*const num_checker)(struct BoolCASAST const *ast) = node->tag==OrNode? is_ast_0 : is_ast_1;
		FOR(i, MAX_EXPR_NODES) {
			if( (*num_checker)(node->data.expr[!i]) ) {
				*optimized = 1;
				return detach_ast_expr(node_ref, i);
			}
		}
	}
	return *node_ref;
}

/// A & 0 = 0
/// A | 1 = 1
struct BoolCASAST *optimize_annulment(struct BoolCASAST **node_ref, int *optimized) {
	if( *node_ref==NULL ) {
		return NULL;
	}
	
	struct BoolCASAST *node = *node_ref;
	if( node->tag==OrNode || node->tag==AndNode ) {
		FOR(i, MAX_EXPR_NODES) {
			node->data.expr[i] = optimize_annulment(&node->data.expr[i], optimized);
		}
		
		int (*const num_checker)(struct BoolCASAST const *ast) = node->tag==OrNode? is_ast_1 : is_ast_0;
		FOR(i, MAX_EXPR_NODES) {
			if( (*num_checker)(node->data.expr[i]) ) {
				*optimized = 1;
				return detach_ast_expr(node_ref, i);
			}
		}
	}
	return *node_ref;
}

/// A | A = A
/// A & A = A
struct BoolCASAST *optimize_idempotent(struct BoolCASAST **node_ref, int *optimized) {
	if( *node_ref==NULL ) {
		return NULL;
	}
	
	struct BoolCASAST *node = *node_ref;
	if( node->tag==OrNode || node->tag==AndNode ) {
		FOR(i, MAX_EXPR_NODES) {
			node->data.expr[i] = optimize_idempotent(&node->data.expr[i], optimized);
		}
		
		if( asts_are_same_var(&node->data.expr, 0) ) {
			*optimized = 1;
			return detach_ast_expr(node_ref, 0);
		}
	}
	return *node_ref;
}

/// A * !A = 0
/// A + !A = 1
struct BoolCASAST *optimize_complement(struct BoolCASAST **node_ref, int *optimized) {
	if( *node_ref==NULL ) {
		return NULL;
	}
	
	struct BoolCASAST *node = *node_ref;
	if( node->tag==NotNode ) {
		struct BoolCASAST const *const notd_expr = node->data.expr[0];
		if( is_ast_0(notd_expr) || is_ast_1(notd_expr) ) {
			/// !1 = 0, !0 = 1
			struct BoolCASAST *optimized_node = detach_ast_expr(node_ref, 0);
			optimized_node->data.lit ^= 1;
			*optimized = 1;
			return optimized_node;
		} else if( notd_expr->tag==NotNode ) {
			/// Optimize double negation.
			struct BoolCASAST *optimized_node = detach_ast_expr(node_ref, 0);
			optimized_node = detach_ast_expr(&optimized_node, 0);
			*optimized = 1;
			return optimized_node;
		} else if( notd_expr->tag==NotVarNode ) {
			struct BoolCASAST *optimized_node = detach_ast_expr(node_ref, 0);
			optimized_node->tag = VarNode;
			*optimized = 1;
			return optimized_node;
		}
	} else if( node->tag==OrNode || node->tag==AndNode ) {
		FOR(i, MAX_EXPR_NODES) {
			node->data.expr[i] = optimize_complement(&node->data.expr[i], optimized);
		}
		
		if( asts_are_same_var(&node->data.expr, 1) ) {
			/// A & !A = 0
			/// A | !A = 1
			int const old_tag = node->tag;
			free_ast(node_ref);
			*node_ref = make_ast(LitNode);
			(*node_ref)->data.lit = old_tag==OrNode;
			*optimized = 1;
		}
	}
	return *node_ref;
}


/**
 * (a + b)(!a*!b)
 * !a(a + b) & !b(a + b)
 * 
 * 
 * a * (b+c) = ab + ac
 */

/// a(b+c) -> ab + ac
/// a+bc -> (a+b)(a+c) -> aa+ac+ba+bc -> a+ac+ba+bc -> a(1+b+c) + bc -> a + bc
/// !a+bc -> (!a+b)(!a+c) -> !a!a+!ac+b!a+bc -> !a+!ac+b!a+bc -> !a(1+b+c) + bc -> !a + bc
/**
		 AND
		/   \
	   a    OR
		   /  \
		  b    c
		
		  OR
		/    \
	  AND    AND
	 /  \   /   \
	a    b a     c
 */
struct BoolCASAST *distribute(struct BoolCASAST **node_ref, int *optimized) {
	if( *node_ref==NULL ) {
		return NULL;
	}
	
	struct BoolCASAST *const node = *node_ref;
	if( node->tag==OrNode||node->tag==AndNode ) {
		FOR(i, MAX_EXPR_NODES) {
			node->data.expr[i] = distribute(&node->data.expr[i], optimized);
		}
	}
	
	if( node->tag==AndNode ) {
		int const idx = asts_have_one_expr(&node->data.expr, OrNode);
		if( idx >= 0 ) {
			/// a(b+c) -> ab + ac
			struct BoolCASAST *or_expr[MAX_EXPR_NODES] = { NULL };
			detach_ast_exprs(&node->data.expr[idx], &or_expr);
			
			struct BoolCASAST *A1 = detach_ast_expr(node_ref, !idx);
			/// need to make a copy or else you get double free.
			struct BoolCASAST *A2 = make_ast_var(A1->data.lit, A1->tag==NotVarNode);
			
			struct BoolCASAST *AB = make_ast_binary(AndNode, A1, or_expr[0]);
			struct BoolCASAST *AC = make_ast_binary(AndNode, A2, or_expr[1]);
			struct BoolCASAST *distributed = make_ast_binary(OrNode, AB, AC);
			*optimized = 1;
			return distributed;
		} else if( idx == -2 ) { /// both are OR expressions.
			/// (a|b)&(c|d) -> ac | ad | bc | bd
			/// (a|b|c) & (d|e) -> ((a|b)|c) & (d|e) -> (a|b)d | (a|b)e | cd | ce -> ad | ae | bd | be | cd | ce
			/// a|b => X --> (X|c) & (d|e) -> Xd | Xe | cd | Xe
			
			/// (a|b|c) & (d|e|f) -> ad | ae | af | bd | be | bf | cd | ce | cf
			/// ((a|b)|c) & ((d|e)|f) -> (a|b)&(d|e) | (a|b)&f | c&(d|e) | c&f
			
			struct BoolCASAST *LeftOr[MAX_EXPR_NODES]  = { NULL };
			struct BoolCASAST *RightOr[MAX_EXPR_NODES] = { NULL };
			detach_ast_exprs(&node->data.expr[0], &LeftOr);
			detach_ast_exprs(&node->data.expr[1], &RightOr);
			
			struct BoolCASAST *A1 = LeftOr[0];
			struct BoolCASAST *B1 = LeftOr[1];
			struct BoolCASAST *C1 = RightOr[0];
			struct BoolCASAST *D1 = RightOr[1];
			
			struct BoolCASAST *A2 = make_ast_copy(A1);
			struct BoolCASAST *B2 = make_ast_copy(B1);
			struct BoolCASAST *C2 = make_ast_copy(C1);
			struct BoolCASAST *D2 = make_ast_copy(D1);
			
			struct BoolCASAST *AC = make_ast_binary(AndNode, A1, C1);
			struct BoolCASAST *AD = make_ast_binary(AndNode, A2, D1);
			struct BoolCASAST *BC = make_ast_binary(AndNode, B1, C2);
			struct BoolCASAST *BD = make_ast_binary(AndNode, B2, D2);
			
			struct BoolCASAST *ACorAD = make_ast_binary(OrNode, AC, AD);
			struct BoolCASAST *BCorBD = make_ast_binary(OrNode, BC, BD);
			
			node->tag = OrNode;
			node->data.expr[0] = ACorAD;
			node->data.expr[1] = BCorBD;
			*optimized = 1;
			//*node_ref = distribute(node_ref, optimized);
			return *node_ref;
		}
	} else if( node->tag==OrNode ) {
		/// NOTE: Do nothing because we want this in Canonical SOP Form.
		/// a + bc -> (a+b)(a+c) -> aa+ac+ba+bc -> a+ac+ba+bc -> a(1+c+b)+bc -> a+bc
	} else if( node->tag==NotNode ) {
		
	}
	return *node_ref;
}

/// a*b + a*!b -> a(b+!b) = a(1) = a
/// abc + !abc + ab!c -> bc(!a + a) + ab!c -> bc + ab!c -> b(c + a!c) -> b( [c+a][c+!c = 1] ) -> bc + ba
///                   -> ab(c + !c) + !abc -> ab + !abc -> b(a + !ac) -> b( [a+!a = 1][a+c] ) -> bc + ba
struct BoolCASAST *factor(struct BoolCASAST **node_ref, int *optimized) {
	if( *node_ref==NULL ) {
		return NULL;
	}
	
	struct BoolCASAST *const node = *node_ref;
	if( node->tag==OrNode||node->tag==AndNode ) {
		FOR(i, MAX_EXPR_NODES) {
			node->data.expr[i] = factor(&node->data.expr[i], optimized);
		}
	}
	
	return *node_ref;
}

/// !a!b -> !(a+b) == a !+ b NOR
/// !a+!b -> !(a*b) == a !& b NAND

/// (a+b)(!a&!b) -> a!a + a!b + !ab + b!b -> 0 + !ab + a!b + 0 -> !ab + a!b -> a^b XOR
/// ab + !a!b -> !(a^b) XNOR
struct BoolCASAST *de_morgans(struct BoolCASAST **node_ref, int *optimized) {
	if( *node_ref==NULL ) {
		return NULL;
	}
	
	struct BoolCASAST *const node = *node_ref;
	if( node->tag==OrNode||node->tag==AndNode ) {
		FOR(i, MAX_EXPR_NODES) {
			node->data.expr[i] = de_morgans(&node->data.expr[i], optimized);
		}
	}
	
	/// convert NANDs and NORs into ANDs and ORs respectively.
	if( node->tag==NotNode ) {
		struct BoolCASAST **expr = &node->data.expr[0];
		switch( (*expr)->tag ) {
			/// NAND
			/// !(a*b) -> !a + !b
			
			/// !(a*b*c) -> !([a*b]*c)
			/// -> !a + !(b*c)
			/// -> !a + !b + !(c) -> !a+!b+!c
			
			/// !(a*b*c*d) -> !({[a*b]*c}*d)
			case AndNode: {
				int const var_idx = asts_have_one_expr(&node->data.expr, VarNode, NotVarNode);
				*expr = de_morgans(expr, optimized);
				struct BoolCASAST *or_expr = make_ast(OrNode);
				
				break;
			}
			
			/// NOR
			case OrNode: {
				break;
			}
			default:
		}
	}
	
	return *node_ref;
}

void ast_optimize_basic(struct BoolCASAST **ast_ref) {
	if( ast_ref==NULL || *ast_ref==NULL ) {
		return;
	}
	for( int optimized=0; 1; optimized=0 ) {
		switch( (*ast_ref)->tag ) {
			case OrNode: case AndNode: {
				*ast_ref = optimize_idempotent(ast_ref, &optimized);
				*ast_ref = optimize_identity  (ast_ref, &optimized);
				*ast_ref = optimize_annulment (ast_ref, &optimized);
				*ast_ref = optimize_complement(ast_ref, &optimized);
				break;
			}
			case NotNode: {
				*ast_ref = optimize_complement(ast_ref, &optimized);
				break;
			}
			default:
		}
		if( optimized <= 0 ) {
			break;
		}
	}
}

void ast_optimize(struct BoolCASAST **ast_ref) {
	if( ast_ref==NULL || *ast_ref==NULL ) {
		return;
	}
	switch( (*ast_ref)->tag ) {
		case OrNode: case AndNode: case NotNode:
			ast_optimize_basic(ast_ref);
			break;
		default:
	}
}


enum {
	/// x2 for negatives
	/// 'z' - 'a' is 25, +1 == 26
	/// 26 * 2 == 52
	MAX_SYMS = ('z' - 'a' + 1) * 2,
};
static struct {
	size_t count[MAX_SYMS];             /// how many of this var exists.
	
	/// this uses ->data.expr[1] as a next node.
	struct BoolCASAST *sym_list[MAX_SYMS]; /// what nodes use the symbol.
} sym_table;

/// indexing scheme: 0-25 -> var, 26-51 -> complement of var.
static inline size_t chr_to_index(int const chr, int const negated) {
	if( chr < 'a' || chr > 'z' ) {
		return -1UL;
	}
	return (chr - 'a') + (negated * 26U);
}
static inline int index_to_chr(size_t const idx, int *negated) {
	if( idx >= MAX_SYMS ) {
		return -1UL;
	}
	*negated = idx >= 26;
	return 'a' + (idx % 26);
}

void initialize_symtable(void) {
	FOR(i, MAX_SYMS) {
		sym_table.sym_list[i] = NULL;
		sym_table.count[i] = 0;
	}
}

void print_symtable(void) {
	FOR(i, MAX_SYMS) {
		size_t const c = sym_table.count[i];
		if( c==0 ) {
			continue;
		}
		int negated = 0;
		int const chr = index_to_chr(i, &negated);
		printf("symbol :: '%s%c' -> count: %zu\n", negated? "!" : "", chr, c);
		printf("nodes of sym::\n");
		
		size_t j = 0;
		for( struct BoolCASAST *n = sym_table.sym_list[i]; n != NULL && j < c; n = n->data.expr[1] ) {
			printf("node(%zu) :: %p - %c\n", j++, (void*)(n), n->data.lit);
		}
	}
}
/*
void collect_var_refs(struct BoolCASAST *const ast) {
	if( ast==NULL ) {
		return;
	}
	
	switch( ast->tag ) {
		case OrNode: case AndNode: case NotNode:
			FOR(i, MAX_EXPR_NODES) {
				collect_var_refs(ast->data.expr[i]);
			}
			break;
		case VarNode:
		case NotVarNode: {
			size_t const sym_index = chr_to_index(ast->data.lit, ast->tag==NotVarNode);
			sym_table.count[sym_index]++;
			if( sym_table.sym_list[sym_index]==NULL ) {
				ast->data.expr[1] = NULL;
				sym_table.sym_list[sym_index] = ast;
			} else {
				/// n->next = head;
				/// head = n;
				ast->data.expr[1] = sym_table.sym_list[sym_index];
				sym_table.sym_list[sym_index] = ast;
			}
			break;
		}
		default:
			break;
	}
}
*/

int main() {
	/*
	char const *test_cases[] = {
		/// optimization tests.
		"1 | 0",
		"0 | 1",
		"0 & 1",
		"1 & 0",
		"1 & 1",
		"0 & 0",
		"1 | 1",
		"0|0",
		"a & a",
		"a | 1",
		"a & 1",
		"a | a",
		"a | 1",
		"!0", "!!a & 1", "!a & 1", "!a | 0", "!a & 0",
		"a & !a", "!a & a", "!a | a", "a | !a", "c&(a|b)", "a&(b|c)",
		/// a(a+b) -> aa + ba = a + ba -> a(1+b) = a
		"a&(a|b)",
		"!a&(a|b)",
		"a&(a|b|c)",
		"(a|b)&(a|c)",
		"(a|b|c) & (d|e)",
		"!(a|b|c) & (d|e)",
		"(a|b|c) & (d|e|f)",
		NULL,
	};
	*/
	
	//GEN_FOR_IDX(test_cases, i, !=, NULL) {
	for(;;) {
		char expr_string[sizeof(size_t) * 1000] = {0};
		puts("Enter an Expression (+ -OR, & -AND): ");
		if( fgets(expr_string, sizeof expr_string, stdin)==NULL ) {
			continue;
		}
		struct BoolCASLexer lexer = { expr_string, .idx = 0 };
		struct BoolCASAST *ast = parse_bool_expr(&lexer);
		puts("\nBefore Optimization");
		print_ast(ast, stdout, 0);
		print_ast_as_expr(ast, stdout, false);
		puts("");
		///*
		ast_optimize(&ast);
		puts("\nAfter Optimization");
		print_ast(ast, stdout, 0);
		print_ast_as_expr(ast, stdout, false);
		puts("");
		//*/
		//initialize_symtable();
		//collect_var_refs(ast);
		//print_symtable();
		puts("");
		free_ast(&ast);
		puts("==========================\npress Enter to continue or Something to quit.");
		enum{ THROWAWAY_LEN = 5 };
		if( strlen(fgets((char[THROWAWAY_LEN]){0}, THROWAWAY_LEN, stdin)) > 1 ) {
			break;
		}
	}
}

/*
static size_t binary_search(uint8_t const *const A, size_t const len, void const *const value, size_t const bytes) {
	size_t
		L = 0,
		R = len - 1
	;
	while( L <= R ) {
		size_t const m = (L+R) / 2;
		if( m > len ) {
			break;
		}
		int const cmp = memcmp(&A[m * bytes], value, bytes);
		if( cmp < 0 ) {
			L = m + 1;
		} else if( cmp > 0 ) {
			R = m - 1;
		} else {
			return m;
		}
	}
	return -1UL;
}
static int sort(uint8_t *const A, size_t const len, size_t const bytes) {
	uint8_t *temp = calloc(bytes, sizeof *temp);
	if( temp==NULL ) {
		return 0;
	}
	FOR(i, len) {
		FOR(j, len) {
			if( i==j ) {
				continue;
			}
			size_t const i_idx = (i * bytes);
			size_t const j_idx = (j * bytes);
			if( memcmp(&A[i * bytes], &A[j * bytes], bytes) < 0 ) {
				FOR(n, bytes) {
					temp[n] = A[i_idx + n];
				}
				FOR(n, bytes) {
					A[i_idx + n] = A[j_idx + n];
				}
				FOR(n, bytes) {
					A[j_idx + n] = temp[n];
				}
			}
		}
	}
	free(temp);
	return 1;
}
*/