shithub: pprolog

--- a/builtins.c

+++ b/builtins.c

@@ -8,7 +8,7 @@

 #define BuiltinProto(name) int name(Term *, Binding **, Module *)

 #define Match(X, Y) (runestrcmp(name, X) == 0 && arity == Y)

 #define Throw(What) do{\

-	Goal *g = malloc(sizeof(Goal)); \

+	Goal *g = gmalloc(sizeof(Goal)); \

 	g->goal = What; \

 	g->module = usermodule; \

 	g->catcher = nil; \

@@ -504,7 +504,7 @@

 	Term *catcher = catchgoal->next;

 	Term *recover = catcher->next;

-	Goal *catchframe = malloc(sizeof(Goal));

+	Goal *catchframe = gmalloc(sizeof(Goal));

 	catchframe->goal = recover;

 	catchframe->module = module;

 	catchframe->catcher = catcher;

@@ -511,7 +511,7 @@

 	catchframe->next = goalstack;

 	goalstack = catchframe;

-	Goal *g = malloc(sizeof(Goal));

+	Goal *g = gmalloc(sizeof(Goal));

 	g->goal = catchgoal;

 	g->module = module;

 	g->catcher = nil;

@@ -543,7 +543,7 @@

 				return 0;

 			}else{

 				goalstack = g->next;

-				Goal *newgoal = malloc(sizeof(Goal));

+				Goal *newgoal = gmalloc(sizeof(Goal));

 				newgoal->goal = copyterm(g->goal, nil);

 				newgoal->module = module;

 				newgoal->catcher = nil;

--- a/eval.c

+++ b/eval.c

@@ -20,12 +20,12 @@

 		and to get the result we can unify the original query with the one at the bottom of the stack, to get the bindings

 		applied.

*/

-		goalstack = malloc(sizeof(Goal));

+		goalstack = gmalloc(sizeof(Goal));

 		goalstack->goal = copyterm(query, nil);

 		goalstack->module = usermodule;

 		goalstack->catcher = nil;

 		goalstack->next = nil;

-		Goal *protector = malloc(sizeof(Goal));

+		Goal *protector = gmalloc(sizeof(Goal));

 		protector->goal = nil;

 		protector->module = usermodule;

 		protector->catcher = mkvariable(L"catch-var");

@@ -125,7 +125,7 @@

 			}else

 				t = typeerror(L"module", moduleterm);

-		Goal *g = malloc(sizeof(Goal));

+		Goal *g = gmalloc(sizeof(Goal));

 		g->goal = t;

 		g->module = module;

 		g->catcher = nil;

@@ -198,7 +198,7 @@

 			if(runestrcmp(left->text, L"_") == 0)

 				continue; /* _ doesn't introduce a new binding */

-			Binding *b = malloc(sizeof(Binding));

+			Binding *b = gmalloc(sizeof(Binding));

 			b->name = left->text;

 			b->nr = left->clausenr;

 			b->value = right;

