From ee4af9b55cb4591e63c596af592abc33a8a8f315 Mon Sep 17 00:00:00 2001 From: Jo-Philipp Wich Date: Tue, 20 Feb 2024 17:30:38 +0100 Subject: 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 --- include/ucode/types.h | 10 ++ include/ucode/util.h | 26 ++++++ tests/custom/02_runtime/08_object_iteration | 51 ++++++++++ types.c | 12 +++ vm.c | 140 +++++++++++++++++++++------- 5 files changed, 203 insertions(+), 36 deletions(-) create mode 100644 tests/custom/02_runtime/08_object_iteration 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; -- cgit v1.2.3