vm: rework object iteration

Ensure that deleting object keys during iteration is safe by keeping a
global chain of per-object iterators which are advanced to the next key
when the entry that is about to be iterated is deleted.

Signed-off-by: Jo-Philipp Wich <jo@mein.io>

5 files changed, 203 insertions, 36 deletions

diff --git a/include/ucode/types.h b/include/ucode/types.h
index 7fcc7f1..c0ccd38 100644
--- a/include/ucode/types.h
+++ b/include/ucode/types.h
@@ -207,6 +207,16 @@ typedef struct {
 uc_declare_vector(uc_resource_types_t, uc_resource_type_t *);
 
 
+/* Object iteration */
+
+extern uc_list_t uc_object_iterators;
+
+typedef struct {
+	uc_list_t list;
+	struct lh_entry *pos;
+} uc_object_iterator_t;
+
+
 /* Program structure definitions */
 
 uc_declare_vector(uc_sources_t, uc_source_t *);
diff --git a/include/ucode/util.h b/include/ucode/util.h
index 52303cc..a3692d5 100644
--- a/include/ucode/util.h
+++ b/include/ucode/util.h
@@ -79,6 +79,32 @@
 } while(0)
 
 
+/* linked lists */
+
+typedef struct uc_list {
+	struct uc_list *prev;
+	struct uc_list *next;
+} uc_list_t;
+
+static inline void uc_list_insert(uc_list_t *list, uc_list_t *item)
+{
+	list->next->prev = item;
+	item->next = list->next;
+	item->prev = list;
+	list->next = item;
+}
+
+static inline void uc_list_remove(uc_list_t *item)
+{
+	item->next->prev = item->prev;
+	item->prev->next = item->next;
+	item->prev = item->next = item;
+}
+
+#define uc_list_foreach(item, list) \
+	for (uc_list_t *item = (list)->next; item != (list); item = item->next)
+
+
 /* "failsafe" utility functions */
 
 static inline void *xcalloc(size_t size, size_t nmemb) {
diff --git a/tests/custom/02_runtime/08_object_iteration b/tests/custom/02_runtime/08_object_iteration
new file mode 100644
index 0000000..2e58cdf
--- /dev/null
+++ b/tests/custom/02_runtime/08_object_iteration
@@ -0,0 +1,51 @@
+Testing object iteration behavior.
+
+
+1. Testing that deleting properties during iteration is safe.
+
+-- Expect stdout --
+a
+w
+z
+-- End --
+
+-- Testcase --
+{%
+	o1 = { a: 1, b: 2, c: 3 };
+
+	for (k in o1) {
+		delete o1.a;
+		delete o1.b;
+		delete o1.c;
+		print(k, "\n");
+	}
+
+	o2 = { w: 1, x: 2, y: 3, z: 4 };
+
+	for (k in o2) {
+		delete o2.x;
+		delete o2.y;
+		print(k, "\n");
+	}
+%}
+-- End --
+
+
+2. Test that reordering object properties during iteration is safe.
+
+-- Expect stdout --
+c
+b
+c
+-- End --
+
+-- Testcase --
+{%
+	o = { c: 1, b: 2, a: 3 };
+
+	for (k in o) {
+		sort(o);
+		print(k, "\n");
+	}
+%}
+-- End --
diff --git a/types.c b/types.c
index eeac8c7..84a7b17 100644
--- a/types.c
+++ b/types.c
@@ -29,6 +29,11 @@
 #include "ucode/vm.h"
 #include "ucode/program.h"
 
+uc_list_t uc_object_iterators = {
+	.prev = &uc_object_iterators,
+	.next = &uc_object_iterators
+};
+
 static char *uc_default_search_path[] = { LIB_SEARCH_PATH };
 
 uc_parse_config_t uc_default_parse_config = {
@@ -888,6 +893,13 @@ ucv_array_length(uc_value_t *uv)
 static void
 ucv_free_object_entry(struct lh_entry *entry)
 {
+	uc_list_foreach(item, &uc_object_iterators) {
+		uc_object_iterator_t *iter = (uc_object_iterator_t *)item;
+
+		if (iter->pos == entry)
+			iter->pos = entry->next;
+	}
+
 	free(lh_entry_k(entry));
 	ucv_put(lh_entry_v(entry));
 }
diff --git a/vm.c b/vm.c
index 3b7cb7c..4642380 100644
--- a/vm.c
+++ b/vm.c
@@ -2173,62 +2173,130 @@ uc_vm_insn_jmpz(uc_vm_t *vm, uc_vm_insn_t insn)
 	ucv_put(v);
 }
 
+
 static void
-uc_vm_insn_next(uc_vm_t *vm, uc_vm_insn_t insn)
+uc_vm_object_iterator_free(void *ud)
 {
-	uc_value_t *k = uc_vm_stack_pop(vm);
-	uc_value_t *v = uc_vm_stack_pop(vm);
-	void *end = (void *)~(uintptr_t)0;
-	uc_resource_t *iterk;
-	struct lh_entry *curr;
-	uint64_t n;
+	uc_object_iterator_t *iter = ud;
 
-	if (k != NULL && ucv_type(k) != UC_RESOURCE) {
-		fprintf(stderr, "Invalid iterator value\n");
-		abort();
+	uc_list_remove(&iter->list);
+}
+
+static uc_resource_type_t uc_vm_object_iterator_type = {
+	.name = "object iterator",
+	.free = uc_vm_object_iterator_free
+};
+
+static bool
+uc_vm_object_iterator_next(uc_vm_t *vm, uc_vm_insn_t insn,
+                           uc_value_t *k, uc_value_t *v)
+{
+	uc_resource_t *res = (uc_resource_t *)k;
+	uc_object_t *obj = (uc_object_t *)v;
+	uc_object_iterator_t *iter;
+
+	if (!res) {
+		/* object is empty */
+		if (!obj->table->head)
+			return false;
+
+		res = xalloc(sizeof(*res) + sizeof(uc_object_iterator_t));
+		res->header.type = UC_RESOURCE;
+		res->header.refcount = 1;
+		res->type = &uc_vm_object_iterator_type;
+
+		iter = res->data = (char *)res + sizeof(*res);
+		iter->pos = obj->table->head;
+
+		uc_list_insert(&uc_object_iterators, &iter->list);
 	}
+	else if (ucv_type(k) == UC_RESOURCE &&
+	         res->type == &uc_vm_object_iterator_type && res->data != NULL) {
 
-	if (k == NULL)
-		k = ucv_resource_new(NULL, NULL);
+		iter = res->data;
+	}
+	else {
+		uc_vm_raise_exception(vm, EXCEPTION_TYPE, "Invalid object iterator");
 
-	iterk = (uc_resource_t *)k;
+		return false;
+	}
 
-	switch (ucv_type(v)) {
-	case UC_OBJECT:
-		curr = iterk->data ? iterk->data : ((uc_object_t *)v)->table->head;
+	/* no next key */
+	if (!iter->pos) {
+		uc_list_remove(&iter->list);
 
-		if (curr != NULL && curr != end) {
-			iterk->data = curr->next ? curr->next : end;
+		return false;
+	}
 
-			uc_vm_stack_push(vm, ucv_string_new(curr->k));
+	uc_vm_stack_push(vm, ucv_string_new(iter->pos->k));
 
-			if (insn == I_NEXTKV)
-				uc_vm_stack_push(vm, ucv_get((uc_value_t *)curr->v));
+	if (insn == I_NEXTKV)
+		uc_vm_stack_push(vm, ucv_get((uc_value_t *)iter->pos->v));
 
-			uc_vm_stack_push(vm, k);
-			ucv_put(v);
+	uc_vm_stack_push(vm, &res->header);
+	ucv_put(v);
 
-			return;
-		}
+	iter->pos = iter->pos->next;
 
-		break;
+	return true;
+}
 
-	case UC_ARRAY:
-		n = (uintptr_t)iterk->data;
+static bool
+uc_vm_array_iterator_next(uc_vm_t *vm, uc_vm_insn_t insn,
+                          uc_value_t *k, uc_value_t *v)
+{
+	uint64_t n;
+
+	if (!k) {
+		/* array is empty */
+		if (!ucv_array_length(v))
+			return false;
+
+		k = ucv_resource_new(NULL, NULL);
+		n = 0;
+	}
+	else if (ucv_type(k) == UC_RESOURCE) {
+		n = (uintptr_t)ucv_resource_data(k, NULL);
+	}
+	else {
+		uc_vm_raise_exception(vm, EXCEPTION_TYPE, "Invalid array iterator");
 
-		if (n < ucv_array_length(v)) {
-			iterk->data = (void *)(uintptr_t)(n + 1);
+		return false;
+	}
 
-			if (insn == I_NEXTKV)
-				uc_vm_stack_push(vm, ucv_uint64_new(n));
+	/* no next index */
+	if (n >= ucv_array_length(v))
+		return false;
 
-			uc_vm_stack_push(vm, ucv_get(ucv_array_get(v, n)));
+	if (insn == I_NEXTKV)
+		uc_vm_stack_push(vm, ucv_uint64_new(n));
 
-			uc_vm_stack_push(vm, k);
-			ucv_put(v);
+	uc_vm_stack_push(vm, ucv_get(ucv_array_get(v, n)));
+
+	uc_vm_stack_push(vm, k);
+	ucv_put(v);
+
+	((uc_resource_t *)k)->data = (void *)(uintptr_t)(n + 1);
 
+	return true;
+}
+
+static void
+uc_vm_insn_next(uc_vm_t *vm, uc_vm_insn_t insn)
+{
+	uc_value_t *k = uc_vm_stack_pop(vm);
+	uc_value_t *v = uc_vm_stack_pop(vm);
+
+	switch (ucv_type(v)) {
+	case UC_OBJECT:
+		if (uc_vm_object_iterator_next(vm, insn, k, v))
+			return;
+
+		break;
+
+	case UC_ARRAY:
+		if (uc_vm_array_iterator_next(vm, insn, k, v))
 			return;
-		}
 
 		break;