summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJohannes Weiner <hannes@cmpxchg.org>2010-02-10 17:34:50 +0100
committerJohannes Weiner <hannes@cmpxchg.org>2010-02-10 17:34:50 +0100
commitb7a5634a9cb85ea7884034ec7515edbf38ca2ed1 (patch)
treed9fab8940c922263bd1451ccdcfbbba2a99bcfa4
parenta5e33ab4ba32510700076288bab987cd3934e1ca (diff)
foreign: centralize foreign reference handling
Signed-off-by: Johannes Weiner <hannes@cmpxchg.org>
-rw-r--r--include/sheep/foreign.h59
-rw-r--r--include/sheep/function.h16
-rw-r--r--sheep/Makefile2
-rw-r--r--sheep/code.c1
-rw-r--r--sheep/compile.c70
-rw-r--r--sheep/core.c3
-rw-r--r--sheep/eval.c118
-rw-r--r--sheep/foreign.c205
-rw-r--r--sheep/function.c61
9 files changed, 281 insertions, 254 deletions
diff --git a/include/sheep/foreign.h b/include/sheep/foreign.h
new file mode 100644
index 0000000..7c37d72
--- /dev/null
+++ b/include/sheep/foreign.h
@@ -0,0 +1,59 @@
+/*
+ * include/sheep/foreign.h
+ *
+ * Copyright (c) 2010 Johannes Weiner <hannes@cmpxchg.org>
+ */
+#ifndef _SHEEP_FOREIGN_H
+#define _SHEEP_FOREIGN_H
+
+#include <sheep/function.h>
+#include <sheep/vector.h>
+#include <sheep/vm.h>
+
+/**
+ * struct sheep_freevar - lexical free variable location
+ * @dist: functional distance
+ * @slot: index of an immediate parent slot
+ *
+ * @slot indexes a local slot if @dist is 1 and a foreign slot
+ * otherwise.
+ */
+struct sheep_freevar {
+ unsigned int dist;
+ unsigned int slot;
+};
+
+/**
+ * struct sheep_indirect - indirect slot pointer
+ * @count: user count, negative if slot is live
+ * @index: live stack slot index
+ * @next: list linkage of live slots
+ * @closed: preserved value slot
+ */
+struct sheep_indirect {
+ int count;
+ union {
+ struct {
+ unsigned int index;
+ struct sheep_indirect *next;
+ } live;
+ sheep_t closed;
+ } value;
+};
+
+/* compile-time */
+unsigned int sheep_foreign_slot(struct sheep_function *,
+ unsigned int, unsigned int);
+void sheep_foreign_propagate(struct sheep_function *, struct sheep_function *);
+
+/* eval-time */
+struct sheep_vector *sheep_foreign_open(struct sheep_vm *, unsigned long,
+ struct sheep_function *,
+ struct sheep_function *);
+void sheep_foreign_save(struct sheep_vm *, unsigned long);
+
+/* life-time */
+void sheep_foreign_mark(struct sheep_vector *);
+void sheep_foreign_release(struct sheep_vm *, struct sheep_vector *);
+
+#endif /* _SHEEP_FOREIGN_H */
diff --git a/include/sheep/function.h b/include/sheep/function.h
index d7a6d08..3e78fcc 100644
--- a/include/sheep/function.h
+++ b/include/sheep/function.h
@@ -12,22 +12,6 @@
struct sheep_vm;
-struct sheep_freevar {
- unsigned int dist;
- unsigned int slot;
-};
-
-struct sheep_indirect {
- int count;
- union {
- struct {
- unsigned int index;
- struct sheep_indirect *next;
- } live;
- sheep_t closed;
- } value;
-};
-
struct sheep_function {
struct sheep_code code;
unsigned int nr_locals;
diff --git a/sheep/Makefile b/sheep/Makefile
index 58d9f4a..b426a6f 100644
--- a/sheep/Makefile
+++ b/sheep/Makefile
@@ -1,5 +1,5 @@
sheep-obj := util.o vector.o map.o code.o gc.o
sheep-obj += object.o bool.o string.o name.o number.o list.o \
- sequence.o function.o alien.o
+ sequence.o foreign.o function.o alien.o
sheep-obj += unpack.o vm.o module.o read.o parse.o compile.o eval.o core.o
sheep-obj += main.o
diff --git a/sheep/code.c b/sheep/code.c
index 4552913..b5f4e87 100644
--- a/sheep/code.c
+++ b/sheep/code.c
@@ -4,6 +4,7 @@
* Copyright (c) 2009 Johannes Weiner <hannes@cmpxchg.org>
*/
#include <sheep/function.h>
+#include <sheep/foreign.h>
#include <sheep/object.h>
#include <sheep/string.h>
#include <sheep/vm.h>
diff --git a/sheep/compile.c b/sheep/compile.c
index bfaba43..a737238 100644
--- a/sheep/compile.c
+++ b/sheep/compile.c
@@ -4,6 +4,7 @@
* Copyright (c) 2009 Johannes Weiner <hannes@cmpxchg.org>
*/
#include <sheep/function.h>
+#include <sheep/foreign.h>
#include <sheep/vector.h>
#include <sheep/parse.h>
#include <sheep/code.h>
@@ -99,35 +100,6 @@ static enum env_level lookup_env(struct sheep_compile *compile,
return ENV_FOREIGN;
}
-static unsigned int slot_foreign(struct sheep_function *function,
- unsigned int dist, unsigned int slot)
-{
- struct sheep_vector *foreign = function->foreign;
- struct sheep_freevar *freevar;
-
- if (!foreign) {
- foreign = sheep_zalloc(sizeof(struct sheep_vector));
- function->foreign = foreign;
- } else {
- unsigned int i;
-
- for (i = 0; i < foreign->nr_items; i++) {
- freevar = foreign->items[i];
- if (freevar->dist != dist)
- continue;
- if (freevar->slot != slot)
- continue;
- return i;
- }
- }
-
- freevar = sheep_malloc(sizeof(struct sheep_freevar));
- freevar->dist = dist;
- freevar->slot = slot;
-
- return sheep_vector_push(foreign, freevar);
-}
-
static int compile_simple_name(struct sheep_compile *compile,
struct sheep_function *function,
struct sheep_context *context,
@@ -153,7 +125,7 @@ static int compile_simple_name(struct sheep_compile *compile,
sheep_emit(&function->code, SHEEP_GLOBAL, slot);
break;
case ENV_FOREIGN:
- slot = slot_foreign(function, dist, slot);
+ slot = sheep_foreign_slot(function, dist, slot);
if (set)
sheep_emit(&function->code, SHEEP_SET_FOREIGN, slot);
sheep_emit(&function->code, SHEEP_FOREIGN, slot);
@@ -289,41 +261,3 @@ int sheep_compile_list(struct sheep_compile *compile,
}
return compile_call(compile, function, context, list);
}
-
-/**
- * sheep_propagate_foreigns
- * @function: container function
- * @childfun: newly defined child of @function
- *
- * This is called for every nested function with free variable
- * references, the foreign slots propagate upwards recursively.
- *
- * (function one (x)
- * (function two ()
- * (function three ()
- * x)))
- *
- * At the time (three) is defined, (one) with its `x' is long gone.
- * The reference from (three) to `x' must be relayed through (two).
- *
- * Allocate a foreign slot from (two) to `x' and relocate the
- * reference in (three) to the intermediate slot.
- */
-void sheep_propagate_foreigns(struct sheep_function *function,
- struct sheep_function *childfun)
-{
- unsigned long i;
-
- for (i = 0; i < childfun->foreign->nr_items; i++) {
- struct sheep_freevar *var;
-
- var = childfun->foreign->items[i];
- if (var->dist == 1)
- continue;
- /*
- * Relocate the reference from the child through a
- * foreign reference in the immediate parent.
- */
- var->slot = slot_foreign(function, var->dist - 1, var->slot);
- }
-}
diff --git a/sheep/core.c b/sheep/core.c
index a861ecc..52c7c74 100644
--- a/sheep/core.c
+++ b/sheep/core.c
@@ -4,6 +4,7 @@
* Copyright (c) 2009 Johannes Weiner <hannes@cmpxchg.org>
*/
#include <sheep/function.h>
+#include <sheep/foreign.h>
#include <sheep/compile.h>
#include <sheep/module.h>
#include <sheep/parse.h>
@@ -254,7 +255,7 @@ static int compile_function(struct sheep_compile *compile,
}
sheep_code_finalize(&childfun->code);
if (childfun->foreign)
- sheep_propagate_foreigns(function, childfun);
+ sheep_foreign_propagate(function, childfun);
out:
sheep_map_drain(&env);
return ret;
diff --git a/sheep/eval.c b/sheep/eval.c
index 3c753ed..28684f4 100644
--- a/sheep/eval.c
+++ b/sheep/eval.c
@@ -4,6 +4,7 @@
* Copyright (c) 2009 Johannes Weiner <hannes@cmpxchg.org>
*/
#include <sheep/function.h>
+#include <sheep/foreign.h>
#include <sheep/object.h>
#include <sheep/alien.h>
#include <sheep/bool.h>
@@ -18,125 +19,22 @@
#include <sheep/eval.h>
-/**
- * open_indirect
- * @vm: runtime
- * @index: stack index into @vm->stack.items
- *
- * Open an indirect pointer to the stack slot at @index. The value
- * will be preserved when the slot is about to leave the stack.
- *
- * Returns an indirect pointer descriptor shared by every function
- * referencing @index indirectly.
- */
-static struct sheep_indirect *open_indirect(struct sheep_vm *vm,
- unsigned long index)
-{
- struct sheep_indirect *new, *prev = NULL, *next = vm->pending;
-
- while (next) {
- if (index == next->value.live.index) {
- next->count--;
- return next;
- }
- if (index > next->value.live.index)
- break;
- prev = next;
- next = next->value.live.next;
- }
-
- new = sheep_malloc(sizeof(struct sheep_indirect));
- new->count = -1;
- new->value.live.index = index;
- new->value.live.next = next;
- if (prev)
- prev->value.live.next = new;
- else
- vm->pending = new;
-
- return new;
-}
-
static sheep_t closure(struct sheep_vm *vm, unsigned long basep,
struct sheep_function *parent, sheep_t sheep)
{
- struct sheep_function *function, *closure;
- struct sheep_vector *freevars, *indirects;
- unsigned int i;
-
- sheep_bug_on(sheep_type(sheep) != &sheep_function_type);
- function = sheep_data(sheep);
+ struct sheep_function *function = sheep_data(sheep);
+ struct sheep_function *closure;
if (!function->foreign)
return sheep;
- freevars = function->foreign;
- indirects = sheep_zalloc(sizeof(struct sheep_vector));
-
- for (i = 0; i < freevars->nr_items; i++) {
- struct sheep_indirect *indirect;
- struct sheep_freevar *freevar;
- /*
- * Okay, here we translate lexical coordinates of free
- * variable references to indirect pointers into the
- * stack or to slots that already left the stack.
- *
- * If the referenced slot is bound by @parent,
- * i.e. the reference distance is one, we know that
- * @parent is living on the stack right now and
- * establish an indirect pointer to its local slot
- * identified by freevar->slot.
- *
- * Otherwise, the reference distance is bigger and
- * @parent has the slot not bound itself. In this
- * case, freevar->slot identifies a _foreign_ slot in
- * @parent. It exists in any case: either @parent
- * refers to the value itself or it kindly relays the
- * reference for us. See sheep_propagate_foreigns()
- * and how it is used.
- */
- freevar = freevars->items[i];
- if (freevar->dist == 1)
- indirect = open_indirect(vm, basep + freevar->slot);
- else {
- indirect = parent->foreign->items[freevar->slot];
- /*
- * The value slot might already be closed
- * over, which is reflected by the sign of the
- * use count. Take care of it.
- */
- if (indirect->count < 0)
- indirect->count--;
- else
- indirect->count++;
- }
- sheep_vector_push(indirects, indirect);
- }
-
sheep = sheep_closure_function(vm, function);
closure = sheep_data(sheep);
- closure->foreign = indirects;
+ closure->foreign = sheep_foreign_open(vm, basep, parent, function);
return sheep;
}
-static void close_indirect(struct sheep_vm *vm, unsigned long basep)
-{
- while (vm->pending) {
- struct sheep_indirect *indirect = vm->pending;
- unsigned long index;
-
- index = indirect->value.live.index;
- if (index < basep)
- break;
-
- vm->pending = indirect->value.live.next;
-
- indirect->count = -indirect->count;
- indirect->value.closed = vm->stack.items[index];
- }
-}
-
static int precall(struct sheep_vm *vm, sheep_t callable, unsigned int nr_args,
sheep_t *value)
{
@@ -230,7 +128,7 @@ sheep_t sheep_eval(struct sheep_vm *vm, sheep_t function)
break;
case SHEEP_FOREIGN:
indirect = current->foreign->items[arg];
- if (indirect->count > 0)
+ if (indirect->count < 0)
tmp = indirect->value.closed;
else {
unsigned long index;
@@ -243,7 +141,7 @@ sheep_t sheep_eval(struct sheep_vm *vm, sheep_t function)
case SHEEP_SET_FOREIGN:
tmp = sheep_vector_pop(&vm->stack);
indirect = current->foreign->items[arg];
- if (indirect->count > 0)
+ if (indirect->count < 0)
indirect->value.closed = tmp;
else {
unsigned long index;
@@ -276,7 +174,7 @@ sheep_t sheep_eval(struct sheep_vm *vm, sheep_t function)
sheep_vector_push(&vm->stack, tmp);
break;
default:
- close_indirect(vm, basep);
+ sheep_foreign_save(vm, basep);
splice_arguments(vm, basep, arg);
sheep_unprotect(vm, function);
@@ -320,7 +218,7 @@ sheep_t sheep_eval(struct sheep_vm *vm, sheep_t function)
sheep_bug_on(vm->stack.nr_items -
basep - current->nr_locals != 1);
- close_indirect(vm, basep);
+ sheep_foreign_save(vm, basep);
if (current->nr_locals) {
vm->stack.items[basep] =
diff --git a/sheep/foreign.c b/sheep/foreign.c
new file mode 100644
index 0000000..bc328ee
--- /dev/null
+++ b/sheep/foreign.c
@@ -0,0 +1,205 @@
+/*
+ * sheep/foreign.c
+ *
+ * Copyright (c) 2010 Johannes Weiner <hannes@cmpxchg.org>
+ */
+#include <sheep/function.h>
+#include <sheep/vector.h>
+#include <sheep/util.h>
+#include <sheep/gc.h>
+#include <sheep/vm.h>
+
+#include <sheep/foreign.h>
+
+/* foreign slot allocation at compile time */
+unsigned int sheep_foreign_slot(struct sheep_function *function,
+ unsigned int dist, unsigned int slot)
+{
+ struct sheep_freevar *freevar;
+ struct sheep_vector *foreign;
+
+ foreign = function->foreign;
+ if (!foreign) {
+ foreign = sheep_zalloc(sizeof(struct sheep_vector));
+ function->foreign = foreign;
+ } else {
+ unsigned int i;
+
+ for (i = 0; i < foreign->nr_items; i++) {
+ freevar = foreign->items[i];
+
+ if (freevar->dist != dist)
+ continue;
+ if (freevar->slot != slot)
+ continue;
+
+ return i;
+ }
+ }
+
+ freevar = sheep_malloc(sizeof(struct sheep_freevar));
+ freevar->dist = dist;
+ freevar->slot = slot;
+
+ return sheep_vector_push(foreign, freevar);
+}
+
+/* foreign slot upward propagation at function finalization */
+void sheep_foreign_propagate(struct sheep_function *parent,
+ struct sheep_function *child)
+{
+ unsigned int i;
+
+ for (i = 0; i < child->foreign->nr_items; i++) {
+ struct sheep_freevar *freevar;
+ unsigned int dist, slot;
+
+ freevar = child->foreign->items[i];
+
+ /* Child refers to parent slot */
+ if (freevar->dist == 1)
+ continue;
+ /*
+ * Child refers to grand-parent slot, relay through
+ * parent.
+ */
+ dist = freevar->dist - 1;
+ slot = freevar->slot;
+ freevar->slot = sheep_foreign_slot(parent, dist, slot);
+ }
+}
+
+static struct sheep_indirect *open_indirect(struct sheep_vm *vm,
+ unsigned long index)
+{
+ struct sheep_indirect *new, *prev = NULL, *next = vm->pending;
+
+ while (next) {
+ if (index == next->value.live.index) {
+ next->count++;
+ return next;
+ }
+ if (index > next->value.live.index)
+ break;
+ prev = next;
+ next = next->value.live.next;
+ }
+
+ new = sheep_malloc(sizeof(struct sheep_indirect));
+ new->count = 1;
+ new->value.live.index = index;
+ new->value.live.next = next;
+ if (prev)
+ prev->value.live.next = new;
+ else
+ vm->pending = new;
+
+ return new;
+}
+
+/* indirect pointer establishing at closure creation */
+struct sheep_vector *sheep_foreign_open(struct sheep_vm *vm,
+ unsigned long basep,
+ struct sheep_function *parent,
+ struct sheep_function *child)
+{
+ struct sheep_vector *freevars = child->foreign;
+ struct sheep_vector *indirects;
+ unsigned int i;
+
+ indirects = sheep_zalloc(sizeof(struct sheep_vector));
+
+ for (i = 0; i < freevars->nr_items; i++) {
+ struct sheep_indirect *indirect;
+ struct sheep_freevar *freevar;
+
+ freevar = freevars->items[i];
+ if (freevar->dist == 1)
+ indirect = open_indirect(vm, basep + freevar->slot);
+ else {
+ indirect = parent->foreign->items[freevar->slot];
+ if (indirect->count < 0)
+ indirect->count--;
+ else
+ indirect->count++;
+ }
+ sheep_vector_push(indirects, indirect);
+ }
+ return indirects;
+}
+
+/* indirect pointer preservation at owner death */
+void sheep_foreign_save(struct sheep_vm *vm, unsigned long basep)
+{
+ while (vm->pending) {
+ struct sheep_indirect *indirect = vm->pending;
+ unsigned long index;
+
+ index = indirect->value.live.index;
+ if (index < basep)
+ break;
+
+ vm->pending = indirect->value.live.next;
+
+ indirect->count = -indirect->count;
+ indirect->value.closed = vm->stack.items[index];
+ }
+}
+
+/* mark reachable indirect pointers */
+void sheep_foreign_mark(struct sheep_vector *foreign)
+{
+ unsigned int i;
+
+ for (i = 0; i < foreign->nr_items; i++) {
+ struct sheep_indirect *indirect;
+
+ indirect = foreign->items[i];
+ if (indirect->count < 0)
+ sheep_mark(indirect->value.closed);
+ }
+}
+
+static void unlink_live(struct sheep_vm *vm, struct sheep_indirect *indirect)
+{
+ struct sheep_indirect *prev = NULL, *this = vm->pending;
+
+ while (this) {
+ struct sheep_indirect *next;
+
+ next = this->value.live.next;
+ if (this == indirect) {
+ if (prev)
+ prev->value.live.next = next;
+ else
+ vm->pending = next;
+ return;
+ }
+ prev = this;
+ this = next;
+ }
+ sheep_bug("unqueued live indirect pointer");
+}
+
+/* indirect pointer release at closure death */
+void sheep_foreign_release(struct sheep_vm *vm, struct sheep_vector *foreign)
+{
+ unsigned int i;
+
+ for (i = 0; i < foreign->nr_items; i++) {
+ struct sheep_indirect *indirect;
+
+ indirect = foreign->items[i];
+ if (indirect->count > 0) {
+ if (--indirect->count == 0) {
+ unlink_live(vm, indirect);
+ sheep_free(indirect);
+ }
+ } else {
+ if (++indirect->count == 0)
+ sheep_free(indirect);
+ }
+ }
+ sheep_free(foreign->items);
+ sheep_free(foreign);
+}
diff --git a/sheep/function.c b/sheep/function.c
index 1be9b8d..2b36e2d 100644
--- a/sheep/function.c
+++ b/sheep/function.c
@@ -3,6 +3,7 @@
*
* Copyright (c) 2009 Johannes Weiner <hannes@cmpxchg.org>
*/
+#include <sheep/foreign.h>
#include <sheep/object.h>
#include <sheep/unpack.h>
#include <sheep/bool.h>
@@ -53,68 +54,12 @@ const struct sheep_type sheep_function_type = {
.format = format_function,
};
-static void mark_indirect(struct sheep_vector *foreign)
-{
- unsigned int i;
-
- for (i = 0; i < foreign->nr_items; i++) {
- struct sheep_indirect *indirect;
-
- indirect = foreign->items[i];
- if (indirect->count > 0)
- sheep_mark(indirect->value.closed);
- }
-}
-
static void mark_closure(sheep_t sheep)
{
struct sheep_function *closure;
closure = sheep_data(sheep);
- mark_indirect(closure->foreign);
-}
-
-static void unlink_pending(struct sheep_vm *vm, struct sheep_indirect *indirect)
-{
- struct sheep_indirect *prev = NULL, *this = vm->pending;
-
- while (this) {
- struct sheep_indirect *next;
-
- next = this->value.live.next;
- if (this == indirect) {
- if (prev)
- prev->value.live.next = next;
- else
- vm->pending = next;
- return;
- }
- prev = this;
- this = next;
- }
- sheep_bug("unqueued live foreign reference");
-}
-
-static void put_indirect(struct sheep_vm *vm, struct sheep_vector *foreign)
-{
- unsigned int i;
-
- for (i = 0; i < foreign->nr_items; i++) {
- struct sheep_indirect *indirect;
-
- indirect = foreign->items[i];
- if (indirect->count < 0) { /* live */
- if (++indirect->count == 0) {
- unlink_pending(vm, indirect);
- sheep_free(indirect);
- }
- } else { /* closed */
- if (--indirect->count == 0)
- sheep_free(indirect);
- }
- }
- sheep_free(foreign->items);
- sheep_free(foreign);
+ sheep_foreign_mark(closure->foreign);
}
static void free_closure(struct sheep_vm *vm, sheep_t sheep)
@@ -122,7 +67,7 @@ static void free_closure(struct sheep_vm *vm, sheep_t sheep)
struct sheep_function *closure;
closure = sheep_data(sheep);
- put_indirect(vm, closure->foreign);
+ sheep_foreign_release(vm, closure->foreign);
sheep_free(closure->name);
sheep_free(closure);
}