Fixed overwriting errors

6 files changed, 143 insertions, 91 deletions

diff --git a/compiler/eval.c b/compiler/eval.c
index ae06dfa..d873088 100644
--- a/compiler/eval.c
+++ b/compiler/eval.c
@@ -14,58 +14,112 @@ void free_rules_until(fuspel* new, fuspel* old) {
 	}
 }
 
-fuspel* match_expr(fuspel* rules, expression* to_match, expression* expr) {
+typedef struct replacements {
+	char* what;
+	expression* with;
+	struct replacements* rest;
+} replacements;
+
+void replace(char* name, expression* new, expression* expr) {
+	if (!expr)
+		return;
+
+	switch (expr->kind) {
+		case EXPR_NAME:
+			if (!strcmp(expr->var1, name)) {
+				cpy_expression(expr, new);
+				break;
+			}
+		case EXPR_INT:
+			break;
+		case EXPR_TUPLE:
+		case EXPR_LIST:
+		case EXPR_APP:
+			replace(name, new, expr->var1);
+			replace(name, new, expr->var2);
+			break;
+	}
+}
+
+void replace_all(replacements* repls, expression* expr) {
+	while (repls) {
+		replace(repls->what, repls->with, expr);
+		repls = repls->rest;
+	}
+}
+
+replacements* push_replacement(char* what, expression* with, replacements* rest) {
+	replacements* new = my_calloc(1, sizeof(replacements));
+	new->what = what;
+	new->with = my_calloc(1, sizeof(expression));
+	cpy_expression(new->with, with);
+	new->rest = rest;
+	return new;
+}
+
+void free_replacements(replacements* repls) {
+	if (repls) {
+		free_replacements(repls->rest);
+		repls->rest = NULL;
+		free_expression(repls->with);
+		my_free(repls->with);
+		my_free(repls);
+	}
+}
+
+unsigned match_expr(fuspel* rules, expression* to_match, expression* expr,
+		replacements** repls) {
 	if (to_match->kind != EXPR_NAME) {
 		expr = eval_rnf(rules, expr);
 		if (!expr)
-			return NULL;
+			return 0;
 	}
 
+	unsigned matches;
+
 	switch (to_match->kind) {
 		case EXPR_NAME:
-			rules = push_fuspel(rules);
-			rules->rule.name = my_calloc(1, strlen(to_match->var1) + 1);
-			strcpy(rules->rule.name, to_match->var1);
-			rules->rule.args = NULL;
-			cpy_expression(&rules->rule.rhs, expr);
-			return rules;
+			*repls = push_replacement(to_match->var1, expr, *repls);
+			free_expression(expr);
+			my_free(expr);
+			return 1;
 		case EXPR_INT:
-			;unsigned matches = eq_expression(to_match, expr);
+			matches = eq_expression(to_match, expr);
 			free_expression(expr);
 			my_free(expr);
-			return matches ? rules : NULL;
+			return matches;
 		case EXPR_LIST:
 			if (!to_match->var1) { // empty list
-				unsigned matches = eq_expression(to_match, expr);
+				matches = eq_expression(to_match, expr);
 				free_expression(expr);
 				my_free(expr);
-				return matches ? rules : NULL;
+				return matches;
 			}
 		case EXPR_TUPLE:
-			;fuspel* _rules = match_expr(rules, to_match->var1, expr->var1);
-			if (!_rules) {
+			if (to_match->kind != expr->kind) {
 				free_expression(expr);
 				my_free(expr);
-				return NULL;
+				return 0;
 			}
-			fuspel* __rules = match_expr(_rules, to_match->var2, expr->var2);
-			if (!__rules)
-				free_rules_until(_rules, rules);
+			matches =
+				match_expr(rules, to_match->var1, expr->var1, repls) &&
+				match_expr(rules, to_match->var2, expr->var2, repls);
 			free_expression(expr);
 			my_free(expr);
-			return __rules;
+			return matches;
 		default:
 			free_expression(expr);
 			my_free(expr);
-			return NULL;
+			return 0;
 	}
 }
 
-fuspel* match_rule(fuspel* rules, rewrite_rule* rule, expression* expr) {
+unsigned match_rule(fuspel* rules, rewrite_rule* rule, expression* expr,
+		replacements** repls) {
 	switch (expr->kind) {
 		case EXPR_NAME:
 			return (!strcmp(expr->var1, rule->name) &&
-				empty_args_list(rule->args)) ? rules : NULL;
+				empty_args_list(rule->args)) ? 1 : 0;
 		case EXPR_APP:
 			;expression** expr_args = flatten_app_args(expr);
 			unsigned char i = 0;
@@ -74,13 +128,11 @@ fuspel* match_rule(fuspel* rules, rewrite_rule* rule, expression* expr) {
 				arg_list* args = rule->args;
 				fuspel* _rules = rules;
 				while (!empty_args_list(args)) {
-					fuspel* __rules = match_expr(_rules, &args->elem, _expr);
-					if (!__rules) {
+					if (!match_expr(_rules, &args->elem, _expr, repls)) {
 						free_rules_until(_rules, rules);
 						my_free(expr_args);
-						return NULL;
+						return 0;
 					}
-					_rules = __rules;
 
 					args = args->rest;
 					_expr = expr_args[++i];
@@ -88,27 +140,14 @@ fuspel* match_rule(fuspel* rules, rewrite_rule* rule, expression* expr) {
 					if (!empty_args_list(args) && !_expr) {
 						free_rules_until(_rules, rules);
 						my_free(expr_args);
-						return NULL;
+						return 0;
 					}
 				}
 				my_free(expr_args);
-				return _rules;
+				return 1;
 			}
 			my_free(expr_args);
 		default:
-			return NULL;
-	}
-}
-
-unsigned apply(expression* result, rewrite_rule* rule, expression* expr) {
-	switch (expr->kind) {
-		case EXPR_NAME:
-			cpy_expression(result, &rule->rhs);
-			return 1;
-			break;
-		case EXPR_APP:
-			// TODO
-		default:
 			return 0;
 	}
 }
@@ -117,7 +156,8 @@ expression* eval_rnf(fuspel* rules, expression* expr) {
 	expression* result = my_calloc(1, sizeof(expression));
 
 	fuspel* _rules = rules;
-	fuspel* new_rules;
+
+	replacements** repls = my_calloc(1, sizeof(replacements*));
 
 	switch (expr->kind) {
 		case EXPR_INT:
@@ -129,20 +169,29 @@ expression* eval_rnf(fuspel* rules, expression* expr) {
 		case EXPR_NAME:
 		case EXPR_APP:
 			while (_rules) {
-				new_rules = match_rule(rules, &_rules->rule, expr);
-				if (new_rules) {
-					rules = new_rules;
-					my_free(result);
-					result = eval_rnf(rules, &_rules->rule.rhs);
-					free_rules_until(new_rules, rules);
+				if (match_rule(rules, &_rules->rule, expr, repls)) {
+					cpy_expression(result, &_rules->rule.rhs);
+					replace_all(*repls, result);
+					free_replacements(*repls);
+					my_free(repls);
+					expression* old_result = result;
+					result = eval_rnf(rules, old_result);
+					free_expression(old_result);
+					my_free(old_result);
 					return result;
 				}
+				free_replacements(*repls);
+				my_free(repls);
+				repls = my_calloc(1, sizeof(replacements*));
 				_rules = _rules->rest;
 			}
 			cpy_expression(result, expr);
 			break;
 	}
 
+	free_replacements(*repls);
+	my_free(repls);
+
 	return result;
 }
 
@@ -152,6 +201,8 @@ expression* eval(fuspel* rules, expression* expr) {
 	expression *e1, *e2;
 	fuspel* _rules = rules;
 
+	replacements** repls = my_calloc(1, sizeof(replacements*));
+
 	switch (expr->kind) {
 		case EXPR_INT:
 			cpy_expression(result, expr);
@@ -160,13 +211,20 @@ expression* eval(fuspel* rules, expression* expr) {
 		case EXPR_NAME:
 		case EXPR_APP:
 			while (_rules) {
-				fuspel* new_rules = match_rule(rules, &_rules->rule, expr);
-				if (new_rules) {
-					my_free(result);
-					result = eval(new_rules, &_rules->rule.rhs);
-					free_rules_until(new_rules, rules);
+				if (match_rule(rules, &_rules->rule, expr, repls)) {
+					cpy_expression(result, &_rules->rule.rhs);
+					replace_all(*repls, result);
+					expression* old_result = result;
+					result = eval(rules, old_result);
+					free_expression(old_result);
+					my_free(old_result);
+					free_replacements(*repls);
+					my_free(repls);
 					return result;
 				}
+				free_replacements(*repls);
+				my_free(repls);
+				repls = my_calloc(1, sizeof(replacements*));
 				_rules = _rules->rest;
 			}
 			cpy_expression(result, expr);
@@ -187,5 +245,8 @@ expression* eval(fuspel* rules, expression* expr) {
 			break;
 	}
 
+	free_replacements(*repls);
+	my_free(repls);
+
 	return result;
 }
diff --git a/compiler/fuspelc.c b/compiler/fuspelc.c
index 9964349..e0e34b7 100644
--- a/compiler/fuspelc.c
+++ b/compiler/fuspelc.c
@@ -8,44 +8,28 @@
 #include "eval.h"
 #include "print.h"
 
-//static char* program =
-//	"take_one [x:_] = [x:[]];"
-//	"inflist = [1:inflist];"
-//	"main = take_one inflist;";
-//static char* program =
-//	"append []     ys = ys;"
-//	"append [x:xs] ys = [x:append xs ys];"
-//	"main = append [1:[2:[3:[]]]] [5:[6:[]]];";
-static char* program =
-	"singleton x = [x:[]];"
-	"push x y = [x:y];"
-	"is_zero 0 = 1;"
-	"is_zero _ = 0;"
-	"flip (a,b) = (b,a);"
-	"main = push 3 (singleton (flip (is_zero 5, is_zero 0)));";
-//static char* program =
-//	"trip x y z = (x,(y,z));"
-//	"main       = trip (trip 1 2 3) 10 (trip a b c);";
-//static char* program =
-//	"return   = (n,1);"
-//	"main     = return;";
-
 int main(void) {
-	token_list* tokens = lex(program);
-	
-	if (!tokens)
-		error(10, "Couldn't lex program.");
-	
-	printf("\n\nLexed program:\n");
-	print_token_list(tokens);
-	printf("\n");
+	token_list* tokens = NULL;
+
+	while (!feof(stdin)) {
+		char program[79];
+		if (!fgets(program, 79, stdin)) {
+			if (feof(stdin))
+				break;
+			error(11, "Couldn't read input.");
+		}
+
+		tokens = lex(tokens, program);
+		if (!tokens)
+			error(12, "Couldn't lex program.");
+	}
 	
 	fuspel* pgm = parse(tokens);
 	free_token_list(tokens);
 	free(tokens);
 	
 	if (!pgm)
-		error(10, "Couldn't parse program.");
+		error(13, "Couldn't parse program.");
 
 	printf("\nParsed program:\n");
 	print_fuspel(pgm);
diff --git a/compiler/lex.c b/compiler/lex.c
index e9cb65b..8255e11 100644
--- a/compiler/lex.c
+++ b/compiler/lex.c
@@ -34,13 +34,20 @@ unsigned char lex_name_length(char* input) {
 	return n;
 }
 
-token_list* lex(char* input) {
+token_list* lex(token_list* list, char* input) {
 	if (input[0] == 0) {
 		return NULL;
 	}
 	
-	token_list* list = my_calloc(1, sizeof(token_list));
-	token_list* first_list = list;
+	token_list* first_list;
+	if (list) {
+		first_list = list;
+		while (list->rest) list = list->rest;
+		list->rest = my_calloc(1, sizeof(token_list));
+		list = list->rest;
+	} else {
+		first_list = list = my_calloc(1, sizeof(token_list));
+	}
 
 	while (*input) {
 		list->elem.var = NULL;
diff --git a/compiler/lex.h b/compiler/lex.h
index 61a7170..268d0e4 100644
--- a/compiler/lex.h
+++ b/compiler/lex.h
@@ -3,6 +3,6 @@
 
 #include "syntax.h"
 
-token_list* lex(char*);
+token_list* lex(token_list*, char*);
 
 #endif
diff --git a/compiler/parse.c b/compiler/parse.c
index e7e2ca7..b9aeab6 100644
--- a/compiler/parse.c
+++ b/compiler/parse.c
@@ -78,7 +78,6 @@ token_list* parse_simple_expression(expression* expr, token_list* list) {
 
 			if (!list || list->elem.kind != TOKEN_COLON) {
 				free_expression(expr->var1);
-				my_free(expr->var1);
 				return NULL;
 			}
 			
@@ -172,8 +171,6 @@ token_list* parse_expression_no_app(expression* expr, token_list* list) {
 	}
 
 	list = parse_simple_expression(expr, list);
-	if (!list)
-		free_expression(expr);
 
 	return list;
 }
diff --git a/compiler/syntax.c b/compiler/syntax.c
index b4ff9dc..3d5e18d 100644
--- a/compiler/syntax.c
+++ b/compiler/syntax.c
@@ -22,6 +22,7 @@ unsigned empty_args_list(arg_list* list) {
 }
 
 void cpy_expression(expression* dst, expression* src) {
+	free_expression(dst);
 	dst->kind = src->kind;
 	switch (dst->kind) {
 		case EXPR_INT:
@@ -136,6 +137,8 @@ void free_expression(expression* expr) {
 			my_free(expr->var2);
 			break;
 	}
+
+	expr->var1 = expr->var2 = NULL;
 }
 
 void free_arg_list(arg_list* list) {