@@ -280,7 +280,7 @@

 copygoals(Goal *goals)

 	if(goals != nil){

-		Goal *g = malloc(sizeof(Goal));

+		Goal *g = gmalloc(sizeof(Goal));

 		g->module = goals->module;

 		if(goals->goal)

 			g->goal = copyterm(goals->goal, nil);

@@ -308,7 +308,7 @@

 		clause = findclause(alt, goal, &altbindings);

 		if(clause){

 			/* Add choicepoint here */

-			Choicepoint *cp = malloc(sizeof(Choicepoint));

+			Choicepoint *cp = gmalloc(sizeof(Choicepoint));

 			cp->goalstack = copygoals(goals);

 			cp->next = nil;

 			cp->alternative = clause;

--- a/fns.h

+++ b/fns.h

@@ -76,4 +76,8 @@

 Term *listtail(Term *);

 /* arithmetic.c */

-Term *aritheval(Term *, int *);

\ No newline at end of file

+Term *aritheval(Term *, int *);

+/* garbage.c */

+void *gmalloc(ulong);

+vlong collectgarbage(void);

\ No newline at end of file

--- /dev/null

+++ b/garbage.c

@@ -1,0 +1,180 @@

+#include <u.h>

+#include <libc.h>

+#include <bio.h>

+#include "dat.h"

+#include "fns.h"

+typedef struct Allocation Allocation;

+struct Allocation

+{

+	ulong size;

+	int reachable;

+	void *data;

+	Allocation *next;

+	Allocation *prev;

+};

+static void mark(void *);

+static void freealloc(Allocation *);

+static void markmodules(void);

+static void markgoalstack(Goal *);

+static void markchoicestack(void);

+static void markpredicates(Predicate *);

+static void markclauses(Clause *);

+static void markterm(Term *);

+static void markbindings(Binding *);

+static Allocation *allocations;

+void *

+gmalloc(ulong size)

+{

+	Allocation *a = malloc(sizeof(Allocation));

+	a->size = size;

+	a->reachable = 1;

+	a->data = malloc(size);

+	a->prev = nil;

+	a->next = allocations;

+	if(allocations)

+		allocations->prev = a;

+	allocations = a;

+	return a->data;

+}

+vlong

+collectgarbage(void)

+{

+	ulong collected = 0;

+	Allocation *a;

+	/* Start by marking all allocations as unreachable */

+	for(a = allocations; a != nil; a = a->next)

+		a->reachable = 0;

+	/* Go through root pointers and mark all allocations found as reachable.

+	   The root pointers are:

+		1) The modules

+		2) The goalstack

+		3) The choicestack

+	*/

+	markmodules();

+	markgoalstack(goalstack);

+	markchoicestack();

+	/* Free the allocations that were not marked as reachable */

+	a = allocations;

+	while(a != nil){

+		if(a->reachable)

+			a = a->next;

+		else{

+			Allocation *tmp = a;

+			collected += a->size;

+			a = a->next;

+			freealloc(tmp);

+		}

+	}

+	return collected;

+}

+static void

+mark(void *ptr)

+{

+	if(ptr == nil)

+		return;

+	Allocation *a;

+	for(a = allocations; a != nil; a = a->next){

+		if(a->data == ptr)

+			a->reachable = 1;

+	}

+}

+static void

+freealloc(Allocation *a)

+{

+	if(a->prev)

+		a->prev->next = a->next;

+	else

+		allocations = a->next;

+	if(a->next)

+		a->next->prev = a->prev;

+	free(a->data);

+	free(a);

+}

+static void

+markmodules(void)

+{

+	Module *m;

+	for(m = modules; m != nil; m = m->next){

+		mark(m);

+		markpredicates(m->predicates);

+	}

+}

+static void

+markgoalstack(Goal *goals)

+{

+	Goal *g;

+	for(g = goals; g != nil; g = g->next){

+		mark(g);

+		markterm(g->goal);

+		markterm(g->catcher);

+	}

+}

+static void

+markchoicestack(void)

+{

+	Choicepoint *c;

+	for(c = choicestack; c != nil; c = c->next){

+		mark(c);

+		markgoalstack(c->goalstack);

+		markclauses(c->alternative);

+		markbindings(c->altbindings);

+	}

+}

+static void

+markpredicates(Predicate *preds)

+{

+	Predicate *p;

+	for(p = preds; p != nil; p = p->next){

+		mark(p);

+		markclauses(p->clauses);

+	}

+}

+static void

+markclauses(Clause *clauses)

+{

+	Clause *c;

+	for(c = clauses; c != nil; c = c->next){

+		mark(c);

+		markterm(c->head);

+		markterm(c->body);

+	}

+}

+static void

+markterm(Term *term)

+{

+	Term *t;

+	for(t = term; t != nil; t = t->next){

+		mark(t);

+		markterm(t->children);

+	}

+}

+static void

+markbindings(Binding *bindings)

+{

+	Binding *b;

+	for(b = bindings; b != nil; b = b->next){

+		mark(b);

+		markterm(b->value);

+	}

+}

\ No newline at end of file

--- a/misc.c

+++ b/misc.c

@@ -8,7 +8,7 @@

 Term *

 copyterm(Term *orig, uvlong *clausenr)

-	Term *new = malloc(sizeof(Term));

+	Term *new = gmalloc(sizeof(Term));

 	memcpy(new, orig, sizeof(Term));

 	new->next = nil;

 	new->children = nil;

@@ -47,7 +47,7 @@

 Term *

 mkterm(int tag)

-	Term *t = malloc(sizeof(Term));

+	Term *t = gmalloc(sizeof(Term));

 	t->tag = tag;

 	t->next = nil;

 	t->children = nil;

@@ -142,7 +142,7 @@

 Clause *

 copyclause(Clause *orig, uvlong *clausenr)

-	Clause *new = malloc(sizeof(Clause));

+	Clause *new = gmalloc(sizeof(Clause));

 	new->head = copyterm(orig->head, clausenr);

 	if(orig->body)

 		new->body = copyterm(orig->body, clausenr);

--- a/mkfile

+++ b/mkfile

@@ -15,7 +15,8 @@

 	streams.$O\

 	module.$O\

 	types.$O\

-	arithmetic.$O

+	arithmetic.$O\

+	garbage.$O

 HFILES=dat.h fns.h

--- a/module.c

+++ b/module.c

@@ -56,7 +56,7 @@

 	Predicate *currentpred = nil;

 	Term *t;

 	for(t = terms; t != nil; t = t->next){

-		Clause *cl = malloc(sizeof(Clause));

+		Clause *cl = gmalloc(sizeof(Clause));

 		int arity;

 		cl->clausenr = 0;

 		cl->next = nil;

@@ -78,7 +78,7 @@

 				m->predicates = appendpredicate(currentpred, m->predicates);

 			else

 				usermodule->predicates = appendpredicate(currentpred, usermodule->predicates);

-			currentpred = malloc(sizeof(Predicate));

+			currentpred = gmalloc(sizeof(Predicate));

 			currentpred->name = cl->head->text;

 			currentpred->arity = arity;

 			currentpred->clauses = cl;

@@ -109,7 +109,7 @@

 Module *

 addemptymodule(Rune *name)

-	Module *m = malloc(sizeof(Module));

+	Module *m = gmalloc(sizeof(Module));

 	m->name = name;

 	m->next = modules;

--- a/parser.c

+++ b/parser.c

@@ -264,8 +264,8 @@

 	int i;

 	int length = termslength(list);

 	Term *t;

-	Term **terms = malloc(sizeof(Term *) * length);

-	OpInfo *infos = malloc(sizeof(OpInfo) * length);

+	Term **terms = gmalloc(sizeof(Term *) * length);

+	OpInfo *infos = gmalloc(sizeof(OpInfo) * length);

 	for(i = 0, t = list; i < length; i++){

 		Operator *op = getoperator(t->text);

@@ -346,8 +346,6 @@

 	Term *result = terms[0];

-	free(infos);

-	free(terms);

 	return result;

@@ -409,6 +407,7 @@

 void

 addoperator(int level, int type, Rune *spelling)

+	/* the operator table is never garbage collected, so just use normal malloc */

 	Operator *op = malloc(sizeof(Operator));

 	op->type = type;

 	op->level = level;

@@ -431,7 +430,7 @@

 		for(tmp = operators[level]; tmp != nil; tmp = tmp->next){

 			if(runestrcmp(tmp->spelling, spelling) == 0){

 				if(op == nil){

-					op = malloc(sizeof(Operator));

+					op = gmalloc(sizeof(Operator));

 					memcpy(op, tmp, sizeof(Operator));

 				}else

 					op->type |= tmp->type;

--- a/repl.c

+++ b/repl.c

@@ -16,7 +16,7 @@

 		Term *query = parse(fd, nil, 1);

 		Binding *bindings = nil;

 		choicestack = nil;

-		goalstack = nil; /* should free old choicestack and goalstack */

+		goalstack = nil;

 		int success;

 		int firsttime = 1;

 FindMore:

@@ -50,6 +50,10 @@

 				print(".\n");

+		vlong amount = collectgarbage();

+		if(amount != 0)

+			print("Collected %lld bytes of garbage\n", amount);

--- a/streams.c

+++ b/streams.c

@@ -228,6 +228,7 @@

 Stream *

 openstreamfd(int fd, Biobuf *bio, int type, int mode)

+	/* streams are not garbage collected for now */

 	Stream *s = malloc(sizeof(Stream));

 	s->fd = fd;

 	s->bio = bio;